1//===- FixedPoint.cpp - Fixed point constant handling -----------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9/// \file 10/// Defines the implementation for the fixed point number interface. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/Basic/FixedPoint.h" 15 16namespace clang { 17 18APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema, 19 bool *Overflow) const { 20 llvm::APSInt NewVal = Val; 21 unsigned DstWidth = DstSema.getWidth(); 22 unsigned DstScale = DstSema.getScale(); 23 bool Upscaling = DstScale > getScale(); 24 if (Overflow) 25 *Overflow = false; 26 27 if (Upscaling) { 28 NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale()); 29 NewVal <<= (DstScale - getScale()); 30 } else { 31 NewVal >>= (getScale() - DstScale); 32 } 33 34 auto Mask = llvm::APInt::getBitsSetFrom( 35 NewVal.getBitWidth(), 36 std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth())); 37 llvm::APInt Masked(NewVal & Mask); 38 39 // Change in the bits above the sign 40 if (!(Masked == Mask || Masked == 0)) { 41 // Found overflow in the bits above the sign 42 if (DstSema.isSaturated()) 43 NewVal = NewVal.isNegative() ? Mask : ~Mask; 44 else if (Overflow) 45 *Overflow = true; 46 } 47 48 // If the dst semantics are unsigned, but our value is signed and negative, we 49 // clamp to zero. 50 if (!DstSema.isSigned() && NewVal.isSigned() && NewVal.isNegative()) { 51 // Found negative overflow for unsigned result 52 if (DstSema.isSaturated()) 53 NewVal = 0; 54 else if (Overflow) 55 *Overflow = true; 56 } 57 58 NewVal = NewVal.extOrTrunc(DstWidth); 59 NewVal.setIsSigned(DstSema.isSigned()); 60 return APFixedPoint(NewVal, DstSema); 61} 62 63int APFixedPoint::compare(const APFixedPoint &Other) const { 64 llvm::APSInt ThisVal = getValue(); 65 llvm::APSInt OtherVal = Other.getValue(); 66 bool ThisSigned = Val.isSigned(); 67 bool OtherSigned = OtherVal.isSigned(); 68 unsigned OtherScale = Other.getScale(); 69 unsigned OtherWidth = OtherVal.getBitWidth(); 70 71 unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth); 72 73 // Prevent overflow in the event the widths are the same but the scales differ 74 CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale 75 : OtherScale - getScale(); 76 77 ThisVal = ThisVal.extOrTrunc(CommonWidth); 78 OtherVal = OtherVal.extOrTrunc(CommonWidth); 79 80 unsigned CommonScale = std::max(getScale(), OtherScale); 81 ThisVal = ThisVal.shl(CommonScale - getScale()); 82 OtherVal = OtherVal.shl(CommonScale - OtherScale); 83 84 if (ThisSigned && OtherSigned) { 85 if (ThisVal.sgt(OtherVal)) 86 return 1; 87 else if (ThisVal.slt(OtherVal)) 88 return -1; 89 } else if (!ThisSigned && !OtherSigned) { 90 if (ThisVal.ugt(OtherVal)) 91 return 1; 92 else if (ThisVal.ult(OtherVal)) 93 return -1; 94 } else if (ThisSigned && !OtherSigned) { 95 if (ThisVal.isSignBitSet()) 96 return -1; 97 else if (ThisVal.ugt(OtherVal)) 98 return 1; 99 else if (ThisVal.ult(OtherVal)) 100 return -1; 101 } else { 102 // !ThisSigned && OtherSigned 103 if (OtherVal.isSignBitSet()) 104 return 1; 105 else if (ThisVal.ugt(OtherVal)) 106 return 1; 107 else if (ThisVal.ult(OtherVal)) 108 return -1; 109 } 110 111 return 0; 112} 113 114APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) { 115 bool IsUnsigned = !Sema.isSigned(); 116 auto Val = llvm::APSInt::getMaxValue(Sema.getWidth(), IsUnsigned); 117 if (IsUnsigned && Sema.hasUnsignedPadding()) 118 Val = Val.lshr(1); 119 return APFixedPoint(Val, Sema); 120} 121 122APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) { 123 auto Val = llvm::APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned()); 124 return APFixedPoint(Val, Sema); 125} 126 127FixedPointSemantics FixedPointSemantics::getCommonSemantics( 128 const FixedPointSemantics &Other) const { 129 unsigned CommonScale = std::max(getScale(), Other.getScale()); 130 unsigned CommonWidth = 131 std::max(getIntegralBits(), Other.getIntegralBits()) + CommonScale; 132 133 bool ResultIsSigned = isSigned() || Other.isSigned(); 134 bool ResultIsSaturated = isSaturated() || Other.isSaturated(); 135 bool ResultHasUnsignedPadding = false; 136 if (!ResultIsSigned) { 137 // Both are unsigned. 138 ResultHasUnsignedPadding = hasUnsignedPadding() && 139 Other.hasUnsignedPadding() && !ResultIsSaturated; 140 } 141 142 // If the result is signed, add an extra bit for the sign. Otherwise, if it is 143 // unsigned and has unsigned padding, we only need to add the extra padding 144 // bit back if we are not saturating. 145 if (ResultIsSigned || ResultHasUnsignedPadding) 146 CommonWidth++; 147 148 return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned, 149 ResultIsSaturated, ResultHasUnsignedPadding); 150} 151 152APFixedPoint APFixedPoint::add(const APFixedPoint &Other, 153 bool *Overflow) const { 154 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics()); 155 APFixedPoint ConvertedThis = convert(CommonFXSema); 156 APFixedPoint ConvertedOther = Other.convert(CommonFXSema); 157 llvm::APSInt ThisVal = ConvertedThis.getValue(); 158 llvm::APSInt OtherVal = ConvertedOther.getValue(); 159 bool Overflowed = false; 160 161 llvm::APSInt Result; 162 if (CommonFXSema.isSaturated()) { 163 Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal) 164 : ThisVal.uadd_sat(OtherVal); 165 } else { 166 Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed) 167 : ThisVal.uadd_ov(OtherVal, Overflowed); 168 } 169 170 if (Overflow) 171 *Overflow = Overflowed; 172 173 return APFixedPoint(Result, CommonFXSema); 174} 175 176APFixedPoint APFixedPoint::sub(const APFixedPoint &Other, 177 bool *Overflow) const { 178 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics()); 179 APFixedPoint ConvertedThis = convert(CommonFXSema); 180 APFixedPoint ConvertedOther = Other.convert(CommonFXSema); 181 llvm::APSInt ThisVal = ConvertedThis.getValue(); 182 llvm::APSInt OtherVal = ConvertedOther.getValue(); 183 bool Overflowed = false; 184 185 llvm::APSInt Result; 186 if (CommonFXSema.isSaturated()) { 187 Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal) 188 : ThisVal.usub_sat(OtherVal); 189 } else { 190 Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed) 191 : ThisVal.usub_ov(OtherVal, Overflowed); 192 } 193 194 if (Overflow) 195 *Overflow = Overflowed; 196 197 return APFixedPoint(Result, CommonFXSema); 198} 199 200APFixedPoint APFixedPoint::mul(const APFixedPoint &Other, 201 bool *Overflow) const { 202 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics()); 203 APFixedPoint ConvertedThis = convert(CommonFXSema); 204 APFixedPoint ConvertedOther = Other.convert(CommonFXSema); 205 llvm::APSInt ThisVal = ConvertedThis.getValue(); 206 llvm::APSInt OtherVal = ConvertedOther.getValue(); 207 bool Overflowed = false; 208 209 // Widen the LHS and RHS so we can perform a full multiplication. 210 unsigned Wide = CommonFXSema.getWidth() * 2; 211 if (CommonFXSema.isSigned()) { 212 ThisVal = ThisVal.sextOrSelf(Wide); 213 OtherVal = OtherVal.sextOrSelf(Wide); 214 } else { 215 ThisVal = ThisVal.zextOrSelf(Wide); 216 OtherVal = OtherVal.zextOrSelf(Wide); 217 } 218 219 // Perform the full multiplication and downscale to get the same scale. 220 // 221 // Note that the right shifts here perform an implicit downwards rounding. 222 // This rounding could discard bits that would technically place the result 223 // outside the representable range. We interpret the spec as allowing us to 224 // perform the rounding step first, avoiding the overflow case that would 225 // arise. 226 llvm::APSInt Result; 227 if (CommonFXSema.isSigned()) 228 Result = ThisVal.smul_ov(OtherVal, Overflowed) 229 .ashr(CommonFXSema.getScale()); 230 else 231 Result = ThisVal.umul_ov(OtherVal, Overflowed) 232 .lshr(CommonFXSema.getScale()); 233 assert(!Overflowed && "Full multiplication cannot overflow!"); 234 Result.setIsSigned(CommonFXSema.isSigned()); 235 236 // If our result lies outside of the representative range of the common 237 // semantic, we either have overflow or saturation. 238 llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue() 239 .extOrTrunc(Wide); 240 llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue() 241 .extOrTrunc(Wide); 242 if (CommonFXSema.isSaturated()) { 243 if (Result < Min) 244 Result = Min; 245 else if (Result > Max) 246 Result = Max; 247 } else 248 Overflowed = Result < Min || Result > Max; 249 250 if (Overflow) 251 *Overflow = Overflowed; 252 253 return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()), 254 CommonFXSema); 255} 256 257APFixedPoint APFixedPoint::div(const APFixedPoint &Other, 258 bool *Overflow) const { 259 auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics()); 260 APFixedPoint ConvertedThis = convert(CommonFXSema); 261 APFixedPoint ConvertedOther = Other.convert(CommonFXSema); 262 llvm::APSInt ThisVal = ConvertedThis.getValue(); 263 llvm::APSInt OtherVal = ConvertedOther.getValue(); 264 bool Overflowed = false; 265 266 // Widen the LHS and RHS so we can perform a full division. 267 unsigned Wide = CommonFXSema.getWidth() * 2; 268 if (CommonFXSema.isSigned()) { 269 ThisVal = ThisVal.sextOrSelf(Wide); 270 OtherVal = OtherVal.sextOrSelf(Wide); 271 } else { 272 ThisVal = ThisVal.zextOrSelf(Wide); 273 OtherVal = OtherVal.zextOrSelf(Wide); 274 } 275 276 // Upscale to compensate for the loss of precision from division, and 277 // perform the full division. 278 ThisVal = ThisVal.shl(CommonFXSema.getScale()); 279 llvm::APSInt Result; 280 if (CommonFXSema.isSigned()) { 281 llvm::APInt Rem; 282 llvm::APInt::sdivrem(ThisVal, OtherVal, Result, Rem); 283 // If the quotient is negative and the remainder is nonzero, round 284 // towards negative infinity by subtracting epsilon from the result. 285 if (ThisVal.isNegative() != OtherVal.isNegative() && !Rem.isNullValue()) 286 Result = Result - 1; 287 } else 288 Result = ThisVal.udiv(OtherVal); 289 Result.setIsSigned(CommonFXSema.isSigned()); 290 291 // If our result lies outside of the representative range of the common 292 // semantic, we either have overflow or saturation. 293 llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue() 294 .extOrTrunc(Wide); 295 llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue() 296 .extOrTrunc(Wide); 297 if (CommonFXSema.isSaturated()) { 298 if (Result < Min) 299 Result = Min; 300 else if (Result > Max) 301 Result = Max; 302 } else 303 Overflowed = Result < Min || Result > Max; 304 305 if (Overflow) 306 *Overflow = Overflowed; 307 308 return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()), 309 CommonFXSema); 310} 311 312void APFixedPoint::toString(llvm::SmallVectorImpl<char> &Str) const { 313 llvm::APSInt Val = getValue(); 314 unsigned Scale = getScale(); 315 316 if (Val.isSigned() && Val.isNegative() && Val != -Val) { 317 Val = -Val; 318 Str.push_back('-'); 319 } 320 321 llvm::APSInt IntPart = Val >> Scale; 322 323 // Add 4 digits to hold the value after multiplying 10 (the radix) 324 unsigned Width = Val.getBitWidth() + 4; 325 llvm::APInt FractPart = Val.zextOrTrunc(Scale).zext(Width); 326 llvm::APInt FractPartMask = llvm::APInt::getAllOnesValue(Scale).zext(Width); 327 llvm::APInt RadixInt = llvm::APInt(Width, 10); 328 329 IntPart.toString(Str, /*Radix=*/10); 330 Str.push_back('.'); 331 do { 332 (FractPart * RadixInt) 333 .lshr(Scale) 334 .toString(Str, /*Radix=*/10, Val.isSigned()); 335 FractPart = (FractPart * RadixInt) & FractPartMask; 336 } while (FractPart != 0); 337} 338 339APFixedPoint APFixedPoint::negate(bool *Overflow) const { 340 if (!isSaturated()) { 341 if (Overflow) 342 *Overflow = 343 (!isSigned() && Val != 0) || (isSigned() && Val.isMinSignedValue()); 344 return APFixedPoint(-Val, Sema); 345 } 346 347 // We never overflow for saturation 348 if (Overflow) 349 *Overflow = false; 350 351 if (isSigned()) 352 return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema); 353 else 354 return APFixedPoint(Sema); 355} 356 357llvm::APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign, 358 bool *Overflow) const { 359 llvm::APSInt Result = getIntPart(); 360 unsigned SrcWidth = getWidth(); 361 362 llvm::APSInt DstMin = llvm::APSInt::getMinValue(DstWidth, !DstSign); 363 llvm::APSInt DstMax = llvm::APSInt::getMaxValue(DstWidth, !DstSign); 364 365 if (SrcWidth < DstWidth) { 366 Result = Result.extend(DstWidth); 367 } else if (SrcWidth > DstWidth) { 368 DstMin = DstMin.extend(SrcWidth); 369 DstMax = DstMax.extend(SrcWidth); 370 } 371 372 if (Overflow) { 373 if (Result.isSigned() && !DstSign) { 374 *Overflow = Result.isNegative() || Result.ugt(DstMax); 375 } else if (Result.isUnsigned() && DstSign) { 376 *Overflow = Result.ugt(DstMax); 377 } else { 378 *Overflow = Result < DstMin || Result > DstMax; 379 } 380 } 381 382 Result.setIsSigned(DstSign); 383 return Result.extOrTrunc(DstWidth); 384} 385 386APFixedPoint APFixedPoint::getFromIntValue(const llvm::APSInt &Value, 387 const FixedPointSemantics &DstFXSema, 388 bool *Overflow) { 389 FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics( 390 Value.getBitWidth(), Value.isSigned()); 391 return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow); 392} 393 394} // namespace clang 395