如果我们按照图11.15的程序流图执行,执行到B5时,i的值总为2,则j的值也为2。事实上,按图11.14的流图,若x=30,y=25,则B3不被执行,执行到B5时,i和j的值都为1,所以图11.15的流图改变了原来程序的运行结果。 问题的原因在于B3不是循环出口结点B4的必经结点。所以,当把一个不变运算提到循环的前置结点时,要求该不变运算所在的结点是循环所有出口结点的必经结点。 此外,如果循环中i的所有引用点只是B2中i的定值点("点"指某一四元式的位置,对变量的"定值"指对变量赋值或输入值)所能达到的,i在循环中不再有其它定值点,并且出循环后不再引用该i的值,那么,即使B3不是B4的必经结点,也还可以把i∶ =2提到B′2中,因为这不影响原来程序的运行结果。 如果把图案11.14中的B2改为 i:= 3; if x<y goto B3 试考虑B2中不变运算i:= 3的外提问题。 现在i:= 3所在的结点B2是循环出口结点的必经结点。但因为循环中除B2外,B3也对i定值,如果把B2中不变运算i:= 3外提到循环的前置结点中,则程序的执行流程是B2→B3→B4→B2→B4→B5,那么到达B5时i的值是2,而j的值也是2;可是如果不把B2中不变运算i:= 3外提,经以上执行流程到达B5时i的值是3,而j的值也是3,并不是2。从该例看到,当把循环中不变运算A:=B op C外提时,要求循环中其它地方不再有A的定值点。 这里所说的定值点指变量在该点被赋值或输入值,引用点则指在该点使用了该变量,定值和引用的关系是全局优化和数据流分析研究的问题,我们不进行讨论。 |