blob: 15fe88ec1c1bf8c4e5c0e1e1a8883caf60b20e77 [file] [log] [blame]
Ted Kremenek50df4f42008-02-14 22:13:12 +00001//=-- GRExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
Ted Kremenekc48b8e42008-01-31 02:35:41 +00002//
Ted Kremenek2e160602008-01-31 06:49:09 +00003// The LLVM Compiler Infrastructure
Ted Kremenek68d70a82008-01-15 23:55:06 +00004//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
Ted Kremenek50df4f42008-02-14 22:13:12 +000010// This file defines a meta-engine for path-sensitive dataflow analysis that
11// is built on GREngine, but provides the boilerplate to execute transfer
12// functions and build the ExplodedGraph at the expression level.
Ted Kremenek68d70a82008-01-15 23:55:06 +000013//
14//===----------------------------------------------------------------------===//
15
Ted Kremenek50df4f42008-02-14 22:13:12 +000016#include "clang/Analysis/PathSensitive/GRExprEngine.h"
Ted Kremenek8b41e8c2008-03-07 20:57:30 +000017#include "clang/Basic/SourceManager.h"
Ted Kremenek3862eb12008-02-14 22:36:46 +000018#include "llvm/Support/Streams.h"
Ted Kremenekd4467432008-02-14 22:16:04 +000019
Ted Kremenek9f6b1612008-02-27 06:07:00 +000020#ifndef NDEBUG
21#include "llvm/Support/GraphWriter.h"
22#include <sstream>
23#endif
24
Ted Kremenekb451dd32008-03-05 21:15:02 +000025// SaveAndRestore - A utility class that uses RIIA to save and restore
26// the value of a variable.
27template<typename T>
28struct VISIBILITY_HIDDEN SaveAndRestore {
29 SaveAndRestore(T& x) : X(x), old_value(x) {}
30 ~SaveAndRestore() { X = old_value; }
31 T get() { return old_value; }
32
33 T& X;
34 T old_value;
35};
36
Ted Kremenekd4467432008-02-14 22:16:04 +000037using namespace clang;
38using llvm::dyn_cast;
39using llvm::cast;
40using llvm::APSInt;
Ted Kremenekf031b872008-01-23 19:59:44 +000041
Ted Kremenekf973eb02008-03-09 18:05:48 +000042
Ted Kremenekf4b49df2008-02-28 10:21:43 +000043ValueState* GRExprEngine::getInitialState() {
Ted Kremenekb5175bf2008-02-27 06:47:26 +000044
45 // The LiveVariables information already has a compilation of all VarDecls
46 // used in the function. Iterate through this set, and "symbolicate"
47 // any VarDecl whose value originally comes from outside the function.
48
49 typedef LiveVariables::AnalysisDataTy LVDataTy;
50 LVDataTy& D = Liveness.getAnalysisData();
51
Ted Kremenekf4b49df2008-02-28 10:21:43 +000052 ValueState StateImpl = *StateMgr.getInitialState();
Ted Kremenekb5175bf2008-02-27 06:47:26 +000053
54 for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
55
56 VarDecl* VD = cast<VarDecl>(const_cast<ScopedDecl*>(I->first));
57
58 if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD)) {
59 RVal X = RVal::GetSymbolValue(SymMgr, VD);
60 StateMgr.BindVar(StateImpl, VD, X);
61 }
62 }
63
64 return StateMgr.getPersistentState(StateImpl);
65}
66
Ted Kremenekf4b49df2008-02-28 10:21:43 +000067ValueState* GRExprEngine::SetRVal(ValueState* St, Expr* Ex, RVal V) {
Ted Kremenek9b32cd02008-02-07 04:16:04 +000068
Ted Kremenek7f5ebc72008-02-04 21:59:01 +000069 bool isBlkExpr = false;
Ted Kremenek9b32cd02008-02-07 04:16:04 +000070
Ted Kremenek07baa252008-02-21 18:02:17 +000071 if (Ex == CurrentStmt) {
72 isBlkExpr = getCFG().isBlkExpr(Ex);
Ted Kremenek7f5ebc72008-02-04 21:59:01 +000073
74 if (!isBlkExpr)
75 return St;
76 }
Ted Kremenek9b32cd02008-02-07 04:16:04 +000077
Ted Kremenekad5d5c52008-02-26 23:37:01 +000078 return StateMgr.SetRVal(St, Ex, V, isBlkExpr, false);
Ted Kremenek7f5ebc72008-02-04 21:59:01 +000079}
80
Ted Kremenekf4b49df2008-02-28 10:21:43 +000081ValueState* GRExprEngine::MarkBranch(ValueState* St, Stmt* Terminator,
82 bool branchTaken) {
Ted Kremenek99ecce72008-02-26 19:05:15 +000083
84 switch (Terminator->getStmtClass()) {
85 default:
86 return St;
87
88 case Stmt::BinaryOperatorClass: { // '&&' and '||'
89
90 BinaryOperator* B = cast<BinaryOperator>(Terminator);
91 BinaryOperator::Opcode Op = B->getOpcode();
92
93 assert (Op == BinaryOperator::LAnd || Op == BinaryOperator::LOr);
94
95 // For &&, if we take the true branch, then the value of the whole
96 // expression is that of the RHS expression.
97 //
98 // For ||, if we take the false branch, then the value of the whole
99 // expression is that of the RHS expression.
100
101 Expr* Ex = (Op == BinaryOperator::LAnd && branchTaken) ||
102 (Op == BinaryOperator::LOr && !branchTaken)
103 ? B->getRHS() : B->getLHS();
104
Ted Kremenekb31af242008-02-28 09:25:22 +0000105 return SetBlkExprRVal(St, B, UndefinedVal(Ex));
Ted Kremenek99ecce72008-02-26 19:05:15 +0000106 }
107
108 case Stmt::ConditionalOperatorClass: { // ?:
109
110 ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
111
112 // For ?, if branchTaken == true then the value is either the LHS or
113 // the condition itself. (GNU extension).
114
115 Expr* Ex;
116
117 if (branchTaken)
118 Ex = C->getLHS() ? C->getLHS() : C->getCond();
119 else
120 Ex = C->getRHS();
121
Ted Kremenekb31af242008-02-28 09:25:22 +0000122 return SetBlkExprRVal(St, C, UndefinedVal(Ex));
Ted Kremenek99ecce72008-02-26 19:05:15 +0000123 }
124
125 case Stmt::ChooseExprClass: { // ?:
126
127 ChooseExpr* C = cast<ChooseExpr>(Terminator);
128
129 Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();
Ted Kremenekb31af242008-02-28 09:25:22 +0000130 return SetBlkExprRVal(St, C, UndefinedVal(Ex));
Ted Kremenek99ecce72008-02-26 19:05:15 +0000131 }
132 }
133}
134
Ted Kremenek5c6eeb12008-02-29 20:27:50 +0000135bool GRExprEngine::ProcessBlockEntrance(CFGBlock* B, ValueState*,
136 GRBlockCounter BC) {
137
138 return BC.getNumVisited(B->getBlockID()) < 3;
139}
140
Ted Kremenek30fa28b2008-02-13 17:41:41 +0000141void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term,
Ted Kremenek07baa252008-02-21 18:02:17 +0000142 BranchNodeBuilder& builder) {
Ted Kremenek90960972008-01-30 23:03:39 +0000143
Ted Kremenek17c5f112008-02-11 19:21:59 +0000144 // Remove old bindings for subexpressions.
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000145 ValueState* PrevState = StateMgr.RemoveSubExprBindings(builder.getState());
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000146
Ted Kremenek022b6052008-02-15 22:29:00 +0000147 // Check for NULL conditions; e.g. "for(;;)"
148 if (!Condition) {
149 builder.markInfeasible(false);
Ted Kremenek022b6052008-02-15 22:29:00 +0000150 return;
151 }
152
Ted Kremenek07baa252008-02-21 18:02:17 +0000153 RVal V = GetRVal(PrevState, Condition);
Ted Kremenek90960972008-01-30 23:03:39 +0000154
155 switch (V.getBaseKind()) {
156 default:
157 break;
158
Ted Kremenek07baa252008-02-21 18:02:17 +0000159 case RVal::UnknownKind:
Ted Kremenek5f2eb192008-02-26 19:40:44 +0000160 builder.generateNode(MarkBranch(PrevState, Term, true), true);
161 builder.generateNode(MarkBranch(PrevState, Term, false), false);
Ted Kremenek90960972008-01-30 23:03:39 +0000162 return;
163
Ted Kremenekb31af242008-02-28 09:25:22 +0000164 case RVal::UndefinedKind: {
Ted Kremenek90960972008-01-30 23:03:39 +0000165 NodeTy* N = builder.generateNode(PrevState, true);
166
167 if (N) {
168 N->markAsSink();
Ted Kremenekb31af242008-02-28 09:25:22 +0000169 UndefBranches.insert(N);
Ted Kremenek90960972008-01-30 23:03:39 +0000170 }
171
172 builder.markInfeasible(false);
173 return;
174 }
175 }
Ted Kremenek4b170e52008-02-12 18:08:17 +0000176
Ted Kremenek90960972008-01-30 23:03:39 +0000177
Ted Kremenek5c6eeb12008-02-29 20:27:50 +0000178 // Process the true branch.
Ted Kremenek4b170e52008-02-12 18:08:17 +0000179
Ted Kremenek5c6eeb12008-02-29 20:27:50 +0000180 bool isFeasible = true;
181 ValueState* St = Assume(PrevState, V, true, isFeasible);
182
183 if (isFeasible)
184 builder.generateNode(MarkBranch(St, Term, true), true);
Ted Kremenek4b170e52008-02-12 18:08:17 +0000185 else
186 builder.markInfeasible(true);
Ted Kremenek5c6eeb12008-02-29 20:27:50 +0000187
188 // Process the false branch.
Ted Kremenek90960972008-01-30 23:03:39 +0000189
Ted Kremenek5c6eeb12008-02-29 20:27:50 +0000190 isFeasible = false;
191 St = Assume(PrevState, V, false, isFeasible);
Ted Kremenek90960972008-01-30 23:03:39 +0000192
Ted Kremenek5c6eeb12008-02-29 20:27:50 +0000193 if (isFeasible)
194 builder.generateNode(MarkBranch(St, Term, false), false);
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000195 else
196 builder.markInfeasible(false);
Ted Kremenek6ff3cea2008-01-29 23:32:35 +0000197}
198
Ted Kremenek30fa28b2008-02-13 17:41:41 +0000199/// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000200/// nodes by processing the 'effects' of a computed goto jump.
Ted Kremenek30fa28b2008-02-13 17:41:41 +0000201void GRExprEngine::ProcessIndirectGoto(IndirectGotoNodeBuilder& builder) {
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000202
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000203 ValueState* St = builder.getState();
Ted Kremenek07baa252008-02-21 18:02:17 +0000204 RVal V = GetRVal(St, builder.getTarget());
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000205
206 // Three possibilities:
207 //
208 // (1) We know the computed label.
Ted Kremenekb31af242008-02-28 09:25:22 +0000209 // (2) The label is NULL (or some other constant), or Undefined.
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000210 // (3) We have no clue about the label. Dispatch to all targets.
211 //
212
213 typedef IndirectGotoNodeBuilder::iterator iterator;
214
215 if (isa<lval::GotoLabel>(V)) {
216 LabelStmt* L = cast<lval::GotoLabel>(V).getLabel();
217
218 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) {
Ted Kremenek79f63f52008-02-13 17:27:37 +0000219 if (I.getLabel() == L) {
220 builder.generateNode(I, St);
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000221 return;
222 }
223 }
224
225 assert (false && "No block with label.");
226 return;
227 }
228
Ted Kremenekb31af242008-02-28 09:25:22 +0000229 if (isa<lval::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000230 // Dispatch to the first target and mark it as a sink.
Ted Kremenek79f63f52008-02-13 17:27:37 +0000231 NodeTy* N = builder.generateNode(builder.begin(), St, true);
Ted Kremenekb31af242008-02-28 09:25:22 +0000232 UndefBranches.insert(N);
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000233 return;
234 }
235
236 // This is really a catch-all. We don't support symbolics yet.
237
Ted Kremenek07baa252008-02-21 18:02:17 +0000238 assert (V.isUnknown());
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000239
240 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
Ted Kremenek79f63f52008-02-13 17:27:37 +0000241 builder.generateNode(I, St);
Ted Kremenek677f4ef2008-02-13 00:24:44 +0000242}
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000243
Ted Kremenekaee121c2008-02-13 23:08:21 +0000244/// ProcessSwitch - Called by GRCoreEngine. Used to generate successor
245/// nodes by processing the 'effects' of a switch statement.
246void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) {
247
248 typedef SwitchNodeBuilder::iterator iterator;
249
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000250 ValueState* St = builder.getState();
Ted Kremenekbc965a62008-02-18 22:57:02 +0000251 Expr* CondE = builder.getCondition();
Ted Kremenek07baa252008-02-21 18:02:17 +0000252 RVal CondV = GetRVal(St, CondE);
Ted Kremenekaee121c2008-02-13 23:08:21 +0000253
Ted Kremenekb31af242008-02-28 09:25:22 +0000254 if (CondV.isUndef()) {
Ted Kremenekaee121c2008-02-13 23:08:21 +0000255 NodeTy* N = builder.generateDefaultCaseNode(St, true);
Ted Kremenekb31af242008-02-28 09:25:22 +0000256 UndefBranches.insert(N);
Ted Kremenekaee121c2008-02-13 23:08:21 +0000257 return;
258 }
259
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000260 ValueState* DefaultSt = St;
Ted Kremenekaee121c2008-02-13 23:08:21 +0000261
262 // While most of this can be assumed (such as the signedness), having it
263 // just computed makes sure everything makes the same assumptions end-to-end.
Ted Kremenekbc965a62008-02-18 22:57:02 +0000264
Chris Lattner8cd0e932008-03-05 18:54:05 +0000265 unsigned bits = getContext().getTypeSize(CondE->getType());
Ted Kremenekbc965a62008-02-18 22:57:02 +0000266
Ted Kremenekaee121c2008-02-13 23:08:21 +0000267 APSInt V1(bits, false);
268 APSInt V2 = V1;
269
Ted Kremenek07baa252008-02-21 18:02:17 +0000270 for (iterator I = builder.begin(), EI = builder.end(); I != EI; ++I) {
Ted Kremenekaee121c2008-02-13 23:08:21 +0000271
272 CaseStmt* Case = cast<CaseStmt>(I.getCase());
273
274 // Evaluate the case.
275 if (!Case->getLHS()->isIntegerConstantExpr(V1, getContext(), 0, true)) {
276 assert (false && "Case condition must evaluate to an integer constant.");
277 return;
278 }
279
280 // Get the RHS of the case, if it exists.
281
282 if (Expr* E = Case->getRHS()) {
283 if (!E->isIntegerConstantExpr(V2, getContext(), 0, true)) {
284 assert (false &&
285 "Case condition (RHS) must evaluate to an integer constant.");
286 return ;
287 }
288
289 assert (V1 <= V2);
290 }
291 else V2 = V1;
292
293 // FIXME: Eventually we should replace the logic below with a range
294 // comparison, rather than concretize the values within the range.
Ted Kremenek07baa252008-02-21 18:02:17 +0000295 // This should be easy once we have "ranges" for NonLVals.
Ted Kremenekaee121c2008-02-13 23:08:21 +0000296
297 do {
Ted Kremenek8ad19872008-03-07 20:13:31 +0000298 nonlval::ConcreteInt CaseVal(BasicVals.getValue(V1));
Ted Kremenekaee121c2008-02-13 23:08:21 +0000299
Ted Kremenek07baa252008-02-21 18:02:17 +0000300 RVal Res = EvalBinOp(BinaryOperator::EQ, CondV, CaseVal);
Ted Kremenekaee121c2008-02-13 23:08:21 +0000301
302 // Now "assume" that the case matches.
Ted Kremenekbc965a62008-02-18 22:57:02 +0000303 bool isFeasible = false;
Ted Kremenekaee121c2008-02-13 23:08:21 +0000304
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000305 ValueState* StNew = Assume(St, Res, true, isFeasible);
Ted Kremenekaee121c2008-02-13 23:08:21 +0000306
307 if (isFeasible) {
308 builder.generateCaseStmtNode(I, StNew);
309
310 // If CondV evaluates to a constant, then we know that this
311 // is the *only* case that we can take, so stop evaluating the
312 // others.
313 if (isa<nonlval::ConcreteInt>(CondV))
314 return;
315 }
316
317 // Now "assume" that the case doesn't match. Add this state
318 // to the default state (if it is feasible).
319
Ted Kremenekb1934132008-02-14 19:37:24 +0000320 StNew = Assume(DefaultSt, Res, false, isFeasible);
Ted Kremenekaee121c2008-02-13 23:08:21 +0000321
322 if (isFeasible)
323 DefaultSt = StNew;
324
325 // Concretize the next value in the range.
326 ++V1;
327
328 } while (V1 < V2);
329 }
330
331 // If we reach here, than we know that the default branch is
332 // possible.
333 builder.generateDefaultCaseNode(DefaultSt);
334}
335
336
Ted Kremenek30fa28b2008-02-13 17:41:41 +0000337void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred,
Ted Kremenek07baa252008-02-21 18:02:17 +0000338 NodeSet& Dst) {
Ted Kremenekbf988d02008-02-19 00:22:37 +0000339
Ted Kremenek99ecce72008-02-26 19:05:15 +0000340 assert (B->getOpcode() == BinaryOperator::LAnd ||
341 B->getOpcode() == BinaryOperator::LOr);
342
343 assert (B == CurrentStmt && getCFG().isBlkExpr(B));
344
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000345 ValueState* St = GetState(Pred);
Ted Kremenek99ecce72008-02-26 19:05:15 +0000346 RVal X = GetBlkExprRVal(St, B);
347
Ted Kremenekb31af242008-02-28 09:25:22 +0000348 assert (X.isUndef());
Ted Kremenek99ecce72008-02-26 19:05:15 +0000349
Ted Kremenekb31af242008-02-28 09:25:22 +0000350 Expr* Ex = (Expr*) cast<UndefinedVal>(X).getData();
Ted Kremenek99ecce72008-02-26 19:05:15 +0000351
352 assert (Ex);
353
354 if (Ex == B->getRHS()) {
355
356 X = GetBlkExprRVal(St, Ex);
357
Ted Kremenekb31af242008-02-28 09:25:22 +0000358 // Handle undefined values.
Ted Kremenek5f2eb192008-02-26 19:40:44 +0000359
Ted Kremenekb31af242008-02-28 09:25:22 +0000360 if (X.isUndef()) {
Ted Kremenek5f2eb192008-02-26 19:40:44 +0000361 Nodify(Dst, B, Pred, SetBlkExprRVal(St, B, X));
362 return;
363 }
364
Ted Kremenek99ecce72008-02-26 19:05:15 +0000365 // We took the RHS. Because the value of the '&&' or '||' expression must
366 // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
367 // or 1. Alternatively, we could take a lazy approach, and calculate this
368 // value later when necessary. We don't have the machinery in place for
369 // this right now, and since most logical expressions are used for branches,
370 // the payoff is not likely to be large. Instead, we do eager evaluation.
371
372 bool isFeasible = false;
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000373 ValueState* NewState = Assume(St, X, true, isFeasible);
Ted Kremenek99ecce72008-02-26 19:05:15 +0000374
375 if (isFeasible)
376 Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(1U, B)));
377
378 isFeasible = false;
379 NewState = Assume(St, X, false, isFeasible);
380
381 if (isFeasible)
382 Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(0U, B)));
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000383 }
384 else {
Ted Kremenek99ecce72008-02-26 19:05:15 +0000385 // We took the LHS expression. Depending on whether we are '&&' or
386 // '||' we know what the value of the expression is via properties of
387 // the short-circuiting.
388
389 X = MakeConstantVal( B->getOpcode() == BinaryOperator::LAnd ? 0U : 1U, B);
390 Nodify(Dst, B, Pred, SetBlkExprRVal(St, B, X));
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000391 }
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000392}
Ted Kremenek99ecce72008-02-26 19:05:15 +0000393
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000394
Ted Kremenek30fa28b2008-02-13 17:41:41 +0000395void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
Ted Kremenekf031b872008-01-23 19:59:44 +0000396
Ted Kremenek07baa252008-02-21 18:02:17 +0000397 Builder = &builder;
Ted Kremenekf031b872008-01-23 19:59:44 +0000398 StmtEntryNode = builder.getLastNode();
399 CurrentStmt = S;
400 NodeSet Dst;
Ted Kremenek02331462008-03-09 18:28:41 +0000401
402 // Create the cleaned state.
403
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000404 CleanedState = StateMgr.RemoveDeadBindings(StmtEntryNode->getState(),
405 CurrentStmt, Liveness);
Ted Kremeneka1d070b2008-03-10 04:45:00 +0000406
407 Builder->SetCleanedState(CleanedState);
Ted Kremenek02331462008-03-09 18:28:41 +0000408
409 // Visit the statement.
Ted Kremenekf031b872008-01-23 19:59:44 +0000410
411 Visit(S, StmtEntryNode, Dst);
412
413 // If no nodes were generated, generate a new node that has all the
414 // dead mappings removed.
Ted Kremenek07baa252008-02-21 18:02:17 +0000415
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000416 if (Dst.size() == 1 && *Dst.begin() == StmtEntryNode)
417 builder.generateNode(S, GetState(StmtEntryNode), StmtEntryNode);
Ted Kremeneka57214f2008-01-18 00:41:32 +0000418
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000419 // NULL out these variables to cleanup.
Ted Kremenek07baa252008-02-21 18:02:17 +0000420
Ted Kremenekf031b872008-01-23 19:59:44 +0000421 CurrentStmt = NULL;
422 StmtEntryNode = NULL;
423 Builder = NULL;
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000424 CleanedState = NULL;
Ted Kremenek68d70a82008-01-15 23:55:06 +0000425}
426
Ted Kremenek6d409922008-02-13 18:06:44 +0000427void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst){
Ted Kremenek07baa252008-02-21 18:02:17 +0000428
Ted Kremenek9b32cd02008-02-07 04:16:04 +0000429 if (D != CurrentStmt) {
430 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
431 return;
432 }
433
434 // If we are here, we are loading the value of the decl and binding
435 // it to the block-level expression.
436
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000437 ValueState* St = GetState(Pred);
Ted Kremenekf97c6682008-03-09 03:30:59 +0000438 RVal X = RVal::MakeVal(BasicVals, D);
439 RVal Y = isa<lval::DeclVal>(X) ? GetRVal(St, cast<lval::DeclVal>(X)) : X;
440 Nodify(Dst, D, Pred, SetBlkExprRVal(St, D, Y));
Ted Kremenek9b32cd02008-02-07 04:16:04 +0000441}
442
Ted Kremenekd9268e32008-02-19 01:44:53 +0000443void GRExprEngine::VisitCall(CallExpr* CE, NodeTy* Pred,
Ted Kremenek07baa252008-02-21 18:02:17 +0000444 CallExpr::arg_iterator AI,
445 CallExpr::arg_iterator AE,
Ted Kremenekd9268e32008-02-19 01:44:53 +0000446 NodeSet& Dst) {
447
Ted Kremenek07baa252008-02-21 18:02:17 +0000448 // Process the arguments.
449
450 if (AI != AE) {
Ted Kremenekd9268e32008-02-19 01:44:53 +0000451
Ted Kremenekef7ea072008-03-04 00:56:45 +0000452 NodeSet DstTmp;
Ted Kremenek769f3482008-03-04 22:01:56 +0000453 Visit(*AI, Pred, DstTmp);
Ted Kremenek07baa252008-02-21 18:02:17 +0000454 ++AI;
455
Ted Kremenek769f3482008-03-04 22:01:56 +0000456 for (NodeSet::iterator DI=DstTmp.begin(), DE=DstTmp.end(); DI != DE; ++DI)
Ted Kremenek07baa252008-02-21 18:02:17 +0000457 VisitCall(CE, *DI, AI, AE, Dst);
Ted Kremenekd9268e32008-02-19 01:44:53 +0000458
459 return;
460 }
461
462 // If we reach here we have processed all of the arguments. Evaluate
463 // the callee expression.
Ted Kremenekcda2efd2008-03-03 16:47:31 +0000464
Ted Kremenekc71901d2008-02-25 21:16:03 +0000465 NodeSet DstTmp;
466 Expr* Callee = CE->getCallee()->IgnoreParenCasts();
Ted Kremenekcda2efd2008-03-03 16:47:31 +0000467
Ted Kremenekc71901d2008-02-25 21:16:03 +0000468 VisitLVal(Callee, Pred, DstTmp);
Ted Kremenekcda2efd2008-03-03 16:47:31 +0000469
470 if (DstTmp.empty())
471 DstTmp.Add(Pred);
Ted Kremenekd9268e32008-02-19 01:44:53 +0000472
473 // Finally, evaluate the function call.
Ted Kremenek07baa252008-02-21 18:02:17 +0000474 for (NodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end(); DI!=DE; ++DI) {
475
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000476 ValueState* St = GetState(*DI);
Ted Kremenekc71901d2008-02-25 21:16:03 +0000477 RVal L = GetLVal(St, Callee);
Ted Kremenekd9268e32008-02-19 01:44:53 +0000478
Ted Kremenekcda2efd2008-03-03 16:47:31 +0000479 // FIXME: Add support for symbolic function calls (calls involving
480 // function pointer values that are symbolic).
481
482 // Check for undefined control-flow or calls to NULL.
483
Ted Kremenek43863eb2008-02-29 23:14:48 +0000484 if (L.isUndef() || isa<lval::ConcreteInt>(L)) {
Ted Kremenekd9268e32008-02-19 01:44:53 +0000485 NodeTy* N = Builder->generateNode(CE, St, *DI);
Ted Kremenek769f3482008-03-04 22:01:56 +0000486
Ted Kremenek9b31f5b2008-02-29 23:53:11 +0000487 if (N) {
488 N->markAsSink();
489 BadCalls.insert(N);
490 }
Ted Kremenek769f3482008-03-04 22:01:56 +0000491
Ted Kremenekd9268e32008-02-19 01:44:53 +0000492 continue;
Ted Kremenekb451dd32008-03-05 21:15:02 +0000493 }
494
495 // Check for the "noreturn" attribute.
496
497 SaveAndRestore<bool> OldSink(Builder->BuildSinks);
498
499 if (isa<lval::FuncVal>(L))
Ted Kremeneka2822eb2008-03-05 22:49:16 +0000500 if (cast<lval::FuncVal>(L).getDecl()->getAttr<NoReturnAttr>())
Ted Kremenekb451dd32008-03-05 21:15:02 +0000501 Builder->BuildSinks = true;
Ted Kremenekb451dd32008-03-05 21:15:02 +0000502
503 // Evaluate the call.
504
Ted Kremenekcda2efd2008-03-03 16:47:31 +0000505
Ted Kremenek769f3482008-03-04 22:01:56 +0000506 bool invalidateArgs = false;
Ted Kremenekd9268e32008-02-19 01:44:53 +0000507
Ted Kremenekb9a20e02008-02-21 19:46:04 +0000508 if (L.isUnknown()) {
Ted Kremenek769f3482008-03-04 22:01:56 +0000509 // Check for an "unknown" callee.
510 invalidateArgs = true;
511 }
512 else if (isa<lval::FuncVal>(L)) {
513
514 IdentifierInfo* Info = cast<lval::FuncVal>(L).getDecl()->getIdentifier();
515
Ted Kremenek21581c62008-03-05 22:59:42 +0000516 if (unsigned id = Info->getBuiltinID()) {
517 switch (id) {
518 case Builtin::BI__builtin_expect: {
519 // For __builtin_expect, just return the value of the subexpression.
520 assert (CE->arg_begin() != CE->arg_end());
521 RVal X = GetRVal(St, *(CE->arg_begin()));
522 Nodify(Dst, CE, *DI, SetRVal(St, CE, X));
523 continue;
524 }
525
526 default:
527 invalidateArgs = true;
528 break;
529 }
530 }
Ted Kremenek769f3482008-03-04 22:01:56 +0000531 }
532
533 if (invalidateArgs) {
Ted Kremenekb9a20e02008-02-21 19:46:04 +0000534 // Invalidate all arguments passed in by reference (LVals).
535 for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
536 I != E; ++I) {
537 RVal V = GetRVal(St, *I);
Ted Kremenek07baa252008-02-21 18:02:17 +0000538
Ted Kremenekb9a20e02008-02-21 19:46:04 +0000539 if (isa<LVal>(V))
540 St = SetRVal(St, cast<LVal>(V), UnknownVal());
Ted Kremenekb451dd32008-03-05 21:15:02 +0000541 }
542
543 Nodify(Dst, CE, *DI, St);
Ted Kremenekb9a20e02008-02-21 19:46:04 +0000544 }
Ted Kremenek769f3482008-03-04 22:01:56 +0000545 else {
546
547 // Check any arguments passed-by-value against being undefined.
548
549 bool badArg = false;
550
551 for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
552 I != E; ++I) {
553
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000554 if (GetRVal(GetState(*DI), *I).isUndef()) {
555 NodeTy* N = Builder->generateNode(CE, GetState(*DI), *DI);
Ted Kremenek769f3482008-03-04 22:01:56 +0000556
557 if (N) {
558 N->markAsSink();
559 UndefArgs[N] = *I;
560 }
561
562 badArg = true;
563 break;
564 }
565 }
566
567 if (badArg)
568 continue;
569
570 // Dispatch to the plug-in transfer function.
Ted Kremenek3eea8dd2008-03-05 00:33:14 +0000571
572 unsigned size = Dst.size();
573
574 EvalCall(Dst, CE, cast<LVal>(L), *DI);
575
Ted Kremeneka2822eb2008-03-05 22:49:16 +0000576 if (!Builder->BuildSinks && Dst.size() == size)
Ted Kremenek3eea8dd2008-03-05 00:33:14 +0000577 Nodify(Dst, CE, *DI, St);
Ted Kremenek769f3482008-03-04 22:01:56 +0000578 }
Ted Kremenekd9268e32008-02-19 01:44:53 +0000579 }
580}
581
Ted Kremenek07baa252008-02-21 18:02:17 +0000582void GRExprEngine::VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst){
Ted Kremenek54eddae2008-01-24 02:02:54 +0000583
Ted Kremenek5f585b02008-02-19 18:52:54 +0000584 NodeSet S1;
Ted Kremenek5f585b02008-02-19 18:52:54 +0000585 QualType T = CastE->getType();
586
Ted Kremenek1d1b6c92008-03-04 22:16:08 +0000587 if (T->isReferenceType())
588 VisitLVal(Ex, Pred, S1);
589 else
590 Visit(Ex, Pred, S1);
591
Ted Kremenek5a9b6aa2008-02-19 18:47:04 +0000592 // Check for redundant casts or casting to "void"
593 if (T->isVoidType() ||
Ted Kremenek07baa252008-02-21 18:02:17 +0000594 Ex->getType() == T ||
595 (T->isPointerType() && Ex->getType()->isFunctionType())) {
Ted Kremenek5f585b02008-02-19 18:52:54 +0000596
Ted Kremenek07baa252008-02-21 18:02:17 +0000597 for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1)
Ted Kremenek5f585b02008-02-19 18:52:54 +0000598 Dst.Add(*I1);
599
Ted Kremenek54eddae2008-01-24 02:02:54 +0000600 return;
601 }
602
Ted Kremenek07baa252008-02-21 18:02:17 +0000603 for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) {
Ted Kremenek54eddae2008-01-24 02:02:54 +0000604 NodeTy* N = *I1;
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000605 ValueState* St = GetState(N);
Ted Kremenek1d1b6c92008-03-04 22:16:08 +0000606
607 RVal V = T->isReferenceType() ? GetLVal(St, Ex) : GetRVal(St, Ex);
608
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000609 Nodify(Dst, CastE, N, SetRVal(St, CastE, EvalCast(V, CastE->getType())));
Ted Kremenek54eddae2008-01-24 02:02:54 +0000610 }
Ted Kremenekb9c30e32008-01-24 20:55:43 +0000611}
612
Ted Kremenek30fa28b2008-02-13 17:41:41 +0000613void GRExprEngine::VisitDeclStmt(DeclStmt* DS, GRExprEngine::NodeTy* Pred,
Ted Kremenek07baa252008-02-21 18:02:17 +0000614 GRExprEngine::NodeSet& Dst) {
Ted Kremenekb9c30e32008-01-24 20:55:43 +0000615
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000616 ValueState* St = GetState(Pred);
Ted Kremenekb9c30e32008-01-24 20:55:43 +0000617
618 for (const ScopedDecl* D = DS->getDecl(); D; D = D->getNextDeclarator())
Ted Kremenek8c9bc342008-01-28 22:51:57 +0000619 if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
Ted Kremeneke0258002008-02-19 00:29:51 +0000620
621 // FIXME: Add support for local arrays.
622 if (VD->getType()->isArrayType())
623 continue;
624
Ted Kremenek04ab4c12008-02-27 19:21:33 +0000625 const Expr* Ex = VD->getInit();
Ted Kremenek07baa252008-02-21 18:02:17 +0000626
Ted Kremenek04ab4c12008-02-27 19:21:33 +0000627 if (!VD->hasGlobalStorage() || VD->getStorageClass() == VarDecl::Static) {
628
629 // In this context, Static => Local variable.
630
631 assert (!VD->getStorageClass() == VarDecl::Static ||
632 !isa<FileVarDecl>(VD));
633
634 // If there is no initializer, set the value of the
Ted Kremenekb31af242008-02-28 09:25:22 +0000635 // variable to "Undefined".
Ted Kremenek04ab4c12008-02-27 19:21:33 +0000636 //
637 // FIXME: static variables may have an initializer, but the second
638 // time a function is called those values may not be current.
Ted Kremenek98d093b2008-03-04 20:40:11 +0000639
640 QualType T = VD->getType();
Ted Kremenek04ab4c12008-02-27 19:21:33 +0000641
Ted Kremeneka6cfcc92008-03-04 04:18:04 +0000642 if ( VD->getStorageClass() == VarDecl::Static) {
Ted Kremeneka6cfcc92008-03-04 04:18:04 +0000643
644 // C99: 6.7.8 Initialization
645 // If an object that has static storage duration is not initialized
646 // explicitly, then:
647 // —if it has pointer type, it is initialized to a null pointer;
648 // —if it has arithmetic type, it is initialized to (positive or
649 // unsigned) zero;
650
Ted Kremenek98d093b2008-03-04 20:40:11 +0000651 // FIXME: Handle structs. Now we treat their values as unknown.
652
Ted Kremeneka6cfcc92008-03-04 04:18:04 +0000653 if (T->isPointerType()) {
654
655 St = SetRVal(St, lval::DeclVal(VD),
Ted Kremenek8ad19872008-03-07 20:13:31 +0000656 lval::ConcreteInt(BasicVals.getValue(0, T)));
Ted Kremeneka6cfcc92008-03-04 04:18:04 +0000657 }
658 else if (T->isIntegerType()) {
659
660 St = SetRVal(St, lval::DeclVal(VD),
Ted Kremenek8ad19872008-03-07 20:13:31 +0000661 nonlval::ConcreteInt(BasicVals.getValue(0, T)));
Ted Kremeneka6cfcc92008-03-04 04:18:04 +0000662 }
663
Ted Kremenek98d093b2008-03-04 20:40:11 +0000664
Ted Kremeneka6cfcc92008-03-04 04:18:04 +0000665 }
Ted Kremenek98d093b2008-03-04 20:40:11 +0000666 else {
Ted Kremeneka6cfcc92008-03-04 04:18:04 +0000667
Ted Kremenek98d093b2008-03-04 20:40:11 +0000668 // FIXME: Handle structs. Now we treat them as unknown. What
669 // we need to do is treat their members as unknown.
670
671 if (T->isPointerType() || T->isIntegerType())
672 St = SetRVal(St, lval::DeclVal(VD),
673 Ex ? GetRVal(St, Ex) : UndefinedVal());
674 }
Ted Kremenek04ab4c12008-02-27 19:21:33 +0000675 }
Ted Kremenek8c9bc342008-01-28 22:51:57 +0000676 }
Ted Kremenekb9c30e32008-01-24 20:55:43 +0000677
678 Nodify(Dst, DS, Pred, St);
Ted Kremenekb9c30e32008-01-24 20:55:43 +0000679}
Ted Kremenek54eddae2008-01-24 02:02:54 +0000680
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000681
Ted Kremenek07baa252008-02-21 18:02:17 +0000682void GRExprEngine::VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R,
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000683 NodeTy* Pred, NodeSet& Dst) {
684
Ted Kremenek99ecce72008-02-26 19:05:15 +0000685 assert (Ex == CurrentStmt && getCFG().isBlkExpr(Ex));
686
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000687 ValueState* St = GetState(Pred);
Ted Kremenek99ecce72008-02-26 19:05:15 +0000688 RVal X = GetBlkExprRVal(St, Ex);
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000689
Ted Kremenekb31af242008-02-28 09:25:22 +0000690 assert (X.isUndef());
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000691
Ted Kremenekb31af242008-02-28 09:25:22 +0000692 Expr* SE = (Expr*) cast<UndefinedVal>(X).getData();
Ted Kremenek99ecce72008-02-26 19:05:15 +0000693
694 assert (SE);
695
696 X = GetBlkExprRVal(St, SE);
Ted Kremenekad5d5c52008-02-26 23:37:01 +0000697
698 // Make sure that we invalidate the previous binding.
699 Nodify(Dst, Ex, Pred, StateMgr.SetRVal(St, Ex, X, true, true));
Ted Kremenek1f0eb992008-02-05 00:26:40 +0000700}
701
Ted Kremenekfd85f292008-02-12 19:49:57 +0000702/// VisitSizeOfAlignOfTypeExpr - Transfer function for sizeof(type).
Ted Kremenek07baa252008-02-21 18:02:17 +0000703void GRExprEngine::VisitSizeOfAlignOfTypeExpr(SizeOfAlignOfTypeExpr* Ex,
704 NodeTy* Pred,
705 NodeSet& Dst) {
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000706
707 assert (Ex->isSizeOf() && "FIXME: AlignOf(Expr) not yet implemented.");
Ted Kremenekfd85f292008-02-12 19:49:57 +0000708
709 // 6.5.3.4 sizeof: "The result type is an integer."
710
Ted Kremenek07baa252008-02-21 18:02:17 +0000711 QualType T = Ex->getArgumentType();
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000712
Ted Kremenek07baa252008-02-21 18:02:17 +0000713
Ted Kremenek571f5192008-02-21 18:15:29 +0000714 // FIXME: Add support for VLAs.
Eli Friedman82ce9a82008-02-15 12:28:27 +0000715 if (!T.getTypePtr()->isConstantSizeType())
Ted Kremenekfd85f292008-02-12 19:49:57 +0000716 return;
717
Ted Kremenek571f5192008-02-21 18:15:29 +0000718
719 uint64_t size = 1; // Handle sizeof(void)
720
Chris Lattner8cd0e932008-03-05 18:54:05 +0000721 if (T != getContext().VoidTy)
722 size = getContext().getTypeSize(T) / 8;
Ted Kremenekfd85f292008-02-12 19:49:57 +0000723
Ted Kremenek07baa252008-02-21 18:02:17 +0000724 Nodify(Dst, Ex, Pred,
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000725 SetRVal(GetState(Pred), Ex,
Ted Kremenek8ad19872008-03-07 20:13:31 +0000726 NonLVal::MakeVal(BasicVals, size, Ex->getType())));
Ted Kremenekfd85f292008-02-12 19:49:57 +0000727
728}
729
Ted Kremenek5e1e05c2008-03-07 22:58:01 +0000730void GRExprEngine::VisitDeref(UnaryOperator* U, NodeTy* Pred,
731 NodeSet& Dst, bool GetLVal) {
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000732
Ted Kremenek07baa252008-02-21 18:02:17 +0000733 Expr* Ex = U->getSubExpr()->IgnoreParens();
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000734
735 NodeSet DstTmp;
736
Ted Kremenek56a89992008-02-26 03:44:25 +0000737 if (isa<DeclRefExpr>(Ex))
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000738 DstTmp.Add(Pred);
739 else
Ted Kremenek07baa252008-02-21 18:02:17 +0000740 Visit(Ex, Pred, DstTmp);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000741
Ted Kremenek07baa252008-02-21 18:02:17 +0000742 for (NodeSet::iterator I = DstTmp.begin(), DE = DstTmp.end(); I != DE; ++I) {
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000743
744 NodeTy* N = *I;
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000745 ValueState* St = GetState(N);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000746
747 // FIXME: Bifurcate when dereferencing a symbolic with no constraints?
748
Ted Kremenek07baa252008-02-21 18:02:17 +0000749 RVal V = GetRVal(St, Ex);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000750
Ted Kremenekb31af242008-02-28 09:25:22 +0000751 // Check for dereferences of undefined values.
Ted Kremenek07baa252008-02-21 18:02:17 +0000752
Ted Kremenekb31af242008-02-28 09:25:22 +0000753 if (V.isUndef()) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000754
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000755 NodeTy* Succ = Builder->generateNode(U, St, N);
756
757 if (Succ) {
758 Succ->markAsSink();
Ted Kremenekb31af242008-02-28 09:25:22 +0000759 UndefDeref.insert(Succ);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000760 }
761
762 continue;
763 }
764
Ted Kremenek07baa252008-02-21 18:02:17 +0000765 // Check for dereferences of unknown values. Treat as No-Ops.
766
767 if (V.isUnknown()) {
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000768 Dst.Add(N);
769 continue;
770 }
771
772 // After a dereference, one of two possible situations arise:
773 // (1) A crash, because the pointer was NULL.
774 // (2) The pointer is not NULL, and the dereference works.
775 //
776 // We add these assumptions.
777
Ted Kremenek07baa252008-02-21 18:02:17 +0000778 LVal LV = cast<LVal>(V);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000779 bool isFeasibleNotNull;
780
781 // "Assume" that the pointer is Not-NULL.
Ted Kremenek07baa252008-02-21 18:02:17 +0000782
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000783 ValueState* StNotNull = Assume(St, LV, true, isFeasibleNotNull);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000784
785 if (isFeasibleNotNull) {
Ted Kremenek5e1e05c2008-03-07 22:58:01 +0000786
787 if (GetLVal) Nodify(Dst, U, N, SetRVal(StNotNull, U, LV));
788 else {
789
790 // FIXME: Currently symbolic analysis "generates" new symbols
791 // for the contents of values. We need a better approach.
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000792
Ted Kremenek5e1e05c2008-03-07 22:58:01 +0000793 Nodify(Dst, U, N, SetRVal(StNotNull, U,
794 GetRVal(StNotNull, LV, U->getType())));
795 }
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000796 }
797
798 bool isFeasibleNull;
799
Ted Kremenek07baa252008-02-21 18:02:17 +0000800 // Now "assume" that the pointer is NULL.
801
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000802 ValueState* StNull = Assume(St, LV, false, isFeasibleNull);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000803
804 if (isFeasibleNull) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000805
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000806 // We don't use "Nodify" here because the node will be a sink
807 // and we have no intention of processing it later.
Ted Kremenek07baa252008-02-21 18:02:17 +0000808
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000809 NodeTy* NullNode = Builder->generateNode(U, StNull, N);
810
811 if (NullNode) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000812
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000813 NullNode->markAsSink();
814
Ted Kremenek07baa252008-02-21 18:02:17 +0000815 if (isFeasibleNotNull) ImplicitNullDeref.insert(NullNode);
816 else ExplicitNullDeref.insert(NullNode);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000817 }
818 }
819 }
820}
821
Ted Kremenek07baa252008-02-21 18:02:17 +0000822void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred,
823 NodeSet& Dst) {
Ted Kremenek9b32cd02008-02-07 04:16:04 +0000824
Ted Kremenek1be5eb92008-01-24 02:28:56 +0000825 NodeSet S1;
Ted Kremenek9b32cd02008-02-07 04:16:04 +0000826
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000827 assert (U->getOpcode() != UnaryOperator::Deref);
Ted Kremenek07baa252008-02-21 18:02:17 +0000828 assert (U->getOpcode() != UnaryOperator::SizeOf);
829 assert (U->getOpcode() != UnaryOperator::AlignOf);
830
831 bool use_GetLVal = false;
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000832
833 switch (U->getOpcode()) {
834 case UnaryOperator::PostInc:
835 case UnaryOperator::PostDec:
836 case UnaryOperator::PreInc:
837 case UnaryOperator::PreDec:
838 case UnaryOperator::AddrOf:
Ted Kremenek07baa252008-02-21 18:02:17 +0000839 // Evalue subexpression as an LVal.
840 use_GetLVal = true;
841 VisitLVal(U->getSubExpr(), Pred, S1);
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000842 break;
843
844 default:
845 Visit(U->getSubExpr(), Pred, S1);
846 break;
847 }
848
Ted Kremenek07baa252008-02-21 18:02:17 +0000849 for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) {
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000850
Ted Kremenek1be5eb92008-01-24 02:28:56 +0000851 NodeTy* N1 = *I1;
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000852 ValueState* St = GetState(N1);
Ted Kremenek07baa252008-02-21 18:02:17 +0000853
854 RVal SubV = use_GetLVal ? GetLVal(St, U->getSubExpr()) :
855 GetRVal(St, U->getSubExpr());
856
857 if (SubV.isUnknown()) {
858 Dst.Add(N1);
859 continue;
860 }
861
Ted Kremenekb31af242008-02-28 09:25:22 +0000862 if (SubV.isUndef()) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000863 Nodify(Dst, U, N1, SetRVal(St, U, SubV));
864 continue;
865 }
Ted Kremenek1be5eb92008-01-24 02:28:56 +0000866
Ted Kremenek22640ce2008-02-15 22:09:30 +0000867 if (U->isIncrementDecrementOp()) {
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000868
869 // Handle ++ and -- (both pre- and post-increment).
870
Ted Kremenek07baa252008-02-21 18:02:17 +0000871 LVal SubLV = cast<LVal>(SubV);
872 RVal V = GetRVal(St, SubLV, U->getType());
873
Ted Kremenekb8782e12008-02-21 19:15:37 +0000874 if (V.isUnknown()) {
875 Dst.Add(N1);
876 continue;
877 }
Ted Kremenek07baa252008-02-21 18:02:17 +0000878
Ted Kremenekb31af242008-02-28 09:25:22 +0000879 // Propagate undefined values.
880 if (V.isUndef()) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000881 Nodify(Dst, U, N1, SetRVal(St, U, V));
882 continue;
883 }
884
Ted Kremenekb1669d42008-02-21 19:29:23 +0000885 // Handle all other values.
Ted Kremenek22640ce2008-02-15 22:09:30 +0000886
887 BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add
888 : BinaryOperator::Sub;
889
Ted Kremenekb1669d42008-02-21 19:29:23 +0000890 RVal Result = EvalBinOp(Op, V, MakeConstantVal(1U, U));
Ted Kremenek22640ce2008-02-15 22:09:30 +0000891
892 if (U->isPostfix())
Ted Kremenek07baa252008-02-21 18:02:17 +0000893 St = SetRVal(SetRVal(St, U, V), SubLV, Result);
Ted Kremenek22640ce2008-02-15 22:09:30 +0000894 else
Ted Kremenek07baa252008-02-21 18:02:17 +0000895 St = SetRVal(SetRVal(St, U, Result), SubLV, Result);
Ted Kremenek22640ce2008-02-15 22:09:30 +0000896
Ted Kremenek07baa252008-02-21 18:02:17 +0000897 Nodify(Dst, U, N1, St);
Ted Kremenek22640ce2008-02-15 22:09:30 +0000898 continue;
899 }
900
901 // Handle all other unary operators.
902
Ted Kremenek1be5eb92008-01-24 02:28:56 +0000903 switch (U->getOpcode()) {
Ted Kremenek15cb0782008-02-06 22:50:25 +0000904
Ted Kremenek07baa252008-02-21 18:02:17 +0000905 case UnaryOperator::Minus:
906 St = SetRVal(St, U, EvalMinus(U, cast<NonLVal>(SubV)));
Ted Kremenekcacd7362008-01-24 08:20:02 +0000907 break;
Ted Kremenekcacd7362008-01-24 08:20:02 +0000908
Ted Kremenek07baa252008-02-21 18:02:17 +0000909 case UnaryOperator::Not:
910 St = SetRVal(St, U, EvalComplement(cast<NonLVal>(SubV)));
Ted Kremenek0cd96352008-02-20 04:12:31 +0000911 break;
Ted Kremenek0cd96352008-02-20 04:12:31 +0000912
Ted Kremenek07baa252008-02-21 18:02:17 +0000913 case UnaryOperator::LNot:
Ted Kremenek2cb46642008-02-04 16:58:30 +0000914
Ted Kremeneka6683bf2008-02-06 17:56:00 +0000915 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
916 //
917 // Note: technically we do "E == 0", but this is the same in the
918 // transfer functions as "0 == E".
Ted Kremenek07baa252008-02-21 18:02:17 +0000919
920 if (isa<LVal>(SubV)) {
Ted Kremenek8ad19872008-03-07 20:13:31 +0000921 lval::ConcreteInt V(BasicVals.getZeroWithPtrWidth());
Ted Kremenek07baa252008-02-21 18:02:17 +0000922 RVal Result = EvalBinOp(BinaryOperator::EQ, cast<LVal>(SubV), V);
923 St = SetRVal(St, U, Result);
Ted Kremeneka6683bf2008-02-06 17:56:00 +0000924 }
925 else {
Ted Kremeneka0894672008-02-22 00:42:36 +0000926 Expr* Ex = U->getSubExpr();
Ted Kremenek8ad19872008-03-07 20:13:31 +0000927 nonlval::ConcreteInt V(BasicVals.getValue(0, Ex->getType()));
Ted Kremenek07baa252008-02-21 18:02:17 +0000928 RVal Result = EvalBinOp(BinaryOperator::EQ, cast<NonLVal>(SubV), V);
929 St = SetRVal(St, U, Result);
Ted Kremeneka6683bf2008-02-06 17:56:00 +0000930 }
931
932 break;
Ted Kremeneka6683bf2008-02-06 17:56:00 +0000933
Ted Kremenekc48b8e42008-01-31 02:35:41 +0000934 case UnaryOperator::AddrOf: {
Ted Kremenek07baa252008-02-21 18:02:17 +0000935 assert (isa<LVal>(SubV));
936 St = SetRVal(St, U, SubV);
Ted Kremenekc48b8e42008-01-31 02:35:41 +0000937 break;
938 }
Ted Kremenek80d52d02008-02-07 05:48:01 +0000939
Ted Kremenek1be5eb92008-01-24 02:28:56 +0000940 default: ;
941 assert (false && "Not implemented.");
Ted Kremenek07baa252008-02-21 18:02:17 +0000942 }
943
944 Nodify(Dst, U, N1, St);
Ted Kremenek1be5eb92008-01-24 02:28:56 +0000945 }
946}
947
Ted Kremenek07baa252008-02-21 18:02:17 +0000948void GRExprEngine::VisitSizeOfExpr(UnaryOperator* U, NodeTy* Pred,
949 NodeSet& Dst) {
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000950
Ted Kremenek07baa252008-02-21 18:02:17 +0000951 QualType T = U->getSubExpr()->getType();
Ted Kremenekb996ebc2008-02-20 04:02:35 +0000952
Ted Kremenek07baa252008-02-21 18:02:17 +0000953 // FIXME: Add support for VLAs.
954 if (!T.getTypePtr()->isConstantSizeType())
955 return;
956
Chris Lattner8cd0e932008-03-05 18:54:05 +0000957 uint64_t size = getContext().getTypeSize(T) / 8;
Ted Kremenek50ef5ff2008-03-10 04:11:42 +0000958 ValueState* St = GetState(Pred);
Ted Kremenek8ad19872008-03-07 20:13:31 +0000959 St = SetRVal(St, U, NonLVal::MakeVal(BasicVals, size, U->getType()));
Ted Kremenek07baa252008-02-21 18:02:17 +0000960
961 Nodify(Dst, U, Pred, St);
962}
963
964void GRExprEngine::VisitLVal(Expr* Ex, NodeTy* Pred, NodeSet& Dst) {
Ted Kremeneka129a2e2008-02-27 07:04:16 +0000965
966 if (Ex != CurrentStmt && getCFG().isBlkExpr(Ex)) {
967 Dst.Add(Pred);
968 return;
969 }
Ted Kremenek07baa252008-02-21 18:02:17 +0000970
971 Ex = Ex->IgnoreParens();
972
Ted Kremenekb5175bf2008-02-27 06:47:26 +0000973 if (isa<DeclRefExpr>(Ex)) {
Ted Kremenek9b32cd02008-02-07 04:16:04 +0000974 Dst.Add(Pred);
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000975 return;
Ted Kremenek9b32cd02008-02-07 04:16:04 +0000976 }
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000977
Ted Kremenek5e1e05c2008-03-07 22:58:01 +0000978 if (UnaryOperator* U = dyn_cast<UnaryOperator>(Ex))
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000979 if (U->getOpcode() == UnaryOperator::Deref) {
Ted Kremenek5e1e05c2008-03-07 22:58:01 +0000980 VisitDeref(U, Pred, Dst, true);
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000981 return;
982 }
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000983
Ted Kremenek07baa252008-02-21 18:02:17 +0000984 Visit(Ex, Pred, Dst);
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000985}
986
Ted Kremenek30fa28b2008-02-13 17:41:41 +0000987void GRExprEngine::VisitBinaryOperator(BinaryOperator* B,
Ted Kremenekaee121c2008-02-13 23:08:21 +0000988 GRExprEngine::NodeTy* Pred,
989 GRExprEngine::NodeSet& Dst) {
Ted Kremenekf031b872008-01-23 19:59:44 +0000990 NodeSet S1;
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000991
992 if (B->isAssignmentOp())
Ted Kremenek07baa252008-02-21 18:02:17 +0000993 VisitLVal(B->getLHS(), Pred, S1);
Ted Kremeneke1f38b62008-02-07 01:08:27 +0000994 else
995 Visit(B->getLHS(), Pred, S1);
Ted Kremenekafba4b22008-01-16 00:53:15 +0000996
Ted Kremenekf031b872008-01-23 19:59:44 +0000997 for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000998
Ted Kremenekf031b872008-01-23 19:59:44 +0000999 NodeTy* N1 = *I1;
Ted Kremeneke860db82008-01-17 00:52:48 +00001000
Ted Kremenekf031b872008-01-23 19:59:44 +00001001 // When getting the value for the LHS, check if we are in an assignment.
Ted Kremenek07baa252008-02-21 18:02:17 +00001002 // In such cases, we want to (initially) treat the LHS as an LVal,
1003 // so we use GetLVal instead of GetRVal so that DeclRefExpr's are
1004 // evaluated to LValDecl's instead of to an NonLVal.
1005
Ted Kremenek50ef5ff2008-03-10 04:11:42 +00001006 RVal LeftV = B->isAssignmentOp() ? GetLVal(GetState(N1), B->getLHS())
1007 : GetRVal(GetState(N1), B->getLHS());
Ted Kremenekafba4b22008-01-16 00:53:15 +00001008
Ted Kremenek07baa252008-02-21 18:02:17 +00001009 // Visit the RHS...
1010
1011 NodeSet S2;
Ted Kremenekf031b872008-01-23 19:59:44 +00001012 Visit(B->getRHS(), N1, S2);
Ted Kremenek07baa252008-02-21 18:02:17 +00001013
1014 // Process the binary operator.
Ted Kremenekf031b872008-01-23 19:59:44 +00001015
Ted Kremenek07baa252008-02-21 18:02:17 +00001016 for (NodeSet::iterator I2 = S2.begin(), E2 = S2.end(); I2 != E2; ++I2) {
Ted Kremenek15cb0782008-02-06 22:50:25 +00001017
Ted Kremenekf031b872008-01-23 19:59:44 +00001018 NodeTy* N2 = *I2;
Ted Kremenek50ef5ff2008-03-10 04:11:42 +00001019 ValueState* St = GetState(N2);
Ted Kremenek2c369792008-02-25 18:42:54 +00001020 Expr* RHS = B->getRHS();
1021 RVal RightV = GetRVal(St, RHS);
Ted Kremenekf031b872008-01-23 19:59:44 +00001022
Ted Kremenek15cb0782008-02-06 22:50:25 +00001023 BinaryOperator::Opcode Op = B->getOpcode();
1024
Ted Kremenek2c369792008-02-25 18:42:54 +00001025 if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem)
1026 && RHS->getType()->isIntegerType()) {
Ted Kremenekef0007f2008-02-26 02:15:56 +00001027
Ted Kremenekb31af242008-02-28 09:25:22 +00001028 // Check if the denominator is undefined.
Ted Kremenek2c369792008-02-25 18:42:54 +00001029
Ted Kremenek5a600862008-02-26 22:27:51 +00001030 if (!RightV.isUnknown()) {
1031
Ted Kremenekb31af242008-02-28 09:25:22 +00001032 if (RightV.isUndef()) {
1033 NodeTy* DivUndef = Builder->generateNode(B, St, N2);
Ted Kremenek5a600862008-02-26 22:27:51 +00001034
Ted Kremenekb31af242008-02-28 09:25:22 +00001035 if (DivUndef) {
1036 DivUndef->markAsSink();
Ted Kremenek75f32c62008-03-07 19:04:53 +00001037 ExplicitBadDivides.insert(DivUndef);
Ted Kremenek5a600862008-02-26 22:27:51 +00001038 }
1039
1040 continue;
1041 }
1042
1043 // Check for divide/remainder-by-zero.
1044 //
Ted Kremenekb31af242008-02-28 09:25:22 +00001045 // First, "assume" that the denominator is 0 or undefined.
Ted Kremenekef0007f2008-02-26 02:15:56 +00001046
Ted Kremenek75f32c62008-03-07 19:04:53 +00001047 bool isFeasibleZero = false;
1048 ValueState* ZeroSt = Assume(St, RightV, false, isFeasibleZero);
Ted Kremenekef0007f2008-02-26 02:15:56 +00001049
Ted Kremenek5a600862008-02-26 22:27:51 +00001050 // Second, "assume" that the denominator cannot be 0.
Ted Kremenekef0007f2008-02-26 02:15:56 +00001051
Ted Kremenek75f32c62008-03-07 19:04:53 +00001052 bool isFeasibleNotZero = false;
1053 St = Assume(St, RightV, true, isFeasibleNotZero);
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001054
Ted Kremenek75f32c62008-03-07 19:04:53 +00001055 // Create the node for the divide-by-zero (if it occurred).
1056
1057 if (isFeasibleZero)
1058 if (NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2)) {
1059 DivZeroNode->markAsSink();
1060
1061 if (isFeasibleNotZero)
1062 ImplicitBadDivides.insert(DivZeroNode);
1063 else
1064 ExplicitBadDivides.insert(DivZeroNode);
1065
1066 }
1067
1068 if (!isFeasibleNotZero)
Ted Kremenek5a600862008-02-26 22:27:51 +00001069 continue;
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001070 }
1071
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001072 // Fall-through. The logic below processes the divide.
1073 }
1074
Ted Kremenekc2d07202008-02-28 20:32:03 +00001075
Ted Kremenek15cb0782008-02-06 22:50:25 +00001076 if (Op <= BinaryOperator::Or) {
1077
Ted Kremenek07baa252008-02-21 18:02:17 +00001078 // Process non-assignements except commas or short-circuited
1079 // logical expressions (LAnd and LOr).
1080
1081 RVal Result = EvalBinOp(Op, LeftV, RightV);
1082
1083 if (Result.isUnknown()) {
1084 Dst.Add(N2);
Ted Kremeneke1f38b62008-02-07 01:08:27 +00001085 continue;
1086 }
1087
Ted Kremenekc2d07202008-02-28 20:32:03 +00001088 if (Result.isUndef() && !LeftV.isUndef() && !RightV.isUndef()) {
1089
1090 // The operands were not undefined, but the result is undefined.
1091
1092 if (NodeTy* UndefNode = Builder->generateNode(B, St, N2)) {
1093 UndefNode->markAsSink();
1094 UndefResults.insert(UndefNode);
1095 }
1096
1097 continue;
1098 }
1099
Ted Kremenek07baa252008-02-21 18:02:17 +00001100 Nodify(Dst, B, N2, SetRVal(St, B, Result));
Ted Kremenek15cb0782008-02-06 22:50:25 +00001101 continue;
1102 }
Ted Kremenek07baa252008-02-21 18:02:17 +00001103
1104 // Process assignments.
1105
1106 switch (Op) {
1107
Ted Kremenekf031b872008-01-23 19:59:44 +00001108 case BinaryOperator::Assign: {
Ted Kremenek07baa252008-02-21 18:02:17 +00001109
1110 // Simple assignments.
Ted Kremenekbf988d02008-02-19 00:22:37 +00001111
Ted Kremenekb31af242008-02-28 09:25:22 +00001112 if (LeftV.isUndef()) {
1113 HandleUndefinedStore(B, N2);
Ted Kremenek07baa252008-02-21 18:02:17 +00001114 continue;
1115 }
1116
1117 if (LeftV.isUnknown()) {
1118 St = SetRVal(St, B, RightV);
1119 break;
1120 }
Ted Kremenekbf988d02008-02-19 00:22:37 +00001121
Ted Kremenek07baa252008-02-21 18:02:17 +00001122 St = SetRVal(SetRVal(St, B, RightV), cast<LVal>(LeftV), RightV);
Ted Kremenekf031b872008-01-23 19:59:44 +00001123 break;
1124 }
1125
Ted Kremenek07baa252008-02-21 18:02:17 +00001126 // Compound assignment operators.
Ted Kremenek19072e02008-01-29 19:43:15 +00001127
Ted Kremenek07baa252008-02-21 18:02:17 +00001128 default: {
Ted Kremenekbf988d02008-02-19 00:22:37 +00001129
Ted Kremenek5a600862008-02-26 22:27:51 +00001130 assert (B->isCompoundAssignmentOp());
1131
1132 if (Op >= BinaryOperator::AndAssign)
1133 ((int&) Op) -= (BinaryOperator::AndAssign - BinaryOperator::And);
1134 else
1135 ((int&) Op) -= BinaryOperator::MulAssign;
1136
Ted Kremenekb31af242008-02-28 09:25:22 +00001137 // Check if the LHS is undefined.
Ted Kremenek07baa252008-02-21 18:02:17 +00001138
Ted Kremenekb31af242008-02-28 09:25:22 +00001139 if (LeftV.isUndef()) {
1140 HandleUndefinedStore(B, N2);
Ted Kremenek07baa252008-02-21 18:02:17 +00001141 continue;
1142 }
1143
1144 if (LeftV.isUnknown()) {
Ted Kremenek80cb2c82008-03-09 08:12:37 +00001145 assert (isa<UnknownVal>(GetRVal(St, B)));
1146 Dst.Add(N2);
1147 continue;
Ted Kremenekbf988d02008-02-19 00:22:37 +00001148 }
1149
Ted Kremenek07baa252008-02-21 18:02:17 +00001150 // At this pointer we know that the LHS evaluates to an LVal
Ted Kremenek80cb2c82008-03-09 08:12:37 +00001151 // that is neither "Unknown" or "Undefined."
Ted Kremenek07baa252008-02-21 18:02:17 +00001152
1153 LVal LeftLV = cast<LVal>(LeftV);
1154
Ted Kremenek07baa252008-02-21 18:02:17 +00001155 // Fetch the value of the LHS (the value of the variable, etc.).
1156
Ted Kremenek50ef5ff2008-03-10 04:11:42 +00001157 RVal V = GetRVal(GetState(N1), LeftLV, B->getLHS()->getType());
Ted Kremenek07baa252008-02-21 18:02:17 +00001158
Ted Kremenekb31af242008-02-28 09:25:22 +00001159 // Propagate undefined value (left-side). We
1160 // propogate undefined values for the RHS below when
Ted Kremenek5a600862008-02-26 22:27:51 +00001161 // we also check for divide-by-zero.
Ted Kremenek07baa252008-02-21 18:02:17 +00001162
Ted Kremenekb31af242008-02-28 09:25:22 +00001163 if (V.isUndef()) {
Ted Kremenek07baa252008-02-21 18:02:17 +00001164 St = SetRVal(St, B, V);
1165 break;
1166 }
1167
1168 // Propagate unknown values.
1169
Ted Kremenekb8782e12008-02-21 19:15:37 +00001170 if (V.isUnknown()) {
Ted Kremenek80cb2c82008-03-09 08:12:37 +00001171 // The value bound to LeftV is unknown. Thus we just
1172 // propagate the current node (as "B" is already bound to nothing).
1173 assert (isa<UnknownVal>(GetRVal(St, B)));
Ted Kremenekb8782e12008-02-21 19:15:37 +00001174 Dst.Add(N2);
1175 continue;
1176 }
Ted Kremenek07baa252008-02-21 18:02:17 +00001177
1178 if (RightV.isUnknown()) {
Ted Kremenek80cb2c82008-03-09 08:12:37 +00001179 assert (isa<UnknownVal>(GetRVal(St, B)));
1180 St = SetRVal(St, LeftLV, UnknownVal());
Ted Kremenek07baa252008-02-21 18:02:17 +00001181 break;
1182 }
1183
Ted Kremenek5a600862008-02-26 22:27:51 +00001184 // At this point:
1185 //
Ted Kremenekb31af242008-02-28 09:25:22 +00001186 // The LHS is not Undef/Unknown.
Ted Kremenek5a600862008-02-26 22:27:51 +00001187 // The RHS is not Unknown.
Ted Kremenek15cb0782008-02-06 22:50:25 +00001188
Ted Kremenek9cfda3f2008-02-21 18:43:30 +00001189 // Get the computation type.
1190 QualType CTy = cast<CompoundAssignOperator>(B)->getComputationType();
1191
1192 // Perform promotions.
1193 V = EvalCast(V, CTy);
Ted Kremenek666ab922008-02-21 18:46:24 +00001194 RightV = EvalCast(RightV, CTy);
Ted Kremenek9cfda3f2008-02-21 18:43:30 +00001195
1196 // Evaluate operands and promote to result type.
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001197
Ted Kremenek2c369792008-02-25 18:42:54 +00001198 if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem)
1199 && RHS->getType()->isIntegerType()) {
1200
Ted Kremenekb31af242008-02-28 09:25:22 +00001201 // Check if the denominator is undefined.
Ted Kremenekef0007f2008-02-26 02:15:56 +00001202
Ted Kremenekb31af242008-02-28 09:25:22 +00001203 if (RightV.isUndef()) {
1204 NodeTy* DivUndef = Builder->generateNode(B, St, N2);
Ted Kremenekef0007f2008-02-26 02:15:56 +00001205
Ted Kremenekb31af242008-02-28 09:25:22 +00001206 if (DivUndef) {
1207 DivUndef->markAsSink();
Ted Kremenek75f32c62008-03-07 19:04:53 +00001208 ExplicitBadDivides.insert(DivUndef);
Ted Kremenekef0007f2008-02-26 02:15:56 +00001209 }
1210
1211 continue;
1212 }
Ted Kremenek5a600862008-02-26 22:27:51 +00001213
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001214 // First, "assume" that the denominator is 0.
1215
Ted Kremenek75f32c62008-03-07 19:04:53 +00001216 bool isFeasibleZero = false;
1217 ValueState* ZeroSt = Assume(St, RightV, false, isFeasibleZero);
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001218
Ted Kremenek75f32c62008-03-07 19:04:53 +00001219 // Second, "assume" that the denominator cannot be 0.
1220
1221 bool isFeasibleNotZero = false;
1222 St = Assume(St, RightV, true, isFeasibleNotZero);
1223
1224 // Create the node for the divide-by-zero error (if it occurred).
1225
1226 if (isFeasibleZero) {
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001227 NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2);
1228
1229 if (DivZeroNode) {
1230 DivZeroNode->markAsSink();
Ted Kremenek75f32c62008-03-07 19:04:53 +00001231
1232 if (isFeasibleNotZero)
1233 ImplicitBadDivides.insert(DivZeroNode);
1234 else
1235 ExplicitBadDivides.insert(DivZeroNode);
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001236 }
1237 }
1238
Ted Kremenek75f32c62008-03-07 19:04:53 +00001239 if (!isFeasibleNotZero)
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001240 continue;
1241
1242 // Fall-through. The logic below processes the divide.
1243 }
Ted Kremenek5a600862008-02-26 22:27:51 +00001244 else {
1245
Ted Kremenekb31af242008-02-28 09:25:22 +00001246 // Propagate undefined values (right-side).
Ted Kremenek5a600862008-02-26 22:27:51 +00001247
Ted Kremenekb31af242008-02-28 09:25:22 +00001248 if (RightV.isUndef()) {
Ted Kremenek5a600862008-02-26 22:27:51 +00001249 St = SetRVal(SetRVal(St, B, RightV), LeftLV, RightV);
1250 break;
1251 }
1252
1253 }
Ted Kremenek6ff5f7f2008-02-25 17:51:31 +00001254
Ted Kremenek9cfda3f2008-02-21 18:43:30 +00001255 RVal Result = EvalCast(EvalBinOp(Op, V, RightV), B->getType());
Ted Kremenekc2d07202008-02-28 20:32:03 +00001256
1257 if (Result.isUndef()) {
1258
1259 // The operands were not undefined, but the result is undefined.
1260
1261 if (NodeTy* UndefNode = Builder->generateNode(B, St, N2)) {
1262 UndefNode->markAsSink();
1263 UndefResults.insert(UndefNode);
1264 }
1265
1266 continue;
1267 }
1268
Ted Kremenek07baa252008-02-21 18:02:17 +00001269 St = SetRVal(SetRVal(St, B, Result), LeftLV, Result);
Ted Kremenek15cb0782008-02-06 22:50:25 +00001270 }
Ted Kremenekf031b872008-01-23 19:59:44 +00001271 }
Ted Kremenek07baa252008-02-21 18:02:17 +00001272
1273 Nodify(Dst, B, N2, St);
Ted Kremenekafba4b22008-01-16 00:53:15 +00001274 }
Ted Kremenek68d70a82008-01-15 23:55:06 +00001275 }
Ted Kremenek68d70a82008-01-15 23:55:06 +00001276}
Ted Kremenekd2500ab2008-01-16 18:18:48 +00001277
Ted Kremenekb31af242008-02-28 09:25:22 +00001278void GRExprEngine::HandleUndefinedStore(Stmt* S, NodeTy* Pred) {
Ted Kremenek50ef5ff2008-03-10 04:11:42 +00001279 NodeTy* N = Builder->generateNode(S, GetState(Pred), Pred);
Ted Kremenekbf988d02008-02-19 00:22:37 +00001280 N->markAsSink();
Ted Kremenekb31af242008-02-28 09:25:22 +00001281 UndefStores.insert(N);
Ted Kremenekbf988d02008-02-19 00:22:37 +00001282}
Ted Kremenekbe962452008-01-16 19:42:59 +00001283
Ted Kremenekbf988d02008-02-19 00:22:37 +00001284void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) {
Ted Kremenekf031b872008-01-23 19:59:44 +00001285
1286 // FIXME: add metadata to the CFG so that we can disable
1287 // this check when we KNOW that there is no block-level subexpression.
1288 // The motivation is that this check requires a hashtable lookup.
1289
1290 if (S != CurrentStmt && getCFG().isBlkExpr(S)) {
1291 Dst.Add(Pred);
1292 return;
1293 }
1294
1295 switch (S->getStmtClass()) {
Ted Kremenek5bde36b2008-02-12 21:37:25 +00001296
1297 default:
1298 // Cases we intentionally have "default" handle:
Ted Kremenek9b496f92008-02-26 19:17:09 +00001299 // AddrLabelExpr, IntegerLiteral, CharacterLiteral
Ted Kremenek5bde36b2008-02-12 21:37:25 +00001300
1301 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
1302 break;
1303
Ted Kremenek744a7862008-02-08 20:29:23 +00001304 case Stmt::BinaryOperatorClass: {
1305 BinaryOperator* B = cast<BinaryOperator>(S);
Ted Kremenek1f0eb992008-02-05 00:26:40 +00001306
Ted Kremenek744a7862008-02-08 20:29:23 +00001307 if (B->isLogicalOp()) {
1308 VisitLogicalExpr(B, Pred, Dst);
Ted Kremenek1f0eb992008-02-05 00:26:40 +00001309 break;
1310 }
Ted Kremenek744a7862008-02-08 20:29:23 +00001311 else if (B->getOpcode() == BinaryOperator::Comma) {
Ted Kremenek50ef5ff2008-03-10 04:11:42 +00001312 ValueState* St = GetState(Pred);
Ted Kremenek07baa252008-02-21 18:02:17 +00001313 Nodify(Dst, B, Pred, SetRVal(St, B, GetRVal(St, B->getRHS())));
Ted Kremenek106f37c2008-02-08 07:05:39 +00001314 break;
1315 }
Ted Kremenekfd85f292008-02-12 19:49:57 +00001316
1317 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1318 break;
1319 }
Ted Kremenekd9268e32008-02-19 01:44:53 +00001320
1321 case Stmt::CallExprClass: {
1322 CallExpr* C = cast<CallExpr>(S);
1323 VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
1324 break;
1325 }
Ted Kremenekfd85f292008-02-12 19:49:57 +00001326
1327 case Stmt::CastExprClass: {
1328 CastExpr* C = cast<CastExpr>(S);
1329 VisitCast(C, C->getSubExpr(), Pred, Dst);
1330 break;
Ted Kremenek744a7862008-02-08 20:29:23 +00001331 }
Ted Kremenek9b496f92008-02-26 19:17:09 +00001332
Ted Kremenek07baa252008-02-21 18:02:17 +00001333 // FIXME: ChooseExpr is really a constant. We need to fix
1334 // the CFG do not model them as explicit control-flow.
1335
Ted Kremenekfd85f292008-02-12 19:49:57 +00001336 case Stmt::ChooseExprClass: { // __builtin_choose_expr
1337 ChooseExpr* C = cast<ChooseExpr>(S);
1338 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
1339 break;
1340 }
Ted Kremenek1f0eb992008-02-05 00:26:40 +00001341
Ted Kremenek9914e9c2008-01-23 23:38:00 +00001342 case Stmt::CompoundAssignOperatorClass:
Ted Kremenekf031b872008-01-23 19:59:44 +00001343 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1344 break;
1345
Ted Kremenekfd85f292008-02-12 19:49:57 +00001346 case Stmt::ConditionalOperatorClass: { // '?' operator
1347 ConditionalOperator* C = cast<ConditionalOperator>(S);
1348 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
1349 break;
1350 }
1351
1352 case Stmt::DeclRefExprClass:
1353 VisitDeclRefExpr(cast<DeclRefExpr>(S), Pred, Dst);
1354 break;
1355
1356 case Stmt::DeclStmtClass:
1357 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
1358 break;
1359
1360 case Stmt::ImplicitCastExprClass: {
1361 ImplicitCastExpr* C = cast<ImplicitCastExpr>(S);
1362 VisitCast(C, C->getSubExpr(), Pred, Dst);
1363 break;
1364 }
1365
1366 case Stmt::ParenExprClass:
1367 Visit(cast<ParenExpr>(S)->getSubExpr(), Pred, Dst);
1368 break;
1369
1370 case Stmt::SizeOfAlignOfTypeExprClass:
1371 VisitSizeOfAlignOfTypeExpr(cast<SizeOfAlignOfTypeExpr>(S), Pred, Dst);
1372 break;
1373
Ted Kremenek106f37c2008-02-08 07:05:39 +00001374 case Stmt::StmtExprClass: {
Ted Kremenek744a7862008-02-08 20:29:23 +00001375 StmtExpr* SE = cast<StmtExpr>(S);
1376
Ted Kremenek50ef5ff2008-03-10 04:11:42 +00001377 ValueState* St = GetState(Pred);
Ted Kremenek744a7862008-02-08 20:29:23 +00001378 Expr* LastExpr = cast<Expr>(*SE->getSubStmt()->body_rbegin());
Ted Kremenek07baa252008-02-21 18:02:17 +00001379 Nodify(Dst, SE, Pred, SetRVal(St, SE, GetRVal(St, LastExpr)));
Ted Kremenek106f37c2008-02-08 07:05:39 +00001380 break;
1381 }
1382
Ted Kremenek07baa252008-02-21 18:02:17 +00001383 // FIXME: We may wish to always bind state to ReturnStmts so
1384 // that users can quickly query what was the state at the
1385 // exit points of a function.
1386
Ted Kremenekfd85f292008-02-12 19:49:57 +00001387 case Stmt::ReturnStmtClass: {
Ted Kremeneke1f38b62008-02-07 01:08:27 +00001388 if (Expr* R = cast<ReturnStmt>(S)->getRetValue())
1389 Visit(R, Pred, Dst);
1390 else
1391 Dst.Add(Pred);
1392
1393 break;
Ted Kremenekfd85f292008-02-12 19:49:57 +00001394 }
Ted Kremeneke1f38b62008-02-07 01:08:27 +00001395
Ted Kremenekb996ebc2008-02-20 04:02:35 +00001396 case Stmt::UnaryOperatorClass: {
1397 UnaryOperator* U = cast<UnaryOperator>(S);
1398
Ted Kremenek07baa252008-02-21 18:02:17 +00001399 switch (U->getOpcode()) {
1400 case UnaryOperator::Deref: VisitDeref(U, Pred, Dst); break;
1401 case UnaryOperator::Plus: Visit(U->getSubExpr(), Pred, Dst); break;
1402 case UnaryOperator::SizeOf: VisitSizeOfExpr(U, Pred, Dst); break;
1403 default: VisitUnaryOperator(U, Pred, Dst); break;
1404 }
Ted Kremenekb996ebc2008-02-20 04:02:35 +00001405
Ted Kremenekb9c30e32008-01-24 20:55:43 +00001406 break;
Ted Kremenekb996ebc2008-02-20 04:02:35 +00001407 }
Ted Kremenekab8ed952008-01-17 18:25:22 +00001408 }
Ted Kremenekbe962452008-01-16 19:42:59 +00001409}
1410
Ted Kremenekd2500ab2008-01-16 18:18:48 +00001411//===----------------------------------------------------------------------===//
Ted Kremenek90960972008-01-30 23:03:39 +00001412// "Assume" logic.
1413//===----------------------------------------------------------------------===//
1414
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001415ValueState* GRExprEngine::Assume(ValueState* St, LVal Cond,
Ted Kremenekbc965a62008-02-18 22:57:02 +00001416 bool Assumption,
Ted Kremenek07baa252008-02-21 18:02:17 +00001417 bool& isFeasible) {
Ted Kremenek6e24a802008-02-01 06:36:40 +00001418 switch (Cond.getSubKind()) {
1419 default:
Ted Kremenek07baa252008-02-21 18:02:17 +00001420 assert (false && "'Assume' not implemented for this LVal.");
Ted Kremenek6e24a802008-02-01 06:36:40 +00001421 return St;
1422
Ted Kremenek13f31562008-02-06 00:54:14 +00001423 case lval::SymbolValKind:
1424 if (Assumption)
1425 return AssumeSymNE(St, cast<lval::SymbolVal>(Cond).getSymbol(),
Ted Kremenek8ad19872008-03-07 20:13:31 +00001426 BasicVals.getZeroWithPtrWidth(), isFeasible);
Ted Kremenek13f31562008-02-06 00:54:14 +00001427 else
1428 return AssumeSymEQ(St, cast<lval::SymbolVal>(Cond).getSymbol(),
Ted Kremenek8ad19872008-03-07 20:13:31 +00001429 BasicVals.getZeroWithPtrWidth(), isFeasible);
Ted Kremenek13f31562008-02-06 00:54:14 +00001430
Ted Kremenek0033fbb2008-02-06 04:31:33 +00001431
Ted Kremenek1b63a3b2008-02-05 21:52:21 +00001432 case lval::DeclValKind:
Ted Kremenek38706192008-02-22 00:54:56 +00001433 case lval::FuncValKind:
1434 case lval::GotoLabelKind:
Ted Kremenek6e24a802008-02-01 06:36:40 +00001435 isFeasible = Assumption;
1436 return St;
Ted Kremenek13f31562008-02-06 00:54:14 +00001437
Ted Kremenek1b63a3b2008-02-05 21:52:21 +00001438 case lval::ConcreteIntKind: {
1439 bool b = cast<lval::ConcreteInt>(Cond).getValue() != 0;
Ted Kremenek6e24a802008-02-01 06:36:40 +00001440 isFeasible = b ? Assumption : !Assumption;
1441 return St;
1442 }
1443 }
Ted Kremenek90960972008-01-30 23:03:39 +00001444}
1445
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001446ValueState* GRExprEngine::Assume(ValueState* St, NonLVal Cond,
Ted Kremenek13f31562008-02-06 00:54:14 +00001447 bool Assumption,
Ted Kremenek07baa252008-02-21 18:02:17 +00001448 bool& isFeasible) {
Ted Kremenek90960972008-01-30 23:03:39 +00001449 switch (Cond.getSubKind()) {
1450 default:
Ted Kremenek07baa252008-02-21 18:02:17 +00001451 assert (false && "'Assume' not implemented for this NonLVal.");
Ted Kremenek90960972008-01-30 23:03:39 +00001452 return St;
1453
Ted Kremenekab359c12008-02-06 17:32:17 +00001454
1455 case nonlval::SymbolValKind: {
Ted Kremenek5bde36b2008-02-12 21:37:25 +00001456 nonlval::SymbolVal& SV = cast<nonlval::SymbolVal>(Cond);
Ted Kremenekab359c12008-02-06 17:32:17 +00001457 SymbolID sym = SV.getSymbol();
1458
1459 if (Assumption)
Ted Kremenek8ad19872008-03-07 20:13:31 +00001460 return AssumeSymNE(St, sym, BasicVals.getValue(0, SymMgr.getType(sym)),
Ted Kremenekab359c12008-02-06 17:32:17 +00001461 isFeasible);
1462 else
Ted Kremenek8ad19872008-03-07 20:13:31 +00001463 return AssumeSymEQ(St, sym, BasicVals.getValue(0, SymMgr.getType(sym)),
Ted Kremenekab359c12008-02-06 17:32:17 +00001464 isFeasible);
1465 }
1466
Ted Kremenek0033fbb2008-02-06 04:31:33 +00001467 case nonlval::SymIntConstraintValKind:
1468 return
1469 AssumeSymInt(St, Assumption,
1470 cast<nonlval::SymIntConstraintVal>(Cond).getConstraint(),
1471 isFeasible);
1472
Ted Kremenek1b63a3b2008-02-05 21:52:21 +00001473 case nonlval::ConcreteIntKind: {
1474 bool b = cast<nonlval::ConcreteInt>(Cond).getValue() != 0;
Ted Kremenek90960972008-01-30 23:03:39 +00001475 isFeasible = b ? Assumption : !Assumption;
1476 return St;
1477 }
1478 }
1479}
1480
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001481ValueState*
1482GRExprEngine::AssumeSymNE(ValueState* St, SymbolID sym,
Ted Kremenek13f31562008-02-06 00:54:14 +00001483 const llvm::APSInt& V, bool& isFeasible) {
Ted Kremenekbc965a62008-02-18 22:57:02 +00001484
Ted Kremenek13f31562008-02-06 00:54:14 +00001485 // First, determine if sym == X, where X != V.
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001486 if (const llvm::APSInt* X = St->getSymVal(sym)) {
Ted Kremenek13f31562008-02-06 00:54:14 +00001487 isFeasible = *X != V;
1488 return St;
1489 }
1490
1491 // Second, determine if sym != V.
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001492 if (St->isNotEqual(sym, V)) {
Ted Kremenek13f31562008-02-06 00:54:14 +00001493 isFeasible = true;
1494 return St;
1495 }
1496
1497 // If we reach here, sym is not a constant and we don't know if it is != V.
1498 // Make that assumption.
1499
1500 isFeasible = true;
1501 return StateMgr.AddNE(St, sym, V);
1502}
1503
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001504ValueState*
1505GRExprEngine::AssumeSymEQ(ValueState* St, SymbolID sym,
Ted Kremenek13f31562008-02-06 00:54:14 +00001506 const llvm::APSInt& V, bool& isFeasible) {
1507
1508 // First, determine if sym == X, where X != V.
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001509 if (const llvm::APSInt* X = St->getSymVal(sym)) {
Ted Kremenek13f31562008-02-06 00:54:14 +00001510 isFeasible = *X == V;
1511 return St;
1512 }
1513
1514 // Second, determine if sym != V.
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001515 if (St->isNotEqual(sym, V)) {
Ted Kremenek13f31562008-02-06 00:54:14 +00001516 isFeasible = false;
1517 return St;
1518 }
1519
1520 // If we reach here, sym is not a constant and we don't know if it is == V.
1521 // Make that assumption.
1522
1523 isFeasible = true;
1524 return StateMgr.AddEQ(St, sym, V);
1525}
Ted Kremenek90960972008-01-30 23:03:39 +00001526
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001527ValueState*
1528GRExprEngine::AssumeSymInt(ValueState* St, bool Assumption,
Ted Kremenek0033fbb2008-02-06 04:31:33 +00001529 const SymIntConstraint& C, bool& isFeasible) {
1530
1531 switch (C.getOpcode()) {
1532 default:
1533 // No logic yet for other operators.
1534 return St;
1535
1536 case BinaryOperator::EQ:
1537 if (Assumption)
1538 return AssumeSymEQ(St, C.getSymbol(), C.getInt(), isFeasible);
1539 else
1540 return AssumeSymNE(St, C.getSymbol(), C.getInt(), isFeasible);
1541
1542 case BinaryOperator::NE:
1543 if (Assumption)
1544 return AssumeSymNE(St, C.getSymbol(), C.getInt(), isFeasible);
1545 else
1546 return AssumeSymEQ(St, C.getSymbol(), C.getInt(), isFeasible);
1547 }
1548}
1549
Ted Kremenek90960972008-01-30 23:03:39 +00001550//===----------------------------------------------------------------------===//
Ted Kremenek3862eb12008-02-14 22:36:46 +00001551// Visualization.
Ted Kremenekd2500ab2008-01-16 18:18:48 +00001552//===----------------------------------------------------------------------===//
1553
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001554#ifndef NDEBUG
Ted Kremenek30fa28b2008-02-13 17:41:41 +00001555static GRExprEngine* GraphPrintCheckerState;
Ted Kremenek8b41e8c2008-03-07 20:57:30 +00001556static SourceManager* GraphPrintSourceManager;
Ted Kremenek428d39e2008-01-30 23:24:39 +00001557
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001558namespace llvm {
1559template<>
Ted Kremenek30fa28b2008-02-13 17:41:41 +00001560struct VISIBILITY_HIDDEN DOTGraphTraits<GRExprEngine::NodeTy*> :
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001561 public DefaultDOTGraphTraits {
Ted Kremenek08cfd832008-02-08 21:10:02 +00001562
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001563 static void PrintVarBindings(std::ostream& Out, ValueState* St) {
Ted Kremenek08cfd832008-02-08 21:10:02 +00001564
1565 Out << "Variables:\\l";
1566
Ted Kremenek3ec7be92008-01-24 22:27:20 +00001567 bool isFirst = true;
1568
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001569 for (ValueState::vb_iterator I=St->vb_begin(), E=St->vb_end(); I!=E;++I) {
Ted Kremenek08cfd832008-02-08 21:10:02 +00001570
1571 if (isFirst)
1572 isFirst = false;
1573 else
1574 Out << "\\l";
1575
1576 Out << ' ' << I.getKey()->getName() << " : ";
1577 I.getData().print(Out);
1578 }
1579
1580 }
1581
Ted Kremenek17c5f112008-02-11 19:21:59 +00001582
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001583 static void PrintSubExprBindings(std::ostream& Out, ValueState* St){
Ted Kremenek17c5f112008-02-11 19:21:59 +00001584
1585 bool isFirst = true;
1586
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001587 for (ValueState::seb_iterator I=St->seb_begin(), E=St->seb_end();I!=E;++I) {
Ted Kremenek17c5f112008-02-11 19:21:59 +00001588
1589 if (isFirst) {
1590 Out << "\\l\\lSub-Expressions:\\l";
1591 isFirst = false;
1592 }
1593 else
1594 Out << "\\l";
1595
1596 Out << " (" << (void*) I.getKey() << ") ";
1597 I.getKey()->printPretty(Out);
1598 Out << " : ";
1599 I.getData().print(Out);
1600 }
1601 }
1602
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001603 static void PrintBlkExprBindings(std::ostream& Out, ValueState* St){
Ted Kremenek17c5f112008-02-11 19:21:59 +00001604
Ted Kremenek08cfd832008-02-08 21:10:02 +00001605 bool isFirst = true;
1606
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001607 for (ValueState::beb_iterator I=St->beb_begin(), E=St->beb_end(); I!=E;++I){
Ted Kremenek3ec7be92008-01-24 22:27:20 +00001608 if (isFirst) {
Ted Kremenek17c5f112008-02-11 19:21:59 +00001609 Out << "\\l\\lBlock-level Expressions:\\l";
Ted Kremenek3ec7be92008-01-24 22:27:20 +00001610 isFirst = false;
1611 }
1612 else
1613 Out << "\\l";
Ted Kremenek08cfd832008-02-08 21:10:02 +00001614
Ted Kremenek17c5f112008-02-11 19:21:59 +00001615 Out << " (" << (void*) I.getKey() << ") ";
1616 I.getKey()->printPretty(Out);
Ted Kremenek3ec7be92008-01-24 22:27:20 +00001617 Out << " : ";
1618 I.getData().print(Out);
1619 }
1620 }
1621
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001622 static void PrintEQ(std::ostream& Out, ValueState* St) {
1623 ValueState::ConstEqTy CE = St->ConstEq;
Ted Kremeneke6536692008-02-06 03:56:15 +00001624
1625 if (CE.isEmpty())
1626 return;
1627
1628 Out << "\\l\\|'==' constraints:";
1629
Ted Kremenek07baa252008-02-21 18:02:17 +00001630 for (ValueState::ConstEqTy::iterator I=CE.begin(), E=CE.end(); I!=E;++I)
Ted Kremeneke6536692008-02-06 03:56:15 +00001631 Out << "\\l $" << I.getKey() << " : " << I.getData()->toString();
1632 }
1633
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001634 static void PrintNE(std::ostream& Out, ValueState* St) {
1635 ValueState::ConstNotEqTy NE = St->ConstNotEq;
Ted Kremeneke6536692008-02-06 03:56:15 +00001636
1637 if (NE.isEmpty())
1638 return;
1639
1640 Out << "\\l\\|'!=' constraints:";
1641
Ted Kremenek07baa252008-02-21 18:02:17 +00001642 for (ValueState::ConstNotEqTy::iterator I=NE.begin(), EI=NE.end();
Ted Kremeneke6536692008-02-06 03:56:15 +00001643 I != EI; ++I){
1644
1645 Out << "\\l $" << I.getKey() << " : ";
1646 bool isFirst = true;
1647
1648 ValueState::IntSetTy::iterator J=I.getData().begin(),
1649 EJ=I.getData().end();
1650 for ( ; J != EJ; ++J) {
1651 if (isFirst) isFirst = false;
1652 else Out << ", ";
1653
1654 Out << (*J)->toString();
1655 }
1656 }
Ted Kremeneka853de62008-02-14 22:54:53 +00001657 }
1658
1659 static std::string getNodeAttributes(const GRExprEngine::NodeTy* N, void*) {
1660
1661 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
Ted Kremenekbf988d02008-02-19 00:22:37 +00001662 GraphPrintCheckerState->isExplicitNullDeref(N) ||
Ted Kremenekb31af242008-02-28 09:25:22 +00001663 GraphPrintCheckerState->isUndefDeref(N) ||
1664 GraphPrintCheckerState->isUndefStore(N) ||
1665 GraphPrintCheckerState->isUndefControlFlow(N) ||
Ted Kremenek75f32c62008-03-07 19:04:53 +00001666 GraphPrintCheckerState->isExplicitBadDivide(N) ||
1667 GraphPrintCheckerState->isImplicitBadDivide(N) ||
Ted Kremenek43863eb2008-02-29 23:14:48 +00001668 GraphPrintCheckerState->isUndefResult(N) ||
Ted Kremenek9b31f5b2008-02-29 23:53:11 +00001669 GraphPrintCheckerState->isBadCall(N) ||
1670 GraphPrintCheckerState->isUndefArg(N))
Ted Kremeneka853de62008-02-14 22:54:53 +00001671 return "color=\"red\",style=\"filled\"";
1672
Ted Kremenekc2d07202008-02-28 20:32:03 +00001673 if (GraphPrintCheckerState->isNoReturnCall(N))
1674 return "color=\"blue\",style=\"filled\"";
1675
Ted Kremeneka853de62008-02-14 22:54:53 +00001676 return "";
1677 }
Ted Kremeneke6536692008-02-06 03:56:15 +00001678
Ted Kremenek30fa28b2008-02-13 17:41:41 +00001679 static std::string getNodeLabel(const GRExprEngine::NodeTy* N, void*) {
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001680 std::ostringstream Out;
Ted Kremenekbacd6cd2008-01-23 22:30:44 +00001681
1682 // Program Location.
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001683 ProgramPoint Loc = N->getLocation();
1684
1685 switch (Loc.getKind()) {
1686 case ProgramPoint::BlockEntranceKind:
1687 Out << "Block Entrance: B"
1688 << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
1689 break;
1690
1691 case ProgramPoint::BlockExitKind:
1692 assert (false);
1693 break;
1694
1695 case ProgramPoint::PostStmtKind: {
Ted Kremenek8b41e8c2008-03-07 20:57:30 +00001696 const PostStmt& L = cast<PostStmt>(Loc);
1697 Stmt* S = L.getStmt();
1698 SourceLocation SLoc = S->getLocStart();
1699
1700 Out << S->getStmtClassName() << ' ' << (void*) S << ' ';
1701 S->printPretty(Out);
Ted Kremenek3ec7be92008-01-24 22:27:20 +00001702
Ted Kremenekf97c6682008-03-09 03:30:59 +00001703 if (SLoc.isFileID()) {
1704 Out << "\\lline="
1705 << GraphPrintSourceManager->getLineNumber(SLoc) << " col="
1706 << GraphPrintSourceManager->getColumnNumber(SLoc) << "\\l";
1707 }
Ted Kremenek80d52d02008-02-07 05:48:01 +00001708
Ted Kremenek43863eb2008-02-29 23:14:48 +00001709 if (GraphPrintCheckerState->isImplicitNullDeref(N))
Ted Kremenek80d52d02008-02-07 05:48:01 +00001710 Out << "\\|Implicit-Null Dereference.\\l";
Ted Kremenek43863eb2008-02-29 23:14:48 +00001711 else if (GraphPrintCheckerState->isExplicitNullDeref(N))
Ted Kremenekae7bdc12008-02-07 06:04:18 +00001712 Out << "\\|Explicit-Null Dereference.\\l";
Ted Kremenek43863eb2008-02-29 23:14:48 +00001713 else if (GraphPrintCheckerState->isUndefDeref(N))
Ted Kremenekb31af242008-02-28 09:25:22 +00001714 Out << "\\|Dereference of undefialied value.\\l";
Ted Kremenek43863eb2008-02-29 23:14:48 +00001715 else if (GraphPrintCheckerState->isUndefStore(N))
Ted Kremenekb31af242008-02-28 09:25:22 +00001716 Out << "\\|Store to Undefined LVal.";
Ted Kremenek75f32c62008-03-07 19:04:53 +00001717 else if (GraphPrintCheckerState->isExplicitBadDivide(N))
1718 Out << "\\|Explicit divide-by zero or undefined value.";
1719 else if (GraphPrintCheckerState->isImplicitBadDivide(N))
1720 Out << "\\|Implicit divide-by zero or undefined value.";
Ted Kremenek43863eb2008-02-29 23:14:48 +00001721 else if (GraphPrintCheckerState->isUndefResult(N))
Ted Kremenekc2d07202008-02-28 20:32:03 +00001722 Out << "\\|Result of operation is undefined.";
Ted Kremenekc2d07202008-02-28 20:32:03 +00001723 else if (GraphPrintCheckerState->isNoReturnCall(N))
1724 Out << "\\|Call to function marked \"noreturn\".";
Ted Kremenek43863eb2008-02-29 23:14:48 +00001725 else if (GraphPrintCheckerState->isBadCall(N))
1726 Out << "\\|Call to NULL/Undefined.";
Ted Kremenek9b31f5b2008-02-29 23:53:11 +00001727 else if (GraphPrintCheckerState->isUndefArg(N))
1728 Out << "\\|Argument in call is undefined";
Ted Kremenek80d52d02008-02-07 05:48:01 +00001729
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001730 break;
1731 }
1732
1733 default: {
1734 const BlockEdge& E = cast<BlockEdge>(Loc);
1735 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
1736 << E.getDst()->getBlockID() << ')';
Ted Kremenek90960972008-01-30 23:03:39 +00001737
1738 if (Stmt* T = E.getSrc()->getTerminator()) {
Ted Kremenek8b41e8c2008-03-07 20:57:30 +00001739
1740 SourceLocation SLoc = T->getLocStart();
1741
Ted Kremenek90960972008-01-30 23:03:39 +00001742 Out << "\\|Terminator: ";
Ted Kremenek8b41e8c2008-03-07 20:57:30 +00001743
Ted Kremenek90960972008-01-30 23:03:39 +00001744 E.getSrc()->printTerminator(Out);
1745
Ted Kremenekf97c6682008-03-09 03:30:59 +00001746 if (SLoc.isFileID()) {
1747 Out << "\\lline="
1748 << GraphPrintSourceManager->getLineNumber(SLoc) << " col="
1749 << GraphPrintSourceManager->getColumnNumber(SLoc);
1750 }
Ted Kremenek8b41e8c2008-03-07 20:57:30 +00001751
Ted Kremenekaee121c2008-02-13 23:08:21 +00001752 if (isa<SwitchStmt>(T)) {
1753 Stmt* Label = E.getDst()->getLabel();
1754
1755 if (Label) {
1756 if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
1757 Out << "\\lcase ";
1758 C->getLHS()->printPretty(Out);
1759
1760 if (Stmt* RHS = C->getRHS()) {
1761 Out << " .. ";
1762 RHS->printPretty(Out);
1763 }
1764
1765 Out << ":";
1766 }
1767 else {
1768 assert (isa<DefaultStmt>(Label));
1769 Out << "\\ldefault:";
1770 }
1771 }
1772 else
1773 Out << "\\l(implicit) default:";
1774 }
1775 else if (isa<IndirectGotoStmt>(T)) {
Ted Kremenek90960972008-01-30 23:03:39 +00001776 // FIXME
1777 }
1778 else {
1779 Out << "\\lCondition: ";
1780 if (*E.getSrc()->succ_begin() == E.getDst())
1781 Out << "true";
1782 else
1783 Out << "false";
1784 }
1785
1786 Out << "\\l";
1787 }
Ted Kremenek428d39e2008-01-30 23:24:39 +00001788
Ted Kremenekb31af242008-02-28 09:25:22 +00001789 if (GraphPrintCheckerState->isUndefControlFlow(N)) {
1790 Out << "\\|Control-flow based on\\lUndefined value.\\l";
Ted Kremenek428d39e2008-01-30 23:24:39 +00001791 }
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001792 }
1793 }
1794
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001795 Out << "\\|StateID: " << (void*) N->getState() << "\\|";
Ted Kremenek08cfd832008-02-08 21:10:02 +00001796
Ted Kremenekf4b49df2008-02-28 10:21:43 +00001797 N->getState()->printDOT(Out);
Ted Kremenekbacd6cd2008-01-23 22:30:44 +00001798
Ted Kremenekbacd6cd2008-01-23 22:30:44 +00001799 Out << "\\l";
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001800 return Out.str();
1801 }
1802};
1803} // end llvm namespace
1804#endif
1805
Ted Kremenek5e1e05c2008-03-07 22:58:01 +00001806#ifndef NDEBUG
1807template <typename ITERATOR>
1808static void AddSources(llvm::SmallVector<GRExprEngine::NodeTy*, 10>& Sources,
1809 ITERATOR I, ITERATOR E) {
1810
1811 for ( ; I != E; ++I )
1812 Sources.push_back(*I);
1813}
1814#endif
1815
1816void GRExprEngine::ViewGraph(bool trim) {
Ted Kremenekdd9e97d2008-01-16 21:46:15 +00001817#ifndef NDEBUG
Ted Kremenek3862eb12008-02-14 22:36:46 +00001818 GraphPrintCheckerState = this;
Ted Kremenek8b41e8c2008-03-07 20:57:30 +00001819 GraphPrintSourceManager = &getContext().getSourceManager();
Ted Kremenek5e1e05c2008-03-07 22:58:01 +00001820
1821 if (trim) {
1822 llvm::SmallVector<NodeTy*, 10> Sources;
1823 AddSources(Sources, null_derefs_begin(), null_derefs_end());
1824 AddSources(Sources, undef_derefs_begin(), undef_derefs_end());
1825
1826 GRExprEngine::GraphTy* TrimmedG = G.Trim(&Sources[0],
1827 &Sources[0]+Sources.size());
1828
1829 if (!TrimmedG)
1830 llvm::cerr << "warning: Trimmed ExplodedGraph is empty.\n";
1831 else {
1832 llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedGRExprEngine");
1833 delete TrimmedG;
1834 }
1835 }
1836 else
1837 llvm::ViewGraph(*G.roots_begin(), "GRExprEngine");
1838
1839
Ted Kremenek428d39e2008-01-30 23:24:39 +00001840 GraphPrintCheckerState = NULL;
Ted Kremenek8b41e8c2008-03-07 20:57:30 +00001841 GraphPrintSourceManager = NULL;
Ted Kremenek3862eb12008-02-14 22:36:46 +00001842#endif
Ted Kremenekd2500ab2008-01-16 18:18:48 +00001843}