10 第十章 优化.pptx

第1页：第十章优化

第十章优化

• 编译原理

第2页：第十章优化（续）

第十章优化（续）

• 号语法单位四元式表格管理出错处理目标代码生成器四元式目标代码

第3页：第十章优化

第十章优化

优化

对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。

等价

指不改变程序的运行结果。

有效

指目标代码运行时间短，占用的存储空间小。编译前端代码优化器编译后端控制流分析数据流分析代码变换

第4页：10.1概述

10.1概述

等价原则

经过优化后不应改变程序运行的结果；

有效原则

使优化后所产生的目标代码运行时间较短，占用的存储空间较小；

合算原则

应尽可能以较低的代价取得较好的优化效果。

第5页：10.1概述（续）

10.1概述（续）

• 优化的三个不同级别：
• 局部优化
• 循环优化
• 全局优化
• 优化的种类：
• 删除多余运算(或称删除公用子表达式)
• 代码外提
• 强度消弱
• 变换循环控制条件
• 合并已知量
• 复写传播
• 删除无用赋值

第6页：10.1概述

10.1概述

intm,n;{inti,j;intv,x;if(n<=m)return;i=m-1;j=n;v=a[n];while(1){doi=i+1;while(a[i]<v);doj=j-1;while(a[j]>v);if(i>=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;quicksort(m,j);quicksort(i+1,n);}

第7页：10.1概述（续）

10.1概述（续）

中间代码程序段i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:=4*ix:=a [T6]T7:=4*iT8:=4*jT9:=a [T8]a [T7]=T9T10:= 4*ja [T10]=xgoto B2B5T11:=4*ix:=a [T11]T12:=4*iT13:=4*nT14:=a [T13]a [T12]=T14T15:= 4*na [T15]=xB6

第8页：10.1概述

10.1概述

中间代码程序段i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:=4*ix:=a [T6]T7:=4*iT8:=4*jT9:=a [T8]a [T7]=T9T10:= 4*ja [T10]=xgoto B2B5T11:=4*ix:=a [T11]T12:=4*iT13:=4*nT14:=a [T13]a [T12]=T14T15:= 4*na [T15]=xB6

第9页：10.1概述（续）

10.1概述（续）

删除公用子表达式后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:= T2x:=a [T6]T7:= T6T8:= T4T9:=a [T8]a [T7]=T9T10:= T8a [T10]=xgoto B2B5T11:= T2x:=a [T11]T12:= T11T13:= T1T14:=a [T13]a [T12]=T14T15:= T13a [T15]=xB6

第10页：10.1概述

10.1概述

复写传播i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:= T2x:=a [T6]T7:= T6T8:= T4T9:=a [T8]a [T7]=T9T10:= T8a [T10]=xgoto B2B5T11:= T2x:=a [T11]T12:= T11T13:= T1T14:=a [T13]a [T12]=T14T15:= T13a [T15]=xB6

第11页：10.1概述（续）

10.1概述（续）

复写传播(一)后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:= T2x:=a[T2]T7:= T2T8:= T4T9:=a [T4]a [T2]=T9T10:= T4a [T4]=xgoto B2B5T11:= T2x:=a [T2]T12:= T2T13:= T1T14:=a [T1]a [T2]=T14T15:= T1a [T1]=xB6

第12页：10.1概述

10.1概述

复写传播(一)后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:= T2x:=a[T2]T7:= T2T8:= T4T9:=a [T4]a [T2]=T9T10:= T4a [T4]=xgoto B2B5T11:= T2x:=a [T2]T12:= T2T13:= T1T14:=a [T1]a [T2]=T14T15:= T1a [T1]=xB6

第13页：10.1概述（续）

10.1概述（续）

复写传播(二)后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:= T2x:=T3T7:= T2T8:= T4T9:=T5a [T2]=T5T10:= T4a [T4]= T3goto B2B5T11:= T2x:=T3T12:= T2T13:= T1T14:= va [T2]=vT15:= T1a [T1]= T3B6

第14页：10.1概述

10.1概述

删除无用赋值i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:= T2x:=T3T7:= T2T8:= T4T9:=T5a [T2]=T5T10:= T4a [T4]= T3goto B2B5T11:= T2x:=T3T12:= T2T13:= T1T14:= va [T2]=vT15:= T1a [T1]= T3B6

第15页：10.1概述（续）

10.1概述（续）

删除无用赋值后i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4a [T2]=T5a [T4]= T3goto B2B5a [T2]=va [T1]=T3B6

第16页：10.1概述

10.1概述

强度削弱i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4a [T2]=T5a [T4]= T3goto B2B5a [T2]=va [T1]=T3B6

第17页：10.1概述（续）

10.1概述（续）

强度削弱后i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1i:=i+1T2:= T2+4T3:=a[T2]if T3<v goto B2B2j:=j-1T4:= T4-4T5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4a [T2]=T5a [T4]= T3goto B2B5a [T2]=va [T1]=T3B6

第18页：10.1概述

10.1概述

删除归纳变量i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1i:=i+1T2:= T2+4T3:=a[T2]if T3<v goto B2B2j:=j-1T4:= T4-4T5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4a [T2]=T5a [T4]= T3goto B2B5a [T2]=va [T1]=T3B6

第19页：10.1概述（续）

10.1概述（续）

删除归纳变量后i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1T2:= T2+4T3:=a[T2]if T3<v goto B2B2T4:= T4-4T5:=a[T4]if T5>v goto B3B3if T2>=T4goto B6B4a [T2]=T5a [T4]= T3goto B2B5a [T2]=va [T1]=T3B6

第20页：10.1概述

10.1概述

中间代码程序段i:=m-1j:=nT1:=4*nv:=a[T1]B1i:=i+1T2:=4*iT3:=a[T2]if T3<v goto B2B2j:=j-1T4:=4*jT5:=a[T4]if T5>v goto B3B3if i>=j goto B6B4T6:=4*ix:=a [T6]T7:=4*iT8:=4*jT9:=a [T8]a [T7]=T9T10:= 4*ja [T10]=xgoto B2B5T11:=4*ix:=a [T11]T12:=4*iT13:=4*nT14:=a [T13]a [T12]=T14T15:= 4*na [T15]=xB6

第21页：10.1概述（续）

10.1概述（续）

删除归纳变量后i:=m-1j:=nT1:=4*nv:=a[T1]T2:=4*iT4:=4*jB1T2:= T2+4T3:=a[T2]if T3<v goto B2B2T4:= T4-4T5:=a[T4]if T5>v goto B3B3if T2>=T4goto B6B4a [T2]=T5a [T4]= T3goto B2B5a [T2]=va [T1]=T3B6

第22页：10.2局部优化

10.2局部优化

基本块

指程序中一顺序执行语句序列，其中只有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个语句。T1:=a*aT2:=a*bT3:=2*T2T4:=T1+T2T5:=b*bT6:=T4+T5

如果一条三地址语句为x

=y+z，则称对x定值并引用y和z。

第23页：10.2局部优化（续）

10.2局部优化（续）

• 局限于基本块范围内的优化称为基本块内的优化，或称局部优化。
• 在一个基本块内通常可以实行下面的优化:
• 删除公共子表达式
• 删除无用赋值
• 合并已知量
• 临时变量改名
• 交换语句的位置
• 代数变换

第24页：10.2局部优化

10.2局部优化

划分四元式程序为基本块的算法:1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。

第25页：10.2局部优化（续）

10.2局部优化（续）

划分四元式程序为基本块的算法:2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)之间的语句序列组成的。入口语句n……入口语句m

第26页：10.2局部优化

10.2局部优化

划分四元式程序为基本块的算法:2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)之间的语句序列组成的。入口语句n……入口语句m入口语句n……转移语句m

