summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [ScalarEvolution] Fix base condition in isNormalAddRecPHI.Bjorn Pettersson2017-12-141-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The function is meant to recurse until it comes upon the phi it's looking for. However, with the current condition, it will recurse until it finds anything _but_ the phi. The function will even fail for simple cases like: %i = phi i32 [ %inc, %loop ], ... ... %inc = add i32 %i, 1 because the base condition will not happen when the phi is recursed to, and the recursion will end with a 'false' result since the previous instruction is a phi. Reviewers: sanjoy, atrick Reviewed By: sanjoy Subscribers: Ka-Ka, bjope, llvm-commits Committing on behalf of: Bevin Hansson (bevinh) Differential Revision: https://reviews.llvm.org/D40946 llvm-svn: 320700
* [InlineCost] Tracking Values through PHI NodesHaicheng Wu2017-12-141-6/+138
| | | | | | | | | | | | This patch fix this FIXME in visitPHI() FIXME: We should potentially be tracking values through phi nodes, especially when they collapse to a single value due to deleted CFG edges during inlining. Differential Revision: https://reviews.llvm.org/D38594 llvm-svn: 320699
* [LV] Support efficient vectorization of an induction with redundant castsDorit Nuzman2017-12-141-6/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | D30041 extended SCEVPredicateRewriter to improve handling of Phi nodes whose update chain involves casts; PSCEV can now build an AddRecurrence for some forms of such phi nodes, under the proper runtime overflow test. This means that we can identify such phi nodes as an induction, and the loop-vectorizer can now vectorize such inductions, however inefficiently. The vectorizer doesn't know that it can ignore the casts, and so it vectorizes them. This patch records the casts in the InductionDescriptor, so that they could be marked to be ignored for cost calculation (we use VecValuesToIgnore for that) and ignored for vectorization/widening/scalarization (i.e. treated as TriviallyDead). In addition to marking all these casts to be ignored, we also need to make sure that each cast is mapped to the right vector value in the vector loop body (be it a widened, vectorized, or scalarized induction). So whenever an induction phi is mapped to a vector value (during vectorization/widening/ scalarization), we also map the respective cast instruction (if exists) to that vector value. (If the phi-update sequence of an induction involves more than one cast, then the above mapping to vector value is relevant only for the last cast of the sequence as we allow only the "last cast" to be used outside the induction update chain itself). This is the last step in addressing PR30654. llvm-svn: 320672
* Remove redundant includes from lib/Analysis.Michael Zolotukhin2017-12-1312-14/+0
| | | | llvm-svn: 320617
* Reintroduce r320049, r320014 and r319894.Igor Laevsky2017-12-131-0/+28
| | | | | | OpenGL issues should be fixed by now. llvm-svn: 320568
* [SLP] Vectorize jumbled memory loads.Mohammad Shahid2017-12-131-0/+71
| | | | | | | | | | | | | | | | | | | | | | Summary: This patch tries to vectorize loads of consecutive memory accesses, accessed in non-consecutive or jumbled way. An earlier attempt was made with patch D26905 which was reverted back due to some basic issue with representing the 'use mask' of jumbled accesses. This patch fixes the mask representation by recording the 'use mask' in the usertree entry. Change-Id: I9fe7f5045f065d84c126fa307ef6ebe0787296df Reviewers: mkuper, loladiro, Ayal, zvi, danielcdh Reviewed By: Ayal Subscribers: mgrang, dcaballe, hans, mzolotukhin Differential Revision: https://reviews.llvm.org/D36130 llvm-svn: 320548
* Revert r320049, r320014 and r319894Igor Laevsky2017-12-121-28/+0
| | | | | | | They were causing failures of the piglit OpenGL tests with AMD GPUs using the Mesa radeonsi driver. llvm-svn: 320466
* [SCEV] Fix wrong Equal predicate created in getAddRecForPhiWithCastsDorit Nuzman2017-12-101-6/+9
| | | | | | | | | | | | | | | | | | | CreateAddRecFromPHIWithCastsImpl() adds an IncrementNUSW overflow predicate which allows the PSCEV rewriter to rewrite this scev expression: (zext i8 {0, + , (trunc i32 step to i8)} to i32) into {0, +, (sext i8 (trunc i32 step to i8) to i32)} But then it adds the wrong Equal predicate: %step == (zext i8 (trunc i32 %step to i8) to i32). instead of: %step == (sext i8 (trunc i32 %step to i8) to i32) This is fixed here. Differential Revision: https://reviews.llvm.org/D40641 llvm-svn: 320298
* Infer lowest bits of an integer Multiply when the low bits of the operands ↵Simon Dardis2017-12-091-9/+66
| | | | | | | | | | | | | | | are known When the lowest bits of the operands to an integer multiply are known, the low bits of the result are deducible. Code to deduce known-zero bottom bits already existed, but this change improves on that by deducing known-ones. Patch by: Pedro Ferreira Reviewers: craig.topper, sanjoy, efriedma Differential Revision: https://reviews.llvm.org/D34029 llvm-svn: 320269
* Hardware-assisted AddressSanitizer (llvm part).Evgeniy Stepanov2017-12-092-3/+6
| | | | | | | | | | | | | | | | | | | | | Summary: This is LLVM instrumentation for the new HWASan tool. It is basically a stripped down copy of ASan at this point, w/o stack or global support. Instrumenation adds a global constructor + runtime callbacks for every load and store. HWASan comes with its own IR attribute. A brief design document can be found in clang/docs/HardwareAssistedAddressSanitizerDesign.rst (submitted earlier). Reviewers: kcc, pcc, alekseyshl Subscribers: srhines, mehdi_amini, mgorny, javed.absar, eraman, llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D40932 llvm-svn: 320217
* Revert r320104: infinite loop profiling bug fixXinliang David Li2017-12-081-4/+0
| | | | | | | | | | | Causes unexpected memory issue with New PM this time. The new PM invalidates BPI but not BFI, leaving the reference to BPI from BFI invalid. Abandon this patch. There is a more general solution which also handles runtime infinite loop (but not statically). llvm-svn: 320180
* [NFC] Rename variable from Cond to Pred to make it more soundMax Kazantsev2017-12-081-12/+12
| | | | llvm-svn: 320144
* [SCEV] Fix predicate usage in computeExitLimitFromICmpMax Kazantsev2017-12-081-1/+2
| | | | | | | | | | | | | | | | | | | In this method, we invoke `SimplifyICmpOperands` which takes the `Cond` predicate by reference and may change it along with `LHS` and `RHS` SCEVs. But then we invoke `computeShiftCompareExitLimit` with Values from which the SCEVs have been derived, these Values have not been modified while `Cond` could be. One of possible outcomes of this is that we may falsely prove that an infinite loop ends within some finite number of iterations. In this patch, we save the original `Cond` and pass it along with original operands. This logic may be removed in future once `computeShiftCompareExitLimit` works with SCEVs instead of value operands. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D40953 llvm-svn: 320142
* [ModRefInfo] Make enum ModRefInfo an enum class [NFC].Alina Sbirlea2017-12-078-115/+119
| | | | | | | | | | | | | | | Summary: Make enum ModRefInfo an enum class. Changes to ModRefInfo values should be done using inline wrappers. This should prevent future bit-wise opearations from being added, which can be more error-prone. Reviewers: sanjoy, dberlin, hfinkel, george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40933 llvm-svn: 320107
* [PGO] detect infinite loop and form MST properlyXinliang David Li2017-12-071-0/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D40873 llvm-svn: 320104
* [ModRefInfo] Replace remaining bit-wise operations with wrappers.Alina Sbirlea2017-12-073-5/+5
| | | | llvm-svn: 319993
* [ModRefInfo] Do not use ModRefInfo result in if conditions as this makesAlina Sbirlea2017-12-061-1/+1
| | | | | | | assumptions about the values in the enum. Replace with wrapper returning bool [NFC]. llvm-svn: 319949
* [ModRefInfo] Use createModRefInfo wrapper to create a ModRefInfo from ↵Alina Sbirlea2017-12-061-4/+4
| | | | | | FunctionModRefBehavior. llvm-svn: 319941
* InstructionSimplify: 'extractelement' with an undef index is undefZvi Rackover2017-12-061-0/+5
| | | | | | | | | | | | | | | | | | | Summary: An undef extract index can be arbitrarily chosen to be an out-of-range index value, which would result in the instruction being undef. This change closes a gap identified while working on lowering vector permute intrinsics with variable index vectors to pure LLVM IR. Reviewers: arsenm, spatel, majnemer Reviewed By: arsenm, spatel Subscribers: fhahn, nhaehnle, wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D40231 llvm-svn: 319910
* [InstSimplify] Fold insertelement into undef if index is out of boundsIgor Laevsky2017-12-061-0/+28
| | | | | | Differential Revision: https://reviews.llvm.org/D40650 llvm-svn: 319894
* [SCEV][NFC] Check NoWrap flags before lexicographical comparison of SCEVsMax Kazantsev2017-12-061-0/+8
| | | | | | | | | | | | | | | | Lexicographical comparison of SCEV trees is potentially expensive for big expression trees. We can define ordering between them for AddRecs and N-ary operations by SCEV NoWrap flags to make non-equality check cheaper. This change does not prevent grouping eqivalent SCEVs together and is not supposed to have any meaningful impact on behavior of any transforms. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D40645 llvm-svn: 319889
* [SCEV][NFC] Share value cache between SCEVs in GroupByComplexityMax Kazantsev2017-12-061-22/+26
| | | | | | | | | | | | | Current implementation of `compareSCEVComplexity` is being unreasonable with `SCEVUnknown`s: every time it sees one, it creates a new value cache and tries to prove equality of two values using it. This cache reallocates and gets lost from SCEV to SCEV. This patch changes this behavior: now we create one cache for all values and share it between SCEVs. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D40597 llvm-svn: 319880
* Revert r319482 and r319483 "[memcpyopt] Teach memcpyopt to optimize across ↵Hans Wennborg2017-12-061-8/+0
| | | | | | | | | | | | | | | | | | | | | | | | basic blocks" This caused PR35519. > [memcpyopt] Teach memcpyopt to optimize across basic blocks > > This teaches memcpyopt to make a non-local memdep query when a local query > indicates that the dependency is non-local. This notably allows it to > eliminate many more llvm.memcpy calls in common Rust code, often by 20-30%. > > Fixes PR28958. > > Differential Revision: https://reviews.llvm.org/D38374 > > [memcpyopt] Commit file missed in r319482. > > This change was meant to be included with r319482 but was accidentally > omitted. llvm-svn: 319873
* [ModRefInfo] Initialize ArgMask to MRI_NoModRef.Alina Sbirlea2017-12-051-1/+1
| | | | llvm-svn: 319831
* Modify ModRefInfo values using static inline method abstractions [NFC].Alina Sbirlea2017-12-057-80/+85
| | | | | | | | | | | | | | | | | Summary: The aim is to make ModRefInfo checks and changes more intuitive and less error prone using inline methods that abstract the bit operations. Ideally ModRefInfo would become an enum class, but that change will require a wider set of changes into FunctionModRefBehavior. Reviewers: sanjoy, george.burgess.iv, dberlin, hfinkel Subscribers: nlopes, llvm-commits Differential Revision: https://reviews.llvm.org/D40749 llvm-svn: 319821
* [InstCombine] Don't crash on out of bounds shiftsIgor Laevsky2017-12-051-13/+17
| | | | | | Differential Revision: https://reviews.llvm.org/D40649 llvm-svn: 319761
* [SCEV] Use a "Discovered" set instead of a "Visited" set; NFCSanjoy Das2017-12-041-4/+3
| | | | | | Suggested by Max Kazantsev in https://reviews.llvm.org/D39361 llvm-svn: 319679
* [SCEV] A different fix for PR33494Sanjoy Das2017-12-041-29/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: I don't think rL309080 is the right fix for PR33494 -- caching ExitLimit only hides the problem[0]. The real issue is that because of how we forget SCEV expressions ScalarEvolution::getBackedgeTakenInfo, in the test case for PR33494 computing the backedge for any loop invalidates the trip count for every other loop. This effectively makes the SCEV cache useless. I've instead made the SCEV expression invalidation in ScalarEvolution::getBackedgeTakenInfo less aggressive to fix this issue. [0]: One way to think about this is that rL309080 essentially augmented the backedge-taken-count cache with another equivalent exit-limit cache. The bug went away because we were explicitly not clearing the exit-limit cache in getBackedgeTakenInfo. But instead of doing all of that, we can just avoid clearing the backedge-taken-count cache. Reviewers: mkazantsev, mzolotukhin Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D39361 llvm-svn: 319678
* Revert "[ValueTracking] Pass only a single lambda to ↵Sam McCall2017-12-041-29/+37
| | | | | | | | | computeKnownBitsFromShiftOperator by using KnownBits struct instead of separate APInts. NFCI" This reverts commit r319624, which seems to cause a miscompile (breaks the multistage PPC buildbots) llvm-svn: 319652
* [ValueTracking] Pass only a single lambda to ↵Craig Topper2017-12-021-37/+29
| | | | | | computeKnownBitsFromShiftOperator by using KnownBits struct instead of separate APInts. NFCI llvm-svn: 319624
* [opt-remarks] If hotness threshold is set, ignore remarks without hotnessAdam Nemet2017-12-011-5/+4
| | | | | | | | | | | | | | These are blocks that haven't not been executed during training. For large projects this could make a significant difference. For the project, I was looking at, I got an order of magnitude decrease in the size of the total YAML files with this and r319235. Differential Revision: https://reviews.llvm.org/D40678 Re-commit after fixing the failing testcase in rL319576, rL319577 and rL319578. llvm-svn: 319581
* IR printing improvement for loop passes - handle -print-module-scopeFedor Sergeev2017-12-011-0/+12
| | | | | | | | | | | | | | | | | Summary: Adding support for -print-module-scope similar to how it is being done for function passes. This option causes loop-pass printer to emit a whole-module IR instead of just a loop itself. Reviewers: sanjoy, silvas, weimingz Reviewed By: sanjoy Subscribers: apilipenko, skatkov, llvm-commits Differential Revision: https://reviews.llvm.org/D40247 llvm-svn: 319566
* Revert "[opt-remarks] If hotness threshold is set, ignore remarks without ↵Adam Nemet2017-12-011-4/+5
| | | | | | | | | | | hotness" This reverts commit r319556. Something is not working with this when used with sample-based profiling. Investigating... llvm-svn: 319562
* [opt-remarks] If hotness threshold is set, ignore remarks without hotnessAdam Nemet2017-12-011-5/+4
| | | | | | | | | | | These are blocks that haven't not been executed during training. For large projects this could make a significant difference. For the project, I was looking at, I got an order of magnitude decrease in the size of the total YAML files with this and r319235. Differential Revision: https://reviews.llvm.org/D40678 llvm-svn: 319556
* [InstSimplify] More fcmp cases when comparing against negative constants.Florian Hahn2017-12-011-0/+22
| | | | | | | | | | | | | | | | | | | | | | | | Summary: For known positive non-zero value X: fcmp uge X, -C => true fcmp ugt X, -C => true fcmp une X, -C => true fcmp oeq X, -C => false fcmp ole X, -C => false fcmp olt X, -C => false Patch by Paul Walker. Reviewers: majnemer, t.p.northover, spatel, RKSimon Reviewed By: spatel Subscribers: fhahn, llvm-commits Differential Revision: https://reviews.llvm.org/D40012 llvm-svn: 319538
* Mark all library options as hidden.Zachary Turner2017-12-015-12/+10
| | | | | | | | | | | | | | | | | These command line options are not intended for public use, and often don't even make sense in the context of a particular tool anyway. About 90% of them are already hidden, but when people add new options they forget to hide them, so if you were to make a brand new tool today, link against one of LLVM's libraries, and run tool -help you would get a bunch of junk that doesn't make sense for the tool you're writing. This patch hides these options. The real solution is to not have libraries defining command line options, but that's a much larger effort and not something I'm prepared to take on. Differential Revision: https://reviews.llvm.org/D40674 llvm-svn: 319505
* [memcpyopt] Teach memcpyopt to optimize across basic blocksDan Gohman2017-11-301-0/+8
| | | | | | | | | | | | This teaches memcpyopt to make a non-local memdep query when a local query indicates that the dependency is non-local. This notably allows it to eliminate many more llvm.memcpy calls in common Rust code, often by 20-30%. Fixes PR28958. Differential Revision: https://reviews.llvm.org/D38374 llvm-svn: 319482
* [InlineCost] Prefer getFunction() to two calls to getParent().Davide Italiano2017-11-301-3/+3
| | | | | | Improves clarity, also slightly cheaper. NFCI. llvm-svn: 319481
* [SCEV][NFC] Break from loop after we found first non-Phi in ↵Max Kazantsev2017-11-291-1/+5
| | | | | | getAddRecExprPHILiterally llvm-svn: 319306
* [SCEV][NFC] Remove condition that can never happen due to check few lines aboveMax Kazantsev2017-11-291-2/+0
| | | | llvm-svn: 319293
* [SCEV][NFC] More efficient caching in CompareValueComplexityMax Kazantsev2017-11-281-4/+4
| | | | | | | | | | | | | | Currently, we use a set of pairs to cache responces like `CompareValueComplexity(X, Y) == 0`. If we had proved that `CompareValueComplexity(S1, S2) == 0` and `CompareValueComplexity(S2, S3) == 0`, this cache does not allow us to prove that `CompareValueComplexity(S1, S3)` is also `0`. This patch replaces this set with `EquivalenceClasses` that merges Values into equivalence sets so that any two values from the same set are equal from point of `CompareValueComplexity`. This, in particular, allows us to prove the fact from example above. Differential Revision: https://reviews.llvm.org/D40429 llvm-svn: 319153
* [SCEV][NFC] More efficient caching in CompareSCEVComplexityMax Kazantsev2017-11-281-8/+9
| | | | | | | | | | | | | Currently, we use a set of pairs to cache responces like `CompareSCEVComplexity(X, Y) == 0`. If we had proved that `CompareSCEVComplexity(S1, S2) == 0` and `CompareSCEVComplexity(S2, S3) == 0`, this cache does not allow us to prove that `CompareSCEVComplexity(S1, S3)` is also `0`. This patch replaces this set with `EquivalenceClasses` any two values from the same set are equal from point of `CompareSCEVComplexity`. This, in particular, allows us to prove the fact from example above. Differential Revision: https://reviews.llvm.org/D40428 llvm-svn: 319149
* [PartiallyInlineLibCalls][x86] add TTI hook to allow sqrt inlining to depend ↵Sanjay Patel2017-11-271-0/+4
| | | | | | | | | | | on arg rather than result This should fix PR31455: https://bugs.llvm.org/show_bug.cgi?id=31455 Differential Revision: https://reviews.llvm.org/D28314 llvm-svn: 319094
* [InstSimplify] use m_APFloat to simplify fcmp folds; NFCISanjay Patel2017-11-271-13/+7
| | | | llvm-svn: 319043
* [SCEV] Adding a check on outgoing branches of a terminator instr for ↵Jatin Bhateja2017-11-261-10/+13
| | | | | | | | | | | | | | | | | | | | | | SCEVBackedgeConditionFolder, NFC. Summary: For a given loop, getLoopLatch returns a non-null value when a loop has only one latch block. In the modified context adding an assertion to check that both the outgoing branches of a terminator instruction (of latch) does not target same header. + few minor code reorganization. Reviewers: jbhateja Reviewed By: jbhateja Subscribers: sanjoy Differential Revision: https://reviews.llvm.org/D40460 llvm-svn: 318997
* [SCEV] NFC : Removing unnecessary check on outgoing branches of a branch instr.Jatin Bhateja2017-11-261-2/+1
| | | | | | | | | | | | | | | | | Summary: For a given loop, getLoopLatch returns a non-null value when a loop has only one latch block. In the modified context a check on both the outgoing branches of a terminator instruction (of latch) to same header is redundant. Reviewers: jbhateja Reviewed By: jbhateja Subscribers: sanjoy Differential Revision: https://reviews.llvm.org/D40460 llvm-svn: 318991
* IR printing improvement for loop passesFedor Sergeev2017-11-221-0/+19
| | | | | | | | | | | | | | | | | | | Summary: Loop-pass printing is somewhat deficient since it does not provide the context around the loop (e.g. preheader). This context information becomes pretty essential when analyzing transformations that move stuff out of the loop. Extending printLoop to cover preheader and exit blocks (if any). Reviewers: sanjoy, silvas, weimingz Reviewed By: sanjoy Subscribers: apilipenko, skatkov, llvm-commits Differential Revision: https://reviews.llvm.org/D40246 llvm-svn: 318878
* [SCEV] Strengthen variance condition in calculateLoopDispositionMax Kazantsev2017-11-221-2/+4
| | | | | | | | | | | | | | | | | | | | | | | | | Given loops `L1` and `L2` with AddRecs `AR1` and `AR2` varying in them respectively. When identifying loop disposition of `AR2` w.r.t. `L1`, we only say that it is varying if `L1` contains `L2`. But there is also a possible situation where `L1` and `L2` are consecutive sibling loops within the parent loop. In this case, `AR2` is also varying w.r.t. `L1`, but we don't correctly identify it. It can lead, for exaple, to attempt of incorrect folding. Consider: AR1 = {a,+,b}<L1> AR2 = {c,+,d}<L2> EXAR2 = sext(AR1) MUL = mul AR1, EXAR2 If we incorrectly assume that `EXAR2` is invariant w.r.t. `L1`, we can end up trying to construct something like: `{a * {c,+,d}<L2>,+,b * {c,+,d}<L2>}<L1>`, which is incorrect because `AR2` is not available on entrance of `L1`. Both situations "`L1` contains `L2`" and "`L1` preceeds sibling loop `L2`" can be handled with one check: "header of `L1` dominates header of `L2`". This patch replaces the old insufficient check with this one. Differential Revision: https://reviews.llvm.org/D39453 llvm-svn: 318819
* Fix r318786Hans Wennborg2017-11-211-2/+2
| | | | llvm-svn: 318787
* removed unused private method decl. NFCNuno Lopes2017-11-211-3/+2
| | | | llvm-svn: 318786
OpenPOWER on IntegriCloud