Mechanically replace LiveInterval* with LiveIntervalMap for intervals being
edited without actually using LiveIntervalMap functionality.

llvm-svn: 113816

Allow LiveIntervalMap to be reused by resetting the current live interval.

llvm-svn: 113815

Let's just declare that it is impossible to construct a std::pair from a null
pointer and work around that.

llvm-svn: 113788

Fix the msvc 2010 build.

The Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01
implements parts of C++0x based on the draft standard. An old version of
the draft had a bug that m

Fix the msvc 2010 build.

The Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01
implements parts of C++0x based on the draft standard. An old version of
the draft had a bug that makes std::pair<T1*, T2*>(something, 0) fail to
compile. This is because the template<class U, class V> pair(U&& x, V&& y)
constructor is selected, even though it later fails to implicitly convert
U and V to frist_type and second_type.

This has been fixed in n3090, but it seems that Microsoft is not going to
update msvc.

llvm-svn: 111535

show more ...

Thinking about it, we don't need MachineDominatorTree after all. The DomValue
map discovers the iterated dominance frontier for free.

llvm-svn: 111400

Revert r111394. It was too aggressive.

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

Revert r111394. It was too aggressive.

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

show more ...

Aggressively prune the DFS when inserting phi-defs.

llvm-svn: 111394

Add the LiveIntervalMap class. Don't hook it up yet.

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 pr

Add the LiveIntervalMap class. Don't hook it up yet.

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

show more ...

Clean up the Spiller.h interface.

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

Replace std::vector with SmallVector

Clean up the Spiller.h interface.

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

show more ...

Implement splitting inside a single block.

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 af

Implement splitting inside a single block.

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

show more ...

Let LiveInterval::addRange extend existing ranges, it will verify that value
numbers match. The old check could accidentally leave holes in openli.

Also let useIntv add all ranges for the phi-def va

Let LiveInterval::addRange extend existing ranges, it will verify that value
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

show more ...

Remember to actually update SplitAnalysis statistics now that we have a fancy
function to do it.

llvm-svn: 110994

Handle an empty dupli.

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 i

Handle an empty dupli.

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

show more ...

Update the SplitAnalysis statistics as uses are moved from curli to the new
split intervals. THis means the analysis can be used for multiple splits as long
as curli doesn't shrink.

llvm-svn: 110975

Also recompute HasPHIKill flags in LiveInterval::RenumberValues.

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

llvm-svn: 110949

Clean up debug output.

llvm-svn: 110940

Implement single block splitting.

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 sm

Implement single block splitting.

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

show more ...

More debug spew

llvm-svn: 110720

Implement register class inflation.

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

Implement register class inflation.

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

show more ...

Recalculate the spill weight and allocation hint for virtual registers created
during live range splitting.

llvm-svn: 110686

Lazily defer duplicating the live interval we are splitting until we know it is
necessary.

Sometimes, live range splitting doesn't shrink the current interval, but simply
changes some instructions t

Lazily defer duplicating the live interval we are splitting until we know it is
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

show more ...

Add LiveInterval::RenumberValues - Garbage collection for VNInfos.

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

Add LiveInterval::RenumberValues - Garbage collection for VNInfos.

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

show more ...

Fix swapped COPY operands.

llvm-svn: 110453

Checkpoint SplitKit progress.

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

Add SplitEditor to SplitKit. This class will be used to edit live intervals and
rewrite instructions for live range splitting.

Still work in progress.

llvm-svn: 109469