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

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

2)数据依赖约束。优化后的程序中的运算必须和原程序中的相应运算生成相同的结果。

3)资源约束。调度不能够超额使用机器上的资源。

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

1.数据依赖

显然，如果两个运算不接触同一个变量，那么改变这两个运算的执行顺序肯定不会影响它们的执行结果。实际上，即使这两个运算读取同一个变量的值，我们仍然可以交换它们的执行次序。只有当一个运算向一个变量写值，而另一个运算对这个变量执行读或写运算时，改变它们的执行次序才会改变它们的结果。这样的一对操作之间被认为存在数据依赖（data dependence)关系，并且它们的相对执行顺序必须保持不变。有三种类型的数据依赖关系：

1)真依赖：写之后再读。如果一个写运算后面跟随一个对同一个位置的读运算，那么这个读操作就依赖于被写人的值，这种依赖关系被认为是一个真依赖关系。

2)反依赖：读之后再写。如果一个读运算之后跟随一个对同一个位置的写运算，我们说存在一个从读运算到写运算的反依赖关系。写运算本质上不依赖于读运算，但是如果写运算在读运算之前发生，那么这个读运算将读取到错误的值。反依赖关系是强制式编程的一个副产品。这种语言中同一个内存位置可以在不同时刻存放不同的值。这不是一个“真”依赖关系，可以把值存放在不同的位置上以达到消除反依赖关系的目的。

3)输出依赖：写之后再写。对同一个位置的两个写运算之间有输出依赖关系。如果违反了这个关系，那么在这两个运算都完成之后，被写内存位置上存放的是错误的值。

反依赖关系和输出依赖关系被称为存储相关的依赖（storage-related dependence)。这些都不是“真”的依赖关系，可以通过使用不同的内存位置存放不同的值来消除这些依赖关系。请注意, 数据依赖关系对于内存访问和寄存器访问同样有效。

2.寻找内存访问之间的依赖关系

要检查两个内存访问之间是否有数据依赖关系，我们只需要指出它们是否可能指向同一个内存位置，而不需要知道到底访问哪个位置。比如，虽然我们可能不知道指针到底指向哪里，但仍然可以指出两个访问* p和4 (P + 4 )(原文为（* p) + 4——译者注）不可能指向同一个位置。总的来说，数据依赖关系是不可能在编译时刻完全确定的。除非能够证明两个运算指向不同的位置，否则编译器必须假设它们可能会指向同一个位置。

IUQDI给定下麵代码序列：

1)a = 1;

2)*P = 2;

3)X = a;

除非编译器知道P不可能指向《,否则它必须决定这三个运算需要顺序执行。从语句（1 )到语句（2)有一个输出依赖关系，从语句（1)、（2)到语句（3)有两个真依赖关系。

数据依赖分析对于程序所使用的程序设计语言是很敏感的。对于非类型安全的语言，比如c和C++, —个指针可以被强制转换，指向任何类型的数据对象，因此要证明任意一对基于指针的内存访问之间的独立性需要复杂的分析过程。即使对于局部变量和全局标量变量，除非可以证明它们的地址没有被程序中的指令存放到任何地方，它们也有可能通过指针被间接访问。在像Java这样的类型安全的语言中，不同类型的对象一定是相互独立的。类似地，栈中的局部简单变量不可能通过其他的变量名字进行访问。

发现正确的数据依赖关系需要多种不同类型的分析。我们将关注那些主要的问题。如果编译器想要检测一个程序中的所有数据依赖关系，它必须首先解决这些问题，并说明如何使用这些信息进行代码调度。后面的章节将说明这些分析是如何完成的。

数组的数据依赖分析

数组的数据依赖分析问题主要是区分数组元素访问中的下标值。比如，下面的循环

for (i = 0; i < n; i++)

A[2*i] = A[2*i+1];

把数组a的奇数号元素拷贝到紧靠在该元素之前的偶数号元素中去。因为这个循环中所有的读/ 写运算的位置互不相同，这些访问之间没有任何依赖关系，所以循环中所有的迭代都可以并行执 行。数组的数据依赖分析，简称为数据依賴分析（data-dependence analysis)，对于数值应用的优化来说是非常重要的。

指针别名分析

如果两个指针指向同一个对象，我们就说它们互为别名（aliased )。指针别名的分析很困难，原因是一个程序中具有很多可能互为别名的指针。随着时间的发展，它们中的每个都可能指向 无限多个动态对象。为了得到精确的信息，进行指针别名分析时必须跨越程序中的各个函数。

过程间分析

对于通过引用传递参数的语言，需要使用过程间分析来确定是否同一个变量被当作两个或多个不同的参数进行传递。这类别名看起来可能会在不同的参数之间建立依赖关系。类似地，全局变量可能被用作参数，由此会建立参数访问和全局变量访问之间的依赖。在确定这些别名时，讨论的过程间分析技术是必需的。