UninitializedValues.cpp revision b2c60b04a597cc5ba4154837cf8e0a155a376fd7
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" 19610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "clang/AST/Decl.h" 20610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "clang/Analysis/CFG.h" 21a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek#include "clang/Analysis/AnalysisContext.h" 22610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 236f34213f8d6ae8c77685b53664527e39bfaaca3bTed Kremenek#include "clang/Analysis/Analyses/UninitializedValues.h" 24b2c60b04a597cc5ba4154837cf8e0a155a376fd7Argyrios Kyrtzidis#include "llvm/Support/SaveAndRestore.h" 25610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 26610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekusing namespace clang; 27610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 2840900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenekstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 291cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 30a21612f95792c1ea8b4362f0861f0c724c39388eTed Kremenek !vd->isExceptionVariable() && 311cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek vd->getDeclContext() == dc) { 321cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek QualType ty = vd->getType(); 331cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek return ty->isScalarType() || ty->isVectorType(); 341cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek } 351cbc31515e9b979f55178ffd4587e8671f7ebbfaTed Kremenek return false; 36c104e53639de4424b83955acfadc977773b5883dTed Kremenek} 37c104e53639de4424b83955acfadc977773b5883dTed Kremenek 38610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 39136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek// DeclToIndex: a mapping from Decls we track to value indices. 40610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 41610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 42610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 43136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekclass DeclToIndex { 44610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek llvm::DenseMap<const VarDecl *, unsigned> map; 45610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 46136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek DeclToIndex() {} 47610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 48610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Compute the actual mapping from declarations to bits. 49610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeMap(const DeclContext &dc); 50610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 51610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Return the number of declarations in the map. 52610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned size() const { return map.size(); } 53610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 54610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Returns the bit vector index for a given declaration. 55b831c673621c5587642343cace9def134916a17bTed Kremenek llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const; 56610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 57610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 58610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 59136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekvoid DeclToIndex::computeMap(const DeclContext &dc) { 60610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned count = 0; 61610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 62610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E(dc.decls_end()); 63610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for ( ; I != E; ++I) { 64610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd = *I; 6540900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek if (isTrackedVar(vd, &dc)) 66610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek map[vd] = count++; 67610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 68610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 69610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 70b831c673621c5587642343cace9def134916a17bTed Kremenekllvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { 71b831c673621c5587642343cace9def134916a17bTed Kremenek llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); 72610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (I == map.end()) 73610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return llvm::Optional<unsigned>(); 74610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return I->second; 75610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 76610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 77610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 78610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// CFGBlockValues: dataflow values for CFG blocks. 79610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 80610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 81f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// These values are defined in such a way that a merge can be done using 82f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek// a bitwise OR. 83f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekenum Value { Unknown = 0x0, /* 00 */ 84f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Initialized = 0x1, /* 01 */ 85f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Uninitialized = 0x2, /* 10 */ 86f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek MayUninitialized = 0x3 /* 11 */ }; 87f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek 88f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isUninitialized(const Value v) { 89f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v >= Uninitialized; 90f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 91f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenekstatic bool isAlwaysUninit(const Value v) { 92f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek return v == Uninitialized; 93f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek} 94afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 95da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramernamespace { 96afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 97049f6d0239e242dc338be6ac6f6c5175803d2163Argyrios Kyrtzidistypedef llvm::PackedVector<Value, 2> ValueVector; 98136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenektypedef std::pair<ValueVector *, ValueVector *> BVPair; 9913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 100610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass CFGBlockValues { 101610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 10213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek BVPair *vals; 103136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector scratch; 1044ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek DeclToIndex declToIndex; 10513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 106136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &lazyCreate(ValueVector *&bv); 107610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 108610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues(const CFG &cfg); 109610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek ~CFGBlockValues(); 110610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 111d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek unsigned getNumEntries() const { return declToIndex.size(); } 112d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 113610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeSetOfDeclarations(const DeclContext &dc); 114136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &getValueVector(const CFGBlock *block, 11513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek const CFGBlock *dstBlock); 11613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 117136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate); 11813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 119136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek void mergeIntoScratch(ValueVector const &source, bool isFirst); 120136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool updateValueVectorWithScratch(const CFGBlock *block); 121136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool updateValueVectors(const CFGBlock *block, const BVPair &newVals); 122610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 123610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool hasNoDeclarations() const { 1244ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek return declToIndex.size() == 0; 125610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 126e0e29332c89da22b6890929b97e6f568c917d85fTed Kremenek 127610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void resetScratch(); 128136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &getScratch() { return scratch; } 12913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 130136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector::reference operator[](const VarDecl *vd); 131610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 132da57f3eeab7b7f7f6e6788956f0a0d9adf196a7dBenjamin Kramer} // end anonymous namespace 133610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 134610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { 135610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned n = cfg.getNumBlockIDs(); 136610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (!n) 137610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 138136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek vals = new std::pair<ValueVector*, ValueVector*>[n]; 13975c4064932d481ac710a80aa88b3370ad8a6af1dChandler Carruth memset((void*)vals, 0, sizeof(*vals) * n); 140610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 141610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 142610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekCFGBlockValues::~CFGBlockValues() { 143610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned n = cfg.getNumBlockIDs(); 144610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (n == 0) 145610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 14613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek for (unsigned i = 0; i < n; ++i) { 14713bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek delete vals[i].first; 14813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek delete vals[i].second; 14913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek } 150610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek delete [] vals; 151610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 152610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 153610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 1544ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek declToIndex.computeMap(dc); 1554ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek scratch.resize(declToIndex.size()); 156610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 157610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 158136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) { 15913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek if (!bv) 1604ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek bv = new ValueVector(declToIndex.size()); 161610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return *bv; 162610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 163610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 16413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek/// This function pattern matches for a '&&' or '||' that appears at 16513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek/// the beginning of a CFGBlock that also (1) has a terminator and 16613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek/// (2) has no other elements. If such an expression is found, it is returned. 167f1d10d939739f1a4544926d807e4f0f9fb64be61Ted Kremenekstatic const BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) { 16813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek if (block->empty()) 16913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return 0; 1709fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 1713c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek const CFGStmt *cstmt = block->front().getAs<CFGStmt>(); 17276709bf816e5e1b70b859bb607cf3ee91db12b76Ted Kremenek if (!cstmt) 17376709bf816e5e1b70b859bb607cf3ee91db12b76Ted Kremenek return 0; 17476709bf816e5e1b70b859bb607cf3ee91db12b76Ted Kremenek 175f1d10d939739f1a4544926d807e4f0f9fb64be61Ted Kremenek const BinaryOperator *b = dyn_cast_or_null<BinaryOperator>(cstmt->getStmt()); 1769fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 1779fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (!b || !b->isLogicalOp()) 17813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return 0; 1799fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 180e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek if (block->pred_size() == 2) { 181e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek if (block->getTerminatorCondition() == b) { 182e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek if (block->succ_size() == 2) 183e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek return b; 184e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek } 185e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek else if (block->size() == 1) 186e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek return b; 187e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek } 188e6c28039c63d829577a2e37170e06a1dbdf89748Ted Kremenek 1899fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek return 0; 19013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 19113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 192136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector &CFGBlockValues::getValueVector(const CFGBlock *block, 193136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek const CFGBlock *dstBlock) { 19413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek unsigned idx = block->getBlockID(); 1959fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (dstBlock && getLogicalOperatorInChain(block)) { 1969fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (*block->succ_begin() == dstBlock) 1979fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek return lazyCreate(vals[idx].first); 1989fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek assert(*(block->succ_begin()+1) == dstBlock); 1999fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek return lazyCreate(vals[idx].second); 20013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek } 20113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 20213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek assert(vals[idx].second == 0); 20313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return lazyCreate(vals[idx].first); 20413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 20513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 206136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekBVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block, 207136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool shouldLazyCreate) { 20813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek unsigned idx = block->getBlockID(); 20913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek lazyCreate(vals[idx].first); 2109fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (shouldLazyCreate) 2119fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek lazyCreate(vals[idx].second); 21213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return vals[idx]; 21313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 21413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 2159fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#if 0 216136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekstatic void printVector(const CFGBlock *block, ValueVector &bv, 2179fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek unsigned num) { 2189fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 2199fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << block->getBlockID() << " :"; 2209fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek for (unsigned i = 0; i < bv.size(); ++i) { 2219fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << ' ' << bv[i]; 2229fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek } 2239fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << " : " << num << '\n'; 2249fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek} 225c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 226c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenekstatic void printVector(const char *name, ValueVector const &bv) { 227c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek llvm::errs() << name << " : "; 228c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek for (unsigned i = 0; i < bv.size(); ++i) { 229c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek llvm::errs() << ' ' << bv[i]; 230c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek } 231c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek llvm::errs() << "\n"; 232c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek} 2339fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 234610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 235c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenekvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 236c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek bool isFirst) { 237c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek if (isFirst) 238c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch = source; 239c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek else 240c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek scratch |= source; 241c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek} 242c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 243136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 244136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &dst = getValueVector(block, 0); 245610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool changed = (dst != scratch); 246610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed) 247610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek dst = scratch; 2489fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#if 0 2499fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, scratch, 0); 2509fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 25113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return changed; 25213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 25313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 254136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekbool CFGBlockValues::updateValueVectors(const CFGBlock *block, 25513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek const BVPair &newVals) { 256136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair &vals = getValueVectors(block, true); 25713bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek bool changed = *newVals.first != *vals.first || 25813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek *newVals.second != *vals.second; 25913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek *vals.first = *newVals.first; 26013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek *vals.second = *newVals.second; 2619fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#if 0 2629fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, *vals.first, 1); 2639fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, *vals.second, 2); 2649fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 265610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return changed; 266610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 267610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 268610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::resetScratch() { 269610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek scratch.reset(); 270610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 271610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 272136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 2734ddb3871307376d27d0f276c9da0ecce0384f01fTed Kremenek const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); 274610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek assert(idx.hasValue()); 275610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return scratch[idx.getValue()]; 276610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 277610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 278610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 279610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// Worklist: worklist for dataflow analysis. 280610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 281610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 282610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 283610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass DataflowWorklist { 2845f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<const CFGBlock *, 20> worklist; 285496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector enqueuedBlocks; 286610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 287610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} 288610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 289610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void enqueueSuccessors(const CFGBlock *block); 290610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *dequeue(); 291610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 292610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 293610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 294610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 2958052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth unsigned OldWorklistSize = worklist.size(); 296610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_succ_iterator I = block->succ_begin(), 297610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->succ_end(); I != E; ++I) { 2988052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth const CFGBlock *Successor = *I; 2998052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth if (!Successor || enqueuedBlocks[Successor->getBlockID()]) 3008052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth continue; 3018052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth worklist.push_back(Successor); 3028052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth enqueuedBlocks[Successor->getBlockID()] = true; 303610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 3048052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 3058052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth return; 3068052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth 3078052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth // Rotate the newly added blocks to the start of the worklist so that it forms 3088052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth // a proper queue when we pop off the end of the worklist. 3098052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize, 3108052050c8ebfcfbbce8afed57fefc8c95fb9a333Chandler Carruth worklist.end()); 311610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 312610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 313610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekconst CFGBlock *DataflowWorklist::dequeue() { 314610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (worklist.empty()) 315610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return 0; 316610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *b = worklist.back(); 317610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.pop_back(); 318610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek enqueuedBlocks[b->getBlockID()] = false; 319610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return b; 320610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 321610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 322610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 323610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// Transfer function for uninitialized values analysis. 324610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 325610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 326610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 327610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass FindVarResult { 328610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd; 329610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *dr; 330610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 331610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {} 332610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 333610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *getDeclRefExpr() const { return dr; } 334610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *getDecl() const { return vd; } 335610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 336610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 3370c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 338610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues &vals; 339610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 3401d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext ∾ 341610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek UninitVariablesHandler *handler; 3420c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek 3430c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek /// The last DeclRefExpr seen when analyzing a block. Used to 3440c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek /// cheat when detecting cases when the address of a variable is taken. 3450c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek DeclRefExpr *lastDR; 3460c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek 3470c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek /// The last lvalue-to-rvalue conversion of a variable whose value 3480c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek /// was uninitialized. Normally this results in a warning, but it is 3490c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek /// possible to either silence the warning in some cases, or we 3500c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek /// propagate the uninitialized value. 3510c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek CastExpr *lastLoad; 35257fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek 35357fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek /// For some expressions, we want to ignore any post-processing after 35457fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek /// visitation. 35557fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek bool skipProcessUses; 35657fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek 357610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 358610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 3591d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, 3606f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek UninitVariablesHandler *handler) 3610c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek : vals(vals), cfg(cfg), ac(ac), handler(handler), 3626f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek lastDR(0), lastLoad(0), 36357fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek skipProcessUses(false) {} 364610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 365f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek void reportUninit(const DeclRefExpr *ex, const VarDecl *vd, 366f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek bool isAlwaysUninit); 367a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 368a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek void VisitBlockExpr(BlockExpr *be); 369610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitDeclStmt(DeclStmt *ds); 370c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek void VisitDeclRefExpr(DeclRefExpr *dr); 371610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitUnaryOperator(UnaryOperator *uo); 372610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitBinaryOperator(BinaryOperator *bo); 373610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitCastExpr(CastExpr *ce); 3740c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); 3750c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek void Visit(Stmt *s); 37640900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek 37740900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek bool isTrackedVar(const VarDecl *vd) { 37840900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 37940900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek } 38040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek 38140900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek FindVarResult findBlockVarDecl(Expr *ex); 3820c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek 3830c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek void ProcessUses(Stmt *s = 0); 384610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 385610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 386610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 387de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenekstatic const Expr *stripCasts(ASTContext &C, const Expr *Ex) { 388de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek while (Ex) { 389de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek Ex = Ex->IgnoreParenNoopCasts(C); 390de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) { 391de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek if (CE->getCastKind() == CK_LValueBitCast) { 392de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek Ex = CE->getSubExpr(); 393de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek continue; 394de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek } 395de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek } 396de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek break; 397de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek } 398de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek return Ex; 399de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek} 400de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek 401610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::reportUninit(const DeclRefExpr *ex, 402f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek const VarDecl *vd, bool isAlwaysUnit) { 403f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek if (handler) handler->handleUseOfUninitVariable(ex, vd, isAlwaysUnit); 404610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 405610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 4069c378f705405d37f49795d5e915989de774fe11fTed KremenekFindVarResult TransferFunctions::findBlockVarDecl(Expr *ex) { 4079c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (DeclRefExpr *dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts())) 4081ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 4091ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (isTrackedVar(vd)) 41040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return FindVarResult(vd, dr); 4111ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek return FindVarResult(0, 0); 4121ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 4131ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 4140c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs) { 4151ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // This represents an initialization of the 'element' value. 4161ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek Stmt *element = fs->getElement(); 4179c378f705405d37f49795d5e915989de774fe11fTed Kremenek const VarDecl *vd = 0; 4181ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 4199c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (DeclStmt *ds = dyn_cast<DeclStmt>(element)) { 4201ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vd = cast<VarDecl>(ds->getSingleDecl()); 4211ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (!isTrackedVar(vd)) 4221ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vd = 0; 4233060178ad9df29789505c1e6debcfc80a3a13587Chad Rosier } else { 4241ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // Initialize the value of the reference variable. 4251ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); 4261ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vd = res.getDecl(); 4271ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 4281ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 4291ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (vd) 4301ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vals[vd] = Initialized; 4311ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 4321ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 433a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 434bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek const BlockDecl *bd = be->getBlockDecl(); 435bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek for (BlockDecl::capture_const_iterator i = bd->capture_begin(), 436bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek e = bd->capture_end() ; i != e; ++i) { 437bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek const VarDecl *vd = i->getVariable(); 438bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek if (!isTrackedVar(vd)) 439bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 440bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek if (i->isByRef()) { 441bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek vals[vd] = Initialized; 442bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek continue; 443bc8b44c4ee7f9c4c3ad296369e72feda61bdb580Ted Kremenek } 444f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek Value v = vals[vd]; 4456f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (handler && isUninitialized(v)) 446f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek handler->handleUseOfUninitVariable(be, vd, isAlwaysUninit(v)); 447a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek } 448a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek} 449a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 4500c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 4510c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // Record the last DeclRefExpr seen. This is an lvalue computation. 4520c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // We use this value to later detect if a variable "escapes" the analysis. 4530c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 454dd4286b5b7b02b8bb962e4b996b8f36cb7935d4fTed Kremenek if (isTrackedVar(vd)) { 455dd4286b5b7b02b8bb962e4b996b8f36cb7935d4fTed Kremenek ProcessUses(); 4560c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastDR = dr; 457dd4286b5b7b02b8bb962e4b996b8f36cb7935d4fTed Kremenek } 4580c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek} 4590c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek 460610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitDeclStmt(DeclStmt *ds) { 461610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end(); 462610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DI != DE; ++DI) { 463610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) { 4644dccb90e92ba9e4abffe0177493b6db9949678ddTed Kremenek if (isTrackedVar(vd)) { 465b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth if (Expr *init = vd->getInit()) { 466b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // If the initializer consists solely of a reference to itself, we 467b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // explicitly mark the variable as uninitialized. This allows code 468b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // like the following: 469b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // 470b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // int x = x; 471b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // 472b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // to deliberately leave a variable uninitialized. Different analysis 473b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // clients can detect this pattern and adjust their reporting 474b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // appropriately, but we need to continue to analyze subsequent uses 475b88fb027bfe2f85da3a341f42549900bd658ac8bChandler Carruth // of the variable. 4760c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek if (init == lastLoad) { 477de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek const DeclRefExpr *DR 478de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek = cast<DeclRefExpr>(stripCasts(ac.getASTContext(), 479de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek lastLoad->getSubExpr())); 48062d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek if (DR->getDecl() == vd) { 48162d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek // int x = x; 48262d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek // Propagate uninitialized value, but don't immediately report 48362d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek // a problem. 48462d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek vals[vd] = Uninitialized; 48562d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek lastLoad = 0; 4860c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastDR = 0; 4879e7617220135a6f6226cf09cb242cc1b905aedb4Ted Kremenek if (handler) 4889e7617220135a6f6226cf09cb242cc1b905aedb4Ted Kremenek handler->handleSelfInit(vd); 48962d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek return; 49062d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek } 4910c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek } 49262d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek 49362d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek // All other cases: treat the new variable as initialized. 4949e7617220135a6f6226cf09cb242cc1b905aedb4Ted Kremenek // This is a minor optimization to reduce the propagation 4959e7617220135a6f6226cf09cb242cc1b905aedb4Ted Kremenek // of the analysis, since we will have already reported 4969e7617220135a6f6226cf09cb242cc1b905aedb4Ted Kremenek // the use of the uninitialized value (which visiting the 4979e7617220135a6f6226cf09cb242cc1b905aedb4Ted Kremenek // initializer). 49862d126e942f9f420c6f398d32deb914d413226a3Ted Kremenek vals[vd] = Initialized; 499610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 500c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek } 501610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 502610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 503610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 504610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 505610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { 506610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (bo->isAssignmentOp()) { 507610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const FindVarResult &res = findBlockVarDecl(bo->getLHS()); 5089c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (const VarDecl *vd = res.getDecl()) { 509496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek ValueVector::reference val = vals[vd]; 510f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek if (isUninitialized(val)) { 5118435069798b5621615f9f65c471c7e7808316b20Chandler Carruth if (bo->getOpcode() != BO_Assign) 512f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 513d837c0dc361a000b951593eaaa80c46b73d15b1dChandler Carruth else 514d837c0dc361a000b951593eaaa80c46b73d15b1dChandler Carruth val = Initialized; 515610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 516610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 517610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 518610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 519610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 520610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { 521610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek switch (uo->getOpcode()) { 522610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PostDec: 523610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PostInc: 524610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PreDec: 525610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PreInc: { 526610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const FindVarResult &res = findBlockVarDecl(uo->getSubExpr()); 527610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (const VarDecl *vd = res.getDecl()) { 5280c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek assert(res.getDeclRefExpr() == lastDR); 5290c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // We null out lastDR to indicate we have fully processed it 5300c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // and we don't want the auto-value setting in Visit(). 5310c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastDR = 0; 532c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek 533f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek ValueVector::reference val = vals[vd]; 534d837c0dc361a000b951593eaaa80c46b73d15b1dChandler Carruth if (isUninitialized(val)) 535f7bafc77ba12bb1beb665243a0334cd81e024728Ted Kremenek reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); 536610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 537610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek break; 538610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 539610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek default: 540610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek break; 541610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 542610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 543610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 544610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { 545610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (ce->getCastKind() == CK_LValueToRValue) { 546610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); 547c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek if (res.getDecl()) { 5480c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek assert(res.getDeclRefExpr() == lastDR); 549c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek lastLoad = ce; 550c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek } 551dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 552de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek else if (ce->getCastKind() == CK_NoOp || 553de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek ce->getCastKind() == CK_LValueBitCast) { 55457fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek skipProcessUses = true; 55557fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek } 556dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) { 557dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek if (cse->getType()->isVoidType()) { 558dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek // e.g. (void) x; 5590c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek if (lastLoad == cse->getSubExpr()) { 5600c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // Squelch any detected load of an uninitialized value if 5610c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // we cast it to void. 5620c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastLoad = 0; 5630c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastDR = 0; 5640c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek } 565dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 566dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 567610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 568610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 5690c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::Visit(clang::Stmt *s) { 57057fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek skipProcessUses = false; 5710c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek StmtVisitor<TransferFunctions>::Visit(s); 57257fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek if (!skipProcessUses) 57357fb591a54eab7db65d73e77c632f047bca22c54Ted Kremenek ProcessUses(s); 5740c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek} 5750c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek 5760c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenekvoid TransferFunctions::ProcessUses(Stmt *s) { 5770c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // This method is typically called after visiting a CFGElement statement 5780c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // in the CFG. We delay processing of reporting many loads of uninitialized 5790c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // values until here. 5800c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek if (lastLoad) { 5810c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // If we just visited the lvalue-to-rvalue cast, there is nothing 5820c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // left to do. 5830c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek if (lastLoad == s) 5849660803cd332d5c605899435019bb3b37fca3accTed Kremenek return; 5850c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek 586de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek const DeclRefExpr *DR = 587de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek cast<DeclRefExpr>(stripCasts(ac.getASTContext(), 588de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek lastLoad->getSubExpr())); 589de091aeb4658e986ed8fa5fbce7ab35ef2ae26ecTed Kremenek const VarDecl *VD = cast<VarDecl>(DR->getDecl()); 590c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 591c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek // If we reach here, we may have seen a load of an uninitialized value 592c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek // and it hasn't been casted to void or otherwise handled. In this 593c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek // situation, report the incident. 594c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek if (isUninitialized(vals[VD])) 595c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek reportUninit(DR, VD, isAlwaysUninit(vals[VD])); 596c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 5970c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastLoad = 0; 598c5f740ecdbc21d5ba08f97b89cc05c9d4f230fdaTed Kremenek 5990c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek if (DR == lastDR) { 6000c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastDR = 0; 6010c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek return; 6020c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek } 6039660803cd332d5c605899435019bb3b37fca3accTed Kremenek } 6049660803cd332d5c605899435019bb3b37fca3accTed Kremenek 6050c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // Any other uses of 'lastDR' involve taking an lvalue of variable. 6060c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek // In this case, it "escapes" the analysis. 6070c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek if (lastDR && lastDR != s) { 6080c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek vals[cast<VarDecl>(lastDR->getDecl())] = Initialized; 6090c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek lastDR = 0; 610866849498461cf9022316034516475188b25955bChandler Carruth } 611866849498461cf9022316034516475188b25955bChandler Carruth} 612866849498461cf9022316034516475188b25955bChandler Carruth 613610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 614610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// High-level "driver" logic for uninitialized values analysis. 615610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 616610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 61713bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenekstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 6181d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, CFGBlockValues &vals, 619f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector &wasAnalyzed, 6206f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek UninitVariablesHandler *handler = 0) { 62113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 622f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek wasAnalyzed[block->getBlockID()] = true; 623f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek 62413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { 6259fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek CFGBlock::const_pred_iterator itr = block->pred_begin(); 626136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair vA = vals.getValueVectors(*itr, false); 6279fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek ++itr; 628136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair vB = vals.getValueVectors(*itr, false); 6299fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 6309fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek BVPair valsAB; 6319fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 6329fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (b->getOpcode() == BO_LAnd) { 6339fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek // Merge the 'F' bits from the first and second. 6349fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true); 6359fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false); 6369fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek valsAB.first = vA.first; 6372d4bed140f65d713673d2d32ec3adadc960078c6Ted Kremenek valsAB.second = &vals.getScratch(); 6383060178ad9df29789505c1e6debcfc80a3a13587Chad Rosier } else { 6399fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek // Merge the 'T' bits from the first and second. 6409fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek assert(b->getOpcode() == BO_LOr); 6419fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*vA.first, true); 6429fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*vB.first, false); 6439fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek valsAB.first = &vals.getScratch(); 6449fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek valsAB.second = vA.second ? vA.second : vA.first; 6459fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek } 646136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectors(block, valsAB); 64713bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek } 64813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 6499fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek // Default behavior: merge in values of predecessor blocks. 650610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.resetScratch(); 651610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool isFirst = true; 652610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 653610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->pred_end(); I != E; ++I) { 6546f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *pred = *I; 6556f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (wasAnalyzed[pred->getBlockID()]) { 6566f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek vals.mergeIntoScratch(vals.getValueVector(pred, block), isFirst); 6576f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek isFirst = false; 6586f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek } 659610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 660610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Apply the transfer function. 6616f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek TransferFunctions tf(vals, cfg, ac, handler); 662610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 663610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek I != E; ++I) { 664610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { 665f1d10d939739f1a4544926d807e4f0f9fb64be61Ted Kremenek tf.Visit(const_cast<Stmt*>(cs->getStmt())); 666610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 667610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 6680c8e5a0f70cbdb800d939c1807d05f380b2854d4Ted Kremenek tf.ProcessUses(); 669136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectorWithScratch(block); 670610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 671610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 6725d98994c7749312a43ce6adf45537979a98e7afdChandler Carruthvoid clang::runUninitializedVariablesAnalysis( 6735d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const DeclContext &dc, 6745d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth const CFG &cfg, 6751d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &ac, 6765d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesHandler &handler, 6775d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth UninitVariablesAnalysisStats &stats) { 678610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues vals(cfg); 679610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.computeSetOfDeclarations(dc); 680610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (vals.hasNoDeclarations()) 681610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 682d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 6835d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth stats.NumVariablesAnalyzed = vals.getNumEntries(); 6845d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth 685d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Mark all variables uninitialized at the entry. 686d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek const CFGBlock &entry = cfg.getEntry(); 687d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek for (CFGBlock::const_succ_iterator i = entry.succ_begin(), 688d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek e = entry.succ_end(); i != e; ++i) { 689d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek if (const CFGBlock *succ = *i) { 690d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek ValueVector &vec = vals.getValueVector(&entry, succ); 691d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek const unsigned n = vals.getNumEntries(); 692d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek for (unsigned j = 0; j < n ; ++j) { 693d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek vec[j] = Uninitialized; 694d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek } 695d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek } 696d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek } 697d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek 698d40066b0fb883839a9100e5455e33190b9b8abacTed Kremenek // Proceed with the workist. 699610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DataflowWorklist worklist(cfg); 700496398d523de712ac1084c53a397ca3987fe43dbTed Kremenek llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); 701610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(&cfg.getEntry()); 702f8adeefa9e9882bff402e092024dd457f8574673Ted Kremenek llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); 7036f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek wasAnalyzed[cfg.getEntry().getBlockID()] = true; 704610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 705610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 706610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Did the block change? 7075d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth bool changed = runOnBlock(block, cfg, ac, vals, wasAnalyzed); 7085d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 709610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed || !previouslyVisited[block->getBlockID()]) 710610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(block); 711610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek previouslyVisited[block->getBlockID()] = true; 712610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 713610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 714610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Run through the blocks one more time, and report uninitialized variabes. 715610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 7166f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek const CFGBlock *block = *BI; 7176f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek if (wasAnalyzed[block->getBlockID()]) { 7186f27542da8843b5c1c579b86e342385bcc43d5f0Ted Kremenek runOnBlock(block, cfg, ac, vals, wasAnalyzed, &handler); 7195d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth ++stats.NumBlockVisits; 7205d98994c7749312a43ce6adf45537979a98e7afdChandler Carruth } 721610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 722610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 723610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 724610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekUninitVariablesHandler::~UninitVariablesHandler() {} 725