Fix IRBuilder.CreateFCmp(X, X) misfolding

[AndrewScheidecker]

Summary

The code incorrectly inferred that the relationship of a constant expression X to itself is FCMP_OEQ (ordered and equal), when it's actually FCMP_UEQ (unordered or equal).
This corrects that, and adds some more limited folds that can be done in this case.

[AndrewScheidecker]

Ping.

[lebedev.ri]

What i think is missing here, is that

The code incorrectly inferred that the relationship of a constant expression X to itself is FCMP_OEQ (ordered and equal), when it's actually FCMP_UEQ (unordered or equal).

simply states it as the matter of a fact.
Clearly, since this patch is here, the previous choice was wrong (i guess?).
So some more blurb with explanation as to why it is so would be good.
(i'm guessing nan / inf etc?)

[AndrewScheidecker]

Clearly, since this patch is here, the previous choice was wrong (i guess?).
So some more blurb with explanation as to why it is so would be good.
(i'm guessing nan / inf etc?)

First, I'll note that usually when trying to fold a FCmp with constant operands, the operands will be ConstantFP instead of ConstantExpr, so they'll hit the code path at ConstantFold.cpp:1789. This code path is only used when one of the operands is constant, but not a literal floating-point value, or I think this bug would be breaking lots of basic stuff. I couldn't find a way to hit this path with Clang, for example.

If V1 == V2 in evaluateFCmpRelation, you can infer that the value of V1 must be the same as the value of V2. But the value may be a NaN, in which case the relation is "unordered". So you cannot infer that the relation is ordered *and* equal, you can only infer that it must be unordered *or* equal.

The incorrectly inferred relation caused ConstantFoldCompareInstruction to fold predicate(X,X) to a literal i1 for all predicates, but it should only be possible to fold it to a literal i1 for two predicates: FCMP_ONE (ordered and not equal, which must be false) and FCMP_UEQ (unordered or equal, which must be true).

Looking at the test now, I think it might be possible to get rid of the vector->bitcast->extractelement path. When I wrote it, it was the only way I found to get an unfolded ConstantExpr through to CreateFCmp. I think it might work to bitcast a global variable pointer to a float, though.

[AndrewScheidecker]

I made the test a little simpler by bitcasting a GlobalVariable pointer to a float to get a FP typed ConstantExpr, instead of using a bitcast vector.

[lebedev.ri]

In D51216#1239501, @AndrewScheidecker wrote:

Clearly, since this patch is here, the previous choice was wrong (i guess?).
So some more blurb with explanation as to why it is so would be good.
(i'm guessing nan / inf etc?)

First, I'll note that usually when trying to fold a FCmp with constant operands, the operands will be ConstantFP instead of ConstantExpr, so they'll hit the code path at ConstantFold.cpp:1789. This code path is only used when one of the operands is constant, but not a literal floating-point value, or I think this bug would be breaking lots of basic stuff. I couldn't find a way to hit this path with Clang, for example.

If V1 == V2 in evaluateFCmpRelation, you can infer that the value of V1 must be the same as the value of V2.

But the value may be a NaN, in which case the relation is "unordered".

Hm, can we use fast-math flags here? Namely, nnan.

So you cannot infer that the relation is ordered *and* equal, you can only infer that it must be unordered *or* equal.

The incorrectly inferred relation caused ConstantFoldCompareInstruction to fold predicate(X,X) to a literal i1 for all predicates, but it should only be possible to fold it to a literal i1 for two predicates: FCMP_ONE (ordered and not equal, which must be false) and FCMP_UEQ (unordered or equal, which must be true).

Looking at the test now, I think it might be possible to get rid of the vector->bitcast->extractelement path. When I wrote it, it was the only way I found to get an unfolded ConstantExpr through to CreateFCmp. I think it might work to bitcast a global variable pointer to a float, though.

[AndrewScheidecker]

Hm, can we use fast-math flags here? Namely, nnan.

It's possible, but not a trivial change. I added a nullable const FastMathFlags* parameter to:

• evaluateFCmpRelation and ConstantFoldCompareInstruction
• ConstantExpr::getCompare and ConstantExpr::getFCmp
• TargetFolder::CreateFCmp, ConstantFolder::CreateFCmp, and NoFolder

Then, IRBuilder::CreateFCmp can pass its current FastMathFlags through to the constant folder. Most places in LLVM I saw that were calling IRBuilder::CreateFCmp seemed to be setting the FastMathFlags, but there were a few transforms that didn't seem to be propagating them through:

• foldLogicOfFCmps in InstCombineAndOrXor.cpp
• foldVectorCmp in InstCombineCompares.cpp
• foldOpIntoPhi in InstructionCombining.cpp (line 993)
• FCmpSplitter in Scalarizer.cpp
• vectorizeTree(TreeEntry*) in SLPVectorizer.cpp (line 3223)

I stopped trying to propagate the fast-math flags dependency out when I got to ConstantFolding.cpp (i.e. the constant folding pass rather than the IRBuilder constant folder). Since ConstantExpr doesn't have fast-math flags, there isn't a way to transmit the fast-math flags from whatever produced the ConstantExpr.

So I think it's doable, but beyond the scope of this change.

[AndrewScheidecker]

Ping.

[spatel]

Some IR tests added here:
rL353992
I think that's better than IRBuilder tests. Feel free to add other predicates if you think they are needed, but I think those 4 give us good coverage.

lib/IR/ConstantFold.cpp

1364 ↗

(On Diff #166176)

Can we assert that either V1 or V2 is a constant expression?
Either way, a bit more code comment (as suggested previously I think) would be helpful.
How about:

// We do not know if a constant expression will evaluate to a number or NaN.
// Therefore, we can only say that the relation is unordered or equal.

[AndrewScheidecker]

Added comment, updated the new bitcast.ll tests to reflect the fix, and removed the superfluous IRBuilder tests.

I also moved the diff from rL to rG because the old LLVM Github mirror I was using stopped updating (https://github.com/llvm-mirror/llvm).

[spatel]

LGTM - have you requested commit access?

[AndrewScheidecker]

LGTM - have you requested commit access?

I have now.

llvm/lib/IR/ConstantFold.cpp

 ///
 /// To simplify this code we canonicalize the relation so that the first
 /// operand is always the most "complex" of the two.  We consider ConstantFP
 /// to be the simplest, and ConstantExprs to be the most complex.
 static FCmpInst::Predicate evaluateFCmpRelation(Constant *V1, Constant *V2) {
   assert(V1->getType() == V2->getType() &&
          "Cannot compare values of different types!");
 
-  // Handle degenerate case quickly
-  if (V1 == V2) return FCmpInst::FCMP_OEQ;
+  // We do not know if a constant expression will evaluate to a number or NaN.
+  // Therefore, we can only say that the relation is unordered or equal.
+  if (V1 == V2) return FCmpInst::FCMP_UEQ;
 
   if (!isa<ConstantExpr>(V1)) {
     if (!isa<ConstantExpr>(V2)) {
       // Simple case, use the standard constant folder.
       ConstantInt *R = nullptr;
       R = dyn_cast<ConstantInt>(
                       ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ, V1, V2));
       if (R && !R->isZero())
if (C1->getType()->isFloatingPointTy() &&
       // Only call evaluateFCmpRelation if we have a constant expr to avoid
       // infinite recursive loop
       (isa<ConstantExpr>(C1) || isa<ConstantExpr>(C2))) {
     int Result = -1;  // -1 = unknown, 0 = known false, 1 = known true.
     switch (evaluateFCmpRelation(C1, C2)) {
     default: llvm_unreachable("Unknown relation!");
     case FCmpInst::FCMP_UNO:
     case FCmpInst::FCMP_ORD:
-    case FCmpInst::FCMP_UEQ:
     case FCmpInst::FCMP_UNE:
     case FCmpInst::FCMP_ULT:
     case FCmpInst::FCMP_UGT:
     case FCmpInst::FCMP_ULE:
     case FCmpInst::FCMP_UGE:
     case FCmpInst::FCMP_TRUE:
     case FCmpInst::FCMP_FALSE:
     case FCmpInst::BAD_FCMP_PREDICATE:
case FCmpInst::FCMP_OGE: // We known that C1 >= C2
       break;
     case FCmpInst::FCMP_ONE: // We know that C1 != C2
       // We can only partially decide this relation.
       if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ)
         Result = 0;
       else if (pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UNE)
         Result = 1;
       break;
+    case FCmpInst::FCMP_UEQ: // We know that C1 == C2 || isUnordered(C1, C2).
+      // We can only partially decide this relation.
+      if (pred == FCmpInst::FCMP_ONE)
+        Result = 0;
+      else if (pred == FCmpInst::FCMP_UEQ)
+        Result = 1;
+      break;
     }
 
     // If we evaluated the result, return it now.
     if (Result != -1)
       return ConstantInt::get(ResultTy, Result);
 
   } else {
     // Evaluate the relation between the two constants, per the predicate.

llvm/test/Transforms/ConstProp/bitcast.ll

 define i1 @bad_icmp_constexpr_bitcast() {
 ; CHECK-LABEL: @bad_icmp_constexpr_bitcast(
 ; CHECK-NEXT:    ret i1 icmp eq (float bitcast (i32 ptrtoint (i16* @a to i32) to float), float fadd (float bitcast (i32 ptrtoint (i16* @b to i32) to float), float 2.000000e+00))
 ;
   %cmp = icmp eq i32 ptrtoint (i16* @a to i32), bitcast (float fadd (float bitcast (i32 ptrtoint (i16* @b to i32) to float), float 2.0) to i32)
   ret i1 %cmp
 }
 
-; FIXME: If the bitcasts result in a NaN FP value, then "ordered and equal" would be false.
+; Ensure that an "ordered and equal" fcmp of a ConstantExpr to itself is not folded, since the ConstantExpr may be a NaN.
 
 define i1 @fcmp_constexpr_oeq(float %conv) {
 ; CHECK-LABEL: @fcmp_constexpr_oeq(
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 fcmp oeq (float bitcast (i32 ptrtoint (i16* @a to i32) to float), float bitcast (i32 ptrtoint (i16* @a to i32) to float))
 ;
   %cmp = fcmp oeq float bitcast (i32 ptrtoint (i16* @a to i32) to float), bitcast (i32 ptrtoint (i16* @a to i32) to float)
   ret i1 %cmp
 }
 
-; FIXME: If the bitcasts result in a NaN FP value, then "unordered or not equal" would be true.
+; Ensure that an "unordered or not equal" fcmp of a ConstantExpr to itself is not folded, since the ConstantExpr may be a NaN.
 
 define i1 @fcmp_constexpr_une(float %conv) {
 ; CHECK-LABEL: @fcmp_constexpr_une(
-; CHECK-NEXT:    ret i1 false
+; CHECK-NEXT:    ret i1 fcmp une (float bitcast (i32 ptrtoint (i16* @a to i32) to float), float bitcast (i32 ptrtoint (i16* @a to i32) to float))
 ;
   %cmp = fcmp une float bitcast (i32 ptrtoint (i16* @a to i32) to float), bitcast (i32 ptrtoint (i16* @a to i32) to float)
   ret i1 %cmp
 }
 
 define i1 @fcmp_constexpr_ueq(float %conv) {
 ; CHECK-LABEL: @fcmp_constexpr_ueq(
 ; CHECK-NEXT:    ret i1 true