[Fixed Point Arithmetic] Validation Test for Saturated Subtraction on Signed _Fracts

[leonardchan]

Summary

This patch includes the logic for subtraction on saturated _Fract types and a test for thm.

• Overflow occurs when the sign bit or MSB of the LHS is different from the resulting sign, depending on the sign of the RHS. Cap at the max value for the type if the LHS is positive, but subtracting a negative number makes the result negative. Cap at the min value if the LHS is negative, but subtracting a positive number makes the result positive.
• Also fixed incorrect minimum value for each _Fract type
• Getters for each fixed point min and max value for a given type
• Correction when casting from a fixed point to a float. If the fixed point data and sign bits do not take up the whole width of the integer (ie. has padding), we will need to either zero out the padding or extend the sign into the padding if it is negative to ensure the correct floating point value is produced after casting.

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 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);
+
 // For a given fixed point type, if the type is unsaturated,
 // return the saturated equivalent of it. Otherwise if it is
 // 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);
 
 } // namespace clang
 
 #endif // LLVM_CLANG_AST_TYPE_H

include/clang/Basic/FixedPoint.h.in

 #define SACCUM_MIN_AS_INT       (1ULL << (BUILTIN_SACCUM_FBIT + BUILTIN_SACCUM_IBIT))
 #define ACCUM_MIN_AS_INT        (1ULL << (BUILTIN_ACCUM_FBIT + BUILTIN_ACCUM_IBIT))
 #define LACCUM_MIN_AS_INT       (1ULL << (BUILTIN_LACCUM_FBIT + BUILTIN_LACCUM_IBIT))
 #define USACCUM_MIN_AS_INT      0ULL
 #define UACCUM_MIN_AS_INT       0ULL
 #define ULACCUM_MIN_AS_INT      0ULL
 
 // Min values of each _Fract type as integer bytes
-#define SFRACT_MIN_AS_INT       (1ULL << BUILTIN_SFRACT_FBIT)
-#define FRACT_MIN_AS_INT        (1ULL << BUILTIN_FRACT_FBIT)
-#define LFRACT_MIN_AS_INT       (1ULL << BUILTIN_LFRACT_FBIT)
+#define SFRACT_MIN_AS_INT       (-SFRACT_MAX_AS_INT - 1)
+#define FRACT_MIN_AS_INT        (-FRACT_MAX_AS_INT - 1)
+#define LFRACT_MIN_AS_INT       (-LFRACT_MAX_AS_INT - 1)
 #define USFRACT_MIN_AS_INT      0ULL
 #define UFRACT_MIN_AS_INT       0ULL
 #define ULFRACT_MIN_AS_INT      0ULL
 
 /************ Fixed Point Bitmasks ******************/
 
 // Used to capture only the relevant bits when comparing with other types
 

lib/AST/Type.cpp

switch (BT->getKind()) {
     case BuiltinType::SatUFract:
       return Context.SatFractTy;
 
     case BuiltinType::SatLongFract:
     case BuiltinType::SatULongFract:
       return Context.SatLongFractTy;
   }
 }
