UninitializedValues.cpp revision b6bbcc9995186799a60ce17d0c1acff31601653a
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 22using namespace clang; 23 24//===----------------------------------------------------------------------===// 25// Dataflow initialization logic. 26//===----------------------------------------------------------------------===// 27 28namespace { 29 30class RegisterDecls 31 : public CFGRecStmtDeclVisitor<RegisterDecls> { 32 33 UninitializedValues::AnalysisDataTy& AD; 34public: 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 43void UninitializedValues::InitializeValues(const CFG& cfg) { 44 RegisterDecls R(getAnalysisData()); 45 cfg.VisitBlockStmts(R); 46} 47 48//===----------------------------------------------------------------------===// 49// Transfer functions. 50//===----------------------------------------------------------------------===// 51 52namespace { 53class TransferFuncs 54 : public CFGStmtVisitor<TransferFuncs,bool> { 55 56 UninitializedValues::ValTy V; 57 UninitializedValues::AnalysisDataTy& AD; 58public: 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 84static const bool Initialized = false; 85static const bool Uninitialized = true; 86 87bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { 88 89 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) 90 if (VD->isLocalVarDecl()) { 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 108static 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->isLocalVarDecl()) return VD; 116 117 return NULL; 118} 119 120bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { 121 122 if (VarDecl* VD = FindBlockVarDecl(B->getLHS())) 123 if (B->isAssignmentOp()) { 124 if (B->getOpcode() == BO_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 133bool 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->isLocalVarDecl()) { 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 164bool TransferFuncs::VisitCallExpr(CallExpr* C) { 165 VisitChildren(C); 166 return Initialized; 167} 168 169bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { 170 switch (U->getOpcode()) { 171 case UO_AddrOf: { 172 VarDecl* VD = FindBlockVarDecl(U->getSubExpr()); 173 if (VD && VD->isLocalVarDecl()) 174 return V(VD,AD) = Initialized; 175 break; 176 } 177 178 default: 179 break; 180 } 181 182 return Visit(U->getSubExpr()); 183} 184 185bool 186TransferFuncs::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 214bool 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 225bool 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 237bool 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 242bool 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 262namespace { 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 271UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {} 272 273namespace { 274class UninitializedValuesChecker 275 : public UninitializedValues::ObserverTy { 276 277 ASTContext &Ctx; 278 Diagnostic &Diags; 279 llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned; 280 281public: 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 299namespace clang { 300void 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