[Fixed Point Arithmetic] Validation Test for Saturated Division and Comparison Fix

[leonardchan]

Summary

This patch includes changes for division on saturated fixed point types. Overflow occurs when the resulting value cannot fit into the number of data bits for the resulting type.

For signed division, we cap at the max value of the type when the dividend sign is positive, divisor sign is negative, but the quotient is still positive. Reciprocally, we cap at the min value if the dividend is negative, divisor is positive, and quotient is negative.

For unsigned division, overflow occurs if the resulting value exceeds the max possible value that this type can hold.

The logic for comparisons between fixed point types was also fixed to account for padding bits. Since the padding bits contains values we do not care about, we mask the fixed point data bits in the underlying integral that we do care about and compare them.

include/clang/AST/Type.h

 // saturated, return back the type itself.
 QualType getCorrespondingSaturatedFixedPointType(ASTContext &Context, const Type& Ty);
 
 // For a given fixed point type, if the type is unsigned,
 // return the signed equivalent of it. Otherwise if it is
 // signed, return back the type itself.
 QualType getCorrespondingSignedFixedPointType(ASTContext &Context, const Type& Ty);
 
+// For a given fixed point type, return the number of bits that the type uses.
+// This includes the sign, integral, and fractional bits, and excludes the
+// padding bits.
+uint64_t getFixedPointBitMask(const QualType& Ty);
+
 } // namespace clang
 
 #endif // LLVM_CLANG_AST_TYPE_H

include/clang/Basic/FixedPoint.h.in

 
 /************ Fixed Point Bitmasks ******************/
 
 // Used to capture only the relevant bits when comparing with other types
 
 // _Accum bitmasks
 #define SACCUM_MASK             ((1ULL << (BUILTIN_SACCUM_FBIT + BUILTIN_SACCUM_IBIT + 1)) - 1)
 #define ACCUM_MASK              ((1ULL << (BUILTIN_ACCUM_FBIT + BUILTIN_ACCUM_IBIT + 1)) - 1)
-#define LACCUM_MASK             ((1ULL << (BUILTIN_LACCUM_FBIT + BUILTIN_LACCUM_IBIT + 1)) - 1)
-#define USACCUM_MASK            ((1ULL << (BUILTIN_USACCUM_FBIT + BUILTIN_USACCUM_IBIT)) - 1)
-#define UACCUM_MASK             ((1ULL << (BUILTIN_UACCUM_FBIT + BUILTIN_UACCUM_IBIT)) - 1)
-#define ULACCUM_MASK            ((1ULL << (BUILTIN_ULACCUM_FBIT + BUILTIN_ULACCUM_IBIT)) - 1)
+#define LACCUM_MASK             ((static_cast<__int128_t>(1ULL) << (BUILTIN_LACCUM_FBIT + BUILTIN_LACCUM_IBIT + 1)) - 1)
+#define USACCUM_MASK            USACCUM_MAX_AS_INT
+#define UACCUM_MASK             UACCUM_MAX_AS_INT
+#define ULACCUM_MASK            ULACCUM_MAX_AS_INT
 
 // _Fract bitmasks
 #define SFRACT_MASK             ((1ULL << (BUILTIN_SFRACT_FBIT + 1)) - 1)
 #define FRACT_MASK              ((1ULL << (BUILTIN_FRACT_FBIT + 1)) - 1)
 #define LFRACT_MASK             ((1ULL << (BUILTIN_LFRACT_FBIT + 1)) - 1)
-#define USFRACT_MASK            ((1ULL << BUILTIN_USFRACT_FBIT) - 1)
-#define UFRACT_MASK             ((1ULL << BUILTIN_UFRACT_FBIT) - 1)
-#define ULFRACT_MASK            ((1ULL << BUILTIN_ULFRACT_FBIT) - 1)
+#define USFRACT_MASK            USFRACT_MAX_AS_INT
+#define UFRACT_MASK             UFRACT_MAX_AS_INT
+#define ULFRACT_MASK            ULFRACT_MAX_AS_INT
 
 #endif

lib/AST/Type.cpp

