[MemorySSA] Teach LoopSimplify to preserve MemorySSA.

[asbirlea]

Summary

Preserve MemorySSA in LoopSimplify, in the old pass manager, if the analysis is available.
Do not preserve it in the new pass manager.
Update tests.

[asbirlea]

Simplify patch to preserve MemorySSA in the old pass manager only when the pass is already available (remove *require*).
New pass manager does not preserve it.

[asbirlea]

Rebase.

[chandlerc]

In D60833#1472319, @asbirlea wrote:

Simplify patch to preserve MemorySSA in the old pass manager only when the pass is already available (remove *require*).
New pass manager does not preserve it.

Ugh.

Ok, I want to revisit a suggestion I made previously: maybe let's just not enable MemorySSA by default in the old pass manager? Given that it forces you to add all of this code and complexity, it seems like we should just leave it off-by-default there, and enable it by default in the new pass manager only.

Other than the slight "ew"-ness of that, are there any other problems?

[asbirlea]

It's not as much the ew-ness that bothers me.
It's that, if MemorySSA is to be preserved and widely used in the loop pass, then this infrastructure change is needed anyway.

The simplifyLoop API is called from a bunch of other *loop* passes. Whenever these are updated, we'll need to teach this API to make the update (the new pass manager will care too)
Following this patch, it will be much easier to just get MemorySSA analysis pass and pass it along to the API that already does the right thing. This same approach saved me a lot of time when I updated the other Utils. If you notice in this patch, the calls to formDedicatedExitBlocks or SplitBlockPredecessors are already doing the right thing.

You're quite right that this is not a requirement to enable MemorySSA in the new pass manager. I am hoping it is not as big of a change to block it, and that it opens up more paths.
If it turns out to be a blocker, I'm happy to split the EnableMSSALoopDependency flag in 2 for the 2 pass managers and flip just one. What do you think?

[george.burgess.iv]

I don't mean to interrupt the ongoing discussion; just wanted to send a few nits about the MSSA-specific bits. Thanks!

lib/Transforms/Utils/Local.cpp

1903

Would it be better to iterate over the block's MemoryAccess list instead of the entire BB? I'd be happy to have a new removeBlock method or similar in MSSAU to do this.

1908

