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

He said *before* the last split point.

This should unbreak the build-self-4-mingw32 tester. I have a very
complicated test case that I will try to clean up.

llvm-svn: 135329

Extract parts of RAGreedy::splitAroundRegion as SplitKit methods.

This gets rid of some of the gory splitting details in RAGreedy and
makes them available to future SplitKit clients.

Slightly gener

Extract parts of RAGreedy::splitAroundRegion as SplitKit methods.

This gets rid of some of the gory splitting details in RAGreedy and
makes them available to future SplitKit clients.

Slightly generalize the functionality to support multi-way splitting.
Specifically, SplitEditor::splitLiveThroughBlock() supports switching
between different register intervals in a block.

llvm-svn: 135307

show more ...

Reapply r134047 now that the world is ready for it.

This patch will sometimes choose live range split points next to
interference instead of always splitting next to a register point. That
means spi

Reapply r134047 now that the world is ready for it.

This patch will sometimes choose live range split points next to
interference instead of always splitting next to a register point. That
means spill code can now appear almost anywhere, and it was necessary
to fix code that didn't expect that.

The difficult places were:

- Between a CALL returning a value on the x87 stack and the
corresponding FpPOP_RETVAL (was FpGET_ST0). Probably also near x87
inline assembly, but that didn't actually show up in testing.

- Between a CALL popping arguments off the stack and the corresponding
ADJCALLSTACKUP.

Both are fixed now. The only place spill code can't appear is after
terminators, see SplitAnalysis::getLastSplitPoint.

Original commit message:

Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art.

This function has to deal with a lot of special cases, and the old
version got it wrong sometimes. In particular, it would sometimes leave
multiple uses in the stack interval in a single block. That causes bad
code with multiple reloads in the same basic block.

The new version handles block entry and exit in a single pass. It first
eliminates all the easy cases, and then goes on to create a local
interval for the blocks with difficult interference. Previously, we
would only create the local interval for completely isolated blocks.

It can happen that the stack interval becomes completely empty because
we could allocate a register in all edge bundles, and the new local
intervals deal with the interference. The empty stack interval is
harmless, but we need to remove a SplitKit assertion that checks for
empty intervals.

llvm-svn: 134125

show more ...

Revert r134047 while investigating a llvm-gcc-i386-linux-selfhost
miscompile.

llvm-svn: 134053

Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art.

This function has to deal with a lot of special cases, and the old
version got it wrong sometimes. In particular, it would sometimes lea

Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art.

This function has to deal with a lot of special cases, and the old
version got it wrong sometimes. In particular, it would sometimes leave
multiple uses in the stack interval in a single block. That causes bad
code with multiple reloads in the same basic block.

The new version handles block entry and exit in a single pass. It first
eliminates all the easy cases, and then goes on to create a local
interval for the blocks with difficult interference. Previously, we
would only create the local interval for completely isolated blocks.

It can happen that the stack interval becomes completely empty because
we could allocate a register in all edge bundles, and the new local
intervals deal with the interference. The empty stack interval is
harmless, but we need to remove a SplitKit assertion that checks for
empty intervals.

llvm-svn: 134047

show more ...

Fix a bad iterator dereference that Evan uncovered.

llvm-svn: 133978

There is only one register coalescer. Merge it into the base class and
remove the analysis group.

llvm-svn: 133899

Reapply r132245 with a fix for the bug that broke the darwin9/i386 build.

llvm-svn: 132309

Revert r132245, "Create two BlockInfo entries when a live range is discontinuous through a block."

This commit seems to have broken a darwin 9 tester.

llvm-svn: 132299

Create two BlockInfo entries when a live range is discontinuous through a block.

Delete the Kill and Def markers in BlockInfo. They are no longer
necessary when BlockInfo describes a continuous live

Create two BlockInfo entries when a live range is discontinuous through a block.

Delete the Kill and Def markers in BlockInfo. They are no longer
necessary when BlockInfo describes a continuous live range.

This only affects the relatively rare kind of basic block where a live
range looks like this:

|---x o---|

Now live range splitting can pretend that it is looking at two blocks:

|---x
o---|

This allows the code to be simplified a bit.

llvm-svn: 132245

show more ...

Add SplitAnalysis::getNumLiveBlocks().

It is important that this function returns the same number of live blocks as
countLiveBlocks(CurLI) because live range splitting uses the number of live
blocks

Add SplitAnalysis::getNumLiveBlocks().

It is important that this function returns the same number of live blocks as
countLiveBlocks(CurLI) because live range splitting uses the number of live
blocks to ensure it is making progress.

This is in preparation of supporting duplicate UseBlock entries for basic blocks
that have a virtual register live-in and live-out, but not live-though.

llvm-svn: 132244

show more ...