LLVM 中的依赖图¶
介绍¶
依赖图是编译器中有用的工具，用于分析各种程序元素之间的关系，以帮助指导优化。这些图背后的思想在论文 [1] 和 [2] 中进行了描述。
这些思想在 LLVM 中的实现可能与论文中提到的略有不同。这些差异在实现细节中进行了记录。
数据依赖图¶
数据依赖图 (DDG) 的最简单形式表示单个指令之间的数据依赖关系。这种图中的每个节点代表一个单独的指令，被称为“原子”节点。也可以将一些在它们之间具有简单 def-use 依赖关系的原子节点组合成包含多个指令的更大的节点。
如 [1] 中所述，DDG 使用图抽象将图中强连通分量的节点分组到称为 pi-block 的特殊节点中。pi-block 表示阻止重排序转换的数据依赖循环。由于图的任何强连通分量都是形成循环的所有节点的最大子图，因此 pi-block 最多只有一层深度。换句话说，没有 pi-block 嵌套在另一个 pi-block 内部，从而形成最多只有一层深度的分层表示。
例如，考虑以下代码
for (int i = 1; i < n; i++) {
b[i] = c[i] + b[i-1];
}
此代码包含一个语句，该语句具有自身携带的循环依赖关系，从而在 DDG 中创建循环。下图说明了依赖循环如何通过多个 def-use 关系和内存访问依赖关系进行传递。
与此示例对应的 DDG 将具有一个 pi-block，其中包含参与循环的所有节点，如下所示
程序依赖图¶
程序依赖图 (PDG) 具有与 DDG 类似的结构，但它能够表示程序元素（如指令、指令组、基本块或基本块组）之间的数据依赖关系和控制流依赖关系。
高层设计¶
DDG 和 PDG 都是有向图，它们都扩展了 DirectedGraph 类。每个实现都扩展了其对应的节点和边类型，从而产生了下图 UML 图中所示的继承关系
图的构建¶
图构建算法考虑给定指令集或基本块集中的元素之间的依赖关系。任何进入或离开不属于该范围的指令的依赖关系都将被忽略。DDG 的构建算法步骤与 PDG 的构建算法步骤非常相似。因此，设计目标之一是重用构建算法代码，以允许创建 DDG 和 PDG 表示，同时允许两个实现定义它们自己独特且独立的节点和边类型。这是通过使用众所周知的构建器设计模式来实现的，该模式将依赖图的构建与其具体表示形式隔离开来。
以下 UML 图描述了设计模式应用于依赖图实现的总体结构。
请注意，构建两种类型图的公共代码在 DependenceGraphBuilder 类中提供，而 DDGBuilder 和 PDGBuilder 通过重写 DependenceGraphBuilder 中定义的虚方法来控制图的构建方式的某些方面。
另请注意，此图表中使用的步骤和名称仅用于说明目的，可能与实际实现中的步骤和名称不同。
设计权衡¶
优点：¶
构建器允许图构建代码在 DDG 和 PDG 之间重用。
构建器允许我们将 DDG 和 PDG 创建为单独的图。
DDG 节点和边与 PDG 节点和边完全不相交，从而允许它们轻松且独立地更改。
缺点：¶
构建器最初可能被认为是过度工程。
与 PDG 节点和边相比，DDG 节点和边之间存在一些相似之处，但类定义的重用很少。
考虑到节点和边类型相当简单，并且无论如何代码重用的机会很少，这是可以容忍的。
实现细节¶
当前 DDG 的实现与 [1] 中描述的依赖图略有不同，具体体现在以下方面
论文中的图节点代表三个主要的程序组件，即 *赋值语句*、*for 循环头* 和 *while 循环头*。在此实现中，DDG 节点自然地表示 LLVM IR 指令。在此实现中，赋值语句通常涉及一个表示
store指令的节点，以及一些计算赋值右侧的单独节点，这些节点通过 def-use 边连接到store节点。循环头指令在此实现中不表示为特殊节点，因为它们用途有限，并且可以很容易地识别，例如，通过LoopAnalysis。该论文描述了节点之间的五种依赖边类型，即 *循环依赖*、*流依赖*、*反依赖*、*输出依赖* 和 *输入依赖*。在此实现中，*内存* 边表示 *流依赖*、*反依赖*、*输出依赖* 和 *输入依赖*。但是，*循环依赖* 没有明确表示，因为它们主要表示循环结构与循环内部的程序元素之间的关联，并且这种关联在 LLVM IR 本身中非常明显。
该论文描述了两种类型的 pi-block；主体是 SCC 的 *recurrences* 和主体不是任何 SCC 的一部分的 *IN* 节点。在此实现中，pi-block 仅为 *recurrences* 创建。*IN* 节点在图中仍为简单的 DDG 节点。