[SCEV] Improve handling of pointer compares involving subtractions (WIP).

[fhahn]

Summary

WIP as I still need to do further testing and re-collecting &
applying the loop guards every time can be quite expensive in terms of
compile time. But I thought it would be good to share early, in case I
missed anything.

This patch improves handling of pointer comparisons involving
subtractions, by using knowledge that the involved variables are != 0
and signed positive.

It uses applyLoopGuards to add != 0 info to the involved expressions (by
re-writing them as umax expression. It also adds a new fold to move zext
into umax expressions and to move udiv expression inside subtraction, if
the operands guarantee a positive result.

The motivating code for this is eliminating range checks for code
like below from PR48965.

#include <assert.h>

void foo(const int *y, unsigned y_len) {
  const int *y_end = y + y_len;
  unsigned c = 0;
  for (const int *y_iter = y; y_iter != y_end; y_iter++, c++) {
    assert(c < y_len);
  }
  assert(c == y_len);
}

Proof for zext/umax fold: https://alive2.llvm.org/ce/z/t75T53

Proof for getUDivExpr extension:a https://alive2.llvm.org/ce/z/H_G2Q0

Proof for isKnownPredicateSubIdiom: https://alive2.llvm.org/ce/z/Gfe8mS

[mkazantsev]

This comment was removed by mkazantsev.

llvm/lib/Analysis/ScalarEvolution.cpp

3121

What C3 stands for? Is it actually C2?

10980

Please specify that <= and >= here are actually unsigned.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

1840

Couple of comments on this transform:

1. It's not clear why (or if) this is a profitable canonicalization. We're replacing one zext with two. I'd want an explanation of why this was the right idea, and in particular, why not to canonicalize the other direction.
2. umax can have more than two operands.
3. this should be a separate change once you're ready for actual review.

3125

Another way to consider approaching this:
(-C1 + X) /u C2

-C1/C2 + (-C1 % C2 + X) /u C2

(i.e. extract out the whole integer divisions and leave only the possible fractional part)

10983

You can also handle ULT without much work. isKnownNonNegative becomes isKnownPositive in that case.

10986

Do we canonicalize x + (-Y) to (-Y) + X somewhere? If not, you're missing some pattern matching cases here.

[fhahn]

Address comments, thanks!

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

1840

I will split this off in a separate review.

Initially I was planning on only restricting it to a umax with at least one constant operand, so the number of zexts stays the same. We already shift zexts inwards for other expressions above, so I think most code would expect them as 'inwards' as possible (but I might be wrong).

3121

It should be C2, thanks!

3125

Thanks, I'll have to think a bit more about that and see if there are any expressions that cannot be handled well by either.

10983

Done, but I still need to construct a test case.

10986

It looks like we don't do that, we only sort the operands by their complexity which should group the -1 * X parts together, but there could be other 'less complex' expression before them. I adjusted to also check for the swapped version.

I still need to construct a test case.

[fhahn]

Make sure to only handle adds with 2 operands.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

10991

For ule case the comment says that X is non-negative and the code checks it's non-positive. I guess it's a bug in code.

[xbolva00]

Re-ping

[reames]

In D97122#2772856, @xbolva00 wrote:

Re-ping

This is still marked as a WIP, what are you hoping for in terms of further reviewer involvement?

[mkazantsev]

This has been a WIP patch w/o author updates for a good while. Please add me back when it'll move somewhere.

[reames]

Pending author action, please re-add as reviewer if you ever return to this.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs,
                                               const Loop *L);
 
   /// Test if the given expression is known to satisfy the condition described
   /// by Pred and the known constant ranges of LHS and RHS.
   bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred,
                                          const SCEV *LHS, const SCEV *RHS);
 
+  /// Test if the given expression is known to satisfy the condition described
+  /// by Pred by decomposing a subtraction.
+  bool isKnownPredicateViaSubIdiom(ICmpInst::Predicate Pred, const SCEV *LHS,
+                                   const SCEV *RHS);
+
   /// Try to prove the condition described by "LHS Pred RHS" by ruling out
   /// integer overflow.
   ///
   /// For instance, this will return true for "A s< (A + C)<nsw>" if C is
   /// positive.
   bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS,
                                      const SCEV *RHS);
 

