# Lab4.1 实验报告

## 实验要求

4.1给出了一个减少内存分配和访问的优化Mem2Reg，通过学习这个示例，我们可以：

1. 看到一种优化方案的很多细节：如何使用支配信息、如何使用`phi`函数、如何重命名(实际上是裁剪冗余代码)……

2. 了解实验框架的实现原理：如基本块的CFG信息、指令类型和值类型的互相转换细节、如何注册优化……为下一次实验的优化(我相信下一次实验是要自己实现什么优化）做好准备。

## 思考题

1. 请简述概念：支配性、严格支配性、直接支配性、支配边界。
   
    - 支配性：给定CFG中，假设初始块是B~0~，对于一个基本块B~j~，如果基本块B~i~存在于B~0~到B~j~的所有路径上时，则称B~i~支配B~j~。根据定义，其中B~0~和B~j~一定支配B~j~
   
    - 严格支配性：如果B~i~支配B~j~，且B~i~不是B~j~，则B~i~严格支配B~j~
   
    - 直接支配：在严格支配基本块B~j~的块集合中，距离B~j~距离最近的块就是B~j~的直接支配节点，称作IDOM(B~j~)
   
    - 支配边界：如果两个节点B~i~和B~j~满足以下两个条件：
      
        - B~i~支配B~j~的一个前驱节点
      
        - B~i~不严格支配B~j~
      
      则认为符合条件的B~j~的集合是B~i~的支配边界，记作DF(B~i~)

2. `phi`节点是SSA的关键特征，请简述`phi`节点的概念，以及引入`phi`节点的理由。
   
   `phi`节点是构造SSA的技术产物之一。
   
   将程序转化为SSA的过程中，会存在一个问题：在CFG的汇合点，一个变量可能对应不同路径的多个定值，由于SSA要求变量只能被赋值至多一次，不同路径上的定值会对应不同的变量，而在汇合点之后使用变量，就需要决策使用哪个定值。
   
   这件事不能静态确定，解决方案是增加一个`phi`函数的赋值，使`phi`函数的参数是可能的定值，`phi`函数的结果是一个新变量。`phi`函数将动态决定使用哪个定值作为新变量的定值，而这个新变量作为汇合点之后的变量定值可以直接使用。

3. 观察下面给出的`cminus`程序对应的 LLVM IR，与**开启**`Mem2Reg`生成的LLVM IR对比，每条`load`, `store`指令发生了变化吗？变化或者没变化的原因是什么？请分类解释。
   
   因为阅读代码后发现，优化是针对函数进行的，所以我们区分函数来观察，先观察函数`func`：
   
   ```c
   int func(int x){
       if(x > 0){
           x = 0;
       }
       return x;
   }
   ```
   
   使用到的变量就只有int型参数`x`，不需要任何分配和`load`/`store`，所以都被优化掉。
   
   再来看函数`main`：
   
   ```cpp
   int main(void){
       int arr[10];
       int b;
       globVar = 1;
       arr[5] = 999;
       b = 2333;
       func(b);
       func(globVar);
       return 0;
   }
   ```
   
   变量`b`是int型，可以删去，所以被优化掉了。
   
   `arr`是数组，`globVar`是全局变量，所以不会被优化掉，因此优化后的中间代码还保存着关于这两个变量的`store`和`load`。

4. 指出放置phi节点的代码，并解释是如何使用支配树的信息的。（需要给出代码中的成员变量或成员函数名称）
   
   插入`phi`节点的代码在`src/optimization/Mem2Reg.cpp`中定义的函数`void Mem2Reg::generate_phi()`中。
   
   这个函数将针对当前指定的**函数**，遍历其所有**基本块**，找到作为`store`指令左值的所有**变量集合**，同时维护**这些变量的定值(即store指令)出现的基本块**。
   
   然后会遍历每个变量，利用**支配树**找到变量定值所在基本块的边界集合，在这些支配边界首部插入`phi`函数，更新`work_list`和基本块的`phi`函数信息`bb_has_var_phi`。
   
   ```cpp
   auto phi =
       PhiInst::create_phi(var->get_type()->get_pointer_element_type(), bb_dominance_frontier_bb);
   phi->set_lval(var);
   bb_dominance_frontier_bb->add_instr_begin(phi);
   ```
   
   计算活跃变量集合时，算法不计入全局变量和数组内容。按照我的理解，这是因为Mem2Reg算法的目标是将局部非数组变量的(int、float)的内存分配移除，期待用寄存器代之，而全局变量和数组不能满足寄存器分配的性质，所以不对这两种类型做处理。

5. 算法是如何选择`value`(变量最新的值)来替换`load`指令的？（描述清楚对应变量与维护该变量的位置）
   替换`load`指令的代码在文件`src/optimization/Mem2Reg.cpp`定义的函数`void Mem2Reg::re_name(BasicBlock *bb)`中。
   
   截取代码如下：
   
   ```cpp
   if (instr->is_load()) {
       auto l_val = static_cast<LoadInst *>(instr)->get_lval();
   
       if (!IS_GLOBAL_VARIABLE(l_val) && !IS_GEP_INSTR(l_val)) {
           if (var_val_stack.find(l_val) != var_val_stack.end()) {
               // 此处指令替换会维护 UD 链与 DU 链
               instr->replace_all_use_with(var_val_stack[l_val].back());
               wait_delete.push_back(instr);
           }
       }
   }
   ```
   
   算法在遇`load`指令时，会检查源地址数据的最新定值是否已经被保存在栈中，具体是查找这个变量对应的栈`var_val_stack[l_val]`是否存在，如果存在则会替换掉这条`load`指令，使用栈顶定值`var_val_stack[l_val].back()`代替其结果。
   
   而针对这个栈的维护还是在`rename`函数中，主要做一下几点维护：
   
    - `phi`函数和`store`指令对一个变量(局部非数组)的最新定值会被压入栈顶。
   
    - 离开`re_name`时恢复栈至进入函数的状态。

### 代码阅读总结

#### UD链与DU链

- UD链在`User`类中维护，内部变量为`operands_`，主要是一个使用者(指令、全局变量等)使用了哪些定值。

- DU链在`Value`类中维护，内部变量是`use_list_`，表示使用这个`Value`变量的对象集合。

在阅读Mem2Reg时，替换load处一个一知半解的函数`replace_all_use_with`：

```cpp
void Value::replace_all_use_with(Value *new_val) {
    for (auto use : use_list_) {
        auto val = dynamic_cast<User *>(use.val_);
        assert(val && "new_val is not a user");
        val->set_operand(use.arg_no_, new_val);
    }
    use_list_.clear();
}
```

根据这段代码，搞清楚了这个函数的逻辑：针对一个`Value*`变量，将使用到它的位置都替换为另一个`Value*`变量`new_val`，不仅要将自己的DU链清空，还要将原来在DU链上的所用定值使用都更换为`new_val`。

回到当初不懂的地方：

```cpp
if (instr->is_load()) {
    auto l_val = static_cast<LoadInst *>(instr)->get_lval();

    if (!IS_GLOBAL_VARIABLE(l_val) && !IS_GEP_INSTR(l_val)) {
        if (var_val_stack.find(l_val) != var_val_stack.end()) {
            // 此处指令替换会维护 UD 链与 DU 链
            instr->replace_all_use_with(var_val_stack[l_val].back());
            wait_delete.push_back(instr);
        }
    }
}
```

这就是在`load`指令可以被替换的时候，`load`指令作为一个`Value*`变量，需要调用其成员函数`replace_all_use_with`，来将其所有使用替换成栈顶的定值。

#### Mem2Reg

- `run`：针对每个函数的产生phi指令`generate_phi()`、重命名`re_name()`和移除冗余alloca指令`remove_alloca()`。

- `generate_phi()`
  
    1. 计算跨基本块的活跃变量集合`global_live_var_name`，并维护每个活跃变量出现的基本块集合`live_var_2blocks`
       
       依据`store`指令即定值产生
       
       这里活跃变量是针对alloca分配过空间的变量，不可以是全局or`GEP`产生的地址。
  
    2. 遍历活跃变量集合，在每个变量定值所在基本块的支配边界处产生`phi`函数。
       
       代码中存在若干细节：
       
        - 使用结构`map<std::pair<BasicBlock *, Value *>, bool>`维护信息：基本块针对某一变量是否存在`phi`函数。
       
        - `work_list`在循环中是变化的，所以使用下标而非auto索引。

- `re_name(bb)`
  
  因为原本就是SSA，所以不需要counter，需要的是裁减冗余代码，修改操作数。资料中的stack使用`var_val_stack`实现，一个全局活跃变量的栈顶表示编译过程中的最新定值。
  
    1. 将bb的`phi`函数指令压栈，作为其结果的定值。
  
    2. 针对store指令，更新栈顶，即压入右值。对于load指令，将load的结果引用都替换为栈顶定值(如果有的话)。如果上述操作成果，store、load均可删去。
  
    3. 填充后继节点的`phi`指令。
  
    4. 在支配树上递归重命名。
  
    5. 恢复栈状态至初始，根据store指令和phi指令的结果变量弹出。
  
    6. 去除第2步的冗余指令。

- `remove_alloca()`
  
  这里应该是有一个断言：经过前边的一系列处理，基本块内部的int、float的分配(alloca)指令都是冗余的，应该直接删去。
  
  这里删去的alloca与`re_name()`中的有什么区别

### 实验反馈 （可选 不会评分）

对同学整体来说，鼓励大家读代码很好，因为有的同学前几个实验做不明白就是因为不看框架代码。

对我自己来说，我还是有点读不清楚，有的地方似懂非懂，估计下个实验真动手做了就会好一点吧。

## 参考

[PHI Node总结](https://www.jianshu.com/p/497a9d0e1b3e)

[llvm PHI Node](https://www.llvmpy.org/llvmpy-doc/dev/doc/llvm_concepts.html#ssa-form-and-phi-nodes)

[北航的mem2reg教程](https://buaa-se-compiling.github.io/miniSysY-tutorial/challenge/mem2reg/help.html)