summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Fix PR9883. Make sure all caches are invalidated when a live range is repaired.Jakob Stoklund Olesen2011-05-101-3/+1
| | | | | | | | The previous invalidation missed the alias interference caches. Also add a stats counter for the number of repaired ranges. llvm-svn: 131133
* Emit a proper error message when register allocators run out of registers.Jakob Stoklund Olesen2011-05-061-1/+4
| | | | | | | 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
* Update LiveDebugVariables after live range splitting.Jakob Stoklund Olesen2011-05-061-1/+6
| | | | | | | | | | | | 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
* Gracefully handle invalid live ranges. Fix PR9831.Jakob Stoklund Olesen2011-05-031-0/+13
| | | | | | | | | | | | | | | | 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
* Use hysteresis for local live range splitting as well.Jakob Stoklund Olesen2011-04-301-4/+4
| | | | llvm-svn: 130596
* Add a safe-guard against repeated splitting for some rare cases.Jakob Stoklund Olesen2011-04-261-3/+15
| | | | | | | 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
* Always compare the cost of region splitting with the cost of per-block ↵Jakob Stoklund Olesen2011-04-221-6/+45
| | | | | | | | splitting. Sometimes it is better to split per block, and we missed those cases. llvm-svn: 130025
* Allow allocatable ranges from global live range splitting to be split again.Jakob Stoklund Olesen2011-04-211-5/+28
| | | | | | | | | | | | | | | | | | | | | 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
* Prefer cheap registers for busy live ranges.Jakob Stoklund Olesen2011-04-201-6/+44
| | | | | | | | | | | | | | 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
* Stop using dead function.Jakob Stoklund Olesen2011-04-131-3/+0
| | | | llvm-svn: 129442
* SparseBitVector is SLOW.Jakob Stoklund Olesen2011-04-121-48/+55
| | | | | | | Use a Bitvector instead, we didn't need the smaller memory footprint anyway. This makes the greedy register allocator 10% faster. llvm-svn: 129390
* Create new intervals for isolated blocks during region splitting.Jakob Stoklund Olesen2011-04-121-21/+23
| | | | | | | | | 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
* Speed up eviction by stopping collectInterferingVRegs as soon as the spillJakob Stoklund Olesen2011-04-111-10/+12
| | | | | | weight limit has been exceeded. llvm-svn: 129305
* Build the Hopfield network incrementally when splitting global live ranges.Jakob Stoklund Olesen2011-04-091-41/+83
| | | | | | | | | 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
* Extract SpillPlacement::addLinks for handling the special transparent blocks.Jakob Stoklund Olesen2011-04-071-17/+27
| | | | llvm-svn: 129079
* Also account for the spill code that would be inserted in live-through ↵Jakob Stoklund Olesen2011-04-061-5/+16
| | | | | | blocks with interference. llvm-svn: 129030
* Abort the constraint calculation early when all positive bias is lost.Jakob Stoklund Olesen2011-04-061-33/+63
| | | | | | | Without any positive bias, there is nothing for the spill placer to to. It will spill everywhere. llvm-svn: 129029
* Keep track of the number of positively biased nodes when adding constraints.Jakob Stoklund Olesen2011-04-061-0/+1
| | | | | | If there are no positive nodes, the algorithm can be aborted early. llvm-svn: 129021
* Break the spill placement algorithm into three parts: prepare, ↵Jakob Stoklund Olesen2011-04-061-1/+4
| | | | | | | | addConstraints, and finish. This will allow us to abort the algorithm early if it is determined to be futile. llvm-svn: 129020
* Oops. Scary.Jakob Stoklund Olesen2011-04-061-1/+1
| | | | llvm-svn: 128986
* Analyze blocks with uses separately from live-through blocks without uses.Jakob Stoklund Olesen2011-04-061-68/+83
| | | | | | | | 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
* Run LiveDebugVariables in RegAllocBasic and RegAllocGreedy.Jakob Stoklund Olesen2011-04-051-0/+7
| | | | llvm-svn: 128935
* Stop precomputing last split points, query the SplitAnalysis cache on demand.Jakob Stoklund Olesen2011-04-051-10/+13
| | | | llvm-svn: 128875
* Stop caching basic block index ranges now that SlotIndexes can keep up.Jakob Stoklund Olesen2011-04-041-18/+22
| | | | llvm-svn: 128821
* Use InterferenceCache in RegAllocGreedy.Jakob Stoklund Olesen2011-04-021-94/+46
| | | | llvm-svn: 128765
* Add an InterferenceCache class for caching per-block interference ranges.Jakob Stoklund Olesen2011-04-021-1/+1
| | | | | | | | 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
* Treat clones the same as their origin.Jakob Stoklund Olesen2011-03-301-5/+21
| | | | | | | | | | | | 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
* Recompute register class and hint for registers created during spilling.Jakob Stoklund Olesen2011-03-291-0/+1
| | | | | | The spill weight is not recomputed for an unspillable register - it stays infinite. llvm-svn: 128490
* Drop interference reassignment in favor of eviction.Jakob Stoklund Olesen2011-03-271-132/+15
| | | | | | | | | 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
* Add debug output.Jakob Stoklund Olesen2011-03-191-0/+1
| | | | llvm-svn: 127959
* Add a LiveRangeEdit delegate callback before shrinking a live range.Jakob Stoklund Olesen2011-03-161-0/+12
| | | | | | The register allocator needs to adjust its live interval unions when that happens. llvm-svn: 127774
* Clarify debugging output.Jakob Stoklund Olesen2011-03-161-2/+8
| | | | llvm-svn: 127771
* Tell the register allocator about new unused virtual registers.Jakob Stoklund Olesen2011-03-131-0/+10
| | | | | | | This allows the allocator to free any resources used by the virtual register, including physical register assignments. llvm-svn: 127560
* Change the Spiller interface to take a LiveRangeEdit reference.Jakob Stoklund Olesen2011-03-101-1/+2
| | | | | | | This makes it possible to register delegates and get callbacks when the spiller edits live ranges. llvm-svn: 127389
* Make SpillIs an optional pointer. Avoid creating a bunch of temporary ↵Jakob Stoklund Olesen2011-03-101-2/+1
| | | | | | SmallVectors. llvm-svn: 127388
* Add a LiveRangeEdit::Delegate protocol.Jakob Stoklund Olesen2011-03-091-4/+20
| | | | | | | This will we used for keeping register allocator data structures up to date while LiveRangeEdit is trimming live intervals. llvm-svn: 127300
* Make the UselessRegs argument optional in the LiveRangeEdit constructor.Jakob Stoklund Olesen2011-03-071-6/+3
| | | | llvm-svn: 127181
* Rework the global split cost calculation.Jakob Stoklund Olesen2011-03-051-21/+30
| | | | | | | The global cost is the sum of block frequencies for spill code that must be inserted because preferences weren't met. llvm-svn: 127062
* Compute the constraints for global live range splitting from an interference ↵Jakob Stoklund Olesen2011-03-051-163/+67
| | | | | | | | | | | pattern. 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
* Extract a method. No functional change.Jakob Stoklund Olesen2011-03-041-40/+52
| | | | llvm-svn: 127040
* Go back to comparing spill weights when deciding if interference can be evicted.Jakob Stoklund Olesen2011-03-041-9/+5
| | | | | | | 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
* Tweak debug output. No functional changes.Jakob Stoklund Olesen2011-03-041-1/+6
| | | | llvm-svn: 127006
* Precompute block frequencies, pow() isn't free.Jakob Stoklund Olesen2011-03-041-4/+3
| | | | llvm-svn: 126975
* Cache basic block bounds instead of asking SlotIndexes::getMBBRange all the ↵Jakob Stoklund Olesen2011-03-031-39/+30
| | | | | | | | | time. This speeds up the greedy register allocator by 15%. DenseMap is not as fast as one might hope. llvm-svn: 126921
* Change the SplitEditor interface to a single instance can be shared for ↵Jakob Stoklund Olesen2011-03-031-34/+37
| | | | | | multiple splits. llvm-svn: 126912
* Drop RAGreedy::trySpillInterferences().Jakob Stoklund Olesen2011-03-011-70/+0
| | | | | | | This is a waste of time since we already know how to evict all interferences which is a better approach anyway. llvm-svn: 126798
* Keep track of which stage produced a live range, and bypass earlier stages ↵Jakob Stoklund Olesen2011-03-011-20/+76
| | | | | | | | | | | | | | | | | | | | | | when revisiting. 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
* Try harder to get the hint by preferring to evict hint interference.Jakob Stoklund Olesen2011-02-251-0/+3
| | | | llvm-svn: 126463
* Tweak the register allocator priority queue some more.Jakob Stoklund Olesen2011-02-241-10/+22
| | | | | | | | | | | | 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
* Keep track of how many times a live range has been dequeued, and prioritize ↵Jakob Stoklund Olesen2011-02-231-0/+7
| | | | | | | | | | | new ranges. 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
OpenPOWER on IntegriCloud