[SCEV] Make howFarToZero produce a smaller max backedge-taken count

[efriedma]

Summary

Use the obvious formula for the maximum backedge-taken count.

[sbaranga]

lib/Analysis/ScalarEvolution.cpp

7217

This looks correct to me, but I think it could use a comment.

Do we only need to match against Distance + 1 because this is what we typically get from rotating the loop? Otherwise I think this could be generalized to Distance + constant, but we would need to do some work to find the value of the constant.

[efriedma]

lib/Analysis/ScalarEvolution.cpp

7217

The transform is correct because we prove "Distance + 1" doesn't overflow. I'll add a comment explaining that.

You could generalize this to "Distance + Constant", but it's not clear what sort of pattern we would be looking for. (Also, at that point, it would probably be better to just write a context-sensitive version of getUnsignedRange().)

[efriedma]

Update comments; add additional testcase.

[sanjoy]

I'm happy with the direction, but I think this is changing the code in two ways at once. I'd rather have the two changes clearly spelt out as different checkins.

lib/Analysis/ScalarEvolution.cpp

7210

I think we should really split this change up into two.

• First the cleanup to handle count-up loops and count-down loops more uniformly (i.e. first reduce to {D,+,-1} and then compute getUnsignedMax(D)) than the current ad-hoc logic. IIUC, this change is already an improvement for cases like {X,+,1} != 0 if range(X) == [-5, 1) (say).
• Add the smartness around unsigned_max(D) == unsigned_max(D + 1) - 1 on no overflow in a separate commit.

7216

s/getAddExpr(Distance, getOne(Distance->getType()))/getAddExpr(Distance, One)/ ?

7219

Why are you checking (Distance + 1) != 0 instead of Distance != -1? I'd find the latter more straightforward.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

7219

In case I gave the wrong impression, I don't specifically care about checking (Distance + 1) != 0 vs. Distance != -1. If you find the former more straightforward, then I'm okay too.

[efriedma]

Split so this change just contains the cleanup. (This is enough to fix ne_max_trip_count_1.)

[efriedma]

lib/Analysis/ScalarEvolution.cpp

7210

Okay, uploaded the first part of the split version.

7219

I went with (Distance + 1) != 0 because it matches the condition which is likely to be written in the IR.

[sanjoy]

lgtm

lib/Analysis/ScalarEvolution.cpp

7209–7229

I'd add a one-liner here:

// Solve {Distance,+,-1} == 0.

lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit,
   // 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()->equalsInt(1) || StepC->getValue()->isAllOnesValue()) {
-    ConstantRange CR = getUnsignedRange(Start);
-    const SCEV *MaxBECount;
-    if (!CountDown && CR.getUnsignedMin().isMinValue())
-      // When counting up, the worst starting value is 1, not 0.
-      MaxBECount = CR.getUnsignedMax().isMinValue()
-        ? getConstant(APInt::getMinValue(CR.getBitWidth()))
-        : getConstant(APInt::getMaxValue(CR.getBitWidth()));
-    else
-      MaxBECount = getConstant(CountDown ? CR.getUnsignedMax()
-                                         : -CR.getUnsignedMin());
-    return ExitLimit(Distance, MaxBECount, false, Predicates);
+    APInt MaxBECount = getUnsignedRange(Distance).getUnsignedMax();
+
+    // When a loop like "for (int i = 0; i != n; ++i) { /* body */ }" is rotated,
+    // we end up with a loop whose backedge-taken count is n - 1.  Detect this
+    // case, and see if we can improve the bound.
+    //
+    // Explicitly handling this here is necessary because getUnsignedRange
+    // isn't context-sensitive; it doesn't know that we only care about the
+    // range inside the loop.
+    const SCEV *Zero = getZero(Distance->getType());
+    const SCEVConstant *One = cast<SCEVConstant>(getOne(Distance->getType()));
+    const SCEV *DistancePlusOne = getAddExpr(Distance, getOne(Distance->getType()));
+    if (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, DistancePlusOne, Zero)) {
+      // If Distance + 1 doesn't overflow, we can compute the maximum distance
+      // as "unsigned_max(Distance + 1) - 1".
+      ConstantRange CR = getUnsignedRange(DistancePlusOne);
+      APInt NewMaxBECount = CR.getUnsignedMax() - One->getAPInt();
+      if (NewMaxBECount.ult(MaxBECount))
+        MaxBECount = NewMaxBECount;
+    }
+    return ExitLimit(Distance, getConstant(MaxBECount), false, Predicates);
   }
 
   // As a special case, handle the instance where Step is a positive power of
   // two. In this case, determining whether Step divides Distance evenly can be
   // done by counting and comparing the number of trailing zeros of Step and
   // Distance.
   if (!CountDown) {
     const APInt &StepV = StepC->getAPInt();

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

 for.cond.i:                                       ; preds = %for.body.i
   store i32 %add.i.i, i32* @a, align 4
   %cmp.i = icmp slt i32 %storemerge1.i, 3
   br i1 %cmp.i, label %for.body.i, label %bar.exit
 
 bar.exit:                                         ; preds = %for.cond.i, %for.body.i
   ret i32 0
 }
+
+; CHECK-LABEL: @ne_max_trip_count_1
+; CHECK: Loop %for.body: max backedge-taken count is 7
+define i32 @ne_max_trip_count_1(i32 %n) {
+entry:
+  %masked = and i32 %n, 7
+  br label %for.body
+
+for.body:
+  %i = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %add = add nsw i32 %i, 1
+  %cmp = icmp ne i32 %i, %masked
+  br i1 %cmp, label %for.body, label %bar.exit
+
+bar.exit:
+  ret i32 0
+}
+
+; CHECK-LABEL: @ne_max_trip_count_2
+; CHECK: Loop %for.body: max backedge-taken count is -1
+define i32 @ne_max_trip_count_2(i32 %n) {
+entry:
+  %masked = and i32 %n, 7
+  br label %for.body
+
+for.body:
+  %i = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %add = add nsw i32 %i, 1
+  %cmp = icmp ne i32 %add, %masked
+  br i1 %cmp, label %for.body, label %bar.exit
+
+bar.exit:
+  ret i32 0
+}
+
+; CHECK-LABEL: @ne_max_trip_count_3
+; CHECK: Loop %for.body: max backedge-taken count is 6
+define i32 @ne_max_trip_count_3(i32 %n) {
+entry:
+  %masked = and i32 %n, 7
+  %guard = icmp eq i32 %masked, 0
+  br i1 %guard, label %exit, label %for.preheader
+
+for.preheader:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ]
+  %add = add nsw i32 %i, 1
+  %cmp = icmp ne i32 %add, %masked
+  br i1 %cmp, label %for.body, label %loop.exit
+
+loop.exit:
+  br label %exit
+
+exit:
+  ret i32 0
+}
+
+; CHECK-LABEL: @ne_max_trip_count_4
+; CHECK: Loop %for.body: max backedge-taken count is -2
+define i32 @ne_max_trip_count_4(i32 %n) {
+entry:
+  %guard = icmp eq i32 %n, 0
+  br i1 %guard, label %exit, label %for.preheader
+
+for.preheader:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [ 0, %for.preheader ], [ %add, %for.body ]
+  %add = add nsw i32 %i, 1
+  %cmp = icmp ne i32 %add, %n
+  br i1 %cmp, label %for.body, label %loop.exit
+
+loop.exit:
+  br label %exit
+
+exit:
+  ret i32 0
+}