Add MemorySSA alternative to AliasSetTracker in LICM.

[asbirlea]

Summary

This patch adds MemorySSA as an alternative to the AliasSetTracker in LICM.
I'm also using this to list several issues I came across, and get feedback on best ways to address them.
At the end of the day, doing such a replacement may require major rewrites to LICM, this patch
still tries to fit into the pattern that already exists in LICM, that, for promotion in particular,
is not ideal for using MemorySSA.

This patch is intended to add the functionality without enabling it by default.
Work for follow-up patches:
---> Teach all loop passes to preserve MemorySSA
---> Expose alias information for Uses in MemorySSA

Issues:

• (Current approach needs review) Adding MemorySSA as a loop dependency ------>This patch adds MemorySSA as a dependency to all loop passes. It is added as a required pass that gets invalidated if used in LICM. The ideal scenario is to have all loop passes preserve MemorySSA. ------>MemorySSA is *not* used by default in LICM in this patch. However it is always *built*. ------>Patch updates tests to reflect MemorySSA pass being run/invalidated: test/Other/loop-pm-invalidation.ll test/Other/new-pass-manager.ll test/Other/pass-pipelines.ll ------>Patch does *not* update "unittests/Transforms/Scalar/LoopPassManagerTest.cpp" (fails when LICMwMSSA=true)

• For hoist/sink, it is possible to get "less than perfect" results, due to the fact that we intentionally allow

some imprecision, by using getDefiningAccess instead of getClobberingAccess. MemorySSA has a cap on the number of stores/phis it will walk past when optimizing Uses (memssa-check-limit).
------>(Done - Working as intended) See "BIG NOTE" in LICM.cpp.

• In order to keep the promotion mechanism the same, we use MemorySSA to create some alias sets.

------>(Major refactor needed, will not address in this patch) Changing the promotion mechanism will require some major changes, I'm not sure this is the path to go on now.
------>(Done) We still face a performance penalty if we allow full sets to be created. This time, we cannot rely on the
imprecision approach used for hoist/sink. See the follow up to BIG NOTE in MemorySSAAliasSets.h
Patch has a cap on the number of sets and number of MemorySSA queries that did work (vs used cached info).
------>(TODO added in MemorySSAAliasSets.h) We can avoid calling into AA for uses. From discussions with dberlin, this info is available and could be exposed by MemorySSA. For defs, we still need to query AA.
------>(Done) [refactor] Move LICM:collectChildrenInLoop to Utils and reuse in MemorySSAAliasSets.h to avoid recursion. This is required to avoid blowing up stack (D35609).

[davide]

Thanks, I'll review this soon.
A quick question. a concern people have about MemorySSA is that you pay upfront for O(1) queries, which may have some impact on compile time.
(e.g. in EarlyCSE). AST is already O(N^2), and in some cases badly so, but I wonder if you have compile time measurements of the impact of your change?

[asbirlea]

As far as I have tested, the cost of building MemorySSA is low because it does not incur all the cost up front.
More precisely, "optimizeUses" is capped. Only when the clobbering info is requested (if this was not part of the initial optimize pass) there's a pass to obtain it.
For hoist/sink, LICM takes advantage of this.

For promotion, LICM does not use it in this patch, and as I mentioned in the description, there is no cap. So the test in PR28670/PR28832 will not be happy.
I have a version that adds a threshold, but it does more work creating the sets. With the current patch, a small extension to MemorySSA should be enough to get a similar threshold.
With sink/hoist/promotion capped like this, the test in the PRs I mentioned runs on par with the saturated AST.

I tried to add extensive comments in code to describe ways to minimize cost, please let me know if they're unclear.

I plan to get more results for compile times after I address all issues, and before landing. I'll appreciate others testing this once this is ready to land.

[• dberlin]

In D35741#817737, @davide wrote:

Thanks, I'll review this soon.
A quick question. a concern people have about MemorySSA is that you pay upfront for O(1) queries, which may have some impact on compile time.

FWIW: This is and always has been false accounting in most passes as you know.
Most passes that could use MemorySSA already ask about every load and store in the function.
The only reason people think it's faster to not use MemorySSA, or to avoid the upfront cost, is because our time-passes doesn't account function time to lazy utilities/analysis properly.
If it did, AA/etc time would look *much* larger than it does now, because in reality, it *is* much larger than it seems.

IE if you avoid optimize uses, and call getClobberingAccess on every load/store, "MemorySSA" time goes down, overall time goes up.

(e.g. in EarlyCSE). AST is already O(N^2), and in some cases badly so, but I wonder if you have compile time measurements of the impact of your change?

MemorySSA as alias sets (IE as done promotion) in this manner is not going to be faster in a lot of cases.

But you are going to have to rewrite how promotion in LICM functions (IE not use alias sets) to get the advantages of really using MemorySSA.
RIght now it's kinda wonky

[davide]

In D35741#817873, @dberlin wrote:

In D35741#817737, @davide wrote:

Thanks, I'll review this soon.
A quick question. a concern people have about MemorySSA is that you pay upfront for O(1) queries, which may have some impact on compile time.

FWIW: This is and always has been false accounting in most passes as you know.
Most passes that could use MemorySSA already ask about every load and store in the function.
The only reason people think it's faster to not use MemorySSA, or to avoid the upfront cost, is because our time-passes doesn't account function time to lazy utilities/analysis properly.
If it did, AA/etc time would look *much* larger than it does now, because in reality, it *is* much larger than it seems.

IE if you avoid optimize uses, and call getClobberingAccess on every load/store, "MemorySSA" time goes down, overall time goes up.

Yes :) Sorry if it wasn't clear, I'm fairly sure this is the correct way forward.
You know this already, but for the records.
What I was referring to is that when EarlyCSE was switched to MemorySSA that resulted in a "regression", which was basically "compute MemorySSA" (this doesn't necessarily apply here as the old earlyCSE was using a fairly simple scheme while LICM uses AST which is already costly).
This could've been avoided if GVNHoist was still the default and both updated MemSSA so you didn't pay the cost of recomputing.
I guess the more stuff we move in the compiler to use MemSSA (and teach to preserve, the more we amortize the cost), but I was curious about what was the situation today with this change :)

