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

Lightweight Instruction Scheduling Algorithm for Just-in-time Compiler

作　　者：史晓华[1] 刘超[1] 金茂忠[1] 郭鹏 

机构地区：[1]北京航空航天大学软件工程研究所,北京100083 [2]英特尔微处理器研究院,北京100086

出　　处：《计算机工程》2007年第15期3-6,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60573084);英特尔研究基金资助项目

摘　　要：介绍了一种为即时编译器和时空受限系统设计的轻量级线性复杂指令调度算法。该算法进行指令调度时,不基于传统的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.

关 键 词：指令调度 即时编译器 JAVA虚拟机 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]