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