第十一章 代码优化论述.ppt

11.3.2 循环的查找 分析程序流图中结点间的关系 m DOM n 定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n (?a,a DOM a) 必经结点集 定义 结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n). 例 : 6 7 3 4 1 2 3 5 7 6 1 2 1 2 1 2 1 必经结点集 D(1)={1} D(2)={1,2} D(3)={1,2,3} D(4)={1,2,4} D(5)={1,2,4,5} D(6)={1,2,4,6} D(7)={1,2,4,7} 3 回边： 假设a→b是流图中的一条有向边，如果b DOM a，则a→b是流图中的一条回边。 对于一已知流图，只要求出各结点的必经结点集，就可以求出流图中所有的回边。 必经结点集 D(1)={1} D(2)={1,2} D(3)={1,2,3} D(4)={1,2,4} D(5)={1,2,4,5} D(6)={1,2,4,6} D(7)={1,2,4,7} 6 7 3 4 1 2 3 5 7 6 1 2 1 2 1 2 1 3 回边 4 → 2 6→6 7 → 4 循环： 有向边n→d是回边，组成的循环是由结点d、节点n以及有通路到达n而该通路不经过d的所有节点组成，并且d是该循环的唯一入口节点。 回边 6→6：该回边组成的循环所包含的节点为 6 回边7 → 4：该回边组成的循环所包含的节点为 4,5,6,7 回边4 → 2：该回边组成的循环所包含的节点为 2,3,4,5,6,7 6 7 3 4 1 2 3 5 7 6 1 2 1 2 1 2 1 3 11.3.3 循环优化 1.代码外提 2.强度消弱与删除归纳变量 (1) I:=1 (2) if XY goto B3 B1 B2 (3) I:=2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 X=30, Y=25 J=1, I=1 1. 代码外提 找循环不变运算 循环：{B2，B3，B4} 循环不变运算是否 都可以提到循环外面？ (1) I:=1 (2) if XY goto B3 B1 B2 (3) I:=2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 X=25, Y=30 J=2, I=2 代码外提条件:不变运算A所在的结点是循环所有出口结点的必经结点. (1) I:=1 (2′) I:=3 (2) if XY goto B3 B1 B2 (3) I:=2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 考虑: B2 ?B3 ? B4 ? B2 ? B4 ? B5 I=3, J=3 不变运算A所在的结点是循环所有出口结点的必经结点一定能外提？ 考虑: B2 ?B3 ? B4 ? B5 I=2, J=2 代码外提条件: A在循环中其他地方未再定值,才能把循环不变运算A:=B op C外提; (1) I:=1 (2′) I:=3 (2) if XY goto B3 B1 B2 (3) I:=2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 代码外提条件: 不变运算A所在的结点是循环所有出口结点的必经结点， 并且A在循环中其他地方未再定值,才能把循环不变运算A:=B op C外提; 或 不变运算A在循环中其他地方未再定值，并且出了A所属的循环后，不在引用A (1) I:=1 (2) I:=3 (3) if XY goto B3 B1 B2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 (1) I:=1 (3) if XY goto B3 B1 B2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 (2) I:=3