16f34213f8d6ae8c77685b53664527e39bfaaca3bTed Kremenek//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// 2610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// 3610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// The LLVM Compiler Infrastructure 4610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// 5610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// This file is distributed under the University of Illinois Open Source 6610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// License. See LICENSE.TXT for details. 7610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// 8610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//===----------------------------------------------------------------------===// 9610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// 10610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// This file implements uninitialized values analysis for source-level CFGs. 11610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// 12610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//===----------------------------------------------------------------------===// 13610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 14558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#include "clang/AST/ASTContext.h" 152fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "clang/AST/Attr.h" 16610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "clang/AST/Decl.h" 17d049b40ef411eee12a735233dbe04fdc42c67e1aJordan Rose#include "clang/AST/StmtVisitor.h" 18c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek#include "clang/Analysis/Analyses/PostOrderCFGView.h" 196f34213f8d6ae8c77685b53664527e39bfaaca3bTed Kremenek#include "clang/Analysis/Analyses/UninitializedValues.h" 202fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "clang/Analysis/AnalysisContext.h" 212fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "clang/Analysis/CFG.h" 2225c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" 232fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/DenseMap.h" 242fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/Optional.h" 252fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/PackedVector.h" 262fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/SmallBitVector.h" 272fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/SmallVector.h" 28b2c60b04a597cc5ba4154837cf8e0a155a376fd7Argyrios Kyrtzidis#include "llvm/Support/SaveAndRestore.h" 292fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include <utility> 30610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 31610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekusing namespace clang; 32610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 33558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#define DEBUG_LOGGING 0 34558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith 3540900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenekstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 361cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 37ef8225444452a1486bd721f3285301fe84643b00Stephen Hines !vd->isExceptionVariable() && !vd->isInitCapture() && 381cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek vd->getDeclContext() == dc) { 391cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek QualType ty = vd->getType(); 401cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek return ty->isScalarType() || ty->isVectorType(); 411cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek } 421cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek return false; 43c104e53639de4424b83955acfadc977773b5883dTed Kremenek} 44c104e53639de4424b83955acfadc977773b5883dTed Kremenek 45610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 46136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek// DeclToIndex: a mapping from Decls we track to value indices. 47610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 48610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 49610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 50136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekclass DeclToIndex { 51610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek llvm::DenseMap<const VarDecl *, unsigned> map; 52610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 53136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek DeclToIndex() {} 54610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 55610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Compute the actual mapping from declarations to bits. 56610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeMap(const DeclContext &dc); 57610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 58610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Return the number of declarations in the map. 59610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned size() const { return map.size(); } 60610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 61610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Returns the bit vector index for a given declaration. 62dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie Optional<unsigned> getValueIndex(const VarDecl *d) const; 63610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 64610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 65610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 66136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekvoid DeclToIndex::computeMap(const DeclContext &dc) { 67610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned count = 0; 68610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 69610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E(dc.decls_end()); 70610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for ( ; I != E; ++I) { 71581deb3da481053c4993c7600f97acf7768caac5David Blaikie const VarDecl *vd = *I; 7240900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek if (isTrackedVar(vd, &dc)) 73610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek map[vd] = count++; 74610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 75610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 76610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 77dc84cd5efdd3430efb22546b4ac656aa0540b210David BlaikieOptional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 78b831c673621c5587642343cace9def134916a17bTed Kremenek llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 79610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (I == map.end()) 8066874fb18afbffb8b2ca05576851a64534be3352David Blaikie return None; 81610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return I->second; 82610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 83610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 84610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 85610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// CFGBlockValues: dataflow values for CFG blocks. 86610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 87610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 88f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// These values are defined in such a way that a merge can be done using 89f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// a bitwise OR. 90f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekenum Value { Unknown = 0x0, /* 00 */ 91f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Initialized = 0x1, /* 01 */ 92f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Uninitialized = 0x2, /* 10 */ 93f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek MayUninitialized = 0x3 /* 11 */ }; 94f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek 95f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isUninitialized(const Value v) { 96f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v >= Uninitialized; 97f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 98f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isAlwaysUninit(const Value v) { 99f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v == Uninitialized; 100f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 101afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 102da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramernamespace { 103afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 104da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramertypedef llvm::PackedVector<Value, 2, llvm::SmallBitVector> ValueVector; 10513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 106610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass CFGBlockValues { 107610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 108da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramer SmallVector<ValueVector, 8> vals; 109136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector scratch; 1104ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek DeclToIndex declToIndex; 111610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 112610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues(const CFG &cfg); 113eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek 114d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek unsigned getNumEntries() const { return declToIndex.size(); } 115d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 116610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeSetOfDeclarations(const DeclContext &dc); 117eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &getValueVector(const CFGBlock *block) { 118da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramer return vals[block->getBlockID()]; 119eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek } 12013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 121a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith void setAllScratchValues(Value V); 122136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek void mergeIntoScratch(ValueVector const &source, bool isFirst); 123136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool updateValueVectorWithScratch(const CFGBlock *block); 124610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 125610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool hasNoDeclarations() const { 1264ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek return declToIndex.size() == 0; 127610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 128e0e29332c89da22b6890929b97e6f568c917d85fTed Kremenek 129610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void resetScratch(); 13013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 131136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector::reference operator[](const VarDecl *vd); 1322815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 1332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, 1342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const VarDecl *vd) { 135dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie const Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 1362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith assert(idx.hasValue()); 137eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek return getValueVector(block)[idx.getValue()]; 1382815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 139610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 140da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramer} // end anonymous namespace 141610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 142eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed KremenekCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} 143610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 144610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 1454ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek declToIndex.computeMap(dc); 146eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek unsigned decls = declToIndex.size(); 147eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek scratch.resize(decls); 148eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek unsigned n = cfg.getNumBlockIDs(); 149eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek if (!n) 150eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek return; 151eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals.resize(n); 152eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (unsigned i = 0; i < n; ++i) 153da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramer vals[i].resize(decls); 15413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 15513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 156558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#if DEBUG_LOGGING 157136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekstatic void printVector(const CFGBlock *block, ValueVector &bv, 1589fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek unsigned num) { 1599fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << block->getBlockID() << " :"; 1609fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek for (unsigned i = 0; i < bv.size(); ++i) { 1619fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << ' ' << bv[i]; 1629fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek } 1639fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << " : " << num << '\n'; 1649fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek} 1659fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 166610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 167a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smithvoid CFGBlockValues::setAllScratchValues(Value V) { 168a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith for (unsigned I = 0, E = scratch.size(); I != E; ++I) 169a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith scratch[I] = V; 170a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith} 171a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith 172c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenekvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 173c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek bool isFirst) { 174c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek if (isFirst) 175c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch = source; 176c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek else 177c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch |= source; 178c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek} 179c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 180136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 181eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &dst = getValueVector(block); 182610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool changed = (dst != scratch); 183610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed) 184610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek dst = scratch; 185558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#if DEBUG_LOGGING 1869fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, scratch, 0); 1879fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 18813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return changed; 18913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 19013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 191610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::resetScratch() { 192610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek scratch.reset(); 193610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 194610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 195136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 196dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie const Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 197610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek assert(idx.hasValue()); 198610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return scratch[idx.getValue()]; 199610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 200610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 201610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 202610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// Worklist: worklist for dataflow analysis. 203610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 204610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 205610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 206610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass DataflowWorklist { 207c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek PostOrderCFGView::iterator PO_I, PO_E; 2085f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<const CFGBlock *, 20> worklist; 209496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector enqueuedBlocks; 210610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 211c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) 212c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek : PO_I(view.begin()), PO_E(view.end()), 213c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek enqueuedBlocks(cfg.getNumBlockIDs(), true) { 214c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // Treat the first block as already analyzed. 215c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek if (PO_I != PO_E) { 216c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek assert(*PO_I == &cfg.getEntry()); 217c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek enqueuedBlocks[(*PO_I)->getBlockID()] = false; 218c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek ++PO_I; 219c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 220c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 221610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 222610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void enqueueSuccessors(const CFGBlock *block); 223610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *dequeue(); 224610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 225610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 226610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 227610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 228610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_succ_iterator I = block->succ_begin(), 229610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->succ_end(); I != E; ++I) { 2308052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth const CFGBlock *Successor = *I; 2318052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 2328052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth continue; 2338052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth worklist.push_back(Successor); 2348052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth enqueuedBlocks[Successor->getBlockID()] = true; 235610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 236610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 237610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 238610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekconst CFGBlock *DataflowWorklist::dequeue() { 2396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const CFGBlock *B = nullptr; 240c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek 241c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // First dequeue from the worklist. This can represent 242c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // updates along backedges that we want propagated as quickly as possible. 243344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm if (!worklist.empty()) 244344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm B = worklist.pop_back_val(); 245344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm 246c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // Next dequeue from the initial reverse post order. This is the 247c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // theoretical ideal in the presence of no back edges. 248c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek else if (PO_I != PO_E) { 249c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek B = *PO_I; 250c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek ++PO_I; 251c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 252c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek else { 2536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 254c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 255c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek 256c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek assert(enqueuedBlocks[B->getBlockID()] == true); 257c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek enqueuedBlocks[B->getBlockID()] = false; 258c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek return B; 259610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 260610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 261610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 2629532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith// Classification of DeclRefExprs as use or initialization. 263610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 264610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 265610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 266610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass FindVarResult { 267610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd; 268610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *dr; 269610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 2709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} 2719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 272610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *getDeclRefExpr() const { return dr; } 273610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *getDecl() const { return vd; } 274610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 2759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 2769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 2779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith while (Ex) { 2789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ex = Ex->IgnoreParenNoopCasts(C); 2799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 2809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CE->getCastKind() == CK_LValueBitCast) { 2819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ex = CE->getSubExpr(); 2829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith continue; 2839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2849532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 2869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Ex; 2889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 2899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 2909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// If E is an expression comprising a reference to a single variable, find that 2919532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// variable. 2929532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic FindVarResult findVar(const Expr *E, const DeclContext *DC) { 2939532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = 2949532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith dyn_cast<DeclRefExpr>(stripCasts(DC->getParentASTContext(), E))) 2959532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) 2969532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (isTrackedVar(VD, DC)) 2979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return FindVarResult(VD, DRE); 2986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return FindVarResult(nullptr, nullptr); 2999532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// \brief Classify each DeclRefExpr as an initialization or a use. Any 3029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// DeclRefExpr which isn't explicitly classified will be assumed to have 3039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// escaped the analysis and will be treated as an initialization. 3049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithclass ClassifyRefs : public StmtVisitor<ClassifyRefs> { 3059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithpublic: 3069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith enum Class { 3079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Init, 3089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Use, 3099532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith SelfInit, 3109532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ignore 3119532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith }; 3129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithprivate: 3149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const DeclContext *DC; 3159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith llvm::DenseMap<const DeclRefExpr*, Class> Classification; 3169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3179532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith bool isTrackedVar(const VarDecl *VD) const { 3189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return ::isTrackedVar(VD, DC); 3199532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3209532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void classify(const Expr *E, Class C); 3229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithpublic: 3249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith ClassifyRefs(AnalysisDeclContext &AC) : DC(cast<DeclContext>(AC.getDecl())) {} 3259532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitDeclStmt(DeclStmt *DS); 3279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitUnaryOperator(UnaryOperator *UO); 3289532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitBinaryOperator(BinaryOperator *BO); 3299532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitCallExpr(CallExpr *CE); 3309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitCastExpr(CastExpr *CE); 3319532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3329532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void operator()(Stmt *S) { Visit(S); } 3339532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3349532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Class get(const DeclRefExpr *DRE) const { 3359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith llvm::DenseMap<const DeclRefExpr*, Class>::const_iterator I 3369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith = Classification.find(DRE); 3379532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (I != Classification.end()) 3389532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return I->second; 3399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3409532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); 3419532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (!VD || !isTrackedVar(VD)) 3429532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Ignore; 3439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Init; 3459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3469532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith}; 3479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { 3509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (Expr *Init = VD->getInit()) { 3519532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const DeclRefExpr *DRE 3529532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith = dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init)); 3539532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (DRE && DRE->getDecl() == VD) 3549532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return DRE; 3559532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 3579532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3589532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3599532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::classify(const Expr *E, Class C) { 36077fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek // The result of a ?: could also be an lvalue. 36177fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek E = E->IgnoreParens(); 36277fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek if (const ConditionalOperator *CO = dyn_cast<ConditionalOperator>(E)) { 36377fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek const Expr *TrueExpr = CO->getTrueExpr(); 36477fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek if (!isa<OpaqueValueExpr>(TrueExpr)) 36577fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek classify(TrueExpr, C); 36677fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek classify(CO->getFalseExpr(), C); 36777fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek return; 36877fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek } 36977fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek 3709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(E, DC); 3719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) 3729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = std::max(Classification[DRE], C); 3739532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { 376651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (auto *DI : DS->decls()) { 377651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarDecl *VD = dyn_cast<VarDecl>(DI); 3789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) 3799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) 3809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = SelfInit; 3819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3849532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { 3859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this 3869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // is not a compound-assignment, we will treat it as initializing the variable 3879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // when TransferFunctions visits it. A compound-assignment does not affect 3889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // whether a variable is uninitialized, and there's no point counting it as a 3899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use. 3906cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith if (BO->isCompoundAssignmentOp()) 3916cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith classify(BO->getLHS(), Use); 3926cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith else if (BO->getOpcode() == BO_Assign) 3939532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(BO->getLHS(), Ignore); 3949532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3959532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3969532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { 3979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Increment and decrement are uses despite there being no lvalue-to-rvalue 3989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // conversion. 3999532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (UO->isIncrementDecrementOp()) 4009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(UO->getSubExpr(), Use); 4019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCallExpr(CallExpr *CE) { 4049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // If a value is passed by const reference to a function, we should not assume 4059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // that it is initialized by the call, and we conservatively do not assume 4069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // that it is used. 4079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); 4089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith I != E; ++I) 4099532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) 4109532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(*I, Ignore); 4119532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCastExpr(CastExpr *CE) { 4149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CE->getCastKind() == CK_LValueToRValue) 4159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CE->getSubExpr(), Use); 4169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith else if (CStyleCastExpr *CSE = dyn_cast<CStyleCastExpr>(CE)) { 4179532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CSE->getType()->isVoidType()) { 4189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Squelch any detected load of an uninitialized value if 4199532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // we cast it to void. 4209532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // e.g. (void) x; 4219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CSE->getSubExpr(), Ignore); 4229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4259532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//------------------------------------------------------------------------====// 4279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith// Transfer function for uninitialized values analysis. 4289532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//====------------------------------------------------------------------------// 4299532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithnamespace { 4310c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 432610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues &vals; 433610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 4342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block; 4351d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext ∾ 4369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification; 43725c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek ObjCNoReturn objCNoRet; 438eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler; 4399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 440610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 441610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 4422815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block, AnalysisDeclContext &ac, 4439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 444eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler) 4459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith : vals(vals), cfg(cfg), block(block), ac(ac), 44625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek classification(classification), objCNoRet(ac.getASTContext()), 44725c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek handler(handler) {} 4489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 449818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith void reportUse(const Expr *ex, const VarDecl *vd); 450a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 45125c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitBinaryOperator(BinaryOperator *bo); 452a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek void VisitBlockExpr(BlockExpr *be); 453a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith void VisitCallExpr(CallExpr *ce); 454c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek void VisitDeclRefExpr(DeclRefExpr *dr); 45525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitDeclStmt(DeclStmt *ds); 45625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); 45725c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCMessageExpr(ObjCMessageExpr *ME); 4582815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 45940900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek bool isTrackedVar(const VarDecl *vd) { 46040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 46140900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek } 4622815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4639532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult findVar(const Expr *ex) { 4649532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return ::findVar(ex, cast<DeclContext>(ac.getDecl())); 4659532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4669532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4672815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { 4682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse Use(ex, isAlwaysUninit(v)); 4692815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4702815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith assert(isUninitialized(v)); 4712815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Use.getKind() == UninitUse::Always) 4722815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 4732815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4742815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // If an edge which leads unconditionally to this use did not initialize 4752815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable, we can say something stronger than 'may be uninitialized': 4762815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // we can say 'either it's used uninitialized or you have dead code'. 4772815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4782815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // We track the number of successors of a node which have been visited, and 4792815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // visit a node once we have visited all of its successors. Only edges where 4802815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable might still be uninitialized are followed. Since a variable 4812815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // can't transfer from being initialized to being uninitialized, this will 4822815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // trace out the subgraph which inevitably leads to the use and does not 4832815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // initialize the variable. We do not want to skip past loops, since their 4842815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // non-termination might be correlated with the initialization condition. 4852815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4862815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // For example: 4872815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4882815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // void f(bool a, bool b) { 4892815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block1: int n; 4902815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // if (a) { 4912815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block2: if (b) 4922815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block3: n = 1; 4932815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block4: } else if (b) { 4942815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block5: while (!a) { 4952815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block6: do_work(&a); 4962815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // n = 2; 4972815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 4982815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 4992815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block7: if (a) 5002815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block8: g(); 5012815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block9: return n; 5022815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 5032815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5042815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Starting from the maybe-uninitialized use in block 9: 5052815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is not visited because we have only visited one of its two 5062815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // successors. 5072815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 8 is visited because we've visited its only successor. 5082815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 8: 5092815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is visited because we've now visited both of its successors. 5102815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 7: 5112815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all 5122815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). 5132815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 3 is not visited because it initializes 'n'. 5142815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Now the algorithm terminates, having visited blocks 7 and 8, and having 5152815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // found the frontier is blocks 2, 4, and 5. 5162815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5172815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 5182815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // and 4), so we report that any time either of those edges is taken (in 5192815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // each case when 'b == false'), 'n' is used uninitialized. 520cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<const CFGBlock*, 32> Queue; 521cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0); 5222815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(block); 5232815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Specify that we've already visited all successors of the starting block. 5242815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This has the dual purpose of ensuring we never add it to the queue, and 5252815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of marking it as not being a candidate element of the frontier. 5262815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith SuccsVisited[block->getBlockID()] = block->succ_size(); 5272815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith while (!Queue.empty()) { 528344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm const CFGBlock *B = Queue.pop_back_val(); 5298a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith 5308a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // If the use is always reached from the entry block, make a note of that. 5318a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (B == &cfg.getEntry()) 5328a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Use.setUninitAfterCall(); 5338a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith 5342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); 5352815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith I != E; ++I) { 5362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Pred = *I; 537651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!Pred) 538651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines continue; 539651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 5408a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Value AtPredExit = vals.getValue(Pred, B, vd); 5418a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (AtPredExit == Initialized) 5422815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block initializes the variable. 5432815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 5448a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (AtPredExit == MayUninitialized && 5456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines vals.getValue(B, nullptr, vd) == Uninitialized) { 5468a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // This block declares the variable (uninitialized), and is reachable 5478a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // from a block that initializes the variable. We can't guarantee to 5488a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // give an earlier location for the diagnostic (and it appears that 5498a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // this code is intended to be reachable) so give a diagnostic here 5508a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // and go no further down this path. 5518a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Use.setUninitAfterDecl(); 5528a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith continue; 5538a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith } 5542815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 555558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith unsigned &SV = SuccsVisited[Pred->getBlockID()]; 556558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!SV) { 557558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // When visiting the first successor of a block, mark all NULL 558558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // successors as having been visited. 559558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), 560558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SE = Pred->succ_end(); 561558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SI != SE; ++SI) 562558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!*SI) 563558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith ++SV; 564558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith } 565558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith 566558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (++SV == Pred->succ_size()) 5672815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // All paths from this block lead to the use and don't initialize the 5682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // variable. 5692815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(Pred); 5702815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5712815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5722815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5732815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Scan the frontier, looking for blocks where the variable was 5742815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // uninitialized. 5752815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 5762815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Block = *BI; 5772815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith unsigned BlockID = Block->getBlockID(); 5782815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Term = Block->getTerminator(); 5792815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && 5802815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Term) { 5812815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block inevitably leads to the use. If we have an edge from here 5822815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // to a post-dominator block, and the variable is uninitialized on that 5832815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // edge, we have found a bug. 5842815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_succ_iterator I = Block->succ_begin(), 5852815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith E = Block->succ_end(); I != E; ++I) { 5862815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Succ = *I; 5872815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && 5882815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith vals.getValue(Block, Succ, vd) == Uninitialized) { 5892815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Switch cases are a special case: report the label to the caller 5902815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // as the 'terminator', not the switch statement itself. Suppress 5912815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // situations where no label matched: we can't be sure that's 5922815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // possible. 5932815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (isa<SwitchStmt>(Term)) { 5942815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Label = Succ->getLabel(); 5952815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (!Label || !isa<SwitchCase>(Label)) 5962815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Might not be possible. 5972815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 5982815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 5992815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Label; 6002815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = 0; // Ignored. 6012815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 6022815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } else { 6032815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 6042815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Term; 6052815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = I - Block->succ_begin(); 6062815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 6072815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6082815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6092815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6102815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6112815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6122815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 6132815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 6142815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 615610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 616610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 617610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 618818918855d84e3db1af5a0807070d4995ca2cf75Richard Smithvoid TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { 619818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith Value v = vals[vd]; 620818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith if (isUninitialized(v)) 621eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); 622610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 623610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { 6251ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // This represents an initialization of the 'element' value. 6269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (DeclStmt *DS = dyn_cast<DeclStmt>(FS->getElement())) { 6279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 6289532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (isTrackedVar(VD)) 6299532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 6301ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 6311ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 6321ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 633a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 634bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek const BlockDecl *bd = be->getBlockDecl(); 635651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (const auto &I : bd->captures()) { 636651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines const VarDecl *vd = I.getVariable(); 637bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek if (!isTrackedVar(vd)) 638bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 639651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (I.isByRef()) { 640bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek vals[vd] = Initialized; 641bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 642bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek } 643818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith reportUse(be, vd); 644a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek } 645a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek} 646a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 647a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smithvoid TransferFunctions::VisitCallExpr(CallExpr *ce) { 64844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Decl *Callee = ce->getCalleeDecl()) { 64944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Callee->hasAttr<ReturnsTwiceAttr>()) { 65044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // After a call to a function like setjmp or vfork, any variable which is 65144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // initialized anywhere within this function may now be initialized. For 65244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // now, just assume such a call initializes all variables. FIXME: Only 65344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // mark variables as initialized if they have an initializer which is 65444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // reachable from here. 65544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Initialized); 65644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 65744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek else if (Callee->hasAttr<AnalyzerNoReturnAttr>()) { 65844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // Functions labeled like "analyzer_noreturn" are often used to denote 65944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // "panic" functions that in special debug situations can still return, 66044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // but for the most part should not be treated as returning. This is a 66144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // useful annotation borrowed from the static analyzer that is useful for 66244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // suppressing branch-specific false positives when we call one of these 66344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // functions but keep pretending the path continues (when in reality the 66444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // user doesn't care). 66544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Unknown); 66644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 66744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 668a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith} 669a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith 6700c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 6719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith switch (classification.get(dr)) { 6729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Ignore: 6739532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 6749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Use: 6759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith reportUse(dr, cast<VarDecl>(dr->getDecl())); 6769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 6779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Init: 6789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[cast<VarDecl>(dr->getDecl())] = Initialized; 6799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 6809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::SelfInit: 681eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek handler.handleSelfInit(cast<VarDecl>(dr->getDecl())); 6829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 683610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 684610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 685610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { 6879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (BO->getOpcode() == BO_Assign) { 6889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(BO->getLHS()); 6899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const VarDecl *VD = Var.getDecl()) 6909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 691610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 692610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 693610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6949532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 695651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (auto *DI : DS->decls()) { 696651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarDecl *VD = dyn_cast<VarDecl>(DI); 6979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) { 6989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (getSelfInitExpr(VD)) { 6999532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // If the initializer consists solely of a reference to itself, we 7009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // explicitly mark the variable as uninitialized. This allows code 7019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // like the following: 7029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 7039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int x = x; 7049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 7059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // to deliberately leave a variable uninitialized. Different analysis 7069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // clients can detect this pattern and adjust their reporting 7079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // appropriately, but we need to continue to analyze subsequent uses 7089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // of the variable. 7099532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 7109532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else if (VD->getInit()) { 7119532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Treat the new variable as initialized. 7129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 7139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else { 7149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // No initializer: the variable is now uninitialized. This matters 7159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // for cases like: 7169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // while (...) { 7179532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int n; 7189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use(n); 7199532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // n = 0; 7209532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // } 7219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // FIXME: Mark the variable as uninitialized whenever its scope is 7229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // left, since its scope could be re-entered by a jump over the 7239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // declaration. 7249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 7250c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek } 726dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 727dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 728610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 729610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 73025c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenekvoid TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { 73125c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // If the Objective-C message expression is an implicit no-return that 73225c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // is not modeled in the CFG, set the tracked dataflow values to Unknown. 73325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek if (objCNoRet.isImplicitNoReturn(ME)) { 73425c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek vals.setAllScratchValues(Unknown); 73525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek } 73625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek} 73725c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek 738610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 739610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// High-level "driver" logic for uninitialized values analysis. 740610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 741610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 74213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenekstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 7431d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, CFGBlockValues &vals, 7449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 745f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector &wasAnalyzed, 746eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler) { 747f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek wasAnalyzed[block->getBlockID()] = true; 748610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.resetScratch(); 749eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek // Merge in values of predecessor blocks. 750610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool isFirst = true; 751610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 752610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->pred_end(); I != E; ++I) { 7536f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *pred = *I; 754651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!pred) 755651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines continue; 7566f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (wasAnalyzed[pred->getBlockID()]) { 757eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); 7586f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek isFirst = false; 7596f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek } 760610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 761610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Apply the transfer function. 7629532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith TransferFunctions tf(vals, cfg, block, ac, classification, handler); 763610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 764610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek I != E; ++I) { 765b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> cs = I->getAs<CFGStmt>()) 766b07805485c603be3d8011f72611465324c9e664bDavid Blaikie tf.Visit(const_cast<Stmt*>(cs->getStmt())); 767610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 768136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectorWithScratch(block); 769610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 770610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 771eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// PruneBlocksHandler is a special UninitVariablesHandler that is used 772eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// to detect when a CFGBlock has any *potential* use of an uninitialized 773eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// variable. It is mainly used to prune out work during the final 774eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// reporting pass. 775eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremeneknamespace { 776eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenekstruct PruneBlocksHandler : public UninitVariablesHandler { 777eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PruneBlocksHandler(unsigned numBlocks) 778eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek : hadUse(numBlocks, false), hadAnyUse(false), 779eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek currentBlock(0) {} 780eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 781eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek virtual ~PruneBlocksHandler() {} 782eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 783eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Records if a CFGBlock had a potential use of an uninitialized variable. 784eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek llvm::BitVector hadUse; 785eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 786eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Records if any CFGBlock had a potential use of an uninitialized variable. 787eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek bool hadAnyUse; 788eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 789eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// The current block to scribble use information. 790eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek unsigned currentBlock; 791eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 792651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void handleUseOfUninitVariable(const VarDecl *vd, 793651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines const UninitUse &use) override { 794eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadUse[currentBlock] = true; 795eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadAnyUse = true; 796eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek } 797eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 798eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Called when the uninitialized variable analysis detects the 799eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// idiom 'int x = x'. All other uses of 'x' within the initializer 800eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// are handled by handleUseOfUninitVariable. 801651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void handleSelfInit(const VarDecl *vd) override { 802eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadUse[currentBlock] = true; 803eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadAnyUse = true; 804eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek } 805eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek}; 806eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek} 807eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 8085d98994c7749312a43ce6adf45537979a98e7afdChandler Carruthvoid clang::runUninitializedVariablesAnalysis( 8095d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const DeclContext &dc, 8105d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const CFG &cfg, 8111d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, 8125d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesHandler &handler, 8135d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesAnalysisStats &stats) { 814610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues vals(cfg); 815610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.computeSetOfDeclarations(dc); 816610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (vals.hasNoDeclarations()) 817610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 818d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 8195d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth stats.NumVariablesAnalyzed = vals.getNumEntries(); 8205d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth 8219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Precompute which expressions are uses and which are initializations. 8229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith ClassifyRefs classification(ac); 8239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith cfg.VisitBlockStmts(classification); 8249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 825d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Mark all variables uninitialized at the entry. 826d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek const CFGBlock &entry = cfg.getEntry(); 827eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &vec = vals.getValueVector(&entry); 828eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek const unsigned n = vals.getNumEntries(); 829eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (unsigned j = 0; j < n ; ++j) { 830eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vec[j] = Uninitialized; 831d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek } 832d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 833d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Proceed with the workist. 834c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek DataflowWorklist worklist(cfg, *ac.getAnalysis<PostOrderCFGView>()); 835496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 836610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(&cfg.getEntry()); 837f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 8386f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek wasAnalyzed[cfg.getEntry().getBlockID()] = true; 839eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PruneBlocksHandler PBH(cfg.getNumBlockIDs()); 840610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 841610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 842eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PBH.currentBlock = block->getBlockID(); 843eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 844610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Did the block change? 8459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith bool changed = runOnBlock(block, cfg, ac, vals, 846eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek classification, wasAnalyzed, PBH); 8475d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 848610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed || !previouslyVisited[block->getBlockID()]) 849610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(block); 850610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek previouslyVisited[block->getBlockID()] = true; 851610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 852eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 853eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek if (!PBH.hadAnyUse) 854eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek return; 855eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 85667d472c19310c06efd5cb87c60b8489abf507233Enea Zaffanella // Run through the blocks one more time, and report uninitialized variables. 857610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 8586f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *block = *BI; 859eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek if (PBH.hadUse[block->getBlockID()]) { 860eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler); 8615d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 8625d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth } 863610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 864610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 865610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 866610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekUninitVariablesHandler::~UninitVariablesHandler() {} 867