GATE CSE 2007 | Question: 54

Question

In a simplified computer the instructions are:

$$\begin{array}{|l|l|} \hline \text {OP }R _j , R _i & \text{Perform }R _j \text{ OP } R _i \text{ and store the result in register }R _j \\\hline
\text{OP }m,R _i & \text{Perform } val\text{ OP }R _i \text{ and store the result in register }R _i  \\
& val \text{ denotes the content of the memory location }m \\\hline
\text{MOV }m,R _i & \text{Moves the content of memory location }m \text{ to register }R _i \\\hline
\text{MOV }R _i,m & \text{Moves the content of register }R _i\text{ to memory location }m\\\hline \end{array}$$

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

yes

 

---

@ijnuhb, at the end store result into moemory also. So total 3 MOV.

---

3 Move Required (Solve using DAG)

Last move for storing result to memory.

Answer 1

• MOV $a, R_1$
• ADD $b, R_1$
• MOV $c, R_2$
• ADD $d, R_2$
• SUB $e, R_2$
• SUB $R_1, R_2$
• MOV $R_2, m$

 Total number of MOV instructions $= 3$

Correct Answer: $B$

Comments

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

---

Why aren't you performing MOV R1,m too?

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

Answer 4

Let the two registers be $R_{1}$ and $R_{2}$

1. Move a into $R_{1}$, then add b into it. Equivalently, we can move b into $R_{1}$ then add a into it. (1 Move)
2. Move c into $R_{2}$, then add d into it. Equivalently, we can move d into $R_{2}$ then add c into it. (1 Move)
3. Subtract e from $R_{2}$
4. Subtract $R_{2}$ from $R_{1}$

Total 2 moves.

Now, the question says that the final value must be in the memory. So, Move the contents of $R_{2}$ into the memory. (1 Move)

 

So, 3 moves. Option B.