Coverage Report

Created: 2020-08-18 13:09

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Basic/FixedPoint.cpp
Line
Count
Source (jump to first uncovered line)
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
16
namespace clang {
17
18
APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema,
19
2.41k
                                   bool *Overflow) const {
20
2.41k
  llvm::APSInt NewVal = Val;
21
2.41k
  unsigned DstWidth = DstSema.getWidth();
22
2.41k
  unsigned DstScale = DstSema.getScale();
23
2.41k
  bool Upscaling = DstScale > getScale();
24
2.41k
  if (Overflow)
25
946
    *Overflow = false;
26
2.41k
27
2.41k
  if (Upscaling) {
28
522
    NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale());
29
522
    NewVal <<= (DstScale - getScale());
30
1.89k
  } else {
31
1.89k
    NewVal >>= (getScale() - DstScale);
32
1.89k
  }
33
2.41k
34
2.41k
  auto Mask = llvm::APInt::getBitsSetFrom(
35
2.41k
      NewVal.getBitWidth(),
36
2.41k
      std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
37
2.41k
  llvm::APInt Masked(NewVal & Mask);
38
2.41k
39
  // Change in the bits above the sign
40
2.41k
  if (!(Masked == Mask || 
Masked == 01.29k
)) {
41
    // Found overflow in the bits above the sign
42
118
    if (DstSema.isSaturated())
43
92
      NewVal = NewVal.isNegative() ? 
Mask18
:
~Mask74
;
44
26
    else if (Overflow)
45
20
      *Overflow = true;
46
118
  }
47
2.41k
48
  // If the dst semantics are unsigned, but our value is signed and negative, we
49
  // clamp to zero.
50
2.41k
  if (!DstSema.isSigned() && 
NewVal.isSigned()576
&&
NewVal.isNegative()244
) {
51
    // Found negative overflow for unsigned result
52
93
    if (DstSema.isSaturated())
53
81
      NewVal = 0;
54
12
    else if (Overflow)
55
9
      *Overflow = true;
56
93
  }
57
2.41k
58
2.41k
  NewVal = NewVal.extOrTrunc(DstWidth);
59
2.41k
  NewVal.setIsSigned(DstSema.isSigned());
60
2.41k
  return APFixedPoint(NewVal, DstSema);
61
2.41k
}
62
63
713
int APFixedPoint::compare(const APFixedPoint &Other) const {
64
713
  llvm::APSInt ThisVal = getValue();
65
713
  llvm::APSInt OtherVal = Other.getValue();
66
713
  bool ThisSigned = Val.isSigned();
67
713
  bool OtherSigned = OtherVal.isSigned();
68
713
  unsigned OtherScale = Other.getScale();
69
713
  unsigned OtherWidth = OtherVal.getBitWidth();
70
713
71
713
  unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth);
72
713
73
  // Prevent overflow in the event the widths are the same but the scales differ
74
605
  CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale
75
108
                                          : OtherScale - getScale();
76
713
77
713
  ThisVal = ThisVal.extOrTrunc(CommonWidth);
78
713
  OtherVal = OtherVal.extOrTrunc(CommonWidth);
79
713
80
713
  unsigned CommonScale = std::max(getScale(), OtherScale);
81
713
  ThisVal = ThisVal.shl(CommonScale - getScale());
82
713
  OtherVal = OtherVal.shl(CommonScale - OtherScale);
83
713
84
713
  if (ThisSigned && 
OtherSigned479
) {
85
297
    if (ThisVal.sgt(OtherVal))
86
59
      return 1;
87
238
    else if (ThisVal.slt(OtherVal))
88
47
      return -1;
89
416
  } else if (!ThisSigned && 
!OtherSigned234
) {
90
215
    if (ThisVal.ugt(OtherVal))
91
5
      return 1;
92
210
    else if (ThisVal.ult(OtherVal))
93
5
      return -1;
94
201
  } else if (ThisSigned && 
!OtherSigned182
) {
95
182
    if (ThisVal.isSignBitSet())
96
3
      return -1;
97
179
    else if (ThisVal.ugt(OtherVal))
98
63
      return 1;
99
116
    else if (ThisVal.ult(OtherVal))
100
24
      return -1;
101
19
  } else {
102
    // !ThisSigned && OtherSigned
103
19
    if (OtherVal.isSignBitSet())
104
3
      return 1;
105
16
    else if (ThisVal.ugt(OtherVal))
106
1
      return 1;
107
15
    else if (ThisVal.ult(OtherVal))
108
3
      return -1;
109
500
  }
110
500
111
500
  return 0;
