llvm gvn

[lfeng14]

流程如下：

---

🧩 1. 构建支配树（Dominator Tree）

因为：

• 如果 A 支配 B，那么 A 的值在 B 一定可用
• GVN 只能用“支配它的表达式”来替换当前表达式

---

🧩 2. 为每条指令计算“值编号”

GVN 会为每条指令构造一个“表达式 key”，例如：

add %a, %b

key = (opcode=add, op1=VN(a), op2=VN(b))

如果另一个 add 的 key 一样，那么它们等价。

---

🧩 3. 使用哈希表（value table）查找等价表达式

GVN 内部维护一个：

map<ExpressionKey, ValueNumber>

如果当前表达式的 key 已存在：

• 说明之前已经计算过相同表达式
• 当前指令可以直接替换成之前的值

---

🧩 4. 特殊处理 load/store（内存分析）

GVN 会做简单的 alias 分析：

• 如果两个 load 来自同一地址
• 且中间没有 store 修改该地址
• 那么 load 是等价的

这就是“冗余 load 消除”。

---

🧩 5. 替换冗余指令并删除死代码

当 GVN 发现：

%2 = add %a, %b

等价于：

%1 = add %a, %b

它会：

• 用 %1 替换 %2
• 删除 %2（如果无其他用途）

---