"Intermediate Code Generation" — Practice

Question 1

How many temporaries does a naive three-address translation of a times b plus c times d minus e require?

Accepted Answer

C

Question 2

Which intermediate representation makes instruction reordering easiest?

Accepted Answer

B

Question 3

Converting an integer to a floating-point value is an example of

Accepted Answer

B

Question 4

Generate three-address code for (a plus b) times (a plus b) plus (a plus b), first naively and then using a directed acyclic graph, and compare the counts.

Accepted Answer

Naively, each occurrence of the parenthesised subexpression is translated independently.

t1 = a plus b
t2 = a plus b
t3 = t1 times t2
t4 = a plus b
t5 = t3 plus t4

That is five temporaries, three additions of a and b, and one multiplication — eight operations counting the final addition.

Now build the directed acyclic graph. The expression a plus b appears three times, and in a DAG all three occurrences share one node. The multiplication node takes that shared node as both operands, and the final addition takes the multiplication result and the shared node again.

Regenerating from the DAG:

t1 = a plus b
t2 = t1 times t1
t3 = t2 plus t1

That is three temporaries and three operations.

The saving is two additions and two temporaries, achieved purely by recognising that identical subexpressions compute identical values within a basic block.

The reason the DAG makes this easy is that construction itself performs the recognition: when building a node, the compiler first checks whether a node with the same operator and the same two children already exists, and reuses it if so. No separate common-subexpression analysis pass is required, which is why the DAG is the standard representation for optimising within a basic block.

Question 5

An array B[5][8] of 8-byte elements has base address 4000 and lower bounds of 0 in both dimensions. Compute the address of B[3][6] in row-major order and give the generated three-address code for B[i][j].

Accepted Answer

With zero lower bounds the row-major formula simplifies.

Address = base plus (i times number-of-columns plus j) times element size.

For B[3][6]: 4000 plus (3 times 8 plus 6) times 8 = 4000 plus 30 times 8 = 4000 plus 240 = 4240.

For the general code, expand and separate compile-time constants from run-time work.

Address = 4000 plus (8i plus j) times 8 = 4000 plus 64i plus 8j.

The constant 4000 and both multipliers, 64 and 8, are known at compile time. The generated three-address code is:

t1 = i times 64
t2 = j times 8
t3 = t1 plus t2
t4 = t3 plus 4000
t5 = contents of t4

Two multiplications and two additions at run time, with the compiler having folded everything it could.

A check on the specific case: i equals 3 gives t1 as 192, j equals 6 gives t2 as 48, their sum is 240, and adding 4000 gives 4240, matching the direct computation.

Note that had the lower bounds been 1 rather than 0, the formula would gain a constant correction of minus 64 minus 8, which folds into the base to give 3928 instead of 4000. The run-time code would be identical apart from that one constant, which is exactly the point of separating the compile-time part.

Question 6

Translate a while loop with condition a less than b and body x = x plus 1 into three-address code, and state where the condition test is placed and why.

Accepted Answer

The standard translation places the condition at the top and jumps back to it after the body.

L1: if a less than b goto L2
    goto L3
L2: x = x plus 1
    goto L1
L3:

Control enters at L1, tests the condition, and either enters the body at L2 or exits to L3. After the body, the unconditional jump returns to L1 to re-test.

An optimised version inverts the test and removes one jump from the loop path:

L1: if a greater-or-equal b goto L3
    x = x plus 1
    goto L1
L3:

This saves an instruction on every iteration, which matters because loop bodies execute repeatedly.

A further standard optimisation moves the test to the bottom and guards the loop with a single entry test, so that the steady-state path contains one conditional jump rather than one conditional plus one unconditional. That transformation is called loop inversion and is why compiled loops often look inside-out relative to the source.

As to placement: the condition must be tested before the first iteration, because a while loop may execute zero times. A do-while loop places the test at the bottom precisely because it is guaranteed at least one iteration, and its translation needs no leading jump at all.

Note also that the condition produces no value anywhere in this code. Its entire meaning is expressed in which label control reaches, which is what jump-based Boolean translation means.

Question 7

Explain how backpatching translates the condition a less than b and c less than d in one pass, listing the instructions generated and the list operations performed.

Accepted Answer

