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

don't just ignore the last line "The final value of the computation should be in memory", i also made a mistake there.

---

@Mayank_Pant i think you mistakenly wrote 2 instead of 3?

---

my mistake buddy, any other correction?

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

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.

Answer 4

Min 3 moves

Comments

Note that according to your last instruction  OP m(t1) Ri(t3), the result of the calculation is still in register Ri , whereas the question states that the final calculation should be in memory, So a additional MOV Ri t4  is needed.

This increases the count to 4, which can be avoided using another register, as we have 2 registers available.

Answer 5

let us consider 2 registers r1 and r2

MOV c,R1

OP d,R1

OP e,R1

MOV a,R2

OP b,R2

OP R1,R2

MOV R1,m

 

so answer is 3 

NOTE:  though 2 can also come in the answer a+b have to be performed separately(basic block)

Answer 6

$R_{j}\Leftarrow R_{j}\ OP\ R_{i}$

$R_{i}\Leftarrow val\ OP\ R_{i}$

$R_{i}\Leftarrow m$

$m\Leftarrow R_{i}$

---

 

$R_{1}\Leftarrow a(mov)$

$R_{1}\Leftarrow b+R_{1}$

$R_{2}\Leftarrow c(mov)$

$R_{2}\Leftarrow d+R_{2}$

$R_{2}\Leftarrow e-R_{2}$

$R_{1}\Leftarrow R_{1}-R_{2}$

$m\Leftarrow R_{1}(mov)$

Answer : B