编译原理代码优化.ppt

第11章 代码优化11．1 什么是代码优化 11．2 局部优化 11．3 控制流程分析和循环 11．4 数据流分析举例何谓代码优化： 宗旨：获得较好性能的代码等价意图，结果，权衡 阶段： source front I.R code target code end generator code 用户中间代码优化目标代码优化int arr[10000]; void Binky() { int i; for (i=0; i = C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt基本块的DAG表示及其应用DAG Directed Acyclic Graph无环路有向图 基本块的DAG是在结点上带有标记的DAG叶结点 独特的标识符(名字,常数)标记内部结点 运算符号标记各个结点 附加标识符标记用DAG进行基本块的优化 四元式DAG结点 0型：A:=B(:=,B,—,A) n1 AB 1型: A:=op B(op,B, —,A) n2 Aopn1B 2型: A:=B op C(op, B, C,A) n3 A opn1 n2 B Cn1n2n1n3n1n211．3 控制流分析和循环 控制流程图（流图）：具有惟一首结点的有向图 G=（N，E，n0） N：结点集 基本块集E：有向边集 n0：首结点 包含程序第一个语句的基本块分析程序流图中结点间的关系 m DOM n 定义在程序流图中,对任意两个结点m和n,如果从 流图的首结点出发,到达n的任意通路都要经过 m,则称m是n的必经结点,记为m DOM n (a,a MOD a)必经结点必经结点集 定义结点n的所有必经结点必经结点的集合,称为结点n的必经 结点集,记为D(n).例:67341235761212121必经结点 必经结点集 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}3循环的查找 循环的查找算法 回边：假设 a→b是流图中的一条有向边，如果b DOM a，则 称 a →b是流图中的一条回边。

有向边 n→d是回边，组成的循环是由结点d ，结点 n以及有 通路到达 n而该通路不经过 d的所有结点组成，并且d是该循 环的惟一入口结点回边 6 6循环{6}7 4 {4,5,6,7}4 2 {2,3,4,5,6,7} 循环(结点序列的性质) 1.强连通的(任意两结点间,必 有一条通路,且该通路上各 结点都属于该结点序列) 2.它们中间有且只有一个是入 口结点.例:673412357612121231数据流分析1.活跃变量数据流方程 2.到达--定值数据流方程 3.讨论 数据流问题分类路径数据流方程解不惟一活跃变量的数据流分析所谓活跃变量就是它的当前值还将被引用 （在赋予一个新值之前）在全局范围 来分析的话，一个变量是活跃的，如果 存在一条路径使得该变量被重新定值之 前它的当前值还要被引用 通过全局活跃变量分析，识别出其当前值 不再活跃（即，它的值已经死了）的那 些变量死变量的值在基本块的出口处 不需要保存令B为一个基本块， 定义LiveIn(B)为在基本块B入口处为活跃的变量的集合 定义LiveOut(B)为基本块B的出口处的活跃变量的集合。

LiveIn 和LiveOut并不是相互独立的，令S（B）为流图中基本块B的 后继的集合，则有 LiveOut(B)=∪LiveIn(i) i∈s(B)如果基本块没有后继，则其LiveOut为空 令LiveUse(B)为B中被定值之前要引用变量的集合这个集合由 基本块B中的语句唯一确定容易看出，如果v∈LiveUse(B) ，则v∈LiveIn(B)； 即LiveIn(B)  LiveUse(B) 令Def(B)为在B中定值的变量集合如果一个变量在基本块B的 出口处为活跃的且vDef(B)，则它在B的入口处也是活跃的 ，即： LiveIn(B)  LiveOut(B)- Def(B) 因此有：LiveIn(B)= LiveUse(B)∪(LiveOut(B)- Def(B)) 即：一个变量在基本块入口处为活跃的，则一定有：或者它在 基本块的LiveUse集中，或者它在基本块的出口处为活跃的 且在基本块中没有重新定值a:=1; if a=b thenb:=1else c:=1 endif; d:=a+ba:=1 if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4提取Def和LiveUse集合基本 块DefLive UseB1{a}{b}B2{b}ØB3{c}ØB4{d}{a,b}a:=1 if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4从最后一个基本块开始由后往前计算，可以得到一定的解LiveIn(B)= LiveUse(B)∪(LiveOut(B)- Def(B))LiveOut(B)=∪LiveIn(i) i∈s(B)LiveOut(B4)=Ø，因此： LiveIn(B4)= LiveUse(B4)= {a,b}-{d} 现在 LiveOut(B2)=LiveIn (B4)={a,b} -{d} LiveOut(B3)=LiveIn (B4)= {a,b} -{d} LiveIn(B2) = LiveOut(B2)- Def(B2)= {a,b}- {b} -{d} = {a} -{d} LiveIn(B3) = LiveOut(B3)- Def(B3)= {a,b} – {c} -{d} = {a,b} – {c} -{d} LiveOut(B1) = LiveIn (B2) ∪LiveIn (B3)= {a}∪ {a,b} -{d} = {a,b} -{d} – {c} 最后 LiveIn(B1)= LiveUse(B1)∪(LiveOut(B1)-Def(B1)) = {b}∪({a,b} – {c} -{d} – {a}) = {b} - {d} – {c} a:=1 if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4分析程序中所有变量的定值和引用之间的关系到达--定值数据流方程 OUT[B]=(IN[B]-KILL[B])GEN[B] IN[B]=  OUT[p]pP[B]P[B]:B的所有前驱基本块 GEN[B]:B中定值并到达B出口之后的所有定值点集. KILL[B]:B之外的那些定值点集,其定值的变量在B中 又重新定值. IN[B]:到B入口之前(紧)的各变量的所有定值点集 OUT[B]:到达B出口之后(紧)各变量的所有定值点集.GEN位向量KILL B1{d1,d2}11000000011100 B2{d3}00100001000000 B3{d4}00010000100100 B4{d5}00001000101000 B5{ }00000000000000IN[B]OUT[B] B101111001100000 B211111000111100 B301111000011000 B400110000010100 B500111000011100入口结点••循环L••前置结点入口结点•••循环L •12345B1B2B3 B4B5(1)I:=1I:=3; (2)if x

3） 要求循环中A的所有引用点都是而且仅仅是这个定值所能 达到的（1）要求s所在结点是循环的所有出口结点的必经结点（4）要求A在离开循环之后不再是活跃的数据流问题的讨论合流问题向前流（forward-flow)(信息流的方向与控制流是一致的)和 向后流（backward – flow） 对每个基本块有一个IN集合和一个Out集合,在同一基本块中，In 和Out集合的关系 对于向前流问题：Out (B) = Used (B) ∪(In(B) – Killed (B)) 对于向后流问题：In (B) = Used (B) ∪(Out (B) – Killed (B)) 作为一个边界条件，向前流问题中的起始基本块的In和向后流 问题中最后一个基本块的Out集合必须指明，通常，这些边界 条件集或者为空，或者包含所有可能的值，因问题而定如：到达--定值数据流方程OUT[B]=(IN[B]-KILL[B])GEN[B] 活跃变量数据流方程 LiveIn(B)=LiveUse(B)∪(LiveOut(B)-Def(B))数据流问题的讨论路径问题任意路径数据流分析 讨论的数据流假定这么一个性质，即某条路径为真，（ 如果存在某条路径上被引用这个变量就认为是活跃的 ；如果存在任何一条路径上被定值，则就认为这个变 量是被定值的）。

