GATE CS 2017 Set 1 — Question 52
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0MediumRegister AllocationCode OptimizationCompiler Design
Compiler Design → Code Optimization → Register Allocation
Last updated
Question
Consider the expression . 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 (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is ________.
Correct answer
2 to 2
Solution
To evaluate the expression , we can represent it as an expression tree and determine the register requirements using the Sethi-Ullman algorithm logic.Expression Tree Structure:
1.Root:
*2.Left Subtree:
a - 1- Load
ainto a register (). - Subtract
1(immediate). Result in . - Registers needed: 1.
((b+c)/3) + d- Inner operation
b + c: - Load
b(). - Load
c(). - Add . Result in .
- Registers needed: 2.
- Division
/ 3: - Divide by
3(immediate). Result in . - Registers needed: 1 (reuse).
- Addition
+ d: - Load
d(). - Add . Result in .
- Registers needed: 2 (one for partial result, one for
d). - Total for Right Subtree: 2 registers.
- The algorithm evaluates the subtree with the higher register requirement first to minimize total registers.
- Right Subtree needs 2 registers.
- Left Subtree needs 1 register.
1.Evaluate Right Subtree (needs 2 regs). Result stored in .
2.Evaluate Left Subtree (needs 1 reg). Use (since is occupied). Total concurrent registers: 2.
3.Multiply and .
The maximum number of registers required at any point is 2.Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Code Optimization
2026 Set 2 Q17In C runtime environment, which one of the following is stored in heap?2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q27Consider the following C statements: Which of the following options is/are correct? [figure]2026 Set 1 Q28Which of the following statements is/are true?2026 Set 2 Q35A lexical analyzer uses the following token definitions - - …