search for: precolor

Hi, David. 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. Imagine that on a second iteration allocation algorithm figures out that some spilled interval can't be ass...

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

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

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

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 flavor of it. > >> Unfortunately, it...

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