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

159

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?

290

This seems unnecessary.

653–659

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.

714

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

1647

How about call it isVolatileLoadOrLiveOnEntry?

1649

The usual idiom I've seen for this is:

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

1650

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?

1656

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)) {
}

1660

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

1667

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

1678

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

1682

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

1699

s/if/If/

1700

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

lib/Transforms/Scalar/LoopSink.cpp

291–292

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

[asbirlea]

Address comments.

lib/Transforms/Scalar/LICM.cpp

1649

Code in question removed.

1650

Right, but code in question removed.

1660

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.

1667

Code updated, see comment below.

1700

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

398

Can this be a std::unique_ptr?

420

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

690

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.

697

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

706–711

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

863

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.

865

Instead of two dyn_cast_or_nulls how about:

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

?

867

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

873

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)).

1134–1135

Can this be cast_or_null?

1661

Stray comment?

1664

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

[asbirlea]

Comments.

[asbirlea]

lib/Transforms/Scalar/LICM.cpp

420

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

873

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

873

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

873

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

318

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

873

(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?

99

Line too long?

420

Probably better to have two asserts here:

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

871

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

1140

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.

1140

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?

1653

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

1140

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

1140

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

1140

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

93

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

107

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.

475–476

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

617–618

Update comment?

632

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;

739

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

107

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?

475–476

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.

632

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/Transforms/Utils/LoopUtils.h

 namespace llvm {
 
 class AliasSet;
 class AliasSetTracker;
 class BasicBlock;
 class DataLayout;
 class Loop;
 class LoopInfo;
+class MemorySSA;
+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 *,
-                OptimizationRemarkEmitter *ORE);
+                AliasSetTracker *, LoopSafetyInfo *, MemorySSAUpdater *,
+                MemorySSA *, 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);
+                 LoopSafetyInfo *, MemorySSAUpdater *, MemorySSA *,
+                 OptimizationRemarkEmitter *);
 
 /// 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
 ///

 /// 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,
+                        MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                         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 *>());
 

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/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/OptimizationRemarkEmitter.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"
static cl::opt<bool>
     DisablePromotion("disable-licm-promotion", cl::Hidden, cl::init(false),
                      cl::desc("Disable memory promotion in LICM pass"));
 
 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)"));
 
+// 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 bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   const LoopSafetyInfo *SafetyInfo,
+                  MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
+                 MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                  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(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 void removeFromAnalyses(Instruction *I, AliasSetTracker *CurAST,
+                               MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA);
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
                             const LoopInfo *LI,
-                            const LoopSafetyInfo *SafetyInfo);
+                            const LoopSafetyInfo *SafetyInfo,
+                            MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA);
 
 namespace {
 struct LoopInvariantCodeMotion {
   bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
                  TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
                  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);
 };
 
 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.");
 
-  AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA);
+  AliasSetTracker *CurAST = nullptr;
+  std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
+
+  if (!MSSA) {
+    DEBUG(dbgs() << "LICM: Using Alias Set Tracker\n");
+    CurAST = collectAliasInfoForLoop(L, LI, AA);
+  } else {
+    DEBUG(dbgs() << "LICM: Using MemorySSA\n");
+    MSSAUpdater = make_unique<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, TTI, L,
-                          CurAST, &SafetyInfo, ORE);
+                          CurAST, &SafetyInfo, MSSAUpdater.get(), MSSA, ORE);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
-                           CurAST, &SafetyInfo, ORE);
+                           CurAST, &SafetyInfo, MSSAUpdater.get(), MSSA, 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,
         }
+      }
+      // 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 (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;
+  }
 
   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,
