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

EquvivalenceClasses.h except it looks like overkill when elements are continuous
integers.

llvm-svn: 117631

llvm-svn: 116156

llvm-svn: 116105

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

llvm-svn: 115650

llvm-svn: 115649

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

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

llvm-svn: 114791

llvm-svn: 114469

llvm-svn: 114459

llvm-svn: 114455

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

llvm-svn: 114447

llvm-svn: 113386

Clobber ranges are no longer used when joining physical registers.
Instead, all aliases are checked for interference.

llvm-svn: 113084

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

llvm-svn: 110949

llvm-svn: 110944

register at a time. This turns out to be slightly faster than iterating over
instructions, but more importantly, it allows us to compute spill weights for
new registers created after the spill weight pass has run.

Also compute the allocation hint at the same time as the spill weight. This
allows us to use the spill weight as a cost metric for copies, and choose the
most profitable hint if there is more than one possibility.

The new hints provide a very small (< 0.1%) but universal code size improvement.

llvm-svn: 110631

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

Fixes potential ambiguity problems on VS 2010.

Patch by nobled!

llvm-svn: 110029

llvm-svn: 109388

llvm-svn: 108277

LiveInterval::overlapsFrom dereferences end() if it is called on an empty
interval.

It would be reasonable to just return false - an empty interval doesn't overlap
anything, but I want to know who is doing it first.

llvm-svn: 108264

Also, one binary search is enough.

llvm-svn: 108261

llvm-svn: 107127

The VNInfo.kills vector was almost unused except for all the code keeping it
updated. The few places using it were easily rewritten to check for interval
ends instead.

The two new methods LiveInterval::killedAt and killedInRange are replacements.

This brings us down to 3 independent data structures tracking kills.

llvm-svn: 106905

This fixes PR7479 and PR7485. The test cases from those PRs are big, so not
included. However, PR7485 comes from self hosting on FreeBSD, so we will surely
hear about any regression.

llvm-svn: 106811

llvm-svn: 106627

only a single type of object to be allocated. Use it to make VNInfo destruction
typesafe.

llvm-svn: 99919

llvm-svn: 99895

llvm-svn: 99883

llvm-svn: 93261

Change errs() to dbgs().

llvm-svn: 92528

When a call is placed to spill an interval this spiller will first try to
break the interval up into its component values. Single value intervals and
intervals which have already been split (or are the result of previous splits)
are spilled by the default spiller.

Splitting intervals as described above may improve the performance of generated
code in some circumstances. This work is experimental however, and it still
miscompiles many benchmarks. It's not recommended for general use yet.

llvm-svn: 90951

This introduces a new pass, SlotIndexes, which is responsible for numbering
instructions for register allocation (and other clients). SlotIndexes numbering
is designed to match the existing scheme, so this patch should not cause any
changes in the generated code.

For consistency, and to avoid naming confusion, LiveIndex has been renamed
SlotIndex.

The processImplicitDefs method of the LiveIntervals analysis has been moved
into its own pass so that it can be run prior to SlotIndexes. This was
necessary to match the existing numbering scheme.

llvm-svn: 85979

llvm-svn: 83255

llvm-svn: 83254

llvm-svn: 81605

a new class, MachineInstrIndex, which hides arithmetic details from
most clients. This is a step towards allowing the register allocator
to update/insert code during allocation.

llvm-svn: 81040