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 only load and store instructions can have memory operands and arithmetic instructions can have only register or immediate operands. The value of $X$ is _____________ . Compiler Design gatecse-2017-set1 compiler-design register-allocation normal numerical-answers + – Arjun asked Feb 14, 2017 • edited Jan 14, 2019 by Sukanya Das Arjun 19.3k views answer comment Share Follow See all 14 Comments See all 14 14 Comments reply Show 11 previous comments Thadymademe commented Oct 23, 2022 reply Follow Share @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. 1 votes 1 votes Pranavpurkar commented Nov 29, 2022 reply Follow Share @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. 2 votes 2 votes Ray Tomlinson commented Jan 15 i edited by Ray Tomlinson Jan 26 reply Follow Share Good Readwhat the question want to tell by these 2 lines –only load and store instructions can have memory operands -> It means that during load and store instruction we can use variable name(memory operands) on RHS (Just to understand in easy language )arithmetic instructions can have only register or immediate operands->.means whenever we perform arithmetic operation then we need to use only register(the register on which the memory operands are stored or loaded ) as a operand OR Immediate Operands(constants) as a operand . 1 votes 1 votes Please log in or register to add a comment.
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 sriv_shubham answered Feb 14, 2017 • edited Dec 12, 2017 by kenzou sriv_shubham comment Share Follow See all 19 Comments See all 19 19 Comments reply rude commented Feb 14, 2017 reply Follow Share 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. 5 votes 5 votes sriv_shubham commented Feb 14, 2017 reply Follow Share but why...the question asks to do it efficiently in minimum number of possible register without spilling... 10 votes 10 votes Samujjal Das commented Feb 14, 2017 reply Follow Share What will be the correct answer for this? 1 votes 1 votes Aditya Sharma commented Feb 14, 2017 reply Follow Share Correct answer would be 2 6 votes 6 votes Amit puri commented Apr 29, 2017 reply Follow Share 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 22 votes 22 votes Bikram commented Apr 30, 2017 reply Follow Share @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 12 votes 12 votes Bikram commented Apr 30, 2017 reply Follow Share 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. 14 votes 14 votes akb1115 commented Jul 27, 2017 i edited by akb1115 Jul 27, 2017 reply Follow Share @Bikram Sir How to solve this question using register interference graph(RIG) approach? My approach:- Three address code:- ----------------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??? 3 votes 3 votes sushmita commented Aug 27, 2017 reply Follow Share but even without storing any result in memory, here only 2 registers are sufficient. 9 votes 9 votes Ayush Upadhyaya commented Oct 14, 2017 reply Follow Share @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. 32 votes 32 votes suchismith roy commented Dec 5, 2017 reply Follow Share the associativity of the multiplication operatoris Left to Right.Why are we not taking that here ? There must be a fixed associativyty followed right ? 1 votes 1 votes MIRIYALA JEEVAN KUMA commented Jan 1, 2018 reply Follow Share i too have same doubt 0 votes 0 votes vishalshrm539 commented Sep 25, 2018 reply Follow Share @suchismith roy Associativity of multiplication operator? There is only one * operator so no point of associativity. 2 votes 2 votes jatin khachane 1 commented Nov 15, 2018 reply Follow Share @Ayush+Upadhyaya I agree with your statement 1 votes 1 votes VIDYADHAR SHELKE 1 commented Nov 21, 2018 reply Follow Share This topic is related CAO...not code optimization 0 votes 0 votes tusharp commented Nov 23, 2018 reply Follow Share @Amit puri could you please explain the algorithm. 0 votes 0 votes Shaik Masthan commented Dec 14, 2018 reply Follow Share @tusharp check this link https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm 1 votes 1 votes sanketnagrale commented Aug 19, 2020 reply Follow Share what if there was another variable in place of 1. Then would we require 3 registers? 0 votes 0 votes rupesh17 commented Oct 20, 2020 i edited by rupesh17 Nov 23, 2020 reply Follow Share @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.. 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 3 votes 3 votes Please log in or register to add a comment.
26 votes 26 votes solution.. akash.dinkar12 answered Mar 31, 2017 akash.dinkar12 comment Share Follow See 1 comment See all 1 1 comment reply Himanshu Dixit commented Sep 29, 2017 reply Follow Share correct answer will be 2 1 votes 1 votes Please log in or register to add a comment.
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) Mahanth Yalla answered Jan 9 Mahanth Yalla comment Share Follow See all 0 reply Please log in or register to add a comment.