GATE CSE 2017 | Set 1 | Question: 52

Question

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 

• A.  only load and store instructions can have memory operands and 
• B.  arithmetic instructions can have only register or immediate operands. 

​​​​​​​The value of $X$ is _____________ .

Comments

@svas7246 

The main advantage of storing the result  as register is they are stored in CPU memory which is accessed very fast compared to RAM. This makes the program to get executed faster.

---

@svas7246

If intermediate result is stored in memory then we don’t need an additional register to store it and it minimizes the registers used.

---

Good Read

what the question want to tell by these 2 lines –

only load and store instructions can have memory operands  -> It means that during load and store instruction we can use variable name(memory operands) on RHS (Just to understand in easy language )

arithmetic instructions can have only register or immediate operands->.means whenever we perform arithmetic operation then we need to use only register(the register on  which the memory operands are stored or loaded ) as a operand OR Immediate Operands(constants) as a operand .

Answer 1

Load $R1,b$

Load $R2,c$

ADD $R1,R2$

Div $R1,3$

Load $R2,d$

Add $R1,R2$

Load $R2,a$

Sub $R2,1$

Mul $R2,R1$

hence minimum $2$ registers required

Comments

@tusharp

check this link https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm

---

what if there was another variable in place of 1. Then would we require 3 registers?

---

@sanketnagrale ...yes 3 registers would be required...assign 1 in place of leaf node having 1…But ..I think this is correct tree according to  Sethi-Ullman algo for given question ….We have to assign 1 to variables and zero if constants…

@Amit Puri You have assigned zero to c variable which is wrong i think…....correct me if wrong..

1. For every non-constant leaf node, assign a 1 (i.e. 1 register is needed to hold the variable/field/etc.). For every constant leaf node (RHS of an operation – literals, values), assign a 0

 

Answer 2

solution..

Comments

correct answer will be 2

---

when evaluated right to left

Answer 3

Answer: 2 Registers (minimum)

(adding this answer to visually see what’s happening really)

Let’s Construct an Expression tree – an easy way to visualize 

now come from bottom to top, numbered 1 to 9

(note: immediate values can be specified by CPU, hence is no need to load them into Reg and here “ $R_{i}$ ← a “ is load operation [abusive notation] )

we try to conserve as many registers as possible, we can come from anyway, left first or right first in the tree but make sure the register is free to use at that point (i.e, not holding any temporary value that we want to use in the future)

 

Answer 4

After converting this expression to three address code we get:

t1=b+c

t2=t1/3

t3=t2+d

t4=a-1

t5=t3*t4

Now after doing liveness analysis of each and every statement we get:

Live(statement1)={a,b,c,d}

Live(statement 2)={a,d,t1}

Live(statement 3)={a,d,t2}

Live(statement 4)={t3,a}

Live(statement 5)={t3,t4}

Register allocation:

r1<-b (Allocate r1 to b)

r2<-c (Allocate r2 to c)

Since outlive of first statement is {a,d,t1}, so we can allocate any of the registers r1 or r2 to t1. Let's allocate r1 to t1.

r1<-r1+r2

Outlive (statement 2)={a,d,t2} , so we either can allocate r2 to t2 or put the result back in r1 after doing the division.

r2<-r1/3

Outlive(statement 3)={t3,a} and t2 is being used in this statement, so we can first allocate r1 to d and then finally allocate r1 to t3.

r1<-r2+r1

Outlive(statement 4)={t3,t4}, so first allocate r2 to a and put the final result back in r2

r2<-r2-1

Finally we can put the final result in either r1 or r2 after doing the multiplication. So minimum no of registers needed=2