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