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" 173ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar#include "clang/AST/DeclCXX.h" 18d049b40ef411eee12a735233dbe04fdc42c67e1aJordan Rose#include "clang/AST/StmtVisitor.h" 19c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek#include "clang/Analysis/Analyses/PostOrderCFGView.h" 206f34213f8d6ae8c77685b53664527e39bfaaca3bTed Kremenek#include "clang/Analysis/Analyses/UninitializedValues.h" 212fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "clang/Analysis/AnalysisContext.h" 222fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "clang/Analysis/CFG.h" 2325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" 242fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/DenseMap.h" 252fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/Optional.h" 262fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/PackedVector.h" 272fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/SmallBitVector.h" 282fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include "llvm/ADT/SmallVector.h" 29b2c60b04a597cc5ba4154837cf8e0a155a376fd7Argyrios Kyrtzidis#include "llvm/Support/SaveAndRestore.h" 302fa67efeaf66a9332c30a026dc1c21bef6c33a6cBenjamin Kramer#include <utility> 31610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 32610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekusing namespace clang; 33610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 34558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#define DEBUG_LOGGING 0 35558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith 3640900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenekstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 371cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 38c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines !vd->isExceptionVariable() && !vd->isInitCapture() && 391cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek vd->getDeclContext() == dc) { 401cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek QualType ty = vd->getType(); 413ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return ty->isScalarType() || ty->isVectorType() || ty->isRecordType(); 421cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek } 431cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek return false; 44c104e53639de4424b83955acfadc977773b5883dTed Kremenek} 45c104e53639de4424b83955acfadc977773b5883dTed Kremenek 46610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 47136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek// DeclToIndex: a mapping from Decls we track to value indices. 48610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 49610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 50610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 51136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekclass DeclToIndex { 52610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek llvm::DenseMap<const VarDecl *, unsigned> map; 53610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 54136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek DeclToIndex() {} 55610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 56610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Compute the actual mapping from declarations to bits. 57610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeMap(const DeclContext &dc); 58610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 59610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Return the number of declarations in the map. 60610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned size() const { return map.size(); } 61610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 62610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Returns the bit vector index for a given declaration. 63dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie Optional<unsigned> getValueIndex(const VarDecl *d) const; 64610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 65610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 66610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 67136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekvoid DeclToIndex::computeMap(const DeclContext &dc) { 68610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned count = 0; 69610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 70610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E(dc.decls_end()); 71610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for ( ; I != E; ++I) { 72581deb3da481053c4993c7600f97acf7768caac5David Blaikie const VarDecl *vd = *I; 7340900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek if (isTrackedVar(vd, &dc)) 74610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek map[vd] = count++; 75610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 76610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 77610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 78dc84cd5efdd3430efb22546b4ac656aa0540b210David BlaikieOptional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 79b831c673621c5587642343cace9def134916a17bTed Kremenek llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 80610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (I == map.end()) 8166874fb18afbffb8b2ca05576851a64534be3352David Blaikie return None; 82610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return I->second; 83610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 84610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 85610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 86610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// CFGBlockValues: dataflow values for CFG blocks. 87610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 88610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 89f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// These values are defined in such a way that a merge can be done using 90f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// a bitwise OR. 91f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekenum Value { Unknown = 0x0, /* 00 */ 92f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Initialized = 0x1, /* 01 */ 93f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Uninitialized = 0x2, /* 10 */ 94f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek MayUninitialized = 0x3 /* 11 */ }; 95f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek 96f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isUninitialized(const Value v) { 97f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v >= Uninitialized; 98f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 99f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isAlwaysUninit(const Value v) { 100f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v == Uninitialized; 101f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 102afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 103da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramernamespace { 104afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 105da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramertypedef llvm::PackedVector<Value, 2, llvm::SmallBitVector> ValueVector; 10613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 107610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass CFGBlockValues { 108610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 109da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramer SmallVector<ValueVector, 8> vals; 110136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector scratch; 1114ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek DeclToIndex declToIndex; 112610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 113610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues(const CFG &cfg); 114eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek 115d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek unsigned getNumEntries() const { return declToIndex.size(); } 116d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 117610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeSetOfDeclarations(const DeclContext &dc); 118eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &getValueVector(const CFGBlock *block) { 119da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramer return vals[block->getBlockID()]; 120eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek } 12113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 122a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith void setAllScratchValues(Value V); 123136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek void mergeIntoScratch(ValueVector const &source, bool isFirst); 124136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool updateValueVectorWithScratch(const CFGBlock *block); 125610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 126610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool hasNoDeclarations() const { 1274ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek return declToIndex.size() == 0; 128610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 129e0e29332c89da22b6890929b97e6f568c917d85fTed Kremenek 130610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void resetScratch(); 13113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 132136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector::reference operator[](const VarDecl *vd); 1332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 1342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, 1352815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const VarDecl *vd) { 136dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie const Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 1372815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith assert(idx.hasValue()); 138eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek return getValueVector(block)[idx.getValue()]; 1392815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 140610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 141da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramer} // end anonymous namespace 142610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 143eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed KremenekCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} 144610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 145610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 1464ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek declToIndex.computeMap(dc); 147eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek unsigned decls = declToIndex.size(); 148eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek scratch.resize(decls); 149eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek unsigned n = cfg.getNumBlockIDs(); 150eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek if (!n) 151eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek return; 152eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals.resize(n); 153eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (unsigned i = 0; i < n; ++i) 154da3d76b4cfbb5ebeb79e03a0abeabd403fe9260aBenjamin Kramer vals[i].resize(decls); 15513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 15613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 157558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#if DEBUG_LOGGING 158136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekstatic void printVector(const CFGBlock *block, ValueVector &bv, 1599fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek unsigned num) { 1609fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << block->getBlockID() << " :"; 1619fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek for (unsigned i = 0; i < bv.size(); ++i) { 1629fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << ' ' << bv[i]; 1639fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek } 1649fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << " : " << num << '\n'; 1659fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek} 1669fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 167610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 168a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smithvoid CFGBlockValues::setAllScratchValues(Value V) { 169a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith for (unsigned I = 0, E = scratch.size(); I != E; ++I) 170a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith scratch[I] = V; 171a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith} 172a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith 173c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenekvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 174c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek bool isFirst) { 175c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek if (isFirst) 176c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch = source; 177c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek else 178c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch |= source; 179c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek} 180c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 181136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 182eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &dst = getValueVector(block); 183610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool changed = (dst != scratch); 184610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed) 185610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek dst = scratch; 186558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#if DEBUG_LOGGING 1879fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, scratch, 0); 1889fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 18913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return changed; 19013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 19113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 192610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::resetScratch() { 193610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek scratch.reset(); 194610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 195610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 196136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 197dc84cd5efdd3430efb22546b4ac656aa0540b210David Blaikie const Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 198610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek assert(idx.hasValue()); 199610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return scratch[idx.getValue()]; 200610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 201610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 202610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 203610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// Worklist: worklist for dataflow analysis. 204610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 205610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 206610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 207610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass DataflowWorklist { 208c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek PostOrderCFGView::iterator PO_I, PO_E; 2095f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<const CFGBlock *, 20> worklist; 210496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector enqueuedBlocks; 211610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 212c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek DataflowWorklist(const CFG &cfg, PostOrderCFGView &view) 213c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek : PO_I(view.begin()), PO_E(view.end()), 214c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek enqueuedBlocks(cfg.getNumBlockIDs(), true) { 215c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // Treat the first block as already analyzed. 216c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek if (PO_I != PO_E) { 217c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek assert(*PO_I == &cfg.getEntry()); 218c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek enqueuedBlocks[(*PO_I)->getBlockID()] = false; 219c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek ++PO_I; 220c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 221c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 222610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 223610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void enqueueSuccessors(const CFGBlock *block); 224610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *dequeue(); 225610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 226610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 227610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 228610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 229610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_succ_iterator I = block->succ_begin(), 230610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->succ_end(); I != E; ++I) { 2318052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth const CFGBlock *Successor = *I; 2328052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 2338052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth continue; 2348052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth worklist.push_back(Successor); 2358052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth enqueuedBlocks[Successor->getBlockID()] = true; 236610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 237610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 238610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 239610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekconst CFGBlock *DataflowWorklist::dequeue() { 2406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const CFGBlock *B = nullptr; 241c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek 242c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // First dequeue from the worklist. This can represent 243c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // updates along backedges that we want propagated as quickly as possible. 244344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm if (!worklist.empty()) 245344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm B = worklist.pop_back_val(); 246344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm 247c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // Next dequeue from the initial reverse post order. This is the 248c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek // theoretical ideal in the presence of no back edges. 249c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek else if (PO_I != PO_E) { 250c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek B = *PO_I; 251c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek ++PO_I; 252c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 253c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek else { 2546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 255c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek } 256c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek 257c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek assert(enqueuedBlocks[B->getBlockID()] == true); 258c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek enqueuedBlocks[B->getBlockID()] = false; 259c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek return B; 260610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 261610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 262610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 2639532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith// Classification of DeclRefExprs as use or initialization. 264610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 265610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 266610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 267610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass FindVarResult { 268610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd; 269610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *dr; 270610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 2719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} 2729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 273610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *getDeclRefExpr() const { return dr; } 274610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *getDecl() const { return vd; } 275610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 2769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 2779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 2789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith while (Ex) { 2799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ex = Ex->IgnoreParenNoopCasts(C); 2809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 2819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CE->getCastKind() == CK_LValueBitCast) { 2829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ex = CE->getSubExpr(); 2839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith continue; 2849532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 2879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Ex; 2899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 2909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 2919532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// If E is an expression comprising a reference to a single variable, find that 2929532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// variable. 2939532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic FindVarResult findVar(const Expr *E, const DeclContext *DC) { 2949532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = 2959532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith dyn_cast<DeclRefExpr>(stripCasts(DC->getParentASTContext(), E))) 2969532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) 2979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (isTrackedVar(VD, DC)) 2989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return FindVarResult(VD, DRE); 2996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return FindVarResult(nullptr, nullptr); 3009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// \brief Classify each DeclRefExpr as an initialization or a use. Any 3039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// DeclRefExpr which isn't explicitly classified will be assumed to have 3049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// escaped the analysis and will be treated as an initialization. 3059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithclass ClassifyRefs : public StmtVisitor<ClassifyRefs> { 3069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithpublic: 3079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith enum Class { 3089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Init, 3099532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Use, 3109532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith SelfInit, 3119532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ignore 3129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith }; 3139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithprivate: 3159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const DeclContext *DC; 3169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith llvm::DenseMap<const DeclRefExpr*, Class> Classification; 3179532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith bool isTrackedVar(const VarDecl *VD) const { 3199532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return ::isTrackedVar(VD, DC); 3209532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void classify(const Expr *E, Class C); 3239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithpublic: 3259532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith ClassifyRefs(AnalysisDeclContext &AC) : DC(cast<DeclContext>(AC.getDecl())) {} 3269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitDeclStmt(DeclStmt *DS); 3289532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitUnaryOperator(UnaryOperator *UO); 3299532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitBinaryOperator(BinaryOperator *BO); 3309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitCallExpr(CallExpr *CE); 3319532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitCastExpr(CastExpr *CE); 3329532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3339532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void operator()(Stmt *S) { Visit(S); } 3349532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Class get(const DeclRefExpr *DRE) const { 3369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith llvm::DenseMap<const DeclRefExpr*, Class>::const_iterator I 3379532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith = Classification.find(DRE); 3389532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (I != Classification.end()) 3399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return I->second; 3409532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3419532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); 3429532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (!VD || !isTrackedVar(VD)) 3439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Ignore; 3449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Init; 3469532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith}; 3489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { 3513ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if (VD->getType()->isRecordType()) return nullptr; 3529532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (Expr *Init = VD->getInit()) { 3539532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const DeclRefExpr *DRE 3549532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith = dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init)); 3559532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (DRE && DRE->getDecl() == VD) 3569532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return DRE; 3579532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 3599532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3609532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3619532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::classify(const Expr *E, Class C) { 36277fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek // The result of a ?: could also be an lvalue. 36377fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek E = E->IgnoreParens(); 36477fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek if (const ConditionalOperator *CO = dyn_cast<ConditionalOperator>(E)) { 365176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(CO->getTrueExpr(), C); 36677fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek classify(CO->getFalseExpr(), C); 36777fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek return; 36877fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek } 36977fd3c0d7837040bb84c1617a6a423f833e784feTed Kremenek 370176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (const BinaryConditionalOperator *BCO = 371176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines dyn_cast<BinaryConditionalOperator>(E)) { 372176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(BCO->getFalseExpr(), C); 373176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 374176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 375176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 376176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) { 377176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(OVE->getSourceExpr(), C); 378176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 379176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 380176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 3813ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if (const MemberExpr *ME = dyn_cast<MemberExpr>(E)) { 3823ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if (VarDecl *VD = dyn_cast<VarDecl>(ME->getMemberDecl())) { 3833ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if (!VD->isStaticDataMember()) 3843ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar classify(ME->getBase(), C); 3853ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 3863ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return; 3873ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 3883ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar 389176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(E)) { 3903ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar switch (BO->getOpcode()) { 3913ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar case BO_PtrMemD: 3923ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar case BO_PtrMemI: 3933ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar classify(BO->getLHS(), C); 3943ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return; 3953ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar case BO_Comma: 396176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines classify(BO->getRHS(), C); 3973ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return; 3983ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar default: 3993ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return; 4003ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 401176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 402176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 4039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(E, DC); 4049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) 4059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = std::max(Classification[DRE], C); 4069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { 409651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (auto *DI : DS->decls()) { 410651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarDecl *VD = dyn_cast<VarDecl>(DI); 4119532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) 4129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) 4139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = SelfInit; 4149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4179532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { 4189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this 4199532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // is not a compound-assignment, we will treat it as initializing the variable 4209532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // when TransferFunctions visits it. A compound-assignment does not affect 4219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // whether a variable is uninitialized, and there's no point counting it as a 4229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use. 4236cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith if (BO->isCompoundAssignmentOp()) 4246cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith classify(BO->getLHS(), Use); 4253ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar else if (BO->getOpcode() == BO_Assign || BO->getOpcode() == BO_Comma) 4269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(BO->getLHS(), Ignore); 4279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4289532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4299532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { 4309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Increment and decrement are uses despite there being no lvalue-to-rvalue 4319532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // conversion. 4329532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (UO->isIncrementDecrementOp()) 4339532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(UO->getSubExpr(), Use); 4349532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4363ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainarstatic bool isPointerToConst(const QualType &QT) { 4373ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar return QT->isAnyPointerType() && QT->getPointeeType().isConstQualified(); 4383ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar} 4393ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar 4409532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCallExpr(CallExpr *CE) { 441176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // Classify arguments to std::move as used. 442176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (CE->getNumArgs() == 1) { 443176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (FunctionDecl *FD = CE->getDirectCallee()) { 4440e2c34f92f00628d48968dfea096d36381f494cbStephen Hines if (FD->isInStdNamespace() && FD->getIdentifier() && 4450e2c34f92f00628d48968dfea096d36381f494cbStephen Hines FD->getIdentifier()->isStr("move")) { 4463ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar // RecordTypes are handled in SemaDeclCXX.cpp. 4473ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if (!CE->getArg(0)->getType()->isRecordType()) 4483ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar classify(CE->getArg(0), Use); 449176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return; 450176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 451176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 452176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 453176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 4543ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar // If a value is passed by const pointer or by const reference to a function, 4553ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar // we should not assume that it is initialized by the call, and we 4563ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar // conservatively do not assume that it is used. 4579532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); 4583ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar I != E; ++I) { 4593ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if ((*I)->isGLValue()) { 4603ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if ((*I)->getType().isConstQualified()) 4613ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar classify((*I), Ignore); 4623ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } else if (isPointerToConst((*I)->getType())) { 4633ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar const Expr *Ex = stripCasts(DC->getParentASTContext(), *I); 4643ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar const UnaryOperator *UO = dyn_cast<UnaryOperator>(Ex); 4653ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar if (UO && UO->getOpcode() == UO_AddrOf) 4663ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar Ex = UO->getSubExpr(); 4673ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar classify(Ex, Ignore); 4683ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 4693ea9e33ea25e0c2b12db56418ba3f994eb662c04Pirama Arumuga Nainar } 4709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCastExpr(CastExpr *CE) { 4739532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CE->getCastKind() == CK_LValueToRValue) 4749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CE->getSubExpr(), Use); 4759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith else if (CStyleCastExpr *CSE = dyn_cast<CStyleCastExpr>(CE)) { 4769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CSE->getType()->isVoidType()) { 4779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Squelch any detected load of an uninitialized value if 4789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // we cast it to void. 4799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // e.g. (void) x; 4809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CSE->getSubExpr(), Ignore); 4819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4849532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//------------------------------------------------------------------------====// 4869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith// Transfer function for uninitialized values analysis. 4879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//====------------------------------------------------------------------------// 4889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithnamespace { 4900c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 491610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues &vals; 492610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 4932815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block; 4941d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext ∾ 4959532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification; 49625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek ObjCNoReturn objCNoRet; 497eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler; 4989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 499610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 500610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 5012815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block, AnalysisDeclContext &ac, 5029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 503eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler) 5049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith : vals(vals), cfg(cfg), block(block), ac(ac), 50525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek classification(classification), objCNoRet(ac.getASTContext()), 50625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek handler(handler) {} 5079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 508818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith void reportUse(const Expr *ex, const VarDecl *vd); 509a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 51025c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitBinaryOperator(BinaryOperator *bo); 511a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek void VisitBlockExpr(BlockExpr *be); 512a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith void VisitCallExpr(CallExpr *ce); 513c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek void VisitDeclRefExpr(DeclRefExpr *dr); 51425c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitDeclStmt(DeclStmt *ds); 51525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); 51625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCMessageExpr(ObjCMessageExpr *ME); 5172815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 51840900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek bool isTrackedVar(const VarDecl *vd) { 51940900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 52040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek } 5212815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult findVar(const Expr *ex) { 5239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return ::findVar(ex, cast<DeclContext>(ac.getDecl())); 5249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 5259532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 5262815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { 5272815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse Use(ex, isAlwaysUninit(v)); 5282815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5292815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith assert(isUninitialized(v)); 5302815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Use.getKind() == UninitUse::Always) 5312815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 5322815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // If an edge which leads unconditionally to this use did not initialize 5342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable, we can say something stronger than 'may be uninitialized': 5352815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // we can say 'either it's used uninitialized or you have dead code'. 5362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5372815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // We track the number of successors of a node which have been visited, and 5382815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // visit a node once we have visited all of its successors. Only edges where 5392815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable might still be uninitialized are followed. Since a variable 5402815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // can't transfer from being initialized to being uninitialized, this will 5412815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // trace out the subgraph which inevitably leads to the use and does not 5422815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // initialize the variable. We do not want to skip past loops, since their 5432815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // non-termination might be correlated with the initialization condition. 5442815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5452815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // For example: 5462815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5472815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // void f(bool a, bool b) { 5482815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block1: int n; 5492815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // if (a) { 5502815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block2: if (b) 5512815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block3: n = 1; 5522815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block4: } else if (b) { 5532815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block5: while (!a) { 5542815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block6: do_work(&a); 5552815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // n = 2; 5562815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 5572815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 5582815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block7: if (a) 5592815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block8: g(); 5602815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block9: return n; 5612815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 5622815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5632815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Starting from the maybe-uninitialized use in block 9: 5642815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is not visited because we have only visited one of its two 5652815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // successors. 5662815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 8 is visited because we've visited its only successor. 5672815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 8: 5682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is visited because we've now visited both of its successors. 5692815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 7: 5702815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all 5712815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). 5722815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 3 is not visited because it initializes 'n'. 5732815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Now the algorithm terminates, having visited blocks 7 and 8, and having 5742815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // found the frontier is blocks 2, 4, and 5. 5752815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 5762815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 5772815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // and 4), so we report that any time either of those edges is taken (in 5782815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // each case when 'b == false'), 'n' is used uninitialized. 579cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<const CFGBlock*, 32> Queue; 580cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0); 5812815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(block); 5822815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Specify that we've already visited all successors of the starting block. 5832815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This has the dual purpose of ensuring we never add it to the queue, and 5842815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of marking it as not being a candidate element of the frontier. 5852815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith SuccsVisited[block->getBlockID()] = block->succ_size(); 5862815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith while (!Queue.empty()) { 587344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm const CFGBlock *B = Queue.pop_back_val(); 5888a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith 5898a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // If the use is always reached from the entry block, make a note of that. 5908a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (B == &cfg.getEntry()) 5918a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Use.setUninitAfterCall(); 5928a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith 5932815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); 5942815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith I != E; ++I) { 5952815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Pred = *I; 596651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!Pred) 597651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines continue; 598651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 5998a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Value AtPredExit = vals.getValue(Pred, B, vd); 6008a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (AtPredExit == Initialized) 6012815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block initializes the variable. 6022815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 6038a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith if (AtPredExit == MayUninitialized && 6046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines vals.getValue(B, nullptr, vd) == Uninitialized) { 6058a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // This block declares the variable (uninitialized), and is reachable 6068a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // from a block that initializes the variable. We can't guarantee to 6078a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // give an earlier location for the diagnostic (and it appears that 6088a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // this code is intended to be reachable) so give a diagnostic here 6098a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith // and go no further down this path. 6108a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith Use.setUninitAfterDecl(); 6118a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith continue; 6128a1fdfc69cc6c2ccbfd57fc8ff643c589da9df9bRichard Smith } 6132815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 614558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith unsigned &SV = SuccsVisited[Pred->getBlockID()]; 615558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!SV) { 616558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // When visiting the first successor of a block, mark all NULL 617558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // successors as having been visited. 618558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), 619558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SE = Pred->succ_end(); 620558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SI != SE; ++SI) 621558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!*SI) 622558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith ++SV; 623558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith } 624558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith 625558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (++SV == Pred->succ_size()) 6262815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // All paths from this block lead to the use and don't initialize the 6272815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // variable. 6282815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(Pred); 6292815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6302815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6312815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 6322815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Scan the frontier, looking for blocks where the variable was 6332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // uninitialized. 6342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 6352815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Block = *BI; 6362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith unsigned BlockID = Block->getBlockID(); 6372815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Term = Block->getTerminator(); 6382815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && 6392815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Term) { 6402815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block inevitably leads to the use. If we have an edge from here 6412815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // to a post-dominator block, and the variable is uninitialized on that 6422815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // edge, we have found a bug. 6432815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_succ_iterator I = Block->succ_begin(), 6442815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith E = Block->succ_end(); I != E; ++I) { 6452815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Succ = *I; 6462815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && 6472815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith vals.getValue(Block, Succ, vd) == Uninitialized) { 6482815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Switch cases are a special case: report the label to the caller 6492815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // as the 'terminator', not the switch statement itself. Suppress 6502815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // situations where no label matched: we can't be sure that's 6512815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // possible. 6522815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (isa<SwitchStmt>(Term)) { 6532815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Label = Succ->getLabel(); 6542815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (!Label || !isa<SwitchCase>(Label)) 6552815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Might not be possible. 6562815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 6572815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 6582815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Label; 6592815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = 0; // Ignored. 6602815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 6612815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } else { 6622815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 6632815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Term; 6642815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = I - Block->succ_begin(); 6652815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 6662815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6672815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6692815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6702815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 6712815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 6722815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 6732815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 674610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 675610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 676610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 677818918855d84e3db1af5a0807070d4995ca2cf75Richard Smithvoid TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { 678818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith Value v = vals[vd]; 679818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith if (isUninitialized(v)) 680eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek handler.handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); 681610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 682610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { 6841ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // This represents an initialization of the 'element' value. 6859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (DeclStmt *DS = dyn_cast<DeclStmt>(FS->getElement())) { 6869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 6879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (isTrackedVar(VD)) 6889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 6891ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 6901ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 6911ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 692a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 693bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek const BlockDecl *bd = be->getBlockDecl(); 694651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (const auto &I : bd->captures()) { 695651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines const VarDecl *vd = I.getVariable(); 696bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek if (!isTrackedVar(vd)) 697bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 698651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (I.isByRef()) { 699bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek vals[vd] = Initialized; 700bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 701bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek } 702818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith reportUse(be, vd); 703a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek } 704a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek} 705a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 706a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smithvoid TransferFunctions::VisitCallExpr(CallExpr *ce) { 70744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Decl *Callee = ce->getCalleeDecl()) { 70844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Callee->hasAttr<ReturnsTwiceAttr>()) { 70944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // After a call to a function like setjmp or vfork, any variable which is 71044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // initialized anywhere within this function may now be initialized. For 71144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // now, just assume such a call initializes all variables. FIXME: Only 71244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // mark variables as initialized if they have an initializer which is 71344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // reachable from here. 71444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Initialized); 71544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 71644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek else if (Callee->hasAttr<AnalyzerNoReturnAttr>()) { 71744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // Functions labeled like "analyzer_noreturn" are often used to denote 71844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // "panic" functions that in special debug situations can still return, 71944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // but for the most part should not be treated as returning. This is a 72044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // useful annotation borrowed from the static analyzer that is useful for 72144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // suppressing branch-specific false positives when we call one of these 72244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // functions but keep pretending the path continues (when in reality the 72344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // user doesn't care). 72444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Unknown); 72544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 72644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 727a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith} 728a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith 7290c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 7309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith switch (classification.get(dr)) { 7319532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Ignore: 7329532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 7339532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Use: 7349532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith reportUse(dr, cast<VarDecl>(dr->getDecl())); 7359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 7369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Init: 7379532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[cast<VarDecl>(dr->getDecl())] = Initialized; 7389532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 7399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::SelfInit: 740eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek handler.handleSelfInit(cast<VarDecl>(dr->getDecl())); 7419532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 742610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 743610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 744610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 7459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { 7469532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (BO->getOpcode() == BO_Assign) { 7479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(BO->getLHS()); 7489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const VarDecl *VD = Var.getDecl()) 7499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 750610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 751610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 752610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 7539532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 754651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (auto *DI : DS->decls()) { 755651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines VarDecl *VD = dyn_cast<VarDecl>(DI); 7569532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) { 7579532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (getSelfInitExpr(VD)) { 7589532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // If the initializer consists solely of a reference to itself, we 7599532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // explicitly mark the variable as uninitialized. This allows code 7609532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // like the following: 7619532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 7629532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int x = x; 7639532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 7649532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // to deliberately leave a variable uninitialized. Different analysis 7659532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // clients can detect this pattern and adjust their reporting 7669532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // appropriately, but we need to continue to analyze subsequent uses 7679532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // of the variable. 7689532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 7699532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else if (VD->getInit()) { 7709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Treat the new variable as initialized. 7719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 7729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else { 7739532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // No initializer: the variable is now uninitialized. This matters 7749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // for cases like: 7759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // while (...) { 7769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int n; 7779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use(n); 7789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // n = 0; 7799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // } 7809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // FIXME: Mark the variable as uninitialized whenever its scope is 7819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // left, since its scope could be re-entered by a jump over the 7829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // declaration. 7839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 7840c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek } 785dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 786dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 787610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 788610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 78925c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenekvoid TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { 79025c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // If the Objective-C message expression is an implicit no-return that 79125c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // is not modeled in the CFG, set the tracked dataflow values to Unknown. 79225c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek if (objCNoRet.isImplicitNoReturn(ME)) { 79325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek vals.setAllScratchValues(Unknown); 79425c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek } 79525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek} 79625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek 797610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 798610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// High-level "driver" logic for uninitialized values analysis. 799610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 800610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 80113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenekstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 8021d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, CFGBlockValues &vals, 8039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 804f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector &wasAnalyzed, 805eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek UninitVariablesHandler &handler) { 806f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek wasAnalyzed[block->getBlockID()] = true; 807610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.resetScratch(); 808eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek // Merge in values of predecessor blocks. 809610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool isFirst = true; 810610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 811610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->pred_end(); I != E; ++I) { 8126f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *pred = *I; 813651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (!pred) 814651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines continue; 8156f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (wasAnalyzed[pred->getBlockID()]) { 816eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); 8176f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek isFirst = false; 8186f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek } 819610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 820610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Apply the transfer function. 8219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith TransferFunctions tf(vals, cfg, block, ac, classification, handler); 822610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 823610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek I != E; ++I) { 824b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> cs = I->getAs<CFGStmt>()) 825b07805485c603be3d8011f72611465324c9e664bDavid Blaikie tf.Visit(const_cast<Stmt*>(cs->getStmt())); 826610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 827136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectorWithScratch(block); 828610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 829610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 830eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// PruneBlocksHandler is a special UninitVariablesHandler that is used 831eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// to detect when a CFGBlock has any *potential* use of an uninitialized 832eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// variable. It is mainly used to prune out work during the final 833eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek/// reporting pass. 834eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremeneknamespace { 835eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenekstruct PruneBlocksHandler : public UninitVariablesHandler { 836eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PruneBlocksHandler(unsigned numBlocks) 837eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek : hadUse(numBlocks, false), hadAnyUse(false), 838eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek currentBlock(0) {} 839eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 84033337ca4d89605025818daf83390ab4271d598d9Pirama Arumuga Nainar ~PruneBlocksHandler() override {} 841eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 842eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Records if a CFGBlock had a potential use of an uninitialized variable. 843eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek llvm::BitVector hadUse; 844eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 845eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Records if any CFGBlock had a potential use of an uninitialized variable. 846eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek bool hadAnyUse; 847eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 848eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// The current block to scribble use information. 849eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek unsigned currentBlock; 850eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 851651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void handleUseOfUninitVariable(const VarDecl *vd, 852651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines const UninitUse &use) override { 853eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadUse[currentBlock] = true; 854eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadAnyUse = true; 855eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek } 856eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 857eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// Called when the uninitialized variable analysis detects the 858eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// idiom 'int x = x'. All other uses of 'x' within the initializer 859eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek /// are handled by handleUseOfUninitVariable. 860651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines void handleSelfInit(const VarDecl *vd) override { 861eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadUse[currentBlock] = true; 862eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek hadAnyUse = true; 863eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek } 864eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek}; 865eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek} 866eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 8675d98994c7749312a43ce6adf45537979a98e7afdChandler Carruthvoid clang::runUninitializedVariablesAnalysis( 8685d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const DeclContext &dc, 8695d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const CFG &cfg, 8701d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, 8715d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesHandler &handler, 8725d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesAnalysisStats &stats) { 873610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues vals(cfg); 874610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.computeSetOfDeclarations(dc); 875610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (vals.hasNoDeclarations()) 876610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 877d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 8785d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth stats.NumVariablesAnalyzed = vals.getNumEntries(); 8795d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth 8809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Precompute which expressions are uses and which are initializations. 8819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith ClassifyRefs classification(ac); 8829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith cfg.VisitBlockStmts(classification); 8839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 884d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Mark all variables uninitialized at the entry. 885d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek const CFGBlock &entry = cfg.getEntry(); 886eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &vec = vals.getValueVector(&entry); 887eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek const unsigned n = vals.getNumEntries(); 888eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (unsigned j = 0; j < n ; ++j) { 889eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vec[j] = Uninitialized; 890d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek } 891d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 892d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Proceed with the workist. 893c1602581f7a4eab486489f09647d724ce35d3f23Ted Kremenek DataflowWorklist worklist(cfg, *ac.getAnalysis<PostOrderCFGView>()); 894496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 895610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(&cfg.getEntry()); 896f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 8976f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek wasAnalyzed[cfg.getEntry().getBlockID()] = true; 898eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PruneBlocksHandler PBH(cfg.getNumBlockIDs()); 899610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 900610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 901eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek PBH.currentBlock = block->getBlockID(); 902eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 903610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Did the block change? 9049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith bool changed = runOnBlock(block, cfg, ac, vals, 905eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek classification, wasAnalyzed, PBH); 9065d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 907610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed || !previouslyVisited[block->getBlockID()]) 908610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(block); 909610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek previouslyVisited[block->getBlockID()] = true; 910610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 911eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 912eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek if (!PBH.hadAnyUse) 913eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek return; 914eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek 91567d472c19310c06efd5cb87c60b8489abf507233Enea Zaffanella // Run through the blocks one more time, and report uninitialized variables. 916610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 9176f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *block = *BI; 918eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek if (PBH.hadUse[block->getBlockID()]) { 919eba76a4379997f66f8114eb7e63206a5932b1be8Ted Kremenek runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, handler); 9205d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 9215d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth } 922610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 923610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 924610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 925610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekUninitVariablesHandler::~UninitVariablesHandler() {} 926