摘要
支配关系在数据流分析和静态单赋值等程序分析和优化中应用很广泛。采用位向量表示支配结点集合,描述了采用迭代法计算控制流图上支配结点集合的算法,在支配结点集合的基础上讨论了对直接支配结点、支配边界结点的计算方法,并在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.
出处
《计算机科学》
CSCD
北大核心
2009年第3期54-57,77,共5页
Computer Science
基金
国家863计划资助项目(2006AA01Z408)资助
