什么是 ‘Global Value Numbering’ (GVN)？编译器如何识别代码中逻辑上完全相等的冗余表达式

各位编程专家，

欢迎来到今天的技术讲座。我们将深入探讨编译器优化领域一个强大而基础的技术——“Global Value Numbering”（GVN），即全局值编号。这个概念听起来可能有些抽象，但其核心思想却非常精妙：它不是简单地比较表达式的语法结构，而是致力于识别并消除那些在逻辑上完全等价的、计算出相同结果的冗余表达式，即便这些表达式在程序的各个角落以不同的形式出现。

在现代高性能计算的背景下，每一次计算、每一次内存访问都可能成为性能瓶颈。编译器优化的核心任务之一，就是尽可能地减少这些不必要的开销。而冗余计算，无疑是性能的巨大浪费。今天，我们将剥开GVN的层层概念，从其基本原理，到如何在复杂的控制流中追踪值的同一性，直至其在SSA（Static Single Assignment）形式下的强大威力，并辅以详尽的代码示例，希望能为大家提供一个全面而深入的理解。

---

一、 冗余计算：性能的无形杀手

在我们的日常编程中，常常会不经意间写出重复的计算。有时是为了代码的清晰性，有时是由于程序的演变，有时则是对底层优化机制缺乏了解。例如：

// 示例1：局部冗余
void calculate_area(int length, int width) {
    int area_rect = length * width;
    // ... 100行代码 ...
    int perimeter = 2 * (length + width);
    // ... 更多代码 ...
    int another_area_calc = length * width; // 冗余计算
    // ...
}

// 示例2：跨基本块的冗余
int process_data(int a, int b, int c) {
    int x = a + b;
    if (c > 0) {
        int y = x * 2;
        return y + (a + b); // (a + b) 冗余
    } else {
        int z = x * 3;
        return z - (a + b); // (a + b) 冗余
    }
}

在上面的示例中，length * width 和 a + b 都出现了多次。一个简单的局部优化（如局部公共子表达式消除，Local Common Subexpression Elimination, L-CSE）可以处理同一个基本块内的冗余。例如，在calculate_area函数中，如果another_area_calc = length * width;紧跟在area_rect = length * width;之后，并且中间没有修改length或width的操作，那么L-CSE可以很容易地消除它。

然而，当冗余表达式分布在不同的基本块中，或者被变量重命名所掩盖时，L-CSE就显得力不从心了。process_data函数中的a + b就是一个典型的跨基本块冗余，它在条件分支的两个路径中都重复出现。更复杂的情况可能涉及多个变量，例如x = a + b和y = b + a，或者p = (c * d) + e和q = e + (d * c)。这些表达式在语法上可能不同，但如果操作数的值是相同的，它们在语义上计算的是同一个结果。

为了解决这种“全局性”的冗余问题，我们需要一种更强大的技术，能够穿透控制流的迷雾，识别出不同位置、不同形式但逻辑上等价的计算。这就是全局值编号（GVN）诞生的初衷。

---

二、 全局值编号（GVN）的核心理念

GVN 的核心思想是为程序中每一个独一无二的计算结果分配一个唯一的“值编号”。如果两个表达式，无论它们在代码中是如何书写的，最终计算出的是同一个逻辑值，那么它们就应该拥有相同的“值编号”。一旦我们确定了某个表达式的值编号已经存在（意味着这个值已经被计算过），我们就可以将当前的表达式替换为对先前计算结果的引用，从而消除冗余。

GVN的强大之处在于它关注的是值的等价性，而非表达式的语法等价性。这使得它能够识别并消除以下类型的冗余：

1. 语法完全相同的冗余（Syntactically Identical）：如 a + b 和 a + b。
2. 语法不同但语义等价的冗义（Syntactically Different, Semantically Identical）：
   • 操作数顺序不同：对于可交换操作（如加法、乘法），a + b 和 b + a 计算的是同一个值。
   • 变量重命名：x = a + b 之后，y = a + b，如果a和b的值未变，那么x和y的值是相同的。
   • 不同操作符但等价：例如，x * 2 和 x << 1 (对于整数)。
   • 常量折叠：1 + 2 会被视为与 3 具有相同的值编号。

举例说明：

int foo(int p, int q, int r) {
    int v1 = p + q;
    int v2 = r * 2;
    int v3 = q + p; // (q + p) 和 (p + q) 语义等价
    int v4 = p + r;
    int v5 = p + q; // (p + q) 和 (p + q) 语义等价
    return v1 + v2 + v3 + v4 + v5;
}

在上述代码中：

• p + q 第一次出现，得到一个值编号VN1。v1被赋予VN1。
• r * 2 第一次出现，得到VN2。v2被赋予VN2。
• q + p 出现，由于加法可交换，它与 p + q 逻辑等价，所以它也得到VN1。v3被赋予VN1。
• p + r 第一次出现，得到VN3。v4被赋予VN3。
• p + q 再次出现，与第一次的 p + q 逻辑等价，所以它也得到VN1。v5被赋予VN1。

