summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/Util/MemorySSA
Commit message (Collapse)AuthorAgeFilesLines
* MemorySSA: Move to Analysis, from Transforms/Utils. It's used asDaniel Berlin2017-04-1122-1510/+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
* Add address space mangling to lifetime intrinsicsMatt Arsenault2017-04-101-6/+6
| | | | | | In preparation for allowing allocas to have non-0 addrspace. llvm-svn: 299876
* MemorySSA: Make lifetime starts defs for mustaliased pointersDaniel Berlin2017-04-101-1/+1
| | | | | | | | | | | | | | | | | | Summary: While we don't want them aliasing with other pointers, there seems to be no point in not having them clobber must-aliased'd pointers. If some day, we split the aliasing and ordering chains, we'd make this not aliasing but an ordering barrier (IE it doesn't affect it's memory, but we can't hoist it above it). Reviewers: hfinkel, george.burgess.iv Subscribers: Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D31865 llvm-svn: 299865
* [MemorySSA] Fix use of pointsToConstantMemory in ↵Hal Finkel2017-04-091-0/+23
| | | | | | | | | | isUseTriviallyOptimizableToLiveOnEntry In isUseTriviallyOptimizableToLiveOnEntry, pointsToConstantMemory needs to be called on the load's pointer operand, not on the result of the load (which might not even be a pointer). llvm-svn: 299823
* [MSSA] Small test fixPiotr Padlewski2017-03-311-1/+1
| | | | llvm-svn: 299235
* [MemorySSA] Add new tests for invariant.groupsPiotr Padlewski2017-01-231-0/+182
| | | | | | | | | | | | | | | | | Summary: Next round of extra tests for MSSA. I have a prototype invariant.group handling implementation that fixes all the FIXMEs, and I think it will be easier to see what is the difference if I firstly post this, and then only fix fixits. Reviewers: george.burgess.iv, dberlin Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D29022 llvm-svn: 292797
* [MemorySSA] Remove deprecated comment from testPiotr Padlewski2017-01-211-3/+0
| | | | llvm-svn: 292733
* [MemorySSA] Fix invariant.group test and add newPiotr Padlewski2017-01-211-2/+75
| | | | | | | | | | | | | | | | | | Summary: This test had a bug: !llvm.invariant.group instead of !invariant.group. Also add some new test for future development. All tests passes, when MSSA will support invariant.group only the lines with FIXIT should be changed. Reviewers: dberlin, george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28969 llvm-svn: 292730
* [AliasAnalysis] Teach BasicAA about memcpy.Bryant Wong2016-12-251-0/+16
| | | | | | Differential Revision: https://reviews.llvm.org/D27034 llvm-svn: 290526
* [MemorySSA] Fix unit tests broken by D26704Mandeep Singh Grang2016-11-212-9/+9
| | | | | | | | | | | | | | | | | Summary: D26704 fixed the non-determinism in codegen by sorting basic blocks before iteration so as to have a defined iteration order. As a result we need to fix the names (numbers) of the temporaries in the following unit tests: test/Transforms/Util/MemorySSA/multi-edges.ll test/Transforms/Util/MemorySSA/multiple-backedges-hal.ll Reviewers: dberlin, david2050, mgrang Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D26926 llvm-svn: 287575
* [MemorySSA] Fix for non-determinism in codegenMandeep Singh Grang2016-11-214-51/+51
| | | | | | | | | | | | | | | | | | | | This patch fixes the non-determinism caused due to iterating SmallPtrSet's which was uncovered due to the experimental "reverse iteration order " patch: https://reviews.llvm.org/D26718 The following unit tests failed because of the undefined order of iteration. LLVM :: Transforms/Util/MemorySSA/cyclicphi.ll LLVM :: Transforms/Util/MemorySSA/many-dom-backedge.ll LLVM :: Transforms/Util/MemorySSA/many-doms.ll LLVM :: Transforms/Util/MemorySSA/phi-translation.ll Reviewers: dberlin, mgrang Subscribers: dberlin, llvm-commits, david2050 Differential Revision: https://reviews.llvm.org/D26704 llvm-svn: 287563
* Remove pruning of phi nodes in MemorySSA - it makes updating harderDaniel Berlin2016-09-261-53/+0
| | | | | | | | | | Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24923 llvm-svn: 282419
* [MSSA] Fix PR28880 by fixing use optimizer's lower bound tracking behavior.Daniel Berlin2016-08-081-0/+51
| | | | | | | | | | | | | | | | Summary: In the use optimizer, we need to keep of whether the lower bound still dominates us or else we may decide a lower bound is still valid when it is not due to intervening pushes/pops. Fixes PR28880 (and probably a bunch of other things). Reviewers: george.burgess.iv Subscribers: MatzeB, llvm-commits, sebpop Differential Revision: https://reviews.llvm.org/D23237 llvm-svn: 277978
* [MSSA] Add special handling for invariant/constant loads.George Burgess IV2016-08-031-1/+17
| | | | | | | 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] Add logic for special handling of atomics/volatiles.George Burgess IV2016-08-034-0/+244
| | | | | | | | | | | | | | | This patch makes MemorySSA recognize atomic/volatile loads, and makes MSSA treat said loads specially. This allows us to be a bit more aggressive in some cases. Administrative note: Revision was LGTM'ed by reames in person. Additionally, this doesn't include the `invariant.load` recognition in the differential revision, because I feel it's better to commit that separately. Will commit soon. Differential Revision: https://reviews.llvm.org/D16875 llvm-svn: 277637
* Support for lifetime begin/end markers in the MemorySSA use optimizerDaniel Berlin2016-08-031-0/+30
| | | | | | | | | | | | Summary: Depends on D23072 Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23076 llvm-svn: 277553
* [MemorySSA] Update to the new shiny walker.George Burgess IV2016-07-192-4/+2
| | | | | | | | | | | | | | | | | | | | | | | | This patch updates MemorySSA's use-optimizing walker to be more accurate and, in some cases, faster. Essentially, this changed our core walking algorithm from a cache-as-you-go DFS to an iteratively expanded DFS, with all of the caching happening at the end. Said expansion happens when we hit a Phi, P; we'll try to do the smallest amount of work possible to see if optimizing above that Phi is legal in the first place. If so, we'll expand the search to see if we can optimize to the next phi, etc. An iteratively expanded DFS lets us potentially quit earlier (because we don't assume that we can optimize above all phis) than our old walker. Additionally, because we don't cache as we go, we can now optimize above loops. As an added bonus, this patch adds a ton of verification (if EXPENSIVE_CHECKS are enabled), so finding bugs is easier. Differential Revision: https://reviews.llvm.org/D21777 llvm-svn: 275940
* [MemorySSA] Reinstate the legacy printer and verifier.Chad Rosier2016-07-0615-15/+15
| | | | | | Differential Revision: http://reviews.llvm.org/D22058 llvm-svn: 274679
* Fix handling of forward unreachable but reverse-reachable blocks in ↵Daniel Berlin2016-07-061-0/+23
| | | | | | MemorySSA construction llvm-svn: 274606
* [MemorySSA] Port to new pass managerGeoff Berry2016-06-0116-16/+32
| | | | | | | | | | | | | | | | | 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: Revert r269678 and r268068; replace with special casing in MemorySSA.Peter Collingbourne2016-05-261-0/+1
| | | | | | | | | | | | | It turns out that too many passes are relying on alias analysis results for control dependencies. Until we fix that by introducing a more accurate modelling of control dependencies, special case assume in MemorySSA instead. Also introduce tests to ensure we don't regress the FunctionAttrs or LICM passes. Differential Revision: http://reviews.llvm.org/D20658 llvm-svn: 270823
* [BasicAA] Treat llvm.assume as not accessing memory in ↵Geoff Berry2016-04-291-0/+17
| | | | | | | | | | | | getModRefBehavior(Function) Reviewers: dberlin, chandlerc, hfinkel, reames, sanjoy Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19730 llvm-svn: 268068
* [MemorySSA] Make the visitor more careful with calls.George Burgess IV2016-03-301-0/+27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Prior to this patch, the MemorySSA caching visitor would cache all calls that it visited. When paired with phi optimization, this can be problematic. Consider: define void @foo() { ; 1 = MemoryDef(liveOnEntry) call void @clobberFunction() br i1 undef, label %if.end, label %if.then if.then: ; MemoryUse(??) call void @readOnlyFunction() ; 2 = MemoryDef(1) call void @clobberFunction() br label %if.end if.end: ; 3 = MemoryPhi(...) ; MemoryUse(?) call void @readOnlyFunction() ret void } When optimizing MemoryUse(?), we visit defs 1 and 2, so we note to cache them later. We ultimately end up not being able to optimize passed the Phi, so we set MemoryUse(?) to point to the Phi. We then cache the clobbering call for def 1 to be the Phi. This commit changes this behavior so that we wipe out any calls added to VisistedCalls while visiting the defs of a phi we couldn't optimize. Aside: With this patch, we now can bootstrap clang/LLVM without a single MemorySSA verifier failure. Woohoo. :) llvm-svn: 264820
* [MemorySSA] Change how the walker views/walks visited phis.George Burgess IV2016-03-302-5/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch teaches the caching MemorySSA walker a few things: 1. Not to walk Phis we've walked before. It seems that we tried to do this before, but it didn't work so well in cases like: define void @foo() { %1 = alloca i8 %2 = alloca i8 br label %begin begin: ; 3 = MemoryPhi({%0,liveOnEntry},{%end,2}) ; 1 = MemoryDef(3) store i8 0, i8* %2 br label %end end: ; MemoryUse(?) load i8, i8* %1 ; 2 = MemoryDef(1) store i8 0, i8* %2 br label %begin } Because we wouldn't put Phis in Q.Visited until we tried to visit them. So, when trying to optimize MemoryUse(?): - We would visit 3 above - ...Which would make us put {%0,liveOnEntry} in Q.Visited - ...Which would make us visit {%0,liveOnEntry} - ...Which would make us put {%end,2} in Q.Visited - ...Which would make us visit {%end,2} - ...Which would make us visit 3 - ...Which would realize we've already visited everything in 3 - ...Which would make us conservatively return 3. In the added test-case, (@looped_visitedonlyonce) this behavior would cause us to give incorrect results. Specifically, we'd visit 4 twice in the same query, but on the second visit, we'd skip while.cond because it had been visited, visit if.then/if.then2, and cache "1" as the clobbering def on the way back. 2. If we try to walk the defs of a {Phi,MemLoc} and see it has been visited before, just hand back the Phi we're trying to optimize. I promise this isn't as terrible as it seems. :) We now insert {Phi,MemLoc} pairs just before walking the Phi's upward defs. So, we check the cache for the {Phi,MemLoc} pair before checking if we've already walked the Phi. The {Phi,MemLoc} pair is (almost?) always guaranteed to have a cache entry if we've already fully walked it, because we cache as we go. So, if the {Phi,MemLoc} pair isn't in cache, either: (a) we must be in the process of visiting it (in which case, we can't give a better answer in a cache-as-we-go DFS walker) (b) we visited it, but didn't cache it on the way back (...which seems to require `ModifyingAccess` to not dominate `StartingAccess`, so I'm 99% sure that would be an error. If it's not an error, I haven't been able to get it to happen locally, so I suspect it's rare.) - - - - - As a consequence of this change, we no longer skip upward defs of phis, so we can kill the `VisitedOnlyOne` check. This gives us better accuracy than we had before, at the cost of potentially doing a bit more work when we have a loop. llvm-svn: 264814
* Fix bugs in the MemorySSA walker.George Burgess IV2016-03-232-0/+237
| | | | | | | | | | | | | | | | | | There are a few bugs in the walker that this patch addresses. Primarily: - Caching can break when we have multiple BBs without phis - We weren't optimizing some phis properly - Because of how the DFS iterator works, there were times where we wouldn't cache any results of our DFS I left the test cases with FIXMEs in, because I'm not sure how much effort it will take to get those to work (read: We'll probably ultimately have to end up redoing the walker, or we'll have to come up with some creative caching tricks), and more test coverage = better. Differential Revision: http://reviews.llvm.org/D18065 llvm-svn: 264180
* [MemorySSA] Consider def-only BBs for live-in calculations.George Burgess IV2016-03-211-0/+23
| | | | | | | | | | | | | | | | | | | | | | | | | | | If we have a BB with only MemoryDefs, live-in calculations will ignore it. This means we get results like this: define void @foo(i8* %p) { ; 1 = MemoryDef(liveOnEntry) store i8 0, i8* %p br i1 undef, label %if.then, label %if.end if.then: ; 2 = MemoryDef(1) store i8 1, i8* %p br label %if.end if.end: ; 3 = MemoryDef(1) store i8 2, i8* %p ret void } ...When there should be a MemoryPhi in the `if.end` BB. This patch fixes that behavior. llvm-svn: 263991
* Make check line consistentDaniel Berlin2016-02-071-0/+29
| | | | llvm-svn: 260055
* Add a test for MemorySSA. NFC.George Burgess IV2016-02-051-0/+24
| | | | | | | We don't currently have many tests that deal with operations on multiple local MemoryLocations. This new test helps out a bit in that regard. llvm-svn: 259854
* The canonical way to XFAIL a test for all targets is XFAIL: *, not XFAIL:Benjamin Kramer2016-02-041-1/+1
| | | | | | | | Fix the lit bug that enabled this "feature" (empty triple is substring of all possible target triples) and change the two outliers to use the documented * syntax. llvm-svn: 259799
* This patch adds MemorySSA to LLVM.George Burgess IV2016-02-0212-0/+502
Please see include/llvm/Transforms/Utils/MemorySSA.h for a description of MemorySSA, and what it does. Differential Revision: http://reviews.llvm.org/D7864 llvm-svn: 259595
OpenPOWER on IntegriCloud