Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Line
Count
Source (jump to first uncovered line)
1
//== RangeConstraintManager.cpp - Manage range constraints.------*- 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
//  This file defines RangeConstraintManager, a class that tracks simple
10
//  equality and inequality constraints on symbolic values of ProgramState.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/Basic/JsonSupport.h"
15
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
16
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
19
#include "llvm/ADT/FoldingSet.h"
20
#include "llvm/ADT/ImmutableSet.h"
21
#include "llvm/Support/raw_ostream.h"
22
23
using namespace clang;
24
using namespace ento;
25
26
void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
27
                      const llvm::APSInt &Lower, const llvm::APSInt &Upper,
28
                      PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
29
248k
                      PrimRangeSet::iterator &e) const {
30
248k
  // There are six cases for each range R in the set:
31
248k
  //   1. R is entirely before the intersection range.
32
248k
  //   2. R is entirely after the intersection range.
33
248k
  //   3. R contains the entire intersection range.
34
248k
  //   4. R starts before the intersection range and ends in the middle.
35
248k
  //   5. R starts in the middle of the intersection range and ends after it.
36
248k
  //   6. R is entirely contained in the intersection range.
37
248k
  // These correspond to each of the conditions below.
38
273k
  for (/* i = begin(), e = end() */; i != e; 
++i25.6k
) {
39
251k
    if (i->To() < Lower) {
40
3.99k
      continue;
41
3.99k
    }
42
247k
    if (i->From() > Upper) {
43
52.6k
      break;
44
52.6k
    }
45
195k
46
195k
    if (i->Includes(Lower)) {
47
191k
      if (i->Includes(Upper)) {
48
171k
        newRanges =
49
171k
            F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
50
171k
        break;
51
171k
      } else
52
20.4k
        newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
53
191k
    } else {
54
3.08k
      if (i->Includes(Upper)) {
55
1.96k
        newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
56
1.96k
        break;
57
1.96k
      } else
58
1.12k
        newRanges = F.add(newRanges, *i);
59
3.08k
    }
60
195k
  }
61
248k
}
62
63
219k
const llvm::APSInt &RangeSet::getMinValue() const {
64
219k
  assert(!isEmpty());
65
219k
  return ranges.begin()->From();
66
219k
}
67
68
219k
bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
69
219k
  // This function has nine cases, the cartesian product of range-testing
70
219k
  // both the upper and lower bounds against the symbol's type.
71
219k
  // Each case requires a different pinning operation.
72
219k
  // The function returns false if the described range is entirely outside
73
219k
  // the range of values for the associated symbol.
74
219k
  APSIntType Type(getMinValue());
75
219k
  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
76
219k
  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
77
219k
78
219k
  switch (LowerTest) {
79
219k
  case APSIntType::RTR_Below:
80
30
    switch (UpperTest) {
81
30
    case APSIntType::RTR_Below:
82
10
      // The entire range is outside the symbol's set of possible values.
83
10
      // If this is a conventionally-ordered range, the state is infeasible.
84
10
      if (Lower <= Upper)
85
7
        return false;
86
3
87
3
      // However, if the range wraps around, it spans all possible values.
88
3
      Lower = Type.getMinValue();
89
3
      Upper = Type.getMaxValue();
90
3
      break;
91
16
    case APSIntType::RTR_Within:
92
16
      // The range starts below what's possible but ends within it. Pin.
93
16
      Lower = Type.getMinValue();
94
16
      Type.apply(Upper);
95
16
      break;
96
4
    case APSIntType::RTR_Above:
97
4
      // The range spans all possible values for the symbol. Pin.
98
4
      Lower = Type.getMinValue();
99
4
      Upper = Type.getMaxValue();
100
4
      break;
101
23
    }
102
23
    break;
103
219k
  case APSIntType::RTR_Within:
104
219k
    switch (UpperTest) {
105
219k
    case APSIntType::RTR_Below:
106
26
      // The range wraps around, but all lower values are not possible.
107
26
      Type.apply(Lower);
108
26
      Upper = Type.getMaxValue();
109
26
      break;
110
219k
    case APSIntType::RTR_Within:
111
219k
      // The range may or may not wrap around, but both limits are valid.
112
219k
      Type.apply(Lower);
113
219k
      Type.apply(Upper);
114
219k
      break;
115
219k
    case APSIntType::RTR_Above:
116
6
      // The range starts within what's possible but ends above it. Pin.
117
6
      Type.apply(Lower);
118
6
      Upper = Type.getMaxValue();
119
6
      break;
120
219k
    }
121
219k
    break;
122
219k
  case APSIntType::RTR_Above:
123
13
    switch (UpperTest) {
124
13
    case APSIntType::RTR_Below:
125
4
      // The range wraps but is outside the symbol's set of possible values.
126
4
      return false;
127
13
    case APSIntType::RTR_Within:
128
6
      // The range starts above what's possible but ends within it (wrap).
129
6
      Lower = Type.getMinValue();
130
6
      Type.apply(Upper);
131
6
      break;
132
13
    case APSIntType::RTR_Above:
133
3
      // The entire range is outside the symbol's set of possible values.
134
3
      // If this is a conventionally-ordered range, the state is infeasible.
135
3
      if (Lower <= Upper)
136
2
        return false;
137
1
138
1
      // However, if the range wraps around, it spans all possible values.
139
1
      Lower = Type.getMinValue();
140
1
      Upper = Type.getMaxValue();
141
1
      break;
142
7
    }
143
7
    break;
144
219k
  }
