一种基于子结构分析的基本块重排算法  

A Basic-Block Reordering Algorithm Based on Structural Analysis

作　　者：刘先华[1] 杨阳[1] 张吉豫[1] 程旭[1] 

机构地区：[1]北京大学计算机科学技术系,北京100871

出　　处：《软件学报》2008年第7期1603-1612,共10页Journal of Software

基　　金：the National High-Tech Research and Development Plan of China under Grant Nos.2002AA1Z2203;2003AA1Z1010;2005AA111010(国家高技术研究发展计划(863))

摘　　要：基本块重排是一类通过重新排布基本块在存储中的位置,以减少转移开销和指令cache失效率的编译优化技术.介绍了一种基于子结构分析的基本块重排算法.该算法通过统计剖视信息中控制流图的边执行频率,基于处理器转移预测策略构建转移开销模型和基本块排布收益模型.算法采用局部子结构优化的策略,改善基本块在存储中的排列顺序,从而减少转移开销,并提高指令cache的使用率,改善程序的总体性能.在UniCore处理器平台上进行了实验.实验结果表明,与其他基本块重排算法相比,该基本块重排算法在更大程度上减少转移开销和指令cache失效率的同时,其时间复杂度保持为O(n×logn).Basic-Block reordering is a kind of compiler optimization technique which has the effect of reducing branch penalty and I-cache miss cost by reordering basic blocks in memory. A new basic-block reordering algorithm based on structural analysis is presented. The algorithm takes the architectural branch cost model and basic-block layout cost model into consideration, uses the execution frequencies of control-flow edges from profile information, builds a local structural optimization policy and utilizes it in reordering program＇s basic blocks. The algorithm is implemented based on UniCore architecture, experimental results show that it better improved programs＇ performance with a complexity of only O（n×logn）.

关 键 词：基本块重排 子结构分析 编译优化 

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