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
13#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntPtr.h"
14#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
15#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
16#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
17#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
19#include <optional>
20
21using namespace clang;
22using namespace ento;
23
24namespace {
25class SimpleSValBuilder : public SValBuilder {
26
27 // Query the constraint manager whether the SVal has only one possible
28 // (integer) value. If that is the case, the value is returned. Otherwise,
29 // returns NULL.
30 // This is an implementation detail. Checkers should use `getKnownValue()`
31 // instead.
32 static const llvm::APSInt *getConstValue(ProgramStateRef state, SVal V);
33
34 // Helper function that returns the value stored in a nonloc::ConcreteInt or
35 // loc::ConcreteInt.
36 static const llvm::APSInt *getConcreteValue(SVal V);
37
38 // With one `simplifySValOnce` call, a compound symbols might collapse to
39 // simpler symbol tree that is still possible to further simplify. Thus, we
40 // do the simplification on a new symbol tree until we reach the simplest
41 // form, i.e. the fixpoint.
42 // Consider the following symbol `(b * b) * b * b` which has this tree:
43 // *
44 // / \
45 // * b
46 // / \
47 // / b
48 // (b * b)
49 // Now, if the `b * b == 1` new constraint is added then during the first
50 // iteration we have the following transformations:
51 // * *
52 // / \ / \
53 // * b --> b b
54 // / \
55 // / b
56 // 1
57 // We need another iteration to reach the final result `1`.
58 SVal simplifyUntilFixpoint(ProgramStateRef State, SVal Val);
59
60 // Recursively descends into symbolic expressions and replaces symbols
61 // with their known values (in the sense of the getConstValue() method).
62 // We traverse the symbol tree and query the constraint values for the
63 // sub-trees and if a value is a constant we do the constant folding.
64 SVal simplifySValOnce(ProgramStateRef State, SVal V);
65
66public:
67 SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
68 ProgramStateManager &stateMgr)
69 : SValBuilder(alloc, context, stateMgr) {}
70 ~SimpleSValBuilder() override {}
71
72 SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
73 NonLoc lhs, NonLoc rhs, QualType resultTy) override;
74 SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
75 Loc lhs, Loc rhs, QualType resultTy) override;
76 SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
77 Loc lhs, NonLoc rhs, QualType resultTy) override;
78
79 /// Evaluates a given SVal by recursively evaluating and
80 /// simplifying the children SVals. If the SVal has only one possible
81 /// (integer) value, that value is returned. Otherwise, returns NULL.
82 const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
83
84 /// Evaluates a given SVal by recursively evaluating and simplifying the
85 /// children SVals, then returns its minimal possible (integer) value. If the
86 /// constraint manager cannot provide a meaningful answer, this returns NULL.
87 const llvm::APSInt *getMinValue(ProgramStateRef state, SVal V) override;
88
89 /// Evaluates a given SVal by recursively evaluating and simplifying the
90 /// children SVals, then returns its maximal possible (integer) value. If the
91 /// constraint manager cannot provide a meaningful answer, this returns NULL.
92 const llvm::APSInt *getMaxValue(ProgramStateRef state, SVal V) override;
93
94 SVal simplifySVal(ProgramStateRef State, SVal V) override;
95
96 SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
97 const llvm::APSInt &RHS, QualType resultTy);
98};
99} // end anonymous namespace
100
101SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
102 ASTContext &context,
103 ProgramStateManager &stateMgr) {
104 return new SimpleSValBuilder(alloc, context, stateMgr);
105}
106
107// Checks if the negation the value and flipping sign preserve
108// the semantics on the operation in the resultType
109static bool isNegationValuePreserving(const llvm::APSInt &Value,
110 APSIntType ResultType) {
111 const unsigned ValueBits = Value.getSignificantBits();
112 if (ValueBits == ResultType.getBitWidth()) {
113 // The value is the lowest negative value that is representable
114 // in signed integer with bitWith of result type. The
115 // negation is representable if resultType is unsigned.
116 return ResultType.isUnsigned();
117 }
118
119 // If resultType bitWith is higher that number of bits required
120 // to represent RHS, the sign flip produce same value.
121 return ValueBits < ResultType.getBitWidth();
122}
123
124//===----------------------------------------------------------------------===//
125// Transfer function for binary operators.
126//===----------------------------------------------------------------------===//
127
128SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
129 BinaryOperator::Opcode op,
130 const llvm::APSInt &RHS,
131 QualType resultTy) {
132 bool isIdempotent = false;
133
134 // Check for a few special cases with known reductions first.
135 switch (op) {
136 default:
137 // We can't reduce this case; just treat it normally.
138 break;
139 case BO_Mul:
140 // a*0 and a*1
141 if (RHS == 0)
142 return makeIntVal(integer: 0, type: resultTy);
143 else if (RHS == 1)
144 isIdempotent = true;
145 break;
146 case BO_Div:
147 // a/0 and a/1
148 if (RHS == 0)
149 // This is also handled elsewhere.
150 return UndefinedVal();
151 else if (RHS == 1)
152 isIdempotent = true;
153 break;
154 case BO_Rem:
155 // a%0 and a%1
156 if (RHS == 0)
157 // This is also handled elsewhere.
158 return UndefinedVal();
159 else if (RHS == 1)
160 return makeIntVal(integer: 0, type: resultTy);
161 break;
162 case BO_Add:
163 case BO_Sub:
164 case BO_Shl:
165 case BO_Shr:
166 case BO_Xor:
167 // a+0, a-0, a<<0, a>>0, a^0
168 if (RHS == 0)
169 isIdempotent = true;
170 break;
171 case BO_And:
172 // a&0 and a&(~0)
173 if (RHS == 0)
174 return makeIntVal(integer: 0, type: resultTy);
175 else if (RHS.isAllOnes())
176 isIdempotent = true;
177 break;
178 case BO_Or:
179 // a|0 and a|(~0)
180 if (RHS == 0)
181 isIdempotent = true;
182 else if (RHS.isAllOnes()) {
183 return nonloc::ConcreteInt(BasicVals.Convert(T: resultTy, From: RHS));
184 }
185 break;
186 }
187
188 // Idempotent ops (like a*1) can still change the type of an expression.
189 // Wrap the LHS up in a NonLoc again and let evalCast do the
190 // dirty work.
191 if (isIdempotent)
192 return evalCast(V: nonloc::SymbolVal(LHS), CastTy: resultTy, OriginalTy: QualType{});
193
194 // If we reach this point, the expression cannot be simplified.
195 // Make a SymbolVal for the entire expression, after converting the RHS.
196 std::optional<APSIntPtr> ConvertedRHS = BasicVals.getValue(X: RHS);
197 if (BinaryOperator::isComparisonOp(Opc: op)) {
198 // We're looking for a type big enough to compare the symbolic value
199 // with the given constant.
200 // FIXME: This is an approximation of Sema::UsualArithmeticConversions.
201 ASTContext &Ctx = getContext();
202 QualType SymbolType = LHS->getType();
203 uint64_t ValWidth = RHS.getBitWidth();
204 uint64_t TypeWidth = Ctx.getTypeSize(T: SymbolType);
205
206 if (ValWidth < TypeWidth) {
207 // If the value is too small, extend it.
208 ConvertedRHS = BasicVals.Convert(T: SymbolType, From: RHS);
209 } else if (ValWidth == TypeWidth) {
210 // If the value is signed but the symbol is unsigned, do the comparison
211 // in unsigned space. [C99 6.3.1.8]
212 // (For the opposite case, the value is already unsigned.)
213 if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType())
214 ConvertedRHS = BasicVals.Convert(T: SymbolType, From: RHS);
215 }
216 } else if (BinaryOperator::isAdditiveOp(Opc: op) && RHS.isNegative()) {
217 // Change a+(-N) into a-N, and a-(-N) into a+N
218 // Adjust addition/subtraction of negative value, to
219 // subtraction/addition of the negated value.
220 APSIntType resultIntTy = BasicVals.getAPSIntType(T: resultTy);
221 if (isNegationValuePreserving(Value: RHS, ResultType: resultIntTy)) {
222 ConvertedRHS = BasicVals.getValue(X: -resultIntTy.convert(Value: RHS));
223 op = (op == BO_Add) ? BO_Sub : BO_Add;
224 } else {
225 ConvertedRHS = BasicVals.Convert(T: resultTy, From: RHS);
226 }
227 } else
228 ConvertedRHS = BasicVals.Convert(T: resultTy, From: RHS);
229
230 return makeNonLoc(lhs: LHS, op, rhs: *ConvertedRHS, type: resultTy);
231}
232
233// See if Sym is known to be a relation Rel with Bound.
234static bool isInRelation(BinaryOperator::Opcode Rel, SymbolRef Sym,
235 llvm::APSInt Bound, ProgramStateRef State) {
236 SValBuilder &SVB = State->getStateManager().getSValBuilder();
237 BasicValueFactory &BV = SVB.getBasicValueFactory();
238 SVal Result = SVB.evalBinOpNN(state: State, op: Rel, lhs: nonloc::SymbolVal(Sym),
239 rhs: nonloc::ConcreteInt(BV.getValue(X: Bound)),
240 resultTy: SVB.getConditionType());
241 if (auto DV = Result.getAs<DefinedSVal>()) {
242 return !State->assume(Cond: *DV, Assumption: false);
243 }
244 return false;
245}
246
247// See if Sym is known to be within [min/4, max/4], where min and max
248// are the bounds of the symbol's integral type. With such symbols,
249// some manipulations can be performed without the risk of overflow.
250// assume() doesn't cause infinite recursion because we should be dealing
251// with simpler symbols on every recursive call.
252static bool isWithinConstantOverflowBounds(SymbolRef Sym,
253 ProgramStateRef State) {
254 SValBuilder &SVB = State->getStateManager().getSValBuilder();
255 BasicValueFactory &BV = SVB.getBasicValueFactory();
256
257 QualType T = Sym->getType();
258 assert(T->isSignedIntegerOrEnumerationType() &&
259 "This only works with signed integers!");
260 APSIntType AT = BV.getAPSIntType(T);
261
262 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(RawValue: 4), Min = -Max;
263 return isInRelation(Rel: BO_LE, Sym, Bound: Max, State) &&
264 isInRelation(Rel: BO_GE, Sym, Bound: Min, State);
265}
266
267// Same for the concrete integers: see if I is within [min/4, max/4].
268static bool isWithinConstantOverflowBounds(llvm::APSInt I, ProgramStateRef) {
269 APSIntType AT(I);
270 assert(!AT.isUnsigned() &&
271 "This only works with signed integers!");
272
273 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(RawValue: 4);
274 return (I <= Max) && (I >= -Max);
275}
276
277static std::pair<SymbolRef, APSIntPtr> decomposeSymbol(SymbolRef Sym,
278 BasicValueFactory &BV) {
279 if (const auto *SymInt = dyn_cast<SymIntExpr>(Val: Sym))
280 if (BinaryOperator::isAdditiveOp(Opc: SymInt->getOpcode()))
281 return std::make_pair(x: SymInt->getLHS(),
282 y: (SymInt->getOpcode() == BO_Add)
283 ? BV.getValue(X: SymInt->getRHS())
284 : BV.getValue(X: -SymInt->getRHS()));
285
286 // Fail to decompose: "reduce" the problem to the "$x + 0" case.
287 return std::make_pair(x&: Sym, y: BV.getValue(X: 0, T: Sym->getType()));
288}
289
290// Simplify "(LSym + LInt) Op (RSym + RInt)" when all values are of the
291// same signed integral type and no overflow occurs. Returns the simplified
292// value or std::nullopt when the preconditions are not satisfied or the
293// symbol complexity limit is reached.
294static std::optional<NonLoc> tryRearrange(ProgramStateRef State,
295 BinaryOperator::Opcode Op, NonLoc Lhs,
296 NonLoc Rhs, QualType ResultTy) {
297 ProgramStateManager &StateMgr = State->getStateManager();
298 SValBuilder &SVB = StateMgr.getSValBuilder();
299
300 // FIXME: This should be enabled by default, at least for additive operations.
301 if (!SVB.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation)
302 return std::nullopt;
303
304 SymbolRef LSym = Lhs.getAsSymbol();
305 if (!LSym)
306 return std::nullopt;
307
308 // We expect everything to be of the same type - this type.
309 QualType CommonTy = LSym->getType();
310
311 if (BinaryOperator::isComparisonOp(Opc: Op)) {
312 if (ResultTy != SVB.getConditionType())
313 return std::nullopt;
314 } else if (BinaryOperator::isAdditiveOp(Opc: Op)) {
315 if (ResultTy != CommonTy)
316 return std::nullopt;
317 } else {
318 // Don't rearrange other operations.
319 return std::nullopt;
320 }
321
322 // Rearrange signed symbolic expressions only.
323 // FIXME: This should also handle unsigned, at least for additive operations.
324 if (!CommonTy->isSignedIntegerOrEnumerationType())
325 return std::nullopt;
326
327 SymbolRef RSym = Rhs.getAsSymbol();
328 if (!RSym || RSym->getType() != CommonTy)
329 return std::nullopt;
330
331 BasicValueFactory &BV = State->getBasicVals();
332 llvm::APSInt LInt, RInt;
333 std::tie(args&: LSym, args&: LInt) = decomposeSymbol(Sym: LSym, BV);
334 std::tie(args&: RSym, args&: RInt) = decomposeSymbol(Sym: RSym, BV);
335
336 if (LSym->getType() != CommonTy || RSym->getType() != CommonTy)
337 return std::nullopt;
338
339 auto InBounds = [State](auto... X) {
340 return (... && isWithinConstantOverflowBounds(X, State));
341 };
342 if (BinaryOperator::isComparisonOp(Opc: Op) && !InBounds(LInt, RInt, LSym, RSym))
343 return std::nullopt;
344
345 // FIXME: Why can we assert these?
346 assert(APSIntType(LInt) == BV.getAPSIntType(CommonTy) &&
347 "Integers are not of the same type as symbols!");
348 assert(APSIntType(RInt) == BV.getAPSIntType(CommonTy) &&
349 "Integers are not of the same type as symbols!");
350
351 if (LSym == RSym)
352 return SVB
353 .evalBinOpNN(state: State, op: Op, lhs: nonloc::ConcreteInt(BV.getValue(X: LInt)),
354 rhs: nonloc::ConcreteInt(BV.getValue(X: RInt)), resultTy: ResultTy)
355 .getAs<NonLoc>();
356
357 auto MakeSymExprVal = [&SVB, CommonTy](SymbolRef Lhs, BinaryOperatorKind Op,
358 SymbolRef Rhs) {
359 return SVB.makeSymExprValNN(op: Op, lhs: nonloc::SymbolVal(Lhs),
360 rhs: nonloc::SymbolVal(Rhs), resultTy: CommonTy);
361 };
362
363 SVal ResultSV = UnknownVal();
364 BinaryOperator::Opcode ResultOp;
365 llvm::APSInt ResultInt;
366 if (BinaryOperator::isComparisonOp(Opc: Op)) {
367 // Prefer comparing to a non-negative number.
368 // FIXME: Maybe it'd be better to have consistency in
369 // "$x - $y" vs. "$y - $x" because those are solver's keys.
370 if (LInt > RInt) {
371 ResultSV = MakeSymExprVal(RSym, BO_Sub, LSym);
372 ResultOp = BinaryOperator::reverseComparisonOp(Opc: Op);
373 ResultInt = LInt - RInt; // Opposite order!
374 } else {
375 ResultSV = MakeSymExprVal(LSym, BO_Sub, RSym);
376 ResultOp = Op;
377 ResultInt = RInt - LInt; // Opposite order!
378 }
379 } else {
380 ResultSV = MakeSymExprVal(LSym, Op, RSym);
381 ResultInt = (Op == BO_Add) ? (LInt + RInt) : (LInt - RInt);
382 ResultOp = BO_Add;
383 // Bring back the cosmetic difference.
384 if (ResultInt < 0) {
385 ResultInt = -ResultInt;
386 ResultOp = BO_Sub;
387 } else if (ResultInt == 0) {
388 // Shortcut: Simplify "$x + 0" to "$x".
389 return ResultSV.getAs<NonLoc>();
390 }
391 }
392 if (auto ResultNL = ResultSV.getAs<NonLoc>()) {
393 nonloc::ConcreteInt ResultCI(BV.getValue(X: ResultInt));
394 return SVB.makeSymExprValNN(op: ResultOp, lhs: *ResultNL, rhs: ResultCI, resultTy: ResultTy)
395 .getAs<NonLoc>();
396 }
397 return std::nullopt;
398}
399
400SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
401 BinaryOperator::Opcode op,
402 NonLoc lhs, NonLoc rhs,
403 QualType resultTy) {
404 NonLoc InputLHS = lhs;
405 NonLoc InputRHS = rhs;
406
407 // Constraints may have changed since the creation of a bound SVal. Check if
408 // the values can be simplified based on those new constraints.
409 SVal simplifiedLhs = simplifySVal(State: state, V: lhs);
410 SVal simplifiedRhs = simplifySVal(State: state, V: rhs);
411 if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs<NonLoc>())
412 lhs = *simplifiedLhsAsNonLoc;
413 if (auto simplifiedRhsAsNonLoc = simplifiedRhs.getAs<NonLoc>())
414 rhs = *simplifiedRhsAsNonLoc;
415
416 // Handle trivial case where left-side and right-side are the same.
417 if (lhs == rhs)
418 switch (op) {
419 default:
420 break;
421 case BO_EQ:
422 case BO_LE:
423 case BO_GE:
424 return makeTruthVal(b: true, type: resultTy);
425 case BO_LT:
426 case BO_GT:
427 case BO_NE:
428 return makeTruthVal(b: false, type: resultTy);
429 case BO_Xor:
430 case BO_Sub:
431 if (resultTy->isIntegralOrEnumerationType())
432 return makeIntVal(integer: 0, type: resultTy);
433 return evalCast(V: makeIntVal(integer: 0, /*isUnsigned=*/false), CastTy: resultTy,
434 OriginalTy: QualType{});
435 case BO_Or:
436 case BO_And:
437 return evalCast(V: lhs, CastTy: resultTy, OriginalTy: QualType{});
438 }
439
440 while (true) {
441 switch (lhs.getKind()) {
442 default:
443 return makeSymExprValNN(op, lhs, rhs, resultTy);
444 case nonloc::PointerToMemberKind: {
445 assert(rhs.getKind() == nonloc::PointerToMemberKind &&
446 "Both SVals should have pointer-to-member-type");
447 auto LPTM = lhs.castAs<nonloc::PointerToMember>(),
448 RPTM = rhs.castAs<nonloc::PointerToMember>();
449 auto LPTMD = LPTM.getPTMData(), RPTMD = RPTM.getPTMData();
450 switch (op) {
451 case BO_EQ:
452 return makeTruthVal(b: LPTMD == RPTMD, type: resultTy);
453 case BO_NE:
454 return makeTruthVal(b: LPTMD != RPTMD, type: resultTy);
455 default:
456 return UnknownVal();
457 }
458 }
459 case nonloc::LocAsIntegerKind: {
460 Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
461 switch (rhs.getKind()) {
462 case nonloc::LocAsIntegerKind:
463 // FIXME: at the moment the implementation
464 // of modeling "pointers as integers" is not complete.
465 if (!BinaryOperator::isComparisonOp(Opc: op))
466 return UnknownVal();
467 return evalBinOpLL(state, op, lhs: lhsL,
468 rhs: rhs.castAs<nonloc::LocAsInteger>().getLoc(),
469 resultTy);
470 case nonloc::ConcreteIntKind: {
471 // FIXME: at the moment the implementation
472 // of modeling "pointers as integers" is not complete.
473 if (!BinaryOperator::isComparisonOp(Opc: op))
474 return UnknownVal();
475 // Transform the integer into a location and compare.
476 // FIXME: This only makes sense for comparisons. If we want to, say,
477 // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it,
478 // then pack it back into a LocAsInteger.
479 llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
480 // If the region has a symbolic base, pay attention to the type; it
481 // might be coming from a non-default address space. For non-symbolic
482 // regions it doesn't matter that much because such comparisons would
483 // most likely evaluate to concrete false anyway. FIXME: We might
484 // still need to handle the non-comparison case.
485 if (SymbolRef lSym = lhs.getAsLocSymbol(IncludeBaseRegions: true))
486 BasicVals.getAPSIntType(T: lSym->getType()).apply(Value&: i);
487 else
488 BasicVals.getAPSIntType(T: Context.VoidPtrTy).apply(Value&: i);
489 return evalBinOpLL(state, op, lhs: lhsL, rhs: makeLoc(integer: i), resultTy);
490 }
491 default:
492 switch (op) {
493 case BO_EQ:
494 return makeTruthVal(b: false, type: resultTy);
495 case BO_NE:
496 return makeTruthVal(b: true, type: resultTy);
497 default:
498 // This case also handles pointer arithmetic.
499 return makeSymExprValNN(op, lhs: InputLHS, rhs: InputRHS, resultTy);
500 }
501 }
502 }
503 case nonloc::ConcreteIntKind: {
504 llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue();
505
506 // If we're dealing with two known constants, just perform the operation.
507 if (const llvm::APSInt *KnownRHSValue = getConstValue(state, V: rhs)) {
508 llvm::APSInt RHSValue = *KnownRHSValue;
509 if (BinaryOperator::isComparisonOp(Opc: op)) {
510 // We're looking for a type big enough to compare the two values.
511 // FIXME: This is not correct. char + short will result in a promotion
512 // to int. Unfortunately we have lost types by this point.
513 APSIntType CompareType = std::max(a: APSIntType(LHSValue),
514 b: APSIntType(RHSValue));
515 CompareType.apply(Value&: LHSValue);
516 CompareType.apply(Value&: RHSValue);
517 } else if (!BinaryOperator::isShiftOp(Opc: op)) {
518 APSIntType IntType = BasicVals.getAPSIntType(T: resultTy);
519 IntType.apply(Value&: LHSValue);
520 IntType.apply(Value&: RHSValue);
521 }
522
523 std::optional<APSIntPtr> Result =
524 BasicVals.evalAPSInt(Op: op, V1: LHSValue, V2: RHSValue);
525 if (!Result) {
526 if (op == BO_Shl || op == BO_Shr) {
527 // FIXME: At this point the constant folding claims that the result
528 // of a bitwise shift is undefined. However, constant folding
529 // relies on the inaccurate type information that is stored in the
530 // bit size of APSInt objects, and if we reached this point, then
531 // the checker core.BitwiseShift already determined that the shift
532 // is valid (in a PreStmt callback, by querying the real type from
533 // the AST node).
534 // To avoid embarrassing false positives, let's just say that we
535 // don't know anything about the result of the shift.
536 return UnknownVal();
537 }
538 return UndefinedVal();
539 }
540
541 return nonloc::ConcreteInt(*Result);
542 }
543
544 // Swap the left and right sides and flip the operator if doing so
545 // allows us to better reason about the expression (this is a form
546 // of expression canonicalization).
547 // While we're at it, catch some special cases for non-commutative ops.
548 switch (op) {
549 case BO_LT:
550 case BO_GT:
551 case BO_LE:
552 case BO_GE:
553 op = BinaryOperator::reverseComparisonOp(Opc: op);
554 [[fallthrough]];
555 case BO_EQ:
556 case BO_NE:
557 case BO_Add:
558 case BO_Mul:
559 case BO_And:
560 case BO_Xor:
561 case BO_Or:
562 std::swap(a&: lhs, b&: rhs);
563 continue;
564 case BO_Shr:
565 // (~0)>>a
566 if (LHSValue.isAllOnes() && LHSValue.isSigned())
567 return evalCast(V: lhs, CastTy: resultTy, OriginalTy: QualType{});
568 [[fallthrough]];
569 case BO_Shl:
570 // 0<<a and 0>>a
571 if (LHSValue == 0)
572 return evalCast(V: lhs, CastTy: resultTy, OriginalTy: QualType{});
573 return makeSymExprValNN(op, lhs: InputLHS, rhs: InputRHS, resultTy);
574 case BO_Div:
575 // 0 / x == 0
576 case BO_Rem:
577 // 0 % x == 0
578 if (LHSValue == 0)
579 return makeZeroVal(type: resultTy);
580 [[fallthrough]];
581 default:
582 return makeSymExprValNN(op, lhs: InputLHS, rhs: InputRHS, resultTy);
583 }
584 }
585 case nonloc::SymbolValKind: {
586 // We only handle LHS as simple symbols or SymIntExprs.
587 SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol();
588
589 // LHS is a symbolic expression.
590 if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Val: Sym)) {
591
592 // Is this a logical not? (!x is represented as x == 0.)
593 if (op == BO_EQ && rhs.isZeroConstant()) {
594 // We know how to negate certain expressions. Simplify them here.
595
596 BinaryOperator::Opcode opc = symIntExpr->getOpcode();
597 switch (opc) {
598 default:
599 // We don't know how to negate this operation.
600 // Just handle it as if it were a normal comparison to 0.
601 break;
602 case BO_LAnd:
603 case BO_LOr:
604 llvm_unreachable("Logical operators handled by branching logic.");
605 case BO_Assign:
606 case BO_MulAssign:
607 case BO_DivAssign:
608 case BO_RemAssign:
609 case BO_AddAssign:
610 case BO_SubAssign:
611 case BO_ShlAssign:
612 case BO_ShrAssign:
613 case BO_AndAssign:
614 case BO_XorAssign:
615 case BO_OrAssign:
616 case BO_Comma:
617 llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
618 case BO_PtrMemD:
619 case BO_PtrMemI:
620 llvm_unreachable("Pointer arithmetic not handled here.");
621 case BO_LT:
622 case BO_GT:
623 case BO_LE:
624 case BO_GE:
625 case BO_EQ:
626 case BO_NE:
627 assert(resultTy->isBooleanType() ||
628 resultTy == getConditionType());
629 assert(symIntExpr->getType()->isBooleanType() ||
630 getContext().hasSameUnqualifiedType(symIntExpr->getType(),
631 getConditionType()));
632 // Negate the comparison and make a value.
633 opc = BinaryOperator::negateComparisonOp(Opc: opc);
634 return makeNonLoc(lhs: symIntExpr->getLHS(), op: opc,
635 rhs: symIntExpr->getRHS(), type: resultTy);
636 }
637 }
638
639 // For now, only handle expressions whose RHS is a constant.
640 if (const llvm::APSInt *RHSValue = getConstValue(state, V: rhs)) {
641 // If both the LHS and the current expression are additive,
642 // fold their constants and try again.
643 if (BinaryOperator::isAdditiveOp(Opc: op)) {
644 BinaryOperator::Opcode lop = symIntExpr->getOpcode();
645 if (BinaryOperator::isAdditiveOp(Opc: lop)) {
646 // Convert the two constants to a common type, then combine them.
647
648 // resultTy may not be the best type to convert to, but it's
649 // probably the best choice in expressions with mixed type
650 // (such as x+1U+2LL). The rules for implicit conversions should
651 // choose a reasonable type to preserve the expression, and will
652 // at least match how the value is going to be used.
653 APSIntType IntType = BasicVals.getAPSIntType(T: resultTy);
654 const llvm::APSInt &first = IntType.convert(Value: symIntExpr->getRHS());
655 const llvm::APSInt &second = IntType.convert(Value: *RHSValue);
656
657 // If the op and lop agrees, then we just need to
658 // sum the constants. Otherwise, we change to operation
659 // type if substraction would produce negative value
660 // (and cause overflow for unsigned integers),
661 // as consequence x+1U-10 produces x-9U, instead
662 // of x+4294967287U, that would be produced without this
663 // additional check.
664 std::optional<APSIntPtr> newRHS;
665 if (lop == op) {
666 newRHS = BasicVals.evalAPSInt(Op: BO_Add, V1: first, V2: second);
667 } else if (first >= second) {
668 newRHS = BasicVals.evalAPSInt(Op: BO_Sub, V1: first, V2: second);
669 op = lop;
670 } else {
671 newRHS = BasicVals.evalAPSInt(Op: BO_Sub, V1: second, V2: first);
672 }
673
674 assert(newRHS && "Invalid operation despite common type!");
675 rhs = nonloc::ConcreteInt(*newRHS);
676 lhs = nonloc::SymbolVal(symIntExpr->getLHS());
677 continue;
678 }
679 }
680
681 // Otherwise, make a SymIntExpr out of the expression.
682 return MakeSymIntVal(LHS: symIntExpr, op, RHS: *RHSValue, resultTy);
683 }
684 }
685
686 // Is the RHS a constant?
687 if (const llvm::APSInt *RHSValue = getConstValue(state, V: rhs))
688 return MakeSymIntVal(LHS: Sym, op, RHS: *RHSValue, resultTy);
689
690 if (std::optional<NonLoc> V = tryRearrange(State: state, Op: op, Lhs: lhs, Rhs: rhs, ResultTy: resultTy))
691 return *V;
692
693 // Give up -- this is not a symbolic expression we can handle.
694 return makeSymExprValNN(op, lhs: InputLHS, rhs: InputRHS, resultTy);
695 }
696 }
697 }
698}
699
700static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR,
701 const FieldRegion *RightFR,
702 BinaryOperator::Opcode op,
703 QualType resultTy,
704 SimpleSValBuilder &SVB) {
705 // Only comparisons are meaningful here!
706 if (!BinaryOperator::isComparisonOp(Opc: op))
707 return UnknownVal();
708
709 // Next, see if the two FRs have the same super-region.
710 // FIXME: This doesn't handle casts yet, and simply stripping the casts
711 // doesn't help.
712 if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
713 return UnknownVal();
714
715 const FieldDecl *LeftFD = LeftFR->getDecl();
716 const FieldDecl *RightFD = RightFR->getDecl();
717 const RecordDecl *RD = LeftFD->getParent();
718
719 // Make sure the two FRs are from the same kind of record. Just in case!
720 // FIXME: This is probably where inheritance would be a problem.
721 if (RD != RightFD->getParent())
722 return UnknownVal();
723
724 // We know for sure that the two fields are not the same, since that
725 // would have given us the same SVal.
726 if (op == BO_EQ)
727 return SVB.makeTruthVal(b: false, type: resultTy);
728 if (op == BO_NE)
729 return SVB.makeTruthVal(b: true, type: resultTy);
730
731 // Iterate through the fields and see which one comes first.
732 // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
733 // members and the units in which bit-fields reside have addresses that
734 // increase in the order in which they are declared."
735 bool leftFirst = (op == BO_LT || op == BO_LE);
736 for (const auto *I : RD->fields()) {
737 if (I == LeftFD)
738 return SVB.makeTruthVal(b: leftFirst, type: resultTy);
739 if (I == RightFD)
740 return SVB.makeTruthVal(b: !leftFirst, type: resultTy);
741 }
742
743 llvm_unreachable("Fields not found in parent record's definition");
744}
745
746// This is used in debug builds only for now because some downstream users
747// may hit this assert in their subsequent merges.
748// There are still places in the analyzer where equal bitwidth Locs
749// are compared, and need to be found and corrected. Recent previous fixes have
750// addressed the known problems of making NULLs with specific bitwidths
751// for Loc comparisons along with deprecation of APIs for the same purpose.
752//
753static void assertEqualBitWidths(ProgramStateRef State, Loc RhsLoc,
754 Loc LhsLoc) {
755 // Implements a "best effort" check for RhsLoc and LhsLoc bit widths
756 ASTContext &Ctx = State->getStateManager().getContext();
757 uint64_t RhsBitwidth =
758 RhsLoc.getType(Ctx).isNull() ? 0 : Ctx.getTypeSize(T: RhsLoc.getType(Ctx));
759 uint64_t LhsBitwidth =
760 LhsLoc.getType(Ctx).isNull() ? 0 : Ctx.getTypeSize(T: LhsLoc.getType(Ctx));
761 if (RhsBitwidth && LhsBitwidth && (LhsLoc.getKind() == RhsLoc.getKind())) {
762 assert(RhsBitwidth == LhsBitwidth &&
763 "RhsLoc and LhsLoc bitwidth must be same!");
764 }
765}
766
767// FIXME: all this logic will change if/when we have MemRegion::getLocation().
768SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
769 BinaryOperator::Opcode op,
770 Loc lhs, Loc rhs,
771 QualType resultTy) {
772
773 // Assert that bitwidth of lhs and rhs are the same.
774 // This can happen if two different address spaces are used,
775 // and the bitwidths of the address spaces are different.
776 // See LIT case clang/test/Analysis/cstring-checker-addressspace.c
777 // FIXME: See comment above in the function assertEqualBitWidths
778 assertEqualBitWidths(State: state, RhsLoc: rhs, LhsLoc: lhs);
779
780 // Only comparisons and subtractions are valid operations on two pointers.
781 // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
782 // However, if a pointer is casted to an integer, evalBinOpNN may end up
783 // calling this function with another operation (PR7527). We don't attempt to
784 // model this for now, but it could be useful, particularly when the
785 // "location" is actually an integer value that's been passed through a void*.
786 if (!(BinaryOperator::isComparisonOp(Opc: op) || op == BO_Sub))
787 return UnknownVal();
788
789 // Special cases for when both sides are identical.
790 if (lhs == rhs) {
791 switch (op) {
792 default:
793 llvm_unreachable("Unimplemented operation for two identical values");
794 case BO_Sub:
795 return makeZeroVal(type: resultTy);
796 case BO_EQ:
797 case BO_LE:
798 case BO_GE:
799 return makeTruthVal(b: true, type: resultTy);
800 case BO_NE:
801 case BO_LT:
802 case BO_GT:
803 return makeTruthVal(b: false, type: resultTy);
804 }
805 }
806
807 switch (lhs.getKind()) {
808 default:
809 llvm_unreachable("Ordering not implemented for this Loc.");
810
811 case loc::GotoLabelKind:
812 // The only thing we know about labels is that they're non-null.
813 if (rhs.isZeroConstant()) {
814 switch (op) {
815 default:
816 break;
817 case BO_Sub:
818 return evalCast(V: lhs, CastTy: resultTy, OriginalTy: QualType{});
819 case BO_EQ:
820 case BO_LE:
821 case BO_LT:
822 return makeTruthVal(b: false, type: resultTy);
823 case BO_NE:
824 case BO_GT:
825 case BO_GE:
826 return makeTruthVal(b: true, type: resultTy);
827 }
828 }
829 // There may be two labels for the same location, and a function region may
830 // have the same address as a label at the start of the function (depending
831 // on the ABI).
832 // FIXME: we can probably do a comparison against other MemRegions, though.
833 // FIXME: is there a way to tell if two labels refer to the same location?
834 return UnknownVal();
835
836 case loc::ConcreteIntKind: {
837 auto L = lhs.castAs<loc::ConcreteInt>();
838
839 // If one of the operands is a symbol and the other is a constant,
840 // build an expression for use by the constraint manager.
841 if (SymbolRef rSym = rhs.getAsLocSymbol(IncludeBaseRegions: true)) {
842 if (op == BO_Cmp)
843 return UnknownVal();
844
845 if (!BinaryOperator::isComparisonOp(Opc: op))
846 return makeNonLoc(rhs: L.getValue(), op, lhs: rSym, type: resultTy);
847
848 op = BinaryOperator::reverseComparisonOp(Opc: op);
849 return makeNonLoc(lhs: rSym, op, rhs: L.getValue(), type: resultTy);
850 }
851
852 // If both operands are constants, just perform the operation.
853 if (std::optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
854 assert(BinaryOperator::isComparisonOp(op) || op == BO_Sub);
855
856 if (std::optional<APSIntPtr> ResultInt =
857 BasicVals.evalAPSInt(Op: op, V1: L.getValue(), V2: rInt->getValue()))
858 return evalCast(V: nonloc::ConcreteInt(*ResultInt), CastTy: resultTy, OriginalTy: QualType{});
859 return UnknownVal();
860 }
861
862 // Special case comparisons against NULL.
863 // This must come after the test if the RHS is a symbol, which is used to
864 // build constraints. The address of any non-symbolic region is guaranteed
865 // to be non-NULL, as is any label.
866 assert((isa<loc::MemRegionVal, loc::GotoLabel>(rhs)));
867 if (lhs.isZeroConstant()) {
868 switch (op) {
869 default:
870 break;
871 case BO_EQ:
872 case BO_GT:
873 case BO_GE:
874 return makeTruthVal(b: false, type: resultTy);
875 case BO_NE:
876 case BO_LT:
877 case BO_LE:
878 return makeTruthVal(b: true, type: resultTy);
879 }
880 }
881
882 // Comparing an arbitrary integer to a region or label address is
883 // completely unknowable.
884 return UnknownVal();
885 }
886 case loc::MemRegionValKind: {
887 if (std::optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
888 // If one of the operands is a symbol and the other is a constant,
889 // build an expression for use by the constraint manager.
890 if (SymbolRef lSym = lhs.getAsLocSymbol(IncludeBaseRegions: true)) {
891 if (BinaryOperator::isComparisonOp(Opc: op))
892 return MakeSymIntVal(LHS: lSym, op, RHS: rInt->getValue(), resultTy);
893 return UnknownVal();
894 }
895 // Special case comparisons to NULL.
896 // This must come after the test if the LHS is a symbol, which is used to
897 // build constraints. The address of any non-symbolic region is guaranteed
898 // to be non-NULL.
899 if (rInt->isZeroConstant()) {
900 if (op == BO_Sub)
901 return evalCast(V: lhs, CastTy: resultTy, OriginalTy: QualType{});
902
903 if (BinaryOperator::isComparisonOp(Opc: op)) {
904 QualType boolType = getContext().BoolTy;
905 NonLoc l = evalCast(V: lhs, CastTy: boolType, OriginalTy: QualType{}).castAs<NonLoc>();
906 NonLoc r = makeTruthVal(b: false, type: boolType).castAs<NonLoc>();
907 return evalBinOpNN(state, op, lhs: l, rhs: r, resultTy);
908 }
909 }
910
911 // Comparing a region to an arbitrary integer is completely unknowable.
912 return UnknownVal();
913 }
914
915 // Get both values as regions, if possible.
916 const MemRegion *LeftMR = lhs.getAsRegion();
917 assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");
918
919 const MemRegion *RightMR = rhs.getAsRegion();
920 if (!RightMR)
921 // The RHS is probably a label, which in theory could address a region.
922 // FIXME: we can probably make a more useful statement about non-code
923 // regions, though.
924 return UnknownVal();
925
926 const MemRegion *LeftBase = LeftMR->getBaseRegion();
927 const MemRegion *RightBase = RightMR->getBaseRegion();
928 const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace(State: state);
929 const MemSpaceRegion *RightMS = RightBase->getMemorySpace(State: state);
930 const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
931
932 // Two regions from different known memory spaces cannot be equal.
933 if (LeftMS != RightMS && LeftMS != UnknownMS && RightMS != UnknownMS) {
934 switch (op) {
935 default:
936 return UnknownVal();
937 case BO_EQ:
938 return makeTruthVal(b: false, type: resultTy);
939 case BO_NE:
940 return makeTruthVal(b: true, type: resultTy);
941 }
942 }
943
944 // If both values wrap regions, see if they're from different base regions.
945 // Note, heap base symbolic regions are assumed to not alias with
946 // each other; for example, we assume that malloc returns different address
947 // on each invocation.
948 // FIXME: ObjC object pointers always reside on the heap, but currently
949 // we treat their memory space as unknown, because symbolic pointers
950 // to ObjC objects may alias. There should be a way to construct
951 // possibly-aliasing heap-based regions. For instance, MacOSXApiChecker
952 // guesses memory space for ObjC object pointers manually instead of
953 // relying on us.
954 if (LeftBase != RightBase &&
955 ((!isa<SymbolicRegion>(Val: LeftBase) && !isa<SymbolicRegion>(Val: RightBase)) ||
956 (isa<HeapSpaceRegion>(Val: LeftMS) || isa<HeapSpaceRegion>(Val: RightMS))) ){
957 switch (op) {
958 default:
959 return UnknownVal();
960 case BO_EQ:
961 return makeTruthVal(b: false, type: resultTy);
962 case BO_NE:
963 return makeTruthVal(b: true, type: resultTy);
964 }
965 }
966
967 // Handle special cases for when both regions are element regions.
968 const ElementRegion *RightER = dyn_cast<ElementRegion>(Val: RightMR);
969 const ElementRegion *LeftER = dyn_cast<ElementRegion>(Val: LeftMR);
970 if (RightER && LeftER) {
971 // Next, see if the two ERs have the same super-region and matching types.
972 // FIXME: This should do something useful even if the types don't match,
973 // though if both indexes are constant the RegionRawOffset path will
974 // give the correct answer.
975 if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
976 LeftER->getElementType() == RightER->getElementType()) {
977 // Get the left index and cast it to the correct type.
978 // If the index is unknown or undefined, bail out here.
979 SVal LeftIndexVal = LeftER->getIndex();
980 std::optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
981 if (!LeftIndex)
982 return UnknownVal();
983 LeftIndexVal = evalCast(V: *LeftIndex, CastTy: ArrayIndexTy, OriginalTy: QualType{});
984 LeftIndex = LeftIndexVal.getAs<NonLoc>();
985 if (!LeftIndex)
986 return UnknownVal();
987
988 // Do the same for the right index.
989 SVal RightIndexVal = RightER->getIndex();
990 std::optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
991 if (!RightIndex)
992 return UnknownVal();
993 RightIndexVal = evalCast(V: *RightIndex, CastTy: ArrayIndexTy, OriginalTy: QualType{});
994 RightIndex = RightIndexVal.getAs<NonLoc>();
995 if (!RightIndex)
996 return UnknownVal();
997
998 // Actually perform the operation.
999 // evalBinOpNN expects the two indexes to already be the right type.
1000 return evalBinOpNN(state, op, lhs: *LeftIndex, rhs: *RightIndex, resultTy);
1001 }
1002 }
1003
1004 // Special handling of the FieldRegions, even with symbolic offsets.
1005 const FieldRegion *RightFR = dyn_cast<FieldRegion>(Val: RightMR);
1006 const FieldRegion *LeftFR = dyn_cast<FieldRegion>(Val: LeftMR);
1007 if (RightFR && LeftFR) {
1008 SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
1009 SVB&: *this);
1010 if (!R.isUnknown())
1011 return R;
1012 }
1013
1014 // Compare the regions using the raw offsets.
1015 RegionOffset LeftOffset = LeftMR->getAsOffset();
1016 RegionOffset RightOffset = RightMR->getAsOffset();
1017
1018 if (LeftOffset.getRegion() != nullptr &&
1019 LeftOffset.getRegion() == RightOffset.getRegion() &&
1020 !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) {
1021 int64_t left = LeftOffset.getOffset();
1022 int64_t right = RightOffset.getOffset();
1023
1024 switch (op) {
1025 default:
1026 return UnknownVal();
1027 case BO_LT:
1028 return makeTruthVal(b: left < right, type: resultTy);
1029 case BO_GT:
1030 return makeTruthVal(b: left > right, type: resultTy);
1031 case BO_LE:
1032 return makeTruthVal(b: left <= right, type: resultTy);
1033 case BO_GE:
1034 return makeTruthVal(b: left >= right, type: resultTy);
1035 case BO_EQ:
1036 return makeTruthVal(b: left == right, type: resultTy);
1037 case BO_NE:
1038 return makeTruthVal(b: left != right, type: resultTy);
1039 }
1040 }
1041
1042 // At this point we're not going to get a good answer, but we can try
1043 // conjuring an expression instead.
1044 SymbolRef LHSSym = lhs.getAsLocSymbol();
1045 SymbolRef RHSSym = rhs.getAsLocSymbol();
1046 if (LHSSym && RHSSym)
1047 return makeNonLoc(lhs: LHSSym, op, rhs: RHSSym, type: resultTy);
1048
1049 // If we get here, we have no way of comparing the regions.
1050 return UnknownVal();
1051 }
1052 }
1053}
1054
1055SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
1056 BinaryOperator::Opcode op, Loc lhs,
1057 NonLoc rhs, QualType resultTy) {
1058 if (op >= BO_PtrMemD && op <= BO_PtrMemI) {
1059 if (auto PTMSV = rhs.getAs<nonloc::PointerToMember>()) {
1060 if (PTMSV->isNullMemberPointer())
1061 return UndefinedVal();
1062
1063 auto getFieldLValue = [&](const auto *FD) -> SVal {
1064 SVal Result = lhs;
1065
1066 for (const auto &I : *PTMSV)
1067 Result = StateMgr.getStoreManager().evalDerivedToBase(
1068 Derived: Result, DerivedPtrType: I->getType(), IsVirtual: I->isVirtual());
1069
1070 return state->getLValue(FD, Result);
1071 };
1072
1073 if (const auto *FD = PTMSV->getDeclAs<FieldDecl>()) {
1074 return getFieldLValue(FD);
1075 }
1076 if (const auto *FD = PTMSV->getDeclAs<IndirectFieldDecl>()) {
1077 return getFieldLValue(FD);
1078 }
1079 }
1080
1081 return rhs;
1082 }
1083
1084 assert(!BinaryOperator::isComparisonOp(op) &&
1085 "arguments to comparison ops must be of the same type");
1086
1087 SVal simplifiedRhs = simplifySVal(State: state, V: rhs);
1088 if (auto simplifiedRhsAsNonLoc = simplifiedRhs.getAs<NonLoc>())
1089 rhs = *simplifiedRhsAsNonLoc;
1090
1091 // Special case: rhs is a zero constant.
1092 if (rhs.isZeroConstant())
1093 return lhs;
1094
1095 // Perserve the null pointer so that it can be found by the DerefChecker.
1096 if (lhs.isZeroConstant())
1097 return lhs;
1098
1099 // We are dealing with pointer arithmetic.
1100
1101 // Handle pointer arithmetic on constant values.
1102 if (std::optional<nonloc::ConcreteInt> rhsInt =
1103 rhs.getAs<nonloc::ConcreteInt>()) {
1104 if (std::optional<loc::ConcreteInt> lhsInt =
1105 lhs.getAs<loc::ConcreteInt>()) {
1106 const llvm::APSInt &leftI = lhsInt->getValue();
1107 assert(leftI.isUnsigned());
1108 llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
1109
1110 // Convert the bitwidth of rightI. This should deal with overflow
1111 // since we are dealing with concrete values.
1112 rightI = rightI.extOrTrunc(width: leftI.getBitWidth());
1113
1114 // Offset the increment by the pointer size.
1115 llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
1116 QualType pointeeType = resultTy->getPointeeType();
1117 Multiplicand = getContext().getTypeSizeInChars(T: pointeeType).getQuantity();
1118 rightI *= Multiplicand;
1119
1120 // Compute the adjusted pointer.
1121 switch (op) {
1122 case BO_Add:
1123 rightI = leftI + rightI;
1124 break;
1125 case BO_Sub:
1126 rightI = leftI - rightI;
1127 break;
1128 default:
1129 llvm_unreachable("Invalid pointer arithmetic operation");
1130 }
1131 return loc::ConcreteInt(getBasicValueFactory().getValue(X: rightI));
1132 }
1133 }
1134
1135 // Handle cases where 'lhs' is a region.
1136 if (const MemRegion *region = lhs.getAsRegion()) {
1137 rhs = convertToArrayIndex(val: rhs).castAs<NonLoc>();
1138 SVal index = UnknownVal();
1139 const SubRegion *superR = nullptr;
1140 // We need to know the type of the pointer in order to add an integer to it.
1141 // Depending on the type, different amount of bytes is added.
1142 QualType elementType;
1143
1144 if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(Val: region)) {
1145 assert(op == BO_Add || op == BO_Sub);
1146 index = evalBinOpNN(state, op, lhs: elemReg->getIndex(), rhs,
1147 resultTy: getArrayIndexType());
1148 superR = cast<SubRegion>(Val: elemReg->getSuperRegion());
1149 elementType = elemReg->getElementType();
1150 }
1151 else if (isa<SubRegion>(Val: region)) {
1152 assert(op == BO_Add || op == BO_Sub);
1153 index = (op == BO_Add) ? rhs : evalMinus(val: rhs);
1154 superR = cast<SubRegion>(Val: region);
1155 // TODO: Is this actually reliable? Maybe improving our MemRegion
1156 // hierarchy to provide typed regions for all non-void pointers would be
1157 // better. For instance, we cannot extend this towards LocAsInteger
1158 // operations, where result type of the expression is integer.
1159 if (resultTy->isAnyPointerType())
1160 elementType = resultTy->getPointeeType();
1161 }
1162
1163 // Represent arithmetic on void pointers as arithmetic on char pointers.
1164 // It is fine when a TypedValueRegion of char value type represents
1165 // a void pointer. Note that arithmetic on void pointers is a GCC extension.
1166 if (elementType->isVoidType())
1167 elementType = getContext().CharTy;
1168
1169 if (std::optional<NonLoc> indexV = index.getAs<NonLoc>()) {
1170 return loc::MemRegionVal(MemMgr.getElementRegion(elementType, Idx: *indexV,
1171 superRegion: superR, Ctx: getContext()));
1172 }
1173 }
1174 return UnknownVal();
1175}
1176
1177const llvm::APSInt *SimpleSValBuilder::getConstValue(ProgramStateRef state,
1178 SVal V) {
1179 if (const llvm::APSInt *Res = getConcreteValue(V))
1180 return Res;
1181
1182 if (SymbolRef Sym = V.getAsSymbol())
1183 return state->getConstraintManager().getSymVal(state, sym: Sym);
1184
1185 return nullptr;
1186}
1187
1188const llvm::APSInt *SimpleSValBuilder::getConcreteValue(SVal V) {
1189 if (std::optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
1190 return X->getValue().get();
1191
1192 if (std::optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
1193 return X->getValue().get();
1194
1195 return nullptr;
1196}
1197
1198const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
1199 SVal V) {
1200 return getConstValue(state, V: simplifySVal(State: state, V));
1201}
1202
1203const llvm::APSInt *SimpleSValBuilder::getMinValue(ProgramStateRef state,
1204 SVal V) {
1205 V = simplifySVal(State: state, V);
1206
1207 if (const llvm::APSInt *Res = getConcreteValue(V))
1208 return Res;
1209
1210 if (SymbolRef Sym = V.getAsSymbol())
1211 return state->getConstraintManager().getSymMinVal(state, sym: Sym);
1212
1213 return nullptr;
1214}
1215
1216const llvm::APSInt *SimpleSValBuilder::getMaxValue(ProgramStateRef state,
1217 SVal V) {
1218 V = simplifySVal(State: state, V);
1219
1220 if (const llvm::APSInt *Res = getConcreteValue(V))
1221 return Res;
1222
1223 if (SymbolRef Sym = V.getAsSymbol())
1224 return state->getConstraintManager().getSymMaxVal(state, sym: Sym);
1225
1226 return nullptr;
1227}
1228
1229SVal SimpleSValBuilder::simplifyUntilFixpoint(ProgramStateRef State, SVal Val) {
1230 SVal SimplifiedVal = simplifySValOnce(State, V: Val);
1231 while (SimplifiedVal != Val) {
1232 Val = SimplifiedVal;
1233 SimplifiedVal = simplifySValOnce(State, V: Val);
1234 }
1235 return SimplifiedVal;
1236}
1237
1238SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
1239 return simplifyUntilFixpoint(State, Val: V);
1240}
1241
1242SVal SimpleSValBuilder::simplifySValOnce(ProgramStateRef State, SVal V) {
1243 // For now, this function tries to constant-fold symbols inside a
1244 // nonloc::SymbolVal, and does nothing else. More simplifications should
1245 // be possible, such as constant-folding an index in an ElementRegion.
1246
1247 class Simplifier : public FullSValVisitor<Simplifier, SVal> {
1248 ProgramStateRef State;
1249 SValBuilder &SVB;
1250
1251 // Cache results for the lifetime of the Simplifier. Results change every
1252 // time new constraints are added to the program state, which is the whole
1253 // point of simplifying, and for that very reason it's pointless to maintain
1254 // the same cache for the duration of the whole analysis.
1255 llvm::DenseMap<SymbolRef, SVal> Cached;
1256
1257 static bool isUnchanged(SymbolRef Sym, SVal Val) {
1258 return Sym == Val.getAsSymbol();
1259 }
1260
1261 SVal cache(SymbolRef Sym, SVal V) {
1262 Cached[Sym] = V;
1263 return V;
1264 }
1265
1266 SVal skip(SymbolRef Sym) {
1267 return cache(Sym, V: SVB.makeSymbolVal(Sym));
1268 }
1269
1270 // Return the known const value for the Sym if available, or return Undef
1271 // otherwise.
1272 SVal getConst(SymbolRef Sym) {
1273 const llvm::APSInt *Const =
1274 State->getConstraintManager().getSymVal(state: State, sym: Sym);
1275 if (Const)
1276 return Loc::isLocType(T: Sym->getType()) ? (SVal)SVB.makeIntLocVal(integer: *Const)
1277 : (SVal)SVB.makeIntVal(integer: *Const);
1278 return UndefinedVal();
1279 }
1280
1281 SVal getConstOrVisit(SymbolRef Sym) {
1282 const SVal Ret = getConst(Sym);
1283 if (Ret.isUndef())
1284 return Visit(S: Sym);
1285 return Ret;
1286 }
1287
1288 public:
1289 Simplifier(ProgramStateRef State)
1290 : State(State), SVB(State->getStateManager().getSValBuilder()) {}
1291
1292 SVal VisitSymbolData(const SymbolData *S) {
1293 // No cache here.
1294 if (const llvm::APSInt *I =
1295 State->getConstraintManager().getSymVal(state: State, sym: S))
1296 return Loc::isLocType(T: S->getType()) ? (SVal)SVB.makeIntLocVal(integer: *I)
1297 : (SVal)SVB.makeIntVal(integer: *I);
1298 return SVB.makeSymbolVal(Sym: S);
1299 }
1300
1301 SVal VisitSymIntExpr(const SymIntExpr *S) {
1302 auto I = Cached.find(Val: S);
1303 if (I != Cached.end())
1304 return I->second;
1305
1306 SVal LHS = getConstOrVisit(Sym: S->getLHS());
1307 if (isUnchanged(Sym: S->getLHS(), Val: LHS))
1308 return skip(Sym: S);
1309
1310 SVal RHS;
1311 // By looking at the APSInt in the right-hand side of S, we cannot
1312 // figure out if it should be treated as a Loc or as a NonLoc.
1313 // So make our guess by recalling that we cannot multiply pointers
1314 // or compare a pointer to an integer.
1315 if (Loc::isLocType(T: S->getLHS()->getType()) &&
1316 BinaryOperator::isComparisonOp(Opc: S->getOpcode())) {
1317 // The usual conversion of $sym to &SymRegion{$sym}, as they have
1318 // the same meaning for Loc-type symbols, but the latter form
1319 // is preferred in SVal computations for being Loc itself.
1320 if (SymbolRef Sym = LHS.getAsSymbol()) {
1321 assert(Loc::isLocType(Sym->getType()));
1322 LHS = SVB.makeLoc(sym: Sym);
1323 }
1324 RHS = SVB.makeIntLocVal(integer: S->getRHS());
1325 } else {
1326 RHS = SVB.makeIntVal(integer: S->getRHS());
1327 }
1328
1329 return cache(
1330 Sym: S, V: SVB.evalBinOp(state: State, op: S->getOpcode(), lhs: LHS, rhs: RHS, type: S->getType()));
1331 }
1332
1333 SVal VisitIntSymExpr(const IntSymExpr *S) {
1334 auto I = Cached.find(Val: S);
1335 if (I != Cached.end())
1336 return I->second;
1337
1338 SVal RHS = getConstOrVisit(Sym: S->getRHS());
1339 if (isUnchanged(Sym: S->getRHS(), Val: RHS))
1340 return skip(Sym: S);
1341
1342 SVal LHS = SVB.makeIntVal(integer: S->getLHS());
1343 return cache(
1344 Sym: S, V: SVB.evalBinOp(state: State, op: S->getOpcode(), lhs: LHS, rhs: RHS, type: S->getType()));
1345 }
1346
1347 SVal VisitSymSymExpr(const SymSymExpr *S) {
1348 auto I = Cached.find(Val: S);
1349 if (I != Cached.end())
1350 return I->second;
1351
1352 // For now don't try to simplify mixed Loc/NonLoc expressions
1353 // because they often appear from LocAsInteger operations
1354 // and we don't know how to combine a LocAsInteger
1355 // with a concrete value.
1356 if (Loc::isLocType(T: S->getLHS()->getType()) !=
1357 Loc::isLocType(T: S->getRHS()->getType()))
1358 return skip(Sym: S);
1359
1360 SVal LHS = getConstOrVisit(Sym: S->getLHS());
1361 SVal RHS = getConstOrVisit(Sym: S->getRHS());
1362
1363 if (isUnchanged(Sym: S->getLHS(), Val: LHS) && isUnchanged(Sym: S->getRHS(), Val: RHS))
1364 return skip(Sym: S);
1365
1366 return cache(
1367 Sym: S, V: SVB.evalBinOp(state: State, op: S->getOpcode(), lhs: LHS, rhs: RHS, type: S->getType()));
1368 }
1369
1370 SVal VisitSymbolCast(const SymbolCast *S) {
1371 auto I = Cached.find(Val: S);
1372 if (I != Cached.end())
1373 return I->second;
1374 const SymExpr *OpSym = S->getOperand();
1375 SVal OpVal = getConstOrVisit(Sym: OpSym);
1376 if (isUnchanged(Sym: OpSym, Val: OpVal))
1377 return skip(Sym: S);
1378
1379 return cache(Sym: S, V: SVB.evalCast(V: OpVal, CastTy: S->getType(), OriginalTy: OpSym->getType()));
1380 }
1381
1382 SVal VisitUnarySymExpr(const UnarySymExpr *S) {
1383 auto I = Cached.find(Val: S);
1384 if (I != Cached.end())
1385 return I->second;
1386 SVal Op = getConstOrVisit(Sym: S->getOperand());
1387 if (isUnchanged(Sym: S->getOperand(), Val: Op))
1388 return skip(Sym: S);
1389
1390 return cache(
1391 Sym: S, V: SVB.evalUnaryOp(state: State, opc: S->getOpcode(), operand: Op, type: S->getType()));
1392 }
1393
1394 SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }
1395
1396 SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }
1397
1398 SVal VisitSymbolVal(nonloc::SymbolVal V) {
1399 // Simplification is much more costly than computing complexity.
1400 // For high complexity, it may be not worth it.
1401 return Visit(S: V.getSymbol());
1402 }
1403
1404 SVal VisitSVal(SVal V) { return V; }
1405 };
1406
1407 SVal SimplifiedV = Simplifier(State).Visit(V);
1408 return SimplifiedV;
1409}
1410