UninitializedValues.cpp revision 224145
1193326Sed//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// 2193326Sed// 3193326Sed// The LLVM Compiler Infrastructure 4193326Sed// 5193326Sed// This file is distributed under the University of Illinois Open Source 6193326Sed// License. See LICENSE.TXT for details. 7193326Sed// 8193326Sed//===----------------------------------------------------------------------===// 9193326Sed// 10221345Sdim// This file implements uninitialized values analysis for source-level CFGs. 11193326Sed// 12193326Sed//===----------------------------------------------------------------------===// 13193326Sed 14221345Sdim#include <utility> 15221345Sdim#include "llvm/ADT/Optional.h" 16221345Sdim#include "llvm/ADT/SmallVector.h" 17223017Sdim#include "llvm/ADT/PackedVector.h" 18221345Sdim#include "llvm/ADT/DenseMap.h" 19221345Sdim#include "clang/AST/Decl.h" 20221345Sdim#include "clang/Analysis/CFG.h" 21221345Sdim#include "clang/Analysis/AnalysisContext.h" 22221345Sdim#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 23193326Sed#include "clang/Analysis/Analyses/UninitializedValues.h" 24221345Sdim#include "clang/Analysis/Support/SaveAndRestore.h" 25193326Sed 26193326Sedusing namespace clang; 27193326Sed 28221345Sdimstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 29221345Sdim if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 30221345Sdim !vd->isExceptionVariable() && 31221345Sdim vd->getDeclContext() == dc) { 32221345Sdim QualType ty = vd->getType(); 33221345Sdim return ty->isScalarType() || ty->isVectorType(); 34221345Sdim } 35221345Sdim return false; 36221345Sdim} 37193326Sed 38221345Sdim//------------------------------------------------------------------------====// 39221345Sdim// DeclToIndex: a mapping from Decls we track to value indices. 40221345Sdim//====------------------------------------------------------------------------// 41221345Sdim 42193326Sednamespace { 43221345Sdimclass DeclToIndex { 44221345Sdim llvm::DenseMap<const VarDecl *, unsigned> map; 45221345Sdimpublic: 46221345Sdim DeclToIndex() {} 47221345Sdim 48221345Sdim /// Compute the actual mapping from declarations to bits. 49221345Sdim void computeMap(const DeclContext &dc); 50221345Sdim 51221345Sdim /// Return the number of declarations in the map. 52221345Sdim unsigned size() const { return map.size(); } 53221345Sdim 54221345Sdim /// Returns the bit vector index for a given declaration. 55221345Sdim llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const; 56221345Sdim}; 57221345Sdim} 58193326Sed 59221345Sdimvoid DeclToIndex::computeMap(const DeclContext &dc) { 60221345Sdim unsigned count = 0; 61221345Sdim DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 62221345Sdim E(dc.decls_end()); 63221345Sdim for ( ; I != E; ++I) { 64221345Sdim const VarDecl *vd = *I; 65221345Sdim if (isTrackedVar(vd, &dc)) 66221345Sdim map[vd] = count++; 67221345Sdim } 68221345Sdim} 69193326Sed 70221345Sdimllvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 71221345Sdim llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 72221345Sdim if (I == map.end()) 73221345Sdim return llvm::Optional<unsigned>(); 74221345Sdim return I->second; 75221345Sdim} 76198092Srdivacky 77221345Sdim//------------------------------------------------------------------------====// 78221345Sdim// CFGBlockValues: dataflow values for CFG blocks. 79221345Sdim//====------------------------------------------------------------------------// 80198092Srdivacky 81221345Sdim// These values are defined in such a way that a merge can be done using 82221345Sdim// a bitwise OR. 83221345Sdimenum Value { Unknown = 0x0, /* 00 */ 84221345Sdim Initialized = 0x1, /* 01 */ 85221345Sdim Uninitialized = 0x2, /* 10 */ 86221345Sdim MayUninitialized = 0x3 /* 11 */ }; 87193326Sed 88221345Sdimstatic bool isUninitialized(const Value v) { 89221345Sdim return v >= Uninitialized; 90193326Sed} 91221345Sdimstatic bool isAlwaysUninit(const Value v) { 92221345Sdim return v == Uninitialized; 93221345Sdim} 94193326Sed 95193326Sednamespace { 96198092Srdivacky 97223017Sdimtypedef llvm::PackedVector<Value, 2> ValueVector; 98221345Sdimtypedef std::pair<ValueVector *, ValueVector *> BVPair; 99221345Sdim 100221345Sdimclass CFGBlockValues { 101221345Sdim const CFG &cfg; 102221345Sdim BVPair *vals; 103221345Sdim ValueVector scratch; 104221345Sdim DeclToIndex declToIndex; 105221345Sdim 106221345Sdim ValueVector &lazyCreate(ValueVector *&bv); 107193326Sedpublic: 108221345Sdim CFGBlockValues(const CFG &cfg); 109221345Sdim ~CFGBlockValues(); 110221345Sdim 111221345Sdim unsigned getNumEntries() const { return declToIndex.size(); } 112221345Sdim 113221345Sdim void computeSetOfDeclarations(const DeclContext &dc); 114221345Sdim ValueVector &getValueVector(const CFGBlock *block, 115221345Sdim const CFGBlock *dstBlock); 116198092Srdivacky 117221345Sdim BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate); 118198092Srdivacky 119221345Sdim void mergeIntoScratch(ValueVector const &source, bool isFirst); 120221345Sdim bool updateValueVectorWithScratch(const CFGBlock *block); 121221345Sdim bool updateValueVectors(const CFGBlock *block, const BVPair &newVals); 122221345Sdim 123221345Sdim bool hasNoDeclarations() const { 124221345Sdim return declToIndex.size() == 0; 125193326Sed } 126221345Sdim 127221345Sdim bool hasEntry(const VarDecl *vd) const { 128221345Sdim return declToIndex.getValueIndex(vd).hasValue(); 129221345Sdim } 130221345Sdim 131221345Sdim bool hasValues(const CFGBlock *block); 132221345Sdim 133221345Sdim void resetScratch(); 134221345Sdim ValueVector &getScratch() { return scratch; } 135221345Sdim 136221345Sdim ValueVector::reference operator[](const VarDecl *vd); 137221345Sdim}; 138221345Sdim} // end anonymous namespace 139198092Srdivacky 140221345SdimCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { 141221345Sdim unsigned n = cfg.getNumBlockIDs(); 142221345Sdim if (!n) 143221345Sdim return; 144221345Sdim vals = new std::pair<ValueVector*, ValueVector*>[n]; 145221345Sdim memset((void*)vals, 0, sizeof(*vals) * n); 146221345Sdim} 147198092Srdivacky 148221345SdimCFGBlockValues::~CFGBlockValues() { 149221345Sdim unsigned n = cfg.getNumBlockIDs(); 150221345Sdim if (n == 0) 151221345Sdim return; 152221345Sdim for (unsigned i = 0; i < n; ++i) { 153221345Sdim delete vals[i].first; 154221345Sdim delete vals[i].second; 155221345Sdim } 156221345Sdim delete [] vals; 157221345Sdim} 158198092Srdivacky 159221345Sdimvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 160221345Sdim declToIndex.computeMap(dc); 161221345Sdim scratch.resize(declToIndex.size()); 162221345Sdim} 163198092Srdivacky 164221345SdimValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) { 165221345Sdim if (!bv) 166221345Sdim bv = new ValueVector(declToIndex.size()); 167221345Sdim return *bv; 168221345Sdim} 169193326Sed 170221345Sdim/// This function pattern matches for a '&&' or '||' that appears at 171221345Sdim/// the beginning of a CFGBlock that also (1) has a terminator and 172221345Sdim/// (2) has no other elements. If such an expression is found, it is returned. 173221345Sdimstatic BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) { 174221345Sdim if (block->empty()) 175221345Sdim return 0; 176198092Srdivacky 177221345Sdim const CFGStmt *cstmt = block->front().getAs<CFGStmt>(); 178221345Sdim if (!cstmt) 179221345Sdim return 0; 180198092Srdivacky 181221345Sdim BinaryOperator *b = llvm::dyn_cast_or_null<BinaryOperator>(cstmt->getStmt()); 182221345Sdim 183221345Sdim if (!b || !b->isLogicalOp()) 184221345Sdim return 0; 185221345Sdim 186223017Sdim if (block->pred_size() == 2) { 187223017Sdim if (block->getTerminatorCondition() == b) { 188223017Sdim if (block->succ_size() == 2) 189223017Sdim return b; 190223017Sdim } 191223017Sdim else if (block->size() == 1) 192223017Sdim return b; 193223017Sdim } 194223017Sdim 195221345Sdim return 0; 196221345Sdim} 197198092Srdivacky 198221345SdimValueVector &CFGBlockValues::getValueVector(const CFGBlock *block, 199221345Sdim const CFGBlock *dstBlock) { 200221345Sdim unsigned idx = block->getBlockID(); 201221345Sdim if (dstBlock && getLogicalOperatorInChain(block)) { 202221345Sdim if (*block->succ_begin() == dstBlock) 203221345Sdim return lazyCreate(vals[idx].first); 204221345Sdim assert(*(block->succ_begin()+1) == dstBlock); 205221345Sdim return lazyCreate(vals[idx].second); 206221345Sdim } 207193326Sed 208221345Sdim assert(vals[idx].second == 0); 209221345Sdim return lazyCreate(vals[idx].first); 210221345Sdim} 211198092Srdivacky 212221345Sdimbool CFGBlockValues::hasValues(const CFGBlock *block) { 213221345Sdim unsigned idx = block->getBlockID(); 214221345Sdim return vals[idx].second != 0; 215193326Sed} 216193326Sed 217221345SdimBVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block, 218221345Sdim bool shouldLazyCreate) { 219221345Sdim unsigned idx = block->getBlockID(); 220221345Sdim lazyCreate(vals[idx].first); 221221345Sdim if (shouldLazyCreate) 222221345Sdim lazyCreate(vals[idx].second); 223221345Sdim return vals[idx]; 224221345Sdim} 225198092Srdivacky 226221345Sdimvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 227221345Sdim bool isFirst) { 228221345Sdim if (isFirst) 229221345Sdim scratch = source; 230221345Sdim else 231223017Sdim scratch |= source; 232221345Sdim} 233221345Sdim#if 0 234221345Sdimstatic void printVector(const CFGBlock *block, ValueVector &bv, 235221345Sdim unsigned num) { 236221345Sdim 237221345Sdim llvm::errs() << block->getBlockID() << " :"; 238221345Sdim for (unsigned i = 0; i < bv.size(); ++i) { 239221345Sdim llvm::errs() << ' ' << bv[i]; 240221345Sdim } 241221345Sdim llvm::errs() << " : " << num << '\n'; 242221345Sdim} 243221345Sdim#endif 244198092Srdivacky 245221345Sdimbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 246221345Sdim ValueVector &dst = getValueVector(block, 0); 247221345Sdim bool changed = (dst != scratch); 248221345Sdim if (changed) 249221345Sdim dst = scratch; 250221345Sdim#if 0 251221345Sdim printVector(block, scratch, 0); 252221345Sdim#endif 253221345Sdim return changed; 254221345Sdim} 255193326Sed 256221345Sdimbool CFGBlockValues::updateValueVectors(const CFGBlock *block, 257221345Sdim const BVPair &newVals) { 258221345Sdim BVPair &vals = getValueVectors(block, true); 259221345Sdim bool changed = *newVals.first != *vals.first || 260221345Sdim *newVals.second != *vals.second; 261221345Sdim *vals.first = *newVals.first; 262221345Sdim *vals.second = *newVals.second; 263221345Sdim#if 0 264221345Sdim printVector(block, *vals.first, 1); 265221345Sdim printVector(block, *vals.second, 2); 266221345Sdim#endif 267221345Sdim return changed; 268193326Sed} 269193326Sed 270221345Sdimvoid CFGBlockValues::resetScratch() { 271221345Sdim scratch.reset(); 272221345Sdim} 273193326Sed 274221345SdimValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 275221345Sdim const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 276221345Sdim assert(idx.hasValue()); 277221345Sdim return scratch[idx.getValue()]; 278221345Sdim} 279193326Sed 280221345Sdim//------------------------------------------------------------------------====// 281221345Sdim// Worklist: worklist for dataflow analysis. 282221345Sdim//====------------------------------------------------------------------------// 283221345Sdim 284221345Sdimnamespace { 285221345Sdimclass DataflowWorklist { 286221345Sdim llvm::SmallVector<const CFGBlock *, 20> worklist; 287221345Sdim llvm::BitVector enqueuedBlocks; 288221345Sdimpublic: 289221345Sdim DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} 290221345Sdim 291221345Sdim void enqueueSuccessors(const CFGBlock *block); 292221345Sdim const CFGBlock *dequeue(); 293221345Sdim}; 294193326Sed} 295193326Sed 296221345Sdimvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 297224145Sdim unsigned OldWorklistSize = worklist.size(); 298221345Sdim for (CFGBlock::const_succ_iterator I = block->succ_begin(), 299221345Sdim E = block->succ_end(); I != E; ++I) { 300224145Sdim const CFGBlock *Successor = *I; 301224145Sdim if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 302224145Sdim continue; 303224145Sdim worklist.push_back(Successor); 304224145Sdim enqueuedBlocks[Successor->getBlockID()] = true; 305193326Sed } 306224145Sdim if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 307224145Sdim return; 308224145Sdim 309224145Sdim // Rotate the newly added blocks to the start of the worklist so that it forms 310224145Sdim // a proper queue when we pop off the end of the worklist. 311224145Sdim std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize, 312224145Sdim worklist.end()); 313193326Sed} 314198092Srdivacky 315221345Sdimconst CFGBlock *DataflowWorklist::dequeue() { 316221345Sdim if (worklist.empty()) 317221345Sdim return 0; 318221345Sdim const CFGBlock *b = worklist.back(); 319221345Sdim worklist.pop_back(); 320221345Sdim enqueuedBlocks[b->getBlockID()] = false; 321221345Sdim return b; 322193326Sed} 323193326Sed 324221345Sdim//------------------------------------------------------------------------====// 325221345Sdim// Transfer function for uninitialized values analysis. 326221345Sdim//====------------------------------------------------------------------------// 327198092Srdivacky 328221345Sdimnamespace { 329221345Sdimclass FindVarResult { 330221345Sdim const VarDecl *vd; 331221345Sdim const DeclRefExpr *dr; 332221345Sdimpublic: 333221345Sdim FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {} 334221345Sdim 335221345Sdim const DeclRefExpr *getDeclRefExpr() const { return dr; } 336221345Sdim const VarDecl *getDecl() const { return vd; } 337221345Sdim}; 338221345Sdim 339221345Sdimclass TransferFunctions : public CFGRecStmtVisitor<TransferFunctions> { 340221345Sdim CFGBlockValues &vals; 341221345Sdim const CFG &cfg; 342221345Sdim AnalysisContext ∾ 343221345Sdim UninitVariablesHandler *handler; 344221345Sdim const DeclRefExpr *currentDR; 345221345Sdim const Expr *currentVoidCast; 346221345Sdim const bool flagBlockUses; 347221345Sdimpublic: 348221345Sdim TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 349221345Sdim AnalysisContext &ac, 350221345Sdim UninitVariablesHandler *handler, 351221345Sdim bool flagBlockUses) 352221345Sdim : vals(vals), cfg(cfg), ac(ac), handler(handler), currentDR(0), 353221345Sdim currentVoidCast(0), flagBlockUses(flagBlockUses) {} 354221345Sdim 355221345Sdim const CFG &getCFG() { return cfg; } 356221345Sdim void reportUninit(const DeclRefExpr *ex, const VarDecl *vd, 357221345Sdim bool isAlwaysUninit); 358221345Sdim 359221345Sdim void VisitBlockExpr(BlockExpr *be); 360221345Sdim void VisitDeclStmt(DeclStmt *ds); 361221345Sdim void VisitDeclRefExpr(DeclRefExpr *dr); 362221345Sdim void VisitUnaryOperator(UnaryOperator *uo); 363221345Sdim void VisitBinaryOperator(BinaryOperator *bo); 364221345Sdim void VisitCastExpr(CastExpr *ce); 365221345Sdim void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *se); 366221345Sdim void VisitCXXTypeidExpr(CXXTypeidExpr *E); 367221345Sdim void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); 368221345Sdim 369221345Sdim bool isTrackedVar(const VarDecl *vd) { 370221345Sdim return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 371193326Sed } 372221345Sdim 373221345Sdim FindVarResult findBlockVarDecl(Expr *ex); 374221345Sdim}; 375221345Sdim} 376193326Sed 377221345Sdimvoid TransferFunctions::reportUninit(const DeclRefExpr *ex, 378221345Sdim const VarDecl *vd, bool isAlwaysUnit) { 379221345Sdim if (handler) handler->handleUseOfUninitVariable(ex, vd, isAlwaysUnit); 380193326Sed} 381198092Srdivacky 382221345SdimFindVarResult TransferFunctions::findBlockVarDecl(Expr* ex) { 383221345Sdim if (DeclRefExpr* dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts())) 384221345Sdim if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 385221345Sdim if (isTrackedVar(vd)) 386221345Sdim return FindVarResult(vd, dr); 387221345Sdim return FindVarResult(0, 0); 388221345Sdim} 389193326Sed 390221345Sdimvoid TransferFunctions::BlockStmt_VisitObjCForCollectionStmt( 391221345Sdim ObjCForCollectionStmt *fs) { 392221345Sdim 393221345Sdim Visit(fs->getCollection()); 394221345Sdim 395193326Sed // This represents an initialization of the 'element' value. 396221345Sdim Stmt *element = fs->getElement(); 397221345Sdim const VarDecl* vd = 0; 398221345Sdim 399221345Sdim if (DeclStmt* ds = dyn_cast<DeclStmt>(element)) { 400221345Sdim vd = cast<VarDecl>(ds->getSingleDecl()); 401221345Sdim if (!isTrackedVar(vd)) 402221345Sdim vd = 0; 403221345Sdim } 404193326Sed else { 405193326Sed // Initialize the value of the reference variable. 406221345Sdim const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); 407221345Sdim vd = res.getDecl(); 408221345Sdim if (!vd) { 409221345Sdim Visit(element); 410221345Sdim return; 411221345Sdim } 412193326Sed } 413221345Sdim 414221345Sdim if (vd) 415221345Sdim vals[vd] = Initialized; 416221345Sdim} 417198092Srdivacky 418221345Sdimvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 419221345Sdim if (!flagBlockUses || !handler) 420221345Sdim return; 421221345Sdim const BlockDecl *bd = be->getBlockDecl(); 422221345Sdim for (BlockDecl::capture_const_iterator i = bd->capture_begin(), 423221345Sdim e = bd->capture_end() ; i != e; ++i) { 424221345Sdim const VarDecl *vd = i->getVariable(); 425221345Sdim if (!vd->hasLocalStorage()) 426221345Sdim continue; 427221345Sdim if (!isTrackedVar(vd)) 428221345Sdim continue; 429221345Sdim if (i->isByRef()) { 430221345Sdim vals[vd] = Initialized; 431221345Sdim continue; 432221345Sdim } 433221345Sdim Value v = vals[vd]; 434221345Sdim if (isUninitialized(v)) 435221345Sdim handler->handleUseOfUninitVariable(be, vd, isAlwaysUninit(v)); 436221345Sdim } 437193326Sed} 438198092Srdivacky 439221345Sdimvoid TransferFunctions::VisitDeclStmt(DeclStmt *ds) { 440221345Sdim for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end(); 441221345Sdim DI != DE; ++DI) { 442221345Sdim if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) { 443221345Sdim if (isTrackedVar(vd)) { 444221345Sdim if (Expr *init = vd->getInit()) { 445221345Sdim Visit(init); 446198092Srdivacky 447221345Sdim // If the initializer consists solely of a reference to itself, we 448221345Sdim // explicitly mark the variable as uninitialized. This allows code 449221345Sdim // like the following: 450221345Sdim // 451221345Sdim // int x = x; 452221345Sdim // 453221345Sdim // to deliberately leave a variable uninitialized. Different analysis 454221345Sdim // clients can detect this pattern and adjust their reporting 455221345Sdim // appropriately, but we need to continue to analyze subsequent uses 456221345Sdim // of the variable. 457221345Sdim DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(init->IgnoreParenImpCasts()); 458221345Sdim vals[vd] = (DRE && DRE->getDecl() == vd) ? Uninitialized 459221345Sdim : Initialized; 460221345Sdim } 461221345Sdim } else if (Stmt *init = vd->getInit()) { 462221345Sdim Visit(init); 463221345Sdim } 464221345Sdim } 465221345Sdim } 466221345Sdim} 467193326Sed 468221345Sdimvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 469221345Sdim // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast 470221345Sdim // cannot be block-level expressions. Therefore, we determine if 471221345Sdim // a DeclRefExpr is involved in a "load" by comparing it to the current 472221345Sdim // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 473221345Sdim // If a DeclRefExpr is not involved in a load, we are essentially computing 474221345Sdim // its address, either for assignment to a reference or via the '&' operator. 475221345Sdim // In such cases, treat the variable as being initialized, since this 476221345Sdim // analysis isn't powerful enough to do alias tracking. 477221345Sdim if (dr != currentDR) 478221345Sdim if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 479221345Sdim if (isTrackedVar(vd)) 480221345Sdim vals[vd] = Initialized; 481193326Sed} 482193326Sed 483221345Sdimvoid TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { 484221345Sdim if (bo->isAssignmentOp()) { 485221345Sdim const FindVarResult &res = findBlockVarDecl(bo->getLHS()); 486221345Sdim if (const VarDecl* vd = res.getDecl()) { 487221345Sdim // We assume that DeclRefExprs wrapped in a BinaryOperator "assignment" 488221345Sdim // cannot be block-level expressions. Therefore, we determine if 489221345Sdim // a DeclRefExpr is involved in a "load" by comparing it to the current 490221345Sdim // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 491221345Sdim SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 492221345Sdim res.getDeclRefExpr()); 493221345Sdim Visit(bo->getRHS()); 494221345Sdim Visit(bo->getLHS()); 495193326Sed 496221345Sdim ValueVector::reference val = vals[vd]; 497221345Sdim if (isUninitialized(val)) { 498221345Sdim if (bo->getOpcode() != BO_Assign) 499221345Sdim reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 500221345Sdim val = Initialized; 501221345Sdim } 502221345Sdim return; 503221345Sdim } 504221345Sdim } 505221345Sdim Visit(bo->getRHS()); 506221345Sdim Visit(bo->getLHS()); 507221345Sdim} 508198092Srdivacky 509221345Sdimvoid TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { 510221345Sdim switch (uo->getOpcode()) { 511221345Sdim case clang::UO_PostDec: 512221345Sdim case clang::UO_PostInc: 513221345Sdim case clang::UO_PreDec: 514221345Sdim case clang::UO_PreInc: { 515221345Sdim const FindVarResult &res = findBlockVarDecl(uo->getSubExpr()); 516221345Sdim if (const VarDecl *vd = res.getDecl()) { 517221345Sdim // We assume that DeclRefExprs wrapped in a unary operator ++/-- 518221345Sdim // cannot be block-level expressions. Therefore, we determine if 519221345Sdim // a DeclRefExpr is involved in a "load" by comparing it to the current 520221345Sdim // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 521221345Sdim SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 522221345Sdim res.getDeclRefExpr()); 523221345Sdim Visit(uo->getSubExpr()); 524221345Sdim 525221345Sdim ValueVector::reference val = vals[vd]; 526221345Sdim if (isUninitialized(val)) { 527221345Sdim reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 528221345Sdim // Don't cascade warnings. 529221345Sdim val = Initialized; 530221345Sdim } 531221345Sdim return; 532221345Sdim } 533221345Sdim break; 534221345Sdim } 535221345Sdim default: 536221345Sdim break; 537221345Sdim } 538221345Sdim Visit(uo->getSubExpr()); 539193326Sed} 540198092Srdivacky 541221345Sdimvoid TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { 542221345Sdim if (ce->getCastKind() == CK_LValueToRValue) { 543221345Sdim const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); 544221345Sdim if (const VarDecl *vd = res.getDecl()) { 545221345Sdim // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast 546221345Sdim // cannot be block-level expressions. Therefore, we determine if 547221345Sdim // a DeclRefExpr is involved in a "load" by comparing it to the current 548221345Sdim // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 549221345Sdim // Here we update 'currentDR' to be the one associated with this 550221345Sdim // lvalue-to-rvalue cast. Then, when we analyze the DeclRefExpr, we 551221345Sdim // will know that we are not computing its lvalue for other purposes 552221345Sdim // than to perform a load. 553221345Sdim SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 554221345Sdim res.getDeclRefExpr()); 555221345Sdim Visit(ce->getSubExpr()); 556221345Sdim if (currentVoidCast != ce) { 557221345Sdim Value val = vals[vd]; 558221345Sdim if (isUninitialized(val)) { 559221345Sdim reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 560221345Sdim // Don't cascade warnings. 561221345Sdim vals[vd] = Initialized; 562221345Sdim } 563221345Sdim } 564221345Sdim return; 565221345Sdim } 566221345Sdim } 567221345Sdim else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) { 568221345Sdim if (cse->getType()->isVoidType()) { 569221345Sdim // e.g. (void) x; 570221345Sdim SaveAndRestore<const Expr *> 571221345Sdim lastVoidCast(currentVoidCast, cse->getSubExpr()->IgnoreParens()); 572221345Sdim Visit(cse->getSubExpr()); 573221345Sdim return; 574221345Sdim } 575221345Sdim } 576221345Sdim Visit(ce->getSubExpr()); 577193326Sed} 578193326Sed 579221345Sdimvoid TransferFunctions::VisitUnaryExprOrTypeTraitExpr( 580221345Sdim UnaryExprOrTypeTraitExpr *se) { 581221345Sdim if (se->getKind() == UETT_SizeOf) { 582221345Sdim if (se->getType()->isConstantSizeType()) 583221345Sdim return; 584221345Sdim // Handle VLAs. 585221345Sdim Visit(se->getArgumentExpr()); 586221345Sdim } 587193326Sed} 588198092Srdivacky 589221345Sdimvoid TransferFunctions::VisitCXXTypeidExpr(CXXTypeidExpr *E) { 590221345Sdim // typeid(expression) is potentially evaluated when the argument is 591221345Sdim // a glvalue of polymorphic type. (C++ 5.2.8p2-3) 592221345Sdim if (!E->isTypeOperand() && E->Classify(ac.getASTContext()).isGLValue()) { 593221345Sdim QualType SubExprTy = E->getExprOperand()->getType(); 594221345Sdim if (const RecordType *Record = SubExprTy->getAs<RecordType>()) 595221345Sdim if (cast<CXXRecordDecl>(Record->getDecl())->isPolymorphic()) 596221345Sdim Visit(E->getExprOperand()); 597221345Sdim } 598193326Sed} 599193326Sed 600221345Sdim//------------------------------------------------------------------------====// 601221345Sdim// High-level "driver" logic for uninitialized values analysis. 602221345Sdim//====------------------------------------------------------------------------// 603193326Sed 604221345Sdimstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 605221345Sdim AnalysisContext &ac, CFGBlockValues &vals, 606221345Sdim llvm::BitVector &wasAnalyzed, 607221345Sdim UninitVariablesHandler *handler = 0, 608221345Sdim bool flagBlockUses = false) { 609221345Sdim 610221345Sdim wasAnalyzed[block->getBlockID()] = true; 611221345Sdim 612221345Sdim if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { 613221345Sdim CFGBlock::const_pred_iterator itr = block->pred_begin(); 614221345Sdim BVPair vA = vals.getValueVectors(*itr, false); 615221345Sdim ++itr; 616221345Sdim BVPair vB = vals.getValueVectors(*itr, false); 617193326Sed 618221345Sdim BVPair valsAB; 619221345Sdim 620221345Sdim if (b->getOpcode() == BO_LAnd) { 621221345Sdim // Merge the 'F' bits from the first and second. 622221345Sdim vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true); 623221345Sdim vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false); 624221345Sdim valsAB.first = vA.first; 625221345Sdim valsAB.second = &vals.getScratch(); 626221345Sdim } 627221345Sdim else { 628221345Sdim // Merge the 'T' bits from the first and second. 629221345Sdim assert(b->getOpcode() == BO_LOr); 630221345Sdim vals.mergeIntoScratch(*vA.first, true); 631221345Sdim vals.mergeIntoScratch(*vB.first, false); 632221345Sdim valsAB.first = &vals.getScratch(); 633221345Sdim valsAB.second = vA.second ? vA.second : vA.first; 634221345Sdim } 635221345Sdim return vals.updateValueVectors(block, valsAB); 636221345Sdim } 637198092Srdivacky 638221345Sdim // Default behavior: merge in values of predecessor blocks. 639221345Sdim vals.resetScratch(); 640221345Sdim bool isFirst = true; 641221345Sdim for (CFGBlock::const_pred_iterator I = block->pred_begin(), 642221345Sdim E = block->pred_end(); I != E; ++I) { 643221345Sdim vals.mergeIntoScratch(vals.getValueVector(*I, block), isFirst); 644221345Sdim isFirst = false; 645221345Sdim } 646221345Sdim // Apply the transfer function. 647221345Sdim TransferFunctions tf(vals, cfg, ac, handler, flagBlockUses); 648221345Sdim for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 649221345Sdim I != E; ++I) { 650221345Sdim if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { 651221345Sdim tf.BlockStmt_Visit(cs->getStmt()); 652221345Sdim } 653221345Sdim } 654221345Sdim return vals.updateValueVectorWithScratch(block); 655221345Sdim} 656198092Srdivacky 657224145Sdimvoid clang::runUninitializedVariablesAnalysis( 658224145Sdim const DeclContext &dc, 659224145Sdim const CFG &cfg, 660224145Sdim AnalysisContext &ac, 661224145Sdim UninitVariablesHandler &handler, 662224145Sdim UninitVariablesAnalysisStats &stats) { 663221345Sdim CFGBlockValues vals(cfg); 664221345Sdim vals.computeSetOfDeclarations(dc); 665221345Sdim if (vals.hasNoDeclarations()) 666221345Sdim return; 667198092Srdivacky 668224145Sdim stats.NumVariablesAnalyzed = vals.getNumEntries(); 669224145Sdim 670221345Sdim // Mark all variables uninitialized at the entry. 671221345Sdim const CFGBlock &entry = cfg.getEntry(); 672221345Sdim for (CFGBlock::const_succ_iterator i = entry.succ_begin(), 673221345Sdim e = entry.succ_end(); i != e; ++i) { 674221345Sdim if (const CFGBlock *succ = *i) { 675221345Sdim ValueVector &vec = vals.getValueVector(&entry, succ); 676221345Sdim const unsigned n = vals.getNumEntries(); 677221345Sdim for (unsigned j = 0; j < n ; ++j) { 678221345Sdim vec[j] = Uninitialized; 679221345Sdim } 680221345Sdim } 681221345Sdim } 682193326Sed 683221345Sdim // Proceed with the workist. 684221345Sdim DataflowWorklist worklist(cfg); 685221345Sdim llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 686221345Sdim worklist.enqueueSuccessors(&cfg.getEntry()); 687221345Sdim llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 688198092Srdivacky 689221345Sdim while (const CFGBlock *block = worklist.dequeue()) { 690221345Sdim // Did the block change? 691224145Sdim bool changed = runOnBlock(block, cfg, ac, vals, wasAnalyzed); 692224145Sdim ++stats.NumBlockVisits; 693221345Sdim if (changed || !previouslyVisited[block->getBlockID()]) 694221345Sdim worklist.enqueueSuccessors(block); 695221345Sdim previouslyVisited[block->getBlockID()] = true; 696193326Sed } 697221345Sdim 698221345Sdim // Run through the blocks one more time, and report uninitialized variabes. 699221345Sdim for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 700224145Sdim if (wasAnalyzed[(*BI)->getBlockID()]) { 701221345Sdim runOnBlock(*BI, cfg, ac, vals, wasAnalyzed, &handler, 702221345Sdim /* flagBlockUses */ true); 703224145Sdim ++stats.NumBlockVisits; 704224145Sdim } 705221345Sdim } 706221345Sdim} 707193326Sed 708221345SdimUninitVariablesHandler::~UninitVariablesHandler() {} 709