I need to allocate the stack for my system with a proper size. I don't
want do a vage estimation, so I would like to know: Is there a tool
that scans C source code, and calculates the required tack size, based
on the call graph? Only plain C, no recursion.

Any suggestions are welcome.

Thanks.

Gerd wrote:

> I need to allocate the stack for my system with a proper size. I don't
> want do a vage estimation, so I would like to know: Is there a tool
> that scans C source code, and calculates the required tack size, based
> on the call graph? Only plain C, no recursion.

It is impossible to estimate stack depth from the source code only.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

Gerd wrote:
> I need to allocate the stack for my system with a proper size. I don't
> want do a vage estimation, so I would like to know: Is there a tool
> that scans C source code, and calculates the required tack size, based
> on the call graph? Only plain C, no recursion.

This is hard to do to any degree of accuracy as it depends on
the sizes of various data types, etc.

You can instrument your code to get a quick feel for this
(e.g., fill the stack with a known data pattern, run the code
and then examine the stack to see how much of it was disturbed).
But, to do this, you need to understand how your code is
*intended* to work so that you can come up with the appropriate
"test case" to bring about maximum stack penetration.

Programming style can also impact how easy this is. E.g,
if you have lots of autovariables in scattered/nested blocks
throughout a function you have to be more observant than
if they are all lumped in one place.

On Mon, 16 Nov 2009 16:37:47 -0600, Vladimir Vassilevsky wrote:

> Gerd wrote:
> 
>> I need to allocate the stack for my system with a proper size. I don't
>> want do a vage estimation, so I would like to know: Is there a tool
>> that scans C source code, and calculates the required tack size, based
>> on the call graph? Only plain C, no recursion.
> 
> It is impossible to estimate stack depth from the source code only.

Proof?  Reference to proof?

Absent recursion this should be a pretty direct calculation, if 
exceedingly tedious.  With recursion the answer is easy: "go back to 
school where you belong, buddy".

Granted, an RTOS makes life difficult, but even there the stack usage of 
any one task should be as easy (or impossible) to calculate as for a 
traditional single thread of execution.

-- 
www.wescottdesign.com

On Mon, 16 Nov 2009 14:19:02 -0800, Gerd wrote:

> I need to allocate the stack for my system with a proper size. I don't
> want do a vage estimation, so I would like to know: Is there a tool that
> scans C source code, and calculates the required tack size, based on the
> call graph? Only plain C, no recursion.
> 
> Any suggestions are welcome.
> 
> Thanks.

"Static code analysis tools" is, I think, the key words you want to 
search on.

Dunno what's out there for you, though.

-- 
www.wescottdesign.com

On Nov 16, 6:23=A0pm, Tim Wescott <t...@seemywebsite.com> wrote:
> On Mon, 16 Nov 2009 16:37:47 -0600, Vladimir Vassilevsky wrote:
> > Gerd wrote:
>
> >> I need to allocate the stack for my system with a proper size. I don't
> >> want do a vage estimation, so I would like to know: Is there a tool
> >> that scans C source code, and calculates the required tack size, based
> >> on the call graph? Only plain C, no recursion.
>
> > It is impossible to estimate stack depth from the source code only.
>
> Proof? =A0Reference to proof?
>
> Absent recursion this should be a pretty direct calculation, if
> exceedingly tedious. =A0With recursion the answer is easy: "go back to
> school where you belong, buddy".
>
> Granted, an RTOS makes life difficult, but even there the stack usage of
> any one task should be as easy (or impossible) to calculate as for a
> traditional single thread of execution.


Assuming no function pointers, you can compute a maximum based on the
call tree simply enough, but that may be a substantial overestimate
based on what sequences of calls are actually possible.  Consider:


void a() {... c(0); ...}

void b() {... c(1); ...}

void c(int p)
{
...
  if (p)
    d();
  else
    e();
...
}

void d() {...}

void e() {...}