145
219k
146
219k
  return true;
147
219k
}
148
149
// Returns a set containing the values in the receiving set, intersected with
150
// the closed range [Lower, Upper]. Unlike the Range type, this range uses
151
// modular arithmetic, corresponding to the common treatment of C integer
152
// overflow. Thus, if the Lower bound is greater than the Upper bound, the
153
// range is taken to wrap around. This is equivalent to taking the
154
// intersection with the two ranges [Min, Upper] and [Lower, Max],
155
// or, alternatively, /removing/ all integers between Upper and Lower.
156
RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
157
219k
                             llvm::APSInt Lower, llvm::APSInt Upper) const {
158
219k
  if (!pin(Lower, Upper))
159
13
    return F.getEmptySet();
160
219k
161
219k
  PrimRangeSet newRanges = F.getEmptySet();
162
219k
163
219k
  PrimRangeSet::iterator i = begin(), e = end();
164
219k
  if (Lower <= Upper)
165
191k
    IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
166
28.2k
  else {
167
28.2k
    // The order of the next two statements is important!
168
28.2k
    // IntersectInRange() does not reset the iteration state for i and e.
169
28.2k
    // Therefore, the lower range most be handled first.
170
28.2k
    IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
171
28.2k
    IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
172
28.2k
  }
173
219k
174
219k
  return newRanges;
175
219k
}
176
177
// Returns a set containing the values in the receiving set, intersected with
178
// the range set passed as parameter.
179
RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
180
54
                             const RangeSet &Other) const {
181
54
  PrimRangeSet newRanges = F.getEmptySet();
182
54
183
155
  for (iterator i = Other.begin(), e = Other.end(); i != e; 
++i101
) {
184
101
    RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
185
186
    for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; 
++j85
) {
186
85
      newRanges = F.add(newRanges, *j);
187
85
    }
188
101
  }
189
54
190
54
  return newRanges;
191
54
}
192
193
// Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set
194
// [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal
195
// signed values of the type.
196
135
RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
197
135
  PrimRangeSet newRanges = F.getEmptySet();
198
135
199
350
  for (iterator i = begin(), e = end(); i != e; 
++i215
) {
200
215
    const llvm::APSInt &from = i->From(), &to = i->To();
201
215
    const llvm::APSInt &newTo = (from.isMinSignedValue() ?
202
31
                                 BV.getMaxValue(from) :
203
215
                                 
BV.getValue(- from)184
);
204
215
    if (to.isMaxSignedValue() && 
!newRanges.isEmpty()19
&&
205
215
        
newRanges.begin()->From().isMinSignedValue()10
) {
206
10
      assert(newRanges.begin()->To().isMinSignedValue() &&
207
10
             "Ranges should not overlap");
208
10
      assert(!from.isMinSignedValue() && "Ranges should not overlap");
209
10
      const llvm::APSInt &newFrom = newRanges.begin()->From();
210
10
      newRanges =
211
10
        F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo));
