《编译原理课程教案》第7章代码优化_图文

《《编译原理课程教案》第7章代码优化_图文》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第7章代码优化_图文（56页珍藏版）》请在金锄头文库上搜索。

1、代码优化第十章 本章要求 主要内容：代码优化的主要功能，局 部优化、全局优化和循环优化的相关概 念，各种优化技术 重点掌握：代码优化技术，基本块、 流图、DAG的概念，必经结点、回边、 循环的概念，各种优化技术。代码优 化所地 位和作 用：7.1 概述实际上很多地方可以对代码的执行效率进行改进 ，主要讲对中间代码的优化 代码优化：对程序进行等价变换，使得从变换后的程 序出发，能够生成更有效的目标代码。优化分类 按阶段分:与机器无关的优化-对中间代码进行依赖于机器的优化-对目标代码进行 根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:

2、大范围的优化 优化的原则 等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 宗旨： 获得较好性能的代码（时间，空间） 等价 意图、结果之间要权衡中间代码优化技术 优化工作数据流分析(control-flow analysis)控制流分析(data-flow analysis) 变换(transformations)快速排序程序 void quicksort(int m,int n) int i,j, v,x; if (nv);if (i=j) break;x=ai;ai=aj;aj=x; x=ai;ai=an;an=x; quicks

3、ort(m,j);quicksort(i+ 1,n); (1) i :=m 1 (2) j :=n (3) T1:=4 * n (4) v := aT1 (5) i := i + 1 (6) T2 := 4 * i (7) T3 := aT2 (8) if T3 v goto (9) (13) if i = j goto (23) (14) T6 := 4 * i (15) x := aT6(16) T7 := 4 * i (17) T8 := 4 * j (18) T9 := aT8 (19) aT7 := T9 (20) T10 := 4 * j (21) aT10 := x (22) g

4、oto (5) (23) T11 := 4 * j (24) x := aT11 (25) T12 := 4 * i (26) T13 := 4 * n (27) T14 := aT13 (28) aT12 := T14 (29) T15 := 4 * n (30) aT15 := x中间代码7.2 基本块的优化 基本块：是指程序中一顺序执行的语句序列， 其中只有一个入口语句和一个出口语句，入口是 其第一个语句，出口是其最后一个语句 如果x:=y+z 则称对x定值, 引用y和z 在一个基本块内的一个名字, 在程序中的某个给 定点是活跃的，是指如果在程序中它的值在该点 之后被引用.入口语句： 1

5、程序的第一个语句；或者， 2条件转移语句或无条件转移语句的转移目标 语句（此处的转移语句包括各种控制的转向，如call， return，end，stop等） ；或者 3紧跟在条件转移语句后面的语句。执行： 对于一个基本块，执行时只能从其入口进入， 从其出口退出划分基本块的算法求出四元式程序之中各个基本块的入口语句 对每一入口语句，构造其所属的基本块。它 是由该语句到下一入口语句（不包括下一入口 语句），或到一转移语句（包括该转移语句） ，或到一停语句（包括该停语句）之间的语句 序列组成的。 凡未被纳入某一基本块的语句，都是程序中 控制流程无法到达的语句，因而也是不会被执 行到的语句，可以把它们

6、删除。 一般把过程调用语句作为一个单独的基本块*(1)read x(2)read yB1*(3)r:=x mod y(4)if r=0 goto (8)B2*(5)x:=y(6)y:=r(7)goto(3)B3*(8)write y(9)haltB4例： *(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)halt 流图：有向图。将控制流的信息增加到基本块的集合 上来表示一个程序。 流图以基本块为单位。如果按顺序执行，就画一条有 向边。 基本块间的关系:( 前驱

7、,后继)B1是B2的前驱，B2是B1的后继: 有一个条件或 无条件转移语句从B1的最后一条语句转移到B2的第 一条语句；或者在程序的序列中，B2紧接在B1的后面，并且B1 的最后一条语句不是一个无条件转移语句。*(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)halt练习f0 = 0f1 = 1if mv);if (i=j) break;x=ai;ai=aj;aj=x; x=ai;ai=an;an=x; quicksort(m,j);quicksort(i+1

8、,n) ; 各种代码优化技术：快速排序程序 的中间代码i=m-1; j=n; v=an; while(1) do i=i+1; while(aiv);if (i=j) break; x=ai;ai=aj;aj= x; x=ai;ai=an;an=x;优化技术1删除公共子表达式 如果表达式E已经在前面计算过，并在计算之 后E的值没有改变，则称该表达式为公共子表达 式。可以避免重复计算。 T6:=4*i x=aT6 T7:=4*i T8:=4*j T9=aT8 aT7:=T9 T10:=4*j aT10:=x goto B2T6:=4*i x=aT6 T7:=T6 T8:=4*j T9=aT8 a

