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

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?

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

3 Answers

+43 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 no. of MOV Instruction $= 3$
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?
+7 votes

3 MOV instructions.

answered by (383 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.
+5 votes

Min 3 moves

answered by (321 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

44,149 questions
49,639 answers
65,807 users