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

When DCE clones a live range because it separates into connected components,
make sure that the clones enter the same register allocator stage as the
register they were cloned from.

For instance, clones may be split even when they where created during spilling.
Other registers created during spilling are not candidates for splitting or even
(re-)spilling.

llvm-svn: 128524

The spill weight is not recomputed for an unspillable register - it stays infinite.

llvm-svn: 128490

The reassignment phase was able to move interference with a higher spill weight,
but it didn't happen very often and it was fairly expensive.

The existing interference eviction picks up the slack.

llvm-svn: 128397

llvm-svn: 127959

The register allocator needs to adjust its live interval unions when that happens.

llvm-svn: 127774

llvm-svn: 127771

This allows the allocator to free any resources used by the virtual register,
including physical register assignments.

llvm-svn: 127560

This makes it possible to register delegates and get callbacks when the spiller
edits live ranges.

llvm-svn: 127389

llvm-svn: 127388

This will we used for keeping register allocator data structures up to date
while LiveRangeEdit is trimming live intervals.

llvm-svn: 127300

llvm-svn: 127181

The global cost is the sum of block frequencies for spill code that must be
inserted because preferences weren't met.

llvm-svn: 127062

This simplifies the code and makes it faster too.

The interference patterns are saved for each candidate register. It will be
reused for actually executing the split. Work in progress.

llvm-svn: 127054

llvm-svn: 127040

It gives better results. Sometimes, a live range can be large and still have
high spill weight. Such a range should not be spilled.

llvm-svn: 127036

llvm-svn: 127006

llvm-svn: 126975