[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

lib/Analysis/ValueTracking.cpp

SelectPatternResult llvm::matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
   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);
   Value *CmpRHS = CmpI->getOperand(1);
   Value *TrueVal = SI->getTrueValue();
   Value *FalseVal = SI->getFalseValue();
+  assert(SI != TrueVal && SI != FalseVal &&
+         "Trying to match select pattern for select that refers to itself");
+
   FastMathFlags FMF;
   if (isa<FPMathOperator>(CmpI))
     FMF = CmpI->getFastMathFlags();
 
   // Bail out early.
   if (CmpI->isEquality())
     return {SPF_UNKNOWN, SPNB_NA, false};