Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/IR/ConstantRange.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ConstantRange.cpp - ConstantRange implementation -------------------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// Represent a range of possible values that may occur when the program is run
11
// for an integral value.  This keeps track of a lower and upper bound for the
12
// constant, which MAY wrap around the end of the numeric range.  To do this, it
13
// keeps track of a [lower, upper) bound, which specifies an interval just like
14
// STL iterators.  When used with boolean values, the following are important
15
// ranges (other integral ranges use min/max values for special range values):
16
//
17
//  [F, F) = {}     = Empty set
18
//  [T, F) = {T}
19
//  [F, T) = {F}
20
//  [T, T) = {F, T} = Full set
21
//
22
//===----------------------------------------------------------------------===//
23
24
#include "llvm/ADT/APInt.h"
25
#include "llvm/IR/ConstantRange.h"
26
#include "llvm/IR/Constants.h"
27
#include "llvm/IR/InstrTypes.h"
28
#include "llvm/IR/Instruction.h"
29
#include "llvm/IR/Metadata.h"
30
#include "llvm/IR/Operator.h"
31
#include "llvm/Support/Compiler.h"
32
#include "llvm/Support/Debug.h"
33
#include "llvm/Support/ErrorHandling.h"
34
#include "llvm/Support/raw_ostream.h"
35
#include <algorithm>
36
#include <cassert>
37
#include <cstdint>
38
39
using namespace llvm;
40
41
ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
42
    : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
43
536M
      Upper(Lower) {}
44
45
ConstantRange::ConstantRange(APInt V)
46
143M
    : Lower(std::move(V)), Upper(Lower + 1) {}
47
48
ConstantRange::ConstantRange(APInt L, APInt U)
49
269M
    : Lower(std::move(L)), Upper(std::move(U)) {
50
269M
  assert(Lower.getBitWidth() == Upper.getBitWidth() &&
51
269M
         "ConstantRange with unequal bit widths");
52
269M
  assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
53
269M
         "Lower == Upper, but they aren't min or max value!");
54
269M
}
55
56
ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
57
57.5M
                                                   const ConstantRange &CR) {
58
57.5M
  if (CR.isEmptySet())
59
0
    return CR;
60
57.5M
61
57.5M
  uint32_t W = CR.getBitWidth();
62
57.5M
  switch (Pred) {
63
0
  default:
64
0
    llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
65
24.8M
  case CmpInst::ICMP_EQ:
66
24.8M
    return CR;
67
2.06M
  case CmpInst::ICMP_NE:
68
2.06M
    if (CR.isSingleElement())
69
1.69M
      return ConstantRange(CR.getUpper(), CR.getLower());
70
365k
    return ConstantRange(W);
71
4.79M
  case CmpInst::ICMP_ULT: {
72
4.79M
    APInt UMax(CR.getUnsignedMax());
73
4.79M
    if (UMax.isMinValue())
74
562
      return ConstantRange(W, /* empty */ false);
75
4.79M
    return ConstantRange(APInt::getMinValue(W), std::move(UMax));
76
4.79M
  }
77
6.36M
  case CmpInst::ICMP_SLT: {
78
6.36M
    APInt SMax(CR.getSignedMax());
79
6.36M
    if (SMax.isMinSignedValue())
80
0
      return ConstantRange(W, /* empty */ false);
81
6.36M
    return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
82
6.36M
  }
83
499k
  case CmpInst::ICMP_ULE: {
84
499k
    APInt UMax(CR.getUnsignedMax());
85
499k
    if (UMax.isMaxValue())
86
19.0k
      return ConstantRange(W);
87
480k
    return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
88
480k
  }
89
2.07M
  case CmpInst::ICMP_SLE: {
90
2.07M
    APInt SMax(CR.getSignedMax());
91
2.07M
    if (SMax.isMaxSignedValue())
92
112k
      return ConstantRange(W);
93
1.95M
    return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
94
1.95M
  }
95
3.50M
  case CmpInst::ICMP_UGT: {
96
3.50M
    APInt UMin(CR.getUnsignedMin());
97
3.50M
    if (UMin.isMaxValue())
98
1.00k
      return ConstantRange(W, /* empty */ false);
99
3.50M
    return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
100
3.50M
  }
101
10.8M
  case CmpInst::ICMP_SGT: {
102
10.8M
    APInt SMin(CR.getSignedMin());
103
10.8M
    if (SMin.isMaxSignedValue())
104
410
      return ConstantRange(W, /* empty */ false);
105
10.8M
    return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
106
10.8M
  }
107
828k
  case CmpInst::ICMP_UGE: {
108
828k
    APInt UMin(CR.getUnsignedMin());
109
828k
    if (UMin.isMinValue())
110
100k
      return ConstantRange(W);
111
728k
    return ConstantRange(std::move(UMin), APInt::getNullValue(W));
112
728k
  }
113
1.75M
  case CmpInst::ICMP_SGE: {
114
1.75M
    APInt SMin(CR.getSignedMin());
115
1.75M
    if (SMin.isMinSignedValue())
116
207k
      return ConstantRange(W);
117
1.54M
    return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
118
1.54M
  }
119
57.5M
  }
120
57.5M
}
121
122
ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
123
8.68M
                                                      const ConstantRange &CR) {
124
8.68M
  // Follows from De-Morgan's laws:
125
8.68M
  //
126
8.68M
  // ~(~A union ~B) == A intersect B.
127
8.68M
  //
128
8.68M
  return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
129
8.68M
      .inverse();
130
8.68M
}
131
132
ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
133
29.9M
                                                 const APInt &C) {
134
29.9M
  // Computes the exact range that is equal to both the constant ranges returned
135
29.9M
  // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
136
29.9M
  // when RHS is a singleton such as an APInt and so the assert is valid.
137
29.9M
  // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
138
29.9M
  // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
139
29.9M
  //
140
29.9M
  assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
141
29.9M
  return makeAllowedICmpRegion(Pred, C);
142
29.9M
}
143
144
bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
145
7.09M
                                      APInt &RHS) const {
146
7.09M
  bool Success = false;
147
7.09M
148
7.09M
  if (
isFullSet() || 7.09M
isEmptySet()7.09M
) {
149
2
    Pred = isEmptySet() ? 
CmpInst::ICMP_ULT1
:
CmpInst::ICMP_UGE1
;
150
2
    RHS = APInt(getBitWidth(), 0);
151
2
    Success = true;
152
7.09M
  } else 
if (auto *7.09M
OnlyElt7.09M
= getSingleElement()) {
153
41.7k
    Pred = CmpInst::ICMP_EQ;
154
41.7k
    RHS = *OnlyElt;
155
41.7k
    Success = true;
156
7.09M
  } else 
if (auto *7.05M
OnlyMissingElt7.05M
= getSingleMissingElement()) {
157
1.30M
    Pred = CmpInst::ICMP_NE;
158
1.30M
    RHS = *OnlyMissingElt;
159
1.30M
    Success = true;
160
7.05M
  } else 
if (5.74M
getLower().isMinSignedValue() || 5.74M
getLower().isMinValue()4.20M
) {
161
2.72M
    Pred =
162
2.72M
        getLower().isMinSignedValue() ? 
CmpInst::ICMP_SLT1.53M
:
CmpInst::ICMP_ULT1.18M
;
163
2.72M
    RHS = getUpper();
164
2.72M
    Success = true;
165
5.74M
  } else 
if (3.01M
getUpper().isMinSignedValue() || 3.01M
getUpper().isMinValue()481k
) {
166
3.01M
    Pred =
167
3.01M
        getUpper().isMinSignedValue() ? 
CmpInst::ICMP_SGE2.53M
:
CmpInst::ICMP_UGE481k
;
168
7.09M
    RHS = getLower();
169
7.09M
    Success = true;
170
7.09M
  }
171
7.09M
172
7.09M
  assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
173
7.09M
         "Bad result!");
