aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/MemorySSAUpdater.cpp
AgeCommit message (Collapse)AuthorFilesLines
2025-05-10[MemorySSAUpdater] Fix iterator invalidation bug in `applyInsertUpdates` ↵Yingwei Zheng1-1/+7
(#139370) This patch defers resetting optimized accesses until all uses are replaced, to avoid invalidating the iterator. Closes https://github.com/llvm/llvm-project/issues/139103. Closes https://github.com/llvm/llvm-project/issues/139289. Closes https://github.com/llvm/llvm-project/issues/139308.
2025-04-27[llvm] Use range constructors of *Set (NFC) (#137552)Kazu Hirata1-2/+2
2025-03-28[llvm] Use range constructors of *Set (NFC) (#133549)Kazu Hirata1-3/+3
2025-03-25[Analysis] Use *Set::insert_range (NFC) (#132878)Kazu Hirata1-3/+2
We can use *Set::insert_range to collapse: for (auto Elem : Range) Set.insert(E); down to: Set.insert_range(Range); In some cases, we can further fold that into the set declaration.
2024-12-09[MemorySSA] Handle MemoryDef optimized away during cloning (#117883)Nikita Popov1-29/+39
When determining the replacement access during cloning, we currently leave accesses for instructions that are not in the VMap alone. This is correct if the instruction is not in VMap because it hasn't been cloned, but not if it has been cloned and then removed. In that case, we should walk up to the defining access, like in other simplification cases. To distinguish the two cases, pass in a callback that queries whether the instruction is part of the cloned region. An alternative to this would be to delay removal of dead instructions in SimpleLoopUnswitch until after MSSA cloning. Fixes https://github.com/llvm/llvm-project/issues/116228.
2024-11-20[LICM] allow MemoryAccess creation failure (#116813)DianQK1-3/+5
Fixes #116809. After running some passes (SimpleLoopUnswitch, LoopInstSimplify, etc.), MemorySSA might be outdated, and the instruction `I` may have become a non-memory touching instruction. LICM has already handled this, but it does not pass `CreationMustSucceed=false` to `createDefinedAccess`.
2024-01-24[MSSAUpdater] Handle simplified accesses when updating phis (#78272)Nikita Popov1-19/+3
This is a followup to #76819. After those changes, we can still run into an assertion failure for a slight variation of the test case: When fixing up MemoryPhis, we map the incoming access to the access of the cloned instruction -- which may now no longer exist. Fix this by reusing the getNewDefiningAccessForClone() helper, which will look upwards for a new defining access in that case.
2024-01-08[MSSA] Don't require clone creation to succeed (#76819)Nikita Popov1-13/+4
Sometimes, we create a MemoryAccess for an instruction, which is later simplified (e.g. via devirtualization) such that the new instruction has no memory effects anymore. If we later clone the instruction (e.g. during unswitching), then MSSA will not create a MemoryAccess for the new instruction, triggering an assert. Disable the assertion (by passing CreationMustSucceed=false) and adjust getDefiningAccessForClone() to work correctly in that case. This PR implements the alternative suggestion by alinas from https://github.com/llvm/llvm-project/pull/76142.
2022-07-16[Analysis] Qualify auto variables in for loops (NFC)Kazu Hirata1-8/+8
2022-03-31Fix MemorySSAUpdater::insertDef for dead codeArtur Pilipenko1-3/+9
Fix for https://github.com/llvm/llvm-project/issues/51257. Differential Revision: https://reviews.llvm.org/D122601
2022-03-01Cleanup includes: LLVMAnalysisserge-sans-paille1-8/+1
Number of lines output by preprocessor: before: 1065940348 after: 1065307662 Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup Differential Revision: https://reviews.llvm.org/D120659
2022-02-18[MemorySSA] Clear VisitedBlocks per queryWhitney Tsang1-0/+2
The problem can be shown from the newly added test case. There are two invocations to MemorySSAUpdater::moveToPlace, and the internal data structure VisitedBlocks is changed in the first invocation, and reused in the second invocation. In between the two invocations, there is a change to the CFG, and MemorySSAUpdater is notified about the change. Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D119898
2021-11-18[llvm] Use range-based for loops (NFC)Kazu Hirata1-3/+2
2021-11-05[llvm] Use make_early_inc_range (NFC)Kazu Hirata1-5/+1
2021-09-19[llvm] Use pop_back_val (NFC)Kazu Hirata1-2/+1
2021-09-01[MemorySSAUpdater] Simplify updates when only deleting edges.Alina Sbirlea1-17/+22
When performing only edge deletion, we don't need to do the DT updates back and forth. Check for the existance of insert updates to simplify this.
2021-07-10[Analysis] Remove changeCondBranchToUnconditionalTo (NFC)Kazu Hirata1-16/+0
The last use was removed on Jan 21, 2021 in commit 0895b836d74ed333468ddece2102140494eb33b6.
2021-04-09[MSSA] Rename uses in IDF regardless of new def position in basic block.Alina Sbirlea1-8/+5
When inserting a new def and renaming of uses is asked, always compute IDF and do the renaming for the blocks with Phis in that IDF. Resolves PR49859. Differential Revision: https://reviews.llvm.org/D100163
2021-02-22[Analysis] Use range-based for loops (NFC)Kazu Hirata1-5/+3
2021-01-06[DominatorTree] Add support for mixed pre/post CFG views.Alina Sbirlea1-5/+12
Add support for mixed pre/post CFG views. Update usages of the MemorySSAUpdater to use the new DT API by requesting the DT updates to be done by the MSSAUpdater. Differential Revision: https://reviews.llvm.org/D93371
2020-12-29[MSSAUpdater] Skip renaming when inserting def in unreachable block.Florian Hahn1-3/+4
This fixes a updater crash when moving memory defs between unreachable blocks. Fixes PR48616.
2020-09-16[MemorySSA] Rename uses in blocks with Phis.Alina Sbirlea1-0/+12
Renaming should include blocks with existing Phis. Resolves PR45927. Differential Revision: https://reviews.llvm.org/D87661
2020-09-01[MemorySSA] Update phi map with replacement value.Alina Sbirlea1-2/+2
2020-08-31[MemorySSA] Clean up single value phis.Alina Sbirlea1-14/+18
MemoryPhis with a single value are correct, but can lead to errors when updating. Clean up single entry Phis newly added when cloning blocks. Resolves PR46574.
2020-08-21[DomTree] Extend update API to allow a post CFG view.Alina Sbirlea1-10/+18
Extend the `applyUpdates` in DominatorTree to allow a post CFG view, different from the current CFG. This patch implements the functionality of updating an already up to date DT, to the desired PostCFGView. Combining a set of updates towards an up to date DT and a PostCFGView is not yet supported. Differential Revision: https://reviews.llvm.org/D85472
2020-08-01Use llvm::is_contained where appropriate (NFC)Kazu Hirata1-2/+1
Use llvm::is_contained where appropriate (NFC) Reviewed By: kazu Differential Revision: https://reviews.llvm.org/D85083
2020-07-27[GraphDiff] Use class method getChildren instead of GraphTraits.Alina Sbirlea1-7/+4
Summary: Use getChildren() method in GraphDiff instead of GraphTraits. This simplifies the code and allows for refactorigns inside GraphDiff. All usecase need not have a light-weight/copyable range. Clean GraphTraits implementation. Reviewers: dblaikie Subscribers: hiraditya, llvm-commits, george.burgess.iv Tags: #llvm Differential Revision: https://reviews.llvm.org/D84562
2020-06-05MemorySSAUpdater.h - reduce unnecessary includes to forward declarations. NFC.Simon Pilgrim1-0/+2
Remove unnecessary MemoryAccess forward declaration as its already included from MemorySSA.h Move implicit include dependencies down to source files.
2020-04-03[GraphDiff] Extend GraphDiff to track a list of updates.Alina Sbirlea1-6/+6
Summary: This patch includes two extensions: 1. It extends the GraphDiff to also keep the original list of updates after legalization, not just the deletes/insert vectors. It also provides an API to pop the first update (the updates are store in reverse, such that the first update is at the end of the list) 2. It adds a bool to mark whether the given updates should be applied as given, or applied in reverse. This moves the task of reversing the updates (when the caller needs this) to a functionality inside GraphDiff, versus having the caller do this. The two changes could be split into two patches, but they seemed reasonably small to be reviewed together. Reviewers: kuhar, dblaikie Subscribers: hiraditya, george.burgess.iv, mgrang, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D77167
2019-11-20[MemorySSA] Moving at the end often means before terminator.Alina Sbirlea1-1/+7
Moving accesses in MemorySSA at InsertionPlace::End, when an instruction is moved into a block, almost always means insert at the end of the block, but before the block terminator. This matters when the block terminator is a MemoryAccess itself (an invoke), and the insertion must be done before the terminator for the update to be correct. Insert an additional position: InsertionPlace:BeforeTerminator and update current usages where this applies. Resolves PR44027.
2019-10-10[MemorySSA] Update Phi simplification.Alina Sbirlea1-5/+12
When simplifying a Phi to the unique value found incoming, check that there wasn't a Phi already created to break a cycle. If so, remove it. Resolves PR43541. Some additional nits included. llvm-svn: 374471
2019-10-10[MemorySSA] Additional handling of unreachable blocks.Alina Sbirlea1-0/+4
Summary: Whenever we get the previous definition, the assumption is that the recursion starts ina reachable block. If the recursion starts in an unreachable block, we may recurse indefinitely. Handle this case by returning LoE if the block is unreachable. Resolves PR43426. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68809 llvm-svn: 374447
2019-10-09[MemorySSA] Make the use of moveAllAfterMergeBlocks consistent.Alina Sbirlea1-15/+22
Summary: The rule for the moveAllAfterMergeBlocks API si for all instructions from `From` to have been moved to `To`, while keeping the CFG edges (and block terminators) unchanged. Update all the callsites for moveAllAfterMergeBlocks to follow this. Pending follow-up: since the same behavior is needed everytime, merge all callsites into one. The common denominator may be the call to `MergeBlockIntoPredecessor`. Resolves PR43569. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D68659 llvm-svn: 374177
2019-10-02[MemorySSA] Update Phi creation when inserting a Def.Alina Sbirlea1-37/+40
MemoryPhis should be added in the IDF of the blocks newly gaining Defs. This includes the blocks that gained a Phi and the block gaining a Def, if the block did not have one before. Resolves PR43427. llvm-svn: 373505
2019-10-02MemorySSAUpdater::applyInsertUpdates - silence static analyzer ↵Simon Pilgrim1-1/+1
dyn_cast<MemoryAccess> null dereference warning. NFCI. The static analyzer is warning about a potential null dereference, but we should be able to use cast<MemoryAccess> directly and if not assert will fire for us. llvm-svn: 373467
2019-10-01[MemorySSA] Check for unreachable blocks when getting last definition.Alina Sbirlea1-0/+3
If a single predecessor is found, still check if the block is unreachable. The test that found this had a self loop unreachable block. Resolves PR43493. llvm-svn: 373383
2019-10-01[MemorySSA] Update last_access_in_block check.Alina Sbirlea1-2/+7
The check for "was there an access in this block" should be: is the last access in this block and is it not a newly inserted phi. Resolves new test in PR43438. Also fix a typo when simplifying trivial Phis to match the comment. llvm-svn: 373380
2019-09-25[MemorySSA] Avoid adding Phis in the presence of unreachable blocks.Alina Sbirlea1-45/+57
Summary: If a block has all incoming values with the same MemoryAccess (ignoring incoming values from unreachable blocks), then use that incoming MemoryAccess and do not create a Phi in the first place. Revert IDF work-around added in rL372673; it should not be required unless the Def inserted is the first in its block. The patch also cleans up a series of tests, added during the many iterations on insertDef. The patch also fixes PR43438. The same issue that occurs in insertDef with "adding phis, hence the IDF of Phis is needed", can also occur in fixupDefs: the `getPreviousRecursive` call only adds Phis walking on the predecessor edges, which means there may be the case of a Phi added walking the CFG "backwards" which triggers the needs for an additional Phi in successor blocks. Such Phis are added during fixupDefs only in the presence of unreachable blocks. Hence this highlights the need to avoid adding Phis in blocks with unreachable predecessors in the first place. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67995 llvm-svn: 372932
2019-09-23[MemorySSA] Update Phi insertion.Alina Sbirlea1-43/+39
Summary: MemoryPhis may be needed following a Def insertion inthe IDF of all the new accesses added (phis + potentially a def). Ensure this also occurs when only the new MemoryPhis are the defining accesses. Note: The need for computing IDF here is because of new Phis added with edges incoming from unreachable code, Phis that had previously been simplified. The preferred solution is to not reintroduce such Phis. This patch is the needed fix while working on the preferred solution. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67927 llvm-svn: 372673
2019-09-17[MemorySSA] Fix phi insertion when inserting a def.Alina Sbirlea1-0/+3
Summary: When inserting a Def, the current algorithm is walking edges backward and inserting new Phis where needed. There may be additional Phis needed in the IDF of the newly inserted Def and Phis. Adding Phis in the IDF of the Def was added ina previous patch, but we may also need other Phis in the IDF of the newly added Phis. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D67637 llvm-svn: 372138
2019-08-27[MemorySSA] Fix insertUse.Alina Sbirlea1-5/+5
Actually call the renamePass on inserted Phis. Fixes PR42940. Subscribers: llvm-commits llvm-svn: 369997
2019-08-20[MemorySSA] Make Phi cleanups consistent.Alina Sbirlea1-24/+17
Summary: Make Phi cleanups consistent: remove self as a trivial Phi and recurse to potentially remove other trivial phis. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66454 llvm-svn: 369466
2019-08-20[MemorySSA] Fix existing phis when inserting defs.Alina Sbirlea1-8/+12
Summary: When inserting a new Def, and inserting Phis in the IDF when needed, also mark the already existing Phis in the IDF as non-optimized, since these may need fixing as well. In the test attached, there is a Phi in the IDF that happens to be trivial, and is wrongfully removed by the call to getLastDef that follows. This is a valid situation and the existing IDF Phis need to marked as "may need fixing" as well. Resolves PR43044. Reviewers: george.burgess.iv Subscribers: Prazek, sanjoy.google, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D66495 llvm-svn: 369464
2019-08-19[MemorySSA] Rename uses when inserting memory uses.Alina Sbirlea1-6/+37
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
2019-08-01[IR] Value: add replaceUsesWithIf() utilityRoman Lebedev1-7/+4
Summary: While there is always a `Value::replaceAllUsesWith()`, sometimes the replacement needs to be conditional. I have only cleaned a few cases where `replaceUsesWithIf()` could be used, to both add test coverage, and show that it is actually useful. Reviewers: jdoerfert, spatel, RKSimon, craig.topper Reviewed By: jdoerfert Subscribers: dschuff, sbc100, jgravelle-google, hiraditya, aheejin, george.burgess.iv, asbirlea, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D65528 llvm-svn: 367548
2019-07-31[MemorySSA] Add additional verification for phis.Alina Sbirlea1-1/+1
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
2019-07-30[MemorySSA] Extend allowed behavior for simplified instructions.Alina Sbirlea1-22/+44
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
2019-07-12[MemorySSA] Use SetVector to avoid nondeterminism.Alina Sbirlea1-1/+1
Summary: Use a SetVector for DeadBlockSet. Resolves PR42574. Reviewers: george.burgess.iv, uabelho, dblaikie Subscribers: jlebar, Prazek, mgrang, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64601 llvm-svn: 365970
2019-06-19[MemorySSA] Cleanup trivial phis.Alina Sbirlea1-5/+8
Summary: This is unfortunately needed for correctness, if we are to extend the tolerance of the update API to the way simple loop unswitch is doing cloning. In simple loop unswitch (as opposed to loop unswitch), not all blocks are cloned. This can create unreachable cloned blocks (no predecessor), which are later cleaned up. In MemorySSA, the APIs for supporting these kind of updates (clone + update exit blocks), make certain assumption on the integrity of the CFG. When cloning, if something was not cloned, it's values in MemorySSA default to LiveOnEntry. When updating exit blocks, it is safe to assume that we can first insert phis in the blocks merging two clones, then add additional phis in the IDF of the blocks that received phis. This no longer holds true if one of the clones being merged comes from an unreachable block. We'd conservatively need to add all phis before filling in their incoming definitions. In practice this restriction can be relaxed if we clean up trivial phis after the first round of insertion. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63354 llvm-svn: 363880
2019-06-19[MemorySSA] Use GraphDiff info when computing IDF.Alina Sbirlea1-1/+1
Summary: When computing IDF for insert updates, ensure we use the snapshot CFG offered by GraphDiff. Caught by D63389. Reviewers: kuhar, george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits, Szelethus Tags: #llvm Differential Revision: https://reviews.llvm.org/D63443 llvm-svn: 363879
generated by cgit v1.1 at 2025-08-03 03:39:35 +0000