Re: stack overflow at compile time

henry@spsystems.net (Henry Spencer)
30 Apr 2006 18:37:23 -0400

          From comp.compilers

Related articles
[5 earlier articles]
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)
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: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 30 Apr 2006 18:37:23 -0400
Organization: SP Systems, Toronto, Canada
References: 06-04-157 06-04-161 06-04-162
Keywords: storage, analysis

glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:
>> The maximum may occur on a path that's actually impossible, but at least
>> you do get a bound.
>
>But it is difficult to tell at compile time which routines are actually
>called, even though you may know there is no recursion and only fixed
>sized allocation. You could, then, way overestimate the stack usage.


As I said, the "worst-case" path may in fact be an impossible one. More
sophisticated static analysis may be able to prune some of the impossible
paths, but it's much more expensive, and the improvement may be limited.


Yes, it's possible for the simple analysis to badly overestimate usage.
How serious that is, depends on how frequently it happens and how much an
overestimate hurts.


>With recursion you could easily underestimate it, not knowing the
>maximum recursion level.


If you want trustworthy results, the analysis has to assume that recursion
depth is potentially unlimited (consider Ackermann's Function) unless it
is bounded by user annotations or more sophisticated static analysis.
--
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.