[CodeMoverUtils] Add optional data dependence checks using MSSA

[RithikSharma]

Summary

isSafeToMoveBefore uses Dependence Info to check for flow/anti/output dependence, this patch adds alternative checks using MSSA.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

221

return !std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
                 [&DI, &I](Instruction *CurInst) {
                   auto DepResult = DI.depends(&I, CurInst, true);
                   if (DepResult &&
                       (DepResult->isOutput() || DepResult->isFlow() ||
                        DepResult->isAnti()))
                     return true;
                   return false;
                 }));

236

Below is the cleaner version of your code:

MemoryUseOrDef *MemUseOrDef = MSSAU.getMemorySSA()->getMemoryAccess(&I);
if (isa<MemoryDef>(MemUseOrDef))
  return false;
return !std::any_of(InstsToCheck.begin(), InstsToCheck.end(), &MSSAU, &I](Instruction *CurInst) {
  MemoryUseOrDef *MemUseOrDef = MSSAU.getMemorySSA()->getMemoryAccess(CurInst);
  return isa<MemoryDef>(MemUseOrDef);
});

But this code is very restrictive. It can be improved by considering the relationship between I and CurInst, e.g. if they don't access the same memory then it should still be safe.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

512–515

change all the existing ones to &DI, nullptr)) to make sure you are testing DI.

[RithikSharma]

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

512–515

Sure but even when we give preference to DI?

if (DI)
   return isDependenceSafe(I, *DI, InstsToCheck);
 else if (MSSAU)
   return isDependenceSafe(I, *MSSAU, InstsToCheck);

[bmahjour]

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

581

Please also add a check to make sure independent memory load/stores can be moved passed each other. For example, %load2 should be able to move before the store to B.

store i32 %load1, i32* %arrayidx_B, align 4
%load2 = load i32, i32* %arrayidx_A, align 4

[fhahn]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

227

The if here doesn't add much I think. It would be simpler to just `return DepResult && DepResult->isOutput() || DepResult->isFlow() ||

