UninitializedValues.cpp revision 6cfa78f6bd4e7d5e23366a0907f8f8792366bc4c 
1//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements uninitialized values analysis for source-level CFGs.
11//
12//===----------------------------------------------------------------------===//
13
14#include <utility>
15#include "llvm/ADT/Optional.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/PackedVector.h"
18#include "llvm/ADT/DenseMap.h"
19#include "clang/AST/ASTContext.h"
20#include "clang/AST/Decl.h"
21#include "clang/Analysis/CFG.h"
22#include "clang/Analysis/AnalysisContext.h"
23#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
24#include "clang/Analysis/Analyses/UninitializedValues.h"
25#include "llvm/Support/SaveAndRestore.h"
26
27using namespace clang;
28
29#define DEBUG_LOGGING 0
30
31static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) {
32  if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() &&
33      !vd->isExceptionVariable() &&
34      vd->getDeclContext() == dc) {
35    QualType ty = vd->getType();
36    return ty->isScalarType() || ty->isVectorType();
37  }
38  return false;
39}
40
41//------------------------------------------------------------------------====//
42// DeclToIndex: a mapping from Decls we track to value indices.
43//====------------------------------------------------------------------------//
44
45namespace {
46class DeclToIndex {
47  llvm::DenseMap<const VarDecl *, unsigned> map;
48public:
49  DeclToIndex() {}
50
51  /// Compute the actual mapping from declarations to bits.
52  void computeMap(const DeclContext &dc);
53
54  /// Return the number of declarations in the map.
55  unsigned size() const { return map.size(); }
56
57  /// Returns the bit vector index for a given declaration.
58  llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const;
59};
60}
61
62void DeclToIndex::computeMap(const DeclContext &dc) {
63  unsigned count = 0;
64  DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()),
65                                               E(dc.decls_end());
66  for ( ; I != E; ++I) {
67    const VarDecl *vd = *I;
68    if (isTrackedVar(vd, &dc))
69      map[vd] = count++;
70  }
71}
72
73llvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const {
74  llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d);
75  if (I == map.end())
76    return llvm::Optional<unsigned>();
77  return I->second;
78}
79
80//------------------------------------------------------------------------====//
81// CFGBlockValues: dataflow values for CFG blocks.
82//====------------------------------------------------------------------------//
83
84// These values are defined in such a way that a merge can be done using
85// a bitwise OR.
86enum Value { Unknown = 0x0,         /* 00 */
87             Initialized = 0x1,     /* 01 */
88             Uninitialized = 0x2,   /* 10 */
89             MayUninitialized = 0x3 /* 11 */ };
90
91static bool isUninitialized(const Value v) {
92  return v >= Uninitialized;
93}
94static bool isAlwaysUninit(const Value v) {
95  return v == Uninitialized;
96}
97
98namespace {
99
100typedef llvm::PackedVector<Value, 2> ValueVector;
101typedef std::pair<ValueVector *, ValueVector *> BVPair;
102
103class CFGBlockValues {
104  const CFG &cfg;
105  BVPair *vals;
106  ValueVector scratch;
107  DeclToIndex declToIndex;
108
109  ValueVector &lazyCreate(ValueVector *&bv);
110public:
111  CFGBlockValues(const CFG &cfg);
112  ~CFGBlockValues();
113
114  unsigned getNumEntries() const { return declToIndex.size(); }
115
116  void computeSetOfDeclarations(const DeclContext &dc);
117  ValueVector &getValueVector(const CFGBlock *block,
118                              const CFGBlock *dstBlock);
119
120  BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate);
121
122  void setAllScratchValues(Value V);
123  void mergeIntoScratch(ValueVector const &source, bool isFirst);
124  bool updateValueVectorWithScratch(const CFGBlock *block);
125  bool updateValueVectors(const CFGBlock *block, const BVPair &newVals);
126
127  bool hasNoDeclarations() const {
128    return declToIndex.size() == 0;
129  }
130
131  void resetScratch();
132  ValueVector &getScratch() { return scratch; }
133
134  ValueVector::reference operator[](const VarDecl *vd);
135
136  Value getValue(const CFGBlock *block, const CFGBlock *dstBlock,
137                 const VarDecl *vd) {
138    const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd);
139    assert(idx.hasValue());
140    return getValueVector(block, dstBlock)[idx.getValue()];
141  }
142};
143} // end anonymous namespace
144
145CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {
146  unsigned n = cfg.getNumBlockIDs();
147  if (!n)
148    return;
149  vals = new std::pair<ValueVector*, ValueVector*>[n];
150  memset((void*)vals, 0, sizeof(*vals) * n);
151}
152
153CFGBlockValues::~CFGBlockValues() {
154  unsigned n = cfg.getNumBlockIDs();
155  if (n == 0)
156    return;
157  for (unsigned i = 0; i < n; ++i) {
158    delete vals[i].first;
159    delete vals[i].second;
160  }
161  delete [] vals;
162}
163
164void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) {
165  declToIndex.computeMap(dc);
166  scratch.resize(declToIndex.size());
167}
168
169ValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) {
170  if (!bv)
171    bv = new ValueVector(declToIndex.size());
172  return *bv;
173}
174
175/// This function pattern matches for a '&&' or '||' that appears at
176/// the beginning of a CFGBlock that also (1) has a terminator and
177/// (2) has no other elements.  If such an expression is found, it is returned.
178static const BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) {
179  if (block->empty())
180    return 0;
181
182  CFGElement front = block->front();
183  const CFGStmt *cstmt = front.getAs<CFGStmt>();
184  if (!cstmt)
185    return 0;
186
187  const BinaryOperator *b = dyn_cast_or_null<BinaryOperator>(cstmt->getStmt());
188
189  if (!b || !b->isLogicalOp())
190    return 0;
191
192  if (block->pred_size() == 2) {
193    if (block->getTerminatorCondition() == b) {
194      if (block->succ_size() == 2)
195      return b;
196    }
197    else if (block->size() == 1)
198      return b;
199  }
200
201  return 0;
202}
203
204ValueVector &CFGBlockValues::getValueVector(const CFGBlock *block,
205                                            const CFGBlock *dstBlock) {
206  unsigned idx = block->getBlockID();
207  if (dstBlock && getLogicalOperatorInChain(block)) {
208    if (*block->succ_begin() == dstBlock)
209      return lazyCreate(vals[idx].first);
210    assert(*(block->succ_begin()+1) == dstBlock);
211    return lazyCreate(vals[idx].second);
212  }
213
214  assert(vals[idx].second == 0);
215  return lazyCreate(vals[idx].first);
216}
217
218BVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block,
219                                        bool shouldLazyCreate) {
220  unsigned idx = block->getBlockID();
221  lazyCreate(vals[idx].first);
222  if (shouldLazyCreate)
223    lazyCreate(vals[idx].second);
224  return vals[idx];
225}
226
227#if DEBUG_LOGGING
228static void printVector(const CFGBlock *block, ValueVector &bv,
229                        unsigned num) {
230  llvm::errs() << block->getBlockID() << " :";
231  for (unsigned i = 0; i < bv.size(); ++i) {
232    llvm::errs() << ' ' << bv[i];
233  }
234  llvm::errs() << " : " << num << '\n';
235}
236#endif
237
238void CFGBlockValues::setAllScratchValues(Value V) {
239  for (unsigned I = 0, E = scratch.size(); I != E; ++I)
240    scratch[I] = V;
241}
242
243void CFGBlockValues::mergeIntoScratch(ValueVector const &source,
244                                      bool isFirst) {
245  if (isFirst)
246    scratch = source;
247  else
248    scratch |= source;
249}
250
251bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) {
252  ValueVector &dst = getValueVector(block, 0);
253  bool changed = (dst != scratch);
254  if (changed)
255    dst = scratch;
256#if DEBUG_LOGGING
257  printVector(block, scratch, 0);
258#endif
259  return changed;
260}
261
262bool CFGBlockValues::updateValueVectors(const CFGBlock *block,
263                                      const BVPair &newVals) {
264  BVPair &vals = getValueVectors(block, true);
265  bool changed = *newVals.first != *vals.first ||
266                 *newVals.second != *vals.second;
267  *vals.first = *newVals.first;
268  *vals.second = *newVals.second;
269#if DEBUG_LOGGING
270  printVector(block, *vals.first, 1);
271  printVector(block, *vals.second, 2);
272#endif
273  return changed;
274}
275
276void CFGBlockValues::resetScratch() {
277  scratch.reset();
278}
279
280ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) {
281  const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd);
282  assert(idx.hasValue());
283  return scratch[idx.getValue()];
284}
285
286//------------------------------------------------------------------------====//
287// Worklist: worklist for dataflow analysis.
288//====------------------------------------------------------------------------//
289
290namespace {
291class DataflowWorklist {
292  SmallVector<const CFGBlock *, 20> worklist;
293  llvm::BitVector enqueuedBlocks;
294public:
295  DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {}
296
297  void enqueueSuccessors(const CFGBlock *block);
298  const CFGBlock *dequeue();
299};
300}
301
302void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) {
303  unsigned OldWorklistSize = worklist.size();
304  for (CFGBlock::const_succ_iterator I = block->succ_begin(),
305       E = block->succ_end(); I != E; ++I) {
306    const CFGBlock *Successor = *I;
307    if (!Successor || enqueuedBlocks[Successor->getBlockID()])
308      continue;
309    worklist.push_back(Successor);
310    enqueuedBlocks[Successor->getBlockID()] = true;
311  }
312  if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
313    return;
314
315  // Rotate the newly added blocks to the start of the worklist so that it forms
316  // a proper queue when we pop off the end of the worklist.
317  std::rotate(worklist.begin(), worklist.begin() + OldWorklistSize,
318              worklist.end());
319}
320
321const CFGBlock *DataflowWorklist::dequeue() {
322  if (worklist.empty())
323    return 0;
324  const CFGBlock *b = worklist.back();
325  worklist.pop_back();
326  enqueuedBlocks[b->getBlockID()] = false;
327  return b;
328}
329
330//------------------------------------------------------------------------====//
331// Classification of DeclRefExprs as use or initialization.
332//====------------------------------------------------------------------------//
333
334namespace {
335class FindVarResult {
336  const VarDecl *vd;
337  const DeclRefExpr *dr;
338public:
339  FindVarResult(const VarDecl *vd, const DeclRefExpr *dr) : vd(vd), dr(dr) {}
340
341  const DeclRefExpr *getDeclRefExpr() const { return dr; }
342  const VarDecl *getDecl() const { return vd; }
343};
344
345static const Expr *stripCasts(ASTContext &C, const Expr *Ex) {
346  while (Ex) {
347    Ex = Ex->IgnoreParenNoopCasts(C);
348    if (const CastExpr *CE = dyn_cast<CastExpr>(Ex)) {
349      if (CE->getCastKind() == CK_LValueBitCast) {
350        Ex = CE->getSubExpr();
351        continue;
352      }
353    }
354    break;
355  }
356  return Ex;
357}
358
359/// If E is an expression comprising a reference to a single variable, find that
360/// variable.
361static FindVarResult findVar(const Expr *E, const DeclContext *DC) {
362  if (const DeclRefExpr *DRE =
363        dyn_cast<DeclRefExpr>(stripCasts(DC->getParentASTContext(), E)))
364    if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()))
365      if (isTrackedVar(VD, DC))
366        return FindVarResult(VD, DRE);
367  return FindVarResult(0, 0);
368}
369
370/// \brief Classify each DeclRefExpr as an initialization or a use. Any
371/// DeclRefExpr which isn't explicitly classified will be assumed to have
372/// escaped the analysis and will be treated as an initialization.
373class ClassifyRefs : public StmtVisitor<ClassifyRefs> {
374public:
375  enum Class {
376    Init,
377    Use,
378    SelfInit,
379    Ignore
380  };
381
382private:
383  const DeclContext *DC;
384  llvm::DenseMap<const DeclRefExpr*, Class> Classification;
385
386  bool isTrackedVar(const VarDecl *VD) const {
387    return ::isTrackedVar(VD, DC);
388  }
389
390  void classify(const Expr *E, Class C);
391
392public:
393  ClassifyRefs(AnalysisDeclContext &AC) : DC(cast<DeclContext>(AC.getDecl())) {}
394
395  void VisitDeclStmt(DeclStmt *DS);
396  void VisitUnaryOperator(UnaryOperator *UO);
397  void VisitBinaryOperator(BinaryOperator *BO);
398  void VisitCallExpr(CallExpr *CE);
399  void VisitCastExpr(CastExpr *CE);
400
401  void operator()(Stmt *S) { Visit(S); }
402
403  Class get(const DeclRefExpr *DRE) const {
404    llvm::DenseMap<const DeclRefExpr*, Class>::const_iterator I
405        = Classification.find(DRE);
406    if (I != Classification.end())
407      return I->second;
408
409    const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl());
410    if (!VD || !isTrackedVar(VD))
411      return Ignore;
412
413    return Init;
414  }
415};
416}
417
418static const DeclRefExpr *getSelfInitExpr(VarDecl *VD) {
419  if (Expr *Init = VD->getInit()) {
420    const DeclRefExpr *DRE
421      = dyn_cast<DeclRefExpr>(stripCasts(VD->getASTContext(), Init));
422    if (DRE && DRE->getDecl() == VD)
423      return DRE;
424  }
425  return 0;
426}
427
428void ClassifyRefs::classify(const Expr *E, Class C) {
429  FindVarResult Var = findVar(E, DC);
430  if (const DeclRefExpr *DRE = Var.getDeclRefExpr())
431    Classification[DRE] = std::max(Classification[DRE], C);
432}
433
434void ClassifyRefs::VisitDeclStmt(DeclStmt *DS) {
435  for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end();
436       DI != DE; ++DI) {
437    VarDecl *VD = dyn_cast<VarDecl>(*DI);
438    if (VD && isTrackedVar(VD))
439      if (const DeclRefExpr *DRE = getSelfInitExpr(VD))
440        Classification[DRE] = SelfInit;
441  }
442}
443
444void ClassifyRefs::VisitBinaryOperator(BinaryOperator *BO) {
445  // Ignore the evaluation of a DeclRefExpr on the LHS of an assignment. If this
446  // is not a compound-assignment, we will treat it as initializing the variable
447  // when TransferFunctions visits it. A compound-assignment does not affect
448  // whether a variable is uninitialized, and there's no point counting it as a
449  // use.
450  if (BO->isCompoundAssignmentOp())
451    classify(BO->getLHS(), Use);
452  else if (BO->getOpcode() == BO_Assign)
453    classify(BO->getLHS(), Ignore);
454}
455
456void ClassifyRefs::VisitUnaryOperator(UnaryOperator *UO) {
457  // Increment and decrement are uses despite there being no lvalue-to-rvalue
458  // conversion.
459  if (UO->isIncrementDecrementOp())
460    classify(UO->getSubExpr(), Use);
461}
462
463void ClassifyRefs::VisitCallExpr(CallExpr *CE) {
464  // If a value is passed by const reference to a function, we should not assume
465  // that it is initialized by the call, and we conservatively do not assume
466  // that it is used.
467  for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
468       I != E; ++I)
469    if ((*I)->getType().isConstQualified() && (*I)->isGLValue())
470      classify(*I, Ignore);
471}
472
473void ClassifyRefs::VisitCastExpr(CastExpr *CE) {
474  if (CE->getCastKind() == CK_LValueToRValue)
475    classify(CE->getSubExpr(), Use);
476  else if (CStyleCastExpr *CSE = dyn_cast<CStyleCastExpr>(CE)) {
477    if (CSE->getType()->isVoidType()) {
478      // Squelch any detected load of an uninitialized value if
479      // we cast it to void.
480      // e.g. (void) x;
481      classify(CSE->getSubExpr(), Ignore);
482    }
483  }
484}
485
486//------------------------------------------------------------------------====//
487// Transfer function for uninitialized values analysis.
488//====------------------------------------------------------------------------//
489
490namespace {
491class TransferFunctions : public StmtVisitor<TransferFunctions> {
492  CFGBlockValues &vals;
493  const CFG &cfg;
494  const CFGBlock *block;
495  AnalysisDeclContext &ac;
496  const ClassifyRefs &classification;
497  UninitVariablesHandler *handler;
498
499public:
500  TransferFunctions(CFGBlockValues &vals, const CFG &cfg,
501                    const CFGBlock *block, AnalysisDeclContext &ac,
502                    const ClassifyRefs &classification,
503                    UninitVariablesHandler *handler)
504    : vals(vals), cfg(cfg), block(block), ac(ac),
505      classification(classification), handler(handler) {}
506
507  void reportUse(const Expr *ex, const VarDecl *vd);
508
509  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS);
510  void VisitBlockExpr(BlockExpr *be);
511  void VisitCallExpr(CallExpr *ce);
512  void VisitDeclStmt(DeclStmt *ds);
513  void VisitDeclRefExpr(DeclRefExpr *dr);
514  void VisitBinaryOperator(BinaryOperator *bo);
515
516  bool isTrackedVar(const VarDecl *vd) {
517    return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl()));
518  }
519
520  FindVarResult findVar(const Expr *ex) {
521    return ::findVar(ex, cast<DeclContext>(ac.getDecl()));
522  }
523
524  UninitUse getUninitUse(const Expr *ex, const VarDecl *vd, Value v) {
525    UninitUse Use(ex, isAlwaysUninit(v));
526
527    assert(isUninitialized(v));
528    if (Use.getKind() == UninitUse::Always)
529      return Use;
530
531    // If an edge which leads unconditionally to this use did not initialize
532    // the variable, we can say something stronger than 'may be uninitialized':
533    // we can say 'either it's used uninitialized or you have dead code'.
534    //
535    // We track the number of successors of a node which have been visited, and
536    // visit a node once we have visited all of its successors. Only edges where
537    // the variable might still be uninitialized are followed. Since a variable
538    // can't transfer from being initialized to being uninitialized, this will
539    // trace out the subgraph which inevitably leads to the use and does not
540    // initialize the variable. We do not want to skip past loops, since their
541    // non-termination might be correlated with the initialization condition.
542    //
543    // For example:
544    //
545    //         void f(bool a, bool b) {
546    // block1:   int n;
547    //           if (a) {
548    // block2:     if (b)
549    // block3:       n = 1;
550    // block4:   } else if (b) {
551    // block5:     while (!a) {
552    // block6:       do_work(&a);
553    //               n = 2;
554    //             }
555    //           }
556    // block7:   if (a)
557    // block8:     g();
558    // block9:   return n;
559    //         }
560    //
561    // Starting from the maybe-uninitialized use in block 9:
562    //  * Block 7 is not visited because we have only visited one of its two
563    //    successors.
564    //  * Block 8 is visited because we've visited its only successor.
565    // From block 8:
566    //  * Block 7 is visited because we've now visited both of its successors.
567    // From block 7:
568    //  * Blocks 1, 2, 4, 5, and 6 are not visited because we didn't visit all
569    //    of their successors (we didn't visit 4, 3, 5, 6, and 5, respectively).
570    //  * Block 3 is not visited because it initializes 'n'.
571    // Now the algorithm terminates, having visited blocks 7 and 8, and having
572    // found the frontier is blocks 2, 4, and 5.
573    //
574    // 'n' is definitely uninitialized for two edges into block 7 (from blocks 2
575    // and 4), so we report that any time either of those edges is taken (in
576    // each case when 'b == false'), 'n' is used uninitialized.
577    llvm::SmallVector<const CFGBlock*, 32> Queue;
578    llvm::SmallVector<unsigned, 32> SuccsVisited(cfg.getNumBlockIDs(), 0);
579    Queue.push_back(block);
580    // Specify that we've already visited all successors of the starting block.
581    // This has the dual purpose of ensuring we never add it to the queue, and
582    // of marking it as not being a candidate element of the frontier.
583    SuccsVisited[block->getBlockID()] = block->succ_size();
584    while (!Queue.empty()) {
585      const CFGBlock *B = Queue.back();
586      Queue.pop_back();
587      for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end();
588           I != E; ++I) {
589        const CFGBlock *Pred = *I;
590        if (vals.getValue(Pred, B, vd) == Initialized)
591          // This block initializes the variable.
592          continue;
593
594        unsigned &SV = SuccsVisited[Pred->getBlockID()];
595        if (!SV) {
596          // When visiting the first successor of a block, mark all NULL
597          // successors as having been visited.
598          for (CFGBlock::const_succ_iterator SI = Pred->succ_begin(),
599                                             SE = Pred->succ_end();
600               SI != SE; ++SI)
601            if (!*SI)
602              ++SV;
603        }
604
605        if (++SV == Pred->succ_size())
606          // All paths from this block lead to the use and don't initialize the
607          // variable.
608          Queue.push_back(Pred);
609      }
610    }
611
612    // Scan the frontier, looking for blocks where the variable was
613    // uninitialized.
614    for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) {
615      const CFGBlock *Block = *BI;
616      unsigned BlockID = Block->getBlockID();
617      const Stmt *Term = Block->getTerminator();
618      if (SuccsVisited[BlockID] && SuccsVisited[BlockID] < Block->succ_size() &&
619          Term) {
620        // This block inevitably leads to the use. If we have an edge from here
621        // to a post-dominator block, and the variable is uninitialized on that
622        // edge, we have found a bug.
623        for (CFGBlock::const_succ_iterator I = Block->succ_begin(),
624             E = Block->succ_end(); I != E; ++I) {
625          const CFGBlock *Succ = *I;
626          if (Succ && SuccsVisited[Succ->getBlockID()] >= Succ->succ_size() &&
627              vals.getValue(Block, Succ, vd) == Uninitialized) {
628            // Switch cases are a special case: report the label to the caller
629            // as the 'terminator', not the switch statement itself. Suppress
630            // situations where no label matched: we can't be sure that's
631            // possible.
632            if (isa<SwitchStmt>(Term)) {
633              const Stmt *Label = Succ->getLabel();
634              if (!Label || !isa<SwitchCase>(Label))
635                // Might not be possible.
636                continue;
637              UninitUse::Branch Branch;
638              Branch.Terminator = Label;
639              Branch.Output = 0; // Ignored.
640              Use.addUninitBranch(Branch);
641            } else {
642              UninitUse::Branch Branch;
643              Branch.Terminator = Term;
644              Branch.Output = I - Block->succ_begin();
645              Use.addUninitBranch(Branch);
646            }
647          }
648        }
649      }
650    }
651
652    return Use;
653  }
654};
655}
656
657void TransferFunctions::reportUse(const Expr *ex, const VarDecl *vd) {
658  if (!handler)
659    return;
660  Value v = vals[vd];
661  if (isUninitialized(v))
662    handler->handleUseOfUninitVariable(vd, getUninitUse(ex, vd, v));
663}
664
665void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *FS) {
666  // This represents an initialization of the 'element' value.
667  if (DeclStmt *DS = dyn_cast<DeclStmt>(FS->getElement())) {
668    const VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
669    if (isTrackedVar(VD))
670      vals[VD] = Initialized;
671  }
672}
673
674void TransferFunctions::VisitBlockExpr(BlockExpr *be) {
675  const BlockDecl *bd = be->getBlockDecl();
676  for (BlockDecl::capture_const_iterator i = bd->capture_begin(),
677        e = bd->capture_end() ; i != e; ++i) {
678    const VarDecl *vd = i->getVariable();
679    if (!isTrackedVar(vd))
680      continue;
681    if (i->isByRef()) {
682      vals[vd] = Initialized;
683      continue;
684    }
685    reportUse(be, vd);
686  }
687}
688
689void TransferFunctions::VisitCallExpr(CallExpr *ce) {
690  // After a call to a function like setjmp or vfork, any variable which is
691  // initialized anywhere within this function may now be initialized. For now,
692  // just assume such a call initializes all variables.
693  // FIXME: Only mark variables as initialized if they have an initializer which
694  // is reachable from here.
695  Decl *Callee = ce->getCalleeDecl();
696  if (Callee && Callee->hasAttr<ReturnsTwiceAttr>())
697    vals.setAllScratchValues(Initialized);
698}
699
700void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) {
701  switch (classification.get(dr)) {
702  case ClassifyRefs::Ignore:
703    break;
704  case ClassifyRefs::Use:
705    reportUse(dr, cast<VarDecl>(dr->getDecl()));
706    break;
707  case ClassifyRefs::Init:
708    vals[cast<VarDecl>(dr->getDecl())] = Initialized;
709    break;
710  case ClassifyRefs::SelfInit:
711    if (handler)
712      handler->handleSelfInit(cast<VarDecl>(dr->getDecl()));
713    break;
714  }
715}
716
717void TransferFunctions::VisitBinaryOperator(BinaryOperator *BO) {
718  if (BO->getOpcode() == BO_Assign) {
719    FindVarResult Var = findVar(BO->getLHS());
720    if (const VarDecl *VD = Var.getDecl())
721      vals[VD] = Initialized;
722  }
723}
724
725void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
726  for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end();
727       DI != DE; ++DI) {
728    VarDecl *VD = dyn_cast<VarDecl>(*DI);
729    if (VD && isTrackedVar(VD)) {
730      if (getSelfInitExpr(VD)) {
731        // If the initializer consists solely of a reference to itself, we
732        // explicitly mark the variable as uninitialized. This allows code
733        // like the following:
734        //
735        //   int x = x;
736        //
737        // to deliberately leave a variable uninitialized. Different analysis
738        // clients can detect this pattern and adjust their reporting
739        // appropriately, but we need to continue to analyze subsequent uses
740        // of the variable.
741        vals[VD] = Uninitialized;
742      } else if (VD->getInit()) {
743        // Treat the new variable as initialized.
744        vals[VD] = Initialized;
745      } else {
746        // No initializer: the variable is now uninitialized. This matters
747        // for cases like:
748        //   while (...) {
749        //     int n;
750        //     use(n);
751        //     n = 0;
752        //   }
753        // FIXME: Mark the variable as uninitialized whenever its scope is
754        // left, since its scope could be re-entered by a jump over the
755        // declaration.
756        vals[VD] = Uninitialized;
757      }
758    }
759  }
760}
761
762//------------------------------------------------------------------------====//
763// High-level "driver" logic for uninitialized values analysis.
764//====------------------------------------------------------------------------//
765
766static bool runOnBlock(const CFGBlock *block, const CFG &cfg,
767                       AnalysisDeclContext &ac, CFGBlockValues &vals,
768                       const ClassifyRefs &classification,
769                       llvm::BitVector &wasAnalyzed,
770                       UninitVariablesHandler *handler = 0) {
771
772  wasAnalyzed[block->getBlockID()] = true;
773
774  if (const BinaryOperator *b = getLogicalOperatorInChain(block)) {
775    CFGBlock::const_pred_iterator itr = block->pred_begin();
776    BVPair vA = vals.getValueVectors(*itr, false);
777    ++itr;
778    BVPair vB = vals.getValueVectors(*itr, false);
779
780    BVPair valsAB;
781
782    if (b->getOpcode() == BO_LAnd) {
783      // Merge the 'F' bits from the first and second.
784      vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true);
785      vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false);
786      valsAB.first = vA.first;
787      valsAB.second = &vals.getScratch();
788    } else {
789      // Merge the 'T' bits from the first and second.
790      assert(b->getOpcode() == BO_LOr);
791      vals.mergeIntoScratch(*vA.first, true);
792      vals.mergeIntoScratch(*vB.first, false);
793      valsAB.first = &vals.getScratch();
794      valsAB.second = vA.second ? vA.second : vA.first;
795    }
796    return vals.updateValueVectors(block, valsAB);
797  }
798
799  // Default behavior: merge in values of predecessor blocks.
800  vals.resetScratch();
801  bool isFirst = true;
802  for (CFGBlock::const_pred_iterator I = block->pred_begin(),
803       E = block->pred_end(); I != E; ++I) {
804    const CFGBlock *pred = *I;
805    if (wasAnalyzed[pred->getBlockID()]) {
806      vals.mergeIntoScratch(vals.getValueVector(pred, block), isFirst);
807      isFirst = false;
808    }
809  }
810  // Apply the transfer function.
811  TransferFunctions tf(vals, cfg, block, ac, classification, handler);
812  for (CFGBlock::const_iterator I = block->begin(), E = block->end();
813       I != E; ++I) {
814    if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) {
815      tf.Visit(const_cast<Stmt*>(cs->getStmt()));
816    }
817  }
818  return vals.updateValueVectorWithScratch(block);
819}
820
821void clang::runUninitializedVariablesAnalysis(
822    const DeclContext &dc,
823    const CFG &cfg,
824    AnalysisDeclContext &ac,
825    UninitVariablesHandler &handler,
826    UninitVariablesAnalysisStats &stats) {
827  CFGBlockValues vals(cfg);
828  vals.computeSetOfDeclarations(dc);
829  if (vals.hasNoDeclarations())
830    return;
831#if DEBUG_LOGGING
832  cfg.dump(dc.getParentASTContext().getLangOpts(), true);
833#endif
834
835  stats.NumVariablesAnalyzed = vals.getNumEntries();
836
837  // Precompute which expressions are uses and which are initializations.
838  ClassifyRefs classification(ac);
839  cfg.VisitBlockStmts(classification);
840
841  // Mark all variables uninitialized at the entry.
842  const CFGBlock &entry = cfg.getEntry();
843  for (CFGBlock::const_succ_iterator i = entry.succ_begin(),
844        e = entry.succ_end(); i != e; ++i) {
845    if (const CFGBlock *succ = *i) {
846      ValueVector &vec = vals.getValueVector(&entry, succ);
847      const unsigned n = vals.getNumEntries();
848      for (unsigned j = 0; j < n ; ++j) {
849        vec[j] = Uninitialized;
850      }
851    }
852  }
853
854  // Proceed with the workist.
855  DataflowWorklist worklist(cfg);
856  llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
857  worklist.enqueueSuccessors(&cfg.getEntry());
858  llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);
859  wasAnalyzed[cfg.getEntry().getBlockID()] = true;
860
861  while (const CFGBlock *block = worklist.dequeue()) {
862    // Did the block change?
863    bool changed = runOnBlock(block, cfg, ac, vals,
864                              classification, wasAnalyzed);
865    ++stats.NumBlockVisits;
866    if (changed || !previouslyVisited[block->getBlockID()])
867      worklist.enqueueSuccessors(block);
868    previouslyVisited[block->getBlockID()] = true;
869  }
870
871  // Run through the blocks one more time, and report uninitialized variabes.
872  for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) {
873    const CFGBlock *block = *BI;
874    if (wasAnalyzed[block->getBlockID()]) {
875      runOnBlock(block, cfg, ac, vals, classification, wasAnalyzed, &handler);
876      ++stats.NumBlockVisits;
877    }
878  }
879}
880
881UninitVariablesHandler::~UninitVariablesHandler() {}
882