UninitializedValues.cpp revision afb10c4bda2ac2c268fa7e6c11141584f57de119
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" 17610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek#include "llvm/ADT/BitVector.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" 24c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek#include "clang/Analysis/Support/SaveAndRestore.h" 25610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 26610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekusing namespace clang; 27610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 2840900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenekstatic bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { 29c104e53639de4424b83955acfadc977773b5883dTed Kremenek return vd->isLocalVarDecl() && !vd->hasGlobalStorage() && 3040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek vd->getType()->isScalarType() && 3140900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek vd->getDeclContext() == dc; 32c104e53639de4424b83955acfadc977773b5883dTed Kremenek} 33c104e53639de4424b83955acfadc977773b5883dTed Kremenek 34610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 35136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek// DeclToIndex: a mapping from Decls we track to value indices. 36610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 37610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 38610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 39136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekclass DeclToIndex { 40610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek llvm::DenseMap<const VarDecl *, unsigned> map; 41610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 42136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek DeclToIndex() {} 43610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 44610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Compute the actual mapping from declarations to bits. 45610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeMap(const DeclContext &dc); 46610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 47610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Return the number of declarations in the map. 48610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned size() const { return map.size(); } 49610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 50610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek /// Returns the bit vector index for a given declaration. 51136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek llvm::Optional<unsigned> getValueIndex(const VarDecl *d); 52610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 53610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 54610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 55136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekvoid DeclToIndex::computeMap(const DeclContext &dc) { 56610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned count = 0; 57610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), 58610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E(dc.decls_end()); 59610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for ( ; I != E; ++I) { 60610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd = *I; 6140900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek if (isTrackedVar(vd, &dc)) 62610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek map[vd] = count++; 63610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 64610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 65610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 66136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekllvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) { 67610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek llvm::DenseMap<const VarDecl *, unsigned>::iterator I = map.find(d); 68610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (I == map.end()) 69610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return llvm::Optional<unsigned>(); 70610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return I->second; 71610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 72610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 73610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 74610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// CFGBlockValues: dataflow values for CFG blocks. 75610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 76610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 77afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenekstatic const bool Initialized = false; 78afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenekstatic const bool Uninitialized = true; 79afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 80afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenekclass ValueVector { 81afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek llvm::BitVector vec; 82afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenekpublic: 83afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek ValueVector() {} 84afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek ValueVector(unsigned size) : vec(size) {} 85afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek typedef llvm::BitVector::reference reference; 86afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek void resize(unsigned n) { vec.resize(n); } 87afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek void merge(const ValueVector &rhs) { vec |= rhs.vec; } 88afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek bool operator!=(const ValueVector &rhs) const { return vec != rhs.vec; } 89afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek reference operator[](unsigned idx) { return vec[idx]; } 90afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek void reset() { vec.reset(); } 91afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek}; 92afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek 93136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenektypedef std::pair<ValueVector *, ValueVector *> BVPair; 9413bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 95610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 96610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass CFGBlockValues { 97610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 9813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek BVPair *vals; 99136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector scratch; 100136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek DeclToIndex DeclToIndex; 10113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 102136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &lazyCreate(ValueVector *&bv); 103610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 104610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues(const CFG &cfg); 105610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek ~CFGBlockValues(); 106610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 107610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void computeSetOfDeclarations(const DeclContext &dc); 108136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &getValueVector(const CFGBlock *block, 10913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek const CFGBlock *dstBlock); 11013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 111136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate); 11213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 113136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek void mergeIntoScratch(ValueVector const &source, bool isFirst); 114136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool updateValueVectorWithScratch(const CFGBlock *block); 115136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool updateValueVectors(const CFGBlock *block, const BVPair &newVals); 116610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 117610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool hasNoDeclarations() const { 118136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return DeclToIndex.size() == 0; 119610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 120610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 121610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void resetScratch(); 122136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &getScratch() { return scratch; } 12313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 124136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector::reference operator[](const VarDecl *vd); 125610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 126610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 127610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 128610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekCFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { 129610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned n = cfg.getNumBlockIDs(); 130610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (!n) 131610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 132136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek vals = new std::pair<ValueVector*, ValueVector*>[n]; 1332d78c374508dc1f4595fe5172b39bf51b07aa48cFrancois Pichet memset(vals, 0, sizeof(*vals) * n); 134610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 135610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 136610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekCFGBlockValues::~CFGBlockValues() { 137610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned n = cfg.getNumBlockIDs(); 138610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (n == 0) 139610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 14013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek for (unsigned i = 0; i < n; ++i) { 14113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek delete vals[i].first; 14213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek delete vals[i].second; 14313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek } 144610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek delete [] vals; 145610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 146610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 147610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { 148136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek DeclToIndex.computeMap(dc); 149136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek scratch.resize(DeclToIndex.size()); 150610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 151610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 152136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) { 15313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek if (!bv) 154136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bv = new ValueVector(DeclToIndex.size()); 155610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return *bv; 156610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 157610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 15813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek/// This function pattern matches for a '&&' or '||' that appears at 15913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek/// the beginning of a CFGBlock that also (1) has a terminator and 16013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek/// (2) has no other elements. If such an expression is found, it is returned. 16113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenekstatic BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) { 16213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek if (block->empty()) 16313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return 0; 1649fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 1653c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek const CFGStmt *cstmt = block->front().getAs<CFGStmt>(); 1663c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek BinaryOperator *b = llvm::dyn_cast_or_null<BinaryOperator>(cstmt->getStmt()); 1679fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 1689fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (!b || !b->isLogicalOp()) 16913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return 0; 1709fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 1719fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (block->pred_size() == 2 && 1729fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek ((block->succ_size() == 2 && block->getTerminatorCondition() == b) || 1739fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek block->size() == 1)) 1749fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek return b; 1759fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 1769fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek return 0; 17713bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 17813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 179136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector &CFGBlockValues::getValueVector(const CFGBlock *block, 180136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek const CFGBlock *dstBlock) { 18113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek unsigned idx = block->getBlockID(); 1829fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (dstBlock && getLogicalOperatorInChain(block)) { 1839fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (*block->succ_begin() == dstBlock) 1849fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek return lazyCreate(vals[idx].first); 1859fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek assert(*(block->succ_begin()+1) == dstBlock); 1869fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek return lazyCreate(vals[idx].second); 18713bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek } 18813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 18913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek assert(vals[idx].second == 0); 19013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return lazyCreate(vals[idx].first); 19113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 19213bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 193136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekBVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block, 194136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek bool shouldLazyCreate) { 19513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek unsigned idx = block->getBlockID(); 19613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek lazyCreate(vals[idx].first); 1979fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (shouldLazyCreate) 1989fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek lazyCreate(vals[idx].second); 19913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return vals[idx]; 20013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 20113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 202136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekvoid CFGBlockValues::mergeIntoScratch(ValueVector const &source, 203610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool isFirst) { 204610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (isFirst) 205610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek scratch = source; 206610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek else 207afb10c4bda2ac2c268fa7e6c11141584f57de119Ted Kremenek scratch.merge(source); 208610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 2099fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#if 0 210136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekstatic void printVector(const CFGBlock *block, ValueVector &bv, 2119fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek unsigned num) { 2129fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 2139fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << block->getBlockID() << " :"; 2149fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek for (unsigned i = 0; i < bv.size(); ++i) { 2159fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << ' ' << bv[i]; 2169fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek } 2179fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek llvm::errs() << " : " << num << '\n'; 2189fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek} 2199fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 220610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 221136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekbool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) { 222136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector &dst = getValueVector(block, 0); 223610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool changed = (dst != scratch); 224610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed) 225610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek dst = scratch; 2269fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#if 0 2279fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, scratch, 0); 2289fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 22913bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek return changed; 23013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek} 23113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 232136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenekbool CFGBlockValues::updateValueVectors(const CFGBlock *block, 23313bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek const BVPair &newVals) { 234136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair &vals = getValueVectors(block, true); 23513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek bool changed = *newVals.first != *vals.first || 23613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek *newVals.second != *vals.second; 23713bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek *vals.first = *newVals.first; 23813bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek *vals.second = *newVals.second; 2399fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#if 0 2409fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, *vals.first, 1); 2419fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek printVector(block, *vals.second, 2); 2429fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek#endif 243610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return changed; 244610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 245610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 246610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid CFGBlockValues::resetScratch() { 247610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek scratch.reset(); 248610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 249610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 250136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted KremenekValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { 251136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek const llvm::Optional<unsigned> &idx = DeclToIndex.getValueIndex(vd); 252610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek assert(idx.hasValue()); 253610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return scratch[idx.getValue()]; 254610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 255610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 256610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 257610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// Worklist: worklist for dataflow analysis. 258610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 259610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 260610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 261610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass DataflowWorklist { 262610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek llvm::SmallVector<const CFGBlock *, 20> worklist; 263136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector enqueuedBlocks; 264610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 265610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} 266610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 267610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void enqueue(const CFGBlock *block); 268610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void enqueueSuccessors(const CFGBlock *block); 269610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *dequeue(); 270610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 271610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 272610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 273610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 274610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid DataflowWorklist::enqueue(const CFGBlock *block) { 275c104e53639de4424b83955acfadc977773b5883dTed Kremenek if (!block) 276c104e53639de4424b83955acfadc977773b5883dTed Kremenek return; 277610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek unsigned idx = block->getBlockID(); 278610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (enqueuedBlocks[idx]) 279610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 280610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.push_back(block); 281610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek enqueuedBlocks[idx] = true; 282610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 283610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 284610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 285610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_succ_iterator I = block->succ_begin(), 286610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->succ_end(); I != E; ++I) { 287610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek enqueue(*I); 288610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 289610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 290610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 291610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekconst CFGBlock *DataflowWorklist::dequeue() { 292610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (worklist.empty()) 293610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return 0; 294610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFGBlock *b = worklist.back(); 295610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.pop_back(); 296610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek enqueuedBlocks[b->getBlockID()] = false; 297610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return b; 298610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 299610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 300610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 301610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// Transfer function for uninitialized values analysis. 302610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 303610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 304610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremeneknamespace { 305610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass FindVarResult { 306610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd; 307610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *dr; 308610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 309610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {} 310610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 311610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const DeclRefExpr *getDeclRefExpr() const { return dr; } 312610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *getDecl() const { return vd; } 313610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 314610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 315610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekclass TransferFunctions : public CFGRecStmtVisitor<TransferFunctions> { 316610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues &vals; 317610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg; 318a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek AnalysisContext ∾ 319610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek UninitVariablesHandler *handler; 320c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek const DeclRefExpr *currentDR; 321dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek const Expr *currentVoidCast; 322a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek const bool flagBlockUses; 323610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekpublic: 324610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek TransferFunctions(CFGBlockValues &vals, const CFG &cfg, 325a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek AnalysisContext &ac, 326a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek UninitVariablesHandler *handler, 327a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek bool flagBlockUses) 328a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek : vals(vals), cfg(cfg), ac(ac), handler(handler), currentDR(0), 329dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek currentVoidCast(0), flagBlockUses(flagBlockUses) {} 330610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 331610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &getCFG() { return cfg; } 332610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void reportUninit(const DeclRefExpr *ex, const VarDecl *vd); 333a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 334a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek void VisitBlockExpr(BlockExpr *be); 335610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitDeclStmt(DeclStmt *ds); 336c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek void VisitDeclRefExpr(DeclRefExpr *dr); 337610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitUnaryOperator(UnaryOperator *uo); 338610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitBinaryOperator(BinaryOperator *bo); 339610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek void VisitCastExpr(CastExpr *ce); 340f4e3cfbe8abd124be6341ef5d714819b4fbd9082Peter Collingbourne void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *se); 3411ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); 34240900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek 34340900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek bool isTrackedVar(const VarDecl *vd) { 34440900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); 34540900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek } 34640900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek 34740900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek FindVarResult findBlockVarDecl(Expr *ex); 348610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek}; 349610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 350610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 351610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::reportUninit(const DeclRefExpr *ex, 352610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const VarDecl *vd) { 353610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (handler) handler->handleUseOfUninitVariable(ex, vd); 354610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 355610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 35640900ee8f3072d05456134b57c0fad85a6bb21a6Ted KremenekFindVarResult TransferFunctions::findBlockVarDecl(Expr* ex) { 3571ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (DeclRefExpr* dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts())) 3581ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 3591ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (isTrackedVar(vd)) 36040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek return FindVarResult(vd, dr); 3611ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek return FindVarResult(0, 0); 3621ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 3631ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 3641ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenekvoid TransferFunctions::BlockStmt_VisitObjCForCollectionStmt( 3651ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek ObjCForCollectionStmt *fs) { 3661ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 3671ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek Visit(fs->getCollection()); 3681ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 3691ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // This represents an initialization of the 'element' value. 3701ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek Stmt *element = fs->getElement(); 3711ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek const VarDecl* vd = 0; 3721ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 3731ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (DeclStmt* ds = dyn_cast<DeclStmt>(element)) { 3741ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vd = cast<VarDecl>(ds->getSingleDecl()); 3751ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (!isTrackedVar(vd)) 3761ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vd = 0; 3771ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 3781ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek else { 3791ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek // Initialize the value of the reference variable. 3801ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); 3811ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vd = res.getDecl(); 3821ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (!vd) { 3831ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek Visit(element); 3841ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek return; 3851ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 3861ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek } 3871ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 3881ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek if (vd) 3891ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek vals[vd] = Initialized; 3901ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek} 3911ea800c4ca76d5bb41aa8a1e0a6c7628b9fff28dTed Kremenek 392a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *be) { 393a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek if (!flagBlockUses || !handler) 394a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek return; 395a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek AnalysisContext::referenced_decls_iterator i, e; 396a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek llvm::tie(i, e) = ac.getReferencedBlockVars(be->getBlockDecl()); 397a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek for ( ; i != e; ++i) { 398a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek const VarDecl *vd = *i; 39940900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek if (vd->getAttr<BlocksAttr>() || !vd->hasLocalStorage() || 40040900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek !isTrackedVar(vd)) 401a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek continue; 402a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek if (vals[vd] == Uninitialized) 40340900ee8f3072d05456134b57c0fad85a6bb21a6Ted Kremenek handler->handleUseOfUninitVariable(be, vd); 404a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek } 405a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek} 406a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek 407610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitDeclStmt(DeclStmt *ds) { 408610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end(); 409610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DI != DE; ++DI) { 410610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) { 4114dccb90e92ba9e4abffe0177493b6db9949678ddTed Kremenek if (isTrackedVar(vd)) { 4124dccb90e92ba9e4abffe0177493b6db9949678ddTed Kremenek vals[vd] = Uninitialized; 413610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (Stmt *init = vd->getInit()) { 414610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek Visit(init); 415c104e53639de4424b83955acfadc977773b5883dTed Kremenek vals[vd] = Initialized; 416610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 4174dccb90e92ba9e4abffe0177493b6db9949678ddTed Kremenek } 418c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek else if (Stmt *init = vd->getInit()) { 419c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(init); 420c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek } 421610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 422610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 423610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 424610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 425c21fed361c11f13db345cba69101578578d8fb79Ted Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { 426c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast 427c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // cannot be block-level expressions. Therefore, we determine if 428c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // a DeclRefExpr is involved in a "load" by comparing it to the current 429c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 430c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // If a DeclRefExpr is not involved in a load, we are essentially computing 431c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // its address, either for assignment to a reference or via the '&' operator. 432c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // In such cases, treat the variable as being initialized, since this 433c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // analysis isn't powerful enough to do alias tracking. 434c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek if (dr != currentDR) 435c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) 436c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek if (isTrackedVar(vd)) 437c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek vals[vd] = Initialized; 438c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek} 439c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek 440610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { 441610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (bo->isAssignmentOp()) { 442610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const FindVarResult &res = findBlockVarDecl(bo->getLHS()); 443610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (const VarDecl* vd = res.getDecl()) { 444c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // We assume that DeclRefExprs wrapped in a BinaryOperator "assignment" 445c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // cannot be block-level expressions. Therefore, we determine if 446c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // a DeclRefExpr is involved in a "load" by comparing it to the current 447c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 448c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 449c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek res.getDeclRefExpr()); 450c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(bo->getRHS()); 451c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(bo->getLHS()); 452c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek 453136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector::reference bit = vals[vd]; 454610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (bit == Uninitialized) { 455610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (bo->getOpcode() != BO_Assign) 456610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek reportUninit(res.getDeclRefExpr(), vd); 457610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bit = Initialized; 458610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 459c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek return; 460610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 461610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 462c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(bo->getRHS()); 463c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(bo->getLHS()); 464610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 465610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 466610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { 467610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek switch (uo->getOpcode()) { 468610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PostDec: 469610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PostInc: 470610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PreDec: 471610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek case clang::UO_PreInc: { 472610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const FindVarResult &res = findBlockVarDecl(uo->getSubExpr()); 473610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (const VarDecl *vd = res.getDecl()) { 474c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // We assume that DeclRefExprs wrapped in a unary operator ++/-- 475c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // cannot be block-level expressions. Therefore, we determine if 476c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // a DeclRefExpr is involved in a "load" by comparing it to the current 477c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 478c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 479c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek res.getDeclRefExpr()); 480c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(uo->getSubExpr()); 481c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek 482136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector::reference bit = vals[vd]; 483610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (bit == Uninitialized) { 484610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek reportUninit(res.getDeclRefExpr(), vd); 485610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bit = Initialized; 486610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 487c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek return; 488610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 489610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek break; 490610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 491610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek default: 492610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek break; 493610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 494c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(uo->getSubExpr()); 495610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 496610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 497610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { 498610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (ce->getCastKind() == CK_LValueToRValue) { 499610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); 500c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek if (const VarDecl *vd = res.getDecl()) { 501c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast 502c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // cannot be block-level expressions. Therefore, we determine if 503c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // a DeclRefExpr is involved in a "load" by comparing it to the current 504c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. 505c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // Here we update 'currentDR' to be the one associated with this 506c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // lvalue-to-rvalue cast. Then, when we analyze the DeclRefExpr, we 507c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // will know that we are not computing its lvalue for other purposes 508c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // than to perform a load. 509c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 510c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek res.getDeclRefExpr()); 511c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(ce->getSubExpr()); 512dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek if (currentVoidCast != ce && vals[vd] == Uninitialized) { 513610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek reportUninit(res.getDeclRefExpr(), vd); 514c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek // Don't cascade warnings. 515c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek vals[vd] = Initialized; 516c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek } 517c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek return; 518c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek } 519dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 520dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) { 521dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek if (cse->getType()->isVoidType()) { 522dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek // e.g. (void) x; 523dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek SaveAndRestore<const Expr *> 524dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek lastVoidCast(currentVoidCast, cse->getSubExpr()->IgnoreParens()); 525dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek Visit(cse->getSubExpr()); 526dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek return; 527dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 528dd0f7942c5415ce146dcc02d57fc503c683f8625Ted Kremenek } 529c21fed361c11f13db345cba69101578578d8fb79Ted Kremenek Visit(ce->getSubExpr()); 530610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 531610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 532f4e3cfbe8abd124be6341ef5d714819b4fbd9082Peter Collingbournevoid TransferFunctions::VisitUnaryExprOrTypeTraitExpr( 533f4e3cfbe8abd124be6341ef5d714819b4fbd9082Peter Collingbourne UnaryExprOrTypeTraitExpr *se) { 534f4e3cfbe8abd124be6341ef5d714819b4fbd9082Peter Collingbourne if (se->getKind() == UETT_SizeOf) { 5359660803cd332d5c605899435019bb3b37fca3accTed Kremenek if (se->getType()->isConstantSizeType()) 5369660803cd332d5c605899435019bb3b37fca3accTed Kremenek return; 5379660803cd332d5c605899435019bb3b37fca3accTed Kremenek // Handle VLAs. 5389660803cd332d5c605899435019bb3b37fca3accTed Kremenek Visit(se->getArgumentExpr()); 5399660803cd332d5c605899435019bb3b37fca3accTed Kremenek } 5409660803cd332d5c605899435019bb3b37fca3accTed Kremenek} 5419660803cd332d5c605899435019bb3b37fca3accTed Kremenek 542610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//------------------------------------------------------------------------====// 543610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek// High-level "driver" logic for uninitialized values analysis. 544610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek//====------------------------------------------------------------------------// 545610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 54613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenekstatic bool runOnBlock(const CFGBlock *block, const CFG &cfg, 547a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek AnalysisContext &ac, CFGBlockValues &vals, 548a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek UninitVariablesHandler *handler = 0, 549a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek bool flagBlockUses = false) { 55013bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 55113bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { 5529fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek CFGBlock::const_pred_iterator itr = block->pred_begin(); 553136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair vA = vals.getValueVectors(*itr, false); 5549fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek ++itr; 555136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek BVPair vB = vals.getValueVectors(*itr, false); 5569fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 5579fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek BVPair valsAB; 5589fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek 5599fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek if (b->getOpcode() == BO_LAnd) { 5609fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek // Merge the 'F' bits from the first and second. 5619fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true); 5629fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false); 5639fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek valsAB.first = vA.first; 5642d4bed140f65d713673d2d32ec3adadc960078c6Ted Kremenek valsAB.second = &vals.getScratch(); 56513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek } 5669fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek else { 5679fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek // Merge the 'T' bits from the first and second. 5689fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek assert(b->getOpcode() == BO_LOr); 5699fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*vA.first, true); 5709fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek vals.mergeIntoScratch(*vB.first, false); 5719fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek valsAB.first = &vals.getScratch(); 5729fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek valsAB.second = vA.second ? vA.second : vA.first; 5739fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek } 574136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectors(block, valsAB); 57513bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek } 57613bd4236ab8297350be388ab442b4c42eb8fe437Ted Kremenek 5779fcbceed43e5610fdff43defe533934733453ae2Ted Kremenek // Default behavior: merge in values of predecessor blocks. 578610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.resetScratch(); 579610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek bool isFirst = true; 580610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 581610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek E = block->pred_end(); I != E; ++I) { 582136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek vals.mergeIntoScratch(vals.getValueVector(*I, block), isFirst); 583610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek isFirst = false; 584610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 585610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Apply the transfer function. 586a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek TransferFunctions tf(vals, cfg, ac, handler, flagBlockUses); 587610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 588610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek I != E; ++I) { 589610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { 590610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek tf.BlockStmt_Visit(cs->getStmt()); 591610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 592610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 593136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek return vals.updateValueVectorWithScratch(block); 594610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 595610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 596610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenekvoid clang::runUninitializedVariablesAnalysis(const DeclContext &dc, 597610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek const CFG &cfg, 598a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek AnalysisContext &ac, 599610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek UninitVariablesHandler &handler) { 600610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek CFGBlockValues vals(cfg); 601610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek vals.computeSetOfDeclarations(dc); 602610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (vals.hasNoDeclarations()) 603610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek return; 604610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek DataflowWorklist worklist(cfg); 605136f8f24b0b6c0e57aaa4375d280d72dc5492615Ted Kremenek ValueVector previouslyVisited(cfg.getNumBlockIDs()); 606610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 607610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(&cfg.getEntry()); 608610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 609610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 610610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Did the block change? 611a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek bool changed = runOnBlock(block, cfg, ac, vals); 612610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek if (changed || !previouslyVisited[block->getBlockID()]) 613610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek worklist.enqueueSuccessors(block); 614610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek previouslyVisited[block->getBlockID()] = true; 615610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 616610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 617610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek // Run through the blocks one more time, and report uninitialized variabes. 618610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { 619a8c17a5babab35f2db26bf218e7571d1af4afedfTed Kremenek runOnBlock(*BI, cfg, ac, vals, &handler, /* flagBlockUses */ true); 620610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek } 621610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek} 622610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 623610068c8cd2321f90e147b12cf794e1f840b6405Ted KremenekUninitVariablesHandler::~UninitVariablesHandler() {} 624610068c8cd2321f90e147b12cf794e1f840b6405Ted Kremenek 625