summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/CFLAliasAnalysis.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [PM/AA] Rebuild LLVM's alias analysis infrastructure in a way compatibleChandler Carruth2015-09-091-51/+56
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Fix: CFLAA -- Mark no-args returns as unknownGeorge Burgess IV2015-08-281-0/+10
| | | | | | | | | | | | | | Prior to this patch, we hadn't been marking StratifiedSets with the appropriate StratifiedAttrs when handling the result of no-args call instructions. This caused us to report NoAlias when handed, for example, an escaped alloca and a result from an opaque function. Now we properly mark the return value of said functions. Thanks again to Chandler, Richard, and Nick for pinging me about this. Differential review: http://reviews.llvm.org/D12408 llvm-svn: 246240
* [PM/AA] Hoist the value handle definition for CFLAA into the header toChandler Carruth2015-08-141-22/+0
| | | | | | | satisfy libc++'s std::forward_list which requires the value type to be complete. llvm-svn: 245011
* [PM/AA] Extract a minimal interface for CFLAA to its own header file.Chandler Carruth2015-08-141-132/+78
| | | | | | | | | | I've used forward declarations and reorderd the source code some to make this reasonably clean and keep as much of the code as possible in the source file, including all the stratified set details. Just the basic AA interface and the create function are in the header file, and the header file is now included into the relevant locations. llvm-svn: 245009
* Fix some comment typos.Benjamin Kramer2015-08-081-2/+2
| | | | llvm-svn: 244402
* -Wdeprecated-clean: Fix cases of violating the rule of 5 in ways that are ↵David Blaikie2015-08-031-3/+1
| | | | | | | | | | | | | | | | | | | | | | deprecated in C++11 Various value handles needed to be copy constructible and copy assignable (mostly for their use in DenseMap). But to avoid an API that might allow accidental slicing, make these members protected in the base class and make derived classes final (the special members become implicitly public there - but disallowing further derived classes that might be sliced to the intermediate type). Might be worth having a warning a bit like -Wnon-virtual-dtor that catches public move/copy assign/ctors in classes with virtual functions. (suppressable in the same way - by making them protected in the base, and making the derived classes final) Could be fancier and only diagnose them when they're actually called, potentially. Also allow a few default implementations where custom implementations (especially with non-standard return types) were implemented. llvm-svn: 243909
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* [PM/AA] Hoist the AliasResult enum out of the AliasAnalysis class.Chandler Carruth2015-06-221-8/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Typo. NFC.Chad Rosier2015-06-191-2/+1
| | | | llvm-svn: 240141
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* [PM/AA] Remove the Location typedef from the AliasAnalysis class nowChandler Carruth2015-06-171-5/+5
| | | | | | | | | | | | 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
* Don't create instructions from ConstantExpr's in CFLAliasAnalysis.Pete Cooper2015-06-121-12/+41
| | | | | | | | | | The CFLAA code currently calls ConstantExpr::getAsInstruction which creates an instruction from a constant expr. We then pass that instruction to the InstVisitor to analyze it. Its not necessary to create these instructions as we can just cast from Constant to Operator in the visitor. This is how other InstVisitor’s such as SelectionDAGBuilder handle ConstantExpr. llvm-svn: 239616
* Convert PHI getIncomingValue() to foreach over incoming_values(). NFC.Pete Cooper2015-05-121-2/+1
| | | | | | | | We already had a method to iterate over all the incoming values of a PHI. This just changes all eligible code to use it. Ineligible code included anything which cared about the index, or was also trying to get the i'th incoming BB. llvm-svn: 237169
* Use 'override/final' instead of 'virtual' for overridden methodsAlexander Kornienko2015-04-111-2/+2
| | | | | | | | | | | | | | The patch is generated using clang-tidy misc-use-override check. This command was used: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py \ -checks='-*,misc-use-override' -header-filter='llvm|clang' \ -j=32 -fix -format http://reviews.llvm.org/D8925 llvm-svn: 234679
* Re-sort includes with sort-includes.py and insert raw_ostream.h where it's used.Benjamin Kramer2015-03-231-1/+2
| | | | llvm-svn: 232998
* Made CFLAA agree with clang-format. NFC.George Burgess IV2015-03-151-9/+7
| | | | | | So everyone's lives are easier in the future llvm-svn: 232293
* Added ConstantExpr support to CFLAA.George Burgess IV2015-03-101-40/+143
| | | | | | | | CFLAA didn't know how to properly handle ConstantExprs; it would silently ignore them. This was a problem if the ConstantExpr is, say, a GEP of a global, because CFLAA wouldn't realize that there's a global there. :) llvm-svn: 231743
* Added special handling for inttoptr in CFLAA.George Burgess IV2015-03-101-10/+22
| | | | | | | | | | We now treat pointers given to ptrtoint and pointers retrieved from inttoptr as similar to arguments or globals (can alias anything, etc.) This solves some of the problems we were having with giving incorrect results. llvm-svn: 231741
* Make DataLayout Non-Optional in the ModuleMehdi Amini2015-03-041-1/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: DataLayout keeps the string used for its creation. As a side effect it is no longer needed in the Module. This is "almost" NFC, the string is no longer canonicalized, you can't rely on two "equals" DataLayout having the same string returned by getStringRepresentation(). Get rid of DataLayoutPass: the DataLayout is in the Module The DataLayout is "per-module", let's enforce this by not duplicating it more than necessary. One more step toward non-optionality of the DataLayout in the module. Make DataLayout Non-Optional in the Module Module->getDataLayout() will never returns nullptr anymore. Reviewers: echristo Subscribers: resistor, llvm-commits, jholewinski Differential Revision: http://reviews.llvm.org/D7992 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231270
* Revert "Remove the explicit SDNodeIterator::operator= in favor of the ↵David Blaikie2015-03-031-1/+3
| | | | | | | | | | | implicit default" Accidentally committed a few more of these cleanup changes than intended. Still breaking these out & tidying them up. This reverts commit r231135. llvm-svn: 231136
* Remove the explicit SDNodeIterator::operator= in favor of the implicit defaultDavid Blaikie2015-03-031-3/+1
| | | | | | | | | | There doesn't seem to be any need to assert that iterator assignment is between iterators over the same node - if you want to reuse an iterator variable to iterate another node, that's perfectly acceptable. Just don't mix comparisons between iterators into disjoint sequences, as usual. llvm-svn: 231135
* Fixed a bug where CFLAA would crash the compiler.George Burgess IV2015-02-121-6/+13
| | | | | | | | We would crash if we couldn't locate a Function that either Location's Value belonged to. Now we just print out a debug message and return conservatively. llvm-svn: 228901
* Fix incorrect partial aliasingDaniel Berlin2015-01-261-7/+20
| | | | | | Update testcases llvm-svn: 227099
* Fix delegationDaniel Berlin2015-01-261-2/+5
| | | | llvm-svn: 227098
* Fixed a bug with how we determine bitset indices.George Burgess IV2015-01-211-1/+1
| | | | llvm-svn: 226671
* [cleanup] Re-sort all the #include lines in LLVM usingChandler Carruth2015-01-141-3/+3
| | | | | | | | | | | utils/sort_includes.py. I clearly haven't done this in a while, so more changed than usual. This even uncovered a missing include from the InstrProf library that I've added. No functionality changed here, just mechanical cleanup of the include order. llvm-svn: 225974
* Remove redundant virtual on overriden functions.David Blaikie2014-11-141-2/+2
| | | | llvm-svn: 222023
* [CFL-AA] CFL-AA should not assert on an va_arg instructionHal Finkel2014-10-141-0/+11
| | | | | | | | | | The CFL-AA implementation was missing a visit* routine for va_arg instructions, causing it to assert when run on a function that had one. For now, handle these in a conservative way. Fixes PR20954. llvm-svn: 219718
* [CFL-AA] Update for handling of globals and more testsHal Finkel2014-10-061-3/+11
| | | | | | | | | | | | | | | | | | We used to return PartialAlias if *either* variable being queried interacted with arguments or globals. AFAICT, we can change this to only returning MayAlias iff *both* variables being queried interacted with arguments or globals. Also, adding some basic functionality tests: some basic IPA tests, checking that we give conservative responses with arguments/globals thrown in the mix, and ensuring that we trace values through stores and loads. Note that saying that 'x' interacted with arguments or globals means that the Attributes of the StratifiedSet that 'x' belongs to has any bits set. Patch by George Burgess IV, thanks! llvm-svn: 219122
* Adds 'override' to overriding methods. NFC.Argyrios Kyrtzidis2014-10-011-1/+1
| | | | llvm-svn: 218815
* [CFLAA] Remove one final initializer listHal Finkel2014-09-031-1/+5
| | | | | | Maybe MSVC will be happy now... llvm-svn: 217000
* [CFLAA] And even more MSVC fixesHal Finkel2014-09-021-1/+5
| | | | | | Remove a couple more initializer lists and constexpr dependencies. llvm-svn: 216998
* [CFLAA] More cleanup for MSVCHal Finkel2014-09-021-9/+12
| | | | | | Remove more initializer lists, etc. llvm-svn: 216994
* [CFLAA] No initializer lists for MSVCHal Finkel2014-09-021-26/+27
| | | | | | MSVC 2012 does not understand initializer lists; remove them. llvm-svn: 216991
* [CFLAA] constexpr -> LLVM_CONSTEXPRHal Finkel2014-09-021-11/+12
| | | | | | Attempt to fix the MSVC build by not using constexpr. llvm-svn: 216979
* Add a CFL Alias Analysis implementationHal Finkel2014-09-021-0/+981
This provides an implementation of CFL alias analysis (including some supporting data structures). Currently, we don't have any extremely fancy features, sans some interprocedural analysis (i.e. no field sensitivity, etc.), and we do best sitting behind BasicAA + TBAA. In such a configuration, we take ~0.6-0.8% of total compile time, and give ~7-8% NoAlias responses to queries TBAA and BasicAA couldn't answer when bootstrapping LLVM. In testing this on other projects, we've seen up to 10.5% of queries dropped by BasicAA+TBAA answered with NoAlias by this algorithm. Patch by George Burgess IV (with minor modifications by me -- mostly adapting some BasicAA tests), thanks! llvm-svn: 216970
OpenPOWER on IntegriCloud