112
500
}
113
114
1.38k
APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) {
115
1.38k
  bool IsUnsigned = !Sema.isSigned();
116
1.38k
  auto Val = llvm::APSInt::getMaxValue(Sema.getWidth(), IsUnsigned);
117
1.38k
  if (IsUnsigned && 
Sema.hasUnsignedPadding()359
)
118
132
    Val = Val.lshr(1);
119
1.38k
  return APFixedPoint(Val, Sema);
120
1.38k
}
121
122
581
APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
123
581
  auto Val = llvm::APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
124
581
  return APFixedPoint(Val, Sema);
125
581
}
126
127
FixedPointSemantics FixedPointSemantics::getCommonSemantics(
128
1.01k
    const FixedPointSemantics &Other) const {
129
1.01k
  unsigned CommonScale = std::max(getScale(), Other.getScale());
130
1.01k
  unsigned CommonWidth =
131
1.01k
      std::max(getIntegralBits(), Other.getIntegralBits()) + CommonScale;
132
1.01k
133
1.01k
  bool ResultIsSigned = isSigned() || 
Other.isSigned()276
;
134
1.01k
  bool ResultIsSaturated = isSaturated() || 
Other.isSaturated()763
;
135
1.01k
  bool ResultHasUnsignedPadding = false;
136
1.01k
  if (!ResultIsSigned) {
137
    // Both are unsigned.
138
176
    ResultHasUnsignedPadding = hasUnsignedPadding() &&
139
83
                               Other.hasUnsignedPadding() && 
!ResultIsSaturated73
;
140
176
  }
141
1.01k
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
1.01k
  if (ResultIsSigned || 
ResultHasUnsignedPadding176
)
146
880
    CommonWidth++;
147
1.01k
148
1.01k
  return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned,
149
1.01k
                             ResultIsSaturated, ResultHasUnsignedPadding);
150
1.01k
}
151
152
APFixedPoint APFixedPoint::add(const APFixedPoint &Other,
153
119
                               bool *Overflow) const {
154
119
  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
155
119
  APFixedPoint ConvertedThis = convert(CommonFXSema);
156
119
  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
157
119
  llvm::APSInt ThisVal = ConvertedThis.getValue();
158
119
  llvm::APSInt OtherVal = ConvertedOther.getValue();
159
119
  bool Overflowed = false;
160
119
161
119
  llvm::APSInt Result;
162
119
  if (CommonFXSema.isSaturated()) {
163
27
    Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal)
164
6
                                     : ThisVal.uadd_sat(OtherVal);
165
86
  } else {
166
80
    Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed)
167
6
                                : ThisVal.uadd_ov(OtherVal, Overflowed);
168
86
  }
169
119
170
119
  if (Overflow)
171
119
    *Overflow = Overflowed;
172
119
173
119
  return APFixedPoint(Result, CommonFXSema);
174
119
}
175
176
APFixedPoint APFixedPoint::sub(const APFixedPoint &Other,
177
160
                               bool *Overflow) const {
178
160
  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
179
160
  APFixedPoint ConvertedThis = convert(CommonFXSema);
180
160
  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
181
160
  llvm::APSInt ThisVal = ConvertedThis.getValue();
182
160
  llvm::APSInt OtherVal = ConvertedOther.getValue();
183
160
  bool Overflowed = false;
184
160
185
160
  llvm::APSInt Result;
186
160
  if (CommonFXSema.isSaturated()) {
187
39
    Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal)
188
6
                                     : ThisVal.usub_sat(OtherVal);
189
115
  } else {
190
106
    Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed)
191
9
                                : ThisVal.usub_ov(OtherVal, Overflowed);
192
115
  }
193
160
194
160
  if (Overflow)
195
160
    *Overflow = Overflowed;
196
160
197
160
  return APFixedPoint(Result, CommonFXSema);
