Program flow control flow

Question

I am taking the compiler class right now, and we are at the point where we need to build CFG in order to implement the optimization. One thing I cannot understand is how many CFGs exist for a program? Every example I've ever seen seems to be CGF of a simple code segment. So, if you have a program that will say three functions. Do you have a separate CFG for each function or have one large CFG for the entire program?

Answer 1

Functional CFGs are connected by calls. If one function calls another, for example:

0 void foo() { /* do stuff */ } 1 void bar() { /* do stuff */ } 2 3 void baz() { 4 foo(); // Callsite for foo. Control transfers to foo, then foo returns here. 5 bar(); // Callsite for bar. Control transfers to bar, then bar returns here. 6 } 

then the control graph for baz will include the edge going to the graph for foo . Similarly, since foo will eventually return to baz (and anywhere else it could have been called), there will be an end from the end of the foo graph back to the statement after calling foo in baz . Here, that next statement is the call to bar on line 5. At that point, there an edge from the . Here, that next statement is the call to bar on line 5. At that point, there an edge from the bar callsite to bar CFG, and lines from exit points in bar back to the end of baz`.

Basically, all you need to think about is what code the following executes. This tells you where the edges should go in your control graph. A function call transfers control until the function returns, which implies an edge from the caller to the CFG function and vice versa.

Please note that not all full-featured CFGs are related graphs. If the program being analyzed has unreachable code , then it will be its own unrelated part of the full CFG. for example, if you made a call to bar in the above example, then bar will have its own graph aside, and baz and foo will be connected by edges.

Answer 2

Well, you can build CFG for each function, and then - if you want what you want to do - combine them into a complete one. However, all CFG programs can be quite large, so they usually do not work well, as examples.