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

llvm-svn: 130596

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

Sometimes it is better to split per block, and we missed those cases.

llvm-svn: 130025

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

On the x86-64 and thumb2 targets, some registers are more expensive to encode
than others in the same register class.

Add a CostPerUse field to the TableGen register description, and make it
available from TRI->getCostPerUse. This represents the cost of a REX prefix or a
32-bit instruction encoding required by choosing a high register.

Teach the greedy register allocator to prefer cheap registers for busy live
ranges (as indicated by spill weight).

llvm-svn: 129864

llvm-svn: 129442

Use a Bitvector instead, we didn't need the smaller memory footprint anyway.
This makes the greedy register allocator 10% faster.

llvm-svn: 129390

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

weight limit has been exceeded.

llvm-svn: 129305

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

llvm-svn: 129079

llvm-svn: 129030

Without any positive bias, there is nothing for the spill placer to to. It will
spill everywhere.

llvm-svn: 129029

If there are no positive nodes, the algorithm can be aborted early.

llvm-svn: 129021

This will allow us to abort the algorithm early if it is determined to be futile.

llvm-svn: 129020

llvm-svn: 128986

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

llvm-svn: 128935

llvm-svn: 128875

llvm-svn: 128821

llvm-svn: 128765

When the greedy register allocator is splitting multiple global live ranges, it
tends to look at the same interference data many times. The InterferenceCache
class caches queries for unaltered LiveIntervalUnions.

llvm-svn: 128764