对于优化，主要分为两个阶段的优化：中端和后端。中端对中间代码先进行优化，随后由后端生成目标代码，再由后端优化代码进行进一步的优化。

核心的优化工作主要集中在以下三个方面：

  1. mem2reg：将内存变量提升为 SSA 寄存器形式，减少 load/store 指令。
  2. removePhi：将 Phi 指令转化为 Move 指令，以便后端 MIPS 翻译。
  3. regAlloc：使用图着色算法进行寄存器分配。

此外，为了支撑这些核心优化，还实现了一些基础的 Pass，如死代码删除、CFG 构建、支配关系分析等。

中端优化

中端优化即机器无关优化，主要针对 LLVM IR 进行处理。

死代码删除

死代码删除分为两层：删除不可达基本块和删除无用指令。

删不可达基本块

SurplusBlock 的实现基于图的可达性分析：从入口块出发进行 DFS，标记所有可达的块，最后将未被标记的块从函数中移除。同时，还需要清理跳转指令之后的无用指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 从入口块开始DFS
visited = new HashSet<>();
dfs(func.getEntryBlock());

// 移除未访问到的块
func.getBasicBlocks().removeIf(block -> {
    if (!visited.contains(block)) {
        block.getInstructions().forEach(Instruction::removeOperands);
        block.removeOperands();
        block.setDeleted(true);
        return true;
    }
    return false;
});

删无用指令

CodeRemoval 进行了两层过滤：

  1. 直接删除无 User 且无副作用的指令。
  2. 从有 User 指令出发计算依赖闭包，删除依赖链之外的指令。
1
2
3
4
5
6
7
8
9
10
11
12
// 判断无user且无副作用
if (instruction.getUserList().isEmpty() && !instruction.getName().isEmpty()) {
    if (!(instruction instanceof CallInst)) {
        instruction.removeOperands();
        return true;
    } else if (instruction instanceof CallInst callInst) {
        if (!callInst.getCalledFunction().hasSideEffects()) {
            instruction.removeOperands();
            return true;
        }
    }
}

控制流与支配分析

这一部分主要为了支撑 mem2reg 的实现。不同于复用对象，我选择在处理每个函数时直接计算这些关系并挂载到 BasicBlock 上。

CFG构建

CFG 的构建非常直接：检查每个基本块的最后一条 BrInst，根据跳转目标建立边。

1
2
3
4
5
6
7
8
if (lastInstruction instanceof BrInst brInst) {
    if (brInst.isConditional()) {
        addEdge(block, brInst.getTrueBlock());
        addEdge(block, brInst.getFalseBlock());
    } else {
        addEdge(block, brInst.getTrueBlock());
    }
}

支配集合与支配树

支配集合的计算采用了“暴力”但稳健的方法：对于每个候选支配者 d，从入口做 DFS，若遇到 d 则停止。最后 DFS 无法到达的块即被 d 支配。

直接支配者的选择则是从所有支配者中挑选最近的一个。

1
2
3
4
5
6
7
8
9
10
for (BasicBlock dominator : currentFunction.getBasicBlocks()) {
    Set<BasicBlock> reachableBlocks = new HashSet<>();
    dfs(entry, dominator, reachableBlocks);
    for (BasicBlock block : currentFunction.getBasicBlocks()) {
        if (!reachableBlocks.contains(block)) {
            dominates.get(dominator).add(block);
            dominatedBy.get(block).add(dominator);
        }
    }
}

支配边界

支配边界的计算逻辑为：对于每个支配者，扫描其支配的块及其后继，若后继不被该支配者支配，则该后继为支配边界。

1
2
3
4
5
6
7
for (BasicBlock dominated : dominator.getDominateBlocks()) {
    for (BasicBlock child : dominated.getNextBlocks()) {
        if (!dominator.getDominateBlocks().contains(child)) {
            frontier.add(child);
        }
    }
}

mem2reg

mem2reg 的目标是将局部变量提升为 SSA 形式，消除 alloca，并尽量用 SSA 值替换 load，将 store 转化为定义的压栈操作。

收集 def/use

首先遍历 alloca 的 userList，将 load 记为 use，store 记为 def。

1
2
3
4
5
6
7
if (instruction instanceof LoadInst && !instruction.getBasicBlock().isDeleted()) {
    useInstructions.add(instruction);
}
if (instruction instanceof StoreInst && !instruction.getBasicBlock().isDeleted()) {
    defInstructions.add(instruction);
    defBlocks.add(instruction.getBasicBlock());
}

插入 phi 指令

