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