summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* Rename getMaximumUnrollFactor -> getMaxInterleaveFactor; also rename option ↵Sanjay Patel2014-09-101-3/+3
| | | | | | | | | | | names controlling this variable. "Unroll" is not the appropriate name for this variable. Clang already uses the term "interleave" in pragmas and metadata for this. Differential Revision: http://reviews.llvm.org/D5066 llvm-svn: 217528
* Make use @llvm.assume for loop guards in ScalarEvolutionHal Finkel2014-09-071-6/+24
| | | | | | | | | This adds a basic (but important) use of @llvm.assume calls in ScalarEvolution. When SE is attempting to validate a condition guarding a loop (such as whether or not the loop count can be zero), this check should also include dominating assumptions. llvm-svn: 217348
* Make use of @llvm.assume from LazyValueInfoHal Finkel2014-09-071-77/+189
| | | | | | | | | | | | | | | | | | | | | | | This change teaches LazyValueInfo to use the @llvm.assume intrinsic. Like with the known-bits change (r217342), this requires feeding a "context" instruction pointer through many functions. Aside from a little refactoring to reuse the logic that turns predicates into constant ranges in LVI, the only new code is that which can 'merge' the range from an assumption into that otherwise computed. There is also a small addition to JumpThreading so that it can have LVI use assumptions in the same block as the comparison feeding a conditional branch. With this patch, we can now simplify this as expected: int foo(int a) { __builtin_assume(a > 5); if (a > 3) { bar(); return 1; } return 0; } llvm-svn: 217345
* Add additional patterns for @llvm.assume in ValueTrackingHal Finkel2014-09-071-0/+212
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This builds on r217342, which added the infrastructure to compute known bits using assumptions (@llvm.assume calls). That original commit added only a few patterns (to catch common cases related to determining pointer alignment); this change adds several other patterns for simple cases. r217342 contained that, for assume(v & b = a), bits in the mask that are known to be one, we can propagate known bits from the a to v. It also had a known-bits transfer for assume(a = b). This patch adds: assume(~(v & b) = a) : For those bits in the mask that are known to be one, we can propagate inverted known bits from the a to v. assume(v | b = a) : For those bits in b that are known to be zero, we can propagate known bits from the a to v. assume(~(v | b) = a): For those bits in b that are known to be zero, we can propagate inverted known bits from the a to v. assume(v ^ b = a) : For those bits in b that are known to be zero, we can propagate known bits from the a to v. For those bits in b that are known to be one, we can propagate inverted known bits from the a to v. assume(~(v ^ b) = a) : For those bits in b that are known to be zero, we can propagate inverted known bits from the a to v. For those bits in b that are known to be one, we can propagate known bits from the a to v. assume(v << c = a) : For those bits in a that are known, we can propagate them to known bits in v shifted to the right by c. assume(~(v << c) = a) : For those bits in a that are known, we can propagate them inverted to known bits in v shifted to the right by c. assume(v >> c = a) : For those bits in a that are known, we can propagate them to known bits in v shifted to the right by c. assume(~(v >> c) = a) : For those bits in a that are known, we can propagate them inverted to known bits in v shifted to the right by c. assume(v >=_s c) where c is non-negative: The sign bit of v is zero assume(v >_s c) where c is at least -1: The sign bit of v is zero assume(v <=_s c) where c is negative: The sign bit of v is one assume(v <_s c) where c is non-positive: The sign bit of v is one assume(v <=_u c): Transfer the known high zero bits assume(v <_u c): Transfer the known high zero bits (if c is know to be a power of 2, transfer one more) A small addition to InstCombine was necessary for some of the test cases. The problem is that when InstCombine was simplifying and, or, etc. it would fail to check the 'do I know all of the bits' condition before checking less specific conditions and would not fully constant-fold the result. I'm not sure how to trigger this aside from using assumptions, so I've just included the change here. llvm-svn: 217343
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-078-250/+729
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change, which allows @llvm.assume to be used from within computeKnownBits (and other associated functions in ValueTracking), adds some (optional) parameters to computeKnownBits and friends. These functions now (optionally) take a "context" instruction pointer, an AssumptionTracker pointer, and also a DomTree pointer, and most of the changes are just to pass this new information when it is easily available from InstSimplify, InstCombine, etc. As explained below, the significant conceptual change is that known properties of a value might depend on the control-flow location of the use (because we care that the @llvm.assume dominates the use because assumptions have control-flow dependencies). This means that, when we ask if bits are known in a value, we might get different answers for different uses. The significant changes are all in ValueTracking. Two main changes: First, as with the rest of the code, new parameters need to be passed around. To make this easier, I grouped them into a structure, and I made internal static versions of the relevant functions that take this structure as a parameter. The new code does as you might expect, it looks for @llvm.assume calls that make use of the value we're trying to learn something about (often indirectly), attempts to pattern match that expression, and uses the result if successful. By making use of the AssumptionTracker, the process of finding @llvm.assume calls is not expensive. Part of the structure being passed around inside ValueTracking is a set of already-considered @llvm.assume calls. This is to prevent a query using, for example, the assume(a == b), to recurse on itself. The context and DT params are used to find applicable assumptions. An assumption needs to dominate the context instruction, or come after it deterministically. In this latter case we only handle the specific case where both the assumption and the context instruction are in the same block, and we need to exclude assumptions from being used to simplify their own ephemeral values (those which contribute only to the assumption) because otherwise the assumption would prove its feeding comparison trivial and would be removed. This commit adds the plumbing and the logic for a simple masked-bit propagation (just enough to write a regression test). Future commits add more patterns (and, correspondingly, more regression tests). llvm-svn: 217342
* Add functions for finding ephemeral valuesHal Finkel2014-09-072-8/+103
| | | | | | | | | | | | | | | | This adds a set of utility functions for collecting 'ephemeral' values. These are LLVM IR values that are used only by @llvm.assume intrinsics (directly or indirectly), and thus will be removed prior to code generation, implying that they should be considered free for certain purposes (like inlining). The inliner's cost analysis, and a few other passes, have been updated to account for ephemeral values using the provided functionality. This functionality is important for the usability of @llvm.assume, because it limits the "non-local" side-effects of adding llvm.assume on inlining, loop unrolling, etc. (these are hints, and do not generate code, so they should not directly contribute to estimates of execution cost). llvm-svn: 217335
* Add an Assumption-Tracking PassHal Finkel2014-09-072-0/+114
| | | | | | | | | | | | | | | | | | | | | | | | This adds an immutable pass, AssumptionTracker, which keeps a cache of @llvm.assume call instructions within a module. It uses callback value handles to keep stale functions and intrinsics out of the map, and it relies on any code that creates new @llvm.assume calls to notify it of the new instructions. The benefit is that code needing to find @llvm.assume intrinsics can do so directly, without scanning the function, thus allowing the cost of @llvm.assume handling to be negligible when none are present. The current design is intended to be lightweight. We don't keep track of anything until we need a list of assumptions in some function. The first time this happens, we scan the function. After that, we add/remove @llvm.assume calls from the cache in response to registration calls and ValueHandle callbacks. There are no new direct test cases for this pass, but because it calls it validation function upon module finalization, we'll pick up detectable inconsistencies from the other tests that touch @llvm.assume calls. This pass will be used by follow-up commits that make use of @llvm.assume. llvm-svn: 217334
* Add override to overriden virtual methods, remove virtual keywords.Benjamin Kramer2014-09-031-13/+11
| | | | | | No functionality change. Changes made by clang-tidy + some manual cleanup. llvm-svn: 217028
* [CFLAA] Remove one final initializer listHal Finkel2014-09-031-1/+5
| | | | | | Maybe MSVC will be happy now... llvm-svn: 217000
* [CFLAA] And even more MSVC fixesHal Finkel2014-09-022-3/+6
| | | | | | Remove a couple more initializer lists and constexpr dependencies. llvm-svn: 216998
* [CFLAA] More cleanup for MSVCHal Finkel2014-09-022-11/+14
| | | | | | Remove more initializer lists, etc. llvm-svn: 216994
* [CFLAA] No initializer lists for MSVCHal Finkel2014-09-022-28/+30
| | | | | | MSVC 2012 does not understand initializer lists; remove them. llvm-svn: 216991
* [CFLAA] Remove tautological comparisonHal Finkel2014-09-021-1/+1
| | | | | | | | Fixes this (the warning is right, the unsigned value is not negative): lib/Analysis/StratifiedSets.h:689:53: warning: comparison of unsigned expression >= 0 is always true [-Wtautological-compare] bool inbounds(StratifiedIndex N) const { return N >= 0 && N < Links.size(); } llvm-svn: 216987
* [CFLAA] LLVM_CONSTEXPR -> constHal Finkel2014-09-021-1/+1
| | | | | | | The number is just a constant, and this should make MSVC happy (or at least happier). llvm-svn: 216981
* [CFLAA] constexpr -> LLVM_CONSTEXPRHal Finkel2014-09-022-13/+15
| | | | | | Attempt to fix the MSVC build by not using constexpr. llvm-svn: 216979
* Add a CFL Alias Analysis implementationHal Finkel2014-09-024-0/+1674
| | | | | | | | | | | | | | | | This provides an implementation of CFL alias analysis (including some supporting data structures). Currently, we don't have any extremely fancy features, sans some interprocedural analysis (i.e. no field sensitivity, etc.), and we do best sitting behind BasicAA + TBAA. In such a configuration, we take ~0.6-0.8% of total compile time, and give ~7-8% NoAlias responses to queries TBAA and BasicAA couldn't answer when bootstrapping LLVM. In testing this on other projects, we've seen up to 10.5% of queries dropped by BasicAA+TBAA answered with NoAlias by this algorithm. Patch by George Burgess IV (with minor modifications by me -- mostly adapting some BasicAA tests), thanks! llvm-svn: 216970
* Fix MemoryDependenceAnalysis in cases where QueryInstr is a CmpXchg or a ↵Robin Morisset2014-09-021-4/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | AtomicRMW Summary: MemoryDependenceAnalysis is currently cautious when the QueryInstr is an atomic load or store, but I forgot to check for atomic cmpxchg/atomicrmw. This patch is a way of fixing that, and making it less brittle (i.e. no risk that I forget another possible kind of atomic, even if the IR ends up changing in the future), by adding a fallback checking mayReadOrWriteFromMemory. Thanks to Philip Reames for finding this bug and suggesting this solution in http://reviews.llvm.org/D4845 Sadly, I don't see how to add a test for this, since the passes depending on MemoryDependenceAnalysis won't trigger for an atomic rmw anyway. Does anyone see a way for testing it? Test Plan: none possible at first sight Reviewers: jfb, reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D5019 llvm-svn: 216940
* Remove an errant outer loop that contains nothing but an inner loop over ↵Nick Lewycky2014-09-011-58/+53
| | | | | | exactly the same elements. While no functionality is change intended (and hence there are no changes to tests), you don't want to skip this revision if bisecting for errors. llvm-svn: 216864
* Remove 'virtual' keyword from methods markedwith 'override' keyword.Craig Topper2014-08-301-3/+3
| | | | llvm-svn: 216823
* Fix typos in comments, NFCRobin Morisset2014-08-292-2/+2
| | | | | | | | | | | | | | Summary: Just fixing comments, no functional change. Test Plan: N/A Reviewers: jfb Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D5130 llvm-svn: 216784
* Relax the constraint more in MemoryDependencyAnalysis.cppRobin Morisset2014-08-291-6/+40
| | | | | | | | Even loads/stores that have a stronger ordering than monotonic can be safe. The rule is no release-acquire pair on the path from the QueryInst, assuming that the QueryInst is not atomic itself. llvm-svn: 216771
* Make fabs safe to speculatively executeMatt Arsenault2014-08-291-0/+1
| | | | llvm-svn: 216736
* InstSimplify: Move a transform from InstCombine to InstSimplifyDavid Majnemer2014-08-281-0/+35
| | | | | | | | Several combines involving icmp (shl C2, %X) C1 can be simplified without introducing any new instructions. Move them to InstSimplify; while we are at it, make them more powerful. llvm-svn: 216642
* InstSimplify: Don't simplify gep X, (Y-X) to Y if types differDavid Majnemer2014-08-271-1/+2
| | | | | | | | | It's incorrect to perform this simplification if the types differ. A bitcast would need to be inserted for this to work. This fixes PR20771. llvm-svn: 216597
* Reland r216439 215441, majnemer has a real fix for PR20771.Nico Weber2014-08-271-11/+53
| | | | llvm-svn: 216586
* Revert r216439 (and r216441, else the former doesn't revert cleanly).Nico Weber2014-08-271-53/+11
| | | | | | It caused PR 20771. I'll land a test on the clang side. llvm-svn: 216582
* InstSimplify: Compute comparison ranges for left shift instructionsDavid Majnemer2014-08-271-0/+16
| | | | | | | | 'shl nuw CI, x' produces [CI, CI << CLZ(CI)] 'shl nsw CI, x' produces [CI << CLO(CI)-1, CI] if CI is negative 'shl nsw CI, x' produces [CI, CI << CLZ(CI)-1] if CI is non-negative llvm-svn: 216570
* InstSimplify: Fold gep X, (sub 0, ptrtoint(X)) to nullDavid Majnemer2014-08-261-21/+32
| | | | | | | Save InstCombine some work if we can perform this fold during InstSimplify. llvm-svn: 216441
* InstSimplify: Simplify trivial pointer expressions like b + (e - b)David Majnemer2014-08-261-5/+36
| | | | | | | | | | | | | | | | | | | | | | | | consider: long long *f(long long *b, long long *e) { return b + (e - b); } we would lower this to something like: define i64* @f(i64* %b, i64* %e) { %1 = ptrtoint i64* %e to i64 %2 = ptrtoint i64* %b to i64 %3 = sub i64 %1, %2 %4 = ashr exact i64 %3, 3 %5 = getelementptr inbounds i64* %b, i64 %4 ret i64* %5 } This should fold away to just 'e'. N.B. This adds m_SpecificInt as a convenient way to match against a particular 64-bit integer when using LLVM's match interface. llvm-svn: 216439
* Analysis: cleanupDylan Noblesmith2014-08-261-3/+2
| | | | | | Address review comments. llvm-svn: 216432
* Revert "Analysis: unique_ptr-ify DependenceAnalysis::collectCoeffInfo"Dylan Noblesmith2014-08-261-8/+8
| | | | | | This reverts commit r216358. llvm-svn: 216431
* Modernize raw_fd_ostream's constructor a bit.Rafael Espindola2014-08-251-8/+8
| | | | | | | | | | Take a StringRef instead of a "const char *". Take a "std::error_code &" instead of a "std::string &" for error. A create static method would be even better, but this patch is already a bit too big. llvm-svn: 216393
* Allow vectorization of division by uniform power of 2.Karthik Bhat2014-08-251-6/+8
| | | | | | | | This patch adds support to recognize division by uniform power of 2 and modifies the cost table to vectorize division by uniform power of 2 whenever possible. Updates Cost model for Loop and SLP Vectorizer.The cost table is currently only updated for X86 backend. Thanks to Hal, Andrea, Sanjay for the review. (http://reviews.llvm.org/D4971) llvm-svn: 216371
* Analysis: unique_ptr-ify DependenceAnalysis::collectCoeffInfoDylan Noblesmith2014-08-251-8/+8
| | | | llvm-svn: 216358
* Analysis: unique_ptr-ify DependenceAnalysis::dependsDylan Noblesmith2014-08-251-8/+8
| | | | llvm-svn: 216357
* Analysis: take a reference instead of pointerDylan Noblesmith2014-08-251-6/+5
| | | | | | This parameter is never null. llvm-svn: 216356
* Use range based for loops to avoid needing to re-mention SmallPtrSet size.Craig Topper2014-08-242-31/+20
| | | | llvm-svn: 216351
* ValueTracking: Figure out more bits when looking at add/subDavid Majnemer2014-08-221-66/+38
| | | | | | | | | Given something like X01XX + X01XX, we know that the result must look like X1XXX. Adapted from a patch by Richard Smith, test-case written by me. llvm-svn: 216250
* Repace SmallPtrSet with SmallPtrSetImpl in function arguments to avoid ↵Craig Topper2014-08-214-6/+6
| | | | | | needing to mention the size. llvm-svn: 216158
* Answer to Philip Reames commentsRobin Morisset2014-08-181-6/+27
| | | | | | | | | | - add check for volatile (probably unneeded, but I agree that we should be conservative about it). - strengthen condition from isUnordered() to isSimple(), as I don't understand well enough Unordered semantics (and it also matches the comment better this way) to be confident in the previous behaviour (thanks for catching that one, I had missed the case Monotonic/Unordered). - separate a condition in two. - lengthen comment about aliasing and loads - add tests in GVN/atomic.ll llvm-svn: 215943
* Weak relaxing of the constraints on atomics in MemoryDependencyAnalysisRobin Morisset2014-08-181-4/+22
| | | | | | | Monotonic accesses do not have to kill the analysis, as long as the QueryInstr is not itself atomic. llvm-svn: 215942
* Revert "Repace SmallPtrSet with SmallPtrSetImpl in function arguments to ↵Craig Topper2014-08-184-6/+6
| | | | | | | | avoid needing to mention the size." Getting a weird buildbot failure that I need to investigate. llvm-svn: 215870
* Repace SmallPtrSet with SmallPtrSetImpl in function arguments to avoid ↵Craig Topper2014-08-174-6/+6
| | | | | | needing to mention the size. llvm-svn: 215868
* In LVI(Lazy Value Info), originally value on a BB can only be caculated once,Jiangning Liu2014-08-111-2/+17
| | | | | | | | | and the lattice will be updated to be a state other than "undefined". This limiation could miss some opportunities of lowering "overdefined" to be an even accurate value. So this patch ask the algorithm to try to lower the lattice value again even if the value has been lowered to be "overdefined". llvm-svn: 215343
* Remove Support/IncludeFile.h and its only user. This is actively harmful, sinceRichard Smith2014-08-071-3/+0
| | | | | | | | | | | | | it breaks the modules builds (where CallGraph.h can be quite reasonably transitively included by an unimported portion of a module, and CallGraph.cpp not linked in), and appears to have been entirely redundant since PR780 was fixed back in 2008. If this breaks anything, please revert; I have only tested this with a single configuration, and it's possible that this is still somehow fixing something (though I doubt it, since no other similar file uses this mechanism any more). llvm-svn: 215142
* Teach the SLP Vectorizer that keeping some values live over a callsite can ↵James Molloy2014-08-051-0/+10
| | | | | | | | have a cost. Some types, such as 128-bit vector types on AArch64, don't have any callee-saved registers. So if a value needs to stay live over a callsite, it must be spilled and refilled. This cost is now taken into account. llvm-svn: 214859
* Fix ScalarEvolutionExpander when creating a PHI in a block with duplicate ↵Hal Finkel2014-07-311-1/+5
| | | | | | | | | | | | | | predecessors It seems that when I fixed this, almost exactly a year ago, I did not quite do it correctly. When we have duplicate block predecessors, we can indeed not have different incoming values for the same block, but we *must* have duplicate entries. So, instead of skipping the duplicates, we explicitly add the duplicate incoming values. Fixes PR20442. llvm-svn: 214423
* InstSimplify: Simplify (X - (0 - Y)) if the second sub is NUWDavid Majnemer2014-07-311-0/+12
| | | | | | | | | | | If the NUW bit is set for 0 - Y, we know that all values for Y other than 0 would produce a poison value. This allows us to replace (0 - Y) with 0 in the expression (X - (0 - Y)) which will ultimately leave us with X. This partially fixes PR20189. llvm-svn: 214384
* Add @llvm.assume, lowering, and some basic propertiesHal Finkel2014-07-252-4/+29
| | | | | | | | | | | | | | | | | This is the first commit in a series that add an @llvm.assume intrinsic which can be used to provide the optimizer with a condition it may assume to be true (when the control flow would hit the intrinsic call). Some basic properties are added here: - llvm.invariant(true) is dead. - llvm.invariant(false) is unreachable (this directly corresponds to the documented behavior of MSVC's __assume(0)), so is llvm.invariant(undef). The intrinsic is tagged as writing arbitrarily, in order to maintain control dependencies. BasicAA has been updated, however, to return NoModRef for any particular location-based query so that we don't unnecessarily block code motion. llvm-svn: 213973
* Simplify and improve scoped-noalias metadata semanticsHal Finkel2014-07-251-47/+51
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In the process of fixing the noalias parameter -> metadata conversion process that will take place during inlining (which will be committed soon, but not turned on by default), I have come to realize that the semantics provided by yesterday's commit are not really what we want. Here's why: void foo(noalias a, noalias b, noalias c, bool x) { *q = x ? a : b; *c = *q; } Generically, we know that *c does not alias with *a and with *b (so there is an 'and' in what we know we're not), and we know that *q might be derived from *a or from *b (so there is an 'or' in what we know that we are). So we do not want the semantics currently, where any noalias scope matching any alias.scope causes a NoAlias return. What we want to know is that the noalias scopes form a superset of the alias.scope list (meaning that all the things we know we're not is a superset of all of things the other instruction might be). Making that change, however, introduces a composibility problem. If we inline once, adding the noalias metadata, and then inline again adding more, and we append new scopes onto the noalias and alias.scope lists each time. But, this means that we could change what was a NoAlias result previously into a MayAlias result because we appended an additional scope onto one of the alias.scope lists. So, instead of giving scopes the ability to have parents (which I had borrowed from the TBAA implementation, but seems increasingly unlikely to be useful in practice), I've given them domains. The subset/superset condition now applies within each domain independently, and we only need it to hold in one domain. Each time we inline, we add the new scopes in a new scope domain, and everything now composes nicely. In addition, this simplifies the implementation. llvm-svn: 213948
OpenPOWER on IntegriCloud