llvm/lib/Analysis/ScalarEvolution.cpp

if (SM->getNumOperands() == 2)
             return getMulExpr(
                 getZeroExtendExpr(MulLHS, Ty),
                 getZeroExtendExpr(
                     getTruncateExpr(TruncRHS->getOperand(), NewTruncTy), Ty),
                 SCEV::FlagNUW, Depth + 1);
           }
   }
 
+  // zext (A umax B) --> (zext A) umax (zext B), if one operands is a constant.
+  if (auto *SM = dyn_cast<SCEVUMaxExpr>(Op)) {
+    const SCEV *Op0 = SM->getOperand(0);
+    const SCEV *Op1 = SM->getOperand(1);
+    if (SM->getNumOperands() == 2 &&
+        (isa<SCEVConstant>(Op0) || isa<SCEVConstant>(Op1)))
+      return getUMaxExpr(getZeroExtendExpr(SM->getOperand(0), Ty),
+                         getZeroExtendExpr(SM->getOperand(1), Ty));
+  }
+
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
   addToLoopUseLists(S);
   return S;

 /// Get a canonical unsigned division expression, or something simpler if
 /// possible.
 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
                                          const SCEV *RHS) {
   assert(getEffectiveSCEVType(LHS->getType()) ==
          getEffectiveSCEVType(RHS->getType()) &&
          "SCEVUDivExpr operand types don't match!");
 
+  // Try to shift udiv across an addition even when no wrapping info is
+  // present, using the fact that (B - A)  will be in [0, B+1), if
+  // B s>= A and A s>= 0.
+  //
+  // (-C1 + X) /u C2 can be transformed to (C1 /u C2) + (X /u C2), if
+  //   * C1 % C2 == 0
+  //   * X % C2 == 0
+  //   * X s>= C1
+  //   * C1 s>= 0
+  //
+  // If C1 and C2 are constants, at least one of udiv expression can be
+  // eliminated. This pattern is commonly created for trip counts
+  // involving pointer IVs, where a multiple of the element width
+  // is subtracted.
+  const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS);
+  const SCEVConstant *C = dyn_cast<SCEVConstant>(RHS);
+  if (Add && C && Add->getNumOperands() == 2) {
+    unsigned MultTrailing = C->getAPInt().countTrailingZeros();
+    auto *NegOp0 = getNegativeSCEV(Add->getOperand(0));
+    if (GetMinTrailingZeros(Add->getOperand(0)) >= MultTrailing &&
+        GetMinTrailingZeros(Add->getOperand(1)) >= MultTrailing &&
+        isKnownNonNegative(NegOp0) &&
+        isKnownPredicate(CmpInst::ICMP_SGE, Add->getOperand(1), NegOp0)) {
+      return getMinusSCEV(getUDivExactExpr(Add->getOperand(1), RHS),
+                          getUDivExactExpr(NegOp0, RHS));
+    }
+  }
+
   FoldingSetNodeID ID;
   ID.AddInteger(scUDivExpr);
   ID.AddPointer(LHS);
   ID.AddPointer(RHS);
   void *IP = nullptr;
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
     return S;
 
ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
 
   // For positive steps (counting up until unsigned overflow):
   //   N = -Start/Step (as unsigned)
   // For negative steps (counting down to zero):
   //   N = Start/-Step
   // First compute the unsigned distance from zero in the direction of Step.
   bool CountDown = StepC->getAPInt().isNegative();
   const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start);
