12 Mar 2001 02:36:21 -0500

Related articles |
---|

Sizing the stack kkilzer@inficad.com (Kevin Kilzer) (2001-03-10) |

Re: Sizing the stack nmh@freenet.de (Nils M Holm) (2001-03-12) |

From: | Nils M Holm <nmh@freenet.de> |

Newsgroups: | comp.compilers |

Date: | 12 Mar 2001 02:36:21 -0500 |

Organization: | Compilers Central |

References: | 01-03-073 |

Keywords: | assembler, tools |

Posted-Date: | 12 Mar 2001 02:36:21 EST |

*> I need a tool that, given assembly language files, can calculate the*

*> maximum depth of the stack that will be used by a program, counted*

*> from some specified entry point.*

*> [...]*

*> [In general it's undecidable, but I'd imagine one could write a static*

*> analyzer that could produce useful results for a lot of real programs.*

*> -John]*

In fact, this problem is equivalent to finding the longest path in a

graph. Each procedure P is a vertex and the distance to each child

(callee) of P is equal to the stack size of P. As long as no procedure

recurses, the graph is a tree, and therefore, finding the longest path

is trivial. If only a single procedure recurses, the problem is indeed

undecidable, but in this case, you can still compute the *minimum*

stack size and use it as a basis for further estimations.

Bye,

nmh.

--

Nils M Holm <nmh@t3x.org> -- http://www.t3x.org/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.