summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/Transforms/Utils/MemorySSA.cpp
Commit message (Collapse)AuthorAgeFilesLines
* MemorySSA: Move to Analysis, from Transforms/Utils. It's used asDaniel Berlin2017-04-111-865/+0
| | | | | | | | Analysis, it has Analysis passes, and once NewGVN is made an Analysis, this removes the cross dependency from Analysis to Transform/Utils. NFC. llvm-svn: 299980
* Move updating functions to MemorySSAUpdater.Daniel Berlin2017-02-221-22/+28
| | | | | | | | | | | | | | | Add updater to passes that now need it. Move around code in MemorySSA to expose needed functions. Summary: Mostly cleanup Reviewers: george.burgess.iv Subscribers: llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D30221 llvm-svn: 295887
* MemorySSA: Add support for renaming uses in the updater.Daniel Berlin2017-02-201-2/+6
| | | | | | | | | | | | | | Summary: This lets one add aliasing stores to the updater. (i'm next going to move the creation/etc functions to the updater) Reviewers: george.burgess.iv Subscribers: llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D30154 llvm-svn: 295677
* Revert "[MemorySSA] Revert r293361 and r293363, as the tests fail under asan."Daniel Berlin2017-01-301-0/+56
| | | | | | | This reverts commit r293471, reapplying r293361 and r293363 with a fix for an out-of-bounds read. llvm-svn: 293474
* [MemorySSA] Revert r293361 and r293363, as the tests fail under asan.Sam McCall2017-01-301-56/+0
| | | | llvm-svn: 293471
* MemorySSA: Allow movement to arbitrary placesDaniel Berlin2017-01-281-0/+56
| | | | | | | | | | | | Summary: Extend the MemorySSAUpdater API to allow movement to arbitrary places Reviewers: davide, george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29239 llvm-svn: 293363
* MemorySSA: Move updater to its own fileDaniel Berlin2017-01-281-0/+1
| | | | llvm-svn: 293357
* Introduce a basic MemorySSA updater, that supports insertDef,Daniel Berlin2017-01-281-8/+270
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | insertUse, moveBefore and moveAfter operations. Summary: This creates a basic MemorySSA updater that handles arbitrary insertion of uses and defs into MemorySSA, as well as arbitrary movement around the CFG. It replaces the current splice API. It can be made to handle arbitrary control flow changes. Currently, it uses the same updater algorithm from D28934. The main difference is because MemorySSA is single variable, we have the complete def and use list, and don't need anyone to give it to us as part of the API. We also have to rename stores below us in some cases. If we go that direction in that patch, i will merge all the updater implementations (using an updater_traits or something to provide the get* functions we use, called read*/write* in that patch). Sadly, the current SSAUpdater algorithm is way too slow to use for what we are doing here. I have updated the tests we have to basically build memoryssa incrementally using the updater api, and make sure it still comes out the same. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29047 llvm-svn: 293356
* MemorySSA: Link all defs together into an intrusive defslist, to make ↵Daniel Berlin2017-01-251-0/+2
| | | | | | | | | | | | | | | | | | | | | | | updater easier Summary: This is the first in a series of patches to add a simple, generalized updater to MemorySSA. For MemorySSA, every def is may-def, instead of the normal must-def. (the best way to think of memoryssa is "everything is really one variable, with different versions of that variable at different points in the program). This means when updating, we end up having to do a bunch of work to touch defs below and above us. In order to support this quickly, i have ilist'd all the defs for each block. ilist supports tags, so this is quite easy. the only slightly messy part is that you can't have two iplists for the same type that differ only whether they have the ownership part enabled or not, because the traits are for the value type. The verifiers have been updated to test that the def order is correct. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29046 llvm-svn: 293085
* [MemorySSA] Define a restricted upward AccessList splice.Bryant Wong2016-12-251-0/+48
| | | | | | Differential Revision: https://reviews.llvm.org/D26661 llvm-svn: 290527
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-2/+3
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-3/+2
| | | | | | | | | 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
* [MemorySSA] Tighten up types to make our API prettier. NFC.George Burgess IV2016-11-011-2/+1
| | | | | | | | Patch by bryant. Differential Revision: https://reviews.llvm.org/D26126 llvm-svn: 285750
* [MSSA] Avoid unnecessary use walks when calling getClobberingMemoryAccessDaniel Berlin2016-10-201-14/+28
| | | | | | | | | | | | | | | Summary: This allows us to mark when uses have been optimized. This lets us avoid rewalking (IE when people call getClobberingAccess on everything), and also enables us to later relax the requirement of use optimization during updates with less cost. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D25172 llvm-svn: 284771
* [MSSA] Allow unittests to use BasicAA when building.George Burgess IV2016-10-031-12/+37
| | | | | | | | | | | | We now build MemorySSA in its ctor, instead of waiting until the user calls MemorySSA::getWalker. This silently changed our unittests, since we add BasicAA to AAResults *after* constructing MemorySSA (...but before calling MemorySSA::getWalker). None of them broke because we do most of our "did this get optimized correctly?" tests in .ll files. llvm-svn: 283158
* Update MemorySSA unittest to account for non-pruned SSA formDaniel Berlin2016-09-261-10/+6
| | | | llvm-svn: 282421
* [MSSA] clang-format. NFC.George Burgess IV2016-08-031-3/+2
| | | | | | | Didn't want to fold this in with r277640, since it touches bits that aren't entirely related to r277640. llvm-svn: 277641
* [MSSA] Add special handling for invariant/constant loads.George Burgess IV2016-08-031-0/+33
| | | | | | | This is a follow-up to r277637. It teaches MemorySSA that invariant loads (and loads of provably constant memory) are always liveOnEntry. llvm-svn: 277640
* [MSSA] Fix a caching bug.George Burgess IV2016-08-031-0/+74
| | | | | | | | | | | | | | | This fixes a bug where we'd sometimes cache overly-conservative results with our walker. This bug was made more obvious by r277480, which makes our cache far more spotty than it was. Test case is llvm-unit, because we're likely going to use CachingWalker only for def optimization in the future. The bug stems from that there was a place where the walker assumed that `DefNode.Last` was a valid target to cache to when failing to optimize phis. This is sometimes incorrect if we have a cache hit. The fix is to use the thing we *can* assume is a valid target to cache to. :) llvm-svn: 277559
* Fix the MemorySSA updating API to enable people to create memory accesses ↵Daniel Berlin2016-07-311-0/+36
| | | | | | before removing old ones llvm-svn: 277309
* Comment fixes to MemorySSA.hDaniel Berlin2016-07-311-1/+1
| | | | llvm-svn: 277308
* Add MemoryAccess creation and PHI creation APIs to MemorySSADaniel Berlin2016-06-211-11/+93
| | | | | | | | | | Reviewers: george.burgess.iv, gberry, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D21463 llvm-svn: 273295
* [MemorySSA] Clean up unit tests a tiny bit. NFC.George Burgess IV2016-06-201-4/+4
| | | | | | | | | We recently made MemorySSA own the walker it creates. As a part of this, the MSSA test fixture was changed to have a `Walker*` instead of a `unique_ptr<Walker>`. So, we no longer need to do `&*Walker` in order to get a `Walker*`. llvm-svn: 273189
* [MemorySSA] Port to new pass managerGeoff Berry2016-06-011-3/+3
| | | | | | | | | | | | | | | | | Add support for the new pass manager to MemorySSA pass. Change MemorySSA to be computed eagerly upon construction. Change MemorySSAWalker to be owned by the MemorySSA object that creates it. Reviewers: dberlin, george.burgess.iv Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19664 llvm-svn: 271432
* [MemorySSA] Fix bugs in walker; refactor unittests a bit.George Burgess IV2016-04-291-23/+163
| | | | | | | | | | | | | | | | | | | | | | | | | | | This patch fixes two somewhat related bugs in MemorySSA's caching walker. These bugs were found because D19695 brought up the problem that we'd have defs cached to themselves, which is incorrect. The bugs this fixes are: - We would sometimes skip the nearest clobber of a MemoryAccess, because we would query our cache for a given potential clobber before checking if the potential clobber is the clobber we're looking for. The cache entry for the potential clobber would point to the nearest clobber *of the potential clobber*, so if that was a cache hit, we'd ignore the potential clobber entirely. - There are times (sometimes in DFS, sometimes in the getClobbering... functions) where we would insert cache entries that say a def clobbers itself. There's a bit of common code between the fixes for the bugs, so they aren't split out into multiple commits. This patch also adds a few unit tests, and refactors existing tests a bit to reduce the duplication of setup code. llvm-svn: 268087
* Remove every uses of getGlobalContext() in LLVM (but the C API)Mehdi Amini2016-04-141-1/+1
| | | | | | | | | | | At the same time, fixes InstructionsTest::CastInst unittest: yes you can leave the IR in an invalid state and exit when you don't destroy the context (like the global one), no longer now. This is the first part of http://reviews.llvm.org/D19094 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266379
* Really fix ASAN leak/etc issues with MemorySSA unittestsDaniel Berlin2016-03-021-10/+11
| | | | llvm-svn: 262519
* Revert "Fix ASAN detected errors in code and test" (it was not meant to be ↵Daniel Berlin2016-03-021-11/+10
| | | | | | | | committed yet) This reverts commit 890bbccd600ba1eb050353d06a29650ad0f2eb95. llvm-svn: 262512
* Fix ASAN detected errors in code and testDaniel Berlin2016-03-021-10/+11
| | | | llvm-svn: 262511
* [AA] Hoist the logic to reformulate various AA queries in terms of otherChandler Carruth2016-03-021-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Add the beginnings of an update API for preserving MemorySSADaniel Berlin2016-03-011-0/+87
Summary: This adds the beginning of an update API to preserve MemorySSA. In particular, this patch adds a way to remove memory SSA accesses when instructions are deleted. It also adds relevant unit testing infrastructure for MemorySSA's API. (There is an actual user of this API, i will make that diff dependent on this one. In practice, a ton of opt passes remove memory instructions, so it's hopefully an obviously useful API :P) Reviewers: hfinkel, reames, george.burgess.iv Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D17157 llvm-svn: 262362
OpenPOWER on IntegriCloud