[CodeMoverUtils] Added an API to check if an instruction can be safely moved before another instruction.

[Whitney]

Summary

Added an API to check if an instruction can be safely moved before another instruction. In future PRs, we will like to add support of moving instructions between blocks that are not control flow equivalent, and add other APIs to enhance usability, e.g. moving basic blocks, moving list of instructions...
Loop Fusion will be its first user. When there is intervening code in between two loops, fusion is currently unable to fuse them. Loop Fusion can use this utility to check if the intervening code can be safely moved before or after the two loops, and move them, then it can successfully fuse them.

[jdoerfert]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

85

Why PDT. domainates? Operands need to dominate the use:
DT.dominates(OpInst, InsertPoint)

Below, dominance is allowing the move but post-dominance would prevent it.

a = add ...
if (abc) {
   IP = ...
   [..]
   I = add a, ... 
}

144

High-level question:

Does dependence info track dependences between side-effects (e.g., global write) and potentially throwing instructions?
E.g., would this allow me to move I to IP in the example below:

IP = ...
call void @unknown() readnone
store ... // <- I

Thinking about it, if you move a (generic) side-effect you need to check nounwind and willreturn for all instructions you move it over.

Nits:
No need for inline (let the compiler figure it out).
If you reorder, forward declarations not necessary (= easier to maintain).

[Meinersbur]

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

30–32

[style] Start function names with lower case letters.

llvm/lib/Analysis/PostDominators.cpp

59

[serious] Should ensure that not both of the instructions are PHIs. These do not (post-)dominate each other even if one follows the other. See https://llvm.org/PR26718.

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

50

[suggestion] Could just return false in this case. Even if this is a wrong use of the interface, callers should not do anything.

[Whitney]

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

30–32

Actually I intensionally start with upper case for this function, as I see global functions in other files also start with upper case (e.g. CloneFunction.cpp). Do you know which way is the recommenced style?

[Meinersbur]

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

30–32

Functions with starting capital letter is an older style. It's just that nobody put in the work to do the style conversion yet.

Recently, the community was even discussing applying lower camelCase to variables as well and apply it wholesale with a conversion script.

In any case, PascalCase style for functions is deprecated and I see no reason why no going to the current coding convention.

[Whitney]

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

30–32

Good to know! I thought there is a different convention for different kind of functions.

[bmahjour]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

144

Does dependence info track dependences between side-effects (e.g., global write) and potentially throwing instructions

Dependence analysis knows nothing about function calls, so it makes worst case assumption and assumes there is confused dependency between calls and other memory accesses (even if the call takes no arguments and is readnone). This should be safe for now but is obviously too pessimistic. I think dependence analysis could be improved to take some obvious cases of function calls into account, but I don't think exception handling would be something it can be taught about.

It also raises the question, to what extend do we need to be worried about exceptions and side-effects at higher optimization levels? For instance one could go as far as saying any store cannot be moved past any other store (even if the memories accessed are disjoint) because for example the first store could cause a segfault before the second store has had a chance to execute.

[jdoerfert]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

144

It's not as bad fortunately. A segfault (or similar) caused by a memory access is undefined behavior (UB).

What we need to make sure is that we do not move a store (or similar) across something that:

might synchronize (but nothing else, incl. readnone)
might throw       (same as above)
might never return = endless loop (only not move it before and only if the pointer is not known dereferenceable and never return call/loop is side effect and synchronization free).

We probably want tests for these.

[Whitney]

With this change, no instructions are considered safe to move across instructions that may throw, or call instructions that may not return or may synchronize, which is straighter than @jdoerfert suggestion. We can generalize it when needed. @jdoerfert What do you think?

[bmahjour]

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

134

None of these checks are required for simple instructions (such as add and icmp which are used in the test bellow). I think we should only check for throw/sync/noreturn if isSafeToSpeculativelyExecute(I) returns false.

157

remove the dump or guard it.

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

71

Please see my comment above. I think we should use an instruction with potential side-effect to really test what moves across safecalls and what doesn't move across unsafe calls. We should also test that instructions without side-effect can be moved across function calls as long as def-use dependency is preserved.

[Whitney]

Addressed all comments from Bardia.

[jdoerfert]

I'm fine with this @bmahjour @Meinersbur please accept if you are satisfied.

