4 公共表达式局部优化 设有下列语句： t := b * c ; e := b * c + b * c ;

Presentation on theme: "4 公共表达式局部优化 设有下列语句： t := b * c ; e := b * c + b * c ;"— Presentation transcript:

1 4 公共表达式局部优化 设有下列语句： t := b * c ; e := b * c + b * c ;
d := b * c + d ; 优化后，可得到下列语句： t := b * c ; e :=t + t ; c := t + 10 ; d := b * c + d ;

2 等价的四元式 设(ω1,A1,B1,t1)和(ω2,A2,B2,t2)是非赋值型运算类四元式，若 ω1＝ω2,并且 A1 和 A2,B1 和 B2 的值彼此相等,则称这两个四元式等价。即如果四元式的操作码和两个运算分量的值彼此相等，就说两个四元式等价。 公共表达式（可节省的公共代码, ECC:Erasable Common Code ） 如果在基本块中出现多个等价的四元式，则除了第一个外其它的等价的四元式称为第一个四元式的公共表达式,或可节省的公共代码。

3 公共表达式的值编码优化方法 值编码优化方法的主要思想:公共表达式优化的关键是判断两个分量值是否相等。其主要思想是对中间代码中出现的每个分量确定一个值编码，使得具有相同值编码的分量等价。 μ( x ) 表示任意运算分量x的值编码； NewVN为新值编码产生器，首次产生1，以后每次递增1 。 把 (μ( A ) ,μ( B ),μ( t ) ) 叫作 ( ω , A , B , t ) 的影像码, (ω ,μ( A ) ,μ( B ),μ( t ) ) 为编码四元式； 优化前 t := b * c ; c := b * c + b * c ; d := b * c + d ; 优化后： c := t + t ;

4 基于值编码的ECC优化用到三张表： 值编码表ValuNum ：存放变量（或常数）及其值编码； 可用表达式代码表UsableExpr ：存放基本块中的可用于匹配的表达式编码四元式； 临时变量等价表PAIR ：存放等价的临时变量偶对：(ti,tj)表示ti和tj是等价的，需用ti替换tj;

5 1. (*,b,c,t1) 2. (*,b,c,t2) 3. (+,t1,t2,t3) 4. (:=,t3,-,a)
实例1： a:=b*c+b*c;d:=b; e:=d*c+b*c; 1. (*,b,c,t1) 2. (*,b,c,t2) 3. (+,t1,t2,t3) 4. (:=,t3,-,a) 5. (:=,b,-,d) 6. (*,d,c,t4) 7. (*,b,c,t5) 8. (+t4,t5,t6) 9. (:=,t6,-,e) ValuNum t1 1. (*,b,c,t1) 2. (+,t1,t1,t3) 3. (:=,t3,-,a) 4. (:=,b,-,d) 5. (:=,t3,-,e) (b,1) (c,2) (t1,3) (t3,4) (a,4) (d,1) (e,4) UsableExpr (*,1,2,3) 1. (*,b,c,t1) 3. (+,t1,t2,t3) (+,3,3,4) PAIR t1 t1 (t1,t2) (t1,t4) (t1,t5) (t3,t6) t3

6 基于值编码的公共表达式节省算法 从基本块的第一条四元式开始 临时等价变量表PAIR替换, (ti,tj)需用ti替换tj。
对四元式(ω,A,B,t)中运算分量A,B查值编码表进行替换，新出现的运算分量进行新值编码，生成编码四元式。 遇到运算型四元式，在可用表达式表UsableExpr中查与当前编码四元式运算符、运算分量都相同的，若有则说明当前四元式为ECC，删去当前四元式，把结果临时变量填入等价表PAIR。 遇到赋值(=,a,-,b), b编码赋值为a的编码。 首先我们从基本块第一条四元式开始，来看看怎么做。 1、等价名的替换，看看四元式中有没有等价，每一个要做之前都要先做等价名的替换 2、我要为四元式中的变量或者是常量进行编码，这个编码过程和前面是一样的。每一个xx、xx、xx获得了一个编码，就要把他们的编码值填到编码表中，比方说他是从1 2 3往后填，a=1 b=2 t=3. 3、进行编码之后我们就生成了一个编码四元式，前面的运算符不变，但是运算分量和运算结果我们都是用编码来代替的，比方说刚才的就变成了（*，1,2,3） 4、如果编码四元式是一个运算型的四元式，我们就需要从当前的编码四元式开始往前查，查什么呢？查运算符和他相同、运算分量编码和他相同的四元式，如果要是找到了，就意味着当前这个四元式是可以被节省的，我们就找到了一个等价的公共子表达式，如果找不到就算了，如果找到了就意味着当前四元式可以被节省，删去，要把等价的名字填入等价表，哪两个是等价名？就是两个四元式的结果部分，把这两个名字填到等价表里，这就算做完了。然后我们再看下面的四元式，一直扫描完基本块。

