Coverage Report

Created: 2019-07-24 05:18

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