第七章 中间代码优化 优化方法概述 基本块划分 常量表达式优化 公共表达式优化 循环不变式外提.

Presentation on theme: "第七章 中间代码优化 优化方法概述 基本块划分 常量表达式优化 公共表达式优化 循环不变式外提."— Presentation transcript:

1 第七章 中间代码优化 优化方法概述 基本块划分 常量表达式优化 公共表达式优化 循环不变式外提

2 1 优化方法概述 优化的目标：提高程序的质量,尤其是程序的运行速度。 优化的要求： 1.优化要保证程序的正确性；
1 优化方法概述 优化的目标：提高程序的质量,尤其是程序的运行速度。 优化的要求： 1.优化要保证程序的正确性； 2.优化后要使程序的运行速度有数量级上的提高； 3.优化要适度。 优化的对象：主要针对循环内下标变量地址的计算.

3 中间代码优化的分类 源程序阶段的优化： 用户基于候选算法的时间复杂度和空间复杂度的比较而作出选择。 编译阶段的优化
1.编译前端的中间代码级的优化： (1) 局部优化:基本块内的优化。 ①常表达式优化（合并常数项） ②公共表达式优化（消除重复操作） (2)非局部优化:涉及的范围比基本块要大。 ①循环上的优化:循环不变表达式外提; ②全局优化； 2.编译后端的目标代码级的优化：有效而合理地使用机器资源，或者减少目标程序指令个数来提高执行效率。

4 2 基本块划分 基本块是指程序的一组顺序执行的语句序列，其中只有一个出口和一个入口。 入口：基本块的第一条语句；
出口：基本块的最后一条语句； 语句1 语句1 语句1 语句2 语句2 语句2 语句n 语句n 语句n

5 基本块划分 对于一个基本块而言，执行时只能从它的入口进入，从出口退出；
一个基本块内部的语句要么全执行，要么全不执行，不能执行其中的一部分，不能在中间转出，也不能从中间转入。 基本块可以基于源代码、中间代码和目标代码。

6 标号性中间代码：也称定位性四元式，起到一个定位的作用不产生跳转指令。例如：
( LABEL , — , — , L ) ( ENTRY , Label , Size , Level ) ( WHILE , — , — , —) ( ENDIF , — , — , —)

7 转移性中间代码：在生成目标代码时一定产生跳转指令的四元式。例如：
( JMP , — , — , L ) ( ENDPROC , — , — , — ) ( ENDFUNC , — , — , — ) ( THEN , E , — , — ) ( ELSE , — , — , —) ( DO , E , — , —) ( ENDWHILE , — , — , — )

8 基于四元式中间代码基本块的划分原则 初始四元式为第一个基本块的入口；
遇到转移性中间代码时，结束当前基本块，并把该转移性中间代码作为当前基本块的出口，下一条代码作为新基本块的入口； 遇到标号性代码结束当前基本块，代码本身作为新基本块的入口； 遇到（ASSIG, A, - ，X）时，如果X为引用型变量时结束当前块，并作为该块的出口。(*X=…) 第4条是为了避免对X指向的地址变量进行错误的局部优化决定。如a=10; X=&a ,*p=20, 这时的a不是不变表达式，但如何判断a是否改变困难。

9 基本块划分的例子 设有源程序如下： (ASSIGN,1,_, y ) (LABEL,_ ,_ ,L) (AND，A, B, t0 )
(THEN,t0 ,-,-) (ASSIG, 0, _,x ) (ELSE,-,-,-) (ASSIG,0, _,y ) (ENDIF,-,-,-) (ADDI, x, 1, t1) (ASSIG,t1,_, x ) (SUBI y, 1, t2 ) (ASSIGN, t2, _,y) (WHILE,-,-,-) (ADDI, x, y,t3 ) (GT, t3, 0, t4 ) (DO,t4,-,-) (SUBI, x, 1,t5 ) (ASSIG, t5, x ) (ENDWHILE,-,-,-) (ASSIGN, 0,_ ,Z ) 设有源程序如下： y := 1 ; L: if A and B then x := 0 else y := 0 ; x := x + 1 ; y := y – 1 ; while x + y > 0 do x := x - 1 ; z := 0 ; 注：x,y为非引用型整数类型形参。

