sun编译原理第7章代码优化(第22-23讲).ppt

2019/8/5,信息学院 孙丽云,1,7.1 优化概述,源程序经过词法分析、语法分析、语义分析等阶段的编译工作，得到与源程序功能等价的中间代码。但是，由于这种中间代码是“机械生成”的，必然存在效率不高，有冗余代码的现象，还需进行代码的优化。 代码优化的含义是：对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。 代码优化的目的是：提高目标代码的质量。,2019/8/5,信息学院 孙丽云,2,t1 = i * 5 ; t2 = t1 + 6 ; t3 = i * 5 ; t4 = b/t3 ; t5 = t2-t4; a=t5,t1 = i * 5 ; t2 = t1 + 6 ; t3 = t1 ; t4 = b/t3 ; t5 = t2-t4; a=t5,局部优化技术, 删除公共子表达式,a = i * 5 + 6 b/(i*5);,2019/8/5,信息学院 孙丽云,3,t1 = 56 ; t2 = t1 b ; a = t2 ;, 常数合并,a = 10 * 5 + 6 - b;,t1 = 10 * 5 ; t2 = t1 + 6 ; t3 = t2 - b ; a = t3 ;,2019/8/5,信息学院 孙丽云,4,t4 = 0 ; f0 = t4; t5 = 1 ; f1 = t5; t6 = 2 ; i = t6 ;,f0 = 0 ; f1 = 1 ; i = 2 ;, 常数传播,2019/8/5,信息学院 孙丽云,5,x+0 = x 0+x = x x*1 = x 1*x = x 0/x = 0 x-0 = x,b & true = b b & false = false b | true = true b | false = b, 代数简化,2019/8/5,信息学院 孙丽云,6,i*2 = 2*i = i+i = i1 （“”为C语言中的移位运算符，表示左移一位） b) i/2 = (int)(i*0.5) c) 0-1 = -1 d) f*2 = 2.0 * f = f + f e) f/2.0 = f*0.5, 降低运算强度,2019/8/5,信息学院 孙丽云,7,基本块：是指程序中顺序执行的语句序列。,基本块内的语句要么全执行，要么全不执行，而不能只执行一部分。 基本块只有一个入口和一个出口，只能从入口进入，出口退出，不存在转入、分支等操作。,局部优化基本块内的优化,例：下面的三地址语句序列组成了一个基本块。 T1=a*a T2=T1+a T3=5+T2,为了叙述方便，本章将四元式写成更为直观的三地址代码形式。,2019/8/5,信息学院 孙丽云,8,基本块的入口可能是下述3种情况之一： (1)程序的第一个语句； (2)转移的目标语句； (3)条件语句之后的第一个语句。,基本块的出口可能是下述3种情况之一： (1)下一个入口语句的前导语句； (2)转移语句； (3)停语句。, 基本块的入口,2019/8/5,信息学院 孙丽云,9, 划分基本块的算法,1. 求基本块的入口语句； 2. 求基本块的出口语句； 3. 凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，把它们删除。,2019/8/5,信息学院 孙丽云,10,例：对下列语句划分基本块 (1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt,解：划分成四个基本块B1，B2，B3，B4,B=C,BC,基本块的入口： (1)程序的第一个语句； (2)转移的目标语句； (3)条件语句之后的第一个语句。,基本块的出口： (1)下一个入口语句的前导语句； (2)转移语句； (3)停语句。,2019/8/5,信息学院 孙丽云,11, 练习,1、将下面程序划分为基本块并作出其程序流图： read(A,B) F=1 C=A*A D=B*B if (CD) goto L1 E=A*A F=F+1 E=E+F write(E) halt,L1: E=B*B F=F+2 E=E+F write(E) if (E100) goto L2 halt L2: F=F-1 goto L1,19 F=F+1,2019/8/5,信息学院 孙丽云,12, 思考,有语句如下： while(A | C （1）求其四元式序列； （2）对四元式序列划分基本块且画出程序流图。,2019/8/5,信息学院 孙丽云,13, 基本块的DAG表示及其应用,DAG是一种有向无环图，常用来对基本块进行优化。基本块内一般可实行3种优化：合并已知量、删除无用赋值、删除公共子表达式（删除多余运算）。 利用DAG进行基本块优化的基本思想： 首先顺序对一个基本块内的所有四元式构造成一个DAG，接着按构造结点的次序将DAG还原成四元式序列。 构造DAG的同时已做了局部优化，所以最后得到的四元式序列已经得到了优化。,2019/8/5,信息学院 孙丽云,14,基本块的DAG是在结点上带有如下标记的DAG： 图的叶结点（无后继的结点）：以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。 图的内部结点（有后继的结点）：以运算符作为标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。 图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。, 基本块的DAG表示及其应用,2019/8/5,信息学院 孙丽云,15,四元式,DAG结点,0型：A=B,2型：A=B op C,1型：A=op B, 四元式按其对应结点的后继结点个数的分类,图中ni是构造DAG过程中各结点的编号，各结点下面的符号（运算符、标识符或常数）是各结点的标记，各结点右边的标识符是结点上的附加标识符。, 仅含0，1，2型四元式的基本块的DAG构造算法,首先，DAG为空。 对基本块的每一四元式，依次执行： 1如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点； 若当前四元式是0型,则记NODE(B)的值为n,转4。 若当前四元式是1型，则转2(1)。 若当前四元式是2型，则： (I) 如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C) 为这个结点； (II) 转2 (2),0型：A=B,2型：A=B op C,1型：A=op B,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)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。 （4）执行B op C（即合并已知量），令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。,第2步的(1)(2)用于判断结点是否为常数，(3)(4)是对常数的处理。第2步的作用是实现合并已知量。,3（1）检查DAG中是否已有一结点，其唯一后继为NODE(B)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。 （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。转处理下一四元式。 5. 可由DAG重新生成原基本块的一个优化的代码序列。,第3步的作用是检查公共子表达式。,第4步的作用是删除无用赋值。,2019/8/5,信息学院 孙丽云,19,例： (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, 基本块的DAG的构造,2019/8/5,信息学院 孙丽云,20,例： (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,2019/8/5,信息学院 孙丽云,21,例： (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,2019/8/5,信息学院 孙丽云,22,例： (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,2019/8/5,信息学院 孙丽云,23,例： (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,2019/8/5,信息学院 孙丽云,24,A,B,*,T2,+,T0 T1,3.14 6.28 R r,(e),n2,n5,n3,n1,n4,n6,例： (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,2019/8/5,信息学院 孙丽云,25,例： (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,2019/8/5,信息学院 孙丽云,26,A,B,*,T2,T4,+,T0 T1,T3,3.14 6.28 R,r,(g),n2,n5,n3,n1,n4,n6,例： (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,2019/8/5,信息学院 孙丽云,27,例： (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,2019/8/5,信息学院 孙丽云,28,A,B,T5,*,T2,T4 T6,+,-,T0 T1,T3,3.14 6.28 R r,n2,n5,n3,n7,n1,n4,n6,例： (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,2019/8/5,信息学院 孙丽云,29,例： (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,3.14 6.28 R r,2019/8/5,信息学院 孙丽云,30,(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*T6, 利用DAG进行基本块的优化处理,基本思想：按照构造DAG结点的顺序，对每一个结点写出其相应的四元式表示。,T0 T1,T3,3.14 6.28 R r,2019/8/5,信息学院 孙丽云,31, 举例,对于基本块P: S0=2 S1=3/S0 S2=T-C S3=T+C R=S0/S3 H=R S4=3/S1 S5=T+C S6=S4/S5 H=S6*S2 请应用DAG对该基本块进行优化。,优化后的中间代码为： S0=2 S4=2 S1=1.5 S2=T-C S3=T+C S5=S3 R=2/S3 S6=R H=R*S2,2019/