我的大学

外观

图IR

约 3339 字大约 11 分钟

2025-01-14

图形化的中间表示（Graphical IRs）

许多编译器使用将底层代码表示为图的IR。虽然所有的图形化IR都由节点和边组成，但它们在抽象层次、图与底层代码之间的关系以及图的结构上有所不同。

解析树、抽象语法树（ASTs）和有向无环图（DAGs）都是用来表示代码的图。这些树状的中间表示（IRs）具有与源代码语法相对应的结构。

解析树

解析树是输入程序推导过程或解析过程的图形化表示。下图展示了经典的表达式语法规则以及表达式 a *x + 2 *x*b 的解析树。解析树相对于源文本来说较大，因为它表示了完整的推导过程，推导中的每个语法符号都有一个对应的节点。由于编译器必须为每个节点和每条边分配内存，并且在编译期间必须遍历所有这些节点和边，因此考虑缩小这棵解析树的方法是有价值的。

picture4.2

解析树主要用在关于解析的讨论中，以及属性文法系统中，在这些地方它们是权威的中间表示（IR）。在大多数其他需要源代码级别树结构的应用中，编译器编写者倾向于使用更加简洁的替代方案，比如抽象语法树（AST）或有向无环图（DAG）。

抽象语法树（Abstract Syntax Tree, AST）

抽象语法树（AST）保留了解析树的结构和含义，但消除了冗余的节点。它去掉了表示推导细节的非终结符号节点。一个表达式 a x 2 + a x 2 x b 的AST展示在下面。

picture4.2

有向无环图（Directed Acyclic Graph）

虽然抽象语法树（AST）比解析树更为简洁，但它忠实地保留了源代码的结构。例如，表达式 a *x^2 + ax^2b 的AST中包含两个不同的 a * x^2 表达式的副本。有向无环图（DAG）是AST的一种压缩形式，它避免了这种重复。在DAG中，节点可以有多个父节点，并且相同的子树会被复用。这样的共享机制使得DAG比相应的AST更加紧凑。

对于没有赋值或函数调用的表达式，文本上相同的表达式必须产生相同的值。a *x^2 + a* x^2 *b 的DAG，如边栏所示，通过共享单一的 a*x^2 实例反映了这一事实。如果a的值在这两个使用位置之间不会发生变化，那么编译器应该生成代码来只计算一次 a* x^2 并两次使用该结果。这种策略可以降低求值成本。DAG明确地编码了子表达式之间的冗余性。如果编译器在中间表示（IR）中表示此类事实，它可以避免重新发现它们的成本。 picture4.2 在为这个表达式构建 DAG 时，编译器必须证明 'a' 的值在其被使用之间不能发生变化。如果表达式既不包含赋值也不包含对其他程序的调用，那么这个证明就很容易完成。由于赋值或程序调用可以改变与名称关联的值，DAG 构建算法必须在操作数的值可能发生改变时使子树失效。

如果内存限制制约了编译器能够处理的程序大小，那么使用 DAG 作为权威的中间表示（IR）可以减少 IR 的内存占用。其他系统使用 DAG 来揭示冗余。在这种情况下，好处在于生成更优质的编译代码。这些后者系统倾向于将 DAG 用作派生的中间表示——构建 DAG，转换权威的 IR 以反映冗余，并丢弃 DAG。这里的“揭示冗余”指的是通过分析程序的DAG表示来识别出程序中的重复计算或不必要的操作。

控制流图

控制流图（Control Flow Graph，CFG）是表示程序控制流结构的图形化中间表示。从数学上看，一个控制流图可以表示为一个有向图 G = (N,E)，其中：

  • N 是节点集合，每个节点 n ∈ N 对应一个基本块
  • E 是边集合，每条边 e = (ni,nj) ∈ E 表示从基本块 ni 到 nj 的可能控制流转移

控制流图由基本块（Basic Block）和边组成，其中：

  1. 基本块是连续执行的指令序列，只有一个入口点和一个出口点
  2. 边表示控制流的转移，通常对应条件跳转、无条件跳转或函数调用

控制流图的主要特点包括：

  • 每个节点代表一个基本块
  • 边表示可能的控制流转移
  • 有向边表示执行顺序
  • 通常包含一个入口节点和一个出口节点

控制流图在编译器中有多种重要用途：

  1. 数据流分析：用于变量定义和使用分析
  2. 优化：识别死代码、循环优化等
  3. 调试：可视化程序执行路径
  4. 测试：生成测试用例覆盖不同路径

构建控制流图的基本步骤：

  1. 将代码划分为基本块
  2. 确定基本块之间的控制流关系
  3. 添加边表示控制流转移
  4. 优化和简化控制流图

控制流图与其他图形化IR的关系：

  • 比AST更关注控制流而非语法结构
  • 比DAG更适合表示程序流程而非表达式计算
  • 常用于优化阶段，与数据流图配合使用

示例控制流图：

      [Entry]
        |
        v
      [Block 1]-----
        |          |
        v          |
      [Block 2]    |
        |          |
        v          |
      [Block 3]-----
        |
        v
      [Exit]

对于 if-then-else 结构，CFG 和 AST 都将是无环的，如下所示。 picture4.2

CFG 建模的是控制流；stmt1 或 stmt2 之一被执行， 但不会同时执行两者。AST 再次捕捉语法，但对代码实际执行方式提供的直接直觉很少。任何这样的联系都是隐含的，而不是显式的。

