Project ForgeA program uses six temporary variables a,b,c,d,e,f: `a=1; b=10; c=20; d=a+b; e=c+d; f=c+e; b=c+e; e=b+f; d=5+e; return d+f;`. Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
Explanation
Tracking live ranges: right after c is computed (before d is computed), a (used at the d=a+b step), b (also used there), and c (used at the e=c+d step and beyond) are ALL simultaneously live — 3 variables at once. At every other point in the program, at most 2 variables are simultaneously live. So the peak register pressure, and hence the minimum registers needed, is 3.
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.