Question

How to draw register allocation interference graph ?

Can anyone explain this along with " What is a live variable "?

Explain with the example given below ?

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 

Comments

Maybe or maynot !! I have seen some questions related to this in gate .

---

@Kapil ,
This is the only resource i saw in the internet https://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

But is bit confusing . I didn't understand many things .I think Register Allocation is removed in 2016 syllabus so I didn't spent much time as I have to finish core subjects. But will give a try when i complete the portions.

IF you understoond pls post the anser . 

---

I am getting $3$ ..

Answer 1

A live range is defined as a write to a register followed by all the uses of that register until the next write. A variable Live during it Live range.An edge between two nodes indicates that those two live ranges interfere with each other because their lifetimes overlap. In other words, they are both simultaneously active at some point in time, so they must be assigned to different registers.

Instruction	Live variables
a=1	{a}
b=10	{a,b}
c=20	{a,b,c}
d=a+b	{c,d}
e=c+d	{c,e}
f=c+e	{c,e,f}
b=c+e	{b,f}
e=b+f	{e}
d=5+e

Now we will draw the graph by keeping all variables as vertices and an edge between vertices if they are live simultaneously at some point in the program.

total $3$ colors required to color this graph.

Comments

I think , here one edge between 'e' and 'f' should also be present because at some point of time both e and f variables were active simultaneously... Please correct me if I am wrong..

---

yes, thanks for correcting..but still answer remains same..total $3$ registers

---

@reena_kandari

Why can’t we directly infer from the table that since at max only 3 variables are live, therefore we need almost 3 registers. Why do we need this graph?

Is there any case where the table fails?