This patch hijacks Danny's MemorySSA, a virtual SSA form for memory. Details on what it looks like are in MemorySSA.h

[george.burgess.iv]

Summary

Note: This is a continued review from D7864. I can’t figure out how to take ownership of that revision, so I made my own. Reviewers/subscribers were taken from said revision.

Changes to the prior patch:

Did a minor overhaul of the code + added tests. On the whole, the algorithms are the same.

Changes in more words:

• Took out the update API at Danny’s request
• Added a few tests, including the case that Hal mentioned (at multiple-backedges-hal.ll )
• Added an abstract MemoryUseOrDef class to more cleanly separate MemoryUses from MemoryDefs
• A few minor bug fixes
• A few minor optimizations (took out some virtual functions, stored things in e.g. PointerIntPairs, ...)
• Minor refactors throughout in an attempt to improve code clarity and robustness

There are a few FIXMEs scattered about that I’ll address before committing, and a few that I won’t (read: no plans to fix the FIXMEs in MemoryAccess before upstreaming this. That will probably come when MemorySSA becomes more mature/has most of its APIs ironed out and implemented).

If anything seems sketchy, please let me know. I’m about 98% sure I know how everything’s meant to work, so I could certainly be wrong. :)

Any suggestions for more test cases are appreciated, as well. I plan to add a few more prior to upstreaming, but this is more or less what I could come up with.

Old summary:

There is no grand scheme to use this across LLVM (at least, that i have).
The main purposees for it are to clean and speed up things like MemoryDependenceAnalysis
(which spends a lot of time walking to find use/defs of memory, etc), and to
be able to provide load value numbering to GVN (and PRE).
Secondarily, it may be possible to speed up some of the other load/store
motion passes using it.

Note that creation of MemorySSA is linear time and space relative to the IR
size. It uses the same linear time phi placement algorithm PromoteMemoryToRegisters does
(though sadly, not the same code because abstracting PromoteMemoryToRegisters
is not easy since we don't derive the memory access classes from things
like Value, etc)

It's lived both as a utility that passes could create and delete, and as a pass.
In the current patch, it's a functionpass that things can require
as an analysis.
Happy to put it back to being a utility, not sure which makes more sense.
I only have GVN using it right now.

As a small note: The immediate-use lists are ugly right now. Suggestions for how to do
that better welcome.

Anyway, happy to answer any questions, and not looking to commit this tomorrow,
more it got to the point where i think it would be good to get some other eyes
on it.

[davidxl]

include/llvm/Transforms/Utils/MemorySSA.h

16

nit: missing period.

18

nit: missing period at the end.

186

In the context when user_begin() is called, the memoryAccess must be a def. Given that assumption, you can safely DownCast the memoryAccess to MemoryDef -- the problem is both Def and Phi need to be handled.

203

I have another suggestion of the hierarchy:

Strictly speaking a MemoryDef and MemoryUse is not the IsA relationship, but a hasA relationship -- basically a memory def is not a use, but it has any implicit may use to model the may-kill. With that in mind, it is probably not a good idea to factor out UseOrDef out as the common ancestor of MemoryDef and MemoryUse. Instead:

1. MemoryDef should have a pointer to a memoryUse instance
2. MemoryDef and Phi Node should have a common ancestor DefOrPhi as drawn above.

Pros: the userList can now be moved into DefOrPhi
Cons: get|setDefininingAccess method now needs to be declared as virtual in MemoryAccess base and overridden in MemoryUse and MemoryDef. For MemoryDef, it just need to forward the call to the memoryUse it owns.

To avoid virtual call, the memoryAccess can do dispatching via DownCasting depending on memoryAccess type.

333

Is this redundant? There is one in base class.

[• dberlin]

Note: You can commandeer the old revision.
In the drop down near the comment box, select "commandeer revision" and you
will take it over.

I would suggest doing that to keep the history going :)

[george.burgess.iv]

Commandeered D7864, as requested.

include/llvm/Transforms/Utils/MemorySSA.h

186

Marking as done, assuming that we want to go with dannyb's "everything is a subclass of User" approach. :)

203

Marking as done, assuming that we want to go with dannyb's "everything is a subclass of User" approach.

333

Nice catch! Remnant of trying different designs.

include/llvm/IR/Function.h

/// @}
   bool hasPrologueData() const {
     return getSubclassDataFromValue() & (1<<2);
   }
 
   /// \brief Get the prologue data associated with this function.
   Constant *getPrologueData() const;
   void setPrologueData(Constant *PrologueData);
 
+  /// Print the function to an output stream with an optional
+  /// AssemblyAnnotationWriter.
+  void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW = nullptr,
+             bool ShouldPreserveUseListOrder = false,
+             bool IsForDebug = false) const;
+
   /// viewCFG - This function is meant for use from the debugger.  You can just
   /// say 'call F->viewCFG()' and a ghostview window should pop up from the
   /// program, displaying the CFG of the current function with the code for each
   /// basic block inside.  This depends on there being a 'dot' and 'gv' program
   /// in your path.
   ///
   void viewCFG() const;
 

include/llvm/InitializePasses.h

 void initializeMachineSchedulerPass(PassRegistry&);
 void initializeMachineSinkingPass(PassRegistry&);
 void initializeMachineTraceMetricsPass(PassRegistry&);
 void initializeMachineVerifierPassPass(PassRegistry&);
 void initializeMemCpyOptPass(PassRegistry&);
 void initializeMemDepPrinterPass(PassRegistry&);
 void initializeMemDerefPrinterPass(PassRegistry&);
 void initializeMemoryDependenceAnalysisPass(PassRegistry&);
+void initializeMemorySSALazyPass(PassRegistry&);
+void initializeMemorySSAPrinterPassPass(PassRegistry&);
 void initializeMergedLoadStoreMotionPass(PassRegistry &);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeNaryReassociatePass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
 void initializeObjCARCAAWrapperPassPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);

include/llvm/Transforms/Utils/MemorySSA.h

