(PDF) Abid M. Malik, Jim McInnes, and Peter van Beek. Optimal basic block instruction scheduling for multiple-issue processors using constraint programming. Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence, Washington, DC, 279-287, November, 2006. A longer version appears in the International J. of AI Tools, (PDF), 17:37-54, 2008.
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 {\em 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.
An implementation of the constraint programming approach to local instruction scheduling for multiple-issue processors described in the paper: README, schedule.tar.gz