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