Track new virtual registers by register number.

Track new virtual registers by register number, rather than by the live
interval created for them. This is the first step in separating the
creation o

Track new virtual registers by register number.

Track new virtual registers by register number, rather than by the live
interval created for them. This is the first step in separating the
creation of new virtual registers and new live intervals. Eventually
live intervals will be created and populated on demand after the virtual
registers have been created and used in instructions.

llvm-svn: 188434

show more ...

Remove unnecessary parameter to RenumberValues.

Patch by Matthias Braun!

llvm-svn: 188393

Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.

The main advantages here are way better heuristics, taking into account not
just loop depth but also __builtin_expect a

Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.

The main advantages here are way better heuristics, taking into account not
just loop depth but also __builtin_expect and other static heuristics and will
eventually learn how to use profile info. Most of the work in this patch is
pushing the MachineBlockFrequencyInfo analysis into the right places.

This is good for a 5% speedup on zlib's deflate (x86_64), there were some very
unfortunate spilling decisions in its hottest loop in longest_match(). Other
benchmarks I tried were mostly neutral.

This changes register allocation in subtle ways, update the tests for it.
2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction
it looked for was gone already (but the FileCheck pattern picked up unrelated
stuff).

llvm-svn: 184105

show more ...

Make the LiveRegMatrix analysis available to targets.

No functional change, just moved header files.

Targets can inject custom passes between register allocation and
rewriting. This makes it possib

Make the LiveRegMatrix analysis available to targets.

No functional change, just moved header files.

Targets can inject custom passes between register allocation and
rewriting. This makes it possible to tweak the register allocation
before rewriting, using the full global interference checking available
from LiveRegMatrix.

llvm-svn: 168806

show more ...

Release build: guard dump functions with
"#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)"

No functional change. Update r163339.

llvm-svn: 163653

Release build: guard dump functions with "ifndef NDEBUG"

No functional change.

llvm-svn: 163339

Fix a couple of loops that were processing unused value numbers.

Unused VNInfos should be left alone. Their def SlotIndex doesn't point
to anything.

llvm-svn: 161257

Eliminate the IS_PHI_DEF flag and VNInfo::setIsPHIDef().

A value number is a PHI def if and only if it begins at a block
boundary. This can be derived from the def slot, a separate flag is not
neces

Eliminate the IS_PHI_DEF flag and VNInfo::setIsPHIDef().

A value number is a PHI def if and only if it begins at a block
boundary. This can be derived from the def slot, a separate flag is not
necessary.

llvm-svn: 160893

show more ...

Pass context pointers to LiveRangeCalc::reset().

Remove the same pointers from all the other LiveRangeCalc functions,
simplifying the interface.

llvm-svn: 157941

Moved LiveRangeEdit.h so that it can be called from other parts of the backend, not just libCodeGen

llvm-svn: 153906

Refactored the LiveRangeEdit interface so that MachineFunction, TargetInstrInfo, MachineRegisterInfo, LiveIntervals, and VirtRegMap are all passed into the constructor and stored as members instead o

Refactored the LiveRangeEdit interface so that MachineFunction, TargetInstrInfo, MachineRegisterInfo, LiveIntervals, and VirtRegMap are all passed into the constructor and stored as members instead of passed in to each method.

llvm-svn: 153903

show more ...

Don't store COPY pointers in VNInfo.

If a value is defined by a COPY, that instuction can easily and cheaply
be found by getInstructionFromIndex(VNI->def).

This reduces the size of VNInfo from 24 t

Don't store COPY pointers in VNInfo.

If a value is defined by a COPY, that instuction can easily and cheaply
be found by getInstructionFromIndex(VNI->def).

This reduces the size of VNInfo from 24 to 16 bytes, and improves
llc compile time by 3%.

llvm-svn: 149763

show more ...

More dead code removal (using -Wunreachable-code)

llvm-svn: 148578

Detect when a value is undefined on an edge to a landing pad.

Consider this code:

int h() {
int x;
try {
x = f();
g();
} catch (...) {
return x+1;
}
return x;
}

The variable

Detect when a value is undefined on an edge to a landing pad.

Consider this code:

int h() {
int x;
try {
x = f();
g();
} catch (...) {
return x+1;
}
return x;
}

The variable x is undefined on the first edge to the landing pad, but it
has the f() return value on the second edge to the landing pad.

SplitAnalysis::getLastSplitPoint() would assume that the return value
from f() was live into the landing pad when f() throws, which is of
course impossible.

Detect these cases, and treat them as if the landing pad wasn't there.
This allows spill code to be inserted after the function call to f().

<rdar://problem/10664933>

llvm-svn: 147912

show more ...

Exclusively use SplitAnalysis::getLastSplitPoint().

Delete the alternative implementation in LiveIntervalAnalysis.

These functions computed the same thing, but SplitAnalysis caches the
result.

llv

Exclusively use SplitAnalysis::getLastSplitPoint().

Delete the alternative implementation in LiveIntervalAnalysis.

These functions computed the same thing, but SplitAnalysis caches the
result.

llvm-svn: 147911

show more ...

Add bundle aware API for querying instruction properties and switch the code
generator to it. For non-bundle instructions, these behave exactly the same
as the MC layer API.

