Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp
+++ lib/Transforms/Scalar/LICM.cpp
@@ -800,21 +800,18 @@
   // which ensures that when we rehoist an instruction we rehoist its operands,
   // and also keep track of where in the block we are rehoisting to to make sure
   // that we rehoist instructions before the instructions that use them.
-  Instruction *HoistPoint = nullptr;
+  DenseMap<BasicBlock*, Instruction*> HoistPoints;
   for (Instruction *I : reverse(HoistedInstructions)) {
     if (!llvm::all_of(I->uses(), [&](Use &U) { return DT->dominates(I, U); })) {
       BasicBlock *Dominator =
           DT->getNode(I->getParent())->getIDom()->getBlock();
       LLVM_DEBUG(dbgs() << "LICM rehoisting to " << Dominator->getName() << ": "
                         << *I << "\n");
-      if (!HoistPoint || HoistPoint->getParent() != Dominator) {
-        if (HoistPoint)
-          assert(DT->dominates(Dominator, HoistPoint->getParent()) &&
-                 "New hoist point expected to dominate old hoist point");
-        HoistPoint = Dominator->getTerminator();
-      }
+      Instruction *HoistPoint = HoistPoints.count(Dominator)
+                                    ? HoistPoints[Dominator]
+                                    : Dominator->getTerminator();
       moveInstructionBefore(*I, *HoistPoint, *SafetyInfo);
-      HoistPoint = I;
+      HoistPoints[Dominator] = I;
       Changed = true;
     }
   }
Index: test/Transforms/LICM/hoist-phi.ll
===================================================================
--- test/Transforms/LICM/hoist-phi.ll
+++ test/Transforms/LICM/hoist-phi.ll
@@ -1349,3 +1349,60 @@
 loop.backedge:
   br label %loop
 }
+
+; The order that we hoist instructions from the loop is different to the textual
+; order in the function. Check that we can rehoist this correctly.
+; CHECK-LABEL: @rehoist_wrong_order
+define void @rehoist_wrong_order(i32* %ptr) {
+; CHECK-LABEL: entry
+; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+; CHECK-DISABLED-DAG: %gep3 = getelementptr inbounds i32, i32* %ptr, i64 3
+; CHECK-DAG: %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+; CHECK-ENABLED: br i1 undef, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
+entry:
+  br label %loop
+
+; CHECK-ENABLED: [[IF1_LICM]]:
+; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM:.*]]
+
+; CHECK-ENABLED: [[ELSE1_LICM]]:
+; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
+
+; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
+; CHECK-ENABLED: %gep3 = getelementptr inbounds i32, i32* %ptr, i64 3
+; CHECK-ENABLED: br i1 undef, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
+
+; CHECK-ENABLED: [[IF3_LICM]]:
+; CHECK-ENABLED: br label %[[END_LICM]]
+
+; CHECK-ENABLED: [[END_LICM]]:
+; CHECK: br label %loop
+
+loop:
+  br i1 undef, label %if1, label %else1
+
+if1:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+  store i32 0, i32* %gep1, align 4
+  br label %loop.backedge
+
+else1:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+  store i32 0, i32* %gep2, align 4
+  br i1 undef, label %if2, label %loop.backedge
+
+if2:
+  br i1 undef, label %if3, label %end
+
+if3:
+  %gep3 = getelementptr inbounds i32, i32* %ptr, i64 3
+  store i32 0, i32* %gep3, align 4
+  br label %end
+
+end:
+  br label %loop.backedge
+
+loop.backedge:
+  br label %loop
+
+}