Index: llvm/trunk/include/llvm/Analysis/ValueTracking.h
===================================================================
--- llvm/trunk/include/llvm/Analysis/ValueTracking.h
+++ llvm/trunk/include/llvm/Analysis/ValueTracking.h
@@ -508,7 +508,8 @@
   /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
   ///
   SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
-                                         Instruction::CastOps *CastOp = nullptr);
+                                         Instruction::CastOps *CastOp = nullptr,
+                                         unsigned Depth = 0);
   inline SelectPatternResult
   matchSelectPattern(const Value *V, const Value *&LHS, const Value *&RHS,
                      Instruction::CastOps *CastOp = nullptr) {
Index: llvm/trunk/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/trunk/lib/Analysis/ValueTracking.cpp
+++ llvm/trunk/lib/Analysis/ValueTracking.cpp
@@ -4165,17 +4165,18 @@
 ///   a < c ? min(a,b) : min(b,c) ==> min(min(a,b),min(b,c))
 static SelectPatternResult matchMinMaxOfMinMax(CmpInst::Predicate Pred,
                                                Value *CmpLHS, Value *CmpRHS,
-                                               Value *TrueVal, Value *FalseVal) {
+                                               Value *TVal, Value *FVal,
+                                               unsigned Depth) {
   // TODO: Allow FP min/max with nnan/nsz.
   assert(CmpInst::isIntPredicate(Pred) && "Expected integer comparison");
 
   Value *A, *B;
-  SelectPatternResult L = matchSelectPattern(TrueVal, A, B);
+  SelectPatternResult L = matchSelectPattern(TVal, A, B, nullptr, Depth + 1);
   if (!SelectPatternResult::isMinOrMax(L.Flavor))
     return {SPF_UNKNOWN, SPNB_NA, false};
 
   Value *C, *D;
-  SelectPatternResult R = matchSelectPattern(FalseVal, C, D);
+  SelectPatternResult R = matchSelectPattern(FVal, C, D, nullptr, Depth + 1);
   if (L.Flavor != R.Flavor)
     return {SPF_UNKNOWN, SPNB_NA, false};
 
@@ -4259,7 +4260,8 @@
 static SelectPatternResult matchMinMax(CmpInst::Predicate Pred,
                                        Value *CmpLHS, Value *CmpRHS,
                                        Value *TrueVal, Value *FalseVal,
-                                       Value *&LHS, Value *&RHS) {
+                                       Value *&LHS, Value *&RHS,
+                                       unsigned Depth) {
   // Assume success. If there's no match, callers should not use these anyway.
   LHS = TrueVal;
   RHS = FalseVal;
@@ -4268,7 +4270,7 @@
   if (SPR.Flavor != SelectPatternFlavor::SPF_UNKNOWN)
     return SPR;
 
-  SPR = matchMinMaxOfMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal);
+  SPR = matchMinMaxOfMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, Depth);
   if (SPR.Flavor != SelectPatternFlavor::SPF_UNKNOWN)
     return SPR;
   
@@ -4332,7 +4334,8 @@
                                               FastMathFlags FMF,
                                               Value *CmpLHS, Value *CmpRHS,
                                               Value *TrueVal, Value *FalseVal,
-                                              Value *&LHS, Value *&RHS) {
+                                              Value *&LHS, Value *&RHS,
+                                              unsigned Depth) {
   LHS = CmpLHS;
   RHS = CmpRHS;
 
@@ -4448,7 +4451,7 @@
   }
 
   if (CmpInst::isIntPredicate(Pred))
-    return matchMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS);
+    return matchMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS, Depth);
 
   // According to (IEEE 754-2008 5.3.1), minNum(0.0, -0.0) and similar
   // may return either -0.0 or 0.0, so fcmp/select pair has stricter
@@ -4569,7 +4572,11 @@
 }
 
 SelectPatternResult llvm::matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
-                                             Instruction::CastOps *CastOp) {
+                                             Instruction::CastOps *CastOp,
+                                             unsigned Depth) {
+  if (Depth >= MaxDepth)
+    return {SPF_UNKNOWN, SPNB_NA, false};
+
   SelectInst *SI = dyn_cast<SelectInst>(V);
   if (!SI) return {SPF_UNKNOWN, SPNB_NA, false};
 
@@ -4598,7 +4605,7 @@
         FMF.setNoSignedZeros();
       return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
                                   cast<CastInst>(TrueVal)->getOperand(0), C,
-                                  LHS, RHS);
+                                  LHS, RHS, Depth);
     }
     if (Value *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp)) {
       // If this is a potential fmin/fmax with a cast to integer, then ignore
@@ -4607,11 +4614,11 @@
         FMF.setNoSignedZeros();
       return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS,
                                   C, cast<CastInst>(FalseVal)->getOperand(0),
-                                  LHS, RHS);
+                                  LHS, RHS, Depth);
     }
   }
   return ::matchSelectPattern(Pred, FMF, CmpLHS, CmpRHS, TrueVal, FalseVal,
-                              LHS, RHS);
+                              LHS, RHS, Depth);
 }
 
 /// Return true if "icmp Pred LHS RHS" is always true.
Index: llvm/trunk/test/Analysis/ValueTracking/select-pattern.ll
===================================================================
--- llvm/trunk/test/Analysis/ValueTracking/select-pattern.ll
+++ llvm/trunk/test/Analysis/ValueTracking/select-pattern.ll
@@ -0,0 +1,46 @@
+; RUN: opt -simplifycfg < %s -S | FileCheck %s
+
+; The dead code would cause a select that had itself
+; as an operand to be analyzed. This would then cause
+; infinite recursion and eventual crash.
+
+define void @PR36045(i1 %t, i32* %b) {
+; CHECK-LABEL: @PR36045(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %t, label %if, label %end
+
+if:
+  br i1 %t, label %unreach, label %pre
+
+unreach:
+  unreachable
+
+pre:
+  %p = phi i32 [ 70, %if ], [ %sel, %for ]
+  br label %for
+
+for:
+  %cmp = icmp sgt i32 %p, 8
+  %add = add i32 %p, 2
+  %sel = select i1 %cmp, i32 %p, i32 %add
+  %cmp21 = icmp ult i32 %sel, 21
+  br i1 %cmp21, label %pre, label %for.end
+
+for.end:
+  br i1 %t, label %unreach2, label %then12
+
+then12:
+  store i32 0, i32* %b
+  br label %unreach2
+
+unreach2:
+  %spec = phi i32 [ %sel, %for.end ], [ 42, %then12 ]
+  unreachable
+
+end:
+  ret void
+}
+