The Gateway to Computer Science Excellence
+13 votes
1.8k views

The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment.

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; 
}

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.

  1. 3
  2. 4
  3. 5
  4. 6
in Compiler Design by Veteran (104k points) | 1.8k views
0
this is still in syllabus asked in 2017
0

If there are not enough registers to hold all the variables, some variables may be moved to and from RAM. This process is called "spilling" the registers. Over the lifetime of a program, a variable can be both spilled and stored in registers: this variable is then considered as "split".

2 Answers

+16 votes
Best answer

Here, we are told not to do code motion. So, we start with 3 registers

c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, e in register, d spilled. 

So, now we try with 4 registers

c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, d, e in register
x = c * c; //a, x, d, e in register
if (x > a) { 
 y = a * a; 
} 
else { 
 d = d * d; 
 e = e * e; 
} 

No spilling. So, 4 is the minimum number of registers needed for avoiding spilling. (If code motion was allowed, we need only 3 registers for avoiding spilling).

by Veteran (422k points)
selected by
0

$\text{sir , why you have not considered registers(?) below the code }$

if (x > a) { 
 y = a * a; 
} 
else { 
 d = d * d; 
 e = e * e; 
} 
0
Thanks sir  for this wonderful explanation.
+9 votes

Here 4 registers are needed


 

by Boss (38.3k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,167 answers
193,836 comments
93,997 users