Assume that a() and d() have large stack allocations, the
straightforward analysis will determine that a()->c()->d() results in
the worst case stack usage, when that's not actually possible because
of the control coupled call to d() or e() from c().

Also, function pointers make the analysis much harder.  Even if you
assume that no recursion will occur, the straight-forward approach
requires you to assume that you can call *any* routine that has its
address taken from *any* use of a function pointer to execute a call,
which will again likely result in a substantial overestimate.

Of course having a maximum is often a nice place to start.

Tim Wescott wrote:

> On Mon, 16 Nov 2009 16:37:47 -0600, Vladimir Vassilevsky wrote:
> 
> 
>>Gerd wrote:
>>
>>
>>>I need to allocate the stack for my system with a proper size. I don't
>>>want do a vage estimation, so I would like to know: Is there a tool
>>>that scans C source code, and calculates the required tack size, based
>>>on the call graph? Only plain C, no recursion.
>>
>>It is impossible to estimate stack depth from the source code only.
>  
> Proof?  Reference to proof?
> 

* Size and alignment
* Register variables
* Inlining, cross-call and interprocedural optimizations
* alloca
* Exceptions, RTTI, local storage and other implicit data
* Implicitly reserved stack space
* Possibly different stack spaces for data, code and interrupts
* Different contexts


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

r...@yahoo.com wrote:

> On Nov 16, 6:23 pm, Tim Wescott <t...@seemywebsite.com> wrote:
>>On Mon, 16 Nov 2009 16:37:47 -0600, Vladimir Vassilevsky wrote:
>>
>>>Gerd wrote:
>>
>>>>I need to allocate the stack for my system with a proper size. I don't
>>>>want do a vage estimation, so I would like to know: Is there a tool
>>>>that scans C source code, and calculates the required tack size, based
>>>>on the call graph? Only plain C, no recursion.
>>
>>>It is impossible to estimate stack depth from the source code only.
>>
>>Proof?  Reference to proof?
>>
>>Absent recursion this should be a pretty direct calculation, if
>>exceedingly tedious.  With recursion the answer is easy: "go back to
>>school where you belong, buddy".
>>
>>Granted, an RTOS makes life difficult, but even there the stack usage of
>>any one task should be as easy (or impossible) to calculate as for a
>>traditional single thread of execution.
> 
> 
> 
> Assuming no function pointers, you can compute a maximum based on the
> call tree simply enough,

[...]

 From the source code, you may be able to compute the depth of nesting, 
however you can only guess about required stack size.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

Tim Wescott wrote:

>>>I need to allocate the stack for my system with a proper size. I don't
>>>want do a vage estimation, so I would like to know: Is there a tool
>>>that scans C source code, and calculates the required tack size, based
>>>on the call graph? Only plain C, no recursion.
>>
>>It is impossible to estimate stack depth from the source code only.
> 
> Proof?  Reference to proof?
> 

Here is a simple code:

float fubar(float x)
{
return 1.2345 + 6789.0*sin(x);
}

Would you please tell me how many bytes of stack this function uses?
The answer is: it depends.



Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

D Yuniskis wrote:

> Gerd wrote:
> 
>> I need to allocate the stack for my system with a proper size. I don't
>> want do a vage estimation, so I would like to know: Is there a tool
>> that scans C source code, and calculates the required tack size, based
>> on the call graph? Only plain C, no recursion.
> 
> 
> This is hard to do to any degree of accuracy as it depends on
> the sizes of various data types, etc.

With modern optimizing compilers, the actual code has little resemblance 
to the original source code. You can't guess how the stack is used.

> You can instrument your code to get a quick feel for this
> (e.g., fill the stack with a known data pattern, run the code
> and then examine the stack to see how much of it was disturbed).

Yes, this is how it is done usually. Even if all required information to 
calculate the stack usage is available, not too many toolsets tell you 
exact numbers. Perhaps, this is not a simple problem.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com