edited by
19,136 views
56 votes
56 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 _____________ .

edited by

3 Answers

Best answer
89 votes
89 votes
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
2 votes
2 votes

Answer: 2 Registers (minimum)


(adding this answer to visually see what’s happening really)

Let’s Construct an Expression tree – an easy way to visualize 

now come from bottom to top, numbered 1 to 9


(note: immediate values can be specified by CPU, hence is no need to load them into Reg and here “ $R_{i}$ ← a “ is load operation [abusive notation] )

we try to conserve as many registers as possible, we can come from anyway, left first or right first in the tree but make sure the register is free to use at that point (i.e, not holding any temporary value that we want to use in the future)

 

Answer

Answer:

Related questions