Broaden FoldItoFPtoI to try and establish whether the integer value fits into the float type

[aarzee]

Summary

Previously, FoldItoFPtoI would only check if the width of the integer type fits into the width of the mantissa. This change will now let it fold if it can establish that the actual value of the integer fits within the floating point type (considering mantissa and exponent).

Was originally D19177, but was notified on IRC that since I didn't add llvm-commits as a subscriber, it wouldn't show up on that list.

[deadalnix]

Wouldn't it make sense to add a test also for case where it is NOT safe to fold ?

[aarzee]

In D19178#402921, @deadalnix wrote:

Wouldn't it make sense to add a test also for case where it is NOT safe to fold ?

That should be covered by the existing tests, namely 13, 17, and 19.

[aarzee]

Fix typo in test (CHECK-NEST -> CHECK-NEXT)

[aarzee]

Any feedback on this?

[reames]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1423

The second part of this comment doesn't make any sense to me. I can understand why an integer value of less than mantissa size (actual bits uses) could be converted lossly to and from a floating point type. Why does the exponent come into this? Are you trying to reason about integer values larger than the mantissa with precise representations in floating point?

If so, could I ask that you split this into two patches:

1. Handle just the mantissa case.
2. Extend it to the full complexity.

Doing it that way would make it far more obvious what's going on. I would personally be comfortable signing off on the former, but would not be on the later.