(e.g. in EarlyCSE). AST is already O(N^2), and in some cases badly so, but I wonder if you have compile time measurements of the impact of your change?

MemorySSA as alias sets (IE as done promotion) in this manner is not going to be faster in a lot of cases.

But you are going to have to rewrite how promotion in LICM functions (IE not use alias sets) to get the advantages of really using MemorySSA.
RIght now it's kinda wonky

[asbirlea]

Update to head following fixes in dependent revisions.
Updated description. Clang-format.
[Still a few items remaining to address]

[asbirlea]

Replace creation of alias sets for promotion with non-recursive method.
There is no gain here compared with AST as long as we have to create these sets (i.e. fit into the current pattern for promotion), and this implementation is more legible and easier to add a threshhold.

Remaining issue in this patch: Resolve what is the best approach to have MemorySSA as a dependency for LICM (before all Loop passes preserve MemorySSA, and without splitting the loop pass pipeline)
Currently failing tests due to this issue:
unittests/Transforms/Scalar/ScalarTests/LoopPassManagerTest
Transforms/LoopUnroll/unroll-loop-invalidation.ll

[asbirlea]

Remove MemorySSA as the default for LICM. All tests passing.
The default remains the Alias Set Tracker with the current state of the patch.
MemorySSA is still built, but never invalidated or used(!). It is only preserved by LICM
when LICMwMSSA is set to true which causes unittests/Transforms/Scalar/LoopPassManagerTest.cpp to fail.

As such, the patch in its current state:

• adds most of (all?) the functionality to use MemorySSA in LICM.
• does not enable any of this functionality
• it is *not* a NFC, since MemorySSA is added as a Loop dependency and built, so there may be some added overhead.

[sanjoy]

I have added some generic style comments.

As discussed in person, I think we should split out the MemorySSAAliasSets class, and add some targeted unit tests.

Please also add a comment describing the algorithm at a high level.

include/llvm/Analysis/MemorySSAAliasSets.h

10 ↗

(On Diff #107731)

s/enablei/enable/

49 ↗

(On Diff #107731)

The whitespace is a bit off here (clang-format?).

98 ↗

(On Diff #107731)

You probably should split this out into header and a .cpp -- that way telling the interface apart from the implementation will become easier.

include/llvm/Support/Debug.h

102

I'd prefer to spell this out as UseLICMWithMSSA.

include/llvm/Transforms/Scalar/LoopPassManager.h

350

LLVM style is to avoid braces around single line statements like this.

include/llvm/Transforms/Utils/MemorySSAAliasSets.h

10

s/enablei/enable/

28

Opening namespaces in headers is against LLVM style.

34

I'd prefer having these under accessors.

43

I'm not sure about the name -- how about MustAliasSet? The "single" part is implied by the fact that the name is singular, and this is semantically a "set" and not a "vec".

54

You probably don't need the CanNeverPromote(false) bit.

58

This will be a line shorter without an early return.

86

These need to be cl::opt s

You should also split this header into a .cpp file (and put the cl::opt s in that .cpp file).

90

You should use LLVM_ENABLE_DUMP and LLVM_DUMP_METHOD for this. See the definition and declaration of e.g. DominanceFrontierWrapperPass::dump()

96

Can be a ternary. Same for loopContains

112

I'd structure this as:

if (MemLocI)
  return AA->alias(MemLocI.getValue(), MemLocJ);
// Rest of the code

247

In loopContains you've handled the case where L is nullptr, but you've not done the same here.

253

Can this be for (auto &Acc : *Accesses)?

260

You can do:

if (const auto *Use = dyn_cast_or_null<MemoryUse>(&Acc))
  addToAliasSets(Use);

also, the second if can be an else if.

284

Can you please give this a more obvious name, like replaceMemoryLocation?

Also, the name LoadI is misleading -- it isn't the load instruction, but it is the memory location, right?

[asbirlea]

Stale, no longer applies.

include/llvm/Analysis/LoopAnalysisManager.h

 
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #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"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 /// The adaptor from a function pass to a loop pass computes these analyses and
 /// makes them available to the loop passes "for free". Each loop pass is
 /// expected expected to update these analyses if necessary to ensure they're
 /// valid after it runs.
 struct LoopStandardAnalysisResults {
   AAResults &AA;
   AssumptionCache ∾
   DominatorTree &DT;
   LoopInfo &LI;
   ScalarEvolution &SE;
   TargetLibraryInfo &TLI;
   TargetTransformInfo &TTI;
+  MemorySSA &MSSA;
 };
 
 /// Extern template declaration for the analysis set for this IR unit.
 extern template class AllAnalysesOn<Loop>;
 
 extern template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;
 /// \brief The loop analysis manager.
 ///

include/llvm/Support/Debug.h

 /// Enables verification of dominator trees.
 ///
 extern bool VerifyDomInfo;
 
 /// Enables verification of loop info.
 ///
 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
 /// stream will install signal handlers to dump any buffered debug
 /// output.  It allows clients to selectively allow the debug stream
 /// to install signal handlers if they are certain there will be no
 /// conflict.
 ///

include/llvm/Transforms/Scalar/LoopPassManager.h

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
     // Get the loop structure for this function
     LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 
     // If there are no loops, there is nothing to do here.
     if (LI.empty())
       return PA;
 
     // Get the analysis results needed by loop passes.
-    LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
-                                       AM.getResult<AssumptionAnalysis>(F),
-                                       AM.getResult<DominatorTreeAnalysis>(F),
-                                       AM.getResult<LoopAnalysis>(F),
-                                       AM.getResult<ScalarEvolutionAnalysis>(F),
-                                       AM.getResult<TargetLibraryAnalysis>(F),
-                                       AM.getResult<TargetIRAnalysis>(F)};
+    LoopStandardAnalysisResults LAR = {
+        AM.getResult<AAManager>(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
     // LoopStandardAnalysisResults object. The loop analyses cached in this
     // manager have access to those analysis results and so it must invalidate
     // itself when they go away.
     LoopAnalysisManager &LAM =
         AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
#endif
     // but that's OK because we've taken care to invalidate analyses in the
     // loop analysis manager incrementally above.
     PA.preserveSet<AllAnalysesOn<Loop>>();
     PA.preserve<LoopAnalysisManagerFunctionProxy>();
     // We also preserve the set of standard analyses.
     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>();
     PA.preserve<BasicAA>();
     PA.preserve<GlobalsAA>();
     PA.preserve<SCEVAA>();
     return PA;
   }

include/llvm/Transforms/Utils/LoopUtils.h

 namespace llvm {
 
 class AliasSet;
 class AliasSetTracker;
 class BasicBlock;
 class DataLayout;
 class Loop;
 class LoopInfo;
+class MemorySSA;
+class MemorySSAUpdater;
+class MemorySSAAliasSets;
 class OptimizationRemarkEmitter;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 

 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
+                MemorySSAUpdater *, MemorySSA *, LoopSafetyInfo *,
+                OptimizationRemarkEmitter *ORE);
 
 /// \brief Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
+                 MemorySSAUpdater *, MemorySSA *, LoopSafetyInfo *,
+                 OptimizationRemarkEmitter *ORE);
 
 /// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
 /// 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(const SmallSetVector<Value *, 8> &,
-                                  SmallVectorImpl<BasicBlock *> &,
-                                  SmallVectorImpl<Instruction *> &,
-                                  PredIteratorCache &, LoopInfo *,
-                                  DominatorTree *, const TargetLibraryInfo *,
-                                  Loop *, AliasSetTracker *, LoopSafetyInfo *,
-                                  OptimizationRemarkEmitter *);
+bool promoteLoopAccessesToScalars(
+    const SmallSetVector<Value *, 8> &, SmallVectorImpl<BasicBlock *> &,
+    SmallVectorImpl<Instruction *> &, PredIteratorCache &, LoopInfo *,
+    DominatorTree *, const TargetLibraryInfo *, Loop *, AliasSetTracker *,
+    MemorySSAAliasSets *, LoopSafetyInfo *, OptimizationRemarkEmitter *);
 
 /// Does a BFS from a given node to all of its children inside a given loop.
 /// The returned vector of nodes includes the starting point.
 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N,
-                                                     const Loop *CurLoop);
+                                                     Loop *CurLoop);
 
 /// \brief Computes safety information for a loop
 /// checks loop body & header for the possibility of may throw
 /// exception, it takes LoopSafetyInfo and loop as argument.
 /// Updates safety information in LoopSafetyInfo argument.
 void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
 
 /// Returns true if the instruction in a loop is guaranteed to execute at least

 
 /// Returns true if the hoister and sinker can handle this instruction.
 /// If SafetyInfo is null, we are checking for sinking instructions from
 /// preheader to loop body (no speculation).
 /// If SafetyInfo is not null, we are checking for hoisting/sinking
 /// 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.
 Value *getShuffleReduction(IRBuilder<> &Builder, Value *Src, unsigned Op,
                            RecurrenceDescriptor::MinMaxRecurrenceKind
                                MinMaxKind = RecurrenceDescriptor::MRK_Invalid,
                            ArrayRef<Value *> RedOps = ArrayRef<Value *>());
 

