[LLVMdev] Deleting LiveVariables

[Jakob Stoklund Olesen]

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