contrib/llvm/include/llvm/Analysis/MemorySSA.h

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