212
205
    } else if (!to.isMinSignedValue()) {
213
198
      const llvm::APSInt &newFrom = BV.getValue(- to);
214
198
      newRanges = F.add(newRanges, Range(newFrom, newTo));
215
198
    }
216
215
    if (from.isMinSignedValue()) {
217
31
      newRanges = F.add(newRanges, Range(BV.getMinValue(from),
218
31
                                         BV.getMinValue(from)));
219
31
    }
220
215
  }
221
135
222
135
  return newRanges;
223
135
}
224
225
1
void RangeSet::print(raw_ostream &os) const {
226
1
  bool isFirst = true;
227
1
  os << "{ ";
228
2
  for (iterator i = begin(), e = end(); i != e; 
++i1
) {
229
1
    if (isFirst)
230
1
      isFirst = false;
231
0
    else
232
0
      os << ", ";
233
1
234
1
    os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
235
1
       << ']';
236
1
  }
237
1
  os << " }";
238
1
}
239
240
namespace {
241
class RangeConstraintManager : public RangedConstraintManager {
242
public:
243
  RangeConstraintManager(SubEngine *SE, SValBuilder &SVB)
244
10.8k
      : RangedConstraintManager(SE, SVB) {}
245
246
  //===------------------------------------------------------------------===//
247
  // Implementation for interface from ConstraintManager.
248
  //===------------------------------------------------------------------===//
249
250
  bool haveEqualConstraints(ProgramStateRef S1,
251
4.54k
                            ProgramStateRef S2) const override {
252
4.54k
    return S1->get<ConstraintRange>() == S2->get<ConstraintRange>();
253
4.54k
  }
254
255
  bool canReasonAbout(SVal X) const override;
256
257
  ConditionTruthVal checkNull(ProgramStateRef State, SymbolRef Sym) override;
258
259
  const llvm::APSInt *getSymVal(ProgramStateRef State,
260
                                SymbolRef Sym) const override;
261
262
  ProgramStateRef removeDeadBindings(ProgramStateRef State,
263
                                     SymbolReaper &SymReaper) override;
264
265
  void printJson(raw_ostream &Out, ProgramStateRef State, const char *NL = "\n",
266
                 unsigned int Space = 0, bool IsDot = false) const override;
267
268
  //===------------------------------------------------------------------===//
269
  // Implementation for interface from RangedConstraintManager.
270
  //===------------------------------------------------------------------===//
271
272
  ProgramStateRef assumeSymNE(ProgramStateRef State, SymbolRef Sym,
273
                              const llvm::APSInt &V,
274
                              const llvm::APSInt &Adjustment) override;
275
276
  ProgramStateRef assumeSymEQ(ProgramStateRef State, SymbolRef Sym,
277
                              const llvm::APSInt &V,
278
                              const llvm::APSInt &Adjustment) override;
279
280
  ProgramStateRef assumeSymLT(ProgramStateRef State, SymbolRef Sym,
281
                              const llvm::APSInt &V,
282
                              const llvm::APSInt &Adjustment) override;
283
284
  ProgramStateRef assumeSymGT(ProgramStateRef State, SymbolRef Sym,
285
                              const llvm::APSInt &V,
286
                              const llvm::APSInt &Adjustment) override;
287
288
  ProgramStateRef assumeSymLE(ProgramStateRef State, SymbolRef Sym,
289
                              const llvm::APSInt &V,
290
                              const llvm::APSInt &Adjustment) override;
291
292
  ProgramStateRef assumeSymGE(ProgramStateRef State, SymbolRef Sym,
293
                              const llvm::APSInt &V,
294
                              const llvm::APSInt &Adjustment) override;
295
296
  ProgramStateRef assumeSymWithinInclusiveRange(
297
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
298
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
299
300
  ProgramStateRef assumeSymOutsideInclusiveRange(
301
      ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
302
      const llvm::APSInt &To, const llvm::APSInt &Adjustment) override;
303
304
private:
305
  RangeSet::Factory F;
306
307
  RangeSet getRange(ProgramStateRef State, SymbolRef Sym);
308
  const RangeSet* getRangeForMinusSymbol(ProgramStateRef State,
309
                                         SymbolRef Sym);
310
311
  RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym,
312
                         const llvm::APSInt &Int,
313
                         const llvm::APSInt &Adjustment);
314
  RangeSet getSymGTRange(ProgramStateRef St, SymbolRef Sym,
315
                         const llvm::APSInt &Int,
316
                         const llvm::APSInt &Adjustment);
317
  RangeSet getSymLERange(ProgramStateRef St, SymbolRef Sym,
318
                         const llvm::APSInt &Int,
319
                         const llvm::APSInt &Adjustment);
320
  RangeSet getSymLERange(llvm::function_ref<RangeSet()> RS,
321
                         const llvm::APSInt &Int,
322
                         const llvm::APSInt &Adjustment);
323
  RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym,
324
                         const llvm::APSInt &Int,
325
                         const llvm::APSInt &Adjustment);
326
327
};
328
329
} // end anonymous namespace
330
331
std::unique_ptr<ConstraintManager>
332
10.8k
ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) {
333
10.8k
  return llvm::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
334
10.8k
}
335
336
667k
bool RangeConstraintManager::canReasonAbout(SVal X) const {
337
667k
  Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
338
667k
  if (SymVal && 
SymVal->isExpression()166k
) {
339
161k
    const SymExpr *SE = SymVal->getSymbol();
340
161k
341
161k
    if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
342
157k
      switch (SIE->getOpcode()) {
343
157k
      // We don't reason yet about bitwise-constraints on symbolic values.
344
157k
      case BO_And:
345
21
      case BO_Or:
346
21
      case BO_Xor:
347
21
        return false;
348
21
      // We don't reason yet about these arithmetic constraints on
349
21
      // symbolic values.
350
21
      case BO_Mul:
351
8
      case BO_Div:
352
8
      case BO_Rem:
353
8
      case BO_Shl:
354
8
      case BO_Shr:
355
8
        return false;
356
8
      // All other cases.
357
157k
      default:
358
157k
        return true;
359
4.32k
      }
360
4.32k
    }
361
4.32k
362
4.32k
    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
363
4.31k
      // FIXME: Handle <=> here.
364
4.31k
      if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
365
4.31k
          
BinaryOperator::isRelationalOp(SSE->getOpcode())3.62k
) {
366
4.28k
        // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
367
4.28k
        // We've recently started producing Loc <> NonLoc comparisons (that
368
4.28k
        // result from casts of one of the operands between eg. intptr_t and
369
4.28k
        // void *), but we can't reason about them yet.
370
4.28k
        if (Loc::isLocType(SSE->getLHS()->getType())) {
371
597
          return Loc::isLocType(SSE->getRHS()->getType());
372
597
        }
373
3.72k
      }
