summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/RegAllocGreedy.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Also use shouldSplitSingleBlock() in the fallback splitting mode.Jakob Stoklund Olesen2011-08-051-8/+18
| | | | | | | Drop the use of SplitAnalysis::getMultiUseBlocks, there is no need to go through a SmallPtrSet any more. llvm-svn: 136992
* Split around single instructions to enable register class inflation.Jakob Stoklund Olesen2011-08-051-1/+7
| | | | | | | | | | | | | Normally, we don't create a live range for a single instruction in a basic block, the spiller does that anyway. However, when splitting a live range that belongs to a proper register sub-class, inserting these extra COPY instructions completely remove the constraints from the remainder interval, and it may be allocated from the larger super-class. The spiller will mop up these small live ranges if we end up spilling anyway. It calls them snippets. llvm-svn: 136989
* Enable compact region splitting by default.Jakob Stoklund Olesen2011-08-031-1/+1
| | | | | | | | | | | This helps generate better code in functions with high register pressure. The previous version of compact region splitting caused regressions because the regions were a bit too large. A stronger negative bias applied in r136832 fixed this problem. llvm-svn: 136836
* Be more conservative when forming compact regions.Jakob Stoklund Olesen2011-08-031-1/+3
| | | | | | | | | | | | | | | Apply twice the negative bias on transparent blocks when computing the compact regions. This excludes loop backedges from the region when only one of the loop blocks uses the register. Previously, we would include the backedge in the region if the loop preheader and the loop latch both used the register, but the loop header didn't. When both the header and latch blocks use the register, we still keep it live on the backedge. llvm-svn: 136832
* Fix some warnings from Clang in release builds:Chandler Carruth2011-08-031-0/+2
| | | | | | | | | | | lib/CodeGen/RegAllocGreedy.cpp:1176:18: warning: unused variable 'B' [-Wunused-variable] if (unsigned B = Cand.getBundles(BundleCand, BestCand)) { ^ lib/CodeGen/RegAllocGreedy.cpp:1188:18: warning: unused variable 'B' [-Wunused-variable] if (unsigned B = Cand.getBundles(BundleCand, 0)) { ^ llvm-svn: 136831
* Use the precomputed def presence in RAGreedy::calcSpillCost.Jakob Stoklund Olesen2011-08-021-11/+2
| | | | llvm-svn: 136742
* Inform SpillPlacement about blocks with defs.Jakob Stoklund Olesen2011-08-021-0/+1
| | | | | | This information is not used for anything yet. llvm-svn: 136741
* Rename {First,Last}Use to {First,Last}Instr.Jakob Stoklund Olesen2011-08-021-10/+12
| | | | | | | With a 'FirstDef' field right there, it is very confusing that FirstUse refers to an instruction that may be a def. llvm-svn: 136739
* Time the emission of debug values.Jakob Stoklund Olesen2011-07-311-1/+4
| | | | llvm-svn: 136584
* Revert r136528 "Enable compact region splitting by default."Jakob Stoklund Olesen2011-07-301-1/+1
| | | | | | | While this generally helped x86-64, there was some large regressions for i386. llvm-svn: 136571
* Enable compact region splitting by default.Jakob Stoklund Olesen2011-07-291-1/+1
| | | | | | | This helps generate better code in functions with high register pressure. llvm-svn: 136528
* Reverse order of RS_Split live ranges under -compact-regions.Jakob Stoklund Olesen2011-07-281-3/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | There are two conflicting strategies in play: - Under high register pressure, we want to assign large live ranges first. Smaller live ranges are easier to place afterwards. - Live range splitting is guided by interference, so splitting should be deferred until interference is as realistic as possible. With the recent changes to the live range stages, and with compact regions enabled, it is less traumatic to split a live range too early. If some of the split products were too big, they can often be split again. By reversing the RS_Split order, we get this queue order: 1. Normal live ranges, large to small. 2. RS_Split live ranges, large to small. The large-to-small order improves RAGreedy's puzzle solving skills under high register pressure. It may cause a bit more iterated splitting, but we handle that better now. With this change, -compact-regions is mostly an improvement on SPEC. llvm-svn: 136388
* Add support for multi-way live range splitting.Jakob Stoklund Olesen2011-07-261-64/+165
| | | | | | | | | | | | | | | | | | | | | When splitting global live ranges, it is now possible to split for multiple destination intervals at once. Previously, we only had the main and stack intervals. Each edge bundle is assigned to a split candidate, and splitAroundRegion will insert copies between the candidate intervals and the stack interval as needed. The multi-way splitting is used to split around compact regions when enabled with -compact-regions. The best candidate register still gets all the bundles it wants, but everything outside the main interval is first split around compact regions before we create single-block intervals. Compact region splitting still causes some regressions, so it is not enabled by default. llvm-svn: 136186
* Revert to RA_Assign when a virtreg separates into components.Jakob Stoklund Olesen2011-07-261-1/+3
| | | | | | | | | | | | | When dead code elimination deletes a PHI value, the virtual register may split into multiple connected components. In that case, revert each component to the RS_Assign stage. The new components are guaranteed to be smaller (the original value numbers are distributed among the components), so this will always be making progress. The components are now allowed to evict other live ranges or be split again. llvm-svn: 136034
* Add an RS_Split2 stage used for loop prevention.Jakob Stoklund Olesen2011-07-251-15/+24
| | | | | | | | | | | | | | | | This mechanism already exists, but the RS_Split2 stage makes it clearer. When live range splitting creates ranges that may not be making progress, they are marked RS_Split2 instead of RS_New. These ranges may be split again, but only in a way that can be proven to make progress. For local ranges, that means they must be split into ranges used by strictly fewer instructions. For global ranges, region splitting is bypassed and the RS_Split2 ranges go straight to per-block splitting. llvm-svn: 135912
* Rename live range stages to better reflect how they are used.Jakob Stoklund Olesen2011-07-251-32/+40
| | | | | | | | | | | | The stage is used to control where a live range is going, not where it is coming from. Live ranges created by splitting will usually be marked RS_New, but some are marked RS_Spill to avoid wasting time trying to split them again. The old RS_Global and RS_Local stages are merged - they are really the same thing for local and global live ranges. llvm-svn: 135911
* Add RAGreedy::calcCompactRegion.Jakob Stoklund Olesen2011-07-231-0/+46
| | | | | | | | | | | | | | | | This method computes the edge bundles that should be live when splitting around a compact region. This is independent of interference. The function returns false if the live range was already a compact region, or the compact region doesn't have any live bundles - it would be the same as splitting around basic blocks. Compact regions are computed using the normal spill placement code. We pretend there is interference in all live-through blocks that don't use the live range. This removes all edges from the Hopfield network used for spill placement, so it converges instantly. llvm-svn: 135847
* Prepare RAGreedy::growRegion for compact regions.Jakob Stoklund Olesen2011-07-231-1/+8
| | | | | | | | | | | | | | | A split candidate can have a null PhysReg which means that it doesn't map to a real interference pattern. Instead, pretend that all through blocks have interference. This makes it possible to generate compact regions where the live range doesn't go through blocks that don't use it. The live range will still be live between directly connected blocks with uses. Splitting around a compact region tends to produce a live range with a high spill weight, so it may evict a less dense live range. llvm-svn: 135845
* Migrate LLVM and Clang to use the new makeArrayRef(...) functions where ↵Frits van Bommel2011-07-181-4/+3
| | | | | | | | previously explicit non-default constructors were used. Mostly mechanical with some manual reformatting. llvm-svn: 135390
* Remove unused LoopRanges from RegAllocGreedy.Jakub Staszak2011-07-161-6/+0
| | | | llvm-svn: 135354
* Extract parts of RAGreedy::splitAroundRegion as SplitKit methods.Jakob Stoklund Olesen2011-07-151-299/+13
| | | | | | | | | | | This gets rid of some of the gory splitting details in RAGreedy and makes them available to future SplitKit clients. Slightly generalize the functionality to support multi-way splitting. Specifically, SplitEditor::splitLiveThroughBlock() supports switching between different register intervals in a block. llvm-svn: 135307
* Reapply r135121 with a fixed copy constructor.Jakob Stoklund Olesen2011-07-141-5/+16
| | | | | | | | | | | | | | | | | | | | | Original commit message: Count references to interference cache entries. 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: 135130
* 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
OpenPOWER on IntegriCloud