aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Utils/LoopUnrollPeel.cpp
AgeCommit message (Collapse)AuthorFilesLines
2020-07-31[Loop Peeling] Separate the Loop Peeling Utilities from the Loop Unrolling ↵Sidharth Baveja1-798/+0
Utilities Summary: This patch separates the Loop Peeling Utilities from Loop Unrolling. The reason for this change is that Loop Peeling is no longer only being used by loop unrolling; Patch D82927 introduces loop peeling with fusion, such that loops can be modified to have to same trip count, making them legal to be peeled. Reviewed By: Meinersbur Differential Revision: https://reviews.llvm.org/D83056
2020-07-10[NFC] Separate Peeling Properties into its own struct (re-land after minor fix)Sidharth Baveja1-12/+13
Summary: This patch separates the peeling specific parameters from the UnrollingPreferences, and creates a new struct called PeelingPreferences. Functions which used the UnrollingPreferences struct for peeling have been updated to use the PeelingPreferences struct. Author: sidbav (Sidharth Baveja) Reviewers: Whitney (Whitney Tsang), Meinersbur (Michael Kruse), skatkov (Serguei Katkov), ashlykov (Arkady Shlykov), bogner (Justin Bogner), hfinkel (Hal Finkel), anhtuyen (Anh Tuyen Tran), nikic (Nikita Popov) Reviewed By: Meinersbur (Michael Kruse) Subscribers: fhahn (Florian Hahn), hiraditya (Aditya Kumar), llvm-commits, LLVM Tag: LLVM Differential Revision: https://reviews.llvm.org/D80580
2020-07-08Revert "[NFC] Separate Peeling Properties into its own struct"Nikita Popov1-13/+12
This reverts commit 0369dc98f958a1ca2ec05f1897f091129bb16e8a. Many failing tests.
2020-07-08[NFC] Separate Peeling Properties into its own structSidharth Baveja1-12/+13
Summary: This patch makes the peeling properties of the loop accessible by other loop transformations. Author: sidbav (Sidharth Baveja) Reviewers: Whitney (Whitney Tsang), Meinersbur (Michael Kruse), skatkov (Serguei Katkov), ashlykov (Arkady Shlykov), bogner (Justin Bogner), hfinkel (Hal Finkel) Reviewed By: Meinersbur (Michael Kruse) Subscribers: fhahn (Florian Hahn), hiraditya (Aditya Kumar), llvm-commits, LLVM Tag: LLVM Differential Revision: https://reviews.llvm.org/D80580
2020-07-08Revert "[NFC] Separate Peeling Properties into its own struct"Anh Tuyen Tran1-13/+12
This reverts commit fead250b439bbd4ec0f21e6a52d0c174e5fcdf5a.
2020-07-08[NFC] Separate Peeling Properties into its own structAnh Tuyen Tran1-12/+13
Summary: This patch makes the peeling properties of the loop accessible by other loop transformations. Author: sidbav (Sidharth Baveja) Reviewers: Whitney (Whitney Tsang), Meinersbur (Michael Kruse), skatkov (Serguei Katkov), ashlykov (Arkady Shlykov), bogner (Justin Bogner), hfinkel (Hal Finkel) Reviewed By: Meinersbur (Michael Kruse) Subscribers: fhahn (Florian Hahn), hiraditya (Aditya Kumar), llvm-commits, LLVM Tag: LLVM Differential Revision: https://reviews.llvm.org/D80580
2020-06-22Revert "[Peeling] Extend the scope of peeling a bit"Serguei Katkov1-1/+1
This reverts commit 29b2c1ca72096ca06415b5e626e6728c42ef1e74. The patch causes the DT verifier failure like: DominatorTree is different than a freshly computed one! Not sure the patch itself it wrong but revert to investigate the failure.
2020-06-22[Peeling] Extend the scope of peeling a bitSerguei Katkov1-1/+1
Currently we allow peeling of the loops if there is a exiting latch block and all other exits are blocks ending with deopt. Actually we want that exit would end up with deopt unconditionally but it is not required that exit itself ends with deopt. Reviewers: reames, ashlykov, fhahn, apilipenko, fedor.sergeev Reviewed By: apilipenko Subscribers: hiraditya, zzheng, dantrushin, llvm-commits Differential Revision: https://reviews.llvm.org/D81140
2020-03-12[LoopPeel] Turn incorrect assert into a checkMax Kazantsev1-4/+3
Summary: This patch replaces incorrectt assert with a check. Previously it asserts that if SCEV cannot prove `isKnownPredicate(A != B)`, then it should be able to prove `isKnownPredicate(A == B)`. Both these fact may be not provable. It is shown in the provided test: Could not prove: `{-294,+,-2}<%bb1> != 0` Asserting: `{-294,+,-2}<%bb1> == 0` Obviously, this SCEV is not equal to zero, but 0 is in its range so we cannot also prove that it is not zero. Instead of assert, we should be checking the required conditions explicitly. Reviewers: lebedev.ri, fhahn, sanjoy, fedor.sergeev Reviewed By: lebedev.ri Subscribers: hiraditya, zzheng, javed.absar, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D76050
2020-03-02[Loop Peeling] Add possibility to enable peeling on loop nests.Arkady Shlykov1-3/+14
Summary: Current peeling implementation bails out in case of loop nests. The patch introduces a field in TargetTransformInfo structure that certain targets can use to relax the constraints if it's profitable (disabled by default). Also additional option is added to enable peeling manually for experimenting and testing purposes. Reviewers: fhahn, lebedev.ri, xbolva00 Reviewed By: xbolva00 Subscribers: RKSimon, xbolva00, hiraditya, zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D70304
2020-01-16Revert "[Loop Peeling] Add possibility to enable peeling on loop nests."Arkady Shlykov1-4/+2
This reverts commit 3f3017e because there's a failure on peel-loop-nests.ll with LLVM_ENABLE_EXPENSIVE_CHECKS on. Differential Revision: https://reviews.llvm.org/D70304
2020-01-15[Loop Peeling] Add possibility to enable peeling on loop nests.Arkady Shlykov1-2/+4
Summary: Current peeling implementation bails out in case of loop nests. The patch introduces a field in TargetTransformInfo structure that certain targets can use to relax the constraints if it's profitable (disabled by default). Also additional option is added to enable peeling manually for experimenting and testing purposes. Reviewers: fhahn, lebedev.ri, xbolva00 Reviewed By: xbolva00 Subscribers: xbolva00, hiraditya, zzheng, llvm-commits Differential Revision: https://reviews.llvm.org/D70304
2019-12-22[Transforms] Fixes -Wrange-loop-analysis warningsMark de Wever1-1/+1
This avoids new warnings due to D68912 adds -Wrange-loop-analysis to -Wall. Differential Revision: https://reviews.llvm.org/D71810
2019-11-06[LoopUnroll] countToEliminateCompares(): fix handling of [in]equality ↵Roman Lebedev1-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
2019-08-22[Loop Peeling] Fix silly bug in metadata update.Serguei Katkov1-6/+6
We must update loop metedata before we moved to parent loop if it is present. llvm-svn: 369637
2019-08-02[Loop Peeling] Do not close further unroll/peel if profile based peeling was ↵Serguei Katkov1-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
2019-07-25[Loop Peeling] Fix idom detection algorithm.Serguei Katkov1-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
2019-07-22[Loop Peeling] Fix the handling of branch weights of peeled off branches.Serguei Katkov1-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
2019-07-19[Loop Peeling] Enable peeling of multiple exits by default.Serguei Katkov1-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
2019-07-18[LoopInfo] Use early return in branch weight update functions. NFC.Serguei Katkov1-29/+30
llvm-svn: 366411
2019-07-15[Loop Peeling] Fix the bug with IDom setting for exit loopsSerguei Katkov1-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
2019-07-15[Loop Peeling] Enable peeling for loops with multiple exitsSerguei Katkov1-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
2019-07-09[Loop Peeling] Add support for peeling of loops with multiple exitsSerguei Katkov1-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
2019-07-04[LoopPeel] Some small comment update. NFC.Serguei Katkov1-3/+3
Follow-up change of comment after https://reviews.llvm.org/D63917 is landed. llvm-svn: 365107
2019-07-03[LoopPeel] Re-factor llvm::peelLoop method. NFC.Serguei Katkov1-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
2019-06-17PHINode: introduce setIncomingValueForBlock() function, and use it.Whitney Tsang1-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
2019-05-08[MemorySSA] Teach LoopSimplify to preserve MemorySSA.Alina Sbirlea1-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
2019-02-14[LoopUnrollPeel] Add case where we should forget the peeled loop from SCEV.Florian Hahn1-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
2019-01-19Update the file headers across all of the LLVM projects in the monorepoChandler Carruth1-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
2018-12-21[LoopUnroll] Don't verify domtree by default with +Asserts.Eli Friedman1-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
2018-09-26Remove LoopID metadata from the branch instructionVyacheslav Zakharin1-1/+5
that follows the peeled iterations. Differential Revision: https://reviews.llvm.org/D52176 llvm-svn: 343054
2018-07-30Remove trailing spaceFangrui Song1-2/+2
sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
2018-05-14Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen1-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
2018-05-01Remove \brief commands from doxygen comments.Adrian Prantl1-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
2018-04-18[LoopUnroll] Only peel if a predicate becomes known in the loop body.Florian Hahn1-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
2018-04-06[LoopUnroll] Make LoopPeeling respect the AllowPeeling preference.Chad Rosier1-10/+14
The SimpleLoopUnrollPass isn't suppose to perform loop peeling. Differential Revision: https://reviews.llvm.org/D45334 llvm-svn: 329395
2018-04-03peel loops with runtime small trip countsIkhlas Ajbar1-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
2018-03-30Revert "peel loops with runtime small trip counts"Krzysztof Parzyszek1-6/+1
This reverts commit r328854, it breaks some Hexagon tests. llvm-svn: 328875
2018-03-30peel loops with runtime small trip countsIkhlas Ajbar1-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
2018-03-27[LoopUnroll][NFC] Remove redundant canPeel checkMax Kazantsev1-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
2018-03-15[LoopUnroll] Peel off iterations if it makes conditions true/false.Florian Hahn1-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
2018-02-28[Dominators] Remove verifyDomTree and add some verifying for Post Dom TreesDavid Green1-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
2018-01-19[NFC] fix trivial typos in commentsHiroshi Inoue1-1/+1
"the the" -> "the" llvm-svn: 322934
2017-12-22Add hasProfileData() to check if a function has profile data. NFC.Easwaran Raman1-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
2017-10-27[Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko1-9/+19
warnings; other minor fixes (NFC). llvm-svn: 316724
2017-04-17[LoopPeeling] Get rid of Phis that become invariant after N stepsMax Kazantsev1-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
2017-04-17[LoopPeeling] Fix condition for phi-eliminating peelingMax Kazantsev1-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
2017-03-26[LoopUnroll] Remap references in peeled iterationSerge Pavlov1-4/+5
References in cloned blocks must be remapped prior to dominator calculation. Differential Revision: https://reviews.llvm.org/D31281 llvm-svn: 298811
2017-03-16[LoopUnroll] Don't peel loops where the latch isn't the exiting blockMichael Kuperstein1-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
2017-03-07[LoopUnrolling] Fix loop size check for peelingSanjoy Das1-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
generated by cgit v1.1 at 2025-09-30 20:01:24 +0000