[Fixed Point Arithmetic] Validation Test for Saturated Multiplication

[leonardchan]

Summary

This patch contains changes for multiplication on saturated _Fract types.

Since we already upcast the underlying integer for the fixed point type, we can do a simple check to see if the resulting value is larger or smaller than the max or min for the fixed point types.

lib/CodeGen/CGExprScalar.cpp

if (Ops.Ty->isFixedPointType()){
       // Round up the bit widths to allocate enough space for calculating the
       // result.
       unsigned LHSWidth = CGF.getContext().getIntWidth(LHSTy);
       unsigned bufferWidth = LHSWidth * 2;
       if (bufferWidth > 128) {
         bufferWidth = 128;
       }
 
-      LHSVal = Builder.CreateIntCast(LHSVal, Builder.getIntNTy(bufferWidth), isSignedResult);
-      RHSVal = Builder.CreateIntCast(RHSVal, Builder.getIntNTy(bufferWidth), isSignedResult);
+      llvm::Type *ResultTy = Builder.getIntNTy(bufferWidth);
+      LHSVal = Builder.CreateIntCast(LHSVal, ResultTy, isSignedResult);
+      RHSVal = Builder.CreateIntCast(RHSVal, ResultTy, isSignedResult);
 
       llvm::Value* MulResult = Builder.CreateMul(LHSVal, RHSVal);
       MulResult = Builder.CreateAShr(MulResult, getFixedPointFBits(Ops.Ty));
+
+      // At this point, MulResult has not been truncated yet and still has extra
+      // assigned bits we can use to check for magnitude overflows.
+      if (Ops.Ty->isSaturatedFixedPointType()) {
+        llvm::Value *SatMaxVal = llvm::ConstantInt::get(
+            ResultTy, getFixedPointMaxVal(Ops.Ty));
+        llvm::Value *SatMinVal = llvm::ConstantInt::get(
+            ResultTy, getFixedPointMinVal(Ops.Ty));
+
+        unsigned FixedPointBits;
+        if (Ops.Ty->isSignedFixedPointType()) {
+          FixedPointBits = getFixedPointIBits(Ops.Ty) + getFixedPointFBits(Ops.Ty) + 1;
+        } else {
+          FixedPointBits = getFixedPointIBits(Ops.Ty) + getFixedPointFBits(Ops.Ty);
+        }
+        unsigned MSBBitShift = FixedPointBits - 1;
+
+        // Number of data + sign bits used in multiplication result after
+        // shifting but before truncation.
+        unsigned UntruncatedBitWidth = FixedPointBits * 2;
+        unsigned BitMask = (1 << UntruncatedBitWidth) - 1;
+        llvm::Value *MaskedMulResult = Builder.CreateAnd(MulResult, BitMask);
+
+        if (Ops.Ty->isSignedFixedPointType()) {
+          if (Ops.Ty->isAccumFixedPointType()) {
+            llvm::Type *Int1Ty = llvm::Type::getInt1Ty(Ops.LHS->getContext());
+            llvm::Value *LHSMSB = Builder.CreateIntCast(Builder.CreateLShr(Ops.LHS, MSBBitShift),
+                                                        Int1Ty, /*isSigned=*/true);
+            llvm::Value *RHSMSB = Builder.CreateIntCast(Builder.CreateLShr(Ops.RHS, MSBBitShift),
+                                                        Int1Ty, /*isSigned=*/true);
+
+            // Cap at max if both operand signs were the same and the result is greater than the
+            // max possible value.
+            llvm::Value *UseSatMax = Builder.CreateAnd(
+                Builder.CreateICmpEQ(LHSMSB, RHSMSB),
+                Builder.CreateICmpUGT(MaskedMulResult, SatMaxVal));
+
+            // Cap at min if the operands were different, and the unsigned
+            // respresentation of the result is greater than the maximum possible
+            // unsigned value that can be represented with the resulting fixed
+            // point bits. Don't use SatMaxVal here since it represents the max
+            // for an signed value.
+            llvm::Value *UseSatMin = Builder.CreateAnd(
+                Builder.CreateXor(LHSMSB, RHSMSB),
+                Builder.CreateICmpUGT(MaskedMulResult, llvm::ConstantInt::get(ResultTy, BitMask)));
+
+            MulResult = Builder.CreateSelect(
+                UseSatMax, SatMaxVal, Builder.CreateSelect(UseSatMin, SatMinVal, MulResult));
+          } else {
+            // The only situation a _Fract overflows is if both are signed and
+            // equal to -1. Signed multiplication would yield a result of -1 when
+            // the result should be 1. Instead return the max possible value.
+            assert(Ops.Ty->isFractFixedPointType());
+
+            unsigned FractMask = (1ULL << FixedPointBits) - 1;
+            llvm::Value *MaskedLHSVal = Builder.CreateAnd(LHSVal, FractMask, "MaskedLHSVal");
+            llvm::Value *MaskedRHSVal = Builder.CreateAnd(RHSVal, FractMask, "MaskedRHSVal");
+            llvm::Value *MaskedMinVal = Builder.CreateAnd(SatMinVal, FractMask, "MaskedMinVal");
+            llvm::Value *UseSatMax = Builder.CreateOr(
+                Builder.CreateICmpEQ(MaskedLHSVal, MaskedMinVal),
+                Builder.CreateICmpEQ(MaskedRHSVal, MaskedMinVal),
+                "UseSatMax");
+            MulResult = Builder.CreateSelect(UseSatMax, SatMaxVal, MulResult);
+          }
+        } else {
+          // Cap at max if the resulting value is greater than the max possible
+          // value.
+          llvm::Value *UseSatMax = Builder.CreateICmpUGT(MaskedMulResult, SatMaxVal);
+          MulResult = Builder.CreateSelect(UseSatMax, SatMaxVal, MulResult);
+        }
+      }
+
       return Builder.CreateIntCast(MulResult, Builder.getIntNTy(LHSWidth), isSignedResult);
     }
 
     if (Ops.Ty->isUnsignedIntegerType() &&
         CGF.SanOpts.has(SanitizerKind::UnsignedIntegerOverflow) &&
         !CanElideOverflowCheck(CGF.getContext(), Ops))
       return EmitOverflowCheckedBinOp(Ops);
 

