Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp
Line
Count
Source (jump to first uncovered line)
1
// SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- C++ -*-
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
//  This file defines SimpleSValBuilder, a basic implementation of SValBuilder.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
15
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
16
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
18
19
using namespace clang;
20
using namespace ento;
21
22
namespace {
23
class SimpleSValBuilder : public SValBuilder {
24
protected:
25
  SVal dispatchCast(SVal val, QualType castTy) override;
26
  SVal evalCastFromNonLoc(NonLoc val, QualType castTy) override;
27
  SVal evalCastFromLoc(Loc val, QualType castTy) override;
28
29
public:
30
  SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
31
                    ProgramStateManager &stateMgr)
32
6.87k
                    : SValBuilder(alloc, context, stateMgr) {}
33
6.87k
  ~SimpleSValBuilder() override {}
34
35
  SVal evalMinus(NonLoc val) override;
36
  SVal evalComplement(NonLoc val) override;
37
  SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
38
                   NonLoc lhs, NonLoc rhs, QualType resultTy) override;
39
  SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
40
                   Loc lhs, Loc rhs, QualType resultTy) override;
41
  SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
42
                   Loc lhs, NonLoc rhs, QualType resultTy) override;
43
44
  /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
45
  ///  (integer) value, that value is returned. Otherwise, returns NULL.
46
  const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
47
48
  /// Recursively descends into symbolic expressions and replaces symbols
49
  /// with their known values (in the sense of the getKnownValue() method).
50
  SVal simplifySVal(ProgramStateRef State, SVal V) override;
51
52
  SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
53
                     const llvm::APSInt &RHS, QualType resultTy);
54
};
55
} // end anonymous namespace
56
57
SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
58
                                           ASTContext &context,
59
6.87k
                                           ProgramStateManager &stateMgr) {
60
6.87k
  return new SimpleSValBuilder(alloc, context, stateMgr);
61
6.87k
}
62
63
//===----------------------------------------------------------------------===//
64
// Transfer function for Casts.
65
//===----------------------------------------------------------------------===//
66
67
129k
SVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) {
68
129k
  assert(Val.getAs<Loc>() || Val.getAs<NonLoc>());
69
71.3k
  return Val.getAs<Loc>() ? evalCastFromLoc(Val.castAs<Loc>(), CastTy)
70
58.4k
                           : evalCastFromNonLoc(Val.castAs<NonLoc>(), CastTy);
71
129k
}
72
73
78.6k
SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) {
74
78.6k
  bool isLocType = Loc::isLocType(castTy);
75
78.6k
  if (val.getAs<nonloc::PointerToMember>())
76
29
    return val;
77
78.6k
78
78.6k
  
if (Optional<nonloc::LocAsInteger> 78.6k
LI78.6k
= val.getAs<nonloc::LocAsInteger>()) {
79
50
    if (isLocType)
80
12
      return LI->getLoc();
81
38
    // FIXME: Correctly support promotions/truncations.
82
38
    unsigned castSize = Context.getIntWidth(castTy);
83
38
    if (castSize == LI->getNumBits())
84
38
      return val;
85
0
    return makeLocAsInteger(LI->getLoc(), castSize);
86
0
  }
87
78.5k
88
78.5k
  
if (const SymExpr *78.5k
se78.5k
= val.getAsSymbolicExpression()) {
89
55.9k
    QualType T = Context.getCanonicalType(se->getType());
90
55.9k
    // If types are the same or both are integers, ignore the cast.
91
55.9k
    // FIXME: Remove this hack when we support symbolic truncation/extension.
92
55.9k
    // HACK: If both castTy and T are integers, ignore the cast.  This is
93
55.9k
    // not a permanent solution.  Eventually we want to precisely handle
94
55.9k
    // extension/truncation of symbolic integers.  This prevents us from losing
95
55.9k
    // precision when we assign 'x = y' and 'y' is symbolic and x and y are
96
55.9k
    // different integer types.
97
55.9k
   if (haveSameType(T, castTy))
98
55.9k
      return val;
99
16
100
16
    
if (16
!isLocType16
)
101
12
      return makeNonLoc(se, T, castTy);
102
4
    return UnknownVal();
103
4
  }
104
22.6k
105
22.6k
  // If value is a non-integer constant, produce unknown.
106
22.6k
  
if (22.6k
!val.getAs<nonloc::ConcreteInt>()22.6k
)
107
1
    return UnknownVal();
108
22.6k
109
22.6k
  // Handle casts to a boolean type.
110
22.6k
  
if (22.6k
castTy->isBooleanType()22.6k
) {
111
26
    bool b = val.castAs<nonloc::ConcreteInt>().getValue().getBoolValue();
112
26
    return makeTruthVal(b, castTy);
113
26
  }
114
22.6k
115
22.6k
  // Only handle casts from integers to integers - if val is an integer constant
116
22.6k
  // being cast to a non-integer type, produce unknown.
117
22.6k
  
if (22.6k
!isLocType && 22.6k
!castTy->isIntegralOrEnumerationType()20.0k
)
118
149
    return UnknownVal();
119
22.4k
120
22.4k
  llvm::APSInt i = val.castAs<nonloc::ConcreteInt>().getValue();
121
22.4k
  BasicVals.getAPSIntType(castTy).apply(i);
122
22.4k
123
22.4k
  if (isLocType)
124
2.57k
    return makeIntLocVal(i);
125
22.4k
  else
126
19.9k
    return makeIntVal(i);
127
0
}
128
129
331k
SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) {
130
331k
131
331k
  // Casts from pointers -> pointers, just return the lval.
132
331k
  //
133
331k
  // Casts from pointers -> references, just return the lval.  These
134
331k
  //   can be introduced by the frontend for corner cases, e.g
135
331k
  //   casting from va_list* to __builtin_va_list&.
136
331k
  //
137
331k
  if (
Loc::isLocType(castTy) || 331k
castTy->isReferenceType()260k
)
138
71.3k
    return val;
139
260k
140
260k
  // FIXME: Handle transparent unions where a value can be "transparently"
141
260k
  //  lifted into a union type.
142
260k
  
if (260k
castTy->isUnionType()260k
)
143
0
    return UnknownVal();
144
260k
145
260k
  // Casting a Loc to a bool will almost always be true,
146
260k
  // unless this is a weak function or a symbolic region.
147
260k
  
if (260k
castTy->isBooleanType()260k
) {
148
259k
    switch (val.getSubKind()) {
149
259k
      case loc::MemRegionValKind: {
150
259k
        const MemRegion *R = val.castAs<loc::MemRegionVal>().getRegion();
151
259k
        if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
152
55.5k
          
if (const FunctionDecl *55.5k
FD55.5k
= dyn_cast<FunctionDecl>(FTR->getDecl()))
153
55.5k
            
if (55.5k
FD->isWeak()55.5k
)
154
55.5k
              // FIXME: Currently we are using an extent symbol here,
155
55.5k
              // because there are no generic region address metadata
156
55.5k
              // symbols to use, only content metadata.
157
29
              return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR));
158
259k
159
259k
        
if (const SymbolicRegion *259k
SymR259k
= R->getSymbolicBase())
160
0
          return nonloc::SymbolVal(SymR->getSymbol());
161
259k
162
259k
        // FALL-THROUGH
163
259k
        
LLVM_FALLTHROUGH259k
;
164
259k
      }
165
259k
166
259k
      case loc::GotoLabelKind:
167
259k
        // Labels and non-symbolic memory regions are always true.
168
259k
        return makeTruthVal(true, castTy);
169
102
    }
