基本块和有向无环图
在编译器设计中，我们关注几个关键阶段，包括词法分析、语法分析和中间代码生成。另一个关键阶段是优化，它通过提高执行速度和减少内存使用来帮助生成高效的机器代码。
一种重要的优化技术涉及 Basic Blocks 和 Directed Acyclic Graphs (DAGs)。基本块将代码分解为独立的单元，而 DAGs 有助于检测公共子表达式并消除冗余计算，从而减少指令数量。
在本章中，我们将探讨基本块，了解 DAGs 如何优化代码，并通过示例以获得更好的清晰度。
什么是 Basic Blocks？
basic block 是一系列指令或操作的序列，具有单一入口点和单一出口点。这意味着执行从开头进入并在结尾离开，中间没有任何跳转或分支。
Basic Blocks 的特性
要正确理解基本块，我们必须了解其特性。下面列出了基本块的重要特性 −
- 内部无跳转或分支语句 − 基本块内部不包含标签 (LBL)、跳转 (JMP) 或测试 (TST) 语句。
- 单一入口，单一出口 − 执行从第一条指令开始，并顺序继续直到最后一条指令。
- 自包含 − 基本块不与其他代码段干扰。这使得它们更容易分析和优化。
示例：识别 Basic Blocks
考虑以下从 Java 表达式生成的原子序列（三地址代码） −
(ADD, b, c, T1) (LBL, L1) (ADD, b, c, T2) (MUL, T1, T2, T3) (TST, b, c,, 1, L3) (MOV, T3,, a)
我们可以将其分为 三个基本块 −
| Basic Block | Instructions |
|---|---|
| Block 1 | (ADD, b, c, T1) |
| Block 2 | (LBL, L1) (ADD, b, c, T2) (MUL, T1, T2, T3) |
| Block 3 | (TST, b, c, 1, L3) (MOV, T3, , a) |
每个块都是独立的，并且在其内部不包含任何控制流变化。
使用 DAGs 优化 Basic Blocks
Directed Acyclic Graph (DAG) 是一种基于图的结构，有助于消除基本块中的冗余计算并检测公共子表达式。在进一步讨论之前，让我们正确理解这一点。
为什么使用 DAGs？
我们使用 DAGs 的原因如下 −
- 减少冗余计算 − 如果像 b + c 这样的操作出现多次，DAG 有助于仅计算一次。
- 优化指令数量 − DAG 简化原子序列。生成更短、更高效的版本。
- 最小化临时存储 − 移除冗余临时变量。这减少了寄存器或内存使用。
示例：表达式优化的 DAG
考虑以下 Java 语句 −
a = (b + c) * (b + c);
解析器生成的未优化原子序列 −
(ADD, b, c, T1) (ADD, b, c, T2) (MUL, T1, T2, T3) (MOV, T3,, a)
该序列重新计算了两次 b + c，这浪费了时间和资源。
使用 DAG 表示，我们认识到两次 b + c 是相同的。因此，我们仅存储一次并重复使用 −
(ADD, b, c, T1) (MUL, T1, T1, a)
现在，我们只有一次 ADD 操作，而不是两次。这里 MUL 操作直接将结果存储在 a 中。
如何为优化构造 DAG
我们了解了 DAG 的作用，但我们需要理解如何构建 DAG。为了从原子序列构建 DAG，我们遵循以下步骤：
- 步骤 1: 读取一个 Atom（指令） − 如果操作和操作数已经在 DAG 中存在，则重用该节点。否则，创建一个新节点。
- 步骤 2: 连接节点 − 从操作节点到操作数节点绘制有向弧。然后跟踪每个节点关联的变量。
- 步骤 3: 生成优化的代码 − 现在按逆序遍历 DAG。这将有助于生成最小的原子序列。
示例：为优化构建 DAG
考虑以下 Java 表达式 −
a * b + a * b + a * b
解析器生成以下 atoms −
(MUL, a, b, T1) (MUL, a, b, T2) (ADD, T1, T2, T3) (MUL, a, b, T4) (ADD, T3, T4, T5)
使用 DAG 构造过程
为 MUL、a、b 创建单个节点（而不是三个）。
在两个 ADD 操作中重用它，而不是重新计算。
优化的原子序列（从 DAG 生成）
(MUL, a, b, T1) (ADD, T1, T1, T3) (ADD, T3, T1, T5)
在这里，我们消除了冗余的乘法运算，并将五个指令减少到仅三个。
基本块和 DAG 优化：优点和缺点
下表突出了基本块和 DAG 优化的优点和缺点 −
| 优点 | 缺点 |
|---|---|
| 更快的执行 − 更少的指令意味着更少的 CPU 时间，从而加速程序执行。 | 仅限于基本块 − DAG 仅在单个基本块内工作，无法优化跨越不同块的代码，因为可能存在跳转和分支语句。 |
| 减少内存使用 − 更少的临时变量减少了寄存器和内存存储需求。 | 无法处理带有标签或跳转的代码 − 当存在标签（LBL）或跳转（JMP）指令时，无法进行基于 DAG 的优化，因为控制流会改变执行顺序。 |
| 更好的代码优化 − 基于 DAG 的优化帮助编译器生成紧凑、高效的代码。 | DAG 构造的开销 − 构建和维护 DAG 会增加编译器的复杂性，大型表达式可能需要更多内存来存储 DAG。 |
结论
在本章中，我们解释了编译器设计中的基本块和 DAG 概念，以及它们如何帮助代码优化。我们看到了基本块如何将代码分割成独立的执行单元，以及 DAG 如何通过检测公共子表达式来消除冗余计算。
使用基于 DAG 的优化，我们可以减少编译程序中的指令数量、内存使用和执行时间。基本块优化很强大，但它仅限于没有跳转或标签的代码段。