Index: lib/Transforms/Scalar/LICM.cpp
===================================================================
--- lib/Transforms/Scalar/LICM.cpp
+++ lib/Transforms/Scalar/LICM.cpp
@@ -449,6 +449,11 @@
     if (inSubLoop(BB, CurLoop, LI))
       continue;
 
+    // Keep track of whether the prefix of instructions visited so far are such
+    // that the next instruction visited is guaranteed to execute if the loop
+    // is entered.  
+    bool IsMustExecute = CurLoop->getHeader() == BB;
+
     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       Instruction &I = *II++;
       // Try constant folding this instruction.  If all the operands are
@@ -496,10 +501,14 @@
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo, ORE) &&
-          isSafeToExecuteUnconditionally(
-              I, DT, CurLoop, SafetyInfo, ORE,
-              CurLoop->getLoopPreheader()->getTerminator()))
+          (IsMustExecute ||
+           isSafeToExecuteUnconditionally(
+               I, DT, CurLoop, SafetyInfo, ORE,
+               CurLoop->getLoopPreheader()->getTerminator())))
         Changed |= hoist(I, DT, CurLoop, SafetyInfo, ORE);
+
+      if (IsMustExecute)
+        IsMustExecute = isGuaranteedToTransferExecutionToSuccessor(&I);
     }
   }
 
Index: test/Transforms/LICM/preheader-safe.ll
===================================================================
--- test/Transforms/LICM/preheader-safe.ll
+++ test/Transforms/LICM/preheader-safe.ll
@@ -55,7 +55,26 @@
   br label %loop
 }
 
+; Similiar to the above, but the hoistable instruction (%y in this case)
+; happens not to be the first instruction in the block.
+define void @throw_header_after_nonfirst(i64* %xp, i64* %yp, i1* %cond) {
+; CHECK-LABEL: throw_header_after_nonfirst
+; CHECK: %y = load i64, i64* %yp
+; CHECK-LABEL: loop
+; CHECK: %div = udiv i64 %x, %y
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
 
+loop:                                         ; preds = %entry, %for.inc
+  %iv = phi i64 [0, %entry], [%div, %loop]
+  %gep = getelementptr i64, i64* %xp, i64 %iv
+  %x = load i64, i64* %gep
+  %y = load i64, i64* %yp
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div) readonly
+  br label %loop
+}
 
 ; Negative test
 define void @throw_header_before(i64 %x, i64 %y, i1* %cond) {