[SCEV] Support single-cond range check idiom in applyLoopGuards.

[fhahn]

Summary

This patch extends applyLoopGuards to detect a single-cond range check
idiom that InstCombine generates.

It extends applyLoopGuards to detect (LHS Predicate RHS) which
represents a compare for a range check with a single condition,
as InstCombine may create. A check of the form (-1 + X) u< C
where C in [1, unsigned max) can be de-composed into 2 separate checks:

• X u< (1 + C)
• X u> 0.

In practice, this enables us to correctly compute a tight trip count
bounds for code as in the function below. InstCombine will fold the
minimum iteration check created by LoopRotate with the user check (< 8).

void unsigned_check(short *pred, unsigned width) {
    if (width < 8) {
        for (int x = 0; x < width; x++)
            pred[x] = pred[x] * pred[x];
    }
}

As a consequence, LLVM creates dead vector loops for the code above,
e.g. see https://godbolt.org/z/cb8eTcqET

Note that I think it is a bit unfortunate that we still need to detect
such patterns explicitly, but I am not sure if there's a better
alternative at the moment.

Attempt to model using Alive2:
https://alive2.llvm.org/ce/z/_VbcYZ

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

13671

Instead of trying to special-case (-1 + X) u< C, could you use ConstantRange::makeExactICmpRegion? Not that this necessarily needs to be generalized, but it would be easier to follow the logic, I think.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

13660

I found the wording on this confusing the first several times I read it. Can you reword? One suggestion below if helpful.

Check for a condition of the form (X - 1) < C. InstCombine will create this form when combining two checks of the form x <= C and x >u 0.

(Note the use of the <= to avoid need for C+1 in example. Note avoid mention "range check" as X > 0 doesn't seem like an idiomatic range check to me.)

13666

Style wise: I'd suggest writing a lambda with the signature
matchSomeName = [&](SCEV *& X, SCEVConstant *&C).

I at least would find early return much easier to follow here.

[fhahn]

Addressed both Philip's and Eli's comments, thanks! I moved the code to a lambda and updated it to use makeExactICmpRegion, which no also support arbitrary lower bound values. Generalized modeling in Alive2: https://alive2.llvm.org/ce/z/Lt2ICd

[fhahn]

Fix formatting

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

13660

Thanks for the suggestion. I updated the wording, but adjusted it slightly to make the lower bound also an arbitrary constant.

13666

Thanks! I moved the checks + update to the map to a single lambda. Happy to only move the 'match' part as well, if you think that's beneficial.

13671

Thanks for the suggestion! I updated the code to use makeExactICmpRegion, which should be a bit simpler and it should now support arbitrary lower bounds. I think we need to make sure the computed region does not wrap and lower <= upper.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

13677

Checking getLower/getUpper here shouldn't be necessary, as you already check for a wrapped set.

13688

Ranges are half-open, so I don't think getUpper() is correct here. I recommend using getUnsignedMin() and getUnsignedMax() instead. If you do that, then the wrapped set check is also no longer relevant for correctness.

[fhahn]

Address @nikic's comments, use getUnsigned{Min,Max}, remove upper/lower check. Thanks!

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

13677

good point, removed.

13688

That's better thanks. I still kept the wrapped check because re-writing is unlikely to add additional info for wrapped ranges.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

13664

I would check || AddExpr->getNumOperands() != 2 already here...

13668

... and then fetch LHSUnknown and check it already here. That seems like a more obvious grouping of conditions.

13688

Right. A future extension here could be to check whether it's wrapping but not sign-wrapping, in which case you could do the same with smin/smax.

[lebedev.ri]

LG in general

llvm/lib/Analysis/ScalarEvolution.cpp

13660–13661

This comment doesn't make sense right now.
https://godbolt.org/z/n7qqsTY9e

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

13660–13661

Thanks, I adjusted the comment, but kept the form where C1 is negative in the original condition, as this seems more common in practice.

13668

Thanks, I adjusted the checks as suggested.

[void]

This commit is breaking the Linux kernel built with it. The kernel's based on version 4.15. When I compile the kernel with it, the system doesn't boot.

[reames]

In D104741#2983158, @void wrote:

This commit is breaking the Linux kernel built with it. The kernel's based on version 4.15. When I compile the kernel with it, the system doesn't boot.

It looks like this was tracked down in PR51760, and fixed. Can you confirm that it is in fact the same issue?

[void]

In D104741#2990044, @reames wrote:

In D104741#2983158, @void wrote:

This commit is breaking the Linux kernel built with it. The kernel's based on version 4.15. When I compile the kernel with it, the system doesn't boot.

It looks like this was tracked down in PR51760, and fixed. Can you confirm that it is in fact the same issue?

That fix did fix my issue. :-)

