[InstSimplify] Fold fcmp with dominating assume

[cppio]

Summary

Fold float comparisons like x >= y after assume(x > y). This treats fcmp like icmp, which already has this optimization.

[nikic]

@spatel seems to be doing work in this area right now...

[spatel]

This looks right. I made some cosmetic changes to this code in the last day (hopefully easier to read), so you'll need to rebase/update.

Please add the new tests with baseline (current) output to D131168. That way, we'll show the diffs in this patch.

It would be good to confirm that everything checks out with Alive2 as well. I don't know of any programmatic way to cycle through the predicates, but you can verify by pasting in the before/after IR for these (and possibly more) tests:
https://alive2.llvm.org/ce/z/5EEWrF

llvm/lib/Analysis/ValueTracking.cpp

6761

Shorten:

if (auto *LHSCmp = dyn_cast<CmpInst>(LHS))
  return isImplied...

6784

Similar to above: use "auto *" here to reduce code.

llvm/lib/Analysis/AssumptionCache.cpp

if (CI->getOperandBundleAt(Idx).Inputs.size() > ABA_WasOn &&
         CI->getOperandBundleAt(Idx).getTagName() != IgnoreBundleTag)
       AddAffected(CI->getOperandBundleAt(Idx).Inputs[ABA_WasOn], Idx);
   }
 
   Value *Cond = CI->getArgOperand(0), *A, *B;
   AddAffected(Cond);
 
   CmpInst::Predicate Pred;