include/llvm/Transforms/Utils/MemorySSAAliasSets.h

+//===-- 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"
+#include "llvm/Transforms/Utils/LoopUtils.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 {
+    MemoryLocation Loc;
+    SmallSetVector<Value *, 8> Vec;
+
+  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; }
+    SmallSetVector<Value *, 8> *getVecRef() { return &Vec; }
+    bool isGoodForPromotion() {
+      return !CanNeverPromote && LoopInvariantAccess && HasAGoodStore;
+    }
+    void setMemoryLocation(Value *LI, Value *Replacement) {
+      Loc = MemoryLocation(Replacement, Loc.Size, Loc.AATags);
+      Vec.remove(LI);
+      Vec.insert(Replacement);
+    }
+    void dump() {
+      dbgs() << "Set cannot be promoted: " << CanNeverPromote << "\n";
+      dbgs() << "Has only loop invariant accesses: " << LoopInvariantAccess
+             << "\n";
+      dbgs() << "Contains a promotable store: " << HasAGoodStore << "\n";
+      dbgs() << "Contents: \n";
+      for (Value *V : Vec)
+        dbgs() << " Value: " << *V << "\n";
+    }
+  };
+
+  SmallVector<SingleMustAliasVec *, 4> AllSets;
+  DenseMap<const MemoryAccess *, SingleMustAliasVec *> StoredDefs;
+  unsigned MemorySSATraversalPenalty = 0;
+  unsigned CAP_NO_ALIAS_SETS = 30;
+  unsigned CAP_MSSA_TRAVERSALS = 30;
+
+  void dump() {
+    for (SingleMustAliasVec *Set : AllSets)
+      Set->dump();
+  }
+
+  bool isLoopInvariant(const Value *V) {
+    if(!L)
+      return true;
+    return L->isLoopInvariant(V);
+  }
+  bool loopContains(Instruction *I) {
+    if(!L)
+      return true;
+    return L->contains(I);
+  }
+  bool loopContains(BasicBlock *B) {
+    if(!L)
+      return true;
+    return L->contains(B);
+  }
+
+  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) {
+    // 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 don't check against existing sets
+    // - we get first defining access, then clobbering access. If the two are
+    // different, then we increment a local cost - the cost of optimizing the
+    // info for this use past the "memssa-check-limit".
+    // - we stop creating sets after CAP_MSSA_TRAVERSALS calls to getClobbering
+    // that did work (result != getDefining).
+    // - we do *not* have partial info to reuse, so nothing is promoted when
+    // cost is exceeded.
+    MemoryDef *DefiningAcc = dyn_cast_or_null<MemoryDef>(
+        const_cast<MemoryUse *>(Use)->getDefiningAccess());
+    MemoryDef *ClobberingAcc = dyn_cast_or_null<MemoryDef>(
+        MSSA->getWalker()->getClobberingMemoryAccess(
+            const_cast<MemoryUse *>(Use)));
+
+    if (DefiningAcc != ClobberingAcc)
+      MemorySSATraversalPenalty++;
+    if (!ClobberingAcc || !ClobberingAcc->getMemoryInst())
+      return;
+
+    SingleMustAliasVec *OneAliasSet = StoredDefs[ClobberingAcc];
+    if (!OneAliasSet)
+      return;
+
+    Instruction *InstrI = Use->getMemoryInst();
+    Optional<MemoryLocation> MemLocI = MemoryLocation::getOrNone(InstrI);
+    MemoryLocation MemLocJ = OneAliasSet->getMemoryLocation();
+    // FIXME: This is KNOWN by MSSA, i.e. if may or must. TODO: expose this.
+    AliasResult Result = alias(MemLocI, InstrI, MemLocJ);
+    if (Result == MayAlias) {
+      OneAliasSet->CanNeverPromote = true;
+    }
+    OneAliasSet->addMemoryLocation(MemLocI);
+  }
+
+  void addToAliasSets(const MemoryDef *Def) {
+    Instruction *InstrI = Def->getMemoryInst();
+    Optional<MemoryLocation> MemLocI = MemoryLocation::getOrNone(InstrI);
+
+    SingleMustAliasVec *FoundMustAlias = nullptr;
+    bool FoundMayAlias = false;
+
+    StoreInst *SIn = dyn_cast_or_null<StoreInst>(InstrI);
+    bool LoopInvariantAccess =
+        ((MemLocI != None) && isLoopInvariant(MemLocI.getValue().Ptr));
+    bool CanNeverPromote = (SIn && SIn->isVolatile()) || MemLocI == None;
+    bool HasAGoodStore = SIn && !SIn->isVolatile();
+
+    for (auto OneAliasSet : AllSets) {
+      MemoryLocation MemLocJ = OneAliasSet->getMemoryLocation();
+      AliasResult Result = alias(MemLocI, InstrI, MemLocJ);
+      if (Result == MustAlias) {
+        OneAliasSet->addMemoryLocation(MemLocI);
+        if (FoundMustAlias != nullptr || CanNeverPromote) {
+          OneAliasSet->CanNeverPromote = true;
+          FoundMayAlias = true;
+          if (FoundMustAlias) {
+            FoundMustAlias->CanNeverPromote = true;
+          }
+        }
+        OneAliasSet->LoopInvariantAccess |= LoopInvariantAccess;
+        OneAliasSet->HasAGoodStore |= HasAGoodStore;
+        FoundMustAlias = OneAliasSet;
+        StoredDefs[Def] = FoundMustAlias;
+      }
+      if (Result == MayAlias) {
+        FoundMayAlias = true;
+        OneAliasSet->CanNeverPromote = true;
+        if (FoundMustAlias) {
+          FoundMustAlias->CanNeverPromote = true;
+        }
+      }
+    }
+
+    // Still need to add this to a new set
+    if (!FoundMustAlias && MemLocI != None) {
+      SingleMustAliasVec *newEntry = new SingleMustAliasVec(MemLocI.getValue());
+      newEntry->CanNeverPromote = CanNeverPromote || FoundMayAlias;
+      newEntry->LoopInvariantAccess = LoopInvariantAccess;
+      newEntry->HasAGoodStore = HasAGoodStore;
+      StoredDefs[Def] = newEntry;
+      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() { addToSets(DT->getNode(L->getHeader())); }
+
+  // Create all alias sets given a basic block (for testing)
+  void createSets(BasicBlock *B) { addToSets(DT->getNode(B)); }
+
+  void addToSets(DomTreeNode *N) {
+    // We want to visit parents before children. We will enque all the parents
+    // before their children in the worklist and process the worklist in order.
+    SmallVector<DomTreeNode *, 16> Worklist = collectChildrenInLoop(N, L);
+
+    for (DomTreeNode *DTN : Worklist) {
+      BasicBlock *BB = DTN->getBlock();
+      auto *Accesses = MSSA->getBlockAccesses(BB);
+      if (Accesses)
+        for (auto &Acc : make_range(Accesses->begin(), Accesses->end())) {
+          if (AllSets.size() > CAP_NO_ALIAS_SETS ||
+              MemorySSATraversalPenalty > CAP_MSSA_TRAVERSALS) {
+            AllSets.clear();
+            return;
+          }
+          // Process uses
+          const MemoryUse *Use = dyn_cast_or_null<MemoryUse>(&Acc);
+          if (Use)
+            addToAliasSets(Use);
+          // Process defs
+          const MemoryDef *Def = dyn_cast_or_null<MemoryDef>(&Acc);
+          if (Def)
+            addToAliasSets(Def);
+        }
+    }
+    // dbgs()<<"No sets: "<<AllSets.size()<<" and mssa penalty:
+    // "<<MemorySSATraversalPenalty<<"\n";  dump();
+  }
+
+  SmallSetVector<Value *, 8> *getSetIfPromotableOrNull(unsigned I) {
+    if (AllSets[I]->isGoodForPromotion()) {
+      SmallSetVector<Value *, 8> *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 &&
+            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

lib/Analysis/LoopAnalysisManager.cpp

 //===- LoopAnalysisManager.cpp - Loop analysis management -----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #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"
 
 using namespace llvm;
 
 // Explicit template instantiations and specialization defininitions for core
 // template typedefs.
bool LoopAnalysisManagerFunctionProxy::Result::invalidate(
   // to clear all the keys coming from that analysis. We also completely blow
   // away the loop analyses if any of the standard analyses provided by the
   // loop pass manager go away so that loop analyses can freely use these
   // without worrying about declaring dependencies on them etc.
   // FIXME: It isn't clear if this is the right tradeoff. We could instead make
   // 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;
+  // Only invalidate MSSA when used in LICM. Caveat: Building MSSA for nothing!
+  // The alternative: always invalidate MemorySSA, until all loop passes preserve it
+  // This alternative change will need to fix:
+  //    unittests/Scalar/ScalarTests/LoopPassManagerTest,
+  //    test/Transforms/LoopUnroll/unroll-loop-invalidation.ll and
+  //    test/Other/loop-pm-invalidation.ll
+  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
     // those results. Note that the order doesn't matter here as this will just
     // directly destroy the results without calling methods on them.
     for (Loop *L : PreOrderLoops)
       InnerAM->clear(*L);
 

 }
 
 PreservedAnalyses llvm::getLoopPassPreservedAnalyses() {
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   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>();
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
   PA.preserve<SCEVAA>();
   return PA;
 }

lib/Analysis/MemorySSA.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 #include <memory>
 #include <utility>
 
 using namespace llvm;
+bool llvm::EnableMSSALoopDep = false;
+bool llvm::UseLICMwMSSA = false;
 
 #define DEBUG_TYPE "memoryssa"
 
 INITIALIZE_PASS_BEGIN(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,
                       true)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(MemorySSAWrapperPass, "memoryssa", "Memory SSA", false,

lib/Transforms/Scalar/LICM.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
+#include "llvm/Transforms/Utils/MemorySSAAliasSets.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
 #include <utility>
 using namespace llvm;
 
 #define DEBUG_TYPE "licm"
 
 STATISTIC(NumSunk, "Number of instructions sunk out of loop");
static cl::opt<uint32_t> MaxNumUsesTraversed(
     "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
     cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 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,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 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() {
     return LoopToAliasSetMap;
   }
 
 private:
   DenseMap<Loop *, AliasSetTracker *> LoopToAliasSetMap;
 
   AliasSetTracker *collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
                                            AliasAnalysis *AA);
+  MemorySSAUpdater *MSSAUpdater = nullptr;
 };
 
 struct LegacyLICMPass : public LoopPass {
   static char ID; // Pass identification, replacement for typeid
   LegacyLICMPass() : LoopPass(ID) {
     initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L)) {
       // If we have run LICM on a previous loop but now we are skipping
       // (because we've hit the opt-bisect limit), we need to clear the
       // loop alias information.
       for (auto &LTAS : LICM.getLoopToAliasSetMap())
         delete LTAS.second;
       LICM.getLoopToAliasSetMap().clear();
       return false;
     }
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
     // pass.  Function analyses need to be preserved across loop transformations
     // but ORE cannot be preserved (see comment before the pass definition).
     OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
-    return LICM.runOnLoop(L,
-                          &getAnalysis<AAResultsWrapperPass>().getAAResults(),
-                          &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
-                          &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-                          &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
-                          SE ? &SE->getSE() : nullptr, &ORE, false);
+    return LICM.runOnLoop(
+        L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
+        SE ? &SE->getSE() : nullptr,
+        &getAnalysis<MemorySSAWrapperPass>().getMSSA(), &ORE, false);
   }
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG...
   ///
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addRequired<MemorySSAWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 
   using llvm::Pass::doFinalization;
 
   bool doFinalization() override {
     assert(LICM.getLoopToAliasSetMap().empty() &&
            "Didn't free loop alias sets");
PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
 
   auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
   // FIXME: This should probably be optional rather than required.
   if (!ORE)
     report_fatal_error("LICM: OptimizationRemarkEmitterAnalysis not "
                        "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 = UseLICMwMSSA ? (&AR.MSSA) : nullptr;
+  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.SE, MSSA, ORE,
+                      true))
     return PreservedAnalyses::all();
 
   auto PA = getLoopPassPreservedAnalyses();
   PA.preserveSet<CFGAnalyses>();
   return PA;
 }
 
 char LegacyLICMPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
                       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)
 
 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
 
 /// Hoist expressions out of the specified loop. Note, alias info for inner
 /// loop is not preserved so it is not a good idea to run LICM multiple
 /// times on one loop.
 /// We should delete AST for inner loops in the new pass manager to avoid
 /// memory leak.
 ///
 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();
 
   // Compute loop safety information.
   LoopSafetyInfo SafetyInfo;
   computeLoopSafetyInfo(&SafetyInfo, L);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   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.
   // Don't sink stores from loops without dedicated block exits. Exits
   // containing indirect branches are not transformed by loop simplify,
   // make sure we catch that. An additional load may be generated in the
   // preheader for SSA updater, so also avoid sinking when no preheader
   // is available.
if (!HasCatchSwitch) {
       InsertPts.reserve(ExitBlocks.size());
       for (BasicBlock *ExitBlock : ExitBlocks)
         InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
 
       PredIteratorCache PIC;
 
       bool Promoted = false;
 
+      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!");
 
           SmallSetVector<Value *, 8> PointerMustAliases;
           for (const auto &ASI : AS)
             PointerMustAliases.insert(ASI.getValue());
 
-        Promoted |= promoteLoopAccessesToScalars(PointerMustAliases, ExitBlocks,
-                                                 InsertPts, PIC, LI, DT, TLI, L,
-                                                 CurAST, &SafetyInfo, ORE);
+          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) {
+          SmallSetVector<Value *, 8> *MustAliasPtrs =
+              AS.getSetIfPromotableOrNull(I);
+          if (MustAliasPtrs) {
+            Promoted |= promoteLoopAccessesToScalars(
+                *MustAliasPtrs, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L,
+                CurAST, &AS, &SafetyInfo, ORE);
+          }
+        }
       }
 
       // Once we have promoted values across the loop body we have to
       // recursively reform LCSSA as any nested loop may now have values defined
       // within the loop used in the outer loop.
       // FIXME: This is really heavy handed. It would be a bit better to use an
       // SSAUpdater strategy during promotion that was LCSSA aware and reformed
       // it as it went.
       if (Promoted)
         formLCSSARecursively(*L, *DT, LI, SE);
 
       Changed |= Promoted;
     }
   }
 
   // Check that neither this loop nor its parent have had LCSSA broken. LICM is
   // specifically moving instructions across the loop boundary and so it is
   // especially in need of sanity checking here.
   assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
   assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
          "Parent loop not left in LCSSA form after LICM!");
 