For properties like mayL

Add bundle aware API for querying instruction properties and switch the code
generator to it. For non-bundle instructions, these behave exactly the same
as the MC layer API.

For properties like mayLoad / mayStore, look into the bundle and if any of the
bundled instructions has the property it would return true.
For properties like isPredicable, only return true if *all* of the bundled
instructions have the property.
For properties like canFoldAsLoad, isCompare, conservatively return false for
bundles.

llvm-svn: 146026

show more ...

Use getVNInfoBefore() when it makes sense.

llvm-svn: 144517

Terminate all dead defs at the dead slot instead of the 'next' slot.

This makes no difference for normal defs, but early clobber dead defs
now look like:

[Slot_EarlyClobber; Slot_Dead)

instead o

Terminate all dead defs at the dead slot instead of the 'next' slot.

This makes no difference for normal defs, but early clobber dead defs
now look like:

[Slot_EarlyClobber; Slot_Dead)

instead of:

[Slot_EarlyClobber; Slot_Register).

Live ranges for normal dead defs look like:

[Slot_Register; Slot_Dead)

as before.

llvm-svn: 144512

show more ...

Rename SlotIndexes to match how they are used.

The old naming scheme (load/use/def/store) can be traced back to an old
linear scan article, but the names don't match how slots are actually
used.

Th

Rename SlotIndexes to match how they are used.

The old naming scheme (load/use/def/store) can be traced back to an old
linear scan article, but the names don't match how slots are actually
used.

The load and store slots are not needed after the deferred spill code
insertion framework was deleted.

The use and def slots don't make any sense because we are using
half-open intervals as is customary in C code, but the names suggest
closed intervals. In reality, these slots were used to distinguish
early-clobber defs from normal defs.

The new naming scheme also has 4 slots, but the names match how the
slots are really used. This is a purely mechanical renaming, but some
of the code makes a lot more sense now.

llvm-svn: 144503

show more ...

Spill mode: Hoist back-copies locally.

The leaveIntvAfter() function normally inserts a back-copy after the
requested instruction, making the back-copy kill the live range.

In spill mode, try to in

Spill mode: Hoist back-copies locally.

The leaveIntvAfter() function normally inserts a back-copy after the
requested instruction, making the back-copy kill the live range.

In spill mode, try to insert the back-copy before the last use instead.
That means the last use becomes the kill instead of the back-copy. This
lowers the register pressure because the last use can now redefine the
same register it was reading.

This will also improve compile time: The back-copy isn't a kill, so
hoisting it in hoistCopiesForSize() won't force a recomputation of the
source live range. Similarly, if the back-copy isn't hoisted by the
splitter, the spiller will not attempt hoisting it locally.

llvm-svn: 139883

show more ...

Hoist back-copies to the least busy dominator.

When a back-copy is hoisted to the nearest common dominator, keep
looking up the dominator tree for a less loopy dominator, and place the
back-copy the

Hoist back-copies to the least busy dominator.

When a back-copy is hoisted to the nearest common dominator, keep
looking up the dominator tree for a less loopy dominator, and place the
back-copy there instead.

Don't do this when a single existing back-copy dominates all the others.
Assume the client knows what he is doing, and keep the dominating
back-copy.

This prevents us from hoisting back-copies into loops in most cases. If
a value is defined in a loop with multiple exits, we may still hoist
back-copies into that loop. That is the speed/size tradeoff.

llvm-svn: 139698

show more ...

Distinguish complex mapped values from forced recomputation.

When a ParentVNI maps to multiple defs in a new interval, its live range
may still be derived directly from RegAssign by transferValues()

Distinguish complex mapped values from forced recomputation.

When a ParentVNI maps to multiple defs in a new interval, its live range
may still be derived directly from RegAssign by transferValues().

On the other hand, when instructions have been rematerialized or
hoisted, it may be necessary to completely recompute live ranges using
LiveRangeCalc::extend() to all uses.

Use a bit in the value map to indicate that a live range must be
recomputed. Rename markComplexMapped() to forceRecompute().

This fixes some live range verification errors when
-split-spill-mode=size hoists back-copies by recomputing source ranges
when RegAssign kills can't be moved.

llvm-svn: 139660

show more ...

Implement -split-spill-mode=size.

Whenever the complement interval is defined by multiple copies of the
same value, hoist those back-copies to the nearest common dominator.

This ensures that at mos

Implement -split-spill-mode=size.

Whenever the complement interval is defined by multiple copies of the
same value, hoist those back-copies to the nearest common dominator.

This ensures that at most one copy is inserted per value in the
complement inteval, and no phi-defs are needed.

llvm-svn: 139651

show more ...

Add SplitEditor::markOverlappedComplement().

This function is used to flag values where the complement interval may
overlap other intervals. Call it from overlapIntv, and use the flag to
fully reco

Add SplitEditor::markOverlappedComplement().

This function is used to flag values where the complement interval may
overlap other intervals. Call it from overlapIntv, and use the flag to
fully recompute those live ranges in transferValues().

llvm-svn: 139612

show more ...

Eliminate the extendRange() wrapper.

llvm-svn: 139608