 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
66.2% |
94 / 142 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
92.3% |
131 / 142 |
| |
|
Line Coverage: |
79.6% |
121 / 152 |
| |
 |
|
 |
1 : // SimpleSValuator.cpp - A basic SValuator ------------------------*- 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 SimpleSValuator, a basic implementation of SValuator.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "clang/Checker/PathSensitive/SValuator.h"
15 : #include "clang/Checker/PathSensitive/GRState.h"
16 :
17 : using namespace clang;
18 :
19 : namespace {
20 : class SimpleSValuator : public SValuator {
21 : protected:
22 : virtual SVal EvalCastNL(NonLoc val, QualType castTy);
23 : virtual SVal EvalCastL(Loc val, QualType castTy);
24 :
25 : public:
26 2138: SimpleSValuator(ValueManager &valMgr) : SValuator(valMgr) {}
2138: branch 1 taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
27 2138: virtual ~SimpleSValuator() {}
28 :
29 : virtual SVal EvalMinus(NonLoc val);
30 : virtual SVal EvalComplement(NonLoc val);
31 : virtual SVal EvalBinOpNN(const GRState *state, BinaryOperator::Opcode op,
32 : NonLoc lhs, NonLoc rhs, QualType resultTy);
33 : virtual SVal EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs,
34 : QualType resultTy);
35 : virtual SVal EvalBinOpLN(const GRState *state, BinaryOperator::Opcode op,
36 : Loc lhs, NonLoc rhs, QualType resultTy);
37 : };
38 : } // end anonymous namespace
39 :
40 2138: SValuator *clang::CreateSimpleSValuator(ValueManager &valMgr) {
41 2138: return new SimpleSValuator(valMgr);
42 : }
43 :
44 : //===----------------------------------------------------------------------===//
45 : // Transfer function for Casts.
46 : //===----------------------------------------------------------------------===//
47 :
48 4243: SVal SimpleSValuator::EvalCastNL(NonLoc val, QualType castTy) {
49 :
50 4243: bool isLocType = Loc::IsLocType(castTy);
51 :
28: branch 1 taken
4215: branch 2 taken
52 4243: if (nonloc::LocAsInteger *LI = dyn_cast<nonloc::LocAsInteger>(&val)) {
4: branch 0 taken
24: branch 1 taken
53 28: if (isLocType)
54 4: return LI->getLoc();
55 :
56 : // FIXME: Correctly support promotions/truncations.
57 24: ASTContext &Ctx = ValMgr.getContext();
58 24: unsigned castSize = Ctx.getTypeSize(castTy);
13: branch 1 taken
11: branch 2 taken
59 24: if (castSize == LI->getNumBits())
60 13: return val;
61 :
62 11: return ValMgr.makeLocAsInteger(LI->getLoc(), castSize);
63 : }
64 :
1032: branch 1 taken
3183: branch 2 taken
65 4215: if (const SymExpr *se = val.getAsSymbolicExpression()) {
66 1032: ASTContext &Ctx = ValMgr.getContext();
67 1032: QualType T = Ctx.getCanonicalType(se->getType(Ctx));
868: branch 3 taken
164: branch 4 taken
68 1032: if (T == Ctx.getCanonicalType(castTy))
69 868: return val;
70 :
71 : // FIXME: Remove this hack when we support symbolic truncation/extension.
72 : // HACK: If both castTy and T are integers, ignore the cast. This is
73 : // not a permanent solution. Eventually we want to precisely handle
74 : // extension/truncation of symbolic integers. This prevents us from losing
75 : // precision when we assign 'x = y' and 'y' is symbolic and x and y are
76 : // different integer types.
164: branch 2 taken
0: branch 3 not taken
164: branch 6 taken
0: branch 7 not taken
164: branch 8 taken
0: branch 9 not taken
77 164: if (T->isIntegerType() && castTy->isIntegerType())
78 164: return val;
79 :
80 0: return UnknownVal();
81 : }
82 :
0: branch 1 not taken
3183: branch 2 taken
83 3183: if (!isa<nonloc::ConcreteInt>(val))
84 0: return UnknownVal();
85 :
86 : // Only handle casts from integers to integers.
2268: branch 0 taken
915: branch 1 taken
0: branch 4 not taken
2268: branch 5 taken
0: branch 6 not taken
3183: branch 7 taken
87 3183: if (!isLocType && !castTy->isIntegerType())
88 0: return UnknownVal();
89 :
90 3183: llvm::APSInt i = cast<nonloc::ConcreteInt>(val).getValue();
2112: branch 2 taken
1071: branch 3 taken
915: branch 5 taken
1197: branch 6 taken
91 3183: i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy));
92 3183: i.extOrTrunc(ValMgr.getContext().getTypeSize(castTy));
93 :
915: branch 0 taken
2268: branch 1 taken
94 3183: if (isLocType)
95 915: return ValMgr.makeIntLocVal(i);
96 : else
97 2268: return ValMgr.makeIntVal(i);
98 : }
99 :
100 2460: SVal SimpleSValuator::EvalCastL(Loc val, QualType castTy) {
101 :
102 : // Casts from pointers -> pointers, just return the lval.
103 : //
104 : // Casts from pointers -> references, just return the lval. These
105 : // can be introduced by the frontend for corner cases, e.g
106 : // casting from va_list* to __builtin_va_list&.
107 : //
102: branch 1 taken
2358: branch 2 taken
0: branch 5 not taken
102: branch 6 taken
2358: branch 7 taken
102: branch 8 taken
108 2460: if (Loc::IsLocType(castTy) || castTy->isReferenceType())
109 2358: return val;
110 :
111 : // FIXME: Handle transparent unions where a value can be "transparently"
112 : // lifted into a union type.
0: branch 2 not taken
102: branch 3 taken
113 102: if (castTy->isUnionType())
114 0: return UnknownVal();
115 :
0: branch 2 not taken
102: branch 3 taken
116 102: assert(castTy->isIntegerType());
117 102: unsigned BitWidth = ValMgr.getContext().getTypeSize(castTy);
118 :
82: branch 1 taken
20: branch 2 taken
119 102: if (!isa<loc::ConcreteInt>(val))
120 82: return ValMgr.makeLocAsInteger(val, BitWidth);
121 :
122 20: llvm::APSInt i = cast<loc::ConcreteInt>(val).getValue();
20: branch 2 taken
0: branch 3 not taken
0: branch 5 not taken
20: branch 6 taken
123 20: i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy));
124 20: i.extOrTrunc(BitWidth);
125 20: return ValMgr.makeIntVal(i);
126 : }
127 :
128 : //===----------------------------------------------------------------------===//
129 : // Transfer function for unary operators.
130 : //===----------------------------------------------------------------------===//
131 :
132 18: SVal SimpleSValuator::EvalMinus(NonLoc val) {
18: branch 1 taken
0: branch 2 not taken
133 18: switch (val.getSubKind()) {
134 : case nonloc::ConcreteIntKind:
135 18: return cast<nonloc::ConcreteInt>(val).evalMinus(ValMgr);
136 : default:
137 0: return UnknownVal();
138 : }
139 : }
140 :
141 34: SVal SimpleSValuator::EvalComplement(NonLoc X) {
20: branch 1 taken
14: branch 2 taken
142 34: switch (X.getSubKind()) {
143 : case nonloc::ConcreteIntKind:
144 20: return cast<nonloc::ConcreteInt>(X).evalComplement(ValMgr);
145 : default:
146 14: return UnknownVal();
147 : }
148 : }
149 :
150 : //===----------------------------------------------------------------------===//
151 : // Transfer function for binary operators.
152 : //===----------------------------------------------------------------------===//
153 :
154 26: static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) {
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
4: branch 5 taken
22: branch 6 taken
155 26: switch (op) {
156 : default:
157 0: assert(false && "Invalid opcode.");
158 0: case BinaryOperator::LT: return BinaryOperator::GE;
159 0: case BinaryOperator::GT: return BinaryOperator::LE;
160 0: case BinaryOperator::LE: return BinaryOperator::GT;
161 0: case BinaryOperator::GE: return BinaryOperator::LT;
162 4: case BinaryOperator::EQ: return BinaryOperator::NE;
163 22: case BinaryOperator::NE: return BinaryOperator::EQ;
164 : }
165 : }
166 :
167 : // Equality operators for Locs.
168 : // FIXME: All this logic will be revamped when we have MemRegion::getLocation()
169 : // implemented.
170 :
171 : static SVal EvalEquality(ValueManager &ValMgr, Loc lhs, Loc rhs, bool isEqual,
172 549: QualType resultTy) {
173 :
0: branch 1 not taken
154: branch 2 taken
395: branch 3 taken
0: branch 4 not taken
174 549: switch (lhs.getSubKind()) {
175 : default:
176 0: assert(false && "EQ/NE not implemented for this Loc.");
177 : return UnknownVal();
178 :
179 : case loc::ConcreteIntKind: {
72: branch 1 taken
82: branch 2 taken
180 154: if (SymbolRef rSym = rhs.getAsSymbol())
181 : return ValMgr.makeNonLoc(rSym,
182 : isEqual ? BinaryOperator::EQ
183 : : BinaryOperator::NE,
184 : cast<loc::ConcreteInt>(lhs).getValue(),
52: branch 2 taken
20: branch 3 taken
185 72: resultTy);
186 82: break;
187 : }
188 : case loc::MemRegionKind: {
385: branch 1 taken
10: branch 2 taken
189 395: if (SymbolRef lSym = lhs.getAsLocSymbol()) {
349: branch 1 taken
36: branch 2 taken
190 385: if (isa<loc::ConcreteInt>(rhs)) {
191 : return ValMgr.makeNonLoc(lSym,
192 : isEqual ? BinaryOperator::EQ
193 : : BinaryOperator::NE,
194 : cast<loc::ConcreteInt>(rhs).getValue(),
267: branch 2 taken
82: branch 3 taken
195 349: resultTy);
196 : }
197 : }
198 : break;
199 : }
200 :
201 : case loc::GotoLabelKind:
202 : break;
203 : }
204 :
117: branch 0 taken
11: branch 1 taken
205 128: return ValMgr.makeTruthVal(isEqual ? lhs == rhs : lhs != rhs, resultTy);
206 : }
207 :
208 : SVal SimpleSValuator::EvalBinOpNN(const GRState *state,
209 : BinaryOperator::Opcode op,
210 : NonLoc lhs, NonLoc rhs,
211 2468: QualType resultTy) {
212 : // Handle trivial case where left-side and right-side are the same.
345: branch 1 taken
2123: branch 2 taken
213 2468: if (lhs == rhs)
165: branch 0 taken
95: branch 1 taken
85: branch 2 taken
214 345: switch (op) {
215 : default:
216 165: break;
217 : case BinaryOperator::EQ:
218 : case BinaryOperator::LE:
219 : case BinaryOperator::GE:
220 95: return ValMgr.makeTruthVal(true, resultTy);
221 : case BinaryOperator::LT:
222 : case BinaryOperator::GT:
223 : case BinaryOperator::NE:
224 85: return ValMgr.makeTruthVal(false, resultTy);
225 : }
226 :
227 453: while (1) {
0: branch 1 not taken
58: branch 2 taken
146: branch 3 taken
1533: branch 4 taken
1004: branch 5 taken
228 2741: switch (lhs.getSubKind()) {
229 : default:
230 0: return UnknownVal();
231 : case nonloc::LocAsIntegerKind: {
232 58: Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc();
0: branch 1 not taken
58: branch 2 taken
0: branch 3 not taken
233 58: switch (rhs.getSubKind()) {
234 : case nonloc::LocAsIntegerKind:
235 : return EvalBinOpLL(op, lhsL, cast<nonloc::LocAsInteger>(rhs).getLoc(),
236 0: resultTy);
237 : case nonloc::ConcreteIntKind: {
238 : // Transform the integer into a location and compare.
239 58: ASTContext& Ctx = ValMgr.getContext();
240 58: llvm::APSInt i = cast<nonloc::ConcreteInt>(rhs).getValue();
241 58: i.setIsUnsigned(true);
242 58: i.extOrTrunc(Ctx.getTypeSize(Ctx.VoidPtrTy));
243 58: return EvalBinOpLL(op, lhsL, ValMgr.makeLoc(i), resultTy);
244 : }
245 : default:
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
246 0: switch (op) {
247 : case BinaryOperator::EQ:
248 0: return ValMgr.makeTruthVal(false, resultTy);
249 : case BinaryOperator::NE:
250 0: return ValMgr.makeTruthVal(true, resultTy);
251 : default:
252 : // This case also handles pointer arithmetic.
253 0: return UnknownVal();
254 : }
255 58: }
256 : }
257 : case nonloc::SymExprValKind: {
258 : // Logical not?
26: branch 0 taken
120: branch 1 taken
0: branch 3 not taken
26: branch 4 taken
120: branch 5 taken
26: branch 6 taken
259 146: if (!(op == BinaryOperator::EQ && rhs.isZeroConstant()))
260 120: return UnknownVal();
261 :
262 : const SymExpr *symExpr =
263 26: cast<nonloc::SymExprVal>(lhs).getSymbolicExpression();
264 :
265 : // Only handle ($sym op constant) for now.
26: branch 1 taken
0: branch 2 not taken
266 26: if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(symExpr)) {
267 26: BinaryOperator::Opcode opc = symIntExpr->getOpcode();
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
26: branch 4 taken
0: branch 5 not taken
268 26: switch (opc) {
269 : case BinaryOperator::LAnd:
270 : case BinaryOperator::LOr:
271 0: assert(false && "Logical operators handled by branching logic.");
272 : return UnknownVal();
273 : case BinaryOperator::Assign:
274 : case BinaryOperator::MulAssign:
275 : case BinaryOperator::DivAssign:
276 : case BinaryOperator::RemAssign:
277 : case BinaryOperator::AddAssign:
278 : case BinaryOperator::SubAssign:
279 : case BinaryOperator::ShlAssign:
280 : case BinaryOperator::ShrAssign:
281 : case BinaryOperator::AndAssign:
282 : case BinaryOperator::XorAssign:
283 : case BinaryOperator::OrAssign:
284 : case BinaryOperator::Comma:
285 0: assert(false && "'=' and ',' operators handled by GRExprEngine.");
286 : return UnknownVal();
287 : case BinaryOperator::PtrMemD:
288 : case BinaryOperator::PtrMemI:
289 0: assert(false && "Pointer arithmetic not handled here.");
290 : return UnknownVal();
291 : case BinaryOperator::Mul:
292 : case BinaryOperator::Div:
293 : case BinaryOperator::Rem:
294 : case BinaryOperator::Add:
295 : case BinaryOperator::Sub:
296 : case BinaryOperator::Shl:
297 : case BinaryOperator::Shr:
298 : case BinaryOperator::And:
299 : case BinaryOperator::Xor:
300 : case BinaryOperator::Or:
301 : // Not handled yet.
302 0: return UnknownVal();
303 : case BinaryOperator::LT:
304 : case BinaryOperator::GT:
305 : case BinaryOperator::LE:
306 : case BinaryOperator::GE:
307 : case BinaryOperator::EQ:
308 : case BinaryOperator::NE:
309 26: opc = NegateComparison(opc);
0: branch 3 not taken
26: branch 4 taken
310 26: assert(symIntExpr->getType(ValMgr.getContext()) == resultTy);
311 : return ValMgr.makeNonLoc(symIntExpr->getLHS(), opc,
312 26: symIntExpr->getRHS(), resultTy);
313 : }
314 : }
315 : }
316 : case nonloc::ConcreteIntKind: {
1223: branch 1 taken
310: branch 2 taken
317 1533: if (isa<nonloc::ConcreteInt>(rhs)) {
318 1223: const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs);
319 1223: return lhsInt.evalBinOp(ValMgr, op, cast<nonloc::ConcreteInt>(rhs));
320 : }
321 : else {
322 : // Swap the left and right sides and flip the operator if doing so
323 : // allows us to better reason about the expression (this is a form
324 : // of expression canonicalization).
325 310: NonLoc tmp = rhs;
326 310: rhs = lhs;
327 310: lhs = tmp;
328 :
264: branch 0 taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
36: branch 4 taken
10: branch 5 taken
329 310: switch (op) {
330 564: case BinaryOperator::LT: op = BinaryOperator::GT; continue;
331 0: case BinaryOperator::GT: op = BinaryOperator::LT; continue;
332 0: case BinaryOperator::LE: op = BinaryOperator::GE; continue;
333 0: case BinaryOperator::GE: op = BinaryOperator::LE; continue;
334 : case BinaryOperator::EQ:
335 : case BinaryOperator::NE:
336 : case BinaryOperator::Add:
337 : case BinaryOperator::Mul:
338 : continue;
339 : default:
340 10: return UnknownVal();
300: branch 1 taken
10: branch 2 taken
341 310: }
342 : }
343 : }
344 : case nonloc::SymbolValKind: {
345 1004: nonloc::SymbolVal *slhs = cast<nonloc::SymbolVal>(&lhs);
346 1004: SymbolRef Sym = slhs->getSymbol();
347 :
348 : // Does the symbol simplify to a constant? If so, "fold" the constant
349 : // by setting 'lhs' to a ConcreteInt and try again.
1004: branch 4 taken
0: branch 5 not taken
350 1004: if (Sym->getType(ValMgr.getContext())->isIntegerType())
153: branch 1 taken
851: branch 2 taken
351 1004: if (const llvm::APSInt *Constant = state->getSymVal(Sym)) {
352 : // The symbol evaluates to a constant. If necessary, promote the
353 : // folded constant (LHS) to the result type.
354 153: BasicValueFactory &BVF = ValMgr.getBasicValueFactory();
355 153: const llvm::APSInt &lhs_I = BVF.Convert(resultTy, *Constant);
356 153: lhs = nonloc::ConcreteInt(lhs_I);
357 :
358 : // Also promote the RHS (if necessary).
359 :
360 : // For shifts, it necessary promote the RHS to the result type.
113: branch 1 taken
40: branch 2 taken
361 153: if (BinaryOperator::isShiftOp(op))
362 40: continue;
363 :
364 : // Other operators: do an implicit conversion. This shouldn't be
365 : // necessary once we support truncation/extension of symbolic values.
113: branch 1 taken
0: branch 2 not taken
366 113: if (nonloc::ConcreteInt *rhs_I = dyn_cast<nonloc::ConcreteInt>(&rhs)){
367 113: rhs = nonloc::ConcreteInt(BVF.Convert(resultTy, rhs_I->getValue()));
368 : }
369 :
370 113: continue;
371 : }
372 :
819: branch 1 taken
32: branch 2 taken
373 851: if (isa<nonloc::ConcreteInt>(rhs)) {
374 : return ValMgr.makeNonLoc(slhs->getSymbol(), op,
375 : cast<nonloc::ConcreteInt>(rhs).getValue(),
376 819: resultTy);
377 : }
378 :
379 32: return UnknownVal();
380 : }
381 : }
382 : }
383 : }
384 :
385 : SVal SimpleSValuator::EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs,
386 567: QualType resultTy) {
8: branch 0 taken
549: branch 1 taken
10: branch 2 taken
387 567: switch (op) {
388 : default:
389 8: return UnknownVal();
390 : case BinaryOperator::EQ:
391 : case BinaryOperator::NE:
392 549: return EvalEquality(ValMgr, lhs, rhs, op == BinaryOperator::EQ, resultTy);
393 : case BinaryOperator::LT:
394 : case BinaryOperator::GT:
395 : // FIXME: Generalize. For now, just handle the trivial case where
396 : // the two locations are identical.
2: branch 1 taken
8: branch 2 taken
397 10: if (lhs == rhs)
398 2: return ValMgr.makeTruthVal(false, resultTy);
399 8: return UnknownVal();
400 : }
401 : }
402 :
403 : SVal SimpleSValuator::EvalBinOpLN(const GRState *state,
404 : BinaryOperator::Opcode op,
405 242: Loc lhs, NonLoc rhs, QualType resultTy) {
406 : // Special case: 'rhs' is an integer that has the same width as a pointer and
407 : // we are using the integer location in a comparison. Normally this cannot be
408 : // triggered, but transfer functions like those for OSCommpareAndSwapBarrier32
409 : // can generate comparisons that trigger this code.
410 : // FIXME: Are all locations guaranteed to have pointer width?
0: branch 1 not taken
242: branch 2 taken
411 242: if (BinaryOperator::isEqualityOp(op)) {
0: branch 1 not taken
0: branch 2 not taken
412 0: if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) {
413 0: const llvm::APSInt *x = &rhsInt->getValue();
414 0: ASTContext &ctx = ValMgr.getContext();
0: branch 3 not taken
0: branch 4 not taken
415 0: if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) {
416 : // Convert the signedness of the integer (if necessary).
0: branch 1 not taken
0: branch 2 not taken
417 0: if (x->isSigned())
418 0: x = &ValMgr.getBasicValueFactory().getValue(*x, true);
419 :
420 0: return EvalBinOpLL(op, lhs, loc::ConcreteInt(*x), resultTy);
421 : }
422 : }
423 : }
424 :
425 : // Delegate pointer arithmetic to the StoreManager.
426 : return state->getStateManager().getStoreManager().EvalBinOp(op, lhs,
427 242: rhs, resultTy);
428 : }
Generated: 2010-02-10 01:31 by zcov