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 ...

Tag debug output as regalloc

llvm-svn: 118193

When inserting copies during splitting, always use the parent register as the
source, and let rewrite() clean it up.

This way, kill flags on the inserted copies are fixed as well during rewrite().

When inserting copies during splitting, always use the parent register as the
source, and let rewrite() clean it up.

This way, kill flags on the inserted copies are fixed as well during rewrite().

We can't just assume that all the copies we insert are going to be kills since
critical edges into loop headers sometimes require both source and dest to be
live out of a block.

llvm-svn: 117980

show more ...

Update kill flags while rewriting instructions after splitting.

llvm-svn: 117959

Make sure copies are inserted after any exception handling labels at the top of
a basic block.

llvm-svn: 117764

Don't transfer unused values to the new intervals formed by splitting.

llvm-svn: 117673

Silence Release build warnings.

llvm-svn: 117671

Never propagate the idom value out of a block that defines its own value.

llvm-svn: 117669

Replace SplitKit SSA update with an iterative algorithm very similar to the one
in SSAUpdaterImpl.h

Verifying live intervals revealed that the old method was completely wrong, and
we need an iterati

Replace SplitKit SSA update with an iterative algorithm very similar to the one
in SSAUpdaterImpl.h

Verifying live intervals revealed that the old method was completely wrong, and
we need an iterative approach to calculating PHI placemant. Fortunately, we have
MachineDominators available, so we don't have to compute that over and over
like SSAUpdaterImpl.h must.

Live-out values are cached between calls to mapValue() and computed in a greedy
way, so most calls will be working with very small block sets.

Thanks to Bob for explaining how this should work.

llvm-svn: 117599

show more ...

Make MachineDominators available for SplitEditor. We are going to need it for
proper SSA updating.

This doesn't cause MachineDominators to be recomputed since we are already
requiring MachineLoopInf

Make MachineDominators available for SplitEditor. We are going to need it for
proper SSA updating.

This doesn't cause MachineDominators to be recomputed since we are already
requiring MachineLoopInfo which uses dominators as well.

llvm-svn: 117598

show more ...

Handle critical loop predecessors by making both inside and outside registers
live out.

This doesn't prevent us from inserting a loop preheader later on, if that is
better.

llvm-svn: 117424

Compute critical loop predecessors in the same way as critical loop exits.

Critical edges going into a loop are not as bad as critical exits. We can handle
them by splitting the critical edge, or by

Compute critical loop predecessors in the same way as critical loop exits.

Critical edges going into a loop are not as bad as critical exits. We can handle
them by splitting the critical edge, or by having both inside and outside
registers live out of the predecessor.

llvm-svn: 117423

show more ...

After splitting, compute connected components of all new registers, not just for
the remainder register.

Example:

bb0:
x = 1
bb1:
use(x)
...
x = 2
jump bb1

When x is isolated in bb1, the

After splitting, compute connected components of all new registers, not just for
the remainder register.

Example:

bb0:
x = 1
bb1:
use(x)
...
x = 2
jump bb1

When x is isolated in bb1, the inner part breaks into two components, x1 and x2:

bb0:
x0 = 1
bb1:
x1 = x0
use(x1)
...
x2 = 2
x0 = x2
jump bb1

llvm-svn: 117408

show more ...

Call RenumberValues for all new registers created during splitting. This is
necessary to get correct hasPHIKill flags.

llvm-svn: 117406

Preserve PHIDef bits in cloned values during splitting.

llvm-svn: 117405