-
   // Handle unitary steps, which cannot wraparound.
   // 1*N = -Start; -1*N = Start (mod 2^BW), so:
   //   N = Distance (as unsigned)
   if (StepC->getValue()->isOne() || StepC->getValue()->isMinusOne()) {
     APInt MaxBECount = getUnsignedRangeMax(applyLoopGuards(Distance, L));
     APInt MaxBECountBase = getUnsignedRangeMax(Distance);
     if (MaxBECountBase.ult(MaxBECount))
       MaxBECount = MaxBECountBase;
bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
   if (!L)
     return false;
 
   // Both LHS and RHS must be available at loop entry.
   assert(isAvailableAtLoopEntry(LHS, L) &&
          "LHS is not available at Loop Entry");
   assert(isAvailableAtLoopEntry(RHS, L) &&
          "RHS is not available at Loop Entry");
-  return isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS);
+  if (isBasicBlockEntryGuardedByCond(L->getHeader(), Pred, LHS, RHS))
+    return true;
+  return isBasicBlockEntryGuardedByCond(
+      L->getHeader(), Pred, applyLoopGuards(LHS, L), applyLoopGuards(RHS, L));
 }
 
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS,
                                     const Value *FoundCondValue, bool Inverse,
                                     const Instruction *Context) {
   if (!PendingLoopPredicates.insert(FoundCondValue).second)
     return false;
case ICmpInst::ICMP_ULE: {
     break;
   }
   default:
     break;
   };
   return false;
 }
 