374
4.31k
    }
375
3.72k
376
3.72k
    return false;
377
3.72k
  }
378
506k
379
506k
  return true;
380
506k
}
381
382
ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
383
46.2k
                                                    SymbolRef Sym) {
384
46.2k
  const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
385
46.2k
386
46.2k
  // If we don't have any information about this symbol, it's underconstrained.
387
46.2k
  if (!Ranges)
388
22.2k
    return ConditionTruthVal();
389
24.0k
390
24.0k
  // If we have a concrete value, see if it's zero.
391
24.0k
  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
392
11.9k
    return *Value == 0;
393
12.1k
394
12.1k
  BasicValueFactory &BV = getBasicVals();
395
12.1k
  APSIntType IntType = BV.getAPSIntType(Sym->getType());
396
12.1k
  llvm::APSInt Zero = IntType.getZeroValue();
397
12.1k
398
12.1k
  // Check if zero is in the set of possible values.
399
12.1k
  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
400
12.1k
    return false;
401
2
402
2
  // Zero is a possible value, but it is not the /only/ possible value.
403
2
  return ConditionTruthVal();
404
2
}
405
406
const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
407
191k
                                                      SymbolRef Sym) const {
408
191k
  const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym);
409
191k
  return T ? 
T->getConcreteValue()31.7k
:
nullptr159k
;
410
191k
}
411
412
/// Scan all symbols referenced by the constraints. If the symbol is not alive
413
/// as marked in LSymbols, mark it as dead in DSymbols.
414
ProgramStateRef
415
RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
416
640k
                                           SymbolReaper &SymReaper) {
417
640k
  bool Changed = false;
418
640k
  ConstraintRangeTy CR = State->get<ConstraintRange>();
419
640k
  ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>();
420
640k
421
4.41M
  for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; 
++I3.77M
) {
422
3.77M
    SymbolRef Sym = I.getKey();
423
3.77M
    if (SymReaper.isDead(Sym)) {
424
109k
      Changed = true;
425
109k
      CR = CRFactory.remove(CR, Sym);
426
109k
    }
427
3.77M
  }
