The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
4.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; 
} 

Q.48 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?

  1. 0
  2. 1
  3. 2
  4. 3
asked in Compiler Design by Veteran (355k points)
retagged by | 4.8k views
0
Is it OUT OF SYLLABUS NOW??
+4

Somehow it is related to intermediate code optimization and is in the syllabus .

in 2011 one two marks question came from this topic https://gateoverflow.in/2138/gate2011_36

even in this year 2017 a question came from this topic, https://gateoverflow.in/118746/gate2017-1-52

so definitely have to read ..

need to study .

+3
We cannot say out of syllabus
this year also came a question from spilling
+1
yes, From spilling topic question came 3 times  2011, 2013 and now in 2017 .
0
yes plz see my question at end?
0
code optimization is out of syllabus but register allocation is in syllabus so this code motion part shouldnt be asked in the question but they asked min number of registers in 2017

3 Answers

+13 votes
Best answer
We can do code motion as follows:

c = a + b; //a and b in register and b replaced by the result c after the instruction
x = c * c; //x replaces c in register and c is spilled (moved to memory)
if (x > a) { //x and a in memory
 y = a * a; 
 d = c * a; //spilled c taken from memory and replaces x in register. 
 e = c + a; 
} 
else { 
 d = c * a; //spilled c taken from memory and replaces x in register. d replaces a in register
 d = d * d; //c and d in register
 e = c + a; //a  taken from memory and e replaces c in register (a taken from memory is not a spill, it is a fill)
 e = e * e; 
} 

So, we need minimum 1 spill in the compiled code.

https://en.wikipedia.org/wiki/Register_allocation 

answered by Veteran (355k points)
selected by
+1

@srestha
x should be stored in memory but not a, for detailed solution see the pic posted by me below. please note that only code motion is used as code optimization technique. see the following pic:

https://gateoverflow.in/?qa=blob&qa_blobid=1725468922318844222

0

@ Bikram Sir , @ Vijay Thakur  can u chk my command again?

0
When d replaces a in the code isn't it a spill?We are storing it in main memory and reusing it later,aren't we?
0

prayas  

When d replaces a in the code isn't it a spill?

No, it is not spill. 

Spilling means store in memory from register for future use.

Here we does not store d in memory before , just after the instruction 

d = c * a; // d replaces a in register and d is in use in very next instruction while staying in register

so it is not spilling after this instruction no instruction use d again so no need to store in memory.

+2

@Bikram Sir, in register filling do we remove the variable from memory and put it into register or we simply move the variable to register and not remove from memory ? Can you give any reference regarding this ?

+3

Filling is the reverse operation of spilling , where we are moving a variable from memory to a register is called filling.

read spilling paragraph https://en.wikipedia.org/wiki/Register_allocation

what i think is register is a kind of storage inside CPU so we not remove from memory itself.. though any such reference i did not found.

The answer of your doubt is : we simply move the variable to register and not remove from memory .

0

@Arjun Suresh Sir,

What is the need of putting following two statements in if() block.

d = c * a; //spilled c taken from memory and replaces x in register. 
e = c + a; 

It is mentioned that all the variables are dead after the given code segment. Variables d and e are used only in else part. So what is the need to calculate d and e in if block. Please clarify

0

@Arjun Suresh,

Sir I have read your comment on why you have put the following statements in both if() and else block.

d = c * a; //spilled c taken from memory and replaces x in register. 
e = c + a;

I have a doubt on your explanation. Code optimization such as Code motion is done to reduce size of code so that it takes less time to execute. But your code has more LOC than original code. What is the use of such movement of code if it is increasing lines of code.

It is mentioned that all the variables are dead after the given code segment. So why will we print the values of dead variables at the end of the code.

Please clarify my doubts.

0

@Arjun Sir,

Consider the following statement in your code:

if (x > a) { //x and a in memory

Why we have stored x and a in memory?? The question says that processor allows only register operands in its instuctions

0
thats poorly explained.
+11 votes
                r1=a   r2=b
c = a + b;      r1=a   r2=c
x = c * c;         a      x     c spilled memory 
if (x > a) {                                   //jump to either block 
 d = c * a;        a      d     c
 e = c + a;        a      e     c
 y = a * a;        y      e     c
}                                         
else { 
 d = c * a;        a      d     c        
 e = c + a;        e      d     c
 d = d * d;               d
 e = e * e;        e
} 

Only c needs to be in memory and spilling (register to memory) is done only once so answer would be 1

answered by (171 points)
0
ok , so u mean in place of c, we can also spill by a.

And another question, is it matching the definition of spilling as I told previous command??
+2
@srestha

i cant get you exactly what you want to ask but spilling is simply storing any any future required register value to memory so that we can use register .Reusing that memory value again is called filling .
0
very nice answer. thanx a lot. Finally its clear.
0

@Bikram sir in the above solution  in the bold statement

x = c * c;         a      x     c spilled memory 
if (x > a) {                                   //jump to either block 
d = c * a;        a      d     c

a is in R1 ,   c is in memory  ,   and when we need to do c* a , c should be in register R2 and d should be spilled in memory. is it true???

0

gari  

spilling means transfer from register to memory for future use.

here 

d = c * a;    // d replaces a in register after this instruction but d is not taken to memory as d is not replaced by any other.

see the very next instruction

d = d * d;    // now at this point  c and d both are in register

so after that there d is not used in any instruction hence no spilling for d is needed to memory.

0

@Bikram

Consider your following statetement in one of the comments above:

d = c * a;    // d replaces a in register after this instruction but d is not taken to memory as d is not replaced by any other.

Here a is replaced by d. So a should be spilled in memory since it needed later while calculating e. Why this spilling is not counted? Please clarify.

0

@Sumit

Sir, the very first line of the question says "The following code segment is executed on a processor which allows only register operands in its instructions.". So how can we do the following operation while c being in memory:

d = c * a;        a      d     c   //a in R1, d in R2 and c in memory

Should not we spill vairiable d or any other here because all the three variables are needed later? Please clarify

0
 Is the below step right?
 y = a * a;        y      e     c

  Shouldn't it be

y = a * a;                     y            a         c

0
@anchitjindal07

it can be done without spilling d

see let x and a ARE IN REGISTER r1 and r2 (SEE IF STATEMENT)

put c in place of x in R2

then perform operation c*a in ALU

put back d in place of c in R2

no need to spill d as it can be made available by storing in register .

hope now you got it
0
@Warlock lord

you can do it either way as neither a nor e is being used later

e is already there in r2 so better not replace it by a
0
@Sumit Gupta2

Yes I understood it later... Thanks for ur help :)
0
How answer is reached? Is there any standard set of rules / steps / algorithm which allow us to do code motion in order to achieve minimum memory spilling? and then the algorithm showing how to use registers to actually execute program incurring minimum register spilling?
0
why you moved two statements inside both if and else ? How its optimising ?
+3 votes

Only one memory spill is required to store x. because when else part to be executed we need to store c after replacing x in register R2 

answered by Boss (17.1k points)
+1
See

What u all are doing, that d and e under if block and else block.

but how do u know that only d and e should come under if block and else block.

 

if block doesnot contain any d or e


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

38,080 questions
45,572 answers
132,070 comments
49,047 users