leonardchan added inline comments.
================ Comment at: clang/lib/Basic/FixedPoint.cpp:242 + } else + Overflowed = Result < Min || Result > Max; + ---------------- 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. 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
