计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2011年
2期
346-352
,共7页
马红途%胡世安%苏彦兵%李迅%赵荣彩
馬紅途%鬍世安%囌彥兵%李迅%趙榮綵
마홍도%호세안%소언병%리신%조영채
静态单赋值%支配边界%支配边界逆转%Φ结点%DJ图
靜態單賦值%支配邊界%支配邊界逆轉%Φ結點%DJ圖
정태단부치%지배변계%지배변계역전%Φ결점%DJ도
基于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计算支配边界的算法相比,该算法对测试集中大部分程序也是有效的.
基于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計算支配邊界的算法相比,該算法對測試集中大部分程序也是有效的.
기우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계산지배변계적산법상비,해산법대측시집중대부분정서야시유효적.
