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

In article 92-04-029, samuel@nada.kth.se writes:
|> I'm developing an application where the use of stack space is crucial.
|> The program almost only manipulates sequential structures and calls no
|> library functions. So what I need is a utility that calculates the maximal
|> used-up stack space for each function in the code.


People have been doing this in the real-time area for nearly two decades.


The techniques are fairly easy, although I've never seen anyone publish.
I've never looked, actually, as inventing my own methods seemed obvious.


|> [I'd think that in many cases it might be easier to scan the generated
|> assembler code for instructions that change the stack pointer. Several C
|> grammars are available, see the compilers FAQ. -John]


Exactly right. 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.


[as an aside, I've seen compilers that emitted this information]


At this point, a the simple parser, sufficient to deal with the assembly
language, produces output like:


main, uses 40 bytes, calls x,y,z
x, uses 200 bytes
y, uses 48 bytes, calls z
z, uses 300 bytes, calls x


(eliminate the syntactic sugar if you like)


Now, write a program that builds a directed graph of all the calls, each
node tagged with its "expense", and then runs the graph recursively,
looking for the most expensive path. There are various optimizations that
can be applied to running the graph - most of them are overkill for this
sort of analysis, so send me mail if you are interested. Dealing with
recursion, either direct or indirect, require human intervention.


Now, doing this with a procedure granularity leads to over-estimation, as
not every path through a procedure has the same cost. Typically, however,
I've never seen the over-estimation exceed 20%. If you need better data
than that, it is necessary to do actual flow-of-control analysis (which
I've also done), which can give you an exact static use figure.


However, even with the best static analysis, you must always keep the
stack usage of asyncronous events in mind, and also watch for human coded
idioms, like pushing the address of a label on the stack, then popping the
program counter, the equivalent of a call without a return address on the
stack.


I'm sure someone will mention filling the stack with "guard" values,
exercising the program, and then checking how far down the stack you went
- this is a good empirical technique, and useful for confirming the static
analysis estimate, but keep in mind that few programs can be fully
exercised.
--
Kirk Hays
--

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