# Lab4.2 实验报告

姓名 学号

## 实验要求

请按照自己的理解，写明本次实验需要做什么

## 实验难点

### 对于函数`detectEquivalences(G)`

```cpp
detectEquivalences(G)
    PIN1 = {} // “1” is the first statement in the program
    POUT1 = transferFunction(PIN1)
    for each statement s other than the first statement in the program
        POUTs = Top
    while changes to any POUT occur // i.e. changes in equivalences
        for each statement s other than the first statement in the program
            if s appears in block b that has two predecessors
            then
                PINs = Join(POUTs1, POUTs2) // s1 and s2 are last statements in respective predecessors
            else
                PINs = POUTs3    // s3 the statement just before s
            POUTs = transferFunction(PINs) // apply transferFunction on each statement in the block
```

- POUT、PIN是对于语句的的map，但是实现中是对于基本块的map，怎么处理区别？
  
  注意到基本块的pin、pout对应着首条语句的pin和末尾语句的pout，所以没有本质上的不同，主要是怎么补全中间语句的pin、pout。
  
  中间语句的pin、pout应该不会被显式保存，只在对基本块执行转移函数时，逐条计算。所以应该没啥问题。

- 怎么设计top？
  
  尽管算法伪代码中，top是对每一条语句的赋值的，但是任意一条语句的都有所属基本块，只要对基本块的pout标注top、就能保证基本块的pin合乎逻辑，逐条执行转移函数后，每条语句的pin都合法。``

- `while changes to any POUT occur`
  
  这句话如此轻松，但是在实现中出现了问题：这涉及到怎么判断分区相等，做不好会出现死循环。
  
  如果单纯比较index恐怕不行：因为我目前的`transferFunction`会生成一个新的等价类，赋予一个新的编号。
  
  所以我使用对等价类中的`members`做相等的判断，如果两个分区中的等价类都能找到相等的，那么就判断分区相等。
  
  > 但是这样依赖于set的排序，
  > 
  > - 对于分区，这个排序依赖于等价类中index的值，侥幸来说每条指令按顺序执行，即使index不一致(每次转移函数分配最新的index)，大小顺序也是一致的？
  > 
  > - 对于等价类，里边是`Value*`指针，这个指针的等价就是语义上的等价，没问题。
  
  改过来后发现还是死循环，DEBUG很久意识到我的分区相等写的有问题：`return members_ == other.members_`，这样会挨个儿比较`members_`指针的值，而不是我预想的比较指针指向的等价类。所以要手动遍历一下。
  
  这个遍历也不是很直观的，因为要做两层解引用：
  
  ```cpp
      for (; it1 != p1.end(); ++it1, ++it2)
          if (not(**it1 == **it2))
              return false;
  ```
  
  `*it`是等价类的指针，`**it`才是等价类。
  
  除此之外，我还忘了`++it2`，淦。
  
  改完这些，终于能跑通第一版本了……

### 对于函数`Intersect(Ci, Cj )`

伪代码中，一个等价类是一个集合，求交后，v~k~是自然而然的在或不在新集合中，但是实现中并不这么简单，如何对这样的两个结构体进行逻辑上的取交：

```cpp
struct CongruenceClass {
    size_t index_;
    Value *leader_;
    std::shared_ptr<GVNExpression::Expression> value_expr_;
    std::shared_ptr<GVNExpression::PhiExpression> value_phi_;
    std::set<Value *> members_;
}
```

- 首先是Intersect的伪代码描述中，下边这句怎么在实现中体现？
  
  > C~k~ does not have value number
  
  解决：index不同的自然就交不出v~i~，相同的时候才有v~i~即value number.
  
  隐患：transferFunction要对v~i~有继承性，即不能每次涉及一个等价类都新开一个value number(这个在后边的值编号维护中已经解决)

