[SCEV] Make isLoopEntryGuardedByCond a bit smarter

[mkazantsev]

Summary

Sometimes isLoopEntryGuardedByCond cannot prove predicate a > b directly.
But it is a common situation when a >= b is known from ranges and a != b is
known from a dominating condition. Thia patch teaches SCEV to sum these facts
together and prove strict comparison via non-strict one.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

9107

Move this to CmpInst, it already has stuff like CmpInst::getInversePredicate.

I'd also s/Loose/NonStrict/ since folks are more likely to be familiar with "strict" than with "loose".

test/Transforms/IRCE/conjunctive-checks.ll

1 ↗

(On Diff #132545)

Can you please also add a direct SCEV or IndVars test?

[mkazantsev]

Added a test on indvars.

[sanjoy]

LGTM with the comment addressed.

lib/Analysis/ScalarEvolution.cpp

9109

I'm sorry I didn't notice this before, but I think this is better to "fuse" this into the iteration we're already doing instead of recursing (which will walk the dominating checks again). Perhaps extract out a lambda that you call instead of isImpliedCond in this function that has this bit of logic too?

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9109

isLoopEntryGuardedByCond does traverse over dominating conditions. If we do this, we will have O(N^2) with N being number of dominating blocks.

I guess that your point here is that we can be able to prove one fact from assumption and another one from dominating guard. I'm totally fine with that, but I'd rather not fuse it into this loop. I'll give it some thought.

How about merging it as is an then making this improvement in separate patch?

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

9109

I guess that your point here is that we can be able to prove one fact from assumption and another one from dominating guard. I'm totally fine with that, but I'd rather not fuse it into this loop.

Yes -- you could do something like: if you can't prove A < B but can prove A != B, simplify the predicate you're trying to prove to A <= B and continue.

How about merging it as is an then making this improvement in separate patch?

Unless you're blocked on this patch, I'd rather do the right thing now than check in something with the intent to remove it later.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9109

Ok, I'll remake it.

[mkazantsev]

Blend-in the changes into the existing traversals.

[mkazantsev]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

9091 ↗

(On Diff #133159)

This assert fails, meaning that the logic of isKnownPredicateViaConstantRanges may be somehow incomplete. We can safely return true here, though.

lib/Analysis/ScalarEvolution.cpp

for (auto &AssumeVH : AC.assumptions()) {
     auto *CI = cast<CallInst>(AssumeVH);
     if (!DT.dominates(CI, L->getHeader()))
       continue;
 
     if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
       return true;
   }
 
-  auto NonStrictPredicate = Pred;
+  // If we cannot prove strict comparison (e.g. a > b), maybe we can prove
+  // the facts (a >= b && a != b) separately. A typical situation is when the
+  // non-strict comparison is known from ranges and non-equality is known from
+  // dominating predicates.
+  auto LoosePredicate = [](ICmpInst::Predicate Pred) {
     switch (Pred) {
-    case ICmpInst::ICMP_SGT: NonStrictPredicate = ICmpInst::ICMP_SGE; break;
-    case ICmpInst::ICMP_SLT: NonStrictPredicate = ICmpInst::ICMP_SLE; break;
-    case ICmpInst::ICMP_UGT: NonStrictPredicate = ICmpInst::ICMP_UGE; break;
-    case ICmpInst::ICMP_ULT: NonStrictPredicate = ICmpInst::ICMP_ULE; break;
-    default: break;
+    case ICmpInst::ICMP_SGT: return ICmpInst::ICMP_SGE;
+    case ICmpInst::ICMP_SLT: return ICmpInst::ICMP_SLE;
+    case ICmpInst::ICMP_UGT: return ICmpInst::ICMP_UGE;
+    case ICmpInst::ICMP_ULT: return ICmpInst::ICMP_ULE;
+    default: return Pred;
     }
+  };
+  auto NonStrictPredicate = LoosePredicate(Pred);
   if (Pred != NonStrictPredicate &&
       isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, LHS, RHS) &&
       isLoopEntryGuardedByCond(L, NonStrictPredicate, LHS, RHS))
     return true;
 
   return false;
 }
 