Do we also want to clean up any Phis that this trivializes (...assuming that's possible), or is the intent for that to be cleaned up later?

[chandlerc]

In D60833#1472530, @asbirlea wrote:

It's not as much the ew-ness that bothers me.
It's that, if MemorySSA is to be preserved and widely used in the loop pass, then this infrastructure change is needed anyway.

The simplifyLoop API is called from a bunch of other *loop* passes. Whenever these are updated, we'll need to teach this API to make the update (the new pass manager will care too)
Following this patch, it will be much easier to just get MemorySSA analysis pass and pass it along to the API that already does the right thing. This same approach saved me a lot of time when I updated the other Utils. If you notice in this patch, the calls to formDedicatedExitBlocks or SplitBlockPredecessors are already doing the right thing.

You're quite right that this is not a requirement to enable MemorySSA in the new pass manager. I am hoping it is not as big of a change to block it, and that it opens up more paths.
If it turns out to be a blocker, I'm happy to split the EnableMSSALoopDependency flag in 2 for the 2 pass managers and flip just one. What do you think?

I see, the fact that this is mostly about getting the utility code to preserve makes lots of sense.

Minor comment below, will look in a bit more detail soon.

include/llvm/Transforms/Utils/LoopSimplify.h

60

Comment needs updating.

[asbirlea]

Address comments.
Moved some updates to MSSAU methods.
Added MSSA updates missed in the previous iteration.

[george.burgess.iv]

MSSA bits LGTM modulo a few nits. Feel free to commit when Chandler is happy.

Thanks again!

lib/Analysis/MemorySSAUpdater.cpp

1258

nit: Would it work just as well to take an ArrayRef<WeakVH> here and drop Start/Stop params? (That way, we can also simplify the loop to a for over UpdatedPHIs)

If not, please make UpdatedPhis a const&

1262

Please clang-format

1290

nit: s/auto */(const )?BasicBlock */ for consistency with elsewhere, please

[asbirlea]

Address comments.

lib/Analysis/MemorySSAUpdater.cpp

1258

Yes, it would work for this patch. I added the range to reuse it in insertDef, where the start and stop are different, but I didn't include that change here since it's not related.
Please let me know if you prefer to have the Start/Stop removed here and re-added in the follow up patch that cleans the other use cases.

[george.burgess.iv]

lib/Analysis/MemorySSAUpdater.cpp

1258

I was hoping more that the ArrayRef would make it so we don't need Start/End to begin with. Slicing/dicing those is trivial, and makes it more obvious what you're doing at the callsite IMO.

I don't feel super strongly either way, though; feel free to do Start/Stop if you think that it's cleaner.

[asbirlea]

Rebase on top of cleanup patch.

lib/Analysis/MemorySSAUpdater.cpp

1258

Done in separate cleanup patch. Thanks for the suggestion!

[chandlerc]

I'm trusting George w/ the MemorySSAUpdater review.

Everything else looks good except for some commented out code I've marked.

lib/Transforms/Utils/LoopSimplify.cpp

823–827

?

841

?

[asbirlea]

Delete left-over comments.

[chandlerc]

(To be explicit, this LGTM, just letting George mark it as accepted when he's happy too.)

[george.burgess.iv]

just letting George mark it as accepted when he's happy too

This CL sparks joy, so LGTM. :)

Thanks again!

[asbirlea]

Thank you both for the review!

[uabelho]

Hi,

With this patch the following starts hitting an assertion:

opt -S -o - memssa.ll -memoryssa -loop-simplify -early-cse-memssa

I get

opt: ../lib/Analysis/MemorySSA.cpp:2019: void llvm::MemorySSA::verifyDefUses(llvm::Function &) const: Assertion `find(predecessors(&B), Phi->getIncomingBlock(I)) != pred_end(&B) && "Incoming phi block not a block predecessor"' failed.

with memssa.ll being

target triple = "x86_64-unknown-linux-gnu"

define void @loop_imm_reg_plus2() {
  br i1 undef, label %bb5, label %bb3

bb5:                                              ; preds = %bb5, %0
  store i16 undef, i16* undef
  br i1 undef, label %bb5, label %bb3

bb3:                                              ; preds = %bb5, %0
  ret void
}

[uabelho]

When the assertion fails we have:

(gdb) call F.dump()

define void @loop_imm_reg_plus2() {
  br i1 undef, label %bb5.preheader, label %bb3

bb5.preheader:                                    ; preds = %0
  br label %bb5

bb5:                                              ; preds = %bb5.preheader, %bb5
  store i16 undef, i16* undef
  br i1 false, label %bb5, label %bb3.loopexit

bb3.loopexit:                                     ; preds = %bb5
  br label %bb3

bb3:                                              ; preds = %bb3.loopexit, %0
  ret void
}

(gdb) call B.getName()
$11 = "bb5"
(gdb) call Phi->dump()
2 = MemoryPhi({%0,liveOnEntry},{bb5,1})

[uabelho]

https://bugs.llvm.org/show_bug.cgi?id=41853

include/llvm/Analysis/MemorySSAUpdater.h

public:
   void insertUse(MemoryUse *Use);
   /// Update the MemoryPhi in `To` following an edge deletion between `From` and
   /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
   void removeEdge(BasicBlock *From, BasicBlock *To);
   /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
   /// following a CFG change that replaced multiple edges (switch) with a direct
   /// branch.
   void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To);
+  /// Update MemorySSA when inserting a unique backedge block for a loop.
+  void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader,
+                                                  BasicBlock *LoopPreheader,
+                                                  BasicBlock *BackedgeBlock);
   /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
   /// the exit blocks and a 1:1 mapping of all blocks and instructions
   /// cloned. This involves duplicating all defs and uses in the cloned blocks
   /// Updating phi nodes in exit block successors is done separately.
   void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
                            ArrayRef<BasicBlock *> ExitBlocks,
                            const ValueToValueMapTy &VM,
                            bool IgnoreIncomingWithNoClones = false);

include/llvm/Transforms/Utils/Local.h

 /// Remove all instructions from a basic block other than it's terminator
 /// and any present EH pad instructions.
 unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
 
 /// Insert an unreachable instruction before the specified
 /// instruction, making it and the rest of the code in the block dead.
 unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,
                              bool PreserveLCSSA = false,
-                             DomTreeUpdater *DTU = nullptr);
+                             DomTreeUpdater *DTU = nullptr,
+                             MemorySSAUpdater *MSSAU = nullptr);
 
 /// Convert the CallInst to InvokeInst with the specified unwind edge basic
 /// block.  This also splits the basic block where CI is located, because
 /// InvokeInst is a terminator instruction.  Returns the newly split basic
 /// block.
 BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                              BasicBlock *UnwindEdge);
 

include/llvm/Transforms/Utils/LoopSimplify.h

 
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class MemorySSAUpdater;
+
 /// This pass is responsible for loop canonicalization.
 class LoopSimplifyPass : public PassInfoMixin<LoopSimplifyPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 /// Simplify each loop in a loop nest recursively.
 ///
 /// This takes a potentially un-simplified loop L (and its children) and turns
 /// it into a simplified loop nest with preheaders and single backedges. It will
 /// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null.
 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE,
-                  AssumptionCache *AC, bool PreserveLCSSA);
+                  AssumptionCache *AC, MemorySSAUpdater *MSSAU,
+                  bool PreserveLCSSA);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H

include/llvm/Transforms/Utils/LoopUtils.h

 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 
 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
-                                   bool PreserveLCSSA);
+                                   MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
 
 /// Ensure that all exit blocks of the loop are dedicated exits.
 ///
 /// For any loop exit block with non-loop predecessors, we split the loop
 /// predecessors to use a dedicated loop exit block. We update the dominator
 /// tree and loop info if provided, and will preserve LCSSA if requested.
 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
                              MemorySSAUpdater *MSSAU, bool PreserveLCSSA);

lib/Analysis/MemorySSAUpdater.cpp

if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
         MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
             NewInsn, GetNewDefiningAccess(MUD->getDefiningAccess()), MUD);
         MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
       }
     }
   }
 }
 
+void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
+    BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
+  auto *MPhi = MSSA->getMemoryAccess(Header);
+  if (!MPhi)
+    return;
+
+  // Create phi node in the backedge block and populate it with the same
+  // incoming values as MPhi. Skip incoming values coming from Preheader.
+  auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
+  bool HasUniqueIncomingValue = true;
+  MemoryAccess *UniqueValue = nullptr;
+  for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
+    BasicBlock *IBB = MPhi->getIncomingBlock(I);
+    MemoryAccess *IV = MPhi->getIncomingValue(I);
+    if (IBB != Preheader) {
+      NewMPhi->addIncoming(IV, IBB);
+      if (HasUniqueIncomingValue) {
+        if (!UniqueValue)
+          UniqueValue = IV;
+        else if (UniqueValue != IV)
+          HasUniqueIncomingValue = false;
+      }
+    }
+  }
+
+  // Update incoming edges into MPhi. Remove all but the incoming edge from
+  // Preheader. Add an edge from NewMPhi
+  auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
+  MPhi->setIncomingValue(0, AccFromPreheader);
+  MPhi->setIncomingBlock(0, Preheader);
+  for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
+    MPhi->unorderedDeleteIncoming(I);
+  MPhi->addIncoming(NewMPhi, BEBlock);
+
+  // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
+  // replaced with the unique value.
+  if (HasUniqueIncomingValue)
+    removeMemoryAccess(NewMPhi);
+}
+
 void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
                                            ArrayRef<BasicBlock *> ExitBlocks,
                                            const ValueToValueMapTy &VMap,
                                            bool IgnoreIncomingWithNoClones) {
   PhiToDefMap MPhiMap;
 
   auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
     assert(Phi && NewPhi && "Invalid Phi nodes.");
for (auto AB = Acc->begin(), AE = Acc->end(); AB != AE;) {
       MemoryAccess *MA = &*AB;
       ++AB;
       MSSA->removeFromLookups(MA);
       MSSA->removeFromLists(MA);
     }
   }
 }
 
 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
     Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
     MemorySSA::InsertionPlace Point) {
   MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
   MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
   return NewAccess;
 }
 
 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
     Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
   assert(I->getParent() == InsertPt->getBlock() &&
          "New and old access must be in the same block");
   MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
   MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
                               InsertPt->getIterator());
   return NewAccess;
 }
 
 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
     Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
   assert(I->getParent() == InsertPt->getBlock() &&
          "New and old access must be in the same block");
   MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
   MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
                               ++InsertPt->getIterator());
   return NewAccess;
 }

lib/Target/PowerPC/PPCCTRLoops.cpp

#endif
 
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // If we don't have a preheader, then insert one. If we already have a
   // preheader, then we can use it (except if the preheader contains a use of
   // the CTR register because some such uses might be reordered by the
   // selection DAG after the mtctr instruction).
   if (!Preheader || mightUseCTR(Preheader))
-    Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
+    Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
   if (!Preheader)
     return MadeChange;
 
   LLVM_DEBUG(dbgs() << "Preheader for exit count: " << Preheader->getName()
                     << "\n");
 
   // Insert the count into the preheader and replace the condition used by the
   // selected branch.

lib/Target/PowerPC/PPCLoopPreIncPrep.cpp

if (Buckets.empty())
     return MadeChange;
 
   BasicBlock *LoopPredecessor = L->getLoopPredecessor();
   // If there is no loop predecessor, or the loop predecessor's terminator
   // returns a value (which might contribute to determining the loop's
   // iteration space), insert a new preheader for the loop.
   if (!LoopPredecessor ||
       !LoopPredecessor->getTerminator()->getType()->isVoidTy()) {
-    LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
+    LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
     if (LoopPredecessor)
       MadeChange = true;
   }
   if (!LoopPredecessor)
     return MadeChange;
 
   LLVM_DEBUG(dbgs() << "PIP: Found " << Buckets.size() << " buckets\n");
 

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

if (!PostLoop.Blocks.empty()) {
     PostL =
         createClonedLoopStructure(&OriginalLoop, OriginalLoop.getParentLoop(),
                                   PostLoop.Map, /* IsSubLoop */ false);
   }
 
   // This function canonicalizes the loop into Loop-Simplify and LCSSA forms.
   auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) {
     formLCSSARecursively(*L, DT, &LI, &SE);
-    simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
+    simplifyLoop(L, &DT, &LI, &SE, nullptr, nullptr, true);
     // Pre/post loops are slow paths, we do not need to perform any loop
     // optimizations on them.
     if (!IsOriginalLoop)
       DisableAllLoopOptsOnLoop(*L);
   };
   if (PreL)
     CanonicalizeLoop(PreL, false);
   if (PostL)

lib/Transforms/Scalar/LoopInterchange.cpp

assert(OuterLoopPreHeader != OuterLoop->getHeader() &&
          InnerLoopPreHeader != InnerLoop->getHeader() && OuterLoopPreHeader &&
          InnerLoopPreHeader && "Guaranteed by loop-simplify form");
   // Ensure that both preheaders do not contain PHI nodes and have single
   // predecessors. This allows us to move them easily. We use
   // InsertPreHeaderForLoop to create an 'extra' preheader, if the existing
   // preheaders do not satisfy those conditions.
   if (isa<PHINode>(OuterLoopPreHeader->begin()) ||
       !OuterLoopPreHeader->getUniquePredecessor())
-    OuterLoopPreHeader = InsertPreheaderForLoop(OuterLoop, DT, LI, true);
+    OuterLoopPreHeader =
+        InsertPreheaderForLoop(OuterLoop, DT, LI, nullptr, true);
   if (InnerLoopPreHeader == OuterLoop->getHeader())
-    InnerLoopPreHeader = InsertPreheaderForLoop(InnerLoop, DT, LI, true);
+    InnerLoopPreHeader =
+        InsertPreheaderForLoop(InnerLoop, DT, LI, nullptr, true);
 
   // Adjust the loop preheader
   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
   BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
   BasicBlock *InnerLoopLatchPredecessor =

lib/Transforms/Scalar/LoopUnrollPass.cpp

PreservedAnalyses LoopUnrollPass::run(Function &F,
   bool Changed = false;
 
   // The unroller requires loops to be in simplified form, and also needs LCSSA.
   // Since simplification may add new inner loops, it has to run before the
   // legality and profitability checks. This means running the loop unroller
   // will simplify all loops, regardless of whether anything end up being
   // unrolled.
   for (auto &L : LI) {
-    Changed |= simplifyLoop(L, &DT, &LI, &SE, &AC, false /* PreserveLCSSA */);
+    Changed |=
+        simplifyLoop(L, &DT, &LI, &SE, &AC, nullptr, false /* PreserveLCSSA */);
     Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
   }
 
   SmallVector<Loop *, 8> Worklist = appendLoopsToWorklist(LI);
 
   while (!Worklist.empty()) {
     // Because the LoopInfo stores the loops in RPO, we walk the worklist
     // from back to front so that we work forward across the CFG, which

lib/Transforms/Utils/Local.cpp

while (EndInst != &BB->front()) {
     if (!isa<DbgInfoIntrinsic>(Inst))
       ++NumDeadInst;
     Inst->eraseFromParent();
   }
   return NumDeadInst;
 }
 
 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
-                                   bool PreserveLCSSA, DomTreeUpdater *DTU) {
+                                   bool PreserveLCSSA, DomTreeUpdater *DTU,
+                                   MemorySSAUpdater *MSSAU) {
   BasicBlock *BB = I->getParent();
   std::vector <DominatorTree::UpdateType> Updates;
 
+  if (MSSAU) {
+    BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
+    while (BBI != BBE)
+      MSSAU->removeMemoryAccess(&*(BBI++));
+    for (BasicBlock *Successor : successors(BB))
+      if (MemoryPhi *MPhi = MSSAU->getMemorySSA()->getMemoryAccess(Successor))
+        MPhi->unorderedDeleteIncomingBlock(BB);
+  }
+
   // Loop over all of the successors, removing BB's entry from any PHI
   // nodes.
   if (DTU)
     Updates.reserve(BB->getTerminator()->getNumSuccessors());
   for (BasicBlock *Successor : successors(BB)) {
     Successor->removePredecessor(BB, PreserveLCSSA);
     if (DTU)
       Updates.push_back({DominatorTree::Delete, BB, Successor});

lib/Transforms/Utils/LoopSimplify.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-simplify"
 
 STATISTIC(NumNested  , "Number of nested loops split out");
 
 // If the block isn't already, move the new block to right after some 'outside
static void placeSplitBlockCarefully(BasicBlock *NewBB,
   NewBB->moveAfter(FoundBB);
 }
 
 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
 /// preheader, this method is called to insert one.  This method has two phases:
 /// preheader insertion and analysis updating.
 ///
 BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
-                                         LoopInfo *LI, bool PreserveLCSSA) {
+                                         LoopInfo *LI, MemorySSAUpdater *MSSAU,
+                                         bool PreserveLCSSA) {
   BasicBlock *Header = L->getHeader();
 
   // Compute the set of predecessors of the loop that are not in the loop.
   SmallVector<BasicBlock*, 8> OutsideBlocks;
   for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
        PI != PE; ++PI) {
     BasicBlock *P = *PI;
     if (!L->contains(P)) {         // Coming in from outside the loop?
       // If the loop is branched to from an indirect terminator, we won't
       // be able to fully transform the loop, because it prohibits
       // edge splitting.
       if (P->getTerminator()->isIndirectTerminator())
         return nullptr;
 
       // Keep track of it.
       OutsideBlocks.push_back(P);
     }
   }
 
   // Split out the loop pre-header.
   BasicBlock *PreheaderBB;
   PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
-                                       LI, nullptr, PreserveLCSSA);
+                                       LI, MSSAU, PreserveLCSSA);
   if (!PreheaderBB)
     return nullptr;
 
   LLVM_DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
                     << PreheaderBB->getName() << "\n");
 
   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
   // code layout too horribly.

 /// that change in the "outer" loop, but not in the "inner" loop.
 ///
 /// If we are able to separate out a loop, return the new outer loop that was
 /// created.
 ///
 static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
                                 DominatorTree *DT, LoopInfo *LI,
                                 ScalarEvolution *SE, bool PreserveLCSSA,
-                                AssumptionCache *AC) {
+                                AssumptionCache *AC, MemorySSAUpdater *MSSAU) {
   // Don't try to separate loops without a preheader.
   if (!Preheader)
     return nullptr;
 
   // The header is not a landing pad; preheader insertion should ensure this.
   BasicBlock *Header = L->getHeader();
   assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
 
static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
 
   // If ScalarEvolution is around and knows anything about values in
   // this loop, tell it to forget them, because we're about to
   // substantially change it.
   if (SE)
     SE->forgetLoop(L);
 
   BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
-                                             DT, LI, nullptr, PreserveLCSSA);
+                                             DT, LI, MSSAU, PreserveLCSSA);
 
   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
   // code layout too horribly.
   placeSplitBlockCarefully(NewBB, OuterLoopPreds, L);
 
   // Create the new outer loop.
   Loop *NewOuter = LI->AllocateLoop();
 
if (!BlocksInL.count(BB)) {
         OuterLoopBlocks.push_back(BB);
       }
       --i;
     }
   }
 
   // Split edges to exit blocks from the inner loop, if they emerged in the
   // process of separating the outer one.
-  formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
+  formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA);
 
   if (PreserveLCSSA) {
     // Fix LCSSA form for L. Some values, which previously were only used inside
     // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
     // in corresponding exit blocks.
     // We don't need to form LCSSA recursively, because there cannot be uses
     // inside a newly created loop of defs from inner loops as those would
     // already be a use of an LCSSA phi node.
     formLCSSA(*L, *DT, LI, SE);
 
     assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
            "LCSSA is broken after separating nested loops!");
   }
 
   return NewOuter;
 }
 
 /// This method is called when the specified loop has more than one
 /// backedge in it.
 ///
 /// If this occurs, revector all of these backedges to target a new basic block
 /// and have that block branch to the loop header.  This ensures that loops
 /// have exactly one backedge.
 static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
-                                             DominatorTree *DT, LoopInfo *LI) {
+                                             DominatorTree *DT, LoopInfo *LI,
+                                             MemorySSAUpdater *MSSAU) {
   assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
 
   // Get information about the loop
   BasicBlock *Header = L->getHeader();
   Function *F = Header->getParent();
 
   // Unique backedge insertion currently depends on having a preheader.
   if (!Preheader)
static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
 
   // Update Loop Information - we know that this block is now in the current
   // loop and all parent loops.
   L->addBasicBlockToLoop(BEBlock, *LI);
 
   // Update dominator information
   DT->splitBlock(BEBlock);
 
+  if (MSSAU)
+    MSSAU->updatePhisWhenInsertingUniqueBackedgeBlock(Header, Preheader,
+                                                      BEBlock);
+
   return BEBlock;
 }
 
 /// Simplify one loop and queue further loops for simplification.
 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
                             DominatorTree *DT, LoopInfo *LI,
                             ScalarEvolution *SE, AssumptionCache *AC,
-                            bool PreserveLCSSA) {
+                            MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
   bool Changed = false;
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
+
 ReprocessLoop:
 
   // Check to see that no blocks (other than the header) in this loop have
   // predecessors that are not in the loop.  This is not valid for natural
   // loops, but can occur if the blocks are unreachable.  Since they are
   // unreachable we can just shamelessly delete those CFG edges!
   for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
        BB != E; ++BB) {
for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
     // Delete each unique out-of-loop (and thus dead) predecessor.
     for (BasicBlock *P : BadPreds) {
 
       LLVM_DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
                         << P->getName() << "\n");
 
       // Zap the dead pred's terminator and replace it with unreachable.
       Instruction *TI = P->getTerminator();
-      changeToUnreachable(TI, /*UseLLVMTrap=*/false, PreserveLCSSA);
+      changeToUnreachable(TI, /*UseLLVMTrap=*/false, PreserveLCSSA,
+                          /*DTU=*/nullptr, MSSAU);
       Changed = true;
     }
   }
 
   // If there are exiting blocks with branches on undef, resolve the undef in
   // the direction which will exit the loop. This will help simplify loop
   // trip count computations.
   SmallVector<BasicBlock*, 8> ExitingBlocks;
if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
 
           Changed = true;
         }
       }
 
   // Does the loop already have a preheader?  If so, don't insert one.
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader) {
-    Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);
+    Preheader = InsertPreheaderForLoop(L, DT, LI, MSSAU, PreserveLCSSA);
     if (Preheader)
       Changed = true;
   }
 
   // Next, check to make sure that all exit nodes of the loop only have
   // predecessors that are inside of the loop.  This check guarantees that the
   // loop preheader/header will dominate the exit blocks.  If the exit block has
   // predecessors from outside of the loop, split the edge now.
-  if (formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA))
+  if (formDedicatedExitBlocks(L, DT, LI, MSSAU, PreserveLCSSA))
     Changed = true;
 
   // If the header has more than two predecessors at this point (from the
   // preheader and from multiple backedges), we must adjust the loop.
   BasicBlock *LoopLatch = L->getLoopLatch();
   if (!LoopLatch) {
     // If this is really a nested loop, rip it out into a child loop.  Don't do
     // this for loops with a giant number of backedges, just factor them into a
     // common backedge instead.
     if (L->getNumBackEdges() < 8) {
-      if (Loop *OuterL =
-              separateNestedLoop(L, Preheader, DT, LI, SE, PreserveLCSSA, AC)) {
+      if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE,
+                                            PreserveLCSSA, AC, MSSAU)) {
         ++NumNested;
         // Enqueue the outer loop as it should be processed next in our
         // depth-first nest walk.
         Worklist.push_back(OuterL);
 
         // This is a big restructuring change, reprocess the whole loop.
         Changed = true;
         // GCC doesn't tail recursion eliminate this.
         // FIXME: It isn't clear we can't rely on LLVM to TRE this.
         goto ReprocessLoop;
       }
     }
 
     // If we either couldn't, or didn't want to, identify nesting of the loops,
     // insert a new block that all backedges target, then make it jump to the
     // loop header.
-    LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI);
+    LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI, MSSAU);
     if (LoopLatch)
       Changed = true;
   }
 
   const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
 
   // Scan over the PHI nodes in the loop header.  Since they now have only two
   // incoming values (the loop is canonicalized), we may have simplified the PHI
ReprocessLoop:
   }
 
   // Changing exit conditions for blocks may affect exit counts of this loop and
   // any of its paretns, so we must invalidate the entire subtree if we've made
   // any changes.
   if (Changed && SE)
     SE->forgetTopmostLoop(L);
 
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
+
   return Changed;
 }
 
 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
                         ScalarEvolution *SE, AssumptionCache *AC,
-                        bool PreserveLCSSA) {
+                        MemorySSAUpdater *MSSAU, bool PreserveLCSSA) {
   bool Changed = false;
 
 #ifndef NDEBUG
   // If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA
   // form.
   if (PreserveLCSSA) {
     assert(DT && "DT not available.");
     assert(LI && "LI not available.");
#endif
   // order. We can use this simple process because loops form a tree.
   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
     Loop *L2 = Worklist[Idx];
     Worklist.append(L2->begin(), L2->end());
   }
 
   while (!Worklist.empty())
     Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
-                               AC, PreserveLCSSA);
+                               AC, MSSAU, PreserveLCSSA);
 
   return Changed;
 }
 
 namespace {
   struct LoopSimplify : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     LoopSimplify() : FunctionPass(ID) {
void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addPreserved<BasicAAWrapperPass>();
       AU.addPreserved<AAResultsWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addPreserved<ScalarEvolutionWrapperPass>();
       AU.addPreserved<SCEVAAWrapperPass>();
       AU.addPreservedID(LCSSAID);
       AU.addPreserved<DependenceAnalysisWrapperPass>();
       AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
+      AU.addPreserved<MemorySSAWrapperPass>();
     }
 
     /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
     void verifyAnalysis() const override;
   };
 }
 
 char LoopSimplify::ID = 0;

 bool LoopSimplify::runOnFunction(Function &F) {
   bool Changed = false;
   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
   ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
   AssumptionCache *AC =
       &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+  MemorySSA *MSSA = nullptr;
+  std::unique_ptr<MemorySSAUpdater> MSSAU;
+  if (EnableMSSALoopDependency) {
+    auto *MSSAAnalysis = getAnalysisIfAvailable<MemorySSAWrapperPass>();
+    if (MSSAAnalysis) {
+      MSSA = &MSSAAnalysis->getMSSA();
+      MSSAU = make_unique<MemorySSAUpdater>(MSSA);
+    }
+  }
 
   bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 
   // Simplify each loop nest in the function.
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
-    Changed |= simplifyLoop(*I, DT, LI, SE, AC, PreserveLCSSA);
+    Changed |= simplifyLoop(*I, DT, LI, SE, AC, MSSAU.get(), PreserveLCSSA);
 
 #ifndef NDEBUG
   if (PreserveLCSSA) {
     bool InLCSSA = all_of(
         *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
     assert(InLCSSA && "LCSSA is broken after loop-simplify.");
   }
 #endif
   return Changed;
 }
 
 PreservedAnalyses LoopSimplifyPass::run(Function &F,
                                         FunctionAnalysisManager &AM) {
   bool Changed = false;
   LoopInfo *LI = &AM.getResult<LoopAnalysis>(F);
   DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   ScalarEvolution *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
   AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
 
   // Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA
-  // after simplifying the loops.
+  // after simplifying the loops. MemorySSA is not preserved either.
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
-    Changed |= simplifyLoop(*I, DT, LI, SE, AC, /*PreserveLCSSA*/ false);
+    Changed |=
+        simplifyLoop(*I, DT, LI, SE, AC, nullptr, /*PreserveLCSSA*/ false);
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<LoopAnalysis>();
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
   PA.preserve<SCEVAA>();
   PA.preserve<ScalarEvolutionAnalysis>();
   PA.preserve<DependenceAnalysis>();
+  PA.preserve<AAManager>();
+  // In the new pass manager, LoopSimplify does *not* preserve
+  // MemorySSAAnalysis.
   return PA;
 }
 
 // FIXME: Restore this code when we re-enable verification in verifyAnalysis
 // below.
 #if 0
 static void verifyLoop(Loop *L) {
   // Verify subloops.

lib/Transforms/Utils/LoopUnroll.cpp

if (OuterL) {
         formLCSSARecursively(*FixLCSSALoop, *DT, LI, SE);
       } else if (PreserveLCSSA) {
         assert(OuterL->isLCSSAForm(*DT) &&
                "Loops should be in LCSSA form after loop-unroll.");
       }
 
       // TODO: That potentially might be compile-time expensive. We should try
       // to fix the loop-simplified form incrementally.
-      simplifyLoop(OuterL, DT, LI, SE, AC, PreserveLCSSA);
+      simplifyLoop(OuterL, DT, LI, SE, AC, nullptr, PreserveLCSSA);
     } else {
       // Simplify loops for which we might've broken loop-simplify form.
       for (Loop *SubLoop : LoopsToSimplify)
-        simplifyLoop(SubLoop, DT, LI, SE, AC, PreserveLCSSA);
+        simplifyLoop(SubLoop, DT, LI, SE, AC, nullptr, PreserveLCSSA);
     }
   }
 
   return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
                           : LoopUnrollResult::PartiallyUnrolled;
 }
 
 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata

lib/Transforms/Utils/LoopUnrollPeel.cpp

#endif
 
   if (Loop *ParentLoop = L->getParentLoop())
     L = ParentLoop;
 
   // We modified the loop, update SE.
   SE->forgetTopmostLoop(L);
 
   // FIXME: Incrementally update loop-simplify
-  simplifyLoop(L, DT, LI, SE, AC, PreserveLCSSA);
+  simplifyLoop(L, DT, LI, SE, AC, nullptr, PreserveLCSSA);
 
   NumPeeled++;
 
   return true;
 }

lib/Transforms/Vectorize/LoopVectorize.cpp

bool LoopVectorizePass::runImpl(
   bool Changed = false;
 
   // The vectorizer requires loops to be in simplified form.
   // Since simplification may add new inner loops, it has to run before the
   // legality and profitability checks. This means running the loop vectorizer
   // will simplify all loops, regardless of whether anything end up being
   // vectorized.
   for (auto &L : *LI)
-    Changed |= simplifyLoop(L, DT, LI, SE, AC, false /* PreserveLCSSA */);
+    Changed |=
+        simplifyLoop(L, DT, LI, SE, AC, nullptr, false /* PreserveLCSSA */);
 
   // Build up a worklist of inner-loops to vectorize. This is necessary as
   // the act of vectorizing or partially unrolling a loop creates new loops
   // and can invalidate iterators across the loops.
   SmallVector<Loop *, 8> Worklist;
 
   for (Loop *L : *LI)
     collectSupportedLoops(*L, LI, ORE, Worklist);