[SCEV] If max BTC is zero, then so is the exact BTC [2 of 2]

[reames]

Summary

This extends D108921 into a generic rule applied to constructing ExitLimits along all paths. The remaining paths (primarily howFarToZero) don't have the same reasoning about UB sensitivity as the howManyLessThan ones did. Instead, the remain cause for max counts being more precise than exact counts is that we apply context sensitive loop guards on the max path, and not on the exact path. That choice is mildly suspect, but out of scope of this patch.

The MVETailPredication.cpp change deserves a bit of explanation. We were previously figuring out that two SCEVs happened to be equal because the happened to be identical. When we optimized one with context sensitive information, but not the other, we lost the ability to prove them equal. So, cover this case by subtracting and then applying loop guards again. Without this, we see changes in test/CodeGen/Thumb2/mve-blockplacement.ll

[nikic]

llvm/lib/Target/ARM/MVETailPredication.cpp

305

Any chance evaluating an EQ predicate with one of our context sensitive functions (like isLoopEntryGuardedBy) would also work here? Calling applyLoopGuards() here is rather tightly coupled to SCEV implementation details.

[reames]

llvm/lib/Target/ARM/MVETailPredication.cpp

305

I don't believe we can here without changing the cases this can and can't handle more than I'm comfortable with. I don't understand this code - the comments appears to be out of sync with what it actually does - so I'd strongly prefer to keep it as close to the original structure as possible.

[nikic]

LGTM

llvm/lib/Target/ARM/MVETailPredication.cpp

305

Okay, let's land this as-is. But maybe @dmgreen or @SjoerdMeijer can take a look at this code and check whether it's possible to avoid doing this.

llvm/lib/Analysis/ScalarEvolution.cpp

 ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E)
     : ExitLimit(E, E, false, None) {
 }
 
 ScalarEvolution::ExitLimit::ExitLimit(
     const SCEV *E, const SCEV *M, bool MaxOrZero,
     ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList)
     : ExactNotTaken(E), MaxNotTaken(M), MaxOrZero(MaxOrZero) {
+  // If we prove the max count is zero, so is the symbolic bound.  This happens
+  // in practice due to differences in a) how context sensitive we've chosen
+  // to be and b) how we reason about bounds impied by UB.
+  if (MaxNotTaken->isZero())
+    ExactNotTaken = MaxNotTaken;
+
   assert((isa<SCEVCouldNotCompute>(ExactNotTaken) ||
           !isa<SCEVCouldNotCompute>(MaxNotTaken)) &&
          "Exact is not allowed to be less precise than Max");
   assert((isa<SCEVCouldNotCompute>(MaxNotTaken) ||
           isa<SCEVConstant>(MaxNotTaken)) &&
          "No point in having a non-constant max backedge taken count!");
   for (auto *PredSet : PredSetList)
     for (auto *P : *PredSet)
if (isa<SCEVConstant>(BECount)) {
     // If we know exactly how many times the backedge will be taken if it's
     // taken at least once, then the backedge count will either be that or
     // zero.
     MaxBECount = BECountIfBackedgeTaken;
     MaxOrZero = true;
   } else {
     MaxBECount = computeMaxBECountForLT(
         Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
-    // If we prove the max count is zero, so is the symbolic bound.  This can
-    // happen due to differences in how we reason about bounds impied by UB.
-    if (MaxBECount->isZero())
-      BECount = MaxBECount;
   }
 
   if (isa<SCEVCouldNotCompute>(MaxBECount) &&
       !isa<SCEVCouldNotCompute>(BECount))
     MaxBECount = getConstant(getUnsignedRangeMax(BECount));
 
   return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates);
 }

llvm/lib/Target/ARM/MVETailPredication.cpp

if ((ConstElemCount = dyn_cast<ConstantInt>(ElemCount))) {
     //
     // and "ElementCount + (VW-1) / VW":
     //
     //   Ceil = ((3 + %N) /u 4)
     //
     // Check for equality of TC and Ceil by calculating SCEV expression
     // TC - Ceil and test it for zero.
     //
-    bool Zero = SE->getMinusSCEV(
-                      SE->getBackedgeTakenCount(L),
+    const SCEV *Sub =
+      SE->getMinusSCEV(SE->getBackedgeTakenCount(L),
                        SE->getUDivExpr(SE->getAddExpr(SE->getMulExpr(Ceil, VW),
                                                       SE->getNegativeSCEV(VW)),
-                                      VW))
-                    ->isZero();
+                                       VW));
 
-    if (!Zero) {
+    // Use context sensitive facts about the path to the loop to refine.  This
+    // comes up as the backedge taken count can incorporate context sensitive
+    // reasoning, and our RHS just above doesn't.
+    Sub = SE->applyLoopGuards(Sub, L);
+
+    if (!Sub->isZero()) {
       LLVM_DEBUG(dbgs() << "ARM TP: possible overflow in sub expression.\n");
       return false;
     }
   }
 
   // 3) Find out if IV is an induction phi. Note that we can't use Loop
   // helpers here to get the induction variable, because the hardware loop is
   // no longer in loopsimplify form, and also the hwloop intrinsic uses a

llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

exit:
   ret void
 }
 
 ; This is a case where our max-backedge taken count logic happens to be
 ; able to prove a zero btc, but our symbolic logic doesn't due to a lack
 ; of context sensativity.
 define void @ne_zero_max_btc(i32 %a) {
 ; CHECK-LABEL: Determining loop execution counts for: @ne_zero_max_btc
-; CHECK: Loop %for.body: backedge-taken count is (-1 + (zext i32 (1 umax (1 smin %a)) to i64))<nsw>
+; CHECK: Loop %for.body: backedge-taken count is 0
 ; CHECK: Loop %for.body: max backedge-taken count is 0
 entry:
   %cmp = icmp slt i32 %a, 1
   %spec.select = select i1 %cmp, i32 %a, i32 1
   %cmp8 = icmp sgt i32 %a, 0
   br i1 %cmp8, label %for.body.preheader, label %loopexit
 
 for.body.preheader:                         ; preds = %if.then4.i.i