170
102
  }
171
102
172
102
  
if (102
castTy->isIntegralOrEnumerationType()102
) {
173
100
    unsigned BitWidth = Context.getIntWidth(castTy);
174
100
175
100
    if (!val.getAs<loc::ConcreteInt>())
176
82
      return makeLocAsInteger(val, BitWidth);
177
18
178
18
    llvm::APSInt i = val.castAs<loc::ConcreteInt>().getValue();
179
18
    BasicVals.getAPSIntType(castTy).apply(i);
180
18
    return makeIntVal(i);
181
18
  }
182
2
183
2
  // All other cases: return 'UnknownVal'.  This includes casting pointers
184
2
  // to floats, which is probably badness it itself, but this is a good
185
2
  // intermediate solution until we do something better.
186
2
  return UnknownVal();
187
2
}
188
189
//===----------------------------------------------------------------------===//
190
// Transfer function for unary operators.
191
//===----------------------------------------------------------------------===//
192
193
817
SVal SimpleSValBuilder::evalMinus(NonLoc val) {
194
817
  switch (val.getSubKind()) {
195
809
  case nonloc::ConcreteIntKind:
196
809
    return val.castAs<nonloc::ConcreteInt>().evalMinus(*this);
197
8
  default:
198
8
    return UnknownVal();
199
0
  }
200
0
}
201
202
123
SVal SimpleSValBuilder::evalComplement(NonLoc X) {
203
123
  switch (X.getSubKind()) {
204
115
  case nonloc::ConcreteIntKind:
205
115
    return X.castAs<nonloc::ConcreteInt>().evalComplement(*this);
206
8
  default:
207
8
    return UnknownVal();
208
0
  }
209
0
}
210
211
//===----------------------------------------------------------------------===//
212
// Transfer function for binary operators.
213
//===----------------------------------------------------------------------===//
214
215
SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
216
                                    BinaryOperator::Opcode op,
217
                                    const llvm::APSInt &RHS,
218
25.5k
                                    QualType resultTy) {
219
25.5k
  bool isIdempotent = false;
220
25.5k
221
25.5k
  // Check for a few special cases with known reductions first.
222
25.5k
  switch (op) {
223
7.41k
  default:
224
7.41k
    // We can't reduce this case; just treat it normally.
225
7.41k
    break;
226
294
  case BO_Mul:
227
294
    // a*0 and a*1
228
294
    if (RHS == 0)
229
133
      return makeIntVal(0, resultTy);
230
161
    else 
if (161
RHS == 1161
)
231
10
      isIdempotent = true;
232
161
    break;
233
30
  case BO_Div:
234
30
    // a/0 and a/1
235
30
    if (RHS == 0)
236
30
      // This is also handled elsewhere.
237
0
      return UndefinedVal();
238
30
    else 
if (30
RHS == 130
)
239
4
      isIdempotent = true;
240
30
    break;
241
33
  case BO_Rem:
242
33
    // a%0 and a%1
243
33
    if (RHS == 0)
244
33
      // This is also handled elsewhere.
245
0
      return UndefinedVal();
246
33
    else 
if (33
RHS == 133
)
247
0
      return makeIntVal(0, resultTy);
248
33
    break;
249
2.13k
  case BO_Add:
250
2.13k
  case BO_Sub:
251
2.13k
  case BO_Shl:
252
2.13k
  case BO_Shr:
253
2.13k
  case BO_Xor:
254
2.13k
    // a+0, a-0, a<<0, a>>0, a^0
255
2.13k
    if (RHS == 0)
256
93
      isIdempotent = true;
257
2.13k
    break;
258
15.6k
  case BO_And:
259
15.6k
    // a&0 and a&(~0)
260
15.6k
    if (RHS == 0)
261
3
      return makeIntVal(0, resultTy);
262
15.6k
    else 
if (15.6k
RHS.isAllOnesValue()15.6k
)
263
1
      isIdempotent = true;
264
15.6k
    break;
265
7
  case BO_Or:
266
7
    // a|0 and a|(~0)
267
7
    if (RHS == 0)
268
3
      isIdempotent = true;
269
4
    else 
if (4
RHS.isAllOnesValue()4
) {
270
1
      const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS);
271
1
      return nonloc::ConcreteInt(Result);
272
1
    }
273
6
    break;
274
25.3k
  }
275
25.3k
276
25.3k
  // Idempotent ops (like a*1) can still change the type of an expression.
277
25.3k
  // Wrap the LHS up in a NonLoc again and let evalCastFromNonLoc do the
278
25.3k
  // dirty work.
279
25.3k
  
if (25.3k
isIdempotent25.3k
)
280
111
      return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy);
281
25.2k
282
25.2k
  // If we reach this point, the expression cannot be simplified.
283
25.2k
  // Make a SymbolVal for the entire expression, after converting the RHS.
284
25.2k
  const llvm::APSInt *ConvertedRHS = &RHS;
