blob: d5c697aa1c8d4849e75ef04ee30c73cba7952138 [file] [log] [blame]
Ted Kremenek13ed7fe2007-09-14 22:49:21 +00001//==- UninitializedValues.cpp - Find Unintialized Values --------*- C++ --*-==//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner0bc735f2007-12-29 19:59:25 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Ted Kremenek13ed7fe2007-09-14 22:49:21 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file implements Uninitialized Values analysis for source-level CFGs.
11//
12//===----------------------------------------------------------------------===//
13
Ted Kremenekcf6e41b2007-12-21 21:42:19 +000014#include "clang/Analysis/Analyses/UninitializedValues.h"
Ted Kremenek11de5cb2007-09-20 21:42:55 +000015#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
Ted Kremenekcd5860c2007-09-17 19:59:27 +000016#include "clang/Analysis/LocalCheckers.h"
17#include "clang/Basic/Diagnostic.h"
18#include "clang/AST/ASTContext.h"
Ted Kremenek1de632b2007-09-25 21:00:24 +000019#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
Ted Kremenekc2b51d82008-01-08 18:19:08 +000020#include "llvm/Support/Compiler.h"
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000021
Ted Kremenekcd5860c2007-09-17 19:59:27 +000022#include "llvm/ADT/SmallPtrSet.h"
23
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000024using namespace clang;
25
Ted Kremenekcd5860c2007-09-17 19:59:27 +000026//===----------------------------------------------------------------------===//
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000027// Dataflow initialization logic.
Ted Kremenekcd5860c2007-09-17 19:59:27 +000028//===----------------------------------------------------------------------===//
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000029
30namespace {
31
Ted Kremenekc2b51d82008-01-08 18:19:08 +000032class VISIBILITY_HIDDEN RegisterDecls
33 : public CFGRecStmtDeclVisitor<RegisterDecls> {
34
Ted Kremenek56d516d2007-09-17 17:14:52 +000035 UninitializedValues::AnalysisDataTy& AD;
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000036public:
Ted Kremenek11e72182007-10-01 20:33:52 +000037 RegisterDecls(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {}
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000038
Ted Kremenekaead1532007-09-27 18:20:22 +000039 void VisitBlockVarDecl(BlockVarDecl* VD) { AD.Register(VD); }
Ted Kremenek9f9141c2007-11-20 03:01:58 +000040 CFG& getCFG() { return AD.getCFG(); }
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000041};
42
43} // end anonymous namespace
44
45void UninitializedValues::InitializeValues(const CFG& cfg) {
Ted Kremenek11e72182007-10-01 20:33:52 +000046 RegisterDecls R(getAnalysisData());
Ted Kremeneka90b0d12007-09-18 20:59:00 +000047 cfg.VisitBlockStmts(R);
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000048}
49
Ted Kremenekcd5860c2007-09-17 19:59:27 +000050//===----------------------------------------------------------------------===//
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000051// Transfer functions.
Ted Kremenekcd5860c2007-09-17 19:59:27 +000052//===----------------------------------------------------------------------===//
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000053
54namespace {
Ted Kremenekc2b51d82008-01-08 18:19:08 +000055class VISIBILITY_HIDDEN TransferFuncs
56 : public CFGStmtVisitor<TransferFuncs,bool> {
57
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000058 UninitializedValues::ValTy V;
Ted Kremenek56d516d2007-09-17 17:14:52 +000059 UninitializedValues::AnalysisDataTy& AD;
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000060public:
Ted Kremeneka1de8c72007-09-28 00:09:38 +000061 TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {
Ted Kremenek2bf55142007-09-17 20:49:30 +000062 V.resetValues(AD);
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000063 }
64
65 UninitializedValues::ValTy& getVal() { return V; }
Ted Kremenek9f9141c2007-11-20 03:01:58 +000066 CFG& getCFG() { return AD.getCFG(); }
Ted Kremenek56d516d2007-09-17 17:14:52 +000067
Ted Kremenek20ee4fb2007-09-17 18:31:23 +000068 bool VisitDeclRefExpr(DeclRefExpr* DR);
69 bool VisitBinaryOperator(BinaryOperator* B);
70 bool VisitUnaryOperator(UnaryOperator* U);
71 bool VisitStmt(Stmt* S);
72 bool VisitCallExpr(CallExpr* C);
Ted Kremenekcd5860c2007-09-17 19:59:27 +000073 bool VisitDeclStmt(DeclStmt* D);
Ted Kremeneka1de8c72007-09-28 00:09:38 +000074 bool VisitConditionalOperator(ConditionalOperator* C);
75
76 bool Visit(Stmt *S);
77 bool BlockStmt_VisitExpr(Expr* E);
Ted Kremenek37622082008-04-15 04:39:08 +000078
79 void VisitTerminator(Stmt* T) { Visit(T); }
Ted Kremenek20ee4fb2007-09-17 18:31:23 +000080
Ted Kremenek43a16982007-09-18 21:43:18 +000081 BlockVarDecl* FindBlockVarDecl(Stmt* S);
Ted Kremenek13ed7fe2007-09-14 22:49:21 +000082};
Ted Kremenekaead1532007-09-27 18:20:22 +000083
84static const bool Initialized = true;
85static const bool Uninitialized = false;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +000086
Ted Kremenek20ee4fb2007-09-17 18:31:23 +000087bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
Ted Kremenek2bf55142007-09-17 20:49:30 +000088 if (BlockVarDecl* VD = dyn_cast<BlockVarDecl>(DR->getDecl())) {
Ted Kremenek43a16982007-09-18 21:43:18 +000089 if (AD.Observer) AD.Observer->ObserveDeclRefExpr(V,AD,DR,VD);
Ted Kremeneka1de8c72007-09-28 00:09:38 +000090
91 // Pseudo-hack to prevent cascade of warnings. If an accessed variable
92 // is uninitialized, then we are already going to flag a warning for
93 // this variable, which a "source" of uninitialized values.
94 // We can otherwise do a full "taint" of uninitialized values. The
95 // client has both options by toggling AD.FullUninitTaint.
96
97 return AD.FullUninitTaint ? V(VD,AD) : Initialized;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +000098 }
Ted Kremenekaead1532007-09-27 18:20:22 +000099 else return Initialized;
Ted Kremenek43a16982007-09-18 21:43:18 +0000100}
101
102BlockVarDecl* TransferFuncs::FindBlockVarDecl(Stmt *S) {
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000103 for (;;)
Ted Kremenek43a16982007-09-18 21:43:18 +0000104 if (ParenExpr* P = dyn_cast<ParenExpr>(S)) {
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000105 S = P->getSubExpr(); continue;
Ted Kremenek43a16982007-09-18 21:43:18 +0000106 }
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000107 else if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(S)) {
Ted Kremenek43a16982007-09-18 21:43:18 +0000108 if (BlockVarDecl* VD = dyn_cast<BlockVarDecl>(DR->getDecl()))
109 return VD;
Ted Kremenekff7c5382007-11-24 20:07:36 +0000110 else
111 return NULL;
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000112 }
113 else return NULL;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000114}
115
116bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
Ted Kremenek6ce2b632007-09-28 21:08:51 +0000117 if (BlockVarDecl* VD = FindBlockVarDecl(B->getLHS()))
118 if (B->isAssignmentOp()) {
Ted Kremenekff7c5382007-11-24 20:07:36 +0000119 if (B->getOpcode() == BinaryOperator::Assign)
120 return V(VD,AD) = Visit(B->getRHS());
121 else // Handle +=, -=, *=, etc. We do want '&', not '&&'.
122 return V(VD,AD) = Visit(B->getLHS()) & Visit(B->getRHS());
Ted Kremenek6ce2b632007-09-28 21:08:51 +0000123 }
124
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000125 return VisitStmt(B);
126}
127
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000128bool TransferFuncs::VisitDeclStmt(DeclStmt* S) {
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000129 for (ScopedDecl* D = S->getDecl(); D != NULL; D = D->getNextDeclarator())
Ted Kremenekaead1532007-09-27 18:20:22 +0000130 if (BlockVarDecl* VD = dyn_cast<BlockVarDecl>(D)) {
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000131 if (Stmt* I = VD->getInit())
132 V(VD,AD) = AD.FullUninitTaint ? V(cast<Expr>(I),AD) : Initialized;
Ted Kremenek81a56ec2007-12-13 05:14:22 +0000133 else {
134 // Special case for declarations of array types. For things like:
135 //
136 // char x[10];
137 //
138 // we should treat "x" as being initialized, because the variable
139 // "x" really refers to the memory block. Clearly x[1] is
140 // uninitialized, but expressions like "(char *) x" really do refer to
141 // an initialized value. This simple dataflow analysis does not reason
142 // about the contents of arrays, although it could be potentially
143 // extended to do so if the array were of constant size.
144 if (VD->getType()->isArrayType())
145 V(VD,AD) = Initialized;
146 else
147 V(VD,AD) = Uninitialized;
148 }
Ted Kremenekaead1532007-09-27 18:20:22 +0000149 }
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000150
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000151 return Uninitialized; // Value is never consumed.
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000152}
153
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000154bool TransferFuncs::VisitCallExpr(CallExpr* C) {
Ted Kremenek59d18272007-09-18 21:47:41 +0000155 VisitChildren(C);
Ted Kremenekaead1532007-09-27 18:20:22 +0000156 return Initialized;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000157}
158
159bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
Ted Kremenek8d9ebae2007-12-13 04:47:15 +0000160 switch (U->getOpcode()) {
161 case UnaryOperator::AddrOf:
162 if (BlockVarDecl* VD = FindBlockVarDecl(U->getSubExpr()))
163 return V(VD,AD) = Initialized;
164
165 break;
166
167 case UnaryOperator::SizeOf:
168 return Initialized;
169
170 default:
171 break;
172 }
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000173
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000174 return Visit(U->getSubExpr());
175}
176
177bool TransferFuncs::VisitConditionalOperator(ConditionalOperator* C) {
178 Visit(C->getCond());
Anders Carlsson39073232007-11-30 19:04:31 +0000179
180 bool rhsResult = Visit(C->getRHS());
181 // Handle the GNU extension for missing LHS.
182 if (Expr *lhs = C->getLHS())
183 return Visit(lhs) & rhsResult; // Yes: we want &, not &&.
184 else
185 return rhsResult;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000186}
187
188bool TransferFuncs::VisitStmt(Stmt* S) {
Ted Kremenekaead1532007-09-27 18:20:22 +0000189 bool x = Initialized;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000190
191 // We don't stop at the first subexpression that is Uninitialized because
192 // evaluating some subexpressions may result in propogating "Uninitialized"
193 // or "Initialized" to variables referenced in the other subexpressions.
194 for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I)
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000195 if (*I && Visit(*I) == Uninitialized) x = Uninitialized;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000196
197 return x;
198}
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000199
200bool TransferFuncs::Visit(Stmt *S) {
201 if (AD.isTracked(static_cast<Expr*>(S))) return V(static_cast<Expr*>(S),AD);
202 else return static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(S);
203}
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000204
205bool TransferFuncs::BlockStmt_VisitExpr(Expr* E) {
Ted Kremenek33d4aab2008-01-26 00:03:27 +0000206 bool x = static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(E);
207 if (AD.isTracked(E)) V(E,AD) = x;
208 return x;
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000209}
210
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000211} // end anonymous namespace
212
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000213//===----------------------------------------------------------------------===//
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000214// Merge operator.
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000215//
216// In our transfer functions we take the approach that any
217// combination of unintialized values, e.g. Unitialized + ___ = Unitialized.
218//
219// Merges take the opposite approach.
220//
Ted Kremeneka90b0d12007-09-18 20:59:00 +0000221// In the merge of dataflow values we prefer unsoundness, and
Ted Kremenek20ee4fb2007-09-17 18:31:23 +0000222// prefer false negatives to false positives. At merges, if a value for a
223// tracked Decl is EVER initialized in any of the predecessors we treat it as
224// initialized at the confluence point.
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000225//===----------------------------------------------------------------------===//
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000226
227namespace {
Ted Kremenek5fb5c6a2008-03-22 20:11:00 +0000228 typedef ExprDeclBitVector_Types::Intersect Merge;
Ted Kremenekaead1532007-09-27 18:20:22 +0000229 typedef DataflowSolver<UninitializedValues,TransferFuncs,Merge> Solver;
230}
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000231
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000232//===----------------------------------------------------------------------===//
233// Unitialized values checker. Scan an AST and flag variable uses
234//===----------------------------------------------------------------------===//
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000235
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000236UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {}
237
238namespace {
Ted Kremenekc2b51d82008-01-08 18:19:08 +0000239class VISIBILITY_HIDDEN UninitializedValuesChecker
240 : public UninitializedValues::ObserverTy {
241
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000242 ASTContext &Ctx;
243 Diagnostic &Diags;
Ted Kremenek2bf55142007-09-17 20:49:30 +0000244 llvm::SmallPtrSet<BlockVarDecl*,10> AlreadyWarned;
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000245
246public:
247 UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags)
248 : Ctx(ctx), Diags(diags) {}
249
250 virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V,
251 UninitializedValues::AnalysisDataTy& AD,
Ted Kremenek2bf55142007-09-17 20:49:30 +0000252 DeclRefExpr* DR, BlockVarDecl* VD) {
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000253
Ted Kremenek43a16982007-09-18 21:43:18 +0000254 assert ( AD.isTracked(VD) && "Unknown VarDecl.");
255
Ted Kremenekaead1532007-09-27 18:20:22 +0000256 if (V(VD,AD) == Uninitialized)
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000257 if (AlreadyWarned.insert(VD))
Ted Kremenek9c728dc2007-12-12 22:39:36 +0000258 Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()),
259 diag::warn_uninit_val);
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000260 }
261};
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000262} // end anonymous namespace
263
Ted Kremenek2bf55142007-09-17 20:49:30 +0000264namespace clang {
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000265void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags,
266 bool FullUninitTaint) {
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000267
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000268 // Compute the unitialized values information.
Ted Kremenek11e72182007-10-01 20:33:52 +0000269 UninitializedValues U(cfg);
Ted Kremeneka1de8c72007-09-28 00:09:38 +0000270 U.getAnalysisData().FullUninitTaint = FullUninitTaint;
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000271 Solver S(U);
Ted Kremenekcd5860c2007-09-17 19:59:27 +0000272 S.runOnCFG(cfg);
273
274 // Scan for DeclRefExprs that use uninitialized values.
275 UninitializedValuesChecker Observer(Ctx,Diags);
276 U.getAnalysisData().Observer = &Observer;
Ted Kremenek294a7c92007-09-18 21:08:21 +0000277 S.runOnAllBlocks(cfg);
Ted Kremenek13ed7fe2007-09-14 22:49:21 +0000278}
Ted Kremenek294a7c92007-09-18 21:08:21 +0000279} // end namespace clang