[CVP] Simplify comparisons without constant operand

[nikic]

Summary

CVP currently only tries to simplify comparisons if there is a constant operand. However, even if both are non-constant, we may be able to determine the result of the comparison based on range information.

IPSCCP is already capable of doing this, but because it runs very early, it may miss some cases.

This has some compile-time cost, but not particularly large: http://llvm-compile-time-tracker.com/compare.php?from=5fe9273c73969791795e5302933abadc9f33f09a&to=4c49e6b0e7d1834dd9e1f29144e915c7279740fb&stat=instructions:u

[spatel]

llvm/lib/Analysis/LazyValueInfo.cpp

1874

Does something in the callers preclude vector icmp from reaching here? If not, should this use CmpInst::makeCmpResultType()? If yes, then can we assert that LHS/RHS are scalars?

llvm/test/Transforms/CorrelatedValuePropagation/mul.ll

215–216

"add nuw" is all that is needed to fold this and the next test. Do those simpler examples work, or should there be a TODO?

[nikic]

llvm/test/Transforms/CorrelatedValuePropagation/mul.ll

215–216

It does work with just add nuw (and the nsw on mul gets inferred). TBH, I don't think this test really makes sense. It was added in https://github.com/llvm/llvm-project/commit/f26758486399a542893addd83cd3a1056911d8bd in preparation for handling nuw/nsw flags on mul, so if the flag ends up not mattering, the test probably doesn't test what it was supposed to.

I think what this might have wanted to test is something closer to this? https://alive2.llvm.org/ce/z/BkZtMv

This patch wouldn't be sufficient to handle that, but this patch + mul nsw support should be able to handle it.

cc @reames

[nikic]

Add vector test, use makeCmpResultType().

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1874

Vector icmps can reach this function, but LVI will always produce overdefined for the operands. That said, it still makes sense to use makeCmpResultType() to make this more future proof, in case LVI gets vector support.

I've also added a vector icmp test case (which currently does not fold).

[spatel]

LGTM

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

351–352

Should update this one to CmpInst::makeCmpResultType() too to future-proof it.

llvm/lib/Analysis/LazyValueInfo.cpp

LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned P, Value *LHS,
   CmpInst::Predicate Pred = (CmpInst::Predicate)P;
 
   if (auto *C = dyn_cast<Constant>(RHS))
     return getPredicateAt(P, LHS, C, CxtI, UseBlockValue);
   if (auto *C = dyn_cast<Constant>(LHS))
     return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI,
                           UseBlockValue);
 
