summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [Transforms] Fixes -Wrange-loop-analysis warningsMark de Wever2019-12-221-1/+1
| | | | | | This avoids new warnings due to D68912 adds -Wrange-loop-analysis to -Wall. Differential Revision: https://reviews.llvm.org/D71810
* [LoopUnroll] countToEliminateCompares(): fix handling of [in]equality ↵Roman Lebedev2019-11-061-16/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | predicates (PR43840) Summary: I believe this bisects to https://reviews.llvm.org/D44983 (`[LoopUnroll] Only peel if a predicate becomes known in the loop body.`) While that revision did contain tests that showed arguably-subpar peeling for [in]equality predicates that [not] happen in the middle of the loop, it also disabled peeling for the *first* loop iteration, because latch would be canonicalized to [in]equality comparison.. That was intentional as per https://reviews.llvm.org/D44983#1059583. I'm not 100% sure that i'm using correct checks here, but this fix appears to be going in the right direction.. Let me know if i'm missing some checks here.. Fixes [[ https://bugs.llvm.org/show_bug.cgi?id=43840 | PR43840 ]]. Reviewers: fhahn, mkazantsev, efriedma Reviewed By: fhahn Subscribers: xbolva00, hiraditya, zzheng, llvm-commits, fhahn Tags: #llvm Differential Revision: https://reviews.llvm.org/D69617
* [Loop Peeling] Fix silly bug in metadata update.Serguei Katkov2019-08-221-6/+6
| | | | | | | We must update loop metedata before we moved to parent loop if it is present. llvm-svn: 369637
* [Loop Peeling] Do not close further unroll/peel if profile based peeling was ↵Serguei Katkov2019-08-021-6/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | not used. Current peeling cost model can decide to peel off not all iterations but only some of them to eliminate conditions on phi. At the same time if any peeling happens the door for further unroll/peel optimizations on that loop closes because the part of the code thinks that if peeling happened it is profile based peeling and all iterations are peeled off. To resolve this inconsistency the patch provides the flag which states whether the full peeling basing on profile is enabled or not and peeling cost model is able to modify this field like it does not PeelCount. In a separate patch I will introduce an option to allow/disallow peeling basing on profile. To avoid infinite loop peeling the patch tracks the total number of peeled iteration through llvm.loop.peeled.count loop metadata. Reviewers: reames, fhahn Reviewed By: reames Subscribers: hiraditya, zzheng, dmgreen, llvm-commits Differential Revision: https://reviews.llvm.org/D64972 llvm-svn: 367647
* [Loop Peeling] Fix idom detection algorithm.Serguei Katkov2019-07-251-1/+20
| | | | | | | | | | | | | | | | | | | | | | We'd like to determine the idom of exit block after peeling one iteration. Let Exit is exit block. Let ExitingSet - is a set of predecessors of Exit block. They are exiting blocks. Let Latch' and ExitingSet' are copies after a peeling. We'd like to find an idom'(Exit) - idom of Exit after peeling. It is an evident that idom'(Exit) will be the nearest common dominator of ExitingSet and ExitingSet'. idom(Exit) is a nearest common dominator of ExitingSet. idom(Exit)' is a nearest common dominator of ExitingSet'. Taking into account that we have a single Latch, Latch' will dominate Header and idom(Exit). So the idom'(Exit) is nearest common dominator of idom(Exit)' and Latch'. All these basic blocks are in the same loop, so what we find is (nearest common dominator of idom(Exit) and Latch)'. Reviewers: reames, fhahn Reviewed By: reames Subscribers: hiraditya, zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D65292 llvm-svn: 367044
* [Loop Peeling] Fix the handling of branch weights of peeled off branches.Serguei Katkov2019-07-221-62/+41
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Current algorithm to update branch weights of latch block and its copies is based on the assumption that number of peeling iterations is approximately equal to trip count. However it is not correct. According to profitability check in one case we can decide to peel in case it helps to reduce the number of phi nodes. In this case the number of peeled iteration can be less then estimated trip count. This patch introduces another way to set the branch weights to peeled of branches. Let F is a weight of the edge from latch to header. Let E is a weight of the edge from latch to exit. F/(F+E) is a probability to go to loop and E/(F+E) is a probability to go to exit. Then, Estimated TripCount = F / E. For I-th (counting from 0) peeled off iteration we set the the weights for the peeled latch as (TC - I, 1). It gives us reasonable distribution, The probability to go to exit 1/(TC-I) increases. At the same time the estimated trip count of remaining loop reduces by I. As a result after peeling off N iteration the weights will be (F - N * E, E) and trip count of loop becomes F / E - N or TC - N. The idea is taken from the review of the patch D63918 proposed by Philip. Reviewers: reames, mkuper, iajbar, fhahn Reviewed By: reames Subscribers: hiraditya, zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D64235 llvm-svn: 366665
* [Loop Peeling] Enable peeling of multiple exits by default.Serguei Katkov2019-07-191-1/+1
| | | | | | | | | | | | Enable loop peeling with multiple exits where all non-latch exits ends up with deopt by default. Reviewers: reames, fhahn Reviewed By: reames Subscribers: xbolva00, hiraditya, zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D64619 llvm-svn: 366542
* [LoopInfo] Use early return in branch weight update functions. NFC.Serguei Katkov2019-07-181-29/+30
| | | | llvm-svn: 366411
* [Loop Peeling] Fix the bug with IDom setting for exit loopsSerguei Katkov2019-07-151-3/+18
| | | | | | | | | | | | | It is possible that loop exit has two predecessors in a loop body. In this case after the peeling the iDom of the exit should be a clone of iDom of original exit but no a clone of a block coming to this exit. Reviewers: reames, fhahn Reviewed By: reames Subscribers: hiraditya, zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D64618 llvm-svn: 366050
* [Loop Peeling] Enable peeling for loops with multiple exitsSerguei Katkov2019-07-151-0/+20
| | | | | | | | | | | | | | | This CL enables peeling of the loop with multiple exits where one exit should be from latch and others are basic blocks with call to deopt. The peeling is enabled under the flag which is false by default. Reviewers: reames, mkuper, iajbar, fhahn Reviewed By: reames Subscribers: xbolva00, hiraditya, zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D63923 llvm-svn: 366048
* [Loop Peeling] Add support for peeling of loops with multiple exitsSerguei Katkov2019-07-091-22/+27
| | | | | | | | | | | | | | | | | | | | | This patch modifies the loop peeling transformation so that it does not expect that there is only one loop exit from latch. It modifies only transformation. Update of branch weights remains only for exit from latch. The motivation is that in follow-up patch I plan to enable loop peeling for loops with multiple exits but only if other exits then from latch one goes to block with call to deopt. For now this patch is NFC. Reviewers: reames, mkuper, iajbar, fhahn Reviewed By: reames, fhahn Subscribers: zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D63921 llvm-svn: 365441
* [LoopPeel] Some small comment update. NFC.Serguei Katkov2019-07-041-3/+3
| | | | | | | Follow-up change of comment after https://reviews.llvm.org/D63917 is landed. llvm-svn: 365107
* [LoopPeel] Re-factor llvm::peelLoop method. NFC.Serguei Katkov2019-07-031-25/+49
| | | | | | | | | | | Extract code dealing with branch weights in separate functions. Reviewers: reames, mkuper, iajbar, fhahn Reviewed By: reames, fhahn Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D63917 llvm-svn: 365002
* PHINode: introduce setIncomingValueForBlock() function, and use it.Whitney Tsang2019-06-171-1/+1
| | | | | | | | | | | | | | | | Summary: There is PHINode::getBasicBlockIndex() and PHINode::setIncomingValue() but no function to replace incoming value for a specified BasicBlock* predecessor. Clearly, there are a lot of places that could use that functionality. Reviewer: craig.topper, lebedev.ri, Meinersbur, kbarton, fhahn Reviewed By: Meinersbur, fhahn Subscribers: fhahn, hiraditya, zzheng, jsji, llvm-commits Tag: LLVM Differential Revision: https://reviews.llvm.org/D63338 llvm-svn: 363566
* [MemorySSA] Teach LoopSimplify to preserve MemorySSA.Alina Sbirlea2019-05-081-1/+1
| | | | | | | | | | | | | | | Summary: Preserve MemorySSA in LoopSimplify, in the old pass manager, if the analysis is available. Do not preserve it in the new pass manager. Update tests. Subscribers: nemanjai, jlebar, javed.absar, Prazek, kbarton, zzheng, jsji, llvm-commits, george.burgess.iv, chandlerc Tags: #llvm Differential Revision: https://reviews.llvm.org/D60833 llvm-svn: 360270
* [LoopUnrollPeel] Add case where we should forget the peeled loop from SCEV.Florian Hahn2019-02-141-10/+8
| | | | | | | | | | | | | | | | | | | | The test case requires the peeled loop to be forgotten after peeling, even though it does not have a parent. When called via the unroller, SE->forgetTopmostLoop is also called, so the test case would also pass without any SCEV invalidation, but peelLoop is exposed as utility function. Also, in the test case, simplifyLoop will make changes, removing the loop from SCEV, but it is better to not rely on this behavior. Reviewers: sanjoy, mkazantsev Reviewed By: mkazantsev Tags: #llvm Differential Revision: https://reviews.llvm.org/D58192 llvm-svn: 354031
* 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
* [LoopUnroll] Don't verify domtree by default with +Asserts.Eli Friedman2018-12-211-0/+2
| | | | | | | | | | This verification is linear in the size of the function, so it can cause a quadratic compile-time explosion in a function with many loops to unroll. Differential Revision: https://reviews.llvm.org/D54732 llvm-svn: 349871
* Remove LoopID metadata from the branch instructionVyacheslav Zakharin2018-09-261-1/+5
| | | | | | | | that follows the peeled iterations. Differential Revision: https://reviews.llvm.org/D52176 llvm-svn: 343054
* Remove trailing spaceFangrui Song2018-07-301-2/+2
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-11/+14
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-3/+3
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* [LoopUnroll] Only peel if a predicate becomes known in the loop body.Florian Hahn2018-04-181-7/+25
| | | | | | | | | | | | | If a predicate does not become known after peeling, peeling is unlikely to be beneficial. Reviewers: mcrosier, efriedma, mkazantsev, junbuml Reviewed By: mkazantsev Differential Revision: https://reviews.llvm.org/D44983 llvm-svn: 330250
* [LoopUnroll] Make LoopPeeling respect the AllowPeeling preference.Chad Rosier2018-04-061-10/+14
| | | | | | | | The SimpleLoopUnrollPass isn't suppose to perform loop peeling. Differential Revision: https://reviews.llvm.org/D45334 llvm-svn: 329395
* peel loops with runtime small trip countsIkhlas Ajbar2018-04-031-2/+7
| | | | | | | | | | For Hexagon, peeling loops with small runtime trip count is beneficial for our benchmarks. We set PeelCount in HexagonTargetInfo.cpp and we use PeelCount set by the target for computing the desired peel count. Differential Revision: https://reviews.llvm.org/D44880 llvm-svn: 329042
* Revert "peel loops with runtime small trip counts"Krzysztof Parzyszek2018-03-301-6/+1
| | | | | | This reverts commit r328854, it breaks some Hexagon tests. llvm-svn: 328875
* peel loops with runtime small trip countsIkhlas Ajbar2018-03-301-1/+6
| | | | | | | | | | For Hexagon, peeling loops with small runtime trip count is beneficial for our benchmarks. We set PeelCount in HexagonTargetInfo.cpp and we use PeelCount set by the target for computing the desired peel count. Differential Revision: https://reviews.llvm.org/D44880 llvm-svn: 328854
* [LoopUnroll][NFC] Remove redundant canPeel checkMax Kazantsev2018-03-271-2/+2
| | | | | | | | | | | | We check `canPeel` twice: when evaluating the number of iterations to be peeled and within the method `peelLoop` that performs peeling. This method is only executed if the calculated peel count is positive. Thus, the check in `peelLoop` can never fail. This patch replaces this check with an assert. Differential Revision: https://reviews.llvm.org/D44919 Reviewed By: fhahn llvm-svn: 328615
* [LoopUnroll] Peel off iterations if it makes conditions true/false.Florian Hahn2018-03-151-4/+89
| | | | | | | | | | | | | | | If the loop body contains conditions of the form IndVar < #constant, we can remove the checks by peeling off #constant iterations. This improves codegen for PR34364. Reviewers: mkuper, mkazantsev, efriedma Reviewed By: mkazantsev Differential Revision: https://reviews.llvm.org/D43876 llvm-svn: 327671
* [Dominators] Remove verifyDomTree and add some verifying for Post Dom TreesDavid Green2018-02-281-4/+1
| | | | | | | | | | | | Removes verifyDomTree, using assert(verify()) everywhere instead, and changes verify a little to always run IsSameAsFreshTree first in order to print good output when we find errors. Also adds verifyAnalysis for PostDomTrees, which will allow checking of PostDomTrees it the same way we check DomTrees and MachineDomTrees. Differential Revision: https://reviews.llvm.org/D41298 llvm-svn: 326315
* [NFC] fix trivial typos in commentsHiroshi Inoue2018-01-191-1/+1
| | | | | | "the the" -> "the" llvm-svn: 322934
* Add hasProfileData() to check if a function has profile data. NFC.Easwaran Raman2017-12-221-1/+1
| | | | | | | | | | | | | | | | | | | Summary: This replaces calls to getEntryCount().hasValue() with hasProfileData that does the same thing. This refactoring is useful to do before adding synthetic function entry counts but also a useful cleanup IMO even otherwise. I have used hasProfileData instead of hasRealProfileData as David had earlier suggested since I think profile implies "real" and I use the phrase "synthetic entry count" and not "synthetic profile count" but I am fine calling it hasRealProfileData if you prefer. Reviewers: davidxl, silvas Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41461 llvm-svn: 321331
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-271-9/+19
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 316724
* [LoopPeeling] Get rid of Phis that become invariant after N stepsMax Kazantsev2017-04-171-20/+83
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch is a generalization of the improvement introduced in rL296898. Previously, we were able to peel one iteration of a loop to get rid of a Phi that becomes an invariant on the 2nd iteration. In more general case, if a Phi becomes invariant after N iterations, we can peel N times and turn it into invariant. In order to do this, we for every Phi in loop's header we define the Invariant Depth value which is calculated as follows: Given %x = phi <Inputs from above the loop>, ..., [%y, %back.edge]. If %y is a loop invariant, then Depth(%x) = 1. If %y is a Phi from the loop header, Depth(%x) = Depth(%y) + 1. Otherwise, Depth(%x) is infinite. Notice that if we peel a loop, all Phis with Depth = 1 become invariants, and all other Phis with finite depth decrease the depth by 1. Thus, peeling N first iterations allows us to turn all Phis with Depth <= N into invariants. Reviewers: reames, apilipenko, mkuper, skatkov, anna, sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31613 llvm-svn: 300446
* [LoopPeeling] Fix condition for phi-eliminating peelingMax Kazantsev2017-04-171-1/+2
| | | | | | | | | | | | | | | | | When peeling loops basing on phis becoming invariants, we make a wrong loop size check. UP.Threshold should be compared against the total numbers of instructions after the transformation, which is equal to 2 * LoopSize in case of peeling one iteration. We should also check that the maximum allowed number of peeled iterations is not zero. Reviewers: sanjoy, anna, reames, mkuper Reviewed By: mkuper Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31753 llvm-svn: 300441
* [LoopUnroll] Remap references in peeled iterationSerge Pavlov2017-03-261-4/+5
| | | | | | | | | References in cloned blocks must be remapped prior to dominator calculation. Differential Revision: https://reviews.llvm.org/D31281 llvm-svn: 298811
* [LoopUnroll] Don't peel loops where the latch isn't the exiting blockMichael Kuperstein2017-03-161-0/+7
| | | | | | | | | Peeling assumed this doesn't happen, but didn't check it. This fixes PR32178. Differential Revision: https://reviews.llvm.org/D30757 llvm-svn: 297993
* [LoopUnrolling] Fix loop size check for peelingSanjoy Das2017-03-071-1/+3
| | | | | | | | | | | | | | | | | | Summary: We should check if loop size allows us to peel at least one iteration before we do so. Patch by Max Kazantsev! Reviewers: sanjoy, mkuper, efriedma Reviewed By: mkuper Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30632 llvm-svn: 297122
* Fix a compiler warningSanjoy Das2017-03-031-1/+2
| | | | llvm-svn: 296903
* [LoopUnrolling] Peel loops with invariant backedge Phi inputSanjoy Das2017-03-031-0/+25
| | | | | | | | | | | | | | | | | | | | | Summary: If a loop contains a Phi node which has an invariant input from back edge, it is profitable to peel such loops (rather than unroll them) to use the advantage that this Phi is always invariant starting from 2nd iteration. After the 1st iteration is peeled, other optimizations can potentially simplify calculations with this invariant. Patch by Max Kazantsev! Reviewers: sanjoy, apilipenko, igor-laevsky, anna, mkuper, reames Reviewed By: mkuper Subscribers: mkuper, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D30161 llvm-svn: 296898
* [LoopUnrolling] Re-prioritize Peeling and Partial unrollingSanjoy Das2017-03-031-1/+7
| | | | | | | | | | | | | | | | | | | | | | | Summary: In current implementation the loop peeling happens after trip-count based partial unrolling and may sometimes not happen at all due to it (for example, if trip count is known, but UP.Partial = false). This is generally bad, the more than there are some situations where peeling is profitable even if the partial unrolling is disabled. This patch is a NFC which reorders peeling and partial unrolling application and prepares the code for implementation of the said optimizations. Patch by Max Kazantsev! Reviewers: sanjoy, anna, reames, apilipenko, igor-laevsky, mkuper Reviewed By: mkuper Subscribers: mkuper, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D30243 llvm-svn: 296897
* Update domtree incrementally in loop peeling.Serge Pavlov2017-01-241-7/+30
| | | | | | | | | With this change dominator tree remains in sync after each step of loop peeling. Differential Revision: https://reviews.llvm.org/D29029 llvm-svn: 292895
* Preserve domtree and loop-simplify for runtime unrolling.Eli Friedman2017-01-181-2/+13
| | | | | | | | | | | | | | | | | Mostly straightforward changes; we just didn't do the computation before. One sort of interesting change in LoopUnroll.cpp: we weren't handling dominance for children of the loop latch correctly, but foldBlockIntoPredecessor hid the problem for complete unrolling. Currently punting on loop peeling; made some minor changes to isolate that problem to LoopUnrollPeel.cpp. Adds a flag -unroll-verify-domtree; it verifies the domtree immediately after we finish updating it. This is on by default for +Asserts builds. Differential Revision: https://reviews.llvm.org/D28073 llvm-svn: 292447
* Make sure total loop body weight is preserved in loop peelingXin Tong2017-01-021-8/+17
| | | | | | | | | | | | | | | Summary: Regardless how the loop body weight is distributed, we should preserve total loop body weight. i.e. we should have same weight reaching the body of the loop or its duplicates in peeled and unpeeled case. Reviewers: mkuper, davidxl, anemet Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28179 llvm-svn: 290833
* [LoopUnroll] Implement profile-based loop peelingMichael Kuperstein2016-11-301-0/+405
This implements PGO-driven loop peeling. The basic idea is that when the average dynamic trip-count of a loop is known, based on PGO, to be low, we can expect a performance win by peeling off the first several iterations of that loop. Unlike unrolling based on a known trip count, or a trip count multiple, this doesn't save us the conditional check and branch on each iteration. However, it does allow us to simplify the straight-line code we get (constant-folding, etc.). This is important given that we know that we will usually only hit this code, and not the actual loop. This is currently disabled by default. Differential Revision: https://reviews.llvm.org/D25963 llvm-svn: 288274
OpenPOWER on IntegriCloud