Also, extracting out a helper function called something like "hasPreciseFPRepresentation" would make this code far more clear. (If I'm actually understanding it correctly at all!)

test/Transforms/InstCombine/sitofp.ll

191

FYI, you're going to need a lot more test cases to convince me this is correct. Even for the split patch.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1423

Yes, that's what I'm doing.

The exponent comes into play because (for example) (2 ** 24 - 1) << 10 has 23 significant bits, which fits into the mantissa, but has 9 leading zeroes, which is too large for the exponent (8 bits).

Could you be more specific about the splitting of the patch? I'm not sure what you mean by 'just the mantissa case' - if you mean the integer fits into the mantissa without any exponent, that's what FoldItoFPtoI already does, but based on bit-width of the integer type, not the integer value.

[aarzee]

Made the code shorter and more concise, added some comments, added a new test. For some reason I'm having an issue building LLVM so I wasn't able to personally verify that this works as intended / at all.

[aarzee]

Highest possible trailing zeros was off by one (exponent is either unsigned or biased, with non-negative values ranging from 0 to 2^(x - 1), where x is the bit width of the exponent).

[reames]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1423

I was suggesting that you first post a patch which implements this optimization for integers which can be represented in floating point without scaling (i.e. without using the exponent for anything non-trivial). Once that's in, the scaling part of the change becomes far easier to reason about in isolation.

To be clear, I am not going to sign off on the change in its current form. I don't understand floating point deeply enough to reason it in this way. You're welcome to find an alternate reviewer, but if you want a LGTM from me, splitting it is going to be required.

[aarzee]

Made the change suggested by @reames to only consider the mantissa. Scaling and exponent is no longer considered. Should be more easily verifiable.

[aarzee]

FWIW I still believe that Diff 2 is (at least close to) correct, and I'd still like to pursue implementing it.

[aarzee]

I've attached a file containing the latest version of the full proposed patch as well as a Python 3 script to test and verify whether the optimization is applied correctly. It requires a bit of editing, as shown in the top and bottom of the script. It's supposed to write any failed generated IR to exN.ll (where N is some number), but I'm not sure whether it actually does. Python's multiprocessing module is finicky. Note that you must use a floating point type that is supported by the platform you're on (I tried 'half' on x86-64 and got weird results because it was legalized to a float).

patch3.txt92 KBDownload

floattestgen.py4 KBDownload

[reames]

Comments inline.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1464

This isn't what you want. In particular, this doesn't produce a useful answer for any (known) positive number since you'll immediately exit the loop.

A better approach here is to look for a prefix which is known to be either zero or one. (i.e. 0000 or 1111, not 0101.) For a signed number, you can simply drop those bits entirely since the sign is encoded separately. For an unsigned, you can only drop a zero prefix. This can be written easily using countNumberOfLeadingX

test/Transforms/InstCombine/sitofp.ll

192

Absolutely minimum testing you're going to need:
sitofp positive number in and out of range
sitofp negative number in and out of range
uitofp number in and out of range

All in the form of LIT tests.

[aarzee]

I've decided to go ahead and submit the full change (considering exponent as well as mantissa) and I've added a few more tests as @reames suggested.

[mcrosier]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1452

How about:

bool Safe = ActualSize <= MantissaWidth;

// Compute known bits to see if the integer value fits into the fp type.
if (!Safe) {
  ...
}

if (Safe) {
  ...

Note: Local variables should be capitalized.

1474

Please capitalize Only and add a period.

http://llvm.org/docs/CodingStandards.html#commenting

[aarzee]

Replace for loops with count{Leading,Trailing}{Zeros,Ones}.

[aarzee]

Added the changes suggested by @mcrosier.

[aarzee]

Same as last diff except that I didn't rush through without actually reading the comment.

[reames]

Previous advice is being actively ignored and outside of my expertise. If anyone else wants to review feel free, I don't have the time to cycle on this.

[scanon]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1423

A few things:

1. This:

and that the number of trailing zeros fits into the exponent

is really confused. That's not how it [floating-point encoding] works at all. A correct algorithm for determining if an integer n can be exactly represented is (pseudocode):

m = absoluteValue(n)
i = mostSignificantNonzeroBit(m)
j = leastSignificantNonzeroBit(m)
if (i - j < numberOfSignificandBits) {
  // significand is representable, check exponent
  if (i <= greatestFiniteExponent) {
    // number can be exactly represented
  }
}
// number cannot be exactly represented

In particular, if we look at your example, (2 ** 24 - 1) << 10, this number absolutely is exactly representable in single-precision. We have:

m = 2**24-1 << 10
i = 33
j = 10
i-j = 23 < numberOfSignificandBits = 24
i = 33 <= greatestFiniteExponent = 127.

2. Please don't use the term "mantissa". It is frequently used, even in the LLVM sources, but it is subtly wrong (https://en.wikipedia.org/wiki/Significand#Use_of_.22mantissa.22). The correct term is "significand"; any new written code should use that instead.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1423

Shouldn't it be j <= greatestFiniteExponent? (I'm clearly not an expert here, so I just wanted to check).

[scanon]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1423

No, it should be i. Normal binary floating-point numbers have the form +/- significand * 2^exponent, where significand is a number in [1,2). Thus, the MSB a representable integer is always 2^exponent.

[aarzee]

Updated variable names and improved correctness.

[aarzee]

Question re: usage of 'mantissa' vs 'significand' - should getFPMantissaWidth be renamed?

[aarzee]

Ping.

[eli.friedman]

Needs more comments in the code, and more tests. In particular, you have zero tests of values with trailing zeros.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1465

Why are you subtracting one here? The use of std::max here is suspicious; you should be treating UUUUUUUU and UUUUUUU0 differently.

1488

I suspect what you're doing here is wrong, but it's hard to follow without any comments.

1495

What are you trying to check here? (Maybe you're looking for APFloat::semanticsMaxExponent?)

[aarzee]

Added additional comments, adjustments, and fixes for code clarity. Added exponent-related tests.

[aarzee]

Thanks very much for the feedback, @eli.friedman. Hopefully I've addressed most of your concerns. Regarding the tests: could you think of cases that the current tests don't cover?

[eli.friedman]

This is taking so many iterations to get to a reasonable place that I think you need some other approach to testing; you clearly aren't finding the interesting cases. Have you considered some sort of test generator, which randomly generates known one and known zero masks, then exhaustively checks whether the end result is consistent?

[aarzee]

Indeed I have (although the tests generated are exhaustive, not random), and I attached a script to do so earlier in the thread: https://reviews.llvm.org/F1891038

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

If a value has unknown sign, isn't KnownZero.countLeadingOnes() always going to zero?

1506

Thinking about it a bit more, we don't actually care if the exponent overflows; the end result would be undef, so it doesn't matter.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

I believe that's correct, yes. Thanks for catching that.

This means:

• The absolute value of an integer with unknown sign and bitwidth X has a maximum bitwidth X;
• We know that we already checked whether the width of the integer fits into the significand earlier in the function, and if we reached this point in the function that comparison was false;
• So if we reach this point in the function with unknown sign, we can immediately return nullptr.

We can add this line after the definitions of KnownNegative and PossiblyNegative, and remove the respective else blocks later in the function:

if (PossiblyNegative && !KnownNegative)
  // If the sign of the number is unknown, the bit range will be the width of the integer type,
  // and we already checked whether that will fit into the fp type earlier in the function, so
  // we can exit early.
  return nullptr;

I'll do this in the next revision.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1506

Is this explicitly defined somewhere?

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

I think you can still optimize based on trailing zero bits even if the sign isn't known.

1506

http://llvm.org/docs/LangRef.html#fptosi-to-instruction . "If the value cannot fit in ty2, the results are undefined."

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

Again, you're right. I wasn't thinking about the least significant possibly set bit. How about this:

// If the number is known to be negative, the highest possibly set bit
// is the lowest bit not known to be one.
// Otherwise, it's the highest bit not known to be zero.

if (KnownNegative)
  MostSignificantPossiblySetBit = int(KnownOne.countTrailingOnes()); 
else
  MostSignificantPossiblySetBit = int(BitWidth - KnownZero.countLeadingOnes()) - 1;

1506

FWIW that's for fptosi, not sitofp, but under sitofp I see this: "If the value cannot fit in the floating point value, the results are undefined."
Thank you. I'll remove that check.

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

I assume you meant to use countLeadingOnes for both? Looks roughly right.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

Nope. Lowest bit not known to be one is KnownOne.countTrailingOnes, and highest bit not known to be zero is BitWidth - KnownZero.countLeadingOnes() - 1.

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

What do you need the lowest bit not known to be one for? If the input is known to be an even number, that will always be zero. (If your testing script didn't catch this, you need a more thorough testing script.)

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

You're right again. This is pretty intellectually trying for me, so apologies for those errors.

The problem with the testing script is that it is currently exhaustive and runs in exponential time, so running it with floats and 32-bit integers is impractical, and I have no hardware that supports half-precision.

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

Can you use some sort of software half-precision floating-point library? numpy has a "float16" type which should support the relevant conversion operations.

[aarzee]

I would post the latest diff but the place I'm staying at has no Internet currently.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

I've tried it and it's still impractical at ~43 million tests.

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

Brute-forcing 43 million tests in an hour on a single-core 2GHz desktop computer comes out to around 200,000 cycles per test. If you're trying to run opt -instcombine 43 million times, that might be a problem, but you should be able to easily fit into a 200,000 cycle budget if you copy-paste the computation from this patch into a C++ test harness. (That wouldn't be a complete end-to-end test, but it would be enough to show the tricky bits work correctly.)

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1495

I managed to pull out the relevant code and call it from Python, and it is significantly faster. So now running 43m tests shouldn't be an issue. And indeed, the lack of a specific condition for unknown sign led to issues. So I added a condition that if the sign is unknown, the highest possibly set bit is the bit to the right of the sign. Small caveat here: if the sign bit is unknown and the rest of the bits are all known zero, the highest possibly set bit will be one to the right of the sign bit, while the lowest possibly set bit is the sign bit, leading to a -1 range. It's not necessary to correct this to 1, because 1 will always fit into any significand, and -1 is less than any significand.

[aarzee]

Additional fixes and comments.

I have verified the accuracy of this version of the code with a testing script that I will attach here.

[aarzee]

Attached are a Python test script (best run in PyPy) and C++ testing program that work together to exhaustively verify this code for a given floating point format. See the comments in either file.

floattest.cpp2 KBDownload

ftg2.py2 KBDownload

[eli.friedman]

Overall, this is looking much better; simple is good. :)

lib/Transforms/InstCombine/InstCombineCasts.cpp

1481

Leftover comment?

1505

Doesn't the + 1 here cancel out the -1 in the setting of MostSignificantPossiblySetBit? That would make the math a bit more straightforward.

test/Transforms/InstCombine/sitofp.ll

272

Did you find any interesting new cases worth having a separate regression test?

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1481

I got rid of that in my local copy but I didn't update my diff. Thanks for catching that.

1505

The reasoning behind this is that I wanted the values for both least and most significant possibly set bit to be zero indexed; I thought it might be confusing if one was and the other wasn't.

test/Transforms/InstCombine/sitofp.ll

272

Yes, I will add some tests with unknown sign.

[aarzee]

Additional comments and tests for unknown sign.

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1505

Are you sure subtracting one actually makes the most significant bit zero-indexed? Normally, finding the distance between two array indexes is just simple subtraction; the extra "+1" looks weird. It's also kind of suspicious that your "zero-based" indexing can return a negative number (as an extreme case, if a 16-bit integer is all ones, your code says the most significant possibly set bit has index -1).

test/Transforms/InstCombine/sitofp.ll

278

Maybe also add a corresponding test which doesn't fold?

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1505

I'm going to take a look at the actual behavior, I think the least significant possibly set bit might be one-indexed; in any case something is behaving differently than I intended.

WRT the all-ones case, if a number has no unknown bits then it is by nature a constant, and would be handled by ConstProp, right?

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1505

Yes, in the all-ones case it would get turned into a constant; not sure off the top of my head if that's guaranteed to happen before this code runs, though.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1505

After checking I remembered the reason for the +1: what I'm calling BitRange is actually the width; for example, the width between the 1s in 0b101 would be 3. Maybe width isn't the best word. Whatever the case, this is the reason.

[eli.friedman]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1505

Oh, hmm... not how I would think of it.

b|  1  |  0  |  1  |
 3     2     1     0
 high              low

So the high index is 3, the low index is zero, the significant bits are the bits inside the range, and the length of the range is the high index minus the low index. This is how iterators and ranges in C++ work.

[aarzee]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1505

Right, I hadn't thought of it that way; that is how ranges are expressed in most languages I work with. I'll make the change.

[aarzee]

Modified most and least significant possibly set bit values to act more like range bounds; modified and added unknown sign tests.

[aarzee]

Ping.

I'd like to know if it's possible for a value to be known to be -1 without being a constant; currently the code would not act correctly if this were the case because I made the assumption that it would be a constant and that the code wouldn't be run.

lib/Transforms/InstCombine/InstCombineCasts.cpp

 }
 
 Instruction *InstCombiner::visitTrunc(TruncInst &CI) {
   if (Instruction *Result = commonCastTransforms(CI))
     return Result;
 
   // Test if the trunc is the user of a select which is part of a
   // minimum or maximum operation. If so, don't do any more simplification.
-  // Even simplifying demanded bits can break the canonical form of a 
+  // Even simplifying demanded bits can break the canonical form of a
   // min/max.
   Value *LHS, *RHS;
   if (SelectInst *SI = dyn_cast<SelectInst>(CI.getOperand(0)))
     if (matchSelectPattern(SI, LHS, RHS).Flavor != SPF_UNKNOWN)
       return nullptr;
-  
   // See if we can simplify any instructions used by the input whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(CI))
     return &CI;
 
   Value *Src = CI.getOperand(0);
   Type *DestTy = CI.getType(), *SrcTy = Src->getType();
 
Instruction *InstCombiner::visitSExt(SExtInst &CI) {
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(CI))
     return &CI;
 
   Value *Src = CI.getOperand(0);
   Type *SrcTy = Src->getType(), *DestTy = CI.getType();
 
   // If we know that the value being extended is positive, we can use a zext
-  // instead. 
+  // instead.
   bool KnownZero, KnownOne;
   ComputeSignBit(Src, KnownZero, KnownOne, 0, &CI);
   if (KnownZero) {
     Value *ZExt = Builder->CreateZExt(Src, DestTy);
     return replaceInstUsesWith(CI, ZExt);
   }
 
   // Attempt to extend the entire input expression tree to the destination

 Instruction *InstCombiner::visitFPExt(CastInst &CI) {
   return commonCastTransforms(CI);
 }
 
 // fpto{s/u}i({u/s}itofp(X)) --> X or zext(X) or sext(X) or trunc(X)
 // This is safe if the intermediate type has enough bits in its mantissa to
 // accurately represent all values of X.  For example, this won't work with
 // i64 -> float -> i64.
+// However, this is also safe if we can establish the range between most and
+// least significant set bits of abs(X) fits into the mantissa, and that the
+// number of trailing zeros fits into the exponent.
+
 Instruction *InstCombiner::FoldItoFPtoI(Instruction &FI) {
   if (!isa<UIToFPInst>(FI.getOperand(0)) && !isa<SIToFPInst>(FI.getOperand(0)))
     return nullptr;
   Instruction *OpI = cast<Instruction>(FI.getOperand(0));
 
   Value *SrcI = OpI->getOperand(0);
   Type *FITy = FI.getType();
   Type *OpITy = OpI->getType();
Instruction *InstCombiner::FoldItoFPtoI(Instruction &FI) {
   // of the input range and output range.
 
   // This means this is also safe for a signed input and unsigned output, since
   // a negative input would lead to undefined behavior.
   int InputSize = (int)SrcTy->getScalarSizeInBits() - IsInputSigned;
   int OutputSize = (int)FITy->getScalarSizeInBits() - IsOutputSigned;
   int ActualSize = std::min(InputSize, OutputSize);
 
-  if (ActualSize <= OpITy->getFPMantissaWidth()) {
+  int MantissaWidth = OpITy->getFPMantissaWidth();
+
+  bool safe;
+
+  if (ActualSize <= MantissaWidth) {
+    safe = true;
+    // No need to compute known bits.
+  } else {
+    // Now try and see if the integer value fits into the fp type.
+    int LeastSignificantPossiblySetBit = 0;
+    int MostSignificantPossiblySetBit = 0;
+    int BitRange = 0;
+    uint32_t BitWidth = SrcTy->getScalarSizeInBits();
+    APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
+    computeKnownBits(SrcI, KnownZero, KnownOne, 0, &FI);
+    for (unsigned i = 0; i < BitWidth - 1; i++) {
+      if (!KnownZero[i]) {
+        LeastSignificantPossiblySetBit = i;
+        break;
+      }
+    }
+    for (unsigned i = 0, j; i < BitWidth - 1; i++) {
+      j = BitWidth - i - 1;
+      if (!KnownZero[j]) {
+        bool offsetOne = (IsInputSigned || !KnownZero[BitWidth - 1]) &&
+            (!KnownOne[BitWidth - 1] || KnownZero.countTrailingOnes() < j);
+        MostSignificantPossiblySetBit = j - offsetOne;
+        break;
+      }
+    }
+    BitRange = MostSignificantPossiblySetBit - LeastSignificantPossiblySetBit + 1;
+    safe = BitRange < MantissaWidth && LeastSignificantPossiblySetBit <
+      ((int)OpITy->getScalarSizeInBits() - 1 - BitRange);
+  }
+
+  if (safe) {
     if (FITy->getScalarSizeInBits() > SrcTy->getScalarSizeInBits()) {
       if (IsInputSigned && IsOutputSigned)
         return new SExtInst(SrcI, FITy);
       return new ZExtInst(SrcI, FITy);
     }
     if (FITy->getScalarSizeInBits() < SrcTy->getScalarSizeInBits())
       return new TruncInst(SrcI, FITy);
     if (SrcTy == FITy)
       return replaceInstUsesWith(FI, SrcI);
     return new BitCastInst(SrcI, FITy);
   }
   return nullptr;
 }
 
 Instruction *InstCombiner::visitFPToUI(FPToUIInst &FI) {
   Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
   if (!OpI)
     return commonCastTransforms(FI);
 
   if (Instruction *I = FoldItoFPtoI(FI))
     return I;
 
   return commonCastTransforms(FI);
 }
 
 Instruction *InstCombiner::visitFPToSI(FPToSIInst &FI) {
   Instruction *OpI = dyn_cast<Instruction>(FI.getOperand(0));
   if (!OpI)
     return commonCastTransforms(FI);

test/Transforms/InstCombine/sitofp.ll

 ; CHECK: sitofp
 ; CHECK-NEXT: fptosi
 define i55 @test19(i64 %A) nounwind {
  %B = sitofp i64 %A to double
  %C = fptosi double %B to i55
  ret i55 %C
 }
 
+; This should fold because even though the bit width of the integer
+; is greater than that of the mantissa, we can establish that the
+; actual value of the integer will fit into the mantissa.
+; CHECK-LABEL: test20
+; CHECK: and
+; CHECK-NEXT: ret i32
+define i32 @test20(i32 %A) nounwind {
+ %B = and i32 %A, 16777215
+ %C = sitofp i32 %B to float
+ %D = fptosi float %C to i32
+ ret i32 %D
+}
+
+; This should fold, because even though the effective exponent is
+; 2**24, which does not fit into float's exponent, we can just
+; shift the mantissa 1 bit to the left to compensate.
+; CHECK-LABEL: test21
+; CHECK: and
+; CHECK-NEXT: ret i32
+define i32 @test21(i32 %A) nounwind {
+ %B = and i32 %A, 16777216
+ %C = sitofp i32 %B to float
+ %D = fptosi float %C to i32
+ ret i32 %D
+}