Re: Sizing the stack

Nils M Holm <nmh@freenet.de>
12 Mar 2001 02:36:21 -0500

          From comp.compilers

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)
| List of all articles for this month |

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.