[AST] Add fixed-point multiplication constant evaluation.

[rjmccall]

clang/lib/Basic/FixedPoint.cpp

242

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?

[ebevhan]

Rebased.

[ebevhan]

clang/lib/Basic/FixedPoint.cpp

242

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.

[ebevhan]

clang/lib/Basic/FixedPoint.cpp

242

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.

[rjmccall]

clang/lib/Basic/FixedPoint.cpp

242

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.

[ebevhan]

clang/lib/Basic/FixedPoint.cpp

242

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.

[leonardchan]

clang/lib/Basic/FixedPoint.cpp

242

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.

[rjmccall]

clang/lib/Basic/FixedPoint.cpp

242

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

[ebevhan]

clang/lib/Basic/FixedPoint.cpp

242

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?

[rjmccall]

clang/lib/Basic/FixedPoint.cpp

242

Well, like I said up-thread, since the spec doesn't seem to impose any constraints on rounding at all, I think we can just define it such that we always round to avoid overflow if possible. For saturating math, it's the same either way, since we either (1) "round to avoid overflow" and thus only see a maximal/minimal value or (2) we detect overflow and thus substitute the maximal/minimal value. For non-saturating math, it changes whether UB formally occurs, which I think affects three areas:

• C++ constexpr, which isn't allowed to invoke UB. Abstractly, it's better to accept more programs here instead of emitting really pedantic errors about unrepresentable overflows.

• Fixed-point intrinsics which check whether UB occurred dynamically. I don't think we have any of these today, but we might add them someday — among other things, I think the UBSan people would say that UBSan should have a check for this, which would require such an intrinsic. It's not unlikely that this will complicate the implementation because we won't be able to simply consider whether the underlying integer operation overflowed.

• High-level optimizations that exploit the UB-ness of non-saturating overflow. For example, it is abstractly true that x * C > x when x is known to be strictly positive and C is a constant greater than 1, but if we define rounding as avoiding overflow, there might be corner cases where this isn't true for some C. I'm not sure we would ever do any optimizations like this, but if we did, they'd probably have to be more conservative in some cases.

So it's really a judgment call for you folks, one that you need to make with an understanding of where you want to take this feature.

[ebevhan]

clang/lib/Basic/FixedPoint.cpp

242

Okay, these are good points. I think I'm starting to agree with the idea of avoiding overflow if possible. I was a bit concerned that it might be a bit too strong of a claim to make, for example if there were cases where it would be more natural for a particular calculation to detect an overflow rather than round and avoid it. But I'm starting to wonder if there really are any such cases.

I would also be fine with simply defining the order in which we perform the operations; round first, then check for overflow. That would be in line with the order it's written in the spec, but I don't know if that was how it was intended to work.

We'll see what Leonard has to say.

[leonardchan]

clang/lib/Basic/FixedPoint.cpp

242

I think for simplicity and since this doesn't seem to actively go against the spec, it would be good to do rounding then overflow check in that sense.

