1 //===- CFG.cpp - Classes for representing and building CFGs ---------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines the CFG and CFGBuilder classes for representing and
10 // building Control-Flow Graphs (CFGs) from ASTs.
12 //===----------------------------------------------------------------------===//
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/APInt.h"
40 #include "llvm/ADT/APSInt.h"
41 #include "llvm/ADT/ArrayRef.h"
42 #include "llvm/ADT/DenseMap.h"
43 #include "llvm/ADT/Optional.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/Casting.h"
50 #include "llvm/Support/Compiler.h"
51 #include "llvm/Support/DOTGraphTraits.h"
52 #include "llvm/Support/ErrorHandling.h"
53 #include "llvm/Support/Format.h"
54 #include "llvm/Support/GraphWriter.h"
55 #include "llvm/Support/SaveAndRestore.h"
56 #include "llvm/Support/raw_ostream.h"
64 using namespace clang;
66 static SourceLocation GetEndLoc(Decl *D) {
67 if (VarDecl *VD = dyn_cast<VarDecl>(D))
68 if (Expr *Ex = VD->getInit())
69 return Ex->getSourceRange().getEnd();
70 return D->getLocation();
73 /// Returns true on constant values based around a single IntegerLiteral.
74 /// Allow for use of parentheses, integer casts, and negative signs.
75 static bool IsIntegerLiteralConstantExpr(const Expr *E) {
77 E = E->IgnoreParens();
79 // Allow conversions to different integer kind.
80 if (const auto *CE = dyn_cast<CastExpr>(E)) {
81 if (CE->getCastKind() != CK_IntegralCast)
86 // Allow negative numbers.
87 if (const auto *UO = dyn_cast<UnaryOperator>(E)) {
88 if (UO->getOpcode() != UO_Minus)
93 return isa<IntegerLiteral>(E);
96 /// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral
97 /// constant expression or EnumConstantDecl from the given Expr. If it fails,
99 static const Expr *tryTransformToIntOrEnumConstant(const Expr *E) {
100 E = E->IgnoreParens();
101 if (IsIntegerLiteralConstantExpr(E))
103 if (auto *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts()))
104 return isa<EnumConstantDecl>(DR->getDecl()) ? DR : nullptr;
108 /// Tries to interpret a binary operator into `Expr Op NumExpr` form, if
109 /// NumExpr is an integer literal or an enum constant.
111 /// If this fails, at least one of the returned DeclRefExpr or Expr will be
113 static std::tuple<const Expr *, BinaryOperatorKind, const Expr *>
114 tryNormalizeBinaryOperator(const BinaryOperator *B) {
115 BinaryOperatorKind Op = B->getOpcode();
117 const Expr *MaybeDecl = B->getLHS();
118 const Expr *Constant = tryTransformToIntOrEnumConstant(B->getRHS());
119 // Expr looked like `0 == Foo` instead of `Foo == 0`
120 if (Constant == nullptr) {
124 else if (Op == BO_GE)
126 else if (Op == BO_LT)
128 else if (Op == BO_LE)
131 MaybeDecl = B->getRHS();
132 Constant = tryTransformToIntOrEnumConstant(B->getLHS());
135 return std::make_tuple(MaybeDecl, Op, Constant);
138 /// For an expression `x == Foo && x == Bar`, this determines whether the
139 /// `Foo` and `Bar` are either of the same enumeration type, or both integer
142 /// It's an error to pass this arguments that are not either IntegerLiterals
143 /// or DeclRefExprs (that have decls of type EnumConstantDecl)
144 static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) {
145 // User intent isn't clear if they're mixing int literals with enum
147 if (isa<DeclRefExpr>(E1) != isa<DeclRefExpr>(E2))
150 // Integer literal comparisons, regardless of literal type, are acceptable.
151 if (!isa<DeclRefExpr>(E1))
154 // IntegerLiterals are handled above and only EnumConstantDecls are expected
156 assert(isa<DeclRefExpr>(E1) && isa<DeclRefExpr>(E2));
157 auto *Decl1 = cast<DeclRefExpr>(E1)->getDecl();
158 auto *Decl2 = cast<DeclRefExpr>(E2)->getDecl();
160 assert(isa<EnumConstantDecl>(Decl1) && isa<EnumConstantDecl>(Decl2));
161 const DeclContext *DC1 = Decl1->getDeclContext();
162 const DeclContext *DC2 = Decl2->getDeclContext();
164 assert(isa<EnumDecl>(DC1) && isa<EnumDecl>(DC2));
172 /// The CFG builder uses a recursive algorithm to build the CFG. When
173 /// we process an expression, sometimes we know that we must add the
174 /// subexpressions as block-level expressions. For example:
178 /// When processing the '||' expression, we know that exp1 and exp2
179 /// need to be added as block-level expressions, even though they
180 /// might not normally need to be. AddStmtChoice records this
181 /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then
182 /// the builder has an option not to add a subexpression as a
183 /// block-level expression.
184 class AddStmtChoice {
186 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };
188 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}
190 bool alwaysAdd(CFGBuilder &builder,
191 const Stmt *stmt) const;
193 /// Return a copy of this object, except with the 'always-add' bit
194 /// set as specified.
195 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {
196 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd);
203 /// LocalScope - Node in tree of local scopes created for C++ implicit
204 /// destructor calls generation. It contains list of automatic variables
205 /// declared in the scope and link to position in previous scope this scope
208 /// The process of creating local scopes is as follows:
209 /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
210 /// - Before processing statements in scope (e.g. CompoundStmt) create
211 /// LocalScope object using CFGBuilder::ScopePos as link to previous scope
212 /// and set CFGBuilder::ScopePos to the end of new scope,
213 /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
215 /// - For every normal (without jump) end of scope add to CFGBlock destructors
216 /// for objects in the current scope,
217 /// - For every jump add to CFGBlock destructors for objects
218 /// between CFGBuilder::ScopePos and local scope position saved for jump
219 /// target. Thanks to C++ restrictions on goto jumps we can be sure that
220 /// jump target position will be on the path to root from CFGBuilder::ScopePos
221 /// (adding any variable that doesn't need constructor to be called to
222 /// LocalScope can break this assumption),
226 using AutomaticVarsTy = BumpVector<VarDecl *>;
228 /// const_iterator - Iterates local scope backwards and jumps to previous
229 /// scope on reaching the beginning of currently iterated scope.
230 class const_iterator {
231 const LocalScope* Scope = nullptr;
233 /// VarIter is guaranteed to be greater then 0 for every valid iterator.
234 /// Invalid iterator (with null Scope) has VarIter equal to 0.
235 unsigned VarIter = 0;
238 /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
239 /// Incrementing invalid iterator is allowed and will result in invalid
241 const_iterator() = default;
243 /// Create valid iterator. In case when S.Prev is an invalid iterator and
244 /// I is equal to 0, this will create invalid iterator.
245 const_iterator(const LocalScope& S, unsigned I)
246 : Scope(&S), VarIter(I) {
247 // Iterator to "end" of scope is not allowed. Handle it by going up
248 // in scopes tree possibly up to invalid iterator in the root.
249 if (VarIter == 0 && Scope)
253 VarDecl *const* operator->() const {
254 assert(Scope && "Dereferencing invalid iterator is not allowed");
255 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
256 return &Scope->Vars[VarIter - 1];
259 const VarDecl *getFirstVarInScope() const {
260 assert(Scope && "Dereferencing invalid iterator is not allowed");
261 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
262 return Scope->Vars[0];
265 VarDecl *operator*() const {
266 return *this->operator->();
269 const_iterator &operator++() {
273 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
279 const_iterator operator++(int) {
280 const_iterator P = *this;
285 bool operator==(const const_iterator &rhs) const {
286 return Scope == rhs.Scope && VarIter == rhs.VarIter;
288 bool operator!=(const const_iterator &rhs) const {
289 return !(*this == rhs);
292 explicit operator bool() const {
293 return *this != const_iterator();
296 int distance(const_iterator L);
297 const_iterator shared_parent(const_iterator L);
298 bool pointsToFirstDeclaredVar() { return VarIter == 1; }
302 BumpVectorContext ctx;
304 /// Automatic variables in order of declaration.
305 AutomaticVarsTy Vars;
307 /// Iterator to variable in previous scope that was declared just before
308 /// begin of this scope.
312 /// Constructs empty scope linked to previous scope in specified place.
313 LocalScope(BumpVectorContext ctx, const_iterator P)
314 : ctx(std::move(ctx)), Vars(this->ctx, 4), Prev(P) {}
316 /// Begin of scope in direction of CFG building (backwards).
317 const_iterator begin() const { return const_iterator(*this, Vars.size()); }
319 void addVar(VarDecl *VD) {
320 Vars.push_back(VD, ctx);
326 /// distance - Calculates distance from this to L. L must be reachable from this
327 /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
328 /// number of scopes between this and L.
329 int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
331 const_iterator F = *this;
332 while (F.Scope != L.Scope) {
333 assert(F != const_iterator() &&
334 "L iterator is not reachable from F iterator.");
338 D += F.VarIter - L.VarIter;
342 /// Calculates the closest parent of this iterator
343 /// that is in a scope reachable through the parents of L.
344 /// I.e. when using 'goto' from this to L, the lifetime of all variables
345 /// between this and shared_parent(L) end.
346 LocalScope::const_iterator
347 LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) {
348 llvm::SmallPtrSet<const LocalScope *, 4> ScopesOfL;
350 ScopesOfL.insert(L.Scope);
351 if (L == const_iterator())
356 const_iterator F = *this;
358 if (ScopesOfL.count(F.Scope))
360 assert(F != const_iterator() &&
361 "L iterator is not reachable from F iterator.");
368 /// Structure for specifying position in CFG during its build process. It
369 /// consists of CFGBlock that specifies position in CFG and
370 /// LocalScope::const_iterator that specifies position in LocalScope graph.
371 struct BlockScopePosPair {
372 CFGBlock *block = nullptr;
373 LocalScope::const_iterator scopePosition;
375 BlockScopePosPair() = default;
376 BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos)
377 : block(b), scopePosition(scopePos) {}
380 /// TryResult - a class representing a variant over the values
381 /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool,
382 /// and is used by the CFGBuilder to decide if a branch condition
383 /// can be decided up front during CFG construction.
388 TryResult() = default;
389 TryResult(bool b) : X(b ? 1 : 0) {}
391 bool isTrue() const { return X == 1; }
392 bool isFalse() const { return X == 0; }
393 bool isKnown() const { return X >= 0; }
403 static TryResult bothKnownTrue(TryResult R1, TryResult R2) {
404 if (!R1.isKnown() || !R2.isKnown())
406 return TryResult(R1.isTrue() && R2.isTrue());
411 class reverse_children {
412 llvm::SmallVector<Stmt *, 12> childrenBuf;
413 ArrayRef<Stmt *> children;
416 reverse_children(Stmt *S);
418 using iterator = ArrayRef<Stmt *>::reverse_iterator;
420 iterator begin() const { return children.rbegin(); }
421 iterator end() const { return children.rend(); }
426 reverse_children::reverse_children(Stmt *S) {
427 if (CallExpr *CE = dyn_cast<CallExpr>(S)) {
428 children = CE->getRawSubExprs();
431 switch (S->getStmtClass()) {
432 // Note: Fill in this switch with more cases we want to optimize.
433 case Stmt::InitListExprClass: {
434 InitListExpr *IE = cast<InitListExpr>(S);
435 children = llvm::makeArrayRef(reinterpret_cast<Stmt**>(IE->getInits()),
443 // Default case for all other statements.
444 for (Stmt *SubStmt : S->children())
445 childrenBuf.push_back(SubStmt);
447 // This needs to be done *after* childrenBuf has been populated.
448 children = childrenBuf;
453 /// CFGBuilder - This class implements CFG construction from an AST.
454 /// The builder is stateful: an instance of the builder should be used to only
455 /// construct a single CFG.
459 /// CFGBuilder builder;
460 /// std::unique_ptr<CFG> cfg = builder.buildCFG(decl, stmt1);
462 /// CFG construction is done via a recursive walk of an AST. We actually parse
463 /// the AST in reverse order so that the successor of a basic block is
464 /// constructed prior to its predecessor. This allows us to nicely capture
465 /// implicit fall-throughs without extra basic blocks.
467 using JumpTarget = BlockScopePosPair;
468 using JumpSource = BlockScopePosPair;
471 std::unique_ptr<CFG> cfg;
474 CFGBlock *Block = nullptr;
476 // Block after the current block.
477 CFGBlock *Succ = nullptr;
479 JumpTarget ContinueJumpTarget;
480 JumpTarget BreakJumpTarget;
481 JumpTarget SEHLeaveJumpTarget;
482 CFGBlock *SwitchTerminatedBlock = nullptr;
483 CFGBlock *DefaultCaseBlock = nullptr;
485 // This can point either to a try or a __try block. The frontend forbids
486 // mixing both kinds in one function, so having one for both is enough.
487 CFGBlock *TryTerminatedBlock = nullptr;
489 // Current position in local scope.
490 LocalScope::const_iterator ScopePos;
492 // LabelMap records the mapping from Label expressions to their jump targets.
493 using LabelMapTy = llvm::DenseMap<LabelDecl *, JumpTarget>;
496 // A list of blocks that end with a "goto" that must be backpatched to their
497 // resolved targets upon completion of CFG construction.
498 using BackpatchBlocksTy = std::vector<JumpSource>;
499 BackpatchBlocksTy BackpatchBlocks;
501 // A list of labels whose address has been taken (for indirect gotos).
502 using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>;
503 LabelSetTy AddressTakenLabels;
505 // Information about the currently visited C++ object construction site.
506 // This is set in the construction trigger and read when the constructor
507 // or a function that returns an object by value is being visited.
508 llvm::DenseMap<Expr *, const ConstructionContextLayer *>
509 ConstructionContextMap;
511 using DeclsWithEndedScopeSetTy = llvm::SmallSetVector<VarDecl *, 16>;
512 DeclsWithEndedScopeSetTy DeclsWithEndedScope;
515 const CFG::BuildOptions &BuildOpts;
517 // State to track for building switch statements.
518 bool switchExclusivelyCovered = false;
519 Expr::EvalResult *switchCond = nullptr;
521 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr;
522 const Stmt *lastLookup = nullptr;
524 // Caches boolean evaluations of expressions to avoid multiple re-evaluations
525 // during construction of branches for chained logical operators.
526 using CachedBoolEvalsTy = llvm::DenseMap<Expr *, TryResult>;
527 CachedBoolEvalsTy CachedBoolEvals;
530 explicit CFGBuilder(ASTContext *astContext,
531 const CFG::BuildOptions &buildOpts)
532 : Context(astContext), cfg(new CFG()), // crew a new CFG
533 ConstructionContextMap(), BuildOpts(buildOpts) {}
536 // buildCFG - Used by external clients to construct the CFG.
537 std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement);
539 bool alwaysAdd(const Stmt *stmt);
542 // Visitors to walk an AST and construct the CFG.
543 CFGBlock *VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc);
544 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
545 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);
546 CFGBlock *VisitBreakStmt(BreakStmt *B);
547 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);
548 CFGBlock *VisitCaseStmt(CaseStmt *C);
549 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);
550 CFGBlock *VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed);
551 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,
553 CFGBlock *VisitContinueStmt(ContinueStmt *C);
554 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
556 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
557 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
558 CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc);
559 CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc);
560 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
561 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
563 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
565 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);
566 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);
567 CFGBlock *VisitDeclStmt(DeclStmt *DS);
568 CFGBlock *VisitDeclSubExpr(DeclStmt *DS);
569 CFGBlock *VisitDefaultStmt(DefaultStmt *D);
570 CFGBlock *VisitDoStmt(DoStmt *D);
571 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E,
572 AddStmtChoice asc, bool ExternallyDestructed);
573 CFGBlock *VisitForStmt(ForStmt *F);
574 CFGBlock *VisitGotoStmt(GotoStmt *G);
575 CFGBlock *VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc);
576 CFGBlock *VisitIfStmt(IfStmt *I);
577 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);
578 CFGBlock *VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc);
579 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);
580 CFGBlock *VisitLabelStmt(LabelStmt *L);
581 CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc);
582 CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc);
583 CFGBlock *VisitLogicalOperator(BinaryOperator *B);
584 std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B,
587 CFGBlock *FalseBlock);
588 CFGBlock *VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
590 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);
591 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);
592 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
593 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
594 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);
595 CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S);
596 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);
597 CFGBlock *VisitObjCMessageExpr(ObjCMessageExpr *E, AddStmtChoice asc);
598 CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E);
599 CFGBlock *VisitReturnStmt(Stmt *S);
600 CFGBlock *VisitSEHExceptStmt(SEHExceptStmt *S);
601 CFGBlock *VisitSEHFinallyStmt(SEHFinallyStmt *S);
602 CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S);
603 CFGBlock *VisitSEHTryStmt(SEHTryStmt *S);
604 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
605 CFGBlock *VisitSwitchStmt(SwitchStmt *S);
606 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
608 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
609 CFGBlock *VisitWhileStmt(WhileStmt *W);
611 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd,
612 bool ExternallyDestructed = false);
613 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
614 CFGBlock *VisitChildren(Stmt *S);
615 CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc);
616 CFGBlock *VisitOMPExecutableDirective(OMPExecutableDirective *D,
619 void maybeAddScopeBeginForVarDecl(CFGBlock *B, const VarDecl *VD,
621 if (ScopePos && (VD == ScopePos.getFirstVarInScope()))
622 appendScopeBegin(B, VD, S);
625 /// When creating the CFG for temporary destructors, we want to mirror the
626 /// branch structure of the corresponding constructor calls.
627 /// Thus, while visiting a statement for temporary destructors, we keep a
628 /// context to keep track of the following information:
629 /// - whether a subexpression is executed unconditionally
630 /// - if a subexpression is executed conditionally, the first
631 /// CXXBindTemporaryExpr we encounter in that subexpression (which
632 /// corresponds to the last temporary destructor we have to call for this
633 /// subexpression) and the CFG block at that point (which will become the
634 /// successor block when inserting the decision point).
636 /// That way, we can build the branch structure for temporary destructors as
638 /// 1. If a subexpression is executed unconditionally, we add the temporary
639 /// destructor calls to the current block.
640 /// 2. If a subexpression is executed conditionally, when we encounter a
641 /// CXXBindTemporaryExpr:
642 /// a) If it is the first temporary destructor call in the subexpression,
643 /// we remember the CXXBindTemporaryExpr and the current block in the
644 /// TempDtorContext; we start a new block, and insert the temporary
646 /// b) Otherwise, add the temporary destructor call to the current block.
647 /// 3. When we finished visiting a conditionally executed subexpression,
648 /// and we found at least one temporary constructor during the visitation
649 /// (2.a has executed), we insert a decision block that uses the
650 /// CXXBindTemporaryExpr as terminator, and branches to the current block
651 /// if the CXXBindTemporaryExpr was marked executed, and otherwise
652 /// branches to the stored successor.
653 struct TempDtorContext {
654 TempDtorContext() = default;
655 TempDtorContext(TryResult KnownExecuted)
656 : IsConditional(true), KnownExecuted(KnownExecuted) {}
658 /// Returns whether we need to start a new branch for a temporary destructor
659 /// call. This is the case when the temporary destructor is
660 /// conditionally executed, and it is the first one we encounter while
661 /// visiting a subexpression - other temporary destructors at the same level
662 /// will be added to the same block and are executed under the same
664 bool needsTempDtorBranch() const {
665 return IsConditional && !TerminatorExpr;
668 /// Remember the successor S of a temporary destructor decision branch for
669 /// the corresponding CXXBindTemporaryExpr E.
670 void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) {
675 const bool IsConditional = false;
676 const TryResult KnownExecuted = true;
677 CFGBlock *Succ = nullptr;
678 CXXBindTemporaryExpr *TerminatorExpr = nullptr;
681 // Visitors to walk an AST and generate destructors of temporaries in
683 CFGBlock *VisitForTemporaryDtors(Stmt *E, bool ExternallyDestructed,
684 TempDtorContext &Context);
685 CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E, bool ExternallyDestructed,
686 TempDtorContext &Context);
687 CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E,
688 bool ExternallyDestructed,
689 TempDtorContext &Context);
690 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(
691 CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context);
692 CFGBlock *VisitConditionalOperatorForTemporaryDtors(
693 AbstractConditionalOperator *E, bool ExternallyDestructed,
694 TempDtorContext &Context);
695 void InsertTempDtorDecisionBlock(const TempDtorContext &Context,
696 CFGBlock *FalseSucc = nullptr);
698 // NYS == Not Yet Supported
704 // Remember to apply the construction context based on the current \p Layer
705 // when constructing the CFG element for \p CE.
706 void consumeConstructionContext(const ConstructionContextLayer *Layer,
709 // Scan \p Child statement to find constructors in it, while keeping in mind
710 // that its parent statement is providing a partial construction context
711 // described by \p Layer. If a constructor is found, it would be assigned
712 // the context based on the layer. If an additional construction context layer
713 // is found, the function recurses into that.
714 void findConstructionContexts(const ConstructionContextLayer *Layer,
717 // Scan all arguments of a call expression for a construction context.
718 // These sorts of call expressions don't have a common superclass,
719 // hence strict duck-typing.
720 template <typename CallLikeExpr,
721 typename = std::enable_if_t<
722 std::is_base_of<CallExpr, CallLikeExpr>::value ||
723 std::is_base_of<CXXConstructExpr, CallLikeExpr>::value ||
724 std::is_base_of<ObjCMessageExpr, CallLikeExpr>::value>>
725 void findConstructionContextsForArguments(CallLikeExpr *E) {
726 for (unsigned i = 0, e = E->getNumArgs(); i != e; ++i) {
727 Expr *Arg = E->getArg(i);
728 if (Arg->getType()->getAsCXXRecordDecl() && !Arg->isGLValue())
729 findConstructionContexts(
730 ConstructionContextLayer::create(cfg->getBumpVectorContext(),
731 ConstructionContextItem(E, i)),
736 // Unset the construction context after consuming it. This is done immediately
737 // after adding the CFGConstructor or CFGCXXRecordTypedCall element, so
738 // there's no need to do this manually in every Visit... function.
739 void cleanupConstructionContext(Expr *E);
741 void autoCreateBlock() { if (!Block) Block = createBlock(); }
742 CFGBlock *createBlock(bool add_successor = true);
743 CFGBlock *createNoReturnBlock();
745 CFGBlock *addStmt(Stmt *S) {
746 return Visit(S, AddStmtChoice::AlwaysAdd);
749 CFGBlock *addInitializer(CXXCtorInitializer *I);
750 void addLoopExit(const Stmt *LoopStmt);
751 void addAutomaticObjDtors(LocalScope::const_iterator B,
752 LocalScope::const_iterator E, Stmt *S);
753 void addLifetimeEnds(LocalScope::const_iterator B,
754 LocalScope::const_iterator E, Stmt *S);
755 void addAutomaticObjHandling(LocalScope::const_iterator B,
756 LocalScope::const_iterator E, Stmt *S);
757 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
758 void addScopesEnd(LocalScope::const_iterator B, LocalScope::const_iterator E,
761 void getDeclsWithEndedScope(LocalScope::const_iterator B,
762 LocalScope::const_iterator E, Stmt *S);
764 // Local scopes creation.
765 LocalScope* createOrReuseLocalScope(LocalScope* Scope);
767 void addLocalScopeForStmt(Stmt *S);
768 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,
769 LocalScope* Scope = nullptr);
770 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);
772 void addLocalScopeAndDtors(Stmt *S);
774 const ConstructionContext *retrieveAndCleanupConstructionContext(Expr *E) {
775 if (!BuildOpts.AddRichCXXConstructors)
778 const ConstructionContextLayer *Layer = ConstructionContextMap.lookup(E);
782 cleanupConstructionContext(E);
783 return ConstructionContext::createFromLayers(cfg->getBumpVectorContext(),
787 // Interface to CFGBlock - adding CFGElements.
789 void appendStmt(CFGBlock *B, const Stmt *S) {
790 if (alwaysAdd(S) && cachedEntry)
791 cachedEntry->second = B;
793 // All block-level expressions should have already been IgnoreParens()ed.
794 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
795 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
798 void appendConstructor(CFGBlock *B, CXXConstructExpr *CE) {
799 if (const ConstructionContext *CC =
800 retrieveAndCleanupConstructionContext(CE)) {
801 B->appendConstructor(CE, CC, cfg->getBumpVectorContext());
805 // No valid construction context found. Fall back to statement.
806 B->appendStmt(CE, cfg->getBumpVectorContext());
809 void appendCall(CFGBlock *B, CallExpr *CE) {
810 if (alwaysAdd(CE) && cachedEntry)
811 cachedEntry->second = B;
813 if (const ConstructionContext *CC =
814 retrieveAndCleanupConstructionContext(CE)) {
815 B->appendCXXRecordTypedCall(CE, CC, cfg->getBumpVectorContext());
819 // No valid construction context found. Fall back to statement.
820 B->appendStmt(CE, cfg->getBumpVectorContext());
823 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
824 B->appendInitializer(I, cfg->getBumpVectorContext());
827 void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {
828 B->appendNewAllocator(NE, cfg->getBumpVectorContext());
831 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
832 B->appendBaseDtor(BS, cfg->getBumpVectorContext());
835 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
836 B->appendMemberDtor(FD, cfg->getBumpVectorContext());
839 void appendObjCMessage(CFGBlock *B, ObjCMessageExpr *ME) {
840 if (alwaysAdd(ME) && cachedEntry)
841 cachedEntry->second = B;
843 if (const ConstructionContext *CC =
844 retrieveAndCleanupConstructionContext(ME)) {
845 B->appendCXXRecordTypedCall(ME, CC, cfg->getBumpVectorContext());
849 B->appendStmt(const_cast<ObjCMessageExpr *>(ME),
850 cfg->getBumpVectorContext());
853 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
854 B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
857 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
858 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
861 void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {
862 B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());
865 void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) {
866 B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext());
869 void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
870 B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
873 void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
874 LocalScope::const_iterator B, LocalScope::const_iterator E);
876 void prependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk,
877 LocalScope::const_iterator B,
878 LocalScope::const_iterator E);
881 prependAutomaticObjScopeEndWithTerminator(CFGBlock *Blk,
882 LocalScope::const_iterator B,
883 LocalScope::const_iterator E);
885 void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {
886 B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable),
887 cfg->getBumpVectorContext());
890 /// Add a reachable successor to a block, with the alternate variant that is
892 void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {
893 B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),
894 cfg->getBumpVectorContext());
897 void appendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
898 if (BuildOpts.AddScopes)
899 B->appendScopeBegin(VD, S, cfg->getBumpVectorContext());
902 void prependScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
903 if (BuildOpts.AddScopes)
904 B->prependScopeBegin(VD, S, cfg->getBumpVectorContext());
907 void appendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
908 if (BuildOpts.AddScopes)
909 B->appendScopeEnd(VD, S, cfg->getBumpVectorContext());
912 void prependScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
913 if (BuildOpts.AddScopes)
914 B->prependScopeEnd(VD, S, cfg->getBumpVectorContext());
917 /// Find a relational comparison with an expression evaluating to a
918 /// boolean and a constant other than 0 and 1.
919 /// e.g. if ((x < y) == 10)
920 TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) {
921 const Expr *LHSExpr = B->getLHS()->IgnoreParens();
922 const Expr *RHSExpr = B->getRHS()->IgnoreParens();
924 const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
925 const Expr *BoolExpr = RHSExpr;
926 bool IntFirst = true;
928 IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
933 if (!IntLiteral || !BoolExpr->isKnownToHaveBooleanValue())
936 llvm::APInt IntValue = IntLiteral->getValue();
937 if ((IntValue == 1) || (IntValue == 0))
940 bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() ||
941 !IntValue.isNegative();
943 BinaryOperatorKind Bok = B->getOpcode();
944 if (Bok == BO_GT || Bok == BO_GE) {
945 // Always true for 10 > bool and bool > -1
946 // Always false for -1 > bool and bool > 10
947 return TryResult(IntFirst == IntLarger);
949 // Always true for -1 < bool and bool < 10
950 // Always false for 10 < bool and bool < -1
951 return TryResult(IntFirst != IntLarger);
955 /// Find an incorrect equality comparison. Either with an expression
956 /// evaluating to a boolean and a constant other than 0 and 1.
957 /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to
958 /// true/false e.q. (x & 8) == 4.
959 TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) {
960 const Expr *LHSExpr = B->getLHS()->IgnoreParens();
961 const Expr *RHSExpr = B->getRHS()->IgnoreParens();
963 const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
964 const Expr *BoolExpr = RHSExpr;
967 IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
974 const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(BoolExpr);
975 if (BitOp && (BitOp->getOpcode() == BO_And ||
976 BitOp->getOpcode() == BO_Or)) {
977 const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens();
978 const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens();
980 const IntegerLiteral *IntLiteral2 = dyn_cast<IntegerLiteral>(LHSExpr2);
983 IntLiteral2 = dyn_cast<IntegerLiteral>(RHSExpr2);
988 llvm::APInt L1 = IntLiteral->getValue();
989 llvm::APInt L2 = IntLiteral2->getValue();
990 if ((BitOp->getOpcode() == BO_And && (L2 & L1) != L1) ||
991 (BitOp->getOpcode() == BO_Or && (L2 | L1) != L1)) {
992 if (BuildOpts.Observer)
993 BuildOpts.Observer->compareBitwiseEquality(B,
994 B->getOpcode() != BO_EQ);
995 TryResult(B->getOpcode() != BO_EQ);
997 } else if (BoolExpr->isKnownToHaveBooleanValue()) {
998 llvm::APInt IntValue = IntLiteral->getValue();
999 if ((IntValue == 1) || (IntValue == 0)) {
1002 return TryResult(B->getOpcode() != BO_EQ);
1008 TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation,
1009 const llvm::APSInt &Value1,
1010 const llvm::APSInt &Value2) {
1011 assert(Value1.isSigned() == Value2.isSigned());
1016 return TryResult(Value1 == Value2);
1018 return TryResult(Value1 != Value2);
1020 return TryResult(Value1 < Value2);
1022 return TryResult(Value1 <= Value2);
1024 return TryResult(Value1 > Value2);
1026 return TryResult(Value1 >= Value2);
1030 /// Find a pair of comparison expressions with or without parentheses
1031 /// with a shared variable and constants and a logical operator between them
1032 /// that always evaluates to either true or false.
1033 /// e.g. if (x != 3 || x != 4)
1034 TryResult checkIncorrectLogicOperator(const BinaryOperator *B) {
1035 assert(B->isLogicalOp());
1036 const BinaryOperator *LHS =
1037 dyn_cast<BinaryOperator>(B->getLHS()->IgnoreParens());
1038 const BinaryOperator *RHS =
1039 dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens());
1043 if (!LHS->isComparisonOp() || !RHS->isComparisonOp())
1046 const Expr *DeclExpr1;
1047 const Expr *NumExpr1;
1048 BinaryOperatorKind BO1;
1049 std::tie(DeclExpr1, BO1, NumExpr1) = tryNormalizeBinaryOperator(LHS);
1051 if (!DeclExpr1 || !NumExpr1)
1054 const Expr *DeclExpr2;
1055 const Expr *NumExpr2;
1056 BinaryOperatorKind BO2;
1057 std::tie(DeclExpr2, BO2, NumExpr2) = tryNormalizeBinaryOperator(RHS);
1059 if (!DeclExpr2 || !NumExpr2)
1062 // Check that it is the same variable on both sides.
1063 if (!Expr::isSameComparisonOperand(DeclExpr1, DeclExpr2))
1066 // Make sure the user's intent is clear (e.g. they're comparing against two
1067 // int literals, or two things from the same enum)
1068 if (!areExprTypesCompatible(NumExpr1, NumExpr2))
1071 Expr::EvalResult L1Result, L2Result;
1072 if (!NumExpr1->EvaluateAsInt(L1Result, *Context) ||
1073 !NumExpr2->EvaluateAsInt(L2Result, *Context))
1076 llvm::APSInt L1 = L1Result.Val.getInt();
1077 llvm::APSInt L2 = L2Result.Val.getInt();
1079 // Can't compare signed with unsigned or with different bit width.
1080 if (L1.isSigned() != L2.isSigned() || L1.getBitWidth() != L2.getBitWidth())
1083 // Values that will be used to determine if result of logical
1084 // operator is always true/false
1085 const llvm::APSInt Values[] = {
1086 // Value less than both Value1 and Value2
1087 llvm::APSInt::getMinValue(L1.getBitWidth(), L1.isUnsigned()),
1090 // Value between Value1 and Value2
1091 ((L1 < L2) ? L1 : L2) + llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1),
1095 // Value greater than both Value1 and Value2
1096 llvm::APSInt::getMaxValue(L1.getBitWidth(), L1.isUnsigned()),
1099 // Check whether expression is always true/false by evaluating the following
1100 // * variable x is less than the smallest literal.
1101 // * variable x is equal to the smallest literal.
1102 // * Variable x is between smallest and largest literal.
1103 // * Variable x is equal to the largest literal.
1104 // * Variable x is greater than largest literal.
1105 bool AlwaysTrue = true, AlwaysFalse = true;
1106 // Track value of both subexpressions. If either side is always
1107 // true/false, another warning should have already been emitted.
1108 bool LHSAlwaysTrue = true, LHSAlwaysFalse = true;
1109 bool RHSAlwaysTrue = true, RHSAlwaysFalse = true;
1110 for (const llvm::APSInt &Value : Values) {
1111 TryResult Res1, Res2;
1112 Res1 = analyzeLogicOperatorCondition(BO1, Value, L1);
1113 Res2 = analyzeLogicOperatorCondition(BO2, Value, L2);
1115 if (!Res1.isKnown() || !Res2.isKnown())
1118 if (B->getOpcode() == BO_LAnd) {
1119 AlwaysTrue &= (Res1.isTrue() && Res2.isTrue());
1120 AlwaysFalse &= !(Res1.isTrue() && Res2.isTrue());
1122 AlwaysTrue &= (Res1.isTrue() || Res2.isTrue());
1123 AlwaysFalse &= !(Res1.isTrue() || Res2.isTrue());
1126 LHSAlwaysTrue &= Res1.isTrue();
1127 LHSAlwaysFalse &= Res1.isFalse();
1128 RHSAlwaysTrue &= Res2.isTrue();
1129 RHSAlwaysFalse &= Res2.isFalse();
1132 if (AlwaysTrue || AlwaysFalse) {
1133 if (!LHSAlwaysTrue && !LHSAlwaysFalse && !RHSAlwaysTrue &&
1134 !RHSAlwaysFalse && BuildOpts.Observer)
1135 BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue);
1136 return TryResult(AlwaysTrue);
1141 /// A bitwise-or with a non-zero constant always evaluates to true.
1142 TryResult checkIncorrectBitwiseOrOperator(const BinaryOperator *B) {
1143 const Expr *LHSConstant =
1144 tryTransformToIntOrEnumConstant(B->getLHS()->IgnoreParenImpCasts());
1145 const Expr *RHSConstant =
1146 tryTransformToIntOrEnumConstant(B->getRHS()->IgnoreParenImpCasts());
1148 if ((LHSConstant && RHSConstant) || (!LHSConstant && !RHSConstant))
1151 const Expr *Constant = LHSConstant ? LHSConstant : RHSConstant;
1153 Expr::EvalResult Result;
1154 if (!Constant->EvaluateAsInt(Result, *Context))
1157 if (Result.Val.getInt() == 0)
1160 if (BuildOpts.Observer)
1161 BuildOpts.Observer->compareBitwiseOr(B);
1163 return TryResult(true);
1166 /// Try and evaluate an expression to an integer constant.
1167 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {
1168 if (!BuildOpts.PruneTriviallyFalseEdges)
1170 return !S->isTypeDependent() &&
1171 !S->isValueDependent() &&
1172 S->EvaluateAsRValue(outResult, *Context);
1175 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
1176 /// if we can evaluate to a known value, otherwise return -1.
1177 TryResult tryEvaluateBool(Expr *S) {
1178 if (!BuildOpts.PruneTriviallyFalseEdges ||
1179 S->isTypeDependent() || S->isValueDependent())
1182 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) {
1183 if (Bop->isLogicalOp() || Bop->isEqualityOp()) {
1184 // Check the cache first.
1185 CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S);
1186 if (I != CachedBoolEvals.end())
1187 return I->second; // already in map;
1189 // Retrieve result at first, or the map might be updated.
1190 TryResult Result = evaluateAsBooleanConditionNoCache(S);
1191 CachedBoolEvals[S] = Result; // update or insert
1195 switch (Bop->getOpcode()) {
1197 // For 'x & 0' and 'x * 0', we can determine that
1198 // the value is always false.
1201 // If either operand is zero, we know the value
1203 Expr::EvalResult LHSResult;
1204 if (Bop->getLHS()->EvaluateAsInt(LHSResult, *Context)) {
1205 llvm::APSInt IntVal = LHSResult.Val.getInt();
1206 if (!IntVal.getBoolValue()) {
1207 return TryResult(false);
1210 Expr::EvalResult RHSResult;
1211 if (Bop->getRHS()->EvaluateAsInt(RHSResult, *Context)) {
1212 llvm::APSInt IntVal = RHSResult.Val.getInt();
1213 if (!IntVal.getBoolValue()) {
1214 return TryResult(false);
1223 return evaluateAsBooleanConditionNoCache(S);
1226 /// Evaluate as boolean \param E without using the cache.
1227 TryResult evaluateAsBooleanConditionNoCache(Expr *E) {
1228 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) {
1229 if (Bop->isLogicalOp()) {
1230 TryResult LHS = tryEvaluateBool(Bop->getLHS());
1231 if (LHS.isKnown()) {
1232 // We were able to evaluate the LHS, see if we can get away with not
1233 // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
1234 if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1235 return LHS.isTrue();
1237 TryResult RHS = tryEvaluateBool(Bop->getRHS());
1238 if (RHS.isKnown()) {
1239 if (Bop->getOpcode() == BO_LOr)
1240 return LHS.isTrue() || RHS.isTrue();
1242 return LHS.isTrue() && RHS.isTrue();
1245 TryResult RHS = tryEvaluateBool(Bop->getRHS());
1246 if (RHS.isKnown()) {
1247 // We can't evaluate the LHS; however, sometimes the result
1248 // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
1249 if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1250 return RHS.isTrue();
1252 TryResult BopRes = checkIncorrectLogicOperator(Bop);
1253 if (BopRes.isKnown())
1254 return BopRes.isTrue();
1259 } else if (Bop->isEqualityOp()) {
1260 TryResult BopRes = checkIncorrectEqualityOperator(Bop);
1261 if (BopRes.isKnown())
1262 return BopRes.isTrue();
1263 } else if (Bop->isRelationalOp()) {
1264 TryResult BopRes = checkIncorrectRelationalOperator(Bop);
1265 if (BopRes.isKnown())
1266 return BopRes.isTrue();
1267 } else if (Bop->getOpcode() == BO_Or) {
1268 TryResult BopRes = checkIncorrectBitwiseOrOperator(Bop);
1269 if (BopRes.isKnown())
1270 return BopRes.isTrue();
1275 if (E->EvaluateAsBooleanCondition(Result, *Context))
1281 bool hasTrivialDestructor(VarDecl *VD);
1286 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
1287 const Stmt *stmt) const {
1288 return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
1291 bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
1292 bool shouldAdd = BuildOpts.alwaysAdd(stmt);
1294 if (!BuildOpts.forcedBlkExprs)
1297 if (lastLookup == stmt) {
1299 assert(cachedEntry->first == stmt);
1307 // Perform the lookup!
1308 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
1311 // No need to update 'cachedEntry', since it will always be null.
1312 assert(!cachedEntry);
1316 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);
1317 if (itr == fb->end()) {
1318 cachedEntry = nullptr;
1322 cachedEntry = &*itr;
1326 // FIXME: Add support for dependent-sized array types in C++?
1327 // Does it even make sense to build a CFG for an uninstantiated template?
1328 static const VariableArrayType *FindVA(const Type *t) {
1329 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {
1330 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
1331 if (vat->getSizeExpr())
1334 t = vt->getElementType().getTypePtr();
1340 void CFGBuilder::consumeConstructionContext(
1341 const ConstructionContextLayer *Layer, Expr *E) {
1342 assert((isa<CXXConstructExpr>(E) || isa<CallExpr>(E) ||
1343 isa<ObjCMessageExpr>(E)) && "Expression cannot construct an object!");
1344 if (const ConstructionContextLayer *PreviouslyStoredLayer =
1345 ConstructionContextMap.lookup(E)) {
1346 (void)PreviouslyStoredLayer;
1347 // We might have visited this child when we were finding construction
1348 // contexts within its parents.
1349 assert(PreviouslyStoredLayer->isStrictlyMoreSpecificThan(Layer) &&
1350 "Already within a different construction context!");
1352 ConstructionContextMap[E] = Layer;
1356 void CFGBuilder::findConstructionContexts(
1357 const ConstructionContextLayer *Layer, Stmt *Child) {
1358 if (!BuildOpts.AddRichCXXConstructors)
1364 auto withExtraLayer = [this, Layer](const ConstructionContextItem &Item) {
1365 return ConstructionContextLayer::create(cfg->getBumpVectorContext(), Item,
1369 switch(Child->getStmtClass()) {
1370 case Stmt::CXXConstructExprClass:
1371 case Stmt::CXXTemporaryObjectExprClass: {
1372 // Support pre-C++17 copy elision AST.
1373 auto *CE = cast<CXXConstructExpr>(Child);
1374 if (BuildOpts.MarkElidedCXXConstructors && CE->isElidable()) {
1375 findConstructionContexts(withExtraLayer(CE), CE->getArg(0));
1378 consumeConstructionContext(Layer, CE);
1381 // FIXME: This, like the main visit, doesn't support CUDAKernelCallExpr.
1382 // FIXME: An isa<> would look much better but this whole switch is a
1383 // workaround for an internal compiler error in MSVC 2015 (see r326021).
1384 case Stmt::CallExprClass:
1385 case Stmt::CXXMemberCallExprClass:
1386 case Stmt::CXXOperatorCallExprClass:
1387 case Stmt::UserDefinedLiteralClass:
1388 case Stmt::ObjCMessageExprClass: {
1389 auto *E = cast<Expr>(Child);
1390 if (CFGCXXRecordTypedCall::isCXXRecordTypedCall(E))
1391 consumeConstructionContext(Layer, E);
1394 case Stmt::ExprWithCleanupsClass: {
1395 auto *Cleanups = cast<ExprWithCleanups>(Child);
1396 findConstructionContexts(Layer, Cleanups->getSubExpr());
1399 case Stmt::CXXFunctionalCastExprClass: {
1400 auto *Cast = cast<CXXFunctionalCastExpr>(Child);
1401 findConstructionContexts(Layer, Cast->getSubExpr());
1404 case Stmt::ImplicitCastExprClass: {
1405 auto *Cast = cast<ImplicitCastExpr>(Child);
1406 // Should we support other implicit cast kinds?
1407 switch (Cast->getCastKind()) {
1409 case CK_ConstructorConversion:
1410 findConstructionContexts(Layer, Cast->getSubExpr());
1417 case Stmt::CXXBindTemporaryExprClass: {
1418 auto *BTE = cast<CXXBindTemporaryExpr>(Child);
1419 findConstructionContexts(withExtraLayer(BTE), BTE->getSubExpr());
1422 case Stmt::MaterializeTemporaryExprClass: {
1423 // Normally we don't want to search in MaterializeTemporaryExpr because
1424 // it indicates the beginning of a temporary object construction context,
1425 // so it shouldn't be found in the middle. However, if it is the beginning
1426 // of an elidable copy or move construction context, we need to include it.
1427 if (Layer->getItem().getKind() ==
1428 ConstructionContextItem::ElidableConstructorKind) {
1429 auto *MTE = cast<MaterializeTemporaryExpr>(Child);
1430 findConstructionContexts(withExtraLayer(MTE), MTE->getSubExpr());
1434 case Stmt::ConditionalOperatorClass: {
1435 auto *CO = cast<ConditionalOperator>(Child);
1436 if (Layer->getItem().getKind() !=
1437 ConstructionContextItem::MaterializationKind) {
1438 // If the object returned by the conditional operator is not going to be a
1439 // temporary object that needs to be immediately materialized, then
1440 // it must be C++17 with its mandatory copy elision. Do not yet promise
1441 // to support this case.
1442 assert(!CO->getType()->getAsCXXRecordDecl() || CO->isGLValue() ||
1443 Context->getLangOpts().CPlusPlus17);
1446 findConstructionContexts(Layer, CO->getLHS());
1447 findConstructionContexts(Layer, CO->getRHS());
1450 case Stmt::InitListExprClass: {
1451 auto *ILE = cast<InitListExpr>(Child);
1452 if (ILE->isTransparent()) {
1453 findConstructionContexts(Layer, ILE->getInit(0));
1456 // TODO: Handle other cases. For now, fail to find construction contexts.
1464 void CFGBuilder::cleanupConstructionContext(Expr *E) {
1465 assert(BuildOpts.AddRichCXXConstructors &&
1466 "We should not be managing construction contexts!");
1467 assert(ConstructionContextMap.count(E) &&
1468 "Cannot exit construction context without the context!");
1469 ConstructionContextMap.erase(E);
1473 /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
1474 /// arbitrary statement. Examples include a single expression or a function
1475 /// body (compound statement). The ownership of the returned CFG is
1476 /// transferred to the caller. If CFG construction fails, this method returns
1478 std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
1483 // Create an empty block that will serve as the exit block for the CFG. Since
1484 // this is the first block added to the CFG, it will be implicitly registered
1485 // as the exit block.
1486 Succ = createBlock();
1487 assert(Succ == &cfg->getExit());
1488 Block = nullptr; // the EXIT block is empty. Create all other blocks lazily.
1490 assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
1491 "AddImplicitDtors and AddLifetime cannot be used at the same time");
1493 if (BuildOpts.AddImplicitDtors)
1494 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
1495 addImplicitDtorsForDestructor(DD);
1497 // Visit the statements and create the CFG.
1498 CFGBlock *B = addStmt(Statement);
1503 // For C++ constructor add initializers to CFG. Constructors of virtual bases
1504 // are ignored unless the object is of the most derived class.
1505 // class VBase { VBase() = default; VBase(int) {} };
1506 // class A : virtual public VBase { A() : VBase(0) {} };
1507 // class B : public A {};
1508 // B b; // Constructor calls in order: VBase(), A(), B().
1509 // // VBase(0) is ignored because A isn't the most derived class.
1510 // This may result in the virtual base(s) being already initialized at this
1511 // point, in which case we should jump right onto non-virtual bases and
1512 // fields. To handle this, make a CFG branch. We only need to add one such
1513 // branch per constructor, since the Standard states that all virtual bases
1514 // shall be initialized before non-virtual bases and direct data members.
1515 if (const auto *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {
1516 CFGBlock *VBaseSucc = nullptr;
1517 for (auto *I : llvm::reverse(CD->inits())) {
1518 if (BuildOpts.AddVirtualBaseBranches && !VBaseSucc &&
1519 I->isBaseInitializer() && I->isBaseVirtual()) {
1520 // We've reached the first virtual base init while iterating in reverse
1521 // order. Make a new block for virtual base initializers so that we
1523 VBaseSucc = Succ = B ? B : &cfg->getExit();
1524 Block = createBlock();
1526 B = addInitializer(I);
1531 // Make a branch block for potentially skipping virtual base initializers.
1535 CFGTerminator(nullptr, CFGTerminator::VirtualBaseBranch));
1536 addSuccessor(B, Block, true);
1543 // Backpatch the gotos whose label -> block mappings we didn't know when we
1544 // encountered them.
1545 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
1546 E = BackpatchBlocks.end(); I != E; ++I ) {
1548 CFGBlock *B = I->block;
1549 if (auto *G = dyn_cast<GotoStmt>(B->getTerminator())) {
1550 LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
1551 // If there is no target for the goto, then we are looking at an
1552 // incomplete AST. Handle this by not registering a successor.
1553 if (LI == LabelMap.end())
1555 JumpTarget JT = LI->second;
1556 prependAutomaticObjLifetimeWithTerminator(B, I->scopePosition,
1558 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
1560 const VarDecl *VD = prependAutomaticObjScopeEndWithTerminator(
1561 B, I->scopePosition, JT.scopePosition);
1562 appendScopeBegin(JT.block, VD, G);
1563 addSuccessor(B, JT.block);
1565 if (auto *G = dyn_cast<GCCAsmStmt>(B->getTerminator())) {
1566 CFGBlock *Successor = (I+1)->block;
1567 for (auto *L : G->labels()) {
1568 LabelMapTy::iterator LI = LabelMap.find(L->getLabel());
1569 // If there is no target for the goto, then we are looking at an
1570 // incomplete AST. Handle this by not registering a successor.
1571 if (LI == LabelMap.end())
1573 JumpTarget JT = LI->second;
1574 // Successor has been added, so skip it.
1575 if (JT.block == Successor)
1577 addSuccessor(B, JT.block);
1583 // Add successors to the Indirect Goto Dispatch block (if we have one).
1584 if (CFGBlock *B = cfg->getIndirectGotoBlock())
1585 for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
1586 E = AddressTakenLabels.end(); I != E; ++I ) {
1587 // Lookup the target block.
1588 LabelMapTy::iterator LI = LabelMap.find(*I);
1590 // If there is no target block that contains label, then we are looking
1591 // at an incomplete AST. Handle this by not registering a successor.
1592 if (LI == LabelMap.end()) continue;
1594 addSuccessor(B, LI->second.block);
1597 // Create an empty entry block that has no predecessors.
1598 cfg->setEntry(createBlock());
1600 if (BuildOpts.AddRichCXXConstructors)
1601 assert(ConstructionContextMap.empty() &&
1602 "Not all construction contexts were cleaned up!");
1604 return std::move(cfg);
1607 /// createBlock - Used to lazily create blocks that are connected
1608 /// to the current (global) succcessor.
1609 CFGBlock *CFGBuilder::createBlock(bool add_successor) {
1610 CFGBlock *B = cfg->createBlock();
1611 if (add_successor && Succ)
1612 addSuccessor(B, Succ);
1616 /// createNoReturnBlock - Used to create a block is a 'noreturn' point in the
1617 /// CFG. It is *not* connected to the current (global) successor, and instead
1618 /// directly tied to the exit block in order to be reachable.
1619 CFGBlock *CFGBuilder::createNoReturnBlock() {
1620 CFGBlock *B = createBlock(false);
1621 B->setHasNoReturnElement();
1622 addSuccessor(B, &cfg->getExit(), Succ);
1626 /// addInitializer - Add C++ base or member initializer element to CFG.
1627 CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
1628 if (!BuildOpts.AddInitializers)
1631 bool HasTemporaries = false;
1633 // Destructors of temporaries in initialization expression should be called
1634 // after initialization finishes.
1635 Expr *Init = I->getInit();
1637 HasTemporaries = isa<ExprWithCleanups>(Init);
1639 if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
1640 // Generate destructors for temporaries in initialization expression.
1641 TempDtorContext Context;
1642 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
1643 /*ExternallyDestructed=*/false, Context);
1648 appendInitializer(Block, I);
1651 findConstructionContexts(
1652 ConstructionContextLayer::create(cfg->getBumpVectorContext(), I),
1655 if (HasTemporaries) {
1656 // For expression with temporaries go directly to subexpression to omit
1657 // generating destructors for the second time.
1658 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
1660 if (BuildOpts.AddCXXDefaultInitExprInCtors) {
1661 if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) {
1662 // In general, appending the expression wrapped by a CXXDefaultInitExpr
1663 // may cause the same Expr to appear more than once in the CFG. Doing it
1664 // here is safe because there's only one initializer per field.
1666 appendStmt(Block, Default);
1667 if (Stmt *Child = Default->getExpr())
1668 if (CFGBlock *R = Visit(Child))
1679 /// Retrieve the type of the temporary object whose lifetime was
1680 /// extended by a local reference with the given initializer.
1681 static QualType getReferenceInitTemporaryType(const Expr *Init,
1682 bool *FoundMTE = nullptr) {
1684 // Skip parentheses.
1685 Init = Init->IgnoreParens();
1687 // Skip through cleanups.
1688 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) {
1689 Init = EWC->getSubExpr();
1693 // Skip through the temporary-materialization expression.
1694 if (const MaterializeTemporaryExpr *MTE
1695 = dyn_cast<MaterializeTemporaryExpr>(Init)) {
1696 Init = MTE->getSubExpr();
1702 // Skip sub-object accesses into rvalues.
1703 SmallVector<const Expr *, 2> CommaLHSs;
1704 SmallVector<SubobjectAdjustment, 2> Adjustments;
1705 const Expr *SkippedInit =
1706 Init->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments);
1707 if (SkippedInit != Init) {
1715 return Init->getType();
1718 // TODO: Support adding LoopExit element to the CFG in case where the loop is
1719 // ended by ReturnStmt, GotoStmt or ThrowExpr.
1720 void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
1721 if(!BuildOpts.AddLoopExit)
1724 appendLoopExit(Block, LoopStmt);
1727 void CFGBuilder::getDeclsWithEndedScope(LocalScope::const_iterator B,
1728 LocalScope::const_iterator E, Stmt *S) {
1729 if (!BuildOpts.AddScopes)
1735 // To go from B to E, one first goes up the scopes from B to P
1736 // then sideways in one scope from P to P' and then down
1737 // the scopes from P' to E.
1738 // The lifetime of all objects between B and P end.
1739 LocalScope::const_iterator P = B.shared_parent(E);
1740 int Dist = B.distance(P);
1744 for (LocalScope::const_iterator I = B; I != P; ++I)
1745 if (I.pointsToFirstDeclaredVar())
1746 DeclsWithEndedScope.insert(*I);
1749 void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
1750 LocalScope::const_iterator E,
1752 getDeclsWithEndedScope(B, E, S);
1753 if (BuildOpts.AddScopes)
1754 addScopesEnd(B, E, S);
1755 if (BuildOpts.AddImplicitDtors)
1756 addAutomaticObjDtors(B, E, S);
1757 if (BuildOpts.AddLifetime)
1758 addLifetimeEnds(B, E, S);
1761 /// Add to current block automatic objects that leave the scope.
1762 void CFGBuilder::addLifetimeEnds(LocalScope::const_iterator B,
1763 LocalScope::const_iterator E, Stmt *S) {
1764 if (!BuildOpts.AddLifetime)
1770 // To go from B to E, one first goes up the scopes from B to P
1771 // then sideways in one scope from P to P' and then down
1772 // the scopes from P' to E.
1773 // The lifetime of all objects between B and P end.
1774 LocalScope::const_iterator P = B.shared_parent(E);
1775 int dist = B.distance(P);
1779 // We need to perform the scope leaving in reverse order
1780 SmallVector<VarDecl *, 10> DeclsTrivial;
1781 SmallVector<VarDecl *, 10> DeclsNonTrivial;
1782 DeclsTrivial.reserve(dist);
1783 DeclsNonTrivial.reserve(dist);
1785 for (LocalScope::const_iterator I = B; I != P; ++I)
1786 if (hasTrivialDestructor(*I))
1787 DeclsTrivial.push_back(*I);
1789 DeclsNonTrivial.push_back(*I);
1792 // object with trivial destructor end their lifetime last (when storage
1794 for (SmallVectorImpl<VarDecl *>::reverse_iterator I = DeclsTrivial.rbegin(),
1795 E = DeclsTrivial.rend();
1797 appendLifetimeEnds(Block, *I, S);
1799 for (SmallVectorImpl<VarDecl *>::reverse_iterator
1800 I = DeclsNonTrivial.rbegin(),
1801 E = DeclsNonTrivial.rend();
1803 appendLifetimeEnds(Block, *I, S);
1806 /// Add to current block markers for ending scopes.
1807 void CFGBuilder::addScopesEnd(LocalScope::const_iterator B,
1808 LocalScope::const_iterator E, Stmt *S) {
1809 // If implicit destructors are enabled, we'll add scope ends in
1810 // addAutomaticObjDtors.
1811 if (BuildOpts.AddImplicitDtors)
1816 for (auto I = DeclsWithEndedScope.rbegin(), E = DeclsWithEndedScope.rend();
1818 appendScopeEnd(Block, *I, S);
1823 /// addAutomaticObjDtors - Add to current block automatic objects destructors
1824 /// for objects in range of local scope positions. Use S as trigger statement
1825 /// for destructors.
1826 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
1827 LocalScope::const_iterator E, Stmt *S) {
1828 if (!BuildOpts.AddImplicitDtors)
1834 // We need to append the destructors in reverse order, but any one of them
1835 // may be a no-return destructor which changes the CFG. As a result, buffer
1836 // this sequence up and replay them in reverse order when appending onto the
1838 SmallVector<VarDecl*, 10> Decls;
1839 Decls.reserve(B.distance(E));
1840 for (LocalScope::const_iterator I = B; I != E; ++I)
1841 Decls.push_back(*I);
1843 for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(),
1846 if (hasTrivialDestructor(*I)) {
1847 // If AddScopes is enabled and *I is a first variable in a scope, add a
1848 // ScopeEnd marker in a Block.
1849 if (BuildOpts.AddScopes && DeclsWithEndedScope.count(*I)) {
1851 appendScopeEnd(Block, *I, S);
1855 // If this destructor is marked as a no-return destructor, we need to
1856 // create a new block for the destructor which does not have as a successor
1857 // anything built thus far: control won't flow out of this block.
1858 QualType Ty = (*I)->getType();
1859 if (Ty->isReferenceType()) {
1860 Ty = getReferenceInitTemporaryType((*I)->getInit());
1862 Ty = Context->getBaseElementType(Ty);
1864 if (Ty->getAsCXXRecordDecl()->isAnyDestructorNoReturn())
1865 Block = createNoReturnBlock();
1869 // Add ScopeEnd just after automatic obj destructor.
1870 if (BuildOpts.AddScopes && DeclsWithEndedScope.count(*I))
1871 appendScopeEnd(Block, *I, S);
1872 appendAutomaticObjDtor(Block, *I, S);
1876 /// addImplicitDtorsForDestructor - Add implicit destructors generated for
1877 /// base and member objects in destructor.
1878 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
1879 assert(BuildOpts.AddImplicitDtors &&
1880 "Can be called only when dtors should be added");
1881 const CXXRecordDecl *RD = DD->getParent();
1883 // At the end destroy virtual base objects.
1884 for (const auto &VI : RD->vbases()) {
1885 // TODO: Add a VirtualBaseBranch to see if the most derived class
1886 // (which is different from the current class) is responsible for
1888 const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl();
1889 if (!CD->hasTrivialDestructor()) {
1891 appendBaseDtor(Block, &VI);
1895 // Before virtual bases destroy direct base objects.
1896 for (const auto &BI : RD->bases()) {
1897 if (!BI.isVirtual()) {
1898 const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl();
1899 if (!CD->hasTrivialDestructor()) {
1901 appendBaseDtor(Block, &BI);
1906 // First destroy member objects.
1907 for (auto *FI : RD->fields()) {
1908 // Check for constant size array. Set type to array element type.
1909 QualType QT = FI->getType();
1910 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
1911 if (AT->getSize() == 0)
1913 QT = AT->getElementType();
1916 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
1917 if (!CD->hasTrivialDestructor()) {
1919 appendMemberDtor(Block, FI);
1924 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
1925 /// way return valid LocalScope object.
1926 LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
1929 llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
1930 return new (alloc.Allocate<LocalScope>())
1931 LocalScope(BumpVectorContext(alloc), ScopePos);
1934 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
1935 /// that should create implicit scope (e.g. if/else substatements).
1936 void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
1937 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
1938 !BuildOpts.AddScopes)
1941 LocalScope *Scope = nullptr;
1943 // For compound statement we will be creating explicit scope.
1944 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {
1945 for (auto *BI : CS->body()) {
1946 Stmt *SI = BI->stripLabelLikeStatements();
1947 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))
1948 Scope = addLocalScopeForDeclStmt(DS, Scope);
1953 // For any other statement scope will be implicit and as such will be
1954 // interesting only for DeclStmt.
1955 if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements()))
1956 addLocalScopeForDeclStmt(DS);
1959 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
1960 /// reuse Scope if not NULL.
1961 LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
1962 LocalScope* Scope) {
1963 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
1964 !BuildOpts.AddScopes)
1967 for (auto *DI : DS->decls())
1968 if (VarDecl *VD = dyn_cast<VarDecl>(DI))
1969 Scope = addLocalScopeForVarDecl(VD, Scope);
1973 bool CFGBuilder::hasTrivialDestructor(VarDecl *VD) {
1974 // Check for const references bound to temporary. Set type to pointee.
1975 QualType QT = VD->getType();
1976 if (QT->isReferenceType()) {
1977 // Attempt to determine whether this declaration lifetime-extends a
1980 // FIXME: This is incorrect. Non-reference declarations can lifetime-extend
1981 // temporaries, and a single declaration can extend multiple temporaries.
1982 // We should look at the storage duration on each nested
1983 // MaterializeTemporaryExpr instead.
1985 const Expr *Init = VD->getInit();
1987 // Probably an exception catch-by-reference variable.
1988 // FIXME: It doesn't really mean that the object has a trivial destructor.
1989 // Also are there other cases?
1993 // Lifetime-extending a temporary?
1994 bool FoundMTE = false;
1995 QT = getReferenceInitTemporaryType(Init, &FoundMTE);
2000 // Check for constant size array. Set type to array element type.
2001 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
2002 if (AT->getSize() == 0)
2004 QT = AT->getElementType();
2007 // Check if type is a C++ class with non-trivial destructor.
2008 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
2009 return !CD->hasDefinition() || CD->hasTrivialDestructor();
2013 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
2014 /// create add scope for automatic objects and temporary objects bound to
2015 /// const reference. Will reuse Scope if not NULL.
2016 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
2017 LocalScope* Scope) {
2018 assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
2019 "AddImplicitDtors and AddLifetime cannot be used at the same time");
2020 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
2021 !BuildOpts.AddScopes)
2024 // Check if variable is local.
2025 switch (VD->getStorageClass()) {
2030 default: return Scope;
2033 if (BuildOpts.AddImplicitDtors) {
2034 if (!hasTrivialDestructor(VD) || BuildOpts.AddScopes) {
2035 // Add the variable to scope
2036 Scope = createOrReuseLocalScope(Scope);
2038 ScopePos = Scope->begin();
2043 assert(BuildOpts.AddLifetime);
2044 // Add the variable to scope
2045 Scope = createOrReuseLocalScope(Scope);
2047 ScopePos = Scope->begin();
2051 /// addLocalScopeAndDtors - For given statement add local scope for it and
2052 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
2053 void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
2054 LocalScope::const_iterator scopeBeginPos = ScopePos;
2055 addLocalScopeForStmt(S);
2056 addAutomaticObjHandling(ScopePos, scopeBeginPos, S);
2059 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
2060 /// variables with automatic storage duration to CFGBlock's elements vector.
2061 /// Elements will be prepended to physical beginning of the vector which
2062 /// happens to be logical end. Use blocks terminator as statement that specifies
2063 /// destructors call site.
2064 /// FIXME: This mechanism for adding automatic destructors doesn't handle
2065 /// no-return destructors properly.
2066 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
2067 LocalScope::const_iterator B, LocalScope::const_iterator E) {
2068 if (!BuildOpts.AddImplicitDtors)
2070 BumpVectorContext &C = cfg->getBumpVectorContext();
2071 CFGBlock::iterator InsertPos
2072 = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
2073 for (LocalScope::const_iterator I = B; I != E; ++I)
2074 InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I,
2075 Blk->getTerminatorStmt());
2078 /// prependAutomaticObjLifetimeWithTerminator - Prepend lifetime CFGElements for
2079 /// variables with automatic storage duration to CFGBlock's elements vector.
2080 /// Elements will be prepended to physical beginning of the vector which
2081 /// happens to be logical end. Use blocks terminator as statement that specifies
2082 /// where lifetime ends.
2083 void CFGBuilder::prependAutomaticObjLifetimeWithTerminator(
2084 CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
2085 if (!BuildOpts.AddLifetime)
2087 BumpVectorContext &C = cfg->getBumpVectorContext();
2088 CFGBlock::iterator InsertPos =
2089 Blk->beginLifetimeEndsInsert(Blk->end(), B.distance(E), C);
2090 for (LocalScope::const_iterator I = B; I != E; ++I) {
2092 Blk->insertLifetimeEnds(InsertPos, *I, Blk->getTerminatorStmt());
2096 /// prependAutomaticObjScopeEndWithTerminator - Prepend scope end CFGElements for
2097 /// variables with automatic storage duration to CFGBlock's elements vector.
2098 /// Elements will be prepended to physical beginning of the vector which
2099 /// happens to be logical end. Use blocks terminator as statement that specifies
2100 /// where scope ends.
2102 CFGBuilder::prependAutomaticObjScopeEndWithTerminator(
2103 CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
2104 if (!BuildOpts.AddScopes)
2106 BumpVectorContext &C = cfg->getBumpVectorContext();
2107 CFGBlock::iterator InsertPos =
2108 Blk->beginScopeEndInsert(Blk->end(), 1, C);
2109 LocalScope::const_iterator PlaceToInsert = B;
2110 for (LocalScope::const_iterator I = B; I != E; ++I)
2112 Blk->insertScopeEnd(InsertPos, *PlaceToInsert, Blk->getTerminatorStmt());
2113 return *PlaceToInsert;
2116 /// Visit - Walk the subtree of a statement and add extra
2117 /// blocks for ternary operators, &&, and ||. We also process "," and
2118 /// DeclStmts (which may contain nested control-flow).
2119 CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc,
2120 bool ExternallyDestructed) {
2126 if (Expr *E = dyn_cast<Expr>(S))
2127 S = E->IgnoreParens();
2129 if (Context->getLangOpts().OpenMP)
2130 if (auto *D = dyn_cast<OMPExecutableDirective>(S))
2131 return VisitOMPExecutableDirective(D, asc);
2133 switch (S->getStmtClass()) {
2135 return VisitStmt(S, asc);
2137 case Stmt::ImplicitValueInitExprClass:
2138 if (BuildOpts.OmitImplicitValueInitializers)
2140 return VisitStmt(S, asc);
2142 case Stmt::InitListExprClass:
2143 return VisitInitListExpr(cast<InitListExpr>(S), asc);
2145 case Stmt::AddrLabelExprClass:
2146 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
2148 case Stmt::BinaryConditionalOperatorClass:
2149 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
2151 case Stmt::BinaryOperatorClass:
2152 return VisitBinaryOperator(cast<BinaryOperator>(S), asc);
2154 case Stmt::BlockExprClass:
2155 return VisitBlockExpr(cast<BlockExpr>(S), asc);
2157 case Stmt::BreakStmtClass:
2158 return VisitBreakStmt(cast<BreakStmt>(S));
2160 case Stmt::CallExprClass:
2161 case Stmt::CXXOperatorCallExprClass:
2162 case Stmt::CXXMemberCallExprClass:
2163 case Stmt::UserDefinedLiteralClass:
2164 return VisitCallExpr(cast<CallExpr>(S), asc);
2166 case Stmt::CaseStmtClass:
2167 return VisitCaseStmt(cast<CaseStmt>(S));
2169 case Stmt::ChooseExprClass:
2170 return VisitChooseExpr(cast<ChooseExpr>(S), asc);
2172 case Stmt::CompoundStmtClass:
2173 return VisitCompoundStmt(cast<CompoundStmt>(S), ExternallyDestructed);
2175 case Stmt::ConditionalOperatorClass:
2176 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);
2178 case Stmt::ContinueStmtClass:
2179 return VisitContinueStmt(cast<ContinueStmt>(S));
2181 case Stmt::CXXCatchStmtClass:
2182 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));
2184 case Stmt::ExprWithCleanupsClass:
2185 return VisitExprWithCleanups(cast<ExprWithCleanups>(S),
2186 asc, ExternallyDestructed);
2188 case Stmt::CXXDefaultArgExprClass:
2189 case Stmt::CXXDefaultInitExprClass:
2190 // FIXME: The expression inside a CXXDefaultArgExpr is owned by the
2191 // called function's declaration, not by the caller. If we simply add
2192 // this expression to the CFG, we could end up with the same Expr
2193 // appearing multiple times.
2194 // PR13385 / <rdar://problem/12156507>
2196 // It's likewise possible for multiple CXXDefaultInitExprs for the same
2197 // expression to be used in the same function (through aggregate
2199 return VisitStmt(S, asc);
2201 case Stmt::CXXBindTemporaryExprClass:
2202 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);
2204 case Stmt::CXXConstructExprClass:
2205 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
2207 case Stmt::CXXNewExprClass:
2208 return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc);
2210 case Stmt::CXXDeleteExprClass:
2211 return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc);
2213 case Stmt::CXXFunctionalCastExprClass:
2214 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);
2216 case Stmt::CXXTemporaryObjectExprClass:
2217 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);
2219 case Stmt::CXXThrowExprClass:
2220 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));
2222 case Stmt::CXXTryStmtClass:
2223 return VisitCXXTryStmt(cast<CXXTryStmt>(S));
2225 case Stmt::CXXForRangeStmtClass:
2226 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));
2228 case Stmt::DeclStmtClass:
2229 return VisitDeclStmt(cast<DeclStmt>(S));
2231 case Stmt::DefaultStmtClass:
2232 return VisitDefaultStmt(cast<DefaultStmt>(S));
2234 case Stmt::DoStmtClass:
2235 return VisitDoStmt(cast<DoStmt>(S));
2237 case Stmt::ForStmtClass:
2238 return VisitForStmt(cast<ForStmt>(S));
2240 case Stmt::GotoStmtClass:
2241 return VisitGotoStmt(cast<GotoStmt>(S));
2243 case Stmt::GCCAsmStmtClass:
2244 return VisitGCCAsmStmt(cast<GCCAsmStmt>(S), asc);
2246 case Stmt::IfStmtClass:
2247 return VisitIfStmt(cast<IfStmt>(S));
2249 case Stmt::ImplicitCastExprClass:
2250 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);
2252 case Stmt::ConstantExprClass:
2253 return VisitConstantExpr(cast<ConstantExpr>(S), asc);
2255 case Stmt::IndirectGotoStmtClass:
2256 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));
2258 case Stmt::LabelStmtClass:
2259 return VisitLabelStmt(cast<LabelStmt>(S));
2261 case Stmt::LambdaExprClass:
2262 return VisitLambdaExpr(cast<LambdaExpr>(S), asc);
2264 case Stmt::MaterializeTemporaryExprClass:
2265 return VisitMaterializeTemporaryExpr(cast<MaterializeTemporaryExpr>(S),
2268 case Stmt::MemberExprClass:
2269 return VisitMemberExpr(cast<MemberExpr>(S), asc);
2271 case Stmt::NullStmtClass:
2274 case Stmt::ObjCAtCatchStmtClass:
2275 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));
2277 case Stmt::ObjCAutoreleasePoolStmtClass:
2278 return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S));
2280 case Stmt::ObjCAtSynchronizedStmtClass:
2281 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));
2283 case Stmt::ObjCAtThrowStmtClass:
2284 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));
2286 case Stmt::ObjCAtTryStmtClass:
2287 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));
2289 case Stmt::ObjCForCollectionStmtClass:
2290 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));
2292 case Stmt::ObjCMessageExprClass:
2293 return VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), asc);
2295 case Stmt::OpaqueValueExprClass:
2298 case Stmt::PseudoObjectExprClass:
2299 return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S));
2301 case Stmt::ReturnStmtClass:
2302 case Stmt::CoreturnStmtClass:
2303 return VisitReturnStmt(S);
2305 case Stmt::SEHExceptStmtClass:
2306 return VisitSEHExceptStmt(cast<SEHExceptStmt>(S));
2308 case Stmt::SEHFinallyStmtClass:
2309 return VisitSEHFinallyStmt(cast<SEHFinallyStmt>(S));
2311 case Stmt::SEHLeaveStmtClass:
2312 return VisitSEHLeaveStmt(cast<SEHLeaveStmt>(S));
2314 case Stmt::SEHTryStmtClass:
2315 return VisitSEHTryStmt(cast<SEHTryStmt>(S));
2317 case Stmt::UnaryExprOrTypeTraitExprClass:
2318 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
2321 case Stmt::StmtExprClass:
2322 return VisitStmtExpr(cast<StmtExpr>(S), asc);
2324 case Stmt::SwitchStmtClass:
2325 return VisitSwitchStmt(cast<SwitchStmt>(S));
2327 case Stmt::UnaryOperatorClass:
2328 return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
2330 case Stmt::WhileStmtClass:
2331 return VisitWhileStmt(cast<WhileStmt>(S));
2335 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
2336 if (asc.alwaysAdd(*this, S)) {
2338 appendStmt(Block, S);
2341 return VisitChildren(S);
2344 /// VisitChildren - Visit the children of a Stmt.
2345 CFGBlock *CFGBuilder::VisitChildren(Stmt *S) {
2346 CFGBlock *B = Block;
2348 // Visit the children in their reverse order so that they appear in
2349 // left-to-right (natural) order in the CFG.
2350 reverse_children RChildren(S);
2351 for (Stmt *Child : RChildren) {
2353 if (CFGBlock *R = Visit(Child))
2359 CFGBlock *CFGBuilder::VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc) {
2360 if (asc.alwaysAdd(*this, ILE)) {
2362 appendStmt(Block, ILE);
2364 CFGBlock *B = Block;
2366 reverse_children RChildren(ILE);
2367 for (Stmt *Child : RChildren) {
2370 if (CFGBlock *R = Visit(Child))
2372 if (BuildOpts.AddCXXDefaultInitExprInAggregates) {
2373 if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Child))
2374 if (Stmt *Child = DIE->getExpr())
2375 if (CFGBlock *R = Visit(Child))
2382 CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
2383 AddStmtChoice asc) {
2384 AddressTakenLabels.insert(A->getLabel());
2386 if (asc.alwaysAdd(*this, A)) {
2388 appendStmt(Block, A);
2394 CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U,
2395 AddStmtChoice asc) {
2396 if (asc.alwaysAdd(*this, U)) {
2398 appendStmt(Block, U);
2401 if (U->getOpcode() == UO_LNot)
2402 tryEvaluateBool(U->getSubExpr()->IgnoreParens());
2404 return Visit(U->getSubExpr(), AddStmtChoice());
2407 CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) {
2408 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2409 appendStmt(ConfluenceBlock, B);
2414 return VisitLogicalOperator(B, nullptr, ConfluenceBlock,
2415 ConfluenceBlock).first;
2418 std::pair<CFGBlock*, CFGBlock*>
2419 CFGBuilder::VisitLogicalOperator(BinaryOperator *B,
2421 CFGBlock *TrueBlock,
2422 CFGBlock *FalseBlock) {
2423 // Introspect the RHS. If it is a nested logical operation, we recursively
2424 // build the CFG using this function. Otherwise, resort to default
2425 // CFG construction behavior.
2426 Expr *RHS = B->getRHS()->IgnoreParens();
2427 CFGBlock *RHSBlock, *ExitBlock;
2430 if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(RHS))
2431 if (B_RHS->isLogicalOp()) {
2432 std::tie(RHSBlock, ExitBlock) =
2433 VisitLogicalOperator(B_RHS, Term, TrueBlock, FalseBlock);
2437 // The RHS is not a nested logical operation. Don't push the terminator
2438 // down further, but instead visit RHS and construct the respective
2439 // pieces of the CFG, and link up the RHSBlock with the terminator
2440 // we have been provided.
2441 ExitBlock = RHSBlock = createBlock(false);
2443 // Even though KnownVal is only used in the else branch of the next
2444 // conditional, tryEvaluateBool performs additional checking on the
2445 // Expr, so it should be called unconditionally.
2446 TryResult KnownVal = tryEvaluateBool(RHS);
2447 if (!KnownVal.isKnown())
2448 KnownVal = tryEvaluateBool(B);
2451 assert(TrueBlock == FalseBlock);
2452 addSuccessor(RHSBlock, TrueBlock);
2455 RHSBlock->setTerminator(Term);
2456 addSuccessor(RHSBlock, TrueBlock, !KnownVal.isFalse());
2457 addSuccessor(RHSBlock, FalseBlock, !KnownVal.isTrue());
2461 RHSBlock = addStmt(RHS);
2466 return std::make_pair(nullptr, nullptr);
2468 // Generate the blocks for evaluating the LHS.
2469 Expr *LHS = B->getLHS()->IgnoreParens();
2471 if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(LHS))
2472 if (B_LHS->isLogicalOp()) {
2473 if (B->getOpcode() == BO_LOr)
2474 FalseBlock = RHSBlock;
2476 TrueBlock = RHSBlock;
2478 // For the LHS, treat 'B' as the terminator that we want to sink
2479 // into the nested branch. The RHS always gets the top-most
2481 return VisitLogicalOperator(B_LHS, B, TrueBlock, FalseBlock);
2484 // Create the block evaluating the LHS.
2485 // This contains the '&&' or '||' as the terminator.
2486 CFGBlock *LHSBlock = createBlock(false);
2487 LHSBlock->setTerminator(B);
2490 CFGBlock *EntryLHSBlock = addStmt(LHS);
2493 return std::make_pair(nullptr, nullptr);
2495 // See if this is a known constant.
2496 TryResult KnownVal = tryEvaluateBool(LHS);
2498 // Now link the LHSBlock with RHSBlock.
2499 if (B->getOpcode() == BO_LOr) {
2500 addSuccessor(LHSBlock, TrueBlock, !KnownVal.isFalse());
2501 addSuccessor(LHSBlock, RHSBlock, !KnownVal.isTrue());
2503 assert(B->getOpcode() == BO_LAnd);
2504 addSuccessor(LHSBlock, RHSBlock, !KnownVal.isFalse());
2505 addSuccessor(LHSBlock, FalseBlock, !KnownVal.isTrue());
2508 return std::make_pair(EntryLHSBlock, ExitBlock);
2511 CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
2512 AddStmtChoice asc) {
2514 if (B->isLogicalOp())
2515 return VisitLogicalOperator(B);
2517 if (B->getOpcode() == BO_Comma) { // ,
2519 appendStmt(Block, B);
2520 addStmt(B->getRHS());
2521 return addStmt(B->getLHS());
2524 if (B->isAssignmentOp()) {
2525 if (asc.alwaysAdd(*this, B)) {
2527 appendStmt(Block, B);
2530 return Visit(B->getRHS());
2533 if (asc.alwaysAdd(*this, B)) {
2535 appendStmt(Block, B);
2538 if (B->isEqualityOp() || B->isRelationalOp())
2541 CFGBlock *RBlock = Visit(B->getRHS());
2542 CFGBlock *LBlock = Visit(B->getLHS());
2543 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
2544 // containing a DoStmt, and the LHS doesn't create a new block, then we should
2545 // return RBlock. Otherwise we'll incorrectly return NULL.
2546 return (LBlock ? LBlock : RBlock);
2549 CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) {
2550 if (asc.alwaysAdd(*this, E)) {
2552 appendStmt(Block, E);
2557 CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
2558 // "break" is a control-flow statement. Thus we stop processing the current
2563 // Now create a new block that ends with the break statement.
2564 Block = createBlock(false);
2565 Block->setTerminator(B);
2567 // If there is no target for the break, then we are looking at an incomplete
2568 // AST. This means that the CFG cannot be constructed.
2569 if (BreakJumpTarget.block) {
2570 addAutomaticObjHandling(ScopePos, BreakJumpTarget.scopePosition, B);
2571 addSuccessor(Block, BreakJumpTarget.block);
2578 static bool CanThrow(Expr *E, ASTContext &Ctx) {
2579 QualType Ty = E->getType();
2580 if (Ty->isFunctionPointerType() || Ty->isBlockPointerType())
2581 Ty = Ty->getPointeeType();
2583 const FunctionType *FT = Ty->getAs<FunctionType>();
2585 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
2586 if (!isUnresolvedExceptionSpec(Proto->getExceptionSpecType()) &&
2593 CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
2594 // Compute the callee type.
2595 QualType calleeType = C->getCallee()->getType();
2596 if (calleeType == Context->BoundMemberTy) {
2597 QualType boundType = Expr::findBoundMemberType(C->getCallee());
2599 // We should only get a null bound type if processing a dependent
2600 // CFG. Recover by assuming nothing.
2601 if (!boundType.isNull()) calleeType = boundType;
2604 // If this is a call to a no-return function, this stops the block here.
2605 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();
2607 bool AddEHEdge = false;
2609 // Languages without exceptions are assumed to not throw.
2610 if (Context->getLangOpts().Exceptions) {
2611 if (BuildOpts.AddEHEdges)
2615 // If this is a call to a builtin function, it might not actually evaluate
2616 // its arguments. Don't add them to the CFG if this is the case.
2617 bool OmitArguments = false;
2619 if (FunctionDecl *FD = C->getDirectCallee()) {
2620 // TODO: Support construction contexts for variadic function arguments.
2621 // These are a bit problematic and not very useful because passing
2622 // C++ objects as C-style variadic arguments doesn't work in general
2623 // (see [expr.call]).
2624 if (!FD->isVariadic())
2625 findConstructionContextsForArguments(C);
2627 if (FD->isNoReturn() || C->isBuiltinAssumeFalse(*Context))
2629 if (FD->hasAttr<NoThrowAttr>())
2631 if (FD->getBuiltinID() == Builtin::BI__builtin_object_size ||
2632 FD->getBuiltinID() == Builtin::BI__builtin_dynamic_object_size)
2633 OmitArguments = true;
2636 if (!CanThrow(C->getCallee(), *Context))
2639 if (OmitArguments) {
2640 assert(!NoReturn && "noreturn calls with unevaluated args not implemented");
2641 assert(!AddEHEdge && "EH calls with unevaluated args not implemented");
2643 appendStmt(Block, C);
2644 return Visit(C->getCallee());
2647 if (!NoReturn && !AddEHEdge) {
2649 appendCall(Block, C);
2651 return VisitChildren(C);
2661 Block = createNoReturnBlock();
2663 Block = createBlock();
2665 appendCall(Block, C);
2668 // Add exceptional edges.
2669 if (TryTerminatedBlock)
2670 addSuccessor(Block, TryTerminatedBlock);
2672 addSuccessor(Block, &cfg->getExit());
2675 return VisitChildren(C);
2678 CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
2679 AddStmtChoice asc) {
2680 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2681 appendStmt(ConfluenceBlock, C);
2685 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
2686 Succ = ConfluenceBlock;
2688 CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd);
2692 Succ = ConfluenceBlock;
2694 CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd);
2698 Block = createBlock(false);
2699 // See if this is a known constant.
2700 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
2701 addSuccessor(Block, KnownVal.isFalse() ? nullptr : LHSBlock);
2702 addSuccessor(Block, KnownVal.isTrue() ? nullptr : RHSBlock);
2703 Block->setTerminator(C);
2704 return addStmt(C->getCond());
2707 CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed) {
2708 LocalScope::const_iterator scopeBeginPos = ScopePos;
2709 addLocalScopeForStmt(C);
2711 if (!C->body_empty() && !isa<ReturnStmt>(*C->body_rbegin())) {
2712 // If the body ends with a ReturnStmt, the dtors will be added in
2714 addAutomaticObjHandling(ScopePos, scopeBeginPos, C);
2717 CFGBlock *LastBlock = Block;
2719 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
2721 // If we hit a segment of code just containing ';' (NullStmts), we can
2722 // get a null block back. In such cases, just use the LastBlock
2723 CFGBlock *newBlock = Visit(*I, AddStmtChoice::AlwaysAdd,
2724 ExternallyDestructed);
2727 LastBlock = newBlock;
2732 ExternallyDestructed = false;
2738 CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
2739 AddStmtChoice asc) {
2740 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);
2741 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr);
2743 // Create the confluence block that will "merge" the results of the ternary
2745 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2746 appendStmt(ConfluenceBlock, C);
2750 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
2752 // Create a block for the LHS expression if there is an LHS expression. A
2753 // GCC extension allows LHS to be NULL, causing the condition to be the
2754 // value that is returned instead.
2755 // e.g: x ?: y is shorthand for: x ? x : y;
2756 Succ = ConfluenceBlock;
2758 CFGBlock *LHSBlock = nullptr;
2759 const Expr *trueExpr = C->getTrueExpr();
2760 if (trueExpr != opaqueValue) {
2761 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);
2767 LHSBlock = ConfluenceBlock;
2769 // Create the block for the RHS expression.
2770 Succ = ConfluenceBlock;
2771 CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);
2775 // If the condition is a logical '&&' or '||', build a more accurate CFG.
2776 if (BinaryOperator *Cond =
2777 dyn_cast<BinaryOperator>(C->getCond()->IgnoreParens()))
2778 if (Cond->isLogicalOp())
2779 return VisitLogicalOperator(Cond, C, LHSBlock, RHSBlock).first;
2781 // Create the block that will contain the condition.
2782 Block = createBlock(false);
2784 // See if this is a known constant.
2785 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
2786 addSuccessor(Block, LHSBlock, !KnownVal.isFalse());
2787 addSuccessor(Block, RHSBlock, !KnownVal.isTrue());
2788 Block->setTerminator(C);
2789 Expr *condExpr = C->getCond();
2792 // Run the condition expression if it's not trivially expressed in
2793 // terms of the opaque value (or if there is no opaque value).
2794 if (condExpr != opaqueValue)
2797 // Before that, run the common subexpression if there was one.
2798 // At least one of this or the above will be run.
2799 return addStmt(BCO->getCommon());
2802 return addStmt(condExpr);
2805 CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
2806 // Check if the Decl is for an __label__. If so, elide it from the
2808 if (isa<LabelDecl>(*DS->decl_begin()))
2811 // This case also handles static_asserts.
2812 if (DS->isSingleDecl())
2813 return VisitDeclSubExpr(DS);
2815 CFGBlock *B = nullptr;
2817 // Build an individual DeclStmt for each decl.
2818 for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(),
2819 E = DS->decl_rend();
2822 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
2823 // automatically freed with the CFG.
2824 DeclGroupRef DG(*I);
2826 DeclStmt *DSNew = new (Context) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
2827 cfg->addSyntheticDeclStmt(DSNew, DS);
2829 // Append the fake DeclStmt to block.
2830 B = VisitDeclSubExpr(DSNew);
2836 /// VisitDeclSubExpr - Utility method to add block-level expressions for
2837 /// DeclStmts and initializers in them.
2838 CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
2839 assert(DS->isSingleDecl() && "Can handle single declarations only.");
2841 if (const auto *TND = dyn_cast<TypedefNameDecl>(DS->getSingleDecl())) {
2842 // If we encounter a VLA, process its size expressions.
2843 const Type *T = TND->getUnderlyingType().getTypePtr();
2844 if (!T->isVariablyModifiedType())
2848 appendStmt(Block, DS);
2850 CFGBlock *LastBlock = Block;
2851 for (const VariableArrayType *VA = FindVA(T); VA != nullptr;
2852 VA = FindVA(VA->getElementType().getTypePtr())) {
2853 if (CFGBlock *NewBlock = addStmt(VA->getSizeExpr()))
2854 LastBlock = NewBlock;
2859 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
2862 // Of everything that can be declared in a DeclStmt, only VarDecls and the
2863 // exceptions above impact runtime semantics.
2867 bool HasTemporaries = false;
2869 // Guard static initializers under a branch.
2870 CFGBlock *blockAfterStaticInit = nullptr;
2872 if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) {
2873 // For static variables, we need to create a branch to track
2874 // whether or not they are initialized.
2881 blockAfterStaticInit = Succ;
2884 // Destructors of temporaries in initialization expression should be called
2885 // after initialization finishes.
2886 Expr *Init = VD->getInit();
2888 HasTemporaries = isa<ExprWithCleanups>(Init);
2890 if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
2891 // Generate destructors for temporaries in initialization expression.
2892 TempDtorContext Context;
2893 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
2894 /*ExternallyDestructed=*/true, Context);
2899 appendStmt(Block, DS);
2901 findConstructionContexts(
2902 ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),
2905 // Keep track of the last non-null block, as 'Block' can be nulled out
2906 // if the initializer expression is something like a 'while' in a
2907 // statement-expression.
2908 CFGBlock *LastBlock = Block;
2911 if (HasTemporaries) {
2912 // For expression with temporaries go directly to subexpression to omit
2913 // generating destructors for the second time.
2914 ExprWithCleanups *EC = cast<ExprWithCleanups>(Init);
2915 if (CFGBlock *newBlock = Visit(EC->getSubExpr()))
2916 LastBlock = newBlock;
2919 if (CFGBlock *newBlock = Visit(Init))
2920 LastBlock = newBlock;
2924 // If the type of VD is a VLA, then we must process its size expressions.
2925 // FIXME: This does not find the VLA if it is embedded in other types,
2926 // like here: `int (*p_vla)[x];`
2927 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());
2928 VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr())) {
2929 if (CFGBlock *newBlock = addStmt(VA->getSizeExpr()))
2930 LastBlock = newBlock;
2933 maybeAddScopeBeginForVarDecl(Block, VD, DS);
2935 // Remove variable from local scope.
2936 if (ScopePos && VD == *ScopePos)
2939 CFGBlock *B = LastBlock;
2940 if (blockAfterStaticInit) {
2942 Block = createBlock(false);
2943 Block->setTerminator(DS);
2944 addSuccessor(Block, blockAfterStaticInit);
2945 addSuccessor(Block, B);
2952 CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
2953 // We may see an if statement in the middle of a basic block, or it may be the
2954 // first statement we are processing. In either case, we create a new basic
2955 // block. First, we create the blocks for the then...else statements, and
2956 // then we create the block containing the if statement. If we were in the
2957 // middle of a block, we stop processing that block. That block is then the
2958 // implicit successor for the "then" and "else" clauses.
2960 // Save local scope position because in case of condition variable ScopePos
2961 // won't be restored when traversing AST.
2962 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2964 // Create local scope for C++17 if init-stmt if one exists.
2965 if (Stmt *Init = I->getInit())
2966 addLocalScopeForStmt(Init);
2968 // Create local scope for possible condition variable.
2969 // Store scope position. Add implicit destructor.
2970 if (VarDecl *VD = I->getConditionVariable())
2971 addLocalScopeForVarDecl(VD);
2973 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), I);
2975 // The block we were processing is now finished. Make it the successor
2983 // Process the false branch.
2984 CFGBlock *ElseBlock = Succ;
2986 if (Stmt *Else = I->getElse()) {
2987 SaveAndRestore<CFGBlock*> sv(Succ);
2989 // NULL out Block so that the recursive call to Visit will
2990 // create a new basic block.
2993 // If branch is not a compound statement create implicit scope
2994 // and add destructors.
2995 if (!isa<CompoundStmt>(Else))
2996 addLocalScopeAndDtors(Else);
2998 ElseBlock = addStmt(Else);
3000 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
3001 ElseBlock = sv.get();
3008 // Process the true branch.
3009 CFGBlock *ThenBlock;
3011 Stmt *Then = I->getThen();
3013 SaveAndRestore<CFGBlock*> sv(Succ);
3016 // If branch is not a compound statement create implicit scope
3017 // and add destructors.
3018 if (!isa<CompoundStmt>(Then))
3019 addLocalScopeAndDtors(Then);
3021 ThenBlock = addStmt(Then);
3024 // We can reach here if the "then" body has all NullStmts.
3025 // Create an empty block so we can distinguish between true and false
3026 // branches in path-sensitive analyses.
3027 ThenBlock = createBlock(false);
3028 addSuccessor(ThenBlock, sv.get());
3035 // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by
3036 // having these handle the actual control-flow jump. Note that
3037 // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)"
3038 // we resort to the old control-flow behavior. This special handling
3039 // removes infeasible paths from the control-flow graph by having the
3040 // control-flow transfer of '&&' or '||' go directly into the then/else
3042 BinaryOperator *Cond =
3043 I->getConditionVariable()
3045 : dyn_cast<BinaryOperator>(I->getCond()->IgnoreParens());
3046 CFGBlock *LastBlock;
3047 if (Cond && Cond->isLogicalOp())
3048 LastBlock = VisitLogicalOperator(Cond, I, ThenBlock, ElseBlock).first;
3050 // Now create a new block containing the if statement.
3051 Block = createBlock(false);
3053 // Set the terminator of the new block to the If statement.
3054 Block->setTerminator(I);
3056 // See if this is a known constant.
3057 const TryResult &KnownVal = tryEvaluateBool(I->getCond());
3059 // Add the successors. If we know that specific branches are
3060 // unreachable, inform addSuccessor() of that knowledge.
3061 addSuccessor(Block, ThenBlock, /* IsReachable = */ !KnownVal.isFalse());
3062 addSuccessor(Block, ElseBlock, /* IsReachable = */ !KnownVal.isTrue());
3064 // Add the condition as the last statement in the new block. This may
3065 // create new blocks as the condition may contain control-flow. Any newly
3066 // created blocks will be pointed to be "Block".
3067 LastBlock = addStmt(I->getCond());
3069 // If the IfStmt contains a condition variable, add it and its
3070 // initializer to the CFG.
3071 if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) {
3073 LastBlock = addStmt(const_cast<DeclStmt *>(DS));
3077 // Finally, if the IfStmt contains a C++17 init-stmt, add it to the CFG.
3078 if (Stmt *Init = I->getInit()) {
3080 LastBlock = addStmt(Init);
3086 CFGBlock *CFGBuilder::VisitReturnStmt(Stmt *S) {
3087 // If we were in the middle of a block we stop processing that block.
3089 // NOTE: If a "return" or "co_return" appears in the middle of a block, this
3090 // means that the code afterwards is DEAD (unreachable). We still keep
3091 // a basic block for that code; a simple "mark-and-sweep" from the entry
3092 // block will be able to report such dead blocks.
3093 assert(isa<ReturnStmt>(S) || isa<CoreturnStmt>(S));
3095 // Create the new block.
3096 Block = createBlock(false);
3098 addAutomaticObjHandling(ScopePos, LocalScope::const_iterator(), S);
3100 if (auto *R = dyn_cast<ReturnStmt>(S))
3101 findConstructionContexts(
3102 ConstructionContextLayer::create(cfg->getBumpVectorContext(), R),
3105 // If the one of the destructors does not return, we already have the Exit
3106 // block as a successor.
3107 if (!Block->hasNoReturnElement())
3108 addSuccessor(Block, &cfg->getExit());
3110 // Add the return statement to the block.
3111 appendStmt(Block, S);
3114 if (ReturnStmt *RS = dyn_cast<ReturnStmt>(S)) {
3115 if (Expr *O = RS->getRetValue())
3116 return Visit(O, AddStmtChoice::AlwaysAdd, /*ExternallyDestructed=*/true);
3118 } else { // co_return
3119 return VisitChildren(S);
3123 CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) {
3124 // SEHExceptStmt are treated like labels, so they are the first statement in a
3127 // Save local scope position because in case of exception variable ScopePos
3128 // won't be restored when traversing AST.
3129 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3131 addStmt(ES->getBlock());
3132 CFGBlock *SEHExceptBlock = Block;
3133 if (!SEHExceptBlock)
3134 SEHExceptBlock = createBlock();
3136 appendStmt(SEHExceptBlock, ES);
3138 // Also add the SEHExceptBlock as a label, like with regular labels.
3139 SEHExceptBlock->setLabel(ES);
3141 // Bail out if the CFG is bad.
3145 // We set Block to NULL to allow lazy creation of a new block (if necessary).
3148 return SEHExceptBlock;
3151 CFGBlock *CFGBuilder::VisitSEHFinallyStmt(SEHFinallyStmt *FS) {
3152 return VisitCompoundStmt(FS->getBlock(), /*ExternallyDestructed=*/false);
3155 CFGBlock *CFGBuilder::VisitSEHLeaveStmt(SEHLeaveStmt *LS) {
3156 // "__leave" is a control-flow statement. Thus we stop processing the current
3161 // Now create a new block that ends with the __leave statement.
3162 Block = createBlock(false);
3163 Block->setTerminator(LS);
3165 // If there is no target for the __leave, then we are looking at an incomplete
3166 // AST. This means that the CFG cannot be constructed.
3167 if (SEHLeaveJumpTarget.block) {
3168 addAutomaticObjHandling(ScopePos, SEHLeaveJumpTarget.scopePosition, LS);
3169 addSuccessor(Block, SEHLeaveJumpTarget.block);
3176 CFGBlock *CFGBuilder::VisitSEHTryStmt(SEHTryStmt *Terminator) {
3177 // "__try"/"__except"/"__finally" is a control-flow statement. Thus we stop
3178 // processing the current block.
3179 CFGBlock *SEHTrySuccessor = nullptr;
3184 SEHTrySuccessor = Block;
3185 } else SEHTrySuccessor = Succ;
3187 // FIXME: Implement __finally support.
3188 if (Terminator->getFinallyHandler())
3191 CFGBlock *PrevSEHTryTerminatedBlock = TryTerminatedBlock;
3193 // Create a new block that will contain the __try statement.
3194 CFGBlock *NewTryTerminatedBlock = createBlock(false);
3196 // Add the terminator in the __try block.
3197 NewTryTerminatedBlock->setTerminator(Terminator);
3199 if (SEHExceptStmt *Except = Terminator->getExceptHandler()) {
3200 // The code after the try is the implicit successor if there's an __except.
3201 Succ = SEHTrySuccessor;
3203 CFGBlock *ExceptBlock = VisitSEHExceptStmt(Except);
3206 // Add this block to the list of successors for the block with the try
3208 addSuccessor(NewTryTerminatedBlock, ExceptBlock);
3210 if (PrevSEHTryTerminatedBlock)
3211 addSuccessor(NewTryTerminatedBlock, PrevSEHTryTerminatedBlock);
3213 addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
3215 // The code after the try is the implicit successor.
3216 Succ = SEHTrySuccessor;
3218 // Save the current "__try" context.
3219 SaveAndRestore<CFGBlock *> save_try(TryTerminatedBlock,
3220 NewTryTerminatedBlock);
3221 cfg->addTryDispatchBlock(TryTerminatedBlock);
3223 // Save the current value for the __leave target.
3224 // All __leaves should go to the code following the __try
3225 // (FIXME: or if the __try has a __finally, to the __finally.)
3226 SaveAndRestore<JumpTarget> save_break(SEHLeaveJumpTarget);
3227 SEHLeaveJumpTarget = JumpTarget(SEHTrySuccessor, ScopePos);
3229 assert(Terminator->getTryBlock() && "__try must contain a non-NULL body");
3231 return addStmt(Terminator->getTryBlock());
3234 CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
3235 // Get the block of the labeled statement. Add it to our map.
3236 addStmt(L->getSubStmt());
3237 CFGBlock *LabelBlock = Block;
3239 if (!LabelBlock) // This can happen when the body is empty, i.e.
3240 LabelBlock = createBlock(); // scopes that only contains NullStmts.
3242 assert(LabelMap.find(L->getDecl()) == LabelMap.end() &&
3243 "label already in map");
3244 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
3246 // Labels partition blocks, so this is the end of the basic block we were
3247 // processing (L is the block's label). Because this is label (and we have
3248 // already processed the substatement) there is no extra control-flow to worry
3250 LabelBlock->setLabel(L);
3254 // We set Block to NULL to allow lazy creation of a new block (if necessary);
3257 // This block is now the implicit successor of other blocks.
3263 CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
3264 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3265 for (const BlockDecl::Capture &CI : E->getBlockDecl()->captures()) {
3266 if (Expr *CopyExpr = CI.getCopyExpr()) {
3267 CFGBlock *Tmp = Visit(CopyExpr);
3275 CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
3276 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3277 for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),
3278 et = E->capture_init_end(); it != et; ++it) {
3279 if (Expr *Init = *it) {
3280 CFGBlock *Tmp = Visit(Init);
3288 CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
3289 // Goto is a control-flow statement. Thus we stop processing the current
3290 // block and create a new one.
3292 Block = createBlock(false);
3293 Block->setTerminator(G);
3295 // If we already know the mapping to the label block add the successor now.
3296 LabelMapTy::iterator I = LabelMap.find(G->getLabel());
3298 if (I == LabelMap.end())
3299 // We will need to backpatch this block later.
3300 BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
3302 JumpTarget JT = I->second;
3303 addAutomaticObjHandling(ScopePos, JT.scopePosition, G);
3304 addSuccessor(Block, JT.block);
3310 CFGBlock *CFGBuilder::VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc) {
3311 // Goto is a control-flow statement. Thus we stop processing the current
3312 // block and create a new one.
3314 if (!G->isAsmGoto())
3315 return VisitStmt(G, asc);
3322 Block = createBlock();
3323 Block->setTerminator(G);
3324 // We will backpatch this block later for all the labels.
3325 BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
3326 // Save "Succ" in BackpatchBlocks. In the backpatch processing, "Succ" is
3327 // used to avoid adding "Succ" again.
3328 BackpatchBlocks.push_back(JumpSource(Succ, ScopePos));
3332 CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
3333 CFGBlock *LoopSuccessor = nullptr;
3335 // Save local scope position because in case of condition variable ScopePos
3336 // won't be restored when traversing AST.
3337 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3339 // Create local scope for init statement and possible condition variable.
3340 // Add destructor for init statement and condition variable.
3341 // Store scope position for continue statement.
3342 if (Stmt *Init = F->getInit())
3343 addLocalScopeForStmt(Init);
3344 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3346 if (VarDecl *VD = F->getConditionVariable())
3347 addLocalScopeForVarDecl(VD);
3348 LocalScope::const_iterator ContinueScopePos = ScopePos;
3350 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F);
3354 // "for" is a control-flow statement. Thus we stop processing the current
3359 LoopSuccessor = Block;
3361 LoopSuccessor = Succ;
3363 // Save the current value for the break targets.
3364 // All breaks should go to the code following the loop.
3365 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
3366 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3368 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3370 // Now create the loop body.
3372 assert(F->getBody());
3374 // Save the current values for Block, Succ, continue and break targets.
3375 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3376 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
3378 // Create an empty block to represent the transition block for looping back
3379 // to the head of the loop. If we have increment code, it will
3380 // go in this block as well.
3381 Block = Succ = TransitionBlock = createBlock(false);
3382 TransitionBlock->setLoopTarget(F);
3384 if (Stmt *I = F->getInc()) {
3385 // Generate increment code in its own basic block. This is the target of
3386 // continue statements.
3390 // Finish up the increment (or empty) block if it hasn't been already.
3392 assert(Block == Succ);
3398 // The starting block for the loop increment is the block that should
3399 // represent the 'loop target' for looping back to the start of the loop.
3400 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
3401 ContinueJumpTarget.block->setLoopTarget(F);
3403 // Loop body should end with destructor of Condition variable (if any).
3404 addAutomaticObjHandling(ScopePos, LoopBeginScopePos, F);
3406 // If body is not a compound statement create implicit scope
3407 // and add destructors.
3408 if (!isa<CompoundStmt>(F->getBody()))
3409 addLocalScopeAndDtors(F->getBody());
3411 // Now populate the body block, and in the process create new blocks as we
3412 // walk the body of the loop.
3413 BodyBlock = addStmt(F->getBody());
3416 // In the case of "for (...;...;...);" we can have a null BodyBlock.
3417 // Use the continue jump target as the proxy for the body.
3418 BodyBlock = ContinueJumpTarget.block;
3424 // Because of short-circuit evaluation, the condition of the loop can span
3425 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3426 // evaluate the condition.
3427 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3430 Expr *C = F->getCond();
3431 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3433 // Specially handle logical operators, which have a slightly
3434 // more optimal CFG representation.
3435 if (BinaryOperator *Cond =
3436 dyn_cast_or_null<BinaryOperator>(C ? C->IgnoreParens() : nullptr))
3437 if (Cond->isLogicalOp()) {
3438 std::tie(EntryConditionBlock, ExitConditionBlock) =
3439 VisitLogicalOperator(Cond, F, BodyBlock, LoopSuccessor);
3443 // The default case when not handling logical operators.
3444 EntryConditionBlock = ExitConditionBlock = createBlock(false);
3445 ExitConditionBlock->setTerminator(F);
3447 // See if this is a known constant.
3448 TryResult KnownVal(true);
3451 // Now add the actual condition to the condition block.
3452 // Because the condition itself may contain control-flow, new blocks may
3453 // be created. Thus we update "Succ" after adding the condition.
3454 Block = ExitConditionBlock;
3455 EntryConditionBlock = addStmt(C);
3457 // If this block contains a condition variable, add both the condition
3458 // variable and initializer to the CFG.
3459 if (VarDecl *VD = F->getConditionVariable()) {
3460 if (Expr *Init = VD->getInit()) {
3462 const DeclStmt *DS = F->getConditionVariableDeclStmt();
3463 assert(DS->isSingleDecl());
3464 findConstructionContexts(
3465 ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),
3467 appendStmt(Block, DS);
3468 EntryConditionBlock = addStmt(Init);
3469 assert(Block == EntryConditionBlock);
3470 maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);
3474 if (Block && badCFG)
3477 KnownVal = tryEvaluateBool(C);
3480 // Add the loop body entry as a successor to the condition.
3481 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);
3482 // Link up the condition block with the code that follows the loop. (the
3484 addSuccessor(ExitConditionBlock,
3485 KnownVal.isTrue() ? nullptr : LoopSuccessor);
3488 // Link up the loop-back block to the entry condition block.
3489 addSuccessor(TransitionBlock, EntryConditionBlock);
3491 // The condition block is the implicit successor for any code above the loop.
3492 Succ = EntryConditionBlock;
3494 // If the loop contains initialization, create a new block for those
3495 // statements. This block can also contain statements that precede the loop.
3496 if (Stmt *I = F->getInit()) {
3497 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3498 ScopePos = LoopBeginScopePos;
3499 Block = createBlock();
3503 // There is no loop initialization. We are thus basically a while loop.
3504 // NULL out Block to force lazy block construction.
3506 Succ = EntryConditionBlock;
3507 return EntryConditionBlock;
3511 CFGBuilder::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
3512 AddStmtChoice asc) {
3513 findConstructionContexts(
3514 ConstructionContextLayer::create(cfg->getBumpVectorContext(), MTE),
3517 return VisitStmt(MTE, asc);
3520 CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
3521 if (asc.alwaysAdd(*this, M)) {
3523 appendStmt(Block, M);
3525 return Visit(M->getBase());
3528 CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
3529 // Objective-C fast enumeration 'for' statements:
3530 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
3532 // for ( Type newVariable in collection_expression ) { statements }
3537 // 1. collection_expression
3538 // T. jump to loop_entry
3540 // 1. side-effects of element expression
3541 // 1. ObjCForCollectionStmt [performs binding to newVariable]
3542 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
3545 // T. jump to loop_entry
3551 // Type existingItem;
3552 // for ( existingItem in expression ) { statements }
3556 // the same with newVariable replaced with existingItem; the binding works
3557 // the same except that for one ObjCForCollectionStmt::getElement() returns
3558 // a DeclStmt and the other returns a DeclRefExpr.
3560 CFGBlock *LoopSuccessor = nullptr;
3565 LoopSuccessor = Block;
3568 LoopSuccessor = Succ;
3570 // Build the condition blocks.
3571 CFGBlock *ExitConditionBlock = createBlock(false);
3573 // Set the terminator for the "exit" condition block.
3574 ExitConditionBlock->setTerminator(S);
3576 // The last statement in the block should be the ObjCForCollectionStmt, which
3577 // performs the actual binding to 'element' and determines if there are any
3578 // more items in the collection.
3579 appendStmt(ExitConditionBlock, S);
3580 Block = ExitConditionBlock;
3582 // Walk the 'element' expression to see if there are any side-effects. We
3583 // generate new blocks as necessary. We DON'T add the statement by default to
3584 // the CFG unless it contains control-flow.
3585 CFGBlock *EntryConditionBlock = Visit(S->getElement(),
3586 AddStmtChoice::NotAlwaysAdd);
3593 // The condition block is the implicit successor for the loop body as well as
3594 // any code above the loop.
3595 Succ = EntryConditionBlock;
3597 // Now create the true branch.
3599 // Save the current values for Succ, continue and break targets.
3600 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3601 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3602 save_break(BreakJumpTarget);
3604 // Add an intermediate block between the BodyBlock and the
3605 // EntryConditionBlock to represent the "loop back" transition, for looping
3606 // back to the head of the loop.
3607 CFGBlock *LoopBackBlock = nullptr;
3608 Succ = LoopBackBlock = createBlock();
3609 LoopBackBlock->setLoopTarget(S);
3611 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3612 ContinueJumpTarget = JumpTarget(Succ, ScopePos);
3614 CFGBlock *BodyBlock = addStmt(S->getBody());
3617 BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;"
3623 // This new body block is a successor to our "exit" condition block.
3624 addSuccessor(ExitConditionBlock, BodyBlock);
3627 // Link up the condition block with the code that follows the loop.
3628 // (the false branch).
3629 addSuccessor(ExitConditionBlock, LoopSuccessor);
3631 // Now create a prologue block to contain the collection expression.
3632 Block = createBlock();
3633 return addStmt(S->getCollection());
3636 CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) {
3638 return addStmt(S->getSubStmt());
3639 // TODO: consider adding cleanups for the end of @autoreleasepool scope.
3642 CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
3643 // FIXME: Add locking 'primitives' to CFG for @synchronized.
3646 CFGBlock *SyncBlock = addStmt(S->getSynchBody());
3648 // The sync body starts its own basic block. This makes it a little easier
3649 // for diagnostic clients.
3658 // Add the @synchronized to the CFG.
3660 appendStmt(Block, S);
3662 // Inline the sync expression.
3663 return addStmt(S->getSynchExpr());
3666 CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) {
3671 CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {
3674 // Add the PseudoObject as the last thing.
3675 appendStmt(Block, E);
3677 CFGBlock *lastBlock = Block;
3679 // Before that, evaluate all of the semantics in order. In
3680 // CFG-land, that means appending them in reverse order.
3681 for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {
3682 Expr *Semantic = E->getSemanticExpr(--i);
3684 // If the semantic is an opaque value, we're being asked to bind
3685 // it to its source expression.
3686 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
3687 Semantic = OVE->getSourceExpr();
3689 if (CFGBlock *B = Visit(Semantic))
3696 CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
3697 CFGBlock *LoopSuccessor = nullptr;
3699 // Save local scope position because in case of condition variable ScopePos
3700 // won't be restored when traversing AST.
3701 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3703 // Create local scope for possible condition variable.
3704 // Store scope position for continue statement.
3705 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3706 if (VarDecl *VD = W->getConditionVariable()) {
3707 addLocalScopeForVarDecl(VD);
3708 addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
3712 // "while" is a control-flow statement. Thus we stop processing the current
3717 LoopSuccessor = Block;
3720 LoopSuccessor = Succ;
3723 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3725 // Process the loop body.
3727 assert(W->getBody());
3729 // Save the current values for Block, Succ, continue and break targets.
3730 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3731 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3732 save_break(BreakJumpTarget);
3734 // Create an empty block to represent the transition block for looping back
3735 // to the head of the loop.
3736 Succ = TransitionBlock = createBlock(false);
3737 TransitionBlock->setLoopTarget(W);
3738 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
3740 // All breaks should go to the code following the loop.
3741 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3743 // Loop body should end with destructor of Condition variable (if any).
3744 addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
3746 // If body is not a compound statement create implicit scope
3747 // and add destructors.
3748 if (!isa<CompoundStmt>(W->getBody()))
3749 addLocalScopeAndDtors(W->getBody());
3751 // Create the body. The returned block is the entry to the loop body.
3752 BodyBlock = addStmt(W->getBody());
3755 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
3756 else if (Block && badCFG)
3760 // Because of short-circuit evaluation, the condition of the loop can span
3761 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3762 // evaluate the condition.
3763 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3766 Expr *C = W->getCond();
3768 // Specially handle logical operators, which have a slightly
3769 // more optimal CFG representation.
3770 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(C->IgnoreParens()))
3771 if (Cond->isLogicalOp()) {
3772 std::tie(EntryConditionBlock, ExitConditionBlock) =
3773 VisitLogicalOperator(Cond, W, BodyBlock, LoopSuccessor);
3777 // The default case when not handling logical operators.
3778 ExitConditionBlock = createBlock(false);
3779 ExitConditionBlock->setTerminator(W);
3781 // Now add the actual condition to the condition block.
3782 // Because the condition itself may contain control-flow, new blocks may
3783 // be created. Thus we update "Succ" after adding the condition.
3784 Block = ExitConditionBlock;
3785 Block = EntryConditionBlock = addStmt(C);
3787 // If this block contains a condition variable, add both the condition
3788 // variable and initializer to the CFG.
3789 if (VarDecl *VD = W->getConditionVariable()) {
3790 if (Expr *Init = VD->getInit()) {
3792 const DeclStmt *DS = W->getConditionVariableDeclStmt();
3793 assert(DS->isSingleDecl());
3794 findConstructionContexts(
3795 ConstructionContextLayer::create(cfg->getBumpVectorContext(),
3796 const_cast<DeclStmt *>(DS)),
3798 appendStmt(Block, DS);
3799 EntryConditionBlock = addStmt(Init);
3800 assert(Block == EntryConditionBlock);
3801 maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);
3805 if (Block && badCFG)
3808 // See if this is a known constant.
3809 const TryResult& KnownVal = tryEvaluateBool(C);
3811 // Add the loop body entry as a successor to the condition.
3812 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);
3813 // Link up the condition block with the code that follows the loop. (the
3815 addSuccessor(ExitConditionBlock,
3816 KnownVal.isTrue() ? nullptr : LoopSuccessor);
3819 // Link up the loop-back block to the entry condition block.
3820 addSuccessor(TransitionBlock, EntryConditionBlock);
3822 // There can be no more statements in the condition block since we loop back
3823 // to this block. NULL out Block to force lazy creation of another block.
3826 // Return the condition block, which is the dominating block for the loop.
3827 Succ = EntryConditionBlock;
3828 return EntryConditionBlock;
3831 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) {
3832 // FIXME: For now we pretend that @catch and the code it contains does not
3837 CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
3838 // FIXME: This isn't complete. We basically treat @throw like a return
3841 // If we were in the middle of a block we stop processing that block.
3845 // Create the new block.
3846 Block = createBlock(false);
3848 // The Exit block is the only successor.
3849 addSuccessor(Block, &cfg->getExit());
3851 // Add the statement to the block. This may create new blocks if S contains
3852 // control-flow (short-circuit operations).
3853 return VisitStmt(S, AddStmtChoice::AlwaysAdd);
3856 CFGBlock *CFGBuilder::VisitObjCMessageExpr(ObjCMessageExpr *ME,
3857 AddStmtChoice asc) {
3858 findConstructionContextsForArguments(ME);
3861 appendObjCMessage(Block, ME);
3863 return VisitChildren(ME);
3866 CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
3867 // If we were in the middle of a block we stop processing that block.
3871 // Create the new block.
3872 Block = createBlock(false);
3874 if (TryTerminatedBlock)
3875 // The current try statement is the only successor.
3876 addSuccessor(Block, TryTerminatedBlock);
3878 // otherwise the Exit block is the only successor.
3879 addSuccessor(Block, &cfg->getExit());
3881 // Add the statement to the block. This may create new blocks if S contains
3882 // control-flow (short-circuit operations).
3883 return VisitStmt(T, AddStmtChoice::AlwaysAdd);
3886 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
3887 CFGBlock *LoopSuccessor = nullptr;
3891 // "do...while" is a control-flow statement. Thus we stop processing the
3896 LoopSuccessor = Block;
3898 LoopSuccessor = Succ;
3900 // Because of short-circuit evaluation, the condition of the loop can span
3901 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3902 // evaluate the condition.
3903 CFGBlock *ExitConditionBlock = createBlock(false);
3904 CFGBlock *EntryConditionBlock = ExitConditionBlock;
3906 // Set the terminator for the "exit" condition block.
3907 ExitConditionBlock->setTerminator(D);
3909 // Now add the actual condition to the condition block. Because the condition
3910 // itself may contain control-flow, new blocks may be created.
3911 if (Stmt *C = D->getCond()) {
3912 Block = ExitConditionBlock;
3913 EntryConditionBlock = addStmt(C);
3920 // The condition block is the implicit successor for the loop body.
3921 Succ = EntryConditionBlock;
3923 // See if this is a known constant.
3924 const TryResult &KnownVal = tryEvaluateBool(D->getCond());
3926 // Process the loop body.
3927 CFGBlock *BodyBlock = nullptr;
3929 assert(D->getBody());
3931 // Save the current values for Block, Succ, and continue and break targets
3932 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3933 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3934 save_break(BreakJumpTarget);
3936 // All continues within this loop should go to the condition block
3937 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
3939 // All breaks should go to the code following the loop.
3940 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3942 // NULL out Block to force lazy instantiation of blocks for the body.
3945 // If body is not a compound statement create implicit scope
3946 // and add destructors.
3947 if (!isa<CompoundStmt>(D->getBody()))
3948 addLocalScopeAndDtors(D->getBody());
3950 // Create the body. The returned block is the entry to the loop body.
3951 BodyBlock = addStmt(D->getBody());
3954 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
3960 // Add an intermediate block between the BodyBlock and the
3961 // ExitConditionBlock to represent the "loop back" transition. Create an
3962 // empty block to represent the transition block for looping back to the
3963 // head of the loop.
3964 // FIXME: Can we do this more efficiently without adding another block?
3967 CFGBlock *LoopBackBlock = createBlock();
3968 LoopBackBlock->setLoopTarget(D);
3970 if (!KnownVal.isFalse())
3971 // Add the loop body entry as a successor to the condition.
3972 addSuccessor(ExitConditionBlock, LoopBackBlock);
3974 addSuccessor(ExitConditionBlock, nullptr);
3977 // Link up the condition block with the code that follows the loop.
3978 // (the false branch).
3979 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);
3981 // There can be no more statements in the body block(s) since we loop back to
3982 // the body. NULL out Block to force lazy creation of another block.
3985 // Return the loop body, which is the dominating block for the loop.
3990 CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
3991 // "continue" is a control-flow statement. Thus we stop processing the
3996 // Now create a new block that ends with the continue statement.
3997 Block = createBlock(false);
3998 Block->setTerminator(C);
4000 // If there is no target for the continue, then we are looking at an
4001 // incomplete AST. This means the CFG cannot be constructed.
4002 if (ContinueJumpTarget.block) {
4003 addAutomaticObjHandling(ScopePos, ContinueJumpTarget.scopePosition, C);
4004 addSuccessor(Block, ContinueJumpTarget.block);
4011 CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
4012 AddStmtChoice asc) {
4013 if (asc.alwaysAdd(*this, E)) {
4015 appendStmt(Block, E);
4018 // VLA types have expressions that must be evaluated.
4019 // Evaluation is done only for `sizeof`.
4021 if (E->getKind() != UETT_SizeOf)
4024 CFGBlock *lastBlock = Block;
4026 if (E->isArgumentType()) {
4027 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());
4028 VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr()))
4029 lastBlock = addStmt(VA->getSizeExpr());
4034 /// VisitStmtExpr - Utility method to handle (nested) statement
4035 /// expressions (a GCC extension).
4036 CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
4037 if (asc.alwaysAdd(*this, SE)) {
4039 appendStmt(Block, SE);
4041 return VisitCompoundStmt(SE->getSubStmt(), /*ExternallyDestructed=*/true);
4044 CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
4045 // "switch" is a control-flow statement. Thus we stop processing the current
4047 CFGBlock *SwitchSuccessor = nullptr;
4049 // Save local scope position because in case of condition variable ScopePos
4050 // won't be restored when traversing AST.
4051 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4053 // Create local scope for C++17 switch init-stmt if one exists.
4054 if (Stmt *Init = Terminator->getInit())
4055 addLocalScopeForStmt(Init);
4057 // Create local scope for possible condition variable.
4058 // Store scope position. Add implicit destructor.
4059 if (VarDecl *VD = Terminator->getConditionVariable())
4060 addLocalScopeForVarDecl(VD);
4062 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), Terminator);
4067 SwitchSuccessor = Block;
4068 } else SwitchSuccessor = Succ;
4070 // Save the current "switch" context.
4071 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
4072 save_default(DefaultCaseBlock);
4073 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
4075 // Set the "default" case to be the block after the switch statement. If the
4076 // switch statement contains a "default:", this value will be overwritten with
4077 // the block for that code.
4078 DefaultCaseBlock = SwitchSuccessor;
4080 // Create a new block that will contain the switch statement.
4081 SwitchTerminatedBlock = createBlock(false);
4083 // Now process the switch body. The code after the switch is the implicit
4085 Succ = SwitchSuccessor;
4086 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
4088 // When visiting the body, the case statements should automatically get linked
4089 // up to the switch. We also don't keep a pointer to the body, since all
4090 // control-flow from the switch goes to case/default statements.
4091 assert(Terminator->getBody() && "switch must contain a non-NULL body");
4094 // For pruning unreachable case statements, save the current state
4095 // for tracking the condition value.
4096 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered,
4099 // Determine if the switch condition can be explicitly evaluated.
4100 assert(Terminator->getCond() && "switch condition must be non-NULL");
4101 Expr::EvalResult result;
4102 bool b = tryEvaluate(Terminator->getCond(), result);
4103 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond,
4104 b ? &result : nullptr);
4106 // If body is not a compound statement create implicit scope
4107 // and add destructors.
4108 if (!isa<CompoundStmt>(Terminator->getBody()))
4109 addLocalScopeAndDtors(Terminator->getBody());
4111 addStmt(Terminator->getBody());
4117 // If we have no "default:" case, the default transition is to the code
4118 // following the switch body. Moreover, take into account if all the
4119 // cases of a switch are covered (e.g., switching on an enum value).
4121 // Note: We add a successor to a switch that is considered covered yet has no
4122 // case statements if the enumeration has no enumerators.
4123 bool SwitchAlwaysHasSuccessor = false;
4124 SwitchAlwaysHasSuccessor |= switchExclusivelyCovered;
4125 SwitchAlwaysHasSuccessor |= Terminator->isAllEnumCasesCovered() &&
4126 Terminator->getSwitchCaseList();
4127 addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock,
4128 !SwitchAlwaysHasSuccessor);
4130 // Add the terminator and condition in the switch block.
4131 SwitchTerminatedBlock->setTerminator(Terminator);
4132 Block = SwitchTerminatedBlock;
4133 CFGBlock *LastBlock = addStmt(Terminator->getCond());
4135 // If the SwitchStmt contains a condition variable, add both the
4136 // SwitchStmt and the condition variable initialization to the CFG.
4137 if (VarDecl *VD = Terminator->getConditionVariable()) {
4138 if (Expr *Init = VD->getInit()) {
4140 appendStmt(Block, Terminator->getConditionVariableDeclStmt());
4141 LastBlock = addStmt(Init);
4142 maybeAddScopeBeginForVarDecl(LastBlock, VD, Init);
4146 // Finally, if the SwitchStmt contains a C++17 init-stmt, add it to the CFG.
4147 if (Stmt *Init = Terminator->getInit()) {
4149 LastBlock = addStmt(Init);
4155 static bool shouldAddCase(bool &switchExclusivelyCovered,
4156 const Expr::EvalResult *switchCond,
4162 bool addCase = false;
4164 if (!switchExclusivelyCovered) {
4165 if (switchCond->Val.isInt()) {
4166 // Evaluate the LHS of the case value.
4167 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
4168 const llvm::APSInt &condInt = switchCond->Val.getInt();
4170 if (condInt == lhsInt) {
4172 switchExclusivelyCovered = true;
4174 else if (condInt > lhsInt) {
4175 if (const Expr *RHS = CS->getRHS()) {
4176 // Evaluate the RHS of the case value.
4177 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
4178 if (V2 >= condInt) {
4180 switchExclusivelyCovered = true;
4191 CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
4192 // CaseStmts are essentially labels, so they are the first statement in a
4194 CFGBlock *TopBlock = nullptr, *LastBlock = nullptr;
4196 if (Stmt *Sub = CS->getSubStmt()) {
4197 // For deeply nested chains of CaseStmts, instead of doing a recursion
4198 // (which can blow out the stack), manually unroll and create blocks
4200 while (isa<CaseStmt>(Sub)) {
4201 CFGBlock *currentBlock = createBlock(false);
4202 currentBlock->setLabel(CS);
4205 addSuccessor(LastBlock, currentBlock);
4207 TopBlock = currentBlock;
4209 addSuccessor(SwitchTerminatedBlock,
4210 shouldAddCase(switchExclusivelyCovered, switchCond,
4212 ? currentBlock : nullptr);
4214 LastBlock = currentBlock;
4215 CS = cast<CaseStmt>(Sub);
4216 Sub = CS->getSubStmt();
4222 CFGBlock *CaseBlock = Block;
4224 CaseBlock = createBlock();
4226 // Cases statements partition blocks, so this is the top of the basic block we
4227 // were processing (the "case XXX:" is the label).
4228 CaseBlock->setLabel(CS);
4233 // Add this block to the list of successors for the block with the switch
4235 assert(SwitchTerminatedBlock);
4236 addSuccessor(SwitchTerminatedBlock, CaseBlock,
4237 shouldAddCase(switchExclusivelyCovered, switchCond,
4240 // We set Block to NULL to allow lazy creation of a new block (if necessary)
4244 addSuccessor(LastBlock, CaseBlock);
4247 // This block is now the implicit successor of other blocks.
4254 CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
4255 if (Terminator->getSubStmt())
4256 addStmt(Terminator->getSubStmt());
4258 DefaultCaseBlock = Block;
4260 if (!DefaultCaseBlock)
4261 DefaultCaseBlock = createBlock();
4263 // Default statements partition blocks, so this is the top of the basic block
4264 // we were processing (the "default:" is the label).
4265 DefaultCaseBlock->setLabel(Terminator);
4270 // Unlike case statements, we don't add the default block to the successors
4271 // for the switch statement immediately. This is done when we finish
4272 // processing the switch statement. This allows for the default case
4273 // (including a fall-through to the code after the switch statement) to always
4274 // be the last successor of a switch-terminated block.
4276 // We set Block to NULL to allow lazy creation of a new block (if necessary)
4279 // This block is now the implicit successor of other blocks.
4280 Succ = DefaultCaseBlock;
4282 return DefaultCaseBlock;
4285 CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
4286 // "try"/"catch" is a control-flow statement. Thus we stop processing the
4288 CFGBlock *TrySuccessor = nullptr;
4293 TrySuccessor = Block;
4294 } else TrySuccessor = Succ;
4296 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
4298 // Create a new block that will contain the try statement.
4299 CFGBlock *NewTryTerminatedBlock = createBlock(false);
4300 // Add the terminator in the try block.
4301 NewTryTerminatedBlock->setTerminator(Terminator);
4303 bool HasCatchAll = false;
4304 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) {
4305 // The code after the try is the implicit successor.
4306 Succ = TrySuccessor;
4307 CXXCatchStmt *CS = Terminator->getHandler(h);
4308 if (CS->getExceptionDecl() == nullptr) {
4312 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);
4315 // Add this block to the list of successors for the block with the try
4317 addSuccessor(NewTryTerminatedBlock, CatchBlock);
4320 if (PrevTryTerminatedBlock)
4321 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);
4323 addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
4326 // The code after the try is the implicit successor.
4327 Succ = TrySuccessor;
4329 // Save the current "try" context.
4330 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock);
4331 cfg->addTryDispatchBlock(TryTerminatedBlock);
4333 assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
4335 return addStmt(Terminator->getTryBlock());
4338 CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
4339 // CXXCatchStmt are treated like labels, so they are the first statement in a
4342 // Save local scope position because in case of exception variable ScopePos
4343 // won't be restored when traversing AST.
4344 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4346 // Create local scope for possible exception variable.
4347 // Store scope position. Add implicit destructor.
4348 if (VarDecl *VD = CS->getExceptionDecl()) {
4349 LocalScope::const_iterator BeginScopePos = ScopePos;
4350 addLocalScopeForVarDecl(VD);
4351 addAutomaticObjHandling(ScopePos, BeginScopePos, CS);
4354 if (CS->getHandlerBlock())
4355 addStmt(CS->getHandlerBlock());
4357 CFGBlock *CatchBlock = Block;
4359 CatchBlock = createBlock();
4361 // CXXCatchStmt is more than just a label. They have semantic meaning
4362 // as well, as they implicitly "initialize" the catch variable. Add
4363 // it to the CFG as a CFGElement so that the control-flow of these
4364 // semantics gets captured.
4365 appendStmt(CatchBlock, CS);
4367 // Also add the CXXCatchStmt as a label, to mirror handling of regular
4369 CatchBlock->setLabel(CS);
4371 // Bail out if the CFG is bad.
4375 // We set Block to NULL to allow lazy creation of a new block (if necessary)
4381 CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
4382 // C++0x for-range statements are specified as [stmt.ranged]:
4385 // auto && __range = range-init;
4386 // for ( auto __begin = begin-expr,
4387 // __end = end-expr;
4388 // __begin != __end;
4390 // for-range-declaration = *__begin;
4395 // Save local scope position before the addition of the implicit variables.
4396 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4398 // Create local scopes and destructors for range, begin and end variables.
4399 if (Stmt *Range = S->getRangeStmt())
4400 addLocalScopeForStmt(Range);
4401 if (Stmt *Begin = S->getBeginStmt())
4402 addLocalScopeForStmt(Begin);
4403 if (Stmt *End = S->getEndStmt())
4404 addLocalScopeForStmt(End);
4405 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), S);
4407 LocalScope::const_iterator ContinueScopePos = ScopePos;
4409 // "for" is a control-flow statement. Thus we stop processing the current
4411 CFGBlock *LoopSuccessor = nullptr;
4415 LoopSuccessor = Block;
4417 LoopSuccessor = Succ;
4419 // Save the current value for the break targets.
4420 // All breaks should go to the code following the loop.
4421 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
4422 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4424 // The block for the __begin != __end expression.
4425 CFGBlock *ConditionBlock = createBlock(false);
4426 ConditionBlock->setTerminator(S);
4428 // Now add the actual condition to the condition block.
4429 if (Expr *C = S->getCond()) {
4430 Block = ConditionBlock;
4431 CFGBlock *BeginConditionBlock = addStmt(C);
4434 assert(BeginConditionBlock == ConditionBlock &&
4435 "condition block in for-range was unexpectedly complex");
4436 (void)BeginConditionBlock;
4439 // The condition block is the implicit successor for the loop body as well as
4440 // any code above the loop.
4441 Succ = ConditionBlock;
4443 // See if this is a known constant.
4444 TryResult KnownVal(true);
4447 KnownVal = tryEvaluateBool(S->getCond());
4449 // Now create the loop body.
4451 assert(S->getBody());
4453 // Save the current values for Block, Succ, and continue targets.
4454 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
4455 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
4457 // Generate increment code in its own basic block. This is the target of
4458 // continue statements.
4460 Succ = addStmt(S->getInc());
4463 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
4465 // The starting block for the loop increment is the block that should
4466 // represent the 'loop target' for looping back to the start of the loop.
4467 ContinueJumpTarget.block->setLoopTarget(S);
4469 // Finish up the increment block and prepare to start the loop body.
4475 // Add implicit scope and dtors for loop variable.
4476 addLocalScopeAndDtors(S->getLoopVarStmt());
4478 // Populate a new block to contain the loop body and loop variable.
4479 addStmt(S->getBody());
4482 CFGBlock *LoopVarStmtBlock = addStmt(S->getLoopVarStmt());
4486 // This new body block is a successor to our condition block.
4487 addSuccessor(ConditionBlock,
4488 KnownVal.isFalse() ? nullptr : LoopVarStmtBlock);
4491 // Link up the condition block with the code that follows the loop (the
4493 addSuccessor(ConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);
4495 // Add the initialization statements.
4496 Block = createBlock();
4497 addStmt(S->getBeginStmt());
4498 addStmt(S->getEndStmt());
4499 CFGBlock *Head = addStmt(S->getRangeStmt());
4501 Head = addStmt(S->getInit());
4505 CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
4506 AddStmtChoice asc, bool ExternallyDestructed) {
4507 if (BuildOpts.AddTemporaryDtors) {
4508 // If adding implicit destructors visit the full expression for adding
4509 // destructors of temporaries.
4510 TempDtorContext Context;
4511 VisitForTemporaryDtors(E->getSubExpr(), ExternallyDestructed, Context);
4513 // Full expression has to be added as CFGStmt so it will be sequenced
4514 // before destructors of it's temporaries.
4515 asc = asc.withAlwaysAdd(true);
4517 return Visit(E->getSubExpr(), asc);
4520 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
4521 AddStmtChoice asc) {
4522 if (asc.alwaysAdd(*this, E)) {
4524 appendStmt(Block, E);
4526 findConstructionContexts(
4527 ConstructionContextLayer::create(cfg->getBumpVectorContext(), E),
4530 // We do not want to propagate the AlwaysAdd property.
4531 asc = asc.withAlwaysAdd(false);
4533 return Visit(E->getSubExpr(), asc);
4536 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
4537 AddStmtChoice asc) {
4538 // If the constructor takes objects as arguments by value, we need to properly
4539 // construct these objects. Construction contexts we find here aren't for the
4540 // constructor C, they're for its arguments only.
4541 findConstructionContextsForArguments(C);
4544 appendConstructor(Block, C);
4546 return VisitChildren(C);
4549 CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
4550 AddStmtChoice asc) {
4552 appendStmt(Block, NE);
4554 findConstructionContexts(
4555 ConstructionContextLayer::create(cfg->getBumpVectorContext(), NE),
4556 const_cast<CXXConstructExpr *>(NE->getConstructExpr()));
4558 if (NE->getInitializer())
4559 Block = Visit(NE->getInitializer());
4561 if (BuildOpts.AddCXXNewAllocator)
4562 appendNewAllocator(Block, NE);
4564 if (NE->isArray() && *NE->getArraySize())
4565 Block = Visit(*NE->getArraySize());
4567 for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),
4568 E = NE->placement_arg_end(); I != E; ++I)
4574 CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
4575 AddStmtChoice asc) {
4577 appendStmt(Block, DE);
4578 QualType DTy = DE->getDestroyedType();
4579 if (!DTy.isNull()) {
4580 DTy = DTy.getNonReferenceType();
4581 CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl();
4583 if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())
4584 appendDeleteDtor(Block, RD, DE);
4588 return VisitChildren(DE);
4591 CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
4592 AddStmtChoice asc) {
4593 if (asc.alwaysAdd(*this, E)) {
4595 appendStmt(Block, E);
4596 // We do not want to propagate the AlwaysAdd property.
4597 asc = asc.withAlwaysAdd(false);
4599 return Visit(E->getSubExpr(), asc);
4602 CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
4603 AddStmtChoice asc) {
4604 // If the constructor takes objects as arguments by value, we need to properly
4605 // construct these objects. Construction contexts we find here aren't for the
4606 // constructor C, they're for its arguments only.
4607 findConstructionContextsForArguments(C);
4610 appendConstructor(Block, C);
4611 return VisitChildren(C);
4614 CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
4615 AddStmtChoice asc) {
4616 if (asc.alwaysAdd(*this, E)) {
4618 appendStmt(Block, E);
4621 if (E->getCastKind() == CK_IntegralToBoolean)
4622 tryEvaluateBool(E->getSubExpr()->IgnoreParens());
4624 return Visit(E->getSubExpr(), AddStmtChoice());
4627 CFGBlock *CFGBuilder::VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc) {
4628 return Visit(E->getSubExpr(), AddStmtChoice());
4631 CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
4632 // Lazily create the indirect-goto dispatch block if there isn't one already.
4633 CFGBlock *IBlock = cfg->getIndirectGotoBlock();
4636 IBlock = createBlock(false);
4637 cfg->setIndirectGotoBlock(IBlock);
4640 // IndirectGoto is a control-flow statement. Thus we stop processing the
4641 // current block and create a new one.
4645 Block = createBlock(false);
4646 Block->setTerminator(I);
4647 addSuccessor(Block, IBlock);
4648 return addStmt(I->getTarget());
4651 CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool ExternallyDestructed,
4652 TempDtorContext &Context) {
4653 assert(BuildOpts.AddImplicitDtors && BuildOpts.AddTemporaryDtors);
4660 switch (E->getStmtClass()) {
4662 return VisitChildrenForTemporaryDtors(E, false, Context);
4664 case Stmt::InitListExprClass:
4665 return VisitChildrenForTemporaryDtors(E, ExternallyDestructed, Context);
4667 case Stmt::BinaryOperatorClass:
4668 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E),
4669 ExternallyDestructed,
4672 case Stmt::CXXBindTemporaryExprClass:
4673 return VisitCXXBindTemporaryExprForTemporaryDtors(
4674 cast<CXXBindTemporaryExpr>(E), ExternallyDestructed, Context);
4676 case Stmt::BinaryConditionalOperatorClass:
4677 case Stmt::ConditionalOperatorClass:
4678 return VisitConditionalOperatorForTemporaryDtors(
4679 cast<AbstractConditionalOperator>(E), ExternallyDestructed, Context);
4681 case Stmt::ImplicitCastExprClass:
4682 // For implicit cast we want ExternallyDestructed to be passed further.
4683 E = cast<CastExpr>(E)->getSubExpr();
4686 case Stmt::CXXFunctionalCastExprClass:
4687 // For functional cast we want ExternallyDestructed to be passed further.
4688 E = cast<CXXFunctionalCastExpr>(E)->getSubExpr();
4691 case Stmt::ConstantExprClass:
4692 E = cast<ConstantExpr>(E)->getSubExpr();
4695 case Stmt::ParenExprClass:
4696 E = cast<ParenExpr>(E)->getSubExpr();
4699 case Stmt::MaterializeTemporaryExprClass: {
4700 const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(E);
4701 ExternallyDestructed = (MTE->getStorageDuration() != SD_FullExpression);
4702 SmallVector<const Expr *, 2> CommaLHSs;
4703 SmallVector<SubobjectAdjustment, 2> Adjustments;
4704 // Find the expression whose lifetime needs to be extended.
4705 E = const_cast<Expr *>(
4706 cast<MaterializeTemporaryExpr>(E)
4708 ->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments));
4709 // Visit the skipped comma operator left-hand sides for other temporaries.
4710 for (const Expr *CommaLHS : CommaLHSs) {
4711 VisitForTemporaryDtors(const_cast<Expr *>(CommaLHS),
4712 /*ExternallyDestructed=*/false, Context);
4717 case Stmt::BlockExprClass:
4718 // Don't recurse into blocks; their subexpressions don't get evaluated
4722 case Stmt::LambdaExprClass: {
4723 // For lambda expressions, only recurse into the capture initializers,
4724 // and not the body.
4725 auto *LE = cast<LambdaExpr>(E);
4726 CFGBlock *B = Block;
4727 for (Expr *Init : LE->capture_inits()) {
4729 if (CFGBlock *R = VisitForTemporaryDtors(
4730 Init, /*ExternallyDestructed=*/true, Context))
4737 case Stmt::StmtExprClass:
4738 // Don't recurse into statement expressions; any cleanups inside them
4739 // will be wrapped in their own ExprWithCleanups.
4742 case Stmt::CXXDefaultArgExprClass:
4743 E = cast<CXXDefaultArgExpr>(E)->getExpr();
4746 case Stmt::CXXDefaultInitExprClass:
4747 E = cast<CXXDefaultInitExpr>(E)->getExpr();
4752 CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E,
4753 bool ExternallyDestructed,
4754 TempDtorContext &Context) {
4755 if (isa<LambdaExpr>(E)) {
4756 // Do not visit the children of lambdas; they have their own CFGs.
4760 // When visiting children for destructors we want to visit them in reverse
4761 // order that they will appear in the CFG. Because the CFG is built
4762 // bottom-up, this means we visit them in their natural order, which
4763 // reverses them in the CFG.
4764 CFGBlock *B = Block;
4765 for (Stmt *Child : E->children())
4767 if (CFGBlock *R = VisitForTemporaryDtors(Child, ExternallyDestructed, Context))
4773 CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(
4774 BinaryOperator *E, bool ExternallyDestructed, TempDtorContext &Context) {
4775 if (E->isCommaOp()) {
4776 // For comma operator LHS expression is visited
4777 // before RHS expression. For destructors visit them in reverse order.
4778 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), ExternallyDestructed, Context);
4779 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
4780 return LHSBlock ? LHSBlock : RHSBlock;
4783 if (E->isLogicalOp()) {
4784 VisitForTemporaryDtors(E->getLHS(), false, Context);
4785 TryResult RHSExecuted = tryEvaluateBool(E->getLHS());
4786 if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr)
4787 RHSExecuted.negate();
4789 // We do not know at CFG-construction time whether the right-hand-side was
4790 // executed, thus we add a branch node that depends on the temporary
4791 // constructor call.
4792 TempDtorContext RHSContext(
4793 bothKnownTrue(Context.KnownExecuted, RHSExecuted));
4794 VisitForTemporaryDtors(E->getRHS(), false, RHSContext);
4795 InsertTempDtorDecisionBlock(RHSContext);
4800 if (E->isAssignmentOp()) {
4801 // For assignment operator (=) LHS expression is visited
4802 // before RHS expression. For destructors visit them in reverse order.
4803 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);
4804 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
4805 return LHSBlock ? LHSBlock : RHSBlock;
4808 // For any other binary operator RHS expression is visited before
4809 // LHS expression (order of children). For destructors visit them in reverse
4811 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
4812 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);
4813 return RHSBlock ? RHSBlock : LHSBlock;
4816 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
4817 CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context) {
4818 // First add destructors for temporaries in subexpression.
4819 // Because VisitCXXBindTemporaryExpr calls setDestructed:
4820 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr(), true, Context);
4821 if (!ExternallyDestructed) {
4822 // If lifetime of temporary is not prolonged (by assigning to constant
4823 // reference) add destructor for it.
4825 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
4827 if (Dtor->getParent()->isAnyDestructorNoReturn()) {
4828 // If the destructor is marked as a no-return destructor, we need to
4829 // create a new block for the destructor which does not have as a
4830 // successor anything built thus far. Control won't flow out of this
4833 Block = createNoReturnBlock();
4834 } else if (Context.needsTempDtorBranch()) {
4835 // If we need to introduce a branch, we add a new block that we will hook
4836 // up to a decision block later.
4838 Block = createBlock();
4842 if (Context.needsTempDtorBranch()) {
4843 Context.setDecisionPoint(Succ, E);
4845 appendTemporaryDtor(Block, E);
4852 void CFGBuilder::InsertTempDtorDecisionBlock(const TempDtorContext &Context,
4853 CFGBlock *FalseSucc) {
4854 if (!Context.TerminatorExpr) {
4855 // If no temporary was found, we do not need to insert a decision point.
4858 assert(Context.TerminatorExpr);
4859 CFGBlock *Decision = createBlock(false);
4860 Decision->setTerminator(CFGTerminator(Context.TerminatorExpr,
4861 CFGTerminator::TemporaryDtorsBranch));
4862 addSuccessor(Decision, Block, !Context.KnownExecuted.isFalse());
4863 addSuccessor(Decision, FalseSucc ? FalseSucc : Context.Succ,
4864 !Context.KnownExecuted.isTrue());
4868 CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
4869 AbstractConditionalOperator *E, bool ExternallyDestructed,
4870 TempDtorContext &Context) {
4871 VisitForTemporaryDtors(E->getCond(), false, Context);
4872 CFGBlock *ConditionBlock = Block;
4873 CFGBlock *ConditionSucc = Succ;
4874 TryResult ConditionVal = tryEvaluateBool(E->getCond());
4875 TryResult NegatedVal = ConditionVal;
4876 if (NegatedVal.isKnown()) NegatedVal.negate();
4878 TempDtorContext TrueContext(
4879 bothKnownTrue(Context.KnownExecuted, ConditionVal));
4880 VisitForTemporaryDtors(E->getTrueExpr(), ExternallyDestructed, TrueContext);
4881 CFGBlock *TrueBlock = Block;
4883 Block = ConditionBlock;
4884 Succ = ConditionSucc;
4885 TempDtorContext FalseContext(
4886 bothKnownTrue(Context.KnownExecuted, NegatedVal));
4887 VisitForTemporaryDtors(E->getFalseExpr(), ExternallyDestructed, FalseContext);
4889 if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) {
4890 InsertTempDtorDecisionBlock(FalseContext, TrueBlock);
4891 } else if (TrueContext.TerminatorExpr) {
4893 InsertTempDtorDecisionBlock(TrueContext);
4895 InsertTempDtorDecisionBlock(FalseContext);
4900 CFGBlock *CFGBuilder::VisitOMPExecutableDirective(OMPExecutableDirective *D,
4901 AddStmtChoice asc) {
4902 if (asc.alwaysAdd(*this, D)) {
4904 appendStmt(Block, D);
4907 // Iterate over all used expression in clauses.
4908 CFGBlock *B = Block;
4910 // Reverse the elements to process them in natural order. Iterators are not
4911 // bidirectional, so we need to create temp vector.
4912 SmallVector<Stmt *, 8> Used(
4913 OMPExecutableDirective::used_clauses_children(D->clauses()));
4914 for (Stmt *S : llvm::reverse(Used)) {
4915 assert(S && "Expected non-null used-in-clause child.");
4916 if (CFGBlock *R = Visit(S))
4919 // Visit associated structured block if any.
4920 if (!D->isStandaloneDirective())
4921 if (CapturedStmt *CS = D->getInnermostCapturedStmt()) {
4922 Stmt *S = CS->getCapturedStmt();
4923 if (!isa<CompoundStmt>(S))
4924 addLocalScopeAndDtors(S);
4925 if (CFGBlock *R = addStmt(S))
4932 /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
4933 /// no successors or predecessors. If this is the first block created in the
4934 /// CFG, it is automatically set to be the Entry and Exit of the CFG.
4935 CFGBlock *CFG::createBlock() {
4936 bool first_block = begin() == end();
4938 // Create the block.
4939 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>();
4940 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this);
4941 Blocks.push_back(Mem, BlkBVC);
4943 // If this is the first block, set it as the Entry and Exit.
4945 Entry = Exit = &back();
4947 // Return the block.
4951 /// buildCFG - Constructs a CFG from an AST.
4952 std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,
4953 ASTContext *C, const BuildOptions &BO) {
4954 CFGBuilder Builder(C, BO);
4955 return Builder.buildCFG(D, Statement);
4958 bool CFG::isLinear() const {
4959 // Quick path: if we only have the ENTRY block, the EXIT block, and some code
4960 // in between, then we have no room for control flow.
4964 // Traverse the CFG until we find a branch.
4965 // TODO: While this should still be very fast,
4966 // maybe we should cache the answer.
4967 llvm::SmallPtrSet<const CFGBlock *, 4> Visited;
4968 const CFGBlock *B = Entry;
4970 auto IteratorAndFlag = Visited.insert(B);
4971 if (!IteratorAndFlag.second) {
4972 // We looped back to a block that we've already visited. Not linear.
4976 // Iterate over reachable successors.
4977 const CFGBlock *FirstReachableB = nullptr;
4978 for (const CFGBlock::AdjacentBlock &AB : B->succs()) {
4979 if (!AB.isReachable())
4982 if (FirstReachableB == nullptr) {
4983 FirstReachableB = &*AB;
4985 // We've encountered a branch. It's not a linear CFG.
4990 if (!FirstReachableB) {
4991 // We reached a dead end. EXIT is unreachable. This is linear enough.
4995 // There's only one way to move forward. Proceed.
4996 B = FirstReachableB;
4999 // We reached EXIT and found no branches.
5003 const CXXDestructorDecl *
5004 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
5005 switch (getKind()) {
5006 case CFGElement::Initializer:
5007 case CFGElement::NewAllocator:
5008 case CFGElement::LoopExit:
5009 case CFGElement::LifetimeEnds:
5010 case CFGElement::Statement:
5011 case CFGElement::Constructor:
5012 case CFGElement::CXXRecordTypedCall:
5013 case CFGElement::ScopeBegin:
5014 case CFGElement::ScopeEnd:
5015 llvm_unreachable("getDestructorDecl should only be used with "
5017 case CFGElement::AutomaticObjectDtor: {
5018 const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();
5019 QualType ty = var->getType();
5021 // FIXME: See CFGBuilder::addLocalScopeForVarDecl.
5023 // Lifetime-extending constructs are handled here. This works for a single
5024 // temporary in an initializer expression.
5025 if (ty->isReferenceType()) {
5026 if (const Expr *Init = var->getInit()) {
5027 ty = getReferenceInitTemporaryType(Init);
5031 while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {
5032 ty = arrayType->getElementType();
5035 // The situation when the type of the lifetime-extending reference
5036 // does not correspond to the type of the object is supposed
5037 // to be handled by now. In particular, 'ty' is now the unwrapped
5039 const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();
5041 return classDecl->getDestructor();
5043 case CFGElement::DeleteDtor: {
5044 const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr();
5045 QualType DTy = DE->getDestroyedType();
5046 DTy = DTy.getNonReferenceType();
5047 const CXXRecordDecl *classDecl =
5048 astContext.getBaseElementType(DTy)->getAsCXXRecordDecl();
5049 return classDecl->getDestructor();
5051 case CFGElement::TemporaryDtor: {
5052 const CXXBindTemporaryExpr *bindExpr =
5053 castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
5054 const CXXTemporary *temp = bindExpr->getTemporary();
5055 return temp->getDestructor();
5057 case CFGElement::BaseDtor:
5058 case CFGElement::MemberDtor:
5059 // Not yet supported.
5062 llvm_unreachable("getKind() returned bogus value");
5065 //===----------------------------------------------------------------------===//
5066 // CFGBlock operations.
5067 //===----------------------------------------------------------------------===//
5069 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable)
5070 : ReachableBlock(IsReachable ? B : nullptr),
5071 UnreachableBlock(!IsReachable ? B : nullptr,
5072 B && IsReachable ? AB_Normal : AB_Unreachable) {}
5074 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock)
5075 : ReachableBlock(B),
5076 UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock,
5077 B == AlternateBlock ? AB_Alternate : AB_Normal) {}
5079 void CFGBlock::addSuccessor(AdjacentBlock Succ,
5080 BumpVectorContext &C) {
5081 if (CFGBlock *B = Succ.getReachableBlock())
5082 B->Preds.push_back(AdjacentBlock(this, Succ.isReachable()), C);
5084 if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock())
5085 UnreachableB->Preds.push_back(AdjacentBlock(this, false), C);
5087 Succs.push_back(Succ, C);
5090 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
5091 const CFGBlock *From, const CFGBlock *To) {
5092 if (F.IgnoreNullPredecessors && !From)
5095 if (To && From && F.IgnoreDefaultsWithCoveredEnums) {
5096 // If the 'To' has no label or is labeled but the label isn't a
5097 // CaseStmt then filter this edge.
5098 if (const SwitchStmt *S =
5099 dyn_cast_or_null<SwitchStmt>(From->getTerminatorStmt())) {
5100 if (S->isAllEnumCasesCovered()) {
5101 const Stmt *L = To->getLabel();
5102 if (!L || !isa<CaseStmt>(L))
5111 //===----------------------------------------------------------------------===//
5112 // CFG pretty printing
5113 //===----------------------------------------------------------------------===//
5117 class StmtPrinterHelper : public PrinterHelper {
5118 using StmtMapTy = llvm::DenseMap<const Stmt *, std::pair<unsigned, unsigned>>;
5119 using DeclMapTy = llvm::DenseMap<const Decl *, std::pair<unsigned, unsigned>>;
5123 signed currentBlock = 0;
5124 unsigned currStmt = 0;
5125 const LangOptions &LangOpts;
5128 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
5132 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
5134 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
5135 BI != BEnd; ++BI, ++j ) {
5136 if (Optional<CFGStmt> SE = BI->getAs<CFGStmt>()) {
5137 const Stmt *stmt= SE->getStmt();
5138 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
5141 switch (stmt->getStmtClass()) {
5142 case Stmt::DeclStmtClass:
5143 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;
5145 case Stmt::IfStmtClass: {
5146 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();
5151 case Stmt::ForStmtClass: {
5152 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();
5157 case Stmt::WhileStmtClass: {
5158 const VarDecl *var =
5159 cast<WhileStmt>(stmt)->getConditionVariable();
5164 case Stmt::SwitchStmtClass: {
5165 const VarDecl *var =
5166 cast<SwitchStmt>(stmt)->getConditionVariable();
5171 case Stmt::CXXCatchStmtClass: {
5172 const VarDecl *var =
5173 cast<CXXCatchStmt>(stmt)->getExceptionDecl();
5186 ~StmtPrinterHelper() override = default;
5188 const LangOptions &getLangOpts() const { return LangOpts; }
5189 void setBlockID(signed i) { currentBlock = i; }
5190 void setStmtID(unsigned i) { currStmt = i; }
5192 bool handledStmt(Stmt *S, raw_ostream &OS) override {
5193 StmtMapTy::iterator I = StmtMap.find(S);
5195 if (I == StmtMap.end())
5198 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
5199 && I->second.second == currStmt) {
5203 OS << "[B" << I->second.first << "." << I->second.second << "]";
5207 bool handleDecl(const Decl *D, raw_ostream &OS) {
5208 DeclMapTy::iterator I = DeclMap.find(D);
5210 if (I == DeclMap.end())
5213 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
5214 && I->second.second == currStmt) {
5218 OS << "[B" << I->second.first << "." << I->second.second << "]";
5223 class CFGBlockTerminatorPrint
5224 : public StmtVisitor<CFGBlockTerminatorPrint,void> {
5226 StmtPrinterHelper* Helper;
5227 PrintingPolicy Policy;
5230 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
5231 const PrintingPolicy &Policy)
5232 : OS(os), Helper(helper), Policy(Policy) {
5233 this->Policy.IncludeNewlines = false;
5236 void VisitIfStmt(IfStmt *I) {
5238 if (Stmt *C = I->getCond())
5239 C->printPretty(OS, Helper, Policy);
5243 void VisitStmt(Stmt *Terminator) {
5244 Terminator->printPretty(OS, Helper, Policy);
5247 void VisitDeclStmt(DeclStmt *DS) {
5248 VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
5249 OS << "static init " << VD->getName();
5252 void VisitForStmt(ForStmt *F) {
5257 if (Stmt *C = F->getCond())
5258 C->printPretty(OS, Helper, Policy);
5265 void VisitWhileStmt(WhileStmt *W) {
5267 if (Stmt *C = W->getCond())
5268 C->printPretty(OS, Helper, Policy);
5271 void VisitDoStmt(DoStmt *D) {
5272 OS << "do ... while ";
5273 if (Stmt *C = D->getCond())
5274 C->printPretty(OS, Helper, Policy);
5277 void VisitSwitchStmt(SwitchStmt *Terminator) {
5279 Terminator->getCond()->printPretty(OS, Helper, Policy);
5282 void VisitCXXTryStmt(CXXTryStmt *CS) {
5286 void VisitSEHTryStmt(SEHTryStmt *CS) {
5290 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
5291 if (Stmt *Cond = C->getCond())
5292 Cond->printPretty(OS, Helper, Policy);
5293 OS << " ? ... : ...";
5296 void VisitChooseExpr(ChooseExpr *C) {
5297 OS << "__builtin_choose_expr( ";
5298 if (Stmt *Cond = C->getCond())
5299 Cond->printPretty(OS, Helper, Policy);
5303 void VisitIndirectGotoStmt(IndirectGotoStmt *I) {
5305 if (Stmt *T = I->getTarget())
5306 T->printPretty(OS, Helper, Policy);
5309 void VisitBinaryOperator(BinaryOperator* B) {
5310 if (!B->isLogicalOp()) {
5316 B->getLHS()->printPretty(OS, Helper, Policy);
5318 switch (B->getOpcode()) {
5326 llvm_unreachable("Invalid logical operator.");
5330 void VisitExpr(Expr *E) {
5331 E->printPretty(OS, Helper, Policy);
5335 void print(CFGTerminator T) {
5336 switch (T.getKind()) {
5337 case CFGTerminator::StmtBranch:
5340 case CFGTerminator::TemporaryDtorsBranch:
5341 OS << "(Temp Dtor) ";
5344 case CFGTerminator::VirtualBaseBranch:
5345 OS << "(See if most derived ctor has already initialized vbases)";
5353 static void print_initializer(raw_ostream &OS, StmtPrinterHelper &Helper,
5354 const CXXCtorInitializer *I) {
5355 if (I->isBaseInitializer())
5356 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
5357 else if (I->isDelegatingInitializer())
5358 OS << I->getTypeSourceInfo()->getType()->getAsCXXRecordDecl()->getName();
5360 OS << I->getAnyMember()->getName();
5362 if (Expr *IE = I->getInit())
5363 IE->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));
5366 if (I->isBaseInitializer())
5367 OS << " (Base initializer)";
5368 else if (I->isDelegatingInitializer())
5369 OS << " (Delegating initializer)";
5371 OS << " (Member initializer)";
5374 static void print_construction_context(raw_ostream &OS,
5375 StmtPrinterHelper &Helper,
5376 const ConstructionContext *CC) {
5377 SmallVector<const Stmt *, 3> Stmts;
5378 switch (CC->getKind()) {
5379 case ConstructionContext::SimpleConstructorInitializerKind: {
5381 const auto *SICC = cast<SimpleConstructorInitializerConstructionContext>(CC);
5382 print_initializer(OS, Helper, SICC->getCXXCtorInitializer());
5385 case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind: {
5388 cast<CXX17ElidedCopyConstructorInitializerConstructionContext>(CC);
5389 print_initializer(OS, Helper, CICC->getCXXCtorInitializer());
5390 Stmts.push_back(CICC->getCXXBindTemporaryExpr());
5393 case ConstructionContext::SimpleVariableKind: {
5394 const auto *SDSCC = cast<SimpleVariableConstructionContext>(CC);
5395 Stmts.push_back(SDSCC->getDeclStmt());
5398 case ConstructionContext::CXX17ElidedCopyVariableKind: {
5399 const auto *CDSCC = cast<CXX17ElidedCopyVariableConstructionContext>(CC);
5400 Stmts.push_back(CDSCC->getDeclStmt());
5401 Stmts.push_back(CDSCC->getCXXBindTemporaryExpr());
5404 case ConstructionContext::NewAllocatedObjectKind: {
5405 const auto *NECC = cast<NewAllocatedObjectConstructionContext>(CC);
5406 Stmts.push_back(NECC->getCXXNewExpr());
5409 case ConstructionContext::SimpleReturnedValueKind: {
5410 const auto *RSCC = cast<SimpleReturnedValueConstructionContext>(CC);
5411 Stmts.push_back(RSCC->getReturnStmt());
5414 case ConstructionContext::CXX17ElidedCopyReturnedValueKind: {
5416 cast<CXX17ElidedCopyReturnedValueConstructionContext>(CC);
5417 Stmts.push_back(RSCC->getReturnStmt());
5418 Stmts.push_back(RSCC->getCXXBindTemporaryExpr());
5421 case ConstructionContext::SimpleTemporaryObjectKind: {
5422 const auto *TOCC = cast<SimpleTemporaryObjectConstructionContext>(CC);
5423 Stmts.push_back(TOCC->getCXXBindTemporaryExpr());
5424 Stmts.push_back(TOCC->getMaterializedTemporaryExpr());
5427 case ConstructionContext::ElidedTemporaryObjectKind: {
5428 const auto *TOCC = cast<ElidedTemporaryObjectConstructionContext>(CC);
5429 Stmts.push_back(TOCC->getCXXBindTemporaryExpr());
5430 Stmts.push_back(TOCC->getMaterializedTemporaryExpr());
5431 Stmts.push_back(TOCC->getConstructorAfterElision());
5434 case ConstructionContext::ArgumentKind: {
5435 const auto *ACC = cast<ArgumentConstructionContext>(CC);
5436 if (const Stmt *BTE = ACC->getCXXBindTemporaryExpr()) {
5438 Helper.handledStmt(const_cast<Stmt *>(BTE), OS);
5441 Helper.handledStmt(const_cast<Expr *>(ACC->getCallLikeExpr()), OS);
5442 OS << "+" << ACC->getIndex();
5449 Helper.handledStmt(const_cast<Stmt *>(I), OS);
5453 static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
5454 const CFGElement &E);
5456 void CFGElement::dumpToStream(llvm::raw_ostream &OS) const {
5457 StmtPrinterHelper Helper(nullptr, {});
5458 print_elem(OS, Helper, *this);
5461 static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
5462 const CFGElement &E) {
5463 switch (E.getKind()) {
5464 case CFGElement::Kind::Statement:
5465 case CFGElement::Kind::CXXRecordTypedCall:
5466 case CFGElement::Kind::Constructor: {
5467 CFGStmt CS = E.castAs<CFGStmt>();
5468 const Stmt *S = CS.getStmt();
5469 assert(S != nullptr && "Expecting non-null Stmt");
5471 // special printing for statement-expressions.
5472 if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) {
5473 const CompoundStmt *Sub = SE->getSubStmt();
5475 auto Children = Sub->children();
5476 if (Children.begin() != Children.end()) {
5478 Helper.handledStmt(*SE->getSubStmt()->body_rbegin(),OS);
5483 // special printing for comma expressions.
5484 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
5485 if (B->getOpcode() == BO_Comma) {
5487 Helper.handledStmt(B->getRHS(),OS);
5492 S->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));
5494 if (auto VTC = E.getAs<CFGCXXRecordTypedCall>()) {
5495 if (isa<CXXOperatorCallExpr>(S))
5496 OS << " (OperatorCall)";
5497 OS << " (CXXRecordTypedCall";
5498 print_construction_context(OS, Helper, VTC->getConstructionContext());
5500 } else if (isa<CXXOperatorCallExpr>(S)) {
5501 OS << " (OperatorCall)";
5502 } else if (isa<CXXBindTemporaryExpr>(S)) {
5503 OS << " (BindTemporary)";
5504 } else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) {
5505 OS << " (CXXConstructExpr";
5506 if (Optional<CFGConstructor> CE = E.getAs<CFGConstructor>()) {
5507 print_construction_context(OS, Helper, CE->getConstructionContext());
5509 OS << ", " << CCE->getType().getAsString() << ")";
5510 } else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) {
5511 OS << " (" << CE->getStmtClassName() << ", "
5512 << CE->getCastKindName()
5513 << ", " << CE->getType().getAsString()
5517 // Expressions need a newline.
5524 case CFGElement::Kind::Initializer:
5525 print_initializer(OS, Helper, E.castAs<CFGInitializer>().getInitializer());
5529 case CFGElement::Kind::AutomaticObjectDtor: {
5530 CFGAutomaticObjDtor DE = E.castAs<CFGAutomaticObjDtor>();
5531 const VarDecl *VD = DE.getVarDecl();
5532 Helper.handleDecl(VD, OS);
5534 QualType T = VD->getType();
5535 if (T->isReferenceType())
5536 T = getReferenceInitTemporaryType(VD->getInit(), nullptr);
5539 T.getUnqualifiedType().print(OS, PrintingPolicy(Helper.getLangOpts()));
5540 OS << "() (Implicit destructor)\n";
5544 case CFGElement::Kind::LifetimeEnds:
5545 Helper.handleDecl(E.castAs<CFGLifetimeEnds>().getVarDecl(), OS);
5546 OS << " (Lifetime ends)\n";
5549 case CFGElement::Kind::LoopExit:
5550 OS << E.castAs<CFGLoopExit>().getLoopStmt()->getStmtClassName() << " (LoopExit)\n";
5553 case CFGElement::Kind::ScopeBegin:
5554 OS << "CFGScopeBegin(";
5555 if (const VarDecl *VD = E.castAs<CFGScopeBegin>().getVarDecl())
5556 OS << VD->getQualifiedNameAsString();
5560 case CFGElement::Kind::ScopeEnd:
5561 OS << "CFGScopeEnd(";
5562 if (const VarDecl *VD = E.castAs<CFGScopeEnd>().getVarDecl())
5563 OS << VD->getQualifiedNameAsString();
5567 case CFGElement::Kind::NewAllocator:
5568 OS << "CFGNewAllocator(";
5569 if (const CXXNewExpr *AllocExpr = E.castAs<CFGNewAllocator>().getAllocatorExpr())
5570 AllocExpr->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
5574 case CFGElement::Kind::DeleteDtor: {
5575 CFGDeleteDtor DE = E.castAs<CFGDeleteDtor>();
5576 const CXXRecordDecl *RD = DE.getCXXRecordDecl();
5579 CXXDeleteExpr *DelExpr =
5580 const_cast<CXXDeleteExpr*>(DE.getDeleteExpr());
5581 Helper.handledStmt(cast<Stmt>(DelExpr->getArgument()), OS);
5582 OS << "->~" << RD->getName().str() << "()";
5583 OS << " (Implicit destructor)\n";
5587 case CFGElement::Kind::BaseDtor: {
5588 const CXXBaseSpecifier *BS = E.castAs<CFGBaseDtor>().getBaseSpecifier();
5589 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
5590 OS << " (Base object destructor)\n";
5594 case CFGElement::Kind::MemberDtor: {
5595 const FieldDecl *FD = E.castAs<CFGMemberDtor>().getFieldDecl();
5596 const Type *T = FD->getType()->getBaseElementTypeUnsafe();
5597 OS << "this->" << FD->getName();
5598 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
5599 OS << " (Member object destructor)\n";
5603 case CFGElement::Kind::TemporaryDtor: {
5604 const CXXBindTemporaryExpr *BT = E.castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
5606 BT->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
5607 OS << "() (Temporary object destructor)\n";
5613 static void print_block(raw_ostream &OS, const CFG* cfg,
5615 StmtPrinterHelper &Helper, bool print_edges,
5617 Helper.setBlockID(B.getBlockID());
5619 // Print the header.
5621 OS.changeColor(raw_ostream::YELLOW, true);
5623 OS << "\n [B" << B.getBlockID();
5625 if (&B == &cfg->getEntry())
5626 OS << " (ENTRY)]\n";
5627 else if (&B == &cfg->getExit())
5629 else if (&B == cfg->getIndirectGotoBlock())
5630 OS << " (INDIRECT GOTO DISPATCH)]\n";
5631 else if (B.hasNoReturnElement())
5632 OS << " (NORETURN)]\n";
5639 // Print the label of this block.
5640 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {
5644 if (LabelStmt *L = dyn_cast<LabelStmt>(Label))
5646 else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
5649 C->getLHS()->printPretty(OS, &Helper,
5650 PrintingPolicy(Helper.getLangOpts()));
5653 C->getRHS()->printPretty(OS, &Helper,
5654 PrintingPolicy(Helper.getLangOpts()));
5656 } else if (isa<DefaultStmt>(Label))
5658 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) {
5660 if (CS->getExceptionDecl())
5661 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper.getLangOpts()),
5666 } else if (SEHExceptStmt *ES = dyn_cast<SEHExceptStmt>(Label)) {
5668 ES->getFilterExpr()->printPretty(OS, &Helper,
5669 PrintingPolicy(Helper.getLangOpts()), 0);
5672 llvm_unreachable("Invalid label statement in CFGBlock.");
5677 // Iterate through the statements in the block and print them.
5680 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
5681 I != E ; ++I, ++j ) {
5682 // Print the statement # in the basic block and the statement itself.
5686 OS << llvm::format("%3d", j) << ": ";
5688 Helper.setStmtID(j);
5690 print_elem(OS, Helper, *I);
5693 // Print the terminator of this block.
5694 if (B.getTerminator().isValid()) {
5696 OS.changeColor(raw_ostream::GREEN);
5700 Helper.setBlockID(-1);
5702 PrintingPolicy PP(Helper.getLangOpts());
5703 CFGBlockTerminatorPrint TPrinter(OS, &Helper, PP);
5704 TPrinter.print(B.getTerminator());
5712 // Print the predecessors of this block.
5713 if (!B.pred_empty()) {
5714 const raw_ostream::Colors Color = raw_ostream::BLUE;
5716 OS.changeColor(Color);
5720 OS << '(' << B.pred_size() << "):";
5724 OS.changeColor(Color);
5726 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
5732 bool Reachable = true;
5735 B = I->getPossiblyUnreachableBlock();
5738 OS << " B" << B->getBlockID();
5740 OS << "(Unreachable)";
5749 // Print the successors of this block.
5750 if (!B.succ_empty()) {
5751 const raw_ostream::Colors Color = raw_ostream::MAGENTA;
5753 OS.changeColor(Color);
5757 OS << '(' << B.succ_size() << "):";
5761 OS.changeColor(Color);
5763 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
5770 bool Reachable = true;
5773 B = I->getPossiblyUnreachableBlock();
5777 OS << " B" << B->getBlockID();
5779 OS << "(Unreachable)";
5793 /// dump - A simple pretty printer of a CFG that outputs to stderr.
5794 void CFG::dump(const LangOptions &LO, bool ShowColors) const {
5795 print(llvm::errs(), LO, ShowColors);
5798 /// print - A simple pretty printer of a CFG that outputs to an ostream.
5799 void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
5800 StmtPrinterHelper Helper(this, LO);
5802 // Print the entry block.
5803 print_block(OS, this, getEntry(), Helper, true, ShowColors);
5805 // Iterate through the CFGBlocks and print them one by one.
5806 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
5807 // Skip the entry block, because we already printed it.
5808 if (&(**I) == &getEntry() || &(**I) == &getExit())
5811 print_block(OS, this, **I, Helper, true, ShowColors);
5814 // Print the exit block.
5815 print_block(OS, this, getExit(), Helper, true, ShowColors);
5820 size_t CFGBlock::getIndexInCFG() const {
5821 return llvm::find(*getParent(), this) - getParent()->begin();
5824 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
5825 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
5826 bool ShowColors) const {
5827 print(llvm::errs(), cfg, LO, ShowColors);
5830 LLVM_DUMP_METHOD void CFGBlock::dump() const {
5831 dump(getParent(), LangOptions(), false);
5834 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
5835 /// Generally this will only be called from CFG::print.
5836 void CFGBlock::print(raw_ostream &OS, const CFG* cfg,
5837 const LangOptions &LO, bool ShowColors) const {
5838 StmtPrinterHelper Helper(cfg, LO);
5839 print_block(OS, cfg, *this, Helper, true, ShowColors);
5843 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
5844 void CFGBlock::printTerminator(raw_ostream &OS,
5845 const LangOptions &LO) const {
5846 CFGBlockTerminatorPrint TPrinter(OS, nullptr, PrintingPolicy(LO));
5847 TPrinter.print(getTerminator());
5850 /// printTerminatorJson - Pretty-prints the terminator in JSON format.
5851 void CFGBlock::printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
5852 bool AddQuotes) const {
5854 llvm::raw_string_ostream TempOut(Buf);
5856 printTerminator(TempOut, LO);
5858 Out << JsonFormat(TempOut.str(), AddQuotes);
5861 // Returns true if by simply looking at the block, we can be sure that it
5862 // results in a sink during analysis. This is useful to know when the analysis
5863 // was interrupted, and we try to figure out if it would sink eventually.
5864 // There may be many more reasons why a sink would appear during analysis
5865 // (eg. checkers may generate sinks arbitrarily), but here we only consider
5866 // sinks that would be obvious by looking at the CFG.
5867 static bool isImmediateSinkBlock(const CFGBlock *Blk) {
5868 if (Blk->hasNoReturnElement())
5871 // FIXME: Throw-expressions are currently generating sinks during analysis:
5872 // they're not supported yet, and also often used for actually terminating
5873 // the program. So we should treat them as sinks in this analysis as well,
5874 // at least for now, but once we have better support for exceptions,
5875 // we'd need to carefully handle the case when the throw is being
5876 // immediately caught.
5877 if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) {
5878 if (Optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())
5879 if (isa<CXXThrowExpr>(StmtElm->getStmt()))
5888 bool CFGBlock::isInevitablySinking() const {
5889 const CFG &Cfg = *getParent();
5891 const CFGBlock *StartBlk = this;
5892 if (isImmediateSinkBlock(StartBlk))
5895 llvm::SmallVector<const CFGBlock *, 32> DFSWorkList;
5896 llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
5898 DFSWorkList.push_back(StartBlk);
5899 while (!DFSWorkList.empty()) {
5900 const CFGBlock *Blk = DFSWorkList.back();
5901 DFSWorkList.pop_back();
5902 Visited.insert(Blk);
5904 // If at least one path reaches the CFG exit, it means that control is
5905 // returned to the caller. For now, say that we are not sure what
5906 // happens next. If necessary, this can be improved to analyze
5907 // the parent StackFrameContext's call site in a similar manner.
5908 if (Blk == &Cfg.getExit())
5911 for (const auto &Succ : Blk->succs()) {
5912 if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {
5913 if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) {
5914 // If the block has reachable child blocks that aren't no-return,
5915 // add them to the worklist.
5916 DFSWorkList.push_back(SuccBlk);
5922 // Nothing reached the exit. It can only mean one thing: there's no return.
5926 const Expr *CFGBlock::getLastCondition() const {
5927 // If the terminator is a temporary dtor or a virtual base, etc, we can't
5928 // retrieve a meaningful condition, bail out.
5929 if (Terminator.getKind() != CFGTerminator::StmtBranch)
5932 // Also, if this method was called on a block that doesn't have 2 successors,
5933 // this block doesn't have retrievable condition.
5934 if (succ_size() < 2)
5937 // FIXME: Is there a better condition expression we can return in this case?
5941 auto StmtElem = rbegin()->getAs<CFGStmt>();
5945 const Stmt *Cond = StmtElem->getStmt();
5946 if (isa<ObjCForCollectionStmt>(Cond) || isa<DeclStmt>(Cond))
5949 // Only ObjCForCollectionStmt is known not to be a non-Expr terminator, hence
5951 return cast<Expr>(Cond)->IgnoreParens();
5954 Stmt *CFGBlock::getTerminatorCondition(bool StripParens) {
5955 Stmt *Terminator = getTerminatorStmt();
5961 switch (Terminator->getStmtClass()) {
5965 case Stmt::CXXForRangeStmtClass:
5966 E = cast<CXXForRangeStmt>(Terminator)->getCond();
5969 case Stmt::ForStmtClass:
5970 E = cast<ForStmt>(Terminator)->getCond();
5973 case Stmt::WhileStmtClass:
5974 E = cast<WhileStmt>(Terminator)->getCond();
5977 case Stmt::DoStmtClass:
5978 E = cast<DoStmt>(Terminator)->getCond();
5981 case Stmt::IfStmtClass:
5982 E = cast<IfStmt>(Terminator)->getCond();
5985 case Stmt::ChooseExprClass:
5986 E = cast<ChooseExpr>(Terminator)->getCond();
5989 case Stmt::IndirectGotoStmtClass:
5990 E = cast<IndirectGotoStmt>(Terminator)->getTarget();
5993 case Stmt::SwitchStmtClass:
5994 E = cast<SwitchStmt>(Terminator)->getCond();
5997 case Stmt::BinaryConditionalOperatorClass:
5998 E = cast<BinaryConditionalOperator>(Terminator)->getCond();
6001 case Stmt::ConditionalOperatorClass:
6002 E = cast<ConditionalOperator>(Terminator)->getCond();
6005 case Stmt::BinaryOperatorClass: // '&&' and '||'
6006 E = cast<BinaryOperator>(Terminator)->getLHS();
6009 case Stmt::ObjCForCollectionStmtClass:
6016 return E ? E->IgnoreParens() : nullptr;
6019 //===----------------------------------------------------------------------===//
6020 // CFG Graphviz Visualization
6021 //===----------------------------------------------------------------------===//
6024 static StmtPrinterHelper* GraphHelper;
6027 void CFG::viewCFG(const LangOptions &LO) const {
6029 StmtPrinterHelper H(this, LO);
6031 llvm::ViewGraph(this,"CFG");
6032 GraphHelper = nullptr;
6039 struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
6040 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
6042 static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) {
6044 std::string OutSStr;
6045 llvm::raw_string_ostream Out(OutSStr);
6046 print_block(Out,Graph, *Node, *GraphHelper, false, false);
6047 std::string& OutStr = Out.str();
6049 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
6051 // Process string output to make it nicer...
6052 for (unsigned i = 0; i != OutStr.length(); ++i)
6053 if (OutStr[i] == '\n') { // Left justify
6055 OutStr.insert(OutStr.begin()+i+1, 'l');