7.3 Control Flow Translation, Boolean Expressions & Backpatching

Back to DBMS Notes

📚Module 01Control Flow Translation, Booleans & Backpatching⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Unresolved Gate Boarding Pass

Imagine booking a flight with a layover in a hub airport where gate assignments haven't been finalized yet:

• When you board your initial flight, the airline issues a connecting pass with: [ GATE: _____ ] (a forward jump with an unfilled target).
• The airline adds your boarding pass serial number to a holding queue: the Gate Resolution Waiting List.
• The instant your connecting aircraft touches down and the airport ground control designates Gate 42, the agent broadcasts the number and fills 42 into every pending pass on that waiting list.
• In compiler construction, this is Backpatching! Instead of halting translation or performing an expensive second traversal over the Abstract Syntax Tree, the compiler generates branch instructions with open targets (goto _), maintains them in lists (truelist, falselist, nextlist), and fills in the concrete instruction addresses the exact millisecond the target destination is determined.

💻 Bridging to Computer Science: Single-Pass Backpatching & Short-Circuit Control Flow

In intermediate code generation:

• Boolean expressions in programming languages serve two purposes: computing numerical truth values (0 or 1) and driving control-flow jumps.
• Short-Circuit Evaluation: Logical operators $\land\land$ and $\lor\lor$ stop evaluation as soon as the outcome is known, preventing unnecessary instructions and guarding against null-pointer exceptions.
• Backpatching: Synthesizes jump targets on-the-fly during a single syntax-directed pass using three core list operations: makelist(i), merge(p1, p2), and backpatch(p, target).

📑Table of Contents

• 🏗️ Architectural Foundations: Two-Pass vs Single-Pass Backpatching
• 📐 Formal Foundations: Short-Circuit Boolean Evaluation
  • ⚡ Short-Circuit Semantics
• 🏗️ Architecture & Execution Mechanics: The Backpatching Engine
  • 🧱 Synthesized Attributes for Boolean Expressions
• 📜 Translation Schemes for Control Flow
  • 1️⃣ Boolean OR Translation Scheme
  • 2️⃣ Boolean AND Translation Scheme
  • 3️⃣ Boolean NOT Translation Scheme
  • 4️⃣ Relational Expression Translation Scheme
• 🏭 Real-World Production Context: How Industry Builds This
• 📐 Numerical Applications & Worked Examples
  • Example 1: Short-Circuit Three-Address Code Generation
  • Example 2: While Loop Translation with Backpatching
• 🎯 Exam & Interview Pitfall Check

---

🏗️ Architectural Foundations: Two-Pass vs Single-Pass Backpatching

Two-Pass Compilation vs Single-Pass Backpatching

Contrasting full-tree label pre-calculation against on-the-fly target resolution

Two-Pass

Two-Pass Compilation

🔄

Dominant Architecture / DomainEarly Compilers, Full-AST Compilers

• •Pass 1: Parses program, builds full AST, and assigns symbolic labels to all blocks.
• •Pass 2: Traverses AST to emit target addresses for every forward branch.
• •Requires large memory footprint to retain complete AST and symbol structures.
• •Higher memory bandwidth and compilation latency.

"Wait until the entire map is drawn before setting foot on the road."

Backpatching

Single-Pass Backpatching

⚡

Dominant Architecture / DomainHigh-Performance Compilers, JIT Engines, One-Pass Tools

• •Emits branch instructions immediately with unassigned destination slots.
• •Maintains compact linked lists of pending instruction addresses.
• •Resolves all forward references instantly when the target label is reached.
• •Zero secondary AST passes: achieves maximum throughput and minimal memory.

"Emit immediately; patch forward targets as soon as they become known."

---

📐 Formal Foundations: Short-Circuit Boolean Evaluation

Boolean expressions in programming languages serve two distinct purposes:

1. Numerical Value Computation: Evaluating conditions into integer representations (e.g. $x = (a < b) + 5$ where $a < b$ produces 1 or 0).
2. Flow of Control: Determining branch trajectories in conditional and iterative statements (if, while, for).

⚡ Short-Circuit Semantics

In modern languages (C, C++, Java, Rust, Python), boolean operators $\land\land$ (AND) and $\lor\lor$ (OR) evaluate using short-circuit evaluation:

• In $B_1 \lor\lor B_2$: If $B_1$ evaluates to true, the overall expression is guaranteed to be true. $B_2$ is never evaluated!
• In $B_1 \land\land B_2$: If $B_1$ evaluates to false, the overall expression is guaranteed to be false. $B_2$ is never evaluated!

// Short-circuit safety guard:
if (ptr != NULL && ptr->value > 0) { ... }
// If ptr is NULL, ptr->value is NEVER dereferenced!
// Without short-circuiting, this triggers a Segmentation Fault!

---

🏗️ Architecture & Execution Mechanics: The Backpatching Engine

In a single-pass syntax-directed translation scheme, the compiler emits a linearized stream of instructions indexed $100, 101, 102, \dots$:

Architecture Flow

The Three Core Backpatching Primitives

Managing jump lists and filling unresolved instruction addresses

📝Create

makelist(i)

Allocates a new list containing a single instruction index i.

→

Returns List

🔀Combine

merge(p1, p2)

Concatenates two jump pointer lists p1 and p2 into a single unified list.

→

Returns Combined

🎯Resolve

backpatch(p, L)

Walks list p, writing instruction index L into the target slot of each jump.

🧱 Synthesized Attributes for Boolean Expressions

For any boolean expression $B$, the compiler synthesizes two lists of unresolved forward jumps:

• $B.\text{truelist}$: The list of instruction indices containing jumps that must execute if $B$ evaluates to true.
• $B.\text{falselist}$: The list of instruction indices containing jumps that must execute if $B$ evaluates to false.

For a statement $S$, the compiler synthesizes:

• $S.\text{nextlist}$: The list of instruction indices containing jumps targeting the statement immediately following $S$.

---

📜 Translation Schemes for Control Flow

1️⃣ Boolean OR Translation Scheme

In $B_1 \lor\lor B_2$, if $B_1$ is true, the entire expression is true. If $B_1$ is false, control falls through to evaluate $B_2$. A marker non-terminal $M \to \epsilon$ records the instruction index of the start of $B_2$:

$$\begin{aligned} M &\to \epsilon && M.\text{instr} = \text{nextinstr} \\ B &\to B_1 \lor\lor M \; B_2 && \text{backpatch}(B_1.\text{falselist}, M.\text{instr}); \\ & && B.\text{truelist} = \text{merge}(B_1.\text{truelist}, B_2.\text{truelist}); \\ & && B.\text{falselist} = B_2.\text{falselist}; \end{aligned}$$

2️⃣ Boolean AND Translation Scheme

In $B_1 \land\land B_2$, if $B_1$ is false, the entire expression is false. If $B_1$ is true, control falls through to evaluate $B_2$:

$$\begin{aligned} B &\to B_1 \land\land M \; B_2 && \text{backpatch}(B_1.\text{truelist}, M.\text{instr}); \\ & && B.\text{truelist} = B_2.\text{truelist}; \\ & && B.\text{falselist} = \text{merge}(B_1.\text{falselist}, B_2.\text{falselist}); \end{aligned}$$

3️⃣ Boolean NOT Translation Scheme

Inversion simply swaps the two lists:

$$B \to !B_1 \implies B.\text{truelist} = B_1.\text{falselist}; \quad B.\text{falselist} = B_1.\text{truelist};$$

4️⃣ Relational Expression Translation Scheme

Emits a conditional jump and an unconditional jump with blank targets:

$$\begin{aligned} B \to E_1 \text{ relop } E_2 \implies &B.\text{truelist} = \text{makelist}(\text{nextinstr}); \\ &\text{emit}('\textbf{if }' + E_1.\text{addr} + \text{ relop } + E_2.\text{addr} + '\textbf{ goto \_}'); \\ &B.\text{falselist} = \text{makelist}(\text{nextinstr}); \\ &\text{emit}('\textbf{goto \_}'); \end{aligned}$$

Control Flow Blueprint: If-Else Statement Translation

Tracing S -> if (B) M1 S1 N else M2 S2

Boolean Evaluator

Marker M1

Statement S1

Branch Escape N

Statement S2

1

Boolean Evaluator→Marker M1

Backpatch B.truelist

2

Statement S1→Branch Escape N

Emit Escape Jump

3

Boolean Evaluator→Statement S2

Backpatch B.falselist

4

Statement S2→Branch Escape N

Merge Nextlists

---

🏭 Real-World Production Context: How Industry Builds This

In industrial compiler engines (such as GCC, Clang, and V8):

Industrial compilers translate high-level switch statements into machine code by dynamically choosing between three strategies based on case density:

• Linear Search: Emits sequential comparison jumps if case count $N \le 3$.
• Direct Jump Table: If case values are dense (e.g. 1, 2, 3, 4, 5), allocates an array of code pointers: void* table[] = { &&L1, &&L2, &&L3, ... };. Bounds-checks the input and executes an indirect jump jmp *table[expr] in $O(1)$ constant time regardless of case count!
• Binary Search Tree on Cases: If case values are sparse (e.g. 10, 500, 100000), generates a balanced binary tree of branches executing in $O(\log N)$ time.

In LLVM IR, backpatching is represented by attaching unlinked BasicBlock* pointers to branch instructions (BranchInst::Create(TrueBB, FalseBB, Cond)). Once the basic block's instructions are constructed, LLVM links the control-flow edge directly.

---

📐 Numerical Applications & Worked Examples

Example 1: Short-Circuit Three-Address Code Generation

Generate intermediate Three-Address Code with explicit instruction numbers starting at 100 for the statement:

if (a < b || c < d && e < f)
    x = 1;
else
    x = 0;

Step-by-Step Backpatching Trace:

1. Deconstruct Boolean Expression:

   • Operator precedence dictates: (a < b) || ((c < d) && (e < f))
   • Let $B_1 = (a < b)$
   • Let $B_2 = (c < d)$
   • Let $B_3 = (e < f)$
   • Let $B_{23} = B_2 \land\land B_3$
   • Overall: $B = B_1 \lor\lor B_{23}$

2. Instruction Emission:

   • For $B_1$:
     • 100: if a < b goto _ $\implies B_1.\text{truelist} = \{100\}$
     • 101: goto _ $\implies B_1.\text{falselist} = \{101\}$
   • $B_1$ fails $\implies$ fallthrough to evaluate $B_{23}$ at nextinstr = 102.
     • $\text{backpatch}(B_1.\text{falselist}, 102) \implies$ Line 101 becomes 101: goto 102.
   • For $B_2$:
     • 102: if c < d goto _ $\implies B_2.\text{truelist} = \{102\}$
     • 103: goto _ $\implies B_2.\text{falselist} = \{103\}$
   • In $B_2 \land\land B_3$, if $B_2$ is true $\implies$ jump to $B_3$ at 104.
     • $\text{backpatch}(B_2.\text{truelist}, 104) \implies$ Line 102 becomes 102: if c < d goto 104.
   • For $B_3$:
     • 104: if e < f goto _ $\implies B_3.\text{truelist} = \{104\}$
     • 105: goto _ $\implies B_3.\text{falselist} = \{105\}$
   • Combine $B_{23}$:
     • $B_{23}.\text{truelist} = B_3.\text{truelist} = \{104\}$
     • $B_{23}.\text{falselist} = \text{merge}(B_2.\text{falselist}, B_3.\text{falselist}) = \{103, 105\}$
   • Combine $B = B_1 \lor\lor B_{23}$:
     • $B.\text{truelist} = \text{merge}(B_1.\text{truelist}, B_{23}.\text{truelist}) = \{100, 104\}$
     • $B.\text{falselist} = B_{23}.\text{falselist} = \{103, 105\}$