198
160
}
199
200
APFixedPoint APFixedPoint::mul(const APFixedPoint &Other,
201
117
                               bool *Overflow) const {
202
117
  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
203
117
  APFixedPoint ConvertedThis = convert(CommonFXSema);
204
117
  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
205
117
  llvm::APSInt ThisVal = ConvertedThis.getValue();
206
117
  llvm::APSInt OtherVal = ConvertedOther.getValue();
207
117
  bool Overflowed = false;
208
117
209
  // Widen the LHS and RHS so we can perform a full multiplication.
210
117
  unsigned Wide = CommonFXSema.getWidth() * 2;
211
117
  if (CommonFXSema.isSigned()) {
212
102
    ThisVal = ThisVal.sextOrSelf(Wide);
213
102
    OtherVal = OtherVal.sextOrSelf(Wide);
214
15
  } else {
215
15
    ThisVal = ThisVal.zextOrSelf(Wide);
216
15
    OtherVal = OtherVal.zextOrSelf(Wide);
217
15
  }
218
117
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
117
  llvm::APSInt Result;
227
117
  if (CommonFXSema.isSigned())
228
102
    Result = ThisVal.smul_ov(OtherVal, Overflowed)
229
102
                    .ashr(CommonFXSema.getScale());
230
15
  else
231
15
    Result = ThisVal.umul_ov(OtherVal, Overflowed)
232
15
                    .lshr(CommonFXSema.getScale());
233
117
  assert(!Overflowed && "Full multiplication cannot overflow!");
234
117
  Result.setIsSigned(CommonFXSema.isSigned());
235
117
236
  // If our result lies outside of the representative range of the common
237
  // semantic, we either have overflow or saturation.
238
117
  llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
239
117
                                                       .extOrTrunc(Wide);
240
117
  llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
241
117
                                                       .extOrTrunc(Wide);
242
117
  if (CommonFXSema.isSaturated()) {
243
33
    if (Result < Min)
244
0
      Result = Min;
245
33
    else if (Result > Max)
246
15
      Result = Max;
247
33
  } else
248
84
    Overflowed = Result < Min || Result > Max;
249
117
250
117
  if (Overflow)
251
117
    *Overflow = Overflowed;
252
117
253
117
  return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
254
117
                      CommonFXSema);
255
117
}
256
257
APFixedPoint APFixedPoint::div(const APFixedPoint &Other,
258
181
                               bool *Overflow) const {
259
181
  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
260
181
  APFixedPoint ConvertedThis = convert(CommonFXSema);
261
181
  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
262
181
  llvm::APSInt ThisVal = ConvertedThis.getValue();
263
181
  llvm::APSInt OtherVal = ConvertedOther.getValue();
264
181
  bool Overflowed = false;
265
181
266
  // Widen the LHS and RHS so we can perform a full division.
267
181
  unsigned Wide = CommonFXSema.getWidth() * 2;
268
181
  if (CommonFXSema.isSigned()) {
269
169
    ThisVal = ThisVal.sextOrSelf(Wide);
270
169
    OtherVal = OtherVal.sextOrSelf(Wide);
271
12
  } else {
272
12
    ThisVal = ThisVal.zextOrSelf(Wide);
273
12
    OtherVal = OtherVal.zextOrSelf(Wide);
274
12
  }
275
181
276
  // Upscale to compensate for the loss of precision from division, and
277
  // perform the full division.
278
181
  ThisVal = ThisVal.shl(CommonFXSema.getScale());
279
181
  llvm::APSInt Result;
280
181
  if (CommonFXSema.isSigned()) {
281
169
    llvm::APInt Rem;
282
169
    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
169
    if (ThisVal.isNegative() != OtherVal.isNegative() && 
!Rem.isNullValue()74
)
286
18
      Result = Result - 1;
287
169
  } else
288
12
    Result = ThisVal.udiv(OtherVal);
289
181
  Result.setIsSigned(CommonFXSema.isSigned());
290
181
291
  // If our result lies outside of the representative range of the common
292
  // semantic, we either have overflow or saturation.
293
181
  llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
294
181
                                                       .extOrTrunc(Wide);
295
181
  llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
296
181
                                                       .extOrTrunc(Wide);
297
181
  if (CommonFXSema.isSaturated()) {
298
65
    if (Result < Min)
299
14
      Result = Min;
300
51
    else if (Result > Max)
301
27
      Result = Max;
302
65
  } else
303
116
    Overflowed = Result < Min || Result > Max;
304
181
305
181
  if (Overflow)
306
181
    *Overflow = Overflowed;
307
181
308
181
  return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
309
181
                      CommonFXSema);
