编译Lab心得
下面为博客摘要，详细内容请看http://keke046.github.io/2022/03/27/compiler/
5k行，对比助教给的kira的rust代码有2。# 一些心得## Shape & InitList为了处理指针，一种通用的表示方法是必须的。为了证明自己的二次元浓度，我给编译器起名叫：**hoka**（日语：ほかほか，意思是暖洋洋的），希望写编译器的过程能带给我一点温暖。elemcnt(); i++) { std::vectorint index = s。at(0);} inline Value & op2() {return args。这样在写常数求值的时候非常好用。分配一个调用者保存的寄存器，可以在调用函数的时候不用考虑它的保存。# 重写的经历助教给了一个样例编译器，叫**kira**，（日语：キラキラ，意思是闪闪发光的）。* AST中有些指针是可以为空的，有些是不能为空的。* 这样可以支持类似`u。这样就可以用for来轻松地遍历IR。## Visitor pattern原理上来说，对Ast进行一次遍历就可以生成IR。pointing()。* 这时候，对Shape写一个`unravel`函数会非常有帮助* `unravel`把扁平索引转换为高维索引，这样可以很方便地遍历所有元素```cppfor(int i = 0; i s。在死代码消除的时候，需要递归遍历操作数，这时候可以直接for一个vector，而不用每种类型的Node特判。也是为了积累工程上的经验。它用来表示一个操作数，操作数可以是立即数，也可以是另一个IR节点。。第三个版本还叫**fuwa**，使用了和**hoka**类似的AST，一样最大程度减少可空指针。。* 用一些C++黑魔法甚至可以实现自己替换掉自己。这是C代码的一种经典逻辑。type()。这样`a。```cppconst ValueType UndefType(。* 但为了简洁，我把几乎所有逻辑都加入到了yacc文件中。一般写法是维护一个“当前Block”，其实可以写成一个Helper：一个很妙的Helper是，`newIfBlk(cond)`函数，函数建立两个block，把当前block设置成iftrue分支，然后返回iffalse分支的block指针。第四个版本叫**huwa**，其实日语里**fuwa**和**huwa**是一个意思。 数组确定后，所有变量的定义都明确了。如果列表中某个项0，表示这是一个指针。* 写了一个优美的Helper来处理控制流转换。```cppfor(auto f: prog-func) for(auto b: *f) for(auto n: *b) ;```Node有多种类型，可以写成共用体，但我为了简单，直接写成一个结构体。可以对不同类型的IR设置的构造函数，如Alloc可以把类型作为参数，Biop是两个Value作为参数。!-- indicate-the-source --# 编译Lab心得编译lab，从零开始写一个编译器，要求能够解析C语法的一个子集。elemcnt()`可以返回一个数组指针对应数组的元素个数。如果有10个AST节点，4趟处理，需要给每个节点写4个函数，就是40个函数，非常容易出错。为了简单，将其打平成一维数组。**hoka**中使用了很多指针，指针如果不为空，认为值存在，否则认为值不存在。但这样对debug极其不友好。。* 没有一个统一的用来描述数组大小的`Shape`抽象。这是一个神奇的软工技巧，可以将数据结构和数据结构的遍历分离。因为常数求值就是把自己替换成常数。 else {li(tmp, off); add(tmp, tmp, base); sw(dst, 0, tmp);} }};```如果addi失败，需要转换成寄存器加法。);ValueType Value::type() { if(isImm()) return IntType; else if(isNode()) return node-valtype; else return UndefType;}```* **注意** 这里的Value表示操作数或者一个IR节点，而不是一个IR的变量名。。结果在一天后**fuwa**又被废弃了。助教给的libkoopa是C的库，我想要的是现代c++，所以放弃libkoopa，自己写IR的内存表示。* **fuwa**最大程度减少可空指针。最后第四版终于一气呵成。 对所有常量表达式求值，现在就可以得到每个数组的维度了，因为维度可以是常量`int a[maxn]={}`3。做一个`Shape`的抽象，加入各种Helper函数，之后会非常好用。然后可以优美地处理控制流：```cpp virtual void visit(If * u) { go(u-child); auto tail = newBlk(); auto handle = newIfBlk(u-child-node); { go(u-iftrue); jumpToBlk(tail); } elseBlk(handle); { go(u-iffalse); jumpToBlk(tail); } setCurBlk(tail); }```# RISCV生成RISCV中有让人困惑的12位立即数。1k行（不算libkoopa）。为了防止自己忘记设置重要的参数，可以写一下IR Node的构造函数。可以将对AST的处理分成多个步骤：我分成了四个步骤1。助教想要让他的编译器像星星一样，闪闪发光，指明同学们写编译器的道路。这样扁平的结构上使用visitor pattern有点杀鸡牛刀。);const ValueType IntType(。还有一个比较重要的抽象是Value的抽象。* 同样，对数组的初始化列表也没有一个统一的抽象。综合了前几次的经验，一气呵成，终于没有了错误。写的时候没有注意，混到了一起。* 可能有 `Node*` 表示单个儿子* 可能有 `std::vectorNode*` 表示一群儿子* 可能有 `std::optionalNode*` 表示可能有儿子这样在写`getChildren`的时候，非常地烦。unravel(i);}```对于InitList为了性能，我选择用`std::unordered_map`。at(1);}};```IR的结构中，比较重要的抽象是ValueType的抽象。* 可以写`toPointer`来返回指针的Shape，写`pointing`返回被指向的Shape* 可以写`elemcnt`来返回元素个数。如果一个if没有else，就造一个空blcok弄成它的else。感觉非常地精简优美，在此将心得分享给大家。可以使用宏套宏的方法来简化```cpp#define Child(var) var-accept(v);#define Children(var) for(auto p: var) p-accept(v);#define MaybeChild(var) if(var) var-accept(v);#define DefineChild(cls, stmt) virtual void iterChild(Visitor * v) { stmt }struct If: public Stmt { Expr * cond; Stmt * iftrue, * iffalse; DefineChild(If, Child(cond) Child(iftrue) Child(iffalse)); };```## IR的结构助教的libkoopa太迷惑了，我自己写了IR的内存表示。虽然得到了96分，但还是感觉不够完美。不如直接让IR的Func和Block继承`std::vector`。```cppstruct Node { 。写了一周lab，重写了3遍。有的是代码不work，有的是感觉代码不够优美。op1()。这里我专门分配一个寄存器给RISCV结构体，其它人都不能用。## 控制流Helper在将AST转换成IR的时候，需要把AST结构化的控制流转换成jump和branch表示的控制流。* 按照这种规则生成的IR一定程度上满足SSA约束，之后优化的时候会很简单。。它和Shape类似，用来处理IR节点的类型推断问题。这个寄存器用来处理imm12的情况。为了解决这样的遍历问题，可以使用**visitor pattern**。 std::vectorValue args; inline Value & op1() {return args。然后yacc直接给我生成了上万行的cpp，简直无法调试。pointing()。## AST代码重用使用Visitor模式的时候，节点的儿子可能有多种模式。但对于Block和Func，它们的本质是容器，我们会往里面不停添加节点，而不是一次把所有节点传进去。不如直接一次到位，在生成IR的时候就直接把定义传过去，这样后面就少了一种需要特判的情况。 最复杂的初始化列表搞定后，就可以愉快地生成IR了。 找到每个变量的定义，call对应的函数，break和continue对应的while循环2。* 将控制流转换成IR的jump的时候，没有写Helper，也非常混乱。。把所有IR拥有的成员都塞进去。!--more--**hoka**在两天后被放弃了。为了进一步方便，将操作数写成std::vector的形式。* 局部数组，作为函数参数的数组，全局数组，三个东西是完全不同的。4。判的时候容易忘掉，然后程序无限Segmentation Fault第二个版本叫做**fuwa**（日语ふわふわ，意思是轻飘飘的），希望写的编译器尽量简单，简洁又优美。这个真的非常让人困惑，也非常容易出错。对它们写构造函数，就会带来负影响。IR是扁平的三层结构：Func，Block，Node。* IR中有`getelemptr`操作，可以写一个`toGEPShape()`来返回经过该函数运算后的Shape对于高维数组，直接处理往往需要递归，非常麻烦。。。```cppstruct Node { virtual void accept(Visitor * v) = 0; virtual std::vectorNode* getChildren();};struct Expr: public Node { virtual void accept(Visitor * v);};struct AddExpr: public Expr { virtual void accept(Visitor * v);};struct If: public Node { virtual void accept(Visitor * v);};struct Visitor { virtual void visit(Node * u) {for(auto c: u-getChildren()) c-accept(this);}; virtual void visit(Expr * u) {visit((Node*)u);} virtual void visit(AddExpr * u) {visit((Expr*)u);} virtual void visit(If * u) {visit((Node*)u);}};void Expr::accept(Visitor * v) {v-visit(this);}void AddExpr::accept(Visitor * v) {v-visit(this);}void If::accept(Visitor * v) {v-visit(this);} ```只要继承Visitor，把关心的节点的visit函数重载，其它节点会自动递归儿子。。既然都处理来立即数操作了，不如干脆把四种情况都处理了算了：```cppstruct RISCV { std::ostream & out; inline std::string tmpreg = "t0"; void biop(Op op, str dst, str op1, str op2); void biop(Op op, str dst, str op1, int op2); // 先尝试使用addi，失败使用add void biop(Op op, str dst, int op1, str op2); // 判断有没有交换律， void biop(Op op, str dst, int op1, int op2); // 直接用li void sw(str dst, int off, str base) { if(isImm12(off)) //。如if没有else，return没有返回值。导致对于数组处理得非常混乱，然后可能哪里情况没有考虑全，就挂了。这时候再来处理初始化列表。可以写一个Helper来处理和立即数相关的操作。我的C++代码有2。然后`elseBlk(handle)`函数将handle设置成当前分支。elemsize()`的操作，会非常方便。 这样处理的其实是和visitor pattern类似的找儿子问题。可以用一个int列表来表示指针。* 在写AST之前，就完成`Shape`和`InitList`的抽象* 尽量减少可空指针，如果真的是可空指针，用`std::optional`来防止忘记判空* 使用最简单的寄存器访问策略，防止汇编出玄学问题* 分离局部变量，全局变量，参数三种AST节点。因为如果把Value设置为变量名，我们还需要对IR做一次找变量定义的操作。如`[0, 10]`表示`*[i32, 10]`，`[0,0,10,5]`表示`**[[i32,5], 10]`
编译Lab心得
编译lab，从零开始写一个编译器，要求能够解析C语法的一个子集。
写了一周lab，重写了3遍。有的是代码不work，有的是感觉代码不够优美。
助教给的libkoopa是C的库，我想要的是现代c++，所以放弃libkoopa，自己写IR的内存表示。也是为了积累工程上的经验。
最后第四版终于一气呵成。我的C++代码有2.5k行，对比助教给的kira的rust代码有2.1k行（不算libkoopa）。感觉非常地精简优美，在此将心得分享给大家。
重写的经历
助教给了一个样例编译器，叫kira，（日语：キラキラ，意思是闪闪发光的）。助教想要让他的编译器像星星一样，闪闪发光，指明同学们写编译器的道路。
为了证明自己的二次元浓度，我给编译器起名叫：hoka（日语：ほかほか，意思是暖洋洋的），希望写编译器的过程能带给我一点温暖。
5k行，对比助教给的kira的rust代码有2。# 一些心得## Shape & InitList为了处理指针，一种通用的表示方法是必须的。为了证明自己的二次元浓度，我给编译器起名叫：**hoka**（日语：ほかほか，意思是暖洋洋的），希望写编译器的过程能带给我一点温暖。elemcnt(); i++) { std::vectorint index = s。at(0);} inline Value & op2() {return args。这样在写常数求值的时候非常好用。分配一个调用者保存的寄存器，可以在调用函数的时候不用考虑它的保存。# 重写的经历助教给了一个样例编译器，叫**kira**，（日语：キラキラ，意思是闪闪发光的）。* AST中有些指针是可以为空的，有些是不能为空的。* 这样可以支持类似`u。这样就可以用for来轻松地遍历IR。## Visitor pattern原理上来说，对Ast进行一次遍历就可以生成IR。pointing()。* 这时候，对Shape写一个`unravel`函数会非常有帮助* `unravel`把扁平索引转换为高维索引，这样可以很方便地遍历所有元素```cppfor(int i = 0; i s。在死代码消除的时候，需要递归遍历操作数，这时候可以直接for一个vector，而不用每种类型的Node特判。也是为了积累工程上的经验。它用来表示一个操作数，操作数可以是立即数，也可以是另一个IR节点。。第三个版本还叫**fuwa**，使用了和**hoka**类似的AST，一样最大程度减少可空指针。。* 用一些C++黑魔法甚至可以实现自己替换掉自己。这是C代码的一种经典逻辑。type()。这样`a。```cppconst ValueType UndefType(。* 但为了简洁，我把几乎所有逻辑都加入到了yacc文件中。一般写法是维护一个“当前Block”，其实可以写成一个Helper：一个很妙的Helper是，`newIfBlk(cond)`函数，函数建立两个block，把当前block设置成iftrue分支，然后返回iffalse分支的block指针。第四个版本叫**huwa**，其实日语里**fuwa**和**huwa**是一个意思。 数组确定后，所有变量的定义都明确了。如果列表中某个项0，表示这是一个指针。* 写了一个优美的Helper来处理控制流转换。```cppfor(auto f: prog-func) for(auto b: *f) for(auto n: *b) ;```Node有多种类型，可以写成共用体，但我为了简单，直接写成一个结构体。可以对不同类型的IR设置的构造函数，如Alloc可以把类型作为参数，Biop是两个Value作为参数。!-- indicate-the-source --# 编译Lab心得编译lab，从零开始写一个编译器，要求能够解析C语法的一个子集。elemcnt()`可以返回一个数组指针对应数组的元素个数。如果有10个AST节点，4趟处理，需要给每个节点写4个函数，就是40个函数，非常容易出错。为了简单，将其打平成一维数组。**hoka**中使用了很多指针，指针如果不为空，认为值存在，否则认为值不存在。但这样对debug极其不友好。。* 没有一个统一的用来描述数组大小的`Shape`抽象。这是一个神奇的软工技巧，可以将数据结构和数据结构的遍历分离。因为常数求值就是把自己替换成常数。 else {li(tmp, off); add(tmp, tmp, base); sw(dst, 0, tmp);} }};```如果addi失败，需要转换成寄存器加法。);ValueType Value::type() { if(isImm()) return IntType; else if(isNode()) return node-valtype; else return UndefType;}```* **注意** 这里的Value表示操作数或者一个IR节点，而不是一个IR的变量名。。结果在一天后**fuwa**又被废弃了。助教给的libkoopa是C的库，我想要的是现代c++，所以放弃libkoopa，自己写IR的内存表示。* **fuwa**最大程度减少可空指针。最后第四版终于一气呵成。 对所有常量表达式求值，现在就可以得到每个数组的维度了，因为维度可以是常量`int a[maxn]={}`3。做一个`Shape`的抽象，加入各种Helper函数，之后会非常好用。然后可以优美地处理控制流：```cpp virtual void visit(If * u) { go(u-child); auto tail = newBlk(); auto handle = newIfBlk(u-child-node); { go(u-iftrue); jumpToBlk(tail); } elseBlk(handle); { go(u-iffalse); jumpToBlk(tail); } setCurBlk(tail); }```# RISCV生成RISCV中有让人困惑的12位立即数。1k行（不算libkoopa）。为了防止自己忘记设置重要的参数，可以写一下IR Node的构造函数。可以将对AST的处理分成多个步骤：我分成了四个步骤1。助教想要让他的编译器像星星一样，闪闪发光，指明同学们写编译器的道路。这样扁平的结构上使用visitor pattern有点杀鸡牛刀。);const ValueType IntType(。还有一个比较重要的抽象是Value的抽象。* 同样，对数组的初始化列表也没有一个统一的抽象。综合了前几次的经验，一气呵成，终于没有了错误。写的时候没有注意，混到了一起。* 可能有 `Node*` 表示单个儿子* 可能有 `std::vectorNode*` 表示一群儿子* 可能有 `std::optionalNode*` 表示可能有儿子这样在写`getChildren`的时候，非常地烦。unravel(i);}```对于InitList为了性能，我选择用`std::unordered_map`。at(1);}};```IR的结构中，比较重要的抽象是ValueType的抽象。* 可以写`toPointer`来返回指针的Shape，写`pointing`返回被指向的Shape* 可以写`elemcnt`来返回元素个数。如果一个if没有else，就造一个空blcok弄成它的else。感觉非常地精简优美，在此将心得分享给大家。可以使用宏套宏的方法来简化```cpp#define Child(var) var-accept(v);#define Children(var) for(auto p: var) p-accept(v);#define MaybeChild(var) if(var) var-accept(v);#define DefineChild(cls, stmt) virtual void iterChild(Visitor * v) { stmt }struct If: public Stmt { Expr * cond; Stmt * iftrue, * iffalse; DefineChild(If, Child(cond) Child(iftrue) Child(iffalse)); };```## IR的结构助教的libkoopa太迷惑了，我自己写了IR的内存表示。虽然得到了96分，但还是感觉不够完美。不如直接让IR的Func和Block继承`std::vector`。```cppstruct Node { 。写了一周lab，重写了3遍。有的是代码不work，有的是感觉代码不够优美。op1()。这里我专门分配一个寄存器给RISCV结构体，其它人都不能用。## 控制流Helper在将AST转换成IR的时候，需要把AST结构化的控制流转换成jump和branch表示的控制流。* 按照这种规则生成的IR一定程度上满足SSA约束，之后优化的时候会很简单。。它和Shape类似，用来处理IR节点的类型推断问题。这个寄存器用来处理imm12的情况。为了解决这样的遍历问题，可以使用**visitor pattern**。 std::vectorValue args; inline Value & op1() {return args。然后yacc直接给我生成了上万行的cpp，简直无法调试。pointing()。## AST代码重用使用Visitor模式的时候，节点的儿子可能有多种模式。但对于Block和Func，它们的本质是容器，我们会往里面不停添加节点，而不是一次把所有节点传进去。不如直接一次到位，在生成IR的时候就直接把定义传过去，这样后面就少了一种需要特判的情况。 最复杂的初始化列表搞定后，就可以愉快地生成IR了。 找到每个变量的定义，call对应的函数，break和continue对应的while循环2。* 将控制流转换成IR的jump的时候，没有写Helper，也非常混乱。。把所有IR拥有的成员都塞进去。!--more--**hoka**在两天后被放弃了。为了进一步方便，将操作数写成std::vector的形式。* 局部数组，作为函数参数的数组，全局数组，三个东西是完全不同的。4。判的时候容易忘掉，然后程序无限Segmentation Fault第二个版本叫做**fuwa**（日语ふわふわ，意思是轻飘飘的），希望写的编译器尽量简单，简洁又优美。这个真的非常让人困惑，也非常容易出错。对它们写构造函数，就会带来负影响。IR是扁平的三层结构：Func，Block，Node。* IR中有`getelemptr`操作，可以写一个`toGEPShape()`来返回经过该函数运算后的Shape对于高维数组，直接处理往往需要递归，非常麻烦。。。```cppstruct Node { virtual void accept(Visitor * v) = 0; virtual std::vectorNode* getChildren();};struct Expr: public Node { virtual void accept(Visitor * v);};struct AddExpr: public Expr { virtual void accept(Visitor * v);};struct If: public Node { virtual void accept(Visitor * v);};struct Visitor { virtual void visit(Node * u) {for(auto c: u-getChildren()) c-accept(this);}; virtual void visit(Expr * u) {visit((Node*)u);} virtual void visit(AddExpr * u) {visit((Expr*)u);} virtual void visit(If * u) {visit((Node*)u);}};void Expr::accept(Visitor * v) {v-visit(this);}void AddExpr::accept(Visitor * v) {v-visit(this);}void If::accept(Visitor * v) {v-visit(this);} ```只要继承Visitor，把关心的节点的visit函数重载，其它节点会自动递归儿子。。既然都处理来立即数操作了，不如干脆把四种情况都处理了算了：```cppstruct RISCV { std::ostream & out; inline std::string tmpreg = "t0"; void biop(Op op, str dst, str op1, str op2); void biop(Op op, str dst, str op1, int op2); // 先尝试使用addi，失败使用add void biop(Op op, str dst, int op1, str op2); // 判断有没有交换律， void biop(Op op, str dst, int op1, int op2); // 直接用li void sw(str dst, int off, str base) { if(isImm12(off)) //。如if没有else，return没有返回值。导致对于数组处理得非常混乱，然后可能哪里情况没有考虑全，就挂了。这时候再来处理初始化列表。可以写一个Helper来处理和立即数相关的操作。我的C++代码有2。然后`elseBlk(handle)`函数将handle设置成当前分支。elemsize()`的操作，会非常方便。 这样处理的其实是和visitor pattern类似的找儿子问题。可以用一个int列表来表示指针。* 在写AST之前，就完成`Shape`和`InitList`的抽象* 尽量减少可空指针，如果真的是可空指针，用`std::optional`来防止忘记判空* 使用最简单的寄存器访问策略，防止汇编出玄学问题* 分离局部变量，全局变量，参数三种AST节点。因为如果把Value设置为变量名，我们还需要对IR做一次找变量定义的操作。如`[0, 10]`表示`*[i32, 10]`，`[0,0,10,5]`表示`**[[i32,5], 10]`