1//===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------===//
8//
9// This file implements the MemorySSAUpdater class.
10//
11//===----------------------------------------------------------------===//
12#include "llvm/Analysis/MemorySSAUpdater.h"
13#include "llvm/ADT/STLExtras.h"
14#include "llvm/ADT/SetVector.h"
15#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/Analysis/IteratedDominanceFrontier.h"
17#include "llvm/Analysis/LoopIterator.h"
18#include "llvm/Analysis/MemorySSA.h"
19#include "llvm/IR/BasicBlock.h"
20#include "llvm/IR/Dominators.h"
21#include "llvm/Support/Debug.h"
22#include <algorithm>
23
24#define DEBUG_TYPE "memoryssa"
25using namespace llvm;
26
27// This is the marker algorithm from "Simple and Efficient Construction of
28// Static Single Assignment Form"
29// The simple, non-marker algorithm places phi nodes at any join
30// Here, we place markers, and only place phi nodes if they end up necessary.
31// They are only necessary if they break a cycle (IE we recursively visit
32// ourselves again), or we discover, while getting the value of the operands,
33// that there are two or more definitions needing to be merged.
34// This still will leave non-minimal form in the case of irreducible control
35// flow, where phi nodes may be in cycles with themselves, but unnecessary.
36//
37// The predecessor walk is driven by an explicit worklist rather than native
38// recursion so that its depth does not scale with the length of the walk;
39// otherwise deep CFGs (e.g. long block chains in large generated
40// kernels/shaders) could overflow the native stack.
41MemoryAccess *MemorySSAUpdater::getPreviousDefIterative(
42 BasicBlock *BB,
43 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
44 // One frame of the explicit worklist. Each frame runs a small state machine
45 // driven by its ResumePoint, suspending when it needs a child block's result
46 // (delivered via Returned) and resuming once that result is available:
47 // EnterBlock Initial cache / unreachable / unique-predecessor / cycle
48 // checks. May finish the frame or push a child frame.
49 // ResumeSinglePred Resume after the unique predecessor is resolved.
50 // RunPredLoop Gather phi operands from predecessors, then place or
51 // simplify the phi.
52 struct StackFrame {
53 enum class ResumePoint { EnterBlock, ResumeSinglePred, RunPredLoop };
54
55 BasicBlock *BB;
56 explicit StackFrame(BasicBlock *BB) : BB(BB), PredIt(pred_begin(BB)) {}
57 ResumePoint Resume = ResumePoint::EnterBlock;
58 // Multi-predecessor loop state.
59 SmallVector<TrackingVH<MemoryAccess>, 4> PhiOps;
60 // Cursor over BB's predecessors for the resumable RunPredLoop walk. This
61 // stays valid across suspend/resume because the walk only modifies
62 // MemorySSA, never terminators or CFG edges, so BB's predecessor list does
63 // not change.
64 pred_iterator PredIt;
65 // When set, `Returned` holds the result for the predecessor at PredIt.
66 bool PendingIncoming = false;
67 bool UniqueIncomingAccess = true;
68 MemoryAccess *SingleAccess = nullptr;
69
70 // Fold an incoming predecessor access into this frame's phi operands,
71 // tracking whether all incoming accesses are identical (so the phi may be
72 // elided).
73 void incorporate(MemoryAccess *Incoming) {
74 if (!SingleAccess)
75 SingleAccess = Incoming;
76 else if (Incoming != SingleAccess)
77 UniqueIncomingAccess = false;
78 PhiOps.push_back(Elt: Incoming);
79 }
80 };
81 using ResumePoint = StackFrame::ResumePoint;
82
83 // Non-recursive part of getPreviousDefFromEnd(Pred): if Pred has a local
84 // definition, cache and return its last def. Returns nullptr when Pred has no
85 // local def, so it must instead be visited via its own worklist frame.
86 auto GetLocalDefFromEnd = [&](BasicBlock *Pred) -> MemoryAccess * {
87 auto *Defs = MSSA->getBlockDefs(BB: Pred);
88 if (!Defs)
89 return nullptr;
90 MemoryAccess *Result = &*Defs->rbegin();
91 CachedPreviousDef.insert(KV: {Pred, Result});
92 return Result;
93 };
94
95 SmallVector<StackFrame, 8> WorkStack;
96 WorkStack.emplace_back(Args&: BB);
97 // Carries a completed child frame's result back to its parent frame.
98 MemoryAccess *Returned = nullptr;
99
100 while (!WorkStack.empty()) {
101 // NOTE: emplace_back below may reallocate and invalidate this reference, so
102 // every path that pushes a new frame sets the ResumePoint first and then
103 // continues the loop without touching the reference again.
104 StackFrame &F = WorkStack.back();
105 BasicBlock *CurBB = F.BB;
106
107 switch (F.Resume) {
108 case ResumePoint::EnterBlock: {
109 // First, do a cache lookup. Without this cache, certain CFG structures
110 // (like a series of if statements) take exponential time to visit.
111 auto Cached = CachedPreviousDef.find(Val: CurBB);
112 if (Cached != CachedPreviousDef.end()) {
113 Returned = Cached->second;
114 WorkStack.pop_back();
115 continue;
116 }
117
118 // If this method is called from an unreachable block, return LoE.
119 if (!MSSA->DT->isReachableFromEntry(A: CurBB)) {
120 Returned = MSSA->getLiveOnEntryDef();
121 WorkStack.pop_back();
122 continue;
123 }
124
125 if (BasicBlock *Pred = CurBB->getUniquePredecessor()) {
126 VisitedBlocks.insert(Ptr: CurBB);
127 // Single predecessor case, there can be only one definition. If Pred
128 // has a local def take it, otherwise descend into Pred.
129 if (MemoryAccess *Result = GetLocalDefFromEnd(Pred)) {
130 CachedPreviousDef.insert(KV: {CurBB, Result});
131 Returned = Result;
132 WorkStack.pop_back();
133 continue;
134 }
135 F.Resume = ResumePoint::ResumeSinglePred;
136 WorkStack.emplace_back(Args&: Pred);
137 continue;
138 }
139
140 if (VisitedBlocks.count(Ptr: CurBB)) {
141 // We hit our node again, meaning we had a cycle, we must insert a phi
142 // node to break it so we have an operand. The only case this will
143 // insert useless phis is if we have irreducible control flow.
144 MemoryAccess *Result = MSSA->createMemoryPhi(BB: CurBB);
145 CachedPreviousDef.insert(KV: {CurBB, Result});
146 Returned = Result;
147 WorkStack.pop_back();
148 continue;
149 }
150
151 // Mark us visited so we can detect a cycle, then walk the predecessors.
152 // PredIt was initialized to pred_begin(CurBB) when the frame was created.
153 VisitedBlocks.insert(Ptr: CurBB);
154 F.Resume = ResumePoint::RunPredLoop;
155 continue;
156 }
157
158 case ResumePoint::ResumeSinglePred: {
159 // The single predecessor's result is in Returned.
160 CachedPreviousDef.insert(KV: {CurBB, Returned});
161 WorkStack.pop_back();
162 continue;
163 }
164
165 case ResumePoint::RunPredLoop: {
166 // Get the values in our predecessors for placement of a potential phi
167 // node. This will insert phi nodes if we cycle in order to break the
168 // cycle and have an operand.
169 if (F.PendingIncoming) {
170 // Returned holds the result for the predecessor at PredIt.
171 F.incorporate(Incoming: Returned);
172 F.PendingIncoming = false;
173 ++F.PredIt;
174 }
175
176 bool Suspended = false;
177 for (; F.PredIt != pred_end(BB: CurBB); ++F.PredIt) {
178 BasicBlock *Pred = *F.PredIt;
179 if (MSSA->DT->isReachableFromEntry(A: Pred)) {
180 // Local def resolves now, otherwise descend into Pred.
181 if (MemoryAccess *IncomingAccess = GetLocalDefFromEnd(Pred)) {
182 F.incorporate(Incoming: IncomingAccess);
183 } else {
184 F.PendingIncoming = true;
185 WorkStack.emplace_back(Args&: Pred);
186 Suspended = true;
187 break;
188 }
189 } else
190 F.PhiOps.push_back(Elt: MSSA->getLiveOnEntryDef());
191 }
192 if (Suspended)
193 continue;
194
195 // Now try to simplify the ops to avoid placing a phi.
196 // This may return null if we never created a phi yet, that's okay
197 MemoryPhi *Phi =
198 dyn_cast_or_null<MemoryPhi>(Val: MSSA->getMemoryAccess(BB: CurBB));
199
200 // See if we can avoid the phi by simplifying it.
201 auto *Result = tryRemoveTrivialPhi(Phi, Operands&: F.PhiOps);
202 // If we couldn't simplify, we may have to create a phi
203 if (Result == Phi && F.UniqueIncomingAccess && F.SingleAccess) {
204 // A concrete Phi only exists if we created an empty one to break a
205 // cycle.
206 if (Phi) {
207 assert(Phi->operands().empty() && "Expected empty Phi");
208 Phi->replaceAllUsesWith(V: F.SingleAccess);
209 removeMemoryAccess(Phi);
210 }
211 Result = F.SingleAccess;
212 } else if (Result == Phi && !(F.UniqueIncomingAccess && F.SingleAccess)) {
213 if (!Phi)
214 Phi = MSSA->createMemoryPhi(BB: CurBB);
215
216 // See if the existing phi operands match what we need.
217 // Unlike normal SSA, we only allow one phi node per block, so we can't
218 // just create a new one.
219 if (Phi->getNumOperands() != 0) {
220 // FIXME: Figure out whether this is dead code and if so remove it.
221 if (!std::equal(first1: Phi->op_begin(), last1: Phi->op_end(), first2: F.PhiOps.begin())) {
222 // These will have been filled in by the predecessor walk above.
223 llvm::copy(Range&: F.PhiOps, Out: Phi->op_begin());
224 llvm::copy(Range: predecessors(BB: CurBB), Out: Phi->block_begin());
225 }
226 } else {
227 unsigned I = 0;
228 for (auto *Pred : predecessors(BB: CurBB))
229 Phi->addIncoming(V: &*F.PhiOps[I++], BB: Pred);
230 InsertedPHIs.push_back(Elt: Phi);
231 }
232 Result = Phi;
233 }
234
235 // Set ourselves up for the next variable by resetting visited state.
236 VisitedBlocks.erase(Ptr: CurBB);
237 CachedPreviousDef.insert(KV: {CurBB, Result});
238 Returned = Result;
239 WorkStack.pop_back();
240 continue;
241 }
242 }
243 }
244
245 return Returned;
246}
247
248// This starts at the memory access, and goes backwards in the block to find the
249// previous definition. If a definition is not found the block of the access,
250// it continues globally, creating phi nodes to ensure we have a single
251// definition.
252MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
253 if (auto *LocalResult = getPreviousDefInBlock(MA))
254 return LocalResult;
255 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
256 return getPreviousDefIterative(BB: MA->getBlock(), CachedPreviousDef);
257}
258
259// This starts at the memory access, and goes backwards in the block to the find
260// the previous definition. If the definition is not found in the block of the
261// access, it returns nullptr.
262MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
263 auto *Defs = MSSA->getBlockDefs(BB: MA->getBlock());
264
265 // It's possible there are no defs, or we got handed the first def to start.
266 if (Defs) {
267 // If this is a def, we can just use the def iterators.
268 if (!isa<MemoryUse>(Val: MA)) {
269 auto Iter = MA->getReverseDefsIterator();
270 ++Iter;
271 if (Iter != Defs->rend())
272 return &*Iter;
273 } else {
274 // Otherwise, have to walk the all access iterator.
275 auto End = MSSA->getBlockAccesses(BB: MA->getBlock())->rend();
276 for (auto &U : make_range(x: ++MA->getReverseIterator(), y: End))
277 if (!isa<MemoryUse>(Val: U))
278 return cast<MemoryAccess>(Val: &U);
279 // Note that if MA comes before Defs->begin(), we won't hit a def.
280 return nullptr;
281 }
282 }
283 return nullptr;
284}
285
286// This starts at the end of block
287MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
288 BasicBlock *BB,
289 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
290 auto *Defs = MSSA->getBlockDefs(BB);
291
292 if (Defs) {
293 CachedPreviousDef.insert(KV: {BB, &*Defs->rbegin()});
294 return &*Defs->rbegin();
295 }
296
297 return getPreviousDefIterative(BB, CachedPreviousDef);
298}
299// Recurse over a set of phi uses to eliminate the trivial ones
300MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
301 if (!Phi)
302 return nullptr;
303 TrackingVH<MemoryAccess> Res(Phi);
304 SmallVector<TrackingVH<Value>, 8> Uses;
305 std::copy(first: Phi->user_begin(), last: Phi->user_end(), result: std::back_inserter(x&: Uses));
306 for (auto &U : Uses)
307 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(Val: &*U))
308 tryRemoveTrivialPhi(Phi: UsePhi);
309 return Res;
310}
311
312// Eliminate trivial phis
313// Phis are trivial if they are defined either by themselves, or all the same
314// argument.
315// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
316// We recursively try to remove them.
317MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi) {
318 assert(Phi && "Can only remove concrete Phi.");
319 auto OperRange = Phi->operands();
320 return tryRemoveTrivialPhi(Phi, Operands&: OperRange);
321}
322template <class RangeType>
323MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
324 RangeType &Operands) {
325 // Bail out on non-opt Phis.
326 if (NonOptPhis.count(V: Phi))
327 return Phi;
328
329 // Detect equal or self arguments
330 MemoryAccess *Same = nullptr;
331 for (auto &Op : Operands) {
332 // If the same or self, good so far
333 if (Op == Phi || Op == Same)
334 continue;
335 // not the same, return the phi since it's not eliminatable by us
336 if (Same)
337 return Phi;
338 Same = cast<MemoryAccess>(&*Op);
339 }
340 // Never found a non-self reference, the phi is undef
341 if (Same == nullptr)
342 return MSSA->getLiveOnEntryDef();
343 if (Phi) {
344 Phi->replaceAllUsesWith(V: Same);
345 removeMemoryAccess(Phi);
346 }
347
348 // We should only end up recursing in case we replaced something, in which
349 // case, we may have made other Phis trivial.
350 return recursePhi(Phi: Same);
351}
352
353void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
354 VisitedBlocks.clear();
355 InsertedPHIs.clear();
356 MU->setDefiningAccess(DMA: getPreviousDef(MA: MU));
357
358 // In cases without unreachable blocks, because uses do not create new
359 // may-defs, there are only two cases:
360 // 1. There was a def already below us, and therefore, we should not have
361 // created a phi node because it was already needed for the def.
362 //
363 // 2. There is no def below us, and therefore, there is no extra renaming work
364 // to do.
365
366 // In cases with unreachable blocks, where the unnecessary Phis were
367 // optimized out, adding the Use may re-insert those Phis. Hence, when
368 // inserting Uses outside of the MSSA creation process, and new Phis were
369 // added, rename all uses if we are asked.
370
371 if (!RenameUses && !InsertedPHIs.empty()) {
372 auto *Defs = MSSA->getBlockDefs(BB: MU->getBlock());
373 (void)Defs;
374 assert((!Defs || (++Defs->begin() == Defs->end())) &&
375 "Block may have only a Phi or no defs");
376 }
377
378 if (RenameUses && InsertedPHIs.size()) {
379 SmallPtrSet<BasicBlock *, 16> Visited;
380 BasicBlock *StartBlock = MU->getBlock();
381
382 if (auto *Defs = MSSA->getBlockDefs(BB: StartBlock)) {
383 MemoryAccess *FirstDef = &*Defs->begin();
384 // Convert to incoming value if it's a memorydef. A phi *is* already an
385 // incoming value.
386 if (auto *MD = dyn_cast<MemoryDef>(Val: FirstDef))
387 FirstDef = MD->getDefiningAccess();
388
389 MSSA->renamePass(BB: MU->getBlock(), IncomingVal: FirstDef, Visited);
390 }
391 // We just inserted a phi into this block, so the incoming value will
392 // become the phi anyway, so it does not matter what we pass.
393 for (auto &MP : InsertedPHIs)
394 if (MemoryPhi *Phi = cast_or_null<MemoryPhi>(Val&: MP))
395 MSSA->renamePass(BB: Phi->getBlock(), IncomingVal: nullptr, Visited);
396 }
397}
398
399// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
400static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
401 MemoryAccess *NewDef) {
402 // Replace any operand with us an incoming block with the new defining
403 // access.
404 int i = MP->getBasicBlockIndex(BB);
405 assert(i != -1 && "Should have found the basic block in the phi");
406 // We can't just compare i against getNumOperands since one is signed and the
407 // other not. So use it to index into the block iterator.
408 for (const BasicBlock *BlockBB : llvm::drop_begin(RangeOrContainer: MP->blocks(), N: i)) {
409 if (BlockBB != BB)
410 break;
411 MP->setIncomingValue(I: i, V: NewDef);
412 ++i;
413 }
414}
415
416// A brief description of the algorithm:
417// First, we compute what should define the new def, using the SSA
418// construction algorithm.
419// Then, we update the defs below us (and any new phi nodes) in the graph to
420// point to the correct new defs, to ensure we only have one variable, and no
421// disconnected stores.
422void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
423 // Don't bother updating dead code.
424 if (!MSSA->DT->isReachableFromEntry(A: MD->getBlock())) {
425 MD->setDefiningAccess(DMA: MSSA->getLiveOnEntryDef());
426 return;
427 }
428
429 VisitedBlocks.clear();
430 InsertedPHIs.clear();
431
432 // See if we had a local def, and if not, go hunting.
433 MemoryAccess *DefBefore = getPreviousDef(MA: MD);
434 bool DefBeforeSameBlock = false;
435 if (DefBefore->getBlock() == MD->getBlock() &&
436 !(isa<MemoryPhi>(Val: DefBefore) &&
437 llvm::is_contained(Range&: InsertedPHIs, Element: DefBefore)))
438 DefBeforeSameBlock = true;
439
440 // There is a def before us, which means we can replace any store/phi uses
441 // of that thing with us, since we are in the way of whatever was there
442 // before.
443 // We now define that def's memorydefs and memoryphis
444 if (DefBeforeSameBlock) {
445 DefBefore->replaceUsesWithIf(New: MD, ShouldReplace: [MD](Use &U) {
446 // Leave the MemoryUses alone.
447 // Also make sure we skip ourselves to avoid self references.
448 User *Usr = U.getUser();
449 return !isa<MemoryUse>(Val: Usr) && Usr != MD;
450 // Defs are automatically unoptimized when the user is set to MD below,
451 // because the isOptimized() call will fail to find the same ID.
452 });
453 }
454
455 // and that def is now our defining access.
456 MD->setDefiningAccess(DMA: DefBefore);
457
458 SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
459
460 SmallSet<WeakVH, 8> ExistingPhis;
461
462 // Remember the index where we may insert new phis.
463 unsigned NewPhiIndex = InsertedPHIs.size();
464 if (!DefBeforeSameBlock) {
465 // If there was a local def before us, we must have the same effect it
466 // did. Because every may-def is the same, any phis/etc we would create, it
467 // would also have created. If there was no local def before us, we
468 // performed a global update, and have to search all successors and make
469 // sure we update the first def in each of them (following all paths until
470 // we hit the first def along each path). This may also insert phi nodes.
471 // TODO: There are other cases we can skip this work, such as when we have a
472 // single successor, and only used a straight line of single pred blocks
473 // backwards to find the def. To make that work, we'd have to track whether
474 // getDefRecursive only ever used the single predecessor case. These types
475 // of paths also only exist in between CFG simplifications.
476
477 // If this is the first def in the block and this insert is in an arbitrary
478 // place, compute IDF and place phis.
479 SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
480
481 // If this is the last Def in the block, we may need additional Phis.
482 // Compute IDF in all cases, as renaming needs to be done even when MD is
483 // not the last access, because it can introduce a new access past which a
484 // previous access was optimized; that access needs to be reoptimized.
485 DefiningBlocks.insert(Ptr: MD->getBlock());
486 for (const auto &VH : InsertedPHIs)
487 if (const auto *RealPHI = cast_or_null<MemoryPhi>(Val: VH))
488 DefiningBlocks.insert(Ptr: RealPHI->getBlock());
489 ForwardIDFCalculator IDFs(*MSSA->DT);
490 SmallVector<BasicBlock *, 32> IDFBlocks;
491 IDFs.setDefiningBlocks(DefiningBlocks);
492 IDFs.calculate(IDFBlocks);
493 SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
494 for (auto *BBIDF : IDFBlocks) {
495 auto *MPhi = MSSA->getMemoryAccess(BB: BBIDF);
496 if (!MPhi) {
497 MPhi = MSSA->createMemoryPhi(BB: BBIDF);
498 NewInsertedPHIs.push_back(Elt: MPhi);
499 } else {
500 ExistingPhis.insert(V: MPhi);
501 }
502 // Add the phis created into the IDF blocks to NonOptPhis, so they are not
503 // optimized out as trivial by the call to getPreviousDefFromEnd below.
504 // Once they are complete, all these Phis are added to the FixupList, and
505 // removed from NonOptPhis inside fixupDefs(). Existing Phis in IDF may
506 // need fixing as well, and potentially be trivial before this insertion,
507 // hence add all IDF Phis. See PR43044.
508 NonOptPhis.insert(V: MPhi);
509 }
510 for (auto &MPhi : NewInsertedPHIs) {
511 auto *BBIDF = MPhi->getBlock();
512 for (auto *Pred : predecessors(BB: BBIDF)) {
513 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
514 MPhi->addIncoming(V: getPreviousDefFromEnd(BB: Pred, CachedPreviousDef), BB: Pred);
515 }
516 }
517
518 // Re-take the index where we're adding the new phis, because the above call
519 // to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
520 NewPhiIndex = InsertedPHIs.size();
521 for (auto &MPhi : NewInsertedPHIs) {
522 InsertedPHIs.push_back(Elt: &*MPhi);
523 FixupList.push_back(Elt: &*MPhi);
524 }
525
526 FixupList.push_back(Elt: MD);
527 }
528
529 // Update defining access of following defs.
530 unsigned NewPhiIndexEnd = InsertedPHIs.size();
531 fixupDefs(FixupList);
532 assert(NewPhiIndexEnd == InsertedPHIs.size() &&
533 "Should not insert new phis during fixupDefs()");
534
535 // Optimize potentially non-minimal phis added in this method.
536 unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
537 if (NewPhiSize)
538 tryRemoveTrivialPhis(UpdatedPHIs: ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
539
540 // Now that all fixups are done, rename all uses if we are asked. The defs are
541 // guaranteed to be in reachable code due to the check at the method entry.
542 BasicBlock *StartBlock = MD->getBlock();
543 if (RenameUses) {
544 SmallPtrSet<BasicBlock *, 16> Visited;
545 // We are guaranteed there is a def in the block, because we just got it
546 // handed to us in this function.
547 MemoryAccess *FirstDef = &*MSSA->getBlockDefs(BB: StartBlock)->begin();
548 // Convert to incoming value if it's a memorydef. A phi *is* already an
549 // incoming value.
550 if (auto *MD = dyn_cast<MemoryDef>(Val: FirstDef))
551 FirstDef = MD->getDefiningAccess();
552
553 MSSA->renamePass(BB: MD->getBlock(), IncomingVal: FirstDef, Visited);
554 // We just inserted a phi into this block, so the incoming value will become
555 // the phi anyway, so it does not matter what we pass.
556 for (auto &MP : InsertedPHIs) {
557 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(Val&: MP);
558 if (Phi)
559 MSSA->renamePass(BB: Phi->getBlock(), IncomingVal: nullptr, Visited);
560 }
561 // Existing Phi blocks may need renaming too, if an access was previously
562 // optimized and the inserted Defs "covers" the Optimized value.
563 for (const auto &MP : ExistingPhis) {
564 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(Val: MP);
565 if (Phi)
566 MSSA->renamePass(BB: Phi->getBlock(), IncomingVal: nullptr, Visited);
567 }
568 }
569}
570
571void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
572 SmallPtrSet<const BasicBlock *, 8> Seen;
573 SmallVector<const BasicBlock *, 16> Worklist;
574 for (const auto &Var : Vars) {
575 MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Val: Var);
576 if (!NewDef)
577 continue;
578 // First, see if there is a local def after the operand.
579 auto *Defs = MSSA->getBlockDefs(BB: NewDef->getBlock());
580 auto DefIter = NewDef->getDefsIterator();
581
582 // The temporary Phi is being fixed, unmark it for not to optimize.
583 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(Val: NewDef))
584 NonOptPhis.erase(V: Phi);
585
586 // If there is a local def after us, we only have to rename that.
587 if (++DefIter != Defs->end()) {
588 cast<MemoryDef>(Val&: DefIter)->setDefiningAccess(DMA: NewDef);
589 continue;
590 }
591
592 // Otherwise, we need to search down through the CFG.
593 // For each of our successors, handle it directly if their is a phi, or
594 // place on the fixup worklist.
595 for (const auto *S : successors(BB: NewDef->getBlock())) {
596 if (auto *MP = MSSA->getMemoryAccess(BB: S))
597 setMemoryPhiValueForBlock(MP, BB: NewDef->getBlock(), NewDef);
598 else
599 Worklist.push_back(Elt: S);
600 }
601
602 while (!Worklist.empty()) {
603 const BasicBlock *FixupBlock = Worklist.pop_back_val();
604
605 // Get the first def in the block that isn't a phi node.
606 if (auto *Defs = MSSA->getBlockDefs(BB: FixupBlock)) {
607 auto *FirstDef = &*Defs->begin();
608 // The loop above and below should have taken care of phi nodes
609 assert(!isa<MemoryPhi>(FirstDef) &&
610 "Should have already handled phi nodes!");
611 // We are now this def's defining access, make sure we actually dominate
612 // it
613 assert(MSSA->dominates(NewDef, FirstDef) &&
614 "Should have dominated the new access");
615
616 cast<MemoryDef>(Val: FirstDef)->setDefiningAccess(DMA: NewDef);
617 continue;
618 }
619 // We didn't find a def, so we must continue.
620 for (const auto *S : successors(BB: FixupBlock)) {
621 // If there is a phi node, handle it.
622 // Otherwise, put the block on the worklist
623 if (auto *MP = MSSA->getMemoryAccess(BB: S))
624 setMemoryPhiValueForBlock(MP, BB: FixupBlock, NewDef);
625 else {
626 // If we cycle, we should have ended up at a phi node that we already
627 // processed. FIXME: Double check this
628 if (!Seen.insert(Ptr: S).second)
629 continue;
630 Worklist.push_back(Elt: S);
631 }
632 }
633 }
634 }
635}
636
637void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
638 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: To)) {
639 MPhi->unorderedDeleteIncomingBlock(BB: From);
640 tryRemoveTrivialPhi(Phi: MPhi);
641 }
642}
643
644void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,
645 const BasicBlock *To) {
646 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: To)) {
647 bool Found = false;
648 MPhi->unorderedDeleteIncomingIf(Pred: [&](const MemoryAccess *, BasicBlock *B) {
649 if (From != B)
650 return false;
651 if (Found)
652 return true;
653 Found = true;
654 return false;
655 });
656 tryRemoveTrivialPhi(Phi: MPhi);
657 }
658}
659
660/// If all arguments of a MemoryPHI are defined by the same incoming
661/// argument, return that argument.
662static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
663 MemoryAccess *MA = nullptr;
664
665 for (auto &Arg : MP->operands()) {
666 if (!MA)
667 MA = cast<MemoryAccess>(Val&: Arg);
668 else if (MA != Arg)
669 return nullptr;
670 }
671 return MA;
672}
673
674static MemoryAccess *getNewDefiningAccessForClone(
675 MemoryAccess *MA, const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
676 MemorySSA *MSSA, function_ref<bool(BasicBlock *BB)> IsInClonedRegion) {
677 MemoryAccess *InsnDefining = MA;
678 if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(Val: InsnDefining)) {
679 if (MSSA->isLiveOnEntryDef(MA: DefMUD))
680 return DefMUD;
681
682 // If the MemoryDef is not part of the cloned region, leave it alone.
683 Instruction *DefMUDI = DefMUD->getMemoryInst();
684 assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
685 if (!IsInClonedRegion(DefMUDI->getParent()))
686 return DefMUD;
687
688 auto *NewDefMUDI = cast_or_null<Instruction>(Val: VMap.lookup(Val: DefMUDI));
689 InsnDefining = NewDefMUDI ? MSSA->getMemoryAccess(I: NewDefMUDI) : nullptr;
690 if (!InsnDefining || isa<MemoryUse>(Val: InsnDefining)) {
691 // The clone was simplified, it's no longer a MemoryDef, look up.
692 InsnDefining = getNewDefiningAccessForClone(
693 MA: DefMUD->getDefiningAccess(), VMap, MPhiMap, MSSA, IsInClonedRegion);
694 }
695 } else {
696 MemoryPhi *DefPhi = cast<MemoryPhi>(Val: InsnDefining);
697 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(Val: DefPhi))
698 InsnDefining = NewDefPhi;
699 }
700 assert(InsnDefining && "Defining instruction cannot be nullptr.");
701 return InsnDefining;
702}
703
704void MemorySSAUpdater::cloneUsesAndDefs(
705 BasicBlock *BB, BasicBlock *NewBB, const ValueToValueMapTy &VMap,
706 PhiToDefMap &MPhiMap, function_ref<bool(BasicBlock *)> IsInClonedRegion,
707 bool CloneWasSimplified) {
708 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
709 if (!Acc)
710 return;
711 for (const MemoryAccess &MA : *Acc) {
712 if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(Val: &MA)) {
713 Instruction *Insn = MUD->getMemoryInst();
714 // Entry does not exist if the clone of the block did not clone all
715 // instructions. This occurs in LoopRotate when cloning instructions
716 // from the old header to the old preheader. The cloned instruction may
717 // also be a simplified Value, not an Instruction (see LoopRotate).
718 // Also in LoopRotate, even when it's an instruction, due to it being
719 // simplified, it may be a Use rather than a Def, so we cannot use MUD as
720 // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
721 if (Instruction *NewInsn =
722 dyn_cast_or_null<Instruction>(Val: VMap.lookup(Val: Insn))) {
723 MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
724 NewInsn,
725 getNewDefiningAccessForClone(MA: MUD->getDefiningAccess(), VMap,
726 MPhiMap, MSSA, IsInClonedRegion),
727 /*Template=*/CloneWasSimplified ? nullptr : MUD,
728 /*CreationMustSucceed=*/false);
729 if (NewUseOrDef)
730 MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
731 }
732 }
733 }
734}
735
736void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
737 BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
738 auto *MPhi = MSSA->getMemoryAccess(BB: Header);
739 if (!MPhi)
740 return;
741
742 // Create phi node in the backedge block and populate it with the same
743 // incoming values as MPhi. Skip incoming values coming from Preheader.
744 auto *NewMPhi = MSSA->createMemoryPhi(BB: BEBlock);
745 bool HasUniqueIncomingValue = true;
746 MemoryAccess *UniqueValue = nullptr;
747 for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
748 BasicBlock *IBB = MPhi->getIncomingBlock(I);
749 MemoryAccess *IV = MPhi->getIncomingValue(I);
750 if (IBB != Preheader) {
751 NewMPhi->addIncoming(V: IV, BB: IBB);
752 if (HasUniqueIncomingValue) {
753 if (!UniqueValue)
754 UniqueValue = IV;
755 else if (UniqueValue != IV)
756 HasUniqueIncomingValue = false;
757 }
758 }
759 }
760
761 // Update incoming edges into MPhi. Remove all but the incoming edge from
762 // Preheader. Add an edge from NewMPhi
763 auto *AccFromPreheader = MPhi->getIncomingValueForBlock(BB: Preheader);
764 MPhi->setIncomingValue(I: 0, V: AccFromPreheader);
765 MPhi->setIncomingBlock(I: 0, BB: Preheader);
766 for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
767 MPhi->unorderedDeleteIncoming(I);
768 MPhi->addIncoming(V: NewMPhi, BB: BEBlock);
769
770 // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
771 // replaced with the unique value.
772 tryRemoveTrivialPhi(Phi: NewMPhi);
773}
774
775void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
776 ArrayRef<BasicBlock *> ExitBlocks,
777 const ValueToValueMapTy &VMap,
778 bool IgnoreIncomingWithNoClones) {
779 SmallSetVector<BasicBlock *, 16> Blocks(
780 llvm::from_range, concat<BasicBlock *const>(Ranges: LoopBlocks, Ranges&: ExitBlocks));
781
782 auto IsInClonedRegion = [&](BasicBlock *BB) { return Blocks.contains(key: BB); };
783
784 PhiToDefMap MPhiMap;
785 auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
786 assert(Phi && NewPhi && "Invalid Phi nodes.");
787 BasicBlock *NewPhiBB = NewPhi->getBlock();
788 SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(llvm::from_range,
789 predecessors(BB: NewPhiBB));
790 for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
791 MemoryAccess *IncomingAccess = Phi->getIncomingValue(I: It);
792 BasicBlock *IncBB = Phi->getIncomingBlock(I: It);
793
794 if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: IncBB)))
795 IncBB = NewIncBB;
796 else if (IgnoreIncomingWithNoClones)
797 continue;
798
799 // Now we have IncBB, and will need to add incoming from it to NewPhi.
800
801 // If IncBB is not a predecessor of NewPhiBB, then do not add it.
802 // NewPhiBB was cloned without that edge.
803 if (!NewPhiBBPreds.count(Ptr: IncBB))
804 continue;
805
806 // Determine incoming value and add it as incoming from IncBB.
807 NewPhi->addIncoming(V: getNewDefiningAccessForClone(MA: IncomingAccess, VMap,
808 MPhiMap, MSSA,
809 IsInClonedRegion),
810 BB: IncBB);
811 }
812 if (auto *SingleAccess = onlySingleValue(MP: NewPhi)) {
813 MPhiMap[Phi] = SingleAccess;
814 removeMemoryAccess(NewPhi);
815 }
816 };
817
818 auto ProcessBlock = [&](BasicBlock *BB) {
819 BasicBlock *NewBlock = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: BB));
820 if (!NewBlock)
821 return;
822
823 assert(!MSSA->getBlockAccesses(NewBlock) &&
824 "Cloned block should have no accesses");
825
826 // Add MemoryPhi.
827 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
828 MemoryPhi *NewPhi = MSSA->createMemoryPhi(BB: NewBlock);
829 MPhiMap[MPhi] = NewPhi;
830 }
831 // Update Uses and Defs.
832 cloneUsesAndDefs(BB, NewBB: NewBlock, VMap, MPhiMap, IsInClonedRegion);
833 };
834
835 for (auto *BB : Blocks)
836 ProcessBlock(BB);
837
838 for (auto *BB : Blocks)
839 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
840 if (MemoryAccess *NewPhi = MPhiMap.lookup(Val: MPhi))
841 FixPhiIncomingValues(MPhi, cast<MemoryPhi>(Val: NewPhi));
842}
843
844void MemorySSAUpdater::updateForClonedBlockIntoPred(
845 BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
846 // All defs/phis from outside BB that are used in BB, are valid uses in P1.
847 // Since those defs/phis must have dominated BB, and also dominate P1.
848 // Defs from BB being used in BB will be replaced with the cloned defs from
849 // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
850 // incoming def into the Phi from P1.
851 // Instructions cloned into the predecessor are in practice sometimes
852 // simplified, so disable the use of the template, and create an access from
853 // scratch.
854 PhiToDefMap MPhiMap;
855 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
856 MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(BB: P1);
857 cloneUsesAndDefs(
858 BB, NewBB: P1, VMap: VM, MPhiMap, IsInClonedRegion: [&](BasicBlock *CheckBB) { return BB == CheckBB; },
859 /*CloneWasSimplified=*/true);
860}
861
862template <typename Iter>
863void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
864 ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
865 DominatorTree &DT) {
866 SmallVector<CFGUpdate, 4> Updates;
867 // Update/insert phis in all successors of exit blocks.
868 for (auto *Exit : ExitBlocks)
869 for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
870 if (BasicBlock *NewExit = cast_or_null<BasicBlock>(Val: VMap->lookup(Val: Exit))) {
871 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(Idx: 0);
872 Updates.push_back(Elt: {DT.Insert, NewExit, ExitSucc});
873 }
874 applyInsertUpdates(Updates, DT);
875}
876
877void MemorySSAUpdater::updateExitBlocksForClonedLoop(
878 ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
879 DominatorTree &DT) {
880 const ValueToValueMapTy *const Arr[] = {&VMap};
881 privateUpdateExitBlocksForClonedLoop(ExitBlocks, ValuesBegin: std::begin(arr: Arr),
882 ValuesEnd: std::end(arr: Arr), DT);
883}
884
885void MemorySSAUpdater::updateExitBlocksForClonedLoop(
886 ArrayRef<BasicBlock *> ExitBlocks,
887 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
888 auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
889 return I.get();
890 };
891 using MappedIteratorType =
892 mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
893 decltype(GetPtr)>;
894 auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
895 auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
896 privateUpdateExitBlocksForClonedLoop(ExitBlocks, ValuesBegin: MapBegin, ValuesEnd: MapEnd, DT);
897}
898
899void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
900 DominatorTree &DT, bool UpdateDT) {
901 SmallVector<CFGUpdate, 4> DeleteUpdates;
902 SmallVector<CFGUpdate, 4> RevDeleteUpdates;
903 SmallVector<CFGUpdate, 4> InsertUpdates;
904 for (const auto &Update : Updates) {
905 if (Update.getKind() == DT.Insert)
906 InsertUpdates.push_back(Elt: {DT.Insert, Update.getFrom(), Update.getTo()});
907 else {
908 DeleteUpdates.push_back(Elt: {DT.Delete, Update.getFrom(), Update.getTo()});
909 RevDeleteUpdates.push_back(Elt: {DT.Insert, Update.getFrom(), Update.getTo()});
910 }
911 }
912
913 if (!DeleteUpdates.empty()) {
914 if (!InsertUpdates.empty()) {
915 if (!UpdateDT) {
916 SmallVector<CFGUpdate, 0> Empty;
917 // Deletes are reversed applied, because this CFGView is pretending the
918 // deletes did not happen yet, hence the edges still exist.
919 DT.applyUpdates(Updates: Empty, PostViewUpdates: RevDeleteUpdates);
920 } else {
921 // Apply all updates, with the RevDeleteUpdates as PostCFGView.
922 DT.applyUpdates(Updates, PostViewUpdates: RevDeleteUpdates);
923 }
924
925 // Note: the MSSA update below doesn't distinguish between a GD with
926 // (RevDelete,false) and (Delete, true), but this matters for the DT
927 // updates above; for "children" purposes they are equivalent; but the
928 // updates themselves convey the desired update, used inside DT only.
929 GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
930 applyInsertUpdates(InsertUpdates, DT, GD: &GD);
931 // Update DT to redelete edges; this matches the real CFG so we can
932 // perform the standard update without a postview of the CFG.
933 DT.applyUpdates(Updates: DeleteUpdates);
934 } else {
935 if (UpdateDT)
936 DT.applyUpdates(Updates: DeleteUpdates);
937 }
938 } else {
939 if (UpdateDT)
940 DT.applyUpdates(Updates);
941 GraphDiff<BasicBlock *> GD;
942 applyInsertUpdates(InsertUpdates, DT, GD: &GD);
943 }
944
945 // Update for deleted edges
946 for (auto &Update : DeleteUpdates)
947 removeEdge(From: Update.getFrom(), To: Update.getTo());
948}
949
950void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
951 DominatorTree &DT) {
952 GraphDiff<BasicBlock *> GD;
953 applyInsertUpdates(Updates, DT, GD: &GD);
954}
955
956void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
957 DominatorTree &DT,
958 const GraphDiff<BasicBlock *> *GD) {
959 // Get recursive last Def, assuming well formed MSSA and updated DT.
960 auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
961 while (true) {
962 MemorySSA::DefsList *Defs = MSSA->getBlockDefs(BB);
963 // Return last Def or Phi in BB, if it exists.
964 if (Defs)
965 return &*(--Defs->end());
966
967 // Check number of predecessors, we only care if there's more than one.
968 unsigned Count = 0;
969 BasicBlock *Pred = nullptr;
970 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(N: BB)) {
971 Pred = Pi;
972 Count++;
973 if (Count == 2)
974 break;
975 }
976
977 // If BB has multiple predecessors, get last definition from IDom.
978 if (Count != 1) {
979 // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
980 // DT is invalidated. Return LoE as its last def. This will be added to
981 // MemoryPhi node, and later deleted when the block is deleted.
982 if (!DT.getNode(BB))
983 return MSSA->getLiveOnEntryDef();
984 if (auto *IDom = DT.getNode(BB)->getIDom())
985 if (IDom->getBlock() != BB) {
986 BB = IDom->getBlock();
987 continue;
988 }
989 return MSSA->getLiveOnEntryDef();
990 } else {
991 // Single predecessor, BB cannot be dead. GetLastDef of Pred.
992 assert(Count == 1 && Pred && "Single predecessor expected.");
993 // BB can be unreachable though, return LoE if that is the case.
994 if (!DT.getNode(BB))
995 return MSSA->getLiveOnEntryDef();
996 BB = Pred;
997 }
998 };
999 llvm_unreachable("Unable to get last definition.");
1000 };
1001
1002 // Get nearest IDom given a set of blocks.
1003 // TODO: this can be optimized by starting the search at the node with the
1004 // lowest level (highest in the tree).
1005 auto FindNearestCommonDominator =
1006 [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
1007 BasicBlock *PrevIDom = *BBSet.begin();
1008 for (auto *BB : BBSet)
1009 PrevIDom = DT.findNearestCommonDominator(A: PrevIDom, B: BB);
1010 return PrevIDom;
1011 };
1012
1013 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
1014 // include CurrIDom.
1015 auto GetNoLongerDomBlocks =
1016 [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
1017 SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
1018 if (PrevIDom == CurrIDom)
1019 return;
1020 BlocksPrevDom.push_back(Elt: PrevIDom);
1021 BasicBlock *NextIDom = PrevIDom;
1022 while (BasicBlock *UpIDom =
1023 DT.getNode(BB: NextIDom)->getIDom()->getBlock()) {
1024 if (UpIDom == CurrIDom)
1025 break;
1026 BlocksPrevDom.push_back(Elt: UpIDom);
1027 NextIDom = UpIDom;
1028 }
1029 };
1030
1031 // Map a BB to its predecessors: added + previously existing. To get a
1032 // deterministic order, store predecessors as SetVectors. The order in each
1033 // will be defined by the order in Updates (fixed) and the order given by
1034 // children<> (also fixed). Since we further iterate over these ordered sets,
1035 // we lose the information of multiple edges possibly existing between two
1036 // blocks, so we'll keep and EdgeCount map for that.
1037 // An alternate implementation could keep unordered set for the predecessors,
1038 // traverse either Updates or children<> each time to get the deterministic
1039 // order, and drop the usage of EdgeCount. This alternate approach would still
1040 // require querying the maps for each predecessor, and children<> call has
1041 // additional computation inside for creating the snapshot-graph predecessors.
1042 // As such, we favor using a little additional storage and less compute time.
1043 // This decision can be revisited if we find the alternative more favorable.
1044
1045 struct PredInfo {
1046 SmallSetVector<BasicBlock *, 2> Added;
1047 SmallSetVector<BasicBlock *, 2> Prev;
1048 };
1049 SmallDenseMap<BasicBlock *, PredInfo> PredMap;
1050
1051 for (const auto &Edge : Updates) {
1052 BasicBlock *BB = Edge.getTo();
1053 auto &AddedBlockSet = PredMap[BB].Added;
1054 AddedBlockSet.insert(X: Edge.getFrom());
1055 }
1056
1057 // Store all existing predecessor for each BB, at least one must exist.
1058 SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
1059 SmallPtrSet<BasicBlock *, 2> NewBlocks;
1060 for (auto &BBPredPair : PredMap) {
1061 auto *BB = BBPredPair.first;
1062 const auto &AddedBlockSet = BBPredPair.second.Added;
1063 auto &PrevBlockSet = BBPredPair.second.Prev;
1064 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(N: BB)) {
1065 if (!AddedBlockSet.count(key: Pi))
1066 PrevBlockSet.insert(X: Pi);
1067 EdgeCountMap[{Pi, BB}]++;
1068 }
1069
1070 if (PrevBlockSet.empty()) {
1071 assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
1072 LLVM_DEBUG(
1073 dbgs()
1074 << "Adding a predecessor to a block with no predecessors. "
1075 "This must be an edge added to a new, likely cloned, block. "
1076 "Its memory accesses must be already correct, assuming completed "
1077 "via the updateExitBlocksForClonedLoop API. "
1078 "Assert a single such edge is added so no phi addition or "
1079 "additional processing is required.\n");
1080 assert(AddedBlockSet.size() == 1 &&
1081 "Can only handle adding one predecessor to a new block.");
1082 // Need to remove new blocks from PredMap. Remove below to not invalidate
1083 // iterator here.
1084 NewBlocks.insert(Ptr: BB);
1085 }
1086 }
1087 // Nothing to process for new/cloned blocks.
1088 for (auto *BB : NewBlocks)
1089 PredMap.erase(Val: BB);
1090
1091 SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
1092 SmallVector<WeakVH, 8> InsertedPhis;
1093
1094 // First create MemoryPhis in all blocks that don't have one. Create in the
1095 // order found in Updates, not in PredMap, to get deterministic numbering.
1096 for (const auto &Edge : Updates) {
1097 BasicBlock *BB = Edge.getTo();
1098 if (PredMap.count(Val: BB) && !MSSA->getMemoryAccess(BB))
1099 InsertedPhis.push_back(Elt: MSSA->createMemoryPhi(BB));
1100 }
1101
1102 // Now we'll fill in the MemoryPhis with the right incoming values.
1103 for (auto &BBPredPair : PredMap) {
1104 auto *BB = BBPredPair.first;
1105 const auto &PrevBlockSet = BBPredPair.second.Prev;
1106 const auto &AddedBlockSet = BBPredPair.second.Added;
1107 assert(!PrevBlockSet.empty() &&
1108 "At least one previous predecessor must exist.");
1109
1110 // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
1111 // keeping this map before the loop. We can reuse already populated entries
1112 // if an edge is added from the same predecessor to two different blocks,
1113 // and this does happen in rotate. Note that the map needs to be updated
1114 // when deleting non-necessary phis below, if the phi is in the map by
1115 // replacing the value with DefP1.
1116 SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
1117 for (auto *AddedPred : AddedBlockSet) {
1118 auto *DefPn = GetLastDef(AddedPred);
1119 assert(DefPn != nullptr && "Unable to find last definition.");
1120 LastDefAddedPred[AddedPred] = DefPn;
1121 }
1122
1123 MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
1124 // If Phi is not empty, add an incoming edge from each added pred. Must
1125 // still compute blocks with defs to replace for this block below.
1126 if (NewPhi->getNumOperands()) {
1127 for (auto *Pred : AddedBlockSet) {
1128 auto *LastDefForPred = LastDefAddedPred[Pred];
1129 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1130 NewPhi->addIncoming(V: LastDefForPred, BB: Pred);
1131 }
1132 } else {
1133 // Pick any existing predecessor and get its definition. All other
1134 // existing predecessors should have the same one, since no phi existed.
1135 auto *P1 = *PrevBlockSet.begin();
1136 MemoryAccess *DefP1 = GetLastDef(P1);
1137
1138 // Check DefP1 against all Defs in LastDefPredPair. If all the same,
1139 // nothing to add.
1140 bool InsertPhi = false;
1141 for (auto LastDefPredPair : LastDefAddedPred)
1142 if (DefP1 != LastDefPredPair.second) {
1143 InsertPhi = true;
1144 break;
1145 }
1146 if (!InsertPhi) {
1147 // Since NewPhi may be used in other newly added Phis, replace all uses
1148 // of NewPhi with the definition coming from all predecessors (DefP1),
1149 // before deleting it.
1150 NewPhi->replaceAllUsesWith(V: DefP1);
1151 removeMemoryAccess(NewPhi);
1152 continue;
1153 }
1154
1155 // Update Phi with new values for new predecessors and old value for all
1156 // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
1157 // sets, the order of entries in NewPhi is deterministic.
1158 for (auto *Pred : AddedBlockSet) {
1159 auto *LastDefForPred = LastDefAddedPred[Pred];
1160 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1161 NewPhi->addIncoming(V: LastDefForPred, BB: Pred);
1162 }
1163 for (auto *Pred : PrevBlockSet)
1164 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1165 NewPhi->addIncoming(V: DefP1, BB: Pred);
1166 }
1167
1168 // Get all blocks that used to dominate BB and no longer do after adding
1169 // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
1170 assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
1171 BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
1172 assert(PrevIDom && "Previous IDom should exists");
1173 BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
1174 assert(NewIDom && "BB should have a new valid idom");
1175 assert(DT.dominates(NewIDom, PrevIDom) &&
1176 "New idom should dominate old idom");
1177 GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
1178 }
1179
1180 tryRemoveTrivialPhis(UpdatedPHIs: InsertedPhis);
1181 // Create the set of blocks that now have a definition. We'll use this to
1182 // compute IDF and add Phis there next.
1183 SmallVector<BasicBlock *, 8> BlocksToProcess;
1184 for (auto &VH : InsertedPhis)
1185 if (auto *MPhi = cast_or_null<MemoryPhi>(Val&: VH))
1186 BlocksToProcess.push_back(Elt: MPhi->getBlock());
1187
1188 // Compute IDF and add Phis in all IDF blocks that do not have one.
1189 SmallVector<BasicBlock *, 32> IDFBlocks;
1190 if (!BlocksToProcess.empty()) {
1191 ForwardIDFCalculator IDFs(DT, GD);
1192 SmallPtrSet<BasicBlock *, 16> DefiningBlocks(llvm::from_range,
1193 BlocksToProcess);
1194 IDFs.setDefiningBlocks(DefiningBlocks);
1195 IDFs.calculate(IDFBlocks);
1196
1197 SmallSetVector<MemoryPhi *, 4> PhisToFill;
1198 // First create all needed Phis.
1199 for (auto *BBIDF : IDFBlocks)
1200 if (!MSSA->getMemoryAccess(BB: BBIDF)) {
1201 auto *IDFPhi = MSSA->createMemoryPhi(BB: BBIDF);
1202 InsertedPhis.push_back(Elt: IDFPhi);
1203 PhisToFill.insert(X: IDFPhi);
1204 }
1205 // Then update or insert their correct incoming values.
1206 for (auto *BBIDF : IDFBlocks) {
1207 auto *IDFPhi = MSSA->getMemoryAccess(BB: BBIDF);
1208 assert(IDFPhi && "Phi must exist");
1209 if (!PhisToFill.count(key: IDFPhi)) {
1210 // Update existing Phi.
1211 // FIXME: some updates may be redundant, try to optimize and skip some.
1212 for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
1213 IDFPhi->setIncomingValue(I, V: GetLastDef(IDFPhi->getIncomingBlock(I)));
1214 } else {
1215 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(N: BBIDF))
1216 IDFPhi->addIncoming(V: GetLastDef(Pi), BB: Pi);
1217 }
1218 }
1219 }
1220
1221 // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
1222 // longer dominate, replace those with the closest dominating def.
1223 // This will also update optimized accesses, as they're also uses.
1224 for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
1225 if (auto DefsList = MSSA->getBlockDefs(BB: BlockWithDefsToReplace)) {
1226 for (auto &DefToReplaceUses : *DefsList) {
1227 BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
1228 // We defer resetting optimized accesses until all uses are replaced, to
1229 // avoid invalidating the iterator.
1230 SmallVector<MemoryUseOrDef *, 4> ResetOptimized;
1231 for (Use &U : llvm::make_early_inc_range(Range: DefToReplaceUses.uses())) {
1232 MemoryAccess *Usr = cast<MemoryAccess>(Val: U.getUser());
1233 if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Val: Usr)) {
1234 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
1235 if (!DT.dominates(A: DominatingBlock, B: DominatedBlock))
1236 U.set(GetLastDef(DominatedBlock));
1237 } else {
1238 BasicBlock *DominatedBlock = Usr->getBlock();
1239 if (!DT.dominates(A: DominatingBlock, B: DominatedBlock)) {
1240 if (auto *DomBlPhi = MSSA->getMemoryAccess(BB: DominatedBlock))
1241 U.set(DomBlPhi);
1242 else {
1243 auto *IDom = DT.getNode(BB: DominatedBlock)->getIDom();
1244 assert(IDom && "Block must have a valid IDom.");
1245 U.set(GetLastDef(IDom->getBlock()));
1246 }
1247 ResetOptimized.push_back(Elt: cast<MemoryUseOrDef>(Val: Usr));
1248 }
1249 }
1250 }
1251
1252 for (auto *Usr : ResetOptimized)
1253 Usr->resetOptimized();
1254 }
1255 }
1256 }
1257 tryRemoveTrivialPhis(UpdatedPHIs: InsertedPhis);
1258}
1259
1260// Move What before Where in the MemorySSA IR.
1261template <class WhereType>
1262void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1263 WhereType Where) {
1264 // Mark MemoryPhi users of What not to be optimized.
1265 for (auto *U : What->users())
1266 if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(Val: U))
1267 NonOptPhis.insert(V: PhiUser);
1268
1269 // Replace all our users with our defining access.
1270 What->replaceAllUsesWith(V: What->getDefiningAccess());
1271
1272 // Let MemorySSA take care of moving it around in the lists.
1273 MSSA->moveTo(What, BB, Where);
1274
1275 // Now reinsert it into the IR and do whatever fixups needed.
1276 if (auto *MD = dyn_cast<MemoryDef>(Val: What))
1277 insertDef(MD, /*RenameUses=*/true);
1278 else
1279 insertUse(MU: cast<MemoryUse>(Val: What), /*RenameUses=*/true);
1280
1281 // Clear dangling pointers. We added all MemoryPhi users, but not all
1282 // of them are removed by fixupDefs().
1283 NonOptPhis.clear();
1284}
1285
1286// Move What before Where in the MemorySSA IR.
1287void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1288 moveTo(What, BB: Where->getBlock(), Where: Where->getIterator());
1289}
1290
1291// Move What after Where in the MemorySSA IR.
1292void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1293 moveTo(What, BB: Where->getBlock(), Where: ++Where->getIterator());
1294}
1295
1296void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
1297 MemorySSA::InsertionPlace Where) {
1298 if (Where != MemorySSA::InsertionPlace::BeforeTerminator)
1299 return moveTo(What, BB, Where);
1300
1301 if (auto *Where = MSSA->getMemoryAccess(I: BB->getTerminator()))
1302 return moveBefore(What, Where);
1303 else
1304 return moveTo(What, BB, Where: MemorySSA::InsertionPlace::End);
1305}
1306
1307// All accesses in To used to be in From. Move to end and update access lists.
1308void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
1309 Instruction *Start) {
1310
1311 MemorySSA::AccessList *Accs = MSSA->getBlockAccesses(BB: From);
1312 if (!Accs)
1313 return;
1314
1315 assert(Start->getParent() == To && "Incorrect Start instruction");
1316 MemoryAccess *FirstInNew = nullptr;
1317 for (Instruction &I : make_range(x: Start->getIterator(), y: To->end()))
1318 if ((FirstInNew = MSSA->getMemoryAccess(I: &I)))
1319 break;
1320 if (FirstInNew) {
1321 auto *MUD = cast<MemoryUseOrDef>(Val: FirstInNew);
1322 do {
1323 auto NextIt = ++MUD->getIterator();
1324 MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
1325 ? nullptr
1326 : cast<MemoryUseOrDef>(Val: &*NextIt);
1327 MSSA->moveTo(What: MUD, BB: To, Point: MemorySSA::End);
1328 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need
1329 // to retrieve it again.
1330 Accs = MSSA->getBlockAccesses(BB: From);
1331 MUD = NextMUD;
1332 } while (MUD);
1333 }
1334
1335 // If all accesses were moved and only a trivial Phi remains, we try to remove
1336 // that Phi. This is needed when From is going to be deleted.
1337 auto *Defs = MSSA->getBlockDefs(BB: From);
1338 if (Defs && !Defs->empty())
1339 if (auto *Phi = dyn_cast<MemoryPhi>(Val: &*Defs->begin()))
1340 tryRemoveTrivialPhi(Phi);
1341}
1342
1343void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
1344 BasicBlock *To,
1345 Instruction *Start) {
1346 assert(MSSA->getBlockAccesses(To) == nullptr &&
1347 "To block is expected to be free of MemoryAccesses.");
1348 moveAllAccesses(From, To, Start);
1349 for (BasicBlock *Succ : successors(BB: To))
1350 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: Succ))
1351 MPhi->setIncomingBlock(I: MPhi->getBasicBlockIndex(BB: From), BB: To);
1352}
1353
1354void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
1355 Instruction *Start) {
1356 assert(From->getUniquePredecessor() == To &&
1357 "From block is expected to have a single predecessor (To).");
1358 moveAllAccesses(From, To, Start);
1359 for (BasicBlock *Succ : successors(BB: From))
1360 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: Succ))
1361 MPhi->setIncomingBlock(I: MPhi->getBasicBlockIndex(BB: From), BB: To);
1362}
1363
1364void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
1365 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
1366 bool IdenticalEdgesWereMerged) {
1367 assert(!MSSA->getBlockAccesses(New) &&
1368 "Access list should be null for a new block.");
1369 MemoryPhi *Phi = MSSA->getMemoryAccess(BB: Old);
1370 if (!Phi)
1371 return;
1372 if (Old->hasNPredecessors(N: 1)) {
1373 assert(pred_size(New) == Preds.size() &&
1374 "Should have moved all predecessors.");
1375 MSSA->moveTo(What: Phi, BB: New, Point: MemorySSA::Beginning);
1376 } else {
1377 assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1378 "new immediate predecessor.");
1379 MemoryPhi *NewPhi = MSSA->createMemoryPhi(BB: New);
1380 SmallPtrSet<BasicBlock *, 16> PredsSet(llvm::from_range, Preds);
1381 // Currently only support the case of removing a single incoming edge when
1382 // identical edges were not merged.
1383 if (!IdenticalEdgesWereMerged)
1384 assert(PredsSet.size() == Preds.size() &&
1385 "If identical edges were not merged, we cannot have duplicate "
1386 "blocks in the predecessors");
1387 Phi->unorderedDeleteIncomingIf(Pred: [&](MemoryAccess *MA, BasicBlock *B) {
1388 if (PredsSet.count(Ptr: B)) {
1389 NewPhi->addIncoming(V: MA, BB: B);
1390 if (!IdenticalEdgesWereMerged)
1391 PredsSet.erase(Ptr: B);
1392 return true;
1393 }
1394 return false;
1395 });
1396 Phi->addIncoming(V: NewPhi, BB: New);
1397 tryRemoveTrivialPhi(Phi: NewPhi);
1398 }
1399}
1400
1401void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
1402 assert(!MSSA->isLiveOnEntryDef(MA) &&
1403 "Trying to remove the live on entry def");
1404 // We can only delete phi nodes if they have no uses, or we can replace all
1405 // uses with a single definition.
1406 MemoryAccess *NewDefTarget = nullptr;
1407 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Val: MA)) {
1408 // Note that it is sufficient to know that all edges of the phi node have
1409 // the same argument. If they do, by the definition of dominance frontiers
1410 // (which we used to place this phi), that argument must dominate this phi,
1411 // and thus, must dominate the phi's uses, and so we will not hit the assert
1412 // below.
1413 NewDefTarget = onlySingleValue(MP);
1414 assert((NewDefTarget || MP->use_empty()) &&
1415 "We can't delete this memory phi");
1416 } else {
1417 NewDefTarget = cast<MemoryUseOrDef>(Val: MA)->getDefiningAccess();
1418 }
1419
1420 SmallSetVector<MemoryPhi *, 4> PhisToCheck;
1421
1422 // Re-point the uses at our defining access
1423 if (!isa<MemoryUse>(Val: MA) && !MA->use_empty()) {
1424 // Reset optimized on users of this store, and reset the uses.
1425 // A few notes:
1426 // 1. This is a slightly modified version of RAUW to avoid walking the
1427 // uses twice here.
1428 // 2. If we wanted to be complete, we would have to reset the optimized
1429 // flags on users of phi nodes if doing the below makes a phi node have all
1430 // the same arguments. Instead, we prefer users to removeMemoryAccess those
1431 // phi nodes, because doing it here would be N^3.
1432 if (MA->hasValueHandle())
1433 ValueHandleBase::ValueIsRAUWd(Old: MA, New: NewDefTarget);
1434 // Note: We assume MemorySSA is not used in metadata since it's not really
1435 // part of the IR.
1436
1437 assert(NewDefTarget != MA && "Going into an infinite loop");
1438 while (!MA->use_empty()) {
1439 Use &U = *MA->use_begin();
1440 if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: U.getUser()))
1441 MUD->resetOptimized();
1442 if (OptimizePhis)
1443 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Val: U.getUser()))
1444 PhisToCheck.insert(X: MP);
1445 U.set(NewDefTarget);
1446 }
1447 }
1448
1449 // The call below to erase will destroy MA, so we can't change the order we
1450 // are doing things here
1451 MSSA->removeFromLookups(MA);
1452 MSSA->removeFromLists(MA);
1453
1454 // Optionally optimize Phi uses. This will recursively remove trivial phis.
1455 if (!PhisToCheck.empty()) {
1456 SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
1457 PhisToCheck.end()};
1458 PhisToCheck.clear();
1459
1460 unsigned PhisSize = PhisToOptimize.size();
1461 while (PhisSize-- > 0)
1462 if (MemoryPhi *MP =
1463 cast_or_null<MemoryPhi>(Val: PhisToOptimize.pop_back_val()))
1464 tryRemoveTrivialPhi(Phi: MP);
1465 }
1466}
1467
1468void MemorySSAUpdater::removeBlocks(
1469 const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
1470 // First delete all uses of BB in MemoryPhis.
1471 for (BasicBlock *BB : DeadBlocks) {
1472 Instruction *TI = BB->getTerminator();
1473 assert(TI && "Basic block expected to have a terminator instruction");
1474 for (BasicBlock *Succ : successors(I: TI))
1475 if (!DeadBlocks.count(key: Succ))
1476 if (MemoryPhi *MP = MSSA->getMemoryAccess(BB: Succ)) {
1477 MP->unorderedDeleteIncomingBlock(BB);
1478 tryRemoveTrivialPhi(Phi: MP);
1479 }
1480 // Drop all references of all accesses in BB
1481 if (MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB))
1482 for (MemoryAccess &MA : *Acc)
1483 MA.dropAllReferences();
1484 }
1485
1486 // Next, delete all memory accesses in each block
1487 for (BasicBlock *BB : DeadBlocks) {
1488 MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
1489 if (!Acc)
1490 continue;
1491 for (MemoryAccess &MA : llvm::make_early_inc_range(Range&: *Acc)) {
1492 MSSA->removeFromLookups(&MA);
1493 MSSA->removeFromLists(&MA);
1494 }
1495 }
1496}
1497
1498void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
1499 for (const auto &VH : UpdatedPHIs)
1500 if (auto *MPhi = cast_or_null<MemoryPhi>(Val: VH))
1501 tryRemoveTrivialPhi(Phi: MPhi);
1502}
1503
1504void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {
1505 const BasicBlock *BB = I->getParent();
1506 // Remove memory accesses in BB for I and all following instructions.
1507 auto BBI = I->getIterator(), BBE = BB->end();
1508 // FIXME: If this becomes too expensive, iterate until the first instruction
1509 // with a memory access, then iterate over MemoryAccesses.
1510 while (BBI != BBE)
1511 removeMemoryAccess(I: &*(BBI++));
1512 // Update phis in BB's successors to remove BB.
1513 SmallVector<WeakVH, 16> UpdatedPHIs;
1514 for (const BasicBlock *Successor : successors(BB)) {
1515 removeDuplicatePhiEdgesBetween(From: BB, To: Successor);
1516 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: Successor)) {
1517 MPhi->unorderedDeleteIncomingBlock(BB);
1518 UpdatedPHIs.push_back(Elt: MPhi);
1519 }
1520 }
1521 // Optimize trivial phis.
1522 tryRemoveTrivialPhis(UpdatedPHIs);
1523}
1524
1525MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
1526 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1527 MemorySSA::InsertionPlace Point, bool CreationMustSucceed) {
1528 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(
1529 I, Definition, /*Template=*/nullptr, CreationMustSucceed);
1530 if (NewAccess)
1531 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1532 return NewAccess;
1533}
1534
1535MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
1536 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1537 assert(I->getParent() == InsertPt->getBlock() &&
1538 "New and old access must be in the same block");
1539 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1540 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1541 InsertPt->getIterator());
1542 return NewAccess;
1543}
1544
1545MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
1546 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1547 assert(I->getParent() == InsertPt->getBlock() &&
1548 "New and old access must be in the same block");
1549 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1550 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1551 ++InsertPt->getIterator());
1552 return NewAccess;
1553}
1554