编译原理——循环和迭代

•do-across循环的数据依赖图：为了表示do-across循环的指令之​​间的相关性，需要用一对值来标记边缘：所需的延迟（如代表基本块的图）和具有依赖性的两条指令之间的迭代次数。
•循环列表调度：要计划一个循环，我们必须为所有迭代选择一个调度，并选择连续迭代开始的启动间隔。该算法涉及通过找到两个节点之间最长非循环路径的长度来推导循环中各种指令相对调度的约束。这些长度以起始间隔作为参数，因此要在起始间隔上设置下限。
•数组中的并行性和局部性。基于并行性和局部性的最有优化空间的部分来自访问数组的循环。这些循环往往对数组元素的访问具有有限的依赖性，并且倾向于以一种规则的模式访问数组，并允许高效地使用缓存以获得良好的局部性。
•仿射访问。几乎所有用于并行和局部优化的理论和技术都假设对数组的访问是仿射的：数组索引的表达式是循环索引的线性函数。
•执行空间。具有d个嵌套循环的循环嵌套定义了d维迭代空间。空间中的点是循环索引在执行循环嵌套期间可以假设值的d元组。在仿射情况下，每个循环索引的限制是外环索引的线性函数，所以迭代空间是一个多面体。
•Fourier - Motzkin消除。迭代空间的一个关键操作是对定义迭代空间的循环重新排序。这样做需要将多面体迭代空间投影到其维的子集上。 Fourier-Motzkin算法通过限制本身之间的不等式来替代给定变量的上限和下限。