UninitializedValues.cpp revision afb10c4bda2ac2c268fa7e6c11141584f57de119 
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/BitVector.h"
18#include "llvm/ADT/DenseMap.h"
19#include "clang/AST/Decl.h"
20#include "clang/Analysis/CFG.h"
21#include "clang/Analysis/AnalysisContext.h"
22#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
23#include "clang/Analysis/Analyses/UninitializedValues.h"
24#include "clang/Analysis/Support/SaveAndRestore.h"
25
26using namespace clang;
27
28static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) {
29  return vd->isLocalVarDecl() && !vd->hasGlobalStorage() &&
30         vd->getType()->isScalarType() &&
31         vd->getDeclContext() == dc;
32}
33
34//------------------------------------------------------------------------====//
35// DeclToIndex: a mapping from Decls we track to value indices.
36//====------------------------------------------------------------------------//
37
38namespace {
39class DeclToIndex {
40  llvm::DenseMap<const VarDecl *, unsigned> map;
41public:
42  DeclToIndex() {}
43
44  /// Compute the actual mapping from declarations to bits.
45  void computeMap(const DeclContext &dc);
46
47  /// Return the number of declarations in the map.
48  unsigned size() const { return map.size(); }
49
50  /// Returns the bit vector index for a given declaration.
51  llvm::Optional<unsigned> getValueIndex(const VarDecl *d);
52};
53}
54
55void DeclToIndex::computeMap(const DeclContext &dc) {
56  unsigned count = 0;
57  DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()),
58                                               E(dc.decls_end());
59  for ( ; I != E; ++I) {
60    const VarDecl *vd = *I;
61    if (isTrackedVar(vd, &dc))
62      map[vd] = count++;
63  }
64}
65
66llvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) {
67  llvm::DenseMap<const VarDecl *, unsigned>::iterator I = map.find(d);
68  if (I == map.end())
69    return llvm::Optional<unsigned>();
70  return I->second;
71}
72
73//------------------------------------------------------------------------====//
74// CFGBlockValues: dataflow values for CFG blocks.
75//====------------------------------------------------------------------------//
76
77static const bool Initialized = false;
78static const bool Uninitialized = true;
79
80class ValueVector {
81  llvm::BitVector vec;
82public:
83  ValueVector() {}
84  ValueVector(unsigned size) : vec(size) {}
85  typedef llvm::BitVector::reference reference;
86  void resize(unsigned n) { vec.resize(n); }
87  void merge(const ValueVector &rhs) { vec |= rhs.vec; }
88  bool operator!=(const ValueVector &rhs) const { return vec != rhs.vec; }
89  reference operator[](unsigned idx) { return vec[idx]; }
90  void reset() { vec.reset(); }
91};
92
93typedef std::pair<ValueVector *, ValueVector *> BVPair;
94
95namespace {
96class CFGBlockValues {
97  const CFG &cfg;
98  BVPair *vals;
99  ValueVector scratch;
100  DeclToIndex DeclToIndex;
101
102  ValueVector &lazyCreate(ValueVector *&bv);
103public:
104  CFGBlockValues(const CFG &cfg);
105  ~CFGBlockValues();
106
107  void computeSetOfDeclarations(const DeclContext &dc);
108  ValueVector &getValueVector(const CFGBlock *block,
109                                const CFGBlock *dstBlock);
110
111  BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate);
112
113  void mergeIntoScratch(ValueVector const &source, bool isFirst);
114  bool updateValueVectorWithScratch(const CFGBlock *block);
115  bool updateValueVectors(const CFGBlock *block, const BVPair &newVals);
116
117  bool hasNoDeclarations() const {
118    return DeclToIndex.size() == 0;
119  }
120
121  void resetScratch();
122  ValueVector &getScratch() { return scratch; }
123
124  ValueVector::reference operator[](const VarDecl *vd);
125};
126}
127
128CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {
129  unsigned n = cfg.getNumBlockIDs();
130  if (!n)
131    return;
132  vals = new std::pair<ValueVector*, ValueVector*>[n];
133  memset(vals, 0, sizeof(*vals) * n);
134}
135
136CFGBlockValues::~CFGBlockValues() {
137  unsigned n = cfg.getNumBlockIDs();
138  if (n == 0)
139    return;
140  for (unsigned i = 0; i < n; ++i) {
141    delete vals[i].first;
142    delete vals[i].second;
143  }
144  delete [] vals;
145}
146
147void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) {
148  DeclToIndex.computeMap(dc);
149  scratch.resize(DeclToIndex.size());
150}
151
152ValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) {
153  if (!bv)
154    bv = new ValueVector(DeclToIndex.size());
155  return *bv;
156}
157
158/// This function pattern matches for a '&&' or '||' that appears at
159/// the beginning of a CFGBlock that also (1) has a terminator and
160/// (2) has no other elements.  If such an expression is found, it is returned.
161static BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) {
162  if (block->empty())
163    return 0;
164
165  const CFGStmt *cstmt = block->front().getAs<CFGStmt>();
166  BinaryOperator *b = llvm::dyn_cast_or_null<BinaryOperator>(cstmt->getStmt());
167
168  if (!b || !b->isLogicalOp())
169    return 0;
170
171  if (block->pred_size() == 2 &&
172      ((block->succ_size() == 2 && block->getTerminatorCondition() == b) ||
173       block->size() == 1))
174    return b;
175
176  return 0;
177}
178
179ValueVector &CFGBlockValues::getValueVector(const CFGBlock *block,
180                                            const CFGBlock *dstBlock) {
181  unsigned idx = block->getBlockID();
182  if (dstBlock && getLogicalOperatorInChain(block)) {
183    if (*block->succ_begin() == dstBlock)
184      return lazyCreate(vals[idx].first);
185    assert(*(block->succ_begin()+1) == dstBlock);
186    return lazyCreate(vals[idx].second);
187  }
188
189  assert(vals[idx].second == 0);
190  return lazyCreate(vals[idx].first);
191}
192
193BVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block,
194                                        bool shouldLazyCreate) {
195  unsigned idx = block->getBlockID();
196  lazyCreate(vals[idx].first);
197  if (shouldLazyCreate)
198    lazyCreate(vals[idx].second);
199  return vals[idx];
200}
201
202void CFGBlockValues::mergeIntoScratch(ValueVector const &source,
203                                      bool isFirst) {
204  if (isFirst)
205    scratch = source;
206  else
207    scratch.merge(source);
208}
209#if 0
210static void printVector(const CFGBlock *block, ValueVector &bv,
211                        unsigned num) {
212
213  llvm::errs() << block->getBlockID() << " :";
214  for (unsigned i = 0; i < bv.size(); ++i) {
215    llvm::errs() << ' ' << bv[i];
216  }
217  llvm::errs() << " : " << num << '\n';
218}
219#endif
220
221bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) {
222  ValueVector &dst = getValueVector(block, 0);
223  bool changed = (dst != scratch);
224  if (changed)
225    dst = scratch;
226#if 0
227  printVector(block, scratch, 0);
228#endif
229  return changed;
230}
231
232bool CFGBlockValues::updateValueVectors(const CFGBlock *block,
233                                      const BVPair &newVals) {
234  BVPair &vals = getValueVectors(block, true);
235  bool changed = *newVals.first != *vals.first ||
236                 *newVals.second != *vals.second;
237  *vals.first = *newVals.first;
238  *vals.second = *newVals.second;
239#if 0
240  printVector(block, *vals.first, 1);
241  printVector(block, *vals.second, 2);
242#endif
243  return changed;
244}
245
246void CFGBlockValues::resetScratch() {
247  scratch.reset();
248}
249
250ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) {
251  const llvm::Optional<unsigned> &idx = DeclToIndex.getValueIndex(vd);
252  assert(idx.hasValue());
253  return scratch[idx.getValue()];
254}
255
256//------------------------------------------------------------------------====//
257// Worklist: worklist for dataflow analysis.
258//====------------------------------------------------------------------------//
259
260namespace {
261class DataflowWorklist {
262  llvm::SmallVector<const CFGBlock *, 20> worklist;
263  ValueVector enqueuedBlocks;
264public:
265  DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {}
266
267  void enqueue(const CFGBlock *block);
268  void enqueueSuccessors(const CFGBlock *block);
269  const CFGBlock *dequeue();
270
271};
272}
273
274void DataflowWorklist::enqueue(const CFGBlock *block) {
275  if (!block)
276    return;
277  unsigned idx = block->getBlockID();
278  if (enqueuedBlocks[idx])
279    return;
280  worklist.push_back(block);
281  enqueuedBlocks[idx] = true;
282}
283
284void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) {
285  for (CFGBlock::const_succ_iterator I = block->succ_begin(),
286       E = block->succ_end(); I != E; ++I) {
287    enqueue(*I);
288  }
289}
290
291const CFGBlock *DataflowWorklist::dequeue() {
292  if (worklist.empty())
293    return 0;
294  const CFGBlock *b = worklist.back();
295  worklist.pop_back();
296  enqueuedBlocks[b->getBlockID()] = false;
297  return b;
298}
299
300//------------------------------------------------------------------------====//
301// Transfer function for uninitialized values analysis.
302//====------------------------------------------------------------------------//
303
304namespace {
305class FindVarResult {
306  const VarDecl *vd;
307  const DeclRefExpr *dr;
308public:
309  FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {}
310
311  const DeclRefExpr *getDeclRefExpr() const { return dr; }
312  const VarDecl *getDecl() const { return vd; }
313};
314
315class TransferFunctions : public CFGRecStmtVisitor<TransferFunctions> {
316  CFGBlockValues &vals;
317  const CFG &cfg;
318  AnalysisContext &ac;
319  UninitVariablesHandler *handler;
320  const DeclRefExpr *currentDR;
321  const Expr *currentVoidCast;
322  const bool flagBlockUses;
323public:
324  TransferFunctions(CFGBlockValues &vals, const CFG &cfg,
325                    AnalysisContext &ac,
326                    UninitVariablesHandler *handler,
327                    bool flagBlockUses)
328    : vals(vals), cfg(cfg), ac(ac), handler(handler), currentDR(0),
329      currentVoidCast(0), flagBlockUses(flagBlockUses) {}
330
331  const CFG &getCFG() { return cfg; }
332  void reportUninit(const DeclRefExpr *ex, const VarDecl *vd);
333
334  void VisitBlockExpr(BlockExpr *be);
335  void VisitDeclStmt(DeclStmt *ds);
336  void VisitDeclRefExpr(DeclRefExpr *dr);
337  void VisitUnaryOperator(UnaryOperator *uo);
338  void VisitBinaryOperator(BinaryOperator *bo);
339  void VisitCastExpr(CastExpr *ce);
340  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *se);
341  void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs);
342
343  bool isTrackedVar(const VarDecl *vd) {
344    return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl()));
345  }
346
347  FindVarResult findBlockVarDecl(Expr *ex);
348};
349}
350
351void TransferFunctions::reportUninit(const DeclRefExpr *ex,
352                                     const VarDecl *vd) {
353  if (handler) handler->handleUseOfUninitVariable(ex, vd);
354}
355
356FindVarResult TransferFunctions::findBlockVarDecl(Expr* ex) {
357  if (DeclRefExpr* dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts()))
358    if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl()))
359      if (isTrackedVar(vd))
360        return FindVarResult(vd, dr);
361  return FindVarResult(0, 0);
362}
363
364void TransferFunctions::BlockStmt_VisitObjCForCollectionStmt(
365    ObjCForCollectionStmt *fs) {
366
367  Visit(fs->getCollection());
368
369  // This represents an initialization of the 'element' value.
370  Stmt *element = fs->getElement();
371  const VarDecl* vd = 0;
372
373  if (DeclStmt* ds = dyn_cast<DeclStmt>(element)) {
374    vd = cast<VarDecl>(ds->getSingleDecl());
375    if (!isTrackedVar(vd))
376      vd = 0;
377  }
378  else {
379    // Initialize the value of the reference variable.
380    const FindVarResult &res = findBlockVarDecl(cast<Expr>(element));
381    vd = res.getDecl();
382    if (!vd) {
383      Visit(element);
384      return;
385    }
386  }
387
388  if (vd)
389    vals[vd] = Initialized;
390}
391
392void TransferFunctions::VisitBlockExpr(BlockExpr *be) {
393  if (!flagBlockUses || !handler)
394    return;
395  AnalysisContext::referenced_decls_iterator i, e;
396  llvm::tie(i, e) = ac.getReferencedBlockVars(be->getBlockDecl());
397  for ( ; i != e; ++i) {
398    const VarDecl *vd = *i;
399    if (vd->getAttr<BlocksAttr>() || !vd->hasLocalStorage() ||
400        !isTrackedVar(vd))
401      continue;
402    if (vals[vd] == Uninitialized)
403      handler->handleUseOfUninitVariable(be, vd);
404  }
405}
406
407void TransferFunctions::VisitDeclStmt(DeclStmt *ds) {
408  for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end();
409       DI != DE; ++DI) {
410    if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) {
411      if (isTrackedVar(vd)) {
412        vals[vd] = Uninitialized;
413        if (Stmt *init = vd->getInit()) {
414          Visit(init);
415          vals[vd] = Initialized;
416        }
417      }
418      else if (Stmt *init = vd->getInit()) {
419        Visit(init);
420      }
421    }
422  }
423}
424
425void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) {
426  // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast
427  // cannot be block-level expressions.  Therefore, we determine if
428  // a DeclRefExpr is involved in a "load" by comparing it to the current
429  // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
430  // If a DeclRefExpr is not involved in a load, we are essentially computing
431  // its address, either for assignment to a reference or via the '&' operator.
432  // In such cases, treat the variable as being initialized, since this
433  // analysis isn't powerful enough to do alias tracking.
434  if (dr != currentDR)
435    if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl()))
436      if (isTrackedVar(vd))
437        vals[vd] = Initialized;
438}
439
440void TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) {
441  if (bo->isAssignmentOp()) {
442    const FindVarResult &res = findBlockVarDecl(bo->getLHS());
443    if (const VarDecl* vd = res.getDecl()) {
444      // We assume that DeclRefExprs wrapped in a BinaryOperator "assignment"
445      // cannot be block-level expressions.  Therefore, we determine if
446      // a DeclRefExpr is involved in a "load" by comparing it to the current
447      // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
448      SaveAndRestore<const DeclRefExpr*> lastDR(currentDR,
449                                                res.getDeclRefExpr());
450      Visit(bo->getRHS());
451      Visit(bo->getLHS());
452
453      ValueVector::reference bit = vals[vd];
454      if (bit == Uninitialized) {
455        if (bo->getOpcode() != BO_Assign)
456          reportUninit(res.getDeclRefExpr(), vd);
457        bit = Initialized;
458      }
459      return;
460    }
461  }
462  Visit(bo->getRHS());
463  Visit(bo->getLHS());
464}
465
466void TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) {
467  switch (uo->getOpcode()) {
468    case clang::UO_PostDec:
469    case clang::UO_PostInc:
470    case clang::UO_PreDec:
471    case clang::UO_PreInc: {
472      const FindVarResult &res = findBlockVarDecl(uo->getSubExpr());
473      if (const VarDecl *vd = res.getDecl()) {
474        // We assume that DeclRefExprs wrapped in a unary operator ++/--
475        // cannot be block-level expressions.  Therefore, we determine if
476        // a DeclRefExpr is involved in a "load" by comparing it to the current
477        // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
478        SaveAndRestore<const DeclRefExpr*> lastDR(currentDR,
479                                                  res.getDeclRefExpr());
480        Visit(uo->getSubExpr());
481
482        ValueVector::reference bit = vals[vd];
483        if (bit == Uninitialized) {
484          reportUninit(res.getDeclRefExpr(), vd);
485          bit = Initialized;
486        }
487        return;
488      }
489      break;
490    }
491    default:
492      break;
493  }
494  Visit(uo->getSubExpr());
495}
496
497void TransferFunctions::VisitCastExpr(clang::CastExpr *ce) {
498  if (ce->getCastKind() == CK_LValueToRValue) {
499    const FindVarResult &res = findBlockVarDecl(ce->getSubExpr());
500    if (const VarDecl *vd = res.getDecl()) {
501      // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast
502      // cannot be block-level expressions.  Therefore, we determine if
503      // a DeclRefExpr is involved in a "load" by comparing it to the current
504      // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
505      // Here we update 'currentDR' to be the one associated with this
506      // lvalue-to-rvalue cast.  Then, when we analyze the DeclRefExpr, we
507      // will know that we are not computing its lvalue for other purposes
508      // than to perform a load.
509      SaveAndRestore<const DeclRefExpr*> lastDR(currentDR,
510                                                res.getDeclRefExpr());
511      Visit(ce->getSubExpr());
512      if (currentVoidCast != ce && vals[vd] == Uninitialized) {
513        reportUninit(res.getDeclRefExpr(), vd);
514        // Don't cascade warnings.
515        vals[vd] = Initialized;
516      }
517      return;
518    }
519  }
520  else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) {
521    if (cse->getType()->isVoidType()) {
522      // e.g. (void) x;
523      SaveAndRestore<const Expr *>
524        lastVoidCast(currentVoidCast, cse->getSubExpr()->IgnoreParens());
525      Visit(cse->getSubExpr());
526      return;
527    }
528  }
529  Visit(ce->getSubExpr());
530}
531
532void TransferFunctions::VisitUnaryExprOrTypeTraitExpr(
533                                          UnaryExprOrTypeTraitExpr *se) {
534  if (se->getKind() == UETT_SizeOf) {
535    if (se->getType()->isConstantSizeType())
536      return;
537    // Handle VLAs.
538    Visit(se->getArgumentExpr());
539  }
540}
541
542//------------------------------------------------------------------------====//
543// High-level "driver" logic for uninitialized values analysis.
544//====------------------------------------------------------------------------//
545
546static bool runOnBlock(const CFGBlock *block, const CFG &cfg,
547                       AnalysisContext &ac, CFGBlockValues &vals,
548                       UninitVariablesHandler *handler = 0,
549                       bool flagBlockUses = false) {
550
551  if (const BinaryOperator *b = getLogicalOperatorInChain(block)) {
552    CFGBlock::const_pred_iterator itr = block->pred_begin();
553    BVPair vA = vals.getValueVectors(*itr, false);
554    ++itr;
555    BVPair vB = vals.getValueVectors(*itr, false);
556
557    BVPair valsAB;
558
559    if (b->getOpcode() == BO_LAnd) {
560      // Merge the 'F' bits from the first and second.
561      vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true);
562      vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false);
563      valsAB.first = vA.first;
564      valsAB.second = &vals.getScratch();
565    }
566    else {
567      // Merge the 'T' bits from the first and second.
568      assert(b->getOpcode() == BO_LOr);
569      vals.mergeIntoScratch(*vA.first, true);
570      vals.mergeIntoScratch(*vB.first, false);
571      valsAB.first = &vals.getScratch();
572      valsAB.second = vA.second ? vA.second : vA.first;
573    }
574    return vals.updateValueVectors(block, valsAB);
575  }
576
577  // Default behavior: merge in values of predecessor blocks.
578  vals.resetScratch();
579  bool isFirst = true;
580  for (CFGBlock::const_pred_iterator I = block->pred_begin(),
581       E = block->pred_end(); I != E; ++I) {
582    vals.mergeIntoScratch(vals.getValueVector(*I, block), isFirst);
583    isFirst = false;
584  }
585  // Apply the transfer function.
586  TransferFunctions tf(vals, cfg, ac, handler, flagBlockUses);
587  for (CFGBlock::const_iterator I = block->begin(), E = block->end();
588       I != E; ++I) {
589    if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) {
590      tf.BlockStmt_Visit(cs->getStmt());
591    }
592  }
593  return vals.updateValueVectorWithScratch(block);
594}
595
596void clang::runUninitializedVariablesAnalysis(const DeclContext &dc,
597                                              const CFG &cfg,
598                                              AnalysisContext &ac,
599                                              UninitVariablesHandler &handler) {
600  CFGBlockValues vals(cfg);
601  vals.computeSetOfDeclarations(dc);
602  if (vals.hasNoDeclarations())
603    return;
604  DataflowWorklist worklist(cfg);
605  ValueVector previouslyVisited(cfg.getNumBlockIDs());
606
607  worklist.enqueueSuccessors(&cfg.getEntry());
608
609  while (const CFGBlock *block = worklist.dequeue()) {
610    // Did the block change?
611    bool changed = runOnBlock(block, cfg, ac, vals);
612    if (changed || !previouslyVisited[block->getBlockID()])
613      worklist.enqueueSuccessors(block);
614    previouslyVisited[block->getBlockID()] = true;
615  }
616
617  // Run through the blocks one more time, and report uninitialized variabes.
618  for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) {
619    runOnBlock(*BI, cfg, ac, vals, &handler, /* flagBlockUses */ true);
620  }
621}
622
623UninitVariablesHandler::~UninitVariablesHandler() {}
624
625