summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Add scoped-noalias metadataHal Finkel2014-07-244-0/+257
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit adds scoped noalias metadata. The primary motivations for this feature are: 1. To preserve noalias function attribute information when inlining 2. To provide the ability to model block-scope C99 restrict pointers Neither of these two abilities are added here, only the necessary infrastructure. In fact, there should be no change to existing functionality, only the addition of new features. The logic that converts noalias function parameters into this metadata during inlining will come in a follow-up commit. What is added here is the ability to generally specify noalias memory-access sets. Regarding the metadata, alias-analysis scopes are defined similar to TBAA nodes: !scope0 = metadata !{ metadata !"scope of foo()" } !scope1 = metadata !{ metadata !"scope 1", metadata !scope0 } !scope2 = metadata !{ metadata !"scope 2", metadata !scope0 } !scope3 = metadata !{ metadata !"scope 2.1", metadata !scope2 } !scope4 = metadata !{ metadata !"scope 2.2", metadata !scope2 } Loads and stores can be tagged with an alias-analysis scope, and also, with a noalias tag for a specific scope: ... = load %ptr1, !alias.scope !{ !scope1 } ... = load %ptr2, !alias.scope !{ !scope1, !scope2 }, !noalias !{ !scope1 } When evaluating an aliasing query, if one of the instructions is associated with an alias.scope id that is identical to the noalias scope associated with the other instruction, or is a descendant (in the scope hierarchy) of the noalias scope associated with the other instruction, then the two memory accesses are assumed not to alias. Note that is the first element of the scope metadata is a string, then it can be combined accross functions and translation units. The string can be replaced by a self-reference to create globally unqiue scope identifiers. [Note: This overview is slightly stylized, since the metadata nodes really need to just be numbers (!0 instead of !scope0), and the scope lists are also global unnamed metadata.] Existing noalias metadata in a callee is "cloned" for use by the inlined code. This is necessary because the aliasing scopes are unique to each call site (because of possible control dependencies on the aliasing properties). For example, consider a function: foo(noalias a, noalias b) { *a = *b; } that gets inlined into bar() { ... if (...) foo(a1, b1); ... if (...) foo(a2, b2); } -- now just because we know that a1 does not alias with b1 at the first call site, and a2 does not alias with b2 at the second call site, we cannot let inlining these functons have the metadata imply that a1 does not alias with b2. llvm-svn: 213864
* AA metadata refactoring (introduce AAMDNodes)Hal Finkel2014-07-248-134/+174
| | | | | | | | | | | | | | | | | | | | In order to enable the preservation of noalias function parameter information after inlining, and the representation of block-level __restrict__ pointer information (etc.), additional kinds of aliasing metadata will be introduced. This metadata needs to be carried around in AliasAnalysis::Location objects (and MMOs at the SDAG level), and so we need to generalize the current scheme (which is hard-coded to just one TBAA MDNode*). This commit introduces only the necessary refactoring to allow for the introduction of other aliasing metadata types, but does not actually introduce any (that will come in a follow-up commit). What it does introduce is a new AAMDNodes structure to hold all of the aliasing metadata nodes associated with a particular memory-accessing instruction, and uses that structure instead of the raw MDNode* in AliasAnalysis::Location, etc. No functionality change intended. llvm-svn: 213859
* Make use of the align parameter attribute for all pointer argumentsHal Finkel2014-07-221-6/+2
| | | | | | | | | | | | | | | | | | | | We previously supported the align attribute on all (pointer) parameters, but we only used it for byval parameters. However, it is completely consistent at the IR level to treat 'align n' on all pointer parameters as an alignment assumption on the pointer, and now we wll. Specifically, this causes computeKnownBits to use the align attribute on all pointer parameters, not just byval parameters. I've also added an explicit parameter attribute test for this to test/Bitcode/attributes.ll. And I've updated the LangRef to document the align parameter attribute (as it turns out, it was not documented at all previously, although the byval documentation mentioned that it could be used). There are (at least) two benefits to doing this: - It allows enhancing alignment based on the pointer alignment after inlining callees. - It allows simplification of pointer arithmetic. llvm-svn: 213670
* Match semantics of PointerMayBeCapturedBefore to its name by defaultHal Finkel2014-07-212-5/+14
| | | | | | | | | | | | | | | As it turns out, the capture tracker named CaptureBefore used by AA, and now available via the PointerMayBeCapturedBefore function, would have been more-aptly named CapturedBeforeOrAt, because it considers captures at the instruction provided. This is not always what one wants, and it is difficult to get the strictly-before behavior given only the current interface. This adds an additional parameter which controls whether or not you want to include captures at the provided instruction. The default is not to include the instruction provided, so that 'Before' matches its name. No functionality change intended. llvm-svn: 213582
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-215-21/+29
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* Move the CapturesBefore tracker from AA into CaptureTrackingHal Finkel2014-07-212-50/+81
| | | | | | | | | | | | | | | | | There were two generally-useful CaptureTracker classes defined in LLVM: the simple tracker defined in CaptureTracking (and made available via the PointerMayBeCaptured utility function), and the CapturesBefore tracker available only inside of AA. This change moves the CapturesBefore tracker into CaptureTracking, generalizes it slightly (by adding a ReturnCaptures parameter), and makes it generally available via a PointerMayBeCapturedBefore utility function. This logic will be needed, for example, to perform noalias function parameter attribute inference. No functionality change intended. llvm-svn: 213519
* Move isIdentifiedFunctionLocal from BasicAA to AAHal Finkel2014-07-212-11/+11
| | | | | | | | | | The ability to identify function locals will exist outside of BasicAA (for example, logic for inferring noalias function arguments will need this), so make this concept generally accessible without code duplication. No functionality change. llvm-svn: 213514
* Remove braces around single-statement block and rangify outer loop.Manuel Jacob2014-07-201-6/+3
| | | | | | This is a follow-up to r213474. llvm-svn: 213475
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-205-25/+20
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* Fix msc17 build. RegionInfo::RegionInfo::recalculate() doesn't make sense.NAKAMURA Takumi2014-07-201-4/+2
| | | | llvm-svn: 213466
* Fix -Asserts build introduced since r213456.NAKAMURA Takumi2014-07-201-0/+2
| | | | llvm-svn: 213465
* Templatify RegionInfo so it works on MachineBasicBlocksMatt Arsenault2014-07-194-789/+96
| | | | llvm-svn: 213456
* Remove uses of the redundant ".reset(nullptr)" of unique_ptr, in favor of ↵David Blaikie2014-07-191-1/+1
| | | | | | | | | | | ".reset()" It's also possible to just write "= nullptr", but there's some question of whether that's as readable, so I leave it up to authors to pick which they prefer for now. If we want to discuss standardizing on one or the other, we can do that at some point in the future. llvm-svn: 213438
* Add a dereferenceable attributeHal Finkel2014-07-181-1/+1
| | | | | | | | | This attribute indicates that the parameter or return pointer is dereferenceable. Practically speaking, loads from such a pointer within the associated byte range are safe to speculatively execute. Such pointer parameters are common in source languages (C++ references, for example). llvm-svn: 213385
* Rectify r213231. Use proper version of 'ComputeNumSignBits'.Suyog Sarda2014-07-171-1/+1
| | | | | | | | | Earlier when the code was in InstCombine, we were calling the version of ComputeNumSignBits in InstCombine.h that automatically added the DataLayout* before calling into ValueTracking. When the code moved to InstSimplify, we are calling into ValueTracking directly without passing in the DataLayout*. This patch rectifies the same by passing DataLayout in ComputeNumSignBits. llvm-svn: 213295
* Move ashr optimization from InstCombineShift to InstSimplify.Suyog Sarda2014-07-171-0/+5
| | | | | | | | | Refactor code, no functionality change, test case moved from instcombine to instsimplify. Differential Revision: http://reviews.llvm.org/D4102 llvm-svn: 213231
* Improve BasicAA CS-CS queries (redux)Hal Finkel2014-07-173-130/+151
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts, "r213024 - Revert r212572 "improve BasicAA CS-CS queries", it causes PR20303." with a fix for the bug in pr20303. As it turned out, the relevant code was both wrong and over-conservative (because, as with the code it replaced, it would return the overall ModRef mask even if just Ref had been implied by the argument aliasing results). Hopefully, this correctly fixes both problems. Thanks to Nick Lewycky for reducing the test case for pr20303 (which I've cleaned up a little and added in DSE's test directory). The BasicAA test has also been updated to check for this error. Original commit message: BasicAA contains knowledge of certain intrinsics, such as memcpy and memset, and uses that information to form more-accurate answers to CallSite vs. Loc ModRef queries. Unfortunately, it did not use this information when answering CallSite vs. CallSite queries. Generically, when an intrinsic takes one or more pointers and the intrinsic is marked only to read/write from its arguments, the offset/size is unknown. As a result, the generic code that answers CallSite vs. CallSite (and CallSite vs. Loc) queries in AA uses UnknownSize when forming Locs from an intrinsic's arguments. While BasicAA's CallSite vs. Loc override could use more-accurate size information for some intrinsics, it did not do the same for CallSite vs. CallSite queries. This change refactors the intrinsic-specific logic in BasicAA into a generic AA query function: getArgLocation, which is overridden by BasicAA to supply the intrinsic-specific knowledge, and used by AA's generic implementation. This allows the intrinsic-specific knowledge to be used by both CallSite vs. Loc and CallSite vs. CallSite queries, and simplifies the BasicAA implementation. Currently, only one function, Mac's memset_pattern16, is handled by BasicAA (all the rest are intrinsics). As a side-effect of this refactoring, BasicAA's getModRefBehavior override now also returns OnlyAccessesArgumentPointees for this function (which is an improvement). llvm-svn: 213219
* Teach computeKnownBits to look through addrspacecast.Matt Arsenault2014-07-151-0/+2
| | | | | | This fixes inferring alignment through an addrspacecast. llvm-svn: 213030
* Teach GetUnderlyingObject / BasicAA about addrspacecastMatt Arsenault2014-07-152-2/+4
| | | | llvm-svn: 213025
* Revert r212572 "improve BasicAA CS-CS queries", it causes PR20303.Nick Lewycky2014-07-153-142/+126
| | | | llvm-svn: 213024
* Look through addrspacecast in IsConstantOffsetFromGlobalMatt Arsenault2014-07-141-1/+2
| | | | llvm-svn: 213000
* Look through addrspacecast in GetPointerBaseWithConstantOffsetMatt Arsenault2014-07-141-1/+2
| | | | llvm-svn: 212999
OpenPOWER on IntegriCloud