+//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// \file
+// \brief 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 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(4)
+//   %7 = load i32* %2, align 4
+//   ; MemoryUse(3)
+//   %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 MemoryUse's,
+// but not the RHS of memorydefs. You can see this above at %8, 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.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H
+#define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+class BasicBlock;
+class DominatorTree;
+class Function;
+class MemoryAccess;
+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>;
+
+// \brief The base for all memory accesses. All memory accesses in a block are
+// linked together using an intrusive list.
+class MemoryAccess : public ilist_node<MemoryAccess> {
+public:
+  // Methods for support type inquiry through isa, cast, and
+  // dyn_cast
+  static inline bool classof(const MemoryAccess *) { return true; }
+
+  virtual ~MemoryAccess();
+  BasicBlock *getBlock() const { return BlockAccessPair.getPointer(); }
+
+  virtual void print(raw_ostream &OS) const = 0;
+  virtual void dump() const;
+
+  // FIXME: SmallSize=8 originally. Dropped to 4 until the FIXME above `Users`
+  // gets sorted out.
+  using UserListType = SmallPtrSet<MemoryAccess *, 4>;
+  using iterator = UserListType::iterator;
+  using const_iterator = UserListType::const_iterator;
+
+  unsigned user_size() const { return Users.size(); }
+  bool user_empty() const { return Users.empty(); }
+  iterator user_begin() { return Users.begin(); }
+  iterator user_end() { return Users.end(); }
+  iterator_range<iterator> users() {
+    return iterator_range<iterator>(user_begin(), user_end());
+  }
+
+  const_iterator user_begin() const { return Users.begin(); }
+  const_iterator user_end() const { return Users.end(); }
+  iterator_range<const_iterator> uses() const {
+    return iterator_range<const_iterator>(user_begin(), user_end());
+  }
+
+  /// \brief 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;
+
+protected:
+  enum MemoryAccessType : uint8_t { AccessUse, AccessDef, AccessPhi };
+  constexpr static unsigned BitsInMemoryAccessType = 2;
+
+  friend class MemorySSA;
+  friend class MemoryUseOrDef;
+  friend class MemoryUse;
+  friend class MemoryDef;
+  friend class MemoryPhi;
+
+  MemoryAccessType getAccessType() const { return BlockAccessPair.getInt(); }
+
+  // More of an assumption than a hard constraint that will subtly break
+  // existing code. Feel free to remove if this fires for valid reasons.
+  void assumeIsNotUse() const {
+    assert(getAccessType() != AccessUse && "MemoryUses can have users?");
+  }
+
+  /// \brief Add a use of this memory access to our list of uses.
+  ///
+  /// Note: We depend on being able to add the same use multiple times and not
+  /// have it end up in our use list multiple times.
+  void addUse(MemoryAccess *Use) {
+    assumeIsNotUse();
+    Users.insert(Use);
+  }
+
+  /// \brief Remove a use of this memory access from our list of uses.
+  void removeUse(MemoryAccess *Use) {
+    assumeIsNotUse();
+    Users.erase(Use);
+  }
+
+  /// \brief Return true if \p Use is one of the uses of this memory access.
+  bool hasUse(MemoryAccess *Use) const {
+    assumeIsNotUse();
+    return Users.count(Use);
+  }
+
+  MemoryAccess(MemoryAccessType AT, BasicBlock *BB) : BlockAccessPair(BB, AT) {}
+
+  /// \brief Used internally to give IDs to MemoryAccesses for printing
+  virtual unsigned getID() const = 0;
+
+private:
+  MemoryAccess(const MemoryAccess &);
+  void operator=(const MemoryAccess &);
+
+  // FIXME(gbiv): MemoryUses don't have users. The quick fix for this would be
+  // to make a virtual `getUsers()` with llvm_unreachable in MemoryUse, but I'd
+  // assume that would be a bad tradeoff for speed vs memory consumption, and
+  // it's mildly suboptimal for type safety (but no more than the current
+  // approach).
+  //
+  // Switching to a traits-based system may be better for code duplication,
+  // efficiency, and type-safety, but potentially more difficult to
+  // grok/maintain/modify.
+  //
+  // We could also have an inheritance tree like
+  //        MemoryAccess
+  //       /            \
+  //    UseOrDef     DefOrPhi
+  //   /        \   /        \
+  //  Use        Def         Phi
+  //
+  // ...But then virtual base classes happen (diamond between MemoryAccess and
+  // Def), and those are icky. Not sure if the trait system would need virtual
+  // bases.
+  UserListType Users;
+  const PointerIntPair<BasicBlock *, BitsInMemoryAccessType, MemoryAccessType>
+      BlockAccessPair;
+};
+
+template <>
+struct ilist_traits<MemoryAccess> : public ilist_default_traits<MemoryAccess> {
+  // See details of the instruction class for why this trick works
+  MemoryAccess *createSentinel() const {
+    return static_cast<MemoryAccess *>(&Sentinel);
+  }
+
+  static void destroySentinel(MemoryAccess *) {}
+
+  MemoryAccess *provideInitialHead() const { return createSentinel(); }
+  MemoryAccess *ensureHead(MemoryAccess *) const { return createSentinel(); }
+  static void noteHead(MemoryAccess *, MemoryAccess *) {}
+
+private:
+  mutable ilist_half_node<MemoryAccess> Sentinel;
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
+  MA.print(OS);
+  return OS;
+}
+
+/// \brief 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:
+  /// \brief Get the instruction that this MemoryUse represents.
+  Instruction *getMemoryInst() const { return MemoryInst; }
+
+  /// \brief Get the access that produces the memory state used by this Use.
+  MemoryAccess *getDefiningAccess() const { return DefiningAccess; }
+
+  static inline bool classof(const MemoryUseOrDef *) { return true; }
+  static inline bool classof(const MemoryAccess *MA) {
+    return MA->getAccessType() == AccessUse || MA->getAccessType() == AccessDef;
+  }
+
+protected:
+  friend class MemorySSA;
+
+  MemoryUseOrDef(MemoryAccess *DMA, MemoryAccessType AT, Instruction *MI,
+                 BasicBlock *BB)
+      : MemoryAccess(AT, BB), DefiningAccess(nullptr), MemoryInst(MI) {
+    setDefiningAccess(DMA);
+  }
+
+  void setDefiningAccess(MemoryAccess *DMA) {
+    if (DefiningAccess == DMA)
+      return;
+
+    if (DefiningAccess)
+      DefiningAccess->removeUse(this);
+    if (DMA)
+      DMA->addUse(this);
+    DefiningAccess = DMA;
+  }
+
+private:
+  MemoryAccess *DefiningAccess;
+  Instruction *MemoryInst;
+};
+
+/// \brief 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 {
+public:
+  MemoryUse(MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
+      : MemoryUseOrDef(DMA, AccessUse, MI, BB) {}
+
+  static inline bool classof(const MemoryUse *) { return true; }
+  static inline bool classof(const MemoryAccess *MA) {
+    return MA->getAccessType() == AccessUse;
+  }
+
+  void print(raw_ostream &OS) const override;
+
+protected:
+  friend class MemorySSA;
+
+  unsigned getID() const override {
+    llvm_unreachable("MemoryUses do not have IDs");
+  }
+};
+
+/// \brief 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 {
+public:
+  MemoryDef(MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, unsigned Ver)
+      : MemoryUseOrDef(DMA, AccessDef, MI, BB), ID(Ver) {}
+
+  static inline bool classof(const MemoryDef *) { return true; }
+  static inline bool classof(const MemoryAccess *MA) {
+    return MA->getAccessType() == AccessDef;
+  }
+
+  void print(raw_ostream &OS) const override;
+
+protected:
+  friend class MemorySSA;
+
+  // For debugging only. This gets used to give memory accesses pretty numbers
+  // when printing them out
+  unsigned getID() const override { return ID; }
+
+private:
+  const unsigned ID;
+  UserListType Users;
+};
+
+/// \brief 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 {
+public:
+  MemoryPhi(BasicBlock *BB, unsigned Ver, unsigned NumPreds = 0)
+      : MemoryAccess(AccessPhi, BB), ID(Ver) {
+    Operands.reserve(NumPreds);
+  }
+
+  /// \brief This is the number of incoming values currently in use
+  ///
+  /// During SSA construction, we differentiate between this and NumPreds to
+  /// know when the PHI node is fully constructed.
+  unsigned getNumIncomingValues() const { return Operands.size(); }
+
+  MemoryAccess *getIncomingValue(unsigned V) const {
+    return getOperand(V).second;
+  }
+
+  BasicBlock *getIncomingBlock(unsigned V) const { return getOperand(V).first; }
+
+  using Operand = std::pair<BasicBlock *, MemoryAccess *>;
+  const Operand &getOperand(unsigned V) const {
+    assert(V < Operands.size() && "Out of bounds Operand access");
+    return Operands[V];
+  }
+
+  using OperandsType = SmallVector<Operand, 4>;
+  using const_op_iterator = OperandsType::const_iterator;
+  inline const_op_iterator ops_begin() const { return Operands.begin(); }
+  inline const_op_iterator ops_end() const { return Operands.end(); }
+  inline iterator_range<const_op_iterator> operands() const {
+    return iterator_range<const_op_iterator>(ops_begin(), ops_end());
+  }
+
+  static inline bool classof(const MemoryPhi *) { return true; }
+  static inline bool classof(const MemoryAccess *MA) {
+    return MA->getAccessType() == AccessPhi;
+  }
+
+  void print(raw_ostream &OS) const override;
+
+protected:
+  friend class MemorySSA;
+
+  // MemorySSA currently cannot handle modifications. This is protected to
+  // ensure people don't try to modify things.
+  void addIncoming(MemoryAccess *MA, BasicBlock *BB) {
+    assert((isa<MemoryPhi>(MA) || isa<MemoryDef>(MA)) &&
+           "Only MemoryPhis or MemoryDefs can be incoming values");
+    Operands.push_back(std::make_pair(BB, MA));
+    MA->addUse(this);
+  }
+
+  // For debugging only. This gets used to give memory accesses pretty numbers
+  // when printing them out
+  virtual unsigned getID() const final { return ID; }
+
+private:
+  // For debugging only
+  const unsigned ID;
+  // FIXME(gbiv): Does having multiple of the same operand make a difference at
+  // all?
+  OperandsType Operands;
+  UserListType Users;
+};
+
+class MemorySSAWalker;
+
+/// \brief Encapsulates MemorySSA, including all data associated with memory
+/// accesses.
+class MemorySSA {
+public:
+  MemorySSA(Function &);
+  ~MemorySSA();
+
+  /// \brief Build Memory SSA, and return the walker we used during building,
+  /// for later reuse. If MemorySSA is already built, just return the walker.
+  MemorySSAWalker *buildMemorySSA(AliasAnalysis *, DominatorTree *);
+
+  /// \brief Returns false if you need to call buildMemorySSA.
+  bool isFinishedBuilding() const { return Walker; }
+
+  /// \brief 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.
+  MemoryAccess *getMemoryAccess(const Value *) const;
+  MemoryPhi *getMemoryAccess(const BasicBlock *BB) const;
+
+  void dump() const;
+  void print(raw_ostream &) const;
+
+  /// \brief 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();
+  }
+
+  using AccessListType = iplist<MemoryAccess>;
+
+  /// \brief Return the list of MemoryAccess's for a given basic block.
+  ///
+  /// This list is not modifiable by the user.
+  const AccessListType *getBlockAccesses(const BasicBlock *BB) const {
+    auto It = PerBlockAccesses.find(BB);
+    return It == PerBlockAccesses.end() ? nullptr : It->second.get();
+  }
+
+  enum InsertionPlace { Beginning, End };
+
+  /// \brief 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;
+
+protected:
+  // Used by Memory SSA annotater, dumpers, and wrapper pass
+  friend class MemorySSAAnnotatedWriter;
+  friend class MemorySSAPrinterPass;
+  void verifyDefUses(Function &F);
+  void verifyDomination(Function &F);
+
+private:
+  void verifyUseInDefs(MemoryAccess *, MemoryAccess *);
+  using AccessMap =
+      DenseMap<const BasicBlock *, std::unique_ptr<AccessListType>>;
+
+  void
+  determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
+  void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
+  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
+  bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
+  MemoryAccess *createNewAccess(Instruction *, bool ignoreNonMemory = false);
+  MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
+
+  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *);
+  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
+                  SmallPtrSet<BasicBlock *, 16> &Visited);
+  AccessListType *getOrCreateAccessList(BasicBlock *);
+  AliasAnalysis *AA;
+  DominatorTree *DT;
+  Function &F;
+
+  // Memory SSA mappings
+  DenseMap<const Value *, MemoryAccess *> InstructionToMemoryAccess;
+  AccessMap PerBlockAccesses;
+  std::unique_ptr<MemoryAccess> LiveOnEntryDef;
+
+  // Memory SSA building info
+  MemorySSAWalker *Walker;
+  unsigned NextID;
+};
+
+// This pass does eager building and then printing of MemorySSA. It is used by
+// the tests to be able to build, dump, and verify Memory SSA.
+class MemorySSAPrinterPass : public FunctionPass {
+public:
+  MemorySSAPrinterPass();
+
+  static char ID;
+  bool doInitialization(Module &M) override;
+  bool runOnFunction(Function &) override;
+  void releaseMemory() override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void print(raw_ostream &OS, const Module *M) const override;
+  static void registerOptions();
+  MemorySSA &getMSSA() { return *MSSA; }
+
+private:
+  bool VerifyMemorySSA;
+
+  std::unique_ptr<MemorySSA> MSSA;
+  // FIXME(gbiv): It seems that MemorySSA doesn't own the walker it returns?
+  std::unique_ptr<MemorySSAWalker> Walker;
+  Function *F;
+};
+
+class MemorySSALazy : public FunctionPass {
+public:
+  MemorySSALazy();
+
+  static char ID;
+  bool runOnFunction(Function &) override;
+  void releaseMemory() override;
+  MemorySSA &getMSSA() {
+    assert(MSSA);
+    return *MSSA;
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+
+private:
+  std::unique_ptr<MemorySSA> MSSA;
+};
+
+/// \brief 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() {}
+
+  using MemoryAccessSet = SmallVector<MemoryAccess *, 8>;
+
+  /// \brief 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.
+  virtual MemoryAccess *getClobberingMemoryAccess(const Instruction *) = 0;
+
+  /// \brief 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 *,
+                                                  MemoryLocation &) = 0;
+
+protected:
+  MemorySSA *MSSA;
+};
+
+/// \brief 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:
+  MemoryAccess *getClobberingMemoryAccess(const Instruction *) override;
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                          MemoryLocation &) override;
+};
+
+using MemoryAccessPair = std::pair<MemoryAccess *, MemoryLocation>;
+using ConstMemoryAccessPair = std::pair<const MemoryAccess *, MemoryLocation>;
+
+/// \brief A MemorySSAWalker that does AA walks and caching of lookups to
+/// disambiguate accesses.
+class CachingMemorySSAWalker final : public MemorySSAWalker {
+public:
+  CachingMemorySSAWalker(MemorySSA *, AliasAnalysis *, DominatorTree *);
+  virtual ~CachingMemorySSAWalker();
+  MemoryAccess *getClobberingMemoryAccess(const Instruction *) override;
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                          MemoryLocation &) override;
+
+protected:
+  struct UpwardsMemoryQuery;
+  MemoryAccess *doCacheLookup(const MemoryAccess *, const UpwardsMemoryQuery &,
+                              const MemoryLocation &);
+
+  void doCacheInsert(const MemoryAccess *, MemoryAccess *,
+                     const UpwardsMemoryQuery &, const MemoryLocation &);
+
+  void doCacheRemove(const MemoryAccess *, const UpwardsMemoryQuery &,
+                     const MemoryLocation &);
+
+private:
+  MemoryAccessPair UpwardsDFSWalk(MemoryAccess *, const MemoryLocation &,
+                                  UpwardsMemoryQuery &, bool);
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *, UpwardsMemoryQuery &);
+  bool instructionClobbersQuery(const MemoryDef *, UpwardsMemoryQuery &,
+                                const MemoryLocation &Loc) const;
+  SmallDenseMap<ConstMemoryAccessPair, MemoryAccess *>
+      CachedUpwardsClobberingAccess;
+  DenseMap<const MemoryAccess *, MemoryAccess *> CachedUpwardsClobberingCall;
+  AliasAnalysis *AA;
+  DominatorTree *DT;
+};
+
+/// \brief 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), ArgNo(0) {}
+  memoryaccess_def_iterator_base() : Access(nullptr), ArgNo(0) {}
+  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 BaseT::iterator::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 (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
+      return MP->getIncomingValue(ArgNo);
+    return cast<MemoryUseOrDef>(Access)->getDefiningAccess();
+  }
+  using BaseT::operator++;
+  memoryaccess_def_iterator &operator++() {
+    assert(Access && "Hit end of iterator");
+    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
+      if (++ArgNo >= MP->getNumIncomingValues()) {
+        ArgNo = 0;
+        Access = nullptr;
+      }
+    } else {
+      Access = nullptr;
+    }
+    return *this;
+  }
+
+private:
+  T *Access;
+  unsigned ArgNo;
+};
+
+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();
+}
+
+/// \brief GraphTraits for a MemoryAccess, which walks defs in the normal case,
+/// and uses in the inverse case.
+template <> struct GraphTraits<MemoryAccess *> {
+  using NodeType = MemoryAccess;
+  using ChildIteratorType = memoryaccess_def_iterator;
+
+  static NodeType *getEntryNode(NodeType *N) { return N; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->defs_begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->defs_end();
+  }
+};
+
+template <> struct GraphTraits<Inverse<MemoryAccess *>> {
+  using NodeType = MemoryAccess;
+  using ChildIteratorType = MemoryAccess::iterator;
+
+  static NodeType *getEntryNode(NodeType *N) { return N; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->user_begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->user_end();
+  }
+};
+
+/// \brief 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)
+      : DefIterator(Info.first), Location(Info.second),
+        OriginalAccess(Info.first) {
+    CurrentPair.first = nullptr;
+
+    WalkingPhi = Info.first && isa<MemoryPhi>(Info.first);
+    fillInCurrentPair();
+  }
+
+  upward_defs_iterator()
+      : DefIterator(), Location(), OriginalAccess(), WalkingPhi(false) {
+    CurrentPair.first = nullptr;
+  }
+
+  bool operator==(const upward_defs_iterator &Other) const {
+    return DefIterator == Other.DefIterator;
+  }
+
+  typename BaseT::iterator::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:
+  void fillInCurrentPair() {
+    CurrentPair.first = *DefIterator;
+    if (WalkingPhi && Location.Ptr) {
+      PHITransAddr Translator(
+          const_cast<Value *>(Location.Ptr),
+          OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
+      if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
+                                        DefIterator.getPhiArgBlock(), nullptr,
+                                        false))
+        if (Translator.getAddr() != Location.Ptr) {
+          CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
+          return;
+        }
+    }
+    CurrentPair.second = Location;
+  }
+
+  MemoryAccessPair CurrentPair;
+  memoryaccess_def_iterator DefIterator;
+  MemoryLocation Location;
+  MemoryAccess *OriginalAccess;
+  bool WalkingPhi;
+};
+
+inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) {
+  return upward_defs_iterator(Pair);
+}
+inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
+}
+
+#endif

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
   initializeLazyValueInfoPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceAnalysisPass(Registry);
