LLVM  9.0.0svn
MemorySSAUpdater.cpp
Go to the documentation of this file.
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 //===----------------------------------------------------------------===//
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/SmallPtrSet.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"
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
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  PhiOps.push_back(getPreviousDefFromEnd(Pred, CachedPreviousDef));
76 
77  // Now try to simplify the ops to avoid placing a phi.
78  // This may return null if we never created a phi yet, that's okay
79  MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
80 
81  // See if we can avoid the phi by simplifying it.
82  auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
83  // If we couldn't simplify, we may have to create a phi
84  if (Result == Phi) {
85  if (!Phi)
86  Phi = MSSA->createMemoryPhi(BB);
87 
88  // See if the existing phi operands match what we need.
89  // Unlike normal SSA, we only allow one phi node per block, so we can't just
90  // create a new one.
91  if (Phi->getNumOperands() != 0) {
92  // FIXME: Figure out whether this is dead code and if so remove it.
93  if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
94  // These will have been filled in by the recursive read we did above.
95  llvm::copy(PhiOps, Phi->op_begin());
96  std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
97  }
98  } else {
99  unsigned i = 0;
100  for (auto *Pred : predecessors(BB))
101  Phi->addIncoming(&*PhiOps[i++], Pred);
102  InsertedPHIs.push_back(Phi);
103  }
104  Result = Phi;
105  }
106 
107  // Set ourselves up for the next variable by resetting visited state.
108  VisitedBlocks.erase(BB);
109  CachedPreviousDef.insert({BB, Result});
110  return Result;
111  }
112  llvm_unreachable("Should have hit one of the three cases above");
113 }
114 
115 // This starts at the memory access, and goes backwards in the block to find the
116 // previous definition. If a definition is not found the block of the access,
117 // it continues globally, creating phi nodes to ensure we have a single
118 // definition.
119 MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
120  if (auto *LocalResult = getPreviousDefInBlock(MA))
121  return LocalResult;
123  return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
124 }
125 
126 // This starts at the memory access, and goes backwards in the block to the find
127 // the previous definition. If the definition is not found in the block of the
128 // access, it returns nullptr.
129 MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
130  auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
131 
132  // It's possible there are no defs, or we got handed the first def to start.
133  if (Defs) {
134  // If this is a def, we can just use the def iterators.
135  if (!isa<MemoryUse>(MA)) {
136  auto Iter = MA->getReverseDefsIterator();
137  ++Iter;
138  if (Iter != Defs->rend())
139  return &*Iter;
140  } else {
141  // Otherwise, have to walk the all access iterator.
142  auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
143  for (auto &U : make_range(++MA->getReverseIterator(), End))
144  if (!isa<MemoryUse>(U))
145  return cast<MemoryAccess>(&U);
146  // Note that if MA comes before Defs->begin(), we won't hit a def.
147  return nullptr;
148  }
149  }
150  return nullptr;
151 }
152 
153 // This starts at the end of block
154 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
155  BasicBlock *BB,
156  DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
157  auto *Defs = MSSA->getWritableBlockDefs(BB);
158 
159  if (Defs) {
160  CachedPreviousDef.insert({BB, &*Defs->rbegin()});
161  return &*Defs->rbegin();
162  }
163 
164  return getPreviousDefRecursive(BB, CachedPreviousDef);
165 }
166 // Recurse over a set of phi uses to eliminate the trivial ones
167 MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
168  if (!Phi)
169  return nullptr;
170  TrackingVH<MemoryAccess> Res(Phi);
172  std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
173  for (auto &U : Uses) {
174  if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U)) {
175  auto OperRange = UsePhi->operands();
176  tryRemoveTrivialPhi(UsePhi, OperRange);
177  }
178  }
179  return Res;
180 }
181 
182 // Eliminate trivial phis
183 // Phis are trivial if they are defined either by themselves, or all the same
184 // argument.
185 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
186 // We recursively try to remove them.
187 template <class RangeType>
188 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
189  RangeType &Operands) {
190  // Bail out on non-opt Phis.
191  if (NonOptPhis.count(Phi))
192  return Phi;
193 
194  // Detect equal or self arguments
195  MemoryAccess *Same = nullptr;
196  for (auto &Op : Operands) {
197  // If the same or self, good so far
198  if (Op == Phi || Op == Same)
199  continue;
200  // not the same, return the phi since it's not eliminatable by us
201  if (Same)
202  return Phi;
203  Same = cast<MemoryAccess>(&*Op);
204  }
205  // Never found a non-self reference, the phi is undef
206  if (Same == nullptr)
207  return MSSA->getLiveOnEntryDef();
208  if (Phi) {
209  Phi->replaceAllUsesWith(Same);
210  removeMemoryAccess(Phi);
211  }
212 
213  // We should only end up recursing in case we replaced something, in which
214  // case, we may have made other Phis trivial.
215  return recursePhi(Same);
216 }
217 
219  InsertedPHIs.clear();
220  MU->setDefiningAccess(getPreviousDef(MU));
221  // Unlike for defs, there is no extra work to do. Because uses do not create
222  // new may-defs, there are only two cases:
223  //
224  // 1. There was a def already below us, and therefore, we should not have
225  // created a phi node because it was already needed for the def.
226  //
227  // 2. There is no def below us, and therefore, there is no extra renaming work
228  // to do.
229 }
230 
231 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
232 static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
233  MemoryAccess *NewDef) {
234  // Replace any operand with us an incoming block with the new defining
235  // access.
236  int i = MP->getBasicBlockIndex(BB);
237  assert(i != -1 && "Should have found the basic block in the phi");
238  // We can't just compare i against getNumOperands since one is signed and the
239  // other not. So use it to index into the block iterator.
240  for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
241  ++BBIter) {
242  if (*BBIter != BB)
243  break;
244  MP->setIncomingValue(i, NewDef);
245  ++i;
246  }
247 }
248 
249 // A brief description of the algorithm:
250 // First, we compute what should define the new def, using the SSA
251 // construction algorithm.
252 // Then, we update the defs below us (and any new phi nodes) in the graph to
253 // point to the correct new defs, to ensure we only have one variable, and no
254 // disconnected stores.
255 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
256  InsertedPHIs.clear();
257 
258  // See if we had a local def, and if not, go hunting.
259  MemoryAccess *DefBefore = getPreviousDef(MD);
260  bool DefBeforeSameBlock = DefBefore->getBlock() == MD->getBlock();
261 
262  // There is a def before us, which means we can replace any store/phi uses
263  // of that thing with us, since we are in the way of whatever was there
264  // before.
265  // We now define that def's memorydefs and memoryphis
266  if (DefBeforeSameBlock) {
267  for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
268  UI != UE;) {
269  Use &U = *UI++;
270  // Leave the MemoryUses alone.
271  // Also make sure we skip ourselves to avoid self references.
272  if (isa<MemoryUse>(U.getUser()) || U.getUser() == MD)
273  continue;
274  // Defs are automatically unoptimized when the user is set to MD below,
275  // because the isOptimized() call will fail to find the same ID.
276  U.set(MD);
277  }
278  }
279 
280  // and that def is now our defining access.
281  MD->setDefiningAccess(DefBefore);
282 
283  // Remember the index where we may insert new phis below.
284  unsigned NewPhiIndex = InsertedPHIs.size();
285 
286  SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
287  if (!DefBeforeSameBlock) {
288  // If there was a local def before us, we must have the same effect it
289  // did. Because every may-def is the same, any phis/etc we would create, it
290  // would also have created. If there was no local def before us, we
291  // performed a global update, and have to search all successors and make
292  // sure we update the first def in each of them (following all paths until
293  // we hit the first def along each path). This may also insert phi nodes.
294  // TODO: There are other cases we can skip this work, such as when we have a
295  // single successor, and only used a straight line of single pred blocks
296  // backwards to find the def. To make that work, we'd have to track whether
297  // getDefRecursive only ever used the single predecessor case. These types
298  // of paths also only exist in between CFG simplifications.
299 
300  // If this is the first def in the block and this insert is in an arbitrary
301  // place, compute IDF and place phis.
302  auto Iter = MD->getDefsIterator();
303  ++Iter;
304  auto IterEnd = MSSA->getBlockDefs(MD->getBlock())->end();
305  if (Iter == IterEnd) {
306  ForwardIDFCalculator IDFs(*MSSA->DT);
308  SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
309  DefiningBlocks.insert(MD->getBlock());
310  IDFs.setDefiningBlocks(DefiningBlocks);
311  IDFs.calculate(IDFBlocks);
312  SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
313  for (auto *BBIDF : IDFBlocks)
314  if (!MSSA->getMemoryAccess(BBIDF)) {
315  auto *MPhi = MSSA->createMemoryPhi(BBIDF);
316  NewInsertedPHIs.push_back(MPhi);
317  // Add the phis created into the IDF blocks to NonOptPhis, so they are
318  // not optimized out as trivial by the call to getPreviousDefFromEnd
319  // below. Once they are complete, all these Phis are added to the
320  // FixupList, and removed from NonOptPhis inside fixupDefs().
321  NonOptPhis.insert(MPhi);
322  }
323 
324  for (auto &MPhi : NewInsertedPHIs) {
325  auto *BBIDF = MPhi->getBlock();
326  for (auto *Pred : predecessors(BBIDF)) {
328  MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef),
329  Pred);
330  }
331  }
332 
333  // Re-take the index where we're adding the new phis, because the above
334  // call to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
335  NewPhiIndex = InsertedPHIs.size();
336  for (auto &MPhi : NewInsertedPHIs) {
337  InsertedPHIs.push_back(&*MPhi);
338  FixupList.push_back(&*MPhi);
339  }
340  }
341 
342  FixupList.push_back(MD);
343  }
344 
345  // Remember the index where we stopped inserting new phis above, since the
346  // fixupDefs call in the loop below may insert more, that are already minimal.
347  unsigned NewPhiIndexEnd = InsertedPHIs.size();
348 
349  while (!FixupList.empty()) {
350  unsigned StartingPHISize = InsertedPHIs.size();
351  fixupDefs(FixupList);
352  FixupList.clear();
353  // Put any new phis on the fixup list, and process them
354  FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
355  }
356 
357  // Optimize potentially non-minimal phis added in this method.
358  for (unsigned Idx = NewPhiIndex; Idx < NewPhiIndexEnd; ++Idx) {
359  if (auto *MPhi = cast_or_null<MemoryPhi>(InsertedPHIs[Idx])) {
360  auto OperRange = MPhi->operands();
361  tryRemoveTrivialPhi(MPhi, OperRange);
362  }
363  }
364 
365  // Now that all fixups are done, rename all uses if we are asked.
366  if (RenameUses) {
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) {
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 
459  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
460  MPhi->unorderedDeleteIncomingBlock(From);
461  if (MPhi->getNumIncomingValues() == 1)
462  removeMemoryAccess(MPhi);
463  }
464 }
465 
467  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  auto GetNewDefiningAccess = [&](MemoryAccess *MA) -> MemoryAccess * {
487  MemoryAccess *InsnDefining = MA;
488  if (MemoryUseOrDef *DefMUD = dyn_cast<MemoryUseOrDef>(InsnDefining)) {
489  if (!MSSA->isLiveOnEntryDef(DefMUD)) {
490  Instruction *DefMUDI = DefMUD->getMemoryInst();
491  assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
492  if (Instruction *NewDefMUDI =
493  cast_or_null<Instruction>(VMap.lookup(DefMUDI)))
494  InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
495  }
496  } else {
497  MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
498  if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
499  InsnDefining = NewDefPhi;
500  }
501  assert(InsnDefining && "Defining instruction cannot be nullptr.");
502  return InsnDefining;
503  };
504 
505  const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
506  if (!Acc)
507  return;
508  for (const MemoryAccess &MA : *Acc) {
509  if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
510  Instruction *Insn = MUD->getMemoryInst();
511  // Entry does not exist if the clone of the block did not clone all
512  // instructions. This occurs in LoopRotate when cloning instructions
513  // from the old header to the old preheader. The cloned instruction may
514  // also be a simplified Value, not an Instruction (see LoopRotate).
515  if (Instruction *NewInsn =
516  dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
517  MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
518  NewInsn, GetNewDefiningAccess(MUD->getDefiningAccess()), MUD);
519  MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
520  }
521  }
522  }
523 }
524 
526  ArrayRef<BasicBlock *> ExitBlocks,
527  const ValueToValueMapTy &VMap,
528  bool IgnoreIncomingWithNoClones) {
529  PhiToDefMap MPhiMap;
530 
531  auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
532  assert(Phi && NewPhi && "Invalid Phi nodes.");
533  BasicBlock *NewPhiBB = NewPhi->getBlock();
534  SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
535  pred_end(NewPhiBB));
536  for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
537  MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
538  BasicBlock *IncBB = Phi->getIncomingBlock(It);
539 
540  if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
541  IncBB = NewIncBB;
542  else if (IgnoreIncomingWithNoClones)
543  continue;
544 
545  // Now we have IncBB, and will need to add incoming from it to NewPhi.
546 
547  // If IncBB is not a predecessor of NewPhiBB, then do not add it.
548  // NewPhiBB was cloned without that edge.
549  if (!NewPhiBBPreds.count(IncBB))
550  continue;
551 
552  // Determine incoming value and add it as incoming from IncBB.
553  if (MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
554  if (!MSSA->isLiveOnEntryDef(IncMUD)) {
555  Instruction *IncI = IncMUD->getMemoryInst();
556  assert(IncI && "Found MemoryUseOrDef with no Instruction.");
557  if (Instruction *NewIncI =
558  cast_or_null<Instruction>(VMap.lookup(IncI))) {
559  IncMUD = MSSA->getMemoryAccess(NewIncI);
560  assert(IncMUD &&
561  "MemoryUseOrDef cannot be null, all preds processed.");
562  }
563  }
564  NewPhi->addIncoming(IncMUD, IncBB);
565  } else {
566  MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
567  if (MemoryAccess *NewDefPhi = MPhiMap.lookup(IncPhi))
568  NewPhi->addIncoming(NewDefPhi, IncBB);
569  else
570  NewPhi->addIncoming(IncPhi, IncBB);
571  }
572  }
573  };
574 
575  auto ProcessBlock = [&](BasicBlock *BB) {
576  BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
577  if (!NewBlock)
578  return;
579 
580  assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
581  "Cloned block should have no accesses");
582 
583  // Add MemoryPhi.
584  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
585  MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
586  MPhiMap[MPhi] = NewPhi;
587  }
588  // Update Uses and Defs.
589  cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap);
590  };
591 
592  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
593  ProcessBlock(BB);
594 
595  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
596  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
597  if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
598  FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
599 }
600 
602  BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
603  // All defs/phis from outside BB that are used in BB, are valid uses in P1.
604  // Since those defs/phis must have dominated BB, and also dominate P1.
605  // Defs from BB being used in BB will be replaced with the cloned defs from
606  // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
607  // incoming def into the Phi from P1.
608  PhiToDefMap MPhiMap;
609  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
610  MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
611  cloneUsesAndDefs(BB, P1, VM, MPhiMap);
612 }
613 
614 template <typename Iter>
615 void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
616  ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
617  DominatorTree &DT) {
619  // Update/insert phis in all successors of exit blocks.
620  for (auto *Exit : ExitBlocks)
621  for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
622  if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
623  BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
624  Updates.push_back({DT.Insert, NewExit, ExitSucc});
625  }
626  applyInsertUpdates(Updates, DT);
627 }
628 
630  ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
631  DominatorTree &DT) {
632  const ValueToValueMapTy *const Arr[] = {&VMap};
633  privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
634  std::end(Arr), DT);
635 }
636 
638  ArrayRef<BasicBlock *> ExitBlocks,
639  ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
640  auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
641  return I.get();
642  };
643  using MappedIteratorType =
645  decltype(GetPtr)>;
646  auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
647  auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
648  privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
649 }
650 
652  DominatorTree &DT) {
653  SmallVector<CFGUpdate, 4> RevDeleteUpdates;
654  SmallVector<CFGUpdate, 4> InsertUpdates;
655  for (auto &Update : Updates) {
656  if (Update.getKind() == DT.Insert)
657  InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
658  else
659  RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
660  }
661 
662  if (!RevDeleteUpdates.empty()) {
663  // Update for inserted edges: use newDT and snapshot CFG as if deletes had
664  // not occurred.
665  // FIXME: This creates a new DT, so it's more expensive to do mix
666  // delete/inserts vs just inserts. We can do an incremental update on the DT
667  // to revert deletes, than re-delete the edges. Teaching DT to do this, is
668  // part of a pending cleanup.
669  DominatorTree NewDT(DT, RevDeleteUpdates);
670  GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
671  applyInsertUpdates(InsertUpdates, NewDT, &GD);
672  } else {
674  applyInsertUpdates(InsertUpdates, DT, &GD);
675  }
676 
677  // Update for deleted edges
678  for (auto &Update : RevDeleteUpdates)
679  removeEdge(Update.getFrom(), Update.getTo());
680 }
681 
683  DominatorTree &DT) {
685  applyInsertUpdates(Updates, DT, &GD);
686 }
687 
689  DominatorTree &DT,
690  const GraphDiff<BasicBlock *> *GD) {
691  // Get recursive last Def, assuming well formed MSSA and updated DT.
692  auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
693  while (true) {
694  MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
695  // Return last Def or Phi in BB, if it exists.
696  if (Defs)
697  return &*(--Defs->end());
698 
699  // Check number of predecessors, we only care if there's more than one.
700  unsigned Count = 0;
701  BasicBlock *Pred = nullptr;
702  for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
703  Pred = Pair.second;
704  Count++;
705  if (Count == 2)
706  break;
707  }
708 
709  // If BB has multiple predecessors, get last definition from IDom.
710  if (Count != 1) {
711  // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
712  // DT is invalidated. Return LoE as its last def. This will be added to
713  // MemoryPhi node, and later deleted when the block is deleted.
714  if (!DT.getNode(BB))
715  return MSSA->getLiveOnEntryDef();
716  if (auto *IDom = DT.getNode(BB)->getIDom())
717  if (IDom->getBlock() != BB) {
718  BB = IDom->getBlock();
719  continue;
720  }
721  return MSSA->getLiveOnEntryDef();
722  } else {
723  // Single predecessor, BB cannot be dead. GetLastDef of Pred.
724  assert(Count == 1 && Pred && "Single predecessor expected.");
725  BB = Pred;
726  }
727  };
728  llvm_unreachable("Unable to get last definition.");
729  };
730 
731  // Get nearest IDom given a set of blocks.
732  // TODO: this can be optimized by starting the search at the node with the
733  // lowest level (highest in the tree).
734  auto FindNearestCommonDominator =
735  [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
736  BasicBlock *PrevIDom = *BBSet.begin();
737  for (auto *BB : BBSet)
738  PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
739  return PrevIDom;
740  };
741 
742  // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
743  // include CurrIDom.
744  auto GetNoLongerDomBlocks =
745  [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
746  SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
747  if (PrevIDom == CurrIDom)
748  return;
749  BlocksPrevDom.push_back(PrevIDom);
750  BasicBlock *NextIDom = PrevIDom;
751  while (BasicBlock *UpIDom =
752  DT.getNode(NextIDom)->getIDom()->getBlock()) {
753  if (UpIDom == CurrIDom)
754  break;
755  BlocksPrevDom.push_back(UpIDom);
756  NextIDom = UpIDom;
757  }
758  };
759 
760  // Map a BB to its predecessors: added + previously existing. To get a
761  // deterministic order, store predecessors as SetVectors. The order in each
762  // will be defined by the order in Updates (fixed) and the order given by
763  // children<> (also fixed). Since we further iterate over these ordered sets,
764  // we lose the information of multiple edges possibly existing between two
765  // blocks, so we'll keep and EdgeCount map for that.
766  // An alternate implementation could keep unordered set for the predecessors,
767  // traverse either Updates or children<> each time to get the deterministic
768  // order, and drop the usage of EdgeCount. This alternate approach would still
769  // require querying the maps for each predecessor, and children<> call has
770  // additional computation inside for creating the snapshot-graph predecessors.
771  // As such, we favor using a little additional storage and less compute time.
772  // This decision can be revisited if we find the alternative more favorable.
773 
774  struct PredInfo {
777  };
779 
780  for (auto &Edge : Updates) {
781  BasicBlock *BB = Edge.getTo();
782  auto &AddedBlockSet = PredMap[BB].Added;
783  AddedBlockSet.insert(Edge.getFrom());
784  }
785 
786  // Store all existing predecessor for each BB, at least one must exist.
789  for (auto &BBPredPair : PredMap) {
790  auto *BB = BBPredPair.first;
791  const auto &AddedBlockSet = BBPredPair.second.Added;
792  auto &PrevBlockSet = BBPredPair.second.Prev;
793  for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
794  BasicBlock *Pi = Pair.second;
795  if (!AddedBlockSet.count(Pi))
796  PrevBlockSet.insert(Pi);
797  EdgeCountMap[{Pi, BB}]++;
798  }
799 
800  if (PrevBlockSet.empty()) {
801  assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
802  LLVM_DEBUG(
803  dbgs()
804  << "Adding a predecessor to a block with no predecessors. "
805  "This must be an edge added to a new, likely cloned, block. "
806  "Its memory accesses must be already correct, assuming completed "
807  "via the updateExitBlocksForClonedLoop API. "
808  "Assert a single such edge is added so no phi addition or "
809  "additional processing is required.\n");
810  assert(AddedBlockSet.size() == 1 &&
811  "Can only handle adding one predecessor to a new block.");
812  // Need to remove new blocks from PredMap. Remove below to not invalidate
813  // iterator here.
814  NewBlocks.insert(BB);
815  }
816  }
817  // Nothing to process for new/cloned blocks.
818  for (auto *BB : NewBlocks)
819  PredMap.erase(BB);
820 
821  SmallVector<BasicBlock *, 8> BlocksToProcess;
822  SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
823 
824  // First create MemoryPhis in all blocks that don't have one. Create in the
825  // order found in Updates, not in PredMap, to get deterministic numbering.
826  for (auto &Edge : Updates) {
827  BasicBlock *BB = Edge.getTo();
828  if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
829  MSSA->createMemoryPhi(BB);
830  }
831 
832  // Now we'll fill in the MemoryPhis with the right incoming values.
833  for (auto &BBPredPair : PredMap) {
834  auto *BB = BBPredPair.first;
835  const auto &PrevBlockSet = BBPredPair.second.Prev;
836  const auto &AddedBlockSet = BBPredPair.second.Added;
837  assert(!PrevBlockSet.empty() &&
838  "At least one previous predecessor must exist.");
839 
840  // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
841  // keeping this map before the loop. We can reuse already populated entries
842  // if an edge is added from the same predecessor to two different blocks,
843  // and this does happen in rotate. Note that the map needs to be updated
844  // when deleting non-necessary phis below, if the phi is in the map by
845  // replacing the value with DefP1.
847  for (auto *AddedPred : AddedBlockSet) {
848  auto *DefPn = GetLastDef(AddedPred);
849  assert(DefPn != nullptr && "Unable to find last definition.");
850  LastDefAddedPred[AddedPred] = DefPn;
851  }
852 
853  MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
854  // If Phi is not empty, add an incoming edge from each added pred. Must
855  // still compute blocks with defs to replace for this block below.
856  if (NewPhi->getNumOperands()) {
857  for (auto *Pred : AddedBlockSet) {
858  auto *LastDefForPred = LastDefAddedPred[Pred];
859  for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
860  NewPhi->addIncoming(LastDefForPred, Pred);
861  }
862  } else {
863  // Pick any existing predecessor and get its definition. All other
864  // existing predecessors should have the same one, since no phi existed.
865  auto *P1 = *PrevBlockSet.begin();
866  MemoryAccess *DefP1 = GetLastDef(P1);
867 
868  // Check DefP1 against all Defs in LastDefPredPair. If all the same,
869  // nothing to add.
870  bool InsertPhi = false;
871  for (auto LastDefPredPair : LastDefAddedPred)
872  if (DefP1 != LastDefPredPair.second) {
873  InsertPhi = true;
874  break;
875  }
876  if (!InsertPhi) {
877  // Since NewPhi may be used in other newly added Phis, replace all uses
878  // of NewPhi with the definition coming from all predecessors (DefP1),
879  // before deleting it.
880  NewPhi->replaceAllUsesWith(DefP1);
881  removeMemoryAccess(NewPhi);
882  continue;
883  }
884 
885  // Update Phi with new values for new predecessors and old value for all
886  // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
887  // sets, the order of entries in NewPhi is deterministic.
888  for (auto *Pred : AddedBlockSet) {
889  auto *LastDefForPred = LastDefAddedPred[Pred];
890  for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
891  NewPhi->addIncoming(LastDefForPred, Pred);
892  }
893  for (auto *Pred : PrevBlockSet)
894  for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
895  NewPhi->addIncoming(DefP1, Pred);
896 
897  // Insert BB in the set of blocks that now have definition. We'll use this
898  // to compute IDF and add Phis there next.
899  BlocksToProcess.push_back(BB);
900  }
901 
902  // Get all blocks that used to dominate BB and no longer do after adding
903  // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
904  assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
905  BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
906  assert(PrevIDom && "Previous IDom should exists");
907  BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
908  assert(NewIDom && "BB should have a new valid idom");
909  assert(DT.dominates(NewIDom, PrevIDom) &&
910  "New idom should dominate old idom");
911  GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
912  }
913 
914  // Compute IDF and add Phis in all IDF blocks that do not have one.
916  if (!BlocksToProcess.empty()) {
917  ForwardIDFCalculator IDFs(DT);
918  SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
919  BlocksToProcess.end());
920  IDFs.setDefiningBlocks(DefiningBlocks);
921  IDFs.calculate(IDFBlocks);
922  for (auto *BBIDF : IDFBlocks) {
923  if (auto *IDFPhi = MSSA->getMemoryAccess(BBIDF)) {
924  // Update existing Phi.
925  // FIXME: some updates may be redundant, try to optimize and skip some.
926  for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
927  IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
928  } else {
929  IDFPhi = MSSA->createMemoryPhi(BBIDF);
930  for (auto &Pair : children<GraphDiffInvBBPair>({GD, BBIDF})) {
931  BasicBlock *Pi = Pair.second;
932  IDFPhi->addIncoming(GetLastDef(Pi), Pi);
933  }
934  }
935  }
936  }
937 
938  // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
939  // longer dominate, replace those with the closest dominating def.
940  // This will also update optimized accesses, as they're also uses.
941  for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
942  if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
943  for (auto &DefToReplaceUses : *DefsList) {
944  BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
945  Value::use_iterator UI = DefToReplaceUses.use_begin(),
946  E = DefToReplaceUses.use_end();
947  for (; UI != E;) {
948  Use &U = *UI;
949  ++UI;
951  if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
952  BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
953  if (!DT.dominates(DominatingBlock, DominatedBlock))
954  U.set(GetLastDef(DominatedBlock));
955  } else {
956  BasicBlock *DominatedBlock = Usr->getBlock();
957  if (!DT.dominates(DominatingBlock, DominatedBlock)) {
958  if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
959  U.set(DomBlPhi);
960  else {
961  auto *IDom = DT.getNode(DominatedBlock)->getIDom();
962  assert(IDom && "Block must have a valid IDom.");
963  U.set(GetLastDef(IDom->getBlock()));
964  }
965  cast<MemoryUseOrDef>(Usr)->resetOptimized();
966  }
967  }
968  }
969  }
970  }
971  }
972 }
973 
974 // Move What before Where in the MemorySSA IR.
975 template <class WhereType>
976 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
977  WhereType Where) {
978  // Mark MemoryPhi users of What not to be optimized.
979  for (auto *U : What->users())
980  if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
981  NonOptPhis.insert(PhiUser);
982 
983  // Replace all our users with our defining access.
984  What->replaceAllUsesWith(What->getDefiningAccess());
985 
986  // Let MemorySSA take care of moving it around in the lists.
987  MSSA->moveTo(What, BB, Where);
988 
989  // Now reinsert it into the IR and do whatever fixups needed.
990  if (auto *MD = dyn_cast<MemoryDef>(What))
991  insertDef(MD);
992  else
993  insertUse(cast<MemoryUse>(What));
994 
995  // Clear dangling pointers. We added all MemoryPhi users, but not all
996  // of them are removed by fixupDefs().
997  NonOptPhis.clear();
998 }
999 
1000 // Move What before Where in the MemorySSA IR.
1002  moveTo(What, Where->getBlock(), Where->getIterator());
1003 }
1004 
1005 // Move What after Where in the MemorySSA IR.
1007  moveTo(What, Where->getBlock(), ++Where->getIterator());
1008 }
1009 
1011  MemorySSA::InsertionPlace Where) {
1012  return moveTo(What, BB, Where);
1013 }
1014 
1015 // All accesses in To used to be in From. Move to end and update access lists.
1016 void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
1017  Instruction *Start) {
1018 
1019  MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);
1020  if (!Accs)
1021  return;
1022 
1023  MemoryAccess *FirstInNew = nullptr;
1024  for (Instruction &I : make_range(Start->getIterator(), To->end()))
1025  if ((FirstInNew = MSSA->getMemoryAccess(&I)))
1026  break;
1027  if (!FirstInNew)
1028  return;
1029 
1030  auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
1031  do {
1032  auto NextIt = ++MUD->getIterator();
1033  MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
1034  ? nullptr
1035  : cast<MemoryUseOrDef>(&*NextIt);
1036  MSSA->moveTo(MUD, To, MemorySSA::End);
1037  // Moving MUD from Accs in the moveTo above, may delete Accs, so we need to
1038  // retrieve it again.
1039  Accs = MSSA->getWritableBlockAccesses(From);
1040  MUD = NextMUD;
1041  } while (MUD);
1042 }
1043 
1045  BasicBlock *To,
1046  Instruction *Start) {
1047  assert(MSSA->getBlockAccesses(To) == nullptr &&
1048  "To block is expected to be free of MemoryAccesses.");
1049  moveAllAccesses(From, To, Start);
1050  for (BasicBlock *Succ : successors(To))
1051  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1052  MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1053 }
1054 
1056  Instruction *Start) {
1057  assert(From->getSinglePredecessor() == To &&
1058  "From block is expected to have a single predecessor (To).");
1059  moveAllAccesses(From, To, Start);
1060  for (BasicBlock *Succ : successors(From))
1061  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1062  MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1063 }
1064 
1065 /// If all arguments of a MemoryPHI are defined by the same incoming
1066 /// argument, return that argument.
1068  MemoryAccess *MA = nullptr;
1069 
1070  for (auto &Arg : MP->operands()) {
1071  if (!MA)
1072  MA = cast<MemoryAccess>(Arg);
1073  else if (MA != Arg)
1074  return nullptr;
1075  }
1076  return MA;
1077 }
1078 
1080  BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
1081  bool IdenticalEdgesWereMerged) {
1082  assert(!MSSA->getWritableBlockAccesses(New) &&
1083  "Access list should be null for a new block.");
1084  MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
1085  if (!Phi)
1086  return;
1087  if (Old->hasNPredecessors(1)) {
1088  assert(pred_size(New) == Preds.size() &&
1089  "Should have moved all predecessors.");
1090  MSSA->moveTo(Phi, New, MemorySSA::Beginning);
1091  } else {
1092  assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1093  "new immediate predecessor.");
1094  MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
1095  SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
1096  // Currently only support the case of removing a single incoming edge when
1097  // identical edges were not merged.
1098  if (!IdenticalEdgesWereMerged)
1099  assert(PredsSet.size() == Preds.size() &&
1100  "If identical edges were not merged, we cannot have duplicate "
1101  "blocks in the predecessors");
1102  Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
1103  if (PredsSet.count(B)) {
1104  NewPhi->addIncoming(MA, B);
1105  if (!IdenticalEdgesWereMerged)
1106  PredsSet.erase(B);
1107  return true;
1108  }
1109  return false;
1110  });
1111  Phi->addIncoming(NewPhi, New);
1112  if (onlySingleValue(NewPhi))
1113  removeMemoryAccess(NewPhi);
1114  }
1115 }
1116 
1118  assert(!MSSA->isLiveOnEntryDef(MA) &&
1119  "Trying to remove the live on entry def");
1120  // We can only delete phi nodes if they have no uses, or we can replace all
1121  // uses with a single definition.
1122  MemoryAccess *NewDefTarget = nullptr;
1123  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
1124  // Note that it is sufficient to know that all edges of the phi node have
1125  // the same argument. If they do, by the definition of dominance frontiers
1126  // (which we used to place this phi), that argument must dominate this phi,
1127  // and thus, must dominate the phi's uses, and so we will not hit the assert
1128  // below.
1129  NewDefTarget = onlySingleValue(MP);
1130  assert((NewDefTarget || MP->use_empty()) &&
1131  "We can't delete this memory phi");
1132  } else {
1133  NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
1134  }
1135 
1136  SmallSetVector<MemoryPhi *, 4> PhisToCheck;
1137 
1138  // Re-point the uses at our defining access
1139  if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
1140  // Reset optimized on users of this store, and reset the uses.
1141  // A few notes:
1142  // 1. This is a slightly modified version of RAUW to avoid walking the
1143  // uses twice here.
1144  // 2. If we wanted to be complete, we would have to reset the optimized
1145  // flags on users of phi nodes if doing the below makes a phi node have all
1146  // the same arguments. Instead, we prefer users to removeMemoryAccess those
1147  // phi nodes, because doing it here would be N^3.
1148  if (MA->hasValueHandle())
1149  ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
1150  // Note: We assume MemorySSA is not used in metadata since it's not really
1151  // part of the IR.
1152 
1153  while (!MA->use_empty()) {
1154  Use &U = *MA->use_begin();
1155  if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
1156  MUD->resetOptimized();
1157  if (OptimizePhis)
1158  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
1159  PhisToCheck.insert(MP);
1160  U.set(NewDefTarget);
1161  }
1162  }
1163 
1164  // The call below to erase will destroy MA, so we can't change the order we
1165  // are doing things here
1166  MSSA->removeFromLookups(MA);
1167  MSSA->removeFromLists(MA);
1168 
1169  // Optionally optimize Phi uses. This will recursively remove trivial phis.
1170  if (!PhisToCheck.empty()) {
1171  SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
1172  PhisToCheck.end()};
1173  PhisToCheck.clear();
1174 
1175  unsigned PhisSize = PhisToOptimize.size();
1176  while (PhisSize-- > 0)
1177  if (MemoryPhi *MP =
1178  cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val())) {
1179  auto OperRange = MP->operands();
1180  tryRemoveTrivialPhi(MP, OperRange);
1181  }
1182  }
1183 }
1184 
1186  const SmallPtrSetImpl<BasicBlock *> &DeadBlocks) {
1187  // First delete all uses of BB in MemoryPhis.
1188  for (BasicBlock *BB : DeadBlocks) {
1189  Instruction *TI = BB->getTerminator();
1190  assert(TI && "Basic block expected to have a terminator instruction");
1191  for (BasicBlock *Succ : successors(TI))
1192  if (!DeadBlocks.count(Succ))
1193  if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
1194  MP->unorderedDeleteIncomingBlock(BB);
1195  if (MP->getNumIncomingValues() == 1)
1196  removeMemoryAccess(MP);
1197  }
1198  // Drop all references of all accesses in BB
1199  if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
1200  for (MemoryAccess &MA : *Acc)
1201  MA.dropAllReferences();
1202  }
1203 
1204  // Next, delete all memory accesses in each block
1205  for (BasicBlock *BB : DeadBlocks) {
1206  MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
1207  if (!Acc)
1208  continue;
1209  for (auto AB = Acc->begin(), AE = Acc->end(); AB != AE;) {
1210  MemoryAccess *MA = &*AB;
1211  ++AB;
1212  MSSA->removeFromLookups(MA);
1213  MSSA->removeFromLists(MA);
1214  }
1215  }
1216 }
1217 
1219  Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1220  MemorySSA::InsertionPlace Point) {
1221  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1222  MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1223  return NewAccess;
1224 }
1225 
1227  Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1228  assert(I->getParent() == InsertPt->getBlock() &&
1229  "New and old access must be in the same block");
1230  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1231  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1232  InsertPt->getIterator());
1233  return NewAccess;
1234 }
1235 
1237  Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1238  assert(I->getParent() == InsertPt->getBlock() &&
1239  "New and old access must be in the same block");
1240  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1241  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1242  ++InsertPt->getIterator());
1243  return NewAccess;
1244 }
use_iterator use_end()
Definition: Value.h:346
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
Definition: MemorySSA.h:799
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
Definition: BasicBlock.cpp:260
static MemoryAccess * onlySingleValue(MemoryPhi *MP)
If all arguments of a MemoryPHI are defined by the same incoming argument, return that argument...
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
void dropAllReferences()
Drop all references to operands.
Definition: User.h:294
This class represents lattice values for constants.
Definition: AllocatorList.h:23
AllAccessType::self_iterator getIterator()
Get the iterators for the all access list and the defs only list We default to the all access list...
Definition: MemorySSA.h:175
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
Definition: MemorySSA.cpp:2075
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:254
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
iterator begin() const
Definition: ArrayRef.h:136
void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess&#39;s for a given basic block.
Definition: MemorySSA.h:755
void removeBlocks(const SmallPtrSetImpl< BasicBlock *> &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
This file contains the declarations for metadata subclasses.
bool hasValueHandle() const
Return true if there is a value handle associated with this value.
Definition: Value.h:485
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:372
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
void insertUse(MemoryUse *Use)
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: MemorySSA.h:572
reverse_iterator rbegin()
Definition: BasicBlock.h:273
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
DefsOnlyType::self_iterator getDefsIterator()
Definition: MemorySSA.h:187
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
op_iterator op_begin()
Definition: User.h:229
void setIncomingValue(unsigned I, MemoryAccess *V)
Definition: MemorySSA.h:531
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
Represents read-only accesses to memory.
Definition: MemorySSA.h:316
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock *> &Visited)
Definition: MemorySSA.h:818
block_iterator block_begin()
Definition: MemorySSA.h:497
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void setDefiningBlocks(const SmallPtrSetImpl< BasicBlock *> &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG updates, analogous with the DT edge updates.
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef&#39;s and MemoryPhi&#39;s for a given basic block.
Definition: MemorySSA.h:763
void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, InsertionPlace)
Definition: MemorySSA.cpp:1574
A simple intrusive list implementation.
Definition: simple_ilist.h:78
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:170
static void ValueIsRAUWd(Value *Old, Value *New)
Definition: Value.cpp:889
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:198
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before or after an existing MemoryAccess.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
MemoryAccess * getIncomingValue(unsigned I) const
Return incoming value number x.
Definition: MemorySSA.h:530
use_iterator_impl< Use > use_iterator
Definition: Value.h:331
NodeT * getBlock() const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
static constexpr UpdateKind Insert
void set(Value *Val)
Definition: Value.h:670
AllAccessType::reverse_self_iterator getReverseIterator()
Definition: MemorySSA.h:181
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB, MemoryAccess *NewDef)
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:327
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
DomTreeNodeBase * getIDom() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void addIncoming(MemoryAccess *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: MemorySSA.h:561
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:112
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:785
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
op_iterator op_end()
Definition: User.h:231
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:115
op_range operands()
Definition: User.h:237
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, ArrayRef< BasicBlock *> ExitBlocks, const ValueToValueMapTy &VM, bool IgnoreIncomingWithNoClones=false)
Update MemorySSA after a loop was cloned, given the blocks in RPO order, the exit blocks and a 1:1 ma...
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block, with a specified clobbering defin...
Compute iterated dominance frontiers using a linear time algorithm.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:388
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
MemoryUseOrDef * createDefinedAccess(Instruction *, MemoryAccess *, const MemoryUseOrDef *Template=nullptr)
Definition: MemorySSA.cpp:1681
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false, Optional< AliasResult > AR=MayAlias)
Definition: MemorySSA.h:296
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
iterator end()
Definition: BasicBlock.h:270
void calculate(SmallVectorImpl< BasicBlock *> &IDFBlocks)
Calculate iterated dominance frontiers.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Module.h This file contains the declarations for the Module class.
iterator end() const
Definition: ArrayRef.h:137
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock *> Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
BasicBlock * getBlock() const
Definition: MemorySSA.h:156
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:124
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:739
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:244
iterator_range< user_iterator > users()
Definition: Value.h:399
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: MemorySSA.h:527
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition: MemorySSA.h:540
use_iterator use_begin()
Definition: Value.h:338
block_iterator block_end()
Definition: MemorySSA.h:508
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
Definition: CFG.h:121
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:735
reverse_iterator rend(StringRef path)
Get reverse end iterator over path.
Definition: Path.cpp:303
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:211
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:159
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
succ_range successors(Instruction *I)
Definition: CFG.h:259
DefsOnlyType::reverse_self_iterator getReverseDefsIterator()
Definition: MemorySSA.h:193
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:478
DefsList * getWritableBlockDefs(const BasicBlock *BB) const
Definition: MemorySSA.h:805
#define LLVM_DEBUG(X)
Definition: Debug.h:122
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1237
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
bool use_empty() const
Definition: Value.h:322
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143
const BasicBlock * getParent() const
Definition: Instruction.h:66
user_iterator user_end()
Definition: Value.h:383