[LLVMdev] Doubts about register interferences in register allocators

[Leandro Santiago]

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>