llvm dev - Sep 2011 - [LLVMdev] Linear scan is going away after 3.0

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

This is very, very cool. Thanks for all you've done w/ this stuff, Jakob.
Fantastic work.

-Jim

On Sep 16, 2011, at 10:06 AM, Jakob Stoklund Olesen wrote:
> 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
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev