head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.9 netbsd-11-0-RC3:1.1.1.9 netbsd-11-0-RC2:1.1.1.9 netbsd-11-0-RC1:1.1.1.9 perseant-exfatfs-base-20250801:1.1.1.9 netbsd-11:1.1.1.9.0.10 netbsd-11-base:1.1.1.9 netbsd-10-1-RELEASE:1.1.1.9 perseant-exfatfs-base-20240630:1.1.1.9 perseant-exfatfs:1.1.1.9.0.8 perseant-exfatfs-base:1.1.1.9 netbsd-8-3-RELEASE:1.1.1.7 netbsd-9-4-RELEASE:1.1.1.8 netbsd-10-0-RELEASE:1.1.1.9 netbsd-10-0-RC6:1.1.1.9 netbsd-10-0-RC5:1.1.1.9 netbsd-10-0-RC4:1.1.1.9 netbsd-10-0-RC3:1.1.1.9 netbsd-10-0-RC2:1.1.1.9 netbsd-10-0-RC1:1.1.1.9 netbsd-10:1.1.1.9.0.6 netbsd-10-base:1.1.1.9 netbsd-9-3-RELEASE:1.1.1.8 cjep_sun2x:1.1.1.9.0.4 cjep_sun2x-base:1.1.1.9 cjep_staticlib_x-base1:1.1.1.9 netbsd-9-2-RELEASE:1.1.1.8 cjep_staticlib_x:1.1.1.9.0.2 cjep_staticlib_x-base:1.1.1.9 netbsd-9-1-RELEASE:1.1.1.8 phil-wifi-20200421:1.1.1.9 phil-wifi-20200411:1.1.1.9 phil-wifi-20200406:1.1.1.9 netbsd-8-2-RELEASE:1.1.1.7 netbsd-9-0-RELEASE:1.1.1.8 netbsd-9-0-RC2:1.1.1.8 netbsd-9-0-RC1:1.1.1.8 netbsd-9:1.1.1.8.0.2 netbsd-9-base:1.1.1.8 phil-wifi-20190609:1.1.1.8 netbsd-8-1-RELEASE:1.1.1.7 netbsd-8-1-RC1:1.1.1.7 pgoyette-compat-merge-20190127:1.1.1.7.12.1 pgoyette-compat-20190127:1.1.1.8 pgoyette-compat-20190118:1.1.1.8 pgoyette-compat-1226:1.1.1.8 pgoyette-compat-1126:1.1.1.8 pgoyette-compat-1020:1.1.1.8 pgoyette-compat-0930:1.1.1.8 pgoyette-compat-0906:1.1.1.8 netbsd-7-2-RELEASE:1.1.1.4.2.1 pgoyette-compat-0728:1.1.1.8 clang-337282:1.1.1.8 netbsd-8-0-RELEASE:1.1.1.7 phil-wifi:1.1.1.7.0.14 phil-wifi-base:1.1.1.7 pgoyette-compat-0625:1.1.1.7 netbsd-8-0-RC2:1.1.1.7 pgoyette-compat-0521:1.1.1.7 pgoyette-compat-0502:1.1.1.7 pgoyette-compat-0422:1.1.1.7 netbsd-8-0-RC1:1.1.1.7 pgoyette-compat-0415:1.1.1.7 pgoyette-compat-0407:1.1.1.7 pgoyette-compat-0330:1.1.1.7 pgoyette-compat-0322:1.1.1.7 pgoyette-compat-0315:1.1.1.7 netbsd-7-1-2-RELEASE:1.1.1.4.2.1 pgoyette-compat:1.1.1.7.0.12 pgoyette-compat-base:1.1.1.7 netbsd-7-1-1-RELEASE:1.1.1.4.2.1 clang-319952:1.1.1.7 matt-nb8-mediatek:1.1.1.7.0.10 matt-nb8-mediatek-base:1.1.1.7 clang-309604:1.1.1.7 perseant-stdc-iso10646:1.1.1.7.0.8 perseant-stdc-iso10646-base:1.1.1.7 netbsd-8:1.1.1.7.0.6 netbsd-8-base:1.1.1.7 prg-localcount2-base3:1.1.1.7 prg-localcount2-base2:1.1.1.7 prg-localcount2-base1:1.1.1.7 prg-localcount2:1.1.1.7.0.4 prg-localcount2-base:1.1.1.7 pgoyette-localcount-20170426:1.1.1.7 bouyer-socketcan-base1:1.1.1.7 pgoyette-localcount-20170320:1.1.1.7 netbsd-7-1:1.1.1.4.2.1.0.6 netbsd-7-1-RELEASE:1.1.1.4.2.1 netbsd-7-1-RC2:1.1.1.4.2.1 clang-294123:1.1.1.7 netbsd-7-nhusb-base-20170116:1.1.1.4.2.1 bouyer-socketcan:1.1.1.7.0.2 bouyer-socketcan-base:1.1.1.7 clang-291444:1.1.1.7 pgoyette-localcount-20170107:1.1.1.6 netbsd-7-1-RC1:1.1.1.4.2.1 pgoyette-localcount-20161104:1.1.1.6 netbsd-7-0-2-RELEASE:1.1.1.4.2.1 localcount-20160914:1.1.1.6 netbsd-7-nhusb:1.1.1.4.2.1.0.4 netbsd-7-nhusb-base:1.1.1.4.2.1 clang-280599:1.1.1.6 pgoyette-localcount-20160806:1.1.1.6 pgoyette-localcount-20160726:1.1.1.6 pgoyette-localcount:1.1.1.6.0.2 pgoyette-localcount-base:1.1.1.6 netbsd-7-0-1-RELEASE:1.1.1.4.2.1 clang-261930:1.1.1.6 netbsd-7-0:1.1.1.4.2.1.0.2 netbsd-7-0-RELEASE:1.1.1.4.2.1 netbsd-7-0-RC3:1.1.1.4.2.1 netbsd-7-0-RC2:1.1.1.4.2.1 netbsd-7-0-RC1:1.1.1.4.2.1 clang-237755:1.1.1.5 clang-232565:1.1.1.5 clang-227398:1.1.1.5 tls-maxphys-base:1.1.1.4 tls-maxphys:1.1.1.4.0.4 netbsd-7:1.1.1.4.0.2 netbsd-7-base:1.1.1.4 clang-215315:1.1.1.4 clang-209886:1.1.1.3 yamt-pagecache:1.1.1.2.0.4 yamt-pagecache-base9:1.1.1.2 tls-earlyentropy:1.1.1.2.0.2 tls-earlyentropy-base:1.1.1.3 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.2 riastradh-drm2-base3:1.1.1.2 clang-202566:1.1.1.2 clang-201163:1.1.1.1 clang-199312:1.1.1.1 clang-198450:1.1.1.1 clang-196603:1.1.1.1 clang-195771:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2013.11.28.14.14.49; author joerg; state Exp; branches 1.1.1.1; next ; commitid ow8OybrawrB1f3fx; 1.1.1.1 date 2013.11.28.14.14.49; author joerg; state Exp; branches; next 1.1.1.2; commitid ow8OybrawrB1f3fx; 1.1.1.2 date 2014.03.04.19.54.04; author joerg; state Exp; branches 1.1.1.2.2.1 1.1.1.2.4.1; next 1.1.1.3; commitid 29z1hJonZISIXprx; 1.1.1.3 date 2014.05.30.18.14.40; author joerg; state Exp; branches; next 1.1.1.4; commitid 8q0kdlBlCn09GACx; 1.1.1.4 date 2014.08.10.17.08.27; author joerg; state Exp; branches 1.1.1.4.2.1 1.1.1.4.4.1; next 1.1.1.5; commitid N85tXAN6Ex9VZPLx; 1.1.1.5 date 2015.01.29.19.57.33; author joerg; state Exp; branches; next 1.1.1.6; commitid mlISSizlPKvepX7y; 1.1.1.6 date 2016.02.27.22.11.54; author joerg; state Exp; branches 1.1.1.6.2.1; next 1.1.1.7; commitid tIimz3oDlh1NpBWy; 1.1.1.7 date 2017.01.11.10.34.45; author joerg; state Exp; branches 1.1.1.7.12.1 1.1.1.7.14.1; next 1.1.1.8; commitid CNnUNfII1jgNmxBz; 1.1.1.8 date 2018.07.17.18.31.08; author joerg; state Exp; branches; next 1.1.1.9; commitid wDzL46ALjrCZgwKA; 1.1.1.9 date 2019.11.13.22.19.20; author joerg; state dead; branches; next ; commitid QD8YATxuNG34YJKB; 1.1.1.2.2.1 date 2014.08.10.07.08.07; author tls; state Exp; branches; next ; commitid t01A1TLTYxkpGMLx; 1.1.1.2.4.1 date 2014.03.04.19.54.04; author yamt; state dead; branches; next 1.1.1.2.4.2; commitid WSrDtL5nYAUyiyBx; 1.1.1.2.4.2 date 2014.05.22.16.18.26; author yamt; state Exp; branches; next ; commitid WSrDtL5nYAUyiyBx; 1.1.1.4.2.1 date 2015.06.04.20.04.27; author snj; state Exp; branches; next ; commitid yRnjq9fueSo6n9oy; 1.1.1.4.4.1 date 2014.08.10.17.08.27; author tls; state dead; branches; next 1.1.1.4.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.4.4.2 date 2014.08.19.23.47.26; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; 1.1.1.6.2.1 date 2017.03.20.06.52.36; author pgoyette; state Exp; branches; next ; commitid jjw7cAwgyKq7RfKz; 1.1.1.7.12.1 date 2018.07.28.04.33.16; author pgoyette; state Exp; branches; next ; commitid 1UP1xAIUxv1ZgRLA; 1.1.1.7.14.1 date 2019.06.10.21.45.20; author christos; state Exp; branches; next 1.1.1.7.14.2; commitid jtc8rnCzWiEEHGqB; 1.1.1.7.14.2 date 2020.04.13.07.46.31; author martin; state dead; branches; next ; commitid X01YhRUPVUDaec4C; desc @@ 1.1 log @Initial revision @ text @//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements uninitialized values analysis for source-level CFGs. // //===----------------------------------------------------------------------===// #include "clang/AST/ASTContext.h" #include "clang/AST/Attr.h" #include "clang/AST/Decl.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/Analyses/UninitializedValues.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/PackedVector.h" #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/SaveAndRestore.h" #include using namespace clang; #define DEBUG_LOGGING 0 static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && !vd->isExceptionVariable() && vd->getDeclContext() == dc) { QualType ty = vd->getType(); return ty->isScalarType() || ty->isVectorType(); } return false; } //------------------------------------------------------------------------====// // DeclToIndex: a mapping from Decls we track to value indices. //====------------------------------------------------------------------------// namespace { class DeclToIndex { llvm::DenseMap map; public: DeclToIndex() {} /// Compute the actual mapping from declarations to bits. void computeMap(const DeclContext &dc); /// Return the number of declarations in the map. unsigned size() const { return map.size(); } /// Returns the bit vector index for a given declaration. Optional getValueIndex(const VarDecl *d) const; }; } void DeclToIndex::computeMap(const DeclContext &dc) { unsigned count = 0; DeclContext::specific_decl_iterator I(dc.decls_begin()), E(dc.decls_end()); for ( ; I != E; ++I) { const VarDecl *vd = *I; if (isTrackedVar(vd, &dc)) map[vd] = count++; } } Optional DeclToIndex::getValueIndex(const VarDecl *d) const { llvm::DenseMap::const_iterator I = map.find(d); if (I == map.end()) return None; return I->second; } //------------------------------------------------------------------------====// // CFGBlockValues: dataflow values for CFG blocks. //====------------------------------------------------------------------------// // These values are defined in such a way that a merge can be done using // a bitwise OR. enum Value { Unknown = 0x0, /* 00 */ Initialized = 0x1, /* 01 */ Uninitialized = 0x2, /* 10 */ MayUninitialized = 0x3 /* 11 */ }; static bool isUninitialized(const Value v) { return v >= Uninitialized; } static bool isAlwaysUninit(const Value v) { return v == Uninitialized; } namespace { typedef llvm::PackedVector ValueVector; class CFGBlockValues { const CFG &cfg; SmallVector vals; ValueVector scratch; DeclToIndex declToIndex; public: CFGBlockValues(const CFG &cfg); unsigned getNumEntries() const { return declToIndex.size(); } void computeSetOfDeclarations(const DeclContext &dc); ValueVector &getValueVector(const CFGBlock *block) { return vals[block->getBlockID()]; } void setAllScratchValues(Value V); void mergeIntoScratch(ValueVector const &source, bool isFirst); bool updateValueVectorWithScratch(const CFGBlock *block); bool hasNoDeclarations() const { return declToIndex.size() == 0; } void resetScratch(); ValueVector::reference operator[](const VarDecl *vd); Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, const VarDecl *vd) { const Optional &idx = declToIndex.getValueIndex(vd); assert(idx.hasValue()); return getValueVector(block)[idx.getValue()]; } }; } // end anonymous namespace CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { declToIndex.computeMap(dc); unsigned decls = declToIndex.size(); scratch.resize(decls); unsigned n = cfg.getNumBlockIDs(); if (!n) return; vals.resize(n); for (unsigned i = 0; i < n; ++i) vals[i].resize(decls); } #if DEBUG_LOGGING static void printVector(const CFGBlock *block, ValueVector &bv, unsigned num) { llvm::errs() << block->getBlockID() << " :"; for (unsigned i = 0; i < bv.size(); ++i) { llvm::errs() << ' ' << bv[i]; } llvm::errs() << " : " << num << '\n'; } #endif void CFGBlockValues::setAllScratchValues(Value V) { for (unsigned I = 0, E = scratch.size(); I != E; ++I) scratch[I] = V; } void CFGBlockValues::mergeIntoScratch(ValueVector const &source, bool isFirst) { if (isFirst) scratch = source; else scratch |= source; } bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { ValueVector &dst = getValueVector(block); bool changed = (dst != scratch); if (changed) dst = scratch; #if DEBUG_LOGGING printVector(block, scratch, 0); #endif return changed; } void CFGBlockValues::resetScratch() { scratch.reset(); } ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { const Optional &idx = declToIndex.getValueIndex(vd); assert(idx.hasValue()); return scratch[idx.getValue()]; } //------------------------------------------------------------------------====// // Worklist: worklist for dataflow analysis. //====------------------------------------------------------------------------// namespace { class DataflowWorklist { PostOrderCFGView::iterator PO_I, PO_E; SmallVector worklist; llvm::BitVector enqueuedBlocks; public: DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) : PO_I(view.begin()), PO_E(view.end()), enqueuedBlocks(cfg.getNumBlockIDs(), true) { // Treat the first block as already analyzed. if (PO_I != PO_E) { assert(*PO_I == &cfg.getEntry()); enqueuedBlocks[(*PO_I)->getBlockID()] = false; ++PO_I; } } void enqueueSuccessors(const CFGBlock *block); const CFGBlock *dequeue(); }; } void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { const CFGBlock *Successor = *I; if (!Successor || enqueuedBlocks[Successor->getBlockID()]) continue; worklist.push_back(Successor); enqueuedBlocks[Successor->getBlockID()] = true; } } const CFGBlock *DataflowWorklist::dequeue() { const CFGBlock *B = 0; // First dequeue from the worklist. This can represent // updates along backedges that we want propagated as quickly as possible. if (!worklist.empty()) B = worklist.pop_back_val(); // Next dequeue from the initial reverse post order. This is the // theoretical ideal in the presence of no back edges. else if (PO_I != PO_E) { B = *PO_I; ++PO_I; } else { return 0; } assert(enqueuedBlocks[B->getBlockID()] == true); enqueuedBlocks[B->getBlockID()] = false; return B; } //------------------------------------------------------------------------====// // Classification of DeclRefExprs as use or initialization. //====------------------------------------------------------------------------// namespace { class FindVarResult { const VarDecl *vd; const DeclRefExpr *dr; public: FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} const DeclRefExpr *getDeclRefExpr() const { return dr; } const VarDecl *getDecl() const { return vd; } }; static const Expr *stripCasts(ASTContext &C, const Expr *Ex) { while (Ex) { Ex = Ex->IgnoreParenNoopCasts(C); if (const CastExpr *CE = dyn_cast(Ex)) { if (CE->getCastKind() == CK_LValueBitCast) { Ex = CE->getSubExpr(); continue; } } break; } return Ex; } /// If E is an expression comprising a reference to a single variable, find that /// variable. static FindVarResult findVar(const Expr *E, const DeclContext *DC) { if (const DeclRefExpr *DRE = dyn_cast(stripCasts(DC->getParentASTContext(), E))) if (const VarDecl *VD = dyn_cast(DRE->getDecl())) if (isTrackedVar(VD, DC)) return FindVarResult(VD, DRE); return FindVarResult(0, 0); } /// \brief Classify each DeclRefExpr as an initialization or a use. Any /// DeclRefExpr which isn't explicitly classified will be assumed to have /// escaped the analysis and will be treated as an initialization. class ClassifyRefs : public StmtVisitor { public: enum Class { Init, Use, SelfInit, Ignore }; private: const DeclContext *DC; llvm::DenseMap Classification; bool isTrackedVar(const VarDecl *VD) const { return ::isTrackedVar(VD, DC); } void classify(const Expr *E, Class C); public: ClassifyRefs(AnalysisDeclContext &AC) : DC(cast(AC.getDecl())) {} void VisitDeclStmt(DeclStmt *DS); void VisitUnaryOperator(UnaryOperator *UO); void VisitBinaryOperator(BinaryOperator *BO); void VisitCallExpr(CallExpr *CE); void VisitCastExpr(CastExpr *CE); void operator()(Stmt *S) { Visit(S); } Class get(const DeclRefExpr *DRE) const { llvm::DenseMap::const_iterator I = Classification.find(DRE); if (I != Classification.end()) return I->second; const VarDecl *VD = dyn_cast(DRE->getDecl()); if (!VD || !isTrackedVar(VD)) return Ignore; return Init; } }; } static const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { if (Expr *Init = VD->getInit()) { const DeclRefExpr *DRE = dyn_cast(stripCasts(VD->getASTContext(), Init)); if (DRE && DRE->getDecl() == VD) return DRE; } return 0; } void ClassifyRefs::classify(const Expr *E, Class C) { // The result of a ?: could also be an lvalue. E = E->IgnoreParens(); if (const ConditionalOperator *CO = dyn_cast(E)) { const Expr *TrueExpr = CO->getTrueExpr(); if (!isa(TrueExpr)) classify(TrueExpr, C); classify(CO->getFalseExpr(), C); return; } FindVarResult Var = findVar(E, DC); if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) Classification[DRE] = std::max(Classification[DRE], C); } void ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); DI != DE; ++DI) { VarDecl *VD = dyn_cast(*DI); if (VD && isTrackedVar(VD)) if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) Classification[DRE] = SelfInit; } } void ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this // is not a compound-assignment, we will treat it as initializing the variable // when TransferFunctions visits it. A compound-assignment does not affect // whether a variable is uninitialized, and there's no point counting it as a // use. if (BO->isCompoundAssignmentOp()) classify(BO->getLHS(), Use); else if (BO->getOpcode() == BO_Assign) classify(BO->getLHS(), Ignore); } void ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { // Increment and decrement are uses despite there being no lvalue-to-rvalue // conversion. if (UO->isIncrementDecrementOp()) classify(UO->getSubExpr(), Use); } void ClassifyRefs::VisitCallExpr(CallExpr *CE) { // If a value is passed by const reference to a function, we should not assume // that it is initialized by the call, and we conservatively do not assume // that it is used. for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); I != E; ++I) if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) classify(*I, Ignore); } void ClassifyRefs::VisitCastExpr(CastExpr *CE) { if (CE->getCastKind() == CK_LValueToRValue) classify(CE->getSubExpr(), Use); else if (CStyleCastExpr *CSE = dyn_cast(CE)) { if (CSE->getType()->isVoidType()) { // Squelch any detected load of an uninitialized value if // we cast it to void. // e.g. (void) x; classify(CSE->getSubExpr(), Ignore); } } } //------------------------------------------------------------------------====// // Transfer function for uninitialized values analysis. //====------------------------------------------------------------------------// namespace { class TransferFunctions : public StmtVisitor { CFGBlockValues &vals; const CFG &cfg; const CFGBlock *block; AnalysisDeclContext ∾ const ClassifyRefs &classification; ObjCNoReturn objCNoRet; UninitVariablesHandler &handler; public: TransferFunctions(CFGBlockValues &vals, const CFG &cfg, const CFGBlock *block, AnalysisDeclContext &ac, const ClassifyRefs &classification, UninitVariablesHandler &handler) : vals(vals), cfg(cfg), block(block), ac(ac), classification(classification), objCNoRet(ac.getASTContext()), handler(handler) {} void reportUse(const Expr *ex, const VarDecl *vd); void VisitBinaryOperator(BinaryOperator *bo); void VisitBlockExpr(BlockExpr *be); void VisitCallExpr(CallExpr *ce); void VisitDeclRefExpr(DeclRefExpr *dr); void VisitDeclStmt(DeclStmt *ds); void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); void VisitObjCMessageExpr(ObjCMessageExpr *ME); bool isTrackedVar(const VarDecl *vd) { return ::isTrackedVar(vd, cast(ac.getDecl())); } FindVarResult findVar(const Expr *ex) { return ::findVar(ex, cast(ac.getDecl())); } UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { UninitUse Use(ex, isAlwaysUninit(v)); assert(isUninitialized(v)); if (Use.getKind() == UninitUse::Always) return Use; // If an edge which leads unconditionally to this use did not initialize // the variable, we can say something stronger than 'may be uninitialized': // we can say 'either it's used uninitialized or you have dead code'. // // We track the number of successors of a node which have been visited, and // visit a node once we have visited all of its successors. Only edges where // the variable might still be uninitialized are followed. Since a variable // can't transfer from being initialized to being uninitialized, this will // trace out the subgraph which inevitably leads to the use and does not // initialize the variable. We do not want to skip past loops, since their // non-termination might be correlated with the initialization condition. // // For example: // // void f(bool a, bool b) { // block1: int n; // if (a) { // block2: if (b) // block3: n = 1; // block4: } else if (b) { // block5: while (!a) { // block6: do_work(&a); // n = 2; // } // } // block7: if (a) // block8: g(); // block9: return n; // } // // Starting from the maybe-uninitialized use in block 9: // * Block 7 is not visited because we have only visited one of its two // successors. // * Block 8 is visited because we've visited its only successor. // From block 8: // * Block 7 is visited because we've now visited both of its successors. // From block 7: // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). // * Block 3 is not visited because it initializes 'n'. // Now the algorithm terminates, having visited blocks 7 and 8, and having // found the frontier is blocks 2, 4, and 5. // // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 // and 4), so we report that any time either of those edges is taken (in // each case when 'b == false'), 'n' is used uninitialized. SmallVector Queue; SmallVector SuccsVisited(cfg.getNumBlockIDs(), 0); Queue.push_back(block); // Specify that we've already visited all successors of the starting block. // This has the dual purpose of ensuring we never add it to the queue, and // of marking it as not being a candidate element of the frontier. SuccsVisited[block->getBlockID()] = block->succ_size(); while (!Queue.empty()) { const CFGBlock *B = Queue.pop_back_val(); // If the use is always reached from the entry block, make a note of that. if (B == &cfg.getEntry()) Use.setUninitAfterCall(); for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); I != E; ++I) { const CFGBlock *Pred = *I; Value AtPredExit = vals.getValue(Pred, B, vd); if (AtPredExit == Initialized) // This block initializes the variable. continue; if (AtPredExit == MayUninitialized && vals.getValue(B, 0, vd) == Uninitialized) { // This block declares the variable (uninitialized), and is reachable // from a block that initializes the variable. We can't guarantee to // give an earlier location for the diagnostic (and it appears that // this code is intended to be reachable) so give a diagnostic here // and go no further down this path. Use.setUninitAfterDecl(); continue; } unsigned &SV = SuccsVisited[Pred->getBlockID()]; if (!SV) { // When visiting the first successor of a block, mark all NULL // successors as having been visited. for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), SE = Pred->succ_end(); SI != SE; ++SI) if (!*SI) ++SV; } if (++SV == Pred->succ_size()) // All paths from this block lead to the use and don't initialize the // variable. Queue.push_back(Pred); } } // Scan the frontier, looking for blocks where the variable was // uninitialized. for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { const CFGBlock *Block = *BI; unsigned BlockID = Block->getBlockID(); const Stmt *Term = Block->getTerminator(); if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && Term) { // This block inevitably leads to the use. If we have an edge from here // to a post-dominator block, and the variable is uninitialized on that // edge, we have found a bug. for (CFGBlock::const_succ_iterator I = Block->succ_begin(), E = Block->succ_end(); I != E; ++I) { const CFGBlock *Succ = *I; if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && vals.getValue(Block, Succ, vd) == Uninitialized) { // Switch cases are a special case: report the label to the caller // as the 'terminator', not the switch statement itself. Suppress // situations where no label matched: we can't be sure that's // possible. if (isa(Term)) { const Stmt *Label = Succ->getLabel(); if (!Label || !isa(Label)) // Might not be possible. continue; UninitUse::Branch Branch; Branch.Terminator = Label; Branch.Output = 0; // Ignored. Use.addUninitBranch(Branch); } else { UninitUse::Branch Branch; Branch.Terminator = Term; Branch.Output = I - Block->succ_begin(); Use.addUninitBranch(Branch); } } } } } return Use; } }; } void TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { Value v = vals[vd]; if (isUninitialized(v)) handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); } void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { // This represents an initialization of the 'element' value. if (DeclStmt *DS = dyn_cast(FS->getElement())) { const VarDecl *VD = cast(DS->getSingleDecl()); if (isTrackedVar(VD)) vals[VD] = Initialized; } } void TransferFunctions::VisitBlockExpr(BlockExpr *be) { const BlockDecl *bd = be->getBlockDecl(); for (BlockDecl::capture_const_iterator i = bd->capture_begin(), e = bd->capture_end() ; i != e; ++i) { const VarDecl *vd = i->getVariable(); if (!isTrackedVar(vd)) continue; if (i->isByRef()) { vals[vd] = Initialized; continue; } reportUse(be, vd); } } void TransferFunctions::VisitCallExpr(CallExpr *ce) { if (Decl *Callee = ce->getCalleeDecl()) { if (Callee->hasAttr()) { // After a call to a function like setjmp or vfork, any variable which is // initialized anywhere within this function may now be initialized. For // now, just assume such a call initializes all variables. FIXME: Only // mark variables as initialized if they have an initializer which is // reachable from here. vals.setAllScratchValues(Initialized); } else if (Callee->hasAttr()) { // Functions labeled like "analyzer_noreturn" are often used to denote // "panic" functions that in special debug situations can still return, // but for the most part should not be treated as returning. This is a // useful annotation borrowed from the static analyzer that is useful for // suppressing branch-specific false positives when we call one of these // functions but keep pretending the path continues (when in reality the // user doesn't care). vals.setAllScratchValues(Unknown); } } } void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { switch (classification.get(dr)) { case ClassifyRefs::Ignore: break; case ClassifyRefs::Use: reportUse(dr, cast(dr->getDecl())); break; case ClassifyRefs::Init: vals[cast(dr->getDecl())] = Initialized; break; case ClassifyRefs::SelfInit: handler.handleSelfInit(cast(dr->getDecl())); break; } } void TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { if (BO->getOpcode() == BO_Assign) { FindVarResult Var = findVar(BO->getLHS()); if (const VarDecl *VD = Var.getDecl()) vals[VD] = Initialized; } } void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); DI != DE; ++DI) { VarDecl *VD = dyn_cast(*DI); if (VD && isTrackedVar(VD)) { if (getSelfInitExpr(VD)) { // If the initializer consists solely of a reference to itself, we // explicitly mark the variable as uninitialized. This allows code // like the following: // // int x = x; // // to deliberately leave a variable uninitialized. Different analysis // clients can detect this pattern and adjust their reporting // appropriately, but we need to continue to analyze subsequent uses // of the variable. vals[VD] = Uninitialized; } else if (VD->getInit()) { // Treat the new variable as initialized. vals[VD] = Initialized; } else { // No initializer: the variable is now uninitialized. This matters // for cases like: // while (...) { // int n; // use(n); // n = 0; // } // FIXME: Mark the variable as uninitialized whenever its scope is // left, since its scope could be re-entered by a jump over the // declaration. vals[VD] = Uninitialized; } } } } void TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { // If the Objective-C message expression is an implicit no-return that // is not modeled in the CFG, set the tracked dataflow values to Unknown. if (objCNoRet.isImplicitNoReturn(ME)) { vals.setAllScratchValues(Unknown); } } //------------------------------------------------------------------------====// // High-level "driver" logic for uninitialized values analysis. //====------------------------------------------------------------------------// static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler) { wasAnalyzed[block->getBlockID()] = true; vals.resetScratch(); // Merge in values of predecessor blocks. bool isFirst = true; for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { const CFGBlock *pred = *I; if (wasAnalyzed[pred->getBlockID()]) { vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); isFirst = false; } } // Apply the transfer function. TransferFunctions tf(vals, cfg, block, ac, classification, handler); for (CFGBlock::const_iterator I = block->begin(), E = block->end(); I != E; ++I) { if (Optional cs = I->getAs()) tf.Visit(const_cast(cs->getStmt())); } return vals.updateValueVectorWithScratch(block); } /// PruneBlocksHandler is a special UninitVariablesHandler that is used /// to detect when a CFGBlock has any *potential* use of an uninitialized /// variable. It is mainly used to prune out work during the final /// reporting pass. namespace { struct PruneBlocksHandler : public UninitVariablesHandler { PruneBlocksHandler(unsigned numBlocks) : hadUse(numBlocks, false), hadAnyUse(false), currentBlock(0) {} virtual ~PruneBlocksHandler() {} /// Records if a CFGBlock had a potential use of an uninitialized variable. llvm::BitVector hadUse; /// Records if any CFGBlock had a potential use of an uninitialized variable. bool hadAnyUse; /// The current block to scribble use information. unsigned currentBlock; virtual void handleUseOfUninitVariable(const VarDecl *vd, const UninitUse &use) { hadUse[currentBlock] = true; hadAnyUse = true; } /// Called when the uninitialized variable analysis detects the /// idiom 'int x = x'. All other uses of 'x' within the initializer /// are handled by handleUseOfUninitVariable. virtual void handleSelfInit(const VarDecl *vd) { hadUse[currentBlock] = true; hadAnyUse = true; } }; } void clang::runUninitializedVariablesAnalysis( const DeclContext &dc, const CFG &cfg, AnalysisDeclContext &ac, UninitVariablesHandler &handler, UninitVariablesAnalysisStats &stats) { CFGBlockValues vals(cfg); vals.computeSetOfDeclarations(dc); if (vals.hasNoDeclarations()) return; stats.NumVariablesAnalyzed = vals.getNumEntries(); // Precompute which expressions are uses and which are initializations. ClassifyRefs classification(ac); cfg.VisitBlockStmts(classification); // Mark all variables uninitialized at the entry. const CFGBlock &entry = cfg.getEntry(); ValueVector &vec = vals.getValueVector(&entry); const unsigned n = vals.getNumEntries(); for (unsigned j = 0; j < n ; ++j) { vec[j] = Uninitialized; } // Proceed with the workist. DataflowWorklist worklist(cfg, *ac.getAnalysis()); llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); worklist.enqueueSuccessors(&cfg.getEntry()); llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); wasAnalyzed[cfg.getEntry().getBlockID()] = true; PruneBlocksHandler PBH(cfg.getNumBlockIDs()); while (const CFGBlock *block = worklist.dequeue()) { PBH.currentBlock = block->getBlockID(); // Did the block change? bool changed = runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, PBH); ++stats.NumBlockVisits; if (changed || !previouslyVisited[block->getBlockID()]) worklist.enqueueSuccessors(block); previouslyVisited[block->getBlockID()] = true; } if (!PBH.hadAnyUse) return; // Run through the blocks one more time, and report uninitialized variables. for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { const CFGBlock *block = *BI; if (PBH.hadUse[block->getBlockID()]) { runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler); ++stats.NumBlockVisits; } } } UninitVariablesHandler::~UninitVariablesHandler() {} @ 1.1.1.1 log @Import Clang 3.4rc1 r195771. @ text @@ 1.1.1.2 log @Import Clang 3.5svn r202566. @ text @a537 3 if (!Pred) continue; a753 2 if (!pred) continue; @ 1.1.1.2.2.1 log @Rebase. @ text @d239 1 a239 1 const CFGBlock *B = nullptr; d253 1 a253 1 return nullptr; d298 1 a298 1 return FindVarResult(nullptr, nullptr); d356 1 a356 1 return nullptr; d376 3 a378 2 for (auto *DI : DS->decls()) { VarDecl *VD = dyn_cast(DI); d546 1 a546 1 vals.getValue(B, nullptr, vd) == Uninitialized) { d636 3 a638 2 for (const auto &I : bd->captures()) { const VarDecl *vd = I.getVariable(); d641 1 a641 1 if (I.isByRef()) { d697 3 a699 2 for (auto *DI : DS->decls()) { VarDecl *VD = dyn_cast(DI); d795 2 a796 2 void handleUseOfUninitVariable(const VarDecl *vd, const UninitUse &use) override { d804 1 a804 1 void handleSelfInit(const VarDecl *vd) override { @ 1.1.1.3 log @Import Clang 3.5svn r209886. @ text @d239 1 a239 1 const CFGBlock *B = nullptr; d253 1 a253 1 return nullptr; d298 1 a298 1 return FindVarResult(nullptr, nullptr); d356 1 a356 1 return nullptr; d376 3 a378 2 for (auto *DI : DS->decls()) { VarDecl *VD = dyn_cast(DI); d546 1 a546 1 vals.getValue(B, nullptr, vd) == Uninitialized) { d636 3 a638 2 for (const auto &I : bd->captures()) { const VarDecl *vd = I.getVariable(); d641 1 a641 1 if (I.isByRef()) { d697 3 a699 2 for (auto *DI : DS->decls()) { VarDecl *VD = dyn_cast(DI); d795 2 a796 2 void handleUseOfUninitVariable(const VarDecl *vd, const UninitUse &use) override { d804 1 a804 1 void handleSelfInit(const VarDecl *vd) override { @ 1.1.1.4 log @Import clang 3.6svn r215315. @ text @d18 1 a18 1 #include "clang/Analysis/Analyses/DataflowWorklist.h" d37 1 a37 1 !vd->isExceptionVariable() && !vd->isInitCapture() && d202 60 d834 1 a834 1 DataflowWorklist worklist(cfg, ac); @ 1.1.1.4.2.1 log @Update LLVM to 3.6.1, requested by joerg in ticket 824. @ text @d18 1 a18 1 #include "clang/Analysis/Analyses/PostOrderCFGView.h" a201 60 // Worklist: worklist for dataflow analysis. //====------------------------------------------------------------------------// namespace { class DataflowWorklist { PostOrderCFGView::iterator PO_I, PO_E; SmallVector worklist; llvm::BitVector enqueuedBlocks; public: DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) : PO_I(view.begin()), PO_E(view.end()), enqueuedBlocks(cfg.getNumBlockIDs(), true) { // Treat the first block as already analyzed. if (PO_I != PO_E) { assert(*PO_I == &cfg.getEntry()); enqueuedBlocks[(*PO_I)->getBlockID()] = false; ++PO_I; } } void enqueueSuccessors(const CFGBlock *block); const CFGBlock *dequeue(); }; } void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { const CFGBlock *Successor = *I; if (!Successor || enqueuedBlocks[Successor->getBlockID()]) continue; worklist.push_back(Successor); enqueuedBlocks[Successor->getBlockID()] = true; } } const CFGBlock *DataflowWorklist::dequeue() { const CFGBlock *B = nullptr; // First dequeue from the worklist. This can represent // updates along backedges that we want propagated as quickly as possible. if (!worklist.empty()) B = worklist.pop_back_val(); // Next dequeue from the initial reverse post order. This is the // theoretical ideal in the presence of no back edges. else if (PO_I != PO_E) { B = *PO_I; ++PO_I; } else { return nullptr; } assert(enqueuedBlocks[B->getBlockID()] == true); enqueuedBlocks[B->getBlockID()] = false; return B; } //------------------------------------------------------------------------====// d303 3 a305 1 classify(CO->getTrueExpr(), C); a309 17 if (const BinaryConditionalOperator *BCO = dyn_cast(E)) { classify(BCO->getFalseExpr(), C); return; } if (const OpaqueValueExpr *OVE = dyn_cast(E)) { classify(OVE->getSourceExpr(), C); return; } if (const BinaryOperator *BO = dyn_cast(E)) { if (BO->getOpcode() == BO_Comma) classify(BO->getRHS(), C); return; } a343 11 // Classify arguments to std::move as used. if (CE->getNumArgs() == 1) { if (FunctionDecl *FD = CE->getDirectCallee()) { if (FD->isInStdNamespace() && FD->getIdentifier() && FD->getIdentifier()->isStr("move")) { classify(CE->getArg(0), Use); return; } } } d774 1 a774 1 DataflowWorklist worklist(cfg, *ac.getAnalysis()); @ 1.1.1.5 log @Import Clang 3.6RC1 r227398. @ text @d18 1 a18 1 #include "clang/Analysis/Analyses/PostOrderCFGView.h" a201 60 // Worklist: worklist for dataflow analysis. //====------------------------------------------------------------------------// namespace { class DataflowWorklist { PostOrderCFGView::iterator PO_I, PO_E; SmallVector worklist; llvm::BitVector enqueuedBlocks; public: DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) : PO_I(view.begin()), PO_E(view.end()), enqueuedBlocks(cfg.getNumBlockIDs(), true) { // Treat the first block as already analyzed. if (PO_I != PO_E) { assert(*PO_I == &cfg.getEntry()); enqueuedBlocks[(*PO_I)->getBlockID()] = false; ++PO_I; } } void enqueueSuccessors(const CFGBlock *block); const CFGBlock *dequeue(); }; } void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { const CFGBlock *Successor = *I; if (!Successor || enqueuedBlocks[Successor->getBlockID()]) continue; worklist.push_back(Successor); enqueuedBlocks[Successor->getBlockID()] = true; } } const CFGBlock *DataflowWorklist::dequeue() { const CFGBlock *B = nullptr; // First dequeue from the worklist. This can represent // updates along backedges that we want propagated as quickly as possible. if (!worklist.empty()) B = worklist.pop_back_val(); // Next dequeue from the initial reverse post order. This is the // theoretical ideal in the presence of no back edges. else if (PO_I != PO_E) { B = *PO_I; ++PO_I; } else { return nullptr; } assert(enqueuedBlocks[B->getBlockID()] == true); enqueuedBlocks[B->getBlockID()] = false; return B; } //------------------------------------------------------------------------====// d303 3 a305 1 classify(CO->getTrueExpr(), C); a309 17 if (const BinaryConditionalOperator *BCO = dyn_cast(E)) { classify(BCO->getFalseExpr(), C); return; } if (const OpaqueValueExpr *OVE = dyn_cast(E)) { classify(OVE->getSourceExpr(), C); return; } if (const BinaryOperator *BO = dyn_cast(E)) { if (BO->getOpcode() == BO_Comma) classify(BO->getRHS(), C); return; } a343 11 // Classify arguments to std::move as used. if (CE->getNumArgs() == 1) { if (FunctionDecl *FD = CE->getDirectCallee()) { if (FD->isInStdNamespace() && FD->getIdentifier() && FD->getIdentifier()->isStr("move")) { classify(CE->getArg(0), Use); return; } } } d774 1 a774 1 DataflowWorklist worklist(cfg, *ac.getAnalysis()); @ 1.1.1.6 log @Import Clang 3.8.0rc3 r261930. @ text @a16 1 #include "clang/AST/DeclCXX.h" d38 1 a38 1 !vd->isImplicit() && vd->getDeclContext() == dc) { d40 1 a40 1 return ty->isScalarType() || ty->isVectorType() || ty->isRecordType(); a349 1 if (VD->getType()->isRecordType()) return nullptr; a378 8 if (const MemberExpr *ME = dyn_cast(E)) { if (VarDecl *VD = dyn_cast(ME->getMemberDecl())) { if (!VD->isStaticDataMember()) classify(ME->getBase(), C); } return; } d380 1 a380 6 switch (BO->getOpcode()) { case BO_PtrMemD: case BO_PtrMemI: classify(BO->getLHS(), C); return; case BO_Comma: d382 1 a382 4 return; default: return; } d407 1 a407 1 else if (BO->getOpcode() == BO_Assign || BO->getOpcode() == BO_Comma) a417 4 static bool isPointerToConst(const QualType &QT) { return QT->isAnyPointerType() && QT->getPointeeType().isConstQualified(); } d424 1 a424 3 // RecordTypes are handled in SemaDeclCXX.cpp. if (!CE->getArg(0)->getType()->isRecordType()) classify(CE->getArg(0), Use); d430 3 a432 3 // If a value is passed by const pointer or by const reference to a function, // we should not assume that it is initialized by the call, and we // conservatively do not assume that it is used. d434 3 a436 12 I != E; ++I) { if ((*I)->isGLValue()) { if ((*I)->getType().isConstQualified()) classify((*I), Ignore); } else if (isPointerToConst((*I)->getType())) { const Expr *Ex = stripCasts(DC->getParentASTContext(), *I); const UnaryOperator *UO = dyn_cast(Ex); if (UO && UO->getOpcode() == UO_AddrOf) Ex = UO->getSubExpr(); classify(Ex, Ignore); } } d807 1 a807 1 ~PruneBlocksHandler() override {} @ 1.1.1.6.2.1 log @Sync with HEAD @ text @d351 1 a351 2 if (VD->getType()->isRecordType()) return nullptr; @ 1.1.1.7 log @Import Clang pre-4.0.0 r291444. @ text @d351 1 a351 2 if (VD->getType()->isRecordType()) return nullptr; @ 1.1.1.7.14.1 log @Sync with HEAD @ text @d1 1 a1 1 //===- UninitializedValues.cpp - Find Uninitialized Values ----------------===// d14 1 a14 1 #include "clang/Analysis/Analyses/UninitializedValues.h" d17 1 a17 5 #include "clang/AST/DeclBase.h" #include "clang/AST/Expr.h" #include "clang/AST/OperationKinds.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtObjC.h" a18 1 #include "clang/AST/Type.h" d20 2 a21 1 #include "clang/Analysis/AnalysisDeclContext.h" a23 2 #include "clang/Basic/LLVM.h" #include "llvm/ADT/BitVector.h" a24 1 #include "llvm/ADT/None.h" d29 2 a30 3 #include "llvm/Support/Casting.h" #include #include a50 1 a52 1 d54 1 a54 1 DeclToIndex() = default; d65 1 a65 2 } // namespace a98 1 d105 1 a105 1 using ValueVector = llvm::PackedVector; a111 1 a117 1 d141 1 a141 2 } // namespace d153 2 a154 2 for (auto &val : vals) val.resize(decls); d161 3 a163 2 for (const auto &i : bv) llvm::errs() << ' ' << i; a206 1 a210 1 d213 9 a221 9 : PO_I(view.begin()), PO_E(view.end()), enqueuedBlocks(cfg.getNumBlockIDs(), true) { // Treat the first block as already analyzed. if (PO_I != PO_E) { assert(*PO_I == &cfg.getEntry()); enqueuedBlocks[(*PO_I)->getBlockID()] = false; ++PO_I; } } d226 1 d228 1 a228 3 } // namespace void DataflowWorklist::enqueueSuccessors(const CFGBlock *block) { d253 1 a253 1 else d255 1 a266 1 a269 1 a276 2 } // namespace d280 1 a280 1 if (const auto *CE = dyn_cast(Ex)) { d294 3 a296 3 if (const auto *DRE = dyn_cast(stripCasts(DC->getParentASTContext(), E))) if (const auto *VD = dyn_cast(DRE->getDecl())) d302 1 a302 3 namespace { /// Classify each DeclRefExpr as an initialization or a use. Any d316 1 a316 1 llvm::DenseMap Classification; d341 1 a341 1 const auto *VD = dyn_cast(DRE->getDecl()); d348 1 a348 2 } // namespace d354 2 a355 2 const auto *DRE = dyn_cast(stripCasts(VD->getASTContext(), Init)); d365 1 a365 1 if (const auto *CO = dyn_cast(E)) { d371 2 a372 1 if (const auto *BCO = dyn_cast(E)) { d377 1 a377 1 if (const auto *OVE = dyn_cast(E)) { d382 2 a383 2 if (const auto *ME = dyn_cast(E)) { if (const auto *VD = dyn_cast(ME->getMemberDecl())) { d390 1 a390 1 if (const auto *BO = dyn_cast(E)) { d411 1 a411 1 auto *VD = dyn_cast(DI); d443 10 a452 5 if (CE->isCallToStdMove()) { // RecordTypes are handled in SemaDeclCXX.cpp. if (!CE->getArg(0)->getType()->isRecordType()) classify(CE->getArg(0), Use); return; d465 1 a465 1 const auto *UO = dyn_cast(Ex); d476 1 a476 1 else if (const auto *CSE = dyn_cast(CE)) { a490 1 d505 3 a507 3 : vals(vals), cfg(cfg), block(block), ac(ac), classification(classification), objCNoRet(ac.getASTContext()), handler(handler) {} d635 2 a636 1 for (const auto *Block : cfg) { d676 1 a676 2 } // namespace d686 2 a687 2 if (const auto *DS = dyn_cast(FS->getElement())) { const auto *VD = cast(DS->getSingleDecl()); d756 1 a756 1 auto *VD = dyn_cast(DI); d823 4 a826 3 for (const auto &I : *block) { if (Optional cs = I.getAs()) tf.Visit(const_cast(cs->getStmt())); a830 2 namespace { d835 1 d837 6 d847 1 a847 1 bool hadAnyUse = false; d850 1 a850 5 unsigned currentBlock = 0; PruneBlocksHandler(unsigned numBlocks) : hadUse(numBlocks, false) {} ~PruneBlocksHandler() override = default; d866 1 a866 2 } // namespace d889 1 a889 1 for (unsigned j = 0; j < n; ++j) { d917 2 a918 1 for (const auto *block : cfg) d923 1 d926 1 a926 1 UninitVariablesHandler::~UninitVariablesHandler() = default; @ 1.1.1.7.14.2 log @Mostly merge changes from HEAD upto 20200411 @ text @@ 1.1.1.7.12.1 log @Sync with HEAD @ text @d1 1 a1 1 //===- UninitializedValues.cpp - Find Uninitialized Values ----------------===// d14 1 a14 1 #include "clang/Analysis/Analyses/UninitializedValues.h" d17 1 a17 5 #include "clang/AST/DeclBase.h" #include "clang/AST/Expr.h" #include "clang/AST/OperationKinds.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtObjC.h" a18 1 #include "clang/AST/Type.h" d20 2 a21 1 #include "clang/Analysis/AnalysisDeclContext.h" a23 2 #include "clang/Basic/LLVM.h" #include "llvm/ADT/BitVector.h" a24 1 #include "llvm/ADT/None.h" d29 2 a30 3 #include "llvm/Support/Casting.h" #include #include a50 1 a52 1 d54 1 a54 1 DeclToIndex() = default; d65 1 a65 2 } // namespace a98 1 d105 1 a105 1 using ValueVector = llvm::PackedVector; a111 1 a117 1 d141 1 a141 2 } // namespace d153 2 a154 2 for (auto &val : vals) val.resize(decls); d161 3 a163 2 for (const auto &i : bv) llvm::errs() << ' ' << i; a206 1 a210 1 d213 9 a221 9 : PO_I(view.begin()), PO_E(view.end()), enqueuedBlocks(cfg.getNumBlockIDs(), true) { // Treat the first block as already analyzed. if (PO_I != PO_E) { assert(*PO_I == &cfg.getEntry()); enqueuedBlocks[(*PO_I)->getBlockID()] = false; ++PO_I; } } d226 1 d228 1 a228 3 } // namespace void DataflowWorklist::enqueueSuccessors(const CFGBlock *block) { d253 1 a253 1 else d255 1 a266 1 a269 1 a276 2 } // namespace d280 1 a280 1 if (const auto *CE = dyn_cast(Ex)) { d294 3 a296 3 if (const auto *DRE = dyn_cast(stripCasts(DC->getParentASTContext(), E))) if (const auto *VD = dyn_cast(DRE->getDecl())) d302 1 a302 3 namespace { /// Classify each DeclRefExpr as an initialization or a use. Any d316 1 a316 1 llvm::DenseMap Classification; d341 1 a341 1 const auto *VD = dyn_cast(DRE->getDecl()); d348 1 a348 2 } // namespace d354 2 a355 2 const auto *DRE = dyn_cast(stripCasts(VD->getASTContext(), Init)); d365 1 a365 1 if (const auto *CO = dyn_cast(E)) { d371 2 a372 1 if (const auto *BCO = dyn_cast(E)) { d377 1 a377 1 if (const auto *OVE = dyn_cast(E)) { d382 2 a383 2 if (const auto *ME = dyn_cast(E)) { if (const auto *VD = dyn_cast(ME->getMemberDecl())) { d390 1 a390 1 if (const auto *BO = dyn_cast(E)) { d411 1 a411 1 auto *VD = dyn_cast(DI); d443 10 a452 5 if (CE->isCallToStdMove()) { // RecordTypes are handled in SemaDeclCXX.cpp. if (!CE->getArg(0)->getType()->isRecordType()) classify(CE->getArg(0), Use); return; d465 1 a465 1 const auto *UO = dyn_cast(Ex); d476 1 a476 1 else if (const auto *CSE = dyn_cast(CE)) { a490 1 d505 3 a507 3 : vals(vals), cfg(cfg), block(block), ac(ac), classification(classification), objCNoRet(ac.getASTContext()), handler(handler) {} d635 2 a636 1 for (const auto *Block : cfg) { d676 1 a676 2 } // namespace d686 2 a687 2 if (const auto *DS = dyn_cast(FS->getElement())) { const auto *VD = cast(DS->getSingleDecl()); d756 1 a756 1 auto *VD = dyn_cast(DI); d823 4 a826 3 for (const auto &I : *block) { if (Optional cs = I.getAs()) tf.Visit(const_cast(cs->getStmt())); a830 2 namespace { d835 1 d837 6 d847 1 a847 1 bool hadAnyUse = false; d850 1 a850 5 unsigned currentBlock = 0; PruneBlocksHandler(unsigned numBlocks) : hadUse(numBlocks, false) {} ~PruneBlocksHandler() override = default; d866 1 a866 2 } // namespace d889 1 a889 1 for (unsigned j = 0; j < n; ++j) { d917 2 a918 1 for (const auto *block : cfg) d923 1 d926 1 a926 1 UninitVariablesHandler::~UninitVariablesHandler() = default; @ 1.1.1.8 log @Import clang r337282 from trunk @ text @d1 1 a1 1 //===- UninitializedValues.cpp - Find Uninitialized Values ----------------===// d14 1 a14 1 #include "clang/Analysis/Analyses/UninitializedValues.h" d17 1 a17 5 #include "clang/AST/DeclBase.h" #include "clang/AST/Expr.h" #include "clang/AST/OperationKinds.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtObjC.h" a18 1 #include "clang/AST/Type.h" d20 2 a21 1 #include "clang/Analysis/AnalysisDeclContext.h" a23 2 #include "clang/Basic/LLVM.h" #include "llvm/ADT/BitVector.h" a24 1 #include "llvm/ADT/None.h" d29 2 a30 3 #include "llvm/Support/Casting.h" #include #include a50 1 a52 1 d54 1 a54 1 DeclToIndex() = default; d65 1 a65 2 } // namespace a98 1 d105 1 a105 1 using ValueVector = llvm::PackedVector; a111 1 a117 1 d141 1 a141 2 } // namespace d153 2 a154 2 for (auto &val : vals) val.resize(decls); d161 3 a163 2 for (const auto &i : bv) llvm::errs() << ' ' << i; a206 1 a210 1 d213 9 a221 9 : PO_I(view.begin()), PO_E(view.end()), enqueuedBlocks(cfg.getNumBlockIDs(), true) { // Treat the first block as already analyzed. if (PO_I != PO_E) { assert(*PO_I == &cfg.getEntry()); enqueuedBlocks[(*PO_I)->getBlockID()] = false; ++PO_I; } } d226 1 d228 1 a228 3 } // namespace void DataflowWorklist::enqueueSuccessors(const CFGBlock *block) { d253 1 a253 1 else d255 1 a266 1 a269 1 a276 2 } // namespace d280 1 a280 1 if (const auto *CE = dyn_cast(Ex)) { d294 3 a296 3 if (const auto *DRE = dyn_cast(stripCasts(DC->getParentASTContext(), E))) if (const auto *VD = dyn_cast(DRE->getDecl())) d302 1 a302 3 namespace { /// Classify each DeclRefExpr as an initialization or a use. Any d316 1 a316 1 llvm::DenseMap Classification; d341 1 a341 1 const auto *VD = dyn_cast(DRE->getDecl()); d348 1 a348 2 } // namespace d354 2 a355 2 const auto *DRE = dyn_cast(stripCasts(VD->getASTContext(), Init)); d365 1 a365 1 if (const auto *CO = dyn_cast(E)) { d371 2 a372 1 if (const auto *BCO = dyn_cast(E)) { d377 1 a377 1 if (const auto *OVE = dyn_cast(E)) { d382 2 a383 2 if (const auto *ME = dyn_cast(E)) { if (const auto *VD = dyn_cast(ME->getMemberDecl())) { d390 1 a390 1 if (const auto *BO = dyn_cast(E)) { d411 1 a411 1 auto *VD = dyn_cast(DI); d443 10 a452 5 if (CE->isCallToStdMove()) { // RecordTypes are handled in SemaDeclCXX.cpp. if (!CE->getArg(0)->getType()->isRecordType()) classify(CE->getArg(0), Use); return; d465 1 a465 1 const auto *UO = dyn_cast(Ex); d476 1 a476 1 else if (const auto *CSE = dyn_cast(CE)) { a490 1 d505 3 a507 3 : vals(vals), cfg(cfg), block(block), ac(ac), classification(classification), objCNoRet(ac.getASTContext()), handler(handler) {} d635 2 a636 1 for (const auto *Block : cfg) { d676 1 a676 2 } // namespace d686 2 a687 2 if (const auto *DS = dyn_cast(FS->getElement())) { const auto *VD = cast(DS->getSingleDecl()); d756 1 a756 1 auto *VD = dyn_cast(DI); d823 4 a826 3 for (const auto &I : *block) { if (Optional cs = I.getAs()) tf.Visit(const_cast(cs->getStmt())); a830 2 namespace { d835 1 d837 6 d847 1 a847 1 bool hadAnyUse = false; d850 1 a850 5 unsigned currentBlock = 0; PruneBlocksHandler(unsigned numBlocks) : hadUse(numBlocks, false) {} ~PruneBlocksHandler() override = default; d866 1 a866 2 } // namespace d889 1 a889 1 for (unsigned j = 0; j < n; ++j) { d917 2 a918 1 for (const auto *block : cfg) d923 1 d926 1 a926 1 UninitVariablesHandler::~UninitVariablesHandler() = default; @ 1.1.1.9 log @Mark old LLVM instance as dead. @ text @@ 1.1.1.4.4.1 log @file UninitializedValues.cpp was added on branch tls-maxphys on 2014-08-19 23:47:26 +0000 @ text @d1 806 @ 1.1.1.4.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 806 //==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements uninitialized values analysis for source-level CFGs. // //===----------------------------------------------------------------------===// #include "clang/AST/ASTContext.h" #include "clang/AST/Attr.h" #include "clang/AST/Decl.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/DataflowWorklist.h" #include "clang/Analysis/Analyses/UninitializedValues.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/PackedVector.h" #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/SaveAndRestore.h" #include using namespace clang; #define DEBUG_LOGGING 0 static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && !vd->isExceptionVariable() && !vd->isInitCapture() && vd->getDeclContext() == dc) { QualType ty = vd->getType(); return ty->isScalarType() || ty->isVectorType(); } return false; } //------------------------------------------------------------------------====// // DeclToIndex: a mapping from Decls we track to value indices. //====------------------------------------------------------------------------// namespace { class DeclToIndex { llvm::DenseMap map; public: DeclToIndex() {} /// Compute the actual mapping from declarations to bits. void computeMap(const DeclContext &dc); /// Return the number of declarations in the map. unsigned size() const { return map.size(); } /// Returns the bit vector index for a given declaration. Optional getValueIndex(const VarDecl *d) const; }; } void DeclToIndex::computeMap(const DeclContext &dc) { unsigned count = 0; DeclContext::specific_decl_iterator I(dc.decls_begin()), E(dc.decls_end()); for ( ; I != E; ++I) { const VarDecl *vd = *I; if (isTrackedVar(vd, &dc)) map[vd] = count++; } } Optional DeclToIndex::getValueIndex(const VarDecl *d) const { llvm::DenseMap::const_iterator I = map.find(d); if (I == map.end()) return None; return I->second; } //------------------------------------------------------------------------====// // CFGBlockValues: dataflow values for CFG blocks. //====------------------------------------------------------------------------// // These values are defined in such a way that a merge can be done using // a bitwise OR. enum Value { Unknown = 0x0, /* 00 */ Initialized = 0x1, /* 01 */ Uninitialized = 0x2, /* 10 */ MayUninitialized = 0x3 /* 11 */ }; static bool isUninitialized(const Value v) { return v >= Uninitialized; } static bool isAlwaysUninit(const Value v) { return v == Uninitialized; } namespace { typedef llvm::PackedVector ValueVector; class CFGBlockValues { const CFG &cfg; SmallVector vals; ValueVector scratch; DeclToIndex declToIndex; public: CFGBlockValues(const CFG &cfg); unsigned getNumEntries() const { return declToIndex.size(); } void computeSetOfDeclarations(const DeclContext &dc); ValueVector &getValueVector(const CFGBlock *block) { return vals[block->getBlockID()]; } void setAllScratchValues(Value V); void mergeIntoScratch(ValueVector const &source, bool isFirst); bool updateValueVectorWithScratch(const CFGBlock *block); bool hasNoDeclarations() const { return declToIndex.size() == 0; } void resetScratch(); ValueVector::reference operator[](const VarDecl *vd); Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, const VarDecl *vd) { const Optional &idx = declToIndex.getValueIndex(vd); assert(idx.hasValue()); return getValueVector(block)[idx.getValue()]; } }; } // end anonymous namespace CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { declToIndex.computeMap(dc); unsigned decls = declToIndex.size(); scratch.resize(decls); unsigned n = cfg.getNumBlockIDs(); if (!n) return; vals.resize(n); for (unsigned i = 0; i < n; ++i) vals[i].resize(decls); } #if DEBUG_LOGGING static void printVector(const CFGBlock *block, ValueVector &bv, unsigned num) { llvm::errs() << block->getBlockID() << " :"; for (unsigned i = 0; i < bv.size(); ++i) { llvm::errs() << ' ' << bv[i]; } llvm::errs() << " : " << num << '\n'; } #endif void CFGBlockValues::setAllScratchValues(Value V) { for (unsigned I = 0, E = scratch.size(); I != E; ++I) scratch[I] = V; } void CFGBlockValues::mergeIntoScratch(ValueVector const &source, bool isFirst) { if (isFirst) scratch = source; else scratch |= source; } bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { ValueVector &dst = getValueVector(block); bool changed = (dst != scratch); if (changed) dst = scratch; #if DEBUG_LOGGING printVector(block, scratch, 0); #endif return changed; } void CFGBlockValues::resetScratch() { scratch.reset(); } ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { const Optional &idx = declToIndex.getValueIndex(vd); assert(idx.hasValue()); return scratch[idx.getValue()]; } //------------------------------------------------------------------------====// // Classification of DeclRefExprs as use or initialization. //====------------------------------------------------------------------------// namespace { class FindVarResult { const VarDecl *vd; const DeclRefExpr *dr; public: FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} const DeclRefExpr *getDeclRefExpr() const { return dr; } const VarDecl *getDecl() const { return vd; } }; static const Expr *stripCasts(ASTContext &C, const Expr *Ex) { while (Ex) { Ex = Ex->IgnoreParenNoopCasts(C); if (const CastExpr *CE = dyn_cast(Ex)) { if (CE->getCastKind() == CK_LValueBitCast) { Ex = CE->getSubExpr(); continue; } } break; } return Ex; } /// If E is an expression comprising a reference to a single variable, find that /// variable. static FindVarResult findVar(const Expr *E, const DeclContext *DC) { if (const DeclRefExpr *DRE = dyn_cast(stripCasts(DC->getParentASTContext(), E))) if (const VarDecl *VD = dyn_cast(DRE->getDecl())) if (isTrackedVar(VD, DC)) return FindVarResult(VD, DRE); return FindVarResult(nullptr, nullptr); } /// \brief Classify each DeclRefExpr as an initialization or a use. Any /// DeclRefExpr which isn't explicitly classified will be assumed to have /// escaped the analysis and will be treated as an initialization. class ClassifyRefs : public StmtVisitor { public: enum Class { Init, Use, SelfInit, Ignore }; private: const DeclContext *DC; llvm::DenseMap Classification; bool isTrackedVar(const VarDecl *VD) const { return ::isTrackedVar(VD, DC); } void classify(const Expr *E, Class C); public: ClassifyRefs(AnalysisDeclContext &AC) : DC(cast(AC.getDecl())) {} void VisitDeclStmt(DeclStmt *DS); void VisitUnaryOperator(UnaryOperator *UO); void VisitBinaryOperator(BinaryOperator *BO); void VisitCallExpr(CallExpr *CE); void VisitCastExpr(CastExpr *CE); void operator()(Stmt *S) { Visit(S); } Class get(const DeclRefExpr *DRE) const { llvm::DenseMap::const_iterator I = Classification.find(DRE); if (I != Classification.end()) return I->second; const VarDecl *VD = dyn_cast(DRE->getDecl()); if (!VD || !isTrackedVar(VD)) return Ignore; return Init; } }; } static const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { if (Expr *Init = VD->getInit()) { const DeclRefExpr *DRE = dyn_cast(stripCasts(VD->getASTContext(), Init)); if (DRE && DRE->getDecl() == VD) return DRE; } return nullptr; } void ClassifyRefs::classify(const Expr *E, Class C) { // The result of a ?: could also be an lvalue. E = E->IgnoreParens(); if (const ConditionalOperator *CO = dyn_cast(E)) { const Expr *TrueExpr = CO->getTrueExpr(); if (!isa(TrueExpr)) classify(TrueExpr, C); classify(CO->getFalseExpr(), C); return; } FindVarResult Var = findVar(E, DC); if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) Classification[DRE] = std::max(Classification[DRE], C); } void ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { for (auto *DI : DS->decls()) { VarDecl *VD = dyn_cast(DI); if (VD && isTrackedVar(VD)) if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) Classification[DRE] = SelfInit; } } void ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this // is not a compound-assignment, we will treat it as initializing the variable // when TransferFunctions visits it. A compound-assignment does not affect // whether a variable is uninitialized, and there's no point counting it as a // use. if (BO->isCompoundAssignmentOp()) classify(BO->getLHS(), Use); else if (BO->getOpcode() == BO_Assign) classify(BO->getLHS(), Ignore); } void ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { // Increment and decrement are uses despite there being no lvalue-to-rvalue // conversion. if (UO->isIncrementDecrementOp()) classify(UO->getSubExpr(), Use); } void ClassifyRefs::VisitCallExpr(CallExpr *CE) { // If a value is passed by const reference to a function, we should not assume // that it is initialized by the call, and we conservatively do not assume // that it is used. for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); I != E; ++I) if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) classify(*I, Ignore); } void ClassifyRefs::VisitCastExpr(CastExpr *CE) { if (CE->getCastKind() == CK_LValueToRValue) classify(CE->getSubExpr(), Use); else if (CStyleCastExpr *CSE = dyn_cast(CE)) { if (CSE->getType()->isVoidType()) { // Squelch any detected load of an uninitialized value if // we cast it to void. // e.g. (void) x; classify(CSE->getSubExpr(), Ignore); } } } //------------------------------------------------------------------------====// // Transfer function for uninitialized values analysis. //====------------------------------------------------------------------------// namespace { class TransferFunctions : public StmtVisitor { CFGBlockValues &vals; const CFG &cfg; const CFGBlock *block; AnalysisDeclContext ∾ const ClassifyRefs &classification; ObjCNoReturn objCNoRet; UninitVariablesHandler &handler; public: TransferFunctions(CFGBlockValues &vals, const CFG &cfg, const CFGBlock *block, AnalysisDeclContext &ac, const ClassifyRefs &classification, UninitVariablesHandler &handler) : vals(vals), cfg(cfg), block(block), ac(ac), classification(classification), objCNoRet(ac.getASTContext()), handler(handler) {} void reportUse(const Expr *ex, const VarDecl *vd); void VisitBinaryOperator(BinaryOperator *bo); void VisitBlockExpr(BlockExpr *be); void VisitCallExpr(CallExpr *ce); void VisitDeclRefExpr(DeclRefExpr *dr); void VisitDeclStmt(DeclStmt *ds); void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); void VisitObjCMessageExpr(ObjCMessageExpr *ME); bool isTrackedVar(const VarDecl *vd) { return ::isTrackedVar(vd, cast(ac.getDecl())); } FindVarResult findVar(const Expr *ex) { return ::findVar(ex, cast(ac.getDecl())); } UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { UninitUse Use(ex, isAlwaysUninit(v)); assert(isUninitialized(v)); if (Use.getKind() == UninitUse::Always) return Use; // If an edge which leads unconditionally to this use did not initialize // the variable, we can say something stronger than 'may be uninitialized': // we can say 'either it's used uninitialized or you have dead code'. // // We track the number of successors of a node which have been visited, and // visit a node once we have visited all of its successors. Only edges where // the variable might still be uninitialized are followed. Since a variable // can't transfer from being initialized to being uninitialized, this will // trace out the subgraph which inevitably leads to the use and does not // initialize the variable. We do not want to skip past loops, since their // non-termination might be correlated with the initialization condition. // // For example: // // void f(bool a, bool b) { // block1: int n; // if (a) { // block2: if (b) // block3: n = 1; // block4: } else if (b) { // block5: while (!a) { // block6: do_work(&a); // n = 2; // } // } // block7: if (a) // block8: g(); // block9: return n; // } // // Starting from the maybe-uninitialized use in block 9: // * Block 7 is not visited because we have only visited one of its two // successors. // * Block 8 is visited because we've visited its only successor. // From block 8: // * Block 7 is visited because we've now visited both of its successors. // From block 7: // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). // * Block 3 is not visited because it initializes 'n'. // Now the algorithm terminates, having visited blocks 7 and 8, and having // found the frontier is blocks 2, 4, and 5. // // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 // and 4), so we report that any time either of those edges is taken (in // each case when 'b == false'), 'n' is used uninitialized. SmallVector Queue; SmallVector SuccsVisited(cfg.getNumBlockIDs(), 0); Queue.push_back(block); // Specify that we've already visited all successors of the starting block. // This has the dual purpose of ensuring we never add it to the queue, and // of marking it as not being a candidate element of the frontier. SuccsVisited[block->getBlockID()] = block->succ_size(); while (!Queue.empty()) { const CFGBlock *B = Queue.pop_back_val(); // If the use is always reached from the entry block, make a note of that. if (B == &cfg.getEntry()) Use.setUninitAfterCall(); for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); I != E; ++I) { const CFGBlock *Pred = *I; if (!Pred) continue; Value AtPredExit = vals.getValue(Pred, B, vd); if (AtPredExit == Initialized) // This block initializes the variable. continue; if (AtPredExit == MayUninitialized && vals.getValue(B, nullptr, vd) == Uninitialized) { // This block declares the variable (uninitialized), and is reachable // from a block that initializes the variable. We can't guarantee to // give an earlier location for the diagnostic (and it appears that // this code is intended to be reachable) so give a diagnostic here // and go no further down this path. Use.setUninitAfterDecl(); continue; } unsigned &SV = SuccsVisited[Pred->getBlockID()]; if (!SV) { // When visiting the first successor of a block, mark all NULL // successors as having been visited. for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), SE = Pred->succ_end(); SI != SE; ++SI) if (!*SI) ++SV; } if (++SV == Pred->succ_size()) // All paths from this block lead to the use and don't initialize the // variable. Queue.push_back(Pred); } } // Scan the frontier, looking for blocks where the variable was // uninitialized. for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { const CFGBlock *Block = *BI; unsigned BlockID = Block->getBlockID(); const Stmt *Term = Block->getTerminator(); if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && Term) { // This block inevitably leads to the use. If we have an edge from here // to a post-dominator block, and the variable is uninitialized on that // edge, we have found a bug. for (CFGBlock::const_succ_iterator I = Block->succ_begin(), E = Block->succ_end(); I != E; ++I) { const CFGBlock *Succ = *I; if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && vals.getValue(Block, Succ, vd) == Uninitialized) { // Switch cases are a special case: report the label to the caller // as the 'terminator', not the switch statement itself. Suppress // situations where no label matched: we can't be sure that's // possible. if (isa(Term)) { const Stmt *Label = Succ->getLabel(); if (!Label || !isa(Label)) // Might not be possible. continue; UninitUse::Branch Branch; Branch.Terminator = Label; Branch.Output = 0; // Ignored. Use.addUninitBranch(Branch); } else { UninitUse::Branch Branch; Branch.Terminator = Term; Branch.Output = I - Block->succ_begin(); Use.addUninitBranch(Branch); } } } } } return Use; } }; } void TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { Value v = vals[vd]; if (isUninitialized(v)) handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); } void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { // This represents an initialization of the 'element' value. if (DeclStmt *DS = dyn_cast(FS->getElement())) { const VarDecl *VD = cast(DS->getSingleDecl()); if (isTrackedVar(VD)) vals[VD] = Initialized; } } void TransferFunctions::VisitBlockExpr(BlockExpr *be) { const BlockDecl *bd = be->getBlockDecl(); for (const auto &I : bd->captures()) { const VarDecl *vd = I.getVariable(); if (!isTrackedVar(vd)) continue; if (I.isByRef()) { vals[vd] = Initialized; continue; } reportUse(be, vd); } } void TransferFunctions::VisitCallExpr(CallExpr *ce) { if (Decl *Callee = ce->getCalleeDecl()) { if (Callee->hasAttr()) { // After a call to a function like setjmp or vfork, any variable which is // initialized anywhere within this function may now be initialized. For // now, just assume such a call initializes all variables. FIXME: Only // mark variables as initialized if they have an initializer which is // reachable from here. vals.setAllScratchValues(Initialized); } else if (Callee->hasAttr()) { // Functions labeled like "analyzer_noreturn" are often used to denote // "panic" functions that in special debug situations can still return, // but for the most part should not be treated as returning. This is a // useful annotation borrowed from the static analyzer that is useful for // suppressing branch-specific false positives when we call one of these // functions but keep pretending the path continues (when in reality the // user doesn't care). vals.setAllScratchValues(Unknown); } } } void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { switch (classification.get(dr)) { case ClassifyRefs::Ignore: break; case ClassifyRefs::Use: reportUse(dr, cast(dr->getDecl())); break; case ClassifyRefs::Init: vals[cast(dr->getDecl())] = Initialized; break; case ClassifyRefs::SelfInit: handler.handleSelfInit(cast(dr->getDecl())); break; } } void TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { if (BO->getOpcode() == BO_Assign) { FindVarResult Var = findVar(BO->getLHS()); if (const VarDecl *VD = Var.getDecl()) vals[VD] = Initialized; } } void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { for (auto *DI : DS->decls()) { VarDecl *VD = dyn_cast(DI); if (VD && isTrackedVar(VD)) { if (getSelfInitExpr(VD)) { // If the initializer consists solely of a reference to itself, we // explicitly mark the variable as uninitialized. This allows code // like the following: // // int x = x; // // to deliberately leave a variable uninitialized. Different analysis // clients can detect this pattern and adjust their reporting // appropriately, but we need to continue to analyze subsequent uses // of the variable. vals[VD] = Uninitialized; } else if (VD->getInit()) { // Treat the new variable as initialized. vals[VD] = Initialized; } else { // No initializer: the variable is now uninitialized. This matters // for cases like: // while (...) { // int n; // use(n); // n = 0; // } // FIXME: Mark the variable as uninitialized whenever its scope is // left, since its scope could be re-entered by a jump over the // declaration. vals[VD] = Uninitialized; } } } } void TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { // If the Objective-C message expression is an implicit no-return that // is not modeled in the CFG, set the tracked dataflow values to Unknown. if (objCNoRet.isImplicitNoReturn(ME)) { vals.setAllScratchValues(Unknown); } } //------------------------------------------------------------------------====// // High-level "driver" logic for uninitialized values analysis. //====------------------------------------------------------------------------// static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler) { wasAnalyzed[block->getBlockID()] = true; vals.resetScratch(); // Merge in values of predecessor blocks. bool isFirst = true; for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { const CFGBlock *pred = *I; if (!pred) continue; if (wasAnalyzed[pred->getBlockID()]) { vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); isFirst = false; } } // Apply the transfer function. TransferFunctions tf(vals, cfg, block, ac, classification, handler); for (CFGBlock::const_iterator I = block->begin(), E = block->end(); I != E; ++I) { if (Optional cs = I->getAs()) tf.Visit(const_cast(cs->getStmt())); } return vals.updateValueVectorWithScratch(block); } /// PruneBlocksHandler is a special UninitVariablesHandler that is used /// to detect when a CFGBlock has any *potential* use of an uninitialized /// variable. It is mainly used to prune out work during the final /// reporting pass. namespace { struct PruneBlocksHandler : public UninitVariablesHandler { PruneBlocksHandler(unsigned numBlocks) : hadUse(numBlocks, false), hadAnyUse(false), currentBlock(0) {} virtual ~PruneBlocksHandler() {} /// Records if a CFGBlock had a potential use of an uninitialized variable. llvm::BitVector hadUse; /// Records if any CFGBlock had a potential use of an uninitialized variable. bool hadAnyUse; /// The current block to scribble use information. unsigned currentBlock; void handleUseOfUninitVariable(const VarDecl *vd, const UninitUse &use) override { hadUse[currentBlock] = true; hadAnyUse = true; } /// Called when the uninitialized variable analysis detects the /// idiom 'int x = x'. All other uses of 'x' within the initializer /// are handled by handleUseOfUninitVariable. void handleSelfInit(const VarDecl *vd) override { hadUse[currentBlock] = true; hadAnyUse = true; } }; } void clang::runUninitializedVariablesAnalysis( const DeclContext &dc, const CFG &cfg, AnalysisDeclContext &ac, UninitVariablesHandler &handler, UninitVariablesAnalysisStats &stats) { CFGBlockValues vals(cfg); vals.computeSetOfDeclarations(dc); if (vals.hasNoDeclarations()) return; stats.NumVariablesAnalyzed = vals.getNumEntries(); // Precompute which expressions are uses and which are initializations. ClassifyRefs classification(ac); cfg.VisitBlockStmts(classification); // Mark all variables uninitialized at the entry. const CFGBlock &entry = cfg.getEntry(); ValueVector &vec = vals.getValueVector(&entry); const unsigned n = vals.getNumEntries(); for (unsigned j = 0; j < n ; ++j) { vec[j] = Uninitialized; } // Proceed with the workist. DataflowWorklist worklist(cfg, ac); llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); worklist.enqueueSuccessors(&cfg.getEntry()); llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); wasAnalyzed[cfg.getEntry().getBlockID()] = true; PruneBlocksHandler PBH(cfg.getNumBlockIDs()); while (const CFGBlock *block = worklist.dequeue()) { PBH.currentBlock = block->getBlockID(); // Did the block change? bool changed = runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, PBH); ++stats.NumBlockVisits; if (changed || !previouslyVisited[block->getBlockID()]) worklist.enqueueSuccessors(block); previouslyVisited[block->getBlockID()] = true; } if (!PBH.hadAnyUse) return; // Run through the blocks one more time, and report uninitialized variables. for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { const CFGBlock *block = *BI; if (PBH.hadUse[block->getBlockID()]) { runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler); ++stats.NumBlockVisits; } } } UninitVariablesHandler::~UninitVariablesHandler() {} @ 1.1.1.2.4.1 log @file UninitializedValues.cpp was added on branch yamt-pagecache on 2014-05-22 16:18:26 +0000 @ text @d1 869 @ 1.1.1.2.4.2 log @sync with head. for a reference, the tree before this commit was tagged as yamt-pagecache-tag8. this commit was splitted into small chunks to avoid a limitation of cvs. ("Protocol error: too many arguments") @ text @a0 869 //==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements uninitialized values analysis for source-level CFGs. // //===----------------------------------------------------------------------===// #include "clang/AST/ASTContext.h" #include "clang/AST/Attr.h" #include "clang/AST/Decl.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/Analyses/UninitializedValues.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/PackedVector.h" #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/SaveAndRestore.h" #include using namespace clang; #define DEBUG_LOGGING 0 static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && !vd->isExceptionVariable() && vd->getDeclContext() == dc) { QualType ty = vd->getType(); return ty->isScalarType() || ty->isVectorType(); } return false; } //------------------------------------------------------------------------====// // DeclToIndex: a mapping from Decls we track to value indices. //====------------------------------------------------------------------------// namespace { class DeclToIndex { llvm::DenseMap map; public: DeclToIndex() {} /// Compute the actual mapping from declarations to bits. void computeMap(const DeclContext &dc); /// Return the number of declarations in the map. unsigned size() const { return map.size(); } /// Returns the bit vector index for a given declaration. Optional getValueIndex(const VarDecl *d) const; }; } void DeclToIndex::computeMap(const DeclContext &dc) { unsigned count = 0; DeclContext::specific_decl_iterator I(dc.decls_begin()), E(dc.decls_end()); for ( ; I != E; ++I) { const VarDecl *vd = *I; if (isTrackedVar(vd, &dc)) map[vd] = count++; } } Optional DeclToIndex::getValueIndex(const VarDecl *d) const { llvm::DenseMap::const_iterator I = map.find(d); if (I == map.end()) return None; return I->second; } //------------------------------------------------------------------------====// // CFGBlockValues: dataflow values for CFG blocks. //====------------------------------------------------------------------------// // These values are defined in such a way that a merge can be done using // a bitwise OR. enum Value { Unknown = 0x0, /* 00 */ Initialized = 0x1, /* 01 */ Uninitialized = 0x2, /* 10 */ MayUninitialized = 0x3 /* 11 */ }; static bool isUninitialized(const Value v) { return v >= Uninitialized; } static bool isAlwaysUninit(const Value v) { return v == Uninitialized; } namespace { typedef llvm::PackedVector ValueVector; class CFGBlockValues { const CFG &cfg; SmallVector vals; ValueVector scratch; DeclToIndex declToIndex; public: CFGBlockValues(const CFG &cfg); unsigned getNumEntries() const { return declToIndex.size(); } void computeSetOfDeclarations(const DeclContext &dc); ValueVector &getValueVector(const CFGBlock *block) { return vals[block->getBlockID()]; } void setAllScratchValues(Value V); void mergeIntoScratch(ValueVector const &source, bool isFirst); bool updateValueVectorWithScratch(const CFGBlock *block); bool hasNoDeclarations() const { return declToIndex.size() == 0; } void resetScratch(); ValueVector::reference operator[](const VarDecl *vd); Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, const VarDecl *vd) { const Optional &idx = declToIndex.getValueIndex(vd); assert(idx.hasValue()); return getValueVector(block)[idx.getValue()]; } }; } // end anonymous namespace CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { declToIndex.computeMap(dc); unsigned decls = declToIndex.size(); scratch.resize(decls); unsigned n = cfg.getNumBlockIDs(); if (!n) return; vals.resize(n); for (unsigned i = 0; i < n; ++i) vals[i].resize(decls); } #if DEBUG_LOGGING static void printVector(const CFGBlock *block, ValueVector &bv, unsigned num) { llvm::errs() << block->getBlockID() << " :"; for (unsigned i = 0; i < bv.size(); ++i) { llvm::errs() << ' ' << bv[i]; } llvm::errs() << " : " << num << '\n'; } #endif void CFGBlockValues::setAllScratchValues(Value V) { for (unsigned I = 0, E = scratch.size(); I != E; ++I) scratch[I] = V; } void CFGBlockValues::mergeIntoScratch(ValueVector const &source, bool isFirst) { if (isFirst) scratch = source; else scratch |= source; } bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { ValueVector &dst = getValueVector(block); bool changed = (dst != scratch); if (changed) dst = scratch; #if DEBUG_LOGGING printVector(block, scratch, 0); #endif return changed; } void CFGBlockValues::resetScratch() { scratch.reset(); } ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { const Optional &idx = declToIndex.getValueIndex(vd); assert(idx.hasValue()); return scratch[idx.getValue()]; } //------------------------------------------------------------------------====// // Worklist: worklist for dataflow analysis. //====------------------------------------------------------------------------// namespace { class DataflowWorklist { PostOrderCFGView::iterator PO_I, PO_E; SmallVector worklist; llvm::BitVector enqueuedBlocks; public: DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) : PO_I(view.begin()), PO_E(view.end()), enqueuedBlocks(cfg.getNumBlockIDs(), true) { // Treat the first block as already analyzed. if (PO_I != PO_E) { assert(*PO_I == &cfg.getEntry()); enqueuedBlocks[(*PO_I)->getBlockID()] = false; ++PO_I; } } void enqueueSuccessors(const CFGBlock *block); const CFGBlock *dequeue(); }; } void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { const CFGBlock *Successor = *I; if (!Successor || enqueuedBlocks[Successor->getBlockID()]) continue; worklist.push_back(Successor); enqueuedBlocks[Successor->getBlockID()] = true; } } const CFGBlock *DataflowWorklist::dequeue() { const CFGBlock *B = 0; // First dequeue from the worklist. This can represent // updates along backedges that we want propagated as quickly as possible. if (!worklist.empty()) B = worklist.pop_back_val(); // Next dequeue from the initial reverse post order. This is the // theoretical ideal in the presence of no back edges. else if (PO_I != PO_E) { B = *PO_I; ++PO_I; } else { return 0; } assert(enqueuedBlocks[B->getBlockID()] == true); enqueuedBlocks[B->getBlockID()] = false; return B; } //------------------------------------------------------------------------====// // Classification of DeclRefExprs as use or initialization. //====------------------------------------------------------------------------// namespace { class FindVarResult { const VarDecl *vd; const DeclRefExpr *dr; public: FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} const DeclRefExpr *getDeclRefExpr() const { return dr; } const VarDecl *getDecl() const { return vd; } }; static const Expr *stripCasts(ASTContext &C, const Expr *Ex) { while (Ex) { Ex = Ex->IgnoreParenNoopCasts(C); if (const CastExpr *CE = dyn_cast(Ex)) { if (CE->getCastKind() == CK_LValueBitCast) { Ex = CE->getSubExpr(); continue; } } break; } return Ex; } /// If E is an expression comprising a reference to a single variable, find that /// variable. static FindVarResult findVar(const Expr *E, const DeclContext *DC) { if (const DeclRefExpr *DRE = dyn_cast(stripCasts(DC->getParentASTContext(), E))) if (const VarDecl *VD = dyn_cast(DRE->getDecl())) if (isTrackedVar(VD, DC)) return FindVarResult(VD, DRE); return FindVarResult(0, 0); } /// \brief Classify each DeclRefExpr as an initialization or a use. Any /// DeclRefExpr which isn't explicitly classified will be assumed to have /// escaped the analysis and will be treated as an initialization. class ClassifyRefs : public StmtVisitor { public: enum Class { Init, Use, SelfInit, Ignore }; private: const DeclContext *DC; llvm::DenseMap Classification; bool isTrackedVar(const VarDecl *VD) const { return ::isTrackedVar(VD, DC); } void classify(const Expr *E, Class C); public: ClassifyRefs(AnalysisDeclContext &AC) : DC(cast(AC.getDecl())) {} void VisitDeclStmt(DeclStmt *DS); void VisitUnaryOperator(UnaryOperator *UO); void VisitBinaryOperator(BinaryOperator *BO); void VisitCallExpr(CallExpr *CE); void VisitCastExpr(CastExpr *CE); void operator()(Stmt *S) { Visit(S); } Class get(const DeclRefExpr *DRE) const { llvm::DenseMap::const_iterator I = Classification.find(DRE); if (I != Classification.end()) return I->second; const VarDecl *VD = dyn_cast(DRE->getDecl()); if (!VD || !isTrackedVar(VD)) return Ignore; return Init; } }; } static const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { if (Expr *Init = VD->getInit()) { const DeclRefExpr *DRE = dyn_cast(stripCasts(VD->getASTContext(), Init)); if (DRE && DRE->getDecl() == VD) return DRE; } return 0; } void ClassifyRefs::classify(const Expr *E, Class C) { // The result of a ?: could also be an lvalue. E = E->IgnoreParens(); if (const ConditionalOperator *CO = dyn_cast(E)) { const Expr *TrueExpr = CO->getTrueExpr(); if (!isa(TrueExpr)) classify(TrueExpr, C); classify(CO->getFalseExpr(), C); return; } FindVarResult Var = findVar(E, DC); if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) Classification[DRE] = std::max(Classification[DRE], C); } void ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); DI != DE; ++DI) { VarDecl *VD = dyn_cast(*DI); if (VD && isTrackedVar(VD)) if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) Classification[DRE] = SelfInit; } } void ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this // is not a compound-assignment, we will treat it as initializing the variable // when TransferFunctions visits it. A compound-assignment does not affect // whether a variable is uninitialized, and there's no point counting it as a // use. if (BO->isCompoundAssignmentOp()) classify(BO->getLHS(), Use); else if (BO->getOpcode() == BO_Assign) classify(BO->getLHS(), Ignore); } void ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { // Increment and decrement are uses despite there being no lvalue-to-rvalue // conversion. if (UO->isIncrementDecrementOp()) classify(UO->getSubExpr(), Use); } void ClassifyRefs::VisitCallExpr(CallExpr *CE) { // If a value is passed by const reference to a function, we should not assume // that it is initialized by the call, and we conservatively do not assume // that it is used. for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); I != E; ++I) if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) classify(*I, Ignore); } void ClassifyRefs::VisitCastExpr(CastExpr *CE) { if (CE->getCastKind() == CK_LValueToRValue) classify(CE->getSubExpr(), Use); else if (CStyleCastExpr *CSE = dyn_cast(CE)) { if (CSE->getType()->isVoidType()) { // Squelch any detected load of an uninitialized value if // we cast it to void. // e.g. (void) x; classify(CSE->getSubExpr(), Ignore); } } } //------------------------------------------------------------------------====// // Transfer function for uninitialized values analysis. //====------------------------------------------------------------------------// namespace { class TransferFunctions : public StmtVisitor { CFGBlockValues &vals; const CFG &cfg; const CFGBlock *block; AnalysisDeclContext ∾ const ClassifyRefs &classification; ObjCNoReturn objCNoRet; UninitVariablesHandler &handler; public: TransferFunctions(CFGBlockValues &vals, const CFG &cfg, const CFGBlock *block, AnalysisDeclContext &ac, const ClassifyRefs &classification, UninitVariablesHandler &handler) : vals(vals), cfg(cfg), block(block), ac(ac), classification(classification), objCNoRet(ac.getASTContext()), handler(handler) {} void reportUse(const Expr *ex, const VarDecl *vd); void VisitBinaryOperator(BinaryOperator *bo); void VisitBlockExpr(BlockExpr *be); void VisitCallExpr(CallExpr *ce); void VisitDeclRefExpr(DeclRefExpr *dr); void VisitDeclStmt(DeclStmt *ds); void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); void VisitObjCMessageExpr(ObjCMessageExpr *ME); bool isTrackedVar(const VarDecl *vd) { return ::isTrackedVar(vd, cast(ac.getDecl())); } FindVarResult findVar(const Expr *ex) { return ::findVar(ex, cast(ac.getDecl())); } UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { UninitUse Use(ex, isAlwaysUninit(v)); assert(isUninitialized(v)); if (Use.getKind() == UninitUse::Always) return Use; // If an edge which leads unconditionally to this use did not initialize // the variable, we can say something stronger than 'may be uninitialized': // we can say 'either it's used uninitialized or you have dead code'. // // We track the number of successors of a node which have been visited, and // visit a node once we have visited all of its successors. Only edges where // the variable might still be uninitialized are followed. Since a variable // can't transfer from being initialized to being uninitialized, this will // trace out the subgraph which inevitably leads to the use and does not // initialize the variable. We do not want to skip past loops, since their // non-termination might be correlated with the initialization condition. // // For example: // // void f(bool a, bool b) { // block1: int n; // if (a) { // block2: if (b) // block3: n = 1; // block4: } else if (b) { // block5: while (!a) { // block6: do_work(&a); // n = 2; // } // } // block7: if (a) // block8: g(); // block9: return n; // } // // Starting from the maybe-uninitialized use in block 9: // * Block 7 is not visited because we have only visited one of its two // successors. // * Block 8 is visited because we've visited its only successor. // From block 8: // * Block 7 is visited because we've now visited both of its successors. // From block 7: // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). // * Block 3 is not visited because it initializes 'n'. // Now the algorithm terminates, having visited blocks 7 and 8, and having // found the frontier is blocks 2, 4, and 5. // // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 // and 4), so we report that any time either of those edges is taken (in // each case when 'b == false'), 'n' is used uninitialized. SmallVector Queue; SmallVector SuccsVisited(cfg.getNumBlockIDs(), 0); Queue.push_back(block); // Specify that we've already visited all successors of the starting block. // This has the dual purpose of ensuring we never add it to the queue, and // of marking it as not being a candidate element of the frontier. SuccsVisited[block->getBlockID()] = block->succ_size(); while (!Queue.empty()) { const CFGBlock *B = Queue.pop_back_val(); // If the use is always reached from the entry block, make a note of that. if (B == &cfg.getEntry()) Use.setUninitAfterCall(); for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); I != E; ++I) { const CFGBlock *Pred = *I; if (!Pred) continue; Value AtPredExit = vals.getValue(Pred, B, vd); if (AtPredExit == Initialized) // This block initializes the variable. continue; if (AtPredExit == MayUninitialized && vals.getValue(B, 0, vd) == Uninitialized) { // This block declares the variable (uninitialized), and is reachable // from a block that initializes the variable. We can't guarantee to // give an earlier location for the diagnostic (and it appears that // this code is intended to be reachable) so give a diagnostic here // and go no further down this path. Use.setUninitAfterDecl(); continue; } unsigned &SV = SuccsVisited[Pred->getBlockID()]; if (!SV) { // When visiting the first successor of a block, mark all NULL // successors as having been visited. for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), SE = Pred->succ_end(); SI != SE; ++SI) if (!*SI) ++SV; } if (++SV == Pred->succ_size()) // All paths from this block lead to the use and don't initialize the // variable. Queue.push_back(Pred); } } // Scan the frontier, looking for blocks where the variable was // uninitialized. for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { const CFGBlock *Block = *BI; unsigned BlockID = Block->getBlockID(); const Stmt *Term = Block->getTerminator(); if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && Term) { // This block inevitably leads to the use. If we have an edge from here // to a post-dominator block, and the variable is uninitialized on that // edge, we have found a bug. for (CFGBlock::const_succ_iterator I = Block->succ_begin(), E = Block->succ_end(); I != E; ++I) { const CFGBlock *Succ = *I; if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && vals.getValue(Block, Succ, vd) == Uninitialized) { // Switch cases are a special case: report the label to the caller // as the 'terminator', not the switch statement itself. Suppress // situations where no label matched: we can't be sure that's // possible. if (isa(Term)) { const Stmt *Label = Succ->getLabel(); if (!Label || !isa(Label)) // Might not be possible. continue; UninitUse::Branch Branch; Branch.Terminator = Label; Branch.Output = 0; // Ignored. Use.addUninitBranch(Branch); } else { UninitUse::Branch Branch; Branch.Terminator = Term; Branch.Output = I - Block->succ_begin(); Use.addUninitBranch(Branch); } } } } } return Use; } }; } void TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { Value v = vals[vd]; if (isUninitialized(v)) handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); } void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { // This represents an initialization of the 'element' value. if (DeclStmt *DS = dyn_cast(FS->getElement())) { const VarDecl *VD = cast(DS->getSingleDecl()); if (isTrackedVar(VD)) vals[VD] = Initialized; } } void TransferFunctions::VisitBlockExpr(BlockExpr *be) { const BlockDecl *bd = be->getBlockDecl(); for (BlockDecl::capture_const_iterator i = bd->capture_begin(), e = bd->capture_end() ; i != e; ++i) { const VarDecl *vd = i->getVariable(); if (!isTrackedVar(vd)) continue; if (i->isByRef()) { vals[vd] = Initialized; continue; } reportUse(be, vd); } } void TransferFunctions::VisitCallExpr(CallExpr *ce) { if (Decl *Callee = ce->getCalleeDecl()) { if (Callee->hasAttr()) { // After a call to a function like setjmp or vfork, any variable which is // initialized anywhere within this function may now be initialized. For // now, just assume such a call initializes all variables. FIXME: Only // mark variables as initialized if they have an initializer which is // reachable from here. vals.setAllScratchValues(Initialized); } else if (Callee->hasAttr()) { // Functions labeled like "analyzer_noreturn" are often used to denote // "panic" functions that in special debug situations can still return, // but for the most part should not be treated as returning. This is a // useful annotation borrowed from the static analyzer that is useful for // suppressing branch-specific false positives when we call one of these // functions but keep pretending the path continues (when in reality the // user doesn't care). vals.setAllScratchValues(Unknown); } } } void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { switch (classification.get(dr)) { case ClassifyRefs::Ignore: break; case ClassifyRefs::Use: reportUse(dr, cast(dr->getDecl())); break; case ClassifyRefs::Init: vals[cast(dr->getDecl())] = Initialized; break; case ClassifyRefs::SelfInit: handler.handleSelfInit(cast(dr->getDecl())); break; } } void TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { if (BO->getOpcode() == BO_Assign) { FindVarResult Var = findVar(BO->getLHS()); if (const VarDecl *VD = Var.getDecl()) vals[VD] = Initialized; } } void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); DI != DE; ++DI) { VarDecl *VD = dyn_cast(*DI); if (VD && isTrackedVar(VD)) { if (getSelfInitExpr(VD)) { // If the initializer consists solely of a reference to itself, we // explicitly mark the variable as uninitialized. This allows code // like the following: // // int x = x; // // to deliberately leave a variable uninitialized. Different analysis // clients can detect this pattern and adjust their reporting // appropriately, but we need to continue to analyze subsequent uses // of the variable. vals[VD] = Uninitialized; } else if (VD->getInit()) { // Treat the new variable as initialized. vals[VD] = Initialized; } else { // No initializer: the variable is now uninitialized. This matters // for cases like: // while (...) { // int n; // use(n); // n = 0; // } // FIXME: Mark the variable as uninitialized whenever its scope is // left, since its scope could be re-entered by a jump over the // declaration. vals[VD] = Uninitialized; } } } } void TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { // If the Objective-C message expression is an implicit no-return that // is not modeled in the CFG, set the tracked dataflow values to Unknown. if (objCNoRet.isImplicitNoReturn(ME)) { vals.setAllScratchValues(Unknown); } } //------------------------------------------------------------------------====// // High-level "driver" logic for uninitialized values analysis. //====------------------------------------------------------------------------// static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler) { wasAnalyzed[block->getBlockID()] = true; vals.resetScratch(); // Merge in values of predecessor blocks. bool isFirst = true; for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { const CFGBlock *pred = *I; if (!pred) continue; if (wasAnalyzed[pred->getBlockID()]) { vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); isFirst = false; } } // Apply the transfer function. TransferFunctions tf(vals, cfg, block, ac, classification, handler); for (CFGBlock::const_iterator I = block->begin(), E = block->end(); I != E; ++I) { if (Optional cs = I->getAs()) tf.Visit(const_cast(cs->getStmt())); } return vals.updateValueVectorWithScratch(block); } /// PruneBlocksHandler is a special UninitVariablesHandler that is used /// to detect when a CFGBlock has any *potential* use of an uninitialized /// variable. It is mainly used to prune out work during the final /// reporting pass. namespace { struct PruneBlocksHandler : public UninitVariablesHandler { PruneBlocksHandler(unsigned numBlocks) : hadUse(numBlocks, false), hadAnyUse(false), currentBlock(0) {} virtual ~PruneBlocksHandler() {} /// Records if a CFGBlock had a potential use of an uninitialized variable. llvm::BitVector hadUse; /// Records if any CFGBlock had a potential use of an uninitialized variable. bool hadAnyUse; /// The current block to scribble use information. unsigned currentBlock; virtual void handleUseOfUninitVariable(const VarDecl *vd, const UninitUse &use) { hadUse[currentBlock] = true; hadAnyUse = true; } /// Called when the uninitialized variable analysis detects the /// idiom 'int x = x'. All other uses of 'x' within the initializer /// are handled by handleUseOfUninitVariable. virtual void handleSelfInit(const VarDecl *vd) { hadUse[currentBlock] = true; hadAnyUse = true; } }; } void clang::runUninitializedVariablesAnalysis( const DeclContext &dc, const CFG &cfg, AnalysisDeclContext &ac, UninitVariablesHandler &handler, UninitVariablesAnalysisStats &stats) { CFGBlockValues vals(cfg); vals.computeSetOfDeclarations(dc); if (vals.hasNoDeclarations()) return; stats.NumVariablesAnalyzed = vals.getNumEntries(); // Precompute which expressions are uses and which are initializations. ClassifyRefs classification(ac); cfg.VisitBlockStmts(classification); // Mark all variables uninitialized at the entry. const CFGBlock &entry = cfg.getEntry(); ValueVector &vec = vals.getValueVector(&entry); const unsigned n = vals.getNumEntries(); for (unsigned j = 0; j < n ; ++j) { vec[j] = Uninitialized; } // Proceed with the workist. DataflowWorklist worklist(cfg, *ac.getAnalysis()); llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); worklist.enqueueSuccessors(&cfg.getEntry()); llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); wasAnalyzed[cfg.getEntry().getBlockID()] = true; PruneBlocksHandler PBH(cfg.getNumBlockIDs()); while (const CFGBlock *block = worklist.dequeue()) { PBH.currentBlock = block->getBlockID(); // Did the block change? bool changed = runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, PBH); ++stats.NumBlockVisits; if (changed || !previouslyVisited[block->getBlockID()]) worklist.enqueueSuccessors(block); previouslyVisited[block->getBlockID()] = true; } if (!PBH.hadAnyUse) return; // Run through the blocks one more time, and report uninitialized variables. for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { const CFGBlock *block = *BI; if (PBH.hadUse[block->getBlockID()]) { runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler); ++stats.NumBlockVisits; } } } UninitVariablesHandler::~UninitVariablesHandler() {} @