Fast optimal instruction scheduling for single-issue processors with arbitrary latencies

Abstract Instruction scheduling is one of the most important steps for improving the performance of object code produced by a compiler. The local instruction scheduling problem is to nd a minimum length instruction schedule for a basic block subject to precedence, latency, andresource constraints.Inthispaperwe consider local instruction scheduling for single-issue processors with arbitrary latencies. The problem is considered intractable, and heuristic approaches are currently used in production compilers. In contrast, we present a relatively simple approach to instruction scheduling based on constraint programming which is fast and optimal. The proposed approach usesanimproved constraint model which allows it to scale up to very large, real problems. We describe powerful redundant constraints that allow a standard constraint solver to solve thesescheduling problems in an almost backtrack-free manner. The redundant constraints are lower bounds on selected sub-problems which take advantage of the structure inherent in the problems. Under speci ed conditions, these constraints are sometimes further improved by testing the consistency of a sub-problem using a fast test. We experimentally evaluated our approach byintegrating it into the Gnu Compiler Collection (GCC) and then applying it to the SPEC95 oating point benchmarks. All 7402 of the benchmarks ' basic-blocks were optimally scheduled, including basic-blocks with up to 1000 instructions. Our results compare favorably to the best previous approach which is based on integer linear programming (Wilken et al., 2000): Across the same benchmarks, the total optimal scheduling time for their approach is98 seconds while the total time for our approach is less than 5 seconds.