summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [InstSimplify] Don't constant fold or DCE calls that are marked nobuiltinAndrew Kaylor2017-06-091-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D33737 llvm-svn: 305132
* 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
* Added LLVM_FALLTHROUGH to address warning: this statement may fall through. NFC.Galina Kistanova2017-05-311-0/+4
| | | | llvm-svn: 304358
* [SCEV][NFC] Remove redundant params from isAvailableAtLoopEntryMax Kazantsev2017-05-301-4/+3
| | | | | | | | Params DT and LI are redundant, because these values are contained in fields anyways. Differential Revision: https://reviews.llvm.org/D33668 llvm-svn: 304204
* [SCEV] Assume parameters coming from function calls contain IVsTobias Grosser2017-05-271-1/+4
| | | | | | | | | | | | | | | | | | | | The optimistic delinearization implemented in LLVM detects array sizes by looking for non-linear products between parameters and induction variables. In OpenCL code, such products often look like: A[get_global_id(0) * N + get_global_id(1)] Hence, the IV is hidden in the get_global_id() call and consequently delinearization would fail as no induction variable is available that helps us to identify N as array size parameter. We now use a very simple heuristic to change this. We assume that each parameter that comes directly from a function call is a hidden induction variable. As a result, we can delinearize the access above to: A[get_global_id(0)][get_global_id(1] llvm-svn: 304073
* Re-enable "[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start"Max Kazantsev2017-05-261-2/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The patch rL303730 was reverted because test lsr-expand-quadratic.ll failed on many non-X86 configs with this patch. The reason of this is that the patch makes a correctless fix that changes optimizer's behavior for this test. Without the change, LSR was making an overconfident simplification basing on a wrong SCEV. Apparently it did not need the IV analysis to do this. With the change, it chose a different way to simplify (that wasn't so confident), and this way required the IV analysis. Now, following the right execution path, LSR tries to make a transformation relying on IV Users analysis. This analysis is target-dependent due to this code: // LSR is not APInt clean, do not touch integers bigger than 64-bits. // Also avoid creating IVs of non-native types. For example, we don't want a // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. uint64_t Width = SE->getTypeSizeInBits(I->getType()); if (Width > 64 || !DL.isLegalInteger(Width)) return false; To make a proper transformation in this test case, the type i32 needs to be legal for the specified data layout. When the test runs on some non-X86 configuration (e.g. pure ARM 64), opt gets confused by the specified target and does not use it, rejecting the specified data layout as well. Instead, it uses some default layout that does not treat i32 as a legal type (currently the layout that is used when it is not specified does not have legal types at all). As result, the transformation we expect to happen does not happen for this test. This re-enabling patch does not have any source code changes compared to the original patch rL303730. The only difference is that the failing test is moved to X86 directory and now has requirement of running on x86 only to comply with the specified target triple and data layout. Differential Revision: https://reviews.llvm.org/D33543 llvm-svn: 303971
* [ValueTracking] Convert most of the calls to computeKnownBits to use the ↵Craig Topper2017-05-241-6/+2
| | | | | | | | | | version that returns the KnownBits object. This continues the changes started when computeSignBit was replaced with this new version of computeKnowBits. Differential Revision: https://reviews.llvm.org/D33431 llvm-svn: 303773
* Revert "[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start"Diana Picus2017-05-241-59/+2
| | | | | | This reverts commit r303730 because it broke all the buildbots. llvm-svn: 303747
* [SCEV] Do not fold dominated SCEVUnknown into AddRecExpr startMax Kazantsev2017-05-241-2/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | When folding arguments of AddExpr or MulExpr with recurrences, we rely on the fact that the loop of our base recurrency is the bottom-lost in terms of domination. This assumption may be broken by an expression which is treated as invariant, and which depends on a complex Phi for which SCEVUnknown was created. If such Phi is a loop Phi, and this loop is lower than the chosen AddRecExpr's loop, it is invalid to fold our expression with the recurrence. Another reason why it might be invalid to fold SCEVUnknown into Phi start value is that unlike other SCEVs, SCEVUnknown are sometimes position-bound. For example, here: for (...) { // loop phi = {A,+,B} } X = load ... Folding phi + X into {A+X,+,B}<loop> actually makes no sense, because X does not exist and cannot exist while we are iterating in loop (this memory can be even not allocated and not filled by this moment). It is only valid to make such folding if X is defined before the loop. In this case the recurrence {A+X,+,B}<loop> may be existant. This patch prohibits folding of SCEVUnknown (and those who use them) into the start value of an AddRecExpr, if this instruction is dominated by the loop. Merging the dominating unknown values is still valid. Some tests that relied on the fact that some SCEVUnknown should be folded into AddRec's are changed so that they no longer expect such behavior. llvm-svn: 303730
* [SCEV] Clarify behavior around max backedge taken countSanjoy Das2017-05-221-10/+37
| | | | | | | | | | | | | | | | | | | | | | | This is a re-application of a r303497 that was reverted in r303498. I thought it had broken a bot when it had not (the breakage did not go away with the revert). This change makes the split between the "exact" backedge taken count and the "maximum" backedge taken count a bit more obvious. Both of these are upper bounds on the number of times the loop header executes (since SCEV does not account for most kinds of abnormal control flow), but the latter is guaranteed to be a constant. There were a few places where the max backedge taken count *was* a non-constant; I've changed those to compute constants instead. At this point, I'm not sure if the constant max backedge count can be computed by calling `getUnsignedRange(Exact).getUnsignedMax()` without losing precision. If it can, we can simplify even further by making `getMaxBackedgeTakenCount` a thin wrapper around `getBackedgeTakenCount` and `getUnsignedRange`. llvm-svn: 303531
* Revert "[SCEV] Clarify behavior around max backedge taken count"Sanjoy Das2017-05-211-37/+10
| | | | | | | This reverts commit r303497 since it breaks the msan bootstrap bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/1379/ llvm-svn: 303498
* [SCEV] Clarify behavior around max backedge taken countSanjoy Das2017-05-211-10/+37
| | | | | | | | | | | | | | | | | | | This change makes the split between the "exact" backedge taken count and the "maximum" backedge taken count a bit more obvious. Both of these are upper bounds on the number of times the loop header executes (since SCEV does not account for most kinds of abnormal control flow), but the latter is guaranteed to be a constant. There were a few places where the max backedge taken count *was* a non-constant; I've changed those to compute constants instead. At this point, I'm not sure if the constant max backedge count can be computed by calling `getUnsignedRange(Exact).getUnsignedMax()` without losing precision. If it can, we can simplify even further by making `getMaxBackedgeTakenCount` a thin wrapper around `getBackedgeTakenCount` and `getUnsignedRange`. llvm-svn: 303497
* [SCEV][NFC] Remove duplication of isLoopInvariant codeMax Kazantsev2017-05-181-2/+2
| | | | | | | | | Replace two places that duplicate the code of isLoopInvariant method with the invocation of this method. Differential Revision: https://reviews.llvm.org/D33313 llvm-svn: 303336
* [SCEV] Always sort AddRecExprs from different loops by dominanceMax Kazantsev2017-05-171-7/+7
| | | | | | | | | | | | | | Sorting of AddRecExprs by loop nesting does not make sense since we only invoke the CompareSCEVComplexity for AddRecExprs that are used by one SCEV. This guarantees that there is always a dominance relationship between them. This patch removes the sorting by nesting which is a dead code in current usage of this function. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D33228 llvm-svn: 303235
* [SCEV][NFC] Replace redundant dyn_cast with cast in getAddExprMax Kazantsev2017-05-171-14/+15
| | | | | | | | Replace dyn_cast which is ensured by isa just one line above with cast. Differential Revision: https://reviews.llvm.org/D33231 llvm-svn: 303234
* [SCEV] Fix sorting order for AddRecExprsMax Kazantsev2017-05-161-16/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The existing sorting order in defined CompareSCEVComplexity sorts AddRecExprs by loop depth, but does not pay attention to dominance of loops. This can lead us to the following buggy situation: for (...) { // loop1 op1 = {A,+,B} } for (...) { // loop2 op2 = {A,+,B} S = add op1, op2 } In this case there is no guarantee that in operand list of S the op2 comes before op1 (loop depth is the same, so they will be sorted just lexicographically), so we can incorrectly treat S as a recurrence of loop1, which is wrong. This patch changes the sorting logic so that it places the dominated recs before the dominating recs. This ensures that when we pick the first recurrency in the operands order, it will be the bottom-most in terms of domination tree. The attached test set includes some tests that produce incorrect SCEV estimations and crashes with oldlogic. Reviewers: sanjoy, reames, apilipenko, anna Reviewed By: sanjoy Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D33121 llvm-svn: 303148
* [SCEV] Use copy initialization of APInts instead of direct initialization.Craig Topper2017-05-151-6/+6
| | | | | | This is based on post commit feed back from r302769. llvm-svn: 303092
* [ValueTracking] Replace all uses of ComputeSignBit with computeKnownBits.Craig Topper2017-05-151-5/+4
| | | | | | | | This patch finishes off the conversion of ComputeSignBit to computeKnownBits. Differential Revision: https://reviews.llvm.org/D33166 llvm-svn: 303035
* Move some code into ScalarEvolution.cpp; NFCSanjoy Das2017-05-151-0/+24
| | | | | | | I need to add some asserts to these constructors that are easier to add once they're in the .cpp file. llvm-svn: 303032
* [KnownBits] Add bit counting methods to KnownBits struct and use them where ↵Craig Topper2017-05-121-1/+1
| | | | | | | | | | | | possible This patch adds min/max population count, leading/trailing zero/one bit counting methods. The min methods return answers based on bits that are known without considering unknown bits. The max methods give answers taking into account the largest count that unknown bits could give. Differential Revision: https://reviews.llvm.org/D32931 llvm-svn: 302925
* [SCEV] Reduce possible APInt allocations a bit.Craig Topper2017-05-111-7/+11
| | | | llvm-svn: 302769
* [SCEV] Remove unneeded 'using namespace APIntOps'.Craig Topper2017-05-111-37/+34
| | | | llvm-svn: 302768
* [SCEV] Don't use std::move on both inputs to APInt::operator+ or operator-. ↵Craig Topper2017-05-081-4/+4
| | | | | | It might be confusing to the reader. NFC llvm-svn: 302448
* [SCEV] Use APInt::operator*=(uint64_t) to avoid a temporary APInt for a ↵Craig Topper2017-05-081-2/+1
| | | | | | constant. llvm-svn: 302404
* [SCEV] Have getRangeForAffineARHelper take StartRange by const reference to ↵Craig Topper2017-05-081-1/+1
| | | | | | avoid a copy in many of the cases. llvm-svn: 302398
* [SCEV] Use move semantics in ScalarEvolution::setRangeCraig Topper2017-05-071-3/+3
| | | | | | | | | | | | | | Summary: This makes setRange take ConstantRange by rvalue reference since most callers were passing an unnamed temporary ConstantRange. We can then move that ConstantRange into the DenseMap caches. For the callers that weren't passing a temporary, I've added std::move to to the local variable being passed. Reviewers: sanjoy, mzolotukhin, efriedma Reviewed By: sanjoy Subscribers: takuto.ikuta, llvm-commits Differential Revision: https://reviews.llvm.org/D32943 llvm-svn: 302371
* Remove unnecessary const_castSanjoy Das2017-05-071-7/+4
| | | | llvm-svn: 302368
* Use array_pod_sort instead of std::sortSanjoy Das2017-05-071-1/+1
| | | | llvm-svn: 302367
* [SCEV] Remove extra APInt copies from getRangeForAffineARHelper.Craig Topper2017-05-061-13/+10
| | | | | | This changes one parameter to be a const APInt& since we only read from it. Use std::move on local APInts once they are no longer needed so we can reuse their allocations. Lastly, use operator+=(uint64_t) instead of adding 1 to an APInt twice creating a new APInt each time. llvm-svn: 302335
* [SCEV] Use std::move to avoid some APInt copies.Craig Topper2017-05-061-5/+5
| | | | llvm-svn: 302334
* [SCEV] Use APInt's uint64_t operations instead of creating a temporary APInt ↵Craig Topper2017-05-061-3/+2
| | | | | | to hold 1. llvm-svn: 302333
* [SCEV] Avoid a couple APInt copies by capturing by reference since the ↵Craig Topper2017-05-061-2/+2
| | | | | | method returns a reference. llvm-svn: 302332
* Fix a typo.Michael Zolotukhin2017-05-041-2/+2
| | | | llvm-svn: 302175
* [SCEV] createAddRecFromPHI: Optimize for the most common case.Michael Zolotukhin2017-05-031-2/+58
| | | | | | | | | | | | | | | | | | | Summary: The existing implementation creates a symbolic SCEV expression every time we analyze a phi node and then has to remove it, when the analysis is finished. This is very expensive, and in most of the cases it's also unnecessary. According to the data I collected, ~60-70% of analyzed phi nodes (measured on SPEC) have the following form: PN = phi(Start, OP(Self, Constant)) Handling such cases separately significantly speeds this up. Reviewers: sanjoy, pete Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32663 llvm-svn: 302096
* Rename isKnownNotFullPoison to programUndefinedIfPoison; NFCSanjoy Das2017-04-301-1/+2
| | | | | | | | | | | | | | | | | Summary: programUndefinedIfPoison makes more sense, given what the function does; and I'm about to add a function with a name similar to isKnownNotFullPoison (so do the rename to avoid confusion). Reviewers: broune, majnemer, bjarke.roune Reviewed By: broune Subscribers: mcrosier, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D30444 llvm-svn: 301776
* [SCEV] Use early exit in createAddRecFromPHI. NFC.Michael Zolotukhin2017-04-281-109/+110
| | | | llvm-svn: 301703
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-1/+1
| | | | llvm-svn: 301673
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-261-10/+12
| | | | | | | | | | | | | | | | computeKnownBits This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit. Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch. I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases. Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with. Differential Revision: https://reviews.llvm.org/D32376 llvm-svn: 301432
* Revert "[SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS builds"Sanjoy Das2017-04-241-10/+3
| | | | | | | This reverts commit r301150. It breaks CodeGen/Hexagon/hwloop-wrap2.ll, reverting while I investigate. llvm-svn: 301154
* Fix unused variables / fields warnings in release buildsSanjoy Das2017-04-241-0/+6
| | | | llvm-svn: 301151
* [SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS buildsSanjoy Das2017-04-241-3/+10
| | | | llvm-svn: 301150
* [SCEV] Fix exponential time complexity by cachingSanjoy Das2017-04-241-19/+63
| | | | llvm-svn: 301149
* [SCEV] Move towards a verifier without false positivesSanjoy Das2017-04-231-68/+59
| | | | | | | | | | | | | | | This change reboots SCEV's current (off by default) verification logic to avoid false failures. Instead of stringifying trip counts, it maps old and new trip counts to the same ScalarEvolution "universe" and asks ScalarEvolution to compute the difference between them. If the difference comes out to be a non-zero constant, then (barring some corner cases) we *know* we messed up. I've not yet enabled this by default since it hits an exponential time issue in SCEV, but once I fix that, I'll flip it on by default in EXPENSIVE_CHECKS builds. llvm-svn: 301146
* Revert r300746 (SCEV analysis for or instructions).Eli Friedman2017-04-201-6/+22
| | | | | | | | There have been multiple reports of this causing problems: a compile-time explosion on the LLVM testsuite, and a stack overflow for an opencl kernel. llvm-svn: 300928
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-201-4/+4
| | | | | | | | getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask. Differential Revision: https://reviews.llvm.org/D32108 llvm-svn: 300856
* [SCEV] Make SCEV or modeling more aggressive.Eli Friedman2017-04-191-22/+6
| | | | | | | | | | Use haveNoCommonBitsSet to figure out whether an "or" instruction is equivalent to addition. This handles more cases than just checking for a constant on the RHS. Differential Revision: https://reviews.llvm.org/D32239 llvm-svn: 300746
* [APInt] Use lshrInPlace to replace lshr where possibleCraig Topper2017-04-181-1/+1
| | | | | | | | | | This patch uses lshrInPlace to replace code where the object that lshr is called on is being overwritten with the result. This adds an lshrInPlace(const APInt &) version as well. Differential Revision: https://reviews.llvm.org/D32155 llvm-svn: 300566
* [SCEV] Fix another unused variable warning in release builds.Benjamin Kramer2017-04-171-0/+1
| | | | llvm-svn: 300500
* Fix an unused variable error in rL300494.Wei Mi2017-04-171-0/+1
| | | | llvm-svn: 300499
* [SCEV] Add a local cache for getZeroExtendExpr and getSignExtendExpr to preventWei Mi2017-04-171-61/+115
| | | | | | | | | | | | | | | | | | the exponential behavior. The patch is to fix PR32043. Functions getZeroExtendExpr and getSignExtendExpr may call themselves recursively more than once. This is potentially a 2^N complexity behavior. The exponential behavior was not commonly exposed before because of existing global cache mechnism like UniqueSCEVs or some early return mechanism when flags FlagNSW or FlagNUW are seen. However, we still have case which can expose the exponential behavior, like the case in PR32043, so we add a local cache in getZeroExtendExpr and getSignExtendExpr. If the input of the functions -- SCEV and type pair have been seen before, we can find the extended expression directly in the local cache. Differential Revision: https://reviews.llvm.org/D30350 llvm-svn: 300494
OpenPOWER on IntegriCloud