The local ranges created get to stay in the RS_New stage, just like for
local and region splitting.

This gives tryLocalSplit a bit more freedom the first time it sees one
of these new local ranges.

llvm-svn: 137001

llvm-svn: 136996

No functional change.

llvm-svn: 136994

Drop the use of SplitAnalysis::getMultiUseBlocks, there is no need to go
through a SmallPtrSet any more.

llvm-svn: 136992

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

This helps generate better code in functions with high register
pressure.

The previous version of compact region splitting caused regressions
because the regions were a bit too large. A stronger negative bias
applied in r136832 fixed this problem.

llvm-svn: 136836

Apply twice the negative bias on transparent blocks when computing the
compact regions. This excludes loop backedges from the region when only
one of the loop blocks uses the register.

Previously, we would include the backedge in the region if the loop
preheader and the loop latch both used the register, but the loop header
didn't.

When both the header and latch blocks use the register, we still keep it
live on the backedge.

llvm-svn: 136832

lib/CodeGen/RegAllocGreedy.cpp:1176:18: warning: unused variable 'B' [-Wunused-variable]
    if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
                 ^
lib/CodeGen/RegAllocGreedy.cpp:1188:18: warning: unused variable 'B' [-Wunused-variable]
    if (unsigned B = Cand.getBundles(BundleCand, 0)) {
                 ^

llvm-svn: 136831

llvm-svn: 136742

This information is not used for anything yet.

llvm-svn: 136741

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

llvm-svn: 136739

llvm-svn: 136584

While this generally helped x86-64, there was some large regressions
for i386.

llvm-svn: 136571

This helps generate better code in functions with high register
pressure.

llvm-svn: 136528

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