summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/AliasAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [MSSA] Print more optimization informationGeorge Burgess IV2018-06-141-0/+18
| | | | | | | | | | | | | | In particular, when asked to print a MemoryAccess, we'll now print where defs are optimized to, and we'll print optimized access types. This patch also introduces an operator<< to make printing AliasResults easier. Patch by Juneyoung Lee! Differential Revision: https://reviews.llvm.org/D47860 llvm-svn: 334760
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-1/+1
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* [ModRefInfo] Rename local variable IsMustAlias to avoid shadowing MustAlias ↵Alina Sbirlea2018-04-301-3/+3
| | | | | | enum entry. llvm-svn: 331222
* [ModRefInfo] Return NoModRef for Must and NoModRef.Alina Sbirlea2018-01-191-71/+77
| | | | | | | | | | | | | | Summary: In ModRefInfo "Must" was introduced to track presence of MustAlias, but we still want to return NoModRef when there is neither Mod or Ref, even when MustAlias is found. Patch has small fixes to ensure this happens. Minor cleanup to remove nesting for 2 if statements when calling getModRefInfo for 2 ImmutableCallSites. Reviewers: sanjoy Subscribers: jlebar, llvm-commits Differential Revision: https://reviews.llvm.org/D42209 llvm-svn: 322932
* [ModRefInfo] Add must alias info to ModRefInfo.Alina Sbirlea2017-12-211-17/+78
| | | | | | | | | | | | | | | | | | | | | | Summary: Add an additional bit to ModRefInfo, ModRefInfo::Must, to be cleared for known must aliases. Shift existing Mod/Ref/ModRef values to include an additional most significant bit. Update wrappers that modify ModRefInfo values to reflect the change. Notes: * ModRefInfo::Must is almost entirely cleared in the AAResults methods, the remaining changes are trying to preserve it. * Only some small changes to make custom AA passes set ModRefInfo::Must (BasicAA). * GlobalsModRef already declares a bit, who's meaning overlaps with the most significant bit in ModRefInfo (MayReadAnyGlobal). No changes to shift the value of MayReadAnyGlobal (see AlignedMap). FunctionInfo.getModRef() ajusts most significant bit so correctness is preserved, but the Must info is lost. * There are cases where the ModRefInfo::Must is not set, e.g. 2 calls that only read will return ModRefInfo::NoModRef, though they may read from exactly the same location. Reviewers: dberlin, hfinkel, george.burgess.iv Subscribers: llvm-commits, sanjoy Differential Revision: https://reviews.llvm.org/D38862 llvm-svn: 321309
* [ModRefInfo] Make enum ModRefInfo an enum class [NFC].Alina Sbirlea2017-12-071-48/+48
| | | | | | | | | | | | | | | Summary: Make enum ModRefInfo an enum class. Changes to ModRefInfo values should be done using inline wrappers. This should prevent future bit-wise opearations from being added, which can be more error-prone. Reviewers: sanjoy, dberlin, hfinkel, george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40933 llvm-svn: 320107
* [ModRefInfo] Do not use ModRefInfo result in if conditions as this makesAlina Sbirlea2017-12-061-1/+1
| | | | | | | assumptions about the values in the enum. Replace with wrapper returning bool [NFC]. llvm-svn: 319949
* [ModRefInfo] Initialize ArgMask to MRI_NoModRef.Alina Sbirlea2017-12-051-1/+1
| | | | llvm-svn: 319831
* Modify ModRefInfo values using static inline method abstractions [NFC].Alina Sbirlea2017-12-051-36/+42
| | | | | | | | | | | | | | | | | Summary: The aim is to make ModRefInfo checks and changes more intuitive and less error prone using inline methods that abstract the bit operations. Ideally ModRefInfo would become an enum class, but that change will require a wider set of changes into FunctionModRefBehavior. Reviewers: sanjoy, george.burgess.iv, dberlin, hfinkel Subscribers: nlopes, llvm-commits Differential Revision: https://reviews.llvm.org/D40749 llvm-svn: 319821
* [Analysis] Fix some Clang-tidy modernize-use-using and Include What You Use ↵Eugene Zelenko2017-08-111-15/+27
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 310766
* [IR] Make paramHasAttr to use arg indices instead of attr indicesReid Kleckner2017-04-141-1/+1
| | | | | | | | | 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
* AliasAnalysis: Be less conservative about volatile than atomic.Daniel Berlin2017-04-071-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: getModRefInfo is meant to answer the question "what impact does this instruction have on a given memory location" (not even another instruction). Long debate on this on IRC comes to the conclusion the answer should be "nothing special". That is, a noalias volatile store does not affect a memory location just by being volatile. Note: DSE and GVN and memdep currently believe this, because memdep just goes behind AA's back after it says "modref" right now. see line 635 of memdep. Prior to this patch we would get modref there, then check aliasing, and if it said noalias, we would continue. getModRefInfo *already* has this same AA check, it just wasn't being used because volatile was lumped in with ordering. (I am separately testing whether this code in memdep is now dead except for the invariant load case) Reviewers: jyknight, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D31726 llvm-svn: 299741
* [AliasAnalysis] Fences do not modify constant memory locationAnna Thomas2017-01-201-0/+8
| | | | | | | | | | | | | | | | | | | Summary: Fence instructions are currently marked as `ModRef` for all memory locations. We can improve this for constant memory locations (such as constant globals), since fence instructions cannot modify these locations. This helps us to forward constant loads across fences (added test case in GVN). There were no changes in behaviour for similar test cases in early-cse and licm. Reviewers: dberlin, sanjoy, reames Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28914 llvm-svn: 292546
* [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 the AAManager and AAResults layer (the worst offender forChandler Carruth2016-12-271-1/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | inter-analysis dependencies) to use the new invalidation infrastructure. This teaches it to invalidate itself when any of the peer function AA results that it uses become invalid. We do this by just tracking the originating IDs. I've kept it in a somewhat clunky API since some users of AAResults are outside the new PM right now. We can clean this API up if/when those users go away. Secondly, it uses the registration on the outer analysis manager proxy to trigger deferred invalidation when a module analysis result becomes invalid. I've included test cases that specifically try to trigger use-after-free in both of these cases and they would crash or hang pretty horribly for me even without ASan. Now they work nicely. The `InvalidateAnalysis` utility pass required some tweaking to be useful in this context and it still is pretty garbage. I'd like to switch it back to the previous implementation and teach the explicit invalidate method on the AnalysisManager to take care of correctly triggering indirect invalidation, but I wanted to go ahead and send this out so folks could see how all of this stuff works together in practice. And, you know, that it does actually work. =] Differential Revision: https://reviews.llvm.org/D27205 llvm-svn: 290595
* Revert part of r289765 that is not necessaryHal Finkel2016-12-151-2/+2
| | | | | | | | CS.doesNotAccessMemory(ArgNo) and CS.onlyReadsMemory(ArgNo) calls dataOperandHasImpliedAttr, so revert this part of r289765 because it should not be necessary. llvm-svn: 289768
* Fix argument attribute queries with bundle operandsHal Finkel2016-12-151-3/+4
| | | | | | | 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
* [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
* [BasicAA] Teach BasicAA to handle the inaccessiblememonly and ↵Andrew Kaylor2016-11-081-2/+3
| | | | | | | | inaccessiblemem_or_argmemonly attributes Differential Revision: https://reviews.llvm.org/D26382 llvm-svn: 286294
* [AliasAnalysis] Give back AA results for fence instructionsDavid Majnemer2016-07-151-0/+3
| | | | | | | | | | | | | Calling getModRefInfo with a fence resulted in crashes because fences don't have a memory location. Add a new predicate to Instruction called isFenceLike which indicates that the instruction mutates memory but not any single memory location in particular. In practice, it is a proxy for the set of instructions which "mayWriteToMemory" but cannot be used with MemoryLocation::get. This fixes PR28570. llvm-svn: 275581
* AliasAnalysis: unify getModRefInfo(I, CS) semantics with other overloadsNicolai Haehnle2016-07-111-1/+1
| | | | | | | | | | | | | | | | | | | This subtle change to getModRefInfo(Instruction, ImmutableCallSite) is to ensure that the semantics are equal to that of getModRefInfo(CS1, CS2) when the Instruction is a call-site. This is now more in line with getModRefInfo generally: it returns Mod when I modifies a memory location that is accessed (read or written) by CS and Ref when I reads a memory location that is written by CS. From a grep of the code, the only uses of this particular getModRefInfo overload are in MemorySSA and MemCpyOptimizer, and they only care about where the result is MR_NoModRef or not. Therefore, this change should have no visible effect. Separated out from D17279 upon request. llvm-svn: 275065
* [CFLAA] Split into Anders+Steens analysis.George Burgess IV2016-07-061-6/+14
| | | | | | | | | | | | | | | | | | | | | StratifiedSets (as implemented) is very fast, but its accuracy is also limited. If we take a more aggressive andersens-like approach, we can be way more accurate, but we'll also end up being slower. So, we've decided to split CFLAA into CFLSteensAA and CFLAndersAA. Long-term, we want to end up in a place where CFLSteens is queried first; if it can provide an answer, great (since queries are basically map lookups). Otherwise, we'll fall back to CFLAnders, BasicAA, etc. This patch splits everything out so we can try to do something like that when we get a reasonable CFLAnders implementation. Patch by Jia Chen. Differential Revision: http://reviews.llvm.org/D21910 llvm-svn: 274589
* Add writeonly IR attributeNicolai Haehnle2016-07-041-0/+4
| | | | | | | | | | | | | | | | | 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
* Fix AAResults::callCapturesBefore for operand bundlesSanjoy Das2016-06-131-1/+1
| | | | | | | | | | | | | | | | Summary: AAResults::callCapturesBefore would previously ignore operand bundles. It was possible for a later instruction to miss its memory dependency on a call site that would only access the pointer through a bundle. Patch by Oscar Blumberg! Reviewers: sanjoy Differential Revision: http://reviews.llvm.org/D21286 llvm-svn: 272580
* NFC: make AtomicOrdering an enum classJF Bastien2016-04-061-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: In the context of http://wg21.link/lwg2445 C++ uses the concept of 'stronger' ordering but doesn't define it properly. This should be fixed in C++17 barring a small question that's still open. The code currently plays fast and loose with the AtomicOrdering enum. Using an enum class is one step towards tightening things. I later also want to tighten related enums, such as clang's AtomicOrderingKind (which should be shared with LLVM as a 'C++ ABI' enum). This change touches a few lines of code which can be improved later, I'd like to keep it as NFC for now as it's already quite complex. I have related changes for clang. As a follow-up I'll add: bool operator<(AtomicOrdering, AtomicOrdering) = delete; bool operator>(AtomicOrdering, AtomicOrdering) = delete; bool operator<=(AtomicOrdering, AtomicOrdering) = delete; bool operator>=(AtomicOrdering, AtomicOrdering) = delete; This is separate so that clang and LLVM changes don't need to be in sync. Reviewers: jyknight, reames Subscribers: jyknight, llvm-commits Differential Revision: http://reviews.llvm.org/D18775 llvm-svn: 265602
* [PM] Implement the final conclusion as to how the analysis IDs shouldChandler Carruth2016-03-111-1/+1
| | | | | | | | | | | | | | | | | | | | 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
* [AA] Hoist the logic to reformulate various AA queries in terms of otherChandler Carruth2016-03-021-11/+127
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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] Appease mingw32's auto-import DLL build with minimal tweaks, with fix ↵NAKAMURA Takumi2016-02-281-0/+3
| | | | | | | | for clang. char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262188
* Revert r262185, "[PM] Appease mingw32's auto-import DLL build with minimal ↵NAKAMURA Takumi2016-02-281-3/+0
| | | | | | | | tweaks." I'll rework soon. llvm-svn: 262186
* [PM] Appease mingw32's auto-import DLL build with minimal tweaks.NAKAMURA Takumi2016-02-281-0/+3
| | | | | | char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262185
* [PM] Introduce CRTP mixin base classes to help define passes andChandler Carruth2016-02-261-3/+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
* [PM/AA] Actually wire the AAManager I built for the new pass managerChandler Carruth2016-02-131-0/+3
| | | | | | | | | | | | into the new pass manager and fix the latent bugs there. This lets everything live together nicely, but it isn't really useful yet. I never finished wiring the AA layer up for the new pass manager, and so subsequent patches will change this to do that wiring and get AA stuff more fully integrated into the new pass manager. Turns out this is necessary even to get functionattrs ported over. =] llvm-svn: 260836
* Add an "addUsedAAAnalyses" helper functionSanjoy Das2016-02-091-0/+11
| | | | | | | | | | | | | | | | | | | Summary: Passes that call `getAnalysisIfAvailable<T>` also need to call `addUsedIfAvailable<T>` in `getAnalysisUsage` to indicate to the legacy pass manager that it uses `T`. This contract was being violated by passes that used `createLegacyPMAAResults`. This change fixes this by exposing a helper in AliasAnalysis.h, `addUsedAAAnalyses`, that is complementary to createLegacyPMAAResults and does the right thing when called from `getAnalysisUsage`. Reviewers: chandlerc Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D17010 llvm-svn: 260183
* Remove SCEVAAWrapperPass from createLegacyPMAAResults; NFCSanjoy Das2016-02-091-2/+0
| | | | | | | | | | | | | | | Summary: createLegacyPMAAResults is only called by CGSCC and Module passes, so the call to getAnalysisIfAvailable<SCEVAAWrapperPass>() never succeeds (SCEVAAWrapperPass is a function pass). Reviewers: chandlerc Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D17009 llvm-svn: 260182
* fix formatting; NFCSanjay Patel2016-01-131-4/+2
| | | | llvm-svn: 257688
* don't duplicate comments that are in the header file; NFCSanjay Patel2016-01-131-16/+0
| | | | llvm-svn: 257676
* [AliasAnalysis] CatchPad and CatchRet can modify escaped memoryDavid Majnemer2015-11-171-0/+26
| | | | | | | CatchPad and CatchRet behave a lot like function calls: they can potentially modify any memory which has been escaped. llvm-svn: 253323
* [AA] Enhance the new AliasAnalysis infrastructure with an optionalChandler Carruth2015-10-211-0/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | "external" AA wrapper pass. This is a generic hook that can be used to thread custom code into the primary AAResultsWrapperPass for the legacy pass manager in order to allow it to merge external AA results into the AA results it is building. It does this by threading in a raw callback and so it is *very* powerful and should serve almost any use case I have come up with for extending the set of alias analyses used. The only thing not well supported here is using a *different order* of alias analyses. That form of extension *is* supportable with the new pass manager, and I can make the callback structure here more elaborate to support it in the legacy pass manager if this is a critical use case that people are already depending on, but the only use cases I have heard of thus far should be reasonably satisfied by this simpler extension mechanism. It is hard to test this using normal facilities (the built-in AAs don't use this for obvious reasons) so I've written a fairly extensive set of custom passes in the alias analysis unit test that should be an excellent test case because it models the out-of-tree users: it adds a totally custom AA to the system. This should also serve as a reasonably good example and guide for out-of-tree users to follow in order to rig up their existing alias analyses. No support in opt for commandline control is provided here however. I'm really unhappy with the kind of contortions that would be required to support that. It would fully re-introduce the analysis group self-recursion kind of patterns. =/ I've heard from out-of-tree users that this will unblock their use cases with extending AAs on top of the new infrastructure and let us retain the new analysis-group-free-world. Differential Revision: http://reviews.llvm.org/D13418 llvm-svn: 250894
* Analysis: Remove implicit ilist iterator conversionsDuncan P. N. Exon Smith2015-10-101-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Remove implicit ilist iterator conversions from LLVMAnalysis. I came across something really scary in `llvm::isKnownNotFullPoison()` which relied on `Instruction::getNextNode()` being completely broken (not surprising, but scary nevertheless). This function is documented (and coded to) return `nullptr` when it gets to the sentinel, but with an `ilist_half_node` as a sentinel, the sentinel check looks into some other memory and we don't recognize we've hit the end. Rooting out these scary cases is the reason I'm removing the implicit conversions before doing anything else with `ilist`; I'm not at all surprised that clients rely on badness. I found another scary case -- this time, not relying on badness, just bad (but I guess getting lucky so far) -- in `ObjectSizeOffsetEvaluator::compute_()`. Here, we save out the insertion point, do some things, and then restore it. Previously, we let the iterator auto-convert to `Instruction*`, and then set it back using the `Instruction*` version: Instruction *PrevInsertPoint = Builder.GetInsertPoint(); /* Logic that may change insert point */ if (PrevInsertPoint) Builder.SetInsertPoint(PrevInsertPoint); The check for `PrevInsertPoint` doesn't protect correctly against bad accesses. If the insertion point has been set to the end of a basic block (i.e., `SetInsertPoint(SomeBB)`), then `GetInsertPoint()` returns an iterator pointing at the list sentinel. The version of `SetInsertPoint()` that's getting called will then call `PrevInsertPoint->getParent()`, which explodes horribly. The only reason this hasn't blown up is that it's fairly unlikely the builder is adding to the end of the block; usually, we're adding instructions somewhere before the terminator. llvm-svn: 249925
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-091-207/+234
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | with the new pass manager, and no longer relying on analysis groups. This builds essentially a ground-up new AA infrastructure stack for LLVM. The core ideas are the same that are used throughout the new pass manager: type erased polymorphism and direct composition. The design is as follows: - FunctionAAResults is a type-erasing alias analysis results aggregation interface to walk a single query across a range of results from different alias analyses. Currently this is function-specific as we always assume that aliasing queries are *within* a function. - AAResultBase is a CRTP utility providing stub implementations of various parts of the alias analysis result concept, notably in several cases in terms of other more general parts of the interface. This can be used to implement only a narrow part of the interface rather than the entire interface. This isn't really ideal, this logic should be hoisted into FunctionAAResults as currently it will cause a significant amount of redundant work, but it faithfully models the behavior of the prior infrastructure. - All the alias analysis passes are ported to be wrapper passes for the legacy PM and new-style analysis passes for the new PM with a shared result object. In some cases (most notably CFL), this is an extremely naive approach that we should revisit when we can specialize for the new pass manager. - BasicAA has been restructured to reflect that it is much more fundamentally a function analysis because it uses dominator trees and loop info that need to be constructed for each function. All of the references to getting alias analysis results have been updated to use the new aggregation interface. All the preservation and other pass management code has been updated accordingly. The way the FunctionAAResultsWrapperPass works is to detect the available alias analyses when run, and add them to the results object. This means that we should be able to continue to respect when various passes are added to the pipeline, for example adding CFL or adding TBAA passes should just cause their results to be available and to get folded into this. The exception to this rule is BasicAA which really needs to be a function pass due to using dominator trees and loop info. As a consequence, the FunctionAAResultsWrapperPass directly depends on BasicAA and always includes it in the aggregation. This has significant implications for preserving analyses. Generally, most passes shouldn't bother preserving FunctionAAResultsWrapperPass because rebuilding the results just updates the set of known AA passes. The exception to this rule are LoopPass instances which need to preserve all the function analyses that the loop pass manager will end up needing. This means preserving both BasicAAWrapperPass and the aggregating FunctionAAResultsWrapperPass. Now, when preserving an alias analysis, you do so by directly preserving that analysis. This is only necessary for non-immutable-pass-provided alias analyses though, and there are only three of interest: BasicAA, GlobalsAA (formerly GlobalsModRef), and SCEVAA. Usually BasicAA is preserved when needed because it (like DominatorTree and LoopInfo) is marked as a CFG-only pass. I've expanded GlobalsAA into the preserved set everywhere we previously were preserving all of AliasAnalysis, and I've added SCEVAA in the intersection of that with where we preserve SCEV itself. One significant challenge to all of this is that the CGSCC passes were actually using the alias analysis implementations by taking advantage of a pretty amazing set of loop holes in the old pass manager's analysis management code which allowed analysis groups to slide through in many cases. Moving away from analysis groups makes this problem much more obvious. To fix it, I've leveraged the flexibility the design of the new PM components provides to just directly construct the relevant alias analyses for the relevant functions in the IPO passes that need them. This is a bit hacky, but should go away with the new pass manager, and is already in many ways cleaner than the prior state. Another significant challenge is that various facilities of the old alias analysis infrastructure just don't fit any more. The most significant of these is the alias analysis 'counter' pass. That pass relied on the ability to snoop on AA queries at different points in the analysis group chain. Instead, I'm planning to build printing functionality directly into the aggregation layer. I've not included that in this patch merely to keep it smaller. Note that all of this needs a nearly complete rewrite of the AA documentation. I'm planning to do that, but I'd like to make sure the new design settles, and to flesh out a bit more of what it looks like in the new pass manager first. Differential Revision: http://reviews.llvm.org/D12080 llvm-svn: 247167
* [PM/AA] Simplify the AliasAnalysis interface by removing a wrapperChandler Carruth2015-08-061-7/+0
| | | | | | | | | | | | | | | | around a DataLayout interface in favor of directly querying DataLayout. This wrapper specifically helped handle the case where this no DataLayout, but LLVM now requires it simplifynig all of this. I've updated callers to directly query DataLayout. This in turn exposed a bunch of places where we should have DataLayout readily available but don't which I've fixed. This then in turn exposed that we were passing DataLayout around in a bunch of arguments rather than making it readily available so I've also fixed that. No functionality changed. llvm-svn: 244189
* [AA] Use CallSite cast idiom. No functionality change.Benjamin Kramer2015-08-051-3/+2
| | | | llvm-svn: 244045
* [CaptureTracker] Provide an ordered basic block to PointerMayBeCapturedBeforeBruno Cardoso Lopes2015-07-311-6/+12
| | | | | | | | | | | | | | | | | | This patch is a follow up from r240560 and is a step further into mitigating the compile time performance issues in CaptureTracker. By providing the CaptureTracker with a "cached ordered basic block" instead of computing it every time, MemDepAnalysis can use this cache throughout its calls to AA->callCapturesBefore, avoiding to recompute it for every scanned instruction. In the same testcase used in r240560, compile time is reduced from 2min to 30s. This also fixes PR22348. rdar://problem/19230319 Differential Revision: http://reviews.llvm.org/D11364 llvm-svn: 243750
* [PM/AA] Extract the ModRef enums from the AliasAnalysis class inChandler Carruth2015-07-221-91/+91
| | | | | | | | | | | | | | | | | | | | | | | preparation for de-coupling the AA implementations. In order to do this, they had to become fake-scoped using the traditional LLVM pattern of a leading initialism. These can't be actual scoped enumerations because they're bitfields and thus inherently we use them as integers. I've also renamed the behavior enums that are specific to reasoning about the mod/ref behavior of functions when called. This makes it more clear that they have a very narrow domain of applicability. I think there is a significantly cleaner API for all of this, but I don't want to try to do really substantive changes for now, I just want to refactor the things away from analysis groups so I'm preserving the exact original design and just cleaning up the names, style, and lifting out of the class. Differential Revision: http://reviews.llvm.org/D10564 llvm-svn: 242963
* [PM/AA] Remove the last of the legacy update API from AliasAnalysis asChandler Carruth2015-07-221-5/+0
| | | | | | | | | | | | | part of simplifying its interface and usage in preparation for porting to work with the new pass manager. Note that this will likely expose that we have dead arguments, members, and maybe even pass requirements for AA. I'll be cleaning those up in seperate patches. This just zaps the actual update API. Differential Revision: http://reviews.llvm.org/D11325 llvm-svn: 242881
* [PM/AA] Remove the addEscapingUse update API that won't be easy toChandler Carruth2015-07-181-5/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | directly model in the new PM. This also was an incredibly brittle and expensive update API that was never fully utilized by all the passes that claimed to preserve AA, nor could it reasonably have been extended to all of them. Any number of places add uses of values. If we ever wanted to reliably instrument this, we would want a callback hook much like we have with ValueHandles, but doing this for every use addition seems *extremely* expensive in terms of compile time. The only user of this update mechanism is GlobalsModRef. The idea of using this to keep it up to date doesn't really work anyways as its analysis requires a symmetric analysis of two different memory locations. It would be very hard to make updates be sufficiently rigorous to *guarantee* symmetric analysis in this way, and it pretty certainly isn't true today. However, folks have been using GMR with this update for a long time and seem to not be hitting the issues. The reported issue that the update hook fixes isn't even a problem any more as other changes to GetUnderlyingObject worked around it, and that issue stemmed from *many* years ago. As a consequence, a prior patch provided a flag to control the unsafe behavior of GMR, and this patch removes the update mechanism that has questionable compile-time tradeoffs and is causing problems with moving to the new pass manager. Note the lack of test updates -- not one test in tree actually requires this update, even for a contrived case. All of this was extensively discussed on the dev list, this patch will just enact what that discussion decides on. I'm sending it for review in part to show what I'm planning, and in part to show the *amazing* amount of work this avoids. Every call to the AA here is something like three to six indirect function calls, which in the non-LTO pipeline never do any work! =[ Differential Revision: http://reviews.llvm.org/D11214 llvm-svn: 242605
* [PM/AA] Completely remove the AliasAnalysis::copyValue interface.Chandler Carruth2015-07-111-5/+0
| | | | | | | | | | | | | | | | | | | | | No in-tree alias analysis used this facility, and it was not called in any particularly rigorous way, so it seems unlikely to be correct. Note that one of the only stateful AA implementations in-tree, GlobalsModRef is completely broken currently (and any AA passes like it are equally broken) because Module AA passes are not effectively invalidated when a function pass that fails to update the AA stack runs. Ultimately, it doesn't seem like we know how we want to build stateful AA, and until then trying to support and maintain correctness for an untested API is essentially impossible. To that end, I'm planning to rip out all of the update API. It can return if and when we need it and know how to build it on top of the new pass manager and as part of *tested* stateful AA implementations in the tree. Differential Revision: http://reviews.llvm.org/D10889 llvm-svn: 241975
* [PM/AA] Hoist the AliasResult enum out of the AliasAnalysis class.Chandler Carruth2015-06-221-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | This will allow classes to implement the AA interface without deriving from the class or referencing an internal enum of some other class as their return types. Also, to a pretty fundamental extent, concepts such as 'NoAlias', 'MayAlias', and 'MustAlias' are first class concepts in LLVM and we aren't saving anything by scoping them heavily. My mild preference would have been to use a scoped enum, but that feature is essentially completely broken AFAICT. I'm extremely disappointed. For example, we cannot through any reasonable[1] means construct an enum class (or analog) which has scoped names but converts to a boolean in order to test for the possibility of aliasing. [1]: Richard Smith came up with a "solution", but it requires class templates, and lots of boilerplate setting up the enumeration multiple times. Something like Boost.PP could potentially bundle this up, but even that would be quite painful and it doesn't seem realistically worth it. The enum class solution would probably work without the need for a bool conversion. Differential Revision: http://reviews.llvm.org/D10495 llvm-svn: 240255
* [PM/AA] Remove the UnknownSize static member from AliasAnalysis.Chandler Carruth2015-06-171-1/+1
| | | | | | | | This is now living in MemoryLocation, which is what it pertains to. It is also an enum there rather than a static data member which is left never defined. llvm-svn: 239886
* [PM/AA] Remove the Location typedef from the AliasAnalysis class nowChandler Carruth2015-06-171-22/+21
| | | | | | | | | | | | that it is its own entity in the form of MemoryLocation, and update all the callers. This is an entirely mechanical change. References to "Location" within AA subclases become "MemoryLocation", and elsewhere "AliasAnalysis::Location" becomes "MemoryLocation". Hope that helps out-of-tree folks update. llvm-svn: 239885
OpenPOWER on IntegriCloud