- 根据上一条讨论，得出一个观点：在伪代码中，一个等价类集合会出现的内容，在实现中的对应如下：
  
    - 普通变量：`members_`
  
    - 值表达式：`value_expr_`
  
    - phi函数：`value_phi_`
  
    - 值编号v~i~：`index`
  
  因此，伪代码中对集合的求交，对应到实现上，就是对以上四个域求交。

- 额外设计：赋予**精准的**值编号
  
  在我的设计中，每条指令都有一个潜在的值编号，如果要为这条指令新建等价类，就使用这个值编号。所以需要`Intersect`确定新的值编号时，应该选用靠前的以为后边指令腾出编号空间。

### 对于函数`valuePhiFunc(ve, P)`

- 输入就一个分区，实际上要用到两个前驱的分区，怎么处理？
  
  传入基本块做参数。

- 二元运算的顺序颠倒怎么办?
  
  > 如phi(x1,y1)+phi(x2,y2)和phi(x1,y1)+phi(y2,x2)
  > 
  > 对于第二种，单纯寻找x1+y2和y1+x2肯定不合逻辑
  
  论文中有详细的版本：
  
  ![](figures/value_phi_func.png)

### 等价类设计

> ```cpp
> shared_ptr<Expression>
> GVN::valueExpr(Instruction *instr);
> ```

等价类涉及到针对指令设计、常量折叠、递归计算等，很复杂，需要拎出来单独讨论。

首先注意到传给传进去的参数是指令类型(指针)。需要`transferFunction`处理的指令，一次赋值的右式自然可以由指令类型得到，所以没有毛病。

指令有多种类型，也即lightIR中有多种赋值方式，而非单纯的伪代码中的二元运算。但是即使是已经在算法中讨论过的二元运算，写起来也不容易。

#### 生成等价类的逻辑

首先讨论生成等价类的逻辑：

- 二元运算`y op z`
  
  如果y、z都是常量，那么可以进行常量折叠，得到**一个**`ConstantExpression`类型。
  
  否则返回的是一个`BinaryExpression`类型，这个类型需要左右操作数，都是`Expression`类型，如果操作数是常量，使用`ConstantExpression`创建新的值表达式，否则递归调用`valueExpr`。
  
  > 这里为什么递归调用不会走到未定义？

- phi函数
  
  我们逻辑上把其改变成了copy，`transferFunction`应该维护这一点，所以认为没有phi函数传入。
  
  具体是`transferFunction`函数中的这几句话：
  
  ```cpp
  GVN::partitions
  GVN::transferFunction(Instruction *x, Value *e, partitions pin)
  {
      auto e_instr = dynamic_cast<Instruction *>(e);
      auto e_const = dynamic_cast<Constant *>(e);
      assert((not e or e_instr or e_const) &&
             "A value must be from an instruction or constant");
      // ……
      if (e) {
          if (e_const)
              ve = ConstantExpression::create(e_const);
          else
              ve = valueExpr(e_instr, &pin);
      } else
          ve = valueExpr(x, &pin);
  }
  ```

- 比较函数：和二元运算一致。

- 类型转换：添加新的表达式类型`CastExpression`，处理和二元操作类似。

- 其他产生赋值的指令，也会由`transferFunction`传递给`ValueExpr`，这些指令是：`load`、`alloca`和返回值非空的`call`。
  
  这里设计一种值表达式类型：`UniqueExpression`，这个表达式和任何其他都不等价，表现为`equiv`直接返回false。
  
  > 看到有同学在的表达式打印都是`add v1 v2`这种，而我是`add %op1=... %op2=...`，好整洁好漂亮，心动了，就搞他。
  > 
  > 因为等价类树的叶子节点就两个：`constant`和这个`Unique`
  > 
  > 常量打印对应的数字即可，而我想实现Unique打印v~i~的效果，所以在其中保存了等价类的值编号`index`，看起来值编号是等价类的属性，似乎不应该和表达式掺和，但是正如其名：UNIQUE，不应该与其他相同的，所以他一定是单独一个等价类，不受其他影响，index是恒定的。
  > 
  > 改好后，打印有如下效果：
  > 
  > ```
  > [INFO] (GVN.cpp:820L  run)
  > index: 9
  > leader: %op13 = call i32 @input()
  > value phi: nullptr
  > value expr: v9
  > members: {%op13 = call i32 @input(); }
  > ```

