编译原理PPT课件第六章中间代码优化

1 局部优化 循环优化 优化目的: 提高运行速度, 减少存储空间.第六章 中间代码优化内容 :第一节 优化概述 2 右面为循环的中间代码:对该段中间代码,可以进行如下优化:1 删除多余运算 见(3),(6)两四元式的 4*I,(6) 可以改写为: T4:=T1, 从而减少了一次乘法.参见下页四元式表(1) PROD:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=4*I(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(12) if I=20 goto(3) 3 (1) PROD:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=T1(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(12) if I代码外提 (4)与(7)每次循环其值都不变,称为循环不变量.可以放到循环前,减少循环中的运算.参见下页四元式表 4 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4*I(5) T3:=T2T1(6) T4:=T1(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(12) if I强度削弱 由于每次循环 I 都增加 1,因此, T1递增 4 , 可把 (3) 改为T1:=T1+4 ,放在(11)之后,并在循环前对 I 赋初值 T1:=4*I.(12)改为 goto (5).参见下页四元式表 5 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4*I(5) T3:=T2T1(6) T4:=T1(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(3) T1:=T1+4(12) if I变换控制条件 由于 I 只用作循环控制, 而 T1=4*I ,因此, 可用 T1 替换 I , I=20 等价于 T1=80,把(12)改为 if T1=80 goto(5)这样, 可以删掉无用的 I .参见下页四元式表 6 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4*I(5) T3:=T2T1(6) T4:=T1(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(3) T1:=T1+4(12) if T1合并已知量 由于(3)中的 I 在 (2)赋值后仍然为 1,因此可改为:T1:=46 复写 (6)中 T1 复制到 T4,而(6)到(8)之间没有改变T1 和 T4, 因此(8) 可以改为: T6:=T5T1 ,从而使(6)式无用.参见下页四元式表 7 (1) PROD:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4(5) T3:=T2T1(6) T4:=T1(8) T6:=T5T1(9) T7:=T3*T6(10) PROD:=PROD+T7(3) T1:=T1+4(12) if T1删除无用赋值 (2) 和 (6) 两四元式为无用四元式,可以删除. 最终优化后,得到下页四元式表 8 (1) PROD:=0(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4(5) T3:=T2T1(8) T6:=T5T1(9) T7:=T3*T6(10) PROD:=PROD+T7(3) T1:=T1+4(12) if T1=80 goto(5)(1) PROD:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=4*I(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) PROD:=PROD+T7(11) I:= I+1(12) if I 定义: 基本块是一顺序执行的中间代码序列,仅包含一个入口 四元式 和一个出口四元式,第一条四元式为入口四元式,最后 一条四元式为出口四元式.中间部分不含转移四元式.2 基本块的划分 给定一四元式程序,可以通过如下算法,划分基本块: 10基本块划分算法:1) 求四元式程序中所有基本入口四元式,包括: a) 程序的第一条四元式; b) 转移语句转移到的四元式; c) 条件语句之后的第一条四元式.2) 对每一入口四元式,构造一个基本块: 从该入口四元式到下一入口四元式之前的一条四元式, 或到一转移语句,或到一停止语句之间的四元式序列 组成.3) 凡未纳入这些基本块的四元式,为无用四元式,可以删除. 11示例:设四元式程序如下:(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基本入口四元式包括: (1) 程序第一条四元式 (3) 转移语句转移到的四元式 (5) 条件语句之后的第一条四元式 (8) 转移语句转移到的四元式由此可以得到四个基本块.(见下页) 12 (8) write (Y)(9) halt(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) B1B2B3B4 13二 基本块内的优化 基本块内可以进行以下几种优化:合并已知量,删除多余运算(公共子表达式)删除无用赋值 优化手段: DAG 1 DAG 的定义 DAG 是有向无环路图的简称,结点的基本形式如右图: n i 为结点名, val 为结点值标记, op 为结点的运算. n ini1 ni2op val 142 四元式的 DAG 表示 考虑下面三种类型的四元式,DAG表示如右所示0 型: (:=, B, , A)1 型: (op, B, , A)2 型: (op,B,C,A) n i B,An in k A Bop An ini1 ni2 B Cop 153 基本块的 DAG 构造算法及优化令 NODE(A)= 若 DAG 中存在值标记为 A 的结点 n ,则返回 n ; 否则 返回 null.基本块的 DAG 构造算法如下: (1) 令 DAG =null (2) for 基本块的 每一四元式 do 若 NODE(A) 未被引用,或有多个值标记 , 则 删除 值标记 A; /(删除无用赋值) 根据四元式类型,分别转到 T0,T1,T2 处 T0 : /(:=, B, , A) 若NODE(B)= null 生成值标记为 B 的叶结点 n否则 令 n= NODE(B); 把 A 添加在 n 结点的右侧; 返回 (2) 16 T1 : /(op, B, , A) 若 B 为已知量 / 合并已知量 执行 op B , 得到一新常数 p, 若NODE(p)= null 生成值标记为 p 的叶结点 n 否则 令 n= NODE(p); 把 A 添加在 n 结点的右侧; 返回 (2) 否则 若 DAG 中存在型如右式的子图 则把 A 添加在 n 结点的右侧; 返回 (2) /合并多余运算 否则 若NODE(B)= null 生成值标记为 B 的叶结点 n1 否则 令 n1= NODE(B); 建立一运算为 op ,值标记为 A 的结点 n, 从 n 连一边到 n1 ,返回(2) n n 1 Bop 17 T2 : /(op, B, C , A) 若 B ,C为已知量 / 合并已知量 执行 op B , 得到一新常数 p, 若NODE(p)= null 生成值标记为 p 的叶结点 n 否则 令 n= NODE(p); 把 A 添加在 n 结点的右侧; 返回 (2) 否则 若 DAG 中存在型如右式的子图 则把 A 添加在 n 结点的右侧; 返回 (2) /合并多余运算 否则 若NODE(B)= null 生成值标记为 B 的叶结点 n1 否则 令 n1= NODE(B); 若NODE(C)= null 生成值标记为 C 的叶结点 n2 否则 令 n2= NODE(C); 建立一运算为 op ,值标记为 A 的结点 n, 从 n 分别连边到 n1 , n2 ,返回(2) n n 1 n 2 B Cop 184 示例:设基本块如下:(1) A:=x+y(2) T0:=3.14(3) T1:=2*T0(4) T2:=R+r(5) A:=T1*T2(6) B:=A(7) T3:=2*T0(8) T4:=R+r(9) T5:=T3*T4(10) T6:=R-r(11) B:=T5*T6 19DAG 如下3 1 2 x y+ A 4 3.14,T0 5 6.28,T1,T3 6 R 7 r8 T2,T4 10 T69 A,B,T511 B+ -* * 20生成DAG 后,实质上已经进行了局部优化,再把 DAG 还原得到如下四元式:(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 21第三节 循环优化 循环是由循环语句,if 及 goto 语句构成. 为了找出中间代码程序中的所有循环,就要对程序的流程进行分析,流程是以基本块为单位的,因为基本块内无循环.一 控制流程图与循环的定义1控制流程图的 定义:控制流程图是具有唯一首结点的有向图,简称为流图.可表示为三元式:G =( N,E,n0 )N 为结点集,每 一结点为一基本块;E 为有向边,代表流向; n0为首结点,它包含了程序的第一条语句. 222 流图的构造方法 (1) 若基本块 j 在程序中的位置紧跟在基本块 i 之后,且 i 的出口语句非 goto (s), 则: (2)若基本块 i 的出口语句为 goto (s), 或 if.goto (s),而( s ) 是基本块 j 的入口语句,则:示例: i j i j 23设四元式程序如下:(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 (8) write (Y)(9) halt(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) B1B2B3B4流图 243 循环的定义 流图中,满足下面两条性质的结点序列称为一个循环:(1) 结点序列为强连通的;(任意两点间都有通路,且通路上的结点都属于结点序列)(2) 结点序列中仅有一个入口结点.示例:右面为一流图结点序列 6 , 4,5,6,7 , 2,3,4,5,6,7是满足以上定义的循环;但结点序列 2,4, 2,3,4, 4,5,7, 4,6,7不是上述意义下的循环. 12 4 3 6 5 7 25二 查找循环 为了建立循环的查找算法,首先介绍几个基本概念: 必经结点集,回边,可归约流图1 必经结点集定义: 若从流图首结点出发到达 nj 的通路都必须经过 ni ,则称ni 为 nj 的必经结点, 记为 ni DOM nj ; 流图中结点 n 的所有必经结点,称为 n 的必经结点集, 记为 D(n). 26 12 4 3 6 5 7 例如: 右图各结点的必经结点集为:D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7 27 设 p1,p2.pk 是 n 的所有前趋结点, 根据定义,若 所有 pi ( 1ik )均有 d DOM pi ,则 d DOM n, 即D(n)= n D(p1) D(p2) . D(pk) 求 D(n) 的算法 (1) 令 D(n0)= n0 ; D(i)= N (i n0); (2) 对每一个 ni (i n0),temp= ni D(p1) D(p2) . D(pk);/ p1,p2.pk 为 ni 的所有前趋结点 if D(ni) temp then D(ni) :=temp (3) 重复(2), 直到所有D(ni)不再改变. d p1 p2 pk n 282 回边定义: 设 ba是流图中一条有向边,且 a D(b), 则ba称是流图中的一条回边. 可以从必经结点集中求出回边:for b N do for a DOM(b) do if 为一条有向边 then 为回边3 可规约流图定义: 一个流图称为可规约流图,但且仅当流图中除去回边而剩余部分构成无环路流图. ba回边DOM 294循环查找算法定理: 若流图为可规约流图,已知有向边 ba 是一条回边,则由结点 b,a 以及有通路到达 b 而不经过 a 的所有结点序列构成流图的一个循环.查找回边ba构成的循环算法:(1) 令 loop:=b,a; push(S,b);(2) if not empty(S) then n:=pop(s); for (m in pn) do / pn 为 n 的前趋结点集 if (m not in loop) then loop:=loop+m;push(S,m) 30三 优化信息-ud 集 为了进行循环优化,还应分析变量的定值及引用关系,这种关系称为 引用-定值链,或称为 引用-定值集.定义: 若变量 A 在四元式 d 定值,并存在一条通路到达四元式 u ,且 该通路上没有 A 的其它定值,则称 A 在 d 的定值到达 u .定义:如在 u 处引用了变量 A,则凡能到达 u 的 A 的所有定值点,构成了 A 在 u 处的引用-定值集 ,记为: udA. 下面介绍如何求 ud集.1 到达-定值方程 31首先定义四个基本集合:INB : 代表到达基本块 B 入口点时的各变量的所有定值点集;OUTB:代表到达基本块 B 出口点时的各变量的所有定值点集;G ENB:表示 B 中所定值的且到达 B 之后的定值点集;KILLB: 表示属于 B 外的定值点,而这些定值点所定值的变量在 B中又被重新定值 这几个集合满足如下方程: OUTB=(INB - KILL(B) G ENB INB = OUTp1 OUTp2 . OUTpk p1 , p2. pk 为B的前趋结点.该方程即为到达-定值方程,求解该方程,得到INB . 322求 ud A 算法如下: 若 B 中,变量 A 的引用点 u 之前有 A 的定值点 d,且到达 u ,则 ud A = d ; 否则 ud A = di | di INB 且 di为A的定值点. 这样,可以求出每个变量在引用点 u 的定值状况. 33四 循环的几种基本优化 下面介绍三种循环优化: 代码外提,强度削弱,删除归纳变量.代码外提定义: 对于循环中的语句 A:= B op C, 若 B 及 C 均为常量,或者 为 循环中未改变的变量, 那么每次循环 A的值都一样,称A:= B op C 为不变运算. 对于不变运算,有可能把 A:= B op C 放到循环前,具体做法是: a) 建立一前置结点; b) 循环入口结点(唯一的) 为前置结点的唯一后继; c) 循环外流向入口结点的有向边,改为流向前置结点; d) 把循环中可以外提的不变运算放在前置结点中.见下图: 34循环入口结点循环外流向前置结点前置结点循环入口结点 下面讨论两个问题:(1)哪些是循环中的不变运算?(2) 循环中的哪些不变运算可以放到前置结点中?循环外流向入口结点循环内结点循环内结点改为 351 不变运算的确定算法 (1) 察看循环中的每条四元式,若每个运算对象或为常量,或定值点在循环外的变量,则标记为不变运算; (2) 察看尚未标记为不变运算的四元式,若每个运算对象或为常量,或定值点在循环外的变量,或在循环内具有唯一定值点的变量且该定值点已经标记为不变运算,则标记为不变运算; (3)重复 (2),直到不产生新的不变运算. 362 代码外提算法 (1) 对循环中每一不变运算 (S) A:=B op C (包括 A:= op C 或 A:=B), 检查是否满足如下条件之一 : a) S所在的结点是循环所有出口结点的必经结点, 且 S为变量A 在循环中唯一 定值点, 且 A 的定值点 S 能到达循环中所有 A 的引用点; b) S为 变量 A 在循环中唯一 定值点, 且 A 的定值点 S 能到达循环中所有 A 的引用点, 且 A 在循环之后不再引用. (2) 把循环中满足条件 a) 或 b) 的不变运算移至前置结点中, 若运算对象 B 或 C 是在循环中定值, 则只有当 B 或 C 的定值点四元式已放入前置结点中后,才可以把 S 外提. 37强度削弱 强度削弱是指循环中,把执行时间较长的运算转换为执行时间较短的运算. 下面仅讨论乘法运算转换为加法运算.( 注:并非每个乘运算都可以进行强度削弱)定义: 若循环中对 B 只有唯一的递归赋值 B:=B+C 且 C 为循环不变量,则称 B 为循环的基本归纳变量.定义: 若 B 为基本归纳变量,而 A 在循环中的定值,可以化归为 B 的线性函数: A:=C1*B+C2 (C1 , C2为循环不变量 ) 则称 A 为归纳变量,并称 A与 B同族. 38一般而言,若循环中有递归赋值 B:=B+C (B 每次循环递增常量C) 而 循环中对 A 的赋值为 B 的线性函数 A :=C1*B+C2 (C1 , C2为常数 ) 那么,循环中A :=C1*B+C2的乘运算可转换为加运算,具体做法如下:在前置结点中添加: A :=C1*B+C2 令 C = C1 *C原A :=C1*B+C2 改为: A:=A在 B:=B+C 之后增加: A:=A+C 39示例: 根据定义 I 为基本归纳变量; T2,T6 为与 I 同族的归纳变量; T3,T7 可转化为: T3:= 10*I +T1 ( T1为循环不变量) T7:= 10*I +T5 ( T5为循环不变量) 也为 与 I 同族的归纳变量; 下面是对 T2 进行强度削弱的示例: (1) I:=1(2) T1:=2*J(3) T4:=addr(A)-11(4) T5:= 2*J(5) T8:=addr(A)-11(7) T2:=10*I(8) T3:=T2+T1(9) T6:= 10*I(10) T7:=T6+T5(11) T9:=T8T7(12) T4T3:=T9+1(13) I:=I+1(14) goto (6)(6) if I10 goto(15) 40基本归纳变量: I:=I+1 (C=1)T2 与 I 同族 : T2:=10*I+0 (C1=10,C2=0 )在前置结点中添加: T2 :=10*I令 C = 10原A :=C1*B+C2 改为: T2:=T2在 I:=I+1 之后增加: T2:=T2+10同理,T6,T3,T7 也一样处理. 41删除基本归纳变量 具体做法如下: 若基本归纳变量 B 在循环出口之后不再引用,且在循环中除B:=B+C 处被引用外,只在型如 if B rop Y goto (s) 中被引用,则 (1) 选一与B 同族的归纳变量 M , M与 B 有如下线性关系: M=C1*B+C2(2)建立一临时变量 R,在前置结点中增加 R:=C1*Y+C2(3)用if M rop R goto (s) 替换 if B rop Y goto (s) (4)删除循环中四元式 B:=B+C 42本章习题 P168 4. 9. 43