llvm/lib/Analysis/ScalarEvolution.cpp

if (Predicate == CmpInst::ICMP_EQ && RHSC &&
               getMulExpr(getUDivExpr(URemLHS, URemRHS), URemRHS,
                          (SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNSW));
           RewriteMap[V] = Multiple;
           return;
         }
       }
     }
 
-    if (!isa<SCEVUnknown>(LHS)) {
+    if (!isa<SCEVUnknown>(LHS) && isa<SCEVUnknown>(RHS)) {
       std::swap(LHS, RHS);
       Predicate = CmpInst::getSwappedPredicate(Predicate);
     }
 
+    // Check for a condition of the form (X - C1) < C2.  InstCombine will create this form when combining two checks of the form x u<= C2 and x >=u C1.
+    auto MatchRangeCheckIdiom = [this, Predicate, LHS, RHS, &RewriteMap]() {
+      auto *AddExpr = dyn_cast<SCEVAddExpr>(LHS);
+      if (!AddExpr)
+        return false;
+
+      auto *C1 = dyn_cast<SCEVConstant>(AddExpr->getOperand(0));
+      auto *C2 = dyn_cast<SCEVConstant>(RHS);
+      if (AddExpr->getNumOperands() != 2 || !C1 || !C2)
+        return false;
+      auto ExactRegion =
+          ConstantRange::makeExactICmpRegion(Predicate, C2->getAPInt())
+              .sub(C1->getAPInt());
+
+      // Bail out, unless we have a non-wrapping, monotonic range.
+      if (ExactRegion.isWrappedSet() ||
+          ExactRegion.isFullSet() ||
+          ExactRegion.getLower().ugt(ExactRegion.getUpper()))
+        return false;
+
+      auto *LHSUnknown = dyn_cast<SCEVUnknown>(AddExpr->getOperand(1));
+      if (!LHSUnknown)
+        return false;
+
+      auto I = RewriteMap.find(LHSUnknown->getValue());
+      const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHS;
+      RewriteMap[LHSUnknown->getValue()] = getUMaxExpr(
+          getConstant(ExactRegion.getLower()),
+          getUMinExpr(RewrittenLHS, getConstant(ExactRegion.getUpper())));
+      return true;
+    };
+    if (MatchRangeCheckIdiom())
+      return;
+
     // For now, limit to conditions that provide information about unknown
     // expressions. RHS also cannot contain add recurrences.
     auto *LHSUnknown = dyn_cast<SCEVUnknown>(LHS);
     if (!LHSUnknown || containsAddRecurrence(RHS))
       return;
 
     // Check whether LHS has already been rewritten. In that case we want to
     // chain further rewrites onto the already rewritten value.

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll

 ; InstCombine transforms such checks with 2 conditions to a single check as in
 ; the test function.
 define void @optimized_range_check_unsigned(i16* %pred, i32 %N) {
 ; CHECK-LABEL: 'optimized_range_check_unsigned'
 ; CHECK-NEXT:  Classifying expressions for: @optimized_range_check_unsigned
 ; CHECK-NEXT:    %N.off = add i32 %N, -1
 ; CHECK-NEXT:    --> (-1 + %N) U: full-set S: full-set
 ; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
-; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %N) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,8) S: [0,8) Exits: (-1 + %N) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %gep = getelementptr inbounds i16, i16* %pred, i32 %iv
 ; CHECK-NEXT:    --> {%pred,+,2}<nuw><%loop> U: full-set S: full-set Exits: ((2 * (zext i32 (-1 + %N) to i64))<nuw><nsw> + %pred) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i32 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %N LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,9) S: [1,9) Exits: %N LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @optimized_range_check_unsigned
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %N)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 7
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %N)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %N.off = add i32 %N, -1
   %cmp = icmp ult i32 %N.off, 7
   br i1 %cmp, label %loop, label %exit
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
   %gep = getelementptr inbounds i16, i16* %pred, i32 %iv
   store i16 0, i16* %gep, align 2
   %iv.next = add nuw nsw i32 %iv, 1
   %ec = icmp eq i32 %iv.next, %N
   br i1 %ec, label %exit, label %loop
 
 exit:
   ret void
 }
 
