Re: stack overflow at compile time

I wrote:


> 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".


Our esteemed moderator replied:


> [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.


My point was that there's no need to calculate max stack sizes bigger
than the address space. If I need a stack of 2**32 bytes, and you need
a stack of 2**40 bytes, both of our programs will fail equally
(on a 32-bit machine).


So a static stack size analyzer can do it's calculations using
saturating arithmetic, with an upper bound of the address space size.
We know we can never allocate a stack as big as the address space,
because there's always something else besides the stack we need memory
for.


So if we count up frame sizes, and we ever reach the address space size,
we can use that as the upper bound. Of course that's not a useful upper
bound. But it IS an upper bound, in the sense that you cannot create a
stack bigger than that (on this particular machine).


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


Yes, of course. Many kinds of embedded systems do not use recursion,
unbounded-size stack variables, heap data, etc...


- Bob

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