285
25.2k
  if (
BinaryOperator::isComparisonOp(op)25.2k
) {
286
7.41k
    // We're looking for a type big enough to compare the symbolic value
287
7.41k
    // with the given constant.
288
7.41k
    // FIXME: This is an approximation of Sema::UsualArithmeticConversions.
289
7.41k
    ASTContext &Ctx = getContext();
290
7.41k
    QualType SymbolType = LHS->getType();
291
7.41k
    uint64_t ValWidth = RHS.getBitWidth();
292
7.41k
    uint64_t TypeWidth = Ctx.getTypeSize(SymbolType);
293
7.41k
294
7.41k
    if (
ValWidth < TypeWidth7.41k
) {
295
742
      // If the value is too small, extend it.
296
742
      ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
297
7.41k
    } else 
if (6.67k
ValWidth == TypeWidth6.67k
) {
298
6.04k
      // If the value is signed but the symbol is unsigned, do the comparison
299
6.04k
      // in unsigned space. [C99 6.3.1.8]
300
6.04k
      // (For the opposite case, the value is already unsigned.)
301
6.04k
      if (
RHS.isSigned() && 6.04k
!SymbolType->isSignedIntegerOrEnumerationType()2.80k
)
302
218
        ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
303
6.67k
    }
304
7.41k
  } else
305
17.8k
    ConvertedRHS = &BasicVals.Convert(resultTy, RHS);
306
25.5k
307
25.5k
  return makeNonLoc(LHS, op, *ConvertedRHS, resultTy);
308
25.5k
}
309
310
SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
311
                                  BinaryOperator::Opcode op,
312
                                  NonLoc lhs, NonLoc rhs,
