TAC for if/while and Boolean expressions (short-circuit; backpatching brief)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Address of A[3][5] in int A[10][20], base 1000, row-major from 0? from Lesson 4.2.2
• Give the form of a conditional jump in three-address code. from Lesson 4.2.1
• In C, which if does an else belong to when ifs are nested without braces? from Lesson 2.1.2

1 · The Story

📖

Detours

Mr. Patel’s speech has conditions: “If the monsoon is good or exports grow and the rupee is stable, we expand.” Dev cannot write that as arithmetic. He writes detour cards: “if the monsoon is good, jump to the EXPAND card; otherwise go to the next check”.

Dev notices he never needs to check everything. If the monsoon is good, the whole condition is true no matter what follows: he jumps straight to EXPAND. If exports did not grow, the “and” part is already false: he skips the rupee check.

One annoyance: when Dev writes “jump to EXPAND”, he often does not yet know which card number EXPAND will get. He leaves the number blank and keeps a list of cards with blanks, then fills them all in when EXPAND is finally written.

2 · Predict First

🤔

For if (a < b || c < d && e < f) x = 1; else x = 2;, if a < b is true, are c < d and e < f evaluated? Write your guess down. The answer is in the vault.

3 · Core Concept

Jumping code for Boolean expressions

A Boolean expression B in a condition is translated into jumps rather than a 0/1 value. B has two exits, B.true and B.false:

• a < b: if a < b goto B.true, goto B.false;
• B₁ || B₂: B₁.true = B.true; B₁.false = a new label where B₂ starts; B₂ takes B’s exits;
• B₁ && B₂: B₁.true = a new label where B₂ starts; B₁.false = B.false; B₂ takes B’s exits;
• !B₁: swap the exits.

This is short-circuit evaluation: the second operand is skipped when the first decides the result (C’s && and || are defined this way).

Statements

if (B) S1            B.code (true → L1, false → next)  L1: S1.code  next:
if (B) S1 else S2    B.code (true → L1, false → L2)    L1: S1.code  goto next  L2: S2.code  next:
while (B) S1         begin: B.code (true → L1, false → next)  L1: S1.code  goto begin  next:

Backpatching (brief)

In one pass, jump targets are often unknown when the jump is emitted. Backpatching emits jumps with empty targets and keeps lists of them: truelist and falselist for Boolean expressions, nextlist for statements. When the target becomes known, backpatch(list, target) fills every jump in the list. For B → B₁ || M B₂ (M records the start of B₂): backpatch(B₁.falselist, M.instr); truelist = B₁.truelist ∪ B₂.truelist; falselist = B₂.falselist. For &&: backpatch(B₁.truelist, M.instr); truelist = B₂.truelist; falselist = B₁.falselist ∪ B₂.falselist.

Story → compiler term

4 · Visual

if a < b goto L1
    goto L4
L4:
    if c < d goto L5
    goto L3
L5:
    if e < f goto L1
    goto L3
L1:
    x = 1
    goto L2
L3:
    x = 2
L2:

Generated jumping code for if (a < b || c < d && e < f) x = 1; else x = 2; (9 instructions, 5 labels). Some jumps go to the very next instruction: a simple translator does not optimise them.

100: if a < b goto _
101: goto 102
102: if c < d goto 104
103: goto _
104: if e < f goto _
105: goto _

Backpatching the condition alone, quads from 100: truelist = { 100, 104 }, falselist = { 103, 105 } (the Dragon-book example, recomputed).

5 · Worked Examples

Example 1 Easy

Translate while (i < 10) { s = s + i; i = i + 2; } preceded by s = 0; i = 0; and followed by t = s * 2.

Solution

( 1) s = 0
( 2) i = 0
( 3) if i < 10 goto (5)
( 4) goto (8)
( 5) s = s + i
( 6) i = i + 2
( 7) goto (3)
( 8) t = s * 2

8 instructions. The condition is tested at the top; the body ends with a jump back. Dev’s detour cards: “if i < 10 go to the body, otherwise leave”.

Example 2 Medium

Translate if (x > 0 && y > 0) z = 1; else z = 0; w = z + 1; with numbered instructions.

Solution

( 1) if x > 0 goto (3)
( 2) goto (7)
( 3) if y > 0 goto (5)
( 4) goto (7)
( 5) z = 1
( 6) goto (8)
( 7) z = 0
( 8) w = z + 1

If x > 0 fails, instruction 2 jumps straight to the else part: y is never compared. 8 instructions.

Example 3 GATE

Backpatch a < b || c < d && e < f with quads starting at 100. Which instructions remain on the truelist and falselist?

Solution

a < b gives 100 (true) and 101 (false). c < d gives 102/103, e < f gives 104/105. The && backpatches 102’s true jump to 104; the || backpatches 101 to 102. Remaining: truelist { 100, 104 }, falselist { 103, 105 }, filled later by the enclosing statement.

6 · Shortcuts

⚡

Instruction count for a condition in jumping code = 2 per relational comparison (if … goto, goto). Valid when: conditions built from relational operators with &&, ||, ! (no fall-through optimisation).

⚡

|| : backpatch the first falselist; && : backpatch the first truelist. Valid when: backpatching questions.

7 · GATE Traps

⚠️

• In short-circuit code the right operand may never be evaluated; side effects in it may not happen.
• ! generates no instruction: it swaps the true and false exits.
• A while loop tests the condition at the top and needs a jump back at the end of the body.
• With backpatching, the || rule fills B₁.falselist; the && rule fills B₁.truelist.
• Unoptimised jumping code can contain a jump to the very next instruction.

8 · Memory Hook

🧠

OR: first true wins, fall to the next test only on false. AND: first false loses, go to the next test only on true.

9 · Connect the Dots

The draft now contains straight-line pieces and jumps. Before improving it, it helps to give every assignment a unique variable version; the next lesson introduces that form.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markShort-circuit

In jumping code for B₁ || B₂, the false exit of B₁ goes to:

• (A) B.false
• (B) the start of B₂
• (C) B.true
• (D) the end of the program

Q2NAT2 marksCount

Using the jumping-code scheme of this lesson (2 instructions per comparison, no fall-through optimisation), how many instructions are generated for if (p == q || r == s || t == u) v = 1;?

Numerical answer: ________

Q3MCQ2 marksBackpatching

Backpatching !(a < b) && c > d from 100, the final truelist is:

• (A) { 100 }
• (B) { 102 }
• (C) { 100, 102 }
• (D) { 101, 103 }

Q4MSQ1 markWhile

Which are part of the standard translation of while (B) S?

• (A) a label before the condition
• (B) a jump back to the condition at the end of S
• (C) evaluating S before testing B
• (D) B.false leading to the code after the loop

Q5NAT1 markCount

How many instructions does the jumping-code translation of if (x > 0 && y > 0) z = 1; else z = 0; w = z + 1; contain?

Numerical answer: ________

11 · Rule Card

• Relop: if a relop b goto B.true; goto B.false.
• ||: B₁.true = B.true, B₁.false → start of B₂. &&: B₁.true → start of B₂, B₁.false = B.false. !: swap.
• if: B; L1: S1; next. if-else: B; L1: S1; goto next; L2: S2; next. while: begin: B; L1: S; goto begin; next.
• Backpatching: truelist/falselist/nextlist; || fills B₁.falselist, && fills B₁.truelist.

12 · Concept Ledger

jumping codeB.true / B.falseshort-circuit evaluationlabelbackpatchingtruelist / falselist / nextlist

13 · Answer Vault