Next: Dataflow analysis: reaching definitions
Up: Compiler Theory: Code Optimization
Previous: Dataflow Analysis and Global Optimization
A LOOP L IN A CONTROL FLOW GRAPH G is a subgraph satisfying the following properties.
 There exists a path from any node of L to any other node of L.
 There is only one node h of L such that there exists a node
n of G which is not a node of L and (n, h) is an edge of G.
This node h is called the entry point
or the header of the loop.
A loop that contains no other loop is called an inner loop.
To identify loops we need the following two notions.
IN A CONTROL FLOW GRAPH G, A DOMINATOR for a node n is a node d such that any path from
the entry of the CFG to n goes through d.
In this case we also say that d dominates n.
Algorithm 2
 This algorithm terminates since
 D(n) 
cannot decrease infinitely many times.
 The correctness of the algorithm can be made easily by induction
on the maximal length of an elementary path from n to n_{0}.
Observe that the header h of a loop L dominates all other
nodes of L. Otherwise it cannot be the only entry point.
A BACK EDGE IN A CFG G is an edge (p, d ) of G such that d dominates p.
To each back edge one can associate a loop as follows.
THE NATURAL LOOP OF A BACK EDGE (n, d ) is a loop of its CFG computed
by the following algorithm.
Algorithm 3
Example 3
Consider the following TAC fragment.

s:=0 

i:=0 

n:=10 
L1: 
t1 := ab 

ifz t1 goto L2 

t2 := i*4 

s := s+t2 

goto L3 
L2: 
s := s+i 
L3: 
i := i+1 

t3 := ni 

ifnz t3 goto L1 

t4 := ab 
Its control flow graph is shown on Figure 2.
There is one back edge: (B_{5}, B_{2}).
Its natural loop consists of the nodes
B_{2}, B_{3}, B_{4}, B_{5}.
Figure 2:
A control flow graph with two loops.

Occasionally it is difficult to determine when a loop is nested.
LOOP OPTIMIZATIONS often involve
 moving code out of the loop or
 precomputing values for use in the loop
To do so, we need a basic block in which we insert such code
 before any loop optimization we create a new block
which is inserted immediately before the header
 such a block is called a preheader
REDUCIBLE CONTROL FLOW GRAPHS. A control flow graph G is said to be reducible
if the removal of its back edges leads to an acyclic graph
where each node can be reached from the initial node of G.
In this case, all the edges of this acyclic graph are called forward edges.
Figure 3:
A control flow graph which is not reducible.

Figure 3 shows a control flow graph which
is not reducible.
Indeed it has no loops (in the sense of the above definition)
and it is not acyclic.
Figure 4 sketches a simple
algorithm for determining whether a control flow graph
is nonreducible. When no more reductions are possible,
the initial CFG is reducible if and only if the reduced
CFG consists only of a single node.
Figure 4:
Determining whether a control flow graph is reducible or not.

In the first situation, one can contract the nodes 1 and 2
since it is allowed to arrive at 2 only from 1.
In the second case, one is allowed to remove the loop (in the sense
of graph theory) around the node.
One can show the following properties about reducible CFG
 Nonreducible flow graphs arise basically only from unstructured use of gotostatements
(jumps into the middle of a loop from the outside of the loop,
without using the header).
 The key property of reducible control flow graphs
is that any set of nodes that intuitively appears as a loop,
contains a back edge.
 Thus we only need to identify the back edges
to find all loops in a reducible control flow graph.
Figure 5 sketches a technique of nodesplitting
for dealing with the improper regions of nonreducible graphs.
Figure 5:
Dealing with improper regions by nodesplitting.

Next: Dataflow analysis: reaching definitions
Up: Compiler Theory: Code Optimization
Previous: Dataflow Analysis and Global Optimization
Marc Moreno Maza
20041202