[ValueTracking][InstSimplify] improve efficiency for detecting non-zero value

[spatel]

Summary

I was stepping through some of the callstacks in the example from D99759 and noticed a potential compile-time improvement.
This is really 2 patches, but I've put them together to make it easier to see if it does anything to help real-world compile-time:

1. Improve the logic in isNonZeroRecurrence() to handle the case of a negative-stepping phi+add pair.
2. Limit a call from instsimplify to isKnownNonEqual() to avoid a pile of redundant analysis.

The first step is needed to avoid a regression - the test example shown here is caught by isKnownNonEqual() but missed by isNonZeroRecurrence() without this patch.

This makes a degenerate test based on PR49785 about 40x faster (25 sec -> 0.6 sec), but it does not address the larger question of how to limit computeKnownBitsFromAssume(). Ie, the original test there is still infinite-time for all practical purposes.

[nikic]

LG, but please apply the two changes separately.

llvm/lib/Analysis/ValueTracking.cpp

2232

I'd directly return !StartC->isNullValue() && !StepC->isNullValue(); here and below.

As a side note, the requirement that StepC is non-zero is unnecessary here -- which also means that we don't need it to be a constant. But that's independent of your patch.

[nikic]

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=64c24f493e5f4637ee193f10f469cdd2695b4ba6&to=8b74fb354fa8193cd3f8da37bc82ec98519d9264&stat=instructions

[spatel]

llvm/lib/Analysis/ValueTracking.cpp

2232

Good point - this patch should be clearer if we hoist the StartC null check:
49193653974a

I'll add a TODO about the StepC requirement.

llvm/lib/Analysis/InstructionSimplify.cpp

if (isa<SExtInst>(LHS)) {
             break;
           }
         }
       }
     }
   }
 
   // icmp eq|ne X, Y -> false|true if X != Y
-  if (ICmpInst::isEquality(Pred) &&
+  // This is potentially expensive, and we have already computedKnownBits for
+  // compares with 0 above here, so only try this for a non-zero compare.
+  if (ICmpInst::isEquality(Pred) && !match(RHS, m_Zero()) &&
       isKnownNonEqual(LHS, RHS, Q.DL, Q.AC, Q.CxtI, Q.DT, Q.IIQ.UseInstrInfo)) {
     return Pred == ICmpInst::ICMP_NE ? getTrue(ITy) : getFalse(ITy);
   }
 
   if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
     return V;
 
   if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))

llvm/lib/Analysis/ValueTracking.cpp

ConstantInt *Upper =
         mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
     ConstantRange Range(Lower->getValue(), Upper->getValue());
     if (Range.contains(Value))
       return false;
   }
   return true;
 }
 
+/// Try to detect a recurrence that monotonically increases/decreases from a
+/// non-zero starting value. These are common as induction variables.
 static bool isNonZeroRecurrence(const PHINode *PN) {
-  // Try and detect a recurrence that monotonically increases from a
-  // starting value, as these are common as induction variables.
   BinaryOperator *BO = nullptr;
   Value *Start = nullptr, *Step = nullptr;
   const APInt *StartC, *StepC;
   if (!matchSimpleRecurrence(PN, BO, Start, Step) ||
       !match(Start, m_APInt(StartC)))
     return false;
 
   switch (BO->getOpcode()) {
   case Instruction::Add:
-    return match(Step, m_APInt(StepC)) &&
-           ((BO->hasNoUnsignedWrap() && !StartC->isNullValue() &&
-             !StepC->isNullValue()) ||
-            (BO->hasNoSignedWrap() && StartC->isStrictlyPositive() &&
-             StepC->isNonNegative()));
+    if (!match(Step, m_APInt(StepC)))
+      return false;
+    if (BO->hasNoUnsignedWrap()) {
+      if (!StartC->isNullValue() && !StepC->isNullValue())
+        return true;
+    }
+    if (BO->hasNoSignedWrap()) {
+      // Starting from non-zero and stepping away from zero can never wrap back
+      // to zero.
+      if (!StartC->isNullValue() && StartC->isNegative() == StepC->isNegative())
+        return true;
+    }
+    return false;
   case Instruction::Mul:
     return !StartC->isNullValue() && match(Step, m_APInt(StepC)) &&
            ((BO->hasNoUnsignedWrap() && !StepC->isNullValue()) ||
             (BO->hasNoSignedWrap() && StepC->isStrictlyPositive()));
   case Instruction::Shl:
     return !StartC->isNullValue() &&
            (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap());
   case Instruction::AShr:

llvm/unittests/Analysis/ValueTrackingTest.cpp

parseAssembly(R"(
     exit:
       %A = or i8 %p, %r
       %CxtI = icmp eq i8 %A, 0
       ret i1 %CxtI
     }
   )");
   DataLayout DL = M->getDataLayout();
   AssumptionCache AC(*F);
-  EXPECT_FALSE(isKnownNonZero(A, DL, 0, &AC, CxtI));
+  EXPECT_TRUE(isKnownNonZero(A, DL, 0, &AC, CxtI));
 }
 
 TEST_F(ValueTrackingTest, KnownNonZeroFromDomCond) {
   parseAssembly(R"(
     declare i8* @f_i8()
     define void @test(i1 %c) {
       %A = call i8* @f_i8()
       %B = call i8* @f_i8()