最终，v3和v5的计算都可以被消除，直接引用v1的值。

GVN通常在编译器的中间表示（Intermediate Representation, IR）上进行，例如三地址码或SSA形式。IR提供了一个抽象的、结构化的程序视图，使得分析和转换更为方便。

---

三、 GVN算法详解：追踪值的足迹

GVN算法的核心在于如何系统地为每一个计算结果分配值编号，并在遇到新表达式时，能够高效地判断它是否与某个已有的值编号等价。这通常涉及对程序控制流图（Control Flow Graph, CFG）的遍历和对数据结构的巧妙运用。

3.1 GVN 的前置条件：中间表示与控制流图

GVN 算法通常运行在程序的中间表示 (IR) 上。IR 是一种介于源代码和机器码之间的抽象表示，它移除了源代码的语法细节，专注于程序的语义。常见的 IR 形式包括：

• 三地址码 (Three-Address Code, TAC)：每条指令最多包含三个操作数，形式如 result = operand1 op operand2。
• 静态单赋值形式 (Static Single Assignment Form, SSA)：每个变量在程序中只被赋值一次。如果一个变量在不同的控制流路径上可能被赋予不同的值，那么在这些路径汇合的地方（如 if-else 语句的末尾），会引入特殊的 Φ (Phi) 函数来合并这些值。

控制流图 (CFG) 则是 GVN 进行全局分析的基石。CFG 由基本块 (Basic Blocks) 组成，每个基本块是一段连续的指令序列，其中只有一个入口点和一个出口点。基本块之间通过边 (Edges) 连接，表示可能的控制流转移。CFG 允许编译器理解程序的执行路径，从而进行跨基本块的分析。

3.2 核心数据结构

为了实现 GVN，我们需要维护以下关键数据结构：

1. ValueNumber 类型：一个简单的整数或唯一标识符，用于代表一个值的编号。
2. ExpressionKey (表达式键)：这是一个结构体，用于唯一地描述一个表达式。它通常包含：
   • 操作符 (OpCode)：例如 ADD, MUL, LOAD 等。
   • 操作数的 ValueNumber 列表：而不是操作数本身的变量名。这是 GVN 区分于简单 CSE 的关键。
   • 常量值：如果表达式包含常量，常量本身的值可以作为其值编号的一部分。
   • 其他上下文信息：例如，对于内存操作，可能需要内存地址的 ValueNumber。
     ExpressionKey 的重要性在于其“规范化 (Canonicalization)”能力。 例如，对于可交换操作 A + B 和 B + A，它们应该生成相同的 ExpressionKey。这可以通过对操作数的值编号进行排序来实现，例如 ADD(min(VN_A, VN_B), max(VN_A, VN_B))。
3. global_value_map (全局值映射)：std::map<ExpressionKey, ValueNumber>
   • 键 (Key)：规范化后的 ExpressionKey。
   • 值 (Value)：分配给该表达式的唯一 ValueNumber。
     这个映射是 GVN 的核心，它记录了所有已计算的、具有唯一值编号的表达式。
4. vn_to_defining_instr (值编号到定义指令的映射)：std::map<ValueNumber, IRInstruction*>
   • 键 (Key)：一个 ValueNumber。
   • 值 (Value)：定义这个 ValueNumber 的第一个 IR 指令。这个指令的计算结果通常会被保留，而后续计算出相同值的指令则会被替换。
5. current_var_vns (当前变量值编号映射)：std::map<Variable*, ValueNumber>
   • 键 (Key)：一个 IR 变量。
   • 值 (Value)：该变量当前所持有的 ValueNumber。
     这个映射在遍历 CFG 时，用于追踪在特定执行路径上变量的最新值。对于 SSA 形式的 IR，这个映射管理起来会简单很多，因为每个变量只被赋值一次。

3.3 GVN 算法的基本流程（非SSA形式）

对于非 SSA 形式的 IR，GVN 算法需要更复杂的路径敏感分析，通常涉及迭代数据流分析或深度优先搜索 (DFS) 遍历，并伴随上下文敏感的 current_var_vns 管理。

1. 初始化：
   • 为所有常量分配唯一的 ValueNumber。
   • 为函数参数分配初始 ValueNumber。
   • 清空 global_value_map 和 vn_to_defining_instr。
   • 初始化 next_vn = 0 (或从某个起始值开始)。
