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