Scheduling expression DAGs for minimal register need

Christoph W. Keßler

Computer Languages 24(1), 1998.


Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n!) enumeration algorithm. We present a new algorithm with worst-case complexity O(n22n) and very good average behavior. Applying a dynamic programming scheme and reordering techniques, our algorithm is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors.


Program optimization; Basic block; Expression DAG; Instruction scheduling; Register allocation; Code generation.


 author = {Christoph W. Ke{\ss}ler},
 title = {Scheduling {E}xpression {DAG}s for {M}inimal {R}egister {N}eed},
 journal = {Computer Languages},
 volume = {24},
 number = 1,
 pages = {33--53},
 month = September,
 year = 1998


Copyright notice: This section contains links to material covered by copyright; copyright may be held by the author and/or the publisher. You may browse them at your convenience (in the same spirit as you may read a journal or a proceedings article in a public library). Retrieving, copying, or distributing these files, however, may violate the copyright protection law. We recommend that the user obey international law in accessing this directory.
Note also that the material made accessible below may be based on a submitted version and thus differ in minor details from the published version.

Christoph Kessler