2. CFG 遍历：通常以支配者树 (Dominator Tree) 的前序遍历顺序或 DFS 顺序遍历基本块。
   • 进入基本块 B：
     • 从 B 的所有前驱基本块中收集 current_var_vns 信息。如果一个变量在所有前驱中都具有相同的 ValueNumber，则它在 B 的入口处也具有该 ValueNumber。如果不同，或者变量在该路径上未定义，则需要特殊处理（可能意味着该变量的值在 B 中是新的或不确定的）。这正是 SSA 形式能极大简化 GVN 的原因。
     • 创建 B 的局部 current_var_vns 副本，用于跟踪本块内的变量值。
   • 处理基本块 B 内的每条指令 instr：
     1. 获取操作数的值编号：对于 instr 的每个操作数 op_i：
        • 如果 op_i 是常量，获取其预分配的 ValueNumber。
        • 如果 op_i 是变量 V，则从 B 的局部 current_var_vns 中查找 V 的 ValueNumber。
        • 如果 op_i 是其他指令的结果，则获取该指令的 ValueNumber。
     2. 规范化表达式：根据操作符和操作数的 ValueNumber 列表，创建 instr 的 ExpressionKey。确保对可交换操作进行排序等规范化处理。
     3. 查询 global_value_map：检查 global_value_map 中是否已存在 expr_key。
        • 如果存在 (existing_vn = global_value_map[expr_key])：
          • 这意味着 instr 计算了一个已经存在的值。instr 是冗余的。
          • 将 instr 标记为冗余，并记录它应该被替换为 vn_to_defining_instr[existing_vn] 的结果。
          • 如果 instr 定义了一个变量 result_var，则更新 B 的局部 current_var_vns：current_var_vns[result_var] = existing_vn。
        • 如果不存在：
          • 这是一个新的、独一无二的值。
          • 分配一个新的 ValueNumber：new_vn = next_vn++。
          • 将 expr_key 和 new_vn 存入 global_value_map。
          • 将 new_vn 和 instr 存入 vn_to_defining_instr (此 instr 现在是该值的定义点)。
          • 如果 instr 定义了一个变量 result_var，则更新 B 的局部 current_var_vns：current_var_vns[result_var] = new_vn。
   • 退出基本块 B：
     • 将 B 的局部 current_var_vns 传递给其后继基本块，用于后续块的入口状态计算。

3.4 GVN 在 SSA 形式下的简化与增强

GVN 在静态单赋值形式 (SSA) 的 IR 上运行时，其效率和精确度会得到显著提升。SSA 形式的两个核心特性极大地简化了 GVN：

1. 每个变量只被赋值一次：这意味着在任何给定点，一个变量的 ValueNumber 是明确的，消除了多重定义带来的歧义。
2. Φ (Phi) 函数：显式地合并来自不同控制流路径的值。例如，x3 = Φ(x1, x2) 表示 x3 的值取决于从哪个前驱路径到达当前基本块，如果从一个路径来，x3 的值是 x1；如果从另一个路径来，x3 的值是 x2。

GVN 在 SSA 形式下的算法流程：

1. 转换到 SSA 形式：首先，将程序的 IR 转换为 SSA 形式。这是一个复杂但成熟的编译器前端步骤。
2. 初始化：同前，为常量和函数参数分配 ValueNumber。
3. CFG 遍历：通常以支配者树的后序遍历 (Post-order Traversal) 进行，这样可以确保在处理一个基本块时，其所有后继（以及它们的 Φ 函数）都已经处理完毕，或者至少其支配者已经处理完毕。
4. 处理基本块中的每条指令 instr：
   • 处理 Φ 函数：result_var = Φ(operand1, operand2, ...)
     • 获取所有 operand_i 的 ValueNumber。
     • 创建 Φ 函数的 ExpressionKey：PHI(sorted_operand_vns)。对操作数 ValueNumber 列表进行排序是关键，以确保 Φ(x1, x2) 和 Φ(x2, x1) 具有相同的键。
     • 查询 global_value_map。如果存在，则 result_var 具有该 existing_vn。否则，分配新的 ValueNumber 并更新映射。
   • 处理其他指令：result_var = op(operand1, operand2, ...)
     • 获取所有 operand_i 的 ValueNumber。在 SSA 中，一个变量的 ValueNumber 就是定义它的指令的 ValueNumber。
     • 创建 instr 的 ExpressionKey，进行规范化。
     • 查询 global_value_map。如果存在，则 result_var 具有该 existing_vn。否则，分配新的 ValueNumber 并更新映射。
   • 记录结果：无论是 Φ 函数还是其他指令，如果 instr 定义了一个 result_var，则将其 ValueNumber 关联到 result_var，并记录 instr 是这个 ValueNumber 的定义点。

SSA GVN 的优势：

• 无需路径敏感的 current_var_vns：由于 SSA 变量的单赋值特性，每个变量的 ValueNumber 在其作用域内是唯一的，无需复杂的跨路径合并。
• Φ 函数明确合并点：Φ 函数使得 GVN 能够清晰地处理不同路径上值的合并，将其视为一种特殊类型的“操作”，从而将更复杂的全局数据流分析问题转化为更简单的局部值等价性问题。
• 更强大的冗余消除：SSA GVN 能够发现非 SSA GVN 难以发现的冗余，因为它能够精确地追踪值在控制流图中的传播。

3.5 实际代码示例 (概念性 C++-like 伪代码)

为了更好地理解 GVN 的实现，我们来看一个概念性的 C++ 伪代码示例。这个例子将专注于 GVN 在 SSA 形式上的核心逻辑。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm> // For std::sort

// --- 假设的中间表示 (IR) 结构 ---

