UninitializedValues.cpp revision 235864
1//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements uninitialized values analysis for source-level CFGs. 11// 12//===----------------------------------------------------------------------===// 13 14#include <utility> 15#include "llvm/ADT/Optional.h" 16#include "llvm/ADT/SmallVector.h" 17#include "llvm/ADT/PackedVector.h" 18#include "llvm/ADT/DenseMap.h" 19#include "clang/AST/Decl.h" 20#include "clang/Analysis/CFG.h" 21#include "clang/Analysis/AnalysisContext.h" 22#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 23#include "clang/Analysis/Analyses/UninitializedValues.h" 24#include "llvm/Support/SaveAndRestore.h" 25 26using namespace clang; 27 28static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 29 if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 30 !vd->isExceptionVariable() && 31 vd->getDeclContext() == dc) { 32 QualType ty = vd->getType(); 33 return ty->isScalarType() || ty->isVectorType(); 34 } 35 return false; 36} 37 38//------------------------------------------------------------------------====// 39// DeclToIndex: a mapping from Decls we track to value indices. 40//====------------------------------------------------------------------------// 41 42namespace { 43class DeclToIndex { 44 llvm::DenseMap<const VarDecl *, unsigned> map; 45public: 46 DeclToIndex() {} 47 48 /// Compute the actual mapping from declarations to bits. 49 void computeMap(const DeclContext &dc); 50 51 /// Return the number of declarations in the map. 52 unsigned size() const { return map.size(); } 53 54 /// Returns the bit vector index for a given declaration. 55 llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const; 56}; 57} 58 59void DeclToIndex::computeMap(const DeclContext &dc) { 60 unsigned count = 0; 61 DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 62 E(dc.decls_end()); 63 for ( ; I != E; ++I) { 64 const VarDecl *vd = *I; 65 if (isTrackedVar(vd, &dc)) 66 map[vd] = count++; 67 } 68} 69 70llvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 71 llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 72 if (I == map.end()) 73 return llvm::Optional<unsigned>(); 74 return I->second; 75} 76 77//------------------------------------------------------------------------====// 78// CFGBlockValues: dataflow values for CFG blocks. 79//====------------------------------------------------------------------------// 80 81// These values are defined in such a way that a merge can be done using 82// a bitwise OR. 83enum Value { Unknown = 0x0, /* 00 */ 84 Initialized = 0x1, /* 01 */ 85 Uninitialized = 0x2, /* 10 */ 86 MayUninitialized = 0x3 /* 11 */ }; 87 88static bool isUninitialized(const Value v) { 89 return v >= Uninitialized; 90} 91static bool isAlwaysUninit(const Value v) { 92 return v == Uninitialized; 93} 94 95namespace { 96 97typedef llvm::PackedVector<Value, 2> ValueVector; 98typedef std::pair<ValueVector *, ValueVector *> BVPair; 99 100class CFGBlockValues { 101 const CFG &cfg; 102 BVPair *vals; 103 ValueVector scratch; 104 DeclToIndex declToIndex; 105 106 ValueVector &lazyCreate(ValueVector *&bv); 107public: 108 CFGBlockValues(const CFG &cfg); 109 ~CFGBlockValues(); 110 111 unsigned getNumEntries() const { return declToIndex.size(); } 112 113 void computeSetOfDeclarations(const DeclContext &dc); 114 ValueVector &getValueVector(const CFGBlock *block, 115 const CFGBlock *dstBlock); 116 117 BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate); 118 119 void mergeIntoScratch(ValueVector const &source, bool isFirst); 120 bool updateValueVectorWithScratch(const CFGBlock *block); 121 bool updateValueVectors(const CFGBlock *block, const BVPair &newVals); 122 123 bool hasNoDeclarations() const { 124 return declToIndex.size() == 0; 125 } 126 127 void resetScratch(); 128 ValueVector &getScratch() { return scratch; } 129 130 ValueVector::reference operator[](const VarDecl *vd); 131}; 132} // end anonymous namespace 133 134CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { 135 unsigned n = cfg.getNumBlockIDs(); 136 if (!n) 137 return; 138 vals = new std::pair<ValueVector*, ValueVector*>[n]; 139 memset((void*)vals, 0, sizeof(*vals) * n); 140} 141 142CFGBlockValues::~CFGBlockValues() { 143 unsigned n = cfg.getNumBlockIDs(); 144 if (n == 0) 145 return; 146 for (unsigned i = 0; i < n; ++i) { 147 delete vals[i].first; 148 delete vals[i].second; 149 } 150 delete [] vals; 151} 152 153void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 154 declToIndex.computeMap(dc); 155 scratch.resize(declToIndex.size()); 156} 157 158ValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) { 159 if (!bv) 160 bv = new ValueVector(declToIndex.size()); 161 return *bv; 162} 163 164/// This function pattern matches for a '&&' or '||' that appears at 165/// the beginning of a CFGBlock that also (1) has a terminator and 166/// (2) has no other elements. If such an expression is found, it is returned. 167static const BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) { 168 if (block->empty()) 169 return 0; 170 171 CFGElement front = block->front(); 172 const CFGStmt *cstmt = front.getAs<CFGStmt>(); 173 if (!cstmt) 174 return 0; 175 176 const BinaryOperator *b = dyn_cast_or_null<BinaryOperator>(cstmt->getStmt()); 177 178 if (!b || !b->isLogicalOp()) 179 return 0; 180 181 if (block->pred_size() == 2) { 182 if (block->getTerminatorCondition() == b) { 183 if (block->succ_size() == 2) 184 return b; 185 } 186 else if (block->size() == 1) 187 return b; 188 } 189 190 return 0; 191} 192 193ValueVector &CFGBlockValues::getValueVector(const CFGBlock *block, 194 const CFGBlock *dstBlock) { 195 unsigned idx = block->getBlockID(); 196 if (dstBlock && getLogicalOperatorInChain(block)) { 197 if (*block->succ_begin() == dstBlock) 198 return lazyCreate(vals[idx].first); 199 assert(*(block->succ_begin()+1) == dstBlock); 200 return lazyCreate(vals[idx].second); 201 } 202 203 assert(vals[idx].second == 0); 204 return lazyCreate(vals[idx].first); 205} 206 207BVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block, 208 bool shouldLazyCreate) { 209 unsigned idx = block->getBlockID(); 210 lazyCreate(vals[idx].first); 211 if (shouldLazyCreate) 212 lazyCreate(vals[idx].second); 213 return vals[idx]; 214} 215 216#if 0 217static void printVector(const CFGBlock *block, ValueVector &bv, 218 unsigned num) { 219 220 llvm::errs() << block->getBlockID() << " :"; 221 for (unsigned i = 0; i < bv.size(); ++i) { 222 llvm::errs() << ' ' << bv[i]; 223 } 224 llvm::errs() << " : " << num << '\n'; 225} 226 227static void printVector(const char *name, ValueVector const &bv) { 228 llvm::errs() << name << " : "; 229 for (unsigned i = 0; i < bv.size(); ++i) { 230 llvm::errs() << ' ' << bv[i]; 231 } 232 llvm::errs() << "\n"; 233} 234#endif 235 236void CFGBlockValues::mergeIntoScratch(ValueVector const &source, 237 bool isFirst) { 238 if (isFirst) 239 scratch = source; 240 else 241 scratch |= source; 242} 243 244bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 245 ValueVector &dst = getValueVector(block, 0); 246 bool changed = (dst != scratch); 247 if (changed) 248 dst = scratch; 249#if 0 250 printVector(block, scratch, 0); 251#endif 252 return changed; 253} 254 255bool CFGBlockValues::updateValueVectors(const CFGBlock *block, 256 const BVPair &newVals) { 257 BVPair &vals = getValueVectors(block, true); 258 bool changed = *newVals.first != *vals.first || 259 *newVals.second != *vals.second; 260 *vals.first = *newVals.first; 261 *vals.second = *newVals.second; 262#if 0 263 printVector(block, *vals.first, 1); 264 printVector(block, *vals.second, 2); 265#endif 266 return changed; 267} 268 269void CFGBlockValues::resetScratch() { 270 scratch.reset(); 271} 272 273ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 274 const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 275 assert(idx.hasValue()); 276 return scratch[idx.getValue()]; 277} 278 279//------------------------------------------------------------------------====// 280// Worklist: worklist for dataflow analysis. 281//====------------------------------------------------------------------------// 282 283namespace { 284class DataflowWorklist { 285 SmallVector<const CFGBlock *, 20> worklist; 286 llvm::BitVector enqueuedBlocks; 287public: 288 DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} 289 290 void enqueueSuccessors(const CFGBlock *block); 291 const CFGBlock *dequeue(); 292}; 293} 294 295void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 296 unsigned OldWorklistSize = worklist.size(); 297 for (CFGBlock::const_succ_iterator I = block->succ_begin(), 298 E = block->succ_end(); I != E; ++I) { 299 const CFGBlock *Successor = *I; 300 if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 301 continue; 302 worklist.push_back(Successor); 303 enqueuedBlocks[Successor->getBlockID()] = true; 304 } 305 if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 306 return; 307 308 // Rotate the newly added blocks to the start of the worklist so that it forms 309 // a proper queue when we pop off the end of the worklist. 310 std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize, 311 worklist.end()); 312} 313 314const CFGBlock *DataflowWorklist::dequeue() { 315 if (worklist.empty()) 316 return 0; 317 const CFGBlock *b = worklist.back(); 318 worklist.pop_back(); 319 enqueuedBlocks[b->getBlockID()] = false; 320 return b; 321} 322 323//------------------------------------------------------------------------====// 324// Transfer function for uninitialized values analysis. 325//====------------------------------------------------------------------------// 326 327namespace { 328class FindVarResult { 329 const VarDecl *vd; 330 const DeclRefExpr *dr; 331public: 332 FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {} 333 334 const DeclRefExpr *getDeclRefExpr() const { return dr; } 335 const VarDecl *getDecl() const { return vd; } 336}; 337 338class TransferFunctions : public StmtVisitor<TransferFunctions> { 339 CFGBlockValues &vals; 340 const CFG &cfg; 341 AnalysisDeclContext ∾ 342 UninitVariablesHandler *handler; 343 344 /// The last DeclRefExpr seen when analyzing a block. Used to 345 /// cheat when detecting cases when the address of a variable is taken. 346 DeclRefExpr *lastDR; 347 348 /// The last lvalue-to-rvalue conversion of a variable whose value 349 /// was uninitialized. Normally this results in a warning, but it is 350 /// possible to either silence the warning in some cases, or we 351 /// propagate the uninitialized value. 352 CastExpr *lastLoad; 353 354 /// For some expressions, we want to ignore any post-processing after 355 /// visitation. 356 bool skipProcessUses; 357 358public: 359 TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 360 AnalysisDeclContext &ac, 361 UninitVariablesHandler *handler) 362 : vals(vals), cfg(cfg), ac(ac), handler(handler), 363 lastDR(0), lastLoad(0), 364 skipProcessUses(false) {} 365 366 void reportUninit(const DeclRefExpr *ex, const VarDecl *vd, 367 bool isAlwaysUninit); 368 369 void VisitBlockExpr(BlockExpr *be); 370 void VisitDeclStmt(DeclStmt *ds); 371 void VisitDeclRefExpr(DeclRefExpr *dr); 372 void VisitUnaryOperator(UnaryOperator *uo); 373 void VisitBinaryOperator(BinaryOperator *bo); 374 void VisitCastExpr(CastExpr *ce); 375 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); 376 void Visit(Stmt *s); 377 378 bool isTrackedVar(const VarDecl *vd) { 379 return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 380 } 381 382 FindVarResult findBlockVarDecl(Expr *ex); 383 384 void ProcessUses(Stmt *s = 0); 385}; 386} 387 388static const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 389 while (Ex) { 390 Ex = Ex->IgnoreParenNoopCasts(C); 391 if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 392 if (CE->getCastKind() == CK_LValueBitCast) { 393 Ex = CE->getSubExpr(); 394 continue; 395 } 396 } 397 break; 398 } 399 return Ex; 400} 401 402void TransferFunctions::reportUninit(const DeclRefExpr *ex, 403 const VarDecl *vd, bool isAlwaysUnit) { 404 if (handler) handler->handleUseOfUninitVariable(ex, vd, isAlwaysUnit); 405} 406 407FindVarResult TransferFunctions::findBlockVarDecl(Expr *ex) { 408 if (DeclRefExpr *dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts())) 409 if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 410 if (isTrackedVar(vd)) 411 return FindVarResult(vd, dr); 412 return FindVarResult(0, 0); 413} 414 415void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs) { 416 // This represents an initialization of the 'element' value. 417 Stmt *element = fs->getElement(); 418 const VarDecl *vd = 0; 419 420 if (DeclStmt *ds = dyn_cast<DeclStmt>(element)) { 421 vd = cast<VarDecl>(ds->getSingleDecl()); 422 if (!isTrackedVar(vd)) 423 vd = 0; 424 } else { 425 // Initialize the value of the reference variable. 426 const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); 427 vd = res.getDecl(); 428 } 429 430 if (vd) 431 vals[vd] = Initialized; 432} 433 434void TransferFunctions::VisitBlockExpr(BlockExpr *be) { 435 const BlockDecl *bd = be->getBlockDecl(); 436 for (BlockDecl::capture_const_iterator i = bd->capture_begin(), 437 e = bd->capture_end() ; i != e; ++i) { 438 const VarDecl *vd = i->getVariable(); 439 if (!isTrackedVar(vd)) 440 continue; 441 if (i->isByRef()) { 442 vals[vd] = Initialized; 443 continue; 444 } 445 Value v = vals[vd]; 446 if (handler && isUninitialized(v)) 447 handler->handleUseOfUninitVariable(be, vd, isAlwaysUninit(v)); 448 } 449} 450 451void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 452 // Record the last DeclRefExpr seen. This is an lvalue computation. 453 // We use this value to later detect if a variable "escapes" the analysis. 454 if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 455 if (isTrackedVar(vd)) { 456 ProcessUses(); 457 lastDR = dr; 458 } 459} 460 461void TransferFunctions::VisitDeclStmt(DeclStmt *ds) { 462 for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end(); 463 DI != DE; ++DI) { 464 if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) { 465 if (isTrackedVar(vd)) { 466 if (Expr *init = vd->getInit()) { 467 // If the initializer consists solely of a reference to itself, we 468 // explicitly mark the variable as uninitialized. This allows code 469 // like the following: 470 // 471 // int x = x; 472 // 473 // to deliberately leave a variable uninitialized. Different analysis 474 // clients can detect this pattern and adjust their reporting 475 // appropriately, but we need to continue to analyze subsequent uses 476 // of the variable. 477 if (init == lastLoad) { 478 const DeclRefExpr *DR 479 = cast<DeclRefExpr>(stripCasts(ac.getASTContext(), 480 lastLoad->getSubExpr())); 481 if (DR->getDecl() == vd) { 482 // int x = x; 483 // Propagate uninitialized value, but don't immediately report 484 // a problem. 485 vals[vd] = Uninitialized; 486 lastLoad = 0; 487 lastDR = 0; 488 if (handler) 489 handler->handleSelfInit(vd); 490 return; 491 } 492 } 493 494 // All other cases: treat the new variable as initialized. 495 // This is a minor optimization to reduce the propagation 496 // of the analysis, since we will have already reported 497 // the use of the uninitialized value (which visiting the 498 // initializer). 499 vals[vd] = Initialized; 500 } 501 } 502 } 503 } 504} 505 506void TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { 507 if (bo->isAssignmentOp()) { 508 const FindVarResult &res = findBlockVarDecl(bo->getLHS()); 509 if (const VarDecl *vd = res.getDecl()) { 510 ValueVector::reference val = vals[vd]; 511 if (isUninitialized(val)) { 512 if (bo->getOpcode() != BO_Assign) 513 reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 514 else 515 val = Initialized; 516 } 517 } 518 } 519} 520 521void TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { 522 switch (uo->getOpcode()) { 523 case clang::UO_PostDec: 524 case clang::UO_PostInc: 525 case clang::UO_PreDec: 526 case clang::UO_PreInc: { 527 const FindVarResult &res = findBlockVarDecl(uo->getSubExpr()); 528 if (const VarDecl *vd = res.getDecl()) { 529 assert(res.getDeclRefExpr() == lastDR); 530 // We null out lastDR to indicate we have fully processed it 531 // and we don't want the auto-value setting in Visit(). 532 lastDR = 0; 533 534 ValueVector::reference val = vals[vd]; 535 if (isUninitialized(val)) 536 reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 537 } 538 break; 539 } 540 default: 541 break; 542 } 543} 544 545void TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { 546 if (ce->getCastKind() == CK_LValueToRValue) { 547 const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); 548 if (res.getDecl()) { 549 assert(res.getDeclRefExpr() == lastDR); 550 lastLoad = ce; 551 } 552 } 553 else if (ce->getCastKind() == CK_NoOp || 554 ce->getCastKind() == CK_LValueBitCast) { 555 skipProcessUses = true; 556 } 557 else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) { 558 if (cse->getType()->isVoidType()) { 559 // e.g. (void) x; 560 if (lastLoad == cse->getSubExpr()) { 561 // Squelch any detected load of an uninitialized value if 562 // we cast it to void. 563 lastLoad = 0; 564 lastDR = 0; 565 } 566 } 567 } 568} 569 570void TransferFunctions::Visit(clang::Stmt *s) { 571 skipProcessUses = false; 572 StmtVisitor<TransferFunctions>::Visit(s); 573 if (!skipProcessUses) 574 ProcessUses(s); 575} 576 577void TransferFunctions::ProcessUses(Stmt *s) { 578 // This method is typically called after visiting a CFGElement statement 579 // in the CFG. We delay processing of reporting many loads of uninitialized 580 // values until here. 581 if (lastLoad) { 582 // If we just visited the lvalue-to-rvalue cast, there is nothing 583 // left to do. 584 if (lastLoad == s) 585 return; 586 587 const DeclRefExpr *DR = 588 cast<DeclRefExpr>(stripCasts(ac.getASTContext(), 589 lastLoad->getSubExpr())); 590 const VarDecl *VD = cast<VarDecl>(DR->getDecl()); 591 592 // If we reach here, we may have seen a load of an uninitialized value 593 // and it hasn't been casted to void or otherwise handled. In this 594 // situation, report the incident. 595 if (isUninitialized(vals[VD])) 596 reportUninit(DR, VD, isAlwaysUninit(vals[VD])); 597 598 lastLoad = 0; 599 600 if (DR == lastDR) { 601 lastDR = 0; 602 return; 603 } 604 } 605 606 // Any other uses of 'lastDR' involve taking an lvalue of variable. 607 // In this case, it "escapes" the analysis. 608 if (lastDR && lastDR != s) { 609 vals[cast<VarDecl>(lastDR->getDecl())] = Initialized; 610 lastDR = 0; 611 } 612} 613 614//------------------------------------------------------------------------====// 615// High-level "driver" logic for uninitialized values analysis. 616//====------------------------------------------------------------------------// 617 618static bool runOnBlock(const CFGBlock *block, const CFG &cfg, 619 AnalysisDeclContext &ac, CFGBlockValues &vals, 620 llvm::BitVector &wasAnalyzed, 621 UninitVariablesHandler *handler = 0) { 622 623 wasAnalyzed[block->getBlockID()] = true; 624 625 if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { 626 CFGBlock::const_pred_iterator itr = block->pred_begin(); 627 BVPair vA = vals.getValueVectors(*itr, false); 628 ++itr; 629 BVPair vB = vals.getValueVectors(*itr, false); 630 631 BVPair valsAB; 632 633 if (b->getOpcode() == BO_LAnd) { 634 // Merge the 'F' bits from the first and second. 635 vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true); 636 vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false); 637 valsAB.first = vA.first; 638 valsAB.second = &vals.getScratch(); 639 } else { 640 // Merge the 'T' bits from the first and second. 641 assert(b->getOpcode() == BO_LOr); 642 vals.mergeIntoScratch(*vA.first, true); 643 vals.mergeIntoScratch(*vB.first, false); 644 valsAB.first = &vals.getScratch(); 645 valsAB.second = vA.second ? vA.second : vA.first; 646 } 647 return vals.updateValueVectors(block, valsAB); 648 } 649 650 // Default behavior: merge in values of predecessor blocks. 651 vals.resetScratch(); 652 bool isFirst = true; 653 for (CFGBlock::const_pred_iterator I = block->pred_begin(), 654 E = block->pred_end(); I != E; ++I) { 655 const CFGBlock *pred = *I; 656 if (wasAnalyzed[pred->getBlockID()]) { 657 vals.mergeIntoScratch(vals.getValueVector(pred, block), isFirst); 658 isFirst = false; 659 } 660 } 661 // Apply the transfer function. 662 TransferFunctions tf(vals, cfg, ac, handler); 663 for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 664 I != E; ++I) { 665 if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { 666 tf.Visit(const_cast<Stmt*>(cs->getStmt())); 667 } 668 } 669 tf.ProcessUses(); 670 return vals.updateValueVectorWithScratch(block); 671} 672 673void clang::runUninitializedVariablesAnalysis( 674 const DeclContext &dc, 675 const CFG &cfg, 676 AnalysisDeclContext &ac, 677 UninitVariablesHandler &handler, 678 UninitVariablesAnalysisStats &stats) { 679 CFGBlockValues vals(cfg); 680 vals.computeSetOfDeclarations(dc); 681 if (vals.hasNoDeclarations()) 682 return; 683 684 stats.NumVariablesAnalyzed = vals.getNumEntries(); 685 686 // Mark all variables uninitialized at the entry. 687 const CFGBlock &entry = cfg.getEntry(); 688 for (CFGBlock::const_succ_iterator i = entry.succ_begin(), 689 e = entry.succ_end(); i != e; ++i) { 690 if (const CFGBlock *succ = *i) { 691 ValueVector &vec = vals.getValueVector(&entry, succ); 692 const unsigned n = vals.getNumEntries(); 693 for (unsigned j = 0; j < n ; ++j) { 694 vec[j] = Uninitialized; 695 } 696 } 697 } 698 699 // Proceed with the workist. 700 DataflowWorklist worklist(cfg); 701 llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 702 worklist.enqueueSuccessors(&cfg.getEntry()); 703 llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 704 wasAnalyzed[cfg.getEntry().getBlockID()] = true; 705 706 while (const CFGBlock *block = worklist.dequeue()) { 707 // Did the block change? 708 bool changed = runOnBlock(block, cfg, ac, vals, wasAnalyzed); 709 ++stats.NumBlockVisits; 710 if (changed || !previouslyVisited[block->getBlockID()]) 711 worklist.enqueueSuccessors(block); 712 previouslyVisited[block->getBlockID()] = true; 713 } 714 715 // Run through the blocks one more time, and report uninitialized variabes. 716 for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 717 const CFGBlock *block = *BI; 718 if (wasAnalyzed[block->getBlockID()]) { 719 runOnBlock(block, cfg, ac, vals, wasAnalyzed, &handler); 720 ++stats.NumBlockVisits; 721 } 722 } 723} 724 725UninitVariablesHandler::~UninitVariablesHandler() {} 726