Register Allocation Basics

Your Task

Implement basic register allocation using a linear scan algorithm.

Requirements

1. Implement liveness analysis:

   • Calculate live-in and live-out sets for each instruction
   • Identify live ranges for each variable

2. Implement linear scan allocation:

   • Sort live ranges by start point
   • Allocate registers greedily
   • Spill when no registers available

3. Generate load/store for spilled variables:

   • Allocate stack slot for spilled variables
   • Insert load before use
   • Insert store after definition

4. Handle register constraints:

   • Reserved registers (esp, ebp)
   • Caller-saved vs callee-saved
   • Special uses (eax for return value)

Success Criteria

• Allocate registers for simple programs
• Spill correctly when registers exhausted
• Generated code uses registers efficiently