LLVM 中的数据依赖图

简介

数据依赖图是编译器中用于分析各种程序元素之间关系的有用工具，有助于指导优化。这些图背后的思想在论文 [1] 和 [2] 中进行了描述。

LLVM 中这些思想的实现可能与论文中提到的略有不同。这些差异在 实现细节 中有记录。

数据依赖图

在最简单的形式中，数据依赖图 (或 DDG) 表示各个指令之间的数据依赖关系。此类图中的每个节点都表示单个指令，并被称为“原子”节点。也可以将一些具有简单 def-use 依赖关系的原子节点组合成包含多个指令的更大节点。

如 [1] 中所述，DDG 使用图抽象将图的强连通分量中的节点分组到称为 pi-块的特殊节点中。pi-块表示阻止重新排序转换的数据依赖循环。由于图的任何强连通分量都是形成循环的所有节点的最大子图，因此 pi-块最多只有一层深度。换句话说，没有 pi-块嵌套在另一个 pi-块内部，从而产生最多只有一层深度的分层表示。

例如，考虑以下内容

for (int i = 1; i < n; i++) {
  b[i] = c[i] + b[i-1];
}

此代码包含一条语句，该语句对其自身具有循环携带依赖关系，从而在 DDG 中创建一个循环。下图说明了依赖循环如何通过多个 def-use 关系和内存访问依赖关系传递。

../_images/cycle.png

对应于此示例的 DDG 将有一个 pi-块，其中包含参与循环的所有节点，如下所示

../_images/cycle_pi.png

程序依赖图

程序依赖图 (或 PDG) 与 DDG 具有类似的结构，但它能够表示程序元素（如指令、指令组、基本块或基本块组）之间的数据依赖关系和控制流依赖关系。

高级设计

DDG 和 PDG 都是有向图，并且它们扩展了 DirectedGraph 类。每个实现都扩展其相应的节点和边类型，从而导致下图所示的继承关系

../_images/uml_nodes_and_edges.png

图构建

图构建算法考虑给定指令集或基本块集中元素之间的依赖关系。来自或进入不属于该范围的指令的任何依赖关系都会被忽略。DDG 构建算法中的步骤与 PDG 构建算法中的步骤非常相似。因此，设计目标之一是重用构建算法代码，以允许创建 DDG 和 PDG 表示，同时允许这两个实现定义自己独特且独立的节点和边类型。这是通过使用众所周知的构建器设计模式来实现的，该模式将依赖图的构建与其具体表示分离。

下图描绘了设计模式的整体结构，因为它适用于依赖图的实现。

../_images/uml_builder_pattern.png

请注意，用于构建两种类型图的公共代码在 DependenceGraphBuilder 类中提供，而 DDGBuilder 和 PDGBuilder 通过覆盖 DependenceGraphBuilder 中定义的虚方法来控制图构建的一些方面。

另请注意，此图中使用的步骤和名称仅用于说明目的，可能与实际实现中的步骤和名称不同。

设计权衡

优势:

  • 构建器允许将图构建代码重用于 DDG 和 PDG。

  • 构建器允许我们将 DDG 和 PDG 创建为单独的图。

  • DDG 节点和边与 PDG 节点和边完全分离，允许它们轻松且独立地更改。

劣势:

  • 最初可能会认为构建器是过度工程。

  • DDG 节点和边与 PDG 节点和边之间存在一些相似之处，但类定义的重用很少。

    • 鉴于节点和边类型相当简单，并且代码重用机会本来就很少，因此这是可以容忍的。

实现细节

DDG 的当前实现与 [1] 中描述的数据依赖图略有不同，具体如下

  1. 论文中的图节点表示三个主要程序组件，即赋值语句、for 循环头和while 循环头。在此实现中，DDG 节点自然表示 LLVM IR 指令。在此实现中，赋值语句通常涉及表示 store 指令的节点以及计算赋值右侧的许多单个节点，这些节点通过 def-use 边连接到 store 节点。循环头指令在此实现中不表示为特殊节点，因为它们的用途有限并且易于识别，例如，通过 LoopAnalysis。

  2. 论文描述了节点之间五种类型的依赖边，即循环依赖、流、反、输出和输入依赖。在此实现中，内存边表示流、反、输出和输入依赖。但是，循环依赖没有明确表示，因为它们主要表示循环结构与其内部程序元素之间的关联，并且这种关联在 LLVM IR 本身中非常明显。

  3. 论文描述了两种类型的 pi-块；递归，其主体是 SCC，以及IN 节点，其主体不属于任何 SCC。在此实现中，仅为递归创建 pi-块。IN 节点在图中仍然是简单的 DDG 节点。

参考文献