Invalid constant-folding when converting from floating-point to integer

[peddie]

I'm using the latest commit 2066aba0074a11f7409007b0417f33e40efb753b.

If I write a program that converts from floating-point to integer type:

toWord8 :: SDouble -> SWord8
toWord8 = fromSDouble sRNE

and apply it directly to a negative constant whose rounded value is outside the range of the integral type in GHCI, I see (for example):

>>> toWord8 (-257)
255 :: SWord8

The generated C code disagrees with the Haskell interpreter if the constant is avoided:

compileToC Nothing "conversion" $ do
  doubleIn <- cgInput "input" :: SBVCodeGen SDouble
  cgReturn $ toWord8 doubleIn

results in

SWord8 conversion(const SDouble input)
{
  const SDouble s0 = input;
  const SBool   s1 = isnan(s0);
  const SBool   s2 = isinf(s0);
  const SBool   s3 = s1 || s2;
  const SBool   s4 = !s3;
  const SWord8  s6 = (!isnan(s0) && signbit(s0)) ? (- ((SWord8) fabs(s0))) : ((SWord8) s0);
  const SWord8  s8 = s4 ? s6 : 0;

  return s8;
}

which when called thus

const double conversion_in = -257;
printf("conversion(%lf) = %"PRIu8"\n", conversion_in, conversion(conversion_in));

yields

conversion(-257.000000) = 1

However, if we let constant-folding see what we're about, we will get a different answer:

compileToC Nothing "conversion" . cgReturn $ toWord8 (-257)

results in

SWord8 conversion()
{
  return 255;
}

If I ask Z3 to check the interpreter's evaluation, I seem to get disagreement:

prove $ do
  doubleIn <- sDouble "input"
  constrain $ doubleIn .== (-257)
  let conv = observe "conv" $ fromSDouble sRNE doubleIn :: SWord8
  pure $ conv .== 255

Falsifiable. Counter-example:
  conv  =      0 :: Word8
  input = -257.0 :: Double

But I can also constrain it to be equal to 255, and Z3 is just as happy.

sat $ do
  doubleIn <- sDouble "input"
  constrain $ doubleIn .== (-257)
  let conv = observe "conv" $ fromSDouble sRNE doubleIn :: SWord8
  pure $ conv .== 255

Satisfiable. Model:
  conv  =    255 :: Word8
  input = -257.0 :: Double

What's going on here?

[LeventErkok]

There are really two bugs here. One of them is conversion to C; and I believe I just fixed that. Please give it a shot and let me know if it's still not working.

The second is trickier, unfortunately. The SMTLib conversion functions are essentially uninterpreted when the value is out of range. This is directly from the spec:

All fp.to_* functions are unspecified for NaN and infinity input values. In addition, fp.to_ubv and fp.to_sbv are unspecified for finite number inputs that are out of range (which includes all negative numbers for fp.to_ubv).

But that's not what Haskell (or C) does. So, when you use the prover to compute the values, you're essentially getting a junk value when the input is out-of-range.

I need to think a bit about how to address that; it's not quite trivial because checking "out-of-range" is a tricky thing to do; but should be possible. I'll deal with it sometime this weekend.

Thanks for the report!

[peddie]

Thanks for the fast turnaround as always. I've got your fix for the function described above, which works. Your explanation of SMTLIB's behavior makes sense.

Unfortunately I seem to have another, similar situation where the result I get in GHCI doesn't match the result I get in a generated C program. It's undefined behavior what happens in C in this particular situation, but SBV doesn't match any version of GCC or clang I could test, and these compilers all agree.

Define a conversion function:

> let toInt16 = fromSDouble sRNE . fpRoundToIntegral sRNE :: SDouble -> SInt16

Try converting an out-of-range value:

>  toInt16 4294967295
-1 :: SInt16

Now generate the corresponding C code for toInt16:

> compileToC Nothing "test" $ do { doubleIn <- cgInput "input"; cgReturn $ toInt16 doubleIn }
...
SInt16 test(const SDouble input)
{
  const SDouble s0 = input;
  const SDouble s2 = rint(s0);
  const SBool   s3 = isnan(s2);
  const SBool   s4 = isinf(s2);
  const SBool   s5 = s3 || s4;
  const SBool   s6 = !s5;
  const SInt16  s7 = (SInt16) s2;
  const SInt16  s9 = s6 ? s7 : 0x0000;

  return s9;
}

When I call this function from main()

  const double test_in = 4294967295;
  printf("test(%.16e) : %"PRIi16"\n", test_in, test(test_in));

I see

test(4.2949672950000000e+09) : 0

Is this a bug, or is this kind of thing undefined too many places (C99, SMTLIB), and I shouldn't expect things to line up?

[LeventErkok]

I'm stumped on this too. Let's forget about SBV for a second, and compare Haskell to C:

Prelude Data.Int> round  (4294967295::Double) :: Int16
-1

But:

#include <stdio.h>
#include <inttypes.h>

int main(void) {

    double d = 4294967295;
    int16_t r = (int16_t) d;

    printf("%"PRId16"\n", r);
    return 0;
}

which produces:

$ make a
cc     a.c   -o a
$ ./a
0

We need to understand why Haskell and C are disagreeing here first. Do you know why?

[LeventErkok]

In Section 6.3.1.4 of the C99 spec (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf), it says:

When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined.

I couldn't find anything clear on the Haskell side on how this should behave.

