OPTIMAL BASIC BLOCK INSTRUCTION SCHEDULING FOR MULTIPLE-ISSUE PROCESSORS USING CONSTRAINT PROGRAMMING

Instruction scheduling is one of the most important steps for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block — a straight-line sequence of code with a single entry point and a single exit point — subject to precedence, latency, and resource constraints. Solving the problem exactly is NP-complete, and heuristic approaches are currently used in most compilers. In contrast, we present a scheduler that finds provably optimal schedules for basic blocks using techniques from constraint programming. In developing our optimal scheduler, the key to scaling up to large, real problems was in the development of preprocessing techniques for improving the constraint model. We experimentally evaluated our optimal scheduler on the SPEC 2000 integer and floating point benchmarks. On this benchmark suite, the optimal scheduler was very robust — all but a handful of the hundreds of thousands of basic blocks in our benchmark suite were solved optimally within a reasonable time limit — and scaled to the largest basic blocks, including basic blocks with up to 2600 instructions. This compares favorably to the best previous exact approaches.