Stack size calculation - tool support?

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.

Reply to
Gerd
Loading thread data ...

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

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

formatting link

Reply to
Vladimir Vassilevsky

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.

Reply to
D Yuniskis

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
Reply to
Tim Wescott

"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
Reply to
Tim Wescott

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.

Reply to
robertwessel2

  • 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

formatting link

Reply to
Vladimir Vassilevsky

[...]

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

formatting link

Reply to
Vladimir Vassilevsky

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

formatting link

Reply to
Vladimir Vassilevsky

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

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

formatting link

Reply to
Vladimir Vassilevsky

But I guess the compiler should know the worst case.

--
42Bastian
Do not email to bastian42@yahoo.com, it's a spam-only account :-)
 Click to see the full signature
Reply to
42Bastian Schick

Reasonably bounded and very estimable.

The register set is finite.

Very limited effect.

I would say that this is very estimable.

We're talking C here.

Can't be a lot.

This would just split one estimate into multiple.

A good analyser will be able to find the 'root' functions.

None of these will make it _impossible_ to estimate stack depth. Most are known to hover around a statistical average, with reasonably known bounds for all except the most obscure systems. Maybe you're expecting too much from an estimation?

--
Gemaakt met Opera's revolutionaire e-mailprogramma:  
http://www.opera.com/mail/
 Click to see the full signature
Reply to
Boudewijn Dijkstra

Tools exist, but they must analyse machine code, not source, so they are processor-specific. And sometimes also cross-compiler-specific, because some compilers use only the processor hardware stack, while others use additional software-defined stacks.

Some tools I know of:

- AbsInt StackAnalyzer

formatting link

- Bound-T

formatting link
Declaration of bias: this is my tool.

- gnatstack

formatting link

- A tool in TinyOS

formatting link

I believe that more than one cross-compiler also has stack-analysis tools. Check with Keil, IAR, ICC. Of course, it is not enough to have this function in the compiler, the linker must also cooperate (unless you have a whole-program-at-once compiler... lucky you :-)

Gerd, for more specific answers please tell us your target processor and cross-compiler tools.

--
Niklas Holsti
Tidorum Ltd
 Click to see the full signature
Reply to
Niklas Holsti

One more tool:

- AVR StackSummary for IccV7

formatting link

--
Niklas Holsti
Tidorum Ltd
 Click to see the full signature
Reply to
Niklas Holsti

I don't know what I might be missing, BUT if you have the source code and you know the target, you should be able to make a pretty good "worse case", assuming no recursion, or at least no bounded recursion, AND worse case would be what you want to plan for, isn't it? I have one compiler that even spits the numbers out for you.

Jim

Reply to
WangoTango

With a few minutes of effort and access to the code generated for a couple example functions, you can calibrate your "guessing" algorithm so that it's going to be pretty close.

That used to be a pretty common feature in cross-compilers aimed at the embedded system market. Some of them would even analyze static call-trees and add up the numbers for you.

--
Grant Edwards                   grante             Yow! The entire CHINESE
                                  at               WOMEN'S VOLLEYBALL TEAM all
 Click to see the full signature
Reply to
Grant Edwards

Bollocks.

It is hard to know what modern optimizing compiler would generate from your source but in trivial cases.

As for wild guesswork, I know that my threads rarely use less then 512B or more then 1K of stack. The 1K or 2K of allocation doesn't really make any difference, so the exact size of stack is not very important.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

formatting link

Reply to
Vladimir Vassilevsky

You need to know the minute details of the compiler's code generation algorithm.

You can't assume that the stack consists precisely of the set of explicitly-declared variables and parameters. The compiler is free to introduce temporaries as it sees fit, and to eliminate or overlay variables.

Reply to
Nobody

But the original task (and particularly Vladimir's statement, which you're arguing against here) was about doing it from the source code

*only* (emphasis mine). The compiler has a lot of knowledge about its own working which is _not_ contained in the source code. I.e. the very same source code can have quite different stack usage, by changing target platform, compiler, or even compiler options, making analysis from source alone obviously impossible. At the very least, you need sizeof() numbers from the same compiler (and applicable options the same, too) that the code is built with.

But even so, the original task is indeed generally impossible --- yes, even without recursion. The reason for that are function pointers.

As soon as there is any non-trivial use of function pointers, the call tree can become useless, because statically analyzing what those function pointers may be pointing to at a given call site is equivalent to the Halting Problem, and thus intractable. So basically, any call by pointer becomes equivalent to a random call to one of _all_ the functions (of compatible signature, if you're inclined to trust your coders at least that far...) that were assigned to function pointers anywhere in the program. If you're really unlucky, this might introduce apparent recursion that doesn't exist in the actual program, and thus blow the whole static stack analysis approach right out of the water.

>
Reply to
Hans-Bernhard Bröker

True, but a pessimistic view. It is impossible to analyse all programs. But some programs are analysable, and "well-written" programs often are. Moreover, some compilers can help.

For example, considering virtual-function calls in C++, the IAR C++ compilers store the class graph in the debug info, and also indicate the compile-time class for every call to a virtual function. This means that a static analyzer can make a call-graph that is safe (contains all possible virtual-function calls) although over-estimated (at run-time, depending on the actual classes of the objects, perhaps some of the calls are infeasible). This can lead to an over-estimated stack-size bound, but overestimation is common for static analysis, and is often acceptably small.

Lots of things in program analysis are as difficult as the Halting Problem, yet analysis often works for the programs that occur in practice.

A program-wide pointer analysis can give better results, even for C code and without compiler assistance.

True, imprecise pointer analysis may create apparent recursion. But recursion (apparent or real) does not necessarily prevent static stack-size analysis, any more than looping prevents static execution-time analysis; you only have to find bounds on the recursion depth, as you have to find loop iteration bounds for the execution-time analysis. For an apparent but not true recursion, the recursion depth bound is of course zero.

--
Niklas Holsti
Tidorum Ltd
 Click to see the full signature
Reply to
Niklas Holsti

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.