编译 第五章 中间代码优化.ppt

1 局部优化 循环优化 优化目的: 提高运行速度, 减少存储空间. 第五章 中间代码优化中间代码优化 内容 : 第一节 优化概述 2 右面为 for 循环的中间代码: prod:=0; for i:=1 to 20 do prod:=prod+ai*bi 对该段中间代码,可以进行 如下优化: 1 删除多余运算 见(3),(6)两四元式的 4*i, (6) 可以改写为: t4:=t1, 从而减少了一次乘法. 参见下页四元式表 一维：i*w+base-low1*w (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代码外提 (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合并已知量 由于(3)中的 i 在 (2)赋值后 仍然为 1,因此可改为: t1:=4 6 复写 (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 定义: 基本块是一顺序执行的中间代码序列,仅包含一个入口 四元式 和一个出口四元式,第一条四元式为入口四元式,最后 一条四元式为出口四元式.中间部分不含转移四元式. 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) b1 b2 b3 b4 13 二 基本块内的优化 基本块内可以进行以下几种优化: 合并已知量, 删除多余运算(公共子表达式) 删除无用赋值 优化手段: dag 1 dag 的定义 dag 是有向无环路图的简称, 结点的基本形式如右图: n i 为结点名, val 为结点值标记, op 为结点的运算. n i ni1ni2 op val 14 2 四元式的 dag 表示 考虑下面三种类型的四元式,dag表示如右所示 0 型: (:=, b, , a) 1 型: (op, b, , a) 2 型: (op,b,c,a) n ib,a n i n k a b op a n i ni1ni2 b c op 15 3 基本块的 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 b op 17 t2 : /(op, b, c , a) 若 b ,c为已知量 / 合并已知量 执行 op b c , 得到一新常数 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 1n 2 b c op 18 4 示例: 设基本块如下: (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 19 dag 如下 3 1 2 x y + a 4 3.14,t0 5 6.28,t1,t3 6 r 7 r 8 t2,t4 1 0 t6 9 a,b,t5 1 1 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为首结点,它包含了程序的第一条语句. 22 2 流图的构造方法 (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) b1 b2 b3 b4 流图 24 3 循环的定义 流图中,满足下面两条性质的结点序列称为一个循环: (1) 结点序列为强连通的;(任意两点间都有通路,且通路上 的结点都属于结点序列) (2) 结点序列中仅有一个入口结点. 示例:右面为一流图 结点序列 6 , 4,5,6,7 , 2,3,4,5,6,7 是满足以上定义的循环; 但结点序列 2,4, 2,3,4, 4,5,7, 4,6,7 不是上述意义下的循环. 1 2 4 3 6 5 7 25 二 查找循环 为了建立循环的查找算法,首先介绍几个基本概念: 必经结点集,回边,可归约流图 1 必经结点集 定义: 若从流图首结点出发到达 nj 的通路都必须经过 ni ,则称 ni 为 nj 的必经结点, 记为 ni dom nj ; 流图中结点 n 的所有必 经结点,称为 n 的必经结点集, 记为 d(n). 26 1 2 4 3 6 5 7 例如: 右图各结点的必经结点集为: d(1)=1 d(2)=1,2 d(3)=1,2,3 d(4)=1,2,4 d(5)=1,2,4,5 d(6)=1,2,4,6 d(7)=1,2,4,7 27 设 p1,p2pk 是 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 (ni n0), temp= ni d(p1) d(p2) d(pk); / p1,p2pk 为 ni 的所有前趋结点 if d(ni) temp then d(ni) :=temp (3) 重复(2), 直到所有d(ni)不再改变. d p1 p2 pk n 28 2 回边 定义: 设 ba是流图中一条有向边,且 ad(b), 则ba称是流图 中的一条回边. 可以从必经结点集中求出回边: for b n do for a dom(b) do if 为一条有向边 then 为回边 3 可规约流图 定义: 一个流图称为可规约流图,但且仅当流图中除去回边而剩余 部分构成无环路流图. b a 回边 dom 29 4循环查找算法 定理: 若流图为可规约流图,已知有向边 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) and(m 到达-定值方程 31 首先定义四个基本集合: inb : 代表到达基本块 b 入口点时的各变量的所有定值点集; outb:代表到达基本块 b 出口点时的各变量的所有定值点集; genb:表示 b 中所定值的且到达 b 之后的定值点集; killb: 表示属于 b 外的定值点,而这些定值点所定值的变量在 b中又被重新定值 这几个集合满足如下方程: outb=(inb - kill(b) genb inb = outp1 outp2 outpk p1 , p2 pk 为b的前趋结点. 该方程即为到达-定值方程,求解该方程,得到inb . 32 2求 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) 循环中的哪些不变运算可以放到前置结点中? 循环外流向入口结点 循环内结点 循环内结点 改为 35 1 不变运算的确定算法 (1) 察看循环中的每条四元式,若每个运算对象或为常量,或定 值点在循环外的变量,则标记为不变运算; (2) 察看尚未标记为不变运算的四元式,若每个运算对象或为 常量,或定值点在循环外的变量,或在循环内具有唯一定值点的变 量且该定值点已经标记为不变运算,则标记为不变运算; (3)重复 (2),直到不产生新的不变运算. 36 (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)t8=t5*10 (11) prod:=prod+t7 (12) i:= i+1 (13) if i 代码外提算法 (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 外提. 38 39 强度削弱 强度削弱是指循环中,把执行时间较长的运算转换为执行时 间较短的运算. 下面仅讨论乘法运算转换为加法运算. ( 注:并非每个乘运算都可以进行强度削弱) 定义: 若循环中对 b 只有唯一的递归赋值 b:=b+c 且 c 为循环不 变量,则称 b 为循环的基本归纳变量. 定义: 若 b 为基本归纳变量,而 a 在循环中的定值,可以化归为 b 的线性函数: a:=c1*b+c2 (c1 , c2为循环不变量 ) 则称 a 为归纳变量,并称 a与 b同族. 40 (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)t8=t5*10 (11) prod:=prod+t7 (12) i:= i+1 (13) if i10 goto(15) 43 基本归纳变量: 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 之后增