UninitializedValues.cpp revision 280031
1193326Sed//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// 2193326Sed// 3193326Sed// The LLVM Compiler Infrastructure 4193326Sed// 5193326Sed// This file is distributed under the University of Illinois Open Source 6193326Sed// License. See LICENSE.TXT for details. 7193326Sed// 8193326Sed//===----------------------------------------------------------------------===// 9193326Sed// 10221345Sdim// This file implements uninitialized values analysis for source-level CFGs. 11193326Sed// 12193326Sed//===----------------------------------------------------------------------===// 13193326Sed 14239462Sdim#include "clang/AST/ASTContext.h" 15249423Sdim#include "clang/AST/Attr.h" 16221345Sdim#include "clang/AST/Decl.h" 17261991Sdim#include "clang/AST/StmtVisitor.h" 18249423Sdim#include "clang/Analysis/Analyses/PostOrderCFGView.h" 19249423Sdim#include "clang/Analysis/Analyses/UninitializedValues.h" 20249423Sdim#include "clang/Analysis/AnalysisContext.h" 21221345Sdim#include "clang/Analysis/CFG.h" 22249423Sdim#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" 23249423Sdim#include "llvm/ADT/DenseMap.h" 24249423Sdim#include "llvm/ADT/Optional.h" 25249423Sdim#include "llvm/ADT/PackedVector.h" 26249423Sdim#include "llvm/ADT/SmallBitVector.h" 27249423Sdim#include "llvm/ADT/SmallVector.h" 28234353Sdim#include "llvm/Support/SaveAndRestore.h" 29249423Sdim#include <utility> 30193326Sed 31193326Sedusing namespace clang; 32193326Sed 33239462Sdim#define DEBUG_LOGGING 0 34239462Sdim 35221345Sdimstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 36221345Sdim if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 37276479Sdim !vd->isExceptionVariable() && !vd->isInitCapture() && 38221345Sdim vd->getDeclContext() == dc) { 39221345Sdim QualType ty = vd->getType(); 40221345Sdim return ty->isScalarType() || ty->isVectorType(); 41221345Sdim } 42221345Sdim return false; 43221345Sdim} 44193326Sed 45221345Sdim//------------------------------------------------------------------------====// 46221345Sdim// DeclToIndex: a mapping from Decls we track to value indices. 47221345Sdim//====------------------------------------------------------------------------// 48221345Sdim 49193326Sednamespace { 50221345Sdimclass DeclToIndex { 51221345Sdim llvm::DenseMap<const VarDecl *, unsigned> map; 52221345Sdimpublic: 53221345Sdim DeclToIndex() {} 54221345Sdim 55221345Sdim /// Compute the actual mapping from declarations to bits. 56221345Sdim void computeMap(const DeclContext &dc); 57221345Sdim 58221345Sdim /// Return the number of declarations in the map. 59221345Sdim unsigned size() const { return map.size(); } 60221345Sdim 61221345Sdim /// Returns the bit vector index for a given declaration. 62249423Sdim Optional<unsigned> getValueIndex(const VarDecl *d) const; 63221345Sdim}; 64221345Sdim} 65193326Sed 66221345Sdimvoid DeclToIndex::computeMap(const DeclContext &dc) { 67221345Sdim unsigned count = 0; 68221345Sdim DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 69221345Sdim E(dc.decls_end()); 70221345Sdim for ( ; I != E; ++I) { 71221345Sdim const VarDecl *vd = *I; 72221345Sdim if (isTrackedVar(vd, &dc)) 73221345Sdim map[vd] = count++; 74221345Sdim } 75221345Sdim} 76193326Sed 77249423SdimOptional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 78221345Sdim llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 79221345Sdim if (I == map.end()) 80249423Sdim return None; 81221345Sdim return I->second; 82221345Sdim} 83198092Srdivacky 84221345Sdim//------------------------------------------------------------------------====// 85221345Sdim// CFGBlockValues: dataflow values for CFG blocks. 86221345Sdim//====------------------------------------------------------------------------// 87198092Srdivacky 88221345Sdim// These values are defined in such a way that a merge can be done using 89221345Sdim// a bitwise OR. 90221345Sdimenum Value { Unknown = 0x0, /* 00 */ 91221345Sdim Initialized = 0x1, /* 01 */ 92221345Sdim Uninitialized = 0x2, /* 10 */ 93221345Sdim MayUninitialized = 0x3 /* 11 */ }; 94193326Sed 95221345Sdimstatic bool isUninitialized(const Value v) { 96221345Sdim return v >= Uninitialized; 97193326Sed} 98221345Sdimstatic bool isAlwaysUninit(const Value v) { 99221345Sdim return v == Uninitialized; 100221345Sdim} 101193326Sed 102193326Sednamespace { 103198092Srdivacky 104243830Sdimtypedef llvm::PackedVector<Value, 2, llvm::SmallBitVector> ValueVector; 105221345Sdim 106221345Sdimclass CFGBlockValues { 107221345Sdim const CFG &cfg; 108243830Sdim SmallVector<ValueVector, 8> vals; 109221345Sdim ValueVector scratch; 110221345Sdim DeclToIndex declToIndex; 111193326Sedpublic: 112221345Sdim CFGBlockValues(const CFG &cfg); 113239462Sdim 114221345Sdim unsigned getNumEntries() const { return declToIndex.size(); } 115221345Sdim 116221345Sdim void computeSetOfDeclarations(const DeclContext &dc); 117239462Sdim ValueVector &getValueVector(const CFGBlock *block) { 118243830Sdim return vals[block->getBlockID()]; 119239462Sdim } 120198092Srdivacky 121239462Sdim void setAllScratchValues(Value V); 122221345Sdim void mergeIntoScratch(ValueVector const &source, bool isFirst); 123221345Sdim bool updateValueVectorWithScratch(const CFGBlock *block); 124221345Sdim 125221345Sdim bool hasNoDeclarations() const { 126221345Sdim return declToIndex.size() == 0; 127193326Sed } 128226633Sdim 129221345Sdim void resetScratch(); 130221345Sdim 131221345Sdim ValueVector::reference operator[](const VarDecl *vd); 132239462Sdim 133239462Sdim Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, 134239462Sdim const VarDecl *vd) { 135249423Sdim const Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 136239462Sdim assert(idx.hasValue()); 137239462Sdim return getValueVector(block)[idx.getValue()]; 138239462Sdim } 139221345Sdim}; 140221345Sdim} // end anonymous namespace 141198092Srdivacky 142239462SdimCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} 143198092Srdivacky 144221345Sdimvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 145221345Sdim declToIndex.computeMap(dc); 146239462Sdim unsigned decls = declToIndex.size(); 147239462Sdim scratch.resize(decls); 148239462Sdim unsigned n = cfg.getNumBlockIDs(); 149239462Sdim if (!n) 150239462Sdim return; 151239462Sdim vals.resize(n); 152239462Sdim for (unsigned i = 0; i < n; ++i) 153243830Sdim vals[i].resize(decls); 154221345Sdim} 155198092Srdivacky 156239462Sdim#if DEBUG_LOGGING 157221345Sdimstatic void printVector(const CFGBlock *block, ValueVector &bv, 158221345Sdim unsigned num) { 159221345Sdim llvm::errs() << block->getBlockID() << " :"; 160221345Sdim for (unsigned i = 0; i < bv.size(); ++i) { 161221345Sdim llvm::errs() << ' ' << bv[i]; 162221345Sdim } 163221345Sdim llvm::errs() << " : " << num << '\n'; 164221345Sdim} 165239462Sdim#endif 166226633Sdim 167239462Sdimvoid CFGBlockValues::setAllScratchValues(Value V) { 168239462Sdim for (unsigned I = 0, E = scratch.size(); I != E; ++I) 169239462Sdim scratch[I] = V; 170226633Sdim} 171198092Srdivacky 172226633Sdimvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 173226633Sdim bool isFirst) { 174226633Sdim if (isFirst) 175226633Sdim scratch = source; 176226633Sdim else 177226633Sdim scratch |= source; 178226633Sdim} 179226633Sdim 180221345Sdimbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 181239462Sdim ValueVector &dst = getValueVector(block); 182221345Sdim bool changed = (dst != scratch); 183221345Sdim if (changed) 184221345Sdim dst = scratch; 185239462Sdim#if DEBUG_LOGGING 186221345Sdim printVector(block, scratch, 0); 187221345Sdim#endif 188221345Sdim return changed; 189221345Sdim} 190193326Sed 191221345Sdimvoid CFGBlockValues::resetScratch() { 192221345Sdim scratch.reset(); 193221345Sdim} 194193326Sed 195221345SdimValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 196249423Sdim const Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 197221345Sdim assert(idx.hasValue()); 198221345Sdim return scratch[idx.getValue()]; 199221345Sdim} 200193326Sed 201221345Sdim//------------------------------------------------------------------------====// 202221345Sdim// Worklist: worklist for dataflow analysis. 203221345Sdim//====------------------------------------------------------------------------// 204221345Sdim 205221345Sdimnamespace { 206221345Sdimclass DataflowWorklist { 207249423Sdim PostOrderCFGView::iterator PO_I, PO_E; 208226633Sdim SmallVector<const CFGBlock *, 20> worklist; 209221345Sdim llvm::BitVector enqueuedBlocks; 210221345Sdimpublic: 211249423Sdim DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) 212249423Sdim : PO_I(view.begin()), PO_E(view.end()), 213249423Sdim enqueuedBlocks(cfg.getNumBlockIDs(), true) { 214249423Sdim // Treat the first block as already analyzed. 215249423Sdim if (PO_I != PO_E) { 216249423Sdim assert(*PO_I == &cfg.getEntry()); 217249423Sdim enqueuedBlocks[(*PO_I)->getBlockID()] = false; 218249423Sdim ++PO_I; 219249423Sdim } 220249423Sdim } 221221345Sdim 222221345Sdim void enqueueSuccessors(const CFGBlock *block); 223221345Sdim const CFGBlock *dequeue(); 224221345Sdim}; 225193326Sed} 226193326Sed 227221345Sdimvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 228221345Sdim for (CFGBlock::const_succ_iterator I = block->succ_begin(), 229221345Sdim E = block->succ_end(); I != E; ++I) { 230224145Sdim const CFGBlock *Successor = *I; 231224145Sdim if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 232224145Sdim continue; 233224145Sdim worklist.push_back(Successor); 234224145Sdim enqueuedBlocks[Successor->getBlockID()] = true; 235193326Sed } 236193326Sed} 237198092Srdivacky 238221345Sdimconst CFGBlock *DataflowWorklist::dequeue() { 239276479Sdim const CFGBlock *B = nullptr; 240249423Sdim 241249423Sdim // First dequeue from the worklist. This can represent 242249423Sdim // updates along backedges that we want propagated as quickly as possible. 243261991Sdim if (!worklist.empty()) 244261991Sdim B = worklist.pop_back_val(); 245261991Sdim 246249423Sdim // Next dequeue from the initial reverse post order. This is the 247249423Sdim // theoretical ideal in the presence of no back edges. 248249423Sdim else if (PO_I != PO_E) { 249249423Sdim B = *PO_I; 250249423Sdim ++PO_I; 251249423Sdim } 252249423Sdim else { 253276479Sdim return nullptr; 254249423Sdim } 255249423Sdim 256249423Sdim assert(enqueuedBlocks[B->getBlockID()] == true); 257249423Sdim enqueuedBlocks[B->getBlockID()] = false; 258249423Sdim return B; 259193326Sed} 260193326Sed 261221345Sdim//------------------------------------------------------------------------====// 262239462Sdim// Classification of DeclRefExprs as use or initialization. 263221345Sdim//====------------------------------------------------------------------------// 264198092Srdivacky 265221345Sdimnamespace { 266221345Sdimclass FindVarResult { 267221345Sdim const VarDecl *vd; 268221345Sdim const DeclRefExpr *dr; 269221345Sdimpublic: 270239462Sdim FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} 271239462Sdim 272221345Sdim const DeclRefExpr *getDeclRefExpr() const { return dr; } 273221345Sdim const VarDecl *getDecl() const { return vd; } 274221345Sdim}; 275239462Sdim 276239462Sdimstatic const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 277239462Sdim while (Ex) { 278239462Sdim Ex = Ex->IgnoreParenNoopCasts(C); 279239462Sdim if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 280239462Sdim if (CE->getCastKind() == CK_LValueBitCast) { 281239462Sdim Ex = CE->getSubExpr(); 282239462Sdim continue; 283239462Sdim } 284239462Sdim } 285239462Sdim break; 286239462Sdim } 287239462Sdim return Ex; 288239462Sdim} 289239462Sdim 290239462Sdim/// If E is an expression comprising a reference to a single variable, find that 291239462Sdim/// variable. 292239462Sdimstatic FindVarResult findVar(const Expr *E, const DeclContext *DC) { 293239462Sdim if (const DeclRefExpr *DRE = 294239462Sdim dyn_cast<DeclRefExpr>(stripCasts(DC->getParentASTContext(), E))) 295239462Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) 296239462Sdim if (isTrackedVar(VD, DC)) 297239462Sdim return FindVarResult(VD, DRE); 298276479Sdim return FindVarResult(nullptr, nullptr); 299239462Sdim} 300239462Sdim 301239462Sdim/// \brief Classify each DeclRefExpr as an initialization or a use. Any 302239462Sdim/// DeclRefExpr which isn't explicitly classified will be assumed to have 303239462Sdim/// escaped the analysis and will be treated as an initialization. 304239462Sdimclass ClassifyRefs : public StmtVisitor<ClassifyRefs> { 305239462Sdimpublic: 306239462Sdim enum Class { 307239462Sdim Init, 308239462Sdim Use, 309239462Sdim SelfInit, 310239462Sdim Ignore 311239462Sdim }; 312239462Sdim 313239462Sdimprivate: 314239462Sdim const DeclContext *DC; 315239462Sdim llvm::DenseMap<const DeclRefExpr*, Class> Classification; 316239462Sdim 317239462Sdim bool isTrackedVar(const VarDecl *VD) const { 318239462Sdim return ::isTrackedVar(VD, DC); 319239462Sdim } 320239462Sdim 321239462Sdim void classify(const Expr *E, Class C); 322239462Sdim 323239462Sdimpublic: 324239462Sdim ClassifyRefs(AnalysisDeclContext &AC) : DC(cast<DeclContext>(AC.getDecl())) {} 325239462Sdim 326239462Sdim void VisitDeclStmt(DeclStmt *DS); 327239462Sdim void VisitUnaryOperator(UnaryOperator *UO); 328239462Sdim void VisitBinaryOperator(BinaryOperator *BO); 329239462Sdim void VisitCallExpr(CallExpr *CE); 330239462Sdim void VisitCastExpr(CastExpr *CE); 331239462Sdim 332239462Sdim void operator()(Stmt *S) { Visit(S); } 333239462Sdim 334239462Sdim Class get(const DeclRefExpr *DRE) const { 335239462Sdim llvm::DenseMap<const DeclRefExpr*, Class>::const_iterator I 336239462Sdim = Classification.find(DRE); 337239462Sdim if (I != Classification.end()) 338239462Sdim return I->second; 339239462Sdim 340239462Sdim const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); 341239462Sdim if (!VD || !isTrackedVar(VD)) 342239462Sdim return Ignore; 343239462Sdim 344239462Sdim return Init; 345239462Sdim } 346239462Sdim}; 347239462Sdim} 348239462Sdim 349239462Sdimstatic const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { 350239462Sdim if (Expr *Init = VD->getInit()) { 351239462Sdim const DeclRefExpr *DRE 352239462Sdim = dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init)); 353239462Sdim if (DRE && DRE->getDecl() == VD) 354239462Sdim return DRE; 355239462Sdim } 356276479Sdim return nullptr; 357239462Sdim} 358239462Sdim 359239462Sdimvoid ClassifyRefs::classify(const Expr *E, Class C) { 360249423Sdim // The result of a ?: could also be an lvalue. 361249423Sdim E = E->IgnoreParens(); 362249423Sdim if (const ConditionalOperator *CO = dyn_cast<ConditionalOperator>(E)) { 363280031Sdim classify(CO->getTrueExpr(), C); 364249423Sdim classify(CO->getFalseExpr(), C); 365249423Sdim return; 366249423Sdim } 367249423Sdim 368280031Sdim if (const BinaryConditionalOperator *BCO = 369280031Sdim dyn_cast<BinaryConditionalOperator>(E)) { 370280031Sdim classify(BCO->getFalseExpr(), C); 371280031Sdim return; 372280031Sdim } 373280031Sdim 374280031Sdim if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) { 375280031Sdim classify(OVE->getSourceExpr(), C); 376280031Sdim return; 377280031Sdim } 378280031Sdim 379280031Sdim if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(E)) { 380280031Sdim if (BO->getOpcode() == BO_Comma) 381280031Sdim classify(BO->getRHS(), C); 382280031Sdim return; 383280031Sdim } 384280031Sdim 385239462Sdim FindVarResult Var = findVar(E, DC); 386239462Sdim if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) 387239462Sdim Classification[DRE] = std::max(Classification[DRE], C); 388239462Sdim} 389239462Sdim 390239462Sdimvoid ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { 391276479Sdim for (auto *DI : DS->decls()) { 392276479Sdim VarDecl *VD = dyn_cast<VarDecl>(DI); 393239462Sdim if (VD && isTrackedVar(VD)) 394239462Sdim if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) 395239462Sdim Classification[DRE] = SelfInit; 396239462Sdim } 397239462Sdim} 398239462Sdim 399239462Sdimvoid ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { 400239462Sdim // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this 401239462Sdim // is not a compound-assignment, we will treat it as initializing the variable 402239462Sdim // when TransferFunctions visits it. A compound-assignment does not affect 403239462Sdim // whether a variable is uninitialized, and there's no point counting it as a 404239462Sdim // use. 405239462Sdim if (BO->isCompoundAssignmentOp()) 406239462Sdim classify(BO->getLHS(), Use); 407239462Sdim else if (BO->getOpcode() == BO_Assign) 408239462Sdim classify(BO->getLHS(), Ignore); 409239462Sdim} 410239462Sdim 411239462Sdimvoid ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { 412239462Sdim // Increment and decrement are uses despite there being no lvalue-to-rvalue 413239462Sdim // conversion. 414239462Sdim if (UO->isIncrementDecrementOp()) 415239462Sdim classify(UO->getSubExpr(), Use); 416239462Sdim} 417239462Sdim 418239462Sdimvoid ClassifyRefs::VisitCallExpr(CallExpr *CE) { 419280031Sdim // Classify arguments to std::move as used. 420280031Sdim if (CE->getNumArgs() == 1) { 421280031Sdim if (FunctionDecl *FD = CE->getDirectCallee()) { 422280031Sdim if (FD->isInStdNamespace() && FD->getIdentifier() && 423280031Sdim FD->getIdentifier()->isStr("move")) { 424280031Sdim classify(CE->getArg(0), Use); 425280031Sdim return; 426280031Sdim } 427280031Sdim } 428280031Sdim } 429280031Sdim 430239462Sdim // If a value is passed by const reference to a function, we should not assume 431239462Sdim // that it is initialized by the call, and we conservatively do not assume 432239462Sdim // that it is used. 433239462Sdim for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); 434239462Sdim I != E; ++I) 435239462Sdim if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) 436239462Sdim classify(*I, Ignore); 437239462Sdim} 438239462Sdim 439239462Sdimvoid ClassifyRefs::VisitCastExpr(CastExpr *CE) { 440239462Sdim if (CE->getCastKind() == CK_LValueToRValue) 441239462Sdim classify(CE->getSubExpr(), Use); 442239462Sdim else if (CStyleCastExpr *CSE = dyn_cast<CStyleCastExpr>(CE)) { 443239462Sdim if (CSE->getType()->isVoidType()) { 444239462Sdim // Squelch any detected load of an uninitialized value if 445239462Sdim // we cast it to void. 446239462Sdim // e.g. (void) x; 447239462Sdim classify(CSE->getSubExpr(), Ignore); 448239462Sdim } 449239462Sdim } 450239462Sdim} 451239462Sdim 452239462Sdim//------------------------------------------------------------------------====// 453239462Sdim// Transfer function for uninitialized values analysis. 454239462Sdim//====------------------------------------------------------------------------// 455239462Sdim 456239462Sdimnamespace { 457226633Sdimclass TransferFunctions : public StmtVisitor<TransferFunctions> { 458221345Sdim CFGBlockValues &vals; 459221345Sdim const CFG &cfg; 460239462Sdim const CFGBlock *block; 461234353Sdim AnalysisDeclContext ∾ 462239462Sdim const ClassifyRefs &classification; 463243830Sdim ObjCNoReturn objCNoRet; 464249423Sdim UninitVariablesHandler &handler; 465239462Sdim 466221345Sdimpublic: 467221345Sdim TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 468239462Sdim const CFGBlock *block, AnalysisDeclContext &ac, 469239462Sdim const ClassifyRefs &classification, 470249423Sdim UninitVariablesHandler &handler) 471239462Sdim : vals(vals), cfg(cfg), block(block), ac(ac), 472243830Sdim classification(classification), objCNoRet(ac.getASTContext()), 473243830Sdim handler(handler) {} 474221345Sdim 475239462Sdim void reportUse(const Expr *ex, const VarDecl *vd); 476239462Sdim 477243830Sdim void VisitBinaryOperator(BinaryOperator *bo); 478221345Sdim void VisitBlockExpr(BlockExpr *be); 479239462Sdim void VisitCallExpr(CallExpr *ce); 480243830Sdim void VisitDeclRefExpr(DeclRefExpr *dr); 481221345Sdim void VisitDeclStmt(DeclStmt *ds); 482243830Sdim void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); 483243830Sdim void VisitObjCMessageExpr(ObjCMessageExpr *ME); 484239462Sdim 485221345Sdim bool isTrackedVar(const VarDecl *vd) { 486221345Sdim return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 487193326Sed } 488193326Sed 489239462Sdim FindVarResult findVar(const Expr *ex) { 490239462Sdim return ::findVar(ex, cast<DeclContext>(ac.getDecl())); 491239462Sdim } 492239462Sdim 493239462Sdim UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { 494239462Sdim UninitUse Use(ex, isAlwaysUninit(v)); 495239462Sdim 496239462Sdim assert(isUninitialized(v)); 497239462Sdim if (Use.getKind() == UninitUse::Always) 498239462Sdim return Use; 499239462Sdim 500239462Sdim // If an edge which leads unconditionally to this use did not initialize 501239462Sdim // the variable, we can say something stronger than 'may be uninitialized': 502239462Sdim // we can say 'either it's used uninitialized or you have dead code'. 503239462Sdim // 504239462Sdim // We track the number of successors of a node which have been visited, and 505239462Sdim // visit a node once we have visited all of its successors. Only edges where 506239462Sdim // the variable might still be uninitialized are followed. Since a variable 507239462Sdim // can't transfer from being initialized to being uninitialized, this will 508239462Sdim // trace out the subgraph which inevitably leads to the use and does not 509239462Sdim // initialize the variable. We do not want to skip past loops, since their 510239462Sdim // non-termination might be correlated with the initialization condition. 511239462Sdim // 512239462Sdim // For example: 513239462Sdim // 514239462Sdim // void f(bool a, bool b) { 515239462Sdim // block1: int n; 516239462Sdim // if (a) { 517239462Sdim // block2: if (b) 518239462Sdim // block3: n = 1; 519239462Sdim // block4: } else if (b) { 520239462Sdim // block5: while (!a) { 521239462Sdim // block6: do_work(&a); 522239462Sdim // n = 2; 523239462Sdim // } 524239462Sdim // } 525239462Sdim // block7: if (a) 526239462Sdim // block8: g(); 527239462Sdim // block9: return n; 528239462Sdim // } 529239462Sdim // 530239462Sdim // Starting from the maybe-uninitialized use in block 9: 531239462Sdim // * Block 7 is not visited because we have only visited one of its two 532239462Sdim // successors. 533239462Sdim // * Block 8 is visited because we've visited its only successor. 534239462Sdim // From block 8: 535239462Sdim // * Block 7 is visited because we've now visited both of its successors. 536239462Sdim // From block 7: 537239462Sdim // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all 538239462Sdim // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). 539239462Sdim // * Block 3 is not visited because it initializes 'n'. 540239462Sdim // Now the algorithm terminates, having visited blocks 7 and 8, and having 541239462Sdim // found the frontier is blocks 2, 4, and 5. 542239462Sdim // 543239462Sdim // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 544239462Sdim // and 4), so we report that any time either of those edges is taken (in 545239462Sdim // each case when 'b == false'), 'n' is used uninitialized. 546249423Sdim SmallVector<const CFGBlock*, 32> Queue; 547249423Sdim SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0); 548239462Sdim Queue.push_back(block); 549239462Sdim // Specify that we've already visited all successors of the starting block. 550239462Sdim // This has the dual purpose of ensuring we never add it to the queue, and 551239462Sdim // of marking it as not being a candidate element of the frontier. 552239462Sdim SuccsVisited[block->getBlockID()] = block->succ_size(); 553239462Sdim while (!Queue.empty()) { 554261991Sdim const CFGBlock *B = Queue.pop_back_val(); 555261991Sdim 556261991Sdim // If the use is always reached from the entry block, make a note of that. 557261991Sdim if (B == &cfg.getEntry()) 558261991Sdim Use.setUninitAfterCall(); 559261991Sdim 560239462Sdim for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); 561239462Sdim I != E; ++I) { 562239462Sdim const CFGBlock *Pred = *I; 563276479Sdim if (!Pred) 564276479Sdim continue; 565276479Sdim 566261991Sdim Value AtPredExit = vals.getValue(Pred, B, vd); 567261991Sdim if (AtPredExit == Initialized) 568239462Sdim // This block initializes the variable. 569239462Sdim continue; 570261991Sdim if (AtPredExit == MayUninitialized && 571276479Sdim vals.getValue(B, nullptr, vd) == Uninitialized) { 572261991Sdim // This block declares the variable (uninitialized), and is reachable 573261991Sdim // from a block that initializes the variable. We can't guarantee to 574261991Sdim // give an earlier location for the diagnostic (and it appears that 575261991Sdim // this code is intended to be reachable) so give a diagnostic here 576261991Sdim // and go no further down this path. 577261991Sdim Use.setUninitAfterDecl(); 578261991Sdim continue; 579261991Sdim } 580239462Sdim 581239462Sdim unsigned &SV = SuccsVisited[Pred->getBlockID()]; 582239462Sdim if (!SV) { 583239462Sdim // When visiting the first successor of a block, mark all NULL 584239462Sdim // successors as having been visited. 585239462Sdim for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), 586239462Sdim SE = Pred->succ_end(); 587239462Sdim SI != SE; ++SI) 588239462Sdim if (!*SI) 589239462Sdim ++SV; 590239462Sdim } 591239462Sdim 592239462Sdim if (++SV == Pred->succ_size()) 593239462Sdim // All paths from this block lead to the use and don't initialize the 594239462Sdim // variable. 595239462Sdim Queue.push_back(Pred); 596226633Sdim } 597226633Sdim } 598239462Sdim 599239462Sdim // Scan the frontier, looking for blocks where the variable was 600239462Sdim // uninitialized. 601239462Sdim for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 602239462Sdim const CFGBlock *Block = *BI; 603239462Sdim unsigned BlockID = Block->getBlockID(); 604239462Sdim const Stmt *Term = Block->getTerminator(); 605239462Sdim if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && 606239462Sdim Term) { 607239462Sdim // This block inevitably leads to the use. If we have an edge from here 608239462Sdim // to a post-dominator block, and the variable is uninitialized on that 609239462Sdim // edge, we have found a bug. 610239462Sdim for (CFGBlock::const_succ_iterator I = Block->succ_begin(), 611239462Sdim E = Block->succ_end(); I != E; ++I) { 612239462Sdim const CFGBlock *Succ = *I; 613239462Sdim if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && 614239462Sdim vals.getValue(Block, Succ, vd) == Uninitialized) { 615239462Sdim // Switch cases are a special case: report the label to the caller 616239462Sdim // as the 'terminator', not the switch statement itself. Suppress 617239462Sdim // situations where no label matched: we can't be sure that's 618239462Sdim // possible. 619239462Sdim if (isa<SwitchStmt>(Term)) { 620239462Sdim const Stmt *Label = Succ->getLabel(); 621239462Sdim if (!Label || !isa<SwitchCase>(Label)) 622239462Sdim // Might not be possible. 623239462Sdim continue; 624239462Sdim UninitUse::Branch Branch; 625239462Sdim Branch.Terminator = Label; 626239462Sdim Branch.Output = 0; // Ignored. 627239462Sdim Use.addUninitBranch(Branch); 628239462Sdim } else { 629239462Sdim UninitUse::Branch Branch; 630239462Sdim Branch.Terminator = Term; 631239462Sdim Branch.Output = I - Block->succ_begin(); 632239462Sdim Use.addUninitBranch(Branch); 633239462Sdim } 634239462Sdim } 635239462Sdim } 636239462Sdim } 637239462Sdim } 638239462Sdim 639239462Sdim return Use; 640226633Sdim } 641239462Sdim}; 642226633Sdim} 643226633Sdim 644239462Sdimvoid TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { 645239462Sdim Value v = vals[vd]; 646239462Sdim if (isUninitialized(v)) 647249423Sdim handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); 648193326Sed} 649198092Srdivacky 650239462Sdimvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { 651193326Sed // This represents an initialization of the 'element' value. 652239462Sdim if (DeclStmt *DS = dyn_cast<DeclStmt>(FS->getElement())) { 653239462Sdim const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 654239462Sdim if (isTrackedVar(VD)) 655239462Sdim vals[VD] = Initialized; 656193326Sed } 657221345Sdim} 658198092Srdivacky 659221345Sdimvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 660221345Sdim const BlockDecl *bd = be->getBlockDecl(); 661276479Sdim for (const auto &I : bd->captures()) { 662276479Sdim const VarDecl *vd = I.getVariable(); 663221345Sdim if (!isTrackedVar(vd)) 664221345Sdim continue; 665276479Sdim if (I.isByRef()) { 666221345Sdim vals[vd] = Initialized; 667221345Sdim continue; 668221345Sdim } 669239462Sdim reportUse(be, vd); 670221345Sdim } 671193326Sed} 672198092Srdivacky 673239462Sdimvoid TransferFunctions::VisitCallExpr(CallExpr *ce) { 674243830Sdim if (Decl *Callee = ce->getCalleeDecl()) { 675243830Sdim if (Callee->hasAttr<ReturnsTwiceAttr>()) { 676243830Sdim // After a call to a function like setjmp or vfork, any variable which is 677243830Sdim // initialized anywhere within this function may now be initialized. For 678243830Sdim // now, just assume such a call initializes all variables. FIXME: Only 679243830Sdim // mark variables as initialized if they have an initializer which is 680243830Sdim // reachable from here. 681243830Sdim vals.setAllScratchValues(Initialized); 682243830Sdim } 683243830Sdim else if (Callee->hasAttr<AnalyzerNoReturnAttr>()) { 684243830Sdim // Functions labeled like "analyzer_noreturn" are often used to denote 685243830Sdim // "panic" functions that in special debug situations can still return, 686243830Sdim // but for the most part should not be treated as returning. This is a 687243830Sdim // useful annotation borrowed from the static analyzer that is useful for 688243830Sdim // suppressing branch-specific false positives when we call one of these 689243830Sdim // functions but keep pretending the path continues (when in reality the 690243830Sdim // user doesn't care). 691243830Sdim vals.setAllScratchValues(Unknown); 692243830Sdim } 693243830Sdim } 694226633Sdim} 695226633Sdim 696239462Sdimvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 697239462Sdim switch (classification.get(dr)) { 698239462Sdim case ClassifyRefs::Ignore: 699239462Sdim break; 700239462Sdim case ClassifyRefs::Use: 701239462Sdim reportUse(dr, cast<VarDecl>(dr->getDecl())); 702239462Sdim break; 703239462Sdim case ClassifyRefs::Init: 704239462Sdim vals[cast<VarDecl>(dr->getDecl())] = Initialized; 705239462Sdim break; 706239462Sdim case ClassifyRefs::SelfInit: 707249423Sdim handler.handleSelfInit(cast<VarDecl>(dr->getDecl())); 708239462Sdim break; 709221345Sdim } 710221345Sdim} 711193326Sed 712239462Sdimvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { 713239462Sdim if (BO->getOpcode() == BO_Assign) { 714239462Sdim FindVarResult Var = findVar(BO->getLHS()); 715239462Sdim if (const VarDecl *VD = Var.getDecl()) 716239462Sdim vals[VD] = Initialized; 717221345Sdim } 718221345Sdim} 719198092Srdivacky 720239462Sdimvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 721276479Sdim for (auto *DI : DS->decls()) { 722276479Sdim VarDecl *VD = dyn_cast<VarDecl>(DI); 723239462Sdim if (VD && isTrackedVar(VD)) { 724239462Sdim if (getSelfInitExpr(VD)) { 725239462Sdim // If the initializer consists solely of a reference to itself, we 726239462Sdim // explicitly mark the variable as uninitialized. This allows code 727239462Sdim // like the following: 728239462Sdim // 729239462Sdim // int x = x; 730239462Sdim // 731239462Sdim // to deliberately leave a variable uninitialized. Different analysis 732239462Sdim // clients can detect this pattern and adjust their reporting 733239462Sdim // appropriately, but we need to continue to analyze subsequent uses 734239462Sdim // of the variable. 735239462Sdim vals[VD] = Uninitialized; 736239462Sdim } else if (VD->getInit()) { 737239462Sdim // Treat the new variable as initialized. 738239462Sdim vals[VD] = Initialized; 739239462Sdim } else { 740239462Sdim // No initializer: the variable is now uninitialized. This matters 741239462Sdim // for cases like: 742239462Sdim // while (...) { 743239462Sdim // int n; 744239462Sdim // use(n); 745239462Sdim // n = 0; 746239462Sdim // } 747239462Sdim // FIXME: Mark the variable as uninitialized whenever its scope is 748239462Sdim // left, since its scope could be re-entered by a jump over the 749239462Sdim // declaration. 750239462Sdim vals[VD] = Uninitialized; 751221345Sdim } 752221345Sdim } 753221345Sdim } 754193326Sed} 755198092Srdivacky 756243830Sdimvoid TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { 757243830Sdim // If the Objective-C message expression is an implicit no-return that 758243830Sdim // is not modeled in the CFG, set the tracked dataflow values to Unknown. 759243830Sdim if (objCNoRet.isImplicitNoReturn(ME)) { 760243830Sdim vals.setAllScratchValues(Unknown); 761243830Sdim } 762243830Sdim} 763243830Sdim 764221345Sdim//------------------------------------------------------------------------====// 765221345Sdim// High-level "driver" logic for uninitialized values analysis. 766221345Sdim//====------------------------------------------------------------------------// 767193326Sed 768221345Sdimstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 769234353Sdim AnalysisDeclContext &ac, CFGBlockValues &vals, 770239462Sdim const ClassifyRefs &classification, 771221345Sdim llvm::BitVector &wasAnalyzed, 772249423Sdim UninitVariablesHandler &handler) { 773221345Sdim wasAnalyzed[block->getBlockID()] = true; 774221345Sdim vals.resetScratch(); 775239462Sdim // Merge in values of predecessor blocks. 776221345Sdim bool isFirst = true; 777221345Sdim for (CFGBlock::const_pred_iterator I = block->pred_begin(), 778221345Sdim E = block->pred_end(); I != E; ++I) { 779226633Sdim const CFGBlock *pred = *I; 780276479Sdim if (!pred) 781276479Sdim continue; 782226633Sdim if (wasAnalyzed[pred->getBlockID()]) { 783239462Sdim vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); 784226633Sdim isFirst = false; 785226633Sdim } 786221345Sdim } 787221345Sdim // Apply the transfer function. 788239462Sdim TransferFunctions tf(vals, cfg, block, ac, classification, handler); 789221345Sdim for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 790221345Sdim I != E; ++I) { 791249423Sdim if (Optional<CFGStmt> cs = I->getAs<CFGStmt>()) 792226633Sdim tf.Visit(const_cast<Stmt*>(cs->getStmt())); 793221345Sdim } 794221345Sdim return vals.updateValueVectorWithScratch(block); 795221345Sdim} 796198092Srdivacky 797249423Sdim/// PruneBlocksHandler is a special UninitVariablesHandler that is used 798249423Sdim/// to detect when a CFGBlock has any *potential* use of an uninitialized 799249423Sdim/// variable. It is mainly used to prune out work during the final 800249423Sdim/// reporting pass. 801249423Sdimnamespace { 802249423Sdimstruct PruneBlocksHandler : public UninitVariablesHandler { 803249423Sdim PruneBlocksHandler(unsigned numBlocks) 804249423Sdim : hadUse(numBlocks, false), hadAnyUse(false), 805249423Sdim currentBlock(0) {} 806249423Sdim 807249423Sdim virtual ~PruneBlocksHandler() {} 808249423Sdim 809249423Sdim /// Records if a CFGBlock had a potential use of an uninitialized variable. 810249423Sdim llvm::BitVector hadUse; 811249423Sdim 812249423Sdim /// Records if any CFGBlock had a potential use of an uninitialized variable. 813249423Sdim bool hadAnyUse; 814249423Sdim 815249423Sdim /// The current block to scribble use information. 816249423Sdim unsigned currentBlock; 817249423Sdim 818276479Sdim void handleUseOfUninitVariable(const VarDecl *vd, 819276479Sdim const UninitUse &use) override { 820249423Sdim hadUse[currentBlock] = true; 821249423Sdim hadAnyUse = true; 822249423Sdim } 823249423Sdim 824249423Sdim /// Called when the uninitialized variable analysis detects the 825249423Sdim /// idiom 'int x = x'. All other uses of 'x' within the initializer 826249423Sdim /// are handled by handleUseOfUninitVariable. 827276479Sdim void handleSelfInit(const VarDecl *vd) override { 828249423Sdim hadUse[currentBlock] = true; 829249423Sdim hadAnyUse = true; 830249423Sdim } 831249423Sdim}; 832249423Sdim} 833249423Sdim 834224145Sdimvoid clang::runUninitializedVariablesAnalysis( 835224145Sdim const DeclContext &dc, 836224145Sdim const CFG &cfg, 837234353Sdim AnalysisDeclContext &ac, 838224145Sdim UninitVariablesHandler &handler, 839224145Sdim UninitVariablesAnalysisStats &stats) { 840221345Sdim CFGBlockValues vals(cfg); 841221345Sdim vals.computeSetOfDeclarations(dc); 842221345Sdim if (vals.hasNoDeclarations()) 843221345Sdim return; 844198092Srdivacky 845224145Sdim stats.NumVariablesAnalyzed = vals.getNumEntries(); 846224145Sdim 847239462Sdim // Precompute which expressions are uses and which are initializations. 848239462Sdim ClassifyRefs classification(ac); 849239462Sdim cfg.VisitBlockStmts(classification); 850239462Sdim 851221345Sdim // Mark all variables uninitialized at the entry. 852221345Sdim const CFGBlock &entry = cfg.getEntry(); 853239462Sdim ValueVector &vec = vals.getValueVector(&entry); 854239462Sdim const unsigned n = vals.getNumEntries(); 855239462Sdim for (unsigned j = 0; j < n ; ++j) { 856239462Sdim vec[j] = Uninitialized; 857221345Sdim } 858193326Sed 859221345Sdim // Proceed with the workist. 860249423Sdim DataflowWorklist worklist(cfg, *ac.getAnalysis<PostOrderCFGView>()); 861221345Sdim llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 862221345Sdim worklist.enqueueSuccessors(&cfg.getEntry()); 863221345Sdim llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 864226633Sdim wasAnalyzed[cfg.getEntry().getBlockID()] = true; 865249423Sdim PruneBlocksHandler PBH(cfg.getNumBlockIDs()); 866198092Srdivacky 867221345Sdim while (const CFGBlock *block = worklist.dequeue()) { 868249423Sdim PBH.currentBlock = block->getBlockID(); 869249423Sdim 870221345Sdim // Did the block change? 871239462Sdim bool changed = runOnBlock(block, cfg, ac, vals, 872249423Sdim classification, wasAnalyzed, PBH); 873224145Sdim ++stats.NumBlockVisits; 874221345Sdim if (changed || !previouslyVisited[block->getBlockID()]) 875221345Sdim worklist.enqueueSuccessors(block); 876221345Sdim previouslyVisited[block->getBlockID()] = true; 877193326Sed } 878249423Sdim 879249423Sdim if (!PBH.hadAnyUse) 880249423Sdim return; 881249423Sdim 882249423Sdim // Run through the blocks one more time, and report uninitialized variables. 883221345Sdim for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 884226633Sdim const CFGBlock *block = *BI; 885249423Sdim if (PBH.hadUse[block->getBlockID()]) { 886249423Sdim runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler); 887224145Sdim ++stats.NumBlockVisits; 888224145Sdim } 889221345Sdim } 890221345Sdim} 891193326Sed 892221345SdimUninitVariablesHandler::~UninitVariablesHandler() {} 893