search for: coalesce

...rks 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 coalescer is very simple. It just goes and replaces every > copy it can. In general, a coalescer will want to query the register > allocator about which copies it should remove. For example, Briggs' > conservative coalescer will not remove copies that could potentially cause > spills. On...

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 coalescer...

...Coloring algorithm,. It's not easy to accomplish within the LLVM framework. I've made a number of structural changes to our code here and it's in a bit of a state of bitrot due to upstream changes we haven't merged in yet. I got some of this work merged upstream in the RegisterCoalescer and RegallocQuery interfaces. RegallocQuery is supposed to be an opaque communication conduit between register allocators and coalescers such that the allocator can update the coalescer when it makes changes and vice versa. When I did the full implementation I found I had to make more changes...

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

...h to reflect the merge. > Please choose a more descriptive name. Yes it's for updating the graph. I'll pick a better name, but I don't want it to be graph-specific. > 3. > > + /// Allow the register allocator to communicate when it doesn't > + /// want a copy coalesced. This may be due to assumptions made by > + /// the allocator about various invariants and so this question is > + /// a matter of legality, not performance. Performance decisions > + /// about which copies to coalesce should be made by the > + /// coalescer. > + vi...

...d, for example, one virtqueue > is busy and another virtqueue is idle, then it will be very useful to > control coalescing parameters at the virtqueue granularity. series: Acked-by: Michael S. Tsirkin <mst at redhat.com> > Example command: > $ ethtool -Q eth5 queue_mask 0x1 --coalesce tx-packets 10 > Would set max_packets=10 to VQ 1. > $ ethtool -Q eth5 queue_mask 0x1 --coalesce rx-packets 10 > Would set max_packets=10 to VQ 0. > $ ethtool -Q eth5 queue_mask 0x1 --show-coalesce > Queue: 0 > Adaptive RX: off TX: off > stats-block-usecs: 0 > sample-int...

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 allocator's algorithm, or even &...

...irtqueue granularity. > > series: > > Acked-by: Michael S. Tsirkin <mst at redhat.com> Why? This series has the bug I reported. Are you thinking that is ok? Or this is not a bug? Thanks. > > > > > Example command: > > $ ethtool -Q eth5 queue_mask 0x1 --coalesce tx-packets 10 > > Would set max_packets=10 to VQ 1. > > $ ethtool -Q eth5 queue_mask 0x1 --coalesce rx-packets 10 > > Would set max_packets=10 to VQ 0. > > $ ethtool -Q eth5 queue_mask 0x1 --show-coalesce > > Queue: 0 > > Adaptive RX: off TX: off > > st...

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 or that we have to > allow the allocator to act as a pass manager itself, i.e. it can > control what passes to run as part the allocating process. I don't > know if the pass manager allows th...

...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 or that we have to >> allow the allocator to act as a pass manager itself, i.e. it can >> control what passes to run as part the allocating process. I don't >> know if the pass m...

On Aug 27, 2007, at 2:04 PM, David Greene wrote: > >> 3. >> >> + /// Allow the register allocator to communicate when it doesn't >> + /// want a copy coalesced. This may be due to assumptions >> made by >> + /// the allocator about various invariants and so this >> question is >> + /// a matter of legality, not performance. Performance >> decisions >> + /// about which copies to coalesce should be made...

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 coalescer that was created, if any, > > and c) run it at the right time for the allocator's algor...

Ok, I'm at a point now where I can implement plyggable register coalescers as we originally wanted when I started the refactoring work. I'm in the midst of finishing up an implementation following the model of how register allocators are selected. Thgere may be some more refactoring/code sharing work to be done with this, but I want to get it working first. creat...

...> > interfere() isn't sufficient because the allocation algorithm may > > place other > > constraints on coalescing. George and Appel's iterated register > > coalescing > > is a prime example. It wants to "freeze" copies that should not be > > coalesced > > because doing so might cause spilling. You don't want the coalescer > > touching > > these because if it does the data structures will be inconsistent. > > Ok. But that means this method doesn't belong to the InterferenceData > class. Shouldn't the alloc...

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 control what passes to run as part the allocating process. I don't know if the pass manager allows that functiona...

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 information. I think...

...pdf I was just looking at this today. One thing that strikes me about all these papers I've read on the topic is that no one seems to consider the interaction of coalescing with spilling. By definition coalescing increases lifetimes and can cause more interferences. Yet the papers all try to coalesce as many copies as possible. On, say, the x86 machines, the cost of a spill is really not much different from the cost of a copy so it's probably close to a wash in the end. But there are many machines where the cost of each operation is vastly different. Aggressive coalescing is not always g...

Hi David, On Mon, 2007-07-09 at 16:32 -0500, David Greene wrote: > Ok, I'm at a point now where I can implement plyggable register coalescers as > we originally wanted when I started the refactoring work. > > I'm in the midst of finishing up an implementation following the model of how > register allocators are selected. Thgere may be some more refactoring/code > sharing work to be done with this, but I want to get...

...mp;copy) {}; I find the name misleading. It's not actually performing the merging, right? It's updating the interference graph to reflect the merge. Please choose a more descriptive name. 3. + /// Allow the register allocator to communicate when it doesn't + /// want a copy coalesced. This may be due to assumptions made by + /// the allocator about various invariants and so this question is + /// a matter of legality, not performance. Performance decisions + /// about which copies to coalesce should be made by the + /// coalescer. + virtual bool okToCoalesce(c...

Hi, I am seeing cases of poorly coalesced IV updates on SystemZ: In the final IR, it is obvious that %R4D<def> = LA %R2D<kill>, 4, %noreg // R4 = R2 + 4 %R2D<def> = LGR %R4D<kill> // R2 = R4 could be optimized to -> %R2D<def> = LA %R2D<kill>, 4, %noreg //...