On Tue, 2012-10-02 at 10:57 -0400, Vladimir Makarov wrote: > Chaitin-Briggs literature does not discuss the termination, just saying > that live-ranges shortening will result to assigning hard regs to all > necessary pseudos which is not clearly guaranteed. There is the same > problem in LRA. So LRA checks that too many passes are done or to many > reloads for one insn are made and abort LRA. Porting LRA is mostly > fixing such aborts.
IIRC, talking with the guys from Rice, they had a limit on the number of color/spill iterations (20) before aborting, since anything more than that would be due to a bug. I believe the largest number of iterations I ever saw in my allocator was about 6 iterations of color/spill. I hit a few cases that iterated forever, but those were always due to bugs in my code or special hairy details I hadn't handled. You're correct that the hairy details are never discussed in papers. :) > Another thing omitted by literature is inheritance which is very > important for performance. Although it could be considered as a special > case of live-range splitting. There are also a lot of small important > details (e.g. what to do in case of displacement constraints, To handle displacement constraints, instead of spilling to stack slots, we spilled to spill pseudos which look like normal register pseudos. We would then color them just like normal pseudos, but the colors represent stack slots and not registers. If "k" becomes too big, it means you surpassed the maximum displacement, and you'll have to spill the spill pseudo. For small displacement cpus, coloring the spill pseudos does a good job reusing stack slots which reduces the largest displacement you'll see. For cpus with no displacement issues, you could just give each spill pseudo a different color which would mean you wouldn't have to compute a interference graph of the spill pseudos and all the work and space that goes into building that. Note, with spill pseudos, you can perform dead code elimination, coalescing and other optimizations on them just like normal pseudos to reduce the amount of spill code generated. Peter