|Sizing the stack firstname.lastname@example.org (Kevin Kilzer) (2001-03-10)|
|Re: Sizing the stack email@example.com (Nils M Holm) (2001-03-12)|
|From:||Nils M Holm <firstname.lastname@example.org>|
|Date:||12 Mar 2001 02:36:21 -0500|
|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.
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.
Nils M Holm <email@example.com> -- http://www.t3x.org/
Return to the
Search the comp.compilers archives again.