Compilers Chaper 10 总结

这一章介绍了指令级并行。其实就是所说的指令调度。
这一章给人最大的感觉是，作者使用了一半的篇幅在讲软件流水的技术，并且，据说Intel的安腾CPU还提供了循环寄存器堆这种特殊的硬件来支持软件流水。可见，这是一个比较重要的技术。事实上的确如此。软件流水可以尽可能的挖掘循环的并行性，即使有loop carried依赖，也可以进行。而在简单的循环结构中，常常能找到最优的解。

1、体系结构的情况。优化的代码调度可以利用现代计算机体系结构的特点。这些机器通常可以同时执行多个操作。
2、数据依赖。当调度指令的时候，我们必须了解每条指令对存储位置或是寄存器的效果。真数据依赖是一个操作的操作数是另外一个操作的结果。反依赖是一个操作要读一个位置，而另外一个操作要写这个位置。输出依赖是两个操作要写相同的位置。后两种依赖是可以通过使用额外的存储位置（寄存器或主存）而消除的。而真依赖无法消除，必须按照要求的顺序执行。
3、基本块的数据依赖图。这种图表达了基本块中语句之间的执行时间上的约束。图的节点对应与语句，从n到m标记为d的边表示m指令必须在n指令开始执行之后d个周期后才能开始执行。
4、加权的拓扑序。一个基本块的数据依赖图总是没有环的。一般该图有多个拓扑序，我们使用一些启发式规则选择一个最优的拓扑序。
5、表调度。给定一个数据依赖图的加权拓扑序，我们按照这个顺序考虑节点。把每一个节点调度到最早的满足依赖图中时间约束和机器的资源约束的时间槽上。
6、基本块间的代码移动。在某些情况下，我们可能希望将指令在基本块之间移动。这样可以使得指令可以和另外一个基本块中的指令并行地执行。如果在目标基本块和源基本块之间没有Dominate的关系的话，我们还可能需要在某些路径上插入补偿代码，以保证优化后程序的语义。
7、Do-All循环。这些循环的迭代之间没有数据依赖。所有的迭代可以并行地执行。
8、软件流水Do-All循环。软件流水是利用机器并行性的一种技术。我们调度的目标是使每个一个小间隔就可以开始一个新的迭代，可能需要在迭代中插入nop指令来避免迭代之间的对机器资源需求的冲突。软件流水的结果是循环执行得更快，而代码大小不会增大很多。
9、Do-Across循环。循环的不同迭代之间存在数据依赖。
10、Do-Across循环的数据依赖图。为了表示Do-Across的数据依赖，在图的边上的标记需要是一个二元组表示，边（n1,n2），如果本次迭代的是第i次迭代，那么n2需要在第i-L此迭代的n1开始执行之后d个周期后才能开始执行。
11、循环的软件流水调度。为了软件流水一个循环，必须让循环的每一个迭代相对于自己的内部调度都一样，并且，每隔一个固定的周期数就要开始一个新的迭代。流水化算法包括找出资源、依赖对指令调度的约束，找到最小的开始一个新的迭代的周期。