Code Generation and Optimization - Compiler Design - Computer Science & Information Technology Previous Year Questions

1

2007 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2007

In a simplified computer the instructions are:
OP R_i,R_j - Performs R_i OP R_j and stores the result in register R_i.
OP m,R_i - Performs val OP R_i and stores the result in R_i. val denotes the content of memory location m.
MOV m,R_i - Moves the content of memory location m to register R_i.
MOV R_i,m - Moves the content of register R_i to memory location m.
The computer has only two registers, and OP is either ADD or SUB. Consider the following basic block:
t₁ = a + b
t₂ = c + d
t₃ = e – t₂
t₄ = t₁ – t₃
Assume that all operands are initially in memory. The final value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block?

A

2

B

3

C

5

D

6

Open complete paper

2

2008 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2008

Some code optimizations are carried out on the intermediate code because

A

they enhance the portability of the compiler to other target processors

B

program analysis is more accurate on intermediate code than on machine code

C

the information from dataflow analysis cannot otherwise be used for optimization

D

the information from the front end cannot otherwise be used for optimization

Open complete paper

3

2010 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2010

The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side?

A

19

B

21

C

20

D

10

Open complete paper

4

2010 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2010

The program below uses six temporary variables a, b, c, d, e, f.
a = 1
b = 10
c = 20
d = a + b
e = c + d
f = c + e
b = c + e
e = b + f
d = 5 + e
return d + f
Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

A

2

B

3

C

4

D

6

Open complete paper

5

2013 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2013 [Session 1]

Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?

A

0

B

1

C

2

D

3

Open complete paper

6

2013 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2013 [Session 1]

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation.

A

3

B

4

C

5

D

6

Check answer

Open complete paper

7

2014 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2014 [Session 1]

Which one of the following is FALSE?

A

A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.

B

Available expression analysis can be used for common subexpression elimination.

C

Live variable analysis can be used for dead code elimination.

D

x = 4 * 5 ⇒ x = 20 is an example of common subexpression elimination.

Open complete paper

8

2014 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2014 [Session 3]

One of the purposes of using intermediate code in compilers is to

A

make parsing and semantic analysis simpler.

B

improve error recovery and error reporting.

C

increase the chances of reusing the machine-independent code optimizer in other compilers.

D

improve the register allocation.

Open complete paper

9

2014 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2014 [Session 3]

Consider the basic block given below.
a = b + c
c = a + d
d = b + c
e = d - b
a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

A

6 and 6

B

8 and 10

C

9 and 12

D

4 and 4

Open complete paper

10

2015 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2015 [Session 2]

Consider the intermediate code given below.
(1)  i = 1
(2)  j = 1
(3)  t1 = 5 * i
(4)  t2 = t1 + j
(5)  t3 = 4 * t2
(6)  t4 = t3
(7)  a[t4] = -1
(8)  j = j + 1
(9)  if j <= 5 goto (3)
(10)  i=i+1
(11)  if i < 5 goto (2)
The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are

A

5 and 7

B

6 and 7

C

5 and 5

D

7 and 8

Open complete paper

11

2021 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2021 [Session 2]

Consider the following ANSI C code segment:
z = x + 3 + y->f1 + y->f2;
for (i = 0; i < 200; i = i + 2) {
if (z > i) {
p = p + x + 3;
q = q + y->f1;
} else {
p = p + y->f2;
q = q + x + 3;
}
}
Assume that the variable y points to a struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y->f1 or y->f2) in the optimized code, respectively, are:

A

403 and 102

B

203 and 2

C

303 and 102

D

303 and 2

Open complete paper

12

2021 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2021 [Session 2]

For a statement \(S\) in a program, in the context of liveness analysis, the following sets are defined:

\(USE(S)\) : the set of variables used in \(S\)

\(IN(S)\) : the set of variables that are live at the entry of \(S\)

\(OUT(S)\) : the set of variables that are live at the exit of \(S\)

Consider a basic block that consists of two statements, \(S_1\) followed by \(S_2\). Which one of the following statements is correct?

A

\(OUT(S_1) = IN(S_2)\)

B

\(OUT(S_1) = IN(S_1) \cup USE(S_1)\)

C

\(OUT(S_1) = IN(S_2) \cup OUT(S_2)\)

D

\(OUT(S_1) = USE(S_1) \cup IN(S_2)\)

Open complete paper

13

2024 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2024 [Session 1]

Consider the following pseudo-code.
L1: t1 = -1
L2: t2 = 0
L3: t3 = 0
L4: t4 = 4 * t3
L5: t5 = 4 * t2
L6: t6 = t5 * M
L7: t7 = t4 + t6
L8: t8 = a[t7]
L9: if t8 <= max goto L11
L10: t1 = t8
L11: t3 = t3 + 1
L12: if t3 < M goto L4
L13: t2 = t2 + 1
L14: if t2 < N goto L3
L15: max = t1
Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively ?

A

6 and 6

B

6 and 7

C

7 and 7

D

7 and 6

Open complete paper

14

2024 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2024 [Session 2]

Consider the following expression: x[i] = (p + r) * -s[i] + u/w. The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6).

(0)	+	p	r
(1)
(2)	uminus	(1)
(3)
(4)	/	u	w
(5)	+	(3)	(4)
(6)
(7)	=	(6)	(5)

Which one of the following options fills in the missing entries CORRECTLY?

A

(1) []= s i (3) * (0) (2) (6) []= x i

B

(1) []= s i (3) - (0) (2) (6) =[] x (5)

C

(1) =[] s i (3) * (0) (2) (6) []= x (5)

D

(1) =[] s i (3) - (0) (2) (6) =[] x i

Open complete paper

15

2025 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2025 [Session 1]

Which ONE of the following techniques used in compiler code optimization uses live variable analysis?

A

Run-time function call management

B

Register assignment to variables

C

Strength reduction

D

Constant folding

Open complete paper

16

2025 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2025 [Session 1]

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is ______. (Answer in integer)

Check answer

Open complete paper

17

2025 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2025 [Session 2]

Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
(I) Backpatching can be used to generate code for Boolean expression in one pass.
(II) Backpatching can be used to generate code for flow-of-control statements in one pass.
Which ONE of the following options is CORRECT?

A

Only (I) is correct.

B

Only (II) is correct.

C

Both (I) and (II) are correct.

D

Neither (I) nor (II) is correct.

Open complete paper

18

2011 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2011

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables \(a, b, c, d\) and \(e\) are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

A

2

B

9

C

5

D

3

Open complete paper

19

2017 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science & Information Technology (CS) 2017 [Session 1]

Consider the expression \((a-1)*(((b+c)/3)+d)\)). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is __________.

Check answer

Open complete paper

20

2026 · Computer Science & Information Technology · Compiler Design · Code Generation and Optimization

Computer Science and Information Technology (CS) 2026

Consider the control flow graph shown in the figure.
Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?
Note: All the variables are integers.

A

B4: { b + i }
B5: { c + m }

B

B4: { g * k }
B5: { c + m }

C

B4: { g * k, b + i }
B5: { }

D

B4: { g * k }
B5: { }

Open complete paper