-  if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
+  if (match(Cond, m_Cmp(Pred, m_Value(A), m_Value(B)))) {
     AddAffected(A);
     AddAffected(B);
 
-    if (Pred == ICmpInst::ICMP_EQ) {
+    if (Pred == CmpInst::ICMP_EQ) {
       // For equality comparisons, we handle the case of bit inversion.
       auto AddAffectedFromEq = [&AddAffected](Value *V) {
         Value *A;
         if (match(V, m_Not(m_Value(A)))) {
           AddAffected(A);
           V = A;
         }
 
if (Pred == CmpInst::ICMP_EQ) {
 
       AddAffectedFromEq(A);
       AddAffectedFromEq(B);
     }
 
     Value *X;
     // Handle (A + C1) u< C2, which is the canonical form of A > C3 && A < C4,
     // and recognized by LVI at least.
-    if (Pred == ICmpInst::ICMP_ULT &&
+    if (Pred == CmpInst::ICMP_ULT &&
         match(A, m_Add(m_Value(X), m_ConstantInt())) &&
         match(B, m_ConstantInt()))
       AddAffected(X);
   }
 
   if (TTI) {
     const Value *Ptr;
     unsigned AS;

llvm/lib/Analysis/InstructionSimplify.cpp

if (match(LHS, m_SMax(m_Value(A), m_Value(B))) &&
     // umax(A, B) <u umin(A, D) --> false
     if (Pred == CmpInst::ICMP_ULT)
       return getFalse(ITy);
   }
 
   return nullptr;
 }
 
-static Value *simplifyICmpWithDominatingAssume(CmpInst::Predicate Predicate,
-                                               Value *LHS, Value *RHS,
-                                               const SimplifyQuery &Q) {
+static Value *simplifyCmpWithDominatingAssume(CmpInst::Predicate Predicate,
   // Gracefully handle instructions that have not been inserted yet.
   if (!Q.AC || !Q.CxtI || !Q.CxtI->getParent())
     return nullptr;
 
   for (Value *AssumeBaseOp : {LHS, RHS}) {
     for (auto &AssumeVH : Q.AC->assumptionsFor(AssumeBaseOp)) {
       if (!AssumeVH)
         continue;
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))
+  if (Value *V = simplifyCmpWithDominatingAssume(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(Pred, LHS, RHS, Q))
       return C;
   if (auto *CLHS = dyn_cast<PtrToIntOperator>(LHS))
case FCmpInst::FCMP_OLT:
       if (CannotBeOrderedLessThanZero(LHS, Q.TLI))
         return Pred == FCmpInst::FCMP_UGE ? getTrue(RetTy) : getFalse(RetTy);
       break;
     default:
       break;
     }
   }
 
+  if (Value *V = simplifyCmpWithDominatingAssume(Pred, LHS, RHS, Q))
+    return V;
+
   // If the comparison is with the result of a select instruction, check whether
   // comparing with either branch of the select always yields the same value.
   if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
     if (Value *V = threadCmpOverSelect(Pred, LHS, RHS, Q, MaxRecurse))
       return V;
 
   // If the comparison is with the result of a phi instruction, check whether
   // doing the compare with each incoming phi value yields a common result.

llvm/lib/Analysis/ValueTracking.cpp

case CmpInst::ICMP_ULE: {
     if (MatchNUWAddsToSameValue(LHS, RHS, X, CLHS, CRHS))
       return CLHS->ule(*CRHS);
 
     return false;
   }
   }
 }
 
-/// Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred
+/// Return true if "cmp Pred BLHS BRHS" is true whenever "cmp Pred
 /// ALHS ARHS" is true.  Otherwise, return None.
 static Optional<bool>
 isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS,
                       const Value *ARHS, const Value *BLHS, const Value *BRHS,
                       const DataLayout &DL, unsigned Depth) {
   switch (Pred) {
   default:
     return None;
static bool isMatchingOps(const Value *ALHS, const Value *ARHS,
                           const Value *BLHS, const Value *BRHS,
                           bool &IsSwappedOps) {
 
   bool IsMatchingOps = (ALHS == BLHS && ARHS == BRHS);
   IsSwappedOps = (ALHS == BRHS && ARHS == BLHS);
   return IsMatchingOps || IsSwappedOps;
 }
 
-/// Return true if "icmp1 APred X, Y" implies "icmp2 BPred X, Y" is true.
-/// Return false if "icmp1 APred X, Y" implies "icmp2 BPred X, Y" is false.
+/// Return true if "cmp1 APred X, Y" implies "cmp2 BPred X, Y" is true.
+/// Return false if "cmp1 APred X, Y" implies "cmp2 BPred X, Y" is false.
 /// Otherwise, return None if we can't infer anything.
 static Optional<bool> isImpliedCondMatchingOperands(CmpInst::Predicate APred,
                                                     CmpInst::Predicate BPred,
                                                     bool AreSwappedOps) {
   // Canonicalize the predicate as if the operands were not commuted.
   if (AreSwappedOps)
-    BPred = ICmpInst::getSwappedPredicate(BPred);
+    BPred = CmpInst::getSwappedPredicate(BPred);
 
   if (CmpInst::isImpliedTrueByMatchingCmp(APred, BPred))
     return true;
   if (CmpInst::isImpliedFalseByMatchingCmp(APred, BPred))
     return false;
 
   return None;
 }
if (Intersection.isEmptySet())
     return false;
   if (Difference.isEmptySet())
     return true;
   return None;
 }
 
 /// Return true if LHS implies RHS is true.  Return false if LHS implies RHS is
 /// false.  Otherwise, return None if we can't infer anything.
-static Optional<bool> isImpliedCondICmps(const ICmpInst *LHS,
-                                         CmpInst::Predicate BPred,
-                                         const Value *BLHS, const Value *BRHS,
-                                         const DataLayout &DL, bool LHSIsTrue,
-                                         unsigned Depth) {
+static Optional<bool> isImpliedCondCmps(const CmpInst *LHS,
   Value *ALHS = LHS->getOperand(0);
   Value *ARHS = LHS->getOperand(1);
 
   // The rest of the logic assumes the LHS condition is true.  If that's not the
   // case, invert the predicate to make it so.
   CmpInst::Predicate APred =
       LHSIsTrue ? LHS->getPredicate() : LHS->getInversePredicate();
 
static Optional<bool> isImpliedCondCmps(const CmpInst *LHS,
 
   if (APred == BPred)
     return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth);
   return None;
 }
 
 /// Return true if LHS implies RHS is true.  Return false if LHS implies RHS is
 /// false.  Otherwise, return None if we can't infer anything.  We expect the
-/// RHS to be an icmp and the LHS to be an 'and', 'or', or a 'select' instruction.
+/// LHS to be an 'and', 'or', or a 'select' instruction.
 static Optional<bool>
 isImpliedCondAndOr(const Instruction *LHS, CmpInst::Predicate RHSPred,
                    const Value *RHSOp0, const Value *RHSOp1,
                    const DataLayout &DL, bool LHSIsTrue, unsigned Depth) {
   // The LHS must be an 'or', 'and', or a 'select' instruction.
   assert((LHS->getOpcode() == Instruction::And ||
           LHS->getOpcode() == Instruction::Or ||
           LHS->getOpcode() == Instruction::Select) &&
llvm::isImpliedCondition(const Value *LHS, CmpInst::Predicate RHSPred,
   // A mismatch occurs when we compare a scalar cmp to a vector cmp, for
   // example.
   if (RHSOp0->getType()->isVectorTy() != LHS->getType()->isVectorTy())
     return None;
 
   assert(LHS->getType()->isIntOrIntVectorTy(1) &&
          "Expected integer type only!");
 
-  // Both LHS and RHS are icmps.
-  const ICmpInst *LHSCmp = dyn_cast<ICmpInst>(LHS);
+  // Both LHS and RHS are cmps.
+  const CmpInst *LHSCmp = dyn_cast<CmpInst>(LHS);
   if (LHSCmp)
-    return isImpliedCondICmps(LHSCmp, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue,
-                              Depth);
+    return isImpliedCondCmps(LHSCmp, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue,
 
-  /// The LHS should be an 'or', 'and', or a 'select' instruction.  We expect
-  /// the RHS to be an icmp.
-  /// FIXME: Add support for and/or/select on the RHS.
+  /// The LHS should be an 'or', 'and', or a 'select' instruction.
   if (const Instruction *LHSI = dyn_cast<Instruction>(LHS)) {
     if ((LHSI->getOpcode() == Instruction::And ||
          LHSI->getOpcode() == Instruction::Or ||
          LHSI->getOpcode() == Instruction::Select))
       return isImpliedCondAndOr(LHSI, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue,
                                 Depth);
   }
   return None;
 }
 
 Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS,
                                         const DataLayout &DL, bool LHSIsTrue,
                                         unsigned Depth) {
   // LHS ==> RHS by definition
   if (LHS == RHS)
     return LHSIsTrue;
 
-  if (const ICmpInst *RHSCmp = dyn_cast<ICmpInst>(RHS))
+  if (const CmpInst *RHSCmp = dyn_cast<CmpInst>(RHS))
     return isImpliedCondition(LHS, RHSCmp->getPredicate(),
                               RHSCmp->getOperand(0), RHSCmp->getOperand(1), DL,
                               LHSIsTrue, Depth);
 
   if (Depth == MaxAnalysisRecursionDepth)
     return None;
 
   // LHS ==> (RHS1 || RHS2) if LHS ==> RHS1 or LHS ==> RHS2

llvm/lib/IR/Instructions.cpp

case ICMP_UGT: // A >u B implies A != B and A >=u B are true.
     return Pred2 == ICMP_NE || Pred2 == ICMP_UGE;
   case ICMP_ULT: // A <u B implies A != B and A <=u B are true.
     return Pred2 == ICMP_NE || Pred2 == ICMP_ULE;
   case ICMP_SGT: // A >s B implies A != B and A >=s B are true.
     return Pred2 == ICMP_NE || Pred2 == ICMP_SGE;
   case ICMP_SLT: // A <s B implies A != B and A <=s B are true.
     return Pred2 == ICMP_NE || Pred2 == ICMP_SLE;
   }
+
+  // Since fcmp predicates act as bitsets, the first condition implies the
+  // second when the first is a subset of the second.
+  if (isFPPredicate(Pred1) && isFPPredicate(Pred2))
+    return (Pred1 & Pred2) == Pred1;
+
   return false;
 }
 
 bool CmpInst::isImpliedFalseByMatchingCmp(Predicate Pred1, Predicate Pred2) {
   return isImpliedTrueByMatchingCmp(Pred1, getInversePredicate(Pred2));
 }
 
 //===----------------------------------------------------------------------===//

llvm/test/Transforms/InstSimplify/assume_cmp.ll

;
   call void @use(i1 %cmp4)
   %cmp5 = icmp ugt i32 %z, %y
   call void @use(i1 %cmp5)
   %cmp6 = icmp uge i32 %z, %y
   call void @use(i1 %cmp6)
 
   ret void
 }
+
+define void @fcmp_ogt(float %x, float %y) {
+; CHECK-LABEL: @fcmp_ogt(
+; CHECK-NEXT:    [[CMP1:%.*]] = fcmp ogt float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; 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 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 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 true)
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = fcmp ogt float %x, %y
+  call void @llvm.assume(i1 %cmp1)
+
+  %cmp2 = fcmp oeq float %x, %y
+  call void @use(i1 %cmp2)
+  %cmp3 = fcmp ogt float %x, %y
+  call void @use(i1 %cmp3)
+  %cmp4 = fcmp oge float %x, %y
+  call void @use(i1 %cmp4)
+  %cmp5 = fcmp olt float %x, %y
+  call void @use(i1 %cmp5)
+  %cmp6 = fcmp ole float %x, %y
+  call void @use(i1 %cmp6)
+  %cmp7 = fcmp one float %x, %y
+  call void @use(i1 %cmp7)
+  %cmp8 = fcmp ord float %x, %y
+  call void @use(i1 %cmp8)
+  %cmp9 = fcmp uno float %x, %y
+  call void @use(i1 %cmp9)
+  %cmp10 = fcmp ueq float %x, %y
+  call void @use(i1 %cmp10)
+  %cmp11 = fcmp ugt float %x, %y
+  call void @use(i1 %cmp11)
+  %cmp12 = fcmp uge float %x, %y
+  call void @use(i1 %cmp12)
+  %cmp13 = fcmp ult float %x, %y
+  call void @use(i1 %cmp13)
+  %cmp14 = fcmp ule float %x, %y
+  call void @use(i1 %cmp14)
+  %cmp15 = fcmp une float %x, %y
+  call void @use(i1 %cmp15)
+
+  ret void
+}
+
+define void @fcmp_ueq(float %x, float %y) {
+; CHECK-LABEL: @fcmp_ueq(
+; CHECK-NEXT:    [[CMP1:%.*]] = fcmp ueq float [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP1]])
+; CHECK-NEXT:    [[CMP2:%.*]] = fcmp oeq float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    [[CMP4:%.*]] = fcmp oge float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP4]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    [[CMP6:%.*]] = fcmp ole float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP6]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    [[CMP8:%.*]] = fcmp ord float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP8]])
+; CHECK-NEXT:    [[CMP9:%.*]] = fcmp uno float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP9]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    [[CMP11:%.*]] = fcmp ugt float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP11]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    [[CMP13:%.*]] = fcmp ult float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP13]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    [[CMP15:%.*]] = fcmp une float [[X]], [[Y]]
+; CHECK-NEXT:    call void @use(i1 [[CMP15]])
+; CHECK-NEXT:    ret void
+;
+  %cmp1 = fcmp ueq float %x, %y
+  call void @llvm.assume(i1 %cmp1)
+
+  %cmp2 = fcmp oeq float %x, %y
+  call void @use(i1 %cmp2)
+  %cmp3 = fcmp ogt float %x, %y
+  call void @use(i1 %cmp3)
+  %cmp4 = fcmp oge float %x, %y
+  call void @use(i1 %cmp4)
+  %cmp5 = fcmp olt float %x, %y
+  call void @use(i1 %cmp5)
+  %cmp6 = fcmp ole float %x, %y
+  call void @use(i1 %cmp6)
+  %cmp7 = fcmp one float %x, %y
+  call void @use(i1 %cmp7)
+  %cmp8 = fcmp ord float %x, %y
+  call void @use(i1 %cmp8)
+  %cmp9 = fcmp uno float %x, %y
+  call void @use(i1 %cmp9)
+  %cmp10 = fcmp ueq float %x, %y
+  call void @use(i1 %cmp10)
+  %cmp11 = fcmp ugt float %x, %y
+  call void @use(i1 %cmp11)
+  %cmp12 = fcmp uge float %x, %y
+  call void @use(i1 %cmp12)
+  %cmp13 = fcmp ult float %x, %y
+  call void @use(i1 %cmp13)
+  %cmp14 = fcmp ule float %x, %y
+  call void @use(i1 %cmp14)
+  %cmp15 = fcmp une float %x, %y
+  call void @use(i1 %cmp15)
+
+  ret void
+}