UninitializedValues.cpp revision 243830
1110603Sphk//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// 2110603Sphk// 3110603Sphk// The LLVM Compiler Infrastructure 4110603Sphk// 5110603Sphk// This file is distributed under the University of Illinois Open Source 6110603Sphk// License. See LICENSE.TXT for details. 7110603Sphk// 8110603Sphk//===----------------------------------------------------------------------===// 9110603Sphk// 10110603Sphk// This file implements uninitialized values analysis for source-level CFGs. 11110603Sphk// 12110603Sphk//===----------------------------------------------------------------------===// 13110603Sphk 14110603Sphk#include <utility> 15110603Sphk#include "llvm/ADT/Optional.h" 16110603Sphk#include "llvm/ADT/SmallBitVector.h" 17110603Sphk#include "llvm/ADT/SmallVector.h" 18110603Sphk#include "llvm/ADT/PackedVector.h" 19110603Sphk#include "llvm/ADT/DenseMap.h" 20110603Sphk#include "clang/AST/ASTContext.h" 21110603Sphk#include "clang/AST/Decl.h" 22110603Sphk#include "clang/Analysis/CFG.h" 23110603Sphk#include "clang/Analysis/AnalysisContext.h" 24110603Sphk#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 25110603Sphk#include "clang/Analysis/Analyses/UninitializedValues.h" 26110603Sphk#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" 27110603Sphk#include "llvm/Support/SaveAndRestore.h" 28110603Sphk 29110603Sphkusing namespace clang; 30110603Sphk 31110603Sphk#define DEBUG_LOGGING 0 32110603Sphk 33110603Sphkstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 34110603Sphk if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 35110603Sphk !vd->isExceptionVariable() && 36110603Sphk vd->getDeclContext() == dc) { 37110603Sphk QualType ty = vd->getType(); 38110603Sphk return ty->isScalarType() || ty->isVectorType(); 39110603Sphk } 40110603Sphk return false; 41110603Sphk} 42110603Sphk 43110603Sphk//------------------------------------------------------------------------====// 44110603Sphk// DeclToIndex: a mapping from Decls we track to value indices. 45110603Sphk//====------------------------------------------------------------------------// 46110603Sphk 47110603Sphknamespace { 48110603Sphkclass DeclToIndex { 49110603Sphk llvm::DenseMap<const VarDecl *, unsigned> map; 50110603Sphkpublic: 51110603Sphk DeclToIndex() {} 52110603Sphk 53110603Sphk /// Compute the actual mapping from declarations to bits. 54110603Sphk void computeMap(const DeclContext &dc); 55110603Sphk 56110603Sphk /// Return the number of declarations in the map. 57110603Sphk unsigned size() const { return map.size(); } 58110603Sphk 59110603Sphk /// Returns the bit vector index for a given declaration. 60110603Sphk llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const; 61110603Sphk}; 62110603Sphk} 63110603Sphk 64110603Sphkvoid DeclToIndex::computeMap(const DeclContext &dc) { 65110603Sphk unsigned count = 0; 66110603Sphk DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 67110603Sphk E(dc.decls_end()); 68110603Sphk for ( ; I != E; ++I) { 69110603Sphk const VarDecl *vd = *I; 70110603Sphk if (isTrackedVar(vd, &dc)) 71181463Sdes map[vd] = count++; 72110603Sphk } 73126786Sjhb} 74110603Sphk 75110603Sphkllvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 76110603Sphk llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 77110603Sphk if (I == map.end()) 78110603Sphk return llvm::Optional<unsigned>(); 79110603Sphk return I->second; 80110603Sphk} 81110603Sphk 82110603Sphk//------------------------------------------------------------------------====// 83110603Sphk// CFGBlockValues: dataflow values for CFG blocks. 84110603Sphk//====------------------------------------------------------------------------// 85110603Sphk 86110603Sphk// These values are defined in such a way that a merge can be done using 87180369Slulf// a bitwise OR. 88180369Slulfenum Value { Unknown = 0x0, /* 00 */ 89180369Slulf Initialized = 0x1, /* 01 */ 90180369Slulf Uninitialized = 0x2, /* 10 */ 91180369Slulf MayUninitialized = 0x3 /* 11 */ }; 92126786Sjhb 93126786Sjhbstatic bool isUninitialized(const Value v) { 94126786Sjhb return v >= Uninitialized; 95126786Sjhb} 96110603Sphkstatic bool isAlwaysUninit(const Value v) { 97110603Sphk return v == Uninitialized; 98110603Sphk} 99110603Sphk 100180369Slulfnamespace { 101180369Slulf 102180369Slulftypedef llvm::PackedVector<Value, 2, llvm::SmallBitVector> ValueVector; 103180369Slulf 104180369Slulfclass CFGBlockValues { 105126786Sjhb const CFG &cfg; 106126786Sjhb SmallVector<ValueVector, 8> vals; 107126786Sjhb ValueVector scratch; 108126786Sjhb DeclToIndex declToIndex; 109126786Sjhbpublic: 110110603Sphk CFGBlockValues(const CFG &cfg); 111110603Sphk 112110603Sphk unsigned getNumEntries() const { return declToIndex.size(); } 113126786Sjhb 114110603Sphk void computeSetOfDeclarations(const DeclContext &dc); 115110603Sphk ValueVector &getValueVector(const CFGBlock *block) { 116110603Sphk return vals[block->getBlockID()]; 117110603Sphk } 118180369Slulf 119180369Slulf void setAllScratchValues(Value V); 120180369Slulf void mergeIntoScratch(ValueVector const &source, bool isFirst); 121180369Slulf bool updateValueVectorWithScratch(const CFGBlock *block); 122180369Slulf 123126786Sjhb bool hasNoDeclarations() const { 124126786Sjhb return declToIndex.size() == 0; 125126786Sjhb } 126126786Sjhb 127110603Sphk void resetScratch(); 128110603Sphk 129110603Sphk ValueVector::reference operator[](const VarDecl *vd); 130126786Sjhb 131110603Sphk Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, 132110603Sphk const VarDecl *vd) { 133110603Sphk const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 134126786Sjhb assert(idx.hasValue()); 135110603Sphk return getValueVector(block)[idx.getValue()]; 136110603Sphk } 137110603Sphk}; 138110603Sphk} // end anonymous namespace 139180369Slulf 140180369SlulfCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} 141180369Slulf 142180369Slulfvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 143180369Slulf declToIndex.computeMap(dc); 144126786Sjhb unsigned decls = declToIndex.size(); 145126786Sjhb scratch.resize(decls); 146126786Sjhb unsigned n = cfg.getNumBlockIDs(); 147126786Sjhb if (!n) 148126786Sjhb return; 149110603Sphk vals.resize(n); 150110603Sphk for (unsigned i = 0; i < n; ++i) 151110603Sphk vals[i].resize(decls); 152126786Sjhb} 153110603Sphk 154110603Sphk#if DEBUG_LOGGING 155110603Sphkstatic void printVector(const CFGBlock *block, ValueVector &bv, 156110603Sphk unsigned num) { 157126786Sjhb llvm::errs() << block->getBlockID() << " :"; 158110603Sphk for (unsigned i = 0; i < bv.size(); ++i) { 159110603Sphk llvm::errs() << ' ' << bv[i]; 160110603Sphk } 161126786Sjhb llvm::errs() << " : " << num << '\n'; 162110603Sphk} 163110603Sphk#endif 164110603Sphk 165126786Sjhbvoid CFGBlockValues::setAllScratchValues(Value V) { 166110603Sphk for (unsigned I = 0, E = scratch.size(); I != E; ++I) 167110603Sphk scratch[I] = V; 168110603Sphk} 169126786Sjhb 170110603Sphkvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 171110603Sphk bool isFirst) { 172110603Sphk if (isFirst) 173110603Sphk scratch = source; 174110603Sphk else 175110603Sphk scratch |= source; 176110603Sphk} 177110603Sphk 178110603Sphkbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 179110603Sphk ValueVector &dst = getValueVector(block); 180110603Sphk bool changed = (dst != scratch); 181110603Sphk if (changed) 182110603Sphk dst = scratch; 183110603Sphk#if DEBUG_LOGGING 184110603Sphk printVector(block, scratch, 0); 185180369Slulf#endif 186180369Slulf return changed; 187180369Slulf} 188180369Slulf 189180369Slulfvoid CFGBlockValues::resetScratch() { 190110603Sphk scratch.reset(); 191110603Sphk} 192110603Sphk 193110603SphkValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 194110603Sphk const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 195110603Sphk assert(idx.hasValue()); 196110603Sphk return scratch[idx.getValue()]; 197110603Sphk} 198110603Sphk 199110603Sphk//------------------------------------------------------------------------====// 200126786Sjhb// Worklist: worklist for dataflow analysis. 201110603Sphk//====------------------------------------------------------------------------// 202110603Sphk 203126786Sjhbnamespace { 204110603Sphkclass DataflowWorklist { 205110603Sphk SmallVector<const CFGBlock *, 20> worklist; 206126786Sjhb llvm::BitVector enqueuedBlocks; 207110603Sphkpublic: 208110603Sphk DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} 209110603Sphk 210110603Sphk void enqueueSuccessors(const CFGBlock *block); 211126786Sjhb const CFGBlock *dequeue(); 212110603Sphk}; 213110603Sphk} 214110603Sphk 215110603Sphkvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 216126786Sjhb unsigned OldWorklistSize = worklist.size(); 217110603Sphk for (CFGBlock::const_succ_iterator I = block->succ_begin(), 218110603Sphk E = block->succ_end(); I != E; ++I) { 219110603Sphk const CFGBlock *Successor = *I; 220126786Sjhb if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 221110603Sphk continue; 222110603Sphk worklist.push_back(Successor); 223110603Sphk enqueuedBlocks[Successor->getBlockID()] = true; 224126786Sjhb } 225110603Sphk if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 226110603Sphk return; 227110603Sphk 228110603Sphk // Rotate the newly added blocks to the start of the worklist so that it forms 229126786Sjhb // a proper queue when we pop off the end of the worklist. 230110603Sphk std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize, 231110603Sphk worklist.end()); 232110603Sphk} 233110603Sphk 234110603Sphkconst CFGBlock *DataflowWorklist::dequeue() { 235110603Sphk if (worklist.empty()) 236110603Sphk return 0; 237110603Sphk const CFGBlock *b = worklist.back(); 238110603Sphk worklist.pop_back(); 239110603Sphk enqueuedBlocks[b->getBlockID()] = false; 240180369Slulf return b; 241180369Slulf} 242180369Slulf 243180369Slulf//------------------------------------------------------------------------====// 244180369Slulf// Classification of DeclRefExprs as use or initialization. 245180369Slulf//====------------------------------------------------------------------------// 246126786Sjhb 247180369Slulfnamespace { 248180369Slulfclass FindVarResult { 249180369Slulf const VarDecl *vd; 250180369Slulf const DeclRefExpr *dr; 251180369Slulfpublic: 252126786Sjhb FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} 253126786Sjhb 254110603Sphk const DeclRefExpr *getDeclRefExpr() const { return dr; } 255110603Sphk const VarDecl *getDecl() const { return vd; } 256110603Sphk}; 257110603Sphk 258112340Sphkstatic const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 259110603Sphk while (Ex) { 260110603Sphk Ex = Ex->IgnoreParenNoopCasts(C); 261110603Sphk if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 262110603Sphk if (CE->getCastKind() == CK_LValueBitCast) { 263110603Sphk Ex = CE->getSubExpr(); 264110603Sphk continue; 265110603Sphk } 266110603Sphk } 267110603Sphk break; 268110603Sphk } 269110603Sphk return Ex; 270110603Sphk} 271110603Sphk 272110603Sphk/// If E is an expression comprising a reference to a single variable, find that 273110603Sphk/// variable. 274110603Sphkstatic FindVarResult findVar(const Expr *E, const DeclContext *DC) { 275110603Sphk if (const DeclRefExpr *DRE = 276110603Sphk dyn_cast<DeclRefExpr>(stripCasts(DC->getParentASTContext(), E))) 277110603Sphk if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) 278110603Sphk if (isTrackedVar(VD, DC)) 279110603Sphk return FindVarResult(VD, DRE); 280110603Sphk return FindVarResult(0, 0); 281110603Sphk} 282110603Sphk 283110603Sphk/// \brief Classify each DeclRefExpr as an initialization or a use. Any 284110603Sphk/// DeclRefExpr which isn't explicitly classified will be assumed to have 285110603Sphk/// escaped the analysis and will be treated as an initialization. 286110603Sphkclass ClassifyRefs : public StmtVisitor<ClassifyRefs> { 287110603Sphkpublic: 288110603Sphk enum Class { 289110603Sphk Init, 290110603Sphk Use, 291110603Sphk SelfInit, 292110603Sphk Ignore 293110603Sphk }; 294110603Sphk 295110603Sphkprivate: 296110603Sphk const DeclContext *DC; 297110603Sphk llvm::DenseMap<const DeclRefExpr*, Class> Classification; 298110603Sphk 299110603Sphk bool isTrackedVar(const VarDecl *VD) const { 300110603Sphk return ::isTrackedVar(VD, DC); 301110603Sphk } 302110603Sphk 303110603Sphk void classify(const Expr *E, Class C); 304110603Sphk 305110603Sphkpublic: 306110603Sphk ClassifyRefs(AnalysisDeclContext &AC) : DC(cast<DeclContext>(AC.getDecl())) {} 307110603Sphk 308112340Sphk void VisitDeclStmt(DeclStmt *DS); 309110603Sphk void VisitUnaryOperator(UnaryOperator *UO); 310110603Sphk void VisitBinaryOperator(BinaryOperator *BO); 311110603Sphk void VisitCallExpr(CallExpr *CE); 312126786Sjhb void VisitCastExpr(CastExpr *CE); 313126786Sjhb 314110603Sphk void operator()(Stmt *S) { Visit(S); } 315110603Sphk 316110603Sphk Class get(const DeclRefExpr *DRE) const { 317110603Sphk llvm::DenseMap<const DeclRefExpr*, Class>::const_iterator I 318110603Sphk = Classification.find(DRE); 319110603Sphk if (I != Classification.end()) 320110603Sphk return I->second; 321110603Sphk 322110603Sphk const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); 323110603Sphk if (!VD || !isTrackedVar(VD)) 324110603Sphk return Ignore; 325110603Sphk 326110603Sphk return Init; 327110603Sphk } 328110603Sphk}; 329110603Sphk} 330126786Sjhb 331110603Sphkstatic const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { 332110603Sphk if (Expr *Init = VD->getInit()) { 333110603Sphk const DeclRefExpr *DRE 334110603Sphk = dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init)); 335110603Sphk if (DRE && DRE->getDecl() == VD) 336110603Sphk return DRE; 337110603Sphk } 338110603Sphk return 0; 339110603Sphk} 340110603Sphk 341110603Sphkvoid ClassifyRefs::classify(const Expr *E, Class C) { 342110603Sphk FindVarResult Var = findVar(E, DC); 343126786Sjhb if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) 344126786Sjhb Classification[DRE] = std::max(Classification[DRE], C); 345110603Sphk} 346110603Sphk 347110603Sphkvoid ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { 348110603Sphk for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); 349126786Sjhb DI != DE; ++DI) { 350126786Sjhb VarDecl *VD = dyn_cast<VarDecl>(*DI); 351126786Sjhb if (VD && isTrackedVar(VD)) 352126786Sjhb if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) 353110603Sphk Classification[DRE] = SelfInit; 354126786Sjhb } 355126786Sjhb} 356126786Sjhb 357126786Sjhbvoid ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { 358110603Sphk // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this 359126786Sjhb // is not a compound-assignment, we will treat it as initializing the variable 360126786Sjhb // when TransferFunctions visits it. A compound-assignment does not affect 361126786Sjhb // whether a variable is uninitialized, and there's no point counting it as a 362126786Sjhb // use. 363110603Sphk if (BO->isCompoundAssignmentOp()) 364110603Sphk classify(BO->getLHS(), Use); 365126786Sjhb else if (BO->getOpcode() == BO_Assign) 366126786Sjhb classify(BO->getLHS(), Ignore); 367126786Sjhb} 368126786Sjhb 369110603Sphkvoid ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { 370110603Sphk // Increment and decrement are uses despite there being no lvalue-to-rvalue 371110603Sphk // conversion. 372110603Sphk if (UO->isIncrementDecrementOp()) 373110603Sphk classify(UO->getSubExpr(), Use); 374126786Sjhb} 375126786Sjhb 376126786Sjhbvoid ClassifyRefs::VisitCallExpr(CallExpr *CE) { 377126786Sjhb // If a value is passed by const reference to a function, we should not assume 378126786Sjhb // that it is initialized by the call, and we conservatively do not assume 379126786Sjhb // that it is used. 380126786Sjhb for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); 381110603Sphk I != E; ++I) 382126786Sjhb if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) 383126786Sjhb classify(*I, Ignore); 384126786Sjhb} 385126786Sjhb 386126786Sjhbvoid ClassifyRefs::VisitCastExpr(CastExpr *CE) { 387126786Sjhb if (CE->getCastKind() == CK_LValueToRValue) 388126786Sjhb classify(CE->getSubExpr(), Use); 389126748Sphk else if (CStyleCastExpr *CSE = dyn_cast<CStyleCastExpr>(CE)) { 390126786Sjhb if (CSE->getType()->isVoidType()) { 391126786Sjhb // Squelch any detected load of an uninitialized value if 392126748Sphk // we cast it to void. 393110603Sphk // e.g. (void) x; 394110603Sphk classify(CSE->getSubExpr(), Ignore); 395110603Sphk } 396110603Sphk } 397110603Sphk} 398110603Sphk 399110603Sphk//------------------------------------------------------------------------====// 400110603Sphk// Transfer function for uninitialized values analysis. 401110603Sphk//====------------------------------------------------------------------------// 402110603Sphk 403110603Sphknamespace { 404110603Sphkclass TransferFunctions : public StmtVisitor<TransferFunctions> { 405110603Sphk CFGBlockValues &vals; 406146561Sphk const CFG &cfg; 407146561Sphk const CFGBlock *block; 408110603Sphk AnalysisDeclContext ∾ 409110603Sphk const ClassifyRefs &classification; 410110603Sphk ObjCNoReturn objCNoRet; 411110603Sphk UninitVariablesHandler *handler; 412110603Sphk 413110603Sphkpublic: 414110603Sphk TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 415110603Sphk const CFGBlock *block, AnalysisDeclContext &ac, 416110603Sphk const ClassifyRefs &classification, 417110603Sphk UninitVariablesHandler *handler) 418110603Sphk : vals(vals), cfg(cfg), block(block), ac(ac), 419110603Sphk classification(classification), objCNoRet(ac.getASTContext()), 420110603Sphk handler(handler) {} 421110603Sphk 422126786Sjhb void reportUse(const Expr *ex, const VarDecl *vd); 423126786Sjhb 424126786Sjhb void VisitBinaryOperator(BinaryOperator *bo); 425110603Sphk void VisitBlockExpr(BlockExpr *be); 426110603Sphk void VisitCallExpr(CallExpr *ce); 427110603Sphk void VisitDeclRefExpr(DeclRefExpr *dr); 428110603Sphk void VisitDeclStmt(DeclStmt *ds); 429110603Sphk void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); 430110603Sphk void VisitObjCMessageExpr(ObjCMessageExpr *ME); 431110603Sphk 432110603Sphk bool isTrackedVar(const VarDecl *vd) { 433110603Sphk return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 434110603Sphk } 435110603Sphk 436110603Sphk FindVarResult findVar(const Expr *ex) { 437126786Sjhb return ::findVar(ex, cast<DeclContext>(ac.getDecl())); 438126786Sjhb } 439110603Sphk 440126786Sjhb UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { 441110603Sphk UninitUse Use(ex, isAlwaysUninit(v)); 442110603Sphk 443126786Sjhb assert(isUninitialized(v)); 444126786Sjhb if (Use.getKind() == UninitUse::Always) 445126786Sjhb return Use; 446110603Sphk 447126786Sjhb // If an edge which leads unconditionally to this use did not initialize 448110603Sphk // the variable, we can say something stronger than 'may be uninitialized': 449110603Sphk // we can say 'either it's used uninitialized or you have dead code'. 450126786Sjhb // 451126786Sjhb // We track the number of successors of a node which have been visited, and 452126786Sjhb // visit a node once we have visited all of its successors. Only edges where 453110603Sphk // the variable might still be uninitialized are followed. Since a variable 454126786Sjhb // can't transfer from being initialized to being uninitialized, this will 455110603Sphk // trace out the subgraph which inevitably leads to the use and does not 456110603Sphk // initialize the variable. We do not want to skip past loops, since their 457126786Sjhb // non-termination might be correlated with the initialization condition. 458126786Sjhb // 459126786Sjhb // For example: 460126786Sjhb // 461110603Sphk // void f(bool a, bool b) { 462110603Sphk // block1: int n; 463110603Sphk // if (a) { 464126786Sjhb // block2: if (b) 465110603Sphk // block3: n = 1; 466110603Sphk // block4: } else if (b) { 467126786Sjhb // block5: while (!a) { 468126786Sjhb // block6: do_work(&a); 469126786Sjhb // n = 2; 470110603Sphk // } 471110603Sphk // } 472110603Sphk // block7: if (a) 473110603Sphk // block8: g(); 474110603Sphk // block9: return n; 475110603Sphk // } 476110603Sphk // 477 // Starting from the maybe-uninitialized use in block 9: 478 // * Block 7 is not visited because we have only visited one of its two 479 // successors. 480 // * Block 8 is visited because we've visited its only successor. 481 // From block 8: 482 // * Block 7 is visited because we've now visited both of its successors. 483 // From block 7: 484 // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all 485 // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). 486 // * Block 3 is not visited because it initializes 'n'. 487 // Now the algorithm terminates, having visited blocks 7 and 8, and having 488 // found the frontier is blocks 2, 4, and 5. 489 // 490 // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 491 // and 4), so we report that any time either of those edges is taken (in 492 // each case when 'b == false'), 'n' is used uninitialized. 493 llvm::SmallVector<const CFGBlock*, 32> Queue; 494 llvm::SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0); 495 Queue.push_back(block); 496 // Specify that we've already visited all successors of the starting block. 497 // This has the dual purpose of ensuring we never add it to the queue, and 498 // of marking it as not being a candidate element of the frontier. 499 SuccsVisited[block->getBlockID()] = block->succ_size(); 500 while (!Queue.empty()) { 501 const CFGBlock *B = Queue.back(); 502 Queue.pop_back(); 503 for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); 504 I != E; ++I) { 505 const CFGBlock *Pred = *I; 506 if (vals.getValue(Pred, B, vd) == Initialized) 507 // This block initializes the variable. 508 continue; 509 510 unsigned &SV = SuccsVisited[Pred->getBlockID()]; 511 if (!SV) { 512 // When visiting the first successor of a block, mark all NULL 513 // successors as having been visited. 514 for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), 515 SE = Pred->succ_end(); 516 SI != SE; ++SI) 517 if (!*SI) 518 ++SV; 519 } 520 521 if (++SV == Pred->succ_size()) 522 // All paths from this block lead to the use and don't initialize the 523 // variable. 524 Queue.push_back(Pred); 525 } 526 } 527 528 // Scan the frontier, looking for blocks where the variable was 529 // uninitialized. 530 for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 531 const CFGBlock *Block = *BI; 532 unsigned BlockID = Block->getBlockID(); 533 const Stmt *Term = Block->getTerminator(); 534 if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && 535 Term) { 536 // This block inevitably leads to the use. If we have an edge from here 537 // to a post-dominator block, and the variable is uninitialized on that 538 // edge, we have found a bug. 539 for (CFGBlock::const_succ_iterator I = Block->succ_begin(), 540 E = Block->succ_end(); I != E; ++I) { 541 const CFGBlock *Succ = *I; 542 if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && 543 vals.getValue(Block, Succ, vd) == Uninitialized) { 544 // Switch cases are a special case: report the label to the caller 545 // as the 'terminator', not the switch statement itself. Suppress 546 // situations where no label matched: we can't be sure that's 547 // possible. 548 if (isa<SwitchStmt>(Term)) { 549 const Stmt *Label = Succ->getLabel(); 550 if (!Label || !isa<SwitchCase>(Label)) 551 // Might not be possible. 552 continue; 553 UninitUse::Branch Branch; 554 Branch.Terminator = Label; 555 Branch.Output = 0; // Ignored. 556 Use.addUninitBranch(Branch); 557 } else { 558 UninitUse::Branch Branch; 559 Branch.Terminator = Term; 560 Branch.Output = I - Block->succ_begin(); 561 Use.addUninitBranch(Branch); 562 } 563 } 564 } 565 } 566 } 567 568 return Use; 569 } 570}; 571} 572 573void TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { 574 if (!handler) 575 return; 576 Value v = vals[vd]; 577 if (isUninitialized(v)) 578 handler->handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); 579} 580 581void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { 582 // This represents an initialization of the 'element' value. 583 if (DeclStmt *DS = dyn_cast<DeclStmt>(FS->getElement())) { 584 const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 585 if (isTrackedVar(VD)) 586 vals[VD] = Initialized; 587 } 588} 589 590void TransferFunctions::VisitBlockExpr(BlockExpr *be) { 591 const BlockDecl *bd = be->getBlockDecl(); 592 for (BlockDecl::capture_const_iterator i = bd->capture_begin(), 593 e = bd->capture_end() ; i != e; ++i) { 594 const VarDecl *vd = i->getVariable(); 595 if (!isTrackedVar(vd)) 596 continue; 597 if (i->isByRef()) { 598 vals[vd] = Initialized; 599 continue; 600 } 601 reportUse(be, vd); 602 } 603} 604 605void TransferFunctions::VisitCallExpr(CallExpr *ce) { 606 if (Decl *Callee = ce->getCalleeDecl()) { 607 if (Callee->hasAttr<ReturnsTwiceAttr>()) { 608 // After a call to a function like setjmp or vfork, any variable which is 609 // initialized anywhere within this function may now be initialized. For 610 // now, just assume such a call initializes all variables. FIXME: Only 611 // mark variables as initialized if they have an initializer which is 612 // reachable from here. 613 vals.setAllScratchValues(Initialized); 614 } 615 else if (Callee->hasAttr<AnalyzerNoReturnAttr>()) { 616 // Functions labeled like "analyzer_noreturn" are often used to denote 617 // "panic" functions that in special debug situations can still return, 618 // but for the most part should not be treated as returning. This is a 619 // useful annotation borrowed from the static analyzer that is useful for 620 // suppressing branch-specific false positives when we call one of these 621 // functions but keep pretending the path continues (when in reality the 622 // user doesn't care). 623 vals.setAllScratchValues(Unknown); 624 } 625 } 626} 627 628void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 629 switch (classification.get(dr)) { 630 case ClassifyRefs::Ignore: 631 break; 632 case ClassifyRefs::Use: 633 reportUse(dr, cast<VarDecl>(dr->getDecl())); 634 break; 635 case ClassifyRefs::Init: 636 vals[cast<VarDecl>(dr->getDecl())] = Initialized; 637 break; 638 case ClassifyRefs::SelfInit: 639 if (handler) 640 handler->handleSelfInit(cast<VarDecl>(dr->getDecl())); 641 break; 642 } 643} 644 645void TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { 646 if (BO->getOpcode() == BO_Assign) { 647 FindVarResult Var = findVar(BO->getLHS()); 648 if (const VarDecl *VD = Var.getDecl()) 649 vals[VD] = Initialized; 650 } 651} 652 653void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 654 for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); 655 DI != DE; ++DI) { 656 VarDecl *VD = dyn_cast<VarDecl>(*DI); 657 if (VD && isTrackedVar(VD)) { 658 if (getSelfInitExpr(VD)) { 659 // If the initializer consists solely of a reference to itself, we 660 // explicitly mark the variable as uninitialized. This allows code 661 // like the following: 662 // 663 // int x = x; 664 // 665 // to deliberately leave a variable uninitialized. Different analysis 666 // clients can detect this pattern and adjust their reporting 667 // appropriately, but we need to continue to analyze subsequent uses 668 // of the variable. 669 vals[VD] = Uninitialized; 670 } else if (VD->getInit()) { 671 // Treat the new variable as initialized. 672 vals[VD] = Initialized; 673 } else { 674 // No initializer: the variable is now uninitialized. This matters 675 // for cases like: 676 // while (...) { 677 // int n; 678 // use(n); 679 // n = 0; 680 // } 681 // FIXME: Mark the variable as uninitialized whenever its scope is 682 // left, since its scope could be re-entered by a jump over the 683 // declaration. 684 vals[VD] = Uninitialized; 685 } 686 } 687 } 688} 689 690void TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { 691 // If the Objective-C message expression is an implicit no-return that 692 // is not modeled in the CFG, set the tracked dataflow values to Unknown. 693 if (objCNoRet.isImplicitNoReturn(ME)) { 694 vals.setAllScratchValues(Unknown); 695 } 696} 697 698//------------------------------------------------------------------------====// 699// High-level "driver" logic for uninitialized values analysis. 700//====------------------------------------------------------------------------// 701 702static bool runOnBlock(const CFGBlock *block, const CFG &cfg, 703 AnalysisDeclContext &ac, CFGBlockValues &vals, 704 const ClassifyRefs &classification, 705 llvm::BitVector &wasAnalyzed, 706 UninitVariablesHandler *handler = 0) { 707 wasAnalyzed[block->getBlockID()] = true; 708 vals.resetScratch(); 709 // Merge in values of predecessor blocks. 710 bool isFirst = true; 711 for (CFGBlock::const_pred_iterator I = block->pred_begin(), 712 E = block->pred_end(); I != E; ++I) { 713 const CFGBlock *pred = *I; 714 if (wasAnalyzed[pred->getBlockID()]) { 715 vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); 716 isFirst = false; 717 } 718 } 719 // Apply the transfer function. 720 TransferFunctions tf(vals, cfg, block, ac, classification, handler); 721 for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 722 I != E; ++I) { 723 if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { 724 tf.Visit(const_cast<Stmt*>(cs->getStmt())); 725 } 726 } 727 return vals.updateValueVectorWithScratch(block); 728} 729 730void clang::runUninitializedVariablesAnalysis( 731 const DeclContext &dc, 732 const CFG &cfg, 733 AnalysisDeclContext &ac, 734 UninitVariablesHandler &handler, 735 UninitVariablesAnalysisStats &stats) { 736 CFGBlockValues vals(cfg); 737 vals.computeSetOfDeclarations(dc); 738 if (vals.hasNoDeclarations()) 739 return; 740 741 stats.NumVariablesAnalyzed = vals.getNumEntries(); 742 743 // Precompute which expressions are uses and which are initializations. 744 ClassifyRefs classification(ac); 745 cfg.VisitBlockStmts(classification); 746 747 // Mark all variables uninitialized at the entry. 748 const CFGBlock &entry = cfg.getEntry(); 749 ValueVector &vec = vals.getValueVector(&entry); 750 const unsigned n = vals.getNumEntries(); 751 for (unsigned j = 0; j < n ; ++j) { 752 vec[j] = Uninitialized; 753 } 754 755 // Proceed with the workist. 756 DataflowWorklist worklist(cfg); 757 llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 758 worklist.enqueueSuccessors(&cfg.getEntry()); 759 llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 760 wasAnalyzed[cfg.getEntry().getBlockID()] = true; 761 762 while (const CFGBlock *block = worklist.dequeue()) { 763 // Did the block change? 764 bool changed = runOnBlock(block, cfg, ac, vals, 765 classification, wasAnalyzed); 766 ++stats.NumBlockVisits; 767 if (changed || !previouslyVisited[block->getBlockID()]) 768 worklist.enqueueSuccessors(block); 769 previouslyVisited[block->getBlockID()] = true; 770 } 771 772 // Run through the blocks one more time, and report uninitialized variabes. 773 for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 774 const CFGBlock *block = *BI; 775 if (wasAnalyzed[block->getBlockID()]) { 776 runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, &handler); 777 ++stats.NumBlockVisits; 778 } 779 } 780} 781 782UninitVariablesHandler::~UninitVariablesHandler() {} 783