The Gateway to Computer Science Excellence

+3 votes

The following program uses six temporary variables *p, q, r, s, t* and *u*. The code is :

Assuming that all operations take their operands from registers. The minimum number of registers needed to execute this program without spilling are __________.

The answer given is 5, but I think all lines except the first three lines and the last line are dead code. So the answer should be 2. Please correct me if wrong.

0

But why should we allocate registers for dead code? In that question, options were provided that's why the legitimate answer should be 5.

0

@Saikat Dutta I think since it isn't mentioned that we could use any of the optimizations thats why we will have to go through the complete code and store all the variables although they may be a part of a Dead Code. It it would have been mentioned that we can use any Optimisation then your answer would have been correct.

+1 vote

Not sure how the given variables are temporary. Also since return statement is given we can assume all other code is dead that doesn't determine the return value.

So, the compiler will do just this:

return 48;

As it will be doing constant propagation and dead code elimination. So no. of registers required will be 0.

If constant propagation is not done, then we need to count the number of live variables at each statement. And then take the maximum value of it. At line 2, p and q are live and after line 3, q becomes dead and t becomes live. So, maximum number of live variables at any point is 2.

So, the compiler will do just this:

return 48;

As it will be doing constant propagation and dead code elimination. So no. of registers required will be 0.

If constant propagation is not done, then we need to count the number of live variables at each statement. And then take the maximum value of it. At line 2, p and q are live and after line 3, q becomes dead and t becomes live. So, maximum number of live variables at any point is 2.

0 votes

The operation of moving a variable from a register to memory is called *spilling*

So we will have to allocate only registers we can't store the result in memory

p=6 => lets save value of p in register R1

q=7 => since we need value of p in future instructions we cant save it in R1, so let us use R2 for q

t=p*q => now both p and q are used in future instructions, so we will have to store t in R3

s=t*p => p, q and t, all 3 are being used in future instructions so we will have to store s in R4

u=8 => p, q, t and s all 4 are being used in future instructions so we will have to store u in R5

u=s*p => no need of extra register. The operation is being performed on u that is R5

s=p+u => since we are updating value of s, again we dont need extra register this will be done in R4

r=r*q => now only t and p are being used in future instruction so we can store r in any of R2,R4 or R5. So no need of extra register

t=t+p => since we are updating value of t, again we dont need extra register this will be done in R3

Hence we need only 5 registers R1, R2, R3, R4 and R5

Hence answer should be 5

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,430 answers

195,209 comments

99,923 users