summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/MemorySSA.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [PM] Change the static object whose address is used to uniquely identifyChandler Carruth2016-11-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
* [MemorySSA] Fix for non-determinism in codegenMandeep Singh Grang2016-11-211-2/+11
| | | | | | | | | | | | | | | | | | | | 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
* [MemorySSA] Tighten up types to make our API prettier. NFC.George Burgess IV2016-11-011-13/+12
| | | | | | | | Patch by bryant. Differential Revision: https://reviews.llvm.org/D26126 llvm-svn: 285750
* [MemorySSA] Add const to getClobberingMemoryAccess.George Burgess IV2016-10-281-3/+3
| | | | | | | | Thanks to bryant for the patch! Differential Revision: https://reviews.llvm.org/D26086 llvm-svn: 285432
* Now that VS2013 is gone, make a memoryssa structure an anonymous union againDaniel Berlin2016-10-221-4/+4
| | | | llvm-svn: 284910
* [MSSA] Avoid unnecessary use walks when calling getClobberingMemoryAccessDaniel Berlin2016-10-201-6/+37
| | | | | | | | | | | | | | | 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
* Memory-SSA: strengthen defClobbersUseOrDef interfaceSebastian Pop2016-10-131-19/+15
| | | | | | | As Danny pointed out, defClobbersUseOrDef should use MemoryLocOrCall to make sure fences are properly handled. llvm-svn: 284099
* commit back "GVN-hoist: fix store past load dependence analysis (PR30216, ↵Sebastian Pop2016-10-131-49/+61
| | | | | | | | | | PR30499)" This is with an extra change to avoid calling MemoryLocation::get() on a call instruction. Differential Revision: https://reviews.llvm.org/D25542 llvm-svn: 284098
* Revert "GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)"Reid Kleckner2016-10-131-56/+49
| | | | | | | | | | | This CL didn't actually address the test case in PR30499, and clang still crashes. Also revert dependent change "Memory-SSA cleanup of clobbers interface, NFC" Reverts r283965 and r283967. llvm-svn: 284093
* Memory-SSA cleanup of clobbers interface, NFCSebastian Pop2016-10-121-4/+10
| | | | | | | | | This implements the cleanup that Danny asked to commit separately from the previous fix to GVN-hoist in https://reviews.llvm.org/D25476#inline-219818 Tested with ninja check on x86_64-linux. llvm-svn: 283967
* GVN-hoist: fix store past load dependence analysis (PR30216, PR30499)Sebastian Pop2016-10-121-53/+54
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is a refreshed version of a patch that was reverted: it fixes the problems reported in both PR30216 and PR30499, and contains all the test-cases from both bugs. To hoist stores past loads, we used to search for potential conflicting loads on the hoisting path by following a MemorySSA def-def link from the store to be hoisted to the previous defining memory access, and from there we followed the def-use chains to all the uses that occur on the hoisting path. The problem is that the def-def link may point to a store that does not alias with the store to be hoisted, and so the loads that are walked may not alias with the store to be hoisted, and even as in the testcase of PR30216, the loads that may alias with the store to be hoisted are not visited. The current patch visits all loads on the path from the store to be hoisted to the hoisting position and uses the alias analysis to ask whether the store may alias the load. I was not able to use the MemorySSA functionality to ask for whether load and store are clobbered: I'm not sure which function to call, so I used a call to AA->isNoAlias(). Store past store is still working as before using a MemorySSA query: I added an extra test to pr30216.ll to make sure store past store does not regress. Tested on x86_64-linux with check and a test-suite run. Differential Revision: https://reviews.llvm.org/D25476 llvm-svn: 283965
* Remove pruning of phi nodes in MemorySSA - it makes updating harderDaniel Berlin2016-09-261-40/+5
| | | | | | | | | | Reviewers: george.burgess.iv Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24923 llvm-svn: 282419
* [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
OpenPOWER on IntegriCloud