Update MemorySSA in LoopRotate.

[asbirlea]

Summary

Teach LoopRotate to preserve MemorySSA.
Enable tests for correctness, dependency disabled by default.

[asbirlea]

Enable tests. Add new tests to check analysis is preserved.

[asbirlea]

Update test and format.

[asbirlea]

Moving the MSSA after cloning earlier to avoid the ValueMap invalidation.
Adding another test.
And ping.

[greened]

lib/Transforms/Scalar/LoopRotation.cpp

49

Why not just pass the Optional?

106

Again, maybe just pass the Optional.

lib/Transforms/Utils/LoopRotationUtils.cpp

59

Use an Optional here?

276

These tests should remain the same with an Optional.

[asbirlea]

lib/Transforms/Scalar/LoopRotation.cpp

49

I'm inclined to prefer using the pointer just due to consistency with the other passes + the hope that this won't be Optional forever :).

If you or other reviewers strongly prefer passing the Optional, please let me know and I'll update here and in all other passes.

[asbirlea]

Update pr35210.ll after recent upstream changes.

[greened]

lib/Transforms/Scalar/LoopRotation.cpp

49

I don't have a strong position on this, just throwing it out as an idea. Using an optional does eliminate the ternary operations and would make the code a bit cleaner.

How expensive is MemorySSA? I'm not sure we can guarantee it will be available so it might always have to be optional.

[asbirlea]

lib/Transforms/Scalar/LoopRotation.cpp

49

It can be expensive if not used but it should be cheaper than MemoryDependenceAnalysis the AliasSetTracker.
End goal is to use it in LICM instead of AST, and in BBUtils instead of MemoryDependenceAnalysis. There are probably others, but these are on my list for now.

I tried to go ahead and make the change to Optional, but I end up moving the ternary somewhere else: either in the constructor for LoopRotate, or in each call to a BasicBlockUtil (e.g. MergeBlockIntoPredecessor or CriticalEdgeSplittingOptions).

In utils, it seems the norm is to use pointers and check for null. Not saying using an Optional wouldn't be better, but it will require having all passes changed to pass Optional as well in the same patch.
I think such a refactoring should be separate from this patch.
What do you think?

[greened]

LGTM, but I don't know if I should be the one to sign off on this since I've never touched LoopRotate.

lib/Transforms/Scalar/LoopRotation.cpp

49

Yeah, that sounds fine to me. I'm fine with the way this is. Was just wondering if Optional might make it cleaner, but it sounds like that would overly complicate this patch and is better left for a later change. Thanks!

[chandlerc]

Minor comments on test case, otherwise this LGTM. Feel free to submit with a minimized test case.

test/Transforms/LoopRotate/preserve-mssa.ll

130–136

Can this test case be minimized some to remove all these atributes and other unnecessary IR boilerplate?

[asbirlea]

Test updated. Thank you for the review!

[lebedev.ri]

llvm/trunk/lib/Transforms/Utils/LoopRotationUtils.cpp

682–687 ↗

(On Diff #171013)

@asbirlea @fhahn

Is this actually correct?
Don't you want to run verification after actually doing the changes?
I.e. shouldn't this be

{
  if (MSSAU && VerifyMemorySSA)
    MSSAU->getMemorySSA()->verifyMemorySSA();
  LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
                IsUtilMode);
  bool Changed = LR.processLoop(L);
  if (MSSAU && VerifyMemorySSA)
    MSSAU->getMemorySSA()->verifyMemorySSA();
  return Changed;
}

[fhahn]

llvm/trunk/lib/Transforms/Utils/LoopRotationUtils.cpp

682–687 ↗

(On Diff #171013)

Yeah the code in the patch doesn't look right, given that the actual modifications happen in processLoop.

[asbirlea]

llvm/trunk/lib/Transforms/Utils/LoopRotationUtils.cpp

682–687 ↗

(On Diff #171013)

It's correct, but unnecessary. Thank you for noticing!
That verification can be removed, since there are additional verificatons inside LoopRotate::rotateLoop that should cover the need to verify after the LR.processLoop(L); call.

[fhahn]

llvm/trunk/lib/Transforms/Utils/LoopRotationUtils.cpp

682–687 ↗

(On Diff #171013)

I dropped the verify calls there in 9ea0d8c38fc5

include/llvm/Transforms/Utils/LoopRotationUtils.h

 #define LLVM_TRANSFORMS_UTILS_LOOPROTATIONUTILS_H
 
 namespace llvm {
 
 class AssumptionCache;
 class DominatorTree;
 class Loop;
 class LoopInfo;
+class MemorySSAUpdater;
 class ScalarEvolution;
 struct SimplifyQuery;
 class TargetTransformInfo;
 
 /// Convert a loop into a loop with bottom test. It may
 /// perform loop latch simplication as well if the flag RotationOnly
 /// is false. The flag Threshold represents the size threshold of the loop
 /// header. If the loop header's size exceeds the threshold, the loop rotation
 /// will give up. The flag IsUtilMode controls the heuristic used in the
 /// LoopRotation. If it is true, the profitability heuristic will be ignored.
 bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
                   AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE,
-                  const SimplifyQuery &SQ, bool RotationOnly,
-                  unsigned Threshold, bool IsUtilMode);
+                  MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ,
+                  bool RotationOnly, unsigned Threshold, bool IsUtilMode);
 
 } // namespace llvm
 
 #endif

lib/Transforms/Scalar/LoopRotation.cpp

 // This file implements Loop Rotation Pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopRotation.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/LoopRotationUtils.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;

 
 PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM,
                                       LoopStandardAnalysisResults &AR,
                                       LPMUpdater &) {
   int Threshold = EnableHeaderDuplication ? DefaultRotationThreshold : 0;
   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
   const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL);
 
