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

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 2

$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

Answer 3

Last value can be located in any register?