UninitializedValues.cpp revision ea285162342df160e7860e26528bc7110bc6c0cd 
1//==- UninitializedValues.cpp - Find Uninitialized 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 file implements Uninitialized Values analysis for source-level CFGs.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Analysis/Analyses/UninitializedValues.h"
15#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
16#include "clang/Analysis/AnalysisDiagnostic.h"
17#include "clang/AST/ASTContext.h"
18#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
19
20#include "llvm/ADT/SmallPtrSet.h"
21
22using namespace clang;
23
24//===----------------------------------------------------------------------===//
25// Dataflow initialization logic.
26//===----------------------------------------------------------------------===//
27
28namespace {
29
30class RegisterDecls
31  : public CFGRecStmtDeclVisitor<RegisterDecls> {
32
33  UninitializedValues::AnalysisDataTy& AD;
34public:
35  RegisterDecls(UninitializedValues::AnalysisDataTy& ad) :  AD(ad) {}
36
37  void VisitVarDecl(VarDecl* VD) { AD.Register(VD); }
38  CFG& getCFG() { return AD.getCFG(); }
39};
40
41} // end anonymous namespace
42
43void UninitializedValues::InitializeValues(const CFG& cfg) {
44  RegisterDecls R(getAnalysisData());
45  cfg.VisitBlockStmts(R);
46}
47
48//===----------------------------------------------------------------------===//
49// Transfer functions.
50//===----------------------------------------------------------------------===//
51
52namespace {
53class TransferFuncs
54  : public CFGStmtVisitor<TransferFuncs,bool> {
55
56  UninitializedValues::ValTy V;
57  UninitializedValues::AnalysisDataTy& AD;
58public:
59  TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {}
60
61  UninitializedValues::ValTy& getVal() { return V; }
62  CFG& getCFG() { return AD.getCFG(); }
63
64  void SetTopValue(UninitializedValues::ValTy& X) {
65    X.setDeclValues(AD);
66    X.resetBlkExprValues(AD);
67  }
68
69  bool VisitDeclRefExpr(DeclRefExpr* DR);
70  bool VisitBinaryOperator(BinaryOperator* B);
71  bool VisitUnaryOperator(UnaryOperator* U);
72  bool VisitStmt(Stmt* S);
73  bool VisitCallExpr(CallExpr* C);
74  bool VisitDeclStmt(DeclStmt* D);
75  bool VisitConditionalOperator(ConditionalOperator* C);
76  bool BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
77
78  bool Visit(Stmt *S);
79  bool BlockStmt_VisitExpr(Expr* E);
80
81  void VisitTerminator(CFGBlock* B) { }
82};
83
84static const bool Initialized = false;
85static const bool Uninitialized = true;
86
87bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
88
89  if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
90    if (VD->isBlockVarDecl()) {
91
92      if (AD.Observer)
93        AD.Observer->ObserveDeclRefExpr(V, AD, DR, VD);
94
95      // Pseudo-hack to prevent cascade of warnings.  If an accessed variable
96      // is uninitialized, then we are already going to flag a warning for
97      // this variable, which a "source" of uninitialized values.
98      // We can otherwise do a full "taint" of uninitialized values.  The
99      // client has both options by toggling AD.FullUninitTaint.
100
101      if (AD.FullUninitTaint)
102        return V(VD,AD);
103    }
104
105  return Initialized;
106}
107
108static VarDecl* FindBlockVarDecl(Expr* E) {
109
110  // Blast through casts and parentheses to find any DeclRefExprs that
111  // refer to a block VarDecl.
112
113  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
114    if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
115      if (VD->isBlockVarDecl()) return VD;
116
117  return NULL;
118}
119
120bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
121
122  if (VarDecl* VD = FindBlockVarDecl(B->getLHS()))
123    if (B->isAssignmentOp()) {
124      if (B->getOpcode() == BinaryOperator::Assign)
125        return V(VD,AD) = Visit(B->getRHS());
126      else // Handle +=, -=, *=, etc.  We do want '&', not '&&'.
127        return V(VD,AD) = Visit(B->getLHS()) & Visit(B->getRHS());
128    }
129
130  return VisitStmt(B);
131}
132
133bool TransferFuncs::VisitDeclStmt(DeclStmt* S) {
134  for (DeclStmt::decl_iterator I=S->decl_begin(), E=S->decl_end(); I!=E; ++I) {
135    VarDecl *VD = dyn_cast<VarDecl>(*I);
136    if (VD && VD->isBlockVarDecl()) {
137      if (Stmt* I = VD->getInit()) {
138        // Visit the subexpression to check for uses of uninitialized values,
139        // even if we don't propagate that value.
140        bool isSubExprUninit = Visit(I);
141        V(VD,AD) = AD.FullUninitTaint ? isSubExprUninit : Initialized;
142      }
143      else {
144        // Special case for declarations of array types.  For things like:
145        //
146        //  char x[10];
147        //
148        // we should treat "x" as being initialized, because the variable
149        // "x" really refers to the memory block.  Clearly x[1] is
150        // uninitialized, but expressions like "(char *) x" really do refer to
151        // an initialized value.  This simple dataflow analysis does not reason
152        // about the contents of arrays, although it could be potentially
153        // extended to do so if the array were of constant size.
154        if (VD->getType()->isArrayType())
155          V(VD,AD) = Initialized;
156        else
157          V(VD,AD) = Uninitialized;
158      }
159    }
160  }
161  return Uninitialized; // Value is never consumed.
162}
163
164bool TransferFuncs::VisitCallExpr(CallExpr* C) {
165  VisitChildren(C);
166  return Initialized;
167}
168
169bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
170  switch (U->getOpcode()) {
171    case UnaryOperator::AddrOf: {
172      VarDecl* VD = FindBlockVarDecl(U->getSubExpr());
173      if (VD && VD->isBlockVarDecl())
174        return V(VD,AD) = Initialized;
175      break;
176    }
177
178    default:
179      break;
180  }
181
182  return Visit(U->getSubExpr());
183}
184
185bool
186TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
187  // This represents a use of the 'collection'
188  bool x = Visit(S->getCollection());
189
190  if (x == Uninitialized)
191    return Uninitialized;
192
193  // This represents an initialization of the 'element' value.
194  Stmt* Element = S->getElement();
195  VarDecl* VD = 0;
196
197  if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
198    VD = cast<VarDecl>(DS->getSingleDecl());
199  else {
200    Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
201
202    // Initialize the value of the reference variable.
203    if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(ElemExpr))
204      VD = cast<VarDecl>(DR->getDecl());
205    else
206      return Visit(ElemExpr);
207  }
208
209  V(VD,AD) = Initialized;
210  return Initialized;
211}
212
213
214bool TransferFuncs::VisitConditionalOperator(ConditionalOperator* C) {
215  Visit(C->getCond());
216
217  bool rhsResult = Visit(C->getRHS());
218  // Handle the GNU extension for missing LHS.
219  if (Expr *lhs = C->getLHS())
220    return Visit(lhs) & rhsResult; // Yes: we want &, not &&.
221  else
222    return rhsResult;
223}
224
225bool TransferFuncs::VisitStmt(Stmt* S) {
226  bool x = Initialized;
227
228  // We don't stop at the first subexpression that is Uninitialized because
229  // evaluating some subexpressions may result in propogating "Uninitialized"
230  // or "Initialized" to variables referenced in the other subexpressions.
231  for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I)
232    if (*I && Visit(*I) == Uninitialized) x = Uninitialized;
233
234  return x;
235}
236
237bool TransferFuncs::Visit(Stmt *S) {
238  if (AD.isTracked(static_cast<Expr*>(S))) return V(static_cast<Expr*>(S),AD);
239  else return static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(S);
240}
241
242bool TransferFuncs::BlockStmt_VisitExpr(Expr* E) {
243  bool x = static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(E);
244  if (AD.isTracked(E)) V(E,AD) = x;
245  return x;
246}
247
248} // end anonymous namespace
249
250//===----------------------------------------------------------------------===//
251// Merge operator.
252//
253//  In our transfer functions we take the approach that any
254//  combination of uninitialized values, e.g.
255//      Uninitialized + ___ = Uninitialized.
256//
257//  Merges take the same approach, preferring soundness.  At a confluence point,
258//  if any predecessor has a variable marked uninitialized, the value is
259//  uninitialized at the confluence point.
260//===----------------------------------------------------------------------===//
261
262namespace {
263  typedef StmtDeclBitVector_Types::Union Merge;
264  typedef DataflowSolver<UninitializedValues,TransferFuncs,Merge> Solver;
265}
266
267//===----------------------------------------------------------------------===//
268// Uninitialized values checker.   Scan an AST and flag variable uses
269//===----------------------------------------------------------------------===//
270
271UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {}
272
273namespace {
274class UninitializedValuesChecker
275  : public UninitializedValues::ObserverTy {
276
277  ASTContext &Ctx;
278  Diagnostic &Diags;
279  llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned;
280
281public:
282  UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags)
283    : Ctx(ctx), Diags(diags) {}
284
285  virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V,
286                                  UninitializedValues::AnalysisDataTy& AD,
287                                  DeclRefExpr* DR, VarDecl* VD) {
288
289    assert ( AD.isTracked(VD) && "Unknown VarDecl.");
290
291    if (V(VD,AD) == Uninitialized)
292      if (AlreadyWarned.insert(VD))
293        Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()),
294                     diag::warn_uninit_val);
295  }
296};
297} // end anonymous namespace
298
299namespace clang {
300void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags,
301                              bool FullUninitTaint) {
302
303  // Compute the uninitialized values information.
304  UninitializedValues U(cfg);
305  U.getAnalysisData().FullUninitTaint = FullUninitTaint;
306  Solver S(U);
307  S.runOnCFG(cfg);
308
309  // Scan for DeclRefExprs that use uninitialized values.
310  UninitializedValuesChecker Observer(Ctx,Diags);
311  U.getAnalysisData().Observer = &Observer;
312  S.runOnAllBlocks(cfg);
313}
314} // end namespace clang
315