Use MemorySSA in LICM to do sinking and hoisting.

[asbirlea]

Summary

Step 2 in using MemorySSA in LICM:
Use MemorySSA in LICM to do sinking and hoisting, all under "EnableMSSALoopDependency" flag.
Promotion is disabled.

Enable flag in LICM sink/hoist tests to test correctness of this change. Moved one test which
relied on promotion, in order to test all sinking tests.

[asbirlea]

Gentle ping!

Note this is still NFC since flag to enable use of MemorySSA remains disabled during this transition.
However I enabled testing to maintain correctness.

[sanjoy]

Initial round of comments.

lib/Transforms/Scalar/LICM.cpp

162

Can this be an std::unique_ptr?

And why is it on the class as opposed to being a stack variable in runOnLoop like CurAST?

295

This seems unnecessary.

730–737

Probably better to leave this un-initialized; that way the compiler will warn if we forget to initialize it in one branch. You could also use a ternary here.

798

This can probably be a single llvm::any_of on CurLoop->blocks().

1789

How about call it isVolatileLoadOrLiveOnEntry?

1791

The usual idiom I've seen for this is:

if (!Processed.insert(Acc).second)
  return false;

1792

Should we be returning true in this recursive case? IE if we have a MemoryPhi that has one of its inputs as itself and the other input as live-on-entry then shouldn't that be equivalent to just a live-on-entry?

1798

I'd avoid testing for MemoryDef early -- instead I'd suggest doing this as:

if (auto *Phi = dyn_cast_or_null<MemoryPhi>(Acc)) {
} else if (auto *Def = dyn_cast_or_null<MemoryDef>(Acc)) {
}

1802

How about a range for on Phi->operands()? Or even better -- return llvm::all_of(Phi->operands(), <lambda>);

1809

Is this correct even if defining access for Def is a store in the loop?

1820

LLVM style is avoiding braces for one liners. You could also fold the assignment into the condition, like if (MemoryUseOrDef *AccI = ...)

1824

This can just be if (MemoryUse *MU = dyn_cast_or_null<MemoryUse>(MUD))

1841

s/if/If/

1842

This seems fishy -- if volatile loads do not invalidate pointers then why are they treated as defs by MSSA?

lib/Transforms/Scalar/LoopSink.cpp

301

How about adding /*MemorySSAUpdater=*/nullptr etc. here?

[asbirlea]

Address comments.

lib/Transforms/Scalar/LICM.cpp

1791

Code in question removed.

1792

Right, but code in question removed.

1802

If using Phi->operands() I need to re-add the conversion from Use to MemoryAccess hidden in the macro in getIncomingValue().
New code would be:

return llvm::all_of(Phi->operands(), [MSSA, &Processed](const Use &Arg) {           
      return isVolatileLoadOrLiveOnEntry(
          cast_or_null<MemoryAccess>(Arg.get()), MSSA, Processed);                      
    });

Does this look better than existing?

Scratch that, code in question removed.

1809

Code updated, see comment below.

1842

Well, because they should be treated as defs. Motivation for special casing this was test/Transforms/LICM/volatile-alias.ll.
I updated the code to no longer consider volatile loads acceptable, meaning test in question will fail. And I believe that's the right thing.

[sanjoy]

Some of the comments inline may be naive since I'm not very familiar with MemorySSA.

lib/Transforms/Scalar/LICM.cpp

405

Can this be a std::unique_ptr?

422

Should this assert be checking CurAST != nullptr ^ (MSSAUpdater != nullptr && MSSA != nullptr)?

775

Minor nit: I usually prefer leaving variables like Invalidated uninitialized; that way if I forget to assign to it on one branch of the if I'll get a warning and/or an ASan failure.

782

We should probably early exit if !Op->getType()->isPointerTy() (and assert Op->getType()->isPointerTy() in pointerInvalidatedByLoopWithMSSA etc.

790–791

Minor nit: even though unnecessary, I'd prefer using braces here since for readability.

972

I'm not sure that setting the defining access to nullptr here is correct -- if there is some subtle reason why it is, please add a comment.

974

Instead of two dyn_cast_or_nulls how about:

if (NewMemAcc) {
  if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc)) {
    ...
  } else {
    auto *MemUse = cast<MemoryUse>(NewMemAcc);
  }
}

?

976

I'd prefer /*RenameUses=*/true.

982

I'm not clear on how this works -- IIUC you're calling into getClobberingMemoryAccess with NewMemUse's DefiningAccess set to nullptr, but:

• Why don't we have to do this for MemoryDefs?
• What if MSSA->getWalker() is a DoNothingMemorySSAWalker?
• There are places where we should be crashing, like: CachingWalker::getClobberingMemoryAccess line 2078 that calls getClobberingMemoryAccess(DefiningAccess, Q) that calls ClobberWalker::findWalker which has if (auto *MU = dyn_cast<MemoryUse>(Start)).

1249–1250

Can this be cast_or_null?

1803

Stray comment?

1806

Minor nit: probably cleaner to use if (MSSA->isLiveOnEntryDef(Source) || !CurLoop->contains(Source->getBlock())) here.

[asbirlea]

Comments.

[asbirlea]

lib/Transforms/Scalar/LICM.cpp

422

At some point I was testing with both enabled, but considering the added compile time when doing that, yes :).

982

AFAIU:
For Defs the DefiningAccess is properly updated.
For Uses, there is a DefiningAccess set, but that one is not optimized. When adding an access like in this case, calling getClobberingMemoryAccess will optimize it.
If the walker is DoNothingMemorySSAWalker, it won't optimize?

Pulling in george.burgess.iv to clarify, it's possible I'm missing something here.

[george.burgess.iv]

Only looked at the bit I was mentioned in.

lib/Transforms/Scalar/LICM.cpp

982

IIUC you're calling into getClobberingMemoryAccess with NewMemUse's DefiningAccess set to nullptr

I'm assuming you meant MemUse, in which case insertUse sets up the defining access to something non-null.

It's sort of sketchy that we're trying to eagerly update the defining access using the walker, though. Is there a reason that we can't call MSSA->getWalker()->getClobberingMemoryAccess(MemUse); when we need optimized clobbers? Doing so should be incredibly cheap when the use has already been optimized, and it lets us be lazy about the work we do (if we don't need an accurate clobber for MemUse, we'll just never compute it)

[asbirlea]

lib/Transforms/Scalar/LICM.cpp

982

I'm assuming you meant MemUse, in which case insertUse sets up the defining access to something non-null.

Thanks for clarifying this.

It's sort of sketchy that we're trying to eagerly update the defining access using the walker, though. Is there a reason that we can't call MSSA->getWalker()->getClobberingMemoryAccess(MemUse); when we need optimized clobbers? Doing so should be incredibly cheap when the use has already been optimized, and it lets us be lazy about the work we do (if we don't need an accurate clobber for MemUse, we'll just never compute it)

