Index: include/llvm/Analysis/LoopAnalysisManager.h
===================================================================
--- include/llvm/Analysis/LoopAnalysisManager.h
+++ include/llvm/Analysis/LoopAnalysisManager.h
@@ -37,6 +37,7 @@
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
@@ -58,6 +59,7 @@
   ScalarEvolution &SE;
   TargetLibraryInfo &TLI;
   TargetTransformInfo &TTI;
+  MemorySSA &MSSA;
 };
 
 /// Extern template declaration for the analysis set for this IR unit.
Index: include/llvm/Analysis/MemorySSAAliasSets.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/MemorySSAAliasSets.h
@@ -0,0 +1,315 @@
+//===-- MemorySSAAliasSets.h - Alias sets using MemorySSA -----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This a a helper class that creates alias sets using MemorySSA, each
+// set being marked with properties that enablei/disable promotion.
+// It is used for promotion in the Loop Invariant Code Motion Pass.
+// It also stores insertion points into MemorySSA for a particular loop.
+// These need to be reset if the sets are reused.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_ANALYSIS_MEMORYSSA_ALIASSETS_H
+#define LLVM_ANALYSIS_MEMORYSSA_ALIASSETS_H
+
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+namespace llvm {
+class MemorySSAAliasSets {
+ public:
+  MemorySSA *MSSA;
+  MemorySSAUpdater *MSSAUpdater;
+
+ private:
+  Loop *L;
+  LoopInfo *LI;
+  AliasAnalysis *AA;
+  DominatorTree *DT;
+  SmallVector<MemoryAccess *, 4> MSSAInsertPts;
+
+  class SingleMustAliasVec {
+    SmallPtrSet<Value*, 4> Vec;
+    MemoryLocation Loc;
+   public:
+    // CanNeverPromote trumps everything else
+    // Set is either may-alias, has a volatile store or aliases an instruction
+    // witout a MemoryLocation.
+    bool CanNeverPromote=false;
+    bool LoopInvariantAccess=false;
+    bool HasAGoodStore=false;
+    SingleMustAliasVec (MemoryLocation loc) : Loc(loc), CanNeverPromote(false) {
+      Vec.insert(const_cast<Value*>(Loc.Ptr));
+    }
+    void addMemoryLocation(Optional<MemoryLocation> MemLoc) {
+      if (MemLoc == None)
+        return;
+      Vec.insert(const_cast<Value*>(MemLoc.getValue().Ptr));
+    }
+    MemoryLocation getMemoryLocation() {
+      return Loc;
+    }
+    SmallPtrSet<Value*, 4>* getVecRef() {
+      return &Vec;
+    }
+    bool isGoodForPromotion() {
+      return !CanNeverPromote && LoopInvariantAccess && HasAGoodStore;
+    }
+    void setMemoryLocation(Value* LI, Value *Replacement) {
+      Loc = MemoryLocation(Replacement, Loc.Size, Loc.AATags);
+      Vec.erase(LI);
+      Vec.insert(Replacement);
+    }
+  };
+
+  SmallVector<SingleMustAliasVec*, 4> AllSets;
+  DenseMap<const MemoryAccess *, SingleMustAliasVec*> StoredDefs;
+
+  //FIXME: This should not need to query AA, MemorySSA should cache this.
+  AliasResult alias(Optional<MemoryLocation> MemLocI, Instruction* InstrI,
+                    MemoryLocation &MemLocJ) {
+    if (MemLocI == None) {
+      ModRefInfo ModRef = AA->getModRefInfo(InstrI, MemLocJ);
+      if(bool(ModRef & MRI_Mod)) {
+        return MustAlias;
+      }
+      if(bool(ModRef & MRI_Ref)) {
+        return MayAlias;
+      }
+      return NoAlias;
+    }
+    else {
+      AliasResult Result = AA->alias(MemLocI.getValue(), MemLocJ);
+      return Result;
+    }
+  }
+
+  void addToAliasSets(const MemoryUse *Use, SmallPtrSetImpl<const MemoryAccess*> &Processed) {
+    Processed.insert(Use);
+    // Follow-up to the BIG NOTE:
+    // Because we allowed some imprecision, it is possible that the
+    // definingAccess is not the clobberingAccess. We *really* want the
+    // correct aliasing definition here, otherwise we're creating a set with
+    // things that don't alias.
+    // This is currently visible in "LoopSimplify/ashr-crash.ll"(Puts @a,@c,@d
+    // in the same set because its uses all point to the newly promoted Def)
+    // We *have to* use getClobberingAccess here for correctness!
+    // To avoid incurring the performance penalty of complete info, we can
+    // either:
+    // a) Create sets in BB order, without walking MemoryAccess uses recursively.
+    // Then, we'll need to check alias information with all existing sets and
+    // cap the number of sets created, much like the AliasSetTracker :/
+    // Working version available, but, well, yuck!
+    // b) Figure out why the MemorySSA uses are not updated to be accurate after
+    // a promotion. The problem here is that when MemorySSA reaches the
+    // "memssa-check-limit", results will still be incorrect.
+    // c) Add another way to cap this in MemorySSA.
+    // e.g. Query MemorySSA on how many calls to getClobberingMemoryAccess have
+    // passed the "memssa-check-limit", and cap that.
+
+    //MemoryDef* DefiningAcc = dyn_cast_or_null<MemoryDef>(Use->getDefiningAccess());
+    MemoryDef* DefiningAcc = dyn_cast_or_null<MemoryDef>(MSSA->getWalker()->getClobberingMemoryAccess(const_cast<MemoryUse*>(Use)));
+    if(!DefiningAcc || !DefiningAcc->getMemoryInst())
+      return;
+
+    SingleMustAliasVec *OneAliasSet = StoredDefs[DefiningAcc];
+    if (!OneAliasSet)
+      return;
+
+    Instruction* InstrI = Use->getMemoryInst();
+    Optional<MemoryLocation> MemLocI = MemoryLocation::getOrNone(InstrI);
+    MemoryLocation MemLocJ = OneAliasSet->getMemoryLocation();
+    AliasResult Result = alias(MemLocI, InstrI, MemLocJ);
+    if (Result == MayAlias) {
+      OneAliasSet->CanNeverPromote = true;
+    }
+    OneAliasSet->addMemoryLocation(MemLocI);
+  }
+
+  void addDefsHelper(MemoryLocation &MemLocJ, const MemoryAccess *DefOrUseOfADef,
+                     SingleMustAliasVec *newEntry,
+                     SmallPtrSetImpl<const MemoryAccess*> &Processed,
+                     SmallPtrSetImpl<const MemoryAccess*> &Phis, bool skipUses) {
+    for (const User *U : DefOrUseOfADef->users()) {
+      /// No need ot look at ProcessedPhis; need to looks at ProcessedDefs!
+      if (Phis.count(dyn_cast<MemoryAccess>(U)))
+        continue;
+
+      /// Process MemoryPhis
+      const MemoryPhi *Phi = dyn_cast<MemoryPhi>(U);
+      if (Phi && L->contains(Phi->getBlock())) {
+        Phis.insert(Phi);
+        addDefsHelper(MemLocJ, Phi, newEntry, Processed, Phis, true);
+        continue;
+      }
+
+      const MemoryUseOrDef *UseOrDef = dyn_cast<MemoryUseOrDef>(U);
+      if (!UseOrDef || !UseOrDef->getMemoryInst()) {
+        continue; /*FIXME: What does this mean? U=unknown value.*/
+      }
+      Instruction* InstrI = UseOrDef->getMemoryInst();
+      if (!InstrI || !L->contains(InstrI))
+        continue;
+      Optional<MemoryLocation> MemLocI = MemoryLocation::getOrNone(InstrI);
+      bool LoopInvariantAccess = ((MemLocI != None) &&
+                                  L->isLoopInvariant(MemLocI.getValue().Ptr));
+
+      /// Process MemoryDefs
+      const MemoryDef *UserDef = dyn_cast_or_null<MemoryDef>(UseOrDef);
+      if (UserDef) {
+        AliasResult Result = alias(MemLocI, InstrI, MemLocJ);
+        if (Result == MayAlias || Result == MustAlias) {
+          Processed.insert(UseOrDef);
+          if (MemLocI != None)
+            newEntry->addMemoryLocation(MemLocI.getValue());
+          else //Cannot promote stuff with no memory locations
+            newEntry->CanNeverPromote = true;
+          StoredDefs[UseOrDef] = newEntry;
+
+          StoreInst *USIn = dyn_cast_or_null<StoreInst>(InstrI);
+
+          //TODO: minor optimization: only check if !CanNeverPromote
+          if (Result == MayAlias || (USIn && USIn->isVolatile()))
+            newEntry->CanNeverPromote = true;
+          if (USIn && !USIn->isVolatile())
+            newEntry->HasAGoodStore = true;
+          newEntry->LoopInvariantAccess |= LoopInvariantAccess;
+        }
+        else {
+          addDefsHelper(MemLocJ, UserDef, newEntry, Processed, Phis, true);
+        }
+        continue;
+      }
+
+      if (skipUses)
+        continue;
+
+      /// Process MemoryUses
+      const MemoryUse *UserUse = dyn_cast_or_null<MemoryUse>(UseOrDef);
+      if (UserUse) {
+        Processed.insert(UseOrDef);
+        if (MemLocI != None)
+          newEntry->addMemoryLocation(MemLocI.getValue());
+
+        if(!newEntry->CanNeverPromote) {
+          AliasResult Result = alias(MemLocI, InstrI, MemLocJ);
+          if (Result == MayAlias)
+            newEntry->CanNeverPromote = true;
+          newEntry->LoopInvariantAccess |= LoopInvariantAccess;
+        }
+      }
+    }
+  }
+
+  void addToAliasSets(const MemoryDef *Def, SmallPtrSetImpl<const MemoryAccess*> &Processed) {
+    Processed.insert(Def);
+    Instruction* InstrJ = Def->getMemoryInst();
+    Optional<MemoryLocation> OptMemLocJ = MemoryLocation::getOrNone(InstrJ);
+    if (OptMemLocJ == None)
+      return;
+    MemoryLocation MemLocJ = OptMemLocJ.getValue();
+
+    StoreInst *SIn = dyn_cast_or_null<StoreInst>(InstrJ);
+    SingleMustAliasVec *newEntry = new SingleMustAliasVec(MemLocJ);
+    newEntry->CanNeverPromote = SIn && SIn->isVolatile();
+    newEntry->LoopInvariantAccess = L->isLoopInvariant(MemLocJ.Ptr);
+    newEntry->HasAGoodStore = SIn && !SIn->isVolatile();
+
+    SmallPtrSet<const MemoryAccess*, 32> Phis;
+    addDefsHelper(MemLocJ, Def, newEntry, Processed, Phis, false);
+    AllSets.push_back(newEntry);
+  }
+
+ public:
+  MemorySSAAliasSets (MemorySSA *mssa, MemorySSAUpdater *mssaupdater, Loop *l,
+                      LoopInfo *li, AliasAnalysis *aa, DominatorTree *dt,
+                      SmallVectorImpl<BasicBlock *> &ExitBlocks):
+                      MSSA(mssa), MSSAUpdater(mssaupdater), L(l),
+                      LI(li), AA(aa), DT(dt), AllSets() {
+    resetMSSAInsertPts(ExitBlocks);
+  }
+
+  void resetMSSAInsertPts(SmallVectorImpl<BasicBlock *> &ExitBlocks) {
+    // TODO: Better way to fill this in.
+    MSSAInsertPts.reserve(ExitBlocks.size());
+    for (unsigned I = 0; I < ExitBlocks.size(); ++I) {
+      MSSAInsertPts.push_back(nullptr);
+    }
+  }
+
+  // Creates all alias sets in L
+  void createSets() {
+    SmallPtrSet<const MemoryAccess*, 32> Processed;
+    addToSets(DT->getNode(L->getHeader()), Processed);
+  }
+
+  // TODO: Remove recursion: move to "Utils" LICM:collectChildrenInLoop.
+  void addToSets(DomTreeNode *N, SmallPtrSetImpl<const MemoryAccess*> &Processed) {
+    BasicBlock *BB = N->getBlock();
+    auto *Accesses = MSSA->getBlockAccesses(BB);
+    if (Accesses)
+    for (auto &Acc : make_range(Accesses->begin(), Accesses->end())) {
+      if (Processed.count(&Acc))
+        continue;
+      //Process uses
+      const MemoryUse *Use = dyn_cast_or_null<MemoryUse>(&Acc);
+      if (Use)
+        addToAliasSets(Use, Processed);
+      //Process defs
+      const MemoryDef *Def = dyn_cast_or_null<MemoryDef>(&Acc);
+      if (Def)
+        addToAliasSets(Def, Processed);
+    }
+
+    const std::vector<DomTreeNode *> &Children = N->getChildren();
+    for (DomTreeNode *Child : Children)
+      addToSets(Child, Processed);
+  }
+
+  SmallPtrSetImpl<Value*>* getSetIfPromotableOrNull(unsigned I) {
+    if(AllSets[I]->isGoodForPromotion()) {
+      SmallPtrSetImpl<Value*> *MustAliasPtrs = AllSets[I]->getVecRef();
+      assert (MustAliasPtrs->size() > 0 && "Alias set cannot be empty!!!\n");
+      return MustAliasPtrs;
+    }
+    return nullptr;
+  }
+
+  unsigned size() {
+    return AllSets.size();
+  }
+
+  void replace(Value *LoadI, Value *Replacement) {
+    for (auto OneAliasSet : AllSets) {
+      MemoryLocation MemLocJ = OneAliasSet->getMemoryLocation();
+      if(MemLocJ.Ptr == LoadI){
+        OneAliasSet->setMemoryLocation(LoadI, Replacement);
+        if(!OneAliasSet->CanNeverPromote && OneAliasSet->HasAGoodStore &&
+           !OneAliasSet->LoopInvariantAccess && L->isLoopInvariant(Replacement)) {
+          OneAliasSet->LoopInvariantAccess = true;
+        }
+      }
+    }
+  }
+
+  MemoryAccess* getInsertPoint(int I) {
+    return MSSAInsertPts[I];
+  }
+  void setInsertPoint(MemoryAccess* Acc, int I) {
+    MSSAInsertPts[I] = Acc;
+  }
+};
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_MEMORYSSA_ALIASSETS_H
Index: include/llvm/Support/Debug.h
===================================================================
--- include/llvm/Support/Debug.h
+++ include/llvm/Support/Debug.h
@@ -93,6 +93,14 @@
 ///
 extern bool VerifyLoopInfo;
 
+/// Enables memory ssa as a dependency for loop passes.
+///
+extern bool EnableMSSALoopDep;
+
+/// Enables LICM to use MSSA if available
+///
+extern bool UseLICMwMSSA;
+
 ///\}
 
 /// EnableDebugBuffering - This defaults to false.  If true, the debug
Index: include/llvm/Transforms/Scalar/LoopPassManager.h
===================================================================
--- include/llvm/Transforms/Scalar/LoopPassManager.h
+++ include/llvm/Transforms/Scalar/LoopPassManager.h
@@ -277,7 +277,8 @@
                                        AM.getResult<LoopAnalysis>(F),
                                        AM.getResult<ScalarEvolutionAnalysis>(F),
                                        AM.getResult<TargetLibraryAnalysis>(F),
-                                       AM.getResult<TargetIRAnalysis>(F)};
+                                       AM.getResult<TargetIRAnalysis>(F),
+                                       AM.getResult<MemorySSAAnalysis>(F).getMSSA()};
 
     // Setup the loop analysis manager from its proxy. It is important that
     // this is only done when there are loops to process and we have built the
