Coverage Report

Created: 2020-02-25 14:32

/Users/buildslave/jenkins/workspace/coverage/llvm-project/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
270k
                      PrimRangeSet::iterator &e) const {
30
270k
  // There are six cases for each range R in the set:
31
270k
  //   1. R is entirely before the intersection range.
32
270k
  //   2. R is entirely after the intersection range.
33
270k
  //   3. R contains the entire intersection range.
34
270k
  //   4. R starts before the intersection range and ends in the middle.
35
270k
  //   5. R starts in the middle of the intersection range and ends after it.
36
270k
  //   6. R is entirely contained in the intersection range.
37
270k
  // These correspond to each of the conditions below.
38
300k
  for (/* i = begin(), e = end() */; i != e; 
++i29.6k
) {
39
274k
    if (i->To() < Lower) {
40
6.50k
      continue;
41
6.50k
    }
42
268k
    if (i->From() > Upper) {
43
57.6k
      break;
44
57.6k
    }
45
210k
46
210k
    if (i->Includes(Lower)) {
47
206k
      if (i->Includes(Upper)) {
48
185k
        newRanges =
49
185k
            F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
50
185k
        break;
51
185k
      } else
52
21.9k
        newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
53
206k
    } else {
54
3.58k
      if (i->Includes(Upper)) {
55
2.33k
        newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
56
2.33k
        break;
57
2.33k
      } else
58
1.25k
        newRanges = F.add(newRanges, *i);
59
3.58k
    }
60
210k
  }
61
270k
}
62
63
242k
const llvm::APSInt &RangeSet::getMinValue() const {
64
242k
  assert(!isEmpty());
65
242k
  return ranges.begin()->From();
66
242k
}
67
68
242k
bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
69
242k
  // This function has nine cases, the cartesian product of range-testing
70
242k
  // both the upper and lower bounds against the symbol's type.
71
242k
  // Each case requires a different pinning operation.
72
242k
  // The function returns false if the described range is entirely outside
73
242k
  // the range of values for the associated symbol.
74
242k
  APSIntType Type(getMinValue());
75
242k
  APSIntType::RangeTestResultKind LowerTest = Type.testInRange(Lower, true);
76
242k
  APSIntType::RangeTestResultKind UpperTest = Type.testInRange(Upper, true);
77
242k
78
242k
  switch (LowerTest) {
79
24
  case APSIntType::RTR_Below:
80
24
    switch (UpperTest) {
81
4
    case APSIntType::RTR_Below:
82
4
      // The entire range is outside the symbol's set of possible values.
83
4
      // If this is a conventionally-ordered range, the state is infeasible.
84
4
      if (Lower <= Upper)
85
3
        return false;
86
1
87
1
      // However, if the range wraps around, it spans all possible values.
88
1
      Lower = Type.getMinValue();
89
1
      Upper = Type.getMaxValue();
90
1
      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
21
    }
102
21
    break;
103
242k
  case APSIntType::RTR_Within:
104
242k
    switch (UpperTest) {
105
33
    case APSIntType::RTR_Below:
106
33
      // The range wraps around, but all lower values are not possible.
107
33
      Type.apply(Lower);
108
33
      Upper = Type.getMaxValue();
109
33
      break;
110
242k
    case APSIntType::RTR_Within:
111
242k
      // The range may or may not wrap around, but both limits are valid.
112
242k
      Type.apply(Lower);
113
242k
      Type.apply(Upper);
114
242k
      break;
115
6
    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
242k
    }
121
242k
    break;
122
242k
  case APSIntType::RTR_Above:
123
13
    switch (UpperTest) {
124
4
    case APSIntType::RTR_Below:
125
4
      // The range wraps but is outside the symbol's set of possible values.
126
4
      return false;
127
6
    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
3
    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
242k
  }
145
242k
146
242k
  return true;
147
242k
}
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
242k
                             llvm::APSInt Lower, llvm::APSInt Upper) const {
158
242k
  if (!pin(Lower, Upper))
159
9
    return F.getEmptySet();
160
242k
161
242k
  PrimRangeSet newRanges = F.getEmptySet();
162
242k
163
242k
  PrimRangeSet::iterator i = begin(), e = end();
164
242k
  if (Lower <= Upper)
165
213k
    IntersectInRange(BV, F, Lower, Upper, newRanges, i, e);
166
28.7k
  else {
167
28.7k
    // The order of the next two statements is important!
168
28.7k
    // IntersectInRange() does not reset the iteration state for i and e.
169
28.7k
    // Therefore, the lower range most be handled first.
170
28.7k
    IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
171
28.7k
    IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
172
28.7k
  }
173
242k
174
242k
  return newRanges;
175
242k
}
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
149
                             const RangeSet &Other) const {
181
149
  PrimRangeSet newRanges = F.getEmptySet();
182
149
183
440
  for (iterator i = Other.begin(), e = Other.end(); i != e; 
++i291
) {
184
291
    RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
185
548
    for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; 
++j257
) {
186
257
      newRanges = F.add(newRanges, *j);
187
257
    }
188
291
  }