+  initializeMemorySSALazyPass(Registry);
+  initializeMemorySSAPrinterPassPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeObjCARCAAWrapperPassPass(Registry);
   initializePostDominatorTreePass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);

lib/IR/AsmWriter.cpp

while (hasMore()) {
     UseListOrders.pop_back();
   }
 }
 
 //===----------------------------------------------------------------------===//
 //                       External Interface declarations
 //===----------------------------------------------------------------------===//
 
+void Function::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW,
+                     bool ShouldPreserveUseListOrder,
+                     bool IsForDebug) const {
+  SlotTracker SlotTable(this->getParent());
+  formatted_raw_ostream OS(ROS);
+  AssemblyWriter W(OS, SlotTable, this->getParent(), AAW,
+                   IsForDebug,
+                   ShouldPreserveUseListOrder);
+  W.printFunction(this);
+}
+
 void Module::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW,
                    bool ShouldPreserveUseListOrder, bool IsForDebug) const {
   SlotTracker SlotTable(this);
   formatted_raw_ostream OS(ROS);
   AssemblyWriter W(OS, SlotTable, this, AAW, IsForDebug,
                    ShouldPreserveUseListOrder);
   W.printModule(this);
 }

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   LoopSimplify.cpp
   LoopUnroll.cpp
   LoopUnrollRuntime.cpp
   LoopUtils.cpp
   LoopVersioning.cpp
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
+  MemorySSA.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   PromoteMemoryToRegister.cpp
   SSAUpdater.cpp
   SanitizerStats.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp

lib/Transforms/Utils/MemorySSA.cpp

