When the live range is live through a block that doesn't use the register, but
that has interference, region splitting wants to split at the top and bottom of
the basic block.

llvm-svn: 124839

llvm-svn: 124815

These end points come from the inserted copies, and can be passed directly to
useIntv. This simplifies the coloring code.

llvm-svn: 124799

llvm-svn: 124779

llvm-svn: 124778

The greedy register allocator revealed some problems with the value mapping in
SplitKit. We would sometimes start mapping values before all defs were known,
and that could change a value from a simple 1-1 mapping to a multi-def mapping
that requires ssa update.

The new approach collects all defs and register assignments first without
filling in any live intervals. Only when finish() is called, do we compute
liveness and mapped values. At this time we know with certainty which values map
to multiple values in a split range.

This also has the advantage that we can compute live ranges based on the
remaining uses after rematerializing at split points.

The current implementation has many opportunities for compile time optimization.

llvm-svn: 124765

The value mapping gets confused about which original values have multiple new
definitions so they may need phi insertions.

This could probably be simplified by letting enterIntvBefore() take a live range
to be added following the instruction. As long as the range stays inside the
same basic block, value mapping shouldn't be a problem.

llvm-svn: 123926

interval after an instruction. The leaveIntvAfter() method only adds liveness
from the instruction's boundary index to the inserted copy.

Ideally, SplitKit should be smarter about this, perhaps by combining useIntv()
and leaveIntvAfter() into one method that guarantees continuity.

llvm-svn: 123858

Region splitting includes loop splitting as a subset, and it is more generic.
The splitting heuristics for variables that are live in more than one block are
now:

1. Try to create a region that covers multiple basic blocks.
2. Try to create a new live range for each block with multiple uses.
3. Spill.

Steps 2 and 3 are similar to what the standard spiller is doing.

llvm-svn: 123853

Analyze the live range's behavior entering and leaving basic blocks. Compute an
interference pattern for each allocation candidate, and use SpillPlacement to
find an optimal region where that register can be live.

This code is still not enabled.

llvm-svn: 123774

in this function, but the compiler was warning that it might be when
doing a release build.

llvm-svn: 122595

pick the victim with the lowest total spill weight.

llvm-svn: 122445

llvm-svn: 122132

  lib/CodeGen/RegAllocGreedy.cpp:311: error: unused variable 'PhysReg' [-Wunused-variable]

llvm-svn: 122122

createMachineVerifierPass and MachineFunction::verify.

The banner is printed before the machine code dump, just like the printer pass.

llvm-svn: 122113

RegAllocBase::VerifyEnabled.

Run the machine code verifier in a few interesting places during RegAllocGreedy.

llvm-svn: 122107

The heuristics split around the largest loop where the current register may be
allocated without interference.

llvm-svn: 122106

live range splitting around loops guided by register pressure.

So far, trySplit() simply prints a lot of debug output.

llvm-svn: 121918

llvm-svn: 121807

warning in the opt build.

llvm-svn: 121791

llvm-svn: 121783

llvm-svn: 121774

llvm-svn: 121741

spill weight. Filter out fixed registers instead.

Add support for reassigning an interference that was assigned to an alias.

llvm-svn: 121737

llvm-svn: 121736

llvm-svn: 121604

llvm-svn: 121599

Fix build breakage.

llvm-svn: 121596

lib/CodeGen/RegAllocGreedy.cpp:233: error: unused variable 'TRC' [-Wunused-variable]

llvm-svn: 121594

Soon, RegAllocGreedy will start splitting live ranges, and then deferred
spilling won't work anyway.

llvm-svn: 121591

llvm-svn: 121584

interference check.

llvm-svn: 121519

llvm-svn: 121411

heuristic to reshuffle register assignments when we can't find an
available reg.

llvm-svn: 121388

llvm-svn: 121319

The hint is simply tried first and then forgotten if it couldn't be allocated
immediately.

llvm-svn: 121306

abstract priority queue interface in subclasses that want to override the
priority calculations.

Subclasses must provide a getPriority() implementation instead.

This approach requires less code as long as priorities are expressable as simple
floats, and it avoids the dangers of defining potentially expensive priority
comparison functions.

It also should speed up priority_queue operations since they no longer have to
chase pointers when comparing registers. This is not measurable, though.

Preferably, we shouldn't use floats to guide code generation. The use of floats
here is derived from the use of floats for spill weights. Spill weights have a
dynamic range that doesn't lend itself easily to a fixpoint implementation.

When someone invents a stable spill weight representation, it can be reused for
allocation priorities.

llvm-svn: 121294

llvm-svn: 121283

This new register allocator is initially identical to RegAllocBasic, but it will
receive all of the tricks that RegAllocBasic won't get.

RegAllocGreedy will eventually replace linear scan.

llvm-svn: 121234