189
149
190
149
  return newRanges;
191
149
}
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
231
RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const {
197
231
  PrimRangeSet newRanges = F.getEmptySet();
198
231
199
641
  for (iterator i = begin(), e = end(); i != e; 
++i410
) {
200
410
    const llvm::APSInt &from = i->From(), &to = i->To();
201
410
    const llvm::APSInt &newTo = (from.isMinSignedValue() ?
202
33
                                 BV.getMaxValue(from) :
203
410
                                 
BV.getValue(- from)377
);
204
410
    if (to.isMaxSignedValue() && 
!newRanges.isEmpty()21
&&
205
410
        
newRanges.begin()->From().isMinSignedValue()12
) {
206
12
      assert(newRanges.begin()->To().isMinSignedValue() &&
207
12
             "Ranges should not overlap");
208
12
      assert(!from.isMinSignedValue() && "Ranges should not overlap");
209
12
      const llvm::APSInt &newFrom = newRanges.begin()->From();
210
12
      newRanges =
211
12
        F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo));
212
398
    } else if (!to.isMinSignedValue()) {
213
391
      const llvm::APSInt &newFrom = BV.getValue(- to);
214
391
      newRanges = F.add(newRanges, Range(newFrom, newTo));
215
391
    }
216
410
    if (from.isMinSignedValue()) {
217
33
      newRanges = F.add(newRanges, Range(BV.getMinValue(from),
218
33
                                         BV.getMinValue(from)));
219
33
    }
220
410
  }
221
231
222
231
  return newRanges;
