[GVN/FP] Considate logic for reasoning about equality vs equivalance for floats

[reames]

Summary

Factor out common logic into some reasonable commented helper functions. In the process, ensure that the in-block vs cross-block cases are handled the same. They previously weren't.

(Carefully review here would be appreciated. I'm by no means a floating point expert and am going solely off existing comments and LangRef.)

[xbolva00]

lib/Transforms/Scalar/GVN.cpp

1429 ↗

(On Diff #218529)

Cmp->getFastMathFlags().noSignedZeros() ?

[reames]

lib/Transforms/Scalar/GVN.cpp

1429 ↗

(On Diff #218529)

a) I just moved the todo
b) See the comment about not considering myself particularly FP knowledgeable.

[xbolva00]

lib/Transforms/Scalar/GVN.cpp

1429 ↗

(On Diff #218529)

Ok, no problem

[arsenm]

lib/Transforms/Scalar/GVN.cpp

1394 ↗

(On Diff #218529)

Spelling, equivalent

1407–1408 ↗

(On Diff #218529)

This won't handle vectors

1429 ↗

(On Diff #218529)

I think you are looking for llvm::CannotBeNegativeZero

[fhahn]

LGTM. Could you add a TODO to handle vector constants? It seems this is used on code paths that would also see vector fcmps, so it would be good to address this as follow up.

Please wait a few days with committing, in case @scanon or anyone else has any additional feedback.

test/Transforms/GVN/edge.ll

96 ↗

(On Diff #218529)

Could you add a few additional tests for ueq?

llvm/lib/Transforms/Scalar/GVN.cpp

bool GVN::processNonLocalLoad(LoadInst *LI) {
 
   // Step 4: Eliminate partial redundancy.
   if (!EnablePRE || !EnableLoadPRE)
     return false;
 
   return PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks);
 }
 
+static bool impliesEquivalanceIfTrue(CmpInst* Cmp) {
+  if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
+    return true;
+
+  // Floating point comparisons can be equal, but not equivalent.  Cases:
+  // NaNs for unordered operators
+  // +0.0 vs 0.0 for all operators
+  if (Cmp->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
+      (Cmp->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
+       Cmp->getFastMathFlags().noNaNs())) {
+      Value *LHS = Cmp->getOperand(0);
+      Value *RHS = Cmp->getOperand(1);
+      // If we can prove either side non-zero, then equality must imply
+      // equivalence.
+      // FIXME: We should do this optimization if 'no signed zeros' is
+      // applicable via an instruction-level fast-math-flag or some other
+      // indicator that relaxed FP semantics are being used.
+      if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
+        return true;
+      if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
+        return true;;
+      // TODO: Handle vector floating point constants
+  }
+  return false;
+}
+
+static bool impliesEquivalanceIfFalse(CmpInst* Cmp) {
+  if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_NE)
+    return true;
+
+  // Floating point comparisons can be equal, but not equivelent.  Cases:
+  // NaNs for unordered operators
+  // +0.0 vs 0.0 for all operators
+  if ((Cmp->getPredicate() == CmpInst::Predicate::FCMP_ONE &&
+       Cmp->getFastMathFlags().noNaNs()) ||
+      Cmp->getPredicate() == CmpInst::Predicate::FCMP_UNE) {
+      Value *LHS = Cmp->getOperand(0);
+      Value *RHS = Cmp->getOperand(1);
+      // If we can prove either side non-zero, then equality must imply
+      // equivalence. 
+      // FIXME: We should do this optimization if 'no signed zeros' is
+      // applicable via an instruction-level fast-math-flag or some other
+      // indicator that relaxed FP semantics are being used.
+      if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
+        return true;
+      if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
+        return true;;
+      // TODO: Handle vector floating point constants
+  }
+  return false;
+}
+
+
 static bool hasUsersIn(Value *V, BasicBlock *BB) {
   for (User *U : V->users())
     if (isa<Instruction>(U) &&
         cast<Instruction>(U)->getParent() == BB)
       return true;
   return false;
 }
 
bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) {
   // call void @llvm.assume(i1 %cmp)
   // ret float %0 ; will change it to ret float 3.000000e+00
   // 2)
   // %load = load float, float* %addr
   // %cmp = fcmp oeq float %load, %0
   // call void @llvm.assume(i1 %cmp)
   // ret float %load ; will change it to ret float %0
   if (auto *CmpI = dyn_cast<CmpInst>(V)) {
-    if (CmpI->getPredicate() == CmpInst::Predicate::ICMP_EQ ||
-        CmpI->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
-        (CmpI->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
-         CmpI->getFastMathFlags().noNaNs())) {
+    if (impliesEquivalanceIfTrue(CmpI)) {
       Value *CmpLHS = CmpI->getOperand(0);
       Value *CmpRHS = CmpI->getOperand(1);
       // Heuristically pick the better replacement -- the choice of heuristic
       // isn't terribly important here, but the fact we canonicalize on some
       // replacement is for exposing other simplifications.
       // TODO: pull this out as a helper function and reuse w/existing
       // (slightly different) logic.
       if (isa<Constant>(CmpLHS) && !isa<Constant>(CmpRHS))
if (impliesEquivalanceIfTrue(CmpI)) {
           std::swap(CmpLHS, CmpRHS);
       }
 
       // Handle degenerate case where we either haven't pruned a dead path or a
       // removed a trivial assume yet.
       if (isa<Constant>(CmpLHS) && isa<Constant>(CmpRHS))
         return Changed;
 
-      // +0.0 and -0.0 compare equal, but do not imply equivalence.  Unless we
-      // can prove equivalence, bail.
-      if (CmpRHS->getType()->isFloatTy() &&
-          (!isa<ConstantFP>(CmpRHS) || cast<ConstantFP>(CmpRHS)->isZero()))
-        return Changed;
-
       LLVM_DEBUG(dbgs() << "Replacing dominated uses of "
                  << *CmpLHS << " with "
                  << *CmpRHS << " in block "
                  << IntrinsicI->getParent()->getName() << "\n");
       
 
       // Setup the replacement map - this handles uses within the same block
       if (hasUsersIn(CmpLHS, IntrinsicI->getParent()))
while (!Worklist.empty()) {
 
     // If we are propagating an equality like "(A == B)" == "true" then also
     // propagate the equality A == B.  When propagating a comparison such as
     // "(A >= B)" == "true", replace all instances of "A < B" with "false".
     if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
       Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
 
       // If "A == B" is known true, or "A != B" is known false, then replace
-      // A with B everywhere in the scope.
-      if ((isKnownTrue && Cmp->getPredicate() == CmpInst::ICMP_EQ) ||
-          (isKnownFalse && Cmp->getPredicate() == CmpInst::ICMP_NE))
+      // A with B everywhere in the scope.  For floating point operations, we
+      // have to be careful since equality does not always imply equivalance.  
+      if ((isKnownTrue && impliesEquivalanceIfTrue(Cmp)) ||
+          (isKnownFalse && impliesEquivalanceIfFalse(Cmp)))
         Worklist.push_back(std::make_pair(Op0, Op1));
 
-      // Handle the floating point versions of equality comparisons too.
-      if ((isKnownTrue && Cmp->getPredicate() == CmpInst::FCMP_OEQ) ||
-          (isKnownFalse && Cmp->getPredicate() == CmpInst::FCMP_UNE)) {
-
-        // Floating point -0.0 and 0.0 compare equal, so we can only
-        // propagate values if we know that we have a constant and that
-        // its value is non-zero.
-
-        // FIXME: We should do this optimization if 'no signed zeros' is
-        // applicable via an instruction-level fast-math-flag or some other
-        // indicator that relaxed FP semantics are being used.
-
-        if (isa<ConstantFP>(Op1) && !cast<ConstantFP>(Op1)->isZero())
-          Worklist.push_back(std::make_pair(Op0, Op1));
-      }
-
       // If "A >= B" is known true, replace "A < B" with false everywhere.
       CmpInst::Predicate NotPred = Cmp->getInversePredicate();
       Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
       // Since we don't have the instruction "A < B" immediately to hand, work
       // out the value number that it would have and use that to find an
       // appropriate instruction (if any).
       uint32_t NextNum = VN.getNextUnusedValueNumber();
       uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);

llvm/test/Transforms/GVN/edge.ll

 return:
   %retval = phi double [ %div, %else ], [ %x, %entry ]
   ret double %retval
 
 ; CHECK-LABEL: define double @fcmp_une_not_zero(
 ; CHECK: %div = fdiv double %x, 2.0
 }
 
+define double @fcmp_one_possibly_nan(double %x, double %y) {
+entry:
+  %cmp = fcmp one double %y, 2.0
+  br i1 %cmp, label %return, label %else
+
+else:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %else ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_one_possibly_nan(
+; CHECK: %div = fdiv double %x, %y
+}
+
+define double @fcmp_one_not_zero_or_nan(double %x, double %y) {
+entry:
+  %cmp = fcmp nnan one double %y, 2.0
+  br i1 %cmp, label %return, label %else
+
+else:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %else ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_one_not_zero_or_nan(
+; CHECK: %div = fdiv double %x, 2.0
+}
+
 ; PR22376 - We can't propagate zero constants because -0.0 
 ; compares equal to 0.0. If %y is -0.0 in this test case,
 ; we would produce the wrong sign on the infinity return value.
 define double @fcmp_oeq_zero(double %x, double %y) {
 entry:
   %cmp = fcmp oeq double %y, 0.0
   br i1 %cmp, label %if, label %return
 

 
 return:
  %retval = phi double [ %div, %else ], [ %x, %entry ]
  ret double %retval
 
 ; CHECK-LABEL: define double @fcmp_une_maybe_zero(
 ; CHECK: %div = fdiv double %x, %z
 }
+
+
+define double @fcmp_ueq_possibly_nan(double %x, double %y) {
+entry:
+  %cmp = fcmp ueq double %y, 2.0
+  br i1 %cmp, label %do_div, label %return
+
+do_div:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %do_div ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_ueq_possibly_nan(
+; CHECK: %div = fdiv double %x, %y
+}
+
+define double @fcmp_ueq_not_zero_or_nan(double %x, double %y) {
+entry:
+  %cmp = fcmp nnan ueq double %y, 2.0
+  br i1 %cmp, label %do_div, label %return
+
+do_div:
+  %div = fdiv double %x, %y
+  br label %return
+
+return:
+  %retval = phi double [ %div, %do_div ], [ %x, %entry ]
+  ret double %retval
+
+; CHECK-LABEL: define double @fcmp_ueq_not_zero_or_nan(
+; CHECK: %div = fdiv double %x, 2.0
+}