Re: Sizing the stack

> 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/

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