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

(On Diff #274926)

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 ↗

(On Diff #274926)

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/Transforms/InstCombine/InstCombineCompares.cpp

 //===- InstCombineCompares.cpp --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitICmp and visitFCmp functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/APSInt.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
if (const APInt *EqC = Intersection.getSingleElement())
       return new ICmpInst(ICmpInst::ICMP_EQ, X, Builder.getInt(*EqC));
     if (const APInt *NeC = Difference.getSingleElement())
       return new ICmpInst(ICmpInst::ICMP_NE, X, Builder.getInt(*NeC));
   }
 
   return nullptr;
 }
 
+Instruction *InstCombiner::foldICmpWithDominatingAssume(ICmpInst &ICmp,
+                                                        Value *Op) {
+  for (auto &AssumeVH : AC.assumptionsFor(Op)) {
+    if (!AssumeVH)
+      continue;
+
+    CallInst *Assume = cast<CallInst>(AssumeVH);
+    if (Optional<bool> Imp = isImpliedCondition(Assume->getArgOperand(0), &ICmp,
+                                                DL))
+      if (isValidAssumeForContext(Assume, &ICmp, &DT))
+        return replaceInstUsesWith(ICmp,
+                                   ConstantInt::get(ICmp.getType(), *Imp));
+  }
+
+  return nullptr;
+}
+
 /// Fold icmp (trunc X, Y), C.
 Instruction *InstCombiner::foldICmpTruncConstant(ICmpInst &Cmp,
                                                  TruncInst *Trunc,
                                                  const APInt &C) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();
   Value *X = Trunc->getOperand(0);
   if (C.isOneValue() && C.getBitWidth() > 1) {
     // icmp slt trunc(signum(V)) 1 --> icmp slt V, 1
Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
 
   if (Instruction *Res = foldICmpWithHighBitMask(I, Builder))
     return Res;
 
   if (I.getType()->isVectorTy())
     if (Instruction *Res = foldVectorCmp(I, Builder))
       return Res;
 
+  if (Instruction *Res = foldICmpWithDominatingAssume(I, Op0))
+    return Res;
+  if (Instruction *Res = foldICmpWithDominatingAssume(I, Op1))
+    return Res;
+
   return Changed ? &I : nullptr;
 }
 
 /// Fold fcmp ([us]itofp x, cst) if possible.
 Instruction *InstCombiner::foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
                                                 Constant *RHSC) {
   if (!isa<ConstantFP>(RHSC)) return nullptr;
   const APFloat &RHS = cast<ConstantFP>(RHSC)->getValueAPF();

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
                                     Constant *RHSC);
   Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
                                   ICmpInst::Predicate Pred);
   Instruction *foldICmpWithCastOp(ICmpInst &ICI);
 
   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
   Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
+  Instruction *foldICmpWithDominatingAssume(ICmpInst &Cmp, Value *Op);
   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
   Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
   Instruction *foldICmpEquality(ICmpInst &Cmp);
   Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
   Instruction *foldSignBitTest(ICmpInst &I);
   Instruction *foldICmpWithZero(ICmpInst &Cmp);

llvm/test/Transforms/InstCombine/assume_icmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -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

 }
 
 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:    call void @llvm.assume(i1 [[CMP1]])
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP2]])
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp ugt i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP3]])
-; CHECK-NEXT:    [[CMP4:%.*]] = icmp uge i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP4]])
-; CHECK-NEXT:    [[CMP5:%.*]] = icmp ugt i32 [[Z]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP5]])
-; CHECK-NEXT:    [[CMP6:%.*]] = icmp uge i32 [[Z]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[CMP6]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ;
   %cmp1 = icmp ugt i32 %x, %y
   %cmp2 = icmp ugt i32 %z, %y
   %and = and i1 %cmp1, %cmp2
   call void @llvm.assume(i1 %and)
 
   %cmp3 = icmp ugt i32 %x, %y