428
640k
429
640k
  return Changed ? 
State->set<ConstraintRange>(CR)53.1k
:
State587k
;
430
640k
}
431
432
/// Return a range set subtracting zero from \p Domain.
433
static RangeSet assumeNonZero(
434
    BasicValueFactory &BV,
435
    RangeSet::Factory &F,
436
    SymbolRef Sym,
437
4.72k
    RangeSet Domain) {
438
4.72k
  APSIntType IntType = BV.getAPSIntType(Sym->getType());
439
4.72k
  return Domain.Intersect(BV, F, ++IntType.getZeroValue(),
440
4.72k
      --IntType.getZeroValue());
441
4.72k
}
442
443
/// Apply implicit constraints for bitwise OR- and AND-.
444
/// For unsigned types, bitwise OR with a constant always returns
445
/// a value greater-or-equal than the constant, and bitwise AND
446
/// returns a value less-or-equal then the constant.
447
///
448
/// Pattern matches the expression \p Sym against those rule,
449
/// and applies the required constraints.
450
/// \p Input Previously established expression range set
451
static RangeSet applyBitwiseConstraints(
452
    BasicValueFactory &BV,
453
    RangeSet::Factory &F,
454
    RangeSet Input,
455
36.1k
    const SymIntExpr* SIE) {
456
36.1k
  QualType T = SIE->getType();
457
36.1k
  bool IsUnsigned = T->isUnsignedIntegerType();
458
36.1k
  const llvm::APSInt &RHS = SIE->getRHS();
459
36.1k
  const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue();
460
36.1k
  BinaryOperator::Opcode Operator = SIE->getOpcode();
461
36.1k
462
36.1k
  // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
463
36.1k
  if (Operator == BO_Or && 
IsUnsigned18
)
464
11
    return Input.Intersect(BV, F, RHS, BV.getMaxValue(T));
465
36.1k
466
36.1k
  // Bitwise-or with a non-zero constant is always non-zero.
467
36.1k
  if (Operator == BO_Or && 
RHS != Zero7
)
468
7
    return assumeNonZero(BV, F, SIE, Input);
469
36.1k
470
36.1k
  // For unsigned types, or positive RHS,
471
36.1k
  // bitwise-and output is always smaller-or-equal than RHS (assuming two's
472
36.1k
  // complement representation of signed types).
473
36.1k
  if (Operator == BO_And && 
(36.0k
IsUnsigned36.0k
||
RHS >= Zero36.0k
))
474
36.0k
    return Input.Intersect(BV, F, BV.getMinValue(T), RHS);
475
142
476
142
  return Input;
477
142
}
478
479
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
480
166k
                                          SymbolRef Sym) {
481
166k
  ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
482
166k
483
166k
  // If Sym is a difference of symbols A - B, then maybe we have range set
484
166k
  // stored for B - A.
485
166k
  BasicValueFactory &BV = getBasicVals();
486
166k
  const RangeSet *R = getRangeForMinusSymbol(State, Sym);
487
166k
488
166k
  // If we have range set stored for both A - B and B - A then calculate the
489
166k
  // effective range set by intersecting the range set for A - B and the
490
166k
  // negated range set of B - A.
491
166k
  if (V && 
R80.4k
)
492
54
    return V->Intersect(BV, F, R->Negate(BV, F));
493
166k
  if (V)
494
80.3k
    return *V;
495
86.3k
  if (R)
496
81
    return R->Negate(BV, F);
497
86.2k
498
86.2k
  // Lazily generate a new RangeSet representing all possible values for the
499
86.2k
  // given symbol type.
500
86.2k
  QualType T = Sym->getType();
501
86.2k
502
86.2k
  RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
503
86.2k
504
86.2k
  // References are known to be non-zero.
505
86.2k
  if (T->isReferenceType())
506
4.72k
    return assumeNonZero(BV, F, Sym, Result);
507
81.5k
508
81.5k
  // Known constraints on ranges of bitwise expressions.
509
81.5k
  if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym))
