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