+//===-- MemorySSA.cpp - Memory SSA Builder---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------===//
+//
+// This file implements the MemorySSA class.
+//
+//===----------------------------------------------------------------===//
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/IteratedDominanceFrontier.h"
+#include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/IR/AssemblyAnnotationWriter.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/MemorySSA.h"
+#include <algorithm>
+
+#define DEBUG_TYPE "memoryssa"
+using namespace llvm;
+STATISTIC(NumClobberCacheLookups, "Number of Memory SSA version cache lookups");
+STATISTIC(NumClobberCacheHits, "Number of Memory SSA version cache hits");
+STATISTIC(NumClobberCacheInserts, "Number of MemorySSA version cache inserts");
+INITIALIZE_PASS_WITH_OPTIONS_BEGIN(MemorySSAPrinterPass, "print-memoryssa",
+                                   "Memory SSA", true, true)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
+INITIALIZE_PASS_END(MemorySSAPrinterPass, "print-memoryssa", "Memory SSA", true,
+                    true)
+INITIALIZE_PASS(MemorySSALazy, "memoryssalazy", "Memory SSA", true, true)
+
+namespace llvm {
+
+/// \brief An assembly annotator class to print Memory SSA information in
+/// comments.
+class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter {
+  friend class MemorySSA;
+  const MemorySSA *MSSA;
+
+public:
+  MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {}
+
+  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
+                                        formatted_raw_ostream &OS) {
+    if (MemoryAccess *MA = MSSA->getMemoryAccess(BB))
+      OS << "; " << *MA << "\n";
+  }
+
+  virtual void emitInstructionAnnot(const Instruction *I,
+                                    formatted_raw_ostream &OS) {
+    if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
+      OS << "; " << *MA << "\n";
+  }
+};
+}
+
+namespace {
+struct RenamePassData {
+  DomTreeNode *DTN;
+  DomTreeNode::const_iterator ChildIt;
+  MemoryAccess *IncomingVal;
+
+  RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
+                 MemoryAccess *M)
+      : DTN(D), ChildIt(It), IncomingVal(M) {}
+  void swap(RenamePassData &RHS) {
+    std::swap(DTN, RHS.DTN);
+    std::swap(ChildIt, RHS.ChildIt);
+    std::swap(IncomingVal, RHS.IncomingVal);
+  }
+};
+}
+
+namespace llvm {
+/// \brief Rename a single basic block into MemorySSA form.
+/// Uses the standard SSA renaming algorithm.
+/// \returns The new incoming value.
+MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB,
+                                     MemoryAccess *IncomingVal) {
+  auto It = PerBlockAccesses.find(BB);
+  // Skip most processing if the list is empty.
+  if (It != PerBlockAccesses.end()) {
+    AccessListType *Accesses = It->second.get();
+    for (MemoryAccess &L : *Accesses) {
+      switch (L.getAccessType()) {
+      case MemoryAccess::AccessUse:
+        cast<MemoryUse>(&L)->setDefiningAccess(IncomingVal);
+        break;
+      case MemoryAccess::AccessDef:
+        // We can't legally optimize defs, because we only allow single
+        // memory phis/uses on operations, and if we optimize these, we can
+        // end up with multiple reaching defs. Uses do not have this
+        // problem, since they do not produce a value
+        cast<MemoryDef>(&L)->setDefiningAccess(IncomingVal);
+        IncomingVal = &L;
+        break;
+      case MemoryAccess::AccessPhi:
+        IncomingVal = &L;
+        break;
+      }
+    }
+  }
+
+  // Pass through values to our successors
+  for (const BasicBlock *S : successors(BB)) {
+    auto It = PerBlockAccesses.find(S);
+    // Rename the phi nodes in our successor block
+    if (It == PerBlockAccesses.end() || !isa<MemoryPhi>(It->second->front()))
+      continue;
+    AccessListType *Accesses = It->second.get();
+    auto *Phi = cast<MemoryPhi>(&Accesses->front());
+    assert(std::find(succ_begin(BB), succ_end(BB), S) != succ_end(BB) &&
+           "Must be at least one edge from Succ to BB!");
+    Phi->addIncoming(IncomingVal, BB);
+  }
+
+  return IncomingVal;
+}
+
+/// \brief This is the standard SSA renaming algorithm.
+///
+/// We walk the dominator tree in preorder, renaming accesses, and then filling
+/// in phi nodes in our successors.
+void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
+                           SmallPtrSet<BasicBlock *, 16> &Visited) {
+  SmallVector<RenamePassData, 32> WorkStack;
+  IncomingVal = renameBlock(Root->getBlock(), IncomingVal);
+  WorkStack.push_back({Root, Root->begin(), IncomingVal});
+  Visited.insert(Root->getBlock());
+
+  while (!WorkStack.empty()) {
+    DomTreeNode *Node = WorkStack.back().DTN;
+    DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt;
+    IncomingVal = WorkStack.back().IncomingVal;
+
+    if (ChildIt == Node->end()) {
+      WorkStack.pop_back();
+    } else {
+      DomTreeNode *Child = *ChildIt;
+      ++WorkStack.back().ChildIt;
+      BasicBlock *BB = Child->getBlock();
+      Visited.insert(BB);
+      IncomingVal = renameBlock(BB, IncomingVal);
+      WorkStack.push_back({Child, Child->begin(), IncomingVal});
+    }
+  }
+}
+
+/// \brief Compute dominator levels, used by the phi insertion algorithm above.
+void MemorySSA::computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels) {
+  for (auto DFI = df_begin(DT->getRootNode()), DFE = df_end(DT->getRootNode());
+       DFI != DFE; ++DFI)
+    DomLevels[*DFI] = DFI.getPathLength() - 1;
+}
+
+/// \brief This handles unreachable block acccesses by deleting phi nodes in
+/// unreachable blocks, and marking all other unreachable MemoryAccess's as
+/// being uses of the live on entry definition.
+void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) {
+  assert(!DT->isReachableFromEntry(BB) &&
+         "Reachable block found while handling unreachable blocks");
+
+  auto It = PerBlockAccesses.find(BB);
+  if (It == PerBlockAccesses.end())
+    return;
+
+  auto &Accesses = It->second;
+  for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
+    auto Next = std::next(AI);
+    // If we have a phi, just remove it. We are going to replace all
+    // users with live on entry.
+    if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(AI))
+      UseOrDef->setDefiningAccess(LiveOnEntryDef.get());
+    else
+      Accesses->erase(AI);
+    AI = Next;
+  }
+}
+
+MemorySSA::MemorySSA(Function &Func)
+    : AA(nullptr), DT(nullptr), F(Func), LiveOnEntryDef(nullptr),
+      Walker(nullptr), NextID(0) {}
+
+MemorySSA::~MemorySSA() {}
+
+MemorySSA::AccessListType *MemorySSA::getOrCreateAccessList(BasicBlock *BB) {
+  auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr));
+  if (Res.second)
+    Res.first->second = make_unique<AccessListType>();
+  return Res.first->second.get();
+}
+
+MemorySSAWalker *MemorySSA::buildMemorySSA(AliasAnalysis *AA,
+                                           DominatorTree *DT) {
+  if (Walker)
+    return Walker;
+
+  assert(!this->AA && !this->DT &&
+         "MemorySSA without a walker already has AA or DT?");
+
+  auto *Result = new CachingMemorySSAWalker(this, AA, DT);
+  this->AA = AA;
+  this->DT = DT;
+
+  // We create an access to represent "live on entry", for things like
+  // arguments or users of globals, where the memory they use is defined before
+  // the beginning of the function. We do not actually insert it in to the IR.
+  // We do not define a live on exit for the immediate uses, and thus our
+  // semantics do *not* imply that something with no immediate uses can simply
+  // be removed.
+  BasicBlock &StartingPoint = F.getEntryBlock();
+  LiveOnEntryDef =
+      make_unique<MemoryDef>(nullptr, nullptr, &StartingPoint, NextID++);
+
+  // We maintain lists of memory accesses per-block, trading memory for time. We
+  // could just look up the memory access for every possible instruction in the
+  // stream.
+  SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
+
+  // Go through each block, figure out where defs occur, and chain together all
+  // the accesses.
+  for (BasicBlock &B : F) {
+    AccessListType *Accesses = nullptr;
+    for (Instruction &I : B) {
+      MemoryAccess *MA = createNewAccess(&I, true);
+      if (!MA)
+        continue;
+      if (isa<MemoryDef>(MA))
+        DefiningBlocks.insert(&B);
+      if (!Accesses)
+        Accesses = getOrCreateAccessList(&B);
+      Accesses->push_back(MA);
+    }
+  }
+
+  // Determine where our MemoryPhi's should go
+  IDFCalculator IDFs(*DT);
+  IDFs.setDefiningBlocks(DefiningBlocks);
+  SmallVector<BasicBlock *, 32> IDFBlocks;
+  IDFs.calculate(IDFBlocks);
+
+  // Now place MemoryPhi nodes.
+  for (auto &BB : IDFBlocks) {
+    // Insert phi node
+    AccessListType *Accesses = getOrCreateAccessList(BB);
+    MemoryPhi *Phi = new MemoryPhi(BB, NextID++);
+    InstructionToMemoryAccess.insert(std::make_pair(BB, Phi));
+    // Phi's always are placed at the front of the block.
+    Accesses->push_front(Phi);
+  }
+
+  // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
+  // filled in with all blocks.
+  SmallPtrSet<BasicBlock *, 16> Visited;
+  renamePass(DT->getRootNode(), LiveOnEntryDef.get(), Visited);
+
+  // Now optimize the MemoryUse's defining access to point to the nearest
+  // dominating clobbering def.
+  // This ensures that MemoryUse's that are killed by the same store are
+  // immediate users of that store, one of the invariants we guarantee.
+  for (auto DomNode : depth_first(DT)) {
+    BasicBlock *BB = DomNode->getBlock();
+    auto AI = PerBlockAccesses.find(BB);
+    if (AI == PerBlockAccesses.end())
+      continue;
+    AccessListType *Accesses = AI->second.get();
+    for (auto &MA : *Accesses) {
+      if (auto *MU = dyn_cast<MemoryUse>(&MA)) {
+        Instruction *Inst = MU->getMemoryInst();
+        MU->setDefiningAccess(Result->getClobberingMemoryAccess(Inst));
+      }
+    }
+  }
+
+  // Mark the uses in unreachable blocks as live on entry, so that they go
+  // somewhere.
+  for (auto &BB : F)
+    if (!Visited.count(&BB))
+      markUnreachableAsLiveOnEntry(&BB);
+
+  Walker = Result;
+  return Walker;
+}
+
+/// \brief Helper function to create new memory accesses
+MemoryAccess *MemorySSA::createNewAccess(Instruction *I, bool IgnoreNonMemory) {
+  // Find out what affect this instruction has on memory.
+  ModRefInfo ModRef = AA->getModRefInfo(I);
+  bool Def = bool(ModRef & MRI_Mod);
+  bool Use = bool(ModRef & MRI_Ref);
+
+  // It's possible for an instruction to not modify memory at all. During
+  // construction, we ignore them.
+  if (IgnoreNonMemory && !Def && !Use)
+    return nullptr;
+
+  assert((Def || Use) &&
+         "Trying to create a memory access with a non-memory instruction");
+
+  MemoryUseOrDef *MA;
+  if (Def)
+    MA = new MemoryDef(nullptr, I, I->getParent(), NextID++);
+  else
+    MA = new MemoryUse(nullptr, I, I->getParent());
+  InstructionToMemoryAccess.insert(std::make_pair(I, MA));
+  return MA;
+}
+
+MemoryAccess *MemorySSA::findDominatingDef(BasicBlock *UseBlock,
+                                           enum InsertionPlace Where) {
+  // Handle the initial case
+  if (Where == Beginning)
+    // The only thing that could define us at the beginning is a phi node
+    if (MemoryPhi *Phi = getMemoryAccess(UseBlock))
+      return Phi;
+
+  DomTreeNode *CurrNode = DT->getNode(UseBlock);
+  // Need to be defined by our dominator
+  if (Where == Beginning)
+    CurrNode = CurrNode->getIDom();
+  Where = End;
+  while (CurrNode) {
+    auto It = PerBlockAccesses.find(CurrNode->getBlock());
+    if (It != PerBlockAccesses.end()) {
+      auto &Accesses = It->second;
+      for (auto RAI = Accesses->rbegin(), RAE = Accesses->rend(); RAI != RAE;
+           ++RAI) {
+        if (isa<MemoryDef>(*RAI) || isa<MemoryPhi>(*RAI))
+          return &*RAI;
+      }
+    }
+    CurrNode = CurrNode->getIDom();
+  }
+  return LiveOnEntryDef.get();
+}
+
+/// \brief Returns true if \p Replacer dominates \p Replacee .
+bool MemorySSA::dominatesUse(const MemoryAccess *Replacer,
+                             const MemoryAccess *Replacee) const {
+  if (isa<MemoryUseOrDef>(Replacee))
+    return DT->dominates(Replacer->getBlock(), Replacee->getBlock());
+  const auto *MP = cast<MemoryPhi>(Replacee);
+  // For a phi node, the use occurs in the predecessor block of the phi node.
+  // Since we may occur multiple times in the phi node, we have to check each
+  // operand to ensure Replacer dominates each operand where Replacee occurs.
+  for (const auto &Arg : MP->operands())
+    if (Arg.second == Replacee)
+      if (!DT->dominates(Replacer->getBlock(), Arg.first))
+        return false;
+  return true;
+}
+
+void MemorySSA::print(raw_ostream &OS) const {
+  MemorySSAAnnotatedWriter Writer(this);
+  F.print(OS, &Writer);
+}
+
+void MemorySSA::dump() const {
+  MemorySSAAnnotatedWriter Writer(this);
+  F.print(dbgs(), &Writer);
+}
+
+/// \brief Verify the domination properties of MemorySSA by checking that each
+/// definition dominates all of its uses.
+void MemorySSA::verifyDomination(Function &F) {
+  for (BasicBlock &B : F) {
+    // Phi nodes are attached to basic blocks
+    if (MemoryPhi *MP = getMemoryAccess(&B)) {
+      for (MemoryAccess *U : MP->users()) {
+        BasicBlock *UseBlock;
+        // Phi operands are used on edges, we simulate the right domination by
+        // acting as if the use occurred at the end of the predecessor block.
+        if (MemoryPhi *P = dyn_cast<MemoryPhi>(U)) {
+          for (const auto &Arg : P->operands()) {
+            if (Arg.second == MP) {
+              UseBlock = Arg.first;
+              break;
+            }
+          }
+        } else {
+          UseBlock = U->getBlock();
+        }
+        assert(DT->dominates(MP->getBlock(), UseBlock) &&
+               "Memory PHI does not dominate it's uses");
+      }
+    }
+
+    for (Instruction &I : B) {
+      MemoryAccess *MD = dyn_cast_or_null<MemoryDef>(getMemoryAccess(&I));
+      if (!MD)
+        continue;
+
+      for (const auto &U : MD->users()) {
+        BasicBlock *UseBlock;
+        // Things are allowed to flow to phi nodes over their predecessor
+        // edge.
+        if (MemoryPhi *P = dyn_cast<MemoryPhi>(U)) {
+          for (const auto &Arg : P->operands()) {
+            if (Arg.second == MD) {
+              UseBlock = Arg.first;
+              break;
+            }
+          }
+        } else {
+          UseBlock = U->getBlock();
+        }
+        assert(DT->dominates(MD->getBlock(), UseBlock) &&
+               "Memory Def does not dominate it's uses");
+      }
+    }
+  }
+}
+
+/// \brief Verify the def-use lists in MemorySSA, by verifying that \p Use
+/// appears in the use list of \p Def.
+///
+/// llvm_unreachable is used instead of asserts because this may be called in
+/// a build without asserts. In that case, we don't want this to turn into a
+/// nop.
+void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) {
+  // The live on entry use may cause us to get a NULL def here
+  if (!Def) {
+    if (!isLiveOnEntryDef(Use))
+      llvm_unreachable("Null def but use not point to live on entry def");
+  } else if (!Def->hasUse(Use)) {
+    llvm_unreachable("Did not find use in def's use list");
+  }
+}
+
+/// \brief Verify the immediate use information, by walking all the memory
+/// accesses and verifying that, for each use, it appears in the
+/// appropriate def's use list
+void MemorySSA::verifyDefUses(Function &F) {
+  for (BasicBlock &B : F) {
+    // Phi nodes are attached to basic blocks
+    if (MemoryPhi *Phi = getMemoryAccess(&B))
+      for (const MemoryPhi::Operand &Op : Phi->operands())
+        verifyUseInDefs(Op.second, Phi);
+
+    for (Instruction &I : B) {
+      MemoryAccess *MA = getMemoryAccess(&I);
+      if (MA) {
+        if (auto *MP = dyn_cast<MemoryPhi>(MA)) {
+          for (unsigned I = 0, E = MP->getNumIncomingValues(); I != E; ++I)
+            verifyUseInDefs(MP->getIncomingValue(I), MP);
+        } else {
+          verifyUseInDefs(cast<MemoryUseOrDef>(MA)->getDefiningAccess(), MA);
+        }
+      }
+    }
+  }
+}
+
+MemoryAccess *MemorySSA::getMemoryAccess(const Value *I) const {
+  return InstructionToMemoryAccess.lookup(I);
+}
+
+MemoryPhi *MemorySSA::getMemoryAccess(const BasicBlock *BB) const {
+  return cast_or_null<MemoryPhi>(getMemoryAccess((const Value *)BB));
+}
+
+/// \brief Determine, for two memory accesses in the same block,
+/// whether \p Dominator dominates \p Dominatee.
+/// \returns True if \p Dominator dominates \p Dominatee.
+bool MemorySSA::locallyDominates(const MemoryAccess *Dominator,
+                                 const MemoryAccess *Dominatee) const {
+
+  assert((Dominator->getBlock() == Dominatee->getBlock()) &&
+         "Asking for local domination when accesses are in different blocks!");
+  // Get the access list for the block
+  const AccessListType *AccessList = getBlockAccesses(Dominator->getBlock());
+  AccessListType::const_reverse_iterator It(Dominator->getIterator());
+
+  // If we hit the beginning of the access list before we hit dominatee, we must
+  // dominate it
+  return std::none_of(It, AccessList->rend(),
+                      [&](const MemoryAccess &MA) { return &MA == Dominatee; });
+}
+
+const static char LiveOnEntryStr[] = "liveOnEntry";
+
+void MemoryDef::print(raw_ostream &OS) const {
+  MemoryAccess *UO = getDefiningAccess();
+
+  OS << getID() << " = MemoryDef(";
+  if (UO && UO->getID())
+    OS << UO->getID();
+  else
+    OS << LiveOnEntryStr;
+  OS << ')';
+}
+
+void MemoryPhi::print(raw_ostream &OS) const {
+  SmallVector<MemoryPhi::Operand, 8> Values(ops_begin(), ops_end());
+
+  // Try to give operands some sort of predictable ordering, so tests are more
+  // resilient.
+  std::sort(Values.begin(), Values.end(),
+            [](const MemoryPhi::Operand &P1, const MemoryPhi::Operand &P2) {
+              unsigned ID1 = P1.second->getID();
+              unsigned ID2 = P2.second->getID();
+              if (ID1 != ID2)
+                return ID1 < ID2;
+              return P1.first->getName() < P2.first->getName();
+            });
+
+  bool First = true;
+  OS << getID() << " = MemoryPhi(";
+  for (const MemoryPhi::Operand &Op : Values) {
+    BasicBlock *BB = Op.first;
+    MemoryAccess *MA = Op.second;
+    if (!First)
+      OS << ',';
+    else
+      First = false;
+
+    OS << '{';
+    if (BB->hasName())
+      OS << BB->getName();
+    else
+      BB->printAsOperand(OS, false);
+    OS << ',';
+    if (unsigned ID = MA->getID())
+      OS << ID;
+    else
+      OS << LiveOnEntryStr;
+    OS << '}';
+  }
+  OS << ')';
+}
+
+MemoryAccess::~MemoryAccess() {}
+
+void MemoryUse::print(raw_ostream &OS) const {
+  MemoryAccess *UO = getDefiningAccess();
+  OS << "MemoryUse(";
+  if (UO && UO->getID())
+    OS << UO->getID();
+  else
+    OS << LiveOnEntryStr;
+  OS << ')';
+}
+
+void MemoryAccess::dump() const {
+  print(dbgs());
+  dbgs() << "\n";
+}
+
+char MemorySSAPrinterPass::ID = 0;
+
+MemorySSAPrinterPass::MemorySSAPrinterPass() : FunctionPass(ID) {
+  initializeMemorySSAPrinterPassPass(*PassRegistry::getPassRegistry());
+}
+
+void MemorySSAPrinterPass::releaseMemory() {
+  // Subtlety: Be sure to delete the walker before MSSA, because the walker's
+  // dtor may try to access MemorySSA.
+  Walker.reset();
+  MSSA.reset();
+}
+
+void MemorySSAPrinterPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<AAResultsWrapperPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addPreserved<DominatorTreeWrapperPass>();
+  AU.addPreserved<GlobalsAAWrapperPass>();
+}
+
+bool MemorySSAPrinterPass::doInitialization(Module &M) {
+  VerifyMemorySSA =
+      M.getContext()
+          .template getOption<bool, MemorySSAPrinterPass,
+                              &MemorySSAPrinterPass::VerifyMemorySSA>();
+  return false;
+}
+
+void MemorySSAPrinterPass::registerOptions() {
+  OptionRegistry::registerOption<bool, MemorySSAPrinterPass,
+                                 &MemorySSAPrinterPass::VerifyMemorySSA>(
+      "verify-memoryssa", "Run the Memory SSA verifier", false);
+}
+
+void MemorySSAPrinterPass::print(raw_ostream &OS, const Module *M) const {
+  MSSA->print(OS);
+}
+
+bool MemorySSAPrinterPass::runOnFunction(Function &F) {
+  this->F = &F;
+  MSSA.reset(new MemorySSA(F));
+  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  Walker.reset(MSSA->buildMemorySSA(AA, DT));
+
+  if (VerifyMemorySSA) {
+    MSSA->verifyDefUses(F);
+    MSSA->verifyDomination(F);
+  }
+
+  return false;
+}
+
+char MemorySSALazy::ID = 0;
+
+MemorySSALazy::MemorySSALazy() : FunctionPass(ID) {
+  initializeMemorySSALazyPass(*PassRegistry::getPassRegistry());
+}
+
+void MemorySSALazy::releaseMemory() { MSSA.reset(); }
+
+bool MemorySSALazy::runOnFunction(Function &F) {
+  MSSA.reset(new MemorySSA(F));
+  return false;
+}
+
+MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
+
+CachingMemorySSAWalker::CachingMemorySSAWalker(MemorySSA *M, AliasAnalysis *A,
+                                               DominatorTree *D)
+    : MemorySSAWalker(M), AA(A), DT(D) {}
+
+CachingMemorySSAWalker::~CachingMemorySSAWalker() {}
+
+struct CachingMemorySSAWalker::UpwardsMemoryQuery {
+  // True if we saw a phi whose predecessor was a backedge
+  bool SawBackedgePhi;
+  // True if our original query started off as a call
+  bool IsCall;
+  // The pointer location we started the query with. This will be empty if
+  // IsCall is true.
+  MemoryLocation StartingLoc;
+  // This is the instruction we were querying about.
+  const Instruction *Inst;
+  // Set of visited Instructions for this query.
+  DenseSet<MemoryAccessPair> Visited;
+  // Set of visited call accesses for this query. This is separated out because
+  // you can always cache and lookup the result of call queries (IE when IsCall
+  // == true) for every call in the chain. The calls have no AA location
+  // associated with them with them, and thus, no context dependence.
+  SmallPtrSet<const MemoryAccess *, 32> VisitedCalls;
+  // The MemoryAccess we actually got called with, used to test local domination
+  const MemoryAccess *OriginalAccess;
+  // The Datalayout for the module we started in
+  const DataLayout *DL;
+
+  UpwardsMemoryQuery()
+      : SawBackedgePhi(false), IsCall(false), Inst(nullptr),
+        OriginalAccess(nullptr), DL(nullptr) {}
+};
+
+void CachingMemorySSAWalker::doCacheRemove(const MemoryAccess *M,
+                                           const UpwardsMemoryQuery &Q,
+                                           const MemoryLocation &Loc) {
+  if (Q.IsCall)
+    CachedUpwardsClobberingCall.erase(M);
+  else
+    CachedUpwardsClobberingAccess.erase({M, Loc});
+}
+
+void CachingMemorySSAWalker::doCacheInsert(const MemoryAccess *M,
+                                           MemoryAccess *Result,
+                                           const UpwardsMemoryQuery &Q,
+                                           const MemoryLocation &Loc) {
+  ++NumClobberCacheInserts;
+  if (Q.IsCall)
+    CachedUpwardsClobberingCall[M] = Result;
+  else
+    CachedUpwardsClobberingAccess[{M, Loc}] = Result;
+}
+
+MemoryAccess *CachingMemorySSAWalker::doCacheLookup(const MemoryAccess *M,
+                                                    const UpwardsMemoryQuery &Q,
+                                                    const MemoryLocation &Loc) {
+  ++NumClobberCacheLookups;
+  MemoryAccess *Result = nullptr;
+
+  if (Q.IsCall)
+    Result = CachedUpwardsClobberingCall.lookup(M);
+  else
+    Result = CachedUpwardsClobberingAccess.lookup({M, Loc});
+
+  if (Result)
+    ++NumClobberCacheHits;
+  return Result;
+}
+
+/// \brief Return true if \p QueryInst could possibly have a Mod result with \p
+/// DefInst.
+static bool possiblyAffectedBy(const Instruction *QueryInst,
+                               const Instruction *DefInst) {
+  if (isa<LoadInst>(DefInst) && isa<LoadInst>(QueryInst)) {
+    const auto *DefLI = cast<LoadInst>(DefInst);
+    const auto *QueryLI = cast<LoadInst>(QueryInst);
+    // A non-volatile load can't be clobbered by a volatile one unless the
+    // volatile one is ordered.
+    if (!QueryLI->isVolatile() && DefLI->isVolatile())
+      return DefLI->getOrdering() > Unordered;
+  }
+  return true;
+}
+
+bool CachingMemorySSAWalker::instructionClobbersQuery(
+    const MemoryDef *MD, UpwardsMemoryQuery &Q,
+    const MemoryLocation &Loc) const {
+  Instruction *DefMemoryInst = MD->getMemoryInst();
+  assert(DefMemoryInst && "Defining instruction not actually an instruction");
+
+  if (!Q.IsCall) {
+    return possiblyAffectedBy(Q.Inst, DefMemoryInst) &&
+           (AA->getModRefInfo(DefMemoryInst, Loc) & MRI_Mod);
+  }
+
+  // If this is a call, mark it for caching
+  if (ImmutableCallSite(DefMemoryInst))
+    Q.VisitedCalls.insert(MD);
+  ModRefInfo I = AA->getModRefInfo(DefMemoryInst, ImmutableCallSite(Q.Inst));
+  return I != MRI_NoModRef;
+}
+
+MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk(
+    MemoryAccess *StartingAccess, const MemoryLocation &Loc,
+    UpwardsMemoryQuery &Q, bool FollowingBackedge) {
+  MemoryAccess *ModifyingAccess = nullptr;
+
+  auto DFI = df_begin(StartingAccess);
+  for (auto DFE = df_end(StartingAccess); DFI != DFE;) {
+    MemoryAccess *CurrAccess = *DFI;
+    if (MSSA->isLiveOnEntryDef(CurrAccess))
+      return {CurrAccess, Loc};
+    if (auto CacheResult = doCacheLookup(CurrAccess, Q, Loc))
+      return {CacheResult, Loc};
+    // If this is a MemoryDef, check whether it clobbers our current query.
+    if (auto *MD = dyn_cast<MemoryDef>(CurrAccess)) {
+      // If we hit the top, stop following this path.
+      // While we can do lookups, we can't sanely do inserts here unless we were
+      // to track everything we saw along the way, since we don't know where we
+      // will stop.
+      if (instructionClobbersQuery(MD, Q, Loc)) {
+        ModifyingAccess = CurrAccess;
+        break;
+      }
+    }
+
+    // We need to know whether it is a phi so we can track backedges.
+    // Otherwise, walk all upward defs.
+    if (!isa<MemoryPhi>(CurrAccess)) {
+      ++DFI;
+      continue;
+    }
+
+    // Recurse on PHI nodes, since we need to change locations.
+    // TODO: Allow graphtraits on pairs, which would turn this whole function
+    // into a normal single depth first walk.
+    MemoryAccess *FirstDef = nullptr;
+    DFI = DFI.skipChildren();
+    const MemoryAccessPair PHIPair(CurrAccess, Loc);
+    bool VisitedOnlyOne = true;
+    for (auto MPI = upward_defs_begin(PHIPair), MPE = upward_defs_end();
+         MPI != MPE; ++MPI) {
+      // Don't follow this path again if we've followed it once
+      if (!Q.Visited.insert(*MPI).second)
+        continue;
+
+      bool Backedge =
+          !FollowingBackedge &&
+          DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock());
+
+      MemoryAccessPair CurrentPair =
+          UpwardsDFSWalk(MPI->first, MPI->second, Q, Backedge);
+      // All the phi arguments should reach the same point if we can bypass
+      // this phi. The alternative is that they hit this phi node, which
+      // means we can skip this argument.
+      if (FirstDef && CurrentPair.first != PHIPair.first &&
+          CurrentPair.first != FirstDef) {
+        ModifyingAccess = CurrAccess;
+        break;
+      }
+
+      if (!FirstDef)
+        FirstDef = CurrentPair.first;
+      else
+        VisitedOnlyOne = false;
+    }
+
+    // The above loop determines if all arguments of the phi node reach the
+    // same place. However we skip arguments that are cyclically dependent
+    // only on the value of this phi node. This means in some cases, we may
+    // only visit one argument of the phi node, and the above loop will
+    // happily say that all the arguments are the same. However, in that case,
+    // we still can't walk past the phi node, because that argument still
+    // kills the access unless we hit the top of the function when walking
+    // that argument.
+    if (VisitedOnlyOne && FirstDef && !MSSA->isLiveOnEntryDef(FirstDef))
+      ModifyingAccess = CurrAccess;
+  }
+
+  if (!ModifyingAccess)
+    return {MSSA->getLiveOnEntryDef(), Q.StartingLoc};
+
+  const BasicBlock *OriginalBlock = Q.OriginalAccess->getBlock();
+  unsigned N = DFI.getPathLength();
+  MemoryAccess *FinalAccess = ModifyingAccess;
+  for (; N != 0; --N) {
+    ModifyingAccess = DFI.getPath(N - 1);
+    BasicBlock *CurrBlock = ModifyingAccess->getBlock();
+    if (!FollowingBackedge)
+      doCacheInsert(ModifyingAccess, FinalAccess, Q, Loc);
+    if (DT->dominates(CurrBlock, OriginalBlock) &&
+        (CurrBlock != OriginalBlock || !FollowingBackedge ||
+         MSSA->locallyDominates(ModifyingAccess, Q.OriginalAccess)))
+      break;
+  }
+
+  // Cache everything else on the way back. The caller should cache
+  // Q.OriginalAccess for us.
+  for (; N != 0; --N) {
+    MemoryAccess *CacheAccess = DFI.getPath(N - 1);
+    doCacheInsert(CacheAccess, ModifyingAccess, Q, Loc);
+  }
+  assert(Q.Visited.size() < 1000 && "Visited too much");
+
+  return {ModifyingAccess, Loc};
+}
+
+/// \brief Walk the use-def chains starting at \p MA and find
+/// the MemoryAccess that actually clobbers Loc.
+///
+/// \returns our clobbering memory access
+
+MemoryAccess *
+CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
+                                                  UpwardsMemoryQuery &Q) {
+  return UpwardsDFSWalk(StartingAccess, Q.StartingLoc, Q, false).first;
+}
+
+MemoryAccess *
+CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
+                                                  MemoryLocation &Loc) {
+  if (isa<MemoryPhi>(StartingAccess))
+    return StartingAccess;
+
+  auto *StartingUseOrDef = cast<MemoryUseOrDef>(StartingAccess);
+  if (MSSA->isLiveOnEntryDef(StartingUseOrDef))
+    return StartingUseOrDef;
+
+  Instruction *I = StartingUseOrDef->getMemoryInst();
+
+  // Conservatively, fences are always clobbers, so don't perform the walk if we
+  // hit a fence.
+  if (isa<FenceInst>(I))
+    return StartingUseOrDef;
+
+  UpwardsMemoryQuery Q;
+  Q.OriginalAccess = StartingUseOrDef;
+  Q.StartingLoc = Loc;
+  Q.Inst = StartingUseOrDef->getMemoryInst();
+  Q.IsCall = false;
+  Q.DL = &Q.Inst->getParent()->getModule()->getDataLayout();
+
+  if (auto CacheResult = doCacheLookup(StartingUseOrDef, Q, Q.StartingLoc))
+    return CacheResult;
+
+  // Unlike the other function, do not walk to the def of a def, because we are
+  // handed something we already believe is the clobbering access.
+  MemoryAccess *DefiningAccess = isa<MemoryUse>(StartingUseOrDef)
+                                     ? StartingUseOrDef->getDefiningAccess()
+                                     : StartingUseOrDef;
+
+  MemoryAccess *Clobber = getClobberingMemoryAccess(DefiningAccess, Q);
+  doCacheInsert(Q.OriginalAccess, Clobber, Q, Q.StartingLoc);
+  DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *StartingUseOrDef << "\n");
+  DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *Clobber << "\n");
+  return Clobber;
+}
+
+MemoryAccess *
+CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
+  // There should be no way to lookup an instruction and get a phi as the
+  // access, since we only map BB's to PHI's. So, this must be a use or def.
+  auto *StartingAccess = cast<MemoryUseOrDef>(MSSA->getMemoryAccess(I));
+
+  // We can't sanely do anything with a FenceInst, they conservatively
+  // clobber all memory, and have no locations to get pointers from to
+  // try to disambiguate
+  if (isa<FenceInst>(I))
+    return StartingAccess;
+
+  UpwardsMemoryQuery Q;
+  Q.OriginalAccess = StartingAccess;
+  Q.IsCall = bool(ImmutableCallSite(I));
+  if (!Q.IsCall)
+    Q.StartingLoc = MemoryLocation::get(I);
+  Q.Inst = I;
+  Q.DL = &Q.Inst->getParent()->getModule()->getDataLayout();
+  if (auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc))
+    return CacheResult;
+
+  // Short circuit invariant loads
+  if (const auto *LI = dyn_cast<LoadInst>(I))
+    if (LI->getMetadata(LLVMContext::MD_invariant_load)) {
+      doCacheInsert(StartingAccess, MSSA->getLiveOnEntryDef(), Q,
+                    Q.StartingLoc);
+      return MSSA->getLiveOnEntryDef();
+    }
+
+  // Start with the thing we already think clobbers this location
+  MemoryAccess *DefiningAccess = StartingAccess->getDefiningAccess();
+
+  // At this point, DefiningAccess may be the live on entry def.
+  // If it is, we will not get a better result.
+  if (MSSA->isLiveOnEntryDef(DefiningAccess))
+    return DefiningAccess;
+
+  MemoryAccess *Result = getClobberingMemoryAccess(DefiningAccess, Q);
+  doCacheInsert(Q.OriginalAccess, Result, Q, Q.StartingLoc);
+  if (Q.IsCall)
+    for (const MemoryAccess *MA : Q.VisitedCalls)
+      doCacheInsert(MA, Result, Q, Q.StartingLoc);
+
+  DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *DefiningAccess << "\n");
+  DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *Result << "\n");
+
+  return Result;
+}
+
+MemoryAccess *
+DoNothingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
+  MemoryAccess *MA = MSSA->getMemoryAccess(I);
+  if (auto *Use = dyn_cast<MemoryUseOrDef>(MA))
+    return Use->getDefiningAccess();
+  return MA;
+}
+
+MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
+    MemoryAccess *StartingAccess, MemoryLocation &) {
+  if (auto *Use = dyn_cast<MemoryUseOrDef>(StartingAccess))
+    return Use->getDefiningAccess();
+  return StartingAccess;
+}
+}

