指令调度和寄存器分配的集成算法  

Integration of instruction scheduling and register allocation

作　　者：戴军[1] 戴桂兰[1] 张素琴[1] 田金兰[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《清华大学学报（自然科学版）》2004年第1期69-73,共5页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(60083004)

摘　　要：指令调度对于充分发挥现代高性能RISC(reducedinstructionsetcomputer)处理器的指令级并行处理能力至关重要。基于扩展的装入延时体系结构模型,提出了在代码生成过程中针对表达式树的森林的局部寄存器分配和局部指令调度的集成算法。此算法以DLS(delayed-loadschedulingalgorithm)算法为基础,在保持了使用寄存器少,算法复杂度低的特点的同时,还为适应新的模型和提高效率做了以下扩展:1)通过记录变量内存值的改变信息,设置调度缓冲区解决了多表达式树指令调度的数据相关性问题;2)将调度范围由单个表达式树扩展到森林更有效地减少指令延时;3)通过对调度生成的指令序列的局部调整来处理store延时,有效地减少了由于共享资源而引起的互锁。Instruction scheduling provides important optimization for current RISC (reduced instruction set computer) processors to achieve high performance by exploiting parallelism. This paper presents an integrated instruction scheduling and register allocation algorithm for processors with an extended delayed-load architecture. The algorithm is based on the delay-load scheduling algorithm using fewer registers and running at a speed proportional to the size of the expression tree. The algorithm also includes some extensions to improve performance: 1) resolve the data dependence of instruction scheduling for multiple expression trees by marking the memory information as changing and by setting a Load Cache; 2) extend the scheduling from expression trees to forests to more effectively reduce delays; 3) effectively reduce structural hazards by adjusting the order of local instructions.

关 键 词：指令调度 寄存器分配 集成算法 编译程序 表达式树 

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