223
231
}
224
225
36
void RangeSet::print(raw_ostream &os) const {
226
36
  bool isFirst = true;
227
36
  os << "{ ";
228
72
  for (iterator i = begin(), e = end(); i != e; 
++i36
) {
229
36
    if (isFirst)
230
36
      isFirst = false;
231
0
    else
232
0
      os << ", ";
233
36
234
36
    os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
235
36
       << ']';
236
36
  }
237
36
  os << " }";
238
36
}
239
240
namespace {
241
class RangeConstraintManager : public RangedConstraintManager {
242
public:
243
  RangeConstraintManager(SubEngine *SE, SValBuilder &SVB)
244
12.6k
      : RangedConstraintManager(SE, SVB) {}
245
246
  //===------------------------------------------------------------------===//
247
  // Implementation for interface from ConstraintManager.
248
  //===------------------------------------------------------------------===//
249
250
  bool haveEqualConstraints(ProgramStateRef S1,
251
6.18k
                            ProgramStateRef S2) const override {
252
6.18k
    return S1->get<ConstraintRange>() == S2->get<ConstraintRange>();
253
6.18k
  }
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
12.6k
ento::CreateRangeConstraintManager(ProgramStateManager &StMgr, SubEngine *Eng) {
333
12.6k
  return std::make_unique<RangeConstraintManager>(Eng, StMgr.getSValBuilder());
334
12.6k
}
335
336
890k
bool RangeConstraintManager::canReasonAbout(SVal X) const {
337
890k
  Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
338
890k
  if (SymVal && 
SymVal->isExpression()183k
) {
339
177k
    const SymExpr *SE = SymVal->getSymbol();
340
177k
341
177k
    if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
342
172k
      switch (SIE->getOpcode()) {
343
0
      // We don't reason yet about bitwise-constraints on symbolic values.
344
21
      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
172k
      default:
358
172k
        return true;
359
4.42k
      }
360
4.42k
    }
361
4.42k
362
4.42k
    if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
363
4.41k
      // FIXME: Handle <=> here.
364
4.41k
      if (BinaryOperator::isEqualityOp(SSE->getOpcode()) ||
365
4.41k
          
BinaryOperator::isRelationalOp(SSE->getOpcode())3.56k
) {
366
4.37k
        // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
367
4.37k
        // We've recently started producing Loc <> NonLoc comparisons (that
368
4.37k
        // result from casts of one of the operands between eg. intptr_t and
369
4.37k
        // void *), but we can't reason about them yet.
370
4.37k
        if (Loc::isLocType(SSE->getLHS()->getType())) {
371
689
          return Loc::isLocType(SSE->getRHS()->getType());
372
689
        }
373
3.73k
      }
374
4.41k
    }
375
3.73k
376
3.73k
    return false;
377
3.73k
  }
378
713k
379
713k
  return true;
380
713k
}
381
382
ConditionTruthVal RangeConstraintManager::checkNull(ProgramStateRef State,
383
58.0k
                                                    SymbolRef Sym) {
384
58.0k
  const RangeSet *Ranges = State->get<ConstraintRange>(Sym);
385
58.0k
386
58.0k
  // If we don't have any information about this symbol, it's underconstrained.
387
58.0k
  if (!Ranges)
388
31.3k
    return ConditionTruthVal();
389
26.7k
390
26.7k
  // If we have a concrete value, see if it's zero.
391
26.7k
  if (const llvm::APSInt *Value = Ranges->getConcreteValue())
392
14.2k
    return *Value == 0;
393
12.5k
394
12.5k
  BasicValueFactory &BV = getBasicVals();
395
12.5k
  APSIntType IntType = BV.getAPSIntType(Sym->getType());
396
12.5k
  llvm::APSInt Zero = IntType.getZeroValue();
397
12.5k
398
12.5k
  // Check if zero is in the set of possible values.
399
12.5k
  if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
400
12.5k
    return false;
401
4
402
4
  // Zero is a possible value, but it is not the /only/ possible value.
403
4
  return ConditionTruthVal();
404
4
}
405
406
const llvm::APSInt *RangeConstraintManager::getSymVal(ProgramStateRef St,
407
206k
                                                      SymbolRef Sym) const {
408
206k
  const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(Sym);
409
206k
  return T ? 
T->getConcreteValue()39.4k
:
nullptr167k
;
410
206k
}
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
470k
                                           SymbolReaper &SymReaper) {
417
470k
  bool Changed = false;
418
470k
  ConstraintRangeTy CR = State->get<ConstraintRange>();
419
470k
  ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>();
420
470k
421
2.39M
  for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; 
++I1.92M
) {
422
1.92M
    SymbolRef Sym = I.getKey();
423
1.92M
    if (SymReaper.isDead(Sym)) {
424
57.5k
      Changed = true;
425
57.5k
      CR = CRFactory.remove(CR, Sym);
426
57.5k
    }
427
1.92M
  }
428
470k
429
470k
  return Changed ? 
State->set<ConstraintRange>(CR)28.7k
:
State441k
;
430
470k
}
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
9.18k
    RangeSet Domain) {
438
9.18k
  APSIntType IntType = BV.getAPSIntType(Sym->getType());
439
9.18k
  return Domain.Intersect(BV, F, ++IntType.getZeroValue(),
440
9.18k
      --IntType.getZeroValue());
441
9.18k
}
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.2k
    const SymIntExpr* SIE) {
456
36.2k
  QualType T = SIE->getType();
457
36.2k
  bool IsUnsigned = T->isUnsignedIntegerType();
458
36.2k
  const llvm::APSInt &RHS = SIE->getRHS();
459
36.2k
  const llvm::APSInt &Zero = BV.getAPSIntType(T).getZeroValue();
460
36.2k
  BinaryOperator::Opcode Operator = SIE->getOpcode();
461
36.2k
462
36.2k
  // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
463
36.2k
  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
164
476
164
  return Input;
477
164
}
478
479
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
480
183k
                                          SymbolRef Sym) {
481
183k
  ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
482
183k
483
183k
  // If Sym is a difference of symbols A - B, then maybe we have range set
484
183k
  // stored for B - A.
485
183k
  BasicValueFactory &BV = getBasicVals();
486
183k
  const RangeSet *R = getRangeForMinusSymbol(State, Sym);
487
183k
488
183k
  // If we have range set stored for both A - B and B - A then calculate the
489
183k
  // effective range set by intersecting the range set for A - B and the
490
183k
  // negated range set of B - A.
491
183k
  if (V && 
R87.2k
)
492
149
    return V->Intersect(BV, F, R->Negate(BV, F));
493
183k
  if (V)
494
87.0k
    return *V;
495
96.5k
  if (R)
496
82
    return R->Negate(BV, F);
497
96.4k
498
96.4k
  // Lazily generate a new RangeSet representing all possible values for the
499
96.4k
  // given symbol type.
500
96.4k
  QualType T = Sym->getType();
501
96.4k
502
96.4k
  RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T));