174
7.09M
175
7.09M
  return Success;
176
7.09M
}
177
178
ConstantRange
179
ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
180
                                          const ConstantRange &Other,
181
85.8M
                                          unsigned NoWrapKind) {
182
85.8M
  using OBO = OverflowingBinaryOperator;
183
85.8M
184
85.8M
  // Computes the intersection of CR0 and CR1.  It is different from
185
85.8M
  // intersectWith in that the ConstantRange returned will only contain elements
186
85.8M
  // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
187
85.8M
  // not, of both X and Y).
188
85.8M
  auto SubsetIntersect =
189
49.4M
      [](const ConstantRange &CR0, const ConstantRange &CR1) {
190
49.4M
    return CR0.inverse().unionWith(CR1.inverse()).inverse();
191
49.4M
  };
192
85.8M
193
85.8M
  assert(BinOp >= Instruction::BinaryOpsBegin &&
194
85.8M
         BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
195
85.8M
196
85.8M
  assert((NoWrapKind == OBO::NoSignedWrap ||
197
85.8M
          NoWrapKind == OBO::NoUnsignedWrap ||
198
85.8M
          NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
199
85.8M
         "NoWrapKind invalid!");
200
85.8M
201
85.8M
  unsigned BitWidth = Other.getBitWidth();
202
85.8M
  if (BinOp != Instruction::Add)
203
85.8M
    // Conservative answer: empty set
204
0
    return ConstantRange(BitWidth, false);
205
85.8M
206
85.8M
  
if (auto *85.8M
C85.8M
= Other.getSingleElement())
207
85.7M
    
if (85.7M
C->isNullValue()85.7M
)
208
85.7M
      // Full set: nothing signed / unsigned wraps when added to 0.
209
36.4M
      return ConstantRange(BitWidth);
210
49.3M
211
49.3M
  ConstantRange Result(BitWidth);
212
49.3M
213
49.3M
  if (NoWrapKind & OBO::NoUnsignedWrap)
214
25.7M
    Result =
215
25.7M
        SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
216
25.7M
                                              -Other.getUnsignedMax()));
217
49.3M
218
49.3M
  if (
NoWrapKind & OBO::NoSignedWrap49.3M
) {
219
23.6M
    const APInt &SignedMin = Other.getSignedMin();
220
23.6M
    const APInt &SignedMax = Other.getSignedMax();
221
23.6M
222
23.6M
    if (SignedMax.isStrictlyPositive())
223
14.9M
      Result = SubsetIntersect(
224
14.9M
          Result,
225
14.9M
          ConstantRange(APInt::getSignedMinValue(BitWidth),
226
14.9M
                        APInt::getSignedMinValue(BitWidth) - SignedMax));
227
23.6M
228
23.6M
    if (SignedMin.isNegative())
229
8.67M
      Result = SubsetIntersect(
230
8.67M
          Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
231
8.67M
                                APInt::getSignedMinValue(BitWidth)));
232
23.6M
  }
233
85.8M
234
85.8M
  return Result;