// 表示一个变量，在SSA中每个定义都是一个新变量
struct IRVariable {
    std::string name;
    int id; // 唯一标识符
    IRVariable(std::string n, int i) : name(n), id(i) {}
    bool operator<(const IRVariable& other) const { return id < other.id; }
};

// 操作数可以是常量或变量
class IROperand {
public:
    enum Type { CONSTANT, VARIABLE };
    Type type;
    union {
        int const_val;
        IRVariable* var_ptr;
    };

    IROperand(int val) : type(CONSTANT), const_val(val) {}
    IROperand(IRVariable* var) : type(VARIABLE), var_ptr(var) {}

    bool is_constant() const { return type == CONSTANT; }
    bool is_variable() const { return type == VARIABLE; }
    int get_const_value() const { return const_val; }
    IRVariable* get_variable() const { return var_ptr; }
};

// IR 指令
class IRInstruction {
public:
    enum OpCode { ADD, MUL, SUB, DIV, LOAD, STORE, CALL, PHI, CONST_DEF, ARG_DEF };
    OpCode op;
    std::vector<IROperand> operands;
    IRVariable* result_var; // 如果是定义指令 (ADD, PHI, etc.)，这是它定义的变量

    // 构造函数简化
    IRInstruction(OpCode o, IRVariable* res_v, const std::vector<IROperand>& ops)
        : op(o), operands(ops), result_var(res_v) {}

    // 标记为冗余的指令，会指向原始定义指令的结果变量
    bool is_redundant = false;
    IRVariable* redundant_replace_with = nullptr;

    void mark_as_redundant(IRVariable* original_def_var) {
        is_redundant = true;
        redundant_replace_with = original_def_var;
    }
};

// 基本块
class BasicBlock {
public:
    std::vector<IRInstruction*> instructions;
    int id; // 块ID
    // ... 其他 CFG 相关的字段：前驱、后继、支配者等

    BasicBlock(int i) : id(i) {}
};

// 函数
class Function {
public:
    std::string name;
    std::vector<IRVariable*> arguments;
    std::vector<BasicBlock*> basic_blocks; // 假设已经排序为支配者树的后序遍历顺序

    Function(std::string n) : name(n) {}
};

// --- GVN 核心数据结构和辅助函数 ---

// 全局唯一的ValueNumber计数器
using ValueNumber = int;
static ValueNumber next_vn = 0;

// 规范化表达式的键
struct ExpressionKey {
    IRInstruction::OpCode op;
    std::vector<ValueNumber> operand_vns;
    int const_val_if_any = 0; // 用于常量指令或包含常量的表达式

    // 构造函数，需要根据指令和操作数VN来构建
    ExpressionKey(IRInstruction::OpCode o, const std::vector<ValueNumber>& ops_vns, int c_val = 0)
        : op(o), operand_vns(ops_vns), const_val_if_any(c_val) {
        // 对可交换操作符的操作数VN进行排序，实现规范化
        if (op == IRInstruction::ADD || op == IRInstruction::MUL || op == IRInstruction::PHI) {
            std::sort(this->operand_vns.begin(), this->operand_vns.end());
        }
    }

    // 用于std::map的比较操作符
    bool operator<(const ExpressionKey& other) const {
        if (op != other.op) return op < other.op;
        if (operand_vns != other.operand_vns) return operand_vns < other.operand_vns;
        return const_val_if_any < other.const_val_if_any;
    }
};

// 全局值编号映射表：存储 ExpressionKey -> ValueNumber
std::map<ExpressionKey, ValueNumber> global_value_map;

// 值编号到定义该值的IR指令的映射表
std::map<ValueNumber, IRInstruction*> vn_to_defining_instr;

// 追踪SSA变量的ValueNumber (在SSA中，变量的VN就是定义它的指令的VN)
std::map<IRVariable*, ValueNumber> var_to_vn;

// 获取操作数的ValueNumber
ValueNumber get_operand_vn(const IROperand& operand) {
    if (operand.is_constant()) {
        // 常量直接使用其值作为ExpressionKey的一部分，或者预先分配VN
        // 为了简化，我们这里直接返回一个基于常量值的'伪'VN，
        // 或者可以专门为每个常量分配一个独立的VN
        // 实际中，常量会被ValueNumbering，如 5 总是 VN_for_5
        // 这里我们让ExpressionKey处理常量值，所以返回一个占位符或特殊VN
        // 更严谨的做法是，所有常量在GVN开始前就分配好自己的VN
        return operand.get_const_value(); // 暂时用常量值作为其“VN”，但ExpressionKey会包含它
    } else { // 是变量
        IRVariable* var = operand.get_variable();
        auto it = var_to_vn.find(var);
        if (it != var_to_vn.end()) {
            return it->second;
        }
        // 如果找不到，可能是错误或未处理的初始值
        // 对于函数参数，它们会在GVN开始时被赋予初始VN
        std::cerr << "Error: ValueNumber not found for variable " << var->name << " (id: " << var->id << ")n";
        return -1; // 错误值
    }
}

