Re: stack overflow at compile time

henry@spsystems.net (Henry Spencer)
27 Apr 2006 23:33:33 -0400

          From comp.compilers

Related articles
stack overflow at compile time jatin.bhateja@conexant.com (Jatin Bhateja) (2006-04-27)
Re: stack overflow at compile time NOSPAMrszeflerNOSPAM@murator.com.pl (RobertSzefler) (2006-04-27)
Re: stack overflow at compile time vb@compilers.de (Volker Barthelmann) (2006-04-27)
Re: stack overflow at compile time nitin@CoWare.com (Nitin Gupta) (2006-04-27)
Re: stack overflow at compile time henry@spsystems.net (2006-04-27)
Re: stack overflow at compile time gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-04-28)
Re: stack overflow at compile time jvorbrueggen@mediasec.de (=?ISO-8859-1?Q?Jan_Vorbr=FCggen?=) (2006-04-28)
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)
[4 later articles]
| List of all articles for this month |

From: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 27 Apr 2006 23:33:33 -0400
Organization: SP Systems, Toronto, Canada
References: 06-04-157
Keywords: storage, theory

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



Post a followup to this message

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