第27页：10.2局部优化（续）

10.2局部优化（续）

划分四元式程序为基本块的算法:2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。入口语句n……入口语句m入口语句n……转移语句m入口语句n……停语句m

第28页：10.2局部优化

10.2局部优化

划分四元式程序为基本块的算法:2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。3.凡未被纳入某一基本块中的语句，可以从程序中删除。

第29页：10.2局部优化（续）

10.2局部优化（续）

例：划分基本块(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。

第30页：10.2局部优化

10.2局部优化

例：划分基本块(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。

第31页：10.2局部优化（续）

10.2局部优化（续）

例：划分基本块(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。

第32页：10.2局部优化

10.2局部优化

例：划分基本块(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。

第33页：10.2局部优化（续）

10.2局部优化（续）

例：划分基本块(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。

第34页：10.2局部优化

10.2局部优化

例：划分基本块(1)read X(2)read Y(3)R:=X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。

第35页：优化措施

优化措施

合并已知量T1

=2…T2:=4*T1变换成T2:=8

临时变量改名T

=b+c其中T是一个临时变量名。把这个语句改成：S:=b+c

第36页：优化措施（续）

优化措施（续）

交换语句的位置T1

=b+cT2:=x+y

代数变换x

=x+0或x:=x*1x:=y**2变换成x:=y*y

第37页：每个流图以基本块为结点

每个流图以基本块为结点

• 每个流图以基本块为结点。如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点。如果在某个执行顺序中，基本块B2紧接在基本块B1之后执行，则从B1到B2有一条有向边。即，如果
• 有一个条件或无条件转移语句从B1的最后一条语句转移到B2的第一条语句；或者
• 在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句不是一个无条件转移语句。我们就说B1是B2的前驱，B2是B1的后继。

第38页：每个流图以基本块为结点（续）

每个流图以基本块为结点（续）

• =X mod Y(4)if R=0 goto (8)(5)X:=Y(6)Y:=R(7)goto (3)(8)write Y(9)halt(8)write Y(9) halt(5)X:=Y(6) Y:=R(7) goto (3)(3)R:=X mod Y(4) if R=0 goto (8)(1)read X(2) read YB1B2B3B4

第39页：10.2.2基本块的DAG表示

10.2.2基本块的DAG表示

前驱

ni是nj的前驱

后继

nj是ni的后继

环路

n1=nk

DAG

无环路有向图(DirectedAcyclic Graph)n1n2n3n4n1n2n3n4

• 用
• 有向图
• 有向边:ni
• nj
• 通路:n1
• n2, n2
• n3,... ,nk-1
• nk

第40页：7.1.2图表示法

7.1.2图表示法

• 图表示法
• DAG
• 抽象语法树
• 无循环有向图(Directed Acyclic Graph，简称DAG)
• 对表达式中的每个子表达式，DAG中都有一个结点
• 一个内部结点代表一个操作符，它的孩子代表操作数
• 在一个DAG中代表公共子表达式的结点具有多个父结点

第41页：7.1.2图表示法（续）

7.1.2图表示法（续）

• =b*(-c)+b*(-c)的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc

第42页：抽象语法树对应的代码

抽象语法树对应的代码

T1

=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5assigna+*buminusc抽象语法树*buminusc

第43页：DAG对应的代码

DAG对应的代码

T1

=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树对应的代码：T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5

第44页：DAG对应的代码（续）

DAG对应的代码（续）

• 表示该结点代表该变量或常数的值;
• 图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果;
• 图中各个结点上可能附加一个或多个标识符(称附加标识符)表示这些变量具有该结点所代表的值。

第45页：10.2.2基本块的DAG表示

10.2.2基本块的DAG表示

• 用
• 一个基本块，可用一个DAG来表示与各四元式相对应的DAG结点形式:四元式DAG图(0) 0型:A:=B(:=，B，-，A)n1AB

第46页：10.2.2基本块的DAG表示（续）

10.2.2基本块的DAG表示（续）

A

=op B(op，B，-，A)n1ABn2op(2) 2型:A:=B op C(op，B，C，A)n2ABn1opn3C

第47页：10.2.2基本块的DAG表示

10.2.2基本块的DAG表示

A

=B[C](=[]，B[C]，-，A)n2ABn1=[]n3C(4) 2型:if B rop C goto (s)(jrop，B，C，(s))n2(s)Bn1ropn3C

第48页：10.2.2基本块的DAG表示（续）

10.2.2基本块的DAG表示（续）

D[C]

=B([]=，B，-，D[C])(6) 0型:goto (s)(j，-，-，(s))(s)n1n2Bn1[]=n4Cn3D

第49页：10.2.2基本块的DAG表示

10.2.2基本块的DAG表示

假设DAG各结点信息将用某种适当的数据结构存放(如链表)。另设置一个标识符与结点的对应函数:

第50页：10.2.2基本块的DAG表示（续）

10.2.2基本块的DAG表示（续）

0，1，2型四元式的基本块的DAG构造算法对基本块中每一四元式，依次执行以下步骤:1.准备操作数的结点2.合并已知量3.删除公共子表达式4.删除无用赋值

第51页：1.准备操作数的结点

1.准备操作数的结点

• 如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点;
• 如果当前四元式是0型，则记NODE(B)的值为n，转4。
• 如果当前四元式是1型，则转2(1)
• 如果当前四元式是2型，则(i)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(ii)转2(2)。

第52页：1.准备操作数的结点（续）

1.准备操作数的结点（续）

• 叶结点则转2(3)；否则，转3(1)。(2)如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)；否则，转3(2)。(3)执行op B (即合并已知量)。令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P作标记的叶结点n。置NODE(P)=n，转4。(4)执行B op C (即合并已知量)。令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P作标记的叶结点n。置NODE(P)=n，转4。

第53页：1.准备操作数的结点

1.准备操作数的结点

• 其唯一后继为NODE(B)且标记为op(即公共子表达式)。如果没有，则构造该结点n，否则，把已有的结点作为它的结点并设该结点为n。转4。(2)检查DAG中是否已有一结点，其左后继为NODE(B)，右后继为NODE(C)，且标记为op(即公共子表达式)。如果没有，则构造该结点n，否则，把已有的结点作为它的结点并设该结点为n。转4。

第54页：1.准备操作数的结点（续）

1.准备操作数的结点（续）

• 则把A附加在结点n上并令NODE(A)=n;否则，先把A从NODE(A)结点上的附加标识符集中删除(注意，如果NODE(A)是叶结点，则其A标记部不删除)。把A附加到新结点n上并置NODE(A)=n。转处理下一四元式。

第55页：1.准备操作数的结点

1.准备操作数的结点

例10.4试构造以下基本块G的DAG(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=R-r(10)B:=T5*T6

第56页：1.准备操作数的结点（续）

1.准备操作数的结点（续）

(1)T0

=13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*B(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=R-r(10)B:=T5*T6T6

第57页：1.准备操作数的结点

1.准备操作数的结点

优化后的四元式(1)T0:=3.14(2)T1:=6.28(3)T3:=6.28(4)T2:=R+r(5)T4:=T2(6) A:=6.28*T2(7)T5:=A(8)T6:=R-r(9)B:=A*T6n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*BT6

第58页：1.准备操作数的结点（续）

1.准备操作数的结点（续）

优化后的四元式——若只有A和B是出基本块之后活跃的(1)T2:=R+r(2) A:=6.28*T2(3)T6:=R-r(4) B:=A*T6(1)S1:=R+r(2) A:=6.28*S1(3)S2:=R-r(4)B:=A*S2n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*BT6

第59页：1.准备操作数的结点

1.准备操作数的结点

• 在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。
• 在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是DAG各结点上的那些附加标识符。

第60页：10.3循环优化

10.3循环优化

• 对循环中的代码，可以实行：
• 代码外提
• 强度消弱
• 删除归纳变量(变换循环控制条件)
• 循环展开
• 循环合并

第61页：10.3.1代码外提

10.3.1代码外提

循环不变运算

对四元式A:=B op C,若B和C是常数，或者到达它们的B和C的定值点都在循环外。

• 所谓变量A在某点d的定值到达另一点u（或称变量A的定值点d到达另一点u），是指流图中从d有一通路到达u且该通路上没有A的其它定值。d: A:=B op C…u: D:=A op E
• 把循环不变运算提到循环体外。

第62页：10.3.1代码外提（续）

10.3.1代码外提（续）

入口结点循环L入口结点循环L前置结点

第63页：10.3.1代码外提

10.3.1代码外提

代码外提条件for I:=1 to 10 doA[I, 2*J] := A[I, 2*J] + 1

第64页：10.3.1代码外提（续）

10.3.1代码外提（续）

• =1(2)if I>10 goto (15)(3)T1=2*J(4)T2=10*I(5)T3= T2+ T1(6) T4=addr(A)-11(7) T5=2*J(8) T6=10*I(9)T7= T6+ T5(10) T8=addr(A)-11(11) T9= T8[T7](12) T4[T3]= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(1)I:=1(2)if I>10 goto (15)(4)T2=10*I(5)T3= T2+T1(8) T6=10*I(9)T7= T6+ T5(11) T9= T8[T7](12) T4[T3]= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(3)T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11B2’

第65页：10.3.1代码外提

10.3.1代码外提

• =1(2)if X<Y goto B3B1B2(3)I:=2(4) X:=X+1(5)Y:=Y-1(6) if Y<=20 goto B5(7)J:=IB3B4B5
• X=30, Y=25
• B1
• B2
• B4
• B2
• B4
• …
• B2
• B4
• B5
• J=1, I=1

第66页：10.3.1代码外提（续）

10.3.1代码外提（续）

代码外提条件

不变运算所在的结点是L所有出口结点的必经结点.

• =2(2)if X<Y goto B3B1B2(4)X:=X+1(5)Y:=Y-1(6) if Y<=20 goto B5(7)J:=IB3B4B5(1)I:=1B2’
• X=30, Y=25
• B1
• B2
• B4
• B2
• B4
• …
• B2
• B4
• B5
• J=2, I=2

第67页：10.3.1代码外提

10.3.1代码外提

=1(2‘)I

=3(2)if X<Y goto B3B1B2(3)I:=2(4) X:=X+1(5)Y:=Y-1(6) if Y<=20 goto B5(7)J:=IB3B4B5

• 考虑:B2
• B3
• B4
• B2
• B4
• B5
• I=3, J=3

第68页：10.3.1代码外提（续）

10.3.1代码外提（续）

代码外提条件

A在循环中其他地方未再定值,才能把循环不变运算A:=B op C外提;

• =3(2)if X<Y goto B3B1B2(3)I:=2(4) X:=X+1(5)Y:=Y-1(6) if Y<=20 goto B5(7)J:=IB3B4B5(1)I:=1B2’
• 考虑:B2
• B3
• B4
• B2
• B4
• B5
• I=2, J=2

第69页：10.3.1代码外提

10.3.1代码外提

• =1(2)if X<Y goto B3B1B2(3)A:=I+1(4) X:=X+1(5)I:=2(6)Y:=Y-1(7) if Y<=0 goto B5(8)J:=AB3B4B5
• B3
• B4
• B2
• B4
• B5

第70页：10.3.1代码外提（续）

10.3.1代码外提（续）

考虑

X=0, Y=2B2

S(A

=B OP C)外提条件:循环中所有A的引用点只有S中的A的定值才能到达。

• =2(2)if X<Y goto B3B1B2(3)A:=I+1(4) X:=X+1(6)Y:=Y-1(7) if Y<=20 goto B5(8)J:=AB3B4B5(1)I:=1B2’
• B3
• B4
• B2
• B4
• B5
• A=3, J=3

第71页：10.3.1代码外提

10.3.1代码外提

• 依次查看L中各基本块的每个四元式，如果它的每个运算对象或为常数，或者定值点在L外，则将次四元式标记为"不变运算";
• 重复第3步直至没有新的四元式被标记为"不变运算"为止;
• 依次查看尚未被标记为"不变运算"的四元式，如果它的每个运算对象或为常数，或定值点在L之外，或只有一个到达-定值点且该点上的四元式已被标记为"不变运算"，则把被查看的四元式标记为"不变运算"。

第72页：代码外提算法

代码外提算法

• 1.求出L的所有不变运算2.对每个不变运算s:A:=B op C或A:=opB或A:=B检查是否满足条件(1)或(2)(1)(i) s所在的结点是L所有出口结点的必经结点;(ii) A在L中其他地方未再定值;(iii) L中所有A的引用点只有s中的A的定值才能到达。

第73页：代码外提算法（续）

代码外提算法（续）

• 并且条件(1)的(ii)和(iii)成立。所谓A在离开L后不是活跃的是指，A在L的任何出口结点的后记结点入口处不是活跃的。3.按步骤1所找出的不变运算的次序，依次把符合条件2的条件(1)或(2)的不变运算s外提到L的前置结点中。但是，如果s的运算对象(B或C)是在L中定值的，那么，只有当这些定值四元式都已外提到前置结点中时，才能把s也外提到前置结点中。

第74页：10.3.2强度消弱

10.3.2强度消弱

• 把程序中执行时间较长的运算转换为执行时间较短的运算。

第75页：10.3.2强度消弱（续）

10.3.2强度消弱（续）

• =1(2)if I>10 goto (15)(4)T2=10*I(5)T3= T2+ T1(8) T6=10*I(9)T7= T6+ T5(11) T9= T8[T7](12) T4[T3]= T9+1(13) I:=I+1(14) goto B2B3B2B1(15)(3)T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11B2’(1)I:=1(2)if I>10 goto (15)(5)T3= T2+ T1(9)T7= T6+ T5(11) T9= T8[T7](12) T4[T3]= T9+1(13) I:=I+1(4‘)T2= T2+10(8’) T6= T6+10(14) goto B2B3B2B1(15)(3)T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11(4)T2=10*I(8) T6=10*IB2’

第76页：10.3.2强度消弱

10.3.2强度消弱

• =1(2)if I>10 goto (15)(5)T3= T2+ T1(9)T7= T6+ T5(11) T9= T8[T7](12) T4[T3]= T9+1(13) I:=I+1(4‘)T2= T2+10(8’) T6= T6+10(14) goto B2B3B2B1(15)(3)T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11(4)T2=10*I(8) T6=10*IB2’(1)I:=1(2)if I>10 goto (15)(11)T9= T8[T7](12) T4[T3]= T9+1(13) I:=I+1(4‘)T2= T2+10(8’) T6= T6+10(5‘)T3= T3+ 10(9‘)T7= T7+ 10(14) goto B2B3B2B1(15)(3)T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11(4)T2=10*I(8) T6=10*I(5)T3= T2+ T1(9)T7= T6+ T5B2’

第77页：10.3.2强度消弱（续）

10.3.2强度消弱（续）

• 强度消弱主要是对与归纳变量有线性关系的变量赋值进行；
• 经过强度消弱后，循环中可能出现一些新的无用赋值；
• 对于消弱下标变量地址计算的强度非常有效。

第78页：10.3.3删除归纳变量

10.3.3删除归纳变量

• 如果循环中对变量I只有唯一的形如I:=I
• C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。
• 如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为I的同一线性函数，也即J=C1*I
• C2，其中C1和C2都是循环不变量，则称J是归纳变量，并称它与I与族。一个基本归纳变量也是一归纳变量。

第79页：10.3.3删除归纳变量（续）

10.3.3删除归纳变量（续）

• =1(2)if I>10 goto (15)(11)T9= T8[T7](12) T4[T3]= T9+1(13) I:=I+1(4‘)T2= T2+10(8’) T6= T6+10(5‘)T3= T3+ 10(9‘)T7= T7+ 10(14) goto B2B3B2B1(15)(3)T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11(4)T2=10*I(8) T6=10*I(5)T3= T2+ T1(9)T7= T6+ T5B2’(1)I:=1(2)if T3>R goto (15)(11)T9= T8[T7](12) T4[T3]= T9+1(5‘)T3= T3+ 10(9‘)T7= T7+ 10(14) goto B2B3B2B1(15)(3)T1=2*J(6) T4=addr(A)-11(7) T5=2*J(10) T8=addr(A)-11(4)T2=10*I(8) T6=10*I(5)T3= T2+ T1(9)T7= T6+ T5(21) R=100+T1B2’

第80页：10.3.3删除归纳变量

10.3.3删除归纳变量

删除归纳变量是在强度削弱以后进行的。强度削弱和删除归纳变量的统一算法框架，其步骤如下：1.利用循环不变运算信息，找出循环中所有基本归纳变量。2.找出所有其它归纳变量A，并找出A与已知基本归纳变量X的同族线性函数关系FA(X)。3.对2中找出的每一归纳变量A，进行强度削弱。4.删除对归纳变量的无用赋值。

第81页：5.删除基本归纳变量

5.删除基本归纳变量

• 如果基本归纳变量B在循环出口之后不是活跃的，并且在循环中，除在其自身的递归赋值中被引用外，只在形如if B rop Y goto L中被引用，则可选取一与B同族的归纳变量M来替换B进行条件控制。最后删除循环中对B的递归赋值的代码。

第82页：5.删除基本归纳变量（续）

5.删除基本归纳变量（续）

• P306-1，2，3，4，5