第6章-中间代码优化1.ppt

首先定义四个基本集合: IN[B] : 代表到达基本块 B 入口点时的各变量的所有定值点集; OUT[B]:代表到达基本块 B 出口点时的各变量的所有定值点集; GEN[B]:表示 B 中所定值的且到达 B 之后的定值点集; KILL[B]: 表示属于 B 外的定值点,而这些定值点所定值的变量在 B中又被重新定值 这几个集合满足如下方程: OUT[B]=(IN[B] - KILL(B)) ∪ GEN[B] IN[B] = OUT[p1] ∪ OUT[p2] ∪...... ∪ OUT[pk] p1 , p2...... pk 为B的前趋结点. 该方程即为到达——定值方程,求解该方程,得到IN[B] . 2求 ud[ A] 算法如下: 若 B 中,变量 A 的引用点 u 之前有 A 的定值点 d,且到达 u ,则 ud[ A] = { d }; 否则 ud[ A] = { di | di ∈IN[B] 且 di为A的定值点}. 这样,可以求出每个变量在引用点 u 的定值状况. 四 循环的几种基本优化 下面介绍三种循环优化: 代码外提,强度削弱,删除归纳变量. 一 代码外提 定义: 对于循环中的语句 A:= B op C, 若 B 及 C 均为常量,或者为 循环中未改变的变量, 那么每次循环 A的值都一样,称A:= B op C 为不变运算. 对于不变运算,有可能把 A:= B op C 放到循环前,具体做法是: a) 建立一前置结点; b) 循环入口结点(唯一的) 为前置结点的唯一后继; c) 循环外流向入口结点的有向边,改为流向前置结点; d) 把循环中可以外提的不变运算放在前置结点中. 见下图: * * * 局部优化 循环优化 优化目的: 提高运行速度, 减少存储空间. 第6章 中间代码优化 内容 : 第一节 优化概述 右面为 for 循环的中间代码: S:=0; for I:=1 to 20 do S:=S+A[I]*B[I] 对该段中间代码,可以进行 如下优化: 1 删除多余运算 见(3),(6)两四元式的 4*I, (6) 可以改写为: T4:=T1, 从而减少了一次乘法. 参见下页四元式表 (1) S:=0 (2) I:=1 (3) T1:=4*I (4) T2:=addr(A)-4 (5) T3:=T2[T1] (6) T4:=4*I (7) T5:=addr(B)-4 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) S:=S+T7 (11) I:= I+1 (12) if I=20 goto(3) (1) S:=0 (2) I:=1 (3) T1:=4*I (4) T2:=addr(A)-4 (5) T3:=T2[T1] (6) T4:=T1 (7) T5:=addr(B)-4 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) S:=S+T7 (11) I:= I+1 (12) if I=20 goto(3) 2代码外提 (4)与(7)每次循环其值都 不变,称为循环不变量.可以放 到循环前,减少循环中的运算. 参见下页四元式表 (1) S:=0 (2) I:=1 (4) T2:=addr(A)-4 (7) T5:=addr(B)-4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) S:=S+T7 (11) I:= I+1 (12) if I=20 goto(3) 3强度削弱 由于每次循环 I 都增加 1, 因此, T1递增 4 , 可把 (3) 改为 T1:=T1+4 ,放在(11)之后,并在 循环前对 I 赋初值 T1:=4*I. (12)改为 goto (5). 参见下页四元式表 (1) S:=0 (2) I:=1 (4) T2:=addr(A)-4 (7) T5:=addr(B)-4 (3) T1:=4*I (5) T3:=T2[T1] (6) T4:=T1 (8) T6:=T5[T4] (9) T7:=T3*T6 (10) S:=S+T7 (11) I:= I+1 (3’) T1:=T1+4 (12) if I=20 goto(