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 
22 using namespace clang;
23 
24 //===----------------------------------------------------------------------===//
25 // Dataflow initialization logic.
26 //===----------------------------------------------------------------------===//
27 
28 namespace {
29 
30 class RegisterDecls
31   : public CFGRecStmtDeclVisitor<RegisterDecls> {
32 
33   UninitializedValues::AnalysisDataTy& AD;
34 public:
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 
43 void UninitializedValues::InitializeValues(const CFG& cfg) {
44   RegisterDecls R(getAnalysisData());
45   cfg.VisitBlockStmts(R);
46 }
47 
48 //===----------------------------------------------------------------------===//
49 // Transfer functions.
50 //===----------------------------------------------------------------------===//
51 
52 namespace {
53 class TransferFuncs
54   : public CFGStmtVisitor<TransferFuncs,bool> {
55 
56   UninitializedValues::ValTy V;
57   UninitializedValues::AnalysisDataTy& AD;
58 public:
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 
84 static const bool Initialized = false;
85 static const bool Uninitialized = true;
86 
87 bool 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 
108 static 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 
120 bool 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 
133 bool 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 
164 bool TransferFuncs::VisitCallExpr(CallExpr* C) {
165   VisitChildren(C);
166   return Initialized;
167 }
168 
169 bool 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 
185 bool
186 TransferFuncs::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 
214 bool 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 
225 bool 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 
237 bool 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 
242 bool 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 
262 namespace {
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 
271 UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {}
272 
273 namespace {
274 class UninitializedValuesChecker
275   : public UninitializedValues::ObserverTy {
276 
277   ASTContext &Ctx;
278   Diagnostic &Diags;
279   llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned;
280 
281 public:
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 
299 namespace clang {
300 void 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