代码外提首先要找到不变运算。所谓不变运算，是指无论循环代码反复执行多少次，那些结果均不改变的运算。例如，假设循环中有形如X：=Y op Z的代码，如果Y、Z是常数，或者循环内没有对Y、Z重新定值，则意味着循环次数对该代码的运算结果毫无意义。因此，对于这种不变运算Y op Z，我们可以把它放到循环外执行。这样做，不会导致程序的运行结果改变，反而提高了程序的运行速度。这种优化技术就是代码外提。
从循环中提出的代码可以放置在循环入口结点的前面，构成一个新的基本块，称为前置结点。循环入口结点是唯一的，前置结点也必须是唯一的。前置结点以循环入口结点为其唯一后继结点，原流图中从循环外指向循环入口结点的有向边，均得改为指向前置结点，如图8-6所示。
图8-6 增加循环前置结点的流图
例8.4 对于如下的一段程序代码：
假设循环体不改变limit的值，那么limit-2为循环不变运算，可将其外提到循环的前置结点中，如图8-7所示。
图8-7 经过代码外提的程序
然而必须指出的是，并非所有的循环不变运算都可以外提。下面通过一个例子来说明这一点。
例8.5 对于如下一段代码：
其流图如图8-8所示。
图8-8 例8.5中程序的流图(www.xing528.com)
容易看出，基本块L2和L3构成循环，L2既是循环的入口结点，又是出口结点。所谓出口结点，是指循环中具有这样性质的结点，它有一条有向边引到循环外的某结点。对于循环不变运算x：=12*B，我们分两种情形讨论能否将其外提。
一种情形是，假设A=20，B=25，此时，无论x：=12*B是否外提，当执行到L4时，x的值总是300，从而y的值也是300。
另一种情形是，如果A=40，B=30，L3是不会被执行的。代码外提之前，执行到L4时，y的值应是60；但当代码外提之后，执行到L4时，y的值却变成了360。这说明代码外提改变了原来程序的运行结果，优化出现了问题。
由例8.5可以看出，代码外提是有条件的。只有符合以下条件的循环不变运算才可以外提：
（1）进行代码外提的不变运算，其所在的结点必须是循环所有出口的必经结点。
（2）把形如X：=Y op Z的不变运算外提时，要求循环中的其他地方不能对X再定值，而且对X的所有引用值均为该不变运算中确定的X的值。
至于如何查找循环W的不变运算，可以采用如下的算法进行：
（1）依次查看W中各基本块的每条代码，若其每个运算对象要么是常数，要么定值点在W外，则将此代码标记为“不变运算”。
（2）查看每条未被标记为“不变运算”的代码，若其每个运算对象要么是常数，要么定值点在W外，要么只有一个到达一定值点且该点上的代码已标记为“不变运算”，则把该被查看的代码标记为“不变运算”。重复执行此步骤，直至没有新的代码被标记为“不变运算”为止。
对标记为“不变运算”的代码执行如下的代码外提算法：
（1）对形如X：=Y op Z或X：=Y的所有不变运算，检查它是否满足下述条件①或②：
①同时具备3点：（i）不变运算所在的结点是循环的所有出口结点的必经结点；（ii）X在循环中的其他地方未再定值；（iii）循环中对X的所有引用均引用的是此循环中该X的定值。
②X在离开循环后是不活跃的，且条件①的（ii）和（iii）成立。所谓X在离开循环后不活跃是指，3X在循环的任何出口结点的后继结点的入口处不是活跃的。
（2）依次把符合上述条件之一的不变运算外提到循环的前置结点中。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
