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

This speeds up the greedy register allocator by 15%.
DenseMap is not as fast as one might hope.

llvm-svn: 126921

llvm-svn: 126912

This is a waste of time since we already know how to evict all interferences
which is a better approach anyway.

llvm-svn: 126798

This effectively disables the 'turbo' functionality of the greedy register
allocator where all new live ranges created by splitting would be reconsidered
as if they were originals.

There are two reasons for doing this, 1. It guarantees that the algorithm
terminates. Early versions were prone to infinite looping in certain corner
cases. 2. It is a 2x speedup. We can skip a lot of unnecessary interference
checks that won't lead to good splitting anyway.

The problem is that region splitting only gets one shot, so it should probably
be changed to target multiple physical registers at once.

Local live range splitting is still 'turbo' enabled. It only accounts for a
small fraction of compile time, so it is probably not necessary to do anything
about that.

llvm-svn: 126781

llvm-svn: 126463

New live ranges are assigned in long -> short order, but live ranges that have
been evicted at least once are deferred and assigned in short -> long order.

Also disable splitting and spilling for live ranges seen for the first time.

The intention is to create a realistic interference pattern from the heavy live
ranges before starting splitting and spilling around it.

llvm-svn: 126451

When a large live range is evicted, it will usually be split when it comes
around again. By deferring evicted live ranges, the splitting happens at a time
when the interference pattern is more realistic. This prevents repeated
splitting and evictions.

llvm-svn: 126282

llvm-svn: 126277

Use interval sizes instead of spill weights to determine if it is legal to evict
interference. A smaller interval can evict interference if all interfering live
ranges are larger.

Allow multiple interferences to be evicted as along as they are all larger than
the live range being allocated.

Spill weights are still used to select the preferred eviction candidate.

llvm-svn: 126276

This is based on the observation that long live ranges are more difficult to
allocate, so there is a better chance of solving the puzzle by handling the big
pieces first. The allocator will evict and split long alive ranges when they get
in the way.

RABasic is still using spill weights for its priority queue, so the interface to
the queue has been virtualized.

llvm-svn: 126259

An original endpoint is an instruction that killed or defined the original live
range before any live ranges were split.

When splitting global live ranges, avoid creating local live ranges without any
original endpoints. We may still create global live ranges without original
endpoints, but such a range won't be split again, and live range splitting still
terminates.

llvm-svn: 126151