一个基于DAG图的指令调度优化算法

指令调度是优化编译技术中一项关键技术，对于VLIW体系结构的CPU，指令调度显得尤为重要。指令调度是在保证语义正确的前提下，改变指令的执行顺序，减少流水线中的空闲周期，从而提高CPU性能的一种优化方法。文章着重分析了优化编译中的指令调度问题，提出了一个指令调度算法和DAG图的一种化简方法，证明了算法的正确性，分析了算法的效率，比较了生成的新指令序列和最优的指令序列总的执行时间的差别。同时，针对目前流行的编译器GCC的指令调度算法中存在的问题，提出了一个较好的解决途径。

A Scheduling Algorithm Based on DAG Graph

： Instruction scheduling is essential in compiler optimization，especially for VLIW architectures．Changing the execution order of instructions，can eliminate the idle cycles in pipelines，and thus achieve higher performance while guaranteeing the correctness．An instruction－scheduling algorithm based on DAG graph is described in this paper with its correctness and efficiency analyzed．A method of simplifying a DAG is also discussed which will further improve the efficiency of the scheduling algorithm．An instruction－scheduling problem of GCC compiler is also mentioned with corresponding solution．