blob: 243c0788769776e300361e59c5d0473e65cdf658 [file] [log] [blame]
Ted Kremenek77349cb2008-02-14 22:13:12 +00001//=-- GRExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
Ted Kremenek64924852008-01-31 02:35:41 +00002//
Ted Kremenek4af84312008-01-31 06:49:09 +00003// The LLVM Compiler Infrastructure
Ted Kremenekd27f8162008-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 Kremenek77349cb2008-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 Kremenekd27f8162008-01-15 23:55:06 +000013//
14//===----------------------------------------------------------------------===//
15
Ted Kremenek77349cb2008-02-14 22:13:12 +000016#include "clang/Analysis/PathSensitive/GRExprEngine.h"
Ted Kremeneke01c9872008-02-14 22:36:46 +000017#include "clang/Analysis/PathSensitive/GRTransferFuncs.h"
18
19#include "llvm/Support/Streams.h"
Ted Kremenekb387a3f2008-02-14 22:16:04 +000020
21using namespace clang;
22using llvm::dyn_cast;
23using llvm::cast;
24using llvm::APSInt;
Ted Kremenekab2b8c52008-01-23 19:59:44 +000025
Ted Kremenek4d4dd852008-02-13 17:41:41 +000026GRExprEngine::StateTy
27GRExprEngine::SetValue(StateTy St, Expr* S, const RValue& V) {
Ted Kremenek3271f8d2008-02-07 04:16:04 +000028
Ted Kremeneke070a1d2008-02-04 21:59:01 +000029 if (!StateCleaned) {
30 St = RemoveDeadBindings(CurrentStmt, St);
31 StateCleaned = true;
32 }
Ted Kremenek3271f8d2008-02-07 04:16:04 +000033
Ted Kremeneke070a1d2008-02-04 21:59:01 +000034 bool isBlkExpr = false;
Ted Kremenek3271f8d2008-02-07 04:16:04 +000035
Ted Kremeneke070a1d2008-02-04 21:59:01 +000036 if (S == CurrentStmt) {
37 isBlkExpr = getCFG().isBlkExpr(S);
38
39 if (!isBlkExpr)
40 return St;
41 }
Ted Kremenek3271f8d2008-02-07 04:16:04 +000042
Ted Kremeneke070a1d2008-02-04 21:59:01 +000043 return StateMgr.SetValue(St, S, isBlkExpr, V);
44}
45
Ted Kremenek4d4dd852008-02-13 17:41:41 +000046const GRExprEngine::StateTy::BufferTy&
47GRExprEngine::SetValue(StateTy St, Expr* S, const RValue::BufferTy& RB,
Ted Kremenekcba2e432008-02-05 19:35:18 +000048 StateTy::BufferTy& RetBuf) {
49
50 assert (RetBuf.empty());
51
52 for (RValue::BufferTy::const_iterator I=RB.begin(), E=RB.end(); I!=E; ++I)
53 RetBuf.push_back(SetValue(St, S, *I));
54
55 return RetBuf;
56}
57
Ted Kremenek4d4dd852008-02-13 17:41:41 +000058GRExprEngine::StateTy
59GRExprEngine::SetValue(StateTy St, const LValue& LV, const RValue& V) {
Ted Kremeneke070a1d2008-02-04 21:59:01 +000060
Ted Kremenek53c641a2008-02-08 03:02:48 +000061 if (LV.isUnknown())
Ted Kremeneke070a1d2008-02-04 21:59:01 +000062 return St;
63
64 if (!StateCleaned) {
65 St = RemoveDeadBindings(CurrentStmt, St);
66 StateCleaned = true;
67 }
68
69 return StateMgr.SetValue(St, LV, V);
70}
71
Ted Kremenek4d4dd852008-02-13 17:41:41 +000072void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term,
Ted Kremenek71c29bd2008-01-29 23:32:35 +000073 BranchNodeBuilder& builder) {
Ted Kremenekb38911f2008-01-30 23:03:39 +000074
Ted Kremeneke7d22112008-02-11 19:21:59 +000075 // Remove old bindings for subexpressions.
76 StateTy PrevState = StateMgr.RemoveSubExprBindings(builder.getState());
Ted Kremenekf233d482008-02-05 00:26:40 +000077
Ted Kremenekb2331832008-02-15 22:29:00 +000078 // Check for NULL conditions; e.g. "for(;;)"
79 if (!Condition) {
80 builder.markInfeasible(false);
81
82 // Get the current block counter.
83 GRBlockCounter BC = builder.getBlockCounter();
84 unsigned BlockID = builder.getTargetBlock(true)->getBlockID();
85 unsigned NumVisited = BC.getNumVisited(BlockID);
86
87 if (NumVisited < 1) builder.generateNode(PrevState, true);
88 else builder.markInfeasible(true);
89
90 return;
91 }
92
Ted Kremenekb38911f2008-01-30 23:03:39 +000093 RValue V = GetValue(PrevState, Condition);
94
95 switch (V.getBaseKind()) {
96 default:
97 break;
98
Ted Kremenek53c641a2008-02-08 03:02:48 +000099 case RValue::UnknownKind:
Ted Kremenekb38911f2008-01-30 23:03:39 +0000100 builder.generateNode(PrevState, true);
101 builder.generateNode(PrevState, false);
102 return;
103
104 case RValue::UninitializedKind: {
105 NodeTy* N = builder.generateNode(PrevState, true);
106
107 if (N) {
108 N->markAsSink();
109 UninitBranches.insert(N);
110 }
111
112 builder.markInfeasible(false);
113 return;
114 }
115 }
Ted Kremenekb2331832008-02-15 22:29:00 +0000116
Ted Kremenek8e49dd62008-02-12 18:08:17 +0000117 // Get the current block counter.
118 GRBlockCounter BC = builder.getBlockCounter();
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000119 unsigned BlockID = builder.getTargetBlock(true)->getBlockID();
120 unsigned NumVisited = BC.getNumVisited(BlockID);
Ted Kremenekf233d482008-02-05 00:26:40 +0000121
Ted Kremenek8e49dd62008-02-12 18:08:17 +0000122 if (isa<nonlval::ConcreteInt>(V) ||
123 BC.getNumVisited(builder.getTargetBlock(true)->getBlockID()) < 1) {
124
125 // Process the true branch.
Ted Kremenekb38911f2008-01-30 23:03:39 +0000126
Ted Kremenek8e49dd62008-02-12 18:08:17 +0000127 bool isFeasible = true;
128
129 StateTy St = Assume(PrevState, V, true, isFeasible);
130
131 if (isFeasible)
132 builder.generateNode(St, true);
133 else
134 builder.markInfeasible(true);
Ted Kremenekb38911f2008-01-30 23:03:39 +0000135 }
Ted Kremenek8e49dd62008-02-12 18:08:17 +0000136 else
137 builder.markInfeasible(true);
Ted Kremenekb38911f2008-01-30 23:03:39 +0000138
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000139 BlockID = builder.getTargetBlock(false)->getBlockID();
140 NumVisited = BC.getNumVisited(BlockID);
Ted Kremenekb38911f2008-01-30 23:03:39 +0000141
Ted Kremenek8e49dd62008-02-12 18:08:17 +0000142 if (isa<nonlval::ConcreteInt>(V) ||
143 BC.getNumVisited(builder.getTargetBlock(false)->getBlockID()) < 1) {
144
145 // Process the false branch.
146
147 bool isFeasible = false;
148
149 StateTy St = Assume(PrevState, V, false, isFeasible);
150
151 if (isFeasible)
152 builder.generateNode(St, false);
153 else
154 builder.markInfeasible(false);
155 }
Ted Kremenekf233d482008-02-05 00:26:40 +0000156 else
157 builder.markInfeasible(false);
Ted Kremenek71c29bd2008-01-29 23:32:35 +0000158}
159
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000160/// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor
Ted Kremenek754607e2008-02-13 00:24:44 +0000161/// nodes by processing the 'effects' of a computed goto jump.
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000162void GRExprEngine::ProcessIndirectGoto(IndirectGotoNodeBuilder& builder) {
Ted Kremenek754607e2008-02-13 00:24:44 +0000163
164 StateTy St = builder.getState();
165 LValue V = cast<LValue>(GetValue(St, builder.getTarget()));
166
167 // Three possibilities:
168 //
169 // (1) We know the computed label.
170 // (2) The label is NULL (or some other constant), or Uninitialized.
171 // (3) We have no clue about the label. Dispatch to all targets.
172 //
173
174 typedef IndirectGotoNodeBuilder::iterator iterator;
175
176 if (isa<lval::GotoLabel>(V)) {
177 LabelStmt* L = cast<lval::GotoLabel>(V).getLabel();
178
179 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) {
Ted Kremenek24f1a962008-02-13 17:27:37 +0000180 if (I.getLabel() == L) {
181 builder.generateNode(I, St);
Ted Kremenek754607e2008-02-13 00:24:44 +0000182 return;
183 }
184 }
185
186 assert (false && "No block with label.");
187 return;
188 }
189
190 if (isa<lval::ConcreteInt>(V) || isa<UninitializedVal>(V)) {
191 // Dispatch to the first target and mark it as a sink.
Ted Kremenek24f1a962008-02-13 17:27:37 +0000192 NodeTy* N = builder.generateNode(builder.begin(), St, true);
Ted Kremenek754607e2008-02-13 00:24:44 +0000193 UninitBranches.insert(N);
194 return;
195 }
196
197 // This is really a catch-all. We don't support symbolics yet.
198
199 assert (isa<UnknownVal>(V));
200
201 for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
Ted Kremenek24f1a962008-02-13 17:27:37 +0000202 builder.generateNode(I, St);
Ted Kremenek754607e2008-02-13 00:24:44 +0000203}
Ted Kremenekf233d482008-02-05 00:26:40 +0000204
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000205/// ProcessSwitch - Called by GRCoreEngine. Used to generate successor
206/// nodes by processing the 'effects' of a switch statement.
207void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) {
208
209 typedef SwitchNodeBuilder::iterator iterator;
210
211 StateTy St = builder.getState();
Ted Kremenek692416c2008-02-18 22:57:02 +0000212 Expr* CondE = builder.getCondition();
213 NonLValue CondV = cast<NonLValue>(GetValue(St, CondE));
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000214
215 if (isa<UninitializedVal>(CondV)) {
216 NodeTy* N = builder.generateDefaultCaseNode(St, true);
217 UninitBranches.insert(N);
218 return;
219 }
220
221 StateTy DefaultSt = St;
222
223 // While most of this can be assumed (such as the signedness), having it
224 // just computed makes sure everything makes the same assumptions end-to-end.
Ted Kremenek692416c2008-02-18 22:57:02 +0000225
226 unsigned bits = getContext().getTypeSize(CondE->getType(),
227 CondE->getExprLoc());
228
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000229 APSInt V1(bits, false);
230 APSInt V2 = V1;
231
232 for (iterator I=builder.begin(), E=builder.end(); I!=E; ++I) {
233
234 CaseStmt* Case = cast<CaseStmt>(I.getCase());
235
236 // Evaluate the case.
237 if (!Case->getLHS()->isIntegerConstantExpr(V1, getContext(), 0, true)) {
238 assert (false && "Case condition must evaluate to an integer constant.");
239 return;
240 }
241
242 // Get the RHS of the case, if it exists.
243
244 if (Expr* E = Case->getRHS()) {
245 if (!E->isIntegerConstantExpr(V2, getContext(), 0, true)) {
246 assert (false &&
247 "Case condition (RHS) must evaluate to an integer constant.");
248 return ;
249 }
250
251 assert (V1 <= V2);
252 }
253 else V2 = V1;
254
255 // FIXME: Eventually we should replace the logic below with a range
256 // comparison, rather than concretize the values within the range.
257 // This should be easy once we have "ranges" for NonLValues.
258
259 do {
260 nonlval::ConcreteInt CaseVal(ValMgr.getValue(V1));
261
Ted Kremenekde434242008-02-19 01:44:53 +0000262 NonLValue Res = EvalBinaryOp(BinaryOperator::EQ, CondV, CaseVal);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000263
264 // Now "assume" that the case matches.
Ted Kremenek692416c2008-02-18 22:57:02 +0000265 bool isFeasible = false;
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000266
Ted Kremenek6cb0b542008-02-14 19:37:24 +0000267 StateTy StNew = Assume(St, Res, true, isFeasible);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000268
269 if (isFeasible) {
270 builder.generateCaseStmtNode(I, StNew);
271
272 // If CondV evaluates to a constant, then we know that this
273 // is the *only* case that we can take, so stop evaluating the
274 // others.
275 if (isa<nonlval::ConcreteInt>(CondV))
276 return;
277 }
278
279 // Now "assume" that the case doesn't match. Add this state
280 // to the default state (if it is feasible).
281
Ted Kremenek6cb0b542008-02-14 19:37:24 +0000282 StNew = Assume(DefaultSt, Res, false, isFeasible);
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000283
284 if (isFeasible)
285 DefaultSt = StNew;
286
287 // Concretize the next value in the range.
288 ++V1;
289
290 } while (V1 < V2);
291 }
292
293 // If we reach here, than we know that the default branch is
294 // possible.
295 builder.generateDefaultCaseNode(DefaultSt);
296}
297
298
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000299void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred,
Ted Kremenekf233d482008-02-05 00:26:40 +0000300 NodeSet& Dst) {
301
302 bool hasR2;
303 StateTy PrevState = Pred->getState();
304
305 RValue R1 = GetValue(PrevState, B->getLHS());
306 RValue R2 = GetValue(PrevState, B->getRHS(), hasR2);
Ted Kremenek9dca0622008-02-19 00:22:37 +0000307
308 if (hasR2) {
309 if (isa<UninitializedVal>(R2) || isa<UnknownVal>(R2)) {
310 Nodify(Dst, B, Pred, SetValue(PrevState, B, R2));
311 return;
312 }
313 }
314 else if (isa<UninitializedVal>(R1) || isa<UnknownVal>(R1)) {
Ted Kremenekf233d482008-02-05 00:26:40 +0000315 Nodify(Dst, B, Pred, SetValue(PrevState, B, R1));
316 return;
317 }
318
319 // R1 is an expression that can evaluate to either 'true' or 'false'.
320 if (B->getOpcode() == BinaryOperator::LAnd) {
321 // hasR2 == 'false' means that LHS evaluated to 'false' and that
322 // we short-circuited, leading to a value of '0' for the '&&' expression.
323 if (hasR2 == false) {
324 Nodify(Dst, B, Pred, SetValue(PrevState, B, GetRValueConstant(0U, B)));
325 return;
326 }
327 }
328 else {
329 assert (B->getOpcode() == BinaryOperator::LOr);
330 // hasR2 == 'false' means that the LHS evaluate to 'true' and that
331 // we short-circuited, leading to a value of '1' for the '||' expression.
332 if (hasR2 == false) {
333 Nodify(Dst, B, Pred, SetValue(PrevState, B, GetRValueConstant(1U, B)));
334 return;
335 }
336 }
337
338 // If we reach here we did not short-circuit. Assume R2 == true and
339 // R2 == false.
340
341 bool isFeasible;
342 StateTy St = Assume(PrevState, R2, true, isFeasible);
343
344 if (isFeasible)
345 Nodify(Dst, B, Pred, SetValue(PrevState, B, GetRValueConstant(1U, B)));
346
347 St = Assume(PrevState, R2, false, isFeasible);
348
349 if (isFeasible)
350 Nodify(Dst, B, Pred, SetValue(PrevState, B, GetRValueConstant(0U, B)));
351}
352
353
354
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000355void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
Ted Kremenekd27f8162008-01-15 23:55:06 +0000356 Builder = &builder;
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000357
358 StmtEntryNode = builder.getLastNode();
359 CurrentStmt = S;
360 NodeSet Dst;
361 StateCleaned = false;
362
363 Visit(S, StmtEntryNode, Dst);
364
365 // If no nodes were generated, generate a new node that has all the
366 // dead mappings removed.
367 if (Dst.size() == 1 && *Dst.begin() == StmtEntryNode) {
368 StateTy St = RemoveDeadBindings(S, StmtEntryNode->getState());
369 builder.generateNode(S, St, StmtEntryNode);
370 }
Ted Kremenekf84469b2008-01-18 00:41:32 +0000371
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000372 CurrentStmt = NULL;
373 StmtEntryNode = NULL;
374 Builder = NULL;
Ted Kremenekd27f8162008-01-15 23:55:06 +0000375}
376
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000377GRExprEngine::NodeTy*
378GRExprEngine::Nodify(NodeSet& Dst, Stmt* S, NodeTy* Pred, StateTy St) {
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000379
380 // If the state hasn't changed, don't generate a new node.
Ted Kremenek7e593362008-02-07 15:20:13 +0000381 if (St == Pred->getState())
Ted Kremenekd131c4f2008-02-07 05:48:01 +0000382 return NULL;
Ted Kremenekcb448ca2008-01-16 00:53:15 +0000383
Ted Kremenekd131c4f2008-02-07 05:48:01 +0000384 NodeTy* N = Builder->generateNode(S, St, Pred);
385 Dst.Add(N);
386 return N;
Ted Kremenekcb448ca2008-01-16 00:53:15 +0000387}
Ted Kremenekd27f8162008-01-15 23:55:06 +0000388
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000389void GRExprEngine::Nodify(NodeSet& Dst, Stmt* S, NodeTy* Pred,
Ted Kremenekcba2e432008-02-05 19:35:18 +0000390 const StateTy::BufferTy& SB) {
391
392 for (StateTy::BufferTy::const_iterator I=SB.begin(), E=SB.end(); I!=E; ++I)
393 Nodify(Dst, S, Pred, *I);
394}
395
Ted Kremenek44842c22008-02-13 18:06:44 +0000396void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst){
Ted Kremenek3271f8d2008-02-07 04:16:04 +0000397 if (D != CurrentStmt) {
398 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
399 return;
400 }
401
402 // If we are here, we are loading the value of the decl and binding
403 // it to the block-level expression.
404
405 StateTy St = Pred->getState();
406
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000407 Nodify(Dst, D, Pred, SetValue(St, D, GetValue(St, D)));
Ted Kremenek3271f8d2008-02-07 04:16:04 +0000408}
409
Ted Kremenekde434242008-02-19 01:44:53 +0000410void GRExprEngine::VisitCall(CallExpr* CE, NodeTy* Pred,
411 CallExpr::arg_iterator I, CallExpr::arg_iterator E,
412 NodeSet& Dst) {
413
414 if (I != E) {
415 NodeSet DstTmp;
416 Visit(*I, Pred, DstTmp);
417 ++I;
418
419 for (NodeSet::iterator DI=DstTmp.begin(), DE=DstTmp.end(); DI!=DE; ++DI)
420 VisitCall(CE, *DI, I, E, Dst);
421
422 return;
423 }
424
425 // If we reach here we have processed all of the arguments. Evaluate
426 // the callee expression.
427 NodeSet DstTmp;
428 Visit(CE->getCallee(), Pred, DstTmp);
429
430 // Finally, evaluate the function call.
431 for (NodeSet::iterator DI=DstTmp.begin(), DE=DstTmp.end(); DI!=DE; ++DI) {
432 StateTy St = (*DI)->getState();
433 LValue L = GetLValue(St, CE->getCallee());
434
435 // Check for uninitialized control-flow.
436 if (isa<UninitializedVal>(L)) {
437 NodeTy* N = Builder->generateNode(CE, St, *DI);
438 N->markAsSink();
439 UninitBranches.insert(N);
440 continue;
441 }
442
443 // Note: EvalCall must handle the case where the callee is "UnknownVal."
444 Nodify(Dst, CE, *DI, EvalCall(CE, (*DI)->getState()));
445 }
446}
447
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000448void GRExprEngine::VisitCast(Expr* CastE, Expr* E, NodeTy* Pred, NodeSet& Dst) {
Ted Kremenek874d63f2008-01-24 02:02:54 +0000449
Ted Kremenek5d3003a2008-02-19 18:52:54 +0000450 NodeSet S1;
451 Visit(E, Pred, S1);
Ted Kremenek874d63f2008-01-24 02:02:54 +0000452
Ted Kremenek5d3003a2008-02-19 18:52:54 +0000453 QualType T = CastE->getType();
454
Ted Kremenek402563b2008-02-19 18:47:04 +0000455 // Check for redundant casts or casting to "void"
456 if (T->isVoidType() ||
457 E->getType() == T ||
Ted Kremenekde434242008-02-19 01:44:53 +0000458 (T->isPointerType() && E->getType()->isFunctionType())) {
Ted Kremenek5d3003a2008-02-19 18:52:54 +0000459
460 for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1)
461 Dst.Add(*I1);
462
Ted Kremenek874d63f2008-01-24 02:02:54 +0000463 return;
464 }
465
Ted Kremenek874d63f2008-01-24 02:02:54 +0000466 for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) {
467 NodeTy* N = *I1;
468 StateTy St = N->getState();
Ted Kremenekbd03f1d2008-01-28 22:09:13 +0000469 const RValue& V = GetValue(St, E);
Ted Kremenekd59cccc2008-02-14 18:28:23 +0000470 Nodify(Dst, CastE, N, SetValue(St, CastE, EvalCast(ValMgr, V, CastE)));
Ted Kremenek874d63f2008-01-24 02:02:54 +0000471 }
Ted Kremenek9de04c42008-01-24 20:55:43 +0000472}
473
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000474void GRExprEngine::VisitDeclStmt(DeclStmt* DS, GRExprEngine::NodeTy* Pred,
475 GRExprEngine::NodeSet& Dst) {
Ted Kremenek9de04c42008-01-24 20:55:43 +0000476
477 StateTy St = Pred->getState();
478
479 for (const ScopedDecl* D = DS->getDecl(); D; D = D->getNextDeclarator())
Ted Kremenek403c1812008-01-28 22:51:57 +0000480 if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
Ted Kremenekc2c95b02008-02-19 00:29:51 +0000481
482 // FIXME: Add support for local arrays.
483 if (VD->getType()->isArrayType())
484 continue;
485
Ted Kremenek403c1812008-01-28 22:51:57 +0000486 const Expr* E = VD->getInit();
Ted Kremenek329f8542008-02-05 21:52:21 +0000487 St = SetValue(St, lval::DeclVal(VD),
Ted Kremenek22031182008-02-08 02:57:34 +0000488 E ? GetValue(St, E) : UninitializedVal());
Ted Kremenek403c1812008-01-28 22:51:57 +0000489 }
Ted Kremenek9de04c42008-01-24 20:55:43 +0000490
491 Nodify(Dst, DS, Pred, St);
492
493 if (Dst.empty())
494 Dst.Add(Pred);
495}
Ted Kremenek874d63f2008-01-24 02:02:54 +0000496
Ted Kremenekf233d482008-02-05 00:26:40 +0000497
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000498void GRExprEngine::VisitGuardedExpr(Expr* S, Expr* LHS, Expr* RHS,
Ted Kremenekf233d482008-02-05 00:26:40 +0000499 NodeTy* Pred, NodeSet& Dst) {
500
501 StateTy St = Pred->getState();
502
503 RValue R = GetValue(St, LHS);
Ted Kremenek22031182008-02-08 02:57:34 +0000504 if (isa<UnknownVal>(R)) R = GetValue(St, RHS);
Ted Kremenekf233d482008-02-05 00:26:40 +0000505
506 Nodify(Dst, S, Pred, SetValue(St, S, R));
507}
508
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000509/// VisitSizeOfAlignOfTypeExpr - Transfer function for sizeof(type).
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000510void GRExprEngine::VisitSizeOfAlignOfTypeExpr(SizeOfAlignOfTypeExpr* S,
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000511 NodeTy* Pred,
512 NodeSet& Dst) {
513
514 // 6.5.3.4 sizeof: "The result type is an integer."
515
516 QualType T = S->getArgumentType();
517
518 // FIXME: Add support for VLAs.
Eli Friedmand8688562008-02-15 12:28:27 +0000519 if (!T.getTypePtr()->isConstantSizeType())
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000520 return;
521
522 SourceLocation L = S->getExprLoc();
523 uint64_t size = getContext().getTypeSize(T, L) / 8;
524
525 Nodify(Dst, S, Pred,
526 SetValue(Pred->getState(), S,
Ted Kremenekc6fbdcd2008-02-15 23:15:23 +0000527 NonLValue::GetValue(ValMgr, size, S->getType(), L)));
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000528
529}
530
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000531void GRExprEngine::VisitDeref(UnaryOperator* U, NodeTy* Pred, NodeSet& Dst) {
532
533 Expr* E = U->getSubExpr()->IgnoreParens();
534
535 NodeSet DstTmp;
536
537 if (!isa<DeclRefExpr>(E))
538 DstTmp.Add(Pred);
539 else
540 Visit(E, Pred, DstTmp);
541
542 for (NodeSet::iterator I=DstTmp.begin(), DE=DstTmp.end(); I != DE; ++I) {
543
544 NodeTy* N = *I;
545 StateTy St = N->getState();
546
547 // FIXME: Bifurcate when dereferencing a symbolic with no constraints?
548
549 LValue L = cast<LValue>(GetValue(St, E));
550
551 if (isa<UninitializedVal>(L)) {
552 NodeTy* Succ = Builder->generateNode(U, St, N);
553
554 if (Succ) {
555 Succ->markAsSink();
556 UninitDeref.insert(Succ);
557 }
558
559 continue;
560 }
561
562 if (L.isUnknown()) {
563 Dst.Add(N);
564 continue;
565 }
566
567 // After a dereference, one of two possible situations arise:
568 // (1) A crash, because the pointer was NULL.
569 // (2) The pointer is not NULL, and the dereference works.
570 //
571 // We add these assumptions.
572
573 bool isFeasibleNotNull;
574
575 // "Assume" that the pointer is Not-NULL.
576 StateTy StNotNull = Assume(St, L, true, isFeasibleNotNull);
577
578 if (isFeasibleNotNull) {
579 QualType T = U->getType();
580
581 // FIXME: Currently symbolic analysis "generates" new symbols
582 // for the contents of values. We need a better approach.
583
584 Nodify(Dst, U, N, SetValue(StNotNull, U, GetValue(StNotNull, L, &T)));
585 }
586
587 bool isFeasibleNull;
588
589 // "Assume" that the pointer is NULL.
590 StateTy StNull = Assume(St, L, false, isFeasibleNull);
591
592 if (isFeasibleNull) {
593 // We don't use "Nodify" here because the node will be a sink
594 // and we have no intention of processing it later.
595 NodeTy* NullNode = Builder->generateNode(U, StNull, N);
596
597 if (NullNode) {
598 NullNode->markAsSink();
599
600 if (isFeasibleNotNull)
601 ImplicitNullDeref.insert(NullNode);
602 else
603 ExplicitNullDeref.insert(NullNode);
604 }
605 }
606 }
607}
608
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000609void GRExprEngine::VisitUnaryOperator(UnaryOperator* U,
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000610 NodeTy* Pred, NodeSet& Dst) {
Ted Kremenek3271f8d2008-02-07 04:16:04 +0000611
Ted Kremenek7b8009a2008-01-24 02:28:56 +0000612 NodeSet S1;
Ted Kremenek3271f8d2008-02-07 04:16:04 +0000613
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000614 assert (U->getOpcode() != UnaryOperator::Deref);
615
616 switch (U->getOpcode()) {
617 case UnaryOperator::PostInc:
618 case UnaryOperator::PostDec:
619 case UnaryOperator::PreInc:
620 case UnaryOperator::PreDec:
621 case UnaryOperator::AddrOf:
622 // Evalue subexpression as an LValue.
623 VisitLValue(U->getSubExpr(), Pred, S1);
624 break;
625
626 case UnaryOperator::SizeOf:
627 case UnaryOperator::AlignOf:
628 // Do not evaluate subexpression.
629 S1.Add(Pred);
630 break;
631
632 default:
633 Visit(U->getSubExpr(), Pred, S1);
634 break;
635 }
636
Ted Kremenek7b8009a2008-01-24 02:28:56 +0000637 for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) {
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000638
Ted Kremenek7b8009a2008-01-24 02:28:56 +0000639 NodeTy* N1 = *I1;
640 StateTy St = N1->getState();
641
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000642 if (U->isIncrementDecrementOp()) {
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000643
644 // Handle ++ and -- (both pre- and post-increment).
645
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000646 const LValue& L1 = GetLValue(St, U->getSubExpr());
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000647 QualType T = U->getType();
648 RValue R1 = GetValue(St, L1, &T);
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000649
650 BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add
651 : BinaryOperator::Sub;
652
Ted Kremenekde434242008-02-19 01:44:53 +0000653 RValue Result = EvalBinaryOp(Op, R1, GetRValueConstant(1U, U));
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000654
655 if (U->isPostfix())
656 Nodify(Dst, U, N1, SetValue(SetValue(St, U, R1), L1, Result));
657 else
658 Nodify(Dst, U, N1, SetValue(SetValue(St, U, Result), L1, Result));
659
660 continue;
661 }
662
663 // Handle all other unary operators.
664
Ted Kremenek7b8009a2008-01-24 02:28:56 +0000665 switch (U->getOpcode()) {
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000666
Ted Kremenekdacbb4f2008-01-24 08:20:02 +0000667 case UnaryOperator::Minus: {
Ted Kremenekbd03f1d2008-01-28 22:09:13 +0000668 const NonLValue& R1 = cast<NonLValue>(GetValue(St, U->getSubExpr()));
Ted Kremenekc3f261d2008-02-14 18:40:24 +0000669 Nodify(Dst, U, N1, SetValue(St, U, EvalMinus(ValMgr, U, R1)));
Ted Kremenekdacbb4f2008-01-24 08:20:02 +0000670 break;
671 }
672
Ted Kremenekc5d3b4c2008-02-04 16:58:30 +0000673 case UnaryOperator::Not: {
674 const NonLValue& R1 = cast<NonLValue>(GetValue(St, U->getSubExpr()));
Ted Kremenekc3f261d2008-02-14 18:40:24 +0000675 Nodify(Dst, U, N1, SetValue(St, U, EvalComplement(ValMgr, R1)));
Ted Kremenekc5d3b4c2008-02-04 16:58:30 +0000676 break;
677 }
678
Ted Kremenekc60f0f72008-02-06 17:56:00 +0000679 case UnaryOperator::LNot: {
680 // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
681 //
682 // Note: technically we do "E == 0", but this is the same in the
683 // transfer functions as "0 == E".
684
685 RValue V1 = GetValue(St, U->getSubExpr());
686
687 if (isa<LValue>(V1)) {
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000688 const LValue& L1 = cast<LValue>(V1);
689 lval::ConcreteInt V2(ValMgr.getZeroWithPtrWidth());
690 Nodify(Dst, U, N1,
Ted Kremenekde434242008-02-19 01:44:53 +0000691 SetValue(St, U, EvalBinaryOp(BinaryOperator::EQ,
Ted Kremenek6cb0b542008-02-14 19:37:24 +0000692 L1, V2)));
Ted Kremenekc60f0f72008-02-06 17:56:00 +0000693 }
694 else {
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000695 const NonLValue& R1 = cast<NonLValue>(V1);
Ted Kremenekc60f0f72008-02-06 17:56:00 +0000696 nonlval::ConcreteInt V2(ValMgr.getZeroWithPtrWidth());
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000697 Nodify(Dst, U, N1,
Ted Kremenekde434242008-02-19 01:44:53 +0000698 SetValue(St, U, EvalBinaryOp(BinaryOperator::EQ,
Ted Kremenek6cb0b542008-02-14 19:37:24 +0000699 R1, V2)));
Ted Kremenekc60f0f72008-02-06 17:56:00 +0000700 }
701
702 break;
703 }
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000704
705 case UnaryOperator::SizeOf: {
706 // 6.5.3.4 sizeof: "The result type is an integer."
707
708 QualType T = U->getSubExpr()->getType();
709
710 // FIXME: Add support for VLAs.
Eli Friedmand8688562008-02-15 12:28:27 +0000711 if (!T.getTypePtr()->isConstantSizeType())
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000712 return;
713
714 SourceLocation L = U->getExprLoc();
715 uint64_t size = getContext().getTypeSize(T, L) / 8;
716
717 Nodify(Dst, U, N1,
718 SetValue(St, U, NonLValue::GetValue(ValMgr, size,
Ted Kremenekc6fbdcd2008-02-15 23:15:23 +0000719 U->getType(), L)));
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000720
721 break;
722 }
Ted Kremenekc60f0f72008-02-06 17:56:00 +0000723
Ted Kremenek64924852008-01-31 02:35:41 +0000724 case UnaryOperator::AddrOf: {
725 const LValue& L1 = GetLValue(St, U->getSubExpr());
726 Nodify(Dst, U, N1, SetValue(St, U, L1));
727 break;
728 }
Ted Kremenekd131c4f2008-02-07 05:48:01 +0000729
Ted Kremenek7b8009a2008-01-24 02:28:56 +0000730 default: ;
731 assert (false && "Not implemented.");
732 }
733 }
734}
735
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000736void GRExprEngine::VisitLValue(Expr* E, NodeTy* Pred, NodeSet& Dst) {
737
738 E = E->IgnoreParens();
739
Ted Kremenek3271f8d2008-02-07 04:16:04 +0000740 if (isa<DeclRefExpr>(E)) {
741 Dst.Add(Pred);
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +0000742 return;
Ted Kremenek3271f8d2008-02-07 04:16:04 +0000743 }
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +0000744
745 if (UnaryOperator* U = dyn_cast<UnaryOperator>(E)) {
746 if (U->getOpcode() == UnaryOperator::Deref) {
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000747 E = U->getSubExpr()->IgnoreParens();
748
749 if (isa<DeclRefExpr>(E))
750 Dst.Add(Pred);
751 else
752 Visit(E, Pred, Dst);
753
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +0000754 return;
755 }
756 }
757
758 Visit(E, Pred, Dst);
759}
760
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000761void GRExprEngine::VisitBinaryOperator(BinaryOperator* B,
Ted Kremenekdaeb9a72008-02-13 23:08:21 +0000762 GRExprEngine::NodeTy* Pred,
763 GRExprEngine::NodeSet& Dst) {
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000764 NodeSet S1;
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +0000765
766 if (B->isAssignmentOp())
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +0000767 VisitLValue(B->getLHS(), Pred, S1);
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +0000768 else
769 Visit(B->getLHS(), Pred, S1);
Ted Kremenekcb448ca2008-01-16 00:53:15 +0000770
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000771 for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) {
772 NodeTy* N1 = *I1;
Ted Kremeneke00fe3f2008-01-17 00:52:48 +0000773
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000774 // When getting the value for the LHS, check if we are in an assignment.
775 // In such cases, we want to (initially) treat the LHS as an LValue,
776 // so we use GetLValue instead of GetValue so that DeclRefExpr's are
Ted Kremenekbd03f1d2008-01-28 22:09:13 +0000777 // evaluated to LValueDecl's instead of to an NonLValue.
778 const RValue& V1 =
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000779 B->isAssignmentOp() ? GetLValue(N1->getState(), B->getLHS())
780 : GetValue(N1->getState(), B->getLHS());
Ted Kremenekcb448ca2008-01-16 00:53:15 +0000781
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000782 NodeSet S2;
783 Visit(B->getRHS(), N1, S2);
784
785 for (NodeSet::iterator I2=S2.begin(), E2=S2.end(); I2 != E2; ++I2) {
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000786
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000787 NodeTy* N2 = *I2;
788 StateTy St = N2->getState();
Ted Kremenekbd03f1d2008-01-28 22:09:13 +0000789 const RValue& V2 = GetValue(St, B->getRHS());
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000790
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000791 BinaryOperator::Opcode Op = B->getOpcode();
792
793 if (Op <= BinaryOperator::Or) {
794
Ted Kremenek22031182008-02-08 02:57:34 +0000795 if (isa<UnknownVal>(V1) || isa<UninitializedVal>(V1)) {
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +0000796 Nodify(Dst, B, N2, SetValue(St, B, V1));
797 continue;
798 }
799
Ted Kremenekde434242008-02-19 01:44:53 +0000800 Nodify(Dst, B, N2, SetValue(St, B, EvalBinaryOp(Op, V1, V2)));
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000801 continue;
Ted Kremenek3271f8d2008-02-07 04:16:04 +0000802
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000803 }
804
805 switch (Op) {
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000806 case BinaryOperator::Assign: {
807 const LValue& L1 = cast<LValue>(V1);
Ted Kremenek9dca0622008-02-19 00:22:37 +0000808
809 if (isa<UninitializedVal>(L1))
810 HandleUninitializedStore(B, N2);
811 else
812 Nodify(Dst, B, N2, SetValue(SetValue(St, B, V2), L1, V2));
813
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000814 break;
815 }
816
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000817 default: { // Compound assignment operators.
Ted Kremenek687af802008-01-29 19:43:15 +0000818
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000819 assert (B->isCompoundAssignmentOp());
820
821 const LValue& L1 = cast<LValue>(V1);
Ted Kremenek9dca0622008-02-19 00:22:37 +0000822
823 if (isa<UninitializedVal>(L1)) {
824 HandleUninitializedStore(B, N2);
825 break;
826 }
827
Ted Kremenekb5339122008-02-19 20:53:06 +0000828 if (isa<UninitializedVal>(V2)) {
829 Nodify(Dst, B, N2, SetValue(SetValue(St, B, V2), L1, V2));
830 break;
831 }
832
Ted Kremenek22031182008-02-08 02:57:34 +0000833 RValue Result = cast<NonLValue>(UnknownVal());
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000834
Ted Kremenekda9bd092008-02-08 07:05:39 +0000835 if (Op >= BinaryOperator::AndAssign)
836 ((int&) Op) -= (BinaryOperator::AndAssign - BinaryOperator::And);
837 else
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000838 ((int&) Op) -= BinaryOperator::MulAssign;
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000839
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000840 if (B->getType()->isPointerType()) { // Perform pointer arithmetic.
841 const NonLValue& R2 = cast<NonLValue>(V2);
Ted Kremenekde434242008-02-19 01:44:53 +0000842 Result = EvalBinaryOp(Op, L1, R2);
Ted Kremenek50d0ac22008-02-15 22:09:30 +0000843 }
Ted Kremenekb2331832008-02-15 22:29:00 +0000844 else if (isa<LValue>(V2)) {
Ted Kremenek687af802008-01-29 19:43:15 +0000845 const LValue& L2 = cast<LValue>(V2);
Ted Kremenekb2331832008-02-15 22:29:00 +0000846
847 if (B->getRHS()->getType()->isPointerType()) {
848 // LValue comparison.
Ted Kremenekde434242008-02-19 01:44:53 +0000849 Result = EvalBinaryOp(Op, L1, L2);
Ted Kremenekb2331832008-02-15 22:29:00 +0000850 }
851 else {
Ted Kremenekc6fbdcd2008-02-15 23:15:23 +0000852 QualType T1 = B->getLHS()->getType();
853 QualType T2 = B->getRHS()->getType();
854
Ted Kremenekb2331832008-02-15 22:29:00 +0000855 // An operation between two variables of a non-lvalue type.
856 Result =
Ted Kremenekde434242008-02-19 01:44:53 +0000857 EvalBinaryOp(Op,
Ted Kremenekc6fbdcd2008-02-15 23:15:23 +0000858 cast<NonLValue>(GetValue(N1->getState(), L1, &T1)),
859 cast<NonLValue>(GetValue(N2->getState(), L2, &T2)));
Ted Kremenekb2331832008-02-15 22:29:00 +0000860 }
Ted Kremenek687af802008-01-29 19:43:15 +0000861 }
Ted Kremenekb2331832008-02-15 22:29:00 +0000862 else { // Any other operation between two Non-LValues.
Ted Kremenekc6fbdcd2008-02-15 23:15:23 +0000863 QualType T = B->getLHS()->getType();
864 const NonLValue& R1 = cast<NonLValue>(GetValue(N1->getState(),
865 L1, &T));
Ted Kremenek687af802008-01-29 19:43:15 +0000866 const NonLValue& R2 = cast<NonLValue>(V2);
Ted Kremenekde434242008-02-19 01:44:53 +0000867 Result = EvalBinaryOp(Op, R1, R2);
Ted Kremenek687af802008-01-29 19:43:15 +0000868 }
869
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000870 Nodify(Dst, B, N2, SetValue(SetValue(St, B, Result), L1, Result));
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000871 break;
Ted Kremenekcf78b6a2008-02-06 22:50:25 +0000872 }
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000873 }
Ted Kremenekcb448ca2008-01-16 00:53:15 +0000874 }
Ted Kremenekd27f8162008-01-15 23:55:06 +0000875 }
Ted Kremenekd27f8162008-01-15 23:55:06 +0000876}
Ted Kremenekee985462008-01-16 18:18:48 +0000877
Ted Kremenek9dca0622008-02-19 00:22:37 +0000878void GRExprEngine::HandleUninitializedStore(Stmt* S, NodeTy* Pred) {
879
880 NodeTy* N = Builder->generateNode(S, Pred->getState(), Pred);
881 N->markAsSink();
882 UninitStores.insert(N);
883}
Ted Kremenek1ccd31c2008-01-16 19:42:59 +0000884
Ted Kremenek9dca0622008-02-19 00:22:37 +0000885void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) {
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000886
887 // FIXME: add metadata to the CFG so that we can disable
888 // this check when we KNOW that there is no block-level subexpression.
889 // The motivation is that this check requires a hashtable lookup.
890
891 if (S != CurrentStmt && getCFG().isBlkExpr(S)) {
892 Dst.Add(Pred);
893 return;
894 }
895
896 switch (S->getStmtClass()) {
Ted Kremenek230aaab2008-02-12 21:37:25 +0000897
898 default:
899 // Cases we intentionally have "default" handle:
Ted Kremenek72639102008-02-19 02:01:16 +0000900 // AddrLabelExpr
Ted Kremenek230aaab2008-02-12 21:37:25 +0000901
902 Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
903 break;
904
Ted Kremenekd70b62e2008-02-08 20:29:23 +0000905 case Stmt::BinaryOperatorClass: {
906 BinaryOperator* B = cast<BinaryOperator>(S);
Ted Kremenekf233d482008-02-05 00:26:40 +0000907
Ted Kremenekd70b62e2008-02-08 20:29:23 +0000908 if (B->isLogicalOp()) {
909 VisitLogicalExpr(B, Pred, Dst);
Ted Kremenekf233d482008-02-05 00:26:40 +0000910 break;
911 }
Ted Kremenekd70b62e2008-02-08 20:29:23 +0000912 else if (B->getOpcode() == BinaryOperator::Comma) {
Ted Kremenekda9bd092008-02-08 07:05:39 +0000913 StateTy St = Pred->getState();
Ted Kremenekd70b62e2008-02-08 20:29:23 +0000914 Nodify(Dst, B, Pred, SetValue(St, B, GetValue(St, B->getRHS())));
Ted Kremenekda9bd092008-02-08 07:05:39 +0000915 break;
916 }
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000917
918 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
919 break;
920 }
Ted Kremenekde434242008-02-19 01:44:53 +0000921
922 case Stmt::CallExprClass: {
923 CallExpr* C = cast<CallExpr>(S);
924 VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
925 break;
926 }
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000927
928 case Stmt::CastExprClass: {
929 CastExpr* C = cast<CastExpr>(S);
930 VisitCast(C, C->getSubExpr(), Pred, Dst);
931 break;
Ted Kremenekd70b62e2008-02-08 20:29:23 +0000932 }
Ted Kremenekf233d482008-02-05 00:26:40 +0000933
Ted Kremenek72639102008-02-19 02:01:16 +0000934 // While explicitly creating a node+state for visiting a CharacterLiteral
935 // seems wasteful, it also solves a bunch of problems when handling
936 // the ?, &&, and ||.
937
938 case Stmt::CharacterLiteralClass: {
939 CharacterLiteral* C = cast<CharacterLiteral>(S);
940 StateTy St = Pred->getState();
941 NonLValue X = NonLValue::GetValue(ValMgr, C->getValue(), C->getType(),
942 C->getLoc());
943 Nodify(Dst, C, Pred, SetValue(St, C, X));
944 break;
945 }
946
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000947 case Stmt::ChooseExprClass: { // __builtin_choose_expr
948 ChooseExpr* C = cast<ChooseExpr>(S);
949 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
950 break;
951 }
Ted Kremenekf233d482008-02-05 00:26:40 +0000952
Ted Kremenekb4ae33f2008-01-23 23:38:00 +0000953 case Stmt::CompoundAssignOperatorClass:
Ted Kremenekab2b8c52008-01-23 19:59:44 +0000954 VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
955 break;
956
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000957 case Stmt::ConditionalOperatorClass: { // '?' operator
958 ConditionalOperator* C = cast<ConditionalOperator>(S);
959 VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
960 break;
961 }
962
963 case Stmt::DeclRefExprClass:
964 VisitDeclRefExpr(cast<DeclRefExpr>(S), Pred, Dst);
965 break;
966
967 case Stmt::DeclStmtClass:
968 VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
969 break;
970
Ted Kremenek72639102008-02-19 02:01:16 +0000971 // While explicitly creating a node+state for visiting an IntegerLiteral
972 // seems wasteful, it also solves a bunch of problems when handling
973 // the ?, &&, and ||.
974
975 case Stmt::IntegerLiteralClass: {
976 StateTy St = Pred->getState();
977 IntegerLiteral* I = cast<IntegerLiteral>(S);
978 NonLValue X = NonLValue::GetValue(ValMgr, I);
979 Nodify(Dst, I, Pred, SetValue(St, I, X));
980 break;
981 }
982
Ted Kremenekd9435bf2008-02-12 19:49:57 +0000983 case Stmt::ImplicitCastExprClass: {
984 ImplicitCastExpr* C = cast<ImplicitCastExpr>(S);
985 VisitCast(C, C->getSubExpr(), Pred, Dst);
986 break;
987 }
988
989 case Stmt::ParenExprClass:
990 Visit(cast<ParenExpr>(S)->getSubExpr(), Pred, Dst);
991 break;
992
993 case Stmt::SizeOfAlignOfTypeExprClass:
994 VisitSizeOfAlignOfTypeExpr(cast<SizeOfAlignOfTypeExpr>(S), Pred, Dst);
995 break;
996
Ted Kremenekda9bd092008-02-08 07:05:39 +0000997 case Stmt::StmtExprClass: {
Ted Kremenekd70b62e2008-02-08 20:29:23 +0000998 StmtExpr* SE = cast<StmtExpr>(S);
999
Ted Kremenekda9bd092008-02-08 07:05:39 +00001000 StateTy St = Pred->getState();
Ted Kremenekd70b62e2008-02-08 20:29:23 +00001001 Expr* LastExpr = cast<Expr>(*SE->getSubStmt()->body_rbegin());
1002 Nodify(Dst, SE, Pred, SetValue(St, SE, GetValue(St, LastExpr)));
Ted Kremenekda9bd092008-02-08 07:05:39 +00001003 break;
1004 }
1005
Ted Kremenekd9435bf2008-02-12 19:49:57 +00001006 case Stmt::ReturnStmtClass: {
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00001007 if (Expr* R = cast<ReturnStmt>(S)->getRetValue())
1008 Visit(R, Pred, Dst);
1009 else
1010 Dst.Add(Pred);
1011
1012 break;
Ted Kremenekd9435bf2008-02-12 19:49:57 +00001013 }
Ted Kremenek5b6dc2d2008-02-07 01:08:27 +00001014
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00001015 case Stmt::UnaryOperatorClass: {
1016 UnaryOperator* U = cast<UnaryOperator>(S);
1017
1018 if (U->getOpcode() == UnaryOperator::Deref)
1019 VisitDeref(U, Pred, Dst);
1020 else
1021 VisitUnaryOperator(U, Pred, Dst);
1022
Ted Kremenek9de04c42008-01-24 20:55:43 +00001023 break;
Ted Kremenekd8e9f0d2008-02-20 04:02:35 +00001024 }
Ted Kremenek79649df2008-01-17 18:25:22 +00001025 }
Ted Kremenek1ccd31c2008-01-16 19:42:59 +00001026}
1027
Ted Kremenekee985462008-01-16 18:18:48 +00001028//===----------------------------------------------------------------------===//
Ted Kremenekb38911f2008-01-30 23:03:39 +00001029// "Assume" logic.
1030//===----------------------------------------------------------------------===//
1031
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001032GRExprEngine::StateTy GRExprEngine::Assume(StateTy St, LValue Cond,
Ted Kremenek692416c2008-02-18 22:57:02 +00001033 bool Assumption,
1034 bool& isFeasible) {
1035
1036 assert (!isa<UninitializedVal>(Cond));
1037
1038 if (isa<UnknownVal>(Cond)) {
1039 isFeasible = true;
1040 return St;
1041 }
Ted Kremeneka6e4d212008-02-01 06:36:40 +00001042
1043 switch (Cond.getSubKind()) {
1044 default:
Ted Kremenek862d5bb2008-02-06 00:54:14 +00001045 assert (false && "'Assume' not implemented for this LValue.");
Ted Kremeneka6e4d212008-02-01 06:36:40 +00001046 return St;
1047
Ted Kremenek862d5bb2008-02-06 00:54:14 +00001048 case lval::SymbolValKind:
1049 if (Assumption)
1050 return AssumeSymNE(St, cast<lval::SymbolVal>(Cond).getSymbol(),
1051 ValMgr.getZeroWithPtrWidth(), isFeasible);
1052 else
1053 return AssumeSymEQ(St, cast<lval::SymbolVal>(Cond).getSymbol(),
1054 ValMgr.getZeroWithPtrWidth(), isFeasible);
1055
Ted Kremenek08b66252008-02-06 04:31:33 +00001056
Ted Kremenek329f8542008-02-05 21:52:21 +00001057 case lval::DeclValKind:
Ted Kremeneka6e4d212008-02-01 06:36:40 +00001058 isFeasible = Assumption;
1059 return St;
Ted Kremenek862d5bb2008-02-06 00:54:14 +00001060
Ted Kremenek329f8542008-02-05 21:52:21 +00001061 case lval::ConcreteIntKind: {
1062 bool b = cast<lval::ConcreteInt>(Cond).getValue() != 0;
Ted Kremeneka6e4d212008-02-01 06:36:40 +00001063 isFeasible = b ? Assumption : !Assumption;
1064 return St;
1065 }
1066 }
Ted Kremenekb38911f2008-01-30 23:03:39 +00001067}
1068
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001069GRExprEngine::StateTy GRExprEngine::Assume(StateTy St, NonLValue Cond,
Ted Kremenek862d5bb2008-02-06 00:54:14 +00001070 bool Assumption,
Ted Kremeneka90ccfe2008-01-31 19:34:24 +00001071 bool& isFeasible) {
Ted Kremenekb38911f2008-01-30 23:03:39 +00001072
Ted Kremenek692416c2008-02-18 22:57:02 +00001073 assert (!isa<UninitializedVal>(Cond));
1074
1075 if (isa<UnknownVal>(Cond)) {
1076 isFeasible = true;
1077 return St;
1078 }
1079
Ted Kremenekb38911f2008-01-30 23:03:39 +00001080 switch (Cond.getSubKind()) {
1081 default:
1082 assert (false && "'Assume' not implemented for this NonLValue.");
1083 return St;
1084
Ted Kremenekfeb01f62008-02-06 17:32:17 +00001085
1086 case nonlval::SymbolValKind: {
Ted Kremenek230aaab2008-02-12 21:37:25 +00001087 nonlval::SymbolVal& SV = cast<nonlval::SymbolVal>(Cond);
Ted Kremenekfeb01f62008-02-06 17:32:17 +00001088 SymbolID sym = SV.getSymbol();
1089
1090 if (Assumption)
1091 return AssumeSymNE(St, sym, ValMgr.getValue(0, SymMgr.getType(sym)),
1092 isFeasible);
1093 else
1094 return AssumeSymEQ(St, sym, ValMgr.getValue(0, SymMgr.getType(sym)),
1095 isFeasible);
1096 }
1097
Ted Kremenek08b66252008-02-06 04:31:33 +00001098 case nonlval::SymIntConstraintValKind:
1099 return
1100 AssumeSymInt(St, Assumption,
1101 cast<nonlval::SymIntConstraintVal>(Cond).getConstraint(),
1102 isFeasible);
1103
Ted Kremenek329f8542008-02-05 21:52:21 +00001104 case nonlval::ConcreteIntKind: {
1105 bool b = cast<nonlval::ConcreteInt>(Cond).getValue() != 0;
Ted Kremenekb38911f2008-01-30 23:03:39 +00001106 isFeasible = b ? Assumption : !Assumption;
1107 return St;
1108 }
1109 }
1110}
1111
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001112GRExprEngine::StateTy
1113GRExprEngine::AssumeSymNE(StateTy St, SymbolID sym,
Ted Kremenek862d5bb2008-02-06 00:54:14 +00001114 const llvm::APSInt& V, bool& isFeasible) {
Ted Kremenek692416c2008-02-18 22:57:02 +00001115
Ted Kremenek862d5bb2008-02-06 00:54:14 +00001116 // First, determine if sym == X, where X != V.
1117 if (const llvm::APSInt* X = St.getSymVal(sym)) {
1118 isFeasible = *X != V;
1119 return St;
1120 }
1121
1122 // Second, determine if sym != V.
1123 if (St.isNotEqual(sym, V)) {
1124 isFeasible = true;
1125 return St;
1126 }
1127
1128 // If we reach here, sym is not a constant and we don't know if it is != V.
1129 // Make that assumption.
1130
1131 isFeasible = true;
1132 return StateMgr.AddNE(St, sym, V);
1133}
1134
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001135GRExprEngine::StateTy
1136GRExprEngine::AssumeSymEQ(StateTy St, SymbolID sym,
Ted Kremenek862d5bb2008-02-06 00:54:14 +00001137 const llvm::APSInt& V, bool& isFeasible) {
1138
1139 // First, determine if sym == X, where X != V.
1140 if (const llvm::APSInt* X = St.getSymVal(sym)) {
1141 isFeasible = *X == V;
1142 return St;
1143 }
1144
1145 // Second, determine if sym != V.
1146 if (St.isNotEqual(sym, V)) {
1147 isFeasible = false;
1148 return St;
1149 }
1150
1151 // If we reach here, sym is not a constant and we don't know if it is == V.
1152 // Make that assumption.
1153
1154 isFeasible = true;
1155 return StateMgr.AddEQ(St, sym, V);
1156}
Ted Kremenekb38911f2008-01-30 23:03:39 +00001157
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001158GRExprEngine::StateTy
1159GRExprEngine::AssumeSymInt(StateTy St, bool Assumption,
Ted Kremenek08b66252008-02-06 04:31:33 +00001160 const SymIntConstraint& C, bool& isFeasible) {
1161
1162 switch (C.getOpcode()) {
1163 default:
1164 // No logic yet for other operators.
1165 return St;
1166
1167 case BinaryOperator::EQ:
1168 if (Assumption)
1169 return AssumeSymEQ(St, C.getSymbol(), C.getInt(), isFeasible);
1170 else
1171 return AssumeSymNE(St, C.getSymbol(), C.getInt(), isFeasible);
1172
1173 case BinaryOperator::NE:
1174 if (Assumption)
1175 return AssumeSymNE(St, C.getSymbol(), C.getInt(), isFeasible);
1176 else
1177 return AssumeSymEQ(St, C.getSymbol(), C.getInt(), isFeasible);
1178 }
1179}
1180
Ted Kremenekb38911f2008-01-30 23:03:39 +00001181//===----------------------------------------------------------------------===//
Ted Kremeneke01c9872008-02-14 22:36:46 +00001182// Visualization.
Ted Kremenekee985462008-01-16 18:18:48 +00001183//===----------------------------------------------------------------------===//
1184
Ted Kremenekaa66a322008-01-16 21:46:15 +00001185#ifndef NDEBUG
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001186static GRExprEngine* GraphPrintCheckerState;
Ted Kremenek3b4f6702008-01-30 23:24:39 +00001187
Ted Kremenekaa66a322008-01-16 21:46:15 +00001188namespace llvm {
1189template<>
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001190struct VISIBILITY_HIDDEN DOTGraphTraits<GRExprEngine::NodeTy*> :
Ted Kremenekaa66a322008-01-16 21:46:15 +00001191 public DefaultDOTGraphTraits {
Ted Kremenek016f52f2008-02-08 21:10:02 +00001192
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001193 static void PrintVarBindings(std::ostream& Out, GRExprEngine::StateTy St) {
Ted Kremenek016f52f2008-02-08 21:10:02 +00001194
1195 Out << "Variables:\\l";
1196
Ted Kremenek9ff731d2008-01-24 22:27:20 +00001197 bool isFirst = true;
1198
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001199 for (GRExprEngine::StateTy::vb_iterator I=St.vb_begin(),
Ted Kremenek016f52f2008-02-08 21:10:02 +00001200 E=St.vb_end(); I!=E;++I) {
1201
1202 if (isFirst)
1203 isFirst = false;
1204 else
1205 Out << "\\l";
1206
1207 Out << ' ' << I.getKey()->getName() << " : ";
1208 I.getData().print(Out);
1209 }
1210
1211 }
1212
Ted Kremeneke7d22112008-02-11 19:21:59 +00001213
Ted Kremenek44842c22008-02-13 18:06:44 +00001214 static void PrintSubExprBindings(std::ostream& Out, GRExprEngine::StateTy St){
Ted Kremeneke7d22112008-02-11 19:21:59 +00001215
1216 bool isFirst = true;
1217
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001218 for (GRExprEngine::StateTy::seb_iterator I=St.seb_begin(), E=St.seb_end();
Ted Kremeneke7d22112008-02-11 19:21:59 +00001219 I != E;++I) {
1220
1221 if (isFirst) {
1222 Out << "\\l\\lSub-Expressions:\\l";
1223 isFirst = false;
1224 }
1225 else
1226 Out << "\\l";
1227
1228 Out << " (" << (void*) I.getKey() << ") ";
1229 I.getKey()->printPretty(Out);
1230 Out << " : ";
1231 I.getData().print(Out);
1232 }
1233 }
1234
Ted Kremenek44842c22008-02-13 18:06:44 +00001235 static void PrintBlkExprBindings(std::ostream& Out, GRExprEngine::StateTy St){
Ted Kremeneke7d22112008-02-11 19:21:59 +00001236
Ted Kremenek016f52f2008-02-08 21:10:02 +00001237 bool isFirst = true;
1238
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001239 for (GRExprEngine::StateTy::beb_iterator I=St.beb_begin(), E=St.beb_end();
Ted Kremeneke7d22112008-02-11 19:21:59 +00001240 I != E; ++I) {
Ted Kremenek9ff731d2008-01-24 22:27:20 +00001241 if (isFirst) {
Ted Kremeneke7d22112008-02-11 19:21:59 +00001242 Out << "\\l\\lBlock-level Expressions:\\l";
Ted Kremenek9ff731d2008-01-24 22:27:20 +00001243 isFirst = false;
1244 }
1245 else
1246 Out << "\\l";
Ted Kremenek016f52f2008-02-08 21:10:02 +00001247
Ted Kremeneke7d22112008-02-11 19:21:59 +00001248 Out << " (" << (void*) I.getKey() << ") ";
1249 I.getKey()->printPretty(Out);
Ted Kremenek9ff731d2008-01-24 22:27:20 +00001250 Out << " : ";
1251 I.getData().print(Out);
1252 }
1253 }
1254
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001255 static void PrintEQ(std::ostream& Out, GRExprEngine::StateTy St) {
Ted Kremeneked4de312008-02-06 03:56:15 +00001256 ValueState::ConstantEqTy CE = St.getImpl()->ConstantEq;
1257
1258 if (CE.isEmpty())
1259 return;
1260
1261 Out << "\\l\\|'==' constraints:";
1262
1263 for (ValueState::ConstantEqTy::iterator I=CE.begin(), E=CE.end(); I!=E;++I)
1264 Out << "\\l $" << I.getKey() << " : " << I.getData()->toString();
1265 }
1266
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001267 static void PrintNE(std::ostream& Out, GRExprEngine::StateTy St) {
Ted Kremeneked4de312008-02-06 03:56:15 +00001268 ValueState::ConstantNotEqTy NE = St.getImpl()->ConstantNotEq;
1269
1270 if (NE.isEmpty())
1271 return;
1272
1273 Out << "\\l\\|'!=' constraints:";
1274
1275 for (ValueState::ConstantNotEqTy::iterator I=NE.begin(), EI=NE.end();
1276 I != EI; ++I){
1277
1278 Out << "\\l $" << I.getKey() << " : ";
1279 bool isFirst = true;
1280
1281 ValueState::IntSetTy::iterator J=I.getData().begin(),
1282 EJ=I.getData().end();
1283 for ( ; J != EJ; ++J) {
1284 if (isFirst) isFirst = false;
1285 else Out << ", ";
1286
1287 Out << (*J)->toString();
1288 }
1289 }
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00001290 }
1291
1292 static std::string getNodeAttributes(const GRExprEngine::NodeTy* N, void*) {
1293
1294 if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
Ted Kremenek9dca0622008-02-19 00:22:37 +00001295 GraphPrintCheckerState->isExplicitNullDeref(N) ||
Ted Kremenekb5339122008-02-19 20:53:06 +00001296 GraphPrintCheckerState->isUninitDeref(N) ||
Ted Kremenek9dca0622008-02-19 00:22:37 +00001297 GraphPrintCheckerState->isUninitStore(N) ||
1298 GraphPrintCheckerState->isUninitControlFlow(N))
Ted Kremeneka3fadfc2008-02-14 22:54:53 +00001299 return "color=\"red\",style=\"filled\"";
1300
1301 return "";
1302 }
Ted Kremeneked4de312008-02-06 03:56:15 +00001303
Ted Kremenek4d4dd852008-02-13 17:41:41 +00001304 static std::string getNodeLabel(const GRExprEngine::NodeTy* N, void*) {
Ted Kremenekaa66a322008-01-16 21:46:15 +00001305 std::ostringstream Out;
Ted Kremenek803c9ed2008-01-23 22:30:44 +00001306
1307 // Program Location.
Ted Kremenekaa66a322008-01-16 21:46:15 +00001308 ProgramPoint Loc = N->getLocation();
1309
1310 switch (Loc.getKind()) {
1311 case ProgramPoint::BlockEntranceKind:
1312 Out << "Block Entrance: B"
1313 << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
1314 break;
1315
1316 case ProgramPoint::BlockExitKind:
1317 assert (false);
1318 break;
1319
1320 case ProgramPoint::PostStmtKind: {
1321 const PostStmt& L = cast<PostStmt>(Loc);
Ted Kremenek9ff731d2008-01-24 22:27:20 +00001322 Out << L.getStmt()->getStmtClassName() << ':'
1323 << (void*) L.getStmt() << ' ';
1324
Ted Kremenekaa66a322008-01-16 21:46:15 +00001325 L.getStmt()->printPretty(Out);
Ted Kremenekd131c4f2008-02-07 05:48:01 +00001326
1327 if (GraphPrintCheckerState->isImplicitNullDeref(N)) {
1328 Out << "\\|Implicit-Null Dereference.\\l";
1329 }
Ted Kremenek63a4f692008-02-07 06:04:18 +00001330 else if (GraphPrintCheckerState->isExplicitNullDeref(N)) {
1331 Out << "\\|Explicit-Null Dereference.\\l";
1332 }
Ted Kremenekb5339122008-02-19 20:53:06 +00001333 else if (GraphPrintCheckerState->isUninitDeref(N)) {
1334 Out << "\\|Dereference of uninitialied value.\\l";
1335 }
Ted Kremenek9dca0622008-02-19 00:22:37 +00001336 else if (GraphPrintCheckerState->isUninitStore(N)) {
1337 Out << "\\|Store to Uninitialized LValue.";
1338 }
Ted Kremenekd131c4f2008-02-07 05:48:01 +00001339
Ted Kremenekaa66a322008-01-16 21:46:15 +00001340 break;
1341 }
1342
1343 default: {
1344 const BlockEdge& E = cast<BlockEdge>(Loc);
1345 Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
1346 << E.getDst()->getBlockID() << ')';
Ted Kremenekb38911f2008-01-30 23:03:39 +00001347
1348 if (Stmt* T = E.getSrc()->getTerminator()) {
1349 Out << "\\|Terminator: ";
1350 E.getSrc()->printTerminator(Out);
1351
Ted Kremenekdaeb9a72008-02-13 23:08:21 +00001352 if (isa<SwitchStmt>(T)) {
1353 Stmt* Label = E.getDst()->getLabel();
1354
1355 if (Label) {
1356 if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
1357 Out << "\\lcase ";
1358 C->getLHS()->printPretty(Out);
1359
1360 if (Stmt* RHS = C->getRHS()) {
1361 Out << " .. ";
1362 RHS->printPretty(Out);
1363 }
1364
1365 Out << ":";
1366 }
1367 else {
1368 assert (isa<DefaultStmt>(Label));
1369 Out << "\\ldefault:";
1370 }
1371 }
1372 else
1373 Out << "\\l(implicit) default:";
1374 }
1375 else if (isa<IndirectGotoStmt>(T)) {
Ted Kremenekb38911f2008-01-30 23:03:39 +00001376 // FIXME
1377 }
1378 else {
1379 Out << "\\lCondition: ";
1380 if (*E.getSrc()->succ_begin() == E.getDst())
1381 Out << "true";
1382 else
1383 Out << "false";
1384 }
1385
1386 Out << "\\l";
1387 }
Ted Kremenek3b4f6702008-01-30 23:24:39 +00001388
1389 if (GraphPrintCheckerState->isUninitControlFlow(N)) {
1390 Out << "\\|Control-flow based on\\lUninitialized value.\\l";
1391 }
Ted Kremenekaa66a322008-01-16 21:46:15 +00001392 }
1393 }
1394
Ted Kremenek9153f732008-02-05 07:17:49 +00001395 Out << "\\|StateID: " << (void*) N->getState().getImpl() << "\\|";
Ted Kremenek016f52f2008-02-08 21:10:02 +00001396
Ted Kremeneke7d22112008-02-11 19:21:59 +00001397 N->getState().printDOT(Out);
Ted Kremenek803c9ed2008-01-23 22:30:44 +00001398
Ted Kremenek803c9ed2008-01-23 22:30:44 +00001399 Out << "\\l";
Ted Kremenekaa66a322008-01-16 21:46:15 +00001400 return Out.str();
1401 }
1402};
1403} // end llvm namespace
1404#endif
1405
Ted Kremeneke01c9872008-02-14 22:36:46 +00001406void GRExprEngine::ViewGraph() {
Ted Kremenekaa66a322008-01-16 21:46:15 +00001407#ifndef NDEBUG
Ted Kremeneke01c9872008-02-14 22:36:46 +00001408 GraphPrintCheckerState = this;
1409 llvm::ViewGraph(*G.roots_begin(), "GRExprEngine");
Ted Kremenek3b4f6702008-01-30 23:24:39 +00001410 GraphPrintCheckerState = NULL;
Ted Kremeneke01c9872008-02-14 22:36:46 +00001411#endif
Ted Kremenekee985462008-01-16 18:18:48 +00001412}