UninitializedValues.cpp revision 234353
167754Smsmith//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// 267754Smsmith// 367754Smsmith// The LLVM Compiler Infrastructure 467754Smsmith// 567754Smsmith// This file is distributed under the University of Illinois Open Source 667754Smsmith// License. See LICENSE.TXT for details. 7217365Sjkim// 8245582Sjkim//===----------------------------------------------------------------------===// 970243Smsmith// 1067754Smsmith// This file implements uninitialized values analysis for source-level CFGs. 11217365Sjkim// 12217365Sjkim//===----------------------------------------------------------------------===// 13217365Sjkim 14217365Sjkim#include <utility> 15217365Sjkim#include "llvm/ADT/Optional.h" 16217365Sjkim#include "llvm/ADT/SmallVector.h" 17217365Sjkim#include "llvm/ADT/PackedVector.h" 18217365Sjkim#include "llvm/ADT/DenseMap.h" 19217365Sjkim#include "clang/AST/Decl.h" 20217365Sjkim#include "clang/Analysis/CFG.h" 21217365Sjkim#include "clang/Analysis/AnalysisContext.h" 22217365Sjkim#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 23217365Sjkim#include "clang/Analysis/Analyses/UninitializedValues.h" 24217365Sjkim#include "llvm/Support/SaveAndRestore.h" 2567754Smsmith 26217365Sjkimusing namespace clang; 27217365Sjkim 28217365Sjkimstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 2967754Smsmith if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 30217365Sjkim !vd->isExceptionVariable() && 31217365Sjkim vd->getDeclContext() == dc) { 32217365Sjkim QualType ty = vd->getType(); 33217365Sjkim return ty->isScalarType() || ty->isVectorType(); 34217365Sjkim } 35217365Sjkim return false; 36217365Sjkim} 37217365Sjkim 38217365Sjkim//------------------------------------------------------------------------====// 39217365Sjkim// DeclToIndex: a mapping from Decls we track to value indices. 40217365Sjkim//====------------------------------------------------------------------------// 41217365Sjkim 42217365Sjkimnamespace { 4367754Smsmithclass DeclToIndex { 4467754Smsmith llvm::DenseMap<const VarDecl *, unsigned> map; 45193341Sjkimpublic: 46193341Sjkim DeclToIndex() {} 47193341Sjkim 48193341Sjkim /// Compute the actual mapping from declarations to bits. 4967754Smsmith void computeMap(const DeclContext &dc); 50102550Siwasaki 5167754Smsmith /// Return the number of declarations in the map. 52102550Siwasaki unsigned size() const { return map.size(); } 5391116Smsmith 5467754Smsmith /// Returns the bit vector index for a given declaration. 5567754Smsmith llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const; 56222544Sjkim}; 5767754Smsmith} 58151937Sjkim 5967754Smsmithvoid DeclToIndex::computeMap(const DeclContext &dc) { 60151937Sjkim unsigned count = 0; 61151937Sjkim DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 62151937Sjkim E(dc.decls_end()); 63151937Sjkim for ( ; I != E; ++I) { 64151937Sjkim const VarDecl *vd = *I; 65151937Sjkim if (isTrackedVar(vd, &dc)) 66151937Sjkim map[vd] = count++; 67151937Sjkim } 68151937Sjkim} 69151937Sjkim 70151937Sjkimllvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 71151937Sjkim llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 72151937Sjkim if (I == map.end()) 73151937Sjkim return llvm::Optional<unsigned>(); 74151937Sjkim return I->second; 75151937Sjkim} 76151937Sjkim 77151937Sjkim//------------------------------------------------------------------------====// 78151937Sjkim// CFGBlockValues: dataflow values for CFG blocks. 79151937Sjkim//====------------------------------------------------------------------------// 80151937Sjkim 81151937Sjkim// These values are defined in such a way that a merge can be done using 82151937Sjkim// a bitwise OR. 83151937Sjkimenum Value { Unknown = 0x0, /* 00 */ 84151937Sjkim Initialized = 0x1, /* 01 */ 8567754Smsmith Uninitialized = 0x2, /* 10 */ 8667754Smsmith MayUninitialized = 0x3 /* 11 */ }; 87222544Sjkim 88222544Sjkimstatic bool isUninitialized(const Value v) { 89222544Sjkim return v >= Uninitialized; 90222544Sjkim} 91222544Sjkimstatic bool isAlwaysUninit(const Value v) { 92222544Sjkim return v == Uninitialized; 93222544Sjkim} 94222544Sjkim 95222544Sjkimnamespace { 96222544Sjkim 97222544Sjkimtypedef llvm::PackedVector<Value, 2> ValueVector; 98222544Sjkimtypedef std::pair<ValueVector *, ValueVector *> BVPair; 99245582Sjkim 100222544Sjkimclass CFGBlockValues { 101222544Sjkim const CFG &cfg; 102222544Sjkim BVPair *vals; 103222544Sjkim ValueVector scratch; 104222544Sjkim DeclToIndex declToIndex; 105222544Sjkim 106222544Sjkim ValueVector &lazyCreate(ValueVector *&bv); 107222544Sjkimpublic: 108222544Sjkim CFGBlockValues(const CFG &cfg); 109222544Sjkim ~CFGBlockValues(); 110222544Sjkim 111222544Sjkim unsigned getNumEntries() const { return declToIndex.size(); } 112222544Sjkim 113222544Sjkim void computeSetOfDeclarations(const DeclContext &dc); 114222544Sjkim ValueVector &getValueVector(const CFGBlock *block, 115222544Sjkim const CFGBlock *dstBlock); 116222544Sjkim 117222544Sjkim BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate); 118222544Sjkim 119222544Sjkim void mergeIntoScratch(ValueVector const &source, bool isFirst); 120222544Sjkim bool updateValueVectorWithScratch(const CFGBlock *block); 121222544Sjkim bool updateValueVectors(const CFGBlock *block, const BVPair &newVals); 122222544Sjkim 123222544Sjkim bool hasNoDeclarations() const { 124222544Sjkim return declToIndex.size() == 0; 125222544Sjkim } 126222544Sjkim 127222544Sjkim void resetScratch(); 128222544Sjkim ValueVector &getScratch() { return scratch; } 129222544Sjkim 130222544Sjkim ValueVector::reference operator[](const VarDecl *vd); 131222544Sjkim}; 132222544Sjkim} // end anonymous namespace 133222544Sjkim 134222544SjkimCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { 135222544Sjkim unsigned n = cfg.getNumBlockIDs(); 13667754Smsmith if (!n) 13767754Smsmith return; 13867754Smsmith vals = new std::pair<ValueVector*, ValueVector*>[n]; 13967754Smsmith memset((void*)vals, 0, sizeof(*vals) * n); 14067754Smsmith} 14167754Smsmith 14267754SmsmithCFGBlockValues::~CFGBlockValues() { 14367754Smsmith unsigned n = cfg.getNumBlockIDs(); 14467754Smsmith if (n == 0) 14567754Smsmith return; 14667754Smsmith for (unsigned i = 0; i < n; ++i) { 147151937Sjkim delete vals[i].first; 14867754Smsmith delete vals[i].second; 14991116Smsmith } 15067754Smsmith delete [] vals; 15167754Smsmith} 15267754Smsmith 15367754Smsmithvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 154249663Sjkim declToIndex.computeMap(dc); 15567754Smsmith scratch.resize(declToIndex.size()); 15667754Smsmith} 15767754Smsmith 158216471SjkimValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) { 159216471Sjkim if (!bv) 160216471Sjkim bv = new ValueVector(declToIndex.size()); 16183174Smsmith return *bv; 16267754Smsmith} 16367754Smsmith 16467754Smsmith/// This function pattern matches for a '&&' or '||' that appears at 16567754Smsmith/// the beginning of a CFGBlock that also (1) has a terminator and 166249663Sjkim/// (2) has no other elements. If such an expression is found, it is returned. 167249663Sjkimstatic const BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) { 168193267Sjkim if (block->empty()) 169249663Sjkim return 0; 170193267Sjkim 171249663Sjkim const CFGStmt *cstmt = block->front().getAs<CFGStmt>(); 17267754Smsmith if (!cstmt) 173249663Sjkim return 0; 17467754Smsmith 175249663Sjkim const BinaryOperator *b = dyn_cast_or_null<BinaryOperator>(cstmt->getStmt()); 176193267Sjkim 177249663Sjkim if (!b || !b->isLogicalOp()) 178222544Sjkim return 0; 179249663Sjkim 180249663Sjkim if (block->pred_size() == 2) { 181249663Sjkim if (block->getTerminatorCondition() == b) { 182193267Sjkim if (block->succ_size() == 2) 183249663Sjkim return b; 184249663Sjkim } 185249663Sjkim else if (block->size() == 1) 186193267Sjkim return b; 187222544Sjkim } 18867754Smsmith 189249663Sjkim return 0; 190222544Sjkim} 19167754Smsmith 19267754SmsmithValueVector &CFGBlockValues::getValueVector(const CFGBlock *block, 19367754Smsmith const CFGBlock *dstBlock) { 19467754Smsmith unsigned idx = block->getBlockID(); 195151937Sjkim if (dstBlock && getLogicalOperatorInChain(block)) { 196151937Sjkim if (*block->succ_begin() == dstBlock) 19767754Smsmith return lazyCreate(vals[idx].first); 19867754Smsmith assert(*(block->succ_begin()+1) == dstBlock); 19967754Smsmith return lazyCreate(vals[idx].second); 200114237Snjl } 201249663Sjkim 202249663Sjkim assert(vals[idx].second == 0); 20367754Smsmith return lazyCreate(vals[idx].first); 20467754Smsmith} 20567754Smsmith 20667754SmsmithBVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block, 207216471Sjkim bool shouldLazyCreate) { 208216471Sjkim unsigned idx = block->getBlockID(); 209216471Sjkim lazyCreate(vals[idx].first); 210222544Sjkim if (shouldLazyCreate) 211216471Sjkim lazyCreate(vals[idx].second); 212216471Sjkim return vals[idx]; 213216471Sjkim} 214216471Sjkim 215222544Sjkim#if 0 216216471Sjkimstatic void printVector(const CFGBlock *block, ValueVector &bv, 217216471Sjkim unsigned num) { 218216471Sjkim 219216471Sjkim llvm::errs() << block->getBlockID() << " :"; 220222544Sjkim for (unsigned i = 0; i < bv.size(); ++i) { 221249663Sjkim llvm::errs() << ' ' << bv[i]; 222216471Sjkim } 22367754Smsmith llvm::errs() << " : " << num << '\n'; 22467754Smsmith} 22567754Smsmith 22667754Smsmithstatic void printVector(const char *name, ValueVector const &bv) { 22767754Smsmith llvm::errs() << name << " : "; 22867754Smsmith for (unsigned i = 0; i < bv.size(); ++i) { 22967754Smsmith llvm::errs() << ' ' << bv[i]; 23067754Smsmith } 23167754Smsmith llvm::errs() << "\n"; 232151937Sjkim} 23367754Smsmith#endif 23467754Smsmith 23567754Smsmithvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 23667754Smsmith bool isFirst) { 23767754Smsmith if (isFirst) 238151937Sjkim scratch = source; 23967754Smsmith else 24099679Siwasaki scratch |= source; 24167754Smsmith} 24267754Smsmith 24367754Smsmithbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 24467754Smsmith ValueVector &dst = getValueVector(block, 0); 24567754Smsmith bool changed = (dst != scratch); 24667754Smsmith if (changed) 24767754Smsmith dst = scratch; 24867754Smsmith#if 0 24991116Smsmith printVector(block, scratch, 0); 25067754Smsmith#endif 25167754Smsmith return changed; 25291116Smsmith} 25367754Smsmith 25467754Smsmithbool CFGBlockValues::updateValueVectors(const CFGBlock *block, 25591116Smsmith const BVPair &newVals) { 256240716Sjkim BVPair &vals = getValueVectors(block, true); 25767754Smsmith bool changed = *newVals.first != *vals.first || 25867754Smsmith *newVals.second != *vals.second; 25967754Smsmith *vals.first = *newVals.first; 26067754Smsmith *vals.second = *newVals.second; 26191116Smsmith#if 0 26267754Smsmith printVector(block, *vals.first, 1); 26367754Smsmith printVector(block, *vals.second, 2); 26467754Smsmith#endif 26567754Smsmith return changed; 26667754Smsmith} 26767754Smsmith 26891116Smsmithvoid CFGBlockValues::resetScratch() { 26967754Smsmith scratch.reset(); 27067754Smsmith} 27167754Smsmith 27267754SmsmithValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 273151937Sjkim const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 274167802Sjkim assert(idx.hasValue()); 275151937Sjkim return scratch[idx.getValue()]; 276151937Sjkim} 277151937Sjkim 278151937Sjkim//------------------------------------------------------------------------====// 279151937Sjkim// Worklist: worklist for dataflow analysis. 280151937Sjkim//====------------------------------------------------------------------------// 281151937Sjkim 282151937Sjkimnamespace { 28367754Smsmithclass DataflowWorklist { 28467754Smsmith SmallVector<const CFGBlock *, 20> worklist; 28582367Smsmith llvm::BitVector enqueuedBlocks; 28682367Smsmithpublic: 28782367Smsmith DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} 28882367Smsmith 28982367Smsmith void enqueueSuccessors(const CFGBlock *block); 29082367Smsmith const CFGBlock *dequeue(); 29182367Smsmith}; 29282367Smsmith} 29382367Smsmith 29482367Smsmithvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 29582367Smsmith unsigned OldWorklistSize = worklist.size(); 29682367Smsmith for (CFGBlock::const_succ_iterator I = block->succ_begin(), 297151937Sjkim E = block->succ_end(); I != E; ++I) { 29899679Siwasaki const CFGBlock *Successor = *I; 29999679Siwasaki if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 30082367Smsmith continue; 30182367Smsmith worklist.push_back(Successor); 30282367Smsmith enqueuedBlocks[Successor->getBlockID()] = true; 30382367Smsmith } 30482367Smsmith if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 305151937Sjkim return; 306151937Sjkim 307151937Sjkim // Rotate the newly added blocks to the start of the worklist so that it forms 308151937Sjkim // a proper queue when we pop off the end of the worklist. 30982367Smsmith std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize, 31082367Smsmith worklist.end()); 31182367Smsmith} 31282367Smsmith 31382367Smsmithconst CFGBlock *DataflowWorklist::dequeue() { 31482367Smsmith if (worklist.empty()) 31582367Smsmith return 0; 31682367Smsmith const CFGBlock *b = worklist.back(); 317114237Snjl worklist.pop_back(); 318114237Snjl enqueuedBlocks[b->getBlockID()] = false; 319114237Snjl return b; 320114237Snjl} 321114237Snjl 322114237Snjl//------------------------------------------------------------------------====// 323241973Sjkim// Transfer function for uninitialized values analysis. 324114237Snjl//====------------------------------------------------------------------------// 325114237Snjl 326114237Snjlnamespace { 327114237Snjlclass FindVarResult { 328151937Sjkim const VarDecl *vd; 329114237Snjl const DeclRefExpr *dr; 330114237Snjlpublic: 331114237Snjl FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {} 332114237Snjl 333114237Snjl const DeclRefExpr *getDeclRefExpr() const { return dr; } 334114237Snjl const VarDecl *getDecl() const { return vd; } 335114237Snjl}; 336114237Snjl 337114237Snjlclass TransferFunctions : public StmtVisitor<TransferFunctions> { 338114237Snjl CFGBlockValues &vals; 339114237Snjl const CFG &cfg; 340114237Snjl AnalysisDeclContext ∾ 341114237Snjl UninitVariablesHandler *handler; 342114237Snjl 343114237Snjl /// The last DeclRefExpr seen when analyzing a block. Used to 344114237Snjl /// cheat when detecting cases when the address of a variable is taken. 345114237Snjl DeclRefExpr *lastDR; 346114237Snjl 347114237Snjl /// The last lvalue-to-rvalue conversion of a variable whose value 348114237Snjl /// was uninitialized. Normally this results in a warning, but it is 349114237Snjl /// possible to either silence the warning in some cases, or we 350240716Sjkim /// propagate the uninitialized value. 351114237Snjl CastExpr *lastLoad; 352114237Snjl 353114237Snjl /// For some expressions, we want to ignore any post-processing after 354114237Snjl /// visitation. 355114237Snjl bool skipProcessUses; 356114237Snjl 357114237Snjlpublic: 358114237Snjl TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 359240716Sjkim AnalysisDeclContext &ac, 360123315Snjl UninitVariablesHandler *handler) 361114237Snjl : vals(vals), cfg(cfg), ac(ac), handler(handler), 362114237Snjl lastDR(0), lastLoad(0), 363114237Snjl skipProcessUses(false) {} 364114237Snjl 365114237Snjl void reportUninit(const DeclRefExpr *ex, const VarDecl *vd, 366114237Snjl bool isAlwaysUninit); 367114237Snjl 368114237Snjl void VisitBlockExpr(BlockExpr *be); 36967754Smsmith void VisitDeclStmt(DeclStmt *ds); 37067754Smsmith void VisitDeclRefExpr(DeclRefExpr *dr); 37167754Smsmith void VisitUnaryOperator(UnaryOperator *uo); 37267754Smsmith void VisitBinaryOperator(BinaryOperator *bo); 37367754Smsmith void VisitCastExpr(CastExpr *ce); 37467754Smsmith void VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); 375151937Sjkim void Visit(Stmt *s); 37667754Smsmith 377241973Sjkim bool isTrackedVar(const VarDecl *vd) { 37867754Smsmith return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 37967754Smsmith } 38067754Smsmith 38167754Smsmith FindVarResult findBlockVarDecl(Expr *ex); 38267754Smsmith 38367754Smsmith void ProcessUses(Stmt *s = 0); 384114237Snjl}; 385114237Snjl} 386222544Sjkim 38767754Smsmithstatic const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 38867754Smsmith while (Ex) { 38967754Smsmith Ex = Ex->IgnoreParenNoopCasts(C); 39069450Smsmith if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 391167802Sjkim if (CE->getCastKind() == CK_LValueBitCast) { 39269450Smsmith Ex = CE->getSubExpr(); 39369450Smsmith continue; 394102550Siwasaki } 39567754Smsmith } 39667754Smsmith break; 39767754Smsmith } 39867754Smsmith return Ex; 39967754Smsmith} 40067754Smsmith 40182367Smsmithvoid TransferFunctions::reportUninit(const DeclRefExpr *ex, 40269450Smsmith const VarDecl *vd, bool isAlwaysUnit) { 40367754Smsmith if (handler) handler->handleUseOfUninitVariable(ex, vd, isAlwaysUnit); 404114237Snjl} 405114237Snjl 406151937SjkimFindVarResult TransferFunctions::findBlockVarDecl(Expr *ex) { 407199337Sjkim if (DeclRefExpr *dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts())) 408114237Snjl if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 409114237Snjl if (isTrackedVar(vd)) 410114237Snjl return FindVarResult(vd, dr); 411114237Snjl return FindVarResult(0, 0); 412167802Sjkim} 413167802Sjkim 414167802Sjkimvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs) { 415167802Sjkim // This represents an initialization of the 'element' value. 416167802Sjkim Stmt *element = fs->getElement(); 417167802Sjkim const VarDecl *vd = 0; 418167802Sjkim 419167802Sjkim if (DeclStmt *ds = dyn_cast<DeclStmt>(element)) { 420167802Sjkim vd = cast<VarDecl>(ds->getSingleDecl()); 421167802Sjkim if (!isTrackedVar(vd)) 422167802Sjkim vd = 0; 423114237Snjl } else { 424222544Sjkim // Initialize the value of the reference variable. 425114237Snjl const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); 42667754Smsmith vd = res.getDecl(); 427114237Snjl } 428114237Snjl 429100966Siwasaki if (vd) 430114237Snjl vals[vd] = Initialized; 431239340Sjkim} 432239340Sjkim 433239340Sjkimvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 434239340Sjkim const BlockDecl *bd = be->getBlockDecl(); 435239340Sjkim for (BlockDecl::capture_const_iterator i = bd->capture_begin(), 436245582Sjkim e = bd->capture_end() ; i != e; ++i) { 437239340Sjkim const VarDecl *vd = i->getVariable(); 438245582Sjkim if (!isTrackedVar(vd)) 439239340Sjkim continue; 440167802Sjkim if (i->isByRef()) { 441114237Snjl vals[vd] = Initialized; 44267754Smsmith continue; 44382367Smsmith } 44482367Smsmith Value v = vals[vd]; 44582367Smsmith if (handler && isUninitialized(v)) 44682367Smsmith handler->handleUseOfUninitVariable(be, vd, isAlwaysUninit(v)); 447202771Sjkim } 44867754Smsmith} 449102550Siwasaki 45069450Smsmithvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 45167754Smsmith // Record the last DeclRefExpr seen. This is an lvalue computation. 45267754Smsmith // We use this value to later detect if a variable "escapes" the analysis. 45382367Smsmith if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 45467754Smsmith if (isTrackedVar(vd)) { 45591116Smsmith ProcessUses(); 45667754Smsmith lastDR = dr; 45767754Smsmith } 45867754Smsmith} 459240716Sjkim 460240716Sjkimvoid TransferFunctions::VisitDeclStmt(DeclStmt *ds) { 46167754Smsmith for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end(); 46269450Smsmith DI != DE; ++DI) { 46367754Smsmith if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) { 46467754Smsmith if (isTrackedVar(vd)) { 46567754Smsmith if (Expr *init = vd->getInit()) { 466240716Sjkim // If the initializer consists solely of a reference to itself, we 46783174Smsmith // explicitly mark the variable as uninitialized. This allows code 46867754Smsmith // like the following: 46967754Smsmith // 47067754Smsmith // int x = x; 47167754Smsmith // 47267754Smsmith // to deliberately leave a variable uninitialized. Different analysis 47367754Smsmith // clients can detect this pattern and adjust their reporting 47467754Smsmith // appropriately, but we need to continue to analyze subsequent uses 475240716Sjkim // of the variable. 476240716Sjkim if (init == lastLoad) { 477114237Snjl const DeclRefExpr *DR 478104470Siwasaki = cast<DeclRefExpr>(stripCasts(ac.getASTContext(), 479151937Sjkim lastLoad->getSubExpr())); 480239340Sjkim if (DR->getDecl() == vd) { 481239340Sjkim // int x = x; 482239340Sjkim // Propagate uninitialized value, but don't immediately report 483239340Sjkim // a problem. 484239340Sjkim vals[vd] = Uninitialized; 485239340Sjkim lastLoad = 0; 486239340Sjkim lastDR = 0; 487239340Sjkim if (handler) 48867754Smsmith handler->handleSelfInit(vd); 489100966Siwasaki return; 490100966Siwasaki } 491240716Sjkim } 492100966Siwasaki 493100966Siwasaki // All other cases: treat the new variable as initialized. 49467754Smsmith // This is a minor optimization to reduce the propagation 49567754Smsmith // of the analysis, since we will have already reported 49691116Smsmith // the use of the uninitialized value (which visiting the 49767754Smsmith // initializer). 49867754Smsmith vals[vd] = Initialized; 49967754Smsmith } 50067754Smsmith } 50167754Smsmith } 50267754Smsmith } 50367754Smsmith} 50467754Smsmith 50567754Smsmithvoid TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { 50667754Smsmith if (bo->isAssignmentOp()) { 50767754Smsmith const FindVarResult &res = findBlockVarDecl(bo->getLHS()); 508241973Sjkim if (const VarDecl *vd = res.getDecl()) { 50967754Smsmith ValueVector::reference val = vals[vd]; 51067754Smsmith if (isUninitialized(val)) { 51167754Smsmith if (bo->getOpcode() != BO_Assign) 51267754Smsmith reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 513151937Sjkim else 51467754Smsmith val = Initialized; 51567754Smsmith } 51667754Smsmith } 51767754Smsmith } 51891116Smsmith} 519193267Sjkim 52067754Smsmithvoid TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { 521167802Sjkim switch (uo->getOpcode()) { 52267754Smsmith case clang::UO_PostDec: 52367754Smsmith case clang::UO_PostInc: 52467754Smsmith case clang::UO_PreDec: 525193267Sjkim case clang::UO_PreInc: { 526193267Sjkim const FindVarResult &res = findBlockVarDecl(uo->getSubExpr()); 527193267Sjkim if (const VarDecl *vd = res.getDecl()) { 528193267Sjkim assert(res.getDeclRefExpr() == lastDR); 529193267Sjkim // We null out lastDR to indicate we have fully processed it 530193267Sjkim // and we don't want the auto-value setting in Visit(). 531193267Sjkim lastDR = 0; 532193267Sjkim 533193267Sjkim ValueVector::reference val = vals[vd]; 534193267Sjkim if (isUninitialized(val)) 535167802Sjkim reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 536167802Sjkim } 537237412Sjkim break; 538237412Sjkim } 539167802Sjkim default: 540167802Sjkim break; 541167802Sjkim } 542167802Sjkim} 543212761Sjkim 544167802Sjkimvoid TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { 545167802Sjkim if (ce->getCastKind() == CK_LValueToRValue) { 546193267Sjkim const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); 547193267Sjkim if (res.getDecl()) { 548193267Sjkim assert(res.getDeclRefExpr() == lastDR); 549193267Sjkim lastLoad = ce; 550193267Sjkim } 551193267Sjkim } 552193267Sjkim else if (ce->getCastKind() == CK_NoOp || 553222544Sjkim ce->getCastKind() == CK_LValueBitCast) { 554222544Sjkim skipProcessUses = true; 555193267Sjkim } 556193267Sjkim else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) { 55767754Smsmith if (cse->getType()->isVoidType()) { 55867754Smsmith // e.g. (void) x; 559193267Sjkim if (lastLoad == cse->getSubExpr()) { 560117521Snjl // Squelch any detected load of an uninitialized value if 56167754Smsmith // we cast it to void. 562240716Sjkim lastLoad = 0; 563117521Snjl lastDR = 0; 564127175Snjl } 565127175Snjl } 566127175Snjl } 567127175Snjl} 56867754Smsmith 569117521Snjlvoid TransferFunctions::Visit(clang::Stmt *s) { 570167802Sjkim skipProcessUses = false; 571128212Snjl StmtVisitor<TransferFunctions>::Visit(s); 572117521Snjl if (!skipProcessUses) 573240716Sjkim ProcessUses(s); 574117521Snjl} 575117521Snjl 576117521Snjlvoid TransferFunctions::ProcessUses(Stmt *s) { 577117521Snjl // This method is typically called after visiting a CFGElement statement 578240716Sjkim // in the CFG. We delay processing of reporting many loads of uninitialized 579117521Snjl // values until here. 580151937Sjkim if (lastLoad) { 581117521Snjl // If we just visited the lvalue-to-rvalue cast, there is nothing 582117521Snjl // left to do. 58367754Smsmith if (lastLoad == s) 58467754Smsmith return; 58567754Smsmith 58667754Smsmith const DeclRefExpr *DR = 587167802Sjkim cast<DeclRefExpr>(stripCasts(ac.getASTContext(), 588193267Sjkim lastLoad->getSubExpr())); 589167802Sjkim const VarDecl *VD = cast<VarDecl>(DR->getDecl()); 590167802Sjkim 591167802Sjkim // If we reach here, we may have seen a load of an uninitialized value 59299679Siwasaki // and it hasn't been casted to void or otherwise handled. In this 593167802Sjkim // situation, report the incident. 594167802Sjkim if (isUninitialized(vals[VD])) 59599679Siwasaki reportUninit(DR, VD, isAlwaysUninit(vals[VD])); 596167802Sjkim 597193267Sjkim lastLoad = 0; 598167802Sjkim 599167802Sjkim if (DR == lastDR) { 600167802Sjkim lastDR = 0; 601167802Sjkim return; 602167802Sjkim } 603167802Sjkim } 604167802Sjkim 605167802Sjkim // Any other uses of 'lastDR' involve taking an lvalue of variable. 606167802Sjkim // In this case, it "escapes" the analysis. 607167802Sjkim if (lastDR && lastDR != s) { 60867754Smsmith vals[cast<VarDecl>(lastDR->getDecl())] = Initialized; 60967754Smsmith lastDR = 0; 61067754Smsmith } 61167754Smsmith} 61267754Smsmith 61367754Smsmith//------------------------------------------------------------------------====// 61467754Smsmith// High-level "driver" logic for uninitialized values analysis. 61567754Smsmith//====------------------------------------------------------------------------// 61667754Smsmith 61767754Smsmithstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 61867754Smsmith AnalysisDeclContext &ac, CFGBlockValues &vals, 61967754Smsmith llvm::BitVector &wasAnalyzed, 62067754Smsmith UninitVariablesHandler *handler = 0) { 62167754Smsmith 62267754Smsmith wasAnalyzed[block->getBlockID()] = true; 62367754Smsmith 62467754Smsmith if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { 62567754Smsmith CFGBlock::const_pred_iterator itr = block->pred_begin(); 62667754Smsmith BVPair vA = vals.getValueVectors(*itr, false); 627114237Snjl ++itr; 628114237Snjl BVPair vB = vals.getValueVectors(*itr, false); 629114237Snjl 63067754Smsmith BVPair valsAB; 63167754Smsmith 63267754Smsmith if (b->getOpcode() == BO_LAnd) { 63367754Smsmith // Merge the 'F' bits from the first and second. 63467754Smsmith vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true); 635167802Sjkim vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false); 636167802Sjkim valsAB.first = vA.first; 637167802Sjkim valsAB.second = &vals.getScratch(); 638193267Sjkim } else { 63967754Smsmith // Merge the 'T' bits from the first and second. 640193267Sjkim assert(b->getOpcode() == BO_LOr); 64167754Smsmith vals.mergeIntoScratch(*vA.first, true); 64267754Smsmith vals.mergeIntoScratch(*vB.first, false); 64391116Smsmith valsAB.first = &vals.getScratch(); 64491116Smsmith valsAB.second = vA.second ? vA.second : vA.first; 64567754Smsmith } 64667754Smsmith return vals.updateValueVectors(block, valsAB); 64767754Smsmith } 648151937Sjkim 649151937Sjkim // Default behavior: merge in values of predecessor blocks. 65067754Smsmith vals.resetScratch(); 65167754Smsmith bool isFirst = true; 65267754Smsmith for (CFGBlock::const_pred_iterator I = block->pred_begin(), 653167802Sjkim E = block->pred_end(); I != E; ++I) { 654167802Sjkim const CFGBlock *pred = *I; 655167802Sjkim if (wasAnalyzed[pred->getBlockID()]) { 656167802Sjkim vals.mergeIntoScratch(vals.getValueVector(pred, block), isFirst); 657167802Sjkim isFirst = false; 658167802Sjkim } 659167802Sjkim } 660167802Sjkim // Apply the transfer function. 661167802Sjkim TransferFunctions tf(vals, cfg, ac, handler); 662167802Sjkim for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 663167802Sjkim I != E; ++I) { 66467754Smsmith if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { 665167802Sjkim tf.Visit(const_cast<Stmt*>(cs->getStmt())); 666167802Sjkim } 667167802Sjkim } 668167802Sjkim tf.ProcessUses(); 669167802Sjkim return vals.updateValueVectorWithScratch(block); 67067754Smsmith} 67167754Smsmith 672167802Sjkimvoid clang::runUninitializedVariablesAnalysis( 673151937Sjkim const DeclContext &dc, 674167802Sjkim const CFG &cfg, 67567754Smsmith AnalysisDeclContext &ac, 67667754Smsmith UninitVariablesHandler &handler, 67767754Smsmith UninitVariablesAnalysisStats &stats) { 678193267Sjkim CFGBlockValues vals(cfg); 679193267Sjkim vals.computeSetOfDeclarations(dc); 680193267Sjkim if (vals.hasNoDeclarations()) 681193267Sjkim return; 682193267Sjkim 683193267Sjkim stats.NumVariablesAnalyzed = vals.getNumEntries(); 684193267Sjkim 685193267Sjkim // Mark all variables uninitialized at the entry. 686193267Sjkim const CFGBlock &entry = cfg.getEntry(); 687193267Sjkim for (CFGBlock::const_succ_iterator i = entry.succ_begin(), 688167802Sjkim e = entry.succ_end(); i != e; ++i) { 689167802Sjkim if (const CFGBlock *succ = *i) { 690167802Sjkim ValueVector &vec = vals.getValueVector(&entry, succ); 691167802Sjkim const unsigned n = vals.getNumEntries(); 692167802Sjkim for (unsigned j = 0; j < n ; ++j) { 693212761Sjkim vec[j] = Uninitialized; 694212761Sjkim } 695167802Sjkim } 696167802Sjkim } 697167802Sjkim 698167802Sjkim // Proceed with the workist. 699167802Sjkim DataflowWorklist worklist(cfg); 700193267Sjkim llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 701167802Sjkim worklist.enqueueSuccessors(&cfg.getEntry()); 702167802Sjkim llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 703167802Sjkim wasAnalyzed[cfg.getEntry().getBlockID()] = true; 704167802Sjkim 70567754Smsmith while (const CFGBlock *block = worklist.dequeue()) { 70667754Smsmith // Did the block change? 70783174Smsmith bool changed = runOnBlock(block, cfg, ac, vals, wasAnalyzed); 70883174Smsmith ++stats.NumBlockVisits; 70983174Smsmith if (changed || !previouslyVisited[block->getBlockID()]) 710167802Sjkim worklist.enqueueSuccessors(block); 711167802Sjkim previouslyVisited[block->getBlockID()] = true; 712193267Sjkim } 71367754Smsmith 714167802Sjkim // Run through the blocks one more time, and report uninitialized variabes. 715167802Sjkim for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 716167802Sjkim const CFGBlock *block = *BI; 717167802Sjkim if (wasAnalyzed[block->getBlockID()]) { 718167802Sjkim runOnBlock(block, cfg, ac, vals, wasAnalyzed, &handler); 719167802Sjkim ++stats.NumBlockVisits; 720167802Sjkim } 721167802Sjkim } 722222544Sjkim} 723222544Sjkim 724222544SjkimUninitVariablesHandler::~UninitVariablesHandler() {} 725222544Sjkim