1、基本块的划分方法:
基本块指程序中一顺序执行的语句序列,其中只有一个入口(该序列的第一个语句)和一个出口(该序列的最后一个语句)
在各个基本块范围内进行的优化叫局部优化。
基本块的划分:
从四元式序列确定满足以下条件的入口语句:
出口
2、DAG图的构建
DAG是一种有向图,常用于基本块的优化,图的叶节点(无后继的节点)以标识符(变量名)或常数作为标记,图的内部节点(有后继的节点)以一运算符作为标记。
为了DAG算法的需要,将四元式分成四类,算法只用0,1,2型四元式。
(1)是0型四元式,后继节点数为0,(2)是1型四元式,有一个后继,(3)、(4)、(5)是2型四元式,有两个后继 (6)是3型四元式,有三个后继。大写字母表示四元式中的变量名(或常数),Node(A)表示A在DAG中相应的节点。
练习:
3、DAG图实现基本块的优化
1、程序流图与循环
控制流程图就是有唯一首节点的有向图,用三元组G=(N,E,n0)表示(节点集,边集,首节点)节点集就是基本块集,有向边表示如下:基本块i出口语句不是转向语句或停语句,i与紧随其后的基本块j有有向边。或者i出口转向j入口语句。
2、循环:程序流图里的一个节点序列强连通,任意两个节点都有至少一条通路,它们中有且只有一个入口节点。(从序列外某节点有一条有向边引导它,或他是程序流图的首节点。
3、找循环:
必经节点集:从流图首节点出发,到n的任意通路都要经过m,m是n的必经节点,记为mDOMn;流图中结点n的所有必经节点的集合称为节点n的必经结点集,极为D(n)。
DOM的性质:自反性:流图中任意节点a,都有aDOMa。传递性:aDOMb,bDOMc则aDOMc。反对称性:aDOMb,bDOMa,a=b。DOM是一个偏序关系,任何节点n的必经节点集是一个有序集。
必经节点的求法:一定包括自己好吧。。。。。。必经节点集就是前驱节点必经节点集的交集加自己没准。
找回边:假设ab是流图中的一条有向边,如果bDOMa,则ab是流图中的一条回边。已知有向边nd是一条回边,则由它组成的循环就是由结点d、结点n以及有通路到达n但该通路不经过d的所有结点组成的。
4、可规约流图:当且仅当一个流图除去回边后,其余边构成一个无环路流图。性质:1. 图中任何直观环路都是循环。2. 找到所有回边可以对应找出所有循环。3. 循环或嵌套或不相交(可能有公共入口节点),goto语句不可跳入循环。
练习:
5、循环优化
练习:
练习:
基本归纳变量:给自己定值,给其他归纳变量赋值,控制循环(给其他归纳变量赋值在强度削弱时已经撇清了),出循环不活跃可删。删除归纳变量就是变换循环控制条件。选一个M,尽量在循环中引用,出了循环活跃,有M和B关系。
参考171页例题。