ebevhan added inline comments.
================ Comment at: clang/lib/Basic/FixedPoint.cpp:242 + } else + Overflowed = Result < Min || Result > Max; + ---------------- rjmccall wrote: > leonardchan wrote: > > ebevhan wrote: > > > rjmccall wrote: > > > > ebevhan wrote: > > > > > ebevhan wrote: > > > > > > rjmccall wrote: > > > > > > > If the maximum expressible value is *k*, and the fully-precise > > > > > > > multiplication yields *k+e* for some epsilon *e* that isn't > > > > > > > representable in the result semantics, is that considered an > > > > > > > overflow? If so, I think you need to do the shift after these > > > > > > > bound checks, since the shift destroys the difference between *k* > > > > > > > and *k+e*. That is, unless there's a compelling mathematical > > > > > > > argument that it's not possible to overflow only in the > > > > > > > fully-precision multiplication — but while I think that's > > > > > > > possibly true of `_Fract` (since *k^2 < k*), it seems unlikely to > > > > > > > be true of `_Accum`, although I haven't looked for a > > > > > > > counter-example. And if there is a compelling argument, it > > > > > > > should probably be at least alluded to in a comment. > > > > > > > > > > > > > > Would this algorithm be simpler if you took advantage of the fact > > > > > > > that `APFixedPointSemantics` doesn't have to correspond to a real > > > > > > > type? You could probably just convert to a double-width common > > > > > > > semantics, right? > > > > > > > If the maximum expressible value is *k*, and the fully-precise > > > > > > > multiplication yields *k+e* for some epsilon *e* that isn't > > > > > > > representable in the result semantics, is that considered an > > > > > > > overflow? If so, I think you need to do the shift after these > > > > > > > bound checks, since the shift destroys the difference between *k* > > > > > > > and *k+e*. > > > > > > > > > > > > I don't think I would consider that to be overflow; that's > > > > > > precision loss. E-C considers these to be different: > > > > > > > > > > > > > If the source value cannot be represented exactly by the > > > > > > > fixed-point type, the source value is rounded to either the > > > > > > > closest fixed-point value greater than the source value (rounded > > > > > > > up) or to the closest fixed-point value less than the source > > > > > > > value (rounded down). > > > > > > > > > > > > > > When the source value does not fit within the range of the > > > > > > > fixed-point type, the conversion overflows. [...] > > > > > > > > > > > > > > [...] > > > > > > > > > > > > > > If the result type of an arithmetic operation is a fixed-point > > > > > > > type, [...] the calculated result is the mathematically exact > > > > > > > result with overflow handling and rounding performed to the full > > > > > > > precision of the result type as explained in 4.1.3. > > > > > > > > > > > > There is also no value of `e` that would affect saturation. Any > > > > > > full precision calculation that gives `k+e` must be `k` after > > > > > > downscaling, since the bits that represent `e` must come from the > > > > > > extra precision range. Even though `k+e` is technically larger than > > > > > > `k`, saturation would still just give us `k` after truncating out > > > > > > `e`, so the end result is the same. > > > > > > > > > > > > > Would this algorithm be simpler if you took advantage of the fact > > > > > > > that APFixedPointSemantics doesn't have to correspond to a real > > > > > > > type? You could probably just convert to a double-width common > > > > > > > semantics, right? > > > > > > > > > > > > It's likely possible to use APFixedPoint in the calculations here, > > > > > > but I used APInt to make the behavior explicit and not accidentally > > > > > > be dependent on the behavior of APFixedPoint's conversions or > > > > > > operations. > > > > > Although.,. I guess I see your point in that an intermediate result > > > > > of k+e technically "does not fit within the range of the fixed-point > > > > > type"... but I wonder if treating such cases as overflow is > > > > > particularly meaningful. I don't find there to be much of a > > > > > distinction between such a case and the case where the exact result > > > > > lands inbetween two representable values. We just end up with a less > > > > > precise result. > > > > Right, I was wondering if there was an accepted answer here. For > > > > saturating arithmetic, it's equivalent to truncate this extra precision > > > > down to *k* or to saturate to the maximum representable value, since by > > > > assumption that was just *k*; but for non-saturating arithmetic, it > > > > affects whether the operation has UB. All else being the same, it's > > > > better to have fewer corner-case sources of UB. > > > > > > > > My read is that Embedded C is saying there's a sequence here: compute > > > > the exact mathematical result; round that to the precision of the > > > > result type; the operation overflows if the rounded result is not > > > > representable in the result type. Is the rounding direction completely > > > > unspecified, down to being potentially operand-specific? If so, we > > > > could just say that we always round to avoid overflow if possible. > > > > The main consideration here is that we need to give the operation the > > > > same semantics statically and dynamically, and I don't know if there's > > > > any situation where those semantics would affect the performance of the > > > > operation when done dynamically. > > > > For saturating arithmetic, it's equivalent to truncate this extra > > > > precision down to *k* or to saturate to the maximum representable > > > > value, since by assumption that was just *k*; but for non-saturating > > > > arithmetic, it affects whether the operation has UB. > > > > > > I'm fairly sure that the conclusions here about k and e only hold if k > > > truly is the maximum representable value. If k is anything else (even > > > epsilon-of-the-representable-range less), k+e can never be greater than > > > the maximum. > > > > > > And actually, crunching the numbers on this... If we have integers a and > > > b of width N, sign extended to the double bitwidth A and B, there can be > > > no values for a and b for which A*B is greater than N_Max<<N (`k`). > > > Taking 8-bit as an example: Max is 127, and Max<<8 is 32512. The maximum > > > possible value attainable is -128*-128, which is 16384. That isn't even > > > close to the k+e case. > > > > > > I'm unsure if this reasoning applies in the minimum case as well. > > > > > > > My read is that Embedded C is saying there's a sequence here: compute > > > > the exact mathematical result; round that to the precision of the > > > > result type; the operation overflows if the rounded result is not > > > > representable in the result type. > > > > > > I wonder if it's intended to be a sequence. It's starting to feel like it > > > can't actually be both cases at the same time. > > > > > > And actually, crunching the numbers on this... If we have integers a and > > > b of width N, sign extended to the double bitwidth A and B, there can be > > > no values for a and b for which A*B is greater than N_Max<<N (k). Taking > > > 8-bit as an example: Max is 127, and Max<<8 is 32512. The maximum > > > possible value attainable is -128*-128, which is 16384. That isn't even > > > close to the k+e case. > > > > I think you mean the scale instead of `N` for `N_Max<<N`, and we would run > > into this case for `(N_max << scale) < (a * b) < ((N_max + 1) << scale)` > > where `a` and `b` represent the scaled integers. An example is `1.75 * > > 2.25`, represented as 4 bit unsigned ints with scales of 2: > > > > ``` > > 01.11 (1.75) > > x 10.01 (2.25) > > ------------- > > 11.1111 (3.9375) -> shr 2 -> 11.11 (3.75) > > ``` > > > > where the our `e` in this < 0.25. > > > > My interpretation of the spec (which could be wrong) is whenever they refer > > to "source value", they mean the exact mathematical result (`3.9375`), so > > precision loss and overflow can occur at the same time independently of > > each other. For the non-saturating case, I'd consider the `k + e` to be UB > > because of this. > Your logic only works if the entire integer is scaled, i.e. for `_Fract`; for > `_Accum` types where the scale S can be less than N, it's possible to have an > "epsilon" overflow. For example, with S=4 and N=8, `(44/16) * (93/16) == > (255/16) + (12/256)`. > > Here's a program to brute-force search for counter-examples for an arbitrary > unsigned fixed-point type: > https://gist.github.com/rjmccall/562c2c7c9d289edd8cdf034edd6c1f17 > I think you mean the scale instead of N >Your logic only works if the entire integer is scaled Yes, you're absolutely correct, big mistake on my part. Realized that I'd made the mistake the same day but stuff got in the way of responding :) > My interpretation of the spec (which could be wrong) is whenever they refer > to "source value", they mean the exact mathematical result (3.9375), so > precision loss and overflow can occur at the same time independently of each > other. For the non-saturating case, I'd consider the k + e to be UB because > of this. I agree with the interpretation of "source value". This is still a bit uncertain for me, though. Can they really occur simultaneously? Aren't we just considering the overflow case first rather than the precision loss/rounding case first? If we instead rounded down first (the shift) and then checked overflow, it wouldn't be UB. It feels like a common case to get this kind of result. All that happened during the operation was that we lost precision. Is it really worth considering it to be UB? Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D73186/new/ https://reviews.llvm.org/D73186 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
