Compiler Design MCQs - Code Optimisation and Code Generation (Set 6)

Q1. A compiler replaces the statement x = 2 * 3.14 * 5 with x = 31.4 at compile time. Which optimisation is this?

a) Strength reduction

b) Code motion

c) Copy propagation

d) Constant folding

Q2. Replacing the computation y = x * 2 with y = x + x or y = x << 1 is an example of

a) constant folding

b) strength reduction

c) dead code elimination

d) loop unrolling

Q3. In the loop below, x and y are not modified inside the loop. Moving the computation of x * y before the loop is called

for (i = 0; i < n; i++) {
    a[i] = x * y + i;
}

a) loop unrolling

b) induction variable elimination

c) loop invariant code motion

d) loop fusion

Q4. How many basic blocks does the three-address code below contain?

1: s = 0
2: i = 0
3: if i >= n goto 8
4: t = i * 4
5: s = s + a[t]
6: i = i + 1
7: goto 3
8: print s

a) 3

b) 5

c) 4

d) 6

Q5. Which variables are live immediately after statement 2, that is, just before statement 3, in the code below?

1: a = b + c
2: d = a - e
3: a = d * 2
4: return a + b

a) {b, d}

b) {a, b, d}

c) {d}

d) {b, d, e}

Q6. Live variable analysis is classified as which kind of data-flow problem?

a) Forward, with union as the meet operator

b) Backward, with union as the meet operator

c) Forward, with intersection as the meet operator

d) Backward, with intersection as the meet operator

Q7. Which data-flow analysis is a forward problem that uses intersection as its meet operator?

a) Live variables

b) Reaching definitions

c) Available expressions

d) Very busy expressions

Q8. In the code below, can line 4 be replaced with t3 = t1 by common subexpression elimination?

1: t1 = a + b
2: t2 = c * t1
3: a = d
4: t3 = a + b

a) Yes, because the expression text a + b is identical

b) No, because a is reassigned between the two computations of a + b

c) Yes, because b is unchanged

d) No, because t1 is used in line 2

Q9. A code generator emits MOV R0, a followed immediately by MOV a, R0, with no label on the second instruction. Deleting the second instruction is an example of

a) register allocation by graph colouring

b) peephole redundant-instruction elimination

c) loop unrolling

d) procedure inlining

Q10. In an interference graph used for register allocation, an edge between variables u and v means

a) u is defined using v

b) u and v are live at the same point, so they cannot share a register

c) u and v always hold the same value

d) u and v must be spilled to memory

Q11. The interference graph has edges a-b, b-c, c-a and c-d. What is the minimum number of registers needed to hold all four variables without spilling?

a) 3

b) 2

c) 4

d) 1

Q12. What is the primary benefit of loop unrolling?

a) It reduces loop-control overhead such as branch and increment instructions per useful operation

b) It always reduces the size of the generated code

c) It removes all loop-invariant computations

d) It converts the loop into recursion

Q13. In a control flow graph, an edge n -> d forms a natural loop with header d when

a) d dominates n

b) n dominates d

c) d and n are in the same basic block

d) d has no predecessors

Q14. After the instruction x = y, a compiler rewrites the later statement z = x + 1 as z = y + 1. Which optimisation is this?

a) Constant folding

b) Strength reduction

c) Copy propagation

d) Code hoisting

Q15. The Sethi-Ullman algorithm is used to

a) compute dominators in a flow graph

b) detect natural loops

c) build the LR(1) parsing table

d) generate code for an expression tree using the minimum number of registers without spilling

Q16. Which definitions of x reach the statement labelled L in the code below?

d1: x = 5
d2: y = x + 1
d3: if y > 3 goto L
d4: x = 7
L:  z = x + y

a) d1 only

b) d4 only

c) Neither d1 nor d4

d) d1 and d4

Q17. Inside a loop, i is incremented by 1 on each iteration and j is always computed as j = 4 * i. In this situation j is called

a) a derived induction variable

b) a basic induction variable

c) a loop-invariant variable

d) a dead variable

Q18. Which statement in the function below can be removed by dead code elimination?

int f(int a) {
    int b = a * 2;
    int c = a + 3;
    return c;
}

a) int c = a + 3;

b) return c;

c) None, because every statement affects the result

d) int b = a * 2;