search for: coallesce

...ed, it sounds as the same bug. Two questions: 1) At least, it would be better if LLVM would crash on an assertion instead of running for ever in such situations. I think this can be easily detected, since this is a case where nothing could be spilled. 2) You write in PR711: >This is due to the coallescer coallescing virtregs with both EAX and >EDX, which makes them unavailable to satisfy spills, causing the RA to >run out of registers. We want to coallesce physregs when possible, >but we cannot pin them in the spiller: >we have to be able to >uncoallesce them. First of all, I t...

...> So far, this has been pretty easy. I've created a new > SimpleRegisterCoalescing pass and the member functions > divide pretty cleanly between than and LiveIntervals. Beyond that, one of the issues is the "r2rmap" and "rep" function. As you've noticed, the coallescer basically uses these to avoid rewriting the code after it does coallescing. For example, if r1024 is coallesced with r1026, it leaves all uses of both registers in the code, instead of rewriting uses of r1026 with r1024 and deleting all memory of r1026. This mades sense long ago, but now it i...

...ly have control, as most of the explicit copies are gone by the time regalloc happens. This means that you have an arbitrary set of copies that come from things like 2-addr elim, phi elim, extensions that don't generate code, etc. Instead of doing this. I think the right design is to: 1. Coallesce vregs together as aggressively as possible. Build huge live ranges, delete as many copies as possible. 2. Start priority based register allocation. 3. For each live range without a register available, consider: 1. live range splitting 2. remat 3. spilling In particular, by doing live...

...that last statement actually do the rewrite? > > Hrm, yes, yes it appears so. Question is: doesn't this make the r2r map > dead? Does something else fill it in? My memory is hazy here :). If it > is dead, we should rip it out (actually, we should make it private to the > coallescer function). I'm trying an experiment to eliminate the r2r map altogether. Is there an efficient way to replace all references to a virtual register? That is, given a virtual register number, is there an easy way to get a list of all Instructions and/or Operands that reference it? I've b...

...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? > Beyond that, one of the issues is the "r2rmap" and "rep" function. As > you've noticed, the coallescer basically uses these to avoid rewriting the > code after it does coallescing. For example, if r1024 is coallesced with > r1026, it leaves all uses of both registers in the code, instead of > rewriting uses of r1026 with r1024 and deleting all memory of r1026. This > mades sense lo...

...ast statement actually do the rewrite? >> Hrm, yes, yes it appears so. Question is: doesn't this make the r2r map >> dead? Does something else fill it in? My memory is hazy here :). If it >> is dead, we should rip it out (actually, we should make it private to the >> coallescer function). > > I'm trying an experiment to eliminate the r2r map altogether. Is there > an efficient way to replace all references to a virtual register? That > is, given a virtual register number, is there an easy way to get a list > of all Instructions and/or Operands that r...

On Thu, 12 Apr 2007, David Greene wrote: >> Beyond that, one of the issues is the "r2rmap" and "rep" function. As >> you've noticed, the coallescer basically uses these to avoid rewriting the >> code after it does coallescing. For example, if r1024 is coallesced with >> r1026, it leaves all uses of both registers in the code, instead of >> rewriting uses of r1026 with r1024 and deleting all memory of r1026. This >> ma...

Hi all, As I work toward improving LLVM register allocation, I've come across the need to do some refactoring. Specifically, I would like to separate register coalescing from live interval analysis. Right now LiveIntervals handles both. The reason I want to separate them is that other types of register allocators might like to do coalescing differently (e.g. graph coloring does it by

Chris Lattner wrote: > No there isn't, unfortunately. I'd suggest building up/maintaining the > r2r map inside the coallescer. Once the coallescer is done with the > entire function, do a single pass over the function rewriting all the > coallesced vregs. Ok. I have a version with the coalescer separated from liveIntervalAnalysis. It still uses the r2r map but as we discussed late last week, it looks like the...

Here''s a peculiar one. I''m trying to simulate some speed effects due to varying sized packets so I have written a quick perl app which spits out packets of a fixed size (<1500 bytes). What I''m finding is the despite apparently turning off nagle and everything else I can think of I still notice that when the receiver isn''t keeping up that the sending

...d Greene wrote: >>> As I work toward improving LLVM register allocation, I've >>> come across the need to do some refactoring. Yay! >> Beyond that, one of the issues is the "r2rmap" and "rep" >> function. As >> you've noticed, the coallescer basically uses these to avoid >> rewriting the >> code after it does coallescing. For example, if r1024 is >> coallesced with >> r1026, it leaves all uses of both registers in the code, instead of >> rewriting uses of r1026 with r1024 and deleting all memory of...

On Fri, 30 Jun 2006, Fernando Magno Quintao Pereira wrote: > where %reg1032 is dead. Right. One of the jobs of the register allocator is to coallesce register copies. Once coallesced, they can be removed. > I'm removing these instructions. In Linear scan, they are removed too. > I'm removing all the dead definitions from instructions that are not > function calls, and the resulting programs seem to work fine. The ratio I s...

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 =

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

On Thu, 21 Dec 2006, Roman Levenstein wrote: > following: > 1) some of the fixed registers intervals are merged with some virtual > registers intervals > 2) later there is a need to spill one of the allocated registers, but > since all joined intervals are FIXED intervals now due to (1), they > cannot be spilled. Therefore, the register allocator loops for ever. > > I would

> > It seems to me that the only instructions > > with dead definitions that I should not remove are the calls. Is it true? > > I would like to know if a code like this below is safe, that is, besides > > call instructions, is there other instructions that must stay in the code > > even if their definitions are dead? > > > > MachineInstr * mi = iter; >

Chris Lattner wrote: > On Tue, 22 Jun 2004, Vladimir Prus wrote: > > First, I attach two files -- LLVM asm and the asm for my target. The > > problem with assembler is: on line 171 it uses register gr2, which is > > copied from gr6 above, on line 161. The only predecessor of this basic > > block is jump on line 90. The problem is that gr6 is not initialized in > >

...like this: > > > CL = shamt_virtreg > X = shl Y, CL > > We don't want the copy and shift to wander apart from each other (e.g. we > don't want another shift to get scheduled in between them), so we flag > them together. In practice, these copies usually get coallesced away. In the second case shl explicitly uses CL. Shouldn't the register allocator be smart enough to avoid scheduling an instruction that destroys CL in between them? In the first case, what do you think about making it possible for an instruction to optionally depend on a value? That is, mak...

...d be represented as explicit registers, and the GPRs should be virtual registers. This would give you code that looks something like this: %reg1024 = add v1, c1 %reg1025 = mul v1, c2 %reg1026 = mul %reg1024, %v2 %o1 = mov %reg1026 The 'mov' register-to-register copy instruction will be coallesced and eliminated by the register allocator. The regalloc will eliminate the virtual registers, assigning physical GPRs. This is what the 'allocation order' is to cover. > I planed to partition the register into different RegisterClass: > input, output, general purpose, constant,...

On 08/09/05, Alkis Evlogimenos <evlogimenos at gmail.com> wrote: > representative register (found using a union find algorithm). Note that > the representative register could be a real register if we ever joined > an interval of a real register with one of a virtual register (and this > real register will be the representative register of the set of > intervals joined