Skip to content

Latest commit

 

History

History
113 lines (77 loc) · 8.42 KB

intro.md

File metadata and controls

113 lines (77 loc) · 8.42 KB
Raw

大实验参考文档

注：大实验文档目前还在完善中，会不断迭代更新。如果对于评分部分有更新，会通知所有选择大实验的同学。

介绍

大实验编译器目标：完成一个具有编译优化功能的高性能编译器。部分达到系统能力设计大赛——编译系统设计赛的要求。

参加大实验的同学应该需要自己从头设计一个符合 minidecaf 规范 的编译器，包括前端、中端和后端。参加大实验可以替代期末考试，详见评分方法一节。

有两个原因我们要求同学们从头设计一个编译器：

  1. 为了简化课程实验，我们的基础实验框架在设计时并未考虑大实验的需求（例如：IR 的类型系统简易、没有区分基本块），在现有框架的基础上重构实现编译优化反而在一定程度上限制了编译器的优化能力。
  2. 大实验设计的其中一个目标是鼓励同学们参加系统能力设计大赛，比赛有查重要求，如果同学们使用相同的框架开始参加大实验并参与后续比赛，可能存在代码被判定为重复的问题。

大实验在 2024 年相对于 2023 年有一些变化，主要体现在：

  • 增加了实验文档
  • 语法要求从 Sysy 语法改为了 MiniDecaf，主要差别在于const标志符号、数组初始化等语法上的区别，难度有所降低
  • 不再要求完成基础实验以后再进行大实验

大实验的语法规范与 step12 的规范是一致的。不过有一点需要注意：

  • 我们要求实现函数声明，即一个函数可以只有声明没有定义，主要是用于评测性能，比如读入数据和打印结果，我们将会把你的代码和一个外部库进行链接编译。这意味着，你需要实现标准的 RiscV 调用约定。

你可以选择 C++，Rust 实现你的编译器，你的编译器生成的目标代码可以是 RISC-V 或者 ARM 架构的，这与比赛要求一致。如果你想用其他语言实现，请告知助教。

大实验为组队实验，4人一组（可以更少，但是评分标准保持不变）。没有特殊情况时，同组同分。

注意：大实验工作量较大，并不推荐所有同学都参加。

编译器的构成

一个编译器主要由以下几个部分构成：

  • 前端：负责词法分析、语法分析、语义分析，生成抽象语法树（AST）。
    • 词法分析器（Lexer）：将输入的源代码转换为一个个的标记（Token）。
    • 语法分析器（Parser）：将标记（Token）转换为抽象语法树（AST）。
    • 语义分析器（Semantic Analyzer）：检查AST是否符合语法规则和语义规则。
  • 中端：负责中间代码生成、优化。
    • 中间代码生成器（Intermediate Representation Generator）：将 AST 转换为中间代码。
    • 优化器（Optimizer）：对中间代码进行优化。
  • 后端：负责目标代码生成。
    • 目标代码生成器（Target Code Generator）：将优化后的中间代码转换为目标机器代码。
    • 寄存器分配：将中间代码中的变量分配到实际的物理寄存器中。

可以通过后续的文档了解每个部分的更多细节。

参考实现进度及顺序

  1. 编写前端、设计 IR、完成中间代码生成 (两周)

    • 前端：你可以使用现有的框架完成前端（如：Antlr、Flex & Bison）辅助你生成 AST，完成词法分析、语法分析、语义分析以及中间代码生成。如果你想在这个过程中锻炼你对分析方法的理解，你可以自己实现 LR(1)、LL(1) 等分析器。
    • 设计 IR 也是需要进行代码编写的，可以参考基础实验框架的IR在代码层面是如何实现的（utils/tac）。
    • 中间代码生成：将 AST 转换为 IR，你可以参考基础实验框架的中间代码生成部分（frontend/tacgen）。

    此阶段分工建议：两位同学负责前端，两位同学负责中间表示设计和中间代码生成。

  2. 完成后端（两周）

    • 实现后端代码生成、栈帧管理
    • 实现一个简单的寄存器分配方案，保证编译器能够完成全流程的运行，然后再考虑优化。

  3. 增加中端优化和后端优化（剩下的时间）

    • 中端优化：死代码消除、常量传播、复写传播、循环不变量外提等等
    • 后端优化：图染色寄存器分配、线性扫描法、指令折叠等等

    分工建议：两位同学负责中端优化，两位同学负责后端优化。

进度检查

  • 第一次进度检查：第六周周六（10.19）

    • 你的编译器应该能完成将简单的程序转换为 RISC-V 汇编代码，可以选择在这次检查时退出大实验。如果退出大实验，你需要在第八周周日（11.3）Stage 3 截止之前完成 Stage 1-3 的实验，不会有额外扣分。

  • 第二次进度检查（中期检查）：第八周周六（11.2）

    • 这时候你的编译器应该能通过基础实验的所有测试样例（Stage 1-5）。如果不能完成，可能会被取消大实验的资格，同时你需要重新完成基础实验你需要在第十周周日（11.17）Stage 4 截止前完成 Stage 1-4 ，不额外扣分。也可以继续大实验不做基础实验，但是至少要在 Stage-5 让你的编译器能够通过 Stage 1-5 的测试样例。
    • 你们需要提交一个简单的报告，说明每个同学在实验过程中的分工以及完成的功能。（如果缺少这部分实验报告，那么报告成绩将会被扣除5分（总评 5%））

  • 第三次进度检查：第十二周周六（11.30）

    • 你们需要提交一个简单的报告，说明每个同学在上次检查后的分工以及完成的功能。（如果缺少这部分实验报告，那么报告成绩将会被扣除 5 分（总评 5%））

  • 第四次进度检查（期末检查）：第十六周周末（12.29）

    • 你的编译器应该能通过所有的测试样例（Stage 1-6），包括附加测试样例。
    • 你应该提交一个完整的实验报告，包括实验的设计、实现、优化以及遇到的问题和解决方法。不需要卷页数，但应该说明了你们实现的功能。（如果缺少这部分实验报告，你将不会得到任何报告成绩）

评分方法

因为大实验实现难度较高且工作量较大，优化目标可能相对难以完成，因此我们给出两种评分方案：

  • 选项一 完成竞赛第二阶段的优化编译器，替代期末考试

    成绩占比 90%，剩余 10% 为书面作业和日常成绩。

    其中这90%构成为：

    • 50% 正确性测试：你需要通过 Stage 1-6 的所有测试样例以及附加测试的测试样例，这样你可以获得 50% 的正确性得分。
    • 10% 报告，介绍你的编译器的设计、你们进行的优化以及每个人完成的功能。
    • 30% 性能测试，将根据你的编译器的性能进行评分。

    性能评分方案： 附加测试中performance部分测试样例，以 gcc 打开-O2优化的性能的 60% 为满分，按照比例折算。如果一个程序 gcc 编译后运行时间为 12s ，如果你的程序执行时间为 20s 即为满分。

    你的单个测试点的得分为：

    min{100, 100 * GCC编译程序运行时间 * 1.67 / 你的程序运行时间}

    所有测试点取算数平均值，最后结果 * 30% 作为你的最终性能测试成绩。

    评测将会在我们提供的服务器上进行，通过 QEMU 模拟 RISC-V 或者 ARM 架构的 CPU 运行你的程序。经过测试 QEMU与 真实硬件的性能相对差值是比较恒定的（如比较 gcc -O1与-O2）。

    实验评测仓库在这里。

    你也可以选择参加期末考，那么你的成绩将会是评分方案一、二取最高的一个。

  • 选项二 仅完成竞赛第一阶段（达到课程基础实验的要求）

    实验部分占比与基础实验一致，你不需要完成思考题，但是需要简单介绍你的编译器是怎么完成每一个 step 的。根据通过测试样例情况评分。

    • 完成 Stage 1 - 5 实验成绩 35% ，书面作业和日常成绩 10% ，期末成绩 55%。
    • 完成 Stage 1 - 6 实验成绩 42% ，书面作业和日常成绩 10% ，期末成绩 48%。
    • 完成 Stage 1 - 7 实验成绩 50% ，书面作业和日常成绩 10% ，期末成绩 40%。