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