The reasoning here is that when making code changes such as hoist/sink, I need accesses to be (reasonably) optimized. I'm not necessarily to looking to get full precision here, I'd be perfectly happy with an API to optimize up to the MemorySSA optimize-uses cap.
In LICM.cpp:1652 (and in the future for promotion) I'm relying on getting the defining access, not the walker->clobbering access, allowing for some imprecision in exchange for not paying the lookup time for blocks with large load/store count.
I had come across a case where after a hoist or sink, this approach did not work for a very small testcase without using the walker to get clobbering.
So the choice I made was to use the walker ahead of time to update accesses I insert when cloning, allowing me to use getDefining afterwards.

Hopefully I clarified the intention here :). Do you think there's a better way to address this problem? I'm open to suggestions.

@dberlin

So, this use renaming is expensive, and i'd like to understand the goal (It requires walking all stores and loads in the dominator subtree rooted at your memory access) It's really meant for when you've inserted defs that may alias existing uses.
If your goal is to replace all uses of an old memory access with some new memoryaccess, you want to use the replace API :)

The code here is creating a new memory access to handle cloning an access in all exit blocks, where that access may alias existing uses, so I think using the replace API isn't enough.
Please let me know if there is a way to handle this differently.

[asbirlea]

Gentle ping.

[asbirlea]

Add a flag for the decision of using getDefining vs Walker->getClobbering, for optimizing pathological cases.

[lebedev.ri]

test/Transforms/LICM/sinking.ll

363

But there is no sink-promote.ll in this differential?
Is that in some other patch?

[asbirlea]

Added sink-promote.ll. Thanks for catching this!

[george.burgess.iv]

lib/Transforms/Scalar/LICM.cpp

982

(To be clear: the addition of the flag resolved my MemorySSA comments. While it's sort of hacky that we need to have it in the first place, the best place to handle "this {block,function} is pathologically big; let's give up instead of taking forever to walk it, and rewalk it, and rewalk it, and ..." is in MSSA, IMO. Until we make MSSA smart enough to actually do that, though, a targeted escape hatch seems like the best way forward to me.)

[asbirlea]

Thanks George, marking as Done. Also note that the optimization enables by this flag remains disabled.

Other reviewers: please let me know if there are remaining issues or concerns.
Please note that the use of MemorySSA remains disabled with this patch.

[sanjoy]

lib/Transforms/Scalar/LICM.cpp

1

Stray edit?

101

Line too long?

422

Probably better to have two asserts here:

• assert((MSSAUpdater == nullptr) == (MSSA == nullptr))
• assert((CurAST != nullptr) ^ (MSSA != nullptr))

980

Note: I did not revisit this bit since it looks like @george.burgess.iv settled it.

1255

I not convinced this is a good idea -- it looks like we're coding to the implementation of getClobberingMemoryAccess here instead of coding to its interface. But if @george.burgess.iv is fine with it, I am too.

1255

It looks like MemorySSA::CachingWalker::getClobberingMemoryAccess has an early exit if OldMemAcc was optimized. Are we okay not updating the defining access in that case?

1795

If MUD is always guaranteed to be a use then this should be cast_or_null. Otherwise please update the comment.

[asbirlea]

Address comments.

[asbirlea]

lib/Transforms/Scalar/LICM.cpp

1255

If it's been optimized, then the defining access should have been updated, and viceversa.
@george.burgess.iv: Could you clarify this please? I don't see resetOptimized being called on any path for the call chain starting with moreToPlace->insertDef, though it would make sense for this to happen. Am I missing something here?

[george.burgess.iv]

lib/Transforms/Scalar/LICM.cpp

1255

I not convinced this is a good idea -- it looks like we're coding to the implementation of getClobberingMemoryAccess here instead of coding to its interface. But if @george.burgess.iv is fine with it, I am too

In general, I agree, but Walkers are a sticky concept. The model we've sold people is "always call getWalker()->getClobberingMemoryAddress(MA) if you need the optimized access; the walker will handle making repeated calls fast," and we're specifically calling this on MSSA->getWalker().

I'll try to find a way to structure MSSA so that this guarantee is more obvious.

Am I missing something here?

Our theoretical isOptimized bit depends on two things: being flipped by a call to setOptimized, and either our defining access or optimized access having the same ID as it did when setOptimized was called. (...It also depends on stores not appearing out of thin air ;) )

So, when you move a Def, all Uses are implicitly invalided by the replaceAllUsesWith (since their defining access no longer has the same ID as before), and the Def's cached clobber is invalidated when you call setDefiningAccess on it.

Similarly, when you move a Use, we just set its defining access to whatever's closest. So, its cache will be invalidated (or not, if you move it right under its old clobber. But then the optimized use is still correct).

What I'm unsure about is what happens what happens to Defs optimized to a Def when said optimized-to Def is moved. I feel like I asked this during the original reviews for the caching/updater stuff, but I don't remember the answer. I'll do archaeology and get back to you. :)

(If the Def/Def case is uninteresting to this pass, feel free to not block this patch on my search)

[george.burgess.iv]

lib/Transforms/Scalar/LICM.cpp

1255

OK, so assuming the fixes stick, https://bugs.llvm.org/show_bug.cgi?id=36529 should fix any def/def craziness we may see here.

Moving things around above the defs should also be fine, since if you have a Def A which has an "optimized" clobber B and you add a clobber between them, that sounds like a functional change (or, if nothing can observe that clobber, a waste of CPU time ;) ). Similarly, if B is moved such that a pre-existing clobber should become A's clobber, that sounds like a functional change.

I think this resolves all the questions. Please let me know if not.

[asbirlea]

Thank you for the fix, George. Yes, I think all issue are addressed now.

[asbirlea]

Rebase and ping.

[asbirlea]

Rebase patch after resect changes.

Updates:
Change test sink-promote due to PR38989.
Sink is incomplete with MSSA due to recent changes, added TODO and will extend in separate patch.

[asbirlea]

Cleaned up after a series of MemorySSA updates, and rebased with ToT changes.

[sanjoy]

I didn't carefully review the MSSA specific stuff since you're the domain expert here. I do have some general comments.

lib/Transforms/Scalar/LICM.cpp

102

Not sure if it is beneficial to split out a separate [Verbose] section -- maybe we can combine both into a large single comment?

116

Just to be clear, if this is true then opt -licm -some_pass_using_mssa is not the same as opt -licm | opt -some_pass_using_mssa? If yes, that needs to be explicitly (and loudly) mentioned.

478–479

Just to be clear, we don't have to tell MSSAU about these new blocks (and the edges between these new blocks)?

667

Update comment?

698

So if there is a memory phi then it has to be Acc->begin()?

Btw, it might be cleaner to express this as a loop:

int nonphi = 0;
for (auto *X : *Acc) {
  if (is_phi) { continue; }
  if (X->getInst() != I || nonphi++ == 1) { return false; }
}
return true;

816

Can be return isOnlyMemoryAccess(FI, CurLoop, MSSAU).

[asbirlea]

Address comments.

[asbirlea]

I also cleaned up the usage of EnableLicmCap. It is only used in 2 places now, with no forced calls to getClobbering (the issue in MemorySSA requiring this is now resolved).
FWIW, I'm planning to replace this with an integer cap in a future patch (i.e. allow a limited number of calls to getClobbering, vs all or none like we have now).