test/Transforms/Util/MemorySSA/atomic-clobber.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Ensures that atomic loads count as MemoryDefs
+
+define i32 @foo(i32* %a, i32* %b) {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 4
+  store i32 4, i32* %a, align 4
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: %1 = load atomic i32
+  %1 = load atomic i32, i32* %b acquire, align 4
+; CHECK: MemoryUse(2)
+; CHECK-NEXT: %2 = load i32
+  %2 = load i32, i32* %a, align 4
+  %3 = add i32 %1, %2
+  ret i32 %3
+}

test/Transforms/Util/MemorySSA/cyclicphi.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+
+%struct.hoge = type { i32, %struct.widget }
+%struct.widget = type { i64 }
+
+define hidden void @quux(%struct.hoge *%f) align 2 {
+  %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
+  %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
+  %tmp25 = bitcast %struct.widget* %tmp24 to i64**
+  br label %bb26
+
+bb26:                                             ; preds = %bb77, %0
+; CHECK:  3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
+; CHECK-NEXT:   br i1 undef, label %bb68, label %bb77
+  br i1 undef, label %bb68, label %bb77
+
+bb68:                                             ; preds = %bb26
+; CHECK:  MemoryUse(liveOnEntry)
+; CHECK-NEXT:   %tmp69 = load i64, i64* null, align 8
+  %tmp69 = load i64, i64* null, align 8
+; CHECK:  1 = MemoryDef(3)
+; CHECK-NEXT:   store i64 %tmp69, i64* %tmp, align 8
+  store i64 %tmp69, i64* %tmp, align 8
+  br label %bb77
+
+bb77:                                             ; preds = %bb68, %bb26
+; CHECK:  2 = MemoryPhi({bb68,1},{bb26,3})
+; CHECK:  MemoryUse(2)
+; CHECK-NEXT:   %tmp78 = load i64*, i64** %tmp25, align 8
+  %tmp78 = load i64*, i64** %tmp25, align 8
+  %tmp79 = getelementptr inbounds i64, i64* %tmp78, i64 undef
+  br label %bb26
+}

