1//===- CFG.cpp - Classes for representing and building CFGs ---------------===//
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 defines the CFG and CFGBuilder classes for representing and
10// building Control-Flow Graphs (CFGs) from ASTs.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Analysis/CFG.h"
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/Attr.h"
17#include "clang/AST/Decl.h"
18#include "clang/AST/DeclBase.h"
19#include "clang/AST/DeclCXX.h"
20#include "clang/AST/DeclGroup.h"
21#include "clang/AST/Expr.h"
22#include "clang/AST/ExprCXX.h"
23#include "clang/AST/OperationKinds.h"
24#include "clang/AST/PrettyPrinter.h"
25#include "clang/AST/Stmt.h"
26#include "clang/AST/StmtCXX.h"
27#include "clang/AST/StmtObjC.h"
28#include "clang/AST/StmtVisitor.h"
29#include "clang/AST/Type.h"
30#include "clang/Analysis/ConstructionContext.h"
31#include "clang/Analysis/Support/BumpVector.h"
32#include "clang/Basic/Builtins.h"
33#include "clang/Basic/ExceptionSpecificationType.h"
34#include "clang/Basic/JsonSupport.h"
35#include "clang/Basic/LLVM.h"
36#include "clang/Basic/LangOptions.h"
37#include "clang/Basic/SourceLocation.h"
38#include "clang/Basic/Specifiers.h"
39#include "llvm/ADT/APFloat.h"
40#include "llvm/ADT/APInt.h"
41#include "llvm/ADT/APSInt.h"
42#include "llvm/ADT/ArrayRef.h"
43#include "llvm/ADT/DenseMap.h"
44#include "llvm/ADT/STLExtras.h"
45#include "llvm/ADT/SetVector.h"
46#include "llvm/ADT/SmallPtrSet.h"
47#include "llvm/ADT/SmallVector.h"
48#include "llvm/Support/Allocator.h"
49#include "llvm/Support/Compiler.h"
50#include "llvm/Support/DOTGraphTraits.h"
51#include "llvm/Support/ErrorHandling.h"
52#include "llvm/Support/Format.h"
53#include "llvm/Support/GraphWriter.h"
54#include "llvm/Support/SaveAndRestore.h"
55#include "llvm/Support/TimeProfiler.h"
56#include "llvm/Support/raw_ostream.h"
57#include <algorithm>
58#include <cassert>
59#include <cstddef>
60#include <memory>
61#include <optional>
62#include <string>
63#include <tuple>
64#include <utility>
65#include <vector>
66
67using namespace clang;
68
69static SourceLocation GetEndLoc(Decl *D) {
70 if (VarDecl *VD = dyn_cast<VarDecl>(Val: D))
71 if (Expr *Ex = VD->getInit())
72 return Ex->getSourceRange().getEnd();
73 return D->getLocation();
74}
75
76/// Returns true on constant values based around a single IntegerLiteral,
77/// CharacterLiteral, or FloatingLiteral. Allow for use of parentheses, integer
78/// casts, and negative signs.
79
80static bool IsLiteralConstantExpr(const Expr *E) {
81 // Allow parentheses
82 E = E->IgnoreParens();
83
84 // Allow conversions to different integer kind, and integer to floating point
85 // (to account for float comparing with int).
86 if (const auto *CE = dyn_cast<CastExpr>(Val: E)) {
87 if (CE->getCastKind() != CK_IntegralCast &&
88 CE->getCastKind() != CK_IntegralToFloating)
89 return false;
90 E = CE->getSubExpr();
91 }
92
93 // Allow negative numbers.
94 if (const auto *UO = dyn_cast<UnaryOperator>(Val: E)) {
95 if (UO->getOpcode() != UO_Minus)
96 return false;
97 E = UO->getSubExpr();
98 }
99 return isa<IntegerLiteral, CharacterLiteral, FloatingLiteral>(Val: E);
100}
101
102/// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral
103/// FloatingLiteral, CharacterLiteral or EnumConstantDecl from the given Expr.
104/// If it fails, returns nullptr.
105static const Expr *tryTransformToLiteralConstant(const Expr *E) {
106 E = E->IgnoreParens();
107 if (IsLiteralConstantExpr(E))
108 return E;
109 if (auto *DR = dyn_cast<DeclRefExpr>(Val: E->IgnoreParenImpCasts()))
110 return isa<EnumConstantDecl>(Val: DR->getDecl()) ? DR : nullptr;
111 return nullptr;
112}
113
114/// Tries to interpret a binary operator into `Expr Op NumExpr` form, if
115/// NumExpr is an integer literal or an enum constant.
116///
117/// If this fails, at least one of the returned DeclRefExpr or Expr will be
118/// null.
119static std::tuple<const Expr *, BinaryOperatorKind, const Expr *>
120tryNormalizeBinaryOperator(const BinaryOperator *B) {
121 BinaryOperatorKind Op = B->getOpcode();
122
123 const Expr *MaybeDecl = B->getLHS();
124 const Expr *Constant = tryTransformToLiteralConstant(E: B->getRHS());
125 // Expr looked like `0 == Foo` instead of `Foo == 0`
126 if (Constant == nullptr) {
127 // Flip the operator
128 if (Op == BO_GT)
129 Op = BO_LT;
130 else if (Op == BO_GE)
131 Op = BO_LE;
132 else if (Op == BO_LT)
133 Op = BO_GT;
134 else if (Op == BO_LE)
135 Op = BO_GE;
136
137 MaybeDecl = B->getRHS();
138 Constant = tryTransformToLiteralConstant(E: B->getLHS());
139 }
140
141 return std::make_tuple(args&: MaybeDecl, args&: Op, args&: Constant);
142}
143
144/// For an expression `x == Foo && x == Bar`, this determines whether the
145/// `Foo` and `Bar` are either of the same enumeration type, or both integer
146/// literals.
147///
148/// It's an error to pass this arguments that are not either IntegerLiterals
149/// or DeclRefExprs (that have decls of type EnumConstantDecl)
150static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) {
151 // User intent isn't clear if they're mixing int literals with enum
152 // constants.
153 if (isa<DeclRefExpr>(Val: E1) != isa<DeclRefExpr>(Val: E2))
154 return false;
155
156 // Integer literal comparisons, regardless of literal type, are acceptable.
157 if (!isa<DeclRefExpr>(Val: E1))
158 return true;
159
160 // IntegerLiterals are handled above and only EnumConstantDecls are expected
161 // beyond this point
162 assert(isa<DeclRefExpr>(E1) && isa<DeclRefExpr>(E2));
163 auto *Decl1 = cast<DeclRefExpr>(Val: E1)->getDecl();
164 auto *Decl2 = cast<DeclRefExpr>(Val: E2)->getDecl();
165
166 assert(isa<EnumConstantDecl>(Decl1) && isa<EnumConstantDecl>(Decl2));
167 const DeclContext *DC1 = Decl1->getDeclContext();
168 const DeclContext *DC2 = Decl2->getDeclContext();
169
170 assert(isa<EnumDecl>(DC1) && isa<EnumDecl>(DC2));
171 return DC1 == DC2;
172}
173
174namespace {
175
176class CFGBuilder;
177
178/// The CFG builder uses a recursive algorithm to build the CFG. When
179/// we process an expression, sometimes we know that we must add the
180/// subexpressions as block-level expressions. For example:
181///
182/// exp1 || exp2
183///
184/// When processing the '||' expression, we know that exp1 and exp2
185/// need to be added as block-level expressions, even though they
186/// might not normally need to be. AddStmtChoice records this
187/// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then
188/// the builder has an option not to add a subexpression as a
189/// block-level expression.
190class AddStmtChoice {
191public:
192 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };
193
194 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}
195
196 bool alwaysAdd(CFGBuilder &builder,
197 const Stmt *stmt) const;
198
199 /// Return a copy of this object, except with the 'always-add' bit
200 /// set as specified.
201 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {
202 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd);
203 }
204
205private:
206 Kind kind;
207};
208
209/// LocalScope - Node in tree of local scopes created for C++ implicit
210/// destructor calls generation. It contains list of automatic variables
211/// declared in the scope and link to position in previous scope this scope
212/// began in.
213///
214/// The process of creating local scopes is as follows:
215/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
216/// - Before processing statements in scope (e.g. CompoundStmt) create
217/// LocalScope object using CFGBuilder::ScopePos as link to previous scope
218/// and set CFGBuilder::ScopePos to the end of new scope,
219/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
220/// at this VarDecl,
221/// - For every normal (without jump) end of scope add to CFGBlock destructors
222/// for objects in the current scope,
223/// - For every jump add to CFGBlock destructors for objects
224/// between CFGBuilder::ScopePos and local scope position saved for jump
225/// target. Thanks to C++ restrictions on goto jumps we can be sure that
226/// jump target position will be on the path to root from CFGBuilder::ScopePos
227/// (adding any variable that doesn't need constructor to be called to
228/// LocalScope can break this assumption),
229///
230class LocalScope {
231public:
232 using AutomaticVarsTy = BumpVector<VarDecl *>;
233
234 /// const_iterator - Iterates local scope backwards and jumps to previous
235 /// scope on reaching the beginning of currently iterated scope.
236 class const_iterator {
237 const LocalScope* Scope = nullptr;
238
239 /// VarIter is guaranteed to be greater then 0 for every valid iterator.
240 /// Invalid iterator (with null Scope) has VarIter equal to 0.
241 unsigned VarIter = 0;
242
243 public:
244 /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
245 /// Incrementing invalid iterator is allowed and will result in invalid
246 /// iterator.
247 const_iterator() = default;
248
249 /// Create valid iterator. In case when S.Prev is an invalid iterator and
250 /// I is equal to 0, this will create invalid iterator.
251 const_iterator(const LocalScope& S, unsigned I)
252 : Scope(&S), VarIter(I) {
253 // Iterator to "end" of scope is not allowed. Handle it by going up
254 // in scopes tree possibly up to invalid iterator in the root.
255 if (VarIter == 0 && Scope)
256 *this = Scope->Prev;
257 }
258
259 VarDecl *const* operator->() const {
260 assert(Scope && "Dereferencing invalid iterator is not allowed");
261 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
262 return &Scope->Vars[VarIter - 1];
263 }
264
265 const VarDecl *getFirstVarInScope() const {
266 assert(Scope && "Dereferencing invalid iterator is not allowed");
267 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
268 return Scope->Vars[0];
269 }
270
271 VarDecl *operator*() const {
272 return *this->operator->();
273 }
274
275 const_iterator &operator++() {
276 if (!Scope)
277 return *this;
278
279 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
280 --VarIter;
281 if (VarIter == 0)
282 *this = Scope->Prev;
283 return *this;
284 }
285 const_iterator operator++(int) {
286 const_iterator P = *this;
287 ++*this;
288 return P;
289 }
290
291 bool operator==(const const_iterator &rhs) const {
292 return Scope == rhs.Scope && VarIter == rhs.VarIter;
293 }
294 bool operator!=(const const_iterator &rhs) const {
295 return !(*this == rhs);
296 }
297
298 explicit operator bool() const {
299 return *this != const_iterator();
300 }
301
302 int distance(const_iterator L);
303 const_iterator shared_parent(const_iterator L);
304 bool pointsToFirstDeclaredVar() { return VarIter == 1; }
305 bool inSameLocalScope(const_iterator rhs) { return Scope == rhs.Scope; }
306 };
307
308private:
309 BumpVectorContext ctx;
310
311 /// Automatic variables in order of declaration.
312 AutomaticVarsTy Vars;
313
314 /// Iterator to variable in previous scope that was declared just before
315 /// begin of this scope.
316 const_iterator Prev;
317
318public:
319 /// Constructs empty scope linked to previous scope in specified place.
320 LocalScope(BumpVectorContext ctx, const_iterator P)
321 : ctx(std::move(ctx)), Vars(this->ctx, 4), Prev(P) {}
322
323 /// Begin of scope in direction of CFG building (backwards).
324 const_iterator begin() const { return const_iterator(*this, Vars.size()); }
325
326 void addVar(VarDecl *VD) {
327 Vars.push_back(Elt: VD, C&: ctx);
328 }
329};
330
331} // namespace
332
333/// distance - Calculates distance from this to L. L must be reachable from this
334/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
335/// number of scopes between this and L.
336int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
337 int D = 0;
338 const_iterator F = *this;
339 while (F.Scope != L.Scope) {
340 assert(F != const_iterator() &&
341 "L iterator is not reachable from F iterator.");
342 D += F.VarIter;
343 F = F.Scope->Prev;
344 }
345 D += F.VarIter - L.VarIter;
346 return D;
347}
348
349/// Calculates the closest parent of this iterator
350/// that is in a scope reachable through the parents of L.
351/// I.e. when using 'goto' from this to L, the lifetime of all variables
352/// between this and shared_parent(L) end.
353LocalScope::const_iterator
354LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) {
355 // one of iterators is not valid (we are not in scope), so common
356 // parent is const_iterator() (i.e. sentinel).
357 if ((*this == const_iterator()) || (L == const_iterator())) {
358 return const_iterator();
359 }
360
361 const_iterator F = *this;
362 if (F.inSameLocalScope(rhs: L)) {
363 // Iterators are in the same scope, get common subset of variables.
364 F.VarIter = std::min(a: F.VarIter, b: L.VarIter);
365 return F;
366 }
367
368 llvm::SmallDenseMap<const LocalScope *, unsigned, 4> ScopesOfL;
369 while (true) {
370 ScopesOfL.try_emplace(Key: L.Scope, Args&: L.VarIter);
371 if (L == const_iterator())
372 break;
373 L = L.Scope->Prev;
374 }
375
376 while (true) {
377 if (auto LIt = ScopesOfL.find(Val: F.Scope); LIt != ScopesOfL.end()) {
378 // Get common subset of variables in given scope
379 F.VarIter = std::min(a: F.VarIter, b: LIt->getSecond());
380 return F;
381 }
382 assert(F != const_iterator() &&
383 "L iterator is not reachable from F iterator.");
384 F = F.Scope->Prev;
385 }
386}
387
388namespace {
389
390/// Structure for specifying position in CFG during its build process. It
391/// consists of CFGBlock that specifies position in CFG and
392/// LocalScope::const_iterator that specifies position in LocalScope graph.
393struct BlockScopePosPair {
394 CFGBlock *block = nullptr;
395 LocalScope::const_iterator scopePosition;
396
397 BlockScopePosPair() = default;
398 BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos)
399 : block(b), scopePosition(scopePos) {}
400};
401
402/// TryResult - a class representing a variant over the values
403/// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool,
404/// and is used by the CFGBuilder to decide if a branch condition
405/// can be decided up front during CFG construction.
406class TryResult {
407 int X = -1;
408
409public:
410 TryResult() = default;
411 TryResult(bool b) : X(b ? 1 : 0) {}
412
413 bool isTrue() const { return X == 1; }
414 bool isFalse() const { return X == 0; }
415 bool isKnown() const { return X >= 0; }
416
417 void negate() {
418 assert(isKnown());
419 X ^= 0x1;
420 }
421};
422
423} // namespace
424
425static TryResult bothKnownTrue(TryResult R1, TryResult R2) {
426 if (!R1.isKnown() || !R2.isKnown())
427 return TryResult();
428 return TryResult(R1.isTrue() && R2.isTrue());
429}
430
431namespace {
432
433class reverse_children {
434 llvm::SmallVector<Stmt *, 12> childrenBuf;
435 ArrayRef<Stmt *> children;
436
437public:
438 reverse_children(Stmt *S, ASTContext &Ctx);
439
440 using iterator = ArrayRef<Stmt *>::reverse_iterator;
441
442 iterator begin() const { return children.rbegin(); }
443 iterator end() const { return children.rend(); }
444};
445
446} // namespace
447
448reverse_children::reverse_children(Stmt *S, ASTContext &Ctx) {
449 if (CallExpr *CE = dyn_cast<CallExpr>(Val: S)) {
450 children = CE->getRawSubExprs();
451 return;
452 }
453
454 switch (S->getStmtClass()) {
455 // Note: Fill in this switch with more cases we want to optimize.
456 case Stmt::InitListExprClass: {
457 InitListExpr *IE = cast<InitListExpr>(Val: S);
458 children = llvm::ArrayRef(reinterpret_cast<Stmt **>(IE->getInits()),
459 IE->getNumInits());
460 return;
461 }
462
463 case Stmt::AttributedStmtClass: {
464 // For an attributed stmt, the "children()" returns only the NullStmt
465 // (;) but semantically the "children" are supposed to be the
466 // expressions _within_ i.e. the two square brackets i.e. [[ HERE ]]
467 // so we add the subexpressions first, _then_ add the "children"
468 auto *AS = cast<AttributedStmt>(Val: S);
469 for (const auto *Attr : AS->getAttrs()) {
470 if (const auto *AssumeAttr = dyn_cast<CXXAssumeAttr>(Val: Attr)) {
471 Expr *AssumeExpr = AssumeAttr->getAssumption();
472 if (!AssumeExpr->HasSideEffects(Ctx)) {
473 childrenBuf.push_back(Elt: AssumeExpr);
474 }
475 }
476 }
477
478 // Visit the actual children AST nodes.
479 // For CXXAssumeAttrs, this is always a NullStmt.
480 llvm::append_range(C&: childrenBuf, R: AS->children());
481 children = childrenBuf;
482 return;
483 }
484 default:
485 break;
486 }
487
488 // Default case for all other statements.
489 llvm::append_range(C&: childrenBuf, R: S->children());
490
491 // This needs to be done *after* childrenBuf has been populated.
492 children = childrenBuf;
493}
494
495namespace {
496
497/// CFGBuilder - This class implements CFG construction from an AST.
498/// The builder is stateful: an instance of the builder should be used to only
499/// construct a single CFG.
500///
501/// Example usage:
502///
503/// CFGBuilder builder;
504/// std::unique_ptr<CFG> cfg = builder.buildCFG(decl, stmt1);
505///
506/// CFG construction is done via a recursive walk of an AST. We actually parse
507/// the AST in reverse order so that the successor of a basic block is
508/// constructed prior to its predecessor. This allows us to nicely capture
509/// implicit fall-throughs without extra basic blocks.
510class CFGBuilder {
511 using JumpTarget = BlockScopePosPair;
512 using JumpSource = BlockScopePosPair;
513
514 ASTContext *Context;
515 std::unique_ptr<CFG> cfg;
516
517 // Current block.
518 CFGBlock *Block = nullptr;
519
520 // Block after the current block.
521 CFGBlock *Succ = nullptr;
522
523 JumpTarget ContinueJumpTarget;
524 JumpTarget BreakJumpTarget;
525 JumpTarget SEHLeaveJumpTarget;
526 CFGBlock *SwitchTerminatedBlock = nullptr;
527 CFGBlock *DefaultCaseBlock = nullptr;
528
529 // This can point to either a C++ try, an Objective-C @try, or an SEH __try.
530 // try and @try can be mixed and generally work the same.
531 // The frontend forbids mixing SEH __try with either try or @try.
532 // So having one for all three is enough.
533 CFGBlock *TryTerminatedBlock = nullptr;
534
535 // Current position in local scope.
536 LocalScope::const_iterator ScopePos;
537
538 // LabelMap records the mapping from Label expressions to their jump targets.
539 using LabelMapTy = llvm::DenseMap<LabelDecl *, JumpTarget>;
540 LabelMapTy LabelMap;
541
542 // A list of blocks that end with a "goto" that must be backpatched to their
543 // resolved targets upon completion of CFG construction.
544 using BackpatchBlocksTy = std::vector<JumpSource>;
545 BackpatchBlocksTy BackpatchBlocks;
546
547 // A list of labels whose address has been taken (for indirect gotos).
548 using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>;
549 LabelSetTy AddressTakenLabels;
550
551 // Information about the currently visited C++ object construction site.
552 // This is set in the construction trigger and read when the constructor
553 // or a function that returns an object by value is being visited.
554 llvm::DenseMap<Expr *, const ConstructionContextLayer *>
555 ConstructionContextMap;
556
557 bool badCFG = false;
558 const CFG::BuildOptions &BuildOpts;
559
560 // State to track for building switch statements.
561 bool switchExclusivelyCovered = false;
562 Expr::EvalResult *switchCond = nullptr;
563
564 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr;
565 const Stmt *lastLookup = nullptr;
566
567 // Caches boolean evaluations of expressions to avoid multiple re-evaluations
568 // during construction of branches for chained logical operators.
569 using CachedBoolEvalsTy = llvm::DenseMap<Expr *, TryResult>;
570 CachedBoolEvalsTy CachedBoolEvals;
571
572public:
573 explicit CFGBuilder(ASTContext *astContext,
574 const CFG::BuildOptions &buildOpts)
575 : Context(astContext), cfg(new CFG()), BuildOpts(buildOpts) {}
576
577 // buildCFG - Used by external clients to construct the CFG.
578 std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement);
579
580 bool alwaysAdd(const Stmt *stmt);
581
582private:
583 // Visitors to walk an AST and construct the CFG.
584 CFGBlock *VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc);
585 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
586 CFGBlock *VisitAttributedStmt(AttributedStmt *A, AddStmtChoice asc);
587 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);
588 CFGBlock *VisitBreakStmt(BreakStmt *B);
589 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);
590 CFGBlock *VisitCaseStmt(CaseStmt *C);
591 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);
592 CFGBlock *VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed);
593 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,
594 AddStmtChoice asc);
595 CFGBlock *VisitContinueStmt(ContinueStmt *C);
596 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
597 AddStmtChoice asc);
598 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
599 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
600 CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc);
601 CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc);
602 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
603 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
604 AddStmtChoice asc);
605 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
606 AddStmtChoice asc);
607 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);
608 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);
609 CFGBlock *VisitCXXTypeidExpr(CXXTypeidExpr *S, AddStmtChoice asc);
610 CFGBlock *VisitDeclStmt(DeclStmt *DS);
611 CFGBlock *VisitDeclSubExpr(DeclStmt *DS);
612 CFGBlock *VisitDefaultStmt(DefaultStmt *D);
613 CFGBlock *VisitDoStmt(DoStmt *D);
614 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E,
615 AddStmtChoice asc, bool ExternallyDestructed);
616 CFGBlock *VisitForStmt(ForStmt *F);
617 CFGBlock *VisitGotoStmt(GotoStmt *G);
618 CFGBlock *VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc);
619 CFGBlock *VisitIfStmt(IfStmt *I);
620 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);
621 CFGBlock *VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc);
622 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);
623 CFGBlock *VisitLabelStmt(LabelStmt *L);
624 CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc);
625 CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc);
626 CFGBlock *VisitLogicalOperator(BinaryOperator *B);
627 std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B,
628 Stmt *Term,
629 CFGBlock *TrueBlock,
630 CFGBlock *FalseBlock);
631 CFGBlock *VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
632 AddStmtChoice asc);
633 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);
634 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);
635 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
636 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
637 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);
638 CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S);
639 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);
640 CFGBlock *VisitObjCMessageExpr(ObjCMessageExpr *E, AddStmtChoice asc);
641 CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E);
642 CFGBlock *VisitReturnStmt(Stmt *S);
643 CFGBlock *VisitCoroutineSuspendExpr(CoroutineSuspendExpr *S,
644 AddStmtChoice asc);
645 CFGBlock *VisitSEHExceptStmt(SEHExceptStmt *S);
646 CFGBlock *VisitSEHFinallyStmt(SEHFinallyStmt *S);
647 CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S);
648 CFGBlock *VisitSEHTryStmt(SEHTryStmt *S);
649 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
650 CFGBlock *VisitSwitchStmt(SwitchStmt *S);
651 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
652 AddStmtChoice asc);
653 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
654 CFGBlock *VisitWhileStmt(WhileStmt *W);
655 CFGBlock *VisitArrayInitLoopExpr(ArrayInitLoopExpr *A, AddStmtChoice asc);
656
657 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd,
658 bool ExternallyDestructed = false);
659 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
660 CFGBlock *VisitChildren(Stmt *S);
661 CFGBlock *VisitCallExprChildren(CallExpr *C);
662 CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc);
663 CFGBlock *VisitOMPExecutableDirective(OMPExecutableDirective *D,
664 AddStmtChoice asc);
665
666 void maybeAddScopeBeginForVarDecl(CFGBlock *B, const VarDecl *VD,
667 const Stmt *S) {
668 if (ScopePos && (VD == ScopePos.getFirstVarInScope()))
669 appendScopeBegin(B, VD, S);
670 }
671
672 /// When creating the CFG for temporary destructors, we want to mirror the
673 /// branch structure of the corresponding constructor calls.
674 /// Thus, while visiting a statement for temporary destructors, we keep a
675 /// context to keep track of the following information:
676 /// - whether a subexpression is executed unconditionally
677 /// - if a subexpression is executed conditionally, the first
678 /// CXXBindTemporaryExpr we encounter in that subexpression (which
679 /// corresponds to the last temporary destructor we have to call for this
680 /// subexpression) and the CFG block at that point (which will become the
681 /// successor block when inserting the decision point).
682 ///
683 /// That way, we can build the branch structure for temporary destructors as
684 /// follows:
685 /// 1. If a subexpression is executed unconditionally, we add the temporary
686 /// destructor calls to the current block.
687 /// 2. If a subexpression is executed conditionally, when we encounter a
688 /// CXXBindTemporaryExpr:
689 /// a) If it is the first temporary destructor call in the subexpression,
690 /// we remember the CXXBindTemporaryExpr and the current block in the
691 /// TempDtorContext; we start a new block, and insert the temporary
692 /// destructor call.
693 /// b) Otherwise, add the temporary destructor call to the current block.
694 /// 3. When we finished visiting a conditionally executed subexpression,
695 /// and we found at least one temporary constructor during the visitation
696 /// (2.a has executed), we insert a decision block that uses the
697 /// CXXBindTemporaryExpr as terminator, and branches to the current block
698 /// if the CXXBindTemporaryExpr was marked executed, and otherwise
699 /// branches to the stored successor.
700 struct TempDtorContext {
701 TempDtorContext() = default;
702 TempDtorContext(TryResult KnownExecuted)
703 : IsConditional(true), KnownExecuted(KnownExecuted) {}
704 /// Returns whether we need to start a new branch for a temporary destructor
705 /// call. This is the case when the temporary destructor is
706 /// conditionally executed, and it is the first one we encounter while
707 /// visiting a subexpression - other temporary destructors at the same level
708 /// will be added to the same block and are executed under the same
709 /// condition.
710 bool needsTempDtorBranch() const {
711 return IsConditional && !TerminatorExpr;
712 }
713
714 /// Remember the successor S of a temporary destructor decision branch for
715 /// the corresponding CXXBindTemporaryExpr E.
716 void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) {
717 Succ = S;
718 TerminatorExpr = E;
719 }
720
721 void track(const MaterializeTemporaryExpr *MTE) {
722 CollectedMTEs.push_back(Elt: MTE);
723 }
724
725 const bool IsConditional = false;
726 SmallVector<const MaterializeTemporaryExpr *, 5> CollectedMTEs;
727 const TryResult KnownExecuted = true;
728 CFGBlock *Succ = nullptr;
729 CXXBindTemporaryExpr *TerminatorExpr = nullptr;
730 };
731
732 // Visitors to walk an AST and generate destructors of temporaries in
733 // full expression.
734 CFGBlock *VisitForTemporaries(Stmt *E, bool ExternallyDestructed,
735 TempDtorContext &Context);
736 CFGBlock *VisitChildrenForTemporaries(Stmt *E, bool ExternallyDestructed,
737 TempDtorContext &Context);
738 CFGBlock *VisitBinaryOperatorForTemporaries(BinaryOperator *E,
739 bool ExternallyDestructed,
740 TempDtorContext &Context);
741 CFGBlock *VisitCXXOperatorCallExprForTemporaryDtors(CXXOperatorCallExpr *E,
742 TempDtorContext &Context);
743 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(
744 CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context);
745 CFGBlock *
746 VisitConditionalOperatorForTemporaries(AbstractConditionalOperator *E,
747 bool ExternallyDestructed,
748 TempDtorContext &Context);
749 void InsertTempDecisionBlock(const TempDtorContext &Context,
750 CFGBlock *FalseSucc = nullptr);
751
752 // NYS == Not Yet Supported
753 CFGBlock *NYS() {
754 badCFG = true;
755 return Block;
756 }
757
758 // Remember to apply the construction context based on the current \p Layer
759 // when constructing the CFG element for \p CE.
760 void consumeConstructionContext(const ConstructionContextLayer *Layer,
761 Expr *E);
762
763 // Scan \p Child statement to find constructors in it, while keeping in mind
764 // that its parent statement is providing a partial construction context
765 // described by \p Layer. If a constructor is found, it would be assigned
766 // the context based on the layer. If an additional construction context layer
767 // is found, the function recurses into that.
768 void findConstructionContexts(const ConstructionContextLayer *Layer,
769 Stmt *Child);
770
771 // Scan all arguments of a call expression for a construction context.
772 // These sorts of call expressions don't have a common superclass,
773 // hence strict duck-typing.
774 template <typename CallLikeExpr,
775 typename = std::enable_if_t<
776 std::is_base_of_v<CallExpr, CallLikeExpr> ||
777 std::is_base_of_v<CXXConstructExpr, CallLikeExpr> ||
778 std::is_base_of_v<ObjCMessageExpr, CallLikeExpr>>>
779 void findConstructionContextsForArguments(CallLikeExpr *E) {
780 for (unsigned i = 0, e = E->getNumArgs(); i != e; ++i) {
781 Expr *Arg = E->getArg(i);
782 if (Arg->getType()->getAsCXXRecordDecl() && !Arg->isGLValue())
783 findConstructionContexts(
784 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(),
785 Item: ConstructionContextItem(E, i)),
786 Child: Arg);
787 }
788 }
789
790 // Unset the construction context after consuming it. This is done immediately
791 // after adding the CFGConstructor or CFGCXXRecordTypedCall element, so
792 // there's no need to do this manually in every Visit... function.
793 void cleanupConstructionContext(Expr *E);
794
795 void autoCreateBlock() { if (!Block) Block = createBlock(); }
796
797 CFGBlock *createBlock(bool add_successor = true);
798 CFGBlock *createNoReturnBlock(bool AnalyzerOnly = false);
799
800 CFGBlock *addStmt(Stmt *S) {
801 return Visit(S, asc: AddStmtChoice::AlwaysAdd);
802 }
803
804 CFGBlock *addInitializer(CXXCtorInitializer *I);
805 void addLoopExit(const Stmt *LoopStmt);
806 void addAutomaticObjHandling(LocalScope::const_iterator B,
807 LocalScope::const_iterator E, Stmt *S);
808 void addAutomaticObjDestruction(LocalScope::const_iterator B,
809 LocalScope::const_iterator E, Stmt *S);
810 void addScopeExitHandling(LocalScope::const_iterator B,
811 LocalScope::const_iterator E, Stmt *S);
812 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
813 void addScopeChangesHandling(LocalScope::const_iterator SrcPos,
814 LocalScope::const_iterator DstPos,
815 Stmt *S);
816 void addFullExprCleanupMarker(TempDtorContext &Context,
817 const ExprWithCleanups *CleanupExpr);
818 CFGBlock *createScopeChangesHandlingBlock(LocalScope::const_iterator SrcPos,
819 CFGBlock *SrcBlk,
820 LocalScope::const_iterator DstPost,
821 CFGBlock *DstBlk);
822
823 // Local scopes creation.
824 LocalScope* createOrReuseLocalScope(LocalScope* Scope);
825
826 void addLocalScopeForStmt(Stmt *S);
827 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,
828 LocalScope* Scope = nullptr);
829 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);
830
831 void addLocalScopeAndDtors(Stmt *S);
832
833 const ConstructionContext *retrieveAndCleanupConstructionContext(Expr *E) {
834 if (!BuildOpts.AddRichCXXConstructors)
835 return nullptr;
836
837 const ConstructionContextLayer *Layer = ConstructionContextMap.lookup(Val: E);
838 if (!Layer)
839 return nullptr;
840
841 cleanupConstructionContext(E);
842 return ConstructionContext::createFromLayers(C&: cfg->getBumpVectorContext(),
843 TopLayer: Layer);
844 }
845
846 // Interface to CFGBlock - adding CFGElements.
847
848 void appendStmt(CFGBlock *B, const Stmt *S) {
849 if (alwaysAdd(stmt: S) && cachedEntry)
850 cachedEntry->second = B;
851
852 // All block-level expressions should have already been IgnoreParens()ed.
853 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
854 B->appendStmt(statement: const_cast<Stmt*>(S), C&: cfg->getBumpVectorContext());
855 }
856
857 void appendConstructor(CXXConstructExpr *CE) {
858 CXXConstructorDecl *C = CE->getConstructor();
859 if (C && C->isNoReturn())
860 Block = createNoReturnBlock();
861 else
862 autoCreateBlock();
863
864 if (const ConstructionContext *CC =
865 retrieveAndCleanupConstructionContext(E: CE)) {
866 Block->appendConstructor(CE, CC, C&: cfg->getBumpVectorContext());
867 return;
868 }
869
870 // No valid construction context found. Fall back to statement.
871 Block->appendStmt(statement: CE, C&: cfg->getBumpVectorContext());
872 }
873
874 void appendCall(CFGBlock *B, CallExpr *CE) {
875 if (alwaysAdd(stmt: CE) && cachedEntry)
876 cachedEntry->second = B;
877
878 if (const ConstructionContext *CC =
879 retrieveAndCleanupConstructionContext(E: CE)) {
880 B->appendCXXRecordTypedCall(E: CE, CC, C&: cfg->getBumpVectorContext());
881 return;
882 }
883
884 // No valid construction context found. Fall back to statement.
885 B->appendStmt(statement: CE, C&: cfg->getBumpVectorContext());
886 }
887
888 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
889 B->appendInitializer(initializer: I, C&: cfg->getBumpVectorContext());
890 }
891
892 void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {
893 B->appendNewAllocator(NE, C&: cfg->getBumpVectorContext());
894 }
895
896 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
897 B->appendBaseDtor(BS, C&: cfg->getBumpVectorContext());
898 }
899
900 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
901 B->appendMemberDtor(FD, C&: cfg->getBumpVectorContext());
902 }
903
904 void appendObjCMessage(CFGBlock *B, ObjCMessageExpr *ME) {
905 if (alwaysAdd(stmt: ME) && cachedEntry)
906 cachedEntry->second = B;
907
908 if (const ConstructionContext *CC =
909 retrieveAndCleanupConstructionContext(E: ME)) {
910 B->appendCXXRecordTypedCall(E: ME, CC, C&: cfg->getBumpVectorContext());
911 return;
912 }
913
914 B->appendStmt(statement: ME, C&: cfg->getBumpVectorContext());
915 }
916
917 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
918 B->appendTemporaryDtor(E, C&: cfg->getBumpVectorContext());
919 }
920
921 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
922 B->appendAutomaticObjDtor(VD, S, C&: cfg->getBumpVectorContext());
923 }
924
925 void appendCleanupFunction(CFGBlock *B, VarDecl *VD) {
926 B->appendCleanupFunction(VD, C&: cfg->getBumpVectorContext());
927 }
928
929 void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {
930 B->appendLifetimeEnds(VD, S, C&: cfg->getBumpVectorContext());
931 }
932
933 void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) {
934 B->appendLoopExit(LoopStmt, C&: cfg->getBumpVectorContext());
935 }
936
937 void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
938 B->appendDeleteDtor(RD, DE, C&: cfg->getBumpVectorContext());
939 }
940
941 void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {
942 B->addSuccessor(Succ: CFGBlock::AdjacentBlock(S, IsReachable),
943 C&: cfg->getBumpVectorContext());
944 }
945
946 /// Add a reachable successor to a block, with the alternate variant that is
947 /// unreachable.
948 void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {
949 B->addSuccessor(Succ: CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),
950 C&: cfg->getBumpVectorContext());
951 }
952
953 void appendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
954 if (BuildOpts.AddScopes)
955 B->appendScopeBegin(VD, S, C&: cfg->getBumpVectorContext());
956 }
957
958 void appendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
959 if (BuildOpts.AddScopes)
960 B->appendScopeEnd(VD, S, C&: cfg->getBumpVectorContext());
961 }
962
963 /// Find a relational comparison with an expression evaluating to a
964 /// boolean and a constant other than 0 and 1.
965 /// e.g. if ((x < y) == 10)
966 TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) {
967 const Expr *LHSExpr = B->getLHS()->IgnoreParens();
968 const Expr *RHSExpr = B->getRHS()->IgnoreParens();
969
970 const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(Val: LHSExpr);
971 const Expr *BoolExpr = RHSExpr;
972 bool IntFirst = true;
973 if (!IntLiteral) {
974 IntLiteral = dyn_cast<IntegerLiteral>(Val: RHSExpr);
975 BoolExpr = LHSExpr;
976 IntFirst = false;
977 }
978
979 if (!IntLiteral || !BoolExpr->isKnownToHaveBooleanValue())
980 return TryResult();
981
982 llvm::APInt IntValue = IntLiteral->getValue();
983 if ((IntValue == 1) || (IntValue == 0))
984 return TryResult();
985
986 bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() ||
987 !IntValue.isNegative();
988
989 BinaryOperatorKind Bok = B->getOpcode();
990 if (Bok == BO_GT || Bok == BO_GE) {
991 // Always true for 10 > bool and bool > -1
992 // Always false for -1 > bool and bool > 10
993 return TryResult(IntFirst == IntLarger);
994 } else {
995 // Always true for -1 < bool and bool < 10
996 // Always false for 10 < bool and bool < -1
997 return TryResult(IntFirst != IntLarger);
998 }
999 }
1000
1001 /// Find an incorrect equality comparison. Either with an expression
1002 /// evaluating to a boolean and a constant other than 0 and 1.
1003 /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to
1004 /// true/false e.q. (x & 8) == 4.
1005 TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) {
1006 const Expr *LHSExpr = B->getLHS()->IgnoreParens();
1007 const Expr *RHSExpr = B->getRHS()->IgnoreParens();
1008
1009 std::optional<llvm::APInt> IntLiteral1 =
1010 getIntegerLiteralSubexpressionValue(E: LHSExpr);
1011 const Expr *BoolExpr = RHSExpr;
1012
1013 if (!IntLiteral1) {
1014 IntLiteral1 = getIntegerLiteralSubexpressionValue(E: RHSExpr);
1015 BoolExpr = LHSExpr;
1016 }
1017
1018 if (!IntLiteral1)
1019 return TryResult();
1020
1021 const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(Val: BoolExpr);
1022 if (BitOp && (BitOp->getOpcode() == BO_And ||
1023 BitOp->getOpcode() == BO_Or)) {
1024 const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens();
1025 const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens();
1026
1027 std::optional<llvm::APInt> IntLiteral2 =
1028 getIntegerLiteralSubexpressionValue(E: LHSExpr2);
1029
1030 if (!IntLiteral2)
1031 IntLiteral2 = getIntegerLiteralSubexpressionValue(E: RHSExpr2);
1032
1033 if (!IntLiteral2)
1034 return TryResult();
1035
1036 if ((BitOp->getOpcode() == BO_And &&
1037 (*IntLiteral2 & *IntLiteral1) != *IntLiteral1) ||
1038 (BitOp->getOpcode() == BO_Or &&
1039 (*IntLiteral2 | *IntLiteral1) != *IntLiteral1)) {
1040 if (BuildOpts.Observer)
1041 BuildOpts.Observer->compareBitwiseEquality(B,
1042 isAlwaysTrue: B->getOpcode() != BO_EQ);
1043 return TryResult(B->getOpcode() != BO_EQ);
1044 }
1045 } else if (BoolExpr->isKnownToHaveBooleanValue()) {
1046 if ((*IntLiteral1 == 1) || (*IntLiteral1 == 0)) {
1047 return TryResult();
1048 }
1049 return TryResult(B->getOpcode() != BO_EQ);
1050 }
1051
1052 return TryResult();
1053 }
1054
1055 // Helper function to get an APInt from an expression. Supports expressions
1056 // which are an IntegerLiteral or a UnaryOperator and returns the value with
1057 // all operations performed on it.
1058 // FIXME: it would be good to unify this function with
1059 // IsIntegerLiteralConstantExpr at some point given the similarity between the
1060 // functions.
1061 std::optional<llvm::APInt>
1062 getIntegerLiteralSubexpressionValue(const Expr *E) {
1063
1064 // If unary.
1065 if (const auto *UnOp = dyn_cast<UnaryOperator>(Val: E->IgnoreParens())) {
1066 // Get the sub expression of the unary expression and get the Integer
1067 // Literal.
1068 const Expr *SubExpr = UnOp->getSubExpr()->IgnoreParens();
1069
1070 if (const auto *IntLiteral = dyn_cast<IntegerLiteral>(Val: SubExpr)) {
1071
1072 llvm::APInt Value = IntLiteral->getValue();
1073
1074 // Perform the operation manually.
1075 switch (UnOp->getOpcode()) {
1076 case UO_Plus:
1077 return Value;
1078 case UO_Minus:
1079 return -Value;
1080 case UO_Not:
1081 return ~Value;
1082 case UO_LNot:
1083 return llvm::APInt(Context->getTypeSize(T: Context->IntTy), !Value);
1084 default:
1085 assert(false && "Unexpected unary operator!");
1086 return std::nullopt;
1087 }
1088 }
1089 } else if (const auto *IntLiteral =
1090 dyn_cast<IntegerLiteral>(Val: E->IgnoreParens()))
1091 return IntLiteral->getValue();
1092
1093 return std::nullopt;
1094 }
1095
1096 template <typename APFloatOrInt>
1097 TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation,
1098 const APFloatOrInt &Value1,
1099 const APFloatOrInt &Value2) {
1100 switch (Relation) {
1101 default:
1102 return TryResult();
1103 case BO_EQ:
1104 return TryResult(Value1 == Value2);
1105 case BO_NE:
1106 return TryResult(Value1 != Value2);
1107 case BO_LT:
1108 return TryResult(Value1 < Value2);
1109 case BO_LE:
1110 return TryResult(Value1 <= Value2);
1111 case BO_GT:
1112 return TryResult(Value1 > Value2);
1113 case BO_GE:
1114 return TryResult(Value1 >= Value2);
1115 }
1116 }
1117
1118 /// There are two checks handled by this function:
1119 /// 1. Find a law-of-excluded-middle or law-of-noncontradiction expression
1120 /// e.g. if (x || !x), if (x && !x)
1121 /// 2. Find a pair of comparison expressions with or without parentheses
1122 /// with a shared variable and constants and a logical operator between them
1123 /// that always evaluates to either true or false.
1124 /// e.g. if (x != 3 || x != 4)
1125 TryResult checkIncorrectLogicOperator(const BinaryOperator *B) {
1126 assert(B->isLogicalOp());
1127 const Expr *LHSExpr = B->getLHS()->IgnoreParens();
1128 const Expr *RHSExpr = B->getRHS()->IgnoreParens();
1129
1130 auto CheckLogicalOpWithNegatedVariable = [this, B](const Expr *E1,
1131 const Expr *E2) {
1132 if (const auto *Negate = dyn_cast<UnaryOperator>(Val: E1)) {
1133 if (Negate->getOpcode() == UO_LNot &&
1134 Expr::isSameComparisonOperand(E1: Negate->getSubExpr(), E2)) {
1135 bool AlwaysTrue = B->getOpcode() == BO_LOr;
1136 if (BuildOpts.Observer)
1137 BuildOpts.Observer->logicAlwaysTrue(B, isAlwaysTrue: AlwaysTrue);
1138 return TryResult(AlwaysTrue);
1139 }
1140 }
1141 return TryResult();
1142 };
1143
1144 TryResult Result = CheckLogicalOpWithNegatedVariable(LHSExpr, RHSExpr);
1145 if (Result.isKnown())
1146 return Result;
1147 Result = CheckLogicalOpWithNegatedVariable(RHSExpr, LHSExpr);
1148 if (Result.isKnown())
1149 return Result;
1150
1151 const auto *LHS = dyn_cast<BinaryOperator>(Val: LHSExpr);
1152 const auto *RHS = dyn_cast<BinaryOperator>(Val: RHSExpr);
1153 if (!LHS || !RHS)
1154 return {};
1155
1156 if (!LHS->isComparisonOp() || !RHS->isComparisonOp())
1157 return {};
1158
1159 const Expr *DeclExpr1;
1160 const Expr *NumExpr1;
1161 BinaryOperatorKind BO1;
1162 std::tie(args&: DeclExpr1, args&: BO1, args&: NumExpr1) = tryNormalizeBinaryOperator(B: LHS);
1163
1164 if (!DeclExpr1 || !NumExpr1)
1165 return {};
1166
1167 const Expr *DeclExpr2;
1168 const Expr *NumExpr2;
1169 BinaryOperatorKind BO2;
1170 std::tie(args&: DeclExpr2, args&: BO2, args&: NumExpr2) = tryNormalizeBinaryOperator(B: RHS);
1171
1172 if (!DeclExpr2 || !NumExpr2)
1173 return {};
1174
1175 // Check that it is the same variable on both sides.
1176 if (!Expr::isSameComparisonOperand(E1: DeclExpr1, E2: DeclExpr2))
1177 return {};
1178
1179 // Make sure the user's intent is clear (e.g. they're comparing against two
1180 // int literals, or two things from the same enum)
1181 if (!areExprTypesCompatible(E1: NumExpr1, E2: NumExpr2))
1182 return {};
1183
1184 // Check that the two expressions are of the same type.
1185 Expr::EvalResult L1Result, L2Result;
1186 if (!NumExpr1->EvaluateAsRValue(Result&: L1Result, Ctx: *Context) ||
1187 !NumExpr2->EvaluateAsRValue(Result&: L2Result, Ctx: *Context))
1188 return {};
1189
1190 // Check whether expression is always true/false by evaluating the
1191 // following
1192 // * variable x is less than the smallest literal.
1193 // * variable x is equal to the smallest literal.
1194 // * Variable x is between smallest and largest literal.
1195 // * Variable x is equal to the largest literal.
1196 // * Variable x is greater than largest literal.
1197 // This isn't technically correct, as it doesn't take into account the
1198 // possibility that the variable could be NaN. However, this is a very rare
1199 // case.
1200 auto AnalyzeConditions = [&](const auto &Values,
1201 const BinaryOperatorKind *BO1,
1202 const BinaryOperatorKind *BO2) -> TryResult {
1203 bool AlwaysTrue = true, AlwaysFalse = true;
1204 // Track value of both subexpressions. If either side is always
1205 // true/false, another warning should have already been emitted.
1206 bool LHSAlwaysTrue = true, LHSAlwaysFalse = true;
1207 bool RHSAlwaysTrue = true, RHSAlwaysFalse = true;
1208
1209 for (const auto &Value : Values) {
1210 TryResult Res1 =
1211 analyzeLogicOperatorCondition(*BO1, Value, Values[1] /* L1 */);
1212 TryResult Res2 =
1213 analyzeLogicOperatorCondition(*BO2, Value, Values[3] /* L2 */);
1214
1215 if (!Res1.isKnown() || !Res2.isKnown())
1216 return {};
1217
1218 const bool IsAnd = B->getOpcode() == BO_LAnd;
1219 const bool Combine = IsAnd ? (Res1.isTrue() && Res2.isTrue())
1220 : (Res1.isTrue() || Res2.isTrue());
1221
1222 AlwaysTrue &= Combine;
1223 AlwaysFalse &= !Combine;
1224
1225 LHSAlwaysTrue &= Res1.isTrue();
1226 LHSAlwaysFalse &= Res1.isFalse();
1227 RHSAlwaysTrue &= Res2.isTrue();
1228 RHSAlwaysFalse &= Res2.isFalse();
1229 }
1230
1231 if (AlwaysTrue || AlwaysFalse) {
1232 if (!LHSAlwaysTrue && !LHSAlwaysFalse && !RHSAlwaysTrue &&
1233 !RHSAlwaysFalse && BuildOpts.Observer) {
1234 BuildOpts.Observer->compareAlwaysTrue(B, isAlwaysTrue: AlwaysTrue);
1235 }
1236 return TryResult(AlwaysTrue);
1237 }
1238 return {};
1239 };
1240
1241 // Handle integer comparison.
1242 if (L1Result.Val.getKind() == APValue::Int &&
1243 L2Result.Val.getKind() == APValue::Int) {
1244 llvm::APSInt L1 = L1Result.Val.getInt();
1245 llvm::APSInt L2 = L2Result.Val.getInt();
1246
1247 // Can't compare signed with unsigned or with different bit width.
1248 if (L1.isSigned() != L2.isSigned() ||
1249 L1.getBitWidth() != L2.getBitWidth())
1250 return {};
1251
1252 // Values that will be used to determine if result of logical
1253 // operator is always true/false
1254 const llvm::APSInt Values[] = {
1255 // Value less than both Value1 and Value2
1256 llvm::APSInt::getMinValue(numBits: L1.getBitWidth(), Unsigned: L1.isUnsigned()),
1257 // L1
1258 L1,
1259 // Value between Value1 and Value2
1260 ((L1 < L2) ? L1 : L2) +
1261 llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1), L1.isUnsigned()),
1262 // L2
1263 L2,
1264 // Value greater than both Value1 and Value2
1265 llvm::APSInt::getMaxValue(numBits: L1.getBitWidth(), Unsigned: L1.isUnsigned()),
1266 };
1267
1268 return AnalyzeConditions(Values, &BO1, &BO2);
1269 }
1270
1271 // Handle float comparison.
1272 if (L1Result.Val.getKind() == APValue::Float &&
1273 L2Result.Val.getKind() == APValue::Float) {
1274 llvm::APFloat L1 = L1Result.Val.getFloat();
1275 llvm::APFloat L2 = L2Result.Val.getFloat();
1276 // Note that L1 and L2 do not necessarily have the same type. For example
1277 // `x != 0 || x != 1.0`, if `x` is a float16, the two literals `0` and
1278 // `1.0` are float16 and double respectively. In this case, we should do
1279 // a conversion before comparing L1 and L2. Their types must be
1280 // compatible since they are comparing with the same DRE.
1281 int Order = Context->getFloatingTypeSemanticOrder(LHS: NumExpr1->getType(),
1282 RHS: NumExpr2->getType());
1283 bool Ignored = false;
1284
1285 if (Order > 0) {
1286 // type rank L1 > L2:
1287 if (llvm::APFloat::opOK !=
1288 L2.convert(ToSemantics: L1.getSemantics(), RM: llvm::APFloat::rmNearestTiesToEven,
1289 losesInfo: &Ignored))
1290 return {};
1291 } else if (Order < 0)
1292 // type rank L1 < L2:
1293 if (llvm::APFloat::opOK !=
1294 L1.convert(ToSemantics: L2.getSemantics(), RM: llvm::APFloat::rmNearestTiesToEven,
1295 losesInfo: &Ignored))
1296 return {};
1297
1298 llvm::APFloat MidValue = L1;
1299 MidValue.add(RHS: L2, RM: llvm::APFloat::rmNearestTiesToEven);
1300 MidValue.divide(RHS: llvm::APFloat(MidValue.getSemantics(), "2.0"),
1301 RM: llvm::APFloat::rmNearestTiesToEven);
1302
1303 const llvm::APFloat Values[] = {
1304 llvm::APFloat::getSmallest(Sem: L1.getSemantics(), Negative: true), L1, MidValue, L2,
1305 llvm::APFloat::getLargest(Sem: L2.getSemantics(), Negative: false),
1306 };
1307
1308 return AnalyzeConditions(Values, &BO1, &BO2);
1309 }
1310
1311 return {};
1312 }
1313
1314 /// A bitwise-or with a non-zero constant always evaluates to true.
1315 TryResult checkIncorrectBitwiseOrOperator(const BinaryOperator *B) {
1316 const Expr *LHSConstant =
1317 tryTransformToLiteralConstant(E: B->getLHS()->IgnoreParenImpCasts());
1318 const Expr *RHSConstant =
1319 tryTransformToLiteralConstant(E: B->getRHS()->IgnoreParenImpCasts());
1320
1321 if ((LHSConstant && RHSConstant) || (!LHSConstant && !RHSConstant))
1322 return {};
1323
1324 const Expr *Constant = LHSConstant ? LHSConstant : RHSConstant;
1325
1326 Expr::EvalResult Result;
1327 if (!Constant->EvaluateAsInt(Result, Ctx: *Context))
1328 return {};
1329
1330 if (Result.Val.getInt() == 0)
1331 return {};
1332
1333 if (BuildOpts.Observer)
1334 BuildOpts.Observer->compareBitwiseOr(B);
1335
1336 return TryResult(true);
1337 }
1338
1339 /// Try and evaluate an expression to an integer constant.
1340 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {
1341 if (!BuildOpts.PruneTriviallyFalseEdges)
1342 return false;
1343 return !S->isTypeDependent() &&
1344 !S->isValueDependent() &&
1345 S->EvaluateAsRValue(Result&: outResult, Ctx: *Context);
1346 }
1347
1348 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
1349 /// if we can evaluate to a known value, otherwise return -1.
1350 TryResult tryEvaluateBool(Expr *S) {
1351 if (!BuildOpts.PruneTriviallyFalseEdges ||
1352 S->isTypeDependent() || S->isValueDependent())
1353 return {};
1354
1355 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(Val: S)) {
1356 if (Bop->isLogicalOp() || Bop->isEqualityOp()) {
1357 // Check the cache first.
1358 CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(Val: S);
1359 if (I != CachedBoolEvals.end())
1360 return I->second; // already in map;
1361
1362 // Retrieve result at first, or the map might be updated.
1363 TryResult Result = evaluateAsBooleanConditionNoCache(E: S);
1364 CachedBoolEvals[S] = Result; // update or insert
1365 return Result;
1366 }
1367 else {
1368 switch (Bop->getOpcode()) {
1369 default: break;
1370 // For 'x & 0' and 'x * 0', we can determine that
1371 // the value is always false.
1372 case BO_Mul:
1373 case BO_And: {
1374 // If either operand is zero, we know the value
1375 // must be false.
1376 Expr::EvalResult LHSResult;
1377 if (Bop->getLHS()->EvaluateAsInt(Result&: LHSResult, Ctx: *Context)) {
1378 llvm::APSInt IntVal = LHSResult.Val.getInt();
1379 if (!IntVal.getBoolValue()) {
1380 return TryResult(false);
1381 }
1382 }
1383 Expr::EvalResult RHSResult;
1384 if (Bop->getRHS()->EvaluateAsInt(Result&: RHSResult, Ctx: *Context)) {
1385 llvm::APSInt IntVal = RHSResult.Val.getInt();
1386 if (!IntVal.getBoolValue()) {
1387 return TryResult(false);
1388 }
1389 }
1390 }
1391 break;
1392 }
1393 }
1394 }
1395
1396 return evaluateAsBooleanConditionNoCache(E: S);
1397 }
1398
1399 /// Evaluate as boolean \param E without using the cache.
1400 TryResult evaluateAsBooleanConditionNoCache(Expr *E) {
1401 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(Val: E)) {
1402 if (Bop->isLogicalOp()) {
1403 TryResult LHS = tryEvaluateBool(S: Bop->getLHS());
1404 if (LHS.isKnown()) {
1405 // We were able to evaluate the LHS, see if we can get away with not
1406 // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
1407 if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1408 return LHS.isTrue();
1409
1410 TryResult RHS = tryEvaluateBool(S: Bop->getRHS());
1411 if (RHS.isKnown()) {
1412 if (Bop->getOpcode() == BO_LOr)
1413 return LHS.isTrue() || RHS.isTrue();
1414 else
1415 return LHS.isTrue() && RHS.isTrue();
1416 }
1417 } else {
1418 TryResult RHS = tryEvaluateBool(S: Bop->getRHS());
1419 if (RHS.isKnown()) {
1420 // We can't evaluate the LHS; however, sometimes the result
1421 // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
1422 if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1423 return RHS.isTrue();
1424 } else {
1425 TryResult BopRes = checkIncorrectLogicOperator(B: Bop);
1426 if (BopRes.isKnown())
1427 return BopRes.isTrue();
1428 }
1429 }
1430
1431 return {};
1432 } else if (Bop->isEqualityOp()) {
1433 TryResult BopRes = checkIncorrectEqualityOperator(B: Bop);
1434 if (BopRes.isKnown())
1435 return BopRes.isTrue();
1436 } else if (Bop->isRelationalOp()) {
1437 TryResult BopRes = checkIncorrectRelationalOperator(B: Bop);
1438 if (BopRes.isKnown())
1439 return BopRes.isTrue();
1440 } else if (Bop->getOpcode() == BO_Or) {
1441 TryResult BopRes = checkIncorrectBitwiseOrOperator(B: Bop);
1442 if (BopRes.isKnown())
1443 return BopRes.isTrue();
1444 }
1445 }
1446
1447 bool Result;
1448 if (E->EvaluateAsBooleanCondition(Result, Ctx: *Context))
1449 return Result;
1450
1451 return {};
1452 }
1453
1454 bool hasTrivialDestructor(const VarDecl *VD) const;
1455 bool needsAutomaticDestruction(const VarDecl *VD) const;
1456};
1457
1458} // namespace
1459
1460Expr *
1461clang::extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE) {
1462 if (!AILE)
1463 return nullptr;
1464
1465 Expr *AILEInit = AILE->getSubExpr();
1466 while (const auto *E = dyn_cast<ArrayInitLoopExpr>(Val: AILEInit))
1467 AILEInit = E->getSubExpr();
1468
1469 return AILEInit;
1470}
1471
1472inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
1473 const Stmt *stmt) const {
1474 return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
1475}
1476
1477bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
1478 bool shouldAdd = BuildOpts.alwaysAdd(stmt);
1479
1480 if (!BuildOpts.forcedBlkExprs)
1481 return shouldAdd;
1482
1483 if (lastLookup == stmt) {
1484 if (cachedEntry) {
1485 assert(cachedEntry->first == stmt);
1486 return true;
1487 }
1488 return shouldAdd;
1489 }
1490
1491 lastLookup = stmt;
1492
1493 // Perform the lookup!
1494 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
1495
1496 if (!fb) {
1497 // No need to update 'cachedEntry', since it will always be null.
1498 assert(!cachedEntry);
1499 return shouldAdd;
1500 }
1501
1502 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(Val: stmt);
1503 if (itr == fb->end()) {
1504 cachedEntry = nullptr;
1505 return shouldAdd;
1506 }
1507
1508 cachedEntry = &*itr;
1509 return true;
1510}
1511
1512// FIXME: Add support for dependent-sized array types in C++?
1513// Does it even make sense to build a CFG for an uninstantiated template?
1514static const VariableArrayType *FindVA(const Type *t) {
1515 while (const ArrayType *vt = dyn_cast<ArrayType>(Val: t)) {
1516 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(Val: vt))
1517 if (vat->getSizeExpr())
1518 return vat;
1519
1520 t = vt->getElementType().getTypePtr();
1521 }
1522
1523 return nullptr;
1524}
1525
1526void CFGBuilder::consumeConstructionContext(
1527 const ConstructionContextLayer *Layer, Expr *E) {
1528 assert((isa<CXXConstructExpr>(E) || isa<CallExpr>(E) ||
1529 isa<ObjCMessageExpr>(E)) && "Expression cannot construct an object!");
1530 if (const ConstructionContextLayer *PreviouslyStoredLayer =
1531 ConstructionContextMap.lookup(Val: E)) {
1532 (void)PreviouslyStoredLayer;
1533 // We might have visited this child when we were finding construction
1534 // contexts within its parents.
1535 assert(PreviouslyStoredLayer->isStrictlyMoreSpecificThan(Layer) &&
1536 "Already within a different construction context!");
1537 } else {
1538 ConstructionContextMap[E] = Layer;
1539 }
1540}
1541
1542void CFGBuilder::findConstructionContexts(
1543 const ConstructionContextLayer *Layer, Stmt *Child) {
1544 if (!BuildOpts.AddRichCXXConstructors)
1545 return;
1546
1547 if (!Child)
1548 return;
1549
1550 auto withExtraLayer = [this, Layer](const ConstructionContextItem &Item) {
1551 return ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item,
1552 Parent: Layer);
1553 };
1554
1555 switch(Child->getStmtClass()) {
1556 case Stmt::CXXConstructExprClass:
1557 case Stmt::CXXTemporaryObjectExprClass: {
1558 // Support pre-C++17 copy elision AST.
1559 auto *CE = cast<CXXConstructExpr>(Val: Child);
1560 if (BuildOpts.MarkElidedCXXConstructors && CE->isElidable()) {
1561 findConstructionContexts(Layer: withExtraLayer(CE), Child: CE->getArg(Arg: 0));
1562 }
1563
1564 consumeConstructionContext(Layer, E: CE);
1565 break;
1566 }
1567 // FIXME: This, like the main visit, doesn't support CUDAKernelCallExpr.
1568 // FIXME: An isa<> would look much better but this whole switch is a
1569 // workaround for an internal compiler error in MSVC 2015 (see r326021).
1570 case Stmt::CallExprClass:
1571 case Stmt::CXXMemberCallExprClass:
1572 case Stmt::CXXOperatorCallExprClass:
1573 case Stmt::UserDefinedLiteralClass:
1574 case Stmt::ObjCMessageExprClass: {
1575 auto *E = cast<Expr>(Val: Child);
1576 if (CFGCXXRecordTypedCall::isCXXRecordTypedCall(E))
1577 consumeConstructionContext(Layer, E);
1578 break;
1579 }
1580 case Stmt::ExprWithCleanupsClass: {
1581 auto *Cleanups = cast<ExprWithCleanups>(Val: Child);
1582 findConstructionContexts(Layer, Child: Cleanups->getSubExpr());
1583 break;
1584 }
1585 case Stmt::CXXFunctionalCastExprClass: {
1586 auto *Cast = cast<CXXFunctionalCastExpr>(Val: Child);
1587 findConstructionContexts(Layer, Child: Cast->getSubExpr());
1588 break;
1589 }
1590 case Stmt::ImplicitCastExprClass: {
1591 auto *Cast = cast<ImplicitCastExpr>(Val: Child);
1592 // Should we support other implicit cast kinds?
1593 switch (Cast->getCastKind()) {
1594 case CK_NoOp:
1595 case CK_ConstructorConversion:
1596 findConstructionContexts(Layer, Child: Cast->getSubExpr());
1597 break;
1598 default:
1599 break;
1600 }
1601 break;
1602 }
1603 case Stmt::CXXBindTemporaryExprClass: {
1604 auto *BTE = cast<CXXBindTemporaryExpr>(Val: Child);
1605 findConstructionContexts(Layer: withExtraLayer(BTE), Child: BTE->getSubExpr());
1606 break;
1607 }
1608 case Stmt::MaterializeTemporaryExprClass: {
1609 // Normally we don't want to search in MaterializeTemporaryExpr because
1610 // it indicates the beginning of a temporary object construction context,
1611 // so it shouldn't be found in the middle. However, if it is the beginning
1612 // of an elidable copy or move construction context, we need to include it.
1613 if (Layer->getItem().getKind() ==
1614 ConstructionContextItem::ElidableConstructorKind) {
1615 auto *MTE = cast<MaterializeTemporaryExpr>(Val: Child);
1616 findConstructionContexts(Layer: withExtraLayer(MTE), Child: MTE->getSubExpr());
1617 }
1618 break;
1619 }
1620 case Stmt::ConditionalOperatorClass: {
1621 auto *CO = cast<ConditionalOperator>(Val: Child);
1622 if (Layer->getItem().getKind() !=
1623 ConstructionContextItem::MaterializationKind) {
1624 // If the object returned by the conditional operator is not going to be a
1625 // temporary object that needs to be immediately materialized, then
1626 // it must be C++17 with its mandatory copy elision. Do not yet promise
1627 // to support this case.
1628 assert(!CO->getType()->getAsCXXRecordDecl() || CO->isGLValue() ||
1629 Context->getLangOpts().CPlusPlus17);
1630 break;
1631 }
1632 findConstructionContexts(Layer, Child: CO->getLHS());
1633 findConstructionContexts(Layer, Child: CO->getRHS());
1634 break;
1635 }
1636 case Stmt::InitListExprClass: {
1637 auto *ILE = cast<InitListExpr>(Val: Child);
1638 if (ILE->isTransparent()) {
1639 findConstructionContexts(Layer, Child: ILE->getInit(Init: 0));
1640 break;
1641 }
1642 // TODO: Handle other cases. For now, fail to find construction contexts.
1643 break;
1644 }
1645 case Stmt::ParenExprClass: {
1646 // If expression is placed into parenthesis we should propagate the parent
1647 // construction context to subexpressions.
1648 auto *PE = cast<ParenExpr>(Val: Child);
1649 findConstructionContexts(Layer, Child: PE->getSubExpr());
1650 break;
1651 }
1652 default:
1653 break;
1654 }
1655}
1656
1657void CFGBuilder::cleanupConstructionContext(Expr *E) {
1658 assert(BuildOpts.AddRichCXXConstructors &&
1659 "We should not be managing construction contexts!");
1660 assert(ConstructionContextMap.count(E) &&
1661 "Cannot exit construction context without the context!");
1662 ConstructionContextMap.erase(Val: E);
1663}
1664
1665/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
1666/// arbitrary statement. Examples include a single expression or a function
1667/// body (compound statement). The ownership of the returned CFG is
1668/// transferred to the caller. If CFG construction fails, this method returns
1669/// NULL.
1670std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
1671 assert(cfg.get());
1672 if (!Statement)
1673 return nullptr;
1674
1675 // Create an empty block that will serve as the exit block for the CFG. Since
1676 // this is the first block added to the CFG, it will be implicitly registered
1677 // as the exit block.
1678 Succ = createBlock();
1679 assert(Succ == &cfg->getExit());
1680 Block = nullptr; // the EXIT block is empty. Create all other blocks lazily.
1681
1682 if (BuildOpts.AddLifetime && BuildOpts.AddParameterLifetimes) {
1683 // Add parameters to the initial scope to handle lifetime ends.
1684 LocalScope *paramScope = nullptr;
1685 if (const auto *FD = dyn_cast_or_null<FunctionDecl>(Val: D))
1686 for (ParmVarDecl *PD : FD->parameters()) {
1687 paramScope = addLocalScopeForVarDecl(VD: PD, Scope: paramScope);
1688 }
1689 if (auto *C = dyn_cast<CompoundStmt>(Val: Statement))
1690 if (C->body_empty() || !isa<ReturnStmt>(Val: *C->body_rbegin()))
1691 // If the body ends with a ReturnStmt, the dtors will be added in
1692 // VisitReturnStmt.
1693 addAutomaticObjHandling(B: ScopePos, E: LocalScope::const_iterator(),
1694 S: Statement);
1695 }
1696 if (BuildOpts.AddImplicitDtors)
1697 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(Val: D))
1698 addImplicitDtorsForDestructor(DD);
1699
1700 // Visit the statements and create the CFG.
1701 CFGBlock *B = addStmt(S: Statement);
1702
1703 if (badCFG)
1704 return nullptr;
1705
1706 // For C++ constructor add initializers to CFG. Constructors of virtual bases
1707 // are ignored unless the object is of the most derived class.
1708 // class VBase { VBase() = default; VBase(int) {} };
1709 // class A : virtual public VBase { A() : VBase(0) {} };
1710 // class B : public A {};
1711 // B b; // Constructor calls in order: VBase(), A(), B().
1712 // // VBase(0) is ignored because A isn't the most derived class.
1713 // This may result in the virtual base(s) being already initialized at this
1714 // point, in which case we should jump right onto non-virtual bases and
1715 // fields. To handle this, make a CFG branch. We only need to add one such
1716 // branch per constructor, since the Standard states that all virtual bases
1717 // shall be initialized before non-virtual bases and direct data members.
1718 if (const auto *CD = dyn_cast_or_null<CXXConstructorDecl>(Val: D)) {
1719 CFGBlock *VBaseSucc = nullptr;
1720 for (auto *I : llvm::reverse(C: CD->inits())) {
1721 if (BuildOpts.AddVirtualBaseBranches && !VBaseSucc &&
1722 I->isBaseInitializer() && I->isBaseVirtual()) {
1723 // We've reached the first virtual base init while iterating in reverse
1724 // order. Make a new block for virtual base initializers so that we
1725 // could skip them.
1726 VBaseSucc = Succ = B ? B : &cfg->getExit();
1727 Block = createBlock();
1728 }
1729 B = addInitializer(I);
1730 if (badCFG)
1731 return nullptr;
1732 }
1733 if (VBaseSucc) {
1734 // Make a branch block for potentially skipping virtual base initializers.
1735 Succ = VBaseSucc;
1736 B = createBlock();
1737 B->setTerminator(
1738 CFGTerminator(nullptr, CFGTerminator::VirtualBaseBranch));
1739 addSuccessor(B, S: Block, IsReachable: true);
1740 }
1741 }
1742
1743 if (B)
1744 Succ = B;
1745
1746 // Backpatch the gotos whose label -> block mappings we didn't know when we
1747 // encountered them.
1748 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
1749 E = BackpatchBlocks.end(); I != E; ++I ) {
1750
1751 CFGBlock *B = I->block;
1752 if (auto *G = dyn_cast<GotoStmt>(Val: B->getTerminator())) {
1753 LabelMapTy::iterator LI = LabelMap.find(Val: G->getLabel());
1754 // If there is no target for the goto, then we are looking at an
1755 // incomplete AST. Handle this by not registering a successor.
1756 if (LI == LabelMap.end())
1757 continue;
1758 JumpTarget JT = LI->second;
1759
1760 CFGBlock *SuccBlk = createScopeChangesHandlingBlock(
1761 SrcPos: I->scopePosition, SrcBlk: B, DstPost: JT.scopePosition, DstBlk: JT.block);
1762 addSuccessor(B, S: SuccBlk);
1763 } else if (auto *G = dyn_cast<GCCAsmStmt>(Val: B->getTerminator())) {
1764 CFGBlock *Successor = (I+1)->block;
1765 for (auto *L : G->labels()) {
1766 LabelMapTy::iterator LI = LabelMap.find(Val: L->getLabel());
1767 // If there is no target for the goto, then we are looking at an
1768 // incomplete AST. Handle this by not registering a successor.
1769 if (LI == LabelMap.end())
1770 continue;
1771 JumpTarget JT = LI->second;
1772 // Successor has been added, so skip it.
1773 if (JT.block == Successor)
1774 continue;
1775 addSuccessor(B, S: JT.block);
1776 }
1777 I++;
1778 }
1779 }
1780
1781 // Add successors to the Indirect Goto Dispatch block (if we have one).
1782 if (CFGBlock *B = cfg->getIndirectGotoBlock())
1783 for (LabelDecl *LD : AddressTakenLabels) {
1784 // Lookup the target block.
1785 LabelMapTy::iterator LI = LabelMap.find(Val: LD);
1786
1787 // If there is no target block that contains label, then we are looking
1788 // at an incomplete AST. Handle this by not registering a successor.
1789 if (LI == LabelMap.end()) continue;
1790
1791 addSuccessor(B, S: LI->second.block);
1792 }
1793
1794 // Create an empty entry block that has no predecessors.
1795 cfg->setEntry(createBlock());
1796
1797 if (BuildOpts.AddRichCXXConstructors)
1798 assert(ConstructionContextMap.empty() &&
1799 "Not all construction contexts were cleaned up!");
1800
1801 return std::move(cfg);
1802}
1803
1804/// createBlock - Used to lazily create blocks that are connected
1805/// to the current (global) successor.
1806CFGBlock *CFGBuilder::createBlock(bool add_successor) {
1807 CFGBlock *B = cfg->createBlock();
1808 if (add_successor && Succ)
1809 addSuccessor(B, S: Succ);
1810 return B;
1811}
1812
1813/// createNoReturnBlock - Used to create a block that is a 'noreturn' or
1814/// 'analyzer_noreturn' point in the CFG. It is *not* connected to the current
1815/// (global) successor, and instead directly tied to the exit block in order to
1816/// be reachable. If \p AnalyzerOnly is true, the block is recorded as ending
1817/// in an 'analyzer_noreturn' call rather than a real 'noreturn' one.
1818CFGBlock *CFGBuilder::createNoReturnBlock(bool AnalyzerOnly) {
1819 CFGBlock *B = createBlock(add_successor: false);
1820 B->setHasNoReturnElement(AnalyzerOnly);
1821 addSuccessor(B, ReachableBlock: &cfg->getExit(), AltBlock: Succ);
1822 return B;
1823}
1824
1825/// addInitializer - Add C++ base or member initializer element to CFG.
1826CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
1827 if (!BuildOpts.AddInitializers)
1828 return Block;
1829
1830 bool HasTemporaries = false;
1831
1832 // Destructors of temporaries in initialization expression should be called
1833 // after initialization finishes.
1834 Expr *Init = I->getInit();
1835 if (Init) {
1836 Expr *ActualInit = Init;
1837 if (BuildOpts.AddCXXDefaultInitExprInCtors)
1838 if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Val: Init))
1839 ActualInit = DIE->getExpr();
1840
1841 HasTemporaries = isa<ExprWithCleanups>(Val: ActualInit);
1842
1843 if (HasTemporaries &&
1844 (BuildOpts.AddTemporaryDtors || BuildOpts.AddLifetime)) {
1845 // Generate destructors for temporaries in initialization expression.
1846 TempDtorContext Context;
1847 auto *FullExprWithCleanups = cast<ExprWithCleanups>(Val: ActualInit);
1848 VisitForTemporaries(E: FullExprWithCleanups->getSubExpr(),
1849 /*ExternallyDestructed=*/false, Context);
1850
1851 addFullExprCleanupMarker(Context, CleanupExpr: FullExprWithCleanups);
1852 }
1853 }
1854
1855 autoCreateBlock();
1856 appendInitializer(B: Block, I);
1857
1858 if (Init) {
1859 // If the initializer is an ArrayInitLoopExpr, we want to extract the
1860 // initializer, that's used for each element.
1861 auto *AILEInit = extractElementInitializerFromNestedAILE(
1862 AILE: dyn_cast<ArrayInitLoopExpr>(Val: Init));
1863
1864 findConstructionContexts(
1865 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: I),
1866 Child: AILEInit ? AILEInit : Init);
1867
1868 if (BuildOpts.AddCXXDefaultInitExprInCtors) {
1869 if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Val: Init)) {
1870 // In general, appending the expression wrapped by a CXXDefaultInitExpr
1871 // may cause the same Expr to appear more than once in the CFG. Doing it
1872 // here is safe because there's only one initializer per field.
1873 autoCreateBlock();
1874 appendStmt(B: Block, S: Default);
1875 if (Stmt *Child = Default->getExpr()) {
1876 if (HasTemporaries)
1877 Child = cast<ExprWithCleanups>(Val: Child)->getSubExpr();
1878 if (CFGBlock *R = Visit(S: Child))
1879 Block = R;
1880 }
1881 return Block;
1882 }
1883 }
1884
1885 if (HasTemporaries) {
1886 // For expression with temporaries go directly to subexpression to omit
1887 // generating destructors for the second time.
1888 return Visit(S: cast<ExprWithCleanups>(Val: Init)->getSubExpr());
1889 }
1890 return Visit(S: Init);
1891 }
1892
1893 return Block;
1894}
1895
1896/// Retrieve the type of the temporary object whose lifetime was
1897/// extended by a local reference with the given initializer.
1898static QualType getReferenceInitTemporaryType(const Expr *Init,
1899 bool *FoundMTE = nullptr) {
1900 while (true) {
1901 // Skip parentheses.
1902 Init = Init->IgnoreParens();
1903
1904 // Skip through cleanups.
1905 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Val: Init)) {
1906 Init = EWC->getSubExpr();
1907 continue;
1908 }
1909
1910 // Skip through the temporary-materialization expression.
1911 if (const MaterializeTemporaryExpr *MTE
1912 = dyn_cast<MaterializeTemporaryExpr>(Val: Init)) {
1913 Init = MTE->getSubExpr();
1914 if (FoundMTE)
1915 *FoundMTE = true;
1916 continue;
1917 }
1918
1919 // Skip sub-object accesses into rvalues.
1920 const Expr *SkippedInit = Init->skipRValueSubobjectAdjustments();
1921 if (SkippedInit != Init) {
1922 Init = SkippedInit;
1923 continue;
1924 }
1925
1926 break;
1927 }
1928
1929 return Init->getType();
1930}
1931
1932// TODO: Support adding LoopExit element to the CFG in case where the loop is
1933// ended by ReturnStmt, GotoStmt or ThrowExpr.
1934void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
1935 if(!BuildOpts.AddLoopExit)
1936 return;
1937 autoCreateBlock();
1938 appendLoopExit(B: Block, LoopStmt);
1939}
1940
1941/// Adds the CFG elements for leaving the scope of automatic objects in
1942/// range [B, E). This include following:
1943/// * AutomaticObjectDtor for variables with non-trivial destructor
1944/// * LifetimeEnds for all variables
1945/// * ScopeEnd for each scope left
1946void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
1947 LocalScope::const_iterator E,
1948 Stmt *S) {
1949 if (!BuildOpts.AddScopes && !BuildOpts.AddImplicitDtors &&
1950 !BuildOpts.AddLifetime)
1951 return;
1952
1953 if (B == E)
1954 return;
1955
1956 // Not leaving the scope, only need to handle destruction and lifetime
1957 if (B.inSameLocalScope(rhs: E)) {
1958 addAutomaticObjDestruction(B, E, S);
1959 return;
1960 }
1961
1962 // Extract information about all local scopes that are left
1963 SmallVector<LocalScope::const_iterator, 10> LocalScopeEndMarkers;
1964 LocalScopeEndMarkers.push_back(Elt: B);
1965 for (LocalScope::const_iterator I = B; I != E; ++I) {
1966 if (!I.inSameLocalScope(rhs: LocalScopeEndMarkers.back()))
1967 LocalScopeEndMarkers.push_back(Elt: I);
1968 }
1969 LocalScopeEndMarkers.push_back(Elt: E);
1970
1971 // We need to leave the scope in reverse order, so we reverse the end
1972 // markers
1973 std::reverse(first: LocalScopeEndMarkers.begin(), last: LocalScopeEndMarkers.end());
1974 auto Pairwise =
1975 llvm::zip(t&: LocalScopeEndMarkers, u: llvm::drop_begin(RangeOrContainer&: LocalScopeEndMarkers));
1976 for (auto [E, B] : Pairwise) {
1977 if (!B.inSameLocalScope(rhs: E))
1978 addScopeExitHandling(B, E, S);
1979 addAutomaticObjDestruction(B, E, S);
1980 }
1981}
1982
1983/// Add CFG elements corresponding to call destructor and end of lifetime
1984/// of all automatic variables with non-trivial destructor in range [B, E).
1985/// This include AutomaticObjectDtor and LifetimeEnds elements.
1986void CFGBuilder::addAutomaticObjDestruction(LocalScope::const_iterator B,
1987 LocalScope::const_iterator E,
1988 Stmt *S) {
1989 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime)
1990 return;
1991
1992 if (B == E)
1993 return;
1994
1995 SmallVector<VarDecl *, 10> DeclsNeedDestruction;
1996 DeclsNeedDestruction.reserve(N: B.distance(L: E));
1997
1998 for (VarDecl* D : llvm::make_range(x: B, y: E))
1999 if (needsAutomaticDestruction(VD: D))
2000 DeclsNeedDestruction.push_back(Elt: D);
2001
2002 for (VarDecl *VD : llvm::reverse(C&: DeclsNeedDestruction)) {
2003 if (BuildOpts.AddImplicitDtors) {
2004 // If this destructor is marked as a no-return destructor, we need to
2005 // create a new block for the destructor which does not have as a
2006 // successor anything built thus far: control won't flow out of this
2007 // block.
2008 QualType Ty = VD->getType();
2009 if (Ty->isReferenceType())
2010 Ty = getReferenceInitTemporaryType(Init: VD->getInit());
2011 Ty = Context->getBaseElementType(QT: Ty);
2012
2013 const CXXRecordDecl *CRD = Ty->getAsCXXRecordDecl();
2014 if (CRD && CRD->isAnyDestructorNoReturn())
2015 Block = createNoReturnBlock();
2016 }
2017
2018 autoCreateBlock();
2019
2020 // Add LifetimeEnd after automatic obj with non-trivial destructors,
2021 // as they end their lifetime when the destructor returns. For trivial
2022 // objects, we end lifetime with scope end.
2023 if (BuildOpts.AddLifetime)
2024 appendLifetimeEnds(B: Block, VD, S);
2025 if (BuildOpts.AddImplicitDtors && !hasTrivialDestructor(VD))
2026 appendAutomaticObjDtor(B: Block, VD, S);
2027 if (VD->hasAttr<CleanupAttr>())
2028 appendCleanupFunction(B: Block, VD);
2029 }
2030}
2031
2032/// Add CFG elements corresponding to leaving a scope.
2033/// Assumes that range [B, E) corresponds to single scope.
2034/// This add following elements:
2035/// * LifetimeEnds for all variables with non-trivial destructor
2036/// * ScopeEnd for each scope left
2037void CFGBuilder::addScopeExitHandling(LocalScope::const_iterator B,
2038 LocalScope::const_iterator E, Stmt *S) {
2039 assert(!B.inSameLocalScope(E));
2040 if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes)
2041 return;
2042
2043 if (BuildOpts.AddScopes) {
2044 autoCreateBlock();
2045 appendScopeEnd(B: Block, VD: B.getFirstVarInScope(), S);
2046 }
2047
2048 if (!BuildOpts.AddLifetime)
2049 return;
2050
2051 // We need to perform the scope leaving in reverse order
2052 SmallVector<VarDecl *, 10> DeclsTrivial;
2053 DeclsTrivial.reserve(N: B.distance(L: E));
2054
2055 // Objects with trivial destructor ends their lifetime when their storage
2056 // is destroyed, for automatic variables, this happens when the end of the
2057 // scope is added.
2058 for (VarDecl* D : llvm::make_range(x: B, y: E))
2059 if (!needsAutomaticDestruction(VD: D))
2060 DeclsTrivial.push_back(Elt: D);
2061
2062 if (DeclsTrivial.empty())
2063 return;
2064
2065 autoCreateBlock();
2066 for (VarDecl *VD : llvm::reverse(C&: DeclsTrivial))
2067 appendLifetimeEnds(B: Block, VD, S);
2068}
2069
2070/// addScopeChangesHandling - appends information about destruction, lifetime
2071/// and cfgScopeEnd for variables in the scope that was left by the jump, and
2072/// appends cfgScopeBegin for all scopes that where entered.
2073/// We insert the cfgScopeBegin at the end of the jump node, as depending on
2074/// the sourceBlock, each goto, may enter different amount of scopes.
2075void CFGBuilder::addScopeChangesHandling(LocalScope::const_iterator SrcPos,
2076 LocalScope::const_iterator DstPos,
2077 Stmt *S) {
2078 assert(Block && "Source block should be always crated");
2079 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2080 !BuildOpts.AddScopes) {
2081 return;
2082 }
2083
2084 if (SrcPos == DstPos)
2085 return;
2086
2087 // Get common scope, the jump leaves all scopes [SrcPos, BasePos), and
2088 // enter all scopes between [DstPos, BasePos)
2089 LocalScope::const_iterator BasePos = SrcPos.shared_parent(L: DstPos);
2090
2091 // Append scope begins for scopes entered by goto
2092 if (BuildOpts.AddScopes && !DstPos.inSameLocalScope(rhs: BasePos)) {
2093 for (LocalScope::const_iterator I = DstPos; I != BasePos; ++I)
2094 if (I.pointsToFirstDeclaredVar())
2095 appendScopeBegin(B: Block, VD: *I, S);
2096 }
2097
2098 // Append scopeEnds, destructor and lifetime with the terminator for
2099 // block left by goto.
2100 addAutomaticObjHandling(B: SrcPos, E: BasePos, S);
2101}
2102
2103void CFGBuilder::addFullExprCleanupMarker(TempDtorContext &Context,
2104 const ExprWithCleanups *CleanupExpr) {
2105 CFGFullExprCleanup::MTEVecTy *ExpiringMTEs = nullptr;
2106 BumpVectorContext &BVC = cfg->getBumpVectorContext();
2107
2108 size_t NumCollected = Context.CollectedMTEs.size();
2109 if (NumCollected > 0) {
2110 autoCreateBlock();
2111 ExpiringMTEs = new (cfg->getAllocator())
2112 CFGFullExprCleanup::MTEVecTy(BVC, NumCollected);
2113 for (const MaterializeTemporaryExpr *MTE : Context.CollectedMTEs)
2114 ExpiringMTEs->push_back(Elt: MTE, C&: BVC);
2115 Block->appendFullExprCleanup(BV: ExpiringMTEs, CleanupExpr, C&: BVC);
2116 }
2117}
2118
2119/// createScopeChangesHandlingBlock - Creates a block with cfgElements
2120/// corresponding to changing the scope from the source scope of the GotoStmt,
2121/// to destination scope. Add destructor, lifetime and cfgScopeEnd
2122/// CFGElements to newly created CFGBlock, that will have the CFG terminator
2123/// transferred.
2124CFGBlock *CFGBuilder::createScopeChangesHandlingBlock(
2125 LocalScope::const_iterator SrcPos, CFGBlock *SrcBlk,
2126 LocalScope::const_iterator DstPos, CFGBlock *DstBlk) {
2127 if (SrcPos == DstPos)
2128 return DstBlk;
2129
2130 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2131 (!BuildOpts.AddScopes || SrcPos.inSameLocalScope(rhs: DstPos)))
2132 return DstBlk;
2133
2134 // We will update CFBBuilder when creating new block, restore the
2135 // previous state at exit.
2136 SaveAndRestore save_Block(Block), save_Succ(Succ);
2137
2138 // Create a new block, and transfer terminator
2139 Block = createBlock(add_successor: false);
2140 Block->setTerminator(SrcBlk->getTerminator());
2141 SrcBlk->setTerminator(CFGTerminator());
2142 addSuccessor(B: Block, S: DstBlk);
2143
2144 // Fill the created Block with the required elements.
2145 addScopeChangesHandling(SrcPos, DstPos, S: Block->getTerminatorStmt());
2146
2147 assert(Block && "There should be at least one scope changing Block");
2148 return Block;
2149}
2150
2151/// addImplicitDtorsForDestructor - Add implicit destructors generated for
2152/// base and member objects in destructor.
2153void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
2154 assert(BuildOpts.AddImplicitDtors &&
2155 "Can be called only when dtors should be added");
2156 const CXXRecordDecl *RD = DD->getParent();
2157
2158 // At the end destroy virtual base objects.
2159 for (const auto &VI : RD->vbases()) {
2160 // TODO: Add a VirtualBaseBranch to see if the most derived class
2161 // (which is different from the current class) is responsible for
2162 // destroying them.
2163 const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl();
2164 if (CD && !CD->hasTrivialDestructor()) {
2165 autoCreateBlock();
2166 appendBaseDtor(B: Block, BS: &VI);
2167 }
2168 }
2169
2170 // Before virtual bases destroy direct base objects.
2171 for (const auto &BI : RD->bases()) {
2172 if (!BI.isVirtual()) {
2173 const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl();
2174 if (CD && !CD->hasTrivialDestructor()) {
2175 autoCreateBlock();
2176 appendBaseDtor(B: Block, BS: &BI);
2177 }
2178 }
2179 }
2180
2181 // First destroy member objects.
2182 if (RD->isUnion())
2183 return;
2184 for (auto *FI : RD->fields()) {
2185 // Check for constant size array. Set type to array element type.
2186 QualType QT = FI->getType();
2187 // It may be a multidimensional array.
2188 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(T: QT)) {
2189 if (AT->isZeroSize())
2190 break;
2191 QT = AT->getElementType();
2192 }
2193
2194 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
2195 if (!CD->hasTrivialDestructor()) {
2196 autoCreateBlock();
2197 appendMemberDtor(B: Block, FD: FI);
2198 }
2199 }
2200}
2201
2202/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
2203/// way return valid LocalScope object.
2204LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
2205 if (Scope)
2206 return Scope;
2207 llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
2208 return new (alloc) LocalScope(BumpVectorContext(alloc), ScopePos);
2209}
2210
2211/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
2212/// that should create implicit scope (e.g. if/else substatements).
2213void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
2214 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2215 !BuildOpts.AddScopes)
2216 return;
2217
2218 LocalScope *Scope = nullptr;
2219
2220 // For compound statement we will be creating explicit scope.
2221 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(Val: S)) {
2222 for (auto *BI : CS->body()) {
2223 Stmt *SI = BI->stripLabelLikeStatements();
2224 if (DeclStmt *DS = dyn_cast<DeclStmt>(Val: SI))
2225 Scope = addLocalScopeForDeclStmt(DS, Scope);
2226 }
2227 return;
2228 }
2229
2230 // For any other statement scope will be implicit and as such will be
2231 // interesting only for DeclStmt.
2232 if (DeclStmt *DS = dyn_cast<DeclStmt>(Val: S->stripLabelLikeStatements()))
2233 addLocalScopeForDeclStmt(DS);
2234}
2235
2236/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
2237/// reuse Scope if not NULL.
2238LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
2239 LocalScope* Scope) {
2240 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2241 !BuildOpts.AddScopes)
2242 return Scope;
2243
2244 for (auto *DI : DS->decls())
2245 if (VarDecl *VD = dyn_cast<VarDecl>(Val: DI))
2246 Scope = addLocalScopeForVarDecl(VD, Scope);
2247 return Scope;
2248}
2249
2250bool CFGBuilder::needsAutomaticDestruction(const VarDecl *VD) const {
2251 return !hasTrivialDestructor(VD) || VD->hasAttr<CleanupAttr>();
2252}
2253
2254bool CFGBuilder::hasTrivialDestructor(const VarDecl *VD) const {
2255 // Check for const references bound to temporary. Set type to pointee.
2256 QualType QT = VD->getType();
2257 if (QT->isReferenceType()) {
2258 // Attempt to determine whether this declaration lifetime-extends a
2259 // temporary.
2260 //
2261 // FIXME: This is incorrect. Non-reference declarations can lifetime-extend
2262 // temporaries, and a single declaration can extend multiple temporaries.
2263 // We should look at the storage duration on each nested
2264 // MaterializeTemporaryExpr instead.
2265
2266 const Expr *Init = VD->getInit();
2267 if (!Init) {
2268 // Probably an exception catch-by-reference variable.
2269 // FIXME: It doesn't really mean that the object has a trivial destructor.
2270 // Also are there other cases?
2271 return true;
2272 }
2273
2274 // Lifetime-extending a temporary?
2275 bool FoundMTE = false;
2276 QT = getReferenceInitTemporaryType(Init, FoundMTE: &FoundMTE);
2277 if (!FoundMTE)
2278 return true;
2279 }
2280
2281 // Check for constant size array. Set type to array element type.
2282 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(T: QT)) {
2283 if (AT->isZeroSize())
2284 return true;
2285 QT = AT->getElementType();
2286 }
2287
2288 // Check if type is a C++ class with non-trivial destructor.
2289 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
2290 return !CD->hasDefinition() || CD->hasTrivialDestructor();
2291 return true;
2292}
2293
2294/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
2295/// create add scope for automatic objects and temporary objects bound to
2296/// const reference. Will reuse Scope if not NULL.
2297LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
2298 LocalScope* Scope) {
2299 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2300 !BuildOpts.AddScopes)
2301 return Scope;
2302
2303 // Check if variable is local.
2304 if (!VD->hasLocalStorage())
2305 return Scope;
2306
2307 // Reference parameters are aliases to objects that live elsewhere, so they
2308 // don't require automatic destruction or lifetime tracking.
2309 if (isa<ParmVarDecl>(Val: VD) && VD->getType()->isReferenceType())
2310 return Scope;
2311
2312 if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes &&
2313 !needsAutomaticDestruction(VD)) {
2314 assert(BuildOpts.AddImplicitDtors);
2315 return Scope;
2316 }
2317
2318 // Add the variable to scope
2319 Scope = createOrReuseLocalScope(Scope);
2320 Scope->addVar(VD);
2321 ScopePos = Scope->begin();
2322 return Scope;
2323}
2324
2325/// addLocalScopeAndDtors - For given statement add local scope for it and
2326/// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
2327void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
2328 LocalScope::const_iterator scopeBeginPos = ScopePos;
2329 addLocalScopeForStmt(S);
2330 addAutomaticObjHandling(B: ScopePos, E: scopeBeginPos, S);
2331}
2332
2333/// Visit - Walk the subtree of a statement and add extra
2334/// blocks for ternary operators, &&, and ||. We also process "," and
2335/// DeclStmts (which may contain nested control-flow).
2336CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc,
2337 bool ExternallyDestructed) {
2338 if (!S) {
2339 badCFG = true;
2340 return nullptr;
2341 }
2342
2343 if (Expr *E = dyn_cast<Expr>(Val: S))
2344 S = E->IgnoreParens();
2345
2346 if (Context->getLangOpts().OpenMP)
2347 if (auto *D = dyn_cast<OMPExecutableDirective>(Val: S))
2348 return VisitOMPExecutableDirective(D, asc);
2349
2350 switch (S->getStmtClass()) {
2351 default:
2352 return VisitStmt(S, asc);
2353
2354 case Stmt::ImplicitValueInitExprClass:
2355 if (BuildOpts.OmitImplicitValueInitializers)
2356 return Block;
2357 return VisitStmt(S, asc);
2358
2359 case Stmt::InitListExprClass:
2360 return VisitInitListExpr(ILE: cast<InitListExpr>(Val: S), asc);
2361
2362 case Stmt::AttributedStmtClass:
2363 return VisitAttributedStmt(A: cast<AttributedStmt>(Val: S), asc);
2364
2365 case Stmt::AddrLabelExprClass:
2366 return VisitAddrLabelExpr(A: cast<AddrLabelExpr>(Val: S), asc);
2367
2368 case Stmt::BinaryConditionalOperatorClass:
2369 return VisitConditionalOperator(C: cast<BinaryConditionalOperator>(Val: S), asc);
2370
2371 case Stmt::BinaryOperatorClass:
2372 case Stmt::CompoundAssignOperatorClass:
2373 return VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), asc);
2374
2375 case Stmt::BlockExprClass:
2376 return VisitBlockExpr(E: cast<BlockExpr>(Val: S), asc);
2377
2378 case Stmt::BreakStmtClass:
2379 return VisitBreakStmt(B: cast<BreakStmt>(Val: S));
2380
2381 case Stmt::CallExprClass:
2382 case Stmt::CXXOperatorCallExprClass:
2383 case Stmt::CXXMemberCallExprClass:
2384 case Stmt::UserDefinedLiteralClass:
2385 return VisitCallExpr(C: cast<CallExpr>(Val: S), asc);
2386
2387 case Stmt::CaseStmtClass:
2388 return VisitCaseStmt(C: cast<CaseStmt>(Val: S));
2389
2390 case Stmt::ChooseExprClass:
2391 return VisitChooseExpr(C: cast<ChooseExpr>(Val: S), asc);
2392
2393 case Stmt::CompoundStmtClass:
2394 return VisitCompoundStmt(C: cast<CompoundStmt>(Val: S), ExternallyDestructed);
2395
2396 case Stmt::ConditionalOperatorClass:
2397 return VisitConditionalOperator(C: cast<ConditionalOperator>(Val: S), asc);
2398
2399 case Stmt::ContinueStmtClass:
2400 return VisitContinueStmt(C: cast<ContinueStmt>(Val: S));
2401
2402 case Stmt::CXXCatchStmtClass:
2403 return VisitCXXCatchStmt(S: cast<CXXCatchStmt>(Val: S));
2404
2405 case Stmt::ExprWithCleanupsClass:
2406 return VisitExprWithCleanups(E: cast<ExprWithCleanups>(Val: S),
2407 asc, ExternallyDestructed);
2408
2409 case Stmt::CXXDefaultArgExprClass:
2410 case Stmt::CXXDefaultInitExprClass:
2411 // FIXME: The expression inside a CXXDefaultArgExpr is owned by the
2412 // called function's declaration, not by the caller. If we simply add
2413 // this expression to the CFG, we could end up with the same Expr
2414 // appearing multiple times (PR13385).
2415 //
2416 // It's likewise possible for multiple CXXDefaultInitExprs for the same
2417 // expression to be used in the same function (through aggregate
2418 // initialization).
2419 return VisitStmt(S, asc);
2420
2421 case Stmt::CXXBindTemporaryExprClass:
2422 return VisitCXXBindTemporaryExpr(E: cast<CXXBindTemporaryExpr>(Val: S), asc);
2423
2424 case Stmt::CXXConstructExprClass:
2425 return VisitCXXConstructExpr(C: cast<CXXConstructExpr>(Val: S), asc);
2426
2427 case Stmt::CXXNewExprClass:
2428 return VisitCXXNewExpr(DE: cast<CXXNewExpr>(Val: S), asc);
2429
2430 case Stmt::CXXDeleteExprClass:
2431 return VisitCXXDeleteExpr(DE: cast<CXXDeleteExpr>(Val: S), asc);
2432
2433 case Stmt::CXXFunctionalCastExprClass:
2434 return VisitCXXFunctionalCastExpr(E: cast<CXXFunctionalCastExpr>(Val: S), asc);
2435
2436 case Stmt::CXXTemporaryObjectExprClass:
2437 return VisitCXXTemporaryObjectExpr(C: cast<CXXTemporaryObjectExpr>(Val: S), asc);
2438
2439 case Stmt::CXXThrowExprClass:
2440 return VisitCXXThrowExpr(T: cast<CXXThrowExpr>(Val: S));
2441
2442 case Stmt::CXXTryStmtClass:
2443 return VisitCXXTryStmt(S: cast<CXXTryStmt>(Val: S));
2444
2445 case Stmt::CXXTypeidExprClass:
2446 return VisitCXXTypeidExpr(S: cast<CXXTypeidExpr>(Val: S), asc);
2447
2448 case Stmt::CXXForRangeStmtClass:
2449 return VisitCXXForRangeStmt(S: cast<CXXForRangeStmt>(Val: S));
2450
2451 case Stmt::DeclStmtClass:
2452 return VisitDeclStmt(DS: cast<DeclStmt>(Val: S));
2453
2454 case Stmt::DefaultStmtClass:
2455 return VisitDefaultStmt(D: cast<DefaultStmt>(Val: S));
2456
2457 case Stmt::DoStmtClass:
2458 return VisitDoStmt(D: cast<DoStmt>(Val: S));
2459
2460 case Stmt::ForStmtClass:
2461 return VisitForStmt(F: cast<ForStmt>(Val: S));
2462
2463 case Stmt::GotoStmtClass:
2464 return VisitGotoStmt(G: cast<GotoStmt>(Val: S));
2465
2466 case Stmt::GCCAsmStmtClass:
2467 return VisitGCCAsmStmt(G: cast<GCCAsmStmt>(Val: S), asc);
2468
2469 case Stmt::IfStmtClass:
2470 return VisitIfStmt(I: cast<IfStmt>(Val: S));
2471
2472 case Stmt::ImplicitCastExprClass:
2473 return VisitImplicitCastExpr(E: cast<ImplicitCastExpr>(Val: S), asc);
2474
2475 case Stmt::ConstantExprClass:
2476 return VisitConstantExpr(E: cast<ConstantExpr>(Val: S), asc);
2477
2478 case Stmt::IndirectGotoStmtClass:
2479 return VisitIndirectGotoStmt(I: cast<IndirectGotoStmt>(Val: S));
2480
2481 case Stmt::LabelStmtClass:
2482 return VisitLabelStmt(L: cast<LabelStmt>(Val: S));
2483
2484 case Stmt::LambdaExprClass:
2485 return VisitLambdaExpr(E: cast<LambdaExpr>(Val: S), asc);
2486
2487 case Stmt::MaterializeTemporaryExprClass:
2488 return VisitMaterializeTemporaryExpr(MTE: cast<MaterializeTemporaryExpr>(Val: S),
2489 asc);
2490
2491 case Stmt::MemberExprClass:
2492 return VisitMemberExpr(M: cast<MemberExpr>(Val: S), asc);
2493
2494 case Stmt::NullStmtClass:
2495 return Block;
2496
2497 case Stmt::ObjCAtCatchStmtClass:
2498 return VisitObjCAtCatchStmt(S: cast<ObjCAtCatchStmt>(Val: S));
2499
2500 case Stmt::ObjCAutoreleasePoolStmtClass:
2501 return VisitObjCAutoreleasePoolStmt(S: cast<ObjCAutoreleasePoolStmt>(Val: S));
2502
2503 case Stmt::ObjCAtSynchronizedStmtClass:
2504 return VisitObjCAtSynchronizedStmt(S: cast<ObjCAtSynchronizedStmt>(Val: S));
2505
2506 case Stmt::ObjCAtThrowStmtClass:
2507 return VisitObjCAtThrowStmt(S: cast<ObjCAtThrowStmt>(Val: S));
2508
2509 case Stmt::ObjCAtTryStmtClass:
2510 return VisitObjCAtTryStmt(S: cast<ObjCAtTryStmt>(Val: S));
2511
2512 case Stmt::ObjCForCollectionStmtClass:
2513 return VisitObjCForCollectionStmt(S: cast<ObjCForCollectionStmt>(Val: S));
2514
2515 case Stmt::ObjCMessageExprClass:
2516 return VisitObjCMessageExpr(E: cast<ObjCMessageExpr>(Val: S), asc);
2517
2518 case Stmt::OpaqueValueExprClass:
2519 return Block;
2520
2521 case Stmt::PseudoObjectExprClass:
2522 return VisitPseudoObjectExpr(E: cast<PseudoObjectExpr>(Val: S));
2523
2524 case Stmt::ReturnStmtClass:
2525 case Stmt::CoreturnStmtClass:
2526 return VisitReturnStmt(S);
2527
2528 case Stmt::CoyieldExprClass:
2529 case Stmt::CoawaitExprClass:
2530 return VisitCoroutineSuspendExpr(S: cast<CoroutineSuspendExpr>(Val: S), asc);
2531
2532 case Stmt::SEHExceptStmtClass:
2533 return VisitSEHExceptStmt(S: cast<SEHExceptStmt>(Val: S));
2534
2535 case Stmt::SEHFinallyStmtClass:
2536 return VisitSEHFinallyStmt(S: cast<SEHFinallyStmt>(Val: S));
2537
2538 case Stmt::SEHLeaveStmtClass:
2539 return VisitSEHLeaveStmt(S: cast<SEHLeaveStmt>(Val: S));
2540
2541 case Stmt::SEHTryStmtClass:
2542 return VisitSEHTryStmt(S: cast<SEHTryStmt>(Val: S));
2543
2544 case Stmt::UnaryExprOrTypeTraitExprClass:
2545 return VisitUnaryExprOrTypeTraitExpr(E: cast<UnaryExprOrTypeTraitExpr>(Val: S),
2546 asc);
2547
2548 case Stmt::StmtExprClass:
2549 return VisitStmtExpr(S: cast<StmtExpr>(Val: S), asc);
2550
2551 case Stmt::SwitchStmtClass:
2552 return VisitSwitchStmt(S: cast<SwitchStmt>(Val: S));
2553
2554 case Stmt::UnaryOperatorClass:
2555 return VisitUnaryOperator(U: cast<UnaryOperator>(Val: S), asc);
2556
2557 case Stmt::WhileStmtClass:
2558 return VisitWhileStmt(W: cast<WhileStmt>(Val: S));
2559
2560 case Stmt::ArrayInitLoopExprClass:
2561 return VisitArrayInitLoopExpr(A: cast<ArrayInitLoopExpr>(Val: S), asc);
2562 }
2563}
2564
2565CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
2566 if (asc.alwaysAdd(builder&: *this, stmt: S)) {
2567 autoCreateBlock();
2568 appendStmt(B: Block, S);
2569 }
2570
2571 return VisitChildren(S);
2572}
2573
2574/// VisitChildren - Visit the children of a Stmt.
2575CFGBlock *CFGBuilder::VisitChildren(Stmt *S) {
2576 CFGBlock *B = Block;
2577
2578 // Visit the children in their reverse order so that they appear in
2579 // left-to-right (natural) order in the CFG.
2580 reverse_children RChildren(S, *Context);
2581 for (Stmt *Child : RChildren) {
2582 if (Child)
2583 if (CFGBlock *R = Visit(S: Child))
2584 B = R;
2585 }
2586 return B;
2587}
2588
2589CFGBlock *CFGBuilder::VisitCallExprChildren(CallExpr *C) {
2590 // For overloaded assignment operators, visit arguments in reverse order (LHS
2591 // then RHS) so that RHS is sequenced before LHS in the CFG, matching C++17
2592 // sequencing rules.
2593 if (auto *OCE = dyn_cast<CXXOperatorCallExpr>(Val: C);
2594 OCE && OCE->isAssignmentOp()) {
2595 Visit(S: OCE->getArg(Arg: 0));
2596 Visit(S: OCE->getArg(Arg: 1));
2597 return Visit(S: OCE->getCallee());
2598 }
2599 return VisitChildren(S: C);
2600}
2601
2602CFGBlock *CFGBuilder::VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc) {
2603 if (asc.alwaysAdd(builder&: *this, stmt: ILE)) {
2604 autoCreateBlock();
2605 appendStmt(B: Block, S: ILE);
2606 }
2607 CFGBlock *B = Block;
2608
2609 reverse_children RChildren(ILE, *Context);
2610 for (Stmt *Child : RChildren) {
2611 if (!Child)
2612 continue;
2613 if (CFGBlock *R = Visit(S: Child))
2614 B = R;
2615 if (BuildOpts.AddCXXDefaultInitExprInAggregates) {
2616 if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Val: Child))
2617 if (Stmt *Child = DIE->getExpr())
2618 if (CFGBlock *R = Visit(S: Child))
2619 B = R;
2620 }
2621 }
2622 return B;
2623}
2624
2625CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
2626 AddStmtChoice asc) {
2627 AddressTakenLabels.insert(X: A->getLabel());
2628
2629 if (asc.alwaysAdd(builder&: *this, stmt: A)) {
2630 autoCreateBlock();
2631 appendStmt(B: Block, S: A);
2632 }
2633
2634 return Block;
2635}
2636
2637static bool isFallthroughStatement(const AttributedStmt *A) {
2638 bool isFallthrough = hasSpecificAttr<FallThroughAttr>(container: A->getAttrs());
2639 assert((!isFallthrough || isa<NullStmt>(A->getSubStmt())) &&
2640 "expected fallthrough not to have children");
2641 return isFallthrough;
2642}
2643
2644static bool isCXXAssumeAttr(const AttributedStmt *A) {
2645 bool hasAssumeAttr = hasSpecificAttr<CXXAssumeAttr>(container: A->getAttrs());
2646
2647 assert((!hasAssumeAttr || isa<NullStmt>(A->getSubStmt())) &&
2648 "expected [[assume]] not to have children");
2649 return hasAssumeAttr;
2650}
2651
2652CFGBlock *CFGBuilder::VisitAttributedStmt(AttributedStmt *A,
2653 AddStmtChoice asc) {
2654 // AttributedStmts for [[likely]] can have arbitrary statements as children,
2655 // and the current visitation order here would add the AttributedStmts
2656 // for [[likely]] after the child nodes, which is undesirable: For example,
2657 // if the child contains an unconditional return, the [[likely]] would be
2658 // considered unreachable.
2659 // So only add the AttributedStmt for FallThrough, which has CFG effects and
2660 // also no children, and omit the others. None of the other current StmtAttrs
2661 // have semantic meaning for the CFG.
2662 bool isInterestingAttribute = isFallthroughStatement(A) || isCXXAssumeAttr(A);
2663 if (isInterestingAttribute && asc.alwaysAdd(builder&: *this, stmt: A)) {
2664 autoCreateBlock();
2665 appendStmt(B: Block, S: A);
2666 }
2667
2668 return VisitChildren(S: A);
2669}
2670
2671CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc) {
2672 if (asc.alwaysAdd(builder&: *this, stmt: U)) {
2673 autoCreateBlock();
2674 appendStmt(B: Block, S: U);
2675 }
2676
2677 if (U->getOpcode() == UO_LNot)
2678 tryEvaluateBool(S: U->getSubExpr()->IgnoreParens());
2679
2680 return Visit(S: U->getSubExpr(), asc: AddStmtChoice());
2681}
2682
2683CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) {
2684 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2685 appendStmt(B: ConfluenceBlock, S: B);
2686
2687 if (badCFG)
2688 return nullptr;
2689
2690 return VisitLogicalOperator(B, Term: nullptr, TrueBlock: ConfluenceBlock,
2691 FalseBlock: ConfluenceBlock).first;
2692}
2693
2694std::pair<CFGBlock*, CFGBlock*>
2695CFGBuilder::VisitLogicalOperator(BinaryOperator *B,
2696 Stmt *Term,
2697 CFGBlock *TrueBlock,
2698 CFGBlock *FalseBlock) {
2699 // Introspect the RHS. If it is a nested logical operation, we recursively
2700 // build the CFG using this function. Otherwise, resort to default
2701 // CFG construction behavior.
2702 Expr *RHS = B->getRHS()->IgnoreParens();
2703 CFGBlock *RHSBlock, *ExitBlock;
2704
2705 do {
2706 if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(Val: RHS))
2707 if (B_RHS->isLogicalOp()) {
2708 std::tie(args&: RHSBlock, args&: ExitBlock) =
2709 VisitLogicalOperator(B: B_RHS, Term, TrueBlock, FalseBlock);
2710 break;
2711 }
2712
2713 // The RHS is not a nested logical operation. Don't push the terminator
2714 // down further, but instead visit RHS and construct the respective
2715 // pieces of the CFG, and link up the RHSBlock with the terminator
2716 // we have been provided.
2717 ExitBlock = RHSBlock = createBlock(add_successor: false);
2718
2719 // Even though KnownVal is only used in the else branch of the next
2720 // conditional, tryEvaluateBool performs additional checking on the
2721 // Expr, so it should be called unconditionally.
2722 TryResult KnownVal = tryEvaluateBool(S: RHS);
2723 if (!KnownVal.isKnown())
2724 KnownVal = tryEvaluateBool(S: B);
2725
2726 if (!Term) {
2727 assert(TrueBlock == FalseBlock);
2728 addSuccessor(B: RHSBlock, S: TrueBlock);
2729 }
2730 else {
2731 RHSBlock->setTerminator(Term);
2732 addSuccessor(B: RHSBlock, S: TrueBlock, IsReachable: !KnownVal.isFalse());
2733 addSuccessor(B: RHSBlock, S: FalseBlock, IsReachable: !KnownVal.isTrue());
2734 }
2735
2736 Block = RHSBlock;
2737 RHSBlock = addStmt(S: RHS);
2738 }
2739 while (false);
2740
2741 if (badCFG)
2742 return std::make_pair(x: nullptr, y: nullptr);
2743
2744 // Generate the blocks for evaluating the LHS.
2745 Expr *LHS = B->getLHS()->IgnoreParens();
2746
2747 if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(Val: LHS))
2748 if (B_LHS->isLogicalOp()) {
2749 if (B->getOpcode() == BO_LOr)
2750 FalseBlock = RHSBlock;
2751 else
2752 TrueBlock = RHSBlock;
2753
2754 // For the LHS, treat 'B' as the terminator that we want to sink
2755 // into the nested branch. The RHS always gets the top-most
2756 // terminator.
2757 return VisitLogicalOperator(B: B_LHS, Term: B, TrueBlock, FalseBlock);
2758 }
2759
2760 // Create the block evaluating the LHS.
2761 // This contains the '&&' or '||' as the terminator.
2762 CFGBlock *LHSBlock = createBlock(add_successor: false);
2763 LHSBlock->setTerminator(B);
2764
2765 Block = LHSBlock;
2766 CFGBlock *EntryLHSBlock = addStmt(S: LHS);
2767
2768 if (badCFG)
2769 return std::make_pair(x: nullptr, y: nullptr);
2770
2771 // See if this is a known constant.
2772 TryResult KnownVal = tryEvaluateBool(S: LHS);
2773
2774 // Now link the LHSBlock with RHSBlock.
2775 if (B->getOpcode() == BO_LOr) {
2776 addSuccessor(B: LHSBlock, S: TrueBlock, IsReachable: !KnownVal.isFalse());
2777 addSuccessor(B: LHSBlock, S: RHSBlock, IsReachable: !KnownVal.isTrue());
2778 } else {
2779 assert(B->getOpcode() == BO_LAnd);
2780 addSuccessor(B: LHSBlock, S: RHSBlock, IsReachable: !KnownVal.isFalse());
2781 addSuccessor(B: LHSBlock, S: FalseBlock, IsReachable: !KnownVal.isTrue());
2782 }
2783
2784 return std::make_pair(x&: EntryLHSBlock, y&: ExitBlock);
2785}
2786
2787CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
2788 AddStmtChoice asc) {
2789 // && or ||
2790 if (B->isLogicalOp())
2791 return VisitLogicalOperator(B);
2792
2793 if (B->getOpcode() == BO_Comma) { // ,
2794 autoCreateBlock();
2795 appendStmt(B: Block, S: B);
2796 addStmt(S: B->getRHS());
2797 return addStmt(S: B->getLHS());
2798 }
2799
2800 if (B->isAssignmentOp()) {
2801 if (asc.alwaysAdd(builder&: *this, stmt: B)) {
2802 autoCreateBlock();
2803 appendStmt(B: Block, S: B);
2804 }
2805 Visit(S: B->getLHS());
2806 return Visit(S: B->getRHS());
2807 }
2808
2809 if (asc.alwaysAdd(builder&: *this, stmt: B)) {
2810 autoCreateBlock();
2811 appendStmt(B: Block, S: B);
2812 }
2813
2814 if (B->isEqualityOp() || B->isRelationalOp())
2815 tryEvaluateBool(S: B);
2816
2817 CFGBlock *RBlock = Visit(S: B->getRHS());
2818 CFGBlock *LBlock = Visit(S: B->getLHS());
2819 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
2820 // containing a DoStmt, and the LHS doesn't create a new block, then we should
2821 // return RBlock. Otherwise we'll incorrectly return NULL.
2822 return (LBlock ? LBlock : RBlock);
2823}
2824
2825CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) {
2826 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
2827 autoCreateBlock();
2828 appendStmt(B: Block, S: E);
2829 }
2830 return Block;
2831}
2832
2833CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
2834 // "break" is a control-flow statement. Thus we stop processing the current
2835 // block.
2836 if (badCFG)
2837 return nullptr;
2838
2839 // Now create a new block that ends with the break statement.
2840 Block = createBlock(add_successor: false);
2841 Block->setTerminator(B);
2842
2843 // If there is no target for the break, then we are looking at an incomplete
2844 // AST. This means that the CFG cannot be constructed.
2845 if (BreakJumpTarget.block) {
2846 addAutomaticObjHandling(B: ScopePos, E: BreakJumpTarget.scopePosition, S: B);
2847 addSuccessor(B: Block, S: BreakJumpTarget.block);
2848 } else
2849 badCFG = true;
2850
2851 return Block;
2852}
2853
2854static bool CanThrow(Expr *E, ASTContext &Ctx) {
2855 QualType Ty = E->getType();
2856 if (Ty->isFunctionPointerType() || Ty->isBlockPointerType())
2857 Ty = Ty->getPointeeType();
2858
2859 const FunctionType *FT = Ty->getAs<FunctionType>();
2860 if (FT) {
2861 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(Val: FT))
2862 if (!isUnresolvedExceptionSpec(ESpecType: Proto->getExceptionSpecType()) &&
2863 Proto->isNothrow())
2864 return false;
2865 }
2866 return true;
2867}
2868
2869static bool isBuiltinAssumeWithSideEffects(const ASTContext &Ctx,
2870 const CallExpr *CE) {
2871 unsigned BuiltinID = CE->getBuiltinCallee();
2872 if (BuiltinID != Builtin::BI__assume &&
2873 BuiltinID != Builtin::BI__builtin_assume)
2874 return false;
2875
2876 return CE->getArg(Arg: 0)->HasSideEffects(Ctx);
2877}
2878
2879CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
2880 // Compute the callee type.
2881 QualType calleeType = C->getCallee()->getType();
2882 if (calleeType == Context->BoundMemberTy) {
2883 QualType boundType = Expr::findBoundMemberType(expr: C->getCallee());
2884
2885 // We should only get a null bound type if processing a dependent
2886 // CFG. Recover by assuming nothing.
2887 if (!boundType.isNull()) calleeType = boundType;
2888 }
2889
2890 // If this is a call to a no-return function, this stops the block here.
2891 bool NoReturn = getFunctionExtInfo(t: *calleeType).getNoReturn();
2892 bool AnalyzerNoReturn = false;
2893
2894 bool AddEHEdge = false;
2895
2896 // Languages without exceptions are assumed to not throw.
2897 if (Context->getLangOpts().Exceptions) {
2898 if (BuildOpts.AddEHEdges)
2899 AddEHEdge = true;
2900 }
2901
2902 // If this is a call to a builtin function, it might not actually evaluate
2903 // its arguments. Don't add them to the CFG if this is the case.
2904 bool OmitArguments = false;
2905
2906 if (FunctionDecl *FD = C->getDirectCallee()) {
2907 // TODO: Support construction contexts for variadic function arguments.
2908 // These are a bit problematic and not very useful because passing
2909 // C++ objects as C-style variadic arguments doesn't work in general
2910 // (see [expr.call]).
2911 if (!FD->isVariadic())
2912 findConstructionContextsForArguments(E: C);
2913
2914 if (FD->isNoReturn() || C->isBuiltinAssumeFalse(Ctx: *Context))
2915 NoReturn = true;
2916 else if (FD->isAnalyzerNoReturn())
2917 AnalyzerNoReturn = true;
2918 if (FD->hasAttr<NoThrowAttr>())
2919 AddEHEdge = false;
2920 if (isBuiltinAssumeWithSideEffects(Ctx: FD->getASTContext(), CE: C) ||
2921 FD->getBuiltinID() == Builtin::BI__builtin_object_size ||
2922 FD->getBuiltinID() == Builtin::BI__builtin_dynamic_object_size)
2923 OmitArguments = true;
2924 }
2925
2926 if (!CanThrow(E: C->getCallee(), Ctx&: *Context))
2927 AddEHEdge = false;
2928
2929 if (OmitArguments) {
2930 assert(!NoReturn && !AnalyzerNoReturn &&
2931 "noreturn calls with unevaluated args not implemented");
2932 assert(!AddEHEdge && "EH calls with unevaluated args not implemented");
2933 autoCreateBlock();
2934 appendStmt(B: Block, S: C);
2935 return Visit(S: C->getCallee());
2936 }
2937
2938 if (!NoReturn && !AnalyzerNoReturn && !AddEHEdge) {
2939 autoCreateBlock();
2940 appendCall(B: Block, CE: C);
2941
2942 return VisitCallExprChildren(C);
2943 }
2944
2945 if (Block) {
2946 Succ = Block;
2947 if (badCFG)
2948 return nullptr;
2949 }
2950
2951 if (NoReturn)
2952 Block = createNoReturnBlock(/*AnalyzerOnly=*/false);
2953 else if (AnalyzerNoReturn)
2954 Block = createNoReturnBlock(/*AnalyzerOnly=*/true);
2955 else
2956 Block = createBlock();
2957
2958 appendCall(B: Block, CE: C);
2959
2960 if (AddEHEdge) {
2961 // Add exceptional edges.
2962 if (TryTerminatedBlock)
2963 addSuccessor(B: Block, S: TryTerminatedBlock);
2964 else
2965 addSuccessor(B: Block, S: &cfg->getExit());
2966 }
2967
2968 return VisitCallExprChildren(C);
2969}
2970
2971CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
2972 AddStmtChoice asc) {
2973 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2974 appendStmt(B: ConfluenceBlock, S: C);
2975 if (badCFG)
2976 return nullptr;
2977
2978 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(alwaysAdd: true);
2979 Succ = ConfluenceBlock;
2980 Block = nullptr;
2981 CFGBlock *LHSBlock = Visit(S: C->getLHS(), asc: alwaysAdd);
2982 if (badCFG)
2983 return nullptr;
2984
2985 Succ = ConfluenceBlock;
2986 Block = nullptr;
2987 CFGBlock *RHSBlock = Visit(S: C->getRHS(), asc: alwaysAdd);
2988 if (badCFG)
2989 return nullptr;
2990
2991 Block = createBlock(add_successor: false);
2992 // See if this is a known constant.
2993 const TryResult& KnownVal = tryEvaluateBool(S: C->getCond());
2994 addSuccessor(B: Block, S: KnownVal.isFalse() ? nullptr : LHSBlock);
2995 addSuccessor(B: Block, S: KnownVal.isTrue() ? nullptr : RHSBlock);
2996 Block->setTerminator(C);
2997 return addStmt(S: C->getCond());
2998}
2999
3000CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C,
3001 bool ExternallyDestructed) {
3002 LocalScope::const_iterator scopeBeginPos = ScopePos;
3003 addLocalScopeForStmt(S: C);
3004
3005 if (!C->body_empty() && !isa<ReturnStmt>(Val: *C->body_rbegin())) {
3006 // If the body ends with a ReturnStmt, the dtors will be added in
3007 // VisitReturnStmt.
3008 addAutomaticObjHandling(B: ScopePos, E: scopeBeginPos, S: C);
3009 }
3010
3011 CFGBlock *LastBlock = Block;
3012
3013 for (Stmt *S : llvm::reverse(C: C->body())) {
3014 // If we hit a segment of code just containing ';' (NullStmts), we can
3015 // get a null block back. In such cases, just use the LastBlock
3016 CFGBlock *newBlock = Visit(S, asc: AddStmtChoice::AlwaysAdd,
3017 ExternallyDestructed);
3018
3019 if (newBlock)
3020 LastBlock = newBlock;
3021
3022 if (badCFG)
3023 return nullptr;
3024
3025 ExternallyDestructed = false;
3026 }
3027
3028 return LastBlock;
3029}
3030
3031CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
3032 AddStmtChoice asc) {
3033 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(Val: C);
3034 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr);
3035
3036 // Create the confluence block that will "merge" the results of the ternary
3037 // expression.
3038 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
3039 appendStmt(B: ConfluenceBlock, S: C);
3040 if (badCFG)
3041 return nullptr;
3042
3043 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(alwaysAdd: true);
3044
3045 // Create a block for the LHS expression if there is an LHS expression. A
3046 // GCC extension allows LHS to be NULL, causing the condition to be the
3047 // value that is returned instead.
3048 // e.g: x ?: y is shorthand for: x ? x : y;
3049 Succ = ConfluenceBlock;
3050 Block = nullptr;
3051 CFGBlock *LHSBlock = nullptr;
3052 const Expr *trueExpr = C->getTrueExpr();
3053 if (trueExpr != opaqueValue) {
3054 LHSBlock = Visit(S: C->getTrueExpr(), asc: alwaysAdd);
3055 if (badCFG)
3056 return nullptr;
3057 Block = nullptr;
3058 }
3059 else
3060 LHSBlock = ConfluenceBlock;
3061
3062 // Create the block for the RHS expression.
3063 Succ = ConfluenceBlock;
3064 CFGBlock *RHSBlock = Visit(S: C->getFalseExpr(), asc: alwaysAdd);
3065 if (badCFG)
3066 return nullptr;
3067
3068 // If the condition is a logical '&&' or '||', build a more accurate CFG.
3069 if (BinaryOperator *Cond =
3070 dyn_cast<BinaryOperator>(Val: C->getCond()->IgnoreParens()))
3071 if (Cond->isLogicalOp())
3072 return VisitLogicalOperator(B: Cond, Term: C, TrueBlock: LHSBlock, FalseBlock: RHSBlock).first;
3073
3074 // Create the block that will contain the condition.
3075 Block = createBlock(add_successor: false);
3076
3077 // See if this is a known constant.
3078 const TryResult& KnownVal = tryEvaluateBool(S: C->getCond());
3079 addSuccessor(B: Block, S: LHSBlock, IsReachable: !KnownVal.isFalse());
3080 addSuccessor(B: Block, S: RHSBlock, IsReachable: !KnownVal.isTrue());
3081 Block->setTerminator(C);
3082 Expr *condExpr = C->getCond();
3083
3084 if (opaqueValue) {
3085 // Run the condition expression if it's not trivially expressed in
3086 // terms of the opaque value (or if there is no opaque value).
3087 if (condExpr != opaqueValue)
3088 addStmt(S: condExpr);
3089
3090 // Before that, run the common subexpression if there was one.
3091 // At least one of this or the above will be run.
3092 return addStmt(S: BCO->getCommon());
3093 }
3094
3095 return addStmt(S: condExpr);
3096}
3097
3098CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
3099 // Check if the Decl is for an __label__. If so, elide it from the
3100 // CFG entirely.
3101 if (isa<LabelDecl>(Val: *DS->decl_begin()))
3102 return Block;
3103
3104 // This case also handles static_asserts.
3105 if (DS->isSingleDecl())
3106 return VisitDeclSubExpr(DS);
3107
3108 CFGBlock *B = nullptr;
3109
3110 // Build an individual DeclStmt for each decl.
3111 for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(),
3112 E = DS->decl_rend();
3113 I != E; ++I) {
3114
3115 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
3116 // automatically freed with the CFG.
3117 DeclGroupRef DG(*I);
3118 Decl *D = *I;
3119 DeclStmt *DSNew = new (Context) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
3120 cfg->addSyntheticDeclStmt(Synthetic: DSNew, Source: DS);
3121
3122 // Append the fake DeclStmt to block.
3123 B = VisitDeclSubExpr(DS: DSNew);
3124 }
3125
3126 return B;
3127}
3128
3129/// VisitDeclSubExpr - Utility method to add block-level expressions for
3130/// DeclStmts and initializers in them.
3131CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
3132 assert(DS->isSingleDecl() && "Can handle single declarations only.");
3133
3134 if (const auto *TND = dyn_cast<TypedefNameDecl>(Val: DS->getSingleDecl())) {
3135 // If we encounter a VLA, process its size expressions.
3136 const Type *T = TND->getUnderlyingType().getTypePtr();
3137 if (!T->isVariablyModifiedType())
3138 return Block;
3139
3140 autoCreateBlock();
3141 appendStmt(B: Block, S: DS);
3142
3143 CFGBlock *LastBlock = Block;
3144 for (const VariableArrayType *VA = FindVA(t: T); VA != nullptr;
3145 VA = FindVA(t: VA->getElementType().getTypePtr())) {
3146 if (CFGBlock *NewBlock = addStmt(S: VA->getSizeExpr()))
3147 LastBlock = NewBlock;
3148 }
3149 return LastBlock;
3150 }
3151
3152 VarDecl *VD = dyn_cast<VarDecl>(Val: DS->getSingleDecl());
3153
3154 if (!VD) {
3155 // Of everything that can be declared in a DeclStmt, only VarDecls and the
3156 // exceptions above impact runtime semantics.
3157 return Block;
3158 }
3159
3160 bool HasTemporaries = false;
3161
3162 // Guard static initializers under a branch.
3163 CFGBlock *blockAfterStaticInit = nullptr;
3164
3165 if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) {
3166 // For static variables, we need to create a branch to track
3167 // whether or not they are initialized.
3168 if (Block) {
3169 Succ = Block;
3170 Block = nullptr;
3171 if (badCFG)
3172 return nullptr;
3173 }
3174 blockAfterStaticInit = Succ;
3175 }
3176
3177 // Destructors of temporaries in initialization expression should be called
3178 // after initialization finishes.
3179 Expr *Init = VD->getInit();
3180 if (Init) {
3181 HasTemporaries = isa<ExprWithCleanups>(Val: Init);
3182
3183 if (HasTemporaries &&
3184 (BuildOpts.AddTemporaryDtors || BuildOpts.AddLifetime)) {
3185 // Generate destructors for temporaries in initialization expression.
3186 TempDtorContext Context;
3187 auto *FullExprWithCleanups = cast<ExprWithCleanups>(Val: Init);
3188 VisitForTemporaries(E: FullExprWithCleanups->getSubExpr(),
3189 /*ExternallyDestructed=*/true, Context);
3190
3191 addFullExprCleanupMarker(Context, CleanupExpr: FullExprWithCleanups);
3192 }
3193 }
3194
3195 // If we bind to a tuple-like type, we iterate over the HoldingVars, and
3196 // create a DeclStmt for each of them.
3197 if (const auto *DD = dyn_cast<DecompositionDecl>(Val: VD)) {
3198 for (auto *BD : llvm::reverse(C: DD->bindings())) {
3199 if (auto *VD = BD->getHoldingVar()) {
3200 DeclGroupRef DG(VD);
3201 DeclStmt *DSNew =
3202 new (Context) DeclStmt(DG, VD->getLocation(), GetEndLoc(D: VD));
3203 cfg->addSyntheticDeclStmt(Synthetic: DSNew, Source: DS);
3204 Block = VisitDeclSubExpr(DS: DSNew);
3205 }
3206 }
3207 }
3208
3209 autoCreateBlock();
3210 appendStmt(B: Block, S: DS);
3211
3212 // If the initializer is an ArrayInitLoopExpr, we want to extract the
3213 // initializer, that's used for each element.
3214 const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Val: Init);
3215
3216 findConstructionContexts(
3217 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: DS),
3218 Child: AILE ? AILE->getSubExpr() : Init);
3219
3220 // Keep track of the last non-null block, as 'Block' can be nulled out
3221 // if the initializer expression is something like a 'while' in a
3222 // statement-expression.
3223 CFGBlock *LastBlock = Block;
3224
3225 if (Init) {
3226 if (HasTemporaries) {
3227 // For expression with temporaries go directly to subexpression to omit
3228 // generating destructors for the second time.
3229 ExprWithCleanups *EC = cast<ExprWithCleanups>(Val: Init);
3230 if (CFGBlock *newBlock = Visit(S: EC->getSubExpr()))
3231 LastBlock = newBlock;
3232 }
3233 else {
3234 if (CFGBlock *newBlock = Visit(S: Init))
3235 LastBlock = newBlock;
3236 }
3237 }
3238
3239 // If the type of VD is a VLA, then we must process its size expressions.
3240 // FIXME: This does not find the VLA if it is embedded in other types,
3241 // like here: `int (*p_vla)[x];`
3242 for (const VariableArrayType* VA = FindVA(t: VD->getType().getTypePtr());
3243 VA != nullptr; VA = FindVA(t: VA->getElementType().getTypePtr())) {
3244 if (CFGBlock *newBlock = addStmt(S: VA->getSizeExpr()))
3245 LastBlock = newBlock;
3246 }
3247
3248 maybeAddScopeBeginForVarDecl(B: Block, VD, S: DS);
3249
3250 // Remove variable from local scope.
3251 if (ScopePos && VD == *ScopePos)
3252 ++ScopePos;
3253
3254 CFGBlock *B = LastBlock;
3255 if (blockAfterStaticInit) {
3256 Succ = B;
3257 Block = createBlock(add_successor: false);
3258 Block->setTerminator(DS);
3259 addSuccessor(B: Block, S: blockAfterStaticInit);
3260 addSuccessor(B: Block, S: B);
3261 B = Block;
3262 }
3263
3264 return B;
3265}
3266
3267CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
3268 // We may see an if statement in the middle of a basic block, or it may be the
3269 // first statement we are processing. In either case, we create a new basic
3270 // block. First, we create the blocks for the then...else statements, and
3271 // then we create the block containing the if statement. If we were in the
3272 // middle of a block, we stop processing that block. That block is then the
3273 // implicit successor for the "then" and "else" clauses.
3274
3275 // Save local scope position because in case of condition variable ScopePos
3276 // won't be restored when traversing AST.
3277 SaveAndRestore save_scope_pos(ScopePos);
3278
3279 // Create local scope for C++17 if init-stmt if one exists.
3280 if (Stmt *Init = I->getInit())
3281 addLocalScopeForStmt(S: Init);
3282
3283 // Create local scope for possible condition variable.
3284 // Store scope position. Add implicit destructor.
3285 if (VarDecl *VD = I->getConditionVariable())
3286 addLocalScopeForVarDecl(VD);
3287
3288 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S: I);
3289
3290 // The block we were processing is now finished. Make it the successor
3291 // block.
3292 if (Block) {
3293 Succ = Block;
3294 if (badCFG)
3295 return nullptr;
3296 }
3297
3298 // Process the false branch.
3299 CFGBlock *ElseBlock = Succ;
3300
3301 if (Stmt *Else = I->getElse()) {
3302 SaveAndRestore sv(Succ);
3303
3304 // NULL out Block so that the recursive call to Visit will
3305 // create a new basic block.
3306 Block = nullptr;
3307
3308 // If branch is not a compound statement create implicit scope
3309 // and add destructors.
3310 if (!isa<CompoundStmt>(Val: Else))
3311 addLocalScopeAndDtors(S: Else);
3312
3313 ElseBlock = addStmt(S: Else);
3314
3315 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
3316 ElseBlock = sv.get();
3317 else if (Block) {
3318 if (badCFG)
3319 return nullptr;
3320 }
3321 }
3322
3323 // Process the true branch.
3324 CFGBlock *ThenBlock;
3325 {
3326 Stmt *Then = I->getThen();
3327 assert(Then);
3328 SaveAndRestore sv(Succ);
3329 Block = nullptr;
3330
3331 // If branch is not a compound statement create implicit scope
3332 // and add destructors.
3333 if (!isa<CompoundStmt>(Val: Then))
3334 addLocalScopeAndDtors(S: Then);
3335
3336 ThenBlock = addStmt(S: Then);
3337
3338 if (!ThenBlock) {
3339 // We can reach here if the "then" body has all NullStmts.
3340 // Create an empty block so we can distinguish between true and false
3341 // branches in path-sensitive analyses.
3342 ThenBlock = createBlock(add_successor: false);
3343 addSuccessor(B: ThenBlock, S: sv.get());
3344 } else if (Block) {
3345 if (badCFG)
3346 return nullptr;
3347 }
3348 }
3349
3350 // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by
3351 // having these handle the actual control-flow jump. Note that
3352 // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)"
3353 // we resort to the old control-flow behavior. This special handling
3354 // removes infeasible paths from the control-flow graph by having the
3355 // control-flow transfer of '&&' or '||' go directly into the then/else
3356 // blocks directly.
3357 BinaryOperator *Cond =
3358 (I->isConsteval() || I->getConditionVariable())
3359 ? nullptr
3360 : dyn_cast<BinaryOperator>(Val: I->getCond()->IgnoreParens());
3361 CFGBlock *LastBlock;
3362 if (Cond && Cond->isLogicalOp())
3363 LastBlock = VisitLogicalOperator(B: Cond, Term: I, TrueBlock: ThenBlock, FalseBlock: ElseBlock).first;
3364 else {
3365 // Now create a new block containing the if statement.
3366 Block = createBlock(add_successor: false);
3367
3368 // Set the terminator of the new block to the If statement.
3369 Block->setTerminator(I);
3370
3371 // See if this is a known constant.
3372 TryResult KnownVal;
3373 if (!I->isConsteval())
3374 KnownVal = tryEvaluateBool(S: I->getCond());
3375
3376 // Add the successors. If we know that specific branches are
3377 // unreachable, inform addSuccessor() of that knowledge.
3378 addSuccessor(B: Block, S: ThenBlock, /* IsReachable = */ !KnownVal.isFalse());
3379 addSuccessor(B: Block, S: ElseBlock, /* IsReachable = */ !KnownVal.isTrue());
3380
3381 if (I->isConsteval())
3382 return Block;
3383
3384 // Add the condition as the last statement in the new block. This may
3385 // create new blocks as the condition may contain control-flow. Any newly
3386 // created blocks will be pointed to be "Block".
3387 LastBlock = addStmt(S: I->getCond());
3388
3389 // If the IfStmt contains a condition variable, add it and its
3390 // initializer to the CFG.
3391 if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) {
3392 autoCreateBlock();
3393 LastBlock = addStmt(S: const_cast<DeclStmt *>(DS));
3394 }
3395 }
3396
3397 // Finally, if the IfStmt contains a C++17 init-stmt, add it to the CFG.
3398 if (Stmt *Init = I->getInit()) {
3399 autoCreateBlock();
3400 LastBlock = addStmt(S: Init);
3401 }
3402
3403 return LastBlock;
3404}
3405
3406CFGBlock *CFGBuilder::VisitReturnStmt(Stmt *S) {
3407 // If we were in the middle of a block we stop processing that block.
3408 //
3409 // NOTE: If a "return" or "co_return" appears in the middle of a block, this
3410 // means that the code afterwards is DEAD (unreachable). We still keep
3411 // a basic block for that code; a simple "mark-and-sweep" from the entry
3412 // block will be able to report such dead blocks.
3413 assert(isa<ReturnStmt>(S) || isa<CoreturnStmt>(S));
3414
3415 // Create the new block.
3416 Block = createBlock(add_successor: false);
3417
3418 addAutomaticObjHandling(B: ScopePos, E: LocalScope::const_iterator(), S);
3419
3420 if (auto *R = dyn_cast<ReturnStmt>(Val: S))
3421 findConstructionContexts(
3422 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: R),
3423 Child: R->getRetValue());
3424
3425 // If the one of the destructors does not return, we already have the Exit
3426 // block as a successor.
3427 if (!Block->hasNoReturnElement())
3428 addSuccessor(B: Block, S: &cfg->getExit());
3429
3430 // Add the return statement to the block.
3431 appendStmt(B: Block, S);
3432
3433 // Visit children
3434 if (ReturnStmt *RS = dyn_cast<ReturnStmt>(Val: S)) {
3435 if (Expr *O = RS->getRetValue())
3436 return Visit(S: O, asc: AddStmtChoice::AlwaysAdd, /*ExternallyDestructed=*/true);
3437 return Block;
3438 }
3439
3440 CoreturnStmt *CRS = cast<CoreturnStmt>(Val: S);
3441 auto *B = Block;
3442 if (Expr *PromiseCall = CRS->getPromiseCall())
3443 if (CFGBlock *R = Visit(S: PromiseCall))
3444 B = R;
3445
3446 if (Expr *RV = CRS->getOperand())
3447 if (RV->getType()->isVoidType() && !isa<InitListExpr>(Val: RV))
3448 // A non-initlist void expression.
3449 if (CFGBlock *R = Visit(S: RV))
3450 B = R;
3451
3452 return B;
3453}
3454
3455CFGBlock *CFGBuilder::VisitCoroutineSuspendExpr(CoroutineSuspendExpr *E,
3456 AddStmtChoice asc) {
3457 // We're modelling the pre-coro-xform CFG. Thus just evalate the various
3458 // active components of the co_await or co_yield. Note we do not model the
3459 // edge from the builtin_suspend to the exit node.
3460 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
3461 autoCreateBlock();
3462 appendStmt(B: Block, S: E);
3463 }
3464 CFGBlock *B = Block;
3465 if (auto *R = Visit(S: E->getResumeExpr()))
3466 B = R;
3467 if (auto *R = Visit(S: E->getSuspendExpr()))
3468 B = R;
3469 if (auto *R = Visit(S: E->getReadyExpr()))
3470 B = R;
3471 if (auto *R = Visit(S: E->getCommonExpr()))
3472 B = R;
3473 return B;
3474}
3475
3476CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) {
3477 // SEHExceptStmt are treated like labels, so they are the first statement in a
3478 // block.
3479
3480 // Save local scope position because in case of exception variable ScopePos
3481 // won't be restored when traversing AST.
3482 SaveAndRestore save_scope_pos(ScopePos);
3483
3484 addStmt(S: ES->getBlock());
3485 CFGBlock *SEHExceptBlock = Block;
3486 if (!SEHExceptBlock)
3487 SEHExceptBlock = createBlock();
3488
3489 appendStmt(B: SEHExceptBlock, S: ES);
3490
3491 // Also add the SEHExceptBlock as a label, like with regular labels.
3492 SEHExceptBlock->setLabel(ES);
3493
3494 // Bail out if the CFG is bad.
3495 if (badCFG)
3496 return nullptr;
3497
3498 // We set Block to NULL to allow lazy creation of a new block (if necessary).
3499 Block = nullptr;
3500
3501 return SEHExceptBlock;
3502}
3503
3504CFGBlock *CFGBuilder::VisitSEHFinallyStmt(SEHFinallyStmt *FS) {
3505 return VisitCompoundStmt(C: FS->getBlock(), /*ExternallyDestructed=*/false);
3506}
3507
3508CFGBlock *CFGBuilder::VisitSEHLeaveStmt(SEHLeaveStmt *LS) {
3509 // "__leave" is a control-flow statement. Thus we stop processing the current
3510 // block.
3511 if (badCFG)
3512 return nullptr;
3513
3514 // Now create a new block that ends with the __leave statement.
3515 Block = createBlock(add_successor: false);
3516 Block->setTerminator(LS);
3517
3518 // If there is no target for the __leave, then we are looking at an incomplete
3519 // AST. This means that the CFG cannot be constructed.
3520 if (SEHLeaveJumpTarget.block) {
3521 addAutomaticObjHandling(B: ScopePos, E: SEHLeaveJumpTarget.scopePosition, S: LS);
3522 addSuccessor(B: Block, S: SEHLeaveJumpTarget.block);
3523 } else
3524 badCFG = true;
3525
3526 return Block;
3527}
3528
3529CFGBlock *CFGBuilder::VisitSEHTryStmt(SEHTryStmt *Terminator) {
3530 // "__try"/"__except"/"__finally" is a control-flow statement. Thus we stop
3531 // processing the current block.
3532 CFGBlock *SEHTrySuccessor = nullptr;
3533
3534 if (Block) {
3535 if (badCFG)
3536 return nullptr;
3537 SEHTrySuccessor = Block;
3538 } else SEHTrySuccessor = Succ;
3539
3540 // FIXME: Implement __finally support.
3541 if (Terminator->getFinallyHandler())
3542 return NYS();
3543
3544 CFGBlock *PrevSEHTryTerminatedBlock = TryTerminatedBlock;
3545
3546 // Create a new block that will contain the __try statement.
3547 CFGBlock *NewTryTerminatedBlock = createBlock(add_successor: false);
3548
3549 // Add the terminator in the __try block.
3550 NewTryTerminatedBlock->setTerminator(Terminator);
3551
3552 if (SEHExceptStmt *Except = Terminator->getExceptHandler()) {
3553 // The code after the try is the implicit successor if there's an __except.
3554 Succ = SEHTrySuccessor;
3555 Block = nullptr;
3556 CFGBlock *ExceptBlock = VisitSEHExceptStmt(ES: Except);
3557 if (!ExceptBlock)
3558 return nullptr;
3559 // Add this block to the list of successors for the block with the try
3560 // statement.
3561 addSuccessor(B: NewTryTerminatedBlock, S: ExceptBlock);
3562 }
3563 if (PrevSEHTryTerminatedBlock)
3564 addSuccessor(B: NewTryTerminatedBlock, S: PrevSEHTryTerminatedBlock);
3565 else
3566 addSuccessor(B: NewTryTerminatedBlock, S: &cfg->getExit());
3567
3568 // The code after the try is the implicit successor.
3569 Succ = SEHTrySuccessor;
3570
3571 // Save the current "__try" context.
3572 SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);
3573 cfg->addTryDispatchBlock(block: TryTerminatedBlock);
3574
3575 // Save the current value for the __leave target.
3576 // All __leaves should go to the code following the __try
3577 // (FIXME: or if the __try has a __finally, to the __finally.)
3578 SaveAndRestore save_break(SEHLeaveJumpTarget);
3579 SEHLeaveJumpTarget = JumpTarget(SEHTrySuccessor, ScopePos);
3580
3581 assert(Terminator->getTryBlock() && "__try must contain a non-NULL body");
3582 Block = nullptr;
3583 return addStmt(S: Terminator->getTryBlock());
3584}
3585
3586CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
3587 // Get the block of the labeled statement. Add it to our map.
3588 addStmt(S: L->getSubStmt());
3589 CFGBlock *LabelBlock = Block;
3590
3591 if (!LabelBlock) // This can happen when the body is empty, i.e.
3592 LabelBlock = createBlock(); // scopes that only contains NullStmts.
3593
3594 assert(!LabelMap.contains(L->getDecl()) && "label already in map");
3595 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
3596
3597 // Labels partition blocks, so this is the end of the basic block we were
3598 // processing (L is the block's label). Because this is label (and we have
3599 // already processed the substatement) there is no extra control-flow to worry
3600 // about.
3601 LabelBlock->setLabel(L);
3602 if (badCFG)
3603 return nullptr;
3604
3605 // We set Block to NULL to allow lazy creation of a new block (if necessary).
3606 Block = nullptr;
3607
3608 // This block is now the implicit successor of other blocks.
3609 Succ = LabelBlock;
3610
3611 return LabelBlock;
3612}
3613
3614CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
3615 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3616 for (const BlockDecl::Capture &CI : E->getBlockDecl()->captures()) {
3617 if (Expr *CopyExpr = CI.getCopyExpr()) {
3618 CFGBlock *Tmp = Visit(S: CopyExpr);
3619 if (Tmp)
3620 LastBlock = Tmp;
3621 }
3622 }
3623 return LastBlock;
3624}
3625
3626CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
3627 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3628
3629 // Visit the capture initializers in reverse order so they appear in
3630 // left-to-right (natural) order in the CFG.
3631 unsigned Idx = E->capture_size();
3632 for (Expr *Init : reverse(C: E->capture_inits())) {
3633 --Idx;
3634 if (Init) {
3635 // If the initializer is an ArrayInitLoopExpr, we want to extract the
3636 // initializer, that's used for each element.
3637 auto *AILEInit = extractElementInitializerFromNestedAILE(
3638 AILE: dyn_cast<ArrayInitLoopExpr>(Val: Init));
3639
3640 findConstructionContexts(Layer: ConstructionContextLayer::create(
3641 C&: cfg->getBumpVectorContext(), Item: {E, Idx}),
3642 Child: AILEInit ? AILEInit : Init);
3643
3644 CFGBlock *Tmp = Visit(S: Init);
3645 if (Tmp)
3646 LastBlock = Tmp;
3647 }
3648 }
3649 return LastBlock;
3650}
3651
3652CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
3653 // Goto is a control-flow statement. Thus we stop processing the current
3654 // block and create a new one.
3655
3656 Block = createBlock(add_successor: false);
3657 Block->setTerminator(G);
3658
3659 // If we already know the mapping to the label block add the successor now.
3660 LabelMapTy::iterator I = LabelMap.find(Val: G->getLabel());
3661
3662 if (I == LabelMap.end())
3663 // We will need to backpatch this block later.
3664 BackpatchBlocks.push_back(x: JumpSource(Block, ScopePos));
3665 else {
3666 JumpTarget JT = I->second;
3667 addSuccessor(B: Block, S: JT.block);
3668 addScopeChangesHandling(SrcPos: ScopePos, DstPos: JT.scopePosition, S: G);
3669 }
3670
3671 return Block;
3672}
3673
3674CFGBlock *CFGBuilder::VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc) {
3675 // Goto is a control-flow statement. Thus we stop processing the current
3676 // block and create a new one.
3677
3678 if (!G->isAsmGoto())
3679 return VisitStmt(S: G, asc);
3680
3681 if (Block) {
3682 Succ = Block;
3683 if (badCFG)
3684 return nullptr;
3685 }
3686 Block = createBlock();
3687 Block->setTerminator(G);
3688 // We will backpatch this block later for all the labels.
3689 BackpatchBlocks.push_back(x: JumpSource(Block, ScopePos));
3690 // Save "Succ" in BackpatchBlocks. In the backpatch processing, "Succ" is
3691 // used to avoid adding "Succ" again.
3692 BackpatchBlocks.push_back(x: JumpSource(Succ, ScopePos));
3693 return VisitChildren(S: G);
3694}
3695
3696CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
3697 CFGBlock *LoopSuccessor = nullptr;
3698
3699 // Save local scope position because in case of condition variable ScopePos
3700 // won't be restored when traversing AST.
3701 SaveAndRestore save_scope_pos(ScopePos);
3702
3703 // Create local scope for init statement and possible condition variable.
3704 // Add destructor for init statement and condition variable.
3705 // Store scope position for continue statement.
3706 if (Stmt *Init = F->getInit())
3707 addLocalScopeForStmt(S: Init);
3708 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3709
3710 if (VarDecl *VD = F->getConditionVariable())
3711 addLocalScopeForVarDecl(VD);
3712 LocalScope::const_iterator ContinueScopePos = ScopePos;
3713
3714 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S: F);
3715
3716 addLoopExit(LoopStmt: F);
3717
3718 // "for" is a control-flow statement. Thus we stop processing the current
3719 // block.
3720 if (Block) {
3721 if (badCFG)
3722 return nullptr;
3723 LoopSuccessor = Block;
3724 } else
3725 LoopSuccessor = Succ;
3726
3727 // Save the current value for the break targets.
3728 // All breaks should go to the code following the loop.
3729 SaveAndRestore save_break(BreakJumpTarget);
3730 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3731
3732 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3733
3734 // Now create the loop body.
3735 {
3736 assert(F->getBody());
3737
3738 // Save the current values for Block, Succ, continue and break targets.
3739 SaveAndRestore save_Block(Block), save_Succ(Succ);
3740 SaveAndRestore save_continue(ContinueJumpTarget);
3741
3742 // Create an empty block to represent the transition block for looping back
3743 // to the head of the loop. If we have increment code, it will
3744 // go in this block as well.
3745 Block = Succ = TransitionBlock = createBlock(add_successor: false);
3746 TransitionBlock->setLoopTarget(F);
3747
3748
3749 // Loop iteration (after increment) should end with destructor of Condition
3750 // variable (if any).
3751 addAutomaticObjHandling(B: ScopePos, E: LoopBeginScopePos, S: F);
3752
3753 if (Stmt *I = F->getInc()) {
3754 // Generate increment code in its own basic block. This is the target of
3755 // continue statements.
3756 Succ = addStmt(S: I);
3757 }
3758
3759 // Finish up the increment (or empty) block if it hasn't been already.
3760 if (Block) {
3761 assert(Block == Succ);
3762 if (badCFG)
3763 return nullptr;
3764 Block = nullptr;
3765 }
3766
3767 // The starting block for the loop increment is the block that should
3768 // represent the 'loop target' for looping back to the start of the loop.
3769 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
3770 ContinueJumpTarget.block->setLoopTarget(F);
3771
3772
3773 // If body is not a compound statement create implicit scope
3774 // and add destructors.
3775 if (!isa<CompoundStmt>(Val: F->getBody()))
3776 addLocalScopeAndDtors(S: F->getBody());
3777
3778 // Now populate the body block, and in the process create new blocks as we
3779 // walk the body of the loop.
3780 BodyBlock = addStmt(S: F->getBody());
3781
3782 if (!BodyBlock) {
3783 // In the case of "for (...;...;...);" we can have a null BodyBlock.
3784 // Use the continue jump target as the proxy for the body.
3785 BodyBlock = ContinueJumpTarget.block;
3786 }
3787 else if (badCFG)
3788 return nullptr;
3789 }
3790
3791 // Because of short-circuit evaluation, the condition of the loop can span
3792 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3793 // evaluate the condition.
3794 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3795
3796 do {
3797 Expr *C = F->getCond();
3798 SaveAndRestore save_scope_pos(ScopePos);
3799
3800 // Specially handle logical operators, which have a slightly
3801 // more optimal CFG representation.
3802 if (BinaryOperator *Cond =
3803 dyn_cast_or_null<BinaryOperator>(Val: C ? C->IgnoreParens() : nullptr))
3804 if (Cond->isLogicalOp()) {
3805 std::tie(args&: EntryConditionBlock, args&: ExitConditionBlock) =
3806 VisitLogicalOperator(B: Cond, Term: F, TrueBlock: BodyBlock, FalseBlock: LoopSuccessor);
3807 break;
3808 }
3809
3810 // The default case when not handling logical operators.
3811 EntryConditionBlock = ExitConditionBlock = createBlock(add_successor: false);
3812 ExitConditionBlock->setTerminator(F);
3813
3814 // See if this is a known constant.
3815 TryResult KnownVal(true);
3816
3817 if (C) {
3818 // Now add the actual condition to the condition block.
3819 // Because the condition itself may contain control-flow, new blocks may
3820 // be created. Thus we update "Succ" after adding the condition.
3821 Block = ExitConditionBlock;
3822 EntryConditionBlock = addStmt(S: C);
3823
3824 // If this block contains a condition variable, add both the condition
3825 // variable and initializer to the CFG.
3826 if (VarDecl *VD = F->getConditionVariable()) {
3827 if (Expr *Init = VD->getInit()) {
3828 autoCreateBlock();
3829 const DeclStmt *DS = F->getConditionVariableDeclStmt();
3830 assert(DS->isSingleDecl());
3831 findConstructionContexts(
3832 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: DS),
3833 Child: Init);
3834 appendStmt(B: Block, S: DS);
3835 EntryConditionBlock = addStmt(S: Init);
3836 assert(Block == EntryConditionBlock);
3837 maybeAddScopeBeginForVarDecl(B: EntryConditionBlock, VD, S: C);
3838 }
3839 }
3840
3841 if (Block && badCFG)
3842 return nullptr;
3843
3844 KnownVal = tryEvaluateBool(S: C);
3845 }
3846
3847 // Add the loop body entry as a successor to the condition.
3848 addSuccessor(B: ExitConditionBlock, S: KnownVal.isFalse() ? nullptr : BodyBlock);
3849 // Link up the condition block with the code that follows the loop. (the
3850 // false branch).
3851 addSuccessor(B: ExitConditionBlock,
3852 S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
3853 } while (false);
3854
3855 // Link up the loop-back block to the entry condition block.
3856 addSuccessor(B: TransitionBlock, S: EntryConditionBlock);
3857
3858 // The condition block is the implicit successor for any code above the loop.
3859 Succ = EntryConditionBlock;
3860
3861 // If the loop contains initialization, create a new block for those
3862 // statements. This block can also contain statements that precede the loop.
3863 if (Stmt *I = F->getInit()) {
3864 SaveAndRestore save_scope_pos(ScopePos);
3865 ScopePos = LoopBeginScopePos;
3866 Block = createBlock();
3867 return addStmt(S: I);
3868 }
3869
3870 // There is no loop initialization. We are thus basically a while loop.
3871 // NULL out Block to force lazy block construction.
3872 Block = nullptr;
3873 Succ = EntryConditionBlock;
3874 return EntryConditionBlock;
3875}
3876
3877CFGBlock *
3878CFGBuilder::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
3879 AddStmtChoice asc) {
3880 findConstructionContexts(
3881 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: MTE),
3882 Child: MTE->getSubExpr());
3883
3884 return VisitStmt(S: MTE, asc);
3885}
3886
3887CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
3888 if (asc.alwaysAdd(builder&: *this, stmt: M)) {
3889 autoCreateBlock();
3890 appendStmt(B: Block, S: M);
3891 }
3892 return Visit(S: M->getBase());
3893}
3894
3895CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
3896 // Objective-C fast enumeration 'for' statements:
3897 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
3898 //
3899 // for ( Type newVariable in collection_expression ) { statements }
3900 //
3901 // becomes:
3902 //
3903 // prologue:
3904 // 1. collection_expression
3905 // T. jump to loop_entry
3906 // loop_entry:
3907 // 1. side-effects of element expression
3908 // 1. ObjCForCollectionStmt [performs binding to newVariable]
3909 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
3910 // TB:
3911 // statements
3912 // T. jump to loop_entry
3913 // FB:
3914 // what comes after
3915 //
3916 // and
3917 //
3918 // Type existingItem;
3919 // for ( existingItem in expression ) { statements }
3920 //
3921 // becomes:
3922 //
3923 // the same with newVariable replaced with existingItem; the binding works
3924 // the same except that for one ObjCForCollectionStmt::getElement() returns
3925 // a DeclStmt and the other returns a DeclRefExpr.
3926
3927 CFGBlock *LoopSuccessor = nullptr;
3928
3929 if (Block) {
3930 if (badCFG)
3931 return nullptr;
3932 LoopSuccessor = Block;
3933 Block = nullptr;
3934 } else
3935 LoopSuccessor = Succ;
3936
3937 // Build the condition blocks.
3938 CFGBlock *ExitConditionBlock = createBlock(add_successor: false);
3939
3940 // Set the terminator for the "exit" condition block.
3941 ExitConditionBlock->setTerminator(S);
3942
3943 // The last statement in the block should be the ObjCForCollectionStmt, which
3944 // performs the actual binding to 'element' and determines if there are any
3945 // more items in the collection.
3946 appendStmt(B: ExitConditionBlock, S);
3947 Block = ExitConditionBlock;
3948
3949 // Walk the 'element' expression to see if there are any side-effects. We
3950 // generate new blocks as necessary. We DON'T add the statement by default to
3951 // the CFG unless it contains control-flow.
3952 CFGBlock *EntryConditionBlock = Visit(S: S->getElement(),
3953 asc: AddStmtChoice::NotAlwaysAdd);
3954 if (Block) {
3955 if (badCFG)
3956 return nullptr;
3957 Block = nullptr;
3958 }
3959
3960 // The condition block is the implicit successor for the loop body as well as
3961 // any code above the loop.
3962 Succ = EntryConditionBlock;
3963
3964 // Now create the true branch.
3965 {
3966 // Save the current values for Succ, continue and break targets.
3967 SaveAndRestore save_Block(Block), save_Succ(Succ);
3968 SaveAndRestore save_continue(ContinueJumpTarget),
3969 save_break(BreakJumpTarget);
3970
3971 // Add an intermediate block between the BodyBlock and the
3972 // EntryConditionBlock to represent the "loop back" transition, for looping
3973 // back to the head of the loop.
3974 CFGBlock *LoopBackBlock = nullptr;
3975 Succ = LoopBackBlock = createBlock();
3976 LoopBackBlock->setLoopTarget(S);
3977
3978 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3979 ContinueJumpTarget = JumpTarget(Succ, ScopePos);
3980
3981 CFGBlock *BodyBlock = addStmt(S: S->getBody());
3982
3983 if (!BodyBlock)
3984 BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;"
3985 else if (Block) {
3986 if (badCFG)
3987 return nullptr;
3988 }
3989
3990 // This new body block is a successor to our "exit" condition block.
3991 addSuccessor(B: ExitConditionBlock, S: BodyBlock);
3992 }
3993
3994 // Link up the condition block with the code that follows the loop.
3995 // (the false branch).
3996 addSuccessor(B: ExitConditionBlock, S: LoopSuccessor);
3997
3998 // Now create a prologue block to contain the collection expression.
3999 Block = createBlock();
4000 return addStmt(S: S->getCollection());
4001}
4002
4003CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) {
4004 // Inline the body.
4005 return addStmt(S: S->getSubStmt());
4006 // TODO: consider adding cleanups for the end of @autoreleasepool scope.
4007}
4008
4009CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
4010 // FIXME: Add locking 'primitives' to CFG for @synchronized.
4011
4012 // Inline the body.
4013 CFGBlock *SyncBlock = addStmt(S: S->getSynchBody());
4014
4015 // The sync body starts its own basic block. This makes it a little easier
4016 // for diagnostic clients.
4017 if (SyncBlock) {
4018 if (badCFG)
4019 return nullptr;
4020
4021 Block = nullptr;
4022 Succ = SyncBlock;
4023 }
4024
4025 // Add the @synchronized to the CFG.
4026 autoCreateBlock();
4027 appendStmt(B: Block, S);
4028
4029 // Inline the sync expression.
4030 return addStmt(S: S->getSynchExpr());
4031}
4032
4033CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {
4034 autoCreateBlock();
4035
4036 // Add the PseudoObject as the last thing.
4037 appendStmt(B: Block, S: E);
4038
4039 CFGBlock *lastBlock = Block;
4040
4041 // Before that, evaluate all of the semantics in order. In
4042 // CFG-land, that means appending them in reverse order.
4043 for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {
4044 Expr *Semantic = E->getSemanticExpr(index: --i);
4045
4046 // If the semantic is an opaque value, we're being asked to bind
4047 // it to its source expression.
4048 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Val: Semantic))
4049 Semantic = OVE->getSourceExpr();
4050
4051 if (CFGBlock *B = Visit(S: Semantic))
4052 lastBlock = B;
4053 }
4054
4055 return lastBlock;
4056}
4057
4058CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
4059 CFGBlock *LoopSuccessor = nullptr;
4060
4061 // Save local scope position because in case of condition variable ScopePos
4062 // won't be restored when traversing AST.
4063 SaveAndRestore save_scope_pos(ScopePos);
4064
4065 // Create local scope for possible condition variable.
4066 // Store scope position for continue statement.
4067 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
4068 if (VarDecl *VD = W->getConditionVariable()) {
4069 addLocalScopeForVarDecl(VD);
4070 addAutomaticObjHandling(B: ScopePos, E: LoopBeginScopePos, S: W);
4071 }
4072 addLoopExit(LoopStmt: W);
4073
4074 // "while" is a control-flow statement. Thus we stop processing the current
4075 // block.
4076 if (Block) {
4077 if (badCFG)
4078 return nullptr;
4079 LoopSuccessor = Block;
4080 Block = nullptr;
4081 } else {
4082 LoopSuccessor = Succ;
4083 }
4084
4085 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
4086
4087 // Process the loop body.
4088 {
4089 assert(W->getBody());
4090
4091 // Save the current values for Block, Succ, continue and break targets.
4092 SaveAndRestore save_Block(Block), save_Succ(Succ);
4093 SaveAndRestore save_continue(ContinueJumpTarget),
4094 save_break(BreakJumpTarget);
4095
4096 // Create an empty block to represent the transition block for looping back
4097 // to the head of the loop.
4098 Succ = TransitionBlock = createBlock(add_successor: false);
4099 TransitionBlock->setLoopTarget(W);
4100 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
4101
4102 // All breaks should go to the code following the loop.
4103 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4104
4105 // Loop body should end with destructor of Condition variable (if any).
4106 addAutomaticObjHandling(B: ScopePos, E: LoopBeginScopePos, S: W);
4107
4108 // If body is not a compound statement create implicit scope
4109 // and add destructors.
4110 if (!isa<CompoundStmt>(Val: W->getBody()))
4111 addLocalScopeAndDtors(S: W->getBody());
4112
4113 // Create the body. The returned block is the entry to the loop body.
4114 BodyBlock = addStmt(S: W->getBody());
4115
4116 if (!BodyBlock)
4117 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
4118 else if (Block && badCFG)
4119 return nullptr;
4120 }
4121
4122 // Because of short-circuit evaluation, the condition of the loop can span
4123 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
4124 // evaluate the condition.
4125 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
4126
4127 do {
4128 Expr *C = W->getCond();
4129
4130 // Specially handle logical operators, which have a slightly
4131 // more optimal CFG representation.
4132 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(Val: C->IgnoreParens()))
4133 if (Cond->isLogicalOp()) {
4134 std::tie(args&: EntryConditionBlock, args&: ExitConditionBlock) =
4135 VisitLogicalOperator(B: Cond, Term: W, TrueBlock: BodyBlock, FalseBlock: LoopSuccessor);
4136 break;
4137 }
4138
4139 // The default case when not handling logical operators.
4140 ExitConditionBlock = createBlock(add_successor: false);
4141 ExitConditionBlock->setTerminator(W);
4142
4143 // Now add the actual condition to the condition block.
4144 // Because the condition itself may contain control-flow, new blocks may
4145 // be created. Thus we update "Succ" after adding the condition.
4146 Block = ExitConditionBlock;
4147 Block = EntryConditionBlock = addStmt(S: C);
4148
4149 // If this block contains a condition variable, add both the condition
4150 // variable and initializer to the CFG.
4151 if (VarDecl *VD = W->getConditionVariable()) {
4152 if (Expr *Init = VD->getInit()) {
4153 autoCreateBlock();
4154 const DeclStmt *DS = W->getConditionVariableDeclStmt();
4155 assert(DS->isSingleDecl());
4156 findConstructionContexts(
4157 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(),
4158 Item: const_cast<DeclStmt *>(DS)),
4159 Child: Init);
4160 appendStmt(B: Block, S: DS);
4161 EntryConditionBlock = addStmt(S: Init);
4162 assert(Block == EntryConditionBlock);
4163 maybeAddScopeBeginForVarDecl(B: EntryConditionBlock, VD, S: C);
4164 }
4165 }
4166
4167 if (Block && badCFG)
4168 return nullptr;
4169
4170 // See if this is a known constant.
4171 const TryResult& KnownVal = tryEvaluateBool(S: C);
4172
4173 // Add the loop body entry as a successor to the condition.
4174 addSuccessor(B: ExitConditionBlock, S: KnownVal.isFalse() ? nullptr : BodyBlock);
4175 // Link up the condition block with the code that follows the loop. (the
4176 // false branch).
4177 addSuccessor(B: ExitConditionBlock,
4178 S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
4179 } while(false);
4180
4181 // Link up the loop-back block to the entry condition block.
4182 addSuccessor(B: TransitionBlock, S: EntryConditionBlock);
4183
4184 // There can be no more statements in the condition block since we loop back
4185 // to this block. NULL out Block to force lazy creation of another block.
4186 Block = nullptr;
4187
4188 // Return the condition block, which is the dominating block for the loop.
4189 Succ = EntryConditionBlock;
4190 return EntryConditionBlock;
4191}
4192
4193CFGBlock *CFGBuilder::VisitArrayInitLoopExpr(ArrayInitLoopExpr *A,
4194 AddStmtChoice asc) {
4195 if (asc.alwaysAdd(builder&: *this, stmt: A)) {
4196 autoCreateBlock();
4197 appendStmt(B: Block, S: A);
4198 }
4199
4200 CFGBlock *B = Block;
4201
4202 if (CFGBlock *R = Visit(S: A->getSubExpr()))
4203 B = R;
4204
4205 OpaqueValueExpr *OVE = A->getCommonExpr();
4206 if (CFGBlock *R = Visit(S: OVE->getSourceExpr()))
4207 B = R;
4208
4209 return B;
4210}
4211
4212CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *CS) {
4213 // ObjCAtCatchStmt are treated like labels, so they are the first statement
4214 // in a block.
4215
4216 // Save local scope position because in case of exception variable ScopePos
4217 // won't be restored when traversing AST.
4218 SaveAndRestore save_scope_pos(ScopePos);
4219
4220 if (CS->getCatchBody())
4221 addStmt(S: CS->getCatchBody());
4222
4223 CFGBlock *CatchBlock = Block;
4224 if (!CatchBlock)
4225 CatchBlock = createBlock();
4226
4227 appendStmt(B: CatchBlock, S: CS);
4228
4229 // Also add the ObjCAtCatchStmt as a label, like with regular labels.
4230 CatchBlock->setLabel(CS);
4231
4232 // Bail out if the CFG is bad.
4233 if (badCFG)
4234 return nullptr;
4235
4236 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4237 Block = nullptr;
4238
4239 return CatchBlock;
4240}
4241
4242CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
4243 // If we were in the middle of a block we stop processing that block.
4244 if (badCFG)
4245 return nullptr;
4246
4247 // Create the new block.
4248 Block = createBlock(add_successor: false);
4249
4250 if (TryTerminatedBlock)
4251 // The current try statement is the only successor.
4252 addSuccessor(B: Block, S: TryTerminatedBlock);
4253 else
4254 // otherwise the Exit block is the only successor.
4255 addSuccessor(B: Block, S: &cfg->getExit());
4256
4257 // Add the statement to the block. This may create new blocks if S contains
4258 // control-flow (short-circuit operations).
4259 return VisitStmt(S, asc: AddStmtChoice::AlwaysAdd);
4260}
4261
4262CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *Terminator) {
4263 // "@try"/"@catch" is a control-flow statement. Thus we stop processing the
4264 // current block.
4265 CFGBlock *TrySuccessor = nullptr;
4266
4267 if (Block) {
4268 if (badCFG)
4269 return nullptr;
4270 TrySuccessor = Block;
4271 } else
4272 TrySuccessor = Succ;
4273
4274 // FIXME: Implement @finally support.
4275 if (Terminator->getFinallyStmt())
4276 return NYS();
4277
4278 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
4279
4280 // Create a new block that will contain the try statement.
4281 CFGBlock *NewTryTerminatedBlock = createBlock(add_successor: false);
4282 // Add the terminator in the try block.
4283 NewTryTerminatedBlock->setTerminator(Terminator);
4284
4285 bool HasCatchAll = false;
4286 for (ObjCAtCatchStmt *CS : Terminator->catch_stmts()) {
4287 // The code after the try is the implicit successor.
4288 Succ = TrySuccessor;
4289 if (CS->hasEllipsis()) {
4290 HasCatchAll = true;
4291 }
4292 Block = nullptr;
4293 CFGBlock *CatchBlock = VisitObjCAtCatchStmt(CS);
4294 if (!CatchBlock)
4295 return nullptr;
4296 // Add this block to the list of successors for the block with the try
4297 // statement.
4298 addSuccessor(B: NewTryTerminatedBlock, S: CatchBlock);
4299 }
4300
4301 // FIXME: This needs updating when @finally support is added.
4302 if (!HasCatchAll) {
4303 if (PrevTryTerminatedBlock)
4304 addSuccessor(B: NewTryTerminatedBlock, S: PrevTryTerminatedBlock);
4305 else
4306 addSuccessor(B: NewTryTerminatedBlock, S: &cfg->getExit());
4307 }
4308
4309 // The code after the try is the implicit successor.
4310 Succ = TrySuccessor;
4311
4312 // Save the current "try" context.
4313 SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);
4314 cfg->addTryDispatchBlock(block: TryTerminatedBlock);
4315
4316 assert(Terminator->getTryBody() && "try must contain a non-NULL body");
4317 Block = nullptr;
4318 return addStmt(S: Terminator->getTryBody());
4319}
4320
4321CFGBlock *CFGBuilder::VisitObjCMessageExpr(ObjCMessageExpr *ME,
4322 AddStmtChoice asc) {
4323 findConstructionContextsForArguments(E: ME);
4324
4325 autoCreateBlock();
4326 appendObjCMessage(B: Block, ME);
4327
4328 return VisitChildren(S: ME);
4329}
4330
4331CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
4332 // If we were in the middle of a block we stop processing that block.
4333 if (badCFG)
4334 return nullptr;
4335
4336 // Create the new block.
4337 Block = createBlock(add_successor: false);
4338
4339 if (TryTerminatedBlock)
4340 // The current try statement is the only successor.
4341 addSuccessor(B: Block, S: TryTerminatedBlock);
4342 else
4343 // otherwise the Exit block is the only successor.
4344 addSuccessor(B: Block, S: &cfg->getExit());
4345
4346 // Add the statement to the block. This may create new blocks if S contains
4347 // control-flow (short-circuit operations).
4348 return VisitStmt(S: T, asc: AddStmtChoice::AlwaysAdd);
4349}
4350
4351CFGBlock *CFGBuilder::VisitCXXTypeidExpr(CXXTypeidExpr *S, AddStmtChoice asc) {
4352 if (asc.alwaysAdd(builder&: *this, stmt: S)) {
4353 autoCreateBlock();
4354 appendStmt(B: Block, S);
4355 }
4356
4357 // C++ [expr.typeid]p3:
4358 // When typeid is applied to an expression other than an glvalue of a
4359 // polymorphic class type [...] [the] expression is an unevaluated
4360 // operand. [...]
4361 // We add only potentially evaluated statements to the block to avoid
4362 // CFG generation for unevaluated operands.
4363 if (!S->isTypeDependent() && S->isPotentiallyEvaluated())
4364 return VisitChildren(S);
4365
4366 // Return block without CFG for unevaluated operands.
4367 return Block;
4368}
4369
4370CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
4371 CFGBlock *LoopSuccessor = nullptr;
4372
4373 addLoopExit(LoopStmt: D);
4374
4375 // "do...while" is a control-flow statement. Thus we stop processing the
4376 // current block.
4377 if (Block) {
4378 if (badCFG)
4379 return nullptr;
4380 LoopSuccessor = Block;
4381 } else
4382 LoopSuccessor = Succ;
4383
4384 // Because of short-circuit evaluation, the condition of the loop can span
4385 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
4386 // evaluate the condition.
4387 CFGBlock *ExitConditionBlock = createBlock(add_successor: false);
4388 CFGBlock *EntryConditionBlock = ExitConditionBlock;
4389
4390 // Set the terminator for the "exit" condition block.
4391 ExitConditionBlock->setTerminator(D);
4392
4393 // Now add the actual condition to the condition block. Because the condition
4394 // itself may contain control-flow, new blocks may be created.
4395 if (Stmt *C = D->getCond()) {
4396 Block = ExitConditionBlock;
4397 EntryConditionBlock = addStmt(S: C);
4398 if (Block) {
4399 if (badCFG)
4400 return nullptr;
4401 }
4402 }
4403
4404 // The condition block is the implicit successor for the loop body.
4405 Succ = EntryConditionBlock;
4406
4407 // See if this is a known constant.
4408 const TryResult &KnownVal = tryEvaluateBool(S: D->getCond());
4409
4410 // Process the loop body.
4411 CFGBlock *BodyBlock = nullptr;
4412 {
4413 assert(D->getBody());
4414
4415 // Save the current values for Block, Succ, and continue and break targets
4416 SaveAndRestore save_Block(Block), save_Succ(Succ);
4417 SaveAndRestore save_continue(ContinueJumpTarget),
4418 save_break(BreakJumpTarget);
4419
4420 // All continues within this loop should go to the condition block
4421 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
4422
4423 // All breaks should go to the code following the loop.
4424 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4425
4426 // NULL out Block to force lazy instantiation of blocks for the body.
4427 Block = nullptr;
4428
4429 // If body is not a compound statement create implicit scope
4430 // and add destructors.
4431 if (!isa<CompoundStmt>(Val: D->getBody()))
4432 addLocalScopeAndDtors(S: D->getBody());
4433
4434 // Create the body. The returned block is the entry to the loop body.
4435 BodyBlock = addStmt(S: D->getBody());
4436
4437 if (!BodyBlock)
4438 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
4439 else if (Block) {
4440 if (badCFG)
4441 return nullptr;
4442 }
4443
4444 // Add an intermediate block between the BodyBlock and the
4445 // ExitConditionBlock to represent the "loop back" transition. Create an
4446 // empty block to represent the transition block for looping back to the
4447 // head of the loop.
4448 // FIXME: Can we do this more efficiently without adding another block?
4449 Block = nullptr;
4450 Succ = BodyBlock;
4451 CFGBlock *LoopBackBlock = createBlock();
4452 LoopBackBlock->setLoopTarget(D);
4453
4454 if (!KnownVal.isFalse())
4455 // Add the loop body entry as a successor to the condition.
4456 addSuccessor(B: ExitConditionBlock, S: LoopBackBlock);
4457 else
4458 addSuccessor(B: ExitConditionBlock, S: nullptr);
4459 }
4460
4461 // Link up the condition block with the code that follows the loop.
4462 // (the false branch).
4463 addSuccessor(B: ExitConditionBlock, S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
4464
4465 // There can be no more statements in the body block(s) since we loop back to
4466 // the body. NULL out Block to force lazy creation of another block.
4467 Block = nullptr;
4468
4469 // Return the loop body, which is the dominating block for the loop.
4470 Succ = BodyBlock;
4471 return BodyBlock;
4472}
4473
4474CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
4475 // "continue" is a control-flow statement. Thus we stop processing the
4476 // current block.
4477 if (badCFG)
4478 return nullptr;
4479
4480 // Now create a new block that ends with the continue statement.
4481 Block = createBlock(add_successor: false);
4482 Block->setTerminator(C);
4483
4484 // If there is no target for the continue, then we are looking at an
4485 // incomplete AST. This means the CFG cannot be constructed.
4486 if (ContinueJumpTarget.block) {
4487 addAutomaticObjHandling(B: ScopePos, E: ContinueJumpTarget.scopePosition, S: C);
4488 addSuccessor(B: Block, S: ContinueJumpTarget.block);
4489 } else
4490 badCFG = true;
4491
4492 return Block;
4493}
4494
4495CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
4496 AddStmtChoice asc) {
4497 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
4498 autoCreateBlock();
4499 appendStmt(B: Block, S: E);
4500 }
4501
4502 // VLA types have expressions that must be evaluated.
4503 // Evaluation is done only for `sizeof`.
4504
4505 if (E->getKind() != UETT_SizeOf)
4506 return Block;
4507
4508 CFGBlock *lastBlock = Block;
4509
4510 if (E->isArgumentType()) {
4511 for (const VariableArrayType *VA =FindVA(t: E->getArgumentType().getTypePtr());
4512 VA != nullptr; VA = FindVA(t: VA->getElementType().getTypePtr()))
4513 lastBlock = addStmt(S: VA->getSizeExpr());
4514 }
4515 return lastBlock;
4516}
4517
4518/// VisitStmtExpr - Utility method to handle (nested) statement
4519/// expressions (a GCC extension).
4520CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
4521 if (asc.alwaysAdd(builder&: *this, stmt: SE)) {
4522 autoCreateBlock();
4523 appendStmt(B: Block, S: SE);
4524 }
4525 return VisitCompoundStmt(C: SE->getSubStmt(), /*ExternallyDestructed=*/true);
4526}
4527
4528CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
4529 // "switch" is a control-flow statement. Thus we stop processing the current
4530 // block.
4531 CFGBlock *SwitchSuccessor = nullptr;
4532
4533 // Save local scope position because in case of condition variable ScopePos
4534 // won't be restored when traversing AST.
4535 SaveAndRestore save_scope_pos(ScopePos);
4536
4537 // Create local scope for C++17 switch init-stmt if one exists.
4538 if (Stmt *Init = Terminator->getInit())
4539 addLocalScopeForStmt(S: Init);
4540
4541 // Create local scope for possible condition variable.
4542 // Store scope position. Add implicit destructor.
4543 if (VarDecl *VD = Terminator->getConditionVariable())
4544 addLocalScopeForVarDecl(VD);
4545
4546 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S: Terminator);
4547
4548 if (Block) {
4549 if (badCFG)
4550 return nullptr;
4551 SwitchSuccessor = Block;
4552 } else SwitchSuccessor = Succ;
4553
4554 // Save the current "switch" context.
4555 SaveAndRestore save_switch(SwitchTerminatedBlock),
4556 save_default(DefaultCaseBlock);
4557 SaveAndRestore save_break(BreakJumpTarget);
4558
4559 // Set the "default" case to be the block after the switch statement. If the
4560 // switch statement contains a "default:", this value will be overwritten with
4561 // the block for that code.
4562 DefaultCaseBlock = SwitchSuccessor;
4563
4564 // Create a new block that will contain the switch statement.
4565 SwitchTerminatedBlock = createBlock(add_successor: false);
4566
4567 // Now process the switch body. The code after the switch is the implicit
4568 // successor.
4569 Succ = SwitchSuccessor;
4570 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
4571
4572 // When visiting the body, the case statements should automatically get linked
4573 // up to the switch. We also don't keep a pointer to the body, since all
4574 // control-flow from the switch goes to case/default statements.
4575 assert(Terminator->getBody() && "switch must contain a non-NULL body");
4576 Block = nullptr;
4577
4578 // For pruning unreachable case statements, save the current state
4579 // for tracking the condition value.
4580 SaveAndRestore save_switchExclusivelyCovered(switchExclusivelyCovered, false);
4581
4582 // Determine if the switch condition can be explicitly evaluated.
4583 assert(Terminator->getCond() && "switch condition must be non-NULL");
4584 Expr::EvalResult result;
4585 bool b = tryEvaluate(S: Terminator->getCond(), outResult&: result);
4586 SaveAndRestore save_switchCond(switchCond, b ? &result : nullptr);
4587
4588 // If body is not a compound statement create implicit scope
4589 // and add destructors.
4590 if (!isa<CompoundStmt>(Val: Terminator->getBody()))
4591 addLocalScopeAndDtors(S: Terminator->getBody());
4592
4593 addStmt(S: Terminator->getBody());
4594 if (Block) {
4595 if (badCFG)
4596 return nullptr;
4597 }
4598
4599 // If we have no "default:" case, the default transition is to the code
4600 // following the switch body. Moreover, take into account if all the
4601 // cases of a switch are covered (e.g., switching on an enum value).
4602 //
4603 // Note: We add a successor to a switch that is considered covered yet has no
4604 // case statements if the enumeration has no enumerators.
4605 // We also consider this successor reachable if
4606 // BuildOpts.SwitchReqDefaultCoveredEnum is true.
4607 bool SwitchAlwaysHasSuccessor = false;
4608 SwitchAlwaysHasSuccessor |= switchExclusivelyCovered;
4609 SwitchAlwaysHasSuccessor |=
4610 !BuildOpts.AssumeReachableDefaultInSwitchStatements &&
4611 Terminator->isAllEnumCasesCovered() && Terminator->getSwitchCaseList();
4612 addSuccessor(B: SwitchTerminatedBlock, S: DefaultCaseBlock,
4613 IsReachable: !SwitchAlwaysHasSuccessor);
4614
4615 // Add the terminator and condition in the switch block.
4616 SwitchTerminatedBlock->setTerminator(Terminator);
4617 Block = SwitchTerminatedBlock;
4618 CFGBlock *LastBlock = addStmt(S: Terminator->getCond());
4619
4620 // If the SwitchStmt contains a condition variable, add both the
4621 // SwitchStmt and the condition variable initialization to the CFG.
4622 if (VarDecl *VD = Terminator->getConditionVariable()) {
4623 if (Expr *Init = VD->getInit()) {
4624 autoCreateBlock();
4625 appendStmt(B: Block, S: Terminator->getConditionVariableDeclStmt());
4626 LastBlock = addStmt(S: Init);
4627 maybeAddScopeBeginForVarDecl(B: LastBlock, VD, S: Init);
4628 }
4629 }
4630
4631 // Finally, if the SwitchStmt contains a C++17 init-stmt, add it to the CFG.
4632 if (Stmt *Init = Terminator->getInit()) {
4633 autoCreateBlock();
4634 LastBlock = addStmt(S: Init);
4635 }
4636
4637 return LastBlock;
4638}
4639
4640static bool shouldAddCase(bool &switchExclusivelyCovered,
4641 const Expr::EvalResult *switchCond,
4642 const CaseStmt *CS,
4643 ASTContext &Ctx) {
4644 if (!switchCond)
4645 return true;
4646
4647 bool addCase = false;
4648
4649 if (!switchExclusivelyCovered) {
4650 if (switchCond->Val.isInt()) {
4651 // Evaluate the LHS of the case value.
4652 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
4653 const llvm::APSInt &condInt = switchCond->Val.getInt();
4654
4655 if (condInt == lhsInt) {
4656 addCase = true;
4657 switchExclusivelyCovered = true;
4658 }
4659 else if (condInt > lhsInt) {
4660 if (const Expr *RHS = CS->getRHS()) {
4661 // Evaluate the RHS of the case value.
4662 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
4663 if (V2 >= condInt) {
4664 addCase = true;
4665 switchExclusivelyCovered = true;
4666 }
4667 }
4668 }
4669 }
4670 else
4671 addCase = true;
4672 }
4673 return addCase;
4674}
4675
4676CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
4677 // CaseStmts are essentially labels, so they are the first statement in a
4678 // block.
4679 CFGBlock *TopBlock = nullptr, *LastBlock = nullptr;
4680
4681 if (Stmt *Sub = CS->getSubStmt()) {
4682 // For deeply nested chains of CaseStmts, instead of doing a recursion
4683 // (which can blow out the stack), manually unroll and create blocks
4684 // along the way.
4685 while (isa<CaseStmt>(Val: Sub)) {
4686 CFGBlock *currentBlock = createBlock(add_successor: false);
4687 currentBlock->setLabel(CS);
4688
4689 if (TopBlock)
4690 addSuccessor(B: LastBlock, S: currentBlock);
4691 else
4692 TopBlock = currentBlock;
4693
4694 addSuccessor(B: SwitchTerminatedBlock,
4695 S: shouldAddCase(switchExclusivelyCovered, switchCond,
4696 CS, Ctx&: *Context)
4697 ? currentBlock : nullptr);
4698
4699 LastBlock = currentBlock;
4700 CS = cast<CaseStmt>(Val: Sub);
4701 Sub = CS->getSubStmt();
4702 }
4703
4704 addStmt(S: Sub);
4705 }
4706
4707 CFGBlock *CaseBlock = Block;
4708 if (!CaseBlock)
4709 CaseBlock = createBlock();
4710
4711 // Cases statements partition blocks, so this is the top of the basic block we
4712 // were processing (the "case XXX:" is the label).
4713 CaseBlock->setLabel(CS);
4714
4715 if (badCFG)
4716 return nullptr;
4717
4718 // Add this block to the list of successors for the block with the switch
4719 // statement.
4720 assert(SwitchTerminatedBlock);
4721 addSuccessor(B: SwitchTerminatedBlock, S: CaseBlock,
4722 IsReachable: shouldAddCase(switchExclusivelyCovered, switchCond,
4723 CS, Ctx&: *Context));
4724
4725 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4726 Block = nullptr;
4727
4728 if (TopBlock) {
4729 addSuccessor(B: LastBlock, S: CaseBlock);
4730 Succ = TopBlock;
4731 } else {
4732 // This block is now the implicit successor of other blocks.
4733 Succ = CaseBlock;
4734 }
4735
4736 return Succ;
4737}
4738
4739CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
4740 if (Terminator->getSubStmt())
4741 addStmt(S: Terminator->getSubStmt());
4742
4743 DefaultCaseBlock = Block;
4744
4745 if (!DefaultCaseBlock)
4746 DefaultCaseBlock = createBlock();
4747
4748 // Default statements partition blocks, so this is the top of the basic block
4749 // we were processing (the "default:" is the label).
4750 DefaultCaseBlock->setLabel(Terminator);
4751
4752 if (badCFG)
4753 return nullptr;
4754
4755 // Unlike case statements, we don't add the default block to the successors
4756 // for the switch statement immediately. This is done when we finish
4757 // processing the switch statement. This allows for the default case
4758 // (including a fall-through to the code after the switch statement) to always
4759 // be the last successor of a switch-terminated block.
4760
4761 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4762 Block = nullptr;
4763
4764 // This block is now the implicit successor of other blocks.
4765 Succ = DefaultCaseBlock;
4766
4767 return DefaultCaseBlock;
4768}
4769
4770CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
4771 // "try"/"catch" is a control-flow statement. Thus we stop processing the
4772 // current block.
4773 CFGBlock *TrySuccessor = nullptr;
4774
4775 if (Block) {
4776 if (badCFG)
4777 return nullptr;
4778 TrySuccessor = Block;
4779 } else
4780 TrySuccessor = Succ;
4781
4782 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
4783
4784 // Create a new block that will contain the try statement.
4785 CFGBlock *NewTryTerminatedBlock = createBlock(add_successor: false);
4786 // Add the terminator in the try block.
4787 NewTryTerminatedBlock->setTerminator(Terminator);
4788
4789 bool HasCatchAll = false;
4790 for (unsigned I = 0, E = Terminator->getNumHandlers(); I != E; ++I) {
4791 // The code after the try is the implicit successor.
4792 Succ = TrySuccessor;
4793 CXXCatchStmt *CS = Terminator->getHandler(i: I);
4794 if (CS->getExceptionDecl() == nullptr) {
4795 HasCatchAll = true;
4796 }
4797 Block = nullptr;
4798 CFGBlock *CatchBlock = VisitCXXCatchStmt(S: CS);
4799 if (!CatchBlock)
4800 return nullptr;
4801 // Add this block to the list of successors for the block with the try
4802 // statement.
4803 addSuccessor(B: NewTryTerminatedBlock, S: CatchBlock);
4804 }
4805 if (!HasCatchAll) {
4806 if (PrevTryTerminatedBlock)
4807 addSuccessor(B: NewTryTerminatedBlock, S: PrevTryTerminatedBlock);
4808 else
4809 addSuccessor(B: NewTryTerminatedBlock, S: &cfg->getExit());
4810 }
4811
4812 // The code after the try is the implicit successor.
4813 Succ = TrySuccessor;
4814
4815 // Save the current "try" context.
4816 SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);
4817 cfg->addTryDispatchBlock(block: TryTerminatedBlock);
4818
4819 assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
4820 Block = nullptr;
4821 return addStmt(S: Terminator->getTryBlock());
4822}
4823
4824CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
4825 // CXXCatchStmt are treated like labels, so they are the first statement in a
4826 // block.
4827
4828 // Save local scope position because in case of exception variable ScopePos
4829 // won't be restored when traversing AST.
4830 SaveAndRestore save_scope_pos(ScopePos);
4831
4832 // Create local scope for possible exception variable.
4833 // Store scope position. Add implicit destructor.
4834 if (VarDecl *VD = CS->getExceptionDecl()) {
4835 LocalScope::const_iterator BeginScopePos = ScopePos;
4836 addLocalScopeForVarDecl(VD);
4837 addAutomaticObjHandling(B: ScopePos, E: BeginScopePos, S: CS);
4838 }
4839
4840 if (CS->getHandlerBlock())
4841 addStmt(S: CS->getHandlerBlock());
4842
4843 CFGBlock *CatchBlock = Block;
4844 if (!CatchBlock)
4845 CatchBlock = createBlock();
4846
4847 // CXXCatchStmt is more than just a label. They have semantic meaning
4848 // as well, as they implicitly "initialize" the catch variable. Add
4849 // it to the CFG as a CFGElement so that the control-flow of these
4850 // semantics gets captured.
4851 appendStmt(B: CatchBlock, S: CS);
4852
4853 // Also add the CXXCatchStmt as a label, to mirror handling of regular
4854 // labels.
4855 CatchBlock->setLabel(CS);
4856
4857 // Bail out if the CFG is bad.
4858 if (badCFG)
4859 return nullptr;
4860
4861 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4862 Block = nullptr;
4863
4864 return CatchBlock;
4865}
4866
4867CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
4868 // C++0x for-range statements are specified as [stmt.ranged]:
4869 //
4870 // {
4871 // auto && __range = range-init;
4872 // for ( auto __begin = begin-expr,
4873 // __end = end-expr;
4874 // __begin != __end;
4875 // ++__begin ) {
4876 // for-range-declaration = *__begin;
4877 // statement
4878 // }
4879 // }
4880
4881 // Save local scope position before the addition of the implicit variables.
4882 SaveAndRestore save_scope_pos(ScopePos);
4883
4884 // Create local scopes and destructors for init, range, begin and end
4885 // variables.
4886 if (Stmt *Init = S->getInit())
4887 addLocalScopeForStmt(S: Init);
4888 if (Stmt *Range = S->getRangeStmt())
4889 addLocalScopeForStmt(S: Range);
4890 if (Stmt *Begin = S->getBeginStmt())
4891 addLocalScopeForStmt(S: Begin);
4892 if (Stmt *End = S->getEndStmt())
4893 addLocalScopeForStmt(S: End);
4894 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S);
4895
4896 LocalScope::const_iterator ContinueScopePos = ScopePos;
4897
4898 // "for" is a control-flow statement. Thus we stop processing the current
4899 // block.
4900 CFGBlock *LoopSuccessor = nullptr;
4901 if (Block) {
4902 if (badCFG)
4903 return nullptr;
4904 LoopSuccessor = Block;
4905 } else
4906 LoopSuccessor = Succ;
4907
4908 // Save the current value for the break targets.
4909 // All breaks should go to the code following the loop.
4910 SaveAndRestore save_break(BreakJumpTarget);
4911 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4912
4913 // The block for the __begin != __end expression.
4914 CFGBlock *ConditionBlock = createBlock(add_successor: false);
4915 ConditionBlock->setTerminator(S);
4916
4917 // Now add the actual condition to the condition block.
4918 if (Expr *C = S->getCond()) {
4919 Block = ConditionBlock;
4920 CFGBlock *BeginConditionBlock = addStmt(S: C);
4921 if (badCFG)
4922 return nullptr;
4923 assert(BeginConditionBlock == ConditionBlock &&
4924 "condition block in for-range was unexpectedly complex");
4925 (void)BeginConditionBlock;
4926 }
4927
4928 // The condition block is the implicit successor for the loop body as well as
4929 // any code above the loop.
4930 Succ = ConditionBlock;
4931
4932 // See if this is a known constant.
4933 TryResult KnownVal(true);
4934
4935 if (S->getCond())
4936 KnownVal = tryEvaluateBool(S: S->getCond());
4937
4938 // Now create the loop body.
4939 {
4940 assert(S->getBody());
4941
4942 // Save the current values for Block, Succ, and continue targets.
4943 SaveAndRestore save_Block(Block), save_Succ(Succ);
4944 SaveAndRestore save_continue(ContinueJumpTarget);
4945
4946 // Generate increment code in its own basic block. This is the target of
4947 // continue statements.
4948 Block = nullptr;
4949 Succ = addStmt(S: S->getInc());
4950 if (badCFG)
4951 return nullptr;
4952 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
4953
4954 // The starting block for the loop increment is the block that should
4955 // represent the 'loop target' for looping back to the start of the loop.
4956 ContinueJumpTarget.block->setLoopTarget(S);
4957
4958 // Finish up the increment block and prepare to start the loop body.
4959 assert(Block);
4960 if (badCFG)
4961 return nullptr;
4962 Block = nullptr;
4963
4964 // Add implicit scope and dtors for loop variable.
4965 addLocalScopeAndDtors(S: S->getLoopVarStmt());
4966
4967 // If body is not a compound statement create implicit scope
4968 // and add destructors.
4969 if (!isa<CompoundStmt>(Val: S->getBody()))
4970 addLocalScopeAndDtors(S: S->getBody());
4971
4972 // Populate a new block to contain the loop body and loop variable.
4973 addStmt(S: S->getBody());
4974
4975 if (badCFG)
4976 return nullptr;
4977 CFGBlock *LoopVarStmtBlock = addStmt(S: S->getLoopVarStmt());
4978 if (badCFG)
4979 return nullptr;
4980
4981 // This new body block is a successor to our condition block.
4982 addSuccessor(B: ConditionBlock,
4983 S: KnownVal.isFalse() ? nullptr : LoopVarStmtBlock);
4984 }
4985
4986 // Link up the condition block with the code that follows the loop (the
4987 // false branch).
4988 addSuccessor(B: ConditionBlock, S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
4989
4990 // Add the initialization statements.
4991 Block = createBlock();
4992 addStmt(S: S->getBeginStmt());
4993 addStmt(S: S->getEndStmt());
4994 CFGBlock *Head = addStmt(S: S->getRangeStmt());
4995 if (S->getInit())
4996 Head = addStmt(S: S->getInit());
4997 return Head;
4998}
4999
5000CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
5001 AddStmtChoice asc,
5002 bool ExternallyDestructed) {
5003 if (BuildOpts.AddTemporaryDtors || BuildOpts.AddLifetime) {
5004 // If adding implicit destructors visit the full expression for adding
5005 // destructors of temporaries.
5006 TempDtorContext Context;
5007 Expr *FullExpr = E->getSubExpr();
5008 VisitForTemporaries(E: FullExpr, ExternallyDestructed, Context);
5009
5010 addFullExprCleanupMarker(Context, CleanupExpr: E);
5011
5012 // Full expression has to be added as CFGStmt so it will be sequenced
5013 // before destructors of it's temporaries.
5014 asc = asc.withAlwaysAdd(alwaysAdd: true);
5015 }
5016 return Visit(S: E->getSubExpr(), asc);
5017}
5018
5019CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
5020 AddStmtChoice asc) {
5021 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
5022 autoCreateBlock();
5023 appendStmt(B: Block, S: E);
5024
5025 findConstructionContexts(
5026 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: E),
5027 Child: E->getSubExpr());
5028
5029 // We do not want to propagate the AlwaysAdd property.
5030 asc = asc.withAlwaysAdd(alwaysAdd: false);
5031 }
5032 return Visit(S: E->getSubExpr(), asc);
5033}
5034
5035CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
5036 AddStmtChoice asc) {
5037 // If the constructor takes objects as arguments by value, we need to properly
5038 // construct these objects. Construction contexts we find here aren't for the
5039 // constructor C, they're for its arguments only.
5040 findConstructionContextsForArguments(E: C);
5041 appendConstructor(CE: C);
5042
5043 return VisitChildren(S: C);
5044}
5045
5046CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
5047 AddStmtChoice asc) {
5048 autoCreateBlock();
5049 appendStmt(B: Block, S: NE);
5050
5051 findConstructionContexts(
5052 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: NE),
5053 Child: const_cast<CXXConstructExpr *>(NE->getConstructExpr()));
5054
5055 if (NE->getInitializer())
5056 Block = Visit(S: NE->getInitializer());
5057
5058 if (BuildOpts.AddCXXNewAllocator)
5059 appendNewAllocator(B: Block, NE);
5060
5061 if (NE->isArray() && *NE->getArraySize())
5062 Block = Visit(S: *NE->getArraySize());
5063
5064 for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),
5065 E = NE->placement_arg_end(); I != E; ++I)
5066 Block = Visit(S: *I);
5067
5068 return Block;
5069}
5070
5071CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
5072 AddStmtChoice asc) {
5073 autoCreateBlock();
5074 appendStmt(B: Block, S: DE);
5075 QualType DTy = DE->getDestroyedType();
5076 if (!DTy.isNull()) {
5077 DTy = DTy.getNonReferenceType();
5078 CXXRecordDecl *RD = Context->getBaseElementType(QT: DTy)->getAsCXXRecordDecl();
5079 if (RD) {
5080 if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())
5081 appendDeleteDtor(B: Block, RD, DE);
5082 }
5083 }
5084
5085 return VisitChildren(S: DE);
5086}
5087
5088CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
5089 AddStmtChoice asc) {
5090 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
5091 autoCreateBlock();
5092 appendStmt(B: Block, S: E);
5093 // We do not want to propagate the AlwaysAdd property.
5094 asc = asc.withAlwaysAdd(alwaysAdd: false);
5095 }
5096 return Visit(S: E->getSubExpr(), asc);
5097}
5098
5099CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *E,
5100 AddStmtChoice asc) {
5101 // If the constructor takes objects as arguments by value, we need to properly
5102 // construct these objects. Construction contexts we find here aren't for the
5103 // constructor C, they're for its arguments only.
5104 findConstructionContextsForArguments(E);
5105 appendConstructor(CE: E);
5106
5107 return VisitChildren(S: E);
5108}
5109
5110CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
5111 AddStmtChoice asc) {
5112 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
5113 autoCreateBlock();
5114 appendStmt(B: Block, S: E);
5115 }
5116
5117 if (E->getCastKind() == CK_IntegralToBoolean)
5118 tryEvaluateBool(S: E->getSubExpr()->IgnoreParens());
5119
5120 return Visit(S: E->getSubExpr(), asc: AddStmtChoice());
5121}
5122
5123CFGBlock *CFGBuilder::VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc) {
5124 return Visit(S: E->getSubExpr(), asc: AddStmtChoice());
5125}
5126
5127CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
5128 // Lazily create the indirect-goto dispatch block if there isn't one already.
5129 CFGBlock *IBlock = cfg->getIndirectGotoBlock();
5130
5131 if (!IBlock) {
5132 IBlock = createBlock(add_successor: false);
5133 cfg->setIndirectGotoBlock(IBlock);
5134 }
5135
5136 // IndirectGoto is a control-flow statement. Thus we stop processing the
5137 // current block and create a new one.
5138 if (badCFG)
5139 return nullptr;
5140
5141 Block = createBlock(add_successor: false);
5142 Block->setTerminator(I);
5143 addSuccessor(B: Block, S: IBlock);
5144 return addStmt(S: I->getTarget());
5145}
5146
5147CFGBlock *CFGBuilder::VisitForTemporaries(Stmt *E, bool ExternallyDestructed,
5148 TempDtorContext &Context) {
5149
5150tryAgain:
5151 if (!E) {
5152 badCFG = true;
5153 return nullptr;
5154 }
5155 switch (E->getStmtClass()) {
5156 default:
5157 return VisitChildrenForTemporaries(E, ExternallyDestructed: false, Context);
5158
5159 case Stmt::InitListExprClass:
5160 return VisitChildrenForTemporaries(E, ExternallyDestructed, Context);
5161
5162 case Stmt::BinaryOperatorClass:
5163 case Stmt::CompoundAssignOperatorClass:
5164 return VisitBinaryOperatorForTemporaries(E: cast<BinaryOperator>(Val: E),
5165 ExternallyDestructed, Context);
5166
5167 case Stmt::CXXOperatorCallExprClass:
5168 return VisitCXXOperatorCallExprForTemporaryDtors(
5169 E: cast<CXXOperatorCallExpr>(Val: E), Context);
5170
5171 case Stmt::CXXBindTemporaryExprClass:
5172 return VisitCXXBindTemporaryExprForTemporaryDtors(
5173 E: cast<CXXBindTemporaryExpr>(Val: E), ExternallyDestructed, Context);
5174
5175 case Stmt::BinaryConditionalOperatorClass:
5176 case Stmt::ConditionalOperatorClass:
5177 return VisitConditionalOperatorForTemporaries(
5178 E: cast<AbstractConditionalOperator>(Val: E), ExternallyDestructed, Context);
5179
5180 case Stmt::ImplicitCastExprClass:
5181 // For implicit cast we want ExternallyDestructed to be passed further.
5182 E = cast<CastExpr>(Val: E)->getSubExpr();
5183 goto tryAgain;
5184
5185 case Stmt::CXXFunctionalCastExprClass:
5186 // For functional cast we want ExternallyDestructed to be passed further.
5187 E = cast<CXXFunctionalCastExpr>(Val: E)->getSubExpr();
5188 goto tryAgain;
5189
5190 case Stmt::ConstantExprClass:
5191 E = cast<ConstantExpr>(Val: E)->getSubExpr();
5192 goto tryAgain;
5193
5194 case Stmt::ParenExprClass:
5195 E = cast<ParenExpr>(Val: E)->getSubExpr();
5196 goto tryAgain;
5197
5198 case Stmt::MaterializeTemporaryExprClass: {
5199 const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(Val: E);
5200 ExternallyDestructed = (MTE->getStorageDuration() != SD_FullExpression);
5201 if (BuildOpts.AddLifetime && !ExternallyDestructed)
5202 Context.track(MTE);
5203 SmallVector<const Expr *, 2> CommaLHSs;
5204 SmallVector<SubobjectAdjustment, 2> Adjustments;
5205 // Find the expression whose lifetime needs to be extended.
5206 E = const_cast<Expr *>(
5207 cast<MaterializeTemporaryExpr>(Val: E)
5208 ->getSubExpr()
5209 ->skipRValueSubobjectAdjustments(CommaLHS&: CommaLHSs, Adjustments));
5210 // Visit the skipped comma operator left-hand sides for other temporaries.
5211 for (const Expr *CommaLHS : CommaLHSs) {
5212 VisitForTemporaries(E: const_cast<Expr *>(CommaLHS),
5213 /*ExternallyDestructed=*/false, Context);
5214 }
5215 goto tryAgain;
5216 }
5217
5218 case Stmt::BlockExprClass:
5219 // Don't recurse into blocks; their subexpressions don't get evaluated
5220 // here.
5221 return Block;
5222
5223 case Stmt::LambdaExprClass: {
5224 // For lambda expressions, only recurse into the capture initializers,
5225 // and not the body.
5226 auto *LE = cast<LambdaExpr>(Val: E);
5227 CFGBlock *B = Block;
5228 for (Expr *Init : LE->capture_inits()) {
5229 if (Init) {
5230 if (CFGBlock *R = VisitForTemporaries(
5231 E: Init, /*ExternallyDestructed=*/true, Context))
5232 B = R;
5233 }
5234 }
5235 return B;
5236 }
5237
5238 case Stmt::StmtExprClass:
5239 // Don't recurse into statement expressions; any cleanups inside them
5240 // will be wrapped in their own ExprWithCleanups.
5241 return Block;
5242
5243 case Stmt::CXXDefaultArgExprClass:
5244 E = cast<CXXDefaultArgExpr>(Val: E)->getExpr();
5245 goto tryAgain;
5246
5247 case Stmt::CXXDefaultInitExprClass:
5248 E = cast<CXXDefaultInitExpr>(Val: E)->getExpr();
5249 goto tryAgain;
5250 }
5251}
5252
5253CFGBlock *CFGBuilder::VisitChildrenForTemporaries(Stmt *E,
5254 bool ExternallyDestructed,
5255 TempDtorContext &Context) {
5256 if (isa<LambdaExpr>(Val: E)) {
5257 // Do not visit the children of lambdas; they have their own CFGs.
5258 return Block;
5259 }
5260
5261 // When visiting children for destructors or lifetime markers we want to visit
5262 // them in reverse order that they will appear in the CFG. Because the CFG is
5263 // built bottom-up, this means we visit them in their natural order, which
5264 // reverses them in the CFG.
5265 CFGBlock *B = Block;
5266 for (Stmt *Child : E->children())
5267 if (Child)
5268 if (CFGBlock *R =
5269 VisitForTemporaries(E: Child, ExternallyDestructed, Context))
5270 B = R;
5271
5272 return B;
5273}
5274
5275CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaries(
5276 BinaryOperator *E, bool ExternallyDestructed, TempDtorContext &Context) {
5277 if (E->isCommaOp()) {
5278 // For the comma operator, the LHS expression is evaluated before the RHS
5279 // expression, so prepend temporary destructors for the LHS first.
5280 CFGBlock *LHSBlock = VisitForTemporaries(E: E->getLHS(), ExternallyDestructed: false, Context);
5281 CFGBlock *RHSBlock =
5282 VisitForTemporaries(E: E->getRHS(), ExternallyDestructed, Context);
5283 return RHSBlock ? RHSBlock : LHSBlock;
5284 }
5285
5286 if (E->isLogicalOp()) {
5287 VisitForTemporaries(E: E->getLHS(), ExternallyDestructed: false, Context);
5288 TryResult RHSExecuted = tryEvaluateBool(S: E->getLHS());
5289 if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr)
5290 RHSExecuted.negate();
5291
5292 // We do not know at CFG-construction time whether the right-hand-side was
5293 // executed, thus we add a branch node that depends on the temporary
5294 // constructor call.
5295 TempDtorContext RHSContext(
5296 bothKnownTrue(R1: Context.KnownExecuted, R2: RHSExecuted));
5297 VisitForTemporaries(E: E->getRHS(), ExternallyDestructed: false, Context&: RHSContext);
5298 InsertTempDecisionBlock(Context: RHSContext);
5299
5300 if (BuildOpts.AddLifetime)
5301 Context.CollectedMTEs.append(RHS: RHSContext.CollectedMTEs);
5302
5303 return Block;
5304 }
5305
5306 if (E->isAssignmentOp()) {
5307 // For assignment operators, the RHS expression is evaluated before the LHS
5308 // expression, so prepend temporary destructors for the RHS first.
5309 CFGBlock *RHSBlock = VisitForTemporaries(E: E->getRHS(), ExternallyDestructed: false, Context);
5310 CFGBlock *LHSBlock = VisitForTemporaries(E: E->getLHS(), ExternallyDestructed: false, Context);
5311 return LHSBlock ? LHSBlock : RHSBlock;
5312 }
5313
5314 // Any other operator is visited normally.
5315 return VisitChildrenForTemporaries(E, ExternallyDestructed, Context);
5316}
5317
5318CFGBlock *CFGBuilder::VisitCXXOperatorCallExprForTemporaryDtors(
5319 CXXOperatorCallExpr *E, TempDtorContext &Context) {
5320 if (E->isAssignmentOp()) {
5321 // For assignment operators, the RHS expression is evaluated before the LHS
5322 // expression, so prepend temporary destructors for the RHS first.
5323 CFGBlock *RHSBlock = VisitForTemporaries(E: E->getArg(Arg: 1), ExternallyDestructed: false, Context);
5324 CFGBlock *LHSBlock = VisitForTemporaries(E: E->getArg(Arg: 0), ExternallyDestructed: false, Context);
5325 return LHSBlock ? LHSBlock : RHSBlock;
5326 }
5327 return VisitChildrenForTemporaries(E, ExternallyDestructed: false, Context);
5328}
5329
5330CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
5331 CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context) {
5332 // First add destructors for temporaries in subexpression.
5333 // Because VisitCXXBindTemporaryExpr calls setDestructed:
5334 CFGBlock *B = VisitForTemporaries(E: E->getSubExpr(), ExternallyDestructed: true, Context);
5335 if (!ExternallyDestructed && BuildOpts.AddImplicitDtors &&
5336 BuildOpts.AddTemporaryDtors) {
5337 // If lifetime of temporary is not prolonged (by assigning to constant
5338 // reference) add destructor for it.
5339
5340 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
5341
5342 if (Dtor->getParent()->isAnyDestructorNoReturn()) {
5343 // If the destructor is marked as a no-return destructor, we need to
5344 // create a new block for the destructor which does not have as a
5345 // successor anything built thus far. Control won't flow out of this
5346 // block.
5347 if (B) Succ = B;
5348 Block = createNoReturnBlock();
5349 } else if (Context.needsTempDtorBranch()) {
5350 // If we need to introduce a branch, we add a new block that we will hook
5351 // up to a decision block later.
5352 if (B) Succ = B;
5353 Block = createBlock();
5354 } else {
5355 autoCreateBlock();
5356 }
5357 if (Context.needsTempDtorBranch()) {
5358 Context.setDecisionPoint(S: Succ, E);
5359 }
5360 appendTemporaryDtor(B: Block, E);
5361 B = Block;
5362 }
5363 return B;
5364}
5365
5366void CFGBuilder::InsertTempDecisionBlock(const TempDtorContext &Context,
5367 CFGBlock *FalseSucc) {
5368 if (!Context.TerminatorExpr) {
5369 // If no temporary was found, we do not need to insert a decision point.
5370 return;
5371 }
5372 assert(Context.TerminatorExpr);
5373 CFGBlock *Decision = createBlock(add_successor: false);
5374 Decision->setTerminator(CFGTerminator(Context.TerminatorExpr,
5375 CFGTerminator::TemporaryDtorsBranch));
5376 addSuccessor(B: Decision, S: Block, IsReachable: !Context.KnownExecuted.isFalse());
5377 addSuccessor(B: Decision, S: FalseSucc ? FalseSucc : Context.Succ,
5378 IsReachable: !Context.KnownExecuted.isTrue());
5379 Block = Decision;
5380}
5381
5382CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaries(
5383 AbstractConditionalOperator *E, bool ExternallyDestructed,
5384 TempDtorContext &Context) {
5385 VisitForTemporaries(E: E->getCond(), ExternallyDestructed: false, Context);
5386 CFGBlock *ConditionBlock = Block;
5387 CFGBlock *ConditionSucc = Succ;
5388 TryResult ConditionVal = tryEvaluateBool(S: E->getCond());
5389 TryResult NegatedVal = ConditionVal;
5390 if (NegatedVal.isKnown()) NegatedVal.negate();
5391
5392 TempDtorContext TrueContext(
5393 bothKnownTrue(R1: Context.KnownExecuted, R2: ConditionVal));
5394 VisitForTemporaries(E: E->getTrueExpr(), ExternallyDestructed, Context&: TrueContext);
5395 CFGBlock *TrueBlock = Block;
5396
5397 Block = ConditionBlock;
5398 Succ = ConditionSucc;
5399 TempDtorContext FalseContext(
5400 bothKnownTrue(R1: Context.KnownExecuted, R2: NegatedVal));
5401 VisitForTemporaries(E: E->getFalseExpr(), ExternallyDestructed, Context&: FalseContext);
5402
5403 if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) {
5404 InsertTempDecisionBlock(Context: FalseContext, FalseSucc: TrueBlock);
5405 } else if (TrueContext.TerminatorExpr) {
5406 Block = TrueBlock;
5407 InsertTempDecisionBlock(Context: TrueContext);
5408 } else {
5409 InsertTempDecisionBlock(Context: FalseContext);
5410 }
5411 if (BuildOpts.AddLifetime) {
5412 Context.CollectedMTEs.append(RHS: TrueContext.CollectedMTEs);
5413 Context.CollectedMTEs.append(RHS: FalseContext.CollectedMTEs);
5414 }
5415
5416 return Block;
5417}
5418
5419CFGBlock *CFGBuilder::VisitOMPExecutableDirective(OMPExecutableDirective *D,
5420 AddStmtChoice asc) {
5421 if (asc.alwaysAdd(builder&: *this, stmt: D)) {
5422 autoCreateBlock();
5423 appendStmt(B: Block, S: D);
5424 }
5425
5426 // Iterate over all used expression in clauses.
5427 CFGBlock *B = Block;
5428
5429 // Reverse the elements to process them in natural order. Iterators are not
5430 // bidirectional, so we need to create temp vector.
5431 SmallVector<Stmt *, 8> Used(
5432 OMPExecutableDirective::used_clauses_children(Clauses: D->clauses()));
5433 for (Stmt *S : llvm::reverse(C&: Used)) {
5434 assert(S && "Expected non-null used-in-clause child.");
5435 if (CFGBlock *R = Visit(S))
5436 B = R;
5437 }
5438 // Visit associated structured block if any.
5439 if (!D->isStandaloneDirective()) {
5440 Stmt *S = D->getRawStmt();
5441 if (!isa<CompoundStmt>(Val: S))
5442 addLocalScopeAndDtors(S);
5443 if (CFGBlock *R = addStmt(S))
5444 B = R;
5445 }
5446
5447 return B;
5448}
5449
5450/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
5451/// no successors or predecessors. If this is the first block created in the
5452/// CFG, it is automatically set to be the Entry and Exit of the CFG.
5453CFGBlock *CFG::createBlock() {
5454 bool first_block = begin() == end();
5455
5456 // Create the block.
5457 CFGBlock *Mem = new (getAllocator()) CFGBlock(NumBlockIDs++, BlkBVC, this);
5458 Blocks.push_back(Elt: Mem, C&: BlkBVC);
5459
5460 // If this is the first block, set it as the Entry and Exit.
5461 if (first_block)
5462 Entry = Exit = &back();
5463
5464 // Return the block.
5465 return &back();
5466}
5467
5468/// buildCFG - Constructs a CFG from an AST.
5469std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,
5470 ASTContext *C, const BuildOptions &BO) {
5471 llvm::TimeTraceScope TimeProfile("BuildCFG");
5472 CFGBuilder Builder(C, BO);
5473 return Builder.buildCFG(D, Statement);
5474}
5475
5476bool CFG::isLinear() const {
5477 // Quick path: if we only have the ENTRY block, the EXIT block, and some code
5478 // in between, then we have no room for control flow.
5479 if (size() <= 3)
5480 return true;
5481
5482 // Traverse the CFG until we find a branch.
5483 // TODO: While this should still be very fast,
5484 // maybe we should cache the answer.
5485 llvm::SmallPtrSet<const CFGBlock *, 4> Visited;
5486 const CFGBlock *B = Entry;
5487 while (B != Exit) {
5488 auto IteratorAndFlag = Visited.insert(Ptr: B);
5489 if (!IteratorAndFlag.second) {
5490 // We looped back to a block that we've already visited. Not linear.
5491 return false;
5492 }
5493
5494 // Iterate over reachable successors.
5495 const CFGBlock *FirstReachableB = nullptr;
5496 for (const CFGBlock::AdjacentBlock &AB : B->succs()) {
5497 if (!AB.isReachable())
5498 continue;
5499
5500 if (FirstReachableB == nullptr) {
5501 FirstReachableB = &*AB;
5502 } else {
5503 // We've encountered a branch. It's not a linear CFG.
5504 return false;
5505 }
5506 }
5507
5508 if (!FirstReachableB) {
5509 // We reached a dead end. EXIT is unreachable. This is linear enough.
5510 return true;
5511 }
5512
5513 // There's only one way to move forward. Proceed.
5514 B = FirstReachableB;
5515 }
5516
5517 // We reached EXIT and found no branches.
5518 return true;
5519}
5520
5521const CXXDestructorDecl *
5522CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
5523 switch (getKind()) {
5524 case CFGElement::Initializer:
5525 case CFGElement::NewAllocator:
5526 case CFGElement::LoopExit:
5527 case CFGElement::LifetimeEnds:
5528 case CFGElement::Statement:
5529 case CFGElement::Constructor:
5530 case CFGElement::CXXRecordTypedCall:
5531 case CFGElement::ScopeBegin:
5532 case CFGElement::ScopeEnd:
5533 case CFGElement::FullExprCleanup:
5534 case CFGElement::CleanupFunction:
5535 llvm_unreachable("getDestructorDecl should only be used with "
5536 "ImplicitDtors");
5537 case CFGElement::AutomaticObjectDtor: {
5538 const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();
5539 QualType ty = var->getType();
5540
5541 // FIXME: See CFGBuilder::addLocalScopeForVarDecl.
5542 //
5543 // Lifetime-extending constructs are handled here. This works for a single
5544 // temporary in an initializer expression.
5545 if (ty->isReferenceType()) {
5546 if (const Expr *Init = var->getInit()) {
5547 ty = getReferenceInitTemporaryType(Init);
5548 }
5549 }
5550
5551 while (const ArrayType *arrayType = astContext.getAsArrayType(T: ty)) {
5552 ty = arrayType->getElementType();
5553 }
5554
5555 // The situation when the type of the lifetime-extending reference
5556 // does not correspond to the type of the object is supposed
5557 // to be handled by now. In particular, 'ty' is now the unwrapped
5558 // record type.
5559 const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();
5560 assert(classDecl);
5561 return classDecl->getDestructor();
5562 }
5563 case CFGElement::DeleteDtor: {
5564 const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr();
5565 QualType DTy = DE->getDestroyedType();
5566 DTy = DTy.getNonReferenceType();
5567 const CXXRecordDecl *classDecl =
5568 astContext.getBaseElementType(QT: DTy)->getAsCXXRecordDecl();
5569 return classDecl->getDestructor();
5570 }
5571 case CFGElement::TemporaryDtor: {
5572 const CXXBindTemporaryExpr *bindExpr =
5573 castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
5574 const CXXTemporary *temp = bindExpr->getTemporary();
5575 return temp->getDestructor();
5576 }
5577 case CFGElement::MemberDtor: {
5578 const FieldDecl *field = castAs<CFGMemberDtor>().getFieldDecl();
5579 QualType ty = field->getType();
5580
5581 while (const ArrayType *arrayType = astContext.getAsArrayType(T: ty)) {
5582 ty = arrayType->getElementType();
5583 }
5584
5585 const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();
5586 assert(classDecl);
5587 return classDecl->getDestructor();
5588 }
5589 case CFGElement::BaseDtor:
5590 // Not yet supported.
5591 return nullptr;
5592 }
5593 llvm_unreachable("getKind() returned bogus value");
5594}
5595
5596//===----------------------------------------------------------------------===//
5597// CFGBlock operations.
5598//===----------------------------------------------------------------------===//
5599
5600CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable)
5601 : ReachableBlock(IsReachable ? B : nullptr),
5602 UnreachableBlock(!IsReachable ? B : nullptr,
5603 B && IsReachable ? AB_Normal : AB_Unreachable) {}
5604
5605CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock)
5606 : ReachableBlock(B),
5607 UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock,
5608 B == AlternateBlock ? AB_Alternate : AB_Normal) {}
5609
5610void CFGBlock::addSuccessor(AdjacentBlock Succ,
5611 BumpVectorContext &C) {
5612 if (CFGBlock *B = Succ.getReachableBlock())
5613 B->Preds.push_back(Elt: AdjacentBlock(this, Succ.isReachable()), C);
5614
5615 if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock())
5616 UnreachableB->Preds.push_back(Elt: AdjacentBlock(this, false), C);
5617
5618 Succs.push_back(Elt: Succ, C);
5619}
5620
5621bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
5622 const CFGBlock *From, const CFGBlock *To) {
5623 if (F.IgnoreNullPredecessors && !From)
5624 return true;
5625
5626 if (To && From && F.IgnoreDefaultsWithCoveredEnums) {
5627 // If the 'To' has no label or is labeled but the label isn't a
5628 // CaseStmt then filter this edge.
5629 if (const SwitchStmt *S =
5630 dyn_cast_or_null<SwitchStmt>(Val: From->getTerminatorStmt())) {
5631 if (S->isAllEnumCasesCovered()) {
5632 const Stmt *L = To->getLabel();
5633 if (!L || !isa<CaseStmt>(Val: L))
5634 return true;
5635 }
5636 }
5637 }
5638
5639 return false;
5640}
5641
5642//===----------------------------------------------------------------------===//
5643// CFG pretty printing
5644//===----------------------------------------------------------------------===//
5645
5646namespace {
5647
5648class StmtPrinterHelper : public PrinterHelper {
5649 using StmtMapTy = llvm::DenseMap<const Stmt *, std::pair<unsigned, unsigned>>;
5650 using DeclMapTy = llvm::DenseMap<const Decl *, std::pair<unsigned, unsigned>>;
5651
5652 StmtMapTy StmtMap;
5653 DeclMapTy DeclMap;
5654 signed currentBlock = 0;
5655 unsigned currStmt = 0;
5656 const LangOptions &LangOpts;
5657
5658public:
5659 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
5660 : LangOpts(LO) {
5661 if (!cfg)
5662 return;
5663 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
5664 unsigned j = 1;
5665 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
5666 BI != BEnd; ++BI, ++j ) {
5667 if (std::optional<CFGStmt> SE = BI->getAs<CFGStmt>()) {
5668 const Stmt *stmt= SE->getStmt();
5669 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
5670 StmtMap[stmt] = P;
5671
5672 switch (stmt->getStmtClass()) {
5673 case Stmt::DeclStmtClass:
5674 DeclMap[cast<DeclStmt>(Val: stmt)->getSingleDecl()] = P;
5675 break;
5676 case Stmt::IfStmtClass: {
5677 const VarDecl *var = cast<IfStmt>(Val: stmt)->getConditionVariable();
5678 if (var)
5679 DeclMap[var] = P;
5680 break;
5681 }
5682 case Stmt::ForStmtClass: {
5683 const VarDecl *var = cast<ForStmt>(Val: stmt)->getConditionVariable();
5684 if (var)
5685 DeclMap[var] = P;
5686 break;
5687 }
5688 case Stmt::WhileStmtClass: {
5689 const VarDecl *var =
5690 cast<WhileStmt>(Val: stmt)->getConditionVariable();
5691 if (var)
5692 DeclMap[var] = P;
5693 break;
5694 }
5695 case Stmt::SwitchStmtClass: {
5696 const VarDecl *var =
5697 cast<SwitchStmt>(Val: stmt)->getConditionVariable();
5698 if (var)
5699 DeclMap[var] = P;
5700 break;
5701 }
5702 case Stmt::CXXCatchStmtClass: {
5703 const VarDecl *var =
5704 cast<CXXCatchStmt>(Val: stmt)->getExceptionDecl();
5705 if (var)
5706 DeclMap[var] = P;
5707 break;
5708 }
5709 default:
5710 break;
5711 }
5712 }
5713 }
5714 }
5715 }
5716
5717 ~StmtPrinterHelper() override = default;
5718
5719 const LangOptions &getLangOpts() const { return LangOpts; }
5720 void setBlockID(signed i) { currentBlock = i; }
5721 void setStmtID(unsigned i) { currStmt = i; }
5722
5723 bool handledStmt(Stmt *S, raw_ostream &OS) override {
5724 StmtMapTy::iterator I = StmtMap.find(Val: S);
5725
5726 if (I == StmtMap.end())
5727 return false;
5728
5729 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
5730 && I->second.second == currStmt) {
5731 return false;
5732 }
5733
5734 OS << "[B" << I->second.first << "." << I->second.second << "]";
5735 return true;
5736 }
5737
5738 bool handleDecl(const Decl *D, raw_ostream &OS) {
5739 DeclMapTy::iterator I = DeclMap.find(Val: D);
5740
5741 if (I == DeclMap.end()) {
5742 // ParmVarDecls are not declared in the CFG itself, so they do not appear
5743 // in DeclMap.
5744 if (auto *PVD = dyn_cast_or_null<ParmVarDecl>(Val: D)) {
5745 OS << "[Parm: " << PVD->getNameAsString() << "]";
5746 return true;
5747 }
5748 return false;
5749 }
5750
5751 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
5752 && I->second.second == currStmt) {
5753 return false;
5754 }
5755
5756 OS << "[B" << I->second.first << "." << I->second.second << "]";
5757 return true;
5758 }
5759};
5760
5761class CFGBlockTerminatorPrint
5762 : public StmtVisitor<CFGBlockTerminatorPrint,void> {
5763 raw_ostream &OS;
5764 StmtPrinterHelper* Helper;
5765 PrintingPolicy Policy;
5766
5767public:
5768 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
5769 const PrintingPolicy &Policy)
5770 : OS(os), Helper(helper), Policy(Policy) {
5771 this->Policy.IncludeNewlines = false;
5772 }
5773
5774 void VisitIfStmt(IfStmt *I) {
5775 OS << "if ";
5776 if (Stmt *C = I->getCond())
5777 C->printPretty(OS, Helper, Policy);
5778 }
5779
5780 // Default case.
5781 void VisitStmt(Stmt *Terminator) {
5782 Terminator->printPretty(OS, Helper, Policy);
5783 }
5784
5785 void VisitDeclStmt(DeclStmt *DS) {
5786 VarDecl *VD = cast<VarDecl>(Val: DS->getSingleDecl());
5787 OS << "static init " << VD->getName();
5788 }
5789
5790 void VisitForStmt(ForStmt *F) {
5791 OS << "for (" ;
5792 if (F->getInit())
5793 OS << "...";
5794 OS << "; ";
5795 if (Stmt *C = F->getCond())
5796 C->printPretty(OS, Helper, Policy);
5797 OS << "; ";
5798 if (F->getInc())
5799 OS << "...";
5800 OS << ")";
5801 }
5802
5803 void VisitWhileStmt(WhileStmt *W) {
5804 OS << "while " ;
5805 if (Stmt *C = W->getCond())
5806 C->printPretty(OS, Helper, Policy);
5807 }
5808
5809 void VisitDoStmt(DoStmt *D) {
5810 OS << "do ... while ";
5811 if (Stmt *C = D->getCond())
5812 C->printPretty(OS, Helper, Policy);
5813 }
5814
5815 void VisitSwitchStmt(SwitchStmt *Terminator) {
5816 OS << "switch ";
5817 Terminator->getCond()->printPretty(OS, Helper, Policy);
5818 }
5819
5820 void VisitCXXTryStmt(CXXTryStmt *) { OS << "try ..."; }
5821
5822 void VisitObjCAtTryStmt(ObjCAtTryStmt *) { OS << "@try ..."; }
5823
5824 void VisitSEHTryStmt(SEHTryStmt *CS) { OS << "__try ..."; }
5825
5826 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
5827 if (Stmt *Cond = C->getCond())
5828 Cond->printPretty(OS, Helper, Policy);
5829 OS << " ? ... : ...";
5830 }
5831
5832 void VisitChooseExpr(ChooseExpr *C) {
5833 OS << "__builtin_choose_expr( ";
5834 if (Stmt *Cond = C->getCond())
5835 Cond->printPretty(OS, Helper, Policy);
5836 OS << " )";
5837 }
5838
5839 void VisitIndirectGotoStmt(IndirectGotoStmt *I) {
5840 OS << "goto *";
5841 if (Stmt *T = I->getTarget())
5842 T->printPretty(OS, Helper, Policy);
5843 }
5844
5845 void VisitBinaryOperator(BinaryOperator* B) {
5846 if (!B->isLogicalOp()) {
5847 VisitExpr(E: B);
5848 return;
5849 }
5850
5851 if (B->getLHS())
5852 B->getLHS()->printPretty(OS, Helper, Policy);
5853
5854 switch (B->getOpcode()) {
5855 case BO_LOr:
5856 OS << " || ...";
5857 return;
5858 case BO_LAnd:
5859 OS << " && ...";
5860 return;
5861 default:
5862 llvm_unreachable("Invalid logical operator.");
5863 }
5864 }
5865
5866 void VisitExpr(Expr *E) {
5867 E->printPretty(OS, Helper, Policy);
5868 }
5869
5870public:
5871 void print(CFGTerminator T) {
5872 switch (T.getKind()) {
5873 case CFGTerminator::StmtBranch:
5874 Visit(S: T.getStmt());
5875 break;
5876 case CFGTerminator::TemporaryDtorsBranch:
5877 OS << "(Temp Dtor) ";
5878 Visit(S: T.getStmt());
5879 break;
5880 case CFGTerminator::VirtualBaseBranch:
5881 OS << "(See if most derived ctor has already initialized vbases)";
5882 break;
5883 }
5884 }
5885};
5886
5887} // namespace
5888
5889static void print_initializer(raw_ostream &OS, StmtPrinterHelper &Helper,
5890 const CXXCtorInitializer *I) {
5891 if (I->isBaseInitializer())
5892 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
5893 else if (I->isDelegatingInitializer())
5894 OS << I->getTypeSourceInfo()->getType()->getAsCXXRecordDecl()->getName();
5895 else
5896 OS << I->getAnyMember()->getName();
5897 OS << "(";
5898 if (Expr *IE = I->getInit())
5899 IE->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
5900 OS << ")";
5901
5902 if (I->isBaseInitializer())
5903 OS << " (Base initializer)";
5904 else if (I->isDelegatingInitializer())
5905 OS << " (Delegating initializer)";
5906 else
5907 OS << " (Member initializer)";
5908}
5909
5910static void print_construction_context(raw_ostream &OS,
5911 StmtPrinterHelper &Helper,
5912 const ConstructionContext *CC) {
5913 SmallVector<const Stmt *, 3> Stmts;
5914 switch (CC->getKind()) {
5915 case ConstructionContext::SimpleConstructorInitializerKind: {
5916 OS << ", ";
5917 const auto *SICC = cast<SimpleConstructorInitializerConstructionContext>(Val: CC);
5918 print_initializer(OS, Helper, I: SICC->getCXXCtorInitializer());
5919 return;
5920 }
5921 case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind: {
5922 OS << ", ";
5923 const auto *CICC =
5924 cast<CXX17ElidedCopyConstructorInitializerConstructionContext>(Val: CC);
5925 print_initializer(OS, Helper, I: CICC->getCXXCtorInitializer());
5926 Stmts.push_back(Elt: CICC->getCXXBindTemporaryExpr());
5927 break;
5928 }
5929 case ConstructionContext::SimpleVariableKind: {
5930 const auto *SDSCC = cast<SimpleVariableConstructionContext>(Val: CC);
5931 Stmts.push_back(Elt: SDSCC->getDeclStmt());
5932 break;
5933 }
5934 case ConstructionContext::CXX17ElidedCopyVariableKind: {
5935 const auto *CDSCC = cast<CXX17ElidedCopyVariableConstructionContext>(Val: CC);
5936 Stmts.push_back(Elt: CDSCC->getDeclStmt());
5937 Stmts.push_back(Elt: CDSCC->getCXXBindTemporaryExpr());
5938 break;
5939 }
5940 case ConstructionContext::NewAllocatedObjectKind: {
5941 const auto *NECC = cast<NewAllocatedObjectConstructionContext>(Val: CC);
5942 Stmts.push_back(Elt: NECC->getCXXNewExpr());
5943 break;
5944 }
5945 case ConstructionContext::SimpleReturnedValueKind: {
5946 const auto *RSCC = cast<SimpleReturnedValueConstructionContext>(Val: CC);
5947 Stmts.push_back(Elt: RSCC->getReturnStmt());
5948 break;
5949 }
5950 case ConstructionContext::CXX17ElidedCopyReturnedValueKind: {
5951 const auto *RSCC =
5952 cast<CXX17ElidedCopyReturnedValueConstructionContext>(Val: CC);
5953 Stmts.push_back(Elt: RSCC->getReturnStmt());
5954 Stmts.push_back(Elt: RSCC->getCXXBindTemporaryExpr());
5955 break;
5956 }
5957 case ConstructionContext::SimpleTemporaryObjectKind: {
5958 const auto *TOCC = cast<SimpleTemporaryObjectConstructionContext>(Val: CC);
5959 Stmts.push_back(Elt: TOCC->getCXXBindTemporaryExpr());
5960 Stmts.push_back(Elt: TOCC->getMaterializedTemporaryExpr());
5961 break;
5962 }
5963 case ConstructionContext::ElidedTemporaryObjectKind: {
5964 const auto *TOCC = cast<ElidedTemporaryObjectConstructionContext>(Val: CC);
5965 Stmts.push_back(Elt: TOCC->getCXXBindTemporaryExpr());
5966 Stmts.push_back(Elt: TOCC->getMaterializedTemporaryExpr());
5967 Stmts.push_back(Elt: TOCC->getConstructorAfterElision());
5968 break;
5969 }
5970 case ConstructionContext::LambdaCaptureKind: {
5971 const auto *LCC = cast<LambdaCaptureConstructionContext>(Val: CC);
5972 Helper.handledStmt(S: const_cast<LambdaExpr *>(LCC->getLambdaExpr()), OS);
5973 OS << "+" << LCC->getIndex();
5974 return;
5975 }
5976 case ConstructionContext::ArgumentKind: {
5977 const auto *ACC = cast<ArgumentConstructionContext>(Val: CC);
5978 if (const Stmt *BTE = ACC->getCXXBindTemporaryExpr()) {
5979 OS << ", ";
5980 Helper.handledStmt(S: const_cast<Stmt *>(BTE), OS);
5981 }
5982 OS << ", ";
5983 Helper.handledStmt(S: const_cast<Expr *>(ACC->getCallLikeExpr()), OS);
5984 OS << "+" << ACC->getIndex();
5985 return;
5986 }
5987 }
5988 for (auto I: Stmts)
5989 if (I) {
5990 OS << ", ";
5991 Helper.handledStmt(S: const_cast<Stmt *>(I), OS);
5992 }
5993}
5994
5995static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
5996 const CFGElement &E, bool TerminateWithNewLine = true);
5997
5998void CFGElement::dumpToStream(llvm::raw_ostream &OS,
5999 bool TerminateWithNewLine) const {
6000 LangOptions LangOpts;
6001 StmtPrinterHelper Helper(nullptr, LangOpts);
6002 print_elem(OS, Helper, E: *this, TerminateWithNewLine);
6003}
6004
6005static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
6006 const CFGElement &E, bool TerminateWithNewLine) {
6007 switch (E.getKind()) {
6008 case CFGElement::Kind::Statement:
6009 case CFGElement::Kind::CXXRecordTypedCall:
6010 case CFGElement::Kind::Constructor: {
6011 CFGStmt CS = E.castAs<CFGStmt>();
6012 const Stmt *S = CS.getStmt();
6013 assert(S != nullptr && "Expecting non-null Stmt");
6014
6015 // special printing for statement-expressions.
6016 if (const StmtExpr *SE = dyn_cast<StmtExpr>(Val: S)) {
6017 const CompoundStmt *Sub = SE->getSubStmt();
6018
6019 auto Children = Sub->children();
6020 if (Children.begin() != Children.end()) {
6021 OS << "({ ... ; ";
6022 Helper.handledStmt(S: *SE->getSubStmt()->body_rbegin(),OS);
6023 OS << " })";
6024 if (TerminateWithNewLine)
6025 OS << '\n';
6026 return;
6027 }
6028 }
6029 // special printing for comma expressions.
6030 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(Val: S)) {
6031 if (B->getOpcode() == BO_Comma) {
6032 OS << "... , ";
6033 Helper.handledStmt(S: B->getRHS(),OS);
6034 if (TerminateWithNewLine)
6035 OS << '\n';
6036 return;
6037 }
6038 }
6039 S->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
6040
6041 if (auto VTC = E.getAs<CFGCXXRecordTypedCall>()) {
6042 if (isa<CXXOperatorCallExpr>(Val: S))
6043 OS << " (OperatorCall)";
6044 OS << " (CXXRecordTypedCall";
6045 print_construction_context(OS, Helper, CC: VTC->getConstructionContext());
6046 OS << ")";
6047 } else if (isa<CXXOperatorCallExpr>(Val: S)) {
6048 OS << " (OperatorCall)";
6049 } else if (isa<CXXBindTemporaryExpr>(Val: S)) {
6050 OS << " (BindTemporary)";
6051 } else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(Val: S)) {
6052 OS << " (CXXConstructExpr";
6053 if (std::optional<CFGConstructor> CE = E.getAs<CFGConstructor>()) {
6054 print_construction_context(OS, Helper, CC: CE->getConstructionContext());
6055 }
6056 OS << ", " << CCE->getType() << ")";
6057 } else if (const CastExpr *CE = dyn_cast<CastExpr>(Val: S)) {
6058 OS << " (" << CE->getStmtClassName() << ", " << CE->getCastKindName()
6059 << ", " << CE->getType() << ")";
6060 }
6061
6062 // Expressions need a newline.
6063 if (isa<Expr>(Val: S) && TerminateWithNewLine)
6064 OS << '\n';
6065
6066 return;
6067 }
6068
6069 case CFGElement::Kind::Initializer:
6070 print_initializer(OS, Helper, I: E.castAs<CFGInitializer>().getInitializer());
6071 break;
6072
6073 case CFGElement::Kind::AutomaticObjectDtor: {
6074 CFGAutomaticObjDtor DE = E.castAs<CFGAutomaticObjDtor>();
6075 const VarDecl *VD = DE.getVarDecl();
6076 Helper.handleDecl(D: VD, OS);
6077
6078 QualType T = VD->getType();
6079 if (T->isReferenceType())
6080 T = getReferenceInitTemporaryType(Init: VD->getInit(), FoundMTE: nullptr);
6081
6082 OS << ".~";
6083 T.getUnqualifiedType().print(OS, Policy: PrintingPolicy(Helper.getLangOpts()));
6084 OS << "() (Implicit destructor)";
6085 break;
6086 }
6087
6088 case CFGElement::Kind::CleanupFunction:
6089 OS << "CleanupFunction ("
6090 << E.castAs<CFGCleanupFunction>().getFunctionDecl()->getName() << ")";
6091 break;
6092
6093 case CFGElement::Kind::LifetimeEnds:
6094 Helper.handleDecl(D: E.castAs<CFGLifetimeEnds>().getVarDecl(), OS);
6095 OS << " (Lifetime ends)";
6096 break;
6097
6098 case CFGElement::Kind::FullExprCleanup: {
6099 auto MTEs = E.castAs<CFGFullExprCleanup>().getExpiringMTEs();
6100 size_t MTECount = MTEs.size();
6101 OS << "(FullExprCleanup collected " << MTECount
6102 << (MTECount > 1 ? " MTEs: " : " MTE: ");
6103 bool FirstMTE = true;
6104 for (const MaterializeTemporaryExpr *MTE : MTEs) {
6105 if (!FirstMTE)
6106 OS << ", ";
6107 if (!Helper.handledStmt(S: MTE->getSubExpr(), OS)) {
6108 PrintingPolicy Policy{Helper.getLangOpts()};
6109 Policy.IncludeNewlines = false;
6110 // Pretty print the sub-expresion as a fallback
6111 MTE->printPretty(OS, Helper: &Helper, Policy);
6112 }
6113 FirstMTE = false;
6114 }
6115 OS << ")";
6116 break;
6117 }
6118
6119 case CFGElement::Kind::LoopExit:
6120 OS << E.castAs<CFGLoopExit>().getLoopStmt()->getStmtClassName()
6121 << " (LoopExit)";
6122 break;
6123
6124 case CFGElement::Kind::ScopeBegin:
6125 OS << "CFGScopeBegin(";
6126 if (const VarDecl *VD = E.castAs<CFGScopeBegin>().getVarDecl())
6127 OS << VD->getQualifiedNameAsString();
6128 OS << ")";
6129 break;
6130
6131 case CFGElement::Kind::ScopeEnd:
6132 OS << "CFGScopeEnd(";
6133 if (const VarDecl *VD = E.castAs<CFGScopeEnd>().getVarDecl())
6134 OS << VD->getQualifiedNameAsString();
6135 OS << ")";
6136 break;
6137
6138 case CFGElement::Kind::NewAllocator:
6139 OS << "CFGNewAllocator(";
6140 if (const CXXNewExpr *AllocExpr = E.castAs<CFGNewAllocator>().getAllocatorExpr())
6141 AllocExpr->getType().print(OS, Policy: PrintingPolicy(Helper.getLangOpts()));
6142 OS << ")";
6143 break;
6144
6145 case CFGElement::Kind::DeleteDtor: {
6146 CFGDeleteDtor DE = E.castAs<CFGDeleteDtor>();
6147 const CXXRecordDecl *RD = DE.getCXXRecordDecl();
6148 if (!RD)
6149 return;
6150 CXXDeleteExpr *DelExpr =
6151 const_cast<CXXDeleteExpr*>(DE.getDeleteExpr());
6152 Helper.handledStmt(S: cast<Stmt>(Val: DelExpr->getArgument()), OS);
6153 OS << "->~" << RD->getName().str() << "()";
6154 OS << " (Implicit destructor)";
6155 break;
6156 }
6157
6158 case CFGElement::Kind::BaseDtor: {
6159 const CXXBaseSpecifier *BS = E.castAs<CFGBaseDtor>().getBaseSpecifier();
6160 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
6161 OS << " (Base object destructor)";
6162 break;
6163 }
6164
6165 case CFGElement::Kind::MemberDtor: {
6166 const FieldDecl *FD = E.castAs<CFGMemberDtor>().getFieldDecl();
6167 const Type *T = FD->getType()->getBaseElementTypeUnsafe();
6168 OS << "this->" << FD->getName();
6169 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
6170 OS << " (Member object destructor)";
6171 break;
6172 }
6173
6174 case CFGElement::Kind::TemporaryDtor: {
6175 const CXXBindTemporaryExpr *BT =
6176 E.castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
6177 OS << "~";
6178 BT->getType().print(OS, Policy: PrintingPolicy(Helper.getLangOpts()));
6179 OS << "() (Temporary object destructor)";
6180 break;
6181 }
6182 }
6183 if (TerminateWithNewLine)
6184 OS << '\n';
6185}
6186
6187static void print_block(raw_ostream &OS, const CFG* cfg,
6188 const CFGBlock &B,
6189 StmtPrinterHelper &Helper, bool print_edges,
6190 bool ShowColors) {
6191 Helper.setBlockID(B.getBlockID());
6192
6193 // Print the header.
6194 if (ShowColors)
6195 OS.changeColor(Color: raw_ostream::YELLOW, Bold: true);
6196
6197 OS << "\n [B" << B.getBlockID();
6198
6199 if (&B == &cfg->getEntry())
6200 OS << " (ENTRY)]\n";
6201 else if (&B == &cfg->getExit())
6202 OS << " (EXIT)]\n";
6203 else if (&B == cfg->getIndirectGotoBlock())
6204 OS << " (INDIRECT GOTO DISPATCH)]\n";
6205 else if (B.hasOnlyAnalyzerNoReturnElement())
6206 OS << " (ANALYZER NORETURN)]\n";
6207 else if (B.hasNoReturnElement())
6208 OS << " (NORETURN)]\n";
6209 else
6210 OS << "]\n";
6211
6212 if (ShowColors)
6213 OS.resetColor();
6214
6215 // Print the label of this block.
6216 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {
6217 if (print_edges)
6218 OS << " ";
6219
6220 if (LabelStmt *L = dyn_cast<LabelStmt>(Val: Label))
6221 OS << L->getName();
6222 else if (CaseStmt *C = dyn_cast<CaseStmt>(Val: Label)) {
6223 OS << "case ";
6224 if (const Expr *LHS = C->getLHS())
6225 LHS->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
6226 if (const Expr *RHS = C->getRHS()) {
6227 OS << " ... ";
6228 RHS->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
6229 }
6230 } else if (isa<DefaultStmt>(Val: Label))
6231 OS << "default";
6232 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Val: Label)) {
6233 OS << "catch (";
6234 if (const VarDecl *ED = CS->getExceptionDecl())
6235 ED->print(Out&: OS, Policy: PrintingPolicy(Helper.getLangOpts()), Indentation: 0);
6236 else
6237 OS << "...";
6238 OS << ")";
6239 } else if (ObjCAtCatchStmt *CS = dyn_cast<ObjCAtCatchStmt>(Val: Label)) {
6240 OS << "@catch (";
6241 if (const VarDecl *PD = CS->getCatchParamDecl())
6242 PD->print(Out&: OS, Policy: PrintingPolicy(Helper.getLangOpts()), Indentation: 0);
6243 else
6244 OS << "...";
6245 OS << ")";
6246 } else if (SEHExceptStmt *ES = dyn_cast<SEHExceptStmt>(Val: Label)) {
6247 OS << "__except (";
6248 ES->getFilterExpr()->printPretty(OS, Helper: &Helper,
6249 Policy: PrintingPolicy(Helper.getLangOpts()), Indentation: 0);
6250 OS << ")";
6251 } else
6252 llvm_unreachable("Invalid label statement in CFGBlock.");
6253
6254 OS << ":\n";
6255 }
6256
6257 // Iterate through the statements in the block and print them.
6258 unsigned j = 1;
6259
6260 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
6261 I != E ; ++I, ++j ) {
6262 // Print the statement # in the basic block and the statement itself.
6263 if (print_edges)
6264 OS << " ";
6265
6266 OS << llvm::format(Fmt: "%3d", Vals: j) << ": ";
6267
6268 Helper.setStmtID(j);
6269
6270 print_elem(OS, Helper, E: *I);
6271 }
6272
6273 // Print the terminator of this block.
6274 if (B.getTerminator().isValid()) {
6275 if (ShowColors)
6276 OS.changeColor(Color: raw_ostream::GREEN);
6277
6278 OS << " T: ";
6279
6280 Helper.setBlockID(-1);
6281
6282 PrintingPolicy PP(Helper.getLangOpts());
6283 CFGBlockTerminatorPrint TPrinter(OS, &Helper, PP);
6284 TPrinter.print(T: B.getTerminator());
6285 OS << '\n';
6286
6287 if (ShowColors)
6288 OS.resetColor();
6289 }
6290
6291 if (print_edges) {
6292 // Print the predecessors of this block.
6293 if (!B.pred_empty()) {
6294 const raw_ostream::Colors Color = raw_ostream::BLUE;
6295 if (ShowColors)
6296 OS.changeColor(Color);
6297 OS << " Preds " ;
6298 if (ShowColors)
6299 OS.resetColor();
6300 OS << '(' << B.pred_size() << "):";
6301 unsigned i = 0;
6302
6303 if (ShowColors)
6304 OS.changeColor(Color);
6305
6306 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
6307 I != E; ++I, ++i) {
6308 if (i % 10 == 8)
6309 OS << "\n ";
6310
6311 CFGBlock *B = *I;
6312 bool Reachable = true;
6313 if (!B) {
6314 Reachable = false;
6315 B = I->getPossiblyUnreachableBlock();
6316 }
6317
6318 OS << " B" << B->getBlockID();
6319 if (!Reachable)
6320 OS << "(Unreachable)";
6321 }
6322
6323 if (ShowColors)
6324 OS.resetColor();
6325
6326 OS << '\n';
6327 }
6328
6329 // Print the successors of this block.
6330 if (!B.succ_empty()) {
6331 const raw_ostream::Colors Color = raw_ostream::MAGENTA;
6332 if (ShowColors)
6333 OS.changeColor(Color);
6334 OS << " Succs ";
6335 if (ShowColors)
6336 OS.resetColor();
6337 OS << '(' << B.succ_size() << "):";
6338 unsigned i = 0;
6339
6340 if (ShowColors)
6341 OS.changeColor(Color);
6342
6343 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
6344 I != E; ++I, ++i) {
6345 if (i % 10 == 8)
6346 OS << "\n ";
6347
6348 CFGBlock *B = *I;
6349
6350 bool Reachable = true;
6351 if (!B) {
6352 Reachable = false;
6353 B = I->getPossiblyUnreachableBlock();
6354 }
6355
6356 if (B) {
6357 OS << " B" << B->getBlockID();
6358 if (!Reachable)
6359 OS << "(Unreachable)";
6360 }
6361 else {
6362 OS << " NULL";
6363 }
6364 }
6365
6366 if (ShowColors)
6367 OS.resetColor();
6368 OS << '\n';
6369 }
6370 }
6371}
6372
6373/// dump - A simple pretty printer of a CFG that outputs to stderr.
6374void CFG::dump(const LangOptions &LO, bool ShowColors) const {
6375 print(OS&: llvm::errs(), LO, ShowColors);
6376}
6377
6378/// print - A simple pretty printer of a CFG that outputs to an ostream.
6379void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
6380 StmtPrinterHelper Helper(this, LO);
6381
6382 // Print the entry block.
6383 print_block(OS, cfg: this, B: getEntry(), Helper, print_edges: true, ShowColors);
6384
6385 // Iterate through the CFGBlocks and print them one by one.
6386 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
6387 // Skip the entry block, because we already printed it.
6388 if (&(**I) == &getEntry() || &(**I) == &getExit())
6389 continue;
6390
6391 print_block(OS, cfg: this, B: **I, Helper, print_edges: true, ShowColors);
6392 }
6393
6394 // Print the exit block.
6395 print_block(OS, cfg: this, B: getExit(), Helper, print_edges: true, ShowColors);
6396 OS << '\n';
6397 OS.flush();
6398}
6399
6400size_t CFGBlock::getIndexInCFG() const {
6401 return llvm::find(Range&: *getParent(), Val: this) - getParent()->begin();
6402}
6403
6404/// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
6405void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
6406 bool ShowColors) const {
6407 print(OS&: llvm::errs(), cfg, LO, ShowColors);
6408}
6409
6410LLVM_DUMP_METHOD void CFGBlock::dump() const {
6411 dump(cfg: getParent(), LO: LangOptions(), ShowColors: false);
6412}
6413
6414/// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
6415/// Generally this will only be called from CFG::print.
6416void CFGBlock::print(raw_ostream &OS, const CFG* cfg,
6417 const LangOptions &LO, bool ShowColors) const {
6418 StmtPrinterHelper Helper(cfg, LO);
6419 print_block(OS, cfg, B: *this, Helper, print_edges: true, ShowColors);
6420 OS << '\n';
6421}
6422
6423/// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
6424void CFGBlock::printTerminator(raw_ostream &OS,
6425 const LangOptions &LO) const {
6426 CFGBlockTerminatorPrint TPrinter(OS, nullptr, PrintingPolicy(LO));
6427 TPrinter.print(T: getTerminator());
6428}
6429
6430/// printTerminatorJson - Pretty-prints the terminator in JSON format.
6431void CFGBlock::printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
6432 bool AddQuotes) const {
6433 std::string Buf;
6434 llvm::raw_string_ostream TempOut(Buf);
6435
6436 printTerminator(OS&: TempOut, LO);
6437
6438 Out << JsonFormat(RawSR: Buf, AddQuotes);
6439}
6440
6441// Returns true if by simply looking at the block, we can be sure that it
6442// results in a sink during analysis. This is useful to know when the analysis
6443// was interrupted, and we try to figure out if it would sink eventually.
6444// There may be many more reasons why a sink would appear during analysis
6445// (eg. checkers may generate sinks arbitrarily), but here we only consider
6446// sinks that would be obvious by looking at the CFG.
6447static bool isImmediateSinkBlock(const CFGBlock *Blk) {
6448 if (Blk->hasNoReturnElement())
6449 return true;
6450
6451 // FIXME: Throw-expressions are currently generating sinks during analysis:
6452 // they're not supported yet, and also often used for actually terminating
6453 // the program. So we should treat them as sinks in this analysis as well,
6454 // at least for now, but once we have better support for exceptions,
6455 // we'd need to carefully handle the case when the throw is being
6456 // immediately caught.
6457 if (llvm::any_of(Range: *Blk, P: [](const CFGElement &Elm) {
6458 if (std::optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())
6459 if (isa<CXXThrowExpr>(Val: StmtElm->getStmt()))
6460 return true;
6461 return false;
6462 }))
6463 return true;
6464
6465 return false;
6466}
6467
6468bool CFGBlock::isInevitablySinking() const {
6469 const CFG &Cfg = *getParent();
6470
6471 const CFGBlock *StartBlk = this;
6472 if (isImmediateSinkBlock(Blk: StartBlk))
6473 return true;
6474
6475 llvm::SmallVector<const CFGBlock *, 32> DFSWorkList;
6476 llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
6477
6478 DFSWorkList.push_back(Elt: StartBlk);
6479 while (!DFSWorkList.empty()) {
6480 const CFGBlock *Blk = DFSWorkList.pop_back_val();
6481 Visited.insert(Ptr: Blk);
6482
6483 // If at least one path reaches the CFG exit, it means that control is
6484 // returned to the caller. For now, say that we are not sure what
6485 // happens next. If necessary, this can be improved to analyze
6486 // the parent StackFrame's call site in a similar manner.
6487 if (Blk == &Cfg.getExit())
6488 return false;
6489
6490 for (const auto &Succ : Blk->succs()) {
6491 if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {
6492 if (!isImmediateSinkBlock(Blk: SuccBlk) && !Visited.count(Ptr: SuccBlk)) {
6493 // If the block has reachable child blocks that aren't no-return,
6494 // add them to the worklist.
6495 DFSWorkList.push_back(Elt: SuccBlk);
6496 }
6497 }
6498 }
6499 }
6500
6501 // Nothing reached the exit. It can only mean one thing: there's no return.
6502 return true;
6503}
6504
6505const Expr *CFGBlock::getLastCondition() const {
6506 // If the terminator is a temporary dtor or a virtual base, etc, we can't
6507 // retrieve a meaningful condition, bail out.
6508 if (Terminator.getKind() != CFGTerminator::StmtBranch)
6509 return nullptr;
6510
6511 // Also, if this method was called on a block that doesn't have 2 successors,
6512 // this block doesn't have retrievable condition.
6513 if (succ_size() < 2)
6514 return nullptr;
6515
6516 // FIXME: Is there a better condition expression we can return in this case?
6517 if (size() == 0)
6518 return nullptr;
6519
6520 auto StmtElem = rbegin()->getAs<CFGStmt>();
6521 if (!StmtElem)
6522 return nullptr;
6523
6524 const Stmt *Cond = StmtElem->getStmt();
6525 if (isa<ObjCForCollectionStmt>(Val: Cond) || isa<DeclStmt>(Val: Cond))
6526 return nullptr;
6527
6528 // Only ObjCForCollectionStmt is known not to be a non-Expr terminator, hence
6529 // the cast<>.
6530 return cast<Expr>(Val: Cond)->IgnoreParens();
6531}
6532
6533const Stmt *CFGBlock::getTerminatorCondition(bool StripParens) const {
6534 const Stmt *Terminator = getTerminatorStmt();
6535 if (!Terminator)
6536 return nullptr;
6537
6538 const Expr *E = nullptr;
6539
6540 switch (Terminator->getStmtClass()) {
6541 default:
6542 break;
6543
6544 case Stmt::CXXForRangeStmtClass:
6545 E = cast<CXXForRangeStmt>(Val: Terminator)->getCond();
6546 break;
6547
6548 case Stmt::ForStmtClass:
6549 E = cast<ForStmt>(Val: Terminator)->getCond();
6550 break;
6551
6552 case Stmt::WhileStmtClass:
6553 E = cast<WhileStmt>(Val: Terminator)->getCond();
6554 break;
6555
6556 case Stmt::DoStmtClass:
6557 E = cast<DoStmt>(Val: Terminator)->getCond();
6558 break;
6559
6560 case Stmt::IfStmtClass:
6561 E = cast<IfStmt>(Val: Terminator)->getCond();
6562 break;
6563
6564 case Stmt::ChooseExprClass:
6565 E = cast<ChooseExpr>(Val: Terminator)->getCond();
6566 break;
6567
6568 case Stmt::IndirectGotoStmtClass:
6569 E = cast<IndirectGotoStmt>(Val: Terminator)->getTarget();
6570 break;
6571
6572 case Stmt::SwitchStmtClass:
6573 E = cast<SwitchStmt>(Val: Terminator)->getCond();
6574 break;
6575
6576 case Stmt::BinaryConditionalOperatorClass:
6577 E = cast<BinaryConditionalOperator>(Val: Terminator)->getCond();
6578 break;
6579
6580 case Stmt::ConditionalOperatorClass:
6581 E = cast<ConditionalOperator>(Val: Terminator)->getCond();
6582 break;
6583
6584 case Stmt::BinaryOperatorClass: // '&&' and '||'
6585 E = cast<BinaryOperator>(Val: Terminator)->getLHS();
6586 break;
6587
6588 case Stmt::ObjCForCollectionStmtClass:
6589 return Terminator;
6590 }
6591
6592 if (!StripParens)
6593 return E;
6594
6595 return E ? E->IgnoreParens() : nullptr;
6596}
6597
6598//===----------------------------------------------------------------------===//
6599// CFG Graphviz Visualization
6600//===----------------------------------------------------------------------===//
6601
6602static StmtPrinterHelper *GraphHelper;
6603
6604void CFG::viewCFG(const LangOptions &LO) const {
6605 StmtPrinterHelper H(this, LO);
6606 GraphHelper = &H;
6607 llvm::ViewGraph(G: this,Name: "CFG");
6608 GraphHelper = nullptr;
6609}
6610
6611namespace llvm {
6612
6613template<>
6614struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
6615 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
6616
6617 static std::string getNodeLabel(const CFGBlock *Node, const CFG *Graph) {
6618 std::string OutStr;
6619 llvm::raw_string_ostream Out(OutStr);
6620 print_block(OS&: Out,cfg: Graph, B: *Node, Helper&: *GraphHelper, print_edges: false, ShowColors: false);
6621
6622 if (OutStr[0] == '\n') OutStr.erase(position: OutStr.begin());
6623
6624 // Process string output to make it nicer...
6625 for (unsigned i = 0; i != OutStr.length(); ++i)
6626 if (OutStr[i] == '\n') { // Left justify
6627 OutStr[i] = '\\';
6628 OutStr.insert(p: OutStr.begin()+i+1, c: 'l');
6629 }
6630
6631 return OutStr;
6632 }
6633};
6634
6635} // namespace llvm
6636