summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/IPA/GlobalsModRef.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [PM/AA] Put the 'final' keyword in the correct place. And actuallyChandler Carruth2015-07-221-1/+1
| | | | | | succeed at compiling my change before committing it too! llvm-svn: 242879
* [PM/AA] Replace the only use of the AliasAnalysis::deleteValue API (inChandler Carruth2015-07-221-35/+58
| | | | | | | | | | | | | | | | | | | | | | GlobalsModRef) with CallbackVHs that trigger the same behavior. This is technically more expensive, but in benchmarking some LTO runs, it seems unlikely to even be above the noise floor. The only way I was able to measure the performance of GMR at all was to run nothing else but this one analysis on a linked clang bitcode file. The call graph analysis still took 5x more time than GMR, and this change at most made GMR 2% slower (this is well within the noise, so its hard for me to be sure that this is an actual change). However, in a real LTO run over the same bitcode, the GMR run takes so little time that the pass timers don't measure it. With this, I can remove the last update API from the AliasAnalysis interface, but I'll actually remove the interface hook point in a follow-up commit. Differential Revision: http://reviews.llvm.org/D11324 llvm-svn: 242878
* [PM/AA] Remove the addEscapingUse update API that won't be easy toChandler Carruth2015-07-181-11/+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] Disable the core unsafe aspect of GlobalsModRef in the face ofChandler Carruth2015-07-171-6/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | basic changes to the IR such as folding pointers through PHIs, Selects, integer casts, store/load pairs, or outlining. This leaves the feature available behind a flag. This flag's default could be flipped if necessary, but the real-world performance impact of this particular feature of GMR may not be sufficiently significant for many folks to want to run the risk. Currently, the risk here is somewhat mitigated by half-hearted attempts to update GlobalsModRef when the rest of the optimizer changes something. However, I am currently trying to remove that update mechanism as it makes migrating the AA infrastructure to a form that can be readily shared between new and old pass managers very challenging. Without this update mechanism, it is possible that this still unlikely failure mode will start to trip people, and so I wanted to try to proactively avoid that. There is a lengthy discussion on the mailing list about why the core approach here is flawed, and likely would need to look totally different to be both reasonably effective and resilient to basic IR changes occuring. This patch is essentially the first of two which will enact the result of that discussion. The next patch will remove the current update mechanism. Thanks to lots of folks that helped look at this from different angles. Especial thanks to Michael Zolotukhin for doing some very prelimanary benchmarking of LTO without GlobalsModRef to get a rough idea of the impact we could be facing here. So far, it looks very small, but there are some concerns lingering from other benchmarking. The default here may get flipped if performance results end up pointing at this as a more significant issue. Also thanks to Pete and Gerolf for reviewing! Differential Revision: http://reviews.llvm.org/D11213 llvm-svn: 242512
* [PM/AA] Fix *numerous* serious bugs in GlobalsModRef found byChandler Carruth2015-07-151-22/+31
| | | | | | | | | | | | | | | | | | | | | | | | | inspection. While we want to handle calls specially in this code because they should have been modeled by the call graph analysis that precedes it, we should *not* be re-implementing the predicates for whether an instruction reads or writes memory. Those are well defined already. Notably, at least the following issues seem to be clearly missed before: - Ordered atomic loads can "write" to memory by causing writes from other threads to become visible. Similarly for ordered atomic stores. - AtomicRMW instructions quite obviously both read and write to memory. - AtomicCmpXchg instructions also read and write to memory. - Fences read and write to memory. - Invokes of intrinsics or memory allocation functions. I don't have any test cases, and I suspect this has never really come up in the real world. But there is no reason why it wouldn't, and it makes the code simpler to do this the right way. While here, I've tried to make the loops significantly simpler as well and added helpful comments as to what is going on. llvm-svn: 242281
* [PM/AA] Cleanup some loops to be range-based. NFC.Chandler Carruth2015-07-151-20/+19
| | | | llvm-svn: 242275
* [PM/AA] Reformat GlobalsModRef so that subsequent patches I make hereChandler Carruth2015-07-141-155/+160
| | | | | | don't continually introduce formatting deltas. NFC llvm-svn: 242129
* [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
* 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-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
* 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-7/+6
| | | | | | | | | | | | 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
* [CallSite] Make construction from Value* (or Instruction*) explicit.Benjamin Kramer2015-04-101-1/+1
| | | | | | | | | | | | | | | | | | | CallSite roughly behaves as a common base CallInst and InvokeInst. Bring the behavior closer to that model by making upcasts explicit. Downcasts remain implicit and work as before. Following dyn_cast as a mental model checking whether a Value *V isa CallSite now looks like this: if (auto CS = CallSite(V)) // think dyn_cast instead of: if (CallSite CS = V) This is an extra token but I think it is slightly clearer. Making the ctor explicit has the advantage of not accidentally creating nullptr CallSites, e.g. when you pass a Value * to a function taking a CallSite argument. llvm-svn: 234601
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-4/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* Make DataLayout Non-Optional in the ModuleMehdi Amini2015-03-041-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Use a range loop.Rafael Espindola2014-05-081-4/+2
| | | | llvm-svn: 208343
* SCC: Change clients to use const, NFCDuncan P. N. Exon Smith2014-04-251-1/+1
| | | | | | | | | | It's fishy to be changing the `std::vector<>` owned by the iterator, and no one actual does it, so I'm going to remove the ability in a subsequent commit. First, update the users. <rdar://problem/14292693> llvm-svn: 207252
* [C++] Use 'nullptr'.Craig Topper2014-04-241-5/+5
| | | | llvm-svn: 207083
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | definition below all the header #include lines, lib/Analysis/... edition. This one has a bit extra as there were *other* #define's before #include lines in addition to DEBUG_TYPE. I've sunk all of them as a block. llvm-svn: 206843
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-14/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-11/+11
| | | | | | class. llvm-svn: 202945
* [Modules] Move InstIterator out of the Support library, where it had noChandler Carruth2014-03-041-1/+1
| | | | | | | | | | | | | business. This header includes Function and BasicBlock and directly uses the interfaces of both classes. It has to do with the IR, it even has that in the name. =] Put it in the library it belongs to. This is one step toward making LLVM's Support library survive a C++ modules bootstrap. llvm-svn: 202814
* GlobalsModRef: Unify and clean up duplicated pointer analysis code.Benjamin Kramer2014-02-101-21/+12
| | | | llvm-svn: 201087
* cleanup: scc_iterator consumers should use isAtEndDuncan P. N. Exon Smith2014-02-041-2/+1
| | | | | | | | | | | | | | No functional change. Updated loops from: for (I = scc_begin(), E = scc_end(); I != E; ++I) to: for (I = scc_begin(); !I.isAtEnd(); ++I) for teh win. llvm-svn: 200789
* [PM] Split the CallGraph out from the ModulePass which creates theChandler Carruth2013-11-261-5/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | CallGraph. This makes the CallGraph a totally generic analysis object that is the container for the graph data structure and the primary interface for querying and manipulating it. The pass logic is separated into its own class. For compatibility reasons, the pass provides wrapper methods for most of the methods on CallGraph -- they all just forward. This will allow the new pass manager infrastructure to provide its own analysis pass that constructs the same CallGraph object and makes it available. The idea is that in the new pass manager, the analysis pass's 'run' method returns a concrete analysis 'result'. Here, that result is a 'CallGraph'. The 'run' method will typically do only minimal work, deferring much of the work into the implementation of the result object in order to be lazy about computing things, but when (like DomTree) there is *some* up-front computation, the analysis does it prior to handing the result back to the querying pass. I know some of this is fairly ugly. I'm happy to change it around if folks can suggest a cleaner interim state, but there is going to be some amount of unavoidable ugliness during the transition period. The good thing is that this is very limited and will naturally go away when the old pass infrastructure goes away. It won't hang around to bother us later. Next up is the initial new-PM-style call graph analysis. =] llvm-svn: 195722
* Merge CallGraph and BasicCallGraph.Rafael Espindola2013-10-311-1/+1
| | | | llvm-svn: 193734
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-5/+5
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-8/+8
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Make MemoryBuiltins aware of TargetLibraryInfo.Benjamin Kramer2012-08-291-3/+3
| | | | | | | | | | | | | | | | This disables malloc-specific optimization when -fno-builtin (or -ffreestanding) is specified. This has been a problem for a long time but became more severe with the recent memory builtin improvements. Since the memory builtin functions are used everywhere, this required passing TLI in many places. This means that functions that now have an optional TLI argument, like RecursivelyDeleteTriviallyDeadFunctions, won't remove dead mallocs anymore if the TLI argument is missing. I've updated most passes to do the right thing. Fixes PR13694 and probably others. llvm-svn: 162841
* refactor the MemoryBuiltin analysis:Nuno Lopes2012-06-211-14/+6
| | | | | | | | | | | | - provide more extensive set of functions to detect library allocation functions (e.g., malloc, calloc, strdup, etc) - provide an API to compute the size and offset of an object pointed by Move a few clients (GVN, AA, instcombine, ...) to the new API. This implementation is a lot more aggressive than each of the custom implementations being replaced. Patch reviewed by Nick Lewycky and Chandler Carruth, thanks. llvm-svn: 158919
* Handle intrinsics in GlobalsModRef. Fixes pr12351.Rafael Espindola2012-03-281-0/+6
| | | | llvm-svn: 153604
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-151-1/+1
| | | | | | Luis Felipe Strano Moraes! llvm-svn: 129558
* Use the new addEscapingValue callback to update GlobalsModRef when GVN adds ↵Owen Anderson2011-01-031-0/+11
| | | | | | | | PHIs of GEPs. For the moment, have GlobalsModRef handle this conservatively by simply removing the value from its maps. llvm-svn: 122787
* Move Value::getUnderlyingObject to be a standaloneDan Gohman2010-12-151-4/+5
| | | | | | | function so that it can live in Analysis instead of VMCore. llvm-svn: 121885
* Make ModRefBehavior a lattice. Use this to clean up AliasAnalysisDan Gohman2010-11-101-12/+17
| | | | | | chaining and simplify FunctionAttrs' GetModRefBehavior logic. llvm-svn: 118660
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Begin adding static dependence information to passes, which will allow us toOwen Anderson2010-10-121-1/+5
| | | | | | | | | perform initialization without static constructors AND without explicit initialization by the client. For the moment, passes are required to initialize both their (potential) dependencies and any passes they preserve. I hope to be able to relax the latter requirement in the future. llvm-svn: 116334
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Remove the experimental AliasAnalysis::getDependency interface, whichDan Gohman2010-09-141-11/+11
| | | | | | | | | | | isn't a good level of abstraction for memdep. Instead, generalize AliasAnalysis::alias and related interfaces with a new Location class for describing a memory location. For now, this is the same Pointer and Size as before, plus an additional field for a TBAA tag. Also, introduce a fixed MD_tbaa metadata tag kind. llvm-svn: 113858
* Now that PassInfo and Pass::ID have been separated, move the rest of the ↵Owen Anderson2010-08-231-3/+3
| | | | | | passes over to the new registration API. llvm-svn: 111815
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-3/+3
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-3/+3
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-3/+3
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* Remove PointerAccessInfo, which nothing was using.Dan Gohman2010-08-031-7/+5
| | | | llvm-svn: 110167
* Thread const correctness through a bunch of AliasAnalysis interfaces andDan Gohman2010-08-031-30/+35
| | | | | | | | | | | | eliminate several const_casts. Make CallSite implicitly convertible to ImmutableCallSite. Rename the getModRefBehavior for intrinsic IDs to getIntrinsicModRefBehavior to avoid overload ambiguity with CallSite, which happens to be implicitly convertible to bool. llvm-svn: 110155
* Speculatively revert r108813, in an attempt to get the self-host buildbots ↵Owen Anderson2010-07-201-1/+1
| | | | | | | | working again. I don't see why this patch would cause them to fail the way they are, but none of the other intervening patches seem likely either. llvm-svn: 108818
* Reapply r108794, a fix for the failing test from last time.Owen Anderson2010-07-201-1/+1
| | | | llvm-svn: 108813
* Revert r108794, "Separate PassInfo into two classes: a constructor-freeDaniel Dunbar2010-07-201-1/+1
| | | | | | | superclass (StaticPassInfo) and a constructor-ful subclass (PassInfo).", it is breaking teh everything. llvm-svn: 108805
* Separate PassInfo into two classes: a constructor-free superclass ↵Owen Anderson2010-07-201-1/+1
| | | | | | (StaticPassInfo) and a constructor-ful subclass (PassInfo). llvm-svn: 108794
* cache result of operator*Gabor Greif2010-07-091-2/+3
| | | | llvm-svn: 107982
OpenPOWER on IntegriCloud