I think there's a general consensus that for "undefined" things, C and Haskell are undefined in the same way. (Whatever that means!) But I think you found a case where their undefined behavior diverges. Perhaps ask about this in the Haskell mailing list?

[peddie]

Sure, I'll ask on the Haskell-cafe list whether anyone knows why this behavior is different.

By the way, if I enable optimizations with -O1 and use gcc version 7 or 8, I get 32767 out of that rounding operation; clang's answer doesn't change.

[LeventErkok]

Yeah, I think this is one of those cases it's impossible to align; obviously don't want to generate different code for different optimization levels.

Does GHC's answer change with different optimization levels?

[peddie]

I haven't found any optimization flag settings that can change GHC's output in this case. I agree that it's not really possible to get everything to line up using the built-in operations.

What I've already begun doing for my program is to ensure that rounding will always result in the nearest valid value (defining 32767 as the "right" answer in this case) and generate C code that explicitly checks the bounds and matches the Haskell behavior. Maybe it would also suit SBV to have some kind of matching behavior like this across SMTLIB, Haskell and C available out of the box or by default?

[LeventErkok]

I've been thinking about it, but haven't found a simple enough solution to align Haskell, SMTLib, C yet. (I'm most worried about the Haskell<->SMTLib correspondence, but if we get the C equivalence, that'd be nice as well.)

There's some discussion here on how to do this: https://stackoverflow.com/questions/526070/handling-overflow-when-casting-doubles-to-integers-in-c

But it's not obvious how to solve the problem "correctly" as the integer-bounds are not necessarily exactly always representable. If you've found a good way to solve the problem that works for all conversions Float/Double/Int8-16-32-64/Word8-16-32-64, I'd love to hear it!

[LeventErkok]

More info here: https://wiki.sei.cmu.edu/confluence/display/c/FLP34-C.+Ensure+that+floating-point+conversions+are+within+range+of+the+new+type

I'm also quite hesitant to spit out a lot of code that complicates both verification and performs a ton of unnecessary checks for the "happy path" execution.

[LeventErkok]

Thought some more about this, and it is really complicated!

The semantics is really the following:

• Take the floating point number
• Round it to the next integral value in that floating-point number's original domain, given the rounding-mode. (That is, find the closest "integral" value that is representable in that domain.)
• If the result is NaN or +/-Inf, then result is 0
• Otherwise, do a rem operation

What this means is that depending on the rounding mode, you can get a different result for the same conversion. (There's, of course, no way to see this in Haskell, since there's only one rounding mode.)

So, even if we're willing to check the "out-of-bounds," that means we have to first do a rounding to and infinitely precise real-number first using the rounding mode. And that's where it gets complicated: There's no function in SMTLib to do that, nor in Haskell or C, that I can rely on.

The way hardware implements this sort of stuff is that they have an internal notion of "working-precision" number, which is conceptually infinitely precise. (In reality, of course, they only need to keep track of what's known as guard/sticky/round bits; I found some notes here if you are interested: http://pages.cs.wisc.edu/~markhill/cs354/Fall2008/notes/flpt.apprec.html)

Long story short, this looks extremely tricky to do correctly across Haskell/SMTLib/C. I'm open for ideas, but I'm inclined towards documenting this a bit more clearly in the code and saying "undefined," that is neither the SMTLib conversion nor the C-translation is guaranteed to match what Haskell does if the inputs are out-of-bounds for the target type and the given rounding mode.

What do you think?

[peddie]

Summary: I understand the price of blowing out the size of SMTLIB expressions just for this hopefully-unlikely case, and I think it makes sense for you to just say "no two parts of this system agree, so don't do this."

Long version:

Thanks for the pointers. I have come across some of this before, but I didn't even know about isgreater() and friends.

I think what I am planning to do is like this:

• If the input value is NaN or +/-Inf, handle the edge case as desired (I might prefer to round Inf to the appropriate bound of the integer type)
• Find the largest (smallest) value in the output domain.
• Given the rounding mode, find the largest (smallest) number in the input domain that rounds to the next largest (smallest) value in the output domain (e.g. what is the largest float that rounds to INT64_MAX - 1?). This need only be done once offline for any given tuple of (input type, output type, rounding mode), I think.
• If the input value is greater (less) than that largest (smallest) floating-point equivalent of the largest(smallest)-within-bounds output domain value, return the largest (smallest) output domain value.
• Otherwise do a normal cast which is well-defined.

It's not yet clear to me that for that limited set of cases (Int|Word)(8|16|32|64), one can't find the correct bounding values, although I can see why care is required. I'm still hoping to implement this shortly and will let you know (unless you can spot a problem already). I wonder whether I'll be able to prove my solution correct with Z3 or MathSAT.

It sounds like our goals are diverging here, because my main application at this point is the C-code generation (most of our terms are far too large and contain too many 64-bit values for any SMT solver I've found to return results in reasonable time), and I'm happy to modify my Haskell DSL's behavior to get whatever behavior I want from the final C program; meanwhile SBV is of course focused on SMT interaction. In other words, I don't think you should worry too much about solving the problems I'm encountering.

[LeventErkok]

Ah, you make an excellent point. We only need to compute the "boundaries" once. Too bad we cannot do this in Haskell, but that doesn't mean these cannot be computed elsewhere.

I'm perfectly happy to adopt this solution directly in SBV! To summarize, I need the following table:

import Data.SBV

-- For each kind/rounding-mode combination; return the min/max convertable
-- values for both float and doubles. For each combo we have 3 values: The minumum
-- representable, the maximum representable, and the default value to return when
-- the input is out-of-range. This should follow what "Haskell" does.
ranges :: [((Kind, RoundingMode) , ((Float, Float, Float) , (Double, Double, Double)))]
ranges = [ ((KBounded False  8, RoundNearestTiesToEven), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False  8, RoundNearestTiesToAway), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False  8, RoundTowardPositive   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False  8, RoundTowardNegative   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False  8, RoundTowardZero       ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 16, RoundNearestTiesToEven), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 16, RoundNearestTiesToAway), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 16, RoundTowardPositive   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 16, RoundTowardNegative   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 16, RoundTowardZero       ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 32, RoundNearestTiesToEven), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 32, RoundNearestTiesToAway), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 32, RoundTowardPositive   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 32, RoundTowardNegative   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 32, RoundTowardZero       ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 64, RoundNearestTiesToEven), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 64, RoundNearestTiesToAway), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 64, RoundTowardPositive   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 64, RoundTowardNegative   ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded False 64, RoundTowardZero       ), ((0,   tbd, tbd), (0,   tbd, tbd)))
         , ((KBounded True   8, RoundNearestTiesToEven), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True   8, RoundNearestTiesToAway), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True   8, RoundTowardPositive   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True   8, RoundTowardNegative   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True   8, RoundTowardZero       ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  16, RoundNearestTiesToEven), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  16, RoundNearestTiesToAway), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  16, RoundTowardPositive   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  16, RoundTowardNegative   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  16, RoundTowardZero       ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  32, RoundNearestTiesToEven), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  32, RoundNearestTiesToAway), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  32, RoundTowardPositive   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  32, RoundTowardNegative   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  32, RoundTowardZero       ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  64, RoundNearestTiesToEven), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  64, RoundNearestTiesToAway), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  64, RoundTowardPositive   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  64, RoundTowardNegative   ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         , ((KBounded True  64, RoundTowardZero       ), ((tbd, tbd, tbd), (tbd, tbd, tbd)))
         ]

