指令调度：修订间差异

指令调度（instruction scheduling）是一种代码优化手段，常见于优化编译器，其主要功能在于通过加强指令层级的并行运行，使得程序在拥有指令流水线的中央处理器上能够高效运行。换句话说，此手段力求以不改变程序运算结果的方式，完成以下任务：

• 通过重组指令的运行顺序，减少或阻止流水线停顿的发生;
• 阻止非法操作（即未定义行为）的产生，例如涉及流水线时序、非互锁资源的等等操作。

其中流水线停顿主要由结构型冒险（受处理器的资源所限）、数据型冒险以及控制流型冒险导致。

数据型冒险

指令调度一般在某基础块（basic block）上执行。为了确保指令的运行顺序在重组后，其运算结果依旧不变，编译器的开发者们必须要认识到数据依赖这种概念。数据型冒险总共有三种，其性质恰恰与数据型冒险相符，这三种数据冒险分别是：

1. 写入后读取（RAW, Read After Write） - I₁ 的输出值之后会被 I₂ 使用。
2. 读取后写入（WAR, Write After Read） - I₁ 的输入位置之后会被 I₂ 使用并覆盖。
3. 写入后写入（WAW, Write After Write） - I₁ 以及 I₂ 皆将结果写入同一个位置上。

其中 I₁ 以及 I₂ 是两个在不同时间点上执行的指令。

对于这三种冒险，指令 I₁ 都必须执行于 I₂ 被执行前，否则其运算结果是不被定义的（具体结果视该机器的硬件实现而定）。对于冒险1，这是因为 I₂ 依赖着 I₁ 的数据；对于冒险2，则是因为 I₁ 依赖着即将被 I₂ 所覆盖的数据；对于冒险3，则是因为在 I₁ 和 I₂ 之间所运行的指令可能会使用到 I₁ 的输出结果。为了确保这些数据依赖所需的运行顺序得到保证，编译器首先需要建立一幅依赖图，即一幅顶点是指令，而边是依赖性的有向图。最终，这幅图的任何一种拓扑排序都可以是有效的指令调度表。

类型

指令调度有几种类型，其中包括了：

1. 本地（基础块）调度：指令仅能在其所在基础块内移动。
2. 全局调度：指令能在各基础块内移动。
3. 模算调度：属于一种软件流水线的生成算法，通过交叉运行不同的循环达到指令层级并行的效果。
4. 跟踪调度：第一种真正实用的全局调度方法，编译器尽力优化最常被运行的代码控制流路。
5. 超块（superblock）调度： 跟踪调度的简化版。