test/Transforms/Util/MemorySSA/function-clobber.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Ensuring that external functions without attributes are MemoryDefs
+
+@g = external global i32
+declare void @modifyG()
+
+define i32 @foo() {
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %1 = load i32
+  %1 = load i32, i32* @g
+
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 4
+  store i32 4, i32* @g, align 4
+
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: call void @modifyG()
+  call void @modifyG()
+
+; CHECK: MemoryUse(2)
+; CHECK-NEXT: %2 = load i32
+  %2 = load i32, i32* @g
+  %3 = add i32 %2, %1
+  ret i32 %3
+}

test/Transforms/Util/MemorySSA/function-mem-attrs.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Test that various function attributes give us sane results.
+
+@g = external global i32
+
+declare void @readonlyFunction() readonly
+declare void @noattrsFunction()
+
+define void @readonlyAttr() {
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 0
+  store i32 0, i32* @g, align 4
+
+  %1 = alloca i32, align 4
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i32 0
+  store i32 0, i32* %1, align 4
+
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: call void @readonlyFunction()
+  call void @readonlyFunction()
+
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: call void @noattrsFunction() #
+; Assume that #N is readonly
+  call void @noattrsFunction() readonly
+
+  ; Sanity check that noattrsFunction is otherwise a MemoryDef
+; CHECK: 3 = MemoryDef(2)
+; CHECK-NEXT: call void @noattrsFunction()
+  call void @noattrsFunction()
+  ret void
+}
+
+declare void @argMemOnly(i32*) argmemonly
+
+define void @inaccessableOnlyAttr() {
+  %1 = alloca i32, align 4
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 0
+  store i32 0, i32* %1, align 4
+
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store i32 0
+  store i32 0, i32* @g, align 4
+
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: call void @argMemOnly(i32* %1) #
+; Assume that #N is readonly
+  call void @argMemOnly(i32* %1) readonly
+
+; CHECK: 3 = MemoryDef(2)
+; CHECK-NEXT: call void @argMemOnly(i32* %1)
+  call void @argMemOnly(i32* %1)
+
+  ret void
+}

