Intermediate Code Generation in Compiler Design: One Cross-Concept Worked Example

A learner may understand syntax trees, three-address code, type conversion, array addressing and control flow separately, then get stuck when one question makes all five interact. One C-like fragment connects source facts to typed temporaries, TAC, quadruples and a control-flow graph. The goal is to preserve its meaning at every representation, not merely memorise tuple formats.

1. What intermediate code generation must preserve

Intermediate code generation turns an analysed source representation into a machine-independent form. The pipeline is:

source -> AST plus symbol/type attributes -> three-address code -> basic blocks/CFG -> later optimisation and target code

Optimisation consumes generated IR later, although a compiler may perform light canonicalisation while emitting it. Operator precedence fixes evaluation order. The symbol table supplies types and widths. Short-circuit Boolean evaluation fixes branch placement. Array indexing becomes address arithmetic followed by a load.

Three-address code, or TAC, keeps at most one principal operator on the right of each instruction. A quadruple records the same operation as (op, arg1, arg2, result). If those terms need revision before the example, the CS Fundamentals path places compiler design beside the supporting core subjects.

The published Intermediate Code Generation in Compiler Design: Three-Address Code, Quadruples, Triples and Worked Examples owns the comparison of TAC, quadruples, triples and DAGs. This trace instead follows an array-and-Boolean fragment through byte offsets, promotion, short-circuit branches and a CFG.

2. Fix one source fragment and all of its starting facts

The source fragment is:

int a[4] = {3, 5, 7, 9};
int i = 2;
float x = 4.5f;

if (i < 4 && a[i] > 5)
    x = x + a[i] * 2;
else
    x = x - 1.0f;

Assume an int occupies 4 bytes. For illustration only, let base(a) = 1000. The starting memory snapshot is a[0..3] = {3, 5, 7, 9}, while i is an int holding 2 and x is a float holding 4.5. Because the array initialisation is already represented by that snapshot, the TAC begins with i = 2 and x = 4.5f.

In the assignment AST, multiplication sits below addition, so a[i] * 2 is evaluated before adding x. The condition is short-circuit &&: evaluate a[i] > 5 only after i < 4 succeeds. This translation adds no bounds check that is absent from the source.

3. Derive addresses and types before emitting operations

First record the symbol and attribute facts:

The byte offset is i * width(int) = 2 * 4 = 8. The effective address is base(a) + offset = 1000 + 8 = 1008, and the value stored there is a[2] = 7.

The type path matters just as much. a[i] * 2 is integer multiplication, giving integer 7 * 2 = 14. Before adding that result to float x, emit inttofloat(14) = 14.0. Float addition then gives 4.5 + 14.0 = 18.5. The else arm stays in float arithmetic and would give 4.5 - 1.0 = 3.5 if taken. Keep address arithmetic, value loading and numeric conversion separate. Collapsing them mentally causes miscounted temporaries and wrongly typed results.

4. Generate the three-address code step by step

The baseline TAC uses a[t] to load from byte offset t relative to base(a). Instructions 7 and 8 deliberately repeat the offset calculation and load because this is pre-optimisation code.

 1  i = 2
 2  x = 4.5f
 3  if i >= 4 goto L_else
 4  t1 = i * 4
 5  t2 = a[t1]
 6  if t2 <= 5 goto L_else
 7  t3 = i * 4
 8  t4 = a[t3]
 9  t5 = t4 * 2
10  t6 = inttofloat(t5)
11  t7 = x + t6
12  x = t7
13  goto L_end
L_else:
14  t8 = x - 1.0f
15  x = t8
L_end:

The two tests branch on complements of the source conditions. Instruction 3 jumps before any array load when i < 4 is false, which is exactly short-circuit behaviour. Instruction 6 jumps when a[i] > 5 is false. Falling through both tests therefore means the complete && condition is true.

Now execute the live path. i >= 4 is false. Then t1 = 2 * 4 = 8, and t2 = a[8] = 7. Here a[8] means byte offset 8, which is source element a[2], not source element a[8]. Next, t2 <= 5 is false. The assignment path gives t3 = 8, t4 = 7, t5 = 7 * 2 = 14, t6 = 14.0, t7 = 4.5 + 14.0 = 18.5, and x = 18.5. Instruction 13 then jumps to L_end.

5. Convert the same TAC to quadruples and a CFG

The quadruples are:

loadIndex is the explicit array-load operator used here. Textbooks may spell it differently without changing the data flow.

The textual TAC above produces five blocks: B1 = 1-3, B2 = 4-6, B3 = 7-13, B4 = 14-15, and B5 = L_end/exit. B1 contains the two initialisations and first branch; B2 performs the first array load and second test; B3 and B4 are the true and else arms. The earlier Intermediate Code Generation in Compiler Design: TAC, Backpatching and DAGs owns backpatching and DAG reuse; this CFG starts from resolved labels and focuses on typed array addressing.

The CFG edges are B1 -> B4 when i >= 4 and B1 -> B2 otherwise; B2 -> B4 when t2 <= 5 and B2 -> B3 otherwise; B3 and B4 both lead to B5. For i = 2 and a[2] = 7, the executed path is B1 -> B2 -> B3 -> B5.

6. Traps that change the generated answer

• Mistake: Load the array before testing i < 4. Consequence: Short-circuit order breaks. Correction: Instruction 3 must branch before the load.

• Mistake: Read a[t1] as source index 8. Consequence: Byte-offset meaning disappears. Correction: Offset 8 means source element a[2].

• Mistake: Omit inttofloat. Consequence: Mixed types become hidden. Correction: Convert integer 14 to float 14.0 before addition.

• Mistake: Branch on i < 4 to L_else. Consequence: The meaning reverses. Correction: Branch on the false complement, i >= 4.

• Mistake: Apply common-subexpression elimination while counting baseline TAC. Consequence: Count changes. Correction: Separate generation from optimisation.

The earlier Intermediate Code Generation Across Compiler Concepts: Worked TAC, Quadruples and DAG Optimisation owns DAG reuse for a repeated arithmetic expression. Here, reusing t2 to remove instructions 7 and 8 is safe only because no write, alias or call changes i or a between loads.

7. How an exam question can combine the concepts

A question can ask you to count TAC instructions or temporaries under a stated translation scheme, fill a missing quadruple field or identify a byte offset, or trace the CFG to find the final value. For this baseline, the checks are 15 instructions, temporaries t1 through t8, byte offset 8, loaded integer 7, and final x = 18.5.

Counts depend on whether the scheme makes array loads and conversions explicit, so follow the convention stated in the question. When you practise mixed questions of this kind, re-derive the offset, the conversion and the final value every time. Use the pipeline to reach the answer, not a memorised instruction count.

8. Short version and the next study step

Remember: AST order decides evaluation, symbol attributes decide width and conversion, TAC exposes operations and jumps, and basic blocks expose paths. Decisive values are offset 8, loaded value 7, promoted product 14.0, and final x = 18.5.

For full-subject study, continue with the Zero to Hero Complete CS Course. Then change the condition or array index; re-derive branches, offset and conversion.