310
181
}
311
312
105
APFixedPoint APFixedPoint::shl(unsigned Amt, bool *Overflow) const {
313
105
  llvm::APSInt ThisVal = Val;
314
105
  bool Overflowed = false;
315
105
316
  // Widen the LHS.
317
105
  unsigned Wide = Sema.getWidth() * 2;
318
105
  if (Sema.isSigned())
319
77
    ThisVal = ThisVal.sextOrSelf(Wide);
320
28
  else
321
28
    ThisVal = ThisVal.zextOrSelf(Wide);
322
105
323
  // Clamp the shift amount at the original width, and perform the shift.
324
105
  Amt = std::min(Amt, ThisVal.getBitWidth());
325
105
  llvm::APSInt Result = ThisVal << Amt;
326
105
  Result.setIsSigned(Sema.isSigned());
327
105
328
  // If our result lies outside of the representative range of the
329
  // semantic, we either have overflow or saturation.
330
105
  llvm::APSInt Max = APFixedPoint::getMax(Sema).getValue().extOrTrunc(Wide);
331
105
  llvm::APSInt Min = APFixedPoint::getMin(Sema).getValue().extOrTrunc(Wide);
332
105
  if (Sema.isSaturated()) {
333
47
    if (Result < Min)
334
6
      Result = Min;
335
41
    else if (Result > Max)
336
29
      Result = Max;
337
47
  } else
338
58
    Overflowed = Result < Min || 
Result > Max56
;
339
105
340
105
  if (Overflow)
341
105
    *Overflow = Overflowed;
342
105
343
105
  return APFixedPoint(Result.sextOrTrunc(Sema.getWidth()), Sema);
344
105
}
345
346
181
void APFixedPoint::toString(llvm::SmallVectorImpl<char> &Str) const {
347
181
  llvm::APSInt Val = getValue();
348
181
  unsigned Scale = getScale();
349
181
350
181
  if (Val.isSigned() && 
Val.isNegative()38
&&
Val != -Val19
) {
351
8
    Val = -Val;
352
8
    Str.push_back('-');
353
8
  }
354
181
355
181
  llvm::APSInt IntPart = Val >> Scale;
356
181
357
  // Add 4 digits to hold the value after multiplying 10 (the radix)
358
181
  unsigned Width = Val.getBitWidth() + 4;
359
181
  llvm::APInt FractPart = Val.zextOrTrunc(Scale).zext(Width);
360
181
  llvm::APInt FractPartMask = llvm::APInt::getAllOnesValue(Scale).zext(Width);
361
181
  llvm::APInt RadixInt = llvm::APInt(Width, 10);
362
181
363
181
  IntPart.toString(Str, /*Radix=*/10);
364
181
  Str.push_back('.');
365
1.29k
  do {
366
1.29k
    (FractPart * RadixInt)
367
1.29k
        .lshr(Scale)
368
1.29k
        .toString(Str, /*Radix=*/10, Val.isSigned());
369
1.29k
    FractPart = (FractPart * RadixInt) & FractPartMask;
370
1.29k
  } while (FractPart != 0);
371
181
}
372
373
274
APFixedPoint APFixedPoint::negate(bool *Overflow) const {
374
274
  if (!isSaturated()) {
375
274
    if (Overflow)
376
274
      *Overflow =
377
274
          (!isSigned() && 
Val != 06
) ||
(268
isSigned()268
&&
Val.isMinSignedValue()268
);
378
274
    return APFixedPoint(-Val, Sema);
379
274
  }
380
0
381
  // We never overflow for saturation
382
0
  if (Overflow)
383
0
    *Overflow = false;
384
0
385
0
  if (isSigned())
386
0
    return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
387
0
  else
388
0
    return APFixedPoint(Sema);
389
0
}
390
391
llvm::APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
392
74
                                        bool *Overflow) const {
393
74
  llvm::APSInt Result = getIntPart();
394
74
  unsigned SrcWidth = getWidth();
395
74
396
74
  llvm::APSInt DstMin = llvm::APSInt::getMinValue(DstWidth, !DstSign);
397
74
  llvm::APSInt DstMax = llvm::APSInt::getMaxValue(DstWidth, !DstSign);
398
74
399
74
  if (SrcWidth < DstWidth) {
400
34
    Result = Result.extend(DstWidth);
401
40
  } else if (SrcWidth > DstWidth) {
402
28
    DstMin = DstMin.extend(SrcWidth);
403
28
    DstMax = DstMax.extend(SrcWidth);
404
28
  }
405
74
406
74
  if (Overflow) {
407
74
    if (Result.isSigned() && 
!DstSign62
) {
408
22
      *Overflow = Result.isNegative() || 
Result.ugt(DstMax)14
;
409
52
    } else if (Result.isUnsigned() && 
DstSign12
) {
410
8
      *Overflow = Result.ugt(DstMax);
411
44
    } else {
412
44
      *Overflow = Result < DstMin || Result > DstMax;
413
44
    }
414
74
  }
415
74
416
74
  Result.setIsSigned(DstSign);
417
74
  return Result.extOrTrunc(DstWidth);
418
74
}
419
420
APFixedPoint APFixedPoint::getFromIntValue(const llvm::APSInt &Value,
421
                                           const FixedPointSemantics &DstFXSema,
422
67
                                           bool *Overflow) {
423
67
  FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
424
67
      Value.getBitWidth(), Value.isSigned());
425
67
  return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);
426
67
}
427
428
}  // namespace clang