313
53.3k
                                  QualType resultTy)  {
314
53.3k
  NonLoc InputLHS = lhs;
315
53.3k
  NonLoc InputRHS = rhs;
316
53.3k
317
53.3k
  // Handle trivial case where left-side and right-side are the same.
318
53.3k
  if (lhs == rhs)
319
3.45k
    switch (op) {
320
635
      default:
321
635
        break;
322
1.56k
      case BO_EQ:
323
1.56k
      case BO_LE:
324
1.56k
      case BO_GE:
325
1.56k
        return makeTruthVal(true, resultTy);
326
917
      case BO_LT:
327
917
      case BO_GT:
328
917
      case BO_NE:
329
917
        return makeTruthVal(false, resultTy);
330
53
      case BO_Xor:
331
53
      case BO_Sub:
332
53
        if (resultTy->isIntegralOrEnumerationType())
333
53
          return makeIntVal(0, resultTy);
334
0
        return evalCastFromNonLoc(makeIntVal(0, /*Unsigned=*/false), resultTy);
335
287
      case BO_Or:
336
287
      case BO_And:
337
287
        return evalCastFromNonLoc(lhs, resultTy);
338
50.5k
    }
339
50.5k
340
52.2k
  
while (50.5k
152.2k
) {
341
52.2k
    switch (lhs.getSubKind()) {
342
0
    default:
343
0
      return makeSymExprValNN(state, op, lhs, rhs, resultTy);
344
2
    case nonloc::PointerToMemberKind: {
345
2
      assert(rhs.getSubKind() == nonloc::PointerToMemberKind &&
346
2
             "Both SVals should have pointer-to-member-type");
347
2
      auto LPTM = lhs.castAs<nonloc::PointerToMember>(),
348
2
           RPTM = rhs.castAs<nonloc::PointerToMember>();
349
2
      auto LPTMD = LPTM.getPTMData(), RPTMD = RPTM.getPTMData();
350
2
      switch (op) {
351
2
        case BO_EQ:
352
2
          return makeTruthVal(LPTMD == RPTMD, resultTy);
353
0
        case BO_NE:
354
0
          return makeTruthVal(LPTMD != RPTMD, resultTy);
355
0
        default:
356
0
          return UnknownVal();
357
0
      }
358
0
    }
359
16
    case nonloc::LocAsIntegerKind: {
360
16
      Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
361
16
      switch (rhs.getSubKind()) {
362
0
        case nonloc::LocAsIntegerKind:
363
0
          // FIXME: at the moment the implementation
364
0
          // of modeling "pointers as integers" is not complete.
365
0
          if (!BinaryOperator::isComparisonOp(op))
366
0
            return UnknownVal();
367
0
          return evalBinOpLL(state, op, lhsL,
368
0
                             rhs.castAs<nonloc::LocAsInteger>().getLoc(),
369
0
                             resultTy);
370
16
        case nonloc::ConcreteIntKind: {
371
16
          // FIXME: at the moment the implementation
372
16
          // of modeling "pointers as integers" is not complete.
373
16
          if (!BinaryOperator::isComparisonOp(op))
374
6
            return UnknownVal();
375
10
          // Transform the integer into a location and compare.
376
10
          // FIXME: This only makes sense for comparisons. If we want to, say,
377
10
          // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it,
378
10
          // then pack it back into a LocAsInteger.
379
10
          llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
380
10
          BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
381
10
          return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
382
10
        }
383
0
        default:
384
0
          switch (op) {
385
0
            case BO_EQ:
386
0
              return makeTruthVal(false, resultTy);
387
0
            case BO_NE:
388
0
              return makeTruthVal(true, resultTy);
389
0
            default:
390
0
              // This case also handles pointer arithmetic.
391
0
              return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
392
0
          }
393
0
      }
394
0
    }
395
18.1k
    case nonloc::ConcreteIntKind: {
396
18.1k
      llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue();
397
18.1k
398
18.1k
      // If we're dealing with two known constants, just perform the operation.
399
18.1k
      if (const llvm::APSInt *
KnownRHSValue18.1k
= getKnownValue(state, rhs)) {
400
17.1k
        llvm::APSInt RHSValue = *KnownRHSValue;
401
17.1k
        if (
BinaryOperator::isComparisonOp(op)17.1k
) {
402
7.52k
          // We're looking for a type big enough to compare the two values.
403
7.52k
          // FIXME: This is not correct. char + short will result in a promotion
404
7.52k
          // to int. Unfortunately we have lost types by this point.
405
7.52k
          APSIntType CompareType = std::max(APSIntType(LHSValue),
406
7.52k
                                            APSIntType(RHSValue));
407
7.52k
          CompareType.apply(LHSValue);
408
7.52k
          CompareType.apply(RHSValue);
409
17.1k
        } else 
if (9.65k
!BinaryOperator::isShiftOp(op)9.65k
) {
410
9.29k
          APSIntType IntType = BasicVals.getAPSIntType(resultTy);
411
9.29k
          IntType.apply(LHSValue);
412
9.29k
          IntType.apply(RHSValue);
413
9.29k
        }
414
17.1k
415
17.1k
        const llvm::APSInt *Result =
416
17.1k
          BasicVals.evalAPSInt(op, LHSValue, RHSValue);
417
17.1k
        if (!Result)
418
3
          return UndefinedVal();
419
17.1k
420
17.1k
        return nonloc::ConcreteInt(*Result);
421
17.1k
      }
422
922
423
922
      // Swap the left and right sides and flip the operator if doing so
424
922
      // allows us to better reason about the expression (this is a form
425
922
      // of expression canonicalization).
426
922
      // While we're at it, catch some special cases for non-commutative ops.
427
922
      switch (op) {
428
430
      case BO_LT:
429
430
      case BO_GT:
430
430
      case BO_LE:
431
430
      case BO_GE:
432
430
        op = BinaryOperator::reverseComparisonOp(op);
433
430
        // FALL-THROUGH
434
806
      case BO_EQ:
435
806
      case BO_NE:
436
806
      case BO_Add:
437
806
      case BO_Mul:
438
806
      case BO_And:
439
806
      case BO_Xor:
440
806
      case BO_Or:
441
806
        std::swap(lhs, rhs);
442
806
        continue;
443
3
      case BO_Shr:
444
3
        // (~0)>>a
445
3
        if (
LHSValue.isAllOnesValue() && 3
LHSValue.isSigned()2
)
446
1
          return evalCastFromNonLoc(lhs, resultTy);
447
2
        // FALL-THROUGH
448
5
      case BO_Shl:
449
5
        // 0<<a and 0>>a
450
3
        if (LHSValue == 0)
451
2
          return evalCastFromNonLoc(lhs, resultTy);
452
1
        return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
453
112
      default:
454
112
        return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
455
0
      }
456
0
    }
457
34.1k
    case nonloc::SymbolValKind: {
458
34.1k
      // We only handle LHS as simple symbols or SymIntExprs.
459
34.1k
      SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol();
460
34.1k
461
34.1k
      // LHS is a symbolic expression.
462
34.1k
      if (const SymIntExpr *
symIntExpr34.1k
= dyn_cast<SymIntExpr>(Sym)) {
463
2.12k
464
2.12k
        // Is this a logical not? (!x is represented as x == 0.)
465
2.12k
        if (
op == BO_EQ && 2.12k
rhs.isZeroConstant()251
) {
466
182
          // We know how to negate certain expressions. Simplify them here.
467
182
468
182
          BinaryOperator::Opcode opc = symIntExpr->getOpcode();
469
182
          switch (opc) {
470
80
          default:
471
80
            // We don't know how to negate this operation.
472
80
            // Just handle it as if it were a normal comparison to 0.
473
80
            break;
474
0
          case BO_LAnd:
475
0
          case BO_LOr:
476
0
            llvm_unreachable("Logical operators handled by branching logic.");
477
0
          case BO_Assign:
478
0
          case BO_MulAssign:
479
0
          case BO_DivAssign:
480
0
          case BO_RemAssign:
481
0
          case BO_AddAssign:
482
0
          case BO_SubAssign:
483
0
          case BO_ShlAssign:
484
0
          case BO_ShrAssign:
485
0
          case BO_AndAssign:
486
0
          case BO_XorAssign:
487
0
          case BO_OrAssign:
488
0
          case BO_Comma:
489
0
            llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
490
0
          case BO_PtrMemD:
491
0
          case BO_PtrMemI:
492
0
            llvm_unreachable("Pointer arithmetic not handled here.");
493
102
          case BO_LT:
494
102
          case BO_GT:
495
102
          case BO_LE:
496
102
          case BO_GE:
497
102
          case BO_EQ:
498
102
          case BO_NE:
499
102
            assert(resultTy->isBooleanType() ||
500
102
                   resultTy == getConditionType());
501
102
            assert(symIntExpr->getType()->isBooleanType() ||
502
102
                   getContext().hasSameUnqualifiedType(symIntExpr->getType(),
503
102
                                                       getConditionType()));
504
102
            // Negate the comparison and make a value.
505
102
            opc = BinaryOperator::negateComparisonOp(opc);
506
102
            return makeNonLoc(symIntExpr->getLHS(), opc,
507
102
                symIntExpr->getRHS(), resultTy);
508
2.02k
          }
509
2.02k
        }
510
2.02k
511
2.02k
        // For now, only handle expressions whose RHS is a constant.
512
2.02k
        
if (const llvm::APSInt *2.02k
RHSValue2.02k
= getKnownValue(state, rhs)) {
513
1.56k
          // If both the LHS and the current expression are additive,
514
1.56k
          // fold their constants and try again.
515
1.56k
          if (
BinaryOperator::isAdditiveOp(op)1.56k
) {
516
671
            BinaryOperator::Opcode lop = symIntExpr->getOpcode();
517
671
            if (
BinaryOperator::isAdditiveOp(lop)671
) {
518
651
              // Convert the two constants to a common type, then combine them.
519
651
520
651
              // resultTy may not be the best type to convert to, but it's
521
651
              // probably the best choice in expressions with mixed type
522
651
              // (such as x+1U+2LL). The rules for implicit conversions should
523
651
              // choose a reasonable type to preserve the expression, and will
524
651
              // at least match how the value is going to be used.
525
651
              APSIntType IntType = BasicVals.getAPSIntType(resultTy);
526
651
              const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
527
651
              const llvm::APSInt &second = IntType.convert(*RHSValue);
528
651
529
651
              const llvm::APSInt *newRHS;
530
651
              if (lop == op)
531
407
                newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
532
651
              else
533
244
                newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
534
651
535
651
              assert(newRHS && "Invalid operation despite common type!");
536
651
              rhs = nonloc::ConcreteInt(*newRHS);
537
651
              lhs = nonloc::SymbolVal(symIntExpr->getLHS());
538
651
              op = lop;
539
651
              continue;
540
651
            }
541
915
          }
542
915
543
915
          // Otherwise, make a SymIntExpr out of the expression.
544
915
          return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
545
915
        }
546
2.12k
      }
547
32.4k
548
32.4k
      // Does the symbolic expression simplify to a constant?
549
32.4k
      // If so, "fold" the constant by setting 'lhs' to a ConcreteInt
550
32.4k
      // and try again.
551
32.4k
      SVal simplifiedLhs = simplifySVal(state, lhs);
552
32.4k
      if (simplifiedLhs != lhs)
553
255
        
if (auto 255
simplifiedLhsAsNonLoc255
= simplifiedLhs.getAs<NonLoc>()) {
554
254
          lhs = *simplifiedLhsAsNonLoc;
555
254
          continue;
556
254
        }
557
32.2k
558
32.2k
      // Is the RHS a constant?
559
32.2k
      
if (const llvm::APSInt *32.2k
RHSValue32.2k
= getKnownValue(state, rhs))
560
23.3k
        return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
561
8.88k
562
8.88k
      // Give up -- this is not a symbolic expression we can handle.
563
8.88k
      return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
564
8.88k
    }
565
52.2k
    }
566
52.2k
  }
567
53.3k
}
568
569
static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR,
570
                                            const FieldRegion *RightFR,
