summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert "[SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV." -- breaks MSVC builds.Justin Lebar2018-06-161-34/+38
| | | | | | This reverts D48237. llvm-svn: 334878
* Revert "[SCEV] Simplify some flags expressions." -- dependent revision ↵Justin Lebar2018-06-161-4/+4
| | | | | | | | breaks MSVC builds. This reverts D48238. llvm-svn: 334877
* [SCEV] Simplify some flags expressions.Justin Lebar2018-06-151-4/+4
| | | | | | | | | | | | | | Summary: Sending for presubmit review out of an abundance of caution; it would be bad to mess this up. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48238 llvm-svn: 334875
* [SCEV] Use LLVM_MARK_AS_BITMASK_ENUM in SCEV.Justin Lebar2018-06-151-38/+34
| | | | | | | | | | | | | | | | | | Summary: Obviates the need for mask/clear/setFlags helpers. There are some expressions here which can be simplified, but to keep this easy to review, I have not simplified them in this patch. No functional change. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48237 llvm-svn: 334874
* [SCEV] Fix a variable name, NFC.Justin Lebar2018-06-141-6/+6
| | | | llvm-svn: 334738
* [SCEV] Simplify zext/trunc idiom that appears when handling bitmasks.Justin Lebar2018-06-141-0/+26
| | | | | | | | | | | | | | | | | | | Summary: Specifically, we transform zext(2^K * (trunc X to iN)) to iM -> 2^K * (zext(trunc X to i{N-K}) to iM)<nuw> This is helpful because pulling the 2^K out of the zext allows further optimizations. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits, timshen Differential Revision: https://reviews.llvm.org/D48158 llvm-svn: 334737
* [SCEV] Simplify trunc-of-add/mul to add/mul-of-trunc under more circumstances.Justin Lebar2018-06-141-32/+22
| | | | | | | | | | | | | | | | | | | | Summary: Previously we would do this simplification only if it did not introduce any new truncs (excepting new truncs which replace other cast ops). This change weakens this condition: If the number of truncs stays the same, but we're able to transform trunc(X + Y) to X + trunc(Y), that's still simpler, and it may open up additional transformations. While we're here, also clean up some duplicated code. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48160 llvm-svn: 334736
* [SCEV] Fix indentation and combine two if statements in getMulExpr, NFC.Justin Lebar2018-06-141-15/+14
| | | | llvm-svn: 334735
* [SCEV] Add transform zext((A * B * ...)<nuw>) --> (zext(A) * zext(B) * ↵Justin Lebar2018-06-111-0/+12
| | | | | | | | | | | | ...)<nuw>. Reviewers: sanjoy Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D48041 llvm-svn: 334429
* [SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe.Justin Lebar2018-06-111-6/+19
| | | | | | | | | | | | | Summary: Previously we would add them for adds, but not multiplies. Reviewers: sanjoy Subscribers: llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D48038 llvm-svn: 334428
* Fix indentation in ScalarEvolution.cpp.Justin Lebar2018-06-111-26/+26
| | | | | | Whitespace-only change. (clang-formatted the whole block.) llvm-svn: 334427
* [SCEV] Canonicalize "A /u C1 /u C2" to "A /u (C1*C2)".Tim Shen2018-06-111-0/+15
| | | | | | | | | | | | Summary: FWIW InstCombine already folds this. Also avoid the case where C1*C2 overflows. Reviewers: sunfish, sanjoy Subscribers: hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D47965 llvm-svn: 334425
* [SCEV] Look through zero-extends in howFarToZeroKrzysztof Parzyszek2018-06-081-1/+11
| | | | | | | | | | | | An expression like (zext i2 {(trunc i32 (1 + %B) to i2),+,1}<%while.body> to i32) will become zero exactly when the nested value becomes zero in its type. Strip injective operations from the input value in howFarToZero to make the value simpler. Differential Revision: https://reviews.llvm.org/D47951 llvm-svn: 334318
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-50/+50
| | | | | | | | | | | | | | | | 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
* SCEV] Do not use induction in isKnownPredicate for simplification umax.Serguei Katkov2018-05-101-5/+6
| | | | | | | | | | | | | | | | | | During simplification umax we trigger isKnownPredicate twice. As a first attempt it tries the induction. To do that it tries to get post increment of SCEV. Re-writing the SCEV may result in simplification of umax. If the SCEV contains a lot of umax operations this recursion becomes very slow. The added test demonstrates the slow behavior. To resolve this we use only simple ways to check whether the predicate is known. Reviewers: sanjoy, mkazantsev Reviewed By: sanjoy Subscribers: lebedev.ri, javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D46046 llvm-svn: 331949
* Re-enable "[SCEV] Make computeExitLimit more simple and more powerful"Max Kazantsev2018-05-031-58/+17
| | | | | | | | | | | This patch was temporarily reverted because it has exposed bug 37229 on PowerPC platform. The bug is unrelated to the patch and was just a general bug in the optimization done for PowerPC platform only. The bug was fixed by the patch rL331410. This patch returns the disabled commit since the bug was fixed. llvm-svn: 331427
* IWYU for llvm-config.h in llvm, additions.Nico Weber2018-04-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See r331124 for how I made a list of files missing the include. I then ran this Python script: for f in open('filelist.txt'): f = f.strip() fl = open(f).readlines() found = False for i in xrange(len(fl)): p = '#include "llvm/' if not fl[i].startswith(p): continue if fl[i][len(p):] > 'Config': fl.insert(i, '#include "llvm/Config/llvm-config.h"\n') found = True break if not found: print 'not found', f else: open(f, 'w').write(''.join(fl)) and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p` and tried to fix include ordering and whatnot. No intended behavior change. llvm-svn: 331184
* [SCEV] Touch the unsused stats variables for product build.Serguei Katkov2018-04-281-0/+3
| | | | | | This is a fix by elimination compiler warnings considered as errors. llvm-svn: 331103
* [SCEV] Reduce the number of invocation to non trivial getExact functionSerguei Katkov2018-04-281-2/+5
| | | | | | | | | | | | | | | | | The invocation of getExact in ScalarEvolution::getBackedgeTakenInfo is used only for getting statistic and for assert. Even if statistics is disabled, the code related to it will be eliminated the invocation to getExact itself will not be eliminated because it may have side-effects like creation of new SCEVs. So do invocation only when we collect statistics or executes asserts. Reviewers: mkazantsev, sanjoy, javed.absar Reviewed By: javed.absar Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D46178 llvm-svn: 331099
* [SCEV] Add trivial case handling for umin utilities. NFC.Serguei Katkov2018-04-271-2/+11
| | | | | | | | | Reviewers: sanjoy, mkazantsev Reviewed By: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D46175 llvm-svn: 331022
* [SCEV] Introduce bulk umin creation utilitiesSerguei Katkov2018-04-271-19/+45
| | | | | | | | | | | | | | | | Add new umin creation method which accepts a list of operands. SCEV does not represents umin which is required in getExact, so it transforms umin to umax with not. As a result the transformation of tree of max to max with several operands does not work. We just use the new introduced method for creation umin from several operands. Reviewers: sanjoy, mkazantsev Reviewed By: sanjoy Subscribers: javed.absar, llvm-commits Differential Revision: https://reviews.llvm.org/D46047 llvm-svn: 331015
* Revert "[SCEV] Make computeExitLimit more simple and more powerful"Max Kazantsev2018-04-261-17/+58
| | | | | | | | | | | This reverts commit 023c8be90980e0180766196cba86f81608b35d38. This patch triggers miscompile of zlib on PowerPC platform. Most likely it is caused by some pre-backend PPC-specific pass, but we don't clearly know the reason yet. So we temporally revert this patch with intention to return it once the problem is resolved. See bug 37229 for details. llvm-svn: 330893
* [LoopSimplify] Fix incorrect SCEV invalidationMax Kazantsev2018-04-231-0/+6
| | | | | | | | | | | | | | | | | | | | | | | | | In the function `simplifyOneLoop` we optimistically assume that changes in the inner loop only affect this very loop and have no impact on its parents. In fact, after rL329047 has been merged, we can now calculate exit counts for outer loops which may depend on inner loops. Thus, we need to invalidate all parents when we do something to a loop. There is an evidence of incorrect behavior of `simplifyOneLoop`: when we insert `SE->verify()` check in the end of this funciton, it fails on a bunch of existing test, in particular: LLVM :: Transforms/LoopUnroll/peel-loop-not-forced.ll LLVM :: Transforms/LoopUnroll/peel-loop-pgo.ll LLVM :: Transforms/LoopUnroll/peel-loop.ll LLVM :: Transforms/LoopUnroll/peel-loop2.ll Note that previously we have fixed issues of this variety, see rL328483. This patch makes this function invalidate the outermost loop properly. Differential Revision: https://reviews.llvm.org/D45937 Reviewed By: chandlerc llvm-svn: 330576
* [NFC] Loosen restriction on preheader to fix buildbotMax Kazantsev2018-04-061-5/+5
| | | | llvm-svn: 329379
* [SCEV] Prove implications for SCEVUnknown PhisMax Kazantsev2018-04-041-0/+118
| | | | | | | | | | | | | | | | | This patch teaches SCEV how to prove implications for SCEVUnknown nodes that are Phis. If we need to prove `Pred` for `LHS, RHS`, and `LHS` is a Phi with possible incoming values `L1, L2, ..., LN`, then if we prove `Pred` for `(L1, RHS), (L2, RHS), ..., (LN, RHS)` then we can also prove it for `(LHS, RHS)`. If both `LHS` and `RHS` are Phis from the same block, it is sufficient to prove the predicate for values that come from the same predecessor block. The typical case that it handles is that we sometimes need to prove that `Phi(Len, Len - 1) >= 0` given that `Len > 0`. The new logic was added to `isImpliedViaOperations` and only uses it and non-recursive reasoning to prove the facts we need, so it should not hurt compile time a lot. Differential Revision: https://reviews.llvm.org/D44001 Reviewed By: anna llvm-svn: 329150
* [SCEV] Fix PR36974.Serguei Katkov2018-04-031-5/+6
| | | | | | | | | | | | | The patch changes the usage of dominate to properlyDominate to satisfy the condition !(a < a) while using std::max. It is actually NFC due to set data structure is used to keep the Loops and no two identical loops can be in collection. So in reality there is no difference between usage of dominate and properlyDominate in this particular case. However it might be changed so it is better to fix it. llvm-svn: 329051
* [SCEV] Make computeExitLimit more simple and more powerfulMax Kazantsev2018-04-031-58/+17
| | | | | | | | | | | | | | | | | | | | | | | Current implementation of `computeExitLimit` has a big piece of code the only purpose of which is to prove that after the execution of this block the latch will be executed. What it currently checks is actually a subset of situations where the exiting block dominates latch. This patch replaces all these checks for simple particular cases with domination check over loop's latch which is the only necessary condition of taking the exiting block into consideration. This change allows to calculate exact loop taken count for simple loops like for (int i = 0; i < 100; i++) { if (cond) {...} else {...} if (i > 50) break; . . . } Differential Revision: https://reviews.llvm.org/D44677 Reviewed By: efriedma llvm-svn: 329047
* [Analysis] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-011-1/+1
| | | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer D44363 for a list of all the required patches. Reviewers: sanjoy, dexonsmith, hfinkel, RKSimon Reviewed By: dexonsmith Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D44944 llvm-svn: 328925
* [NFC] Fix meaningless assert in SCEVMax Kazantsev2018-03-291-2/+2
| | | | llvm-svn: 328764
* [NFC] Fix comments in getExact()Max Kazantsev2018-03-271-12/+11
| | | | llvm-svn: 328612
* [SCEV] Make exact taken count calculation more optimisticMax Kazantsev2018-03-271-6/+16
| | | | | | | | | | | | | | | | | | | | | Currently, `getExact` fails if it sees two exit counts in different blocks. There is no solid reason to do so, given that we only calculate exact non-taken count for exiting blocks that dominate latch. Using this fact, we can simply take min out of all exits of all blocks to get the exact taken count. This patch makes the calculation more optimistic with enforcing our assumption with asserts. It allows us to calculate exact backedge taken count in trivial loops like for (int i = 0; i < 100; i++) { if (i > 50) break; . . . } Differential Revision: https://reviews.llvm.org/D44676 Reviewed By: fhahn llvm-svn: 328611
* [SCEV] Add one more case in computeConstantDifferenceMax Kazantsev2018-03-271-10/+18
| | | | | | | | | | This patch teaches `computeConstantDifference` handle calculation of constant difference between `(X + C1)` and `(X + C2)` which is `(C2 - C1)`. Differential Revision: https://reviews.llvm.org/D43759 Reviewed By: anna llvm-svn: 328609
* Revert r325687 (workaround for PR36032).Evgeny Stupachenko2018-03-221-7/+0
| | | | | | | | | | | | | | Summary: Revert r325687 workaround for PR36032 since a fix was committed in r326154. Reviewers: sbaranga Differential Revision: http://reviews.llvm.org/D44768 From: Evgeny Stupachenko <evstupac@gmail.com> <evgeny.v.stupachenko@intel.com> llvm-svn: 328257
* [SCEV] Factor out isKnownViaInduction. NFC.Serguei Katkov2018-03-191-49/+38
| | | | | | | | | | | This just extracts the isKnownViaInduction from isKnownPredicate. Reviewers: sanjoy, mkazantsev, reames Reviewed By: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D44554 llvm-svn: 327824
* [SCEV] Re-land: Fix isKnownPredicateSerguei Katkov2018-03-191-27/+73
| | | | | | | | | | | | | | | | | This is re-land of https://reviews.llvm.org/rL327362 with a fix and regression test. The crash was due to it is possible that for found MDL loop, LHS or RHS may contain an invariant unknown SCEV which does not dominate the MDL. Please see regression test for an example. Reviewers: sanjoy, mkazantsev, reames Reviewed By: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D44553 llvm-svn: 327822
* [NFC] Void variables used for asserts onlyMax Kazantsev2018-03-161-0/+2
| | | | llvm-svn: 327693
* [SCEV][NFC] Remove TBB, FBB parameters from exit limit computationsMax Kazantsev2018-03-151-38/+36
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Methods `computeExitLimitFromCondCached` and `computeExitLimitFromCondImpl` take true and false branches as parameters and only use them for asserts and for identifying whether true/false branch belongs to the loop (which can be done once earlier). This fact complicates generalization of exit limit computation logic on guards because the guards don't have blocks to which they go in case of failure explicitly. The motivation of this patch is that currently this part of SCEV knows nothing about guards and only works with explicit branches. As result, it fails to prove that a loop for (i = 0; i < 100; i++) guard(i < 10); exits after 10th iteration, while in the equivalent example for (i = 0; i < 100; i++) if (i >= 10) break; SCEV easily proves this fact. We are going to change it in near future, and this is why we need to make these methods operate on more abstract level. This patch refactors this code to get rid of these parameters as meaningless and prepare ground for teaching these methods to work with guards as well as they work with explicit branching instructions. Differential Revision: https://reviews.llvm.org/D44419 llvm-svn: 327615
* [SCEV][NFC] Smarter implementation of isAvailableAtLoopEntryMax Kazantsev2018-03-131-53/+1
| | | | | | | | | | isAvailableAtLoopEntry duplicates logic of `properlyDominates` after checking invariance. This patch replaces this logic with invocation of this method which is more profitable because it supports caching. Differential Revision: https://reviews.llvm.org/D43997 llvm-svn: 327373
* Revert [SCEV] Fix isKnownPredicateSerguei Katkov2018-03-131-67/+27
| | | | | | | | It is a revert of rL327362 which causes build bot failures with assert like Assertion `isAvailableAtLoopEntry(RHS, L) && "RHS is not available at Loop Entry"' failed. llvm-svn: 327363
* [SCEV] Fix isKnownPredicateSerguei Katkov2018-03-131-27/+67
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | IsKnownPredicate is updated to implement the following algorithm proposed by @sanjoy and @mkazantsev : isKnownPredicate(Pred, LHS, RHS) { Collect set S all loops on which either LHS or RHS depend. If S is non-empty a. Let PD be the element of S which is dominated by all other elements of S b. Let E(LHS) be value of LHS on entry of PD. To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values. Define E(RHS) in the same way. c. Let B(LHS) be value of L on backedge of PD. To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values. Define B(RHS) in the same way. d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that. e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS)) Return true if Pred, L, R is known from ranges, splitting etc. } This is follow-up for https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy, mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43507 llvm-svn: 327362
* [SCEV] Smart range calculation for SCEVUnknown PhisMax Kazantsev2018-03-011-0/+21
| | | | | | | | | | The range of SCEVUnknown Phi which merges values `X1, X2, ..., XN` can be evaluated as `U(Range(X1), Range(X2), ..., Range(XN))`. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D43810 llvm-svn: 326418
* [SCEV] Cleanup SCEVInitRewriter. NFC.Serguei Katkov2018-02-271-2/+2
| | | | | | | | | | Set default value for IgnoreOtherLoops of SCEVInitRewriter::rewrite to true to be consistent with SCEVPostIncRewriter which does not have this parameter but behaves as it would be true. This is follow up for rL326067. llvm-svn: 326174
* Fix PR36032, PR35432Evgeny Stupachenko2018-02-271-0/+6
| | | | | | | | | | | | | | | Summary: The change fix an assert fail at ScalarEvolutionExpander.cpp: assert(ExitCount != SE.getCouldNotCompute() && "Invalid loop count"); Reviewers: sbaranga Differential Revision: http://reviews.llvm.org/D42604 From: Evgeny Stupachenko <evstupac@gmail.com> <evgeny.v.stupachenko@intel.com> llvm-svn: 326154
* [SCEV] Factor out getUsedLoopsSerguei Katkov2018-02-261-4/+12
| | | | | | | | | | | | | | | The patch introduces the new function in ScalarEvolution to get all loops used in specified SCEV. This is a preparation for re-writing isKnownPredicate utility as described in https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43504 llvm-svn: 326072
* [SCEV] Introduce SCEVPostIncRewriterSerguei Katkov2018-02-261-0/+41
| | | | | | | | | | | | | | | | The patch introduces the SCEVPostIncRewriter rewriter which is similar to SCEVInitRewriter but rewrites AddRec with post increment value of this AddRec. This is a preparation for re-writing isKnownPredicate utility as described in https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43499 llvm-svn: 326071
* [SCEV] Extends the SCEVInitRewriterSerguei Katkov2018-02-261-8/+20
| | | | | | | | | | | | | | | | | The patch introduces an additional parameter IgnoreOtherLoops to SCEVInitRewriter. if it is equal to true then rewriter will not invalidate result in case SCEV depends on other loops then specified during creation. The patch does not change the default behavior. This is a preparation for re-writing isKnownPredicate utility as described in https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43498 llvm-svn: 326067
* [SCEV][NFC] Factor out common logic into a separate methodMax Kazantsev2018-02-221-13/+14
| | | | | | | | | | | | SCEV has multiple occurences of code when we need to prove some predicate on every iteration of a loop and do it with invocations of couple `isLoopEntryGuardedByCond`, `isLoopBackedgeGuardedByCond`. This patch factors out these two calls into a separate method. It is a preparation step to extend this logic: it is not the only way how we can prove such conditions. Differential Revision: https://reviews.llvm.org/D43373 llvm-svn: 325745
* [SCEV] Temporarily disable loop versioning for the purposeSilviu Baranga2018-02-211-0/+7
| | | | | | | | | | of turning SCEVUnknowns of PHIs into AddRecExprs. This feature is now hidden behind the -scev-version-unknown flag. Fixes PR36032 and PR35432. llvm-svn: 325687
* [NFC] Rename isKnownViaSimpleReasoning to isKnownViaNonRecursiveReasoningMax Kazantsev2018-02-151-15/+15
| | | | llvm-svn: 325216
* [SCEV] Favor isKnownViaSimpleReasoning over constant ranges checkMax Kazantsev2018-02-151-6/+6
| | | | | | | | | | | | | | | | | | | | | There is a more powerful but still simple function `isKnownViaSimpleReasoning ` that does constant range check and few more additional checks. We use it some places (e.g. when proving implications) and in some other places we only check constant ranges. Currently, indvar simplifier fails to remove the check in following loop: int inc = ...; for (int i = inc, j = inc - 1; i < 200; ++i, ++j) if (i > j) { ... } This patch replaces all usages of `isKnownPredicateViaConstantRanges` with `isKnownViaSimpleReasoning` to have smarter proofs. In particular, it fixes the case above. Reviewed-By: sanjoy Differential Revision: https://reviews.llvm.org/D43175 llvm-svn: 325214
OpenPOWER on IntegriCloud