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

Fix PR9883. Make sure all caches are invalidated when a live range is repaired.

The previous invalidation missed the alias interference caches.

Also add a stats counter for the number of repaired r

Fix PR9883. Make sure all caches are invalidated when a live range is repaired.

The previous invalidation missed the alias interference caches.

Also add a stats counter for the number of repaired ranges.

llvm-svn: 131133

show more ...

Add some statistics to the splitting and spilling frameworks.

llvm-svn: 130931

Gracefully handle invalid live ranges. Fix PR9831.

Register coalescing can sometimes create live ranges that end in the middle of a
basic block without any killing instruction. When SplitKit detects

Gracefully handle invalid live ranges. Fix PR9831.

Register coalescing can sometimes create live ranges that end in the middle of a
basic block without any killing instruction. When SplitKit detects this, it will
repair the live range by shrinking it to its uses.

Live range splitting also needs to know about this. When the range shrinks so
much that it becomes allocatable, live range splitting fails because it can't
find a good split point. It is paranoid about making progress, so an allocatable
range is considered an error.

The coalescer should really not be creating these bad live ranges. They appear
when coalescing dead copies.

llvm-svn: 130787

show more ...

Minimize the slot indexes spanned by register ranges created when splitting.

When an interfering live range ends at a dead slot index between two
instructions, make sure that the inserted copy instr

Minimize the slot indexes spanned by register ranges created when splitting.

When an interfering live range ends at a dead slot index between two
instructions, make sure that the inserted copy instruction gets a slot index
after the dead ones. This makes it possible to avoid the interference.

Ideally, there shouldn't be interference ending at a deleted instruction, but
physical register coalescing can sometimes do that to sub-registers.

This fixes PR9823.

llvm-svn: 130687

show more ...

Add a safe-guard against repeated splitting for some rare cases.

The number of blocks covered by a live range must be strictly decreasing when
splitting, otherwise we can't allow repeated splitting.

Add a safe-guard against repeated splitting for some rare cases.

The number of blocks covered by a live range must be strictly decreasing when
splitting, otherwise we can't allow repeated splitting.

llvm-svn: 130249

show more ...

Don't recycle loop variables.

llvm-svn: 129928

Allow allocatable ranges from global live range splitting to be split again.

These intervals are allocatable immediately after splitting, but they may be
evicted because of later splitting. This is

Allow allocatable ranges from global live range splitting to be split again.

These intervals are allocatable immediately after splitting, but they may be
evicted because of later splitting. This is rare, but when it happens they
should be split again.

The remainder intervals that cannot be allocated after splitting still move
directly to spilling.

SplitEditor::finish can optionally provide a mapping from new live intervals
back to the original interval indexes returned by openIntv().

Each original interval index can map to multiple new intervals after connected
components have been separated. Dead code elimination may also add existing
intervals to the list.

The reverse mapping allows the SplitEditor client to treat the new intervals
differently depending on the split region they came from.

llvm-svn: 129925

show more ...

Unbreak the MSVC 2010 build.
For further information on this particular issue see: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-st

Unbreak the MSVC 2010 build.
For further information on this particular issue see: http://connect.microsoft.com/VisualStudio/feedback/details/520043/error-converting-from-null-to-a-pointer-type-in-std-pair

llvm-svn: 129642

show more ...

Teach the SplitKit blitter to handle multiply defined values as well.

The transferValues() function can now handle both singly and multiply defined
values, as long as the resulting live range is kno

Teach the SplitKit blitter to handle multiply defined values as well.

The transferValues() function can now handle both singly and multiply defined
values, as long as the resulting live range is known. Only rematerialized values
have their live range recomputed by extendRange().

The updateSSA() function can now insert PHI values in bulk across multiple
values in multiple target registers in one pass. The list of blocks received
from transferValues() is in layout order which seems to work well for the
iterative algorithm. Blocks from extendRange() are still in reverse BFS order,
but this function is used so rarely now that it doesn't matter.

llvm-svn: 129580

show more ...

Stop using dead function.

llvm-svn: 129442

Create new intervals for isolated blocks during region splitting.

This merges the behavior of splitSingleBlocks into splitAroundRegion, so the
RS_Region and RS_Block register stages can be coalesced

Create new intervals for isolated blocks during region splitting.

This merges the behavior of splitSingleBlocks into splitAroundRegion, so the
RS_Region and RS_Block register stages can be coalesced. That means the leftover
intervals after region splitting go directly to spilling instead of a second
pass of per-block splitting.

llvm-svn: 129379

show more ...

Add SplitKit API to query and select the current interval being worked on.

This makes it possible to target multiple registers in one pass.

llvm-svn: 129374

Build the Hopfield network incrementally when splitting global live ranges.

It is common for large live ranges to have few basic blocks with register uses
and many live-through blocks without any us

Build the Hopfield network incrementally when splitting global live ranges.

It is common for large live ranges to have few basic blocks with register uses
and many live-through blocks without any uses. This approach grows the Hopfield
network incrementally around the use blocks, completely avoiding checking
interference for some through blocks.

llvm-svn: 129188

show more ...

Analyze blocks with uses separately from live-through blocks without uses.

About 90% of the relevant blocks are live-through without uses, and the only
information required about them is their numbe

Analyze blocks with uses separately from live-through blocks without uses.

About 90% of the relevant blocks are live-through without uses, and the only
information required about them is their number. This saves memory and enables
later optimizations that need to look at only the use-blocks.

llvm-svn: 128985

show more ...