lib/Transforms/Scalar/LICM.cpp

116

Hmm, let me think this out loud.

If the flag is true, there may be more opportunities for sink/hoist found at the cost of compile time, so the end result (module) may be different. But the users of the resulting MemorySSA should not be affected by the flag being true or false.

There may be more things already optimized in MemorySSA with the flag set to false.
And more things to be optimized on demand with the flag set to true.
So printing MemorySSA after LICM may have differences.
But the pass running after LICM should get the same results to MemorySSA clobbering queries.

Does this make sense?

478–479

MSSAU doesn't keep track of blocks with no memory accesses. This code if just duplicating the control flow from inside the loop to outside the loop. MSSAU only starts caring when instructions that touch memory are moved in there.

It also matters that the correct block predecessors are included in MemoryPhis, so when control flow changes to modify that, we need to update MSSA. The 3 lines below address this.

698

Yes, a block may have a single MemoryPhi, and it's always the first one in the list of Defs.

SG! Updated with loop.

[sanjoy]

lgtm

include/llvm/Analysis/MemorySSAUpdater.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFGDiff.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Type.h"

include/llvm/Transforms/Utils/LoopUtils.h

 namespace llvm {
 
 class AliasSet;
 class AliasSetTracker;
 class BasicBlock;
 class DataLayout;
 class Loop;
 class LoopInfo;
+class MemorySSAUpdater;
 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 *, TargetTransformInfo *, Loop *,
-                AliasSetTracker *, LoopSafetyInfo *,
+                AliasSetTracker *, MemorySSAUpdater *, LoopSafetyInfo *,
                 OptimizationRemarkEmitter *ORE);
 
 /// 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 *, LoopSafetyInfo *,
+                 OptimizationRemarkEmitter *ORE);
 
 /// This function deletes dead loops. The caller of this function needs to
 /// guarantee that the loop is infact dead.
 /// The function requires a bunch or prerequisites to be present:
 ///   - The loop needs to be in LCSSA form
 ///   - The loop needs to have a Preheader
 ///   - A unique dedicated exit block must exist
 ///

 /// do efficiently from within this routine.
 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
 /// target executes at most once per execution of the loop body.  This is used
 /// to assess the legality of duplicating atomic loads.  Generally, this is
 /// true when moving out of loop and not true when moving into loops.
 /// If \p ORE is set use it to emit optimization remarks.
 bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                         Loop *CurLoop, AliasSetTracker *CurAST,
-                        bool TargetExecutesOncePerLoop,
+                        MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop,
                         OptimizationRemarkEmitter *ORE = nullptr);
 
 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 Value *createMinMaxOp(IRBuilder<> &Builder,
                       RecurrenceDescriptor::MinMaxRecurrenceKind RK,
                       Value *Left, Value *Right);
 
 /// Generates an ordered vector reduction using extracts to reduce the value.

lib/Transforms/Scalar/LICM.cpp

 //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //

 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GuardUtils.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/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Transforms/Utils/Local.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/PatternMatch.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/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
 #include <utility>
 using namespace llvm;
 
 #define DEBUG_TYPE "licm"
 
cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
 // Default value of zero implies we use the regular alias set tracker mechanism
 // instead of the cross product using AA to identify aliasing of the memory
 // location we are interested in.
 static cl::opt<int>
 LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0),
                cl::desc("How many instruction to cross product using AA"));
 
+// Experimental option to allow imprecision in LICM (use MemorySSA cap) in
+// pathological cases, in exchange for faster compile. This is to be removed
+// if MemorySSA starts to address the same issue.
+
+// [Verbose] This flag applies only when LICM uses MemorySSA instead on
+// AliasSetTracker.
+// When flag is disabled (default), LICM calls MemorySSAWalker's
+// getClobberingMemoryAccess, which gets perfect accuracy. When flag is enabled,
+// LICM will call into MemorySSA's getDefiningAccess, which may not be precise,
+// since optimizeUses is capped. This means that doing sink, hoist and promotion
+// will not incur a performance penalty for loops with large load and store
+// count. For the updates done by sink/hoist/promotion (insertUse, moveToPlace),
+// we will need to *explicitly* call getClobberingMemoryAccesses. This will get
+// perfect results for small tests, and imprecise but fast for large ones.
+static cl::opt<bool> EnableLicmCap(
+    "enable-licm-cap", cl::init(false), cl::Hidden,
+    cl::desc("Enable imprecision in LICM (uses MemorySSA cap) in "
+             "pathological cases, in exchange for faster compile"));
+
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
                                   const LoopSafetyInfo *SafetyInfo,
                                   TargetTransformInfo *TTI, bool &FreeInLoop);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
-                  LoopSafetyInfo *SafetyInfo,
+                  LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
-                 OptimizationRemarkEmitter *ORE, bool FreeInLoop);
+                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE,
+                 bool FreeInLoop);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
                                      AliasSetTracker *CurAST, Loop *CurLoop,
                                      AliasAnalysis *AA);
-
-static Instruction *
-CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
-                            const LoopInfo *LI,
-                            const LoopSafetyInfo *SafetyInfo);
+static bool pointerInvalidatedByLoopWithMSSA(Value *V, MemorySSA *MSSA,
+                                             MemoryUseOrDef *MUD,
+                                             Loop *CurLoop);
+static void removeFromAnalyses(Instruction *I, AliasSetTracker *CurAST,
+                               MemorySSAUpdater *MSSAU);
+static Instruction *CloneInstructionInExitBlock(
+    Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
+    const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU);
 
 namespace {
 struct LoopInvariantCodeMotion {
   using ASTrackerMapTy = DenseMap<Loop *, std::unique_ptr<AliasSetTracker>>;
   bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
                  TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
                  ScalarEvolution *SE, MemorySSA *MSSA,
                  OptimizationRemarkEmitter *ORE, bool DeleteAST);
 
   ASTrackerMapTy &getLoopToAliasSetMap() { return LoopToAliasSetMap; }
 
 private:
   ASTrackerMapTy LoopToAliasSetMap;
 
   std::unique_ptr<AliasSetTracker>
   collectAliasInfoForLoop(Loop *L, LoopInfo *LI, AliasAnalysis *AA);
 };
 
 struct LegacyLICMPass : public LoopPass {
   static char ID; // Pass identification, replacement for typeid
   LegacyLICMPass() : LoopPass(ID) {
     initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());

 bool LoopInvariantCodeMotion::runOnLoop(
     Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
     TargetLibraryInfo *TLI, TargetTransformInfo *TTI, ScalarEvolution *SE,
     MemorySSA *MSSA, OptimizationRemarkEmitter *ORE, bool DeleteAST) {
   bool Changed = false;
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
-  std::unique_ptr<AliasSetTracker> CurAST = collectAliasInfoForLoop(L, LI, AA);
+  std::unique_ptr<AliasSetTracker> CurAST;
+  std::unique_ptr<MemorySSAUpdater> MSSAU;
+  if (!MSSA) {
+    LLVM_DEBUG(dbgs() << "LICM: Using Alias Set Tracker.\n");
+    CurAST = collectAliasInfoForLoop(L, LI, AA);
+  } else {
+    LLVM_DEBUG(dbgs() << "LICM: Using MemorySSA. Promotion disabled.\n");
+    MSSAU = make_unique<MemorySSAUpdater>(MSSA);
+  }
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Compute loop safety information.
   LoopSafetyInfo SafetyInfo;
   SafetyInfo.computeLoopSafetyInfo(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, TTI, L,
-                          CurAST.get(), &SafetyInfo, ORE);
+                          CurAST.get(), MSSAU.get(), &SafetyInfo, ORE);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
-                           CurAST.get(), &SafetyInfo, ORE);
+                           CurAST.get(), MSSAU.get(), &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.get()) {
         // 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() ||
               !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.get(), &SafetyInfo, ORE);
         }