7 a:=b*c+b*c; d:=b; e:=d*c+b*c;
实例1： a:=b*c+b*c; d:=b; e:=d*c+b*c; 序号 中间代码 映像 a b c d e t1 t2 t3 t4 t5 t6 等价表 优化后 1 *,b,c,t1 123 2 3 不变 *,b,c,t2 (t1,t2) 节省 +,t1,t2,t3 334 4 +,t1,t1,t3 =,t3,-,a 5 =,b,-,d 6 *,d,c,t4 (t1,t4) 7 *,b,c,t5 (t1,t5) 8 +,t4,t5,t6 (t3,t6) 9 =,t6,-,e =,t3,-,e

8 5 循环不变式外提优化 循环不变式:如果一个表达式E在一个循环中不改变其值，则称它为该循环的不变表达式。
循环不变式外提：将循环不变式提到循环外面进行. i:=1; t:=x*y; while i<=1000 do begin a[i]:=t; i:=i+1 end; i:=1; while i<=1000 do begin a[i]:= x*y; i:=i+1 end;

9 循环不变式外提的关键 识别循环结构(循环入口，循环体，循环出口)； 检查循环体中哪些变量的值被改变过；
根据这个结果来看哪些表达式是不变的表达式； 建立变量定值表，将循环体中值被改变的变量都填到表里，若某运算型四元式中两个运算分量都不出现在这个表里，就说明其值不发生改变，可以进行外提。

10 循环的识别：识别循环的入口、重复体、出口部分。 识别方法：基于程序文本，基于程序流图。
(WHILE , — , — , — ) E 的中间代码 基于程序文本:不需要什么开销；， 基于程序图的识别却需要很大的开销，但其优点是不管是用什么的语句写成的，只要程序图中出现环路即可识别出循环来。 ( DO , E . FORM , — , — ) S的中间代码 (ENDWHILE, — , — , — )

11 安全性: 不可外提类 1. 除法表达式不能外提(除零溢出) 设有如下循环语句： while E do
安全性: 不可外提类 1. 除法表达式不能外提(除零溢出) 设有如下循环语句： while E do if y=0 then x:=y; else x:= a/y; 假设a/y是不变表达式，若外提: t:=a/y; if y=0 then x:=y; else x:=t; 2. 赋值表达式不能外提( 既使赋值操作的左部和右部都是循环不变式):因为不一定执行该循环。

12 外提策略： 凡是循环不变式都外提 只外提一定被执行的循环不变式

13 循环不变式外提算法 对循环体四元式进行第一遍扫描，把循环内被定义的变量填到变量信息表LoopDef ，即若它是一个运算型四元式(ω1,A1,B1,t1)，则把t1填到表中，若为赋值型四元式(=，a，-，b)则把b填入表中； 循环不变式外提为第二遍扫描，每遇到一个运算型四元式(ω1,A1,B1,t1)，若A1、B1都不在变量信息表中，则将其提到循环体外，同时在变量定值表中删去t1，把t1从本层LoopDef表移到外层LoopDef表；删除原代码 ( ω , A , B , t ) ； 1对循环体进行第一遍扫描，把有定值的变量都找到填到表里，首先从循环体的第一条四元式做起，若他是一个运算型的四元式，%，a b t 就把t填到表里，遇到赋值型时=，a，-，x把x填到变量定值表里。我们从头到尾一条条的扫描就把所需要的信息找出来了。 2循环不变式外提，一条条扫描，遇到一个运算型四元式，看他的两个运算分量是否出现在定值表中，如果都没出现，就是一个不变表达式，就把他提到循环体的外面，我们要把表达式运算结果的变量t从变量定值表中删除掉，然后继续扫描。

