That's it, I am declaring this a failure of the C++03 STL.

There are too many compatibility problems with using mixed types in
std::upper_bound, and I don't want to spend 110 lines of boilerplate se

That's it, I am declaring this a failure of the C++03 STL.

There are too many compatibility problems with using mixed types in
std::upper_bound, and I don't want to spend 110 lines of boilerplate setting up
a call to a 10-line function. Binary search is not /that/ hard to implement
correctly.

I tried terminating the binary search with a linear search, but that actually
made the algorithm slower against my expectation. Most live intervals have less
than 4 segments. The early test against endIndex() does pay, and this version is
25% faster than plain std::upper_bound().

llvm-svn: 127522

show more ...

Fix use of CompEnd predicate to be standards conforming

The existing CompEnd predicate does not define a strict weak order as required
by the C++03 standard; therefore, its use as a predicate to std

Fix use of CompEnd predicate to be standards conforming

The existing CompEnd predicate does not define a strict weak order as required
by the C++03 standard; therefore, its use as a predicate to std::upper_bound
is invalid. For a discussion of this issue, see
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270

This patch replaces the asymmetrical comparison with an iterator adaptor that
achieves the same effect while being strictly standard-conforming by ensuring
an apples-to-apples comparison.

llvm-svn: 127462

show more ...

Fix the build for MSVC 9 whose upper_bound() wants to compare elements in the sorted array.

Patch by Olaf Krzikalla!

llvm-svn: 127264

Revert "Make a comparator's argument `const'. This fixes the build for
MSVC 9."

The "fix" was meaningless.

This reverts commit r127245.

llvm-svn: 127260

Make a comparator's argument `const'. This fixes the build for MSVC 9.

llvm-svn: 127245

Avoid comparing invalid slot indexes.

llvm-svn: 126922

Move LiveIntervalMap::extendTo into LiveInterval itself.

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

l

Move LiveIntervalMap::extendTo into LiveInterval itself.

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

llvm-svn: 126803

show more ...

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

Teach TargetRegisterInfo how to cram stack slot indexes in with the virtual and
physical register numbers.

This makes the hack used in LiveInterval official, and lets LiveInterval be
oblivious of st

Teach TargetRegisterInfo how to cram stack slot indexes in with the virtual and
physical register numbers.

This makes the hack used in LiveInterval official, and lets LiveInterval be
oblivious of stack slots.

The isPhysicalRegister() and isVirtualRegister() predicates don't know about
this, so when a variable may contain a stack slot, isStackSlot() should always
be tested first.

llvm-svn: 123128

show more ...

Replace TargetRegisterInfo::printReg with a PrintReg class that also works without a TRI instance.

Print virtual registers numbered from 0 instead of the arbitrary
FirstVirtualRegister. The first vi

Replace TargetRegisterInfo::printReg with a PrintReg class that also works without a TRI instance.

Print virtual registers numbered from 0 instead of the arbitrary
FirstVirtualRegister. The first virtual register is printed as %vreg0.
TRI::NoRegister is printed as %noreg.

llvm-svn: 123107

show more ...

Use IntEqClasses to compute connected components of live intervals.

llvm-svn: 122296

Fix PR8815 by checking for an explicit clobber def tied to a use operand in
ConnectedVNInfoEqClasses::Classify().

llvm-svn: 122202

Teach ConnectedVNInfoEqClasses::Classify to deal with unused values.

We don't want unused values forming their own equivalence classes, so we lump
them all together in one class, and then merge them

Teach ConnectedVNInfoEqClasses::Classify to deal with unused values.

We don't want unused values forming their own equivalence classes, so we lump
them all together in one class, and then merge them with the class of the last
used value.

llvm-svn: 117670

show more ...

Fix broken equivalence class calculation. We could probably also use
EquvivalenceClasses.h except it looks like overkill when elements are continuous
integers.

llvm-svn: 117631

Silence compiler warning.

llvm-svn: 116156

Classify value numbers into connected components in linear time.

llvm-svn: 116105

After splitting, the remaining LiveInterval may be fragmented into multiple
connected components. These components should be allocated different virtual
registers because there is no reason for them

After splitting, the remaining LiveInterval may be fragmented into multiple
connected components. These components should be allocated different virtual
registers because there is no reason for them to be allocated together.

Add the ConnectedVNInfoEqClasses class to calculate the connected components,
and move values to new LiveIntervals.

Use it from SplitKit::rewrite by creating new virtual registers for the
components.

llvm-svn: 116006

show more ...

Tweak VNInfo printing.

llvm-svn: 115650

Add assert for valid slot indexes.

llvm-svn: 115649

When RemoveCopyByCommutingDef is creating additional identity copies, just use
LiveInterval::MergeValueNumberInto instead of trying to extend LiveRanges and
getting it wrong.

This fixed PR8249 where

When RemoveCopyByCommutingDef is creating additional identity copies, just use
LiveInterval::MergeValueNumberInto instead of trying to extend LiveRanges and
getting it wrong.

This fixed PR8249 where a valno with a multi-segment live range was defined by
an identity copy created by RemoveCopyByCommutingDef. Some of the live
segments disappeared.

llvm-svn: 115385

show more ...

Removed VNInfo::isDefAccurate(). Def "accuracy" can be checked by testing whether LiveIntervals::getInstructionFromIndex(def) returns NULL.

llvm-svn: 114791

Refix MSVC9 and upper_bound. It actually needs a fully symmetric comparator.

llvm-svn: 114469

Don't pollute the global namespace.

llvm-svn: 114459

MSVC9 does not support upper_bound with an asymmetric comparator.

llvm-svn: 114455

Add LiveInterval::find and use it for most LiveRange searching operations
instead of calling lower_bound or upper_bound directly.

This cleans up the search logic a bit because {lower,upper}_bound co

Add LiveInterval::find and use it for most LiveRange searching operations
instead of calling lower_bound or upper_bound directly.

This cleans up the search logic a bit because {lower,upper}_bound compare
LR->start by default, and it is usually simpler to search LR->end.

Funnelling all searches through one function also makes it possible to replace
the search algorithm with something faster than binary search.

llvm-svn: 114448

show more ...