// 执行 GVN 优化
void perform_gvn(Function* func) {
    std::cout << "--- Starting GVN for Function: " << func->name << " ---n";

    // 1. 初始化：为函数参数分配初始ValueNumber
    for (IRVariable* arg : func->arguments) {
        ValueNumber new_vn = next_vn++;
        var_to_vn[arg] = new_vn;
        // 参数没有定义指令，可以存nullptr或特殊标记
        vn_to_defining_instr[new_vn] = nullptr;
        std::cout << "Assigned VN " << new_vn << " to argument " << arg->name << "n";
    }

    // 2. 遍历基本块 (假设已按支配者树后序遍历排序，或适当的拓扑顺序)
    for (BasicBlock* bb : func->basic_blocks) {
        std::cout << "Processing Basic Block " << bb->id << "n";

        for (IRInstruction* instr : bb->instructions) {
            // 收集操作数的ValueNumber
            std::vector<ValueNumber> operand_vns;
            for (const auto& op : instr->operands) {
                operand_vns.push_back(get_operand_vn(op));
            }

            // 根据指令类型创建 ExpressionKey
            ExpressionKey expr_key = ExpressionKey(IRInstruction::CONST_DEF, {}, 0); // 默认值
            bool is_non_value_producing_instr = false;

            switch (instr->op) {
                case IRInstruction::ADD:
                case IRInstruction::SUB:
                case IRInstruction::MUL:
                case IRInstruction::DIV:
                    expr_key = ExpressionKey(instr->op, operand_vns);
                    break;
                case IRInstruction::PHI:
                    expr_key = ExpressionKey(instr->op, operand_vns);
                    break;
                case IRInstruction::CONST_DEF: { // 例如 `x = 5`
                    if (!instr->operands.empty() && instr->operands[0].is_constant()) {
                        expr_key = ExpressionKey(instr->op, {}, instr->operands[0].get_const_value());
                    } else {
                        std::cerr << "Error: CONST_DEF without a constant operand.n";
                        is_non_value_producing_instr = true;
                    }
                    break;
                }
                case IRInstruction::LOAD: {
                    // LOAD指令的GVN需要复杂的别名分析。
                    // 简单起见，这里假设每次LOAD都可能产生新值，
                    // 除非能证明内存地址和内容未变。
                    // 实际GVN会尝试给内存位置本身分配VN。
                    // 这里我们暂时让它产生新的VN，不进行CSE。
                    is_non_value_producing_instr = true; // 暂时不进行CSE，直接分配新VN
                    break;
                }
                case IRInstruction::STORE:
                case IRInstruction::CALL:
                case IRInstruction::ARG_DEF: // 参数定义已在函数开始时处理
                    is_non_value_producing_instr = true; // 这些指令不直接产生可共享的值
                    break;
            }

            if (is_non_value_producing_instr) {
                // 对于不产生值的指令 (如STORE, CALL) 或暂时不进行GVN的指令 (如LOAD)，
                // 如果它们定义了一个变量 (如LOAD)，仍需给该变量一个新VN。
                if (instr->result_var) {
                    ValueNumber new_vn = next_vn++;
                    var_to_vn[instr->result_var] = new_vn;
                    vn_to_defining_instr[new_vn] = instr;
                    std::cout << "  Instruction " << instr->op << " for " << instr->result_var->name
                              << " gets new VN " << new_vn << " (non-CSEable).n";
                }
                continue; // 跳过GVN核心逻辑
            }

            // 3. 检查 global_value_map
            auto it = global_value_map.find(expr_key);
            if (it != global_value_map.end()) {
                // 找到公共子表达式！
                ValueNumber existing_vn = it->second;
                IRInstruction* original_def_instr = vn_to_defining_instr[existing_vn];

                // 标记当前指令为冗余，并指向上一个计算出相同值的变量
                if (instr->result_var) {
                    instr->mark_as_redundant(original_def_instr->result_var);
                    var_to_vn[instr->result_var] = existing_vn; // 确保新变量也指向旧VN
                    std::cout << "  Instruction " << instr->op << " for " << instr->result_var->name
                              << " is REDUNDANT. Replaced with "
                              << original_def_instr->result_var->name << " (VN " << existing_vn << ").n";
                } else {
                    std::cout << "  Instruction " << instr->op << " (no result var) is REDUNDANT (VN "
                              << existing_vn << ").n";
                }
            } else {
                // 这是一个新的、独一无二的值
                ValueNumber new_vn = next_vn++;
                global_value_map[expr_key] = new_vn;
                vn_to_defining_instr[new_vn] = instr;

                if (instr->result_var) {
                    var_to_vn[instr->result_var] = new_vn;
                    std::cout << "  Instruction " << instr->op << " for " << instr->result_var->name
                              << " gets new VN " << new_vn << ".n";
                } else {
                    std::cout << "  Instruction " << instr->op << " (no result var) gets new VN "
                              << new_vn << ".n";
                }
            }
        }
    }
    std::cout << "--- GVN Completed ---n";
}

