Optimizing with Basic Blocks and Flow Graphs

From Linear Code to a Program Map: Basic Blocks and CFGs

The Three-Address Code we generated in the last lesson is a linear sequence of instructions. However, programs aren't just straight lines; they have branches, loops, and jumps. To reason about optimization, especially across these control flow changes, we first need to partition our TAC into Basic Blocks.

A basic block is a sequence of consecutive instructions where:

1. Control flow enters only at the beginning of the block.
2. Control flow leaves only at the end of the block.
   There are no jumps into or out of the middle of a basic block. This means if the first instruction in a block executes, all instructions in that block will execute sequentially.

To find these blocks, we first identify leaders, which are the first statements of basic blocks. A statement is a leader if:

1. It is the very first statement in the program.
2. It is the target of a conditional or unconditional goto.
3. It immediately follows a goto or conditional goto statement.

Once leaders are identified, a basic block consists of a leader and all subsequent statements up to (but not including) the next leader.

These blocks become the nodes in a Control Flow Graph (CFG). The directed edges of the graph represent the possible flow of control between the blocks.

Let's apply this to the while loop example from our last lesson. The TAC was:

      i = 0                   (1)
L1:   if i >= 20 goto L2      (2)
      t1 = i * 4              (3)
      a[t1] = i               (4)
      t2 = i + 1              (5)
      i = t2                  (6)
      goto L1                 (7)
L2:   ... (code continues)    (8)

Let's find the leaders:

• Instruction (1) is the first statement, so it's a leader.
• Instruction (2) is the target of the goto L1 at (7), so L1 (instruction 2) is a leader.
• Instruction (8) is the target of the if...goto L2 at (2), so L2 (instruction 8) is a leader.

This gives us three basic blocks:

• B1: Instruction (1). It ends because instruction (2) is a leader.
• B2: Instructions (2) through (7). It ends because instruction (8) is a leader.
• B3: Instruction (8) and whatever follows.

The CFG would look like this:

• An edge from B1 to B2 (sequential flow).
• An edge from B2 back to itself (the loop, via goto L1).
• An edge from B2 to B3 (exiting the loop, via if i >= 20 goto L2).

A simple Control Flow Graph. B1 is the entry block, B2 is the loop body which can either branch back to itself or exit to B3.

Local Optimization Techniques

Now that we have our code structured into basic blocks, we can start optimizing. Local optimization refers to transformations applied to the code within a single basic block. Since there are no jumps into or out of the middle of a block, we can make strong assumptions about the code's execution.

Let's explore some key local optimization techniques that are frequently tested in GATE.

Let's clarify these with more direct examples.

1. Common Subexpression Elimination (CSE)

If a basic block contains x = a + b and later y = a + b, and the values of a and b have not changed in between, we can optimize it.

Unoptimized TAC:

t1 = a + b
x = t1
...
t2 = a + b  // Redundant computation
y = t2

Optimized TAC:

t1 = a + b
x = t1
...
y = t1      // Reuse the result from t1

This saves one addition operation.

2. Constant Folding and Propagation

These two techniques work hand-in-hand.

• Constant Propagation: If we have an assignment x = 3, we can replace later uses of x with the constant 3.
• Constant Folding: If an expression has constant operands, like y = 3 + 4, the compiler can compute the result at compile time and replace it with y = 7.

Example:

a = 5;
b = a - 2;

TAC:

a = 5
b = a - 2

After Constant Propagation:

a = 5
b = 5 - 2  // 'a' is replaced with 5

After Constant Folding:

a = 5
b = 3      // '5 - 2' is computed at compile time

3. Algebraic Transformations and Strength Reduction

This involves using algebraic rules to simplify or improve code.

• Identity: x = y + 0 or x = y * 1 can be simplified to x = y.
• Strength Reduction: Replacing an expensive operation (a "strong" one) with a cheaper one (a "weak" one). The classic example is replacing multiplication by a power of two with a bit shift.
  x = y * 2 becomes x = y << 1.
  x = y / 4 becomes x = y >> 2.