DepResult->isAnti()`?

232

I don't think there is a reason to pass MemorySSAUpdater here, as you don't modify the IR. Just pass MemorySSA directly.

Also, please add a comment what the logic behind the checks is (same for the DI version)

244

What we are doing here is basically checking if 2 instructions may alias, right? Given that, the variable names seem a bit confusing. Also, the function returns true if either IsFlowOrOutput or IsAnti is true. Could you just return true directly?

358

Does it make sense to even call this function if either of those are not available, i.e. if all those required wouldn't it make sense to assert that they are all provided or turn them into references?

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

221

1. !any_of can change to none_of
2. use llvm::none_of instead of std::none_of

return none_of(InstsToCheck, [&DI, &I]
...

249

DestMemUseOrDef is of type MemoryUseOrDef, so it must be a MemoryUse of MemoryDef.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

512–515

Yes, because the code may change.

581

Good idea. The test should include all four types of dependence, and all should be considered safe. Also make sure they are bidirectional, so check both move forward and move backward.

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

227

Thanks, yeah I should directly return it. I missed it in this diff as well. I'll update in the next diff.

232

Acknowledged and updated to MemorySSA instead of MemorySSAUpdater. Will add the required comments in the next diff.

358

I'm sorry, I didn't understand. We need at least DI or MSSA to find dependency.

[fhahn]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

358

I meant does it make sense to call this function without PDT == nullptr for example? It seems like it is kind of required here, right?

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

358

Got it, why is PDT not a reference if it is required, right? Most code motion clients example LICM don't have PDT so until we find a way to prove control flow equivalence with some other analysis we need to keep the !PDT check but we did changed PDT into pointer as we will be expecting nullptr in near future.

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

221

Acknowledged, updated with changes.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

512–515

Thanks, Acknowledged.

[bmahjour]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

259

I don't understand why we need this part: || InstLastDefMA == CurInstDefMA. Wouldn't it suffice to check the reaching def of the use against the instruction being moved (the first part of this condition) ? Do you have a test that would fail if you remove it?

264

Do we really need InstDefMA == CurInstLastDefMA ||? See my comment above.

[Whitney]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

264

This is needed for cases like

store 1, ptr
x = load ptr
store 0, ptr

check if x is safe to move after store 0, ptr.
e.g. in https://reviews.llvm.org/D83543

// Anti forward dependency
EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI));

the defining access of x is store 1, ptr, the getClobberingMemoryAccess of store 0, ptr is x.
Not sure if this works if there is no store before the memory use.
I wonder if there is a better to do this, like if there is a way to directly get x from store 0, ptr.

[RithikSharma]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

259

Yes we have a failure if we remove this,

isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, nullptr, &MSSA)

[bmahjour]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

264

That still won't work if the first store is after the load or is absent all together. I don't think there is a way to get x from store 0, ptr because there is no def-use relationship between them. This highlights the need to use Alias Analysis instead or in combination with MSSA. I see that current LICM has similar issues, for example see comment in pointerInvalidatedByLoopWithMSSA().

I suppose improvements can be made in steps. Currently LICM uses an over-approximation to deal with this situation by looking for any definitions that are locally dominated by the sinking use. Perhaps we can start with that and gradually add aliasing queries into the equation.

[bmahjour]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

255

We also need to check for InstLastDefMA == CurInstLastDefMA in case both definitions are clobbered by the same memory phi.

[bmahjour]

This can be closed in favor of https://reviews.llvm.org/D84589. Please migrate the tests and close the review. Thanks.

llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h

 #define LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H
 
 namespace llvm {
 
 class BasicBlock;
 class DependenceInfo;
 class DominatorTree;
 class Instruction;
+class MemorySSA;
 class PostDominatorTree;
 
 /// Return true if \p I0 and \p I1 are control flow equivalent.
 /// Two instructions are control flow equivalent if their basic blocks are
 /// control flow equivalent.
 bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p BB0 and \p BB1 are control flow equivalent.
 /// Two basic blocks are control flow equivalent if when one executes, the other
 /// is guaranteed to execute.
 bool isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p I can be safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                         DominatorTree &DT,
                         const PostDominatorTree *PDT = nullptr,
-                        DependenceInfo *DI = nullptr);
+                        DependenceInfo *DI = nullptr,
+                        MemorySSA *MSSA = nullptr);
 
 /// Return true if all instructions (except the terminator) in \p BB can be
 /// safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
                         DominatorTree &DT,
                         const PostDominatorTree *PDT = nullptr,
-                        DependenceInfo *DI = nullptr);
+                        DependenceInfo *DI = nullptr,
+                        MemorySSA *MSSA = nullptr);
 
 /// Move instructions, in an order-preserving manner, from \p FromBB to the
 /// beginning of \p ToBB when proven safe.
 void moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
                                     DominatorTree &DT,
                                     const PostDominatorTree &PDT,
                                     DependenceInfo &DI);
 

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

 // contained within a function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/OrderedInstructions.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "codemover-utils"
if (const CmpInst *Cmp2 = dyn_cast<CmpInst>(&V2)) {
               CmpInst::getSwappedPredicate(Cmp2->getInversePredicate()) &&
           Cmp1->getOperand(0) == Cmp2->getOperand(1) &&
           Cmp1->getOperand(1) == Cmp2->getOperand(0))
         return true;
     }
   return false;
 }
 
+bool isDependenceSafe(Instruction &I, DependenceInfo &DI,
+                      SmallPtrSet<Instruction *, 10> InstsToCheck) {
+  for (Instruction *CurInst : InstsToCheck) {
+    auto DepResult = DI.depends(&I, CurInst, true);
+    if (DepResult &&
+        (DepResult->isOutput() || DepResult->isFlow() || DepResult->isAnti()))
+      return false;
+  }
+  return true;
+}
+
+bool isDependenceSafe(Instruction &I, MemorySSA &MSSA,
+                      SmallPtrSet<Instruction *, 10> InstsToCheck) {
+  MemoryUseOrDef *MemUseOrDef = MSSA.getMemoryAccess(&I);
+  if (!MemUseOrDef)
+    return true;
+  for (Instruction *CurInst : InstsToCheck) {
+    MemoryUseOrDef *DestMemUseOrDef = MSSA.getMemoryAccess(CurInst);
+    if (!DestMemUseOrDef)
+      continue;
+    bool IsFlowOrOutput = false;
+    bool IsAnti = false;
+    MemoryAccess *MemAccess = MemUseOrDef->getDefiningAccess();
+    MemoryAccess *DestMemAccess = DestMemUseOrDef->getDefiningAccess();
+    if (isa<MemoryDef>(MemUseOrDef)) {
+      if (MemoryDef *DestMemDef = dyn_cast<MemoryDef>(DestMemAccess)) {
+        if (DestMemDef == MemUseOrDef) {
+          IsFlowOrOutput = true;
+        }
+      }
+    } else if (isa<MemoryUse>(MemUseOrDef)) {
+      if (isa<MemoryDef>(DestMemUseOrDef)) {
+        MemoryDef *MemDef = dyn_cast<MemoryDef>(MemAccess);
+        MemoryDef *DestMemDef = dyn_cast<MemoryDef>(DestMemAccess);
+        if (MemDef == DestMemDef) {
+          IsAnti = true;
+        }
+      }
+    }
+    if (IsFlowOrOutput || IsAnti)
+      return false;
+  }
+  return true;
+}
+
+bool isDependenceSafe(Instruction &I, DependenceInfo *DI, MemorySSA *MSSA,
+                      SmallPtrSet<Instruction *, 10> InstsToCheck) {
+  if (DI)
+    return isDependenceSafe(I, *DI, InstsToCheck);
+  else if (MSSA)
+    return isDependenceSafe(I, *MSSA, InstsToCheck);
+  return false;
+}
+
 bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
                                    const DominatorTree &DT,
                                    const PostDominatorTree &PDT) {
   return isControlFlowEquivalent(*I0.getParent(), *I1.getParent(), DT, PDT);
 }
 
 bool llvm::isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                                    const DominatorTree &DT,
if (!InBetweenInsts.insert(CurInst).second)
       continue;
 
     getNextInsts(*CurInst, WorkList);
   }
 }
 
 bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                               DominatorTree &DT, const PostDominatorTree *PDT,
-                              DependenceInfo *DI) {
+                              DependenceInfo *DI, MemorySSA *MSSA) {
   // Skip tests when we don't have PDT or DI
-  if (!PDT || !DI)
+  if (!PDT || !(DI || MSSA))
     return false;
 
   // Cannot move itself before itself.
   if (&I == &InsertPoint)
     return false;
 
   // Not moved.
   if (I.getNextNode() == &InsertPoint)
if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
 
                       return false;
                     })) {
       return reportInvalidCandidate(I, MayThrowException);
     }
 
   // Check if I has any output/flow/anti dependences with instructions from \p
   // StartInst to \p EndInst.
-  if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
-                  [&DI, &I](Instruction *CurInst) {
-                    auto DepResult = DI->depends(&I, CurInst, true);
-                    if (DepResult &&
-                        (DepResult->isOutput() || DepResult->isFlow() ||
-                         DepResult->isAnti()))
-                      return true;
-                    return false;
-                  }))
+  if (!isDependenceSafe(I, DI, MSSA, InstsToCheck))
     return reportInvalidCandidate(I, HasDependences);
 
   return true;
 }
 
 bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
                               DominatorTree &DT, const PostDominatorTree *PDT,
-                              DependenceInfo *DI) {
+                              DependenceInfo *DI, MemorySSA *MSSA) {
   return llvm::all_of(BB, [&](Instruction &I) {
     if (BB.getTerminator() == &I)
       return true;
 
-    return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI);
+    return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI, MSSA);
   });
 }
 
 void llvm::moveInstructionsToTheBeginning(BasicBlock &FromBB, BasicBlock &ToBB,
                                           DominatorTree &DT,
                                           const PostDominatorTree &PDT,
                                           DependenceInfo &DI) {
   for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

 //===- CodeMoverUtils.cpp - Unit tests for CodeMoverUtils ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/CodeMoverUtils.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
   SMDiagnostic Err;
   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
   if (!Mod)
     Err.print("CodeMoverUtilsTests", errs());
   return Mod;
 }
 
-static void run(Module &M, StringRef FuncName,
-                function_ref<void(Function &F, DominatorTree &DT,
-                                  PostDominatorTree &PDT, DependenceInfo &DI)>
-                    Test) {
+static void
+run(Module &M, StringRef FuncName,
+    function_ref<void(Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+                      DependenceInfo &DI, MemorySSA &MSSA)>
   auto *F = M.getFunction(FuncName);
   DominatorTree DT(*F);
   PostDominatorTree PDT(*F);
   TargetLibraryInfoImpl TLII;
   TargetLibraryInfo TLI(TLII);
   AssumptionCache AC(*F);
   AliasAnalysis AA(TLI);
   LoopInfo LI(DT);
   ScalarEvolution SE(*F, TLI, AC, DT, LI);
   DependenceInfo DI(F, &AA, &SE, &LI);
-  Test(*F, DT, PDT, DI);
+  MemorySSA MSSA(*F, &AA, &DT);
+  Test(*F, DT, PDT, DI, MSSA);
 }
 
 static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {
   for (BasicBlock &BB : F)
     if (BB.getName() == Name)
       return &BB;
   llvm_unreachable("Expected to find basic block!");
 }
std::unique_ptr<Module> M =
                  if.third:
                    store i32 3, i32* %i, align 4
                    br label %if.third.end
                  if.third.end:
                    ret void
                  })");
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");
         EXPECT_TRUE(
             isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT));
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");
         EXPECT_TRUE(
             isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
 
         BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third");
std::unique_ptr<Module> M =
                  if.sixth.else:
                    store i32 9, i32* %i, align 4
                    br label %if.sixth.end
                  if.sixth.end:
                    ret void
                  })");
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");
         BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third");
         BasicBlock *ThirdElseBody = getBasicBlockByName(F, "if.third.else");
         EXPECT_TRUE(
             isControlFlowEquivalent(*FirstIfBody, *ThirdElseBody, DT, PDT));
         EXPECT_TRUE(
             isControlFlowEquivalent(*SecondIfBody, *ThirdElseBody, DT, PDT));
std::unique_ptr<Module> M =
          if.inner.second:
            store i32 2, i32* %i, align 4
            br label %if.second.end
          if.second.end:
            ret void
          })");
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first");
         BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first");
         BasicBlock *SecondOuterIfBody =
             getBasicBlockByName(F, "if.outer.second");
         BasicBlock *SecondInnerIfBody =
             getBasicBlockByName(F, "if.inner.second");
         EXPECT_TRUE(isControlFlowEquivalent(*FirstInnerIfBody,
                                             *SecondInnerIfBody, DT, PDT));
std::unique_ptr<Module> M = parseIR(
          if.fourth:
            store i32 4, i32* %i, align 4
            br label %if.fourth.end
          if.fourth.end:
            ret void
          })");
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first");
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second");
         EXPECT_FALSE(
             isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
 
         BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.inner.third");
         BasicBlock *FourthIfBody = getBasicBlockByName(F, "if.fourth");
         EXPECT_TRUE(
std::unique_ptr<Module> M =
                  if.third:
                    store i32 3, i32* %i, align 4
                    br label %if.third.end
                  if.third.end:
                    ret void
                  })");
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first");
         BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second");
         // Limitation: if we can prove cond haven't been modify between %0 and
         // %1, then we can prove FirstIfBody and SecondIfBody are control flow
         // equivalent.
         EXPECT_FALSE(
             isControlFlowEquivalent(*FirstIfBody, *SecondIfBody, DT, PDT));
 
std::unique_ptr<Module> M =
                    ret void
                  succ1succ1:
                    br label %bb
                  bb:
                    ret void
                  })");
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         BasicBlock &Idom = F.front();
         assert(Idom.getName() == "idom" && "Expecting BasicBlock idom");
         BasicBlock &BB = F.back();
         assert(BB.getName() == "bb" && "Expecting BasicBlock bb");
         EXPECT_FALSE(isControlFlowEquivalent(Idom, BB, DT, PDT));
       });
 }
 
std::unique_ptr<Module> M = parseIR(
            ret void
          }
          declare void @safecall() nounwind nosync willreturn
          declare void @unsafecall1()
          declare void @unsafecall2())");
 
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         BasicBlock *Entry = getBasicBlockByName(F, "entry");
         Instruction *CI_safecall = Entry->front().getNextNode();
         assert(isa<CallInst>(CI_safecall) &&
                "Expecting CI_safecall to be a CallInst");
         Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode();
         assert(isa<CallInst>(CI_unsafecall) &&
                "Expecting CI_unsafecall to be a CallInst");
         BasicBlock *ForBody = getBasicBlockByName(F, "for.body");
         Instruction &PN = ForBody->front();
         assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode");
         Instruction *SI_A5 =
             getInstructionByName(F, "arrayidx_A5")->getNextNode();
         Instruction *SI = getInstructionByName(F, "arrayidx_A")->getNextNode();
         Instruction *LI1 = getInstructionByName(F, "load1");
         Instruction *LI2 = getInstructionByName(F, "load2");
         Instruction *SI_A6 =
             getInstructionByName(F, "arrayidx_A6")->getNextNode();
 
         // Can move after CI_safecall, as it does not throw, not synchronize, or
         // must return.
         EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(),
                                        *CI_safecall->getNextNode(), DT, &PDT,
-                                       &DI));
+                                       &DI, &MSSA));
+        EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(),
+                                       *CI_safecall->getNextNode(), DT, &PDT,
+                                       nullptr, &MSSA));
 
         // Cannot move CI_unsafecall, as it may throw.
         EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(),
-                                        *CI_unsafecall, DT, &PDT, &DI));
+                                        *CI_unsafecall, DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(),
+                                        *CI_unsafecall, DT, &PDT, nullptr,
+                                        &MSSA));
 
         // Moving instruction to non control flow equivalent places are not
         // supported.
         EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT,
-                                        &PDT, &DI));
+                                        &PDT, &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT,
+                                        &PDT, nullptr, &MSSA));
 
         // Moving PHINode is not supported.
         EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(),
-                                        DT, &PDT, &DI));
+                                        DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(),
+                                        DT, &PDT, nullptr, &MSSA));
 
         // Cannot move non-PHINode before PHINode.
-        EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT,
+                                        nullptr, &MSSA));
 
         // Moving Terminator is not supported.
+        EXPECT_FALSE(isSafeToMoveBefore(
+            *Entry->getTerminator(), *PN.getNextNode(), DT, &PDT, &DI, &MSSA));
         EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(),
-                                        *PN.getNextNode(), DT, &PDT, &DI));
+                                        *PN.getNextNode(), DT, &PDT, nullptr,
+                                        &MSSA));
 
         // Cannot move %arrayidx_A after SI, as SI is its user.
         EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(),
-                                        DT, &PDT, &DI));
+                                        DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(),
+                                        DT, &PDT, nullptr, &MSSA));
 
         // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand.
         EXPECT_FALSE(
-            isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI));
+            isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT,
+                                        nullptr, &MSSA));
 
         // Cannot move LI2 after SI_A6, as there is a flow dependence.
-        EXPECT_FALSE(
-            isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, &DI));
+        EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT,
+                                        &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT,
+                                        nullptr, &MSSA));
 
         // Cannot move SI after LI1, as there is a anti dependence.
         EXPECT_FALSE(
-            isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI));
+            isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT,
+                                        nullptr, &MSSA));
 
         // Cannot move SI_A5 after SI, as there is a output dependence.
-        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI));
+        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, nullptr, &MSSA));
 
         // Can move LI2 before LI1, as there is only an input dependence.
-        EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI));
+        EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI, &MSSA));
+        EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, nullptr, &MSSA));
       });
 }
 
 TEST(CodeMoverUtils, IsSafeToMoveTest2) {
   LLVMContext C;
 
   std::unique_ptr<Module> M =
       parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {
std::unique_ptr<Module> M =
                    %sub = sub i32 %sub_op0, %op1
                    br label %if.end.second
                  if.end.second:
                    ret void
                  })");
 
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         Instruction *AddInst = getInstructionByName(F, "add");
         Instruction *SubInst = getInstructionByName(F, "sub");
 
         // Cannot move as %user uses %add and %sub doesn't dominates %user.
-        EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, nullptr, &MSSA));
 
         // Cannot move as %sub_op0 is an operand of %sub and %add doesn't
         // dominates %sub_op0.
-        EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSA));
       });
 }
 
 TEST(CodeMoverUtils, IsSafeToMoveTest3) {
   LLVMContext C;
 
   std::unique_ptr<Module> M = parseIR(C, R"(define void @foo(i64 %N) {
                  entry:
                    br label %for.body
                  for.body:
                    %i = phi i64 [ 0, %entry ], [ %inc, %for.latch ]
                    %inc = add nsw i64 %i, 1
                    br label %for.latch
                  for.latch:
                    %cmp = icmp slt i64 %inc, %N
                    br i1 %cmp, label %for.body, label %for.end
                  for.end:
                    ret void
                  })");
 
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         Instruction *IncInst = getInstructionByName(F, "inc");
         Instruction *CmpInst = getInstructionByName(F, "cmp");
 
         // Can move as the incoming block of %inc for %i (%for.latch) dominated
         // by %cmp.
-        EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI));
+        EXPECT_TRUE(
+            isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI, &MSSA));
+        EXPECT_TRUE(
+            isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, nullptr, &MSSA));
       });
 }
 
 TEST(CodeMoverUtils, IsSafeToMoveTest4) {
   LLVMContext C;
 
   std::unique_ptr<Module> M =
       parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {
std::unique_ptr<Module> M =
                    %sub = sub i32 %sub_op0, %op1
                    br label %if.end.second
                  if.end.second:
                    ret void
                  })");
 
   run(*M, "foo",
       [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
-          DependenceInfo &DI) {
+          DependenceInfo &DI, MemorySSA &MSSA) {
         Instruction *AddInst = getInstructionByName(F, "add");
         Instruction *SubInst = getInstructionByName(F, "sub");
 
         // Cannot move as %user uses %add and %sub doesn't dominates %user.
-        EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, nullptr, &MSSA));
 
         // Cannot move as %sub_op0 is an operand of %sub and %add doesn't
         // dominates %sub_op0.
-        EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI, &MSSA));
+        EXPECT_FALSE(
+            isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSA));
       });
 }