@@ -345,6 +346,9 @@
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<LoopAnalysis>();
     PA.preserve<ScalarEvolutionAnalysis>();
+    if(EnableMSSALoopDep) {
+      PA.preserve<MemorySSAAnalysis>();
+    }
     // FIXME: What we really want to do here is preserve an AA category, but
     // that concept doesn't exist yet.
     PA.preserve<AAManager>();
Index: include/llvm/Transforms/Utils/LoopUtils.h
===================================================================
--- include/llvm/Transforms/Utils/LoopUtils.h
+++ include/llvm/Transforms/Utils/LoopUtils.h
@@ -37,6 +37,9 @@
 class DataLayout;
 class Loop;
 class LoopInfo;
+class MemorySSA;
+class MemorySSAUpdater;
+class MemorySSAAliasSets;
 class OptimizationRemarkEmitter;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
@@ -424,6 +427,7 @@
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
+                MemorySSAUpdater *, MemorySSA *,
                 LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
 
 /// \brief Walk the specified region of the CFG (defined by all blocks
@@ -436,6 +440,7 @@
 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
+                 MemorySSAUpdater *, MemorySSA *,
                  LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
 
 /// \brief Try to promote memory values to scalars by sinking stores out of
@@ -445,13 +450,15 @@
 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
 /// of the loop and loop safety information as arguments.
