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