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 Bikram commented Apr 1, 2017 reply Follow Share same type of question https://gateoverflow.in/2138/gate2011_36 14 votes 14 votes Venkat Sai commented Dec 19, 2017 reply Follow Share 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 5 votes 5 votes Chhotu commented Jan 2, 2018 reply Follow Share Register Spilling http://www.webster-dictionary.org/definition/register%20spilling 4 votes 4 votes jatin khachane 1 commented Nov 15, 2018 reply Follow Share 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 votes 0 votes Iamgveeresh commented Nov 19, 2018 reply Follow Share What does mean without any register spill? 0 votes 0 votes Nitesh Singh 2 commented Dec 11, 2018 reply Follow Share Bracket mismatch here. 0 votes 0 votes Anshul999 commented Oct 30, 2019 reply Follow Share 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. 9 votes 9 votes Setika Mehra commented Oct 30, 2020 reply Follow Share The labelling or Sethi Ullman algorithm works here perfectly, check out this https://www.cse.iitb.ac.in/~uday/courses/cs324-08/code-generation.pdf 3 votes 3 votes himanshu2021 commented Jan 2, 2021 reply Follow Share @Setika Mehra No, we can’t apply Sethi-Ullman algorithm bcz, acc to the algorithm: But in given question, its explicitly mention that both operands must be in register or an immediate operands. “arithmetic instructions can have only register or immediate operands”. 4 votes 4 votes ankit3009 commented Nov 12, 2021 reply Follow Share This comment of @Ayush Sir answers this question : https://gateoverflow.in/118746/Gate-cse-2017-set-1-question-52?show=159976#c159976 0 votes 0 votes svas7246 commented Dec 11, 2021 reply Follow Share what difference does it make whether result stored in memory or not stored in memory 0 votes 0 votes 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 Show 16 previous comments 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.