The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 votes

In a simplified computer the instructions are:

$$\begin{array}{|l|l|} \hline \text {OP $R _j  , R _i$} &  \text{Perform $R _j $OP $R _i$ and store the result in register $R _j$ } \\\hline \text{OP $m,R _i$} & \text{Perform $val$ OP $R _i$ and store the result in register $R _i$ } \\ & \textbf{$val$ } \text{ denotes the content of the memory location $m$}  \\\hline \text{MOV $m,R _i$} & \text{Moves the content of memory location $m$ to register $R _i$} \\\hline \text{MOV $R _i,m$} & \text{Moves the content of register $R _i$ 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?

  1. $2$
  2. $3$
  3. $5$
  4. $6$
asked in CO & Architecture by Veteran (52k points)
edited by | 3.6k views
Analysis after DAG construction makes it easy.
According to question, $OP R_j, R_i$ should store result in $R_i$

3 Answers

+49 votes
Best answer
  • 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$

answered by Boss (19.9k points)
edited by

MOV               c, R1

ADD               d, R1

SUB                e, R1

SUB                a, R1

ADD               b, R1

MOV              R1, 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


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              R1, 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.?
Why aren't you performing MOV R1,m too?
+8 votes

3 MOV instructions.

answered by (399 points)
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.
+6 votes

Min 3 moves

answered by (427 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,093 answers
71,001 users