summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/BasicAliasAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* revert r317812 [BasicAA] fix build break by converting the previously ↵Nuno Lopes2017-11-091-2/+1
| | | | | | | | | introduced assert into an if stmt The code has a bug, but some tests regress. I'll discuss this further on the mailing list. llvm-svn: 317815
* [BasicAA] fix build break by converting the previously introduced assert ↵Nuno Lopes2017-11-091-2/+2
| | | | | | | | into an if stmt Apparently V1Size == -1 doest imply V2Size == -1, which is a bit surprising to me. llvm-svn: 317812
* [BasicAA] add assertion for corner case in aliasGEP()Nuno Lopes2017-11-091-0/+1
| | | | llvm-svn: 317803
* BasicAA: fix bug where we would return partialalias instead of noaliasNuno Lopes2017-11-081-3/+3
| | | | | | | | | | | | | | | My fix is conservative and will make us return may-alias instead. The test case is: check(gep(x, 0), n, gep(x, n), -1) with n == sizeof(x) Here, the first value accesses the whole object, but the second access doesn't access anything. The semantics of -1 is read until the end of the object, which in this case means read nothing. No test case, since isn't trivial to exploit this one, but I've proved it correct. llvm-svn: 317680
* Allow inaccessiblememonly and inaccessiblemem_or_argmemonly to be overwriten ↵Yichao Yu2017-11-021-0/+4
| | | | | | | | | | | | | | | | | | | on call site with operand bundle Summary: Similar to argmemonly, readonly and readnone. Fix PR35128 Reviewers: andrew.w.kaylor, chandlerc, hfinkel Reviewed By: hfinkel Subscribers: hfinkel, llvm-commits Differential Revision: https://reviews.llvm.org/D39434 llvm-svn: 317201
* Fix PR33878: BasicAA incorrectly assumes different address spaces don't aliasNuno Lopes2017-09-061-5/+0
| | | | | | | | | Remove code that assumed that a nullptr of address space != 0 couldnt alias with a non-null pointer. This is incorrect, since nothing can be concluded about a null pointer in an address space != 0. This code was written before address spaces were introduced Differential Revision: https://reviews.llvm.org/D37518 llvm-svn: 312648
* [Analysis] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-08-111-7/+25
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 310766
* BasicAA: assert on another case where aliasGEP shouldn't get a PartialAlias ↵Nuno Lopes2017-08-081-1/+3
| | | | | | response llvm-svn: 310420
* BasicAA: aliasGEP shouldn't get a PartialAlias response hereNuno Lopes2017-08-081-1/+3
| | | | | | add an assert() to ensure that's the case (as I'm not convinced it won't happen) llvm-svn: 310373
* Whitespace.NAKAMURA Takumi2017-07-111-1/+1
| | | | llvm-svn: 307614
* Revert r307581, "Avoid doing conservative phi checks in ↵NAKAMURA Takumi2017-07-111-11/+7
| | | | | | | | aliasSameBasePointerGEPs() if no phis have been visited yet." It broke stage2 tests in selfhosting. llvm-svn: 307613
* Avoid doing conservative phi checks in aliasSameBasePointerGEPs() if no phis ↵Farhana Aleen2017-07-101-7/+11
| | | | | | | | | | | | have been visited yet. Reviewers: Daniel Berlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34478 llvm-svn: 307581
* [BasicAA] Add type check and Value equality check around code added in r305481.Craig Topper2017-06-221-5/+8
| | | | | | | | This matches the checks done at the beginning of isKnownNonEqual that this code is partially emulating. Without this we can get assertion failures due to the bit widths of the KnownBits not matching. llvm-svn: 306044
* [BasicAA] Use MayAlias instead of PartialAlias for fallback.Michael Kruse2017-06-211-5/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Using various methods, BasicAA tries to determine whether two GetElementPtr memory locations alias when its base pointers are known to be equal. When none of its heuristics are applicable, it falls back to PartialAlias to, according to a comment, protect TBAA making a wrong decision in case of unions and malloc. PartialAlias is not correct, because a PartialAlias result implies that some, but not all, bytes overlap which is not necessarily the case here. AAResults returns the first analysis result that is not MayAlias. BasicAA is always the first alias analysis. When it returns PartialAlias, no other analysis is queried to give a more exact result (which was the intention of returning PartialAlias instead of MayAlias). For instance, ScopedAA could return a more accurate result. The PartialAlias hack was introduced in r131781 (and re-applied in r132632 after some reverts) to fix llvm.org/PR9971 where TBAA returns a wrong NoAlias result due to a union. A test case for the malloc case mentioned in the comment was not provided and I don't think it is affected since it returns an omnipotent char anyway. Since r303851 (https://reviews.llvm.org/D33328) clang does emit specific TBAA for unions anymore (but "omnipotent char" instead). Hence, the PartialAlias workaround is not required anymore. This patch passes the test-suite and check-llvm/check-clang of a self-hoisted build on x64. Reviewed By: hfinkel Differential Revision: https://reviews.llvm.org/D34318 llvm-svn: 305938
* [BasicAA] Don't call isKnownNonEqual if we might be have gone through a PHINode.Craig Topper2017-06-151-4/+18
| | | | | | | | | | | | This is a fix for the test case in PR32314. Basic Alias Analysis can ask if two nodes are known non-equal after looking through a phi node to find a GEP. isAddOfNonZero saw an add of a constant from the same phi and said that its output couldn't be equal. But Basic Alias Analysis was really asking about the value from the previous loop iteration. This patch at least makes that case not happen anymore, I'm not sure if there were still other ways this can fail. As was discussed in the bug, it looks like fixing BasicAA would be difficult so this patch seemed like a possible workaround Differential Revision: https://reviews.llvm.org/D33136 llvm-svn: 305481
* BasicAA: Uninserted instructions have no parent, and notDifferentParent ↵Daniel Berlin2017-05-191-1/+4
| | | | | | explicitly allows for this case, but getParent crashes when handed one. llvm-svn: 303442
* [ValueTracking] Replace all uses of ComputeSignBit with computeKnownBits.Craig Topper2017-05-151-2/+4
| | | | | | | | This patch finishes off the conversion of ComputeSignBit to computeKnownBits. Differential Revision: https://reviews.llvm.org/D33166 llvm-svn: 303035
* [BasicAA] Alphabetize includes. NFCCraig Topper2017-05-141-1/+1
| | | | llvm-svn: 303002
* [ValueTracking] Remove const_casts on several calls to computeKnownBits and ↵Craig Topper2017-05-131-2/+1
| | | | | | ComputeSignBit. NFC llvm-svn: 302991
* Handle invariant.group.barrier in BasicAAPiotr Padlewski2017-04-241-6/+6
| | | | | | | | | | | | | | | | | | | | | Summary: llvm.invariant.group.barrier returns pointer that mustalias pointer it takes. It can't be marked with `returned` attribute, because it would be remove easily. The other reason is that only Alias Analysis can know about this, because if any other pass would know it, then the result would be replaced with it's argument, which would be invalid. We can think about returned pointer as something that mustalias, but it doesn't have to be bitwise the same as the argument. Reviewers: dberlin, chandlerc, hfinkel, sanjoy Subscribers: reames, nlewycky, rsmith, anna, amharc Differential Revision: https://reviews.llvm.org/D31585 llvm-svn: 301227
* Add a getPointerOperandType() helper to LoadInst and StoreInst; NFCSanjoy Das2017-04-181-6/+4
| | | | | | I will use this in a later change. llvm-svn: 300613
* [MemoryBuiltins] Add isMallocOrCallocLikeFn so BasicAA can check for both at ↵Craig Topper2017-04-181-1/+1
| | | | | | | | | | | | | | the same time BasicAA wants to know if a function is either a malloc or calloc like function. Currently we have to check both separately. This means both calls check if its an intrinsic, query TLI, check the nobuiltin attribute, scan the AllocationFnData, etc. This patch adds a isMallocOrCallocLikeFn so we can go through all of the checks once per call. This also changes the one other location I saw that called both together. Differential Revision: https://reviews.llvm.org/D32188 llvm-svn: 300608
* [IR] Make paramHasAttr to use arg indices instead of attr indicesReid Kleckner2017-04-141-3/+3
| | | | | | | | | This avoids the confusing 'CS.paramHasAttr(ArgNo + 1, Foo)' pattern. Previously we were testing return value attributes with index 0, so I introduced hasReturnAttr() for that use case. llvm-svn: 300367
* Let llvm.objectsize be conservative with null pointersGeorge Burgess IV2017-03-211-1/+3
| | | | | | | | | | | This adds a parameter to @llvm.objectsize that makes it return conservative values if it's given null. This fixes PR23277. Differential Revision: https://reviews.llvm.org/D28494 llvm-svn: 298430
* [BasicAA] Take attributes into account when requesting modref info for a ↵Igor Laevsky2017-03-011-9/+31
| | | | | | | | call site Differential Revision: https://reviews.llvm.org/D29989 llvm-svn: 296617
* Fix BasicAA incorrect assumption on GEPMehdi Amini2017-01-271-5/+5
| | | | | | | | | | | | | | This is fixing pr31761: BasicAA is deducing NoAlias on the result of the GEP if the base pointer is itself NoAlias. This is possible only if the NoAlias on the base pointer is deduced with a non-sized query: this should guarantee that the pointers are belonging to different memory allocation and that the GEP can't legally jump from one to another. Differential Revision: https://reviews.llvm.org/D29216 llvm-svn: 293293
* [Analysis] Add LibFunc_ prefix to enums in TargetLibraryInfo. (NFC)David L. Jones2017-01-231-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The LibFunc::Func enum holds enumerators named for libc functions. Unfortunately, there are real situations, including libc implementations, where function names are actually macros (musl uses "#define fopen64 fopen", for example; any other transitively visible macro would have similar effects). Strictly speaking, a conforming C++ Standard Library should provide any such macros as functions instead (via <cstdio>). However, there are some "library" functions which are not part of the standard, and thus not subject to this rule (fopen64, for example). So, in order to be both portable and consistent, the enum should not use the bare function names. The old enum naming used a namespace LibFunc and an enum Func, with bare enumerators. This patch changes LibFunc to be an enum with enumerators prefixed with "LibFFunc_". (Unfortunately, a scoped enum is not sufficient to override macros.) There are additional changes required in clang. Reviewers: rsmith Subscribers: mehdi_amini, mzolotukhin, nemanjai, llvm-commits Differential Revision: https://reviews.llvm.org/D28476 llvm-svn: 292848
* [PM] Remove a pointless optimization.Chandler Carruth2016-12-271-3/+0
| | | | | | | | There is no need to do this within an analysis. That method shouldn't even be reached if this predicate holds as the actual useful optimization is in the analysis manager itself. llvm-svn: 290614
* [PM] Teach BasicAA how to invalidate its result object.Chandler Carruth2016-12-271-0/+18
| | | | | | | | | | | | | | | This requires custom handling because BasicAA caches handles to other analyses and so it needs to trigger indirect invalidation. This fixes one of the common crashes when using the new PM in real pipelines. I've also tweaked a regression test to check that we are at least handling the most immediate case. I'm going to work at re-structuring this test some to both scale better (rather than all being in one file) and check more invalidation paths in a follow-up commit, but I wanted to get the basic bug fix in place. llvm-svn: 290603
* [AliasAnalysis] Teach BasicAA about memcpy.Bryant Wong2016-12-251-0/+25
| | | | | | Differential Revision: https://reviews.llvm.org/D27034 llvm-svn: 290526
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-21/+28
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Fix argument attribute queries with bundle operandsHal Finkel2016-12-151-1/+2
| | | | | | | When iterating over data operands in AA, don't make argument-attribute-specific queries on bundle operands. Trying to fix self hosting... llvm-svn: 289765
* Remove the AssumptionCacheHal Finkel2016-12-151-28/+21
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* IR: Change the gep_type_iterator API to avoid always exposing the "current" ↵Peter Collingbourne2016-12-021-4/+4
| | | | | | | | | | | | | type. Instead, expose whether the current type is an array or a struct, if an array what the upper bound is, and if a struct the struct type itself. This is in preparation for a later change which will make PointerType derive from Type rather than SequentialType. Differential Revision: https://reviews.llvm.org/D26594 llvm-svn: 288458
* [PM] Change the static object whose address is used to uniquely identifyChandler Carruth2016-11-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
* Fix comment typos. NFC.Simon Pilgrim2016-11-201-1/+1
| | | | | | Identified by Pedro Giffuni in PR27636. llvm-svn: 287490
* [BasicAA] Teach BasicAA to handle the inaccessiblememonly and ↵Andrew Kaylor2016-11-081-0/+4
| | | | | | | | inaccessiblemem_or_argmemonly attributes Differential Revision: https://reviews.llvm.org/D26382 llvm-svn: 286294
* [BasicAA] Fix - missed alias in GEP expressionsGerolf Hoflehner2016-10-221-5/+11
| | | | | | | | | | | | In BasicAA GEP operand values get adjusted ("wrap-around") based on the pointersize. Otherwise, in non-64b modes, AA could report false negatives. However, a wrap-around is valid only for a fully evaluated expression. It had been introduced to fix an alias problem in http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160118/326163.html. This commit restricts the wrap-around to constant gep operands only where the value is known at compile-time. llvm-svn: 284908
* Replace a few more "fall through" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-1/+1
| | | | | | Follow up to r278902. I had missed "fall through", with a space. llvm-svn: 278970
* [BasicAA] Avoid calling GetUnderlyingObject, when the result of a previous ↵Ehsan Amiri2016-08-121-13/+25
| | | | | | | | | | call can be reused. Recursive calls to aliasCheck from alias[GEP|Select|PHI] may result in a second call to GetUnderlyingObject for a Value, whose underlying object is already computed. This patch ensures that in this situations, the underlying object is not computed again, and the result of the previous call is resued. https://reviews.llvm.org/D22305 llvm-svn: 278519
* [AliasAnalysis] Treat invariant.start as read-memoryAnna Thomas2016-08-091-0/+26
| | | | | | | | | | | | | | | | | Summary: We teach alias analysis that invariant.start is readonly. This helps with GVN and memcopy optimizations that currently treat. invariant.start as a clobber. We need to treat this as readonly, so that DSE does not incorrectly remove stores prior to the invariant.start Reviewers: sanjoy, reames, majnemer, dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23214 llvm-svn: 278138
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
* BasicAA should look through functions with returned argumentsHal Finkel2016-07-111-2/+14
| | | | | | | | | | | Motivated by the work on the llvm.noalias intrinsic, teach BasicAA to look through returned-argument functions when answering queries. This is essential so that we don't loose all other AA information when supplementing with llvm.noalias. Differential Revision: http://reviews.llvm.org/D9383 llvm-svn: 275035
* Add writeonly IR attributeNicolai Haehnle2016-07-041-22/+11
| | | | | | | | | | | | | | | | | Summary: This complements the earlier addition of IntrWriteMem and IntrWriteArgMem LLVM intrinsic properties, see D18291. Also start using the attribute for memset, memcpy, and memmove intrinsics, and remove their special-casing in BasicAliasAnalysis. Reviewers: reames, joker.eph Subscribers: joker.eph, llvm-commits Differential Revision: http://reviews.llvm.org/D18714 llvm-svn: 274485
* Revert "Claim NoAlias if two GEPs index different fields of the same struct"Daniel Berlin2016-06-011-36/+2
| | | | | | This reverts commit 2d5d6493f43eb68493a3852b8c226ac9fafdc7eb. llvm-svn: 271422
* Claim NoAlias if two GEPs index different fields of the same structDaniel Berlin2016-06-011-2/+36
| | | | | | | | | | | | | | Patch by Taewook Oh Summary: Patch for Bug 27478. Make BasicAliasAnalysis claims NoAlias if two GEPs index different fields of the same structure. Reviewers: hfinkel, dberlin Subscribers: dberlin, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20665 llvm-svn: 271415
* [BasicAA] Extend inbound GEP negative offset logic to GlobalVariablesMichael Kuperstein2016-05-261-10/+18
| | | | | | | | | | | | | | r270777 improved the precision of alloca vs. inbounbds GEP alias queries: if we have (a) an inbounds GEP and (b) a pointer based on an alloca, and the beginning of the object the GEP points to would have a negative offset with respect to the alloca, then the GEP can not alias pointer (b). This makes the same logic fire when (b) is based on a GlobalVariable instead of an alloca. Differential Revision: http://reviews.llvm.org/D20652 llvm-svn: 270893
* MemorySSA: Revert r269678 and r268068; replace with special casing in MemorySSA.Peter Collingbourne2016-05-261-9/+0
| | | | | | | | | | | | | It turns out that too many passes are relying on alias analysis results for control dependencies. Until we fix that by introducing a more accurate modelling of control dependencies, special case assume in MemorySSA instead. Also introduce tests to ensure we don't regress the FunctionAttrs or LICM passes. Differential Revision: http://reviews.llvm.org/D20658 llvm-svn: 270823
* [BasicAA] Improve precision of alloca vs. inbounds GEP alias queriesMichael Kuperstein2016-05-251-82/+120
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If a we have (a) a GEP and (b) a pointer based on an alloca, and the beginning of the object the GEP points would have a negative offset with repsect to the alloca, then the GEP can not alias pointer (b). For example, consider code like: struct { int f0, int f1, ...} foo; ... foo alloca; foo *random = bar(alloca); int *f0 = &alloca.f0 int *f1 = &random->f1; Which is lowered, approximately, to: %alloca = alloca %struct.foo %random = call %struct.foo* @random(%struct.foo* %alloca) %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0 %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1 Assume %f1 and %f0 alias. Then %f1 would point into the object allocated by %alloca. Since the %f1 GEP is inbounds, that means %random must also point into the same object. But since %f0 points to the beginning of %alloca, the highest %f1 can be is (%alloca + 3). This means %random can not be higher than (%alloca - 1), and so is not inbounds, a contradiction. Differential Revision: http://reviews.llvm.org/D20495 llvm-svn: 270777
* Revert r270268 due to unused variable warnings.Michael Kuperstein2016-05-201-12/+17
| | | | llvm-svn: 270272
OpenPOWER on IntegriCloud