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

Switch extendInBlock() to take a kill slot instead of the last use slot.

Three out of four clients prefer this interface which is consistent with
extendIntervalEndTo() and LiveRangeCalc::extend().

Switch extendInBlock() to take a kill slot instead of the last use slot.

Three out of four clients prefer this interface which is consistent with
extendIntervalEndTo() and LiveRangeCalc::extend().

llvm-svn: 139604

show more ...

Use a separate LiveRangeCalc for the complement in spill modes.

The complement interval may overlap the other intervals created, so use
a separate LiveRangeCalc instance to compute its live range.

Use a separate LiveRangeCalc for the complement in spill modes.

The complement interval may overlap the other intervals created, so use
a separate LiveRangeCalc instance to compute its live range.

A LiveRangeCalc instance can only be shared among non-overlapping
intervals.

llvm-svn: 139603

show more ...

Extract live range calculations from SplitKit.

SplitKit will soon need two copies of these data structures, and the
algorithms will also be useful when LiveIntervalAnalysis becomes
independent of Li

Extract live range calculations from SplitKit.

SplitKit will soon need two copies of these data structures, and the
algorithms will also be useful when LiveIntervalAnalysis becomes
independent of LiveVariables.

llvm-svn: 139572

show more ...

Add an interface for SplitKit complement spill modes.

SplitKit always computes a complement live range to cover the places
where the original live range was live, but no explicit region has been
all

Add an interface for SplitKit complement spill modes.

SplitKit always computes a complement live range to cover the places
where the original live range was live, but no explicit region has been
allocated.

Currently, the complement live range is created to be as small as
possible - it never overlaps any of the regions. This minimizes
register pressure, but if the complement is going to be spilled anyway,
that is not very important. The spiller will eliminate redundant
spills, and hoist others by making the spill slot live range overlap
some of the regions created by splitting. Stack slots are cheap.

This patch adds the interface to enable spill modes in SplitKit. In
spill mode, SplitKit will assume that the complement is going to spill,
so it will allow it to overlap regions in order to avoid back-copies.
By doing some of the spiller's work early, the complement live range
becomes simpler. In some cases, it can become much simpler because no
extra PHI-defs are required. This will speed up both splitting and
spilling.

This is only the interface to enable spill modes, no implementation yet.

llvm-svn: 139500

show more ...

Delete getMultiUseBlocks and splitSingleBlocks.

These functions are no longer used, and they are easily replaced with a
loop calling shouldSplitSingleBlock and splitSingleBlock.

llvm-svn: 136993

Split around single instructions to enable register class inflation.

Normally, we don't create a live range for a single instruction in a
basic block, the spiller does that anyway. However, when spl

Split around single instructions to enable register class inflation.

Normally, we don't create a live range for a single instruction in a
basic block, the spiller does that anyway. However, when splitting a
live range that belongs to a proper register sub-class, inserting these
extra COPY instructions completely remove the constraints from the
remainder interval, and it may be allocated from the larger super-class.

The spiller will mop up these small live ranges if we end up spilling
anyway. It calls them snippets.

llvm-svn: 136989

show more ...

Rename {First,Last}Use to {First,Last}Instr.

With a 'FirstDef' field right there, it is very confusing that FirstUse
refers to an instruction that may be a def.

llvm-svn: 136739

Add a BlockInfo::FirstDef field.

This is either an invalid SlotIndex, or valno->def for the first value
defined inside the block. PHI values are not counted as defined inside
the block.

The FirstDe

Add a BlockInfo::FirstDef field.

This is either an invalid SlotIndex, or valno->def for the first value
defined inside the block. PHI values are not counted as defined inside
the block.

The FirstDef field will be used when estimating the cost of spilling
around a block.

llvm-svn: 136736

show more ...

Delete BlockInfo::LiveThrough. It wasn't used any more.

llvm-svn: 136735

Never extend live ranges for <undef> uses.

llvm-svn: 135886

Correctly handle <undef> tied uses when rewriting after a split.

This fixes PR10463. A two-address instruction with an <undef> use
operand was incorrectly rewritten so the def and use no longer used

Correctly handle <undef> tied uses when rewriting after a split.

This fixes PR10463. A two-address instruction with an <undef> use
operand was incorrectly rewritten so the def and use no longer used the
same register, violating the tie constraint.

Fix this by always rewriting <undef> operands with the register a def
operand would use.

llvm-svn: 135885

show more ...

Fix bug in SplitEditor::splitLiveThroughBlock when switching registers.

If there is no interference and no last split point, we cannot
enterIntvBefore(Stop) - that function needs a real instruction.

Fix bug in SplitEditor::splitLiveThroughBlock when switching registers.

If there is no interference and no last split point, we cannot
enterIntvBefore(Stop) - that function needs a real instruction.

Use enterIntvAtEnd instead for that very easy case.

This code doesn't currently run, it is needed by multi-way splitting.

llvm-svn: 135846

show more ...

Fix a crash when building 177.mesa for armv6.

When splitting a live range immediately before an LDR_POST instruction
that redefines the address register, make sure to use the correct value
number in

Fix a crash when building 177.mesa for armv6.

When splitting a live range immediately before an LDR_POST instruction
that redefines the address register, make sure to use the correct value
number in leaveIntvBefore.

We need the value number entering the instruction.

<rdar://problem/9793765>

llvm-svn: 135413

show more ...

Silence unused variable warning

llvm-svn: 135339