+/// The AliasSetTracker and MemorySSAAliasSets are alternatives to one another.
 /// Diagnostics is emitted via \p ORE. It returns changed status.
 bool promoteLoopAccessesToScalars(SmallPtrSetImpl<Value *> &,
                                   SmallVectorImpl<BasicBlock *> &,
                                   SmallVectorImpl<Instruction *> &,
                                   PredIteratorCache &, LoopInfo *,
                                   DominatorTree *, const TargetLibraryInfo *,
-                                  Loop *, AliasSetTracker *, LoopSafetyInfo *,
+                                  Loop *, AliasSetTracker *,
+                                  MemorySSAAliasSets *, LoopSafetyInfo *,
                                   OptimizationRemarkEmitter *);
 
 /// \brief Computes safety information for a loop
@@ -500,9 +507,10 @@
 /// instructions from loop body to preheader/exit. Check if the instruction
 /// can execute speculatively.
 /// If \p ORE is set use it to emit optimization remarks.
-bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
-                        Loop *CurLoop, AliasSetTracker *CurAST,
-                        LoopSafetyInfo *SafetyInfo,
+bool canSinkOrHoistInst(Instruction &, AAResults *, DominatorTree *,
+                        Loop *, AliasSetTracker *,
+                        MemorySSAUpdater *, MemorySSA *,
+                        LoopSafetyInfo *,
                         OptimizationRemarkEmitter *ORE = nullptr);
 
 /// Generates a vector reduction using shufflevectors to reduce the value.
Index: lib/Analysis/LoopAnalysisManager.cpp
===================================================================
--- lib/Analysis/LoopAnalysisManager.cpp
+++ lib/Analysis/LoopAnalysisManager.cpp
@@ -11,6 +11,7 @@
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/IR/Dominators.h"
@@ -45,12 +46,16 @@
   // loop analyses declare any dependencies on these and use the more general
   // invalidation logic below to act on that.
   auto PAC = PA.getChecker<LoopAnalysisManagerFunctionProxy>();
+  bool invalidateMemorySSAAnalysis = false;
+  if (UseLICMwMSSA && !EnableMSSALoopDep)
+    invalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA);
   if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
       Inv.invalidate<AAManager>(F, PA) ||
       Inv.invalidate<AssumptionAnalysis>(F, PA) ||
       Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
       Inv.invalidate<LoopAnalysis>(F, PA) ||
