EIC code displayed by LXR master/​include/​llvm/​Analysis/​MemorySSA.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:43:15

 //===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// This file exposes an interface to building/using memory SSA to
 /// walk memory instructions using a use/def graph.
 ///
 /// Memory SSA class builds an SSA form that links together memory access
 /// instructions such as loads, stores, atomics, and calls. Additionally, it
 /// does a trivial form of "heap versioning" Every time the memory state changes
 /// in the program, we generate a new heap version. It generates
 /// MemoryDef/Uses/Phis that are overlayed on top of the existing instructions.
 ///
 /// As a trivial example,
 /// define i32 @main() #0 {
 /// entry:
 ///   %call = call noalias i8* @_Znwm(i64 4) #2
 ///   %0 = bitcast i8* %call to i32*
 ///   %call1 = call noalias i8* @_Znwm(i64 4) #2
 ///   %1 = bitcast i8* %call1 to i32*
 ///   store i32 5, i32* %0, align 4
 ///   store i32 7, i32* %1, align 4
 ///   %2 = load i32* %0, align 4
 ///   %3 = load i32* %1, align 4
 ///   %add = add nsw i32 %2, %3
 ///   ret i32 %add
 /// }
 ///
 /// Will become
 /// define i32 @main() #0 {
 /// entry:
 ///   ; 1 = MemoryDef(0)
 ///   %call = call noalias i8* @_Znwm(i64 4) #3
 ///   %2 = bitcast i8* %call to i32*
 ///   ; 2 = MemoryDef(1)
 ///   %call1 = call noalias i8* @_Znwm(i64 4) #3
 ///   %4 = bitcast i8* %call1 to i32*
 ///   ; 3 = MemoryDef(2)
 ///   store i32 5, i32* %2, align 4
 ///   ; 4 = MemoryDef(3)
 ///   store i32 7, i32* %4, align 4
 ///   ; MemoryUse(3)
 ///   %7 = load i32* %2, align 4
 ///   ; MemoryUse(4)
 ///   %8 = load i32* %4, align 4
 ///   %add = add nsw i32 %7, %8
 ///   ret i32 %add
 /// }
 ///
 /// Given this form, all the stores that could ever effect the load at %8 can be
 /// gotten by using the MemoryUse associated with it, and walking from use to
 /// def until you hit the top of the function.
 ///
 /// Each def also has a list of users associated with it, so you can walk from
 /// both def to users, and users to defs. Note that we disambiguate MemoryUses,
 /// but not the RHS of MemoryDefs. You can see this above at %7, which would
 /// otherwise be a MemoryUse(4). Being disambiguated means that for a given
 /// store, all the MemoryUses on its use lists are may-aliases of that store
 /// (but the MemoryDefs on its use list may not be).
 ///
 /// MemoryDefs are not disambiguated because it would require multiple reaching
 /// definitions, which would require multiple phis, and multiple memoryaccesses
 /// per instruction.
 ///
 /// In addition to the def/use graph described above, MemoryDefs also contain
 /// an "optimized" definition use.  The "optimized" use points to some def
 /// reachable through the memory def chain.  The optimized def *may* (but is
 /// not required to) alias the original MemoryDef, but no def *closer* to the
 /// source def may alias it.  As the name implies, the purpose of the optimized
 /// use is to allow caching of clobber searches for memory defs.  The optimized
 /// def may be nullptr, in which case clients must walk the defining access
 /// chain.
 ///
 /// When iterating the uses of a MemoryDef, both defining uses and optimized
 /// uses will be encountered.  If only one type is needed, the client must
 /// filter the use walk.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MEMORYSSA_H
 #define LLVM_ANALYSIS_MEMORYSSA_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/IR/DerivedUser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/Pass.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <utility>
 
 namespace llvm {
 
 template <class GraphType> struct GraphTraits;
 class Function;
 class Loop;
 class LLVMContext;
 class MemoryAccess;
 class MemorySSAWalker;
 class Module;
 class raw_ostream;
 
 namespace MSSAHelpers {
 
 struct AllAccessTag {};
 struct DefsOnlyTag {};
 
 } // end namespace MSSAHelpers
 
 enum : unsigned {
   // Used to signify what the default invalid ID is for MemoryAccess's
   // getID()
   INVALID_MEMORYACCESS_ID = -1U
 };
 
 template <class T> class memoryaccess_def_iterator_base;
 using memoryaccess_def_iterator = memoryaccess_def_iterator_base<MemoryAccess>;
 using const_memoryaccess_def_iterator =
     memoryaccess_def_iterator_base<const MemoryAccess>;
 
 // The base for all memory accesses. All memory accesses in a block are
 // linked together using an intrusive list.
 class MemoryAccess
     : public DerivedUser,
       public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>,
       public ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>> {
 public:
   using AllAccessType =
       ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
   using DefsOnlyType =
       ilist_node<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
 
   MemoryAccess(const MemoryAccess &) = delete;
   MemoryAccess &operator=(const MemoryAccess &) = delete;
 
   void *operator new(size_t) = delete;
 
   // Methods for support type inquiry through isa, cast, and
   // dyn_cast
   static bool classof(const Value *V) {
     unsigned ID = V->getValueID();
     return ID == MemoryUseVal || ID == MemoryPhiVal || ID == MemoryDefVal;
   }
 
   BasicBlock *getBlock() const { return Block; }
 
   void print(raw_ostream &OS) const;
   void dump() const;
 
   /// The user iterators for a memory access
   using iterator = user_iterator;
   using const_iterator = const_user_iterator;
 
   /// This iterator walks over all of the defs in a given
   /// MemoryAccess. For MemoryPhi nodes, this walks arguments. For
   /// MemoryUse/MemoryDef, this walks the defining access.
   memoryaccess_def_iterator defs_begin();
   const_memoryaccess_def_iterator defs_begin() const;
   memoryaccess_def_iterator defs_end();
   const_memoryaccess_def_iterator defs_end() const;
 
   /// Get the iterators for the all access list and the defs only list
   /// We default to the all access list.
   AllAccessType::self_iterator getIterator() {
     return this->AllAccessType::getIterator();
   }
   AllAccessType::const_self_iterator getIterator() const {
     return this->AllAccessType::getIterator();
   }
   AllAccessType::reverse_self_iterator getReverseIterator() {
     return this->AllAccessType::getReverseIterator();
   }
   AllAccessType::const_reverse_self_iterator getReverseIterator() const {
     return this->AllAccessType::getReverseIterator();
   }
   DefsOnlyType::self_iterator getDefsIterator() {
     return this->DefsOnlyType::getIterator();
   }
   DefsOnlyType::const_self_iterator getDefsIterator() const {
     return this->DefsOnlyType::getIterator();
   }
   DefsOnlyType::reverse_self_iterator getReverseDefsIterator() {
     return this->DefsOnlyType::getReverseIterator();
   }
   DefsOnlyType::const_reverse_self_iterator getReverseDefsIterator() const {
     return this->DefsOnlyType::getReverseIterator();
   }
 
 protected:
   friend class MemoryDef;
   friend class MemoryPhi;
   friend class MemorySSA;
   friend class MemoryUse;
   friend class MemoryUseOrDef;
 
   /// Used by MemorySSA to change the block of a MemoryAccess when it is
   /// moved.
   void setBlock(BasicBlock *BB) { Block = BB; }
 
   /// Used for debugging and tracking things about MemoryAccesses.
   /// Guaranteed unique among MemoryAccesses, no guarantees otherwise.
   inline unsigned getID() const;
 
   MemoryAccess(LLVMContext &C, unsigned Vty, DeleteValueTy DeleteValue,
                BasicBlock *BB, AllocInfo AllocInfo)
       : DerivedUser(Type::getVoidTy(C), Vty, AllocInfo, DeleteValue),
         Block(BB) {}
 
   // Use deleteValue() to delete a generic MemoryAccess.
   ~MemoryAccess() = default;
 
 private:
   BasicBlock *Block;
 };
 
 template <>
 struct ilist_alloc_traits<MemoryAccess> {
   static void deleteNode(MemoryAccess *MA) { MA->deleteValue(); }
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
   MA.print(OS);
   return OS;
 }
 
 /// Class that has the common methods + fields of memory uses/defs. It's
 /// a little awkward to have, but there are many cases where we want either a
 /// use or def, and there are many cases where uses are needed (defs aren't
 /// acceptable), and vice-versa.
 ///
 /// This class should never be instantiated directly; make a MemoryUse or
 /// MemoryDef instead.
 class MemoryUseOrDef : public MemoryAccess {
 public:
   void *operator new(size_t) = delete;
 
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   /// Get the instruction that this MemoryUse represents.
   Instruction *getMemoryInst() const { return MemoryInstruction; }
 
   /// Get the access that produces the memory state used by this Use.
   MemoryAccess *getDefiningAccess() const { return getOperand(0); }
 
   static bool classof(const Value *MA) {
     return MA->getValueID() == MemoryUseVal || MA->getValueID() == MemoryDefVal;
   }
 
   /// Do we have an optimized use?
   inline bool isOptimized() const;
   /// Return the MemoryAccess associated with the optimized use, or nullptr.
   inline MemoryAccess *getOptimized() const;
   /// Sets the optimized use for a MemoryDef.
   inline void setOptimized(MemoryAccess *);
 
   /// Reset the ID of what this MemoryUse was optimized to, causing it to
   /// be rewalked by the walker if necessary.
   /// This really should only be called by tests.
   inline void resetOptimized();
 
 protected:
   friend class MemorySSA;
   friend class MemorySSAUpdater;
 
   MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
                  DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
                  AllocInfo AllocInfo)
       : MemoryAccess(C, Vty, DeleteValue, BB, AllocInfo),
         MemoryInstruction(MI) {
     setDefiningAccess(DMA);
   }
 
   // Use deleteValue() to delete a generic MemoryUseOrDef.
   ~MemoryUseOrDef() = default;
 
   void setDefiningAccess(MemoryAccess *DMA, bool Optimized = false) {
     if (!Optimized) {
       setOperand(0, DMA);
       return;
     }
     setOptimized(DMA);
   }
 
 private:
   Instruction *MemoryInstruction;
 };
 
 /// Represents read-only accesses to memory
 ///
 /// In particular, the set of Instructions that will be represented by
 /// MemoryUse's is exactly the set of Instructions for which
 /// AliasAnalysis::getModRefInfo returns "Ref".
 class MemoryUse final : public MemoryUseOrDef {
   constexpr static IntrusiveOperandsAllocMarker AllocMarker{1};
 
 public:
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
       : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB, AllocMarker) {}
 
   // allocate space for exactly one operand
   void *operator new(size_t S) { return User::operator new(S, AllocMarker); }
   void operator delete(void *Ptr) { User::operator delete(Ptr); }
 
   static bool classof(const Value *MA) {
     return MA->getValueID() == MemoryUseVal;
   }
 
   void print(raw_ostream &OS) const;
 
   void setOptimized(MemoryAccess *DMA) {
     OptimizedID = DMA->getID();
     setOperand(0, DMA);
   }
 
   /// Whether the MemoryUse is optimized. If ensureOptimizedUses() was called,
   /// uses will usually be optimized, but this is not guaranteed (e.g. due to
   /// invalidation and optimization limits.)
   bool isOptimized() const {
     return getDefiningAccess() && OptimizedID == getDefiningAccess()->getID();
   }
 
   MemoryAccess *getOptimized() const {
     return getDefiningAccess();
   }
 
   void resetOptimized() {
     OptimizedID = INVALID_MEMORYACCESS_ID;
   }
 
 protected:
   friend class MemorySSA;
 
 private:
   static void deleteMe(DerivedUser *Self);
 
   unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
 };
 
 template <>
 struct OperandTraits<MemoryUse> : public FixedNumOperandTraits<MemoryUse, 1> {};
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUse, MemoryAccess)
 
 /// Represents a read-write access to memory, whether it is a must-alias,
 /// or a may-alias.
 ///
 /// In particular, the set of Instructions that will be represented by
 /// MemoryDef's is exactly the set of Instructions for which
 /// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
 /// Note that, in order to provide def-def chains, all defs also have a use
 /// associated with them. This use points to the nearest reaching
 /// MemoryDef/MemoryPhi.
 class MemoryDef final : public MemoryUseOrDef {
   constexpr static IntrusiveOperandsAllocMarker AllocMarker{2};
 
 public:
   friend class MemorySSA;
 
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
             unsigned Ver)
       : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB, AllocMarker),
         ID(Ver) {}
 
   // allocate space for exactly two operands
   void *operator new(size_t S) { return User::operator new(S, AllocMarker); }
   void operator delete(void *Ptr) { User::operator delete(Ptr); }
 
   static bool classof(const Value *MA) {
     return MA->getValueID() == MemoryDefVal;
   }
 
   void setOptimized(MemoryAccess *MA) {
     setOperand(1, MA);
     OptimizedID = MA->getID();
   }
 
   MemoryAccess *getOptimized() const {
     return cast_or_null<MemoryAccess>(getOperand(1));
   }
 
   bool isOptimized() const {
     return getOptimized() && OptimizedID == getOptimized()->getID();
   }
 
   void resetOptimized() {
     OptimizedID = INVALID_MEMORYACCESS_ID;
     setOperand(1, nullptr);
   }
 
   void print(raw_ostream &OS) const;
 
   unsigned getID() const { return ID; }
 
 private:
   static void deleteMe(DerivedUser *Self);
 
   const unsigned ID;
   unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
 };
 
 template <>
 struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)
 
 template <>
 struct OperandTraits<MemoryUseOrDef> {
   static Use *op_begin(MemoryUseOrDef *MUD) {
     if (auto *MU = dyn_cast<MemoryUse>(MUD))
       return OperandTraits<MemoryUse>::op_begin(MU);
     return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
   }
 
   static Use *op_end(MemoryUseOrDef *MUD) {
     if (auto *MU = dyn_cast<MemoryUse>(MUD))
       return OperandTraits<MemoryUse>::op_end(MU);
     return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
   }
 
   static unsigned operands(const MemoryUseOrDef *MUD) {
     if (const auto *MU = dyn_cast<MemoryUse>(MUD))
       return OperandTraits<MemoryUse>::operands(MU);
     return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
   }
 };
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
 
 /// Represents phi nodes for memory accesses.
 ///
 /// These have the same semantic as regular phi nodes, with the exception that
 /// only one phi will ever exist in a given basic block.
 /// Guaranteeing one phi per block means guaranteeing there is only ever one
 /// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
 /// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
 /// a MemoryPhi's operands.
 /// That is, given
 /// if (a) {
 ///   store %a
 ///   store %b
 /// }
 /// it *must* be transformed into
 /// if (a) {
 ///    1 = MemoryDef(liveOnEntry)
 ///    store %a
 ///    2 = MemoryDef(1)
 ///    store %b
 /// }
 /// and *not*
 /// if (a) {
 ///    1 = MemoryDef(liveOnEntry)
 ///    store %a
 ///    2 = MemoryDef(liveOnEntry)
 ///    store %b
 /// }
 /// even if the two stores do not conflict. Otherwise, both 1 and 2 reach the
 /// end of the branch, and if there are not two phi nodes, one will be
 /// disconnected completely from the SSA graph below that point.
 /// Because MemoryUse's do not generate new definitions, they do not have this
 /// issue.
 class MemoryPhi final : public MemoryAccess {
   constexpr static HungOffOperandsAllocMarker AllocMarker{};
 
   // allocate space for exactly zero operands
   void *operator new(size_t S) { return User::operator new(S, AllocMarker); }
 
 public:
   void operator delete(void *Ptr) { User::operator delete(Ptr); }
 
   /// Provide fast operand accessors
   DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
 
   MemoryPhi(LLVMContext &C, BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
       : MemoryAccess(C, MemoryPhiVal, deleteMe, BB, AllocMarker), ID(Ver),
         ReservedSpace(NumPreds) {
     allocHungoffUses(ReservedSpace);
   }
 
   // Block iterator interface. This provides access to the list of incoming
   // basic blocks, which parallels the list of incoming values.
   using block_iterator = BasicBlock **;
   using const_block_iterator = BasicBlock *const *;
 
   block_iterator block_begin() {
     return reinterpret_cast<block_iterator>(op_begin() + ReservedSpace);
   }
 
   const_block_iterator block_begin() const {
     return reinterpret_cast<const_block_iterator>(op_begin() + ReservedSpace);
   }
 
   block_iterator block_end() { return block_begin() + getNumOperands(); }
 
   const_block_iterator block_end() const {
     return block_begin() + getNumOperands();
   }
 
   iterator_range<block_iterator> blocks() {
     return make_range(block_begin(), block_end());
   }
 
   iterator_range<const_block_iterator> blocks() const {
     return make_range(block_begin(), block_end());
   }
 
   op_range incoming_values() { return operands(); }
 
   const_op_range incoming_values() const { return operands(); }
 
   /// Return the number of incoming edges
   unsigned getNumIncomingValues() const { return getNumOperands(); }
 
   /// Return incoming value number x
   MemoryAccess *getIncomingValue(unsigned I) const { return getOperand(I); }
   void setIncomingValue(unsigned I, MemoryAccess *V) {
     assert(V && "PHI node got a null value!");
     setOperand(I, V);
   }
 
   static unsigned getOperandNumForIncomingValue(unsigned I) { return I; }
   static unsigned getIncomingValueNumForOperand(unsigned I) { return I; }
 
   /// Return incoming basic block number @p i.
   BasicBlock *getIncomingBlock(unsigned I) const { return block_begin()[I]; }
 
   /// Return incoming basic block corresponding
   /// to an operand of the PHI.
   BasicBlock *getIncomingBlock(const Use &U) const {
     assert(this == U.getUser() && "Iterator doesn't point to PHI's Uses?");
     return getIncomingBlock(unsigned(&U - op_begin()));
   }
 
   /// Return incoming basic block corresponding
   /// to value use iterator.
   BasicBlock *getIncomingBlock(MemoryAccess::const_user_iterator I) const {
     return getIncomingBlock(I.getUse());
   }
 
   void setIncomingBlock(unsigned I, BasicBlock *BB) {
     assert(BB && "PHI node got a null basic block!");
     block_begin()[I] = BB;
   }
 
   /// Add an incoming value to the end of the PHI list
   void addIncoming(MemoryAccess *V, BasicBlock *BB) {
     if (getNumOperands() == ReservedSpace)
       growOperands(); // Get more space!
     // Initialize some new operands.
     setNumHungOffUseOperands(getNumOperands() + 1);
     setIncomingValue(getNumOperands() - 1, V);
     setIncomingBlock(getNumOperands() - 1, BB);
   }
 
   /// Return the first index of the specified basic
   /// block in the value list for this PHI.  Returns -1 if no instance.
   int getBasicBlockIndex(const BasicBlock *BB) const {
     for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
       if (block_begin()[I] == BB)
         return I;
     return -1;
   }
 
   MemoryAccess *getIncomingValueForBlock(const BasicBlock *BB) const {
     int Idx = getBasicBlockIndex(BB);
     assert(Idx >= 0 && "Invalid basic block argument!");
     return getIncomingValue(Idx);
   }
 
   // After deleting incoming position I, the order of incoming may be changed.
   void unorderedDeleteIncoming(unsigned I) {
     unsigned E = getNumOperands();
     assert(I < E && "Cannot remove out of bounds Phi entry.");
     // MemoryPhi must have at least two incoming values, otherwise the MemoryPhi
     // itself should be deleted.
     assert(E >= 2 && "Cannot only remove incoming values in MemoryPhis with "
                      "at least 2 values.");
     setIncomingValue(I, getIncomingValue(E - 1));
     setIncomingBlock(I, block_begin()[E - 1]);
     setOperand(E - 1, nullptr);
     block_begin()[E - 1] = nullptr;
     setNumHungOffUseOperands(getNumOperands() - 1);
   }
 
   // After deleting entries that satisfy Pred, remaining entries may have
   // changed order.
   template <typename Fn> void unorderedDeleteIncomingIf(Fn &&Pred) {
     for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
       if (Pred(getIncomingValue(I), getIncomingBlock(I))) {
         unorderedDeleteIncoming(I);
         E = getNumOperands();
         --I;
       }
     assert(getNumOperands() >= 1 &&
            "Cannot remove all incoming blocks in a MemoryPhi.");
   }
 
   // After deleting incoming block BB, the incoming blocks order may be changed.
   void unorderedDeleteIncomingBlock(const BasicBlock *BB) {
     unorderedDeleteIncomingIf(
         [&](const MemoryAccess *, const BasicBlock *B) { return BB == B; });
   }
 
   // After deleting incoming memory access MA, the incoming accesses order may
   // be changed.
   void unorderedDeleteIncomingValue(const MemoryAccess *MA) {
     unorderedDeleteIncomingIf(
         [&](const MemoryAccess *M, const BasicBlock *) { return MA == M; });
   }
 
   static bool classof(const Value *V) {
     return V->getValueID() == MemoryPhiVal;
   }
 
   void print(raw_ostream &OS) const;
 
   unsigned getID() const { return ID; }
 
 protected:
   friend class MemorySSA;
 
   /// this is more complicated than the generic
   /// User::allocHungoffUses, because we have to allocate Uses for the incoming
   /// values and pointers to the incoming blocks, all in one allocation.
   void allocHungoffUses(unsigned N) {
     User::allocHungoffUses(N, /* IsPhi */ true);
   }
 
 private:
   // For debugging only
   const unsigned ID;
   unsigned ReservedSpace;
 
   /// This grows the operand list in response to a push_back style of
   /// operation.  This grows the number of ops by 1.5 times.
   void growOperands() {
     unsigned E = getNumOperands();
     // 2 op PHI nodes are VERY common, so reserve at least enough for that.
     ReservedSpace = std::max(E + E / 2, 2u);
     growHungoffUses(ReservedSpace, /* IsPhi */ true);
   }
 
   static void deleteMe(DerivedUser *Self);
 };
 
 inline unsigned MemoryAccess::getID() const {
   assert((isa<MemoryDef>(this) || isa<MemoryPhi>(this)) &&
          "only memory defs and phis have ids");
   if (const auto *MD = dyn_cast<MemoryDef>(this))
     return MD->getID();
   return cast<MemoryPhi>(this)->getID();
 }
 
 inline bool MemoryUseOrDef::isOptimized() const {
   if (const auto *MD = dyn_cast<MemoryDef>(this))
     return MD->isOptimized();
   return cast<MemoryUse>(this)->isOptimized();
 }
 
 inline MemoryAccess *MemoryUseOrDef::getOptimized() const {
   if (const auto *MD = dyn_cast<MemoryDef>(this))
     return MD->getOptimized();
   return cast<MemoryUse>(this)->getOptimized();
 }
 
 inline void MemoryUseOrDef::setOptimized(MemoryAccess *MA) {
   if (auto *MD = dyn_cast<MemoryDef>(this))
     MD->setOptimized(MA);
   else
     cast<MemoryUse>(this)->setOptimized(MA);
 }
 
 inline void MemoryUseOrDef::resetOptimized() {
   if (auto *MD = dyn_cast<MemoryDef>(this))
     MD->resetOptimized();
   else
     cast<MemoryUse>(this)->resetOptimized();
 }
 
 template <> struct OperandTraits<MemoryPhi> : public HungoffOperandTraits {};
 DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryPhi, MemoryAccess)
 
 /// Encapsulates MemorySSA, including all data associated with memory
 /// accesses.
 class MemorySSA {
 public:
   MemorySSA(Function &, AliasAnalysis *, DominatorTree *);
   MemorySSA(Loop &, AliasAnalysis *, DominatorTree *);
 
   // MemorySSA must remain where it's constructed; Walkers it creates store
   // pointers to it.
   MemorySSA(MemorySSA &&) = delete;
 
   ~MemorySSA();
 
   MemorySSAWalker *getWalker();
   MemorySSAWalker *getSkipSelfWalker();
 
   /// Given a memory Mod/Ref'ing instruction, get the MemorySSA
   /// access associated with it. If passed a basic block gets the memory phi
   /// node that exists for that block, if there is one. Otherwise, this will get
   /// a MemoryUseOrDef.
   MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
     return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
   }
 
   MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
     return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
   }
 
   DominatorTree &getDomTree() const { return *DT; }
 
   void dump() const;
   void print(raw_ostream &) const;
 
   /// Return true if \p MA represents the live on entry value
   ///
   /// Loads and stores from pointer arguments and other global values may be
   /// defined by memory operations that do not occur in the current function, so
   /// they may be live on entry to the function. MemorySSA represents such
   /// memory state by the live on entry definition, which is guaranteed to occur
   /// before any other memory access in the function.
   inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
     return MA == LiveOnEntryDef.get();
   }
 
   inline MemoryAccess *getLiveOnEntryDef() const {
     return LiveOnEntryDef.get();
   }
 
   // Sadly, iplists, by default, owns and deletes pointers added to the
   // list. It's not currently possible to have two iplists for the same type,
   // where one owns the pointers, and one does not. This is because the traits
   // are per-type, not per-tag.  If this ever changes, we should make the
   // DefList an iplist.
   using AccessList = iplist<MemoryAccess, ilist_tag<MSSAHelpers::AllAccessTag>>;
   using DefsList =
       simple_ilist<MemoryAccess, ilist_tag<MSSAHelpers::DefsOnlyTag>>;
 
   /// Return the list of MemoryAccess's for a given basic block.
   ///
   /// This list is not modifiable by the user.
   const AccessList *getBlockAccesses(const BasicBlock *BB) const {
     return getWritableBlockAccesses(BB);
   }
 
   /// Return the list of MemoryDef's and MemoryPhi's for a given basic
   /// block.
   ///
   /// This list is not modifiable by the user.
   const DefsList *getBlockDefs(const BasicBlock *BB) const {
     return getWritableBlockDefs(BB);
   }
 
   /// Given two memory accesses in the same basic block, determine
   /// whether MemoryAccess \p A dominates MemoryAccess \p B.
   bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
 
   /// Given two memory accesses in potentially different blocks,
   /// determine whether MemoryAccess \p A dominates MemoryAccess \p B.
   bool dominates(const MemoryAccess *A, const MemoryAccess *B) const;
 
   /// Given a MemoryAccess and a Use, determine whether MemoryAccess \p A
   /// dominates Use \p B.
   bool dominates(const MemoryAccess *A, const Use &B) const;
 
   enum class VerificationLevel { Fast, Full };
   /// Verify that MemorySSA is self consistent (IE definitions dominate
   /// all uses, uses appear in the right places).  This is used by unit tests.
   void verifyMemorySSA(VerificationLevel = VerificationLevel::Fast) const;
 
   /// Used in various insertion functions to specify whether we are talking
   /// about the beginning or end of a block.
   enum InsertionPlace { Beginning, End, BeforeTerminator };
 
   /// By default, uses are *not* optimized during MemorySSA construction.
   /// Calling this method will attempt to optimize all MemoryUses, if this has
   /// not happened yet for this MemorySSA instance. This should be done if you
   /// plan to query the clobbering access for most uses, or if you walk the
   /// def-use chain of uses.
   void ensureOptimizedUses();
 
   AliasAnalysis &getAA() { return *AA; }
 
 protected:
   // Used by Memory SSA dumpers and wrapper pass
   friend class MemorySSAUpdater;
 
   template <typename IterT>
   void verifyOrderingDominationAndDefUses(
       IterT Blocks, VerificationLevel = VerificationLevel::Fast) const;
   template <typename IterT> void verifyDominationNumbers(IterT Blocks) const;
   template <typename IterT> void verifyPrevDefInPhis(IterT Blocks) const;
 
   // This is used by the use optimizer and updater.
   AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
     auto It = PerBlockAccesses.find(BB);
     return It == PerBlockAccesses.end() ? nullptr : It->second.get();
   }
 
   // This is used by the use optimizer and updater.
   DefsList *getWritableBlockDefs(const BasicBlock *BB) const {
     auto It = PerBlockDefs.find(BB);
     return It == PerBlockDefs.end() ? nullptr : It->second.get();
   }
 
   // These is used by the updater to perform various internal MemorySSA
   // machinsations.  They do not always leave the IR in a correct state, and
   // relies on the updater to fixup what it breaks, so it is not public.
 
   void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where);
   void moveTo(MemoryAccess *What, BasicBlock *BB, InsertionPlace Point);
 
   // Rename the dominator tree branch rooted at BB.
   void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal,
                   SmallPtrSetImpl<BasicBlock *> &Visited) {
     renamePass(DT->getNode(BB), IncomingVal, Visited, true, true);
   }
 
   void removeFromLookups(MemoryAccess *);
   void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
   void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
                                InsertionPlace);
   void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
                              AccessList::iterator);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
                                       const MemoryUseOrDef *Template = nullptr,
                                       bool CreationMustSucceed = true);
 
 private:
   class ClobberWalkerBase;
   class CachingWalker;
   class SkipSelfWalker;
   class OptimizeUses;
 
   CachingWalker *getWalkerImpl();
   template <typename IterT>
   void buildMemorySSA(BatchAAResults &BAA, IterT Blocks);
 
   void prepareForMoveTo(MemoryAccess *, BasicBlock *);
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
 
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
   using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
 
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   MemoryPhi *createMemoryPhi(BasicBlock *BB);
   template <typename AliasAnalysisType>
   MemoryUseOrDef *createNewAccess(Instruction *, AliasAnalysisType *,
                                   const MemoryUseOrDef *Template = nullptr);
   void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
   void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
   void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
                   SmallPtrSetImpl<BasicBlock *> &Visited,
                   bool SkipVisited = false, bool RenameAllUses = false);
   AccessList *getOrCreateAccessList(const BasicBlock *);
   DefsList *getOrCreateDefsList(const BasicBlock *);
   void renumberBlock(const BasicBlock *) const;
   AliasAnalysis *AA = nullptr;
   DominatorTree *DT;
   Function *F = nullptr;
   Loop *L = nullptr;
 
   // Memory SSA mappings
   DenseMap<const Value *, MemoryAccess *> ValueToMemoryAccess;
 
   // These two mappings contain the main block to access/def mappings for
   // MemorySSA. The list contained in PerBlockAccesses really owns all the
   // MemoryAccesses.
   // Both maps maintain the invariant that if a block is found in them, the
   // corresponding list is not empty, and if a block is not found in them, the
   // corresponding list is empty.
   AccessMap PerBlockAccesses;
   DefsMap PerBlockDefs;
   std::unique_ptr<MemoryAccess, ValueDeleter> LiveOnEntryDef;
 
   // Domination mappings
   // Note that the numbering is local to a block, even though the map is
   // global.
   mutable SmallPtrSet<const BasicBlock *, 16> BlockNumberingValid;
   mutable DenseMap<const MemoryAccess *, unsigned long> BlockNumbering;
 
   // Memory SSA building info
   std::unique_ptr<ClobberWalkerBase> WalkerBase;
   std::unique_ptr<CachingWalker> Walker;
   std::unique_ptr<SkipSelfWalker> SkipWalker;
   unsigned NextID = 0;
   bool IsOptimized = false;
 };
 
 /// Enables verification of MemorySSA.
 ///
 /// The checks which this flag enables is exensive and disabled by default
 /// unless `EXPENSIVE_CHECKS` is defined.  The flag `-verify-memoryssa` can be
 /// used to selectively enable the verification without re-compilation.
 extern bool VerifyMemorySSA;
 
 // Internal MemorySSA utils, for use by MemorySSA classes and walkers
 class MemorySSAUtil {
 protected:
   friend class GVNHoist;
   friend class MemorySSAWalker;
 
   // This function should not be used by new passes.
   static bool defClobbersUseOrDef(MemoryDef *MD, const MemoryUseOrDef *MU,
                                   AliasAnalysis &AA);
 };
 
 /// An analysis that produces \c MemorySSA for a function.
 ///
 class MemorySSAAnalysis : public AnalysisInfoMixin<MemorySSAAnalysis> {
   friend AnalysisInfoMixin<MemorySSAAnalysis>;
 
   static AnalysisKey Key;
 
 public:
   // Wrap MemorySSA result to ensure address stability of internal MemorySSA
   // pointers after construction.  Use a wrapper class instead of plain
   // unique_ptr<MemorySSA> to avoid build breakage on MSVC.
   struct Result {
     Result(std::unique_ptr<MemorySSA> &&MSSA) : MSSA(std::move(MSSA)) {}
 
     MemorySSA &getMSSA() { return *MSSA; }
 
     std::unique_ptr<MemorySSA> MSSA;
 
     bool invalidate(Function &F, const PreservedAnalyses &PA,
                     FunctionAnalysisManager::Invalidator &Inv);
   };
 
   Result run(Function &F, FunctionAnalysisManager &AM);
 };
 
 /// Printer pass for \c MemorySSA.
 class MemorySSAPrinterPass : public PassInfoMixin<MemorySSAPrinterPass> {
   raw_ostream &OS;
   bool EnsureOptimizedUses;
 
 public:
   explicit MemorySSAPrinterPass(raw_ostream &OS, bool EnsureOptimizedUses)
       : OS(OS), EnsureOptimizedUses(EnsureOptimizedUses) {}
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   static bool isRequired() { return true; }
 };
 
 /// Printer pass for \c MemorySSA via the walker.
 class MemorySSAWalkerPrinterPass
     : public PassInfoMixin<MemorySSAWalkerPrinterPass> {
   raw_ostream &OS;
 
 public:
   explicit MemorySSAWalkerPrinterPass(raw_ostream &OS) : OS(OS) {}
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   static bool isRequired() { return true; }
 };
 
 /// Verifier pass for \c MemorySSA.
 struct MemorySSAVerifierPass : PassInfoMixin<MemorySSAVerifierPass> {
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
   static bool isRequired() { return true; }
 };
 
 /// Legacy analysis pass which computes \c MemorySSA.
 class MemorySSAWrapperPass : public FunctionPass {
 public:
   MemorySSAWrapperPass();
 
   static char ID;
 
   bool runOnFunction(Function &) override;
   void releaseMemory() override;
   MemorySSA &getMSSA() { return *MSSA; }
   const MemorySSA &getMSSA() const { return *MSSA; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   void verifyAnalysis() const override;
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 
 private:
   std::unique_ptr<MemorySSA> MSSA;
 };
 
 /// This is the generic walker interface for walkers of MemorySSA.
 /// Walkers are used to be able to further disambiguate the def-use chains
 /// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
 /// you.
 /// In particular, while the def-use chains provide basic information, and are
 /// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
 /// MemoryUse as AliasAnalysis considers it, a user mant want better or other
 /// information. In particular, they may want to use SCEV info to further
 /// disambiguate memory accesses, or they may want the nearest dominating
 /// may-aliasing MemoryDef for a call or a store. This API enables a
 /// standardized interface to getting and using that info.
 class MemorySSAWalker {
 public:
   MemorySSAWalker(MemorySSA *);
   virtual ~MemorySSAWalker() = default;
 
   using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
 
   /// Given a memory Mod/Ref/ModRef'ing instruction, calling this
   /// will give you the nearest dominating MemoryAccess that Mod's the location
   /// the instruction accesses (by skipping any def which AA can prove does not
   /// alias the location(s) accessed by the instruction given).
   ///
   /// Note that this will return a single access, and it must dominate the
   /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
   /// this will return the MemoryPhi, not the operand. This means that
   /// given:
   /// if (a) {
   ///   1 = MemoryDef(liveOnEntry)
   ///   store %a
   /// } else {
   ///   2 = MemoryDef(liveOnEntry)
   ///   store %b
   /// }
   /// 3 = MemoryPhi(2, 1)
   /// MemoryUse(3)
   /// load %a
   ///
   /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
   /// in the if (a) branch.
   MemoryAccess *getClobberingMemoryAccess(const Instruction *I,
                                           BatchAAResults &AA) {
     MemoryAccess *MA = MSSA->getMemoryAccess(I);
     assert(MA && "Handed an instruction that MemorySSA doesn't recognize?");
     return getClobberingMemoryAccess(MA, AA);
   }
 
   /// Does the same thing as getClobberingMemoryAccess(const Instruction *I),
   /// but takes a MemoryAccess instead of an Instruction.
   virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
                                                   BatchAAResults &AA) = 0;
 
   /// Given a potentially clobbering memory access and a new location,
   /// calling this will give you the nearest dominating clobbering MemoryAccess
   /// (by skipping non-aliasing def links).
   ///
   /// This version of the function is mainly used to disambiguate phi translated
   /// pointers, where the value of a pointer may have changed from the initial
   /// memory access. Note that this expects to be handed either a MemoryUse,
   /// or an already potentially clobbering access. Unlike the above API, if
   /// given a MemoryDef that clobbers the pointer as the starting access, it
   /// will return that MemoryDef, whereas the above would return the clobber
   /// starting from the use side of  the memory def.
   virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
                                                   const MemoryLocation &,
                                                   BatchAAResults &AA) = 0;
 
   MemoryAccess *getClobberingMemoryAccess(const Instruction *I) {
     BatchAAResults BAA(MSSA->getAA());
     return getClobberingMemoryAccess(I, BAA);
   }
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA) {
     BatchAAResults BAA(MSSA->getAA());
     return getClobberingMemoryAccess(MA, BAA);
   }
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                           const MemoryLocation &Loc) {
     BatchAAResults BAA(MSSA->getAA());
     return getClobberingMemoryAccess(MA, Loc, BAA);
   }
 
   /// Given a memory access, invalidate anything this walker knows about
   /// that access.
   /// This API is used by walkers that store information to perform basic cache
   /// invalidation.  This will be called by MemorySSA at appropriate times for
   /// the walker it uses or returns.
   virtual void invalidateInfo(MemoryAccess *) {}
 
 protected:
   friend class MemorySSA; // For updating MSSA pointer in MemorySSA move
                           // constructor.
   MemorySSA *MSSA;
 };
 
 /// A MemorySSAWalker that does no alias queries, or anything else. It
 /// simply returns the links as they were constructed by the builder.
 class DoNothingMemorySSAWalker final : public MemorySSAWalker {
 public:
   // Keep the overrides below from hiding the Instruction overload of
   // getClobberingMemoryAccess.
   using MemorySSAWalker::getClobberingMemoryAccess;
 
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
                                           BatchAAResults &) override;
   MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
                                           const MemoryLocation &,
                                           BatchAAResults &) override;
 };
 
 using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
 using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
 
 /// Iterator base class used to implement const and non-const iterators
 /// over the defining accesses of a MemoryAccess.
 template <class T>
 class memoryaccess_def_iterator_base
     : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
                                   std::forward_iterator_tag, T, ptrdiff_t, T *,
                                   T *> {
   using BaseT = typename memoryaccess_def_iterator_base::iterator_facade_base;
 
 public:
   memoryaccess_def_iterator_base(T *Start) : Access(Start) {}
   memoryaccess_def_iterator_base() = default;
 
   bool operator==(const memoryaccess_def_iterator_base &Other) const {
     return Access == Other.Access && (!Access || ArgNo == Other.ArgNo);
   }
 
   // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
   // block from the operand in constant time (In a PHINode, the uselist has
   // both, so it's just subtraction). We provide it as part of the
   // iterator to avoid callers having to linear walk to get the block.
   // If the operation becomes constant time on MemoryPHI's, this bit of
   // abstraction breaking should be removed.
   BasicBlock *getPhiArgBlock() const {
     MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
     assert(MP && "Tried to get phi arg block when not iterating over a PHI");
     return MP->getIncomingBlock(ArgNo);
   }
 
   typename std::iterator_traits<BaseT>::pointer operator*() const {
     assert(Access && "Tried to access past the end of our iterator");
     // Go to the first argument for phis, and the defining access for everything
     // else.
     if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
       return MP->getIncomingValue(ArgNo);
     return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
   }
 
   using BaseT::operator++;
   memoryaccess_def_iterator_base &operator++() {
     assert(Access && "Hit end of iterator");
     if (const MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
       if (++ArgNo >= MP->getNumIncomingValues()) {
         ArgNo = 0;
         Access = nullptr;
       }
     } else {
       Access = nullptr;
     }
     return *this;
   }
 
 private:
   T *Access = nullptr;
   unsigned ArgNo = 0;
 };
 
 inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
   return memoryaccess_def_iterator(this);
 }
 
 inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
   return const_memoryaccess_def_iterator(this);
 }
 
 inline memoryaccess_def_iterator MemoryAccess::defs_end() {
   return memoryaccess_def_iterator();
 }
 
 inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
   return const_memoryaccess_def_iterator();
 }
 
 /// GraphTraits for a MemoryAccess, which walks defs in the normal case,
 /// and uses in the inverse case.
 template <> struct GraphTraits<MemoryAccess *> {
   using NodeRef = MemoryAccess *;
   using ChildIteratorType = memoryaccess_def_iterator;
 
   static NodeRef getEntryNode(NodeRef N) { return N; }
   static ChildIteratorType child_begin(NodeRef N) { return N->defs_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
 };
 
 template <> struct GraphTraits<Inverse<MemoryAccess *>> {
   using NodeRef = MemoryAccess *;
   using ChildIteratorType = MemoryAccess::iterator;
 
   static NodeRef getEntryNode(NodeRef N) { return N; }
   static ChildIteratorType child_begin(NodeRef N) { return N->user_begin(); }
   static ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
 };
 
 /// Provide an iterator that walks defs, giving both the memory access,
 /// and the current pointer location, updating the pointer location as it
 /// changes due to phi node translation.
 ///
 /// This iterator, while somewhat specialized, is what most clients actually
 /// want when walking upwards through MemorySSA def chains. It takes a pair of
 /// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
 /// memory location through phi nodes for the user.
 class upward_defs_iterator
     : public iterator_facade_base<upward_defs_iterator,
                                   std::forward_iterator_tag,
                                   const MemoryAccessPair> {
   using BaseT = upward_defs_iterator::iterator_facade_base;
 
 public:
   upward_defs_iterator(const MemoryAccessPair &Info, DominatorTree *DT)
       : DefIterator(Info.first), Location(Info.second),
         OriginalAccess(Info.first), DT(DT) {
     CurrentPair.first = nullptr;
 
     WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
     fillInCurrentPair();
   }
 
   upward_defs_iterator() { CurrentPair.first = nullptr; }
 
   bool operator==(const upward_defs_iterator &Other) const {
     return DefIterator == Other.DefIterator;
   }
 
   typename std::iterator_traits<BaseT>::reference operator*() const {
     assert(DefIterator != OriginalAccess->defs_end() &&
            "Tried to access past the end of our iterator");
     return CurrentPair;
   }
 
   using BaseT::operator++;
   upward_defs_iterator &operator++() {
     assert(DefIterator != OriginalAccess->defs_end() &&
            "Tried to access past the end of the iterator");
     ++DefIterator;
     if (DefIterator != OriginalAccess->defs_end())
       fillInCurrentPair();
     return *this;
   }
 
   BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
 
 private:
   /// Returns true if \p Ptr is guaranteed to be loop invariant for any possible
   /// loop. In particular, this guarantees that it only references a single
   /// MemoryLocation during execution of the containing function.
   bool IsGuaranteedLoopInvariant(const Value *Ptr) const;
 
   void fillInCurrentPair() {
     CurrentPair.first = *DefIterator;
     CurrentPair.second = Location;
     if (WalkingPhi && Location.Ptr) {
       PHITransAddr Translator(
           const_cast<Value *>(Location.Ptr),
           OriginalAccess->getBlock()->getDataLayout(), nullptr);
 
       if (Value *Addr =
               Translator.translateValue(OriginalAccess->getBlock(),
                                         DefIterator.getPhiArgBlock(), DT, true))
         if (Addr != CurrentPair.second.Ptr)
           CurrentPair.second = CurrentPair.second.getWithNewPtr(Addr);
 
       // Mark size as unknown, if the location is not guaranteed to be
       // loop-invariant for any possible loop in the function. Setting the size
       // to unknown guarantees that any memory accesses that access locations
       // after the pointer are considered as clobbers, which is important to
       // catch loop carried dependences.
       if (!IsGuaranteedLoopInvariant(CurrentPair.second.Ptr))
         CurrentPair.second = CurrentPair.second.getWithNewSize(
             LocationSize::beforeOrAfterPointer());
     }
   }
 
   MemoryAccessPair CurrentPair;
   memoryaccess_def_iterator DefIterator;
   MemoryLocation Location;
   MemoryAccess *OriginalAccess = nullptr;
   DominatorTree *DT = nullptr;
   bool WalkingPhi = false;
 };
 
 inline upward_defs_iterator
 upward_defs_begin(const MemoryAccessPair &Pair, DominatorTree &DT) {
   return upward_defs_iterator(Pair, &DT);
 }
 
 inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
 
 inline iterator_range<upward_defs_iterator>
 upward_defs(const MemoryAccessPair &Pair, DominatorTree &DT) {
   return make_range(upward_defs_begin(Pair, DT), upward_defs_end());
 }
 
 /// Walks the defining accesses of MemoryDefs. Stops after we hit something that
 /// has no defining use (e.g. a MemoryPhi or liveOnEntry). Note that, when
 /// comparing against a null def_chain_iterator, this will compare equal only
 /// after walking said Phi/liveOnEntry.
 ///
 /// The UseOptimizedChain flag specifies whether to walk the clobbering
 /// access chain, or all the accesses.
 ///
 /// Normally, MemoryDef are all just def/use linked together, so a def_chain on
 /// a MemoryDef will walk all MemoryDefs above it in the program until it hits
 /// a phi node.  The optimized chain walks the clobbering access of a store.
 /// So if you are just trying to find, given a store, what the next
 /// thing that would clobber the same memory is, you want the optimized chain.
 template <class T, bool UseOptimizedChain = false>
 struct def_chain_iterator
     : public iterator_facade_base<def_chain_iterator<T, UseOptimizedChain>,
                                   std::forward_iterator_tag, MemoryAccess *> {
   def_chain_iterator() : MA(nullptr) {}
   def_chain_iterator(T MA) : MA(MA) {}
 
   T operator*() const { return MA; }
 
   def_chain_iterator &operator++() {
     // N.B. liveOnEntry has a null defining access.
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {
       if (UseOptimizedChain && MUD->isOptimized())
         MA = MUD->getOptimized();
       else
         MA = MUD->getDefiningAccess();
     } else {
       MA = nullptr;
     }
 
     return *this;
   }
 
   bool operator==(const def_chain_iterator &O) const { return MA == O.MA; }
 
 private:
   T MA;
 };
 
 template <class T>
 inline iterator_range<def_chain_iterator<T>>
 def_chain(T MA, MemoryAccess *UpTo = nullptr) {
 #ifdef EXPENSIVE_CHECKS
   assert((!UpTo || find(def_chain(MA), UpTo) != def_chain_iterator<T>()) &&
          "UpTo isn't in the def chain!");
 #endif
   return make_range(def_chain_iterator<T>(MA), def_chain_iterator<T>(UpTo));
 }
 
 template <class T>
 inline iterator_range<def_chain_iterator<T, true>> optimized_def_chain(T MA) {
   return make_range(def_chain_iterator<T, true>(MA),
                     def_chain_iterator<T, true>(nullptr));
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_MEMORYSSA_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team