[ValueTracking] Relaxed requirement of UseInstrInfo in power of 2 recurrece check

[huangjd]

Summary

add isExact check for recurrence using division operator

llvm/lib/Analysis/ValueTracking.cpp

static bool isPowerOfTwoRecurrence(const PHINode *PN, bool OrZero,
   // increment expression, otherwise its value can be arbitrary.
   if (BO->getOpcode() != Instruction::Mul && BO->getOperand(1) != Step)
     return false;
 
   Q.CxtI = BO->getParent()->getTerminator();
   switch (BO->getOpcode()) {
   case Instruction::Mul:
     // Power of two is closed under multiplication.
-    return (OrZero || BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
+    return (OrZero || Q.IIQ.hasNoUnsignedWrap(BO) ||
+            Q.IIQ.hasNoSignedWrap(BO)) &&
            isKnownToBeAPowerOfTwo(Step, OrZero, Depth, Q);
   case Instruction::SDiv:
     // Start value must not be signmask for signed division, so simply being a
     // power of two is not sufficient, and it has to be a constant.
     if (!match(Start, m_Power2()) || match(Start, m_SignMask()))
       return false;
     LLVM_FALLTHROUGH;
   case Instruction::UDiv:
     // Divisor must be a power of two.
     // If OrZero is false, cannot guarantee induction variable is non-zero after
-    // division, same for Shr.
-    return OrZero && isKnownToBeAPowerOfTwo(Step, false, Depth, Q);
+    // division, same for Shr, unless it is exact division.
+    return (OrZero || Q.IIQ.isExact(BO)) &&
+           isKnownToBeAPowerOfTwo(Step, false, Depth, Q);
   case Instruction::Shl:
-    return OrZero || BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap();
+    return OrZero || Q.IIQ.hasNoUnsignedWrap(BO) || Q.IIQ.hasNoSignedWrap(BO);
   case Instruction::AShr:
     if (!match(Start, m_Power2()) || match(Start, m_SignMask()))
       return false;
     LLVM_FALLTHROUGH;
   case Instruction::LShr:
-    return OrZero;
+    return OrZero || Q.IIQ.isExact(BO);
   default:
     return false;
   }
 }
 
 /// Return true if the given value is known to have exactly one
 /// bit set when defined. For vectors return true if every element is known to
 /// be a power of two when defined. Supports values with integer or pointer
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
   }
 
   // A PHI node is power of two if all incoming values are power of two, or if
   // it is an induction variable where in each step its value is a power of two.
   if (const PHINode *PN = dyn_cast<PHINode>(V)) {
     Query RecQ = Q;
 
     // Check if it is an induction variable and always power of two.
-    if (Q.IIQ.UseInstrInfo && isPowerOfTwoRecurrence(PN, OrZero, Depth, RecQ))
+    if (isPowerOfTwoRecurrence(PN, OrZero, Depth, RecQ))
       return true;
 
     // Recursively check all incoming values. Limit recursion to 2 levels, so
     // that search complexity is limited to number of operands^2.
     unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
     return llvm::all_of(PN->operands(), [&](const Use &U) {
       // Value is power of 2 if it is coming from PHI node itself by induction.
       if (U.get() == PN)