+      }
+      // FIXME: Promotion initially disabled when using MemorySSA.
 
       // 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 this loop is nested inside of another one, save the alias information
   // for when we process the outer loop.
-  if (L->getParentLoop() && !DeleteAST)
+  if (CurAST.get() && L->getParentLoop() && !DeleteAST)
     LoopToAliasSetMap[L] = std::move(CurAST);
 
+  if (MSSAU.get() && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
+
   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,
                       TargetTransformInfo *TTI, Loop *CurLoop,
-                      AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
+                      AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
+                      LoopSafetyInfo *SafetyInfo,
                       OptimizationRemarkEmitter *ORE) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
-         CurLoop != nullptr && CurAST && SafetyInfo != nullptr &&
-         "Unexpected input to sinkRegion");
+         CurLoop != nullptr && SafetyInfo != nullptr &&
+         "Unexpected input to sinkRegion.");
+  assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
+         "Either AliasSetTracker or MemorySSA should be initialized.");
 
   // 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)) {
         LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
         salvageDebugInfo(I);
         ++II;
-        CurAST->deleteValue(&I);
+        removeFromAnalyses(&I, CurAST, MSSAU);
         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.
       //
       bool FreeInLoop = false;
       if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, true, ORE) &&
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, ORE) &&
           !I.mayHaveSideEffects()) {
-        if (sink(I, LI, DT, CurLoop, SafetyInfo, ORE, FreeInLoop)) {
+        if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE, FreeInLoop)) {
           if (!FreeInLoop) {
             ++II;
-            CurAST->deleteValue(&I);
+            removeFromAnalyses(&I, CurAST, MSSAU);
             I.eraseFromParent();
           }
           Changed = true;
         }
       }
     }
   }
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
   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 *MSSAU,
+                       LoopSafetyInfo *SafetyInfo,
                        OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
-         CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
-         "Unexpected input to hoistRegion");
+         CurLoop != nullptr && SafetyInfo != nullptr &&
+         "Unexpected input to hoistRegion.");
+  assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
+         "Either AliasSetTracker or MemorySSA should be initialized.");
 
   // 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();
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)) {
         LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C
                           << '\n');
+        if (CurAST)
           CurAST->copyValue(&I, C);
+        // FIXME MSSA: Such replacements may make accesses unoptimized (D51960).
         I.replaceAllUsesWith(C);
         if (isInstructionTriviallyDead(&I, TLI)) {
-          CurAST->deleteValue(&I);
+          removeFromAnalyses(&I, CurAST, MSSAU);
           I.eraseFromParent();
         }
         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, true, ORE) &&
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, ORE) &&
           (IsMustExecute ||
            isSafeToExecuteUnconditionally(
                I, DT, CurLoop, SafetyInfo, ORE,
                CurLoop->getLoopPreheader()->getTerminator()))) {
-        hoist(I, DT, CurLoop, SafetyInfo, ORE);
+        hoist(I, DT, CurLoop, SafetyInfo, MSSAU, ORE);
         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, SafetyInfo, MSSAU, ORE);
         Changed = true;
         continue;
       }
 
       using namespace PatternMatch;
       if (((I.use_empty() &&
             match(&I, m_Intrinsic<Intrinsic::invariant_start>())) ||
            isGuard(&I)) &&
           IsMustExecute && IsMemoryNotModified &&
           CurLoop->hasLoopInvariantOperands(&I)) {
-        hoist(I, DT, CurLoop, SafetyInfo, ORE);
+        hoist(I, DT, CurLoop, SafetyInfo, MSSAU, ORE);
         Changed = true;
         continue;
       }
 
       if (IsMustExecute)
         IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
       if (IsMemoryNotModified)
         IsMemoryNotModified = !I.mayWriteToMemory();
     }
   }
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
 
   return Changed;
 }
 
 // Return true if LI is invariant within scope of the loop. LI is invariant if
 // CurLoop is dominated by an invariant.start representing the same memory
 // location and size as the memory location LI loads from, and also the
 // invariant.start has no uses.
bool isHoistableAndSinkableInst(Instruction &I) {
   return (isa<LoadInst>(I) || isa<StoreInst>(I) ||
           isa<CallInst>(I) || isa<FenceInst>(I) || 
           isa<BinaryOperator>(I) || isa<CastInst>(I) ||
           isa<SelectInst>(I) || isa<GetElementPtrInst>(I) ||
           isa<CmpInst>(I) || isa<InsertElementInst>(I) ||
           isa<ExtractElementInst>(I) || isa<ShuffleVectorInst>(I) ||
           isa<ExtractValueInst>(I) || isa<InsertValueInst>(I));
 }
 /// Return true if all of the alias sets within this AST are known not to
 /// contain a Mod.
-bool isReadOnly(AliasSetTracker *CurAST) {
+bool isReadOnly(AliasSetTracker *CurAST, const MemorySSAUpdater *MSSAU,
+                const Loop *L) {
+  if (CurAST) {
     for (AliasSet &AS : *CurAST) {
       if (!AS.isForwardingAliasSet() && AS.isMod()) {
         return false;
       }
     }
     return true;
+  } else { /*MSSAU*/
+    for (auto *BB : L->getBlocks())
+      if (MSSAU->getMemorySSA()->getBlockDefs(BB))
+        return false;
+    return true;
+  }
+}
+
+/// Return true if I is the only Instruction with a MemoryAccess in L.
+bool isOnlyMemoryAccess(const Instruction *I, const Loop *L,
+                        const MemorySSAUpdater *MSSAU) {
+  for (auto *BB : L->getBlocks())
+    if (auto *Acc = MSSAU->getMemorySSA()->getBlockAccesses(BB)) {
+      if (Acc->size() > 1)
+        return false;
+      if (const auto *MUD = dyn_cast<MemoryUseOrDef>(&*Acc->begin()))
+        if (MUD->getMemoryInst() != I)
+          return false;
+    }
+  return true;
 }
 }
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                               Loop *CurLoop, AliasSetTracker *CurAST,
+                              MemorySSAUpdater *MSSAU,
                               bool TargetExecutesOncePerLoop,
                               OptimizationRemarkEmitter *ORE) {
   // If we don't understand the instruction, bail early.
   if (!isHoistableAndSinkableInst(I))
     return false;
-  
+  MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
+
   // 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 sink/hoist volatile or ordered atomic loads!
 
     // Loads from constant memory are always safe to move, even if they end up
     // in the same alias set as something that ends up being modified.
     if (AA->pointsToConstantMemory(LI->getOperand(0)))
       return true;
     if (LI->getMetadata(LLVMContext::MD_invariant_load))
       return true;
 
     if (LI->isAtomic() && !TargetExecutesOncePerLoop)
       return false; // Don't risk duplicating unordered loads
 
     // This checks for an invariant.start dominating the load.
     if (isLoadInvariantInLoop(LI, DT, CurLoop))
       return true;
 
-    bool Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI),
-                                                CurAST, CurLoop, AA);
+    bool Invalidated;
+    if (CurAST)
+      Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
+                                             CurLoop, AA);
+    else
+      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([&]() {
         return OptimizationRemarkMissed(
                    DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
                << "failed to move load with loop-invariant address "
                   "because the loop may invalidate its value";
       });
 
     return !Invalidated;
   } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
     // Don't sink or hoist dbg info; it's legal, but not useful.
     if (isa<DbgInfoIntrinsic>(I))
       return false;
 
     // Don't sink calls which can throw.
     if (CI->mayThrow())
       return false;
 
     using namespace PatternMatch;
     if (match(CI, m_Intrinsic<Intrinsic::assume>()))
       // Assumes don't actually alias anything or throw
       return true;
