Deleting LiveVariables

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

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

That reminds me: LiveRangeCalc::extendToUses() has code to deal with PHI instructions, but I am not sure it has ever actually met one. There could be lurking bugs.

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

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.

I'll try doing that. Did you ever add a way to update LiveIntervals quickly after splitting an edge or will that have to finally be added? I can skip the critical edge splitting for now.

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

Jogging my memory some more, the problem wasn't with values in phis, it was just that the change in pass ordering broke subregister liveness in some other ways. StrongPhiElimination goes after the 2-address pass rather than before it, but it looks like you are preserving the existing ordering.

Cameron

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.

I'll try doing that. Did you ever add a way to update LiveIntervals quickly after splitting an edge or will that have to finally be added? I can skip the critical edge splitting for now.

That doesn't exist yet, we'll need that too.

My thinking was to keep a list of all global live ranges in LiveIntervals so we at least don't have to go through all the local virtual registers when splitting a critical edge. (That's how LiveVariables is updated now, and it's slow).

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

Jogging my memory some more, the problem wasn't with values in phis, it was just that the change in pass ordering broke subregister liveness in some other ways. StrongPhiElimination goes after the 2-address pass rather than before it, but it looks like you are preserving the existing ordering.

I see. Yes, things get a lot more complicated after 2-addr has removed INSERT_SUBREG and REG_SEQUENCE instructions. Sub-registers everywhere.

/jakob

I checked in LiveIntervals support to PHIElimination in r174831. I encountered all of the usual edge cases in 'make check', so hopefully it has no latent bugs.

I'll add a splitEdge() method to LiveIntervalAnalysis (got a better name?) that does things the slow way first, and then we can speed it up.

Cameron

I'll try doing that. Did you ever add a way to update LiveIntervals quickly after splitting an edge or will that have to finally be added? I can skip the critical edge splitting for now.

That doesn't exist yet, we'll need that too.

My thinking was to keep a list of all global live ranges in LiveIntervals so we at least don't have to go through all the local virtual registers when splitting a critical edge. (That's how LiveVariables is updated now, and it's slow).

I checked in LiveIntervals support to PHIElimination in r174831. I encountered all of the usual edge cases in 'make check', so hopefully it has no latent bugs.

Very cool. Thanks, Cameron.

I'll add a splitEdge() method to LiveIntervalAnalysis (got a better name?) that does things the slow way first, and then we can speed it up.

Sounds good.

/jakob