[llvm-dev] Build a Interference Graph

[Matthias Braun via llvm-dev]

I'm not sure I completely understand what you want here. But I think this is how you would build a traditional register allocation interference graph:

Register Units are the things the allocator assigns, I would think it would look something like:
- Add a node for each register unit and pre-color it!
- Add a node for each vreg.
- Then pair up: Each vreg against other vregs with overlapping register classes, each vreg against each register unit contained in the vregs register class.
    If there is a liverange overlaps add an edge.

- Matthias

> On Nov 18, 2015, at 4:09 PM, Natanael Ramos via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> Good Night.
> 
> I'm implementing a Interference Graph in the Register Allocation pass. I'm building this graph BEFORE any assignment of a virtual register to physical register.  But I have a doubt about how to check the interference between two Live Intervals (i.e. They live at same point), should I use:
> 
> L1->overlaps(L2)
> 
> Where L1 and L2 are two different Live Intervals. Or should I use:
> 
> L1->overlaps(RG1)
> 
> Where L1 is a Live Interval and RG1 is a RegUnit for an arbitrary physical register.
> 
> I saw this second method in the PBQP allocator code, I think that maybe will be related to avoid allocation to reserved physical registers or for a on-the-fly check for interference, but the LiveRegMatrix already do that.
> 
> So my question is: Considering that I will build this interference graph before any assignment (with information only about the Liveness Analisys) and I freeze all reserved physical registers before perform register allocation, should I use the first or the second method? If the second is the right one, why is that?
> 
> I'm using LLVM version 3.6.2.
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev