[Fixed Point Arithmetic] Validation Test for Saturated Shift Left, Saturated Unsigned _Fract Types, and Fix for Saturated Unsigned Addition

[leonardchan]

Summary

This patch includes changes for the shift left operator involving saturated fixed point types.

For unsigned shifting, overflow occurs if the number of bits we shift exceeds the number of leading zeros in the number. This number is found using the intrinsic llvm function ctlz.

For signed shifting, if the number is positive, we cap at the max value for that type if the number of bits we shift exceeds the number of leading zeros. If the number is negative, we cap at the min value for that type if the number of bits we shift exceeds the number of leading ones. ctlz can be used in this case after flipping the bits in the number.

• Saturation tests were also added for saturated unsigned _Fract types.
• Added a fix to unsigned addition for saturated fixed point types where we would not be able to get the overflow if the number of data bits was equal to the underlying integer width. In this case, we need to use the intrinsic function uadd.with.overflow to detect overflow on this carry bit.

include/clang/AST/Type.h

 
 // Return the number of integral bits in a fixed point type.
 unsigned getFixedPointIBits(const Type& Ty);
 
 inline unsigned getFixedPointIBits(const QualType& Ty) {
   return getFixedPointIBits(*Ty);
 }
 
+// Return the number of bits used for this fixed point type. This will count the
+// number of integral, fractional, and sign bits, but ignore padding bits.
+inline unsigned getFixedPointBits(const QualType& Ty) {
+  assert(Ty->isFixedPointType());
+  if (Ty->isSignedFixedPointType()) {
+    return getFixedPointIBits(Ty) + getFixedPointFBits(Ty) + 1;
+  } else {
+    return getFixedPointIBits(Ty) + getFixedPointFBits(Ty);
+  }
+}
+
 // Return the highest possible value for this fixed point type represented as an
 // integer.
 uint64_t getFixedPointMaxVal(const QualType& Ty);
 
 // Return the smallest possible value for this fixed point type represented as an
 // integer.
 uint64_t getFixedPointMinVal(const QualType& Ty);
 

lib/CodeGen/CGExprScalar.cpp

if (DstTy->isFloatingPointTy()) {
         Src = Builder.CreateFPExt(Src, CGF.CGM.FloatTy, "conv");
       }
       SrcType = CGF.getContext().FloatTy;
       SrcTy = CGF.FloatTy;
     }
   }
 
   // Ignore conversions like int -> uint.
-  if (SrcTy == DstTy)
+  // Except for fixed point types which may need radix transformations.
+  bool WorkingOnFixedPoints = DstType->isFixedPointType() && SrcType->isFixedPointType();
+  if (SrcTy == DstTy && !WorkingOnFixedPoints)
     return Src;
 
   // Handle pointer conversions next: pointers can only be converted to/from
   // other pointers and integers. Check for pointer types in terms of LLVM, as
   // some native types (like Obj-C id) may map to a pointer type.
   if (auto DstPT = dyn_cast<llvm::PointerType>(DstTy)) {
     // The source value may be an integer, or a pointer.
     if (isa<llvm::PointerType>(SrcTy))
if (SrcTy->isFloatingPointTy()) {
         return Builder.CreateCall(
             CGF.CGM.getIntrinsic(llvm::Intrinsic::convert_to_fp16, SrcTy), Src);
       // If the half type is supported, just use an fptrunc.
       return Builder.CreateFPTrunc(Src, DstTy);
     }
     DstTy = CGF.FloatTy;
   }
 