235
85.8M
}
236
237
891M
bool ConstantRange::isFullSet() const {
238
231M
  return Lower == Upper && Lower.isMaxValue();
239
891M
}
240
241
558M
bool ConstantRange::isEmptySet() const {
242
95.5M
  return Lower == Upper && Lower.isMinValue();
243
558M
}
244
245
271M
bool ConstantRange::isWrappedSet() const {
246
271M
  return Lower.ugt(Upper);
247
271M
}
248
249
184k
bool ConstantRange::isSignWrappedSet() const {
250
184k
  return contains(APInt::getSignedMaxValue(getBitWidth())) &&
251
88.5k
         contains(APInt::getSignedMinValue(getBitWidth()));
252
184k
}
253
254
6
APInt ConstantRange::getSetSize() const {
255
6
  if (isFullSet())
256
1
    return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
257
5
258
5
  // This is also correct for wrapped sets.
259
5
  return (Upper - Lower).zext(getBitWidth()+1);
260
5
}
261
262
bool
263
11.1M
ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
264
11.1M
  assert(getBitWidth() == Other.getBitWidth());
265
11.1M
  if (isFullSet())
266
2.25M
    return false;
267
8.87M
  
if (8.87M
Other.isFullSet()8.87M
)
268
52
    return true;
269
8.87M
  return (Upper - Lower).ult(Other.Upper - Other.Lower);
270
8.87M
}
271
272
bool
273
15.9M
ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
274
15.9M
  assert(MaxSize && "MaxSize can't be 0.");
275
15.9M
  // If this a full set, we need special handling to avoid needing an extra bit
276
15.9M
  // to represent the size.
277
15.9M
  if (isFullSet())
278
30
    return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
279
15.9M
280
15.9M
  return (Upper - Lower).ugt(MaxSize);
281
15.9M
}
282
283
63.3M
APInt ConstantRange::getUnsignedMax() const {
284
63.3M
  if (
isFullSet() || 63.3M
isWrappedSet()61.0M
)
285
14.6M
    return APInt::getMaxValue(getBitWidth());
286
48.7M
  return getUpper() - 1;
287
48.7M
}
288
289
14.1M
APInt ConstantRange::getUnsignedMin() const {
290
14.1M
  if (
isFullSet() || 14.1M
(isWrappedSet() && 11.9M
!getUpper().isNullValue()3.08M
))
291
3.29M
    return APInt::getMinValue(getBitWidth());
292
10.8M
  return getLower();
293
10.8M
}
294
295
53.6M
APInt ConstantRange::getSignedMax() const {
296
53.6M
  if (
isFullSet() || 53.6M
Lower.sgt(Upper)50.8M
)
297
3.25M
    return APInt::getSignedMaxValue(getBitWidth());
298
50.4M
  return getUpper() - 1;
299
50.4M
}
300
301
89.2M
APInt ConstantRange::getSignedMin() const {
302
89.2M
  if (
isFullSet() || 89.2M
(Lower.sgt(Upper) && 81.0M
!getUpper().isMinSignedValue()1.77M
))
303
9.01M
    return APInt::getSignedMinValue(getBitWidth());
304
80.2M
  return getLower();
305
80.2M
}
306
307
16.6M
bool ConstantRange::contains(const APInt &V) const {
308
16.6M
  if (Lower == Upper)
309
51.8k
    return isFullSet();
310
16.5M
311
16.5M
  
if (16.5M
!isWrappedSet()16.5M
)
312
12.6M
    
return Lower.ule(V) && 12.6M
V.ult(Upper)11.5M
;
313
3.85M
  
return Lower.ule(V) || 3.85M
V.ult(Upper)2.42M
;
314
16.6M
}
315
316
102M
bool ConstantRange::contains(const ConstantRange &Other) const {
317
102M
  if (
isFullSet() || 102M
Other.isEmptySet()65.8M
)
return true36.4M
;
318
65.8M
  
if (65.8M
isEmptySet() || 65.8M
Other.isFullSet()65.4M
)
return false19.3M
;
319
46.4M
320
46.4M
  
if (46.4M
!isWrappedSet()46.4M
) {
321
23.8M
    if (Other.isWrappedSet())
322
7.95M
      return false;
323
15.8M
324
15.8M
    
return Lower.ule(Other.getLower()) && 15.8M
Other.getUpper().ule(Upper)14.6M
;
325
23.8M
  }
326
22.6M
327
22.6M
  
if (22.6M
!Other.isWrappedSet()22.6M
)
328
12.5M
    return Other.getUpper().ule(Upper) ||
329
7.74M
           Lower.ule(Other.getLower());
330
10.1M
331
10.1M
  
return Other.getUpper().ule(Upper) && 10.1M
Lower.ule(Other.getLower())6.75M
;
332
102M
}
333
334
947k
ConstantRange ConstantRange::subtract(const APInt &Val) const {
335
947k
  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
336
947k
  // If the set is empty or full, don't modify the endpoints.
337
947k
  if (Lower == Upper) 
338
30.1k
    return *this;
339
917k
  return ConstantRange(Lower - Val, Upper - Val);
340
917k
}
341
342
932k
ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
343
932k
  return intersectWith(CR.inverse());
344
932k
}
345
346
30.1M
ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
347
30.1M
  assert(getBitWidth() == CR.getBitWidth() && 
348
30.1M
         "ConstantRange types don't agree!");
349
30.1M
350
30.1M
  // Handle common cases.
351
30.1M
  if (   
isEmptySet() || 30.1M
CR.isFullSet()30.1M
)
return *this8.54M
;
352
21.6M
  
if (21.6M
CR.isEmptySet() || 21.6M
isFullSet()21.6M
)
return CR8.37M
;
353
13.2M
354
13.2M
  
if (13.2M
!isWrappedSet() && 13.2M
CR.isWrappedSet()7.18M
)
355
1.28M
    return CR.intersectWith(*this);
356
11.9M
357
11.9M
  
