# Lab5 报告

## 实验任务

基于前4个实验，完成对LightIR的翻译，目标架构为龙芯LA64架构。

## 实验流程

1. 使用栈式内存分配，优先追求功能性
   
   这一步主要完成了指令选择，所有变量(local or global)均在栈中储存，参数通过栈传递。常量保存在只读区(模拟gcc)。
   
   这里对于phi指令的处理是：将phi指令还原为前驱块的`copy-statement`，需要将其插入在基本块的最后一条指令(跳转指令)之前。
   
   这一步可以完成所有测试样例，但是生成的代码效率较差。

2. 活跃变量分析
   
   先确定指令的遍历顺序，这里使用常规的BFS遍历，phi指令的处理和上述相同，例如对于`5-while.ll`：
   
   ```llvm
   define i32 @main() {
   label_entry:
     br label %label0
   label0:                                                ; preds = %label_entry, %label5
     %op1 = phi i32 [ 0, %label_entry ], [ %op6, %label5 ]
     %op2 = icmp slt i32 %op1, 10
     %op3 = zext i1 %op2 to i32
     %op4 = icmp ne i32 %op3, 0
     br i1 %op4, label %label5, label %label7
   label5:                                                ; preds = %label0
     call void @output(i32 %op1)
     %op6 = add i32 %op1, 1
     br label %label0
   label7:                                                ; preds = %label0
     ret i32 0
   }
   ```
   
   指令遍历顺序如下，第1条与第9条指令就是phi指令的还原。
   
   ```llvm
   1. op1 = 0
   2. br label %label0 
   3. %op2 = icmp slt i32 %op1, 10 
   4. %op3 = zext i1 %op2 to i32 
   5. %op4 = icmp ne i32 %op3, 0 
   6. br i1 %op4, label %label5, label %label7 
   7. call void @output(i32 %op1) 
   8. %op6 = add i32 %op1, 1 
   9. op1 = op6
   10. br label %label0 
   11. ret i32 0 
   ```
   
   用编号代替指令，获得每个程序点的IN和OUT：
   
   ```llvm
   1. op1 = 0
   	in-set: [ ]
   	out-set: [ op1 ]
   2. br label %label0 
   	in-set: [ op1 ]
   	out-set: [ op1 ]
   3. %op2 = icmp slt i32 %op1, 10 
   	in-set: [ op1 ]
   	out-set: [ op2 op1 ]
   4. %op3 = zext i1 %op2 to i32 
   	in-set: [ op2 op1 ]
   	out-set: [ op3 op1 ]
   5. %op4 = icmp ne i32 %op3, 0 
   	in-set: [ op3 op1 ]
   	out-set: [ op4 op1 ]
   6. br i1 %op4, label %label5, label %label7 
   	in-set: [ op4 op1 ]
   	out-set: [ op1 ]
   7. call void @output(i32 %op1) 
   	in-set: [ op1 ]
   	out-set: [ op1 ]
   8. %op6 = add i32 %op1, 1 
   	in-set: [ op1 ]
   	out-set: [ op6 ]
   9. op1 = op6
   	in-set: [ op6 ]
   	out-set: [ op1 ]
   10. br label %label0 
   	in-set: [ op1 ]
   	out-set: [ op1 ]
   11. ret i32 0 
   	in-set: [ ]
   	out-set: [ ]
   ```
   
   获得活跃区间：编号为i的指令，涉及两个端点：i-1和i，分别对应IN和OUT。由此得到各个变量的活跃区间是：
   
   ```llvm
   op1: <1, 10>
   op2: <3, 3>
   op3: <4, 4>
   op4: <5, 5>
   op6: <8, 8>
   ```

3. 寄存器分配
   
   使用线性扫描算法实现寄存器分配，参考：
   
    - http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf
   
    - [Documentations/5-bonus/寄存器分配.md · master · compiler_staff / 2022fall-Compiler_CMinus · GitLab](https://cscourse.ustc.edu.cn/vdir/Gitlab/compiler_staff/2022fall-compiler_cminus/-/blob/master/Documentations/5-bonus/%E5%AF%84%E5%AD%98%E5%99%A8%E5%88%86%E9%85%8D.md#poletto)