这种数据流问题被称为任意路径问 题任意路径问题的解不能保证所需的性质一定会满 足，仅仅是可能满足 全路径数据流分析 数据流问题也可以用全路径（all- path）形式来解决，使 所需的性质在所有可能的路径都满足对于全路径问 题的解，所需的性质可以保证总是满足 数据流问题的解不一定唯一考察图10.20的流图，其中有一个简单的循环在 这个流图中，没有对任何变量定值，a在B4中被 引用应用向后流方法传播可以得到一个最明 显的解，即四个基本块的LiveIn集合均为{a} 但是，不太合理的解也是可能的 若 Def(B1)=Def(B2)= Def(B3)= Def(B4)= Liveuse(B1)=  Liveuse(B1)=  Liveuse(B1)=  Liveuse(B1)={a}则最明显的解： LiveIn(B1)= LiveIn(B1)= LiveIn(B1)= LiveIn(B1)={a}B1B2B3B4例如，下面解是满足数据流方程的：基本块LiveInLiveOut B1{a,b}{a,b} B2{a,b}{a,b} B3{a,b}{a,b} B4{a}Ø注意b没有在任何基本块中被引用！问题所在是 基本块B2和B3互为祖先；而且，因为b从未定值 （所有Def集为空），一旦b被包括在LiveIn集合中， 它就永远消除不了。