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