-      Inv.invalidate<ScalarEvolutionAnalysis>(F, PA)) {
+      Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||
+      invalidateMemorySSAAnalysis) {
     // Note that the LoopInfo may be stale at this point, however the loop
     // objects themselves remain the only viable keys that could be in the
     // analysis manager's cache. So we just walk the keys and forcibly clear
@@ -135,6 +140,9 @@
   PA.preserve<LoopAnalysis>();
   PA.preserve<LoopAnalysisManagerFunctionProxy>();
   PA.preserve<ScalarEvolutionAnalysis>();
+  if(EnableMSSALoopDep) {
+    PA.preserve<MemorySSAAnalysis>();
+  }
   // TODO: What we really want to do here is preserve an AA category, but that
   // concept doesn't exist yet.
   PA.preserve<AAManager>();
Index: lib/Analysis/MemorySSA.cpp
===================================================================
--- lib/Analysis/MemorySSA.cpp
+++ lib/Analysis/MemorySSA.cpp
@@ -43,6 +43,8 @@
 
 #define DEBUG_TYPE "memoryssa"
 using namespace llvm;
+bool llvm::EnableMSSALoopDep = false;
+bool llvm::UseLICMwMSSA = true;
 
 INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
                       true)
Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp
+++ lib/Transforms/Scalar/LICM.cpp
@@ -42,6 +42,9 @@
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAAliasSets.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
@@ -91,10 +94,12 @@
 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
                             const LoopSafetyInfo *SafetyInfo);
 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
+                  MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                   const LoopSafetyInfo *SafetyInfo,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
                  const Loop *CurLoop, AliasSetTracker *CurAST,
+                 MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                  const LoopSafetyInfo *SafetyInfo,
                  OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
@@ -106,15 +111,21 @@
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST);
+static bool pointerInvalidatedByLoopWithMSSA(Value *V, MemorySSA *MSSA,
+                                             MemoryUseOrDef *MUD,
+                                             Loop *CurLoop);
+static void removeFromMSSA(Instruction *I, MemorySSAUpdater *MSSAUpdater,
+                           MemorySSA *MSSA);
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
+                            MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                             const LoopInfo *LI,
                             const LoopSafetyInfo *SafetyInfo);
 
 namespace {
 struct LoopInvariantCodeMotion {
   bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
-                 TargetLibraryInfo *TLI, ScalarEvolution *SE,
+                 TargetLibraryInfo *TLI, ScalarEvolution *SE, MemorySSA *MSSA,
                  OptimizationRemarkEmitter *ORE, bool DeleteAST);
 
   DenseMap<Loop *, AliasSetTracker *> &getLoopToAliasSetMap() {
@@ -126,6 +137,7 @@
 
   AliasSetTracker *collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
                                            AliasAnalysis *AA);
+  MemorySSAUpdater* MSSAUpdater = nullptr;
 };
 
 struct LegacyLICMPass : public LoopPass {
@@ -155,7 +167,9 @@
                           &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
                           &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
                           &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
-                          SE ? &SE->getSE() : nullptr, &ORE, false);
+                          SE ? &SE->getSE() : nullptr,
+                          &getAnalysis<MemorySSAWrapperPass>().getMSSA(),
+                          &ORE, false);
   }
 
   /// This transformation requires natural loop information & requires that
@@ -164,6 +178,7 @@
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addRequired<MemorySSAWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 
@@ -204,7 +219,10 @@
                        "cached at a higher level");
 
   LoopInvariantCodeMotion LICM;
-  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.SE, ORE, true))
+  //MemorySSA *MSSA = EnableMSSALoopDep ? (&AR.MSSA) : nullptr;
+  MemorySSA *MSSA = UseLICMwMSSA ? (&AR.MSSA) : nullptr;
+  //MemorySSA *MSSA = &AR.MSSA;
+  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.SE, MSSA, ORE, true))
     return PreservedAnalyses::all();
 
   auto PA = getLoopPassPreservedAnalyses();
@@ -217,6 +235,7 @@
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
                     false)
 
@@ -231,14 +250,25 @@
 bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA,
                                         LoopInfo *LI, DominatorTree *DT,
                                         TargetLibraryInfo *TLI,
-                                        ScalarEvolution *SE,
+                                        ScalarEvolution *SE, MemorySSA *MSSA,
                                         OptimizationRemarkEmitter *ORE,
                                         bool DeleteAST) {
   bool Changed = false;
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
-  AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA);
+  AliasSetTracker *CurAST = nullptr;
+  if(!MSSA) {
+    //Note: MSSA disabled in the new PM until all loop passes preserve MSSA
+    DEBUG(dbgs() << "LICM: Using Alias Set Tracker\n");
+    CurAST = collectAliasInfoForLoop(L, LI, AA);
+    MSSAUpdater = nullptr;
+  }
+  else {
+    DEBUG(dbgs() << "LICM: Using MemorySSA\n");
+    CurAST = nullptr;
+    MSSAUpdater = new MemorySSAUpdater(MSSA);
+  }
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
@@ -259,10 +289,11 @@
   //
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
-                          CurAST, &SafetyInfo, ORE);
+                          CurAST, MSSAUpdater, MSSA, &SafetyInfo, ORE);
+
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
-                           CurAST, &SafetyInfo, ORE);
+                           CurAST, MSSAUpdater, MSSA, &SafetyInfo, ORE);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
@@ -291,27 +322,45 @@
 
       bool Promoted = false;
 
-      // Loop over all of the alias sets in the tracker object.
-      for (AliasSet &AS : *CurAST) {
-        // We can promote this alias set if it has a store, if it is a "Must" alias
-        // set, if the pointer is loop invariant, and if we are not eliminating any
-        // volatile loads or stores.
-        if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
-            AS.isVolatile() || !L->isLoopInvariant(AS.begin()->getValue()))
-          continue;
-
-        assert(!AS.empty() &&
-          "Must alias set should have at least one pointer element in it!");
+      if (CurAST) {
+        // Loop over all of the alias sets in the tracker object.
+        for (AliasSet &AS : *CurAST) {
+          // We can promote this alias set if it has a store, if it is a "Must" alias
+          // set, if the pointer is loop invariant, and if we are not eliminating any
+          // volatile loads or stores.
+          if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
+              AS.isVolatile() || !L->isLoopInvariant(AS.begin()->getValue()))
+            continue;
+
+          assert(!AS.empty() &&
+            "Must alias set should have at least one pointer element in it!");
+
+          SmallPtrSet<Value *, 4> PointerMustAliases;
+          for (const auto &ASI : AS) {
+            PointerMustAliases.insert(ASI.getValue());
+          }
 
-        SmallPtrSet<Value *, 4> PointerMustAliases;
-        for (const auto &ASI : AS) {
-          PointerMustAliases.insert(ASI.getValue());
+          Promoted |=
+              promoteLoopAccessesToScalars(PointerMustAliases,
+                                           ExitBlocks, InsertPts, PIC, LI, DT,
+                                           TLI, L, CurAST, nullptr, &SafetyInfo,
+                                           ORE);
+        }
+      }
+      else {
+        MemorySSAAliasSets AS(MSSA, MSSAUpdater, L, LI, AA, DT, ExitBlocks);
+        AS.createSets();
+
+        for (unsigned I=0; I<AS.size(); ++I) {
+          SmallPtrSetImpl<Value*> *MustAliasPtrs = AS.getSetIfPromotableOrNull(I);
+          if (MustAliasPtrs) {
+            Promoted |=
+                promoteLoopAccessesToScalars(*MustAliasPtrs,
+                                             ExitBlocks, InsertPts, PIC, LI, DT,
+                                             TLI, L, CurAST, &AS, &SafetyInfo,
+                                             ORE);
+          }
         }
-
-        Promoted |=
-            promoteLoopAccessesToScalars(PointerMustAliases,
-                                         ExitBlocks, InsertPts, PIC, LI, DT,
-                                         TLI, L, CurAST, &SafetyInfo, ORE);
       }
 
       // Once we have promoted values across the loop body we have to