503
96.4k
504
96.4k
  // References are known to be non-zero.
505
96.4k
  if (T->isReferenceType())
506
9.17k
    return assumeNonZero(BV, F, Sym, Result);
507
87.3k
508
87.3k
  // Known constraints on ranges of bitwise expressions.
509
87.3k
  if (const SymIntExpr* SIE = dyn_cast<SymIntExpr>(Sym))
510
36.2k
    return applyBitwiseConstraints(BV, F, Result, SIE);
511
51.1k
512
51.1k
  return Result;
513
51.1k
}
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
183k
                                               SymbolRef Sym) {
523
183k
  if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
524
6.17k
    if (SSE->getOpcode() == BO_Sub) {
525
2.34k
      QualType T = Sym->getType();
526
2.34k
      SymbolManager &SymMgr = State->getSymbolManager();
527
2.34k
      SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub,
528
2.34k
                                              SSE->getLHS(), T);
529
2.34k
      if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) {
530
231
        // Unsigned range set cannot be negated, unless it is [0, 0].
531
231
        if ((negV->getConcreteValue() &&
532
231
             
(*negV->getConcreteValue() == 0)19
) ||
533
231
            
T->isSignedIntegerOrEnumerationType()215
)
534
231
          return negV;
535
183k
      }
536
2.34k
    }
537
6.17k
  }
538
183k
  return nullptr;
