I'm reading Briggs94 Improvements to Graph Coloring Register Allocation.
I'm just wondering what kind of program will have the diamond interference graph? That is for four live ranges w, x, y, z: w interferes with x, x interferes with z, z interferes with y, and y interferes with w. And there're no more other interferences.
Since both w and z interfere with x and y, at the timeline there must be a hole between live range x and y. And both w and z will cross this hole, inducing that w interferes with z, contradiction.
(Here's the link to the paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.253&rep=rep1&type=pdf)
A loop like
loop: // live range w x y z
x:=y+z; // start end |
w:=z+x; // start | end
y:=x+w; // | end start
z:=w+y; // end | start
goto loop; // | |
generates such an interference graph.