@@ -334,12 +383,16 @@
   assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
          "Parent loop not left in LCSSA form after LICM!");
 
-  // If this loop is nested inside of another one, save the alias information
-  // for when we process the outer loop.
-  if (L->getParentLoop() && !DeleteAST)
-    LoopToAliasSetMap[L] = CurAST;
+  if (CurAST) {
+    // If this loop is nested inside of another one, save the alias information
+    // for when we process the outer loop.
+    if (L->getParentLoop() && !DeleteAST)
+      LoopToAliasSetMap[L] = CurAST;
+    else
+      delete CurAST;
+  }
   else
-    delete CurAST;
+    delete MSSAUpdater;
 
   if (Changed && SE)
     SE->forgetLoopDispositions(L);
@@ -376,12 +429,16 @@
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                       DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                      AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
+                      AliasSetTracker *CurAST,
+                      MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
+                      LoopSafetyInfo *SafetyInfo,
                       OptimizationRemarkEmitter *ORE) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
-         CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
+         CurLoop != nullptr && SafetyInfo != nullptr &&
+         "Unexpected input to sinkRegion");
+  assert((CurAST != nullptr || (MSSAUpdater != nullptr && MSSA != nullptr)) &&
          "Unexpected input to sinkRegion");
 
   // We want to visit children before parents. We will enque all the parents
@@ -405,7 +462,10 @@
       if (isInstructionTriviallyDead(&I, TLI)) {
         DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
         ++II;
-        CurAST->deleteValue(&I);
+        if (CurAST)
+          CurAST->deleteValue(&I);
+        if (MSSA)
+          removeFromMSSA(&I, MSSAUpdater, MSSA);
         I.eraseFromParent();
         Changed = true;
         continue;
@@ -417,9 +477,11 @@
       // operands of the instruction are loop invariant.
       //
       if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE)) {
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAUpdater, MSSA,
+                             SafetyInfo, ORE)) {
         ++II;
-        Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo, ORE);
+        Changed |= sink(I, LI, DT, CurLoop, CurAST, MSSAUpdater, MSSA,
+                        SafetyInfo, ORE);
       }
     }
   }
@@ -433,11 +495,15 @@
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                       AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
+                       AliasSetTracker *CurAST,
+                       MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
+                       LoopSafetyInfo *SafetyInfo,
                        OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
-         CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
+         CurLoop != nullptr && SafetyInfo != nullptr &&
+         "Unexpected input to hoistRegion");
+  assert((CurAST != nullptr || (MSSAUpdater != nullptr && MSSA != nullptr)) &&
          "Unexpected input to hoistRegion");
 
   // We want to visit parents before children. We will enque all the parents
@@ -458,10 +524,16 @@
         if (Constant *C = ConstantFoldInstruction(
                 &I, I.getModule()->getDataLayout(), TLI)) {
           DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
-          CurAST->copyValue(&I, C);
+          if (CurAST)
+            CurAST->copyValue(&I, C);
+          //TODO: update sets if built beforehand; otherwise, no-op
+          if (MSSA) {}
           I.replaceAllUsesWith(C);
           if (isInstructionTriviallyDead(&I, TLI)) {
-            CurAST->deleteValue(&I);
+            if (CurAST)
+              CurAST->deleteValue(&I);
+            if (MSSA)
+              removeFromMSSA(&I, MSSAUpdater, MSSA);
             I.eraseFromParent();
           }
           Changed = true;
@@ -486,7 +558,8 @@
           I.replaceAllUsesWith(Product);
           I.eraseFromParent();
 
-          hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
+          hoist(*ReciprocalDivisor, DT, CurLoop, MSSAUpdater, MSSA,
+                SafetyInfo, ORE);
           Changed = true;
           continue;
         }
@@ -496,11 +569,12 @@
         // if it is safe to hoist the instruction.
         //
         if (CurLoop->hasLoopInvariantOperands(&I) &&
-            canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) &&
+            canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAUpdater, MSSA,
+                               SafetyInfo, ORE) &&
             isSafeToExecuteUnconditionally(
                 I, DT, CurLoop, SafetyInfo, ORE,
                 CurLoop->getLoopPreheader()->getTerminator()))
-          Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+          Changed |= hoist(I, DT, CurLoop, MSSAUpdater, MSSA, SafetyInfo, ORE);
       }
   }
 
@@ -598,6 +672,7 @@
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                               Loop *CurLoop, AliasSetTracker *CurAST,
+                              MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                               LoopSafetyInfo *SafetyInfo,
                               OptimizationRemarkEmitter *ORE) {
   // Loads have extra constraints we have to verify before we can hoist them.
@@ -624,8 +699,14 @@
     AAMDNodes AAInfo;
     LI->getAAMetadata(AAInfo);
 
-    bool Invalidated =
-        pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
+    bool Invalidated = false;
+    if (CurAST)
+      Invalidated = pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
+    else //if (MSSA)
+      Invalidated = pointerInvalidatedByLoopWithMSSA(LI->getOperand(0), MSSA,
+                                                     MSSA->getMemoryAccess(LI),
+                                                     CurLoop);
+
     // Check loop-invariant address because this may also be a sinkable load
     // whose address is not necessarily loop-invariant.
     if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
@@ -653,20 +734,41 @@
       // it's arguments with arbitrary offsets.  If we can prove there are no
       // writes to this memory in the loop, we can hoist or sink.
       if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
-        for (Value *Op : CI->arg_operands())
-          if (Op->getType()->isPointerTy() &&
-              pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize,
-                                       AAMDNodes(), CurAST))
+        for (Value *Op : CI->arg_operands()) {
+          bool Invalidated = false;
+          if (CurAST)
+            Invalidated =
+                pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize,
+                                         AAMDNodes(), CurAST);
+          else //if (MSSA)
+            Invalidated =
+                pointerInvalidatedByLoopWithMSSA(Op, MSSA,
+                                                 MSSA->getMemoryAccess(CI),
+                                                 CurLoop);
+          if (Op->getType()->isPointerTy() && Invalidated)
             return false;