test/Transforms/IRCE/decrementing-loop.ll

-; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
+; RUN: opt -verify-loop-info -irce -debug-only=irce -S < %s 2>&1 | FileCheck %s
+
+; CHECK-LABEL: irce: in function decrementing_loop: constrained Loop at depth 1
+; CHECK-LABEL: irce: in function test_01: constrained Loop at depth 1
+; CHECK-LABEL: irce: in function test_02: constrained Loop at depth 1
 
 define void @decrementing_loop(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
  entry:
   %len = load i32, i32* %a_len_ptr, !range !0
   %first.itr.check = icmp sgt i32 %n, 0
   %start = sub i32 %n, 1
   br i1 %first.itr.check, label %loop, label %exit
 

 ; CHECK:   [[not_len_hiclamp_cmp:[^ ]+]] = icmp sgt i32 [[not_len]], [[not_n]]
 ; CHECK:   [[not_len_hiclamp:[^ ]+]] = select i1 [[not_len_hiclamp_cmp]], i32 [[not_len]], i32 [[not_n]]
 ; CHECK:   [[len_hiclamp:[^ ]+]] = sub i32 -1, [[not_len_hiclamp]]
 ; CHECK:   [[not_exit_preloop_at_cmp:[^ ]+]] = icmp sgt i32 [[len_hiclamp]], 0
 ; CHECK:   [[not_exit_preloop_at:[^ ]+]] = select i1 [[not_exit_preloop_at_cmp]], i32 [[len_hiclamp]], i32 0
 ; CHECK:   %exit.preloop.at = add i32 [[not_exit_preloop_at]], -1
 }
 
+; Make sure that we can eliminate the range check when the loop looks like:
+; for (i = len.a - 1; i >= 0; --i)
+;   b[i] = a[i];
+define void @test_01(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
+
+; CHECK-LABEL: test_01
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         %rc = and i1 true, true
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.b = load i32, i32* %b_len_ptr, !range !0
+  %first.itr.check = icmp ne i32 %len.a, 0
+  br i1 %first.itr.check, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rca = icmp ult i32 %idx.next, %len.a
+  %rcb = icmp ult i32 %idx.next, %len.b
+  %rc = and i1 %rca, %rcb
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+ in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %el.b = getelementptr i32, i32* %b, i32 %idx.next
+  %v = load i32, i32* %el.a
+  store i32 %v, i32* %el.b
+  %loop.cond = icmp slt i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+ out.of.bounds:
+  ret void
+
+ exit:
+  ret void
+}
+
+; Same as test_01, but the latch condition is unsigned
+define void @test_02(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
+
+; CHECK-LABEL: test_02
+; CHECK:       mainloop:
+; CHECK-NEXT:    br label %loop
+; CHECK:       loop:
+; CHECK:         %rc = and i1 true, true
+; CHECK:       loop.preloop:
+
+ entry:
+  %len.a = load i32, i32* %a_len_ptr, !range !0
+  %len.b = load i32, i32* %b_len_ptr, !range !0
+  %first.itr.check = icmp ne i32 %len.a, 0
+  br i1 %first.itr.check, label %loop, label %exit
+
+ loop:
+  %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
+  %idx.next = sub i32 %idx, 1
+  %rca = icmp ult i32 %idx.next, %len.a
+  %rcb = icmp ult i32 %idx.next, %len.b
+  %rc = and i1 %rca, %rcb
+  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
+
+ in.bounds:
+  %el.a = getelementptr i32, i32* %a, i32 %idx.next
+  %el.b = getelementptr i32, i32* %b, i32 %idx.next
+  %v = load i32, i32* %el.a
+  store i32 %v, i32* %el.b
+  %loop.cond = icmp ult i32 %idx, 2
+  br i1 %loop.cond, label %exit, label %loop
+
+ out.of.bounds:
+  ret void
+
+ exit:
+  ret void
+}
+
 !0 = !{i32 0, i32 2147483647}
 !1 = !{!"branch_weights", i32 64, i32 4}