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