+        }
         return true;
       }
       // If this call only reads from memory and there are no writes to memory
       // in the loop, we can hoist or sink the call as appropriate.
       bool FoundMod = false;
-      for (AliasSet &AS : *CurAST) {
-        if (!AS.isForwardingAliasSet() && AS.isMod()) {
-          FoundMod = true;
-          break;
+      if (CurAST) {
+        for (AliasSet &AS : *CurAST) {
+          if (!AS.isForwardingAliasSet() && AS.isMod()) {
+            FoundMod = true;
+            break;
+          }
+        }
+      }
+      else if (MSSA) {
+        //TODO: need "if this call only reads from memory"
+        for (auto BBIt = (CurLoop->block_begin()); BBIt != CurLoop->block_end(); BBIt++) {
+          auto *Defs = MSSA->getBlockDefs(*BBIt);
+          if(Defs) {
+            FoundMod = true;
+            break;
+          }
         }
       }
       if (!FoundMod)
@@ -762,6 +864,7 @@
 
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
+                            MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                             const LoopInfo *LI,
                             const LoopSafetyInfo *SafetyInfo) {
   Instruction *New;
@@ -799,6 +902,23 @@
   if (!I.getName().empty())
     New->setName(I.getName() + ".le");
 
+  MemoryAccess *OldMemAcc;
+  if (MSSA && (OldMemAcc = MSSA->getMemoryAccess(&I))) {
+    MemoryAccess * NewMemAcc = MSSAUpdater->createMemoryAccessInBB(New, nullptr,
+                                         New->getParent(), MemorySSA::Beginning);
+    MemoryDef *NewMemDef = dyn_cast_or_null<MemoryDef>(NewMemAcc);
+    if(NewMemDef)
+      MSSAUpdater->insertDef(NewMemDef, true);
+    else {
+      MemoryUse *NewMemUse = dyn_cast_or_null<MemoryUse>(NewMemAcc);
+      if(NewMemUse) {
+        MSSAUpdater->insertUse(NewMemUse);
+        // This is only called to properly update the defining access
+        MSSA->getWalker()->getClobberingMemoryAccess(NewMemUse);
+      }
+    }
+  }
+
   // Build LCSSA PHI nodes for any in-loop operands. Note that this is
   // particularly cheap because we can rip off the PHI node that we're
   // replacing for the number and blocks of the predecessors.
@@ -828,6 +948,7 @@
 ///
 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
                  const Loop *CurLoop, AliasSetTracker *CurAST,
+                 MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                  const LoopSafetyInfo *SafetyInfo,
                  OptimizationRemarkEmitter *ORE) {
   DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
@@ -884,13 +1005,17 @@
       New = It->second;
     else
       New = SunkCopies[ExitBlock] =
-          CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
+          CloneInstructionInExitBlock(I, *ExitBlock, *PN,
+                                      MSSAUpdater, MSSA, LI, SafetyInfo);
 
     PN->replaceAllUsesWith(New);
     PN->eraseFromParent();
   }
 
-  CurAST->deleteValue(&I);
+  if (CurAST)
+    CurAST->deleteValue(&I);
+  if (MSSA)
+    removeFromMSSA(&I, MSSAUpdater, MSSA);
   I.eraseFromParent();
   return Changed;
 }
@@ -899,6 +1024,7 @@
 /// is safe to hoist, this instruction is called to do the dirty work.
 ///
 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
+                  MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                   const LoopSafetyInfo *SafetyInfo,
                   OptimizationRemarkEmitter *ORE) {
   auto *Preheader = CurLoop->getLoopPreheader();
@@ -920,6 +1046,15 @@
 
   // Move the new node to the Preheader, before its terminator.
   I.moveBefore(Preheader->getTerminator());
+  if (MSSA) {
+    // Update MemorySSA if moving I just moved a load or store
+    MemoryUseOrDef *OldMemAcc = dyn_cast_or_null<MemoryUseOrDef>(MSSA->getMemoryAccess(&I));
+    if(OldMemAcc) {
+      MSSAUpdater->moveToPlace(OldMemAcc, Preheader, MemorySSA::End);
+      // This is only called to properly update the defining access
+      MSSA->getWalker()->getClobberingMemoryAccess(OldMemAcc);
+    }
+  }
 
   // Do not retain debug locations when we are moving instructions to different
   // basic blocks, because we want to avoid jumpy line tables. Calls, however,
@@ -971,7 +1106,11 @@
   SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
   SmallVectorImpl<Instruction *> &LoopInsertPts;
   PredIteratorCache &PredCache;
-  AliasSetTracker &AST;
+
+  // AST and AS are alternatives!
+  AliasSetTracker *AST;
+  MemorySSAAliasSets *AS;
+
   LoopInfo &LI;
   DebugLoc DL;
   int Alignment;
@@ -998,12 +1137,13 @@
                SmallPtrSetImpl<Value *> &PMA,
                SmallVectorImpl<BasicBlock *> &LEB,
                SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
-               AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
+               AliasSetTracker *ast, MemorySSAAliasSets *as,
+               LoopInfo &li, DebugLoc dl, int alignment,
                bool UnorderedAtomic, const AAMDNodes &AATags)
       : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
         LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