-    
     // Handle simple cases by querying alias analysis.
     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)) {
         // TODO: expand to writeable arguments
         for (Value *Op : CI->arg_operands())
-          if (Op->getType()->isPointerTy() &&
-              pointerInvalidatedByLoop(
+          if (Op->getType()->isPointerTy()) {
+            bool Invalidated;
+            if (CurAST)
+              Invalidated = pointerInvalidatedByLoop(
                   MemoryLocation(Op, MemoryLocation::UnknownSize, AAMDNodes()),
-                  CurAST, CurLoop, AA))
+                  CurAST, CurLoop, AA);
+            else
+              Invalidated = pointerInvalidatedByLoopWithMSSA(
+                  Op, MSSA, MSSA->getMemoryAccess(CI), CurLoop);
+            if (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.
-      if (isReadOnly(CurAST))
+      if (isReadOnly(CurAST, MSSAU, CurLoop))
         return true;
     }
 
     // FIXME: This should use mod/ref information to see if we can hoist or
     // sink the call.
 
     return false;
   } else if (auto *FI = dyn_cast<FenceInst>(&I)) {
     // Fences alias (most) everything to provide ordering.  For the moment,
     // just give up if there are any other memory operations in the loop.
+    if (CurAST) {
       auto Begin = CurAST->begin();
       assert(Begin != CurAST->end() && "must contain FI");
       if (std::next(Begin) != CurAST->end())
         // constant memory for instance, TODO: handle better
         return false;
       auto *UniqueI = Begin->getUniqueInstruction();
       if (!UniqueI)
         // other memory op, give up
         return false;
-    (void)FI; //suppress unused variable warning
+      (void)FI; // suppress unused variable warning
       assert(UniqueI == FI && "AS must contain FI");
       return true;
+    } else { // MSSAU
+      if (isOnlyMemoryAccess(FI, CurLoop, MSSAU))
+        return true;
+      return false;
+    }
   } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
     if (!SI->isUnordered())
       return false; // Don't sink/hoist volatile or ordered atomic store!
 
     // We can only hoist a store that we can prove writes a value which is not
     // read or overwritten within the loop.  For those cases, we fallback to
     // load store promotion instead.  TODO: We can extend this to cases where
     // there is exactly one write to the location and that write dominates an
     // arbitrary number of reads in the loop.
+    if (CurAST) {
       auto &AS = CurAST->getAliasSetFor(MemoryLocation::get(SI));
 
       if (AS.isRef() || !AS.isMustAlias())
         // Quick exit test, handled by the full path below as well.
         return false;
       auto *UniqueI = AS.getUniqueInstruction();
       if (!UniqueI)
         // other memory op, give up
         return false;
       assert(UniqueI == SI && "AS must contain SI");
       return true;
+    } else { // MSSAU
+      if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
+        return true;
+      // FIXME: Checking alias() of SI against all other memory instructions is
+      // initially disabled when using MemorySSA.
+      // example: test/Transforms/LICM/atomics.ll:test7b
+      return false;
+    }
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
 
   // We've established mechanical ability and aliasing, it's up to the caller
   // to check fault safety
   return true;
 }
if (CurLoop->contains(UI)) {
         continue;
       }
       return false;
     }
   }
   return true;
 }
 
-static Instruction *
-CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
-                            const LoopInfo *LI,
-                            const LoopSafetyInfo *SafetyInfo) {
+static Instruction *CloneInstructionInExitBlock(
+    Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
+    const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU) {
   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
     // appropriate for it's location in the CFG.
     SmallVector<OperandBundleDef, 1> OpBundles;
static Instruction *CloneInstructionInExitBlock(
   } else {
     New = I.clone();
   }
 
   ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
   if (!I.getName().empty())
     New->setName(I.getName() + ".le");
 
+  MemoryAccess *OldMemAcc;
+  if (MSSAU && (OldMemAcc = MSSAU->getMemorySSA()->getMemoryAccess(&I))) {
+    // Create a new MemoryAccess and let MemorySSA set its defining access.
+    MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
+        New, nullptr, New->getParent(), MemorySSA::Beginning);
+    if (NewMemAcc) {
+      if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
+        MSSAU->insertDef(MemDef, /*RenameUses=*/true);
+      else {
+        auto *MemUse = cast<MemoryUse>(NewMemAcc);
+        MSSAU->insertUse(MemUse);
+        // This is only called to properly update the defining access.
+        if (EnableLicmCap)
+          MSSAU->getMemorySSA()->getWalker()->getClobberingMemoryAccess(MemUse);
+      }
+    }
+  }
+
   // 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;
if (Instruction *OInst = dyn_cast<Instruction>(*OI))
           *OI = OpPN;
         }
   return New;
 }
 
 static Instruction *sinkThroughTriviallyReplaceablePHI(
     PHINode *TPN, Instruction *I, LoopInfo *LI,
     SmallDenseMap<BasicBlock *, Instruction *, 32> &SunkCopies,
-    const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop) {
+    const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop,
+    MemorySSAUpdater *MSSAU) {
   assert(isTriviallyReplaceablePHI(*TPN, *I) &&
          "Expect only trivially replaceable PHI");
   BasicBlock *ExitBlock = TPN->getParent();
   Instruction *New;
   auto It = SunkCopies.find(ExitBlock);
   if (It != SunkCopies.end())
     New = It->second;
   else
-    New = SunkCopies[ExitBlock] =
-        CloneInstructionInExitBlock(*I, *ExitBlock, *TPN, LI, SafetyInfo);
+    New = SunkCopies[ExitBlock] = CloneInstructionInExitBlock(
+        *I, *ExitBlock, *TPN, LI, SafetyInfo, MSSAU);
   return New;
 }
 
 static bool canSplitPredecessors(PHINode *PN, LoopSafetyInfo *SafetyInfo) {
   BasicBlock *BB = PN->getParent();
   if (!BB->canSplitPredecessors())
     return false;
   // It's not impossible to split EHPad blocks, but if BlockColors already exist
   // it require updating BlockColors for all offspring blocks accordingly. By
   // skipping such corner case, we can make updating BlockColors after splitting
   // predecessor fairly simple.
   if (!SafetyInfo->BlockColors.empty() && BB->getFirstNonPHI()->isEHPad())
     return false;
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
     BasicBlock *BBPred = *PI;
     if (isa<IndirectBrInst>(BBPred->getTerminator()))
       return false;
   }
   return true;
 }
 
 static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT,
                                         LoopInfo *LI, const Loop *CurLoop,
