summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/BasicAliasAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* [BasicAA] Turn DecomposeGEPExpression runtime checks into asserts.Michael Kuperstein2016-05-201-17/+12
| | | | | | | | When it has a DataLayout, DecomposeGEPExpression() should return the same object as GetUnderlyingObject(). Per the FIXME, it currently always has a DL, so the runtime check is redundant and can become an assert. llvm-svn: 270268
* [BasicAA] Update comments based on feedback from hfinkel. NFCI.Geoff Berry2016-05-161-1/+4
| | | | | | | Original change Hal's comments were based on: http://reviews.llvm.org/D19730 llvm-svn: 269678
* [BasicAA] Compare GEP indices based on value (Fix PR27418)Vedant Kumar2016-05-111-1/+1
| | | | | | | | | | | | Equivalent GEP indices with different types are treated as different indices altogether, leading to an incorrect AA result. Fix the issue by comparing indices based on their values. Thanks to Mikael Holmén for reporting the issue! Differential Revision: http://reviews.llvm.org/D19935 llvm-svn: 269197
* [BasicAA] Guard intrinsics don't write to memorySanjoy Das2016-05-101-4/+32
| | | | | | | | | | | | | | | | Summary: The idea is very close to what we do for assume intrinsics: we mark the guard intrinsics as writing to arbitrary memory to maintain control dependence, but under the covers we teach AA that they do not mod any particular memory location. Reviewers: chandlerc, hfinkel, gbiv, reames Subscribers: george.burgess.iv, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19575 llvm-svn: 269007
* [BasicAA] Treat llvm.assume as not accessing memory in ↵Geoff Berry2016-04-291-0/+6
| | | | | | | | | | | | getModRefBehavior(Function) Reviewers: dberlin, chandlerc, hfinkel, reames, sanjoy Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19730 llvm-svn: 268068
* [TLI] Unify LibFunc signature checking. NFCI.Ahmed Bougacha2016-04-271-17/+3
| | | | | | | | | I tried to be as close as possible to the strongest check that existed before; cleaning these up properly is left for future work. Differential Revision: http://reviews.llvm.org/D19469 llvm-svn: 267758
* Don't IPO over functions that can be de-refinedSanjoy Das2016-04-081-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Fixes PR26774. If you're aware of the issue, feel free to skip the "Motivation" section and jump directly to "This patch". Motivation: I define "refinement" as discarding behaviors from a program that the optimizer has license to discard. So transforming: ``` void f(unsigned x) { unsigned t = 5 / x; (void)t; } ``` to ``` void f(unsigned x) { } ``` is refinement, since the behavior went from "if x == 0 then undefined else nothing" to "nothing" (the optimizer has license to discard undefined behavior). Refinement is a fundamental aspect of many mid-level optimizations done by LLVM. For instance, transforming `x == (x + 1)` to `false` also involves refinement since the expression's value went from "if x is `undef` then { `true` or `false` } else { `false` }" to "`false`" (by definition, the optimizer has license to fold `undef` to any non-`undef` value). Unfortunately, refinement implies that the optimizer cannot assume that the implementation of a function it can see has all of the behavior an unoptimized or a differently optimized version of the same function can have. This is a problem for functions with comdat linkage, where a function can be replaced by an unoptimized or a differently optimized version of the same source level function. For instance, FunctionAttrs cannot assume a comdat function is actually `readnone` even if it does not have any loads or stores in it; since there may have been loads and stores in the "original function" that were refined out in the currently visible variant, and at the link step the linker may in fact choose an implementation with a load or a store. As an example, consider a function that does two atomic loads from the same memory location, and writes to memory only if the two values are not equal. The optimizer is allowed to refine this function by first CSE'ing the two loads, and the folding the comparision to always report that the two values are equal. Such a refined variant will look like it is `readonly`. However, the unoptimized version of the function can still write to memory (since the two loads //can// result in different values), and selecting the unoptimized version at link time will retroactively invalidate transforms we may have done under the assumption that the function does not write to memory. Note: this is not just a problem with atomics or with linking differently optimized object files. See PR26774 for more realistic examples that involved neither. This patch: This change introduces a new set of linkage types, predicated as `GlobalValue::mayBeDerefined` that returns true if the linkage type allows a function to be replaced by a differently optimized variant at link time. It then changes a set of IPO passes to bail out if they see such a function. Reviewers: chandlerc, hfinkel, dexonsmith, joker.eph, rnk Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D18634 llvm-svn: 265762
* [AA] Make BasicAA just require domtree.Chandler Carruth2016-03-111-4/+5
| | | | | | | | | | | | | This doesn't change how many times we construct domtrees in the normal pipeline, and it removes fragility and instability where basic-aa may not be run in time to see domtrees because they happen to be constructed afterward. This isn't quite as clean as the change to memdep because there is a mode where basic-aa specifically runs without domtrees -- in the hacking version used by function-attrs with the legacy pass manager. llvm-svn: 263234
* [PM] Make the AnalysisManager parameter to run methods a reference.Chandler Carruth2016-03-111-5/+5
| | | | | | | | | | | | This was originally a pointer to support pass managers which didn't use AnalysisManagers. However, that doesn't realistically come up much and the complexity of supporting it doesn't really make sense. In fact, *many* parts of the pass manager were just assuming the pointer was never null already. This at least makes it much more explicit and clear. llvm-svn: 263219
* [PM] Implement the final conclusion as to how the analysis IDs shouldChandler Carruth2016-03-111-0/+2
| | | | | | | | | | | | | | | | | | | | work in the face of the limitations of DLLs and templated static variables. This requires passes that use the AnalysisBase mixin provide a static variable themselves. So as to keep their APIs clean, I've made these private and befriended the CRTP base class (which is the common practice). I've added documentation to AnalysisBase for why this is necessary and at what point we can go back to the much simpler system. This is clearly a better pattern than the extern template as it caught *numerous* places where the template magic hadn't been applied and things were "just working" but would eventually have broken mysteriously. llvm-svn: 263216
* [BasicAA/MDA] Sink aliasing rules for malloc and calloc into BasicAAPhilip Reames2016-03-091-0/+14
| | | | | | | | | | MemoryDependenceAnalysis had a hard-coded exception to the general aliasing rules for malloc and calloc. The reasoning that applied there is equally valid in BasicAA and clarifies the remaining logic in MDA. In principal, this can expose slightly more optimization opportunities, but since essentially all of our aliasing aware memory optimization passes go through MDA, this will likely be NFC in practice. Differential Revision: http://reviews.llvm.org/D15912 llvm-svn: 263075
* [AA] Hoist the logic to reformulate various AA queries in terms of otherChandler Carruth2016-03-021-4/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | parts of the AA interface out of the base class of every single AA result object. Because this logic reformulates the query in terms of some other aspect of the API, it would easily cause O(n^2) query patterns in alias analysis. These could in turn be magnified further based on the number of call arguments, and then further based on the number of AA queries made for a particular call. This ended up causing problems for Rust that were actually noticable enough to get a bug (PR26564) and probably other places as well. When originally re-working the AA infrastructure, the desire was to regularize the pattern of refinement without losing any generality. While I think it was successful, that is clearly proving to be too costly. And the cost is needless: we gain no actual improvement for this generality of making a direct query to tbaa actually be able to re-use some other alias analysis's refinement logic for one of the other APIs, or some such. In short, this is entirely wasted work. To the extent possible, delegation to other API surfaces should be done at the aggregation layer so that we can avoid re-walking the aggregation. In fact, this significantly simplifies the logic as we no longer need to smuggle the aggregation layer into each alias analysis (or the TargetLibraryInfo into each alias analysis just so we can form argument memory locations!). However, we also have some delegation logic inside of BasicAA and some of it even makes sense. When the delegation logic is baking in specific knowledge of aliasing properties of the LLVM IR, as opposed to simply reformulating the query to utilize a different alias analysis interface entry point, it makes a lot of sense to restrict that logic to a different layer such as BasicAA. So one aspect of the delegation that was in every AA base class is that when we don't have operand bundles, we re-use function AA results as a fallback for callsite alias results. This relies on the IR properties of calls and functions w.r.t. aliasing, and so seems a better fit to BasicAA. I've lifted the logic up to that point where it seems to be a natural fit. This still does a bit of redundant work (we query function attributes twice, once via the callsite and once via the function AA query) but it is *exactly* twice here, no more. The end result is that all of the delegation logic is hoisted out of the base class and into either the aggregation layer when it is a pure retargeting to a different API surface, or into BasicAA when it relies on the IR's aliasing properties. This should fix the quadratic query pattern reported in PR26564, although I don't have a stand-alone test case to reproduce it. It also seems general goodness. Now the numerous AAs that don't need target library info don't carry it around and depend on it. I think I can even rip out the general access to the aggregation layer and only expose that in BasicAA as it is the only place where we re-query in that manner. However, this is a non-trivial change to the AA infrastructure so I want to get some additional eyes on this before it lands. Sadly, it can't wait long because we should really cherry pick this into 3.8 if we're going to go this route. Differential Revision: http://reviews.llvm.org/D17329 llvm-svn: 262490
* [PM] Introduce CRTP mixin base classes to help define passes andChandler Carruth2016-02-261-2/+0
| | | | | | | | | | | | | | | | | analyses in the new pass manager. These just handle really basic stuff: turning a type name into a string statically that is nice to print in logs, and getting a static unique ID for each analysis. Sadly, the format of passes in anonymous namespaces makes using their names in tests really annoying so I've customized the names of the no-op passes to keep tests sane to read. This is the first of a few simplifying refactorings for the new pass manager that should reduce boilerplate and confusion. llvm-svn: 262004
* Remove uses of builtin comma operator.Richard Trieu2016-02-181-1/+2
| | | | | | Cleanup for upcoming Clang warning -Wcomma. No functionality change intended. llvm-svn: 261270
* [BasicAA] NFC - revised comment for function adjustToPointerSize()Gerolf Hoflehner2016-01-301-1/+1
| | | | llvm-svn: 259300
* [BasicAA] Fix for missing must alias (D16343)Gerolf Hoflehner2016-01-301-0/+3
| | | | llvm-svn: 259299
* [BasicAA] Update on r259290 - added missing castGerolf Hoflehner2016-01-301-1/+1
| | | | llvm-svn: 259298
* [BasicAA] NFC - utility function for two's complement wrap-aroundGerolf Hoflehner2016-01-301-7/+15
| | | | llvm-svn: 259290
* [opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with ↵Eduard Burtescu2016-01-191-1/+1
| | | | | | | | | | | | | | | | | | get{Source,Result}ElementType. Summary: GEPOperator: provide getResultElementType alongside getSourceElementType. This is made possible by adding a result element type field to GetElementPtrConstantExpr, which GetElementPtrInst already has. GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16275 llvm-svn: 258145
* fix typos; NFCSanjay Patel2016-01-171-17/+16
| | | | llvm-svn: 258026
* [BasicAliasAnalysis] Take into account operand bundles in the getModRefInfo ↵Igor Laevsky2016-01-161-4/+4
| | | | | | | | function Differential Revision: http://reviews.llvm.org/D16225 llvm-svn: 257991
* [BasicAA] Extract WriteOnly predicate on parameters [NFC]Philip Reames2016-01-061-5/+25
| | | | | | Since writeonly is the only missing attribute and special case left for the memset/memcpy family of intrinsics, rearrange the code to make that much more clear. llvm-svn: 256949
* [BasicAA] Remove special casing of memset_pattern16 in favor of generic ↵Philip Reames2016-01-061-12/+5
| | | | | | | | | | | | attribute inference Most of the properties of memset_pattern16 can be now covered by the generic attributes and inferred by InferFunctionAttrs. The only exceptions are: - We don't yet have a writeonly attribute for the first argument. - We don't have an attribute for modeling the access size facts encoded in MemoryLocation.cpp. Differential Revision: http://reviews.llvm.org/D15879 llvm-svn: 256911
* [BasicAA] Delete dead code related to memset/memcpy/memmove intrinsics [NFCI]Philip Reames2016-01-061-3/+5
| | | | | | | | We only need to describe the writeonly property of one of the arguments. All of the rest of the semantics are nicely described by existing attributes in Intrinsics.td. Differential Revision: http://reviews.llvm.org/D15880 llvm-svn: 256910
* Fix a typo in BasicAliasAnalysisDavid Majnemer2015-11-171-1/+1
| | | | llvm-svn: 253322
* Refactor: Simplify boolean conditional return statements in llvm/lib/AnalysisAlexander Kornienko2015-11-051-4/+1
| | | | | | | | Patch by Richard Thomson! Differential revision: http://reviews.llvm.org/D9967 llvm-svn: 252209
* [AliasAnalysis] Take into account readnone attribute for the function argumentsIgor Laevsky2015-10-281-0/+3
| | | | | | Differential Revision: http://reviews.llvm.org/D13992 llvm-svn: 251535
* [AliasAnalysis] Take into account readonly attribute for the function argumentsIgor Laevsky2015-10-281-0/+3
| | | | | | | | | | In getArgModRefInfo we consider all arguments as having MRI_ModRef. However for arguments marked with readonly attribute we can return more precise answer - MRI_Ref. Differential Revision: http://reviews.llvm.org/D13992 llvm-svn: 251525
* Initialize BasicAAWrapperPass in it's constructorKeno Fischer2015-10-261-0/+4
| | | | | | | | | | | | Summary: This idiom is used elsewhere in LLVM, but was overlooked here. Reviewers: chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13628 llvm-svn: 251348
* [BasicAliasAnalysis] Simplify expression, no functional change.Benjamin Kramer2015-10-241-3/+2
| | | | | | (-1) - x + 1 is the same as -x. llvm-svn: 251185
* [BasicAA] Bugfix for r251016James Molloy2015-10-231-2/+8
| | | | | | | | If the loaded type sizes don't match the element type of the sequential type, all bets are off and the addresses may, indeed, overlap. Surprisingly, this just got caught in one test, on one builder, out of the 30+ builders testing this change. Congratulations go to http://lab.llvm.org:8011/builders/clang-aarch64-lnt/builds/5205. llvm-svn: 251112
* [BasicAA] Non-equal indices in a GEP of a SequentialType don't overlapJames Molloy2015-10-221-8/+38
| | | | | | | | If the final indices of two GEPs can be proven to not be equal, and the GEP is of a SequentialType (not a StructType), then the two GEPs do not alias. llvm-svn: 251016
OpenPOWER on IntegriCloud