summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemorySSA.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [MemorySSA] Don't verify MemorySSA unless VerifyMemorySSA enabledNikita Popov2020-02-271-1/+4
| | | | | | | | | | | MemorySSA is often taking up an unreasonable fraction of runtime in assertion enabled builds. Turns out that there is one code-path that runs verifyMemorySSA() even if VerifyMemorySSA is not enabled. This patch makes it conditional as well. Differential Revision: https://reviews.llvm.org/D74505 (cherry picked from commit f0b57d8071853ec2ab459c0492854c67ea4fa93c)
* [MemorySSA] Combine verifications.Alina Sbirlea2019-11-251-61/+40
| | | | | | | | | | | | | | | | | | | Summary: Combine three verification methods into one to improve compile time when asserts are enabled. Motivated by PR44066. Sample change of timings on testcase in PR44066 (release+asserts): MSSA off or verification disabled: 1.13s. MSSA on (ToT): 2.48s. With patch: 2.03s. With enabling DefUses after combining Domination+Ordering: 2.6s. After also combining DefUses with Domination+Ordering: 2.06s (candidate to be taken out of EXPENSIVE_CHECKS). Subscribers: Prazek, hiraditya, george.burgess.iv, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D70618
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [MemorySSA] Fixed null check after dereferencing warning. NFCI.Dávid Bolvanský2019-11-031-0/+1
|
* MemorySSA tryOptimizePhi - assert that we've found a DefChainEnd. NFCI.Simon Pilgrim2019-10-021-0/+1
| | | | | | Silences static analyzer null dereference warning. llvm-svn: 373466
* [MemorySSA] Update MSSA for non-conventional AA.Alina Sbirlea2019-09-171-1/+7
| | | | | | | | | | | | | | | | | | | Summary: Regularly when moving an instruction that may not read or write memory, the instruction is not modelled in MSSA, so not action is necessary. For a non-conventional AA pipeline, MSSA needs to explicitly check when creating accesses, so as to not model instructions that may not read and write memory. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67562 llvm-svn: 372137
* [MemorySSA] Do not create memoryaccesses for debug info intrinsics.Alina Sbirlea2019-09-101-2/+9
| | | | | | | | | | | | | | | | Summary: Do not model debuginfo intrinsics in MemorySSA. Regularly these are non-memory modifying instructions. With -disable-basicaa, they were being modelled as Defs. Reviewers: george.burgess.iv Subscribers: aprantl, Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67307 llvm-svn: 371565
* [MemorySSA] Re-enable MemorySSA use.Alina Sbirlea2019-09-041-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D58311 llvm-svn: 370957
* [NFC] Switch last couple of invariant_load checks to use hasMetadataPhilip Reames2019-09-041-1/+1
| | | | llvm-svn: 370948
* [MemorySSA] Move two verify calls under expensive checks.Alina Sbirlea2019-09-041-2/+2
| | | | llvm-svn: 370831
* [MemorySSA] Disable MemorySSA use.Alina Sbirlea2019-09-031-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D58311 llvm-svn: 370821
* [MemorySSA] Re-enable MemorySSA use.Alina Sbirlea2019-09-031-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D58311 llvm-svn: 370811
* [MemorySSA] Rename all phi entries.Alina Sbirlea2019-08-301-3/+8
| | | | | | | When renaming Phis incoming values, there may be multiple edges incoming from the same block (switch). Rename all. llvm-svn: 370548
* Revert enabling MemorySSA.Alina Sbirlea2019-08-291-1/+1
| | | | | | | | Breaks sanitizers bots. Differential Revision: https://reviews.llvm.org/D58311 llvm-svn: 370397
* [MemorySSA & LoopPassManager] Enable MemorySSA as loop dependency. Update tests.Alina Sbirlea2019-08-291-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: I'm not planning to check this in at the moment, but feedback is very welcome, in particular how this affects performance. The feedback obtains here will guide the next steps towards enabling this. This patch enables the use of MemorySSA in the loop pass manager. Passes that currently use MemorySSA: - EarlyCSE Passes that use MemorySSA after this patch: - EarlyCSE - LICM - SimpleLoopUnswitch Loop passes that update MemorySSA (and do not use it yet, but could use it after this patch): - LoopInstSimplify - LoopSimplifyCFG - LoopUnswitch - LoopRotate - LoopSimplify - LCSSA Loop passes that do *not* update MemorySSA: - IndVarSimplify - LoopDelete - LoopIdiom - LoopSink - LoopUnroll - LoopInterchange - LoopUnrollAndJam - LoopVectorize - LoopReroll - IRCE Reviewers: chandlerc, george.burgess.iv, davide, sanjoy, gberry Subscribers: jlebar, Prazek, dmgreen, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58311 llvm-svn: 370384
* [MemorySSA] Rename uses when inserting memory uses.Alina Sbirlea2019-08-191-8/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When inserting uses from outside the MemorySSA creation, we don't normally need to rename uses, based on the assumption that there will be no inserted Phis (if Def existed that required a Phi, that Phi already exists). However, when dealing with unreachable blocks, MemorySSA will optimize away Phis whose incoming blocks are unreachable, and these Phis end up being re-added when inserting a Use. There are two potential solutions here: 1. Analyze the inserted Phis and clean them up if they are unneeded (current method for cleaning up trivial phis does not cover this) 2. Leave the Phi in place and rename uses, the same way as whe inserting defs. This patch use approach 2. Resolves first test in PR42940. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66033 llvm-svn: 369291
* [MemorySSA] Remove restrictive asserts.Alina Sbirlea2019-08-151-4/+1
| | | | | | | | | The verification I added has overly restrictive asserts. Unreachable blocks can have any incoming value in practice, after an update due to a "replaceAllUses" call when the repalced entry is LiveOnEntry. llvm-svn: 369050
* [llvm] Migrate llvm::make_unique to std::make_uniqueJonas Devlieghere2019-08-151-7/+7
| | | | | | | | Now that we've moved to C++14, we no longer need the llvm::make_unique implementation from STLExtras.h. This patch is a mechanical replacement of (hopefully) all the llvm::make_unique instances across the monorepo. llvm-svn: 369013
* [MemorySSA] Add additional verification for phis.Alina Sbirlea2019-07-311-0/+42
| | | | | | | | | | | | | | | | | | Summary: Verify that the incoming defs into phis are the last defs from the respective incoming blocks. When moving blocks, insertDef must RenameUses. Adding this verification makes GVNHoist tests fail that uncovered this issue. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63147 llvm-svn: 367451
* [MemorySSA] Extend allowed behavior for simplified instructions.Alina Sbirlea2019-07-301-5/+7
| | | | | | | | | | | | | | | | Summary: LoopRotate may simplify instructions, leading to the new instructions not having memory accesses created for them. Allow this behavior, by allowing the new access to be null when the template is null, and looking upwards for the proper defined access when dealing with simplified instructions. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65338 llvm-svn: 367352
* [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
OpenPOWER on IntegriCloud