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