LLVM  6.0.0svn
MemorySSAUpdater.cpp
Go to the documentation of this file.
1 //===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------===//
9 //
10 // This file implements the MemorySSAUpdater class.
11 //
12 //===----------------------------------------------------------------===//
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/ADT/SmallSet.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/IntrinsicInst.h"
23 #include "llvm/IR/LLVMContext.h"
24 #include "llvm/IR/Metadata.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Support/Debug.h"
28 #include <algorithm>
29 
30 #define DEBUG_TYPE "memoryssa"
31 using namespace llvm;
32 
33 // This is the marker algorithm from "Simple and Efficient Construction of
34 // Static Single Assignment Form"
35 // The simple, non-marker algorithm places phi nodes at any join
36 // Here, we place markers, and only place phi nodes if they end up necessary.
37 // They are only necessary if they break a cycle (IE we recursively visit
38 // ourselves again), or we discover, while getting the value of the operands,
39 // that there are two or more definitions needing to be merged.
40 // This still will leave non-minimal form in the case of irreducible control
41 // flow, where phi nodes may be in cycles with themselves, but unnecessary.
42 MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(BasicBlock *BB) {
43  // Single predecessor case, just recurse, we can only have one definition.
44  if (BasicBlock *Pred = BB->getSinglePredecessor()) {
45  return getPreviousDefFromEnd(Pred);
46  } else if (VisitedBlocks.count(BB)) {
47  // We hit our node again, meaning we had a cycle, we must insert a phi
48  // node to break it so we have an operand. The only case this will
49  // insert useless phis is if we have irreducible control flow.
50  return MSSA->createMemoryPhi(BB);
51  } else if (VisitedBlocks.insert(BB).second) {
52  // Mark us visited so we can detect a cycle
54 
55  // Recurse to get the values in our predecessors for placement of a
56  // potential phi node. This will insert phi nodes if we cycle in order to
57  // break the cycle and have an operand.
58  for (auto *Pred : predecessors(BB))
59  PhiOps.push_back(getPreviousDefFromEnd(Pred));
60 
61  // Now try to simplify the ops to avoid placing a phi.
62  // This may return null if we never created a phi yet, that's okay
63  MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
64  bool PHIExistsButNeedsUpdate = false;
65  // See if the existing phi operands match what we need.
66  // Unlike normal SSA, we only allow one phi node per block, so we can't just
67  // create a new one.
68  if (Phi && Phi->getNumOperands() != 0)
69  if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
70  PHIExistsButNeedsUpdate = true;
71  }
72 
73  // See if we can avoid the phi by simplifying it.
74  auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
75  // If we couldn't simplify, we may have to create a phi
76  if (Result == Phi) {
77  if (!Phi)
78  Phi = MSSA->createMemoryPhi(BB);
79 
80  // These will have been filled in by the recursive read we did above.
81  if (PHIExistsButNeedsUpdate) {
82  std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
83  std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
84  } else {
85  unsigned i = 0;
86  for (auto *Pred : predecessors(BB))
87  Phi->addIncoming(PhiOps[i++], Pred);
88  InsertedPHIs.push_back(Phi);
89  }
90  Result = Phi;
91  }
92 
93  // Set ourselves up for the next variable by resetting visited state.
94  VisitedBlocks.erase(BB);
95  return Result;
96  }
97  llvm_unreachable("Should have hit one of the three cases above");
98 }
99 
100 // This starts at the memory access, and goes backwards in the block to find the
101 // previous definition. If a definition is not found the block of the access,
102 // it continues globally, creating phi nodes to ensure we have a single
103 // definition.
104 MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
105  auto *LocalResult = getPreviousDefInBlock(MA);
106 
107  return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock());
108 }
109 
110 // This starts at the memory access, and goes backwards in the block to the find
111 // the previous definition. If the definition is not found in the block of the
112 // access, it returns nullptr.
113 MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
114  auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
115 
116  // It's possible there are no defs, or we got handed the first def to start.
117  if (Defs) {
118  // If this is a def, we can just use the def iterators.
119  if (!isa<MemoryUse>(MA)) {
120  auto Iter = MA->getReverseDefsIterator();
121  ++Iter;
122  if (Iter != Defs->rend())
123  return &*Iter;
124  } else {
125  // Otherwise, have to walk the all access iterator.
126  auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
127  for (auto &U : make_range(++MA->getReverseIterator(), End))
128  if (!isa<MemoryUse>(U))
129  return cast<MemoryAccess>(&U);
130  // Note that if MA comes before Defs->begin(), we won't hit a def.
131  return nullptr;
132  }
133  }
134  return nullptr;
135 }
136 
137 // This starts at the end of block
138 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) {
139  auto *Defs = MSSA->getWritableBlockDefs(BB);
140 
141  if (Defs)
142  return &*Defs->rbegin();
143 
144  return getPreviousDefRecursive(BB);
145 }
146 // Recurse over a set of phi uses to eliminate the trivial ones
147 MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
148  if (!Phi)
149  return nullptr;
150  TrackingVH<MemoryAccess> Res(Phi);
152  std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
153  for (auto &U : Uses) {
154  if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U)) {
155  auto OperRange = UsePhi->operands();
156  tryRemoveTrivialPhi(UsePhi, OperRange);
157  }
158  }
159  return Res;
160 }
161 
162 // Eliminate trivial phis
163 // Phis are trivial if they are defined either by themselves, or all the same
164 // argument.
165 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
166 // We recursively try to remove them.
167 template <class RangeType>
168 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
169  RangeType &Operands) {
170  // Detect equal or self arguments
171  MemoryAccess *Same = nullptr;
172  for (auto &Op : Operands) {
173  // If the same or self, good so far
174  if (Op == Phi || Op == Same)
175  continue;
176  // not the same, return the phi since it's not eliminatable by us
177  if (Same)
178  return Phi;
179  Same = cast<MemoryAccess>(Op);
180  }
181  // Never found a non-self reference, the phi is undef
182  if (Same == nullptr)
183  return MSSA->getLiveOnEntryDef();
184  if (Phi) {
185  Phi->replaceAllUsesWith(Same);
186  removeMemoryAccess(Phi);
187  }
188 
189  // We should only end up recursing in case we replaced something, in which
190  // case, we may have made other Phis trivial.
191  return recursePhi(Same);
192 }
193 
195  InsertedPHIs.clear();
196  MU->setDefiningAccess(getPreviousDef(MU));
197  // Unlike for defs, there is no extra work to do. Because uses do not create
198  // new may-defs, there are only two cases:
199  //
200  // 1. There was a def already below us, and therefore, we should not have
201  // created a phi node because it was already needed for the def.
202  //
203  // 2. There is no def below us, and therefore, there is no extra renaming work
204  // to do.
205 }
206 
207 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
208 static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
209  MemoryAccess *NewDef) {
210  // Replace any operand with us an incoming block with the new defining
211  // access.
212  int i = MP->getBasicBlockIndex(BB);
213  assert(i != -1 && "Should have found the basic block in the phi");
214  // We can't just compare i against getNumOperands since one is signed and the
215  // other not. So use it to index into the block iterator.
216  for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
217  ++BBIter) {
218  if (*BBIter != BB)
219  break;
220  MP->setIncomingValue(i, NewDef);
221  ++i;
222  }
223 }
224 
225 // A brief description of the algorithm:
226 // First, we compute what should define the new def, using the SSA
227 // construction algorithm.
228 // Then, we update the defs below us (and any new phi nodes) in the graph to
229 // point to the correct new defs, to ensure we only have one variable, and no
230 // disconnected stores.
231 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
232  InsertedPHIs.clear();
233 
234  // See if we had a local def, and if not, go hunting.
235  MemoryAccess *DefBefore = getPreviousDefInBlock(MD);
236  bool DefBeforeSameBlock = DefBefore != nullptr;
237  if (!DefBefore)
238  DefBefore = getPreviousDefRecursive(MD->getBlock());
239 
240  // There is a def before us, which means we can replace any store/phi uses
241  // of that thing with us, since we are in the way of whatever was there
242  // before.
243  // We now define that def's memorydefs and memoryphis
244  if (DefBeforeSameBlock) {
245  for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
246  UI != UE;) {
247  Use &U = *UI++;
248  // Leave the uses alone
249  if (isa<MemoryUse>(U.getUser()))
250  continue;
251  U.set(MD);
252  }
253  }
254 
255  // and that def is now our defining access.
256  // We change them in this order otherwise we will appear in the use list
257  // above and reset ourselves.
258  MD->setDefiningAccess(DefBefore);
259 
260  SmallVector<MemoryAccess *, 8> FixupList(InsertedPHIs.begin(),
261  InsertedPHIs.end());
262  if (!DefBeforeSameBlock) {
263  // If there was a local def before us, we must have the same effect it
264  // did. Because every may-def is the same, any phis/etc we would create, it
265  // would also have created. If there was no local def before us, we
266  // performed a global update, and have to search all successors and make
267  // sure we update the first def in each of them (following all paths until
268  // we hit the first def along each path). This may also insert phi nodes.
269  // TODO: There are other cases we can skip this work, such as when we have a
270  // single successor, and only used a straight line of single pred blocks
271  // backwards to find the def. To make that work, we'd have to track whether
272  // getDefRecursive only ever used the single predecessor case. These types
273  // of paths also only exist in between CFG simplifications.
274  FixupList.push_back(MD);
275  }
276 
277  while (!FixupList.empty()) {
278  unsigned StartingPHISize = InsertedPHIs.size();
279  fixupDefs(FixupList);
280  FixupList.clear();
281  // Put any new phis on the fixup list, and process them
282  FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end());
283  }
284  // Now that all fixups are done, rename all uses if we are asked.
285  if (RenameUses) {
287  BasicBlock *StartBlock = MD->getBlock();
288  // We are guaranteed there is a def in the block, because we just got it
289  // handed to us in this function.
290  MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
291  // Convert to incoming value if it's a memorydef. A phi *is* already an
292  // incoming value.
293  if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
294  FirstDef = MD->getDefiningAccess();
295 
296  MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
297  // We just inserted a phi into this block, so the incoming value will become
298  // the phi anyway, so it does not matter what we pass.
299  for (auto *MP : InsertedPHIs)
300  MSSA->renamePass(MP->getBlock(), nullptr, Visited);
301  }
302 }
303 
304 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<MemoryAccess *> &Vars) {
307  for (auto *NewDef : Vars) {
308  // First, see if there is a local def after the operand.
309  auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
310  auto DefIter = NewDef->getDefsIterator();
311 
312  // If there is a local def after us, we only have to rename that.
313  if (++DefIter != Defs->end()) {
314  cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
315  continue;
316  }
317 
318  // Otherwise, we need to search down through the CFG.
319  // For each of our successors, handle it directly if their is a phi, or
320  // place on the fixup worklist.
321  for (const auto *S : successors(NewDef->getBlock())) {
322  if (auto *MP = MSSA->getMemoryAccess(S))
323  setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
324  else
325  Worklist.push_back(S);
326  }
327 
328  while (!Worklist.empty()) {
329  const BasicBlock *FixupBlock = Worklist.back();
330  Worklist.pop_back();
331 
332  // Get the first def in the block that isn't a phi node.
333  if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
334  auto *FirstDef = &*Defs->begin();
335  // The loop above and below should have taken care of phi nodes
336  assert(!isa<MemoryPhi>(FirstDef) &&
337  "Should have already handled phi nodes!");
338  // We are now this def's defining access, make sure we actually dominate
339  // it
340  assert(MSSA->dominates(NewDef, FirstDef) &&
341  "Should have dominated the new access");
342 
343  // This may insert new phi nodes, because we are not guaranteed the
344  // block we are processing has a single pred, and depending where the
345  // store was inserted, it may require phi nodes below it.
346  cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
347  return;
348  }
349  // We didn't find a def, so we must continue.
350  for (const auto *S : successors(FixupBlock)) {
351  // If there is a phi node, handle it.
352  // Otherwise, put the block on the worklist
353  if (auto *MP = MSSA->getMemoryAccess(S))
354  setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
355  else {
356  // If we cycle, we should have ended up at a phi node that we already
357  // processed. FIXME: Double check this
358  if (!Seen.insert(S).second)
359  continue;
360  Worklist.push_back(S);
361  }
362  }
363  }
364  }
365 }
366 
367 // Move What before Where in the MemorySSA IR.
368 template <class WhereType>
369 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
370  WhereType Where) {
371  // Replace all our users with our defining access.
372  What->replaceAllUsesWith(What->getDefiningAccess());
373 
374  // Let MemorySSA take care of moving it around in the lists.
375  MSSA->moveTo(What, BB, Where);
376 
377  // Now reinsert it into the IR and do whatever fixups needed.
378  if (auto *MD = dyn_cast<MemoryDef>(What))
379  insertDef(MD);
380  else
381  insertUse(cast<MemoryUse>(What));
382 }
383 
384 // Move What before Where in the MemorySSA IR.
386  moveTo(What, Where->getBlock(), Where->getIterator());
387 }
388 
389 // Move What after Where in the MemorySSA IR.
391  moveTo(What, Where->getBlock(), ++Where->getIterator());
392 }
393 
396  return moveTo(What, BB, Where);
397 }
398 
399 /// \brief If all arguments of a MemoryPHI are defined by the same incoming
400 /// argument, return that argument.
402  MemoryAccess *MA = nullptr;
403 
404  for (auto &Arg : MP->operands()) {
405  if (!MA)
406  MA = cast<MemoryAccess>(Arg);
407  else if (MA != Arg)
408  return nullptr;
409  }
410  return MA;
411 }
412 
414  assert(!MSSA->isLiveOnEntryDef(MA) &&
415  "Trying to remove the live on entry def");
416  // We can only delete phi nodes if they have no uses, or we can replace all
417  // uses with a single definition.
418  MemoryAccess *NewDefTarget = nullptr;
419  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
420  // Note that it is sufficient to know that all edges of the phi node have
421  // the same argument. If they do, by the definition of dominance frontiers
422  // (which we used to place this phi), that argument must dominate this phi,
423  // and thus, must dominate the phi's uses, and so we will not hit the assert
424  // below.
425  NewDefTarget = onlySingleValue(MP);
426  assert((NewDefTarget || MP->use_empty()) &&
427  "We can't delete this memory phi");
428  } else {
429  NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
430  }
431 
432  // Re-point the uses at our defining access
433  if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
434  // Reset optimized on users of this store, and reset the uses.
435  // A few notes:
436  // 1. This is a slightly modified version of RAUW to avoid walking the
437  // uses twice here.
438  // 2. If we wanted to be complete, we would have to reset the optimized
439  // flags on users of phi nodes if doing the below makes a phi node have all
440  // the same arguments. Instead, we prefer users to removeMemoryAccess those
441  // phi nodes, because doing it here would be N^3.
442  if (MA->hasValueHandle())
443  ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
444  // Note: We assume MemorySSA is not used in metadata since it's not really
445  // part of the IR.
446 
447  while (!MA->use_empty()) {
448  Use &U = *MA->use_begin();
449  if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
450  MUD->resetOptimized();
451  U.set(NewDefTarget);
452  }
453  }
454 
455  // The call below to erase will destroy MA, so we can't change the order we
456  // are doing things here
457  MSSA->removeFromLookups(MA);
458  MSSA->removeFromLists(MA);
459 }
460 
462  Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
464  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
465  MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
466  return NewAccess;
467 }
468 
470  Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
471  assert(I->getParent() == InsertPt->getBlock() &&
472  "New and old access must be in the same block");
473  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
474  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
475  InsertPt->getIterator());
476  return NewAccess;
477 }
478 
480  Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
481  assert(I->getParent() == InsertPt->getBlock() &&
482  "New and old access must be in the same block");
483  MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
484  MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
485  ++InsertPt->getIterator());
486  return NewAccess;
487 }
use_iterator use_end()
Definition: Value.h:348
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
Definition: MemorySSA.h:699
static MemoryAccess * onlySingleValue(MemoryPhi *MP)
If all arguments of a MemoryPHI are defined by the same incoming argument, return that argument...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
AllAccessType::self_iterator getIterator()
Get the iterators for the all access list and the defs only list We default to the all access list...
Definition: MemorySSA.h:175
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
Definition: MemorySSA.cpp:1814
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:246
MemoryUseOrDef * createDefinedAccess(Instruction *, MemoryAccess *)
Definition: MemorySSA.cpp:1484
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:487
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:350
void insertUse(MemoryUse *Use)
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: MemorySSA.h:525
op_iterator op_begin()
Definition: User.h:214
void setIncomingValue(unsigned I, MemoryAccess *V)
Definition: MemorySSA.h:484
Represents read-only accesses to memory.
Definition: MemorySSA.h:295
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock *> &Visited)
Definition: MemorySSA.h:718
block_iterator block_begin()
Definition: MemorySSA.h:450
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, InsertionPlace)
Definition: MemorySSA.cpp:1396
void removeMemoryAccess(MemoryAccess *)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
static void ValueIsRAUWd(Value *Old, Value *New)
Definition: Value.cpp:908
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before or after an existing MemoryAccess.
void removeFromLookups(MemoryAccess *)
Properly remove MA from all of MemorySSA&#39;s lookup tables.
Definition: MemorySSA.cpp:1567
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:217
void set(Value *Val)
Definition: Value.h:677
AllAccessType::reverse_self_iterator getReverseIterator()
Definition: MemorySSA.h:181
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB, MemoryAccess *NewDef)
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:337
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
void addIncoming(MemoryAccess *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: MemorySSA.h:514
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:371
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:113
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:686
op_iterator op_end()
Definition: User.h:216
static const unsigned End
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
op_range operands()
Definition: User.h:222
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...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
MemoryUseOrDef * getMemoryAccess(const Instruction *) const
Given a memory Mod/Ref&#39;ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.cpp:1756
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getNumOperands() const
Definition: User.h:176
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
BasicBlock * getBlock() const
Definition: MemorySSA.h:156
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:110
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:640
void removeFromLists(MemoryAccess *, bool ShouldDelete=true)
Properly remove MA from all of MemorySSA&#39;s lists.
Definition: MemorySSA.cpp:1595
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:236
amdgpu Simplify well known AMD library false Value Value * Arg
use_iterator use_begin()
Definition: Value.h:340
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
block_iterator block_end()
Definition: MemorySSA.h:461
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false)
Definition: MemorySSA.h:273
#define I(x, y, z)
Definition: MD5.cpp:58
void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where)
Definition: MemorySSA.cpp:1460
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:636
reverse_iterator rend(StringRef path)
Get reverse end iterator over path.
Definition: Path.cpp:314
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:377
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
succ_range successors(BasicBlock *BB)
Definition: CFG.h:143
DefsOnlyType::reverse_self_iterator getReverseDefsIterator()
Definition: MemorySSA.h:193
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:431
DefsList * getWritableBlockDefs(const BasicBlock *BB) const
Definition: MemorySSA.h:705
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator)
Definition: MemorySSA.cpp:1428
bool use_empty() const
Definition: Value.h:328
reverse_iterator rbegin()
Definition: simple_ilist.h:122
const BasicBlock * getParent() const
Definition: Instruction.h:66
user_iterator user_end()
Definition: Value.h:385