510
36.1k
    return applyBitwiseConstraints(BV, F, Result, SIE);
511
45.3k
512
45.3k
  return Result;
513
45.3k
}
514
515
// FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
516
//        obtain the negated symbolic expression instead of constructing the
517
//        symbol manually. This will allow us to support finding ranges of not
518
//        only negated SymSymExpr-type expressions, but also of other, simpler
519
//        expressions which we currently do not know how to negate.
520
const RangeSet*
521
RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State,
522
166k
                                               SymbolRef Sym) {
523
166k
  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
524
4.95k
    if (SSE->getOpcode() == BO_Sub) {
525
1.11k
      QualType T = Sym->getType();
526
1.11k
      SymbolManager &SymMgr = State->getSymbolManager();
527
1.11k
      SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub,
528
1.11k
                                              SSE->getLHS(), T);
529
1.11k
      if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
530
135
        // Unsigned range set cannot be negated, unless it is [0, 0].
531
135
        if ((negV->getConcreteValue() &&
532
135
             
(*negV->getConcreteValue() == 0)22
) ||
533
135
            
T->isSignedIntegerOrEnumerationType()117
)
534
135
          return negV;
535
166k
      }
536
1.11k
    }
537
4.95k
  }
538
166k
  return nullptr;
539
166k
}
540
541
//===------------------------------------------------------------------------===
542
// assumeSymX methods: protected interface for RangeConstraintManager.
543
//===------------------------------------------------------------------------===/
544
545
// The syntax for ranges below is mathematical, using [x, y] for closed ranges
546
// and (x, y) for open ranges. These ranges are modular, corresponding with
547
// a common treatment of C integer overflow. This means that these methods
548
// do not have to worry about overflow; RangeSet::Intersect can handle such a
549
// "wraparound" range.
550
// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
551
// UINT_MAX, 0, 1, and 2.
552
553
ProgramStateRef
554
RangeConstraintManager::assumeSymNE(ProgramStateRef St, SymbolRef Sym,
555
                                    const llvm::APSInt &Int,
556
75.9k
                                    const llvm::APSInt &Adjustment) {
557
75.9k
  // Before we do any real work, see if the value can even show up.
558
75.9k
  APSIntType AdjustmentType(Adjustment);
559
75.9k
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
560
3
    return St;
561
75.9k
562
75.9k
  llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
563
75.9k
  llvm::APSInt Upper = Lower;
564
75.9k
  --Lower;
565
75.9k
  ++Upper;
566
75.9k
567
75.9k
  // [Int-Adjustment+1, Int-Adjustment-1]
568
75.9k
  // Notice that the lower bound is greater than the upper bound.
569
75.9k
  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
570
75.9k
  return New.isEmpty() ? 
nullptr254
:
St->set<ConstraintRange>(Sym, New)75.6k
;
571
75.9k
}
572
573
ProgramStateRef
574
RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
575
                                    const llvm::APSInt &Int,
576
75.4k
                                    const llvm::APSInt &Adjustment) {
577
75.4k
  // Before we do any real work, see if the value can even show up.
578
75.4k
  APSIntType AdjustmentType(Adjustment);
579
75.4k
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
580
3
    return nullptr;
581
75.4k
582
75.4k
  // [Int-Adjustment, Int-Adjustment]
583
75.4k
  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
584
75.4k
  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
585
75.4k
  return New.isEmpty() ? 
nullptr38.2k
:
St->set<ConstraintRange>(Sym, New)37.1k
;
586
75.4k
}
587
588
RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
589
                                               SymbolRef Sym,
590
                                               const llvm::APSInt &Int,
