[LLVMdev] Greedy Register Allocation in LLVM 3.0

[Leo Romanoff]

Hi Jakob,

Thanks for a very interesting description of the new register allocation algorithm in LLVM!!!

Could you elaborate a bit on the following topics:

1) Do you have any plans to publish something more formal and detailed about this algorithm, e.g. a paper or something similar?  It would be nice to better understand how this algorithm relates to well-known algorithms described in the literature, e.g. linear scan, graph coloring, iterated register coalescing by Chaitin-Briggs, register allocation by priority-based coloring by Chow and Hennesey and if it represents an extension of one of those algorithms or if it is a totally new algorithm. And of course it would be nice if the terminology used by this description would follow the one published in the literature, as sometimes use of a different terminology can be misleading. For example, it is rather well known that the Linear Scan register allocation of LLVM was not a real linear scan register allocator, as it allowed for backtracking and re-coloring. It was de-facto more of a special case of graph-coloring register allocator. But due to its name, many
 published research papers assumed that it is a real linear scan implementation and took it as a representative example for such allocators.

2) A comparison of the quality of generated allocations  and allocator performance with well-known register allocation algorithms would be very interesting to better understand pros and cons of this new algorithm. Do you have any numbers at hand? If not, do you plan to produce a more thorough analysis?

3) It is stated in the blog that this allocator is much simpler than the old linear scan implementation of LLVM. Can you provide a bit more information?
   For example:
    - How many lines of code it is and how it compares in this regard to the old linear scan?
    - Are there any wired places like the former SimpleRegisterCoalescer, which was not that simple at all and had an extremely wired logic ;-)
    - You explained that it produces  in most situations a better code than linear scan, which is cool! But it would be also interesting to know in which pathological cases it still looses against linear scan and why
    - Can you provide a rough estimate of the algorithmic complexity of the new algorithm? Is it O(n), O(n^2) or something else?

Thanks,
  Roman


----- Ursprüngliche Message -----
> Von: Jakob Stoklund Olesen <jolesen at apple.com>
> An: "llvmdev at cs.uiuc.edu List" <llvmdev at cs.uiuc.edu>
> Cc:
> Gesendet: 17:44 Montag, 19.September 2011
> Betreff: [LLVMdev] Greedy Register Allocation in LLVM 3.0
>
> I just uploaded a blog post outlining the new register allocation algorithm in
> LLVM 3.0.
>
>   http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
>
> Please direct comments here.
>
> /jakob
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu        http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>