Instruction Scheduling After Register Allocation

This chapter presents a postpass instruction scheduling technique suitable for just-in-time (JIT) compilers targeted to VLIW processors. Just-in-time (JIT) compilation of programs distributed as Java or .NET Common Language Infrastructure (CLI) byte-codes are becoming increasingly relevant for consumer electronics applications. The chapter proves that the new postpass instruction scheduling preserves the instruction schedules created by prepass scheduling and software pipelining, provided that register allocation and basic block alignment only introduced redundant scheduling constraints. It reviews local instruction scheduling heuristics and propose scoreboard scheduling. The chapter then describes an optimized implementation of the technique. In addition, it discusses inter-region instruction scheduling and introduces inter-block scoreboard scheduling. This technique relies on iterative scheduling constraint propagation. Finally, the chapter provides an experimental evaluation of the contributions, which are implemented in the STMicroelectronics CLI-JIT compiler that targets the ST200 VLIW and the ARM processors.