blob: 366ffb70c6636faa5f28d8bc49ffa3448b41fcfc [file] [log] [blame]
Ted Kremenek25a484d2008-02-14 18:28:23 +00001// GRSimpleVals.cpp - Transfer functions for tracking simple values -*- C++ -*--
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This files defines GRSimpleVals, a sub-class of GRTransferFuncs that
11// provides transfer functions for performing simple value tracking with
12// limited support for symbolics.
13//
14//===----------------------------------------------------------------------===//
15
16#include "GRSimpleVals.h"
Ted Kremenek9f6b1612008-02-27 06:07:00 +000017#include "clang/Analysis/PathSensitive/ValueState.h"
Ted Kremenek3862eb12008-02-14 22:36:46 +000018#include "clang/Basic/Diagnostic.h"
Ted Kremenek9cac66e2008-02-27 17:56:16 +000019#include <sstream>
Ted Kremenek25a484d2008-02-14 18:28:23 +000020
21using namespace clang;
22
Ted Kremenek3862eb12008-02-14 22:36:46 +000023namespace clang {
Ted Kremenekf567a822008-02-26 21:31:18 +000024
25template <typename ITERATOR>
26static void EmitWarning(Diagnostic& Diag, SourceManager& SrcMgr,
27 ITERATOR I, ITERATOR E, const char* msg) {
28
Ted Kremenek9cac66e2008-02-27 17:56:16 +000029 std::ostringstream Out;
30 Out << "[CHECKER] " << msg;
31 msg = Out.str().c_str();
32
Ted Kremenek717bd7d2008-02-27 20:47:56 +000033 bool isFirst = true;
Ted Kremenekf567a822008-02-26 21:31:18 +000034 unsigned ErrorDiag;
Ted Kremenek3f3a30b2008-02-28 20:38:16 +000035 llvm::SmallPtrSet<void*,10> CachedErrors;
36
Ted Kremenekf567a822008-02-26 21:31:18 +000037
38 for (; I != E; ++I) {
39
40 if (isFirst) {
41 isFirst = false;
42 ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, msg);
43 }
Ted Kremenek3f3a30b2008-02-28 20:38:16 +000044 else {
45
46 // HACK: Cache the location of the error. Don't emit the same
47 // warning for the same error type that occurs at the same program
48 // location but along a different path.
49 void* p = (*I)->getLocation().getRawData();
50
51 if (CachedErrors.count(p))
52 continue;
53
54 CachedErrors.insert(p);
55 }
Ted Kremenekf567a822008-02-26 21:31:18 +000056
57 const PostStmt& L = cast<PostStmt>((*I)->getLocation());
58 Expr* Exp = cast<Expr>(L.getStmt());
59
60 Diag.Report(FullSourceLoc(Exp->getExprLoc(), SrcMgr), ErrorDiag);
61 }
62}
Ted Kremenek07baa252008-02-21 18:02:17 +000063
64unsigned RunGRSimpleVals(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx,
65 Diagnostic& Diag, bool Visualize) {
66
67 if (Diag.hasErrorOccurred())
68 return 0;
69
70 GRCoreEngine<GRExprEngine> Engine(cfg, FD, Ctx);
71 GRExprEngine* CheckerState = &Engine.getCheckerState();
72 GRSimpleVals GRSV;
73 CheckerState->setTransferFunctions(GRSV);
74
75 // Execute the worklist algorithm.
Ted Kremenekf567a822008-02-26 21:31:18 +000076 Engine.ExecuteWorkList(20000);
Ted Kremenek07baa252008-02-21 18:02:17 +000077
Ted Kremenekf567a822008-02-26 21:31:18 +000078 SourceManager& SrcMgr = Ctx.getSourceManager();
79
80 EmitWarning(Diag, SrcMgr,
81 CheckerState->null_derefs_begin(),
82 CheckerState->null_derefs_end(),
83 "NULL pointer is dereferenced after it is checked for NULL.");
84
85 EmitWarning(Diag, SrcMgr,
Ted Kremenekb31af242008-02-28 09:25:22 +000086 CheckerState->undef_derefs_begin(),
87 CheckerState->undef_derefs_end(),
88 "Dereference of undefined value.");
Ted Kremenekf567a822008-02-26 21:31:18 +000089
90 EmitWarning(Diag, SrcMgr,
Ted Kremenekb31af242008-02-28 09:25:22 +000091 CheckerState->undef_derefs_begin(),
92 CheckerState->undef_derefs_end(),
93 "Dereference of undefined value.");
Ted Kremenekf567a822008-02-26 21:31:18 +000094
95 EmitWarning(Diag, SrcMgr,
96 CheckerState->bad_divides_begin(),
97 CheckerState->bad_divides_end(),
Ted Kremenekb31af242008-02-28 09:25:22 +000098 "Division by zero/undefined value.");
Ted Kremenekc2d07202008-02-28 20:32:03 +000099
100 EmitWarning(Diag, SrcMgr,
101 CheckerState->undef_results_begin(),
102 CheckerState->undef_results_end(),
103 "Result of operation is undefined.");
Ted Kremenek07baa252008-02-21 18:02:17 +0000104
105#ifndef NDEBUG
106 if (Visualize) CheckerState->ViewGraph();
107#endif
108
109 return Engine.getGraph().size();
110}
111
Ted Kremenek3862eb12008-02-14 22:36:46 +0000112} // end clang namespace
113
Ted Kremenek25a484d2008-02-14 18:28:23 +0000114//===----------------------------------------------------------------------===//
115// Transfer function for Casts.
116//===----------------------------------------------------------------------===//
117
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000118RVal GRSimpleVals::EvalCast(ValueManager& ValMgr, NonLVal X, QualType T) {
Ted Kremenekbc965a62008-02-18 22:57:02 +0000119
Ted Kremenek25a484d2008-02-14 18:28:23 +0000120 if (!isa<nonlval::ConcreteInt>(X))
121 return UnknownVal();
122
123 llvm::APSInt V = cast<nonlval::ConcreteInt>(X).getValue();
Ted Kremenek25a484d2008-02-14 18:28:23 +0000124 V.setIsUnsigned(T->isUnsignedIntegerType() || T->isPointerType());
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000125 V.extOrTrunc(ValMgr.getContext().getTypeSize(T, SourceLocation()));
Ted Kremenek25a484d2008-02-14 18:28:23 +0000126
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000127 if (T->isPointerType())
Ted Kremenek25a484d2008-02-14 18:28:23 +0000128 return lval::ConcreteInt(ValMgr.getValue(V));
129 else
130 return nonlval::ConcreteInt(ValMgr.getValue(V));
131}
132
133// Casts.
134
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000135RVal GRSimpleVals::EvalCast(ValueManager& ValMgr, LVal X, QualType T) {
Ted Kremenekbc965a62008-02-18 22:57:02 +0000136
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000137 if (T->isPointerType())
Ted Kremenek25a484d2008-02-14 18:28:23 +0000138 return X;
139
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000140 assert (T->isIntegerType());
Ted Kremenek25a484d2008-02-14 18:28:23 +0000141
142 if (!isa<lval::ConcreteInt>(X))
143 return UnknownVal();
144
145 llvm::APSInt V = cast<lval::ConcreteInt>(X).getValue();
Ted Kremenek25a484d2008-02-14 18:28:23 +0000146 V.setIsUnsigned(T->isUnsignedIntegerType() || T->isPointerType());
Ted Kremenek9cfda3f2008-02-21 18:43:30 +0000147 V.extOrTrunc(ValMgr.getContext().getTypeSize(T, SourceLocation()));
Ted Kremenek25a484d2008-02-14 18:28:23 +0000148
149 return nonlval::ConcreteInt(ValMgr.getValue(V));
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000150}
151
152// Unary operators.
153
Ted Kremenek07baa252008-02-21 18:02:17 +0000154RVal GRSimpleVals::EvalMinus(ValueManager& ValMgr, UnaryOperator* U, NonLVal X){
Ted Kremenekbc965a62008-02-18 22:57:02 +0000155
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000156 switch (X.getSubKind()) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000157
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000158 case nonlval::ConcreteIntKind:
159 return cast<nonlval::ConcreteInt>(X).EvalMinus(ValMgr, U);
Ted Kremenek07baa252008-02-21 18:02:17 +0000160
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000161 default:
Ted Kremenek07baa252008-02-21 18:02:17 +0000162 return UnknownVal();
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000163 }
164}
165
Ted Kremenek07baa252008-02-21 18:02:17 +0000166RVal GRSimpleVals::EvalComplement(ValueManager& ValMgr, NonLVal X) {
167
Ted Kremenek0cd96352008-02-20 04:12:31 +0000168 switch (X.getSubKind()) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000169
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000170 case nonlval::ConcreteIntKind:
171 return cast<nonlval::ConcreteInt>(X).EvalComplement(ValMgr);
Ted Kremenek07baa252008-02-21 18:02:17 +0000172
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000173 default:
Ted Kremenek07baa252008-02-21 18:02:17 +0000174 return UnknownVal();
Ted Kremenekc9922fd2008-02-14 18:40:24 +0000175 }
176}
Ted Kremenekb1934132008-02-14 19:37:24 +0000177
178// Binary operators.
179
Ted Kremenek07baa252008-02-21 18:02:17 +0000180RVal GRSimpleVals::EvalBinOp(ValueManager& ValMgr, BinaryOperator::Opcode Op,
181 NonLVal L, NonLVal R) {
182 while (1) {
Ted Kremenekb1934132008-02-14 19:37:24 +0000183
Ted Kremenek07baa252008-02-21 18:02:17 +0000184 switch (L.getSubKind()) {
Ted Kremenekb1934132008-02-14 19:37:24 +0000185 default:
Ted Kremenekde89ec02008-02-21 19:10:12 +0000186 return UnknownVal();
Ted Kremenekb1934132008-02-14 19:37:24 +0000187
188 case nonlval::ConcreteIntKind:
189
Ted Kremenek07baa252008-02-21 18:02:17 +0000190 if (isa<nonlval::ConcreteInt>(R)) {
191 const nonlval::ConcreteInt& L_CI = cast<nonlval::ConcreteInt>(L);
192 const nonlval::ConcreteInt& R_CI = cast<nonlval::ConcreteInt>(R);
193 return L_CI.EvalBinOp(ValMgr, Op, R_CI);
Ted Kremenekb1934132008-02-14 19:37:24 +0000194 }
Ted Kremenekb1934132008-02-14 19:37:24 +0000195 else {
Ted Kremenek07baa252008-02-21 18:02:17 +0000196 NonLVal tmp = R;
197 R = L;
198 L = tmp;
Ted Kremenekb1934132008-02-14 19:37:24 +0000199 continue;
200 }
201
202 case nonlval::SymbolValKind: {
Ted Kremenek07baa252008-02-21 18:02:17 +0000203
204 if (isa<nonlval::ConcreteInt>(R)) {
Ted Kremenekb1934132008-02-14 19:37:24 +0000205 const SymIntConstraint& C =
Ted Kremenek07baa252008-02-21 18:02:17 +0000206 ValMgr.getConstraint(cast<nonlval::SymbolVal>(L).getSymbol(), Op,
207 cast<nonlval::ConcreteInt>(R).getValue());
Ted Kremenekb1934132008-02-14 19:37:24 +0000208
209 return nonlval::SymIntConstraintVal(C);
210 }
211 else
Ted Kremenek07baa252008-02-21 18:02:17 +0000212 return UnknownVal();
Ted Kremenekb1934132008-02-14 19:37:24 +0000213 }
214 }
215 }
216}
217
Ted Kremenek775e0d82008-02-15 00:52:26 +0000218
Ted Kremenek521d9722008-02-15 23:15:23 +0000219// Binary Operators (except assignments and comma).
220
Ted Kremenek07baa252008-02-21 18:02:17 +0000221RVal GRSimpleVals::EvalBinOp(ValueManager& ValMgr, BinaryOperator::Opcode Op,
222 LVal L, LVal R) {
Ted Kremenekbc965a62008-02-18 22:57:02 +0000223
Ted Kremenek521d9722008-02-15 23:15:23 +0000224 switch (Op) {
Ted Kremenek07baa252008-02-21 18:02:17 +0000225
Ted Kremenek521d9722008-02-15 23:15:23 +0000226 default:
227 return UnknownVal();
228
229 case BinaryOperator::EQ:
Ted Kremenek07baa252008-02-21 18:02:17 +0000230 return EvalEQ(ValMgr, L, R);
Ted Kremenek521d9722008-02-15 23:15:23 +0000231
232 case BinaryOperator::NE:
Ted Kremenek07baa252008-02-21 18:02:17 +0000233 return EvalNE(ValMgr, L, R);
Ted Kremenek521d9722008-02-15 23:15:23 +0000234 }
235}
236
Ted Kremenek775e0d82008-02-15 00:52:26 +0000237// Pointer arithmetic.
238
Ted Kremenek07baa252008-02-21 18:02:17 +0000239RVal GRSimpleVals::EvalBinOp(ValueManager& ValMgr, BinaryOperator::Opcode Op,
240 LVal L, NonLVal R) {
241 return UnknownVal();
Ted Kremenek775e0d82008-02-15 00:52:26 +0000242}
243
Ted Kremenek07baa252008-02-21 18:02:17 +0000244// Equality operators for LVals.
Ted Kremenekb1934132008-02-14 19:37:24 +0000245
Ted Kremenek07baa252008-02-21 18:02:17 +0000246RVal GRSimpleVals::EvalEQ(ValueManager& ValMgr, LVal L, LVal R) {
247
248 switch (L.getSubKind()) {
Ted Kremenekb1934132008-02-14 19:37:24 +0000249
Ted Kremenekb1934132008-02-14 19:37:24 +0000250 default:
Ted Kremenek07baa252008-02-21 18:02:17 +0000251 assert(false && "EQ not implemented for this LVal.");
252 return UnknownVal();
Ted Kremenekb1934132008-02-14 19:37:24 +0000253
254 case lval::ConcreteIntKind:
Ted Kremenek07baa252008-02-21 18:02:17 +0000255
256 if (isa<lval::ConcreteInt>(R)) {
257 bool b = cast<lval::ConcreteInt>(L).getValue() ==
258 cast<lval::ConcreteInt>(R).getValue();
Ted Kremenekb1934132008-02-14 19:37:24 +0000259
Ted Kremenek07baa252008-02-21 18:02:17 +0000260 return NonLVal::MakeIntTruthVal(ValMgr, b);
Ted Kremenekb1934132008-02-14 19:37:24 +0000261 }
Ted Kremenek07baa252008-02-21 18:02:17 +0000262 else if (isa<lval::SymbolVal>(R)) {
Ted Kremenekb1934132008-02-14 19:37:24 +0000263
264 const SymIntConstraint& C =
Ted Kremenek07baa252008-02-21 18:02:17 +0000265 ValMgr.getConstraint(cast<lval::SymbolVal>(R).getSymbol(),
Ted Kremenekb1934132008-02-14 19:37:24 +0000266 BinaryOperator::EQ,
Ted Kremenek07baa252008-02-21 18:02:17 +0000267 cast<lval::ConcreteInt>(L).getValue());
Ted Kremenekb1934132008-02-14 19:37:24 +0000268
269 return nonlval::SymIntConstraintVal(C);
270 }
271
272 break;
273
Ted Kremenek07baa252008-02-21 18:02:17 +0000274 case lval::SymbolValKind: {
275
276 if (isa<lval::ConcreteInt>(R)) {
277 const SymIntConstraint& C =
278 ValMgr.getConstraint(cast<lval::SymbolVal>(L).getSymbol(),
279 BinaryOperator::EQ,
280 cast<lval::ConcreteInt>(R).getValue());
Ted Kremenekb1934132008-02-14 19:37:24 +0000281
Ted Kremenek07baa252008-02-21 18:02:17 +0000282 return nonlval::SymIntConstraintVal(C);
Ted Kremenekb1934132008-02-14 19:37:24 +0000283 }
284
Ted Kremenekfe944c42008-02-22 18:41:59 +0000285 // FIXME: Implement == for lval Symbols. This is mainly useful
286 // in iterator loops when traversing a buffer, e.g. while(z != zTerm).
287 // Since this is not useful for many checkers we'll punt on this for
288 // now.
289
290 return UnknownVal();
Ted Kremenek07baa252008-02-21 18:02:17 +0000291 }
Ted Kremenekb1934132008-02-14 19:37:24 +0000292
Ted Kremenek07baa252008-02-21 18:02:17 +0000293 case lval::DeclValKind:
Ted Kremenek38706192008-02-22 00:54:56 +0000294 case lval::FuncValKind:
295 case lval::GotoLabelKind:
296 return NonLVal::MakeIntTruthVal(ValMgr, L == R);
Ted Kremenekb1934132008-02-14 19:37:24 +0000297 }
298
Ted Kremenek07baa252008-02-21 18:02:17 +0000299 return NonLVal::MakeIntTruthVal(ValMgr, false);
Ted Kremenekb1934132008-02-14 19:37:24 +0000300}
301
Ted Kremenek07baa252008-02-21 18:02:17 +0000302RVal GRSimpleVals::EvalNE(ValueManager& ValMgr, LVal L, LVal R) {
Ted Kremenekbc965a62008-02-18 22:57:02 +0000303
Ted Kremenek07baa252008-02-21 18:02:17 +0000304 switch (L.getSubKind()) {
Ted Kremenekb1934132008-02-14 19:37:24 +0000305
Ted Kremenekb1934132008-02-14 19:37:24 +0000306 default:
Ted Kremenek07baa252008-02-21 18:02:17 +0000307 assert(false && "NE not implemented for this LVal.");
308 return UnknownVal();
Ted Kremenekb1934132008-02-14 19:37:24 +0000309
310 case lval::ConcreteIntKind:
Ted Kremenek07baa252008-02-21 18:02:17 +0000311
312 if (isa<lval::ConcreteInt>(R)) {
313 bool b = cast<lval::ConcreteInt>(L).getValue() !=
314 cast<lval::ConcreteInt>(R).getValue();
Ted Kremenekb1934132008-02-14 19:37:24 +0000315
Ted Kremenek07baa252008-02-21 18:02:17 +0000316 return NonLVal::MakeIntTruthVal(ValMgr, b);
Ted Kremenekb1934132008-02-14 19:37:24 +0000317 }
Ted Kremenek07baa252008-02-21 18:02:17 +0000318 else if (isa<lval::SymbolVal>(R)) {
Ted Kremenekb1934132008-02-14 19:37:24 +0000319 const SymIntConstraint& C =
Ted Kremenek07baa252008-02-21 18:02:17 +0000320 ValMgr.getConstraint(cast<lval::SymbolVal>(R).getSymbol(),
Ted Kremenekb1934132008-02-14 19:37:24 +0000321 BinaryOperator::NE,
Ted Kremenek07baa252008-02-21 18:02:17 +0000322 cast<lval::ConcreteInt>(L).getValue());
Ted Kremenekb1934132008-02-14 19:37:24 +0000323
324 return nonlval::SymIntConstraintVal(C);
325 }
326
327 break;
328
Ted Kremenek07baa252008-02-21 18:02:17 +0000329 case lval::SymbolValKind: {
330 if (isa<lval::ConcreteInt>(R)) {
331 const SymIntConstraint& C =
332 ValMgr.getConstraint(cast<lval::SymbolVal>(L).getSymbol(),
333 BinaryOperator::NE,
334 cast<lval::ConcreteInt>(R).getValue());
Ted Kremenekb1934132008-02-14 19:37:24 +0000335
Ted Kremenek07baa252008-02-21 18:02:17 +0000336 return nonlval::SymIntConstraintVal(C);
Ted Kremenekb1934132008-02-14 19:37:24 +0000337 }
338
Ted Kremenekfe944c42008-02-22 18:41:59 +0000339 // FIXME: Implement != for lval Symbols. This is mainly useful
340 // in iterator loops when traversing a buffer, e.g. while(z != zTerm).
341 // Since this is not useful for many checkers we'll punt on this for
342 // now.
343
344 return UnknownVal();
Ted Kremenekb1934132008-02-14 19:37:24 +0000345
346 break;
Ted Kremenek07baa252008-02-21 18:02:17 +0000347 }
348
349 case lval::DeclValKind:
Ted Kremenek38706192008-02-22 00:54:56 +0000350 case lval::FuncValKind:
351 case lval::GotoLabelKind:
352 return NonLVal::MakeIntTruthVal(ValMgr, L != R);
Ted Kremenekb1934132008-02-14 19:37:24 +0000353 }
354
Ted Kremenek07baa252008-02-21 18:02:17 +0000355 return NonLVal::MakeIntTruthVal(ValMgr, true);
Ted Kremenekb1934132008-02-14 19:37:24 +0000356}
Ted Kremenek348d7852008-02-26 23:04:29 +0000357
358//===----------------------------------------------------------------------===//
359// Transfer function for Function Calls.
360//===----------------------------------------------------------------------===//
361
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000362ValueState*
Ted Kremenek348d7852008-02-26 23:04:29 +0000363GRSimpleVals::EvalCall(ValueStateManager& StateMgr, ValueManager& ValMgr,
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000364 CallExpr* CE, LVal L, ValueState* St) {
Ted Kremenek348d7852008-02-26 23:04:29 +0000365
366 // Invalidate all arguments passed in by reference (LVals).
367
368 for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
369 I != E; ++I) {
370
371 RVal V = StateMgr.GetRVal(St, *I);
372
373 if (isa<LVal>(V))
374 St = StateMgr.SetRVal(St, cast<LVal>(V), UnknownVal());
375 }
376
Ted Kremenekf4b49df2008-02-28 10:21:43 +0000377 return St;
Ted Kremenek348d7852008-02-26 23:04:29 +0000378}