I just enabled a new algorithm for computing live intervals that doesn't
depend on LiveVariables.
The goal is to get rid of the LiveVariables analysis completely, but
unfortunately PHI elimination and the two-address pass still use LiveVariables
for some optimizations. They don't require it, they work just fine without
it at -O0. They use it to generate better code in some cases.
The current pass order in the optimizing pipeline is:
Live Variable Analysis
Eliminate PHI nodes for register allocation
Two-Address instruction pass
Slot index numbering
Live Interval Analysis
LiveIntervals still claims to require LiveVariables to make sure it stays live
during phi-elim and 2-addr.
The plan is to 'bubble up' LiveIntervals, by first teaching 2-addr to
use and update it:
Live Variable Analysis
Eliminate PHI nodes for register allocation
Slot index numbering
Live Interval Analysis
Two-Address instruction pass
There is an -early-live-intervals option that enables that pass order.
Then do the same to phi-elim:
Live Variable Analysis
Slot index numbering
Live Interval Analysis
Eliminate PHI nodes for register allocation
Two-Address instruction pass
Then LiveVariables can be deleted. (And so can SparseBitVector).
When live intervals are computed on SSA form, we can use tricks to speed up live
range computations for values that span large loops by resurrecting the
MachineLoopRanges analysis.
/jakob
How much of the work is done here? I'd be happy to do the phi elimination part, since I basically did that for StrongPhiElimination (RIP). IIRC you run into a lot of problems with NEON subregister defs, which might be fixed by your new direct LiveIntervals implementation. Cameron On Feb 8, 2013, at 3:41 PM, Jakob Stoklund Olesen <stoklund at 2pi.dk> wrote:> I just enabled a new algorithm for computing live intervals that doesn't depend on LiveVariables. > > The goal is to get rid of the LiveVariables analysis completely, but unfortunately PHI elimination and the two-address pass still use LiveVariables for some optimizations. They don't require it, they work just fine without it at -O0. They use it to generate better code in some cases. > > The current pass order in the optimizing pipeline is: > > Live Variable Analysis > Eliminate PHI nodes for register allocation > Two-Address instruction pass > Slot index numbering > Live Interval Analysis > > LiveIntervals still claims to require LiveVariables to make sure it stays live during phi-elim and 2-addr. > > The plan is to 'bubble up' LiveIntervals, by first teaching 2-addr to use and update it: > > Live Variable Analysis > Eliminate PHI nodes for register allocation > Slot index numbering > Live Interval Analysis > Two-Address instruction pass > > There is an -early-live-intervals option that enables that pass order. > > Then do the same to phi-elim: > > Live Variable Analysis > Slot index numbering > Live Interval Analysis > Eliminate PHI nodes for register allocation > Two-Address instruction pass > > Then LiveVariables can be deleted. (And so can SparseBitVector). > > When live intervals are computed on SSA form, we can use tricks to speed up live range computations for values that span large loops by resurrecting the MachineLoopRanges analysis. > > /jakob > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Feb 8, 2013, at 4:03 PM, Cameron Zwarich <zwarich at apple.com> wrote:> How much of the work is done here? I'd be happy to do the phi elimination part, since I basically did that for StrongPhiElimination (RIP).Any help would be appreciated. I did a bit of the easy stuff in 2-addr, it has a LIS = getAnalysisIfAvailable<LiveIntervals>() member that it sometimes updates. It has a lot of weird transformations, though. I haven't touched phi-elim yet because of the 'bubble-up' approach. If you want to help with phi-elim, you could hack -early-live-intervals to insert LiveIntervals before phi-elim, and then run MF.verify(this) at the end of runOnMachineFunction(). That should be enough to check that phi-elim updates live intervals correctly even when 2-addr is going to break it later.> IIRC you run into a lot of problems with NEON subregister defs, which might be fixed by your new direct LiveIntervals implementation.The direct live intervals work on anything that has virtual registers - it can handle all the sub-register fun. I don't think you will see any problems with sub-registers in phi-elim because PHI instructions never have sub-register operands. (And this version of phi-elim just inserts a million copies). /jakob