-  bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE, SQ,
-                              false, Threshold, false);
+  Optional<MemorySSAUpdater> MSSAU;
+  if (AR.MSSA)
+    MSSAU = MemorySSAUpdater(AR.MSSA);
+  bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE,
+                              MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
+                              SQ, false, Threshold, false);
 
   if (!Changed)
     return PreservedAnalyses::all();
 
+  if (AR.MSSA && VerifyMemorySSA)
+    AR.MSSA->verifyMemorySSA();
+
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 
 class LoopRotateLegacyPass : public LoopPass {
   unsigned MaxHeaderSize;
 
 public:
   static char ID; // Pass ID, replacement for typeid
   LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) {
     initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry());
     if (SpecifiedMaxHeaderSize == -1)
       MaxHeaderSize = DefaultRotationThreshold;
     else
       MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
   }
 
   // LCSSA form makes instruction renaming easier.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    if (EnableMSSALoopDependency) {
+      AU.addRequired<MemorySSAWrapperPass>();
+      AU.addPreserved<MemorySSAWrapperPass>();
+    }
     getLoopAnalysisUsage(AU);
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
     Function &F = *L->getHeader()->getParent();
 
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
     auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
     auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     auto *SE = SEWP ? &SEWP->getSE() : nullptr;
     const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
-    return LoopRotation(L, LI, TTI, AC, DT, SE, SQ, false, MaxHeaderSize,
-                        false);
+    Optional<MemorySSAUpdater> MSSAU;
+    if (EnableMSSALoopDependency) {
+      MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
+      MSSAU = MemorySSAUpdater(MSSA);
+    }
+    return LoopRotation(L, LI, TTI, AC, DT, SE,
+                        MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ,
+                        false, MaxHeaderSize, false);
   }
 };
 }
 
 char LoopRotateLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
                     false)
 
 Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
   return new LoopRotateLegacyPass(MaxHeaderSize);
 }

lib/Transforms/Utils/LoopRotationUtils.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"

 /// A simple loop rotation transformation.
 class LoopRotate {
   const unsigned MaxHeaderSize;
   LoopInfo *LI;
   const TargetTransformInfo *TTI;
   AssumptionCache *AC;
   DominatorTree *DT;
   ScalarEvolution *SE;
+  MemorySSAUpdater *MSSAU;
   const SimplifyQuery &SQ;
   bool RotationOnly;
   bool IsUtilMode;
 
 public:
   LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
              const TargetTransformInfo *TTI, AssumptionCache *AC,
-             DominatorTree *DT, ScalarEvolution *SE, const SimplifyQuery &SQ,
-             bool RotationOnly, bool IsUtilMode)
+             DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
+             const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode)
       : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE),
-        SQ(SQ), RotationOnly(RotationOnly), IsUtilMode(IsUtilMode) {}
+        MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly),
+        IsUtilMode(IsUtilMode) {}
   bool processLoop(Loop *L);
 
 private:
   bool rotateLoop(Loop *L, bool SimplifiedLatch);
   bool simplifyLoopLatch(Loop *L);
 };
 } // end anonymous namespace
 
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   // in its header will soon be invalidated. We should also invalidate
   // all outer loops because insertion and deletion of blocks that happens
   // during the rotation may violate invariants related to backedge taken
   // infos in them.
   if (SE)
     SE->forgetTopmostLoop(L);
 
   LLVM_DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
 
   // Find new Loop header. NewHeader is a Header's one and only successor
   // that is inside loop.  Header's other successor is outside the
   // loop.  Otherwise loop is not suitable for rotation.
   BasicBlock *Exit = BI->getSuccessor(0);
   BasicBlock *NewHeader = BI->getSuccessor(1);
   if (L->contains(Exit))
     std::swap(Exit, NewHeader);
