What is register allocation? Explain register allocation using graph coloring algorithm. Given the following live ranges, perform register allocation with 3 registers available:

Variables: a, b, c, d, e

 

Live ranges overlap:

– a and b overlap

– b and c overlap  

– c and d overlap

– d and e overlap

– a and c don’t overlap

– b and e overlap

 

Draw the interference graph and assign registers.