Iterative Optimization: The Real Power

The true benefit of these optimizations emerges when they are applied repeatedly over the Control Flow Graph. An optimization in one block can create new opportunities for optimization in other blocks. This iterative process continues until no more improvements can be made.

As you saw in the video, the process is cyclical:

1. Analyze the CFG.
2. Apply simple optimizations (Constant Propagation, Folding, CSE, Dead Code Elimination).
3. Repeat, as the output of one pass becomes the input for the next.

This iterative approach is powerful because it allows a few simple rules to achieve complex, large-scale optimizations without needing a single, monolithic "super-optimizer."

Putting It All Together: A GATE-Style Walkthrough

Let's analyze a piece of code from start to finish.

Source Code:

int x = 10;
int y = x - 7;
int z;
while (y > 1) {
    z = y * 2;
    y = y - 1;
}
int w = x - 7;

1. Generate Three-Address Code:

       x = 10
       y = x - 7
L1:    if y <= 1 goto L2
       t1 = y * 2
       z = t1
       t2 = y - 1
       y = t2
       goto L1
L2:    w = x - 7

2. Identify Basic Blocks:

• B1 (Entry):

  x = 10
  y = x - 7
  

• B2 (Loop Header & Condition):

  L1: if y <= 1 goto L2
  

• B3 (Loop Body):

  t1 = y * 2
  z = t1
  t2 = y - 1
  y = t2
  goto L1
  

• B4 (Exit):

  L2: w = x - 7
  

CFG Edges: (B1, B2), (B2, B3), (B2, B4), (B3, B2)

3. Apply Optimizations Iteratively:

• Round 1 (In B1):

  • Constant Propagation: y = 10 - 7
  • Constant Folding: y = 3
  • B1 becomes: x = 10, y = 3.

• Round 2 (Propagating from B1 to B2):

  • The value y=3 from B1 is the only value reaching B2 on the first entry.
  • The condition in B2 becomes if 3 <= 1 goto L2. This is always false.
  • Since the condition is known at compile time, the branch to L2 on the first iteration will not be taken. The program will definitely enter the loop body (B3) at least once.

• Round 3 (Strength Reduction in B3):

  • In B3, we have t1 = y * 2.
  • This can be replaced with t1 = y << 1. A cheaper operation.

• Round 4 (Common Subexpression Elimination across blocks):

  • Notice B1 computes x - 7 and stores it in y.
  • Block B4 computes x - 7 again.
  • Since the value of x is never changed throughout the program, x - 7 is a global common subexpression.
  • However, the value of y is changed inside the loop. When control reaches B4, y will be 1. But the value of x - 7 is still 3.
  • A smart compiler could notice x is unchanged and w = x - 7 can be replaced with w = 3. This is a more advanced (global) optimization, but it's built upon the same principles. For local optimization, in block B4, we can't just reuse y because its value has changed. But we can see x-7 is the same expression.

This step-by-step analysis, moving from code to TAC to CFG and then applying iterative optimization, is exactly the thought process required for many GATE problems in this area.

Conclusion

This lesson marks the end of our journey through Compiler Design. We've seen how a compiler intelligently restructures and refines code long before it ever becomes executable machine instructions.

Here are the key takeaways from today:

• Basic Blocks are straight-line code sequences that form the nodes of a Control Flow Graph (CFG).
• The CFG provides a map of a program's execution paths, enabling sophisticated analysis.
• Local optimizations are applied within a single basic block. Key examples include:
  • Common Subexpression Elimination (CSE): "Compute once, use many times."
  • Constant Folding & Propagation: Perform calculations at compile time.
  • Dead Code Elimination: Remove useless or unreachable code.
• The most powerful optimizations arise from applying these simple techniques iteratively, where one improvement opens the door for another.

You have now covered the entire compiler pipeline, from scanning source text to optimizing intermediate code. In our next module, we will shift our focus from how programs are built to how they are managed by the computer's master software: the Operating System. We will begin by exploring the fundamental concepts of processes, threads, and system calls.