search for: precoloring

...s why they also have their weights set to #INF. Imagine that on a second iteration allocation algorithm figures out that some spilled interval can't be assigned a physical register. Allocator can't spill it so some recoloring must be done to free at least one physical register to allocate. Precoloring #INF weighted intervals makes allocation simpler by eliminating such situations. 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). But in theory you can spi...

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

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

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

Can someone explain the theory behind the spillers in VirtRegMap.cpp? It seems as though the spillers do triple duty: - Insert load/store operations and/or fold instructions as necessary to carry out spills - Rewrite the spilled virtual registers to use machine registers (mapping given by the caller in the VRM). - Rewrite machine code to change virtual registers to physical registers

...uncolored like every other interval then, right? When your algorithm finds out during one iteration that it should spill some interval it checks whether this interval is marked. If it is marked what's happening? Choosing some neighbour interval to spill instead of that one? Is this better then precoloring spill intervals (starting from allocation_order_end phys reg)? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070807/7b49e1f5/attachment.html>

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

For spilling, I plan to use the Hack-Braun generalization of the furthest-first heuristic for SSA: http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf For coloring, there are a few different approaches you can take, e.g. dominator tree scan, puzzle-solving, or a modified graph coloring / coalescing heuristic like IRC. The best quality for the least amount of implementation effort

The allocator you are building, is it the Hack's and Goos's polynomial time algorithm? On Tue, Oct 5, 2010 at 7:14 PM, Cameron Zwarich <zwarich at apple.com> wrote: > There is nothing that currently handles this properly, as far as I know. If you have a phi > > c = phi(a, b) > > where a, b and c are all assigned distinct stack slots, then copies must be inserted in