Re: Wanted: a program that calulates the maximal stack depth

In article 92-04-044 hays@ssd.intel.com (Kirk Hays) writes:
>In article 92-04-029, samuel@nada.kth.se writes:
>|> ... I need a utility that calculates the maximal
>|> used-up stack space for each function in the code.
> ...
>What you need to do is to enumerate all instructions that
>change the top of stack (ENTER, EXIT, CALL, PUSH, POP, etc. as a
>hypothetical set), and all instructions that cause a change of flow of
>control. That's all that you need to parse, and awk scripts are a fast
>and dirty way to implement the simple parsing that's needed.


Sorry to rain on everyone's parade, but calculating the maximum
stack space used by a program is undecidable. (More precisely, deciding
if a program uses less than k elements of the stack is undecidable.)
While, as Kirk points out, it's easy to determine how much stack space a
piece of _straight_line_ code uses, if a program is allowed to have
_single_ loop it is possible to code up a Turing machine, using the stack
as the tape. If we could determine the maximum amount of stack space this
program could use, then we could determine if the machine would halt or
not.


Of course, if we limit ourselves to programs without recursion, or
containing only loops that use zero stack space within the loop, this
problem goes away, but I don't think that these are very interesting
programs, or address the original poster's question.
[As with many undecidable or NP-complete questions, there are easily solvable
subsets that are often quite useful. In this case, if you are trying to
ensure that your embedded application won't use more stack RAM than is
physically present in the system, both the program and and question can be
pretty interesting, at least to some people. -John]
--

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