Re: stack overflow at compile time

Robert A Duff <bobduff@shell01.TheWorld.com>
1 May 2006 20:14:09 -0400

          From comp.compilers

Related articles
[7 earlier articles]
Re: stack overflow at compile time jatin.bhateja@conexant.com (Jatin Bhateja) (2006-04-28)
Re: stack overflow at compile time emailamit@gmail.com (Amit Gupta) (2006-04-29)
Re: stack overflow at compile time bobduff@shell01.TheWorld.com (Robert A Duff) (2006-04-29)
Re: stack overflow at compile time emailamit@gmail.com (Amit Gupta) (2006-04-30)
Re: stack overflow at compile time henry@spsystems.net (2006-04-30)
Re: stack overflow at compile time henry@spsystems.net (2006-04-30)
Re: stack overflow at compile time bobduff@shell01.TheWorld.com (Robert A Duff) (2006-05-01)
Re: stack overflow at compile time gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-05-03)
| List of all articles for this month |

From: Robert A Duff <bobduff@shell01.TheWorld.com>
Newsgroups: comp.compilers
Date: 1 May 2006 20:14:09 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 06-04-157 06-04-161 06-04-166 06-04-177 06-04-178
Keywords: analysis

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


Post a followup to this message

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