Loop processing

Before getting started with loop processing and optimization, we must have a little heads up about the concepts of CFG and dominance information. A CFG is the control flow graph of the program that gives a look into how the program may be executed through the various basic blocks. By dominance information, we get to know about the relation between the various basic blocks in the CFG.

In a CFG, we say a node d dominates a node n if every path (from the input towards output) that passes through n must also pass through d. This is denoted by d -> n. The graph G = (V, E), where V is the set of basic blocks and E is the dominance relation defined on V, is called dominator tree.

Let's take an example to show the CFG of a program and the corresponding dominator tree.

Put example code here:

void fun() {
  int iter, a, b;

  for (iter = 0; iter < 10; iter++) {
    a = 5;
    if (iter == a)
      b = 2;
    else
      b = 5;
  }
}

The CFG for the preceding code looks like the following...