[LLVMdev] Doubts about register interferences in register allocators

[Leandro Santiago]

Hi Andrew.

I really hadn't realized the existence of overlap methods in LiveInterval.
I've just implemented it by myself (and my implementation probably is wrong
:-()... I'll pay more attention next time :-)

I really apreciate your help. Thx a lot!


On 17 September 2013 12:56, Andrew Trick <atrick at apple.com> wrote:

>
> 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




-- 
Sent from my mind
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130917/0232f939/attachment.html>