llvm dev - Sep 2013 - [LLVMdev] Doubts about register interferences in register allocators

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 in advance!

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

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

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>