There are two conflicting strategies in play:

- Under high register pressure, we want to assign large live ranges
  first. Smaller live ranges are easier to place afterwards.

- Live range splitting is guided by interference, so splitting should be
  deferred until interference is as realistic as possible.

With the recent changes to the live range stages, and with compact
regions enabled, it is less traumatic to split a live range too early.
If some of the split products were too big, they can often be split
again.

By reversing the RS_Split order, we get this queue order:

1. Normal live ranges, large to small.
2. RS_Split live ranges, large to small.

The large-to-small order improves RAGreedy's puzzle solving skills under
high register pressure. It may cause a bit more iterated splitting, but
we handle that better now.

With this change, -compact-regions is mostly an improvement on SPEC.

llvm-svn: 136388

When splitting global live ranges, it is now possible to split for
multiple destination intervals at once. Previously, we only had the main
and stack intervals.

Each edge bundle is assigned to a split candidate, and splitAroundRegion
will insert copies between the candidate intervals and the stack
interval as needed.

The multi-way splitting is used to split around compact regions when
enabled with -compact-regions. The best candidate register still gets
all the bundles it wants, but everything outside the main interval is
first split around compact regions before we create single-block
intervals.

Compact region splitting still causes some regressions, so it is not
enabled by default.

llvm-svn: 136186

When dead code elimination deletes a PHI value, the virtual register may
split into multiple connected components. In that case, revert each
component to the RS_Assign stage.

The new components are guaranteed to be smaller (the original value
numbers are distributed among the components), so this will always be
making progress. The components are now allowed to evict other live
ranges or be split again.

llvm-svn: 136034

This mechanism already exists, but the RS_Split2 stage makes it clearer.

When live range splitting creates ranges that may not be making
progress, they are marked RS_Split2 instead of RS_New. These ranges may
be split again, but only in a way that can be proven to make progress.

For local ranges, that means they must be split into ranges used by
strictly fewer instructions.

For global ranges, region splitting is bypassed and the RS_Split2
ranges go straight to per-block splitting.

llvm-svn: 135912

The stage is used to control where a live range is going, not where it
is coming from. Live ranges created by splitting will usually be marked
RS_New, but some are marked RS_Spill to avoid wasting time trying to
split them again.

The old RS_Global and RS_Local stages are merged - they are really the
same thing for local and global live ranges.

llvm-svn: 135911

This method computes the edge bundles that should be live when splitting
around a compact region. This is independent of interference.

The function returns false if the live range was already a compact
region, or the compact region doesn't have any live bundles - it would
be the same as splitting around basic blocks.

Compact regions are computed using the normal spill placement code. We
pretend there is interference in all live-through blocks that don't use
the live range. This removes all edges from the Hopfield network used
for spill placement, so it converges instantly.

llvm-svn: 135847

A split candidate can have a null PhysReg which means that it doesn't
map to a real interference pattern. Instead, pretend that all through
blocks have interference.

This makes it possible to generate compact regions where the live range
doesn't go through blocks that don't use it. The live range will still
be live between directly connected blocks with uses.

Splitting around a compact region tends to produce a live range with a
high spill weight, so it may evict a less dense live range.

llvm-svn: 135845

Migrate LLVM and Clang to use the new makeArrayRef(...) functions where previously explicit non-default constructors were used.
Mostly mechanical with some manual reformatting.

llvm-svn: 135390

llvm-svn: 135354

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

Original commit message:

Count references to interference cache entries.

Each InterferenceCache::Cursor instance references a cache entry. A
non-zero reference count guarantees that the entry won't be reused for a
new register.

This makes it possible to have multiple live cursors examining
interference for different physregs.

The total number of live cursors into a cache must be kept below
InterferenceCache::getMaxCursors().

Code generation should be unaffected by this change, and it doesn't seem
to affect the cache replacement strategy either.

llvm-svn: 135130

llvm-svn: 135122

Each InterferenceCache::Cursor instance references a cache entry. A
non-zero reference count guarantees that the entry won't be reused for a
new register.

This makes it possible to have multiple live cursors examining
interference for different physregs.

The total number of live cursors into a cache must be kept below
InterferenceCache::getMaxCursors().

Code generation should be unaffected by this change, and it doesn't seem
to affect the cache replacement strategy either.

llvm-svn: 135121

The cache entry referenced by the best split candidate could become
clobbered by an unsuccessful candidate.

The correct fix here is to use reference counts on the cache entries.
Coming up.

