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