test/Transforms/Util/MemorySSA/load-invariant.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Invariant loads should be considered live on entry, because, once the
+; location is known to be dereferenceable, the value can never change.
+
+@g = external global i32
+
+define i32 @foo() {
+  %1 = alloca i32, align 4
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 0
+  store i32 0, i32* %1, align 4
+  %2 = alloca i32, align 4
+
+; CHECK: MemoryUse(1)
+; CHECK-NEXT: %3 = load i32
+  %3 = load i32, i32* %1, align 4
+; CHECK: MemoryUse(liveOnEntry)
+; CHECK-NEXT: %4 = load i32
+  %4 = load i32, i32* %2, align 4, !invariant.load !0
+  %5 = add i32 %3, %4
+  ret i32 %5
+}
+
+!0 = !{}

test/Transforms/Util/MemorySSA/many-dom-backedge.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; many-dom.ll, with an added back-edge back into the switch.
+; Because people love their gotos.
+
+declare i1 @getBool() readnone
+
+define i32 @foo(i32* %p) {
+entry:
+  br label %loopbegin
+
+loopbegin:
+; CHECK: 9 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6})
+; CHECK-NEXT: %n =
+  %n = phi i32 [ 0, %entry ], [ %1, %sw.epilog ]
+  %m = alloca i32, align 4
+  switch i32 %n, label %sw.default [
+    i32 0, label %sw.bb
+    i32 1, label %sw.bb1
+    i32 2, label %sw.bb2
+    i32 3, label %sw.bb3
+  ]
+
+sw.bb:
+; CHECK: 1 = MemoryDef(9)
+; CHECK-NEXT: store i32 1
+  store i32 1, i32* %m, align 4
+  br label %sw.epilog
+
+sw.bb1:
+; CHECK: 2 = MemoryDef(9)
+; CHECK-NEXT: store i32 2
+  store i32 2, i32* %m, align 4
+  br label %sw.epilog
+
+sw.bb2:
+; CHECK: 3 = MemoryDef(9)
+; CHECK-NEXT: store i32 3
+  store i32 3, i32* %m, align 4
+  br label %sw.epilog
+
+sw.bb3:
+; CHECK: 10 = MemoryPhi({sw.almostexit,6},{loopbegin,9})
+; CHECK: 4 = MemoryDef(10)
+; CHECK-NEXT: store i32 4
+  store i32 4, i32* %m, align 4
+  br label %sw.epilog
+
+sw.default:
+; CHECK: 5 = MemoryDef(9)
+; CHECK-NEXT: store i32 5
+  store i32 5, i32* %m, align 4
+  br label %sw.epilog
+
+sw.epilog:
+; CHECK: 8 = MemoryPhi({sw.bb,1},{sw.bb1,2},{sw.bb2,3},{sw.bb3,4},{sw.default,5})
+; CHECK-NEXT: MemoryUse(8)
+; CHECK-NEXT: %0 =
+  %0 = load i32, i32* %m, align 4
+; CHECK: 6 = MemoryDef(8)
+; CHECK-NEXT: %1 =
+  %1 = load volatile i32, i32* %p, align 4
+  %2 = icmp eq i32 %0, %1
+  br i1 %2, label %sw.almostexit, label %loopbegin
+
+sw.almostexit:
+  %3 = icmp eq i32 0, %1
+  br i1 %3, label %exit, label %sw.bb3
+
+exit:
+; CHECK: 7 = MemoryDef(6)
+; CHECK-NEXT: %4 = load volatile i32
+  %4 = load volatile i32, i32* %p, align 4
+  %5 = add i32 %4, %1
+  ret i32 %5
+}