for (BasicBlock::iterator BI = SuccBB->begin();
          PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
       PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
 
   // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
   // OrigPreHeader's old terminator (the original branch into the loop), and
   // remove the corresponding incoming values from the PHI nodes in OrigHeader.
   LoopEntryBranch->eraseFromParent();
 
+  // Update MemorySSA before the rewrite call below changes the 1:1
+  // instruction:cloned_instruction_or_value mapping in ValueMap.
+  if (MSSAU) {
+    ValueMap[OrigHeader] = OrigPreheader;
+    MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader, ValueMap);
+  }
 
   SmallVector<PHINode*, 2> InsertedPHIs;
   // If there were any uses of instructions in the duplicated block outside the
   // loop, update them, inserting PHI nodes as required
   RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap,
                                   &InsertedPHIs);
 
   // Attach dbg.value intrinsics to the new phis if that phi uses a value that
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   if (DT) {
     // The OrigPreheader branches to the NewHeader and Exit now. Then, inform
     // the DT about the removed edge to the OrigHeader (that got removed).
     SmallVector<DominatorTree::UpdateType, 3> Updates;
     Updates.push_back({DominatorTree::Insert, OrigPreheader, Exit});
     Updates.push_back({DominatorTree::Insert, OrigPreheader, NewHeader});
     Updates.push_back({DominatorTree::Delete, OrigPreheader, OrigHeader});
     DT->applyUpdates(Updates);
+
+    if (MSSAU) {
+      MSSAU->applyUpdates(Updates, *DT);
+      if (VerifyMemorySSA)
+        MSSAU->getMemorySSA()->verifyMemorySSA();
+    }
   }
 
   // At this point, we've finished our major CFG changes.  As part of cloning
   // the loop into the preheader we've simplified instructions and the
   // duplicated conditional branch may now be branching on a constant.  If it is
   // branching on a constant and if that constant means that we enter the loop,
   // then we fold away the cond branch to an uncond branch.  This simplifies the
   // loop in cases important for nested loops, and it also means we don't have
   // to split as many edges.
   BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
   assert(PHBI->isConditional() && "Should be clone of BI condbr!");
   if (!isa<ConstantInt>(PHBI->getCondition()) ||
       PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
           NewHeader) {
     // The conditional branch can't be folded, handle the general case.
     // Split edges as necessary to preserve LoopSimplify form.
 
     // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
     // thus is not a preheader anymore.
     // Split the edge to form a real preheader.
     BasicBlock *NewPH = SplitCriticalEdge(
         OrigPreheader, NewHeader,
-        CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA());
+        CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
     NewPH->setName(NewHeader->getName() + ".lr.ph");
 
     // Preserve canonical loop form, which means that 'Exit' should have only
     // one predecessor. Note that Exit could be an exit block for multiple
     // nested loops, causing both of the edges to now be critical and need to
     // be split.
     SmallVector<BasicBlock *, 4> ExitPreds(pred_begin(Exit), pred_end(Exit));
     bool SplitLatchEdge = false;
     for (BasicBlock *ExitPred : ExitPreds) {
       // We only need to split loop exit edges.
       Loop *PredLoop = LI->getLoopFor(ExitPred);
       if (!PredLoop || PredLoop->contains(Exit))
         continue;
       if (isa<IndirectBrInst>(ExitPred->getTerminator()))
         continue;
       SplitLatchEdge |= L->getLoopLatch() == ExitPred;
       BasicBlock *ExitSplit = SplitCriticalEdge(
           ExitPred, Exit,
-          CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA());
+          CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA());
       ExitSplit->moveBefore(Exit);
     }
     assert(SplitLatchEdge &&
            "Despite splitting all preds, failed to split latch exit?");
   } else {
     // We can fold the conditional branch in the preheader, this makes things
     // simpler. The first step is to remove the extra edge to the Exit block.
     Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
     BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
     NewBI->setDebugLoc(PHBI->getDebugLoc());
     PHBI->eraseFromParent();
 
     // With our CFG finalized, update DomTree if it is available.
     if (DT) DT->deleteEdge(OrigPreheader, Exit);
+
+    // Update MSSA too, if available.
+    if (MSSAU)
+      MSSAU->removeEdge(OrigPreheader, Exit);
   }
 
   assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
   assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
 
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
+
   // Now that the CFG and DomTree are in a consistent state again, try to merge
   // the OrigHeader block into OrigLatch.  This will succeed if they are
   // connected by an unconditional branch.  This is just a cleanup so the
   // emitted code isn't too gross in this common case.
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
-  MergeBlockIntoPredecessor(OrigHeader, &DTU, LI);
+  MergeBlockIntoPredecessor(OrigHeader, &DTU, LI, MSSAU);
+
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
 
   LLVM_DEBUG(dbgs() << "LoopRotation: into "; L->dump());
 
   ++NumRotated;
   return true;
 }
 
 /// Determine whether the instructions in this range may be safely and cheaply
bool LoopRotate::simplifyLoopLatch(Loop *L) {
 
   if (!shouldSpeculateInstrs(Latch->begin(), Jmp->getIterator(), L))
     return false;
 
   LLVM_DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
                     << LastExit->getName() << "\n");
 
   // Hoist the instructions from Latch into LastExit.
+  Instruction *FirstLatchInst = &*(Latch->begin());
   LastExit->getInstList().splice(BI->getIterator(), Latch->getInstList(),
                                  Latch->begin(), Jmp->getIterator());
 
