3 Feb 1997 13:39:15 -0500

Related articles |
---|

Optimal emission of DAGS hasdi@umich.edu (1997-02-02) |

Re: Optimal emission of DAGS anton@a0.complang.tuwien.ac.at (1997-02-03) |

From: | anton@a0.complang.tuwien.ac.at (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@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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.