一个重要的优化是在循环中找到归纳变量并优化它们的计算。对于一个变量^如果存在 一个正的或负的常数c使得每次x被赋值时它的值总是增加c，那么x就称为“归纳变量”。比如， 在i和t2都是B2组成的循环中的归纳变量。归纳变量可以通过每次迭代进行一次简 单的增量运算（加法或减法）来计算。把一个高代价的运算（比如乘法）替换为一个代价较低的运 算（比如加法）的转换被称为强度消减（strength reduction)。但是归纳变量不仅允许我们在适当的 时候进行强度消减优化；在我们沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，我们常常可以将这组变量删剩一个。
在处理循环时，按照“从里到外”的方式进行工作是很有用的。也就是说，我们应该从内部循环开 始，然后逐步处理较大的外围循环。这样，我们将看到这个优化是如何从最内层的循环之一（即B3)开 始被应用到我们的快速排序例子中的。请注意，j和t4的值的步调保持一致；因为4*j被赋给t4，每次 j的值减少1时t4的值就减少4。变量y和t4就形成了一个很好的归纳变量对的例子。
当一个循环中存在两个或更多的归纳变量时，有可能只留下一个而删除其他的变量。对内层循环B3,我们不能把或完全删除。t4在B3中使用，而j在B4中使用。但是，我们可以用这个例子来说明强度消减优化以及归纳变量消除的部分过程。当考虑由B2、B3、B4、B5组成的外层循环时，y最终会被消除。
数据流分析简介
在介绍的所有优化都依赖于数据流分析。“数据流分析”指的是一组用来获取有关数据如何沿着程序执行路径流动的相关信息的技术。比如，实现全局公共子表达式消除的方法之一要求我们确定在程序的任何可能执行路径上，两个在文字上相同的表达式是否会给出相同的值。另一个例子是，如果某一个赋值语句的结果在任何后续的执行路径中都没有被使用，那么我们可以把这个赋值语句当作死代码消除。这些以及很多其他重要问题，都可以通过数据流分析来回答。
数据流抽象
可知，程序的执行可以看作是对程序状态的一系列转换。程序状态由程序中的所有变量的值组成，同时包括运行时刻栈的栈顶之下各个栈帧的相关值。一个中间代码语句的每次执行都会把一个输人状态转换成一个新的输出状态。这个输人状态和处于该语句之前的程序点相关联，而输出状态和该语句之后的程序点相关联。
当我们分析一个程序的行为时，我们必须考虑程序执行时可能采取的各种通过程序的流图 的程序点序列（“路径”）。然后我们从各个程序点上可能的程序状态中抽取出需要的信息，用以 解决特定数据流分析问题。在更加复杂的分析中，我们必须考虑调用和返回执行时会形成在不 同过程的流图之间跳转的路径。但是，在我们刚开始研究的时候，我们将关注穿越单个过程的单个流图的路径。
*让我们看一下流图会给出哪些关于可能执行路径的信息。
在一个基本块内部，一个语句之后的程序点和它的下一个语句之前的程序点相同。
*如果有一个从基本块B1到基本块B2的边，那么B2的第一个语句之前的程序点可能紧跟在B1的最后一个语句后的程序点之后。
这样，我们可以把从点P1到点Pn的一个执行路径（excution path,简称路径）定义为满足下列条件的点的序列P'1，P2’…，Pn ：对于每个i = 1，2，…，n-1：
1)要么九是紧靠在一个语句前面的点，且九+ 1是紧跟在该语句后面的点。
2)要么pi是某个基本块的结尾，且pi+ 1是该基本块的一个后继基本块的开头。
一般来说，一个程序有无穷多条可能的执行路径，执行路径的长度并没有上界。程序分析把可能出现在某个程序点上的所有程序状态总结为有穷的特性集合。不同的分析技术可以选择抽 象掉不同的信息，并且一般来说，没有哪个分析会给出状态的完全表示。
即使是图9-12中的简单程序也描述了无限多个执行路径。最短的完全执行路径由程 序点（1, 2, 3，4，9)组成，它不进入任何循环。次短的路径执行一次循环，它由程序点（1，2, 3，4，
5，6，7，8，3，4，9)组成。在这个例子中，我们知 道在第一次执行程序点（5)时，因为 < 的定值，a的值必然是1。我们说士在第一次迭代的时候到达了点（5)。在其后的迭代中，d3到达了点（5)， a的值是243。
一般来说，跟踪所有路径上的所有程序状态是不可能的。在数据流分析中，我们并不区分到达一个程序点的路径之间的差异。此外，我们并不跟踪整个状态，而是抽象掉某些细节，只保留进行分析所需要的数据。下面的两个例子将说明一个程序点上的同一个状态可以导出不同的抽象信息。
1)为了帮助用户调试他们的程序，我们可能希望找出在某个程序点上一个变量可能有哪些值，以及这些值可能在哪里定值。比如，我们可能对在程序点（5)上的所有程序状态进行如下总结：a的值总是{1，243}中的一个，而它由{d1，d2}中的一个定值。可能沿着某条路径到达某个程序点的定值称为到达定值（reaching definition)。
2)假设我们感兴趣的不是到达定值，而是常量折叠的实现。如果对变量x的某次使用只有一个定值可以到达，并且该定值把一个常量赋给那么我们可以简单地把x替换为该常量。另一方面，如果有多个对x的定值可以到达某一个程序点，我们就不能对x进行常量折叠转换。因此，为了进行常量折叠，我们希望找到这样的定值：对于某个给定的程序点，不管执行哪条路径，它们都是唯一到达该点的对相应变量的定值。对于图9-12中的点(5),没有哪个定值是到达该点的对a的唯一定值，因此对于点（5)上的a来说，这个集合是空的。即使一个变量在某个点上被唯一定值，该定值必须把一个常量值赋给该变量，才可能进行常量折叠转换。这样，我们可以简单地把某些变量描述成“非常量”，而不是记录它们所有可能的取值，或者所有可能的定值。
因此，我们看到，根据分析的目的，同样的信息可以通过不同的方式进行概括。