GATE2007-54

Question

In a simplified computer the instructions are:

OP $R_j$, $R_i$	-Performs $R_j$ OP $R_i$ and stores the result in register $R_j$.
OP $m,R_i$	-Performs $val$ OP $R_i$ and stores the result in register $R_i$. $val$ denotes the content of the 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_1\: = \: a+b$

$t_2\: = \: c+d$

$t_3\: = \: e-t_2$

$t_4\: = \: t_1 – t_3$

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

Comments

Analysis after DAG construction makes it easy.

---

According to question, $OP R_j, R_i$ should store result in $R_i$

Answer 1

 MOV              a, R₁

 ADD               b, R₁

 MOV               c, R₂

 ADD               d, R₂

 SUB                e, R₂

 SUB                R₁, R₂

 MOV               R₂, m

 Total no. of MOV Instruction = 3

Comments

MOV               c, R1

ADD               d, R1

SUB                e, R1

SUB                a, R1

ADD               b, R1

MOV              R_1, m

What's wrong with this one?

---

you change the sequence

---

this is also worked... What is the right answer

---

Why is simplification not allowed here?The answer should be 2 otherwise.

---

Last move should be ::

Mov R1,m

---

@sidharth

MOV               c, R1       ; R1=c

ADD               d, R1        ; R1= d+c

SUB                e, R1        ; R1=e-(c+d)

SUB                a, R1        ; R1=a-(e-(c+d))

ADD               b, R1         ;R1=b+a-(e-(c+d))

MOV              R_1, m

I think this is right, answer should be  2 then !

---

I think ,basic block should be executed in sequence

---

@VS  and @ Sidharth Singla 

I think this is right, answer should be  2.

is @rahul sharma 5's answer not OK ? (means answer is not 2 because basic block should be executed in sequence)

---

By the definition of a basic block "whenever the first instruction in a basic block is executed, the rest of the instructions are necessarily executed exactly once, in order." [Source: Wikipedia]

---

Why only a c are moved in register what about b d and e.?

Answer 2

3 MOV instructions.

Comments

In second last instruction, the result will be stored in Ri not in Rj, as in question mentioned OP Rj Ri result will be stored in Rj as it on the right side and in your answer, Ri is on the right side. so the last instruction should be MOV Ri,t4.

Answer 3

Min 3 moves