1 //===- CFG.cpp - Classes for representing and building CFGs ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the CFG and CFGBuilder classes for representing and
11 // building Control-Flow Graphs (CFGs) from ASTs.
13 //===----------------------------------------------------------------------===//
15 #include "clang/Analysis/CFG.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/Attr.h"
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/DeclBase.h"
20 #include "clang/AST/DeclCXX.h"
21 #include "clang/AST/DeclGroup.h"
22 #include "clang/AST/Expr.h"
23 #include "clang/AST/ExprCXX.h"
24 #include "clang/AST/OperationKinds.h"
25 #include "clang/AST/PrettyPrinter.h"
26 #include "clang/AST/Stmt.h"
27 #include "clang/AST/StmtCXX.h"
28 #include "clang/AST/StmtObjC.h"
29 #include "clang/AST/StmtVisitor.h"
30 #include "clang/AST/Type.h"
31 #include "clang/Analysis/Support/BumpVector.h"
32 #include "clang/Analysis/ConstructionContext.h"
33 #include "clang/Basic/Builtins.h"
34 #include "clang/Basic/ExceptionSpecificationType.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 /// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral
74 /// or EnumConstantDecl from the given Expr. If it fails, returns nullptr.
75 static const Expr *tryTransformToIntOrEnumConstant(const Expr *E) {
76 E = E->IgnoreParens();
77 if (isa<IntegerLiteral>(E))
79 if (auto *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts()))
80 return isa<EnumConstantDecl>(DR->getDecl()) ? DR : nullptr;
84 /// Tries to interpret a binary operator into `Decl Op Expr` form, if Expr is
85 /// an integer literal or an enum constant.
87 /// If this fails, at least one of the returned DeclRefExpr or Expr will be
89 static std::tuple<const DeclRefExpr *, BinaryOperatorKind, const Expr *>
90 tryNormalizeBinaryOperator(const BinaryOperator *B) {
91 BinaryOperatorKind Op = B->getOpcode();
93 const Expr *MaybeDecl = B->getLHS();
94 const Expr *Constant = tryTransformToIntOrEnumConstant(B->getRHS());
95 // Expr looked like `0 == Foo` instead of `Foo == 0`
96 if (Constant == nullptr) {
100 else if (Op == BO_GE)
102 else if (Op == BO_LT)
104 else if (Op == BO_LE)
107 MaybeDecl = B->getRHS();
108 Constant = tryTransformToIntOrEnumConstant(B->getLHS());
111 auto *D = dyn_cast<DeclRefExpr>(MaybeDecl->IgnoreParenImpCasts());
112 return std::make_tuple(D, Op, Constant);
115 /// For an expression `x == Foo && x == Bar`, this determines whether the
116 /// `Foo` and `Bar` are either of the same enumeration type, or both integer
119 /// It's an error to pass this arguments that are not either IntegerLiterals
120 /// or DeclRefExprs (that have decls of type EnumConstantDecl)
121 static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) {
122 // User intent isn't clear if they're mixing int literals with enum
124 if (isa<IntegerLiteral>(E1) != isa<IntegerLiteral>(E2))
127 // Integer literal comparisons, regardless of literal type, are acceptable.
128 if (isa<IntegerLiteral>(E1))
131 // IntegerLiterals are handled above and only EnumConstantDecls are expected
133 assert(isa<DeclRefExpr>(E1) && isa<DeclRefExpr>(E2));
134 auto *Decl1 = cast<DeclRefExpr>(E1)->getDecl();
135 auto *Decl2 = cast<DeclRefExpr>(E2)->getDecl();
137 assert(isa<EnumConstantDecl>(Decl1) && isa<EnumConstantDecl>(Decl2));
138 const DeclContext *DC1 = Decl1->getDeclContext();
139 const DeclContext *DC2 = Decl2->getDeclContext();
141 assert(isa<EnumDecl>(DC1) && isa<EnumDecl>(DC2));
149 /// The CFG builder uses a recursive algorithm to build the CFG. When
150 /// we process an expression, sometimes we know that we must add the
151 /// subexpressions as block-level expressions. For example:
155 /// When processing the '||' expression, we know that exp1 and exp2
156 /// need to be added as block-level expressions, even though they
157 /// might not normally need to be. AddStmtChoice records this
158 /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then
159 /// the builder has an option not to add a subexpression as a
160 /// block-level expression.
161 class AddStmtChoice {
163 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };
165 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}
167 bool alwaysAdd(CFGBuilder &builder,
168 const Stmt *stmt) const;
170 /// Return a copy of this object, except with the 'always-add' bit
171 /// set as specified.
172 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {
173 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd);
180 /// LocalScope - Node in tree of local scopes created for C++ implicit
181 /// destructor calls generation. It contains list of automatic variables
182 /// declared in the scope and link to position in previous scope this scope
185 /// The process of creating local scopes is as follows:
186 /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
187 /// - Before processing statements in scope (e.g. CompoundStmt) create
188 /// LocalScope object using CFGBuilder::ScopePos as link to previous scope
189 /// and set CFGBuilder::ScopePos to the end of new scope,
190 /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
192 /// - For every normal (without jump) end of scope add to CFGBlock destructors
193 /// for objects in the current scope,
194 /// - For every jump add to CFGBlock destructors for objects
195 /// between CFGBuilder::ScopePos and local scope position saved for jump
196 /// target. Thanks to C++ restrictions on goto jumps we can be sure that
197 /// jump target position will be on the path to root from CFGBuilder::ScopePos
198 /// (adding any variable that doesn't need constructor to be called to
199 /// LocalScope can break this assumption),
203 friend class const_iterator;
205 using AutomaticVarsTy = BumpVector<VarDecl *>;
207 /// const_iterator - Iterates local scope backwards and jumps to previous
208 /// scope on reaching the beginning of currently iterated scope.
209 class const_iterator {
210 const LocalScope* Scope = nullptr;
212 /// VarIter is guaranteed to be greater then 0 for every valid iterator.
213 /// Invalid iterator (with null Scope) has VarIter equal to 0.
214 unsigned VarIter = 0;
217 /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
218 /// Incrementing invalid iterator is allowed and will result in invalid
220 const_iterator() = default;
222 /// Create valid iterator. In case when S.Prev is an invalid iterator and
223 /// I is equal to 0, this will create invalid iterator.
224 const_iterator(const LocalScope& S, unsigned I)
225 : Scope(&S), VarIter(I) {
226 // Iterator to "end" of scope is not allowed. Handle it by going up
227 // in scopes tree possibly up to invalid iterator in the root.
228 if (VarIter == 0 && Scope)
232 VarDecl *const* operator->() const {
233 assert(Scope && "Dereferencing invalid iterator is not allowed");
234 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
235 return &Scope->Vars[VarIter - 1];
238 const VarDecl *getFirstVarInScope() const {
239 assert(Scope && "Dereferencing invalid iterator is not allowed");
240 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
241 return Scope->Vars[0];
244 VarDecl *operator*() const {
245 return *this->operator->();
248 const_iterator &operator++() {
252 assert(VarIter != 0 && "Iterator has invalid value of VarIter member");
258 const_iterator operator++(int) {
259 const_iterator P = *this;
264 bool operator==(const const_iterator &rhs) const {
265 return Scope == rhs.Scope && VarIter == rhs.VarIter;
267 bool operator!=(const const_iterator &rhs) const {
268 return !(*this == rhs);
271 explicit operator bool() const {
272 return *this != const_iterator();
275 int distance(const_iterator L);
276 const_iterator shared_parent(const_iterator L);
277 bool pointsToFirstDeclaredVar() { return VarIter == 1; }
281 BumpVectorContext ctx;
283 /// Automatic variables in order of declaration.
284 AutomaticVarsTy Vars;
286 /// Iterator to variable in previous scope that was declared just before
287 /// begin of this scope.
291 /// Constructs empty scope linked to previous scope in specified place.
292 LocalScope(BumpVectorContext ctx, const_iterator P)
293 : ctx(std::move(ctx)), Vars(this->ctx, 4), Prev(P) {}
295 /// Begin of scope in direction of CFG building (backwards).
296 const_iterator begin() const { return const_iterator(*this, Vars.size()); }
298 void addVar(VarDecl *VD) {
299 Vars.push_back(VD, ctx);
305 /// distance - Calculates distance from this to L. L must be reachable from this
306 /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
307 /// number of scopes between this and L.
308 int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
310 const_iterator F = *this;
311 while (F.Scope != L.Scope) {
312 assert(F != const_iterator() &&
313 "L iterator is not reachable from F iterator.");
317 D += F.VarIter - L.VarIter;
321 /// Calculates the closest parent of this iterator
322 /// that is in a scope reachable through the parents of L.
323 /// I.e. when using 'goto' from this to L, the lifetime of all variables
324 /// between this and shared_parent(L) end.
325 LocalScope::const_iterator
326 LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) {
327 llvm::SmallPtrSet<const LocalScope *, 4> ScopesOfL;
329 ScopesOfL.insert(L.Scope);
330 if (L == const_iterator())
335 const_iterator F = *this;
337 if (ScopesOfL.count(F.Scope))
339 assert(F != const_iterator() &&
340 "L iterator is not reachable from F iterator.");
347 /// Structure for specifying position in CFG during its build process. It
348 /// consists of CFGBlock that specifies position in CFG and
349 /// LocalScope::const_iterator that specifies position in LocalScope graph.
350 struct BlockScopePosPair {
351 CFGBlock *block = nullptr;
352 LocalScope::const_iterator scopePosition;
354 BlockScopePosPair() = default;
355 BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos)
356 : block(b), scopePosition(scopePos) {}
359 /// TryResult - a class representing a variant over the values
360 /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool,
361 /// and is used by the CFGBuilder to decide if a branch condition
362 /// can be decided up front during CFG construction.
367 TryResult() = default;
368 TryResult(bool b) : X(b ? 1 : 0) {}
370 bool isTrue() const { return X == 1; }
371 bool isFalse() const { return X == 0; }
372 bool isKnown() const { return X >= 0; }
382 static TryResult bothKnownTrue(TryResult R1, TryResult R2) {
383 if (!R1.isKnown() || !R2.isKnown())
385 return TryResult(R1.isTrue() && R2.isTrue());
390 class reverse_children {
391 llvm::SmallVector<Stmt *, 12> childrenBuf;
392 ArrayRef<Stmt *> children;
395 reverse_children(Stmt *S);
397 using iterator = ArrayRef<Stmt *>::reverse_iterator;
399 iterator begin() const { return children.rbegin(); }
400 iterator end() const { return children.rend(); }
405 reverse_children::reverse_children(Stmt *S) {
406 if (CallExpr *CE = dyn_cast<CallExpr>(S)) {
407 children = CE->getRawSubExprs();
410 switch (S->getStmtClass()) {
411 // Note: Fill in this switch with more cases we want to optimize.
412 case Stmt::InitListExprClass: {
413 InitListExpr *IE = cast<InitListExpr>(S);
414 children = llvm::makeArrayRef(reinterpret_cast<Stmt**>(IE->getInits()),
422 // Default case for all other statements.
423 for (Stmt *SubStmt : S->children())
424 childrenBuf.push_back(SubStmt);
426 // This needs to be done *after* childrenBuf has been populated.
427 children = childrenBuf;
432 /// CFGBuilder - This class implements CFG construction from an AST.
433 /// The builder is stateful: an instance of the builder should be used to only
434 /// construct a single CFG.
438 /// CFGBuilder builder;
439 /// std::unique_ptr<CFG> cfg = builder.buildCFG(decl, stmt1);
441 /// CFG construction is done via a recursive walk of an AST. We actually parse
442 /// the AST in reverse order so that the successor of a basic block is
443 /// constructed prior to its predecessor. This allows us to nicely capture
444 /// implicit fall-throughs without extra basic blocks.
446 using JumpTarget = BlockScopePosPair;
447 using JumpSource = BlockScopePosPair;
450 std::unique_ptr<CFG> cfg;
453 CFGBlock *Block = nullptr;
455 // Block after the current block.
456 CFGBlock *Succ = nullptr;
458 JumpTarget ContinueJumpTarget;
459 JumpTarget BreakJumpTarget;
460 JumpTarget SEHLeaveJumpTarget;
461 CFGBlock *SwitchTerminatedBlock = nullptr;
462 CFGBlock *DefaultCaseBlock = nullptr;
464 // This can point either to a try or a __try block. The frontend forbids
465 // mixing both kinds in one function, so having one for both is enough.
466 CFGBlock *TryTerminatedBlock = nullptr;
468 // Current position in local scope.
469 LocalScope::const_iterator ScopePos;
471 // LabelMap records the mapping from Label expressions to their jump targets.
472 using LabelMapTy = llvm::DenseMap<LabelDecl *, JumpTarget>;
475 // A list of blocks that end with a "goto" that must be backpatched to their
476 // resolved targets upon completion of CFG construction.
477 using BackpatchBlocksTy = std::vector<JumpSource>;
478 BackpatchBlocksTy BackpatchBlocks;
480 // A list of labels whose address has been taken (for indirect gotos).
481 using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>;
482 LabelSetTy AddressTakenLabels;
484 // Information about the currently visited C++ object construction site.
485 // This is set in the construction trigger and read when the constructor
486 // or a function that returns an object by value is being visited.
487 llvm::DenseMap<Expr *, const ConstructionContextLayer *>
488 ConstructionContextMap;
490 using DeclsWithEndedScopeSetTy = llvm::SmallSetVector<VarDecl *, 16>;
491 DeclsWithEndedScopeSetTy DeclsWithEndedScope;
494 const CFG::BuildOptions &BuildOpts;
496 // State to track for building switch statements.
497 bool switchExclusivelyCovered = false;
498 Expr::EvalResult *switchCond = nullptr;
500 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr;
501 const Stmt *lastLookup = nullptr;
503 // Caches boolean evaluations of expressions to avoid multiple re-evaluations
504 // during construction of branches for chained logical operators.
505 using CachedBoolEvalsTy = llvm::DenseMap<Expr *, TryResult>;
506 CachedBoolEvalsTy CachedBoolEvals;
509 explicit CFGBuilder(ASTContext *astContext,
510 const CFG::BuildOptions &buildOpts)
511 : Context(astContext), cfg(new CFG()), // crew a new CFG
512 ConstructionContextMap(), BuildOpts(buildOpts) {}
515 // buildCFG - Used by external clients to construct the CFG.
516 std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement);
518 bool alwaysAdd(const Stmt *stmt);
521 // Visitors to walk an AST and construct the CFG.
522 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
523 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);
524 CFGBlock *VisitBreakStmt(BreakStmt *B);
525 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);
526 CFGBlock *VisitCaseStmt(CaseStmt *C);
527 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);
528 CFGBlock *VisitCompoundStmt(CompoundStmt *C);
529 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,
531 CFGBlock *VisitContinueStmt(ContinueStmt *C);
532 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
534 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
535 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
536 CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc);
537 CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc);
538 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
539 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
541 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
543 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);
544 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);
545 CFGBlock *VisitDeclStmt(DeclStmt *DS);
546 CFGBlock *VisitDeclSubExpr(DeclStmt *DS);
547 CFGBlock *VisitDefaultStmt(DefaultStmt *D);
548 CFGBlock *VisitDoStmt(DoStmt *D);
549 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, AddStmtChoice asc);
550 CFGBlock *VisitForStmt(ForStmt *F);
551 CFGBlock *VisitGotoStmt(GotoStmt *G);
552 CFGBlock *VisitIfStmt(IfStmt *I);
553 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);
554 CFGBlock *VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc);
555 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);
556 CFGBlock *VisitLabelStmt(LabelStmt *L);
557 CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc);
558 CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc);
559 CFGBlock *VisitLogicalOperator(BinaryOperator *B);
560 std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B,
563 CFGBlock *FalseBlock);
564 CFGBlock *VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
566 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);
567 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);
568 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
569 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
570 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);
571 CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S);
572 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);
573 CFGBlock *VisitObjCMessageExpr(ObjCMessageExpr *E, AddStmtChoice asc);
574 CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E);
575 CFGBlock *VisitReturnStmt(Stmt *S);
576 CFGBlock *VisitSEHExceptStmt(SEHExceptStmt *S);
577 CFGBlock *VisitSEHFinallyStmt(SEHFinallyStmt *S);
578 CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S);
579 CFGBlock *VisitSEHTryStmt(SEHTryStmt *S);
580 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
581 CFGBlock *VisitSwitchStmt(SwitchStmt *S);
582 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
584 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
585 CFGBlock *VisitWhileStmt(WhileStmt *W);
587 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd);
588 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
589 CFGBlock *VisitChildren(Stmt *S);
590 CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc);
592 void maybeAddScopeBeginForVarDecl(CFGBlock *B, const VarDecl *VD,
594 if (ScopePos && (VD == ScopePos.getFirstVarInScope()))
595 appendScopeBegin(B, VD, S);
598 /// When creating the CFG for temporary destructors, we want to mirror the
599 /// branch structure of the corresponding constructor calls.
600 /// Thus, while visiting a statement for temporary destructors, we keep a
601 /// context to keep track of the following information:
602 /// - whether a subexpression is executed unconditionally
603 /// - if a subexpression is executed conditionally, the first
604 /// CXXBindTemporaryExpr we encounter in that subexpression (which
605 /// corresponds to the last temporary destructor we have to call for this
606 /// subexpression) and the CFG block at that point (which will become the
607 /// successor block when inserting the decision point).
609 /// That way, we can build the branch structure for temporary destructors as
611 /// 1. If a subexpression is executed unconditionally, we add the temporary
612 /// destructor calls to the current block.
613 /// 2. If a subexpression is executed conditionally, when we encounter a
614 /// CXXBindTemporaryExpr:
615 /// a) If it is the first temporary destructor call in the subexpression,
616 /// we remember the CXXBindTemporaryExpr and the current block in the
617 /// TempDtorContext; we start a new block, and insert the temporary
619 /// b) Otherwise, add the temporary destructor call to the current block.
620 /// 3. When we finished visiting a conditionally executed subexpression,
621 /// and we found at least one temporary constructor during the visitation
622 /// (2.a has executed), we insert a decision block that uses the
623 /// CXXBindTemporaryExpr as terminator, and branches to the current block
624 /// if the CXXBindTemporaryExpr was marked executed, and otherwise
625 /// branches to the stored successor.
626 struct TempDtorContext {
627 TempDtorContext() = default;
628 TempDtorContext(TryResult KnownExecuted)
629 : IsConditional(true), KnownExecuted(KnownExecuted) {}
631 /// Returns whether we need to start a new branch for a temporary destructor
632 /// call. This is the case when the temporary destructor is
633 /// conditionally executed, and it is the first one we encounter while
634 /// visiting a subexpression - other temporary destructors at the same level
635 /// will be added to the same block and are executed under the same
637 bool needsTempDtorBranch() const {
638 return IsConditional && !TerminatorExpr;
641 /// Remember the successor S of a temporary destructor decision branch for
642 /// the corresponding CXXBindTemporaryExpr E.
643 void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) {
648 const bool IsConditional = false;
649 const TryResult KnownExecuted = true;
650 CFGBlock *Succ = nullptr;
651 CXXBindTemporaryExpr *TerminatorExpr = nullptr;
654 // Visitors to walk an AST and generate destructors of temporaries in
656 CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary,
657 TempDtorContext &Context);
658 CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E, TempDtorContext &Context);
659 CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E,
660 TempDtorContext &Context);
661 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(
662 CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context);
663 CFGBlock *VisitConditionalOperatorForTemporaryDtors(
664 AbstractConditionalOperator *E, bool BindToTemporary,
665 TempDtorContext &Context);
666 void InsertTempDtorDecisionBlock(const TempDtorContext &Context,
667 CFGBlock *FalseSucc = nullptr);
669 // NYS == Not Yet Supported
675 // Remember to apply the construction context based on the current \p Layer
676 // when constructing the CFG element for \p CE.
677 void consumeConstructionContext(const ConstructionContextLayer *Layer,
680 // Scan \p Child statement to find constructors in it, while keeping in mind
681 // that its parent statement is providing a partial construction context
682 // described by \p Layer. If a constructor is found, it would be assigned
683 // the context based on the layer. If an additional construction context layer
684 // is found, the function recurses into that.
685 void findConstructionContexts(const ConstructionContextLayer *Layer,
688 // Scan all arguments of a call expression for a construction context.
689 // These sorts of call expressions don't have a common superclass,
690 // hence strict duck-typing.
691 template <typename CallLikeExpr,
692 typename = typename std::enable_if<
693 std::is_same<CallLikeExpr, CallExpr>::value ||
694 std::is_same<CallLikeExpr, CXXConstructExpr>::value ||
695 std::is_same<CallLikeExpr, ObjCMessageExpr>::value>>
696 void findConstructionContextsForArguments(CallLikeExpr *E) {
697 for (unsigned i = 0, e = E->getNumArgs(); i != e; ++i) {
698 Expr *Arg = E->getArg(i);
699 if (Arg->getType()->getAsCXXRecordDecl() && !Arg->isGLValue())
700 findConstructionContexts(
701 ConstructionContextLayer::create(cfg->getBumpVectorContext(),
702 ConstructionContextItem(E, i)),
707 // Unset the construction context after consuming it. This is done immediately
708 // after adding the CFGConstructor or CFGCXXRecordTypedCall element, so
709 // there's no need to do this manually in every Visit... function.
710 void cleanupConstructionContext(Expr *E);
712 void autoCreateBlock() { if (!Block) Block = createBlock(); }
713 CFGBlock *createBlock(bool add_successor = true);
714 CFGBlock *createNoReturnBlock();
716 CFGBlock *addStmt(Stmt *S) {
717 return Visit(S, AddStmtChoice::AlwaysAdd);
720 CFGBlock *addInitializer(CXXCtorInitializer *I);
721 void addLoopExit(const Stmt *LoopStmt);
722 void addAutomaticObjDtors(LocalScope::const_iterator B,
723 LocalScope::const_iterator E, Stmt *S);
724 void addLifetimeEnds(LocalScope::const_iterator B,
725 LocalScope::const_iterator E, Stmt *S);
726 void addAutomaticObjHandling(LocalScope::const_iterator B,
727 LocalScope::const_iterator E, Stmt *S);
728 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
729 void addScopesEnd(LocalScope::const_iterator B, LocalScope::const_iterator E,
732 void getDeclsWithEndedScope(LocalScope::const_iterator B,
733 LocalScope::const_iterator E, Stmt *S);
735 // Local scopes creation.
736 LocalScope* createOrReuseLocalScope(LocalScope* Scope);
738 void addLocalScopeForStmt(Stmt *S);
739 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,
740 LocalScope* Scope = nullptr);
741 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);
743 void addLocalScopeAndDtors(Stmt *S);
745 const ConstructionContext *retrieveAndCleanupConstructionContext(Expr *E) {
746 if (!BuildOpts.AddRichCXXConstructors)
749 const ConstructionContextLayer *Layer = ConstructionContextMap.lookup(E);
753 cleanupConstructionContext(E);
754 return ConstructionContext::createFromLayers(cfg->getBumpVectorContext(),
758 // Interface to CFGBlock - adding CFGElements.
760 void appendStmt(CFGBlock *B, const Stmt *S) {
761 if (alwaysAdd(S) && cachedEntry)
762 cachedEntry->second = B;
764 // All block-level expressions should have already been IgnoreParens()ed.
765 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
766 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
769 void appendConstructor(CFGBlock *B, CXXConstructExpr *CE) {
770 if (const ConstructionContext *CC =
771 retrieveAndCleanupConstructionContext(CE)) {
772 B->appendConstructor(CE, CC, cfg->getBumpVectorContext());
776 // No valid construction context found. Fall back to statement.
777 B->appendStmt(CE, cfg->getBumpVectorContext());
780 void appendCall(CFGBlock *B, CallExpr *CE) {
781 if (alwaysAdd(CE) && cachedEntry)
782 cachedEntry->second = B;
784 if (const ConstructionContext *CC =
785 retrieveAndCleanupConstructionContext(CE)) {
786 B->appendCXXRecordTypedCall(CE, CC, cfg->getBumpVectorContext());
790 // No valid construction context found. Fall back to statement.
791 B->appendStmt(CE, cfg->getBumpVectorContext());
794 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
795 B->appendInitializer(I, cfg->getBumpVectorContext());
798 void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {
799 B->appendNewAllocator(NE, cfg->getBumpVectorContext());
802 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
803 B->appendBaseDtor(BS, cfg->getBumpVectorContext());
806 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
807 B->appendMemberDtor(FD, cfg->getBumpVectorContext());
810 void appendObjCMessage(CFGBlock *B, ObjCMessageExpr *ME) {
811 if (alwaysAdd(ME) && cachedEntry)
812 cachedEntry->second = B;
814 if (const ConstructionContext *CC =
815 retrieveAndCleanupConstructionContext(ME)) {
816 B->appendCXXRecordTypedCall(ME, CC, cfg->getBumpVectorContext());
820 B->appendStmt(const_cast<ObjCMessageExpr *>(ME),
821 cfg->getBumpVectorContext());
824 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
825 B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
828 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
829 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
832 void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {
833 B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());
836 void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) {
837 B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext());
840 void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
841 B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
844 void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
845 LocalScope::const_iterator B, LocalScope::const_iterator E);
847 void prependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk,
848 LocalScope::const_iterator B,
849 LocalScope::const_iterator E);
852 prependAutomaticObjScopeEndWithTerminator(CFGBlock *Blk,
853 LocalScope::const_iterator B,
854 LocalScope::const_iterator E);
856 void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {
857 B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable),
858 cfg->getBumpVectorContext());
861 /// Add a reachable successor to a block, with the alternate variant that is
863 void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {
864 B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),
865 cfg->getBumpVectorContext());
868 void appendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
869 if (BuildOpts.AddScopes)
870 B->appendScopeBegin(VD, S, cfg->getBumpVectorContext());
873 void prependScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
874 if (BuildOpts.AddScopes)
875 B->prependScopeBegin(VD, S, cfg->getBumpVectorContext());
878 void appendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
879 if (BuildOpts.AddScopes)
880 B->appendScopeEnd(VD, S, cfg->getBumpVectorContext());
883 void prependScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
884 if (BuildOpts.AddScopes)
885 B->prependScopeEnd(VD, S, cfg->getBumpVectorContext());
888 /// Find a relational comparison with an expression evaluating to a
889 /// boolean and a constant other than 0 and 1.
890 /// e.g. if ((x < y) == 10)
891 TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) {
892 const Expr *LHSExpr = B->getLHS()->IgnoreParens();
893 const Expr *RHSExpr = B->getRHS()->IgnoreParens();
895 const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
896 const Expr *BoolExpr = RHSExpr;
897 bool IntFirst = true;
899 IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
904 if (!IntLiteral || !BoolExpr->isKnownToHaveBooleanValue())
907 llvm::APInt IntValue = IntLiteral->getValue();
908 if ((IntValue == 1) || (IntValue == 0))
911 bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() ||
912 !IntValue.isNegative();
914 BinaryOperatorKind Bok = B->getOpcode();
915 if (Bok == BO_GT || Bok == BO_GE) {
916 // Always true for 10 > bool and bool > -1
917 // Always false for -1 > bool and bool > 10
918 return TryResult(IntFirst == IntLarger);
920 // Always true for -1 < bool and bool < 10
921 // Always false for 10 < bool and bool < -1
922 return TryResult(IntFirst != IntLarger);
926 /// Find an incorrect equality comparison. Either with an expression
927 /// evaluating to a boolean and a constant other than 0 and 1.
928 /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to
929 /// true/false e.q. (x & 8) == 4.
930 TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) {
931 const Expr *LHSExpr = B->getLHS()->IgnoreParens();
932 const Expr *RHSExpr = B->getRHS()->IgnoreParens();
934 const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
935 const Expr *BoolExpr = RHSExpr;
938 IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
945 const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(BoolExpr);
946 if (BitOp && (BitOp->getOpcode() == BO_And ||
947 BitOp->getOpcode() == BO_Or)) {
948 const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens();
949 const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens();
951 const IntegerLiteral *IntLiteral2 = dyn_cast<IntegerLiteral>(LHSExpr2);
954 IntLiteral2 = dyn_cast<IntegerLiteral>(RHSExpr2);
959 llvm::APInt L1 = IntLiteral->getValue();
960 llvm::APInt L2 = IntLiteral2->getValue();
961 if ((BitOp->getOpcode() == BO_And && (L2 & L1) != L1) ||
962 (BitOp->getOpcode() == BO_Or && (L2 | L1) != L1)) {
963 if (BuildOpts.Observer)
964 BuildOpts.Observer->compareBitwiseEquality(B,
965 B->getOpcode() != BO_EQ);
966 TryResult(B->getOpcode() != BO_EQ);
968 } else if (BoolExpr->isKnownToHaveBooleanValue()) {
969 llvm::APInt IntValue = IntLiteral->getValue();
970 if ((IntValue == 1) || (IntValue == 0)) {
973 return TryResult(B->getOpcode() != BO_EQ);
979 TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation,
980 const llvm::APSInt &Value1,
981 const llvm::APSInt &Value2) {
982 assert(Value1.isSigned() == Value2.isSigned());
987 return TryResult(Value1 == Value2);
989 return TryResult(Value1 != Value2);
991 return TryResult(Value1 < Value2);
993 return TryResult(Value1 <= Value2);
995 return TryResult(Value1 > Value2);
997 return TryResult(Value1 >= Value2);
1001 /// Find a pair of comparison expressions with or without parentheses
1002 /// with a shared variable and constants and a logical operator between them
1003 /// that always evaluates to either true or false.
1004 /// e.g. if (x != 3 || x != 4)
1005 TryResult checkIncorrectLogicOperator(const BinaryOperator *B) {
1006 assert(B->isLogicalOp());
1007 const BinaryOperator *LHS =
1008 dyn_cast<BinaryOperator>(B->getLHS()->IgnoreParens());
1009 const BinaryOperator *RHS =
1010 dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens());
1014 if (!LHS->isComparisonOp() || !RHS->isComparisonOp())
1017 const DeclRefExpr *Decl1;
1019 BinaryOperatorKind BO1;
1020 std::tie(Decl1, BO1, Expr1) = tryNormalizeBinaryOperator(LHS);
1022 if (!Decl1 || !Expr1)
1025 const DeclRefExpr *Decl2;
1027 BinaryOperatorKind BO2;
1028 std::tie(Decl2, BO2, Expr2) = tryNormalizeBinaryOperator(RHS);
1030 if (!Decl2 || !Expr2)
1033 // Check that it is the same variable on both sides.
1034 if (Decl1->getDecl() != Decl2->getDecl())
1037 // Make sure the user's intent is clear (e.g. they're comparing against two
1038 // int literals, or two things from the same enum)
1039 if (!areExprTypesCompatible(Expr1, Expr2))
1042 Expr::EvalResult L1Result, L2Result;
1043 if (!Expr1->EvaluateAsInt(L1Result, *Context) ||
1044 !Expr2->EvaluateAsInt(L2Result, *Context))
1047 llvm::APSInt L1 = L1Result.Val.getInt();
1048 llvm::APSInt L2 = L2Result.Val.getInt();
1050 // Can't compare signed with unsigned or with different bit width.
1051 if (L1.isSigned() != L2.isSigned() || L1.getBitWidth() != L2.getBitWidth())
1054 // Values that will be used to determine if result of logical
1055 // operator is always true/false
1056 const llvm::APSInt Values[] = {
1057 // Value less than both Value1 and Value2
1058 llvm::APSInt::getMinValue(L1.getBitWidth(), L1.isUnsigned()),
1061 // Value between Value1 and Value2
1062 ((L1 < L2) ? L1 : L2) + llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1),
1066 // Value greater than both Value1 and Value2
1067 llvm::APSInt::getMaxValue(L1.getBitWidth(), L1.isUnsigned()),
1070 // Check whether expression is always true/false by evaluating the following
1071 // * variable x is less than the smallest literal.
1072 // * variable x is equal to the smallest literal.
1073 // * Variable x is between smallest and largest literal.
1074 // * Variable x is equal to the largest literal.
1075 // * Variable x is greater than largest literal.
1076 bool AlwaysTrue = true, AlwaysFalse = true;
1077 for (const llvm::APSInt &Value : Values) {
1078 TryResult Res1, Res2;
1079 Res1 = analyzeLogicOperatorCondition(BO1, Value, L1);
1080 Res2 = analyzeLogicOperatorCondition(BO2, Value, L2);
1082 if (!Res1.isKnown() || !Res2.isKnown())
1085 if (B->getOpcode() == BO_LAnd) {
1086 AlwaysTrue &= (Res1.isTrue() && Res2.isTrue());
1087 AlwaysFalse &= !(Res1.isTrue() && Res2.isTrue());
1089 AlwaysTrue &= (Res1.isTrue() || Res2.isTrue());
1090 AlwaysFalse &= !(Res1.isTrue() || Res2.isTrue());
1094 if (AlwaysTrue || AlwaysFalse) {
1095 if (BuildOpts.Observer)
1096 BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue);
1097 return TryResult(AlwaysTrue);
1102 /// Try and evaluate an expression to an integer constant.
1103 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {
1104 if (!BuildOpts.PruneTriviallyFalseEdges)
1106 return !S->isTypeDependent() &&
1107 !S->isValueDependent() &&
1108 S->EvaluateAsRValue(outResult, *Context);
1111 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
1112 /// if we can evaluate to a known value, otherwise return -1.
1113 TryResult tryEvaluateBool(Expr *S) {
1114 if (!BuildOpts.PruneTriviallyFalseEdges ||
1115 S->isTypeDependent() || S->isValueDependent())
1118 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) {
1119 if (Bop->isLogicalOp()) {
1120 // Check the cache first.
1121 CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S);
1122 if (I != CachedBoolEvals.end())
1123 return I->second; // already in map;
1125 // Retrieve result at first, or the map might be updated.
1126 TryResult Result = evaluateAsBooleanConditionNoCache(S);
1127 CachedBoolEvals[S] = Result; // update or insert
1131 switch (Bop->getOpcode()) {
1133 // For 'x & 0' and 'x * 0', we can determine that
1134 // the value is always false.
1137 // If either operand is zero, we know the value
1139 Expr::EvalResult LHSResult;
1140 if (Bop->getLHS()->EvaluateAsInt(LHSResult, *Context)) {
1141 llvm::APSInt IntVal = LHSResult.Val.getInt();
1142 if (!IntVal.getBoolValue()) {
1143 return TryResult(false);
1146 Expr::EvalResult RHSResult;
1147 if (Bop->getRHS()->EvaluateAsInt(RHSResult, *Context)) {
1148 llvm::APSInt IntVal = RHSResult.Val.getInt();
1149 if (!IntVal.getBoolValue()) {
1150 return TryResult(false);
1159 return evaluateAsBooleanConditionNoCache(S);
1162 /// Evaluate as boolean \param E without using the cache.
1163 TryResult evaluateAsBooleanConditionNoCache(Expr *E) {
1164 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) {
1165 if (Bop->isLogicalOp()) {
1166 TryResult LHS = tryEvaluateBool(Bop->getLHS());
1167 if (LHS.isKnown()) {
1168 // We were able to evaluate the LHS, see if we can get away with not
1169 // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
1170 if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1171 return LHS.isTrue();
1173 TryResult RHS = tryEvaluateBool(Bop->getRHS());
1174 if (RHS.isKnown()) {
1175 if (Bop->getOpcode() == BO_LOr)
1176 return LHS.isTrue() || RHS.isTrue();
1178 return LHS.isTrue() && RHS.isTrue();
1181 TryResult RHS = tryEvaluateBool(Bop->getRHS());
1182 if (RHS.isKnown()) {
1183 // We can't evaluate the LHS; however, sometimes the result
1184 // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
1185 if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr))
1186 return RHS.isTrue();
1188 TryResult BopRes = checkIncorrectLogicOperator(Bop);
1189 if (BopRes.isKnown())
1190 return BopRes.isTrue();
1195 } else if (Bop->isEqualityOp()) {
1196 TryResult BopRes = checkIncorrectEqualityOperator(Bop);
1197 if (BopRes.isKnown())
1198 return BopRes.isTrue();
1199 } else if (Bop->isRelationalOp()) {
1200 TryResult BopRes = checkIncorrectRelationalOperator(Bop);
1201 if (BopRes.isKnown())
1202 return BopRes.isTrue();
1207 if (E->EvaluateAsBooleanCondition(Result, *Context))
1213 bool hasTrivialDestructor(VarDecl *VD);
1218 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
1219 const Stmt *stmt) const {
1220 return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
1223 bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
1224 bool shouldAdd = BuildOpts.alwaysAdd(stmt);
1226 if (!BuildOpts.forcedBlkExprs)
1229 if (lastLookup == stmt) {
1231 assert(cachedEntry->first == stmt);
1239 // Perform the lookup!
1240 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
1243 // No need to update 'cachedEntry', since it will always be null.
1244 assert(!cachedEntry);
1248 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);
1249 if (itr == fb->end()) {
1250 cachedEntry = nullptr;
1254 cachedEntry = &*itr;
1258 // FIXME: Add support for dependent-sized array types in C++?
1259 // Does it even make sense to build a CFG for an uninstantiated template?
1260 static const VariableArrayType *FindVA(const Type *t) {
1261 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {
1262 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
1263 if (vat->getSizeExpr())
1266 t = vt->getElementType().getTypePtr();
1272 void CFGBuilder::consumeConstructionContext(
1273 const ConstructionContextLayer *Layer, Expr *E) {
1274 assert((isa<CXXConstructExpr>(E) || isa<CallExpr>(E) ||
1275 isa<ObjCMessageExpr>(E)) && "Expression cannot construct an object!");
1276 if (const ConstructionContextLayer *PreviouslyStoredLayer =
1277 ConstructionContextMap.lookup(E)) {
1278 (void)PreviouslyStoredLayer;
1279 // We might have visited this child when we were finding construction
1280 // contexts within its parents.
1281 assert(PreviouslyStoredLayer->isStrictlyMoreSpecificThan(Layer) &&
1282 "Already within a different construction context!");
1284 ConstructionContextMap[E] = Layer;
1288 void CFGBuilder::findConstructionContexts(
1289 const ConstructionContextLayer *Layer, Stmt *Child) {
1290 if (!BuildOpts.AddRichCXXConstructors)
1296 auto withExtraLayer = [this, Layer](const ConstructionContextItem &Item) {
1297 return ConstructionContextLayer::create(cfg->getBumpVectorContext(), Item,
1301 switch(Child->getStmtClass()) {
1302 case Stmt::CXXConstructExprClass:
1303 case Stmt::CXXTemporaryObjectExprClass: {
1304 // Support pre-C++17 copy elision AST.
1305 auto *CE = cast<CXXConstructExpr>(Child);
1306 if (BuildOpts.MarkElidedCXXConstructors && CE->isElidable()) {
1307 findConstructionContexts(withExtraLayer(CE), CE->getArg(0));
1310 consumeConstructionContext(Layer, CE);
1313 // FIXME: This, like the main visit, doesn't support CUDAKernelCallExpr.
1314 // FIXME: An isa<> would look much better but this whole switch is a
1315 // workaround for an internal compiler error in MSVC 2015 (see r326021).
1316 case Stmt::CallExprClass:
1317 case Stmt::CXXMemberCallExprClass:
1318 case Stmt::CXXOperatorCallExprClass:
1319 case Stmt::UserDefinedLiteralClass:
1320 case Stmt::ObjCMessageExprClass: {
1321 auto *E = cast<Expr>(Child);
1322 if (CFGCXXRecordTypedCall::isCXXRecordTypedCall(E))
1323 consumeConstructionContext(Layer, E);
1326 case Stmt::ExprWithCleanupsClass: {
1327 auto *Cleanups = cast<ExprWithCleanups>(Child);
1328 findConstructionContexts(Layer, Cleanups->getSubExpr());
1331 case Stmt::CXXFunctionalCastExprClass: {
1332 auto *Cast = cast<CXXFunctionalCastExpr>(Child);
1333 findConstructionContexts(Layer, Cast->getSubExpr());
1336 case Stmt::ImplicitCastExprClass: {
1337 auto *Cast = cast<ImplicitCastExpr>(Child);
1338 // Should we support other implicit cast kinds?
1339 switch (Cast->getCastKind()) {
1341 case CK_ConstructorConversion:
1342 findConstructionContexts(Layer, Cast->getSubExpr());
1349 case Stmt::CXXBindTemporaryExprClass: {
1350 auto *BTE = cast<CXXBindTemporaryExpr>(Child);
1351 findConstructionContexts(withExtraLayer(BTE), BTE->getSubExpr());
1354 case Stmt::MaterializeTemporaryExprClass: {
1355 // Normally we don't want to search in MaterializeTemporaryExpr because
1356 // it indicates the beginning of a temporary object construction context,
1357 // so it shouldn't be found in the middle. However, if it is the beginning
1358 // of an elidable copy or move construction context, we need to include it.
1359 if (Layer->getItem().getKind() ==
1360 ConstructionContextItem::ElidableConstructorKind) {
1361 auto *MTE = cast<MaterializeTemporaryExpr>(Child);
1362 findConstructionContexts(withExtraLayer(MTE), MTE->GetTemporaryExpr());
1366 case Stmt::ConditionalOperatorClass: {
1367 auto *CO = cast<ConditionalOperator>(Child);
1368 if (Layer->getItem().getKind() !=
1369 ConstructionContextItem::MaterializationKind) {
1370 // If the object returned by the conditional operator is not going to be a
1371 // temporary object that needs to be immediately materialized, then
1372 // it must be C++17 with its mandatory copy elision. Do not yet promise
1373 // to support this case.
1374 assert(!CO->getType()->getAsCXXRecordDecl() || CO->isGLValue() ||
1375 Context->getLangOpts().CPlusPlus17);
1378 findConstructionContexts(Layer, CO->getLHS());
1379 findConstructionContexts(Layer, CO->getRHS());
1387 void CFGBuilder::cleanupConstructionContext(Expr *E) {
1388 assert(BuildOpts.AddRichCXXConstructors &&
1389 "We should not be managing construction contexts!");
1390 assert(ConstructionContextMap.count(E) &&
1391 "Cannot exit construction context without the context!");
1392 ConstructionContextMap.erase(E);
1396 /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
1397 /// arbitrary statement. Examples include a single expression or a function
1398 /// body (compound statement). The ownership of the returned CFG is
1399 /// transferred to the caller. If CFG construction fails, this method returns
1401 std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
1406 // Create an empty block that will serve as the exit block for the CFG. Since
1407 // this is the first block added to the CFG, it will be implicitly registered
1408 // as the exit block.
1409 Succ = createBlock();
1410 assert(Succ == &cfg->getExit());
1411 Block = nullptr; // the EXIT block is empty. Create all other blocks lazily.
1413 assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
1414 "AddImplicitDtors and AddLifetime cannot be used at the same time");
1416 if (BuildOpts.AddImplicitDtors)
1417 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
1418 addImplicitDtorsForDestructor(DD);
1420 // Visit the statements and create the CFG.
1421 CFGBlock *B = addStmt(Statement);
1426 // For C++ constructor add initializers to CFG.
1427 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {
1428 for (auto *I : llvm::reverse(CD->inits())) {
1429 B = addInitializer(I);
1438 // Backpatch the gotos whose label -> block mappings we didn't know when we
1439 // encountered them.
1440 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
1441 E = BackpatchBlocks.end(); I != E; ++I ) {
1443 CFGBlock *B = I->block;
1444 const GotoStmt *G = cast<GotoStmt>(B->getTerminator());
1445 LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
1447 // If there is no target for the goto, then we are looking at an
1448 // incomplete AST. Handle this by not registering a successor.
1449 if (LI == LabelMap.end()) continue;
1451 JumpTarget JT = LI->second;
1452 prependAutomaticObjLifetimeWithTerminator(B, I->scopePosition,
1454 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
1456 const VarDecl *VD = prependAutomaticObjScopeEndWithTerminator(
1457 B, I->scopePosition, JT.scopePosition);
1458 appendScopeBegin(JT.block, VD, G);
1459 addSuccessor(B, JT.block);
1462 // Add successors to the Indirect Goto Dispatch block (if we have one).
1463 if (CFGBlock *B = cfg->getIndirectGotoBlock())
1464 for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
1465 E = AddressTakenLabels.end(); I != E; ++I ) {
1466 // Lookup the target block.
1467 LabelMapTy::iterator LI = LabelMap.find(*I);
1469 // If there is no target block that contains label, then we are looking
1470 // at an incomplete AST. Handle this by not registering a successor.
1471 if (LI == LabelMap.end()) continue;
1473 addSuccessor(B, LI->second.block);
1476 // Create an empty entry block that has no predecessors.
1477 cfg->setEntry(createBlock());
1479 if (BuildOpts.AddRichCXXConstructors)
1480 assert(ConstructionContextMap.empty() &&
1481 "Not all construction contexts were cleaned up!");
1483 return std::move(cfg);
1486 /// createBlock - Used to lazily create blocks that are connected
1487 /// to the current (global) succcessor.
1488 CFGBlock *CFGBuilder::createBlock(bool add_successor) {
1489 CFGBlock *B = cfg->createBlock();
1490 if (add_successor && Succ)
1491 addSuccessor(B, Succ);
1495 /// createNoReturnBlock - Used to create a block is a 'noreturn' point in the
1496 /// CFG. It is *not* connected to the current (global) successor, and instead
1497 /// directly tied to the exit block in order to be reachable.
1498 CFGBlock *CFGBuilder::createNoReturnBlock() {
1499 CFGBlock *B = createBlock(false);
1500 B->setHasNoReturnElement();
1501 addSuccessor(B, &cfg->getExit(), Succ);
1505 /// addInitializer - Add C++ base or member initializer element to CFG.
1506 CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
1507 if (!BuildOpts.AddInitializers)
1510 bool HasTemporaries = false;
1512 // Destructors of temporaries in initialization expression should be called
1513 // after initialization finishes.
1514 Expr *Init = I->getInit();
1516 HasTemporaries = isa<ExprWithCleanups>(Init);
1518 if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
1519 // Generate destructors for temporaries in initialization expression.
1520 TempDtorContext Context;
1521 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
1522 /*BindToTemporary=*/false, Context);
1527 appendInitializer(Block, I);
1530 findConstructionContexts(
1531 ConstructionContextLayer::create(cfg->getBumpVectorContext(), I),
1534 if (HasTemporaries) {
1535 // For expression with temporaries go directly to subexpression to omit
1536 // generating destructors for the second time.
1537 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
1539 if (BuildOpts.AddCXXDefaultInitExprInCtors) {
1540 if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) {
1541 // In general, appending the expression wrapped by a CXXDefaultInitExpr
1542 // may cause the same Expr to appear more than once in the CFG. Doing it
1543 // here is safe because there's only one initializer per field.
1545 appendStmt(Block, Default);
1546 if (Stmt *Child = Default->getExpr())
1547 if (CFGBlock *R = Visit(Child))
1558 /// Retrieve the type of the temporary object whose lifetime was
1559 /// extended by a local reference with the given initializer.
1560 static QualType getReferenceInitTemporaryType(const Expr *Init,
1561 bool *FoundMTE = nullptr) {
1563 // Skip parentheses.
1564 Init = Init->IgnoreParens();
1566 // Skip through cleanups.
1567 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) {
1568 Init = EWC->getSubExpr();
1572 // Skip through the temporary-materialization expression.
1573 if (const MaterializeTemporaryExpr *MTE
1574 = dyn_cast<MaterializeTemporaryExpr>(Init)) {
1575 Init = MTE->GetTemporaryExpr();
1581 // Skip sub-object accesses into rvalues.
1582 SmallVector<const Expr *, 2> CommaLHSs;
1583 SmallVector<SubobjectAdjustment, 2> Adjustments;
1584 const Expr *SkippedInit =
1585 Init->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments);
1586 if (SkippedInit != Init) {
1594 return Init->getType();
1597 // TODO: Support adding LoopExit element to the CFG in case where the loop is
1598 // ended by ReturnStmt, GotoStmt or ThrowExpr.
1599 void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
1600 if(!BuildOpts.AddLoopExit)
1603 appendLoopExit(Block, LoopStmt);
1606 void CFGBuilder::getDeclsWithEndedScope(LocalScope::const_iterator B,
1607 LocalScope::const_iterator E, Stmt *S) {
1608 if (!BuildOpts.AddScopes)
1614 // To go from B to E, one first goes up the scopes from B to P
1615 // then sideways in one scope from P to P' and then down
1616 // the scopes from P' to E.
1617 // The lifetime of all objects between B and P end.
1618 LocalScope::const_iterator P = B.shared_parent(E);
1619 int Dist = B.distance(P);
1623 for (LocalScope::const_iterator I = B; I != P; ++I)
1624 if (I.pointsToFirstDeclaredVar())
1625 DeclsWithEndedScope.insert(*I);
1628 void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
1629 LocalScope::const_iterator E,
1631 getDeclsWithEndedScope(B, E, S);
1632 if (BuildOpts.AddScopes)
1633 addScopesEnd(B, E, S);
1634 if (BuildOpts.AddImplicitDtors)
1635 addAutomaticObjDtors(B, E, S);
1636 if (BuildOpts.AddLifetime)
1637 addLifetimeEnds(B, E, S);
1640 /// Add to current block automatic objects that leave the scope.
1641 void CFGBuilder::addLifetimeEnds(LocalScope::const_iterator B,
1642 LocalScope::const_iterator E, Stmt *S) {
1643 if (!BuildOpts.AddLifetime)
1649 // To go from B to E, one first goes up the scopes from B to P
1650 // then sideways in one scope from P to P' and then down
1651 // the scopes from P' to E.
1652 // The lifetime of all objects between B and P end.
1653 LocalScope::const_iterator P = B.shared_parent(E);
1654 int dist = B.distance(P);
1658 // We need to perform the scope leaving in reverse order
1659 SmallVector<VarDecl *, 10> DeclsTrivial;
1660 SmallVector<VarDecl *, 10> DeclsNonTrivial;
1661 DeclsTrivial.reserve(dist);
1662 DeclsNonTrivial.reserve(dist);
1664 for (LocalScope::const_iterator I = B; I != P; ++I)
1665 if (hasTrivialDestructor(*I))
1666 DeclsTrivial.push_back(*I);
1668 DeclsNonTrivial.push_back(*I);
1671 // object with trivial destructor end their lifetime last (when storage
1673 for (SmallVectorImpl<VarDecl *>::reverse_iterator I = DeclsTrivial.rbegin(),
1674 E = DeclsTrivial.rend();
1676 appendLifetimeEnds(Block, *I, S);
1678 for (SmallVectorImpl<VarDecl *>::reverse_iterator
1679 I = DeclsNonTrivial.rbegin(),
1680 E = DeclsNonTrivial.rend();
1682 appendLifetimeEnds(Block, *I, S);
1685 /// Add to current block markers for ending scopes.
1686 void CFGBuilder::addScopesEnd(LocalScope::const_iterator B,
1687 LocalScope::const_iterator E, Stmt *S) {
1688 // If implicit destructors are enabled, we'll add scope ends in
1689 // addAutomaticObjDtors.
1690 if (BuildOpts.AddImplicitDtors)
1695 for (auto I = DeclsWithEndedScope.rbegin(), E = DeclsWithEndedScope.rend();
1697 appendScopeEnd(Block, *I, S);
1702 /// addAutomaticObjDtors - Add to current block automatic objects destructors
1703 /// for objects in range of local scope positions. Use S as trigger statement
1704 /// for destructors.
1705 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
1706 LocalScope::const_iterator E, Stmt *S) {
1707 if (!BuildOpts.AddImplicitDtors)
1713 // We need to append the destructors in reverse order, but any one of them
1714 // may be a no-return destructor which changes the CFG. As a result, buffer
1715 // this sequence up and replay them in reverse order when appending onto the
1717 SmallVector<VarDecl*, 10> Decls;
1718 Decls.reserve(B.distance(E));
1719 for (LocalScope::const_iterator I = B; I != E; ++I)
1720 Decls.push_back(*I);
1722 for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(),
1725 if (hasTrivialDestructor(*I)) {
1726 // If AddScopes is enabled and *I is a first variable in a scope, add a
1727 // ScopeEnd marker in a Block.
1728 if (BuildOpts.AddScopes && DeclsWithEndedScope.count(*I)) {
1730 appendScopeEnd(Block, *I, S);
1734 // If this destructor is marked as a no-return destructor, we need to
1735 // create a new block for the destructor which does not have as a successor
1736 // anything built thus far: control won't flow out of this block.
1737 QualType Ty = (*I)->getType();
1738 if (Ty->isReferenceType()) {
1739 Ty = getReferenceInitTemporaryType((*I)->getInit());
1741 Ty = Context->getBaseElementType(Ty);
1743 if (Ty->getAsCXXRecordDecl()->isAnyDestructorNoReturn())
1744 Block = createNoReturnBlock();
1748 // Add ScopeEnd just after automatic obj destructor.
1749 if (BuildOpts.AddScopes && DeclsWithEndedScope.count(*I))
1750 appendScopeEnd(Block, *I, S);
1751 appendAutomaticObjDtor(Block, *I, S);
1755 /// addImplicitDtorsForDestructor - Add implicit destructors generated for
1756 /// base and member objects in destructor.
1757 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
1758 assert(BuildOpts.AddImplicitDtors &&
1759 "Can be called only when dtors should be added");
1760 const CXXRecordDecl *RD = DD->getParent();
1762 // At the end destroy virtual base objects.
1763 for (const auto &VI : RD->vbases()) {
1764 const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl();
1765 if (!CD->hasTrivialDestructor()) {
1767 appendBaseDtor(Block, &VI);
1771 // Before virtual bases destroy direct base objects.
1772 for (const auto &BI : RD->bases()) {
1773 if (!BI.isVirtual()) {
1774 const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl();
1775 if (!CD->hasTrivialDestructor()) {
1777 appendBaseDtor(Block, &BI);
1782 // First destroy member objects.
1783 for (auto *FI : RD->fields()) {
1784 // Check for constant size array. Set type to array element type.
1785 QualType QT = FI->getType();
1786 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
1787 if (AT->getSize() == 0)
1789 QT = AT->getElementType();
1792 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
1793 if (!CD->hasTrivialDestructor()) {
1795 appendMemberDtor(Block, FI);
1800 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
1801 /// way return valid LocalScope object.
1802 LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
1805 llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
1806 return new (alloc.Allocate<LocalScope>())
1807 LocalScope(BumpVectorContext(alloc), ScopePos);
1810 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
1811 /// that should create implicit scope (e.g. if/else substatements).
1812 void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
1813 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
1814 !BuildOpts.AddScopes)
1817 LocalScope *Scope = nullptr;
1819 // For compound statement we will be creating explicit scope.
1820 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {
1821 for (auto *BI : CS->body()) {
1822 Stmt *SI = BI->stripLabelLikeStatements();
1823 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))
1824 Scope = addLocalScopeForDeclStmt(DS, Scope);
1829 // For any other statement scope will be implicit and as such will be
1830 // interesting only for DeclStmt.
1831 if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements()))
1832 addLocalScopeForDeclStmt(DS);
1835 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
1836 /// reuse Scope if not NULL.
1837 LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
1838 LocalScope* Scope) {
1839 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
1840 !BuildOpts.AddScopes)
1843 for (auto *DI : DS->decls())
1844 if (VarDecl *VD = dyn_cast<VarDecl>(DI))
1845 Scope = addLocalScopeForVarDecl(VD, Scope);
1849 bool CFGBuilder::hasTrivialDestructor(VarDecl *VD) {
1850 // Check for const references bound to temporary. Set type to pointee.
1851 QualType QT = VD->getType();
1852 if (QT->isReferenceType()) {
1853 // Attempt to determine whether this declaration lifetime-extends a
1856 // FIXME: This is incorrect. Non-reference declarations can lifetime-extend
1857 // temporaries, and a single declaration can extend multiple temporaries.
1858 // We should look at the storage duration on each nested
1859 // MaterializeTemporaryExpr instead.
1861 const Expr *Init = VD->getInit();
1863 // Probably an exception catch-by-reference variable.
1864 // FIXME: It doesn't really mean that the object has a trivial destructor.
1865 // Also are there other cases?
1869 // Lifetime-extending a temporary?
1870 bool FoundMTE = false;
1871 QT = getReferenceInitTemporaryType(Init, &FoundMTE);
1876 // Check for constant size array. Set type to array element type.
1877 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
1878 if (AT->getSize() == 0)
1880 QT = AT->getElementType();
1883 // Check if type is a C++ class with non-trivial destructor.
1884 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
1885 return !CD->hasDefinition() || CD->hasTrivialDestructor();
1889 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
1890 /// create add scope for automatic objects and temporary objects bound to
1891 /// const reference. Will reuse Scope if not NULL.
1892 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
1893 LocalScope* Scope) {
1894 assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) &&
1895 "AddImplicitDtors and AddLifetime cannot be used at the same time");
1896 if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&
1897 !BuildOpts.AddScopes)
1900 // Check if variable is local.
1901 switch (VD->getStorageClass()) {
1906 default: return Scope;
1909 if (BuildOpts.AddImplicitDtors) {
1910 if (!hasTrivialDestructor(VD) || BuildOpts.AddScopes) {
1911 // Add the variable to scope
1912 Scope = createOrReuseLocalScope(Scope);
1914 ScopePos = Scope->begin();
1919 assert(BuildOpts.AddLifetime);
1920 // Add the variable to scope
1921 Scope = createOrReuseLocalScope(Scope);
1923 ScopePos = Scope->begin();
1927 /// addLocalScopeAndDtors - For given statement add local scope for it and
1928 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
1929 void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
1930 LocalScope::const_iterator scopeBeginPos = ScopePos;
1931 addLocalScopeForStmt(S);
1932 addAutomaticObjHandling(ScopePos, scopeBeginPos, S);
1935 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
1936 /// variables with automatic storage duration to CFGBlock's elements vector.
1937 /// Elements will be prepended to physical beginning of the vector which
1938 /// happens to be logical end. Use blocks terminator as statement that specifies
1939 /// destructors call site.
1940 /// FIXME: This mechanism for adding automatic destructors doesn't handle
1941 /// no-return destructors properly.
1942 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
1943 LocalScope::const_iterator B, LocalScope::const_iterator E) {
1944 if (!BuildOpts.AddImplicitDtors)
1946 BumpVectorContext &C = cfg->getBumpVectorContext();
1947 CFGBlock::iterator InsertPos
1948 = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
1949 for (LocalScope::const_iterator I = B; I != E; ++I)
1950 InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I,
1951 Blk->getTerminator());
1954 /// prependAutomaticObjLifetimeWithTerminator - Prepend lifetime CFGElements for
1955 /// variables with automatic storage duration to CFGBlock's elements vector.
1956 /// Elements will be prepended to physical beginning of the vector which
1957 /// happens to be logical end. Use blocks terminator as statement that specifies
1958 /// where lifetime ends.
1959 void CFGBuilder::prependAutomaticObjLifetimeWithTerminator(
1960 CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
1961 if (!BuildOpts.AddLifetime)
1963 BumpVectorContext &C = cfg->getBumpVectorContext();
1964 CFGBlock::iterator InsertPos =
1965 Blk->beginLifetimeEndsInsert(Blk->end(), B.distance(E), C);
1966 for (LocalScope::const_iterator I = B; I != E; ++I)
1967 InsertPos = Blk->insertLifetimeEnds(InsertPos, *I, Blk->getTerminator());
1970 /// prependAutomaticObjScopeEndWithTerminator - Prepend scope end CFGElements for
1971 /// variables with automatic storage duration to CFGBlock's elements vector.
1972 /// Elements will be prepended to physical beginning of the vector which
1973 /// happens to be logical end. Use blocks terminator as statement that specifies
1974 /// where scope ends.
1976 CFGBuilder::prependAutomaticObjScopeEndWithTerminator(
1977 CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) {
1978 if (!BuildOpts.AddScopes)
1980 BumpVectorContext &C = cfg->getBumpVectorContext();
1981 CFGBlock::iterator InsertPos =
1982 Blk->beginScopeEndInsert(Blk->end(), 1, C);
1983 LocalScope::const_iterator PlaceToInsert = B;
1984 for (LocalScope::const_iterator I = B; I != E; ++I)
1986 Blk->insertScopeEnd(InsertPos, *PlaceToInsert, Blk->getTerminator());
1987 return *PlaceToInsert;
1990 /// Visit - Walk the subtree of a statement and add extra
1991 /// blocks for ternary operators, &&, and ||. We also process "," and
1992 /// DeclStmts (which may contain nested control-flow).
1993 CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) {
1999 if (Expr *E = dyn_cast<Expr>(S))
2000 S = E->IgnoreParens();
2002 switch (S->getStmtClass()) {
2004 return VisitStmt(S, asc);
2006 case Stmt::AddrLabelExprClass:
2007 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
2009 case Stmt::BinaryConditionalOperatorClass:
2010 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
2012 case Stmt::BinaryOperatorClass:
2013 return VisitBinaryOperator(cast<BinaryOperator>(S), asc);
2015 case Stmt::BlockExprClass:
2016 return VisitBlockExpr(cast<BlockExpr>(S), asc);
2018 case Stmt::BreakStmtClass:
2019 return VisitBreakStmt(cast<BreakStmt>(S));
2021 case Stmt::CallExprClass:
2022 case Stmt::CXXOperatorCallExprClass:
2023 case Stmt::CXXMemberCallExprClass:
2024 case Stmt::UserDefinedLiteralClass:
2025 return VisitCallExpr(cast<CallExpr>(S), asc);
2027 case Stmt::CaseStmtClass:
2028 return VisitCaseStmt(cast<CaseStmt>(S));
2030 case Stmt::ChooseExprClass:
2031 return VisitChooseExpr(cast<ChooseExpr>(S), asc);
2033 case Stmt::CompoundStmtClass:
2034 return VisitCompoundStmt(cast<CompoundStmt>(S));
2036 case Stmt::ConditionalOperatorClass:
2037 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);
2039 case Stmt::ContinueStmtClass:
2040 return VisitContinueStmt(cast<ContinueStmt>(S));
2042 case Stmt::CXXCatchStmtClass:
2043 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));
2045 case Stmt::ExprWithCleanupsClass:
2046 return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc);
2048 case Stmt::CXXDefaultArgExprClass:
2049 case Stmt::CXXDefaultInitExprClass:
2050 // FIXME: The expression inside a CXXDefaultArgExpr is owned by the
2051 // called function's declaration, not by the caller. If we simply add
2052 // this expression to the CFG, we could end up with the same Expr
2053 // appearing multiple times.
2054 // PR13385 / <rdar://problem/12156507>
2056 // It's likewise possible for multiple CXXDefaultInitExprs for the same
2057 // expression to be used in the same function (through aggregate
2059 return VisitStmt(S, asc);
2061 case Stmt::CXXBindTemporaryExprClass:
2062 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);
2064 case Stmt::CXXConstructExprClass:
2065 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
2067 case Stmt::CXXNewExprClass:
2068 return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc);
2070 case Stmt::CXXDeleteExprClass:
2071 return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc);
2073 case Stmt::CXXFunctionalCastExprClass:
2074 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);
2076 case Stmt::CXXTemporaryObjectExprClass:
2077 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);
2079 case Stmt::CXXThrowExprClass:
2080 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));
2082 case Stmt::CXXTryStmtClass:
2083 return VisitCXXTryStmt(cast<CXXTryStmt>(S));
2085 case Stmt::CXXForRangeStmtClass:
2086 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));
2088 case Stmt::DeclStmtClass:
2089 return VisitDeclStmt(cast<DeclStmt>(S));
2091 case Stmt::DefaultStmtClass:
2092 return VisitDefaultStmt(cast<DefaultStmt>(S));
2094 case Stmt::DoStmtClass:
2095 return VisitDoStmt(cast<DoStmt>(S));
2097 case Stmt::ForStmtClass:
2098 return VisitForStmt(cast<ForStmt>(S));
2100 case Stmt::GotoStmtClass:
2101 return VisitGotoStmt(cast<GotoStmt>(S));
2103 case Stmt::IfStmtClass:
2104 return VisitIfStmt(cast<IfStmt>(S));
2106 case Stmt::ImplicitCastExprClass:
2107 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);
2109 case Stmt::ConstantExprClass:
2110 return VisitConstantExpr(cast<ConstantExpr>(S), asc);
2112 case Stmt::IndirectGotoStmtClass:
2113 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));
2115 case Stmt::LabelStmtClass:
2116 return VisitLabelStmt(cast<LabelStmt>(S));
2118 case Stmt::LambdaExprClass:
2119 return VisitLambdaExpr(cast<LambdaExpr>(S), asc);
2121 case Stmt::MaterializeTemporaryExprClass:
2122 return VisitMaterializeTemporaryExpr(cast<MaterializeTemporaryExpr>(S),
2125 case Stmt::MemberExprClass:
2126 return VisitMemberExpr(cast<MemberExpr>(S), asc);
2128 case Stmt::NullStmtClass:
2131 case Stmt::ObjCAtCatchStmtClass:
2132 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));
2134 case Stmt::ObjCAutoreleasePoolStmtClass:
2135 return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S));
2137 case Stmt::ObjCAtSynchronizedStmtClass:
2138 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));
2140 case Stmt::ObjCAtThrowStmtClass:
2141 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));
2143 case Stmt::ObjCAtTryStmtClass:
2144 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));
2146 case Stmt::ObjCForCollectionStmtClass:
2147 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));
2149 case Stmt::ObjCMessageExprClass:
2150 return VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), asc);
2152 case Stmt::OpaqueValueExprClass:
2155 case Stmt::PseudoObjectExprClass:
2156 return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S));
2158 case Stmt::ReturnStmtClass:
2159 case Stmt::CoreturnStmtClass:
2160 return VisitReturnStmt(S);
2162 case Stmt::SEHExceptStmtClass:
2163 return VisitSEHExceptStmt(cast<SEHExceptStmt>(S));
2165 case Stmt::SEHFinallyStmtClass:
2166 return VisitSEHFinallyStmt(cast<SEHFinallyStmt>(S));
2168 case Stmt::SEHLeaveStmtClass:
2169 return VisitSEHLeaveStmt(cast<SEHLeaveStmt>(S));
2171 case Stmt::SEHTryStmtClass:
2172 return VisitSEHTryStmt(cast<SEHTryStmt>(S));
2174 case Stmt::UnaryExprOrTypeTraitExprClass:
2175 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
2178 case Stmt::StmtExprClass:
2179 return VisitStmtExpr(cast<StmtExpr>(S), asc);
2181 case Stmt::SwitchStmtClass:
2182 return VisitSwitchStmt(cast<SwitchStmt>(S));
2184 case Stmt::UnaryOperatorClass:
2185 return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
2187 case Stmt::WhileStmtClass:
2188 return VisitWhileStmt(cast<WhileStmt>(S));
2192 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
2193 if (asc.alwaysAdd(*this, S)) {
2195 appendStmt(Block, S);
2198 return VisitChildren(S);
2201 /// VisitChildren - Visit the children of a Stmt.
2202 CFGBlock *CFGBuilder::VisitChildren(Stmt *S) {
2203 CFGBlock *B = Block;
2205 // Visit the children in their reverse order so that they appear in
2206 // left-to-right (natural) order in the CFG.
2207 reverse_children RChildren(S);
2208 for (reverse_children::iterator I = RChildren.begin(), E = RChildren.end();
2210 if (Stmt *Child = *I)
2211 if (CFGBlock *R = Visit(Child))
2217 CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
2218 AddStmtChoice asc) {
2219 AddressTakenLabels.insert(A->getLabel());
2221 if (asc.alwaysAdd(*this, A)) {
2223 appendStmt(Block, A);
2229 CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U,
2230 AddStmtChoice asc) {
2231 if (asc.alwaysAdd(*this, U)) {
2233 appendStmt(Block, U);
2236 return Visit(U->getSubExpr(), AddStmtChoice());
2239 CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) {
2240 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2241 appendStmt(ConfluenceBlock, B);
2246 return VisitLogicalOperator(B, nullptr, ConfluenceBlock,
2247 ConfluenceBlock).first;
2250 std::pair<CFGBlock*, CFGBlock*>
2251 CFGBuilder::VisitLogicalOperator(BinaryOperator *B,
2253 CFGBlock *TrueBlock,
2254 CFGBlock *FalseBlock) {
2255 // Introspect the RHS. If it is a nested logical operation, we recursively
2256 // build the CFG using this function. Otherwise, resort to default
2257 // CFG construction behavior.
2258 Expr *RHS = B->getRHS()->IgnoreParens();
2259 CFGBlock *RHSBlock, *ExitBlock;
2262 if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(RHS))
2263 if (B_RHS->isLogicalOp()) {
2264 std::tie(RHSBlock, ExitBlock) =
2265 VisitLogicalOperator(B_RHS, Term, TrueBlock, FalseBlock);
2269 // The RHS is not a nested logical operation. Don't push the terminator
2270 // down further, but instead visit RHS and construct the respective
2271 // pieces of the CFG, and link up the RHSBlock with the terminator
2272 // we have been provided.
2273 ExitBlock = RHSBlock = createBlock(false);
2275 // Even though KnownVal is only used in the else branch of the next
2276 // conditional, tryEvaluateBool performs additional checking on the
2277 // Expr, so it should be called unconditionally.
2278 TryResult KnownVal = tryEvaluateBool(RHS);
2279 if (!KnownVal.isKnown())
2280 KnownVal = tryEvaluateBool(B);
2283 assert(TrueBlock == FalseBlock);
2284 addSuccessor(RHSBlock, TrueBlock);
2287 RHSBlock->setTerminator(Term);
2288 addSuccessor(RHSBlock, TrueBlock, !KnownVal.isFalse());
2289 addSuccessor(RHSBlock, FalseBlock, !KnownVal.isTrue());
2293 RHSBlock = addStmt(RHS);
2298 return std::make_pair(nullptr, nullptr);
2300 // Generate the blocks for evaluating the LHS.
2301 Expr *LHS = B->getLHS()->IgnoreParens();
2303 if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(LHS))
2304 if (B_LHS->isLogicalOp()) {
2305 if (B->getOpcode() == BO_LOr)
2306 FalseBlock = RHSBlock;
2308 TrueBlock = RHSBlock;
2310 // For the LHS, treat 'B' as the terminator that we want to sink
2311 // into the nested branch. The RHS always gets the top-most
2313 return VisitLogicalOperator(B_LHS, B, TrueBlock, FalseBlock);
2316 // Create the block evaluating the LHS.
2317 // This contains the '&&' or '||' as the terminator.
2318 CFGBlock *LHSBlock = createBlock(false);
2319 LHSBlock->setTerminator(B);
2322 CFGBlock *EntryLHSBlock = addStmt(LHS);
2325 return std::make_pair(nullptr, nullptr);
2327 // See if this is a known constant.
2328 TryResult KnownVal = tryEvaluateBool(LHS);
2330 // Now link the LHSBlock with RHSBlock.
2331 if (B->getOpcode() == BO_LOr) {
2332 addSuccessor(LHSBlock, TrueBlock, !KnownVal.isFalse());
2333 addSuccessor(LHSBlock, RHSBlock, !KnownVal.isTrue());
2335 assert(B->getOpcode() == BO_LAnd);
2336 addSuccessor(LHSBlock, RHSBlock, !KnownVal.isFalse());
2337 addSuccessor(LHSBlock, FalseBlock, !KnownVal.isTrue());
2340 return std::make_pair(EntryLHSBlock, ExitBlock);
2343 CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
2344 AddStmtChoice asc) {
2346 if (B->isLogicalOp())
2347 return VisitLogicalOperator(B);
2349 if (B->getOpcode() == BO_Comma) { // ,
2351 appendStmt(Block, B);
2352 addStmt(B->getRHS());
2353 return addStmt(B->getLHS());
2356 if (B->isAssignmentOp()) {
2357 if (asc.alwaysAdd(*this, B)) {
2359 appendStmt(Block, B);
2362 return Visit(B->getRHS());
2365 if (asc.alwaysAdd(*this, B)) {
2367 appendStmt(Block, B);
2370 CFGBlock *RBlock = Visit(B->getRHS());
2371 CFGBlock *LBlock = Visit(B->getLHS());
2372 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
2373 // containing a DoStmt, and the LHS doesn't create a new block, then we should
2374 // return RBlock. Otherwise we'll incorrectly return NULL.
2375 return (LBlock ? LBlock : RBlock);
2378 CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) {
2379 if (asc.alwaysAdd(*this, E)) {
2381 appendStmt(Block, E);
2386 CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
2387 // "break" is a control-flow statement. Thus we stop processing the current
2392 // Now create a new block that ends with the break statement.
2393 Block = createBlock(false);
2394 Block->setTerminator(B);
2396 // If there is no target for the break, then we are looking at an incomplete
2397 // AST. This means that the CFG cannot be constructed.
2398 if (BreakJumpTarget.block) {
2399 addAutomaticObjHandling(ScopePos, BreakJumpTarget.scopePosition, B);
2400 addSuccessor(Block, BreakJumpTarget.block);
2407 static bool CanThrow(Expr *E, ASTContext &Ctx) {
2408 QualType Ty = E->getType();
2409 if (Ty->isFunctionPointerType())
2410 Ty = Ty->getAs<PointerType>()->getPointeeType();
2411 else if (Ty->isBlockPointerType())
2412 Ty = Ty->getAs<BlockPointerType>()->getPointeeType();
2414 const FunctionType *FT = Ty->getAs<FunctionType>();
2416 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
2417 if (!isUnresolvedExceptionSpec(Proto->getExceptionSpecType()) &&
2424 CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
2425 // Compute the callee type.
2426 QualType calleeType = C->getCallee()->getType();
2427 if (calleeType == Context->BoundMemberTy) {
2428 QualType boundType = Expr::findBoundMemberType(C->getCallee());
2430 // We should only get a null bound type if processing a dependent
2431 // CFG. Recover by assuming nothing.
2432 if (!boundType.isNull()) calleeType = boundType;
2435 // If this is a call to a no-return function, this stops the block here.
2436 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();
2438 bool AddEHEdge = false;
2440 // Languages without exceptions are assumed to not throw.
2441 if (Context->getLangOpts().Exceptions) {
2442 if (BuildOpts.AddEHEdges)
2446 // If this is a call to a builtin function, it might not actually evaluate
2447 // its arguments. Don't add them to the CFG if this is the case.
2448 bool OmitArguments = false;
2450 if (FunctionDecl *FD = C->getDirectCallee()) {
2451 // TODO: Support construction contexts for variadic function arguments.
2452 // These are a bit problematic and not very useful because passing
2453 // C++ objects as C-style variadic arguments doesn't work in general
2454 // (see [expr.call]).
2455 if (!FD->isVariadic())
2456 findConstructionContextsForArguments(C);
2458 if (FD->isNoReturn() || C->isBuiltinAssumeFalse(*Context))
2460 if (FD->hasAttr<NoThrowAttr>())
2462 if (FD->getBuiltinID() == Builtin::BI__builtin_object_size)
2463 OmitArguments = true;
2466 if (!CanThrow(C->getCallee(), *Context))
2469 if (OmitArguments) {
2470 assert(!NoReturn && "noreturn calls with unevaluated args not implemented");
2471 assert(!AddEHEdge && "EH calls with unevaluated args not implemented");
2473 appendStmt(Block, C);
2474 return Visit(C->getCallee());
2477 if (!NoReturn && !AddEHEdge) {
2479 appendCall(Block, C);
2481 return VisitChildren(C);
2491 Block = createNoReturnBlock();
2493 Block = createBlock();
2495 appendCall(Block, C);
2498 // Add exceptional edges.
2499 if (TryTerminatedBlock)
2500 addSuccessor(Block, TryTerminatedBlock);
2502 addSuccessor(Block, &cfg->getExit());
2505 return VisitChildren(C);
2508 CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
2509 AddStmtChoice asc) {
2510 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2511 appendStmt(ConfluenceBlock, C);
2515 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
2516 Succ = ConfluenceBlock;
2518 CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd);
2522 Succ = ConfluenceBlock;
2524 CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd);
2528 Block = createBlock(false);
2529 // See if this is a known constant.
2530 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
2531 addSuccessor(Block, KnownVal.isFalse() ? nullptr : LHSBlock);
2532 addSuccessor(Block, KnownVal.isTrue() ? nullptr : RHSBlock);
2533 Block->setTerminator(C);
2534 return addStmt(C->getCond());
2537 CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) {
2538 LocalScope::const_iterator scopeBeginPos = ScopePos;
2539 addLocalScopeForStmt(C);
2541 if (!C->body_empty() && !isa<ReturnStmt>(*C->body_rbegin())) {
2542 // If the body ends with a ReturnStmt, the dtors will be added in
2544 addAutomaticObjHandling(ScopePos, scopeBeginPos, C);
2547 CFGBlock *LastBlock = Block;
2549 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
2551 // If we hit a segment of code just containing ';' (NullStmts), we can
2552 // get a null block back. In such cases, just use the LastBlock
2553 if (CFGBlock *newBlock = addStmt(*I))
2554 LastBlock = newBlock;
2563 CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
2564 AddStmtChoice asc) {
2565 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);
2566 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr);
2568 // Create the confluence block that will "merge" the results of the ternary
2570 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
2571 appendStmt(ConfluenceBlock, C);
2575 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
2577 // Create a block for the LHS expression if there is an LHS expression. A
2578 // GCC extension allows LHS to be NULL, causing the condition to be the
2579 // value that is returned instead.
2580 // e.g: x ?: y is shorthand for: x ? x : y;
2581 Succ = ConfluenceBlock;
2583 CFGBlock *LHSBlock = nullptr;
2584 const Expr *trueExpr = C->getTrueExpr();
2585 if (trueExpr != opaqueValue) {
2586 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);
2592 LHSBlock = ConfluenceBlock;
2594 // Create the block for the RHS expression.
2595 Succ = ConfluenceBlock;
2596 CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);
2600 // If the condition is a logical '&&' or '||', build a more accurate CFG.
2601 if (BinaryOperator *Cond =
2602 dyn_cast<BinaryOperator>(C->getCond()->IgnoreParens()))
2603 if (Cond->isLogicalOp())
2604 return VisitLogicalOperator(Cond, C, LHSBlock, RHSBlock).first;
2606 // Create the block that will contain the condition.
2607 Block = createBlock(false);
2609 // See if this is a known constant.
2610 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
2611 addSuccessor(Block, LHSBlock, !KnownVal.isFalse());
2612 addSuccessor(Block, RHSBlock, !KnownVal.isTrue());
2613 Block->setTerminator(C);
2614 Expr *condExpr = C->getCond();
2617 // Run the condition expression if it's not trivially expressed in
2618 // terms of the opaque value (or if there is no opaque value).
2619 if (condExpr != opaqueValue)
2622 // Before that, run the common subexpression if there was one.
2623 // At least one of this or the above will be run.
2624 return addStmt(BCO->getCommon());
2627 return addStmt(condExpr);
2630 CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
2631 // Check if the Decl is for an __label__. If so, elide it from the
2633 if (isa<LabelDecl>(*DS->decl_begin()))
2636 // This case also handles static_asserts.
2637 if (DS->isSingleDecl())
2638 return VisitDeclSubExpr(DS);
2640 CFGBlock *B = nullptr;
2642 // Build an individual DeclStmt for each decl.
2643 for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(),
2644 E = DS->decl_rend();
2647 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
2648 // automatically freed with the CFG.
2649 DeclGroupRef DG(*I);
2651 DeclStmt *DSNew = new (Context) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
2652 cfg->addSyntheticDeclStmt(DSNew, DS);
2654 // Append the fake DeclStmt to block.
2655 B = VisitDeclSubExpr(DSNew);
2661 /// VisitDeclSubExpr - Utility method to add block-level expressions for
2662 /// DeclStmts and initializers in them.
2663 CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
2664 assert(DS->isSingleDecl() && "Can handle single declarations only.");
2665 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
2668 // Of everything that can be declared in a DeclStmt, only VarDecls impact
2669 // runtime semantics.
2673 bool HasTemporaries = false;
2675 // Guard static initializers under a branch.
2676 CFGBlock *blockAfterStaticInit = nullptr;
2678 if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) {
2679 // For static variables, we need to create a branch to track
2680 // whether or not they are initialized.
2687 blockAfterStaticInit = Succ;
2690 // Destructors of temporaries in initialization expression should be called
2691 // after initialization finishes.
2692 Expr *Init = VD->getInit();
2694 HasTemporaries = isa<ExprWithCleanups>(Init);
2696 if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
2697 // Generate destructors for temporaries in initialization expression.
2698 TempDtorContext Context;
2699 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
2700 /*BindToTemporary=*/false, Context);
2705 appendStmt(Block, DS);
2707 findConstructionContexts(
2708 ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),
2711 // Keep track of the last non-null block, as 'Block' can be nulled out
2712 // if the initializer expression is something like a 'while' in a
2713 // statement-expression.
2714 CFGBlock *LastBlock = Block;
2717 if (HasTemporaries) {
2718 // For expression with temporaries go directly to subexpression to omit
2719 // generating destructors for the second time.
2720 ExprWithCleanups *EC = cast<ExprWithCleanups>(Init);
2721 if (CFGBlock *newBlock = Visit(EC->getSubExpr()))
2722 LastBlock = newBlock;
2725 if (CFGBlock *newBlock = Visit(Init))
2726 LastBlock = newBlock;
2730 // If the type of VD is a VLA, then we must process its size expressions.
2731 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());
2732 VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr())) {
2733 if (CFGBlock *newBlock = addStmt(VA->getSizeExpr()))
2734 LastBlock = newBlock;
2737 maybeAddScopeBeginForVarDecl(Block, VD, DS);
2739 // Remove variable from local scope.
2740 if (ScopePos && VD == *ScopePos)
2743 CFGBlock *B = LastBlock;
2744 if (blockAfterStaticInit) {
2746 Block = createBlock(false);
2747 Block->setTerminator(DS);
2748 addSuccessor(Block, blockAfterStaticInit);
2749 addSuccessor(Block, B);
2756 CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
2757 // We may see an if statement in the middle of a basic block, or it may be the
2758 // first statement we are processing. In either case, we create a new basic
2759 // block. First, we create the blocks for the then...else statements, and
2760 // then we create the block containing the if statement. If we were in the
2761 // middle of a block, we stop processing that block. That block is then the
2762 // implicit successor for the "then" and "else" clauses.
2764 // Save local scope position because in case of condition variable ScopePos
2765 // won't be restored when traversing AST.
2766 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2768 // Create local scope for C++17 if init-stmt if one exists.
2769 if (Stmt *Init = I->getInit())
2770 addLocalScopeForStmt(Init);
2772 // Create local scope for possible condition variable.
2773 // Store scope position. Add implicit destructor.
2774 if (VarDecl *VD = I->getConditionVariable())
2775 addLocalScopeForVarDecl(VD);
2777 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), I);
2779 // The block we were processing is now finished. Make it the successor
2787 // Process the false branch.
2788 CFGBlock *ElseBlock = Succ;
2790 if (Stmt *Else = I->getElse()) {
2791 SaveAndRestore<CFGBlock*> sv(Succ);
2793 // NULL out Block so that the recursive call to Visit will
2794 // create a new basic block.
2797 // If branch is not a compound statement create implicit scope
2798 // and add destructors.
2799 if (!isa<CompoundStmt>(Else))
2800 addLocalScopeAndDtors(Else);
2802 ElseBlock = addStmt(Else);
2804 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
2805 ElseBlock = sv.get();
2812 // Process the true branch.
2813 CFGBlock *ThenBlock;
2815 Stmt *Then = I->getThen();
2817 SaveAndRestore<CFGBlock*> sv(Succ);
2820 // If branch is not a compound statement create implicit scope
2821 // and add destructors.
2822 if (!isa<CompoundStmt>(Then))
2823 addLocalScopeAndDtors(Then);
2825 ThenBlock = addStmt(Then);
2828 // We can reach here if the "then" body has all NullStmts.
2829 // Create an empty block so we can distinguish between true and false
2830 // branches in path-sensitive analyses.
2831 ThenBlock = createBlock(false);
2832 addSuccessor(ThenBlock, sv.get());
2839 // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by
2840 // having these handle the actual control-flow jump. Note that
2841 // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)"
2842 // we resort to the old control-flow behavior. This special handling
2843 // removes infeasible paths from the control-flow graph by having the
2844 // control-flow transfer of '&&' or '||' go directly into the then/else
2846 BinaryOperator *Cond =
2847 I->getConditionVariable()
2849 : dyn_cast<BinaryOperator>(I->getCond()->IgnoreParens());
2850 CFGBlock *LastBlock;
2851 if (Cond && Cond->isLogicalOp())
2852 LastBlock = VisitLogicalOperator(Cond, I, ThenBlock, ElseBlock).first;
2854 // Now create a new block containing the if statement.
2855 Block = createBlock(false);
2857 // Set the terminator of the new block to the If statement.
2858 Block->setTerminator(I);
2860 // See if this is a known constant.
2861 const TryResult &KnownVal = tryEvaluateBool(I->getCond());
2863 // Add the successors. If we know that specific branches are
2864 // unreachable, inform addSuccessor() of that knowledge.
2865 addSuccessor(Block, ThenBlock, /* isReachable = */ !KnownVal.isFalse());
2866 addSuccessor(Block, ElseBlock, /* isReachable = */ !KnownVal.isTrue());
2868 // Add the condition as the last statement in the new block. This may
2869 // create new blocks as the condition may contain control-flow. Any newly
2870 // created blocks will be pointed to be "Block".
2871 LastBlock = addStmt(I->getCond());
2873 // If the IfStmt contains a condition variable, add it and its
2874 // initializer to the CFG.
2875 if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) {
2877 LastBlock = addStmt(const_cast<DeclStmt *>(DS));
2881 // Finally, if the IfStmt contains a C++17 init-stmt, add it to the CFG.
2882 if (Stmt *Init = I->getInit()) {
2884 LastBlock = addStmt(Init);
2890 CFGBlock *CFGBuilder::VisitReturnStmt(Stmt *S) {
2891 // If we were in the middle of a block we stop processing that block.
2893 // NOTE: If a "return" or "co_return" appears in the middle of a block, this
2894 // means that the code afterwards is DEAD (unreachable). We still keep
2895 // a basic block for that code; a simple "mark-and-sweep" from the entry
2896 // block will be able to report such dead blocks.
2897 assert(isa<ReturnStmt>(S) || isa<CoreturnStmt>(S));
2899 // Create the new block.
2900 Block = createBlock(false);
2902 addAutomaticObjHandling(ScopePos, LocalScope::const_iterator(), S);
2904 if (auto *R = dyn_cast<ReturnStmt>(S))
2905 findConstructionContexts(
2906 ConstructionContextLayer::create(cfg->getBumpVectorContext(), R),
2909 // If the one of the destructors does not return, we already have the Exit
2910 // block as a successor.
2911 if (!Block->hasNoReturnElement())
2912 addSuccessor(Block, &cfg->getExit());
2914 // Add the return statement to the block. This may create new blocks if R
2915 // contains control-flow (short-circuit operations).
2916 return VisitStmt(S, AddStmtChoice::AlwaysAdd);
2919 CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) {
2920 // SEHExceptStmt are treated like labels, so they are the first statement in a
2923 // Save local scope position because in case of exception variable ScopePos
2924 // won't be restored when traversing AST.
2925 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2927 addStmt(ES->getBlock());
2928 CFGBlock *SEHExceptBlock = Block;
2929 if (!SEHExceptBlock)
2930 SEHExceptBlock = createBlock();
2932 appendStmt(SEHExceptBlock, ES);
2934 // Also add the SEHExceptBlock as a label, like with regular labels.
2935 SEHExceptBlock->setLabel(ES);
2937 // Bail out if the CFG is bad.
2941 // We set Block to NULL to allow lazy creation of a new block (if necessary).
2944 return SEHExceptBlock;
2947 CFGBlock *CFGBuilder::VisitSEHFinallyStmt(SEHFinallyStmt *FS) {
2948 return VisitCompoundStmt(FS->getBlock());
2951 CFGBlock *CFGBuilder::VisitSEHLeaveStmt(SEHLeaveStmt *LS) {
2952 // "__leave" is a control-flow statement. Thus we stop processing the current
2957 // Now create a new block that ends with the __leave statement.
2958 Block = createBlock(false);
2959 Block->setTerminator(LS);
2961 // If there is no target for the __leave, then we are looking at an incomplete
2962 // AST. This means that the CFG cannot be constructed.
2963 if (SEHLeaveJumpTarget.block) {
2964 addAutomaticObjHandling(ScopePos, SEHLeaveJumpTarget.scopePosition, LS);
2965 addSuccessor(Block, SEHLeaveJumpTarget.block);
2972 CFGBlock *CFGBuilder::VisitSEHTryStmt(SEHTryStmt *Terminator) {
2973 // "__try"/"__except"/"__finally" is a control-flow statement. Thus we stop
2974 // processing the current block.
2975 CFGBlock *SEHTrySuccessor = nullptr;
2980 SEHTrySuccessor = Block;
2981 } else SEHTrySuccessor = Succ;
2983 // FIXME: Implement __finally support.
2984 if (Terminator->getFinallyHandler())
2987 CFGBlock *PrevSEHTryTerminatedBlock = TryTerminatedBlock;
2989 // Create a new block that will contain the __try statement.
2990 CFGBlock *NewTryTerminatedBlock = createBlock(false);
2992 // Add the terminator in the __try block.
2993 NewTryTerminatedBlock->setTerminator(Terminator);
2995 if (SEHExceptStmt *Except = Terminator->getExceptHandler()) {
2996 // The code after the try is the implicit successor if there's an __except.
2997 Succ = SEHTrySuccessor;
2999 CFGBlock *ExceptBlock = VisitSEHExceptStmt(Except);
3002 // Add this block to the list of successors for the block with the try
3004 addSuccessor(NewTryTerminatedBlock, ExceptBlock);
3006 if (PrevSEHTryTerminatedBlock)
3007 addSuccessor(NewTryTerminatedBlock, PrevSEHTryTerminatedBlock);
3009 addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
3011 // The code after the try is the implicit successor.
3012 Succ = SEHTrySuccessor;
3014 // Save the current "__try" context.
3015 SaveAndRestore<CFGBlock *> save_try(TryTerminatedBlock,
3016 NewTryTerminatedBlock);
3017 cfg->addTryDispatchBlock(TryTerminatedBlock);
3019 // Save the current value for the __leave target.
3020 // All __leaves should go to the code following the __try
3021 // (FIXME: or if the __try has a __finally, to the __finally.)
3022 SaveAndRestore<JumpTarget> save_break(SEHLeaveJumpTarget);
3023 SEHLeaveJumpTarget = JumpTarget(SEHTrySuccessor, ScopePos);
3025 assert(Terminator->getTryBlock() && "__try must contain a non-NULL body");
3027 return addStmt(Terminator->getTryBlock());
3030 CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
3031 // Get the block of the labeled statement. Add it to our map.
3032 addStmt(L->getSubStmt());
3033 CFGBlock *LabelBlock = Block;
3035 if (!LabelBlock) // This can happen when the body is empty, i.e.
3036 LabelBlock = createBlock(); // scopes that only contains NullStmts.
3038 assert(LabelMap.find(L->getDecl()) == LabelMap.end() &&
3039 "label already in map");
3040 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
3042 // Labels partition blocks, so this is the end of the basic block we were
3043 // processing (L is the block's label). Because this is label (and we have
3044 // already processed the substatement) there is no extra control-flow to worry
3046 LabelBlock->setLabel(L);
3050 // We set Block to NULL to allow lazy creation of a new block (if necessary);
3053 // This block is now the implicit successor of other blocks.
3059 CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
3060 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3061 for (const BlockDecl::Capture &CI : E->getBlockDecl()->captures()) {
3062 if (Expr *CopyExpr = CI.getCopyExpr()) {
3063 CFGBlock *Tmp = Visit(CopyExpr);
3071 CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
3072 CFGBlock *LastBlock = VisitNoRecurse(E, asc);
3073 for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),
3074 et = E->capture_init_end(); it != et; ++it) {
3075 if (Expr *Init = *it) {
3076 CFGBlock *Tmp = Visit(Init);
3084 CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
3085 // Goto is a control-flow statement. Thus we stop processing the current
3086 // block and create a new one.
3088 Block = createBlock(false);
3089 Block->setTerminator(G);
3091 // If we already know the mapping to the label block add the successor now.
3092 LabelMapTy::iterator I = LabelMap.find(G->getLabel());
3094 if (I == LabelMap.end())
3095 // We will need to backpatch this block later.
3096 BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
3098 JumpTarget JT = I->second;
3099 addAutomaticObjHandling(ScopePos, JT.scopePosition, G);
3100 addSuccessor(Block, JT.block);
3106 CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
3107 CFGBlock *LoopSuccessor = nullptr;
3109 // Save local scope position because in case of condition variable ScopePos
3110 // won't be restored when traversing AST.
3111 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3113 // Create local scope for init statement and possible condition variable.
3114 // Add destructor for init statement and condition variable.
3115 // Store scope position for continue statement.
3116 if (Stmt *Init = F->getInit())
3117 addLocalScopeForStmt(Init);
3118 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3120 if (VarDecl *VD = F->getConditionVariable())
3121 addLocalScopeForVarDecl(VD);
3122 LocalScope::const_iterator ContinueScopePos = ScopePos;
3124 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F);
3128 // "for" is a control-flow statement. Thus we stop processing the current
3133 LoopSuccessor = Block;
3135 LoopSuccessor = Succ;
3137 // Save the current value for the break targets.
3138 // All breaks should go to the code following the loop.
3139 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
3140 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3142 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3144 // Now create the loop body.
3146 assert(F->getBody());
3148 // Save the current values for Block, Succ, continue and break targets.
3149 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3150 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
3152 // Create an empty block to represent the transition block for looping back
3153 // to the head of the loop. If we have increment code, it will
3154 // go in this block as well.
3155 Block = Succ = TransitionBlock = createBlock(false);
3156 TransitionBlock->setLoopTarget(F);
3158 if (Stmt *I = F->getInc()) {
3159 // Generate increment code in its own basic block. This is the target of
3160 // continue statements.
3164 // Finish up the increment (or empty) block if it hasn't been already.
3166 assert(Block == Succ);
3172 // The starting block for the loop increment is the block that should
3173 // represent the 'loop target' for looping back to the start of the loop.
3174 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
3175 ContinueJumpTarget.block->setLoopTarget(F);
3177 // Loop body should end with destructor of Condition variable (if any).
3178 addAutomaticObjHandling(ScopePos, LoopBeginScopePos, F);
3180 // If body is not a compound statement create implicit scope
3181 // and add destructors.
3182 if (!isa<CompoundStmt>(F->getBody()))
3183 addLocalScopeAndDtors(F->getBody());
3185 // Now populate the body block, and in the process create new blocks as we
3186 // walk the body of the loop.
3187 BodyBlock = addStmt(F->getBody());
3190 // In the case of "for (...;...;...);" we can have a null BodyBlock.
3191 // Use the continue jump target as the proxy for the body.
3192 BodyBlock = ContinueJumpTarget.block;
3198 // Because of short-circuit evaluation, the condition of the loop can span
3199 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3200 // evaluate the condition.
3201 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3204 Expr *C = F->getCond();
3205 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3207 // Specially handle logical operators, which have a slightly
3208 // more optimal CFG representation.
3209 if (BinaryOperator *Cond =
3210 dyn_cast_or_null<BinaryOperator>(C ? C->IgnoreParens() : nullptr))
3211 if (Cond->isLogicalOp()) {
3212 std::tie(EntryConditionBlock, ExitConditionBlock) =
3213 VisitLogicalOperator(Cond, F, BodyBlock, LoopSuccessor);
3217 // The default case when not handling logical operators.
3218 EntryConditionBlock = ExitConditionBlock = createBlock(false);
3219 ExitConditionBlock->setTerminator(F);
3221 // See if this is a known constant.
3222 TryResult KnownVal(true);
3225 // Now add the actual condition to the condition block.
3226 // Because the condition itself may contain control-flow, new blocks may
3227 // be created. Thus we update "Succ" after adding the condition.
3228 Block = ExitConditionBlock;
3229 EntryConditionBlock = addStmt(C);
3231 // If this block contains a condition variable, add both the condition
3232 // variable and initializer to the CFG.
3233 if (VarDecl *VD = F->getConditionVariable()) {
3234 if (Expr *Init = VD->getInit()) {
3236 const DeclStmt *DS = F->getConditionVariableDeclStmt();
3237 assert(DS->isSingleDecl());
3238 findConstructionContexts(
3239 ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),
3241 appendStmt(Block, DS);
3242 EntryConditionBlock = addStmt(Init);
3243 assert(Block == EntryConditionBlock);
3244 maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);
3248 if (Block && badCFG)
3251 KnownVal = tryEvaluateBool(C);
3254 // Add the loop body entry as a successor to the condition.
3255 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);
3256 // Link up the condition block with the code that follows the loop. (the
3258 addSuccessor(ExitConditionBlock,
3259 KnownVal.isTrue() ? nullptr : LoopSuccessor);
3262 // Link up the loop-back block to the entry condition block.
3263 addSuccessor(TransitionBlock, EntryConditionBlock);
3265 // The condition block is the implicit successor for any code above the loop.
3266 Succ = EntryConditionBlock;
3268 // If the loop contains initialization, create a new block for those
3269 // statements. This block can also contain statements that precede the loop.
3270 if (Stmt *I = F->getInit()) {
3271 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3272 ScopePos = LoopBeginScopePos;
3273 Block = createBlock();
3277 // There is no loop initialization. We are thus basically a while loop.
3278 // NULL out Block to force lazy block construction.
3280 Succ = EntryConditionBlock;
3281 return EntryConditionBlock;
3285 CFGBuilder::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,
3286 AddStmtChoice asc) {
3287 findConstructionContexts(
3288 ConstructionContextLayer::create(cfg->getBumpVectorContext(), MTE),
3289 MTE->getTemporary());
3291 return VisitStmt(MTE, asc);
3294 CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
3295 if (asc.alwaysAdd(*this, M)) {
3297 appendStmt(Block, M);
3299 return Visit(M->getBase());
3302 CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
3303 // Objective-C fast enumeration 'for' statements:
3304 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
3306 // for ( Type newVariable in collection_expression ) { statements }
3311 // 1. collection_expression
3312 // T. jump to loop_entry
3314 // 1. side-effects of element expression
3315 // 1. ObjCForCollectionStmt [performs binding to newVariable]
3316 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
3319 // T. jump to loop_entry
3325 // Type existingItem;
3326 // for ( existingItem in expression ) { statements }
3330 // the same with newVariable replaced with existingItem; the binding works
3331 // the same except that for one ObjCForCollectionStmt::getElement() returns
3332 // a DeclStmt and the other returns a DeclRefExpr.
3334 CFGBlock *LoopSuccessor = nullptr;
3339 LoopSuccessor = Block;
3342 LoopSuccessor = Succ;
3344 // Build the condition blocks.
3345 CFGBlock *ExitConditionBlock = createBlock(false);
3347 // Set the terminator for the "exit" condition block.
3348 ExitConditionBlock->setTerminator(S);
3350 // The last statement in the block should be the ObjCForCollectionStmt, which
3351 // performs the actual binding to 'element' and determines if there are any
3352 // more items in the collection.
3353 appendStmt(ExitConditionBlock, S);
3354 Block = ExitConditionBlock;
3356 // Walk the 'element' expression to see if there are any side-effects. We
3357 // generate new blocks as necessary. We DON'T add the statement by default to
3358 // the CFG unless it contains control-flow.
3359 CFGBlock *EntryConditionBlock = Visit(S->getElement(),
3360 AddStmtChoice::NotAlwaysAdd);
3367 // The condition block is the implicit successor for the loop body as well as
3368 // any code above the loop.
3369 Succ = EntryConditionBlock;
3371 // Now create the true branch.
3373 // Save the current values for Succ, continue and break targets.
3374 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3375 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3376 save_break(BreakJumpTarget);
3378 // Add an intermediate block between the BodyBlock and the
3379 // EntryConditionBlock to represent the "loop back" transition, for looping
3380 // back to the head of the loop.
3381 CFGBlock *LoopBackBlock = nullptr;
3382 Succ = LoopBackBlock = createBlock();
3383 LoopBackBlock->setLoopTarget(S);
3385 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3386 ContinueJumpTarget = JumpTarget(Succ, ScopePos);
3388 CFGBlock *BodyBlock = addStmt(S->getBody());
3391 BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;"
3397 // This new body block is a successor to our "exit" condition block.
3398 addSuccessor(ExitConditionBlock, BodyBlock);
3401 // Link up the condition block with the code that follows the loop.
3402 // (the false branch).
3403 addSuccessor(ExitConditionBlock, LoopSuccessor);
3405 // Now create a prologue block to contain the collection expression.
3406 Block = createBlock();
3407 return addStmt(S->getCollection());
3410 CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) {
3412 return addStmt(S->getSubStmt());
3413 // TODO: consider adding cleanups for the end of @autoreleasepool scope.
3416 CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
3417 // FIXME: Add locking 'primitives' to CFG for @synchronized.
3420 CFGBlock *SyncBlock = addStmt(S->getSynchBody());
3422 // The sync body starts its own basic block. This makes it a little easier
3423 // for diagnostic clients.
3432 // Add the @synchronized to the CFG.
3434 appendStmt(Block, S);
3436 // Inline the sync expression.
3437 return addStmt(S->getSynchExpr());
3440 CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) {
3445 CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {
3448 // Add the PseudoObject as the last thing.
3449 appendStmt(Block, E);
3451 CFGBlock *lastBlock = Block;
3453 // Before that, evaluate all of the semantics in order. In
3454 // CFG-land, that means appending them in reverse order.
3455 for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {
3456 Expr *Semantic = E->getSemanticExpr(--i);
3458 // If the semantic is an opaque value, we're being asked to bind
3459 // it to its source expression.
3460 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
3461 Semantic = OVE->getSourceExpr();
3463 if (CFGBlock *B = Visit(Semantic))
3470 CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
3471 CFGBlock *LoopSuccessor = nullptr;
3473 // Save local scope position because in case of condition variable ScopePos
3474 // won't be restored when traversing AST.
3475 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3477 // Create local scope for possible condition variable.
3478 // Store scope position for continue statement.
3479 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
3480 if (VarDecl *VD = W->getConditionVariable()) {
3481 addLocalScopeForVarDecl(VD);
3482 addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
3486 // "while" is a control-flow statement. Thus we stop processing the current
3491 LoopSuccessor = Block;
3494 LoopSuccessor = Succ;
3497 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
3499 // Process the loop body.
3501 assert(W->getBody());
3503 // Save the current values for Block, Succ, continue and break targets.
3504 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3505 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3506 save_break(BreakJumpTarget);
3508 // Create an empty block to represent the transition block for looping back
3509 // to the head of the loop.
3510 Succ = TransitionBlock = createBlock(false);
3511 TransitionBlock->setLoopTarget(W);
3512 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
3514 // All breaks should go to the code following the loop.
3515 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3517 // Loop body should end with destructor of Condition variable (if any).
3518 addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);
3520 // If body is not a compound statement create implicit scope
3521 // and add destructors.
3522 if (!isa<CompoundStmt>(W->getBody()))
3523 addLocalScopeAndDtors(W->getBody());
3525 // Create the body. The returned block is the entry to the loop body.
3526 BodyBlock = addStmt(W->getBody());
3529 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
3530 else if (Block && badCFG)
3534 // Because of short-circuit evaluation, the condition of the loop can span
3535 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3536 // evaluate the condition.
3537 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
3540 Expr *C = W->getCond();
3542 // Specially handle logical operators, which have a slightly
3543 // more optimal CFG representation.
3544 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(C->IgnoreParens()))
3545 if (Cond->isLogicalOp()) {
3546 std::tie(EntryConditionBlock, ExitConditionBlock) =
3547 VisitLogicalOperator(Cond, W, BodyBlock, LoopSuccessor);
3551 // The default case when not handling logical operators.
3552 ExitConditionBlock = createBlock(false);
3553 ExitConditionBlock->setTerminator(W);
3555 // Now add the actual condition to the condition block.
3556 // Because the condition itself may contain control-flow, new blocks may
3557 // be created. Thus we update "Succ" after adding the condition.
3558 Block = ExitConditionBlock;
3559 Block = EntryConditionBlock = addStmt(C);
3561 // If this block contains a condition variable, add both the condition
3562 // variable and initializer to the CFG.
3563 if (VarDecl *VD = W->getConditionVariable()) {
3564 if (Expr *Init = VD->getInit()) {
3566 const DeclStmt *DS = W->getConditionVariableDeclStmt();
3567 assert(DS->isSingleDecl());
3568 findConstructionContexts(
3569 ConstructionContextLayer::create(cfg->getBumpVectorContext(),
3570 const_cast<DeclStmt *>(DS)),
3572 appendStmt(Block, DS);
3573 EntryConditionBlock = addStmt(Init);
3574 assert(Block == EntryConditionBlock);
3575 maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);
3579 if (Block && badCFG)
3582 // See if this is a known constant.
3583 const TryResult& KnownVal = tryEvaluateBool(C);
3585 // Add the loop body entry as a successor to the condition.
3586 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);
3587 // Link up the condition block with the code that follows the loop. (the
3589 addSuccessor(ExitConditionBlock,
3590 KnownVal.isTrue() ? nullptr : LoopSuccessor);
3593 // Link up the loop-back block to the entry condition block.
3594 addSuccessor(TransitionBlock, EntryConditionBlock);
3596 // There can be no more statements in the condition block since we loop back
3597 // to this block. NULL out Block to force lazy creation of another block.
3600 // Return the condition block, which is the dominating block for the loop.
3601 Succ = EntryConditionBlock;
3602 return EntryConditionBlock;
3605 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) {
3606 // FIXME: For now we pretend that @catch and the code it contains does not
3611 CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
3612 // FIXME: This isn't complete. We basically treat @throw like a return
3615 // If we were in the middle of a block we stop processing that block.
3619 // Create the new block.
3620 Block = createBlock(false);
3622 // The Exit block is the only successor.
3623 addSuccessor(Block, &cfg->getExit());
3625 // Add the statement to the block. This may create new blocks if S contains
3626 // control-flow (short-circuit operations).
3627 return VisitStmt(S, AddStmtChoice::AlwaysAdd);
3630 CFGBlock *CFGBuilder::VisitObjCMessageExpr(ObjCMessageExpr *ME,
3631 AddStmtChoice asc) {
3632 findConstructionContextsForArguments(ME);
3635 appendObjCMessage(Block, ME);
3637 return VisitChildren(ME);
3640 CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
3641 // If we were in the middle of a block we stop processing that block.
3645 // Create the new block.
3646 Block = createBlock(false);
3648 if (TryTerminatedBlock)
3649 // The current try statement is the only successor.
3650 addSuccessor(Block, TryTerminatedBlock);
3652 // otherwise the Exit block is the only successor.
3653 addSuccessor(Block, &cfg->getExit());
3655 // Add the statement to the block. This may create new blocks if S contains
3656 // control-flow (short-circuit operations).
3657 return VisitStmt(T, AddStmtChoice::AlwaysAdd);
3660 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
3661 CFGBlock *LoopSuccessor = nullptr;
3665 // "do...while" is a control-flow statement. Thus we stop processing the
3670 LoopSuccessor = Block;
3672 LoopSuccessor = Succ;
3674 // Because of short-circuit evaluation, the condition of the loop can span
3675 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
3676 // evaluate the condition.
3677 CFGBlock *ExitConditionBlock = createBlock(false);
3678 CFGBlock *EntryConditionBlock = ExitConditionBlock;
3680 // Set the terminator for the "exit" condition block.
3681 ExitConditionBlock->setTerminator(D);
3683 // Now add the actual condition to the condition block. Because the condition
3684 // itself may contain control-flow, new blocks may be created.
3685 if (Stmt *C = D->getCond()) {
3686 Block = ExitConditionBlock;
3687 EntryConditionBlock = addStmt(C);
3694 // The condition block is the implicit successor for the loop body.
3695 Succ = EntryConditionBlock;
3697 // See if this is a known constant.
3698 const TryResult &KnownVal = tryEvaluateBool(D->getCond());
3700 // Process the loop body.
3701 CFGBlock *BodyBlock = nullptr;
3703 assert(D->getBody());
3705 // Save the current values for Block, Succ, and continue and break targets
3706 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3707 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
3708 save_break(BreakJumpTarget);
3710 // All continues within this loop should go to the condition block
3711 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
3713 // All breaks should go to the code following the loop.
3714 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3716 // NULL out Block to force lazy instantiation of blocks for the body.
3719 // If body is not a compound statement create implicit scope
3720 // and add destructors.
3721 if (!isa<CompoundStmt>(D->getBody()))
3722 addLocalScopeAndDtors(D->getBody());
3724 // Create the body. The returned block is the entry to the loop body.
3725 BodyBlock = addStmt(D->getBody());
3728 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
3734 // Add an intermediate block between the BodyBlock and the
3735 // ExitConditionBlock to represent the "loop back" transition. Create an
3736 // empty block to represent the transition block for looping back to the
3737 // head of the loop.
3738 // FIXME: Can we do this more efficiently without adding another block?
3741 CFGBlock *LoopBackBlock = createBlock();
3742 LoopBackBlock->setLoopTarget(D);
3744 if (!KnownVal.isFalse())
3745 // Add the loop body entry as a successor to the condition.
3746 addSuccessor(ExitConditionBlock, LoopBackBlock);
3748 addSuccessor(ExitConditionBlock, nullptr);
3751 // Link up the condition block with the code that follows the loop.
3752 // (the false branch).
3753 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);
3755 // There can be no more statements in the body block(s) since we loop back to
3756 // the body. NULL out Block to force lazy creation of another block.
3759 // Return the loop body, which is the dominating block for the loop.
3764 CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
3765 // "continue" is a control-flow statement. Thus we stop processing the
3770 // Now create a new block that ends with the continue statement.
3771 Block = createBlock(false);
3772 Block->setTerminator(C);
3774 // If there is no target for the continue, then we are looking at an
3775 // incomplete AST. This means the CFG cannot be constructed.
3776 if (ContinueJumpTarget.block) {
3777 addAutomaticObjHandling(ScopePos, ContinueJumpTarget.scopePosition, C);
3778 addSuccessor(Block, ContinueJumpTarget.block);
3785 CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
3786 AddStmtChoice asc) {
3787 if (asc.alwaysAdd(*this, E)) {
3789 appendStmt(Block, E);
3792 // VLA types have expressions that must be evaluated.
3793 CFGBlock *lastBlock = Block;
3795 if (E->isArgumentType()) {
3796 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());
3797 VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr()))
3798 lastBlock = addStmt(VA->getSizeExpr());
3803 /// VisitStmtExpr - Utility method to handle (nested) statement
3804 /// expressions (a GCC extension).
3805 CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
3806 if (asc.alwaysAdd(*this, SE)) {
3808 appendStmt(Block, SE);
3810 return VisitCompoundStmt(SE->getSubStmt());
3813 CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
3814 // "switch" is a control-flow statement. Thus we stop processing the current
3816 CFGBlock *SwitchSuccessor = nullptr;
3818 // Save local scope position because in case of condition variable ScopePos
3819 // won't be restored when traversing AST.
3820 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3822 // Create local scope for C++17 switch init-stmt if one exists.
3823 if (Stmt *Init = Terminator->getInit())
3824 addLocalScopeForStmt(Init);
3826 // Create local scope for possible condition variable.
3827 // Store scope position. Add implicit destructor.
3828 if (VarDecl *VD = Terminator->getConditionVariable())
3829 addLocalScopeForVarDecl(VD);
3831 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), Terminator);
3836 SwitchSuccessor = Block;
3837 } else SwitchSuccessor = Succ;
3839 // Save the current "switch" context.
3840 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
3841 save_default(DefaultCaseBlock);
3842 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
3844 // Set the "default" case to be the block after the switch statement. If the
3845 // switch statement contains a "default:", this value will be overwritten with
3846 // the block for that code.
3847 DefaultCaseBlock = SwitchSuccessor;
3849 // Create a new block that will contain the switch statement.
3850 SwitchTerminatedBlock = createBlock(false);
3852 // Now process the switch body. The code after the switch is the implicit
3854 Succ = SwitchSuccessor;
3855 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
3857 // When visiting the body, the case statements should automatically get linked
3858 // up to the switch. We also don't keep a pointer to the body, since all
3859 // control-flow from the switch goes to case/default statements.
3860 assert(Terminator->getBody() && "switch must contain a non-NULL body");
3863 // For pruning unreachable case statements, save the current state
3864 // for tracking the condition value.
3865 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered,
3868 // Determine if the switch condition can be explicitly evaluated.
3869 assert(Terminator->getCond() && "switch condition must be non-NULL");
3870 Expr::EvalResult result;
3871 bool b = tryEvaluate(Terminator->getCond(), result);
3872 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond,
3873 b ? &result : nullptr);
3875 // If body is not a compound statement create implicit scope
3876 // and add destructors.
3877 if (!isa<CompoundStmt>(Terminator->getBody()))
3878 addLocalScopeAndDtors(Terminator->getBody());
3880 addStmt(Terminator->getBody());
3886 // If we have no "default:" case, the default transition is to the code
3887 // following the switch body. Moreover, take into account if all the
3888 // cases of a switch are covered (e.g., switching on an enum value).
3890 // Note: We add a successor to a switch that is considered covered yet has no
3891 // case statements if the enumeration has no enumerators.
3892 bool SwitchAlwaysHasSuccessor = false;
3893 SwitchAlwaysHasSuccessor |= switchExclusivelyCovered;
3894 SwitchAlwaysHasSuccessor |= Terminator->isAllEnumCasesCovered() &&
3895 Terminator->getSwitchCaseList();
3896 addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock,
3897 !SwitchAlwaysHasSuccessor);
3899 // Add the terminator and condition in the switch block.
3900 SwitchTerminatedBlock->setTerminator(Terminator);
3901 Block = SwitchTerminatedBlock;
3902 CFGBlock *LastBlock = addStmt(Terminator->getCond());
3904 // If the SwitchStmt contains a condition variable, add both the
3905 // SwitchStmt and the condition variable initialization to the CFG.
3906 if (VarDecl *VD = Terminator->getConditionVariable()) {
3907 if (Expr *Init = VD->getInit()) {
3909 appendStmt(Block, Terminator->getConditionVariableDeclStmt());
3910 LastBlock = addStmt(Init);
3911 maybeAddScopeBeginForVarDecl(LastBlock, VD, Init);
3915 // Finally, if the SwitchStmt contains a C++17 init-stmt, add it to the CFG.
3916 if (Stmt *Init = Terminator->getInit()) {
3918 LastBlock = addStmt(Init);
3924 static bool shouldAddCase(bool &switchExclusivelyCovered,
3925 const Expr::EvalResult *switchCond,
3931 bool addCase = false;
3933 if (!switchExclusivelyCovered) {
3934 if (switchCond->Val.isInt()) {
3935 // Evaluate the LHS of the case value.
3936 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
3937 const llvm::APSInt &condInt = switchCond->Val.getInt();
3939 if (condInt == lhsInt) {
3941 switchExclusivelyCovered = true;
3943 else if (condInt > lhsInt) {
3944 if (const Expr *RHS = CS->getRHS()) {
3945 // Evaluate the RHS of the case value.
3946 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
3947 if (V2 >= condInt) {
3949 switchExclusivelyCovered = true;
3960 CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
3961 // CaseStmts are essentially labels, so they are the first statement in a
3963 CFGBlock *TopBlock = nullptr, *LastBlock = nullptr;
3965 if (Stmt *Sub = CS->getSubStmt()) {
3966 // For deeply nested chains of CaseStmts, instead of doing a recursion
3967 // (which can blow out the stack), manually unroll and create blocks
3969 while (isa<CaseStmt>(Sub)) {
3970 CFGBlock *currentBlock = createBlock(false);
3971 currentBlock->setLabel(CS);
3974 addSuccessor(LastBlock, currentBlock);
3976 TopBlock = currentBlock;
3978 addSuccessor(SwitchTerminatedBlock,
3979 shouldAddCase(switchExclusivelyCovered, switchCond,
3981 ? currentBlock : nullptr);
3983 LastBlock = currentBlock;
3984 CS = cast<CaseStmt>(Sub);
3985 Sub = CS->getSubStmt();
3991 CFGBlock *CaseBlock = Block;
3993 CaseBlock = createBlock();
3995 // Cases statements partition blocks, so this is the top of the basic block we
3996 // were processing (the "case XXX:" is the label).
3997 CaseBlock->setLabel(CS);
4002 // Add this block to the list of successors for the block with the switch
4004 assert(SwitchTerminatedBlock);
4005 addSuccessor(SwitchTerminatedBlock, CaseBlock,
4006 shouldAddCase(switchExclusivelyCovered, switchCond,
4009 // We set Block to NULL to allow lazy creation of a new block (if necessary)
4013 addSuccessor(LastBlock, CaseBlock);
4016 // This block is now the implicit successor of other blocks.
4023 CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
4024 if (Terminator->getSubStmt())
4025 addStmt(Terminator->getSubStmt());
4027 DefaultCaseBlock = Block;
4029 if (!DefaultCaseBlock)
4030 DefaultCaseBlock = createBlock();
4032 // Default statements partition blocks, so this is the top of the basic block
4033 // we were processing (the "default:" is the label).
4034 DefaultCaseBlock->setLabel(Terminator);
4039 // Unlike case statements, we don't add the default block to the successors
4040 // for the switch statement immediately. This is done when we finish
4041 // processing the switch statement. This allows for the default case
4042 // (including a fall-through to the code after the switch statement) to always
4043 // be the last successor of a switch-terminated block.
4045 // We set Block to NULL to allow lazy creation of a new block (if necessary)
4048 // This block is now the implicit successor of other blocks.
4049 Succ = DefaultCaseBlock;
4051 return DefaultCaseBlock;
4054 CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
4055 // "try"/"catch" is a control-flow statement. Thus we stop processing the
4057 CFGBlock *TrySuccessor = nullptr;
4062 TrySuccessor = Block;
4063 } else TrySuccessor = Succ;
4065 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
4067 // Create a new block that will contain the try statement.
4068 CFGBlock *NewTryTerminatedBlock = createBlock(false);
4069 // Add the terminator in the try block.
4070 NewTryTerminatedBlock->setTerminator(Terminator);
4072 bool HasCatchAll = false;
4073 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) {
4074 // The code after the try is the implicit successor.
4075 Succ = TrySuccessor;
4076 CXXCatchStmt *CS = Terminator->getHandler(h);
4077 if (CS->getExceptionDecl() == nullptr) {
4081 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);
4084 // Add this block to the list of successors for the block with the try
4086 addSuccessor(NewTryTerminatedBlock, CatchBlock);
4089 if (PrevTryTerminatedBlock)
4090 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);
4092 addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
4095 // The code after the try is the implicit successor.
4096 Succ = TrySuccessor;
4098 // Save the current "try" context.
4099 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock);
4100 cfg->addTryDispatchBlock(TryTerminatedBlock);
4102 assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
4104 return addStmt(Terminator->getTryBlock());
4107 CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
4108 // CXXCatchStmt are treated like labels, so they are the first statement in a
4111 // Save local scope position because in case of exception variable ScopePos
4112 // won't be restored when traversing AST.
4113 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4115 // Create local scope for possible exception variable.
4116 // Store scope position. Add implicit destructor.
4117 if (VarDecl *VD = CS->getExceptionDecl()) {
4118 LocalScope::const_iterator BeginScopePos = ScopePos;
4119 addLocalScopeForVarDecl(VD);
4120 addAutomaticObjHandling(ScopePos, BeginScopePos, CS);
4123 if (CS->getHandlerBlock())
4124 addStmt(CS->getHandlerBlock());
4126 CFGBlock *CatchBlock = Block;
4128 CatchBlock = createBlock();
4130 // CXXCatchStmt is more than just a label. They have semantic meaning
4131 // as well, as they implicitly "initialize" the catch variable. Add
4132 // it to the CFG as a CFGElement so that the control-flow of these
4133 // semantics gets captured.
4134 appendStmt(CatchBlock, CS);
4136 // Also add the CXXCatchStmt as a label, to mirror handling of regular
4138 CatchBlock->setLabel(CS);
4140 // Bail out if the CFG is bad.
4144 // We set Block to NULL to allow lazy creation of a new block (if necessary)
4150 CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
4151 // C++0x for-range statements are specified as [stmt.ranged]:
4154 // auto && __range = range-init;
4155 // for ( auto __begin = begin-expr,
4156 // __end = end-expr;
4157 // __begin != __end;
4159 // for-range-declaration = *__begin;
4164 // Save local scope position before the addition of the implicit variables.
4165 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
4167 // Create local scopes and destructors for range, begin and end variables.
4168 if (Stmt *Range = S->getRangeStmt())
4169 addLocalScopeForStmt(Range);
4170 if (Stmt *Begin = S->getBeginStmt())
4171 addLocalScopeForStmt(Begin);
4172 if (Stmt *End = S->getEndStmt())
4173 addLocalScopeForStmt(End);
4174 addAutomaticObjHandling(ScopePos, save_scope_pos.get(), S);
4176 LocalScope::const_iterator ContinueScopePos = ScopePos;
4178 // "for" is a control-flow statement. Thus we stop processing the current
4180 CFGBlock *LoopSuccessor = nullptr;
4184 LoopSuccessor = Block;
4186 LoopSuccessor = Succ;
4188 // Save the current value for the break targets.
4189 // All breaks should go to the code following the loop.
4190 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
4191 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
4193 // The block for the __begin != __end expression.
4194 CFGBlock *ConditionBlock = createBlock(false);
4195 ConditionBlock->setTerminator(S);
4197 // Now add the actual condition to the condition block.
4198 if (Expr *C = S->getCond()) {
4199 Block = ConditionBlock;
4200 CFGBlock *BeginConditionBlock = addStmt(C);
4203 assert(BeginConditionBlock == ConditionBlock &&
4204 "condition block in for-range was unexpectedly complex");
4205 (void)BeginConditionBlock;
4208 // The condition block is the implicit successor for the loop body as well as
4209 // any code above the loop.
4210 Succ = ConditionBlock;
4212 // See if this is a known constant.
4213 TryResult KnownVal(true);
4216 KnownVal = tryEvaluateBool(S->getCond());
4218 // Now create the loop body.
4220 assert(S->getBody());
4222 // Save the current values for Block, Succ, and continue targets.
4223 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
4224 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
4226 // Generate increment code in its own basic block. This is the target of
4227 // continue statements.
4229 Succ = addStmt(S->getInc());
4232 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
4234 // The starting block for the loop increment is the block that should
4235 // represent the 'loop target' for looping back to the start of the loop.
4236 ContinueJumpTarget.block->setLoopTarget(S);
4238 // Finish up the increment block and prepare to start the loop body.
4244 // Add implicit scope and dtors for loop variable.
4245 addLocalScopeAndDtors(S->getLoopVarStmt());
4247 // Populate a new block to contain the loop body and loop variable.
4248 addStmt(S->getBody());
4251 CFGBlock *LoopVarStmtBlock = addStmt(S->getLoopVarStmt());
4255 // This new body block is a successor to our condition block.
4256 addSuccessor(ConditionBlock,
4257 KnownVal.isFalse() ? nullptr : LoopVarStmtBlock);
4260 // Link up the condition block with the code that follows the loop (the
4262 addSuccessor(ConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);
4264 // Add the initialization statements.
4265 Block = createBlock();
4266 addStmt(S->getBeginStmt());
4267 addStmt(S->getEndStmt());
4268 CFGBlock *Head = addStmt(S->getRangeStmt());
4270 Head = addStmt(S->getInit());
4274 CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
4275 AddStmtChoice asc) {
4276 if (BuildOpts.AddTemporaryDtors) {
4277 // If adding implicit destructors visit the full expression for adding
4278 // destructors of temporaries.
4279 TempDtorContext Context;
4280 VisitForTemporaryDtors(E->getSubExpr(), false, Context);
4282 // Full expression has to be added as CFGStmt so it will be sequenced
4283 // before destructors of it's temporaries.
4284 asc = asc.withAlwaysAdd(true);
4286 return Visit(E->getSubExpr(), asc);
4289 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
4290 AddStmtChoice asc) {
4291 if (asc.alwaysAdd(*this, E)) {
4293 appendStmt(Block, E);
4295 findConstructionContexts(
4296 ConstructionContextLayer::create(cfg->getBumpVectorContext(), E),
4299 // We do not want to propagate the AlwaysAdd property.
4300 asc = asc.withAlwaysAdd(false);
4302 return Visit(E->getSubExpr(), asc);
4305 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
4306 AddStmtChoice asc) {
4307 // If the constructor takes objects as arguments by value, we need to properly
4308 // construct these objects. Construction contexts we find here aren't for the
4309 // constructor C, they're for its arguments only.
4310 findConstructionContextsForArguments(C);
4313 appendConstructor(Block, C);
4315 return VisitChildren(C);
4318 CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
4319 AddStmtChoice asc) {
4321 appendStmt(Block, NE);
4323 findConstructionContexts(
4324 ConstructionContextLayer::create(cfg->getBumpVectorContext(), NE),
4325 const_cast<CXXConstructExpr *>(NE->getConstructExpr()));
4327 if (NE->getInitializer())
4328 Block = Visit(NE->getInitializer());
4330 if (BuildOpts.AddCXXNewAllocator)
4331 appendNewAllocator(Block, NE);
4334 Block = Visit(NE->getArraySize());
4336 for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),
4337 E = NE->placement_arg_end(); I != E; ++I)
4343 CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
4344 AddStmtChoice asc) {
4346 appendStmt(Block, DE);
4347 QualType DTy = DE->getDestroyedType();
4348 if (!DTy.isNull()) {
4349 DTy = DTy.getNonReferenceType();
4350 CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl();
4352 if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())
4353 appendDeleteDtor(Block, RD, DE);
4357 return VisitChildren(DE);
4360 CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
4361 AddStmtChoice asc) {
4362 if (asc.alwaysAdd(*this, E)) {
4364 appendStmt(Block, E);
4365 // We do not want to propagate the AlwaysAdd property.
4366 asc = asc.withAlwaysAdd(false);
4368 return Visit(E->getSubExpr(), asc);
4371 CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
4372 AddStmtChoice asc) {
4373 // If the constructor takes objects as arguments by value, we need to properly
4374 // construct these objects. Construction contexts we find here aren't for the
4375 // constructor C, they're for its arguments only.
4376 findConstructionContextsForArguments(C);
4379 appendConstructor(Block, C);
4380 return VisitChildren(C);
4383 CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
4384 AddStmtChoice asc) {
4385 if (asc.alwaysAdd(*this, E)) {
4387 appendStmt(Block, E);
4389 return Visit(E->getSubExpr(), AddStmtChoice());
4392 CFGBlock *CFGBuilder::VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc) {
4393 return Visit(E->getSubExpr(), AddStmtChoice());
4396 CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
4397 // Lazily create the indirect-goto dispatch block if there isn't one already.
4398 CFGBlock *IBlock = cfg->getIndirectGotoBlock();
4401 IBlock = createBlock(false);
4402 cfg->setIndirectGotoBlock(IBlock);
4405 // IndirectGoto is a control-flow statement. Thus we stop processing the
4406 // current block and create a new one.
4410 Block = createBlock(false);
4411 Block->setTerminator(I);
4412 addSuccessor(Block, IBlock);
4413 return addStmt(I->getTarget());
4416 CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary,
4417 TempDtorContext &Context) {
4418 assert(BuildOpts.AddImplicitDtors && BuildOpts.AddTemporaryDtors);
4425 switch (E->getStmtClass()) {
4427 return VisitChildrenForTemporaryDtors(E, Context);
4429 case Stmt::BinaryOperatorClass:
4430 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E),
4433 case Stmt::CXXBindTemporaryExprClass:
4434 return VisitCXXBindTemporaryExprForTemporaryDtors(
4435 cast<CXXBindTemporaryExpr>(E), BindToTemporary, Context);
4437 case Stmt::BinaryConditionalOperatorClass:
4438 case Stmt::ConditionalOperatorClass:
4439 return VisitConditionalOperatorForTemporaryDtors(
4440 cast<AbstractConditionalOperator>(E), BindToTemporary, Context);
4442 case Stmt::ImplicitCastExprClass:
4443 // For implicit cast we want BindToTemporary to be passed further.
4444 E = cast<CastExpr>(E)->getSubExpr();
4447 case Stmt::CXXFunctionalCastExprClass:
4448 // For functional cast we want BindToTemporary to be passed further.
4449 E = cast<CXXFunctionalCastExpr>(E)->getSubExpr();
4452 case Stmt::ConstantExprClass:
4453 E = cast<ConstantExpr>(E)->getSubExpr();
4456 case Stmt::ParenExprClass:
4457 E = cast<ParenExpr>(E)->getSubExpr();
4460 case Stmt::MaterializeTemporaryExprClass: {
4461 const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(E);
4462 BindToTemporary = (MTE->getStorageDuration() != SD_FullExpression);
4463 SmallVector<const Expr *, 2> CommaLHSs;
4464 SmallVector<SubobjectAdjustment, 2> Adjustments;
4465 // Find the expression whose lifetime needs to be extended.
4466 E = const_cast<Expr *>(
4467 cast<MaterializeTemporaryExpr>(E)
4468 ->GetTemporaryExpr()
4469 ->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments));
4470 // Visit the skipped comma operator left-hand sides for other temporaries.
4471 for (const Expr *CommaLHS : CommaLHSs) {
4472 VisitForTemporaryDtors(const_cast<Expr *>(CommaLHS),
4473 /*BindToTemporary=*/false, Context);
4478 case Stmt::BlockExprClass:
4479 // Don't recurse into blocks; their subexpressions don't get evaluated
4483 case Stmt::LambdaExprClass: {
4484 // For lambda expressions, only recurse into the capture initializers,
4485 // and not the body.
4486 auto *LE = cast<LambdaExpr>(E);
4487 CFGBlock *B = Block;
4488 for (Expr *Init : LE->capture_inits()) {
4490 if (CFGBlock *R = VisitForTemporaryDtors(
4491 Init, /*BindToTemporary=*/false, Context))
4498 case Stmt::CXXDefaultArgExprClass:
4499 E = cast<CXXDefaultArgExpr>(E)->getExpr();
4502 case Stmt::CXXDefaultInitExprClass:
4503 E = cast<CXXDefaultInitExpr>(E)->getExpr();
4508 CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E,
4509 TempDtorContext &Context) {
4510 if (isa<LambdaExpr>(E)) {
4511 // Do not visit the children of lambdas; they have their own CFGs.
4515 // When visiting children for destructors we want to visit them in reverse
4516 // order that they will appear in the CFG. Because the CFG is built
4517 // bottom-up, this means we visit them in their natural order, which
4518 // reverses them in the CFG.
4519 CFGBlock *B = Block;
4520 for (Stmt *Child : E->children())
4522 if (CFGBlock *R = VisitForTemporaryDtors(Child, false, Context))
4528 CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(
4529 BinaryOperator *E, TempDtorContext &Context) {
4530 if (E->isLogicalOp()) {
4531 VisitForTemporaryDtors(E->getLHS(), false, Context);
4532 TryResult RHSExecuted = tryEvaluateBool(E->getLHS());
4533 if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr)
4534 RHSExecuted.negate();
4536 // We do not know at CFG-construction time whether the right-hand-side was
4537 // executed, thus we add a branch node that depends on the temporary
4538 // constructor call.
4539 TempDtorContext RHSContext(
4540 bothKnownTrue(Context.KnownExecuted, RHSExecuted));
4541 VisitForTemporaryDtors(E->getRHS(), false, RHSContext);
4542 InsertTempDtorDecisionBlock(RHSContext);
4547 if (E->isAssignmentOp()) {
4548 // For assignment operator (=) LHS expression is visited
4549 // before RHS expression. For destructors visit them in reverse order.
4550 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);
4551 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
4552 return LHSBlock ? LHSBlock : RHSBlock;
4555 // For any other binary operator RHS expression is visited before
4556 // LHS expression (order of children). For destructors visit them in reverse
4558 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
4559 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);
4560 return RHSBlock ? RHSBlock : LHSBlock;
4563 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
4564 CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context) {
4565 // First add destructors for temporaries in subexpression.
4566 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr(), false, Context);
4567 if (!BindToTemporary) {
4568 // If lifetime of temporary is not prolonged (by assigning to constant
4569 // reference) add destructor for it.
4571 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
4573 if (Dtor->getParent()->isAnyDestructorNoReturn()) {
4574 // If the destructor is marked as a no-return destructor, we need to
4575 // create a new block for the destructor which does not have as a
4576 // successor anything built thus far. Control won't flow out of this
4579 Block = createNoReturnBlock();
4580 } else if (Context.needsTempDtorBranch()) {
4581 // If we need to introduce a branch, we add a new block that we will hook
4582 // up to a decision block later.
4584 Block = createBlock();
4588 if (Context.needsTempDtorBranch()) {
4589 Context.setDecisionPoint(Succ, E);
4591 appendTemporaryDtor(Block, E);
4598 void CFGBuilder::InsertTempDtorDecisionBlock(const TempDtorContext &Context,
4599 CFGBlock *FalseSucc) {
4600 if (!Context.TerminatorExpr) {
4601 // If no temporary was found, we do not need to insert a decision point.
4604 assert(Context.TerminatorExpr);
4605 CFGBlock *Decision = createBlock(false);
4606 Decision->setTerminator(CFGTerminator(Context.TerminatorExpr, true));
4607 addSuccessor(Decision, Block, !Context.KnownExecuted.isFalse());
4608 addSuccessor(Decision, FalseSucc ? FalseSucc : Context.Succ,
4609 !Context.KnownExecuted.isTrue());
4613 CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
4614 AbstractConditionalOperator *E, bool BindToTemporary,
4615 TempDtorContext &Context) {
4616 VisitForTemporaryDtors(E->getCond(), false, Context);
4617 CFGBlock *ConditionBlock = Block;
4618 CFGBlock *ConditionSucc = Succ;
4619 TryResult ConditionVal = tryEvaluateBool(E->getCond());
4620 TryResult NegatedVal = ConditionVal;
4621 if (NegatedVal.isKnown()) NegatedVal.negate();
4623 TempDtorContext TrueContext(
4624 bothKnownTrue(Context.KnownExecuted, ConditionVal));
4625 VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary, TrueContext);
4626 CFGBlock *TrueBlock = Block;
4628 Block = ConditionBlock;
4629 Succ = ConditionSucc;
4630 TempDtorContext FalseContext(
4631 bothKnownTrue(Context.KnownExecuted, NegatedVal));
4632 VisitForTemporaryDtors(E->getFalseExpr(), BindToTemporary, FalseContext);
4634 if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) {
4635 InsertTempDtorDecisionBlock(FalseContext, TrueBlock);
4636 } else if (TrueContext.TerminatorExpr) {
4638 InsertTempDtorDecisionBlock(TrueContext);
4640 InsertTempDtorDecisionBlock(FalseContext);
4645 /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
4646 /// no successors or predecessors. If this is the first block created in the
4647 /// CFG, it is automatically set to be the Entry and Exit of the CFG.
4648 CFGBlock *CFG::createBlock() {
4649 bool first_block = begin() == end();
4651 // Create the block.
4652 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>();
4653 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this);
4654 Blocks.push_back(Mem, BlkBVC);
4656 // If this is the first block, set it as the Entry and Exit.
4658 Entry = Exit = &back();
4660 // Return the block.
4664 /// buildCFG - Constructs a CFG from an AST.
4665 std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,
4666 ASTContext *C, const BuildOptions &BO) {
4667 CFGBuilder Builder(C, BO);
4668 return Builder.buildCFG(D, Statement);
4671 const CXXDestructorDecl *
4672 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
4673 switch (getKind()) {
4674 case CFGElement::Initializer:
4675 case CFGElement::NewAllocator:
4676 case CFGElement::LoopExit:
4677 case CFGElement::LifetimeEnds:
4678 case CFGElement::Statement:
4679 case CFGElement::Constructor:
4680 case CFGElement::CXXRecordTypedCall:
4681 case CFGElement::ScopeBegin:
4682 case CFGElement::ScopeEnd:
4683 llvm_unreachable("getDestructorDecl should only be used with "
4685 case CFGElement::AutomaticObjectDtor: {
4686 const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();
4687 QualType ty = var->getType();
4689 // FIXME: See CFGBuilder::addLocalScopeForVarDecl.
4691 // Lifetime-extending constructs are handled here. This works for a single
4692 // temporary in an initializer expression.
4693 if (ty->isReferenceType()) {
4694 if (const Expr *Init = var->getInit()) {
4695 ty = getReferenceInitTemporaryType(Init);
4699 while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {
4700 ty = arrayType->getElementType();
4702 const RecordType *recordType = ty->getAs<RecordType>();
4703 const CXXRecordDecl *classDecl =
4704 cast<CXXRecordDecl>(recordType->getDecl());
4705 return classDecl->getDestructor();
4707 case CFGElement::DeleteDtor: {
4708 const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr();
4709 QualType DTy = DE->getDestroyedType();
4710 DTy = DTy.getNonReferenceType();
4711 const CXXRecordDecl *classDecl =
4712 astContext.getBaseElementType(DTy)->getAsCXXRecordDecl();
4713 return classDecl->getDestructor();
4715 case CFGElement::TemporaryDtor: {
4716 const CXXBindTemporaryExpr *bindExpr =
4717 castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
4718 const CXXTemporary *temp = bindExpr->getTemporary();
4719 return temp->getDestructor();
4721 case CFGElement::BaseDtor:
4722 case CFGElement::MemberDtor:
4723 // Not yet supported.
4726 llvm_unreachable("getKind() returned bogus value");
4729 bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const {
4730 if (const CXXDestructorDecl *DD = getDestructorDecl(astContext))
4731 return DD->isNoReturn();
4735 //===----------------------------------------------------------------------===//
4736 // CFGBlock operations.
4737 //===----------------------------------------------------------------------===//
4739 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable)
4740 : ReachableBlock(IsReachable ? B : nullptr),
4741 UnreachableBlock(!IsReachable ? B : nullptr,
4742 B && IsReachable ? AB_Normal : AB_Unreachable) {}
4744 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock)
4745 : ReachableBlock(B),
4746 UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock,
4747 B == AlternateBlock ? AB_Alternate : AB_Normal) {}
4749 void CFGBlock::addSuccessor(AdjacentBlock Succ,
4750 BumpVectorContext &C) {
4751 if (CFGBlock *B = Succ.getReachableBlock())
4752 B->Preds.push_back(AdjacentBlock(this, Succ.isReachable()), C);
4754 if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock())
4755 UnreachableB->Preds.push_back(AdjacentBlock(this, false), C);
4757 Succs.push_back(Succ, C);
4760 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
4761 const CFGBlock *From, const CFGBlock *To) {
4762 if (F.IgnoreNullPredecessors && !From)
4765 if (To && From && F.IgnoreDefaultsWithCoveredEnums) {
4766 // If the 'To' has no label or is labeled but the label isn't a
4767 // CaseStmt then filter this edge.
4768 if (const SwitchStmt *S =
4769 dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) {
4770 if (S->isAllEnumCasesCovered()) {
4771 const Stmt *L = To->getLabel();
4772 if (!L || !isa<CaseStmt>(L))
4781 //===----------------------------------------------------------------------===//
4782 // CFG pretty printing
4783 //===----------------------------------------------------------------------===//
4787 class StmtPrinterHelper : public PrinterHelper {
4788 using StmtMapTy = llvm::DenseMap<const Stmt *, std::pair<unsigned, unsigned>>;
4789 using DeclMapTy = llvm::DenseMap<const Decl *, std::pair<unsigned, unsigned>>;
4793 signed currentBlock = 0;
4794 unsigned currStmt = 0;
4795 const LangOptions &LangOpts;
4798 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
4800 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
4802 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
4803 BI != BEnd; ++BI, ++j ) {
4804 if (Optional<CFGStmt> SE = BI->getAs<CFGStmt>()) {
4805 const Stmt *stmt= SE->getStmt();
4806 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
4809 switch (stmt->getStmtClass()) {
4810 case Stmt::DeclStmtClass:
4811 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;
4813 case Stmt::IfStmtClass: {
4814 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();
4819 case Stmt::ForStmtClass: {
4820 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();
4825 case Stmt::WhileStmtClass: {
4826 const VarDecl *var =
4827 cast<WhileStmt>(stmt)->getConditionVariable();
4832 case Stmt::SwitchStmtClass: {
4833 const VarDecl *var =
4834 cast<SwitchStmt>(stmt)->getConditionVariable();
4839 case Stmt::CXXCatchStmtClass: {
4840 const VarDecl *var =
4841 cast<CXXCatchStmt>(stmt)->getExceptionDecl();
4854 ~StmtPrinterHelper() override = default;
4856 const LangOptions &getLangOpts() const { return LangOpts; }
4857 void setBlockID(signed i) { currentBlock = i; }
4858 void setStmtID(unsigned i) { currStmt = i; }
4860 bool handledStmt(Stmt *S, raw_ostream &OS) override {
4861 StmtMapTy::iterator I = StmtMap.find(S);
4863 if (I == StmtMap.end())
4866 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
4867 && I->second.second == currStmt) {
4871 OS << "[B" << I->second.first << "." << I->second.second << "]";
4875 bool handleDecl(const Decl *D, raw_ostream &OS) {
4876 DeclMapTy::iterator I = DeclMap.find(D);
4878 if (I == DeclMap.end())
4881 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
4882 && I->second.second == currStmt) {
4886 OS << "[B" << I->second.first << "." << I->second.second << "]";
4891 class CFGBlockTerminatorPrint
4892 : public StmtVisitor<CFGBlockTerminatorPrint,void> {
4894 StmtPrinterHelper* Helper;
4895 PrintingPolicy Policy;
4898 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
4899 const PrintingPolicy &Policy)
4900 : OS(os), Helper(helper), Policy(Policy) {
4901 this->Policy.IncludeNewlines = false;
4904 void VisitIfStmt(IfStmt *I) {
4906 if (Stmt *C = I->getCond())
4907 C->printPretty(OS, Helper, Policy);
4911 void VisitStmt(Stmt *Terminator) {
4912 Terminator->printPretty(OS, Helper, Policy);
4915 void VisitDeclStmt(DeclStmt *DS) {
4916 VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
4917 OS << "static init " << VD->getName();
4920 void VisitForStmt(ForStmt *F) {
4925 if (Stmt *C = F->getCond())
4926 C->printPretty(OS, Helper, Policy);
4933 void VisitWhileStmt(WhileStmt *W) {
4935 if (Stmt *C = W->getCond())
4936 C->printPretty(OS, Helper, Policy);
4939 void VisitDoStmt(DoStmt *D) {
4940 OS << "do ... while ";
4941 if (Stmt *C = D->getCond())
4942 C->printPretty(OS, Helper, Policy);
4945 void VisitSwitchStmt(SwitchStmt *Terminator) {
4947 Terminator->getCond()->printPretty(OS, Helper, Policy);
4950 void VisitCXXTryStmt(CXXTryStmt *CS) {
4954 void VisitSEHTryStmt(SEHTryStmt *CS) {
4958 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
4959 if (Stmt *Cond = C->getCond())
4960 Cond->printPretty(OS, Helper, Policy);
4961 OS << " ? ... : ...";
4964 void VisitChooseExpr(ChooseExpr *C) {
4965 OS << "__builtin_choose_expr( ";
4966 if (Stmt *Cond = C->getCond())
4967 Cond->printPretty(OS, Helper, Policy);
4971 void VisitIndirectGotoStmt(IndirectGotoStmt *I) {
4973 if (Stmt *T = I->getTarget())
4974 T->printPretty(OS, Helper, Policy);
4977 void VisitBinaryOperator(BinaryOperator* B) {
4978 if (!B->isLogicalOp()) {
4984 B->getLHS()->printPretty(OS, Helper, Policy);
4986 switch (B->getOpcode()) {
4994 llvm_unreachable("Invalid logical operator.");
4998 void VisitExpr(Expr *E) {
4999 E->printPretty(OS, Helper, Policy);
5003 void print(CFGTerminator T) {
5004 if (T.isTemporaryDtorsBranch())
5005 OS << "(Temp Dtor) ";
5012 static void print_initializer(raw_ostream &OS, StmtPrinterHelper &Helper,
5013 const CXXCtorInitializer *I) {
5014 if (I->isBaseInitializer())
5015 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
5016 else if (I->isDelegatingInitializer())
5017 OS << I->getTypeSourceInfo()->getType()->getAsCXXRecordDecl()->getName();
5019 OS << I->getAnyMember()->getName();
5021 if (Expr *IE = I->getInit())
5022 IE->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));
5025 if (I->isBaseInitializer())
5026 OS << " (Base initializer)";
5027 else if (I->isDelegatingInitializer())
5028 OS << " (Delegating initializer)";
5030 OS << " (Member initializer)";
5033 static void print_construction_context(raw_ostream &OS,
5034 StmtPrinterHelper &Helper,
5035 const ConstructionContext *CC) {
5036 SmallVector<const Stmt *, 3> Stmts;
5037 switch (CC->getKind()) {
5038 case ConstructionContext::SimpleConstructorInitializerKind: {
5040 const auto *SICC = cast<SimpleConstructorInitializerConstructionContext>(CC);
5041 print_initializer(OS, Helper, SICC->getCXXCtorInitializer());
5044 case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind: {
5047 cast<CXX17ElidedCopyConstructorInitializerConstructionContext>(CC);
5048 print_initializer(OS, Helper, CICC->getCXXCtorInitializer());
5049 Stmts.push_back(CICC->getCXXBindTemporaryExpr());
5052 case ConstructionContext::SimpleVariableKind: {
5053 const auto *SDSCC = cast<SimpleVariableConstructionContext>(CC);
5054 Stmts.push_back(SDSCC->getDeclStmt());
5057 case ConstructionContext::CXX17ElidedCopyVariableKind: {
5058 const auto *CDSCC = cast<CXX17ElidedCopyVariableConstructionContext>(CC);
5059 Stmts.push_back(CDSCC->getDeclStmt());
5060 Stmts.push_back(CDSCC->getCXXBindTemporaryExpr());
5063 case ConstructionContext::NewAllocatedObjectKind: {
5064 const auto *NECC = cast<NewAllocatedObjectConstructionContext>(CC);
5065 Stmts.push_back(NECC->getCXXNewExpr());
5068 case ConstructionContext::SimpleReturnedValueKind: {
5069 const auto *RSCC = cast<SimpleReturnedValueConstructionContext>(CC);
5070 Stmts.push_back(RSCC->getReturnStmt());
5073 case ConstructionContext::CXX17ElidedCopyReturnedValueKind: {
5075 cast<CXX17ElidedCopyReturnedValueConstructionContext>(CC);
5076 Stmts.push_back(RSCC->getReturnStmt());
5077 Stmts.push_back(RSCC->getCXXBindTemporaryExpr());
5080 case ConstructionContext::SimpleTemporaryObjectKind: {
5081 const auto *TOCC = cast<SimpleTemporaryObjectConstructionContext>(CC);
5082 Stmts.push_back(TOCC->getCXXBindTemporaryExpr());
5083 Stmts.push_back(TOCC->getMaterializedTemporaryExpr());
5086 case ConstructionContext::ElidedTemporaryObjectKind: {
5087 const auto *TOCC = cast<ElidedTemporaryObjectConstructionContext>(CC);
5088 Stmts.push_back(TOCC->getCXXBindTemporaryExpr());
5089 Stmts.push_back(TOCC->getMaterializedTemporaryExpr());
5090 Stmts.push_back(TOCC->getConstructorAfterElision());
5093 case ConstructionContext::ArgumentKind: {
5094 const auto *ACC = cast<ArgumentConstructionContext>(CC);
5095 if (const Stmt *BTE = ACC->getCXXBindTemporaryExpr()) {
5097 Helper.handledStmt(const_cast<Stmt *>(BTE), OS);
5100 Helper.handledStmt(const_cast<Expr *>(ACC->getCallLikeExpr()), OS);
5101 OS << "+" << ACC->getIndex();
5108 Helper.handledStmt(const_cast<Stmt *>(I), OS);
5112 static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
5113 const CFGElement &E) {
5114 if (Optional<CFGStmt> CS = E.getAs<CFGStmt>()) {
5115 const Stmt *S = CS->getStmt();
5116 assert(S != nullptr && "Expecting non-null Stmt");
5118 // special printing for statement-expressions.
5119 if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) {
5120 const CompoundStmt *Sub = SE->getSubStmt();
5122 auto Children = Sub->children();
5123 if (Children.begin() != Children.end()) {
5125 Helper.handledStmt(*SE->getSubStmt()->body_rbegin(),OS);
5130 // special printing for comma expressions.
5131 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
5132 if (B->getOpcode() == BO_Comma) {
5134 Helper.handledStmt(B->getRHS(),OS);
5139 S->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));
5141 if (auto VTC = E.getAs<CFGCXXRecordTypedCall>()) {
5142 if (isa<CXXOperatorCallExpr>(S))
5143 OS << " (OperatorCall)";
5144 OS << " (CXXRecordTypedCall";
5145 print_construction_context(OS, Helper, VTC->getConstructionContext());
5147 } else if (isa<CXXOperatorCallExpr>(S)) {
5148 OS << " (OperatorCall)";
5149 } else if (isa<CXXBindTemporaryExpr>(S)) {
5150 OS << " (BindTemporary)";
5151 } else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) {
5152 OS << " (CXXConstructExpr";
5153 if (Optional<CFGConstructor> CE = E.getAs<CFGConstructor>()) {
5154 print_construction_context(OS, Helper, CE->getConstructionContext());
5156 OS << ", " << CCE->getType().getAsString() << ")";
5157 } else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) {
5158 OS << " (" << CE->getStmtClassName() << ", "
5159 << CE->getCastKindName()
5160 << ", " << CE->getType().getAsString()
5164 // Expressions need a newline.
5167 } else if (Optional<CFGInitializer> IE = E.getAs<CFGInitializer>()) {
5168 print_initializer(OS, Helper, IE->getInitializer());
5170 } else if (Optional<CFGAutomaticObjDtor> DE =
5171 E.getAs<CFGAutomaticObjDtor>()) {
5172 const VarDecl *VD = DE->getVarDecl();
5173 Helper.handleDecl(VD, OS);
5175 ASTContext &ACtx = VD->getASTContext();
5176 QualType T = VD->getType();
5177 if (T->isReferenceType())
5178 T = getReferenceInitTemporaryType(VD->getInit(), nullptr);
5179 if (const ArrayType *AT = ACtx.getAsArrayType(T))
5180 T = ACtx.getBaseElementType(AT);
5182 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()";
5183 OS << " (Implicit destructor)\n";
5184 } else if (Optional<CFGLifetimeEnds> DE = E.getAs<CFGLifetimeEnds>()) {
5185 const VarDecl *VD = DE->getVarDecl();
5186 Helper.handleDecl(VD, OS);
5188 OS << " (Lifetime ends)\n";
5189 } else if (Optional<CFGLoopExit> LE = E.getAs<CFGLoopExit>()) {
5190 const Stmt *LoopStmt = LE->getLoopStmt();
5191 OS << LoopStmt->getStmtClassName() << " (LoopExit)\n";
5192 } else if (Optional<CFGScopeBegin> SB = E.getAs<CFGScopeBegin>()) {
5193 OS << "CFGScopeBegin(";
5194 if (const VarDecl *VD = SB->getVarDecl())
5195 OS << VD->getQualifiedNameAsString();
5197 } else if (Optional<CFGScopeEnd> SE = E.getAs<CFGScopeEnd>()) {
5198 OS << "CFGScopeEnd(";
5199 if (const VarDecl *VD = SE->getVarDecl())
5200 OS << VD->getQualifiedNameAsString();
5202 } else if (Optional<CFGNewAllocator> NE = E.getAs<CFGNewAllocator>()) {
5203 OS << "CFGNewAllocator(";
5204 if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr())
5205 AllocExpr->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
5207 } else if (Optional<CFGDeleteDtor> DE = E.getAs<CFGDeleteDtor>()) {
5208 const CXXRecordDecl *RD = DE->getCXXRecordDecl();
5211 CXXDeleteExpr *DelExpr =
5212 const_cast<CXXDeleteExpr*>(DE->getDeleteExpr());
5213 Helper.handledStmt(cast<Stmt>(DelExpr->getArgument()), OS);
5214 OS << "->~" << RD->getName().str() << "()";
5215 OS << " (Implicit destructor)\n";
5216 } else if (Optional<CFGBaseDtor> BE = E.getAs<CFGBaseDtor>()) {
5217 const CXXBaseSpecifier *BS = BE->getBaseSpecifier();
5218 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
5219 OS << " (Base object destructor)\n";
5220 } else if (Optional<CFGMemberDtor> ME = E.getAs<CFGMemberDtor>()) {
5221 const FieldDecl *FD = ME->getFieldDecl();
5222 const Type *T = FD->getType()->getBaseElementTypeUnsafe();
5223 OS << "this->" << FD->getName();
5224 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
5225 OS << " (Member object destructor)\n";
5226 } else if (Optional<CFGTemporaryDtor> TE = E.getAs<CFGTemporaryDtor>()) {
5227 const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr();
5229 BT->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
5230 OS << "() (Temporary object destructor)\n";
5234 static void print_block(raw_ostream &OS, const CFG* cfg,
5236 StmtPrinterHelper &Helper, bool print_edges,
5238 Helper.setBlockID(B.getBlockID());
5240 // Print the header.
5242 OS.changeColor(raw_ostream::YELLOW, true);
5244 OS << "\n [B" << B.getBlockID();
5246 if (&B == &cfg->getEntry())
5247 OS << " (ENTRY)]\n";
5248 else if (&B == &cfg->getExit())
5250 else if (&B == cfg->getIndirectGotoBlock())
5251 OS << " (INDIRECT GOTO DISPATCH)]\n";
5252 else if (B.hasNoReturnElement())
5253 OS << " (NORETURN)]\n";
5260 // Print the label of this block.
5261 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {
5265 if (LabelStmt *L = dyn_cast<LabelStmt>(Label))
5267 else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
5270 C->getLHS()->printPretty(OS, &Helper,
5271 PrintingPolicy(Helper.getLangOpts()));
5274 C->getRHS()->printPretty(OS, &Helper,
5275 PrintingPolicy(Helper.getLangOpts()));
5277 } else if (isa<DefaultStmt>(Label))
5279 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) {
5281 if (CS->getExceptionDecl())
5282 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper.getLangOpts()),
5287 } else if (SEHExceptStmt *ES = dyn_cast<SEHExceptStmt>(Label)) {
5289 ES->getFilterExpr()->printPretty(OS, &Helper,
5290 PrintingPolicy(Helper.getLangOpts()), 0);
5293 llvm_unreachable("Invalid label statement in CFGBlock.");
5298 // Iterate through the statements in the block and print them.
5301 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
5302 I != E ; ++I, ++j ) {
5303 // Print the statement # in the basic block and the statement itself.
5307 OS << llvm::format("%3d", j) << ": ";
5309 Helper.setStmtID(j);
5311 print_elem(OS, Helper, *I);
5314 // Print the terminator of this block.
5315 if (B.getTerminator()) {
5317 OS.changeColor(raw_ostream::GREEN);
5321 Helper.setBlockID(-1);
5323 PrintingPolicy PP(Helper.getLangOpts());
5324 CFGBlockTerminatorPrint TPrinter(OS, &Helper, PP);
5325 TPrinter.print(B.getTerminator());
5333 // Print the predecessors of this block.
5334 if (!B.pred_empty()) {
5335 const raw_ostream::Colors Color = raw_ostream::BLUE;
5337 OS.changeColor(Color);
5341 OS << '(' << B.pred_size() << "):";
5345 OS.changeColor(Color);
5347 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
5353 bool Reachable = true;
5356 B = I->getPossiblyUnreachableBlock();
5359 OS << " B" << B->getBlockID();
5361 OS << "(Unreachable)";
5370 // Print the successors of this block.
5371 if (!B.succ_empty()) {
5372 const raw_ostream::Colors Color = raw_ostream::MAGENTA;
5374 OS.changeColor(Color);
5378 OS << '(' << B.succ_size() << "):";
5382 OS.changeColor(Color);
5384 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
5391 bool Reachable = true;
5394 B = I->getPossiblyUnreachableBlock();
5398 OS << " B" << B->getBlockID();
5400 OS << "(Unreachable)";
5414 /// dump - A simple pretty printer of a CFG that outputs to stderr.
5415 void CFG::dump(const LangOptions &LO, bool ShowColors) const {
5416 print(llvm::errs(), LO, ShowColors);
5419 /// print - A simple pretty printer of a CFG that outputs to an ostream.
5420 void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
5421 StmtPrinterHelper Helper(this, LO);
5423 // Print the entry block.
5424 print_block(OS, this, getEntry(), Helper, true, ShowColors);
5426 // Iterate through the CFGBlocks and print them one by one.
5427 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
5428 // Skip the entry block, because we already printed it.
5429 if (&(**I) == &getEntry() || &(**I) == &getExit())
5432 print_block(OS, this, **I, Helper, true, ShowColors);
5435 // Print the exit block.
5436 print_block(OS, this, getExit(), Helper, true, ShowColors);
5441 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
5442 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
5443 bool ShowColors) const {
5444 print(llvm::errs(), cfg, LO, ShowColors);
5447 LLVM_DUMP_METHOD void CFGBlock::dump() const {
5448 dump(getParent(), LangOptions(), false);
5451 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
5452 /// Generally this will only be called from CFG::print.
5453 void CFGBlock::print(raw_ostream &OS, const CFG* cfg,
5454 const LangOptions &LO, bool ShowColors) const {
5455 StmtPrinterHelper Helper(cfg, LO);
5456 print_block(OS, cfg, *this, Helper, true, ShowColors);
5460 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
5461 void CFGBlock::printTerminator(raw_ostream &OS,
5462 const LangOptions &LO) const {
5463 CFGBlockTerminatorPrint TPrinter(OS, nullptr, PrintingPolicy(LO));
5464 TPrinter.print(getTerminator());
5467 Stmt *CFGBlock::getTerminatorCondition(bool StripParens) {
5468 Stmt *Terminator = this->Terminator;
5474 switch (Terminator->getStmtClass()) {
5478 case Stmt::CXXForRangeStmtClass:
5479 E = cast<CXXForRangeStmt>(Terminator)->getCond();
5482 case Stmt::ForStmtClass:
5483 E = cast<ForStmt>(Terminator)->getCond();
5486 case Stmt::WhileStmtClass:
5487 E = cast<WhileStmt>(Terminator)->getCond();
5490 case Stmt::DoStmtClass:
5491 E = cast<DoStmt>(Terminator)->getCond();
5494 case Stmt::IfStmtClass:
5495 E = cast<IfStmt>(Terminator)->getCond();
5498 case Stmt::ChooseExprClass:
5499 E = cast<ChooseExpr>(Terminator)->getCond();
5502 case Stmt::IndirectGotoStmtClass:
5503 E = cast<IndirectGotoStmt>(Terminator)->getTarget();
5506 case Stmt::SwitchStmtClass:
5507 E = cast<SwitchStmt>(Terminator)->getCond();
5510 case Stmt::BinaryConditionalOperatorClass:
5511 E = cast<BinaryConditionalOperator>(Terminator)->getCond();
5514 case Stmt::ConditionalOperatorClass:
5515 E = cast<ConditionalOperator>(Terminator)->getCond();
5518 case Stmt::BinaryOperatorClass: // '&&' and '||'
5519 E = cast<BinaryOperator>(Terminator)->getLHS();
5522 case Stmt::ObjCForCollectionStmtClass:
5529 return E ? E->IgnoreParens() : nullptr;
5532 //===----------------------------------------------------------------------===//
5533 // CFG Graphviz Visualization
5534 //===----------------------------------------------------------------------===//
5537 static StmtPrinterHelper* GraphHelper;
5540 void CFG::viewCFG(const LangOptions &LO) const {
5542 StmtPrinterHelper H(this, LO);
5544 llvm::ViewGraph(this,"CFG");
5545 GraphHelper = nullptr;
5552 struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
5553 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
5555 static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) {
5557 std::string OutSStr;
5558 llvm::raw_string_ostream Out(OutSStr);
5559 print_block(Out,Graph, *Node, *GraphHelper, false, false);
5560 std::string& OutStr = Out.str();
5562 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
5564 // Process string output to make it nicer...
5565 for (unsigned i = 0; i != OutStr.length(); ++i)
5566 if (OutStr[i] == '\n') { // Left justify
5568 OutStr.insert(OutStr.begin()+i+1, 'l');