571
                                            BinaryOperator::Opcode op,
572
                                            QualType resultTy,
573
12
                                            SimpleSValBuilder &SVB) {
574
12
  // Only comparisons are meaningful here!
575
12
  if (!BinaryOperator::isComparisonOp(op))
576
0
    return UnknownVal();
577
12
578
12
  // Next, see if the two FRs have the same super-region.
579
12
  // FIXME: This doesn't handle casts yet, and simply stripping the casts
580
12
  // doesn't help.
581
12
  
if (12
LeftFR->getSuperRegion() != RightFR->getSuperRegion()12
)
582
2
    return UnknownVal();
583
10
584
10
  const FieldDecl *LeftFD = LeftFR->getDecl();
585
10
  const FieldDecl *RightFD = RightFR->getDecl();
586
10
  const RecordDecl *RD = LeftFD->getParent();
587
10
588
10
  // Make sure the two FRs are from the same kind of record. Just in case!
589
10
  // FIXME: This is probably where inheritance would be a problem.
590
10
  if (RD != RightFD->getParent())
591
0
    return UnknownVal();
592
10
593
10
  // We know for sure that the two fields are not the same, since that
594
10
  // would have given us the same SVal.
595
10
  
if (10
op == BO_EQ10
)
596
2
    return SVB.makeTruthVal(false, resultTy);
597
8
  
if (8
op == BO_NE8
)
598
2
    return SVB.makeTruthVal(true, resultTy);
599
6
600
6
  // Iterate through the fields and see which one comes first.
601
6
  // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
602
6
  // members and the units in which bit-fields reside have addresses that
603
6
  // increase in the order in which they are declared."
604
6
  
bool leftFirst = (op == BO_LT || 6
op == BO_LE2
);
605
6
  for (const auto *I : RD->fields()) {
606
6
    if (I == LeftFD)
607
6
      return SVB.makeTruthVal(leftFirst, resultTy);
608
0
    
if (0
I == RightFD0
)
609
0
      return SVB.makeTruthVal(!leftFirst, resultTy);
610
0
  }
611
0
612
0
  
llvm_unreachable0
("Fields not found in parent record's definition");
613
0
}
614
615
// FIXME: all this logic will change if/when we have MemRegion::getLocation().
616
SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
617
                                  BinaryOperator::Opcode op,
618
                                  Loc lhs, Loc rhs,
