Loops in flow graph
To identify loops, first find "dominator”.
Dominator: Node d of a flow graph dominates node n, written d dom n, if every path from
the initial node of the flow graph to n goes through d.
Every node dominates itself, and the entry of a Ioop dominates all nodes in the loop.
Dominator Tree: is used to represent dominator information. It is a tree in which the initial
node is the root, and each node d dominates only its descendants in the tree.
In this flow graph:
Initial node,node1 dominates every node
node 2 dominates only 2
node 3 dominates 3,4,5,6,7,8,9,10
node 4 dominates 4,5,6,7,8,9,10
node 5 and 6 dominates 5,6
node 7 dominates 7,8,9,10
node 8 dominates 8,9,10
node 9 and 10 dominates 9,10
Dominator Tree
The existence of dominator tree follows from a property of dominators; each node has a
unique immediate dominator in that is the last dominator of n on any path from the initial
node to n.
D(1)={1} D(7)={1,3,4,7}
D(2)={1,2}
D(3)={1,3} D(8)={1,3,4,7,8}
D(4)={1,3,4}
D(5)={1,3,4,5} D(9)={1,3,4,7,8,9}
D(6)={1,3,4,6} D(10)={1,3,4,7,8,10}
Natural Loop:
One application of dominator information is in determining the loops of a flow graph
suitable for improvement.
The properties of loops are:
A loop must have a single entry point, called the header. This entry point-dominates
all nodes in the loop, or it would not be the sole entry to the loop.
There must be at least one way to iterate the loop (i.e.) at least one path back to the
header.
One way to find all the loops in a flow graph is to search for edges in the flow graph whose
heads dominate their tails. If a→b is an edge, b is the head and a is the tail. These types of
edges are called as back edges.
Example:
In the above flow graph, back edges are:
7→4 4 DOM 7
10 →7 7 DOM 10
4 → 3, 8 → 3, 9 →1
The above edges will form loop in flow graph.
Given a back edge n → d, we define the natural loop of the edge to be d plus the set of
nodes that can reach n without going through d. Node d is the header of the loop.
Algorithm: Constructing the natural loop of a back edge.
Input: A flow graph G and a back edge n→d.
Output: The set loop consisting of all nodes in the natural loop n→d.
Method: Beginning with node n, we consider each node m=!d that we know is in loop, to
make sure that m’s predecessors are also placed in loop. Each node in loop, except for d, is
placed once on stack, so its predecessors will be examined. Note that because d is put in the
loop initially, we never examine its predecessors, and thus find only those nodes that reach
n without going through d.
Procedure insert(m);
Only inner loop,'' that is, a loop with no subloops, is
if m is not in loop then begin { 7,8,10}, the natural Ioop of back edge 10 7.
loop := loop U {m}; The set {7,4,6,5,8,10} is the natural loop of 74.
push m onto stack Next larger Ioop is {4,3,5,6,7,8,10}, which is the natural
end; loop of both edges 4 3 and 8-->3
/*main program*/ The last loop, for back edge 91, is 1,2,3,4,5,6,7,8,9,10
stack : = empty;
loop : = {d};
insert(n);
while stack is not empty do begin
pop m, the first element of stack, off stack;
for each predecessor p of m do insert(p)
end
Inner loop:
one that contains no other loop.
When two natural loops have the same header, but neither is nested within the
other, they are combined and treated as a single loop.
Two loops with same header
Pre-Headers:
Several transformations require us to move statements “before the header”.
Therefore begin treatment of a loop L by creating a new block, called the preheader.
The pre-header has only the header as successor, and all edges which formerly
entered the header of L from outside L instead enter the pre-header.
Edges from inside loop L to the header are not changed.
Initially the pre-header is empty, but transformations on L may place statements in
it.
Reducible Flow Graph:
A flow graph G is reducible if and only if we can partition the edges into two disjoint groups,
forward edges and back edges, with the following properties.
The forward edges from an acyclic graph in which every node can be reached from
initial node of G.
The back edges consist only of edges where heads dominate their tails.
Example:
If we know the relation DOM for a flow graph, we can find and remove all the back
edges. The remaining edges are forward edges.
If the forward edges form an acyclic graph, then we can say the flow graph reducible.
In the above example remove the five back edges 4→3, 7→4, 8→3, 9→1 and 10→7
whose heads dominate their tails, the remaining graph is acyclic.
The key property of reducible flow graphs for loop analysis is that in such flow
graphs every set of nodes that we would informally regard as a loop must contain a
back edge.
Non reducible flow graph
This flow graph has no back edges, since no head of an edge dominates the tail of that edge.
Thus it could only be reducible if the entire graph were acyclic. But since it is not, the flow
graph is not reducible. Intuitively, the reason this flow graph is not reducible is that the cycle
2-3 can be entered at two different places, nodes 2 and 3.
LOOP JAMMING
Loop jamming is a technique that merges the bodies of two loops if the two loops have the
same number of iterations and they use the same indices. This eliminates the test of one
loop. For example, consider the following loop:
Initial Code:
for(int i=0; i<5; i++)
a = i + 5;
for(int i=0; i<5; i++)
b = i + 10;
Optimized code:
for(int i=0; i<5; i++)
{
a = i + 5;
b = i + 10;
}
LOOP UNROLLING
Loop unrolling involves replicating the body of the loop to reduce/remove the required
number of tests if the numbers of iterations are constant. For example consider the
following loop:
I=1
while (I <= 100)
{
x[I] = 0;
I++;
}
In this case, the test I <= 100 will be performed 100 times. But if the body of the loop is
replicated, then the number of times this test will need to be performed will be 50. After
replication of the body, the loop will be:
I=1
while(I<= 100)
{
x[I] = 0;
I++;
X[I] = 0;
I++;
}
Example of remove:
int main(void)
{
for (int i=0; i<5; i++)
printf("Hello\n"); //print hello 5 times
return 0;
}
Optimized code:
int main(void)
{
printf("Hello\n");
printf("Hello\n");
printf("Hello\n");
printf("Hello\n");
printf("Hello\n");
return 0;
}