+  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 MSSAUpdater;
 
   if (Changed && SE)
     SE->forgetLoopDispositions(L);
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in reverse depth
 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 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
   // before their children in the worklist and process the worklist in reverse
   // order.
   SmallVector<DomTreeNode *, 16> Worklist = collectChildrenInLoop(N, CurLoop);
 
   bool Changed = false;
   for (DomTreeNode *DTN : reverse(Worklist)) {
     BasicBlock *BB = DTN->getBlock();
     // Only need to process the contents of this block if it is not part of a
     // subloop (which would already have been processed).
     if (inSubLoop(BB, CurLoop, LI))
       continue;
 
     for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
       Instruction &I = *--II;
 
       // If the instruction is dead, we would try to sink it because it isn't
       // used in the loop, instead, just delete it.
       if (isInstructionTriviallyDead(&I, TLI)) {
         DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
         ++II;
+        if (CurAST)
           CurAST->deleteValue(&I);
+        if (MSSA)
+          removeFromMSSA(&I, MSSAUpdater, MSSA);
         I.eraseFromParent();
         Changed = true;
         continue;
       }
 
       // Check to see if we can sink this instruction to the exit blocks
       // of the loop.  We can do this if the all users of the instruction are
       // outside of the loop.  In this case, it doesn't even matter if the
       // 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);
       }
     }
   }
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 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
   // before their children in the worklist and process the worklist in order.
   SmallVector<DomTreeNode *, 16> Worklist = collectChildrenInLoop(N, CurLoop);
 
   bool Changed = false;
   for (DomTreeNode *DTN : Worklist) {
     BasicBlock *BB = DTN->getBlock();
     // Only need to process the contents of this block if it is not part of a
     // subloop (which would already have been processed).
     if (!inSubLoop(BB, CurLoop, LI))
       for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
         Instruction &I = *II++;
         // Try constant folding this instruction.  If all the operands are
         // constants, it is technically hoistable, but it would be better to
         // just fold it.
         if (Constant *C = ConstantFoldInstruction(
                 &I, I.getModule()->getDataLayout(), TLI)) {
           DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
+          if (CurAST)
             CurAST->copyValue(&I, C);
+          // TODO: update sets if built beforehand; otherwise, no-op
+          if (MSSA) {
+          }
           I.replaceAllUsesWith(C);
           if (isInstructionTriviallyDead(&I, TLI)) {
+            if (CurAST)
               CurAST->deleteValue(&I);
+            if (MSSA)
+              removeFromMSSA(&I, MSSAUpdater, MSSA);
             I.eraseFromParent();
           }
           Changed = true;
           continue;
         }
 
         // Attempt to remove floating point division out of the loop by
         // converting it to a reciprocal multiplication.
         if (I.getOpcode() == Instruction::FDiv &&
             CurLoop->isLoopInvariant(I.getOperand(1)) &&
             I.hasAllowReciprocal()) {
           auto Divisor = I.getOperand(1);
           auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
           auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
           ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
           ReciprocalDivisor->insertBefore(&I);
 
           auto Product =
               BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
           Product->setFastMathFlags(I.getFastMathFlags());
           Product->insertAfter(&I);
           I.replaceAllUsesWith(Product);
           I.eraseFromParent();
 
-          hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
+          hoist(*ReciprocalDivisor, DT, CurLoop, MSSAUpdater, MSSA, SafetyInfo,
+                ORE);
           Changed = true;
           continue;
         }
 
         // Try hoisting the instruction out to the preheader.  We can only do
         // this if all of the operands of the instruction are loop invariant and
         // 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);
       }
   }
 
   return Changed;
 }
 
 /// Computes loop safety information, checks loop body & header
 /// for the possibility of may throw exception.
