in Compiler Design edited by
14,764 views
54 votes
54 votes

Consider the expression $(a-1) * (((b+c)/3)+d)$. Let $X$ be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which 

  1.  only load and store instructions can have memory operands and 
  2.  arithmetic instructions can have only register or immediate operands. 

​​​​​​​The value of $X$ is _____________ .

in Compiler Design edited by
by
14.8k views

4 Comments

what difference does it make whether result stored in memory or not stored in memory
0
0

@svas7246 

The main advantage of storing the result  as register is they are stored in CPU memory which is accessed very fast compared to RAM. This makes the program to get executed faster.

0
0

@svas7246

If intermediate result is stored in memory then we don’t need an additional register to store it and it minimizes the registers used.

0
0

2 Answers

82 votes
82 votes
Best answer
Load $R1,b$

Load $R2,c$

ADD $R1,R2$

Div $R1,3$

Load $R2,d$

Add $R1,R2$

Load $R2,a$

Sub $R2,1$

Mul $R2,R1$

hence minimum $2$ registers required
edited by

4 Comments

0
0
what if there was another variable in place of 1. Then would we require 3 registers?
0
0
edited by

@sanketnagrale ...yes 3 registers would be required...assign 1 in place of leaf node having 1…But ..I think this is correct tree according to  Sethi-Ullman algo for given question ….We have to assign 1 to variables and zero if constants…

@Amit Puri You have assigned zero to c variable which is wrong i think…....correct me if wrong..

  1. For every non-constant leaf node, assign a 1 (i.e. 1 register is needed to hold the variable/field/etc.). For every constant leaf node (RHS of an operation – literals, values), assign a 0

 

2
2
24 votes
24 votes

solution..

1 comment

correct answer will be 2
1
1
Answer:

Related questions