[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.

7515

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.

7515

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

[reames]

LGTM

include/llvm/IR/InstrTypes.h

1035

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.

include/llvm/IR/InstrTypes.h

public:
   }
 
   /// @returns true if the comparison is unsigned, false otherwise.
   /// @brief Determine if this instruction is using an unsigned comparison.
   bool isUnsigned() const {
     return isUnsigned(getPredicate());
   }
 
+  /// For example, ULT->SLT, ULE->SLE, UGT->SGT, UGE->SGE, SLT->Failed assert
+  /// @returns the signed version of the unsigned predicate pred.
+  /// @brief return the signed version of a predicate
+  static Predicate getSignedPredicate(Predicate pred);
+
+  /// For example, ULT->SLT, ULE->SLE, UGT->SGT, UGE->SGE, SLT->Failed assert
+  /// @returns the signed version of the predicate for this instruction (which
+  /// has to be an unsigned predicate).
+  /// @brief return the signed version of a predicate
+  Predicate getSignedPredicate() {
+    return getSignedPredicate(getPredicate());
+  }
+
   /// This is just a convenience.
   /// @brief Determine if this is true when both operands are the same.
   bool isTrueWhenEqual() const {
     return isTrueWhenEqual(getPredicate());
   }
 
   /// This is just a convenience.
   /// @brief Determine if this is false when both operands are the same.

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);
 }
 
 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())) {
     if (CmpInst::isSigned(Pred)) {
       LHS = getSignExtendExpr(LHS, FoundLHS->getType());
       RHS = getSignExtendExpr(RHS, FoundLHS->getType());
     } else {
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 (CmpInst::isUnsigned(FoundPred) &&
+      CmpInst::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)) {

lib/IR/Instructions.cpp

switch (pred) {
     case FCMP_OLE: return FCMP_OGE;
     case FCMP_UGT: return FCMP_ULT;
     case FCMP_ULT: return FCMP_UGT;
     case FCMP_UGE: return FCMP_ULE;
     case FCMP_ULE: return FCMP_UGE;
   }
 }
 
+CmpInst::Predicate CmpInst::getSignedPredicate(Predicate pred) {
+  assert(CmpInst::isUnsigned(pred) && "Call only with signed predicates!");
+
+  switch (pred) {
+  default:
+    llvm_unreachable("Unknown predicate!");
+  case CmpInst::ICMP_ULT:
+    return CmpInst::ICMP_SLT;
+  case CmpInst::ICMP_ULE:
+    return CmpInst::ICMP_SLE;
+  case CmpInst::ICMP_UGT:
+    return CmpInst::ICMP_SGT;
+  case CmpInst::ICMP_UGE:
+    return CmpInst::ICMP_SGE;
+  }
+}
+
 bool CmpInst::isUnsigned(unsigned short predicate) {
   switch (predicate) {
     default: return false;
     case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: case ICmpInst::ICMP_UGT: 
     case ICmpInst::ICMP_UGE: return true;
   }
 }
 

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}