similar to: [LLVMdev] Live Range Splitting

On Wednesday 23 January 2008 02:01, Evan Cheng wrote: > On Jan 22, 2008, at 12:23 PM, David Greene wrote: > > Evan, > > > > Can you explain the basic mechanics of the live interval splitting > > code? > > Is it all in LiveIntervalAnalysis.cpp under addIntervalsForSpills > > and child > > routines? What is it trying to do? > > It's splitting

On Jan 23, 2008, at 2:40 PM, David Greene <dag at cray.com> wrote: > On Wednesday 23 January 2008 02:01, Evan Cheng wrote: >> On Jan 22, 2008, at 12:23 PM, David Greene wrote: >>> Evan, >>> >>> Can you explain the basic mechanics of the live interval splitting >>> code? >>> Is it all in LiveIntervalAnalysis.cpp under

On Jan 22, 2008, at 12:23 PM, David Greene wrote: > Evan, > > Can you explain the basic mechanics of the live interval splitting > code? > Is it all in LiveIntervalAnalysis.cpp under addIntervalsForSpills > and child > routines? What is it trying to do? It's splitting live intervals that span multiple basic blocks. That is, when an interval is spilled, it

Evan, Can you explain the basic mechanics of the live interval splitting code? Is it all in LiveIntervalAnalysis.cpp under addIntervalsForSpills and child routines? What is it trying to do? Also, in the ancient subregister coalescing code, there used to be an update of the SSARegMap to point subregisters to the superregister they were coalesced to (IIRC). That has since gone away. I used to

Hi Evan, I have a few questions about current implementation of live intervals spilling, which is required for the implementation of Extended Linear Scan algorithm. --- Evan Cheng <evan.cheng at apple.com> wrote: > > On Wednesday 23 January 2008 02:01, Evan Cheng wrote: > >> On Jan 22, 2008, at 12:23 PM, David Greene wrote: > >>> Evan, > >>> >

Hi Evan, Thanks a lot for your reply! 2009/2/27 Evan Cheng <evan.cheng at apple.com>: > > On Feb 27, 2009, at 7:20 AM, Roman Levenstein wrote: > >> Hi, >> >> I'm working on the implementation of Extended Linear Scan register >> allocator as described by Sarkar & Bodik. >> One of the interesting features of their algorithm is the possibility

Hi Fernando, --- Fernando Magno Quintao Pereira <fernando at cs.ucla.edu> wrote: > > Hi, Roman, > > maybe I can try to answer this. I think that all boils down to > having register to reload spilled values. Ok. That I can follow. > Once a register is spilled, its live range is split into smaller > pieces. These pieces most be contained into registers, and

On Feb 27, 2009, at 7:20 AM, Roman Levenstein wrote: > Hi, > > I'm working on the implementation of Extended Linear Scan register > allocator as described by Sarkar & Bodik. > One of the interesting features of their algorithm is the possibility > to allocate different physical registers to different live-ranges of > the same LiveInterval. Of course, it may require

On Wednesday 23 January 2008 02:01, Evan Cheng wrote: > > Can you explain the basic mechanics of the live interval splitting > > code? > It's splitting live intervals that span multiple basic blocks. That > is, when an interval is spilled, it introduce a single reload per > basic block and retarget all the uses to use the result of the single > reload. It does not

Hi, I'm working on the implementation of Extended Linear Scan register allocator as described by Sarkar & Bodik. One of the interesting features of their algorithm is the possibility to allocate different physical registers to different live-ranges of the same LiveInterval. Of course, it may require some glue code to be inserted in cases, where different physical regs were assigned to

Dear LLVMers OK, when I signed up for this mailing list, I asked for a once-daily digest. This is the fourth digest I receive today, and there are about that many each day. The only reason I subscribe to the mailing list is so I can post to it. But I don't need to receive the emails, because I can fully well read them in the archive online, and I certainly don't want to get spammed

Hi, Roman, maybe I can try to answer this. I think that all boils down to having register to reload spilled values. Once a register is spilled, its live range is split into smaller pieces. These pieces most be contained into registers, and it is the task of the allocator to find these registers. Imagine that you have something like: Before After allocation: allocation: a

On 7 August 2013 17:06, Jakob Stoklund Olesen <stoklund at 2pi.dk> wrote: > With the D-Wave computer in the news recently, you may find it interesting that LLVM’s register allocator is using Ising models to compute regions for live range splitting. > > The problem of finding a region for splitting a live range is mapped to an Ising model with the help of the edge bundle graph, see

Hi, Anton and Fernando have answered most of your questions. I don't have anything to add there. I do want to comment on the "conservative" nature of LiveIntervalAnalysis. I think the comment is misleading and is probably just a relic of early implementation. The biggest problem with the current implementation is the overly aggressive copy coalescer. Right now the

With the D-Wave computer in the news recently, you may find it interesting that LLVM’s register allocator is using Ising models to compute regions for live range splitting. The problem of finding a region for splitting a live range is mapped to an Ising model with the help of the edge bundle graph, see EdgeBundles.h. A node in the edge bundle graph represents a set of CFG edges that enter or

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 May 9, 2008, at 12:21 PM, David Greene wrote: > On Friday 09 May 2008 13:20, David Greene wrote: > >> One is that %reg1461 is assigned a register but LocalSpiller still >> tries to >> remat it instead of just using the register it was assigned to. I >> think >> it's easy enough to fix this problem, but I don't think this gets >> at the

Jeff Kunkel <jdkunk3 at gmail.com> writes: > Spiller::Spill( LiveInterval *li, >                           SmallVectorImpl<LiveInterval*> &newIntervals, >                           const SmallVectorImpl<LiveInterval*> &spillIs ); > > has two reference vectors which contain a small list of Live > Intervals. What is the register allocator's job to do

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 Aug 8, 2013, at 9:01 AM, David Tweed <David.Tweed at arm.com> wrote: > Just as general comments not related to the specific implementation in LLVM: > > I believe that 2-state Ising models can be reduced to max-flow/min-cut (eg, Finding ground states in random-field Ising ferromagnets by F Barahona) , so were a guaranteed polynomial time solution wanted that could be used