Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -4556,6 +4556,10 @@
 Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS,
                                         const DataLayout &DL, bool LHSIsTrue,
                                         unsigned Depth) {
+  // Bail out when we hit the limit.
+  if (Depth == MaxDepth)
+    return None;
+
   // A mismatch occurs when we compare a scalar cmp to a vector cmp, for
   // example.
   if (LHS->getType() != RHS->getType())
Index: test/Transforms/SimplifyCFG/pr34131.ll
===================================================================
--- /dev/null
+++ test/Transforms/SimplifyCFG/pr34131.ll
@@ -0,0 +1,116 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -simplifycfg %s -S | FileCheck %s
+
+define void @patatino() {
+; CHECK-LABEL: @patatino(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 undef, label [[BB4:%.*]], label [[BB9_CRITEDGE:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[DOTPR:%.*]] = phi i1 [ undef, [[BB4]] ], [ true, [[BB1]] ]
+; CHECK-NEXT:    br i1 [[DOTPR]], label [[BB4]], label [[BB6:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP:%.*]] = or i64 undef, 1
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp ult i64 [[TMP]], 0
+; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 undef, [[TMP8]]
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp ult i64 0, 0
+; CHECK-NEXT:    [[OR_COND2:%.*]] = and i1 [[OR_COND]], [[TMP13]]
+; CHECK-NEXT:    [[TMP15:%.*]] = icmp ult i64 undef, 0
+; CHECK-NEXT:    [[OR_COND3:%.*]] = and i1 [[OR_COND2]], [[TMP15]]
+; CHECK-NEXT:    [[TMP19:%.*]] = or i64 undef, 5
+; CHECK-NEXT:    [[TMP20:%.*]] = icmp ult i64 [[TMP19]], 0
+; CHECK-NEXT:    [[OR_COND4:%.*]] = and i1 [[OR_COND3]], [[TMP20]]
+; CHECK-NEXT:    [[TMP22:%.*]] = or i64 undef, 6
+; CHECK-NEXT:    [[TMP23:%.*]] = icmp ult i64 [[TMP22]], 0
+; CHECK-NEXT:    [[OR_COND5:%.*]] = and i1 [[OR_COND4]], [[TMP23]]
+; CHECK-NEXT:    [[TMP25:%.*]] = or i64 undef, 7
+; CHECK-NEXT:    [[TMP26:%.*]] = icmp ult i64 [[TMP25]], 0
+; CHECK-NEXT:    [[OR_COND6:%.*]] = and i1 [[OR_COND5]], [[TMP26]]
+; CHECK-NEXT:    [[TMP28:%.*]] = or i64 undef, 8
+; CHECK-NEXT:    [[TMP29:%.*]] = icmp ult i64 [[TMP28]], 0
+; CHECK-NEXT:    [[OR_COND7:%.*]] = and i1 [[OR_COND6]], [[TMP29]]
+; CHECK-NEXT:    [[OR_COND7_NOT:%.*]] = xor i1 [[OR_COND7]], true
+; CHECK-NEXT:    [[DOTNOT:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    [[BRMERGE:%.*]] = or i1 [[OR_COND7_NOT]], [[DOTNOT]]
+; CHECK-NEXT:    [[DOTNOT8:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    [[BRMERGE9:%.*]] = or i1 [[BRMERGE]], [[DOTNOT8]]
+; CHECK-NEXT:    [[DOTNOT10:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    [[BRMERGE11:%.*]] = or i1 [[BRMERGE9]], [[DOTNOT10]]
+; CHECK-NEXT:    [[DOTNOT12:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    [[BRMERGE13:%.*]] = or i1 [[BRMERGE11]], [[DOTNOT12]]
+; CHECK-NEXT:    [[DOTNOT14:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    [[BRMERGE15:%.*]] = or i1 [[BRMERGE13]], [[DOTNOT14]]
+; CHECK-NEXT:    [[DOTNOT16:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    [[BRMERGE17:%.*]] = or i1 [[BRMERGE15]], [[DOTNOT16]]
+; CHECK-NEXT:    [[DOTNOT18:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    [[BRMERGE19:%.*]] = or i1 [[BRMERGE17]], [[DOTNOT18]]
+; CHECK-NEXT:    br i1 [[BRMERGE19]], label [[BB11:%.*]], label [[BB1]]
+; CHECK:       bb9.critedge:
+; CHECK-NEXT:    br label [[BB11]]
+; CHECK:       bb11:
+; CHECK-NEXT:    ret void
+;
+  br label %bb1
+bb1:                                              ; preds = %bb36, %0
+  br label %bb2
+bb2:                                              ; preds = %bb3, %bb1
+  br i1 undef, label %bb4, label %bb3
+bb3:                                              ; preds = %bb4, %bb2
+  br i1 undef, label %bb2, label %bb5
+bb4:                                              ; preds = %bb2
+  switch i32 undef, label %bb3 [
+  ]
+bb5:                                              ; preds = %bb3
+  br label %bb6
+bb6:                                              ; preds = %bb5
+  br i1 undef, label %bb7, label %bb9
+bb7:                                              ; preds = %bb6
+  %tmp = or i64 undef, 1
+  %tmp8 = icmp ult i64 %tmp, 0
+  br i1 %tmp8, label %bb12, label %bb9
+bb9:                                              ; preds = %bb35, %bb34, %bb33, %bb32, %bb31, %bb30, %bb27, %bb24, %bb21, %bb18, %bb16, %bb14, %bb12, %bb7, %bb6
+  br label %bb11
+bb10:                                             ; preds = %bb36
+  br label %bb11
+bb11:                                             ; preds = %bb10, %bb9
+  ret void
+bb12:                                             ; preds = %bb7
+  %tmp13 = icmp ult i64 0, 0
+  br i1 %tmp13, label %bb14, label %bb9
+bb14:                                             ; preds = %bb12
+  %tmp15 = icmp ult i64 undef, 0
+  br i1 %tmp15, label %bb16, label %bb9
+bb16:                                             ; preds = %bb14
+  %tmp17 = icmp ult i64 undef, 0
+  br i1 %tmp17, label %bb18, label %bb9
+bb18:                                             ; preds = %bb16
+  %tmp19 = or i64 undef, 5
+  %tmp20 = icmp ult i64 %tmp19, 0
+  br i1 %tmp20, label %bb21, label %bb9
+bb21:                                             ; preds = %bb18
+  %tmp22 = or i64 undef, 6
+  %tmp23 = icmp ult i64 %tmp22, 0
+  br i1 %tmp23, label %bb24, label %bb9
+bb24:                                             ; preds = %bb21
+  %tmp25 = or i64 undef, 7
+  %tmp26 = icmp ult i64 %tmp25, 0
+  br i1 %tmp26, label %bb27, label %bb9
+bb27:                                             ; preds = %bb24
+  %tmp28 = or i64 undef, 8
+  %tmp29 = icmp ult i64 %tmp28, 0
+  br i1 %tmp29, label %bb30, label %bb9
+bb30:                                             ; preds = %bb27
+  br i1 undef, label %bb31, label %bb9
+bb31:                                             ; preds = %bb30
+  br i1 undef, label %bb32, label %bb9
+bb32:                                             ; preds = %bb31
+  br i1 undef, label %bb33, label %bb9
+bb33:                                             ; preds = %bb32
+  br i1 undef, label %bb34, label %bb9
+bb34:                                             ; preds = %bb33
+  br i1 undef, label %bb35, label %bb9
+bb35:                                             ; preds = %bb34
+  br i1 undef, label %bb36, label %bb9
+bb36:                                             ; preds = %bb35
+  br i1 undef, label %bb1, label %bb10
+}