591
3.74k
                                               const llvm::APSInt &Adjustment) {
592
3.74k
  // Before we do any real work, see if the value can even show up.
593
3.74k
  APSIntType AdjustmentType(Adjustment);
594
3.74k
  switch (AdjustmentType.testInRange(Int, true)) {
595
3.74k
  case APSIntType::RTR_Below:
596
2
    return F.getEmptySet();
597
3.74k
  case APSIntType::RTR_Within:
598
3.74k
    break;
599
3.74k
  case APSIntType::RTR_Above:
600
2
    return getRange(St, Sym);
601
3.74k
  }
602
3.74k
603
3.74k
  // Special case for Int == Min. This is always false.
604
3.74k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
605
3.74k
  llvm::APSInt Min = AdjustmentType.getMinValue();
606
3.74k
  if (ComparisonVal == Min)
607
429
    return F.getEmptySet();
608
3.31k
609
3.31k
  llvm::APSInt Lower = Min - Adjustment;
610
3.31k
  llvm::APSInt Upper = ComparisonVal - Adjustment;
611
3.31k
  --Upper;
612
3.31k
613
3.31k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
614
3.31k
}
615
616
ProgramStateRef
617
RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
618
                                    const llvm::APSInt &Int,
619
2.39k
                                    const llvm::APSInt &Adjustment) {
620
2.39k
  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
621
2.39k
  return New.isEmpty() ? 
nullptr1.15k
:
St->set<ConstraintRange>(Sym, New)1.23k
;
622
2.39k
}
623
624
RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
625
                                               SymbolRef Sym,
626
                                               const llvm::APSInt &Int,
627
5.75k
                                               const llvm::APSInt &Adjustment) {
628
5.75k
  // Before we do any real work, see if the value can even show up.
629
5.75k
  APSIntType AdjustmentType(Adjustment);
630
5.75k
  switch (AdjustmentType.testInRange(Int, true)) {
631
5.75k
  case APSIntType::RTR_Below:
632
2
    return getRange(St, Sym);
633
5.75k
  case APSIntType::RTR_Within:
634
5.75k
    break;
635
5.75k
  case APSIntType::RTR_Above:
636
2
    return F.getEmptySet();
637
5.75k
  }
638
5.75k
639
5.75k
  // Special case for Int == Max. This is always false.
640
5.75k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
641
5.75k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
642
5.75k
  if (ComparisonVal == Max)
643
353
    return F.getEmptySet();
644
5.39k
645
5.39k
  llvm::APSInt Lower = ComparisonVal - Adjustment;
646
5.39k
  llvm::APSInt Upper = Max - Adjustment;
647
5.39k
  ++Lower;
648
5.39k
649
5.39k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
650
5.39k
}
651
652
ProgramStateRef
653
RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
654
                                    const llvm::APSInt &Int,
655
4.40k
                                    const llvm::APSInt &Adjustment) {
656
4.40k
  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
657
4.40k
  return New.isEmpty() ? 
nullptr1.06k
:
St->set<ConstraintRange>(Sym, New)3.34k
;
658
4.40k
}
659
660
RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
661
                                               SymbolRef Sym,
662
                                               const llvm::APSInt &Int,
663
2.29k
                                               const llvm::APSInt &Adjustment) {
664
2.29k
  // Before we do any real work, see if the value can even show up.
665
2.29k
  APSIntType AdjustmentType(Adjustment);
666
2.29k
  switch (AdjustmentType.testInRange(Int, true)) {
667
2.29k
  case APSIntType::RTR_Below:
668
2
    return getRange(St, Sym);
669
2.29k
  case APSIntType::RTR_Within:
670
2.29k
    break;
671
2.29k
  case APSIntType::RTR_Above:
672
2
    return F.getEmptySet();
673
2.29k
  }
674
2.29k
675
2.29k
  // Special case for Int == Min. This is always feasible.
676
2.29k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
677
2.29k
  llvm::APSInt Min = AdjustmentType.getMinValue();
678
2.29k
  if (ComparisonVal == Min)
679
52
    return getRange(St, Sym);
680
2.23k
681
2.23k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
682
2.23k
  llvm::APSInt Lower = ComparisonVal - Adjustment;
683
2.23k
  llvm::APSInt Upper = Max - Adjustment;
684
2.23k
685
2.23k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
686
2.23k
}
687
688
ProgramStateRef
689
RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
690
                                    const llvm::APSInt &Int,