3. Then-Block ($x = 1$):

   • Starts at instruction 106.
   • $\text{backpatch}(B.\text{truelist}, 106) \implies$ Lines 100 and 104 jump to 106.
   • 106: x = 1
   • 107: goto _ (Escape branch over else-block, added to $S.\text{nextlist} = \{107\}$).

4. Else-Block ($x = 0$):

   • Starts at instruction 108.
   • $\text{backpatch}(B.\text{falselist}, 108) \implies$ Lines 103 and 105 jump to 108.
   • 108: x = 0
   • Next statement begins at 109.
   • $\text{backpatch}(S.\text{nextlist}, 109) \implies$ Line 107 becomes 107: goto 109.

Final Generated Instruction Stream:

100: if a < b goto 106
101: goto 102
102: if c < d goto 104
103: goto 108
104: if e < f goto 106
105: goto 108
106: x = 1
107: goto 109
108: x = 0
109: ... (next statement)

---

Example 2: While Loop Translation with Backpatching

Construct the SDD rules and generate code for the while loop:

$$S \to \textbf{while} \; M_1 \; (B) \; M_2 \; S_1$$

Trace the generated instructions for:

while (i < 10)
    i = i + 1;

Step-by-Step Code Generation (Starting at 200):

• $M_1.\text{instr} = 200$.
• Evaluate $B = (i < 10)$:
  • 200: if i < 10 goto _ $\implies B.\text{truelist} = \{200\}$
  • 201: goto _ $\implies B.\text{falselist} = \{201\}$
• $M_2.\text{instr} = 202$.
  • $\text{backpatch}(B.\text{truelist}, 202) \implies$ Line 200 becomes 200: if i < 10 goto 202.
• Loop body $S_1$ ($i = i + 1$):
  • 202: t1 = i + 1
  • 203: i = t1
• Loop loop-back:
  • 204: goto 200
• Exit backpatch:
  • When the loop terminates, any jump on $S_1.\text{nextlist}$ targets 200.
  • $S.\text{nextlist} = B.\text{falselist} = \{201\}$, which backpatches to point to the instruction immediately following line 204 (i.e. 205).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why is an unconditional escape branch mandatory after the then-block in if-then-else translation?"
Key Focus Points:

• In linearized assembly/three-address code, the else-block physically follows the then-block in sequential memory.
• Without an unconditional jump goto exit at the end of the then-block, successful execution of the then-block would fall through and execute the else-block as well!

Question 2: "What are the three core primitives of the backpatching algorithm?"
Key Focus Points:

• makelist(i): Creates a new linked list containing the single instruction address $i$.
• merge(p1, p2): Concatenates two jump lists into a single unified list.
• backpatch(p, target): Traverses list $p$, filling target address target into the empty destination slot of each instruction.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Evaluating all boolean subexpressions eagerly.
Answer: Violation of short-circuit semantics. In languages like C and Java, if $a$ is true in a || b(), function b() must never execute. Evaluating b() alters side effects and can cause fatal errors (e.g. checking ptr != NULL && *ptr == 5).

Trap 2: Losing track of break and continue statements in loops.
Answer: Control-flow corruption. A continue statement inside a loop must jump back to the loop header/condition evaluation ($M_1.\text{instr}$). A break statement must be merged directly into the loop's exit list ($S.\text{nextlist}$).

---

🗺️View Complete Compiler Design Roadmap & Syllabus

← Previous Topic7.2 Syntax Trees, Directed Acyclic Graphs & Value NumberingNext Topic →8.1 Basic Blocks, Flow Graphs & Control Flow Analysis