search for: coalescing

>> 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 coalescer is very simple. It just goes and replaces every > copy it can. In general, a coalescer will want to query the register > allocato...

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

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 already, I would like to reuse it (even > though I could of course create my own coalescing implementation). But &g...

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 implementation). But this class is a Machin...

...; I think we discussed this early but please remind me. Why is this > necessary? Why isn't interfere() sufficient test? Also, I would prefer > a name like isLegalToCoalesce over okToCoalesce. 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. > 4....

On Mon, Jul 10, 2023 at 12:20:01PM +0300, Gavin Li wrote: > Currently, coalescing parameters are grouped for all transmit and receive > virtqueues. This patch series add support to set or get the parameters for > a specified virtqueue. > > When the traffic between virtqueues is unbalanced, for example, one virtqueue > is busy and another virtqueue is idle, then i...

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

On Thu, 13 Jul 2023 07:40:12 -0400, "Michael S. Tsirkin" <mst at redhat.com> wrote: > On Mon, Jul 10, 2023 at 12:20:01PM +0300, Gavin Li wrote: > > Currently, coalescing parameters are grouped for all transmit and receive > > virtqueues. This patch series add support to set or get the parameters for > > a specified virtqueue. > > > > When the traffic between virtqueues is unbalanced, for example, one virtqueue > > is busy and another v...

...lents that can run through the PassManager) and those that are tied to some abstract register allocation algorithm. A coalescer that runs in conjunction with an allocator need not be tied to a particular implementation of register allocation. For example, George and Appel's Iterated Register Coalescing can work with any concrete implementation of graph coloring (and there are lots of variations out there) and can probably work with other algorithms as well. So if we can avoid it, I'd rather not be limited to hard-coding these things. These two requirements led to the abstract RegisterCoales...

...gh the > PassManager) and those that are tied to some abstract register > allocation algorithm. A coalescer that runs in conjunction with an > allocator need not be tied to a particular implementation of register > allocation. For example, George and Appel's Iterated Register > Coalescing can work with any concrete implementation of graph > coloring (and there are lots of variations out there) and can probably > work with other algorithms as well. So if we can avoid it, I'd > rather not > be limited to hard-coding these things. Ok. > > These two requiremen...

...ease remind me. Why is this >> necessary? Why isn't interfere() sufficient test? Also, I would >> prefer >> a name like isLegalToCoalesce over okToCoalesce. > > 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 struc...

...t at the right time for the allocator's algorithm, or even > > not at all. > > 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 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 i...

...ishing 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. createRegisterAllocator() is called by addPassesToEmit.* to instantiate the register allocator. Coalescing is a bit different. Typically, the register allocator is the client of the coalescer. My original thought was to have each register allocator implementation call createRegisterCoalescer directly. I then thought it might be better to have allocators just declare they want a coalescer run and le...

On Monday 27 August 2007 19:02, Evan Cheng wrote: > > 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 i...

...x: llvm/include/llvm/CodeGen/RegisterAllocator.h =================================================================== --- llvm/include/llvm/CodeGen/RegisterAllocator.h (revision 0) +++ llvm/include/llvm/CodeGen/RegisterAllocator.h (revision 0) @@ -0,0 +1,41 @@ +//===-- RegisterAllocator.h - Register Coalescing Interface ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +// ===-----------------------...

...cer that doesn't work with the register allocator of choice, we > can output an error (or a warning and override the choice). Ok. > > Register allocators know information about interference, for example, > > the interference graph in a coloring allocator. The classic > > coalescing > > algorithm examines the interference graph and looks for copies between > > allocation units whose corresponding nodes do not have an edge between > > them in the graph. That's why that interface is there. > > Right, then perhaps the interference graph should not be...

Chris Lattner wrote: > On Thu, 12 Apr 2007, Fernando Magno Quintao Pereira wrote: >>> I'm definitely interested in improving coalescing and it sounds like >>> this would fall under that work. Do you have references to papers >>> that talk about the various algorithms? >> Some suggestions: >> >> @InProceedings{Budimlic02, >> AUTHOR = {Zoran Budimlic and Keith D. Cooper and Timothy J....

...ng 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. > > createRegisterAllocator() is called by addPassesToEmit.* to instantiate the > register allocator. > > Coalescing is a bit different. Typically, the register allocator is the > client of the coalescer. My original thought was to have each register > allocator implementation call createRegisterCoalescer directly. I then > thought it might be better to have allocators just declare they want a >...

...RegisterCoalescer.h? 5. + /// Run the coalescer on this function, providing interference + /// data to query. Return whether we removed any copies. + virtual bool coalesceFunction(MachineFunction &mf, InterferenceData &ifd) = 0; 80 col violation. 6. + /// doWork - The main coalescing algorithm. Return whether any + /// copies were coalesced. + bool doWork(MachineFunction &mf); Please rename it to something like performCoalescing. Also, is this defined anywhere? 7. About class LinearScanInterferenceData. Since it's just an example, perhaps it should go into...

...= 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 // R2 = R2 + 4 The reason this wasn't coalesced, is because of overlapping during coalescing: 864B %vreg11<def> = LA %vreg2, 4, %noreg 880B %vreg16<def> = LLCMux %vreg2, 4, %noreg 928B %vreg2<def> = COPY %vreg11 It seems that if this had been rescheduled to 880B %vreg16<def> = LLCMux %vreg2, 4, %noreg 864B %...