使用经典算法：从 defBlocks 开始，沿支配边界扩散，在遇到新块时插入 PhiInst。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
HashSet<BasicBlock> F = new HashSet<>();
ArrayList<BasicBlock> W = new ArrayList<>(defBlocks);
while (!W.isEmpty()) {
    BasicBlock X = W.remove(0);
    for (BasicBlock Y : X.getDominanceFrontier()) {
        if (!F.contains(Y)) {
            PhiInst phiInst = new PhiInst(currentAlloc.getTargetType(),
                                          Y, new ArrayList<>(Y.getPrevBlocks()));
            Y.getInstructions().add(0, phiInst);
            F.add(Y);
            if (!defBlocks.contains(Y)) {
                W.add(Y);
            }
        }
    }
}

变量重命名

重命名阶段维护一个 defStack，通过一次 DFS 完成：

  1. Store：将值压栈，删除指令。
  2. Load：用栈顶值替换，删除指令。
  3. Phi：将 Phi 自身压栈，作为新定义。
  4. Alloca：删除。

在从当前块走向后继时，为后继的 Phi 填充来自当前块的 incoming value。

1
2
3
4
5
6
if (instruction instanceof PhiInst phiInst) {
    if (useInstructions.contains(phiInst)) {
        Value value = defStack.empty() ? new Undefined() : defStack.peek();
        phiInst.addValue(block, value);
    }
}

后端优化

后端优化主要包括 removePhi 和寄存器分配。

removePhi

由于 MIPS 没有 Phi 指令，需要在生成代码前将 Phi 拆分为 MoveInst。

拆分流程

  1. 清理与生成 Move：对每个前驱，生成 MoveInst(to=phi, from=alt)。
  2. 解决并行赋值：若 to 在后续被用作 from，引入临时变量中转。
  3. 解决寄存器覆盖：若 to 和 from 分配到了同一寄存器，同样使用临时变量。
  4. 插入 Move：
    • 若前驱只有一个后继，直接插入。
    • 若前驱有多个后继，新建中间块插入 move 和跳转。

关键点在于处理多后继前驱时建立中间块，以保证语义正确。

寄存器分配

寄存器分配采用了图着色算法，流程为：活跃变量分析 -> 建干涉图 -> 图着色。

活跃变量分析

计算每个基本块的 use 和 def，并迭代计算 IN 和 OUT 集合。特别注意 Phi 指令的 operand 应视为在前驱边上被使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (changed) {
    changed = false;
    for (int i = blocks.size() - 1; i >= 0; i--) {
        // ... 计算OUT集合，包含Phi的修正 ...
        HashSet<Value> inSet = new HashSet<>(outSet);
        
        inSet.removeAll(defMap.get(block));
        inSet.addAll(useMap.get(block));

        if (!inSet.equals(inMap.get(block))) {
            changed = true;
            inMap.put(block, inSet);
        }
    }
}

建干涉图

从后往前扫描指令，维护 live set。每遇到一个定义，就使其与当前 live set 中的所有变量建立干涉边。

1
2
3
4
5
6
7
8
9
10
11
12
13
HashSet<Value> live = new HashSet<>(outMap.get(block));
ListIterator<Instruction> iterator = instructions.listIterator(instructions.size());
while (iterator.hasPrevious()) {
    Instruction instruction = iterator.previous();
    if (!instruction.getName().isEmpty() && !(instruction instanceof ZextInst)) {
        live.remove(instruction);
        InterferenceGraphNode nodeU = getOrCreateNode(instruction);
        for (Value v : live) {
            addEdge(nodeU, getOrCreateNode(v));
        }
    }
    // ... 添加操作数到live set ...
}

图着色

采用 simplify/spill/select 步骤：

  1. Simplify：反复移除度数 < K 的节点压栈。
  2. Spill：若无度数 < K 的节点，选择度数最大的节点作为溢出候选压栈。
  3. Select：出栈分配颜色，若无色可选则标记溢出。

最终将分配结果记录在 function.setVar2reg 中，供后端代码生成使用。

优化总结

整体的优化流水线如下：

  1. 中端：先进行死代码删除和 CFG 清理，再执行 mem2reg，最后进行局部优化。
  2. 后端：在生成 MIPS 前，依次执行 ZextRemoval -> RegAlloc -> RemovePhi。
  3. 窥孔：生成 MIPS 代码后，再进行一轮窥孔优化。

这一顺序确保了 IR 在结构稳定后进行重优化，最后在目标代码层面进行局部调整。

学习编译的过程中，经常会听到一句话，“相信编译器的力量”。

相比于目前的成熟编译器，我的编译器还处于非常简陋的阶段，不过我已经很满意了。