test/Transforms/Util/MemorySSA/many-doms.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Testing many dominators, specifically from a switch statement in C.
+
+declare i1 @getBool() readnone
+
+define i32 @foo(i32* %p) {
+entry:
+  br label %loopbegin
+
+loopbegin:
+; CHECK: 8 = MemoryPhi({entry,liveOnEntry},{sw.epilog,6})
+; CHECK-NEXT: %n =
+  %n = phi i32 [ 0, %entry ], [ %1, %sw.epilog ]
+  %m = alloca i32, align 4
+  switch i32 %n, label %sw.default [
+    i32 0, label %sw.bb
+    i32 1, label %sw.bb1
+    i32 2, label %sw.bb2
+    i32 3, label %sw.bb3
+  ]
+
+sw.bb:
+; CHECK: 1 = MemoryDef(8)
+; CHECK-NEXT: store i32 1
+  store i32 1, i32* %m, align 4
+  br label %sw.epilog
+
+sw.bb1:
+; CHECK: 2 = MemoryDef(8)
+; CHECK-NEXT: store i32 2
+  store i32 2, i32* %m, align 4
+  br label %sw.epilog
+
+sw.bb2:
+; CHECK: 3 = MemoryDef(8)
+; CHECK-NEXT: store i32 3
+  store i32 3, i32* %m, align 4
+  br label %sw.epilog
+
+sw.bb3:
+; CHECK: 4 = MemoryDef(8)
+; CHECK-NEXT: store i32 4
+  store i32 4, i32* %m, align 4
+  br label %sw.epilog
+
+sw.default:
+; CHECK: 5 = MemoryDef(8)
+; CHECK-NEXT: store i32 5
+  store i32 5, i32* %m, align 4
+  br label %sw.epilog
+
+sw.epilog:
+; CHECK: 7 = MemoryPhi({sw.bb,1},{sw.bb1,2},{sw.bb2,3},{sw.bb3,4},{sw.default,5})
+; CHECK-NEXT: MemoryUse(7)
+; CHECK-NEXT: %0 =
+  %0 = load i32, i32* %m, align 4
+; CHECK: 6 = MemoryDef(7)
+; CHECK-NEXT: %1 =
+  %1 = load volatile i32, i32* %p, align 4
+  %2 = icmp eq i32 %0, %1
+  br i1 %2, label %exit, label %loopbegin
+
+exit:
+  ret i32 %1
+}

test/Transforms/Util/MemorySSA/multi-edges.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Makes sure we have a sane model if both successors of some block is the same
+; block.
+
+define i32 @foo(i1 %a) {
+entry:
+  %0 = alloca i32, align 4
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i32 4
+  store i32 4, i32* %0
+  br i1 %a, label %Loop.Body, label %Loop.End
+
+Loop.Body:
+; CHECK: 4 = MemoryPhi({entry,1},{Loop.End,3})
+; CHECK-NEXT: 2 = MemoryDef(4)
+; CHECK-NEXT: store i32 5
+  store i32 5, i32* %0, align 4
+  br i1 %a, label %Loop.End, label %Loop.End ; WhyDoWeEvenHaveThatLever.gif
+
+Loop.End:
+; CHECK: 3 = MemoryPhi({entry,1},{Loop.Body,2},{Loop.Body,2})
+; CHECK-NEXT: MemoryUse(3)
+; CHECK-NEXT: %1 = load
+  %1 = load i32, i32* %0, align 4
+  %2 = icmp eq i32 5, %1
+  br i1 %2, label %Ret, label %Loop.Body
+
+Ret:
+  ret i32 %1
+}

test/Transforms/Util/MemorySSA/multiple-backedges-hal.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+
+; hfinkel's case
+; [entry]
+;  |
+; .....
+; (clobbering access - b)
+;  |
+; ....  ________________________________
+;  \   /                               |
+;   (x)                                |
+;  ......                              |
+;    |                                 |
+;    |    ______________________       |
+;     \   /                    |       |
+; (starting access)            |       |
+;     ...                      |       |
+; (clobbering access - a)      |       |
+;    ...                       |       |
+;    | |                       |       |
+;    | |_______________________|       |
+;    |                                 |
+;    |_________________________________|
+;
+; More specifically, one access, with multiple clobbering accesses. One of
+; which strictly dominates the access, the other of which has a backedge
+
+; readnone so we don't have a 1:1 mapping of MemorySSA edges to Instructions.
+declare void @doThingWithoutReading() readnone
+declare i8 @getValue() readnone
+declare i1 @getBool() readnone
+
+define hidden void @testcase(i8* %Arg) {
+Entry:
+  call void @doThingWithoutReading()
+  %Val.Entry = call i8 @getValue()
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store i8 %Val.Entry
+  store i8 %Val.Entry, i8* %Arg
+  call void @doThingWithoutReading()
+  br label %OuterLoop
+
+OuterLoop:
+; CHECK: 5 = MemoryPhi({Entry,1},{InnerLoop.Tail,3})
+; CHECK-NEXT: %Val.Outer =
+  %Val.Outer = call i8 @getValue()
+; CHECK: 2 = MemoryDef(5)
+; CHECK-NEXT: store i8 %Val.Outer
+  store i8 %Val.Outer, i8* %Arg
+  call void @doThingWithoutReading()
+  br label %InnerLoop
+
+InnerLoop:
+; CHECK: 4 = MemoryPhi({OuterLoop,2},{InnerLoop,3})
+; CHECK-NEXT: ; MemoryUse(4)
+; CHECK-NEXT: %StartingAccess = load
+  %StartingAccess = load i8, i8* %Arg, align 4
+  %Val.Inner = call i8 @getValue()
+; CHECK: 3 = MemoryDef(4)
+; CHECK-NEXT: store i8 %Val.Inner
+  store i8 %Val.Inner, i8* %Arg
+  call void @doThingWithoutReading()
+  %KeepGoing = call i1 @getBool()
+  br i1 %KeepGoing, label %InnerLoop.Tail, label %InnerLoop
+
+InnerLoop.Tail:
+  %KeepGoing.Tail = call i1 @getBool()
+  br i1 %KeepGoing.Tail, label %End, label %OuterLoop
+
+End:
+  ret void
+}

test/Transforms/Util/MemorySSA/no-disconnected.ll

+; RUN: opt -basicaa -print-memoryssa -analyze -verify-memoryssa < %s 2>&1 | FileCheck %s
+;
+; This test ensures we don't end up with multiple reaching defs for a single
+; use/phi edge If we were to optimize defs, we would end up with 2=
+; MemoryDef(liveOnEntry) and 4 = MemoryDef(liveOnEntry) Both would mean both
+; 1,2, and 3,4 would reach the phi node.  Because the phi node can only have one
+; entry on each edge, it would choose 2, 4 and disconnect 1 and 3 completely
+; from the SSA graph, even though they are not dead
+
+define void @sink_store(i32 %index, i32* %foo, i32* %bar) {
+entry:
+  %cmp = trunc i32 %index to i1
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   store i32 %index, i32* %foo, align 4
+  store i32 %index, i32* %foo, align 4
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT:   store i32 %index, i32* %bar, align 4
+  store i32 %index, i32* %bar, align 4
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+; CHECK: 3 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   store i32 %index, i32* %foo, align 4
+  store i32 %index, i32* %foo, align 4
+; CHECK: 4 = MemoryDef(3)
+; CHECK-NEXT:   store i32 %index, i32* %bar, align 4
+  store i32 %index, i32* %bar, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK: 5 = MemoryPhi({if.then,2},{if.else,4})
+; CHECK: MemoryUse(5)
+; CHECK-NEXT:   %c = load i32, i32* %foo
+  %c = load i32, i32* %foo
+; CHECK: MemoryUse(5)
+; CHECK-NEXT:   %d = load i32, i32* %bar
+  %d = load i32, i32* %bar
+  ret void
+}

test/Transforms/Util/MemorySSA/optimize-use.ll

+; RUN: opt -basicaa -print-memoryssa -analyze -verify-memoryssa < %s 2>&1 | FileCheck %s
+
+; Function Attrs: ssp uwtable
+define i32 @main() {
+entry:
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   %call = call noalias i8* @_Znwm(i64 4)
+  %call = call noalias i8* @_Znwm(i64 4)
+  %0 = bitcast i8* %call to i32*
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT:   %call1 = call noalias i8* @_Znwm(i64 4)
+  %call1 = call noalias i8* @_Znwm(i64 4)
+  %1 = bitcast i8* %call1 to i32*
+; CHECK: 3 = MemoryDef(2)
+; CHECK-NEXT:   store i32 5, i32* %0, align 4
+  store i32 5, i32* %0, align 4
+; CHECK: 4 = MemoryDef(3)
+; CHECK-NEXT:   store i32 7, i32* %1, align 4
+  store i32 7, i32* %1, align 4
+; CHECK: MemoryUse(3)
+; CHECK-NEXT:   %2 = load i32, i32* %0, align 4
+  %2 = load i32, i32* %0, align 4
+; CHECK: MemoryUse(4)
+; CHECK-NEXT:   %3 = load i32, i32* %1, align 4
+  %3 = load i32, i32* %1, align 4
+; CHECK: MemoryUse(3)
+; CHECK-NEXT:   %4 = load i32, i32* %0, align 4
+  %4 = load i32, i32* %0, align 4
+; CHECK: MemoryUse(4)
+; CHECK-NEXT:   %5 = load i32, i32* %1, align 4
+  %5 = load i32, i32* %1, align 4
+  %add = add nsw i32 %3, %5
+  ret i32 %add
+}
+
+declare noalias i8* @_Znwm(i64)

test/Transforms/Util/MemorySSA/volatile-clobber.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1 | FileCheck %s
+;
+; Ensures that volatile stores/loads count as MemoryDefs
+
+define i32 @foo() {
+  %1 = alloca i32, align 4
+; CHECK: 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT: store volatile i32 4
+  store volatile i32 4, i32* %1, align 4
+; CHECK: 2 = MemoryDef(1)
+; CHECK-NEXT: store volatile i32 8
+  store volatile i32 8, i32* %1, align 4
+; CHECK: 3 = MemoryDef(2)
+; CHECK-NEXT: %2 = load volatile i32
+  %2 = load volatile i32, i32* %1, align 4
+; CHECK: 4 = MemoryDef(3)
+; CHECK-NEXT: %3 = load volatile i32
+  %3 = load volatile i32, i32* %1, align 4
+  %4 = add i32 %3, %2
+  ret i32 %4
+}