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();
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 is a 'noreturn' point in the
1814/// CFG. It is *not* connected to the current (global) successor, and instead
1815/// directly tied to the exit block in order to be reachable.
1816CFGBlock *CFGBuilder::createNoReturnBlock() {
1817 CFGBlock *B = createBlock(add_successor: false);
1818 B->setHasNoReturnElement();
1819 addSuccessor(B, ReachableBlock: &cfg->getExit(), AltBlock: Succ);
1820 return B;
1821}
1822
1823/// addInitializer - Add C++ base or member initializer element to CFG.
1824CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
1825 if (!BuildOpts.AddInitializers)
1826 return Block;
1827
1828 bool HasTemporaries = false;
1829
1830 // Destructors of temporaries in initialization expression should be called
1831 // after initialization finishes.
1832 Expr *Init = I->getInit();
1833 if (Init) {
1834 Expr *ActualInit = Init;
1835 if (BuildOpts.AddCXXDefaultInitExprInCtors)
1836 if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Val: Init))
1837 ActualInit = DIE->getExpr();
1838
1839 HasTemporaries = isa<ExprWithCleanups>(Val: ActualInit);
1840
1841 if (HasTemporaries &&
1842 (BuildOpts.AddTemporaryDtors || BuildOpts.AddLifetime)) {
1843 // Generate destructors for temporaries in initialization expression.
1844 TempDtorContext Context;
1845 auto *FullExprWithCleanups = cast<ExprWithCleanups>(Val: ActualInit);
1846 VisitForTemporaries(E: FullExprWithCleanups->getSubExpr(),
1847 /*ExternallyDestructed=*/false, Context);
1848
1849 addFullExprCleanupMarker(Context, CleanupExpr: FullExprWithCleanups);
1850 }
1851 }
1852
1853 autoCreateBlock();
1854 appendInitializer(B: Block, I);
1855
1856 if (Init) {
1857 // If the initializer is an ArrayInitLoopExpr, we want to extract the
1858 // initializer, that's used for each element.
1859 auto *AILEInit = extractElementInitializerFromNestedAILE(
1860 AILE: dyn_cast<ArrayInitLoopExpr>(Val: Init));
1861
1862 findConstructionContexts(
1863 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: I),
1864 Child: AILEInit ? AILEInit : Init);
1865
1866 if (BuildOpts.AddCXXDefaultInitExprInCtors) {
1867 if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Val: Init)) {
1868 // In general, appending the expression wrapped by a CXXDefaultInitExpr
1869 // may cause the same Expr to appear more than once in the CFG. Doing it
1870 // here is safe because there's only one initializer per field.
1871 autoCreateBlock();
1872 appendStmt(B: Block, S: Default);
1873 if (Stmt *Child = Default->getExpr()) {
1874 if (HasTemporaries)
1875 Child = cast<ExprWithCleanups>(Val: Child)->getSubExpr();
1876 if (CFGBlock *R = Visit(S: Child))
1877 Block = R;
1878 }
1879 return Block;
1880 }
1881 }
1882
1883 if (HasTemporaries) {
1884 // For expression with temporaries go directly to subexpression to omit
1885 // generating destructors for the second time.
1886 return Visit(S: cast<ExprWithCleanups>(Val: Init)->getSubExpr());
1887 }
1888 return Visit(S: Init);
1889 }
1890
1891 return Block;
1892}
1893
1894/// Retrieve the type of the temporary object whose lifetime was
1895/// extended by a local reference with the given initializer.
1896static QualType getReferenceInitTemporaryType(const Expr *Init,
1897 bool *FoundMTE = nullptr) {
1898 while (true) {
1899 // Skip parentheses.
1900 Init = Init->IgnoreParens();
1901
1902 // Skip through cleanups.
1903 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Val: Init)) {
1904 Init = EWC->getSubExpr();
1905 continue;
1906 }
1907
1908 // Skip through the temporary-materialization expression.
1909 if (const MaterializeTemporaryExpr *MTE
1910 = dyn_cast<MaterializeTemporaryExpr>(Val: Init)) {
1911 Init = MTE->getSubExpr();
1912 if (FoundMTE)
1913 *FoundMTE = true;
1914 continue;
1915 }
1916
1917 // Skip sub-object accesses into rvalues.
1918 const Expr *SkippedInit = Init->skipRValueSubobjectAdjustments();
1919 if (SkippedInit != Init) {
1920 Init = SkippedInit;
1921 continue;
1922 }
1923
1924 break;
1925 }
1926
1927 return Init->getType();
1928}
1929
1930// TODO: Support adding LoopExit element to the CFG in case where the loop is
1931// ended by ReturnStmt, GotoStmt or ThrowExpr.
1932void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
1933 if(!BuildOpts.AddLoopExit)
1934 return;
1935 autoCreateBlock();
1936 appendLoopExit(B: Block, LoopStmt);
1937}
1938
1939/// Adds the CFG elements for leaving the scope of automatic objects in
1940/// range [B, E). This include following:
1941/// * AutomaticObjectDtor for variables with non-trivial destructor
1942/// * LifetimeEnds for all variables
1943/// * ScopeEnd for each scope left
1944void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
1945 LocalScope::const_iterator E,
1946 Stmt *S) {
1947 if (!BuildOpts.AddScopes && !BuildOpts.AddImplicitDtors &&
1948 !BuildOpts.AddLifetime)
1949 return;
1950
1951 if (B == E)
1952 return;
1953
1954 // Not leaving the scope, only need to handle destruction and lifetime
1955 if (B.inSameLocalScope(rhs: E)) {
1956 addAutomaticObjDestruction(B, E, S);
1957 return;
1958 }
1959
1960 // Extract information about all local scopes that are left
1961 SmallVector<LocalScope::const_iterator, 10> LocalScopeEndMarkers;
1962 LocalScopeEndMarkers.push_back(Elt: B);
1963 for (LocalScope::const_iterator I = B; I != E; ++I) {
1964 if (!I.inSameLocalScope(rhs: LocalScopeEndMarkers.back()))
1965 LocalScopeEndMarkers.push_back(Elt: I);
1966 }
1967 LocalScopeEndMarkers.push_back(Elt: E);
1968
1969 // We need to leave the scope in reverse order, so we reverse the end
1970 // markers
1971 std::reverse(first: LocalScopeEndMarkers.begin(), last: LocalScopeEndMarkers.end());
1972 auto Pairwise =
1973 llvm::zip(t&: LocalScopeEndMarkers, u: llvm::drop_begin(RangeOrContainer&: LocalScopeEndMarkers));
1974 for (auto [E, B] : Pairwise) {
1975 if (!B.inSameLocalScope(rhs: E))
1976 addScopeExitHandling(B, E, S);
1977 addAutomaticObjDestruction(B, E, S);
1978 }
1979}
1980
1981/// Add CFG elements corresponding to call destructor and end of lifetime
1982/// of all automatic variables with non-trivial destructor in range [B, E).
1983/// This include AutomaticObjectDtor and LifetimeEnds elements.
1984void CFGBuilder::addAutomaticObjDestruction(LocalScope::const_iterator B,
1985 LocalScope::const_iterator E,
1986 Stmt *S) {
1987 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime)
1988 return;
1989
1990 if (B == E)
1991 return;
1992
1993 SmallVector<VarDecl *, 10> DeclsNeedDestruction;
1994 DeclsNeedDestruction.reserve(N: B.distance(L: E));
1995
1996 for (VarDecl* D : llvm::make_range(x: B, y: E))
1997 if (needsAutomaticDestruction(VD: D))
1998 DeclsNeedDestruction.push_back(Elt: D);
1999
2000 for (VarDecl *VD : llvm::reverse(C&: DeclsNeedDestruction)) {
2001 if (BuildOpts.AddImplicitDtors) {
2002 // If this destructor is marked as a no-return destructor, we need to
2003 // create a new block for the destructor which does not have as a
2004 // successor anything built thus far: control won't flow out of this
2005 // block.
2006 QualType Ty = VD->getType();
2007 if (Ty->isReferenceType())
2008 Ty = getReferenceInitTemporaryType(Init: VD->getInit());
2009 Ty = Context->getBaseElementType(QT: Ty);
2010
2011 const CXXRecordDecl *CRD = Ty->getAsCXXRecordDecl();
2012 if (CRD && CRD->isAnyDestructorNoReturn())
2013 Block = createNoReturnBlock();
2014 }
2015
2016 autoCreateBlock();
2017
2018 // Add LifetimeEnd after automatic obj with non-trivial destructors,
2019 // as they end their lifetime when the destructor returns. For trivial
2020 // objects, we end lifetime with scope end.
2021 if (BuildOpts.AddLifetime)
2022 appendLifetimeEnds(B: Block, VD, S);
2023 if (BuildOpts.AddImplicitDtors && !hasTrivialDestructor(VD))
2024 appendAutomaticObjDtor(B: Block, VD, S);
2025 if (VD->hasAttr<CleanupAttr>())
2026 appendCleanupFunction(B: Block, VD);
2027 }
2028}
2029
2030/// Add CFG elements corresponding to leaving a scope.
2031/// Assumes that range [B, E) corresponds to single scope.
2032/// This add following elements:
2033/// * LifetimeEnds for all variables with non-trivial destructor
2034/// * ScopeEnd for each scope left
2035void CFGBuilder::addScopeExitHandling(LocalScope::const_iterator B,
2036 LocalScope::const_iterator E, Stmt *S) {
2037 assert(!B.inSameLocalScope(E));
2038 if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes)
2039 return;
2040
2041 if (BuildOpts.AddScopes) {
2042 autoCreateBlock();
2043 appendScopeEnd(B: Block, VD: B.getFirstVarInScope(), S);
2044 }
2045
2046 if (!BuildOpts.AddLifetime)
2047 return;
2048
2049 // We need to perform the scope leaving in reverse order
2050 SmallVector<VarDecl *, 10> DeclsTrivial;
2051 DeclsTrivial.reserve(N: B.distance(L: E));
2052
2053 // Objects with trivial destructor ends their lifetime when their storage
2054 // is destroyed, for automatic variables, this happens when the end of the
2055 // scope is added.
2056 for (VarDecl* D : llvm::make_range(x: B, y: E))
2057 if (!needsAutomaticDestruction(VD: D))
2058 DeclsTrivial.push_back(Elt: D);
2059
2060 if (DeclsTrivial.empty())
2061 return;
2062
2063 autoCreateBlock();
2064 for (VarDecl *VD : llvm::reverse(C&: DeclsTrivial))
2065 appendLifetimeEnds(B: Block, VD, S);
2066}
2067
2068/// addScopeChangesHandling - appends information about destruction, lifetime
2069/// and cfgScopeEnd for variables in the scope that was left by the jump, and
2070/// appends cfgScopeBegin for all scopes that where entered.
2071/// We insert the cfgScopeBegin at the end of the jump node, as depending on
2072/// the sourceBlock, each goto, may enter different amount of scopes.
2073void CFGBuilder::addScopeChangesHandling(LocalScope::const_iterator SrcPos,
2074 LocalScope::const_iterator DstPos,
2075 Stmt *S) {
2076 assert(Block && "Source block should be always crated");
2077 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2078 !BuildOpts.AddScopes) {
2079 return;
2080 }
2081
2082 if (SrcPos == DstPos)
2083 return;
2084
2085 // Get common scope, the jump leaves all scopes [SrcPos, BasePos), and
2086 // enter all scopes between [DstPos, BasePos)
2087 LocalScope::const_iterator BasePos = SrcPos.shared_parent(L: DstPos);
2088
2089 // Append scope begins for scopes entered by goto
2090 if (BuildOpts.AddScopes && !DstPos.inSameLocalScope(rhs: BasePos)) {
2091 for (LocalScope::const_iterator I = DstPos; I != BasePos; ++I)
2092 if (I.pointsToFirstDeclaredVar())
2093 appendScopeBegin(B: Block, VD: *I, S);
2094 }
2095
2096 // Append scopeEnds, destructor and lifetime with the terminator for
2097 // block left by goto.
2098 addAutomaticObjHandling(B: SrcPos, E: BasePos, S);
2099}
2100
2101void CFGBuilder::addFullExprCleanupMarker(TempDtorContext &Context,
2102 const ExprWithCleanups *CleanupExpr) {
2103 CFGFullExprCleanup::MTEVecTy *ExpiringMTEs = nullptr;
2104 BumpVectorContext &BVC = cfg->getBumpVectorContext();
2105
2106 size_t NumCollected = Context.CollectedMTEs.size();
2107 if (NumCollected > 0) {
2108 autoCreateBlock();
2109 ExpiringMTEs = new (cfg->getAllocator())
2110 CFGFullExprCleanup::MTEVecTy(BVC, NumCollected);
2111 for (const MaterializeTemporaryExpr *MTE : Context.CollectedMTEs)
2112 ExpiringMTEs->push_back(Elt: MTE, C&: BVC);
2113 Block->appendFullExprCleanup(BV: ExpiringMTEs, CleanupExpr, C&: BVC);
2114 }
2115}
2116
2117/// createScopeChangesHandlingBlock - Creates a block with cfgElements
2118/// corresponding to changing the scope from the source scope of the GotoStmt,
2119/// to destination scope. Add destructor, lifetime and cfgScopeEnd
2120/// CFGElements to newly created CFGBlock, that will have the CFG terminator
2121/// transferred.
2122CFGBlock *CFGBuilder::createScopeChangesHandlingBlock(
2123 LocalScope::const_iterator SrcPos, CFGBlock *SrcBlk,
2124 LocalScope::const_iterator DstPos, CFGBlock *DstBlk) {
2125 if (SrcPos == DstPos)
2126 return DstBlk;
2127
2128 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2129 (!BuildOpts.AddScopes || SrcPos.inSameLocalScope(rhs: DstPos)))
2130 return DstBlk;
2131
2132 // We will update CFBBuilder when creating new block, restore the
2133 // previous state at exit.
2134 SaveAndRestore save_Block(Block), save_Succ(Succ);
2135
2136 // Create a new block, and transfer terminator
2137 Block = createBlock(add_successor: false);
2138 Block->setTerminator(SrcBlk->getTerminator());
2139 SrcBlk->setTerminator(CFGTerminator());
2140 addSuccessor(B: Block, S: DstBlk);
2141
2142 // Fill the created Block with the required elements.
2143 addScopeChangesHandling(SrcPos, DstPos, S: Block->getTerminatorStmt());
2144
2145 assert(Block && "There should be at least one scope changing Block");
2146 return Block;
2147}
2148
2149/// addImplicitDtorsForDestructor - Add implicit destructors generated for
2150/// base and member objects in destructor.
2151void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
2152 assert(BuildOpts.AddImplicitDtors &&
2153 "Can be called only when dtors should be added");
2154 const CXXRecordDecl *RD = DD->getParent();
2155
2156 // At the end destroy virtual base objects.
2157 for (const auto &VI : RD->vbases()) {
2158 // TODO: Add a VirtualBaseBranch to see if the most derived class
2159 // (which is different from the current class) is responsible for
2160 // destroying them.
2161 const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl();
2162 if (CD && !CD->hasTrivialDestructor()) {
2163 autoCreateBlock();
2164 appendBaseDtor(B: Block, BS: &VI);
2165 }
2166 }
2167
2168 // Before virtual bases destroy direct base objects.
2169 for (const auto &BI : RD->bases()) {
2170 if (!BI.isVirtual()) {
2171 const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl();
2172 if (CD && !CD->hasTrivialDestructor()) {
2173 autoCreateBlock();
2174 appendBaseDtor(B: Block, BS: &BI);
2175 }
2176 }
2177 }
2178
2179 // First destroy member objects.
2180 if (RD->isUnion())
2181 return;
2182 for (auto *FI : RD->fields()) {
2183 // Check for constant size array. Set type to array element type.
2184 QualType QT = FI->getType();
2185 // It may be a multidimensional array.
2186 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(T: QT)) {
2187 if (AT->isZeroSize())
2188 break;
2189 QT = AT->getElementType();
2190 }
2191
2192 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
2193 if (!CD->hasTrivialDestructor()) {
2194 autoCreateBlock();
2195 appendMemberDtor(B: Block, FD: FI);
2196 }
2197 }
2198}
2199
2200/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
2201/// way return valid LocalScope object.
2202LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
2203 if (Scope)
2204 return Scope;
2205 llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
2206 return new (alloc) LocalScope(BumpVectorContext(alloc), ScopePos);
2207}
2208
2209/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
2210/// that should create implicit scope (e.g. if/else substatements).
2211void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
2212 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2213 !BuildOpts.AddScopes)
2214 return;
2215
2216 LocalScope *Scope = nullptr;
2217
2218 // For compound statement we will be creating explicit scope.
2219 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(Val: S)) {
2220 for (auto *BI : CS->body()) {
2221 Stmt *SI = BI->stripLabelLikeStatements();
2222 if (DeclStmt *DS = dyn_cast<DeclStmt>(Val: SI))
2223 Scope = addLocalScopeForDeclStmt(DS, Scope);
2224 }
2225 return;
2226 }
2227
2228 // For any other statement scope will be implicit and as such will be
2229 // interesting only for DeclStmt.
2230 if (DeclStmt *DS = dyn_cast<DeclStmt>(Val: S->stripLabelLikeStatements()))
2231 addLocalScopeForDeclStmt(DS);
2232}
2233
2234/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
2235/// reuse Scope if not NULL.
2236LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
2237 LocalScope* Scope) {
2238 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2239 !BuildOpts.AddScopes)
2240 return Scope;
2241
2242 for (auto *DI : DS->decls())
2243 if (VarDecl *VD = dyn_cast<VarDecl>(Val: DI))
2244 Scope = addLocalScopeForVarDecl(VD, Scope);
2245 return Scope;
2246}
2247
2248bool CFGBuilder::needsAutomaticDestruction(const VarDecl *VD) const {
2249 return !hasTrivialDestructor(VD) || VD->hasAttr<CleanupAttr>();
2250}
2251
2252bool CFGBuilder::hasTrivialDestructor(const VarDecl *VD) const {
2253 // Check for const references bound to temporary. Set type to pointee.
2254 QualType QT = VD->getType();
2255 if (QT->isReferenceType()) {
2256 // Attempt to determine whether this declaration lifetime-extends a
2257 // temporary.
2258 //
2259 // FIXME: This is incorrect. Non-reference declarations can lifetime-extend
2260 // temporaries, and a single declaration can extend multiple temporaries.
2261 // We should look at the storage duration on each nested
2262 // MaterializeTemporaryExpr instead.
2263
2264 const Expr *Init = VD->getInit();
2265 if (!Init) {
2266 // Probably an exception catch-by-reference variable.
2267 // FIXME: It doesn't really mean that the object has a trivial destructor.
2268 // Also are there other cases?
2269 return true;
2270 }
2271
2272 // Lifetime-extending a temporary?
2273 bool FoundMTE = false;
2274 QT = getReferenceInitTemporaryType(Init, FoundMTE: &FoundMTE);
2275 if (!FoundMTE)
2276 return true;
2277 }
2278
2279 // Check for constant size array. Set type to array element type.
2280 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(T: QT)) {
2281 if (AT->isZeroSize())
2282 return true;
2283 QT = AT->getElementType();
2284 }
2285
2286 // Check if type is a C++ class with non-trivial destructor.
2287 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
2288 return !CD->hasDefinition() || CD->hasTrivialDestructor();
2289 return true;
2290}
2291
2292/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
2293/// create add scope for automatic objects and temporary objects bound to
2294/// const reference. Will reuse Scope if not NULL.
2295LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
2296 LocalScope* Scope) {
2297 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2298 !BuildOpts.AddScopes)
2299 return Scope;
2300
2301 // Check if variable is local.
2302 if (!VD->hasLocalStorage())
2303 return Scope;
2304
2305 // Reference parameters are aliases to objects that live elsewhere, so they
2306 // don't require automatic destruction or lifetime tracking.
2307 if (isa<ParmVarDecl>(Val: VD) && VD->getType()->isReferenceType())
2308 return Scope;
2309
2310 if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes &&
2311 !needsAutomaticDestruction(VD)) {
2312 assert(BuildOpts.AddImplicitDtors);
2313 return Scope;
2314 }
2315
2316 // Add the variable to scope
2317 Scope = createOrReuseLocalScope(Scope);
2318 Scope->addVar(VD);
2319 ScopePos = Scope->begin();
2320 return Scope;
2321}
2322
2323/// addLocalScopeAndDtors - For given statement add local scope for it and
2324/// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
2325void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
2326 LocalScope::const_iterator scopeBeginPos = ScopePos;
2327 addLocalScopeForStmt(S);
2328 addAutomaticObjHandling(B: ScopePos, E: scopeBeginPos, S);
2329}
2330
2331/// Visit - Walk the subtree of a statement and add extra
2332/// blocks for ternary operators, &&, and ||. We also process "," and
2333/// DeclStmts (which may contain nested control-flow).
2334CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc,
2335 bool ExternallyDestructed) {
2336 if (!S) {
2337 badCFG = true;
2338 return nullptr;
2339 }
2340
2341 if (Expr *E = dyn_cast<Expr>(Val: S))
2342 S = E->IgnoreParens();
2343
2344 if (Context->getLangOpts().OpenMP)
2345 if (auto *D = dyn_cast<OMPExecutableDirective>(Val: S))
2346 return VisitOMPExecutableDirective(D, asc);
2347
2348 switch (S->getStmtClass()) {
2349 default:
2350 return VisitStmt(S, asc);
2351
2352 case Stmt::ImplicitValueInitExprClass:
2353 if (BuildOpts.OmitImplicitValueInitializers)
2354 return Block;
2355 return VisitStmt(S, asc);
2356
2357 case Stmt::InitListExprClass:
2358 return VisitInitListExpr(ILE: cast<InitListExpr>(Val: S), asc);
2359
2360 case Stmt::AttributedStmtClass:
2361 return VisitAttributedStmt(A: cast<AttributedStmt>(Val: S), asc);
2362
2363 case Stmt::AddrLabelExprClass:
2364 return VisitAddrLabelExpr(A: cast<AddrLabelExpr>(Val: S), asc);
2365
2366 case Stmt::BinaryConditionalOperatorClass:
2367 return VisitConditionalOperator(C: cast<BinaryConditionalOperator>(Val: S), asc);
2368
2369 case Stmt::BinaryOperatorClass:
2370 return VisitBinaryOperator(B: cast<BinaryOperator>(Val: S), asc);
2371
2372 case Stmt::BlockExprClass:
2373 return VisitBlockExpr(E: cast<BlockExpr>(Val: S), asc);
2374
2375 case Stmt::BreakStmtClass:
2376 return VisitBreakStmt(B: cast<BreakStmt>(Val: S));
2377
2378 case Stmt::CallExprClass:
2379 case Stmt::CXXOperatorCallExprClass:
2380 case Stmt::CXXMemberCallExprClass:
2381 case Stmt::UserDefinedLiteralClass:
2382 return VisitCallExpr(C: cast<CallExpr>(Val: S), asc);
2383
2384 case Stmt::CaseStmtClass:
2385 return VisitCaseStmt(C: cast<CaseStmt>(Val: S));
2386
2387 case Stmt::ChooseExprClass:
2388 return VisitChooseExpr(C: cast<ChooseExpr>(Val: S), asc);
2389
2390 case Stmt::CompoundStmtClass:
2391 return VisitCompoundStmt(C: cast<CompoundStmt>(Val: S), ExternallyDestructed);
2392
2393 case Stmt::ConditionalOperatorClass:
2394 return VisitConditionalOperator(C: cast<ConditionalOperator>(Val: S), asc);
2395
2396 case Stmt::ContinueStmtClass:
2397 return VisitContinueStmt(C: cast<ContinueStmt>(Val: S));
2398
2399 case Stmt::CXXCatchStmtClass:
2400 return VisitCXXCatchStmt(S: cast<CXXCatchStmt>(Val: S));
2401
2402 case Stmt::ExprWithCleanupsClass:
2403 return VisitExprWithCleanups(E: cast<ExprWithCleanups>(Val: S),
2404 asc, ExternallyDestructed);
2405
2406 case Stmt::CXXDefaultArgExprClass:
2407 case Stmt::CXXDefaultInitExprClass:
2408 // FIXME: The expression inside a CXXDefaultArgExpr is owned by the
2409 // called function's declaration, not by the caller. If we simply add
2410 // this expression to the CFG, we could end up with the same Expr
2411 // appearing multiple times (PR13385).
2412 //
2413 // It's likewise possible for multiple CXXDefaultInitExprs for the same
2414 // expression to be used in the same function (through aggregate
2415 // initialization).
2416 return VisitStmt(S, asc);
2417
2418 case Stmt::CXXBindTemporaryExprClass:
2419 return VisitCXXBindTemporaryExpr(E: cast<CXXBindTemporaryExpr>(Val: S), asc);
2420
2421 case Stmt::CXXConstructExprClass:
2422 return VisitCXXConstructExpr(C: cast<CXXConstructExpr>(Val: S), asc);
2423
2424 case Stmt::CXXNewExprClass:
2425 return VisitCXXNewExpr(DE: cast<CXXNewExpr>(Val: S), asc);
2426
2427 case Stmt::CXXDeleteExprClass:
2428 return VisitCXXDeleteExpr(DE: cast<CXXDeleteExpr>(Val: S), asc);
2429
2430 case Stmt::CXXFunctionalCastExprClass:
2431 return VisitCXXFunctionalCastExpr(E: cast<CXXFunctionalCastExpr>(Val: S), asc);
2432
2433 case Stmt::CXXTemporaryObjectExprClass:
2434 return VisitCXXTemporaryObjectExpr(C: cast<CXXTemporaryObjectExpr>(Val: S), asc);
2435
2436 case Stmt::CXXThrowExprClass:
2437 return VisitCXXThrowExpr(T: cast<CXXThrowExpr>(Val: S));
2438
2439 case Stmt::CXXTryStmtClass:
2440 return VisitCXXTryStmt(S: cast<CXXTryStmt>(Val: S));
2441
2442 case Stmt::CXXTypeidExprClass:
2443 return VisitCXXTypeidExpr(S: cast<CXXTypeidExpr>(Val: S), asc);
2444
2445 case Stmt::CXXForRangeStmtClass:
2446 return VisitCXXForRangeStmt(S: cast<CXXForRangeStmt>(Val: S));
2447
2448 case Stmt::DeclStmtClass:
2449 return VisitDeclStmt(DS: cast<DeclStmt>(Val: S));
2450
2451 case Stmt::DefaultStmtClass:
2452 return VisitDefaultStmt(D: cast<DefaultStmt>(Val: S));
2453
2454 case Stmt::DoStmtClass:
2455 return VisitDoStmt(D: cast<DoStmt>(Val: S));
2456
2457 case Stmt::ForStmtClass:
2458 return VisitForStmt(F: cast<ForStmt>(Val: S));
2459
2460 case Stmt::GotoStmtClass:
2461 return VisitGotoStmt(G: cast<GotoStmt>(Val: S));
2462
2463 case Stmt::GCCAsmStmtClass:
2464 return VisitGCCAsmStmt(G: cast<GCCAsmStmt>(Val: S), asc);
2465
2466 case Stmt::IfStmtClass:
2467 return VisitIfStmt(I: cast<IfStmt>(Val: S));
2468
2469 case Stmt::ImplicitCastExprClass:
2470 return VisitImplicitCastExpr(E: cast<ImplicitCastExpr>(Val: S), asc);
2471
2472 case Stmt::ConstantExprClass:
2473 return VisitConstantExpr(E: cast<ConstantExpr>(Val: S), asc);
2474
2475 case Stmt::IndirectGotoStmtClass:
2476 return VisitIndirectGotoStmt(I: cast<IndirectGotoStmt>(Val: S));
2477
2478 case Stmt::LabelStmtClass:
2479 return VisitLabelStmt(L: cast<LabelStmt>(Val: S));
2480
2481 case Stmt::LambdaExprClass:
2482 return VisitLambdaExpr(E: cast<LambdaExpr>(Val: S), asc);
2483
2484 case Stmt::MaterializeTemporaryExprClass:
2485 return VisitMaterializeTemporaryExpr(MTE: cast<MaterializeTemporaryExpr>(Val: S),
2486 asc);
2487
2488 case Stmt::MemberExprClass:
2489 return VisitMemberExpr(M: cast<MemberExpr>(Val: S), asc);
2490
2491 case Stmt::NullStmtClass:
2492 return Block;
2493
2494 case Stmt::ObjCAtCatchStmtClass:
2495 return VisitObjCAtCatchStmt(S: cast<ObjCAtCatchStmt>(Val: S));
2496
2497 case Stmt::ObjCAutoreleasePoolStmtClass:
2498 return VisitObjCAutoreleasePoolStmt(S: cast<ObjCAutoreleasePoolStmt>(Val: S));
2499
2500 case Stmt::ObjCAtSynchronizedStmtClass:
2501 return VisitObjCAtSynchronizedStmt(S: cast<ObjCAtSynchronizedStmt>(Val: S));
2502
2503 case Stmt::ObjCAtThrowStmtClass:
2504 return VisitObjCAtThrowStmt(S: cast<ObjCAtThrowStmt>(Val: S));
2505
2506 case Stmt::ObjCAtTryStmtClass:
2507 return VisitObjCAtTryStmt(S: cast<ObjCAtTryStmt>(Val: S));
2508
2509 case Stmt::ObjCForCollectionStmtClass:
2510 return VisitObjCForCollectionStmt(S: cast<ObjCForCollectionStmt>(Val: S));
2511
2512 case Stmt::ObjCMessageExprClass:
2513 return VisitObjCMessageExpr(E: cast<ObjCMessageExpr>(Val: S), asc);
2514
2515 case Stmt::OpaqueValueExprClass:
2516 return Block;
2517
2518 case Stmt::PseudoObjectExprClass:
2519 return VisitPseudoObjectExpr(E: cast<PseudoObjectExpr>(Val: S));
2520
2521 case Stmt::ReturnStmtClass:
2522 case Stmt::CoreturnStmtClass:
2523 return VisitReturnStmt(S);
2524
2525 case Stmt::CoyieldExprClass:
2526 case Stmt::CoawaitExprClass:
2527 return VisitCoroutineSuspendExpr(S: cast<CoroutineSuspendExpr>(Val: S), asc);
2528
2529 case Stmt::SEHExceptStmtClass:
2530 return VisitSEHExceptStmt(S: cast<SEHExceptStmt>(Val: S));
2531
2532 case Stmt::SEHFinallyStmtClass:
2533 return VisitSEHFinallyStmt(S: cast<SEHFinallyStmt>(Val: S));
2534
2535 case Stmt::SEHLeaveStmtClass:
2536 return VisitSEHLeaveStmt(S: cast<SEHLeaveStmt>(Val: S));
2537
2538 case Stmt::SEHTryStmtClass:
2539 return VisitSEHTryStmt(S: cast<SEHTryStmt>(Val: S));
2540
2541 case Stmt::UnaryExprOrTypeTraitExprClass:
2542 return VisitUnaryExprOrTypeTraitExpr(E: cast<UnaryExprOrTypeTraitExpr>(Val: S),
2543 asc);
2544
2545 case Stmt::StmtExprClass:
2546 return VisitStmtExpr(S: cast<StmtExpr>(Val: S), asc);
2547
2548 case Stmt::SwitchStmtClass:
2549 return VisitSwitchStmt(S: cast<SwitchStmt>(Val: S));
2550
2551 case Stmt::UnaryOperatorClass:
2552 return VisitUnaryOperator(U: cast<UnaryOperator>(Val: S), asc);
2553
2554 case Stmt::WhileStmtClass:
2555 return VisitWhileStmt(W: cast<WhileStmt>(Val: S));
2556
2557 case Stmt::ArrayInitLoopExprClass:
2558 return VisitArrayInitLoopExpr(A: cast<ArrayInitLoopExpr>(Val: S), asc);
2559 }
2560}
2561
2562CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
2563 if (asc.alwaysAdd(builder&: *this, stmt: S)) {
2564 autoCreateBlock();
2565 appendStmt(B: Block, S);
2566 }
2567
2568 return VisitChildren(S);
2569}
2570
2571/// VisitChildren - Visit the children of a Stmt.
2572CFGBlock *CFGBuilder::VisitChildren(Stmt *S) {
2573 CFGBlock *B = Block;
2574
2575 // Visit the children in their reverse order so that they appear in
2576 // left-to-right (natural) order in the CFG.
2577 reverse_children RChildren(S, *Context);
2578 for (Stmt *Child : RChildren) {
2579 if (Child)
2580 if (CFGBlock *R = Visit(S: Child))
2581 B = R;
2582 }
2583 return B;
2584}
2585
2586CFGBlock *CFGBuilder::VisitCallExprChildren(CallExpr *C) {
2587 // For overloaded assignment operators, visit arguments in reverse order (LHS
2588 // then RHS) so that RHS is sequenced before LHS in the CFG, matching C++17
2589 // sequencing rules.
2590 if (auto *OCE = dyn_cast<CXXOperatorCallExpr>(Val: C);
2591 OCE && OCE->isAssignmentOp()) {
2592 Visit(S: OCE->getArg(Arg: 0));
2593 Visit(S: OCE->getArg(Arg: 1));
2594 return Visit(S: OCE->getCallee());
2595 }
2596 return VisitChildren(S: C);
2597}
2598
2599CFGBlock *CFGBuilder::VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc) {
2600 if (asc.alwaysAdd(builder&: *this, stmt: ILE)) {
2601 autoCreateBlock();
2602 appendStmt(B: Block, S: ILE);
2603 }
2604 CFGBlock *B = Block;
2605
2606 reverse_children RChildren(ILE, *Context);
2607 for (Stmt *Child : RChildren) {
2608 if (!Child)
2609 continue;
2610 if (CFGBlock *R = Visit(S: Child))
2611 B = R;
2612 if (BuildOpts.AddCXXDefaultInitExprInAggregates) {
2613 if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Val: Child))
2614 if (Stmt *Child = DIE->getExpr())
2615 if (CFGBlock *R = Visit(S: Child))
2616 B = R;
2617 }
2618 }
2619 return B;
2620}
2621
2622CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
2623 AddStmtChoice asc) {
2624 AddressTakenLabels.insert(X: A->getLabel());
2625
2626 if (asc.alwaysAdd(builder&: *this, stmt: A)) {
2627 autoCreateBlock();
2628 appendStmt(B: Block, S: A);
2629 }
2630
2631 return Block;
2632}
2633
2634static bool isFallthroughStatement(const AttributedStmt *A) {
2635 bool isFallthrough = hasSpecificAttr<FallThroughAttr>(container: A->getAttrs());
2636 assert((!isFallthrough || isa<NullStmt>(A->getSubStmt())) &&
2637 "expected fallthrough not to have children");
2638 return isFallthrough;
2639}
2640
2641static bool isCXXAssumeAttr(const AttributedStmt *A) {
2642 bool hasAssumeAttr = hasSpecificAttr<CXXAssumeAttr>(container: A->getAttrs());
2643
2644 assert((!hasAssumeAttr || isa<NullStmt>(A->getSubStmt())) &&
2645 "expected [[assume]] not to have children");
2646 return hasAssumeAttr;
2647}
2648
2649CFGBlock *CFGBuilder::VisitAttributedStmt(AttributedStmt *A,
2650 AddStmtChoice asc) {
2651 // AttributedStmts for [[likely]] can have arbitrary statements as children,
2652 // and the current visitation order here would add the AttributedStmts
2653 // for [[likely]] after the child nodes, which is undesirable: For example,
2654 // if the child contains an unconditional return, the [[likely]] would be
2655 // considered unreachable.
2656 // So only add the AttributedStmt for FallThrough, which has CFG effects and
2657 // also no children, and omit the others. None of the other current StmtAttrs
2658 // have semantic meaning for the CFG.
2659 bool isInterestingAttribute = isFallthroughStatement(A) || isCXXAssumeAttr(A);
2660 if (isInterestingAttribute && asc.alwaysAdd(builder&: *this, stmt: A)) {
2661 autoCreateBlock();
2662 appendStmt(B: Block, S: A);
2663 }
2664
2665 return VisitChildren(S: A);
2666}
2667
2668CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc) {
2669 if (asc.alwaysAdd(builder&: *this, stmt: U)) {
2670 autoCreateBlock();
2671 appendStmt(B: Block, S: U);
2672 }
2673
2674 if (U->getOpcode() == UO_LNot)
2675 tryEvaluateBool(S: U->getSubExpr()->IgnoreParens());
2676
2677 return Visit(S: U->getSubExpr(), asc: AddStmtChoice());
2678}
2679
2680CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) {
2681 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2682 appendStmt(B: ConfluenceBlock, S: B);
2683
2684 if (badCFG)
2685 return nullptr;
2686
2687 return VisitLogicalOperator(B, Term: nullptr, TrueBlock: ConfluenceBlock,
2688 FalseBlock: ConfluenceBlock).first;
2689}
2690
2691std::pair<CFGBlock*, CFGBlock*>
2692CFGBuilder::VisitLogicalOperator(BinaryOperator *B,
2693 Stmt *Term,
2694 CFGBlock *TrueBlock,
2695 CFGBlock *FalseBlock) {
2696 // Introspect the RHS. If it is a nested logical operation, we recursively
2697 // build the CFG using this function. Otherwise, resort to default
2698 // CFG construction behavior.
2699 Expr *RHS = B->getRHS()->IgnoreParens();
2700 CFGBlock *RHSBlock, *ExitBlock;
2701
2702 do {
2703 if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(Val: RHS))
2704 if (B_RHS->isLogicalOp()) {
2705 std::tie(args&: RHSBlock, args&: ExitBlock) =
2706 VisitLogicalOperator(B: B_RHS, Term, TrueBlock, FalseBlock);
2707 break;
2708 }
2709
2710 // The RHS is not a nested logical operation. Don't push the terminator
2711 // down further, but instead visit RHS and construct the respective
2712 // pieces of the CFG, and link up the RHSBlock with the terminator
2713 // we have been provided.
2714 ExitBlock = RHSBlock = createBlock(add_successor: false);
2715
2716 // Even though KnownVal is only used in the else branch of the next
2717 // conditional, tryEvaluateBool performs additional checking on the
2718 // Expr, so it should be called unconditionally.
2719 TryResult KnownVal = tryEvaluateBool(S: RHS);
2720 if (!KnownVal.isKnown())
2721 KnownVal = tryEvaluateBool(S: B);
2722
2723 if (!Term) {
2724 assert(TrueBlock == FalseBlock);
2725 addSuccessor(B: RHSBlock, S: TrueBlock);
2726 }
2727 else {
2728 RHSBlock->setTerminator(Term);
2729 addSuccessor(B: RHSBlock, S: TrueBlock, IsReachable: !KnownVal.isFalse());
2730 addSuccessor(B: RHSBlock, S: FalseBlock, IsReachable: !KnownVal.isTrue());
2731 }
2732
2733 Block = RHSBlock;
2734 RHSBlock = addStmt(S: RHS);
2735 }
2736 while (false);
2737
2738 if (badCFG)
2739 return std::make_pair(x: nullptr, y: nullptr);
2740
2741 // Generate the blocks for evaluating the LHS.
2742 Expr *LHS = B->getLHS()->IgnoreParens();
2743
2744 if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(Val: LHS))
2745 if (B_LHS->isLogicalOp()) {
2746 if (B->getOpcode() == BO_LOr)
2747 FalseBlock = RHSBlock;
2748 else
2749 TrueBlock = RHSBlock;
2750
2751 // For the LHS, treat 'B' as the terminator that we want to sink
2752 // into the nested branch. The RHS always gets the top-most
2753 // terminator.
2754 return VisitLogicalOperator(B: B_LHS, Term: B, TrueBlock, FalseBlock);
2755 }
2756
2757 // Create the block evaluating the LHS.
2758 // This contains the '&&' or '||' as the terminator.
2759 CFGBlock *LHSBlock = createBlock(add_successor: false);
2760 LHSBlock->setTerminator(B);
2761
2762 Block = LHSBlock;
2763 CFGBlock *EntryLHSBlock = addStmt(S: LHS);
2764
2765 if (badCFG)
2766 return std::make_pair(x: nullptr, y: nullptr);
2767
2768 // See if this is a known constant.
2769 TryResult KnownVal = tryEvaluateBool(S: LHS);
2770
2771 // Now link the LHSBlock with RHSBlock.
2772 if (B->getOpcode() == BO_LOr) {
2773 addSuccessor(B: LHSBlock, S: TrueBlock, IsReachable: !KnownVal.isFalse());
2774 addSuccessor(B: LHSBlock, S: RHSBlock, IsReachable: !KnownVal.isTrue());
2775 } else {
2776 assert(B->getOpcode() == BO_LAnd);
2777 addSuccessor(B: LHSBlock, S: RHSBlock, IsReachable: !KnownVal.isFalse());
2778 addSuccessor(B: LHSBlock, S: FalseBlock, IsReachable: !KnownVal.isTrue());
2779 }
2780
2781 return std::make_pair(x&: EntryLHSBlock, y&: ExitBlock);
2782}
2783
2784CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
2785 AddStmtChoice asc) {
2786 // && or ||
2787 if (B->isLogicalOp())
2788 return VisitLogicalOperator(B);
2789
2790 if (B->getOpcode() == BO_Comma) { // ,
2791 autoCreateBlock();
2792 appendStmt(B: Block, S: B);
2793 addStmt(S: B->getRHS());
2794 return addStmt(S: B->getLHS());
2795 }
2796
2797 if (B->isAssignmentOp()) {
2798 if (asc.alwaysAdd(builder&: *this, stmt: B)) {
2799 autoCreateBlock();
2800 appendStmt(B: Block, S: B);
2801 }
2802 Visit(S: B->getLHS());
2803 return Visit(S: B->getRHS());
2804 }
2805
2806 if (asc.alwaysAdd(builder&: *this, stmt: B)) {
2807 autoCreateBlock();
2808 appendStmt(B: Block, S: B);
2809 }
2810
2811 if (B->isEqualityOp() || B->isRelationalOp())
2812 tryEvaluateBool(S: B);
2813
2814 CFGBlock *RBlock = Visit(S: B->getRHS());
2815 CFGBlock *LBlock = Visit(S: B->getLHS());
2816 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
2817 // containing a DoStmt, and the LHS doesn't create a new block, then we should
2818 // return RBlock. Otherwise we'll incorrectly return NULL.
2819 return (LBlock ? LBlock : RBlock);
2820}
2821
2822CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) {
2823 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
2824 autoCreateBlock();
2825 appendStmt(B: Block, S: E);
2826 }
2827 return Block;
2828}
2829
2830CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
2831 // "break" is a control-flow statement. Thus we stop processing the current
2832 // block.
2833 if (badCFG)
2834 return nullptr;
2835
2836 // Now create a new block that ends with the break statement.
2837 Block = createBlock(add_successor: false);
2838 Block->setTerminator(B);
2839
2840 // If there is no target for the break, then we are looking at an incomplete
2841 // AST. This means that the CFG cannot be constructed.
2842 if (BreakJumpTarget.block) {
2843 addAutomaticObjHandling(B: ScopePos, E: BreakJumpTarget.scopePosition, S: B);
2844 addSuccessor(B: Block, S: BreakJumpTarget.block);
2845 } else
2846 badCFG = true;
2847
2848 return Block;
2849}
2850
2851static bool CanThrow(Expr *E, ASTContext &Ctx) {
2852 QualType Ty = E->getType();
2853 if (Ty->isFunctionPointerType() || Ty->isBlockPointerType())
2854 Ty = Ty->getPointeeType();
2855
2856 const FunctionType *FT = Ty->getAs<FunctionType>();
2857 if (FT) {
2858 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(Val: FT))
2859 if (!isUnresolvedExceptionSpec(ESpecType: Proto->getExceptionSpecType()) &&
2860 Proto->isNothrow())
2861 return false;
2862 }
2863 return true;
2864}
2865
2866static bool isBuiltinAssumeWithSideEffects(const ASTContext &Ctx,
2867 const CallExpr *CE) {
2868 unsigned BuiltinID = CE->getBuiltinCallee();
2869 if (BuiltinID != Builtin::BI__assume &&
2870 BuiltinID != Builtin::BI__builtin_assume)
2871 return false;
2872
2873 return CE->getArg(Arg: 0)->HasSideEffects(Ctx);
2874}
2875
2876CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
2877 // Compute the callee type.
2878 QualType calleeType = C->getCallee()->getType();
2879 if (calleeType == Context->BoundMemberTy) {
2880 QualType boundType = Expr::findBoundMemberType(expr: C->getCallee());
2881
2882 // We should only get a null bound type if processing a dependent
2883 // CFG. Recover by assuming nothing.
2884 if (!boundType.isNull()) calleeType = boundType;
2885 }
2886
2887 // If this is a call to a no-return function, this stops the block here.
2888 bool NoReturn = getFunctionExtInfo(t: *calleeType).getNoReturn();
2889
2890 bool AddEHEdge = false;
2891
2892 // Languages without exceptions are assumed to not throw.
2893 if (Context->getLangOpts().Exceptions) {
2894 if (BuildOpts.AddEHEdges)
2895 AddEHEdge = true;
2896 }
2897
2898 // If this is a call to a builtin function, it might not actually evaluate
2899 // its arguments. Don't add them to the CFG if this is the case.
2900 bool OmitArguments = false;
2901
2902 if (FunctionDecl *FD = C->getDirectCallee()) {
2903 // TODO: Support construction contexts for variadic function arguments.
2904 // These are a bit problematic and not very useful because passing
2905 // C++ objects as C-style variadic arguments doesn't work in general
2906 // (see [expr.call]).
2907 if (!FD->isVariadic())
2908 findConstructionContextsForArguments(E: C);
2909
2910 if (FD->isNoReturn() || FD->isAnalyzerNoReturn() ||
2911 C->isBuiltinAssumeFalse(Ctx: *Context))
2912 NoReturn = true;
2913 if (FD->hasAttr<NoThrowAttr>())
2914 AddEHEdge = false;
2915 if (isBuiltinAssumeWithSideEffects(Ctx: FD->getASTContext(), CE: C) ||
2916 FD->getBuiltinID() == Builtin::BI__builtin_object_size ||
2917 FD->getBuiltinID() == Builtin::BI__builtin_dynamic_object_size)
2918 OmitArguments = true;
2919 }
2920
2921 if (!CanThrow(E: C->getCallee(), Ctx&: *Context))
2922 AddEHEdge = false;
2923
2924 if (OmitArguments) {
2925 assert(!NoReturn && "noreturn calls with unevaluated args not implemented");
2926 assert(!AddEHEdge && "EH calls with unevaluated args not implemented");
2927 autoCreateBlock();
2928 appendStmt(B: Block, S: C);
2929 return Visit(S: C->getCallee());
2930 }
2931
2932 if (!NoReturn && !AddEHEdge) {
2933 autoCreateBlock();
2934 appendCall(B: Block, CE: C);
2935
2936 return VisitCallExprChildren(C);
2937 }
2938
2939 if (Block) {
2940 Succ = Block;
2941 if (badCFG)
2942 return nullptr;
2943 }
2944
2945 if (NoReturn)
2946 Block = createNoReturnBlock();
2947 else
2948 Block = createBlock();
2949
2950 appendCall(B: Block, CE: C);
2951
2952 if (AddEHEdge) {
2953 // Add exceptional edges.
2954 if (TryTerminatedBlock)
2955 addSuccessor(B: Block, S: TryTerminatedBlock);
2956 else
2957 addSuccessor(B: Block, S: &cfg->getExit());
2958 }
2959
2960 return VisitCallExprChildren(C);
2961}
2962
2963CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
2964 AddStmtChoice asc) {
2965 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2966 appendStmt(B: ConfluenceBlock, S: C);
2967 if (badCFG)
2968 return nullptr;
2969
2970 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(alwaysAdd: true);
2971 Succ = ConfluenceBlock;
2972 Block = nullptr;
2973 CFGBlock *LHSBlock = Visit(S: C->getLHS(), asc: alwaysAdd);
2974 if (badCFG)
2975 return nullptr;
2976
2977 Succ = ConfluenceBlock;
2978 Block = nullptr;
2979 CFGBlock *RHSBlock = Visit(S: C->getRHS(), asc: alwaysAdd);
2980 if (badCFG)
2981 return nullptr;
2982
2983 Block = createBlock(add_successor: false);
2984 // See if this is a known constant.
2985 const TryResult& KnownVal = tryEvaluateBool(S: C->getCond());
2986 addSuccessor(B: Block, S: KnownVal.isFalse() ? nullptr : LHSBlock);
2987 addSuccessor(B: Block, S: KnownVal.isTrue() ? nullptr : RHSBlock);
2988 Block->setTerminator(C);
2989 return addStmt(S: C->getCond());
2990}
2991
2992CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C,
2993 bool ExternallyDestructed) {
2994 LocalScope::const_iterator scopeBeginPos = ScopePos;
2995 addLocalScopeForStmt(S: C);
2996
2997 if (!C->body_empty() && !isa<ReturnStmt>(Val: *C->body_rbegin())) {
2998 // If the body ends with a ReturnStmt, the dtors will be added in
2999 // VisitReturnStmt.
3000 addAutomaticObjHandling(B: ScopePos, E: scopeBeginPos, S: C);
3001 }
3002
3003 CFGBlock *LastBlock = Block;
3004
3005 for (Stmt *S : llvm::reverse(C: C->body())) {
3006 // If we hit a segment of code just containing ';' (NullStmts), we can
3007 // get a null block back. In such cases, just use the LastBlock
3008 CFGBlock *newBlock = Visit(S, asc: AddStmtChoice::AlwaysAdd,
3009 ExternallyDestructed);
3010
3011 if (newBlock)
3012 LastBlock = newBlock;
3013
3014 if (badCFG)
3015 return nullptr;
3016
3017 ExternallyDestructed = false;
3018 }
3019
3020 return LastBlock;
3021}
3022
3023CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
3024 AddStmtChoice asc) {
3025 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(Val: C);
3026 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr);
3027
3028 // Create the confluence block that will "merge" the results of the ternary
3029 // expression.
3030 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
3031 appendStmt(B: ConfluenceBlock, S: C);
3032 if (badCFG)
3033 return nullptr;
3034
3035 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(alwaysAdd: true);
3036
3037 // Create a block for the LHS expression if there is an LHS expression. A
3038 // GCC extension allows LHS to be NULL, causing the condition to be the
3039 // value that is returned instead.
3040 // e.g: x ?: y is shorthand for: x ? x : y;
3041 Succ = ConfluenceBlock;
3042 Block = nullptr;
3043 CFGBlock *LHSBlock = nullptr;
3044 const Expr *trueExpr = C->getTrueExpr();
3045 if (trueExpr != opaqueValue) {
3046 LHSBlock = Visit(S: C->getTrueExpr(), asc: alwaysAdd);
3047 if (badCFG)
3048 return nullptr;
3049 Block = nullptr;
3050 }
3051 else
3052 LHSBlock = ConfluenceBlock;
3053
3054 // Create the block for the RHS expression.
3055 Succ = ConfluenceBlock;
3056 CFGBlock *RHSBlock = Visit(S: C->getFalseExpr(), asc: alwaysAdd);
3057 if (badCFG)
3058 return nullptr;
3059
3060 // If the condition is a logical '&&' or '||', build a more accurate CFG.
3061 if (BinaryOperator *Cond =
3062 dyn_cast<BinaryOperator>(Val: C->getCond()->IgnoreParens()))
3063 if (Cond->isLogicalOp())
3064 return VisitLogicalOperator(B: Cond, Term: C, TrueBlock: LHSBlock, FalseBlock: RHSBlock).first;
3065
3066 // Create the block that will contain the condition.
3067 Block = createBlock(add_successor: false);
3068
3069 // See if this is a known constant.
3070 const TryResult& KnownVal = tryEvaluateBool(S: C->getCond());
3071 addSuccessor(B: Block, S: LHSBlock, IsReachable: !KnownVal.isFalse());
3072 addSuccessor(B: Block, S: RHSBlock, IsReachable: !KnownVal.isTrue());
3073 Block->setTerminator(C);
3074 Expr *condExpr = C->getCond();
3075
3076 if (opaqueValue) {
3077 // Run the condition expression if it's not trivially expressed in
3078 // terms of the opaque value (or if there is no opaque value).
3079 if (condExpr != opaqueValue)
3080 addStmt(S: condExpr);
3081
3082 // Before that, run the common subexpression if there was one.
3083 // At least one of this or the above will be run.
3084 return addStmt(S: BCO->getCommon());
3085 }
3086
3087 return addStmt(S: condExpr);
3088}
3089
3090CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
3091 // Check if the Decl is for an __label__. If so, elide it from the
3092 // CFG entirely.
3093 if (isa<LabelDecl>(Val: *DS->decl_begin()))
3094 return Block;
3095
3096 // This case also handles static_asserts.
3097 if (DS->isSingleDecl())
3098 return VisitDeclSubExpr(DS);
3099
3100 CFGBlock *B = nullptr;
3101
3102 // Build an individual DeclStmt for each decl.
3103 for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(),
3104 E = DS->decl_rend();
3105 I != E; ++I) {
3106
3107 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
3108 // automatically freed with the CFG.
3109 DeclGroupRef DG(*I);
3110 Decl *D = *I;
3111 DeclStmt *DSNew = new (Context) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
3112 cfg->addSyntheticDeclStmt(Synthetic: DSNew, Source: DS);
3113
3114 // Append the fake DeclStmt to block.
3115 B = VisitDeclSubExpr(DS: DSNew);
3116 }
3117
3118 return B;
3119}
3120
3121/// VisitDeclSubExpr - Utility method to add block-level expressions for
3122/// DeclStmts and initializers in them.
3123CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
3124 assert(DS->isSingleDecl() && "Can handle single declarations only.");
3125
3126 if (const auto *TND = dyn_cast<TypedefNameDecl>(Val: DS->getSingleDecl())) {
3127 // If we encounter a VLA, process its size expressions.
3128 const Type *T = TND->getUnderlyingType().getTypePtr();
3129 if (!T->isVariablyModifiedType())
3130 return Block;
3131
3132 autoCreateBlock();
3133 appendStmt(B: Block, S: DS);
3134
3135 CFGBlock *LastBlock = Block;
3136 for (const VariableArrayType *VA = FindVA(t: T); VA != nullptr;
3137 VA = FindVA(t: VA->getElementType().getTypePtr())) {
3138 if (CFGBlock *NewBlock = addStmt(S: VA->getSizeExpr()))
3139 LastBlock = NewBlock;
3140 }
3141 return LastBlock;
3142 }
3143
3144 VarDecl *VD = dyn_cast<VarDecl>(Val: DS->getSingleDecl());
3145
3146 if (!VD) {
3147 // Of everything that can be declared in a DeclStmt, only VarDecls and the
3148 // exceptions above impact runtime semantics.
3149 return Block;
3150 }
3151
3152 bool HasTemporaries = false;
3153
3154 // Guard static initializers under a branch.
3155 CFGBlock *blockAfterStaticInit = nullptr;
3156
3157 if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) {
3158 // For static variables, we need to create a branch to track
3159 // whether or not they are initialized.
3160 if (Block) {
3161 Succ = Block;
3162 Block = nullptr;
3163 if (badCFG)
3164 return nullptr;
3165 }
3166 blockAfterStaticInit = Succ;
3167 }
3168
3169 // Destructors of temporaries in initialization expression should be called
3170 // after initialization finishes.
3171 Expr *Init = VD->getInit();
3172 if (Init) {
3173 HasTemporaries = isa<ExprWithCleanups>(Val: Init);
3174
3175 if (HasTemporaries &&
3176 (BuildOpts.AddTemporaryDtors || BuildOpts.AddLifetime)) {
3177 // Generate destructors for temporaries in initialization expression.
3178 TempDtorContext Context;
3179 auto *FullExprWithCleanups = cast<ExprWithCleanups>(Val: Init);
3180 VisitForTemporaries(E: FullExprWithCleanups->getSubExpr(),
3181 /*ExternallyDestructed=*/true, Context);
3182
3183 addFullExprCleanupMarker(Context, CleanupExpr: FullExprWithCleanups);
3184 }
3185 }
3186
3187 // If we bind to a tuple-like type, we iterate over the HoldingVars, and
3188 // create a DeclStmt for each of them.
3189 if (const auto *DD = dyn_cast<DecompositionDecl>(Val: VD)) {
3190 for (auto *BD : llvm::reverse(C: DD->bindings())) {
3191 if (auto *VD = BD->getHoldingVar()) {
3192 DeclGroupRef DG(VD);
3193 DeclStmt *DSNew =
3194 new (Context) DeclStmt(DG, VD->getLocation(), GetEndLoc(D: VD));
3195 cfg->addSyntheticDeclStmt(Synthetic: DSNew, Source: DS);
3196 Block = VisitDeclSubExpr(DS: DSNew);
3197 }
3198 }
3199 }
3200
3201 autoCreateBlock();
3202 appendStmt(B: Block, S: DS);
3203
3204 // If the initializer is an ArrayInitLoopExpr, we want to extract the
3205 // initializer, that's used for each element.
3206 const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Val: Init);
3207
3208 findConstructionContexts(
3209 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: DS),
3210 Child: AILE ? AILE->getSubExpr() : Init);
3211
3212 // Keep track of the last non-null block, as 'Block' can be nulled out
3213 // if the initializer expression is something like a 'while' in a
3214 // statement-expression.
3215 CFGBlock *LastBlock = Block;
3216
3217 if (Init) {
3218 if (HasTemporaries) {
3219 // For expression with temporaries go directly to subexpression to omit
3220 // generating destructors for the second time.
3221 ExprWithCleanups *EC = cast<ExprWithCleanups>(Val: Init);
3222 if (CFGBlock *newBlock = Visit(S: EC->getSubExpr()))
3223 LastBlock = newBlock;
3224 }
3225 else {
3226 if (CFGBlock *newBlock = Visit(S: Init))
3227 LastBlock = newBlock;
3228 }
3229 }
3230
3231 // If the type of VD is a VLA, then we must process its size expressions.
3232 // FIXME: This does not find the VLA if it is embedded in other types,
3233 // like here: `int (*p_vla)[x];`
3234 for (const VariableArrayType* VA = FindVA(t: VD->getType().getTypePtr());
3235 VA != nullptr; VA = FindVA(t: VA->getElementType().getTypePtr())) {
3236 if (CFGBlock *newBlock = addStmt(S: VA->getSizeExpr()))
3237 LastBlock = newBlock;
3238 }
3239
3240 maybeAddScopeBeginForVarDecl(B: Block, VD, S: DS);
3241
3242 // Remove variable from local scope.
3243 if (ScopePos && VD == *ScopePos)
3244 ++ScopePos;
3245
3246 CFGBlock *B = LastBlock;
3247 if (blockAfterStaticInit) {
3248 Succ = B;
3249 Block = createBlock(add_successor: false);
3250 Block->setTerminator(DS);
3251 addSuccessor(B: Block, S: blockAfterStaticInit);
3252 addSuccessor(B: Block, S: B);
3253 B = Block;
3254 }
3255
3256 return B;
3257}
3258
3259CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
3260 // We may see an if statement in the middle of a basic block, or it may be the
3261 // first statement we are processing. In either case, we create a new basic
3262 // block. First, we create the blocks for the then...else statements, and
3263 // then we create the block containing the if statement. If we were in the
3264 // middle of a block, we stop processing that block. That block is then the
3265 // implicit successor for the "then" and "else" clauses.
3266
3267 // Save local scope position because in case of condition variable ScopePos
3268 // won't be restored when traversing AST.
3269 SaveAndRestore save_scope_pos(ScopePos);
3270
3271 // Create local scope for C++17 if init-stmt if one exists.
3272 if (Stmt *Init = I->getInit())
3273 addLocalScopeForStmt(S: Init);
3274
3275 // Create local scope for possible condition variable.
3276 // Store scope position. Add implicit destructor.
3277 if (VarDecl *VD = I->getConditionVariable())
3278 addLocalScopeForVarDecl(VD);
3279
3280 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S: I);
3281
3282 // The block we were processing is now finished. Make it the successor
3283 // block.
3284 if (Block) {
3285 Succ = Block;
3286 if (badCFG)
3287 return nullptr;
3288 }
3289
3290 // Process the false branch.
3291 CFGBlock *ElseBlock = Succ;
3292
3293 if (Stmt *Else = I->getElse()) {
3294 SaveAndRestore sv(Succ);
3295
3296 // NULL out Block so that the recursive call to Visit will
3297 // create a new basic block.
3298 Block = nullptr;
3299
3300 // If branch is not a compound statement create implicit scope
3301 // and add destructors.
3302 if (!isa<CompoundStmt>(Val: Else))
3303 addLocalScopeAndDtors(S: Else);
3304
3305 ElseBlock = addStmt(S: Else);
3306
3307 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
3308 ElseBlock = sv.get();
3309 else if (Block) {
3310 if (badCFG)
3311 return nullptr;
3312 }
3313 }
3314
3315 // Process the true branch.
3316 CFGBlock *ThenBlock;
3317 {
3318 Stmt *Then = I->getThen();
3319 assert(Then);
3320 SaveAndRestore sv(Succ);
3321 Block = nullptr;
3322
3323 // If branch is not a compound statement create implicit scope
3324 // and add destructors.
3325 if (!isa<CompoundStmt>(Val: Then))
3326 addLocalScopeAndDtors(S: Then);
3327
3328 ThenBlock = addStmt(S: Then);
3329
3330 if (!ThenBlock) {
3331 // We can reach here if the "then" body has all NullStmts.
3332 // Create an empty block so we can distinguish between true and false
3333 // branches in path-sensitive analyses.
3334 ThenBlock = createBlock(add_successor: false);
3335 addSuccessor(B: ThenBlock, S: sv.get());
3336 } else if (Block) {
3337 if (badCFG)
3338 return nullptr;
3339 }
3340 }
3341
3342 // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by
3343 // having these handle the actual control-flow jump. Note that
3344 // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)"
3345 // we resort to the old control-flow behavior. This special handling
3346 // removes infeasible paths from the control-flow graph by having the
3347 // control-flow transfer of '&&' or '||' go directly into the then/else
3348 // blocks directly.
3349 BinaryOperator *Cond =
3350 (I->isConsteval() || I->getConditionVariable())
3351 ? nullptr
3352 : dyn_cast<BinaryOperator>(Val: I->getCond()->IgnoreParens());
3353 CFGBlock *LastBlock;
3354 if (Cond && Cond->isLogicalOp())
3355 LastBlock = VisitLogicalOperator(B: Cond, Term: I, TrueBlock: ThenBlock, FalseBlock: ElseBlock).first;
3356 else {
3357 // Now create a new block containing the if statement.
3358 Block = createBlock(add_successor: false);
3359
3360 // Set the terminator of the new block to the If statement.
3361 Block->setTerminator(I);
3362
3363 // See if this is a known constant.
3364 TryResult KnownVal;
3365 if (!I->isConsteval())
3366 KnownVal = tryEvaluateBool(S: I->getCond());
3367
3368 // Add the successors. If we know that specific branches are
3369 // unreachable, inform addSuccessor() of that knowledge.
3370 addSuccessor(B: Block, S: ThenBlock, /* IsReachable = */ !KnownVal.isFalse());
3371 addSuccessor(B: Block, S: ElseBlock, /* IsReachable = */ !KnownVal.isTrue());
3372
3373 if (I->isConsteval())
3374 return Block;
3375
3376 // Add the condition as the last statement in the new block. This may
3377 // create new blocks as the condition may contain control-flow. Any newly
3378 // created blocks will be pointed to be "Block".
3379 LastBlock = addStmt(S: I->getCond());
3380
3381 // If the IfStmt contains a condition variable, add it and its
3382 // initializer to the CFG.
3383 if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) {
3384 autoCreateBlock();
3385 LastBlock = addStmt(S: const_cast<DeclStmt *>(DS));
3386 }
3387 }
3388
3389 // Finally, if the IfStmt contains a C++17 init-stmt, add it to the CFG.
3390 if (Stmt *Init = I->getInit()) {
3391 autoCreateBlock();
3392 LastBlock = addStmt(S: Init);
3393 }
3394
3395 return LastBlock;
3396}
3397
3398CFGBlock *CFGBuilder::VisitReturnStmt(Stmt *S) {
3399 // If we were in the middle of a block we stop processing that block.
3400 //
3401 // NOTE: If a "return" or "co_return" appears in the middle of a block, this
3402 // means that the code afterwards is DEAD (unreachable). We still keep
3403 // a basic block for that code; a simple "mark-and-sweep" from the entry
3404 // block will be able to report such dead blocks.
3405 assert(isa<ReturnStmt>(S) || isa<CoreturnStmt>(S));
3406
3407 // Create the new block.
3408 Block = createBlock(add_successor: false);
3409
3410 addAutomaticObjHandling(B: ScopePos, E: LocalScope::const_iterator(), S);
3411
3412 if (auto *R = dyn_cast<ReturnStmt>(Val: S))
3413 findConstructionContexts(
3414 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: R),
3415 Child: R->getRetValue());
3416
3417 // If the one of the destructors does not return, we already have the Exit
3418 // block as a successor.
3419 if (!Block->hasNoReturnElement())
3420 addSuccessor(B: Block, S: &cfg->getExit());
3421
3422 // Add the return statement to the block.
3423 appendStmt(B: Block, S);
3424
3425 // Visit children
3426 if (ReturnStmt *RS = dyn_cast<ReturnStmt>(Val: S)) {
3427 if (Expr *O = RS->getRetValue())
3428 return Visit(S: O, asc: AddStmtChoice::AlwaysAdd, /*ExternallyDestructed=*/true);
3429 return Block;
3430 }
3431
3432 CoreturnStmt *CRS = cast<CoreturnStmt>(Val: S);
3433 auto *B = Block;
3434 if (CFGBlock *R = Visit(S: CRS->getPromiseCall()))
3435 B = R;
3436
3437 if (Expr *RV = CRS->getOperand())
3438 if (RV->getType()->isVoidType() && !isa<InitListExpr>(Val: RV))
3439 // A non-initlist void expression.
3440 if (CFGBlock *R = Visit(S: RV))
3441 B = R;
3442
3443 return B;
3444}
3445
3446CFGBlock *CFGBuilder::VisitCoroutineSuspendExpr(CoroutineSuspendExpr *E,
3447 AddStmtChoice asc) {
3448 // We're modelling the pre-coro-xform CFG. Thus just evalate the various
3449 // active components of the co_await or co_yield. Note we do not model the
3450 // edge from the builtin_suspend to the exit node.
3451 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
3452 autoCreateBlock();
3453 appendStmt(B: Block, S: E);
3454 }
3455 CFGBlock *B = Block;
3456 if (auto *R = Visit(S: E->getResumeExpr()))
3457 B = R;
3458 if (auto *R = Visit(S: E->getSuspendExpr()))
3459 B = R;
3460 if (auto *R = Visit(S: E->getReadyExpr()))
3461 B = R;
3462 if (auto *R = Visit(S: E->getCommonExpr()))
3463 B = R;
3464 return B;
3465}
3466
3467CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) {
3468 // SEHExceptStmt are treated like labels, so they are the first statement in a
3469 // block.
3470
3471 // Save local scope position because in case of exception variable ScopePos
3472 // won't be restored when traversing AST.
3473 SaveAndRestore save_scope_pos(ScopePos);
3474
3475 addStmt(S: ES->getBlock());
3476 CFGBlock *SEHExceptBlock = Block;
3477 if (!SEHExceptBlock)
3478 SEHExceptBlock = createBlock();
3479
3480 appendStmt(B: SEHExceptBlock, S: ES);
3481
3482 // Also add the SEHExceptBlock as a label, like with regular labels.
3483 SEHExceptBlock->setLabel(ES);
3484
3485 // Bail out if the CFG is bad.
3486 if (badCFG)
3487 return nullptr;
3488
3489 // We set Block to NULL to allow lazy creation of a new block (if necessary).
3490 Block = nullptr;
3491
3492 return SEHExceptBlock;
3493}
3494
3495CFGBlock *CFGBuilder::VisitSEHFinallyStmt(SEHFinallyStmt *FS) {
3496 return VisitCompoundStmt(C: FS->getBlock(), /*ExternallyDestructed=*/false);
3497}
3498
3499CFGBlock *CFGBuilder::VisitSEHLeaveStmt(SEHLeaveStmt *LS) {
3500 // "__leave" is a control-flow statement. Thus we stop processing the current
3501 // block.
3502 if (badCFG)
3503 return nullptr;
3504
3505 // Now create a new block that ends with the __leave statement.
3506 Block = createBlock(add_successor: false);
3507 Block->setTerminator(LS);
3508
3509 // If there is no target for the __leave, then we are looking at an incomplete
3510 // AST. This means that the CFG cannot be constructed.
3511 if (SEHLeaveJumpTarget.block) {
3512 addAutomaticObjHandling(B: ScopePos, E: SEHLeaveJumpTarget.scopePosition, S: LS);
3513 addSuccessor(B: Block, S: SEHLeaveJumpTarget.block);
3514 } else
3515 badCFG = true;
3516
3517 return Block;
3518}
3519
3520CFGBlock *CFGBuilder::VisitSEHTryStmt(SEHTryStmt *Terminator) {
3521 // "__try"/"__except"/"__finally" is a control-flow statement. Thus we stop
3522 // processing the current block.
3523 CFGBlock *SEHTrySuccessor = nullptr;
3524
3525 if (Block) {
3526 if (badCFG)
3527 return nullptr;
3528 SEHTrySuccessor = Block;
3529 } else SEHTrySuccessor = Succ;
3530
3531 // FIXME: Implement __finally support.
3532 if (Terminator->getFinallyHandler())
3533 return NYS();
3534
3535 CFGBlock *PrevSEHTryTerminatedBlock = TryTerminatedBlock;
3536
3537 // Create a new block that will contain the __try statement.
3538 CFGBlock *NewTryTerminatedBlock = createBlock(add_successor: false);
3539
3540 // Add the terminator in the __try block.
3541 NewTryTerminatedBlock->setTerminator(Terminator);
3542
3543 if (SEHExceptStmt *Except = Terminator->getExceptHandler()) {
3544 // The code after the try is the implicit successor if there's an __except.
3545 Succ = SEHTrySuccessor;
3546 Block = nullptr;
3547 CFGBlock *ExceptBlock = VisitSEHExceptStmt(ES: Except);
3548 if (!ExceptBlock)
3549 return nullptr;
3550 // Add this block to the list of successors for the block with the try
3551 // statement.
3552 addSuccessor(B: NewTryTerminatedBlock, S: ExceptBlock);
3553 }
3554 if (PrevSEHTryTerminatedBlock)
3555 addSuccessor(B: NewTryTerminatedBlock, S: PrevSEHTryTerminatedBlock);
3556 else
3557 addSuccessor(B: NewTryTerminatedBlock, S: &cfg->getExit());
3558
3559 // The code after the try is the implicit successor.
3560 Succ = SEHTrySuccessor;
3561
3562 // Save the current "__try" context.
3563 SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);
3564 cfg->addTryDispatchBlock(block: TryTerminatedBlock);
3565
3566 // Save the current value for the __leave target.
3567 // All __leaves should go to the code following the __try
3568 // (FIXME: or if the __try has a __finally, to the __finally.)
3569 SaveAndRestore save_break(SEHLeaveJumpTarget);
3570 SEHLeaveJumpTarget = JumpTarget(SEHTrySuccessor, ScopePos);
3571
3572 assert(Terminator->getTryBlock() && "__try must contain a non-NULL body");
3573 Block = nullptr;
3574 return addStmt(S: Terminator->getTryBlock());
3575}
3576
3577CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
3578 // Get the block of the labeled statement. Add it to our map.
3579 addStmt(S: L->getSubStmt());
3580 CFGBlock *LabelBlock = Block;
3581
3582 if (!LabelBlock) // This can happen when the body is empty, i.e.
3583 LabelBlock = createBlock(); // scopes that only contains NullStmts.
3584
3585 assert(!LabelMap.contains(L->getDecl()) && "label already in map");
3586 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
3587
3588 // Labels partition blocks, so this is the end of the basic block we were
3589 // processing (L is the block's label). Because this is label (and we have
3590 // already processed the substatement) there is no extra control-flow to worry
3591 // about.
3592 LabelBlock->setLabel(L);
3593 if (badCFG)
3594 return nullptr;
3595
3596 // We set Block to NULL to allow lazy creation of a new block (if necessary).
3597 Block = nullptr;
3598
3599 // This block is now the implicit successor of other blocks.
3600 Succ = LabelBlock;
3601
3602 return LabelBlock;
3603}
3604
3605CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
3606 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3607 for (const BlockDecl::Capture &CI : E->getBlockDecl()->captures()) {
3608 if (Expr *CopyExpr = CI.getCopyExpr()) {
3609 CFGBlock *Tmp = Visit(S: CopyExpr);
3610 if (Tmp)
3611 LastBlock = Tmp;
3612 }
3613 }
3614 return LastBlock;
3615}
3616
3617CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
3618 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3619
3620 unsigned Idx = 0;
3621 for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),
3622 et = E->capture_init_end();
3623 it != et; ++it, ++Idx) {
3624 if (Expr *Init = *it) {
3625 // If the initializer is an ArrayInitLoopExpr, we want to extract the
3626 // initializer, that's used for each element.
3627 auto *AILEInit = extractElementInitializerFromNestedAILE(
3628 AILE: dyn_cast<ArrayInitLoopExpr>(Val: Init));
3629
3630 findConstructionContexts(Layer: ConstructionContextLayer::create(
3631 C&: cfg->getBumpVectorContext(), Item: {E, Idx}),
3632 Child: AILEInit ? AILEInit : Init);
3633
3634 CFGBlock *Tmp = Visit(S: Init);
3635 if (Tmp)
3636 LastBlock = Tmp;
3637 }
3638 }
3639 return LastBlock;
3640}
3641
3642CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
3643 // Goto is a control-flow statement. Thus we stop processing the current
3644 // block and create a new one.
3645
3646 Block = createBlock(add_successor: false);
3647 Block->setTerminator(G);
3648
3649 // If we already know the mapping to the label block add the successor now.
3650 LabelMapTy::iterator I = LabelMap.find(Val: G->getLabel());
3651
3652 if (I == LabelMap.end())
3653 // We will need to backpatch this block later.
3654 BackpatchBlocks.push_back(x: JumpSource(Block, ScopePos));
3655 else {
3656 JumpTarget JT = I->second;
3657 addSuccessor(B: Block, S: JT.block);
3658 addScopeChangesHandling(SrcPos: ScopePos, DstPos: JT.scopePosition, S: G);
3659 }
3660
3661 return Block;
3662}
3663
3664CFGBlock *CFGBuilder::VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc) {
3665 // Goto is a control-flow statement. Thus we stop processing the current
3666 // block and create a new one.
3667
3668 if (!G->isAsmGoto())
3669 return VisitStmt(S: G, asc);
3670
3671 if (Block) {
3672 Succ = Block;
3673 if (badCFG)
3674 return nullptr;
3675 }
3676 Block = createBlock();
3677 Block->setTerminator(G);
3678 // We will backpatch this block later for all the labels.
3679 BackpatchBlocks.push_back(x: JumpSource(Block, ScopePos));
3680 // Save "Succ" in BackpatchBlocks. In the backpatch processing, "Succ" is
3681 // used to avoid adding "Succ" again.
3682 BackpatchBlocks.push_back(x: JumpSource(Succ, ScopePos));
3683 return VisitChildren(S: G);
3684}
3685
3686CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
3687 CFGBlock *LoopSuccessor = nullptr;
3688
3689 // Save local scope position because in case of condition variable ScopePos
3690 // won't be restored when traversing AST.
3691 SaveAndRestore save_scope_pos(ScopePos);
3692
3693 // Create local scope for init statement and possible condition variable.
3694 // Add destructor for init statement and condition variable.
3695 // Store scope position for continue statement.
3696 if (Stmt *Init = F->getInit())
3697 addLocalScopeForStmt(S: Init);
3698 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3699
3700 if (VarDecl *VD = F->getConditionVariable())
3701 addLocalScopeForVarDecl(VD);
3702 LocalScope::const_iterator ContinueScopePos = ScopePos;
3703
3704 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S: F);
3705
3706 addLoopExit(LoopStmt: F);
3707
3708 // "for" is a control-flow statement. Thus we stop processing the current
3709 // block.
3710 if (Block) {
3711 if (badCFG)
3712 return nullptr;
3713 LoopSuccessor = Block;
3714 } else
3715 LoopSuccessor = Succ;
3716
3717 // Save the current value for the break targets.
3718 // All breaks should go to the code following the loop.
3719 SaveAndRestore save_break(BreakJumpTarget);
3720 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3721
3722 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3723
3724 // Now create the loop body.
3725 {
3726 assert(F->getBody());
3727
3728 // Save the current values for Block, Succ, continue and break targets.
3729 SaveAndRestore save_Block(Block), save_Succ(Succ);
3730 SaveAndRestore save_continue(ContinueJumpTarget);
3731
3732 // Create an empty block to represent the transition block for looping back
3733 // to the head of the loop. If we have increment code, it will
3734 // go in this block as well.
3735 Block = Succ = TransitionBlock = createBlock(add_successor: false);
3736 TransitionBlock->setLoopTarget(F);
3737
3738
3739 // Loop iteration (after increment) should end with destructor of Condition
3740 // variable (if any).
3741 addAutomaticObjHandling(B: ScopePos, E: LoopBeginScopePos, S: F);
3742
3743 if (Stmt *I = F->getInc()) {
3744 // Generate increment code in its own basic block. This is the target of
3745 // continue statements.
3746 Succ = addStmt(S: I);
3747 }
3748
3749 // Finish up the increment (or empty) block if it hasn't been already.
3750 if (Block) {
3751 assert(Block == Succ);
3752 if (badCFG)
3753 return nullptr;
3754 Block = nullptr;
3755 }
3756
3757 // The starting block for the loop increment is the block that should
3758 // represent the 'loop target' for looping back to the start of the loop.
3759 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
3760 ContinueJumpTarget.block->setLoopTarget(F);
3761
3762
3763 // If body is not a compound statement create implicit scope
3764 // and add destructors.
3765 if (!isa<CompoundStmt>(Val: F->getBody()))
3766 addLocalScopeAndDtors(S: F->getBody());
3767
3768 // Now populate the body block, and in the process create new blocks as we
3769 // walk the body of the loop.
3770 BodyBlock = addStmt(S: F->getBody());
3771
3772 if (!BodyBlock) {
3773 // In the case of "for (...;...;...);" we can have a null BodyBlock.
3774 // Use the continue jump target as the proxy for the body.
3775 BodyBlock = ContinueJumpTarget.block;
3776 }
3777 else if (badCFG)
3778 return nullptr;
3779 }
3780
3781 // Because of short-circuit evaluation, the condition of the loop can span
3782 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3783 // evaluate the condition.
3784 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3785
3786 do {
3787 Expr *C = F->getCond();
3788 SaveAndRestore save_scope_pos(ScopePos);
3789
3790 // Specially handle logical operators, which have a slightly
3791 // more optimal CFG representation.
3792 if (BinaryOperator *Cond =
3793 dyn_cast_or_null<BinaryOperator>(Val: C ? C->IgnoreParens() : nullptr))
3794 if (Cond->isLogicalOp()) {
3795 std::tie(args&: EntryConditionBlock, args&: ExitConditionBlock) =
3796 VisitLogicalOperator(B: Cond, Term: F, TrueBlock: BodyBlock, FalseBlock: LoopSuccessor);
3797 break;
3798 }
3799
3800 // The default case when not handling logical operators.
3801 EntryConditionBlock = ExitConditionBlock = createBlock(add_successor: false);
3802 ExitConditionBlock->setTerminator(F);
3803
3804 // See if this is a known constant.
3805 TryResult KnownVal(true);
3806
3807 if (C) {
3808 // Now add the actual condition to the condition block.
3809 // Because the condition itself may contain control-flow, new blocks may
3810 // be created. Thus we update "Succ" after adding the condition.
3811 Block = ExitConditionBlock;
3812 EntryConditionBlock = addStmt(S: C);
3813
3814 // If this block contains a condition variable, add both the condition
3815 // variable and initializer to the CFG.
3816 if (VarDecl *VD = F->getConditionVariable()) {
3817 if (Expr *Init = VD->getInit()) {
3818 autoCreateBlock();
3819 const DeclStmt *DS = F->getConditionVariableDeclStmt();
3820 assert(DS->isSingleDecl());
3821 findConstructionContexts(
3822 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: DS),
3823 Child: Init);
3824 appendStmt(B: Block, S: DS);
3825 EntryConditionBlock = addStmt(S: Init);
3826 assert(Block == EntryConditionBlock);
3827 maybeAddScopeBeginForVarDecl(B: EntryConditionBlock, VD, S: C);
3828 }
3829 }
3830
3831 if (Block && badCFG)
3832 return nullptr;
3833
3834 KnownVal = tryEvaluateBool(S: C);
3835 }
3836
3837 // Add the loop body entry as a successor to the condition.
3838 addSuccessor(B: ExitConditionBlock, S: KnownVal.isFalse() ? nullptr : BodyBlock);
3839 // Link up the condition block with the code that follows the loop. (the
3840 // false branch).
3841 addSuccessor(B: ExitConditionBlock,
3842 S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
3843 } while (false);
3844
3845 // Link up the loop-back block to the entry condition block.
3846 addSuccessor(B: TransitionBlock, S: EntryConditionBlock);
3847
3848 // The condition block is the implicit successor for any code above the loop.
3849 Succ = EntryConditionBlock;
3850
3851 // If the loop contains initialization, create a new block for those
3852 // statements. This block can also contain statements that precede the loop.
3853 if (Stmt *I = F->getInit()) {
3854 SaveAndRestore save_scope_pos(ScopePos);
3855 ScopePos = LoopBeginScopePos;
3856 Block = createBlock();
3857 return addStmt(S: I);
3858 }
3859
3860 // There is no loop initialization. We are thus basically a while loop.
3861 // NULL out Block to force lazy block construction.
3862 Block = nullptr;
3863 Succ = EntryConditionBlock;
3864 return EntryConditionBlock;
3865}
3866
3867CFGBlock *
3868CFGBuilder::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
3869 AddStmtChoice asc) {
3870 findConstructionContexts(
3871 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: MTE),
3872 Child: MTE->getSubExpr());
3873
3874 return VisitStmt(S: MTE, asc);
3875}
3876
3877CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
3878 if (asc.alwaysAdd(builder&: *this, stmt: M)) {
3879 autoCreateBlock();
3880 appendStmt(B: Block, S: M);
3881 }
3882 return Visit(S: M->getBase());
3883}
3884
3885CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
3886 // Objective-C fast enumeration 'for' statements:
3887 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
3888 //
3889 // for ( Type newVariable in collection_expression ) { statements }
3890 //
3891 // becomes:
3892 //
3893 // prologue:
3894 // 1. collection_expression
3895 // T. jump to loop_entry
3896 // loop_entry:
3897 // 1. side-effects of element expression
3898 // 1. ObjCForCollectionStmt [performs binding to newVariable]
3899 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
3900 // TB:
3901 // statements
3902 // T. jump to loop_entry
3903 // FB:
3904 // what comes after
3905 //
3906 // and
3907 //
3908 // Type existingItem;
3909 // for ( existingItem in expression ) { statements }
3910 //
3911 // becomes:
3912 //
3913 // the same with newVariable replaced with existingItem; the binding works
3914 // the same except that for one ObjCForCollectionStmt::getElement() returns
3915 // a DeclStmt and the other returns a DeclRefExpr.
3916
3917 CFGBlock *LoopSuccessor = nullptr;
3918
3919 if (Block) {
3920 if (badCFG)
3921 return nullptr;
3922 LoopSuccessor = Block;
3923 Block = nullptr;
3924 } else
3925 LoopSuccessor = Succ;
3926
3927 // Build the condition blocks.
3928 CFGBlock *ExitConditionBlock = createBlock(add_successor: false);
3929
3930 // Set the terminator for the "exit" condition block.
3931 ExitConditionBlock->setTerminator(S);
3932
3933 // The last statement in the block should be the ObjCForCollectionStmt, which
3934 // performs the actual binding to 'element' and determines if there are any
3935 // more items in the collection.
3936 appendStmt(B: ExitConditionBlock, S);
3937 Block = ExitConditionBlock;
3938
3939 // Walk the 'element' expression to see if there are any side-effects. We
3940 // generate new blocks as necessary. We DON'T add the statement by default to
3941 // the CFG unless it contains control-flow.
3942 CFGBlock *EntryConditionBlock = Visit(S: S->getElement(),
3943 asc: AddStmtChoice::NotAlwaysAdd);
3944 if (Block) {
3945 if (badCFG)
3946 return nullptr;
3947 Block = nullptr;
3948 }
3949
3950 // The condition block is the implicit successor for the loop body as well as
3951 // any code above the loop.
3952 Succ = EntryConditionBlock;
3953
3954 // Now create the true branch.
3955 {
3956 // Save the current values for Succ, continue and break targets.
3957 SaveAndRestore save_Block(Block), save_Succ(Succ);
3958 SaveAndRestore save_continue(ContinueJumpTarget),
3959 save_break(BreakJumpTarget);
3960
3961 // Add an intermediate block between the BodyBlock and the
3962 // EntryConditionBlock to represent the "loop back" transition, for looping
3963 // back to the head of the loop.
3964 CFGBlock *LoopBackBlock = nullptr;
3965 Succ = LoopBackBlock = createBlock();
3966 LoopBackBlock->setLoopTarget(S);
3967
3968 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3969 ContinueJumpTarget = JumpTarget(Succ, ScopePos);
3970
3971 CFGBlock *BodyBlock = addStmt(S: S->getBody());
3972
3973 if (!BodyBlock)
3974 BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;"
3975 else if (Block) {
3976 if (badCFG)
3977 return nullptr;
3978 }
3979
3980 // This new body block is a successor to our "exit" condition block.
3981 addSuccessor(B: ExitConditionBlock, S: BodyBlock);
3982 }
3983
3984 // Link up the condition block with the code that follows the loop.
3985 // (the false branch).
3986 addSuccessor(B: ExitConditionBlock, S: LoopSuccessor);
3987
3988 // Now create a prologue block to contain the collection expression.
3989 Block = createBlock();
3990 return addStmt(S: S->getCollection());
3991}
3992
3993CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) {
3994 // Inline the body.
3995 return addStmt(S: S->getSubStmt());
3996 // TODO: consider adding cleanups for the end of @autoreleasepool scope.
3997}
3998
3999CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
4000 // FIXME: Add locking 'primitives' to CFG for @synchronized.
4001
4002 // Inline the body.
4003 CFGBlock *SyncBlock = addStmt(S: S->getSynchBody());
4004
4005 // The sync body starts its own basic block. This makes it a little easier
4006 // for diagnostic clients.
4007 if (SyncBlock) {
4008 if (badCFG)
4009 return nullptr;
4010
4011 Block = nullptr;
4012 Succ = SyncBlock;
4013 }
4014
4015 // Add the @synchronized to the CFG.
4016 autoCreateBlock();
4017 appendStmt(B: Block, S);
4018
4019 // Inline the sync expression.
4020 return addStmt(S: S->getSynchExpr());
4021}
4022
4023CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {
4024 autoCreateBlock();
4025
4026 // Add the PseudoObject as the last thing.
4027 appendStmt(B: Block, S: E);
4028
4029 CFGBlock *lastBlock = Block;
4030
4031 // Before that, evaluate all of the semantics in order. In
4032 // CFG-land, that means appending them in reverse order.
4033 for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {
4034 Expr *Semantic = E->getSemanticExpr(index: --i);
4035
4036 // If the semantic is an opaque value, we're being asked to bind
4037 // it to its source expression.
4038 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Val: Semantic))
4039 Semantic = OVE->getSourceExpr();
4040
4041 if (CFGBlock *B = Visit(S: Semantic))
4042 lastBlock = B;
4043 }
4044
4045 return lastBlock;
4046}
4047
4048CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
4049 CFGBlock *LoopSuccessor = nullptr;
4050
4051 // Save local scope position because in case of condition variable ScopePos
4052 // won't be restored when traversing AST.
4053 SaveAndRestore save_scope_pos(ScopePos);
4054
4055 // Create local scope for possible condition variable.
4056 // Store scope position for continue statement.
4057 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
4058 if (VarDecl *VD = W->getConditionVariable()) {
4059 addLocalScopeForVarDecl(VD);
4060 addAutomaticObjHandling(B: ScopePos, E: LoopBeginScopePos, S: W);
4061 }
4062 addLoopExit(LoopStmt: W);
4063
4064 // "while" is a control-flow statement. Thus we stop processing the current
4065 // block.
4066 if (Block) {
4067 if (badCFG)
4068 return nullptr;
4069 LoopSuccessor = Block;
4070 Block = nullptr;
4071 } else {
4072 LoopSuccessor = Succ;
4073 }
4074
4075 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
4076
4077 // Process the loop body.
4078 {
4079 assert(W->getBody());
4080
4081 // Save the current values for Block, Succ, continue and break targets.
4082 SaveAndRestore save_Block(Block), save_Succ(Succ);
4083 SaveAndRestore save_continue(ContinueJumpTarget),
4084 save_break(BreakJumpTarget);
4085
4086 // Create an empty block to represent the transition block for looping back
4087 // to the head of the loop.
4088 Succ = TransitionBlock = createBlock(add_successor: false);
4089 TransitionBlock->setLoopTarget(W);
4090 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
4091
4092 // All breaks should go to the code following the loop.
4093 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4094
4095 // Loop body should end with destructor of Condition variable (if any).
4096 addAutomaticObjHandling(B: ScopePos, E: LoopBeginScopePos, S: W);
4097
4098 // If body is not a compound statement create implicit scope
4099 // and add destructors.
4100 if (!isa<CompoundStmt>(Val: W->getBody()))
4101 addLocalScopeAndDtors(S: W->getBody());
4102
4103 // Create the body. The returned block is the entry to the loop body.
4104 BodyBlock = addStmt(S: W->getBody());
4105
4106 if (!BodyBlock)
4107 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
4108 else if (Block && badCFG)
4109 return nullptr;
4110 }
4111
4112 // Because of short-circuit evaluation, the condition of the loop can span
4113 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
4114 // evaluate the condition.
4115 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
4116
4117 do {
4118 Expr *C = W->getCond();
4119
4120 // Specially handle logical operators, which have a slightly
4121 // more optimal CFG representation.
4122 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(Val: C->IgnoreParens()))
4123 if (Cond->isLogicalOp()) {
4124 std::tie(args&: EntryConditionBlock, args&: ExitConditionBlock) =
4125 VisitLogicalOperator(B: Cond, Term: W, TrueBlock: BodyBlock, FalseBlock: LoopSuccessor);
4126 break;
4127 }
4128
4129 // The default case when not handling logical operators.
4130 ExitConditionBlock = createBlock(add_successor: false);
4131 ExitConditionBlock->setTerminator(W);
4132
4133 // Now add the actual condition to the condition block.
4134 // Because the condition itself may contain control-flow, new blocks may
4135 // be created. Thus we update "Succ" after adding the condition.
4136 Block = ExitConditionBlock;
4137 Block = EntryConditionBlock = addStmt(S: C);
4138
4139 // If this block contains a condition variable, add both the condition
4140 // variable and initializer to the CFG.
4141 if (VarDecl *VD = W->getConditionVariable()) {
4142 if (Expr *Init = VD->getInit()) {
4143 autoCreateBlock();
4144 const DeclStmt *DS = W->getConditionVariableDeclStmt();
4145 assert(DS->isSingleDecl());
4146 findConstructionContexts(
4147 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(),
4148 Item: const_cast<DeclStmt *>(DS)),
4149 Child: Init);
4150 appendStmt(B: Block, S: DS);
4151 EntryConditionBlock = addStmt(S: Init);
4152 assert(Block == EntryConditionBlock);
4153 maybeAddScopeBeginForVarDecl(B: EntryConditionBlock, VD, S: C);
4154 }
4155 }
4156
4157 if (Block && badCFG)
4158 return nullptr;
4159
4160 // See if this is a known constant.
4161 const TryResult& KnownVal = tryEvaluateBool(S: C);
4162
4163 // Add the loop body entry as a successor to the condition.
4164 addSuccessor(B: ExitConditionBlock, S: KnownVal.isFalse() ? nullptr : BodyBlock);
4165 // Link up the condition block with the code that follows the loop. (the
4166 // false branch).
4167 addSuccessor(B: ExitConditionBlock,
4168 S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
4169 } while(false);
4170
4171 // Link up the loop-back block to the entry condition block.
4172 addSuccessor(B: TransitionBlock, S: EntryConditionBlock);
4173
4174 // There can be no more statements in the condition block since we loop back
4175 // to this block. NULL out Block to force lazy creation of another block.
4176 Block = nullptr;
4177
4178 // Return the condition block, which is the dominating block for the loop.
4179 Succ = EntryConditionBlock;
4180 return EntryConditionBlock;
4181}
4182
4183CFGBlock *CFGBuilder::VisitArrayInitLoopExpr(ArrayInitLoopExpr *A,
4184 AddStmtChoice asc) {
4185 if (asc.alwaysAdd(builder&: *this, stmt: A)) {
4186 autoCreateBlock();
4187 appendStmt(B: Block, S: A);
4188 }
4189
4190 CFGBlock *B = Block;
4191
4192 if (CFGBlock *R = Visit(S: A->getSubExpr()))
4193 B = R;
4194
4195 OpaqueValueExpr *OVE = A->getCommonExpr();
4196 if (CFGBlock *R = Visit(S: OVE->getSourceExpr()))
4197 B = R;
4198
4199 return B;
4200}
4201
4202CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *CS) {
4203 // ObjCAtCatchStmt are treated like labels, so they are the first statement
4204 // in a block.
4205
4206 // Save local scope position because in case of exception variable ScopePos
4207 // won't be restored when traversing AST.
4208 SaveAndRestore save_scope_pos(ScopePos);
4209
4210 if (CS->getCatchBody())
4211 addStmt(S: CS->getCatchBody());
4212
4213 CFGBlock *CatchBlock = Block;
4214 if (!CatchBlock)
4215 CatchBlock = createBlock();
4216
4217 appendStmt(B: CatchBlock, S: CS);
4218
4219 // Also add the ObjCAtCatchStmt as a label, like with regular labels.
4220 CatchBlock->setLabel(CS);
4221
4222 // Bail out if the CFG is bad.
4223 if (badCFG)
4224 return nullptr;
4225
4226 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4227 Block = nullptr;
4228
4229 return CatchBlock;
4230}
4231
4232CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
4233 // If we were in the middle of a block we stop processing that block.
4234 if (badCFG)
4235 return nullptr;
4236
4237 // Create the new block.
4238 Block = createBlock(add_successor: false);
4239
4240 if (TryTerminatedBlock)
4241 // The current try statement is the only successor.
4242 addSuccessor(B: Block, S: TryTerminatedBlock);
4243 else
4244 // otherwise the Exit block is the only successor.
4245 addSuccessor(B: Block, S: &cfg->getExit());
4246
4247 // Add the statement to the block. This may create new blocks if S contains
4248 // control-flow (short-circuit operations).
4249 return VisitStmt(S, asc: AddStmtChoice::AlwaysAdd);
4250}
4251
4252CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *Terminator) {
4253 // "@try"/"@catch" is a control-flow statement. Thus we stop processing the
4254 // current block.
4255 CFGBlock *TrySuccessor = nullptr;
4256
4257 if (Block) {
4258 if (badCFG)
4259 return nullptr;
4260 TrySuccessor = Block;
4261 } else
4262 TrySuccessor = Succ;
4263
4264 // FIXME: Implement @finally support.
4265 if (Terminator->getFinallyStmt())
4266 return NYS();
4267
4268 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
4269
4270 // Create a new block that will contain the try statement.
4271 CFGBlock *NewTryTerminatedBlock = createBlock(add_successor: false);
4272 // Add the terminator in the try block.
4273 NewTryTerminatedBlock->setTerminator(Terminator);
4274
4275 bool HasCatchAll = false;
4276 for (ObjCAtCatchStmt *CS : Terminator->catch_stmts()) {
4277 // The code after the try is the implicit successor.
4278 Succ = TrySuccessor;
4279 if (CS->hasEllipsis()) {
4280 HasCatchAll = true;
4281 }
4282 Block = nullptr;
4283 CFGBlock *CatchBlock = VisitObjCAtCatchStmt(CS);
4284 if (!CatchBlock)
4285 return nullptr;
4286 // Add this block to the list of successors for the block with the try
4287 // statement.
4288 addSuccessor(B: NewTryTerminatedBlock, S: CatchBlock);
4289 }
4290
4291 // FIXME: This needs updating when @finally support is added.
4292 if (!HasCatchAll) {
4293 if (PrevTryTerminatedBlock)
4294 addSuccessor(B: NewTryTerminatedBlock, S: PrevTryTerminatedBlock);
4295 else
4296 addSuccessor(B: NewTryTerminatedBlock, S: &cfg->getExit());
4297 }
4298
4299 // The code after the try is the implicit successor.
4300 Succ = TrySuccessor;
4301
4302 // Save the current "try" context.
4303 SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);
4304 cfg->addTryDispatchBlock(block: TryTerminatedBlock);
4305
4306 assert(Terminator->getTryBody() && "try must contain a non-NULL body");
4307 Block = nullptr;
4308 return addStmt(S: Terminator->getTryBody());
4309}
4310
4311CFGBlock *CFGBuilder::VisitObjCMessageExpr(ObjCMessageExpr *ME,
4312 AddStmtChoice asc) {
4313 findConstructionContextsForArguments(E: ME);
4314
4315 autoCreateBlock();
4316 appendObjCMessage(B: Block, ME);
4317
4318 return VisitChildren(S: ME);
4319}
4320
4321CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
4322 // If we were in the middle of a block we stop processing that block.
4323 if (badCFG)
4324 return nullptr;
4325
4326 // Create the new block.
4327 Block = createBlock(add_successor: false);
4328
4329 if (TryTerminatedBlock)
4330 // The current try statement is the only successor.
4331 addSuccessor(B: Block, S: TryTerminatedBlock);
4332 else
4333 // otherwise the Exit block is the only successor.
4334 addSuccessor(B: Block, S: &cfg->getExit());
4335
4336 // Add the statement to the block. This may create new blocks if S contains
4337 // control-flow (short-circuit operations).
4338 return VisitStmt(S: T, asc: AddStmtChoice::AlwaysAdd);
4339}
4340
4341CFGBlock *CFGBuilder::VisitCXXTypeidExpr(CXXTypeidExpr *S, AddStmtChoice asc) {
4342 if (asc.alwaysAdd(builder&: *this, stmt: S)) {
4343 autoCreateBlock();
4344 appendStmt(B: Block, S);
4345 }
4346
4347 // C++ [expr.typeid]p3:
4348 // When typeid is applied to an expression other than an glvalue of a
4349 // polymorphic class type [...] [the] expression is an unevaluated
4350 // operand. [...]
4351 // We add only potentially evaluated statements to the block to avoid
4352 // CFG generation for unevaluated operands.
4353 if (!S->isTypeDependent() && S->isPotentiallyEvaluated())
4354 return VisitChildren(S);
4355
4356 // Return block without CFG for unevaluated operands.
4357 return Block;
4358}
4359
4360CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
4361 CFGBlock *LoopSuccessor = nullptr;
4362
4363 addLoopExit(LoopStmt: D);
4364
4365 // "do...while" is a control-flow statement. Thus we stop processing the
4366 // current block.
4367 if (Block) {
4368 if (badCFG)
4369 return nullptr;
4370 LoopSuccessor = Block;
4371 } else
4372 LoopSuccessor = Succ;
4373
4374 // Because of short-circuit evaluation, the condition of the loop can span
4375 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
4376 // evaluate the condition.
4377 CFGBlock *ExitConditionBlock = createBlock(add_successor: false);
4378 CFGBlock *EntryConditionBlock = ExitConditionBlock;
4379
4380 // Set the terminator for the "exit" condition block.
4381 ExitConditionBlock->setTerminator(D);
4382
4383 // Now add the actual condition to the condition block. Because the condition
4384 // itself may contain control-flow, new blocks may be created.
4385 if (Stmt *C = D->getCond()) {
4386 Block = ExitConditionBlock;
4387 EntryConditionBlock = addStmt(S: C);
4388 if (Block) {
4389 if (badCFG)
4390 return nullptr;
4391 }
4392 }
4393
4394 // The condition block is the implicit successor for the loop body.
4395 Succ = EntryConditionBlock;
4396
4397 // See if this is a known constant.
4398 const TryResult &KnownVal = tryEvaluateBool(S: D->getCond());
4399
4400 // Process the loop body.
4401 CFGBlock *BodyBlock = nullptr;
4402 {
4403 assert(D->getBody());
4404
4405 // Save the current values for Block, Succ, and continue and break targets
4406 SaveAndRestore save_Block(Block), save_Succ(Succ);
4407 SaveAndRestore save_continue(ContinueJumpTarget),
4408 save_break(BreakJumpTarget);
4409
4410 // All continues within this loop should go to the condition block
4411 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
4412
4413 // All breaks should go to the code following the loop.
4414 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4415
4416 // NULL out Block to force lazy instantiation of blocks for the body.
4417 Block = nullptr;
4418
4419 // If body is not a compound statement create implicit scope
4420 // and add destructors.
4421 if (!isa<CompoundStmt>(Val: D->getBody()))
4422 addLocalScopeAndDtors(S: D->getBody());
4423
4424 // Create the body. The returned block is the entry to the loop body.
4425 BodyBlock = addStmt(S: D->getBody());
4426
4427 if (!BodyBlock)
4428 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
4429 else if (Block) {
4430 if (badCFG)
4431 return nullptr;
4432 }
4433
4434 // Add an intermediate block between the BodyBlock and the
4435 // ExitConditionBlock to represent the "loop back" transition. Create an
4436 // empty block to represent the transition block for looping back to the
4437 // head of the loop.
4438 // FIXME: Can we do this more efficiently without adding another block?
4439 Block = nullptr;
4440 Succ = BodyBlock;
4441 CFGBlock *LoopBackBlock = createBlock();
4442 LoopBackBlock->setLoopTarget(D);
4443
4444 if (!KnownVal.isFalse())
4445 // Add the loop body entry as a successor to the condition.
4446 addSuccessor(B: ExitConditionBlock, S: LoopBackBlock);
4447 else
4448 addSuccessor(B: ExitConditionBlock, S: nullptr);
4449 }
4450
4451 // Link up the condition block with the code that follows the loop.
4452 // (the false branch).
4453 addSuccessor(B: ExitConditionBlock, S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
4454
4455 // There can be no more statements in the body block(s) since we loop back to
4456 // the body. NULL out Block to force lazy creation of another block.
4457 Block = nullptr;
4458
4459 // Return the loop body, which is the dominating block for the loop.
4460 Succ = BodyBlock;
4461 return BodyBlock;
4462}
4463
4464CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
4465 // "continue" is a control-flow statement. Thus we stop processing the
4466 // current block.
4467 if (badCFG)
4468 return nullptr;
4469
4470 // Now create a new block that ends with the continue statement.
4471 Block = createBlock(add_successor: false);
4472 Block->setTerminator(C);
4473
4474 // If there is no target for the continue, then we are looking at an
4475 // incomplete AST. This means the CFG cannot be constructed.
4476 if (ContinueJumpTarget.block) {
4477 addAutomaticObjHandling(B: ScopePos, E: ContinueJumpTarget.scopePosition, S: C);
4478 addSuccessor(B: Block, S: ContinueJumpTarget.block);
4479 } else
4480 badCFG = true;
4481
4482 return Block;
4483}
4484
4485CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
4486 AddStmtChoice asc) {
4487 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
4488 autoCreateBlock();
4489 appendStmt(B: Block, S: E);
4490 }
4491
4492 // VLA types have expressions that must be evaluated.
4493 // Evaluation is done only for `sizeof`.
4494
4495 if (E->getKind() != UETT_SizeOf)
4496 return Block;
4497
4498 CFGBlock *lastBlock = Block;
4499
4500 if (E->isArgumentType()) {
4501 for (const VariableArrayType *VA =FindVA(t: E->getArgumentType().getTypePtr());
4502 VA != nullptr; VA = FindVA(t: VA->getElementType().getTypePtr()))
4503 lastBlock = addStmt(S: VA->getSizeExpr());
4504 }
4505 return lastBlock;
4506}
4507
4508/// VisitStmtExpr - Utility method to handle (nested) statement
4509/// expressions (a GCC extension).
4510CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
4511 if (asc.alwaysAdd(builder&: *this, stmt: SE)) {
4512 autoCreateBlock();
4513 appendStmt(B: Block, S: SE);
4514 }
4515 return VisitCompoundStmt(C: SE->getSubStmt(), /*ExternallyDestructed=*/true);
4516}
4517
4518CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
4519 // "switch" is a control-flow statement. Thus we stop processing the current
4520 // block.
4521 CFGBlock *SwitchSuccessor = nullptr;
4522
4523 // Save local scope position because in case of condition variable ScopePos
4524 // won't be restored when traversing AST.
4525 SaveAndRestore save_scope_pos(ScopePos);
4526
4527 // Create local scope for C++17 switch init-stmt if one exists.
4528 if (Stmt *Init = Terminator->getInit())
4529 addLocalScopeForStmt(S: Init);
4530
4531 // Create local scope for possible condition variable.
4532 // Store scope position. Add implicit destructor.
4533 if (VarDecl *VD = Terminator->getConditionVariable())
4534 addLocalScopeForVarDecl(VD);
4535
4536 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S: Terminator);
4537
4538 if (Block) {
4539 if (badCFG)
4540 return nullptr;
4541 SwitchSuccessor = Block;
4542 } else SwitchSuccessor = Succ;
4543
4544 // Save the current "switch" context.
4545 SaveAndRestore save_switch(SwitchTerminatedBlock),
4546 save_default(DefaultCaseBlock);
4547 SaveAndRestore save_break(BreakJumpTarget);
4548
4549 // Set the "default" case to be the block after the switch statement. If the
4550 // switch statement contains a "default:", this value will be overwritten with
4551 // the block for that code.
4552 DefaultCaseBlock = SwitchSuccessor;
4553
4554 // Create a new block that will contain the switch statement.
4555 SwitchTerminatedBlock = createBlock(add_successor: false);
4556
4557 // Now process the switch body. The code after the switch is the implicit
4558 // successor.
4559 Succ = SwitchSuccessor;
4560 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
4561
4562 // When visiting the body, the case statements should automatically get linked
4563 // up to the switch. We also don't keep a pointer to the body, since all
4564 // control-flow from the switch goes to case/default statements.
4565 assert(Terminator->getBody() && "switch must contain a non-NULL body");
4566 Block = nullptr;
4567
4568 // For pruning unreachable case statements, save the current state
4569 // for tracking the condition value.
4570 SaveAndRestore save_switchExclusivelyCovered(switchExclusivelyCovered, false);
4571
4572 // Determine if the switch condition can be explicitly evaluated.
4573 assert(Terminator->getCond() && "switch condition must be non-NULL");
4574 Expr::EvalResult result;
4575 bool b = tryEvaluate(S: Terminator->getCond(), outResult&: result);
4576 SaveAndRestore save_switchCond(switchCond, b ? &result : nullptr);
4577
4578 // If body is not a compound statement create implicit scope
4579 // and add destructors.
4580 if (!isa<CompoundStmt>(Val: Terminator->getBody()))
4581 addLocalScopeAndDtors(S: Terminator->getBody());
4582
4583 addStmt(S: Terminator->getBody());
4584 if (Block) {
4585 if (badCFG)
4586 return nullptr;
4587 }
4588
4589 // If we have no "default:" case, the default transition is to the code
4590 // following the switch body. Moreover, take into account if all the
4591 // cases of a switch are covered (e.g., switching on an enum value).
4592 //
4593 // Note: We add a successor to a switch that is considered covered yet has no
4594 // case statements if the enumeration has no enumerators.
4595 // We also consider this successor reachable if
4596 // BuildOpts.SwitchReqDefaultCoveredEnum is true.
4597 bool SwitchAlwaysHasSuccessor = false;
4598 SwitchAlwaysHasSuccessor |= switchExclusivelyCovered;
4599 SwitchAlwaysHasSuccessor |=
4600 !BuildOpts.AssumeReachableDefaultInSwitchStatements &&
4601 Terminator->isAllEnumCasesCovered() && Terminator->getSwitchCaseList();
4602 addSuccessor(B: SwitchTerminatedBlock, S: DefaultCaseBlock,
4603 IsReachable: !SwitchAlwaysHasSuccessor);
4604
4605 // Add the terminator and condition in the switch block.
4606 SwitchTerminatedBlock->setTerminator(Terminator);
4607 Block = SwitchTerminatedBlock;
4608 CFGBlock *LastBlock = addStmt(S: Terminator->getCond());
4609
4610 // If the SwitchStmt contains a condition variable, add both the
4611 // SwitchStmt and the condition variable initialization to the CFG.
4612 if (VarDecl *VD = Terminator->getConditionVariable()) {
4613 if (Expr *Init = VD->getInit()) {
4614 autoCreateBlock();
4615 appendStmt(B: Block, S: Terminator->getConditionVariableDeclStmt());
4616 LastBlock = addStmt(S: Init);
4617 maybeAddScopeBeginForVarDecl(B: LastBlock, VD, S: Init);
4618 }
4619 }
4620
4621 // Finally, if the SwitchStmt contains a C++17 init-stmt, add it to the CFG.
4622 if (Stmt *Init = Terminator->getInit()) {
4623 autoCreateBlock();
4624 LastBlock = addStmt(S: Init);
4625 }
4626
4627 return LastBlock;
4628}
4629
4630static bool shouldAddCase(bool &switchExclusivelyCovered,
4631 const Expr::EvalResult *switchCond,
4632 const CaseStmt *CS,
4633 ASTContext &Ctx) {
4634 if (!switchCond)
4635 return true;
4636
4637 bool addCase = false;
4638
4639 if (!switchExclusivelyCovered) {
4640 if (switchCond->Val.isInt()) {
4641 // Evaluate the LHS of the case value.
4642 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
4643 const llvm::APSInt &condInt = switchCond->Val.getInt();
4644
4645 if (condInt == lhsInt) {
4646 addCase = true;
4647 switchExclusivelyCovered = true;
4648 }
4649 else if (condInt > lhsInt) {
4650 if (const Expr *RHS = CS->getRHS()) {
4651 // Evaluate the RHS of the case value.
4652 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
4653 if (V2 >= condInt) {
4654 addCase = true;
4655 switchExclusivelyCovered = true;
4656 }
4657 }
4658 }
4659 }
4660 else
4661 addCase = true;
4662 }
4663 return addCase;
4664}
4665
4666CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
4667 // CaseStmts are essentially labels, so they are the first statement in a
4668 // block.
4669 CFGBlock *TopBlock = nullptr, *LastBlock = nullptr;
4670
4671 if (Stmt *Sub = CS->getSubStmt()) {
4672 // For deeply nested chains of CaseStmts, instead of doing a recursion
4673 // (which can blow out the stack), manually unroll and create blocks
4674 // along the way.
4675 while (isa<CaseStmt>(Val: Sub)) {
4676 CFGBlock *currentBlock = createBlock(add_successor: false);
4677 currentBlock->setLabel(CS);
4678
4679 if (TopBlock)
4680 addSuccessor(B: LastBlock, S: currentBlock);
4681 else
4682 TopBlock = currentBlock;
4683
4684 addSuccessor(B: SwitchTerminatedBlock,
4685 S: shouldAddCase(switchExclusivelyCovered, switchCond,
4686 CS, Ctx&: *Context)
4687 ? currentBlock : nullptr);
4688
4689 LastBlock = currentBlock;
4690 CS = cast<CaseStmt>(Val: Sub);
4691 Sub = CS->getSubStmt();
4692 }
4693
4694 addStmt(S: Sub);
4695 }
4696
4697 CFGBlock *CaseBlock = Block;
4698 if (!CaseBlock)
4699 CaseBlock = createBlock();
4700
4701 // Cases statements partition blocks, so this is the top of the basic block we
4702 // were processing (the "case XXX:" is the label).
4703 CaseBlock->setLabel(CS);
4704
4705 if (badCFG)
4706 return nullptr;
4707
4708 // Add this block to the list of successors for the block with the switch
4709 // statement.
4710 assert(SwitchTerminatedBlock);
4711 addSuccessor(B: SwitchTerminatedBlock, S: CaseBlock,
4712 IsReachable: shouldAddCase(switchExclusivelyCovered, switchCond,
4713 CS, Ctx&: *Context));
4714
4715 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4716 Block = nullptr;
4717
4718 if (TopBlock) {
4719 addSuccessor(B: LastBlock, S: CaseBlock);
4720 Succ = TopBlock;
4721 } else {
4722 // This block is now the implicit successor of other blocks.
4723 Succ = CaseBlock;
4724 }
4725
4726 return Succ;
4727}
4728
4729CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
4730 if (Terminator->getSubStmt())
4731 addStmt(S: Terminator->getSubStmt());
4732
4733 DefaultCaseBlock = Block;
4734
4735 if (!DefaultCaseBlock)
4736 DefaultCaseBlock = createBlock();
4737
4738 // Default statements partition blocks, so this is the top of the basic block
4739 // we were processing (the "default:" is the label).
4740 DefaultCaseBlock->setLabel(Terminator);
4741
4742 if (badCFG)
4743 return nullptr;
4744
4745 // Unlike case statements, we don't add the default block to the successors
4746 // for the switch statement immediately. This is done when we finish
4747 // processing the switch statement. This allows for the default case
4748 // (including a fall-through to the code after the switch statement) to always
4749 // be the last successor of a switch-terminated block.
4750
4751 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4752 Block = nullptr;
4753
4754 // This block is now the implicit successor of other blocks.
4755 Succ = DefaultCaseBlock;
4756
4757 return DefaultCaseBlock;
4758}
4759
4760CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
4761 // "try"/"catch" is a control-flow statement. Thus we stop processing the
4762 // current block.
4763 CFGBlock *TrySuccessor = nullptr;
4764
4765 if (Block) {
4766 if (badCFG)
4767 return nullptr;
4768 TrySuccessor = Block;
4769 } else
4770 TrySuccessor = Succ;
4771
4772 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
4773
4774 // Create a new block that will contain the try statement.
4775 CFGBlock *NewTryTerminatedBlock = createBlock(add_successor: false);
4776 // Add the terminator in the try block.
4777 NewTryTerminatedBlock->setTerminator(Terminator);
4778
4779 bool HasCatchAll = false;
4780 for (unsigned I = 0, E = Terminator->getNumHandlers(); I != E; ++I) {
4781 // The code after the try is the implicit successor.
4782 Succ = TrySuccessor;
4783 CXXCatchStmt *CS = Terminator->getHandler(i: I);
4784 if (CS->getExceptionDecl() == nullptr) {
4785 HasCatchAll = true;
4786 }
4787 Block = nullptr;
4788 CFGBlock *CatchBlock = VisitCXXCatchStmt(S: CS);
4789 if (!CatchBlock)
4790 return nullptr;
4791 // Add this block to the list of successors for the block with the try
4792 // statement.
4793 addSuccessor(B: NewTryTerminatedBlock, S: CatchBlock);
4794 }
4795 if (!HasCatchAll) {
4796 if (PrevTryTerminatedBlock)
4797 addSuccessor(B: NewTryTerminatedBlock, S: PrevTryTerminatedBlock);
4798 else
4799 addSuccessor(B: NewTryTerminatedBlock, S: &cfg->getExit());
4800 }
4801
4802 // The code after the try is the implicit successor.
4803 Succ = TrySuccessor;
4804
4805 // Save the current "try" context.
4806 SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);
4807 cfg->addTryDispatchBlock(block: TryTerminatedBlock);
4808
4809 assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
4810 Block = nullptr;
4811 return addStmt(S: Terminator->getTryBlock());
4812}
4813
4814CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
4815 // CXXCatchStmt are treated like labels, so they are the first statement in a
4816 // block.
4817
4818 // Save local scope position because in case of exception variable ScopePos
4819 // won't be restored when traversing AST.
4820 SaveAndRestore save_scope_pos(ScopePos);
4821
4822 // Create local scope for possible exception variable.
4823 // Store scope position. Add implicit destructor.
4824 if (VarDecl *VD = CS->getExceptionDecl()) {
4825 LocalScope::const_iterator BeginScopePos = ScopePos;
4826 addLocalScopeForVarDecl(VD);
4827 addAutomaticObjHandling(B: ScopePos, E: BeginScopePos, S: CS);
4828 }
4829
4830 if (CS->getHandlerBlock())
4831 addStmt(S: CS->getHandlerBlock());
4832
4833 CFGBlock *CatchBlock = Block;
4834 if (!CatchBlock)
4835 CatchBlock = createBlock();
4836
4837 // CXXCatchStmt is more than just a label. They have semantic meaning
4838 // as well, as they implicitly "initialize" the catch variable. Add
4839 // it to the CFG as a CFGElement so that the control-flow of these
4840 // semantics gets captured.
4841 appendStmt(B: CatchBlock, S: CS);
4842
4843 // Also add the CXXCatchStmt as a label, to mirror handling of regular
4844 // labels.
4845 CatchBlock->setLabel(CS);
4846
4847 // Bail out if the CFG is bad.
4848 if (badCFG)
4849 return nullptr;
4850
4851 // We set Block to NULL to allow lazy creation of a new block (if necessary).
4852 Block = nullptr;
4853
4854 return CatchBlock;
4855}
4856
4857CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
4858 // C++0x for-range statements are specified as [stmt.ranged]:
4859 //
4860 // {
4861 // auto && __range = range-init;
4862 // for ( auto __begin = begin-expr,
4863 // __end = end-expr;
4864 // __begin != __end;
4865 // ++__begin ) {
4866 // for-range-declaration = *__begin;
4867 // statement
4868 // }
4869 // }
4870
4871 // Save local scope position before the addition of the implicit variables.
4872 SaveAndRestore save_scope_pos(ScopePos);
4873
4874 // Create local scopes and destructors for init, range, begin and end
4875 // variables.
4876 if (Stmt *Init = S->getInit())
4877 addLocalScopeForStmt(S: Init);
4878 if (Stmt *Range = S->getRangeStmt())
4879 addLocalScopeForStmt(S: Range);
4880 if (Stmt *Begin = S->getBeginStmt())
4881 addLocalScopeForStmt(S: Begin);
4882 if (Stmt *End = S->getEndStmt())
4883 addLocalScopeForStmt(S: End);
4884 addAutomaticObjHandling(B: ScopePos, E: save_scope_pos.get(), S);
4885
4886 LocalScope::const_iterator ContinueScopePos = ScopePos;
4887
4888 // "for" is a control-flow statement. Thus we stop processing the current
4889 // block.
4890 CFGBlock *LoopSuccessor = nullptr;
4891 if (Block) {
4892 if (badCFG)
4893 return nullptr;
4894 LoopSuccessor = Block;
4895 } else
4896 LoopSuccessor = Succ;
4897
4898 // Save the current value for the break targets.
4899 // All breaks should go to the code following the loop.
4900 SaveAndRestore save_break(BreakJumpTarget);
4901 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4902
4903 // The block for the __begin != __end expression.
4904 CFGBlock *ConditionBlock = createBlock(add_successor: false);
4905 ConditionBlock->setTerminator(S);
4906
4907 // Now add the actual condition to the condition block.
4908 if (Expr *C = S->getCond()) {
4909 Block = ConditionBlock;
4910 CFGBlock *BeginConditionBlock = addStmt(S: C);
4911 if (badCFG)
4912 return nullptr;
4913 assert(BeginConditionBlock == ConditionBlock &&
4914 "condition block in for-range was unexpectedly complex");
4915 (void)BeginConditionBlock;
4916 }
4917
4918 // The condition block is the implicit successor for the loop body as well as
4919 // any code above the loop.
4920 Succ = ConditionBlock;
4921
4922 // See if this is a known constant.
4923 TryResult KnownVal(true);
4924
4925 if (S->getCond())
4926 KnownVal = tryEvaluateBool(S: S->getCond());
4927
4928 // Now create the loop body.
4929 {
4930 assert(S->getBody());
4931
4932 // Save the current values for Block, Succ, and continue targets.
4933 SaveAndRestore save_Block(Block), save_Succ(Succ);
4934 SaveAndRestore save_continue(ContinueJumpTarget);
4935
4936 // Generate increment code in its own basic block. This is the target of
4937 // continue statements.
4938 Block = nullptr;
4939 Succ = addStmt(S: S->getInc());
4940 if (badCFG)
4941 return nullptr;
4942 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
4943
4944 // The starting block for the loop increment is the block that should
4945 // represent the 'loop target' for looping back to the start of the loop.
4946 ContinueJumpTarget.block->setLoopTarget(S);
4947
4948 // Finish up the increment block and prepare to start the loop body.
4949 assert(Block);
4950 if (badCFG)
4951 return nullptr;
4952 Block = nullptr;
4953
4954 // Add implicit scope and dtors for loop variable.
4955 addLocalScopeAndDtors(S: S->getLoopVarStmt());
4956
4957 // If body is not a compound statement create implicit scope
4958 // and add destructors.
4959 if (!isa<CompoundStmt>(Val: S->getBody()))
4960 addLocalScopeAndDtors(S: S->getBody());
4961
4962 // Populate a new block to contain the loop body and loop variable.
4963 addStmt(S: S->getBody());
4964
4965 if (badCFG)
4966 return nullptr;
4967 CFGBlock *LoopVarStmtBlock = addStmt(S: S->getLoopVarStmt());
4968 if (badCFG)
4969 return nullptr;
4970
4971 // This new body block is a successor to our condition block.
4972 addSuccessor(B: ConditionBlock,
4973 S: KnownVal.isFalse() ? nullptr : LoopVarStmtBlock);
4974 }
4975
4976 // Link up the condition block with the code that follows the loop (the
4977 // false branch).
4978 addSuccessor(B: ConditionBlock, S: KnownVal.isTrue() ? nullptr : LoopSuccessor);
4979
4980 // Add the initialization statements.
4981 Block = createBlock();
4982 addStmt(S: S->getBeginStmt());
4983 addStmt(S: S->getEndStmt());
4984 CFGBlock *Head = addStmt(S: S->getRangeStmt());
4985 if (S->getInit())
4986 Head = addStmt(S: S->getInit());
4987 return Head;
4988}
4989
4990CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
4991 AddStmtChoice asc,
4992 bool ExternallyDestructed) {
4993 if (BuildOpts.AddTemporaryDtors || BuildOpts.AddLifetime) {
4994 // If adding implicit destructors visit the full expression for adding
4995 // destructors of temporaries.
4996 TempDtorContext Context;
4997 Expr *FullExpr = E->getSubExpr();
4998 VisitForTemporaries(E: FullExpr, ExternallyDestructed, Context);
4999
5000 addFullExprCleanupMarker(Context, CleanupExpr: E);
5001
5002 // Full expression has to be added as CFGStmt so it will be sequenced
5003 // before destructors of it's temporaries.
5004 asc = asc.withAlwaysAdd(alwaysAdd: true);
5005 }
5006 return Visit(S: E->getSubExpr(), asc);
5007}
5008
5009CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
5010 AddStmtChoice asc) {
5011 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
5012 autoCreateBlock();
5013 appendStmt(B: Block, S: E);
5014
5015 findConstructionContexts(
5016 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: E),
5017 Child: E->getSubExpr());
5018
5019 // We do not want to propagate the AlwaysAdd property.
5020 asc = asc.withAlwaysAdd(alwaysAdd: false);
5021 }
5022 return Visit(S: E->getSubExpr(), asc);
5023}
5024
5025CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
5026 AddStmtChoice asc) {
5027 // If the constructor takes objects as arguments by value, we need to properly
5028 // construct these objects. Construction contexts we find here aren't for the
5029 // constructor C, they're for its arguments only.
5030 findConstructionContextsForArguments(E: C);
5031 appendConstructor(CE: C);
5032
5033 return VisitChildren(S: C);
5034}
5035
5036CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
5037 AddStmtChoice asc) {
5038 autoCreateBlock();
5039 appendStmt(B: Block, S: NE);
5040
5041 findConstructionContexts(
5042 Layer: ConstructionContextLayer::create(C&: cfg->getBumpVectorContext(), Item: NE),
5043 Child: const_cast<CXXConstructExpr *>(NE->getConstructExpr()));
5044
5045 if (NE->getInitializer())
5046 Block = Visit(S: NE->getInitializer());
5047
5048 if (BuildOpts.AddCXXNewAllocator)
5049 appendNewAllocator(B: Block, NE);
5050
5051 if (NE->isArray() && *NE->getArraySize())
5052 Block = Visit(S: *NE->getArraySize());
5053
5054 for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),
5055 E = NE->placement_arg_end(); I != E; ++I)
5056 Block = Visit(S: *I);
5057
5058 return Block;
5059}
5060
5061CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
5062 AddStmtChoice asc) {
5063 autoCreateBlock();
5064 appendStmt(B: Block, S: DE);
5065 QualType DTy = DE->getDestroyedType();
5066 if (!DTy.isNull()) {
5067 DTy = DTy.getNonReferenceType();
5068 CXXRecordDecl *RD = Context->getBaseElementType(QT: DTy)->getAsCXXRecordDecl();
5069 if (RD) {
5070 if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())
5071 appendDeleteDtor(B: Block, RD, DE);
5072 }
5073 }
5074
5075 return VisitChildren(S: DE);
5076}
5077
5078CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
5079 AddStmtChoice asc) {
5080 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
5081 autoCreateBlock();
5082 appendStmt(B: Block, S: E);
5083 // We do not want to propagate the AlwaysAdd property.
5084 asc = asc.withAlwaysAdd(alwaysAdd: false);
5085 }
5086 return Visit(S: E->getSubExpr(), asc);
5087}
5088
5089CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *E,
5090 AddStmtChoice asc) {
5091 // If the constructor takes objects as arguments by value, we need to properly
5092 // construct these objects. Construction contexts we find here aren't for the
5093 // constructor C, they're for its arguments only.
5094 findConstructionContextsForArguments(E);
5095 appendConstructor(CE: E);
5096
5097 return VisitChildren(S: E);
5098}
5099
5100CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
5101 AddStmtChoice asc) {
5102 if (asc.alwaysAdd(builder&: *this, stmt: E)) {
5103 autoCreateBlock();
5104 appendStmt(B: Block, S: E);
5105 }
5106
5107 if (E->getCastKind() == CK_IntegralToBoolean)
5108 tryEvaluateBool(S: E->getSubExpr()->IgnoreParens());
5109
5110 return Visit(S: E->getSubExpr(), asc: AddStmtChoice());
5111}
5112
5113CFGBlock *CFGBuilder::VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc) {
5114 return Visit(S: E->getSubExpr(), asc: AddStmtChoice());
5115}
5116
5117CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
5118 // Lazily create the indirect-goto dispatch block if there isn't one already.
5119 CFGBlock *IBlock = cfg->getIndirectGotoBlock();
5120
5121 if (!IBlock) {
5122 IBlock = createBlock(add_successor: false);
5123 cfg->setIndirectGotoBlock(IBlock);
5124 }
5125
5126 // IndirectGoto is a control-flow statement. Thus we stop processing the
5127 // current block and create a new one.
5128 if (badCFG)
5129 return nullptr;
5130
5131 Block = createBlock(add_successor: false);
5132 Block->setTerminator(I);
5133 addSuccessor(B: Block, S: IBlock);
5134 return addStmt(S: I->getTarget());
5135}
5136
5137CFGBlock *CFGBuilder::VisitForTemporaries(Stmt *E, bool ExternallyDestructed,
5138 TempDtorContext &Context) {
5139
5140tryAgain:
5141 if (!E) {
5142 badCFG = true;
5143 return nullptr;
5144 }
5145 switch (E->getStmtClass()) {
5146 default:
5147 return VisitChildrenForTemporaries(E, ExternallyDestructed: false, Context);
5148
5149 case Stmt::InitListExprClass:
5150 return VisitChildrenForTemporaries(E, ExternallyDestructed, Context);
5151
5152 case Stmt::BinaryOperatorClass:
5153 return VisitBinaryOperatorForTemporaries(E: cast<BinaryOperator>(Val: E),
5154 ExternallyDestructed, Context);
5155
5156 case Stmt::CXXOperatorCallExprClass:
5157 return VisitCXXOperatorCallExprForTemporaryDtors(
5158 E: cast<CXXOperatorCallExpr>(Val: E), Context);
5159
5160 case Stmt::CXXBindTemporaryExprClass:
5161 return VisitCXXBindTemporaryExprForTemporaryDtors(
5162 E: cast<CXXBindTemporaryExpr>(Val: E), ExternallyDestructed, Context);
5163
5164 case Stmt::BinaryConditionalOperatorClass:
5165 case Stmt::ConditionalOperatorClass:
5166 return VisitConditionalOperatorForTemporaries(
5167 E: cast<AbstractConditionalOperator>(Val: E), ExternallyDestructed, Context);
5168
5169 case Stmt::ImplicitCastExprClass:
5170 // For implicit cast we want ExternallyDestructed to be passed further.
5171 E = cast<CastExpr>(Val: E)->getSubExpr();
5172 goto tryAgain;
5173
5174 case Stmt::CXXFunctionalCastExprClass:
5175 // For functional cast we want ExternallyDestructed to be passed further.
5176 E = cast<CXXFunctionalCastExpr>(Val: E)->getSubExpr();
5177 goto tryAgain;
5178
5179 case Stmt::ConstantExprClass:
5180 E = cast<ConstantExpr>(Val: E)->getSubExpr();
5181 goto tryAgain;
5182
5183 case Stmt::ParenExprClass:
5184 E = cast<ParenExpr>(Val: E)->getSubExpr();
5185 goto tryAgain;
5186
5187 case Stmt::MaterializeTemporaryExprClass: {
5188 const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(Val: E);
5189 ExternallyDestructed = (MTE->getStorageDuration() != SD_FullExpression);
5190 if (BuildOpts.AddLifetime && !ExternallyDestructed)
5191 Context.track(MTE);
5192 SmallVector<const Expr *, 2> CommaLHSs;
5193 SmallVector<SubobjectAdjustment, 2> Adjustments;
5194 // Find the expression whose lifetime needs to be extended.
5195 E = const_cast<Expr *>(
5196 cast<MaterializeTemporaryExpr>(Val: E)
5197 ->getSubExpr()
5198 ->skipRValueSubobjectAdjustments(CommaLHS&: CommaLHSs, Adjustments));
5199 // Visit the skipped comma operator left-hand sides for other temporaries.
5200 for (const Expr *CommaLHS : CommaLHSs) {
5201 VisitForTemporaries(E: const_cast<Expr *>(CommaLHS),
5202 /*ExternallyDestructed=*/false, Context);
5203 }
5204 goto tryAgain;
5205 }
5206
5207 case Stmt::BlockExprClass:
5208 // Don't recurse into blocks; their subexpressions don't get evaluated
5209 // here.
5210 return Block;
5211
5212 case Stmt::LambdaExprClass: {
5213 // For lambda expressions, only recurse into the capture initializers,
5214 // and not the body.
5215 auto *LE = cast<LambdaExpr>(Val: E);
5216 CFGBlock *B = Block;
5217 for (Expr *Init : LE->capture_inits()) {
5218 if (Init) {
5219 if (CFGBlock *R = VisitForTemporaries(
5220 E: Init, /*ExternallyDestructed=*/true, Context))
5221 B = R;
5222 }
5223 }
5224 return B;
5225 }
5226
5227 case Stmt::StmtExprClass:
5228 // Don't recurse into statement expressions; any cleanups inside them
5229 // will be wrapped in their own ExprWithCleanups.
5230 return Block;
5231
5232 case Stmt::CXXDefaultArgExprClass:
5233 E = cast<CXXDefaultArgExpr>(Val: E)->getExpr();
5234 goto tryAgain;
5235
5236 case Stmt::CXXDefaultInitExprClass:
5237 E = cast<CXXDefaultInitExpr>(Val: E)->getExpr();
5238 goto tryAgain;
5239 }
5240}
5241
5242CFGBlock *CFGBuilder::VisitChildrenForTemporaries(Stmt *E,
5243 bool ExternallyDestructed,
5244 TempDtorContext &Context) {
5245 if (isa<LambdaExpr>(Val: E)) {
5246 // Do not visit the children of lambdas; they have their own CFGs.
5247 return Block;
5248 }
5249
5250 // When visiting children for destructors or lifetime markers we want to visit
5251 // them in reverse order that they will appear in the CFG. Because the CFG is
5252 // built bottom-up, this means we visit them in their natural order, which
5253 // reverses them in the CFG.
5254 CFGBlock *B = Block;
5255 for (Stmt *Child : E->children())
5256 if (Child)
5257 if (CFGBlock *R =
5258 VisitForTemporaries(E: Child, ExternallyDestructed, Context))
5259 B = R;
5260
5261 return B;
5262}
5263
5264CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaries(
5265 BinaryOperator *E, bool ExternallyDestructed, TempDtorContext &Context) {
5266 if (E->isCommaOp()) {
5267 // For the comma operator, the LHS expression is evaluated before the RHS
5268 // expression, so prepend temporary destructors for the LHS first.
5269 CFGBlock *LHSBlock = VisitForTemporaries(E: E->getLHS(), ExternallyDestructed: false, Context);
5270 CFGBlock *RHSBlock =
5271 VisitForTemporaries(E: E->getRHS(), ExternallyDestructed, Context);
5272 return RHSBlock ? RHSBlock : LHSBlock;
5273 }
5274
5275 if (E->isLogicalOp()) {
5276 VisitForTemporaries(E: E->getLHS(), ExternallyDestructed: false, Context);
5277 TryResult RHSExecuted = tryEvaluateBool(S: E->getLHS());
5278 if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr)
5279 RHSExecuted.negate();
5280
5281 // We do not know at CFG-construction time whether the right-hand-side was
5282 // executed, thus we add a branch node that depends on the temporary
5283 // constructor call.
5284 TempDtorContext RHSContext(
5285 bothKnownTrue(R1: Context.KnownExecuted, R2: RHSExecuted));
5286 VisitForTemporaries(E: E->getRHS(), ExternallyDestructed: false, Context&: RHSContext);
5287 InsertTempDecisionBlock(Context: RHSContext);
5288
5289 if (BuildOpts.AddLifetime)
5290 Context.CollectedMTEs.append(RHS: RHSContext.CollectedMTEs);
5291
5292 return Block;
5293 }
5294
5295 if (E->isAssignmentOp()) {
5296 // For assignment operators, the RHS expression is evaluated before the LHS
5297 // expression, so prepend temporary destructors for the RHS first.
5298 CFGBlock *RHSBlock = VisitForTemporaries(E: E->getRHS(), ExternallyDestructed: false, Context);
5299 CFGBlock *LHSBlock = VisitForTemporaries(E: E->getLHS(), ExternallyDestructed: false, Context);
5300 return LHSBlock ? LHSBlock : RHSBlock;
5301 }
5302
5303 // Any other operator is visited normally.
5304 return VisitChildrenForTemporaries(E, ExternallyDestructed, Context);
5305}
5306
5307CFGBlock *CFGBuilder::VisitCXXOperatorCallExprForTemporaryDtors(
5308 CXXOperatorCallExpr *E, TempDtorContext &Context) {
5309 if (E->isAssignmentOp()) {
5310 // For assignment operators, the RHS expression is evaluated before the LHS
5311 // expression, so prepend temporary destructors for the RHS first.
5312 CFGBlock *RHSBlock = VisitForTemporaries(E: E->getArg(Arg: 1), ExternallyDestructed: false, Context);
5313 CFGBlock *LHSBlock = VisitForTemporaries(E: E->getArg(Arg: 0), ExternallyDestructed: false, Context);
5314 return LHSBlock ? LHSBlock : RHSBlock;
5315 }
5316 return VisitChildrenForTemporaries(E, ExternallyDestructed: false, Context);
5317}
5318
5319CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
5320 CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context) {
5321 // First add destructors for temporaries in subexpression.
5322 // Because VisitCXXBindTemporaryExpr calls setDestructed:
5323 CFGBlock *B = VisitForTemporaries(E: E->getSubExpr(), ExternallyDestructed: true, Context);
5324 if (!ExternallyDestructed && BuildOpts.AddImplicitDtors &&
5325 BuildOpts.AddTemporaryDtors) {
5326 // If lifetime of temporary is not prolonged (by assigning to constant
5327 // reference) add destructor for it.
5328
5329 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
5330
5331 if (Dtor->getParent()->isAnyDestructorNoReturn()) {
5332 // If the destructor is marked as a no-return destructor, we need to
5333 // create a new block for the destructor which does not have as a
5334 // successor anything built thus far. Control won't flow out of this
5335 // block.
5336 if (B) Succ = B;
5337 Block = createNoReturnBlock();
5338 } else if (Context.needsTempDtorBranch()) {
5339 // If we need to introduce a branch, we add a new block that we will hook
5340 // up to a decision block later.
5341 if (B) Succ = B;
5342 Block = createBlock();
5343 } else {
5344 autoCreateBlock();
5345 }
5346 if (Context.needsTempDtorBranch()) {
5347 Context.setDecisionPoint(S: Succ, E);
5348 }
5349 appendTemporaryDtor(B: Block, E);
5350 B = Block;
5351 }
5352 return B;
5353}
5354
5355void CFGBuilder::InsertTempDecisionBlock(const TempDtorContext &Context,
5356 CFGBlock *FalseSucc) {
5357 if (!Context.TerminatorExpr) {
5358 // If no temporary was found, we do not need to insert a decision point.
5359 return;
5360 }
5361 assert(Context.TerminatorExpr);
5362 CFGBlock *Decision = createBlock(add_successor: false);
5363 Decision->setTerminator(CFGTerminator(Context.TerminatorExpr,
5364 CFGTerminator::TemporaryDtorsBranch));
5365 addSuccessor(B: Decision, S: Block, IsReachable: !Context.KnownExecuted.isFalse());
5366 addSuccessor(B: Decision, S: FalseSucc ? FalseSucc : Context.Succ,
5367 IsReachable: !Context.KnownExecuted.isTrue());
5368 Block = Decision;
5369}
5370
5371CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaries(
5372 AbstractConditionalOperator *E, bool ExternallyDestructed,
5373 TempDtorContext &Context) {
5374 VisitForTemporaries(E: E->getCond(), ExternallyDestructed: false, Context);
5375 CFGBlock *ConditionBlock = Block;
5376 CFGBlock *ConditionSucc = Succ;
5377 TryResult ConditionVal = tryEvaluateBool(S: E->getCond());
5378 TryResult NegatedVal = ConditionVal;
5379 if (NegatedVal.isKnown()) NegatedVal.negate();
5380
5381 TempDtorContext TrueContext(
5382 bothKnownTrue(R1: Context.KnownExecuted, R2: ConditionVal));
5383 VisitForTemporaries(E: E->getTrueExpr(), ExternallyDestructed, Context&: TrueContext);
5384 CFGBlock *TrueBlock = Block;
5385
5386 Block = ConditionBlock;
5387 Succ = ConditionSucc;
5388 TempDtorContext FalseContext(
5389 bothKnownTrue(R1: Context.KnownExecuted, R2: NegatedVal));
5390 VisitForTemporaries(E: E->getFalseExpr(), ExternallyDestructed, Context&: FalseContext);
5391
5392 if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) {
5393 InsertTempDecisionBlock(Context: FalseContext, FalseSucc: TrueBlock);
5394 } else if (TrueContext.TerminatorExpr) {
5395 Block = TrueBlock;
5396 InsertTempDecisionBlock(Context: TrueContext);
5397 } else {
5398 InsertTempDecisionBlock(Context: FalseContext);
5399 }
5400 if (BuildOpts.AddLifetime) {
5401 Context.CollectedMTEs.append(RHS: TrueContext.CollectedMTEs);
5402 Context.CollectedMTEs.append(RHS: FalseContext.CollectedMTEs);
5403 }
5404
5405 return Block;
5406}
5407
5408CFGBlock *CFGBuilder::VisitOMPExecutableDirective(OMPExecutableDirective *D,
5409 AddStmtChoice asc) {
5410 if (asc.alwaysAdd(builder&: *this, stmt: D)) {
5411 autoCreateBlock();
5412 appendStmt(B: Block, S: D);
5413 }
5414
5415 // Iterate over all used expression in clauses.
5416 CFGBlock *B = Block;
5417
5418 // Reverse the elements to process them in natural order. Iterators are not
5419 // bidirectional, so we need to create temp vector.
5420 SmallVector<Stmt *, 8> Used(
5421 OMPExecutableDirective::used_clauses_children(Clauses: D->clauses()));
5422 for (Stmt *S : llvm::reverse(C&: Used)) {
5423 assert(S && "Expected non-null used-in-clause child.");
5424 if (CFGBlock *R = Visit(S))
5425 B = R;
5426 }
5427 // Visit associated structured block if any.
5428 if (!D->isStandaloneDirective()) {
5429 Stmt *S = D->getRawStmt();
5430 if (!isa<CompoundStmt>(Val: S))
5431 addLocalScopeAndDtors(S);
5432 if (CFGBlock *R = addStmt(S))
5433 B = R;
5434 }
5435
5436 return B;
5437}
5438
5439/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
5440/// no successors or predecessors. If this is the first block created in the
5441/// CFG, it is automatically set to be the Entry and Exit of the CFG.
5442CFGBlock *CFG::createBlock() {
5443 bool first_block = begin() == end();
5444
5445 // Create the block.
5446 CFGBlock *Mem = new (getAllocator()) CFGBlock(NumBlockIDs++, BlkBVC, this);
5447 Blocks.push_back(Elt: Mem, C&: BlkBVC);
5448
5449 // If this is the first block, set it as the Entry and Exit.
5450 if (first_block)
5451 Entry = Exit = &back();
5452
5453 // Return the block.
5454 return &back();
5455}
5456
5457/// buildCFG - Constructs a CFG from an AST.
5458std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,
5459 ASTContext *C, const BuildOptions &BO) {
5460 llvm::TimeTraceScope TimeProfile("BuildCFG");
5461 CFGBuilder Builder(C, BO);
5462 return Builder.buildCFG(D, Statement);
5463}
5464
5465bool CFG::isLinear() const {
5466 // Quick path: if we only have the ENTRY block, the EXIT block, and some code
5467 // in between, then we have no room for control flow.
5468 if (size() <= 3)
5469 return true;
5470
5471 // Traverse the CFG until we find a branch.
5472 // TODO: While this should still be very fast,
5473 // maybe we should cache the answer.
5474 llvm::SmallPtrSet<const CFGBlock *, 4> Visited;
5475 const CFGBlock *B = Entry;
5476 while (B != Exit) {
5477 auto IteratorAndFlag = Visited.insert(Ptr: B);
5478 if (!IteratorAndFlag.second) {
5479 // We looped back to a block that we've already visited. Not linear.
5480 return false;
5481 }
5482
5483 // Iterate over reachable successors.
5484 const CFGBlock *FirstReachableB = nullptr;
5485 for (const CFGBlock::AdjacentBlock &AB : B->succs()) {
5486 if (!AB.isReachable())
5487 continue;
5488
5489 if (FirstReachableB == nullptr) {
5490 FirstReachableB = &*AB;
5491 } else {
5492 // We've encountered a branch. It's not a linear CFG.
5493 return false;
5494 }
5495 }
5496
5497 if (!FirstReachableB) {
5498 // We reached a dead end. EXIT is unreachable. This is linear enough.
5499 return true;
5500 }
5501
5502 // There's only one way to move forward. Proceed.
5503 B = FirstReachableB;
5504 }
5505
5506 // We reached EXIT and found no branches.
5507 return true;
5508}
5509
5510const CXXDestructorDecl *
5511CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
5512 switch (getKind()) {
5513 case CFGElement::Initializer:
5514 case CFGElement::NewAllocator:
5515 case CFGElement::LoopExit:
5516 case CFGElement::LifetimeEnds:
5517 case CFGElement::Statement:
5518 case CFGElement::Constructor:
5519 case CFGElement::CXXRecordTypedCall:
5520 case CFGElement::ScopeBegin:
5521 case CFGElement::ScopeEnd:
5522 case CFGElement::FullExprCleanup:
5523 case CFGElement::CleanupFunction:
5524 llvm_unreachable("getDestructorDecl should only be used with "
5525 "ImplicitDtors");
5526 case CFGElement::AutomaticObjectDtor: {
5527 const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();
5528 QualType ty = var->getType();
5529
5530 // FIXME: See CFGBuilder::addLocalScopeForVarDecl.
5531 //
5532 // Lifetime-extending constructs are handled here. This works for a single
5533 // temporary in an initializer expression.
5534 if (ty->isReferenceType()) {
5535 if (const Expr *Init = var->getInit()) {
5536 ty = getReferenceInitTemporaryType(Init);
5537 }
5538 }
5539
5540 while (const ArrayType *arrayType = astContext.getAsArrayType(T: ty)) {
5541 ty = arrayType->getElementType();
5542 }
5543
5544 // The situation when the type of the lifetime-extending reference
5545 // does not correspond to the type of the object is supposed
5546 // to be handled by now. In particular, 'ty' is now the unwrapped
5547 // record type.
5548 const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();
5549 assert(classDecl);
5550 return classDecl->getDestructor();
5551 }
5552 case CFGElement::DeleteDtor: {
5553 const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr();
5554 QualType DTy = DE->getDestroyedType();
5555 DTy = DTy.getNonReferenceType();
5556 const CXXRecordDecl *classDecl =
5557 astContext.getBaseElementType(QT: DTy)->getAsCXXRecordDecl();
5558 return classDecl->getDestructor();
5559 }
5560 case CFGElement::TemporaryDtor: {
5561 const CXXBindTemporaryExpr *bindExpr =
5562 castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
5563 const CXXTemporary *temp = bindExpr->getTemporary();
5564 return temp->getDestructor();
5565 }
5566 case CFGElement::MemberDtor: {
5567 const FieldDecl *field = castAs<CFGMemberDtor>().getFieldDecl();
5568 QualType ty = field->getType();
5569
5570 while (const ArrayType *arrayType = astContext.getAsArrayType(T: ty)) {
5571 ty = arrayType->getElementType();
5572 }
5573
5574 const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();
5575 assert(classDecl);
5576 return classDecl->getDestructor();
5577 }
5578 case CFGElement::BaseDtor:
5579 // Not yet supported.
5580 return nullptr;
5581 }
5582 llvm_unreachable("getKind() returned bogus value");
5583}
5584
5585//===----------------------------------------------------------------------===//
5586// CFGBlock operations.
5587//===----------------------------------------------------------------------===//
5588
5589CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable)
5590 : ReachableBlock(IsReachable ? B : nullptr),
5591 UnreachableBlock(!IsReachable ? B : nullptr,
5592 B && IsReachable ? AB_Normal : AB_Unreachable) {}
5593
5594CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock)
5595 : ReachableBlock(B),
5596 UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock,
5597 B == AlternateBlock ? AB_Alternate : AB_Normal) {}
5598
5599void CFGBlock::addSuccessor(AdjacentBlock Succ,
5600 BumpVectorContext &C) {
5601 if (CFGBlock *B = Succ.getReachableBlock())
5602 B->Preds.push_back(Elt: AdjacentBlock(this, Succ.isReachable()), C);
5603
5604 if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock())
5605 UnreachableB->Preds.push_back(Elt: AdjacentBlock(this, false), C);
5606
5607 Succs.push_back(Elt: Succ, C);
5608}
5609
5610bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
5611 const CFGBlock *From, const CFGBlock *To) {
5612 if (F.IgnoreNullPredecessors && !From)
5613 return true;
5614
5615 if (To && From && F.IgnoreDefaultsWithCoveredEnums) {
5616 // If the 'To' has no label or is labeled but the label isn't a
5617 // CaseStmt then filter this edge.
5618 if (const SwitchStmt *S =
5619 dyn_cast_or_null<SwitchStmt>(Val: From->getTerminatorStmt())) {
5620 if (S->isAllEnumCasesCovered()) {
5621 const Stmt *L = To->getLabel();
5622 if (!L || !isa<CaseStmt>(Val: L))
5623 return true;
5624 }
5625 }
5626 }
5627
5628 return false;
5629}
5630
5631//===----------------------------------------------------------------------===//
5632// CFG pretty printing
5633//===----------------------------------------------------------------------===//
5634
5635namespace {
5636
5637class StmtPrinterHelper : public PrinterHelper {
5638 using StmtMapTy = llvm::DenseMap<const Stmt *, std::pair<unsigned, unsigned>>;
5639 using DeclMapTy = llvm::DenseMap<const Decl *, std::pair<unsigned, unsigned>>;
5640
5641 StmtMapTy StmtMap;
5642 DeclMapTy DeclMap;
5643 signed currentBlock = 0;
5644 unsigned currStmt = 0;
5645 const LangOptions &LangOpts;
5646
5647public:
5648 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
5649 : LangOpts(LO) {
5650 if (!cfg)
5651 return;
5652 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
5653 unsigned j = 1;
5654 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
5655 BI != BEnd; ++BI, ++j ) {
5656 if (std::optional<CFGStmt> SE = BI->getAs<CFGStmt>()) {
5657 const Stmt *stmt= SE->getStmt();
5658 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
5659 StmtMap[stmt] = P;
5660
5661 switch (stmt->getStmtClass()) {
5662 case Stmt::DeclStmtClass:
5663 DeclMap[cast<DeclStmt>(Val: stmt)->getSingleDecl()] = P;
5664 break;
5665 case Stmt::IfStmtClass: {
5666 const VarDecl *var = cast<IfStmt>(Val: stmt)->getConditionVariable();
5667 if (var)
5668 DeclMap[var] = P;
5669 break;
5670 }
5671 case Stmt::ForStmtClass: {
5672 const VarDecl *var = cast<ForStmt>(Val: stmt)->getConditionVariable();
5673 if (var)
5674 DeclMap[var] = P;
5675 break;
5676 }
5677 case Stmt::WhileStmtClass: {
5678 const VarDecl *var =
5679 cast<WhileStmt>(Val: stmt)->getConditionVariable();
5680 if (var)
5681 DeclMap[var] = P;
5682 break;
5683 }
5684 case Stmt::SwitchStmtClass: {
5685 const VarDecl *var =
5686 cast<SwitchStmt>(Val: stmt)->getConditionVariable();
5687 if (var)
5688 DeclMap[var] = P;
5689 break;
5690 }
5691 case Stmt::CXXCatchStmtClass: {
5692 const VarDecl *var =
5693 cast<CXXCatchStmt>(Val: stmt)->getExceptionDecl();
5694 if (var)
5695 DeclMap[var] = P;
5696 break;
5697 }
5698 default:
5699 break;
5700 }
5701 }
5702 }
5703 }
5704 }
5705
5706 ~StmtPrinterHelper() override = default;
5707
5708 const LangOptions &getLangOpts() const { return LangOpts; }
5709 void setBlockID(signed i) { currentBlock = i; }
5710 void setStmtID(unsigned i) { currStmt = i; }
5711
5712 bool handledStmt(Stmt *S, raw_ostream &OS) override {
5713 StmtMapTy::iterator I = StmtMap.find(Val: S);
5714
5715 if (I == StmtMap.end())
5716 return false;
5717
5718 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
5719 && I->second.second == currStmt) {
5720 return false;
5721 }
5722
5723 OS << "[B" << I->second.first << "." << I->second.second << "]";
5724 return true;
5725 }
5726
5727 bool handleDecl(const Decl *D, raw_ostream &OS) {
5728 DeclMapTy::iterator I = DeclMap.find(Val: D);
5729
5730 if (I == DeclMap.end()) {
5731 // ParmVarDecls are not declared in the CFG itself, so they do not appear
5732 // in DeclMap.
5733 if (auto *PVD = dyn_cast_or_null<ParmVarDecl>(Val: D)) {
5734 OS << "[Parm: " << PVD->getNameAsString() << "]";
5735 return true;
5736 }
5737 return false;
5738 }
5739
5740 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
5741 && I->second.second == currStmt) {
5742 return false;
5743 }
5744
5745 OS << "[B" << I->second.first << "." << I->second.second << "]";
5746 return true;
5747 }
5748};
5749
5750class CFGBlockTerminatorPrint
5751 : public StmtVisitor<CFGBlockTerminatorPrint,void> {
5752 raw_ostream &OS;
5753 StmtPrinterHelper* Helper;
5754 PrintingPolicy Policy;
5755
5756public:
5757 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
5758 const PrintingPolicy &Policy)
5759 : OS(os), Helper(helper), Policy(Policy) {
5760 this->Policy.IncludeNewlines = false;
5761 }
5762
5763 void VisitIfStmt(IfStmt *I) {
5764 OS << "if ";
5765 if (Stmt *C = I->getCond())
5766 C->printPretty(OS, Helper, Policy);
5767 }
5768
5769 // Default case.
5770 void VisitStmt(Stmt *Terminator) {
5771 Terminator->printPretty(OS, Helper, Policy);
5772 }
5773
5774 void VisitDeclStmt(DeclStmt *DS) {
5775 VarDecl *VD = cast<VarDecl>(Val: DS->getSingleDecl());
5776 OS << "static init " << VD->getName();
5777 }
5778
5779 void VisitForStmt(ForStmt *F) {
5780 OS << "for (" ;
5781 if (F->getInit())
5782 OS << "...";
5783 OS << "; ";
5784 if (Stmt *C = F->getCond())
5785 C->printPretty(OS, Helper, Policy);
5786 OS << "; ";
5787 if (F->getInc())
5788 OS << "...";
5789 OS << ")";
5790 }
5791
5792 void VisitWhileStmt(WhileStmt *W) {
5793 OS << "while " ;
5794 if (Stmt *C = W->getCond())
5795 C->printPretty(OS, Helper, Policy);
5796 }
5797
5798 void VisitDoStmt(DoStmt *D) {
5799 OS << "do ... while ";
5800 if (Stmt *C = D->getCond())
5801 C->printPretty(OS, Helper, Policy);
5802 }
5803
5804 void VisitSwitchStmt(SwitchStmt *Terminator) {
5805 OS << "switch ";
5806 Terminator->getCond()->printPretty(OS, Helper, Policy);
5807 }
5808
5809 void VisitCXXTryStmt(CXXTryStmt *) { OS << "try ..."; }
5810
5811 void VisitObjCAtTryStmt(ObjCAtTryStmt *) { OS << "@try ..."; }
5812
5813 void VisitSEHTryStmt(SEHTryStmt *CS) { OS << "__try ..."; }
5814
5815 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
5816 if (Stmt *Cond = C->getCond())
5817 Cond->printPretty(OS, Helper, Policy);
5818 OS << " ? ... : ...";
5819 }
5820
5821 void VisitChooseExpr(ChooseExpr *C) {
5822 OS << "__builtin_choose_expr( ";
5823 if (Stmt *Cond = C->getCond())
5824 Cond->printPretty(OS, Helper, Policy);
5825 OS << " )";
5826 }
5827
5828 void VisitIndirectGotoStmt(IndirectGotoStmt *I) {
5829 OS << "goto *";
5830 if (Stmt *T = I->getTarget())
5831 T->printPretty(OS, Helper, Policy);
5832 }
5833
5834 void VisitBinaryOperator(BinaryOperator* B) {
5835 if (!B->isLogicalOp()) {
5836 VisitExpr(E: B);
5837 return;
5838 }
5839
5840 if (B->getLHS())
5841 B->getLHS()->printPretty(OS, Helper, Policy);
5842
5843 switch (B->getOpcode()) {
5844 case BO_LOr:
5845 OS << " || ...";
5846 return;
5847 case BO_LAnd:
5848 OS << " && ...";
5849 return;
5850 default:
5851 llvm_unreachable("Invalid logical operator.");
5852 }
5853 }
5854
5855 void VisitExpr(Expr *E) {
5856 E->printPretty(OS, Helper, Policy);
5857 }
5858
5859public:
5860 void print(CFGTerminator T) {
5861 switch (T.getKind()) {
5862 case CFGTerminator::StmtBranch:
5863 Visit(S: T.getStmt());
5864 break;
5865 case CFGTerminator::TemporaryDtorsBranch:
5866 OS << "(Temp Dtor) ";
5867 Visit(S: T.getStmt());
5868 break;
5869 case CFGTerminator::VirtualBaseBranch:
5870 OS << "(See if most derived ctor has already initialized vbases)";
5871 break;
5872 }
5873 }
5874};
5875
5876} // namespace
5877
5878static void print_initializer(raw_ostream &OS, StmtPrinterHelper &Helper,
5879 const CXXCtorInitializer *I) {
5880 if (I->isBaseInitializer())
5881 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
5882 else if (I->isDelegatingInitializer())
5883 OS << I->getTypeSourceInfo()->getType()->getAsCXXRecordDecl()->getName();
5884 else
5885 OS << I->getAnyMember()->getName();
5886 OS << "(";
5887 if (Expr *IE = I->getInit())
5888 IE->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
5889 OS << ")";
5890
5891 if (I->isBaseInitializer())
5892 OS << " (Base initializer)";
5893 else if (I->isDelegatingInitializer())
5894 OS << " (Delegating initializer)";
5895 else
5896 OS << " (Member initializer)";
5897}
5898
5899static void print_construction_context(raw_ostream &OS,
5900 StmtPrinterHelper &Helper,
5901 const ConstructionContext *CC) {
5902 SmallVector<const Stmt *, 3> Stmts;
5903 switch (CC->getKind()) {
5904 case ConstructionContext::SimpleConstructorInitializerKind: {
5905 OS << ", ";
5906 const auto *SICC = cast<SimpleConstructorInitializerConstructionContext>(Val: CC);
5907 print_initializer(OS, Helper, I: SICC->getCXXCtorInitializer());
5908 return;
5909 }
5910 case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind: {
5911 OS << ", ";
5912 const auto *CICC =
5913 cast<CXX17ElidedCopyConstructorInitializerConstructionContext>(Val: CC);
5914 print_initializer(OS, Helper, I: CICC->getCXXCtorInitializer());
5915 Stmts.push_back(Elt: CICC->getCXXBindTemporaryExpr());
5916 break;
5917 }
5918 case ConstructionContext::SimpleVariableKind: {
5919 const auto *SDSCC = cast<SimpleVariableConstructionContext>(Val: CC);
5920 Stmts.push_back(Elt: SDSCC->getDeclStmt());
5921 break;
5922 }
5923 case ConstructionContext::CXX17ElidedCopyVariableKind: {
5924 const auto *CDSCC = cast<CXX17ElidedCopyVariableConstructionContext>(Val: CC);
5925 Stmts.push_back(Elt: CDSCC->getDeclStmt());
5926 Stmts.push_back(Elt: CDSCC->getCXXBindTemporaryExpr());
5927 break;
5928 }
5929 case ConstructionContext::NewAllocatedObjectKind: {
5930 const auto *NECC = cast<NewAllocatedObjectConstructionContext>(Val: CC);
5931 Stmts.push_back(Elt: NECC->getCXXNewExpr());
5932 break;
5933 }
5934 case ConstructionContext::SimpleReturnedValueKind: {
5935 const auto *RSCC = cast<SimpleReturnedValueConstructionContext>(Val: CC);
5936 Stmts.push_back(Elt: RSCC->getReturnStmt());
5937 break;
5938 }
5939 case ConstructionContext::CXX17ElidedCopyReturnedValueKind: {
5940 const auto *RSCC =
5941 cast<CXX17ElidedCopyReturnedValueConstructionContext>(Val: CC);
5942 Stmts.push_back(Elt: RSCC->getReturnStmt());
5943 Stmts.push_back(Elt: RSCC->getCXXBindTemporaryExpr());
5944 break;
5945 }
5946 case ConstructionContext::SimpleTemporaryObjectKind: {
5947 const auto *TOCC = cast<SimpleTemporaryObjectConstructionContext>(Val: CC);
5948 Stmts.push_back(Elt: TOCC->getCXXBindTemporaryExpr());
5949 Stmts.push_back(Elt: TOCC->getMaterializedTemporaryExpr());
5950 break;
5951 }
5952 case ConstructionContext::ElidedTemporaryObjectKind: {
5953 const auto *TOCC = cast<ElidedTemporaryObjectConstructionContext>(Val: CC);
5954 Stmts.push_back(Elt: TOCC->getCXXBindTemporaryExpr());
5955 Stmts.push_back(Elt: TOCC->getMaterializedTemporaryExpr());
5956 Stmts.push_back(Elt: TOCC->getConstructorAfterElision());
5957 break;
5958 }
5959 case ConstructionContext::LambdaCaptureKind: {
5960 const auto *LCC = cast<LambdaCaptureConstructionContext>(Val: CC);
5961 Helper.handledStmt(S: const_cast<LambdaExpr *>(LCC->getLambdaExpr()), OS);
5962 OS << "+" << LCC->getIndex();
5963 return;
5964 }
5965 case ConstructionContext::ArgumentKind: {
5966 const auto *ACC = cast<ArgumentConstructionContext>(Val: CC);
5967 if (const Stmt *BTE = ACC->getCXXBindTemporaryExpr()) {
5968 OS << ", ";
5969 Helper.handledStmt(S: const_cast<Stmt *>(BTE), OS);
5970 }
5971 OS << ", ";
5972 Helper.handledStmt(S: const_cast<Expr *>(ACC->getCallLikeExpr()), OS);
5973 OS << "+" << ACC->getIndex();
5974 return;
5975 }
5976 }
5977 for (auto I: Stmts)
5978 if (I) {
5979 OS << ", ";
5980 Helper.handledStmt(S: const_cast<Stmt *>(I), OS);
5981 }
5982}
5983
5984static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
5985 const CFGElement &E, bool TerminateWithNewLine = true);
5986
5987void CFGElement::dumpToStream(llvm::raw_ostream &OS,
5988 bool TerminateWithNewLine) const {
5989 LangOptions LangOpts;
5990 StmtPrinterHelper Helper(nullptr, LangOpts);
5991 print_elem(OS, Helper, E: *this, TerminateWithNewLine);
5992}
5993
5994static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
5995 const CFGElement &E, bool TerminateWithNewLine) {
5996 switch (E.getKind()) {
5997 case CFGElement::Kind::Statement:
5998 case CFGElement::Kind::CXXRecordTypedCall:
5999 case CFGElement::Kind::Constructor: {
6000 CFGStmt CS = E.castAs<CFGStmt>();
6001 const Stmt *S = CS.getStmt();
6002 assert(S != nullptr && "Expecting non-null Stmt");
6003
6004 // special printing for statement-expressions.
6005 if (const StmtExpr *SE = dyn_cast<StmtExpr>(Val: S)) {
6006 const CompoundStmt *Sub = SE->getSubStmt();
6007
6008 auto Children = Sub->children();
6009 if (Children.begin() != Children.end()) {
6010 OS << "({ ... ; ";
6011 Helper.handledStmt(S: *SE->getSubStmt()->body_rbegin(),OS);
6012 OS << " })";
6013 if (TerminateWithNewLine)
6014 OS << '\n';
6015 return;
6016 }
6017 }
6018 // special printing for comma expressions.
6019 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(Val: S)) {
6020 if (B->getOpcode() == BO_Comma) {
6021 OS << "... , ";
6022 Helper.handledStmt(S: B->getRHS(),OS);
6023 if (TerminateWithNewLine)
6024 OS << '\n';
6025 return;
6026 }
6027 }
6028 S->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
6029
6030 if (auto VTC = E.getAs<CFGCXXRecordTypedCall>()) {
6031 if (isa<CXXOperatorCallExpr>(Val: S))
6032 OS << " (OperatorCall)";
6033 OS << " (CXXRecordTypedCall";
6034 print_construction_context(OS, Helper, CC: VTC->getConstructionContext());
6035 OS << ")";
6036 } else if (isa<CXXOperatorCallExpr>(Val: S)) {
6037 OS << " (OperatorCall)";
6038 } else if (isa<CXXBindTemporaryExpr>(Val: S)) {
6039 OS << " (BindTemporary)";
6040 } else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(Val: S)) {
6041 OS << " (CXXConstructExpr";
6042 if (std::optional<CFGConstructor> CE = E.getAs<CFGConstructor>()) {
6043 print_construction_context(OS, Helper, CC: CE->getConstructionContext());
6044 }
6045 OS << ", " << CCE->getType() << ")";
6046 } else if (const CastExpr *CE = dyn_cast<CastExpr>(Val: S)) {
6047 OS << " (" << CE->getStmtClassName() << ", " << CE->getCastKindName()
6048 << ", " << CE->getType() << ")";
6049 }
6050
6051 // Expressions need a newline.
6052 if (isa<Expr>(Val: S) && TerminateWithNewLine)
6053 OS << '\n';
6054
6055 return;
6056 }
6057
6058 case CFGElement::Kind::Initializer:
6059 print_initializer(OS, Helper, I: E.castAs<CFGInitializer>().getInitializer());
6060 break;
6061
6062 case CFGElement::Kind::AutomaticObjectDtor: {
6063 CFGAutomaticObjDtor DE = E.castAs<CFGAutomaticObjDtor>();
6064 const VarDecl *VD = DE.getVarDecl();
6065 Helper.handleDecl(D: VD, OS);
6066
6067 QualType T = VD->getType();
6068 if (T->isReferenceType())
6069 T = getReferenceInitTemporaryType(Init: VD->getInit(), FoundMTE: nullptr);
6070
6071 OS << ".~";
6072 T.getUnqualifiedType().print(OS, Policy: PrintingPolicy(Helper.getLangOpts()));
6073 OS << "() (Implicit destructor)";
6074 break;
6075 }
6076
6077 case CFGElement::Kind::CleanupFunction:
6078 OS << "CleanupFunction ("
6079 << E.castAs<CFGCleanupFunction>().getFunctionDecl()->getName() << ")";
6080 break;
6081
6082 case CFGElement::Kind::LifetimeEnds:
6083 Helper.handleDecl(D: E.castAs<CFGLifetimeEnds>().getVarDecl(), OS);
6084 OS << " (Lifetime ends)";
6085 break;
6086
6087 case CFGElement::Kind::FullExprCleanup: {
6088 auto MTEs = E.castAs<CFGFullExprCleanup>().getExpiringMTEs();
6089 size_t MTECount = MTEs.size();
6090 OS << "(FullExprCleanup collected " << MTECount
6091 << (MTECount > 1 ? " MTEs: " : " MTE: ");
6092 bool FirstMTE = true;
6093 for (const MaterializeTemporaryExpr *MTE : MTEs) {
6094 if (!FirstMTE)
6095 OS << ", ";
6096 if (!Helper.handledStmt(S: MTE->getSubExpr(), OS)) {
6097 PrintingPolicy Policy{Helper.getLangOpts()};
6098 Policy.IncludeNewlines = false;
6099 // Pretty print the sub-expresion as a fallback
6100 MTE->printPretty(OS, Helper: &Helper, Policy);
6101 }
6102 FirstMTE = false;
6103 }
6104 OS << ")";
6105 break;
6106 }
6107
6108 case CFGElement::Kind::LoopExit:
6109 OS << E.castAs<CFGLoopExit>().getLoopStmt()->getStmtClassName()
6110 << " (LoopExit)";
6111 break;
6112
6113 case CFGElement::Kind::ScopeBegin:
6114 OS << "CFGScopeBegin(";
6115 if (const VarDecl *VD = E.castAs<CFGScopeBegin>().getVarDecl())
6116 OS << VD->getQualifiedNameAsString();
6117 OS << ")";
6118 break;
6119
6120 case CFGElement::Kind::ScopeEnd:
6121 OS << "CFGScopeEnd(";
6122 if (const VarDecl *VD = E.castAs<CFGScopeEnd>().getVarDecl())
6123 OS << VD->getQualifiedNameAsString();
6124 OS << ")";
6125 break;
6126
6127 case CFGElement::Kind::NewAllocator:
6128 OS << "CFGNewAllocator(";
6129 if (const CXXNewExpr *AllocExpr = E.castAs<CFGNewAllocator>().getAllocatorExpr())
6130 AllocExpr->getType().print(OS, Policy: PrintingPolicy(Helper.getLangOpts()));
6131 OS << ")";
6132 break;
6133
6134 case CFGElement::Kind::DeleteDtor: {
6135 CFGDeleteDtor DE = E.castAs<CFGDeleteDtor>();
6136 const CXXRecordDecl *RD = DE.getCXXRecordDecl();
6137 if (!RD)
6138 return;
6139 CXXDeleteExpr *DelExpr =
6140 const_cast<CXXDeleteExpr*>(DE.getDeleteExpr());
6141 Helper.handledStmt(S: cast<Stmt>(Val: DelExpr->getArgument()), OS);
6142 OS << "->~" << RD->getName().str() << "()";
6143 OS << " (Implicit destructor)";
6144 break;
6145 }
6146
6147 case CFGElement::Kind::BaseDtor: {
6148 const CXXBaseSpecifier *BS = E.castAs<CFGBaseDtor>().getBaseSpecifier();
6149 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
6150 OS << " (Base object destructor)";
6151 break;
6152 }
6153
6154 case CFGElement::Kind::MemberDtor: {
6155 const FieldDecl *FD = E.castAs<CFGMemberDtor>().getFieldDecl();
6156 const Type *T = FD->getType()->getBaseElementTypeUnsafe();
6157 OS << "this->" << FD->getName();
6158 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
6159 OS << " (Member object destructor)";
6160 break;
6161 }
6162
6163 case CFGElement::Kind::TemporaryDtor: {
6164 const CXXBindTemporaryExpr *BT =
6165 E.castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
6166 OS << "~";
6167 BT->getType().print(OS, Policy: PrintingPolicy(Helper.getLangOpts()));
6168 OS << "() (Temporary object destructor)";
6169 break;
6170 }
6171 }
6172 if (TerminateWithNewLine)
6173 OS << '\n';
6174}
6175
6176static void print_block(raw_ostream &OS, const CFG* cfg,
6177 const CFGBlock &B,
6178 StmtPrinterHelper &Helper, bool print_edges,
6179 bool ShowColors) {
6180 Helper.setBlockID(B.getBlockID());
6181
6182 // Print the header.
6183 if (ShowColors)
6184 OS.changeColor(Color: raw_ostream::YELLOW, Bold: true);
6185
6186 OS << "\n [B" << B.getBlockID();
6187
6188 if (&B == &cfg->getEntry())
6189 OS << " (ENTRY)]\n";
6190 else if (&B == &cfg->getExit())
6191 OS << " (EXIT)]\n";
6192 else if (&B == cfg->getIndirectGotoBlock())
6193 OS << " (INDIRECT GOTO DISPATCH)]\n";
6194 else if (B.hasNoReturnElement())
6195 OS << " (NORETURN)]\n";
6196 else
6197 OS << "]\n";
6198
6199 if (ShowColors)
6200 OS.resetColor();
6201
6202 // Print the label of this block.
6203 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {
6204 if (print_edges)
6205 OS << " ";
6206
6207 if (LabelStmt *L = dyn_cast<LabelStmt>(Val: Label))
6208 OS << L->getName();
6209 else if (CaseStmt *C = dyn_cast<CaseStmt>(Val: Label)) {
6210 OS << "case ";
6211 if (const Expr *LHS = C->getLHS())
6212 LHS->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
6213 if (const Expr *RHS = C->getRHS()) {
6214 OS << " ... ";
6215 RHS->printPretty(OS, Helper: &Helper, Policy: PrintingPolicy(Helper.getLangOpts()));
6216 }
6217 } else if (isa<DefaultStmt>(Val: Label))
6218 OS << "default";
6219 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Val: Label)) {
6220 OS << "catch (";
6221 if (const VarDecl *ED = CS->getExceptionDecl())
6222 ED->print(Out&: OS, Policy: PrintingPolicy(Helper.getLangOpts()), Indentation: 0);
6223 else
6224 OS << "...";
6225 OS << ")";
6226 } else if (ObjCAtCatchStmt *CS = dyn_cast<ObjCAtCatchStmt>(Val: Label)) {
6227 OS << "@catch (";
6228 if (const VarDecl *PD = CS->getCatchParamDecl())
6229 PD->print(Out&: OS, Policy: PrintingPolicy(Helper.getLangOpts()), Indentation: 0);
6230 else
6231 OS << "...";
6232 OS << ")";
6233 } else if (SEHExceptStmt *ES = dyn_cast<SEHExceptStmt>(Val: Label)) {
6234 OS << "__except (";
6235 ES->getFilterExpr()->printPretty(OS, Helper: &Helper,
6236 Policy: PrintingPolicy(Helper.getLangOpts()), Indentation: 0);
6237 OS << ")";
6238 } else
6239 llvm_unreachable("Invalid label statement in CFGBlock.");
6240
6241 OS << ":\n";
6242 }
6243
6244 // Iterate through the statements in the block and print them.
6245 unsigned j = 1;
6246
6247 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
6248 I != E ; ++I, ++j ) {
6249 // Print the statement # in the basic block and the statement itself.
6250 if (print_edges)
6251 OS << " ";
6252
6253 OS << llvm::format(Fmt: "%3d", Vals: j) << ": ";
6254
6255 Helper.setStmtID(j);
6256
6257 print_elem(OS, Helper, E: *I);
6258 }
6259
6260 // Print the terminator of this block.
6261 if (B.getTerminator().isValid()) {
6262 if (ShowColors)
6263 OS.changeColor(Color: raw_ostream::GREEN);
6264
6265 OS << " T: ";
6266
6267 Helper.setBlockID(-1);
6268
6269 PrintingPolicy PP(Helper.getLangOpts());
6270 CFGBlockTerminatorPrint TPrinter(OS, &Helper, PP);
6271 TPrinter.print(T: B.getTerminator());
6272 OS << '\n';
6273
6274 if (ShowColors)
6275 OS.resetColor();
6276 }
6277
6278 if (print_edges) {
6279 // Print the predecessors of this block.
6280 if (!B.pred_empty()) {
6281 const raw_ostream::Colors Color = raw_ostream::BLUE;
6282 if (ShowColors)
6283 OS.changeColor(Color);
6284 OS << " Preds " ;
6285 if (ShowColors)
6286 OS.resetColor();
6287 OS << '(' << B.pred_size() << "):";
6288 unsigned i = 0;
6289
6290 if (ShowColors)
6291 OS.changeColor(Color);
6292
6293 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
6294 I != E; ++I, ++i) {
6295 if (i % 10 == 8)
6296 OS << "\n ";
6297
6298 CFGBlock *B = *I;
6299 bool Reachable = true;
6300 if (!B) {
6301 Reachable = false;
6302 B = I->getPossiblyUnreachableBlock();
6303 }
6304
6305 OS << " B" << B->getBlockID();
6306 if (!Reachable)
6307 OS << "(Unreachable)";
6308 }
6309
6310 if (ShowColors)
6311 OS.resetColor();
6312
6313 OS << '\n';
6314 }
6315
6316 // Print the successors of this block.
6317 if (!B.succ_empty()) {
6318 const raw_ostream::Colors Color = raw_ostream::MAGENTA;
6319 if (ShowColors)
6320 OS.changeColor(Color);
6321 OS << " Succs ";
6322 if (ShowColors)
6323 OS.resetColor();
6324 OS << '(' << B.succ_size() << "):";
6325 unsigned i = 0;
6326
6327 if (ShowColors)
6328 OS.changeColor(Color);
6329
6330 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
6331 I != E; ++I, ++i) {
6332 if (i % 10 == 8)
6333 OS << "\n ";
6334
6335 CFGBlock *B = *I;
6336
6337 bool Reachable = true;
6338 if (!B) {
6339 Reachable = false;
6340 B = I->getPossiblyUnreachableBlock();
6341 }
6342
6343 if (B) {
6344 OS << " B" << B->getBlockID();
6345 if (!Reachable)
6346 OS << "(Unreachable)";
6347 }
6348 else {
6349 OS << " NULL";
6350 }
6351 }
6352
6353 if (ShowColors)
6354 OS.resetColor();
6355 OS << '\n';
6356 }
6357 }
6358}
6359
6360/// dump - A simple pretty printer of a CFG that outputs to stderr.
6361void CFG::dump(const LangOptions &LO, bool ShowColors) const {
6362 print(OS&: llvm::errs(), LO, ShowColors);
6363}
6364
6365/// print - A simple pretty printer of a CFG that outputs to an ostream.
6366void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
6367 StmtPrinterHelper Helper(this, LO);
6368
6369 // Print the entry block.
6370 print_block(OS, cfg: this, B: getEntry(), Helper, print_edges: true, ShowColors);
6371
6372 // Iterate through the CFGBlocks and print them one by one.
6373 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
6374 // Skip the entry block, because we already printed it.
6375 if (&(**I) == &getEntry() || &(**I) == &getExit())
6376 continue;
6377
6378 print_block(OS, cfg: this, B: **I, Helper, print_edges: true, ShowColors);
6379 }
6380
6381 // Print the exit block.
6382 print_block(OS, cfg: this, B: getExit(), Helper, print_edges: true, ShowColors);
6383 OS << '\n';
6384 OS.flush();
6385}
6386
6387size_t CFGBlock::getIndexInCFG() const {
6388 return llvm::find(Range&: *getParent(), Val: this) - getParent()->begin();
6389}
6390
6391/// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
6392void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
6393 bool ShowColors) const {
6394 print(OS&: llvm::errs(), cfg, LO, ShowColors);
6395}
6396
6397LLVM_DUMP_METHOD void CFGBlock::dump() const {
6398 dump(cfg: getParent(), LO: LangOptions(), ShowColors: false);
6399}
6400
6401/// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
6402/// Generally this will only be called from CFG::print.
6403void CFGBlock::print(raw_ostream &OS, const CFG* cfg,
6404 const LangOptions &LO, bool ShowColors) const {
6405 StmtPrinterHelper Helper(cfg, LO);
6406 print_block(OS, cfg, B: *this, Helper, print_edges: true, ShowColors);
6407 OS << '\n';
6408}
6409
6410/// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
6411void CFGBlock::printTerminator(raw_ostream &OS,
6412 const LangOptions &LO) const {
6413 CFGBlockTerminatorPrint TPrinter(OS, nullptr, PrintingPolicy(LO));
6414 TPrinter.print(T: getTerminator());
6415}
6416
6417/// printTerminatorJson - Pretty-prints the terminator in JSON format.
6418void CFGBlock::printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
6419 bool AddQuotes) const {
6420 std::string Buf;
6421 llvm::raw_string_ostream TempOut(Buf);
6422
6423 printTerminator(OS&: TempOut, LO);
6424
6425 Out << JsonFormat(RawSR: Buf, AddQuotes);
6426}
6427
6428// Returns true if by simply looking at the block, we can be sure that it
6429// results in a sink during analysis. This is useful to know when the analysis
6430// was interrupted, and we try to figure out if it would sink eventually.
6431// There may be many more reasons why a sink would appear during analysis
6432// (eg. checkers may generate sinks arbitrarily), but here we only consider
6433// sinks that would be obvious by looking at the CFG.
6434static bool isImmediateSinkBlock(const CFGBlock *Blk) {
6435 if (Blk->hasNoReturnElement())
6436 return true;
6437
6438 // FIXME: Throw-expressions are currently generating sinks during analysis:
6439 // they're not supported yet, and also often used for actually terminating
6440 // the program. So we should treat them as sinks in this analysis as well,
6441 // at least for now, but once we have better support for exceptions,
6442 // we'd need to carefully handle the case when the throw is being
6443 // immediately caught.
6444 if (llvm::any_of(Range: *Blk, P: [](const CFGElement &Elm) {
6445 if (std::optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())
6446 if (isa<CXXThrowExpr>(Val: StmtElm->getStmt()))
6447 return true;
6448 return false;
6449 }))
6450 return true;
6451
6452 return false;
6453}
6454
6455bool CFGBlock::isInevitablySinking() const {
6456 const CFG &Cfg = *getParent();
6457
6458 const CFGBlock *StartBlk = this;
6459 if (isImmediateSinkBlock(Blk: StartBlk))
6460 return true;
6461
6462 llvm::SmallVector<const CFGBlock *, 32> DFSWorkList;
6463 llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
6464
6465 DFSWorkList.push_back(Elt: StartBlk);
6466 while (!DFSWorkList.empty()) {
6467 const CFGBlock *Blk = DFSWorkList.pop_back_val();
6468 Visited.insert(Ptr: Blk);
6469
6470 // If at least one path reaches the CFG exit, it means that control is
6471 // returned to the caller. For now, say that we are not sure what
6472 // happens next. If necessary, this can be improved to analyze
6473 // the parent StackFrame's call site in a similar manner.
6474 if (Blk == &Cfg.getExit())
6475 return false;
6476
6477 for (const auto &Succ : Blk->succs()) {
6478 if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {
6479 if (!isImmediateSinkBlock(Blk: SuccBlk) && !Visited.count(Ptr: SuccBlk)) {
6480 // If the block has reachable child blocks that aren't no-return,
6481 // add them to the worklist.
6482 DFSWorkList.push_back(Elt: SuccBlk);
6483 }
6484 }
6485 }
6486 }
6487
6488 // Nothing reached the exit. It can only mean one thing: there's no return.
6489 return true;
6490}
6491
6492const Expr *CFGBlock::getLastCondition() const {
6493 // If the terminator is a temporary dtor or a virtual base, etc, we can't
6494 // retrieve a meaningful condition, bail out.
6495 if (Terminator.getKind() != CFGTerminator::StmtBranch)
6496 return nullptr;
6497
6498 // Also, if this method was called on a block that doesn't have 2 successors,
6499 // this block doesn't have retrievable condition.
6500 if (succ_size() < 2)
6501 return nullptr;
6502
6503 // FIXME: Is there a better condition expression we can return in this case?
6504 if (size() == 0)
6505 return nullptr;
6506
6507 auto StmtElem = rbegin()->getAs<CFGStmt>();
6508 if (!StmtElem)
6509 return nullptr;
6510
6511 const Stmt *Cond = StmtElem->getStmt();
6512 if (isa<ObjCForCollectionStmt>(Val: Cond) || isa<DeclStmt>(Val: Cond))
6513 return nullptr;
6514
6515 // Only ObjCForCollectionStmt is known not to be a non-Expr terminator, hence
6516 // the cast<>.
6517 return cast<Expr>(Val: Cond)->IgnoreParens();
6518}
6519
6520const Stmt *CFGBlock::getTerminatorCondition(bool StripParens) const {
6521 const Stmt *Terminator = getTerminatorStmt();
6522 if (!Terminator)
6523 return nullptr;
6524
6525 const Expr *E = nullptr;
6526
6527 switch (Terminator->getStmtClass()) {
6528 default:
6529 break;
6530
6531 case Stmt::CXXForRangeStmtClass:
6532 E = cast<CXXForRangeStmt>(Val: Terminator)->getCond();
6533 break;
6534
6535 case Stmt::ForStmtClass:
6536 E = cast<ForStmt>(Val: Terminator)->getCond();
6537 break;
6538
6539 case Stmt::WhileStmtClass:
6540 E = cast<WhileStmt>(Val: Terminator)->getCond();
6541 break;
6542
6543 case Stmt::DoStmtClass:
6544 E = cast<DoStmt>(Val: Terminator)->getCond();
6545 break;
6546
6547 case Stmt::IfStmtClass:
6548 E = cast<IfStmt>(Val: Terminator)->getCond();
6549 break;
6550
6551 case Stmt::ChooseExprClass:
6552 E = cast<ChooseExpr>(Val: Terminator)->getCond();
6553 break;
6554
6555 case Stmt::IndirectGotoStmtClass:
6556 E = cast<IndirectGotoStmt>(Val: Terminator)->getTarget();
6557 break;
6558
6559 case Stmt::SwitchStmtClass:
6560 E = cast<SwitchStmt>(Val: Terminator)->getCond();
6561 break;
6562
6563 case Stmt::BinaryConditionalOperatorClass:
6564 E = cast<BinaryConditionalOperator>(Val: Terminator)->getCond();
6565 break;
6566
6567 case Stmt::ConditionalOperatorClass:
6568 E = cast<ConditionalOperator>(Val: Terminator)->getCond();
6569 break;
6570
6571 case Stmt::BinaryOperatorClass: // '&&' and '||'
6572 E = cast<BinaryOperator>(Val: Terminator)->getLHS();
6573 break;
6574
6575 case Stmt::ObjCForCollectionStmtClass:
6576 return Terminator;
6577 }
6578
6579 if (!StripParens)
6580 return E;
6581
6582 return E ? E->IgnoreParens() : nullptr;
6583}
6584
6585//===----------------------------------------------------------------------===//
6586// CFG Graphviz Visualization
6587//===----------------------------------------------------------------------===//
6588
6589static StmtPrinterHelper *GraphHelper;
6590
6591void CFG::viewCFG(const LangOptions &LO) const {
6592 StmtPrinterHelper H(this, LO);
6593 GraphHelper = &H;
6594 llvm::ViewGraph(G: this,Name: "CFG");
6595 GraphHelper = nullptr;
6596}
6597
6598namespace llvm {
6599
6600template<>
6601struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
6602 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
6603
6604 static std::string getNodeLabel(const CFGBlock *Node, const CFG *Graph) {
6605 std::string OutStr;
6606 llvm::raw_string_ostream Out(OutStr);
6607 print_block(OS&: Out,cfg: Graph, B: *Node, Helper&: *GraphHelper, print_edges: false, ShowColors: false);
6608
6609 if (OutStr[0] == '\n') OutStr.erase(position: OutStr.begin());
6610
6611 // Process string output to make it nicer...
6612 for (unsigned i = 0; i != OutStr.length(); ++i)
6613 if (OutStr[i] == '\n') { // Left justify
6614 OutStr[i] = '\\';
6615 OutStr.insert(p: OutStr.begin()+i+1, c: 'l');
6616 }
6617
6618 return OutStr;
6619 }
6620};
6621
6622} // namespace llvm
6623