+; The function below uses a single condition to ensure %N > 2 && %N < 22.
+; InstCombine transforms such checks with 2 conditions to a single check as in
+; the test function.
+define void @optimized_range_check_unsigned2(i16* %pred, i32 %N) {
+; CHECK-LABEL: 'optimized_range_check_unsigned2'
+; CHECK-NEXT:  Classifying expressions for: @optimized_range_check_unsigned2
+; CHECK-NEXT:    %N.off = add i32 %N, -2
+; CHECK-NEXT:    --> (-2 + %N) U: full-set S: full-set
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,22) S: [0,22) Exits: (-1 + %N) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %gep = getelementptr inbounds i16, i16* %pred, i32 %iv
+; CHECK-NEXT:    --> {%pred,+,2}<nuw><%loop> U: full-set S: full-set Exits: ((2 * (zext i32 (-1 + %N) to i64))<nuw><nsw> + %pred) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.next = add nuw nsw i32 %iv, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,23) S: [1,23) Exits: %N LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @optimized_range_check_unsigned2
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %N)
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 21
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %N)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  %N.off = add i32 %N, -2
+  %cmp = icmp ult i32 %N.off, 20
+  br i1 %cmp, label %loop, label %exit
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+  %gep = getelementptr inbounds i16, i16* %pred, i32 %iv
+  store i16 0, i16* %gep, align 2
+  %iv.next = add nuw nsw i32 %iv, 1
+  %ec = icmp eq i32 %iv.next, %N
+  br i1 %ec, label %exit, label %loop
+
+exit:
+  ret void
+}
+
 ; Similar to @optimized_range_check_unsigned, but the initial compare checks
 ; against unsigned max (-1), which breaks the range check idiom.
 define void @not_optimized_range_check_unsigned1(i16* %pred, i32 %N) {
 ; CHECK-LABEL: 'not_optimized_range_check_unsigned1'
 ; CHECK-NEXT:  Classifying expressions for: @not_optimized_range_check_unsigned1
 ; CHECK-NEXT:    %N.off = add i32 %N, -1
 ; CHECK-NEXT:    --> (-1 + %N) U: full-set S: full-set
 ; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]

 ; CHECK-NEXT:    --> {%pred,+,2}<nuw><%loop> U: full-set S: full-set Exits: ((2 * (zext i32 (-1 + %N) to i64))<nuw><nsw> + %pred) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i32 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %N LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @not_optimized_range_check_unsigned2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %N)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -2
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %N)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %loop: Trip multiple is 1
+; CHECK:       Loop %loop: Trip multiple is 2147483648
 ;
 entry:
   %N.off = add i32 %N, -1
   %cmp = icmp ult i32 %N.off, 0
   br i1 %cmp, label %loop, label %exit
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]