Generating Optimal Contiguous Evaluations for Expression DAGs

Christoph W. Keßler, Thomas Rauber

Computer Languages 21(2), 1995.


We consider the NP-complete problem of generating contiguous evaluations for expression DAGs with a minimal number of registers. We present two algorithms that generate optimal contiguous evaluation for a given DAG. The first is a modification of a complete search algorithm that omits the generation of redundant evaluations. The second algorithm generates only the most promising evaluations by splitting the DAG into trees with import and export nodes and evaluating the trees with a modified labeling scheme. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithms generate optimal contiguous evaluations quite fast.


This article presents an algorithm that computes a space-optimal contiguous schedule for basic blocks with DAG-structured data dependences. The goal is to mimimize the number of registers used (minimum register instruction scheduling problem, MRIS), subject to the constraint that the schedules taken into consideration must be generatable by postorder traversals of the dependence graph.


@article{ Kessler_j1,
 author = {Christoph W. Ke{\ss}ler and Thomas Rauber},
 title = {Generating Optimal Contiguous Evaluations for Expression {DAG}s},
 journal = {Computer Languages},
 volume = {21}, number = {2},
 pages = {113--127},
 year = {1995}


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