691
1.86k
                                    const llvm::APSInt &Adjustment) {
692
1.86k
  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
693
1.86k
  return New.isEmpty() ? 
nullptr206
:
St->set<ConstraintRange>(Sym, New)1.66k
;
694
1.86k
}
695
696
RangeSet RangeConstraintManager::getSymLERange(
697
      llvm::function_ref<RangeSet()> RS,
698
      const llvm::APSInt &Int,
699
4.73k
      const llvm::APSInt &Adjustment) {
700
4.73k
  // Before we do any real work, see if the value can even show up.
701
4.73k
  APSIntType AdjustmentType(Adjustment);
702
4.73k
  switch (AdjustmentType.testInRange(Int, true)) {
703
4.73k
  case APSIntType::RTR_Below:
704
2
    return F.getEmptySet();
705
4.73k
  case APSIntType::RTR_Within:
706
4.72k
    break;
707
4.73k
  case APSIntType::RTR_Above:
708
2
    return RS();
709
4.72k
  }
710
4.72k
711
4.72k
  // Special case for Int == Max. This is always feasible.
712
4.72k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
713
4.72k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
714
4.72k
  if (ComparisonVal == Max)
715
22
    return RS();
716
4.70k
717
4.70k
  llvm::APSInt Min = AdjustmentType.getMinValue();
718
4.70k
  llvm::APSInt Lower = Min - Adjustment;
719
4.70k
  llvm::APSInt Upper = ComparisonVal - Adjustment;
720
4.70k
721
4.70k
  return RS().Intersect(getBasicVals(), F, Lower, Upper);
722
4.70k
}
723
724
RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
725
                                               SymbolRef Sym,
726
                                               const llvm::APSInt &Int,
727
4.38k
                                               const llvm::APSInt &Adjustment) {
728
4.38k
  return getSymLERange([&] 
{ return getRange(St, Sym); }4.38k
, Int, Adjustment);
729
4.38k
}
730
731
ProgramStateRef
732
RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
733
                                    const llvm::APSInt &Int,
734
4.38k
                                    const llvm::APSInt &Adjustment) {
735
4.38k
  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
736
4.38k
  return New.isEmpty() ? 
nullptr233
:
St->set<ConstraintRange>(Sym, New)4.15k
;
737
4.38k
}
738
739
ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
740
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
741
425
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
742
425
  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
743
425
  if (New.isEmpty())
744
79
    return nullptr;
745
346
  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
746
346
  return Out.isEmpty() ? 
nullptr42
:
State->set<ConstraintRange>(Sym, Out)304
;
747
346
}
748
749
ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
750
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
751
1.34k
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
752
1.34k
  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
753
1.34k
  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
754
1.34k
  RangeSet New(RangeLT.addRange(F, RangeGT));
755
1.34k
  return New.isEmpty() ? 
nullptr42
:
State->set<ConstraintRange>(Sym, New)1.30k
;
756
1.34k
}
757
758
//===----------------------------------------------------------------------===//
759
// Pretty-printing.
760
//===----------------------------------------------------------------------===//
761
762
void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
763
                                       const char *NL, unsigned int Space,
764
4
                                       bool IsDot) const {
765
4
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
766
4
767
4
  Indent(Out, Space, IsDot) << "\"constraints\": ";
768
4
  if (Constraints.isEmpty()) {
769
3
    Out << "null," << NL;
770
3
    return;
771
3
  }
772
1
773
1
  ++Space;
774
1
  Out << '[' << NL;
775
1
  for (ConstraintRangeTy::iterator I = Constraints.begin();
776
2
       I != Constraints.end(); 
++I1
) {
777
1
    Indent(Out, Space, IsDot)
778
1
        << "{ \"symbol\": \"" << I.getKey() << "\", \"range\": \"";
779
1
    I.getData().print(Out);
780
1
    Out << "\" }";
781
1
782
1
    if (std::next(I) != Constraints.end())
783
0
      Out << ',';
784
1
    Out << NL;
785
1
  }
786
1
787
1
  --Space;
788
1
  Indent(Out, Space, IsDot) << "]," << NL;
789
1
}