控制流与数据流分析..doc

第七章 控制流分析 优化需要从程序中获得足够多的信息。控制流分析就是用来获取程序控制结构信息的形式化分析方法，它是数据流分析，依赖分析的基础。 7.1控制流分析方法概述 7.1.1 过程内控制流分析方法主要有下面3种： 1．用dominator图找出循环，把循环标记出来供后面的优化使用。因为循环是程序中最值得改进的地方，所以这种方法广泛被现在的编译器采用。 2．Interval分析：这是一类分析方法的统称，用来分析单个过程的结构，并把它分解成为一系列有层次的结构称为interval。这些结构的层次关系可以用一棵树来表示，就叫控制树。接下来许多分析和优化就可以基于控制树来做。 3．结构分析：结构分析是Interval分析中的特别重要且有代表性的一种，而且它在许多编译器或优化方法中被用到，所以单独作为一种控制流分析方法。 这三种分析方法各有优劣之处，且三种方法并不是互相隔离的，具体实现时可以根据需求做出折衷选择。 7.1.2 控制流图和BB 上面三种分析方法都是基于控制流图(CFG)的基本单元BB来做的。因为控制流图和BB大家都知道，所以这里省略它们的基本概念。只是在识别BB的方法上补充一点：对call语句的处理。 对call语句的处理：一般情况下call语句调用目标过程后会返回call语句顺序的下一条语句。这时call语句和它顺序的下一条语句都不会被作为入口语句。但是，如果一个call语句有好几个返回地址(例如：Fortran中有alternate返回地址)，那么call语句的下一条语句就应该作为入口语句，否则BB中将有一条既不是顺序执行又不在BB末尾的指令。C库函数中的setjump( )和longjump( )也有类似情况。 7.13 EBB EBB与控制流分析的关系不大，只是因为刚介绍了BB，所以把EBB也顺带介绍一下。EBB跟BB相比可以使指令调度这种局部优化在选择指令时范围更宽。介召EBB之前先要知道join node 1. join node的概念：若一个节点不止一个前驱(随便有几个后继)，那么该节点就叫做join node。 2. EBB：除了第一个节点外，其余节点都不是join节点的最大CFG子图。(这里的第一个节点指的是唯一一个前驱不在该EBB之内的节点，其余节点都不是join节点因而只有唯一前驱，而且前驱属于该EBB之内，所以一个EBB就是以join节点为根的一棵树) 图可见《muchnick一书》p177 Fig7.8 完全对称的，我们可以有branch node和reverse EBB的概念，这里略。 找EBB的算法：《muchnick一书》p176 Fig7.6 7.7 Build_EBB(r, succ, pred)： 作用：给定某个join node，求以它为根的EBB树。 思想：它调用Add_Bbs( )从join节点r出发在CFG上做深度优先搜索，若遇到非join节点就把它加入该EBB，然后沿该节点继续深度优先搜索；若遇到join节点就把它放入一个单独的集合EbbRoots里，然后控制返回它的父节点继续搜索。 Build_All_Ebbs(r, succ, pred)： 作用：找到CFG中所有EBB 思想：把CFG的根放入EbbRoots集合里，并把它作为r调用Build_EBB(r, succ, pred)；然后对EbbRoots中的join node队列依次调用Build_EBB(r, succ, pred)，得到所有EBB。 7.2 深度/广度优先搜索，前序/后序遍历 略 7.3 Dominators和PostDominators 7.3.1 dom，idom基本概念 dominate(简写为dom) 是一个二元关系，a dom b表示从CFG的entry节点到b节点的任意一条路径都会经过a节点。这时把a叫做b的dominator。 idom关系由dom关系得来，a idom b表示a dom b，且不存在节点c同时满足a dom c、c dom b。 由CFG的节点集N和idom关系构成的边集组成一棵树，叫idom树，这棵树反映了CFG上所有节点间dom和idom关系。 求dominator和idominator 求dominator的常规算法用的是迭代计算的方法，收敛结果即所求每个节点的domintor集合。该算法大家比较熟悉，略。 求idominator的算法要基于domintor算法的结果，用下图来简单阐述： 《muchnick一书》p184 Fig7.15 思想：任取节点i属于Domin(n)-{n}，固定i