7.8k views

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 | 7.8k views
+10
+3
here i think the order of evaluation of the expression is done in such a way that the code generated is small and the number of registers is less hence evaluating (a-1) first will give the answer 3 and evaluating last gives the answer 2 but the answer is 2 as it is least with minimum number of registers
+2
0

https://gateoverflow.in/2138/gate2011-36

The instructions produce result only in a register. If no intermediate results can be stored in memory,

(without any register spill)

Does this statements means the same ??

0
What does mean without any register spill?
0
Bracket mismatch here.
0

Register Spilling:

In most register allocators, each variable is assigned to either a CPU
register or to main memory. The advantage of using a register is
speed. Computers have a limited number of registers, so not all
variables can be assigned to registers. A “spilled variable” is a
variable in main memory rather than in a CPU register. The operation
of moving a variable from a register to memory is called spilling,
while the reverse operation of moving a variable from memory to a
register is called filling. For example, a 32-bit variable spilled to
memory gets 32 bits of stack space allocated and all references to the
variable are then to that memory. Such a variable has a much slower
processing speed than a variable in a register. When deciding which
variables to spill, multiple factors are considered: execution time,
code space, data space.

So to solve the given question without the register spilling means we have to use registers only and not move the register content to memory.

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
by Active (3.4k points)
edited by
+4

The correct answer would be 3. Because you have to calculate (a-1) first, which you have to keep upto the last. Hence 3 Register.

+7
but why...the question asks to do it efficiently in minimum number of possible register without spilling...
+1
What will be the correct answer for this?
+5
Correct answer would be 2
+16

by labelling algorithm we can get minimum 2 registers for the above question.

https://gateoverflow.in/2138/gate2011_36

my doubt is why we have not applied labelling algo in the gate 2011 question..please help

@Bikram Ballav Sir

@Arjun Sir

+10

@amit

Yes, The Labelling algorithm we can directly apply here .

It is actually Known as Sethi-Ullman Algorithm

https://en.wikipedia.org/wiki/Sethi–Ullman_algorithm

+10
and @amit

" If no intermediate results can be stored in memory, " this line is not given in this question , like it was given in 2011 question.

Hence here, in this question , we can store intermediate results into memory, no extra register require for that.

That's the only reason we can get minimum number of registers are 2 in this question but  minimum number of registers are  3 in 2011 question. Just because of this line .

Hope things get clear now.
+2

@Bikram  Sir

How to solve this question using register interference graph(RIG) approach?

My approach:-

----------------Live{a,b,c,d}

t1=a-1

-----------------Live{b,c,t1,d}

t2=b+c

------------------Live{t1,t2,d}

t3=t2+3

------------------Live{t3,t1,d}

t4=t3+d

------------------Live{t1,t4}

t5=t1*t4

When I try to color the RIG for this I need more than 2 colors

What is the problem with this approach???

+8
but even without storing any result in memory, here only 2 registers are sufficient.
+19

@Bikram Sir,

"" If no intermediate results can be stored in memory, " this line is not given in this question , like it was given in 2011 question."

I think the above line in this question also is implied by the words "no spilling" ??

Here also in this question we cannot store intermediate results into memory.

The difference in answer of values as here(2) and that compared to 2011 question is because here we have some constant values in the expression of this question and the question clearly mentions that

"arithmetic instructions can have only register or immediate operands"

That means we can save on one register while performing ALU computations with constants.

+1
the associativity of the multiplication operatoris Left to Right.Why are we not taking that here ? There must be a fixed associativyty followed right ?
0
i too have same doubt
+1

Associativity of multiplication operator?

There is only one * operator so no point of associativity.

0

I agree with your statement

0
This topic is related CAO...not code optimization
0

@Amit puri could you please explain the algorithm.

0

solution..

by Boss (41.9k points)
+1
correct answer will be 2