On Monday 06 August 2007 12:15, Anton Vayvod wrote:> Spill intervals must be precolored because they can't be spilled once more. > They are the shortest intervals precisely over each def/use of the original > interval. That is why they also have their weights set to #INF.Yes, that's true. But I wonder if we shouldn't be smarter about which register we pick to color it. In Bill W's implementation, it was essentially random. What was your solution to this?> As for giving the best result. If assumed that each interval is spilled > into the shortest spill intervals then precoloring won't do any harm to the > quality of allocation (as shown above).Wait, but aren't you implying then that it's impossible for an interval corresponding to a spill to be uncolorable? I don't think that's true. Therefore, precoloring most certainly can cause harm because a decision is being made in local context without the global information that could help make a better one.> But in theory you can spill intervals differently. For example, interval can > be split into two intervals - the shortest interval that cannot be colored > right now and the rest part that can be colored. That say if you have [10, > 50) intervals that conflicts with [40, 45) and can't be colored it can be > split into smth like [10, 40) and [40, 50). The former part should not be > precolored as it has less conflicts (it doesn't intersects with [40, 45) ) > and can be colored entirely by one register on the next iteration.Right. Live range splitting would indeed be nice to have. Bill's implementation has a flavor of it.> Unfortunately, it seems that current implementation doesn't support such > "clever" spilling.True. People have talked about adding it ever since I started getting involved.> Anyway, this precoloring doesn't force allocation algorithms to be > non-iterative. In my implementation of optimistic register coloring I > precolor spill intervals at the beginning of each iteration and thus don't > have to spill their neghbours specifically. It was done automatically by > Select phase of algorithm.So how did you get around the requirement of the spillers that intervals be mapped to physical registers? Or did you not use the provided spillers? That may be what I end up doing. Loads and stores don't absolutely have to be inserted into the actual instruction text on each iteration, though it is nice for debugging purposes.> As Fernando has mentioned while I was writing this after the last iteration > of your algorithm before you call Spiller::runOnMachineFunction method > every interval in VirtRegMap must be mapped to a physical register, both > spill and others.Right, which means the pre-defined spillers can't be called during iteration. -Dave
On Monday 06 August 2007 16:44, Chris Lattner wrote:> >> Unfortunately, it seems that current implementation doesn't support such > >> "clever" spilling. > > > > True. People have talked about adding it ever since I started getting > > involved. > > To be clear, the spiller interface does support (or could with very > straight-forward extension) splitting, it just requires you to give the > split ranges new intervals and a new vreg.Right. Splitting should happen outside of the spiller, in the allocator proper. The spiller should not care how intervals got there. Except for the ones that perform spills and reloads, of course. :) -Dave
On Mon, 6 Aug 2007, David Greene wrote:>> split into smth like [10, 40) and [40, 50). The former part should not be >> precolored as it has less conflicts (it doesn't intersects with [40, 45) ) >> and can be colored entirely by one register on the next iteration. > > Right. Live range splitting would indeed be nice to have. Bill's > implementation has a flavor of it. > >> Unfortunately, it seems that current implementation doesn't support such >> "clever" spilling. > > True. People have talked about adding it ever since I started getting > involved.To be clear, the spiller interface does support (or could with very straight-forward extension) splitting, it just requires you to give the split ranges new intervals and a new vreg. -Chris -- http://nondot.org/sabre/ http://llvm.org/
On 8/7/07, David Greene <dag at cray.com> wrote:> > On Monday 06 August 2007 12:15, Anton Vayvod wrote: > > > Spill intervals must be precolored because they can't be spilled once > more. > > They are the shortest intervals precisely over each def/use of the > original > > interval. That is why they also have their weights set to #INF. > > Yes, that's true. But I wonder if we shouldn't be smarter about which > register we pick to color it. In Bill W's implementation, it was > essentially > random. What was your solution to this?I allocated spill intervals at the beginning of each iteration so all the rest intervals (except of physreg intervals) were uncolored at the moment. So the only difference in allocating regs for spills was what end to choose: allocation_order_begin() or allocation_order_end(), I chose the former. I understand that sometimes you can prefer one register over another for spill so it won't conflict with as much intervals as it would being mapped to another phys, but the same can be said about every interval, right?> > As for giving the best result. If assumed that each interval is spilled > > into the shortest spill intervals then precoloring won't do any harm to > the > > quality of allocation (as shown above). > > Wait, but aren't you implying then that it's impossible for an interval > corresponding to a spill to be uncolorable? I don't think that's true. > Therefore, precoloring most certainly can cause harm because a decision > is being made in local context without the global information that could > help make a better one.At least this is the imply of LiveIntervals: try to call addIntervalsForSpills on a spill interval and you'll have an assertion (that was true at least for 1.9, probably it's true now). If spill interval has a length of 1 (and it has because of addIntervalsForSpills implementation) it can't be spilled again physically. Moreover if you were able to spill such intervals your iterations could become an infinite loop: algorithm could spill these intervals over and over again. Having spill intervals mapped to physregs garantees that your iterations will finish eventually.> But in theory you can spill intervals differently. For example, interval > can > > be split into two intervals - the shortest interval that cannot be > colored > > right now and the rest part that can be colored. That say if you have > [10, > > 50) intervals that conflicts with [40, 45) and can't be colored it can > be > > split into smth like [10, 40) and [40, 50). The former part should not > be > > precolored as it has less conflicts (it doesn't intersects with [40, > 45) ) > > and can be colored entirely by one register on the next iteration. > > Right. Live range splitting would indeed be nice to have. Bill's > implementation has a flavor of it.In case live range splitting implemented spill intervals wouldn't have to be the shortest when some interval is spilled the first time. But during iterations uncolored spill intervals should become shorter and shorter until they are must-be-precolored.> Unfortunately, it seems that current implementation doesn't support such > > "clever" spilling. > > True. People have talked about adding it ever since I started getting > involved. > > > Anyway, this precoloring doesn't force allocation algorithms to be > > non-iterative. In my implementation of optimistic register coloring I > > precolor spill intervals at the beginning of each iteration and thus > don't > > have to spill their neghbours specifically. It was done automatically by > > Select phase of algorithm. > > So how did you get around the requirement of the spillers that intervals > be mapped to physical registers? Or did you not use the provided > spillers? > That may be what I end up doing. Loads and stores don't absolutely have > to be > inserted into the actual instruction text on each iteration, though it is > nice > for debugging purposes.As far as I understand, you don't need to call spiller every iteration. LiveIntervals::addIntervalsForSpills does everything necessary for allocation to start next iteration. The idea is that when you spill some interval you only need to replace it with spill intervals for loads and stores and do the next iteration on new interval set but you don't need to insert actual instructions in code until the very end of your algorithm.> As Fernando has mentioned while I was writing this after the last > iteration > > of your algorithm before you call Spiller::runOnMachineFunction method > > every interval in VirtRegMap must be mapped to a physical register, both > > spill and others. > > Right, which means the pre-defined spillers can't be called during > iteration.Exact. Anton. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070807/cb02b3f4/attachment.html>
On Tuesday 07 August 2007 05:00, Anton Vayvod wrote:> > Yes, that's true. But I wonder if we shouldn't be smarter about which > > register we pick to color it. In Bill W's implementation, it was > > essentially random. What was your solution to this? > > I allocated spill intervals at the beginning of each iteration so all the > rest intervals (except of physreg intervals) were uncolored at the moment. > So the only difference in allocating regs for spills was what end to > choose: allocation_order_begin() or allocation_order_end(), I chose the > former. I understand that sometimes you can prefer one register over > another for spill so it won't conflict with as much intervals as it would > being mapped to another phys, but the same can be said about every > interval, right?Ah, ok, that makes sense. Yes, this is true of every interval. It's the classic, "do I reuse registers to limit spilling or chew up registers to help scheduling" question. FYI, in my implementation I just marked the intervals introduced by spills as being special so that they would not be chosen to be spilled again. Then they just get colored like every other interval.> > Wait, but aren't you implying then that it's impossible for an interval > > corresponding to a spill to be uncolorable? I don't think that's true. > > Therefore, precoloring most certainly can cause harm because a decision > > is being made in local context without the global information that could > > help make a better one. > > At least this is the imply of LiveIntervals: try to call > addIntervalsForSpills on a spill interval and you'll have an assertionYep, and that's a good check.> algorithm could spill these intervals over and over again. Having spill > intervals mapped to physregs garantees that your iterations will finish > eventually.As noted above, you don't actually have to color them early. You can just mark them as unspillable. There will always be some other interval to spill, unless there's a serious bug in the algorithm.> > Right. Live range splitting would indeed be nice to have. Bill's > > implementation has a flavor of it. > > In case live range splitting implemented spill intervals wouldn't have to > be the shortest when some interval is spilled the first time. But during > iterations uncolored spill intervals should become shorter and shorter > until they are must-be-precolored.Right, except for the pre-coloring bit. :)> As far as I understand, you don't need to call spiller every iteration.Right, that was my fundamental misunderstanding. I've got it straight now. Thanks to everyone for the help. -Dave