if (LocSizeInBits <= InvariantSizeInBits &&
       return true;
   }
 
   return false;
 }
 
 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.
   if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     if (!LI->isUnordered())
       return false; // Don't hoist volatile/atomic loads!
 
     // Loads from constant memory are always safe to move, even if they end up
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     // Don't hoist loads which have may-aliased stores in loop.
     uint64_t Size = 0;
     if (LI->getType()->isSized())
       Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
 
     AAMDNodes AAInfo;
     LI->getAAMetadata(AAInfo);
 
-    bool Invalidated =
+    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()))
       ORE->emit(OptimizationRemarkMissed(
                     DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
                 << "failed to move load with loop-invariant address "
                    "because the loop may invalidate its value");
 
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
     if (Behavior == FMRB_DoesNotAccessMemory)
       return true;
     if (AliasAnalysis::onlyReadsMemory(Behavior)) {
       // A readonly argmemonly function only reads from memory pointed to by
       // 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;
+      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)
         return true;
     }
 
     // FIXME: This should use mod/ref information to see if we can hoist or
     // sink the call.
 
     return false;
for (const User *U : I.users()) {
     if (CurLoop->contains(UI))
       return false;
   }
   return true;
 }
 
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
+                            MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                             const LoopInfo *LI,
                             const LoopSafetyInfo *SafetyInfo) {
   Instruction *New;
   if (auto *CI = dyn_cast<CallInst>(&I)) {
     const auto &BlockColors = SafetyInfo->BlockColors;
 
     // Sinking call-sites need to be handled differently from other
     // instructions.  The cloned call-site needs a funclet bundle operand
CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
   } else {
     New = I.clone();
   }
 
   ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
   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.
   // OPT: If this shows up in a profile, we can instead finish sinking all
   // invariant instructions, and then walk their operands to re-establish
   // LCSSA. That will eliminate creating PHI nodes just to nuke them when
   // sinking bottom-up.
   for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;

 
 /// When an instruction is found to only be used outside of the loop, this
 /// function moves it to the exit blocks and patches up SSA form as needed.
 /// This method is guaranteed to remove the original instruction from its
 /// position, and may either delete it or move it to outside of the loop.
 ///
 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");
   ORE->emit(OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
             << "sinking " << ore::NV("Inst", &I));
   bool Changed = false;
   if (isa<LoadInst>(I))
     ++NumMovedLoads;
while (!I.use_empty()) {
     assert(ExitBlockSet.count(ExitBlock) &&
            "The LCSSA PHI is not in an exit block!");
 
     Instruction *New;
     auto It = SunkCopies.find(ExitBlock);
     if (It != SunkCopies.end())
       New = It->second;
     else
-      New = SunkCopies[ExitBlock] =
-          CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
+      New = SunkCopies[ExitBlock] = CloneInstructionInExitBlock(
+          I, *ExitBlock, *PN, MSSAUpdater, MSSA, LI, SafetyInfo);
 
     PN->replaceAllUsesWith(New);
     PN->eraseFromParent();
   }
 
+  if (CurAST)
     CurAST->deleteValue(&I);
+  if (MSSA)
+    removeFromMSSA(&I, MSSAUpdater, MSSA);
   I.eraseFromParent();
   return Changed;
 }
 
 /// When an instruction is found to only use loop invariant operands that
 /// 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();
   DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
                << "\n");
   ORE->emit(OptimizationRemark(DEBUG_TYPE, "Hoisted", &I)
             << "hoisting " << ore::NV("Inst", &I));
 
   // Metadata can be dependent on conditions we are hoisting above.
   // Conservatively strip all metadata on the instruction unless we were
   // guaranteed to execute I if we entered the loop, in which case the metadata
   // is valid in the loop preheader.
   if (I.hasMetadataOtherThanDebugLoc() &&
       // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
       // time in isGuaranteedToExecute if we don't actually have anything to
       // drop.  It is a compile time optimization, not required for correctness.
       !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
     I.dropUnknownNonDebugMetadata();
 
   // 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,
   // need to retain their debug locs because they may be inlined.
   // FIXME: How do we retain source locations without causing poor debugging
   // behavior?
   if (!isa<CallInst>(I))
     I.setDebugLoc(DebugLoc());

 
 namespace {
 class LoopPromoter : public LoadAndStorePromoter {
   Value *SomePtr; // Designated pointer to store to.
   const SmallSetVector<Value *, 8> &PointerMustAliases;
   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;
   bool UnorderedAtomic;
   AAMDNodes AATags;
 
   Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
     if (Instruction *I = dyn_cast<Instruction>(V))
Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
     return V;
   }
 
 public:
   LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
                const SmallSetVector<Value *, 8> &PMA,
                SmallVectorImpl<BasicBlock *> &LEB,
                SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
-               AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
-               bool UnorderedAtomic, const AAMDNodes &AATags)
+               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),
+        AS(as), LI(li), DL(std::move(dl)), Alignment(alignment),
         UnorderedAtomic(UnorderedAtomic), AATags(AATags) {}
 
   bool isInstInList(Instruction *I,
                     const SmallVectorImpl<Instruction *> &) const override {
     Value *Ptr;
     if (LoadInst *LI = dyn_cast<LoadInst>(I))
       Ptr = LI->getOperand(0);
     else
for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
       Instruction *InsertPos = LoopInsertPts[i];
       StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
       if (UnorderedAtomic)
         NewSI->setOrdering(AtomicOrdering::Unordered);
       NewSI->setAlignment(Alignment);
       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); }
 };
 } // namespace
 
 /// Try to promote memory values to scalars by sinking stores out of the
 /// loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
 ///
 bool llvm::promoteLoopAccessesToScalars(
     const SmallSetVector<Value *, 8> &PointerMustAliases,
     SmallVectorImpl<BasicBlock *> &ExitBlocks,
     SmallVectorImpl<Instruction *> &InsertPts, PredIteratorCache &PIC,
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
-    Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
-    OptimizationRemarkEmitter *ORE) {
+    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();
 
   // It isn't safe to promote a load/store from the loop if the load/store is
   // conditional.  For example, turning:
   //
   //    for () { if (c) *P += 1; }
bool llvm::promoteLoopAccessesToScalars(
   // this code just arbitrarily picks a location from one, since any debug
   // location is better than none.
   DebugLoc DL = LoopUses[0]->getDebugLoc();
 
   // We use the SSAUpdater interface to insert phi nodes as required.
   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
   // value from the preheader that uses in the loop will use.
   LoadInst *PreheaderLoad = new LoadInst(
       SomePtr, SomePtr->getName() + ".promoted", Preheader->getTerminator());
   if (SawUnorderedAtomic)
     PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
   PreheaderLoad->setAlignment(Alignment);
   PreheaderLoad->setDebugLoc(DL);
   if (AATags)
     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;
 }
 
 /// Returns an owning pointer to an alias set which incorporates aliasing info
 /// from L and all subloops of L.
 /// FIXME: In new pass manager, there is no helper function to handle loop
 /// analysis such as cloneBasicBlockAnalysis, so the AST needs to be recomputed

 ///
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST) {
   // Check to see if any of the basic blocks in CurLoop invalidate *V.
   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.
 ///
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
   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);