-  bool WorkingOnFixedPoints = DstType->isFixedPointType() && SrcType->isFixedPointType();
   int order = WorkingOnFixedPoints ? CGF.getContext().getFixedPointTypeOrder(DstType, SrcType) : 0;
 
   if (WorkingOnFixedPoints && order < 0) {
     // Casting down, so we will need to shift early as to not lose data
     Src = EmitFixedPointRadixShift(Src, SrcType, DstType);
   }
 
   if (isa<llvm::IntegerType>(SrcTy)) {
if (Ops.Ty->isSaturatedFixedPointType()) {
         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 division
       unsigned DividendBits = FixedPointBits + fbits;
-      unsigned BitMask = (1 << DividendBits) - 1;
+      uint64_t BitMask = (static_cast<__int128_t>(1ULL) << DividendBits) - 1;
       llvm::Value *MaskedDivResult = Builder.CreateAnd(DivResult, BitMask);
 
       if (Ops.Ty->isSignedFixedPointType()) {
         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);
if (op.Ty->isSaturatedFixedPointType()) {
     assert(op.LHS->getType() == op.RHS->getType());
     assert(op.LHS->getType() == opTy);
 
     llvm::Value *SatMaxVal = llvm::ConstantInt::get(
         opTy, getFixedPointMaxVal(op.Ty));
     llvm::Value *SatMinVal = llvm::ConstantInt::get(
         opTy, getFixedPointMinVal(op.Ty));
 
+    if (op.Ty->isSignedFixedPointType()) {
       unsigned MSBBitShift;
       if (op.Ty->isSignedFixedPointType()) {
         MSBBitShift = getFixedPointIBits(op.Ty) + getFixedPointFBits(op.Ty);
       } else {
         MSBBitShift = getFixedPointIBits(op.Ty) + getFixedPointFBits(op.Ty) - 1;
       }
 
       llvm::Value *Sum = Builder.CreateAdd(op.LHS, op.RHS);
       llvm::Value *LHSMSB = Builder.CreateLShr(op.LHS, MSBBitShift);
       llvm::Value *RHSMSB = Builder.CreateLShr(op.RHS, MSBBitShift);
       llvm::Value *ResultMSB = Builder.CreateLShr(Sum, MSBBitShift);
 
-    if (op.Ty->isSignedFixedPointType()) {
       // Cap at max if both operand signs were 0 and the result sign is 1
       llvm::Value *UseSatMax = Builder.CreateAnd(
           Builder.CreateNot(Builder.CreateOr(LHSMSB, RHSMSB)),
           ResultMSB);
       UseSatMax = Builder.CreateIntCast(
           UseSatMax,
           llvm::Type::getInt1Ty(ResultMSB->getContext()), /*isSigned=*/true);
 
       // Cap at min if both operand signs were 1 and the result sign is 0
       llvm::Value *UseSatMin = Builder.CreateAnd(
           Builder.CreateAnd(LHSMSB, RHSMSB),
           Builder.CreateNot(ResultMSB));
-      UseSatMin = Builder.CreateIntCast(
-          UseSatMin,
-          llvm::Type::getInt1Ty(ResultMSB->getContext()), /*isSigned=*/true);
+      UseSatMin = Builder.CreateIntCast(UseSatMin, Builder.getInt1Ty(), /*isSigned=*/true);
 
       return Builder.CreateSelect(
           UseSatMax, SatMaxVal, Builder.CreateSelect(UseSatMin, SatMinVal, Sum));
     } else {
-      // Cap at max if the resulting MSB is less than either operand MSB
-      llvm::Value *UseSatMax = Builder.CreateAnd(
-          Builder.CreateOr(LHSMSB, RHSMSB),
-          Builder.CreateNot(ResultMSB));
-      UseSatMax = Builder.CreateIntCast(
-          UseSatMax,
-          llvm::Type::getInt1Ty(ResultMSB->getContext()), /*isSigned=*/true);
-      return Builder.CreateSelect(UseSatMax, SatMaxVal, Sum);
+      // Overflow if the bit after the MSB is set. Use the builtin intrinsic for
+      // detecting overflow on types where there is no padding.
+      llvm::Value *Callee = CGF.CGM.getIntrinsic(llvm::Intrinsic::uadd_with_overflow,
+                                                 op.LHS->getType());
+      llvm::Value *Tmp = CGF.Builder.CreateCall(Callee, {op.LHS, op.RHS});
+      llvm::Value *UnsignedOverflow = CGF.Builder.CreateExtractValue(Tmp, 1);
+      llvm::Value *UnsignedResult = CGF.Builder.CreateExtractValue(Tmp, 0);
+
+      unsigned FixedPointBits = getFixedPointBits(op.Ty);
+      unsigned BitWidth = SatMaxVal->getType()->getIntegerBitWidth();
+      if (FixedPointBits < BitWidth) {
+        llvm::Value *CarryBit = Builder.CreateLShr(UnsignedResult, FixedPointBits);
+        CarryBit = Builder.CreateIntCast(CarryBit, Builder.getInt1Ty(), /*isSigned=*/true);
+        UnsignedOverflow = Builder.CreateOr(UnsignedOverflow, CarryBit);
+      }
+
+      return Builder.CreateSelect(UnsignedOverflow, SatMaxVal, UnsignedResult);
     }
   }
 
   return Builder.CreateAdd(op.LHS, op.RHS, "add");
 }
 
 Value *ScalarExprEmitter::EmitSub(const BinOpInfo &op) {
   // The LHS is always a pointer if either side is.
if (op.Ty->isSaturatedFixedPointType()) {
             Builder.CreateNot(Builder.CreateOr(RHSMSB, ResultMSB)));
         UseSatMin = Builder.CreateIntCast(
             UseSatMin,
             llvm::Type::getInt1Ty(ResultMSB->getContext()), /*isSigned=*/true);
 
         return Builder.CreateSelect(
             UseSatMax, SatMaxVal, Builder.CreateSelect(UseSatMin, SatMinVal, Diff));
       } else {
-        // Cap at min if the LHS MSB is 0 and the resulting MSB is 1
-        llvm::Value *UseSatMin = Builder.CreateAnd(Builder.CreateNot(LHSMSB), ResultMSB);
-        UseSatMin = Builder.CreateIntCast(
-            UseSatMin,
-            llvm::Type::getInt1Ty(ResultMSB->getContext()), /*isSigned=*/true);
+        // Overflowed if the LHS is less than the RHS
+        llvm::Value *UseSatMin = Builder.CreateICmpULT(op.LHS, op.RHS);
         return Builder.CreateSelect(UseSatMin, SatMinVal, Diff);
       }
     }
     return Builder.CreateSub(op.LHS, op.RHS, "sub");
   }
 
   // If the RHS is not a pointer, then we have normal pointer
   // arithmetic.
