Re: stack overflow at compile time

Our moderator writes:
>[This looks to me equivalent to the halting problem. That means there are some
>special cases you can solve, some of which are quite useful, but in general
>it's undecidable. -John]


This is true, but uninteresting. :-) All real programs are special cases
of one kind or another, as witness the fact that human beings reason
effectively (if not always correctly) about their programs' halting
behavior all the time.


In the absence of recursion or non-trivial dynamic allocation, bounding
stack size at compile time is obviously a straightforward problem:
generate the call graph, label each arc with the stack size of the routine
being called, and find the greatest "distance" from the root to a leaf.
The maximum may occur on a path that's actually impossible, but at least
you do get a bound.


As a practical matter, you'll need either compiler-linker cooperation or a
compiler that sees the whole program (including all libraries), but that's
no big deal.


I have a dim recollection that some commercial compiler systems for
microcontrollers (some of which have quite small fixed-size stacks) do
in fact do this.


Introducing recursion or significant dynamic allocation (either on the
stack, or counting against total memory and thus reducing available space
for the stack) complicates life badly; now you need to put constraints on
the dynamic behavior of the program. This isn't necessarily beyond the
reach of static analysis, but it's a lot more complicated, success isn't
assured (although failure may indicate a badly-written program), and
program annotation may be required. I don't immediately recall anyone
who's studied this seriously...
--
spsystems.net is temporarily off the air; | Henry Spencer
mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net

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