[bmahjour]

LGTM.

[Whitney]

Landed.

[vitalybuka]

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

146

https://github.com/llvm/llvm-project/commit/ad58d1a9d117d46916bfff77aad0c369cee91cea.diff
to fix

Note: Google Test filter = CodeMoverUtils.BasicTest
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from CodeMoverUtils
[ RUN      ] CodeMoverUtils.BasicTest
/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:145:9: runtime error: reference binding to null pointer of type 'llvm::Instruction'
    #0 0x45d68e in operator() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:145:9
    #1 0x45d68e in void llvm::function_ref<void (llvm::Function&, llvm::DominatorTree&, llvm::PostDominatorTree&, llvm::DependenceInfo&)>::callback_fn<CodeMoverUtils_BasicTest_Test::TestBody()::$_0>(long, llvm::Function&, llvm::DominatorTree&, llvm::PostDominatorTree&, llvm::DependenceInfo&) /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/include/llvm/ADT/STLExtras.h:108:12
    #2 0x45be28 in run /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:45:3
    #3 0x45be28 in CodeMoverUtils_BasicTest_Test::TestBody() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:102:3
    #4 0x94138b in testing::Test::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2474:5
    #5 0x94207a in testing::TestInfo::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2656:11
    #6 0x942a42 in testing::TestCase::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2774:28
    #7 0x94a042 in testing::internal::UnitTestImpl::RunAllTests() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:4649:43
    #8 0x949ab5 in testing::UnitTest::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:4257:10
    #9 0x939d23 in RUN_ALL_TESTS /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/include/gtest/gtest.h:2233:46
    #10 0x939d23 in main /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/UnitTestMain/TestMain.cpp:50:10
    #11 0x7f1b4d6402e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #12 0x412ad9 in _start (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan/unittests/Transforms/Utils/UtilsTests+0x412ad9)

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp:145:9 in 

********************

[Whitney]

llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp

146

Thanks for putting in the fix.

llvm/include/llvm/Analysis/PostDominators.h

 public:
   using Base = PostDomTreeBase<BasicBlock>;
 
   PostDominatorTree() = default;
   explicit PostDominatorTree(Function &F) { recalculate(F); }
   /// Handle invalidation explicitly.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
+
+  // Ensure base-class overloads are visible.
+  using Base::dominates;
+
+  /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before
+  /// \p I1 if they belongs to the same basic block.
+  bool dominates(const Instruction *I1, const Instruction *I2) const;
 };
 
 /// Analysis pass which computes a \c PostDominatorTree.
 class PostDominatorTreeAnalysis
     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
 
   static AnalysisKey Key;

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

+//===- Transform/Utils/CodeMoverUtils.h - CodeMover Utils -------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions determine movements are safe on basic blocks, and
+// instructions contained within a function.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H
+#define LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H
+
+namespace llvm {
+
+class DependenceInfo;
+class DominatorTree;
+class Instruction;
+class PostDominatorTree;
+
+/// Return true if \p I0 and \p I1 are control flow equivalent.
+/// Two instructions are control flow equivalent if when one executes,
+/// the other is guaranteed to execute. This is determined using dominators
+/// and post-dominators: if A dominates B and B post-dominates A then A and B
+/// are control-flow equivalent.
+bool isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
+                             const DominatorTree &DT,
+                             const PostDominatorTree &PDT);
+
+/// Return true if \p I can be safely moved before \p InsertPoint.
+bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
+                        const DominatorTree &DT, const PostDominatorTree &PDT,
+                        DependenceInfo &DI);
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H

llvm/lib/Analysis/PostDominators.cpp

 //===- PostDominators.cpp - Post-Dominator Calculation --------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the post-dominator construction algorithms.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "postdomtree"
 
bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
                                    FunctionAnalysisManager::Invalidator &) {
   // Check whether the analysis, all analyses on functions, or the function's
   // CFG have been preserved.
   auto PAC = PA.getChecker<PostDominatorTreeAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
+bool PostDominatorTree::dominates(const Instruction *I1,
+                                  const Instruction *I2) const {
+  assert(I1 && I2 && "Expecting valid I1 and I2");
+
+  const BasicBlock *BB1 = I1->getParent();
+  const BasicBlock *BB2 = I2->getParent();
+
+  if (BB1 != BB2)
+    return Base::dominates(BB1, BB2);
+
+  // PHINodes in a block are unordered.
+  if (isa<PHINode>(I1) && isa<PHINode>(I2))
+    return false;
+
+  // Loop through the basic block until we find I1 or I2.
+  BasicBlock::const_iterator I = BB1->begin();
+  for (; &*I != I1 && &*I != I2; ++I)
+    /*empty*/;
+
+  return &*I == I2;
+}
+
 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
   DT.recalculate(F);
   return false;
 }
 
 void PostDominatorTreeWrapperPass::verifyAnalysis() const {
   if (VerifyDomInfo)
     assert(DT.verify(PostDominatorTree::VerificationLevel::Full));

llvm/lib/Transforms/Utils/CMakeLists.txt

 add_llvm_library(LLVMTransformUtils
   ASanStackFrameLayout.cpp
   AddDiscriminators.cpp
   BasicBlockUtils.cpp
   BreakCriticalEdges.cpp
   BuildLibCalls.cpp
   BypassSlowDivision.cpp
   CallPromotionUtils.cpp
   CanonicalizeAliases.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CodeExtractor.cpp
+  CodeMoverUtils.cpp
   CtorUtils.cpp
   DemoteRegToStack.cpp
   EntryExitInstrumenter.cpp
   EscapeEnumerator.cpp
   Evaluator.cpp
   FlattenCFG.cpp
   FunctionComparator.cpp
   FunctionImportUtils.cpp

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

+//===- CodeMoverUtils.cpp - CodeMover Utilities ----------------------------==//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions perform movements on basic blocks, and instructions
+// contained within a function.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CodeMoverUtils.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/IR/Dominators.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "codemover-utils"
+
+STATISTIC(HasDependences,
+          "Cannot move across instructions that has memory dependences");
+STATISTIC(MayThrowException, "Cannot move across instructions that may throw");
+STATISTIC(NotControlFlowEquivalent,
+          "Instructions are not control flow equivalent");
+STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported");
+STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported");
+
+bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1,
+                                   const DominatorTree &DT,
+                                   const PostDominatorTree &PDT) {
+  const BasicBlock *BB0 = I0.getParent();
+  const BasicBlock *BB1 = I1.getParent();
+  return ((DT.dominates(BB0, BB1) && PDT.dominates(BB1, BB0)) ||
+          (PDT.dominates(BB0, BB1) && DT.dominates(BB1, BB0)));
+}
+
+static bool reportInvalidCandidate(const Instruction &I,
+                                   llvm::Statistic &Stat) {
+  ++Stat;
+  LLVM_DEBUG(dbgs() << "Unable to move instruction: " << I << ". "
+                    << Stat.getDesc());
+  return false;
+}
+
+/// Collect all instructions in between \p StartInst and \p EndInst, and store
+/// them in \p InBetweenInsts.
+static void
+collectInstructionsInBetween(Instruction &StartInst, const Instruction &EndInst,
+                             SmallPtrSetImpl<Instruction *> &InBetweenInsts) {
+  assert(InBetweenInsts.empty() && "Expecting InBetweenInsts to be empty");
+
+  /// Get the next instructions of \p I, and push them to \p WorkList.
+  auto getNextInsts = [](Instruction &I,
+                         SmallPtrSetImpl<Instruction *> &WorkList) {
+    if (Instruction *NextInst = I.getNextNode())
+      WorkList.insert(NextInst);
+    else {
+      assert(I.isTerminator() && "Expecting a terminator instruction");
+      for (BasicBlock *Succ : successors(&I))
+        WorkList.insert(&Succ->front());
+    }
+  };
+
+  SmallPtrSet<Instruction *, 10> WorkList;
+  getNextInsts(StartInst, WorkList);
+  while (!WorkList.empty()) {
+    Instruction *CurInst = *WorkList.begin();
+    WorkList.erase(CurInst);
+
+    if (CurInst == &EndInst)
+      continue;
+
+    if (!InBetweenInsts.insert(CurInst).second)
+      continue;
+
+    getNextInsts(*CurInst, WorkList);
+  }
+}
+
+bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
+                              const DominatorTree &DT,
+                              const PostDominatorTree &PDT,
+                              DependenceInfo &DI) {
+  // Cannot move itself before itself.
+  if (&I == &InsertPoint)
+    return false;
+
+  // Not moved.
+  if (I.getNextNode() == &InsertPoint)
+    return true;
+
+  if (isa<PHINode>(I) || isa<PHINode>(InsertPoint))
+    return reportInvalidCandidate(I, NotMovedPHINode);
+
+  if (I.isTerminator())
+    return reportInvalidCandidate(I, NotMovedTerminator);
+
+  // TODO remove this limitation.
+  if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
+    return reportInvalidCandidate(I, NotControlFlowEquivalent);
+
+  // As I and InsertPoint are control flow equivalent, if I dominates
+  // InsertPoint, then I comes before InsertPoint.
+  const bool MoveForward = DT.dominates(&I, &InsertPoint);
+  if (MoveForward) {
+    // When I is being moved forward, we need to make sure the InsertPoint
+    // dominates every users. Or else, a user may be using an undefined I.
+    for (const Value *User : I.users())
+      if (auto *UserInst = dyn_cast<Instruction>(User))
+        if (!DT.dominates(&InsertPoint, UserInst))
+          return false;
+  } else {
+    // When I is being moved backward, we need to make sure all its opernads
+    // dominates the InsertPoint. Or else, an operand may be undefined for I.
+    for (const Value *Op : I.operands())
+      if (auto *OpInst = dyn_cast<Instruction>(Op))
+        if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
+          return false;
+  }
+
+  Instruction &StartInst = (MoveForward ? I : InsertPoint);
+  Instruction &EndInst = (MoveForward ? InsertPoint : I);
+  SmallPtrSet<Instruction *, 10> InstsToCheck;
+  collectInstructionsInBetween(StartInst, EndInst, InstsToCheck);
+  if (!MoveForward)
+    InstsToCheck.insert(&InsertPoint);
+
+  // Check if there exists instructions which may throw, may synchonize, or may
+  // never return, from I to InsertPoint.
+  InstsToCheck.insert(&I);
+  if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(), [](Instruction *I) {
+        if (I->mayThrow())
+          return true;
+
+        const CallBase *CB = dyn_cast<CallBase>(I);
+        if (!CB)
+          return false;
+        if (!CB->hasFnAttr(Attribute::WillReturn))
+          return true;
+        if (!CB->hasFnAttr(Attribute::NoSync))
+          return true;
+
+        return false;
+      })) {
+    return reportInvalidCandidate(I, MayThrowException);
+  }
+  InstsToCheck.erase(&I);
+
+  // 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) {
+                    CurInst->dump();
+                    auto DepResult = DI.depends(&I, CurInst, true);
+                    if (DepResult &&
+                        (DepResult->isOutput() || DepResult->isFlow() ||
+                         DepResult->isAnti()))
+                      return true;
+                    return false;
+                  }))
+    return reportInvalidCandidate(I, HasDependences);
+
+  return true;
+}

