Index: lib/CodeGen/MachineLICM.cpp
===================================================================
--- lib/CodeGen/MachineLICM.cpp
+++ lib/CodeGen/MachineLICM.cpp
@@ -1077,17 +1077,17 @@
   bool CheapInstr = IsCheapInstruction(MI);
   bool CreatesCopy = HasLoopPHIUse(&MI);
 
+  // Rematerializable instructions should always be hoisted since the register
+  // allocator can just pull them down again when needed.
+  if (TII->isTriviallyReMaterializable(MI, AA))
+    return true;
+
   // Don't hoist a cheap instruction if it would create a copy in the loop.
   if (CheapInstr && CreatesCopy) {
     DEBUG(dbgs() << "Won't hoist cheap instr with loop PHI use: " << MI);
     return false;
   }
 
-  // Rematerializable instructions should always be hoisted since the register
-  // allocator can just pull them down again when needed.
-  if (TII->isTriviallyReMaterializable(MI, AA))
-    return true;
-
   // FIXME: If there are long latency loop-invariant instructions inside the
   // loop at this point, why didn't the optimizer's LICM hoist them?
   for (unsigned i = 0, e = MI.getDesc().getNumOperands(); i != e; ++i) {
Index: test/CodeGen/X86/licm-nested.ll
===================================================================
--- test/CodeGen/X86/licm-nested.ll
+++ test/CodeGen/X86/licm-nested.ll
@@ -1,5 +1,5 @@
 ; REQUIRES: asserts
-; RUN: llc -mtriple=x86_64-apple-darwin -march=x86-64 < %s -o /dev/null -stats -info-output-file - | grep "hoisted out of loops" | grep 4
+; RUN: llc -mtriple=x86_64-apple-darwin -march=x86-64 < %s -o /dev/null -stats -info-output-file - | grep "hoisted out of loops" | grep 6
 
 ; MachineLICM should be able to hoist the symbolic addresses out of
 ; the inner loops.
Index: test/CodeGen/X86/loop-hoist.c
===================================================================
--- test/CodeGen/X86/loop-hoist.c
+++ test/CodeGen/X86/loop-hoist.c
@@ -0,0 +1,17 @@
+// RUN: clang -O3 -S -o - -march=btver2 %s | FileCheck %s
+
+int search(int needle, const int *haystack, int count) {
+  for (int i = 0; i < count; ++i)
+    if (needle == haystack[i])
+      return 1; // true;
+  return 0; // false;
+}
+
+// CHECK: %for.body.preheader
+// CHECK: movl $1, %eax
+// CHECK: %for.body
+// CHECK: cmpl %edi, (%rsi,%rdx,4)
+// CHECK: je [[LABEL:.*]]
+// CHECK: [[LABEL]]: {{.*}} %cleanup
+// CHECK-NEXT: retq
+