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(Phi->op_begin(), Phi->op_end(), 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(pred_begin(BB), pred_end(BB), 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(Phi->user_begin(), Phi->user_end(), 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 // Remember the index where we stopped inserting new phis above, since the
415 // fixupDefs call in the loop below may insert more, that are already minimal.
416 unsigned NewPhiIndexEnd = InsertedPHIs.size();
417
418 while (!FixupList.empty()) {
419 unsigned StartingPHISize = InsertedPHIs.size();
420 fixupDefs(FixupList);
421 FixupList.clear();
422 // Put any new phis on the fixup list, and process them
423 FixupList.append(in_start: InsertedPHIs.begin() + StartingPHISize, in_end: InsertedPHIs.end());
424 }
425
426 // Optimize potentially non-minimal phis added in this method.
427 unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
428 if (NewPhiSize)
429 tryRemoveTrivialPhis(UpdatedPHIs: ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
430
431 // Now that all fixups are done, rename all uses if we are asked. The defs are
432 // guaranteed to be in reachable code due to the check at the method entry.
433 BasicBlock *StartBlock = MD->getBlock();
434 if (RenameUses) {
435 SmallPtrSet<BasicBlock *, 16> Visited;
436 // We are guaranteed there is a def in the block, because we just got it
437 // handed to us in this function.
438 MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(BB: StartBlock)->begin();
439 // Convert to incoming value if it's a memorydef. A phi *is* already an
440 // incoming value.
441 if (auto *MD = dyn_cast<MemoryDef>(Val: FirstDef))
442 FirstDef = MD->getDefiningAccess();
443
444 MSSA->renamePass(BB: MD->getBlock(), IncomingVal: FirstDef, Visited);
445 // We just inserted a phi into this block, so the incoming value will become
446 // the phi anyway, so it does not matter what we pass.
447 for (auto &MP : InsertedPHIs) {
448 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(Val&: MP);
449 if (Phi)
450 MSSA->renamePass(BB: Phi->getBlock(), IncomingVal: nullptr, Visited);
451 }
452 // Existing Phi blocks may need renaming too, if an access was previously
453 // optimized and the inserted Defs "covers" the Optimized value.
454 for (const auto &MP : ExistingPhis) {
455 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(Val: MP);
456 if (Phi)
457 MSSA->renamePass(BB: Phi->getBlock(), IncomingVal: nullptr, Visited);
458 }
459 }
460}
461
462void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
463 SmallPtrSet<const BasicBlock *, 8> Seen;
464 SmallVector<const BasicBlock *, 16> Worklist;
465 for (const auto &Var : Vars) {
466 MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Val: Var);
467 if (!NewDef)
468 continue;
469 // First, see if there is a local def after the operand.
470 auto *Defs = MSSA->getWritableBlockDefs(BB: NewDef->getBlock());
471 auto DefIter = NewDef->getDefsIterator();
472
473 // The temporary Phi is being fixed, unmark it for not to optimize.
474 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(Val: NewDef))
475 NonOptPhis.erase(V: Phi);
476
477 // If there is a local def after us, we only have to rename that.
478 if (++DefIter != Defs->end()) {
479 cast<MemoryDef>(Val&: DefIter)->setDefiningAccess(DMA: NewDef);
480 continue;
481 }
482
483 // Otherwise, we need to search down through the CFG.
484 // For each of our successors, handle it directly if their is a phi, or
485 // place on the fixup worklist.
486 for (const auto *S : successors(BB: NewDef->getBlock())) {
487 if (auto *MP = MSSA->getMemoryAccess(BB: S))
488 setMemoryPhiValueForBlock(MP, BB: NewDef->getBlock(), NewDef);
489 else
490 Worklist.push_back(Elt: S);
491 }
492
493 while (!Worklist.empty()) {
494 const BasicBlock *FixupBlock = Worklist.pop_back_val();
495
496 // Get the first def in the block that isn't a phi node.
497 if (auto *Defs = MSSA->getWritableBlockDefs(BB: FixupBlock)) {
498 auto *FirstDef = &*Defs->begin();
499 // The loop above and below should have taken care of phi nodes
500 assert(!isa<MemoryPhi>(FirstDef) &&
501 "Should have already handled phi nodes!");
502 // We are now this def's defining access, make sure we actually dominate
503 // it
504 assert(MSSA->dominates(NewDef, FirstDef) &&
505 "Should have dominated the new access");
506
507 // This may insert new phi nodes, because we are not guaranteed the
508 // block we are processing has a single pred, and depending where the
509 // store was inserted, it may require phi nodes below it.
510 cast<MemoryDef>(Val: FirstDef)->setDefiningAccess(DMA: getPreviousDef(MA: FirstDef));
511 return;
512 }
513 // We didn't find a def, so we must continue.
514 for (const auto *S : successors(BB: FixupBlock)) {
515 // If there is a phi node, handle it.
516 // Otherwise, put the block on the worklist
517 if (auto *MP = MSSA->getMemoryAccess(BB: S))
518 setMemoryPhiValueForBlock(MP, BB: FixupBlock, NewDef);
519 else {
520 // If we cycle, we should have ended up at a phi node that we already
521 // processed. FIXME: Double check this
522 if (!Seen.insert(Ptr: S).second)
523 continue;
524 Worklist.push_back(Elt: S);
525 }
526 }
527 }
528 }
529}
530
531void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
532 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: To)) {
533 MPhi->unorderedDeleteIncomingBlock(BB: From);
534 tryRemoveTrivialPhi(Phi: MPhi);
535 }
536}
537
538void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,
539 const BasicBlock *To) {
540 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: To)) {
541 bool Found = false;
542 MPhi->unorderedDeleteIncomingIf(Pred: [&](const MemoryAccess *, BasicBlock *B) {
543 if (From != B)
544 return false;
545 if (Found)
546 return true;
547 Found = true;
548 return false;
549 });
550 tryRemoveTrivialPhi(Phi: MPhi);
551 }
552}
553
554/// If all arguments of a MemoryPHI are defined by the same incoming
555/// argument, return that argument.
556static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
557 MemoryAccess *MA = nullptr;
558
559 for (auto &Arg : MP->operands()) {
560 if (!MA)
561 MA = cast<MemoryAccess>(Val&: Arg);
562 else if (MA != Arg)
563 return nullptr;
564 }
565 return MA;
566}
567
568static MemoryAccess *getNewDefiningAccessForClone(MemoryAccess *MA,
569 const ValueToValueMapTy &VMap,
570 PhiToDefMap &MPhiMap,
571 MemorySSA *MSSA) {
572 MemoryAccess *InsnDefining = MA;
573 if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(Val: InsnDefining)) {
574 if (!MSSA->isLiveOnEntryDef(MA: DefMUD)) {
575 Instruction *DefMUDI = DefMUD->getMemoryInst();
576 assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
577 if (Instruction *NewDefMUDI =
578 cast_or_null<Instruction>(Val: VMap.lookup(Val: DefMUDI))) {
579 InsnDefining = MSSA->getMemoryAccess(I: NewDefMUDI);
580 if (!InsnDefining || isa<MemoryUse>(Val: InsnDefining)) {
581 // The clone was simplified, it's no longer a MemoryDef, look up.
582 InsnDefining = getNewDefiningAccessForClone(
583 MA: DefMUD->getDefiningAccess(), VMap, MPhiMap, MSSA);
584 }
585 }
586 }
587 } else {
588 MemoryPhi *DefPhi = cast<MemoryPhi>(Val: InsnDefining);
589 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(Val: DefPhi))
590 InsnDefining = NewDefPhi;
591 }
592 assert(InsnDefining && "Defining instruction cannot be nullptr.");
593 return InsnDefining;
594}
595
596void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
597 const ValueToValueMapTy &VMap,
598 PhiToDefMap &MPhiMap,
599 bool CloneWasSimplified) {
600 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
601 if (!Acc)
602 return;
603 for (const MemoryAccess &MA : *Acc) {
604 if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(Val: &MA)) {
605 Instruction *Insn = MUD->getMemoryInst();
606 // Entry does not exist if the clone of the block did not clone all
607 // instructions. This occurs in LoopRotate when cloning instructions
608 // from the old header to the old preheader. The cloned instruction may
609 // also be a simplified Value, not an Instruction (see LoopRotate).
610 // Also in LoopRotate, even when it's an instruction, due to it being
611 // simplified, it may be a Use rather than a Def, so we cannot use MUD as
612 // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
613 if (Instruction *NewInsn =
614 dyn_cast_or_null<Instruction>(Val: VMap.lookup(Val: Insn))) {
615 MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
616 NewInsn,
617 getNewDefiningAccessForClone(MA: MUD->getDefiningAccess(), VMap,
618 MPhiMap, MSSA),
619 /*Template=*/CloneWasSimplified ? nullptr : MUD,
620 /*CreationMustSucceed=*/false);
621 if (NewUseOrDef)
622 MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
623 }
624 }
625 }
626}
627
628void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
629 BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
630 auto *MPhi = MSSA->getMemoryAccess(BB: Header);
631 if (!MPhi)
632 return;
633
634 // Create phi node in the backedge block and populate it with the same
635 // incoming values as MPhi. Skip incoming values coming from Preheader.
636 auto *NewMPhi = MSSA->createMemoryPhi(BB: BEBlock);
637 bool HasUniqueIncomingValue = true;
638 MemoryAccess *UniqueValue = nullptr;
639 for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
640 BasicBlock *IBB = MPhi->getIncomingBlock(I);
641 MemoryAccess *IV = MPhi->getIncomingValue(I);
642 if (IBB != Preheader) {
643 NewMPhi->addIncoming(V: IV, BB: IBB);
644 if (HasUniqueIncomingValue) {
645 if (!UniqueValue)
646 UniqueValue = IV;
647 else if (UniqueValue != IV)
648 HasUniqueIncomingValue = false;
649 }
650 }
651 }
652
653 // Update incoming edges into MPhi. Remove all but the incoming edge from
654 // Preheader. Add an edge from NewMPhi
655 auto *AccFromPreheader = MPhi->getIncomingValueForBlock(BB: Preheader);
656 MPhi->setIncomingValue(I: 0, V: AccFromPreheader);
657 MPhi->setIncomingBlock(I: 0, BB: Preheader);
658 for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
659 MPhi->unorderedDeleteIncoming(I);
660 MPhi->addIncoming(V: NewMPhi, BB: BEBlock);
661
662 // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
663 // replaced with the unique value.
664 tryRemoveTrivialPhi(Phi: NewMPhi);
665}
666
667void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
668 ArrayRef<BasicBlock *> ExitBlocks,
669 const ValueToValueMapTy &VMap,
670 bool IgnoreIncomingWithNoClones) {
671 PhiToDefMap MPhiMap;
672
673 auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
674 assert(Phi && NewPhi && "Invalid Phi nodes.");
675 BasicBlock *NewPhiBB = NewPhi->getBlock();
676 SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(BB: NewPhiBB),
677 pred_end(BB: NewPhiBB));
678 for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
679 MemoryAccess *IncomingAccess = Phi->getIncomingValue(I: It);
680 BasicBlock *IncBB = Phi->getIncomingBlock(I: It);
681
682 if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: IncBB)))
683 IncBB = NewIncBB;
684 else if (IgnoreIncomingWithNoClones)
685 continue;
686
687 // Now we have IncBB, and will need to add incoming from it to NewPhi.
688
689 // If IncBB is not a predecessor of NewPhiBB, then do not add it.
690 // NewPhiBB was cloned without that edge.
691 if (!NewPhiBBPreds.count(Ptr: IncBB))
692 continue;
693
694 // Determine incoming value and add it as incoming from IncBB.
695 NewPhi->addIncoming(
696 V: getNewDefiningAccessForClone(MA: IncomingAccess, VMap, MPhiMap, MSSA),
697 BB: IncBB);
698 }
699 if (auto *SingleAccess = onlySingleValue(MP: NewPhi)) {
700 MPhiMap[Phi] = SingleAccess;
701 removeMemoryAccess(NewPhi);
702 }
703 };
704
705 auto ProcessBlock = [&](BasicBlock *BB) {
706 BasicBlock *NewBlock = cast_or_null<BasicBlock>(Val: VMap.lookup(Val: BB));
707 if (!NewBlock)
708 return;
709
710 assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
711 "Cloned block should have no accesses");
712
713 // Add MemoryPhi.
714 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
715 MemoryPhi *NewPhi = MSSA->createMemoryPhi(BB: NewBlock);
716 MPhiMap[MPhi] = NewPhi;
717 }
718 // Update Uses and Defs.
719 cloneUsesAndDefs(BB, NewBB: NewBlock, VMap, MPhiMap);
720 };
721
722 for (auto *BB : llvm::concat<BasicBlock *const>(Ranges: LoopBlocks, Ranges&: ExitBlocks))
723 ProcessBlock(BB);
724
725 for (auto *BB : llvm::concat<BasicBlock *const>(Ranges: LoopBlocks, Ranges&: ExitBlocks))
726 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
727 if (MemoryAccess *NewPhi = MPhiMap.lookup(Val: MPhi))
728 FixPhiIncomingValues(MPhi, cast<MemoryPhi>(Val: NewPhi));
729}
730
731void MemorySSAUpdater::updateForClonedBlockIntoPred(
732 BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
733 // All defs/phis from outside BB that are used in BB, are valid uses in P1.
734 // Since those defs/phis must have dominated BB, and also dominate P1.
735 // Defs from BB being used in BB will be replaced with the cloned defs from
736 // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
737 // incoming def into the Phi from P1.
738 // Instructions cloned into the predecessor are in practice sometimes
739 // simplified, so disable the use of the template, and create an access from
740 // scratch.
741 PhiToDefMap MPhiMap;
742 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
743 MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(BB: P1);
744 cloneUsesAndDefs(BB, NewBB: P1, VMap: VM, MPhiMap, /*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(BlocksToProcess.begin(),
1078 BlocksToProcess.end());
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 for (Use &U : llvm::make_early_inc_range(Range: DefToReplaceUses.uses())) {
1114 MemoryAccess *Usr = cast<MemoryAccess>(Val: U.getUser());
1115 if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Val: Usr)) {
1116 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
1117 if (!DT.dominates(A: DominatingBlock, B: DominatedBlock))
1118 U.set(GetLastDef(DominatedBlock));
1119 } else {
1120 BasicBlock *DominatedBlock = Usr->getBlock();
1121 if (!DT.dominates(A: DominatingBlock, B: DominatedBlock)) {
1122 if (auto *DomBlPhi = MSSA->getMemoryAccess(BB: DominatedBlock))
1123 U.set(DomBlPhi);
1124 else {
1125 auto *IDom = DT.getNode(BB: DominatedBlock)->getIDom();
1126 assert(IDom && "Block must have a valid IDom.");
1127 U.set(GetLastDef(IDom->getBlock()));
1128 }
1129 cast<MemoryUseOrDef>(Val: Usr)->resetOptimized();
1130 }
1131 }
1132 }
1133 }
1134 }
1135 }
1136 tryRemoveTrivialPhis(UpdatedPHIs: InsertedPhis);
1137}
1138
1139// Move What before Where in the MemorySSA IR.
1140template <class WhereType>
1141void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1142 WhereType Where) {
1143 // Mark MemoryPhi users of What not to be optimized.
1144 for (auto *U : What->users())
1145 if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(Val: U))
1146 NonOptPhis.insert(V: PhiUser);
1147
1148 // Replace all our users with our defining access.
1149 What->replaceAllUsesWith(V: What->getDefiningAccess());
1150
1151 // Let MemorySSA take care of moving it around in the lists.
1152 MSSA->moveTo(What, BB, Where);
1153
1154 // Now reinsert it into the IR and do whatever fixups needed.
1155 if (auto *MD = dyn_cast<MemoryDef>(Val: What))
1156 insertDef(MD, /*RenameUses=*/true);
1157 else
1158 insertUse(MU: cast<MemoryUse>(Val: What), /*RenameUses=*/true);
1159
1160 // Clear dangling pointers. We added all MemoryPhi users, but not all
1161 // of them are removed by fixupDefs().
1162 NonOptPhis.clear();
1163}
1164
1165// Move What before Where in the MemorySSA IR.
1166void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1167 moveTo(What, BB: Where->getBlock(), Where: Where->getIterator());
1168}
1169
1170// Move What after Where in the MemorySSA IR.
1171void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1172 moveTo(What, BB: Where->getBlock(), Where: ++Where->getIterator());
1173}
1174
1175void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
1176 MemorySSA::InsertionPlace Where) {
1177 if (Where != MemorySSA::InsertionPlace::BeforeTerminator)
1178 return moveTo(What, BB, Where);
1179
1180 if (auto *Where = MSSA->getMemoryAccess(I: BB->getTerminator()))
1181 return moveBefore(What, Where);
1182 else
1183 return moveTo(What, BB, Where: MemorySSA::InsertionPlace::End);
1184}
1185
1186// All accesses in To used to be in From. Move to end and update access lists.
1187void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
1188 Instruction *Start) {
1189
1190 MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(BB: From);
1191 if (!Accs)
1192 return;
1193
1194 assert(Start->getParent() == To && "Incorrect Start instruction");
1195 MemoryAccess *FirstInNew = nullptr;
1196 for (Instruction &I : make_range(x: Start->getIterator(), y: To->end()))
1197 if ((FirstInNew = MSSA->getMemoryAccess(I: &I)))
1198 break;
1199 if (FirstInNew) {
1200 auto *MUD = cast<MemoryUseOrDef>(Val: FirstInNew);
1201 do {
1202 auto NextIt = ++MUD->getIterator();
1203 MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
1204 ? nullptr
1205 : cast<MemoryUseOrDef>(Val: &*NextIt);
1206 MSSA->moveTo(What: MUD, BB: To, Point: MemorySSA::End);
1207 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need
1208 // to retrieve it again.
1209 Accs = MSSA->getWritableBlockAccesses(BB: From);
1210 MUD = NextMUD;
1211 } while (MUD);
1212 }
1213
1214 // If all accesses were moved and only a trivial Phi remains, we try to remove
1215 // that Phi. This is needed when From is going to be deleted.
1216 auto *Defs = MSSA->getWritableBlockDefs(BB: From);
1217 if (Defs && !Defs->empty())
1218 if (auto *Phi = dyn_cast<MemoryPhi>(Val: &*Defs->begin()))
1219 tryRemoveTrivialPhi(Phi);
1220}
1221
1222void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
1223 BasicBlock *To,
1224 Instruction *Start) {
1225 assert(MSSA->getBlockAccesses(To) == nullptr &&
1226 "To block is expected to be free of MemoryAccesses.");
1227 moveAllAccesses(From, To, Start);
1228 for (BasicBlock *Succ : successors(BB: To))
1229 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: Succ))
1230 MPhi->setIncomingBlock(I: MPhi->getBasicBlockIndex(BB: From), BB: To);
1231}
1232
1233void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
1234 Instruction *Start) {
1235 assert(From->getUniquePredecessor() == To &&
1236 "From block is expected to have a single predecessor (To).");
1237 moveAllAccesses(From, To, Start);
1238 for (BasicBlock *Succ : successors(BB: From))
1239 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: Succ))
1240 MPhi->setIncomingBlock(I: MPhi->getBasicBlockIndex(BB: From), BB: To);
1241}
1242
1243void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
1244 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
1245 bool IdenticalEdgesWereMerged) {
1246 assert(!MSSA->getWritableBlockAccesses(New) &&
1247 "Access list should be null for a new block.");
1248 MemoryPhi *Phi = MSSA->getMemoryAccess(BB: Old);
1249 if (!Phi)
1250 return;
1251 if (Old->hasNPredecessors(N: 1)) {
1252 assert(pred_size(New) == Preds.size() &&
1253 "Should have moved all predecessors.");
1254 MSSA->moveTo(What: Phi, BB: New, Point: MemorySSA::Beginning);
1255 } else {
1256 assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1257 "new immediate predecessor.");
1258 MemoryPhi *NewPhi = MSSA->createMemoryPhi(BB: New);
1259 SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
1260 // Currently only support the case of removing a single incoming edge when
1261 // identical edges were not merged.
1262 if (!IdenticalEdgesWereMerged)
1263 assert(PredsSet.size() == Preds.size() &&
1264 "If identical edges were not merged, we cannot have duplicate "
1265 "blocks in the predecessors");
1266 Phi->unorderedDeleteIncomingIf(Pred: [&](MemoryAccess *MA, BasicBlock *B) {
1267 if (PredsSet.count(Ptr: B)) {
1268 NewPhi->addIncoming(V: MA, BB: B);
1269 if (!IdenticalEdgesWereMerged)
1270 PredsSet.erase(Ptr: B);
1271 return true;
1272 }
1273 return false;
1274 });
1275 Phi->addIncoming(V: NewPhi, BB: New);
1276 tryRemoveTrivialPhi(Phi: NewPhi);
1277 }
1278}
1279
1280void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
1281 assert(!MSSA->isLiveOnEntryDef(MA) &&
1282 "Trying to remove the live on entry def");
1283 // We can only delete phi nodes if they have no uses, or we can replace all
1284 // uses with a single definition.
1285 MemoryAccess *NewDefTarget = nullptr;
1286 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Val: MA)) {
1287 // Note that it is sufficient to know that all edges of the phi node have
1288 // the same argument. If they do, by the definition of dominance frontiers
1289 // (which we used to place this phi), that argument must dominate this phi,
1290 // and thus, must dominate the phi's uses, and so we will not hit the assert
1291 // below.
1292 NewDefTarget = onlySingleValue(MP);
1293 assert((NewDefTarget || MP->use_empty()) &&
1294 "We can't delete this memory phi");
1295 } else {
1296 NewDefTarget = cast<MemoryUseOrDef>(Val: MA)->getDefiningAccess();
1297 }
1298
1299 SmallSetVector<MemoryPhi *, 4> PhisToCheck;
1300
1301 // Re-point the uses at our defining access
1302 if (!isa<MemoryUse>(Val: MA) && !MA->use_empty()) {
1303 // Reset optimized on users of this store, and reset the uses.
1304 // A few notes:
1305 // 1. This is a slightly modified version of RAUW to avoid walking the
1306 // uses twice here.
1307 // 2. If we wanted to be complete, we would have to reset the optimized
1308 // flags on users of phi nodes if doing the below makes a phi node have all
1309 // the same arguments. Instead, we prefer users to removeMemoryAccess those
1310 // phi nodes, because doing it here would be N^3.
1311 if (MA->hasValueHandle())
1312 ValueHandleBase::ValueIsRAUWd(Old: MA, New: NewDefTarget);
1313 // Note: We assume MemorySSA is not used in metadata since it's not really
1314 // part of the IR.
1315
1316 assert(NewDefTarget != MA && "Going into an infinite loop");
1317 while (!MA->use_empty()) {
1318 Use &U = *MA->use_begin();
1319 if (auto *MUD = dyn_cast<MemoryUseOrDef>(Val: U.getUser()))
1320 MUD->resetOptimized();
1321 if (OptimizePhis)
1322 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Val: U.getUser()))
1323 PhisToCheck.insert(X: MP);
1324 U.set(NewDefTarget);
1325 }
1326 }
1327
1328 // The call below to erase will destroy MA, so we can't change the order we
1329 // are doing things here
1330 MSSA->removeFromLookups(MA);
1331 MSSA->removeFromLists(MA);
1332
1333 // Optionally optimize Phi uses. This will recursively remove trivial phis.
1334 if (!PhisToCheck.empty()) {
1335 SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
1336 PhisToCheck.end()};
1337 PhisToCheck.clear();
1338
1339 unsigned PhisSize = PhisToOptimize.size();
1340 while (PhisSize-- > 0)
1341 if (MemoryPhi *MP =
1342 cast_or_null<MemoryPhi>(Val: PhisToOptimize.pop_back_val()))
1343 tryRemoveTrivialPhi(Phi: MP);
1344 }
1345}
1346
1347void MemorySSAUpdater::removeBlocks(
1348 const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
1349 // First delete all uses of BB in MemoryPhis.
1350 for (BasicBlock *BB : DeadBlocks) {
1351 Instruction *TI = BB->getTerminator();
1352 assert(TI && "Basic block expected to have a terminator instruction");
1353 for (BasicBlock *Succ : successors(I: TI))
1354 if (!DeadBlocks.count(key: Succ))
1355 if (MemoryPhi *MP = MSSA->getMemoryAccess(BB: Succ)) {
1356 MP->unorderedDeleteIncomingBlock(BB);
1357 tryRemoveTrivialPhi(Phi: MP);
1358 }
1359 // Drop all references of all accesses in BB
1360 if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
1361 for (MemoryAccess &MA : *Acc)
1362 MA.dropAllReferences();
1363 }
1364
1365 // Next, delete all memory accesses in each block
1366 for (BasicBlock *BB : DeadBlocks) {
1367 MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
1368 if (!Acc)
1369 continue;
1370 for (MemoryAccess &MA : llvm::make_early_inc_range(Range&: *Acc)) {
1371 MSSA->removeFromLookups(&MA);
1372 MSSA->removeFromLists(&MA);
1373 }
1374 }
1375}
1376
1377void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
1378 for (const auto &VH : UpdatedPHIs)
1379 if (auto *MPhi = cast_or_null<MemoryPhi>(Val: VH))
1380 tryRemoveTrivialPhi(Phi: MPhi);
1381}
1382
1383void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {
1384 const BasicBlock *BB = I->getParent();
1385 // Remove memory accesses in BB for I and all following instructions.
1386 auto BBI = I->getIterator(), BBE = BB->end();
1387 // FIXME: If this becomes too expensive, iterate until the first instruction
1388 // with a memory access, then iterate over MemoryAccesses.
1389 while (BBI != BBE)
1390 removeMemoryAccess(I: &*(BBI++));
1391 // Update phis in BB's successors to remove BB.
1392 SmallVector<WeakVH, 16> UpdatedPHIs;
1393 for (const BasicBlock *Successor : successors(BB)) {
1394 removeDuplicatePhiEdgesBetween(From: BB, To: Successor);
1395 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB: Successor)) {
1396 MPhi->unorderedDeleteIncomingBlock(BB);
1397 UpdatedPHIs.push_back(Elt: MPhi);
1398 }
1399 }
1400 // Optimize trivial phis.
1401 tryRemoveTrivialPhis(UpdatedPHIs);
1402}
1403
1404MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
1405 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1406 MemorySSA::InsertionPlace Point) {
1407 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1408 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1409 return NewAccess;
1410}
1411
1412MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
1413 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1414 assert(I->getParent() == InsertPt->getBlock() &&
1415 "New and old access must be in the same block");
1416 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1417 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1418 InsertPt->getIterator());
1419 return NewAccess;
1420}
1421
1422MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
1423 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1424 assert(I->getParent() == InsertPt->getBlock() &&
1425 "New and old access must be in the same block");
1426 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1427 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1428 ++InsertPt->getIterator());
1429 return NewAccess;
1430}
1431