有些代码改进转换所依赖的信息是按照程序控制流的相反方向进行计算的，我们现在将要研究这样的一个例子。在活跃变量分析（live-variable analysis)中，我们希望知道对于变量x和程 序点P, *在点上的值是否会在流图中的某条从点P出发的路径中使用。如果是，我们就说x在 p上活跃，否则就说*在p上是死的。

活跃变量信息的重要用途之一是为基本块进行寄存器分配。这个问题的某些方面，在一个值被计算并保存到一个寄存器中后，它很可能会在基本块中使用。如果它在基本块的结尾处是死的，就不必在结尾处保存这个值。另外，在所有寄存器都被占用时，如果我们还需要申请一个寄存器的话，那么应该考虑使用一个存放了已死亡的值的寄存器，因为这个值不需要保存到内存。

交汇运算是交集运算，任何发现x+y在某个程序点上不可用的理由都会在流图中沿着所有可能的路径向前传播，直到x+y被重新计算并再次变得可用为止。第二，只有两个理由可能会使x+y变成不可用的。

1）因为x或y在基本块B中被定值且其后没有计算x+y，因此x+y被杀死。在这种情况下，我们第一次应用传递函数fs的时候，x+y就会从OUT[B]中被删除。

2)在某些路径中，x+y—直没有被计算。因为x+y肯定不会在OUT[ENTRY]中，并且它也不会在上面说的那条路径中被生成。我们可以通过对路径长度的归纳来证明x + y最终会从这条路径的所有基本块的IN和OUT值中删除。

把域V画成一个格图对我们会有所帮助。格图的结点是V的元素，而它的边是向下的，即如果y≤x，那么从x到y有一个边。给出了一个到达定值数据流模式的集合V。其中有三个定值：d1、d2和d3。因为半格中的偏序关系在≤是⊇,从这三个定值的集合的子集到 其所有超集有一个向下的边。因为 ≤是传递的，如果有一条从x到y的路径，我们可以按照惯例省略从x到y的边。因此，虽然在这个例子中{d1,d2,d3}≤{d1},我们并没有画出这条边，因为这个边可以用经过d1，d2的路径来表示。

有一点也很有用，即我们可以从这样的图中读出交汇值。因为x ∧y就是它们的最大下界，因此这个值总是最高的、从x和y都有向下的路径到达的元素z。比如，如果想x是 {d1}而y是{d2},那么z就是{d1，d2}。这是正确的，因为这里的交汇运算是并集运算。顶元素将出现在格图的顶部，也就是说，从T到图中的每个元素都有一条向下的路径。类似地，底元素将出现在图的底部，从每个元素都有一条边到达丄。

数据流框架具有有穷高度的情况。因为每个IN[B]和OUT[B]的值在每次被改变时都会减小，而程序在某一轮循环中没有值改变时就会停止，因此算法的迭代次数不会大于框架高度和流图结点个数的乘积，因此算法必然终止。
我们可以对算法进行推广，使之能够处理各种数据流问题。通用数据流框架的迭代解法。

输入：一个由下列部分组成的数据流框架：

1)一个数据流图，它有两个被特别标记为ENTRY和EXIT的结点。

2)数据流的方向D。

3)一个值集V。

所有根据流模式实际上都是具有有限高度的可分配框架的简单例子。这样，迭代算法的前向或逆向版本可以用来解决这些问题，并求出每个问题的MOP解。我们将深人研究一个具有更多有趣性质的有用的数据流框架。

回忆一下常量传播（或者说“常量折叠”），即把那些在每次运行时总是得到相同常量值的表达式替换为该常量值。下面描述的常量传播框架和至今已经讨论的数据流问题都有所不同。不同之处在于：

1)它的可能数据流值的集合是无界的。即使对于一个确定的流图也是如此。

2)它不是可分配的。

如果一个程序中的所有运算之间都是高度依赖的，那么再多的硬件或采用并行化技术都无法使这个程序快速并行执行。关于并行化的限制方面已经有了很多研究。典型的非数值应用有很多固有的依赖性。比如，这些程序具有很多依赖于数据的分支，使得哪怕预测一下下面将执行哪条指令都变得很困难，更不要说去决定哪些运算可以并行执行了。因此，这个领域中的研究工作集中在放松调度约束的技术，包括引人新的体系结构特性，而不是调度技术本身。
每一个现代高性能处理器都能够在一个时钟周期内执行多条指令。在一个具有指令级并行机制的处理器上一个程序能够以多快的速度运行？这可是一个“价值十亿美元的问题”。对这个问题的回答要考虑下列因素：

这些调度约束保证了优化后的程序和原程序生成同样的结果。但是，因为代码调度改变了运算执行的顺序，所以优化后的程序执行时某一点上的内存状态可能和顺序执行时任一点上的内存状态都不匹配。如果一个程序的执行因异常或用户设定的断点而中断时，就会产生问题。因此经过优化的程序比较难以调试。请注意，这个问题不是代码调度专有的，所有的优化技术都会出现这个问题，包括部分冗余消除和寄存器分配。
代码调度是程序优化的一种形式，它应用于由代码生成器生成的机器代码。代码调度要遵守下面三种约束：

1)控制依赖约束。所有在原程序中执行的运算都必须在优化后的程序中执行。

我们将假设源程序的机器无关中间表示形式使用了无限多个伪寄存器（pseudoregister)。 这些伪寄存器代表了可以分配到寄存器的变量。这些变量包括源程序中不能通过任何其他名字访问的标量，也包括由编译器生成的用于存放表达式的部分结果的临时变量。和内存位置不同，寄存器的命名是唯一的。因此可以很容易地为寄存器访问生成精确的数据依赖约束。

在中间表示形式中使用的无限多个伪寄存器最终必须被映射到在目标机器上可用的少量物理寄存器。把几个伪寄存器映射为同一个物理寄存器有一个副作用。这种映射会生成人为的存储依赖，这限制了指令级的并行性。反过来，并行执行指令产生了更多的存储需求，以便存放同时计算出来的值。因此，尽量降低寄存器使用数量的目标和最大化指令级并行性的目标直接冲突。

代码移动可能会改变运算之间的数据依赖关系。因此在每次代码移动之后都必须更新数据依赖关系。

对x的两个赋值 之一可以被向上移动到顶部的基本块，因为这样的转换保持了原程序中的所有依赖关系。但是，一但我们把其中一个赋值语句上移，就不能再移动另一个。更明确地说，我们看到在代码移动之前顶部的基本块的出口处X是不活跃的，但是在移动之后就变得活跃了。如果一个变量在一个程序点上活跃，那么我们不能把对该变量的投机性定值移动到该程序点的前面。

全局调度算法

我们看到代码移动对某些路径有益，但是会损害另外一些路径的性能。好消息是指令并不是生而平等的。实际上，我们知道，一个程序的90%以上的执行时间被花在不到10%的代码上。因此，我们可以把目标确定为使得频繁执行的路径更快运行，虽然有可能降低不频繁路径的运行速度。

由于无法重复地在Flash的同一块存储位置做写入操作（必须事先擦除该块后才能再写入)，因此 一般在硬盘上使用的文件系统，如FAT16、FAT32、 NTFS、Ext2等将无法直接用在Flash上，为了沿用 这些文件系统，则必须透过一层转换层（Translation Layer)来将逻辑块地址（Logical Block Address)对 应到Flash存储器的物理位置，使系统能把Flash当作普通的硬盘一样处理，我们称这层为FTL (Flash Translation Layer)。FTL 应用于NOR Flash.而 NFTL则应用于NAND Flash。