基于支配边界逆转的多变量Φ函数摆放算法  

A Multi-Variable Φ-Function Placement Algorithm Based on Dominator Frontier Inverse

作　　者：马红途[1,2] 胡世安[1] 苏彦兵[1] 李迅[1] 赵荣彩[2] 

机构地区：[1]海军装备研究院,北京102249 [2]解放军信息工程大学信息工程学院,郑州450002

出　　处：《计算机研究与发展》2011年第2期346-352,共7页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2006AA01Z408)

摘　　要：基于Cytron和Cooper等人的研究成果,提出了一个新的概念——支配边界逆转(dominatorfrontier inverse,DFI)来同时为多个变量摆放Φ函数.如果结点y以结点x为支配边界,则结点x就是结点y支配边界逆转.支配边界逆转存在一个很重要的属性,DFI(x)中的结点在支配树上的高度一定不小于x的高度.对DFI(x)中任何结点y,如果存在对于变量v的定义,则结点x上就需要插入变量v的Φ函数.由于采用PHI(x)表示在结点x上需要插入Φ函数的变量集合,实现过程中并不需要实际计算DFI结点集合.算法首先按照结点在支配树上的高度自底向上进行遍历,并逐层计算高度相同的交结点上摆放函数的变量集合PHI的不动点.算法的主要优点是可以直接工作于支配树上,不需要额外的数据结构.C Specint 2000的测试结果表明该算法比Cytron原始的Φ函数摆放算法要快,并且与采用Cooper计算支配边界的算法相比,该算法对测试集中大部分程序也是有效的.Based on the work of Cytron and Cooper,we employ the concept of dominance frontier inverse（DFI） to present an iterative algorithm to simultaneously place -nodes for all variables of a function.The set DFI（x） is a set of the nodes N whose dominance frontier is x.The set DFI（x） has one important property： The nodes in the set DFI（x） must be the nodes whose level is no smaller than the level of x on the dominator tree.For each node y contained in the set DFI（x）,the variables defined on node y should be placed on node x,and if there are -nodes only,the variables of Φ-nodes should also be placed on x.In fact,the DFI set needn＇t be computed when placing Φ-nodes in the algorithm of this paper,because a variable set is adopted to hold the Φ-nodes.The algorithm firstly visits the dominator tree in a bottom-up traversal by levels,and then iteratively computes fixed point for the Φ-nodes sets on the join nodes with the same level.The innovation is that the algorithm can directly work on the dominator tree.And it merges the former two-step algorithm into one.Experimental results of the C Specint2000 show that this algorithm is much faster than Cytron＇s original algorithm,and is also comparable with Cytron＇s Φ-placement algorithm based on Cooper＇s DF algorithm.

关 键 词：静态单赋值 支配边界 支配边界逆转 Φ结点 DJ图 

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