test/Frontend/fixed_point_all_builtin_operations.c

#define FRACT_SAT_BINARY_OPS(TYPE, ID, SUFFIX) \
     b = -0.9 ## SUFFIX; \
     ASSERT(add ## ID(a, b) == -0.5 ## SUFFIX - 0.5 ## SUFFIX); \
     a = 0.7 ## SUFFIX; \
     b = -0.9 ## SUFFIX; \
     ASSERT(sub ## ID(a, b) == 1.0 ## SUFFIX); \
     a = -0.7 ## SUFFIX; \
     b = 0.9 ## SUFFIX; \
     ASSERT(sub ## ID(a, b) == -0.5 ## SUFFIX - 0.5 ## SUFFIX); \
+    a = -0.5 ## SUFFIX - 0.5 ## SUFFIX; \
+    ASSERT(mul ## ID(a, a) == 1.0 ## SUFFIX); \
   }
 
 int main(){
   BINARY_OPS(short _Fract, ShortFract, hr);
   BINARY_OPS(_Fract, Fract, r);
   BINARY_OPS(long _Fract, LongFract, lr);
   BINARY_OPS(short _Accum, ShortAccum, hk);
   BINARY_OPS(_Accum, Accum, k);
   BINARY_OPS(long _Accum, LongAccum, lk);
 
   FRACT_SAT_BINARY_OPS(_Sat short _Fract, SatShortFract, hr);
   FRACT_SAT_BINARY_OPS(_Sat _Fract, SatFract, r);
   FRACT_SAT_BINARY_OPS(_Sat long _Fract, SatLongFract, lr);
 
   return 0;
 }