UninitializedValues.cpp revision 25c1d57fc906e895535fb5c7e6dde80219f353b5
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 1413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek#include <utility> 15610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "llvm/ADT/Optional.h" 16610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "llvm/ADT/SmallVector.h" 17049f6d0239e242dc338be6ac6f6c5175803d2163Argyrios Kyrtzidis#include "llvm/ADT/PackedVector.h" 18610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "llvm/ADT/DenseMap.h" 19558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#include "clang/AST/ASTContext.h" 20610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "clang/AST/Decl.h" 21610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "clang/Analysis/CFG.h" 22a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek#include "clang/Analysis/AnalysisContext.h" 23610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 246f34213f8d6ae8c77685b53664527e39bfaaca3bTed Kremenek#include "clang/Analysis/Analyses/UninitializedValues.h" 2525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h" 26b2c60b04a597cc5ba4154837cf8e0a155a376fd7Argyrios Kyrtzidis#include "llvm/Support/SaveAndRestore.h" 27610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 28610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekusing namespace clang; 29610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 30558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#define DEBUG_LOGGING 0 31558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith 3240900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenekstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 331cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 34a21612f95792c1ea8b4362f0861f0c724c39388eTed Kremenek !vd->isExceptionVariable() && 351cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek vd->getDeclContext() == dc) { 361cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek QualType ty = vd->getType(); 371cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek return ty->isScalarType() || ty->isVectorType(); 381cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek } 391cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek return false; 40c104e53639de4424b83955acfadc977773b5883dTed Kremenek} 41c104e53639de4424b83955acfadc977773b5883dTed Kremenek 42610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 43136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek// DeclToIndex: a mapping from Decls we track to value indices. 44610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 45610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 46610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 47136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekclass DeclToIndex { 48610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek llvm::DenseMap<const VarDecl *, unsigned> map; 49610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 50136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek DeclToIndex() {} 51610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 52610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Compute the actual mapping from declarations to bits. 53610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeMap(const DeclContext &dc); 54610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 55610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Return the number of declarations in the map. 56610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned size() const { return map.size(); } 57610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 58610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Returns the bit vector index for a given declaration. 59b831c673621c5587642343cace9def134916a17bTed Kremenek llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const; 60610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 61610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 62610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 63136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekvoid DeclToIndex::computeMap(const DeclContext &dc) { 64610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned count = 0; 65610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 66610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E(dc.decls_end()); 67610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for ( ; I != E; ++I) { 68581deb3da481053c4993c7600f97acf7768caac5David Blaikie const VarDecl *vd = *I; 6940900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek if (isTrackedVar(vd, &dc)) 70610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek map[vd] = count++; 71610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 72610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 73610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 74b831c673621c5587642343cace9def134916a17bTed Kremenekllvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 75b831c673621c5587642343cace9def134916a17bTed Kremenek llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 76610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (I == map.end()) 77610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return llvm::Optional<unsigned>(); 78610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return I->second; 79610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 80610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 81610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 82610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// CFGBlockValues: dataflow values for CFG blocks. 83610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 84610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 85f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// These values are defined in such a way that a merge can be done using 86f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// a bitwise OR. 87f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekenum Value { Unknown = 0x0, /* 00 */ 88f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Initialized = 0x1, /* 01 */ 89f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Uninitialized = 0x2, /* 10 */ 90f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek MayUninitialized = 0x3 /* 11 */ }; 91f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek 92f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isUninitialized(const Value v) { 93f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v >= Uninitialized; 94f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 95f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isAlwaysUninit(const Value v) { 96f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v == Uninitialized; 97f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 98afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 99da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramernamespace { 100afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 101049f6d0239e242dc338be6ac6f6c5175803d2163Argyrios Kyrtzidistypedef llvm::PackedVector<Value, 2> ValueVector; 10213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 103610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass CFGBlockValues { 104610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 105eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek std::vector<ValueVector*> vals; 106136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector scratch; 1074ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek DeclToIndex declToIndex; 108610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 109610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues(const CFG &cfg); 110610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek ~CFGBlockValues(); 111eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek 112d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek unsigned getNumEntries() const { return declToIndex.size(); } 113d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 114610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeSetOfDeclarations(const DeclContext &dc); 115eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &getValueVector(const CFGBlock *block) { 116eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek return *vals[block->getBlockID()]; 117eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek } 11813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 119a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith void setAllScratchValues(Value V); 120136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek void mergeIntoScratch(ValueVector const &source, bool isFirst); 121136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool updateValueVectorWithScratch(const CFGBlock *block); 122610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 123610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool hasNoDeclarations() const { 1244ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek return declToIndex.size() == 0; 125610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 126e0e29332c89da22b6890929b97e6f568c917d85fTed Kremenek 127610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void resetScratch(); 12813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 129136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector::reference operator[](const VarDecl *vd); 1302815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 1312815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Value getValue(const CFGBlock *block, const CFGBlock *dstBlock, 1322815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const VarDecl *vd) { 1332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 1342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith assert(idx.hasValue()); 135eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek return getValueVector(block)[idx.getValue()]; 1362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 137610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 138da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramer} // end anonymous namespace 139610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 140eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed KremenekCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {} 141610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 142610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekCFGBlockValues::~CFGBlockValues() { 143eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (std::vector<ValueVector*>::iterator I = vals.begin(), E = vals.end(); 144eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek I != E; ++I) 145eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek delete *I; 146610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 147610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 148610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 1494ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek declToIndex.computeMap(dc); 150eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek unsigned decls = declToIndex.size(); 151eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek scratch.resize(decls); 152eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek unsigned n = cfg.getNumBlockIDs(); 153eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek if (!n) 154eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek return; 155eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals.resize(n); 156eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (unsigned i = 0; i < n; ++i) 157eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals[i] = new ValueVector(decls); 15813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 15913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 160558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#if DEBUG_LOGGING 161136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekstatic void printVector(const CFGBlock *block, ValueVector &bv, 1629fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek unsigned num) { 1639fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << block->getBlockID() << " :"; 1649fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek for (unsigned i = 0; i < bv.size(); ++i) { 1659fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << ' ' << bv[i]; 1669fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek } 1679fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << " : " << num << '\n'; 1689fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek} 1699fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 170610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 171a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smithvoid CFGBlockValues::setAllScratchValues(Value V) { 172a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith for (unsigned I = 0, E = scratch.size(); I != E; ++I) 173a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith scratch[I] = V; 174a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith} 175a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith 176c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenekvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 177c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek bool isFirst) { 178c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek if (isFirst) 179c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch = source; 180c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek else 181c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch |= source; 182c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek} 183c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 184136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 185eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &dst = getValueVector(block); 186610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool changed = (dst != scratch); 187610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed) 188610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek dst = scratch; 189558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith#if DEBUG_LOGGING 1909fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, scratch, 0); 1919fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 19213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return changed; 19313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 19413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 195610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::resetScratch() { 196610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek scratch.reset(); 197610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 198610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 199136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 2004ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 201610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek assert(idx.hasValue()); 202610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return scratch[idx.getValue()]; 203610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 204610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 205610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 206610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// Worklist: worklist for dataflow analysis. 207610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 208610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 209610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 210610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass DataflowWorklist { 2115f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<const CFGBlock *, 20> worklist; 212496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector enqueuedBlocks; 213610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 214610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} 215610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 216610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void enqueueSuccessors(const CFGBlock *block); 217610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *dequeue(); 218610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 219610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 220610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 221610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 2228052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth unsigned OldWorklistSize = worklist.size(); 223610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_succ_iterator I = block->succ_begin(), 224610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->succ_end(); I != E; ++I) { 2258052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth const CFGBlock *Successor = *I; 2268052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 2278052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth continue; 2288052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth worklist.push_back(Successor); 2298052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth enqueuedBlocks[Successor->getBlockID()] = true; 230610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 2318052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 2328052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth return; 2338052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth 2348052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth // Rotate the newly added blocks to the start of the worklist so that it forms 2358052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth // a proper queue when we pop off the end of the worklist. 2368052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize, 2378052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth worklist.end()); 238610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 239610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 240610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekconst CFGBlock *DataflowWorklist::dequeue() { 241610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (worklist.empty()) 242610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return 0; 243610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *b = worklist.back(); 244610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.pop_back(); 245610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek enqueuedBlocks[b->getBlockID()] = false; 246610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return b; 247610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 248610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 249610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 2509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith// Classification of DeclRefExprs as use or initialization. 251610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 252610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 253610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 254610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass FindVarResult { 255610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd; 256610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *dr; 257610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 2589532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {} 2599532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 260610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *getDeclRefExpr() const { return dr; } 261610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *getDecl() const { return vd; } 262610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 2639532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 2649532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 2659532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith while (Ex) { 2669532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ex = Ex->IgnoreParenNoopCasts(C); 2679532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 2689532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CE->getCastKind() == CK_LValueBitCast) { 2699532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ex = CE->getSubExpr(); 2709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith continue; 2719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2739532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 2749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 2759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Ex; 2769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 2779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 2789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// If E is an expression comprising a reference to a single variable, find that 2799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// variable. 2809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic FindVarResult findVar(const Expr *E, const DeclContext *DC) { 2819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = 2829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith dyn_cast<DeclRefExpr>(stripCasts(DC->getParentASTContext(), E))) 2839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) 2849532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (isTrackedVar(VD, DC)) 2859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return FindVarResult(VD, DRE); 2869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return FindVarResult(0, 0); 2879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 2889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 2899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// \brief Classify each DeclRefExpr as an initialization or a use. Any 2909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// DeclRefExpr which isn't explicitly classified will be assumed to have 2919532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith/// escaped the analysis and will be treated as an initialization. 2929532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithclass ClassifyRefs : public StmtVisitor<ClassifyRefs> { 2939532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithpublic: 2949532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith enum Class { 2959532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Init, 2969532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Use, 2979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith SelfInit, 2989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Ignore 2999532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith }; 3009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithprivate: 3029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const DeclContext *DC; 3039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith llvm::DenseMap<const DeclRefExpr*, Class> Classification; 3049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith bool isTrackedVar(const VarDecl *VD) const { 3069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return ::isTrackedVar(VD, DC); 3079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3099532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void classify(const Expr *E, Class C); 3109532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3119532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithpublic: 3129532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith ClassifyRefs(AnalysisDeclContext &AC) : DC(cast<DeclContext>(AC.getDecl())) {} 3139532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3149532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitDeclStmt(DeclStmt *DS); 3159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitUnaryOperator(UnaryOperator *UO); 3169532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitBinaryOperator(BinaryOperator *BO); 3179532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitCallExpr(CallExpr *CE); 3189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void VisitCastExpr(CastExpr *CE); 3199532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3209532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith void operator()(Stmt *S) { Visit(S); } 3219532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Class get(const DeclRefExpr *DRE) const { 3239532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith llvm::DenseMap<const DeclRefExpr*, Class>::const_iterator I 3249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith = Classification.find(DRE); 3259532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (I != Classification.end()) 3269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return I->second; 3279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3289532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); 3299532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (!VD || !isTrackedVar(VD)) 3309532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Ignore; 3319532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3329532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return Init; 3339532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3349532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith}; 3359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3379532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithstatic const DeclRefExpr *getSelfInitExpr(VarDecl *VD) { 3389532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (Expr *Init = VD->getInit()) { 3399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const DeclRefExpr *DRE 3409532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith = dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init)); 3419532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (DRE && DRE->getDecl() == VD) 3429532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return DRE; 3439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return 0; 3459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3469532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::classify(const Expr *E, Class C) { 3489532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(E, DC); 3499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = Var.getDeclRefExpr()) 3509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = std::max(Classification[DRE], C); 3519532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3529532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3539532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitDeclStmt(DeclStmt *DS) { 3549532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); 3559532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith DI != DE; ++DI) { 3569532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith VarDecl *VD = dyn_cast<VarDecl>(*DI); 3579532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) 3589532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const DeclRefExpr *DRE = getSelfInitExpr(VD)) 3599532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith Classification[DRE] = SelfInit; 3609532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 3619532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3629532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3639532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) { 3649532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this 3659532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // is not a compound-assignment, we will treat it as initializing the variable 3669532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // when TransferFunctions visits it. A compound-assignment does not affect 3679532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // whether a variable is uninitialized, and there's no point counting it as a 3689532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use. 3696cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith if (BO->isCompoundAssignmentOp()) 3706cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith classify(BO->getLHS(), Use); 3716cfa78f6bd4e7d5e23366a0907f8f8792366bc4cRichard Smith else if (BO->getOpcode() == BO_Assign) 3729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(BO->getLHS(), Ignore); 3739532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) { 3769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Increment and decrement are uses despite there being no lvalue-to-rvalue 3779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // conversion. 3789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (UO->isIncrementDecrementOp()) 3799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(UO->getSubExpr(), Use); 3809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCallExpr(CallExpr *CE) { 3839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // If a value is passed by const reference to a function, we should not assume 3849532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // that it is initialized by the call, and we conservatively do not assume 3859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // that it is used. 3869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); 3879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith I != E; ++I) 3889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if ((*I)->getType().isConstQualified() && (*I)->isGLValue()) 3899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(*I, Ignore); 3909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 3919532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 3929532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid ClassifyRefs::VisitCastExpr(CastExpr *CE) { 3939532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CE->getCastKind() == CK_LValueToRValue) 3949532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CE->getSubExpr(), Use); 3959532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith else if (CStyleCastExpr *CSE = dyn_cast<CStyleCastExpr>(CE)) { 3969532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (CSE->getType()->isVoidType()) { 3979532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Squelch any detected load of an uninitialized value if 3989532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // we cast it to void. 3999532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // e.g. (void) x; 4009532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classify(CSE->getSubExpr(), Ignore); 4019532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4029532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4039532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith} 4049532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4059532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//------------------------------------------------------------------------====// 4069532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith// Transfer function for uninitialized values analysis. 4079532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith//====------------------------------------------------------------------------// 4089532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4099532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithnamespace { 4100c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 411610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues &vals; 412610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 4132815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block; 4141d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext ∾ 4159532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification; 41625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek ObjCNoReturn objCNoRet; 417610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek UninitVariablesHandler *handler; 4189532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 419610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 420610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 4212815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *block, AnalysisDeclContext &ac, 4229532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 4236f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek UninitVariablesHandler *handler) 4249532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith : vals(vals), cfg(cfg), block(block), ac(ac), 42525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek classification(classification), objCNoRet(ac.getASTContext()), 42625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek handler(handler) {} 4279532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 428818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith void reportUse(const Expr *ex, const VarDecl *vd); 429a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 43025c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitBinaryOperator(BinaryOperator *bo); 431a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek void VisitBlockExpr(BlockExpr *be); 432a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith void VisitCallExpr(CallExpr *ce); 433c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek void VisitDeclRefExpr(DeclRefExpr *dr); 43425c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitDeclStmt(DeclStmt *ds); 43525c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS); 43625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek void VisitObjCMessageExpr(ObjCMessageExpr *ME); 4372815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 43840900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek bool isTrackedVar(const VarDecl *vd) { 43940900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 44040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek } 4412815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4429532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult findVar(const Expr *ex) { 4439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith return ::findVar(ex, cast<DeclContext>(ac.getDecl())); 4449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } 4459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 4462815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) { 4472815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse Use(ex, isAlwaysUninit(v)); 4482815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4492815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith assert(isUninitialized(v)); 4502815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Use.getKind() == UninitUse::Always) 4512815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 4522815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 4532815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // If an edge which leads unconditionally to this use did not initialize 4542815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable, we can say something stronger than 'may be uninitialized': 4552815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // we can say 'either it's used uninitialized or you have dead code'. 4562815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4572815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // We track the number of successors of a node which have been visited, and 4582815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // visit a node once we have visited all of its successors. Only edges where 4592815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // the variable might still be uninitialized are followed. Since a variable 4602815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // can't transfer from being initialized to being uninitialized, this will 4612815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // trace out the subgraph which inevitably leads to the use and does not 4622815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // initialize the variable. We do not want to skip past loops, since their 4632815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // non-termination might be correlated with the initialization condition. 4642815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4652815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // For example: 4662815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4672815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // void f(bool a, bool b) { 4682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block1: int n; 4692815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // if (a) { 4702815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block2: if (b) 4712815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block3: n = 1; 4722815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block4: } else if (b) { 4732815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block5: while (!a) { 4742815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block6: do_work(&a); 4752815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // n = 2; 4762815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 4772815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 4782815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block7: if (a) 4792815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block8: g(); 4802815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // block9: return n; 4812815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // } 4822815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4832815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Starting from the maybe-uninitialized use in block 9: 4842815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is not visited because we have only visited one of its two 4852815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // successors. 4862815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 8 is visited because we've visited its only successor. 4872815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 8: 4882815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 7 is visited because we've now visited both of its successors. 4892815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // From block 7: 4902815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all 4912815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively). 4922815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // * Block 3 is not visited because it initializes 'n'. 4932815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Now the algorithm terminates, having visited blocks 7 and 8, and having 4942815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // found the frontier is blocks 2, 4, and 5. 4952815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 4962815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2 4972815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // and 4), so we report that any time either of those edges is taken (in 4982815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // each case when 'b == false'), 'n' is used uninitialized. 4992815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith llvm::SmallVector<const CFGBlock*, 32> Queue; 5002815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith llvm::SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0); 5012815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(block); 5022815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Specify that we've already visited all successors of the starting block. 5032815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This has the dual purpose of ensuring we never add it to the queue, and 5042815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // of marking it as not being a candidate element of the frontier. 5052815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith SuccsVisited[block->getBlockID()] = block->succ_size(); 5062815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith while (!Queue.empty()) { 5072815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *B = Queue.back(); 5082815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.pop_back(); 5092815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); 5102815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith I != E; ++I) { 5112815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Pred = *I; 5122815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (vals.getValue(Pred, B, vd) == Initialized) 5132815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block initializes the variable. 5142815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 5152815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 516558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith unsigned &SV = SuccsVisited[Pred->getBlockID()]; 517558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!SV) { 518558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // When visiting the first successor of a block, mark all NULL 519558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith // successors as having been visited. 520558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(), 521558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SE = Pred->succ_end(); 522558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith SI != SE; ++SI) 523558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (!*SI) 524558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith ++SV; 525558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith } 526558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith 527558e8872b364b43ab9f201dd6b2df9a5b74b0542Richard Smith if (++SV == Pred->succ_size()) 5282815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // All paths from this block lead to the use and don't initialize the 5292815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // variable. 5302815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Queue.push_back(Pred); 5312815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5322815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5332815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5342815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Scan the frontier, looking for blocks where the variable was 5352815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // uninitialized. 5362815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 5372815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Block = *BI; 5382815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith unsigned BlockID = Block->getBlockID(); 5392815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Term = Block->getTerminator(); 5402815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() && 5412815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Term) { 5422815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // This block inevitably leads to the use. If we have an edge from here 5432815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // to a post-dominator block, and the variable is uninitialized on that 5442815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // edge, we have found a bug. 5452815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith for (CFGBlock::const_succ_iterator I = Block->succ_begin(), 5462815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith E = Block->succ_end(); I != E; ++I) { 5472815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const CFGBlock *Succ = *I; 5482815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() && 5492815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith vals.getValue(Block, Succ, vd) == Uninitialized) { 5502815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Switch cases are a special case: report the label to the caller 5512815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // as the 'terminator', not the switch statement itself. Suppress 5522815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // situations where no label matched: we can't be sure that's 5532815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // possible. 5542815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (isa<SwitchStmt>(Term)) { 5552815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith const Stmt *Label = Succ->getLabel(); 5562815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith if (!Label || !isa<SwitchCase>(Label)) 5572815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith // Might not be possible. 5582815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith continue; 5592815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 5602815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Label; 5612815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = 0; // Ignored. 5622815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 5632815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } else { 5642815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith UninitUse::Branch Branch; 5652815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Terminator = Term; 5662815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Branch.Output = I - Block->succ_begin(); 5672815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith Use.addUninitBranch(Branch); 5682815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5692815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5702815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5712815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5722815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 5732815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith 5742815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith return Use; 5752815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith } 576610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 577610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 578610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 579818918855d84e3db1af5a0807070d4995ca2cf75Richard Smithvoid TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) { 580818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith if (!handler) 581818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith return; 582818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith Value v = vals[vd]; 583818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith if (isUninitialized(v)) 5842815e1a075c74143a0b60a632090ece1dffa5c7cRichard Smith handler->handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v)); 585610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 586610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 5879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) { 5881ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // This represents an initialization of the 'element' value. 5899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (DeclStmt *DS = dyn_cast<DeclStmt>(FS->getElement())) { 5909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 5919532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (isTrackedVar(VD)) 5929532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 5931ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 5941ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 5951ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 596a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 597bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek const BlockDecl *bd = be->getBlockDecl(); 598bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek for (BlockDecl::capture_const_iterator i = bd->capture_begin(), 599bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek e = bd->capture_end() ; i != e; ++i) { 600bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek const VarDecl *vd = i->getVariable(); 601bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek if (!isTrackedVar(vd)) 602bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 603bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek if (i->isByRef()) { 604bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek vals[vd] = Initialized; 605bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 606bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek } 607818918855d84e3db1af5a0807070d4995ca2cf75Richard Smith reportUse(be, vd); 608a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek } 609a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek} 610a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 611a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smithvoid TransferFunctions::VisitCallExpr(CallExpr *ce) { 61244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Decl *Callee = ce->getCalleeDecl()) { 61344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek if (Callee->hasAttr<ReturnsTwiceAttr>()) { 61444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // After a call to a function like setjmp or vfork, any variable which is 61544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // initialized anywhere within this function may now be initialized. For 61644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // now, just assume such a call initializes all variables. FIXME: Only 61744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // mark variables as initialized if they have an initializer which is 61844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // reachable from here. 61944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Initialized); 62044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 62144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek else if (Callee->hasAttr<AnalyzerNoReturnAttr>()) { 62244ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // Functions labeled like "analyzer_noreturn" are often used to denote 62344ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // "panic" functions that in special debug situations can still return, 62444ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // but for the most part should not be treated as returning. This is a 62544ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // useful annotation borrowed from the static analyzer that is useful for 62644ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // suppressing branch-specific false positives when we call one of these 62744ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // functions but keep pretending the path continues (when in reality the 62844ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek // user doesn't care). 62944ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek vals.setAllScratchValues(Unknown); 63044ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 63144ca53f34deb5efe9fc6f246781f66f1ed83eabcTed Kremenek } 632a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith} 633a9e8b9e3e90fcfe10a04624a89c39b63c32614d1Richard Smith 6340c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 6359532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith switch (classification.get(dr)) { 6369532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Ignore: 6379532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 6389532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Use: 6399532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith reportUse(dr, cast<VarDecl>(dr->getDecl())); 6409532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 6419532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::Init: 6429532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[cast<VarDecl>(dr->getDecl())] = Initialized; 6439532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 6449532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith case ClassifyRefs::SelfInit: 6459532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (handler) 6469532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith handler->handleSelfInit(cast<VarDecl>(dr->getDecl())); 6479532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith break; 648610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 649610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 650610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6519532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) { 6529532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (BO->getOpcode() == BO_Assign) { 6539532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith FindVarResult Var = findVar(BO->getLHS()); 6549532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (const VarDecl *VD = Var.getDecl()) 6559532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 656610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 657610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 658610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6599532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smithvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 6609532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end(); 6619532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith DI != DE; ++DI) { 6629532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith VarDecl *VD = dyn_cast<VarDecl>(*DI); 6639532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (VD && isTrackedVar(VD)) { 6649532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith if (getSelfInitExpr(VD)) { 6659532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // If the initializer consists solely of a reference to itself, we 6669532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // explicitly mark the variable as uninitialized. This allows code 6679532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // like the following: 6689532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 6699532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int x = x; 6709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // 6719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // to deliberately leave a variable uninitialized. Different analysis 6729532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // clients can detect this pattern and adjust their reporting 6739532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // appropriately, but we need to continue to analyze subsequent uses 6749532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // of the variable. 6759532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 6769532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else if (VD->getInit()) { 6779532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Treat the new variable as initialized. 6789532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Initialized; 6799532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith } else { 6809532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // No initializer: the variable is now uninitialized. This matters 6819532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // for cases like: 6829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // while (...) { 6839532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // int n; 6849532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // use(n); 6859532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // n = 0; 6869532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // } 6879532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // FIXME: Mark the variable as uninitialized whenever its scope is 6889532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // left, since its scope could be re-entered by a jump over the 6899532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // declaration. 6909532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith vals[VD] = Uninitialized; 6910c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek } 692dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 693dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 694610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 695610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 69625c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenekvoid TransferFunctions::VisitObjCMessageExpr(ObjCMessageExpr *ME) { 69725c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // If the Objective-C message expression is an implicit no-return that 69825c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek // is not modeled in the CFG, set the tracked dataflow values to Unknown. 69925c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek if (objCNoRet.isImplicitNoReturn(ME)) { 70025c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek vals.setAllScratchValues(Unknown); 70125c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek } 70225c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek} 70325c1d57fc906e895535fb5c7e6dde80219f353b5Ted Kremenek 704610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 705610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// High-level "driver" logic for uninitialized values analysis. 706610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 707610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 70813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenekstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 7091d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, CFGBlockValues &vals, 7109532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith const ClassifyRefs &classification, 711f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector &wasAnalyzed, 7126f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek UninitVariablesHandler *handler = 0) { 713f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek wasAnalyzed[block->getBlockID()] = true; 714610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.resetScratch(); 715eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek // Merge in values of predecessor blocks. 716610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool isFirst = true; 717610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 718610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->pred_end(); I != E; ++I) { 7196f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *pred = *I; 7206f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (wasAnalyzed[pred->getBlockID()]) { 721eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vals.mergeIntoScratch(vals.getValueVector(pred), isFirst); 7226f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek isFirst = false; 7236f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek } 724610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 725610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Apply the transfer function. 7269532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith TransferFunctions tf(vals, cfg, block, ac, classification, handler); 727610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 728610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek I != E; ++I) { 729610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { 730f1d10d939739f1a4544926d807e4f0f9fb64be61Ted Kremenek tf.Visit(const_cast<Stmt*>(cs->getStmt())); 731610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 732610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 733136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectorWithScratch(block); 734610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 735610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 7365d98994c7749312a43ce6adf45537979a98e7afdChandler Carruthvoid clang::runUninitializedVariablesAnalysis( 7375d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const DeclContext &dc, 7385d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const CFG &cfg, 7391d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, 7405d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesHandler &handler, 7415d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesAnalysisStats &stats) { 742610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues vals(cfg); 743610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.computeSetOfDeclarations(dc); 744610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (vals.hasNoDeclarations()) 745610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 746d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 7475d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth stats.NumVariablesAnalyzed = vals.getNumEntries(); 7485d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth 7499532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith // Precompute which expressions are uses and which are initializations. 7509532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith ClassifyRefs classification(ac); 7519532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith cfg.VisitBlockStmts(classification); 7529532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith 753d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Mark all variables uninitialized at the entry. 754d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek const CFGBlock &entry = cfg.getEntry(); 755eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek ValueVector &vec = vals.getValueVector(&entry); 756eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek const unsigned n = vals.getNumEntries(); 757eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek for (unsigned j = 0; j < n ; ++j) { 758eee18c38b6dd29c0e6982f5565fcbc3f76d1bf4dTed Kremenek vec[j] = Uninitialized; 759d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek } 760d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 761d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Proceed with the workist. 762610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DataflowWorklist worklist(cfg); 763496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 764610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(&cfg.getEntry()); 765f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 7666f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek wasAnalyzed[cfg.getEntry().getBlockID()] = true; 767610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 768610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 769610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Did the block change? 7709532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith bool changed = runOnBlock(block, cfg, ac, vals, 7719532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith classification, wasAnalyzed); 7725d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 773610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed || !previouslyVisited[block->getBlockID()]) 774610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(block); 775610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek previouslyVisited[block->getBlockID()] = true; 776610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 777610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 778610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Run through the blocks one more time, and report uninitialized variabes. 779610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 7806f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *block = *BI; 7816f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (wasAnalyzed[block->getBlockID()]) { 7829532e0d89ca2afa556f032aa9377f6ec1d3eaa3eRichard Smith runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, &handler); 7835d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 7845d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth } 785610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 786610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 787610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 788610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekUninitVariablesHandler::~UninitVariablesHandler() {} 789