+  }
+}

lib/Transforms/Scalar/LoopDistribute.cpp

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #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"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
PreservedAnalyses LoopDistributePass::run(Function &F,
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
 
   // We don't directly need these analyses but they're required for loop
   // analyses so provide them below.
   auto &AA = AM.getResult<AAManager>(F);
   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);
   };
 
   bool Changed = runImpl(F, &LI, &DT, &SE, &ORE, GetLAA);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<LoopAnalysis>();

lib/Transforms/Scalar/LoopLoadElimination.cpp

 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #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"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
PreservedAnalyses LoopLoadEliminationPass::run(Function &F,
                                                FunctionAnalysisManager &AM) {
   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
   auto &LI = AM.getResult<LoopAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   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);
       });
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   return PA;
 }
 
 } // end namespace llvm

lib/Transforms/Scalar/LoopSink.cpp

static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
   // Traverse preheader's instructions in reverse order becaue if A depends
   // on B (A appears after B), A needs to be sinked first before B can be
   // sinked.
   for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
     Instruction *I = &*II++;
     // 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;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   return Changed;

lib/Transforms/Utils/LoopUtils.cpp

if (Name.equals(S->getString()))
       }
   }
   return None;
 }
 
 /// Does a BFS from a given node to all of its children inside a given loop.
 /// The returned vector of nodes includes the starting point.
 SmallVector<DomTreeNode *, 16>
-llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
+llvm::collectChildrenInLoop(DomTreeNode *N, Loop *CurLoop) {
   SmallVector<DomTreeNode *, 16> Worklist;
   auto AddRegionToWorklist = [&](DomTreeNode *DTN) {
     // Only include subregions in the top level loop.
     BasicBlock *BB = DTN->getBlock();
-    if (CurLoop->contains(BB))
+    if (!CurLoop || CurLoop->contains(BB))
       Worklist.push_back(DTN);
   };
 
   AddRegionToWorklist(N);
 
   for (size_t I = 0; I < Worklist.size(); I++)
     for (DomTreeNode *Child : Worklist[I]->getChildren())
       AddRegionToWorklist(Child);

lib/Transforms/Vectorize/LoopVectorize.cpp

PreservedAnalyses LoopVectorizePass::run(Function &F,
     auto &TTI = AM.getResult<TargetIRAnalysis>(F);
     auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
     auto &BFI = AM.getResult<BlockFrequencyAnalysis>(F);
     auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
     auto &AA = AM.getResult<AAManager>(F);
     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 =
         runImpl(F, SE, LI, TTI, DT, BFI, &TLI, DB, AA, AC, GetLAA, ORE);
     if (!Changed)
       return PreservedAnalyses::all();
     PreservedAnalyses PA;
     PA.preserve<LoopAnalysis>();
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<BasicAA>();
     PA.preserve<GlobalsAA>();
     return PA;
 }

test/Other/loop-pm-invalidation.ll

 ; CHECK-LOOP-INV-LABEL: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on one_loop
 ; CHECK-LOOP-INV-NEXT: Running analysis: LoopAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-LOOP-INV-NEXT: Finished {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}LoopAnalysis
 ; CHECK-LOOP-INV-NEXT: Invalidating all non-preserved analyses
 ; CHECK-LOOP-INV-NEXT: Clearing all analysis results for: l0.header
 ; CHECK-LOOP-INV-NEXT: Invalidating analysis: LoopAnalysis

 ; CHECK-SCEV-INV-LABEL: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on one_loop
 ; CHECK-SCEV-INV-NEXT: Running analysis: LoopAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-SCEV-INV-NEXT: Finished {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}ScalarEvolutionAnalysis
 ; CHECK-SCEV-INV-NEXT: Invalidating all non-preserved analyses
 ; CHECK-SCEV-INV-NEXT: Clearing all analysis results for: l0.header
 ; CHECK-SCEV-INV-NEXT: Invalidating analysis: ScalarEvolutionAnalysis

 ; CHECK-LOOP-INV-LABEL: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on nested_loops
 ; CHECK-LOOP-INV-NEXT: Running analysis: LoopAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-LOOP-INV-NEXT: Finished {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Running pass: NoOpLoopPass
 ; CHECK-LOOP-INV: Finished {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}LoopAnalysis

 ; CHECK-SCEV-INV-LABEL: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on nested_loops
 ; CHECK-SCEV-INV-NEXT: Running analysis: LoopAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-SCEV-INV-NEXT: Finished {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Starting {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Running pass: NoOpLoopPass
 ; CHECK-SCEV-INV: Finished {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}ScalarEvolutionAnalysis

 ; CHECK-LOOP-INV-LABEL: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on dead_loop
 ; CHECK-LOOP-INV-NEXT: Running analysis: LoopAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-LOOP-INV-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-LOOP-INV-NEXT: Finished {{.*}}Loop pass manager run.
 ; CHECK-LOOP-INV-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}LoopAnalysis
 ; CHECK-LOOP-INV-NEXT: Invalidating all non-preserved analyses
 ; CHECK-LOOP-INV-NEXT: Clearing all analysis results for: l0.header
 ; CHECK-LOOP-INV-NEXT: Invalidating analysis: LoopAnalysis

 ; CHECK-SCEV-INV-LABEL: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on dead_loop
 ; CHECK-SCEV-INV-NEXT: Running analysis: LoopAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-SCEV-INV-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-SCEV-INV-NEXT: Finished {{.*}}Loop pass manager run.
 ; CHECK-SCEV-INV-NEXT: Running pass: InvalidateAnalysisPass<{{.*}}ScalarEvolutionAnalysis
 ; CHECK-SCEV-INV-NEXT: Invalidating all non-preserved analyses
 ; CHECK-SCEV-INV-NEXT: Clearing all analysis results for: l0.header
 ; CHECK-SCEV-INV-NEXT: Invalidating analysis: ScalarEvolutionAnalysis

 ; CHECK-SCEV-INV-AFTER-DELETE-LABEL: Running pass: FunctionToLoopPassAdaptor<{{.*}}> on dead_loop
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: LoopAnalysis
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-SCEV-INV-AFTER-DELETE-NEXT: Running pass: LoopDeletionPass
 ; 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: 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.
 
 entry:
   br label %l0.header
 
 l0.header:
   br i1 false, label %l0.header, label %exit
 
 exit:
   ret void
 }

test/Other/new-pass-manager.ll

 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Invalidating all non-preserved analyses
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: AAManager
 ; 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
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Starting Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running pass: NoOpLoopPass
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Finished Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Starting Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running pass: NoOpLoopPass

test/Other/pass-pipelines.ll

 ; CHECK-O2-NEXT: Remove unused exception handling info
 ; CHECK-O2-NEXT: Function Integration/Inlining
 ; CHECK-O2-NEXT: Deduce function attributes
 ; Next up is the main function pass pipeline. It shouldn't be split up and
 ; should contain the main loop pass pipeline as well.
 ; 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.
 ; CHECK-O2: Simplify the CFG
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Combine redundant instructions
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager

unittests/Transforms/Scalar/LoopPassManagerTest.cpp

LoopPassManagerTest()
 
     // We need DominatorTreeAnalysis for LoopAnalysis.
     FAM.registerPass([&] { return DominatorTreeAnalysis(); });
     FAM.registerPass([&] { return LoopAnalysis(); });
     // We also allow loop passes to assume a set of other analyses and so need
     // 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(); });
 
     // Cross-register proxies.
     LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); });
     FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); });
     FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });