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