if (11.9M
!isWrappedSet() && 11.9M
!CR.isWrappedSet()5.89M
) {
358
5.89M
    if (
Lower.ult(CR.Lower)5.89M
) {
359
368k
      if (Upper.ule(CR.Lower))
360
207
        return ConstantRange(getBitWidth(), false);
361
368k
362
368k
      
if (368k
Upper.ult(CR.Upper)368k
)
363
28.7k
        return ConstantRange(CR.Lower, Upper);
364
339k
365
339k
      return CR;
366
339k
    }
367
5.52M
    
if (5.52M
Upper.ult(CR.Upper)5.52M
)
368
28.7k
      return *this;
369
5.49M
370
5.49M
    
if (5.49M
Lower.ult(CR.Upper)5.49M
)
371
5.49M
      return ConstantRange(Lower, CR.Upper);
372
106
373
106
    return ConstantRange(getBitWidth(), false);
374
106
  }
375
6.08M
376
6.08M
  
if (6.08M
isWrappedSet() && 6.08M
!CR.isWrappedSet()6.08M
) {
377
3.65M
    if (
CR.Lower.ult(Upper)3.65M
) {
378
1.99M
      if (CR.Upper.ult(Upper))
379
691k
        return CR;
380
1.29M
381
1.29M
      
if (1.29M
CR.Upper.ule(Lower)1.29M
)
382
452k
        return ConstantRange(CR.Lower, Upper);
383
846k
384
846k
      
if (846k
isSizeStrictlySmallerThan(CR)846k
)
385
550k
        return *this;
386
296k
      return CR;
387
296k
    }
388
1.65M
    
if (1.65M
CR.Lower.ult(Lower)1.65M
) {
389
1.44M
      if (CR.Upper.ule(Lower))
390
6.20k
        return ConstantRange(getBitWidth(), false);
391
1.43M
392
1.43M
      return ConstantRange(Lower, CR.Upper);
393
1.43M
    }
394
214k
    return CR;
395
214k
  }
396
2.43M
397
2.43M
  
if (2.43M
CR.Upper.ult(Upper)2.43M
) {
398
1.35M
    if (
CR.Lower.ult(Upper)1.35M
) {
399
616k
      if (isSizeStrictlySmallerThan(CR))
400
6.60k
        return *this;
401
610k
      return CR;
402
610k
    }
403
742k
404
742k
    
if (742k
CR.Lower.ult(Lower)742k
)
405
33.5k
      return ConstantRange(Lower, CR.Upper);
406
708k
407
708k
    return CR;
408
708k
  }
409
1.07M
  
if (1.07M
CR.Upper.ule(Lower)1.07M
) {
410
813k
    if (CR.Lower.ult(Lower))
411
19.5k
      return *this;
412
793k
413
793k
    return ConstantRange(CR.Lower, Upper);
414
793k
  }
415
265k
  
if (265k
isSizeStrictlySmallerThan(CR)265k
)
416
9.96k
    return *this;
417
255k
  return CR;
418
255k
}
419
420
63.1M
ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
421
63.1M
  assert(getBitWidth() == CR.getBitWidth() && 
422
63.1M
         "ConstantRange types don't agree!");
423
63.1M
424
63.1M
  if (   
isFullSet() || 63.1M
CR.isEmptySet()59.6M
)
return *this3.79M
;
425
59.3M
  
if (59.3M
CR.isFullSet() || 59.3M
isEmptySet()59.2M
)
return CR49.4M
;
426
9.87M
427
9.87M
  
if (9.87M
!isWrappedSet() && 9.87M
CR.isWrappedSet()5.59M
)
return CR.unionWith(*this)2.23M
;
428
7.64M
429
7.64M
  
if (7.64M
!isWrappedSet() && 7.64M
!CR.isWrappedSet()3.35M
) {
430
3.35M
    if (
CR.Upper.ult(Lower) || 3.35M
Upper.ult(CR.Lower)3.34M
) {
431
75.0k
      // If the two ranges are disjoint, find the smaller gap and bridge it.
432
75.0k
      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
433
75.0k
      if (d1.ult(d2))
434
24.1k
        return ConstantRange(Lower, CR.Upper);
435
50.8k
      return ConstantRange(CR.Lower, Upper);
436
50.8k
    }
437
3.28M
438
3.28M
    
APInt L = CR.Lower.ult(Lower) ? 3.28M
CR.Lower43.7k
:
Lower3.23M
;
439
3.28M
    APInt U = (CR.Upper - 1).ugt(Upper - 1) ? 
CR.Upper162k
:
Upper3.11M
;
440
3.28M
441
3.28M
    if (
L.isNullValue() && 3.28M
U.isNullValue()1.65M
)
442
0
      return ConstantRange(getBitWidth());
443
3.28M
444
3.28M
    return ConstantRange(std::move(L), std::move(U));
445
3.28M
  }
446
4.28M
447
4.28M
  
if (4.28M
!CR.isWrappedSet()4.28M
) {
448
2.36M
    // ------U   L-----  and  ------U   L----- : this
449
2.36M
    //   L--U                            L--U  : CR
450
2.36M
    if (
CR.Upper.ule(Upper) || 2.36M
CR.Lower.uge(Lower)2.21M
)
451
202k
      return *this;
452
2.16M
453
2.16M
    // ------U   L----- : this
454
2.16M
    //    L---------U   : CR
455
2.16M
    
if (2.16M
CR.Lower.ule(Upper) && 2.16M
Lower.ule(CR.Upper)958k
)
456
915k
      return ConstantRange(getBitWidth());
457
1.25M
458
1.25M
    // ----U       L---- : this
459
1.25M
    //       L---U       : CR
460
1.25M
    //    <d1>  <d2>
461
1.25M
    
if (1.25M
Upper.ule(CR.Lower) && 1.25M
CR.Upper.ule(Lower)1.24M
) {
462
1.24M
      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
463
1.24M
      if (d1.ult(d2))
464
40.4k
        return ConstantRange(Lower, CR.Upper);
465
1.20M
      return ConstantRange(CR.Lower, Upper);
466
1.20M
    }
467
5.51k
468
5.51k
    // ----U     L----- : this
469
5.51k
    //        L----U    : CR
470
5.51k
    
if (5.51k
Upper.ult(CR.Lower) && 5.51k
Lower.ult(CR.Upper)104
)
471
104
      return ConstantRange(CR.Lower, Upper);
472
5.41k
473
5.41k
    // ------U    L---- : this
474
5.41k
    //    L-----U       : CR
475
0
    assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
476
5.41k
           "ConstantRange::unionWith missed a case with one range wrapped");
