# Lab5 报告

## 实验任务

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

## 实验流程

#### 1. 使用栈式内存分配，优先追求功能性

这一步主要完成了指令选择，所有变量(local or global)均在栈中储存，参数通过栈传递。常量保存在只读区(模拟gcc)。

这里对于phi指令的处理是：将phi指令还原为前驱块的`copy-statement`，需要将其插入在基本块的最后一条指令(跳转指令)之前。

一个坑：汇编指令`ftint.w.s fa0, fa0`将浮点数转化为定点数，竟然是四舍五入的...后来对比gcc的生成的汇编，发现了`ftintrz`这条指令。

这一步可以完成所有测试样例，但是生成的代码效率较差。

#### 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)

程序有`$a`系列寄存器8个，`$t`系列9个，拿出`$t0`、`$t1`做IR生成汇编过程中的临时寄存器(这个方案仅在cminus下成立)，所以可以自由分配的寄存器一共15个。

首先完成对于局部变量的寄存器分配，即全局变量、传参依旧通过栈进行。

程序分配寄存器时会对部分指令做特殊处理，具体如下：

- `phi`指令：还原为`copy-stmt`，所以寄存器照样分配，如果没分到使用栈内存

- `alloca`指令：这里忽略对于`alloca`指令的寄存器分配，`alloca`仍然使用栈存储，原因如下：
  
    - 对于int|float的`alloca`，使用寄存器可以正常进行，只需将相关指令`load`和`store`分别成赋值即可。
  
    - 但是对于数组的`alloca`，使用寄存器就很难模拟了。
  
  即寄存器不能完成`alloca`的内存逻辑，同时经过`mem2reg`优化过后，不再有局部变量的声明，所以忽略对于`alloca`指令的寄存器分配。

- `cmp`、`fcmp`和`zext`指令：不做寄存器分配，也不做栈分配。
  
  这实际是指令选择部分的内容：
  
  因为在cminus中并没有bool变量，这些IR指令用到的i1类型都是临时的：只为分支指令服务，所以直接将这些指令集成到分支跳转的判断中。

- `call`指令：使用栈传参，caller保存自己用到的寄存器，被保存的寄存器的活跃区间覆盖`call`指令的程序点。