编译器代码优化

PAGE2

inta[25][25],…a[i][j]=…a[i][j]=a[i][j]= 一.优化所涉及的源程序的范围—基本块内优化；——5—目标代码生成前的优化；5BeforeBeforeAfterX+2*Beforee+fe+

Afterx=e+f 3.LoopinvariantcodeBeforeb=for(i=0;i<3;i++)d[i]=2*b+1;

Afterb=z=2*b+for(i=0;i<3;i++)=zBeforeBefore AfterJump-to-jumpBeforeifelsegotoJ1;J1:gotoJ2;

AfterifgotoDeadcodeBeforecharif(c>300)a=1;a=2

Aftera=FunctionBefore AfterintCheck(int{return}voidmain({if(check(y))

voidmain({if(y>10}}Looptransformation-simple Csourcecodeinttable[100];step=1;for(i=0;i<100;i+=step)table[i]=0;beforei=L1:t1=i*4;=if(i<100)goto

afteri=t1=i*L1:table[t1]=0t1=t1+4;if(i<100)gotoLooptransformation-dynamicCsourcestep=for(i=0;i<MAX;i+=step)=beforeoptimizationstep=step_table[1];i=0;L1:t1=i*table[t1]=0;i=i+step;if(i<MAX)goto

afteri=step=t1=i*t2=step*2;L1:table[t1]=0;t1=t1+t2;i=i+step;if(i<MAX)gotoLooptransformation-composedCsourceinttable[0]=table[11]=table[0]=table[11]=table[22]=table[99]=beforei=0;j=t1=i*10;L1:t2=t1+t3=t2* /*addresstable[t3]=i;i=i+1;t1=t1+j=j+if(j<10)goto

i=0;j=t1=1*t2=t1+j;t3=t2*Repeat10table[t3]=i;i=i+1;t3=t3+PAGE20根据基本块的结构特点，它的入口语句⑵由条件转移语句或无条件转移语句转⑶紧跟在条件转移或无条件转移后面的所属的基本块。即：⑴由该入口语句直到下一个入口语句（不包含下一个入口语句）之间的所有语句构成一⑵由该入口语句到下一转移语句（含该转移语句）之间的所有语句构成一个基本块；或到程序中的停止或暂停语句（包含该停止或暂 234567PAGE24 Step2:对求出的每一个入口语句构造相应Step3:凡不属于某一基本块中的语句，皆G=(N,E,n0N：是流图的所有的结点组成的集合。流图设有结点i到结点k(或说从结点i到结点k由有向边Ei相连)可表示为：iik①基本块k在流图中的位置紧跟在基本块i之后，且基本块i的出口语句不是无条igotos)if...goto(s)(s)k 234567 ①read②read③R=x/ ④ifR=0gotox=⑤x=x=⑥y=⑦goto⑧write ⑨DAG（DirectedAcyclicGraph）设G是由若干结点构成的有向图，从结点ni到结点nj的有向边用ni→nj表示。①若存在有向边序列ni1→ni2→…→nim，则称结ni1与结点nim之间存在一条路径，或称ni1与nim是连通的。路径上有向边的数目为路径的长度；②如果存在一条路径，其长度≥2，且该路径起每个基本块都可以用一个DAG表示，称为基本块①叶结点用标识符或常量作为其惟一的标记，②内部结点用运算符标记，同时也表示计算的③各结点上可以附加一个或多个标识符，附加2828例8.3–

+ba,d 01 23 41

常见四元式与DAG结点对应关系P226 A=BopC (op,B,C,A) ifBropCgotos(jrop,B,C,(s)Aop op,B, A B, AB31 31 输入：一个基本块iiDAG：[1].[2].[3]. [4]. 3，则令：NODE(B)=n，即叶子结2，转[2]1，如果NODE(C)无定义，则建立PAGE34NODE(B)是标记为常数的叶子结点，则转②如果NODE(B)和NODE(C)都是标记为常数的叶opB(即常量合并)，设得到的新常数为P。如果NODE(B)是处理当前四元式时新建立的结点，则删除它。如果NODE(P)无定义，则建立一标记为P的叶子结点，令NODE(P)=n，转[4]。④执行BopC(即常量合并)，设得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新建立的结点，则删除它。如果NODE(P义，则建立一标记为P的叶子结点，令NODE(P)=n①检查DAG中是否有一结点，其唯一后继为NODE(BOP如果没有，则建立该结点，并令NODE(OP)=n；否则，为了叙述方便，也认为NODE(OP)=n。转DAG中是否有一结点，其左后继为，右后继为NODE(C)且标记为OP(即查找公共子表达式)。如果没有，则建立该结点，并令NODE(OP)=n；否则，为了叙述方便，也认为如果NODE(A)无定义，则把A附加在否则，先把A从NODE(A)结点的附加标识符集中删除(如果NODE(A)是叶子结点，则其标记A不删除)，把A附加在结点n的右边，并令NODE(A)=n。 2*R+rT1*T22*R+rT3*T4

P228例PAGE39⑴T0=⑵T1=2*⑶T2=⑷A=T1* n5+ ⑴T0=⑵T1=2*⑷⑸A=T1⑷⑸A=T1*B=⑹T3=2*⑺T4=⑻T5=T3*⑼T6=R-⑽B=T5*

6 86578657–234 PAGE44

定义8.3n0出发，到达nj的任何一条通路都必经过ni，则称ni是nj的必经结点，记作niDOMnj。 自反性：aDOMa传递性：如果aDOMb，bDOMc，则有：aDOMc。反对称性：若有aDOMb，bDOMa，则有：a=b。 D(1)=D(2)=D(3)={1,2,D(4)={1,2,D(5)={1,2,4,D(6)={1,2,4,D(7)={1,2,4,定义8.5（回边设a→b是流图G中一条有向边，如果bDOMa，则称a→b是流图G中的一条回边。记作<a,b>。例8.5流图中存在有向边6→6，7→4和4→2。 D(6)={1,2,4,6则6D(7)={1,2,4,7则4D(4)={1,2,4则24849若<n,d>是一回边，则由结点d、结点nnd的所有<6,6>loop={6<7,4>loop={4,5,6,7<4,2>loop={2,3,4,5,6,7PAGE51.实施

.循环优化

采集一.为了进行循环优化和全局优化，编译程PAGE54点 x=a*b+c; readx;x获得值的中间代码的位置d，称为x的定值点。例如di：xdj：read

x的中间代码的位置d，称为变x的引用点。dji dki设有流图G，变量AGdpd通路到达p且该通路上没有对变量A进行 <A>—对变量A的引用A—对变量AAp:

变量Ad的定值到达点

= = = PAGE61定义8.6（ud链P引用了变量A的值，则把GPA为A在引用点P的引用-定值链（即ud链）。 即某变量A在点d的引用的ud链，是AdAd注销掉 在程序中对某变量A在点P进行定值，如果存在一条从P开始的通路，其中引用了APA在点P是活跃的，否则称变量A在点P是死亡的。定义8.7（du链假设在程序中某点P对一个变量A定A的引用点的全体A在定值点P的定值-引用链（即du 63A63d-du={d1,d2 ={dj+1,={di,dj+1,

tttt={dj,dk ={dk+2,dj,dkPAGE67 out[B]=gen[B]∪(in[B]–kill[B] 后（每个基本块Bi的有关信息利in[B 前（每个基本块Bi的有关信息利PAGE71IN(BiBi入口点OUT(BiBi出口点后，所有变GEN(Bi)：BiBi出口之后所达Bi结束点的定值）。

IN(B)= P∈P(B) 12345674512763725①如果某定值点d在IN(B)中，而且被d定值的变量在B中未被重新定值，则d也在OUT(B)中；②如果定值点dGEN(B)中，则它一定在而对于IN(B)，则可知，某定值点d到达基本 for(i=1;i<=N;i++{IN[Bi]=Φ; /*IN[Bi]和OUT[Bi]的迭代初值}change=―真 change：相继2次迭代所得的IN[Bi]之值不等则为―真，whilechange 需要继续迭代；若相等，则迭代过程结束，值为― change=―for(i=1;i<=N;i++ NEWIN=∪out[P]; /*P∈Pred(Bi)。求B的前驱块的OUT的并*/if(NEWIN!=IN[Bi] /*NEWIN记录每次迭代后IN[Bi]的新值 =―真”; OUT[Bi]=GEN[Bi]∪(IN[Bi]-}}}}}若在基本块B中，某变量A的引用点u之前有A的定值点dd点A的定值能到达u，则Auud{d}；若在基本块B中，某变量A的引用点u之前无A的定值点，则包含在IN[B]中的全部A的定值点均可到达点uIN[B]中的这些A的定值点组成Auud链。x+yPP算x+y，并且在最后一个x+y到P之间未对x或y定值，则表达式x+y在点P可用。xyB2中没有对变量iB2中没有对变量iB2中对变量i定值B2中对变量i定值Out[B]=in[B]–kill[B] in(B)=∩ 设in(B0)= 7979INL(B)=OUTL(B)–DEFL(B)∪USEL(B) OUTL(B)=∪ OUTL(B)B的出口点PAGE81

∴ 代码外提就是将循环中的不变运算提到这里所指的不变运算，是指与循环执行次数无关的运算，或不受循环控制变量影响84例如，设循环L84 A= I=1；L1:B=J+C=B+A=C+ifI=100gotoL2I=I+1gotoL2:PAGE87<B,B>loop={B，B B=J+1JJ B2查找循环中的不变运算；（X1）实施代码外提；（X2）依次查看L如果其中的每个运算对象为常数或定值点在L之外（根据ud链判断），将该语句标记为依次查看未被标记为“不变运算”的语句，如果其运算对象为常数或定值点在L外，或只有一个到达-定值点且该点上的语句已标记为“不变运算”，则将被查看的 SABopC或A=opB或AB，①（iii）L中所有AS②A在离开L后不再是活跃的，且条件①的在L的任何出口结点的后继结点（指不属于LL的前置结点中。但若S中的运算对象（B或C）是在L中定值的，那么，只有当这些定值语句都提到前置结点中后，才可把S也外提。

ifu<vgotoB3

L={B2,B3,B4v=v-ifv<=20goto

B5，A **LA不止一次定值情况下，i阻挡将A=3外B5时，A

A= ifu<vgotoA=ifv<=20gotoj= ***L中所有A的引用点只有语句S中A的定值

ifu<vgoto B4时，A的

k=AA=2;v=v-ifv<=20goto= I=I=T=K*IK1T=T±

98II=I±C式的赋值，其中CI如果I是循环中一个基本归纳变量，变量J在循环中的定值总可化为I的同一线性函数的形式：J=C1*I±C2，其中：C1、C2是循环不变量，则称J是归纳变量，称J与I同族。 PAGE102 (W1：查找归纳变量step2：寻找L中只有一个定值的K（归纳K=J*C;K=C*J;K=J/C;K=J±C;J是基本归纳变量，KJ族中；K、J同族}J是归纳变量，J∈K族，K、J、I同族 LJ的惟一定值和对K的定值间没有对I的定值；**找出一族归纳变量，可以变换计算归纳变量的指令（*→+） (