// 模拟IR创建和优化后的代码生成/打印
void print_optimized_ir(Function* func) {
    std::cout << "n--- Optimized IR for Function: " << func->name << " ---n";
    for (IRVariable* arg : func->arguments) {
        std::cout << "  ARG " << arg->name << "n";
    }

    for (BasicBlock* bb : func->basic_blocks) {
        std::cout << "Basic Block " << bb->id << ":n";
        for (IRInstruction* instr : bb->instructions) {
            std::cout << "  ";
            if (instr->result_var) {
                std::cout << instr->result_var->name << " = ";
            }

            if (instr->is_redundant) {
                std::cout << "MOV " << instr->redundant_replace_with->name << " ; (Original: ";
            }

            std::cout << instr->op;
            for (const auto& op : instr->operands) {
                if (op.is_constant()) {
                    std::cout << " #" << op.get_const_value();
                } else {
                    std::cout << " " << op.get_variable()->name;
                }
            }
            if (instr->is_redundant) {
                std::cout << ")";
            }
            std::cout << "n";
        }
    }
}

int main() {
    // 模拟IR变量
    IRVariable a("a", 1), b("b", 2), c("c", 3);
    IRVariable x1("x1", 4), y1("y1", 5), z1("z1", 6);
    IRVariable x2("x2", 7), y2("y2", 8);
    IRVariable x3("x3", 9), y3("y3", 10);
    IRVariable res("res", 11);

    // 创建一个函数
    Function func("example_gvn_ssa");
    func.arguments = {&a, &b, &c};

    // 创建基本块
    BasicBlock bb0(0), bb1(1), bb2(2), bb3(3); // bb0 -> bb1, bb2 -> bb3 (merge)
    func.basic_blocks = {&bb0, &bb1, &bb2, &bb3}; // 假设已排序

    // BB0: 入口块
    // x1 = a + b
    bb0.instructions.push_back(new IRInstruction(IRInstruction::ADD, &x1, {IROperand(&a), IROperand(&b)}));
    // y1 = b * 2
    bb0.instructions.push_back(new IRInstruction(IRInstruction::MUL, &y1, {IROperand(&b), IROperand(2)}));
    // ... if (c > 0) goto bb1 else goto bb2 ... (控制流指令省略)

    // BB1: if 分支
    // x2 = x1 + 5
    bb1.instructions.push_back(new IRInstruction(IRInstruction::ADD, &x2, {IROperand(&x1), IROperand(5)}));
    // y2 = b * 2 // 冗余，与 y1 相同
    bb1.instructions.push_back(new IRInstruction(IRInstruction::MUL, &y2, {IROperand(&b), IROperand(2)}));
    // ... goto bb3 ... (控制流指令省略)

    // BB2: else 分支
    // x3 = a + b // 冗余，与 x1 相同
    bb2.instructions.push_back(new IRInstruction(IRInstruction::ADD, &x3, {IROperand(&a), IROperand(&b)}));
    // y3 = b * 2 // 冗余，与 y1 相同
    bb2.instructions.push_back(new IRInstruction(IRInstruction::MUL, &y3, {IROperand(&b), IROperand(2)}));
    // ... goto bb3 ... (控制流指令省略)

    // BB3: 合并块 (假设 z1 是一个 phi 结果)
    // res = phi(x2, x3)
    bb3.instructions.push_back(new IRInstruction(IRInstruction::PHI, &res, {IROperand(&x2), IROperand(&x3)}));

    // 执行 GVN
    perform_gvn(&func);

    // 打印优化后的IR
    print_optimized_ir(&func);

    // 清理内存 (在实际编译器中由IR管理)
    for (auto bb : func.basic_blocks) {
        for (auto instr : bb->instructions) {
            delete instr;
        }
        delete bb;
    }
    // delete &a, &b, ... (变量的生命周期管理)

    return 0;
}

运行上述伪代码的预期输出片段解释：

1. x1 = a + b 会得到一个新的 ValueNumber (例如 VN0)。
2. y1 = b * 2 会得到一个新的 ValueNumber (例如 VN1)。
3. x2 = x1 + 5 会得到一个新的 ValueNumber (例如 VN2)。
4. y2 = b * 2 (在 BB1 中) 会被识别为与 y1 = b * 2 (在 BB0 中) 具有相同的 ExpressionKey。因此，y2 会被标记为冗余，并被重定向到 y1 的值。
5. x3 = a + b (在 BB2 中) 会被识别为与 x1 = a + b (在 BB0 中) 具有相同的 ExpressionKey。因此，x3 会被标记为冗余，并被重定向到 x1 的值。
6. y3 = b * 2 (在 BB2 中) 同样会被识别为与 y1 = b * 2 具有相同的 ExpressionKey。因此，y3 会被标记为冗余，并被重定向到 y1 的值。
7. res = phi(x2, x3)：phi 函数也会被值编号。它的 ExpressionKey 将由 x2 的 ValueNumber 和 x3 的 ValueNumber 构成。由于 x3 被重定向到 x1，所以 phi 函数实际上会变成 phi(x2, x1)。如果之后有另一个 phi 函数 res2 = phi(x1, x2)，它也会被识别为冗余。

