Basic Blocks and Code Optimization

Code optimization transforms the intermediate code so that it runs faster or uses less space, without changing what the program computes. Most optimizations work on basic blocks and the control-flow graph that connects them.

Basic blocks

A basic block is a maximal sequence of consecutive instructions that control enters only at the first instruction and leaves only at the last (no jumps into the middle, no jumps out except at the end).

To find them, first find the leaders:

1. The first instruction of the program is a leader.
2. Every target of a jump (conditional or unconditional) is a leader.
3. Every instruction that immediately follows a jump is a leader.

Each basic block runs from a leader up to (not including) the next leader.

The control-flow graph (CFG) has the basic blocks as nodes, and an edge B → C when C can run right after B: either B ends with a jump to C's leader, or C follows B in the code and B does not end with an unconditional jump.

import re

code = [
    "s = 0",                    # 1
    "i = 1",                    # 2
    "t1 = i * 4",               # 3
    "t2 = a[t1]",               # 4
    "s = s + t2",               # 5
    "i = i + 1",                # 6
    "if i <= n goto 3",         # 7
    "if s > 100 goto 11",       # 8
    "r = 0",                    # 9
    "goto 12",                  # 10
    "r = 1",                    # 11
    "return r",                 # 12
]

def target(instr):
    m = re.search(r"goto (\d+)", instr)
    return int(m.group(1)) if m else None

leaders = {1}
for n, instr in enumerate(code, 1):
    if target(instr):
        leaders.add(target(instr))                   # rule 2
        if n < len(code):
            leaders.add(n + 1)                       # rule 3
leaders = sorted(leaders)
blocks = [(start, (leaders[k + 1] - 1) if k + 1 < len(leaders) else len(code))
          for k, start in enumerate(leaders)]
edges = []
for k, (start, end) in enumerate(blocks):
    last = code[end - 1]
    if target(last):
        edges.append((k, next(b for b, (s, _) in enumerate(blocks) if s == target(last))))
    if not last.startswith("goto") and k + 1 < len(blocks):
        edges.append((k, k + 1))
print("leaders:", leaders)
for k, (start, end) in enumerate(blocks):
    print(f"B{k}: instructions {start}-{end}")
print("edges:", sorted(f"B{a}->B{b}" for a, b in edges))

leaders: [1, 3, 8, 9, 11, 12]
B0: instructions 1-2
B1: instructions 3-7
B2: instructions 8-8
B3: instructions 9-10
B4: instructions 11-11
B5: instructions 12-12
edges: ['B0->B1', 'B1->B1', 'B1->B2', 'B2->B3', 'B2->B4', 'B3->B5', 'B4->B5']

Local optimizations (within a basic block)

These often enable each other: copy propagation turns an assignment into dead code, which is then removed. The DAG of a basic block (previous lesson) finds common subexpressions automatically.

Loop optimizations

Programs spend most of their time in loops, so loop optimizations pay off the most.

• Loop-invariant code motion: move a computation whose value does not change inside the loop to just before the loop. while (i < n) { x = y + z; a[i] = x * i; i++; } computes y + z once, before the loop.
• Induction variable elimination and strength reduction: in the CFG example above, t1 = i * 4 grows by 4 in every iteration. Replace the multiplication by t1 = t1 + 4 (strength reduction), and if i is then used only for the loop test, test t1 instead (eliminating i).
• Loop unrolling: repeat the body several times per iteration, reducing the number of tests and jumps.
• Loop jamming (fusion): merge two loops over the same range into one.

Peephole optimization

A peephole optimizer slides a small window over the target code and replaces short instruction sequences with better ones:

• remove redundant loads and stores (STORE R1, x followed by LOAD R1, x),
• remove unreachable code and jumps to the next instruction,
• collapse jump chains (goto L1 where L1: goto L2 becomes goto L2),
• algebraic simplification and use of special instructions (INC instead of ADD 1).

Practice questions