Spill multiple registers at once.

Live range splitting can create a number of small live ranges containing only a
single real use. Spill these small live ranges along with the large range they
are c

Spill multiple registers at once.

Live range splitting can create a number of small live ranges containing only a
single real use. Spill these small live ranges along with the large range they
are connected to with copies. This enables memory operand folding and maximizes
the spill to fill distance.

Work in progress with known bugs.

llvm-svn: 127529

show more ...

Change the Spiller interface to take a LiveRangeEdit reference.

This makes it possible to register delegates and get callbacks when the spiller
edits live ranges.

llvm-svn: 127389

Make SpillIs an optional pointer. Avoid creating a bunch of temporary SmallVectors.

llvm-svn: 127388

Change the RAGreedy register assignment order so large live ranges are allocated first.

This is based on the observation that long live ranges are more difficult to
allocate, so there is a better ch

Change the RAGreedy register assignment order so large live ranges are allocated first.

This is based on the observation that long live ranges are more difficult to
allocate, so there is a better chance of solving the puzzle by handling the big
pieces first. The allocator will evict and split long alive ranges when they get
in the way.

RABasic is still using spill weights for its priority queue, so the interface to
the queue has been virtualized.

llvm-svn: 126259

show more ...

Add VirtRegMap::rewrite() and use it in the new register allocators.

The rewriter works almost identically to -rewriter=trivial, except it also
eliminates any identity copies.

This makes the new re

Add VirtRegMap::rewrite() and use it in the new register allocators.

The rewriter works almost identically to -rewriter=trivial, except it also
eliminates any identity copies.

This makes the new register allocators independent of VirtRegRewriter.cpp which
will be going away at the same time as RegAllocLinearScan.

llvm-svn: 125967

show more ...

Trim debugging output.

llvm-svn: 125802

Add basic register allocator statistics.

llvm-svn: 125789

Evict a lighter single interference before attempting to split a live range.

Registers are not allocated strictly in spill weight order when live range
splitting and spilling has created new shorter

Evict a lighter single interference before attempting to split a live range.

Registers are not allocated strictly in spill weight order when live range
splitting and spilling has created new shorter intervals with higher spill
weights.

When one of the new heavy intervals conflicts with a single lighter interval,
simply evict the old interval instead of trying to split the heavy one.

The lighter interval is a better candidate for splitting, it has a smaller use
density.

llvm-svn: 125151

show more ...

Pass a Banner argument to the machine code verifier both from
createMachineVerifierPass and MachineFunction::verify.

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

Pass a Banner argument to the machine code verifier both from
createMachineVerifierPass and MachineFunction::verify.

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

llvm-svn: 122113

show more ...

Make the -verify-regalloc command line option available to base classes as
RegAllocBase::VerifyEnabled.

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

llvm-svn: 12

Make the -verify-regalloc command line option available to base classes as
RegAllocBase::VerifyEnabled.

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

llvm-svn: 122107

show more ...

Simplyfy RegAllocBasic by using getOverlaps instead of getAliasSet.

llvm-svn: 121801

Use TRI::printReg instead of AbstractRegisterDescription when printing
LiveIntervalUnions.

llvm-svn: 121781

Add named timer groups for the different stages of register allocation.

llvm-svn: 121604

Move MRI into RegAllocBase. Clean up debug output a bit.

llvm-svn: 121599

Added register reassignment prototype to RAGreedy. It's a simple
heuristic to reshuffle register assignments when we can't find an
available reg.

llvm-svn: 121388

Store (priority,regnum) pairs in the priority queue instead of providing an
abstract priority queue interface in subclasses that want to override the
priority calculations.

Subclasses must provide a

Store (priority,regnum) pairs in the priority queue instead of providing an
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

show more ...

Move RABasic::addMBBLiveIns to the base class, it is generally useful.

Minor optimization to the use of IntervalMap iterators. They are fairly
heavyweight, so prefer SI.valid() over SI != end().

ll

Move RABasic::addMBBLiveIns to the base class, it is generally useful.

Minor optimization to the use of IntervalMap iterators. They are fairly
heavyweight, so prefer SI.valid() over SI != end().

llvm-svn: 121217

show more ...

Switch LiveIntervalUnion from std::set to IntervalMap.

This speeds up RegAllocBasic by 20%, not counting releaseMemory which becomes
way faster.

llvm-svn: 121201

Simplify assertion.

llvm-svn: 121162

Coding style. No significant functionality. Abandon linear scan style
in favor of the widespread llvm style. Capitalize variables and add
newlines for visual parsing. Rename variables for readability

Coding style. No significant functionality. Abandon linear scan style
in favor of the widespread llvm style. Capitalize variables and add
newlines for visual parsing. Rename variables for readability.
And other cleanup.

llvm-svn: 120490

show more ...

Namespacify.

llvm-svn: 120146

RABasic fix. Regalloc is responsible for updating block live ins.

llvm-svn: 119896

Whitespace.

llvm-svn: 119895

Check TRI->getReservedRegs because other allocators do it. Even though
it makes no sense for allocation_order iterators to visit reserved regs.
The inline spiller depends on AliasAnalysis.
Manage the

Check TRI->getReservedRegs because other allocators do it. Even though
it makes no sense for allocation_order iterators to visit reserved regs.
The inline spiller depends on AliasAnalysis.
Manage the Query state to avoid uninitialized or stale results.

llvm-svn: 118800

show more ...

RABasic is nearly functionally complete. There are a few remaining
benchmarks hitting an assertion.
Adds LiveIntervalUnion::collectInterferingVRegs.
Fixes "late spilling" by checking for any unspilla

RABasic is nearly functionally complete. There are a few remaining
benchmarks hitting an assertion.
Adds LiveIntervalUnion::collectInterferingVRegs.
Fixes "late spilling" by checking for any unspillable live vregs among
all physReg aliases.

llvm-svn: 118701

show more ...