====== Control-Flow Graph Definition ======
Related to traditional notion of flow charts
**Example program 1:**
while (i < 10) {
println(j);
i = i + 1;
j = j +2*i + 1;
}
Corresponding control-flow graph:
{{cc09:cfg.png|CFG for Squaring}}
**Example program 2:**
int i = n;
while (i > 1) {
println(i);
if (i % 2 == 0) {
i = i / 2;
} else {
i = 3*i + 1;
}
}
Corresponding control-flow graph:
{{cc09:cfg2.png|Control-Flow Graph}}
**Definition:** Control-Flow Graph (CFG) is graph $(V,E,L)$ where
* $V$ is set of CFG nodes, representing program points
* $E \subseteq V\times V$ is a multiset of CFG edges (represent how **control flows** from one point to another)
* $L : E \to ST$ gives a CFG statement for each edge
* statements
* conditions
++++Side Note:| there are alternative representations
* putting statements on nodes instead of edges
* labelling outgoing edges
++++
In the example, what are V,E,L?
atomic expression = variable or a constant
ST statements are simple:
* quadruples: x = y * z (y,z are atomic expression)
* copy
* procedure calls (parameters are atomic)
* relational operators between atomic expressions
Notion of Basic Blocks: straight sequence of nodes (no jumps to or from the middle)