10 (ASSIG,1,-,y) (SUBI,y,1,t2) B1 (LABEL,-,-,L) (ASSIG,t2,-,y)
(AND,A,B,t0) (THEN,t0,-,-) (ASSIG,0,-,x) (ELSE,-,-,-) (ASSIG,0,-,y) (ENDIF,-,-,-) (ADDI,x,1,t1) (ASSIG,t1,-,x) (SUBI,y,1,t2) (ASSIG,t2,-,y) (WHILE,-,-,-) (ADDI,x,y,t3) (GT,t3,0,t4) (DO,t4,-,-) (SUBI,x,1,t5) (ASSIG,t5,-,x) (ENDWHILE,-,-,-) (ASSIG,0,-,z) B1 B2 B6 基本块划分的例子 B3 B4 B7 B5 B8

11 程序流图 B1 B2 B3 B4 B5 B6 B7 B8 程序流图是以基本块为节点的有向图。
B1:(ASSIGN,1,_, y ) B6:(WHILE, -, -, -) B2:(LABEL,_ ,_ ,L) (ADDI, x,y,t3 ) (AND，A, B, t0 ) (GT, t3, 0, t4 ) (THEN, t0 , - ,- ) (DO, t4, -, - ) B3:(ASSIGN, 0, _,x ) B7:(SUBI, x, 1,t5 ) (ELSE, -, -,- ) (ASSIGN, t5, x ) B4:(ASSIG,0, _,y ) (ENDWHILE, -, -, -) B5: (ENDIF, - ,- ,-) B8 :( ASSIGN, 0 ,_ , z ) (ADDI, x, 1, t1) (ASSIGN,t1, _ , x ) (SUBI ,y, 1, t2 ) (ASSIGN, t2, _,y) B2 B3 B4 B5 B6 程序流图是以基本块为节点的有向图。 B7 B8

12 3 常表达式节省 常表达式：任何时候都取固定常数值的表达式。 优化范围通常为基本块。 处理思想：针对每个基本块，如果一个四元式的两
个分量的值已知，则由编译器将其值计 算出来，并用所求的值替换原来的运算结 果变量,并删掉相应的中间代码。

13 例:假设有下列语句： m:=10; a := m + 10 ; b := a + m ; c := a + b – d ; 则上列语句可优化如下： a := 20 ; b := 30 ; c := 50 – d ;

14 常表达式节省 原理： 常量定值表ConstDef：表元素为二元组(Var,Val)。如果在ConstDef中有元素（V，c),表示变量此时一定取常数值c，在V被更改之前出现的V均可替换成c。

15 常表达式节省 基本块上常量表达式的局部优化算法： 基本块入口置ConstDef为空； 读当前四元式；
对当前四元式的分量利用ConstDef表进行值代换得新四元式newtuple； 如果新多元式newtuple 形如（，A, B，t): 若A和B是常数，则计算AB的值v，并将（t,v）填入ConsDef表。删除当前四元式。 如果新多元式newtuple形如（ASSIG，A, -, B）: 如果A是常数，则把（B,A）填入ConsDef表，若已有B项， 只需修改其值；否则(A为非常数)从ConsDef中删除B的登记 项。 重复②～⑤直到基本块结束。

16 常表达式局部优化的例子 优化后中间代码 (ASSIG,10,-,x) (ASSIG,11,-,y) (ASSIG,a,-,x)
ConDef 中间代码 优化后中间代码 (ASSIG,10,-,x) (ASSIG,11,-,y) (ASSIG,a,-,x) (ASSIG,16,-,z) 源程序 x := 10 y := x+1; x:=a; z:=y+5; x 10 (ASSIG,10,-,x) (ADDI,x,1,t1) (ASSIG,t1,-,y) (ASSIG,a,-,x) (ADDI,y,5,t2) (ASSIG,t2,-,z) t1 11 10 11 y 11 t2 16 11 z 16 16