#### 若干需要梳理的问题

除此之外，关于等价类有几个命题一定要说明，这些是理解GVN的关键。

- 等价类中的ve一定存在吗？
  
  根据等价类的设计，ve一定是存在的，且等价类中`members_`中一定存在元素。

- ve一定唯一吗？
  
  从逻辑上，等价类集合中的元素享有共同的ve产生的结果，ve是唯一的
  
  从实现上，添加

- ve或者vpf能够作为代表吗？
  
  这个问题源于`transferFunction`的一句话：
  
  > if ve or vpf is in a class Ci in POUTs
  
  可以的，等价类中的元素都有唯一的表达式，其他等价类即使形式相同，操作数也不会相同，所以等价类和表达式其实是一一对应的关系。
  
  (这也解释了UNIQUE中传入index的合理性)

- 代表元如何选取？什么时候选取？
  
  目前只对常量传播的Constant特别设置了主元，负责设置为`members_`的第一个元素。

- 怎么判断等价类相等
  
  根据论坛上这个[例子](http://cscourse.ustc.edu.cn/forum/thread.jsp?forum=91&thread=68)，我发现值编号会有非必要的增长，即最终收敛时用到的编号是1、5、6，其中2、3、4都是迭代中用到的但是最后都没有体现。
  
  从这个例子中可以发现，迭代收敛时，是pout中对应分区的`members_`不变，值编号还是会变化的，所以判断等价类相等，应该比较`members_`集合。

- 等价类为空的判定，可以用`members_`做判断吗？
  
  我认为是可以的，存在情况：两个基本块汇合时，交出一个集合，它的members为空，但是ve不空：
  
  ```
  BB0: y =
       z =
  ; pout: [{v1,y}, {v2,z}]
  
  BB1: x1 = y + z ; preds = BB0
  ; pout: [{v1,y}, {v2,z}, {v3, x1, v1+v2}]
  
  BB2: x2 = y + z ; preds = BB0
  ; pout: [{v1,y}, {v2,z}, {v4, x2, v1+v2}]
  
  BB3: ... ; preds = BB1, BB2
  ```
  
  进入BB3时，对BB1和BB2的pout中等价类分别取交，执行`Intersect(Ci={v3, x1, v1+v2}, Cj={v4, x2, v1+v2}`，得到的是`{v1+v2}`，`members_`中没有成员，但是ve存在，我认为这种情况也应该判定结果为空集。
  
  因为最终反映到IR上，我们直接关心的都是`members_`中的成员，所以用`members_`的空代表等价类的空我觉得是合适的。

### 值编号的维护

#### 值编号的目的

> 编号即`index_`不能一直递增，`loop3.ll`检测了这一点。
> ![](figures/loop3.png)
> 关注`%op12`和基本块`label17`：
> 
> 第二次迭代过程中，`label17`的两个前驱作交集，对应的是两个分区分别是：
> 
> - `label11`的pout，第二次迭代结果
> 
> - `label24`的pout，第一次迭代结果
> 
> 如果每次新建等价类都使index递增，注意第二次经过`label11`新建出来的等价类编号和第一次也即`label24`那个不一样，这时候麻烦就来了：`INTERSECT`函数会交出一个`phi`函数。
> 
> 关键在于：index不应该递增，对于`%op12`，第二次迭代明明是同一个位置的定值，应该享有相同的值编号。

一个目标清晰起来：我要保证，不同迭代中，同一位置生成的等价类要享有相同的值编号，以标示同一个等价类。这里的同一个不是指完全相同，举例如下：

```
// partition: {}
x=1
// partition: {v1, 1, x}
y = 1
// partition: {v1, 1, x, y}
```

后两个分区具有同一值编号`v1`，但是内部包含了不同的元素。

所以值编号的作用是指示同一个等价类，而不表示相等。

#### 我的设计

> 助教有提示过：
> ![](figures/index_set.png)
> 
> 我尝试了第2种，因为这个最简单，但是发现不可行：对loop3，第一次迭代进入`label0`，编号从3开始记，但是第二次迭代就要从5开始，因为`label_Entry`和`label28`相交，会拆分出`%op1`和`%op7`，而我还是index递增的逻辑，所以两个分别占用3、4，导致`label0`的编号从5开始，这样一来，在第一次迭代中编号为3的`%op8`无论如何也分不到编号3了。

上边不成立是有一个本质的原因的。比如说`op1`，第一次迭代和`%op2`、`%op3`在一个等价类中，第二次被拆出来占用了一个新的编号(假设是3)，而`%op8`想嗔怪`%op1`占用了编号3，本来就不占理，因为`%op8`在最开始就应该从一个更大的编号开始使用，为前边的指令预留出充足的编号空间（数据流收敛的过程是等价类拆分的过程）。

我灵机一动，想出了下面这个维护方案：

- 首先，我遍历所有的指令是存在一个顺序的，我记录下这个信息

- 其次，等价类至多，也就是一条指令一个等价类

- 设计方案：每个指令的潜在值编号，是其遍历顺序。
  
  对一条指令执行转移函数时，如果有可以归属的等价类，就插入之，
  
  否则新建等价类的编号设置为遍历顺序。

这个方案可以保证一条指令执行后，如果新建了等价类，会产生相同的编号，以和后边的数据流标示同一个等价类，这样的编号空间预留可以避免编号冲突的问题。

实现上要注意两点：

- 每次调用针对指令的转移函数之前，都要重新设置值编号

- `Intersect(Ci, Cj)`中可能发现两个等价类不是相同的值编号，这时要新建phi等价类，并赋予一个精准的值编号：两个前驱中的定值，分别对应一个值编号，选择遍历顺序靠前的那个。

这个的实现就`Intersect`比较讲究技巧了，其他写起来都挺直观的。

### 常量传播的实现

### 所见非所得

- 论文中伪代码对于基本块的关注不是很多，但是我们的实现一定要围绕基本块进行，这个的解决对策说到了，其实和单条语句没有本质差异。

- 我们针对lightir优化，经常深入API中陷入到实现细节，还容易被C++的语言特性绊住，但是应该尝试从直观上理解：我们究竟要实现什么样的效果。这个就得去看ll文件找灵感。然后这还不够，回过头来看代码又呆住了，因为ll语句和那些类型对应不上，这个就是容易忽视的一点：看lightir类型的print函数，这个能帮我们直观地串联起实现细节和表象的ll文件。

- 到了实验的后半阶段，调试信息的解读就变得越来越重要了。感谢某位同学劝我不要在用gdb debug，而是改用vscode，用gdb确实太慢了。
  
  这里调试的困难其实不在于调试的技巧，更多是信息解读，很多时候，用了半个小时甚至一上午才明白错误的原因在哪里，这也来源于对算法的理解不足。

## 实验设计

> 设计见上述难点的描述

实现思路，相应代码，优化前后的IR对比（举一个例子）并辅以简单说明

### 思考题

1. 请简要分析你的算法复杂度
2. `std::shared_ptr`如果存在环形引用，则无法正确释放内存，你的 Expression 类是否存在 circular reference?
3. 尽管本次实验已经写了很多代码，但是在算法上和工程上仍然可以对 GVN 进行改进，请简述你的 GVN 实现可以改进的地方

## 实验总结

此次实验有什么收获

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

对本次实验的建议