llvm/unittests/Transforms/Utils/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   TransformUtils
   )
 
 add_llvm_unittest(UtilsTests
   ASanStackFrameLayoutTest.cpp
   BasicBlockUtilsTest.cpp
   CloningTest.cpp
   CodeExtractorTest.cpp
+  CodeMoverUtilsTest.cpp
   FunctionComparatorTest.cpp
   IntegerDivisionTest.cpp
   LocalTest.cpp
   SizeOptsTest.cpp
   SSAUpdaterBulkTest.cpp
   UnrollLoopTest.cpp
   ValueMapperTest.cpp
   )

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/AssumptionCache.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/SourceMgr.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) {
+  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);
+}
+
+TEST(CodeMoverUtils, BasicTest) {
+  LLVMContext C;
+
+  // void safecall() noexcept willreturn nosync;
+  // void unsafecall();
+  // void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C,
+  //          long N) {
+  //   N = N + 1;
+  //   safecall();
+  //   unsafecall();
+  //   for (long i = 0; i < N; ++i) {
+  //     A[5] = 5;
+  //     A[i] = 0;
+  //     B[i] = A[i];
+  //     C[i] = A[i];
+  //     A[6] = 6;
+  //   }
+  // }
+  std::unique_ptr<Module> M = parseIR(
+      C,
+      "define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C\n"
+      "                  , i64 %N_) {\n"
+      "entry:\n"
+      "  %N = add nsw i64 %N_, 1\n"
+      "  call void @safecall()\n"
+      "  %cmp1 = icmp slt i64 0, %N\n"
+      "  call void @unsafecall()\n"
+      "  br i1 %cmp1, label %for.body, label %for.end\n"
+      "for.body:\n"
+      "  %i = phi i64 [ 0, %entry ], [ %inc, %for.body ]\n"
+      "  %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5\n"
+      "  store i32 5, i32* %arrayidx_A5, align 4\n"
+      "  %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i\n"
+      "  store i32 0, i32* %arrayidx_A, align 4\n"
+      "  %load1 = load i32, i32* %arrayidx_A, align 4\n"
+      "  %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i\n"
+      "  store i32 %load1, i32* %arrayidx_B, align 4\n"
+      "  %load2 = load i32, i32* %arrayidx_A, align 4\n"
+      "  %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i\n"
+      "  store i32 %load2, i32* %arrayidx_C, align 4\n"
+      "  %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6\n"
+      "  store i32 6, i32* %arrayidx_A6, align 4\n"
+      "  %inc = add nsw i64 %i, 1\n"
+      "  %cmp = icmp slt i64 %inc, %N\n"
+      "  br i1 %cmp, label %for.body, label %for.end\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n"
+      "declare void @safecall() nounwind nosync willreturn\n"
+      "declare void @unsafecall()\n");
+
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT,
+          DependenceInfo &DI) {
+        Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI++);
+        assert(Entry->getName() == "entry" && "Expecting BasicBlock 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 = &*(FI++);
+        assert(ForBody->getName() == "for.body" &&
+               "Expecting BasicBlock for.body");
+        Instruction &PN = ForBody->front();
+        assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode");
+        Instruction *SI_A5 = PN.getNextNode()->getNextNode();
+        assert(isa<StoreInst>(SI_A5) &&
+               SI_A5->getOperand(1)->getName() == "arrayidx_A5" &&
+               "Expecting store to arrayidx_A5");
+        Instruction *SI = SI_A5->getNextNode()->getNextNode();
+        assert(isa<StoreInst>(SI) &&
+               SI->getOperand(1)->getName() == "arrayidx_A" &&
+               "Expecting store to arrayidx_A");
+        Instruction *LI1 = SI->getNextNode();
+        assert(LI1->getName() == "load1" && "Expecting LI1 to be load1");
+        Instruction *LI2 = LI1->getNextNode()->getNextNode()->getNextNode();
+        assert(LI2->getName() == "load2" && "Expecting LI2 to be load2");
+  Instruction *SI_A6 = LI2->getNextNode()->getNextNode()->getNextNode()->getNextNode();
+        assert(isa<StoreInst>(SI_A6) &&
+               SI_A6->getOperand(1)->getName() == "arrayidx_A6" &&
+               "Expecting store to arrayidx_A6");
+
+        // Can move CI_safecall, as it does not throw.
+        EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall, *CI_safecall->getPrevNode(), DT, PDT, DI));
+
+        // Cannot move CI_unsafecall, as it may throw.
+        EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall, *CI_unsafecall->getPrevNode(), DT, PDT, DI));
+
+        // Moving instruction to non control flow equivalent places are not
+        // supported.
+        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, PDT, DI));
+
+        // Moving PHINode is not supported.
+        EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getPrevNode(), DT, PDT, DI));
+
+        // Cannot move non-PHINode before PHINode.
+        EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI));
+
+        // Moving Terminator is not supported.
+        EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), *PN.getNextNode(), DT,
+                                PDT, DI));
+
+        // Cannot move %arrayidx_A after SI, as SI is its user.
+        EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), DT, PDT, DI));
+
+        // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand.
+        EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI));
+
+        // Cannot move LI2 after SI_A6, as there is a flow dependence.
+        EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI));
+
+        // Cannot move SI after LI1, as there is a anti dependence.
+        EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI));
+
+        // Cannot move SI_A5 after SI, as there is a output dependence.
+        EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI));
+
+        // Can move LI2 before LI1, as there is only an input dependence.
+        EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI));
+      });
+}