switch (BT->getKind()) {
     case BuiltinType::UFract:
     case BuiltinType::SatUFract:
        return UFRACT_MIN_AS_INT;
     case BuiltinType::ULongFract:
     case BuiltinType::SatULongFract:
        return ULFRACT_MIN_AS_INT;
   }
 }
+
+uint64_t clang::getFixedPointBitMask(const QualType& Ty) {
+  assert(Ty->isFixedPointType());
+  const auto &BT = Ty->getAs<BuiltinType>();
+  switch (BT->getKind()) {
+    default: llvm_unreachable("Unhandled fixed point type");
+    case BuiltinType::ShortAccum:
+    case BuiltinType::SatShortAccum:
+       return SACCUM_MASK;
+    case BuiltinType::Accum:
+    case BuiltinType::SatAccum:
+       return ACCUM_MASK;
+    case BuiltinType::LongAccum:
+    case BuiltinType::SatLongAccum:
+       return LACCUM_MASK;
+    case BuiltinType::UShortAccum:
+    case BuiltinType::SatUShortAccum:
+       return USACCUM_MASK;
+    case BuiltinType::UAccum:
+    case BuiltinType::SatUAccum:
+       return UACCUM_MASK;
+    case BuiltinType::ULongAccum:
+    case BuiltinType::SatULongAccum:
+       return ULACCUM_MASK;
+    case BuiltinType::ShortFract:
+    case BuiltinType::SatShortFract:
+       return SFRACT_MASK;
+    case BuiltinType::Fract:
+    case BuiltinType::SatFract:
+       return FRACT_MASK;
+    case BuiltinType::LongFract:
+    case BuiltinType::SatLongFract:
+       return LFRACT_MASK;
+    case BuiltinType::UShortFract:
+    case BuiltinType::SatUShortFract:
+       return USFRACT_MASK;
+    case BuiltinType::UFract:
+    case BuiltinType::SatUFract:
+       return UFRACT_MASK;
+    case BuiltinType::ULongFract:
+    case BuiltinType::SatULongFract:
+       return ULFRACT_MASK;
+  }
+}

lib/CodeGen/CGExprScalar.cpp