Once you fill on all the tbd entries, I think we can code this up and it wouldn't be too terrible in practice. I already filled in the easy ones for you :-)

I'm not sure what it would take to "validate" these numbers. But let's see how you compute them first (because I'm not sure how to go about it), we can think about that later.

[peddie]

It's by no means clever, but my plan is to write a loop in C that starts by casting the extreme-minus-one value to double, then calls nextafter() in a loop, checking that the reverse cast still yields the extreme-minus-one value and returning the last value that does and the first value that does not.

[LeventErkok]

And do this for each rounding mode?

[LeventErkok]

I guess you also have to make sure there are no optimizations turned on? You reported different compilers return different values with differing flags; so I'm a little concerned with that.

[peddie]

Each rounding mode, each integer type, each floating-point type and each boundary.

[peddie]

I don't believe my plan will involve any undefined behavior, since I'm only ever rounding from the floating-point domain to the value next closest to the maximum or minimum representable by the integer domain, which is a defined cast. Did I miss something?

[LeventErkok]

I guess there's an argument there about continuity; but these things are tricky to think about.

If you end up writing a C program that generates that table automatically (which I suspect you will!), please consider turning that into the SBV repo. There's a buildUtils directory that we can put it in and refer to it later should something be in dispute. (And regenerate the table if necessary.)

[peddie]

I'm just testing that it works in a single case right now. I will update with the whole program if it's working.

I'm not sure I understand the continuity issue you are referring to. My naive hope is that nextafter() will be sufficient to make this work.

[LeventErkok]

Oh, I meant your nextafter idea will work because of continuity. But I've been bitten by bizarre floating-point behavior before, so I wanted to hedge my bets.

[LeventErkok]

One final point. When you fill in the entries of the table, please use hexadecimal floats: https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#hexadecimal-floating-point-literals

This way we don't have to worry about precision loss from/to strings. I think the corresponding printf modifier is %a in C.

[peddie]

Re-reading your comment above the table, I want to clarify that I'm not (currently) computing the min/max roundable value. I'm computing the min (max) floating value for which rounding from floating to integer yields a value above (below) the min (max) bound of the integer type. This is because I set out with the goal of rounding out-of-bounds values to the appropriate bound, so I know the answer once my input value is beyond this.

I don't think the same approach will work to determine the min and max values for which casting is defined in the general case, because of the optimization issue, as you mentioned (gcc returned INT16_MAX when I gave it a high out-of-bounds value to round to int16_t, so my loop would not terminate in the right place if I enabled optimizations). But hopefully between two compilers and an explanatory note in the docs, we could reasonably expect to get the right result again in the future somehow.

[LeventErkok]

It'd be great if we can figure out a way to compute this table as I described. Then I can easily use it to both correctly generate SMTLib and C that match the Haskell behavior. (The whole goal of SBV is to match Haskell behavior in SMTLib and C; not the other way around.)

I'll think about this some more; but please explore and let me know what you find out!

[peddie]

I will try my best to compute both! Thanks for the tip about %a, I had been memcpying.

[LeventErkok]

Hmm, looks like maybe we can just use z3 to compute these for us!

Prelude Data.SBV> optimizeWith z3{printBase=16} Lexicographic $ \x z -> do { minimize "z" z; return (sFromIntegral (z::SInt16) .== fpRoundToIntegral sRTZ (x :: SDouble)) }
Optimal model:
  s0 = -32768.004396084696 :: Double
                  6    5          4         3         2         1         0
                  3 21098765432 1098765432109876543210987654321098765432109876543210
                  S ----E11---- ------------------------F52-------------------------
          Binary: 1 10000001110 0000000000000000000000100100000000110100001000000000
             Hex: C0E0 0000 2403 4200
       Precision: DP
            Sign: Negative
        Exponent: 15 (Stored: 1038, Bias: 1023)
       Hex-float: -0x1.00000240342p15
           Value: -32768.004396084696 (NORMAL)
  s1 =             -0x8000 :: Int16
  z  =             -0x8000 :: Int16
Prelude Data.SBV> optimizeWith z3{printBase=16} Lexicographic $ \x z -> do { maximize "z" z; return (sFromIntegral (z::SInt16) .== fpRoundToIntegral sRTZ (x :: SDouble)) }
Optimal model:
  s0 = 32767.00781250052 :: Double
                  6    5          4         3         2         1         0
                  3 21098765432 1098765432109876543210987654321098765432109876543210
                  S ----E11---- ------------------------F52-------------------------
          Binary: 0 10000001101 1111111111111100000010000000000000000000000010001111
             Hex: 40DF FFC0 8000 008F
       Precision: DP
            Sign: Positive
        Exponent: 14 (Stored: 1037, Bias: 1023)
       Hex-float: +0x1.fffc08000008fp14
           Value: +32767.00781250052 (NORMAL)
  s1 =            0x7fff :: Int16
  z  =            0x7fff :: Int16

I belive this is exactly what we're looking for!

[peddie]

You are the man! That's exactly it! Time to throw away my hacky binary search code.

What else do you need from me to implement this?

[LeventErkok]

I hacked a program, but I'm not sure if I like the output. The program is here: https://gist.github.com/LeventErkok/fdc8880fe8b726362c0feba15018be36

It takes a bit to run, and spits out this:

[ (KBounded False 8 , RoundNearestTiesToEven, (0x1.40001p-96  , 0x1.fe44p7   ), (-0x1.080002p-968       , 0x1.fe0bp7           ))
, (KBounded False 8 , RoundNearestTiesToAway, (-0x1.001p-104  , 0x1.fe0004p7 ), (-0x1.0004p-936         , 0x1.fe00084p7        ))
, (KBounded False 8 , RoundTowardPositive   , (-0x1.000ap-82  , 0x1.fep7     ), (-0x1.0000000001251p-800, 0x1.fep7             ))
, (KBounded False 8 , RoundTowardNegative   , (-0x0p+0        , 0x1.fe01p7   ), (0x1.000007fd8434p-952  , 0x1.fe00000000141p7  ))
, (KBounded False 8 , RoundTowardZero       , (0x1.110022p-104, 0x1.fe20b2p7 ), (-0x1.0000000449942p-932, 0x1.fe00032600169p7  ))
, (KBounded False 16, RoundNearestTiesToEven, (-0x1p-94       , 0x1.fffep15  ), (0x1.ap-512             , 0x1.fffep15          ))
, (KBounded False 16, RoundNearestTiesToAway, (-0x1.ab617p-104, 0x1.fffe04p15), (-0x1.200004259914ep-936, 0x1.fffe47fcp15      ))
, (KBounded False 16, RoundTowardPositive   , (0x0p+0         , 0x1.fffep15  ), (-0x1.840000605e51p-1016, 0x1.fffep15          ))
, (KBounded False 16, RoundTowardNegative   , (0x1.144p-40    , 0x1.fffep15  ), (0x1.000208a048p-960    , 0x1.fffe000000061p15 ))
, (KBounded False 16, RoundTowardZero       , (0x1.000104p-126, 0x1.fffe0cp15), (0x1.0000008607p-1012   , 0x1.fffe000201p15    ))
, (KBounded False 32, RoundNearestTiesToEven, (0x1p-130       , 0x1p32       ), (0x1.000000002p-72      , 0x1.fffffffe004p31   ))
, (KBounded False 32, RoundNearestTiesToAway, (-0x1.405p-104  , 0x1p32       ), (0x1.000852p-970        , 0x1.fffffffe0002p31  ))
, (KBounded False 32, RoundTowardPositive   , (-0x1.000008p-96, 0x1p32       ), (-0x1.00000bp-512       , 0x1.fffffffc22p31    ))
, (KBounded False 32, RoundTowardNegative   , (-0x0p+0        , 0x1p32       ), (0x1.00840308p-970      , 0x1.fffffffe02051p31 ))
, (KBounded False 32, RoundTowardZero       , (0x1.0100dap-96 , 0x1p32       ), (0x1.00001p-950         , 0x1.fffffffe00001p31 ))
, (KBounded False 64, RoundNearestTiesToEven, (-0x1p-104      , 0x1p64       ), (0x1.08c0800842042p-202 , 0x1p64               ))
, (KBounded False 64, RoundNearestTiesToAway, (-0x1.046b18p-40, 0x1p64       ), (-0x1.100003290a08cp-970, 0x1p64               ))
, (KBounded False 64, RoundTowardPositive   , (0x0p+0         , 0x1p64       ), (-0x1.1db807c01ep-968   , 0x1p64               ))
, (KBounded False 64, RoundTowardNegative   , (0x1.002492p-96 , 0x1p64       ), (0x1.000000c1ab14p-971  , 0x1p64               ))
, (KBounded False 64, RoundTowardZero       , (0x1.0609a8p-70 , 0x1p64       ), (0x1.0000121e84f54p-72  , 0x1p64               ))
, (KBounded True  8 , RoundNearestTiesToEven, (-0x1.fe02p6    , 0x1.fc001p6  ), (-0x1.000001411306ap7   , 0x1.fcp6             ))
, (KBounded True  8 , RoundNearestTiesToAway, (-0x1.fe0134p6  , 0x1.fc028p6  ), (-0x1.00081000000b9p7   , 0x1.fc004p6          ))
, (KBounded True  8 , RoundTowardPositive   , (-0x1.000206p7  , 0x1.fcp6     ), (-0x1.0000004p7         , 0x1.fcp6             ))
, (KBounded True  8 , RoundTowardNegative   , (-0x1p7         , 0x1.fc34p6   ), (-0x1p7                 , 0x1.fc00000bp6       ))
, (KBounded True  8 , RoundTowardZero       , (-0x1.000004p7  , 0x1.fc02p6   ), (-0x1.001e10c7c7018p7   , 0x1.fc1020414c05p6   ))
, (KBounded True  16, RoundNearestTiesToEven, (-0x1.000024p15 , 0x1.fffa24p14), (-0x1.000000039008bp15  , 0x1.fffa001p14       ))
, (KBounded True  16, RoundNearestTiesToAway, (-0x1.00008p15  , 0x1.fffcp14  ), (-0x1.000000054102p15   , 0x1.fffc0a0024p14    ))
, (KBounded True  16, RoundTowardPositive   , (-0x1.00001ep15 , 0x1.fffcp14  ), (-0x1.00000000002p15    , 0x1.fffcp14          ))
, (KBounded True  16, RoundTowardNegative   , (-0x1.fffc2p14  , 0x1.fffcp14  ), (-0x1.fffc001p14        , 0x1.fffc0001p14      ))
, (KBounded True  16, RoundTowardZero       , (-0x1.000086p15 , 0x1.fffc02p14), (-0x1.00000240342p15    , 0x1.fffc08000008fp14 ))
, (KBounded True  32, RoundNearestTiesToEven, (-0x1p31        , 0x1p31       ), (-0x0.ffffffff08p31     , 0x0.fffffffe808p31   ))
, (KBounded True  32, RoundNearestTiesToAway, (-0x1p31        , 0x1p31       ), (-0x1.00000000031cp31   , 0x0.fffffffe186b78p31))
, (KBounded True  32, RoundTowardPositive   , (-0x1p31        , 0x1p31       ), (-0x1.00000000002p31    , 0x0.fffffffc5p31     ))
, (KBounded True  32, RoundTowardNegative   , (-0x1p31        , 0x1p31       ), (-0x1p31                , 0x0.fffffffe8p31     ))
, (KBounded True  32, RoundTowardZero       , (-0x1p31        , 0x1p31       ), (-0x1.000000016a0ap31   , 0x0.fffffffe1f76b8p31))
, (KBounded True  64, RoundNearestTiesToEven, (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundNearestTiesToAway, (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundTowardPositive   , (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundTowardNegative   , (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundTowardZero       , (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
]

I don't understand why the lower-bounds aren't exactly 0 whenever the type is unsigned. Maybe I have a bug in the code somewhere, or maybe z3 is having issues. Also, the negative values in lower bounds for unsigned types need better understanding: I expected bizarre results would come out like this, but I wish we had a second means of computing these values.

It'd be good to at least confirm some of these values, and understand the lower-bound problem. Once we're comfortable with the table, we just need to decide what value to map the out-of-bounds values to, and that should do it.

Do take a look, and hopefully you'll fix the program! (Or file a bug with z3 folks!!)

[LeventErkok]

For instance, I'm very suspicious of the very first value in the table:

(KBounded False 8 , RoundNearestTiesToEven, (0x1.40001p-96  , 0x1.fe44p7   ), (-0x1.080002p-968       , 0x1.fe0bp7           ))

Why are the lower bounds not simply 0? With RNE, 0 should map to 0. Something isn't right. Do you have any insight into this?

[LeventErkok]

I also notice that that current translation to C by simply type-casting is buggy, as it simply truncates the result. We need to use rint in all cases. I'll fix that separately once we resolve this issue first.

[peddie]

I'll dig in, but some initial thoughts:

I would expect some floating-point values below zero to round up to zero. I think this would be defined in C99, wherein

When a finite value of real floating type is converted to an integer type other than _Bool, the fractional part is discarded (i.e., the value is truncated toward zero). If the value of the integral part cannot be represented by the integer type, the behavior is undefined.

But I think this implies that for the same rounding mode and floating type, the lower bound should still be the same (below-zero) value for all unsigned types, which is obviously not what we see.

According to your quote from the SMTLIB spec, though, maybe any floating value below 0 falls in the realm of undefined behavior. In this case, the undefined behavior could be "round to 0" for any subset of values below 0, and you don't get any promises that out-of-bounds values don't match at the .== in your program. That seems like the same underlying issue as the optimization level problem we discussed for the C boundary-search program.

[LeventErkok]

I need to think more about this; would be a shame to invest in this if we don't have a good way of making sure the values we get are actually correct. Back to the drawing board!

[peddie]

Side thought: it's wholly unsatisfying, but perhaps we could do the optimization problem with multiple solvers via the old iterative optimization strategy from SBV pre-7 to detect behavior that is specific to one solver. Maybe that would be more work than just getting the C program working.

[LeventErkok]

Binary search through the solver is painful! But give it a shot!!

Here's why I think maybe there's a bug in z3:

$ ghci
GHCi, version 8.6.3: http://www.haskell.org/ghc/  :? for help
Prelude> :m + Data.Int
Prelude Data.Int> :set -XHexFloatLiterals
Prelude Data.Int> round (0x1.40001p-96 :: Float) :: Int8
0
Prelude Data.Int> round (0 :: Float) :: Int8
0
Prelude Data.Int> (0 :: Float) < 0x1.40001p-96
True

This suggest z3 is lying. Can you run the same with your C compiler to make sure it matches Haskell?

[LeventErkok]

ps. I'll be offline for a while; about 9-10 hrs.. Hopefully you'll have some results by then!

[peddie]

I need to look at this more, but maybe we could use MPFR (which even has a haskell binding) to double-check that we've got the right result, rather than checking whether the rounded value matches?

Return non-zero if op would fit in the respective C data type, respectively unsigned long, long, unsigned int, int, unsigned short, short, uintmax_t, intmax_t, when rounded to an integer in the direction rnd. For instance, with the MPFR_RNDU rounding mode on -0.5, the result will be non-zero for all these functions. For MPFR_RNDF, those functions return non-zero when it is guaranteed that the corresponding conversion function (for example mpfr_get_ui for mpfr_fits_ulong_p), when called with faithful rounding, will always return a number that is representable in the corresponding type. As a consequence, for MPFR_RNDF, mpfr_fits_ulong_p will return non-zero for a non-negative number less or equal to ULONG_MAX.

from here. It looks like their rounding modes correspond to 4 of the IEEE754 ones. There isn't a version for char and unsigned char, unfortunately -- not sure how to get around that.

[peddie]

Sorry, I made a silly mistake. My C compiler has the same behavior as GHCI.

So I have two things to look at:

• What is Z3 doing?
• Can we use MPFR to confirm these bounds are accurate?

I checked and the "fits" implementation in MPFR is a macro, so it's possible it will do the right thing for byte-size integers as well if I just add the expected boilerplate.

[peddie]

I misread your first value as the negative of what it is (sorry for the confusion). I agree, it seems like a clear indication that Z3 is up to no good, and I'll focus on that.

But I don't think these values have to be zero according to SMTLIB or IEEE:

Prelude> import Data.Number.MPFR as MPFR
Prelude MPFR> :set -XHexFloatLiterals
Prelude MPFR> let n = stringToMPFR Near 24 16 "-0x1.40001p-96"  -- rounding mode, significand size (implicit) in bits, string base, string
Prelude MPFR> fitsUInt Down n                                 
False
Prelude MPFR> fitsUShort Near n                               
True
Prelude MPFR> fitsUShort Zero n
True
Prelude MPFR> fitsUShort Up n  
True
Prelude MPFR> fitsUShort Down n
False

[peddie]

Taking a closer look at your example

optimizeWith z3{printBase=16} Lexicographic $ \x z -> do { minimize "z" z; return (sFromIntegral (z::SWord8) .== fpRoundToIntegral sRTN (x :: SFloat)) }

It's getting late, so perhaps I've fooled myself yet again today, but it looks like we're actually finding the minimal Word8 that can be rounded to by floating-point, and we get a floating-point value that rounds to zero, and happens to be close to it. There appears to be no way to request that the floating-point value itself be minimized; I didn't know this, but Z3 cannot minimize floating-point values:

The (maximize t) command instructs check-sat to produce a model that maximizes the value of term t. The type of t must be either Int, Real, or BitVec.

and SBV knows this:

Currently, bounded signed/unsigned bit-vectors, unbounded integers, and algebraic reals can be optimized. (But not, say, SFloat, SDouble, or SBool.)

So I'll press on with binary search via MPFR.

[peddie]

I've got most of a program at https://gist.github.com/peddie/0296a6c9809174243ae4221c949061dc -- it works as written, but there are a few problems:

• MPFR does not expose 8-bit int conversions. The other conversions are implemented by a generic macro, so it seems like this is an easy fix.
• The current Haskell MPFR bindings are outdated and don't expose round-away-from-zero mode or direct conversion to single-precision float (which we want if we want to be able to printf "%a"). These exist in MPFR, so it should be another easy fix.

Finally, because nothing is ever easy with floating-point, when using the Down rounding mode and looking for the lower bound on Word16, I seem to have hit some kind of bug in MPFR in my binary search that results in strange sequences of values like -6.418972936498817e-1080, -3.209486468249409e-1080, -1.604743234124704e-1080 etc., so my search never finds equal values and never returns. I have told MPFR that these values are to have 24-bit significand precision (Float), and supposedly MPFR doesn't even support ordinary subnormal values, so I'm not clear how such values can even be represented. On the one hand, this does happen to be the only rounding mode where (I think?) we already know the lower bound we're looking for (0), but on the other hand, this doesn't inspire confidence.

Unfortunately I have to call it quits for tonight, but I hope some of this will be helpful for you when you return. I'm prepared to pick up where I left off tomorrow. Maybe there is a better arbitrary-precision library out there that can reliably compute these constants (or maybe the bug is in the binding, and a C program would get the answer). I'm somewhat fascinated by the difficulty of actually determining these values.

[LeventErkok]

Good point! I fooled myself by optimizing for the converted value; but that doesn't mean the corresponding float will be optimized as well. In a sense, that's precisely what we're trying to do!

I'll take a look at your program in a bit; though maybe there might be another trick we can play with z3's optimizer to give us what we want. I need to experiment a bit..

[peddie]

Perhaps you could minimize the algebraic real conversion of the floating-point value?

[peddie]

Tried it quick and got

[RECV] unknown
[SEND] (get-info :reason-unknown)
[RECV] (:reason-unknown "(incomplete (theory arithmetic))")

[LeventErkok]

Nice try! I've a similar idea, but doesn't go through algebraic reals. Instead, I plan to use the sFloatAsSWord32 and track the bit-pattern instead. But I didn't get a chance to try it yet. (If you want to try, go for it!)

[peddie]

I don't have time to understand the implications of this conversion yet, but I did just do a dummy problem that converts a float to a 32-bit word, and the solver doesn't complain about the theory involved, so that's a good sign. I hope to get back to this soon.

[LeventErkok]

I’m away from a decent computer to try this, but should have access in 4-5 hrs. O think it’ll work, since floats are lexicographically comparable after sign switch. I’m not sure about performance though, that’s what I need to play, later tonight hopefully.

On Feb 28, 2019, at 4:44 PM, Matt Peddie notifications@github.com wrote:

I don't have time to understand the implications of this conversion yet, but I did just do a dummy problem that converts a float to a 32-bit word, and the solver doesn't complain about the theory involved, so that's a good sign. I hope to get back to this soon.

— You are receiving this because you were assigned. Reply to this email directly, view it on GitHub, or mute the thread.

[peddie]

Ah, thanks, I was trying to find a source to confirm my recollection about some such property. That seems to work:

*Data.SBV> optimizeWith z3{printBase=16, verbose=True} Lexicographic $ \x y z -> do { maximize "z" z; maximize "y" y; return $ sFromIntegral (y::SWord8) .== fpRoundToIntegral sRNE (x :: SFloat) .&& (z .== setBittTo (sFloatAsSWord32 x :: SWord32) 31 sFalse
Optimal model:
  s0 =  255.49998 :: Float
                  3  2          1         0
                  1 09876543 21098765432109876543210
                  S ---E8--- ----------F23----------
          Binary: 0 10000110 11111110111111111111111
             Hex: 437F 7FFF
       Precision: SP
            Sign: Positive
        Exponent: 7 (Stored: 134, Bias: 127)
       Hex-float: +0x1.fefffep7
           Value: +255.49998 (NORMAL)
  s1 =       0xff :: Word8
  s2 = 0x437f7fff :: Word32
  z  = 0x437f7fff :: Word32
  y  =       0xff :: Word8

I will have to think a bit about the sign-handling, but I think you've got it here. What's more, this constant agrees with MPFR's result in this case.

[LeventErkok]

Essentially, if the sign bit is high, then you should flip all the bits. If the sign bit is low, then just flip the sign bit and keep mantissa and fraction exactly the same. Should first maximize/minimize the float, then max/min the z value; in that order. (Because not all bounds maybe exactly representable.)

I'm not sure how well this would perform with all the variations, but it's worth a shot! Why don't you generate a table, and I'll generate another independently and we can compare and see if we get the same results. I'm still away from a decent machine, but should have something within the next 7-8 hours.

[peddie]

We cannot get Z3 to minimize or maximize the float; we can only maximize or minimize the rounded value and the integer corresponding to the bits of the floating value.

Just based on my understanding of the different rounding modes, here's what my expectation is for the lower bound when rounding from Float to any unsigned type:

• sRTZ -> nextafterf(-1.0, 0) (-0x1.fffffep-1)
• sRTP -> nextafterf(-1.0, 0) (-0x1.fffffep-1)
• sRNA -> nextafterf(-0.5, 0) (-0x1.fffffep-2)
• sRNE -> -0.5 (-0x1p-1)
• sRTN -> -0.0 (-0x0p+0)

[peddie]

I had a few comments that I think were misguided and unhelpful, so I deleted them (you probably got emails for them, sorry for the noise). I don't seem to be able to match the values for Float I see above using your logic, though (I never get anything with a negative sign when rounding to unsigned values).

[peddie]

A disappointing number of mistakes later, here's my table:

[ (KBounded False 8 , RoundNearestTiesToEven, (-0x1p-1        , 0x1.fefffep7 ), (-0x1p-1                , 0x1.fefffffffffffp7  ))
, (KBounded False 8 , RoundNearestTiesToAway, (-0x1.fffffep-2 , 0x1.fefffep7 ), (-0x0.fffffffffffff8p-1 , 0x1.fefffffffffffp7  ))
, (KBounded False 8 , RoundTowardPositive   , (-0x1.fffffep-1 , 0x1.fep7     ), (-0x1.fffffffffffffp-1  , 0x1.fep7             ))
, (KBounded False 8 , RoundTowardNegative   , (-0x0p+0        , 0x1.fffffep7 ), (-0x0p+0                , 0x1.fffffffffffffp7  ))
, (KBounded False 8 , RoundTowardZero       , (-0x1.fffffep-1 , 0x1.fffffep7 ), (-0x1.fffffffffffffp-1  , 0x1.fffffffffffffp7  ))
, (KBounded False 16, RoundNearestTiesToEven, (-0x1p-1        , 0x1.fffefep15), (-0x1p-1                , 0x1.fffefffffffffp15 ))
, (KBounded False 16, RoundNearestTiesToAway, (-0x1.fffffep-2 , 0x1.fffefep15), (-0x0.fffffffffffff8p-1 , 0x1.fffefffffffffp15 ))
, (KBounded False 16, RoundTowardPositive   , (-0x1.fffffep-1 , 0x1.fffep15  ), (-0x1.fffffffffffffp-1  , 0x1.fffep15          ))
, (KBounded False 16, RoundTowardNegative   , (-0x0p+0        , 0x1.fffffep15), (-0x0p+0                , 0x1.fffffffffffffp15 ))
, (KBounded False 16, RoundTowardZero       , (-0x1.fffffep-1 , 0x1.fffffep15), (-0x1.fffffffffffffp-1  , 0x1.fffffffffffffp15 ))
, (KBounded False 32, RoundNearestTiesToEven, (-0x1p-1        , 0x1p32       ), (-0x1p-1                , 0x1.fffffffefffffp31 ))
, (KBounded False 32, RoundNearestTiesToAway, (-0x1.fffffep-2 , 0x1p32       ), (-0x0.fffffffffffff8p-1 , 0x1.fffffffefffffp31 ))
, (KBounded False 32, RoundTowardPositive   , (-0x1.fffffep-1 , 0x1p32       ), (-0x1.fffffffffffffp-1  , 0x1.fffffffep31      ))
, (KBounded False 32, RoundTowardNegative   , (-0x0p+0        , 0x1p32       ), (-0x0p+0                , 0x1.fffffffffffffp31 ))
, (KBounded False 32, RoundTowardZero       , (-0x1.fffffep-1 , 0x1p32       ), (-0x1.fffffffffffffp-1  , 0x1.fffffffffffffp31 ))
, (KBounded False 64, RoundNearestTiesToEven, (-0x1p-1        , 0x1p64       ), (-0x1p-1                , 0x1p64               ))
, (KBounded False 64, RoundNearestTiesToAway, (-0x1.fffffep-2 , 0x1p64       ), (-0x0.fffffffffffff8p-1 , 0x1p64               ))
, (KBounded False 64, RoundTowardPositive   , (-0x1.fffffep-1 , 0x1p64       ), (-0x1.fffffffffffffp-1  , 0x1p64               ))
, (KBounded False 64, RoundTowardNegative   , (-0x0p+0        , 0x1p64       ), (-0x0p+0                , 0x1p64               ))
, (KBounded False 64, RoundTowardZero       , (-0x1.fffffep-1 , 0x1p64       ), (-0x1.fffffffffffffp-1  , 0x1p64               ))
, (KBounded True  8 , RoundNearestTiesToEven, (-0x1.01p7      , 0x1.fdfffep6 ), (-0x1.01p7              , 0x1.fdfffffffffffp6  ))
, (KBounded True  8 , RoundNearestTiesToAway, (-0x1.00fffep7  , 0x1.fdfffep6 ), (-0x1.00fffffffffffp7   , 0x1.fdfffffffffffp6  ))
, (KBounded True  8 , RoundTowardPositive   , (-0x1.01fffep7  , 0x1.fcp6     ), (-0x1.01fffffffffffp7   , 0x1.fcp6             ))
, (KBounded True  8 , RoundTowardNegative   , (-0x1p7         , 0x1.fffffep6 ), (-0x1p7                 , 0x0.fffffffffffff8p7 ))
, (KBounded True  8 , RoundTowardZero       , (-0x1.01fffep7  , 0x1.fffffep6 ), (-0x1.01fffffffffffp7   , 0x0.fffffffffffff8p7 ))
, (KBounded True  16, RoundNearestTiesToEven, (-0x1.0001p15   , 0x1.fffdfep14), (-0x1.0001p15           , 0x1.fffdfffffffffp14 ))
, (KBounded True  16, RoundNearestTiesToAway, (-0x1.0000fep15 , 0x1.fffdfep14), (-0x1.0000fffffffffp15  , 0x1.fffdfffffffffp14 ))
, (KBounded True  16, RoundTowardPositive   , (-0x1.0001fep15 , 0x1.fffcp14  ), (-0x1.0001fffffffffp15  , 0x1.fffcp14          ))
, (KBounded True  16, RoundTowardNegative   , (-0x1p15        , 0x1.fffffep14), (-0x1p15                , 0x0.fffffffffffff8p15))
, (KBounded True  16, RoundTowardZero       , (-0x1.0001fep15 , 0x1.fffffep14), (-0x1.0001fffffffffp15  , 0x0.fffffffffffff8p15))
, (KBounded True  32, RoundNearestTiesToEven, (-0x1p31        , 0x1p31       ), (-0x1.00000001p31       , 0x0.fffffffefffff8p31))
, (KBounded True  32, RoundNearestTiesToAway, (-0x1p31        , 0x1p31       ), (-0x1.00000000fffffp31  , 0x0.fffffffefffff8p31))
, (KBounded True  32, RoundTowardPositive   , (-0x1p31        , 0x1p31       ), (-0x1.00000001fffffp31  , 0x0.fffffffep31      ))
, (KBounded True  32, RoundTowardNegative   , (-0x1p31        , 0x1p31       ), (-0x1p31                , 0x0.fffffffffffff8p31))
, (KBounded True  32, RoundTowardZero       , (-0x1p31        , 0x1p31       ), (-0x1.00000001fffffp31  , 0x0.fffffffffffff8p31))
, (KBounded True  64, RoundNearestTiesToEven, (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundNearestTiesToAway, (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundTowardPositive   , (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundTowardNegative   , (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
, (KBounded True  64, RoundTowardZero       , (-0x1p63        , 0x1p63       ), (-0x1p63                , 0x1p63               ))
]