Going on a tangent (I don't remember if this was brought up before, but do remind me if there was a consensus on this): let's say we have a target that defines rounding to always be towards positive infinity for their multiplication intrinsics. Currently in this patch, I believe the default is always going to be rounding towards negative infinity from right shifting after the multiplication. To match the static calculation behavior against the dynamic intrinsics, would it be better to add a field in TargetInfo, next to the fixed point type widths, that specified different rounding types?

Something that's been bothering me with this is that if we wanted to do something like contexpr evaluation for these types, we'd also need to consider the rounding, but that could potentially mean a constexpr value can vary depending on the target, unless this is allowed or already considered.

[rjmccall]

clang/lib/Basic/FixedPoint.cpp

242

You're right that if we have targets with divergent rounding semantics, we'll probably need to represent that in the FixedPointSemantics — and yeah, the results could then be target-specific.

[ebevhan]

clang/lib/Basic/FixedPoint.cpp

242

Going on a tangent (I don't remember if this was brought up before, but do remind me if there was a consensus on this): let's say we have a target that defines rounding to always be towards positive infinity for their multiplication intrinsics. Currently in this patch, I believe the default is always going to be rounding towards negative infinity from right shifting after the multiplication.

Well, rounding direction isn't just a problem in consteval. If a target's legal fixed-point multiplication instructions all round up, but we somehow get an illegal intrinsic and the expansion code is invoked, that particular runtime operation will round down instead since the default expansion lowering rounds down.

It's really hard to balance the complexity of this without running wires through the entire compilation pipeline for managing rounding direction. That's why it's a bit more straightforward to state that the rounding is indeterminate, but keeping it consistent in the general case, say, if a target doesn't have any opinion on fixed-point operation rounding (which most targets probably don't). Rounding down just happens to be simpler than rounding up (for multiplication, anyway) so that's a fair choice.

Maybe rounding is something we should look into in the future, though.

[ebevhan]

So, any more on this or are we in agreement?

[rjmccall]

Since we've settled on not considering that to be overflow, yeah, I think the patch is fine. Might be worth being explicit about that at the point you do the shift: that it's known that this discards precision that could leave the true mathematical value outside of the expressible range, and that we are interpreting the spec as allowing us to round to avoid this formal overflow in order to avoid unnecessary UB.

[ebevhan]

Rebased.

[ebevhan]

The last patchset contains the comment about rounding, so I think I will consider this accepted.

As a final addendum to the discussion on rounding and overflow... The last Appendix to the E-C TR does actually say:

2.   In the first edition requires that overflow handling is done before rounding; for the second edition the order is changed: rounding should be done first, followed by overflow handling. Note that this change does not affect any result when the overflow mode is saturation.

The wording in the main text could be a bit clearer about it being explicit, though.

[leonardchan]

LGTM

clang/include/clang/Basic/FixedPoint.h

APFixedPoint convert(const FixedPointSemantics &DstSema,
                         bool *Overflow = nullptr) const;
 
    // Perform binary operations on a fixed point type. The resulting fixed point
    // value will be in the common, full precision semantics that can represent
    // the precision and ranges of both input values. See convert() for an
    // explanation of the Overflow parameter.
    APFixedPoint add(const APFixedPoint &Other, bool *Overflow = nullptr) const;
    APFixedPoint sub(const APFixedPoint &Other, bool *Overflow = nullptr) const;
+   APFixedPoint mul(const APFixedPoint &Other, bool *Overflow = nullptr) const;
 
    /// Perform a unary negation (-X) on this fixed point type, taking into
    /// account saturation if applicable.
    APFixedPoint negate(bool *Overflow = nullptr) const;
 
    APFixedPoint shr(unsigned Amt) const {
      return APFixedPoint(Val >> Amt, Sema);
    }

clang/lib/AST/ExprConstant.cpp

case BO_Sub: {
     bool AddOverflow, ConversionOverflow;
     APFixedPoint Result = LHSFX.sub(RHSFX, &AddOverflow)
                                .convert(ResultFXSema, &ConversionOverflow);
     if ((AddOverflow || ConversionOverflow) &&
         !HandleOverflow(Info, E, Result, E->getType()))
       return false;
     return Success(Result, E);
   }
+  case BO_Mul: {
+    bool AddOverflow, ConversionOverflow;
+    APFixedPoint Result = LHSFX.mul(RHSFX, &AddOverflow)
+                               .convert(ResultFXSema, &ConversionOverflow);
+    if ((AddOverflow || ConversionOverflow) &&
+        !HandleOverflow(Info, E, Result, E->getType()))
+      return false;
+    return Success(Result, E);
+  }
   default:
     return false;
   }
   llvm_unreachable("Should've exited before this");
 }
 
 //===----------------------------------------------------------------------===//
 // Float Evaluation

clang/lib/Basic/FixedPoint.cpp

APFixedPoint APFixedPoint::sub(const APFixedPoint &Other,
   }
 
   if (Overflow)
     *Overflow = Overflowed;
 
   return APFixedPoint(Result, CommonFXSema);
 }
 
