数据依赖和控制依赖分析是许多优化的重要工具，比如指令调度、激进死代码删除（ADCE）等。
数据依赖 Data Dependence
数据依赖的概念
数据依赖是数据流之间的一种依赖，主要包括四种（参考鲸书）。
1.流依赖/真依赖（flow/true dependence）：S1定义了一个值，随后S2使用了这个值。记 S 1 δ f S 2 S1\ \delta^f\ S2 S1 δf S2。
a = b + c // S1
d = a + c // S2
如上例子，S1给a定值， S2使用a。
2.反依赖（anti-dependence）：S1使用了一个值，而随后S2定义了这个值。记 S 1 δ a S 2 S1\ \delta^a\ S2 S1 δa S2。
a = b + c // S1
b = c + d // S2
如上例，S1使用了b，而S2定值了b。
3.输出依赖（output dependence）：两个语句都定义了一个值。记 S 1 δ o S 2 S1\ \delta^o \ S2 S1 δo S2。
a = b + c // S1
a = 3 // S2
如上例，S1和S2都定值了a。
4.输入依赖（input dependence）：两个语句都使用了一个值。记 S 1 δ i S 2 S1\ \delta^i \ S2 S1 δi S2。
a = b + c // S1
d = b + 2 // S2
如上例，S1和S2都使用b。
以上4种数据依赖，前3种依赖都约束了语句的执行顺序，也即不能打乱S1和S2前后执行顺序。
其实，还存在一种情况：不能确定两条语句是否是否可以乱序执行。比如两条使用到不同寄存器进行间接寻址的指令，静态分析时我们可能无法确定两条指令访问的内存是否存在重叠。
r2 <--- [r1] // S1
[r3] <--- r4 // S2
这个例子中，如果不确定r1和r3中存储的地址是否存在重叠，我们只能做保守处理，认为这两条语句存在依赖。
基本块依赖DAG
DAG
在一个基本块内，常用DAG（Directed Acyclic Graph）来表示指令的数据依赖。在DAG中节点表示语句，边表示依赖关系，如果S2必须S1执行了若干拍之后才能执行，则节点S1是S2的前驱。使用一个整数来标记边，这个整数是S1和S2之间要求的等待时间（整数为0时可以省略），等待时间是从S1开始执行到S2开始可以执行之间的延迟减去其他任何指令可以开始执行之前S1所需的执行时间（通常为一拍，但在超标量系统中常常为0）。
r2 <-- [r1] // S1
r3 <-- [r1 + 4] // S2
r4 <-- r2 + r3 // S3
r5 <-- r2 -1 // S4
S1 S2
/ \ /
1 / 1\ /1
V V V
S4 S3
DAG的拓扑排序
拓扑排序：任意一条边 n->m，节点 n 都先于节点 m。
DAG的构建方法有两种：
- 定义法。首先找到DAG中没有入边的顶点，删除它；然后对剩余顶点重复上述过程。
- DFS。使用DFS得到post-order，再得到reverse post-order。
DAG 的构建算法可以戳我另外两篇博客：
拓扑排序（Topological Sorting）：Kahn 算法和 DFS 算法
图，树，遍历顺序 Graphs，Trees and Traversal Oreder
编译器中有一个pass叫做”指令调度“，可以借助DAG的拓扑排序得到较优流水线的指令序列。根据拓扑排序的定义可以知道，满足拓扑排序的指令序列肯定可以保证功能的正确性。但是不同的拓扑排序得到的指令序列性能会有差异。
上图的例子，4到8的边其实是多余的，因为存在了4到6到8的边。但是如果将4到8的边等待时间改为4则这个边不是多余的。1-2-4-5-6-7-8-3和1-2-4-5-6-8-7-3两种拓扑排序都是可行的调度，但是后一种排序比前一种多出一拍。
控制依赖 Control Dependence
控制依赖的概念
控制依赖是程序控制流导致的一种约束。例如：
if (a > 3) goto L1 // S1
b = 2 // S2
c = b + 3 // S3
L1: d = 5 // S4
S2和S3仅在S1中条件不满足时候才执行。记 S 1 δ c S 2 S1\ \delta^c\ S2 S1 δc S2和 S 1 δ c S 3 S1\ \delta^c\ S3 S1 δc S3。。
控制依赖图 CDG
（鲸书）对于一个有向图 G = < N , E > G = <N, E> G=<N,E>，节点n控制依赖于节点m，当且仅当：
- 存在一条m到n的控制路径，n是该路径上除m之外每个节点的后支配节点，并且
- n不是m的后支配节点。
通过求解有向图中节点的控制依赖关系得到控制依赖图（CDG）。虎书中介绍了一种构建CDG的方法：
Dominator和Dominance Frontier相关概念和算法戳我的博客：
支配节点树及其构建算法 Dominator-tree and its Construction Algorithms
支配边界及其构建算法 Dominance Frontier and its construction algorithm
CDG的一个应用：激进死代码删除ADCE
死代码删除（DCE，Dead Code Elimination）和激进死代码删除（ADCE，Aggressive Dead Code Elimination）是编译中常见的优化pass。相较于DCE，ADCE会删除冗余的分支。
ADCE的基本算法：
- 将输入、输出、存储至存储器、有副作用等语句标记成活跃的；
- 将那些对这些有效语句有贡献的语句标记成活跃的（通常使用du链）；
- 对于条件分支语句，其他活跃语句控制依赖于该语句，也标记成活跃的；
- 最后删除不活跃的语句。
文章来源：https://www.toymoban.com/news/detail-485597.html
值得注意的是：ADCE会删除没有输出的无限循环，这在有些场景下是不可接受的。文章来源地址https://www.toymoban.com/news/detail-485597.html
参考
- [1] 高级编译器设计与实现
- [2] 现代编译原理C语言描述（修订版）
到了这里，关于数据依赖和控制依赖 Data Dependence and Contol Dependence的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