llvm-svn: 135113

llvm-svn: 135096

Some pysical registers create split solutions that would spill anywhere.
They should not even be considered in future multi-way global splits.

This does not affect code generation (yet).

llvm-svn: 135080

This is in preparation of supporting multiple global split candidates in
a single live range split operation.

llvm-svn: 135074

RAGreedy::tryAssign will now evict interference from the preferred
register even when another register is free.

To support this, add the EvictionCost struct that counts how many hints
are broken by an eviction. We don't want to break one hint just to
satisfy another.

Rename canEvict to shouldEvict, and add the first bit of eviction policy
that doesn't depend on spill weights: Always make room in the preferred
register as long as the evictees can be split and aren't already
assigned to their preferred register.

Also make the CSR avoidance more accurate. When looking for a cheaper
register it is OK to use a new volatile register. Only CSR aliases that
have never been used before should be avoided.

llvm-svn: 134735

This is impossible in theory, I can prove it. In practice, our near-zero
threshold can cause the network to oscillate between equally good
solutions.

<rdar://problem/9720596>

llvm-svn: 134428

llvm-svn: 134412

A split point inserted in a block with a landing pad successor may be
hoisted above the call to ensure that it dominates all successors. The
code that handles the rest of the basic block must take this into
account.

I am not including a test case, it would be very fragile. PR10244 comes
from building clang with exceptions enabled.

llvm-svn: 134369

Every live range is assigned a cascade number the first time it is
involved in an eviction. As the evictor, it gets a new cascade number.
Every evictee is assigned the same cascade number as the evictor.

Eviction is prohibited if the evictor has a lower assigned cascade
number than the evictee.

This means that assigned cascade numbers are monotonically increasing
with every eviction, yet they are bounded by NextCascade which can only
be incremented by new live ranges. Thus, infinite loops cannot happen,
but eviction cascades can still be triggered by new live ranges as we
want.

Thanks to Andy for explaining this to me.

llvm-svn: 134303

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

miscompile.

llvm-svn: 134053

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

remove the analysis group.

llvm-svn: 133899

llvm-svn: 133895

When local live range splitting creates a live range with the same
number of instructions as the old range, mark it as RS_Local. When such
a range is seen again, require that it be split in a way that reduces
the number of instructions. That guarantees we are making progress while
still being able to perform 3 -> 2+3 splits as required by PR10070.

This also means that the PrevSlot map is no longer needed. This was also
used to estimate new spill weights, but that is no longer necessary
after slotIndexes::insertMachineInstrInMaps() got the extra Late
insertion argument.

llvm-svn: 132697

of reserved registers.

Use RegisterClassInfo in RABasic as well. This slightly changes som
allocation orders because RegisterClassInfo puts CSR aliases last.

llvm-svn: 132581

This commit caused regressions in i386 flops-[568], matrix, salsa20,
256.bzip2, and enc-md5.

llvm-svn: 132413

When assigned ranges are evicted, they are put in the RS_Evicted stage and are
not allowed to evict anything else. That prevents looping automatically.

When evicting ranges just to get a cheaper register, use only spill weights to
find the possible candidates. Avoid breaking hints for this purpose, it is not
worth it.

Start implementing more complex eviction heuristics, guarded by the temporary
-complex-eviction flag. The initial version permits a heavier range to be
evicted if it doesn't have any uses where the evicting range is live. This makes
it a good candidate for live ranfge splitting.

llvm-svn: 132358

llvm-svn: 132309

This commit seems to have broken a darwin 9 tester.

llvm-svn: 132299

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

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

This doesn't change functionality (much), but it allows for a more fine-grained
eviction policy. The current policy only compares spill weights, and that is not
always the best thing to do.  Spill weights are designed to serve linear scan,
and they don't consider live range splitting.

Add a mechanism so canEvict() can request that a live range be evicted and
split/spilled. This is to avoid infinite eviction loops.

llvm-svn: 132101

The previous invalidation missed the alias interference caches.

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

llvm-svn: 131133

This can't be just an assertion, users can always write impossible inline
assembly. Such an assembly statement should be included in the error message.

llvm-svn: 131024

After a virtual register is split, update any debug user variables that resided
in the old register. This ensures that the LiveDebugVariables are still correct
after register allocation.

This may create DBG_VALUE instructions that place a user variable in a register
in parts of the function and in a stack slot in other parts. DwarfDebug
currently doesn't support that.

llvm-svn: 130998

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