similar to: [LLVMdev] Is it possible to use the SimpleRegisterCoalescing pass in an iterative way?

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

On Tuesday 17 July 2007 14:21, David Greene wrote: > > I don't care for a MachineFunctionPass that can be directly called. I > > think it's a very good idea to keep the coalescers independent from > > the allocators. If that's desired, we should enhance passmanager so > > each allocator can run some sub-passes as part of the allocation > > pass. > >

On Jul 11, 2007, at 11:39 AM, David Greene wrote: > On Wednesday 11 July 2007 12:41, Tanya M. Lattner wrote: > >> I think the coalescer should be flexible enough to be run >> independent of >> the register allocator. For example, you may want to expose the >> copies >> induced by transforming out of SSA to the scheduler. If the >> scheduler is

Here's a proposed patch for reworking register coalescing to allow pluggable coalescers. I think I've got the interfaces where I want them and am reasonably sure I've squashed most of the bugs. I'm still doing some testing and want to get through a whole regimen before committing. As a reminder, this patch has several goals: - Allow user-specified register coalescers, similar

On Monday 27 August 2007 15:13, Evan Cheng wrote: > 1. typedef std::set<const LiveInterval *> IntervalSet; > Please use SmallPtrSet instead. Ok. > 2. > + virtual void mergeIntervals(const LiveInterval &a, > + const LiveInterval &b, > + const MachineInstr &copy) {}; > > I find the name

Hi David, Thanks for this patch! Some comments: 1. typedef std::set<const LiveInterval *> IntervalSet; Please use SmallPtrSet instead. 2. + virtual void mergeIntervals(const LiveInterval &a, + const LiveInterval &b, + const MachineInstr &copy) {}; I find the name misleading. It's not actually

On Jul 17, 2007, at 8:40 AM, David Greene wrote: > On Monday 16 July 2007 18:19, Evan Cheng wrote: > >> Sorry I should have replied earlier. I really don't like this dual >> interface approach. To me, this muddles things without offering any >> real useful new functionalities. > > Ok. See below for the rationale. > >> IMHO, if a register coalescer is

On Aug 10, 2007, at 10:15 AM, David Greene wrote: > However, what happens when alias analysis information gets > invalidated? > Is Andersen's still "available" in the sense analysis groups use it? > > If not, it seems it would be tough to make sure Andersen's is always > used everywhere that AliasAnalysis is asked for because there are > passes > llvm

On Thursday 09 August 2007 19:21, Chris Lattner wrote: > Interesting question, I don't have an answer to this. To make things more > complicated, you can have multiple instances of an analysis group and may > want different things at different times: > > -basicaa -licm -something_that_invalidates_aa -andersaa -licm -whatever Some questions about that: How does this

On Tuesday 17 July 2007 13:06, Evan Cheng wrote: > > These two requirements led to the abstract RegisterCoalescer > > interface in the patch. This is the interface that register > > allocators > > know about. Likewise, coalescers need an abstract interface to > > register allocators to ask questions and do other things. > > If the two modules need to share

On Monday 09 July 2007 16:49, Reid Spencer wrote: > The only thing that comes to mind is that creating and running the > coalescer are separate operations so you might want to do the creation > of it in alias analysis style. Then, the allocator can a) determine if a > coalescer was created, b) obtain the coalescer that was created, if any, > and c) run it at the right time for the

Hi David, Sorry I should have replied earlier. I really don't like this dual interface approach. To me, this muddles things without offering any real useful new functionalities. IMHO, if a register coalescer is tied to a particular allocator. Then either it should simply belong to that allocator or that we have to allow the allocator to act as a pass manager itself, i.e. it can

On Wednesday 11 July 2007 15:07, Christopher Lamb wrote: > Could it be possible for there to be a harness type interface that > would allow coalescers that support both modes to be hooked into the > pass registration, and those that depend on the allocator not be > registered as passes? I have a patch for this kind of thing attached. Please take a look and let me know if it looks

>> Ok, that sounds like a good plan. I'll brush up on how alias analysis >> works and work from there. > > I've been looking at this and it's become clear to me that we need some kind > of abstract coalescing interface similar to what the AliasAnalysis class > provides. I think we need the same thing for register allocators. > > LLVM's existing

On Monday 16 July 2007 18:19, Evan Cheng wrote: > Sorry I should have replied earlier. I really don't like this dual > interface approach. To me, this muddles things without offering any > real useful new functionalities. Ok. See below for the rationale. > IMHO, if a register coalescer is tied to a particular allocator. Then > either it should simply belong to that allocator

On Monday 09 July 2007 17:07, David Greene wrote: > On Monday 09 July 2007 16:49, Reid Spencer wrote: > > The only thing that comes to mind is that creating and running the > > coalescer are separate operations so you might want to do the creation > > of it in alias analysis style. Then, the allocator can a) determine if a > > coalescer was created, b) obtain the

On Jul 17, 2007, at 8:49 PM, David A. Greene wrote: > On Tuesday 17 July 2007 14:21, David Greene wrote: > >>> I don't care for a MachineFunctionPass that can be directly >>> called. I >>> think it's a very good idea to keep the coalescers independent from >>> the allocators. If that's desired, we should enhance passmanager so >>>

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

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

Hi, I'm trying to sketch an LLVM-based implementation of the Extended Linear Scan algorithm, described in this Vivek Sarkar's paper: http://www.cs.rice.edu/~vs3/PDF/cc2007.pdf Sarkar reports that this version of Linear Scan produces better code than graph-coloring regallocs and is also much faster (15x to 68x). I already started work on the implementation of this algorithm and have a few