UninitializedValues.cpp revision 0e2c34f92f00628d48968dfea096d36381f494cb
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() && 37c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen 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)) { 363176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(CO->getTrueExpr(), C); 36477fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek classify(CO->getFalseExpr(), C); 36577fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek return; 36677fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek } 36777fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek 368176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (const BinaryConditionalOperator *BCO = 369176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines dyn_cast<BinaryConditionalOperator>(E)) { 370176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(BCO->getFalseExpr(), C); 371176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 372176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 373176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 374176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) { 375176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(OVE->getSourceExpr(), C); 376176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 377176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 378176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 379176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(E)) { 380176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (BO->getOpcode() == BO_Comma) 381176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(BO->getRHS(), C); 382176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 383176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 384176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 3859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(E, DC); 3869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) 3879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = std::max(Classification[DRE], C); 3889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { 391651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (auto *DI : DS->decls()) { 392651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarDecl *VD = dyn_cast<VarDecl>(DI); 3939532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) 3949532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) 3959532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = SelfInit; 3969532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3999532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { 4009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this 4019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // is not a compound-assignment, we will treat it as initializing the variable 4029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // when TransferFunctions visits it. A compound-assignment does not affect 4039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // whether a variable is uninitialized, and there's no point counting it as a 4049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use. 4056cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith if (BO->isCompoundAssignmentOp()) 4066cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith classify(BO->getLHS(), Use); 4076cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith else if (BO->getOpcode() == BO_Assign) 4089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(BO->getLHS(), Ignore); 4099532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4109532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4119532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { 4129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Increment and decrement are uses despite there being no lvalue-to-rvalue 4139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // conversion. 4149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (UO->isIncrementDecrementOp()) 4159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(UO->getSubExpr(), Use); 4169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4179532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCallExpr(CallExpr *CE) { 419176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // Classify arguments to std::move as used. 420176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (CE->getNumArgs() == 1) { 421176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (FunctionDecl *FD = CE->getDirectCallee()) { 4220e2c34f92f00628d48968dfea096d36381f494cbStephen Hines if (FD->isInStdNamespace() && FD->getIdentifier() && 4230e2c34f92f00628d48968dfea096d36381f494cbStephen Hines FD->getIdentifier()->isStr("move")) { 424176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(CE->getArg(0), Use); 425176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 426176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 427176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 428176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 429176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 4309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // If a value is passed by const reference to a function, we should not assume 4319532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // that it is initialized by the call, and we conservatively do not assume 4329532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // that it is used. 4339532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); 4349532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith I != E; ++I) 4359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) 4369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(*I, Ignore); 4379532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4389532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCastExpr(CastExpr *CE) { 4409532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CE->getCastKind() == CK_LValueToRValue) 4419532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CE->getSubExpr(), Use); 4429532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith else if (CStyleCastExpr *CSE = dyn_cast<CStyleCastExpr>(CE)) { 4439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CSE->getType()->isVoidType()) { 4449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Squelch any detected load of an uninitialized value if 4459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // we cast it to void. 4469532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // e.g. (void) x; 4479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CSE->getSubExpr(), Ignore); 4489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4519532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4529532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//------------------------------------------------------------------------====// 4539532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith// Transfer function for uninitialized values analysis. 4549532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//====------------------------------------------------------------------------// 4559532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4569532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithnamespace { 4570c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 458610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues &vals; 459610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 4602815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block; 4611d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext ∾ 4629532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification; 46325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek ObjCNoReturn objCNoRet; 464eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler; 4659532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 466610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 467610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 4682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block, AnalysisDeclContext &ac, 4699532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 470eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler) 4719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith : vals(vals), cfg(cfg), block(block), ac(ac), 47225c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek classification(classification), objCNoRet(ac.getASTContext()), 47325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek handler(handler) {} 4749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 475818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith void reportUse(const Expr *ex, const VarDecl *vd); 476a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 47725c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitBinaryOperator(BinaryOperator *bo); 478a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek void VisitBlockExpr(BlockExpr *be); 479a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith void VisitCallExpr(CallExpr *ce); 480c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek void VisitDeclRefExpr(DeclRefExpr *dr); 48125c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitDeclStmt(DeclStmt *ds); 48225c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); 48325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCMessageExpr(ObjCMessageExpr *ME); 4842815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 48540900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek bool isTrackedVar(const VarDecl *vd) { 48640900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 48740900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek } 4882815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult findVar(const Expr *ex) { 4909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return ::findVar(ex, cast<DeclContext>(ac.getDecl())); 4919532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4929532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4932815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { 4942815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse Use(ex, isAlwaysUninit(v)); 4952815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4962815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith assert(isUninitialized(v)); 4972815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Use.getKind() == UninitUse::Always) 4982815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 4992815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5002815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // If an edge which leads unconditionally to this use did not initialize 5012815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable, we can say something stronger than 'may be uninitialized': 5022815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // we can say 'either it's used uninitialized or you have dead code'. 5032815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5042815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // We track the number of successors of a node which have been visited, and 5052815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // visit a node once we have visited all of its successors. Only edges where 5062815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable might still be uninitialized are followed. Since a variable 5072815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // can't transfer from being initialized to being uninitialized, this will 5082815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // trace out the subgraph which inevitably leads to the use and does not 5092815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // initialize the variable. We do not want to skip past loops, since their 5102815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // non-termination might be correlated with the initialization condition. 5112815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5122815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // For example: 5132815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5142815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // void f(bool a, bool b) { 5152815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block1: int n; 5162815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // if (a) { 5172815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block2: if (b) 5182815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block3: n = 1; 5192815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block4: } else if (b) { 5202815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block5: while (!a) { 5212815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block6: do_work(&a); 5222815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // n = 2; 5232815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 5242815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 5252815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block7: if (a) 5262815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block8: g(); 5272815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block9: return n; 5282815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 5292815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5302815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Starting from the maybe-uninitialized use in block 9: 5312815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is not visited because we have only visited one of its two 5322815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // successors. 5332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 8 is visited because we've visited its only successor. 5342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 8: 5352815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is visited because we've now visited both of its successors. 5362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 7: 5372815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all 5382815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). 5392815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 3 is not visited because it initializes 'n'. 5402815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Now the algorithm terminates, having visited blocks 7 and 8, and having 5412815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // found the frontier is blocks 2, 4, and 5. 5422815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5432815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 5442815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // and 4), so we report that any time either of those edges is taken (in 5452815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // each case when 'b == false'), 'n' is used uninitialized. 546cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<const CFGBlock*, 32> Queue; 547cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0); 5482815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(block); 5492815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Specify that we've already visited all successors of the starting block. 5502815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This has the dual purpose of ensuring we never add it to the queue, and 5512815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of marking it as not being a candidate element of the frontier. 5522815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith SuccsVisited[block->getBlockID()] = block->succ_size(); 5532815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith while (!Queue.empty()) { 554344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm const CFGBlock *B = Queue.pop_back_val(); 5558a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith 5568a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // If the use is always reached from the entry block, make a note of that. 5578a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (B == &cfg.getEntry()) 5588a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Use.setUninitAfterCall(); 5598a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith 5602815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); 5612815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith I != E; ++I) { 5622815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Pred = *I; 563651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!Pred) 564651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines continue; 565651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 5668a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Value AtPredExit = vals.getValue(Pred, B, vd); 5678a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (AtPredExit == Initialized) 5682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block initializes the variable. 5692815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 5708a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (AtPredExit == MayUninitialized && 5716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines vals.getValue(B, nullptr, vd) == Uninitialized) { 5728a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // This block declares the variable (uninitialized), and is reachable 5738a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // from a block that initializes the variable. We can't guarantee to 5748a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // give an earlier location for the diagnostic (and it appears that 5758a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // this code is intended to be reachable) so give a diagnostic here 5768a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // and go no further down this path. 5778a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Use.setUninitAfterDecl(); 5788a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith continue; 5798a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith } 5802815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 581558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith unsigned &SV = SuccsVisited[Pred->getBlockID()]; 582558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!SV) { 583558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // When visiting the first successor of a block, mark all NULL 584558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // successors as having been visited. 585558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), 586558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SE = Pred->succ_end(); 587558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SI != SE; ++SI) 588558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!*SI) 589558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith ++SV; 590558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith } 591558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith 592558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (++SV == Pred->succ_size()) 5932815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // All paths from this block lead to the use and don't initialize the 5942815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // variable. 5952815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(Pred); 5962815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5972815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5982815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5992815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Scan the frontier, looking for blocks where the variable was 6002815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // uninitialized. 6012815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 6022815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Block = *BI; 6032815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith unsigned BlockID = Block->getBlockID(); 6042815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Term = Block->getTerminator(); 6052815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && 6062815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Term) { 6072815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block inevitably leads to the use. If we have an edge from here 6082815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // to a post-dominator block, and the variable is uninitialized on that 6092815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // edge, we have found a bug. 6102815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_succ_iterator I = Block->succ_begin(), 6112815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith E = Block->succ_end(); I != E; ++I) { 6122815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Succ = *I; 6132815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && 6142815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith vals.getValue(Block, Succ, vd) == Uninitialized) { 6152815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Switch cases are a special case: report the label to the caller 6162815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // as the 'terminator', not the switch statement itself. Suppress 6172815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // situations where no label matched: we can't be sure that's 6182815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // possible. 6192815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (isa<SwitchStmt>(Term)) { 6202815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Label = Succ->getLabel(); 6212815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (!Label || !isa<SwitchCase>(Label)) 6222815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Might not be possible. 6232815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 6242815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 6252815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Label; 6262815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = 0; // Ignored. 6272815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 6282815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } else { 6292815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 6302815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Term; 6312815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = I - Block->succ_begin(); 6322815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 6332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6352815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6372815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6382815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 6392815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 6402815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 641610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 642610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 643610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 644818918855d84e3db1af5a0807070d4995ca2cf75Richard Smithvoid TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { 645818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith Value v = vals[vd]; 646818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith if (isUninitialized(v)) 647eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); 648610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 649610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { 6511ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // This represents an initialization of the 'element' value. 6529532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (DeclStmt *DS = dyn_cast<DeclStmt>(FS->getElement())) { 6539532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 6549532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (isTrackedVar(VD)) 6559532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 6561ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 6571ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 6581ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 659a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 660bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek const BlockDecl *bd = be->getBlockDecl(); 661651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (const auto &I : bd->captures()) { 662651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines const VarDecl *vd = I.getVariable(); 663bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek if (!isTrackedVar(vd)) 664bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 665651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (I.isByRef()) { 666bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek vals[vd] = Initialized; 667bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 668bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek } 669818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith reportUse(be, vd); 670a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek } 671a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek} 672a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 673a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smithvoid TransferFunctions::VisitCallExpr(CallExpr *ce) { 67444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Decl *Callee = ce->getCalleeDecl()) { 67544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Callee->hasAttr<ReturnsTwiceAttr>()) { 67644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // After a call to a function like setjmp or vfork, any variable which is 67744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // initialized anywhere within this function may now be initialized. For 67844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // now, just assume such a call initializes all variables. FIXME: Only 67944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // mark variables as initialized if they have an initializer which is 68044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // reachable from here. 68144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Initialized); 68244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 68344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek else if (Callee->hasAttr<AnalyzerNoReturnAttr>()) { 68444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // Functions labeled like "analyzer_noreturn" are often used to denote 68544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // "panic" functions that in special debug situations can still return, 68644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // but for the most part should not be treated as returning. This is a 68744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // useful annotation borrowed from the static analyzer that is useful for 68844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // suppressing branch-specific false positives when we call one of these 68944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // functions but keep pretending the path continues (when in reality the 69044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // user doesn't care). 69144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Unknown); 69244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 69344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 694a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith} 695a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith 6960c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 6979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith switch (classification.get(dr)) { 6989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Ignore: 6999532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 7009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Use: 7019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith reportUse(dr, cast<VarDecl>(dr->getDecl())); 7029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 7039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Init: 7049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[cast<VarDecl>(dr->getDecl())] = Initialized; 7059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 7069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::SelfInit: 707eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek handler.handleSelfInit(cast<VarDecl>(dr->getDecl())); 7089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 709610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 710610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 711610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 7129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { 7139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (BO->getOpcode() == BO_Assign) { 7149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(BO->getLHS()); 7159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const VarDecl *VD = Var.getDecl()) 7169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 717610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 718610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 719610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 7209532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 721651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (auto *DI : DS->decls()) { 722651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarDecl *VD = dyn_cast<VarDecl>(DI); 7239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) { 7249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (getSelfInitExpr(VD)) { 7259532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // If the initializer consists solely of a reference to itself, we 7269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // explicitly mark the variable as uninitialized. This allows code 7279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // like the following: 7289532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 7299532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int x = x; 7309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 7319532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // to deliberately leave a variable uninitialized. Different analysis 7329532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // clients can detect this pattern and adjust their reporting 7339532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // appropriately, but we need to continue to analyze subsequent uses 7349532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // of the variable. 7359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 7369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else if (VD->getInit()) { 7379532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Treat the new variable as initialized. 7389532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 7399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else { 7409532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // No initializer: the variable is now uninitialized. This matters 7419532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // for cases like: 7429532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // while (...) { 7439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int n; 7449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use(n); 7459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // n = 0; 7469532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // } 7479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // FIXME: Mark the variable as uninitialized whenever its scope is 7489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // left, since its scope could be re-entered by a jump over the 7499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // declaration. 7509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 7510c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek } 752dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 753dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 754610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 755610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 75625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenekvoid TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { 75725c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // If the Objective-C message expression is an implicit no-return that 75825c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // is not modeled in the CFG, set the tracked dataflow values to Unknown. 75925c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek if (objCNoRet.isImplicitNoReturn(ME)) { 76025c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek vals.setAllScratchValues(Unknown); 76125c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek } 76225c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek} 76325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek 764610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 765610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// High-level "driver" logic for uninitialized values analysis. 766610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 767610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 76813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenekstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 7691d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, CFGBlockValues &vals, 7709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 771f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector &wasAnalyzed, 772eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler) { 773f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek wasAnalyzed[block->getBlockID()] = true; 774610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.resetScratch(); 775eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek // Merge in values of predecessor blocks. 776610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool isFirst = true; 777610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 778610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->pred_end(); I != E; ++I) { 7796f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *pred = *I; 780651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!pred) 781651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines continue; 7826f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (wasAnalyzed[pred->getBlockID()]) { 783eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); 7846f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek isFirst = false; 7856f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek } 786610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 787610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Apply the transfer function. 7889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith TransferFunctions tf(vals, cfg, block, ac, classification, handler); 789610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 790610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek I != E; ++I) { 791b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> cs = I->getAs<CFGStmt>()) 792b07805485c603be3d8011f72611465324c9e664bDavid Blaikie tf.Visit(const_cast<Stmt*>(cs->getStmt())); 793610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 794136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectorWithScratch(block); 795610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 796610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 797eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// PruneBlocksHandler is a special UninitVariablesHandler that is used 798eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// to detect when a CFGBlock has any *potential* use of an uninitialized 799eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// variable. It is mainly used to prune out work during the final 800eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// reporting pass. 801eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremeneknamespace { 802eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenekstruct PruneBlocksHandler : public UninitVariablesHandler { 803eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PruneBlocksHandler(unsigned numBlocks) 804eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek : hadUse(numBlocks, false), hadAnyUse(false), 805eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek currentBlock(0) {} 806eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 807eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek virtual ~PruneBlocksHandler() {} 808eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 809eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Records if a CFGBlock had a potential use of an uninitialized variable. 810eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek llvm::BitVector hadUse; 811eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 812eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Records if any CFGBlock had a potential use of an uninitialized variable. 813eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek bool hadAnyUse; 814eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 815eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// The current block to scribble use information. 816eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek unsigned currentBlock; 817eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 818651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void handleUseOfUninitVariable(const VarDecl *vd, 819651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines const UninitUse &use) override { 820eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadUse[currentBlock] = true; 821eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadAnyUse = true; 822eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek } 823eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 824eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Called when the uninitialized variable analysis detects the 825eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// idiom 'int x = x'. All other uses of 'x' within the initializer 826eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// are handled by handleUseOfUninitVariable. 827651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void handleSelfInit(const VarDecl *vd) override { 828eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadUse[currentBlock] = true; 829eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadAnyUse = true; 830eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek } 831eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek}; 832eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek} 833eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 8345d98994c7749312a43ce6adf45537979a98e7afdChandler Carruthvoid clang::runUninitializedVariablesAnalysis( 8355d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const DeclContext &dc, 8365d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const CFG &cfg, 8371d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, 8385d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesHandler &handler, 8395d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesAnalysisStats &stats) { 840610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues vals(cfg); 841610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.computeSetOfDeclarations(dc); 842610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (vals.hasNoDeclarations()) 843610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 844d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 8455d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth stats.NumVariablesAnalyzed = vals.getNumEntries(); 8465d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth 8479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Precompute which expressions are uses and which are initializations. 8489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith ClassifyRefs classification(ac); 8499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith cfg.VisitBlockStmts(classification); 8509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 851d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Mark all variables uninitialized at the entry. 852d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek const CFGBlock &entry = cfg.getEntry(); 853eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &vec = vals.getValueVector(&entry); 854eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek const unsigned n = vals.getNumEntries(); 855eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (unsigned j = 0; j < n ; ++j) { 856eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vec[j] = Uninitialized; 857d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek } 858d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 859d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Proceed with the workist. 860c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek DataflowWorklist worklist(cfg, *ac.getAnalysis<PostOrderCFGView>()); 861496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 862610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(&cfg.getEntry()); 863f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 8646f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek wasAnalyzed[cfg.getEntry().getBlockID()] = true; 865eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PruneBlocksHandler PBH(cfg.getNumBlockIDs()); 866610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 867610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 868eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PBH.currentBlock = block->getBlockID(); 869eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 870610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Did the block change? 8719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith bool changed = runOnBlock(block, cfg, ac, vals, 872eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek classification, wasAnalyzed, PBH); 8735d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 874610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed || !previouslyVisited[block->getBlockID()]) 875610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(block); 876610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek previouslyVisited[block->getBlockID()] = true; 877610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 878eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 879eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek if (!PBH.hadAnyUse) 880eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek return; 881eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 88267d472c19310c06efd5cb87c60b8489abf507233Enea Zaffanella // Run through the blocks one more time, and report uninitialized variables. 883610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 8846f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *block = *BI; 885eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek if (PBH.hadUse[block->getBlockID()]) { 886eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler); 8875d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 8885d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth } 889610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 890610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 891610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 892610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekUninitVariablesHandler::~UninitVariablesHandler() {} 893