Build a Interference Graph

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:


Where L1 and L2 are two different Live Intervals. Or should I use:


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.

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

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.

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

Ok. Thank you for your help.