+bool ScalarEvolution::isKnownPredicateViaSubIdiom(ICmpInst::Predicate Pred,
+                                                  const SCEV *LHS,
+                                                  const SCEV *RHS) {
+  // Handle Y - X u<= Y, if X s>= 0 and Y u>= X. In that case, the result of (Y
+  // - X) will be in [0, Y+1) expression won't wrap in the unsigned sense. Apply
+  // similar reasoning for Y - X u< Y, if X s> 0.
+  auto *Add = dyn_cast<SCEVAddExpr>(LHS);
+  if (Add && Add->getNumOperands() == 2 &&
+      (Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT)) {
+    auto *X = Add->getOperand(0);
+    auto *Y = Add->getOperand(1);
+    auto Check = [this, Pred, RHS](const SCEV *X, const SCEV *Y) {
+      // For Y - X u<= Y, check X s>= 0,  for Y - X u< Y, check X s> 0.
+      bool CheckX = Pred == CmpInst::ICMP_ULE ? isKnownNonPositive(X)
+                                              : isKnownPositive(X);
+      return Y == RHS && CheckX && isKnownNonNegative(Y) &&
+             isKnownPredicateViaConstantRanges(CmpInst::ICMP_UGE, Y,
+                                               getNegativeSCEV(X));
+    };
+
+    // Handle (-1) * X + Y variant.
+    if (Check(X, Y))
+      return true;
+
+    // Handle swapped variant Y + (-1) * X variant.
+    if (Check(Y, X))
+      return true;
+  }
+  return false;
+}
+
 bool
 ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
                                            const SCEV *LHS, const SCEV *RHS) {
   return isKnownPredicateExtendIdiom(Pred, LHS, RHS) ||
+         isKnownPredicateViaSubIdiom(Pred, LHS, RHS) ||
          isKnownPredicateViaConstantRanges(Pred, LHS, RHS) ||
          IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) ||
          IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS) ||
          isKnownPredicateViaNoOverflow(Pred, LHS, RHS);
 }
 
 bool
 ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
   // bound of the loop (RHS), and the fact that IV does not overflow (which is
   // checked above).
   if (!isLoopInvariant(RHS, L)) {
     const SCEV *MaxBECount = computeMaxBECountForLT(
         Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
     return ExitLimit(getCouldNotCompute() /* ExactNotTaken */, MaxBECount,
                      false /*MaxOrZero*/, Predicates);
   }
+
   // If the backedge is taken at least once, then it will be taken
   // (End-Start)/Stride times (rounded up to a multiple of Stride), where Start
   // is the LHS value of the less-than comparison the first time it is evaluated
   // and End is the RHS.
   const SCEV *BECountIfBackedgeTaken =
       computeBECount(getMinusSCEV(End, Start), Stride, false);
   // If the loop entry is guarded by the result of the backedge test of the
   // first loop iteration, then we know the backedge will be taken at least
   // once and so the backedge taken count is as above. If not then we use the
   // expression (max(End,Start)-Start)/Stride to describe the backedge count,
   // as if the backedge is taken at least once max(End,Start) is End and so the
   // result is as above, and if not max(End,Start) is Start so we get a backedge
   // count of zero.
   const SCEV *BECount;

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

for (BasicBlock *ExitingBB : ExitingBlocks) {
     Type *WiderType =
       SE->getWiderType(MaxExitCount->getType(), ExitCount->getType());
     ExitCount = SE->getNoopOrZeroExtend(ExitCount, WiderType);
     MaxExitCount = SE->getNoopOrZeroExtend(MaxExitCount, WiderType);
     assert(MaxExitCount->getType() == ExitCount->getType());
 
     // Can we prove that some other exit must be taken strictly before this
     // one?
-    if (SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT,
-                                     MaxExitCount, ExitCount)) {
+    if (SE->isLoopEntryGuardedByCond(L, CmpInst::ICMP_ULT, MaxExitCount,
+                                     ExitCount)) {
       foldExit(L, ExitingBB, false, DeadInsts);
       Changed = true;
       continue;
     }
 
     // As we run, keep track of which exit counts we've encountered.  If we
     // find a duplicate, we've found an exit which would have exited on the
     // exiting iteration, but (from the visit order) strictly follows another

llvm/test/Transforms/IndVarSimplify/simplify-pointer-arithmetic.ll

 ; CHECK:       header.preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       trap.loopexit:
 ; CHECK-NEXT:    br label [[TRAP]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       header:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
-; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 0, [[HEADER_PREHEADER]] ]
-; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
-; CHECK-NEXT:    [[I_ULT_EXT:%.*]] = icmp ult i64 [[I]], [[EXT]]
-; CHECK-NEXT:    br i1 [[I_ULT_EXT]], label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 true, label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
 ; CHECK:       latch:
 ; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
 ; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i1 true
 ;

 ; CHECK:       header.preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       trap.loopexit:
 ; CHECK-NEXT:    br label [[TRAP]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       header:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
-; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 1, [[HEADER_PREHEADER]] ]
-; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
-; CHECK-NEXT:    [[I_ULT_EXT:%.*]] = icmp ule i64 [[I]], [[EXT]]
-; CHECK-NEXT:    br i1 [[I_ULT_EXT]], label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br i1 true, label [[LATCH]], label [[TRAP_LOOPEXIT:%.*]]
 ; CHECK:       latch:
 ; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
 ; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i1 true
 ;

 ; CHECK:       header.preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       trap.loopexit:
 ; CHECK-NEXT:    br label [[TRAP]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       header:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32* [ [[P_INC:%.*]], [[LATCH:%.*]] ], [ [[P_BASE]], [[HEADER_PREHEADER]] ]
-; CHECK-NEXT:    [[I:%.*]] = phi i64 [ [[I_INC:%.*]], [[LATCH]] ], [ 0, [[HEADER_PREHEADER]] ]
-; CHECK-NEXT:    [[I_INC]] = add nuw nsw i64 [[I]], 1
-; CHECK-NEXT:    [[I_UGE_EXT:%.*]] = icmp uge i64 [[I]], [[EXT]]
-; CHECK-NEXT:    br i1 [[I_UGE_EXT]], label [[TRAP_LOOPEXIT:%.*]], label [[LATCH]]
+; CHECK-NEXT:    br i1 false, label [[TRAP_LOOPEXIT:%.*]], label [[LATCH]]
 ; CHECK:       latch:
 ; CHECK-NEXT:    [[P_INC]] = getelementptr inbounds i32, i32* [[P]], i64 1
 ; CHECK-NEXT:    [[C:%.*]] = icmp ne i32* [[P_INC]], [[P_END]]
 ; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    br i1 [[C]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i1 true
 ;