在 Lab4.1 中，我们介绍了 SSA IR，并阐明了其优势。本次实验中我们需要在 SSA IR 基础上，实现一个基于数据流分析的冗余消除的优化 Pass : Global Value Numbering（全局值编号）。
GVN(Global Value Numbering) 全局值编号，是一个基于 SSA 格式的优化，通过建立变量，表达式到值编号的映射关系，从而检测到冗余计算代码并删除。本次实验采用的算法参考论文为：Detection of Redundant Expressions: A Complete and Polynomial-Time Algorithm in SSA 在该论文中，提出了一种适合 SSA IR ，多项式算法复杂度的数据流分析方式的算法，能够实现对冗余代码完备的检测。本次实验中，我们将在Light IR 上实现该数据流分析算法，并根据数据流分析结果删掉冗余代码，达到优化目的。
将IR抽象为具有空的entry block与exit block的控制流图（CFG）。块内包含形式为x = e的赋值语句，其中e为表达式，x为变量。每个bb块最多可以有两个前驱，有两个前驱的bb块被称为join block。
一个Expression（表达式）可以是一个常量，一个变量，或者是Expression也可以是 Expression被称作 phi 函数。基于 Lab4.1 对phi指令概念的理解，我们知道 phi 函数是出现在 join block 的起始处，而在实际的数据流分析过程中，我们会将 phi 指令作为 join block 前驱的赋值指令进行处理。
注：如下例子所示：形如
bb1:
x1 = 1 + 1
br bb3
bb2:
x2 = 2 + 2
br bb3
bb3:
x3=phi(x1,x2)
...为了实现 SSA 上 GVN 分析的完备性，我们在数据流分析中，将 phi 指令在对应前驱中转化为
bb1:
x1 = 1 + 1
x3 = x1
br bb3
bb2:
x2 = 2 + 2
x3 = x2
br bb3
bb3:
...两个表达式 e1,e2 如果被称作等价的，那么他们有着相同的运算符，并且操作数也是对应等价的。
一个 Value Expression（值表达式），
与值表达式类似，value phi-function 视作为一系列等价的 phi-function 的抽象。在本次 GVN 实验中，需要扩展 phi-function 的理解，例如如下ir片段的例子：
bb1:
y=x1+1
br bb3
bb2:
z=x2+1
br bb3
bb3:
x3=phi(x1,x2)
w3=x3+1对于 变量 w3 对应的 Expression x3+1，由于x3是phi function，因此可以通过expression 概念中对phi function的处理探测出：w3，y在bb1中等价，w3，z在bb2中等价，因此可以将 w3 视作是变量 y 与变量 z 在 bb3 处的合并，可以用
一个 Partition （分区）由一系列等价类组成，一个等价类是由一个值编号，和一系列成员组成。每个成员可以是：变量，常量，值表达式。同时，一个等价类可能会关联一个 value-phi-function。
Join 操作检测到达此处的所有路径共有的等价项。在 SSA 格式的 IR 中，变量只会被赋值一次，当程序点 p 支配 join block 时，在 p 点成立的等价关系，在 join block 处仍然成立。通过对 join block 的前驱 Partition 取交集，可以保留所有支配 join block 的程序点的等价关系。对于在每个路径的等价的探测，我们将在2.GVN算法中通过伪代码进行阐述。对于表达式的等价关系与变量等价关系的检测与判定，我们会分别阐述。
例如如下代码段：
bb1:
x1=1+1
y1=2+2
z1=x1+y1
br bb3
bb2:
x2=2+2
y2=3+3
z2=x2+y2
br bb3
bb3:
x3=phi(x1,x2)
y3=phi(y1,y2)
z3=phi(z1,z2)
z4=x3+y3在左分支bb1中，通过将 x3=phi(x1, x2)语句转换为前驱的复制语句 x3=x1 ，可以检测出，x3与x1在左分支路径上的等价性。同理也有x3与x2在右分支上的等价性。此为变量等价
同时，通过对z4=x3+y3的分析，可以看出，x3+y3 这个表达式，在bb1中与x1+y1等价，在bb2中与x2+y2等价，此为表达式等价，通过这个表达式等价的关系，可以分析出，z4与z1在bb1中变量等价，z4与z2在bb2中变量等价，因此可以建立z4的phi函数为phi(z1,z2)，进而可以导出z3与z4的变量等价，从而消除z3与z4的冗余。
TransferFunction 作用于一条语句s：x=e 上，接受 partition 记为
bb1:
x1=1+1
y1=2+2
z1=x1+y1
br bb3
bb2:
x2=2+2
y2=3+3
z2=x2+y2
br bb3
bb3:
x3=phi(x1,x2)
y3=phi(y1,y2)
z3=phi(z1,z2)
z4=x3+y3在对z4=x3+y3这个表达式执行
其中，x 为 z4, e 为 x3+y3
在 x3+y3 对应的 expression 表达式。
但是，对 x3+y3 进一步分析可以得到：因为x3和y3都是phi，x3+y3可以表示为 bb1 中 x1+y1 与 bb2 中 x2+y2 的两个表达式的合并，因此可以记为 phi(x1+y1, x2+y2)
接下来，可以检测到变量 z1 与 x1+y1 expression 在bb3前驱bb1中的等价关系，变量 z2 与 x2+y2 expression 在bb3前驱bb2中的等价关系。因此可以检测到 phi(x1+y1, x2+y2)与 phi（z1,z2）的等价关系。
进而得到 变量 z3 与 z4 是等价的，x3 + y3 expression 的计算是冗余的。
注：这里的
本小节附上了原论文中附的伪代码，伪代码中给出了五个主函数的逻辑，这里自顶向下梳理一下：
detectEquivalences(G) 包含了最主要的数据流迭代过程，传入参数 G 为抽象的数据流分析的 CFG 图结构，实现中可以以函数为分析的基本单位来执行此函数，迭代初始时，将各个 Partition 初始化为顶元Top， 定义为Join(P, Top) = P = Join(Top, P)
注：此函数中的 statement 的概念对应前述的一条语句
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
Join 操作仅仅在某个语句有两个前驱时被触发，注意：在join操作执行之前，join block 中的 phi 语句会作为 copy statement 加入 join block 对应的两个前驱末尾处。细节处理方式见expression 概念的注栏。
Join(P1, P2)
P = {}
for each pair of classes Ci ∈ P1 and Cj ∈ P2
Ck = Intersect(Ci, Cj)
P = P ∪ Ck // Ignore when Ck is empty
return P
Intersect(Ci, Cj)
Ck = Ci ∩ Cj // set intersection
if Ck ！= {} and Ck does not have value number
then
Ck = Ck ∪ {vk} // vk is new value number
Ck = (Ck − {vpf}) ∪ {φb(vi, vj)}
// vpf is value φ-function in Ck, vi ∈ Ci, vj ∈ Cj, b is join block
return Ck
TransferFunction 接受一个赋值语句 x=e（x是变量，e为表达式），与一个 partition
注1： 在 lightir 的设计中，普通语句的 x 与 e 存在同一个 Instruction 类中，参考lightir核心类，Instruction 本身可以视作为 x，而通过 Instruction 成员运算符，和成员操作数可以抽象的组成 expression e。
注2： phi 语句中需要经转换为 copy 语句，x 与 e 将不存在同一个 Instruction 中，请仔细思考区分一下。
TransferFunction(x = e, PINs)
POUTs = PINs
if x is in a class Ci in POUTs
then Ci = Ci − {x}
ve = valueExpr(e)
vpf = valuePhiFunc(ve,PINs) // can be NULL
if ve or vpf is in a class Ci in POUTs // ignore vpf when NULL
then
Ci = Ci ∪ {x, ve} // set union
else
POUTs = POUTs ∪ {vn, x, ve : vpf} // vn is new value number
return POUTs
valuePhiFunc(ve,P)
if ve is of the form φk(vi1, vj1) ⊕ φk(vi2, vj2)
then
// process left edge
vi = getVN(POUTkl, vi1 ⊕ vi2)
if vi is NULL
then vi = valuePhiFunc(vi1 ⊕ vi2, POUTkl)
// process right edge
vj = getVN(POUTkr, vj1 ⊕ vj2)
if vj is NULL
then vj = valuePhiFunc(vj1 ⊕ vj2, POUTkr)
if vi is not NULL and vj is not NULL
then return φk(vi, vj)
else return NULL
在本次实验中，请仔细阅读3.1 GVN pass 实现内容要求，根据要求补全src/optimization/GVN.cpp，include/optimization/GVN.h中关于 GVN pass 数据流分析部分，同时需要在 Reports/4-ir-opt/ 目录下撰写实验报告。为了在评测中统一分析结果，请大家采用 lab3 的 TA-impl 分支提供的答案来完成后续实验。
GVN 通过数据流分析来检测冗余的变量和计算，通过替换和死代码删除结合，实现优化效果。前述的例子中主要以二元运算语句来解释原理，且助教为大家提供了代码替换和删除的逻辑，除此之外，需要完成的方向有：
-
对冗余指令的检测与消除包括
-
二元运算指令：add, sub, mul, sdiv, fadd, fsub, fmul, fdiv
-
地址运算指令：getelementptr
-
比较指令：cmp, fcmp
-
类型转换指令：zext, fptosi, sitofp
-
-
对于 call 指令冗余的检测与消除：
-
对纯函数的冗余调用需要进行检测与消除
-
对于非纯函数（例如 input()）的多次调用不得分析成同一个等价类中
注：助教提供了纯函数分析，见FuncInfo.h，该 Pass 的接口
is_pure_function接受一个lightIR Function，判断该函数是否为纯函数；对于纯函数，如果其参数等价，对这个纯函数的不同调用也等价。 -
-
常量传播：在数据流分析的过程中，需要使用常量折叠来实现常量传播，从而将可在编译时计算的结果计算好，减少运行时开销。
- 本次实验要求借助 GVN 的数据流分析框架，实现常量传播，在含有常量的等价类中，通过将 leader_ 设置为 Constant* 类型，在常量传播后将指令替换成相应的常数。
注：助教提供了常量折叠类，在辅助类的介绍中
-
value phi function 的冗余的检测与消除：
- 通过 value phi function 可以在某个程序点比较两个变量每条路径的等价关系，为了简化这部分逻辑，仅考察
phi(a+b, c+d)与phi(a,c)+phi(b,d)之间的冗余。+ 代表 add, sub, mul, sdiv, fadd, fsub, fmul, fdiv。a,b,c,d 代表不含常数的等价类
- 通过 value phi function 可以在某个程序点比较两个变量每条路径的等价关系，为了简化这部分逻辑，仅考察
我们会在测试样例中对这三点进行考察。
case 考察范围说明：在 Lab4-2 的公开 case 与隐藏 case 中，以下情况不会出现：
- 不会对加法乘法运算的交换律，结合律造成的冗余进行考察。
- 不会对访存指令之间的等价性进行考察。
- 对于 value phi function 的冗余仅仅考察
phi(a+b, c+d)与phi(a,c)+phi(b,d)之间的冗余。（其中 + 代表四则二元运算+ - * /，value phi function 上某一路径的常量传播可以不考虑，例如 case 不会涉及如下情况冗余phi(0, c+d)与phi(0,c)+phi(0,d)）
注：我们为大家提供了冗余删除的函数 GVN::replace_cc_members ，只需要正确填充在 GVN 类中的 pout 变量，我们的替换逻辑将会根据每个 bb 的 pout 自行使用CongruenceClass 的 leader_ 成员来替换在此 bb 内与其等价其他指令。
在上述对 GVN 概念的介绍中，为了能让大家专注于核心数据流分析逻辑的实现，我们为大家提供了一些相应实现的辅助类，并在注释里解释了其相应用途，请注意与前述的 GVN 的抽象概念结合，理解其设计，并补充必要的类成员的实现。
GVN.h:
class ConstFolder; // 常量折叠类，用于折叠操作数都是常量的指令
// 该 namespace 下，包含了用于判断 expression 等价的结构，我们提供了 binary expression，phi expression，constant expression 的结构，请根据测试用例添加你需要的其他 expression 的结构，具体细节请据 GVN.h 结合代码与注释理解
namespace GVNExpression {
class Expression; // 所有 expression 类型的基类
class ConstantExpression; // 常量 expression 类型
class BinaryExpression; // 二元运算 expression 包括 + - * /
class PhiExpression; // phi expression 类型，表示不同路径的 expression 在此的合并
}
struct CongruenceClass; // 对应伪代码中等价类的概念，分析结果会根据此类 dump 至 json 文件中，代码替换与消除逻辑也根据此结构实现
class GVN; // GVN pass核心实现逻辑，除一些用的上的辅助函数外，重点补齐此处与伪代码对应的核心函数，其中run()函数是 pass 启动的入口，已经为大家补充好。GVN.cpp:
namespace utils // 一些用于输出的函数，可方便调试，以及将结果 dump 到 json 文件中的方法本次实验使用了由 C++ 编写的 LightIR 来在 IR 层面完成优化化简，在include/optimization/PassManager.hpp中，定义了一个用于管理 Pass 的类PassManager。它的作用是注册与运行 Pass 。它提供了以下接口：
PassManager pm(module.get())
pm.add_Pass<GVN>(emit, dump_json) // 注册Pass，emit为true时打印优化后的IR
pm.run() // 按照注册的顺序运行 Pass 的 run() 函数mkdir build && cd build
cmake ..
make -j
make install为了便于大家进行实验，助教对之前的cminusfc增加了选项，用来选择是否开启某种优化，通过-mem2reg开关来控制优化 Pass 的使用，当需要对 .cminus 文件测试时，可以这样使用：
./cminusfc [ -mem2reg ] [ -gvn [ -dump-json ] ] <input-file>其中，gvn pass 需要在 mem2reg pass 运行后运行。
助教贴心地为大家准备了自动测试脚本，它在 tests/4-ir-opt 目录下，使用方法如下：
python3 lab4_evals.py [ -gvn-analysis ] [ -gvn ]该脚本可以在任意目录下运行
python3 tests/4-ir-opt/lab4_evals.py [ -gvn-analysis ] [ -gvn ]其中 -gvn-analysis 对 GVN 分析结果的正确性进行判断，执行结果如下所示：
========== GlobalValueNumberAnalysis ==========
Compiling -mem2reg -emit-llvm -gvn -dump-json
0%| | 0/4 [00:00<?, ?it/s]
Compile bin.cminus success
generate json bin.cminus success
25%|███▊ | 1/4 [00:00<00:00, 8.38it/s]
Compile loop3.cminus success
generate json loop3.cminus success
50%|███████▌ | 2/4 [00:00<00:00, 7.21it/s]
Compile pure_func.cminus success
generate json pure_func.cminus success
75%|███████████▎ | 3/4 [00:00<00:00, 4.08it/s]
Compile single_bb1.cminus success
generate json single_bb1.cminus success
100%|███████████████| 4/4 [00:00<00:00, 4.64it/s]
bin.cminus: 1.0
loop3.cminus: 1.0
pure_func.cminus: 1.0
single_bb1.cminus: 1.0-gvn 会执行测试文件，比对你实现的 GVN 算法优化后的程序，与助教的基准程序的运行时间。
========== GlobalValueNumber ==========
Compiling -mem2reg
100%|███████████████| 2/2 [00:00<00:00, 8.22it/s]
Evalution
100%|███████████████| 2/2 [00:17<00:00, 6.44s/it]
Compiling -mem2reg -gvn
100%|███████████████| 2/2 [00:00<00:00, 5.67it/s]
Evalution
100%|███████████████| 2/2 [00:13<00:00, 4.36s/it]
Compiling baseline files
100%|███████████████| 2/2 [00:00<00:00, 13.70it/s]
Evalution
100%|███████████████| 2/2 [00:09<00:00, 3.24s/it]
testcase before optimization after optimization baseline
constant.cminus 0.70 0.24 0.24
transpose.cminus 3.72 3.04 3.03
root@3fd22a9ed627:/labs/2022fall-compiler_cminus-taversion/tests/4-ir-opt#如果要增加样例，直接在样例目录中添加文件即可，命名参考目录下的其他文件。
-
为了大家能够循序渐进地实现 GVN pass，助教给出一个实现上的规划：
-
使用 GVN pass 分析单一基本块的程序 case
补充
detectEquivalences函数（无需处理 Join ），在转移方程transferFunction中，为每个变量创建等价类。 -
使用 GVN pass 分析带有冗余计算的单一基本块的程序 case，并在分析过程中进行常量传播
依照伪代码补全转移方程
transferFunction，得到正确的等价类，将输出结构 dump 至 json 文件，与手动推算结果进行比对。 -
使用 GVN pass 分析带有选择语句的程序 case，处理phi语句之间的冗余
完善
detectEquivalences，实现合并两个前驱分区的合并算法Join，和valuePhiFunc，注意本次实验只考察phi(a+b, c+d)与phi(a,c)+phi(b,d)之间的冗余。 -
正确分析带有循环的程序
完成了前三点后，你的 GVN 应该比较完整了，可以根据带循环的简单程序来调试。
-
-
Lab3 的测试样例仍然可以用来测试优化正确性
-
使用 logging 工具来打印调试信息，以及 GDB 等软件进行单步调试来检查错误的原因
logging 是帮助大家打印调试信息的工具，如有需求可以阅读文档后进行使用
.
├── CMakeLists.txt
├── Documentations
│ ├── ...
│ ├── common
│ | ├── LightIR.md LightIR 相关文档
│ | ├── logging.md logging 工具相关文档
│ | └── cminusf.md cminus-f 的语法和语义文档
│ └── 4.2-gvn
│ ├── gvn.pdf 本实验参考文献原文
│ └── README.md Lab4 实验文档说明（你在这里）
├── include 实验所需的头文件
│ ├── ...
│ ├── optimization
│ │ ├── Mem2Reg.hpp Mem2Reg
│ │ ├── Dominators.hpp 支配树
│ │ └── GVN.h GVN <--- 修改并提交
│ ├── cminusf_builder.hpp
| └── ast.hpp
├── Reports
│ ├── ...
│ └── 4.2-gvn
│ └── report.md lab4 本次实验报告模板 <--- 修改并提交
│
├── src
│ ├── ...
│ └── optimization
│ ├── Mem2Reg.cpp Mem2Reg
│ ├── Dominators.cpp 支配树
│ └── GVN.cpp GVN <--- 修改并提交
│
└── tests
├── ...
└── 4-ir-opt
├── testcases 助教提供的测试样例
└── lab4_test.py 助教提供的测试脚本
-
提交要求 本实验是个人实验，需要将代码上传至gitlab实验仓库，并在希冀评测平台上提交仓库链接。
-
需要填补
include/optimization/GVN.h,src/optimization/GVN.cpp，在Reports/4.2-gvn/report.md中撰写实验报告。- 实验报告内容包括
实验要求、实验难点、实验设计、实验结果验证、思考题、实验反馈等，具体见
Reports/4.2-gvn/report.md
- 实验报告内容包括
实验要求、实验难点、实验设计、实验结果验证、思考题、实验反馈等，具体见
-
本次实验不提供希冀平台在线测试通道，将在 soft ddl 时收取同学仓库
master分支下include/optimization/GVN.h，src/optimization/GVN.cpp文件，请同学们在ddl前将自己的最新分支push到 git 仓库上 -
本次实验报告以 pdf 格式提交到希冀平台对应提交通道
-
-
评分标准: 实验完成分（总分 60 分）组成如下：
-
实验报告 (5 分)
需要回答 Reports 目录下实验报告模板的思考题。
-
easy case（40分）
助教提供了 4 个公开测试用例，并保留 4 个隐藏用例，根据每个用例 dump 出来的分析结果正误给分。json 文件判断的逻辑如下，仅对每个bb的 pout 进行判断。
例如：
"pout": { "label_entry": [["%op0", ], ["%op1", ], ["%op2", ], ], "label3": [["%op0", ], ["%op1", ], ["%op2", ], ["%op4", "%op10", ], ["%op5", "%op9", ], ["%op6", "%op8", ], ], "label7": [["%op0", ], ["%op1", ], ["%op2", ], ["%op10", ], ["%op9", ], ["%op11", "%op8", ], ], "label12": [["%op0", ], ["%op1", ], ["%op2", ], ["%op13", "%op10", ], ["%op14", "%op9", ], ["%op15", "%op8", ], ],}
对于分值为 x，n 个基本块的程序，每个 bb 分析结果为
$x/n$ 分，某个bb的分析结果多或者少一个等价类，或有分析错误的等价类，该 bb 分析结果没有分值。 -
performance case（15分）
助教提供了 2 个公开case，并保留 2 个隐藏用例。以及助教实现优化后的 baseline.ll ，优化效果按照如下方式给分（执行结果不正确则此项分数为0）
对于每一个testcase: (before_optimization-after_optimization)/(before_optimization-baseline) > 0.8 得满分 (before_optimization-after_optimization)/(before_optimization-baseline) > 0.5 得85%分数 (before_optimization-after_optimization)/(before_optimization-baseline) > 0.2 得60%分数 -
禁止执行恶意代码，违者本次实验0分处理
-
-
迟交规定
-
Deadline: 2023/01/14 23:59:59 (北京标准时间，UTC+8)本次实验不接受补交
-
-
关于抄袭和雷同 经过助教和老师判定属于实验抄袭或雷同情况，所有参与方一律零分，不接受任何解释和反驳（严禁对开源代码或者其他同学代码的直接搬运）。 如有任何问题，欢迎提issue进行批判指正。