[LLVMdev] Linear scan is going away after 3.0

[Jakob Stoklund Olesen]

I will be removing RegAllocLinearScan and VirtRegRewriter from trunk shortly after we cut the 3.0 release branch.

LLVM 3.0 will still ship with the linear scan register allocator, but the default will be the new greedy allocator.  Linear scan can be enabled by passing '-regalloc=linearscan -join-physregs' to llc.


RegAllocLinearScan and VirtRegRewriter need to go away soon because they are blocking some code cleanup efforts in the register allocation framework.  I will also be removing the StandardSpiller class from Spiller.cpp as well as the code it depends on in LiveIntervalAnalysis.

- Linear scan is using the deferred spill code insertion that StandardSpiller and VirtRegRewriter provides.  This was originally designed to cope with a static instruction numbering, but today's dynamic SlotIndexes can handle new instructions.  The new InlineSpiller inserts spill code immediately, and we can get rid of the deferred spill support.

- With deferred spill support out of the way, we can get rid of the mysterious LOAD and STORE slots in SlotIndexes.  The slot names come from an old linear scan paper that used inclusive interval end points.  LLVM uses C-style half-open intervals which adds to the confusion.  Slots will be renamed to:

  LOAD	-> Block, used for basic block boundaries only.
  USE	-> EarlyClobber, kill and def slot for early-clobber operands.
  DEF	-> Register, kill and def slot for normal register operands.
  STORE	-> Dead, kill slot for dead defs.

- Linear scan depends of physical register coalescing to generate good ABI code.  It has been disabled by default because RegAllocGreedy doesn't need it.  With linear scan gone, the code can be removed completely.  That will clean up RegisterCoalescer quite a bit.


If you are writing a new register allocator, use RABasic as a template.  This simple allocator doesn't use any of the obsolete code.  It uses InlineSpiller::spill() for spilling, and VirtRegMap::rewrite() for rewriting.  The new rewriter is very simple, the only optimization it performs is identity copy elimination.  It depends on the register allocator having split live ranges before spilling, so it doesn't try to undo anything like VirtRegRewriter does.

StandardSpiller supported basic per-block live range splitting.  Similar functionality using SplitKit can be found in RAGreedy::tryBlockSplit().

/jakob