Re: stack overflow at compile time

Jatin Bhateja wrote:


> Hi,
>
> Is it possible at compile time to know whether there is a possibility of
> stack overflow at run time? I feel that to some extent it is possible.


To some extent.


> Let me explain it to you in detail. As compiler knows the stack offsets
> for all the locals/temporaries/function arguments so at compile time one
> can know the stack requirement of a particular function.


An upper bound as long as no variably sized objects are allowed.


> Now problem will occur in case of recursive function where if the
> condition of recursion is not calculable at compile time then one cannot
> make out the stack requirements.


Generally, yes.


> Another thing is that as the size of executable comprises code and
> global data it contains (of course not uninitialized global data) and at
> run time heap and stack space is allocated to the running executable. So
> if our OS is single tasking then only one program is present in memory
> at run time and so the maximum size of stack that can be used is size of
> the entire virtual memory. Thus under this circumstances if one knows
> the stack size requirement of a program then we can tell at compile time
> that stack overflow will occur or not.
>
> Also this decision will be taken by the linker (of course it will use
> some extra info about the stack requirement of a program that will be
> emitted by compiler) as only at that time the exact size of object file
> can be calculated by summing the size of each section of object file. We
> need to know the size of exe/object file because maximum stack available
> at run time will be virtual memory size - size of exe. Also no DLLs
> will be allowed,


You may want to have at my dissertation at:
http://www.ibaug.de/vb/diss-barthelmann.pdf


There I present in one chapter compile-time stack calculation for a
special class of applications (small embedded systems using static
operating systems, no recursions and restricted use of function
pointers) and also show some problems of other approaches.


Some sources of problems in practice are:
- code that cannot be analyzed, because it is only available in binary
    format or similar
- code that cannot be analyzed, because it does tricky stuff (e.g. some
    uses of function pointers, context-switching etc.)
- you can calculate an upper bound, but it is too far off the real
    stack-usage
- the programming-language in use is not well-suited for this problem


Hope that helps,


Volker
--
Dr. Volker Barthelmann EMail: vb@ibaug.de
Ingenieurbüro Barthelmann http://www.ibaug.de

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