Integrated Prepass Scheduling for a Java Just-in-time Compiler on the IA-64 Architecture
Tatsushi Inagaki, Hideaki Komatsu, Toshio Nakatani · 2003
We present a new integrated prepass scheduling (IPS) algorithm for a Java Just-In-Time (JIT) compiler, which in-tegrates register minimization into list scheduling. We use backtracking in the list scheduling when we have used up all the available registers. To reduce the overhead of back-tracking, we incrementally maintain a set of candidate in-structions for undoing scheduling. To maximize the ILP af-ter undoing scheduling, we select an instruction chain with the smallest increase in the total execution time. We im-plemented our new algorithm in a production-level Java JIT compiler for the Intel Itanium processor. The exper-iment showed that, compared to the best known algorithm by Govindarajan et al., our IPS algorithm improved the per-formance by up to +1.8 % while it reduced the compilation time for IPS by 58 % on average. 1.