+APFixedPoint APFixedPoint::mul(const APFixedPoint &Other,
+                               bool *Overflow) const {
+  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
+  APFixedPoint ConvertedThis = convert(CommonFXSema);
+  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
+  llvm::APSInt ThisVal = ConvertedThis.getValue();
+  llvm::APSInt OtherVal = ConvertedOther.getValue();
+  bool Overflowed = false;
+
+  // Widen the LHS and RHS so we can perform a full multiplication.
+  unsigned Wide = CommonFXSema.getWidth() * 2;
+  if (CommonFXSema.isSigned()) {
+    ThisVal = ThisVal.sextOrSelf(Wide);
+    OtherVal = OtherVal.sextOrSelf(Wide);
+  } else {
+    ThisVal = ThisVal.zextOrSelf(Wide);
+    OtherVal = OtherVal.zextOrSelf(Wide);
+  }
+
+  // Perform the full multiplication and downscale to get the same scale.
+  //
+  // Note that the right shifts here perform an implicit downwards rounding.
+  // This rounding could discard bits that would technically place the result
+  // outside the representable range. We interpret the spec as allowing us to
+  // perform the rounding step first, avoiding the overflow case that would
+  // arise.
+  llvm::APSInt Result;
+  if (CommonFXSema.isSigned())
+    Result = ThisVal.smul_ov(OtherVal, Overflowed)
+                    .ashr(CommonFXSema.getScale());
+  else
+    Result = ThisVal.umul_ov(OtherVal, Overflowed)
+                    .lshr(CommonFXSema.getScale());
+  assert(!Overflowed && "Full multiplication cannot overflow!");
+  Result.setIsSigned(CommonFXSema.isSigned());
+
+  // If our result lies outside of the representative range of the common
+  // semantic, we either have overflow or saturation.
+  llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
+                                                       .extOrTrunc(Wide);
+  llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
+                                                       .extOrTrunc(Wide);
+  if (CommonFXSema.isSaturated()) {
+    if (Result < Min)
+      Result = Min;
+    else if (Result > Max)
+      Result = Max;
+  } else
+    Overflowed = Result < Min || Result > Max;
+
+  if (Overflow)
+    *Overflow = Overflowed;
+
+  return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
+                      CommonFXSema);
+}
+
 void APFixedPoint::toString(llvm::SmallVectorImpl<char> &Str) const {
   llvm::APSInt Val = getValue();
   unsigned Scale = getScale();
 
   if (Val.isSigned() && Val.isNegative() && Val != -Val) {
     Val = -Val;
     Str.push_back('-');
   }

clang/test/Frontend/fixed_point_mul.c

 // RUN: %clang_cc1 -ffixed-point -triple x86_64-unknown-linux-gnu -S -emit-llvm %s -o - | FileCheck %s --check-prefixes=CHECK,SIGNED
 // RUN: %clang_cc1 -ffixed-point -triple x86_64-unknown-linux-gnu -fpadding-on-unsigned-fixed-point -S -emit-llvm %s -o - | FileCheck %s --check-prefixes=CHECK,UNSIGNED
 
+// Multiplication between different fixed point types
+short _Accum sa_const = 2.0hk * 2.0hk;  // CHECK-DAG: @sa_const  = {{.*}}global i16 512, align 2
+_Accum a_const = 3.0hk * 2.0k;          // CHECK-DAG: @a_const   = {{.*}}global i32 196608, align 4
+long _Accum la_const = 4.0hk * 2.0lk;   // CHECK-DAG: @la_const  = {{.*}}global i64 17179869184, align 8
+short _Accum sa_const2 = 0.5hr * 2.0hk; // CHECK-DAG: @sa_const2  = {{.*}}global i16 128, align 2
+short _Accum sa_const3 = 0.5r * 3.0hk;  // CHECK-DAG: @sa_const3  = {{.*}}global i16 192, align 2
+short _Accum sa_const4 = 0.5lr * 4.0hk; // CHECK-DAG: @sa_const4  = {{.*}}global i16 256, align 2
+
+// Unsigned multiplication
+unsigned short _Accum usa_const = 1.0uhk * 2.0uhk;
+// CHECK-SIGNED-DAG:   @usa_const = {{.*}}global i16 768, align 2
+// CHECK-UNSIGNED-DAG: @usa_const = {{.*}}global i16 384, align 2
+
+// Unsigned * signed
+short _Accum sa_const5 = 20.0uhk * 3.0hk;
+// CHECK-DAG: @sa_const5 = {{.*}}global i16 7680, align 2
+
+// Multiplication with negative number
+short _Accum sa_const6 = 0.5hr * (-2.0hk);
+// CHECK-DAG: @sa_const6 = {{.*}}global i16 -128, align 2
+
+// Int multiplication
+unsigned short _Accum usa_const2 = 5 * 10.5uhk;
+// CHECK-SIGNED-DAG:   @usa_const2 = {{.*}}global i16 640, align 2
+// CHECK-UNSIGNED-DAG: @usa_const2 = {{.*}}global i16 320, align 2
+short _Accum sa_const7 = 3 * (-0.5hk);   // CHECK-DAG: @sa_const7 = {{.*}}global i16 -192, align 2
+short _Accum sa_const8 = 100 * (-2.0hk); // CHECK-DAG: @sa_const8 = {{.*}}global i16 -25600, align 2
+long _Fract lf_const = -0.25lr * 3;      // CHECK-DAG: @lf_const  = {{.*}}global i32 -1610612736, align 4
+
+// Saturated multiplication
+_Sat short _Accum sat_sa_const = (_Sat short _Accum)128.0hk * 3.0hk;
+// CHECK-DAG: @sat_sa_const = {{.*}}global i16 32767, align 2
+_Sat unsigned short _Accum sat_usa_const = (_Sat unsigned short _Accum)128.0uhk * 128.0uhk;
+// CHECK-SIGNED-DAG:   @sat_usa_const = {{.*}}global i16 65535, align 2
+// CHECK-UNSIGNED-DAG: @sat_usa_const = {{.*}}global i16 32767, align 2
+_Sat short _Accum sat_sa_const2 = (_Sat short _Accum)128.0hk * -128;
+// CHECK-DAG: @sat_sa_const2 = {{.*}}global i16 -32768, align 2
+_Sat unsigned short _Accum sat_usa_const2 = (_Sat unsigned short _Accum)128.0uhk * 30;
+// CHECK-SIGNED-DAG:   @sat_usa_const2 = {{.*}}global i16 65535, align 2
+// CHECK-UNSIGNED-DAG: @sat_usa_const2 = {{.*}}global i16 32767, align 2
+_Sat unsigned short _Accum sat_usa_const3 = (_Sat unsigned short _Accum)0.5uhk * (-2);
+// CHECK-DAG:   @sat_usa_const3 = {{.*}}global i16 0, align 2
+
 void SignedMultiplication() {
   // CHECK-LABEL: SignedMultiplication
   short _Accum sa;
   _Accum a, b, c, d;
   long _Accum la;
   unsigned short _Accum usa;
   unsigned _Accum ua;
   unsigned long _Accum ula;