-                                        LoopSafetyInfo *SafetyInfo) {
+                                        LoopSafetyInfo *SafetyInfo,
+                                        MemorySSAUpdater *MSSAU) {
 #ifndef NDEBUG
   SmallVector<BasicBlock *, 32> ExitBlocks;
   CurLoop->getUniqueExitBlocks(ExitBlocks);
   SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
                                              ExitBlocks.end());
 #endif
   BasicBlock *ExitBB = PN->getParent();
   assert(ExitBlockSet.count(ExitBB) && "Expect the PHI is in an exit block.");
#endif
   auto &BlockColors = SafetyInfo->BlockColors;
   SmallSetVector<BasicBlock *, 8> PredBBs(pred_begin(ExitBB), pred_end(ExitBB));
   while (!PredBBs.empty()) {
     BasicBlock *PredBB = *PredBBs.begin();
     assert(CurLoop->contains(PredBB) &&
            "Expect all predecessors are in the loop");
     if (PN->getBasicBlockIndex(PredBB) >= 0) {
       BasicBlock *NewPred = SplitBlockPredecessors(
-          ExitBB, PredBB, ".split.loop.exit", DT, LI, nullptr, true);
+          ExitBB, PredBB, ".split.loop.exit", DT, LI, MSSAU, true);
       // Since we do not allow splitting EH-block with BlockColors in
       // canSplitPredecessors(), we can simply assign predecessor's color to
       // the new block.
       if (!BlockColors.empty()) {
         // Grab a reference to the ColorVector to be inserted before getting the
         // reference to the vector we are copying because inserting the new
         // element in BlockColors might cause the map to be reallocated.
         ColorVector &ColorsForNewBlock = BlockColors[NewPred];
         ColorVector &ColorsForOldBlock = BlockColors[PredBB];
         ColorsForNewBlock = ColorsForOldBlock;
       }
     }
     PredBBs.remove(PredBB);
   }
 }
 
 /// 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, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
-                 OptimizationRemarkEmitter *ORE, bool FreeInLoop) {
+                 MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE,
+                 bool FreeInLoop) {
   LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
            << "sinking " << ore::NV("Inst", &I);
   });
   bool Changed = false;
   if (isa<LoadInst>(I))
     ++NumMovedLoads;
for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
     if (isTriviallyReplaceablePHI(*PN, I))
       continue;
 
     if (!canSplitPredecessors(PN, SafetyInfo))
       return Changed;
 
     // Split predecessors of the PHI so that we can make users trivially
     // replaceable.
-    splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo);
+    splitPredecessorsOfLoopExit(PN, DT, LI, CurLoop, SafetyInfo, MSSAU);
 
     // Should rebuild the iterators, as they may be invalidated by
     // splitPredecessorsOfLoopExit().
     UI = I.user_begin();
     UE = I.user_end();
   }
 
   if (VisitedUsers.empty())
for (auto *UI : Users) {
 
     if (CurLoop->contains(User))
       continue;
 
     PHINode *PN = cast<PHINode>(User);
     assert(ExitBlockSet.count(PN->getParent()) &&
            "The LCSSA PHI is not in an exit block!");
     // The PHI must be trivially replaceable.
-    Instruction *New = sinkThroughTriviallyReplaceablePHI(PN, &I, LI, SunkCopies,
-                                                          SafetyInfo, CurLoop);
+    Instruction *New = sinkThroughTriviallyReplaceablePHI(
+        PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
     PN->replaceAllUsesWith(New);
     PN->eraseFromParent();
     Changed = true;
   }
   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 void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
-                  LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
+                  LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU,
+                  OptimizationRemarkEmitter *ORE) {
   auto *Preheader = CurLoop->getLoopPreheader();
   LLVM_DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
                     << "\n");
   ORE->emit([&]() {
     return 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 (MSSAU) {
+    // If moving, I just moved a load or store, so update MemorySSA.
+    MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
+        MSSAU->getMemorySSA()->getMemoryAccess(&I));
+    if (OldMemAcc) {
+      MSSAU->moveToPlace(OldMemAcc, Preheader, MemorySSA::End);
+      // This is only called to properly update the defining access.
+      if (EnableLicmCap)
+        MSSAU->getMemorySSA()->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());
for (Instruction &I : *BB) {
                           << *(MemLoc.Ptr) << "\n");
         return true;
       }
     }
   LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
   return false;
 }
 
+static bool pointerInvalidatedByLoopWithMSSA(Value *V, MemorySSA *MSSA,
+                                             MemoryUseOrDef *MUD,
+                                             Loop *CurLoop) {
+  assert(V->getType()->isPointerTy() && "Value tested is not a pointer.");
+  if (isa<UndefValue>(V))
+    return true;
+
+  // MUD is from a LoadInst or CallInst, so both Uses.
+  if (MemoryUse *MU = cast_or_null<MemoryUse>(MUD)) {
+    MemoryAccess *Source;
+    // See declaration of EnableLicmCap for usage details.
+    if (EnableLicmCap)
+      Source = MU->getDefiningAccess();
+    else
+      Source = MSSA->getWalker()->getClobberingMemoryAccess(MU);
+    if (MSSA->isLiveOnEntryDef(Source) ||
+        !CurLoop->contains(Source->getBlock()))
+      return false;
+  }
+  return true;
+}
+
 /// 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 removeFromAnalyses(Instruction *I, AliasSetTracker *CurAST,
+                               MemorySSAUpdater *MSSAU) {
+  if (CurAST)
+    CurAST->deleteValue(I);
+  else
+    MSSAU->removeMemoryAccess(I);
+}

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, false))
+    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false))
       continue;
     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
       Changed = true;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   return Changed;

test/Transforms/LICM/argmemonly-call.ll

 ; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 %s | FileCheck %s
 ; RUN: opt -licm -basicaa -licm-n2-threshold=200 < %s -S | FileCheck %s --check-prefix=ALIAS-N2
 ; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=0 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -licm-n2-threshold=200 -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s --check-prefix=ALIAS-N2
