[InstSimplify] Fold icmp with dominating assume

[nikic]

Summary

If we assume(x > y), then we should be able to fold the basic implications of that, like x >= y. This already happens if either one of the operands is constant (LVI) or if the conditions are exactly the same (CSE), but not we have an implication with non-constant operands. Support this by querying AssumptionCache.

Fixes https://bugs.llvm.org/show_bug.cgi?id=40149.

[spatel]

Can we do this in InstSimplify instead? (always folds to constant)

[nikic]

Move transform from InstCombine into InstSimplify.

[nikic]

In D82717#2125651, @spatel wrote:

Can we do this in InstSimplify instead? (always folds to constant)

Done! I have some slight compile-time apprehensions about doing this in InstSimplify. On CTMark this is barely above the noise, but that's probably just a result of little assume use in those benchmarks. But I agree that InstSimplify is logically the right place for this, and we can move it, if it becomes a problem.

[spatel]

In D82717#2126613, @nikic wrote:

In D82717#2125651, @spatel wrote:

Can we do this in InstSimplify instead? (always folds to constant)

Done! I have some slight compile-time apprehensions about doing this in InstSimplify. On CTMark this is barely above the noise, but that's probably just a result of little assume use in those benchmarks. But I agree that InstSimplify is logically the right place for this, and we can move it, if it becomes a problem.

Thanks for checking that. Yes, our icmp analysis is known to be expensive, and I remember seeing at least anecdotal evidence that using the assumption cache is also expensive.
So watch out for pushback, but LGTM.

llvm/lib/Analysis/InstructionSimplify.cpp

3287

Would it make sense to also use "Q.AC.assumptions().empty()" as an early exit?
We use that in InstCombiner::visitSelectInst() to mitigate cost for the presumed common case where there are no assumes available.

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

3287

I believe the reason why visitSelectInst() checks for assumptions().empty() is that it does not directly query the assumption cache, but goes through a known bits calculation that takes assumes into account indirectly. In this case we query the assumption cache directly, so if there are no assumes we'll just perform a lookup in an empty hash table.

I wonder if that code in visitSelectInst() is needed at all, as GVN can also perform that fold... EarlyCSE can as well, but not in all cases (as it is conditioned on "SimpleValue::canHandle").

[dmajor]

After this commit, Firefox builds crash inside the isValidAssumeForContext. I filed https://bugs.llvm.org/show_bug.cgi?id=46638.

llvm/lib/Analysis/InstructionSimplify.cpp

if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
     if (Pred == CmpInst::ICMP_UGT)
       // Always false.
       return getFalse(ITy);
   }
 
   return nullptr;
 }
 
+static Value *simplifyICmpWithDominatingAssume(CmpInst::Predicate Predicate,
+                                               Value *LHS, Value *RHS,
+                                               const SimplifyQuery &Q) {
+  if (!Q.AC || !Q.CxtI)
+    return nullptr;
+
+  for (Value *AssumeBaseOp : {LHS, RHS}) {
+    for (auto &AssumeVH : Q.AC->assumptionsFor(AssumeBaseOp)) {
+      if (!AssumeVH)
+        continue;
+
+      CallInst *Assume = cast<CallInst>(AssumeVH);
+      if (Optional<bool> Imp =
+              isImpliedCondition(Assume->getArgOperand(0), Predicate, LHS, RHS,
+                                 Q.DL))
+        if (isValidAssumeForContext(Assume, Q.CxtI, Q.DT))
+          return ConstantInt::get(GetCompareTy(LHS), *Imp);
+    }
+  }
+
+  return nullptr;
+}
+
 /// Given operands for an ICmpInst, see if we can fold the result.
 /// If not, this returns null.
 static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                                const SimplifyQuery &Q, unsigned MaxRecurse) {
   CmpInst::Predicate Pred = (CmpInst::Predicate)Predicate;
   assert(CmpInst::isIntPredicate(Pred) && "Not an integer compare!");
 
   if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
   }
 
   if (Value *V = simplifyICmpWithBinOp(Pred, LHS, RHS, Q, MaxRecurse))
     return V;
 
   if (Value *V = simplifyICmpWithMinMax(Pred, LHS, RHS, Q, MaxRecurse))
     return V;
 
+  if (Value *V = simplifyICmpWithDominatingAssume(Pred, LHS, RHS, Q))
+    return V;
+
   // Simplify comparisons of related pointers using a powerful, recursive
   // GEP-walk when we have target data available..
   if (LHS->getType()->isPointerTy())
     if (auto *C = computePointerICmp(Q.DL, Q.TLI, Q.DT, Pred, Q.AC, Q.CxtI,
                                      Q.IIQ, LHS, RHS))
       return C;
   if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
     if (auto *CRHS = dyn_cast<PtrToIntOperator>(RHS))

llvm/test/Transforms/InstSimplify/assume_icmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 declare void @llvm.assume(i1)
 declare void @use(i1)
 
 define void @basic_ugt(i32 %x, i32 %y) {
 ; CHECK-LABEL: @basic_ugt(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP1]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp uge i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP3]])
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp ule i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP5]])
-; CHECK-NEXT:    [[CMP6:%.*]] = icmp ugt i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[CMP6]])
-; CHECK-NEXT:    [[CMP7:%.*]] = icmp uge i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[CMP7]])
-; CHECK-NEXT:    [[CMP8:%.*]] = icmp ult i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[CMP8]])
-; CHECK-NEXT:    [[CMP9:%.*]] = icmp ule i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[CMP9]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ;
   %cmp1 = icmp ugt i32 %x, %y
   call void @llvm.assume(i1 %cmp1)
 
   %cmp2 = icmp ugt i32 %x, %y
   call void @use(i1 %cmp2)
   %cmp3 = icmp uge i32 %x, %y

 }
 
 define void @basic_uge(i32 %x, i32 %y) {
 ; CHECK-LABEL: @basic_uge(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp uge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP1]])
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[X]], [[Y]]
 ; CHECK-NEXT:    call void @use(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp uge i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP3]])
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP4]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[CMP5:%.*]] = icmp ule i32 [[X]], [[Y]]
 ; CHECK-NEXT:    call void @use(i1 [[CMP5]])
-; CHECK-NEXT:    [[CMP6:%.*]] = icmp ugt i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[CMP6]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[CMP7:%.*]] = icmp uge i32 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[CMP7]])
 ; CHECK-NEXT:    [[CMP8:%.*]] = icmp ult i32 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[CMP8]])
-; CHECK-NEXT:    [[CMP9:%.*]] = icmp ule i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[CMP9]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ;
   %cmp1 = icmp uge i32 %x, %y
   call void @llvm.assume(i1 %cmp1)
 
   %cmp2 = icmp ugt i32 %x, %y
   call void @use(i1 %cmp2)
   %cmp3 = icmp uge i32 %x, %y
;
   %cmp8 = icmp ult i32 %y, %x
   call void @use(i1 %cmp8)
   %cmp9 = icmp ule i32 %y, %x
   call void @use(i1 %cmp9)
 
   ret void
 }
 
+; This does not simplify in InstSimplify, because AssumptionCache tracker
+; does not track values through "and". The "and" assume will be broken
+; down into two separate assume calls by InstCombine.
 define void @and(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @and(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ugt i32 [[Z:%.*]], [[Y]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[AND]])
 ; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i32 [[X]], [[Y]]
 ; CHECK-NEXT:    call void @use(i1 [[CMP3]])