即时编译器中的轻量级指令调度算法

Lightweight Instruction Scheduling Algorithm for Just-in-time Compiler

介绍了一种为即时编译器和时空受限系统设计的轻量级线性复杂指令调度算法。该算法进行指令调度时,不基于传统的DAG图或表达式树,而是基于一种独创的数据结构扩展关联矩阵,其时间复杂性在最坏情况下也能与全部指令长度构成严格的线性关系,仅占用不到1 KB的内存空间。该算法已被Intel为Xscale设计的高性能J2ME虚拟机XORP采用为即时编辑器中的缺省指令调度算法。

This paper presents a novel lightweight algorithm of instruction scheduling for reducing the pipeline stalls on RISC micro-architecture with super pipelines. The algorithm is designed for and implemented in a J2ME JIT（just-in-time） compiler in memory constraint and time critical system. It is not based on DAG（directed acyclic graphs） or expression trees, but a novel data structure, namely EDM（extended dependency matrix）. The algorithm has strict linear time complexity to the code length in the worst cases. It consumes only about 1KB constant memory space, to fit the small memory footprint for J2ME configurations. This algorithm has been chosen as the default instruction scheduling solution in the JIT compiler by Intel＇s high-performance J2ME JVM, namely XORP.