summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Break infinite loop when the Hopfield network oscillates.Jakob Stoklund Olesen2011-07-051-8/+6
| | | | | | | | | | 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
* Tweak comment and debug output.Jakob Stoklund Olesen2011-07-051-2/+3
| | | | llvm-svn: 134412
* Fix PR10244.Jakob Stoklund Olesen2011-07-041-4/+4
| | | | | | | | | | | | 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
* Use a new strategy for preventing eviction loops in RAGreedy.Jakob Stoklund Olesen2011-07-021-57/+74
| | | | | | | | | | | | | | | | | | | 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
* Reapply r134047 now that the world is ready for it.Jakob Stoklund Olesen2011-06-301-132/+262
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert r134047 while investigating a llvm-gcc-i386-linux-selfhostJakob Stoklund Olesen2011-06-291-262/+132
| | | | | | miscompile. llvm-svn: 134053
* Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art.Jakob Stoklund Olesen2011-06-291-132/+262
| | | | | | | | | | | | | | | | | | | | 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
* There is only one register coalescer. Merge it into the base class andRafael Espindola2011-06-261-1/+1
| | | | | | remove the analysis group. llvm-svn: 133899
* Move RegisterCoalescer.h to lib/CodeGen.Rafael Espindola2011-06-261-1/+1
| | | | llvm-svn: 133895
* Simplify local live range splitting's safeguard to fix PR10070.Jakob Stoklund Olesen2011-06-061-87/+57
| | | | | | | | | | | | | | | 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
* Switch AllocationOrder to using RegisterClassInfo instead of a BitVectorJakob Stoklund Olesen2011-06-031-3/+1
| | | | | | | | | of reserved registers. Use RegisterClassInfo in RABasic as well. This slightly changes som allocation orders because RegisterClassInfo puts CSR aliases last. llvm-svn: 132581
* Revert r132358 "Simplify the eviction policy by making the failsafe explicit."Jakob Stoklund Olesen2011-06-011-97/+44
| | | | | | | This commit caused regressions in i386 flops-[568], matrix, salsa20, 256.bzip2, and enc-md5. llvm-svn: 132413
* Simplify the eviction policy by making the failsafe explicit.Jakob Stoklund Olesen2011-05-311-44/+97
| | | | | | | | | | | | | | | | 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
* Reapply r132245 with a fix for the bug that broke the darwin9/i386 build.Jakob Stoklund Olesen2011-05-301-10/+10
| | | | llvm-svn: 132309
* Revert r132245, "Create two BlockInfo entries when a live range is ↵Jakob Stoklund Olesen2011-05-291-10/+10
| | | | | | | | discontinuous through a block." This commit seems to have broken a darwin 9 tester. llvm-svn: 132299
* Create two BlockInfo entries when a live range is discontinuous through a block.Jakob Stoklund Olesen2011-05-281-10/+10
| | | | | | | | | | | | | | | | | | | 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
* Add SplitAnalysis::getNumLiveBlocks().Jakob Stoklund Olesen2011-05-281-1/+1
| | | | | | | | | | | 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
* Add a RAGreedy::canEvict function.Jakob Stoklund Olesen2011-05-251-4/+62
| | | | | | | | | | | | 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
* 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
OpenPOWER on IntegriCloud