Optimal versus Heuristic Global Code Scheduling

We present a global instruction scheduler based on integer linear programming (ILP) that was implemented experimentally in the Intel Itaniumreg product compiler. It features virtually the full scale of known EPIC scheduling optimizations, more than its heuristic counterpart in the compiler, GCS, and in contrast to the latter it computes optimal solutions in the form of schedules with minimal length. Due to our highly efficient ILP model it can solve problem instances with 500-750 instructions, and in combination with region scheduling we are able to schedule routines of arbitrary size. In experiments on five SPECreg CPU2006 integer benchmarks, ILP-scheduled code exhibits a 32% schedule length advantage and a 10% runtime speedup over GCS-scheduled code, at the highest compiler optimization levels typically used for SPEC submissions. We further study the impact of different code motion classes, region sizes, and target microarchitectures, gaining insights into the nature of the global instruction scheduling problem.