The GATE Grind

GATE 2013 CS (CS1) – Question 58

Compiler Design · Code Optimization and Data Flow Analysis · 2 marks · Multiple choice

A processor permits register operands only, at most two sources and one destination per instruction. All variables are dead after this segment. Only correctness-preserving code motion is allowed. With two registers, find the minimum memory spills.

c=a+b;
d=c*a;
e=c+a;
x=c*c;
if (x>a) { y=a*a; }
else { d=d*d; e=e*e; }
  1. 0
  2. 1
  3. 2
  4. 3

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 1

Explanation

Move d=c*a and e=c+a into the else branch, immediately before their respective squarings, because only that branch uses them. At the branch test a,c,x would otherwise require three values, so spill c once and use its register for x. After the branch reload c as needed while producing and squaring d and e in place. Thus one spill suffices and zero cannot preserve all three needed values. Answer B; dead-code elimination is excluded.

More Code Optimization and Data Flow Analysis questions

All Code Optimization and Data Flow Analysis questions →