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