| 摘要: |
| 基本块重排是一类通过重新排布基本块在存储中的位置,以减少转移开销和指令cache失效率的编译优化技术.介绍了一种基于子结构分析的基本块重排算法.该算法通过统计剖视信息中控制流图的边执行频率,基于处理器转移预测策略构建转移开销模型和基本块排布收益模型.算法采用局部子结构优化的策略,改善基本块在存储中的排列顺序,从而减少转移开销,并提高指令cache的使用率,改善程序的总体性能.在UniCore处理器平台上进行了实验.实验结果表明,与其他基本块重排算法相比,该基本块重排算法在更大程度上减少转移开销和指令cache失效率的同时,其时间复杂度保持为O(n(logn). |
| 关键词: 基本块重排 子结构分析 编译优化 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National High-Tech Research and Development Plan of China under Grant Nos.2002AA1Z2203, 2003AA1Z1010, 2005AA111010 (国家高技术研究发展计划(863)) |
|
| A Basic-Block Reordering Algorithm Based on Structural Analysis |
|
LIU Xian-Hua,YANG Yang,ZHANG Ji-Yu,CHENG Xu
|
| Abstract: |
| 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). |
| Key words: basic-block reordering structural analysis compiler optimization |
