summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert r135121 which broke a gcc-4.2 builder.Jakob Stoklund Olesen2011-07-141-16/+5
| | | | llvm-svn: 135122
* Count references to interference cache entries.Jakob Stoklund Olesen2011-07-141-5/+16
| | | | | | | | | | | | | | | | | Each InterferenceCache::Cursor instance references a cache entry. A non-zero reference count guarantees that the entry won't be reused for a new register. This makes it possible to have multiple live cursors examining interference for different physregs. The total number of live cursors into a cache must be kept below InterferenceCache::getMaxCursors(). Code generation should be unaffected by this change, and it doesn't seem to affect the cache replacement strategy either. llvm-svn: 135121
* Reapply r135074 and r135080 with a fix.Jakob Stoklund Olesen2011-07-141-24/+31
| | | | | | | | | | The cache entry referenced by the best split candidate could become clobbered by an unsuccessful candidate. The correct fix here is to use reference counts on the cache entries. Coming up. llvm-svn: 135113
* Revert r135074 and r135080. They broke clamscan.Jakob Stoklund Olesen2011-07-131-26/+24
| | | | llvm-svn: 135096
* Only keep the global split candidates that work out.Jakob Stoklund Olesen2011-07-131-12/+15
| | | | | | | | | Some pysical registers create split solutions that would spill anywhere. They should not even be considered in future multi-way global splits. This does not affect code generation (yet). llvm-svn: 135080
* Move the InterferenceCache cursor into the GlobalSplitCand struct.Jakob Stoklund Olesen2011-07-131-16/+15
| | | | | | | This is in preparation of supporting multiple global split candidates in a single live range split operation. llvm-svn: 135074
* Be more aggressive about following hints.Jakob Stoklund Olesen2011-07-081-59/+142
| | | | | | | | | | | | | | | | | | | | RAGreedy::tryAssign will now evict interference from the preferred register even when another register is free. To support this, add the EvictionCost struct that counts how many hints are broken by an eviction. We don't want to break one hint just to satisfy another. Rename canEvict to shouldEvict, and add the first bit of eviction policy that doesn't depend on spill weights: Always make room in the preferred register as long as the evictees can be split and aren't already assigned to their preferred register. Also make the CSR avoidance more accurate. When looking for a cheaper register it is OK to use a new volatile register. Only CSR aliases that have never been used before should be avoided. llvm-svn: 134735
* 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
OpenPOWER on IntegriCloud