编译原理第11章 代码优化ppt课件.ppt

编译原理之代码优化 第11章代码优化 优化技术简介局部优化控制流分析和循环优化数据流的分析与全局优化 优化技术简介 优化概念优化分类优化技术 优化概念 优化实质上是对代码进行等价变换 使得变换后的代码运行结果与变换前代码运行结果相同 而运行速度加大或占用存储空间少 或两者都有 优化可在编译的不同阶段进行 对同一阶段 涉及的程序范围也有所不同 在同一范围内 可进行多种优化 一般 优化工作阶段可在中间代码生成之后和 或 目标代码生成之后进行 优化分类 按阶段分类与机器无关的优化依赖于机器的优化根据优化所涉及的程序范围分类局部优化 是在只有一个入口 一个出口的基本程序块上进行的优化 循环优化 是对循环中的代码进行的优化 全局优化 是在整个程序范围内进行的优化 优化技术 删除多余运算 删除公共子表达式 代码外提强度削弱变换循环控制条件合并已知量与复写传播删除无用赋值 删除多余运算 目的 在于使目标代码执行速度较快 示例 程序代码中间代码段 删除多余运算的程序代码 P 0forI 1to20doP P A I B I 删除多余运算优化的中间代码 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 P P T7 11 I I 1 12 ifI 20goto 3 1 P 0 2 I 1 B1 B2 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 P P T7 11 I I 1 12 ifI 20goto 3 1 P 0 2 I 1 B1 B2 代码外提 把循环不变运算 即其结果独立于循环执行次数的表达式 提到循环的前面 使之只在循环外计算一次 示例 代码外提示例 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 P P T7 11 I I 1 12 ifI 20goto 3 1 P 0 2 I 1 B1 B2 3 T1 4 I 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 12 ifI 20goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 B1 B2 强度削弱 强度削弱的思想是把强度大的运算换算成强度小的运算 示例 强度削弱示例 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 3 T1 T1 4 12 ifI 20goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 3 T1 4 I B1 B2 3 T1 4 I 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 12 ifI 20goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 B1 B2 变换循环控制条件 变换循环控制条件 确保整个程序的运行结果不变 示例 变换循环控制条件示例 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 3 T1 T1 4 12 ifT1 80goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 3 T1 4 I B1 B2 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 3 T1 T1 4 12 ifI 20goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 3 T1 4 I B1 B2 合并已知量与复写传播 运算对象都是编码时的已知量 可在编译时计算出它的值 复写传播变换的做法是 在复写语句f g后尽可能用g代表f 示例 合并已知量与复写传播示例 5 T3 T2 T1 6 T4 T1 8 T6 T5 T1 9 T7 T3 T6 10 P P T7 11 I I 1 3 T1 T1 4 12 ifT1 80goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 3 T1 4 B1 B2 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 3 T1 T1 4 12 ifT1 80goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 3 T1 4 I B1 B2 删除无用赋值 只要程序中其它地方不需要引用的赋值语句 删除后对程序的运行结果无任何作用 示例 删除无用赋值示例 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 3 T1 T1 4 12 ifT1 80goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 3 T1 4 B1 B2 5 T3 T2 T1 6 T4 T1 8 T6 T5 T4 9 T7 T3 T6 10 P P T7 11 I I 1 3 T1 T1 4 12 ifT1 80goto 3 1 P 0 2 I 1 4 T2 addr A 4 7 T5 addr B 4 3 T1 4 B1 B2 局部优化 基本块的概念基本块的划分基本块的变换基本块的DAG表示DAG构造算法DAG的应用 基本块的概念 基本块 是指程序中一顺序执行的语句序列 其中只有一个入口语句和一个出口语句 执行时只能从其入口语句进入 从其出口语句退出 入口语句 严格地说来就是 1 程序的第一个语句 2 条件转移语句或无条件转移语句的转移目标语句 3 紧跟在条件转移语句后面的语句 基本块的划分 划分中间代码 四元式程序 为基本块的算法 其步骤如下 1 求出四元式程序中各个基本块的入口语句 2 对每一入口语句 构造其所属的基本块 它是由该入口语句到下一入口语句 不包括下一入口语句 或到一转移语句 包括该转移语句 或到一停语句 包括该停语句 之间的语句序列组成的 3 凡末被纳入某一基本块的语句 都是程序中控制流程无法到达的语句 因而也是不会被执行到的语句 我们可以把它们删除 示例 基本块划分的示例 1 P 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 P P T7 11 I I 1 12 ifI 20goto 3 入口语句 入口语句 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 P P T7 11 I I 1 12 ifI 20goto 3 1 P 0 2 I 1 B1 B2 基本块的变换 基本块的主要保结构变换是 1 删除公共子表达式2 删除无用代码3 重新命名临时变量4 交换语句次序示例 基本块变换的示例 重新命名 语句t b c 其中t是临时变量 如果把这个语句改为u b c 其中u是新的临时变量 并且把这个t的所有引用改成u 那么基本块的运算结果不变交换语句次序 t1 b ct2 x y如果基本块有两个相邻的语句 当且仅当x和y都不是tl b和c都不是t2时 可以交换这两个语句的次序 代数变换 可以把基本块计算的表达式集合变换成代数等价的集合 简化表达式或用较快运算代替较设运算的变换 例如 x X 0或x x 1这样的语句可以从基本块中删除而不改变它计算的表达式集合 又如x y 2的指数算符通常要用函数调用来实现 使用代数变换 这个语句可由快速 等价的语句x y y来代替 基本块的DAG表示 概念DAG的要素DAG的表示 DAG的概念 在一个有向图中 称任一有向边m n 或表示为有序对 m n 中的结点m为结点n的前驱 分结 结点n为结点m的后继 子结 环路 任一有向边序列n1 n2 n2 n3 nk 1 nk为从结点n1到结点nk的一条通路 如果其中n1 nk 则称该通路为环路 该结点序列记为 n1 n2 nk 如果有向图中任一通路都不是环路 则称该有向图为无环路有向图 简称DAG DAG的要素 图的叶结点 即无后继的结点 以一标识符 变量名 或常数作为标记 表示该结点代表该变量或常数的值 如果叶结点用来代表某变量A的地址 则用addr A 作为该结点的标记 通常把叶结点上作为标记的标识符加上下标0 以表示它是该变量的初值 图的内部结点 即有后继的结点以一运算符作为标记 表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果 图中各个结点上可能附加一个或多个标识符 表示这些变虽具有该结点所代表的值 DAG的表示 一个基本块 可用一个DAG来表示 表示方法 ni为结点编号 结点下面的符号 运算符 标识符或常数 是各结点的标记 各结点右边的标识符是结点的附加标识符 四元式的DAG表示 四元式的DAG表示 6 goto s j s 0 A B B A 1 A opB op B A 2 A BopC op B C A 3 A B C B C A 4 ifBropCgoto s jrop B C s 5 D C B B D C DAG构造算法 一 首先 DAG为空 对基本块的每一四元式 依次执行 1 如果NODE D 无定义 则构造一标记为B的叶结点并定义NODE B 为这个结点 如果当前四元式是0型 则记NODE B 的值为n 转4 如果当前四元式是1型 则转2 1 如果当前四元式是2型 则 I 如果NODE C 无定义 则构造一标记为C的叶结点并定义NODE 1 为这个结点 II 转2 2 DAG构造算法 二 2 1 如果NODE B 是标记为常数的叶结点 则转2 3 否则转3 1 2 如果NODE B 和NODE C 都是标记为常数的叶结点 则转2 4 否则转3 2 3 执行opB 即合并已知量 令得到的新常数为P 如果NODE B 是处理当前四元式时新构造出来的结点 则删除它 如果NODE P 无定义 则构造一用P做标记的叶结点n 置NODE P n 转4 4 执行BopC 即合并已知量 令得到的新常数为P 如果NODE B 或NODE C 是处理当前四元式时新构造出来的结点 则删除它 如果NODE P 无定义 则构造一用P做标记的叶结点n 置NODE P n 转4 DAG构造算法 三 3 1 检查DAG中是否已有一结点 其唯一后继为NODE B 且标记为op 即找公共子表达式 如果没有 则构造该结点n 否则就把已有的结点作为它的结点并设该结点为n 转4 2 检查DAG中是否已有一结点 其左后继为NODE B 右后继为NODE C 且标记为op 即找公共子表达式 如果没有 则构造该结点n 否则就把已有的结点作为它的结点并设该结点为n 转4 4 如果NODE A 无定义 则把A附加在结点n上并令NODE A n 否则先把A从NODE A 结点上的附加标识符集中删除 注意 如果NODE A 是叶结点 则其标记A不删除 把A附加到新结点n上并令NODE A n 转处理下一四元式 DAG的应用 示例基本块G相应的DAG利用DAG进行优化从基本块得到的优化信息 基本块G T0 3 14T1 2 T0T2 R rA T1 T2B AT3 2 T0T4 R rT5 T3 T4T6 R rB T5 T6 相应的DAG 利用DAG进行优化 T0 3 14T1 6 28T3 6 28T2 R rT4 T2A 6 28 T2T5 AT6 R rB A T6 从基本块得到的优化信息 1 在基本块外被定值并在基本块内被引用的所有标识符 就是作为叶子结点上标记的那些标识符 2 在基本块内被定值且该值能在基本块后被引用约所有标识符 就是DAG各结点上的那些附加标识符 控制流分析和循环优化 概述程序流图循环 概述 在一个程序流程中 循环是必不可少的一种控制结构 所谓循环 就是程序中那些可能反复执行的代码序列 因为循环中的代码要反复执行 因而为了提高目标代码的效率必须着重考虑循环的代码优化 要进行循环优化 首先必须找出程序中的循环 为找出程序中的循环 就需要对程序的控制进程进行分析 程序流图 相关概念有向边集的构成示例程序流图 相关概念 一个控制流程图 简称为流图 就是具有唯一首结点的有向图 首结点就是从它开始到控制流程图中任何结点都有一条通路的结点 一个控制流程图表示成一个三元组C N E no 其中 N代表图中所有结点集 E代表图中所有有向边集 取代表首结点 一个程序可用一个流图来表示 流图中的有限结点集N就是程序的基本块集 流图中的结点就是程序中的基本块 流图的首结点就是包含程序第一个语句的基本块 有向边集的构成 假设流图中结点i和结点j分别对应于程序的基本块i和基本块j 则当下述条件1或2有一个成立时 从结点i有一有向边引向结点j1 基本块j在程序中的位置紧跟在基本块i之后 并且基本块的出口语句不是无条件转移语句goto s 或停语句 2 基本块i的出口语句是goto s 或if goto s 并且 s 是基本块j的入口语句 程序 例构造以下程序的流图 1 readx 2 ready 3 r xmody 4 ifr 0goto 8 5 x y 6 y r 7 goto 3 8 writey 9 halt 流图 循环 定义查找可归约流图优化 循环定义 入口结点 是指序列中具有下述性质的结点 从序列外某结点 有一有向边引到它 或者它就是程序流图的首结点 在程序流图中 称具有下列性质的结点序列为一个循环 1 它们是强连通的 也即 其中任意两个结点之间 必有一条通路 而且该通路上各结点部居于该结点序列 如果序列只包含一个结点则必有一有向边从该结点引到其自身 2 它们中间有且只有一个是入口结点 示例 循环示例 是循环的结点序列 6 4 5 6 7 2 3 4 5 6 7 不是循环的结点序列 2 4 2 4为入口 2 3 4 2 4为入口 4 6 7 4 7为入口 4 5 7 4 7为入口 程序流图 返回算法的D N 返回D N 示例 返回回边求循环 返回求扩展树 返回可归约流图 循环查找 必经结点 在程序流图中 对任意两个结点m和n 如果从流图的首结点出发 到达n的任一通路都要经过m 则称m是n的必经结点 记为mDOMn 必经结点集 流图中结点n的所有必经结点的集合 称为结点n的必经结点集 记为D n 示例回边 假设a b是流图中的一条有向边 如果bDOMa 则称n b是流图中的一条回边 必经结点的性质查找算法 必经结点的性质 1 自反性 对流图中任意结点a 有aDOMa 2 传递性 对流图中任意结点a b和c 若aDOMb bDOMc 则有aDOMc 3 反对称性 若aDOMb且bDOMa 则必有a b 因此 关系DOM是一个偏序关系 任何结点n的必经结点集是一个有序集 循环查找算法 求流图所有结点必经结点集的算法计算必经结点集结点次序的方法由回边求循环的结论由回边求循环算法的基本思想求流图中由回边组成循环的算法示例 运用算法求D N 的示例求回边由回边求循环 求流图所有结点必经结点集的算法 深度为主查找法 简介相关概念 前向边后向边横向边深度深度为主扩展树深度为主扩展树算法示例 深度为主查找法简介 如果对于给定的流图 在沿着从首结点开始的通路访问图中各个结点的过程中 始终沿着某通路前进 直到访问不到新结点时 才回退到其前驱 然后由前驱结点沿另一通路前进 直到访问不到新结点时 再回退其前驱 按此步骤 直至退到首结点并且再也访问不到新结点为止 这种查找方法被称为深度为主查找法 如果按深度为主查找中所经过结点序列的逆序 依次给各结点排上一个次序 则称该次序为深度为主次序 前向边 假设m n是流图的一条有向边 如果在流图的DFST中m是n的祖先 则称m n为流图的前向边 后向边 假设m n是流图的一条有向边 如果在流因的DFST中 n是m的祖先或n m 则称m n为流图的后向边 横向边 假设m n是流图的一条有向边 如果在流图的DFST中m与n没有祖先与后代的关系 则称m n为流图的横向边 深度 对于一个流图和它的某一扩展树 流图中任何无环路通路含有的后向边边数的最大值称为该流图的深度 深度为主扩展树 把在按深度为主查找中依次访问到的各个新结点用有向边联结成一个图 就成为一棵树 称该树为深度为主扩展树 简称DFST DepthFirstSpanningTree 深度为主扩展树算法 proceduresearch n begin 1 把n标记为 已访问 2 fors S n do S n 为n的后继集 3 ifs标记为 未访问 thenbegin 4 把有向边n s加到T中 5 search s end 6 DFN n i i i 1end begin 8 T 空 9 forn Ndo标记n为 未访问 10 i N 11 search n0 end 深度为主扩展树示例 对于流图 把各结点按深度为主次序进行访问 先沿最左通路访问各结点 所经过的结点序列是 1246764542321结点下面的底线指出该结点在序列中最后一次出现的位置 按以上序列的逆序 各结点的排出次序为 1 2 3 4 5 6 7这个次序就是各结点的深度为主次序 由此可得其深度为主扩展树见右图 由回边求循环的结论 如果已知有向边n d是回边 那么就可以求出由它组成的循环 该循环就是由结点d 结点n以及有通路到达n而该通路不经过d的所有结点组成 并且d是该循环的唯一入口结点 这是因为 1 令上述结点集为L 则L必定是强连通的 这一点可由图论知识予以证明 2 对所有的ni L 都有dDOMni d必为L的一个入口结点 同时也是ni的唯一入口结点 由回边求循环算法的基本思想 由于要求回边n d组成的循环 这个循环将以d为其唯一入口 n是它的一个出口 若n不同时是d 则n的所有前驱结点应属于循环 当求出n的所有前驱后 只要它们不是循环入口d 就应再求出它们的前驱 新求出的所有前驱也应属于循环 然后再对新求出的所有前驱 重复以上步骤 直到所求出的前驱是d为止 此时算法结束 求流图中由回边组成循环的算法 主程序 stack 空 loop d insert n whilestack非空dobegin把Stack的栈顶元素m上托出去forp P m doinsert p end procedureinsert m ifm不属于loopthenbeginloop loop m 把m下推进栈stack end 求D N 的示例 结点必经结点集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 程序流图 返回算法求D N 的示例 运用算法求D N 的示例 一 首先置初值 D 1 1 D 2 D 3 D 7 1 2 3 4 5 6 7 置CHANGE为FALSE 对结点2到结点7依次执行 7 10 对结点2 NEWD 2 D 1 D 4 2 1 1 2 3 4 5 6 7 1 2 因D 2 NEWD 故置CHANGE TRUE 令D 2 NEWD 1 2 对结点3 NEWD 3 D 2 1 2 3 因D 3 NEWD 令D 3 NEWD 1 2 3 对结点4 NEWD 4 D 2 D 3 D 7 1 2 4 D 4 令D 3 1 2 4 程序流图 运用算法求D N 的示例 二 同理得D 5 5 D 4 1 2 4 5 D 6 6 D 4 1 2 4 6 D 7 7 D 5 D 6 1 2 4 7 至此 一次迭代完毕 由于CHANGE TRUE 进行下一次迭代 运用算法求D N 的示例 三 置CHANGE为FALSE 对结点2到结点7依次执行 7 10 对结点2 NEWD 2 D 1 D 4 2 1 1 2 4 1 2 4 此时D 2 NEWD 故D 2 不变对结点3 NEWD 3 D 2 1 2 3 D 3 同理可求得所有结点均有NEWD D n 故第二次送代结束后 CHANGE为FALSE 迭代结束 每个结点的D n 值就是所求的结果 求回边的示例 程序流图因为在所有的有向边中 存在 6DOM6 4DOM7 2DOM4 所以有向边6 6 7 4 4 2是回边 由回边求循环示例 求流图中回边7 4组成的循环开始 置loop 4 stack为空 由insert把结点7放到栈中 此时loop 4 7 然后7退栈 7的前驱结点集P 7 5 6 把5和6先后故入loop和stack中 这时loop 4 7 5 6 然后6退栈 P 6 6 4 已在loop中 故6仅退出stack而已 此时栈顶为P 5 6 4 也在loop中 之后stack已空 算法结束 所求循环loop 4 5 6 7 可归约流图 可归约流图 当且仅当流图中除去回边外 其余的边构成的一个无环路流图 示例 可归约流图的性质 1 图中任何直观意义下的环路 都属于循环 2 只要找出图中所有回边 对回边应用前述循环查找算法 就可找出流图中所有的循环 3 图中任意两个循环要么嵌套 要么不相交 除了可能有公共的入门结点 循环优化 相关定义优化方法代码外提强度削弱删除归纳变量 相关定义 点 指某一四元式的位置 对变量的 定值 指对变量赋值或输入值 定值点指变量在该点被赋值或输入值 引用点则指在该点使用了该变量 到达一定值点是指变量在某点定值后到达的一点 通路上没有其它该变量的定值 如果循环中对变量I只有唯一的形如I I C的赋值 且其中C为循环不变量 则称I为循环中的基本归纳变量 如果J是循环中一基本归纳变量 J在循环中的定值总是可以化归为I的同一线性函数 也即J C1 I C2 其中C1和C2都是循环不变量 则称J为归纳变量 并称它与I同族 代码外提 代码外提的流图不变运算的查找算法代码外提的要求代码外提的算法示例 代码外提的流图 实行代码外提时 在循环的入口结点前面建立一个新结点 基本块 称之为循环的前置结点 循环的前置结点以循环的入口结点为其唯一后继 原来流图中从循环外引到循环入口结点的有向边 改成引到循环前置结点 不变运算的查找算法 1 依次查看循环L中各基本块的每个四元式 如果它的每个运算对象或为常数 或者定值点在L外 则将此四元式标记为 不变运算 2 依次查看尚未被标记为 不变运算 的四元式 如果它的每个运算对象或为常数 或者定值点在L之外 或只有一个到达 定值点且该点上的四元式已被标记为 不变运算 则被查看的四元式标记为 不变运算 3 重复第 2 步直至没有新的四元式被标记为 不变运算 为止 代码外提的要求 1 当把循环中的不变运算A BopC外提时 要求循环中其它地方不再有A的定值点 2 当把循环中的不变运算A BopC外提时 要求循环中A的所有引用点都是而且仅仅是这个定值所能达到的 代码外提的算法 1 求出循环L的所有不变运算 2 对步骤1 所求得的每一不变运算s A BopC或A opB检查它是否满足以下条件 a 或 b a s所在的结点是L的所有出口结点的必经结点 A在L中其它地方未再定值 L中所有A的引用点只有s中A的定值才能到达 b A在离开L之后不再是活跃的 并且条件 a 的 I 和 成立 所谓A在离开L后不再是活跃的是指 A在L的任何出口结点的后继结点的入口处不是活跃的 从此点后不被引用 3 按步骤 1 所找出的不变运算的顺序 依次把符合 2 的条件 a 或 b 的不变运算s外提到C的前置结点中 如果s的运算对象 B或C 是在L中定值的 则只有当这些定值四元式都已外提到前置结点中时 才可把s也外提到前置结点 代码外提的示例 1 i 1 2 ifx ygotoB3 5 y y 1 6 ify 20gotoB5 3 i 2 4 x x 1 7 j i B1 B2 B3 B4 B5 3 i 2 1 i 1 2 ifx ygotoB3 5 y y 1 6 ify 20gotoB5 4 x x 1 7 j i B1 B2 B3 B4 B5 B2 在入口处 B2 如果x的值大于或等于y 则将i 2外提则是错误的 强度削弱 算法 1 找出循环中的所有基本归纳变量 2 找出所有其它归纳变量A 并找出A与已知基本归纳变量x的同族线性函数关系FA x 具体地说 a 在循环L中找出形如A B C A C B A B C A B C A C B的四元式 其中B是归纳变量 C是循环不变量 b 假设找出的四元式为s A C B 这时 I 如果B就是基本归纳变量 则X就是B A与基本归纳变量B是同族的归纳变量 且A与B的函数关系就是FA B C B II 如果B不是基本归纳变量 假设B与基本归纳变量D同族且它们的函数关系为FB D 那么 如果L外B的定值点不能到达s且L中B的定值点与s之间未曾对D定值 则x就是D A与基本归纳变量D是同族的归纳变量 A与D的函数关系是 FA D C B C FB D 强度削弱 算法 3 对 2 中找出的每一归纳变量A 假设A与基本归纳变量B同族 而且A与B的函数关系为FA B C1 B C2 其中C1和C2均为循环不变量 执行以下步骤 a 建立一个新的临时变量SFA B 如果两个归纳变量同族且这两个归纳变量与其同族基本归纳变量的函数关系相同 即 若A和A 都与B同族且FA B FA B 则为这两个归纳变量只建一个临时变量SFA B b 在循环前置结点原有的四元式后 增加 SFA B C1 BSFA B SFA B C2如果C2 0 则没有后一四元式 c 把循环中原来对A赋值的四元式改为A SFA B d 在循环中基本归纳变量B的唯一赋值B B E E为循环不变量 后增加 SFA B SFA B C1 E如果C1 1且E是变量名 则上式是以下两个四元式 T C1 ESFA B SFA B T其中T为临时变量 强度削弱 算法 4 依次考察 3 中每一归纳变量A 如果在A SFA B 与循环中任何引用A的四元式之间没有对SFA B 的赋值且A在循环出口之后不活跃 则删除A SFA B 并把所有引用A的地方改为引用SFA B 删除归纳变量 1 找出循环中的所有基本归纳变量B 2 如果基本归纳变量B在循环出口之后不是活跃的 并且在循环中 除在其自身的递归赋值中被引用外 只在形如ifBropYgotoZ中被引用 则 a 选取一个与B同族的归纳变量M 并设FM B Cl B C2 b 建立一个临时变量R 并用R C1 YR R C2ifFM B ropYgotoZ来替换ifBropYgotoZ c 删除循环中对B递归赋值的四元式 数据流的分析与全局优化 主要的概念到达 定值引用 定值链活跃变量定值 引用链可用表达式数据流方程复写传播 到达 定值 定值点 变量A的定值是一个语句 四元式 它赋值或可能赋值给A 最普通的定值是对A的赋值或读值到A的语句 该语句的位置称作A的定置点 到达 定值 变量A的定值点d到达某点p 是指如果有路径从紧跟d的点到达p 并且在这条路径上d没有被 注销 指该变量重新被定值 即在流图中从d有一条路径到达p且该通路上没有A的其它定值 引用 定值链 假设在程序中某点u引用了变量A的值 则把能到达u的A的所有定值点的全体 称为A在引用点u的引用 定值链 通常 把到达 定值信息存储作为引用 定值链是比较方便的 它是所有能够到达变量的某个引用的定值表 也称之为ud链 在进行循环优化时 为了求出循环中的所有不变运算 我们需要知道各变量引用点的ud链信息 活跃变量 对程序中的某变量A和某点p而言 如果存在一条从p开始的通路 其中引用了A在点P的值 则称A在点p是活跃的 否则称A在点p是死亡的 无论是基本块优化或是循环优化 都可能引起某些变量的定值在该基本块或循环内不会被引用 只要这些变量在基本块或循环的出口之后也不是活跃的 那么 这些变量在该基本块或循环内的定值就是无用赋值 从而可以予以删除 因此 活跃变量的分析对于删除无用赋值是很有意义的 定值 引用链 对一个变量A在某点p的定值 该定值能到达的对A的所有引用点 这些引用点的集合称为该定值点的定值 引用链 简称du链 可用表达式 如果从首结点到p的每条路径上 不必是无环 都计算XopY 并且在每条通路上最后一个这样的计算和p之间没有对X和Y的定值 则称表达式XopY在点p可用 对可用表达式 如果一个基本块对X或Y赋值 或可能赋值 并且随后没有重新计算XopY 则称为基本块注销表达式 如果它计算XopY 并且随后又没有重新定义X或Y 则称为基本块产生表达式 可用表达式的应用 可用表达式的应用 可用表达式的基本应用是寻找公共子表达式 首先要计算基本块产生的可用表达式集合 在块的开始点 假定无可用表达式 从头到尾扫描块中所有语句 如果在p点可用表达式集合是A q是p的下一点 p和q之间的语句是X YopZ 那么q点的可用表达式集合由下列两步计算 1 把表达式YopZ加入A 2 删掉A中任何含X的表达式 注意 这两步必须以此次序完成 因为x可能就是Y和Z 到达块的结束点之后 A是由此块产生的表达式集合 注销表达式集合是所有的表达式YopZ 其中Y或Z在本块中定值 并且该块没有产生YopZ 示例 可用表达式的应用示例 语句 1 a b c 2 b a d 3 c b c 4 d a d 可用表达式 none onlyb c onlya d onlya d none 左图的四个语句中 第一个语句后 b c可用 第二个语句后 a d可用 b c不再可用 因为b已重新定值 第三个语句不能使b c再次可用 因为c的值立即改变 经最后一个语句 a d也不再可用 因为d已改变 这样 没有可用表达式生成 包含a b c或d的表达式都被注销 数据流方程 基本形式建立和解散的依据具体的数据流方程到达 定值数据流方程可用表达式数据流方程活跃变量数据流方程 数据流方程的基本形式 当控制流通过一个语句时 在语句末尾的信息是进入这个语句中的信息扣除语句中产生和注销的信息并上产生的信息 这样的方程称之为数据流方程 一般形式 out s in s kill s gen s 建立和解散的依据 1 产生和注销的概念依赖于所需要的信息 即根据数据流方程所要解决的问题来决定 对某些问题 有可能不是沿着控制流前进和由in s 来定义out s 而是反向前进和由out s 来定义in s 2 因为数据沿控制路径流动 所以数据流分析受程序控制结构影响 事实上 当写out s 时 隐合地认为控制流从语句的唯一出口点离开这个语句 通常方程是在基本块一级建立而不是在语句级建立 因为基本块有唯一的出口点 3 在过程调用 通过指针赋值以及对数组变量的赋值语句中 常常会伴随一些问题 对于这些问题需进行相应的处理 到达 定值数据流方程 约定求定值点的规则到达 定值数据流方程out B m B kill B gen B in B out p p P B 求解算法示例 约定 in B 到达基本块B入口之前的各个变量的所有定值点集 out B 到达B的出口之后 紧接着B出口之后的位置 的各个变量的所有定值点 gen B B中定值的并到达B出口之后的所有定值点集 也即B所 生成 的定值点集 kill B 基本块B外满足下述条件的定值点集 这些定值点所定值的变量在B中巳被重新定值 也即B所 注销 的定位点集 gen B 和kill B 均可直接从给定的流图求出 利用gen B 和kill B 可以列出关于in B 和out B 的数据流方程而求出In B 和out B 求定值点的规则 1 如果B中p的前面有A的定值 则到达p的A的定值点是唯一的 它就是与p最靠近的那个A的定值点 2 如果B中p的前面没有A的定值 则到达p的A的所有定值点就是in B 中A的那些定值点 求解算法 beginfori 1tondobeginin Bi out Bi gen Bi end change true whilechangedobeginchange false fori 1tondobeginnewin out p p P Bi ifnewin in Bi thenbeginchange ture in Bi newin out Bi in Bi kill Bi gen Bi endendendend 到达 定值数据流方程示例 i 2j i 1 i 1 j j 1 j j 4 B2 B1 B3 B4 B5 d1d2 d3 d4 d5 d6d7 流图 深度为主扩展树 gen和kill的值置迭代初值迭代过程 a ib j gen和kill的值 迭代过程 置迭代初值 开始 置迭代初值 第0次迭代 in B1 in B2 in B3 in B4 in B5 0000000out B1 1100000out B2 0010000out B3 0001000out B4 0000100out B5 0000000执行算法第 4 行 置change为true 第一次迭代 迭代初值 第1次迭代开始 置change为false 在算法第 7 行按深度为主次序依次对B1 B2 B3 B4 B5执行算法第 8 行至第 12 行 对于B1 newin out B2 0010000 in B1 所以 change为true in B1 0010000out B1 in B1 kill B1 gen B1 001 1100000 1100000对于B2 newin out B1 out B5 1100000 0000000 in B2 所以 change为true in B2 1100000out B2 in B2 kill B2 gen B2 110 0010000 0110000对于B3 newin out B2 0110000 in B3 所以 change为true in B3 0110000out B3 in B3 kill B3 gen B3 011 0001000 0011000对于B4 newin out B3 0011000 in B4 所以 change为true in B4 0011000out B4 in B4 kill B4 gen B4 001 0000100 0010100对于B5 newin out B3 out B4 0011000 0010100 in B2 所以 change为true in B5 0011100out B5 in B5 kill B5 gen B5 001 0000000 0011100 可用表达式数据流方程 约定数据流方程out B int B E kill B E gen B in B out p B不是首结点 p P B in B1 B1是首结点 求解算法应用 删除全局公共子表达式 约定 是程序中出现在各四元式右部的所有表达式集合 in B 是在B开始点的可用表达式集合 out B 是在B结束点的可用表达式集合 E gen B 是B生成的表达式集合 E kill是 中被B注销的表达式集合 求解算法 应用 假设已计算出基本块B入口之前的可用表达式集in B 以及到达 定值信息 对基本块B中每个四元式s A DopC 其中DopC在B入口之前是可用的 并且B中之前未对D或C重新定值 依次执行以下步骤 1 在到达B的每条通路上 求出与s有相同