14 外提实例1 优化前四元式序列： i:=1 while i<=100 do begin z:=i*k*5 a:=2*k+2*k*2
(ASSIG, 1, ─ , i) (WHILE, —，—，—) (LE, i, 100, t1) (DO, t1, —， —) (MULTI, i, k, t2) (MULTI, t2, 5, t3) (ASSIG, t3, ─ , z) (MULTI, 2, k, t4) (MULTI, 2, k, t5) (MULTI, t5, 2, t6) (ADDI, t4, t6, t7) (ASSIG, t7, ─, a) (ADDI, i, 1,t8) (ASSIG, t8, ─, i) (ENDWHILE, —，—，—) i:=1 while i<=100 do begin z:=i*k*5 a:=2*k+2*k*2 i:=i+1; end t4 LoopDef ={t1, t2, t3, z, t4, t5, t6, t7, a,t8 ,i}

15 循环优化前四元式序列： LoopDef={t1, t2, t3, z, t4, t6, t7, a,t8 ,i}
(ASSIG, 1, ─ , i) (WHILE,-，-，-) (LE, i, 100, t1) (DO, t1, -，-) (MULTI, i, k, t2) (MULTI, t2, 5, t3) (ASSIG, t3,- , z) (MULTI, 2, k, t4) (MULTI, t4, 2, t6) (ADDI, t4, t6, t7) (ASSIG, t7, ─, a) (ADDI, i, 1,t8) (ASSIG, t8, ─, i) (ENDWHILE,-，-，-) LoopDef={t1, t2, t3, z, t4, t6, t7, a,t8 ,i}

16 循环优化后四元式序列： i:=1 t7 while i<=100 do begin z:=i*k*5 a:=2*k+2*k*2
(ASSIG, 1, ─ , i) (MULTI, 2, k, t4) (MULTI, t4, 2, t6) (ADDI, t4, t6, t7) (WHILE,-，-，-) (LE, i, 100, t1) (DO, t1, —， —) (MULTI, i, k, t2) (MULTI, t2, 5, t3) (ASSIG, t3, ─ , z) (ASSIG, t7, ─, a) (ADDI, i, 1,t8) (ASSIG, t8, ─, i) (ENDWHILE,，-，-) i:=1 while i<=100 do begin z:=i*k*5 a:=2*k+2*k*2 i:=i+1; end t7 循环优化前四元式序列： (ASSIG, 1, ─ , i) (WHILE, -，-，-) (LE, i, 100, t1) (DO, t1, —， —) (MULTI, i, k, t2) (MULTI, t2, 5, t3) (ASSIG, t3, ─ , z) (MULTI, 2, k, t4) (MULTI, t4, 2, t6) (ADDI, t4, t6, t7) (ASSIG, t7, ─, a) (ADDI, i, 1,t8) (ASSIG, t8, ─, i) (ENDWHILE, -，-，-) t7

17 外提实例2 例2:已知:a:array[1..10][1..1000] of integer;设有如下循环语句： j:=1
while j<=1000 do begin a[i][j]:=0; j:=j+1; end; ( SUBI, i , 1, t1) ( MULTI , t1 ,S1,t2 ) ( AADD , a , t2 , t3) ( SUBI, j, 1, t4) ( MULTI , t4 , S2,t5 ) ( AADD , t3, t5, t6 ) 注：S1=1000*sizeof(T)=1000 S2=sizeof(T)=1

18 优化前的四元式序列： (ASSIG, 1, ─, j) (WHILE, ─, ─, ─) (LE, j, 1000, t1)
(DO, t1, ─, ─) (SUBI, i, 1, t2) (MULTI, t2, 1000, t3) (AADD, a, t3, t4) (SUBI, j, 1, t5) (MULTI, t5, 1, t6) (AADD, t4, t6, t7) (ASSIG, 0, ─, t7) (ADDI, j, 1, t8) (ASSIG, t8, ─, j) (ENDWHILE, ─, ─, ─) LoopDef={t1, t2, t3, t4, t5, t6, t7,t8,j} 优化后的四元式序列： (ASSIG, 1, ─, j) (SUBI, i, 1, t2) (MULTI, t2, 1000, t3) (AADD, a, t3, t4) (WHILE, ─, ─, ─) (LE, j, 1000, t1) (DO, t1, ─, ─) (SUBI, j, 1, t5) (MULTI, t5, 1, t6) (AADD, t4, t6, t7) (ASSIG, 0, ─, t7) (ADDI, j, 1, t8) (ASSIG, t8, ─, j) (ENDWHILE, ─, ─, ─) LoopDef={t1, t5, t6, t7,t8} 已知:a:array[1..10][ ] of integer; j:=1 while j<=1000 do begin a[i][j]:=0; j:=j+1; end;

