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