通过这种方式，GVN 能够有效地发现并标记这些冗余计算，后续的优化阶段（如死代码消除或指令调度）就可以将它们移除或替换为简单的移动指令。

---

四、 GVN 能够识别的冗余类型

GVN 的核心能力在于其基于值等价性的判断，而非简单的语法匹配。这使得它能够识别多种形式的冗余：

| 冗余类型 | 描述 引言：编译器的任务与挑战

GVN，即 Global Value Numbering（全局值编号），是现代优化编译器中一个基础而强大的优化技术。在探讨GVN之前，我们首先要理解为什么需要这样的优化。

编译器的核心任务是将高级语言代码转换为高效的机器代码。这个过程不仅仅是简单的翻译，更是一个复杂的优化过程。优化的目标是使生成的机器代码更快、更小，或两者兼顾。冗余计算是性能的巨大浪费，它指的是程序中多次计算出相同值的表达式，而其中只有第一次计算是真正必要的。

考虑一个简单的例子：

int foo(int a, int b) {
    int x = a + b;
    // ... 大量不改变 a 或 b 的代码 ...
    int y = a + b; // 冗余计算
    return x * y;
}

在这里，a + b 被计算了两次。一个理想的编译器应该能够识别出第二次计算是冗余的，并将其替换为对第一次计算结果的引用。这种优化被称为公共子表达式消除 (Common Subexpression Elimination, CSE)。

早期的 CSE 优化通常是“局部”的，即只在基本块 (Basic Block) 内部进行。一个基本块是一段连续的指令序列，其中只有一个入口点和一个出口点。例如，在上述 foo 函数中，如果 int y = a + b; 和 int x = a + b; 处于同一个基本块内，并且中间没有指令修改 a 或 b，那么局部 CSE 可以轻松地消除 y 的计算。

然而，程序的控制流远比这复杂。代码中可能存在分支、循环，导致同一个表达式在不同的基本块中、不同的执行路径上重复出现。例如：

int bar(int p, int q, int r) {
    int temp1 = p * q;
    if (r > 0) {
        int res1 = temp1 + 10;
        return res1 + (p * q); // 冗余
    } else {
        int res2 = temp1 - 5;
        return res2 + (q * p); // 冗余，且操作数顺序不同
    }
}

在这个 bar 函数中，p * q 在 if 和 else 分支中都重复出现，甚至在 else 分支中以 q * p 的形式出现。局部 CSE 无法处理这种跨基本块的冗余。此外，q * p 与 p * q 在语法上不同，但对于整数乘法而言，它们计算的是同一个值。如何识别这种“语义上等价但语法上不同”的冗余，是更高级优化面临的挑战。

这就是 GVN 登场的舞台。GVN 是一种全局性的优化技术，它能够超越基本块的边界，识别并消除程序中逻辑上等价的冗余表达式，无论它们在代码中以何种形式出现。

---

二、 GVN 的核心思想：为值编号

GVN 的核心理念是为程序中每一个独一无二的计算结果分配一个唯一的“值编号” (Value Number)。这个值编号代表了某个特定的计算结果，而不是表达式的文本形式。如果两个表达式，无论它们在代码中是如何书写的，最终计算出的是同一个逻辑值，那么它们就应该拥有相同的“值编号”。

想象一下，我们有一个中央登记处，每当程序计算出一个新的值时，我们就给这个值一个唯一的 ID。如果稍后我们发现另一个表达式计算出了与某个已有 ID 对应的值完全相同的结果，那么我们就知道这个新的计算是冗余的，可以直接使用那个已有 ID 对应的值。

GVN 的关键特征：

1. 值等价性而非语法等价性：GVN 关注的是表达式计算出的“值”是否相同，而不是表达式的“文本”是否相同。这使得它能够处理：
   • 操作数顺序不同但等价：如 a + b 和 b + a (对于可交换操作，如加法、乘法)。
   • 不同变量名但指向相同值：如 x = a + b 和 y = a + b。
   • 不同操作但等价：如 x * 2 和 x << 1 (对于整数)。
   • 常量折叠：1 + 2 会被视为与 3 具有相同的值编号。
2. 全局性：GVN 能够分析整个函数或整个程序，识别跨基本块、跨控制流路径的冗余。
3. 精确性：通过仔细追踪数据流和控制流，GVN 能够精确地判断在特定程序点上，两个值是否确实是等价的。

一个简单的 GVN 流程概览：

1. 遍历程序的中间表示 (IR) 指令。
2. 对于每个指令，收集其操作数的值编号。
3. 根据操作符和操作数的值编号，创建一个规范化的表达式键 (Expression Key)。
4. 查询一个全局映射表：如果这个表达式键已经存在，说明这个值已经计算过了，当前指令是冗余的。
5. 如果表达式键不存在，说明这是一个新的值，分配一个新的值编号，并将其与表达式键和当前指令关联起来。

---

三、 GVN 算法的实现细节

GVN 算法的实现通常依赖于编译器的中间表示 (IR) 和控制流图 (CFG)。我们将详细探讨其所需的数据结构、处理流程，特别是在静态单赋值 (SSA) 形式下的优势。