+
+uint64_t clang::getFixedPointMaxVal(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_MAX_AS_INT;
+    case BuiltinType::Accum:
+    case BuiltinType::SatAccum:
+       return ACCUM_MAX_AS_INT;
+    case BuiltinType::LongAccum:
+    case BuiltinType::SatLongAccum:
+       return LACCUM_MAX_AS_INT;
+    case BuiltinType::UShortAccum:
+    case BuiltinType::SatUShortAccum:
+       return USACCUM_MAX_AS_INT;
+    case BuiltinType::UAccum:
+    case BuiltinType::SatUAccum:
+       return UACCUM_MAX_AS_INT;
+    case BuiltinType::ULongAccum:
+    case BuiltinType::SatULongAccum:
+       return ULACCUM_MAX_AS_INT;
+    case BuiltinType::ShortFract:
+    case BuiltinType::SatShortFract:
+       return SFRACT_MAX_AS_INT;
+    case BuiltinType::Fract:
+    case BuiltinType::SatFract:
+       return FRACT_MAX_AS_INT;
+    case BuiltinType::LongFract:
+    case BuiltinType::SatLongFract:
+       return LFRACT_MAX_AS_INT;
+    case BuiltinType::UShortFract:
+    case BuiltinType::SatUShortFract:
+       return USFRACT_MAX_AS_INT;
+    case BuiltinType::UFract:
+    case BuiltinType::SatUFract:
+       return UFRACT_MAX_AS_INT;
+    case BuiltinType::ULongFract:
+    case BuiltinType::SatULongFract:
+       return ULFRACT_MAX_AS_INT;
+  }
+}
+
+uint64_t clang::getFixedPointMinVal(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_MIN_AS_INT;
+    case BuiltinType::Accum:
+    case BuiltinType::SatAccum:
+       return ACCUM_MIN_AS_INT;
+    case BuiltinType::LongAccum:
+    case BuiltinType::SatLongAccum:
+       return LACCUM_MIN_AS_INT;
+    case BuiltinType::UShortAccum:
+    case BuiltinType::SatUShortAccum:
+       return USACCUM_MIN_AS_INT;
+    case BuiltinType::UAccum:
+    case BuiltinType::SatUAccum:
+       return UACCUM_MIN_AS_INT;
+    case BuiltinType::ULongAccum:
+    case BuiltinType::SatULongAccum:
+       return ULACCUM_MIN_AS_INT;
+    case BuiltinType::ShortFract:
+    case BuiltinType::SatShortFract:
+       return SFRACT_MIN_AS_INT;
+    case BuiltinType::Fract:
+    case BuiltinType::SatFract:
+       return FRACT_MIN_AS_INT;
+    case BuiltinType::LongFract:
+    case BuiltinType::SatLongFract:
+       return LFRACT_MIN_AS_INT;
+    case BuiltinType::UShortFract:
+    case BuiltinType::SatUShortFract:
+       return USFRACT_MIN_AS_INT;
+    case BuiltinType::UFract:
+    case BuiltinType::SatUFract:
+       return UFRACT_MIN_AS_INT;
+    case BuiltinType::ULongFract:
+    case BuiltinType::SatULongFract:
+       return ULFRACT_MIN_AS_INT;
+  }
+}

lib/CodeGen/CGExprScalar.cpp

#undef VISITCOMP
   Value *VisitObjCArrayLiteral(ObjCArrayLiteral *E) {
     return CGF.EmitObjCArrayLiteral(E);
   }
   Value *VisitObjCDictionaryLiteral(ObjCDictionaryLiteral *E) {
     return CGF.EmitObjCDictionaryLiteral(E);
   }
   Value *VisitAsTypeExpr(AsTypeExpr *CE);
   Value *VisitAtomicExpr(AtomicExpr *AE);
+
+  // For all fixed point values, we usually do not care about the padding bits,
+  // but if we convert to another type dependent on the whole value of the
+  // underlying type, we will need to either zero extend or sign extend.
+  llvm::Value* FixedPointExtendSignToPadding(const QualType& Ty, llvm::Value* Val);
 };
 }  // end anonymous namespace.
 
 //===----------------------------------------------------------------------===//
 //                                Utilities
 //===----------------------------------------------------------------------===//
 
 /// EmitConversionToBool - Convert the specified expression value to a
if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(CE)) {
     // And that glvalue casts are never null.
     if (ICE->getValueKind() != VK_RValue)
       return false;
   }
 
   return true;
 }
 
