控制流图上支配关系计算方法的分析与实现  

Analysis and Implementation of the Computation of Dominator in CFG

作　　者：马红途[1,2] 赵荣彩[1] 苏彦兵[2] 

机构地区：[1]信息工程大学信息工程学院,郑州450002 [2]信息工程技术研究所,北京102249

出　　处：《计算机科学》2009年第3期54-57,77,共5页Computer Science

基　　金：国家863计划资助项目(2006AA01Z408)资助

摘　　要：支配关系在数据流分析和静态单赋值等程序分析和优化中应用很广泛。采用位向量表示支配结点集合,描述了采用迭代法计算控制流图上支配结点集合的算法,在支配结点集合的基础上讨论了对直接支配结点、支配边界结点的计算方法,并在NPB和SPEC2000测试集上进行了测试。测试结果表明:控制流图的构建占用了过程内支配关系计算的几乎一半时间;对于不包含goto语句的结构化程序,迭代算法一般只需迭代2次。Compilers use dominance information extensively during program analysis and optimization, such as data-flow analysis and the computation of static single-assignment forms. The iterative method to compute dominators was discussed in detail, in which dominator relation is represented by bit vector. Based on the result of dominators, the method to compute immediate dominator and dominator frontier was given. At last, experimental results of NPB and SPEC2000 were presented,which show that construction of intraprocedual CFG takes almost half of the total time; if goto statement is not contained in structural program, the iterative algorithm will finish in two iterations.

关 键 词：控制流图 迭代算法 位向量 支配关系 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP391[自动化与计算机技术—计算机科学与技术]