477
5.41k
    return ConstantRange(Lower, CR.Upper);
478
5.41k
  }
479
1.91M
480
1.91M
  // ------U    L----  and  ------U    L---- : this
481
1.91M
  // -U  L-----------  and  ------------U  L : CR
482
1.91M
  
if (1.91M
CR.Lower.ule(Upper) || 1.91M
Lower.ule(CR.Upper)1.89M
)
483
19.8k
    return ConstantRange(getBitWidth());
484
1.89M
485
1.89M
  
APInt L = CR.Lower.ult(Lower) ? 1.89M
CR.Lower1.51k
:
Lower1.89M
;
486
1.89M
  APInt U = CR.Upper.ugt(Upper) ? 
CR.Upper47.9k
:
Upper1.84M
;
487
63.1M
488
63.1M
  return ConstantRange(std::move(L), std::move(U));
489
63.1M
}
490
491
ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
492
133k
                                    uint32_t ResultBitWidth) const {
493
133k
  switch (CastOp) {
494
0
  default:
495
0
    llvm_unreachable("unsupported cast type");
496
61.8k
  case Instruction::Trunc:
497
61.8k
    return truncate(ResultBitWidth);
498
18.0k
  case Instruction::SExt:
499
18.0k
    return signExtend(ResultBitWidth);
500
32.3k
  case Instruction::ZExt:
501
32.3k
    return zeroExtend(ResultBitWidth);
502
3.54k
  case Instruction::BitCast:
503
3.54k
    return *this;
504
10.0k
  case Instruction::FPToUI:
505
10.0k
  case Instruction::FPToSI:
506
10.0k
    if (getBitWidth() == ResultBitWidth)
507
10.0k
      return *this;
508
10.0k
    else
509
0
      return ConstantRange(getBitWidth(), /*isFullSet=*/true);
510
5.88k
  case Instruction::UIToFP: {
511
5.88k
    // TODO: use input range if available
512
5.88k
    auto BW = getBitWidth();
513
5.88k
    APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
514
5.88k
    APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
515
5.88k
    return ConstantRange(std::move(Min), std::move(Max));
516
0
  }
517
1.95k
  case Instruction::SIToFP: {
518
1.95k
    // TODO: use input range if available
519
1.95k
    auto BW = getBitWidth();
520
1.95k
    APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
521
1.95k
    APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
522
1.95k
    return ConstantRange(std::move(SMin), std::move(SMax));
523
0
  }
524
0
  case Instruction::FPTrunc:
525
0
  case Instruction::FPExt:
526
0
  case Instruction::IntToPtr:
527
0
  case Instruction::PtrToInt:
528
0
  case Instruction::AddrSpaceCast:
529
0
    // Conservatively return full set.
530
0
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
531
0
  };
532
0
}
533
534
1.17M
ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
535
1.17M
  if (
isEmptySet()1.17M
)
return ConstantRange(DstTySize, /*isFullSet=*/false)1
;
536
1.17M
537
1.17M
  unsigned SrcTySize = getBitWidth();
538
1.17M
  assert(SrcTySize < DstTySize && "Not a value extension");
539
1.17M
  if (
isFullSet() || 1.17M
isWrappedSet()350k
) {
540
992k
    // Change into [0, 1 << src bit width)
541
992k
    APInt LowerExt(DstTySize, 0);
542
992k
    if (!Upper) // special case: [X, 0) -- not really wrapping around
543
865
      LowerExt = Lower.zext(DstTySize);
544
992k
    return ConstantRange(std::move(LowerExt),
545
992k
                         APInt::getOneBitSet(DstTySize, SrcTySize));
546
992k
  }
547
186k
548
186k
  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
549
186k
}
550
551
1.07M
ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
552
1.07M
  if (
isEmptySet()1.07M
)
return ConstantRange(DstTySize, /*isFullSet=*/false)1
;
553
1.07M
554
1.07M
  unsigned SrcTySize = getBitWidth();
555
1.07M
  assert(SrcTySize < DstTySize && "Not a value extension");
556
1.07M
557
1.07M
  // special case: [X, INT_MIN) -- not really wrapping around
558
1.07M
  if (Upper.isMinSignedValue())
559
2.41k
    return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
560
1.07M
561
1.07M
  
if (1.07M
isFullSet() || 1.07M
isSignWrappedSet()184k
) {
562
977k
    return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
563
977k
                         APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
564
977k
  }
565
95.7k
566
95.7k
  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
567
95.7k
}
568
569
5.05M
ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
570
5.05M
  assert(getBitWidth() > DstTySize && "Not a value truncation");
571
5.05M
  if (isEmptySet())
572
1
    return ConstantRange(DstTySize, /*isFullSet=*/false);
573
5.05M
  
if (5.05M
isFullSet()5.05M
)
574
166k
    return ConstantRange(DstTySize, /*isFullSet=*/true);
