[SelectionDAG] Limit max recursion in `isKnownNeverZero` and `isKnownToBeAPowerOfTwo`

[goldstein.w.n]

Summary

Both of these functions recursively call themselves so it makes sense
to limit that upper bound.

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

4027

This is missing a depth too?

[foad]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

5013–5015

Need to pass Depth into the recursive calls, otherwise what's the point?

[goldstein.w.n]

Use Depth in all recursive calls

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3979

In the existing SelectionDAG recursion methods, we don't increment Depth here but in the recursive calls to make it more obvious (and avoids any messy Depth - 1 hacks)

[goldstein.w.n]

Use common style

[RKSimon]

LGTM - cheers

[goldstein.w.n]

Rebase

llvm/include/llvm/CodeGen/SelectionDAG.h

public:
   };
 
   /// Determine if the result of the addition of 2 node can overflow.
   OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const;
 
   /// Test if the given value is known to have exactly one bit set. This differs
   /// from computeKnownBits in that it doesn't necessarily determine which bit
   /// is set.
-  bool isKnownToBeAPowerOfTwo(SDValue Val) const;
+  bool isKnownToBeAPowerOfTwo(SDValue Val, unsigned Depth = 0) const;
 
   /// Return the number of times the sign bit of the register is replicated into
   /// the other bits. We know that at least 1 bit is always equal to the sign
   /// bit (itself), but other cases can give us information. For example,
   /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
   /// to each other, so we return 3. Targets can implement the
   /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow
   /// target nodes to be understood.
bool isKnownNeverSNaN(SDValue Op, unsigned Depth = 0) const {
     return isKnownNeverNaN(Op, true, Depth);
   }
 
   /// Test whether the given floating point SDValue is known to never be
   /// positive or negative zero.
   bool isKnownNeverZeroFloat(SDValue Op) const;
 
   /// Test whether the given SDValue is known to contain non-zero value(s).
-  bool isKnownNeverZero(SDValue Op) const;
+  bool isKnownNeverZero(SDValue Op, unsigned Depth = 0) const;
 
   /// Test whether two SDValues are known to compare equal. This
   /// is true if they are the same value, or if one is negative zero and the
   /// other positive zero.
   bool isEqualTo(SDValue A, SDValue B) const;
 
   /// Return true if A and B have no common bits set. As an example, this can
   /// allow an 'add' to be transformed into an 'or'.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (N1.getOpcode() == ISD::UMUL_LOHI && N1.getResNo() == 1) {
 
     if ((N0Known.getMaxValue() & 0x01) == N0Known.getMaxValue())
       return OFK_Never;
   }
 
   return OFK_Sometime;
 }
 
-bool SelectionDAG::isKnownToBeAPowerOfTwo(SDValue Val) const {
+bool SelectionDAG::isKnownToBeAPowerOfTwo(SDValue Val, unsigned Depth) const {
+  if (Depth++ >= MaxRecursionDepth)
+    return false; // Limit search depth.
+
   EVT OpVT = Val.getValueType();
   unsigned BitWidth = OpVT.getScalarSizeInBits();
 
   // Is the constant a known power of 2?
   if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(Val))
     return Const->getAPIntValue().zextOrTrunc(BitWidth).isPowerOf2();
 
   // A left-shift of a constant one will have exactly one bit set because
bool SelectionDAG::isKnownToBeAPowerOfTwo(SDValue Val, unsigned Depth) const {
   if (Val.getOpcode() == ISD::SPLAT_VECTOR)
     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Val->getOperand(0)))
       if (C->getAPIntValue().zextOrTrunc(BitWidth).isPowerOf2())
         return true;
 
   // vscale(power-of-two) is a power-of-two for some targets
   if (Val.getOpcode() == ISD::VSCALE &&
       getTargetLoweringInfo().isVScaleKnownToBeAPowerOfTwo() &&
-      isKnownToBeAPowerOfTwo(Val.getOperand(0)))
+      isKnownToBeAPowerOfTwo(Val.getOperand(0), Depth))
     return true;
 
   // More could be done here, though the above checks are enough
   // to handle some common cases.
 
   // Fall back to computeKnownBits to catch other known cases.
-  KnownBits Known = computeKnownBits(Val);
+  KnownBits Known = computeKnownBits(Val, Depth - 1);
   return (Known.countMaxPopulation() == 1) && (Known.countMinPopulation() == 1);
 }
 
 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const {
   EVT VT = Op.getValueType();
 
   // Since the number of lanes in a scalable vector is unknown at compile time,
   // we track one bit which is implicitly broadcast to all lanes.  This means
for (const SDValue &OpVal : Op->op_values()) {
         if (C->isZero())
           return false;
     }
     return true;
   }
   return false;
 }
 
-bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
+bool SelectionDAG::isKnownNeverZero(SDValue Op, unsigned Depth) const {
+  if (Depth++ >= MaxRecursionDepth)
+    return false; // Limit search depth.
+
   assert(!Op.getValueType().isFloatingPoint() &&
          "Floating point types unsupported - use isKnownNeverZeroFloat");
 
   // If the value is a constant, we can obviously see if it is a zero or not.
   if (ISD::matchUnaryPredicate(Op,
                                [](ConstantSDNode *C) { return !C->isZero(); }))
     return true;
 
   // TODO: Recognize more cases here.
   switch (Op.getOpcode()) {
   default: break;
   case ISD::OR:
-    if (isKnownNeverZero(Op.getOperand(1)) ||
-        isKnownNeverZero(Op.getOperand(0)))
+    if (isKnownNeverZero(Op.getOperand(1), Depth) ||
+        isKnownNeverZero(Op.getOperand(0), Depth))
       return true;
     break;
   }
 
   return false;
 }
 
 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {