编译原理第十章习题答案分析

编译原理电子教案第十章

优化·谢强·计算机科学与技术学院xieqiang@本章的主要内容2上一页下一页基本块的划分和流图的构建基本块的DAG表示及基于DAG的局部优化循环优化本章要求3上一页下一页知识点：优化的基本概念及方法、基本块及程序流图、

DAG及基于DAG的优化、循环优化熟练掌握：局部优化：基本块，流图，DAG优化。循环优化：代码外提，强度削弱，删除归纳变量。优化分类4上一页下一页按阶段分:与机器无关的优化---对中间代码进行依赖于机器的优化---对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优化优化工作数据流分析(data-flow

analysis)控制流分析(control-flowanalysis)变换(transformations)本章教学线索5上一页下一页概述优化技术简介局部优化循环优化1概述6上一页下一页优化的目的是为了获得更高效的代码，必须遵循以下原则：等价原则：优化后不能改变程序运行的结果有效原则：优化后所产生的目标代码运行时间更短、占用的存储空间更小合算原则：尽可能以较低的代价获取较好的优化效果。常用的优化技术：删除公共子表达式复写传播删除无用代码代码外提强度削弱删除归纳变量本章教学线索7上一页下一页概述优化技术简介局部优化循环优化2优化技术简介8上一页下一页a

=

10

*

5

+

6

-

b;优化前：_tmp0

=

10

;_tmp1

=

5

;_tmp2

=

_tmp0

*

_tmp1

;_tmp3

=

6

;_tmp4

=

_tmp2

+

_tmp3

;_tmp5

=

_tmp4

–

b;a

=

_tmp5

;优化后：_tmp0

=

56

;_tmp1

=

_tmp0

–

b

;a

=

_tmp1

;常数合并常数传播_tmp4

=

0

;f0

=

_tmp4

;_tmp5

=

1

;f1

=

_tmp5

;_tmp6

=

2

;i

=

_tmp6

;f0

=

0

;f1

=

1

;i

=

2

;优化9上一页下一页代数简化x+0

=

x0+x

=

xx*1

=

x1*x

=

x0/x

=

0x-0

=

xb

&&

true

=

bb

&&

false

=

falseb

||

true

=

trueb

||

false

=

bb

=

5

+

a

+

10

;优化前：_tmp0

=

5

;_tmp1

=

_tmp0

+

a

;_tmp2

=

_tmp1

+

10

;b

=

_tmp2

;优化后：_tmp0

=

15

;_tmp1

=

a

+

_tmp0

;b

=

_tmp1

;10上一页下一页b)

i/2=(int)(i*0.5)c)

0-1=-111上一页下一页降低运算强度a)

i*2

=

2*i

=

i+i

=

i<<2d)f*2

=

2.0

*

f

=

f

+

fe)

f/2.0

=

f*0.5c

=

tmp5

+

tmp4

;复写传播tmp2tmp3tmp4tmp5====tmp1tmp2tmp3tmp3;*;*tmp1;tmp2

;tmp3

=

tmp1

*

tmp1

;tmp5

=

tmp3

*

tmp1

;c

=

tmp5

+

tmp3

;12上一页下一页P:=0for

I:=1

to

20

doP:=P+A[I]*B[I]P:=0I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if

I<=20goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if