575
4.88M
576
4.88M
  APInt LowerDiv(Lower), UpperDiv(Upper);
577
4.88M
  ConstantRange Union(DstTySize, /*isFullSet=*/false);
578
4.88M
579
4.88M
  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
580
4.88M
  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
581
4.88M
  // then we do the union with [MaxValue, Upper)
582
4.88M
  if (
isWrappedSet()4.88M
) {
583
2.23M
    // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
584
2.23M
    // truncated range.
585
2.23M
    if (Upper.getActiveBits() > DstTySize ||
586
2.07M
        Upper.countTrailingOnes() == DstTySize)
587
176k
      return ConstantRange(DstTySize, /*isFullSet=*/true);
588
2.05M
589
2.05M
    Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
590
2.05M
    UpperDiv.setAllBits();
591
2.05M
592
2.05M
    // Union covers the MaxValue case, so return if the remaining range is just
593
2.05M
    // MaxValue(DstTy).
594
2.05M
    if (LowerDiv == UpperDiv)
595
12.4k
      return Union;
596
4.69M
  }
597
4.69M
598
4.69M
  // Chop off the most significant bits that are past the destination bitwidth.
599
4.69M
  
if (4.69M
LowerDiv.getActiveBits() > DstTySize4.69M
) {
600
2.07M
    // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
601
2.07M
    APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
602
2.07M
    LowerDiv -= Adjust;
603
2.07M
    UpperDiv -= Adjust;
604
2.07M
  }
605
4.69M
606
4.69M
  unsigned UpperDivWidth = UpperDiv.getActiveBits();
607
4.69M
  if (UpperDivWidth <= DstTySize)
608
2.33M
    return ConstantRange(LowerDiv.trunc(DstTySize),
609
2.33M
                         UpperDiv.trunc(DstTySize)).unionWith(Union);
610
2.36M
611
2.36M
  // The truncated value wraps around. Check if we can do better than fullset.
612
2.36M
  
if (2.36M
UpperDivWidth == DstTySize + 12.36M
) {
613
107k
    // Clear the MSB so that UpperDiv wraps around.
614
107k
    UpperDiv.clearBit(DstTySize);
615
107k
    if (UpperDiv.ult(LowerDiv))
616
153
      return ConstantRange(LowerDiv.trunc(DstTySize),
617
153
                           UpperDiv.trunc(DstTySize)).unionWith(Union);
618
2.36M
  }
619
2.36M
620
2.36M
  return ConstantRange(DstTySize, /*isFullSet=*/true);
621
2.36M
}
622
623
84.5k
ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
624
84.5k
  unsigned SrcTySize = getBitWidth();
625
84.5k
  if (SrcTySize > DstTySize)
626
9.23k
    return truncate(DstTySize);
627
75.2k
  
if (75.2k
SrcTySize < DstTySize75.2k
)
628
11.0k
    return zeroExtend(DstTySize);
629
64.2k
  return *this;
630
64.2k
}
631
632
20.7k
ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
633
20.7k
  unsigned SrcTySize = getBitWidth();
634
20.7k
  if (SrcTySize > DstTySize)
635
15
    return truncate(DstTySize);
636
20.7k
  
if (20.7k
SrcTySize < DstTySize20.7k
)
637
823
    return signExtend(DstTySize);
638
19.8k
  return *this;
639
19.8k
}
640
641
ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
642
636k
                                      const ConstantRange &Other) const {
643
636k
  assert(BinOp >= Instruction::BinaryOpsBegin &&
644
636k
         BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
645
636k
646
636k
  switch (BinOp) {
647
477k
  case Instruction::Add:
648
477k
    return add(Other);
649
17
  case Instruction::Sub:
650
17
    return sub(Other);
651
6.54k
  case Instruction::Mul:
652
6.54k
    return multiply(Other);
653
5.75k
  case Instruction::UDiv:
654
5.75k
    return udiv(Other);
655
37.3k
  case Instruction::Shl:
656
37.3k
    return shl(Other);
657
42.8k
  case Instruction::LShr:
658
42.8k
    return lshr(Other);
659
41.4k
  case Instruction::And:
660
41.4k
    return binaryAnd(Other);
661
10.1k
  case Instruction::Or:
662
10.1k
    return binaryOr(Other);
663
636k
  // Note: floating point operations applied to abstract ranges are just
664
636k
  // ideal integer operations with a lossy representation
665
2.49k
  case Instruction::FAdd:
666
2.49k
    return add(Other);
667
1.05k
  case Instruction::FSub:
668
1.05k
    return sub(Other);
669
11.2k
  case Instruction::FMul:
670
11.2k
    return multiply(Other);
671
0
  default:
672
0
    // Conservatively return full set.
673
0
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
674
0
  }
675
0
}
676
677
ConstantRange
678
6.70M
ConstantRange::add(const ConstantRange &Other) const {
679
6.70M
  if (
isEmptySet() || 6.70M
Other.isEmptySet()6.70M
)
680
881
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
681
6.70M
  
if (6.70M
isFullSet() || 6.70M
Other.isFullSet()5.75M
)
682
3.04M
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
683
3.66M
684
3.66M
  APInt NewLower = getLower() + Other.getLower();
685
3.66M
  APInt NewUpper = getUpper() + Other.getUpper() - 1;
686
3.66M
  if (NewLower == NewUpper)
687
401
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
688
3.66M
689
3.66M
  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
690
3.66M
  if (X.isSizeStrictlySmallerThan(*this) ||
691
3.43M
      X.isSizeStrictlySmallerThan(Other))
692
3.66M
    // We've wrapped, therefore, full set.
693
229k
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
694
3.43M
  return X;
695
3.43M
}
696
697
227
ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
698
227
  // Calculate the subset of this range such that "X + Other" is
699
227
  // guaranteed not to wrap (overflow) for all X in this subset.
700
227
  // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
701
227
  // passing a single element range.
702
227
  auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
703
227
                                      ConstantRange(Other),
704
227
                                      OverflowingBinaryOperator::NoSignedWrap);
