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

(On Diff #37213)

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

7458 ↗

(On Diff #37213)

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 ↗

(On Diff #37213)

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 ↗

(On Diff #37213)

Moved to CmpInst::getSignedPredicate.

7534 ↗

(On Diff #37213)

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.

llvm/trunk/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.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

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)) {

llvm/trunk/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;
   }
 }
 

llvm/trunk/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}