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

摘要：

基于Cytron和Cooper等人的研究成果,提出了一个新的概念--支配边界逆转(dominator frontier inverse,DFI)来同时为多个变量摆放Φ函数.如果结点y以结点x为支配边界,则结点x就是结点y支配边界逆转.支配边界逆转存在一个很重要的属性,DFI(x)中的结点在支配树上的高度一定不小于x的高度.对DFJ(x)中任何结点y,如果存在对于变量v的定叉,则结点x上就需要插入变量v的Φ函数.由于采用PHI(x)表示在结点x上需要插入Φ函数的变量集合,实现过程中并不需要实际计算DFI结点集合.算法首先按照结点在支配树上的高度自底向上进行遍历,并逐层计算高度相同的交结点上摆放Φ函数的变量集合PHI的不动点.算法的主要优点是可以直接工作于支配树上,不需要额外的数据结构.C Specint 2000的测试结果表明该算法比Cytron原始的Φ函数摆放算法要快,并且与采用Cooper计算支配边界的算法相比,该算法对测试集中大部分程序也是有效的.

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

所属期刊栏目：48

分类号：TP311(计算技术、计算机技术)

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

在线出版日期：2011-06-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：346-352