llvm-svn: 126893

Extract the updateSSA() method from the too long extendRange().

LiveOutCache can be shared among all the new intervals since there is at most
one of the new ranges live out from each basic block.

llvm-svn: 126818

Simplify the signature - The return value and ParentVNI are no longer needed.

llvm-svn: 126809

This method could probably be used by LiveIntervalAnalysis::shrinkToUses, and
now it can use extendIntervalEndTo() which coalesces ranges.

llvm-svn: 126803

llvm-svn: 126801

The value map is currently not used, all values are 'complex mapped' and
LiveIntervalMap::mapValue is used to dig them out.

This is the first step in a series changes leading to the removal of
LiveIntervalMap. Its data structures can be shared among all the live intervals
created by a split, so it is wasteful to create a copy for each.

llvm-svn: 126800

Local live range splitting is better driven by interference. This code was just
guessing.

llvm-svn: 126799

No code will be inserted after the split point anyway.

llvm-svn: 126319

An original endpoint is an instruction that killed or defined the original live
range before any live ranges were split.

When splitting global live ranges, avoid creating local live ranges without any
original endpoints. We may still create global live ranges without original
endpoints, but such a range won't be split again, and live range splitting still
terminates.

llvm-svn: 126151

llvm-svn: 126005

llvm-svn: 126003

Loop splitting is better handled by the more generic global region splitting
based on the edge bundle graph.

llvm-svn: 125243

This fixes a bug where splitSingleBlocks() could split a live range after a
terminator instruction.

llvm-svn: 125237

No functional changes intended.

llvm-svn: 125231

llvm-svn: 125226

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

llvm-svn: 125101

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

llvm-svn: 124842

llvm-svn: 124813

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

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

No functional change.

llvm-svn: 124257

llvm-svn: 123925

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

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

llvm-svn: 122444

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

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

llvm-svn: 121872

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

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

llvm-svn: 121870

llvm-svn: 118742

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

llvm-svn: 118193

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