if (Ops.Ty->isFixedPointType()){
     QualType LHSTy = LHS->getType();
     QualType RHSTy = RHS->getType();
 
     // At least one side should be implicitely casted up to fixed point
     assert(LHSTy->isFixedPointType() && RHSTy->isFixedPointType());
     assert(LHSTy == RHSTy);
 
     bool isSignedResult = LHSTy->isSignedFixedPointType() || RHSTy->isSignedFixedPointType();
+    unsigned fbits = getFixedPointFBits(Ops.Ty);
+    unsigned ibits = getFixedPointIBits(Ops.Ty);
+    unsigned FixedPointBits;
+    if (isSignedResult) {
+      FixedPointBits = fbits + ibits + 1;
+    } else {
+      FixedPointBits = fbits + ibits;
+    }
 
     // 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);
-    LHSVal = Builder.CreateShl(LHSVal, getFixedPointFBits(LHSTy));
 
+    LHSVal = Builder.CreateShl(LHSVal, fbits);
     llvm::Value* DivResult = Builder.CreateSDiv(LHSVal, RHSVal);
+
+    if (Ops.Ty->isSaturatedFixedPointType()) {
+      llvm::Value *SatMaxVal = llvm::ConstantInt::get(
+          DivResult->getType(), getFixedPointMaxVal(Ops.Ty));
+      llvm::Value *SatMinVal = llvm::ConstantInt::get(
+          DivResult->getType(), 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 division
+      unsigned DividendBits = FixedPointBits + fbits;
+      unsigned BitMask = (1 << 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);
+        llvm::Value *ResultMSB = Builder.CreateIntCast(Builder.CreateLShr(DivResult, MSBBitShift),
+                                                       Int1Ty, /*isSigned=*/true);
+
+        if (Ops.Ty->isAccumFixedPointType()) {
+          // 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(MaskedDivResult, 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(MaskedDivResult,
+                                    llvm::ConstantInt::get(DivResult->getType(), BitMask)));
+
+          DivResult = Builder.CreateSelect(
+              UseSatMax, SatMaxVal, Builder.CreateSelect(UseSatMin, SatMinVal, DivResult));
+        } else {
+          assert(Ops.Ty->isFractFixedPointType());
+
+          // We cap at max if the signs of both operands are the same but the
+          // result is negative.
+          llvm::Value *UseSatMax = Builder.CreateAnd(
+              Builder.CreateICmpEQ(LHSMSB, RHSMSB),
+              ResultMSB);
+
+          // We cap at min if the signs of both operands are different but the
+          // result is positive.
+          llvm::Value *UseSatMin = Builder.CreateAnd(
+              Builder.CreateICmpNE(LHSMSB, RHSMSB),
+              Builder.CreateNot(ResultMSB));
+
+          DivResult = Builder.CreateSelect(UseSatMax, SatMaxVal,
+                                           Builder.CreateSelect(UseSatMin, SatMinVal, DivResult));
+        }
+      } else {
+        assert(Ops.Ty->isUnsignedFixedPointType());
+
+        // Cap at max if the resulting value is greater than the max possible
+        // value.
+        llvm::Value *UseSatMax = Builder.CreateICmpUGT(MaskedDivResult, SatMaxVal);
+        DivResult = Builder.CreateSelect(UseSatMax, SatMaxVal, DivResult);
+      }
+    }
+
     return Builder.CreateIntCast(DivResult, Builder.getIntNTy(LHSWidth), isSignedResult);
   }
 
   if (Ops.LHS->getType()->isFPOrFPVectorTy()) {
     llvm::Value *Val = Builder.CreateFDiv(Ops.LHS, Ops.RHS, "div");
     if (CGF.getLangOpts().OpenCL &&
         !CGF.CGM.getCodeGenOpts().CorrectlyRoundedDivSqrt) {
       // OpenCL v1.1 s7.4: minimum accuracy of single precision / is 2.5ulp
if (LHSTy->isVectorType() && !E->getType()->isVectorType()) {
       llvm::IntegerType *ResultTy = cast<llvm::IntegerType>(Result->getType());
       if (ResultTy->getBitWidth() > 1 &&
           E->getType() == CGF.getContext().BoolTy)
         Result = Builder.CreateTrunc(Result, Builder.getInt1Ty());
       return EmitScalarConversion(Result, CGF.getContext().BoolTy, E->getType(),
                                   E->getExprLoc());
     }
 
-    if (LHS->getType()->isFPOrFPVectorTy()) {
+    if (LHSTy->isFixedPointType() || RHSTy->isFixedPointType()) {
+      assert(LHSTy == RHSTy);
+      bool Signed = LHSTy->isSignedFixedPointType();
+      unsigned FixedPointBits = getFixedPointFBits(LHSTy) + getFixedPointIBits(LHSTy);
+      if (Signed) ++FixedPointBits;
+
+      // Will need to remove any padding bits. If the value is signed, we will
+      // need to extend the sign into the padding.
+      if (Signed) {
+        unsigned BitWidth = LHS->getType()->getIntegerBitWidth();
+        unsigned PaddingBits = BitWidth - FixedPointBits;
+        if (PaddingBits) {
+          llvm::Value *MaskedLHS = Builder.CreateAShr(Builder.CreateShl(LHS, PaddingBits),
+                                                      PaddingBits, "Corrected LHS");
+          llvm::Value *MaskedRHS = Builder.CreateAShr(Builder.CreateShl(RHS, PaddingBits),
+                                                      PaddingBits, "Corrected RHS");
+          Result = Builder.CreateICmp(SICmpOpc, MaskedLHS, MaskedRHS, "cmp");
+        } else {
+          Result = Builder.CreateICmp(SICmpOpc, LHS, RHS, "cmp");
+        }
+      } else {
+        unsigned BitMask = getFixedPointBitMask(LHSTy);
+        llvm::Value *MaskedLHS = Builder.CreateAnd(LHS, BitMask, "Masked LHS");
+        llvm::Value *MaskedRHS = Builder.CreateAnd(RHS, BitMask, "Masked RHS");
+        Result = Builder.CreateICmp(UICmpOpc, MaskedLHS, MaskedRHS, "cmp");
+      }
+    } else if (LHS->getType()->isFPOrFPVectorTy()) {
       Result = Builder.CreateFCmp(FCmpOpc, LHS, RHS, "cmp");
-    } else if (LHSTy->hasSignedIntegerRepresentation() ||
-               LHSTy->isSignedFixedPointType() ||
-               RHSTy->isSignedFixedPointType()) {
+    } else if (LHSTy->hasSignedIntegerRepresentation()) {
       Result = Builder.CreateICmp(SICmpOpc, LHS, RHS, "cmp");
     } else {
       // Unsigned integers and pointers.
       Result = Builder.CreateICmp(UICmpOpc, LHS, RHS, "cmp");
     }
 
     // If this is a vector comparison, sign extend the result to the appropriate
     // vector integer type and return it (don't convert to bool).

test/Frontend/fixed_point_all_builtin_operations.c

#define FRACT_SAT_BINARY_OPS(TYPE, ID, 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); \
+    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); \
   }
 
 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;
 }