I<=20goto(3)优化13上一页下一页(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if

I<=20

goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3")T1:=T1+4(12)if

I<=20

goto(5)优化14上一页下一页(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3")T1:=T1+4(12)if

I<=20

goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3")T1:=T1+4(12)if

T1<=80

goto(5)优化15上一页下一页(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3")T1:=T1+4(12)if

T1<=80

goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3")T1:=T1+4(12)if

T1<=80

goto(5)优化16上一页下一页本章教学线索17上一页下一页概述优化技术简介局部优化基本块和流图基本块的DAG及其应用循环优化3局部优化18上一页下一页局部优化就是以程序的基本块为范围进行局部优化。3.1基本块和流图19上一页下一页基本块：程序中一顺序执行的语句序列，其中第一句为其唯一的入口，最后一句为其唯一的出口。划分四元式为基本块的算法：1）求四元式程序中各个基本块的入口语句：①程序的第一条语句能由条件转移语句或无条件转移语句转移到的语句紧跟在条件转移语句后面的语句②③对每一个入口语句，其基本块是由该入口语句到下一 个入口语句（不包括此入口语句）、或到一个转移语 句（包括此转移语句）、或到一个停语句(包括此停语 句）之间的语句序列组成。将未划入基本块的语句删除。例：p279：read

Xread

YR=X

mod

Y(4)

if

R

=

0

goto

(8)X

=

YY=

Rgoto

(3)write

Yhalt根据规则1)，可以得出（1）、（3）、（8）、（5）是入口语句，从而由规则2）可知：基本块为：（1）（2）、（3）（4）、（5）（6）（7）、（8）（9）。第一句条件或者无条件转移语句转移到的语句条件或者无条件转移语句转移到的语句紧跟在条件转移语句后面的语句20上一页下一页流图（控制流程图）：一个控制流程图是具有唯一首结点的有向图，表示成：G=（N，E，n0）其中，N是基本块集；n0是首结点，是含有第一条语句的基本块；E是有向边集。E的构成如下：基本块Bi和基本块Bj满足如下条件之一，则从Bi引一条有向边到Bj

。1）Bj紧跟在Bi之后，且Bi的出口语句不是goto语句（无条件）。2）Bi的出口语句是“[if]goto

L”（条件/无条件转移）语句，而L是Bj

的入L1：if

a<b

goto

L2goto

LnextL2：if

c<d

goto

L3goto

L4L3：t1

=

y

+

zx

=

t1goto

L1L4：t2

=

y

-

zx

=

t2goto

L1口语句，Bi是Bj的前驱结点。例：

L1：

if

a<b

goto

L2goto

Lnext21上一页下一页L2：

if

c<d

goto

L3goto

L4L3：

t1

=y+zx

=t1goto

L1L4：t2

=

y-zx

=t2

goto

L13.2基本块的DAG及其应用基本块DAG图的概念：图的叶子结点以一标识符或常数作为标志，表示该结点代表该变量或常数的值；图中的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果；图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。基本块DAG图的构造算法：（1）A

=

op

Bn1ABn1ABn2op假设代码形式为（0）A=B（2）A=B

op

C或A=B[C]DAG结点n1ABn3n2C22上一页下一页op算法步骤：1.如果NODE（B）无定义，则构造一标记为B的叶子结点并定义NODE（B）为这个结点；如果当前的代码是（0）型，则记NODE（B）的值为n，转4；如果是（1）型，则转2（1）；如果当前代码是（2）型，则：（i）如果NODE（C）无定义，则构造一标记为C的叶结点，并定义NODE（C）为这个结点；转2（2）。2.（1）如果NODE(B)是标记为常数的叶结点,则转2(3),否则转3(1)。若NODE(B)和NODE(C)都是标记为常数的叶结点,则转2(4),否则转3(2)。执行opB(合并已知量),令得到的新常数为p。如果NODE（B）是处理当前代码时新构造出来的结点，则删除它，如果NODE(p)无定义，则构造一用p做标记的叶结点n。置NODE(p)=n，转4。执行B

op

C(合并已知量),令得到的新常数为p，如果NODE（B）是处理当前代码时新构造出来的结点，则删除它，如果NODE（p）无定义，则构造一用p做标记的叶结点。置NODE（p）=

n，转4；23上一页下一页3.(1)检查DAG中是否已有一结点，其唯一后继为NODE(B)且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n。转4。24上一页下一页（2）检查DAG中是否已有一结点，其左后继为NODE(B)，右后继为NODE（C），且标为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。4.如果NODE(A)无定义，则把A附加在结点n上并令NODE（A）=n；否则先把A从NODE(A)结点上的附加标记符集中删除（如果NODE(A)是叶子结点，则其标记A不删除），把A附加到新结点n上并令NODE(A)=n。转处理下一条代码。DAG的应用：根据DAG，重写代码，即可实现局部优化。例：构造以下基本块的DAG：（1）T0=3.14（2）T1=2*3.14T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-r（10）B=T5*T6n6n8T0-T2,T4n5+A，T5

BBT6n7n1n2

T1,T3

n3n43.14

6.28

Rr(1)

T0=3.14

(2)

T1=6.28(6)

A=6.28*T2

(7)

T5=A(3)T3=6.28

(4)T2=R+r(8)

T6=R-r

(9)

B=A*T6(5)

T4=T2**25上一页下一页本章教学线索26上一页下一页概述优化技术简介局部优化循环优化代码外提强度削弱删除归纳变量4循环优化27上一页下一页循环：程序中可能反复执行的代码序列，比如高级语言中的for语句、while语句、do-until语句等都是循环语句由于循环语句常常要反复执行，因此对其优化，将大大提高目标代码的执行效率。4.1代码外提28上一页下一页在循环中如果有形如A=B

op

C的代码，而B和C或者是

常数、或者其定值点在循环外，则可以将其提到循环外。方法：在循环入口点建立一新的结点（循环前置结点）（基本块），将循环中可以外提的代码放在其中。注意：（1）当把一不变运算外提到循环前置结点时，要求该不变运算所在的结点是循环所有出口结点的必经结点；（2）当把A=B

op

C外提时，要求循环中A的所有引用点都是而且仅仅是这个定值所能达到的。（3）对不变运算A=B

op

C要求循环中其他地方不能再有

A的定值入口结点循环L入口结点循环

L前置结点外提29上一页下一页代码外提的总体结构：（1）

I=1B2（2）

if

X<Y

goto

B430上一页下一页B3（3）

I=2(4)X=X+1B4（5）

Y=Y-1(6)if

x<20

goto

B2B5（7）

J=II=2是循环不变运算，是否能够外提？B3不是循环出口结点B4的必经之路，如果外提，则循环结束后，J的值一定是2，而在原来循环中，J的值可能是1。B1结论：当把一不变运算外提到循环前置结点时，要求该不变算所在的结点是循环所有出口结点的必经结点。如果循环中I的所有引用点只是B3中I的定值所能到达

I在循环中不再有其它定值点，并且出循环后不会再引用该I的值（即在循环外的循环后继结点入口，I不是活跃的），那么即使B3不是B4的必经结点，还是可以将

I=2外提。31上一页下一页（3）I=2（4）X=X+1（5）

Y=Y-1(6)if

x<20

goto

B2（7）

J=I（1）

I=1B2I=3（2）

if

X<Y

goto

B432上一页下一页B3B4B5结论：I=3也不能外提，对不变运算A=B

op

C要求循环中其他地方不能再有A的定值。B1I=3所在结点B2是循环出口点的必经结点，能否外提？A=I+1X=X+1I=2Y=Y-1if

Y<0

goto

B2J=AB333上一页下一页B4B5B4中的I=2为循环不变运算，并且为循环出口的必经之路，并且没有再被定值是否能够外提？B1I=1B2if

X<Y

goto

B4不能外提，否则改变J的值。结论：当把循环不变运算A=B

op

C外提时，要求循环中A的所有引用点都是而且仅仅是这个定值所能到达的。查找循环L中的不变运算的算法：依次查看L中各个基本块的每个代码，如果它的每个运算对象或为常数，或者定值点在L外，则将其标记为“不变运算”；重复（3）直到没有新的代码标记为“不变运算”；依次查看尚未被标记为“不变运算”的代码，如果它的每个运算对象或为常数，或定值点在L之外，或者只有一个到达一定值点且该点上的代码已经标记为“不变运算”，则把它标记为“不变运算”。代码外提算法：求出循环L中所有不变运算；对步骤（1）所求出的每一个“不变运算”s：A=B

op

C（或

A=B），检查它是否满足以下条件①或②：①（i）s所在的结点是L的所有出口结点的必经结点A在L中其它地方未再定值；L中所有A的引用点只有s中的A的定值才能达到。②A在离开L后不再活跃，并且条件①的（ii）和（iii）成立。按步骤（1）所找到的不变运算的顺序，依次把符合条件①或②的不变运算s外提到L的前置结点。但是如果s的运算对象（B或C）是在L中定值的，那么只有当这些定值代码都已经提到前置结点中时，才能将s提到前置结点中。34上一页下一页4.2强度削弱35上一页下一页强度削弱：就是将循环中执行时间长的运算等价替换为执行时间较短的运算。一般对于乘法运算可以替换为在循环前置结点进行一次乘法运算和循环中递归赋值的加法运算。（1）如果循环中有I的递归赋值I=I±C（C为循环不变量），并且循环中T的赋值运算可划归为T=K

*

I±C1，（C1为循环不变量），那么T的赋值运算可以进行强度削弱。（2）强度削弱后，循环中可能出现一些新无用的赋值，一般为临时变量，可以删除；(1)

I

=1(15)B1B2’(3)

T1=2*J(6)T4=addr(A)-11(7)T5=2*I(10)T8=addr(A)-11B2(2)

if

I>10

goto

(15)B3(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)gotoB2(1)

I

=1(3)

T1=2*J(15)B1B2’(6)T4=addr(A)-11(7)T5=2*I(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*IB2(2)

if

I>10

goto

(15)B3(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)gotoB2B1(1)

I

=1(3)

T1=2*J(6)T4=addr(A)-11(7)T5=2*I(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*I(5)T3=T2+T1(9)T7=T6+T5(15)36上一页下一页B2’B2(2)

if

I>10

goto

(15)B3(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)gotoB24.3删除归纳变量37上一页下一页基本归纳变量：如果循环中对变量I只有唯一的形如：I=I±C的赋值，且C为循环不变量，则称I为循环中的基本归纳变量