RTUComputer ScienceYr 2023 · Sem 52023

Q7Compiler Design

Question

4 marks

Explain the basic blocks and flow graphs in code optimization.

Answer

In code optimization, a Basic Block is a strictly linear sequence of code with no branches, while a Flow Graph mathematically links these blocks to map execution paths.

During the Code Optimization phase, the compiler refuses to analyze the raw, massive list of intermediate Three-Address Code (TAC) linearly. Instead, to apply advanced mathematical optimization algorithms (like loop invariant removal or data-flow analysis), the compiler must architecturally slice the code into strict, indivisible atomic units known as "Basic Blocks," and then map their relationships using a "Control Flow Graph" (CFG).

The Architecture of a Basic Block

A Basic Block is mathematically defined as a strictly linear, continuous sequence of executable instructions that guarantees absolutely no branching. It operates under two unbreakable physical laws: 1. Execution MUST enter exactly at the first instruction of the block. 2. Execution MUST exit exactly at the last instruction of the block, without halting or branching out in the middle.

To aggressively isolate Basic Blocks from a massive file of code, the compiler utilizes the "Leader Algorithm": - The absolute first instruction of the code is a Leader. - Any instruction that is the specific target of a conditional or unconditional jump (e.g., a GOTO label) is instantly marked as a Leader. - Any instruction that immediately physically follows a jump or GOTO is marked as a Leader. A Basic Block mathematically consists of a Leader and all subsequent instructions right up to, but strictly excluding, the next Leader.

The Control Flow Graph (CFG)

Once the compiler has violently shattered the code into isolated Basic Blocks, it must understand how the program actually executes. It constructs a Control Flow Graph (CFG).

  • The CFG is a highly rigorous, directed mathematical graph.
  • Nodes: Every single Basic Block becomes a solid Node in the graph.
  • Edges: Directed arrows (Edges) are drawn between nodes to represent the physical jump of execution. If Block B mathematically executes immediately after Block A, an arrow connects A to B.
  • Loop Detection: The CFG allows the compiler to instantly visually detect infinite loops and nested loops (represented by physical back-edges in the graph). By identifying these heavily executed loops, the compiler can violently focus its optimization algorithms on the most critical bottlenecks of the software.
Back to Paper