705
227
  auto NSWConstrainedRange = intersectWith(NSWRange);
706
227
707
227
  return NSWConstrainedRange.add(ConstantRange(Other));
708
227
}
709
710
ConstantRange
711
1.09k
ConstantRange::sub(const ConstantRange &Other) const {
712
1.09k
  if (
isEmptySet() || 1.09k
Other.isEmptySet()940
)
713
190
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
714
900
  
if (900
isFullSet() || 900
Other.isFullSet()111
)
715
859
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
716
41
717
41
  APInt NewLower = getLower() - Other.getUpper() + 1;
718
41
  APInt NewUpper = getUpper() - Other.getLower();
719
41
  if (NewLower == NewUpper)
720
0
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
721
41
722
41
  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
723
41
  if (X.isSizeStrictlySmallerThan(*this) ||
724
41
      X.isSizeStrictlySmallerThan(Other))
725
41
    // We've wrapped, therefore, full set.
726
0
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
727
41
  return X;
728
41
}
729
730
ConstantRange
731
2.44M
ConstantRange::multiply(const ConstantRange &Other) const {
732
2.44M
  // TODO: If either operand is a single element and the multiply is known to
733
2.44M
  // be non-wrapping, round the result min and max value to the appropriate
734
2.44M
  // multiple of that element. If wrapping is possible, at least adjust the
735
2.44M
  // range according to the greatest power-of-two factor of the single element.
736
2.44M
737
2.44M
  if (
isEmptySet() || 2.44M
Other.isEmptySet()2.44M
)
738
521
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
739
2.44M
740
2.44M
  // Multiplication is signedness-independent. However different ranges can be
741
2.44M
  // obtained depending on how the input ranges are treated. These different
742
2.44M
  // ranges are all conservatively correct, but one might be better than the
743
2.44M
  // other. We calculate two ranges; one treating the inputs as unsigned
744
2.44M
  // and the other signed, then return the smallest of these ranges.
745
2.44M
746
2.44M
  // Unsigned range first.
747
2.44M
  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
748
2.44M
  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
749
2.44M
  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
750
2.44M
  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
751
2.44M
752
2.44M
  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
753
2.44M
                                            this_max * Other_max + 1);
754
2.44M
  ConstantRange UR = Result_zext.truncate(getBitWidth());
755
2.44M
756
2.44M
  // If the unsigned range doesn't wrap, and isn't negative then it's a range
757
2.44M
  // from one positive number to another which is as good as we can generate.
758
2.44M
  // In this case, skip the extra work of generating signed ranges which aren't
759
2.44M
  // going to be better than this range.
760
2.44M
  if (!UR.isWrappedSet() &&
761
2.44M
      
(UR.getUpper().isNonNegative() || 2.44M
UR.getUpper().isMinSignedValue()2.30M
))
762
145k
    return UR;
763
2.30M
764
2.30M
  // Now the signed range. Because we could be dealing with negative numbers
765
2.30M
  // here, the lower bound is the smallest of the cartesian product of the
766
2.30M
  // lower and upper ranges; for example:
767
2.30M
  //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
768
2.30M
  // Similarly for the upper bound, swapping min for max.
769
2.30M
770
2.30M
  this_min = getSignedMin().sext(getBitWidth() * 2);
771
2.30M
  this_max = getSignedMax().sext(getBitWidth() * 2);
772
2.30M
  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
773
2.30M
  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
774
2.30M
  
775
2.30M
  auto L = {this_min * Other_min, this_min * Other_max,
776
2.30M
            this_max * Other_min, this_max * Other_max};
777
13.8M
  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
778
2.30M
  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
779
2.30M
  ConstantRange SR = Result_sext.truncate(getBitWidth());
780
2.30M
781
2.30M
  return UR.isSizeStrictlySmallerThan(SR) ? 
