Update MemorySSA in LoopUnswitch.

[asbirlea]

Summary

Update MemorySSA in old LoopUnswitch pass.
Actual dependency and update is disabled by default.

[asbirlea]

Rebase on dependent patch.

[asbirlea]

Update to use new API in dependent patch.

[asbirlea]

Rebase and update after API change.

[asbirlea]

Rebase. Ready to review.

[chandlerc]

LGTM

lib/Transforms/Scalar/LoopUnswitch.cpp

 //
 // This pass expects LICM to be run before it to hoist invariant conditions out
 // of the loop, to make the unswitching opportunity obvious.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/DivergenceAnalysis.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.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/Transforms/Utils/Local.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"

 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <algorithm>
 #include <cassert>
 #include <map>
 #include <set>
 #include <tuple>
 #include <utility>
class LoopUnswitch : public LoopPass {
 
     LUAnalysisCache BranchesInfo;
 
     bool OptimizeForSize;
     bool redoLoop = false;
 
     Loop *currentLoop = nullptr;
     DominatorTree *DT = nullptr;
+    MemorySSA *MSSA = nullptr;
+    std::unique_ptr<MemorySSAUpdater> MSSAU;
     BasicBlock *loopHeader = nullptr;
     BasicBlock *loopPreheader = nullptr;
 
     bool SanitizeMemory;
     LoopSafetyInfo SafetyInfo;
 
     // LoopBlocks contains all of the basic blocks of the loop, including the
     // preheader of the loop, the body of the loop, and the exit blocks of the
public:
     bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
 
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG.
     ///
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<AssumptionCacheTracker>();
       AU.addRequired<TargetTransformInfoWrapperPass>();
+      if (EnableMSSALoopDependency) {
+        AU.addRequired<MemorySSAWrapperPass>();
+        AU.addPreserved<MemorySSAWrapperPass>();
+      }
       if (hasBranchDivergence)
         AU.addRequired<DivergenceAnalysis>();
       getLoopAnalysisUsage(AU);
     }
 
   private:
     void releaseMemory() override {
       BranchesInfo.forgetLoop(currentLoop);

 
 char LoopUnswitch::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DivergenceAnalysis)
 INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",
                       false, false)
 
 Pass *llvm::createLoopUnswitchPass(bool Os, bool hasBranchDivergence) {
   return new LoopUnswitch(Os, hasBranchDivergence);
 }
 
bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   if (skipLoop(L))
     return false;
 
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
       *L->getHeader()->getParent());
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   LPM = &LPM_Ref;
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  if (EnableMSSALoopDependency) {
+    MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
+    MSSAU = make_unique<MemorySSAUpdater>(MSSA);
+    assert(DT && "Cannot update MemorySSA without a valid DomTree.");
+  }
   currentLoop = L;
   Function *F = currentLoop->getHeader()->getParent();
 
   SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
   if (SanitizeMemory)
     SafetyInfo.computeLoopSafetyInfo(L);
 
+  if (MSSA && VerifyMemorySSA)
+    MSSA->verifyMemorySSA();
+
   bool Changed = false;
   do {
     assert(currentLoop->isLCSSAForm(*DT));
+    if (MSSA && VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
     redoLoop = false;
     Changed |= processCurrentLoop();
   } while(redoLoop);
 
+  if (MSSA && VerifyMemorySSA)
+    MSSA->verifyMemorySSA();
+
   return Changed;
 }
 
 // Return true if the BasicBlock BB is unreachable from the loop header.
 // Return false, otherwise.
 bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) {
   auto *Node = DT->getNode(BB)->getIDom();
   BasicBlock *DomBB = Node->getBlock();
if (TrueDest != OldBranchSucc)
       Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest});
     if (FalseDest != OldBranchSucc)
       Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest});
     // If both of the new successors are different from the old one, inform the
     // DT that the edge was deleted.
     if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) {
       Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc});
     }
-
     DT->applyUpdates(Updates);
+
+    if (MSSAU)
+      MSSAU->applyUpdates(Updates, *DT);
   }
 
   // If either edge is critical, split it. This helps preserve LoopSimplify
   // form for enclosing loops.