编译器通常将 CFG 与另一种中间表示（IR）结合使用，使 CFG 成为衍生的 IR。CFG 表示各块之间的关系，而块内的操作则用另一种 IR 表示， 比如表达式级别的 AST、DAG 或线性 IR 之一。

编译器的许多部分都依赖于 CFG，无论是显式还是隐式地。

编译器通常将控制流图（CFG）与另一种中间表示（IR）结合使用，使CFG成为衍生的IR。CFG表示各代码块之间的关系，而块内的操作则用另一种IR表示，比如表达式级别的抽象语法树（AST）、有向无环图（DAG）或线性的IR之一。编译器可以将这种混合IR作为其权威的IR，但保持多种形式的一致性的复杂性使得这种做法并不常见。

基本块的长度

一些专家建议构建围绕比基本块更短的块的 CFG。最常见的替代块是单语句块。单语句块可以简化分析和优化的算法。

使用单语句块构建的 CFG 与使用最大长度块构建的 CFG 之间的权衡涉及到空间和时间。基于单语句块构建的 CFG 比基于最大长度块构建的 CFG 拥有更多的节点和边。因此，在其他因素相同的情况下，单语句 CFG 将比最大长度 CFG 使用更多的内存。随着节点和边数量的增加，遍历和处理 CFG 的时间成本也会相应提高。然而，单语句块可以使得某些类型的分析和优化更加直观和容易实现，因为每个节点只包含一个操作，这可能会减少复杂性并使某些算法更容易编写和理解。

随着节点和边的增多，遍历过程会变得更长。更重要的是，当编译器对控制流图（CFG）进行注解时，单语句CFG相较于基本块CFG会有更多的注解。构建和使用这些注解所花费的时间和空间毫无疑问远远超过了构建CFG的成本。 另一方面，一些优化可以从单语句块中受益。例如，懒代码移动（参见第10章内容）仅在块边界插入代码。因此，单语句块允许懒代码移动以比最大长度块更细的粒度优化代码放置。

数据依赖图

数据依赖图体现了这种关系。在数据依赖图中，节点代表操作。大多数操作既包含定义又包含使用。数据依赖图中的一条边连接两个节点，一个节点是定义，另一个节点是使用。我们绘制依赖图时，边是从定义指向使用；有些作者则将这些边从使用指向定义。

下图展示了用于计算a←ax2xbxcxd的ILOC代码。图(a)包含了ILOC代码。图(b)显示了相应数据依赖图。

picture4.2

依赖图中每个操作都有一个节点。每条边显示单个值的流动。例如，从3到7的边反映了语句3中rb的定义及其在语句7中的后续使用。虚拟寄存器 rarpr_{arp} 包含一个与局部数据区起始位置固定距离的地址。rarpr_{arp} 的使用引用了其在过程开始时的隐式定义；它们用虚线表示。

数据依赖图通常为特定任务构建，然后被丢弃，因此它们是一种衍生的中间表示（IR）。它们在指令调度中扮演着核心角色（第12章）。数据依赖图在各种优化中找到应用，特别是那些重新排序循环以暴露并行性和改善内存行为的转换。在更复杂的数据依赖图应用中，编译器可能会对数组下标值进行广泛分析，以确定对同一数组的引用何时可以重叠。

调用图

为了在过程边界之外优化代码，一些编译器执行跨过程分析和优化。为了表示过程之间的调用，编译器构建一个调用图。调用图中每个过程有一个节点，每个不同的过程调用点有一条边。因此，如果代码从p中的三个文本上不同的位置调用q，则调用图会有三条从p到q的边，每条边对应一个调用点。 软件工程实践和语言特性都使调用图的构建变得复杂。

  • 单独编译限制了编译器构建调用图的能力，因为它限制了编译器能够看到的过程集合。一些编译器为编译单元中的过程构建部分调用图，并优化该子集。
  • 以过程值作为参数（无论是实际参数还是返回值）创建了模糊调用，这使得调用图的构建变得复杂。
  • 编译器可能会执行跨过程分析以限制此类调用在调用图中所引起的边集，从而使调用图的构建成为迭代细化的过程。（这个问题类似于在后面讨论的控制流图构建中分支模糊的问题。）
  • 在面向对象程序中，继承可以创建只能通过额外类型信息来解析的模糊过程调用。
  • 在某些语言中，类层次结构分析可以消除许多这些调用的歧义；而在其他语言中，这类信息直到运行时才能得知。 模糊调用的运行时解析对于调用图的构建来说是一个严重的问题；它还给模糊调用增加了显著的运行时开销。

调用图几乎总是作为衍生的中间表示（IR）出现，构建目的是为了支持跨过程分析和优化，之后会被丢弃。实际上，最著名的跨过程变换——内联替换（参见第8章），在执行过程中会改变调用图，使得旧的调用图变得不准确。

回顾总结

图形IR提供了正在编译的代码的抽象视图。图形IR中的抽象级别，如抽象语法树（AST），可以从源代码级别变化到低于机器码级别。图形IR可以作为权威的IR，也可以构建为特殊目的的衍生IR。 由于它们是图，这些IR编码了可能在线性IR中难以表示或操作的关系。图遍历是程序中逻辑连接点之间高效移动的方式；大多数线性IR缺乏这种跨操作的连通性。

更新日志

2025/1/19 03:57
查看所有更新日志
  • e0e13-中间代码结束于