控制流与数据流分析

《控制流与数据流分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章控制流分析优化需要从程序中获得足够多的信息。控制流分析就是用来获取程序控制结构信息的形式化分析方法，它是数据流分析，依赖分析的基础。7.1控制流分析方法概述7.1.1过程内控制流分析方法主要有下面3种：1．用dominator图找出循环，把循环标记出来供后面的优化使用。因为循环是程序中最值得改进的地方，所以这种方法广泛被现在的编译器采用。2．Interval分析：这是一类分析方法的统称，用来分析单个过程的结构，并把它分解成为一系列有层次的结构称为interval。这些结构的层次关系可以用一棵树来表示，就叫控制树。接下来许多分析和优化就可以基于控制树来做。3．结构分析：结构分析是Inter

2、val分析中的特别重要且有代表性的一种，而且它在许多编译器或优化方法中被用到，所以单独作为一种控制流分析方法。这三种分析方法各有优劣之处，且三种方法并不是互相隔离的，具体实现时可以根据需求做出折衷选择。7.1.2控制流图和BB上面三种分析方法都是基于控制流图(CFG)的基本单元BB来做的。因为控制流图和BB大家都知道，所以这里省略它们的基本概念。只是在识别BB的方法上补充一点：对call语句的处理。对call语句的处理：一般情况下call语句调用目标过程后会返回call语句顺序的下一条语句。这时call语句和它顺序的下一条语句都不会被作为入口语句。但是，如果一个call语句有好几个返回地址(例

3、如：Fortran中有alternate返回地址)，那么call语句的下一条语句就应该作为入口语句，否则BB中将有一条既不是顺序执行又不在BB末尾的指令。C库函数中的setjump()和longjump()也有类似情况。Fortran1call…2…3……n…箭头所指都是入口语句7.13EBBEBB与控制流分析的关系不大，只是因为刚介绍了BB，所以把EBB也顺带介绍一下。EBB跟BB相比可以使指令调度这种局部优化在选择指令时范围更宽。介召EBB之前先要知道joinnode1.joinnode的概念：若一个节点不止一个前驱(随便有几个后继)，那么该节点就叫做joinnode。2.EBB：除了第一

4、个节点外，其余节点都不是join节点的最大CFG子图。(这里的第一个节点指的是唯一一个前驱不在该EBB之内的节点，其余节点都不是join节点因而只有唯一前驱，而且前驱属于该EBB之内，所以一个EBB就是以join节点为根的一棵树)图可见《muchnick一书》p177Fig7.8完全对称的，我们可以有branchnode和reverseEBB的概念，这里略。3.找EBB的算法：《muchnick一书》p176Fig7.67.7Build_EBB(r,succ,pred)：作用：给定某个joinnode，求以它为根的EBB树。思想：它调用Add_Bbs()从join节点r出发在CFG上做深度优先

5、搜索，若遇到非join节点就把它加入该EBB，然后沿该节点继续深度优先搜索；若遇到join节点就把它放入一个单独的集合EbbRoots里，然后控制返回它的父节点继续搜索。Build_All_Ebbs(r,succ,pred)：作用：找到CFG中所有EBB思想：把CFG的根放入EbbRoots集合里，并把它作为r调用Build_EBB(r,succ,pred)；然后对EbbRoots中的joinnode队列依次调用Build_EBB(r,succ,pred)，得到所有EBB。7.2深度/广度优先搜索，前序/后序遍历略7.3Dominators和PostDominators7.3.1dom，ido

6、m基本概念dominate(简写为dom)是一个二元关系，adomb表示从CFG的entry节点到b节点的任意一条路径都会经过a节点。这时把a叫做b的dominator。idom关系由dom关系得来，aidomb表示adomb，且不存在节点c同时满足adomc、cdomb。由CFG的节点集N和idom关系构成的边集组成一棵树，叫idom树，这棵树反映了CFG上所有节点间dom和idom关系。7.3.2求dominator和idominator求dominator的常规算法用的是迭代计算的方法，收敛结果即所求每个节点的domintor集合。该算法大家比较熟悉，略。求idominator的算法要基

7、于domintor算法的结果，用下图来简单阐述：Domin(n)-{n}节点n节点i节点s《muchnick一书》p184Fig7.15思想：任取节点i属于Domin(n)-{n}，固定i，依次检查Domin(n)-{n}-{i}中节点s，若s属于Domin(i)，则从Domin(n)中删除节点s，因为它不可能成为节点n的idominator了。检查完集合Domin(n)-{n}-{i}中剩余节点