[clang] Add test for CWG190 "Layout-compatible POD-struct types" (#121668)
[llvm-project.git] / llvm / lib / Analysis / MemorySSAUpdater.cpp
blob050b827388d3cf8d079148013814db57c5869d46
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.
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>
24 #define DEBUG_TYPE "memoryssa"
25 using namespace llvm;
27 // This is the marker algorithm from "Simple and Efficient Construction of
28 // Static Single Assignment Form"
29 // The simple, non-marker algorithm places phi nodes at any join
30 // Here, we place markers, and only place phi nodes if they end up necessary.
31 // They are only necessary if they break a cycle (IE we recursively visit
32 // ourselves again), or we discover, while getting the value of the operands,
33 // that there are two or more definitions needing to be merged.
34 // This still will leave non-minimal form in the case of irreducible control
35 // flow, where phi nodes may be in cycles with themselves, but unnecessary.
36 MemoryAccess *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(BB);
42 if (Cached != CachedPreviousDef.end())
43 return Cached->second;
45 // If this method is called from an unreachable block, return LoE.
46 if (!MSSA->DT->isReachableFromEntry(BB))
47 return MSSA->getLiveOnEntryDef();
49 if (BasicBlock *Pred = BB->getUniquePredecessor()) {
50 VisitedBlocks.insert(BB);
51 // Single predecessor case, just recurse, we can only have one definition.
52 MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
53 CachedPreviousDef.insert({BB, Result});
54 return Result;
57 if (VisitedBlocks.count(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({BB, Result});
63 return Result;
66 if (VisitedBlocks.insert(BB).second) {
67 // Mark us visited so we can detect a cycle
68 SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;
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(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(IncomingAccess);
83 } else
84 PhiOps.push_back(MSSA->getLiveOnEntryDef());
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>(MSSA->getMemoryAccess(BB));
91 // See if we can avoid the phi by simplifying it.
92 auto *Result = tryRemoveTrivialPhi(Phi, 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(SingleAccess);
99 removeMemoryAccess(Phi);
101 Result = SingleAccess;
102 } else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {
103 if (!Phi)
104 Phi = MSSA->createMemoryPhi(BB);
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(PhiOps, Phi->op_begin());
114 std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
116 } else {
117 unsigned i = 0;
118 for (auto *Pred : predecessors(BB))
119 Phi->addIncoming(&*PhiOps[i++], Pred);
120 InsertedPHIs.push_back(Phi);
122 Result = Phi;
125 // Set ourselves up for the next variable by resetting visited state.
126 VisitedBlocks.erase(BB);
127 CachedPreviousDef.insert({BB, Result});
128 return Result;
130 llvm_unreachable("Should have hit one of the three cases above");
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.
137 MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
138 if (auto *LocalResult = getPreviousDefInBlock(MA))
139 return LocalResult;
140 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
141 return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
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.
147 MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
148 auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
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>(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(MA->getBlock())->rend();
161 for (auto &U : make_range(++MA->getReverseIterator(), End))
162 if (!isa<MemoryUse>(U))
163 return cast<MemoryAccess>(&U);
164 // Note that if MA comes before Defs->begin(), we won't hit a def.
165 return nullptr;
168 return nullptr;
171 // This starts at the end of block
172 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
173 BasicBlock *BB,
174 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
175 auto *Defs = MSSA->getWritableBlockDefs(BB);
177 if (Defs) {
178 CachedPreviousDef.insert({BB, &*Defs->rbegin()});
179 return &*Defs->rbegin();
182 return getPreviousDefRecursive(BB, CachedPreviousDef);
184 // Recurse over a set of phi uses to eliminate the trivial ones
185 MemoryAccess *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(Uses));
191 for (auto &U : Uses)
192 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U))
193 tryRemoveTrivialPhi(UsePhi);
194 return Res;
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.
202 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi) {
203 assert(Phi && "Can only remove concrete Phi.");
204 auto OperRange = Phi->operands();
205 return tryRemoveTrivialPhi(Phi, OperRange);
207 template <class RangeType>
208 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
209 RangeType &Operands) {
210 // Bail out on non-opt Phis.
211 if (NonOptPhis.count(Phi))
212 return Phi;
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);
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(Same);
230 removeMemoryAccess(Phi);
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(Same);
238 void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
239 VisitedBlocks.clear();
240 InsertedPHIs.clear();
241 MU->setDefiningAccess(getPreviousDef(MU));
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.
248 // 2. There is no def below us, and therefore, there is no extra renaming work
249 // to do.
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.
256 if (!RenameUses && !InsertedPHIs.empty()) {
257 auto *Defs = MSSA->getBlockDefs(MU->getBlock());
258 (void)Defs;
259 assert((!Defs || (++Defs->begin() == Defs->end())) &&
260 "Block may have only a Phi or no defs");
263 if (RenameUses && InsertedPHIs.size()) {
264 SmallPtrSet<BasicBlock *, 16> Visited;
265 BasicBlock *StartBlock = MU->getBlock();
267 if (auto *Defs = MSSA->getWritableBlockDefs(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>(FirstDef))
272 FirstDef = MD->getDefiningAccess();
274 MSSA->renamePass(MU->getBlock(), FirstDef, Visited);
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>(MP))
280 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
284 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
285 static 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(MP->blocks(), i)) {
294 if (BlockBB != BB)
295 break;
296 MP->setIncomingValue(i, NewDef);
297 ++i;
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.
307 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
308 // Don't bother updating dead code.
309 if (!MSSA->DT->isReachableFromEntry(MD->getBlock())) {
310 MD->setDefiningAccess(MSSA->getLiveOnEntryDef());
311 return;
314 VisitedBlocks.clear();
315 InsertedPHIs.clear();
317 // See if we had a local def, and if not, go hunting.
318 MemoryAccess *DefBefore = getPreviousDef(MD);
319 bool DefBeforeSameBlock = false;
320 if (DefBefore->getBlock() == MD->getBlock() &&
321 !(isa<MemoryPhi>(DefBefore) &&
322 llvm::is_contained(InsertedPHIs, DefBefore)))
323 DefBeforeSameBlock = true;
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(MD, [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>(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.
340 // and that def is now our defining access.
341 MD->setDefiningAccess(DefBefore);
343 SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
345 SmallSet<WeakVH, 8> ExistingPhis;
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.
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;
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(MD->getBlock());
371 for (const auto &VH : InsertedPHIs)
372 if (const auto *RealPHI = cast_or_null<MemoryPhi>(VH))
373 DefiningBlocks.insert(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(BBIDF);
381 if (!MPhi) {
382 MPhi = MSSA->createMemoryPhi(BBIDF);
383 NewInsertedPHIs.push_back(MPhi);
384 } else {
385 ExistingPhis.insert(MPhi);
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(MPhi);
395 for (auto &MPhi : NewInsertedPHIs) {
396 auto *BBIDF = MPhi->getBlock();
397 for (auto *Pred : predecessors(BBIDF)) {
398 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
399 MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);
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(&*MPhi);
408 FixupList.push_back(&*MPhi);
411 FixupList.push_back(MD);
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();
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(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
426 // Optimize potentially non-minimal phis added in this method.
427 unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
428 if (NewPhiSize)
429 tryRemoveTrivialPhis(ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
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(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>(FirstDef))
442 FirstDef = MD->getDefiningAccess();
444 MSSA->renamePass(MD->getBlock(), 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>(MP);
449 if (Phi)
450 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
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>(MP);
456 if (Phi)
457 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
462 void 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>(Var);
467 if (!NewDef)
468 continue;
469 // First, see if there is a local def after the operand.
470 auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
471 auto DefIter = NewDef->getDefsIterator();
473 // The temporary Phi is being fixed, unmark it for not to optimize.
474 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))
475 NonOptPhis.erase(Phi);
477 // If there is a local def after us, we only have to rename that.
478 if (++DefIter != Defs->end()) {
479 cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
480 continue;
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(NewDef->getBlock())) {
487 if (auto *MP = MSSA->getMemoryAccess(S))
488 setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
489 else
490 Worklist.push_back(S);
493 while (!Worklist.empty()) {
494 const BasicBlock *FixupBlock = Worklist.pop_back_val();
496 // Get the first def in the block that isn't a phi node.
497 if (auto *Defs = MSSA->getWritableBlockDefs(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");
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>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
511 return;
513 // We didn't find a def, so we must continue.
514 for (const auto *S : successors(FixupBlock)) {
515 // If there is a phi node, handle it.
516 // Otherwise, put the block on the worklist
517 if (auto *MP = MSSA->getMemoryAccess(S))
518 setMemoryPhiValueForBlock(MP, 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(S).second)
523 continue;
524 Worklist.push_back(S);
531 void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
532 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
533 MPhi->unorderedDeleteIncomingBlock(From);
534 tryRemoveTrivialPhi(MPhi);
538 void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,
539 const BasicBlock *To) {
540 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
541 bool Found = false;
542 MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
543 if (From != B)
544 return false;
545 if (Found)
546 return true;
547 Found = true;
548 return false;
550 tryRemoveTrivialPhi(MPhi);
554 /// If all arguments of a MemoryPHI are defined by the same incoming
555 /// argument, return that argument.
556 static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
557 MemoryAccess *MA = nullptr;
559 for (auto &Arg : MP->operands()) {
560 if (!MA)
561 MA = cast<MemoryAccess>(Arg);
562 else if (MA != Arg)
563 return nullptr;
565 return MA;
568 static MemoryAccess *getNewDefiningAccessForClone(
569 MemoryAccess *MA, const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
570 MemorySSA *MSSA, function_ref<bool(BasicBlock *BB)> IsInClonedRegion) {
571 MemoryAccess *InsnDefining = MA;
572 if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
573 if (MSSA->isLiveOnEntryDef(DefMUD))
574 return DefMUD;
576 // If the MemoryDef is not part of the cloned region, leave it alone.
577 Instruction *DefMUDI = DefMUD->getMemoryInst();
578 assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
579 if (!IsInClonedRegion(DefMUDI->getParent()))
580 return DefMUD;
582 auto *NewDefMUDI = cast_or_null<Instruction>(VMap.lookup(DefMUDI));
583 InsnDefining = NewDefMUDI ? MSSA->getMemoryAccess(NewDefMUDI) : nullptr;
584 if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {
585 // The clone was simplified, it's no longer a MemoryDef, look up.
586 InsnDefining = getNewDefiningAccessForClone(
587 DefMUD->getDefiningAccess(), VMap, MPhiMap, MSSA, IsInClonedRegion);
589 } else {
590 MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
591 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
592 InsnDefining = NewDefPhi;
594 assert(InsnDefining && "Defining instruction cannot be nullptr.");
595 return InsnDefining;
598 void MemorySSAUpdater::cloneUsesAndDefs(
599 BasicBlock *BB, BasicBlock *NewBB, const ValueToValueMapTy &VMap,
600 PhiToDefMap &MPhiMap, function_ref<bool(BasicBlock *)> IsInClonedRegion,
601 bool CloneWasSimplified) {
602 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
603 if (!Acc)
604 return;
605 for (const MemoryAccess &MA : *Acc) {
606 if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
607 Instruction *Insn = MUD->getMemoryInst();
608 // Entry does not exist if the clone of the block did not clone all
609 // instructions. This occurs in LoopRotate when cloning instructions
610 // from the old header to the old preheader. The cloned instruction may
611 // also be a simplified Value, not an Instruction (see LoopRotate).
612 // Also in LoopRotate, even when it's an instruction, due to it being
613 // simplified, it may be a Use rather than a Def, so we cannot use MUD as
614 // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
615 if (Instruction *NewInsn =
616 dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
617 MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
618 NewInsn,
619 getNewDefiningAccessForClone(MUD->getDefiningAccess(), VMap,
620 MPhiMap, MSSA, IsInClonedRegion),
621 /*Template=*/CloneWasSimplified ? nullptr : MUD,
622 /*CreationMustSucceed=*/false);
623 if (NewUseOrDef)
624 MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
630 void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
631 BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
632 auto *MPhi = MSSA->getMemoryAccess(Header);
633 if (!MPhi)
634 return;
636 // Create phi node in the backedge block and populate it with the same
637 // incoming values as MPhi. Skip incoming values coming from Preheader.
638 auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
639 bool HasUniqueIncomingValue = true;
640 MemoryAccess *UniqueValue = nullptr;
641 for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
642 BasicBlock *IBB = MPhi->getIncomingBlock(I);
643 MemoryAccess *IV = MPhi->getIncomingValue(I);
644 if (IBB != Preheader) {
645 NewMPhi->addIncoming(IV, IBB);
646 if (HasUniqueIncomingValue) {
647 if (!UniqueValue)
648 UniqueValue = IV;
649 else if (UniqueValue != IV)
650 HasUniqueIncomingValue = false;
655 // Update incoming edges into MPhi. Remove all but the incoming edge from
656 // Preheader. Add an edge from NewMPhi
657 auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
658 MPhi->setIncomingValue(0, AccFromPreheader);
659 MPhi->setIncomingBlock(0, Preheader);
660 for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
661 MPhi->unorderedDeleteIncoming(I);
662 MPhi->addIncoming(NewMPhi, BEBlock);
664 // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
665 // replaced with the unique value.
666 tryRemoveTrivialPhi(NewMPhi);
669 void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
670 ArrayRef<BasicBlock *> ExitBlocks,
671 const ValueToValueMapTy &VMap,
672 bool IgnoreIncomingWithNoClones) {
673 SmallSetVector<BasicBlock *, 16> Blocks;
674 for (BasicBlock *BB : concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
675 Blocks.insert(BB);
677 auto IsInClonedRegion = [&](BasicBlock *BB) { return Blocks.contains(BB); };
679 PhiToDefMap MPhiMap;
680 auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
681 assert(Phi && NewPhi && "Invalid Phi nodes.");
682 BasicBlock *NewPhiBB = NewPhi->getBlock();
683 SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
684 pred_end(NewPhiBB));
685 for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
686 MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
687 BasicBlock *IncBB = Phi->getIncomingBlock(It);
689 if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
690 IncBB = NewIncBB;
691 else if (IgnoreIncomingWithNoClones)
692 continue;
694 // Now we have IncBB, and will need to add incoming from it to NewPhi.
696 // If IncBB is not a predecessor of NewPhiBB, then do not add it.
697 // NewPhiBB was cloned without that edge.
698 if (!NewPhiBBPreds.count(IncBB))
699 continue;
701 // Determine incoming value and add it as incoming from IncBB.
702 NewPhi->addIncoming(getNewDefiningAccessForClone(IncomingAccess, VMap,
703 MPhiMap, MSSA,
704 IsInClonedRegion),
705 IncBB);
707 if (auto *SingleAccess = onlySingleValue(NewPhi)) {
708 MPhiMap[Phi] = SingleAccess;
709 removeMemoryAccess(NewPhi);
713 auto ProcessBlock = [&](BasicBlock *BB) {
714 BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
715 if (!NewBlock)
716 return;
718 assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
719 "Cloned block should have no accesses");
721 // Add MemoryPhi.
722 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
723 MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
724 MPhiMap[MPhi] = NewPhi;
726 // Update Uses and Defs.
727 cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap, IsInClonedRegion);
730 for (auto *BB : Blocks)
731 ProcessBlock(BB);
733 for (auto *BB : Blocks)
734 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
735 if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
736 FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
739 void MemorySSAUpdater::updateForClonedBlockIntoPred(
740 BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
741 // All defs/phis from outside BB that are used in BB, are valid uses in P1.
742 // Since those defs/phis must have dominated BB, and also dominate P1.
743 // Defs from BB being used in BB will be replaced with the cloned defs from
744 // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
745 // incoming def into the Phi from P1.
746 // Instructions cloned into the predecessor are in practice sometimes
747 // simplified, so disable the use of the template, and create an access from
748 // scratch.
749 PhiToDefMap MPhiMap;
750 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
751 MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
752 cloneUsesAndDefs(
753 BB, P1, VM, MPhiMap, [&](BasicBlock *CheckBB) { return BB == CheckBB; },
754 /*CloneWasSimplified=*/true);
757 template <typename Iter>
758 void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
759 ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
760 DominatorTree &DT) {
761 SmallVector<CFGUpdate, 4> Updates;
762 // Update/insert phis in all successors of exit blocks.
763 for (auto *Exit : ExitBlocks)
764 for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
765 if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
766 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
767 Updates.push_back({DT.Insert, NewExit, ExitSucc});
769 applyInsertUpdates(Updates, DT);
772 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
773 ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
774 DominatorTree &DT) {
775 const ValueToValueMapTy *const Arr[] = {&VMap};
776 privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
777 std::end(Arr), DT);
780 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
781 ArrayRef<BasicBlock *> ExitBlocks,
782 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
783 auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
784 return I.get();
786 using MappedIteratorType =
787 mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
788 decltype(GetPtr)>;
789 auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
790 auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
791 privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
794 void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
795 DominatorTree &DT, bool UpdateDT) {
796 SmallVector<CFGUpdate, 4> DeleteUpdates;
797 SmallVector<CFGUpdate, 4> RevDeleteUpdates;
798 SmallVector<CFGUpdate, 4> InsertUpdates;
799 for (const auto &Update : Updates) {
800 if (Update.getKind() == DT.Insert)
801 InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
802 else {
803 DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
804 RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
808 if (!DeleteUpdates.empty()) {
809 if (!InsertUpdates.empty()) {
810 if (!UpdateDT) {
811 SmallVector<CFGUpdate, 0> Empty;
812 // Deletes are reversed applied, because this CFGView is pretending the
813 // deletes did not happen yet, hence the edges still exist.
814 DT.applyUpdates(Empty, RevDeleteUpdates);
815 } else {
816 // Apply all updates, with the RevDeleteUpdates as PostCFGView.
817 DT.applyUpdates(Updates, RevDeleteUpdates);
820 // Note: the MSSA update below doesn't distinguish between a GD with
821 // (RevDelete,false) and (Delete, true), but this matters for the DT
822 // updates above; for "children" purposes they are equivalent; but the
823 // updates themselves convey the desired update, used inside DT only.
824 GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
825 applyInsertUpdates(InsertUpdates, DT, &GD);
826 // Update DT to redelete edges; this matches the real CFG so we can
827 // perform the standard update without a postview of the CFG.
828 DT.applyUpdates(DeleteUpdates);
829 } else {
830 if (UpdateDT)
831 DT.applyUpdates(DeleteUpdates);
833 } else {
834 if (UpdateDT)
835 DT.applyUpdates(Updates);
836 GraphDiff<BasicBlock *> GD;
837 applyInsertUpdates(InsertUpdates, DT, &GD);
840 // Update for deleted edges
841 for (auto &Update : DeleteUpdates)
842 removeEdge(Update.getFrom(), Update.getTo());
845 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
846 DominatorTree &DT) {
847 GraphDiff<BasicBlock *> GD;
848 applyInsertUpdates(Updates, DT, &GD);
851 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
852 DominatorTree &DT,
853 const GraphDiff<BasicBlock *> *GD) {
854 // Get recursive last Def, assuming well formed MSSA and updated DT.
855 auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
856 while (true) {
857 MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
858 // Return last Def or Phi in BB, if it exists.
859 if (Defs)
860 return &*(--Defs->end());
862 // Check number of predecessors, we only care if there's more than one.
863 unsigned Count = 0;
864 BasicBlock *Pred = nullptr;
865 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
866 Pred = Pi;
867 Count++;
868 if (Count == 2)
869 break;
872 // If BB has multiple predecessors, get last definition from IDom.
873 if (Count != 1) {
874 // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
875 // DT is invalidated. Return LoE as its last def. This will be added to
876 // MemoryPhi node, and later deleted when the block is deleted.
877 if (!DT.getNode(BB))
878 return MSSA->getLiveOnEntryDef();
879 if (auto *IDom = DT.getNode(BB)->getIDom())
880 if (IDom->getBlock() != BB) {
881 BB = IDom->getBlock();
882 continue;
884 return MSSA->getLiveOnEntryDef();
885 } else {
886 // Single predecessor, BB cannot be dead. GetLastDef of Pred.
887 assert(Count == 1 && Pred && "Single predecessor expected.");
888 // BB can be unreachable though, return LoE if that is the case.
889 if (!DT.getNode(BB))
890 return MSSA->getLiveOnEntryDef();
891 BB = Pred;
894 llvm_unreachable("Unable to get last definition.");
897 // Get nearest IDom given a set of blocks.
898 // TODO: this can be optimized by starting the search at the node with the
899 // lowest level (highest in the tree).
900 auto FindNearestCommonDominator =
901 [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
902 BasicBlock *PrevIDom = *BBSet.begin();
903 for (auto *BB : BBSet)
904 PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
905 return PrevIDom;
908 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
909 // include CurrIDom.
910 auto GetNoLongerDomBlocks =
911 [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
912 SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
913 if (PrevIDom == CurrIDom)
914 return;
915 BlocksPrevDom.push_back(PrevIDom);
916 BasicBlock *NextIDom = PrevIDom;
917 while (BasicBlock *UpIDom =
918 DT.getNode(NextIDom)->getIDom()->getBlock()) {
919 if (UpIDom == CurrIDom)
920 break;
921 BlocksPrevDom.push_back(UpIDom);
922 NextIDom = UpIDom;
926 // Map a BB to its predecessors: added + previously existing. To get a
927 // deterministic order, store predecessors as SetVectors. The order in each
928 // will be defined by the order in Updates (fixed) and the order given by
929 // children<> (also fixed). Since we further iterate over these ordered sets,
930 // we lose the information of multiple edges possibly existing between two
931 // blocks, so we'll keep and EdgeCount map for that.
932 // An alternate implementation could keep unordered set for the predecessors,
933 // traverse either Updates or children<> each time to get the deterministic
934 // order, and drop the usage of EdgeCount. This alternate approach would still
935 // require querying the maps for each predecessor, and children<> call has
936 // additional computation inside for creating the snapshot-graph predecessors.
937 // As such, we favor using a little additional storage and less compute time.
938 // This decision can be revisited if we find the alternative more favorable.
940 struct PredInfo {
941 SmallSetVector<BasicBlock *, 2> Added;
942 SmallSetVector<BasicBlock *, 2> Prev;
944 SmallDenseMap<BasicBlock *, PredInfo> PredMap;
946 for (const auto &Edge : Updates) {
947 BasicBlock *BB = Edge.getTo();
948 auto &AddedBlockSet = PredMap[BB].Added;
949 AddedBlockSet.insert(Edge.getFrom());
952 // Store all existing predecessor for each BB, at least one must exist.
953 SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
954 SmallPtrSet<BasicBlock *, 2> NewBlocks;
955 for (auto &BBPredPair : PredMap) {
956 auto *BB = BBPredPair.first;
957 const auto &AddedBlockSet = BBPredPair.second.Added;
958 auto &PrevBlockSet = BBPredPair.second.Prev;
959 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
960 if (!AddedBlockSet.count(Pi))
961 PrevBlockSet.insert(Pi);
962 EdgeCountMap[{Pi, BB}]++;
965 if (PrevBlockSet.empty()) {
966 assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
967 LLVM_DEBUG(
968 dbgs()
969 << "Adding a predecessor to a block with no predecessors. "
970 "This must be an edge added to a new, likely cloned, block. "
971 "Its memory accesses must be already correct, assuming completed "
972 "via the updateExitBlocksForClonedLoop API. "
973 "Assert a single such edge is added so no phi addition or "
974 "additional processing is required.\n");
975 assert(AddedBlockSet.size() == 1 &&
976 "Can only handle adding one predecessor to a new block.");
977 // Need to remove new blocks from PredMap. Remove below to not invalidate
978 // iterator here.
979 NewBlocks.insert(BB);
982 // Nothing to process for new/cloned blocks.
983 for (auto *BB : NewBlocks)
984 PredMap.erase(BB);
986 SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
987 SmallVector<WeakVH, 8> InsertedPhis;
989 // First create MemoryPhis in all blocks that don't have one. Create in the
990 // order found in Updates, not in PredMap, to get deterministic numbering.
991 for (const auto &Edge : Updates) {
992 BasicBlock *BB = Edge.getTo();
993 if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
994 InsertedPhis.push_back(MSSA->createMemoryPhi(BB));
997 // Now we'll fill in the MemoryPhis with the right incoming values.
998 for (auto &BBPredPair : PredMap) {
999 auto *BB = BBPredPair.first;
1000 const auto &PrevBlockSet = BBPredPair.second.Prev;
1001 const auto &AddedBlockSet = BBPredPair.second.Added;
1002 assert(!PrevBlockSet.empty() &&
1003 "At least one previous predecessor must exist.");
1005 // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
1006 // keeping this map before the loop. We can reuse already populated entries
1007 // if an edge is added from the same predecessor to two different blocks,
1008 // and this does happen in rotate. Note that the map needs to be updated
1009 // when deleting non-necessary phis below, if the phi is in the map by
1010 // replacing the value with DefP1.
1011 SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
1012 for (auto *AddedPred : AddedBlockSet) {
1013 auto *DefPn = GetLastDef(AddedPred);
1014 assert(DefPn != nullptr && "Unable to find last definition.");
1015 LastDefAddedPred[AddedPred] = DefPn;
1018 MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
1019 // If Phi is not empty, add an incoming edge from each added pred. Must
1020 // still compute blocks with defs to replace for this block below.
1021 if (NewPhi->getNumOperands()) {
1022 for (auto *Pred : AddedBlockSet) {
1023 auto *LastDefForPred = LastDefAddedPred[Pred];
1024 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1025 NewPhi->addIncoming(LastDefForPred, Pred);
1027 } else {
1028 // Pick any existing predecessor and get its definition. All other
1029 // existing predecessors should have the same one, since no phi existed.
1030 auto *P1 = *PrevBlockSet.begin();
1031 MemoryAccess *DefP1 = GetLastDef(P1);
1033 // Check DefP1 against all Defs in LastDefPredPair. If all the same,
1034 // nothing to add.
1035 bool InsertPhi = false;
1036 for (auto LastDefPredPair : LastDefAddedPred)
1037 if (DefP1 != LastDefPredPair.second) {
1038 InsertPhi = true;
1039 break;
1041 if (!InsertPhi) {
1042 // Since NewPhi may be used in other newly added Phis, replace all uses
1043 // of NewPhi with the definition coming from all predecessors (DefP1),
1044 // before deleting it.
1045 NewPhi->replaceAllUsesWith(DefP1);
1046 removeMemoryAccess(NewPhi);
1047 continue;
1050 // Update Phi with new values for new predecessors and old value for all
1051 // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
1052 // sets, the order of entries in NewPhi is deterministic.
1053 for (auto *Pred : AddedBlockSet) {
1054 auto *LastDefForPred = LastDefAddedPred[Pred];
1055 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1056 NewPhi->addIncoming(LastDefForPred, Pred);
1058 for (auto *Pred : PrevBlockSet)
1059 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1060 NewPhi->addIncoming(DefP1, Pred);
1063 // Get all blocks that used to dominate BB and no longer do after adding
1064 // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
1065 assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
1066 BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
1067 assert(PrevIDom && "Previous IDom should exists");
1068 BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
1069 assert(NewIDom && "BB should have a new valid idom");
1070 assert(DT.dominates(NewIDom, PrevIDom) &&
1071 "New idom should dominate old idom");
1072 GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
1075 tryRemoveTrivialPhis(InsertedPhis);
1076 // Create the set of blocks that now have a definition. We'll use this to
1077 // compute IDF and add Phis there next.
1078 SmallVector<BasicBlock *, 8> BlocksToProcess;
1079 for (auto &VH : InsertedPhis)
1080 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
1081 BlocksToProcess.push_back(MPhi->getBlock());
1083 // Compute IDF and add Phis in all IDF blocks that do not have one.
1084 SmallVector<BasicBlock *, 32> IDFBlocks;
1085 if (!BlocksToProcess.empty()) {
1086 ForwardIDFCalculator IDFs(DT, GD);
1087 SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
1088 BlocksToProcess.end());
1089 IDFs.setDefiningBlocks(DefiningBlocks);
1090 IDFs.calculate(IDFBlocks);
1092 SmallSetVector<MemoryPhi *, 4> PhisToFill;
1093 // First create all needed Phis.
1094 for (auto *BBIDF : IDFBlocks)
1095 if (!MSSA->getMemoryAccess(BBIDF)) {
1096 auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);
1097 InsertedPhis.push_back(IDFPhi);
1098 PhisToFill.insert(IDFPhi);
1100 // Then update or insert their correct incoming values.
1101 for (auto *BBIDF : IDFBlocks) {
1102 auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);
1103 assert(IDFPhi && "Phi must exist");
1104 if (!PhisToFill.count(IDFPhi)) {
1105 // Update existing Phi.
1106 // FIXME: some updates may be redundant, try to optimize and skip some.
1107 for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
1108 IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
1109 } else {
1110 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BBIDF))
1111 IDFPhi->addIncoming(GetLastDef(Pi), Pi);
1116 // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
1117 // longer dominate, replace those with the closest dominating def.
1118 // This will also update optimized accesses, as they're also uses.
1119 for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
1120 if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
1121 for (auto &DefToReplaceUses : *DefsList) {
1122 BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
1123 for (Use &U : llvm::make_early_inc_range(DefToReplaceUses.uses())) {
1124 MemoryAccess *Usr = cast<MemoryAccess>(U.getUser());
1125 if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
1126 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
1127 if (!DT.dominates(DominatingBlock, DominatedBlock))
1128 U.set(GetLastDef(DominatedBlock));
1129 } else {
1130 BasicBlock *DominatedBlock = Usr->getBlock();
1131 if (!DT.dominates(DominatingBlock, DominatedBlock)) {
1132 if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
1133 U.set(DomBlPhi);
1134 else {
1135 auto *IDom = DT.getNode(DominatedBlock)->getIDom();
1136 assert(IDom && "Block must have a valid IDom.");
1137 U.set(GetLastDef(IDom->getBlock()));
1139 cast<MemoryUseOrDef>(Usr)->resetOptimized();
1146 tryRemoveTrivialPhis(InsertedPhis);
1149 // Move What before Where in the MemorySSA IR.
1150 template <class WhereType>
1151 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1152 WhereType Where) {
1153 // Mark MemoryPhi users of What not to be optimized.
1154 for (auto *U : What->users())
1155 if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
1156 NonOptPhis.insert(PhiUser);
1158 // Replace all our users with our defining access.
1159 What->replaceAllUsesWith(What->getDefiningAccess());
1161 // Let MemorySSA take care of moving it around in the lists.
1162 MSSA->moveTo(What, BB, Where);
1164 // Now reinsert it into the IR and do whatever fixups needed.
1165 if (auto *MD = dyn_cast<MemoryDef>(What))
1166 insertDef(MD, /*RenameUses=*/true);
1167 else
1168 insertUse(cast<MemoryUse>(What), /*RenameUses=*/true);
1170 // Clear dangling pointers. We added all MemoryPhi users, but not all
1171 // of them are removed by fixupDefs().
1172 NonOptPhis.clear();
1175 // Move What before Where in the MemorySSA IR.
1176 void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1177 moveTo(What, Where->getBlock(), Where->getIterator());
1180 // Move What after Where in the MemorySSA IR.
1181 void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1182 moveTo(What, Where->getBlock(), ++Where->getIterator());
1185 void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
1186 MemorySSA::InsertionPlace Where) {
1187 if (Where != MemorySSA::InsertionPlace::BeforeTerminator)
1188 return moveTo(What, BB, Where);
1190 if (auto *Where = MSSA->getMemoryAccess(BB->getTerminator()))
1191 return moveBefore(What, Where);
1192 else
1193 return moveTo(What, BB, MemorySSA::InsertionPlace::End);
1196 // All accesses in To used to be in From. Move to end and update access lists.
1197 void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
1198 Instruction *Start) {
1200 MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);
1201 if (!Accs)
1202 return;
1204 assert(Start->getParent() == To && "Incorrect Start instruction");
1205 MemoryAccess *FirstInNew = nullptr;
1206 for (Instruction &I : make_range(Start->getIterator(), To->end()))
1207 if ((FirstInNew = MSSA->getMemoryAccess(&I)))
1208 break;
1209 if (FirstInNew) {
1210 auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
1211 do {
1212 auto NextIt = ++MUD->getIterator();
1213 MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
1214 ? nullptr
1215 : cast<MemoryUseOrDef>(&*NextIt);
1216 MSSA->moveTo(MUD, To, MemorySSA::End);
1217 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need
1218 // to retrieve it again.
1219 Accs = MSSA->getWritableBlockAccesses(From);
1220 MUD = NextMUD;
1221 } while (MUD);
1224 // If all accesses were moved and only a trivial Phi remains, we try to remove
1225 // that Phi. This is needed when From is going to be deleted.
1226 auto *Defs = MSSA->getWritableBlockDefs(From);
1227 if (Defs && !Defs->empty())
1228 if (auto *Phi = dyn_cast<MemoryPhi>(&*Defs->begin()))
1229 tryRemoveTrivialPhi(Phi);
1232 void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
1233 BasicBlock *To,
1234 Instruction *Start) {
1235 assert(MSSA->getBlockAccesses(To) == nullptr &&
1236 "To block is expected to be free of MemoryAccesses.");
1237 moveAllAccesses(From, To, Start);
1238 for (BasicBlock *Succ : successors(To))
1239 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1240 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1243 void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
1244 Instruction *Start) {
1245 assert(From->getUniquePredecessor() == To &&
1246 "From block is expected to have a single predecessor (To).");
1247 moveAllAccesses(From, To, Start);
1248 for (BasicBlock *Succ : successors(From))
1249 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1250 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1253 void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
1254 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
1255 bool IdenticalEdgesWereMerged) {
1256 assert(!MSSA->getWritableBlockAccesses(New) &&
1257 "Access list should be null for a new block.");
1258 MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
1259 if (!Phi)
1260 return;
1261 if (Old->hasNPredecessors(1)) {
1262 assert(pred_size(New) == Preds.size() &&
1263 "Should have moved all predecessors.");
1264 MSSA->moveTo(Phi, New, MemorySSA::Beginning);
1265 } else {
1266 assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1267 "new immediate predecessor.");
1268 MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
1269 SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
1270 // Currently only support the case of removing a single incoming edge when
1271 // identical edges were not merged.
1272 if (!IdenticalEdgesWereMerged)
1273 assert(PredsSet.size() == Preds.size() &&
1274 "If identical edges were not merged, we cannot have duplicate "
1275 "blocks in the predecessors");
1276 Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
1277 if (PredsSet.count(B)) {
1278 NewPhi->addIncoming(MA, B);
1279 if (!IdenticalEdgesWereMerged)
1280 PredsSet.erase(B);
1281 return true;
1283 return false;
1285 Phi->addIncoming(NewPhi, New);
1286 tryRemoveTrivialPhi(NewPhi);
1290 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
1291 assert(!MSSA->isLiveOnEntryDef(MA) &&
1292 "Trying to remove the live on entry def");
1293 // We can only delete phi nodes if they have no uses, or we can replace all
1294 // uses with a single definition.
1295 MemoryAccess *NewDefTarget = nullptr;
1296 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
1297 // Note that it is sufficient to know that all edges of the phi node have
1298 // the same argument. If they do, by the definition of dominance frontiers
1299 // (which we used to place this phi), that argument must dominate this phi,
1300 // and thus, must dominate the phi's uses, and so we will not hit the assert
1301 // below.
1302 NewDefTarget = onlySingleValue(MP);
1303 assert((NewDefTarget || MP->use_empty()) &&
1304 "We can't delete this memory phi");
1305 } else {
1306 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
1309 SmallSetVector<MemoryPhi *, 4> PhisToCheck;
1311 // Re-point the uses at our defining access
1312 if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
1313 // Reset optimized on users of this store, and reset the uses.
1314 // A few notes:
1315 // 1. This is a slightly modified version of RAUW to avoid walking the
1316 // uses twice here.
1317 // 2. If we wanted to be complete, we would have to reset the optimized
1318 // flags on users of phi nodes if doing the below makes a phi node have all
1319 // the same arguments. Instead, we prefer users to removeMemoryAccess those
1320 // phi nodes, because doing it here would be N^3.
1321 if (MA->hasValueHandle())
1322 ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
1323 // Note: We assume MemorySSA is not used in metadata since it's not really
1324 // part of the IR.
1326 assert(NewDefTarget != MA && "Going into an infinite loop");
1327 while (!MA->use_empty()) {
1328 Use &U = *MA->use_begin();
1329 if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
1330 MUD->resetOptimized();
1331 if (OptimizePhis)
1332 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
1333 PhisToCheck.insert(MP);
1334 U.set(NewDefTarget);
1338 // The call below to erase will destroy MA, so we can't change the order we
1339 // are doing things here
1340 MSSA->removeFromLookups(MA);
1341 MSSA->removeFromLists(MA);
1343 // Optionally optimize Phi uses. This will recursively remove trivial phis.
1344 if (!PhisToCheck.empty()) {
1345 SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
1346 PhisToCheck.end()};
1347 PhisToCheck.clear();
1349 unsigned PhisSize = PhisToOptimize.size();
1350 while (PhisSize-- > 0)
1351 if (MemoryPhi *MP =
1352 cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val()))
1353 tryRemoveTrivialPhi(MP);
1357 void MemorySSAUpdater::removeBlocks(
1358 const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
1359 // First delete all uses of BB in MemoryPhis.
1360 for (BasicBlock *BB : DeadBlocks) {
1361 Instruction *TI = BB->getTerminator();
1362 assert(TI && "Basic block expected to have a terminator instruction");
1363 for (BasicBlock *Succ : successors(TI))
1364 if (!DeadBlocks.count(Succ))
1365 if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
1366 MP->unorderedDeleteIncomingBlock(BB);
1367 tryRemoveTrivialPhi(MP);
1369 // Drop all references of all accesses in BB
1370 if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
1371 for (MemoryAccess &MA : *Acc)
1372 MA.dropAllReferences();
1375 // Next, delete all memory accesses in each block
1376 for (BasicBlock *BB : DeadBlocks) {
1377 MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
1378 if (!Acc)
1379 continue;
1380 for (MemoryAccess &MA : llvm::make_early_inc_range(*Acc)) {
1381 MSSA->removeFromLookups(&MA);
1382 MSSA->removeFromLists(&MA);
1387 void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
1388 for (const auto &VH : UpdatedPHIs)
1389 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
1390 tryRemoveTrivialPhi(MPhi);
1393 void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {
1394 const BasicBlock *BB = I->getParent();
1395 // Remove memory accesses in BB for I and all following instructions.
1396 auto BBI = I->getIterator(), BBE = BB->end();
1397 // FIXME: If this becomes too expensive, iterate until the first instruction
1398 // with a memory access, then iterate over MemoryAccesses.
1399 while (BBI != BBE)
1400 removeMemoryAccess(&*(BBI++));
1401 // Update phis in BB's successors to remove BB.
1402 SmallVector<WeakVH, 16> UpdatedPHIs;
1403 for (const BasicBlock *Successor : successors(BB)) {
1404 removeDuplicatePhiEdgesBetween(BB, Successor);
1405 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Successor)) {
1406 MPhi->unorderedDeleteIncomingBlock(BB);
1407 UpdatedPHIs.push_back(MPhi);
1410 // Optimize trivial phis.
1411 tryRemoveTrivialPhis(UpdatedPHIs);
1414 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
1415 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1416 MemorySSA::InsertionPlace Point, bool CreationMustSucceed) {
1417 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(
1418 I, Definition, /*Template=*/nullptr, CreationMustSucceed);
1419 if (NewAccess)
1420 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1421 return NewAccess;
1424 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
1425 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1426 assert(I->getParent() == InsertPt->getBlock() &&
1427 "New and old access must be in the same block");
1428 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1429 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1430 InsertPt->getIterator());
1431 return NewAccess;
1434 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
1435 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1436 assert(I->getParent() == InsertPt->getBlock() &&
1437 "New and old access must be in the same block");
1438 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1439 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1440 ++InsertPt->getIterator());
1441 return NewAccess;