summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* [InstSimplify] fix formatting; NFCSanjay Patel2018-04-101-7/+7
| | | | llvm-svn: 329736
* [DA] Improve alias checking in dependence analysisDavid Green2018-04-101-10/+37
| | | | | | | | | | | | Improve the alias analysis to account for cases where we know that src/dst pairs cannot alias due to things like TBAA. As we know they are noalias, we know no dependency can occur. Also fixes issues around the size parameter to AA being incorrect. Differential Revision: https://reviews.llvm.org/D42381 llvm-svn: 329692
* [MemorySSA] remove cruft; NFC.George Burgess IV2018-04-091-23/+1
| | | | | | | | | | | | The caching walker used to hold its own caches, which made its `reset()` function meaningful. Since caching has been moved out of it, there's no reason to continue to have these cache-related methods. Similarly, the EXPENSIVE_CHECKS block that's getting removed used to rerun the query with caching disabled. Since that's how we always do queries now, it's redundant. llvm-svn: 329638
* [MemorySSA] Remove redundant assert; NFCGeorge Burgess IV2018-04-091-3/+0
| | | | | | | The `if (!Def && !Use) return nullptr;` right above this assert sort of defeats the purpose. llvm-svn: 329632
* [MemorySSAUpdater] Mark Phi users of a node being moved as non-optimizeZhaoshi Zheng2018-04-091-0/+17
| | | | | | | | | | Fix PR36484, as suggested: <quote> during moves, mark the direct users of the erased things that were phis as "not to be optimized" <quote> llvm-svn: 329621
* [NFC] Loosen restriction on preheader to fix buildbotMax Kazantsev2018-04-061-5/+5
| | | | llvm-svn: 329379
* Don't inline @llvm.icall.branch.funnelVitaly Buka2018-04-041-9/+14
| | | | | | | | | | | | | | Summary: @llvm.icall.branch.funnel is musttail with variable number of arguments. After inlining current backend can't separate call targets from call arguments. Reviewers: pcc Subscribers: hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D45116 llvm-svn: 329235
* [MemorySSA] Fix spelling errors in MemorySSA.cpp. NFCZhaoshi Zheng2018-04-041-2/+2
| | | | llvm-svn: 329230
* [Analysis] Support aligned new/delete functions.Eric Fiselier2018-04-042-0/+45
| | | | | | | | | | | | | | | | Summary: Clang's __builtin_operator_new/delete was recently taught about the aligned allocation overloads (r328134). This patch makes LLVM aware of them as well. This allows the compiler to perform certain optimizations including eliding new/delete calls. Reviewers: rsmith, majnemer, dblaikie, vsk, bkramer Reviewed By: bkramer Subscribers: ckennelly, llvm-commits Differential Revision: https://reviews.llvm.org/D44769 llvm-svn: 329218
* Revert "[Analysis] Support aligned new/delete functions."Eric Fiselier2018-04-042-45/+0
| | | | | | This reverts commit bee3bbd9bdd3ab3364b8fb0cdb6326bc1ae740e0. llvm-svn: 329217
* [Analysis] Support aligned new/delete functions.Eric Fiselier2018-04-042-0/+45
| | | | | | | | | | | | | | | | Summary: Clang's __builtin_operator_new/delete was recently taught about the aligned allocation overloads (r328134). This patch makes LLVM aware of them as well. This allows the compiler to perform certain optimizations including eliding new/delete calls. Reviewers: rsmith, majnemer, dblaikie, vsk, bkramer Reviewed By: bkramer Subscribers: ckennelly, llvm-commits Differential Revision: https://reviews.llvm.org/D44769 llvm-svn: 329215
* Make helpers static. NFC.Benjamin Kramer2018-04-041-1/+3
| | | | llvm-svn: 329170
* [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
* [SLP] Fix PR36481: vectorize reassociated instructions.Alexey Bataev2018-04-031-0/+61
| | | | | | | | | | | | | | | | | | Summary: If the load/extractelement/extractvalue instructions are not originally consecutive, the SLP vectorizer is unable to vectorize them. Patch allows reordering of such instructions. Patch does not support reordering of the repeated instruction, this must be handled in the separate patch. Reviewers: RKSimon, spatel, hfinkel, mkuper, Ayal, ashahid Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43776 llvm-svn: 329085
* Revert "[SLP] Fix PR36481: vectorize reassociated instructions."Benjamin Kramer2018-04-031-61/+0
| | | | | | This reverts commit r328980 and r329046. Makes the vectorizer crash. llvm-svn: 329071
* [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
* [SLP] Fix PR36481: vectorize reassociated instructions.Alexey Bataev2018-04-021-0/+61
| | | | | | | | | | | | | | | Summary: If the load/extractelement/extractvalue instructions are not originally consecutive, the SLP vectorizer is unable to vectorize them. Patch allows reordering of such instructions. Reviewers: RKSimon, spatel, hfinkel, mkuper, Ayal, ashahid Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43776 llvm-svn: 328980
* [Analysis] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-018-21/+21
| | | | | | | | | | | | | | | | | | | | | | 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
* [ThinLTO] Add an option to force summary call edges cold for debuggingTeresa Johnson2018-03-311-1/+18
| | | | | | | | | | | | | | Summary: Useful to selectively disable importing into specific modules for debugging/triaging/workarounds. Reviewers: eraman Subscribers: inglorion, llvm-commits Differential Revision: https://reviews.llvm.org/D45062 llvm-svn: 328909
* Fix a bunch of typoes. NFCFangrui Song2018-03-301-1/+1
| | | | llvm-svn: 328907
* Fix an accidental circular dependencePhilip Reames2018-03-291-1/+1
| | | | llvm-svn: 328816
* [NFC] Fix meaningless assert in SCEVMax Kazantsev2018-03-291-2/+2
| | | | llvm-svn: 328764
* [MemorySSA] Turn an assert into a conditionGeorge Burgess IV2018-03-291-2/+2
| | | | | | | | | | | | Eli pointed out that variadic functions are totally a thing, so this assert is incorrect. No test-case is provided, since the only way this assert fires is if a specific DenseMap falls back to doing `isEqual` checks, and that seems fairly brittle (and requires a pyramid of growing `call void (i8, ...) @varargs(i8 0)`). llvm-svn: 328755
* [MemorySSA] Consider callsite args for hashing and equality.George Burgess IV2018-03-291-9/+20
| | | | | | | | | | | | | | We use a `DenseMap<MemoryLocOrCall, MemlocStackInfo>` to keep track of prior work when optimizing uses in MemorySSA. Because we weren't accounting for callsite arguments in either the hash code or equality tests for `MemoryLocOrCall`s, we optimized uses too aggressively in some rare cases. Fix by Daniel Berlin. Should fix PR36883. llvm-svn: 328748
* Plumb useAA through TargetTransformInfo to remove Transforms->CodeGen header ↵David Blaikie2018-03-281-0/+2
| | | | | | | | dependency Thanks to echristo for the pointers on direction. llvm-svn: 328737
* [NFC] OptPassGate extracted from OptBisectFedor Sergeev2018-03-273-3/+3
| | | | | | | | | | | | | | | Summary: This is an NFC refactoring of the OptBisect class to split it into an optional pass gate interface used by LLVMContext and the Optional Pass Bisector (OptBisect) used for debugging of optional passes. This refactoring is needed for D44464, which introduces setOptPassGate() method to allow implementations other than OptBisect. Patch by Yevgeny Rouban. Reviewers: andrew.w.kaylor, fedor.sergeev, vsk, dberlin, Eugene.Zelenko, reames, skatkov Reviewed By: fedor.sergeev Differential Revision: https://reviews.llvm.org/D44821 llvm-svn: 328637
* [LV] Add TTI::shouldMaximizeVectorBandwidth to allow enabling it per targetKrzysztof Parzyszek2018-03-271-0/+4
| | | | | | | | The default implementation returns false and keeps the current behavior. Differential Revision: https://reviews.llvm.org/D44735 llvm-svn: 328632
* [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
* [MemorySSA] Fix exponential compile-time updating MemorySSA.Eli Friedman2018-03-261-15/+28
| | | | | | | | | | | | | | | | | | | | | | | MemorySSAUpdater::getPreviousDefRecursive is a recursive algorithm, for each block, it computes the previous definition for each predecessor, then takes those definitions and combines them. But currently it doesn't remember results which it already computed; this means it can visit the same block multiple times, which adds up to exponential time overall. To fix this, this patch adds a cache. If we computed the result for a block already, we don't need to visit it again because we'll come up with the same result. Well, unless we RAUW a MemoryPHI; in that case, the TrackingVH will be updated automatically. This matches the original source paper for this algorithm. The testcase isn't really a test for the bug, but it adds coverage for the case where tryRemoveTrivialPhi erases an existing PHI node. (It's hard to write a good regression test for a performance issue.) Differential Revision: https://reviews.llvm.org/D44715 llvm-svn: 328577
* [LSR] Allow giving priority to post-incrementing addressing modesKrzysztof Parzyszek2018-03-261-0/+14
| | | | | | | | | | | Implement TTI interface for targets to indicate that the LSR should give priority to post-incrementing addressing modes. Combination of patches by Sebastian Pop and Brendon Cahoon. Differential Revision: https://reviews.llvm.org/D44758 llvm-svn: 328490
* [PatternMatch] allow undef elements when matching vector FP +0.0Sanjay Patel2018-03-252-10/+11
| | | | | | | | | | | | | This continues the FP constant pattern matching improvements from: https://reviews.llvm.org/rL327627 https://reviews.llvm.org/rL327339 https://reviews.llvm.org/rL327307 Several integer constant matchers also have this ability. I'm separating matching of integer/pointer null from FP positive zero and renaming/commenting to make the functionality clearer. llvm-svn: 328461
* 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
* Fix a couple of layering violations in TransformsDavid Blaikie2018-03-211-1/+1
| | | | | | | | | | | | | Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering. Transforms depends on Transforms/Utils, not the other way around. So remove the header and the "createStripGCRelocatesPass" function declaration (& definition) that is unused and motivated this dependency. Move Transforms/Utils/Local.h into Analysis because it's used by Analysis/MemoryBuiltins.cpp. llvm-svn: 328165
* [InstSimplify] fp_binop X, NaN --> NaNSanjay Patel2018-03-211-10/+32
| | | | | | | | We propagate the existing NaN value when possible. Differential Revision: https://reviews.llvm.org/D44521 llvm-svn: 328140
* [MustExecute] Shwo the effect of using full loop info variantPhilip Reames2018-03-201-5/+7
| | | | | | | | Most basic possible test for the logic used by LICM. Also contains a speculative build fix for compiles which complain about a definition of a stuct K; followed by a declaration as class K; llvm-svn: 328058
* [MustExecute] Move isGuaranteedToExecute and related rourtines to AnalysisPhilip Reames2018-03-201-0/+135
| | | | | | Next step is to actually merge the implementations and get both implementations tested through the new printer. llvm-svn: 328055
* [MustExecute] Use the annotation style printerPhilip Reames2018-03-201-33/+54
| | | | | | | As suggested in the original review (https://reviews.llvm.org/D44524), use an annotation style printer instead. Note: The switch from -analyze to -disable-output in tests was driven by the fact that seems to be the idiomatic style used in annoation passes. I tried to keep both working, but the old style pass API for printers really doesn't make this easy. It invokes (runOnFunction, print(Module)) repeatedly. I decided the extra state wasn't worth it given the old pass manager is going away soonish anyway. llvm-svn: 328015
* Add an analysis printer for must execute reasoningPhilip Reames2018-03-203-0/+104
| | | | | | | | | | | | Many of our loop passes make use of so called "must execute" or "guaranteed to execute" facts to prove the legality of code motion. The basic notion is that we know (by assumption) an instruction didn't fault at it's original location, so if the location we move it to is strictly post dominated by the original, then we can't have introduced a new fault. At the moment, the testing for this logic is somewhat adhoc and done mostly through LICM. Since I'm working on that code, I want to improve the testing. This patch is the first step in that direction. It doesn't actually test the variant used by the loop passes - I need to move that to the Analysis library first - but instead exercises an alternate implementation used by SCEV. (I plan on merging both implementations.) Note: I'll be replacing the printing logic within this with an annotation based version in the near future. Anna suggested this in review, and it seems like a strictly better format. Differential Revision: https://reviews.llvm.org/D44524 llvm-svn: 328004
* [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
* [InstSimplify] loosen FMF for sqrt(X) * sqrt(X) --> XSanjay Patel2018-03-181-3/+6
| | | | | | | | | As shown in the code comment, we don't need all of 'fast', but we do need reassoc + nsz + nnan. Differential Revision: https://reviews.llvm.org/D43765 llvm-svn: 327796
* [GlobalsAA] Fix a pretty terrible bug that has been in GlobalsAA forChandler Carruth2018-03-161-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | a long time. The key thing is that we need to create value handles for every function that we create a `FunctionInfo` object around. Without this, when that function is deleted we can end up creating a new function that collides with its address and look up a stale AA result. With that AA result we can in turn miscompile code in ways that break. This is seriously one of the most absurd miscompiles I've seen. It only reproduced for us recently and only when building a very large server with both ThinLTO and PGO. A *HUGE* shout out to Wei Mi who tracked all of this down and came up with this patch. I'm just landing it because I happened to still by at a computer. He or I can work on crafting a test case to hit this (now that we know what to target) but it'll take a while, and we've been chasing this for a long time and need it fix Right Now. llvm-svn: 327761
* [NFC] Void variables used for asserts onlyMax Kazantsev2018-03-161-0/+2
| | | | llvm-svn: 327693
* [InstSimplify] peek through unsigned FP casts for sign-bit compares (PR36682)Roman Lebedev2018-03-151-0/+12
| | | | | | | | | | | | | | | | | | | This pattern came up in PR36682 / D44390 https://bugs.llvm.org/show_bug.cgi?id=36682 https://reviews.llvm.org/D44390 https://godbolt.org/g/oKvT5H See also D44421, D44424 Reviewers: spatel, majnemer, efriedma, arsenm Reviewed By: spatel Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D44425 llvm-svn: 327642
* [InstSimplify][NFC] simplifyICmpWithConstant(): refactor GetCompareTy() callsRoman Lebedev2018-03-151-4/+6
| | | | | | Preparation for D44425. llvm-svn: 327641
* [ConstantFolding, InstSimplify] Handle more vector GEPsMatthew Simpson2018-03-151-2/+2
| | | | | | | | | | This patch addresses some additional cases where the compiler crashes upon encountering vector GEPs. This should fix PR36116. Differential Revision: https://reviews.llvm.org/D44219 Reference: https://bugs.llvm.org/show_bug.cgi?id=36116 llvm-svn: 327638
* [PatternMatch, InstSimplify] allow undef elements when matching any vector ↵Sanjay Patel2018-03-151-8/+8
| | | | | | | | | | | FP zero This matcher implementation appears to be slightly more efficient than the generic constant check that it is replacing because every use was for matching FP patterns, but the previous code would check int and pointer type nulls too. llvm-svn: 327627
OpenPOWER on IntegriCloud