+                      MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                       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(((MSSAUpdater == nullptr) == (MSSA == nullptr)) &&
+         "MemorySSA and MemorySSAUpdater found inconsistent in sinkRegion");
+  assert(((CurAST != nullptr) ^ (MSSA != nullptr)) && "Either AliasSetTracker "
+         "or MemorySSA should be initialized in 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;
-        CurAST->deleteValue(&I);
+        removeFromAnalyses(&I, CurAST, 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.
       //
       bool FreeInLoop = false;
       if (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
-          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE)) {
-        if (sink(I, LI, DT, CurLoop, SafetyInfo, ORE, FreeInLoop)) {
+          canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo,
+                             MSSAUpdater, MSSA, ORE)) {
+        if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAUpdater, MSSA, ORE,
+                 FreeInLoop)) {
           if (!FreeInLoop) {
             ++II;
-            CurAST->deleteValue(&I);
+            removeFromAnalyses(&I, CurAST, MSSAUpdater, MSSA);
             I.eraseFromParent();
           }
           Changed = true;
         }
       }
     }
   }
   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,
+                       MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                        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(((MSSAUpdater == nullptr) == (MSSA == nullptr)) &&
+         "MemorySSA and MemorySSAUpdater found inconsistent in hoistRegion");
+  assert(((CurAST != nullptr) ^ (MSSA != nullptr)) && "Either AliasSetTracker "
+         "or MemorySSA should be initialized in 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);
           I.replaceAllUsesWith(C);
           if (isInstructionTriviallyDead(&I, TLI)) {
-            CurAST->deleteValue(&I);
+            removeFromAnalyses(&I, CurAST, 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, SafetyInfo, MSSAUpdater, MSSA,
+                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, SafetyInfo,
+                               MSSAUpdater, MSSA, ORE) &&
             isSafeToExecuteUnconditionally(
                 I, DT, CurLoop, SafetyInfo, ORE,
                 CurLoop->getLoopPreheader()->getTerminator()))
-          Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+          Changed |= hoist(I, DT, CurLoop, SafetyInfo, MSSAUpdater, MSSA, ORE);
       }
   }
 
   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
for (auto *U : Addr->users()) {
     // invariant.start.
     if (LocSizeInBits <= InvariantSizeInBits &&
         DT->properlyDominates(II->getParent(), CurLoop->getHeader()))
       return true;
   }
 
   return false;
 }
 
 bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
                               Loop *CurLoop, AliasSetTracker *CurAST,
                               LoopSafetyInfo *SafetyInfo,
+                              MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                               OptimizationRemarkEmitter *ORE) {
   // SafetyInfo is nullptr if we are checking for sinking from preheader to
   // loop body.
   const bool SinkingToLoopBody = !SafetyInfo;
   // 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() && SinkingToLoopBody)
       return false; // Don't sink unordered atomic loads to loop body.
 
     // This checks for an invariant.start dominating the load.
     if (isLoadInvariantInLoop(LI, DT, CurLoop))
       return true;
 
     // 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;
+    if (CurAST)
+      Invalidated =
           pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
+    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";
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     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))
+          if (Op->getType()->isPointerTy()) {
+            bool Invalidated;
+            if (CurAST)
+              Invalidated = pointerInvalidatedByLoop(
+                  Op, MemoryLocation::UnknownSize, AAMDNodes(), CurAST);
+            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.
       bool FoundMod = false;
+      if (CurAST) {
         for (AliasSet &AS : *CurAST) {
           if (!AS.isForwardingAliasSet() && AS.isMod()) {
             FoundMod = true;
             break;
           }
         }
+      } else
+        FoundMod =
+            llvm::any_of(CurLoop->blocks(), [MSSA](const BasicBlock *BB) {
+              return MSSA->getBlockDefs(BB) != nullptr;
+            });
       if (!FoundMod)
         return true;
     }
 
     // FIXME: This should use mod/ref information to see if we can hoist or
     // sink the call.
 
     return false;
   }
 
   // Only these instructions are hoistable/sinkable.
   if (!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 false;
 
   // If we are checking for sinking from preheader to loop body it will be
   // always safe as there is no speculative execution.
   if (SinkingToLoopBody)
     return true;
 
   // TODO: Plumb the context instruction through to make hoisting and sinking
   // more powerful. Hoisting of loads already works due to the special casing
   // above.
   return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr);
 }
 
 /// Returns true if a PHINode is a trivially replaceable with an