-  auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA();
+  auto Options =
+      CriticalEdgeSplittingOptions(DT, LI, MSSAU.get()).setPreserveLCSSA();
   SplitCriticalEdge(BI, 0, Options);
   SplitCriticalEdge(BI, 1, Options);
 }
 
 /// Given a loop that has a trivial unswitchable condition in it (a cond branch
 /// from its header block to its latch block, where the path through the loop
 /// that doesn't execute its body has no side-effects), unswitch it. This
 /// doesn't involve any code duplication, just moving the conditional branch
void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
   // We are going to make essential changes to CFG. This may invalidate cached
   // information for L or one of its parent loops in SCEV.
   if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
     SEWP->getSE().forgetTopmostLoop(L);
 
   // First step, split the preheader, so that we know that there is a safe place
   // to insert the conditional branch.  We will change loopPreheader to have a
   // conditional branch on Cond.
-  BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI);
+  BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get());
 
   // Now that we have a place to insert the conditional branch, create a place
   // to branch to: this is the exit block out of the loop that we should
   // short-circuit to.
 
   // Split this block now, so that the loop maintains its exit block, and so
   // that the jump from the preheader can execute the contents of the exit block
   // without actually branching to it (the exit block should be dominated by the
   // loop header, not the preheader).
   assert(!L->contains(ExitBlock) && "Exit block is in the loop?");
-  BasicBlock *NewExit = SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI);
+  BasicBlock *NewExit =
+      SplitBlock(ExitBlock, &ExitBlock->front(), DT, LI, MSSAU.get());
 
   // Okay, now we have a position to branch from and a position to branch to,
   // insert the new conditional branch.
   auto *OldBranch = dyn_cast<BranchInst>(loopPreheader->getTerminator());
   assert(OldBranch && "Failed to split the preheader");
   EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI);
   LPM->deleteSimpleAnalysisValue(OldBranch, L);
 
   // EmitPreheaderBranchOnCondition removed the OldBranch from the function.
   // Delete it, as it is no longer needed.
   delete OldBranch;
 
   // We need to reprocess this loop, it could be unswitched again.
   redoLoop = true;
 
   // Now that we know that the loop is never entered when this condition is a
   // particular value, rewrite the loop with this info.  We know that this will
   // at least eliminate the old branch.
   RewriteLoopBodyWithConditionConstant(L, Cond, Val, false);
+
   ++NumTrivial;
 }
 
 /// Check if the first non-constant condition starting from the loop header is
 /// a trivial unswitch condition: that is, a condition controls whether or not
 /// the loop does anything at all. If it is a trivial condition, unswitching
 /// produces no code duplications (equivalently, it produces a simpler loop and
 /// a new empty loop, which gets deleted). Therefore always unswitch trivial
void LoopUnswitch::SplitExitEdges(Loop *L,
 
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
     BasicBlock *ExitBlock = ExitBlocks[i];
     SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock),
                                        pred_end(ExitBlock));
 
     // Although SplitBlockPredecessors doesn't preserve loop-simplify in
     // general, if we call it on all predecessors of all exits then it does.
-    SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, nullptr,
+    SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, MSSAU.get(),
                            /*PreserveLCSSA*/ true);
   }
 }
 
 /// We determined that the loop is profitable to unswitch when LIC equal Val.
 /// Split it into loop versions and test the condition outside of either loop.
 /// Return the loops created as Out1/Out2.
 void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
   if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
     SEWP->getSE().forgetTopmostLoop(L);
 
   LoopBlocks.clear();
   NewBlocks.clear();
 
   // First step, split the preheader and exit blocks, and add these blocks to
   // the LoopBlocks list.
-  BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI);
+  BasicBlock *NewPreheader =
+      SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get());
   LoopBlocks.push_back(NewPreheader);
 
   // We want the loop to come after the preheader, but before the exit blocks.
   LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
 
for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
     }
   }
 
   // Rewrite the original preheader to select between versions of the loop.
   BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator());
   assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&
          "Preheader splitting did not work correctly!");
 