539
183k
}
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
81.1k
                                    const llvm::APSInt &Adjustment) {
557
81.1k
  // Before we do any real work, see if the value can even show up.
558
81.1k
  APSIntType AdjustmentType(Adjustment);
559
81.1k
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
560
3
    return St;
561
81.1k
562
81.1k
  llvm::APSInt Lower = AdjustmentType.convert(Int) - Adjustment;
563
81.1k
  llvm::APSInt Upper = Lower;
564
81.1k
  --Lower;
565
81.1k
  ++Upper;
566
81.1k
567
81.1k
  // [Int-Adjustment+1, Int-Adjustment-1]
568
81.1k
  // Notice that the lower bound is greater than the upper bound.
569
81.1k
  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
570
81.1k
  return New.isEmpty() ? 
nullptr360
:
St->set<ConstraintRange>(Sym, New)80.7k
;
571
81.1k
}
572
573
ProgramStateRef
574
RangeConstraintManager::assumeSymEQ(ProgramStateRef St, SymbolRef Sym,
575
                                    const llvm::APSInt &Int,
576
79.7k
                                    const llvm::APSInt &Adjustment) {
577
79.7k
  // Before we do any real work, see if the value can even show up.
578
79.7k
  APSIntType AdjustmentType(Adjustment);
579
79.7k
  if (AdjustmentType.testInRange(Int, true) != APSIntType::RTR_Within)
580
3
    return nullptr;
581
79.7k
582
79.7k
  // [Int-Adjustment, Int-Adjustment]
583
79.7k
  llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
584
79.7k
  RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
585
79.7k
  return New.isEmpty() ? 
nullptr41.0k
:
St->set<ConstraintRange>(Sym, New)38.7k
;
586
79.7k
}
587
588
RangeSet RangeConstraintManager::getSymLTRange(ProgramStateRef St,
589
                                               SymbolRef Sym,
590
                                               const llvm::APSInt &Int,
591
6.09k
                                               const llvm::APSInt &Adjustment) {
592
6.09k
  // Before we do any real work, see if the value can even show up.
593
6.09k
  APSIntType AdjustmentType(Adjustment);
594
6.09k
  switch (AdjustmentType.testInRange(Int, true)) {
595
2
  case APSIntType::RTR_Below:
596
2
    return F.getEmptySet();
597
6.09k
  case APSIntType::RTR_Within:
598
6.09k
    break;
599
2
  case APSIntType::RTR_Above:
600
2
    return getRange(St, Sym);
601
6.09k
  }
602
6.09k
603
6.09k
  // Special case for Int == Min. This is always false.
604
6.09k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
605
6.09k
  llvm::APSInt Min = AdjustmentType.getMinValue();
606
6.09k
  if (ComparisonVal == Min)
607
454
    return F.getEmptySet();
608
5.63k
609
5.63k
  llvm::APSInt Lower = Min - Adjustment;
610
5.63k
  llvm::APSInt Upper = ComparisonVal - Adjustment;
611
5.63k
  --Upper;
612
5.63k
613
5.63k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
614
5.63k
}
615
616
ProgramStateRef
617
RangeConstraintManager::assumeSymLT(ProgramStateRef St, SymbolRef Sym,
618
                                    const llvm::APSInt &Int,
619
4.62k
                                    const llvm::APSInt &Adjustment) {
620
4.62k
  RangeSet New = getSymLTRange(St, Sym, Int, Adjustment);
621
4.62k
  return New.isEmpty() ? 
nullptr3.05k
:
St->set<ConstraintRange>(Sym, New)1.57k
;
622
4.62k
}
623
624
RangeSet RangeConstraintManager::getSymGTRange(ProgramStateRef St,
625
                                               SymbolRef Sym,
626
                                               const llvm::APSInt &Int,
627
7.85k
                                               const llvm::APSInt &Adjustment) {
628
7.85k
  // Before we do any real work, see if the value can even show up.
629
7.85k
  APSIntType AdjustmentType(Adjustment);
630
7.85k
  switch (AdjustmentType.testInRange(Int, true)) {
631
2
  case APSIntType::RTR_Below:
632
2
    return getRange(St, Sym);
633
7.85k
  case APSIntType::RTR_Within:
634
7.85k
    break;
635
2
  case APSIntType::RTR_Above:
636
2
    return F.getEmptySet();
637
7.85k
  }
638
7.85k
639
7.85k
  // Special case for Int == Max. This is always false.
640
7.85k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
641
7.85k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
642
7.85k
  if (ComparisonVal == Max)
643
378
    return F.getEmptySet();
644
7.47k
645
7.47k
  llvm::APSInt Lower = ComparisonVal - Adjustment;
646
7.47k
  llvm::APSInt Upper = Max - Adjustment;
647
7.47k
  ++Lower;
648
7.47k
649
7.47k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
650
7.47k
}
651
652
ProgramStateRef
653
RangeConstraintManager::assumeSymGT(ProgramStateRef St, SymbolRef Sym,
654
                                    const llvm::APSInt &Int,
655
6.38k
                                    const llvm::APSInt &Adjustment) {
656
6.38k
  RangeSet New = getSymGTRange(St, Sym, Int, Adjustment);
657
6.38k
  return New.isEmpty() ? 
nullptr2.87k
:
St->set<ConstraintRange>(Sym, New)3.51k
;
658
6.38k
}
659
660
RangeSet RangeConstraintManager::getSymGERange(ProgramStateRef St,
661
                                               SymbolRef Sym,
662
                                               const llvm::APSInt &Int,
663
3.93k
                                               const llvm::APSInt &Adjustment) {
664
3.93k
  // Before we do any real work, see if the value can even show up.
665
3.93k
  APSIntType AdjustmentType(Adjustment);
666
3.93k
  switch (AdjustmentType.testInRange(Int, true)) {
667
2
  case APSIntType::RTR_Below:
668
2
    return getRange(St, Sym);
669
3.93k
  case APSIntType::RTR_Within:
670
3.93k
    break;
671
2
  case APSIntType::RTR_Above:
672
2
    return F.getEmptySet();
673
3.93k
  }
674
3.93k
675
3.93k
  // Special case for Int == Min. This is always feasible.
676
3.93k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
677
3.93k
  llvm::APSInt Min = AdjustmentType.getMinValue();
678
3.93k
  if (ComparisonVal == Min)
679
52
    return getRange(St, Sym);
680
3.87k
681
3.87k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
682
3.87k
  llvm::APSInt Lower = ComparisonVal - Adjustment;
683
3.87k
  llvm::APSInt Upper = Max - Adjustment;
684
3.87k
685
3.87k
  return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
686
3.87k
}
687
688
ProgramStateRef
689
RangeConstraintManager::assumeSymGE(ProgramStateRef St, SymbolRef Sym,
690
                                    const llvm::APSInt &Int,
691
3.44k
                                    const llvm::APSInt &Adjustment) {
692
3.44k
  RangeSet New = getSymGERange(St, Sym, Int, Adjustment);
693
3.44k
  return New.isEmpty() ? 
nullptr306
:
St->set<ConstraintRange>(Sym, New)3.13k
;
694
3.44k
}
695
696
RangeSet RangeConstraintManager::getSymLERange(
697
      llvm::function_ref<RangeSet()> RS,
698
      const llvm::APSInt &Int,
699
6.27k
      const llvm::APSInt &Adjustment) {
700
6.27k
  // Before we do any real work, see if the value can even show up.
701
6.27k
  APSIntType AdjustmentType(Adjustment);
702
6.27k
  switch (AdjustmentType.testInRange(Int, true)) {
703
2
  case APSIntType::RTR_Below:
704
2
    return F.getEmptySet();
705
6.27k
  case APSIntType::RTR_Within:
706
6.27k
    break;
707
2
  case APSIntType::RTR_Above:
708
2
    return RS();
709
6.27k
  }
710
6.27k
711
6.27k
  // Special case for Int == Max. This is always feasible.
712
6.27k
  llvm::APSInt ComparisonVal = AdjustmentType.convert(Int);
713
6.27k
  llvm::APSInt Max = AdjustmentType.getMaxValue();
714
6.27k
  if (ComparisonVal == Max)
715
22
    return RS();
716
6.25k
717
6.25k
  llvm::APSInt Min = AdjustmentType.getMinValue();
718
6.25k
  llvm::APSInt Lower = Min - Adjustment;
719
6.25k
  llvm::APSInt Upper = ComparisonVal - Adjustment;
720
6.25k
721
6.25k
  return RS().Intersect(getBasicVals(), F, Lower, Upper);
722
6.25k
}
723
724
RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
725
                                               SymbolRef Sym,