The parser reduces the first operand, then the second, then the AND, generating code as it goes and never revisiting.

Step 1: reduce a less than b. Emit two instructions with blank targets.

100: if a less than b goto ___
101: goto ___

Makelist(100) becomes the true list; makelist(101) becomes the false list.

Step 2: the AND production has a marker before its second operand, which records the current instruction address, 102. Since the whole expression is true only if both operands are, the first operand being true means the second must be tested. Backpatch the first operand's true list with 102.

Instruction 100 becomes: if a less than b goto 102.

Step 3: reduce c less than d, emitting at 102 and 103.

102: if c less than d goto ___
103: goto ___

Makelist(102) is its true list; makelist(103) is its false list.

Step 4: complete the AND. The combined expression is true exactly when the second operand is true, so the combined true list is simply the second operand's true list, containing 102.

The combined expression is false when either operand is false, so the combined false list is the merge of the two false lists, containing 101 and 103.

Both remaining lists travel upward with the expression, to be backpatched by whatever construct encloses it — the true list with the start of the then-branch and the false list with whatever follows.

The key property is that no instruction is ever revisited except to have a blank target filled, and every fill happens at the earliest moment the address is known. That is what makes single-pass generation possible without building a syntax tree.

Question 8

An optimiser wants to move an instruction earlier within a basic block. Compare the cost under quadruples, triples and indirect triples, and explain which the optimiser should prefer.

Accepted Answer

Under quadruples, each instruction names its result in an explicit fourth field, and later instructions refer to that value by name. Moving an instruction changes only its position in the sequence; every reference still resolves to the same name.

The cost is constant: unlink and relink, with no other instruction touched. The only correctness obligation is not moving an instruction past a definition or use that would change its meaning, which is a dependence question rather than a representation one.

Under triples, an instruction has no result field, and later instructions refer to its result by its position in the list. Moving instruction 3 to position 1 means every reference written as (3) is now wrong, and every reference to instructions between the old and new positions has also shifted.

The cost is a full scan of the block to renumber references, which is linear in the block size per move. An optimiser performing many moves would pay quadratically overall, which is why triples are described as suiting non-optimising compilers.

Under indirect triples, the triples themselves live in a fixed array and are never moved. A separate list of pointers determines the execution order, and reordering permutes only that list.

Since the triples keep their storage positions, all internal references remain valid, and the cost per move is constant, matching quadruples.

The optimiser should prefer quadruples or indirect triples. Between them, quadruples make temporaries explicit, which lets the optimiser reason about a value's live range for register allocation. Indirect triples save the space of naming temporaries but give up that visibility. For a compiler doing serious optimisation, the naming is worth the space, which is why quadruples dominate in practice.

Question 9

Give three concrete cases where full and short-circuit evaluation of a Boolean expression produce different program behaviour, and explain why the choice belongs in the language specification.

Accepted Answer

Case one, guarded dereference. The expression p is not null AND p arrow value is greater than zero. Under short-circuiting, a null pointer makes the first operand false, the result is determined, and the dereference never executes. Under full evaluation the dereference happens regardless and the program crashes. The idiom is ubiquitous and depends entirely on the guarantee.

Case two, guarded indexing. The expression i is less than n AND array at i is greater than zero. Short-circuiting prevents an out-of-bounds read when i equals n, which is exactly the boundary a loop reaches on its final test. Full evaluation reads past the end, producing either a wrong answer or a fault.

Case three, side effects. The expression flag OR increment of counter. Under short-circuiting, a true flag means the function is never called and the counter never changes. Under full evaluation it is always called. The two produce different program state, not merely different timings, and no amount of reasoning about the Boolean result reveals the difference.

The choice belongs in the language specification rather than the compiler because programs depend on it for correctness. If a compiler were free to choose, the guarded dereference idiom would be unsafe, and every such expression would need rewriting as a nested conditional. Portable code would become substantially more verbose, and a program correct under one compiler could crash under another.

That is why C, Java and most modern languages mandate short-circuiting for their logical operators and provide separate bitwise operators for cases where full evaluation is wanted. For the compiler writer the consequence is direct: the jump-based translation is not an alternative implementation but the required one, and generating code that evaluates both operands is a correctness bug rather than a missed optimisation.

Practice — "Intermediate Code Generation"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities