[ValueTracking] add recursion depth param to matchSelectPattern

[spatel]

Summary

We're getting bug reports:
https://bugs.llvm.org/show_bug.cgi?id=35807
https://bugs.llvm.org/show_bug.cgi?id=35840
https://bugs.llvm.org/show_bug.cgi?id=36045
...where we blow up the stack in value tracking because other passes are sending in selects that have an operand that is itself the select.

We don't currently have a reliable way to avoid analyzing dead code that may take non-standard forms, so bail out when things go too far.

[efriedma]

As I understand it, we want to uncover these bugs in passes that use value tracking because it signals a potential efficiency improvement for them when dealing with dead code or other corner cases.

We don't actually have a solution to reliably avoid analyzing dead code... see the discussion on https://reviews.llvm.org/D34135.

[spatel]

In D42442#985767, @efriedma wrote:

As I understand it, we want to uncover these bugs in passes that use value tracking because it signals a potential efficiency improvement for them when dealing with dead code or other corner cases.

We don't actually have a solution to reliably avoid analyzing dead code... see the discussion on https://reviews.llvm.org/D34135.

Ah...so should we just bail out here in value tracking then?

[efriedma]

Well, checking explicitly for a select which directly refers to itself doesn't really solve anything; you can have exactly the same issue with indirect references.

Let's just add a recursion limit for now, I think.

[efriedma]

I think this looks okay, but let's wait to see if @davide has any input.

[davide]

lg

include/llvm/Analysis/ValueTracking.h

class Value;
   /// For example:
   ///   %1 = icmp slt i32 %a, i32 4
   ///   %2 = sext i32 %a to i64
   ///   %3 = select i1 %1, i64 %2, i64 4
   ///
   /// -> 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) {
     Value *L = const_cast<Value*>(LHS);
     Value *R = const_cast<Value*>(RHS);
     auto Result = matchSelectPattern(const_cast<Value*>(V), L, R);
     LHS = L;
     RHS = R;

lib/Analysis/ValueTracking.cpp

static SelectPatternResult matchClamp(CmpInst::Predicate Pred,
   }
   return {SPF_UNKNOWN, SPNB_NA, false};
 }
 
 /// Recognize variations of:
 ///   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 *TrueVal, Value *FalseVal,
+                                               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(TrueVal, A, B, nullptr, ++Depth);
   if (!SelectPatternResult::isMinOrMax(L.Flavor))
     return {SPF_UNKNOWN, SPNB_NA, false};
 
   Value *C, *D;
-  SelectPatternResult R = matchSelectPattern(FalseVal, C, D);
+  SelectPatternResult R = matchSelectPattern(FalseVal, C, D, nullptr, ++Depth);
   if (L.Flavor != R.Flavor)
     return {SPF_UNKNOWN, SPNB_NA, false};
 
   // We have something like: x Pred y ? min(a, b) : min(c, d).
   // Try to match the compare to the min/max operations of the select operands.
   // First, make sure we have the right compare predicate.
   switch (L.Flavor) {
   case SPF_SMIN:
static SelectPatternResult matchMinMaxOfMinMax(CmpInst::Predicate Pred,
 
   return {SPF_UNKNOWN, SPNB_NA, false};
 }
 
 /// Match non-obvious integer minimum and maximum sequences.
 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;
 
   SelectPatternResult SPR = matchClamp(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal);
   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;
   
   if (Pred != CmpInst::ICMP_SGT && Pred != CmpInst::ICMP_SLT)
     return {SPF_UNKNOWN, SPNB_NA, false};
 
   // Z = X -nsw Y
   // (X >s Y) ? 0 : Z ==> (Z >s 0) ? 0 : Z ==> SMIN(Z, 0)
static SelectPatternResult matchMinMax(CmpInst::Predicate Pred,
 
   return {SPF_UNKNOWN, SPNB_NA, false};
 }
 
 static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred,
                                               FastMathFlags FMF,
                                               Value *CmpLHS, Value *CmpRHS,
                                               Value *TrueVal, Value *FalseVal,
-                                              Value *&LHS, Value *&RHS) {
+                                              Value *&LHS, Value *&RHS,
+                                              unsigned Depth) {
   LHS = CmpLHS;
   RHS = CmpRHS;
 
   // Signed zero may return inconsistent results between implementations.
   //  (0.0 <= -0.0) ? 0.0 : -0.0 // Returns 0.0
   //  minNum(0.0, -0.0)          // May return -0.0 or 0.0 (IEEE 754-2008 5.3.1)
   // Therefore, we behave conservatively and only proceed if at least one of the
   // operands is known to not be zero or if we don't care about signed zero.
if ((CmpLHS == TrueVal && match(FalseVal, m_Neg(m_Specific(CmpLHS)))) ||
       if (Pred == ICmpInst::ICMP_SLT &&
           (C1->isNullValue() || C1->isOneValue())) {
         return {(CmpLHS == FalseVal) ? SPF_ABS : SPF_NABS, SPNB_NA, false};
       }
     }
   }
 
   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
   // semantics than minNum. Be conservative in such case.
   if (NaNBehavior != SPNB_RETURNS_ANY ||
       (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
        !isKnownNonZero(CmpRHS)))
     return {SPF_UNKNOWN, SPNB_NA, false};
Constant *CastedBack =
       ConstantExpr::getCast(*CastOp, CastedTo, C->getType(), true);
   if (CastedBack != C)
     return nullptr;
 
   return CastedTo;
 }
 
 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};
 
   CmpInst *CmpI = dyn_cast<CmpInst>(SI->getCondition());
   if (!CmpI) return {SPF_UNKNOWN, SPNB_NA, false};
 
   CmpInst::Predicate Pred = CmpI->getPredicate();
   Value *CmpLHS = CmpI->getOperand(0);
SelectPatternResult llvm::matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
   if (CastOp && CmpLHS->getType() != TrueVal->getType()) {
     if (Value *C = lookThroughCast(CmpI, TrueVal, FalseVal, CastOp)) {
       // If this is a potential fmin/fmax with a cast to integer, then ignore
       // -0.0 because there is no corresponding integer value.
       if (*CastOp == Instruction::FPToSI || *CastOp == Instruction::FPToUI)
         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
       // -0.0 because there is no corresponding integer value.
       if (*CastOp == Instruction::FPToSI || *CastOp == Instruction::FPToUI)
         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.
 static bool isTruePredicate(CmpInst::Predicate Pred, const Value *LHS,
                             const Value *RHS, const DataLayout &DL,
                             unsigned Depth) {
   assert(!LHS->getType()->isVectorTy() && "TODO: extend to handle vectors!");
   if (ICmpInst::isTrueWhenEqual(Pred) && LHS == RHS)

test/Analysis/ValueTracking/select-pattern.ll

+; 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
+}
+