726
                                               const llvm::APSInt &Int,
727
5.87k
                                               const llvm::APSInt &Adjustment) {
728
5.87k
  return getSymLERange([&] 
{ return getRange(St, Sym); }5.87k
, Int, Adjustment);
729
5.87k
}
730
731
ProgramStateRef
732
RangeConstraintManager::assumeSymLE(ProgramStateRef St, SymbolRef Sym,
733
                                    const llvm::APSInt &Int,
734
5.87k
                                    const llvm::APSInt &Adjustment) {
735
5.87k
  RangeSet New = getSymLERange(St, Sym, Int, Adjustment);
736
5.87k
  return New.isEmpty() ? 
nullptr223
:
St->set<ConstraintRange>(Sym, New)5.65k
;
737
5.87k
}
738
739
ProgramStateRef RangeConstraintManager::assumeSymWithinInclusiveRange(
740
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
741
490
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
742
490
  RangeSet New = getSymGERange(State, Sym, From, Adjustment);
743
490
  if (New.isEmpty())
744
87
    return nullptr;
745
403
  RangeSet Out = getSymLERange([&] { return New; }, To, Adjustment);
746
403
  return Out.isEmpty() ? 
nullptr52
:
State->set<ConstraintRange>(Sym, Out)351
;
747
403
}
748
749
ProgramStateRef RangeConstraintManager::assumeSymOutsideInclusiveRange(
750
    ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
751
1.47k
    const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
752
1.47k
  RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
753
1.47k
  RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
754
1.47k
  RangeSet New(RangeLT.addRange(F, RangeGT));
755
1.47k
  return New.isEmpty() ? 
nullptr62
:
State->set<ConstraintRange>(Sym, New)1.40k
;
756
1.47k
}
757
758
//===----------------------------------------------------------------------===//
759
// Pretty-printing.
760
//===----------------------------------------------------------------------===//
761
762
void RangeConstraintManager::printJson(raw_ostream &Out, ProgramStateRef State,
763
                                       const char *NL, unsigned int Space,
764
107
                                       bool IsDot) const {
765
107
  ConstraintRangeTy Constraints = State->get<ConstraintRange>();
766
107
767
107
  Indent(Out, Space, IsDot) << "\"constraints\": ";
768
107
  if (Constraints.isEmpty()) {
769
77
    Out << "null," << NL;
770
77
    return;
771
77
  }
772
30
773
30
  ++Space;
774
30
  Out << '[' << NL;
775
30
  for (ConstraintRangeTy::iterator I = Constraints.begin();
776
66
       I != Constraints.end(); 
++I36
) {
777
36
    Indent(Out, Space, IsDot)
778
36
        << "{ \"symbol\": \"" << I.getKey() << "\", \"range\": \"";
779
36
    I.getData().print(Out);
780
36
    Out << "\" }";
781
36
782
36
    if (std::next(I) != Constraints.end())
783
6
      Out << ',';
784
36
    Out << NL;
785
36
  }
786
30
787
30
  --Space;
788
30
  Indent(Out, Space, IsDot) << "]," << NL;
789
30
}