summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemorySSA.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [MemorySSA] Check that block is reachable when adding phis.Alina Sbirlea2019-05-021-0/+2
| | | | | | | | | | | | | | | | | | | Summary: Originally the insertDef method was only used when building MemorySSA, and was limiting the number of Phi nodes that it created. Now it's used for updates as well, and it can create additional Phis needed for correctness. Make sure no Phis are created in unreachable blocks (condition met during MSSA build), otherwise the renamePass will find a null DTNode. Resolves PR41640. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61410 llvm-svn: 359845
* [MemorySSA] Invalidate MemorySSA if AA or DT are invalidated.Alina Sbirlea2019-04-301-0/+9
| | | | | | | | | | | | | | | | Summary: MemorySSA keeps internal pointers of AA and DT. If these get invalidated, so should MemorySSA. Reviewers: george.burgess.iv, chandlerc Subscribers: jlebar, Prazek, llvm-commits Tags: LLVM Differential Revision: https://reviews.llvm.org/D61043 llvm-svn: 359627
* Revert rL359519 : [MemorySSA] Invalidate MemorySSA if AA or DT are invalidated.Simon Pilgrim2019-04-301-9/+0
| | | | | | | | | | | | | | | | | | Summary: MemorySSA keeps internal pointers of AA and DT. If these get invalidated, so should MemorySSA. Reviewers: george.burgess.iv, chandlerc Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61043 ........ This was causing windows build bot failures llvm-svn: 359555
* [MemorySSA] Invalidate MemorySSA if AA or DT are invalidated.Alina Sbirlea2019-04-291-0/+9
| | | | | | | | | | | | | | | | Summary: MemorySSA keeps internal pointers of AA and DT. If these get invalidated, so should MemorySSA. Reviewers: george.burgess.iv, chandlerc Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61043 llvm-svn: 359519
* [MemorySSA] LCSSA preserves MemorySSA.Alina Sbirlea2019-04-231-0/+5
| | | | | | | | | | | | | | | | | | | | | Summary: Enabling MemorySSA in the old pass manager leads to MemorySSA being run twice due to the fact that LCSSA and LoopSimplify do not preserve MemorySSA. This is the first step to address that: target LCSSA. LCSSA does not make any changes that invalidate MemorySSA, so it preserves it by design. It must preserve AA as well, for this to hold. After this patch, MemorySSA is still run twice in the old pass manager. Step two follows: target LoopSimplify. Subscribers: mehdi_amini, jlebar, Prazek, llvm-commits, george.burgess.iv, chandlerc Tags: #llvm Differential Revision: https://reviews.llvm.org/D60832 llvm-svn: 359032
* [MemorySSA] Small fix for the clobber limit.Alina Sbirlea2019-04-121-4/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: After introducing the limit for clobber walking, `walkToPhiOrClobber` would assert that the limit is at least 1 on entry. The test included triggered that assert. The callsite in `tryOptimizePhi` making the calls to `walkToPhiOrClobber` is structured like this: ``` while (true) { if (getBlockingAccess()) { // calls walkToPhiOrClobber } for (...) { walkToPhiOrClobber(); } } ``` The cleanest fix is to check if the limit was reached inside `walkToPhiOrClobber`, and give an allowence of 1. This approach not make any alias() calls (no calls to instructionClobbersQuery), so the performance condition is enforced. The limit is set back to 0 if not used, as this provides info on the fact that we stopped before reaching a true clobber. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60479 llvm-svn: 358303
* [MemorySSA] Temporary fix assert when reaching 0 limit.Alina Sbirlea2019-03-291-2/+5
| | | | llvm-svn: 357327
* [MemorySSA] Limit clobber walks.Alina Sbirlea2019-03-291-21/+61
| | | | | | | | | | | | | | Summary: This patch limits all getClobberingMemoryAccess() walks to MaxCheckLimit. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D59569 llvm-svn: 357319
* Fix the build with GCC 4.8 after r356783Hans Wennborg2019-03-251-1/+1
| | | | llvm-svn: 356875
* [AliasAnalysis] Second prototype to cache BasicAA / anyAA state.Alina Sbirlea2019-03-221-70/+83
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Adding contained caching to AliasAnalysis. BasicAA is currently the only one using it. AA changes: - This patch is pulling the caches from BasicAAResults to AAResults, meaning the getModRefInfo call benefits from the IsCapturedCache as well when in "batch mode". - All AAResultBase implementations add the QueryInfo member to all APIs. AAResults APIs maintain wrapper APIs such that all alias()/getModRefInfo call sites are unchanged. - AA now provides a BatchAAResults type as a wrapper to AAResults. It keeps the AAResults instance and a QueryInfo instantiated to batch mode. It delegates all work to the AAResults instance with the batched QueryInfo. More API wrappers may be needed in BatchAAResults; only the minimum needed is currently added. MemorySSA changes: - All walkers are now templated on the AA used (AliasAnalysis=AAResults or BatchAAResults). - At build time, we optimize uses; now we create a local walker (lives only as long as OptimizeUses does) using BatchAAResults. - All Walkers have an internal AA and only use that now, never the AA in MemorySSA. The Walkers receive the AA they will use when built. - The walker we use for queries after the build is instantiated on AliasAnalysis and is built after building MemorySSA and setting AA. - All static methods doing walking are now templated on AliasAnalysisType if they are used both during build and after. If used only during build, the method now only takes a BatchAAResults. If used only after build, the method now takes an AliasAnalysis. Subscribers: sanjoy, arsenm, jvesely, nhaehnle, jlebar, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D59315 llvm-svn: 356783
* [MSSA] Delete move ctor; remove dynamic never-moved verificationGeorge Burgess IV2019-03-211-14/+0
| | | | | | | | | | | | | | | | Code archaeology in D59315 revealed that MSSA should never be moved. Rather than trying to check dynamically that this hasn't happened in the verify() functions of Walkers, it's likely best to just delete its move constructor. Since all these verify() functions did is check that MSSA hasn't moved, this allows us to remove these verify functions. I can readd the verification checks if someone's super concerned about us trying to `memcpy` MemorySSA or something somewhere, but I imagine we have other problems if we're trying anything like that... llvm-svn: 356641
* [MemorySSA] Remove redundant walker assignment [NFC].Alina Sbirlea2019-03-141-3/+1
| | | | | Subscribers: llvm-commits llvm-svn: 356189
* [MemorySSA] Remove verifyClobberSanity.Alina Sbirlea2019-02-111-29/+11
| | | | | | | | | | | | | | | | | | Summary: This verification may fail after certain transformations due to BasicAA's fragility. Added a small explanation and a testcase that triggers the assert in checkClobberSanity (before its removal). Addresses PR40509. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, llvm-commits, Prazek Tags: #llvm Differential Revision: https://reviews.llvm.org/D57973 llvm-svn: 353739
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [MemorySSA] Disable checkClobberSanity for SkipSelfWalker.Alina Sbirlea2019-01-101-1/+2
| | | | | | | | | Sanity will fail for this, since we're exploring getting a clobber further than the sanity check expects. Ideally we need to teach the sanity check to differentiate between the two walkers based on the SkipSelf bool in the query. llvm-svn: 350895
* [MemorySSA] Add SkipSelfWalker.Alina Sbirlea2019-01-071-1/+49
| | | | | | | | | | | | Summary: Add implementation of SkipSelfWalker. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D56285 llvm-svn: 350561
* [MemorySSA] Refactor CachingWalker.Alina Sbirlea2019-01-071-49/+95
| | | | | | | | | | | | | | Summary: Refactor caching walker to make creating a walker that skips the starting access strightforward. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits, jfb Differential Revision: https://reviews.llvm.org/D55957 llvm-svn: 350558
* [MemorySSA] Extend the clobber walker with the option to skip the starting ↵Alina Sbirlea2019-01-071-8/+19
| | | | | | | | | | | | | | | | | | | access. Summary: The option enables loop transformations to hoist accesses that do not have clobbers in the loop. If the clobber queries skips the starting access, the result may be outside the loop instead of the header Phi. Adding the walker that uses this option in a separate patch. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D55944 llvm-svn: 350551
* [CallSite removal] Migrate all Alias Analysis APIs to use the newlyChandler Carruth2019-01-071-18/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | minted `CallBase` class instead of the `CallSite` wrapper. This moves the largest interwoven collection of APIs that traffic in `CallSite`s. While a handful of these could have been migrated with a minorly more shallow migration by converting from a `CallSite` to a `CallBase`, it hardly seemed worth it. Most of the APIs needed to migrate together because of the complex interplay of AA APIs and the fact that converting from a `CallBase` to a `CallSite` isn't free in its current implementation. Out of tree users of these APIs can fairly reliably migrate with some combination of `.getInstruction()` on the `CallSite` instance and casting the resulting pointer. The most generic form will look like `CS` -> `cast_or_null<CallBase>(CS.getInstruction())` but in most cases there is a more elegant migration. Hopefully, this migrates enough APIs for users to fully move from `CallSite` to the base class. All of the in-tree users were easily migrated in that fashion. Thanks for the review from Saleem! Differential Revision: https://reviews.llvm.org/D55641 llvm-svn: 350503
* [MemorySSA] Create query after checking if instruction is a fence.Alina Sbirlea2018-11-131-2/+3
| | | | | | | The alternative is checking if I is a fence in the Query constructor, so as to not attempt to get a non-existent MemoryLocation. llvm-svn: 346798
* [cxx2a] Fix warning triggered by r343285Vitaly Buka2018-09-291-1/+0
| | | | llvm-svn: 343369
* API to update MemorySSA for cloned blocks and added CFG edges.Alina Sbirlea2018-09-101-15/+30
| | | | | | | | | | | | | | | | Summary: End goal is to update MemorySSA in all loop passes. LoopUnswitch clones all blocks in a loop. SimpleLoopUnswitch clones some blocks. LoopRotate clones some instructions. Some of these loop passes also make CFG changes. This is an API based on what I found needed in LoopUnswitch, SimpleLoopUnswitch, LoopRotate, LoopInstSimplify, LoopSimplifyCFG. Adding dependent patches using this API for context. Reviewers: george.burgess.iv, dberlin Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D45299 llvm-svn: 341855
* [MemorySSA] Relax verification of clobbering accesses.Alina Sbirlea2018-09-071-2/+12
| | | | llvm-svn: 341733
* [MemorySSA] Silence warning.Alina Sbirlea2018-08-291-0/+1
| | | | llvm-svn: 340995
* [MemorySSA] Fix checkClobberSanity to skip Start only for Defs and Uses.Alina Sbirlea2018-08-291-5/+10
| | | | llvm-svn: 340981
* [MemorySSA] Add expesive check for validating clobber accesses.Alina Sbirlea2018-08-291-11/+45
| | | | | | | | | | | | Summary: Add validation of clobber accesses as expensive check. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D51327 llvm-svn: 340951
* [MemorySSA] Add NDEBUG checks to verifiers; NFCGeorge Burgess IV2018-08-281-0/+4
| | | | | | | | verify*() methods are intended to have no side-effects (unless we detect broken MSSA, in which case they assert()), and all of the other verify methods are wrapped by `#ifndef NDEBUG`. llvm-svn: 340793
* [MemorySSA] Invalidate optimized Defs upon moving them; NFCGeorge Burgess IV2018-08-221-5/+14
| | | | | | | | | | | | | | | | | We're currently getting this behavior implicitly, since we determine if a Def's optimization is valid based on the ID of its defining access. This is incorrect, though I wouldn't be surprised if this was masked in part by that we're using a WeakVH to track what Defs are optimized to. (Not to mention that we don't move Defs super often, AFAICT). I'll submit a patch to fix this shortly. This also includes a minor refactor to reduce duplication a bit. No test is included, since like said, this already happens to be our behavior. I'll add a test for this with my fix to the other bug mentioned above. llvm-svn: 340461
* [MemorySSA] Move two simple getters; NFCGeorge Burgess IV2018-08-221-8/+0
| | | | | | | | We're calling these functions quite a bit from outside of MemorySSA.cpp now. Given that they're relatively simple one-liners, I think the style preference is to have them inline. llvm-svn: 340430
* [MemorySSA] Expose the verify as a debug option.Alina Sbirlea2018-08-151-3/+9
| | | | | | | | | | | | Summary: Expose VerifyMemorySSA as a debug option. If set, passes will call the MSSA->verifyMemorySSA() after calling into the updater's APIs when MemorySSA should be valid. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D50749 llvm-svn: 339795
* [MemorySSA] "Fix" lifetime intrinsic handlingGeorge Burgess IV2018-08-101-2/+7
| | | | | | | | | | | | | | | | | | | MemorySSA currently creates MemoryAccesses for lifetime intrinsics, and sometimes treats them as clobbers. This may/may not be the best way forward, but while we're doing it, we should consider MayAlias/PartialAlias to be clobbers. The ideal fix here is probably to remove all of this reasoning about lifetimes from MemorySSA + put it into the passes that need to care. But that's a wayyy broader fix that needs some consensus, and we have miscompiles + a release branch today, and this should solve the miscompiles just as well. differential revision is D43269. Landing without an explicit LGTM (and without using the special please-autoclose-this syntax) so we can still use that revision as a place to decide what the right fix here is. llvm-svn: 339411
* [MemorySSA] Add APIs to move memory accesses between blocks, following CFG ↵Alina Sbirlea2018-07-111-1/+11
| | | | | | | | | | | | | | | | changes. Summary: The move APIs added in this patch will be used to update MemorySSA when CFG changes merge or split blocks, by moving memory accesses accordingly in MemorySSA's internal data structures. [Split from D45299 for easier review] Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48897 llvm-svn: 336860
* [MemorySSA] Add APIs to MemoryPhis to delete incoming blocks/values, and an ↵Alina Sbirlea2018-06-291-3/+6
| | | | | | | | | | | | | | | | updater API to remove blocks. Summary: MemoryPhis now have APIs analogous to BB Phis to remove an incoming value/block. The MemorySSAUpdater uses the above APIs when updating MemorySSA given a set of dead blocks about to be deleted. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48396 llvm-svn: 336015
* [MSSA] Add domination number verifier; NFCGeorge Burgess IV2018-06-251-0/+39
| | | | | | | | | | | It's easy for domination numbers to get out-of-date, and this is no more costly than any of the other verifiers we already have, so it seems nice to have. A stage3 build with this Works On My Machine, so this hasn't caught any bugs... yet. :) llvm-svn: 335444
* [MSSA] Remove incorrect comment + `auto`ify dyn_cast results; NFCGeorge Burgess IV2018-06-221-6/+5
| | | | llvm-svn: 335399
* [MemorySSA] Verify Phi incoming blocks are block predecessors.Alina Sbirlea2018-06-201-1/+5
| | | | | | | | | | | | Summary: Make the MemorySSA verify also check that all Phi incoming blocks are block predecessors. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D48333 llvm-svn: 335174
* [MSSA] Print more optimization informationGeorge Burgess IV2018-06-141-5/+20
| | | | | | | | | | | | | | In particular, when asked to print a MemoryAccess, we'll now print where defs are optimized to, and we'll print optimized access types. This patch also introduces an operator<< to make printing AliasResults easier. Patch by Juneyoung Lee! Differential Revision: https://reviews.llvm.org/D47860 llvm-svn: 334760
* [MemorySSA] Reflow comments + clean up control flow; NFCGeorge Burgess IV2018-05-261-2/+2
| | | | | | | Style guide says `else`s after returns are iffy, and I agree. I also don't know what broke the comments here and in CFLAA, but *shrug*. llvm-svn: 333332
* [MemorySSA] Don't sort IDF blocks.Michael Zolotukhin2018-05-151-11/+2
| | | | | | | | | | | | | | | | Summary: After r332167 we started to sort the IDF blocks inside IDF calculation, so there is no need to re-sort them on the user site. The test changes are due to a slightly different order we're using now (originally we used DFSInNumber and now the blocks are sorted by a pair (LevelFromRoot, DFSInNumber)). Reviewers: dberlin, mgrang Subscribers: Prazek, hiraditya, george.burgess.iv, llvm-commits Differential Revision: https://reviews.llvm.org/D46899 llvm-svn: 332385
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-12/+13
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Rename invariant.group.barrier to launder.invariant.groupPiotr Padlewski2018-05-031-3/+0
| | | | | | | | | | | | | | Summary: This is one of the initial commit of "RFC: Devirtualization v2" proposal: https://docs.google.com/document/d/16GVtCpzK8sIHNc2qZz6RN8amICNBtvjWUod2SujZVEo/edit?usp=sharing Reviewers: rsmith, amharc, kuhar, sanjoy Subscribers: arsenm, nhaehnle, javed.absar, hiraditya, llvm-commits Differential Revision: https://reviews.llvm.org/D45111 llvm-svn: 331448
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-15/+15
| | | | | | | | | | | | | | | | We've been running doxygen with the autobrief option for a couple of years now. This makes the \brief markers into our comments redundant. Since they are a visual distraction and we don't want to encourage more \brief markers in new code either, this patch removes them all. Patch produced by for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done Differential Revision: https://reviews.llvm.org/D46290 llvm-svn: 331272
* IWYU for llvm-config.h in llvm, additions.Nico Weber2018-04-301-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | See r331124 for how I made a list of files missing the include. I then ran this Python script: for f in open('filelist.txt'): f = f.strip() fl = open(f).readlines() found = False for i in xrange(len(fl)): p = '#include "llvm/' if not fl[i].startswith(p): continue if fl[i][len(p):] > 'Config': fl.insert(i, '#include "llvm/Config/llvm-config.h"\n') found = True break if not found: print 'not found', f else: open(f, 'w').write(''.join(fl)) and then looked through everything with `svn diff | diffstat -l | xargs -n 1000 gvim -p` and tried to fix include ordering and whatnot. No intended behavior change. llvm-svn: 331184
* [MemorySSA] remove cruft; NFC.George Burgess IV2018-04-091-23/+1
| | | | | | | | | | | | The caching walker used to hold its own caches, which made its `reset()` function meaningful. Since caching has been moved out of it, there's no reason to continue to have these cache-related methods. Similarly, the EXPENSIVE_CHECKS block that's getting removed used to rerun the query with caching disabled. Since that's how we always do queries now, it's redundant. llvm-svn: 329638
* [MemorySSA] Remove redundant assert; NFCGeorge Burgess IV2018-04-091-3/+0
| | | | | | | The `if (!Def && !Use) return nullptr;` right above this assert sort of defeats the purpose. llvm-svn: 329632
* [MemorySSA] Fix spelling errors in MemorySSA.cpp. NFCZhaoshi Zheng2018-04-041-2/+2
| | | | llvm-svn: 329230
* [Analysis] Change std::sort to llvm::sort in response to r327219Mandeep Singh Grang2018-04-011-4/+4
| | | | | | | | | | | | | | | | | | | | | | Summary: r327219 added wrappers to std::sort which randomly shuffle the container before sorting. This will help in uncovering non-determinism caused due to undefined sorting order of objects having the same key. To make use of that infrastructure we need to invoke llvm::sort instead of std::sort. Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort. Refer D44363 for a list of all the required patches. Reviewers: sanjoy, dexonsmith, hfinkel, RKSimon Reviewed By: dexonsmith Subscribers: david2050, llvm-commits Differential Revision: https://reviews.llvm.org/D44944 llvm-svn: 328925
* [MemorySSA] Turn an assert into a conditionGeorge Burgess IV2018-03-291-2/+2
| | | | | | | | | | | | Eli pointed out that variadic functions are totally a thing, so this assert is incorrect. No test-case is provided, since the only way this assert fires is if a specific DenseMap falls back to doing `isEqual` checks, and that seems fairly brittle (and requires a pyramid of growing `call void (i8, ...) @varargs(i8 0)`). llvm-svn: 328755
* [MemorySSA] Consider callsite args for hashing and equality.George Burgess IV2018-03-291-9/+20
| | | | | | | | | | | | | | We use a `DenseMap<MemoryLocOrCall, MemlocStackInfo>` to keep track of prior work when optimizing uses in MemorySSA. Because we weren't accounting for callsite arguments in either the hash code or equality tests for `MemoryLocOrCall`s, we optimized uses too aggressively in some rare cases. Fix by Daniel Berlin. Should fix PR36883. llvm-svn: 328748
* [MemorySSA] Fix comment + remove redundant dyn_casts; NFCGeorge Burgess IV2018-03-111-18/+12
| | | | | | StartingAccess is already a MemoryUseOrDef. llvm-svn: 327235
OpenPOWER on IntegriCloud