+  if (MSSAU) {
+    // Update MemorySSA after cloning, and before splitting to unreachables,
+    // since that invalidates the 1:1 mapping of clones in VMap.
+    LoopBlocksRPO LBRPO(L);
+    LBRPO.perform(LI);
+    MSSAU->updateForClonedLoop(LBRPO, ExitBlocks, VMap);
+  }
+
   // Emit the new branch that selects between the two versions of this loop.
   EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR,
                                  TI);
   LPM->deleteSimpleAnalysisValue(OldBR, L);
+  if (MSSAU) {
+    // Update MemoryPhis in Exit blocks.
+    MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT);
+    if (VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
+  }
 
   // The OldBr was replaced by a new one and removed (but not erased) by
   // EmitPreheaderBranchOnCondition. It is no longer needed, so delete it.
   delete OldBR;
 
   LoopProcessWorklist.push_back(NewLoop);
   redoLoop = true;
 
void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
   RewriteLoopBodyWithConditionConstant(L, LIC, Val, false);
 
   // It's possible that simplifying one loop could cause the other to be
   // changed to another value or a constant.  If its a constant, don't simplify
   // it.
   if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop &&
       LICHandle && !isa<Constant>(LICHandle))
     RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true);
+
+  if (MSSA && VerifyMemorySSA)
+    MSSA->verifyMemorySSA();
 }
 
 /// Remove all instances of I from the worklist vector specified.
 static void RemoveFromWorklist(Instruction *I,
                                std::vector<Instruction*> &Worklist) {
 
   Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
                  Worklist.end());
