# 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`，淦。 改完这些，终于能跑通第一版本了…… ### 等价类设计 > ```cpp > shared_ptr > 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(e); auto e_const = dynamic_cast(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。 #### 若干需要梳理的问题 除此之外，关于等价类有几个命题一定要说明，这些是理解GVN的关键。 - 等价类中的ve一定存在吗？ 根据等价类的设计，ve一定是存在的，且等价类中`members_`中一定存在元素。 - ve一定唯一吗？ 从逻辑上，等价类集合中的元素享有共同的ve产生的结果，ve是唯一的 从实现上，添加 - ve或者vpf能够作为代表吗？ 这个问题源于`transferFunction`的一句话： > if ve or vpf is in a class Ci in POUTs - 代表元如何选取？什么时候选取？ - 怎么判断等价类相等 根据论坛上这个[例子](http://cscourse.ustc.edu.cn/forum/thread.jsp?forum=91&thread=68)，我发现值编号会有非必要的增长，即最终收敛时用到的编号是1、5、6，其中2、3、4都是迭代中用到的但是最后都没有体现。 从这个例子中可以发现，迭代收敛时，是pout中对应分区的`members_`不变，值编号还是会变化的，所以判断等价类相等，应该比较`members_`集合。 - 什么时候给新的值编号？ 1. 执行转移函数发现没有可以归属的等价类时 2. 求交巴拉巴拉还没搞清楚那里 - 等价类为空的判定，可以用`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_`的空代表等价类的空我觉得是合适的。 | 类型 | 处理 | | ---------------- | ------------------------- | | 二元运算 | 依伪代码 | | 没有返回值的 | 不处理 | | phi函数 | 本块中的不管，后继块的做考虑 | | 函数调用 | 有返回值的考虑等价类，**注意后边纯函数的处理** | | 产生指针(GEP、alloca) | 先为返回值单独新建等价类 | | 类型转换及0扩展 | 单独新建等价类 | | 比较 | 根据op和操作数递归判断，应该和二元运算类似 | | load | 单独新建等价类 | ### 对于函数`Intersect(Ci, Cj )` 伪代码中，一个等价类是一个集合，求交后，v~k~是自然而然的在或不在新集合中，但是实现中并不这么简单，如何对这样的两个结构体进行逻辑上的取交： ```cpp struct CongruenceClass { size_t index_; Value *leader_; std::shared_ptr value_expr_; std::shared_ptr value_phi_; std::set 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` 因此，伪代码中对集合的求交，对应到实现上，就是对以上四个域求交。 ### 对于函数`valuePhiFunc(ve, P)` - 输入就一个分区，实际上要用到两个前驱的分区，怎么处理？ 传入基本块做参数。 - 二元运算的顺序颠倒怎么办? > 如phi(x1,y1)+phi(x2,y2)和phi(x1,y1)+phi(y2,x2) > > 对于第二种，单纯寻找x1+y2和y1+x2肯定不合逻辑 应该不会有这种情况：phi表达式，追根溯源是在join时产生的： ```cpp GVN::join(const partitions &P1, const partitions &P2); ``` 这里的分区是严格按照`Basicblock`的方法`get_pre_basic_blocks()`的返回顺序传入的，所以不会有担心的情况发生。 ### 所见非所得 两方面： - 论文中伪代码对于基本块的关注不是很多，但是我们的实现一定要围绕基本块进行，这个的解决对策说到了，其实和单条语句没有本质差异。 - 我们针对lightir优化，经常深入API中陷入到实现细节，还容易被C++的语言特性绊住，但是应该尝试从直观上理解：我们究竟要实现什么样的效果。这个就得去看ll文件找灵感。然后这还不够，回过头来看代码又呆住了，因为ll语句和那些类型对应不上，这个就是容易忽视的一点：看lightir类型的print函数，这个能帮我们直观地串联起实现细节和表象的ll文件。 ## 实验设计 ### join_helper ### _TOP ### transferFunction(Basicblock) ### 实现思路，相应代码，优化前后的IR对比（举一个例子）并辅以简单说明 ### 思考题 1. 请简要分析你的算法复杂度 2. `std::shared_ptr`如果存在环形引用，则无法正确释放内存，你的 Expression 类是否存在 circular reference? 3. 尽管本次实验已经写了很多代码，但是在算法上和工程上仍然可以对 GVN 进行改进，请简述你的 GVN 实现可以改进的地方 ## 实验总结 此次实验有什么收获 ## 实验反馈（可选 不会评分） 对本次实验的建议