+; RUN: opt -S -basicaa -licm -licm-n2-threshold=0 -enable-mssa-loop-dependency=true -verify-memoryssa %s | FileCheck %s --check-prefix=ALIAS-N2
 
 declare i32 @foo() readonly argmemonly nounwind
 declare i32 @foo2() readonly nounwind
 declare i32 @bar(i32* %loc2) readonly argmemonly nounwind
 
 define void @test(i32* %loc) {
 ; CHECK-LABEL: @test
 ; CHECK: @foo
 ; CHECK-LABEL: loop:
+; ALIAS-N2-LABEL: @test
+; ALIAS-N2: @foo
+; ALIAS-N2-LABEL: loop:
   br label %loop
 
 loop:
   %res = call i32 @foo()
   store i32 %res, i32* %loc
   br label %loop
 }
 
 ; Negative test: show argmemonly is required
 define void @test_neg(i32* %loc) {
 ; CHECK-LABEL: @test_neg
 ; CHECK-LABEL: loop:
 ; CHECK: @foo
+; ALIAS-N2-LABEL: @test_neg
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2: @foo
   br label %loop
 
 loop:
   %res = call i32 @foo2()
   store i32 %res, i32* %loc
   br label %loop
 }
 
 define void @test2(i32* noalias %loc, i32* noalias %loc2) {
 ; CHECK-LABEL: @test2
 ; CHECK: @bar
 ; CHECK-LABEL: loop:
+; ALIAS-N2-LABEL: @test2
+; ALIAS-N2: @bar
+; ALIAS-N2-LABEL: loop:
   br label %loop
 
 loop:
   %res = call i32 @bar(i32* %loc2)
   store i32 %res, i32* %loc
   br label %loop
 }
 
 ; Negative test: %might clobber gep
 define void @test3(i32* %loc) {
 ; CHECK-LABEL: @test3
 ; CHECK-LABEL: loop:
 ; CHECK: @bar
+; ALIAS-N2-LABEL: @test3
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2: @bar
   br label %loop
 
 loop:
   %res = call i32 @bar(i32* %loc)
   %gep = getelementptr i32, i32 *%loc, i64 1000000
   store i32 %res, i32* %gep
   br label %loop
 }
 
 
 ; Negative test: %loc might alias %loc2
 define void @test4(i32* %loc, i32* %loc2) {
 ; CHECK-LABEL: @test4
 ; CHECK-LABEL: loop:
 ; CHECK: @bar
+; ALIAS-N2-LABEL: @test4
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2: @bar
   br label %loop
 
 loop:
   %res = call i32 @bar(i32* %loc2)
   store i32 %res, i32* %loc
   br label %loop
 }
 
 declare i32 @foo_new(i32*) readonly
 ; With the default AST mechanism used by LICM for alias analysis,
 ; we clump foo_new with bar.
 ; With the N2 Alias analysis diagnostic tool, we are able to hoist the
 ; argmemonly bar call out of the loop.
+; Using MemorySSA we can also hoist bar.
 
 define void @test5(i32* %loc2, i32* noalias %loc) {
 ; ALIAS-N2-LABEL: @test5
 ; ALIAS-N2: @bar
 ; ALIAS-N2-LABEL: loop:
 
 ; CHECK-LABEL: @test5
 ; CHECK-LABEL: loop:

 
 ; memcpy doesn't write to it's source argument, so loads to that location
 ; can still be hoisted
 define void @test6(i32* noalias %loc, i32* noalias %loc2) {
 ; CHECK-LABEL: @test6
 ; CHECK: %val = load i32, i32* %loc2
 ; CHECK-LABEL: loop:
 ; CHECK: @llvm.memcpy
+; ALIAS-N2-LABEL: @test6
+; ALIAS-N2: %val = load i32, i32* %loc2
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2: @llvm.memcpy
   br label %loop
 
 loop:
   %val = load i32, i32* %loc2
   store i32 %val, i32* %loc
   %dest = bitcast i32* %loc to i8*
   %src = bitcast i32* %loc2 to i8*
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dest, i8* %src, i64 8, i1 false)
   br label %loop
 }
 
 define void @test7(i32* noalias %loc, i32* noalias %loc2) {
 ; CHECK-LABEL: @test7
 ; CHECK: %val = load i32, i32* %loc2
 ; CHECK-LABEL: loop:
 ; CHECK: @custom_memcpy
+; ALIAS-N2-LABEL: @test7
+; ALIAS-N2: %val = load i32, i32* %loc2
+; ALIAS-N2-LABEL: loop:
+; ALIAS-N2: @custom_memcpy
   br label %loop
 
 loop:
   %val = load i32, i32* %loc2
   store i32 %val, i32* %loc
   %dest = bitcast i32* %loc to i8*
   %src = bitcast i32* %loc2 to i8*
   call void @custom_memcpy(i8* %dest, i8* %src)
   br label %loop
 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1)
 declare void @custom_memcpy(i8* nocapture writeonly, i8* nocapture readonly) argmemonly nounwind

test/Transforms/LICM/hoist-bitcast-load.ll

 ; RUN: opt -S -basicaa -licm < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(simplify-cfg,licm)' -S < %s | FileCheck %s
+; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Make sure the basic alloca pointer hoisting works:
 ; CHECK-LABEL: @test1
 ; CHECK: load i32, i32* %c, align 4
 ; CHECK: for.body:

test/Transforms/LICM/hoist-debuginvariant.ll

 ; RUN: opt < %s -licm -S | FileCheck %s
 ; RUN: opt < %s -strip-debug -licm -S | FileCheck %s
+; RUN: opt < %s -licm -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Verify that the sdiv is hoisted out of the loop
 ; even in the presence of a preceding debug intrinsic.
 
 @a = global i32 0

test/Transforms/LICM/hoist-deref-load.ll

 ; RUN: opt -S -basicaa -licm < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(simplify-cfg,licm)' -S < %s | FileCheck %s
+; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(simplify-cfg,licm)' -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; This test represents the following function:
 ; void test1(int * __restrict__ a, int * __restrict__ b, int &c, int n) {
 ;   for (int i = 0; i < n; ++i)
 ;     if (a[i] > 0)

test/Transforms/LICM/hoist-fast-fdiv.ll

 ; RUN: opt -licm -S < %s | FileCheck %s
+; RUN: opt -licm -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s | FileCheck %s
 
 ; Function Attrs: noinline norecurse nounwind readnone ssp uwtable
 define zeroext i1 @invariant_denom(double %v) #0 {
 entry:
 ; CHECK-LABEL: @invariant_denom(
 ; CHECK-NEXT: entry:
 ; CHECK-NEXT: fdiv fast double 1.000000e+00, %v
   br label %loop

test/Transforms/LICM/hoist-invariant-load.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -licm -disable-basicaa -stats -S 2>&1 | grep "1 licm"
+; RUN: opt < %s -licm -enable-mssa-loop-dependency=true -verify-memoryssa -disable-basicaa -stats -S 2>&1 | grep "1 licm"
 
 @"\01L_OBJC_METH_VAR_NAME_" = internal global [4 x i8] c"foo\00", section "__TEXT,__objc_methname,cstring_literals", align 1
 @"\01L_OBJC_SELECTOR_REFERENCES_" = internal global i8* getelementptr inbounds ([4 x i8], [4 x i8]* @"\01L_OBJC_METH_VAR_NAME_", i32 0, i32 0), section "__DATA, __objc_selrefs, literal_pointers, no_dead_strip"
 @"\01L_OBJC_IMAGE_INFO" = internal constant [2 x i32] [i32 0, i32 16], section "__DATA, __objc_imageinfo, regular, no_dead_strip"
 @llvm.used = appending global [3 x i8*] [i8* getelementptr inbounds ([4 x i8], [4 x i8]* @"\01L_OBJC_METH_VAR_NAME_", i32 0, i32 0), i8* bitcast (i8** @"\01L_OBJC_SELECTOR_REFERENCES_" to i8*), i8* bitcast ([2 x i32]* @"\01L_OBJC_IMAGE_INFO" to i8*)], section "llvm.metadata"
 
 define void @test(i8* %x) uwtable ssp {
 entry:

test/Transforms/LICM/hoist-nounwind.ll

 ; RUN: opt -S -basicaa -licm < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
+; RUN: opt -S -basicaa -licm -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @f() nounwind
 
 ; Don't hoist load past nounwind call.
 define i32 @test1(i32* noalias nocapture readonly %a) nounwind uwtable {
 ; CHECK-LABEL: @test1(

test/Transforms/LICM/hoist-round.ll

 ; RUN: opt -S -licm < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
+; RUN: opt -S -licm -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 target datalayout = "E-m:e-p:32:32-i8:8:8-i16:16:16-i64:32:32-f64:32:32-v64:32:32-v128:32:32-a0:0:32-n32"
 
 ; This test verifies that ceil, floor, nearbyint, trunc, rint, round,
 ; copysign, minnum, maxnum and fabs intrinsics are considered safe
 ; to speculate.
 
 ; CHECK-LABEL: @test

test/Transforms/LICM/hoisting.ll

 ; RUN: opt < %s -licm -S | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S | FileCheck %s
+; RUN: opt < %s -licm -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 @X = global i32 0   ; <i32*> [#uses=1]
 
 declare void @foo()
 
 declare i32 @llvm.bitreverse.i32(i32)
 
 ; This testcase tests for a problem where LICM hoists 

test/Transforms/LICM/sink-promote.ll

+; RUN: opt < %s -basicaa -licm -S | FileCheck %s
+
+; Test moved from sinking.ll, as it tests sinking of a store who alone touches
+; a memory location in a loop.
+; Store can be sunk out of exit block containing indirectbr instructions after
+; D50925. Updated to use an argument instead of undef, due to PR38989.
+define void @test12(i32* %ptr) {
+; CHECK-LABEL: @test12
+; CHECK: store
+; CHECK-NEXT: br label %lab4
+  br label %lab4
+
+lab4:
+  br label %lab20
+
+lab5:
+  br label %lab20
+
+lab6:
+  br label %lab4
+
+lab7:
+  br i1 undef, label %lab8, label %lab13
+
+lab8:
+  br i1 undef, label %lab13, label %lab10
+
+lab10:
+  br label %lab7
+
+lab13:
+  ret void
+
+lab20:
+  br label %lab21
+
+lab21:
+; CHECK: lab21:
+; CHECK-NOT: store
+; CHECK: br i1 false, label %lab21, label %lab22
+  store i32 36127957, i32* %ptr, align 4
+  br i1 undef, label %lab21, label %lab22
+
+lab22:
+; CHECK: lab22:
+; CHECK-NOT: store
+; CHECK-NEXT: indirectbr i8* undef
+  indirectbr i8* undef, [label %lab5, label %lab6, label %lab7]
+}
+

test/Transforms/LICM/sink.ll

 ; RUN: opt -S -licm < %s | FileCheck %s --check-prefix=CHECK-LICM
 ; RUN: opt -S -licm < %s | opt -S -loop-sink | FileCheck %s --check-prefix=CHECK-SINK
 ; RUN: opt -S < %s -passes='require<opt-remark-emit>,loop(licm),loop-sink' \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-SINK
+; RUN: opt -S -licm -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s --check-prefix=CHECK-LICM
 
 ; Original source code:
 ; int g;
 ; int foo(int p, int x) {
 ;   for (int i = 0; i != x; i++)
 ;     if (__builtin_expect(i == p, 0)) {
 ;       x += g; x *= g;
 ;     }

test/Transforms/LICM/sinking.ll

 ; RUN: opt < %s -basicaa -licm -S | FileCheck %s
 ; RUN: opt < %s -debugify -basicaa -licm -S | FileCheck %s -check-prefix=DEBUGIFY
+; RUN: opt < %s -basicaa -licm -S -enable-mssa-loop-dependency=true -verify-memoryssa | FileCheck %s
+
 
 declare i32 @strlen(i8*) readonly nounwind
 
 declare void @foo()
 
 ; Sink readonly function.
 define i32 @test1(i8* %P) {
   br label %Loop

 ; CHECK:       exit:
 ; CHECK-NEXT:    %[[LCSSAPHI:.*]] = phi i64 [ %iv, %l4.latch ], [ %iv, %l4.body ]
 ; CHECK-NEXT:    %l.le = trunc i64 %[[LCSSAPHI]] to i32
 ; CHECK-NEXT:    ret i32 %l.le
 
   ret i32 %lcssa
 }
 
-; Can't sink stores out of exit blocks containing indirectbr instructions
-; because loop simplify does not create dedicated exits for such blocks. Test
-; that by sinking the store from lab21 to lab22, but not further.
-define void @test12() {
-; CHECK-LABEL: @test12
-  br label %lab4
-
-lab4:
-  br label %lab20
-
-lab5:
-  br label %lab20
-
-lab6:
-  br label %lab4
-
-lab7:
-  br i1 undef, label %lab8, label %lab13
-
-lab8:
-  br i1 undef, label %lab13, label %lab10
-
-lab10:
-  br label %lab7
-
-lab13:
-  ret void
-
-lab20:
-  br label %lab21
-
-lab21:
-; CHECK: lab21:
-; CHECK-NOT: store
-; CHECK: br i1 false, label %lab21, label %lab22
-  store i32 36127957, i32* undef, align 4
-  br i1 undef, label %lab21, label %lab22
-
-lab22:
-; CHECK: lab22:
-; CHECK: store
-; CHECK-NEXT: indirectbr i8* undef
-  indirectbr i8* undef, [label %lab5, label %lab6, label %lab7]
-}
+; @test12 moved to sink-promote.ll, as it tests sinking and promotion.
 
 ; Test that we don't crash when trying to sink stores and there's no preheader
 ; available (which is used for creating loads that may be used by the SSA
 ; updater)
 define void @test13() {
 ; CHECK-LABEL: @test13
   br label %lab59
 

test/Transforms/LICM/volatile-alias.ll

 ; RUN: opt -basicaa -sroa -loop-rotate -licm -S < %s | FileCheck %s
 ; RUN: opt -basicaa -sroa -loop-rotate %s | opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' -S | FileCheck %s
+; RUN: opt -basicaa -sroa -loop-rotate -licm -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s | FileCheck %s
 ; The objects *p and *q are aliased to each other, but even though *q is
 ; volatile, *p can be considered invariant in the loop. Check if it is moved
 ; out of the loop.
 ; CHECK: load i32, i32* %p
 ; CHECK: for.body:
 ; CHECK: load volatile i32, i32* %q
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"