Skip to content

part0.md

Latest commit

 

History

History
112 lines (70 loc) · 7.59 KB

part0.md

File metadata and controls

112 lines (70 loc) · 7.59 KB

本项目提供SysYF语言的中间表示(IR)优化的编译器实践框架。SysYF语言是全国编译系统设计赛要求实现的SysY语言的扩展语言，SysYF IR兼容LLVM IR。该项目由中国科学技术大学张昱老师研究组设计和开发，旨在引导更多学生和社会人员学习和实践编译器相关知识，开展语言设计与实现、程序分析、编译优化等研发，让越来越多的人有能力运用程序语言基础提供可靠、高效的软件解决方案。

评测说明(必看)

请在id.txt中添加组长学号，如PB00000000，否则无法记录成绩。

实验说明

本次实验为合作实验，任务自由分配，请在doc/reports/contribution.md中填写贡献详述和贡献比。请在头歌平台的组长账号中提交测评。

必做关卡

必做部分共有四关（支配树、Mem2Reg、活跃变量分析、优化）。

每一关的文档除了在头歌平台关卡中展示外，也在代码仓库中存在，命名为partN.md。文档中的仓库内相对链接在头歌平台关卡界面中失效。

项目结构说明

- <your repo>
   | grammar/       # 存放文法文件：  SysYFScanner.ll、 SysYFParser.yy
   | include/       # 存放头文件
     | AST/            # 抽象语法树相关
     | ErrorReporter/  # 错误报告相关
     | Frontend/       # 编译器前端相关
     | Log/            # 日志相关
     | Optimize/       # 优化相关
     | SysYFIR/        # SysYF IR相关
     | SysYFIRBuilder/ # SysYF IR构建器相关
     | *.h             # 包含internal_macros.h、internal_types.h
   | src/           # 存放C++程序文件
     | …/              # 包含与include中的各个子目录
     | main.cpp        # 主程序
   | lib/           # SysYF语言库（IO）
   | test/          # 测试脚本，测试输入和测试预期输出
   | doc/           # 存放提供的SysYF、IR等说明文档，以及需要提交的文档等
     | reports/        # 存放要提交的实验报告（各关）及组内成员贡献
   | CMakeLists.txt # cmake项目配置脚本
   | part0.md~part4.md # 关卡文档
   | id.txt         # 组长学号

编译命令的flag说明

本实验中新增了-O2命令行参数，使用-O2参数将开启全部优化（默认不开启）。例如：

./compiler -emit-ir -O2 test.sy -o test.ll

同时保留了-emit-ast参数用于从AST复原代码，-check参数用于静态检查。

同时新增了 -O 命令行参数，用于开始 Mem2Reg pass 和 DominateTree pass 。

若要开启单项优化，-lv代表开启活跃变量分析，-cse代表开启公共子表达式删除，开启这些优化的同时也会开启 Mem2Reg pass 和 DominateTree pass。例如，若你想开启活跃变量分析，就需要使用如下命令：

./compiler -emit-ir -lv test.sy -o test.ll

**注意：**以下两条命令产生的IR是不同的:

./compiler -emit-ir -O test.sy -o test.ll
./compiler -emit-ir test.sy -o test.ll

原因在于-O选项会开启Mem2Reg pass，可以消除部分栈分配指令alloca。

有关flag详情，可以参见src/main.cpp。

分析与优化Pass说明

  • Pass

    Pass类是所有分析与优化Pass的基类（比如Mem2Reg、DominateTree、LiveVar等），定义在include/Optimize/Pass.h中。该基类中有两个纯虚函数需要子类重写：一个是virtual void execute() = 0，该函数是pass的总控函数，该函数会被调用去执行该pass；另一个是virtual const std::string get_name() const = 0，该函数用于获得该pass的名字。

    该基类中有一个成员变量Ptr<Module> module，可以被子类访问。这里module表示一个编译单元，是一个源程序文件对应的中间表示。

    本实验中，你所实现的分析和优化pass均需继承自该类。你需要重写上述的execute函数和get_name函数。可以参考给出的src/Optimize/Mem2Reg.cpp和src/Optimize/DominateTree.cpp是如何继承Pass类并实现对应功能的。

    这里的Pass对应于LLVM中的ModulePass。LLVM还有其他类型的Pass，如FunctionPass, LoopPass等，针对不同规模的IR进行分析和优化，感兴趣的同学可以进一步查看Writing an LLVM Pass (legacy PM version)。

  • PassMgr

    PassMgr类负责管理Pass。定义在include/Optimize/Pass.h中。该类有两个私有成员变量:module和pass_list。module含义同上,pass_list为当前添加的所有pass的list。该类有两个公有的函数：addPass和execute。addPass函数用于向pass_list中添加pass，每次添加采用push_back的方式。execute函数用于顺序调用pass_list中pass的execute函数(即上述需要重写的execute函数)。PassMgr的使用实例可参见src/main.cpp。

    本实验中你无需修改Pass类和PassMgr类。如果有修改，请在报告中说明。

  • Mem2Reg

    Mem2Reg用于将IR转换成为SSA形式的IR。以LLVM IR为例，在生成IR时，局部变量被生成为alloca/load/store的形式。用 alloca 指令来“声明”变量，得到一个指向该变量的指针，用 store 指令来把值存在变量里，用 load 指令来把值读出。LLVM 在 mem2reg 这个 pass 中，会识别出上述这种模式的 alloca，把它提升为 SSA value(register)，在提升为 SSA value时会对应地消除 store 与 load，修改为 SSA 的 def-use/use-def 关系，并且在适当的位置安插 Phi 和 进行变量重命名。本次实验中，助教给出了Mem2Reg的一种实现(见src/Optimize/Mem2Reg.cpp)，在开启优化时会开启Mem2Reg，将IR转换为SSA形式的IR。因此本实验中的所有优化均基于SSA形式的IR。

    参考链接: LLVM对mem2reg的说明, LLVM的mem2reg实现，静态单赋值格式构造

类型与API说明

为了防止std::shared_ptr循环引用导致的内存泄漏，助教提供了WeakPtr，并定义了相关的容器类型，包括WeakPtrSet, WeakPtrList, WeakPtrMap和WeakPtrVec。

对于WeakPtrSet，提供了包括setUnion, setDiff, setIntersect等操作。

这是为了防止内存泄漏做的妥协。另外一种方法是侵入式智能指针(你可以参考后面这些链接了解博客, Boost intrusive_ptr: faster shared pointer和Intrusive Pointers)，即让Instruction等类继承intrusive_ptr_base，通过intrusive_ptr_base实现引用计数管理。然而这需要添加Instruction的拷贝构造函数等内容。同时仅引入intrusive_ptr_base也无法解决循环引用的问题。总结来说在C++中没有好的办法用很少的代价解决内存泄漏问题。

使用Log方便调试

该部分文档见logging.md。