Leandro Santiago
2013-Sep-17 12:15 UTC
[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: <lists.llvm.org/pipermail/llvm-dev/attachments/20130917/b37f4511/attachment.html>
Andrew Trick
2013-Sep-17 15:56 UTC
[LLVMdev] Doubts about register interferences in register allocators
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? > > ThanksHi 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
Leandro Santiago
2013-Sep-17 17:50 UTC
[LLVMdev] Doubts about register interferences in register allocators
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: <lists.llvm.org/pipermail/llvm-dev/attachments/20130917/0232f939/attachment.html>