+// For all fixed point values, we usually do not care about the padding bits,
+// but if we convert to another type dependent on the whole value of the
+// underlying type, we will need to either zero extend or sign extend.
+llvm::Value* ScalarExprEmitter::FixedPointExtendSignToPadding(const QualType& Ty,
+                                                              llvm::Value* Val) {
+  assert(Ty->isFixedPointType());
+
+  llvm::Type *opTy = CGF.CGM.getTypes().ConvertType(Ty);
+  unsigned BitWidth = opTy->getIntegerBitWidth();
+  unsigned fbits = getFixedPointFBits(Ty);
+  unsigned ibits = getFixedPointIBits(Ty);
+
+  if (Ty->isSignedFixedPointType()) {
+    assert((BitWidth >= fbits + ibits + 1) &&
+           "Cannot fit signed fixed point bits into integral type");
+
+    unsigned ShiftBits = BitWidth - (fbits + ibits + 1);
+    if (!ShiftBits) {
+      return Val;
+    }
+
+    return Builder.CreateAShr(Builder.CreateShl(Val, ShiftBits), ShiftBits);
+  } else {
+    assert((BitWidth >= fbits + ibits) &&
+           "Cannot fit unsigned fixed point bits into integral type");
+
+    unsigned ShiftBits = BitWidth - (fbits + ibits);
+    if (!ShiftBits) {
+      return Val;
+    }
+
+    return Builder.CreateLShr(Builder.CreateShl(Val, ShiftBits), ShiftBits);
+  }
+}
+
 // VisitCastExpr - Emit code for an explicit or implicit cast.  Implicit casts
 // have to handle a more broad range of conversions than explicit casts, as they
 // handle things like function to ptr-to-function decay etc.
 Value *ScalarExprEmitter::VisitCastExpr(CastExpr *CE) {
   Expr *E = CE->getSubExpr();
   QualType DestTy = CE->getType();
   CastKind Kind = CE->getCastKind();
 
case CK_IntegralToFixedPoint: {
     return Builder.CreateShl(EmitScalarConversion(Visit(E), E->getType(), DestTy, CE->getExprLoc()),
                              getFixedPointFBits(DestTy), "int_to_fixed");
   }
 
   case CK_FixedPointToFloating: {
     assert(DestTy->isFloatingType());
     assert(E->getType()->isFixedPointType());
     unsigned fbits = getFixedPointFBits(E->getType());
-    return Builder.CreateFDiv(EmitScalarConversion(Visit(E), E->getType(), DestTy, CE->getExprLoc()),
-                              llvm::ConstantFP::get(CGF.CGM.FloatTy, (1ULL << fbits) * 1.0));
+
+    llvm::Value *Val = FixedPointExtendSignToPadding(E->getType(), Visit(E));
+    Val = EmitScalarConversion(Val, E->getType(), DestTy, CE->getExprLoc());
+
+    return Builder.CreateFDiv(
+        Val, llvm::ConstantFP::get(CGF.CGM.FloatTy, (1ULL << fbits) * 1.0));
   }
 
   case CK_IntegralCast:
   case CK_IntegralToFloating:
   case CK_FloatingToIntegral:
   case CK_FloatingCast:
     return EmitScalarConversion(Visit(E), E->getType(), DestTy,
                                 CE->getExprLoc());
Value *ScalarExprEmitter::EmitAdd(const BinOpInfo &op) {
   }
 
   if (op.Ty->isSaturatedFixedPointType()) {
     llvm::Type *opTy = CGF.CGM.getTypes().ConvertType(op.Ty);
 
     assert(op.LHS->getType() == op.RHS->getType());
     assert(op.LHS->getType() == opTy);
 
-    llvm::Value *SatMaxVal;
-    llvm::Value *SatMinVal;
-
-    const auto &BT = op.Ty->getAs<BuiltinType>();
-    switch (BT->getKind()) {
-      default: llvm_unreachable("Unhandled saturated signed fixed point type");
-      case BuiltinType::SatShortAccum:
-         SatMaxVal = llvm::ConstantInt::get(opTy, SACCUM_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, SACCUM_MIN_AS_INT);
-         break;
-      case BuiltinType::SatAccum:
-         SatMaxVal = llvm::ConstantInt::get(opTy, ACCUM_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, ACCUM_MIN_AS_INT);
-         break;
-      case BuiltinType::SatLongAccum:
-         SatMaxVal = llvm::ConstantInt::get(opTy, LACCUM_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, LACCUM_MIN_AS_INT);
-         break;
-      case BuiltinType::SatUShortAccum:
-         SatMaxVal = llvm::ConstantInt::get(opTy, USACCUM_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, USACCUM_MIN_AS_INT);
-         break;
-      case BuiltinType::SatUAccum:
-         SatMaxVal = llvm::ConstantInt::get(opTy, UACCUM_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, UACCUM_MIN_AS_INT);
-         break;
-      case BuiltinType::SatULongAccum:
-         SatMaxVal = llvm::ConstantInt::get(opTy, ULACCUM_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, ULACCUM_MIN_AS_INT);
-         break;
-      case BuiltinType::SatShortFract:
-         SatMaxVal = llvm::ConstantInt::get(opTy, SFRACT_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, SFRACT_MIN_AS_INT);
-         break;
-      case BuiltinType::SatFract:
-         SatMaxVal = llvm::ConstantInt::get(opTy, FRACT_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, FRACT_MIN_AS_INT);
-         break;
-      case BuiltinType::SatLongFract:
-         SatMaxVal = llvm::ConstantInt::get(opTy, LFRACT_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, LFRACT_MIN_AS_INT);
-         break;
-      case BuiltinType::SatUShortFract:
-         SatMaxVal = llvm::ConstantInt::get(opTy, USFRACT_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, USFRACT_MIN_AS_INT);
-         break;
-      case BuiltinType::SatUFract:
-         SatMaxVal = llvm::ConstantInt::get(opTy, UFRACT_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, UFRACT_MIN_AS_INT);
-         break;
-      case BuiltinType::SatULongFract:
-         SatMaxVal = llvm::ConstantInt::get(opTy, ULFRACT_MAX_AS_INT);
-         SatMinVal = llvm::ConstantInt::get(opTy, ULFRACT_MIN_AS_INT);
-         break;
-    }
+    llvm::Value *SatMaxVal = llvm::ConstantInt::get(
+        opTy, getFixedPointMaxVal(op.Ty));
+    llvm::Value *SatMinVal = llvm::ConstantInt::get(
+        opTy, getFixedPointMinVal(op.Ty));
 
     unsigned MSBBitShift;
     if (op.Ty->isSignedFixedPointType()) {
       MSBBitShift = getFixedPointIBits(op.Ty) + getFixedPointFBits(op.Ty);
     } else {
       MSBBitShift = getFixedPointIBits(op.Ty) + getFixedPointFBits(op.Ty) - 1;
     }
 
if (!op.LHS->getType()->isPointerTy()) {
     if (op.LHS->getType()->isFPOrFPVectorTy()) {
       // Try to form an fmuladd.
       if (Value *FMulAdd = tryEmitFMulAdd(op, CGF, Builder, true))
         return FMulAdd;
       Value *V = Builder.CreateFSub(op.LHS, op.RHS, "sub");
       return propagateFMFlags(V, op);
     }
 
+    if (op.Ty->isSaturatedFixedPointType()) {
+      llvm::Type *opTy = CGF.CGM.getTypes().ConvertType(op.Ty);
+
+      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));
+
+      unsigned MSBBitShift;
+      if (op.Ty->isSignedFixedPointType()) {
+        MSBBitShift = getFixedPointIBits(op.Ty) + getFixedPointFBits(op.Ty);
+      } else {
+        MSBBitShift = getFixedPointIBits(op.Ty) + getFixedPointFBits(op.Ty) - 1;
+      }
+
+      llvm::Value *Diff = Builder.CreateSub(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(Diff, MSBBitShift);
+
+      if (op.Ty->isSignedFixedPointType()) {
+        // Cap at max if the LHS MSB is 0 and the RHS MSB is 1 and the result
+        // MSB is 1
+        llvm::Value *UseSatMax = Builder.CreateAnd(
+            Builder.CreateNot(LHSMSB),
+            Builder.CreateAnd(RHSMSB, ResultMSB));
+        UseSatMax = Builder.CreateIntCast(
+            UseSatMax,
+            llvm::Type::getInt1Ty(ResultMSB->getContext()), /*isSigned=*/true);
+
+        // Cap at min if the LHS MSB is 1 and the RHS MSB is 0 and the result
+        // MSB is 0
+        llvm::Value *UseSatMin = Builder.CreateAnd(
+            LHSMSB,
+            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);
+        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 (!op.RHS->getType()->isPointerTy())
     return emitPointerArithmetic(CGF, op, CodeGenFunction::IsSubtraction);
 

test/Frontend/fixed_point_all_builtin_operations.c

#define BINARY_OPS(TYPE, ID, SUFFIX) \
   BINARY_OPS_FOR_TYPE(_Sat signed TYPE, SatSigned ## ID, SUFFIX); \
   BINARY_OPS_FOR_TYPE(_Sat unsigned TYPE, SatUnsigned ## ID, u ## SUFFIX);
 
 #define FRACT_SAT_BINARY_OPS(TYPE, ID, SUFFIX) \
   { \
     TYPE a = 0.7 ## SUFFIX; \
     TYPE b = 0.9 ## SUFFIX; \
     ASSERT(add ## ID(a, b) == 1.0 ## SUFFIX); \
+    a = -0.7 ## 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); \
   }
 
 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;
 }