summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopPredication.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Revert "[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC)."Florian Hahn2020-01-041-1/+1
| | | | | This reverts commit 51ef53f3bd23559203fe9af82ff2facbfedc1db3, as it breaks some bots.
* [SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).Florian Hahn2020-01-041-1/+1
| | | | | | | | | | | | SCEVExpander modifies the underlying function so it is more suitable in Transforms/Utils, rather than Analysis. This allows using other transform utils in SCEVExpander. Reviewers: sanjoy.google, efriedma, reames Reviewed By: sanjoy.google Differential Revision: https://reviews.llvm.org/D71537
* [LoopPred] Robustly handle partially unswitched loopsPhilip Reames2019-11-211-0/+29
| | | | We may end up with a case where we have a widenable branch above the loop, but not all widenable branches within the loop have been removed. Since a widenable branch inhibit SCEVs ability to reason about exit counts (by design), we have a tradeoff between effectiveness of this optimization and allowing future widening of the branches within the loop. LoopPred is thought to be one of the most important optimizations for range check elimination, so let's pay the cost.
* [NFC] Factor out utilities for manipulating widenable branchesPhilip Reames2019-11-191-8/+2
| | | | | | With the widenable condition construct, we have the ability to reason about branches which can be 'widened' (i.e. made to fail more often). We've got a couple o transforms which leverage this. This patch just cleans up the API a bit. This is prep work for generalizing our definition of a widenable branch slightly. At the moment "br i1 (and A, wc()), ..." is considered widenable, but oddly, neither "br i1 (and wc(), B), ..." or "br i1 wc(), ..." is. That clearly needs addressed, so first, let's centralize the code in one place.
* [LoopPred] Generalize profitability check to handle unswitch outputPhilip Reames2019-11-191-1/+12
| | | | Unswitch (and other loop transforms) like to generate loop exit blocks with unconditional successors, and phi nodes (LCSSA, or simple multiple exiting blocks sharing an exit). Generalize the "likely very rare exit" check slightly to handle this form.
* [LoopPred/WC] Use a dominating widenable condition to remove analyze loop exitsPhilip Reames2019-11-181-9/+206
| | | | | | | | | | | | This implements a version of the predicateLoopExits transform from IndVarSimplify extended to exploit widenable conditions - and thus be much wider in scope of legality. The code structure ends up being almost entirely different, so I chose to duplicate this into the LoopPredication pass instead of trying to reuse the code in the IndVars. The core notions of the transform are as follows: If we have a widenable condition which controls entry into the loop, we're allowed to widen it arbitrarily. Given that, it's simply a *profitability* question as to what conditions to fold into the widenable branch. To avoid pass ordering issues, we want to avoid widening cases that would otherwise be dischargeable. Or... widen in a form which can still be discharged. Thus, we phrase the transform as selecting one analyzeable exit from the set of analyzeable exits to keep. This avoids creating pass ordering complexities. Since none of the above proves that we actually exit through our analyzeable exits - we might exit through something else entirely - we limit ourselves to cases where a) the latch is analyzeable and b) the latch is predicted taken, and c) the exit being removed is statically cold. Differential Revision: https://reviews.llvm.org/D69830
* Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner2019-11-141-0/+1
| | | | | These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [WC] Fix a subtle bug in our definition of widenable branchPhilip Reames2019-11-061-1/+1
| | | | | | | | | | | | We had a subtle, but nasty bug in our definition of a widenable branch, and thus in the transforms which used that utility. Specifically, we returned true for any branch which included a widenable condition within it's condition, regardless of whether that widenable condition also had other uses. The problem is that the result of the WC() call is defined to be one particular value. As such, all users must agree as to what that value is. If we widen a branch without also updating *all other users* of the WC in the same way, we have broken the required semantics. Most of the textual diff is updating existing transforms not to leave dead uses hanging around. They're largely NFC as the dead instructions would be immediately deleted by other passes. The reason to make these changes is so that the transforms preserve the widenable branch form. In practice, we don't get bitten by this only because it isn't profitable to CSE WC() calls and the lowering pass from guards uses distinct WC calls per branch. Differential Revision: https://reviews.llvm.org/D69916
* [Instruction] Add hasMetadata(Kind) helper [NFC]Philip Reames2019-09-041-1/+1
| | | | | | It's a common idiom, so let's add the obvious wrapper for metadata kinds which are basically booleans. llvm-svn: 370933
* [LoopInfo] Update getExitEdges to accept vector of pairs for non const ↵Serguei Katkov2019-07-091-1/+1
| | | | | | | | | | | | | | | | | | | BasicBlock D63921 requires getExitEdges fills a vector of Edge pairs where BasicBlocks are not constant. The rest Loop API mostly returns non-const BasicBlocks, so to be more consistent with other Loop API getExitEdges is modified to return non-const BasicBlocks as well. This is an alternative solution to D64060. Reviewers: reames, fhahn Reviewed By: reames, fhahn Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D64309 llvm-svn: 365437
* [LoopPred] Stylistic improvement to recently added NE/EQ normalization [NFC]Philip Reames2019-07-091-9/+5
| | | | llvm-svn: 365425
* [LoopPred] Extend LFTR normalization to the inverse EQ casePhilip Reames2019-07-091-0/+5
| | | | | | A while back, I added support for NE latches formed by LFTR. I didn't think that quite through, as LFTR will also produce the inverse EQ form for some loops and I hadn't handled that. This change just adds handling for that case as well. llvm-svn: 365419
* [IRBuilder] Introduce helpers for and/or of multiple values at oncePhilip Reames2019-07-061-14/+4
| | | | | | | | We had versions of this code scattered around, so consolidate into one location. Not strictly NFC since the order of intermediate results may change in some places, but since these operations are associatives, should not change results. llvm-svn: 365259
* [LoopPred] Fix a bug in unconditional latch bailout introduced in r362284Philip Reames2019-06-061-2/+2
| | | | | | This is a really silly bug that even a simple test w/an unconditional latch would have caught. I tried to guard against the case, but put it in the wrong if check. Oops. llvm-svn: 362727
* [LoopPred] Convert a second member function to a static helper [NFC]Philip Reames2019-06-031-14/+15
| | | | | | (And remember to actually mark the first one static.) llvm-svn: 362415
* [LoopPred] Convert member function to free helper function [NFC]Philip Reames2019-06-031-43/+47
| | | | llvm-svn: 362411
* Inline variable into assert to fix unused variable warning.Richard Trieu2019-06-011-3/+3
| | | | llvm-svn: 362285
* [LoopPred] Eliminate a redundant/confusing cover function [NFC]Philip Reames2019-06-011-19/+20
| | | | llvm-svn: 362284
* [LoopPred] Handle a subset of NE comparison based latchesPhilip Reames2019-06-011-21/+33
| | | | | | | | | | | | | | | | | | | | | At the moment, LoopPredication completely bails out if it sees a latch of the form: %cmp = icmp ne %iv, %N br i1 %cmp, label %loop, label %exit OR %cmp = icmp ne %iv.next, %NPlus1 br i1 %cmp, label %loop, label %exit This is unfortunate since this is exactly the form that LFTR likes to produce. So, go ahead and recognize simple cases where we can. For pre-increment loops, we leverage the fact that LFTR likes canonical counters (i.e. those starting at zero) and a (presumed) range fact on RHS to discharge the check trivially. For post-increment forms, the key insight is in remembering that LFTR had to insert a (N+1) for the RHS. CVP can hopefully prove that add nsw/nuw (if there's appropriate range on N to start with). This leaves us both with the post-inc IV and the RHS involving an nsw/nuw add, and SCEV can discharge that with no problem. This does still need to be extended to handle non-one steps, or other harder patterns of variable (but range restricted) starting values. That'll come later. Differential Revision: https://reviews.llvm.org/D62748 llvm-svn: 362282
* [LoopPred] Fix a blatantly obvious bug in r358684Philip Reames2019-04-181-1/+1
| | | | | | The bug is that I didn't check whether the operand of the invariant_loads were themselves invariant. I don't know how this got missed in the patch and review. I even had an unreduced test case locally, and I remember handling this case, but I must have lost it in one of the rebases. Oops. llvm-svn: 358688
* [LoopPredication] Allow predication of loop invariant computations (within ↵Philip Reames2019-04-181-15/+80
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | the loop) The purpose of this patch is to eliminate a pass ordering dependence between LoopPredication and LICM. To understand the purpose, consider the following snippet of code inside some loop 'L' with IV 'i' A = _a.length; guard (i < A) a = _a[i] B = _b.length; guard (i < B); b = _b[i]; ... Z = _z.length; guard (i < Z) z = _z[i] accum += a + b + ... + z; Today, we need LICM to hoist the length loads, LoopPredication to make the guards loop invariant, and TrivialUnswitch to eliminate the loop invariant guard to establish must execute for the next length load. Today, if we can't prove speculation safety, we'd have to iterate these three passes 26 times to reduce this example down to the minimal form. Using the fact that the array lengths are known to be invariant, we can short circuit this iteration. By forming the loop invariant form of all the guards at once, we remove the need for LoopPredication from the iterative cycle. At the moment, we'd still have to iterate LICM and TrivialUnswitch; we'll leave that part for later. As a secondary benefit, this allows LoopPred to expose peeling oppurtunities in a much more obvious manner. See the udiv test changes as an example. If the udiv was not hoistable (i.e. we couldn't prove speculation safety) this would be an example where peeling becomes obviously profitable whereas it wasn't before. A couple of subtleties in the implementation: - SCEV's isSafeToExpand guarantees speculation safety (i.e. let's us expand at a new point). It is not a precondition for expansion if we know the SCEV corresponds to a Value which dominates the requested expansion point. - SCEV's isLoopInvariant returns true for expressions which compute the same value across all iterations executed, regardless of where the original Value is located. (i.e. it can be in the loop) This implies we have a speculation burden to prove before expanding them outside loops. - invariant_loads and AA->pointsToConstantMemory are two cases that SCEV currently does not handle, but meets the SCEV definition of invariance. I plan to sink this part into SCEV once this has baked for a bit. Differential Revision: https://reviews.llvm.org/D60093 llvm-svn: 358684
* [LoopPred] Stop passing around builders [NFC]Philip Reames2019-04-151-31/+49
| | | | | | | | | | | | This is a preparatory patch for D60093. This patch itself is NFC, but while preparing this I noticed and committed a small hoisting change in rL358419. The basic structure of the new scheme is that we pass around the guard ("the using instruction"), and select an optimal insert point by examining operands at each construction point. This seems conceptually a bit cleaner to start with as it isolates the knowledge about insertion safety at the actual insertion point. Note that the non-hoisting path is not actually used at the moment. That's not exercised until D60093 is rebased on this one. Differential Revision: https://reviews.llvm.org/D60718 llvm-svn: 358434
* [LoopPred] Hoist and of predicated checks where legalPhilip Reames2019-04-151-2/+16
| | | | | | If we have multiple range checks which can be predicated, hoist the and of the results outside the loop. This minorly cleans up the resulting IR, but the main motivation is as a building block for D60093. llvm-svn: 358419
* [LoopPredication] Simplify widenable condition handling [NFC]Philip Reames2019-04-021-9/+18
| | | | | | The code doesn't actually need any of the information about the widenable condition at this level. The only thing we need is to ensure the WC call is the last thing anded in, and even that is a quirk we should really look to remove. llvm-svn: 357448
* [LoopPred] Rename a variable to simply a future patch [NFC]Philip Reames2019-04-011-8/+8
| | | | llvm-svn: 357433
* [LoopPred] Be uniform about proving generated conditionsPhilip Reames2019-04-011-0/+3
| | | | | | We'd been optimizing the case where the predicate was obviously true, do the same for the false case. Mostly just for completeness sake, but also may improve compile time in loops which will exit through the guard. Such loops are presumed rare in fastpath code, but may be present down untaken paths, so optimizing for them is still useful. llvm-svn: 357408
* [LoopPred] Delete the old condition expressions if unusedPhilip Reames2019-04-011-0/+5
| | | | | | LoopPredication was replacing the original condition, but leaving the instructions to compute the old conditions around. This would get cleaned up by other passes of course, but we might as well do it eagerly. That also makes the test output less confusing. llvm-svn: 357406
* [LoopPredication] Remove stale TODOPhilip Reames2019-03-291-2/+0
| | | | llvm-svn: 357331
* [LoopPredication] Use the builder's insertion point everywhere [NFC]Philip Reames2019-03-291-11/+11
| | | | llvm-svn: 357330
* [LoopPredication] Support guards expressed as branches by widenable conditionMax Kazantsev2019-01-221-4/+60
| | | | | | | | | | This patch adds support of guards expressed as branches by widenable conditions in Loop Predication. Differential Revision: https://reviews.llvm.org/D56081 Reviewed By: reames llvm-svn: 351805
* [NFC] Factor out some reusable logicMax Kazantsev2019-01-221-15/+21
| | | | llvm-svn: 351794
* 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
* [NFC] Use utility function for guards detectionMax Kazantsev2018-12-261-3/+3
| | | | llvm-svn: 350064
* [LoopPredication] add some simple statsFedor Sergeev2018-10-171-0/+8
| | | | | | | Just adding some useful statistics to LoopPredication pass which was lacking any of these. llvm-svn: 344681
* Remove trailing spaceFangrui Song2018-07-301-3/+3
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-43/+43
| | | | | | | | | | | | | | | | 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
* [LoopPredication] Add profitability check based on BPIAnna Thomas2018-03-221-3/+92
| | | | | | | | | | | | | | | | | | | | | | | | Summary: LoopPredication is not profitable when the loop is known to always exit through some block other than the latch block. A coarse grained latch check can cause loop predication to predicate the loop, and unconditionally deoptimize. However, without predicating the loop, the guard may never fail within the loop during the dynamic execution because the non-latch loop termination condition exits the loop before the latch condition causes the loop to exit. We teach LP about this using BranchProfileInfo pass. Reviewers: apilipenko, skatkov, mkazantsev, reames Reviewed by: skatkov Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D44667 llvm-svn: 328210
* Rename and move utility function getLatchPredicateForGuard. NFC.Serguei Katkov2018-02-091-30/+4
| | | | | | | Rename getLatchPredicateForGuard to more common name getFlippedStrictnessPredicate and move it to ICmpInst class. llvm-svn: 324717
* [Loop Predication] Teach LP about reverse loops with uge and sge latch ↵Serguei Katkov2018-02-081-5/+8
| | | | | | | | | | | | | | conditions Add support of uge and sge latch condition to Loop Prediction for reverse loops. Reviewers: apilipenko, mkazantsev, sanjoy, anna Reviewed By: anna Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42837 llvm-svn: 324589
* [LoopPrediction] Introduce utility function getLatchPredicateForGuard. NFC.Serguei Katkov2018-02-071-17/+30
| | | | | | | Factor out getting the predicate for latch condition in a guard to utility function getLatchPredicateForGuard. llvm-svn: 324450
* [NFC] fix trivial typos in comments and documentsHiroshi Inoue2018-01-261-1/+1
| | | | | | "in in" -> "in", "on on" -> "on" etc. llvm-svn: 323508
* [Loop Predication] Teach LP about reverse loopsAnna Thomas2017-12-041-58/+135
| | | | | | | | | | | | | | | | | | | | | | | Summary: Currently, we only support predication for forward loops with step of 1. This patch enables loop predication for reverse or countdownLoops, which satisfy the following conditions: 1. The step of the IV is -1. 2. The loop has a singe latch as B(X) = X <pred> latchLimit with pred as s> or u> 3. The IV of the guard is the decrement IV of the latch condition (Guard is: G(X) = X-1 u< guardLimit). This patch was downstream for a while and is the last series of patches that's from our LP implementation downstream. Reviewers: apilipenko, mkazantsev, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40353 llvm-svn: 319659
* [LoopPredication] NFC: Refactored code to separate out functions being reusedAnna Thomas2017-11-031-62/+92
| | | | | | | | | | | | Summary: Refactored the code to separate out common functions that are being reused. This is to reduce the changes for changes coming up wrt loop predication with reverse loops. This refactoring is what we have in our downstream code. llvm-svn: 317324
* [LoopPredication] Enable predication when latchCheckIV is wider than rangeCheckAnna Thomas2017-11-021-10/+96
| | | | | | | | | | | | | | | | | | | | | | Summary: This patch allows us to predicate range checks that have a type narrower than the latch check type. We leverage SCEV analysis to identify a truncate for the latchLimit and latchStart. There is also safety checks in place which requires the start and limit to be known at compile time. We require this to make sure that the SCEV truncate expr for the IV corresponding to the latch does not cause us to lose information about the IV range. Added tests show the loop predication over range checks that are of various types and are narrower than the latch type. This enhancement has been in our downstream tree for a while. Reviewers: apilipenko, sanjoy, mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D39500 llvm-svn: 317269
* [LoopPredication] Handle the case when the guard and the latch IV have ↵Artur Pilipenko2017-10-271-61/+87
| | | | | | | | | | | | | | | | | | | | | | | | | | different offsets This is a follow up change for D37569. Currently the transformation is limited to the case when: * The loop has a single latch with the condition of the form: ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=. * The step of the IV used in the latch condition is 1. * The IV of the latch condition is the same as the post increment IV of the guard condition. * The guard condition is of the form i u< guardLimit. This patch enables the transform in the case when the latch is latchStart + i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=. And the guard is guardStart + i u< guardLimit Reviewed By: anna Differential Revision: https://reviews.llvm.org/D39097 llvm-svn: 316768
* [LoopPredication] Check whether the loop is already guarded by the first ↵Artur Pilipenko2017-10-121-2/+6
| | | | | | iteration check condition llvm-svn: 315623
* [LoopPredication] Support ule, sle latch predicatesArtur Pilipenko2017-10-121-20/+35
| | | | | | | | | | This is a follow up for the loop predication change 313981 to support ule, sle latch predicates. Reviewed By: mkazantsev Differential Revision: https://reviews.llvm.org/D38177 llvm-svn: 315616
* Rework loop predication passArtur Pilipenko2017-09-221-38/+220
| | | | | | | | | | | | | | | | | | | | | | | We've found a serious issue with the current implementation of loop predication. The current implementation relies on SCEV and this turned out to be problematic. To fix the problem we had to rework the pass substantially. We have had the reworked implementation in our downstream tree for a while. This is the initial patch of the series of changes to upstream the new implementation. For now the transformation is limited to the following case: * The loop has a single latch with either ult or slt icmp condition. * The step of the IV used in the latch condition is 1. * The IV of the latch condition is the same as the post increment IV of the guard condition. * The guard condition is ult. See the review or the LoopPredication.cpp header for the details about the problem and the new implementation. Reviewed By: sanjoy, mkazantsev Differential Revision: https://reviews.llvm.org/D37569 llvm-svn: 313981
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
OpenPOWER on IntegriCloud