Scheduling expression DAGs for minimal register need
Christoph W. Keßler
Computer Languages 24(1), 1998.
Abstract:
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.
Keywords:
Program optimization; Basic block; Expression DAG; Instruction scheduling; Register allocation; Code generation.
BibTeX:
@article{kessler_j4,
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
}
Download:
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