619
5.14k
                                  QualType resultTy) {
620
5.14k
  // Only comparisons and subtractions are valid operations on two pointers.
621
5.14k
  // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
622
5.14k
  // However, if a pointer is casted to an integer, evalBinOpNN may end up
623
5.14k
  // calling this function with another operation (PR7527). We don't attempt to
624
5.14k
  // model this for now, but it could be useful, particularly when the
625
5.14k
  // "location" is actually an integer value that's been passed through a void*.
626
5.14k
  if (
!(BinaryOperator::isComparisonOp(op) || 5.14k
op == BO_Sub102
))
627
0
    return UnknownVal();
628
5.14k
629
5.14k
  // Special cases for when both sides are identical.
630
5.14k
  
if (5.14k
lhs == rhs5.14k
) {
631
461
    switch (op) {
632
0
    default:
633
0
      llvm_unreachable("Unimplemented operation for two identical values");
634
1
    case BO_Sub:
635
1
      return makeZeroVal(resultTy);
636
384
    case BO_EQ:
637
384
    case BO_LE:
638
384
    case BO_GE:
639
384
      return makeTruthVal(true, resultTy);
640
76
    case BO_NE:
641
76
    case BO_LT:
642
76
    case BO_GT:
643
76
      return makeTruthVal(false, resultTy);
644
4.68k
    }
645
4.68k
  }
646
4.68k
647
4.68k
  switch (lhs.getSubKind()) {
648
0
  default:
649
0
    llvm_unreachable("Ordering not implemented for this Loc.");
650
4.68k
651
18
  case loc::GotoLabelKind:
652
18
    // The only thing we know about labels is that they're non-null.
653
18
    if (
rhs.isZeroConstant()18
) {
654
16
      switch (op) {
655
0
      default:
656
0
        break;
657
0
      case BO_Sub:
658
0
        return evalCastFromLoc(lhs, resultTy);
659
8
      case BO_EQ:
660
8
      case BO_LE:
661
8
      case BO_LT:
662
8
        return makeTruthVal(false, resultTy);
663
8
      case BO_NE:
664
8
      case BO_GT:
665
8
      case BO_GE:
666
8
        return makeTruthVal(true, resultTy);
667
2
      }
668
2
    }
669
2
    // There may be two labels for the same location, and a function region may
670
2
    // have the same address as a label at the start of the function (depending
671
2
    // on the ABI).
672
2
    // FIXME: we can probably do a comparison against other MemRegions, though.
673
2
    // FIXME: is there a way to tell if two labels refer to the same location?
674
2
    return UnknownVal();
675
2
676
230
  case loc::ConcreteIntKind: {
677
230
    // If one of the operands is a symbol and the other is a constant,
678
230
    // build an expression for use by the constraint manager.
679
230
    if (SymbolRef 
rSym230
= rhs.getAsLocSymbol()) {
680
206
      // We can only build expressions with symbols on the left,
681
206
      // so we need a reversible operator.
682
206
      if (!BinaryOperator::isComparisonOp(op))
683
0
        return UnknownVal();
684
206
685
206
      const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
686
206
      op = BinaryOperator::reverseComparisonOp(op);
687
206
      return makeNonLoc(rSym, op, lVal, resultTy);
688
206
    }
689
24
690
24
    // If both operands are constants, just perform the operation.
691
24
    
if (Optional<loc::ConcreteInt> 24
rInt24
= rhs.getAs<loc::ConcreteInt>()) {
692
13
      SVal ResultVal =
693
13
          lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
694
13
      if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
695
13
        return evalCastFromNonLoc(*Result, resultTy);
696
0
697
0
      assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
698
0
      return UnknownVal();
699
0
    }
700
11
701
11
    // Special case comparisons against NULL.
702
11
    // This must come after the test if the RHS is a symbol, which is used to
703
11
    // build constraints. The address of any non-symbolic region is guaranteed
704
11
    // to be non-NULL, as is any label.
705
24
    assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
706
11
    if (
lhs.isZeroConstant()11
) {
707
7
      switch (op) {
708
0
      default:
709
0
        break;
710
0
      case BO_EQ:
711
0
      case BO_GT:
712
0
      case BO_GE:
713
0
        return makeTruthVal(false, resultTy);
714
7
      case BO_NE:
715
7
      case BO_LT:
716
7
      case BO_LE:
717
7
        return makeTruthVal(true, resultTy);
718
4
      }
719
4
    }
720
4
721
4
    // Comparing an arbitrary integer to a region or label address is
722
4
    // completely unknowable.
723
4
    return UnknownVal();
724
4
  }
725
4.43k
  case loc::MemRegionValKind: {
726
4.43k
    if (Optional<loc::ConcreteInt> 
rInt4.43k
= rhs.getAs<loc::ConcreteInt>()) {
727
3.04k
      // If one of the operands is a symbol and the other is a constant,
728
3.04k
      // build an expression for use by the constraint manager.
729
3.04k
      if (SymbolRef 
lSym3.04k
= lhs.getAsLocSymbol(true)) {
730
1.27k
        if (BinaryOperator::isComparisonOp(op))
731
1.27k
          return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
732
2
        return UnknownVal();
733
2
      }
734
1.76k
      // Special case comparisons to NULL.
735
1.76k
      // This must come after the test if the LHS is a symbol, which is used to
736
1.76k
      // build constraints. The address of any non-symbolic region is guaranteed
737
1.76k
      // to be non-NULL.
738
1.76k
      
if (1.76k
rInt->isZeroConstant()1.76k
) {
739
1.76k
        if (op == BO_Sub)
740
0
          return evalCastFromLoc(lhs, resultTy);
741
1.76k
742
1.76k
        
if (1.76k
BinaryOperator::isComparisonOp(op)1.76k
) {
743
1.76k
          QualType boolType = getContext().BoolTy;
744
1.76k
          NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>();
745
1.76k
          NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>();
746
1.76k
          return evalBinOpNN(state, op, l, r, resultTy);
747
1.76k
        }
748
2
      }
749
2
750
2
      // Comparing a region to an arbitrary integer is completely unknowable.
751
2
      return UnknownVal();
752
2
    }
753
1.39k
754
1.39k
    // Get both values as regions, if possible.
755
1.39k
    const MemRegion *LeftMR = lhs.getAsRegion();
756
1.39k
    assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");
757
1.39k
758
1.39k
    const MemRegion *RightMR = rhs.getAsRegion();
759
1.39k
    if (!RightMR)
760
1.39k
      // The RHS is probably a label, which in theory could address a region.
761
1.39k
      // FIXME: we can probably make a more useful statement about non-code
762
1.39k
      // regions, though.
763
0
      return UnknownVal();
764
1.39k
765
1.39k
    const MemRegion *LeftBase = LeftMR->getBaseRegion();
766
1.39k
    const MemRegion *RightBase = RightMR->getBaseRegion();
767
1.39k
    const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
768
1.39k
    const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
769
1.39k
    const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
770
1.39k
771
1.39k
    // If the two regions are from different known memory spaces they cannot be
772
1.39k
    // equal. Also, assume that no symbolic region (whose memory space is
773
1.39k
    // unknown) is on the stack.
774
1.39k
    if (LeftMS != RightMS &&
775
161
        
((LeftMS != UnknownMS && 161
RightMS != UnknownMS149
) ||
776
1.39k
         
(isa<StackSpaceRegion>(LeftMS) || 158
isa<StackSpaceRegion>(RightMS)13
))) {
777
148
      switch (op) {
778
8
      default:
779
8
        return UnknownVal();
780
10
      case BO_EQ:
781
10
        return makeTruthVal(false, resultTy);
782
130
      case BO_NE:
783
130
        return makeTruthVal(true, resultTy);
784
1.24k
      }
785
1.24k
    }
786
1.24k
787
1.24k
    // If both values wrap regions, see if they're from different base regions.
788
1.24k
    // Note, heap base symbolic regions are assumed to not alias with
789
1.24k
    // each other; for example, we assume that malloc returns different address
790
1.24k
    // on each invocation.
791
1.24k
    // FIXME: ObjC object pointers always reside on the heap, but currently
792
1.24k
    // we treat their memory space as unknown, because symbolic pointers
793
1.24k
    // to ObjC objects may alias. There should be a way to construct
794
1.24k
    // possibly-aliasing heap-based regions. For instance, MacOSXApiChecker
795
1.24k
    // guesses memory space for ObjC object pointers manually instead of
796
1.24k
    // relying on us.
797
1.24k
    
if (1.24k
LeftBase != RightBase &&
798
733
        
((!isa<SymbolicRegion>(LeftBase) && 733
!isa<SymbolicRegion>(RightBase)408
) ||
799
1.24k
         
(isa<HeapSpaceRegion>(LeftMS) || 325
isa<HeapSpaceRegion>(RightMS)323
)) ){
800
414
      switch (op) {
801
50
      default:
802
50
        return UnknownVal();
803
357
      case BO_EQ:
804
357
        return makeTruthVal(false, resultTy);
805
7
      case BO_NE:
806
7
        return makeTruthVal(true, resultTy);
807
831
      }
808
831
    }
809
831
810
831
    // Handle special cases for when both regions are element regions.
811
831
    const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
812
831
    const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR);
813
831
    if (
RightER && 831
LeftER506
) {
814
493
      // Next, see if the two ERs have the same super-region and matching types.
815
493
      // FIXME: This should do something useful even if the types don't match,
816
493
      // though if both indexes are constant the RegionRawOffset path will
817
493
      // give the correct answer.
818
493
      if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
819
493
          
LeftER->getElementType() == RightER->getElementType()493
) {
820
461
        // Get the left index and cast it to the correct type.
821
461
        // If the index is unknown or undefined, bail out here.
822
461
        SVal LeftIndexVal = LeftER->getIndex();
823
461
        Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
824
461
        if (!LeftIndex)
825
0
          return UnknownVal();
826
461
        LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy);
827
461
        LeftIndex = LeftIndexVal.getAs<NonLoc>();
828
461
        if (!LeftIndex)
829
0
          return UnknownVal();
830
461
831
461
        // Do the same for the right index.
832
461
        SVal RightIndexVal = RightER->getIndex();
833
461
        Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
834
461
        if (!RightIndex)
835
0
          return UnknownVal();
836
461
        RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy);
837
461
        RightIndex = RightIndexVal.getAs<NonLoc>();
838
461
        if (!RightIndex)
839
0
          return UnknownVal();
840
461
841
461
        // Actually perform the operation.
842
461
        // evalBinOpNN expects the two indexes to already be the right type.
843
461
        return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
844
461
      }
