Various Topics on Programming

..m ..i..

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 ***ume 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).

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

..ua..

"Tim Frink" <plfriko@yahoo.de> wrote in message
newsan.2007.06.11.14.43.41.126129@yahoo.de...

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

Try looking for papers that address topics like Data-Flow or
Information-Flow analysis of programs. Unfortunately I do not have a handy
link to an on-line paper.

Although the problem you are looking at is concerned with timing; at the
level you appear to be considering it, it may be reasonable to model it as
an update to a global 'pseudo-variable' T. This makes it amenable to
data/information flow analysis techniques.

You can do some simple types of analysis of systems using this technique and
program proving systems such as SPARK (and indeed SPADE which predates it),
or abstract interpretation tools like Polyspace. You would probably do even
better with tools specialising in timing analysis - look for absINT. For
actual timing analysis there is also good work being done by Rapita.

But I am guessing you are more interested in the modelling side than
actually doing a particular analysis.

Regards
--
Stuart

..a ..xt..

"Tim Frink" <plfriko@yahoo.de> wrote in message
newsan.2007.06.11.14.43.41.126129@yahoo.de...
> 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:
>
> If I use a simple control-flow graph (CFG), it would look
> something like:

I would have called your diagram a call graph,
not a control flow graph.

> And further, let's ***ume 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).
>
> What graph/path representation and algorithms would you suggest?

One that has enough detail so that you can compute the answer
correctly. Your call graph abstracted away the conditionals
and the multiple calls. If those details are important to you,
well, you can't abstract them away and expect and answer.

What we do for most flow analyses is model the control flow
(not the call graph) in exquisite detail, e.g., we retain
the conditions and the essential sequencing of events,
even inside expressions. Then such details are not lost.

(See http://www.semanticdesigns.com/Produ...wAnalysis.html
for a description of such a control flow graph)
Of course, computing anything is now a bit more complicated,
because you have to ignore the part of the graph you don't
want to see. But we don't have to spend a lot of time
worrying about whether the raw information needed
to answer questions is there or not.

Now, there's a bunch of messy things your example didn't
bring up. First are function pointers, second (at least for
GCC) are goto indirects. How can you follow
flow arcs that don't exist in your graph? Answer:
do a conservative points-to analysis. And that's hard
in a big C program. So to do this right, you need
a flow graph *and* points-to analysis.

[Our tools can compute both].


--
Ira Baxter, CTO
www.semanticdesigns.com