summaryrefslogtreecommitdiffstats
path: root/llvm/test/Analysis/ScalarEvolution
Commit message (Collapse)AuthorAgeFilesLines
* [SCEV] accurate range for addrecexpr with nuw flagZheng Chen2020-01-121-2/+2
| | | | | | | | | If addrecexpr has nuw flag, the value should never be less than its start value and start value does not required to be SCEVConstant. Reviewed By: nikic, sanjoy Differential Revision: https://reviews.llvm.org/D71690
* [SCEV] more accurate range for addrecexpr with nsw flag.Zheng Chen2020-01-111-4/+4
| | | | | | Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D72436
* [SCEV] [NFC] add more test cases for range of addrecexpr with nsw flagZheng Chen2020-01-101-4/+65
|
* [SCEV] [NFC] add testcase for constant range for addrecexpr with nsw flagZheng Chen2020-01-091-0/+19
|
* Migrate function attribute "no-frame-pointer-elim"="false" to ↵Fangrui Song2019-12-242-2/+2
| | | | "frame-pointer"="none" as cleanups after D56351
* [SCEV] add testcase for get accurate range for addrecexpr with nuw flagczhengsz2019-12-221-0/+20
|
* [SCEV] NFC - add testcase for get accurate range for AddExprczhengsz2019-12-191-0/+21
|
* [Tests] Autogenerate a bunch of SCEV trip count tests for readability. Will ↵Philip Reames2019-11-219-260/+443
| | | | likely merge some of these files soon.
* [SCEV] Add a mode to skip classification when printing analysisPhilip Reames2019-11-211-113/+1
| | | | For the various trip-count tests, the classification isn't useful and makes the auto-generated tests super verbose. By skipping it, we make the auto-gen tests closer to the manually written ones. Up next: auto-genning a bunch of the existings tests.
* [SCEV] Be robust against IR generated by simple-loop-unswitchPhilip Reames2019-11-211-48/+64
| | | | | | Simple loop unswitch likes to leave around unsimplified and/or/xors. SCEV today bails out on these idioms which is unfortunate in general, and specifically for the unswitch interaction. Differential Revision: https://reviews.llvm.org/D70459
* Precommit test showing oppurtunity when computing exit tests of unsimplified IRPhilip Reames2019-11-191-0/+461
| | | | If we partially unswitch a loop, we leave around the (and i1 X, true) or (or i1 X, false) forms. At the moment, this inhibits SCEVs ability to compute trip counts, patch forthcoming.
* [SCEV] Simplify umin/max of zext and sext of the same valuePhilip Reames2019-10-194-48/+48
| | | | | | | | This is a common idiom which arises after induction variables are widened, and we have two or more exit conditions. Interestingly, we don't have instcombine or instsimplify support for this either. Differential Revision: https://reviews.llvm.org/D69006 llvm-svn: 375349
* [Test] Precommit test for D69006Philip Reames2019-10-171-0/+317
| | | | llvm-svn: 375190
* [Tests] Add a SCEV analysis test for llvm.widenable.conditionPhilip Reames2019-10-141-0/+45
| | | | | | Mostly because we don't appear to have one and a prototype patch I just saw would have broken the example committed. llvm-svn: 374835
* Revert "[SCEV] add no wrap flag for SCEVAddExpr."Tim Northover2019-09-304-7/+7
| | | | | | | | This reverts r366419 because the analysis performed is within the context of the loop and it's only valid to add wrapping flags to "global" expressions if they're always correct. llvm-svn: 373184
* [Analysis] Allow -scalar-evolution-max-iterations more than onceShoaib Meenai2019-09-191-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | At present, `-scalar-evolution-max-iterations` is a `cl::Optional` option, which means it demands to be passed exactly zero or one times. Our build system makes it pretty tricky to guarantee this. We often accidentally pass the flag more than once (but always with the same value) which results in an error, after which compilation fails: ``` clang (LLVM option parsing): for the -scalar-evolution-max-iterations option: may only occur zero or one times! ``` It seems reasonable to allow -scalar-evolution-max-iterations to be passed more than once. Quoting the [[ http://llvm.org/docs/CommandLine.html#controlling-the-number-of-occurrences-required-and-allowed | documentation ]]: > The cl::ZeroOrMore modifier ... indicates that your program will allow the option to be specified zero or more times. > ... > If an option is specified multiple times for an option of the cl::opt class, only the last value will be retained. Original patch by: Enrico Bern Hardy Tanuwidjaja <etanuwid@fb.com> Differential Revision: https://reviews.llvm.org/D67512 llvm-svn: 372346
* [SCEV] Add smin support to getRangeRefPhilip Reames2019-09-122-9/+15
| | | | | | | | We were failing to compute trip counts (both exact and maximum) for any loop which involved a comparison against either an umin or smin. It looks like this simply got missed when we added smin/umin to SCEV. (Note: umin was submitted separately earlier today. Turned out two folks hit this at the same time.) Differential Revision: https://reviews.llvm.org/D67514 llvm-svn: 371776
* [SCEV] Support SCEVUMinExpr in getRangeRef.Florian Hahn2019-09-122-13/+13
| | | | | | | | | | | | | This patch adds support for SCEVUMinExpr to getRangeRef, similar to the support for SCEVUMaxExpr. Reviewers: sanjoy.google, efriedma, reames, nikic Reviewed By: sanjoy.google Differential Revision: https://reviews.llvm.org/D67177 llvm-svn: 371768
* Precommit tests for D67514Philip Reames2019-09-121-0/+115
| | | | llvm-svn: 371762
* [SCEV] add no wrap flag for SCEVAddExpr.Chen Zheng2019-07-184-7/+7
| | | | | | Differential Revision: https://reviews.llvm.org/D64868 llvm-svn: 366419
* [SCEV] teach SCEV symbolical execution about overflow intrinsics folding.Chen Zheng2019-07-111-0/+128
| | | | | | Differential Revision: https://reviews.llvm.org/D64422 llvm-svn: 365726
* Update -analyze -scalar-evolution output for multiple exit loops ↵Philip Reames2019-06-271-0/+4
| | | | | | | | w/computable exit values The previous output was next to useless if *any* exit was not computable. If we have more than one exit, show the exit count for each so that it's easier to see what's going from with SCEV analysis when debugging. llvm-svn: 364579
* [LoopUnroll] Add support for loops with exiting headers and uncond latches.Florian Hahn2019-06-261-1/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch generalizes the UnrollLoop utility to support loops that exit from the header instead of the latch. Usually, LoopRotate would take care of must of those cases, but in some cases (e.g. -Oz), LoopRotate does not kick in. Codesize impact looks relatively neutral on ARM64 with -Oz + LTO. Program master patch diff External/S.../CFP2006/447.dealII/447.dealII 629060.00 627676.00 -0.2% External/SPEC/CINT2000/176.gcc/176.gcc 1245916.00 1244932.00 -0.1% MultiSourc...Prolangs-C/simulator/simulator 86100.00 86156.00 0.1% MultiSourc...arks/Rodinia/backprop/backprop 66212.00 66252.00 0.1% MultiSourc...chmarks/Prolangs-C++/life/life 67276.00 67312.00 0.1% MultiSourc...s/Prolangs-C/compiler/compiler 69824.00 69788.00 -0.1% MultiSourc...Prolangs-C/assembler/assembler 86672.00 86696.00 0.0% Reviewers: efriedma, vsk, paquette Reviewed By: paquette Differential Revision: https://reviews.llvm.org/D61962 llvm-svn: 364398
* [SCEV] Use unsigned/signed intersection type in SCEVNikita Popov2019-06-155-11/+11
| | | | | | | | | | | | Based on D59959, this switches SCEV to use unsigned/signed range intersection based on the sign hint. This will prefer non-wrapping ranges in the relevant domain. I've left the one intersection in getRangeForAffineAR() to use the smallest intersection heuristic, as there doesn't seem to be any obvious preference there. Differential Revision: https://reviews.llvm.org/D60035 llvm-svn: 363490
* [SCEV] Add explicit representations of umin/sminKeno Fischer2019-05-076-8/+8
| | | | | | | | | | | | | | | | | | Summary: Currently we express umin as `~umax(~x, ~y)`. However, this becomes a problem for operands in non-integral pointer spaces, because `~x` is not something we can compute for `x` non-integral. However, since comparisons are generally still allowed, we are actually able to express `umin(x, y)` directly as long as we don't try to express is as a umax. Support this by adding an explicit umin/smin representation to SCEV. We do this by factoring the existing getUMax/getSMax functions into a new function that does all four. The previous two functions were largely identical. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D50167 llvm-svn: 360159
* [SCEV] Check the cache in get{S|U}MaxExpr before doing any workSanjoy Das2019-03-291-0/+156
| | | | | | | | | | | | | | | | | | Summary: This lets us avoid e.g. checking if A >=s B in getSMaxExpr(A, B) if we've already established that (A smax B) is the best we can do. Fixes PR41225. Reviewers: asbirlea Subscribers: mcrosier, jlebar, bixia, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60010 llvm-svn: 357320
* [SCEV] Use depth limit for trunc analysisTeresa Johnson2019-03-121-1/+29
| | | | | | | | | | | | | | | | | | | Summary: This fixes an extremely long compile time caused by recursive analysis of truncs, which were not previously subject to any depth limits unlike some of the other ops. I decided to use the same control used for sext/zext, since the routines analyzing these are sometimes mutually recursive with the trunc analysis. Reviewers: mkazantsev, sanjoy Subscribers: sanjoy, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58994 llvm-svn: 355949
* [SCEV] Handle case where MaxBECount is less precise than ExactBECount for OR.Florian Hahn2019-03-021-0/+49
| | | | | | | | | | | | | | | | | | | | | | | | In some cases, MaxBECount can be less precise than ExactBECount for AND and OR (the AND case was PR26207). In the OR test case, both ExactBECounts are undef, but MaxBECount are different, so we hit the assertion below. This patch uses the same solution the AND case already uses. Assertion failed: ((isa<SCEVCouldNotCompute>(ExactNotTaken) || !isa<SCEVCouldNotCompute>(MaxNotTaken)) && "Exact is not allowed to be less precise than Max"), function ExitLimit This patch also consolidates test cases for both AND and OR in a single test case. Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=13245 Reviewers: sanjoy, efriedma, mkazantsev Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D58853 llvm-svn: 355259
* Fixed typos in tests: s/CEHCK/CHECK/Dmitri Gribenko2019-02-252-2/+2
| | | | | | | | | | | | Reviewers: ilya-biryukov Subscribers: sanjoy, sdardis, javed.absar, jrtc27, atanasyan, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58608 llvm-svn: 354781
* [SCEV] Do not bother creating separate SCEVUnknown for unreachable nodesMax Kazantsev2019-02-041-1/+1
| | | | | | | | | | | Currently, SCEV creates SCEVUnknown for every node of unreachable code. If we have a huge amounts of such code, we will be littering SE with these nodes. We could just state that they all are undef and save some memory. Differential Revision: https://reviews.llvm.org/D57567 Reviewed By: sanjoy llvm-svn: 353017
* [SCEV] Prohibit SCEV transformations for huge SCEVsMax Kazantsev2019-01-311-0/+41
| | | | | | | | | | | | | | | | | | | | | | Currently SCEV attempts to limit transformations so that they do not work with big SCEVs (that may take almost infinite compile time). But for this, it uses heuristics such as recursion depth and number of operands, which do not give us a guarantee that we don't actually have big SCEVs. This situation is still possible, though it is not likely to happen. However, the bug PR33494 showed a bunch of simple corner case tests where we still produce huge SCEVs, even not reaching big recursion depth etc. This patch introduces a concept of 'huge' SCEVs. A SCEV is huge if its expression size (intoduced in D35989) exceeds some threshold value. We prohibit optimizing transformations if any of SCEVs we are dealing with is huge. This gives us a reliable check that we don't spend too much time working with them. As the next step, we can possibly get rid of old limiting mechanisms, such as recursion depth thresholds. Differential Revision: https://reviews.llvm.org/D35990 Reviewed By: reames llvm-svn: 352728
* [SCEV] Take correct loop in AddRec simplification. PR40420Max Kazantsev2019-01-291-1/+0
| | | | | | | | | | | | The code of AddRec simplification is using wrong loop when it creates a new AddRecExpr. It should be using AddRecLoop which we have saved and against which all gate checks are made, and not calling AddRec->getLoop() over and over again because AddRec may change and become an AddRecurrency from outer loop during the transform iterations. Considering this change trivial, commiting for postcommit review. llvm-svn: 352451
* [NFC] Merge failing test from PR40420Max Kazantsev2019-01-291-0/+51
| | | | llvm-svn: 352450
* [test] Fix ScalarEvolution test to allow __func__ with prototypeMichal Gorny2018-12-021-123/+123
| | | | | | | | | | | | | | | | | | | | Fix ScalarEvolution/solve-quadratic.ll test to account for __func__ output listing the complete function prototype rather than just its name, as it does on NetBSD. Example Linux output: GetQuadraticEquation: addrec coeff bw: 4 GetQuadraticEquation: equation -2x^2 + -2x + -4, coeff bw: 5, multiplied by 2 Example NetBSD output: llvm::Optional<std::tuple<llvm::APInt, llvm::APInt, llvm::APInt, llvm::APInt, unsigned int> > GetQuadraticEquation(const llvm::SCEVAddRecExpr*): addrec coeff bw: 4 llvm::Optional<std::tuple<llvm::APInt, llvm::APInt, llvm::APInt, llvm::APInt, unsigned int> > GetQuadraticEquation(const llvm::SCEVAddRecExpr*): equation -2x^2 + -2x + -4, coeff bw: 5, multiplied by 2 Differential Revision: https://reviews.llvm.org/D55162 llvm-svn: 348096
* Return "[IndVars] Smart hard uses detection"Max Kazantsev2018-11-081-3/+3
| | | | | | | | | | The patch has been reverted because it ended up prohibiting propagation of a constant to exit value. For such values, we should skip all checks related to hard uses because propagating a constant is always profitable. Differential Revision: https://reviews.llvm.org/D53691 llvm-svn: 346397
* Revert "[IndVars] Smart hard uses detection"Max Kazantsev2018-11-061-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts commit 2f425e9c7946b9d74e64ebbfa33c1caa36914402. It seems that the check that we still should do the transform if we know the result is constant is missing in this code. So the logic that has been deleted by this change is still sometimes accidentally useful. I revert the change to see what can be done about it. The motivating case is the following: @Y = global [400 x i16] zeroinitializer, align 1 define i16 @foo() { entry: br label %for.body for.body: ; preds = %entry, %for.body %i = phi i16 [ 0, %entry ], [ %inc, %for.body ] %arrayidx = getelementptr inbounds [400 x i16], [400 x i16]* @Y, i16 0, i16 %i store i16 0, i16* %arrayidx, align 1 %inc = add nuw nsw i16 %i, 1 %cmp = icmp ult i16 %inc, 400 br i1 %cmp, label %for.body, label %for.end for.end: ; preds = %for.body %inc.lcssa = phi i16 [ %inc, %for.body ] ret i16 %inc.lcssa } We should be able to figure out that the result is constant, but the patch breaks it. Differential Revision: https://reviews.llvm.org/D51584 llvm-svn: 346198
* [IndVars] Smart hard uses detectionMax Kazantsev2018-11-011-3/+3
| | | | | | | | | | | | | | | | When rewriting loop exit values, IndVars considers this transform not profitable if the loop instruction has a loop user which it believes cannot be optimized away. In current implementation only calls that immediately use the instruction are considered as such. This patch extends the definition of "hard" users to any side-effecting instructions (which usually cannot be optimized away from the loop) and also allows handling of not just immediate users, but use chains. Differentlai Revision: https://reviews.llvm.org/D51584 Reviewed By: etherzhhb llvm-svn: 345814
* [SCEV] Avoid redundant computations when doing AddRec mergeMax Kazantsev2018-11-011-1/+1
| | | | | | | | | | | | | When we calculate a product of 2 AddRecs, we end up making quite massive computations to deduce the operands of resulting AddRec. This process can be optimized by computing all args of intermediate sum and then calling `getAddExpr` once rather than calling `getAddExpr` with intermediate result every time a new argument is computed. Differential Revision: https://reviews.llvm.org/D53189 Reviewed By: rtereshin llvm-svn: 345813
* [SCEV] Limit AddRec "simplifications" to avoid combinatorial explosionsMax Kazantsev2018-10-161-0/+47
| | | | | | | | | | | | | | | | | | SCEV's transform that turns `{A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L>` into a single AddRec of size `2n+1` with complex combinatorial coefficients can easily trigger exponential growth of the SCEV (in case if nothing gets folded and simplified). We tried to restrain this transform using the option `scalar-evolution-max-add-rec-size`, but its default value seems to be insufficiently small: the test attached to this patch with default value of this option `16` has a SCEV of >3M symbols (when printed out). This patch reduces the simplification limit. It is not a cure to combinatorial explosions, but at least it reduces this corner case to something more or less reasonable. Differential Revision: https://reviews.llvm.org/D53282 Reviewed By: sanjoy llvm-svn: 344584
* [SCEV] Properly solve quadratic equationsKrzysztof Parzyszek2018-08-023-0/+515
| | | | | | Differential Revision: https://reviews.llvm.org/D48283 llvm-svn: 338758
* [SCEV] Add zext(C + x + ...) -> D + zext(C-D + x + ...)<nuw><nsw> transformRoman Tereshin2018-07-241-0/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | if the top level addition in (D + (C-D + x + ...)) could be proven to not wrap, where the choice of D also maximizes the number of trailing zeroes of (C-D + x + ...), ensuring homogeneous behaviour of the transformation and better canonicalization of such expressions. This enables better canonicalization of expressions like 1 + zext(5 + 20 * %x + 24 * %y) and zext(6 + 20 * %x + 24 * %y) which get both transformed to 2 + zext(4 + 20 * %x + 24 * %y) This pattern is common in address arithmetics and the transformation makes it easier for passes like LoadStoreVectorizer to prove that 2 or more memory accesses are consecutive and optimize (vectorize) them. Reviewed By: mzolotukhin Differential Revision: https://reviews.llvm.org/D48853 llvm-svn: 337859
* [SCEV] Fix buggy behavior in getAddExpr with truncsMax Kazantsev2018-07-191-0/+34
| | | | | | | | | | | | | | | | | SCEV tries to constant-fold arguments of trunc operands in SCEVAddExpr, and when it does that, it passes wrong flags into the recursion. It is only valid to pass flags that are proved for narrow type into a computation in wider type if we can prove that trunc instruction doesn't actually change the value. If it did lose some meaningful bits, we may end up proving wrong no-wrap flags for sum of arguments of trunc. In the provided test we end up with `nuw` where it shouldn't be because of this bug. The solution is to conservatively pass `SCEV::FlagAnyWrap` which is always a valid thing to do. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D49471 llvm-svn: 337435
* [NFC] Make a test more neatMax Kazantsev2018-07-181-2/+5
| | | | llvm-svn: 337379
* Re-apply "[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428)."Tim Shen2018-07-1311-25/+29
| | | | llvm-svn: 337075
* Revert "[SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428)."Tim Shen2018-07-0611-29/+25
| | | | | | This reverts commit r336140. Our tests shows that LSR assert fails with it. llvm-svn: 336473
* [SCEV] Strengthen StrengthenNoWrapFlags (reapply r334428).Tim Shen2018-07-0211-25/+29
| | | | | | | | | | | | | | | | Summary: Comment on Transforms/LoopVersioning/incorrect-phi.ll: With the change SCEV is able to prove that the loop doesn't wrap-self (due to zext i16 to i64), disabling the entire loop versioning pass. Removed the zext and just use i64. Reviewers: sanjoy Subscribers: jlebar, hiraditya, javed.absar, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48409 llvm-svn: 336140
* Fix overconfident assert in ScalarEvolution::isImpliedViaMergeRoman Shirokiy2018-06-291-0/+127
| | | | | | | | | We can have AddRec with loops having many predecessors. This changes an assert to an early return. Differential Revision: https://reviews.llvm.org/D48766 llvm-svn: 335965
* [SCEV] Re-apply r335197 (with Polly fixes).Tim Shen2018-06-211-0/+42
| | | | | | | | | | | | | | | | | Summary: This initiates a discussion on changing Polly accordingly while re-applying r335197 (D48338). I have never worked on Polly. The proposed change to param_div_div_div_2.ll is not educated, but just patterns that match the output. All LLVM files are already reviewed in D48338. Reviewers: jdoerfert, bollu, efriedma Subscribers: jlebar, sanjoy, hiraditya, llvm-commits, bixia Differential Revision: https://reviews.llvm.org/D48453 llvm-svn: 335292
* Revert "[SCEV] Improve zext(A /u B) and zext(A % B)"Tim Shen2018-06-211-42/+0
| | | | | | This reverts commit r335197, as some bots are not happy. llvm-svn: 335198
* [SCEV] Improve zext(A /u B) and zext(A % B)Tim Shen2018-06-211-0/+42
| | | | | | | | | | | | | | | Summary: Try to match udiv and urem patterns, and sink zext down to the leaves. I'm not entirely sure why some unrelated tests change, but the added <nsw>s seem right. Reviewers: sanjoy Subscribers: jlebar, hiraditya, bixia, llvm-commits Differential Revision: https://reviews.llvm.org/D48338 llvm-svn: 335197
OpenPOWER on IntegriCloud