summaryrefslogtreecommitdiffstats
path: root/llvm/lib/CodeGen/SplitKit.h
Commit message (Collapse)AuthorAgeFilesLines
* Move LiveRangeCalc header to publicily available position. NFCMarcello Maggioni2019-10-171-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D69078 llvm-svn: 375075
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [RegAllocGreedy] avoid using physreg candidates that cannot be correctly spilledDaniil Fukalov2018-09-251-0/+17
| | | | | | | | | | | | | | | | | | | For the AMDGPU target if a MBB contains exec mask restore preamble, SplitEditor may get state when it cannot insert a spill instruction. E.g. for a MIR bb.100: %1 = S_OR_SAVEEXEC_B64 %2, implicit-def $exec, implicit-def $scc, implicit $exec and if the regalloc will try to allocate a virtreg to the physreg already assigned to virtreg %1, it should insert spill instruction before the S_OR_SAVEEXEC_B64 instruction. But it is not possible since can generate incorrect code in terms of exec mask. The change makes regalloc to ignore such physreg candidates. Reviewed By: rampitec Differential Revision: https://reviews.llvm.org/D52052 llvm-svn: 343004
* Remove trailing spaceFangrui Song2018-07-301-1/+1
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [CodeGen] Fix inconsistent declaration parameter nameFangrui Song2018-07-161-1/+1
| | | | llvm-svn: 337200
* SplitKit: Fix liveness recomputation in some remat cases.Matthias Braun2018-02-021-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Example situation: ``` BB0: %0 = ... use %0 ; ... condjump BB1 jmp BB2 BB1: %0 = ... ; rematerialized def from above (from earlier split step) jmp BB2 BB2: ; ... use %0 ``` %0 will have a live interval with 3 value numbers (for the BB0, BB1 and BB2 parts). Now SplitKit tries and succeeds in rematerializing the value number in BB2 (This only works because it is a secondary split so SplitKit is can trace this back to a single original def). We need to recompute all live ranges affected by a value number that we rematerialize. The case that we missed before is that when the value that is rematerialized is at a join (Phi VNI) then we also have to recompute liveness for the predecessor VNIs. rdar://35699130 Differential Revision: https://reviews.llvm.org/D42667 llvm-svn: 324039
* [CodeGen] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-08-291-22/+25
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 312053
* SplitKit: Correctly implement partial subregister copiesMatthias Braun2017-03-171-0/+11
| | | | | | | | | | | - This fixes a bug where subregister incompatible with the vregs register class where used. - Implement the case where multiple copies are necessary to cover a given lanemask. Differential Revision: https://reviews.llvm.org/D30438 llvm-svn: 298025
* Check proper live range in extendPHIRangesKrzysztof Parzyszek2016-11-211-3/+7
| | | | | | | | | | | | | The function extendPHIRanges checks the main range of the original live interval, even when dealing with a subrange. This could also lead to an assert when the subrange is not live at the extension point, but the main range is. To avoid this, check the corresponding subrange of the original live range, instead of always checking the main range. Review (as a part of a bigger set of changes): https://reviews.llvm.org/D26359 llvm-svn: 287571
* Create subranges for new intervals resulting from live interval splittingKrzysztof Parzyszek2016-08-241-2/+25
| | | | | | | | | | | | | | | | | | | The register allocator can split a live interval of a register into a set of smaller intervals. After the allocation of registers is complete, the rewriter will modify the IR to replace virtual registers with the corres- ponding physical registers. At this stage, if a register corresponding to a subregister of a virtual register is used, the rewriter will check if that subregister is undefined, and if so, it will add the <undef> flag to the machine operand. The function verifying liveness of the subregis- ter would assume that it is undefined, unless any of the subranges of the live interval proves otherwise. The problem is that the live intervals created during splitting do not have any subranges, even if the original parent interval did. This could result in the <undef> flag placed on a register that is actually defined. Differential Revision: http://reviews.llvm.org/D21189 llvm-svn: 279625
* Allow dead insts to be kept in DeadRemat only when they are rematerializable.Wei Mi2016-07-081-2/+4
| | | | | | | | | | | | | | | Because isReallyTriviallyReMaterializableGeneric puts many limits on rematerializable instructions, this fix can prevent instructions with tied virtual operands and instructions with virtual register uses from being kept in DeadRemat, so as to workaround the live interval consistency problem for the dummy instructions kept in DeadRemat. But we still need to fix the live interval consistency problem. This patch is just a short time relieve. PR28464 has been filed as a reminder. Differential Revision: http://reviews.llvm.org/D19486 llvm-svn: 274928
* InsertPointAnalysis: Move current live interval from being a class memberWei Mi2016-05-231-13/+11
| | | | | | | | to query interfaces argument; NFC Differential Revision: http://reviews.llvm.org/D20532 llvm-svn: 270481
* [NFC] Extract LastSplitPoint computation from SplitAnalysis to a new classWei Mi2016-05-111-21/+47
| | | | | | | | | | | | InsertPointAnalysis. Because both split and spill hoisting want to use LastSplitPoint computation result, extract the LastSplitPoint computation from SplitAnalysis class which also contains a bunch of other analysises only related to split. Differential Revision: http://reviews.llvm.org/D20027. llvm-svn: 269248
* Spelling and grammar corrections in comments.Eric Christopher2016-05-041-1/+1
| | | | llvm-svn: 268560
* Recommit r265547, and r265610,r265639,r265657 on top of it, plusWei Mi2016-04-131-3/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | two fixes with one about error verify-regalloc reported, and another about live range update of phi after rematerialization. r265547: Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Patches on top of r265547: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" Differential Revision: http://reviews.llvm.org/D15302 Differential Revision: http://reviews.llvm.org/D18934 Differential Revision: http://reviews.llvm.org/D18935 Differential Revision: http://reviews.llvm.org/D18936 llvm-svn: 266162
* Revert r265547 "Recommit r265309 after fixed an invalid memory reference bug ↵Hans Wennborg2016-04-081-9/+3
| | | | | | | | | | | | | happened" It caused PR27275: "ARM: Bad machine code: Using an undefined physical register" Also reverting the following commits that were landed on top: r265610 "Fix the compare-clang diff error introduced by r265547." r265639 "Fix the sanitizer bootstrap error in r265547." r265657 "InlineSpiller.cpp: Escap \@ in r265547. [-Wdocumentation]" llvm-svn: 265790
* Recommit r265309 after fixed an invalid memory reference bug happenedWei Mi2016-04-061-3/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | when DenseMap growed and moved memory. I verified it fixed the bootstrap problem on x86_64-linux-gnu but I cannot verify whether it fixes the bootstrap error on clang-ppc64be-linux. I will watch the build-bot result closely. Replace analyzeSiblingValues with new algorithm to fix its compile time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265547
* Revert r265309 and r265312 because they caused some errors I need to ↵Wei Mi2016-04-041-9/+3
| | | | | | investigate. llvm-svn: 265317
* Replace analyzeSiblingValues with new algorithm to fix its compileWei Mi2016-04-041-3/+9
| | | | | | | | | | | | | | | | | | | | | | | | | time issue. The patch is to solve PR17409 and its duplicates. analyzeSiblingValues is a N x N complexity algorithm where N is the number of siblings generated by reg splitting. Although it causes siginificant compile time issue when N is large, it is also important for performance since it removes redundent spills and enables rematerialization. To solve the compile time issue, the patch removes analyzeSiblingValues and replaces it with lower cost alternatives containing two parts. The first part creates a new spill hoisting method in postOptimization of register allocation. It does spill hoisting at once after all the spills are generated instead of inside every instance of selectOrSplit. The second part queries the define expr of the original register for rematerializaiton and keep it always available during register allocation even if it is already dead. It deletes those dead instructions only in postOptimization. With the two parts in the patch, it can remove analyzeSiblingValues without sacrificing performance. Differential Revision: http://reviews.llvm.org/D15302 llvm-svn: 265309
* [CodeGen] Reduce visibility of implementation detailsBenjamin Kramer2015-07-011-2/+2
| | | | | | NFC. llvm-svn: 241164
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* Fix spelling.Jim Grosbach2015-05-021-1/+1
| | | | llvm-svn: 236367
* Canonicalize header guards into a common format.Benjamin Kramer2014-08-131-2/+2
| | | | | | | | | | Add header guards to files that were missing guards. Remove #endif comments as they don't seem common in LLVM (we can easily add them back if we decide they're useful) Changes made by clang-tidy with minor tweaks. llvm-svn: 215558
* Clean up language and grammar.Eric Christopher2014-05-201-1/+1
| | | | | | | Based on a patch by jfcaron3@gmail.com! PR19806 llvm-svn: 209216
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-161-1/+1
| | | | | | instead of comparing to nullptr. llvm-svn: 206356
* Revert "Give internal classes hidden visibility."Benjamin Kramer2013-09-111-2/+2
| | | | | | | It works with clang, but GCC has different rules so we can't make all of those hidden. This reverts commit r190534. llvm-svn: 190536
* Give internal classes hidden visibility.Benjamin Kramer2013-09-111-2/+2
| | | | | | Worth 100k on a linux/x86_64 Release+Asserts clang. llvm-svn: 190534
* Switch spill weights from a basic loop depth estimation to BlockFrequencyInfo.Benjamin Kramer2013-06-171-1/+3
| | | | | | | | | | | | | | | | | | The main advantages here are way better heuristics, taking into account not just loop depth but also __builtin_expect and other static heuristics and will eventually learn how to use profile info. Most of the work in this patch is pushing the MachineBlockFrequencyInfo analysis into the right places. This is good for a 5% speedup on zlib's deflate (x86_64), there were some very unfortunate spilling decisions in its hottest loop in longest_match(). Other benchmarks I tried were mostly neutral. This changes register allocation in subtle ways, update the tests for it. 2012-02-20-MachineCPBug.ll was deleted as it's very fragile and the instruction it looked for was gone already (but the FileCheck pattern picked up unrelated stuff). llvm-svn: 184105
* Make SplitAnalysis::UseSlots private.Jakob Stoklund Olesen2012-01-121-3/+7
| | | | llvm-svn: 148031
* Exclusively use SplitAnalysis::getLastSplitPoint().Jakob Stoklund Olesen2012-01-111-1/+4
| | | | | | | | | Delete the alternative implementation in LiveIntervalAnalysis. These functions computed the same thing, but SplitAnalysis caches the result. llvm-svn: 147911
* Hoist back-copies to the least busy dominator.Jakob Stoklund Olesen2011-09-141-0/+5
| | | | | | | | | | | | | | | | When a back-copy is hoisted to the nearest common dominator, keep looking up the dominator tree for a less loopy dominator, and place the back-copy there instead. Don't do this when a single existing back-copy dominates all the others. Assume the client knows what he is doing, and keep the dominating back-copy. This prevents us from hoisting back-copies into loops in most cases. If a value is defined in a loop with multiple exits, we may still hoist back-copies into that loop. That is the speed/size tradeoff. llvm-svn: 139698
* Distinguish complex mapped values from forced recomputation.Jakob Stoklund Olesen2011-09-131-22/+14
| | | | | | | | | | | | | | | | | | When a ParentVNI maps to multiple defs in a new interval, its live range may still be derived directly from RegAssign by transferValues(). On the other hand, when instructions have been rematerialized or hoisted, it may be necessary to completely recompute live ranges using LiveRangeCalc::extend() to all uses. Use a bit in the value map to indicate that a live range must be recomputed. Rename markComplexMapped() to forceRecompute(). This fixes some live range verification errors when -split-spill-mode=size hoists back-copies by recomputing source ranges when RegAssign kills can't be moved. llvm-svn: 139660
* Implement -split-spill-mode=size.Jakob Stoklund Olesen2011-09-131-0/+8
| | | | | | | | | | Whenever the complement interval is defined by multiple copies of the same value, hoist those back-copies to the nearest common dominator. This ensures that at most one copy is inserted per value in the complement inteval, and no phi-defs are needed. llvm-svn: 139651
* Add SplitEditor::markOverlappedComplement().Jakob Stoklund Olesen2011-09-131-0/+15
| | | | | | | | This function is used to flag values where the complement interval may overlap other intervals. Call it from overlapIntv, and use the flag to fully recompute those live ranges in transferValues(). llvm-svn: 139612
* Eliminate the extendRange() wrapper.Jakob Stoklund Olesen2011-09-131-4/+0
| | | | llvm-svn: 139608
* Use a separate LiveRangeCalc for the complement in spill modes.Jakob Stoklund Olesen2011-09-131-2/+11
| | | | | | | | | | The complement interval may overlap the other intervals created, so use a separate LiveRangeCalc instance to compute its live range. A LiveRangeCalc instance can only be shared among non-overlapping intervals. llvm-svn: 139603
* Extract live range calculations from SplitKit.Jakob Stoklund Olesen2011-09-131-70/+3
| | | | | | | | SplitKit will soon need two copies of these data structures, and the algorithms will also be useful when LiveIntervalAnalysis becomes independent of LiveVariables. llvm-svn: 139572
* Add an interface for SplitKit complement spill modes.Jakob Stoklund Olesen2011-09-121-1/+34
| | | | | | | | | | | | | | | | | | | | | | | | | SplitKit always computes a complement live range to cover the places where the original live range was live, but no explicit region has been allocated. Currently, the complement live range is created to be as small as possible - it never overlaps any of the regions. This minimizes register pressure, but if the complement is going to be spilled anyway, that is not very important. The spiller will eliminate redundant spills, and hoist others by making the spill slot live range overlap some of the regions created by splitting. Stack slots are cheap. This patch adds the interface to enable spill modes in SplitKit. In spill mode, SplitKit will assume that the complement is going to spill, so it will allow it to overlap regions in order to avoid back-copies. By doing some of the spiller's work early, the complement live range becomes simpler. In some cases, it can become much simpler because no extra PHI-defs are required. This will speed up both splitting and spilling. This is only the interface to enable spill modes, no implementation yet. llvm-svn: 139500
* Update comments to reflect some (not so) recent changes.Jakob Stoklund Olesen2011-09-121-4/+5
| | | | llvm-svn: 139498
* Delete getMultiUseBlocks and splitSingleBlocks.Jakob Stoklund Olesen2011-08-051-9/+0
| | | | | | | These functions are no longer used, and they are easily replaced with a loop calling shouldSplitSingleBlock and splitSingleBlock. llvm-svn: 136993
* Split around single instructions to enable register class inflation.Jakob Stoklund Olesen2011-08-051-0/+10
| | | | | | | | | | | | | 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
* Rename {First,Last}Use to {First,Last}Instr.Jakob Stoklund Olesen2011-08-021-3/+3
| | | | | | | With a 'FirstDef' field right there, it is very confusing that FirstUse refers to an instruction that may be a def. llvm-svn: 136739
* Add a BlockInfo::FirstDef field.Jakob Stoklund Olesen2011-08-021-0/+1
| | | | | | | | | | | This is either an invalid SlotIndex, or valno->def for the first value defined inside the block. PHI values are not counted as defined inside the block. The FirstDef field will be used when estimating the cost of spilling around a block. llvm-svn: 136736
* Delete BlockInfo::LiveThrough. It wasn't used any more.Jakob Stoklund Olesen2011-08-021-1/+0
| | | | llvm-svn: 136735
* Extract parts of RAGreedy::splitAroundRegion as SplitKit methods.Jakob Stoklund Olesen2011-07-151-0/+36
| | | | | | | | | | | 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 r134047 now that the world is ready for it.Jakob Stoklund Olesen2011-06-301-0/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-10/+0
| | | | | | miscompile. llvm-svn: 134053
* Rewrite RAGreedy::splitAroundRegion, now with cool ASCII art.Jakob Stoklund Olesen2011-06-291-0/+10
| | | | | | | | | | | | | | | | | | | | 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
* Reapply r132245 with a fix for the bug that broke the darwin9/i386 build.Jakob Stoklund Olesen2011-05-301-6/+15
| | | | llvm-svn: 132309
OpenPOWER on IntegriCloud