3.1 预备知识：中间表示 (IR) 与控制流图 (CFG)

GVN 算法在编译器的中间表示 (IR) 上执行。IR 是一种抽象的程序表示，它去除了源代码语言的语法细节，专注于程序的语义。常见的 IR 形式包括：

• 三地址码 (Three-Address Code, TAC)：每条指令最多包含一个操作符和三个操作数，例如 t1 = a + b。
• 静态单赋值形式 (Static Single Assignment Form, SSA)：这是 GVN 最常使用的 IR 形式。在 SSA 形式中，每个变量在程序中只被赋值一次。如果一个变量在不同的控制流路径上可能被赋予不同的值，那么在这些路径汇合的地方（例如 if-else 语句的末尾），会引入特殊的 Φ (Phi) 函数来合并这些值。例如，x3 = Φ(x1, x2) 意味着如果从左侧路径到达，x3 的值是 x1；如果从右侧路径到达，x3 的值是 x2。SSA 极大地简化了数据流分析，从而也简化了 GVN。

控制流图 (CFG) 是 GVN 进行全局分析的骨架。CFG 由基本块 (Basic Blocks) 构成，每个基本块是一段连续的指令序列，只有一个入口和一个出口。基本块之间通过边 (Edges) 连接，表示可能的控制流转移。CFG 允许编译器理解程序的执行路径，从而进行跨基本块的分析。

3.2 核心数据结构

为了有效地实现 GVN，我们需要维护以下几个关键数据结构：

1. ValueNumber 类型：一个简单的整数，作为值的唯一标识符。通常从 0 或 1 开始递增。

   using ValueNumber = int;
   static ValueNumber next_vn = 0; // 全局计数器，用于分配新的值编号

2. ExpressionKey (表达式键)：这是 GVN 算法的核心。它是一个结构体，用于规范化地描述一个表达式，使其可以作为映射表的键。它的设计目标是：如果两个表达式计算的是相同的值，它们就应该生成相同的 ExpressionKey。
   ExpressionKey 通常包含：

   • 操作符 (OpCode)：例如 ADD, MUL, LOAD, PHI 等。
   • 操作数的 ValueNumber 列表：这是关键，我们比较的是操作数的值，而不是它们的变量名。
   • 常量值：如果表达式本身是一个常量（如 5），或包含常量操作数（如 a + 5），常量值也应作为键的一部分。
   • 其他上下文信息：例如，对于内存操作 LOAD(ptr)，可能需要 ptr 的 ValueNumber 以及某种内存状态的 ValueNumber。对于函数调用 CALL(func_id, args)，需要函数 ID 和参数的 ValueNumber。

   规范化 (Canonicalization) 的例子：

   • 可交换操作：对于 ADD 或 MUL，a + b 和 b + a 应该生成相同的键。这可以通过对操作数的 ValueNumber 列表进行排序来实现。例如，ADD(VN_a, VN_b) 和 ADD(VN_b, VN_a) 在排序后都变成 ADD(min(VN_a, VN_b), max(VN_a, VN_b))。
   • 常量折叠：ADD(VN_1, VN_2) 应该与 CONST(VN_3) 生成等价的键。这通常通过在 GVN 之前执行常量折叠或在 ExpressionKey 构造时进行简化来实现。

   // 假设 IRInstruction 定义了 OpCode 枚举
   struct ExpressionKey {
       IRInstruction::OpCode op;
       std::vector<ValueNumber> operand_vns;
       long long const_val_if_any = 0; // 用于常量指令或包含常量的表达式
   
       // 构造函数，需要根据指令和操作数VN来构建
       ExpressionKey(IRInstruction::OpCode o, const std::vector<ValueNumber>& ops_vns, long long c_val = 0)
           : op(o), operand_vns(ops_vns), const_val_if_any(c_val) {
           // 对可交换操作符的操作数VN进行排序，实现规范化
           if (op == IRInstruction::ADD || op == IRInstruction::MUL || op == IRInstruction::PHI) {
               std::sort(this->operand_vns.begin(), this->operand_vns.end());
           }
           // 更多规范化规则可以添加在这里，例如：
           // if (op == IRInstruction::SUB && operand_vns[0] == operand_vns[1]) {
           //     this->op = IRInstruction::CONST_DEF; // x - x = 0
           //     this->operand_vns.clear();
           //     this->const_val_if_any = 0;
           // }
       }
   
       // 用于std::map的比较操作符，实现严格弱序
       bool operator<(const ExpressionKey& other) const {
           if (op != other.op) return op < other.op;
           if (operand_vns != other.operand_vns) return operand_vns < other.operand_vns;
           return const_val_if_any < other.const_val_if_any;
       }
   };

3. global_value_map (全局值映射表)：这是一个核心映射，存储了所有已计算的、具有唯一值编号的表达式的 ExpressionKey 到 ValueNumber 的映射。

   std::map<ExpressionKey, ValueNumber> global_value_map;

4. vn_to_defining_instr (值编号到定义指令的映射表)：这个映射