+  // Update MemorySSA
+  if (MSSAU)
+    MSSAU->moveAllAfterMergeBlocks(Latch, LastExit, FirstLatchInst);
+
   unsigned FallThruPath = BI->getSuccessor(0) == Latch ? 0 : 1;
   BasicBlock *Header = Jmp->getSuccessor(0);
   assert(Header == L->getHeader() && "expected a backward branch");
 
   // Remove Latch from the CFG so that LastExit becomes the new Latch.
   BI->setSuccessor(FallThruPath, Header);
   Latch->replaceSuccessorsPhiUsesWith(LastExit);
   Jmp->eraseFromParent();
 
   // Nuke the Latch block.
   assert(Latch->empty() && "unable to evacuate Latch");
   LI->removeBlock(Latch);
   if (DT)
     DT->eraseNode(Latch);
   Latch->eraseFromParent();
+
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
+
   return true;
 }
 
 /// Rotate \c L, and return true if any modification was made.
 bool LoopRotate::processLoop(Loop *L) {
   // Save the loop metadata.
   MDNode *LoopMD = L->getLoopID();
 
bool LoopRotate::processLoop(Loop *L) {
 
   return MadeChange || SimplifiedLatch;
 }
 
 
 /// The utility to convert a loop into a loop with bottom test.
 bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
                         AssumptionCache *AC, DominatorTree *DT,
-                        ScalarEvolution *SE, const SimplifyQuery &SQ,
-                        bool RotationOnly = true,
+                        ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
+                        const SimplifyQuery &SQ, bool RotationOnly = true,
                         unsigned Threshold = unsigned(-1),
                         bool IsUtilMode = true) {
-  LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, SQ, RotationOnly, IsUtilMode);
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
+  LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
+                IsUtilMode);
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
 
   return LR.processLoop(L);
 }

test/Transforms/LoopRotate/2009-01-25-SingleEntryPhi.ll

 ; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -disable-output
+; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 ; PR3408
 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"
 target triple = "x86_64-unknown-linux-gnu"
   %struct.Cls = type { i32, i8, [2 x %struct.Cls*], [2 x %struct.Lit*] }
   %struct.Lit = type { i8 }
 
 define void @picosat_main_bb13.i.i71.outer_bb132.i.i.i.outer(%struct.Cls**, %struct.Cls**, i32 %collect.i.i.i.1.lcssa, i32 %lcollect.i.i.i.2.lcssa, %struct.Cls*** %rhead.tmp.0236.out, i32* %collect.i.i.i.2.out, i32* %lcollect.i.i.i.3.ph.ph.ph.out) nounwind {
 newFuncRoot:

test/Transforms/LoopRotate/PhiRename-1.ll

 ; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -S | FileCheck %s
+; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 ; CHECK-NOT: [ {{.}}tmp224
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"
 
   %struct.FILE = type { i8*, i32, i32, i16, i16, %struct.__sbuf, i32, i8*, i32 (i8*)*, i32 (i8*, i8*, i32)*, i64 (i8*, i64, i32)*, i32 (i8*, i8*, i32)*, %struct.__sbuf, %struct.__sFILEX*, i32, [3 x i8], [1 x i8], %struct.__sbuf, i32, i64 }
   %struct.Index_Map = type { i32, %struct.item_set** }
   %struct.Item = type { [4 x i16], %struct.rule* }
   %struct.__sFILEX = type opaque

test/Transforms/LoopRotate/PhiSelfReference-1.ll

 ; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -disable-output
+; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 ; ModuleID = 'PhiSelfReference-1.bc'
 
 define void @snrm2(i32 %incx) {
 entry:
   br i1 false, label %START, label %return
 
 START:    ; preds = %entry
   br i1 false, label %bb85, label %cond_false93

test/Transforms/LoopRotate/alloca.ll

 ; RUN: opt < %s -loop-rotate -S | FileCheck %s
+; RUN: opt < %s -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 ; Test alloca in -loop-rotate.
 
 ; We expect a different value for %ptr each iteration (according to the
 ; definition of alloca). I.e. each @use must be paired with an alloca.
 
 ; CHECK: call void @use(i8* %
 ; CHECK: %ptr = alloca i8

test/Transforms/LoopRotate/basic.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
+; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 ; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop(rotate)' < %s | FileCheck %s
+; RUN: opt -S -passes='require<targetir>,require<assumptions>,loop(rotate)' -enable-mssa-loop-dependency=true -verify-memoryssa  < %s | FileCheck %s
 
 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"
 target triple = "x86_64-apple-darwin10.0.0"
 
 ; PR5319 - The "arrayidx" gep should be hoisted, not duplicated.  We should
 ; end up with one phi node.
 define void @test1() nounwind ssp {
 ; CHECK-LABEL: @test1(

test/Transforms/LoopRotate/catchret.ll

 ; RUN: opt < %s -loop-rotate -S | FileCheck %s
+; RUN: opt < %s -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 target triple = "x86_64-pc-windows-msvc"
 
 declare void @always_throws()
 
 define i32 @test() personality i8* bitcast (i32 (...)* @__CxxFrameHandler3 to i8*) {
 entry:
   invoke void @always_throws()

test/Transforms/LoopRotate/convergent.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
+; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 @e = global i32 10
 
 declare void @f1(i32) convergent
 declare void @f2(i32)
 
 ; The call to f1 in the loop header shouldn't be duplicated (meaning, loop
 ; rotation shouldn't occur), because f1 is convergent.

test/Transforms/LoopRotate/crash.ll

 ; RUN: opt -loop-rotate -disable-output -verify-dom-info -verify-loop-info < %s
+; RUN: opt -loop-rotate -disable-output -verify-dom-info -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa < %s
 
 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"
 target triple = "x86_64-apple-darwin10.0.0"
 
 ; PR8955 - Rotating an outer loop that has a condbr for a latch block.
 define void @test1() nounwind ssp {
 entry:
   br label %lbl_283

test/Transforms/LoopRotate/dbg-value-duplicates.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
+; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 source_filename = "/tmp/loop.c"
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.13.0"
 
 ; Function Attrs: nounwind ssp uwtable
 define void @f(float* %input, i64 %n, i64 %s) local_unnamed_addr #0 !dbg !8 {
 entry:
   call void @llvm.dbg.value(metadata float* %input, metadata !15, metadata !DIExpression()), !dbg !20

test/Transforms/LoopRotate/dbgvalue.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
+; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 declare void @llvm.dbg.declare(metadata, metadata, metadata) nounwind readnone
 declare void @llvm.dbg.value(metadata, metadata, metadata) nounwind readnone
 
 define i32 @tak(i32 %x, i32 %y, i32 %z) nounwind ssp !dbg !0 {
 ; CHECK-LABEL: define i32 @tak(
 ; CHECK: entry
 ; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 %x

test/Transforms/LoopRotate/indirectbr.ll

 ; RUN: opt < %s -S -loop-rotate -o - -verify-loop-info -verify-dom-info | FileCheck %s
+; RUN: opt < %s -S -loop-rotate -o - -verify-loop-info -verify-dom-info -enable-mssa-loop-dependency=true -verify-memoryssa | FileCheck %s
 
 ; PR5502
 define void @z80_do_opcodes() nounwind {
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %end_opcode, %entry
   br label %while.body

test/Transforms/LoopRotate/loopexitinglatch.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-rotate < %s -verify-loop-info -verify-dom-info | FileCheck %s
+; RUN: opt -S -loop-rotate < %s -verify-loop-info -verify-dom-info -enable-mssa-loop-dependency=true -verify-memoryssa | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "thumbv8m.base-arm-none-eabi"
 
 %struct.List = type { %struct.List*, i32 }
 
 define void @list_add(%struct.List** nocapture %list, %struct.List* %data) {
 ; CHECK-LABEL: @list_add(

test/Transforms/LoopRotate/multiple-exits.ll

 ; RUN: opt -S -loop-rotate < %s -verify-loop-info -verify-dom-info | FileCheck %s
+; RUN: opt -S -loop-rotate < %s -verify-loop-info -verify-dom-info -enable-mssa-loop-dependency=true -verify-memoryssa | FileCheck %s
 
 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"
 target triple = "x86_64-apple-macosx10.8.0"
 
 ; PR7447
 define i32 @test1([100 x i32]* nocapture %a) nounwind readonly {
 entry:
   br label %for.cond

test/Transforms/LoopRotate/phi-dbgvalue.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
+; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 ;CHECK-LABEL: func
 ;CHECK-LABEL: entry
 ;CHECK-NEXT: tail call void @llvm.dbg.value(metadata i32 %a
 ;CHECK-NEXT: tail call void @llvm.dbg.value(metadata i32 1, metadata ![[I_VAR:[0-9]+]], metadata !DIExpression())
 ;CHECK-LABEL: for.body:
 ;CHECK-NEXT: [[I:%.*]] = phi i32 [ 1, %entry ], [ %inc, %for.body ]
 ;CHECK-NEXT: tail call void @llvm.dbg.value(metadata i32 [[I]], metadata ![[I_VAR]], metadata !DIExpression())

test/Transforms/LoopRotate/phi-duplicate.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
+; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 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"
 target triple = "x86_64-apple-darwin10.0"
 
 ; PR5837
 define void @test(i32 %N, double* %G) nounwind ssp {
 entry:
   br label %for.cond
 

test/Transforms/LoopRotate/pr22337.ll

 ; RUN: opt < %s -loop-rotate -S | FileCheck %s
+; RUN: opt < %s -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 @a = external global i8, align 4
 @tmp = global i8* @a
 
 define void @f() {
 ; CHECK-LABEL: define void @f(
 ; CHECK: getelementptr i8, i8* @a, i32 0
 entry:

test/Transforms/LoopRotate/pr33701.ll

 ; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -disable-output
+; RUN: opt < %s -loop-rotate -verify-dom-info -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 
 define void @func() {
 bb0:
   br label %bb1
 
 bb1:                                              ; preds = %bb4, %bb0
   %0 = phi i16 [ %2, %bb4 ], [ 0, %bb0 ]
   %1 = icmp sle i16 %0, 2

test/Transforms/LoopRotate/pr35210.ll

 ;RUN: opt %s -passes='adce,loop(rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate 2>&1 | FileCheck %s
+;RUN: opt %s -passes='adce,loop(rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa 2>&1 | FileCheck %s --check-prefix=MSSA
 ;REQUIRES: asserts
 
 ; This test is to make sure we invalidate the post dominator pass after loop rotate simplifies the loop latch.
 ; The adce passes are here to make sure post dominator analysis is required.
 
 ; CHECK: Starting llvm::Function pass manager run.
 ; CHECK-NEXT: Running pass: ADCEPass on f
 ; CHECK-NEXT: Running analysis: PostDominatorTreeAnalysis on f

 ; CHECK-NEXT: Invalidating all non-preserved analyses for: bb
 ; CHECK-NEXT: Finished Loop pass manager run.
 ; CHECK-NEXT: Invalidating all non-preserved analyses for: f
 ; CHECK-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f
 ; CHECK-NEXT: Running pass: ADCEPass on f
 ; CHECK-NEXT: Running analysis: PostDominatorTreeAnalysis on f
 ; CHECK-NEXT: Finished llvm::Function pass manager run.
 
+; MSSA: Starting llvm::Function pass manager run.
+; MSSA-NEXT: Running pass: ADCEPass on f
+; MSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f
+; MSSA-NEXT: Running pass: FunctionToLoopPassAdaptor{{.*}} on f
+; MSSA-NEXT: Starting llvm::Function pass manager run.
+; MSSA-NEXT: Running pass: LoopSimplifyPass on f
+; MSSA-NEXT: Running analysis: LoopAnalysis on f
+; MSSA-NEXT: Running analysis: DominatorTreeAnalysis on f
+; MSSA-NEXT: Running analysis: AssumptionAnalysis on f
+; MSSA-NEXT: Running pass: LCSSAPass on f
+; MSSA-NEXT: Finished llvm::Function pass manager run.
+; MSSA-NEXT: Running analysis: MemorySSAAnalysis on f
+; MSSA-NEXT: Running analysis: AAManager on f
+; MSSA-NEXT: Running analysis: TargetLibraryAnalysis on f
+; MSSA-NEXT: Running analysis: ScalarEvolutionAnalysis on f
+; MSSA-NEXT: Running analysis: TargetIRAnalysis on f
+; MSSA-NEXT: Running analysis: InnerAnalysisManagerProxy{{.*}} on f
+; MSSA-NEXT: Starting Loop pass manager run.
+; MSSA-NEXT: Running analysis: PassInstrumentationAnalysis on bb
+; MSSA-NEXT: Running pass: LoopRotatePass on Loop at depth 1 containing: %bb<header><exiting>,%bb4<latch>
+; MSSA-NEXT: Folding loop latch bb4 into bb
+; MSSA-NEXT: Invalidating all non-preserved analyses for: bb
+; MSSA-NEXT: Finished Loop pass manager run.
+; MSSA-NEXT: Invalidating all non-preserved analyses for: f
+; MSSA-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f
+; MSSA-NEXT: Running pass: ADCEPass on f
+; MSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f
+; MSSA-NEXT: Finished llvm::Function pass manager run.
+
+
 ; CHECK-LABEL: define i8 @f() {
 ; CHECK-NEXT : entry:
 ; CHECK-NEXT :   br label %bb
 ; CHECK-NEXT :
 ; CHECK-NEXT : bb:                                               ; preds = %bb, %entry
 ; CHECK-NEXT :   %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ]
 ; CHECK-NEXT :   %tmp5 = icmp eq i8 %mode.0, 1
 ; CHECK-NEXT :   %indvar.next = add i8 %mode.0, 1
 ; CHECK-NEXT :   br i1 %tmp5, label %bb5, label %bb
 ; CHECK-NEXT :
 ; CHECK-NEXT : bb5:                                              ; preds = %bb
 ; CHECK-NEXT :   tail call void @raise_exception() #0
 ; CHECK-NEXT :   unreachable
 ; CHECK-NEXT : }
 ; CHECK-NEXT :
 ; CHECK-NEXT : ; Function Attrs: noreturn
 ; CHECK-NEXT : declare void @raise_exception() #0
 ; CHECK-NEXT :
 ; CHECK-NEXT : attributes #0 = { noreturn }
 
+; MSSA-LABEL: define i8 @f() {
+; MSSA-NEXT : entry:
+; MSSA-NEXT :   br label %bb
+; MSSA-NEXT :
+; MSSA-NEXT : bb:                                               ; preds = %bb, %entry
+; MSSA-NEXT :   %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ]
+; MSSA-NEXT :   %tmp5 = icmp eq i8 %mode.0, 1
+; MSSA-NEXT :   %indvar.next = add i8 %mode.0, 1
+; MSSA-NEXT :   br i1 %tmp5, label %bb5, label %bb
+; MSSA-NEXT :
+; MSSA-NEXT : bb5:                                              ; preds = %bb
+; MSSA-NEXT :   tail call void @raise_exception() #0
+; MSSA-NEXT :   unreachable
+; MSSA-NEXT : }
+; MSSA-NEXT :
+; MSSA-NEXT : ; Function Attrs: noreturn
+; MSSA-NEXT : declare void @raise_exception() #0
+; MSSA-NEXT :
+; MSSA-NEXT : attributes #0 = { noreturn }
+
 define i8 @f() {
 entry:
   br label %bb
 
 bb:                                               ; preds = %bb4, %entry
   %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb4 ]
   %tmp5 = icmp eq i8 %mode.0, 1
   br i1 %tmp5, label %bb5, label %bb4

test/Transforms/LoopRotate/pr37205.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -indvars -verify -loop-rotate -loop-idiom < %s | FileCheck %s
+; RUN: opt -S -indvars -verify -loop-rotate -loop-idiom -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Verify that we invalidate SCEV properly.
 
 define void @test_01() {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LBL1:%.*]]

test/Transforms/LoopRotate/preserve-mssa.ll

+; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
+
+; CHECK-LABEL: @multiedge(
+; Function Attrs: nounwind uwtable
+define dso_local void @multiedge() local_unnamed_addr #0 {
+entry:
+  br label %retry
+
+retry:                                            ; preds = %sw.epilog, %entry
+  br i1 undef, label %cleanup, label %if.end
+
+if.end:                                           ; preds = %retry
+  switch i32 undef, label %sw.epilog [
+    i32 -3, label %cleanup
+    i32 -5, label %cleanup
+    i32 -16, label %cleanup
+    i32 -25, label %cleanup
+  ]
+
+sw.epilog:                                        ; preds = %if.end
+  br label %retry
+
+cleanup:                                          ; preds = %if.end, %if.end, %if.end, %if.end, %retry
+  ret void
+}
+
+; CHECK-LABEL: @read_line(
+; Function Attrs: nounwind uwtable
+define internal fastcc i32 @read_line(i8* nocapture %f) unnamed_addr #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.end, %entry
+  %call = call i8* @prepbuffer(i8* nonnull undef) #4
+  %call1 = call i8* @fgets(i8* %call, i32 8192, i8* %f)
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.cond
+  ret i32 undef
+
+if.end:                                           ; preds = %for.cond
+  %call4 = call i64 @strlen(i8* %call) #5
+  br label %for.cond
+}
+
+; Function Attrs: nounwind readonly
+declare dso_local i8* @prepbuffer(i8*) local_unnamed_addr #1
+
+; Function Attrs: nounwind
+declare dso_local i8* @fgets(i8*, i32, i8* nocapture) local_unnamed_addr #3
+
+; Function Attrs: argmemonly nounwind readonly
+declare dso_local i64 @strlen(i8* nocapture) local_unnamed_addr #2
+
+
+
+; Function Attrs: inlinehint norecurse nounwind uwtable
+declare dso_local fastcc void @list_Pop() unnamed_addr #6
+
+; CHECK-LABEL: @loop3
+; Function Attrs: nounwind uwtable
+define dso_local fastcc void @loop3() unnamed_addr #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  br i1 undef, label %for.body, label %for.end81
+
+for.body:                                         ; preds = %for.cond
+  %.idx122.val = load i32, i32* undef, align 8
+  call fastcc void @list_Pop()
+  br label %for.cond
+
+for.end81:                                        ; preds = %for.cond
+  ret void
+}
+
+; CHECK-LABEL: @loop4
+; Function Attrs: inlinehint nounwind uwtable
+define dso_local fastcc void @loop4() unnamed_addr #6 {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  br i1 undef, label %while.end, label %while.body
+
+while.body:                                       ; preds = %while.cond
+  call fastcc void @cont_BackTrackLastBinding()
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  call fastcc void @cont_StackInit()
+  call fastcc void @cont_ResetIndexVarScanner()
+  ret void
+}
+
+; Function Attrs: inlinehint nounwind uwtable
+declare dso_local fastcc void @cont_BackTrackLastBinding() unnamed_addr #6
+
+; Function Attrs: inlinehint nounwind uwtable
+declare dso_local fastcc void @cont_StackInit() unnamed_addr #6
+
+; Function Attrs: inlinehint nounwind uwtable
+declare dso_local fastcc void @cont_ResetIndexVarScanner() unnamed_addr #6
+
+
+@glob_array = internal unnamed_addr constant [3 x i32] [i32 1, i32 0, i32 2], align 4
+; Test against failure in MemorySSAUpdater, when rotate clones instructions as Value.
+; CHECK-LABEL: @loop5
+define dso_local fastcc void @loop5() unnamed_addr {
+entry:
+  br label %for.body
+
+do.cond:                          ; preds = %for.body
+  unreachable
+
+for.body:                               ; preds = %if.end, %entry
+  %indvar = phi i64 [ %indvar.next, %if.end ], [ 0, %entry ]
+  %array = getelementptr inbounds [3 x i32], [3 x i32]* @glob_array, i64 0, i64 %indvar
+  %0 = load i32, i32* %array, align 4
+  br i1 undef, label %do.cond, label %if.end
+
+if.end:                                 ; preds = %for.body
+  store i32 undef, i32* undef, align 4
+  %indvar.next = add nuw nsw i64 %indvar, 1
+  br label %for.body
+}
+
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { argmemonly nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #4 = { nounwind }
+attributes #5 = { nounwind readonly }
+attributes #6 = { inlinehint norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+

test/Transforms/LoopRotate/preserve-scev.ll

 ; RUN: opt < %s -loop-rotate -loop-reduce -verify-dom-info -verify-loop-info -disable-output
 
-define fastcc void @foo() nounwind {
+define fastcc void @foo(i32* %A, i64 %i) nounwind {
 BB:
   br label %BB1
 
 BB1:                                              ; preds = %BB19, %BB
+  %tttmp1 = getelementptr i32, i32* %A, i64 %i
+  %tttmp2 = load i32, i32* %tttmp1
+  %tttmp3 = add i32 %tttmp2, 1
+  store i32 %tttmp3, i32* %tttmp1
   br label %BB4
 
 BB2:                                              ; preds = %BB4
   %tmp = bitcast i32 undef to i32                 ; <i32> [#uses=1]
+  %tttmp7 = getelementptr i32, i32* %A, i64 %i
+  %tttmp8 = load i32, i32* %tttmp7
+  %tttmp9 = add i32 %tttmp8, 3
+  store i32 %tttmp9, i32* %tttmp7
   br label %BB4
 
-BB4:                                              ; preds = %BB3, %BB1
+BB4:                                              ; preds = %BB2, %BB1
   %tmp5 = phi i32 [ undef, %BB1 ], [ %tmp, %BB2 ] ; <i32> [#uses=1]
+  %tttmp4 = getelementptr i32, i32* %A, i64 %i
+  %tttmp5 = load i32, i32* %tttmp4
+  %tttmp6 = add i32 %tttmp5, 3
+  store i32 %tttmp6, i32* %tttmp4
   br i1 false, label %BB8, label %BB2
 
 BB8:                                              ; preds = %BB6
   %tmp7 = bitcast i32 %tmp5 to i32                ; <i32> [#uses=2]
+  %tttmp10 = getelementptr i32, i32* %A, i64 %i
+  %tttmp11 = load i32, i32* %tttmp10
+  %tttmp12 = add i32 %tttmp11, 3
+  store i32 %tttmp12, i32* %tttmp10
   br i1 false, label %BB9, label %BB13
 
 BB9:                                              ; preds = %BB12, %BB8
   %tmp10 = phi i32 [ %tmp11, %BB12 ], [ %tmp7, %BB8 ] ; <i32> [#uses=2]
   %tmp11 = add i32 %tmp10, 1                      ; <i32> [#uses=1]
+  %tttmp13 = getelementptr i32, i32* %A, i64 %i
+  %tttmp14 = load i32, i32* %tttmp13
+  %tttmp15 = add i32 %tttmp14, 3
+  store i32 %tttmp15, i32* %tttmp13
   br label %BB12
 
 BB12:                                             ; preds = %BB9
   br i1 false, label %BB9, label %BB17
 
 BB13:                                             ; preds = %BB15, %BB8
   %tmp14 = phi i32 [ %tmp16, %BB15 ], [ %tmp7, %BB8 ] ; <i32> [#uses=1]
+  %tttmp16 = getelementptr i32, i32* %A, i64 %i
+  %tttmp17 = load i32, i32* %tttmp16
+  %tttmp18 = add i32 %tttmp17, 3
+  store i32 %tttmp18, i32* %tttmp16
   br label %BB15
 
 BB15:                                             ; preds = %BB13
   %tmp16 = add i32 %tmp14, -1                     ; <i32> [#uses=1]
+  %tttmp19 = getelementptr i32, i32* %A, i64 %i
+  %tttmp20 = load i32, i32* %tttmp19
+  %tttmp21 = add i32 %tttmp20, 3
+  store i32 %tttmp21, i32* %tttmp19
   br i1 false, label %BB13, label %BB18
 
 BB17:                                             ; preds = %BB12
   br label %BB19
 
 BB18:                                             ; preds = %BB15
+  %tttmp22 = getelementptr i32, i32* %A, i64 %i
+  %tttmp23 = load i32, i32* %tttmp22
+  %tttmp24 = add i32 %tttmp23, 3
+  store i32 %tttmp24, i32* %tttmp22
   br label %BB19
 
 BB19:                                             ; preds = %BB18, %BB17
   %tmp20 = phi i32 [ %tmp10, %BB17 ], [ undef, %BB18 ] ; <i32> [#uses=0]
   br label %BB1
 }

test/Transforms/LoopRotate/vect.omp.persistence.ll

 ; RUN: opt < %s -loop-rotate -S | FileCheck %s
+; RUN: opt < %s -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 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"
 
 ; Ensure that "llvm.loop.vectorize.enable" metadata was not lost after loop-rotate.
 ; In past LoopRotate was clearing that metadata.
 ;
 ; See http://reviews.llvm.org/D3348 for details.