[IRCE] isKnownNonNegative helper

[samparker]

Summary

Breaking out the isKnownNonNegative helper function from D45439. The reason why isKnownNegative was seemingly eeded was because I was using the UGE predicate as well as SGE...

[mkazantsev]

Code part is fine (with a nit inline). Do you have a test for which this change enabled IRCE? If yes, please add.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

809

You can use SE.getZero(BoundSCEV->getType()).

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

807

How about isKnownNonNegativeInLoop?

[mkazantsev]

LGTM after you address the nits; if there is a test which shows that IRCE now works where it didn't, I highly encourage you to add it. But even if not, this change is obviously profitable.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

   APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) : 
     APInt::getMinValue(BitWidth);
   auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
   return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
          SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV,
                                      SE.getConstant(Min));
 }
 
+static bool isKnownNonNegative(const SCEV *BoundSCEV, Loop *L,
+                               ScalarEvolution &SE) {
+  const SCEV *Zero = SE.getConstant(BoundSCEV->getType(), 0, true);
+  return SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGE, BoundSCEV, Zero);
+}
+
 Optional<LoopStructure>
 LoopStructure::parseLoopStructure(ScalarEvolution &SE,
                                   BranchProbabilityInfo *BPI, Loop &L,
                                   const char *&FailureReason) {
   if (!L.isLoopSimplifyForm()) {
     FailureReason = "loop not in LoopSimplify form";
     return None;
   }

       // Try to turn eq/ne predicates to those we can work with.
       if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
         // while (++i != len) {         while (++i < len) {
         //   ...                 --->     ...
         // }                            }
         // If both parts are known non-negative, it is profitable to use
         // unsigned comparison in increasing loop. This allows us to make the
         // comparison check against "RightSCEV + 1" more optimistic.
-        if (SE.isKnownNonNegative(IndVarStart) &&
-            SE.isKnownNonNegative(RightSCEV))
+        if (isKnownNonNegative(IndVarStart, &L, SE) &&
+            isKnownNonNegative(RightSCEV, &L, SE))
           Pred = ICmpInst::ICMP_ULT;
         else
           Pred = ICmpInst::ICMP_SLT;
       else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
         // while (true) {               while (true) {
         //   if (++i == len)     --->     if (++i > len - 1)
         //     break;                       break;
         //   ...                          ...

test/Transforms/IRCE/variable-loop-bounds.ll

for.inc:
   %inc = add nuw nsw i32 %i.017, 1
   %exitcond = icmp eq i32 %inc, %N
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 }
 
 ; CHECK-LABEL: test_inc_ne
 ; CHECK: main.exit.selector:
 ; CHECK: [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %inc, %for.inc ]
-; CHECK: [[COND:%[^ ]+]] = icmp slt i32 [[PSEUDO_PHI]], %N
+; CHECK: [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], %N
 ; CHECK: br i1 [[COND]], label %main.pseudo.exit, label %for.cond.cleanup.loopexit
 define void @test_inc_ne(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
 entry:
   %cmp16 = icmp sgt i32 %N, 0
   br i1 %cmp16, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:
   ret void