Index: llvm/lib/CodeGen/MachineCSE.cpp
===================================================================
--- llvm/lib/CodeGen/MachineCSE.cpp
+++ llvm/lib/CodeGen/MachineCSE.cpp
@@ -344,15 +344,17 @@
                                   bool &NonLocal) const {
   // For now conservatively returns false if the common subexpression is
   // not in the same basic block as the given instruction. The only exception
-  // is if the common subexpression is in the sole predecessor block.
-  const MachineBasicBlock *MBB = MI->getParent();
+  // is if the common subexpression is in chain of sole predecessor blocks.
   const MachineBasicBlock *CSMBB = CSMI->getParent();
-
-  bool CrossMBB = false;
-  if (CSMBB != MBB) {
-    if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB)
+  // BB2Visit contains [MBB, CSMBB). Might be empty if MBB == CSMBB.
+  SmallVector<MachineBasicBlock *, 4> BB2Visit;
+  for (auto *MBB = MI->getParent(); MBB != CSMBB; MBB = *MBB->pred_begin()) {
+    if (MBB->pred_size() != 1)
       return false;
+    BB2Visit.push_back(MBB);
+  }
 
+  if (!BB2Visit.empty()) {
     for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
       if (MRI->isAllocatable(PhysDefs[i].second) ||
           MRI->isReserved(PhysDefs[i].second))
@@ -360,7 +362,6 @@
         //allocatable or reserved.
         return false;
     }
-    CrossMBB = true;
   }
   MachineBasicBlock::const_iterator I = CSMI; I = std::next(I);
   MachineBasicBlock::const_iterator E = MI;
@@ -372,12 +373,11 @@
       ++I;
 
     if (I == EE) {
-      assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
-      (void)CrossMBB;
-      CrossMBB = false;
+      assert(!BB2Visit.empty() && "Missed CSMI?");
+      auto *BB = BB2Visit.pop_back_val();
       NonLocal = true;
-      I = MBB->begin();
-      EE = MBB->end();
+      I = BB->begin();
+      EE = BB->end();
       continue;
     }
 
