summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/MemorySSA.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [MemorySSA] Remove unused field. NFC.George Burgess IV2016-08-221-6/+1
| | | | | | | | Given that we're not currently using blocker info, and whether or not we will end up using it it is unclear, don't waste 8 (or 4) bytes of memory per path node. llvm-svn: 279493
* MSSA: Factor out phi node placementDaniel Berlin2016-08-221-17/+22
| | | | llvm-svn: 279462
* MSSA: Only rename accesses whose defining access is nullptrDaniel Berlin2016-08-221-14/+6
| | | | llvm-svn: 279461
* Use the range variant of find/find_if instead of unpacking begin/endDavid Majnemer2016-08-121-3/+2
| | | | | | | | | If the result of the find is only used to compare against end(), just use is_contained instead. No functionality change is intended. llvm-svn: 278469
* [MSSA] Use is_containedDaniel Berlin2016-08-111-1/+1
| | | | llvm-svn: 278418
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
* [MemorySSA] Fix windows build breakage caused by r278028Geoff Berry2016-08-081-4/+4
| | | | | r278028: [MemorySSA] Ensure address stability of MemorySSA object. llvm-svn: 278035
* [MemorySSA] Ensure address stability of MemorySSA object.Geoff Berry2016-08-081-17/+13
| | | | | | | | | | | | | | | | | Summary: Ensure that the MemorySSA object never changes address when using the new pass manager since the walkers contained by MemorySSA cache pointers to it at construction time. This is achieved by wrapping the MemorySSAAnalysis result in a unique_ptr. Also add some asserts that check for this bug. Reviewers: george.burgess.iv, dberlin Subscribers: mcrosier, hfinkel, chandlerc, silvas, llvm-commits Differential Revision: https://reviews.llvm.org/D23171 llvm-svn: 278028
* [MSSA] Fix PR28880 by fixing use optimizer's lower bound tracking behavior.Daniel Berlin2016-08-081-4/+16
| | | | | | | | | | | | | | | | 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] Use depth first iterator instead of custom version.Daniel Berlin2016-08-051-19/+3
| | | | | | | | | | | | | | | | | Summary: Originally the plan was to use the custom worklist to do some block popping, and because we don't actually need a visited set. The custom one we have here is slightly broken, and it's not worth fixing vs using depth_first_iterator since we aren't going to go the route we originally were. Fixes PR28874 Reviewers: george.burgess.iv Subscribers: llvm-commits, gberry Differential Revision: https://reviews.llvm.org/D23187 llvm-svn: 277880
* [MSSA] Match assert vs llvm_unreachable style in verification functions.Daniel Berlin2016-08-051-11/+12
| | | | llvm-svn: 277873
* Rewrite domination verifier to handle local domination as well.Daniel Berlin2016-08-051-38/+19
| | | | | | | | | | | | | | Summary: Rewrite domination verifier to handle local domination as well. This catches a bug Geoff Berry noticed. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23184 llvm-svn: 277872
* [MSSA] Fix a bug in MemorySSA's move ctor.George Burgess IV2016-08-031-0/+2
| | | | | | | Not a correctness issue, but it would be nice if we didn't have to recompute our block numbering (worst-case) every time we move MSSA. llvm-svn: 277652
* [MSSA] clang-format. NFC.George Burgess IV2016-08-031-8/+4
| | | | | | | 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/+23
| | | | | | | 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-031-0/+58
| | | | | | | | | | | | | | | 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
* [MSSA] Fix a caching bug.George Burgess IV2016-08-031-8/+8
| | | | | | | | | | | | | | | 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
* Support for lifetime begin/end markers in the MemorySSA use optimizerDaniel Berlin2016-08-031-1/+38
| | | | | | | | | | | | Summary: Depends on D23072 Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23076 llvm-svn: 277553
* Move to having a single real instructionClobbersQueryDaniel Berlin2016-08-021-88/+94
| | | | | | | | | | | | Summary: We really want to move towards MemoryLocOrCall (or fix AA) everywhere, but for now, this lets us have a single instructionClobbersQuery. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23072 llvm-svn: 277530
* Fixes for post-commit review comments on r277480Daniel Berlin2016-08-021-12/+10
| | | | llvm-svn: 277510
* MSVC 2013 does not implement C++11 unions properly, so remove the anoymous ↵Daniel Berlin2016-08-021-2/+2
| | | | | | | | union for now, and leave a FIXME. llvm-svn: 277485
* Rewrite the use optimizer to be less memory intensive and 50% faster.Daniel Berlin2016-08-021-31/+311
| | | | | | | | | | | | | | | | | | | | | | | | Fixes PR28670 Summary: Rewrite the use optimizer to be less memory intensive and 50% faster. Fixes PR28670 The new use optimizer works like a standard SSA renaming pass, storing all possible versions a MemorySSA use could get in a stack, and just tracking indexes into the stack. This uses much less memory than caching N^2 alias query results. It's also a lot faster. The current version defers phi node walking to the normal walker. Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23032 llvm-svn: 277480
* Fix the MemorySSA updating API to enable people to create memory accesses ↵Daniel Berlin2016-07-311-4/+6
| | | | | | before removing old ones llvm-svn: 277309
* [MSSA] Make EXPENSIVE_CHECKS check more.George Burgess IV2016-07-241-13/+11
| | | | | | | | checkClobberSanity will now be run for all results of `ClobberWalk`, instead of just the crazy phi-optimized ones. This can help us catch cases where our cache is being wonky. llvm-svn: 276553
* [MSSA] Remove useless assert. NFC.George Burgess IV2016-07-241-1/+0
| | | | | | | liveOnEntry is always a MemoryDef; asserting that a MemoryPhi isn't liveOnEntry, while correct, isn't very helpful. :) llvm-svn: 276542
* [MSSA] Add an overload for getClobberingMemoryAccess.George Burgess IV2016-07-201-7/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | A seemingly common use for the walker's getClobberingMemoryAccess function is: ``` MemoryAccess *getClobber(MemorySSAWalker *W, MemoryUseOrDef *MUD) { const Instruction *I = MUD->getMemoryInst(); return W->getClobberingMemoryAccess(I); } ``` Which is kind of redundant, since walkers will ultimately query MSSA to find out which MemoryAccess `I` maps to (...which is always `MUD`). So, this patch adds an overload of getClobberingMemoryAccess that accepts MemoryAccesses directly. As a result, the Instruction overload of getClobberingMemoryAccess becomes a lightweight wrapper around our new overload. Additionally, this patch un`virtual`izes the Instruction overload of getClobberingMemoryAccess, since there doesn't seem to be a walker that benefits from that being virtual, and I can't think of how else one would implement it. Happy to make it virtual again if we would benefit from doing so. llvm-svn: 276169
* Fix unused variableDaniel Berlin2016-07-191-2/+1
| | | | llvm-svn: 276050
* Make MemorySSA::dominates/locallydominates constant timeDaniel Berlin2016-07-191-16/+36
| | | | | | | | | | | | Summary: Make MemorySSA::dominates/locallydominates constant time Reviewers: george.burgess.iv, gberry Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D22527 llvm-svn: 276046
* [MemorySSA] Update to the new shiny walker.George Burgess IV2016-07-191-307/+830
| | | | | | | | | | | | | | | | | | | | | | | | 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
* [AliasAnalysis] Give back AA results for fence instructionsDavid Majnemer2016-07-151-5/+7
| | | | | | | | | | | | | 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
* [MemorySSA] Reinstate the legacy printer and verifier.Chad Rosier2016-07-061-0/+30
| | | | | | Differential Revision: http://reviews.llvm.org/D22058 llvm-svn: 274679
* Fix handling of forward unreachable but reverse-reachable blocks in ↵Daniel Berlin2016-07-061-2/+16
| | | | | | MemorySSA construction llvm-svn: 274606
* [MSSA] Fix typo. NFC.George Burgess IV2016-07-061-1/+1
| | | | llvm-svn: 274590
* Factor out buildMemorySSA from getWalker.Daniel Berlin2016-06-271-8/+11
| | | | | | NFC. llvm-svn: 273901
* Silence a -Wsign-compare warningDavid Majnemer2016-06-251-2/+2
| | | | llvm-svn: 273752
* [MemorySSA] Move code around a bit. NFC.George Burgess IV2016-06-241-34/+100
| | | | | | | | | | | | This patch moves MSSA's caching walker into MemorySSA, and moves the actual definition of MSSA's caching walker out of MemorySSA.h. This is done in preparation for the new walker, which should be out for review soonish. Also, this patch removes a field from UpwardsMemoryQuery and has a few lines of diff from clang-format'ing MemorySSA.cpp. llvm-svn: 273723
* Switch more loops to be range-basedDavid Majnemer2016-06-241-4/+3
| | | | | | | This makes the code a little more concise, no functional change is intended. llvm-svn: 273644
* Add MemoryAccess creation and PHI creation APIs to MemorySSADaniel Berlin2016-06-211-3/+108
| | | | | | | | | | Reviewers: george.burgess.iv, gberry, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D21463 llvm-svn: 273295
* Rename to be consistent with other type names. NFCDaniel Berlin2016-06-201-11/+12
| | | | llvm-svn: 273194
* [MemorySSA] Set CFGOnly correctly for MemorySSAWrapperPassGeoff Berry2016-06-141-2/+3
| | | | | | | | Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D21344 llvm-svn: 272712
* MemorySSA: fix memory access local dominance function for live on entrySebastian Pop2016-06-101-0/+15
| | | | | | | | | A memory access defined on function entry cannot be locally dominated by another memory access. The patch was split from http://reviews.llvm.org/D19338 which exposes the problem. Differential Revision: http://reviews.llvm.org/D21039 llvm-svn: 272436
* [MemorySSA] Port to new pass managerGeoff Berry2016-06-011-65/+55
| | | | | | | | | | | | | | | | | 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/+8
| | | | | | | | | | | | | 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
* MemorySSA: Remove argument to createNewAccess function.Peter Collingbourne2016-05-261-4/+3
| | | | | | | | There is only one caller of MemorySSA::createNewAccess, and it passes true as the IgnoreNonMemory argument. Remove that argument and fold its behavior into createNewAccess. llvm-svn: 270812
* [MemorySSA] Fix bugs in walker; refactor unittests a bit.George Burgess IV2016-04-291-8/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Unify XDEBUG and EXPENSIVE_CHECKS (into the latter), and add an option to ↵Filipe Cabecinhas2016-04-291-1/+1
| | | | | | | | | | | | | | | | | | | the cmake build to enable them. Summary: Historically, we had a switch in the Makefiles for turning on "expensive checks". This has never been ported to the cmake build, but the (dead-ish) code is still around. This will also make it easier to turn it on in buildbots. Reviewers: chandlerc Subscribers: jyknight, mzolotukhin, RKSimon, gberry, llvm-commits Differential Revision: http://reviews.llvm.org/D19723 llvm-svn: 268050
* [MemorySSA] Fix bug in CachingMemorySSAWalker::invalidateInfoGeoff Berry2016-04-221-11/+20
| | | | | | | | | | | | | | | | | | | | | Summary: CachingMemorySSAWalker::invalidateInfo was using IsCall to determine which cache map needed to be cleared of entries referring to the invalidated MemoryAccess, but there could also be entries referring to it in the other cache map (value entries, not key entries). This change just clears both tables to be conservatively correct. Also add a verifyRemoved() function, called when expensive checks (i.e. XDEBUG) are enabled to verify that the invalidated MemoryAccess object is not referenced in any of the caches. Reviewers: dberlin, george.burgess.iv Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19388 llvm-svn: 267157
* Correct IDF calculator for ReverseIDFDaniel Berlin2016-04-191-1/+1
| | | | | | | | | | | | | | Summary: Need to use predecessors for reverse graph, successors for forward graph. succ_iterator/pred_iterator are not compatible, this patch is all the work necessary to work around that (which is what everywhere else does). Not sure if there is a better way, so cc'ing some random folks to take a gander :) Reviewers: dblaikie, qcolombet, echristo Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D18796 llvm-svn: 266718
* [NFC] Header cleanupMehdi Amini2016-04-181-2/+1
| | | | | | | | | | | | | | Removed some unused headers, replaced some headers with forward class declarations. Found using simple scripts like this one: clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap' Patch by Eugene Kosov <claprix@yandex.ru> Differential Revision: http://reviews.llvm.org/D19219 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266595
* Fix "warning: variabl 'XX’ set but not used" in release build (variable ↵Mehdi Amini2016-04-021-1/+1
| | | | | | | used in assertion, NFC) From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 265220
OpenPOWER on IntegriCloud