similar to: [LLVMdev] Greedy Register Allocation in LLVM 3.0

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

On Sep 26, 2011, at 4:22 AM, Leo Romanoff wrote: > 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

Yes, I quite liked the things I've read about the PBQP allocator. Given what the hardware folks have to go through to get 1% improvements in scalar code, spending 20% (or whatever) compile time (under control of a flag) seems like nothing. And falling back on "average code" is a little disingenuous. People looking for performance don't care about average code; they care about

> The underlying liveness datastructure is a list of ranges where each vreg is alive > (ranges in terms of instructions numbered). I remember a couple of later linear scan > papers describing the same thing (Traub et.al. being the first if I remember correctly). > That should be as accurate as you can get in terms of liveness information. It depends on the details. For example, given

The phi instruction is irrelevant; just the way I think about things. The question is if the allocator believes that t0 and t2 interfere. Perhaps the coalescing example was too simple. In the general case, we can't coalesce without a notion of interference. My worry is that looking at interference by ranges of instruction numbers leads to inaccuracies when a range is introduced by a copy.

Hi, Using Chaitin's approach, removing a copy via coalescing could expose more opportunities for coalescing. So he would iteratively rebuild the interference graph and check for more opportunities. Chaitin was also careful to make sure that the source and destination of a copy didn't interfere unnecessarily (because of the copy alone); that is, his approach to interference was very

Hi Jakob, Hi Andy, First of all, thanks a lot for very elaborative and interesting answers! > It may be more helpful to explain how LLVM's register allocator came > into existence before debating the high level algorithm. > > When I began working on LLVM last October, Jakob was developing an > infrastructure for global live range splitting. It was just becoming > clear

> On Sep 10, 2018, at 5:25 PM, Matthias Braun <mbraun at apple.com> wrote: > > > >> On Sep 10, 2018, at 5:11 PM, Preston Briggs <preston.briggs at gmail.com <mailto:preston.briggs at gmail.com>> wrote: >> >> The phi instruction is irrelevant; just the way I think about things. >> The question is if the allocator believes that t0 and t2

How precise is the interference checking (to my mind, a great weakness of linear scan)? Is there way to do coalescing (the great strength of coloring)? I ask these questions because we (guys I work with) see loops where there's a little register juggling that seems unnecessary. Is there a paper that describes what y'all do? Thanks, Preston On Mon, Sep 10, 2018 at 9:57 AM, Matthias

Hi Matthias, Thanks for your hint! It is just for learning and practicing for me, just like migrate DragonEgg http://lists.llvm.org/pipermail/llvm-dev/2017-September/117201.html the motivating is for learning from GCC and LLVM developers. 在 2017年12月19日 10:07, Matthias Braun 写道: > > >> On Dec 18, 2017, at 9:52 AM, Leslie Zhai via llvm-dev >> <llvm-dev at lists.llvm.org

Hi, I'm implementing some variations of graph-coloring register allocators for LLVM. Many of them perform their phases (e.g. coalescing, graph simplification, spilling, color selection) in an iterative way. Since LLVM provides an implementation of the coalescing in the SimpleRegisterCoalescing class already, I would like to reuse it (even though I could of course create my own coalescing

On Friday 09 January 2009 03:36, Roman Levenstein wrote: > Hi, > > I'm implementing some variations of graph-coloring register allocators for > LLVM. Many of them perform their phases (e.g. coalescing, graph > simplification, spilling, color selection) in an iterative way. Since > LLVM provides an implementation of the coalescing in the > SimpleRegisterCoalescing class

Hi Leslie, I suggest adding these 3 papers to your reading list. Register allocation for programs in SSA-form Sebastian Hack, Daniel Grund, and Gerhard Goos http://www.rw.cdl.uni-saarland.de/~grund/papers/cc06-ra_ssa.pdf Simple and Efficient Construction of Static Single Assignment Form Matthias Braun , Sebastian Buchwald , Sebastian Hack , Roland Leißa , Christoph Mallon , and Andreas

Hi Jakob, After reading your blog article, I have some questions. :-) In [1], it says: "It was an important design goal to make the algorithm as flexible as possible, and to avoid introducing arbitrary constraints. It is possible to change machine code and live ranges at any time. Simply evict the relevant live ranges, make the change, and put them back on the queue." Q1. The

On Sep 26, 2011, at 2:41 AM, 陳韋任 wrote: >> The greedy allocator is global, but so was the old linear scan allocator. > > In http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html > , it says "The algorithm is local, and it cannot clean up messes that > extend beyond a single basic block". Does it mean the rewriter algorithm > not the linear scan?

On Sep 27, 2011, at 12:11 AM, Leo Romanoff wrote: > Quite some of these register allocation proposals are also able to handle overlapping register classes. That's interesting. Do you have any references? /jakob -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110927/e4b1f13d/attachment.html>

On May 3, 2011, at 12:03 PM, David A. Greene wrote: >> >> I am working my way through the regressions, looking for things the >> allocator did wrong. Any help is appreciated, please file bugs if you >> find examples of stupid register allocation. > > Certainly. I would ask that we keep linearscan around, if possible, as > long as there are significant

On May 3, 2011, at 9:19 AM, David A. Greene wrote: > Jakob Stoklund Olesen <stoklund at 2pi.dk> writes: > >> +10.0% SingleSource/Benchmarks/CoyoteBench/huffbench >> +12.0% SingleSource/Benchmarks/McGill/chomp >> +18.0% SingleSource/Benchmarks/BenchmarkGame/n-body >> +45.5% SingleSource/Benchmarks/BenchmarkGame/puzzle >> +10.0%

Il 26/09/2011 16:49, Jakob Stoklund Olesen ha scritto: > On Sep 26, 2011, at 2:41 AM, 陳韋任 wrote: > >>> The greedy allocator is global, but so was the old linear scan allocator. >> In http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html >> , it says "The algorithm is local, and it cannot clean up messes that >> extend beyond a single basic

On Sep 27, 2011, at 12:11 AM, Leo Romanoff wrote: > > > It is true that names are not always reflecting the essense. But on the other hand, there is a lot of ongoing research on register allocation (and compilers in general) and it looks like more and more such efforts choose LLVM as a platform for experimentation. Quite some results and comparisons are published. So, it would be nice