clang  14.0.0git
SimpleSValBuilder.cpp
Go to the documentation of this file.
1 // SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- 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 SimpleSValBuilder, a basic implementation of SValBuilder.
10 //
11 //===----------------------------------------------------------------------===//
12 
18 
19 using namespace clang;
20 using namespace ento;
21 
22 namespace {
23 class SimpleSValBuilder : public SValBuilder {
24 public:
25  SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
26  ProgramStateManager &stateMgr)
27  : SValBuilder(alloc, context, stateMgr) {}
28  ~SimpleSValBuilder() override {}
29 
30  SVal evalMinus(NonLoc val) override;
31  SVal evalComplement(NonLoc val) override;
32  SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
33  NonLoc lhs, NonLoc rhs, QualType resultTy) override;
34  SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
35  Loc lhs, Loc rhs, QualType resultTy) override;
36  SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
37  Loc lhs, NonLoc rhs, QualType resultTy) override;
38 
39  /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
40  /// (integer) value, that value is returned. Otherwise, returns NULL.
41  const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
42 
43  /// Recursively descends into symbolic expressions and replaces symbols
44  /// with their known values (in the sense of the getKnownValue() method).
45  SVal simplifySVal(ProgramStateRef State, SVal V) override;
46 
47  SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
48  const llvm::APSInt &RHS, QualType resultTy);
49 };
50 } // end anonymous namespace
51 
52 SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
53  ASTContext &context,
54  ProgramStateManager &stateMgr) {
55  return new SimpleSValBuilder(alloc, context, stateMgr);
56 }
57 
58 //===----------------------------------------------------------------------===//
59 // Transfer function for unary operators.
60 //===----------------------------------------------------------------------===//
61 
62 SVal SimpleSValBuilder::evalMinus(NonLoc val) {
63  switch (val.getSubKind()) {
64  case nonloc::ConcreteIntKind:
65  return val.castAs<nonloc::ConcreteInt>().evalMinus(*this);
66  default:
67  return UnknownVal();
68  }
69 }
70 
71 SVal SimpleSValBuilder::evalComplement(NonLoc X) {
72  switch (X.getSubKind()) {
73  case nonloc::ConcreteIntKind:
74  return X.castAs<nonloc::ConcreteInt>().evalComplement(*this);
75  default:
76  return UnknownVal();
77  }
78 }
79 
80 //===----------------------------------------------------------------------===//
81 // Transfer function for binary operators.
82 //===----------------------------------------------------------------------===//
83 
84 SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
86  const llvm::APSInt &RHS,
87  QualType resultTy) {
88  bool isIdempotent = false;
89 
90  // Check for a few special cases with known reductions first.
91  switch (op) {
92  default:
93  // We can't reduce this case; just treat it normally.
94  break;
95  case BO_Mul:
96  // a*0 and a*1
97  if (RHS == 0)
98  return makeIntVal(0, resultTy);
99  else if (RHS == 1)
100  isIdempotent = true;
101  break;
102  case BO_Div:
103  // a/0 and a/1
104  if (RHS == 0)
105  // This is also handled elsewhere.
106  return UndefinedVal();
107  else if (RHS == 1)
108  isIdempotent = true;
109  break;
110  case BO_Rem:
111  // a%0 and a%1
112  if (RHS == 0)
113  // This is also handled elsewhere.
114  return UndefinedVal();
115  else if (RHS == 1)
116  return makeIntVal(0, resultTy);
117  break;
118  case BO_Add:
119  case BO_Sub:
120  case BO_Shl:
121  case BO_Shr:
122  case BO_Xor:
123  // a+0, a-0, a<<0, a>>0, a^0
124  if (RHS == 0)
125  isIdempotent = true;
126  break;
127  case BO_And:
128  // a&0 and a&(~0)
129  if (RHS == 0)
130  return makeIntVal(0, resultTy);
131  else if (RHS.isAllOnes())
132  isIdempotent = true;
133  break;
134  case BO_Or:
135  // a|0 and a|(~0)
136  if (RHS == 0)
137  isIdempotent = true;
138  else if (RHS.isAllOnes()) {
139  const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS);
140  return nonloc::ConcreteInt(Result);
141  }
142  break;
143  }
144 
145  // Idempotent ops (like a*1) can still change the type of an expression.
146  // Wrap the LHS up in a NonLoc again and let evalCast do the
147  // dirty work.
148  if (isIdempotent)
149  return evalCast(nonloc::SymbolVal(LHS), resultTy, QualType{});
150 
151  // If we reach this point, the expression cannot be simplified.
152  // Make a SymbolVal for the entire expression, after converting the RHS.
153  const llvm::APSInt *ConvertedRHS = &RHS;
155  // We're looking for a type big enough to compare the symbolic value
156  // with the given constant.
157  // FIXME: This is an approximation of Sema::UsualArithmeticConversions.
158  ASTContext &Ctx = getContext();
159  QualType SymbolType = LHS->getType();
160  uint64_t ValWidth = RHS.getBitWidth();
161  uint64_t TypeWidth = Ctx.getTypeSize(SymbolType);
162 
163  if (ValWidth < TypeWidth) {
164  // If the value is too small, extend it.
165  ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
166  } else if (ValWidth == TypeWidth) {
167  // If the value is signed but the symbol is unsigned, do the comparison
168  // in unsigned space. [C99 6.3.1.8]
169  // (For the opposite case, the value is already unsigned.)
170  if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType())
171  ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
172  }
173  } else
174  ConvertedRHS = &BasicVals.Convert(resultTy, RHS);
175 
176  return makeNonLoc(LHS, op, *ConvertedRHS, resultTy);
177 }
178 
179 // See if Sym is known to be a relation Rel with Bound.
182  SValBuilder &SVB = State->getStateManager().getSValBuilder();
183  SVal Result =
184  SVB.evalBinOpNN(State, Rel, nonloc::SymbolVal(Sym),
185  nonloc::ConcreteInt(Bound), SVB.getConditionType());
186  if (auto DV = Result.getAs<DefinedSVal>()) {
187  return !State->assume(*DV, false);
188  }
189  return false;
190 }
191 
192 // See if Sym is known to be within [min/4, max/4], where min and max
193 // are the bounds of the symbol's integral type. With such symbols,
194 // some manipulations can be performed without the risk of overflow.
195 // assume() doesn't cause infinite recursion because we should be dealing
196 // with simpler symbols on every recursive call.
199  SValBuilder &SVB = State->getStateManager().getSValBuilder();
200  BasicValueFactory &BV = SVB.getBasicValueFactory();
201 
202  QualType T = Sym->getType();
203  assert(T->isSignedIntegerOrEnumerationType() &&
204  "This only works with signed integers!");
205  APSIntType AT = BV.getAPSIntType(T);
206 
207  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(4), Min = -Max;
208  return isInRelation(BO_LE, Sym, Max, State) &&
209  isInRelation(BO_GE, Sym, Min, State);
210 }
211 
212 // Same for the concrete integers: see if I is within [min/4, max/4].
214  APSIntType AT(I);
215  assert(!AT.isUnsigned() &&
216  "This only works with signed integers!");
217 
218  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(4), Min = -Max;
219  return (I <= Max) && (I >= -Max);
220 }
221 
222 static std::pair<SymbolRef, llvm::APSInt>
223 decomposeSymbol(SymbolRef Sym, BasicValueFactory &BV) {
224  if (const auto *SymInt = dyn_cast<SymIntExpr>(Sym))
225  if (BinaryOperator::isAdditiveOp(SymInt->getOpcode()))
226  return std::make_pair(SymInt->getLHS(),
227  (SymInt->getOpcode() == BO_Add) ?
228  (SymInt->getRHS()) :
229  (-SymInt->getRHS()));
230 
231  // Fail to decompose: "reduce" the problem to the "$x + 0" case.
232  return std::make_pair(Sym, BV.getValue(0, Sym->getType()));
233 }
234 
235 // Simplify "(LSym + LInt) Op (RSym + RInt)" assuming all values are of the
236 // same signed integral type and no overflows occur (which should be checked
237 // by the caller).
240  SymbolRef LSym, llvm::APSInt LInt,
241  SymbolRef RSym, llvm::APSInt RInt) {
242  SValBuilder &SVB = State->getStateManager().getSValBuilder();
243  BasicValueFactory &BV = SVB.getBasicValueFactory();
244  SymbolManager &SymMgr = SVB.getSymbolManager();
245 
246  QualType SymTy = LSym->getType();
247  assert(SymTy == RSym->getType() &&
248  "Symbols are not of the same type!");
249  assert(APSIntType(LInt) == BV.getAPSIntType(SymTy) &&
250  "Integers are not of the same type as symbols!");
251  assert(APSIntType(RInt) == BV.getAPSIntType(SymTy) &&
252  "Integers are not of the same type as symbols!");
253 
254  QualType ResultTy;
256  ResultTy = SVB.getConditionType();
257  else if (BinaryOperator::isAdditiveOp(Op))
258  ResultTy = SymTy;
259  else
260  llvm_unreachable("Operation not suitable for unchecked rearrangement!");
261 
262  // FIXME: Can we use assume() without getting into an infinite recursion?
263  if (LSym == RSym)
264  return SVB.evalBinOpNN(State, Op, nonloc::ConcreteInt(LInt),
265  nonloc::ConcreteInt(RInt), ResultTy)
266  .castAs<NonLoc>();
267 
268  SymbolRef ResultSym = nullptr;
269  BinaryOperator::Opcode ResultOp;
270  llvm::APSInt ResultInt;
272  // Prefer comparing to a non-negative number.
273  // FIXME: Maybe it'd be better to have consistency in
274  // "$x - $y" vs. "$y - $x" because those are solver's keys.
275  if (LInt > RInt) {
276  ResultSym = SymMgr.getSymSymExpr(RSym, BO_Sub, LSym, SymTy);
278  ResultInt = LInt - RInt; // Opposite order!
279  } else {
280  ResultSym = SymMgr.getSymSymExpr(LSym, BO_Sub, RSym, SymTy);
281  ResultOp = Op;
282  ResultInt = RInt - LInt; // Opposite order!
283  }
284  } else {
285  ResultSym = SymMgr.getSymSymExpr(LSym, Op, RSym, SymTy);
286  ResultInt = (Op == BO_Add) ? (LInt + RInt) : (LInt - RInt);
287  ResultOp = BO_Add;
288  // Bring back the cosmetic difference.
289  if (ResultInt < 0) {
290  ResultInt = -ResultInt;
291  ResultOp = BO_Sub;
292  } else if (ResultInt == 0) {
293  // Shortcut: Simplify "$x + 0" to "$x".
294  return nonloc::SymbolVal(ResultSym);
295  }
296  }
297  const llvm::APSInt &PersistentResultInt = BV.getValue(ResultInt);
298  return nonloc::SymbolVal(
299  SymMgr.getSymIntExpr(ResultSym, ResultOp, PersistentResultInt, ResultTy));
300 }
301 
302 // Rearrange if symbol type matches the result type and if the operator is a
303 // comparison operator, both symbol and constant must be within constant
304 // overflow bounds.
306  SymbolRef Sym, llvm::APSInt Int, QualType Ty) {
307  return Sym->getType() == Ty &&
311 }
312 
314  BinaryOperator::Opcode Op, NonLoc Lhs,
315  NonLoc Rhs, QualType ResultTy) {
316  ProgramStateManager &StateMgr = State->getStateManager();
317  SValBuilder &SVB = StateMgr.getSValBuilder();
318 
319  // We expect everything to be of the same type - this type.
320  QualType SingleTy;
321 
322  // FIXME: After putting complexity threshold to the symbols we can always
323  // rearrange additive operations but rearrange comparisons only if
324  // option is set.
325  if (!SVB.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation)
326  return None;
327 
328  SymbolRef LSym = Lhs.getAsSymbol();
329  if (!LSym)
330  return None;
331 
333  SingleTy = LSym->getType();
334  if (ResultTy != SVB.getConditionType())
335  return None;
336  // Initialize SingleTy later with a symbol's type.
337  } else if (BinaryOperator::isAdditiveOp(Op)) {
338  SingleTy = ResultTy;
339  if (LSym->getType() != SingleTy)
340  return None;
341  } else {
342  // Don't rearrange other operations.
343  return None;
344  }
345 
346  assert(!SingleTy.isNull() && "We should have figured out the type by now!");
347 
348  // Rearrange signed symbolic expressions only
349  if (!SingleTy->isSignedIntegerOrEnumerationType())
350  return None;
351 
352  SymbolRef RSym = Rhs.getAsSymbol();
353  if (!RSym || RSym->getType() != SingleTy)
354  return None;
355 
356  BasicValueFactory &BV = State->getBasicVals();
357  llvm::APSInt LInt, RInt;
358  std::tie(LSym, LInt) = decomposeSymbol(LSym, BV);
359  std::tie(RSym, RInt) = decomposeSymbol(RSym, BV);
360  if (!shouldRearrange(State, Op, LSym, LInt, SingleTy) ||
361  !shouldRearrange(State, Op, RSym, RInt, SingleTy))
362  return None;
363 
364  // We know that no overflows can occur anymore.
365  return doRearrangeUnchecked(State, Op, LSym, LInt, RSym, RInt);
366 }
367 
368 SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
370  NonLoc lhs, NonLoc rhs,
371  QualType resultTy) {
372  NonLoc InputLHS = lhs;
373  NonLoc InputRHS = rhs;
374 
375  // Handle trivial case where left-side and right-side are the same.
376  if (lhs == rhs)
377  switch (op) {
378  default:
379  break;
380  case BO_EQ:
381  case BO_LE:
382  case BO_GE:
383  return makeTruthVal(true, resultTy);
384  case BO_LT:
385  case BO_GT:
386  case BO_NE:
387  return makeTruthVal(false, resultTy);
388  case BO_Xor:
389  case BO_Sub:
390  if (resultTy->isIntegralOrEnumerationType())
391  return makeIntVal(0, resultTy);
392  return evalCast(makeIntVal(0, /*isUnsigned=*/false), resultTy,
393  QualType{});
394  case BO_Or:
395  case BO_And:
396  return evalCast(lhs, resultTy, QualType{});
397  }
398 
399  while (1) {
400  switch (lhs.getSubKind()) {
401  default:
402  return makeSymExprValNN(op, lhs, rhs, resultTy);
403  case nonloc::PointerToMemberKind: {
404  assert(rhs.getSubKind() == nonloc::PointerToMemberKind &&
405  "Both SVals should have pointer-to-member-type");
406  auto LPTM = lhs.castAs<nonloc::PointerToMember>(),
407  RPTM = rhs.castAs<nonloc::PointerToMember>();
408  auto LPTMD = LPTM.getPTMData(), RPTMD = RPTM.getPTMData();
409  switch (op) {
410  case BO_EQ:
411  return makeTruthVal(LPTMD == RPTMD, resultTy);
412  case BO_NE:
413  return makeTruthVal(LPTMD != RPTMD, resultTy);
414  default:
415  return UnknownVal();
416  }
417  }
418  case nonloc::LocAsIntegerKind: {
419  Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
420  switch (rhs.getSubKind()) {
421  case nonloc::LocAsIntegerKind:
422  // FIXME: at the moment the implementation
423  // of modeling "pointers as integers" is not complete.
425  return UnknownVal();
426  return evalBinOpLL(state, op, lhsL,
427  rhs.castAs<nonloc::LocAsInteger>().getLoc(),
428  resultTy);
429  case nonloc::ConcreteIntKind: {
430  // FIXME: at the moment the implementation
431  // of modeling "pointers as integers" is not complete.
433  return UnknownVal();
434  // Transform the integer into a location and compare.
435  // FIXME: This only makes sense for comparisons. If we want to, say,
436  // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it,
437  // then pack it back into a LocAsInteger.
438  llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
439  // If the region has a symbolic base, pay attention to the type; it
440  // might be coming from a non-default address space. For non-symbolic
441  // regions it doesn't matter that much because such comparisons would
442  // most likely evaluate to concrete false anyway. FIXME: We might
443  // still need to handle the non-comparison case.
444  if (SymbolRef lSym = lhs.getAsLocSymbol(true))
445  BasicVals.getAPSIntType(lSym->getType()).apply(i);
446  else
447  BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
448  return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
449  }
450  default:
451  switch (op) {
452  case BO_EQ:
453  return makeTruthVal(false, resultTy);
454  case BO_NE:
455  return makeTruthVal(true, resultTy);
456  default:
457  // This case also handles pointer arithmetic.
458  return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
459  }
460  }
461  }
462  case nonloc::ConcreteIntKind: {
463  llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue();
464 
465  // If we're dealing with two known constants, just perform the operation.
466  if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) {
467  llvm::APSInt RHSValue = *KnownRHSValue;
469  // We're looking for a type big enough to compare the two values.
470  // FIXME: This is not correct. char + short will result in a promotion
471  // to int. Unfortunately we have lost types by this point.
472  APSIntType CompareType = std::max(APSIntType(LHSValue),
473  APSIntType(RHSValue));
474  CompareType.apply(LHSValue);
475  CompareType.apply(RHSValue);
476  } else if (!BinaryOperator::isShiftOp(op)) {
477  APSIntType IntType = BasicVals.getAPSIntType(resultTy);
478  IntType.apply(LHSValue);
479  IntType.apply(RHSValue);
480  }
481 
482  const llvm::APSInt *Result =
483  BasicVals.evalAPSInt(op, LHSValue, RHSValue);
484  if (!Result)
485  return UndefinedVal();
486 
487  return nonloc::ConcreteInt(*Result);
488  }
489 
490  // Swap the left and right sides and flip the operator if doing so
491  // allows us to better reason about the expression (this is a form
492  // of expression canonicalization).
493  // While we're at it, catch some special cases for non-commutative ops.
494  switch (op) {
495  case BO_LT:
496  case BO_GT:
497  case BO_LE:
498  case BO_GE:
500  LLVM_FALLTHROUGH;
501  case BO_EQ:
502  case BO_NE:
503  case BO_Add:
504  case BO_Mul:
505  case BO_And:
506  case BO_Xor:
507  case BO_Or:
508  std::swap(lhs, rhs);
509  continue;
510  case BO_Shr:
511  // (~0)>>a
512  if (LHSValue.isAllOnes() && LHSValue.isSigned())
513  return evalCast(lhs, resultTy, QualType{});
514  LLVM_FALLTHROUGH;
515  case BO_Shl:
516  // 0<<a and 0>>a
517  if (LHSValue == 0)
518  return evalCast(lhs, resultTy, QualType{});
519  return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
520  case BO_Div:
521  // 0 / x == 0
522  case BO_Rem:
523  // 0 % x == 0
524  if (LHSValue == 0)
525  return makeZeroVal(resultTy);
526  LLVM_FALLTHROUGH;
527  default:
528  return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
529  }
530  }
531  case nonloc::SymbolValKind: {
532  // We only handle LHS as simple symbols or SymIntExprs.
533  SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol();
534 
535  // LHS is a symbolic expression.
536  if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) {
537 
538  // Is this a logical not? (!x is represented as x == 0.)
539  if (op == BO_EQ && rhs.isZeroConstant()) {
540  // We know how to negate certain expressions. Simplify them here.
541 
542  BinaryOperator::Opcode opc = symIntExpr->getOpcode();
543  switch (opc) {
544  default:
545  // We don't know how to negate this operation.
546  // Just handle it as if it were a normal comparison to 0.
547  break;
548  case BO_LAnd:
549  case BO_LOr:
550  llvm_unreachable("Logical operators handled by branching logic.");
551  case BO_Assign:
552  case BO_MulAssign:
553  case BO_DivAssign:
554  case BO_RemAssign:
555  case BO_AddAssign:
556  case BO_SubAssign:
557  case BO_ShlAssign:
558  case BO_ShrAssign:
559  case BO_AndAssign:
560  case BO_XorAssign:
561  case BO_OrAssign:
562  case BO_Comma:
563  llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
564  case BO_PtrMemD:
565  case BO_PtrMemI:
566  llvm_unreachable("Pointer arithmetic not handled here.");
567  case BO_LT:
568  case BO_GT:
569  case BO_LE:
570  case BO_GE:
571  case BO_EQ:
572  case BO_NE:
573  assert(resultTy->isBooleanType() ||
574  resultTy == getConditionType());
575  assert(symIntExpr->getType()->isBooleanType() ||
576  getContext().hasSameUnqualifiedType(symIntExpr->getType(),
577  getConditionType()));
578  // Negate the comparison and make a value.
580  return makeNonLoc(symIntExpr->getLHS(), opc,
581  symIntExpr->getRHS(), resultTy);
582  }
583  }
584 
585  // For now, only handle expressions whose RHS is a constant.
586  if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
587  // If both the LHS and the current expression are additive,
588  // fold their constants and try again.
590  BinaryOperator::Opcode lop = symIntExpr->getOpcode();
591  if (BinaryOperator::isAdditiveOp(lop)) {
592  // Convert the two constants to a common type, then combine them.
593 
594  // resultTy may not be the best type to convert to, but it's
595  // probably the best choice in expressions with mixed type
596  // (such as x+1U+2LL). The rules for implicit conversions should
597  // choose a reasonable type to preserve the expression, and will
598  // at least match how the value is going to be used.
599  APSIntType IntType = BasicVals.getAPSIntType(resultTy);
600  const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
601  const llvm::APSInt &second = IntType.convert(*RHSValue);
602 
603  const llvm::APSInt *newRHS;
604  if (lop == op)
605  newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
606  else
607  newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
608 
609  assert(newRHS && "Invalid operation despite common type!");
610  rhs = nonloc::ConcreteInt(*newRHS);
611  lhs = nonloc::SymbolVal(symIntExpr->getLHS());
612  op = lop;
613  continue;
614  }
615  }
616 
617  // Otherwise, make a SymIntExpr out of the expression.
618  return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
619  }
620  }
621 
622  // Does the symbolic expression simplify to a constant?
623  // If so, "fold" the constant by setting 'lhs' to a ConcreteInt
624  // and try again.
625  SVal simplifiedLhs = simplifySVal(state, lhs);
626  if (simplifiedLhs != lhs)
627  if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs<NonLoc>()) {
628  lhs = *simplifiedLhsAsNonLoc;
629  continue;
630  }
631 
632  // Is the RHS a constant?
633  if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
634  return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
635 
636  if (Optional<NonLoc> V = tryRearrange(state, op, lhs, rhs, resultTy))
637  return *V;
638 
639  // Give up -- this is not a symbolic expression we can handle.
640  return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
641  }
642  }
643  }
644 }
645 
646 static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR,
647  const FieldRegion *RightFR,
649  QualType resultTy,
650  SimpleSValBuilder &SVB) {
651  // Only comparisons are meaningful here!
653  return UnknownVal();
654 
655  // Next, see if the two FRs have the same super-region.
656  // FIXME: This doesn't handle casts yet, and simply stripping the casts
657  // doesn't help.
658  if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
659  return UnknownVal();
660 
661  const FieldDecl *LeftFD = LeftFR->getDecl();
662  const FieldDecl *RightFD = RightFR->getDecl();
663  const RecordDecl *RD = LeftFD->getParent();
664 
665  // Make sure the two FRs are from the same kind of record. Just in case!
666  // FIXME: This is probably where inheritance would be a problem.
667  if (RD != RightFD->getParent())
668  return UnknownVal();
669 
670  // We know for sure that the two fields are not the same, since that
671  // would have given us the same SVal.
672  if (op == BO_EQ)
673  return SVB.makeTruthVal(false, resultTy);
674  if (op == BO_NE)
675  return SVB.makeTruthVal(true, resultTy);
676 
677  // Iterate through the fields and see which one comes first.
678  // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
679  // members and the units in which bit-fields reside have addresses that
680  // increase in the order in which they are declared."
681  bool leftFirst = (op == BO_LT || op == BO_LE);
682  for (const auto *I : RD->fields()) {
683  if (I == LeftFD)
684  return SVB.makeTruthVal(leftFirst, resultTy);
685  if (I == RightFD)
686  return SVB.makeTruthVal(!leftFirst, resultTy);
687  }
688 
689  llvm_unreachable("Fields not found in parent record's definition");
690 }
691 
692 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
693 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
695  Loc lhs, Loc rhs,
696  QualType resultTy) {
697  // Only comparisons and subtractions are valid operations on two pointers.
698  // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
699  // However, if a pointer is casted to an integer, evalBinOpNN may end up
700  // calling this function with another operation (PR7527). We don't attempt to
701  // model this for now, but it could be useful, particularly when the
702  // "location" is actually an integer value that's been passed through a void*.
703  if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
704  return UnknownVal();
705 
706  // Special cases for when both sides are identical.
707  if (lhs == rhs) {
708  switch (op) {
709  default:
710  llvm_unreachable("Unimplemented operation for two identical values");
711  case BO_Sub:
712  return makeZeroVal(resultTy);
713  case BO_EQ:
714  case BO_LE:
715  case BO_GE:
716  return makeTruthVal(true, resultTy);
717  case BO_NE:
718  case BO_LT:
719  case BO_GT:
720  return makeTruthVal(false, resultTy);
721  }
722  }
723 
724  switch (lhs.getSubKind()) {
725  default:
726  llvm_unreachable("Ordering not implemented for this Loc.");
727 
728  case loc::GotoLabelKind:
729  // The only thing we know about labels is that they're non-null.
730  if (rhs.isZeroConstant()) {
731  switch (op) {
732  default:
733  break;
734  case BO_Sub:
735  return evalCast(lhs, resultTy, QualType{});
736  case BO_EQ:
737  case BO_LE:
738  case BO_LT:
739  return makeTruthVal(false, resultTy);
740  case BO_NE:
741  case BO_GT:
742  case BO_GE:
743  return makeTruthVal(true, resultTy);
744  }
745  }
746  // There may be two labels for the same location, and a function region may
747  // have the same address as a label at the start of the function (depending
748  // on the ABI).
749  // FIXME: we can probably do a comparison against other MemRegions, though.
750  // FIXME: is there a way to tell if two labels refer to the same location?
751  return UnknownVal();
752 
753  case loc::ConcreteIntKind: {
754  // If one of the operands is a symbol and the other is a constant,
755  // build an expression for use by the constraint manager.
756  if (SymbolRef rSym = rhs.getAsLocSymbol()) {
757  // We can only build expressions with symbols on the left,
758  // so we need a reversible operator.
759  if (!BinaryOperator::isComparisonOp(op) || op == BO_Cmp)
760  return UnknownVal();
761 
762  const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
764  return makeNonLoc(rSym, op, lVal, resultTy);
765  }
766 
767  // If both operands are constants, just perform the operation.
768  if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
769  SVal ResultVal =
770  lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
771  if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
772  return evalCast(*Result, resultTy, QualType{});
773 
774  assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
775  return UnknownVal();
776  }
777 
778  // Special case comparisons against NULL.
779  // This must come after the test if the RHS is a symbol, which is used to
780  // build constraints. The address of any non-symbolic region is guaranteed
781  // to be non-NULL, as is any label.
782  assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
783  if (lhs.isZeroConstant()) {
784  switch (op) {
785  default:
786  break;
787  case BO_EQ:
788  case BO_GT:
789  case BO_GE:
790  return makeTruthVal(false, resultTy);
791  case BO_NE:
792  case BO_LT:
793  case BO_LE:
794  return makeTruthVal(true, resultTy);
795  }
796  }
797 
798  // Comparing an arbitrary integer to a region or label address is
799  // completely unknowable.
800  return UnknownVal();
801  }
802  case loc::MemRegionValKind: {
803  if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
804  // If one of the operands is a symbol and the other is a constant,
805  // build an expression for use by the constraint manager.
806  if (SymbolRef lSym = lhs.getAsLocSymbol(true)) {
808  return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
809  return UnknownVal();
810  }
811  // Special case comparisons to NULL.
812  // This must come after the test if the LHS is a symbol, which is used to
813  // build constraints. The address of any non-symbolic region is guaranteed
814  // to be non-NULL.
815  if (rInt->isZeroConstant()) {
816  if (op == BO_Sub)
817  return evalCast(lhs, resultTy, QualType{});
818 
820  QualType boolType = getContext().BoolTy;
821  NonLoc l = evalCast(lhs, boolType, QualType{}).castAs<NonLoc>();
822  NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>();
823  return evalBinOpNN(state, op, l, r, resultTy);
824  }
825  }
826 
827  // Comparing a region to an arbitrary integer is completely unknowable.
828  return UnknownVal();
829  }
830 
831  // Get both values as regions, if possible.
832  const MemRegion *LeftMR = lhs.getAsRegion();
833  assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");
834 
835  const MemRegion *RightMR = rhs.getAsRegion();
836  if (!RightMR)
837  // The RHS is probably a label, which in theory could address a region.
838  // FIXME: we can probably make a more useful statement about non-code
839  // regions, though.
840  return UnknownVal();
841 
842  const MemRegion *LeftBase = LeftMR->getBaseRegion();
843  const MemRegion *RightBase = RightMR->getBaseRegion();
844  const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
845  const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
846  const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
847 
848  // If the two regions are from different known memory spaces they cannot be
849  // equal. Also, assume that no symbolic region (whose memory space is
850  // unknown) is on the stack.
851  if (LeftMS != RightMS &&
852  ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
853  (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
854  switch (op) {
855  default:
856  return UnknownVal();
857  case BO_EQ:
858  return makeTruthVal(false, resultTy);
859  case BO_NE:
860  return makeTruthVal(true, resultTy);
861  }
862  }
863 
864  // If both values wrap regions, see if they're from different base regions.
865  // Note, heap base symbolic regions are assumed to not alias with
866  // each other; for example, we assume that malloc returns different address
867  // on each invocation.
868  // FIXME: ObjC object pointers always reside on the heap, but currently
869  // we treat their memory space as unknown, because symbolic pointers
870  // to ObjC objects may alias. There should be a way to construct
871  // possibly-aliasing heap-based regions. For instance, MacOSXApiChecker
872  // guesses memory space for ObjC object pointers manually instead of
873  // relying on us.
874  if (LeftBase != RightBase &&
875  ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
876  (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
877  switch (op) {
878  default:
879  return UnknownVal();
880  case BO_EQ:
881  return makeTruthVal(false, resultTy);
882  case BO_NE:
883  return makeTruthVal(true, resultTy);
884  }
885  }
886 
887  // Handle special cases for when both regions are element regions.
888  const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
889  const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR);
890  if (RightER && LeftER) {
891  // Next, see if the two ERs have the same super-region and matching types.
892  // FIXME: This should do something useful even if the types don't match,
893  // though if both indexes are constant the RegionRawOffset path will
894  // give the correct answer.
895  if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
896  LeftER->getElementType() == RightER->getElementType()) {
897  // Get the left index and cast it to the correct type.
898  // If the index is unknown or undefined, bail out here.
899  SVal LeftIndexVal = LeftER->getIndex();
900  Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
901  if (!LeftIndex)
902  return UnknownVal();
903  LeftIndexVal = evalCast(*LeftIndex, ArrayIndexTy, QualType{});
904  LeftIndex = LeftIndexVal.getAs<NonLoc>();
905  if (!LeftIndex)
906  return UnknownVal();
907 
908  // Do the same for the right index.
909  SVal RightIndexVal = RightER->getIndex();
910  Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
911  if (!RightIndex)
912  return UnknownVal();
913  RightIndexVal = evalCast(*RightIndex, ArrayIndexTy, QualType{});
914  RightIndex = RightIndexVal.getAs<NonLoc>();
915  if (!RightIndex)
916  return UnknownVal();
917 
918  // Actually perform the operation.
919  // evalBinOpNN expects the two indexes to already be the right type.
920  return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
921  }
922  }
923 
924  // Special handling of the FieldRegions, even with symbolic offsets.
925  const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
926  const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR);
927  if (RightFR && LeftFR) {
928  SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
929  *this);
930  if (!R.isUnknown())
931  return R;
932  }
933 
934  // Compare the regions using the raw offsets.
935  RegionOffset LeftOffset = LeftMR->getAsOffset();
936  RegionOffset RightOffset = RightMR->getAsOffset();
937 
938  if (LeftOffset.getRegion() != nullptr &&
939  LeftOffset.getRegion() == RightOffset.getRegion() &&
940  !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) {
941  int64_t left = LeftOffset.getOffset();
942  int64_t right = RightOffset.getOffset();
943 
944  switch (op) {
945  default:
946  return UnknownVal();
947  case BO_LT:
948  return makeTruthVal(left < right, resultTy);
949  case BO_GT:
950  return makeTruthVal(left > right, resultTy);
951  case BO_LE:
952  return makeTruthVal(left <= right, resultTy);
953  case BO_GE:
954  return makeTruthVal(left >= right, resultTy);
955  case BO_EQ:
956  return makeTruthVal(left == right, resultTy);
957  case BO_NE:
958  return makeTruthVal(left != right, resultTy);
959  }
960  }
961 
962  // At this point we're not going to get a good answer, but we can try
963  // conjuring an expression instead.
964  SymbolRef LHSSym = lhs.getAsLocSymbol();
965  SymbolRef RHSSym = rhs.getAsLocSymbol();
966  if (LHSSym && RHSSym)
967  return makeNonLoc(LHSSym, op, RHSSym, resultTy);
968 
969  // If we get here, we have no way of comparing the regions.
970  return UnknownVal();
971  }
972  }
973 }
974 
975 SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
976  BinaryOperator::Opcode op, Loc lhs,
977  NonLoc rhs, QualType resultTy) {
978  if (op >= BO_PtrMemD && op <= BO_PtrMemI) {
979  if (auto PTMSV = rhs.getAs<nonloc::PointerToMember>()) {
980  if (PTMSV->isNullMemberPointer())
981  return UndefinedVal();
982 
983  auto getFieldLValue = [&](const auto *FD) -> SVal {
984  SVal Result = lhs;
985 
986  for (const auto &I : *PTMSV)
987  Result = StateMgr.getStoreManager().evalDerivedToBase(
988  Result, I->getType(), I->isVirtual());
989 
990  return state->getLValue(FD, Result);
991  };
992 
993  if (const auto *FD = PTMSV->getDeclAs<FieldDecl>()) {
994  return getFieldLValue(FD);
995  }
996  if (const auto *FD = PTMSV->getDeclAs<IndirectFieldDecl>()) {
997  return getFieldLValue(FD);
998  }
999  }
1000 
1001  return rhs;
1002  }
1003 
1004  assert(!BinaryOperator::isComparisonOp(op) &&
1005  "arguments to comparison ops must be of the same type");
1006 
1007  // Special case: rhs is a zero constant.
1008  if (rhs.isZeroConstant())
1009  return lhs;
1010 
1011  // Perserve the null pointer so that it can be found by the DerefChecker.
1012  if (lhs.isZeroConstant())
1013  return lhs;
1014 
1015  // We are dealing with pointer arithmetic.
1016 
1017  // Handle pointer arithmetic on constant values.
1018  if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) {
1019  if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) {
1020  const llvm::APSInt &leftI = lhsInt->getValue();
1021  assert(leftI.isUnsigned());
1022  llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
1023 
1024  // Convert the bitwidth of rightI. This should deal with overflow
1025  // since we are dealing with concrete values.
1026  rightI = rightI.extOrTrunc(leftI.getBitWidth());
1027 
1028  // Offset the increment by the pointer size.
1029  llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
1030  QualType pointeeType = resultTy->getPointeeType();
1031  Multiplicand = getContext().getTypeSizeInChars(pointeeType).getQuantity();
1032  rightI *= Multiplicand;
1033 
1034  // Compute the adjusted pointer.
1035  switch (op) {
1036  case BO_Add:
1037  rightI = leftI + rightI;
1038  break;
1039  case BO_Sub:
1040  rightI = leftI - rightI;
1041  break;
1042  default:
1043  llvm_unreachable("Invalid pointer arithmetic operation");
1044  }
1045  return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
1046  }
1047  }
1048 
1049  // Handle cases where 'lhs' is a region.
1050  if (const MemRegion *region = lhs.getAsRegion()) {
1051  rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
1052  SVal index = UnknownVal();
1053  const SubRegion *superR = nullptr;
1054  // We need to know the type of the pointer in order to add an integer to it.
1055  // Depending on the type, different amount of bytes is added.
1056  QualType elementType;
1057 
1058  if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
1059  assert(op == BO_Add || op == BO_Sub);
1060  index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
1061  getArrayIndexType());
1062  superR = cast<SubRegion>(elemReg->getSuperRegion());
1063  elementType = elemReg->getElementType();
1064  }
1065  else if (isa<SubRegion>(region)) {
1066  assert(op == BO_Add || op == BO_Sub);
1067  index = (op == BO_Add) ? rhs : evalMinus(rhs);
1068  superR = cast<SubRegion>(region);
1069  // TODO: Is this actually reliable? Maybe improving our MemRegion
1070  // hierarchy to provide typed regions for all non-void pointers would be
1071  // better. For instance, we cannot extend this towards LocAsInteger
1072  // operations, where result type of the expression is integer.
1073  if (resultTy->isAnyPointerType())
1074  elementType = resultTy->getPointeeType();
1075  }
1076 
1077  // Represent arithmetic on void pointers as arithmetic on char pointers.
1078  // It is fine when a TypedValueRegion of char value type represents
1079  // a void pointer. Note that arithmetic on void pointers is a GCC extension.
1080  if (elementType->isVoidType())
1081  elementType = getContext().CharTy;
1082 
1083  if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) {
1084  return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
1085  superR, getContext()));
1086  }
1087  }
1088  return UnknownVal();
1089 }
1090 
1091 const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
1092  SVal V) {
1093  V = simplifySVal(state, V);
1094  if (V.isUnknownOrUndef())
1095  return nullptr;
1096 
1097  if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
1098  return &X->getValue();
1099 
1100  if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
1101  return &X->getValue();
1102 
1103  if (SymbolRef Sym = V.getAsSymbol())
1104  return state->getConstraintManager().getSymVal(state, Sym);
1105 
1106  // FIXME: Add support for SymExprs.
1107  return nullptr;
1108 }
1109 
1110 SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
1111  // For now, this function tries to constant-fold symbols inside a
1112  // nonloc::SymbolVal, and does nothing else. More simplifications should
1113  // be possible, such as constant-folding an index in an ElementRegion.
1114 
1115  class Simplifier : public FullSValVisitor<Simplifier, SVal> {
1117  SValBuilder &SVB;
1118 
1119  // Cache results for the lifetime of the Simplifier. Results change every
1120  // time new constraints are added to the program state, which is the whole
1121  // point of simplifying, and for that very reason it's pointless to maintain
1122  // the same cache for the duration of the whole analysis.
1123  llvm::DenseMap<SymbolRef, SVal> Cached;
1124 
1125  static bool isUnchanged(SymbolRef Sym, SVal Val) {
1126  return Sym == Val.getAsSymbol();
1127  }
1128 
1129  SVal cache(SymbolRef Sym, SVal V) {
1130  Cached[Sym] = V;
1131  return V;
1132  }
1133 
1134  SVal skip(SymbolRef Sym) {
1135  return cache(Sym, SVB.makeSymbolVal(Sym));
1136  }
1137 
1138  public:
1139  Simplifier(ProgramStateRef State)
1140  : State(State), SVB(State->getStateManager().getSValBuilder()) {}
1141 
1142  SVal VisitSymbolData(const SymbolData *S) {
1143  // No cache here.
1144  if (const llvm::APSInt *I =
1145  SVB.getKnownValue(State, SVB.makeSymbolVal(S)))
1146  return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I)
1147  : (SVal)SVB.makeIntVal(*I);
1148  return SVB.makeSymbolVal(S);
1149  }
1150 
1151  // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
1152  // start producing them.
1153 
1154  SVal VisitSymIntExpr(const SymIntExpr *S) {
1155  auto I = Cached.find(S);
1156  if (I != Cached.end())
1157  return I->second;
1158 
1159  SVal LHS = Visit(S->getLHS());
1160  if (isUnchanged(S->getLHS(), LHS))
1161  return skip(S);
1162 
1163  SVal RHS;
1164  // By looking at the APSInt in the right-hand side of S, we cannot
1165  // figure out if it should be treated as a Loc or as a NonLoc.
1166  // So make our guess by recalling that we cannot multiply pointers
1167  // or compare a pointer to an integer.
1168  if (Loc::isLocType(S->getLHS()->getType()) &&
1169  BinaryOperator::isComparisonOp(S->getOpcode())) {
1170  // The usual conversion of $sym to &SymRegion{$sym}, as they have
1171  // the same meaning for Loc-type symbols, but the latter form
1172  // is preferred in SVal computations for being Loc itself.
1173  if (SymbolRef Sym = LHS.getAsSymbol()) {
1174  assert(Loc::isLocType(Sym->getType()));
1175  LHS = SVB.makeLoc(Sym);
1176  }
1177  RHS = SVB.makeIntLocVal(S->getRHS());
1178  } else {
1179  RHS = SVB.makeIntVal(S->getRHS());
1180  }
1181 
1182  return cache(
1183  S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));
1184  }
1185 
1186  SVal VisitSymSymExpr(const SymSymExpr *S) {
1187  auto I = Cached.find(S);
1188  if (I != Cached.end())
1189  return I->second;
1190 
1191  // For now don't try to simplify mixed Loc/NonLoc expressions
1192  // because they often appear from LocAsInteger operations
1193  // and we don't know how to combine a LocAsInteger
1194  // with a concrete value.
1195  if (Loc::isLocType(S->getLHS()->getType()) !=
1196  Loc::isLocType(S->getRHS()->getType()))
1197  return skip(S);
1198 
1199  SVal LHS = Visit(S->getLHS());
1200  SVal RHS = Visit(S->getRHS());
1201  if (isUnchanged(S->getLHS(), LHS) && isUnchanged(S->getRHS(), RHS))
1202  return skip(S);
1203 
1204  return cache(
1205  S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));
1206  }
1207 
1208  SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }
1209 
1210  SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }
1211 
1212  SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
1213  // Simplification is much more costly than computing complexity.
1214  // For high complexity, it may be not worth it.
1215  return Visit(V.getSymbol());
1216  }
1217 
1218  SVal VisitSVal(SVal V) { return V; }
1219  };
1220 
1221  // A crude way of preventing this function from calling itself from evalBinOp.
1222  static bool isReentering = false;
1223  if (isReentering)
1224  return V;
1225 
1226  isReentering = true;
1227  SVal SimplifiedV = Simplifier(State).Visit(V);
1228  isReentering = false;
1229 
1230  return SimplifiedV;
1231 }
clang::ento::Loc::isLocType
static bool isLocType(QualType T)
Definition: SVals.h:336
max
__DEVICE__ int max(int __a, int __b)
Definition: __clang_cuda_math.h:196
isWithinConstantOverflowBounds
static bool isWithinConstantOverflowBounds(SymbolRef Sym, ProgramStateRef State)
Definition: SimpleSValBuilder.cpp:197
isInRelation
static bool isInRelation(BinaryOperator::Opcode Rel, SymbolRef Sym, llvm::APSInt Bound, ProgramStateRef State)
Definition: SimpleSValBuilder.cpp:180
clang::BinaryOperator::isAdditiveOp
bool isAdditiveOp() const
Definition: Expr.h:3889
clang::ento::createSimpleSValBuilder
SValBuilder * createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context, ProgramStateManager &stateMgr)
Definition: SimpleSValBuilder.cpp:52
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:673
evalBinOpFieldRegionFieldRegion
static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR, const FieldRegion *RightFR, BinaryOperator::Opcode op, QualType resultTy, SimpleSValBuilder &SVB)
Definition: SimpleSValBuilder.cpp:646
doRearrangeUnchecked
static NonLoc doRearrangeUnchecked(ProgramStateRef State, BinaryOperator::Opcode Op, SymbolRef LSym, llvm::APSInt LInt, SymbolRef RSym, llvm::APSInt RInt)
Definition: SimpleSValBuilder.cpp:238
clang::FieldDecl
Represents a member of a struct/union/class.
Definition: Decl.h:2835
clang::BinaryOperator::reverseComparisonOp
static Opcode reverseComparisonOp(Opcode Opc)
Definition: Expr.h:3921
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:110
llvm::Optional
Definition: LLVM.h:40
clang::Type::isVoidType
bool isVoidType() const
Definition: Type.h:6955
clang::tooling::X
static ToolExecutorPluginRegistry::Add< AllTUsToolExecutorPlugin > X("all-TUs", "Runs FrontendActions on all TUs in the compilation database. " "Tool results are stored in memory.")
clang::ento::SymSymExpr
BinarySymExprImpl< const SymExpr *, const SymExpr *, SymExpr::Kind::SymSymExprKind > SymSymExpr
Represents a symbolic expression like 'x' + 'y'.
Definition: SymbolManager.h:415
getValue
static SVal getValue(SVal val, SValBuilder &svalBuilder)
Definition: ArrayBoundCheckerV2.cpp:277
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
V
#define V(N, I)
Definition: ASTContext.h:3121
decomposeSymbol
static std::pair< SymbolRef, llvm::APSInt > decomposeSymbol(SymbolRef Sym, BasicValueFactory &BV)
Definition: SimpleSValBuilder.cpp:223
clang::Type::isSignedIntegerOrEnumerationType
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:2032
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:212
clang::ASTContext::getTypeSize
uint64_t getTypeSize(QualType T) const
Return the size of the specified (complete) type T, in bits.
Definition: ASTContext.h:2245
shouldRearrange
static bool shouldRearrange(ProgramStateRef State, BinaryOperator::Opcode Op, SymbolRef Sym, llvm::APSInt Int, QualType Ty)
Definition: SimpleSValBuilder.cpp:305
clang::Type::getPointeeType
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.
Definition: Type.cpp:625
clang::BinaryOperator::negateComparisonOp
static Opcode negateComparisonOp(Opcode Opc)
Definition: Expr.h:3908
clang::prec::PointerToMember
@ PointerToMember
Definition: OperatorPrecedence.h:42
state
and static some checkers Checker The latter are built on top of the former via the Checker and CheckerVisitor and attempts to isolate them from much of the gore of the internal analysis the analyzer is basically a source code simulator that traces out possible paths of execution The state of the and the combination of state and program point is a node in an exploded which has the entry program point and initial state
Definition: README.txt:30
clang::ento::SValBuilder
Definition: SValBuilder.h:53
clang::ASTContext::VoidPtrTy
CanQualType VoidPtrTy
Definition: ASTContext.h:1102
clang::ento::ProgramStateManager
Definition: ProgramState.h:463
clang::ento::SymIntExpr
BinarySymExprImpl< const SymExpr *, const llvm::APSInt &, SymExpr::Kind::SymIntExprKind > SymIntExpr
Represents a symbolic expression like 'x' + 3.
Definition: SymbolManager.h:407
SValBuilder.h
clang::RecordDecl::fields
field_range fields() const
Definition: Decl.h:4079
clang::QualType::isNull
bool isNull() const
Return true if this QualType doesn't point to a type yet.
Definition: Type.h:738
clang::BinaryOperator::isComparisonOp
bool isComparisonOp() const
Definition: Expr.h:3903
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
APSIntType.h
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
clang::Type::isBooleanType
bool isBooleanType() const
Definition: Type.h:7071
ProgramState.h
tryRearrange
static Optional< NonLoc > tryRearrange(ProgramStateRef State, BinaryOperator::Opcode Op, NonLoc Lhs, NonLoc Rhs, QualType ResultTy)
Definition: SimpleSValBuilder.cpp:313
ExprEngine.h
clang::FieldDecl::getParent
const RecordDecl * getParent() const
Returns the parent of this field declaration, which is the struct in which this field is defined.
Definition: Decl.h:3027
clang
Definition: CalledOnceCheck.h:17
clang::Type::isAnyPointerType
bool isAnyPointerType() const
Definition: Type.h:6676
clang::IndirectFieldDecl
Represents a field injected from an anonymous union/struct into the parent scope.
Definition: Decl.h:3089
clang::BinaryOperator::isShiftOp
bool isShiftOp() const
Definition: Expr.h:3891
SValVisitor.h
clang::RecordDecl
Represents a struct/union/class.
Definition: Decl.h:3859
clang::Type::isIntegralOrEnumerationType
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7058