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 
24 using namespace clang;
25 
26 //===----------------------------------------------------------------------===//
27 // Dataflow initialization logic.
28 //===----------------------------------------------------------------------===//
29 
30 namespace {
31 
32 class VISIBILITY_HIDDEN RegisterDecls
33   : public CFGRecStmtDeclVisitor<RegisterDecls> {
34 
35   UninitializedValues::AnalysisDataTy& AD;
36 public:
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 
45 void UninitializedValues::InitializeValues(const CFG& cfg) {
46   RegisterDecls R(getAnalysisData());
47   cfg.VisitBlockStmts(R);
48 }
49 
50 //===----------------------------------------------------------------------===//
51 // Transfer functions.
52 //===----------------------------------------------------------------------===//
53 
54 namespace {
55 class VISIBILITY_HIDDEN TransferFuncs
56   : public CFGStmtVisitor<TransferFuncs,bool> {
57 
58   UninitializedValues::ValTy V;
59   UninitializedValues::AnalysisDataTy& AD;
60 public:
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 
86 static const bool Initialized = false;
87 static const bool Uninitialized = true;
88 
89 bool 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 
110 static 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 
122 bool 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 
135 bool 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 
162 bool TransferFuncs::VisitCallExpr(CallExpr* C) {
163   VisitChildren(C);
164   return Initialized;
165 }
166 
167 bool 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 
183 bool
184 TransferFuncs::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 
212 bool 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 
223 bool 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 
235 bool 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 
240 bool 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 
260 namespace {
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 
269 UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {}
270 
271 namespace {
272 class VISIBILITY_HIDDEN UninitializedValuesChecker
273   : public UninitializedValues::ObserverTy {
274 
275   ASTContext &Ctx;
276   Diagnostic &Diags;
277   llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned;
278 
279 public:
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 
297 namespace clang {
298 void 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