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