[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 ↗

(On Diff #337227)

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 ↗

(On Diff #337227)

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

static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
   // icmp X, X -> true/false
   // icmp X, undef -> true/false because undef could be X.
   if (LHS == RHS || Q.isUndefValue(RHS))
     return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
 
   if (Value *V = simplifyICmpOfBools(Pred, LHS, RHS, Q))
     return V;
 
+  // TODO: Sink/common this with other potentially expensive calls that use
+  //       ValueTracking? See comment below for isKnownNonEqual().
   if (Value *V = simplifyICmpWithZero(Pred, LHS, RHS, Q))
     return V;
 
   if (Value *V = simplifyICmpWithConstant(Pred, LHS, RHS, Q.IIQ))
     return V;
 
   // If both operands have range metadata, use the metadata
   // to simplify the comparison.
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))