Coverage Report

Created: 2020-02-25 14:32

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