19 6 其它各类优化介绍 1. 消减（降低）运算强度 消减运算强度的意思是：用强度低的运算(执行时间较短的运算)等价地代替强度高的运算。
例如:for j:=1 to 100 do a[j]:=3*j+10; 可优化为： m:=13; for j:=1 to 100 do begin a[j]:=m; m:=m+3; end 乘法运算强度一般比加法运算强度高， 因此可以用加法运算代替乘法运算。 如果乘法运算不在循环内， 那么其效益并不大， 因此都在循环内进行这种优化。设有循环语句： 因此可以用加法运算代替乘法运算。如果乘法运算不在循环内，那么其效益并不大，因此都在循环内进行这种优化。设有循环语句： 其它消减运算强度方法： a) i*2 = 2*i = i+i = i<<1 b) i/2 = (int)(i*0.5) c) 0-1 = -1

20 2. 复写传播 复写传播优化是把形如a:=b的复写型赋值语句删除掉，其中a和b都是变量。如果此后a和b都不变，则很显然a:=b可以删除的，但是要把以后的a都换成b。 假设有下列语句： a:=b; c:=a+1; d:=a+c; a:=…… ; 经复写传播优化后，得到下列语句： c:=b+1; d:=b+c; a:=…… ;

21 3. 无用代码消除 复写传播的特例是无用代码消除。假设有赋值语句 a := E ，但此后没有 a 的引用，那么该语句显然是无用的代码，这些代码在复写传播优化时自然被删除掉。 foo(x) { int i; i = x+10; x=25+x*5; }

22 4.代数简化 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

23 LoopDef={t3,t6,t7,a,t8,k,t9,t11,t12,t13,j}
例：对下列代码进行优化，其中 A：array[1..100] of integer (: = , 0 , _，a) (+, a, 1, t1) (*, t1, 5, t2) (:=, t2,_, j) (WHILE, _, _, _) (<, j, 100, t3) (Do, t3, _, _) (-,3, 1, t4) (*, t4, 1, t5) ([+], A, t5, t6) (+, a, t6, t7) (:=, t7, _, a) (<, a, 10, t8) (THEN, t8, _, _) (:=, 0, _, k) (ELSE, _, _, _ ) (*, x, y, t9) (*, x, y, t10) (/, t10, 5, t11) (+, t9, t11, t12) (:=, t12, _, k) (ENDIF, _, _, _) (+, j, 1, t13) (:=, t13, _, j) (ENDWHILE, _, _, _) a:=0; j:=(a+1)*5; while j<100 do begin a:=a+A[3]; if a<10 then k:=0; else k:=x*y+x*y/5; j:=j+1; end 5 t9 2 LoopDef={t3,t6,t7,a,t8,k,t9,t11,t12,t13,j}

24 优化后 (: = , 0 , _，a) (:=,5,_, j) (AADD, A, 2, t6) (*, x, y, t9)
(/, t9, 5, t11) (+, t9, t11, t12) (WHILE, _, _, _) (<, j, 100, t3) (Do, t3, _, _) (+, a, t6, t7) (:=, t7, _, a) (<, a, 10, t8) (THEN, t8, _, _) (:=, 0, _, k) (ELSE, _, _, _ ) (:=, t12, _, k) (ENDIF, _, _, _) (+, j, 1, t13) (:=, t13, _, j) (ENDWHILE, _, _, _) a:=0; j:=(a+1)*5; while j<100 do begin a:=a+A[3]; if a<10 then k:=0; else k:=x*y+x*y/5; j:=j+1; end

25 作业 P152 5