[llvm-dev] Build a Interference Graph

[Matthias Braun via llvm-dev]

See MCRegisterInfo.h has a description on what register units are, they are an abstraction over physical registers to speedup complicate subregister structures.

> On Nov 18, 2015, at 4:41 PM, Natanael Ramos <naelr8 at gmail.com> wrote:
> 
> Ok, just to clarify, RegUnits, as far I understand, are Physical registers or alias to Physical registers. They exist because some instructions  use physical registers directly rather than virtual register. It's right?
> 
> And why this RegUnits should be present in the Interference Graph? I thought were only the Live Intervals would be the nodes of the graph.
> 
> Sorry about the trouble to understand my question, my English doesn't help that much, I'm from Brazil.
> 
> Em 18/11/2015 10:19 PM, "Matthias Braun" <mbraun at apple.com> escreveu:
> 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
>