On Apr 16, 2007, at 1:17 PM, David Greene wrote:> 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. >>> Harvey >>> and Ken Kennedy and Timothy S. Oberg and Steven W. Reeves}, >>> YEAR = "2002", >>> TITLE = "Fast copy coalescing and live-range identification", >> >> Yep, this is the one I was thinking of. It is available online here: >> http://www.cs.rice.edu/~keith/LACSI/pldi02.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 good. Often > you'd rather copy than spill. > > Is anyone aware of publications addressing the interplay among > coalescing, live range splitting, register allocation and spilling? > > This is one of the reasons I want to separate all of these concerns. > We shouldn't force developers to always coalesce or always use some > generic measure of spill cost.These are "implementation details". They don't necessarily make good paper material. :-) Obviously, smart heuristics can make a big difference here (estimated register pressures, etc.) But the more important thing is how the passes down stream can recover from the earlier mistakes. By this, we mean live range splitting and re-materialization. Unfortunately, neither of these are feasible given the current infrastructure. Chris and I have been discussing a rewrite informally, but no formal plan has been materialized. Evan> > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Evan Cheng wrote:> Obviously, smart heuristics can make a big difference here (estimated > register pressures, etc.) But the more important thing is how the > passes down stream can recover from the earlier mistakes. By this, we > mean live range splitting and re-materialization.Can you explain this a little more? Do you mean that neither live range splitting nor rematerialization are practically possible with LLVM right now? If that's the case, what are the primary issues? These are things I will definitely have to do here so I'm quite interested in how this will all work. I'm more than happy to do a bunch of heavy lifting getting things into shape. -Dave
David Greene wrote:> Evan Cheng wrote: > >> Obviously, smart heuristics can make a big difference here (estimated >> register pressures, etc.) But the more important thing is how the >> passes down stream can recover from the earlier mistakes. By this, we >> mean live range splitting and re-materialization. > > Can you explain this a little more? Do you mean that neither liveOops, copied the wrong part of the paragraph. I meant to respond to this: > Unfortunately, neither of these are feasible given the current > infrastructure. -Dave
On Tue, 17 Apr 2007, David Greene wrote:> Evan Cheng wrote: >> Obviously, smart heuristics can make a big difference here (estimated >> register pressures, etc.) But the more important thing is how the >> passes down stream can recover from the earlier mistakes. By this, we >> mean live range splitting and re-materialization. > > Can you explain this a little more? Do you mean that neither live > range splitting nor rematerialization are practically possible > with LLVM right now?Anything is possible. :) In practice, there are good ways and bad ways to build things. For example, Evan recently implemented a really simple form of remat that works on instructions that have no register inputs (e.g. things like "load immediate"). That said, we want to implement the full generality of remat and splitting and have them work together well in the same framework. The key to this is getting the right data structure.> If that's the case, what are the primary issues?Evan is the best to respond to this at this point :)> These are things I will definitely have to do here so I'm quite > interested in how this will all work. I'm more than happy to do > a bunch of heavy lifting getting things into shape.Great! -Chris -- http://nondot.org/sabre/ http://llvm.org/