if (SanitizeBase) {
       BaseCheck->addIncoming(ValidBase, CheckShiftBase);
       Checks.push_back(std::make_pair(BaseCheck, SanitizerKind::ShiftBase));
     }
 
     assert(!Checks.empty());
     EmitBinOpCheck(Checks, Ops);
   }
 
+  if (Ops.Ty->isSaturatedFixedPointType()) {
+    const auto* BinExpr = dyn_cast<BinaryOperator>(Ops.E);
+    const Expr* LHS = BinExpr->getLHS();
+    Value* LHSVal = Ops.LHS;
+    Value* RHSVal = RHS;
+    QualType LHSTy = LHS->getType();
+
+    assert(LHSTy == Ops.Ty);
+
+    llvm::Value *Result = Builder.CreateShl(LHSVal, RHSVal, "Saturated shl");
+    llvm::Value *SatMaxVal = llvm::ConstantInt::get(
+        Result->getType(), getFixedPointMaxVal(Ops.Ty));
+    llvm::Value *SatMinVal = llvm::ConstantInt::get(
+        Result->getType(), getFixedPointMinVal(Ops.Ty));
+
+    uint64_t BitMask = getFixedPointBitMask(Ops.Ty);
+    llvm::Value *MaskedLHS = Builder.CreateAnd(LHSVal, BitMask);
+
+    unsigned BitWidth = LHSVal->getType()->getIntegerBitWidth();
+    unsigned FixedPointBits = getFixedPointBits(Ops.Ty);
+    unsigned MSBBitShift = FixedPointBits - 1;
+    llvm::Value *CTLZFunc = CGF.CGM.getIntrinsic(llvm::Intrinsic::ctlz, Result->getType());
+    llvm::Value *LeadZeroCount = Builder.CreateCall(CTLZFunc, {MaskedLHS, Builder.getTrue()}, "LeadZeroCount");
+
+    // Ignore any padding bits that were zero'd out when masking
+    unsigned PaddingBits = BitWidth - FixedPointBits;
+    LeadZeroCount = Builder.CreateSub(
+        LeadZeroCount, llvm::ConstantInt::get(LeadZeroCount->getType(), PaddingBits), "LeadZeroCount");
+
+    if (Ops.Ty->isSignedFixedPointType()) {
+      llvm::Type *Int1Ty = llvm::Type::getInt1Ty(Ops.LHS->getContext());
+      llvm::Value *LHSMSB = Builder.CreateIntCast(Builder.CreateLShr(Ops.LHS, MSBBitShift),
+                                                  Int1Ty, /*isSigned=*/true, "LHSMSB");
+
+      // Cap at max if the number is positive and the highest order 1 bit after
+      // shifting is at least the number of fixed point bits for this type. This is
+      // equivalent to checking if the number of leading zeros is less than the
+      // amount we want to shift by (after removing any padding).
+      llvm::Value *UseMaxVal = Builder.CreateAnd(
+          Builder.CreateNot(LHSMSB), Builder.CreateICmpUGE(RHSVal, LeadZeroCount), "UseMaxVal");
+
+      // Cap at min if the number is negative and the highest order 0 bit after
+      // shifting exceeds the number of fixed point bits for this type. Similar to
+      // checking for max, but accounting for the sign.
+      llvm::Value *CorrectedVal = Builder.CreateAShr(
+          Builder.CreateShl(LHSVal, PaddingBits), PaddingBits);
+
+      llvm::Value *LeadOneCount = Builder.CreateCall(
+          CTLZFunc, {Builder.CreateNot(CorrectedVal), Builder.getTrue()}, "LeadOneCount");
+      LeadOneCount = Builder.CreateSub(
+          LeadOneCount, llvm::ConstantInt::get(LeadOneCount->getType(), PaddingBits), "LeadOneCount");
+
+      llvm::Value *UseMinVal = Builder.CreateAnd(
+          LHSMSB, Builder.CreateICmpUGE(RHSVal, LeadOneCount), "UseMinVal");
+
+      return Builder.CreateSelect(UseMaxVal, SatMaxVal,
+                                  Builder.CreateSelect(UseMinVal, SatMinVal, Result));
+    } else {
+      // Cap at max if the number is positive and the highest order 1 bit after
+      // shifting exceeds the number of fixed point bits for this type.
+      llvm::Value *UseMaxVal = Builder.CreateICmpUGT(RHSVal, LeadZeroCount, "UseMaxVal");
+      return Builder.CreateSelect(UseMaxVal, SatMaxVal, Result);
+    }
+  }
+
   return Builder.CreateShl(Ops.LHS, RHS, "shl");
 }
 
 Value *ScalarExprEmitter::EmitShr(const BinOpInfo &Ops) {
   // LLVM requires the LHS and RHS to be the same type: promote or truncate the
   // RHS to the same size as the LHS.
   Value *RHS = Ops.RHS;
   if (Ops.LHS->getType() != RHS->getType())

test/Frontend/fixed_point_all_builtin_operations.c

#define FRACT_SAT_BINARY_OPS(TYPE, ID, SUFFIX) \
     a = -0.5 ## SUFFIX - 0.5 ## SUFFIX; \
     ASSERT(mul ## ID(a, a) == 1.0 ## SUFFIX); \
     a = 0.8 ## SUFFIX; \
     b = 0.5 ## SUFFIX; \
     ASSERT(a / b == 1.0 ## SUFFIX); \
     a = -0.8 ## SUFFIX; \
     b = 0.5 ## SUFFIX; \
     ASSERT(a / b == -0.5 ## SUFFIX - 0.5 ## SUFFIX); \
+    a = 0.1 ## SUFFIX; \
+    ASSERT(a << 4 == 1.0 ## SUFFIX); \
+    a = -0.8 ## SUFFIX; \
+    ASSERT(a << 4 == -0.5 ## SUFFIX - 0.5 ## SUFFIX); \
+  }
+
+#define FRACT_SATU_BINARY_OPS(TYPE, ID, SUFFIX) \
+  { \
+    TYPE a = 0.7 ## SUFFIX; \
+    TYPE b = 0.9 ## SUFFIX; \
+    ASSERT(a + b == 1.0 ## SUFFIX); \
+    ASSERT(a - b == 0.0 ## SUFFIX); \
+    ASSERT(b / a == 1.0 ## SUFFIX); \
+    ASSERT(a << 1 == 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);
 
+  FRACT_SATU_BINARY_OPS(_Sat unsigned short _Fract, SatUnsignedShortFract, uhr);
+  FRACT_SATU_BINARY_OPS(_Sat unsigned _Fract, SatUnsignedFract, ur);
+  FRACT_SATU_BINARY_OPS(_Sat unsigned long _Fract, SatUnsignedLongFract, ulr);
+
   return 0;
 }