Re: stack overflow at compile time

"Amit Gupta" <emailamit@gmail.com> writes:


> [You can't even get an upper bound in the general case. Imagine a
> program that reads in a number and uses that as the number of times to
> call itself recursively. -John]


You can always get an upper bound. It just might not be useful in
some cases. The upper bound in the above program would be "the size
of the address space".


GNAT (the gcc Ada compiler) does static stack-size analysis. I'm not
sure of all the details, but I think you can get a conservative upper
bound, or a not-so-conservative estimate based on user-provided
information about recursion depth and so forth.


Ada also requires run-time stack overflow checks, in cases where it
can't be statically determined.


GNAT also allows you to find out the stack depth used for any given
run of a program.


In many embedded systems, a static worst case is quite good enough,
because such programs might not need to use recursion,
dynamically-sized stack variables, and indirect calls.


- Bob Duff
    AdaCore Technologies


[It's not even the size of the address space. If my frame size is,
say, a megabyte, and my recursion is a million, I'm going to need a
million megabytes. If the system doesn't have a million megabytes,
well, shucks, my program will fail. I entirely agree that in many
useful special cases you can do static stack size analysis and come up
with a result, but in the general case, it's hopeless. -John]

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