for (User *U : LIC->users()) {
     // to the latch.
     if (Latch && DT->dominates(SISucc, Latch))
       continue;
 
     // FIXME: This is a hack.  We need to keep the successor around
     // and hooked up so as to preserve the loop structure, because
     // trying to update it is complicated.  So instead we preserve the
     // loop structure and put the block on a dead code path.
-    SplitEdge(Switch, SISucc, DT, LI);
+    SplitEdge(Switch, SISucc, DT, LI, MSSAU.get());
     // Compute the successors instead of relying on the return value
     // of SplitEdge, since it may have split the switch successor
     // after PHI nodes.
     BasicBlock *NewSISucc = DeadCase.getCaseSuccessor();
     BasicBlock *OldSISucc = *succ_begin(NewSISucc);
     // Create an "unreachable" destination.
     BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
                                            Switch->getParent(),
if (isInstructionTriviallyDead(I)) {
       LLVM_DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");
 
       // Add uses to the worklist, which may be dead now.
       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
         if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
           Worklist.push_back(Use);
       LPM->deleteSimpleAnalysisValue(I, L);
       RemoveFromWorklist(I, Worklist);
+      if (MSSAU)
+        MSSAU->removeMemoryAccess(I);
       I->eraseFromParent();
       ++NumSimplify;
       continue;
     }
 
     // See if instruction simplification can hack this up.  This is common for
     // things like "select false, X, Y" after unswitching made the condition be
     // 'false'.  TODO: update the domtree properly so we can pass it here.
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
 
         // If Succ has any successors with PHI nodes, update them to have
         // entries coming from Pred instead of Succ.
         Succ->replaceAllUsesWith(Pred);
 
         // Move all of the successor contents from Succ to Pred.
         Pred->getInstList().splice(BI->getIterator(), Succ->getInstList(),
                                    Succ->begin(), Succ->end());
+        if (MSSAU)
+          MSSAU->moveAllAfterMergeBlocks(Succ, Pred, BI);
         LPM->deleteSimpleAnalysisValue(BI, L);
         RemoveFromWorklist(BI, Worklist);
         BI->eraseFromParent();
 
         // Remove Succ from the loop tree.
         LI->removeBlock(Succ);
         LPM->deleteSimpleAnalysisValue(Succ, L);
         Succ->eraseFromParent();

test/Transforms/LoopUnswitch/2006-06-13-SingleEntryPHI.ll

 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 
   %struct.BLEND_MAP = type { i16, i16, i16, i32, %struct.BLEND_MAP_ENTRY* }
   %struct.BLEND_MAP_ENTRY = type { float, i8, { [5 x float], [4 x i8] } }
   %struct.TPATTERN = type { i16, i16, i16, i32, float, float, float, %struct.WARP*, %struct.TPATTERN*, %struct.BLEND_MAP*, { %struct.anon, [4 x i8] } }
   %struct.TURB = type { i16, %struct.WARP*, [3 x double], i32, float, float }
   %struct.WARP = type { i16, %struct.WARP* }
   %struct.anon = type { float, [3 x double] }
 

test/Transforms/LoopUnswitch/2006-06-27-DeadSwitchCase.ll

 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 
 define void @init_caller_save() {
 entry:
   br label %cond_true78
 cond_next20:    ; preds = %cond_true64
   br label %bb31
 bb31:   ; preds = %cond_true64, %cond_true64, %cond_next20
   %iftmp.29.1 = phi i32 [ 0, %cond_next20 ], [ 0, %cond_true64 ], [ 0, %cond_true64 ]    ; <i32> [#uses=0]

test/Transforms/LoopUnswitch/2007-05-09-Unreachable.ll

 ; PR1333
 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 
 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"
 target triple = "i686-pc-linux-gnu"
   %struct.ada__streams__root_stream_type = type { %struct.ada__tags__dispatch_table* }
   %struct.ada__tags__dispatch_table = type { [1 x i8*] }
   %struct.quotes__T173s = type { i8, %struct.quotes__T173s__T174s, [2 x [1 x double]], [2 x i16], i64, i8 }
   %struct.quotes__T173s__T174s = type { i8, i8, i8, i16, i16, [2 x [1 x double]] }
 

test/Transforms/LoopUnswitch/2007-05-09-tl.ll

 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 ; PR1333
 
 define void @pp_cxx_expression() {
 entry:
   %tmp6 = lshr i32 0, 24    ; <i32> [#uses=1]
   br label %tailrecurse
 
 tailrecurse:    ; preds = %tailrecurse, %tailrecurse, %entry

test/Transforms/LoopUnswitch/2007-07-12-ExitDomInfo.ll

 ; RUN: opt < %s -loop-unswitch -instcombine -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -instcombine -disable-output
 
 @str3 = external constant [3 x i8]    ; <[3 x i8]*> [#uses=1]
 
 define i32 @stringSearch_Clib(i32 %count) {
 entry:
   %ttmp25 = icmp sgt i32 %count, 0    ; <i1> [#uses=1]
   br i1 %ttmp25, label %bb36.preheader, label %bb44
 

test/Transforms/LoopUnswitch/2007-07-13-DomInfo.ll

 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 
 define i32 @main(i32 %argc, i8** %argv) {
 entry:
   %tmp1785365 = icmp ult i32 0, 100    ; <i1> [#uses=1]
   br label %bb
 
 bb:   ; preds = %cond_true, %entry
   br i1 false, label %cond_true, label %cond_next

test/Transforms/LoopUnswitch/2007-07-18-DomInfo.ll

 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 ; PR1559
 
 target triple = "i686-pc-linux-gnu"
   %struct.re_pattern_buffer = type { i8*, i32, i32, i32, i8*, i8*, i32, i8 }
 
 define fastcc i32 @byte_regex_compile(i8* %pattern, i32 %size, i32 %syntax, %struct.re_pattern_buffer* %bufp) {
 entry:
         br i1 false, label %bb147, label %cond_next123

test/Transforms/LoopUnswitch/2007-08-01-LCSSA.ll

 ; RUN: opt < %s -loop-unswitch -instcombine -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -instcombine -disable-output
   %struct.ClassDef = type { %struct.QByteArray, %struct.QByteArray, %"struct.QList<ArgumentDef>", %"struct.QList<ArgumentDef>", i8, i8, %"struct.QList<ArgumentDef>", %"struct.QList<ArgumentDef>", %"struct.QList<ArgumentDef>", %"struct.QList<ArgumentDef>", %"struct.QList<ArgumentDef>", %"struct.QList<ArgumentDef>", %"struct.QMap<QByteArray,QByteArray>", %"struct.QList<ArgumentDef>", %"struct.QMap<QByteArray,QByteArray>", i32, i32 }
   %struct.FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct.FILE*, i32, i32, i32, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i32, i32, [40 x i8] }
   %struct.Generator = type { %struct.FILE*, %struct.ClassDef*, %"struct.QList<ArgumentDef>", %struct.QByteArray, %"struct.QList<ArgumentDef>" }
   %struct.QBasicAtomic = type { i32 }
   %struct.QByteArray = type { %"struct.QByteArray::Data"* }
   %"struct.QByteArray::Data" = type { %struct.QBasicAtomic, i32, i32, i8*, [1 x i8] }
   %"struct.QList<ArgumentDef>" = type { %"struct.QList<ArgumentDef>::._19" }
   %"struct.QList<ArgumentDef>::._19" = type { %struct.QListData }

test/Transforms/LoopUnswitch/2008-06-02-DomInfo.ll

 ; RUN: opt < %s -loop-unswitch -instcombine -gvn -disable-output
+; RUN: opt < %s -loop-unswitch -instcombine -gvn -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 ; PR2372
 target triple = "i386-pc-linux-gnu"
 
 define i32 @func_3(i16 signext  %p_5, i16 signext  %p_6) nounwind  {
 entry:
   %tmp3 = icmp eq i16 %p_5, 0    ; <i1> [#uses=1]
   %tmp1314 = sext i16 %p_6 to i32   ; <i32> [#uses=1]
   %tmp28 = icmp ugt i32 %tmp1314, 3    ; <i1> [#uses=1]

test/Transforms/LoopUnswitch/2008-11-03-Invariant.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -loop-unswitch -stats -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -stats -disable-output 2>&1 | FileCheck %s
 ; PR 3170
 
 define i32 @a(i32 %x, i32 %y) nounwind {
 ; CHECK: 1 loop-unswitch - Number of branches unswitched
 ; CHECK-NOT: Number of branches unswitched
 
 entry:
   %0 = icmp ult i32 0, %y    ; <i1> [#uses=1]

test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll

 ; RUN: opt < %s -loop-unswitch
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa
 ; PR8622
 @g_38 = external global i32, align 4
 
 define void @func_67(i32 %p_68.coerce) nounwind {
 entry:
   br i1 true, label %for.end12, label %bb.nph
 
 bb.nph:                                           ; preds = %entry

test/Transforms/LoopUnswitch/2011-09-26-EHCrash.ll

 ; RUN: opt < %s -sroa -loop-unswitch -disable-output
+; RUN: opt < %s -sroa -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 ; PR11016
 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-macosx10.7.2"
 
 %class.MyContainer.1.3.19.29 = type { [6 x %class.MyMemVarClass.0.2.18.28*] }
 %class.MyMemVarClass.0.2.18.28 = type { i32 }
 
 define void @_ZN11MyContainer1fEi(%class.MyContainer.1.3.19.29* %this, i32 %doit) uwtable ssp align 2 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {

test/Transforms/LoopUnswitch/2011-11-18-SimpleSwitch.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -S -loop-unswitch -verify-loop-info -verify-dom-info < %s | FileCheck %s
+; RUN: opt -S -loop-unswitch -verify-loop-info -verify-dom-info -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 ; STATS: 2 loop-unswitch - Number of switches unswitched
 
 ; CHECK:      %1 = icmp eq i32 %c, 1
 ; CHECK-NEXT: br i1 %1, label %.split.us, label %..split_crit_edge
 
 ; CHECK:      ..split_crit_edge:                                ; preds = %0
 ; CHECK-NEXT:   br label %.split

test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches-Threshold.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -loop-unswitch-threshold 13 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 13 -verify-loop-info -verify-dom-info < %s | FileCheck %s
+; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 13 -verify-loop-info -verify-dom-info -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 ; STATS: 1 loop-unswitch - Number of switches unswitched
 
 ; ModuleID = '../llvm/test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll'
 
 ; CHECK:        %1 = icmp eq i32 %c, 1
 ; CHECK-NEXT:   br i1 %1, label %.split.us, label %..split_crit_edge
 

test/Transforms/LoopUnswitch/2011-11-18-TwoSwitches.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -loop-unswitch-threshold 1000 -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 1000 -verify-loop-info -verify-dom-info < %s | FileCheck %s
+; RUN: opt -S -loop-unswitch -loop-unswitch-threshold 1000 -verify-loop-info -verify-dom-info -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 ; STATS: 3 loop-unswitch - Number of switches unswitched
 
 ; CHECK:        %1 = icmp eq i32 %c, 1
 ; CHECK-NEXT:   br i1 %1, label %.split.us, label %..split_crit_edge
 
 ; CHECK:      ..split_crit_edge:                                ; preds = %0
 ; CHECK-NEXT:   br label %.split

test/Transforms/LoopUnswitch/2012-04-02-IndirectBr.ll

 ; RUN: opt < %s -S -loop-unswitch -verify-loop-info -verify-dom-info | FileCheck %s
+; RUN: opt < %s -S -loop-unswitch -verify-loop-info -verify-dom-info -enable-mssa-loop-dependency=true -verify-memoryssa | FileCheck %s
 ; PR12343: -loop-unswitch crash on indirect branch
 
 ; CHECK:       %0 = icmp eq i64 undef, 0
 ; CHECK-NEXT:  br i1 %0, label %"5", label %"4"
 
 ; CHECK:       "5":                                              ; preds = %entry
 ; CHECK-NEXT:  br label %"16"
 

test/Transforms/LoopUnswitch/2012-05-20-Phi.ll

 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 ; PR12887
 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-unknown-linux-gnu"
 
 @a = common global i32 0, align 4
 @c = common global i32 0, align 4
 @b = common global i32 0, align 4
 

test/Transforms/LoopUnswitch/2015-09-18-Addrspace.ll

 ; RUN: opt < %s -loop-unswitch -S | FileCheck %s
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -S | FileCheck %s
 
 ; In cases where two address spaces do not have the same size pointer, the
 ; input for the addrspacecast should not be used as a substitute for itself
 ; when manipulating the pointer.
 
 target datalayout = "e-m:e-p:16:16-p1:32:16-i32:16-i64:16-n8:16"
 
 define void @foo() {

test/Transforms/LoopUnswitch/LIV-loop-condtion.ll

 ; RUN: opt < %s -loop-unswitch -loop-unswitch-threshold=0 -S 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-unswitch -loop-unswitch-threshold=0 -enable-mssa-loop-dependency=true -verify-memoryssa -S 2>&1 | FileCheck %s
 
 ; This is to test trivial loop unswitch only happens when trivial condition
 ; itself is an LIV loop condition (not partial LIV which could occur in and/or).
 
 define i32 @test(i1 %cond1, i32 %var1) {
 entry:
   br label %loop_begin
 
do_something:
   %var2 = add i32 %var3, 1
   call void @some_func() noreturn nounwind
   br label %loop_begin
 
 loop_exit:
   ret i32 0
 }
 
-declare void @some_func() noreturn 
+declare void @some_func() noreturn 
 

test/Transforms/LoopUnswitch/basictest.ll

 ; RUN: opt < %s -loop-unswitch -verify-loop-info -S < %s 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-unswitch -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s 2>&1 | FileCheck %s
 
 define i32 @test(i32* %A, i1 %C) {
 entry:
   br label %no_exit
 no_exit:    ; preds = %no_exit.backedge, %entry
   %i.0.0 = phi i32 [ 0, %entry ], [ %i.0.0.be, %no_exit.backedge ]    ; <i32> [#uses=3]
   %gep.upgrd.1 = zext i32 %i.0.0 to i64   ; <i64> [#uses=1]
   %tmp.7 = getelementptr i32, i32* %A, i64 %gep.upgrd.1    ; <i32*> [#uses=4]

test/Transforms/LoopUnswitch/cleanuppad.ll

 ; RUN: opt -S -loop-unswitch < %s | FileCheck %s
+; RUN: opt -S -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 target triple = "x86_64-pc-win32"
 
 define void @f(i32 %doit, i1 %x, i1 %y) personality i32 (...)* @__CxxFrameHandler3 {
 entry:
   %tobool = icmp eq i32 %doit, 0
   br label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %entry

test/Transforms/LoopUnswitch/copy-metadata.ll

 ; RUN: opt < %s -loop-unswitch -S < %s 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s 2>&1 | FileCheck %s
 
 ; This test checks if unswitched condition preserve make.implicit metadata.
 
 define i32 @test(i1 %cond) {
 ; CHECK-LABEL: @test(
 ; CHECK:  br i1 %cond, label %..split_crit_edge, label %.loop_exit.split_crit_edge, !make.implicit !0
   br label %loop_begin
 

test/Transforms/LoopUnswitch/crash.ll

 ; RUN: opt < %s -loop-unswitch -disable-output
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output
 
 define void @test1(i32* %S2) {
 entry:
   br i1 false, label %list_Length.exit, label %cond_true.i
 cond_true.i:    ; preds = %entry
   ret void
 list_Length.exit:   ; preds = %entry
   br i1 false, label %list_Length.exit9, label %cond_true.i5

test/Transforms/LoopUnswitch/elseif-non-exponential-behavior.ll

 ; RUN: opt -loop-unswitch -S - < %s | FileCheck %s
+; RUN: opt -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -S - < %s | FileCheck %s
 
 ;CHECK-LABEL: @b
 ;CHECK: [[Loop1:for\.end.*]]:                              ; preds = %for.cond.us
 ;CHECK-NEXT:  %[[PhiVar1:pdt.*]] = phi i32 [ %pdt.0.us, %for.cond.us ]
 ;CHECK: [[Loop2:for\.end.*]]:                     ; preds = %for.cond.us1
 ;CHECK-NEXT:  %[[PhiVar2:pdt.*]] = phi i32 [ %pdt.0.us2, %for.cond.us1 ]
 ;CHECK: [[Loop3:for\.end.*]]:                        ; preds = %for.cond
 ;CHECK-NEXT:  %[[PhiVar3:pdt.*]] = phi i32 [ %pdt.0, %for.cond ]

test/Transforms/LoopUnswitch/exponential-behavior.ll

 ; RUN: opt -loop-unswitch -S < %s | FileCheck %s
+; RUN: opt -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s | FileCheck %s
 
 define void @f(i32 %n, i32* %ptr) {
 ; CHECK-LABEL: @f(
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]

test/Transforms/LoopUnswitch/guards.ll

 ; RUN: opt -S -loop-unswitch < %s | FileCheck %s
+; RUN: opt -S -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 define void @f_0(i32 %n, i32* %ptr, i1 %c) {
 ; CHECK-LABEL: @f_0(
 ; CHECK: loop.us:
 ; CHECK-NOT: guard
 ; CHECK: loop:

test/Transforms/LoopUnswitch/infinite-loop.ll

 ; REQUIRES: asserts
 ; RUN: opt -loop-unswitch -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
+; RUN: opt -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output -stats -info-output-file - < %s | FileCheck --check-prefix=STATS %s
 ; RUN: opt -loop-unswitch -simplifycfg -S < %s | FileCheck %s
 ; PR5373
 
 ; Loop unswitching shouldn't trivially unswitch the true case of condition %a
 ; in the code here because it leads to an infinite loop. While this doesn't
 ; contain any instructions with side effects, it's still a kind of side effect.
 ; It can trivially unswitch on the false case of condition %a though.
 

test/Transforms/LoopUnswitch/invalidate-scev.ll

 ; RUN: opt -S -indvars -loop-unswitch < %s | FileCheck %s
+; RUN: opt -S -indvars -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @test_01() {
 
 ; Make sure we don't fail by SCEV's assertion due to incorrect invalidation.
 ; CHECK-LABEL: @test_01
 

test/Transforms/LoopUnswitch/msan.ll

 ; RUN: opt < %s -loop-unswitch -verify-loop-info -S < %s 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-unswitch -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s 2>&1 | FileCheck %s
 
 @sink = global i32 0, align 4
 @y = global i64 0, align 8
 
 ; The following is approximately:
 ; void f(bool x, int p, int q) {
 ;   volatile bool x2 = x;
 ;   for (int i = 0; i < 1; ++i) {

test/Transforms/LoopUnswitch/pr32818.ll

 ; Check that the call doesn't get removed even if
 ; it has no uses. It could have side-effects.
 ; RUN: opt -loop-unswitch -S %s | FileCheck %s
+; RUN: opt -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -S %s | FileCheck %s
 
 ; CHECK-LABEL: @tinky
 define i32 @tinkywinky(i8 %patatino) {
   %cmp1 = icmp slt i8 %patatino, 5
   br label %body
 body:
   %i = select i1 %cmp1, i8 6, i8 undef
   br i1 true, label %body, label %end
 end:
   %split = phi i8 [ %i, %body ]
   %conv4 = sext i8 %split to i32
 ; CHECK: tail call fastcc i32 @fn5(
   %call = tail call fastcc i32 @fn5(i32 %conv4)
   ret i32 0
 }
 declare fastcc i32 @fn5(i32 returned) unnamed_addr

test/Transforms/LoopUnswitch/preserve-analyses.ll

 ; RUN: opt -loop-unswitch -verify-loop-info -verify-dom-info -disable-output < %s
+; RUN: opt -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -verify-loop-info -verify-dom-info -disable-output < %s
 
 ; Loop unswitch should be able to unswitch these loops and
 ; preserve LCSSA and LoopSimplify forms.
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:32-f32:32:32-f64:32:32-v64:64:64-v128:128:128-a0:0:64"
 target triple = "armv6-apple-darwin9"
 
 @delim1 = external global i32                     ; <i32*> [#uses=1]

test/Transforms/LoopUnswitch/simplify-with-nonvalness.ll

 ; RUN: opt < %s -loop-unswitch -verify-loop-info -S < %s 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-unswitch -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s 2>&1 | FileCheck %s
 
 ; There are 1 case and 1 default case in the switch. after we unswitch, we know the
 ; %a is definitely not 0 in one of the unswitched loop, make sure we take advantage
 ; of that and simplify the branches in the loop.
 ;
 ; CHECK: define void @simplify_with_nonvalness(
 
 ; This is the loop in which we know %a is definitely 0.

test/Transforms/LoopUnswitch/trivial-unswitch.ll

 ; RUN: opt < %s -loop-unswitch -loop-unswitch-threshold=0 -verify-loop-info -S < %s 2>&1 | FileCheck %s
+; RUN: opt < %s -loop-unswitch -loop-unswitch-threshold=0 -verify-loop-info -enable-mssa-loop-dependency=true -verify-memoryssa -S < %s 2>&1 | FileCheck %s
 
 ; This test contains two trivial unswitch condition in one loop. 
 ; LoopUnswitch pass should be able to unswitch the second one 
 ; after unswitching the first one.
 
 
 ; CHECK:  br i1 %cond1, label %..split_crit_edge, label %.loop_exit.split_crit_edge
 

test/Transforms/LoopUnswitch/unswitch-equality-undef.ll

 ; REQUIRES: asserts
-; RUN: opt < %s -instcombine -licm -loop-unswitch -loop-unswitch-threshold=1000 -disable-output -stats 2>&1| FileCheck %s
+; RUN: opt < %s -instcombine -licm -loop-unswitch -loop-unswitch-threshold=1000 -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output -stats 2>&1| FileCheck %s
 ; Check no loop unswitch is done because unswitching of equality expr with
 ; undef is unsafe before the freeze patch is committed.
 ; CHECK-NOT: Number of branches unswitched
 
 define void @ham(i64 %arg) local_unnamed_addr {
 bb:
   %tmp = icmp eq i64 %arg, 0
   br i1 %tmp, label %bb3, label %bb1

test/Transforms/LoopUnswitch/unswitch-select.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -loop-unswitch -disable-output -stats 2>&1| FileCheck %s
+; RUN: opt < %s -loop-unswitch -enable-mssa-loop-dependency=true -verify-memoryssa -disable-output -stats 2>&1| FileCheck %s
 
 ; Check the select statement in the loop will be unswitched.
 ; CHECK: 1 loop-unswitch - Number of selects unswitched
 define i32 @test(i1 zeroext %x, i32 %a) local_unnamed_addr #0 {
 entry:
   br label %while.cond
 
 while.cond:                                       ; preds = %while.body, %entry