Index: llvm/include/llvm/Analysis/OrderedInstructions.h
===================================================================
--- llvm/include/llvm/Analysis/OrderedInstructions.h
+++ llvm/include/llvm/Analysis/OrderedInstructions.h
@@ -45,6 +45,7 @@
   /// or if the first instruction comes before the second in the same basic
   /// block.
   bool dfsBefore(const Instruction *, const Instruction *) const;
+  bool bfsLevelBefore(const Instruction *, const Instruction *) const;
 };
 
 } // end namespace llvm
Index: llvm/lib/Analysis/OrderedInstructions.cpp
===================================================================
--- llvm/lib/Analysis/OrderedInstructions.cpp
+++ llvm/lib/Analysis/OrderedInstructions.cpp
@@ -43,3 +43,15 @@
   DomTreeNode *DB = DT->getNode(InstB->getParent());
   return DA->getDFSNumIn() < DB->getDFSNumIn();
 }
+
+bool OrderedInstructions::bfsLevelBefore(const Instruction *InstA,
+                                    const Instruction *InstB) const {
+  // Use ordered basic block in case the 2 instructions are in the same basic
+  // block.
+  if (InstA->getParent() == InstB->getParent())
+    return localDominates(InstA, InstB);
+
+  DomTreeNode *DA = DT->getNode(InstA->getParent());
+  DomTreeNode *DB = DT->getNode(InstB->getParent());
+  return DA->getLevel() < DB->getLevel();
+}
Index: llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
===================================================================
--- llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
+++ llvm/lib/Transforms/Utils/CodeMoverUtils.cpp
@@ -319,7 +319,7 @@
 
   OrderedInstructions OI(&DT);
   DT.updateDFSNumbers();
-  const bool MoveForward = OI.dfsBefore(&I, &InsertPoint);
+  const bool MoveForward = OI.bfsLevelBefore(&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.
Index: llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
===================================================================
--- llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
+++ llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp
@@ -613,3 +613,39 @@
         EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, PDT, DI));
       });
 }
+
+TEST(CodeMoverUtils, IsSafeToMoveTest4) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M =
+      parseIR(C, R"(define void @foo(i1 %cond, i32 %op0, i32 %op1) {
+                 entry:
+                   br i1 %cond, label %if.end.first, label %if.then.first
+                 if.then.first:
+                   %add = add i32 %op0, %op1
+                   %user = add i32 %add, 1
+                   br label %if.end.first
+                 if.end.first:
+                   br i1 %cond, label %if.end.second, label %if.then.second
+                 if.then.second:
+                   %sub_op0 = add i32 %op0, 1
+                   %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) {
+        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));
+
+        // 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));
+      });
+}