Insert copy after defining instruction.

Fix LiveIntervalMap::extendTo to properly handle live segments starting before
the current basic block.

Make sure the open live range is extended to the inserted copy's use slot.

llvm-svn: 115665

creating it before and subtracting split ranges.

This way, the SSA update code in LiveIntervalMap can properly create and use new
phi values in dupli. Now it is possible to create split regions where a value
escapes along two different CFG edges, creating phi values outside the split
region.

This is a work in progress and probably quite broken.

llvm-svn: 114492

great deal because we don't have to worry about maintaining SSA form.

Unconditionally copy back to dupli when the register is live out of the split
range, even if the live-out value was defined outside the range. Skipping the
back-copy only makes sense when the live range is going to spill outside the
split range, and we don't know that it will. Besides, this was a hack to avoid
SSA update issues.

Clear up some confusion about the end point of a half-open LiveRange. Methinks
LiveRanges need to be closed so both start and end are included in the range.
The low bits of a SlotIndex are symbolic, so a half-open range doesn't really
make sense. This would be a pervasive change, though.

llvm-svn: 114043

edited without actually using LiveIntervalMap functionality.

llvm-svn: 113816

llvm-svn: 113815

map discovers the iterated dominance frontier for free.

llvm-svn: 111400

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

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

llvm-svn: 110975

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

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

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