-  // Got two non-Constant values. While we could handle them somewhat,
-  // by getting their constant ranges, and applying ConstantRange::icmp(),
-  // so far it did not appear to be profitable.
+  // Got two non-Constant values. Try to determine the comparison results based
+  // on the block values of the two operands, e.g. because they have
+  // non-overlapping ranges.
+  if (UseBlockValue) {
+    Module *M = CxtI->getModule();
+    ValueLatticeElement L =
+        getImpl(PImpl, AC, M).getValueInBlock(LHS, CxtI->getParent(), CxtI);
+    if (L.isOverdefined())
+      return LazyValueInfo::Unknown;
+
+    ValueLatticeElement R =
+        getImpl(PImpl, AC, M).getValueInBlock(RHS, CxtI->getParent(), CxtI);
+    Type *Ty = CmpInst::makeCmpResultType(LHS->getType());
+    if (Constant *Res = L.getCompare((CmpInst::Predicate)P, Ty, R,
+                                     M->getDataLayout())) {
+      if (Res->isNullValue())
+        return LazyValueInfo::False;
+      if (Res->isOneValue())
+        return LazyValueInfo::True;
+    }
+  }
   return LazyValueInfo::Unknown;
 }
 
 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
                                BasicBlock *NewSucc) {
   if (PImpl) {
     getImpl(PImpl, AC, PredBB->getModule())
         .threadEdge(PredBB, OldSucc, NewSucc);

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

 }
 
 /// See if LazyValueInfo's ability to exploit edge conditions or range
 /// information is sufficient to prove this comparison. Even for local
 /// conditions, this can sometimes prove conditions instcombine can't by
 /// exploiting range information.
 static bool constantFoldCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
   Value *Op0 = Cmp->getOperand(0);
-  auto *C = dyn_cast<Constant>(Cmp->getOperand(1));
-  if (!C)
-    return false;
-
+  Value *Op1 = Cmp->getOperand(1);
   LazyValueInfo::Tristate Result =
-      LVI->getPredicateAt(Cmp->getPredicate(), Op0, C, Cmp,
+      LVI->getPredicateAt(Cmp->getPredicate(), Op0, Op1, Cmp,
                           /*UseBlockValue=*/true);
   if (Result == LazyValueInfo::Unknown)
     return false;
 
   ++NumCmps;
-  Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
+  Constant *TorF =
+      ConstantInt::get(CmpInst::makeCmpResultType(Op0->getType()), Result);
   Cmp->replaceAllUsesWith(TorF);
   Cmp->eraseFromParent();
   return true;
 }
 
 static bool processCmp(CmpInst *Cmp, LazyValueInfo *LVI) {
   if (constantFoldCmp(Cmp, LVI))
     return true;

llvm/test/Transforms/CorrelatedValuePropagation/icmp.ll

 define void @non_const_range(i32 %a, i32 %b) {
 ; CHECK-LABEL: @non_const_range(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[A:%.*]], 11
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[B:%.*]], 21
 ; CHECK-NEXT:    [[AND:%.*]] = select i1 [[CMP1]], i1 [[CMP2]], i1 false
 ; CHECK-NEXT:    br i1 [[AND]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[A_100:%.*]] = add nuw nsw i32 [[A]], 100
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i32 [[A_100]], [[B]]
-; CHECK-NEXT:    call void @check1(i1 [[CMP3]])
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i32 [[A_100]], [[B]]
-; CHECK-NEXT:    call void @check1(i1 [[CMP4]])
+; CHECK-NEXT:    call void @check1(i1 true)
+; CHECK-NEXT:    call void @check1(i1 false)
 ; CHECK-NEXT:    [[A_10:%.*]] = add nuw nsw i32 [[A]], 10
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp ne i32 [[A_10]], [[B]]
 ; CHECK-NEXT:    call void @check1(i1 [[CMP5]])
 ; CHECK-NEXT:    [[CMP6:%.*]] = icmp eq i32 [[A_10]], [[B]]
 ; CHECK-NEXT:    call void @check1(i1 [[CMP6]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       else:
 ; CHECK-NEXT:    ret void

 else:
   ret void
 }
 
 define i1 @non_const_range_minmax(i8 %a, i8 %b) {
 ; CHECK-LABEL: @non_const_range_minmax(
 ; CHECK-NEXT:    [[A2:%.*]] = call i8 @llvm.umin.i8(i8 [[A:%.*]], i8 10)
 ; CHECK-NEXT:    [[B2:%.*]] = call i8 @llvm.umax.i8(i8 [[B:%.*]], i8 11)
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i8 [[A2]], [[B2]]
-; CHECK-NEXT:    ret i1 [[CMP1]]
+; CHECK-NEXT:    ret i1 true
 ;
   %a2 = call i8 @llvm.umin.i8(i8 %a, i8 10)
   %b2 = call i8 @llvm.umax.i8(i8 %b, i8 11)
   %cmp1 = icmp ult i8 %a2, %b2
   ret i1 %cmp1
 }
 
+; FIXME: Also support vectors.
 define <2 x i1> @non_const_range_minmax_vec(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @non_const_range_minmax_vec(
 ; CHECK-NEXT:    [[A2:%.*]] = call <2 x i8> @llvm.umin.v2i8(<2 x i8> [[A:%.*]], <2 x i8> <i8 10, i8 10>)
 ; CHECK-NEXT:    [[B2:%.*]] = call <2 x i8> @llvm.umax.v2i8(<2 x i8> [[B:%.*]], <2 x i8> <i8 11, i8 11>)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult <2 x i8> [[A2]], [[B2]]
 ; CHECK-NEXT:    ret <2 x i1> [[CMP1]]
 ;
   %a2 = call <2 x i8> @llvm.umin.v2i8(<2 x i8> %a, <2 x i8> <i8 10, i8 10>)

llvm/test/Transforms/CorrelatedValuePropagation/mul.ll

entry:
   ret i1 %cmp
 }
 
 define i1 @nsw_range1(i8 %b) {
 ; CHECK-LABEL: @nsw_range1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C:%.*]] = add nuw nsw i8 [[B:%.*]], -3
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i8 [[C]], 4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[C]], [[MUL]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %c = add nuw nsw i8 %b, -3
   %mul = mul nsw i8 %c, 4
   %cmp = icmp slt i8 %c, %mul
   ret i1 %cmp
 }

llvm/test/Transforms/CorrelatedValuePropagation/shl.ll

entry:
   ret i1 %cmp
 }
 
 define i1 @nsw_range1(i8 %b) {
 ; CHECK-LABEL: @nsw_range1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C:%.*]] = add nuw nsw i8 [[B:%.*]], -3
 ; CHECK-NEXT:    [[SHL:%.*]] = shl nsw i8 [[C]], 2
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[C]], [[SHL]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
 entry:
   %c = add nuw nsw i8 %b, -3
   %shl = shl nsw i8 %c, 2
   %cmp = icmp slt i8 %c, %shl
   ret i1 %cmp
 }