Re: Optimal emission of DAGS (Anton Ertl)
3 Feb 1997 13:39:15 -0500

          From comp.compilers

Related articles
Optimal emission of DAGS (1997-02-02)
Re: Optimal emission of DAGS (1997-02-03)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: 3 Feb 1997 13:39:15 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 97-02-022
Keywords: tools, optimize (Hasdi Rodzmann Hashim) writes:
> I am looking for something similar to Sethi-Ullman method of emitting
> expression. In Sethi-Ullman method, you can emit an expression in the
> order that would use the least number of resources. This assumes that
> the expression is in a form of a tree. Is there a way to do something
> similar if the expression is in a form of a directed acyclic graph?

In general, this problem is NP-complete. Christoph Kessler has
developed a dynamic programming algorithm that is useable for DAGs
with up to around 50 nodes:

    author = {Christoph W. Ke{\ss}ler},
    title = {Scheduling Expression DAGs for Minimal Register Need},
    booktitle = {Programming Languages: Implementations, Logics, and
                                    Programs (PLILP'96)},
    series = {LNCS 1140},
    year = {1996},
    publisher = {Springer},
    pages = {228--242}

If you are also interested in suboptimal solutions, there are some
findings about heuristics for linear-time methods, read:

    author = "C. W. Ke{\ss}ler and W. J. Paul and T. Rauber",
    title = "A Randomized Heuristic Approach to Register Allocation",
    crossref = "plilp91",
    pages = "195--206"

    key = "PLILP'91",
    title = "Programming Language Implementation and Logic
Programming (PLILP)",
    booktitle = "Programming Language Implementation and Logic
Programming (PLILP)",
    year = "1991",
    OPTeditor = "Jan Ma{\l}uszy\'nski and Martin Wirsing",
    publisher = "Springer LNCS~528",
    address = "Passau"

- anton
M. Anton Ertl

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.