9、T7:=T9 T10:=T8 aT10:=x goto B24*i，4*j 重复计算 在更大的 范围内删除 4*i,4*j的计 算，得到：优化技术2复写传播T6:=T2 x=T3 T7:=T2 T8:=T4 T9=T5 aT2:=T5 T10:=T4 aT4:=T3 goto B2T6:=T2 x=aT6 T7:=T6 T8:=T4 T9=aT8 aT7:=T9 T10:=T8 aT10:=x goto B2T6:=T2， x=aT6，之间 没有改变T6,因 此，可以直接写 x=aT2在B2中 T3:=aT2因此 ，x=T3优化技术3删除无用代码aT2:=T5 aT4:=T3 goto B2T

10、6:=T2 x=T3 T7:=T2 T8:=T4 T9=T5 aT2:=T5 T10:=T4 aT4:=T3 goto B2某些变量的赋值 无用，在后面的 程序中不再有用aT2:=v aT1:=T3B5B6优化技术4对程序进行代数恒等 变换（降低运算强度）a) i*2 = 2*i = i+i = iv goto B3T4=T4-4 T5=aT4 if T5v goto B3B3J每次减1后再 做乘4操作改为先赋值 后，T4的计 算用减法运 算T4=4*j优化技术7删除归纳变量 当进行强度削弱后 ，B4中i,j的比较可以 使用T2,T4If T2=T4 goto B6基本块的DAG表示及其应用D

11、AG Directed Acyclic Graph 有向无环路图 基本块的DAG是在结点上带有标记的DAG DAG表示了基本块的计算过程 叶结点表示标识符或常数的值，以标识符或常数作 为标记 内部结点以运算符作为标记，表示运算结果 边表示了操作间的前驱和后继的关系 每个结点：附加标识符标记，可以是一个或多个标 识符都具有该结点代表的值用DAG进行基本块的优化(0)x := y (1)x := op y (2)x := y op z 基本块的DAG构造算法:首先，DAG为空。 对基本块的每一四元式，依次执行1，2，3，4步： 1. 如果NODE(B)无定义，则构造一标记为B的叶结点并定 义NOD

12、E(B)为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1)。如果当前四元式是2型，则：(1) 如果NODE(C)无定义，则构造一标记为C的叶结点 并定义NODE(C) 为这个结点；(2) 转2 (2)2. (1) 如果NODE(B)是标记为常数的叶结点 ，则转2(3)， 否则转3(1)。(2) 如果NODE(B)和NODE(C)都是标记为常数的叶结点 ，则转2(4)，否则转3(2)。(3) 执行op B（即合并已知量），令得到的新常数为P。 如果NODE(B)是处理当前四元式时新构造出来的结点， 则删除它。如果NODE(P)无定义，则构造一用

13、P做标记的 叶结点n。置NODE(P)=n，转4。(4) 执行B op C（即合并已知量），令得到的新常数为P 。如果NODE(B)或NODE(C)是处理当前四元式时新构造 出来的结点，则删除它。如果NODE(P)无定义，则构造 一用P做标记的叶结点n。置NODE(P)=n，转4。 3.(1) 检查DAG中是否已有一结点，其唯一后继为 NODE(B)，且标记为op（即找公共子表达式）。如果没 有，则构造该结点n，否则就把已有的结点作为它的结点 并设该结点为n，转4。 (2) 检查中DAG中是否已有一结点，其左后继为 NODE(B)，其右后继为NODE(C)，且标记为op（即找公 共子表达式）。

14、如果没有，则构造该结点n，否则就把已 有的结点作为它的结点并设该结点为n，转4。 4.如果NODE(A)无定义，则把A附加在结点n上并令 NODE(A)=n；否则先把A从NODE(A)结点上附加标识符 集中删除（注意，如果NODE(A)是叶结点，则其标记A不 删除），把A附加到新结点n上并令NODE(A)=n。转处理 下一四元式。 这样，就可由DAG重新生成原基本块的一个优化的代 码序列。例：求下列基 本块的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

15、:=T3*T4 (9) T6:=R-r (10) B:=T5*T6 (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 (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 (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