Re: Optimal emission of DAGS

hasdi@umich.edu (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:


@InProceedings{kessler96,
    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:


@InProceedings{kessler+91,
    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"
}


@Proceedings{plilp91,
    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
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html
--

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