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

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.

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;
+  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.

unittests/IR/IRBuilderTest.cpp

TEST_F(IRBuilderTest, DIBuilderMacro) {
   EXPECT_EQ(MN1, MF1->getRawElements());
 
   Elements.clear();
   Elements.push_back(MDef2);
   auto MN2 = MDTuple::get(Ctx, Elements);
   EXPECT_EQ(MN2, MF2->getRawElements());
   EXPECT_TRUE(verifyModule(*M));
 }
+
+TEST_F(IRBuilderTest, FCmpFolding) {
+  IRBuilder<> Builder(BB);
+
+  // Create a FP ConstantExpr by bitcasting the address of a global variable.
+  auto I32 = ConstantExpr::getPtrToInt(GV, Type::getInt32Ty(Ctx));
+  auto F32 = ConstantExpr::getBitCast(I32, Type::getFloatTy(Ctx));
+  EXPECT_TRUE(isa<ConstantExpr>(F32));
+
+  auto FCmpOEQ = Builder.CreateFCmpOEQ(F32, F32);
+  auto FCmpOGT = Builder.CreateFCmpOGT(F32, F32);
+  auto FCmpOGE = Builder.CreateFCmpOGE(F32, F32);
+  auto FCmpOLT = Builder.CreateFCmpOLT(F32, F32);
+  auto FCmpOLE = Builder.CreateFCmpOLE(F32, F32);
+  auto FCmpONE = Builder.CreateFCmpONE(F32, F32);
+  auto FCmpORD = Builder.CreateFCmpORD(F32, F32);
+  auto FCmpUEQ = Builder.CreateFCmpUEQ(F32, F32);
+  auto FCmpUGT = Builder.CreateFCmpUGT(F32, F32);
+  auto FCmpUGE = Builder.CreateFCmpUGE(F32, F32);
+  auto FCmpULT = Builder.CreateFCmpULT(F32, F32);
+  auto FCmpULE = Builder.CreateFCmpULE(F32, F32);
+  auto FCmpUNE = Builder.CreateFCmpUNE(F32, F32);
+  auto FCmpUNO = Builder.CreateFCmpUNO(F32, F32);
+
+  // Assuming that the bitcast vector produced a constant expression rather than
+  // a constant, the folder should only be able to infer a constant value for
+  // FCMP_ONE (ordered and not-equal) and FCMP_UEQ (unordered or equal).
+  EXPECT_EQ(FCmpONE, ConstantInt::getFalse(Type::getInt1Ty(Ctx)));
+  EXPECT_EQ(FCmpUEQ, ConstantInt::getTrue(Type::getInt1Ty(Ctx)));
+
+  EXPECT_FALSE(isa<ConstantInt>(FCmpOEQ));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpOGT));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpOGE));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpOLT));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpOLE));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpORD));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpUNE));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpUGT));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpUGE));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpULT));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpULE));
+  EXPECT_FALSE(isa<ConstantInt>(FCmpUNO));
+}
 }