Move calcLiveBlockInfo() and the BlockInfo struct into SplitAnalysis.

No functional changes intended.

llvm-svn: 125231

Ignore <undef> uses when analyzing and rewriting.

llvm-svn: 125226

Add SplitEditor::overlapIntv() to create small ranges where both registers are live.

If a live range is used by a terminator instruction, and that live range needs
to leave the block on the stack or

Add SplitEditor::overlapIntv() to create small ranges where both registers are live.

If a live range is used by a terminator instruction, and that live range needs
to leave the block on the stack or in a different register, it can be necessary
to have both sides of the split live at the terminator instruction.

Example:

%vreg2 = COPY %vreg1
JMP %vreg1

Becomes after spilling %vreg2:

SPILL %vreg1
JMP %vreg1

The spill doesn't kill the register as is normally the case.

llvm-svn: 125102

show more ...

Add assertion.

llvm-svn: 125101

Add LiveIntervals::getLastSplitPoint().

A live range cannot be split everywhere in a basic block. A split must go before
the first terminator, and if the variable is live into a landing pad, the spl

Add LiveIntervals::getLastSplitPoint().

A live range cannot be split everywhere in a basic block. A split must go before
the first terminator, and if the variable is live into a landing pad, the split
must happen before the call that can throw.

llvm-svn: 124894

show more ...

Skip unused values.

llvm-svn: 124842

Add debug output and asserts to the phi-connecting code.

llvm-svn: 124813

Fix coloring bug when mapping values in the middle of a live-through block.

If the found value is not live-through the block, we should only add liveness up
to the requested slot index. When the val

Fix coloring bug when mapping values in the middle of a live-through block.

If the found value is not live-through the block, we should only add liveness up
to the requested slot index. When the value is live-through, the whole block
should be colored.

Bug found by SSA verification in the machine code verifier.

llvm-svn: 124812

show more ...

Return live range end points from SplitEditor::enter*/leave*.

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

llvm-svn: 124

Return live range end points from SplitEditor::enter*/leave*.

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

llvm-svn: 124799

show more ...

Reapply this.

llvm-svn: 124779

Temporarily revert 124765 in an attempt to find the cycle breaking bootstrap.

llvm-svn: 124778

Defer SplitKit value mapping until all defs are available.

The greedy register allocator revealed some problems with the value mapping in
SplitKit. We would sometimes start mapping values before all

Defer SplitKit value mapping until all defs are available.

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

show more ...

Rename member variables to follow the rest of LLVM.
No functional change.

llvm-svn: 124257

Add LiveIntervalMap::dumpCache() to print out the cache used by the ssa update algorithm.

llvm-svn: 123925

Implement RAGreedy::splitAroundRegion and remove loop splitting.

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

Implement RAGreedy::splitAroundRegion and remove loop splitting.

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

show more ...

Add RAGreedy methods for splitting live ranges around regions.

Analyze the live range's behavior entering and leaving basic blocks. Compute an
interference pattern for each allocation candidate, and

Add RAGreedy methods for splitting live ranges around regions.

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

show more ...

Turn the EdgeBundles class into a stand-alone machine CFG analysis pass.

The analysis will be needed by both the greedy register allocator and the
X86FloatingPoint pass. It only needs to be computed

Turn the EdgeBundles class into a stand-alone machine CFG analysis pass.

The analysis will be needed by both the greedy register allocator and the
X86FloatingPoint pass. It only needs to be computed once when the CFG doesn't
change.

This pass is very fast, usually showing up as 0.0% wall time.

llvm-svn: 122832

show more ...

Include a shadow of the original CFG edges in the edge bundle graph.

llvm-svn: 122444

Add EdgeBundles to SplitKit.

Edge bundles is an annotation on the CFG that turns it into a bipartite directed
graph where each basic block is connected to an outgoing and an ingoing bundle.
These bu

Add EdgeBundles to SplitKit.

Edge bundles is an annotation on the CFG that turns it into a bipartite directed
graph where each basic block is connected to an outgoing and an ingoing bundle.
These bundles are useful for identifying regions of the CFG for live range
splitting.

llvm-svn: 122301

show more ...

Check that the register is live-in to the loop header before inserting copies in
the loop predecessors.

The register can be live-out from a predecessor without being live-in to the
loop header if th

Check that the register is live-in to the loop header before inserting copies in
the loop predecessors.

The register can be live-out from a predecessor without being live-in to the
loop header if there is a critical edge from the predecessor.

llvm-svn: 122123

show more ...

Fix build.

llvm-svn: 121872

Detect and enumerate bypass loops.

Bypass loops have the current live range live through, but contain no uses or
defs. Splitting around a bypass loop can free registers for other uses inside
the loo

Detect and enumerate bypass loops.

Bypass loops have the current live range live through, but contain no uses or
defs. Splitting around a bypass loop can free registers for other uses inside
the loop by spilling the split range.

llvm-svn: 121871

show more ...

Separate SplitAnalysis::getSplitLoops().

This method returns the set of loops with uses that are candidates for
splitting.

llvm-svn: 121870

No need to add liveness that's already there.

llvm-svn: 118742

Basic rematerialization during splitting.

Whenever splitting wants to insert a copy, it checks if the value can be
rematerialized cheaply instead.

Missing features:
- Delete instructions when all u

Basic rematerialization during splitting.

Whenever splitting wants to insert a copy, it checks if the value can be
rematerialized cheaply instead.

Missing features:
- Delete instructions when all uses have been rematerialized.
- Truncate live ranges to the remaining uses after rematerialization.

llvm-svn: 118702

show more ...