summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/MemorySSAUpdater.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [MemorySSA] Moving at the end often means before terminator.Alina Sbirlea2019-11-201-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.
* [MemorySSA] Update Phi simplification.Alina Sbirlea2019-10-101-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
* [MemorySSA] Additional handling of unreachable blocks.Alina Sbirlea2019-10-101-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
* [MemorySSA] Make the use of moveAllAfterMergeBlocks consistent.Alina Sbirlea2019-10-091-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
* [MemorySSA] Update Phi creation when inserting a Def.Alina Sbirlea2019-10-021-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
* MemorySSAUpdater::applyInsertUpdates - silence static analyzer ↵Simon Pilgrim2019-10-021-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
* [MemorySSA] Check for unreachable blocks when getting last definition.Alina Sbirlea2019-10-011-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
* [MemorySSA] Update last_access_in_block check.Alina Sbirlea2019-10-011-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
* [MemorySSA] Avoid adding Phis in the presence of unreachable blocks.Alina Sbirlea2019-09-251-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
* [MemorySSA] Update Phi insertion.Alina Sbirlea2019-09-231-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
* [MemorySSA] Fix phi insertion when inserting a def.Alina Sbirlea2019-09-171-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
* [MemorySSA] Fix insertUse.Alina Sbirlea2019-08-271-5/+5
| | | | | | | | Actually call the renamePass on inserted Phis. Fixes PR42940. Subscribers: llvm-commits llvm-svn: 369997
* [MemorySSA] Make Phi cleanups consistent.Alina Sbirlea2019-08-201-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
* [MemorySSA] Fix existing phis when inserting defs.Alina Sbirlea2019-08-201-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
* [MemorySSA] Rename uses when inserting memory uses.Alina Sbirlea2019-08-191-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
* [IR] Value: add replaceUsesWithIf() utilityRoman Lebedev2019-08-011-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
* [MemorySSA] Add additional verification for phis.Alina Sbirlea2019-07-311-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
* [MemorySSA] Extend allowed behavior for simplified instructions.Alina Sbirlea2019-07-301-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
* [MemorySSA] Use SetVector to avoid nondeterminism.Alina Sbirlea2019-07-121-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
* [MemorySSA] Cleanup trivial phis.Alina Sbirlea2019-06-191-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
* [MemorySSA] Use GraphDiff info when computing IDF.Alina Sbirlea2019-06-191-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
* [MemorySSA] Don't use template when the clone is a simplified instruction.Alina Sbirlea2019-06-171-3/+11
| | | | | | | | | | | | | | | | | | | Summary: LoopRotate doesn't create a faithful clone of an instruction, it may simplify it beforehand. Hence the clone of an instruction that has a MemoryDef associated may not be a definition, but a use or not a memory alternig instruction. Don't rely on the template when the clone may be simplified. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63355 llvm-svn: 363597
* [MemorySSA] Add all MemoryPhis before filling their values.Alina Sbirlea2019-06-171-3/+13
| | | | | | | | | | | | | | | | | | Summary: Add all MemoryPhis in IDF before filling in their incomign values. Otherwise, a new Phi can be added that needs to become the incoming value of another Phi. Test fails the verification in verifyPrevDefInPhis. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, zzheng, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63353 llvm-svn: 363590
* [MemorySSA] When applying updates, clean unnecessary Phis.Alina Sbirlea2019-06-111-1/+4
| | | | | | | | | | | | | | Summary: After applying a set of insert updates, there may be trivial Phis left over. Clean them up. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D63033 llvm-svn: 363094
* [MemorySSA] Teach LoopSimplify to preserve MemorySSA.Alina Sbirlea2019-05-081-2/+79
| | | | | | | | | | | | | | | Summary: Preserve MemorySSA in LoopSimplify, in the old pass manager, if the analysis is available. Do not preserve it in the new pass manager. Update tests. Subscribers: nemanjai, jlebar, javed.absar, Prazek, kbarton, zzheng, jsji, llvm-commits, george.burgess.iv, chandlerc Tags: #llvm Differential Revision: https://reviews.llvm.org/D60833 llvm-svn: 360270
* [MemorySSA] Check that block is reachable when adding phis.Alina Sbirlea2019-05-021-1/+4
| | | | | | | | | | | | | | | | | | | 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] Refactor removing multiple trivial phis [NFC].Alina Sbirlea2019-05-021-6/+11
| | | | | | | | | | | | | | Summary: Create a method to clean up multiple potentially trivial phis, since we will need this often. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D61471 llvm-svn: 359842
* [MemorySSA] Add previous def to cache when found, even if trivial.Alina Sbirlea2019-04-121-1/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When inserting a new Def, MemorySSA may be have non-minimal number of Phis. While inserting, the walk to find the previous definition may cleanup minimal Phis. When the last definition is trivial to obtain, we do not cache it. It is possible while getting the previous definition for a Def to get two different answers: - one that was straight-forward to find when walking the first path (a trivial phi in this case), and - another that follows a cleanup of the trivial phi, it determines it may need additional Phi nodes, it inserts them and returns a new phi in the same position as the former trivial one. While the Phis added for the second path are all redundant, they are not complete (the walk is only done upwards), and they are not properly cleaned up afterwards. A way to fix this problem is to cache the straight-forward answer we got on the first walk. The caching is only kept for the duration of a getPreviousDef call, and for Phis we use TrackingVH, so removing the trivial phi will lead to replacing it with the next dominating phi in the cache. Resolves PR40749. Reviewers: george.burgess.iv Subscribers: jlebar, Prazek, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D60634 llvm-svn: 358313
* [MemorySSA] Don't optimize incomplete phis.Alina Sbirlea2019-03-291-2/+9
| | | | | | | | | | | | | | | | Summary: MemoryPhis cannot be optimized out until they are complete. Resolves PR41254. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D59966 llvm-svn: 357315
* [MemorySSA] Make insertDef insert corresponding phi nodes.Alina Sbirlea2019-02-271-0/+54
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The original assumption for the insertDef method was that it would not materialize Defs out of no-where, hence it will not insert phis needed after inserting a Def. However, when cloning an instruction (use case used in LICM), we do materialize Defs "out of no-where". If the block receiving a Def has at least one other Def, then no processing is needed. If the block just received its first Def, we must check where Phi placement is needed. The only new usage of insertDef is in LICM, hence the trigger for the bug. But the original goal of the method also fails to apply for the move() method. If we move a Def from the entry point of a diamond to either the left or right blocks, then the merge block must add a phi. While this usecase does not currently occur, or may be viewed as an incorrect transformation, MSSA must behave corectly given the scenario. Resolves PR40749 and PR40754. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, jdoerfert, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58652 llvm-svn: 355040
* [NFC] fix trivial typos in commentsHiroshi Inoue2019-02-051-2/+2
| | | | llvm-svn: 353147
* [MemorySSA] Extend removeMemoryAccess API to optimize MemoryPhis.Alina Sbirlea2019-01-311-1/+21
| | | | | | | | | | | | | | | | Summary: EarlyCSE needs to optimize MemoryPhis after an access is removed and has special handling for it. This should be handled by MemorySSA instead. The default remains that MemoryPhis are *not* optimized after an access is removed. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, llvm-commits, Prazek Differential Revision: https://reviews.llvm.org/D57199 llvm-svn: 352787
* 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
* [IR] Add hasNPredecessors, hasNPredecessorsOrMore to BasicBlockVedant Kumar2018-11-191-1/+1
| | | | | | | | | | | | | | | | | | | | | | | Add methods to BasicBlock which make it easier to efficiently check whether a block has N (or more) predecessors. This can be more efficient than using pred_size(), which is a linear time operation. We might consider adding similar methods for successors. I haven't done so in this patch because succ_size() is already O(1). With this patch applied, I measured a 0.065% compile-time reduction in user time for running `opt -O3` on the sqlite3 amalgamation (30 trials). The change in mergeStoreIntoSuccessor alone saves 45 million linked list iterations in a stage2 Release build of llc. See llvm.org/PR39702 for a harder but more general way of achieving similar results. Differential Revision: https://reviews.llvm.org/D54686 llvm-svn: 347256
* Use llvm::copy. NFCFangrui Song2018-11-171-1/+1
| | | | llvm-svn: 347126
* [TI removal] Make variables declared as `TerminatorInst` and initializedChandler Carruth2018-10-151-1/+1
| | | | | | | | | | | | | by `getTerminator()` calls instead be declared as `Instruction`. This is the biggest remaining chunk of the usage of `getTerminator()` that insists on the narrow type and so is an easy batch of updates. Several files saw more extensive updates where this would cascade to requiring API updates within the file to use `Instruction` instead of `TerminatorInst`. All of these were trivial in nature (pervasively using `Instruction` instead just worked). llvm-svn: 344502
* [MemorySSAUpdater] Avoid creating self-referencing MemoryDefsAlexandros Lamprineas2018-09-111-4/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fix for https://bugs.llvm.org/show_bug.cgi?id=38807, which occurred while compiling SemaTemplateInstantiate.cpp with clang and GVNHoist enabled. In the following example: 1=def(entry) / \ 2=def(1) 4=def(1) 3=def(2) 5=def(4) When removing the MemoryDef 2=def(1) from its basic block, and just before adding it to the end of the parent basic block, we first replace all its uses with the defining memory access: 3=def(2) -> 3=def(1) Then we call insertDef for adding 2=def(1) to the parent basic block, where we replace the uses of 1=def(entry) with 2=def(1). Doing so we create a self reference: 2=def(1) -> 2=def(2) (bad) 3=def(1) -> 3=def(2) (ok) 4=def(1) -> 4=def(2) (ok) Differential Revision: https://reviews.llvm.org/D51801 llvm-svn: 341947
* API to update MemorySSA for cloned blocks and added CFG edges.Alina Sbirlea2018-09-101-0/+518
| | | | | | | | | | | | | | | | 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] Update MemoryPhi wiring for block splitting to consider if ↵Alina Sbirlea2018-09-071-1/+10
| | | | | | | | | | | | | | | | | identical edges were merged. Summary: Block splitting is done with either identical edges being merged, or not. Only critical edges can be split without merging identical edges based on an option. Teach the memoryssa updater to take this into account: for the same edge between two blocks only move one entry from the Phi in Old to the new Phi in New. Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D51563 llvm-svn: 341709
* [IR] Begin removal of TerminatorInst by removing successor manipulation.Chandler Carruth2018-08-261-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The core get and set routines move to the `Instruction` class. These routines are only valid to call on instructions which are terminators. The iterator and *generic* range based access move to `CFG.h` where all the other generic successor and predecessor access lives. While moving the iterator here, simplify it using the iterator utilities LLVM provides and updates coding style as much as reasonable. The APIs remain pointer-heavy when they could better use references, and retain the odd behavior of `operator*` and `operator->` that is common in LLVM iterators. Adjusting this API, if desired, should be a follow-up step. Non-generic range iteration is added for the two instructions where there is an especially easy mechanism and where there was code attempting to use the range accessor from a specific subclass: `indirectbr` and `br`. In both cases, the successors are contiguous operands and can be easily iterated via the operand list. This is the first major patch in removing the `TerminatorInst` type from the IR's instruction type hierarchy. This change was discussed in an RFC here and was pretty clearly positive: http://lists.llvm.org/pipermail/llvm-dev/2018-May/123407.html There will be a series of much more mechanical changes following this one to complete this move. Differential Revision: https://reviews.llvm.org/D47467 llvm-svn: 340698
* [MemorySSAUpdater] Update Phi operands after trivial Phi eliminationAlexandros Lamprineas2018-07-231-15/+13
| | | | | | | | | | | | Bug fix for PR37445. The underlying problem and its fix are similar to PR37808. The bug lies in MemorySSAUpdater::getPreviousDefRecursive(), where PhiOps is computed before the call to tryRemoveTrivialPhi() and it ends up being out of date, pointing to stale data. We have now turned each of the PhiOps into a TrackingVH<MemoryAccess>. Differential Revision: https://reviews.llvm.org/D49425 llvm-svn: 337680
* [MemorySSA] Add API to update MemoryPhis, following CFG changes.Alina Sbirlea2018-07-201-0/+29
| | | | | | | | | | | | | | | | Summary: When splitting predecessors in BasicBlockUtils, we create a new block as an immediate predecessor of the original BB, then we connect a given set of predecessors to the new block. The API in this patch will be used to update MemoryPhis for this CFG change. If all predecessors are being moved, we move the MemoryPhi directly. Otherwise we create a new MemoryPhi in the NewBB and populate its incoming values, while deleting them from BB's Phi. [Split from D45299 for easier review] Reviewers: george.burgess.iv Subscribers: sanjoy, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D49156 llvm-svn: 337581
* [MemorySSAUpdater] Remove deleted trivial Phis from active worksetAlexandros Lamprineas2018-07-161-7/+12
| | | | | | | | | | | | | Bug fix for PR37808. The regression test is a reduced version of the original reproducer attached to the bug report. As stated in the report, the problem was that InsertedPHIs was keeping dangling pointers to deleted Memory-Phis. MemoryPhis are created eagerly and sometimes get zapped shortly afterwards. I've used WeakVH instead of an expensive removal operation from the active workset. Differential Revision: https://reviews.llvm.org/D48372 llvm-svn: 337149
* Remove redundant *_or_null checks; NFCGeorge Burgess IV2018-07-121-2/+2
| | | | | | | For the first one, we dereference `NewDef` right before the `if` anyway. For the second, we shouldn't have NULL users(). llvm-svn: 336952
* [MemorySSA] Add APIs to move memory accesses between blocks, following CFG ↵Alina Sbirlea2018-07-111-0/+50
| | | | | | | | | | | | | | | | 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-0/+33
| | | | | | | | | | | | | | | | 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
* [MemorySSA] Reflow comments + clean up control flow; NFCGeorge Burgess IV2018-05-261-3/+9
| | | | | | | 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
* Remove \brief commands from doxygen comments.Adrian Prantl2018-05-011-1/+1
| | | | | | | | | | | | | | | | 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
* [MemorySSAUpdater] Mark Phi users of a node being moved as non-optimizeZhaoshi Zheng2018-04-091-0/+17
| | | | | | | | | | Fix PR36484, as suggested: <quote> during moves, mark the direct users of the erased things that were phis as "not to be optimized" <quote> llvm-svn: 329621
* [MemorySSA] Fix exponential compile-time updating MemorySSA.Eli Friedman2018-03-261-15/+28
| | | | | | | | | | | | | | | | | | | | | | | MemorySSAUpdater::getPreviousDefRecursive is a recursive algorithm, for each block, it computes the previous definition for each predecessor, then takes those definitions and combines them. But currently it doesn't remember results which it already computed; this means it can visit the same block multiple times, which adds up to exponential time overall. To fix this, this patch adds a cache. If we computed the result for a block already, we don't need to visit it again because we'll come up with the same result. Well, unless we RAUW a MemoryPHI; in that case, the TrackingVH will be updated automatically. This matches the original source paper for this algorithm. The testcase isn't really a test for the bug, but it adds coverage for the case where tryRemoveTrivialPhi erases an existing PHI node. (It's hard to write a good regression test for a performance issue.) Differential Revision: https://reviews.llvm.org/D44715 llvm-svn: 328577
OpenPOWER on IntegriCloud