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