845
493
    }
846
370
847
370
    // Special handling of the FieldRegions, even with symbolic offsets.
848
370
    const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
849
370
    const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR);
850
370
    if (
RightFR && 370
LeftFR12
) {
851
12
      SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
852
12
                                               *this);
853
12
      if (!R.isUnknown())
854
10
        return R;
855
360
    }
856
360
857
360
    // Compare the regions using the raw offsets.
858
360
    RegionOffset LeftOffset = LeftMR->getAsOffset();
859
360
    RegionOffset RightOffset = RightMR->getAsOffset();
860
360
861
360
    if (LeftOffset.getRegion() != nullptr &&
862
360
        LeftOffset.getRegion() == RightOffset.getRegion() &&
863
360
        
!LeftOffset.hasSymbolicOffset()41
&&
!RightOffset.hasSymbolicOffset()39
) {
864
39
      int64_t left = LeftOffset.getOffset();
865
39
      int64_t right = RightOffset.getOffset();
866
39
867
39
      switch (op) {
868
0
        default:
869
0
          return UnknownVal();
870
0
        case BO_LT:
871
0
          return makeTruthVal(left < right, resultTy);
872
32
        case BO_GT:
873
32
          return makeTruthVal(left > right, resultTy);
874
0
        case BO_LE:
875
0
          return makeTruthVal(left <= right, resultTy);
876
0
        case BO_GE:
877
0
          return makeTruthVal(left >= right, resultTy);
878
5
        case BO_EQ:
879
5
          return makeTruthVal(left == right, resultTy);
880
2
        case BO_NE:
881
2
          return makeTruthVal(left != right, resultTy);
882
321
      }
883
321
    }
884
321
885
321
    // At this point we're not going to get a good answer, but we can try
886
321
    // conjuring an expression instead.
887
321
    SymbolRef LHSSym = lhs.getAsLocSymbol();
888
321
    SymbolRef RHSSym = rhs.getAsLocSymbol();
889
321
    if (
LHSSym && 321
RHSSym305
)
890
297
      return makeNonLoc(LHSSym, op, RHSSym, resultTy);
891
24
892
24
    // If we get here, we have no way of comparing the regions.
893
24
    return UnknownVal();
894
24
  }
895
5.14k
  }
896
5.14k
}
897
898
SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
899
                                  BinaryOperator::Opcode op,
900
17.3k
                                  Loc lhs, NonLoc rhs, QualType resultTy) {
901
17.3k
  if (
op >= BO_PtrMemD && 17.3k
op <= BO_PtrMemI17.3k
) {
902
21
    if (auto 
PTMSV21
= rhs.getAs<nonloc::PointerToMember>()) {
903
21
      if (PTMSV->isNullMemberPointer())
904
1
        return UndefinedVal();
905
20
      
if (const FieldDecl *20
FD20
= PTMSV->getDeclAs<FieldDecl>()) {
906
9
        SVal Result = lhs;
907
9
908
9
        for (const auto &I : *PTMSV)
909
21
          Result = StateMgr.getStoreManager().evalDerivedToBase(
910
21
              Result, I->getType(),I->isVirtual());
911
9
        return state->getLValue(FD, Result);
912
9
      }
913
11
    }
914
11
915
11
    return rhs;
916
11
  }
917
17.2k
918
17.3k
  assert(!BinaryOperator::isComparisonOp(op) &&
919
17.2k
         "arguments to comparison ops must be of the same type");
920
17.2k
921
17.2k
  // Special case: rhs is a zero constant.
922
17.2k
  if (rhs.isZeroConstant())
923
284
    return lhs;
924
17.0k
925
17.0k
  // We are dealing with pointer arithmetic.
926
17.0k
927
17.0k
  // Handle pointer arithmetic on constant values.
928
17.0k
  
if (Optional<nonloc::ConcreteInt> 17.0k
rhsInt17.0k
= rhs.getAs<nonloc::ConcreteInt>()) {
929
1.55k
    if (Optional<loc::ConcreteInt> 
lhsInt1.55k
= lhs.getAs<loc::ConcreteInt>()) {
930
6
      const llvm::APSInt &leftI = lhsInt->getValue();
931
6
      assert(leftI.isUnsigned());
932
6
      llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
933
6
934
6
      // Convert the bitwidth of rightI.  This should deal with overflow
935
6
      // since we are dealing with concrete values.
936
6
      rightI = rightI.extOrTrunc(leftI.getBitWidth());
937
6
938
6
      // Offset the increment by the pointer size.
939
6
      llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
940
6
      rightI *= Multiplicand;
941
6
942
6
      // Compute the adjusted pointer.
943
6
      switch (op) {
944
5
        case BO_Add:
945
5
          rightI = leftI + rightI;
946
5
          break;
947
1
        case BO_Sub:
948
1
          rightI = leftI - rightI;
949
1
          break;
950
0
        default:
951
0
          llvm_unreachable("Invalid pointer arithmetic operation");
952
6
      }
953
6
      return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
954
6
    }
955
1.55k
  }
956
17.0k
957
17.0k
  // Handle cases where 'lhs' is a region.
958
17.0k
  
if (const MemRegion *17.0k
region17.0k
= lhs.getAsRegion()) {
959
17.0k
    rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
960
17.0k
    SVal index = UnknownVal();
961
17.0k
    const SubRegion *superR = nullptr;
962
17.0k
    // We need to know the type of the pointer in order to add an integer to it.
963
17.0k
    // Depending on the type, different amount of bytes is added.
964
17.0k
    QualType elementType;
965
17.0k
966
17.0k
    if (const ElementRegion *
elemReg17.0k
= dyn_cast<ElementRegion>(region)) {
967
9.07k
      assert(op == BO_Add || op == BO_Sub);
968
9.07k
      index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
969
9.07k
                          getArrayIndexType());
970
9.07k
      superR = cast<SubRegion>(elemReg->getSuperRegion());
971
9.07k
      elementType = elemReg->getElementType();
972
9.07k
    }
973
7.92k
    else 
if (7.92k
isa<SubRegion>(region)7.92k
) {
974
7.92k
      assert(op == BO_Add || op == BO_Sub);
975
7.92k
      index = (op == BO_Add) ? 
rhs7.91k
:
evalMinus(rhs)13
;
976
7.92k
      superR = cast<SubRegion>(region);
977
7.92k
      // TODO: Is this actually reliable? Maybe improving our MemRegion
978
7.92k
      // hierarchy to provide typed regions for all non-void pointers would be
979
7.92k
      // better. For instance, we cannot extend this towards LocAsInteger
980
7.92k
      // operations, where result type of the expression is integer.
981
7.92k
      if (resultTy->isAnyPointerType())
982
7.92k
        elementType = resultTy->getPointeeType();
983
7.92k
    }
984
17.0k
985
17.0k
    if (Optional<NonLoc> 
indexV17.0k
= index.getAs<NonLoc>()) {
986
9.35k
      return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
987
9.35k
                                                       superR, getContext()));