Index: llvm/test/CodeGen/Thumb2/thumb2-cbnz.ll
===================================================================
--- llvm/test/CodeGen/Thumb2/thumb2-cbnz.ll
+++ llvm/test/CodeGen/Thumb2/thumb2-cbnz.ll
@@ -5,15 +5,15 @@
 
 define void @t(i32 %c, double %b) {
 entry:
-; CHECK:      cmp	r0, #0
-  %cmp1 = icmp ne i32 %c, 0
+; CHECK:      cmp	r0, #2
+  %cmp1 = icmp ne i32 %c, 2
   br i1 %cmp1, label %bb3, label %bb1
 
 bb1:                                              ; preds = %entry
   unreachable
 
 bb3:                                              ; preds = %entry
-  %cmp2 = icmp ne i32 %c, 0
+  %cmp2 = icmp ne i32 %c, 1
   br i1 %cmp2, label %bb7, label %bb5
 
 bb5:                                              ; preds = %bb3
Index: llvm/test/CodeGen/X86/2007-11-30-LoadFolding-Bug.ll
===================================================================
--- llvm/test/CodeGen/X86/2007-11-30-LoadFolding-Bug.ll
+++ llvm/test/CodeGen/X86/2007-11-30-LoadFolding-Bug.ll
@@ -13,25 +13,24 @@
 ; CHECK-NEXT:    pushl %edi
 ; CHECK-NEXT:    pushl %esi
 ; CHECK-NEXT:    movl %edx, %esi
-; CHECK-NEXT:    movb $1, %cl
+; CHECK-NEXT:    movb $1, %al
 ; CHECK-NEXT:    movl $1, %ebx
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_1: # %bb.i5
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    movl %ecx, %eax
+; CHECK-NEXT:    movl %eax, %ecx
 ; CHECK-NEXT:    addl %ebx, %ebx
-; CHECK-NEXT:    xorl %ecx, %ecx
-; CHECK-NEXT:    testb $1, %al
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    testb $1, %cl
 ; CHECK-NEXT:    jne .LBB0_1
 ; CHECK-NEXT:  # %bb.2: # %mp_unexp_mp2d.exit.i
 ; CHECK-NEXT:    je .LBB0_10
 ; CHECK-NEXT:  # %bb.3: # %cond_next.i
-; CHECK-NEXT:    testb $1, %al
 ; CHECK-NEXT:    jne .LBB0_10
 ; CHECK-NEXT:  # %bb.4: # %cond_next36.i
 ; CHECK-NEXT:    movl $0, 0
-; CHECK-NEXT:    movzbl %al, %ebp
+; CHECK-NEXT:    movzbl %cl, %ebp
 ; CHECK-NEXT:    andl $1, %ebp
 ; CHECK-NEXT:    xorpd %xmm0, %xmm0
 ; CHECK-NEXT:    xorl %eax, %eax
Index: llvm/test/CodeGen/X86/2008-04-17-CoalescerBug.ll
===================================================================
--- llvm/test/CodeGen/X86/2008-04-17-CoalescerBug.ll
+++ llvm/test/CodeGen/X86/2008-04-17-CoalescerBug.ll
@@ -37,9 +37,9 @@
 ; CHECK-NEXT:  ## %bb.1: ## %bb116.i
 ; CHECK-NEXT:    je LBB0_25
 ; CHECK-NEXT:  ## %bb.2: ## %bb52.i.i
-; CHECK-NEXT:    testb $1, %bl
 ; CHECK-NEXT:    je LBB0_25
 ; CHECK-NEXT:  ## %bb.3: ## %bb142.i
+; CHECK-NEXT:    testb $1, %bl
 ; CHECK-NEXT:    je LBB0_25
 ; CHECK-NEXT:  ## %bb.4:
 ; CHECK-NEXT:    movl L_.str89$non_lazy_ptr, %edi
Index: llvm/test/CodeGen/X86/cse-two-preds.mir
===================================================================
--- llvm/test/CodeGen/X86/cse-two-preds.mir
+++ llvm/test/CodeGen/X86/cse-two-preds.mir
@@ -113,8 +113,8 @@
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.2.NGT:
   ; CHECK-NEXT:   successors: %bb.8(0x50000000), %bb.3(0x30000000)
+  ; CHECK-NEXT:   liveins: $eflags
   ; CHECK-NEXT: {{  $}}
-  ; CHECK-NEXT:   nofpexcept VUCOMISSrr [[COPY1]], [[COPY]], implicit-def $eflags, implicit $mxcsr
   ; CHECK-NEXT:   JCC_1 %bb.8, 5, implicit $eflags
   ; CHECK-NEXT:   JMP_1 %bb.3
   ; CHECK-NEXT: {{  $}}
Index: llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll
===================================================================
--- llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll
+++ llvm/test/CodeGen/X86/ins_subreg_coalesce-3.ll
@@ -22,40 +22,44 @@
 ; CHECK-LABEL: FontChange:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    je .LBB0_9
+; CHECK-NEXT:    je .LBB0_11
+; CHECK-NEXT:  # %bb.1: # %bb298
+; CHECK-NEXT:    je .LBB0_3
+; CHECK-NEXT:  # %bb.2: # %bb304
+; CHECK-NEXT:    je .LBB0_4
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_1: # %bb366
+; CHECK-NEXT:  .LBB0_3: # %bb366
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    jne .LBB0_1
-; CHECK-NEXT:  # %bb.2: # %bb428
+; CHECK-NEXT:    jne .LBB0_3
+; CHECK-NEXT:  .LBB0_4: # %bb428
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    je .LBB0_9
+; CHECK-NEXT:    je .LBB0_11
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_3: # %bb650
+; CHECK-NEXT:  .LBB0_5: # %bb650
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpb $0, 0
-; CHECK-NEXT:    je .LBB0_3
-; CHECK-NEXT:  # %bb.4: # %bb662
+; CHECK-NEXT:    je .LBB0_5
+; CHECK-NEXT:  # %bb.6: # %bb662
 ; CHECK-NEXT:    movl 0, %eax
 ; CHECK-NEXT:    movl %eax, %ecx
 ; CHECK-NEXT:    andl $57344, %ecx # imm = 0xE000
 ; CHECK-NEXT:    cmpl $8192, %ecx # imm = 0x2000
-; CHECK-NEXT:    jne .LBB0_9
-; CHECK-NEXT:  # %bb.5: # %bb4884
+; CHECK-NEXT:    jne .LBB0_11
+; CHECK-NEXT:  # %bb.7: # %bb4884
 ; CHECK-NEXT:    andl $7168, %eax # imm = 0x1C00
 ; CHECK-NEXT:    cmpl $1024, %eax # imm = 0x400
-; CHECK-NEXT:    jne .LBB0_9
-; CHECK-NEXT:  # %bb.6: # %bb4932
+; CHECK-NEXT:    jne .LBB0_11
+; CHECK-NEXT:  # %bb.8: # %bb4932
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    jne .LBB0_9
-; CHECK-NEXT:  # %bb.7: # %bb4940
+; CHECK-NEXT:    jne .LBB0_11
+; CHECK-NEXT:  # %bb.9: # %bb4940
 ; CHECK-NEXT:    movl 0, %eax
 ; CHECK-NEXT:    cmpl $160, %eax
-; CHECK-NEXT:    je .LBB0_9
-; CHECK-NEXT:  # %bb.8: # %bb4940
+; CHECK-NEXT:    je .LBB0_11
+; CHECK-NEXT:  # %bb.10: # %bb4940
 ; CHECK-NEXT:    cmpl $159, %eax
-; CHECK-NEXT:  .LBB0_9: # %bb4897
+; CHECK-NEXT:  .LBB0_11: # %bb4897
 ; CHECK-NEXT:    retq
 entry:
 	br i1 %foo, label %bb298, label %bb49