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

eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Fri, 10 Apr 1992 17:20:48 GMT

          From comp.compilers

Related articles
Wanted: a program that calulates the maximal stack depth samuel@nada.kth.se (1992-04-06)
Re: Wanted: a program that calulates the maximal stack depth russw@cs.utexas.edu (1992-04-09)
Re: Wanted: a program that calulates the maximal stack depth bliss@sp64.csrd.uiuc.edu (1992-04-09)
Re: Wanted: a program that calulates the maximal stack depth hays@ssd.intel.com (1992-04-09)
Re: Wanted: a program that calulates the maximal stack depth pbk@arkesden.Eng.Sun.COM (1992-04-10)
Re: Wanted: a program that calulates the maximal stack depth eifrig@beanworld.cs.jhu.edu (1992-04-10)
Re: Wanted: a program that calulates the maximal stack depth samuel@nada.kth.se (1992-04-11)
| List of all articles for this month |

Newsgroups: comp.compilers
From: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Keywords: code, storage
Organization: The Johns Hopkins University CS Department
References: 92-04-029 92-04-044
Date: Fri, 10 Apr 1992 17:20:48 GMT

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


Post a followup to this message

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