UR52
:
SR2.30M
;
782
2.44M
}
783
784
ConstantRange
785
225k
ConstantRange::smax(const ConstantRange &Other) const {
786
225k
  // X smax Y is: range(smax(X_smin, Y_smin),
787
225k
  //                    smax(X_smax, Y_smax))
788
225k
  if (
isEmptySet() || 225k
Other.isEmptySet()225k
)
789
5
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
790
225k
  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
791
225k
  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
792
225k
  if (NewU == NewL)
793
20.9k
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
794
204k
  return ConstantRange(std::move(NewL), std::move(NewU));
795
204k
}
796
797
ConstantRange
798
210k
ConstantRange::umax(const ConstantRange &Other) const {
799
210k
  // X umax Y is: range(umax(X_umin, Y_umin),
800
210k
  //                    umax(X_umax, Y_umax))
801
210k
  if (
isEmptySet() || 210k
Other.isEmptySet()210k
)
802
5
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
803
210k
  APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
804
210k
  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
805
210k
  if (NewU == NewL)
806
138k
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
807
71.8k
  return ConstantRange(std::move(NewL), std::move(NewU));
808
71.8k
}
809
810
ConstantRange
811
157
ConstantRange::smin(const ConstantRange &Other) const {
812
157
  // X smin Y is: range(smin(X_smin, Y_smin),
813
157
  //                    smin(X_smax, Y_smax))
814
157
  if (
isEmptySet() || 157
Other.isEmptySet()153
)
815
5
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
816
152
  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
817
152
  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
818
152
  if (NewU == NewL)
819
97
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
820
55
  return ConstantRange(std::move(NewL), std::move(NewU));
821
55
}
822
823
ConstantRange
824
173
ConstantRange::umin(const ConstantRange &Other) const {
825
173
  // X umin Y is: range(umin(X_umin, Y_umin),
826
173
  //                    umin(X_umax, Y_umax))
827
173
  if (
isEmptySet() || 173
Other.isEmptySet()169
)
828
5
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
829
168
  APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
830
168
  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
831
168
  if (NewU == NewL)
832
47
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
833
121
  return ConstantRange(std::move(NewL), std::move(NewU));
834
121
}
835
836
ConstantRange
837
220k
ConstantRange::udiv(const ConstantRange &RHS) const {
838
220k
  if (
isEmptySet() || 220k
RHS.isEmptySet()220k
||
RHS.getUnsignedMax().isNullValue()220k
)
839
7
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
840
220k
  
if (220k
RHS.isFullSet()220k
)
841
2.05k
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
842
218k
843
218k
  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
844
218k
845
218k
  APInt RHS_umin = RHS.getUnsignedMin();
846
218k
  if (
RHS_umin.isNullValue()218k
) {
847
3.15k
    // We want the lowest value in RHS excluding zero. Usually that would be 1
848
3.15k
    // except for a range in the form of [X, 1) in which case it would be X.
849
3.15k
    if (RHS.getUpper() == 1)
850
0
      RHS_umin = RHS.getLower();
851
3.15k
    else
852
3.15k
      RHS_umin = 1;
853
3.15k
  }
854
218k
855
218k
  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
856
218k
857
218k
  // If the LHS is Full and the RHS is a wrapped interval containing 1 then
858
218k
  // this could occur.
859
218k
  if (Lower == Upper)
860
1.13k
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
861
217k
862
217k
  return ConstantRange(std::move(Lower), std::move(Upper));
863
217k
}
864
865
ConstantRange
866
41.4k
ConstantRange::binaryAnd(const ConstantRange &Other) const {
867
41.4k
  if (
isEmptySet() || 41.4k
Other.isEmptySet()41.4k
)
868
0
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
869
41.4k
870
41.4k
  // TODO: replace this with something less conservative
871
41.4k
872
41.4k
  APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
873
41.4k
  if (umin.isAllOnesValue())
874
0
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
875
41.4k
  return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
876
41.4k
}
877
878
ConstantRange
879
10.1k
ConstantRange::binaryOr(const ConstantRange &Other) const {
880
10.1k
  if (
isEmptySet() || 10.1k
Other.isEmptySet()10.1k
)
881
0
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
882
10.1k
883
10.1k
  // TODO: replace this with something less conservative
884
10.1k
885
10.1k
  APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
886
10.1k
  if (umax.isNullValue())
887
9
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
888
10.1k
  return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
889
10.1k
}
890
891
ConstantRange
892
37.3k
ConstantRange::shl(const ConstantRange &Other) const {
893
37.3k
  if (
isEmptySet() || 37.3k
Other.isEmptySet()37.3k
)
894
5
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
895
37.3k
896
37.3k
  APInt max = getUnsignedMax();
897
37.3k
  APInt Other_umax = Other.getUnsignedMax();
898
37.3k
899
37.3k
  // there's overflow!
900
37.3k
  if (Other_umax.uge(max.countLeadingZeros()))
901
23.4k
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
902
13.8k
903
13.8k
  // FIXME: implement the other tricky cases
904
13.8k
905
13.8k
  APInt min = getUnsignedMin();
906
13.8k
  min <<= Other.getUnsignedMin();
907
13.8k
  max <<= Other_umax;
908
13.8k
909
13.8k
  return ConstantRange(std::move(min), std::move(max) + 1);
910
13.8k
}
911
912
ConstantRange
913
42.8k
ConstantRange::lshr(const ConstantRange &Other) const {
914
42.8k
  if (
isEmptySet() || 42.8k
Other.isEmptySet()42.8k
)
915
5
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
916
42.8k
917
42.8k
  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
918
42.8k
  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
919
42.8k
  if (min == max)
920
3
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
921
42.8k
922
42.8k
  return ConstantRange(std::move(min), std::move(max));
923
42.8k
}
924
925
177M
ConstantRange ConstantRange::inverse() const {
926
177M
  if (isFullSet())
927
49.7M
    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
928
127M
  
if (127M
isEmptySet()127M
)
929
323
    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
930
127M
  return ConstantRange(Upper, Lower);
931
127M
}
932
933
3.96k
void ConstantRange::print(raw_ostream &OS) const {
934
3.96k
  if (isFullSet())
935
1.91k
    OS << "full-set";
936
2.05k
  else 
if (2.05k
isEmptySet()2.05k
)
937
2
    OS << "empty-set";
938
2.05k
  else
939
2.05k
    OS << "[" << Lower << "," << Upper << ")";
940
3.96k
}
941
942
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
943
LLVM_DUMP_METHOD void ConstantRange::dump() const {
944
  print(dbgs());
945
}
946
#endif
947
948
798k
ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
949
798k
  const unsigned NumRanges = Ranges.getNumOperands() / 2;
950
798k
  assert(NumRanges >= 1 && "Must have at least one range!");
951
798k
  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
952
798k
953
798k
  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
954
798k
  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
955
798k
956
798k
  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
957
798k
958
798k
  for (unsigned i = 1; 
i < NumRanges798k
;
++i8
) {
959
8
    auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
960
8
    auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
961
8
962
8
    // Note: unionWith will potentially create a range that contains values not
963
8
    // contained in any of the original N ranges.
964
8
    CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
965
8
  }
966
798k
967
798k
  return CR;
968
798k
}