[LLVMdev] Implement a Register Allocator in LLVM

[Natanael Ramos]

One of the great difficulties he was seeing was to work with the
interference graph, as needed to implement it, I will study carefully the
LiveRegMatrix class.

Also will study the code PBQP allocator, since it is also based on graph
coloring heuristics.

Thank you for guidance and help.

2015-05-20 19:43 GMT-03:00 Quentin Colombet <qcolombet at apple.com>:

>
> On May 20, 2015, at 3:12 PM, Matthias Braun <mbraun at apple.com> wrote:
>
> If you want to stay within the bounds of the existing register allocation
> architecture in llvm you should subclass from RegAllocBase and work from
> there. It basically has a LiveInterval structure (what you would find a
> linear scan allocator that allows holes in the liverange) for each virtual
> register, they are all put into a worklist and you pop them one by one and
> color, split and spill them. RegAllocBasic is about the simplest
> implementation of that you should read that code for understanding the
> concepts.
> As for graph coloring, there is no code that builds interference graphs in
> llvm (interferences are checked on demand with the LiveRegMatrix instead).
> I'm not aware of any documentation outside the code (and maybe a few
> mailing list posts).
>
>
> We have the PBQP register allocator in LLVM that does graph coloring.
>
> Q.
>
>
> - Matthias
>
> On May 20, 2015, at 2:18 PM, Natanael Ramos <naelr8 at gmail.com> wrote:
>
> I'm working on my project for completion undergraduate courses, consisting
> of an experimental analysis of registers allocation algorithms. For this
> task, I am using the set of tools from the LLVM project.
>
> However, I have read the documentation of the LLVM project and not yet
> found a way to put the pieces of the puzzle together. So far I know:
>
>
>    - As passes work as engage them to LLVM and know I must implement
>    MachineFunctionPass pass.
>
>
>
>    - I follow some suggestions to look at the Basic Allocator code, but
>    could not understand much.
>
>
> The allocator I intend to implement is based on graph coloring heuristics,
> as the theory of operation of such methods I’m well aware.
>
> So I look for is some sort of "How to", a defined set of steps to
> implement such allocator. It sounds like carelessness, but I have to
> deliver the work in about six months and I'm a little confused.
>
> If anyone can give me some guidance or reference to any supporting
> material (besides the own documentation), I would be grateful.
>
> My English may be a little wrong, I am a Brazilian student.
>
>
> --
> Natanael Ramos
> Membro do corpo discente de Ciência da Computação pelo Instituto Federal
> de
> Minas Gerais - Campus Formiga
>
>  _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>


-- 
Natanael Ramos
Membro do corpo discente de Ciência da Computação pelo Instituto Federal de
Minas Gerais - Campus Formiga
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150521/de2bc577/attachment.html>