Fix a naming issue in recurrence matcher

[reames]

Summary

This was brought up in D98222. The recently added matchSimpleRecurrence doesn't actually match a recurrence (oops). It matches something which is nearly a recurrence, but allows one additional free variable.

This patch splits the concept into a true recurrence matcher and a "near" recurrence matcher, and tries to clarify some comments. I'm not particularly a fan of the "near" wording, but I haven't found anything better just yet. Suggestions welcome.

[mkazantsev]

Is there any difference between this "near recurrence" and any loop-variant value? Like, in code

iv = phi 0, iv.next
x = load volatile ...
iv.next = iv + x

iv is near-recurrence in your definition. But what is a conceptual difference between iv and x? Both change on every loop iteration by a random value (or maybe don't change). They even may happen to be the same most of the time.

If you think that "near recurrences" have to be a specific class of loop variants, then we need clear definition of that is it and what properties it is expected to have.

Just from the backedge value beng a binop, I don't think we can derive any useful properties.

[reames]

Subsumed by comment change to header.

Max, on your example, consider the case where the volatile load has range metadata. Just because we have a loop varying value does not mean we know nothing about it.

llvm/include/llvm/Analysis/ValueTracking.h

constexpr unsigned MaxAnalysisRecursionDepth = 6;
   /// Check if the values in \p VL are select instructions that can be converted
   /// to a min or max (vector) intrinsic. Returns the intrinsic ID, if such a
   /// conversion is possible, together with a bool indicating whether all select
   /// conditions are only used by the selects. Otherwise return
   /// Intrinsic::not_intrinsic.
   std::pair<Intrinsic::ID, bool>
   canConvertToMinOrMaxIntrinsic(ArrayRef<Value *> VL);
 
-  /// Attempt to match a simple first order recurrence cycle of the form:
+  /// Attempt to match a cyclic phi structure of the form:
   ///   %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
   ///   %inc = binop %iv, %step
   /// OR
   ///   %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
   ///   %inc = binop %step, %iv
   ///
+  /// This is *almost* a recurrence, but %step is not required to be
+  /// invariant with respect to the cycle.  That is, we would have a
+  /// recurrence except that %step is a free variable in the formula.
+  bool matchNearRecurrence(const PHINode *P, BinaryOperator *&BO,
+                           Value *&Start, Value *&Step);
+
+  /// Analogous to the above, but starting from the binary operator
+  bool matchNearRecurrence(const BinaryOperator *I, PHINode *&P,
+                           Value *&Start, Value *&Step);
+
+  /// Attempt to match a simple first order recurrence cycle of the form:
+  ///   %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
+  ///   %inc = binop %iv, %invariant_step
+  /// OR
+  ///   %iv = phi Ty [%Start, %Entry], [%Inc, %backedge]
+  ///   %inc = binop %invariant_step, %iv
+  ///
   /// WARNING: For non-commutative operators, we will match both forms.  This
   /// results in some odd recurrence structures.  Callers may wish to filter
   /// out recurrences where the phi is not the LHS of the returned operator.
   ///
   /// NOTE: This is intentional simple.  If you want the ability to analyze
   /// non-trivial loop conditons, see ScalarEvolution instead.
   bool matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO,
-                             Value *&Start, Value *&Step);
+                             Value *&Start, Value *&Step,
+                             const DominatorTree &DT);
 
   /// Analogous to the above, but starting from the binary operator
   bool matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P,
-                                    Value *&Start, Value *&Step);
+                             Value *&Start, Value *&Step,
+                             const DominatorTree &DT);
 
   /// Return true if RHS is known to be implied true by LHS.  Return false if
   /// RHS is known to be implied false by LHS.  Otherwise, return None if no
   /// implication can be made.
   /// A & B must be i1 (boolean) values or a vector of such values. Note that
   /// the truth table for implication is the same as <=u on i1 values (but not
   /// <=s!).  The truth table for both is:
   ///    | T | F (B)

llvm/lib/Analysis/ValueTracking.cpp

if (!Known.isUnknown() && !AccConstIndices.isNullValue()) {
           /*Add=*/true, /*NSW=*/false, Known, Index);
     }
     break;
   }
   case Instruction::PHI: {
     const PHINode *P = cast<PHINode>(I);
     BinaryOperator *BO = nullptr;
     Value *R = nullptr, *L = nullptr;
-    if (matchSimpleRecurrence(P, BO, R, L)) {
+    if (matchNearRecurrence(P, BO, R, L)) {
       // Handle the case of a simple two-predecessor recurrence PHI.
       // There's a lot more that could theoretically be done here, but
       // this is sufficient to catch some interesting cases.
       unsigned Opcode = BO->getOpcode();
 
-      // If this is a shift recurrence, we know the bits being shifted in.
+      // If this is a near shift recurrence, we know the bits being shifted in.
       // We can combine that with information about the start value of the
       // recurrence to conclude facts about the result.
       if ((Opcode == Instruction::LShr || Opcode == Instruction::AShr ||
            Opcode == Instruction::Shl) &&
           BO->getOperand(0) == I) {
 
-        // We have matched a recurrence of the form:
+        // We have matched a near recurrence of the form:
         // %iv = [R, %entry], [%iv.next, %backedge]
         // %iv.next = shift_op %iv, L
+        // (Note that L may not be invariant.)
 
         // Recurse with the phi context to avoid concern about whether facts
         // inferred hold at original context instruction.  TODO: It may be
         // correct to use the original context.  IF warranted, explore and
         // add sufficient tests to cover.
         Query RecQ = Q;
         RecQ.CxtI = P;
         computeKnownBits(R, DemandedElts, Known2, Depth + 1, RecQ);
case SPF_UMAX:
       return {Intrinsic::umax, AllCmpSingleUse};
     default:
       llvm_unreachable("unexpected select pattern flavor");
     }
   }
   return {Intrinsic::not_intrinsic, false};
 }
 
-bool llvm::matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO,
+bool llvm::matchNearRecurrence(const PHINode *P, BinaryOperator *&BO,
                                  Value *&Start, Value *&Step) {
   // Handle the case of a simple two-predecessor recurrence PHI.
   // There's a lot more that could theoretically be done here, but
   // this is sufficient to catch some interesting cases.
   if (P->getNumIncomingValues() != 2)
     return false;
 
   for (unsigned i = 0; i != 2; ++i) {
     Value *L = P->getIncomingValue(i);
for (unsigned i = 0; i != 2; ++i) {
     BO = cast<BinaryOperator>(LU);
     Start = R;
     Step = L;
     return true;
   }
   return false;
 }
 
-bool llvm::matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P,
-                                 Value *&Start, Value *&Step) {
+bool llvm::matchNearRecurrence(const BinaryOperator *I, PHINode *&P,
   BinaryOperator *BO = nullptr;
   P = dyn_cast<PHINode>(I->getOperand(0));
   if (!P)
     P = dyn_cast<PHINode>(I->getOperand(1));
-  return P && matchSimpleRecurrence(P, BO, Start, Step) && BO == I;
+  return P && matchNearRecurrence(P, BO, Start, Step) && BO == I;
+}
+
+bool llvm::matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO,
+                                 Value *&Start, Value *&Step,
+                                 const DominatorTree &DT) {
+  if (!matchNearRecurrence(P, BO, Start, Step))
+    return false;
+  return DT.dominates(Step, P);
+}
+
+bool llvm::matchSimpleRecurrence(const BinaryOperator *I, PHINode *&P,
+                                 Value *&Start, Value *&Step,
+                                 const DominatorTree &DT) {
+   if (!matchNearRecurrence(I, P, Start, Step))
+    return false;
+  return DT.dominates(Step, P);
 }
 
 /// Return true if "icmp Pred LHS RHS" is always true.
 static bool isTruePredicate(CmpInst::Predicate Pred, const Value *LHS,
                             const Value *RHS, const DataLayout &DL,
                             unsigned Depth) {
   assert(!LHS->getType()->isVectorTy() && "TODO: extend to handle vectors!");
   if (ICmpInst::isTrueWhenEqual(Pred) && LHS == RHS)

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
 
   // (~x) & y  -->  ~(x | (~y))  iff that gets rid of inversions
   if (sinkNotIntoOtherHandOfAndOrOr(I))
     return &I;
 
   // An and recurrence w/loop invariant step is equivelent to (and start, step)
   PHINode *PN = nullptr;
   Value *Start = nullptr, *Step = nullptr;
-  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
+  if (matchSimpleRecurrence(&I, PN, Start, Step, DT))
     return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
 
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::matchBSwapOrBitReverse(Instruction &I,
                                                       bool MatchBSwaps,
                                                       bool MatchBitReversals) {
Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
 
   // (~x) | y  -->  ~(x & (~y))  iff that gets rid of inversions
   if (sinkNotIntoOtherHandOfAndOrOr(I))
     return &I;
 
   // An or recurrence w/loop invariant step is equivelent to (or start, step)
   PHINode *PN = nullptr;
   Value *Start = nullptr, *Step = nullptr;
-  if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
+  if (matchSimpleRecurrence(&I, PN, Start, Step, DT))
     return replaceInstUsesWith(I, Builder.CreateOr(Start, Step));
 
   return nullptr;
 }
 
 /// A ^ B can be specified using other logic ops in a variety of patterns. We
 /// can fold these early and efficiently by morphing an existing instruction.
 static Instruction *foldXorToXor(BinaryOperator &I,

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

#endif
   // latch to maximimize the chance this is true.  However, if we reused
   // existing IVs, we now need to move the increments to match our
   // expectations.  Otherwise, our cost modeling results in us having a
   // chosen a non-optimal result for the actual schedule.  (And yes, this
   // scheduling decision does impact later codegen.)
   for (PHINode &PN : L->getHeader()->phis()) {
     BinaryOperator *BO = nullptr;
     Value *Start = nullptr, *Step = nullptr;
-    if (!matchSimpleRecurrence(&PN, BO, Start, Step))
+    if (!matchSimpleRecurrence(&PN, BO, Start, Step, DT))
       continue;
 
     switch (BO->getOpcode()) {
     case Instruction::Sub:
       if (BO->getOperand(0) != &PN)
         // sub is non-commutative - match handling elsewhere in LSR
         continue;
       break;