-        LI(li), DL(std::move(dl)), Alignment(alignment),
-        UnorderedAtomic(UnorderedAtomic),AATags(AATags) {}
+        AS(as), LI(li), DL(std::move(dl)), Alignment(alignment),
+        UnorderedAtomic(UnorderedAtomic), AATags(AATags) {}
 
   bool isInstInList(Instruction *I,
                     const SmallVectorImpl<Instruction *> &) const override {
@@ -1033,14 +1173,37 @@
       NewSI->setDebugLoc(DL);
       if (AATags)
         NewSI->setAAMetadata(AATags);
+      if (AS) {
+        MemoryAccess *MSSAInsertPoint = AS->getInsertPoint(i);
+        MemoryAccess *NewMemAcc;
+        if (!MSSAInsertPoint) {
+          NewMemAcc = AS->MSSAUpdater->createMemoryAccessInBB
+              (NewSI, nullptr, NewSI->getParent(), MemorySSA::Beginning);
+        }
+        else {
+          NewMemAcc = AS->MSSAUpdater->createMemoryAccessAfter
+              (NewSI, nullptr, MSSAInsertPoint);
+        }
+        AS->setInsertPoint(NewMemAcc, i);
+        AS->MSSAUpdater->insertDef(cast<MemoryDef>(NewMemAcc), true);
+        //FIXME: true for safety, false may still be correct.
+      }
     }
   }
 
   void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
     // Update alias analysis.
-    AST.copyValue(LI, V);
+    if (AST)
+      AST->copyValue(LI, V);
+    if (AS)
+      AS->replace(LI, V);
+  }
+  void instructionDeleted(Instruction *I) const override {
+    if (AST)
+      AST->deleteValue(I);
+    if (AS)
+      removeFromMSSA(I, AS->MSSAUpdater, AS->MSSA);
   }
-  void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); }
 };
 } // end anon namespace
 
@@ -1054,12 +1217,16 @@
     SmallVectorImpl<BasicBlock *> &ExitBlocks,
     SmallVectorImpl<Instruction *> &InsertPts, PredIteratorCache &PIC,
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
-    Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
+    Loop *CurLoop, AliasSetTracker *CurAST,
+    MemorySSAAliasSets *AS,
+    LoopSafetyInfo *SafetyInfo,
     OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
-         CurAST != nullptr && SafetyInfo != nullptr &&
+         SafetyInfo != nullptr &&
          "Unexpected Input to promoteLoopAccessesToScalars");
+  assert((CurAST != nullptr || (AS != nullptr)) &&
+         "Unexpected input to promoteLoopAccessesToScalars");
 
   Value *SomePtr = *PointerMustAliases.begin();
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
@@ -1288,7 +1455,7 @@
   SmallVector<PHINode *, 16> NewPHIs;
   SSAUpdater SSA(&NewPHIs);
   LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
-                        InsertPts, PIC, *CurAST, *LI, DL, Alignment,
+                        InsertPts, PIC, CurAST, AS, *LI, DL, Alignment,
                         SawUnorderedAtomic, AATags);
 
   // Set up the preheader to have a definition of the value.  It is the live-out
@@ -1303,13 +1470,29 @@
     PreheaderLoad->setAAMetadata(AATags);
   SSA.AddAvailableValue(Preheader, PreheaderLoad);
 
+  MemoryAccess *PreheaderLoadMemoryAccess;
+  if (AS) {
+    //Update MSSA
+    PreheaderLoadMemoryAccess =
+      AS->MSSAUpdater->createMemoryAccessInBB(PreheaderLoad, nullptr,
+                                          PreheaderLoad->getParent(),
+                                          MemorySSA::End);
+    MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
+    AS->MSSAUpdater->insertUse(NewMemUse);
+    // This is only called to properly update the defining access
+    AS->MSSA->getWalker()->getClobberingMemoryAccess(NewMemUse);
+  }
+
   // Rewrite all the loads in the loop and remember all the definitions from
   // stores in the loop.
   Promoter.run(LoopUses);
 
   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
-  if (PreheaderLoad->use_empty())
+  if (PreheaderLoad->use_empty()) {
+    if (AS)
+      AS->MSSAUpdater->removeMemoryAccess(PreheaderLoadMemoryAccess);
     PreheaderLoad->eraseFromParent();
+  }
 
   return true;
 }
@@ -1409,6 +1592,76 @@
   return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
 }
 
+// Checks arguments of a Phi, so Defs and other Phis.
+// returns true if Acc is not a load or a live on entry
+static bool checkNotLoadOrLOE(MemoryAccess *Acc, MemorySSA *MSSA,
+                              SmallPtrSetImpl<MemoryAccess*>& Processed) {
+  if (Processed.count(Acc))
+    return true;
+  if (MSSA->isLiveOnEntryDef(Acc))
+    return false;
+
+  MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(Acc);
+  MemoryDef *Def = dyn_cast_or_null<MemoryDef>(Acc);
+  if (Phi) {
+    bool MSSAResult = false;
+    int NoArgsPhi = Phi->getNumIncomingValues();
+    Processed.insert(Acc);
+    for (int I = 0; I < NoArgsPhi; I++) {
+      MemoryAccess *Arg = Phi->getIncomingValue(I);
+      MSSAResult |= checkNotLoadOrLOE(Arg, MSSA, Processed);
+    }
+    return MSSAResult;
+  }
+  else if (Def){
+    Instruction *AccI = Def->getMemoryInst();
+    if(AccI && isa<LoadInst>(AccI)) //a load is a def if volatile
+      return false;
+  }
+  return true;
+}
+
+static bool pointerInvalidatedByLoopWithMSSAHelper
+    (MemorySSA *MSSA, MemoryUseOrDef *MUD, Loop *CurLoop) {
+  bool MSSAResult = false;
+  MemoryUse *MU = nullptr;
+  //MUD is from a LoopInstr or CallInstr, so both Uses.
+  if (MUD && (MU = dyn_cast_or_null<MemoryUse>(MUD))) {
+    // BIG NOTE: getDefiningAccess may not be precise, since optimizeUses
+    // in MemorySSA is capped. This is good! It means that this becomes best
+    // effort, rather than incur a performance penalty for loops with large load
+    // count. Perfect accuracy can be obtained with:
+    // MSSA->getWalker()->getClobberingMemoryAccess(MU)
+    // For the updates done by sink/hoist/promotion (insertUse, moveToPlace),
+    // we *explicitly* call getClobberingMemoryAccesses. This will get perfect
+    // results for small tests, and imprecise but fast for large ones.
+    //MemoryAccess *Source = MSSA->getWalker()->getClobberingMemoryAccess(MU);
+    MemoryAccess *Source = MU->getDefiningAccess();
+
+    if (MSSA->isLiveOnEntryDef(Source)) {
+      MSSAResult = false;
+    }
+    else {
+      BasicBlock *DBB = Source->getBlock();
+      if (CurLoop->contains(DBB)) {
+        // if the Source is a combination of liveOnEntry and
+        // volatile loads (treated as Defs), it's not invalidated.
+        SmallPtrSet<MemoryAccess*, 4> Processed;
+        MSSAResult = checkNotLoadOrLOE(Source, MSSA, Processed);
+      }
+    }
+  }
+  return MSSAResult;
+}
+static bool pointerInvalidatedByLoopWithMSSA(Value *V, MemorySSA *MSSA,
+                                             MemoryUseOrDef *MUD,
+                                             Loop *CurLoop) {
+  if(isa<UndefValue>(V))
+    return true;
+  bool MSSAResult = pointerInvalidatedByLoopWithMSSAHelper(MSSA, MUD, CurLoop);
+  return MSSAResult;
+}
+
 /// Little predicate that returns true if the specified basic block is in
 /// a subloop of the current one, not the current one itself.
 ///
