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

作者：马红途; 胡世安; 苏彦兵; 李迅; 赵荣彩

来源：Z201102028, 2011, (02): 346-352.

• 静态单赋值
• 支配边界
• 支配边界逆转
• Φ结点
• DJ图 static single assignment form
• dominance frontier
• dominance frontier inverse(DFI)
• Φ-node
• DJ graph

基于Cytron和Cooper等人的研究成果,提出了一个新的概念——支配边界逆转(dominatorfrontier inverse,DFI)来同时为多个变量摆放Φ函数.如果结点y以结点x为支配边界,则结点x就是结点y支配边界逆转.支配边界逆转存在一个很重要的属性,DFI(x)中的结点在支配树上的高度一定不小于x的高度.对DFI(x)中任何结点y,如果存在对于变量v的定义,则结点x上就需要插入变量v的Φ函数.由于采用PHI(x)表示在结点x上需要插入Φ函数的变量集合,实现过程中并不需要实际计算DFI结点集合.算法首先按照结点在支配树上的高度自底向上进行遍历,并逐层计算高度相同的交结点上摆放函...

• 出版日期2011
• 单位中国人民解放军海军装备研究院; 中国人民解放军信息工程大学