test/Frontend/fixed_point_validation.c

int main(){
   /**************** Simple Comparisons ***************/
 
   assert(s_accum == 0);
   // CHECK:      {{.*}} = load i16, i16* %s_accum, align 2
   // CHECK-NEXT: {{.*}} = icmp eq i16 {{.*}}, 0
 
   s_accum = s_accum2;
   // CHECK:      {{.*}} = load i16, i16* %s_accum2, align 2
-  // CHECK-NEXT: store i16 %1, i16* %s_accum, align 2
+  // CHECK-NEXT: store i16 {{.*}}, i16* %s_accum, align 2
 
   assert(s_accum == s_accum2);
   // CHECK:      {{.*}} = load i16, i16* %s_accum, align 2
   // CHECK-NEXT: {{.*}} = load i16, i16* %s_accum2, align 2
   // CHECK-NEXT: {{.*}} = icmp eq i16 {{.*}}, {{.*}}
 
   assert(s_accum2 == s_accum);
   // CHECK:      {{.*}} = load i16, i16* %s_accum2, align 2
int main(){
   assert(s_fract == -s_fract2);
 
   assert(s_fract > s_fract2);
   // CHECK:      {{.*}} = load i16, i16* %s_fract, align 2
   // CHECK:      {{.*}} = load i16, i16* %s_fract2, align 2
   // CHECK:      {{.*}} = icmp sgt i16 {{.*}}, {{.*}}
 
   assert(s_fract2 < s_fract);
-  // CHECK:      {{.*}} = load i16, i16* %s_fract2, align 2
-  // CHECK-NEXT: {{.*}} = load i16, i16* %s_fract, align 2
-  // CHECK-NEXT: {{.*}} = icmp slt i16 {{.*}}, {{.*}}
+  // CHECK:      [[VAL:%.+]] = load i16, i16* %s_fract2, align 2
+  // CHECK-NEXT: [[VAL2:%.+]] = load i16, i16* %s_fract, align 2
+  // CHECK-NEXT: [[SHIFTED_VAL:%.+]] = shl i16 [[VAL]], 8
+  // CHECK-NEXT: [[CORRECTED_VAL:%.+]] = ashr i16 [[SHIFTED_VAL]], 8
+  // CHECK-NEXT: [[SHIFTED_VAL2:%.+]] = shl i16 [[VAL2]], 8
+  // CHECK-NEXT: [[CORRECTED_VAL2:%.+]] = ashr i16 [[SHIFTED_VAL2]], 8
+  // CHECK-NEXT: {{.*}} = icmp slt i16 [[CORRECTED_VAL]], [[CORRECTED_VAL2]]
 
   assert(s_fract >= s_fract);
   // CHECK:      {{.*}} = icmp sge i16 {{.*}}, {{.*}}
 
   assert(s_fract <= s_fract);
   // CHECK:      {{.*}} = icmp sle i16 {{.*}}, {{.*}}
 
   assert(s_fract >= s_fract2);