@@ -1416,3 +1669,12 @@
   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
   return LI->getLoopFor(BB) != CurLoop;
 }
+
+static void removeFromMSSA(Instruction *I,
+                           MemorySSAUpdater *MSSAUpdater,
+                           MemorySSA *MSSA) {
+  MemoryUseOrDef *AccI = MSSA->getMemoryAccess(I);
+  if(AccI) {
+    MSSAUpdater->removeMemoryAccess(AccI);
+  }
+}
Index: lib/Transforms/Scalar/LoopDistribute.cpp
===================================================================
--- lib/Transforms/Scalar/LoopDistribute.cpp
+++ lib/Transforms/Scalar/LoopDistribute.cpp
@@ -31,6 +31,7 @@
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
@@ -952,11 +953,12 @@
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
 
   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
   std::function<const LoopAccessInfo &(Loop &)> GetLAA =
       [&](Loop &L) -> const LoopAccessInfo & {
-    LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI};
+    LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
     return LAM.getResult<LoopAccessAnalysis>(L, AR);
   };
 
Index: lib/Transforms/Scalar/LoopLoadElimination.cpp
===================================================================
--- lib/Transforms/Scalar/LoopLoadElimination.cpp
+++ lib/Transforms/Scalar/LoopLoadElimination.cpp
@@ -31,6 +31,7 @@
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
@@ -648,11 +649,12 @@
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
 
   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
   bool Changed = eliminateLoadsAcrossLoops(
       F, LI, DT, [&](Loop &L) -> const LoopAccessInfo & {
-        LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI};
+        LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
         return LAM.getResult<LoopAccessAnalysis>(L, AR);
       });
 
Index: lib/Transforms/Scalar/LoopSink.cpp
===================================================================
--- lib/Transforms/Scalar/LoopSink.cpp
+++ lib/Transforms/Scalar/LoopSink.cpp
@@ -288,7 +288,8 @@
     // No need to check for instruction's operands are loop invariant.
     assert(L.hasLoopInvariantOperands(I) &&
            "Insts in a loop's preheader should have loop invariant operands!");
-    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr))
+    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, nullptr,
+                            nullptr, nullptr))
       continue;
     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
       Changed = true;
Index: lib/Transforms/Vectorize/LoopVectorize.cpp
===================================================================
--- lib/Transforms/Vectorize/LoopVectorize.cpp
+++ lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -8084,11 +8084,12 @@
     auto &AC = AM.getResult<AssumptionAnalysis>(F);
     auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
     auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+    auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
 
     auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
     std::function<const LoopAccessInfo &(Loop &)> GetLAA =
         [&](Loop &L) -> const LoopAccessInfo & {
-      LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI};
+      LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
       return LAM.getResult<LoopAccessAnalysis>(L, AR);
     };
     bool Changed =
Index: test/Other/loop-pm-invalidation.ll
===================================================================
--- test/Other/loop-pm-invalidation.ll
+++ test/Other/loop-pm-invalidation.ll
@@ -51,6 +51,7 @@
 ; CHECK-LOOP-INV-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-LOOP-INV-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-LOOP-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Running pass: NoOpLoopPass
@@ -78,6 +79,7 @@
 ; CHECK-SCEV-INV-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-SCEV-INV-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-SCEV-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Running pass: NoOpLoopPass
@@ -115,6 +117,7 @@
 ; CHECK-LOOP-INV-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-LOOP-INV-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-LOOP-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Running pass: NoOpLoopPass
@@ -149,6 +152,7 @@
 ; CHECK-SCEV-INV-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-SCEV-INV-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-SCEV-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Running pass: NoOpLoopPass
@@ -200,6 +204,7 @@
 ; CHECK-LOOP-INV-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-LOOP-INV-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-LOOP-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Running pass: NoOpLoopPass
@@ -227,6 +232,7 @@
 ; CHECK-SCEV-INV-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-SCEV-INV-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-SCEV-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Running pass: NoOpLoopPass
@@ -252,6 +258,7 @@
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running pass: NoOpLoopPass
@@ -259,10 +266,11 @@
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Clearing all analysis results for:
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Finished {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Invalidating all non-preserved analyses
+; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Invalidating analysis: MemorySSAAnalysis
+; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Invalidating analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}ScalarEvolutionAnalysis
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Invalidating all non-preserved analyses
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Invalidating analysis: ScalarEvolutionAnalysis
-; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Invalidating analysis: InnerAnalysisManagerProxy<{{.*}}Loop
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on dead_loop
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Finished {{.*}}Function pass manager run.
 
Index: test/Other/new-pass-manager.ll
===================================================================
--- test/Other/new-pass-manager.ll
+++ test/Other/new-pass-manager.ll
@@ -460,6 +460,7 @@
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: TargetIRAnalysis
+; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Starting Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running pass: RepeatedPass
Index: test/Other/pass-pipelines.ll
===================================================================
--- test/Other/pass-pipelines.ll
+++ test/Other/pass-pipelines.ll
@@ -37,6 +37,9 @@
 ; CHECK-O2-NEXT: FunctionPass Manager
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager
+; FIXME: Adition of MemorySSA splits the Loop Pass Manager into 3.
+; CHECK-O2: Loop Pass Manager
+; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NOT: Manager
 ; FIXME: We shouldn't be pulling out to simplify-cfg and instcombine and
 ; causing new loop pass managers.
Index: unittests/Transforms/Scalar/LoopPassManagerTest.cpp
===================================================================
--- unittests/Transforms/Scalar/LoopPassManagerTest.cpp
+++ unittests/Transforms/Scalar/LoopPassManagerTest.cpp
@@ -304,6 +304,7 @@
     // those.
     FAM.registerPass([&] { return AAManager(); });
     FAM.registerPass([&] { return AssumptionAnalysis(); });
+    FAM.registerPass([&] { return MemorySSAAnalysis(); });
     FAM.registerPass([&] { return ScalarEvolutionAnalysis(); });
     FAM.registerPass([&] { return TargetLibraryAnalysis(); });
     FAM.registerPass([&] { return TargetIRAnalysis(); });