Stack size calculation - looking for supporting tool

G

Gerd

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 stack size,
based on the call graph? Only plain C, no recursion.

Any suggestions are welcome.

Thanks.
 
J

jacob navia

Gerd a écrit :
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 stack size,
based on the call graph? Only plain C, no recursion.

Any suggestions are welcome.

Thanks.

I did that in the port of lcc-win to a 16 bit DSP.

The compiler would calculate the stack needed, and verify it did not
exceed 4K. Basically it started at main() and recursed at each call.
For each function it would remember the stack needed. Note that
that version did not use VLA's, and recursion was strictly forbidden.

I could adapt it for you but it would cost you some money.

jacob
 
L

Lew Pitcher

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 stack size,
based on the call graph? Only plain C, no recursion.

For all but the simplest of programs, this is just a variation of
the "halting problem". Essentially, the /exact/ size of automatic storage
(don't say "stack" around comp.lang.c; here, that word doesn't mean what
you think it means) is not readily calculable from an examination of the C
source code.

HTH
 
N

Nick

Lew Pitcher said:
For all but the simplest of programs, this is just a variation of
the "halting problem". Essentially, the /exact/ size of automatic storage
(don't say "stack" around comp.lang.c; here, that word doesn't mean what
you think it means) is not readily calculable from an examination of the C
source code.

Without recursion you should be able to get a worst case I think without
getting bogged down with the halting problem. As there's no recursion
you can construct a tree of the program structure, and assume that all
conditional calls happen. Then replace terminal nodes with the size of
their space, then nodes only calling terminals with the sum of the
terminals. Repeat until only one node is left. That sounds like it is
guaranteed to halt.
 
I

Ian Collins

Nick said:
Without recursion you should be able to get a worst case I think without
getting bogged down with the halting problem. As there's no recursion
you can construct a tree of the program structure, and assume that all
conditional calls happen. Then replace terminal nodes with the size of
their space, then nodes only calling terminals with the sum of the
terminals. Repeat until only one node is left. That sounds like it is
guaranteed to halt.

Function pointers anyone?

I tried this once and the use of function pointers in the code made it
impossible.
 
J

jacob navia

Nick a écrit :
Without recursion you should be able to get a worst case I think without
getting bogged down with the halting problem. As there's no recursion
you can construct a tree of the program structure, and assume that all
conditional calls happen. Then replace terminal nodes with the size of
their space, then nodes only calling terminals with the sum of the
terminals. Repeat until only one node is left. That sounds like it is
guaranteed to halt.

That is exactly what I did. The only problem are function pointers.
 
N

Nick

Ian Collins said:
Function pointers anyone?

I tried this once and the use of function pointers in the code made it
impossible.

They are certainly going to make it difficult. Unless they are very
constrained (and if not, how do you know you don't have recursion). If
very constrained you can treat them as a chain of "if"s on the potential
values (and so true for the tree creation).
 
A

Alan Curry

They are certainly going to make it difficult. Unless they are very
constrained (and if not, how do you know you don't have recursion). If
very constrained you can treat them as a chain of "if"s on the potential
values (and so true for the tree creation).

Easy upper bound: just assume every function is active simultaneously. Forget
about how it can or can't happen in the actual program flow. Add them all up.
Anything bigger than that violates the "no recursion" rule.

If the number's too big, change all auto variables to statics. No point
having auto variables in a language without recursion where they live on a
statically-allocated stack anyway.
 
F

Flash Gordon

The constraint can be any function with a matching definition (otherwise
you've got undefined behaviour) which you have not passed through to
reach that point.
Easy upper bound: just assume every function is active simultaneously. Forget
about how it can or can't happen in the actual program flow. Add them all up.
Anything bigger than that violates the "no recursion" rule.

Your upper bounds are going to be high if based on the source code since
the compiler is likely to have managed to eliminate at least some of the
auto variables.

You still have a problem with VLAs, the simplest example being a
function which prompts the user for the size of the VLA to be created
and then creates one of the requested size!
If the number's too big, change all auto variables to statics. No point
having auto variables in a language without recursion where they live on a
statically-allocated stack anyway.

That is likely to significantly increase memory requirements since a lot
of those functions probably cannot be active simultaneously. Also, I've
seen this done in asembler, and it was truly horrible!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top