A novel lightweight instruction scheduling algorithm for Just-In-Time compiler

In this paper, we present a lightweight algorithm of instruction scheduling to reduce the pipeline stalls on XScale. The algorithm is designed for and implemented in a J2ME Just-In-Time (JIT) compiler. It is not based on Directed Acyclic Graphs (DAGs) or expression trees, but a novel data structure namely extended dependency matrix (EDM). The algorithm has almost linear time complexity to one order of magnitude less of the code length in practice, and linear to the code length in the worst cases. It consumes only about 1 KB constant memory space. On the benchmarks we studied, it can eliminate up to 41% data dependency stalls at runtime. The algorithm is on average 2 times faster than a list scheduling implementation, in terms of compilation time. On all benchmarks we studied, the performance is more than 90% as efficient as that obtained using more time and memory consuming algorithms on average.