LLVM  7.0.0svn
MemorySSA.h
Go to the documentation of this file.
1 //===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
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 /// \file
11 /// This file exposes an interface to building/using memory SSA to
12 /// walk memory instructions using a use/def graph.
13 ///
14 /// Memory SSA class builds an SSA form that links together memory access
15 /// instructions such as loads, stores, atomics, and calls. Additionally, it
16 /// does a trivial form of "heap versioning" Every time the memory state changes
17 /// in the program, we generate a new heap version. It generates
18 /// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.
19 ///
20 /// As a trivial example,
21 /// define i32 @main() #0 {
22 /// entry:
23 /// %call = call noalias i8* @_Znwm(i64 4) #2
24 /// %0 = bitcast i8* %call to i32*
25 /// %call1 = call noalias i8* @_Znwm(i64 4) #2
26 /// %1 = bitcast i8* %call1 to i32*
27 /// store i32 5, i32* %0, align 4
28 /// store i32 7, i32* %1, align 4
29 /// %2 = load i32* %0, align 4
30 /// %3 = load i32* %1, align 4
31 /// %add = add nsw i32 %2, %3
32 /// ret i32 %add
33 /// }
34 ///
35 /// Will become
36 /// define i32 @main() #0 {
37 /// entry:
38 /// ; 1 = MemoryDef(0)
39 /// %call = call noalias i8* @_Znwm(i64 4) #3
40 /// %2 = bitcast i8* %call to i32*
41 /// ; 2 = MemoryDef(1)
42 /// %call1 = call noalias i8* @_Znwm(i64 4) #3
43 /// %4 = bitcast i8* %call1 to i32*
44 /// ; 3 = MemoryDef(2)
45 /// store i32 5, i32* %2, align 4
46 /// ; 4 = MemoryDef(3)
47 /// store i32 7, i32* %4, align 4
48 /// ; MemoryUse(3)
49 /// %7 = load i32* %2, align 4
50 /// ; MemoryUse(4)
51 /// %8 = load i32* %4, align 4
52 /// %add = add nsw i32 %7, %8
53 /// ret i32 %add
54 /// }
55 ///
56 /// Given this form, all the stores that could ever effect the load at %8 can be
57 /// gotten by using the MemoryUse associated with it, and walking from use to
58 /// def until you hit the top of the function.
59 ///
60 /// Each def also has a list of users associated with it, so you can walk from
61 /// both def to users, and users to defs. Note that we disambiguate MemoryUses,
62 /// but not the RHS of MemoryDefs. You can see this above at %7, which would
63 /// otherwise be a MemoryUse(4). Being disambiguated means that for a given
64 /// store, all the MemoryUses on its use lists are may-aliases of that store
65 /// (but the MemoryDefs on its use list may not be).
66 ///
67 /// MemoryDefs are not disambiguated because it would require multiple reaching
68 /// definitions, which would require multiple phis, and multiple memoryaccesses
69 /// per instruction.
70 //
71 //===----------------------------------------------------------------------===//
72 
73 #ifndef LLVM_ANALYSIS_MEMORYSSA_H
74 #define LLVM_ANALYSIS_MEMORYSSA_H
75 
76 #include "llvm/ADT/DenseMap.h"
77 #include "llvm/ADT/GraphTraits.h"
78 #include "llvm/ADT/SmallPtrSet.h"
79 #include "llvm/ADT/SmallVector.h"
80 #include "llvm/ADT/ilist.h"
81 #include "llvm/ADT/ilist_node.h"
82 #include "llvm/ADT/iterator.h"
84 #include "llvm/ADT/simple_ilist.h"
88 #include "llvm/IR/BasicBlock.h"
89 #include "llvm/IR/DerivedUser.h"
90 #include "llvm/IR/Dominators.h"
91 #include "llvm/IR/Module.h"
92 #include "llvm/IR/Type.h"
93 #include "llvm/IR/Use.h"
94 #include "llvm/IR/User.h"
95 #include "llvm/IR/Value.h"
96 #include "llvm/IR/ValueHandle.h"
97 #include "llvm/Pass.h"
98 #include "llvm/Support/Casting.h"
99 #include <algorithm>
100 #include <cassert>
101 #include <cstddef>
102 #include <iterator>
103 #include <memory>
104 #include <utility>
105 
106 namespace llvm {
107 
108 class Function;
109 class Instruction;
110 class MemoryAccess;
111 class MemorySSAWalker;
112 class LLVMContext;
113 class raw_ostream;
114 
115 namespace MSSAHelpers {
116 
117 struct AllAccessTag {};
118 struct DefsOnlyTag {};
119 
120 } // end namespace MSSAHelpers
121 
122 enum : unsigned {
123  // Used to signify what the default invalid ID is for MemoryAccess's
124  // getID()
126 };
127 
128 template <class T> class memoryaccess_def_iterator_base;
132 
133 // The base for all memory accesses. All memory accesses in a block are
134 // linked together using an intrusive list.
136  : public DerivedUser,
137  public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
138  public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
139 public:
140  using AllAccessType =
142  using DefsOnlyType =
144 
145  MemoryAccess(const MemoryAccess &) = delete;
146  MemoryAccess &operator=(const MemoryAccess &) = delete;
147 
148  void *operator new(size_t) = delete;
149 
150  // Methods for support type inquiry through isa, cast, and
151  // dyn_cast
152  static bool classof(const Value *V) {
153  unsigned ID = V->getValueID();
154  return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal;
155  }
156 
157  BasicBlock *getBlock() const { return Block; }
158 
159  void print(raw_ostream &OS) const;
160  void dump() const;
161 
162  /// The user iterators for a memory access
165 
166  /// This iterator walks over all of the defs in a given
167  /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For
168  /// MemoryUse/MemoryDef, this walks the defining access.
169  memoryaccess_def_iterator defs_begin();
170  const_memoryaccess_def_iterator defs_begin() const;
171  memoryaccess_def_iterator defs_end();
172  const_memoryaccess_def_iterator defs_end() const;
173 
174  /// Get the iterators for the all access list and the defs only list
175  /// We default to the all access list.
177  return this->AllAccessType::getIterator();
178  }
180  return this->AllAccessType::getIterator();
181  }
183  return this->AllAccessType::getReverseIterator();
184  }
186  return this->AllAccessType::getReverseIterator();
187  }
189  return this->DefsOnlyType::getIterator();
190  }
192  return this->DefsOnlyType::getIterator();
193  }
195  return this->DefsOnlyType::getReverseIterator();
196  }
198  return this->DefsOnlyType::getReverseIterator();
199  }
200 
201 protected:
202  friend class MemoryDef;
203  friend class MemoryPhi;
204  friend class MemorySSA;
205  friend class MemoryUse;
206  friend class MemoryUseOrDef;
207 
208  /// Used by MemorySSA to change the block of a MemoryAccess when it is
209  /// moved.
210  void setBlock(BasicBlock *BB) { Block = BB; }
211 
212  /// Used for debugging and tracking things about MemoryAccesses.
213  /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
214  inline unsigned getID() const;
215 
216  MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
217  BasicBlock *BB, unsigned NumOperands)
218  : DerivedUser(Type::getVoidTy(C), Vty, nullptr, NumOperands, DeleteValue),
219  Block(BB) {}
220 
221  // Use deleteValue() to delete a generic MemoryAccess.
222  ~MemoryAccess() = default;
223 
224 private:
225  BasicBlock *Block;
226 };
227 
228 template <>
230  static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }
231 };
232 
234  MA.print(OS);
235  return OS;
236 }
237 
238 /// Class that has the common methods + fields of memory uses/defs. It's
239 /// a little awkward to have, but there are many cases where we want either a
240 /// use or def, and there are many cases where uses are needed (defs aren't
241 /// acceptable), and vice-versa.
242 ///
243 /// This class should never be instantiated directly; make a MemoryUse or
244 /// MemoryDef instead.
245 class MemoryUseOrDef : public MemoryAccess {
246 public:
247  void *operator new(size_t) = delete;
248 
250 
251  /// Get the instruction that this MemoryUse represents.
252  Instruction *getMemoryInst() const { return MemoryInstruction; }
253 
254  /// Get the access that produces the memory state used by this Use.
255  MemoryAccess *getDefiningAccess() const { return getOperand(0); }
256 
257  static bool classof(const Value *MA) {
258  return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;
259  }
260 
261  // Sadly, these have to be public because they are needed in some of the
262  // iterators.
263  inline bool isOptimized() const;
264  inline MemoryAccess *getOptimized() const;
265  inline void setOptimized(MemoryAccess *);
266 
267  // Retrieve AliasResult type of the optimized access. Ideally this would be
268  // returned by the caching walker and may go away in the future.
270  return OptimizedAccessAlias;
271  }
272 
273  /// Reset the ID of what this MemoryUse was optimized to, causing it to
274  /// be rewalked by the walker if necessary.
275  /// This really should only be called by tests.
276  inline void resetOptimized();
277 
278 protected:
279  friend class MemorySSA;
280  friend class MemorySSAUpdater;
281 
282  MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
283  DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB)
284  : MemoryAccess(C, Vty, DeleteValue, BB, 1), MemoryInstruction(MI),
285  OptimizedAccessAlias(MayAlias) {
286  setDefiningAccess(DMA);
287  }
288 
289  // Use deleteValue() to delete a generic MemoryUseOrDef.
290  ~MemoryUseOrDef() = default;
291 
293  OptimizedAccessAlias = AR;
294  }
295 
296  void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false,
298  if (!Optimized) {
299  setOperand(0, DMA);
300  return;
301  }
302  setOptimized(DMA);
303  setOptimizedAccessType(AR);
304  }
305 
306 private:
307  Instruction *MemoryInstruction;
308  Optional<AliasResult> OptimizedAccessAlias;
309 };
310 
311 template <>
313  : public FixedNumOperandTraits<MemoryUseOrDef, 1> {};
315 
316 /// Represents read-only accesses to memory
317 ///
318 /// In particular, the set of Instructions that will be represented by
319 /// MemoryUse's is exactly the set of Instructions for which
320 /// AliasAnalysis::getModRefInfo returns "Ref".
321 class MemoryUse final : public MemoryUseOrDef {
322 public:
324 
326  : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB) {}
327 
328  // allocate space for exactly one operand
329  void *operator new(size_t s) { return User::operator new(s, 1); }
330 
331  static bool classof(const Value *MA) {
332  return MA->getValueID() == MemoryUseVal;
333  }
334 
335  void print(raw_ostream &OS) const;
336 
338  OptimizedID = DMA->getID();
339  setOperand(0, DMA);
340  }
341 
342  bool isOptimized() const {
343  return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
344  }
345 
347  return getDefiningAccess();
348  }
349 
350  void resetOptimized() {
351  OptimizedID = INVALID_MEMORYACCESS_ID;
352  }
353 
354 protected:
355  friend class MemorySSA;
356 
357 private:
358  static void deleteMe(DerivedUser *Self);
359 
360  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
361 };
362 
363 template <>
364 struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
366 
367 /// Represents a read-write access to memory, whether it is a must-alias,
368 /// or a may-alias.
369 ///
370 /// In particular, the set of Instructions that will be represented by
371 /// MemoryDef's is exactly the set of Instructions for which
372 /// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
373 /// Note that, in order to provide def-def chains, all defs also have a use
374 /// associated with them. This use points to the nearest reaching
375 /// MemoryDef/MemoryPhi.
376 class MemoryDef final : public MemoryUseOrDef {
377 public:
378  friend class MemorySSA;
379 
381 
383  unsigned Ver)
384  : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB), ID(Ver) {}
385 
386  // allocate space for exactly one operand
387  void *operator new(size_t s) { return User::operator new(s, 1); }
388 
389  static bool classof(const Value *MA) {
390  return MA->getValueID() == MemoryDefVal;
391  }
392 
394  Optimized = MA;
395  OptimizedID = getDefiningAccess()->getID();
396  }
397 
399  return cast_or_null<MemoryAccess>(Optimized);
400  }
401 
402  bool isOptimized() const {
403  return getOptimized() && getDefiningAccess() &&
404  OptimizedID == getDefiningAccess()->getID();
405  }
406 
407  void resetOptimized() {
408  OptimizedID = INVALID_MEMORYACCESS_ID;
409  }
410 
411  void print(raw_ostream &OS) const;
412 
413  unsigned getID() const { return ID; }
414 
415 private:
416  static void deleteMe(DerivedUser *Self);
417 
418  const unsigned ID;
419  unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
420  WeakVH Optimized;
421 };
422 
423 template <>
424 struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 1> {};
426 
427 /// Represents phi nodes for memory accesses.
428 ///
429 /// These have the same semantic as regular phi nodes, with the exception that
430 /// only one phi will ever exist in a given basic block.
431 /// Guaranteeing one phi per block means guaranteeing there is only ever one
432 /// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
433 /// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
434 /// a MemoryPhi's operands.
435 /// That is, given
436 /// if (a) {
437 /// store %a
438 /// store %b
439 /// }
440 /// it *must* be transformed into
441 /// if (a) {
442 /// 1 = MemoryDef(liveOnEntry)
443 /// store %a
444 /// 2 = MemoryDef(1)
445 /// store %b
446 /// }
447 /// and *not*
448 /// if (a) {
449 /// 1 = MemoryDef(liveOnEntry)
450 /// store %a
451 /// 2 = MemoryDef(liveOnEntry)
452 /// store %b
453 /// }
454 /// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
455 /// end of the branch, and if there are not two phi nodes, one will be
456 /// disconnected completely from the SSA graph below that point.
457 /// Because MemoryUse's do not generate new definitions, they do not have this
458 /// issue.
459 class MemoryPhi final : public MemoryAccess {
460  // allocate space for exactly zero operands
461  void *operator new(size_t s) { return User::operator new(s); }
462 
463 public:
464  /// Provide fast operand accessors
466 
467  MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
468  : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, 0), ID(Ver),
469  ReservedSpace(NumPreds) {
470  allocHungoffUses(ReservedSpace);
471  }
472 
473  // Block iterator interface. This provides access to the list of incoming
474  // basic blocks, which parallels the list of incoming values.
477 
479  auto *Ref = reinterpret_cast<Use::UserRef *>(op_begin() + ReservedSpace);
480  return reinterpret_cast<block_iterator>(Ref + 1);
481  }
482 
484  const auto *Ref =
485  reinterpret_cast<const Use::UserRef *>(op_begin() + ReservedSpace);
486  return reinterpret_cast<const_block_iterator>(Ref + 1);
487  }
488 
489  block_iterator block_end() { return block_begin() + getNumOperands(); }
490 
492  return block_begin() + getNumOperands();
493  }
494 
496  return make_range(block_begin(), block_end());
497  }
498 
500  return make_range(block_begin(), block_end());
501  }
502 
503  op_range incoming_values() { return operands(); }
504 
505  const_op_range incoming_values() const { return operands(); }
506 
507  /// Return the number of incoming edges
508  unsigned getNumIncomingValues() const { return getNumOperands(); }
509 
510  /// Return incoming value number x
511  MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
512  void setIncomingValue(unsigned I, MemoryAccess *V) {
513  assert(V && "PHI node got a null value!");
514  setOperand(I, V);
515  }
516 
517  static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
518  static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
519 
520  /// Return incoming basic block number @p i.
521  BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
522 
523  /// Return incoming basic block corresponding
524  /// to an operand of the PHI.
525  BasicBlock *getIncomingBlock(const Use &U) const {
526  assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
527  return getIncomingBlock(unsigned(&U - op_begin()));
528  }
529 
530  /// Return incoming basic block corresponding
531  /// to value use iterator.
533  return getIncomingBlock(I.getUse());
534  }
535 
536  void setIncomingBlock(unsigned I, BasicBlock *BB) {
537  assert(BB && "PHI node got a null basic block!");
538  block_begin()[I] = BB;
539  }
540 
541  /// Add an incoming value to the end of the PHI list
543  if (getNumOperands() == ReservedSpace)
544  growOperands(); // Get more space!
545  // Initialize some new operands.
546  setNumHungOffUseOperands(getNumOperands() + 1);
547  setIncomingValue(getNumOperands() - 1, V);
548  setIncomingBlock(getNumOperands() - 1, BB);
549  }
550 
551  /// Return the first index of the specified basic
552  /// block in the value list for this PHI. Returns -1 if no instance.
553  int getBasicBlockIndex(const BasicBlock *BB) const {
554  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
555  if (block_begin()[I] == BB)
556  return I;
557  return -1;
558  }
559 
561  int Idx = getBasicBlockIndex(BB);
562  assert(Idx >= 0 && "Invalid basic block argument!");
563  return getIncomingValue(Idx);
564  }
565 
566  // After deleting incoming position I, the order of incoming may be changed.
567  void unorderedDeleteIncoming(unsigned I) {
568  unsigned E = getNumOperands();
569  assert(I < E && "Cannot remove out of bounds Phi entry.");
570  // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
571  // itself should be deleted.
572  assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
573  "at least 2 values.");
574  setIncomingValue(I, getIncomingValue(E - 1));
575  setIncomingBlock(I, block_begin()[E - 1]);
576  setOperand(E - 1, nullptr);
577  block_begin()[E - 1] = nullptr;
578  setNumHungOffUseOperands(getNumOperands() - 1);
579  }
580 
581  // After deleting entries that satisfy Pred, remaining entries may have
582  // changed order.
583  template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
584  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
585  if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
586  unorderedDeleteIncoming(I);
587  E = getNumOperands();
588  --I;
589  }
590  assert(getNumOperands() >= 1 &&
591  "Cannot remove all incoming blocks in a MemoryPhi.");
592  }
593 
594  // After deleting incoming block BB, the incoming blocks order may be changed.
596  unorderedDeleteIncomingIf(
597  [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
598  }
599 
600  // After deleting incoming memory access MA, the incoming accesses order may
601  // be changed.
603  unorderedDeleteIncomingIf(
604  [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
605  }
606 
607  static bool classof(const Value *V) {
608  return V->getValueID() == MemoryPhiVal;
609  }
610 
611  void print(raw_ostream &OS) const;
612 
613  unsigned getID() const { return ID; }
614 
615 protected:
616  friend class MemorySSA;
617 
618  /// this is more complicated than the generic
619  /// User::allocHungoffUses, because we have to allocate Uses for the incoming
620  /// values and pointers to the incoming blocks, all in one allocation.
621  void allocHungoffUses(unsigned N) {
622  User::allocHungoffUses(N, /* IsPhi */ true);
623  }
624 
625 private:
626  // For debugging only
627  const unsigned ID;
628  unsigned ReservedSpace;
629 
630  /// This grows the operand list in response to a push_back style of
631  /// operation. This grows the number of ops by 1.5 times.
632  void growOperands() {
633  unsigned E = getNumOperands();
634  // 2 op PHI nodes are VERY common, so reserve at least enough for that.
635  ReservedSpace = std::max(E + E / 2, 2u);
636  growHungoffUses(ReservedSpace, /* IsPhi */ true);
637  }
638 
639  static void deleteMe(DerivedUser *Self);
640 };
641 
642 inline unsigned MemoryAccess::getID() const {
643  assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
644  "only memory defs and phis have ids");
645  if (const auto *MD = dyn_cast<MemoryDef>(this))
646  return MD->getID();
647  return cast<MemoryPhi>(this)->getID();
648 }
649 
650 inline bool MemoryUseOrDef::isOptimized() const {
651  if (const auto *MD = dyn_cast<MemoryDef>(this))
652  return MD->isOptimized();
653  return cast<MemoryUse>(this)->isOptimized();
654 }
655 
657  if (const auto *MD = dyn_cast<MemoryDef>(this))
658  return MD->getOptimized();
659  return cast<MemoryUse>(this)->getOptimized();
660 }
661 
663  if (auto *MD = dyn_cast<MemoryDef>(this))
664  MD->setOptimized(MA);
665  else
666  cast<MemoryUse>(this)->setOptimized(MA);
667 }
668 
670  if (auto *MD = dyn_cast<MemoryDef>(this))
671  MD->resetOptimized();
672  else
673  cast<MemoryUse>(this)->resetOptimized();
674 }
675 
676 template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits<2> {};
678 
679 /// Encapsulates MemorySSA, including all data associated with memory
680 /// accesses.
681 class MemorySSA {
682 public:
684  ~MemorySSA();
685 
686  MemorySSAWalker *getWalker();
687 
688  /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
689  /// access associated with it. If passed a basic block gets the memory phi
690  /// node that exists for that block, if there is one. Otherwise, this will get
691  /// a MemoryUseOrDef.
692  MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
693  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const;
694 
695  void dump() const;
696  void print(raw_ostream &) const;
697 
698  /// Return true if \p MA represents the live on entry value
699  ///
700  /// Loads and stores from pointer arguments and other global values may be
701  /// defined by memory operations that do not occur in the current function, so
702  /// they may be live on entry to the function. MemorySSA represents such
703  /// memory state by the live on entry definition, which is guaranteed to occur
704  /// before any other memory access in the function.
705  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
706  return MA == LiveOnEntryDef.get();
707  }
708 
709  inline MemoryAccess *getLiveOnEntryDef() const {
710  return LiveOnEntryDef.get();
711  }
712 
713  // Sadly, iplists, by default, owns and deletes pointers added to the
714  // list. It's not currently possible to have two iplists for the same type,
715  // where one owns the pointers, and one does not. This is because the traits
716  // are per-type, not per-tag. If this ever changes, we should make the
717  // DefList an iplist.
719  using DefsList =
721 
722  /// Return the list of MemoryAccess's for a given basic block.
723  ///
724  /// This list is not modifiable by the user.
725  const AccessList *getBlockAccesses(const BasicBlock *BB) const {
726  return getWritableBlockAccesses(BB);
727  }
728 
729  /// Return the list of MemoryDef's and MemoryPhi's for a given basic
730  /// block.
731  ///
732  /// This list is not modifiable by the user.
733  const DefsList *getBlockDefs(const BasicBlock *BB) const {
734  return getWritableBlockDefs(BB);
735  }
736 
737  /// Given two memory accesses in the same basic block, determine
738  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
739  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
740 
741  /// Given two memory accesses in potentially different blocks,
742  /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
743  bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
744 
745  /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
746  /// dominates Use \p B.
747  bool dominates(const MemoryAccess *A, const Use &B) const;
748 
749  /// Verify that MemorySSA is self consistent (IE definitions dominate
750  /// all uses, uses appear in the right places). This is used by unit tests.
751  void verifyMemorySSA() const;
752 
753  /// Used in various insertion functions to specify whether we are talking
754  /// about the beginning or end of a block.
755  enum InsertionPlace { Beginning, End };
756 
757 protected:
758  // Used by Memory SSA annotater, dumpers, and wrapper pass
761  friend class MemorySSAUpdater;
762 
763  void verifyDefUses(Function &F) const;
764  void verifyDomination(Function &F) const;
765  void verifyOrdering(Function &F) const;
766  void verifyDominationNumbers(const Function &F) const;
767 
768  // This is used by the use optimizer and updater.
770  auto It = PerBlockAccesses.find(BB);
771  return It == PerBlockAccesses.end() ? nullptr : It->second.get();
772  }
773 
774  // This is used by the use optimizer and updater.
776  auto It = PerBlockDefs.find(BB);
777  return It == PerBlockDefs.end() ? nullptr : It->second.get();
778  }
779 
780  // These is used by the updater to perform various internal MemorySSA
781  // machinsations. They do not always leave the IR in a correct state, and
782  // relies on the updater to fixup what it breaks, so it is not public.
783 
784  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
785  void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
786 
787  // Rename the dominator tree branch rooted at BB.
788  void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
790  renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
791  }
792 
793  void removeFromLookups(MemoryAccess *);
794  void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
795  void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
797  void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
798  AccessList::iterator);
799  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
800 
801 private:
802  class CachingWalker;
803  class OptimizeUses;
804 
805  CachingWalker *getWalkerImpl();
806  void buildMemorySSA();
807  void optimizeUses();
808 
809  void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
810 
813 
814  void
815  determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
816  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
817  bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
818  MemoryPhi *createMemoryPhi(BasicBlock *BB);
819  MemoryUseOrDef *createNewAccess(Instruction *);
820  MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
821  void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
822  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
823  void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
824  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
826  bool SkipVisited = false, bool RenameAllUses = false);
827  AccessList *getOrCreateAccessList(const BasicBlock *);
828  DefsList *getOrCreateDefsList(const BasicBlock *);
829  void renumberBlock(const BasicBlock *) const;
830  AliasAnalysis *AA;
831  DominatorTree *DT;
832  Function &F;
833 
834  // Memory SSA mappings
835  DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
836 
837  // These two mappings contain the main block to access/def mappings for
838  // MemorySSA. The list contained in PerBlockAccesses really owns all the
839  // MemoryAccesses.
840  // Both maps maintain the invariant that if a block is found in them, the
841  // corresponding list is not empty, and if a block is not found in them, the
842  // corresponding list is empty.
843  AccessMap PerBlockAccesses;
844  DefsMap PerBlockDefs;
845  std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
846 
847  // Domination mappings
848  // Note that the numbering is local to a block, even though the map is
849  // global.
850  mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
851  mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
852 
853  // Memory SSA building info
854  std::unique_ptr<CachingWalker> Walker;
855  unsigned NextID;
856 };
857 
858 // Internal MemorySSA utils, for use by MemorySSA classes and walkers
860 protected:
861  friend class GVNHoist;
862  friend class MemorySSAWalker;
863 
864  // This function should not be used by new passes.
865  static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
866  AliasAnalysis &AA);
867 };
868 
869 // This pass does eager building and then printing of MemorySSA. It is used by
870 // the tests to be able to build, dump, and verify Memory SSA.
872 public:
874 
875  bool runOnFunction(Function &) override;
876  void getAnalysisUsage(AnalysisUsage &AU) const override;
877 
878  static char ID;
879 };
880 
881 /// An analysis that produces \c MemorySSA for a function.
882 ///
883 class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
885 
886  static AnalysisKey Key;
887 
888 public:
889  // Wrap MemorySSA result to ensure address stability of internal MemorySSA
890  // pointers after construction. Use a wrapper class instead of plain
891  // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
892  struct Result {
893  Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
894 
895  MemorySSA &getMSSA() { return *MSSA.get(); }
896 
897  std::unique_ptr<MemorySSA> MSSA;
898  };
899 
901 };
902 
903 /// Printer pass for \c MemorySSA.
904 class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
905  raw_ostream &OS;
906 
907 public:
908  explicit MemorySSAPrinterPass(raw_ostream &OS) : OS(OS) {}
909 
911 };
912 
913 /// Verifier pass for \c MemorySSA.
914 struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
916 };
917 
918 /// Legacy analysis pass which computes \c MemorySSA.
920 public:
922 
923  static char ID;
924 
925  bool runOnFunction(Function &) override;
926  void releaseMemory() override;
927  MemorySSA &getMSSA() { return *MSSA; }
928  const MemorySSA &getMSSA() const { return *MSSA; }
929 
930  void getAnalysisUsage(AnalysisUsage &AU) const override;
931 
932  void verifyAnalysis() const override;
933  void print(raw_ostream &OS, const Module *M = nullptr) const override;
934 
935 private:
936  std::unique_ptr<MemorySSA> MSSA;
937 };
938 
939 /// This is the generic walker interface for walkers of MemorySSA.
940 /// Walkers are used to be able to further disambiguate the def-use chains
941 /// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
942 /// you.
943 /// In particular, while the def-use chains provide basic information, and are
944 /// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
945 /// MemoryUse as AliasAnalysis considers it, a user mant want better or other
946 /// information. In particular, they may want to use SCEV info to further
947 /// disambiguate memory accesses, or they may want the nearest dominating
948 /// may-aliasing MemoryDef for a call or a store. This API enables a
949 /// standardized interface to getting and using that info.
951 public:
953  virtual ~MemorySSAWalker() = default;
954 
956 
957  /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
958  /// will give you the nearest dominating MemoryAccess that Mod's the location
959  /// the instruction accesses (by skipping any def which AA can prove does not
960  /// alias the location(s) accessed by the instruction given).
961  ///
962  /// Note that this will return a single access, and it must dominate the
963  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
964  /// this will return the MemoryPhi, not the operand. This means that
965  /// given:
966  /// if (a) {
967  /// 1 = MemoryDef(liveOnEntry)
968  /// store %a
969  /// } else {
970  /// 2 = MemoryDef(liveOnEntry)
971  /// store %b
972  /// }
973  /// 3 = MemoryPhi(2, 1)
974  /// MemoryUse(3)
975  /// load %a
976  ///
977  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
978  /// in the if (a) branch.
980  MemoryAccess *MA = MSSA->getMemoryAccess(I);
981  assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
982  return getClobberingMemoryAccess(MA);
983  }
984 
985  /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
986  /// but takes a MemoryAccess instead of an Instruction.
987  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) = 0;
988 
989  /// Given a potentially clobbering memory access and a new location,
990  /// calling this will give you the nearest dominating clobbering MemoryAccess
991  /// (by skipping non-aliasing def links).
992  ///
993  /// This version of the function is mainly used to disambiguate phi translated
994  /// pointers, where the value of a pointer may have changed from the initial
995  /// memory access. Note that this expects to be handed either a MemoryUse,
996  /// or an already potentially clobbering access. Unlike the above API, if
997  /// given a MemoryDef that clobbers the pointer as the starting access, it
998  /// will return that MemoryDef, whereas the above would return the clobber
999  /// starting from the use side of the memory def.
1000  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1001  const MemoryLocation &) = 0;
1002 
1003  /// Given a memory access, invalidate anything this walker knows about
1004  /// that access.
1005  /// This API is used by walkers that store information to perform basic cache
1006  /// invalidation. This will be called by MemorySSA at appropriate times for
1007  /// the walker it uses or returns.
1008  virtual void invalidateInfo(MemoryAccess *) {}
1009 
1010  virtual void verify(const MemorySSA *MSSA) { assert(MSSA == this->MSSA); }
1011 
1012 protected:
1013  friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
1014  // constructor.
1016 };
1017 
1018 /// A MemorySSAWalker that does no alias queries, or anything else. It
1019 /// simply returns the links as they were constructed by the builder.
1021 public:
1022  // Keep the overrides below from hiding the Instruction overload of
1023  // getClobberingMemoryAccess.
1025 
1026  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *) override;
1027  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
1028  const MemoryLocation &) override;
1029 };
1030 
1031 using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
1032 using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
1033 
1034 /// Iterator base class used to implement const and non-const iterators
1035 /// over the defining accesses of a MemoryAccess.
1036 template <class T>
1038  : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
1039  std::forward_iterator_tag, T, ptrdiff_t, T *,
1040  T *> {
1041  using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
1042 
1043 public:
1044  memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
1045  memoryaccess_def_iterator_base() = default;
1046 
1047  bool operator==(const memoryaccess_def_iterator_base &Other) const {
1048  return Access == Other.Access && (!Access || ArgNo == Other.ArgNo);
1049  }
1050 
1051  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
1052  // block from the operand in constant time (In a PHINode, the uselist has
1053  // both, so it's just subtraction). We provide it as part of the
1054  // iterator to avoid callers having to linear walk to get the block.
1055  // If the operation becomes constant time on MemoryPHI's, this bit of
1056  // abstraction breaking should be removed.
1058  MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
1059  assert(MP && "Tried to get phi arg block when not iterating over a PHI");
1060  return MP->getIncomingBlock(ArgNo);
1061  }
1062 
1063  typename BaseT::iterator::pointer operator*() const {
1064  assert(Access && "Tried to access past the end of our iterator");
1065  // Go to the first argument for phis, and the defining access for everything
1066  // else.
1067  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
1068  return MP->getIncomingValue(ArgNo);
1069  return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
1070  }
1071 
1072  using BaseT::operator++;
1074  assert(Access && "Hit end of iterator");
1075  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
1076  if (++ArgNo >= MP->getNumIncomingValues()) {
1077  ArgNo = 0;
1078  Access = nullptr;
1079  }
1080  } else {
1081  Access = nullptr;
1082  }
1083  return *this;
1084  }
1085 
1086 private:
1087  T *Access = nullptr;
1088  unsigned ArgNo = 0;
1089 };
1090 
1092  return memoryaccess_def_iterator(this);
1093 }
1094 
1096  return const_memoryaccess_def_iterator(this);
1097 }
1098 
1100  return memoryaccess_def_iterator();
1101 }
1102 
1105 }
1106 
1107 /// GraphTraits for a MemoryAccess, which walks defs in the normal case,
1108 /// and uses in the inverse case.
1109 template <> struct GraphTraits<MemoryAccess *> {
1112 
1113  static NodeRef getEntryNode(NodeRef N) { return N; }
1115  static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
1116 };
1117 
1118 template <> struct GraphTraits<Inverse<MemoryAccess *>> {
1121 
1122  static NodeRef getEntryNode(NodeRef N) { return N; }
1124  static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
1125 };
1126 
1127 /// Provide an iterator that walks defs, giving both the memory access,
1128 /// and the current pointer location, updating the pointer location as it
1129 /// changes due to phi node translation.
1130 ///
1131 /// This iterator, while somewhat specialized, is what most clients actually
1132 /// want when walking upwards through MemorySSA def chains. It takes a pair of
1133 /// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
1134 /// memory location through phi nodes for the user.
1136  : public iterator_facade_base<upward_defs_iterator,
1137  std::forward_iterator_tag,
1138  const MemoryAccessPair> {
1139  using BaseT = upward_defs_iterator::iterator_facade_base;
1140 
1141 public:
1143  : DefIterator(Info.first), Location(Info.second),
1144  OriginalAccess(Info.first) {
1145  CurrentPair.first = nullptr;
1146 
1147  WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
1148  fillInCurrentPair();
1149  }
1150 
1151  upward_defs_iterator() { CurrentPair.first = nullptr; }
1152 
1153  bool operator==(const upward_defs_iterator &Other) const {
1154  return DefIterator == Other.DefIterator;
1155  }
1156 
1157  BaseT::iterator::reference operator*() const {
1158  assert(DefIterator != OriginalAccess->defs_end() &&
1159  "Tried to access past the end of our iterator");
1160  return CurrentPair;
1161  }
1162 
1163  using BaseT::operator++;
1165  assert(DefIterator != OriginalAccess->defs_end() &&
1166  "Tried to access past the end of the iterator");
1167  ++DefIterator;
1168  if (DefIterator != OriginalAccess->defs_end())
1169  fillInCurrentPair();
1170  return *this;
1171  }
1172 
1173  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
1174 
1175 private:
1176  void fillInCurrentPair() {
1177  CurrentPair.first = *DefIterator;
1178  if (WalkingPhi && Location.Ptr) {
1179  PHITransAddr Translator(
1180  const_cast<Value *>(Location.Ptr),
1181  OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
1182  if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
1183  DefIterator.getPhiArgBlock(), nullptr,
1184  false))
1185  if (Translator.getAddr() != Location.Ptr) {
1186  CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
1187  return;
1188  }
1189  }
1190  CurrentPair.second = Location;
1191  }
1192 
1193  MemoryAccessPair CurrentPair;
1194  memoryaccess_def_iterator DefIterator;
1195  MemoryLocation Location;
1196  MemoryAccess *OriginalAccess = nullptr;
1197  bool WalkingPhi = false;
1198 };
1199 
1201  return upward_defs_iterator(Pair);
1202 }
1203 
1205 
1208  return make_range(upward_defs_begin(Pair), upward_defs_end());
1209 }
1210 
1211 /// Walks the defining accesses of MemoryDefs. Stops after we hit something that
1212 /// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
1213 /// comparing against a null def_chain_iterator, this will compare equal only
1214 /// after walking said Phi/liveOnEntry.
1215 ///
1216 /// The UseOptimizedChain flag specifies whether to walk the clobbering
1217 /// access chain, or all the accesses.
1218 ///
1219 /// Normally, MemoryDef are all just def/use linked together, so a def_chain on
1220 /// a MemoryDef will walk all MemoryDefs above it in the program until it hits
1221 /// a phi node. The optimized chain walks the clobbering access of a store.
1222 /// So if you are just trying to find, given a store, what the next
1223 /// thing that would clobber the same memory is, you want the optimized chain.
1224 template <class T, bool UseOptimizedChain = false>
1226  : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
1227  std::forward_iterator_tag, MemoryAccess *> {
1228  def_chain_iterator() : MA(nullptr) {}
1229  def_chain_iterator(T MA) : MA(MA) {}
1230 
1231  T operator*() const { return MA; }
1232 
1234  // N.B. liveOnEntry has a null defining access.
1235  if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
1236  if (UseOptimizedChain && MUD->isOptimized())
1237  MA = MUD->getOptimized();
1238  else
1239  MA = MUD->getDefiningAccess();
1240  } else {
1241  MA = nullptr;
1242  }
1243 
1244  return *this;
1245  }
1246 
1247  bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
1248 
1249 private:
1250  T MA;
1251 };
1252 
1253 template <class T>
1255 def_chain(T MA, MemoryAccess *UpTo = nullptr) {
1256 #ifdef EXPENSIVE_CHECKS
1257  assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
1258  "UpTo isn't in the def chain!");
1259 #endif
1261 }
1262 
1263 template <class T>
1266  def_chain_iterator<T, true>(nullptr));
1267 }
1268 
1269 } // end namespace llvm
1270 
1271 #endif // LLVM_ANALYSIS_MEMORYSSA_H
uint64_t CallInst * C
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
Definition: MemorySSA.h:769
memoryaccess_def_iterator & operator++()
Definition: MemorySSA.h:1073
BasicBlock * getIncomingBlock(MemoryAccess::const_user_iterator I) const
Return incoming basic block corresponding to value use iterator.
Definition: MemorySSA.h:532
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
unsigned getValueID() const
Return an ID for the concrete type of this object.
Definition: Value.h:463
virtual void verify(const MemorySSA *MSSA)
Definition: MemorySSA.h:1010
void unorderedDeleteIncomingValue(const MemoryAccess *MA)
Definition: MemorySSA.h:602
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void unorderedDeleteIncomingIf(Fn &&Pred)
Definition: MemorySSA.h:583
Result(std::unique_ptr< MemorySSA > &&MSSA)
Definition: MemorySSA.h:893
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:176
BasicBlock * getIncomingBlock(const Use &U) const
Return incoming basic block corresponding to an operand of the PHI.
Definition: MemorySSA.h:525
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:255
MemorySSAPrinterPass(raw_ostream &OS)
Definition: MemorySSA.h:908
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void resetOptimized()
Definition: MemorySSA.h:350
const MemorySSA & getMSSA() const
Definition: MemorySSA.h:928
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess&#39;s for a given basic block.
Definition: MemorySSA.h:725
BasicBlock *const * const_block_iterator
Definition: MemorySSA.h:476
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
MemoryAccess * getOptimized() const
Definition: MemorySSA.h:398
Extension point for the Value hierarchy.
Definition: DerivedUser.h:28
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:376
BaseT::iterator::reference operator*() const
Definition: MemorySSA.h:1157
void setOptimized(MemoryAccess *)
Definition: MemorySSA.h:662
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:99
BasicBlock * getPhiArgBlock() const
Definition: MemorySSA.h:1057
memoryaccess_def_iterator defs_begin()
This iterator walks over all of the defs in a given MemoryAccess.
Definition: MemorySSA.h:1091
unsigned second
F(f)
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:553
void(*)(DerivedUser *) DeleteValueTy
Definition: DerivedUser.h:30
This defines the Use class.
AllAccessType::const_self_iterator getIterator() const
Definition: MemorySSA.h:179
DefsOnlyType::self_iterator getDefsIterator()
Definition: MemorySSA.h:188
void setIncomingValue(unsigned I, MemoryAccess *V)
Definition: MemorySSA.h:512
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
Represents read-only accesses to memory.
Definition: MemorySSA.h:321
This class is a batch walker of all MemoryUse&#39;s in the program, and points their defining access at t...
Definition: MemorySSA.cpp:1102
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:919
Definition: BitVector.h:921
void resetOptimized()
Reset the ID of what this MemoryUse was optimized to, causing it to be rewalked by the walker if nece...
Definition: MemorySSA.h:669
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock *> &Visited)
Definition: MemorySSA.h:788
block_iterator block_begin()
Definition: MemorySSA.h:478
A MemorySSAWalker that does AA walks to disambiguate accesses.
Definition: MemorySSA.cpp:909
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:681
The access may reference the value stored in memory.
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef&#39;s and MemoryPhi&#39;s for a given basic block.
Definition: MemorySSA.h:733
const_block_iterator block_end() const
Definition: MemorySSA.h:491
bool isOptimized() const
Definition: MemorySSA.h:402
Walks the defining accesses of MemoryDefs.
Definition: MemorySSA.h:1225
def_chain_iterator & operator++()
Definition: MemorySSA.h:1233
bool isOptimized() const
Definition: MemorySSA.h:650
MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty, DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB)
Definition: MemorySSA.h:282
BaseT::iterator::pointer operator*() const
Definition: MemorySSA.h:1063
static bool classof(const Value *MA)
Definition: MemorySSA.h:389
iterator_range< block_iterator > blocks()
Definition: MemorySSA.h:495
A simple intrusive list implementation.
Definition: simple_ilist.h:79
Key
PAL metadata keys.
#define DEFINE_TRANSPARENT_OPERAND_ACCESSORS(CLASS, VALUECLASS)
Macro for generating out-of-class operand accessor definitions.
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
static ChildIteratorType child_end(NodeRef N)
Definition: MemorySSA.h:1124
static int getID(struct InternalInstruction *insn, const void *miiArg)
MemoryAccess * getOptimized() const
Definition: MemorySSA.h:346
AllAccessType::const_reverse_self_iterator getReverseIterator() const
Definition: MemorySSA.h:185
upward_defs_iterator upward_defs_end()
Definition: MemorySSA.h:1204
std::unique_ptr< MemorySSA > MSSA
Definition: MemorySSA.h:897
A nullable Value handle that is nullable.
Definition: ValueHandle.h:141
void unorderedDeleteIncoming(unsigned I)
Definition: MemorySSA.h:567
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:365
This is the generic walker interface for walkers of MemorySSA.
Definition: MemorySSA.h:950
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
op_range incoming_values()
Definition: MemorySSA.h:503
memoryaccess_def_iterator defs_end()
Definition: MemorySSA.h:1099
unsigned getID() const
Definition: MemorySSA.h:613
MemoryAccess * getIncomingValue(unsigned I) const
Return incoming value number x.
Definition: MemorySSA.h:511
const_block_iterator block_begin() const
Definition: MemorySSA.h:483
An assembly annotator class to print Memory SSA information in comments.
Definition: MemorySSA.cpp:88
Use delete by default for iplist and ilist.
Definition: ilist.h:41
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const
Definition: MemorySSA.h:197
AllAccessType::reverse_self_iterator getReverseIterator()
Definition: MemorySSA.h:182
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
PointerIntPair - This class implements a pair of a pointer and small integer.
PHITransAddr - An address value which tracks and handles phi translation.
Definition: PHITransAddr.h:36
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
const_op_range incoming_values() const
Definition: MemorySSA.h:505
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
upward_defs_iterator & operator++()
Definition: MemorySSA.h:1164
void addIncoming(MemoryAccess *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: MemorySSA.h:542
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1329
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:382
static unsigned getIncomingValueNumForOperand(unsigned I)
Definition: MemorySSA.h:518
void setIncomingBlock(unsigned I, BasicBlock *BB)
Definition: MemorySSA.h:536
upward_defs_iterator(const MemoryAccessPair &Info)
Definition: MemorySSA.h:1142
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:755
Represent the analysis usage information of a pass.
iterator_range< def_chain_iterator< T, true > > optimized_def_chain(T MA)
Definition: MemorySSA.h:1264
void print(raw_ostream &OS) const
Definition: MemorySSA.cpp:1903
Printer pass for MemorySSA.
Definition: MemorySSA.h:904
static unsigned getOperandNumForIncomingValue(unsigned I)
Definition: MemorySSA.h:517
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static bool classof(const Value *MA)
Definition: MemorySSA.h:331
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
BasicBlock * getPhiArgBlock() const
Definition: MemorySSA.h:1173
virtual void invalidateInfo(MemoryAccess *)
Given a memory access, invalidate anything this walker knows about that access.
Definition: MemorySSA.h:1008
Iterator base class used to implement const and non-const iterators over the defining accesses of a M...
Definition: MemorySSA.h:128
#define DECLARE_TRANSPARENT_OPERAND_ACCESSORS(VALUECLASS)
Macro for generating in-class operand accessor declarations.
Provide an iterator that walks defs, giving both the memory access, and the current pointer location...
Definition: MemorySSA.h:1135
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:942
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:390
MemoryAccess * getOptimized() const
Definition: MemorySSA.h:656
A MemorySSAWalker that does no alias queries, or anything else.
Definition: MemorySSA.h:1020
std::pair< const MemoryAccess *, MemoryLocation > ConstMemoryAccessPair
Definition: MemorySSA.h:1032
static void deleteNode(MemoryAccess *MA)
Definition: MemorySSA.h:230
unsigned first
bool operator==(const memoryaccess_def_iterator_base &Other) const
Definition: MemorySSA.h:1047
bool isOptimized() const
Definition: MemorySSA.h:342
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:87
Representation for a specific memory location.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false, Optional< AliasResult > AR=MayAlias)
Definition: MemorySSA.h:296
Iterator for intrusive lists based on ilist_node.
static bool classof(const Value *V)
Definition: MemorySSA.h:607
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:841
Module.h This file contains the declarations for the Module class.
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:883
BasicBlock * getBlock() const
Definition: MemorySSA.h:157
void unorderedDeleteIncomingBlock(const BasicBlock *BB)
Definition: MemorySSA.h:595
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:709
Verifier pass for MemorySSA.
Definition: MemorySSA.h:914
A range adaptor for a pair of iterators.
MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds=0)
Definition: MemorySSA.h:467
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:245
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: MemorySSA.h:508
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition: MemorySSA.h:521
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
Definition: MemorySSA.h:252
iterator_range< const_block_iterator > blocks() const
Definition: MemorySSA.h:499
user_iterator_impl< const User > const_user_iterator
Definition: Value.h:369
DefsOnlyType::const_self_iterator getDefsIterator() const
Definition: MemorySSA.h:191
void setOptimizedAccessType(Optional< AliasResult > AR)
Definition: MemorySSA.h:292
iterator_range< def_chain_iterator< T > > def_chain(T MA, MemoryAccess *UpTo=nullptr)
Definition: MemorySSA.h:1255
memoryaccess_def_iterator_base< MemoryAccess > memoryaccess_def_iterator
Definition: MemorySSA.h:129
block_iterator block_end()
Definition: MemorySSA.h:489
bool operator==(const def_chain_iterator &O) const
Definition: MemorySSA.h:1247
This file provides utility analysis objects describing memory locations.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
user_iterator_impl< User > user_iterator
Definition: Value.h:368
MemoryAccess * getIncomingValueForBlock(const BasicBlock *BB) const
Definition: MemorySSA.h:560
Compile-time customization of User operands.
Definition: User.h:43
MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue, BasicBlock *BB, unsigned NumOperands)
Definition: MemorySSA.h:216
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:705
Optional< AliasResult > getOptimizedAccessType() const
Definition: MemorySSA.h:269
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2032
static ChildIteratorType child_begin(NodeRef N)
Definition: MemorySSA.h:1123
MemoryAccess * getClobberingMemoryAccess(const Instruction *I)
Given a memory Mod/Ref/ModRef&#39;ing instruction, calling this will give you the nearest dominating Memo...
Definition: MemorySSA.h:979
static ChildIteratorType child_begin(NodeRef N)
Definition: MemorySSA.h:1114
static bool classof(const Value *MA)
Definition: MemorySSA.h:257
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
void setOptimized(MemoryAccess *MA)
Definition: MemorySSA.h:393
static NodeRef getEntryNode(NodeRef N)
Definition: MemorySSA.h:1113
LLVM Value Representation.
Definition: Value.h:73
MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, unsigned Ver)
Definition: MemorySSA.h:382
DefsOnlyType::reverse_self_iterator getReverseDefsIterator()
Definition: MemorySSA.h:194
upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair)
Definition: MemorySSA.h:1200
HungoffOperandTraits - determine the allocation regime of the Use array when it is not a prefix to th...
Definition: OperandTraits.h:96
void allocHungoffUses(unsigned N, bool IsPhi=false)
Allocate the array of Uses, followed by a pointer (with bottom bit set) to the User.
Definition: User.cpp:40
unsigned getID() const
Used for debugging and tracking things about MemoryAccesses.
Definition: MemorySSA.h:642
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
const_user_iterator const_iterator
Definition: MemorySSA.h:164
IRTranslator LLVM IR MI
FixedNumOperandTraits - determine the allocation regime of the Use array when it is a prefix to the U...
Definition: OperandTraits.h:31
A container for analyses that lazily runs them and caches their results.
void setBlock(BasicBlock *BB)
Used by MemorySSA to change the block of a MemoryAccess when it is moved.
Definition: MemorySSA.h:210
MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
Definition: MemorySSA.h:325
static bool classof(const Value *V)
Definition: MemorySSA.h:152
iterator_range< upward_defs_iterator > upward_defs(const MemoryAccessPair &Pair)
Definition: MemorySSA.h:1207
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:459
unsigned getID() const
Definition: MemorySSA.h:413
static ChildIteratorType child_end(NodeRef N)
Definition: MemorySSA.h:1115
DefsList * getWritableBlockDefs(const BasicBlock *BB) const
Definition: MemorySSA.h:775
user_iterator iterator
The user iterators for a memory access.
Definition: MemorySSA.h:163
memoryaccess_def_iterator_base< const MemoryAccess > const_memoryaccess_def_iterator
Definition: MemorySSA.h:131
bool operator==(const upward_defs_iterator &Other) const
Definition: MemorySSA.h:1153
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
void resetOptimized()
Definition: MemorySSA.h:407
void setOptimized(MemoryAccess *DMA)
Definition: MemorySSA.h:337
std::pair< MemoryAccess *, MemoryLocation > MemoryAccessPair
Definition: MemorySSA.h:1031
void allocHungoffUses(unsigned N)
this is more complicated than the generic User::allocHungoffUses, because we have to allocate Uses fo...
Definition: MemorySSA.h:621
user_iterator user_end()
Definition: Value.h:383