Model control-flow graphs

Hi,

I'm looking for an appropriate way to represent the control flow graph of programs.

Let's say I've this easy C program:

void foo3(void) { int a = 0; return; }

void foo2(void) { foo3(); foo5(); return; }

void foo4(void) { foo5(); foo5(); return; }

void foo5(void) { int b = 0; return; }

int main(int argc, char *argv[]) { if( argc == 0 ) foo2(); else foo4(); return 0; }

If I use a simple control-flow graph (CFG), it would look something like:

main | |------| | | foo2 foo4 |\ | | \ | | \ | | \ | | \ | | \| foo3 foo5

And further, let's assume I know the execution time for each function. Now, I'd like to find the longest path within my graph (the path through the entire program with the maximal execution time). I think that this issue is not fully off-topic since the problem of determining the longest program execution is relevant for (hard) realtime systems.

What graph/path representation and algorithms would you suggest?

With the control-flow graph given above, I can't use any single- source shortest path algorithms (and take the last vertex with the longest path) since a) multiple calls of foo5 in foo4 can't be modeled - in the graph it looks as if foo4 called foo5 once. b) the path main->foo2->foo3--->foo5 is not modeled correctly since it is not obvious that foo2 will first call foo3 _and_ then call foo5

I would appreciate any help. Also any ideas how program executions (based on their CFG) are modeled in general are welcomed.

Thank you.

Regards, Tim

Reply to
Tim Frink
Loading thread data ...

Here are some links to work on static analysis of worst-case execution time, perhaps relevant to your question:

Survey:

formatting link

Some tools:

aiT :

formatting link
Bound-T:
formatting link
SWEET :
formatting link

Many WCET analysis methods make "context-sensitive" analyses of functions so that different call sites (or even call paths) are analysed separately and there can be parameter-dependent WCET bounds on each function. Then there is the question of loop bounds, whether different iterations of a given loop are analysed separately (iteration-sensitive analysis), and the question of globally infeasible execution paths... I think that the best analysis of feasible execution paths is currently in SWEET, see link above.

The maximal execution time is typically discovered using Integer Linear Programming applied to the extended CFG -- the Implicit Path Enumeration technique; see the survey (link above) for references.

HTH,

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

void foo4(void) { foo5(); foo5(); return; } void foo3(void) { int a = 0; return; } void foo2(void) { foo3(); foo5(); return; }

... snip ...

I don't see the problem. I have reorganized your foos so that the calls are valid, and reduced vertical space used. You can time everything with timers attached to foo2 and foo4, also main.

--
 
 
 Click to see the full signature
Reply to
CBFalconer

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.