We must complete the DFS, otherwise we might miss needed phi-defs, and
prematurely color live ranges with a non-dominating value.

This is not a big deal since we get to color more of the CFG and the next
mapValue call will be faster.

llvm-svn: 111397

llvm-svn: 111394

LiveIntervalMap maps values from a parent LiveInterval to a child interval that
is a strict subset. It will create phi-def values as needed to preserve the
VNInfo SSA form in the child interval.

This leads to an algorithm very similar to the one in SSAUpdaterImpl.h, but with
enough differences that the code can't be reused:

- We don't need to manipulate PHI instructions.
- LiveIntervals have kills.
- We have MachineDominatorTree.
- We can use df_iterator.

llvm-svn: 111393

The earliestStart argument is entirely specific to linear scan allocation, and
can be easily calculated by RegAllocLinearScan.

Replace std::vector with SmallVector.

llvm-svn: 111055

When a live range is contained a single block, we can split it around
instruction clusters. The current approach is very primitive, splitting before
and after the largest gap between uses.

llvm-svn: 111043

numbers match. The old check could accidentally leave holes in openli.

Also let useIntv add all ranges for the phi-def value inserted by
enterIntvAtEnd. This works as long at the value mapping is established in
enterIntvAtEnd.

llvm-svn: 110995

function to do it.

llvm-svn: 110994

This can happen if the original interval has been broken into two disconnected
parts. Ideally, we should be able to detect when the graph is disconnected and
create separate intervals, but that code is not implemented yet.

Example:

Two basic blocks are both branching to a loop header. Our interval is defined in
both basic blocks, and live into the loop along both edges.

We decide to split the interval around the loop. The interval is split into an
inside part and an outside part. The outside part now has two disconnected
segments, one in each basic block.

If we later decide to split the outside interval into single blocks, we get one
interval per basic block and an empty dupli for the remainder.

llvm-svn: 110976

split intervals. THis means the analysis can be used for multiple splits as long
as curli doesn't shrink.

llvm-svn: 110975

If a phi-def value were removed from the interval, the phi-kill flags are no
longer valid.

llvm-svn: 110949

llvm-svn: 110940

Before spilling a live range, we split it into a separate range for each basic
block where it is used. That way we only get one reload per basic block if the
new smaller ranges can allocate to a register.

This type of splitting is already present in the standard spiller.

llvm-svn: 110934

llvm-svn: 110720

When splitting a live range, the new registers have fewer uses and the
permissible register class may be less constrained. Recompute the register class
constraint from the uses of new registers created for a split. This may let them
be allocated from a larger set, possibly avoiding a spill.

llvm-svn: 110703

during live range splitting.

llvm-svn: 110686

necessary.

Sometimes, live range splitting doesn't shrink the current interval, but simply
changes some instructions to use a new interval. That makes the original more
suitable for spilling. In this case, we don't need to duplicate the original.

llvm-svn: 110481

After heavy editing of a live interval, it is much easier to simply renumber the
live values instead of trying to keep track of the unused ones.

llvm-svn: 110463

llvm-svn: 110453

We are now at a point where we can split around simple single-entry, single-exit
loops, although still with some bugs.

llvm-svn: 110257

rewrite instructions for live range splitting.

Still work in progress.

llvm-svn: 109469

The spillers can pluck the analyses they need from the pass reference.

Switch some never-null pointers to references.

llvm-svn: 108969

Determine which loop exit blocks need a 'pre-exit' block inserted.
Recognize when this would be impossible.

llvm-svn: 108941

llvm-svn: 108845

This is a work in progress. So far we have some basic loop analysis to help
determine where it is useful to split a live range around a loop.

The actual loop splitting code from Splitter.cpp is also going to move in here.

llvm-svn: 108842