for (const User *U : I.users()) {
     }
   }
   return true;
 }
 
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
                             const LoopInfo *LI,
-                            const LoopSafetyInfo *SafetyInfo) {
+                            const LoopSafetyInfo *SafetyInfo,
+                            MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA) {
   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;
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))) {
+    // Create a new MemoryAccess and let MemorySSA set its defining access.
+    MemoryAccess *NewMemAcc = MSSAUpdater->createMemoryAccessInBB(
+        New, nullptr, New->getParent(), MemorySSA::Beginning);
+    if (NewMemAcc) {
+      if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
+        MSSAUpdater->insertDef(MemDef, /*RenameUses=*/true);
+      else {
+        auto *MemUse = cast<MemoryUse>(NewMemAcc);
+        MSSAUpdater->insertUse(MemUse);
+        // This is only called to properly update the defining access.
+        if (EnableLicmCap)
+          MSSA->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 *sinkThroughTriviallyReplacablePHI(
     PHINode *TPN, Instruction *I, LoopInfo *LI,
     SmallDenseMap<BasicBlock *, Instruction *, 32> &SunkCopies,
-    const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop) {
+    const LoopSafetyInfo *SafetyInfo, const Loop *CurLoop,
+    MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA) {
   assert(isTriviallyReplacablePHI(*TPN, *I) &&
          "Expect only trivially replacalbe 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, MSSAUpdater, MSSA);
   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

 
 /// 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,
+                 MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                  OptimizationRemarkEmitter *ORE, bool FreeInLoop) {
   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))
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 replacable.
-    Instruction *New = sinkThroughTriviallyReplacablePHI(PN, &I, LI, SunkCopies,
-                                                         SafetyInfo, CurLoop);
+    Instruction *New = sinkThroughTriviallyReplacablePHI(
+        PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAUpdater, MSSA);
     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 bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   const LoopSafetyInfo *SafetyInfo,
+                  MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA,
                   OptimizationRemarkEmitter *ORE) {
   auto *Preheader = CurLoop->getLoopPreheader();
   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 (MSSA) {
+    // If moving, I just moved a load or store, so update MemorySSA.
+    MemoryUseOrDef *OldMemAcc =
+        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.
+      if (EnableLicmCap)
+        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());

 }
 
 /// Return true if the body of this loop may store into the memory
 /// location pointed to by V.
 ///
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST) {
+  assert(V->getType()->isPointerTy() && "Value tested is not a pointer.");
   // Check to see if any of the basic blocks in CurLoop invalidate *V.
   return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
 }
 
+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 LoopInstr or CallInstr, 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 removeFromMSSA(Instruction *I, MemorySSAUpdater *MSSAUpdater,
+                           MemorySSA *MSSA) {
+  if (MemoryUseOrDef *AccI = MSSA->getMemoryAccess(I))
+    MSSAUpdater->removeMemoryAccess(AccI);
+}
+
+static void removeFromAnalyses(Instruction *I, AliasSetTracker *CurAST,
+                               MemorySSAUpdater *MSSAUpdater, MemorySSA *MSSA) {
+  if (CurAST)
+    CurAST->deleteValue(I);
+  else
+    removeFromMSSA(I, MSSAUpdater, MSSA);
+}

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

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 < %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-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 < %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 -S -enable-mssa-loop-dependency=true < %s | FileCheck %s
 
 ; Function Attrs: noinline norecurse nounwind readnone ssp uwtable
 define zeroext i1 @f(double %v) #0 {
 entry:
 ; CHECK-LABEL: @f(
 ; 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 -disable-basicaa -stats -S -enable-mssa-loop-dependency=true 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 < %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 < %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 -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 promotion and sinking.
+; 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]
+}

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 < %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 -basicaa -licm -S -enable-mssa-loop-dependency=true | 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 -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"