[LLVMdev] Doubts about register interferences in register allocators

[Andrew Trick]

On Sep 17, 2013, at 5:15 AM, Leandro Santiago <leandrosansilva at gmail.com> wrote:

> Hello to all. I'm trying to implement a simple register allocator using graph colouring (I know, everyone has already done that :-)) and I'm also using LLVM 3.4 from master branch.
> 
> The algorithm I'm using is based on the one described on the "Modern Compiler Implementation in C". My implementation is totally experimental and doesn't aim to be fast, eficient or even faster than the current allocators (so please don't say "you'd better use a better algorithm" :-)).
> 
> I've been reading the code of current allocators as well some documentation about them in blogs, etc., but I still have some doubts.
> 
> I need to create a graph with the interference between LiveIntervals, where each node is a LiveInterval and an edge between two of them means they interfere. 
> 
> By "X interferes Y" I mean: "LiveInterval X and Y must me mapped to some register of a class Z AND there's an interception between the ranges of X and ranges of Y", that's something like "X overlaps Y, which are the same type". 
> 
> This deffinition differs from the definition I've found reading the source code. In the class LiveRegMatrix, which is queried to check interferences you ask something "does virtual register X interfere in physical register Y?". But I realized the answer is yes only if register Y has been already assigned to another virtual register.
> 
> I confess I couldn't understand why it was implemented in that way. That means I must first assign the virtual do physical in order to be able to apply my allocation heuristic (please correct me if I'm wrong (what's very likely to be true)).
> 
> Do you have any ideas about how to implement the initial idea, of checking interferences between virtual regs regardless have already assigned them to physical registers?
> 
> Thanks 

Hi Leandro,

LiveRegMatrix is a data structure that allows “incremental" register allocation by summarizing the liveness of physical register units. LLVM regalloc is fast because it uses this data structure instead of computing an interference graph.

Checking interference between to virtual registers should be as simply as calling LiveInterval::overlaps(LI). You may want to refer to the LLVM RegisterCoalescer which has more in common with text-book register allocators.

-Andy