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