971 lines · cpp
1//===- UninitializedValues.cpp - Find Uninitialized Values ----------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements uninitialized values analysis for source-level CFGs.10//11//===----------------------------------------------------------------------===//12 13#include "clang/Analysis/Analyses/UninitializedValues.h"14#include "clang/AST/Attr.h"15#include "clang/AST/Decl.h"16#include "clang/AST/DeclBase.h"17#include "clang/AST/Expr.h"18#include "clang/AST/OperationKinds.h"19#include "clang/AST/Stmt.h"20#include "clang/AST/StmtObjC.h"21#include "clang/AST/StmtVisitor.h"22#include "clang/AST/Type.h"23#include "clang/Analysis/AnalysisDeclContext.h"24#include "clang/Analysis/CFG.h"25#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h"26#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"27#include "clang/Basic/LLVM.h"28#include "llvm/ADT/BitVector.h"29#include "llvm/ADT/DenseMap.h"30#include "llvm/ADT/PackedVector.h"31#include "llvm/ADT/SmallBitVector.h"32#include "llvm/ADT/SmallVector.h"33#include <algorithm>34#include <cassert>35#include <optional>36 37using namespace clang;38 39#define DEBUG_LOGGING 040 41static bool recordIsNotEmpty(const RecordDecl *RD) {42 // We consider a record decl to be empty if it contains only unnamed bit-43 // fields, zero-width fields, and fields of empty record type.44 for (const auto *FD : RD->fields()) {45 if (FD->isUnnamedBitField())46 continue;47 if (FD->isZeroSize(FD->getASTContext()))48 continue;49 // The only case remaining to check is for a field declaration of record50 // type and whether that record itself is empty.51 if (const auto *FieldRD = FD->getType()->getAsRecordDecl();52 !FieldRD || recordIsNotEmpty(FieldRD))53 return true;54 }55 return false;56}57 58static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) {59 if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() &&60 !vd->isExceptionVariable() && !vd->isInitCapture() && !vd->isImplicit() &&61 vd->getDeclContext() == dc) {62 QualType ty = vd->getType();63 if (const auto *RD = ty->getAsRecordDecl())64 return recordIsNotEmpty(RD);65 return ty->isScalarType() || ty->isVectorType() || ty->isRVVSizelessBuiltinType();66 }67 return false;68}69 70//------------------------------------------------------------------------====//71// DeclToIndex: a mapping from Decls we track to value indices.72//====------------------------------------------------------------------------//73 74namespace {75 76class DeclToIndex {77 llvm::DenseMap<const VarDecl *, unsigned> map;78 79public:80 DeclToIndex() = default;81 82 /// Compute the actual mapping from declarations to bits.83 void computeMap(const DeclContext &dc);84 85 /// Return the number of declarations in the map.86 unsigned size() const { return map.size(); }87 88 /// Returns the bit vector index for a given declaration.89 std::optional<unsigned> getValueIndex(const VarDecl *d) const;90};91 92} // namespace93 94void DeclToIndex::computeMap(const DeclContext &dc) {95 unsigned count = 0;96 DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()),97 E(dc.decls_end());98 for ( ; I != E; ++I) {99 const VarDecl *vd = *I;100 if (isTrackedVar(vd, &dc))101 map[vd] = count++;102 }103}104 105std::optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const {106 llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d);107 if (I == map.end())108 return std::nullopt;109 return I->second;110}111 112//------------------------------------------------------------------------====//113// CFGBlockValues: dataflow values for CFG blocks.114//====------------------------------------------------------------------------//115 116// These values are defined in such a way that a merge can be done using117// a bitwise OR.118enum Value { Unknown = 0x0, /* 00 */119 Initialized = 0x1, /* 01 */120 Uninitialized = 0x2, /* 10 */121 MayUninitialized = 0x3 /* 11 */ };122 123static bool isUninitialized(const Value v) {124 return v >= Uninitialized;125}126 127static bool isAlwaysUninit(const Value v) {128 return v == Uninitialized;129}130 131namespace {132 133using ValueVector = llvm::PackedVector<Value, 2, llvm::SmallBitVector>;134 135class CFGBlockValues {136 const CFG &cfg;137 SmallVector<ValueVector, 8> vals;138 ValueVector scratch;139 DeclToIndex declToIndex;140 141public:142 CFGBlockValues(const CFG &cfg);143 144 unsigned getNumEntries() const { return declToIndex.size(); }145 146 void computeSetOfDeclarations(const DeclContext &dc);147 148 ValueVector &getValueVector(const CFGBlock *block) {149 return vals[block->getBlockID()];150 }151 152 void setAllScratchValues(Value V);153 void mergeIntoScratch(ValueVector const &source, bool isFirst);154 bool updateValueVectorWithScratch(const CFGBlock *block);155 156 bool hasNoDeclarations() const {157 return declToIndex.size() == 0;158 }159 160 void resetScratch();161 162 ValueVector::reference operator[](const VarDecl *vd);163 164 Value getValue(const CFGBlock *block, const VarDecl *vd) {165 std::optional<unsigned> idx = declToIndex.getValueIndex(vd);166 return getValueVector(block)[*idx];167 }168};169 170} // namespace171 172CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {}173 174void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) {175 declToIndex.computeMap(dc);176 unsigned decls = declToIndex.size();177 scratch.resize(decls);178 unsigned n = cfg.getNumBlockIDs();179 if (!n)180 return;181 vals.resize(n);182 for (auto &val : vals)183 val.resize(decls);184}185 186#if DEBUG_LOGGING187static void printVector(const CFGBlock *block, ValueVector &bv,188 unsigned num) {189 llvm::errs() << block->getBlockID() << " :";190 for (const auto &i : bv)191 llvm::errs() << ' ' << i;192 llvm::errs() << " : " << num << '\n';193}194#endif195 196void CFGBlockValues::setAllScratchValues(Value V) {197 for (unsigned I = 0, E = scratch.size(); I != E; ++I)198 scratch[I] = V;199}200 201void CFGBlockValues::mergeIntoScratch(ValueVector const &source,202 bool isFirst) {203 if (isFirst)204 scratch = source;205 else206 scratch |= source;207}208 209bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) {210 ValueVector &dst = getValueVector(block);211 bool changed = (dst != scratch);212 if (changed)213 dst = scratch;214#if DEBUG_LOGGING215 printVector(block, scratch, 0);216#endif217 return changed;218}219 220void CFGBlockValues::resetScratch() {221 scratch.reset();222}223 224ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) {225 return scratch[*declToIndex.getValueIndex(vd)];226}227 228//------------------------------------------------------------------------====//229// Classification of DeclRefExprs as use or initialization.230//====------------------------------------------------------------------------//231 232namespace {233 234class FindVarResult {235 const VarDecl *vd;236 const DeclRefExpr *dr;237 238public:239 FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {}240 241 const DeclRefExpr *getDeclRefExpr() const { return dr; }242 const VarDecl *getDecl() const { return vd; }243};244 245} // namespace246 247static const Expr *stripCasts(ASTContext &C, const Expr *Ex) {248 while (Ex) {249 Ex = Ex->IgnoreParenNoopCasts(C);250 if (const auto *CE = dyn_cast<CastExpr>(Ex)) {251 if (CE->getCastKind() == CK_LValueBitCast) {252 Ex = CE->getSubExpr();253 continue;254 }255 }256 break;257 }258 return Ex;259}260 261/// If E is an expression comprising a reference to a single variable, find that262/// variable.263static FindVarResult findVar(const Expr *E, const DeclContext *DC) {264 if (const auto *DRE =265 dyn_cast<DeclRefExpr>(stripCasts(DC->getParentASTContext(), E)))266 if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()))267 if (isTrackedVar(VD, DC))268 return FindVarResult(VD, DRE);269 return FindVarResult(nullptr, nullptr);270}271 272namespace {273 274/// Classify each DeclRefExpr as an initialization or a use. Any275/// DeclRefExpr which isn't explicitly classified will be assumed to have276/// escaped the analysis and will be treated as an initialization.277class ClassifyRefs : public StmtVisitor<ClassifyRefs> {278public:279 enum Class { Init, Use, SelfInit, ConstRefUse, ConstPtrUse, Ignore };280 281private:282 const DeclContext *DC;283 llvm::DenseMap<const DeclRefExpr *, Class> Classification;284 285 bool isTrackedVar(const VarDecl *VD) const {286 return ::isTrackedVar(VD, DC);287 }288 289 void classify(const Expr *E, Class C);290 291public:292 ClassifyRefs(AnalysisDeclContext &AC) : DC(cast<DeclContext>(AC.getDecl())) {}293 294 void VisitDeclStmt(DeclStmt *DS);295 void VisitUnaryOperator(UnaryOperator *UO);296 void VisitBinaryOperator(BinaryOperator *BO);297 void VisitCallExpr(CallExpr *CE);298 void VisitCastExpr(CastExpr *CE);299 void VisitOMPExecutableDirective(OMPExecutableDirective *ED);300 301 void operator()(Stmt *S) { Visit(S); }302 303 Class get(const DeclRefExpr *DRE) const {304 llvm::DenseMap<const DeclRefExpr*, Class>::const_iterator I305 = Classification.find(DRE);306 if (I != Classification.end())307 return I->second;308 309 const auto *VD = dyn_cast<VarDecl>(DRE->getDecl());310 if (!VD || !isTrackedVar(VD))311 return Ignore;312 313 return Init;314 }315};316 317} // namespace318 319static const DeclRefExpr *getSelfInitExpr(VarDecl *VD) {320 if (VD->getType()->isRecordType())321 return nullptr;322 if (Expr *Init = VD->getInit()) {323 const auto *DRE =324 dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init));325 if (DRE && DRE->getDecl() == VD)326 return DRE;327 }328 return nullptr;329}330 331void ClassifyRefs::classify(const Expr *E, Class C) {332 // The result of a ?: could also be an lvalue.333 E = E->IgnoreParens();334 if (const auto *CO = dyn_cast<ConditionalOperator>(E)) {335 classify(CO->getTrueExpr(), C);336 classify(CO->getFalseExpr(), C);337 return;338 }339 340 if (const auto *BCO = dyn_cast<BinaryConditionalOperator>(E)) {341 classify(BCO->getFalseExpr(), C);342 return;343 }344 345 if (const auto *OVE = dyn_cast<OpaqueValueExpr>(E)) {346 classify(OVE->getSourceExpr(), C);347 return;348 }349 350 if (const auto *ME = dyn_cast<MemberExpr>(E)) {351 if (const auto *VD = dyn_cast<VarDecl>(ME->getMemberDecl())) {352 if (!VD->isStaticDataMember())353 classify(ME->getBase(), C);354 }355 return;356 }357 358 if (const auto *BO = dyn_cast<BinaryOperator>(E)) {359 switch (BO->getOpcode()) {360 case BO_PtrMemD:361 case BO_PtrMemI:362 classify(BO->getLHS(), C);363 return;364 case BO_Comma:365 classify(BO->getRHS(), C);366 return;367 default:368 return;369 }370 }371 372 FindVarResult Var = findVar(E, DC);373 if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) {374 auto &Class = Classification[DRE];375 Class = std::max(Class, C);376 }377}378 379void ClassifyRefs::VisitDeclStmt(DeclStmt *DS) {380 for (auto *DI : DS->decls()) {381 auto *VD = dyn_cast<VarDecl>(DI);382 if (VD && isTrackedVar(VD))383 if (const DeclRefExpr *DRE = getSelfInitExpr(VD))384 Classification[DRE] = SelfInit;385 }386}387 388void ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) {389 // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this390 // is not a compound-assignment, we will treat it as initializing the variable391 // when TransferFunctions visits it. A compound-assignment does not affect392 // whether a variable is uninitialized, and there's no point counting it as a393 // use.394 if (BO->isCompoundAssignmentOp())395 classify(BO->getLHS(), Use);396 else if (BO->getOpcode() == BO_Assign || BO->getOpcode() == BO_Comma)397 classify(BO->getLHS(), Ignore);398}399 400void ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) {401 // Increment and decrement are uses despite there being no lvalue-to-rvalue402 // conversion.403 if (UO->isIncrementDecrementOp())404 classify(UO->getSubExpr(), Use);405}406 407void ClassifyRefs::VisitOMPExecutableDirective(OMPExecutableDirective *ED) {408 for (Stmt *S : OMPExecutableDirective::used_clauses_children(ED->clauses()))409 classify(cast<Expr>(S), Use);410}411 412static bool isPointerToConst(const QualType &QT) {413 return QT->isAnyPointerType() && QT->getPointeeType().isConstQualified();414}415 416static bool hasTrivialBody(CallExpr *CE) {417 if (FunctionDecl *FD = CE->getDirectCallee()) {418 if (FunctionTemplateDecl *FTD = FD->getPrimaryTemplate())419 return FTD->getTemplatedDecl()->hasTrivialBody();420 return FD->hasTrivialBody();421 }422 return false;423}424 425void ClassifyRefs::VisitCallExpr(CallExpr *CE) {426 // Classify arguments to std::move as used.427 if (CE->isCallToStdMove()) {428 // RecordTypes are handled in SemaDeclCXX.cpp.429 if (!CE->getArg(0)->getType()->isRecordType())430 classify(CE->getArg(0), Use);431 return;432 }433 bool isTrivialBody = hasTrivialBody(CE);434 // If a value is passed by const pointer to a function,435 // we should not assume that it is initialized by the call, and we436 // conservatively do not assume that it is used.437 // If a value is passed by const reference to a function,438 // it should already be initialized.439 for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();440 I != E; ++I) {441 if ((*I)->isGLValue()) {442 if ((*I)->getType().isConstQualified())443 classify((*I), isTrivialBody ? Ignore : ConstRefUse);444 } else if (isPointerToConst((*I)->getType())) {445 const Expr *Ex = stripCasts(DC->getParentASTContext(), *I);446 const auto *UO = dyn_cast<UnaryOperator>(Ex);447 if (UO && UO->getOpcode() == UO_AddrOf)448 classify(UO->getSubExpr(), isTrivialBody ? Ignore : ConstPtrUse);449 }450 }451}452 453void ClassifyRefs::VisitCastExpr(CastExpr *CE) {454 if (CE->getCastKind() == CK_LValueToRValue)455 classify(CE->getSubExpr(), Use);456 else if (const auto *CSE = dyn_cast<CStyleCastExpr>(CE)) {457 if (CSE->getType()->isVoidType()) {458 // Squelch any detected load of an uninitialized value if459 // we cast it to void.460 // e.g. (void) x;461 classify(CSE->getSubExpr(), Ignore);462 }463 }464}465 466//------------------------------------------------------------------------====//467// Transfer function for uninitialized values analysis.468//====------------------------------------------------------------------------//469 470namespace {471 472class TransferFunctions : public StmtVisitor<TransferFunctions> {473 CFGBlockValues &vals;474 const CFG &cfg;475 const CFGBlock *block;476 AnalysisDeclContext ∾477 const ClassifyRefs &classification;478 ObjCNoReturn objCNoRet;479 UninitVariablesHandler &handler;480 481public:482 TransferFunctions(CFGBlockValues &vals, const CFG &cfg,483 const CFGBlock *block, AnalysisDeclContext &ac,484 const ClassifyRefs &classification,485 UninitVariablesHandler &handler)486 : vals(vals), cfg(cfg), block(block), ac(ac),487 classification(classification), objCNoRet(ac.getASTContext()),488 handler(handler) {}489 490 void reportUse(const Expr *ex, const VarDecl *vd);491 void reportConstRefUse(const Expr *ex, const VarDecl *vd);492 void reportConstPtrUse(const Expr *ex, const VarDecl *vd);493 494 void VisitBinaryOperator(BinaryOperator *bo);495 void VisitBlockExpr(BlockExpr *be);496 void VisitCallExpr(CallExpr *ce);497 void VisitDeclRefExpr(DeclRefExpr *dr);498 void VisitDeclStmt(DeclStmt *ds);499 void VisitGCCAsmStmt(GCCAsmStmt *as);500 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS);501 void VisitObjCMessageExpr(ObjCMessageExpr *ME);502 void VisitOMPExecutableDirective(OMPExecutableDirective *ED);503 504 bool isTrackedVar(const VarDecl *vd) {505 return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl()));506 }507 508 FindVarResult findVar(const Expr *ex) {509 return ::findVar(ex, cast<DeclContext>(ac.getDecl()));510 }511 512 UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) {513 UninitUse Use(ex, isAlwaysUninit(v));514 515 assert(isUninitialized(v));516 if (Use.getKind() == UninitUse::Always)517 return Use;518 519 // If an edge which leads unconditionally to this use did not initialize520 // the variable, we can say something stronger than 'may be uninitialized':521 // we can say 'either it's used uninitialized or you have dead code'.522 //523 // We track the number of successors of a node which have been visited, and524 // visit a node once we have visited all of its successors. Only edges where525 // the variable might still be uninitialized are followed. Since a variable526 // can't transfer from being initialized to being uninitialized, this will527 // trace out the subgraph which inevitably leads to the use and does not528 // initialize the variable. We do not want to skip past loops, since their529 // non-termination might be correlated with the initialization condition.530 //531 // For example:532 //533 // void f(bool a, bool b) {534 // block1: int n;535 // if (a) {536 // block2: if (b)537 // block3: n = 1;538 // block4: } else if (b) {539 // block5: while (!a) {540 // block6: do_work(&a);541 // n = 2;542 // }543 // }544 // block7: if (a)545 // block8: g();546 // block9: return n;547 // }548 //549 // Starting from the maybe-uninitialized use in block 9:550 // * Block 7 is not visited because we have only visited one of its two551 // successors.552 // * Block 8 is visited because we've visited its only successor.553 // From block 8:554 // * Block 7 is visited because we've now visited both of its successors.555 // From block 7:556 // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all557 // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively).558 // * Block 3 is not visited because it initializes 'n'.559 // Now the algorithm terminates, having visited blocks 7 and 8, and having560 // found the frontier is blocks 2, 4, and 5.561 //562 // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2563 // and 4), so we report that any time either of those edges is taken (in564 // each case when 'b == false'), 'n' is used uninitialized.565 SmallVector<const CFGBlock*, 32> Queue;566 SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0);567 Queue.push_back(block);568 // Specify that we've already visited all successors of the starting block.569 // This has the dual purpose of ensuring we never add it to the queue, and570 // of marking it as not being a candidate element of the frontier.571 SuccsVisited[block->getBlockID()] = block->succ_size();572 while (!Queue.empty()) {573 const CFGBlock *B = Queue.pop_back_val();574 575 // If the use is always reached from the entry block, make a note of that.576 if (B == &cfg.getEntry())577 Use.setUninitAfterCall();578 579 for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end();580 I != E; ++I) {581 const CFGBlock *Pred = *I;582 if (!Pred)583 continue;584 585 Value AtPredExit = vals.getValue(Pred, vd);586 if (AtPredExit == Initialized)587 // This block initializes the variable.588 continue;589 if (AtPredExit == MayUninitialized &&590 vals.getValue(B, vd) == Uninitialized) {591 // This block declares the variable (uninitialized), and is reachable592 // from a block that initializes the variable. We can't guarantee to593 // give an earlier location for the diagnostic (and it appears that594 // this code is intended to be reachable) so give a diagnostic here595 // and go no further down this path.596 Use.setUninitAfterDecl();597 continue;598 }599 600 unsigned &SV = SuccsVisited[Pred->getBlockID()];601 if (!SV) {602 // When visiting the first successor of a block, mark all NULL603 // successors as having been visited.604 for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(),605 SE = Pred->succ_end();606 SI != SE; ++SI)607 if (!*SI)608 ++SV;609 }610 611 if (++SV == Pred->succ_size())612 // All paths from this block lead to the use and don't initialize the613 // variable.614 Queue.push_back(Pred);615 }616 }617 618 // Scan the frontier, looking for blocks where the variable was619 // uninitialized.620 for (const auto *Block : cfg) {621 if (vals.getValue(Block, vd) != Uninitialized)622 continue;623 unsigned BlockID = Block->getBlockID();624 const Stmt *Term = Block->getTerminatorStmt();625 if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() &&626 Term) {627 // This block inevitably leads to the use. If we have an edge from here628 // to a post-dominator block, and the variable is uninitialized on that629 // edge, we have found a bug.630 for (CFGBlock::const_succ_iterator I = Block->succ_begin(),631 E = Block->succ_end(); I != E; ++I) {632 const CFGBlock *Succ = *I;633 if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size()) {634 // Switch cases are a special case: report the label to the caller635 // as the 'terminator', not the switch statement itself. Suppress636 // situations where no label matched: we can't be sure that's637 // possible.638 if (isa<SwitchStmt>(Term)) {639 const Stmt *Label = Succ->getLabel();640 if (!Label || !isa<SwitchCase>(Label))641 // Might not be possible.642 continue;643 UninitUse::Branch Branch;644 Branch.Terminator = Label;645 Branch.Output = 0; // Ignored.646 Use.addUninitBranch(Branch);647 } else {648 UninitUse::Branch Branch;649 Branch.Terminator = Term;650 Branch.Output = I - Block->succ_begin();651 Use.addUninitBranch(Branch);652 }653 }654 }655 }656 }657 658 return Use;659 }660};661 662} // namespace663 664void TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) {665 Value v = vals[vd];666 if (isUninitialized(v))667 handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v));668}669 670void TransferFunctions::reportConstRefUse(const Expr *ex, const VarDecl *vd) {671 Value v = vals[vd];672 if (isAlwaysUninit(v)) {673 auto use = getUninitUse(ex, vd, v);674 use.setConstRefUse();675 handler.handleUseOfUninitVariable(vd, use);676 }677}678 679void TransferFunctions::reportConstPtrUse(const Expr *ex, const VarDecl *vd) {680 Value v = vals[vd];681 if (isAlwaysUninit(v)) {682 auto use = getUninitUse(ex, vd, v);683 use.setConstPtrUse();684 handler.handleUseOfUninitVariable(vd, use);685 }686}687 688void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) {689 // This represents an initialization of the 'element' value.690 if (const auto *DS = dyn_cast<DeclStmt>(FS->getElement())) {691 const auto *VD = cast<VarDecl>(DS->getSingleDecl());692 if (isTrackedVar(VD))693 vals[VD] = Initialized;694 }695}696 697void TransferFunctions::VisitOMPExecutableDirective(698 OMPExecutableDirective *ED) {699 for (Stmt *S : OMPExecutableDirective::used_clauses_children(ED->clauses())) {700 assert(S && "Expected non-null used-in-clause child.");701 Visit(S);702 }703 if (!ED->isStandaloneDirective())704 Visit(ED->getStructuredBlock());705}706 707void TransferFunctions::VisitBlockExpr(BlockExpr *be) {708 const BlockDecl *bd = be->getBlockDecl();709 for (const auto &I : bd->captures()) {710 const VarDecl *vd = I.getVariable();711 if (!isTrackedVar(vd))712 continue;713 if (I.isByRef()) {714 vals[vd] = Initialized;715 continue;716 }717 reportUse(be, vd);718 }719}720 721void TransferFunctions::VisitCallExpr(CallExpr *ce) {722 if (Decl *Callee = ce->getCalleeDecl()) {723 if (Callee->hasAttr<ReturnsTwiceAttr>()) {724 // After a call to a function like setjmp or vfork, any variable which is725 // initialized anywhere within this function may now be initialized. For726 // now, just assume such a call initializes all variables. FIXME: Only727 // mark variables as initialized if they have an initializer which is728 // reachable from here.729 vals.setAllScratchValues(Initialized);730 }731 else if (Callee->hasAttr<AnalyzerNoReturnAttr>()) {732 // Functions labeled like "analyzer_noreturn" are often used to denote733 // "panic" functions that in special debug situations can still return,734 // but for the most part should not be treated as returning. This is a735 // useful annotation borrowed from the static analyzer that is useful for736 // suppressing branch-specific false positives when we call one of these737 // functions but keep pretending the path continues (when in reality the738 // user doesn't care).739 vals.setAllScratchValues(Unknown);740 }741 }742}743 744void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) {745 switch (classification.get(dr)) {746 case ClassifyRefs::Ignore:747 break;748 case ClassifyRefs::Use:749 reportUse(dr, cast<VarDecl>(dr->getDecl()));750 break;751 case ClassifyRefs::Init:752 vals[cast<VarDecl>(dr->getDecl())] = Initialized;753 break;754 case ClassifyRefs::SelfInit:755 handler.handleSelfInit(cast<VarDecl>(dr->getDecl()));756 break;757 case ClassifyRefs::ConstRefUse:758 reportConstRefUse(dr, cast<VarDecl>(dr->getDecl()));759 break;760 case ClassifyRefs::ConstPtrUse:761 reportConstPtrUse(dr, cast<VarDecl>(dr->getDecl()));762 break;763 }764}765 766void TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) {767 if (BO->getOpcode() == BO_Assign) {768 FindVarResult Var = findVar(BO->getLHS());769 if (const VarDecl *VD = Var.getDecl())770 vals[VD] = Initialized;771 }772}773 774void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {775 for (auto *DI : DS->decls()) {776 auto *VD = dyn_cast<VarDecl>(DI);777 if (VD && isTrackedVar(VD)) {778 if (getSelfInitExpr(VD)) {779 // If the initializer consists solely of a reference to itself, we780 // explicitly mark the variable as uninitialized. This allows code781 // like the following:782 //783 // int x = x;784 //785 // to deliberately leave a variable uninitialized. Different analysis786 // clients can detect this pattern and adjust their reporting787 // appropriately, but we need to continue to analyze subsequent uses788 // of the variable.789 vals[VD] = Uninitialized;790 } else if (VD->getInit()) {791 // Treat the new variable as initialized.792 vals[VD] = Initialized;793 } else {794 // No initializer: the variable is now uninitialized. This matters795 // for cases like:796 // while (...) {797 // int n;798 // use(n);799 // n = 0;800 // }801 // FIXME: Mark the variable as uninitialized whenever its scope is802 // left, since its scope could be re-entered by a jump over the803 // declaration.804 vals[VD] = Uninitialized;805 }806 }807 }808}809 810void TransferFunctions::VisitGCCAsmStmt(GCCAsmStmt *as) {811 // An "asm goto" statement is a terminator that may initialize some variables.812 if (!as->isAsmGoto())813 return;814 815 ASTContext &C = ac.getASTContext();816 for (const Expr *O : as->outputs()) {817 const Expr *Ex = stripCasts(C, O);818 819 // Strip away any unary operators. Invalid l-values are reported by other820 // semantic analysis passes.821 while (const auto *UO = dyn_cast<UnaryOperator>(Ex))822 Ex = stripCasts(C, UO->getSubExpr());823 824 // Mark the variable as potentially uninitialized for those cases where825 // it's used on an indirect path, where it's not guaranteed to be826 // defined.827 if (const VarDecl *VD = findVar(Ex).getDecl())828 if (vals[VD] != Initialized)829 vals[VD] = MayUninitialized;830 }831}832 833void TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) {834 // If the Objective-C message expression is an implicit no-return that835 // is not modeled in the CFG, set the tracked dataflow values to Unknown.836 if (objCNoRet.isImplicitNoReturn(ME)) {837 vals.setAllScratchValues(Unknown);838 }839}840 841//------------------------------------------------------------------------====//842// High-level "driver" logic for uninitialized values analysis.843//====------------------------------------------------------------------------//844 845static bool runOnBlock(const CFGBlock *block, const CFG &cfg,846 AnalysisDeclContext &ac, CFGBlockValues &vals,847 const ClassifyRefs &classification,848 llvm::BitVector &wasAnalyzed,849 UninitVariablesHandler &handler) {850 wasAnalyzed[block->getBlockID()] = true;851 vals.resetScratch();852 // Merge in values of predecessor blocks.853 bool isFirst = true;854 for (CFGBlock::const_pred_iterator I = block->pred_begin(),855 E = block->pred_end(); I != E; ++I) {856 const CFGBlock *pred = *I;857 if (!pred)858 continue;859 if (wasAnalyzed[pred->getBlockID()]) {860 vals.mergeIntoScratch(vals.getValueVector(pred), isFirst);861 isFirst = false;862 }863 }864 // Apply the transfer function.865 TransferFunctions tf(vals, cfg, block, ac, classification, handler);866 for (const auto &I : *block) {867 if (std::optional<CFGStmt> cs = I.getAs<CFGStmt>())868 tf.Visit(const_cast<Stmt *>(cs->getStmt()));869 }870 CFGTerminator terminator = block->getTerminator();871 if (auto *as = dyn_cast_or_null<GCCAsmStmt>(terminator.getStmt()))872 if (as->isAsmGoto())873 tf.Visit(as);874 return vals.updateValueVectorWithScratch(block);875}876 877namespace {878 879/// PruneBlocksHandler is a special UninitVariablesHandler that is used880/// to detect when a CFGBlock has any *potential* use of an uninitialized881/// variable. It is mainly used to prune out work during the final882/// reporting pass.883struct PruneBlocksHandler : public UninitVariablesHandler {884 /// Records if a CFGBlock had a potential use of an uninitialized variable.885 llvm::BitVector hadUse;886 887 /// Records if any CFGBlock had a potential use of an uninitialized variable.888 bool hadAnyUse = false;889 890 /// The current block to scribble use information.891 unsigned currentBlock = 0;892 893 PruneBlocksHandler(unsigned numBlocks) : hadUse(numBlocks, false) {}894 895 ~PruneBlocksHandler() override = default;896 897 void handleUseOfUninitVariable(const VarDecl *vd,898 const UninitUse &use) override {899 hadUse[currentBlock] = true;900 hadAnyUse = true;901 }902 903 /// Called when the uninitialized variable analysis detects the904 /// idiom 'int x = x'. All other uses of 'x' within the initializer905 /// are handled by handleUseOfUninitVariable.906 void handleSelfInit(const VarDecl *vd) override {907 hadUse[currentBlock] = true;908 hadAnyUse = true;909 }910};911 912} // namespace913 914void clang::runUninitializedVariablesAnalysis(915 const DeclContext &dc,916 const CFG &cfg,917 AnalysisDeclContext &ac,918 UninitVariablesHandler &handler,919 UninitVariablesAnalysisStats &stats) {920 CFGBlockValues vals(cfg);921 vals.computeSetOfDeclarations(dc);922 if (vals.hasNoDeclarations())923 return;924 925 stats.NumVariablesAnalyzed = vals.getNumEntries();926 927 // Precompute which expressions are uses and which are initializations.928 ClassifyRefs classification(ac);929 cfg.VisitBlockStmts(classification);930 931 // Mark all variables uninitialized at the entry.932 const CFGBlock &entry = cfg.getEntry();933 ValueVector &vec = vals.getValueVector(&entry);934 const unsigned n = vals.getNumEntries();935 for (unsigned j = 0; j < n; ++j) {936 vec[j] = Uninitialized;937 }938 939 // Proceed with the workist.940 ForwardDataflowWorklist worklist(cfg, ac);941 llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());942 worklist.enqueueSuccessors(&cfg.getEntry());943 llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);944 wasAnalyzed[cfg.getEntry().getBlockID()] = true;945 PruneBlocksHandler PBH(cfg.getNumBlockIDs());946 947 while (const CFGBlock *block = worklist.dequeue()) {948 PBH.currentBlock = block->getBlockID();949 950 // Did the block change?951 bool changed = runOnBlock(block, cfg, ac, vals,952 classification, wasAnalyzed, PBH);953 ++stats.NumBlockVisits;954 if (changed || !previouslyVisited[block->getBlockID()])955 worklist.enqueueSuccessors(block);956 previouslyVisited[block->getBlockID()] = true;957 }958 959 if (!PBH.hadAnyUse)960 return;961 962 // Run through the blocks one more time, and report uninitialized variables.963 for (const auto *block : cfg)964 if (PBH.hadUse[block->getBlockID()]) {965 runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler);966 ++stats.NumBlockVisits;967 }968}969 970UninitVariablesHandler::~UninitVariablesHandler() = default;971