988
9.35k
    }
989
7.64k
  }
990
7.64k
  return UnknownVal();
991
7.64k
}
992
993
const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
994
86.2k
                                                   SVal V) {
995
86.2k
  if (V.isUnknownOrUndef())
996
7
    return nullptr;
997
86.2k
998
86.2k
  
if (Optional<loc::ConcreteInt> 86.2k
X86.2k
= V.getAs<loc::ConcreteInt>())
999
0
    return &X->getValue();
1000
86.2k
1001
86.2k
  
if (Optional<nonloc::ConcreteInt> 86.2k
X86.2k
= V.getAs<nonloc::ConcreteInt>())
1002
42.5k
    return &X->getValue();
1003
43.7k
1004
43.7k
  
if (SymbolRef 43.7k
Sym43.7k
= V.getAsSymbol())
1005
43.7k
    return state->getConstraintManager().getSymVal(state, Sym);
1006
1
1007
1
  // FIXME: Add support for SymExprs.
1008
1
  return nullptr;
1009
1
}
1010
1011
32.4k
SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
1012
32.4k
  // For now, this function tries to constant-fold symbols inside a
1013
32.4k
  // nonloc::SymbolVal, and does nothing else. More simplifications should
1014
32.4k
  // be possible, such as constant-folding an index in an ElementRegion.
1015
32.4k
1016
32.4k
  class Simplifier : public FullSValVisitor<Simplifier, SVal> {
1017
32.4k
    ProgramStateRef State;
1018
32.4k
    SValBuilder &SVB;
1019
32.4k
1020
32.4k
  public:
1021
32.4k
    Simplifier(ProgramStateRef State)
1022
32.4k
        : State(State), SVB(State->getStateManager().getSValBuilder()) {}
1023
32.4k
1024
33.0k
    SVal VisitSymbolData(const SymbolData *S) {
1025
33.0k
      if (const llvm::APSInt *I =
1026
33.0k
              SVB.getKnownValue(State, nonloc::SymbolVal(S)))
1027
255
        
return Loc::isLocType(S->getType()) ? 255
(SVal)SVB.makeIntLocVal(*I)1
1028
254
                                            : (SVal)SVB.makeIntVal(*I);
1029
32.7k
      
return Loc::isLocType(S->getType()) ? 32.7k
(SVal)SVB.makeLoc(S)87
1030
32.6k
                                          : nonloc::SymbolVal(S);
1031
33.0k
    }
1032
32.4k
1033
32.4k
    // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
1034
32.4k
    // start producing them.
1035
32.4k
1036
656
    SVal VisitSymIntExpr(const SymIntExpr *S) {
1037
656
      SVal LHS = Visit(S->getLHS());
1038
656
      SVal RHS;
1039
656
      // By looking at the APSInt in the right-hand side of S, we cannot
1040
656
      // figure out if it should be treated as a Loc or as a NonLoc.
1041
656
      // So make our guess by recalling that we cannot multiply pointers
1042
656
      // or compare a pointer to an integer.
1043
656
      if (Loc::isLocType(S->getLHS()->getType()) &&
1044
656
          
BinaryOperator::isComparisonOp(S->getOpcode())0
) {
1045
0
        // The usual conversion of $sym to &SymRegion{$sym}, as they have
1046
0
        // the same meaning for Loc-type symbols, but the latter form
1047
0
        // is preferred in SVal computations for being Loc itself.
1048
0
        if (SymbolRef 
Sym0
= LHS.getAsSymbol()) {
1049
0
          assert(Loc::isLocType(Sym->getType()));
1050
0
          LHS = SVB.makeLoc(Sym);
1051
0
        }
1052
0
        RHS = SVB.makeIntLocVal(S->getRHS());
1053
656
      } else {
1054
656
        RHS = SVB.makeIntVal(S->getRHS());
1055
656
      }
1056
656
      return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
1057
656
    }
1058
32.4k
1059
692
    SVal VisitSymSymExpr(const SymSymExpr *S) {
1060
692
      SVal LHS = Visit(S->getLHS());
1061
692
      SVal RHS = Visit(S->getRHS());
1062
692
      return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
1063
692
    }
1064
32.4k
1065
104
    SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }
1066
32.4k
1067
0
    SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }
1068
32.4k
1069
32.4k
    SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
1070
32.4k
      // Simplification is much more costly than computing complexity.
1071
32.4k
      // For high complexity, it may be not worth it.
1072
32.4k
      if (V.getSymbol()->computeComplexity() > 100)
1073
33
        return V;
1074
32.4k
      return Visit(V.getSymbol());
1075
32.4k
    }
1076
32.4k
1077
0
    SVal VisitSVal(SVal V) { return V; }
1078
32.4k
  };
1079
32.4k
1080
32.4k
  return Simplifier(State).Visit(V);
1081
32.4k
}