[SCEV] Opportunistically interpret unsigned constraints as signed

[sanjoy]

Summary

An unsigned comparision is equivalent to is corresponding signed version
if both the operands being compared are positive. Teach SCEV to use
this fact when profitable.

[reames]

LGTM w/comments addressed.

Q: Does InstCombine have similar logic? If it doesn't, it really should.

lib/Analysis/ScalarEvolution.cpp

7455

I'm pretty sure this function already exists somewhere. If it doesn't, it should be a utility on ICmpInst or something.

7458

Make this an assert? I'd rather see the calling code as isUnsignedCmp, followed by a call to this with an assert inside it. Less error prone.

7534

This code is obviously correct, but it only handles one of the two cases immediately above it. I'd suggest in a separate change, pulling out the two cases above into a lambda, and then calling it twice, once with FoundPred, once with the signed compare if legal.

[sanjoy]

• address review

lib/Analysis/ScalarEvolution.cpp

7455

Moved to CmpInst::getSignedPredicate.

7534

Good idea, I'll make a follow up patch doing this.

[reames]

LGTM

include/llvm/IR/InstrTypes.h

1035 ↗

(On Diff #37386)

I believe we're moving away from this style of doxygen comment even when in code surrounded by similar. the "/// brief. long" style has seemingly become the norm.

lib/Analysis/ScalarEvolution.cpp

else
     FoundPred = ICI->getPredicate();
 
   const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
   const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
 
   return isImpliedCond(Pred, LHS, RHS, FoundPred, FoundLHS, FoundRHS);
 }
 
+static CmpInst::Predicate GetSignedPredicate(CmpInst::Predicate P) {
+  switch (P) {
+  default:
+    return CmpInst::BAD_ICMP_PREDICATE;
+
+  case CmpInst::ICMP_UGT:
+    return CmpInst::ICMP_SGT;
+
+  case CmpInst::ICMP_UGE:
+    return CmpInst::ICMP_SGE;
+
+  case CmpInst::ICMP_ULT:
+    return CmpInst::ICMP_SLT;
+
+  case CmpInst::ICMP_ULE:
+    return CmpInst::ICMP_SLE;
+  }
+}
+
 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS,
                                     ICmpInst::Predicate FoundPred,
                                     const SCEV *FoundLHS,
                                     const SCEV *FoundRHS) {
   // Balance the types.
   if (getTypeSizeInBits(LHS->getType()) <
       getTypeSizeInBits(FoundLHS->getType())) {
bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
   if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
     if (isa<SCEVConstant>(RHS))
       return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS);
     else
       return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred),
                                    RHS, LHS, FoundLHS, FoundRHS);
   }
 
+  // Unsigned comparison is the same as signed comparison when both the operands
+  // are non-negative.
+  if (GetSignedPredicate(FoundPred) == Pred && isKnownNonNegative(FoundLHS) &&
+      isKnownNonNegative(FoundRHS))
+    return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
+
   // Check if we can make progress by sharpening ranges.
   if (FoundPred == ICmpInst::ICMP_NE &&
       (isa<SCEVConstant>(FoundLHS) || isa<SCEVConstant>(FoundRHS))) {
 
     const SCEVConstant *C = nullptr;
     const SCEV *V = nullptr;
 
     if (isa<SCEVConstant>(FoundLHS)) {

test/Transforms/IndVarSimplify/eliminate-comparison.ll

be:
   call void @side_effect()
   %be.cond = icmp sle i32 %iv.inc, %lim
   br i1 %be.cond, label %loop, label %leave
 
  leave:
   ret void
 }
 
+define void @func_24(i32* %length.ptr) {
+; CHECK-LABEL: @func_24(
+ entry:
+  %length = load i32, i32* %length.ptr, !range !0
+  %entry.cond = icmp ult i32 4, %length
+  br i1 %entry.cond, label %loop, label %leave
+
+ loop:
+; CHECK: loop:
+  %iv = phi i32 [ 4, %entry ], [ %iv.inc, %be ]
+  %iv.inc = add i32 %iv, 1
+  %range.check = icmp slt i32 %iv, %length
+  br i1 %range.check, label %be, label %leave
+; CHECK:   br i1 true, label %be, label %leave.loopexit
+; CHECK: be:
+
+ be:
+  call void @side_effect()
+  %be.cond = icmp slt i32 %iv.inc, %length
+  br i1 %be.cond, label %loop, label %leave
+
+ leave:
+  ret void
+}
+
+define void @func_25(i32* %init.ptr) {
+; CHECK-LABEL: @func_25(
+ entry:
+  %init = load i32, i32* %init.ptr, !range !0
+  %entry.cond = icmp ugt i32 %init, 4
+  br i1 %entry.cond, label %loop, label %leave
+
+ loop:
+; CHECK: loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.dec, %be ]
+  %iv.dec = add i32 %iv, -1
+  %range.check = icmp sgt i32 %iv, 4
+  br i1 %range.check, label %be, label %leave
+; CHECK:   br i1 true, label %be, label %leave.loopexit
+; CHECK: be:
+
+ be:
+  call void @side_effect()
+  %be.cond = icmp sgt i32 %iv.dec, 4
+  br i1 %be.cond, label %loop, label %leave
+
+ leave:
+  ret void
+}
+
 
 !0 = !{i32 0, i32 2147483647}