• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines the CFG and CFGBuilder classes for representing and
11 //  building Control-Flow Graphs (CFGs) from ASTs.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/Analysis/CFG.h"
16 #include "clang/AST/ASTContext.h"
17 #include "clang/AST/Attr.h"
18 #include "clang/AST/CharUnits.h"
19 #include "clang/AST/DeclCXX.h"
20 #include "clang/AST/PrettyPrinter.h"
21 #include "clang/AST/StmtVisitor.h"
22 #include "clang/Basic/Builtins.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include <memory>
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/Support/Allocator.h"
27 #include "llvm/Support/Format.h"
28 #include "llvm/Support/GraphWriter.h"
29 #include "llvm/Support/SaveAndRestore.h"
30 
31 using namespace clang;
32 
33 namespace {
34 
GetEndLoc(Decl * D)35 static SourceLocation GetEndLoc(Decl *D) {
36   if (VarDecl *VD = dyn_cast<VarDecl>(D))
37     if (Expr *Ex = VD->getInit())
38       return Ex->getSourceRange().getEnd();
39   return D->getLocation();
40 }
41 
42 /// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral
43 /// or EnumConstantDecl from the given Expr. If it fails, returns nullptr.
tryTransformToIntOrEnumConstant(const Expr * E)44 const Expr *tryTransformToIntOrEnumConstant(const Expr *E) {
45   E = E->IgnoreParens();
46   if (isa<IntegerLiteral>(E))
47     return E;
48   if (auto *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts()))
49     return isa<EnumConstantDecl>(DR->getDecl()) ? DR : nullptr;
50   return nullptr;
51 }
52 
53 /// Tries to interpret a binary operator into `Decl Op Expr` form, if Expr is
54 /// an integer literal or an enum constant.
55 ///
56 /// If this fails, at least one of the returned DeclRefExpr or Expr will be
57 /// null.
58 static std::tuple<const DeclRefExpr *, BinaryOperatorKind, const Expr *>
tryNormalizeBinaryOperator(const BinaryOperator * B)59 tryNormalizeBinaryOperator(const BinaryOperator *B) {
60   BinaryOperatorKind Op = B->getOpcode();
61 
62   const Expr *MaybeDecl = B->getLHS();
63   const Expr *Constant = tryTransformToIntOrEnumConstant(B->getRHS());
64   // Expr looked like `0 == Foo` instead of `Foo == 0`
65   if (Constant == nullptr) {
66     // Flip the operator
67     if (Op == BO_GT)
68       Op = BO_LT;
69     else if (Op == BO_GE)
70       Op = BO_LE;
71     else if (Op == BO_LT)
72       Op = BO_GT;
73     else if (Op == BO_LE)
74       Op = BO_GE;
75 
76     MaybeDecl = B->getRHS();
77     Constant = tryTransformToIntOrEnumConstant(B->getLHS());
78   }
79 
80   auto *D = dyn_cast<DeclRefExpr>(MaybeDecl->IgnoreParenImpCasts());
81   return std::make_tuple(D, Op, Constant);
82 }
83 
84 /// For an expression `x == Foo && x == Bar`, this determines whether the
85 /// `Foo` and `Bar` are either of the same enumeration type, or both integer
86 /// literals.
87 ///
88 /// It's an error to pass this arguments that are not either IntegerLiterals
89 /// or DeclRefExprs (that have decls of type EnumConstantDecl)
areExprTypesCompatible(const Expr * E1,const Expr * E2)90 static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) {
91   // User intent isn't clear if they're mixing int literals with enum
92   // constants.
93   if (isa<IntegerLiteral>(E1) != isa<IntegerLiteral>(E2))
94     return false;
95 
96   // Integer literal comparisons, regardless of literal type, are acceptable.
97   if (isa<IntegerLiteral>(E1))
98     return true;
99 
100   // IntegerLiterals are handled above and only EnumConstantDecls are expected
101   // beyond this point
102   assert(isa<DeclRefExpr>(E1) && isa<DeclRefExpr>(E2));
103   auto *Decl1 = cast<DeclRefExpr>(E1)->getDecl();
104   auto *Decl2 = cast<DeclRefExpr>(E2)->getDecl();
105 
106   assert(isa<EnumConstantDecl>(Decl1) && isa<EnumConstantDecl>(Decl2));
107   const DeclContext *DC1 = Decl1->getDeclContext();
108   const DeclContext *DC2 = Decl2->getDeclContext();
109 
110   assert(isa<EnumDecl>(DC1) && isa<EnumDecl>(DC2));
111   return DC1 == DC2;
112 }
113 
114 class CFGBuilder;
115 
116 /// The CFG builder uses a recursive algorithm to build the CFG.  When
117 ///  we process an expression, sometimes we know that we must add the
118 ///  subexpressions as block-level expressions.  For example:
119 ///
120 ///    exp1 || exp2
121 ///
122 ///  When processing the '||' expression, we know that exp1 and exp2
123 ///  need to be added as block-level expressions, even though they
124 ///  might not normally need to be.  AddStmtChoice records this
125 ///  contextual information.  If AddStmtChoice is 'NotAlwaysAdd', then
126 ///  the builder has an option not to add a subexpression as a
127 ///  block-level expression.
128 ///
129 class AddStmtChoice {
130 public:
131   enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };
132 
AddStmtChoice(Kind a_kind=NotAlwaysAdd)133   AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}
134 
135   bool alwaysAdd(CFGBuilder &builder,
136                  const Stmt *stmt) const;
137 
138   /// Return a copy of this object, except with the 'always-add' bit
139   ///  set as specified.
withAlwaysAdd(bool alwaysAdd) const140   AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {
141     return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd);
142   }
143 
144 private:
145   Kind kind;
146 };
147 
148 /// LocalScope - Node in tree of local scopes created for C++ implicit
149 /// destructor calls generation. It contains list of automatic variables
150 /// declared in the scope and link to position in previous scope this scope
151 /// began in.
152 ///
153 /// The process of creating local scopes is as follows:
154 /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
155 /// - Before processing statements in scope (e.g. CompoundStmt) create
156 ///   LocalScope object using CFGBuilder::ScopePos as link to previous scope
157 ///   and set CFGBuilder::ScopePos to the end of new scope,
158 /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
159 ///   at this VarDecl,
160 /// - For every normal (without jump) end of scope add to CFGBlock destructors
161 ///   for objects in the current scope,
162 /// - For every jump add to CFGBlock destructors for objects
163 ///   between CFGBuilder::ScopePos and local scope position saved for jump
164 ///   target. Thanks to C++ restrictions on goto jumps we can be sure that
165 ///   jump target position will be on the path to root from CFGBuilder::ScopePos
166 ///   (adding any variable that doesn't need constructor to be called to
167 ///   LocalScope can break this assumption),
168 ///
169 class LocalScope {
170 public:
171   typedef BumpVector<VarDecl*> AutomaticVarsTy;
172 
173   /// const_iterator - Iterates local scope backwards and jumps to previous
174   /// scope on reaching the beginning of currently iterated scope.
175   class const_iterator {
176     const LocalScope* Scope;
177 
178     /// VarIter is guaranteed to be greater then 0 for every valid iterator.
179     /// Invalid iterator (with null Scope) has VarIter equal to 0.
180     unsigned VarIter;
181 
182   public:
183     /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
184     /// Incrementing invalid iterator is allowed and will result in invalid
185     /// iterator.
const_iterator()186     const_iterator()
187         : Scope(nullptr), VarIter(0) {}
188 
189     /// Create valid iterator. In case when S.Prev is an invalid iterator and
190     /// I is equal to 0, this will create invalid iterator.
const_iterator(const LocalScope & S,unsigned I)191     const_iterator(const LocalScope& S, unsigned I)
192         : Scope(&S), VarIter(I) {
193       // Iterator to "end" of scope is not allowed. Handle it by going up
194       // in scopes tree possibly up to invalid iterator in the root.
195       if (VarIter == 0 && Scope)
196         *this = Scope->Prev;
197     }
198 
operator ->() const199     VarDecl *const* operator->() const {
200       assert (Scope && "Dereferencing invalid iterator is not allowed");
201       assert (VarIter != 0 && "Iterator has invalid value of VarIter member");
202       return &Scope->Vars[VarIter - 1];
203     }
operator *() const204     VarDecl *operator*() const {
205       return *this->operator->();
206     }
207 
operator ++()208     const_iterator &operator++() {
209       if (!Scope)
210         return *this;
211 
212       assert (VarIter != 0 && "Iterator has invalid value of VarIter member");
213       --VarIter;
214       if (VarIter == 0)
215         *this = Scope->Prev;
216       return *this;
217     }
operator ++(int)218     const_iterator operator++(int) {
219       const_iterator P = *this;
220       ++*this;
221       return P;
222     }
223 
operator ==(const const_iterator & rhs) const224     bool operator==(const const_iterator &rhs) const {
225       return Scope == rhs.Scope && VarIter == rhs.VarIter;
226     }
operator !=(const const_iterator & rhs) const227     bool operator!=(const const_iterator &rhs) const {
228       return !(*this == rhs);
229     }
230 
operator bool() const231     explicit operator bool() const {
232       return *this != const_iterator();
233     }
234 
235     int distance(const_iterator L);
236   };
237 
238   friend class const_iterator;
239 
240 private:
241   BumpVectorContext ctx;
242 
243   /// Automatic variables in order of declaration.
244   AutomaticVarsTy Vars;
245   /// Iterator to variable in previous scope that was declared just before
246   /// begin of this scope.
247   const_iterator Prev;
248 
249 public:
250   /// Constructs empty scope linked to previous scope in specified place.
LocalScope(BumpVectorContext ctx,const_iterator P)251   LocalScope(BumpVectorContext ctx, const_iterator P)
252       : ctx(std::move(ctx)), Vars(this->ctx, 4), Prev(P) {}
253 
254   /// Begin of scope in direction of CFG building (backwards).
begin() const255   const_iterator begin() const { return const_iterator(*this, Vars.size()); }
256 
addVar(VarDecl * VD)257   void addVar(VarDecl *VD) {
258     Vars.push_back(VD, ctx);
259   }
260 };
261 
262 /// distance - Calculates distance from this to L. L must be reachable from this
263 /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
264 /// number of scopes between this and L.
distance(LocalScope::const_iterator L)265 int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
266   int D = 0;
267   const_iterator F = *this;
268   while (F.Scope != L.Scope) {
269     assert (F != const_iterator()
270         && "L iterator is not reachable from F iterator.");
271     D += F.VarIter;
272     F = F.Scope->Prev;
273   }
274   D += F.VarIter - L.VarIter;
275   return D;
276 }
277 
278 /// Structure for specifying position in CFG during its build process. It
279 /// consists of CFGBlock that specifies position in CFG and
280 /// LocalScope::const_iterator that specifies position in LocalScope graph.
281 struct BlockScopePosPair {
BlockScopePosPair__anon83acd1880111::BlockScopePosPair282   BlockScopePosPair() : block(nullptr) {}
BlockScopePosPair__anon83acd1880111::BlockScopePosPair283   BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos)
284       : block(b), scopePosition(scopePos) {}
285 
286   CFGBlock *block;
287   LocalScope::const_iterator scopePosition;
288 };
289 
290 /// TryResult - a class representing a variant over the values
291 ///  'true', 'false', or 'unknown'.  This is returned by tryEvaluateBool,
292 ///  and is used by the CFGBuilder to decide if a branch condition
293 ///  can be decided up front during CFG construction.
294 class TryResult {
295   int X;
296 public:
TryResult(bool b)297   TryResult(bool b) : X(b ? 1 : 0) {}
TryResult()298   TryResult() : X(-1) {}
299 
isTrue() const300   bool isTrue() const { return X == 1; }
isFalse() const301   bool isFalse() const { return X == 0; }
isKnown() const302   bool isKnown() const { return X >= 0; }
negate()303   void negate() {
304     assert(isKnown());
305     X ^= 0x1;
306   }
307 };
308 
bothKnownTrue(TryResult R1,TryResult R2)309 TryResult bothKnownTrue(TryResult R1, TryResult R2) {
310   if (!R1.isKnown() || !R2.isKnown())
311     return TryResult();
312   return TryResult(R1.isTrue() && R2.isTrue());
313 }
314 
315 class reverse_children {
316   llvm::SmallVector<Stmt *, 12> childrenBuf;
317   ArrayRef<Stmt*> children;
318 public:
319   reverse_children(Stmt *S);
320 
321   typedef ArrayRef<Stmt*>::reverse_iterator iterator;
begin() const322   iterator begin() const { return children.rbegin(); }
end() const323   iterator end() const { return children.rend(); }
324 };
325 
326 
reverse_children(Stmt * S)327 reverse_children::reverse_children(Stmt *S) {
328   if (CallExpr *CE = dyn_cast<CallExpr>(S)) {
329     children = CE->getRawSubExprs();
330     return;
331   }
332   switch (S->getStmtClass()) {
333     // Note: Fill in this switch with more cases we want to optimize.
334     case Stmt::InitListExprClass: {
335       InitListExpr *IE = cast<InitListExpr>(S);
336       children = llvm::makeArrayRef(reinterpret_cast<Stmt**>(IE->getInits()),
337                                     IE->getNumInits());
338       return;
339     }
340     default:
341       break;
342   }
343 
344   // Default case for all other statements.
345   for (Stmt *SubStmt : S->children())
346     childrenBuf.push_back(SubStmt);
347 
348   // This needs to be done *after* childrenBuf has been populated.
349   children = childrenBuf;
350 }
351 
352 /// CFGBuilder - This class implements CFG construction from an AST.
353 ///   The builder is stateful: an instance of the builder should be used to only
354 ///   construct a single CFG.
355 ///
356 ///   Example usage:
357 ///
358 ///     CFGBuilder builder;
359 ///     std::unique_ptr<CFG> cfg = builder.buildCFG(decl, stmt1);
360 ///
361 ///  CFG construction is done via a recursive walk of an AST.  We actually parse
362 ///  the AST in reverse order so that the successor of a basic block is
363 ///  constructed prior to its predecessor.  This allows us to nicely capture
364 ///  implicit fall-throughs without extra basic blocks.
365 ///
366 class CFGBuilder {
367   typedef BlockScopePosPair JumpTarget;
368   typedef BlockScopePosPair JumpSource;
369 
370   ASTContext *Context;
371   std::unique_ptr<CFG> cfg;
372 
373   CFGBlock *Block;
374   CFGBlock *Succ;
375   JumpTarget ContinueJumpTarget;
376   JumpTarget BreakJumpTarget;
377   CFGBlock *SwitchTerminatedBlock;
378   CFGBlock *DefaultCaseBlock;
379   CFGBlock *TryTerminatedBlock;
380 
381   // Current position in local scope.
382   LocalScope::const_iterator ScopePos;
383 
384   // LabelMap records the mapping from Label expressions to their jump targets.
385   typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy;
386   LabelMapTy LabelMap;
387 
388   // A list of blocks that end with a "goto" that must be backpatched to their
389   // resolved targets upon completion of CFG construction.
390   typedef std::vector<JumpSource> BackpatchBlocksTy;
391   BackpatchBlocksTy BackpatchBlocks;
392 
393   // A list of labels whose address has been taken (for indirect gotos).
394   typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy;
395   LabelSetTy AddressTakenLabels;
396 
397   bool badCFG;
398   const CFG::BuildOptions &BuildOpts;
399 
400   // State to track for building switch statements.
401   bool switchExclusivelyCovered;
402   Expr::EvalResult *switchCond;
403 
404   CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry;
405   const Stmt *lastLookup;
406 
407   // Caches boolean evaluations of expressions to avoid multiple re-evaluations
408   // during construction of branches for chained logical operators.
409   typedef llvm::DenseMap<Expr *, TryResult> CachedBoolEvalsTy;
410   CachedBoolEvalsTy CachedBoolEvals;
411 
412 public:
CFGBuilder(ASTContext * astContext,const CFG::BuildOptions & buildOpts)413   explicit CFGBuilder(ASTContext *astContext,
414                       const CFG::BuildOptions &buildOpts)
415     : Context(astContext), cfg(new CFG()), // crew a new CFG
416       Block(nullptr), Succ(nullptr),
417       SwitchTerminatedBlock(nullptr), DefaultCaseBlock(nullptr),
418       TryTerminatedBlock(nullptr), badCFG(false), BuildOpts(buildOpts),
419       switchExclusivelyCovered(false), switchCond(nullptr),
420       cachedEntry(nullptr), lastLookup(nullptr) {}
421 
422   // buildCFG - Used by external clients to construct the CFG.
423   std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement);
424 
425   bool alwaysAdd(const Stmt *stmt);
426 
427 private:
428   // Visitors to walk an AST and construct the CFG.
429   CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
430   CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);
431   CFGBlock *VisitBreakStmt(BreakStmt *B);
432   CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);
433   CFGBlock *VisitCaseStmt(CaseStmt *C);
434   CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);
435   CFGBlock *VisitCompoundStmt(CompoundStmt *C);
436   CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,
437                                      AddStmtChoice asc);
438   CFGBlock *VisitContinueStmt(ContinueStmt *C);
439   CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
440                                       AddStmtChoice asc);
441   CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
442   CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
443   CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc);
444   CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc);
445   CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
446   CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
447                                        AddStmtChoice asc);
448   CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
449                                         AddStmtChoice asc);
450   CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);
451   CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);
452   CFGBlock *VisitDeclStmt(DeclStmt *DS);
453   CFGBlock *VisitDeclSubExpr(DeclStmt *DS);
454   CFGBlock *VisitDefaultStmt(DefaultStmt *D);
455   CFGBlock *VisitDoStmt(DoStmt *D);
456   CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, AddStmtChoice asc);
457   CFGBlock *VisitForStmt(ForStmt *F);
458   CFGBlock *VisitGotoStmt(GotoStmt *G);
459   CFGBlock *VisitIfStmt(IfStmt *I);
460   CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);
461   CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);
462   CFGBlock *VisitLabelStmt(LabelStmt *L);
463   CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc);
464   CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc);
465   CFGBlock *VisitLogicalOperator(BinaryOperator *B);
466   std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B,
467                                                          Stmt *Term,
468                                                          CFGBlock *TrueBlock,
469                                                          CFGBlock *FalseBlock);
470   CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);
471   CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);
472   CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
473   CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
474   CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);
475   CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S);
476   CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);
477   CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E);
478   CFGBlock *VisitReturnStmt(ReturnStmt *R);
479   CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
480   CFGBlock *VisitSwitchStmt(SwitchStmt *S);
481   CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
482                                           AddStmtChoice asc);
483   CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
484   CFGBlock *VisitWhileStmt(WhileStmt *W);
485 
486   CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd);
487   CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
488   CFGBlock *VisitChildren(Stmt *S);
489   CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc);
490 
491   /// When creating the CFG for temporary destructors, we want to mirror the
492   /// branch structure of the corresponding constructor calls.
493   /// Thus, while visiting a statement for temporary destructors, we keep a
494   /// context to keep track of the following information:
495   /// - whether a subexpression is executed unconditionally
496   /// - if a subexpression is executed conditionally, the first
497   ///   CXXBindTemporaryExpr we encounter in that subexpression (which
498   ///   corresponds to the last temporary destructor we have to call for this
499   ///   subexpression) and the CFG block at that point (which will become the
500   ///   successor block when inserting the decision point).
501   ///
502   /// That way, we can build the branch structure for temporary destructors as
503   /// follows:
504   /// 1. If a subexpression is executed unconditionally, we add the temporary
505   ///    destructor calls to the current block.
506   /// 2. If a subexpression is executed conditionally, when we encounter a
507   ///    CXXBindTemporaryExpr:
508   ///    a) If it is the first temporary destructor call in the subexpression,
509   ///       we remember the CXXBindTemporaryExpr and the current block in the
510   ///       TempDtorContext; we start a new block, and insert the temporary
511   ///       destructor call.
512   ///    b) Otherwise, add the temporary destructor call to the current block.
513   ///  3. When we finished visiting a conditionally executed subexpression,
514   ///     and we found at least one temporary constructor during the visitation
515   ///     (2.a has executed), we insert a decision block that uses the
516   ///     CXXBindTemporaryExpr as terminator, and branches to the current block
517   ///     if the CXXBindTemporaryExpr was marked executed, and otherwise
518   ///     branches to the stored successor.
519   struct TempDtorContext {
TempDtorContext__anon83acd1880111::CFGBuilder::TempDtorContext520     TempDtorContext()
521         : IsConditional(false), KnownExecuted(true), Succ(nullptr),
522           TerminatorExpr(nullptr) {}
523 
TempDtorContext__anon83acd1880111::CFGBuilder::TempDtorContext524     TempDtorContext(TryResult KnownExecuted)
525         : IsConditional(true), KnownExecuted(KnownExecuted), Succ(nullptr),
526           TerminatorExpr(nullptr) {}
527 
528     /// Returns whether we need to start a new branch for a temporary destructor
529     /// call. This is the case when the temporary destructor is
530     /// conditionally executed, and it is the first one we encounter while
531     /// visiting a subexpression - other temporary destructors at the same level
532     /// will be added to the same block and are executed under the same
533     /// condition.
needsTempDtorBranch__anon83acd1880111::CFGBuilder::TempDtorContext534     bool needsTempDtorBranch() const {
535       return IsConditional && !TerminatorExpr;
536     }
537 
538     /// Remember the successor S of a temporary destructor decision branch for
539     /// the corresponding CXXBindTemporaryExpr E.
setDecisionPoint__anon83acd1880111::CFGBuilder::TempDtorContext540     void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) {
541       Succ = S;
542       TerminatorExpr = E;
543     }
544 
545     const bool IsConditional;
546     const TryResult KnownExecuted;
547     CFGBlock *Succ;
548     CXXBindTemporaryExpr *TerminatorExpr;
549   };
550 
551   // Visitors to walk an AST and generate destructors of temporaries in
552   // full expression.
553   CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary,
554                                    TempDtorContext &Context);
555   CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E, TempDtorContext &Context);
556   CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E,
557                                                  TempDtorContext &Context);
558   CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(
559       CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context);
560   CFGBlock *VisitConditionalOperatorForTemporaryDtors(
561       AbstractConditionalOperator *E, bool BindToTemporary,
562       TempDtorContext &Context);
563   void InsertTempDtorDecisionBlock(const TempDtorContext &Context,
564                                    CFGBlock *FalseSucc = nullptr);
565 
566   // NYS == Not Yet Supported
NYS()567   CFGBlock *NYS() {
568     badCFG = true;
569     return Block;
570   }
571 
autoCreateBlock()572   void autoCreateBlock() { if (!Block) Block = createBlock(); }
573   CFGBlock *createBlock(bool add_successor = true);
574   CFGBlock *createNoReturnBlock();
575 
addStmt(Stmt * S)576   CFGBlock *addStmt(Stmt *S) {
577     return Visit(S, AddStmtChoice::AlwaysAdd);
578   }
579   CFGBlock *addInitializer(CXXCtorInitializer *I);
580   void addAutomaticObjDtors(LocalScope::const_iterator B,
581                             LocalScope::const_iterator E, Stmt *S);
582   void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
583 
584   // Local scopes creation.
585   LocalScope* createOrReuseLocalScope(LocalScope* Scope);
586 
587   void addLocalScopeForStmt(Stmt *S);
588   LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,
589                                        LocalScope* Scope = nullptr);
590   LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);
591 
592   void addLocalScopeAndDtors(Stmt *S);
593 
594   // Interface to CFGBlock - adding CFGElements.
appendStmt(CFGBlock * B,const Stmt * S)595   void appendStmt(CFGBlock *B, const Stmt *S) {
596     if (alwaysAdd(S) && cachedEntry)
597       cachedEntry->second = B;
598 
599     // All block-level expressions should have already been IgnoreParens()ed.
600     assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
601     B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
602   }
appendInitializer(CFGBlock * B,CXXCtorInitializer * I)603   void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
604     B->appendInitializer(I, cfg->getBumpVectorContext());
605   }
appendNewAllocator(CFGBlock * B,CXXNewExpr * NE)606   void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {
607     B->appendNewAllocator(NE, cfg->getBumpVectorContext());
608   }
appendBaseDtor(CFGBlock * B,const CXXBaseSpecifier * BS)609   void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
610     B->appendBaseDtor(BS, cfg->getBumpVectorContext());
611   }
appendMemberDtor(CFGBlock * B,FieldDecl * FD)612   void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
613     B->appendMemberDtor(FD, cfg->getBumpVectorContext());
614   }
appendTemporaryDtor(CFGBlock * B,CXXBindTemporaryExpr * E)615   void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
616     B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
617   }
appendAutomaticObjDtor(CFGBlock * B,VarDecl * VD,Stmt * S)618   void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
619     B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
620   }
621 
appendDeleteDtor(CFGBlock * B,CXXRecordDecl * RD,CXXDeleteExpr * DE)622   void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
623     B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
624   }
625 
626   void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
627       LocalScope::const_iterator B, LocalScope::const_iterator E);
628 
addSuccessor(CFGBlock * B,CFGBlock * S,bool IsReachable=true)629   void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {
630     B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable),
631                     cfg->getBumpVectorContext());
632   }
633 
634   /// Add a reachable successor to a block, with the alternate variant that is
635   /// unreachable.
addSuccessor(CFGBlock * B,CFGBlock * ReachableBlock,CFGBlock * AltBlock)636   void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {
637     B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),
638                     cfg->getBumpVectorContext());
639   }
640 
641   /// \brief Find a relational comparison with an expression evaluating to a
642   /// boolean and a constant other than 0 and 1.
643   /// e.g. if ((x < y) == 10)
checkIncorrectRelationalOperator(const BinaryOperator * B)644   TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) {
645     const Expr *LHSExpr = B->getLHS()->IgnoreParens();
646     const Expr *RHSExpr = B->getRHS()->IgnoreParens();
647 
648     const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
649     const Expr *BoolExpr = RHSExpr;
650     bool IntFirst = true;
651     if (!IntLiteral) {
652       IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
653       BoolExpr = LHSExpr;
654       IntFirst = false;
655     }
656 
657     if (!IntLiteral || !BoolExpr->isKnownToHaveBooleanValue())
658       return TryResult();
659 
660     llvm::APInt IntValue = IntLiteral->getValue();
661     if ((IntValue == 1) || (IntValue == 0))
662       return TryResult();
663 
664     bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() ||
665                      !IntValue.isNegative();
666 
667     BinaryOperatorKind Bok = B->getOpcode();
668     if (Bok == BO_GT || Bok == BO_GE) {
669       // Always true for 10 > bool and bool > -1
670       // Always false for -1 > bool and bool > 10
671       return TryResult(IntFirst == IntLarger);
672     } else {
673       // Always true for -1 < bool and bool < 10
674       // Always false for 10 < bool and bool < -1
675       return TryResult(IntFirst != IntLarger);
676     }
677   }
678 
679   /// Find an incorrect equality comparison. Either with an expression
680   /// evaluating to a boolean and a constant other than 0 and 1.
681   /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to
682   /// true/false e.q. (x & 8) == 4.
checkIncorrectEqualityOperator(const BinaryOperator * B)683   TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) {
684     const Expr *LHSExpr = B->getLHS()->IgnoreParens();
685     const Expr *RHSExpr = B->getRHS()->IgnoreParens();
686 
687     const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);
688     const Expr *BoolExpr = RHSExpr;
689 
690     if (!IntLiteral) {
691       IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);
692       BoolExpr = LHSExpr;
693     }
694 
695     if (!IntLiteral)
696       return TryResult();
697 
698     const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(BoolExpr);
699     if (BitOp && (BitOp->getOpcode() == BO_And ||
700                   BitOp->getOpcode() == BO_Or)) {
701       const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens();
702       const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens();
703 
704       const IntegerLiteral *IntLiteral2 = dyn_cast<IntegerLiteral>(LHSExpr2);
705 
706       if (!IntLiteral2)
707         IntLiteral2 = dyn_cast<IntegerLiteral>(RHSExpr2);
708 
709       if (!IntLiteral2)
710         return TryResult();
711 
712       llvm::APInt L1 = IntLiteral->getValue();
713       llvm::APInt L2 = IntLiteral2->getValue();
714       if ((BitOp->getOpcode() == BO_And && (L2 & L1) != L1) ||
715           (BitOp->getOpcode() == BO_Or  && (L2 | L1) != L1)) {
716         if (BuildOpts.Observer)
717           BuildOpts.Observer->compareBitwiseEquality(B,
718                                                      B->getOpcode() != BO_EQ);
719         TryResult(B->getOpcode() != BO_EQ);
720       }
721     } else if (BoolExpr->isKnownToHaveBooleanValue()) {
722       llvm::APInt IntValue = IntLiteral->getValue();
723       if ((IntValue == 1) || (IntValue == 0)) {
724         return TryResult();
725       }
726       return TryResult(B->getOpcode() != BO_EQ);
727     }
728 
729     return TryResult();
730   }
731 
analyzeLogicOperatorCondition(BinaryOperatorKind Relation,const llvm::APSInt & Value1,const llvm::APSInt & Value2)732   TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation,
733                                           const llvm::APSInt &Value1,
734                                           const llvm::APSInt &Value2) {
735     assert(Value1.isSigned() == Value2.isSigned());
736     switch (Relation) {
737       default:
738         return TryResult();
739       case BO_EQ:
740         return TryResult(Value1 == Value2);
741       case BO_NE:
742         return TryResult(Value1 != Value2);
743       case BO_LT:
744         return TryResult(Value1 <  Value2);
745       case BO_LE:
746         return TryResult(Value1 <= Value2);
747       case BO_GT:
748         return TryResult(Value1 >  Value2);
749       case BO_GE:
750         return TryResult(Value1 >= Value2);
751     }
752   }
753 
754   /// \brief Find a pair of comparison expressions with or without parentheses
755   /// with a shared variable and constants and a logical operator between them
756   /// that always evaluates to either true or false.
757   /// e.g. if (x != 3 || x != 4)
checkIncorrectLogicOperator(const BinaryOperator * B)758   TryResult checkIncorrectLogicOperator(const BinaryOperator *B) {
759     assert(B->isLogicalOp());
760     const BinaryOperator *LHS =
761         dyn_cast<BinaryOperator>(B->getLHS()->IgnoreParens());
762     const BinaryOperator *RHS =
763         dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens());
764     if (!LHS || !RHS)
765       return TryResult();
766 
767     if (!LHS->isComparisonOp() || !RHS->isComparisonOp())
768       return TryResult();
769 
770     const DeclRefExpr *Decl1;
771     const Expr *Expr1;
772     BinaryOperatorKind BO1;
773     std::tie(Decl1, BO1, Expr1) = tryNormalizeBinaryOperator(LHS);
774 
775     if (!Decl1 || !Expr1)
776       return TryResult();
777 
778     const DeclRefExpr *Decl2;
779     const Expr *Expr2;
780     BinaryOperatorKind BO2;
781     std::tie(Decl2, BO2, Expr2) = tryNormalizeBinaryOperator(RHS);
782 
783     if (!Decl2 || !Expr2)
784       return TryResult();
785 
786     // Check that it is the same variable on both sides.
787     if (Decl1->getDecl() != Decl2->getDecl())
788       return TryResult();
789 
790     // Make sure the user's intent is clear (e.g. they're comparing against two
791     // int literals, or two things from the same enum)
792     if (!areExprTypesCompatible(Expr1, Expr2))
793       return TryResult();
794 
795     llvm::APSInt L1, L2;
796 
797     if (!Expr1->EvaluateAsInt(L1, *Context) ||
798         !Expr2->EvaluateAsInt(L2, *Context))
799       return TryResult();
800 
801     // Can't compare signed with unsigned or with different bit width.
802     if (L1.isSigned() != L2.isSigned() || L1.getBitWidth() != L2.getBitWidth())
803       return TryResult();
804 
805     // Values that will be used to determine if result of logical
806     // operator is always true/false
807     const llvm::APSInt Values[] = {
808       // Value less than both Value1 and Value2
809       llvm::APSInt::getMinValue(L1.getBitWidth(), L1.isUnsigned()),
810       // L1
811       L1,
812       // Value between Value1 and Value2
813       ((L1 < L2) ? L1 : L2) + llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1),
814                               L1.isUnsigned()),
815       // L2
816       L2,
817       // Value greater than both Value1 and Value2
818       llvm::APSInt::getMaxValue(L1.getBitWidth(), L1.isUnsigned()),
819     };
820 
821     // Check whether expression is always true/false by evaluating the following
822     // * variable x is less than the smallest literal.
823     // * variable x is equal to the smallest literal.
824     // * Variable x is between smallest and largest literal.
825     // * Variable x is equal to the largest literal.
826     // * Variable x is greater than largest literal.
827     bool AlwaysTrue = true, AlwaysFalse = true;
828     for (const llvm::APSInt &Value : Values) {
829       TryResult Res1, Res2;
830       Res1 = analyzeLogicOperatorCondition(BO1, Value, L1);
831       Res2 = analyzeLogicOperatorCondition(BO2, Value, L2);
832 
833       if (!Res1.isKnown() || !Res2.isKnown())
834         return TryResult();
835 
836       if (B->getOpcode() == BO_LAnd) {
837         AlwaysTrue &= (Res1.isTrue() && Res2.isTrue());
838         AlwaysFalse &= !(Res1.isTrue() && Res2.isTrue());
839       } else {
840         AlwaysTrue &= (Res1.isTrue() || Res2.isTrue());
841         AlwaysFalse &= !(Res1.isTrue() || Res2.isTrue());
842       }
843     }
844 
845     if (AlwaysTrue || AlwaysFalse) {
846       if (BuildOpts.Observer)
847         BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue);
848       return TryResult(AlwaysTrue);
849     }
850     return TryResult();
851   }
852 
853   /// Try and evaluate an expression to an integer constant.
tryEvaluate(Expr * S,Expr::EvalResult & outResult)854   bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {
855     if (!BuildOpts.PruneTriviallyFalseEdges)
856       return false;
857     return !S->isTypeDependent() &&
858            !S->isValueDependent() &&
859            S->EvaluateAsRValue(outResult, *Context);
860   }
861 
862   /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
863   /// if we can evaluate to a known value, otherwise return -1.
tryEvaluateBool(Expr * S)864   TryResult tryEvaluateBool(Expr *S) {
865     if (!BuildOpts.PruneTriviallyFalseEdges ||
866         S->isTypeDependent() || S->isValueDependent())
867       return TryResult();
868 
869     if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) {
870       if (Bop->isLogicalOp()) {
871         // Check the cache first.
872         CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S);
873         if (I != CachedBoolEvals.end())
874           return I->second; // already in map;
875 
876         // Retrieve result at first, or the map might be updated.
877         TryResult Result = evaluateAsBooleanConditionNoCache(S);
878         CachedBoolEvals[S] = Result; // update or insert
879         return Result;
880       }
881       else {
882         switch (Bop->getOpcode()) {
883           default: break;
884           // For 'x & 0' and 'x * 0', we can determine that
885           // the value is always false.
886           case BO_Mul:
887           case BO_And: {
888             // If either operand is zero, we know the value
889             // must be false.
890             llvm::APSInt IntVal;
891             if (Bop->getLHS()->EvaluateAsInt(IntVal, *Context)) {
892               if (!IntVal.getBoolValue()) {
893                 return TryResult(false);
894               }
895             }
896             if (Bop->getRHS()->EvaluateAsInt(IntVal, *Context)) {
897               if (!IntVal.getBoolValue()) {
898                 return TryResult(false);
899               }
900             }
901           }
902           break;
903         }
904       }
905     }
906 
907     return evaluateAsBooleanConditionNoCache(S);
908   }
909 
910   /// \brief Evaluate as boolean \param E without using the cache.
evaluateAsBooleanConditionNoCache(Expr * E)911   TryResult evaluateAsBooleanConditionNoCache(Expr *E) {
912     if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) {
913       if (Bop->isLogicalOp()) {
914         TryResult LHS = tryEvaluateBool(Bop->getLHS());
915         if (LHS.isKnown()) {
916           // We were able to evaluate the LHS, see if we can get away with not
917           // evaluating the RHS: 0 && X -> 0, 1 || X -> 1
918           if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr))
919             return LHS.isTrue();
920 
921           TryResult RHS = tryEvaluateBool(Bop->getRHS());
922           if (RHS.isKnown()) {
923             if (Bop->getOpcode() == BO_LOr)
924               return LHS.isTrue() || RHS.isTrue();
925             else
926               return LHS.isTrue() && RHS.isTrue();
927           }
928         } else {
929           TryResult RHS = tryEvaluateBool(Bop->getRHS());
930           if (RHS.isKnown()) {
931             // We can't evaluate the LHS; however, sometimes the result
932             // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.
933             if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr))
934               return RHS.isTrue();
935           } else {
936             TryResult BopRes = checkIncorrectLogicOperator(Bop);
937             if (BopRes.isKnown())
938               return BopRes.isTrue();
939           }
940         }
941 
942         return TryResult();
943       } else if (Bop->isEqualityOp()) {
944           TryResult BopRes = checkIncorrectEqualityOperator(Bop);
945           if (BopRes.isKnown())
946             return BopRes.isTrue();
947       } else if (Bop->isRelationalOp()) {
948         TryResult BopRes = checkIncorrectRelationalOperator(Bop);
949         if (BopRes.isKnown())
950           return BopRes.isTrue();
951       }
952     }
953 
954     bool Result;
955     if (E->EvaluateAsBooleanCondition(Result, *Context))
956       return Result;
957 
958     return TryResult();
959   }
960 
961 };
962 
alwaysAdd(CFGBuilder & builder,const Stmt * stmt) const963 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
964                                      const Stmt *stmt) const {
965   return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
966 }
967 
alwaysAdd(const Stmt * stmt)968 bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
969   bool shouldAdd = BuildOpts.alwaysAdd(stmt);
970 
971   if (!BuildOpts.forcedBlkExprs)
972     return shouldAdd;
973 
974   if (lastLookup == stmt) {
975     if (cachedEntry) {
976       assert(cachedEntry->first == stmt);
977       return true;
978     }
979     return shouldAdd;
980   }
981 
982   lastLookup = stmt;
983 
984   // Perform the lookup!
985   CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
986 
987   if (!fb) {
988     // No need to update 'cachedEntry', since it will always be null.
989     assert(!cachedEntry);
990     return shouldAdd;
991   }
992 
993   CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);
994   if (itr == fb->end()) {
995     cachedEntry = nullptr;
996     return shouldAdd;
997   }
998 
999   cachedEntry = &*itr;
1000   return true;
1001 }
1002 
1003 // FIXME: Add support for dependent-sized array types in C++?
1004 // Does it even make sense to build a CFG for an uninstantiated template?
FindVA(const Type * t)1005 static const VariableArrayType *FindVA(const Type *t) {
1006   while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {
1007     if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
1008       if (vat->getSizeExpr())
1009         return vat;
1010 
1011     t = vt->getElementType().getTypePtr();
1012   }
1013 
1014   return nullptr;
1015 }
1016 
1017 /// BuildCFG - Constructs a CFG from an AST (a Stmt*).  The AST can represent an
1018 ///  arbitrary statement.  Examples include a single expression or a function
1019 ///  body (compound statement).  The ownership of the returned CFG is
1020 ///  transferred to the caller.  If CFG construction fails, this method returns
1021 ///  NULL.
buildCFG(const Decl * D,Stmt * Statement)1022 std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
1023   assert(cfg.get());
1024   if (!Statement)
1025     return nullptr;
1026 
1027   // Create an empty block that will serve as the exit block for the CFG.  Since
1028   // this is the first block added to the CFG, it will be implicitly registered
1029   // as the exit block.
1030   Succ = createBlock();
1031   assert(Succ == &cfg->getExit());
1032   Block = nullptr;  // the EXIT block is empty.  Create all other blocks lazily.
1033 
1034   if (BuildOpts.AddImplicitDtors)
1035     if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
1036       addImplicitDtorsForDestructor(DD);
1037 
1038   // Visit the statements and create the CFG.
1039   CFGBlock *B = addStmt(Statement);
1040 
1041   if (badCFG)
1042     return nullptr;
1043 
1044   // For C++ constructor add initializers to CFG.
1045   if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {
1046     for (auto *I : llvm::reverse(CD->inits())) {
1047       B = addInitializer(I);
1048       if (badCFG)
1049         return nullptr;
1050     }
1051   }
1052 
1053   if (B)
1054     Succ = B;
1055 
1056   // Backpatch the gotos whose label -> block mappings we didn't know when we
1057   // encountered them.
1058   for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
1059                                    E = BackpatchBlocks.end(); I != E; ++I ) {
1060 
1061     CFGBlock *B = I->block;
1062     const GotoStmt *G = cast<GotoStmt>(B->getTerminator());
1063     LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
1064 
1065     // If there is no target for the goto, then we are looking at an
1066     // incomplete AST.  Handle this by not registering a successor.
1067     if (LI == LabelMap.end()) continue;
1068 
1069     JumpTarget JT = LI->second;
1070     prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
1071                                            JT.scopePosition);
1072     addSuccessor(B, JT.block);
1073   }
1074 
1075   // Add successors to the Indirect Goto Dispatch block (if we have one).
1076   if (CFGBlock *B = cfg->getIndirectGotoBlock())
1077     for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
1078                               E = AddressTakenLabels.end(); I != E; ++I ) {
1079 
1080       // Lookup the target block.
1081       LabelMapTy::iterator LI = LabelMap.find(*I);
1082 
1083       // If there is no target block that contains label, then we are looking
1084       // at an incomplete AST.  Handle this by not registering a successor.
1085       if (LI == LabelMap.end()) continue;
1086 
1087       addSuccessor(B, LI->second.block);
1088     }
1089 
1090   // Create an empty entry block that has no predecessors.
1091   cfg->setEntry(createBlock());
1092 
1093   return std::move(cfg);
1094 }
1095 
1096 /// createBlock - Used to lazily create blocks that are connected
1097 ///  to the current (global) succcessor.
createBlock(bool add_successor)1098 CFGBlock *CFGBuilder::createBlock(bool add_successor) {
1099   CFGBlock *B = cfg->createBlock();
1100   if (add_successor && Succ)
1101     addSuccessor(B, Succ);
1102   return B;
1103 }
1104 
1105 /// createNoReturnBlock - Used to create a block is a 'noreturn' point in the
1106 /// CFG. It is *not* connected to the current (global) successor, and instead
1107 /// directly tied to the exit block in order to be reachable.
createNoReturnBlock()1108 CFGBlock *CFGBuilder::createNoReturnBlock() {
1109   CFGBlock *B = createBlock(false);
1110   B->setHasNoReturnElement();
1111   addSuccessor(B, &cfg->getExit(), Succ);
1112   return B;
1113 }
1114 
1115 /// addInitializer - Add C++ base or member initializer element to CFG.
addInitializer(CXXCtorInitializer * I)1116 CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
1117   if (!BuildOpts.AddInitializers)
1118     return Block;
1119 
1120   bool HasTemporaries = false;
1121 
1122   // Destructors of temporaries in initialization expression should be called
1123   // after initialization finishes.
1124   Expr *Init = I->getInit();
1125   if (Init) {
1126     HasTemporaries = isa<ExprWithCleanups>(Init);
1127 
1128     if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
1129       // Generate destructors for temporaries in initialization expression.
1130       TempDtorContext Context;
1131       VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
1132                              /*BindToTemporary=*/false, Context);
1133     }
1134   }
1135 
1136   autoCreateBlock();
1137   appendInitializer(Block, I);
1138 
1139   if (Init) {
1140     if (HasTemporaries) {
1141       // For expression with temporaries go directly to subexpression to omit
1142       // generating destructors for the second time.
1143       return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
1144     }
1145     if (BuildOpts.AddCXXDefaultInitExprInCtors) {
1146       if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) {
1147         // In general, appending the expression wrapped by a CXXDefaultInitExpr
1148         // may cause the same Expr to appear more than once in the CFG. Doing it
1149         // here is safe because there's only one initializer per field.
1150         autoCreateBlock();
1151         appendStmt(Block, Default);
1152         if (Stmt *Child = Default->getExpr())
1153           if (CFGBlock *R = Visit(Child))
1154             Block = R;
1155         return Block;
1156       }
1157     }
1158     return Visit(Init);
1159   }
1160 
1161   return Block;
1162 }
1163 
1164 /// \brief Retrieve the type of the temporary object whose lifetime was
1165 /// extended by a local reference with the given initializer.
getReferenceInitTemporaryType(ASTContext & Context,const Expr * Init)1166 static QualType getReferenceInitTemporaryType(ASTContext &Context,
1167                                               const Expr *Init) {
1168   while (true) {
1169     // Skip parentheses.
1170     Init = Init->IgnoreParens();
1171 
1172     // Skip through cleanups.
1173     if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) {
1174       Init = EWC->getSubExpr();
1175       continue;
1176     }
1177 
1178     // Skip through the temporary-materialization expression.
1179     if (const MaterializeTemporaryExpr *MTE
1180           = dyn_cast<MaterializeTemporaryExpr>(Init)) {
1181       Init = MTE->GetTemporaryExpr();
1182       continue;
1183     }
1184 
1185     // Skip derived-to-base and no-op casts.
1186     if (const CastExpr *CE = dyn_cast<CastExpr>(Init)) {
1187       if ((CE->getCastKind() == CK_DerivedToBase ||
1188            CE->getCastKind() == CK_UncheckedDerivedToBase ||
1189            CE->getCastKind() == CK_NoOp) &&
1190           Init->getType()->isRecordType()) {
1191         Init = CE->getSubExpr();
1192         continue;
1193       }
1194     }
1195 
1196     // Skip member accesses into rvalues.
1197     if (const MemberExpr *ME = dyn_cast<MemberExpr>(Init)) {
1198       if (!ME->isArrow() && ME->getBase()->isRValue()) {
1199         Init = ME->getBase();
1200         continue;
1201       }
1202     }
1203 
1204     break;
1205   }
1206 
1207   return Init->getType();
1208 }
1209 
1210 /// addAutomaticObjDtors - Add to current block automatic objects destructors
1211 /// for objects in range of local scope positions. Use S as trigger statement
1212 /// for destructors.
addAutomaticObjDtors(LocalScope::const_iterator B,LocalScope::const_iterator E,Stmt * S)1213 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
1214                                       LocalScope::const_iterator E, Stmt *S) {
1215   if (!BuildOpts.AddImplicitDtors)
1216     return;
1217 
1218   if (B == E)
1219     return;
1220 
1221   // We need to append the destructors in reverse order, but any one of them
1222   // may be a no-return destructor which changes the CFG. As a result, buffer
1223   // this sequence up and replay them in reverse order when appending onto the
1224   // CFGBlock(s).
1225   SmallVector<VarDecl*, 10> Decls;
1226   Decls.reserve(B.distance(E));
1227   for (LocalScope::const_iterator I = B; I != E; ++I)
1228     Decls.push_back(*I);
1229 
1230   for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(),
1231                                                    E = Decls.rend();
1232        I != E; ++I) {
1233     // If this destructor is marked as a no-return destructor, we need to
1234     // create a new block for the destructor which does not have as a successor
1235     // anything built thus far: control won't flow out of this block.
1236     QualType Ty = (*I)->getType();
1237     if (Ty->isReferenceType()) {
1238       Ty = getReferenceInitTemporaryType(*Context, (*I)->getInit());
1239     }
1240     Ty = Context->getBaseElementType(Ty);
1241 
1242     if (Ty->getAsCXXRecordDecl()->isAnyDestructorNoReturn())
1243       Block = createNoReturnBlock();
1244     else
1245       autoCreateBlock();
1246 
1247     appendAutomaticObjDtor(Block, *I, S);
1248   }
1249 }
1250 
1251 /// addImplicitDtorsForDestructor - Add implicit destructors generated for
1252 /// base and member objects in destructor.
addImplicitDtorsForDestructor(const CXXDestructorDecl * DD)1253 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
1254   assert (BuildOpts.AddImplicitDtors
1255       && "Can be called only when dtors should be added");
1256   const CXXRecordDecl *RD = DD->getParent();
1257 
1258   // At the end destroy virtual base objects.
1259   for (const auto &VI : RD->vbases()) {
1260     const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl();
1261     if (!CD->hasTrivialDestructor()) {
1262       autoCreateBlock();
1263       appendBaseDtor(Block, &VI);
1264     }
1265   }
1266 
1267   // Before virtual bases destroy direct base objects.
1268   for (const auto &BI : RD->bases()) {
1269     if (!BI.isVirtual()) {
1270       const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl();
1271       if (!CD->hasTrivialDestructor()) {
1272         autoCreateBlock();
1273         appendBaseDtor(Block, &BI);
1274       }
1275     }
1276   }
1277 
1278   // First destroy member objects.
1279   for (auto *FI : RD->fields()) {
1280     // Check for constant size array. Set type to array element type.
1281     QualType QT = FI->getType();
1282     if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
1283       if (AT->getSize() == 0)
1284         continue;
1285       QT = AT->getElementType();
1286     }
1287 
1288     if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
1289       if (!CD->hasTrivialDestructor()) {
1290         autoCreateBlock();
1291         appendMemberDtor(Block, FI);
1292       }
1293   }
1294 }
1295 
1296 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
1297 /// way return valid LocalScope object.
createOrReuseLocalScope(LocalScope * Scope)1298 LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
1299   if (Scope)
1300     return Scope;
1301   llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
1302   return new (alloc.Allocate<LocalScope>())
1303       LocalScope(BumpVectorContext(alloc), ScopePos);
1304 }
1305 
1306 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
1307 /// that should create implicit scope (e.g. if/else substatements).
addLocalScopeForStmt(Stmt * S)1308 void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
1309   if (!BuildOpts.AddImplicitDtors)
1310     return;
1311 
1312   LocalScope *Scope = nullptr;
1313 
1314   // For compound statement we will be creating explicit scope.
1315   if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {
1316     for (auto *BI : CS->body()) {
1317       Stmt *SI = BI->stripLabelLikeStatements();
1318       if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))
1319         Scope = addLocalScopeForDeclStmt(DS, Scope);
1320     }
1321     return;
1322   }
1323 
1324   // For any other statement scope will be implicit and as such will be
1325   // interesting only for DeclStmt.
1326   if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements()))
1327     addLocalScopeForDeclStmt(DS);
1328 }
1329 
1330 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
1331 /// reuse Scope if not NULL.
addLocalScopeForDeclStmt(DeclStmt * DS,LocalScope * Scope)1332 LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
1333                                                  LocalScope* Scope) {
1334   if (!BuildOpts.AddImplicitDtors)
1335     return Scope;
1336 
1337   for (auto *DI : DS->decls())
1338     if (VarDecl *VD = dyn_cast<VarDecl>(DI))
1339       Scope = addLocalScopeForVarDecl(VD, Scope);
1340   return Scope;
1341 }
1342 
1343 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
1344 /// create add scope for automatic objects and temporary objects bound to
1345 /// const reference. Will reuse Scope if not NULL.
addLocalScopeForVarDecl(VarDecl * VD,LocalScope * Scope)1346 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
1347                                                 LocalScope* Scope) {
1348   if (!BuildOpts.AddImplicitDtors)
1349     return Scope;
1350 
1351   // Check if variable is local.
1352   switch (VD->getStorageClass()) {
1353   case SC_None:
1354   case SC_Auto:
1355   case SC_Register:
1356     break;
1357   default: return Scope;
1358   }
1359 
1360   // Check for const references bound to temporary. Set type to pointee.
1361   QualType QT = VD->getType();
1362   if (QT.getTypePtr()->isReferenceType()) {
1363     // Attempt to determine whether this declaration lifetime-extends a
1364     // temporary.
1365     //
1366     // FIXME: This is incorrect. Non-reference declarations can lifetime-extend
1367     // temporaries, and a single declaration can extend multiple temporaries.
1368     // We should look at the storage duration on each nested
1369     // MaterializeTemporaryExpr instead.
1370     const Expr *Init = VD->getInit();
1371     if (!Init)
1372       return Scope;
1373     if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init))
1374       Init = EWC->getSubExpr();
1375     if (!isa<MaterializeTemporaryExpr>(Init))
1376       return Scope;
1377 
1378     // Lifetime-extending a temporary.
1379     QT = getReferenceInitTemporaryType(*Context, Init);
1380   }
1381 
1382   // Check for constant size array. Set type to array element type.
1383   while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
1384     if (AT->getSize() == 0)
1385       return Scope;
1386     QT = AT->getElementType();
1387   }
1388 
1389   // Check if type is a C++ class with non-trivial destructor.
1390   if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
1391     if (!CD->hasTrivialDestructor()) {
1392       // Add the variable to scope
1393       Scope = createOrReuseLocalScope(Scope);
1394       Scope->addVar(VD);
1395       ScopePos = Scope->begin();
1396     }
1397   return Scope;
1398 }
1399 
1400 /// addLocalScopeAndDtors - For given statement add local scope for it and
1401 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
addLocalScopeAndDtors(Stmt * S)1402 void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
1403   if (!BuildOpts.AddImplicitDtors)
1404     return;
1405 
1406   LocalScope::const_iterator scopeBeginPos = ScopePos;
1407   addLocalScopeForStmt(S);
1408   addAutomaticObjDtors(ScopePos, scopeBeginPos, S);
1409 }
1410 
1411 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
1412 /// variables with automatic storage duration to CFGBlock's elements vector.
1413 /// Elements will be prepended to physical beginning of the vector which
1414 /// happens to be logical end. Use blocks terminator as statement that specifies
1415 /// destructors call site.
1416 /// FIXME: This mechanism for adding automatic destructors doesn't handle
1417 /// no-return destructors properly.
prependAutomaticObjDtorsWithTerminator(CFGBlock * Blk,LocalScope::const_iterator B,LocalScope::const_iterator E)1418 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
1419     LocalScope::const_iterator B, LocalScope::const_iterator E) {
1420   BumpVectorContext &C = cfg->getBumpVectorContext();
1421   CFGBlock::iterator InsertPos
1422     = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
1423   for (LocalScope::const_iterator I = B; I != E; ++I)
1424     InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I,
1425                                             Blk->getTerminator());
1426 }
1427 
1428 /// Visit - Walk the subtree of a statement and add extra
1429 ///   blocks for ternary operators, &&, and ||.  We also process "," and
1430 ///   DeclStmts (which may contain nested control-flow).
Visit(Stmt * S,AddStmtChoice asc)1431 CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) {
1432   if (!S) {
1433     badCFG = true;
1434     return nullptr;
1435   }
1436 
1437   if (Expr *E = dyn_cast<Expr>(S))
1438     S = E->IgnoreParens();
1439 
1440   switch (S->getStmtClass()) {
1441     default:
1442       return VisitStmt(S, asc);
1443 
1444     case Stmt::AddrLabelExprClass:
1445       return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
1446 
1447     case Stmt::BinaryConditionalOperatorClass:
1448       return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
1449 
1450     case Stmt::BinaryOperatorClass:
1451       return VisitBinaryOperator(cast<BinaryOperator>(S), asc);
1452 
1453     case Stmt::BlockExprClass:
1454       return VisitBlockExpr(cast<BlockExpr>(S), asc);
1455 
1456     case Stmt::BreakStmtClass:
1457       return VisitBreakStmt(cast<BreakStmt>(S));
1458 
1459     case Stmt::CallExprClass:
1460     case Stmt::CXXOperatorCallExprClass:
1461     case Stmt::CXXMemberCallExprClass:
1462     case Stmt::UserDefinedLiteralClass:
1463       return VisitCallExpr(cast<CallExpr>(S), asc);
1464 
1465     case Stmt::CaseStmtClass:
1466       return VisitCaseStmt(cast<CaseStmt>(S));
1467 
1468     case Stmt::ChooseExprClass:
1469       return VisitChooseExpr(cast<ChooseExpr>(S), asc);
1470 
1471     case Stmt::CompoundStmtClass:
1472       return VisitCompoundStmt(cast<CompoundStmt>(S));
1473 
1474     case Stmt::ConditionalOperatorClass:
1475       return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);
1476 
1477     case Stmt::ContinueStmtClass:
1478       return VisitContinueStmt(cast<ContinueStmt>(S));
1479 
1480     case Stmt::CXXCatchStmtClass:
1481       return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));
1482 
1483     case Stmt::ExprWithCleanupsClass:
1484       return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc);
1485 
1486     case Stmt::CXXDefaultArgExprClass:
1487     case Stmt::CXXDefaultInitExprClass:
1488       // FIXME: The expression inside a CXXDefaultArgExpr is owned by the
1489       // called function's declaration, not by the caller. If we simply add
1490       // this expression to the CFG, we could end up with the same Expr
1491       // appearing multiple times.
1492       // PR13385 / <rdar://problem/12156507>
1493       //
1494       // It's likewise possible for multiple CXXDefaultInitExprs for the same
1495       // expression to be used in the same function (through aggregate
1496       // initialization).
1497       return VisitStmt(S, asc);
1498 
1499     case Stmt::CXXBindTemporaryExprClass:
1500       return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);
1501 
1502     case Stmt::CXXConstructExprClass:
1503       return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
1504 
1505     case Stmt::CXXNewExprClass:
1506       return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc);
1507 
1508     case Stmt::CXXDeleteExprClass:
1509       return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc);
1510 
1511     case Stmt::CXXFunctionalCastExprClass:
1512       return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);
1513 
1514     case Stmt::CXXTemporaryObjectExprClass:
1515       return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);
1516 
1517     case Stmt::CXXThrowExprClass:
1518       return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));
1519 
1520     case Stmt::CXXTryStmtClass:
1521       return VisitCXXTryStmt(cast<CXXTryStmt>(S));
1522 
1523     case Stmt::CXXForRangeStmtClass:
1524       return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));
1525 
1526     case Stmt::DeclStmtClass:
1527       return VisitDeclStmt(cast<DeclStmt>(S));
1528 
1529     case Stmt::DefaultStmtClass:
1530       return VisitDefaultStmt(cast<DefaultStmt>(S));
1531 
1532     case Stmt::DoStmtClass:
1533       return VisitDoStmt(cast<DoStmt>(S));
1534 
1535     case Stmt::ForStmtClass:
1536       return VisitForStmt(cast<ForStmt>(S));
1537 
1538     case Stmt::GotoStmtClass:
1539       return VisitGotoStmt(cast<GotoStmt>(S));
1540 
1541     case Stmt::IfStmtClass:
1542       return VisitIfStmt(cast<IfStmt>(S));
1543 
1544     case Stmt::ImplicitCastExprClass:
1545       return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);
1546 
1547     case Stmt::IndirectGotoStmtClass:
1548       return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));
1549 
1550     case Stmt::LabelStmtClass:
1551       return VisitLabelStmt(cast<LabelStmt>(S));
1552 
1553     case Stmt::LambdaExprClass:
1554       return VisitLambdaExpr(cast<LambdaExpr>(S), asc);
1555 
1556     case Stmt::MemberExprClass:
1557       return VisitMemberExpr(cast<MemberExpr>(S), asc);
1558 
1559     case Stmt::NullStmtClass:
1560       return Block;
1561 
1562     case Stmt::ObjCAtCatchStmtClass:
1563       return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));
1564 
1565     case Stmt::ObjCAutoreleasePoolStmtClass:
1566     return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S));
1567 
1568     case Stmt::ObjCAtSynchronizedStmtClass:
1569       return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));
1570 
1571     case Stmt::ObjCAtThrowStmtClass:
1572       return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));
1573 
1574     case Stmt::ObjCAtTryStmtClass:
1575       return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));
1576 
1577     case Stmt::ObjCForCollectionStmtClass:
1578       return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));
1579 
1580     case Stmt::OpaqueValueExprClass:
1581       return Block;
1582 
1583     case Stmt::PseudoObjectExprClass:
1584       return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S));
1585 
1586     case Stmt::ReturnStmtClass:
1587       return VisitReturnStmt(cast<ReturnStmt>(S));
1588 
1589     case Stmt::UnaryExprOrTypeTraitExprClass:
1590       return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1591                                            asc);
1592 
1593     case Stmt::StmtExprClass:
1594       return VisitStmtExpr(cast<StmtExpr>(S), asc);
1595 
1596     case Stmt::SwitchStmtClass:
1597       return VisitSwitchStmt(cast<SwitchStmt>(S));
1598 
1599     case Stmt::UnaryOperatorClass:
1600       return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
1601 
1602     case Stmt::WhileStmtClass:
1603       return VisitWhileStmt(cast<WhileStmt>(S));
1604   }
1605 }
1606 
VisitStmt(Stmt * S,AddStmtChoice asc)1607 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
1608   if (asc.alwaysAdd(*this, S)) {
1609     autoCreateBlock();
1610     appendStmt(Block, S);
1611   }
1612 
1613   return VisitChildren(S);
1614 }
1615 
1616 /// VisitChildren - Visit the children of a Stmt.
VisitChildren(Stmt * S)1617 CFGBlock *CFGBuilder::VisitChildren(Stmt *S) {
1618   CFGBlock *B = Block;
1619 
1620   // Visit the children in their reverse order so that they appear in
1621   // left-to-right (natural) order in the CFG.
1622   reverse_children RChildren(S);
1623   for (reverse_children::iterator I = RChildren.begin(), E = RChildren.end();
1624        I != E; ++I) {
1625     if (Stmt *Child = *I)
1626       if (CFGBlock *R = Visit(Child))
1627         B = R;
1628   }
1629   return B;
1630 }
1631 
VisitAddrLabelExpr(AddrLabelExpr * A,AddStmtChoice asc)1632 CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
1633                                          AddStmtChoice asc) {
1634   AddressTakenLabels.insert(A->getLabel());
1635 
1636   if (asc.alwaysAdd(*this, A)) {
1637     autoCreateBlock();
1638     appendStmt(Block, A);
1639   }
1640 
1641   return Block;
1642 }
1643 
VisitUnaryOperator(UnaryOperator * U,AddStmtChoice asc)1644 CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U,
1645            AddStmtChoice asc) {
1646   if (asc.alwaysAdd(*this, U)) {
1647     autoCreateBlock();
1648     appendStmt(Block, U);
1649   }
1650 
1651   return Visit(U->getSubExpr(), AddStmtChoice());
1652 }
1653 
VisitLogicalOperator(BinaryOperator * B)1654 CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) {
1655   CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
1656   appendStmt(ConfluenceBlock, B);
1657 
1658   if (badCFG)
1659     return nullptr;
1660 
1661   return VisitLogicalOperator(B, nullptr, ConfluenceBlock,
1662                               ConfluenceBlock).first;
1663 }
1664 
1665 std::pair<CFGBlock*, CFGBlock*>
VisitLogicalOperator(BinaryOperator * B,Stmt * Term,CFGBlock * TrueBlock,CFGBlock * FalseBlock)1666 CFGBuilder::VisitLogicalOperator(BinaryOperator *B,
1667                                  Stmt *Term,
1668                                  CFGBlock *TrueBlock,
1669                                  CFGBlock *FalseBlock) {
1670 
1671   // Introspect the RHS.  If it is a nested logical operation, we recursively
1672   // build the CFG using this function.  Otherwise, resort to default
1673   // CFG construction behavior.
1674   Expr *RHS = B->getRHS()->IgnoreParens();
1675   CFGBlock *RHSBlock, *ExitBlock;
1676 
1677   do {
1678     if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(RHS))
1679       if (B_RHS->isLogicalOp()) {
1680         std::tie(RHSBlock, ExitBlock) =
1681           VisitLogicalOperator(B_RHS, Term, TrueBlock, FalseBlock);
1682         break;
1683       }
1684 
1685     // The RHS is not a nested logical operation.  Don't push the terminator
1686     // down further, but instead visit RHS and construct the respective
1687     // pieces of the CFG, and link up the RHSBlock with the terminator
1688     // we have been provided.
1689     ExitBlock = RHSBlock = createBlock(false);
1690 
1691     if (!Term) {
1692       assert(TrueBlock == FalseBlock);
1693       addSuccessor(RHSBlock, TrueBlock);
1694     }
1695     else {
1696       RHSBlock->setTerminator(Term);
1697       TryResult KnownVal = tryEvaluateBool(RHS);
1698       if (!KnownVal.isKnown())
1699         KnownVal = tryEvaluateBool(B);
1700       addSuccessor(RHSBlock, TrueBlock, !KnownVal.isFalse());
1701       addSuccessor(RHSBlock, FalseBlock, !KnownVal.isTrue());
1702     }
1703 
1704     Block = RHSBlock;
1705     RHSBlock = addStmt(RHS);
1706   }
1707   while (false);
1708 
1709   if (badCFG)
1710     return std::make_pair(nullptr, nullptr);
1711 
1712   // Generate the blocks for evaluating the LHS.
1713   Expr *LHS = B->getLHS()->IgnoreParens();
1714 
1715   if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(LHS))
1716     if (B_LHS->isLogicalOp()) {
1717       if (B->getOpcode() == BO_LOr)
1718         FalseBlock = RHSBlock;
1719       else
1720         TrueBlock = RHSBlock;
1721 
1722       // For the LHS, treat 'B' as the terminator that we want to sink
1723       // into the nested branch.  The RHS always gets the top-most
1724       // terminator.
1725       return VisitLogicalOperator(B_LHS, B, TrueBlock, FalseBlock);
1726     }
1727 
1728   // Create the block evaluating the LHS.
1729   // This contains the '&&' or '||' as the terminator.
1730   CFGBlock *LHSBlock = createBlock(false);
1731   LHSBlock->setTerminator(B);
1732 
1733   Block = LHSBlock;
1734   CFGBlock *EntryLHSBlock = addStmt(LHS);
1735 
1736   if (badCFG)
1737     return std::make_pair(nullptr, nullptr);
1738 
1739   // See if this is a known constant.
1740   TryResult KnownVal = tryEvaluateBool(LHS);
1741 
1742   // Now link the LHSBlock with RHSBlock.
1743   if (B->getOpcode() == BO_LOr) {
1744     addSuccessor(LHSBlock, TrueBlock, !KnownVal.isFalse());
1745     addSuccessor(LHSBlock, RHSBlock, !KnownVal.isTrue());
1746   } else {
1747     assert(B->getOpcode() == BO_LAnd);
1748     addSuccessor(LHSBlock, RHSBlock, !KnownVal.isFalse());
1749     addSuccessor(LHSBlock, FalseBlock, !KnownVal.isTrue());
1750   }
1751 
1752   return std::make_pair(EntryLHSBlock, ExitBlock);
1753 }
1754 
1755 
VisitBinaryOperator(BinaryOperator * B,AddStmtChoice asc)1756 CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
1757                                           AddStmtChoice asc) {
1758    // && or ||
1759   if (B->isLogicalOp())
1760     return VisitLogicalOperator(B);
1761 
1762   if (B->getOpcode() == BO_Comma) { // ,
1763     autoCreateBlock();
1764     appendStmt(Block, B);
1765     addStmt(B->getRHS());
1766     return addStmt(B->getLHS());
1767   }
1768 
1769   if (B->isAssignmentOp()) {
1770     if (asc.alwaysAdd(*this, B)) {
1771       autoCreateBlock();
1772       appendStmt(Block, B);
1773     }
1774     Visit(B->getLHS());
1775     return Visit(B->getRHS());
1776   }
1777 
1778   if (asc.alwaysAdd(*this, B)) {
1779     autoCreateBlock();
1780     appendStmt(Block, B);
1781   }
1782 
1783   CFGBlock *RBlock = Visit(B->getRHS());
1784   CFGBlock *LBlock = Visit(B->getLHS());
1785   // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
1786   // containing a DoStmt, and the LHS doesn't create a new block, then we should
1787   // return RBlock.  Otherwise we'll incorrectly return NULL.
1788   return (LBlock ? LBlock : RBlock);
1789 }
1790 
VisitNoRecurse(Expr * E,AddStmtChoice asc)1791 CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) {
1792   if (asc.alwaysAdd(*this, E)) {
1793     autoCreateBlock();
1794     appendStmt(Block, E);
1795   }
1796   return Block;
1797 }
1798 
VisitBreakStmt(BreakStmt * B)1799 CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
1800   // "break" is a control-flow statement.  Thus we stop processing the current
1801   // block.
1802   if (badCFG)
1803     return nullptr;
1804 
1805   // Now create a new block that ends with the break statement.
1806   Block = createBlock(false);
1807   Block->setTerminator(B);
1808 
1809   // If there is no target for the break, then we are looking at an incomplete
1810   // AST.  This means that the CFG cannot be constructed.
1811   if (BreakJumpTarget.block) {
1812     addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B);
1813     addSuccessor(Block, BreakJumpTarget.block);
1814   } else
1815     badCFG = true;
1816 
1817 
1818   return Block;
1819 }
1820 
CanThrow(Expr * E,ASTContext & Ctx)1821 static bool CanThrow(Expr *E, ASTContext &Ctx) {
1822   QualType Ty = E->getType();
1823   if (Ty->isFunctionPointerType())
1824     Ty = Ty->getAs<PointerType>()->getPointeeType();
1825   else if (Ty->isBlockPointerType())
1826     Ty = Ty->getAs<BlockPointerType>()->getPointeeType();
1827 
1828   const FunctionType *FT = Ty->getAs<FunctionType>();
1829   if (FT) {
1830     if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
1831       if (!isUnresolvedExceptionSpec(Proto->getExceptionSpecType()) &&
1832           Proto->isNothrow(Ctx))
1833         return false;
1834   }
1835   return true;
1836 }
1837 
VisitCallExpr(CallExpr * C,AddStmtChoice asc)1838 CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
1839   // Compute the callee type.
1840   QualType calleeType = C->getCallee()->getType();
1841   if (calleeType == Context->BoundMemberTy) {
1842     QualType boundType = Expr::findBoundMemberType(C->getCallee());
1843 
1844     // We should only get a null bound type if processing a dependent
1845     // CFG.  Recover by assuming nothing.
1846     if (!boundType.isNull()) calleeType = boundType;
1847   }
1848 
1849   // If this is a call to a no-return function, this stops the block here.
1850   bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();
1851 
1852   bool AddEHEdge = false;
1853 
1854   // Languages without exceptions are assumed to not throw.
1855   if (Context->getLangOpts().Exceptions) {
1856     if (BuildOpts.AddEHEdges)
1857       AddEHEdge = true;
1858   }
1859 
1860   // If this is a call to a builtin function, it might not actually evaluate
1861   // its arguments. Don't add them to the CFG if this is the case.
1862   bool OmitArguments = false;
1863 
1864   if (FunctionDecl *FD = C->getDirectCallee()) {
1865     if (FD->isNoReturn())
1866       NoReturn = true;
1867     if (FD->hasAttr<NoThrowAttr>())
1868       AddEHEdge = false;
1869     if (FD->getBuiltinID() == Builtin::BI__builtin_object_size)
1870       OmitArguments = true;
1871   }
1872 
1873   if (!CanThrow(C->getCallee(), *Context))
1874     AddEHEdge = false;
1875 
1876   if (OmitArguments) {
1877     assert(!NoReturn && "noreturn calls with unevaluated args not implemented");
1878     assert(!AddEHEdge && "EH calls with unevaluated args not implemented");
1879     autoCreateBlock();
1880     appendStmt(Block, C);
1881     return Visit(C->getCallee());
1882   }
1883 
1884   if (!NoReturn && !AddEHEdge) {
1885     return VisitStmt(C, asc.withAlwaysAdd(true));
1886   }
1887 
1888   if (Block) {
1889     Succ = Block;
1890     if (badCFG)
1891       return nullptr;
1892   }
1893 
1894   if (NoReturn)
1895     Block = createNoReturnBlock();
1896   else
1897     Block = createBlock();
1898 
1899   appendStmt(Block, C);
1900 
1901   if (AddEHEdge) {
1902     // Add exceptional edges.
1903     if (TryTerminatedBlock)
1904       addSuccessor(Block, TryTerminatedBlock);
1905     else
1906       addSuccessor(Block, &cfg->getExit());
1907   }
1908 
1909   return VisitChildren(C);
1910 }
1911 
VisitChooseExpr(ChooseExpr * C,AddStmtChoice asc)1912 CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
1913                                       AddStmtChoice asc) {
1914   CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
1915   appendStmt(ConfluenceBlock, C);
1916   if (badCFG)
1917     return nullptr;
1918 
1919   AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
1920   Succ = ConfluenceBlock;
1921   Block = nullptr;
1922   CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd);
1923   if (badCFG)
1924     return nullptr;
1925 
1926   Succ = ConfluenceBlock;
1927   Block = nullptr;
1928   CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd);
1929   if (badCFG)
1930     return nullptr;
1931 
1932   Block = createBlock(false);
1933   // See if this is a known constant.
1934   const TryResult& KnownVal = tryEvaluateBool(C->getCond());
1935   addSuccessor(Block, KnownVal.isFalse() ? nullptr : LHSBlock);
1936   addSuccessor(Block, KnownVal.isTrue() ? nullptr : RHSBlock);
1937   Block->setTerminator(C);
1938   return addStmt(C->getCond());
1939 }
1940 
1941 
VisitCompoundStmt(CompoundStmt * C)1942 CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) {
1943   LocalScope::const_iterator scopeBeginPos = ScopePos;
1944   if (BuildOpts.AddImplicitDtors) {
1945     addLocalScopeForStmt(C);
1946   }
1947   if (!C->body_empty() && !isa<ReturnStmt>(*C->body_rbegin())) {
1948     // If the body ends with a ReturnStmt, the dtors will be added in
1949     // VisitReturnStmt.
1950     addAutomaticObjDtors(ScopePos, scopeBeginPos, C);
1951   }
1952 
1953   CFGBlock *LastBlock = Block;
1954 
1955   for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
1956        I != E; ++I ) {
1957     // If we hit a segment of code just containing ';' (NullStmts), we can
1958     // get a null block back.  In such cases, just use the LastBlock
1959     if (CFGBlock *newBlock = addStmt(*I))
1960       LastBlock = newBlock;
1961 
1962     if (badCFG)
1963       return nullptr;
1964   }
1965 
1966   return LastBlock;
1967 }
1968 
VisitConditionalOperator(AbstractConditionalOperator * C,AddStmtChoice asc)1969 CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
1970                                                AddStmtChoice asc) {
1971   const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);
1972   const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr);
1973 
1974   // Create the confluence block that will "merge" the results of the ternary
1975   // expression.
1976   CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
1977   appendStmt(ConfluenceBlock, C);
1978   if (badCFG)
1979     return nullptr;
1980 
1981   AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
1982 
1983   // Create a block for the LHS expression if there is an LHS expression.  A
1984   // GCC extension allows LHS to be NULL, causing the condition to be the
1985   // value that is returned instead.
1986   //  e.g: x ?: y is shorthand for: x ? x : y;
1987   Succ = ConfluenceBlock;
1988   Block = nullptr;
1989   CFGBlock *LHSBlock = nullptr;
1990   const Expr *trueExpr = C->getTrueExpr();
1991   if (trueExpr != opaqueValue) {
1992     LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);
1993     if (badCFG)
1994       return nullptr;
1995     Block = nullptr;
1996   }
1997   else
1998     LHSBlock = ConfluenceBlock;
1999 
2000   // Create the block for the RHS expression.
2001   Succ = ConfluenceBlock;
2002   CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);
2003   if (badCFG)
2004     return nullptr;
2005 
2006   // If the condition is a logical '&&' or '||', build a more accurate CFG.
2007   if (BinaryOperator *Cond =
2008         dyn_cast<BinaryOperator>(C->getCond()->IgnoreParens()))
2009     if (Cond->isLogicalOp())
2010       return VisitLogicalOperator(Cond, C, LHSBlock, RHSBlock).first;
2011 
2012   // Create the block that will contain the condition.
2013   Block = createBlock(false);
2014 
2015   // See if this is a known constant.
2016   const TryResult& KnownVal = tryEvaluateBool(C->getCond());
2017   addSuccessor(Block, LHSBlock, !KnownVal.isFalse());
2018   addSuccessor(Block, RHSBlock, !KnownVal.isTrue());
2019   Block->setTerminator(C);
2020   Expr *condExpr = C->getCond();
2021 
2022   if (opaqueValue) {
2023     // Run the condition expression if it's not trivially expressed in
2024     // terms of the opaque value (or if there is no opaque value).
2025     if (condExpr != opaqueValue)
2026       addStmt(condExpr);
2027 
2028     // Before that, run the common subexpression if there was one.
2029     // At least one of this or the above will be run.
2030     return addStmt(BCO->getCommon());
2031   }
2032 
2033   return addStmt(condExpr);
2034 }
2035 
VisitDeclStmt(DeclStmt * DS)2036 CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
2037   // Check if the Decl is for an __label__.  If so, elide it from the
2038   // CFG entirely.
2039   if (isa<LabelDecl>(*DS->decl_begin()))
2040     return Block;
2041 
2042   // This case also handles static_asserts.
2043   if (DS->isSingleDecl())
2044     return VisitDeclSubExpr(DS);
2045 
2046   CFGBlock *B = nullptr;
2047 
2048   // Build an individual DeclStmt for each decl.
2049   for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(),
2050                                        E = DS->decl_rend();
2051        I != E; ++I) {
2052     // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
2053     unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8
2054                ? 8 : llvm::AlignOf<DeclStmt>::Alignment;
2055 
2056     // Allocate the DeclStmt using the BumpPtrAllocator.  It will get
2057     // automatically freed with the CFG.
2058     DeclGroupRef DG(*I);
2059     Decl *D = *I;
2060     void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A);
2061     DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
2062     cfg->addSyntheticDeclStmt(DSNew, DS);
2063 
2064     // Append the fake DeclStmt to block.
2065     B = VisitDeclSubExpr(DSNew);
2066   }
2067 
2068   return B;
2069 }
2070 
2071 /// VisitDeclSubExpr - Utility method to add block-level expressions for
2072 /// DeclStmts and initializers in them.
VisitDeclSubExpr(DeclStmt * DS)2073 CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
2074   assert(DS->isSingleDecl() && "Can handle single declarations only.");
2075   VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
2076 
2077   if (!VD) {
2078     // Of everything that can be declared in a DeclStmt, only VarDecls impact
2079     // runtime semantics.
2080     return Block;
2081   }
2082 
2083   bool HasTemporaries = false;
2084 
2085   // Guard static initializers under a branch.
2086   CFGBlock *blockAfterStaticInit = nullptr;
2087 
2088   if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) {
2089     // For static variables, we need to create a branch to track
2090     // whether or not they are initialized.
2091     if (Block) {
2092       Succ = Block;
2093       Block = nullptr;
2094       if (badCFG)
2095         return nullptr;
2096     }
2097     blockAfterStaticInit = Succ;
2098   }
2099 
2100   // Destructors of temporaries in initialization expression should be called
2101   // after initialization finishes.
2102   Expr *Init = VD->getInit();
2103   if (Init) {
2104     HasTemporaries = isa<ExprWithCleanups>(Init);
2105 
2106     if (BuildOpts.AddTemporaryDtors && HasTemporaries) {
2107       // Generate destructors for temporaries in initialization expression.
2108       TempDtorContext Context;
2109       VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
2110                              /*BindToTemporary=*/false, Context);
2111     }
2112   }
2113 
2114   autoCreateBlock();
2115   appendStmt(Block, DS);
2116 
2117   // Keep track of the last non-null block, as 'Block' can be nulled out
2118   // if the initializer expression is something like a 'while' in a
2119   // statement-expression.
2120   CFGBlock *LastBlock = Block;
2121 
2122   if (Init) {
2123     if (HasTemporaries) {
2124       // For expression with temporaries go directly to subexpression to omit
2125       // generating destructors for the second time.
2126       ExprWithCleanups *EC = cast<ExprWithCleanups>(Init);
2127       if (CFGBlock *newBlock = Visit(EC->getSubExpr()))
2128         LastBlock = newBlock;
2129     }
2130     else {
2131       if (CFGBlock *newBlock = Visit(Init))
2132         LastBlock = newBlock;
2133     }
2134   }
2135 
2136   // If the type of VD is a VLA, then we must process its size expressions.
2137   for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());
2138        VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr())) {
2139     if (CFGBlock *newBlock = addStmt(VA->getSizeExpr()))
2140       LastBlock = newBlock;
2141   }
2142 
2143   // Remove variable from local scope.
2144   if (ScopePos && VD == *ScopePos)
2145     ++ScopePos;
2146 
2147   CFGBlock *B = LastBlock;
2148   if (blockAfterStaticInit) {
2149     Succ = B;
2150     Block = createBlock(false);
2151     Block->setTerminator(DS);
2152     addSuccessor(Block, blockAfterStaticInit);
2153     addSuccessor(Block, B);
2154     B = Block;
2155   }
2156 
2157   return B;
2158 }
2159 
VisitIfStmt(IfStmt * I)2160 CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
2161   // We may see an if statement in the middle of a basic block, or it may be the
2162   // first statement we are processing.  In either case, we create a new basic
2163   // block.  First, we create the blocks for the then...else statements, and
2164   // then we create the block containing the if statement.  If we were in the
2165   // middle of a block, we stop processing that block.  That block is then the
2166   // implicit successor for the "then" and "else" clauses.
2167 
2168   // Save local scope position because in case of condition variable ScopePos
2169   // won't be restored when traversing AST.
2170   SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2171 
2172   // Create local scope for C++17 if init-stmt if one exists.
2173   if (Stmt *Init = I->getInit()) {
2174     LocalScope::const_iterator BeginScopePos = ScopePos;
2175     addLocalScopeForStmt(Init);
2176     addAutomaticObjDtors(ScopePos, BeginScopePos, I);
2177   }
2178 
2179   // Create local scope for possible condition variable.
2180   // Store scope position. Add implicit destructor.
2181   if (VarDecl *VD = I->getConditionVariable()) {
2182     LocalScope::const_iterator BeginScopePos = ScopePos;
2183     addLocalScopeForVarDecl(VD);
2184     addAutomaticObjDtors(ScopePos, BeginScopePos, I);
2185   }
2186 
2187   // The block we were processing is now finished.  Make it the successor
2188   // block.
2189   if (Block) {
2190     Succ = Block;
2191     if (badCFG)
2192       return nullptr;
2193   }
2194 
2195   // Process the false branch.
2196   CFGBlock *ElseBlock = Succ;
2197 
2198   if (Stmt *Else = I->getElse()) {
2199     SaveAndRestore<CFGBlock*> sv(Succ);
2200 
2201     // NULL out Block so that the recursive call to Visit will
2202     // create a new basic block.
2203     Block = nullptr;
2204 
2205     // If branch is not a compound statement create implicit scope
2206     // and add destructors.
2207     if (!isa<CompoundStmt>(Else))
2208       addLocalScopeAndDtors(Else);
2209 
2210     ElseBlock = addStmt(Else);
2211 
2212     if (!ElseBlock) // Can occur when the Else body has all NullStmts.
2213       ElseBlock = sv.get();
2214     else if (Block) {
2215       if (badCFG)
2216         return nullptr;
2217     }
2218   }
2219 
2220   // Process the true branch.
2221   CFGBlock *ThenBlock;
2222   {
2223     Stmt *Then = I->getThen();
2224     assert(Then);
2225     SaveAndRestore<CFGBlock*> sv(Succ);
2226     Block = nullptr;
2227 
2228     // If branch is not a compound statement create implicit scope
2229     // and add destructors.
2230     if (!isa<CompoundStmt>(Then))
2231       addLocalScopeAndDtors(Then);
2232 
2233     ThenBlock = addStmt(Then);
2234 
2235     if (!ThenBlock) {
2236       // We can reach here if the "then" body has all NullStmts.
2237       // Create an empty block so we can distinguish between true and false
2238       // branches in path-sensitive analyses.
2239       ThenBlock = createBlock(false);
2240       addSuccessor(ThenBlock, sv.get());
2241     } else if (Block) {
2242       if (badCFG)
2243         return nullptr;
2244     }
2245   }
2246 
2247   // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by
2248   // having these handle the actual control-flow jump.  Note that
2249   // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)"
2250   // we resort to the old control-flow behavior.  This special handling
2251   // removes infeasible paths from the control-flow graph by having the
2252   // control-flow transfer of '&&' or '||' go directly into the then/else
2253   // blocks directly.
2254   if (!I->getConditionVariable())
2255     if (BinaryOperator *Cond =
2256             dyn_cast<BinaryOperator>(I->getCond()->IgnoreParens()))
2257       if (Cond->isLogicalOp())
2258         return VisitLogicalOperator(Cond, I, ThenBlock, ElseBlock).first;
2259 
2260   // Now create a new block containing the if statement.
2261   Block = createBlock(false);
2262 
2263   // Set the terminator of the new block to the If statement.
2264   Block->setTerminator(I);
2265 
2266   // See if this is a known constant.
2267   const TryResult &KnownVal = tryEvaluateBool(I->getCond());
2268 
2269   // Add the successors.  If we know that specific branches are
2270   // unreachable, inform addSuccessor() of that knowledge.
2271   addSuccessor(Block, ThenBlock, /* isReachable = */ !KnownVal.isFalse());
2272   addSuccessor(Block, ElseBlock, /* isReachable = */ !KnownVal.isTrue());
2273 
2274   // Add the condition as the last statement in the new block.  This may create
2275   // new blocks as the condition may contain control-flow.  Any newly created
2276   // blocks will be pointed to be "Block".
2277   CFGBlock *LastBlock = addStmt(I->getCond());
2278 
2279   // If the IfStmt contains a condition variable, add it and its
2280   // initializer to the CFG.
2281   if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) {
2282     autoCreateBlock();
2283     LastBlock = addStmt(const_cast<DeclStmt *>(DS));
2284   }
2285 
2286   // Finally, if the IfStmt contains a C++17 init-stmt, add it to the CFG.
2287   if (Stmt *Init = I->getInit()) {
2288     autoCreateBlock();
2289     LastBlock = addStmt(Init);
2290   }
2291 
2292   return LastBlock;
2293 }
2294 
2295 
VisitReturnStmt(ReturnStmt * R)2296 CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) {
2297   // If we were in the middle of a block we stop processing that block.
2298   //
2299   // NOTE: If a "return" appears in the middle of a block, this means that the
2300   //       code afterwards is DEAD (unreachable).  We still keep a basic block
2301   //       for that code; a simple "mark-and-sweep" from the entry block will be
2302   //       able to report such dead blocks.
2303 
2304   // Create the new block.
2305   Block = createBlock(false);
2306 
2307   addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R);
2308 
2309   // If the one of the destructors does not return, we already have the Exit
2310   // block as a successor.
2311   if (!Block->hasNoReturnElement())
2312     addSuccessor(Block, &cfg->getExit());
2313 
2314   // Add the return statement to the block.  This may create new blocks if R
2315   // contains control-flow (short-circuit operations).
2316   return VisitStmt(R, AddStmtChoice::AlwaysAdd);
2317 }
2318 
VisitLabelStmt(LabelStmt * L)2319 CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
2320   // Get the block of the labeled statement.  Add it to our map.
2321   addStmt(L->getSubStmt());
2322   CFGBlock *LabelBlock = Block;
2323 
2324   if (!LabelBlock)              // This can happen when the body is empty, i.e.
2325     LabelBlock = createBlock(); // scopes that only contains NullStmts.
2326 
2327   assert(LabelMap.find(L->getDecl()) == LabelMap.end() &&
2328          "label already in map");
2329   LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
2330 
2331   // Labels partition blocks, so this is the end of the basic block we were
2332   // processing (L is the block's label).  Because this is label (and we have
2333   // already processed the substatement) there is no extra control-flow to worry
2334   // about.
2335   LabelBlock->setLabel(L);
2336   if (badCFG)
2337     return nullptr;
2338 
2339   // We set Block to NULL to allow lazy creation of a new block (if necessary);
2340   Block = nullptr;
2341 
2342   // This block is now the implicit successor of other blocks.
2343   Succ = LabelBlock;
2344 
2345   return LabelBlock;
2346 }
2347 
VisitBlockExpr(BlockExpr * E,AddStmtChoice asc)2348 CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
2349   CFGBlock *LastBlock = VisitNoRecurse(E, asc);
2350   for (const BlockDecl::Capture &CI : E->getBlockDecl()->captures()) {
2351     if (Expr *CopyExpr = CI.getCopyExpr()) {
2352       CFGBlock *Tmp = Visit(CopyExpr);
2353       if (Tmp)
2354         LastBlock = Tmp;
2355     }
2356   }
2357   return LastBlock;
2358 }
2359 
VisitLambdaExpr(LambdaExpr * E,AddStmtChoice asc)2360 CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {
2361   CFGBlock *LastBlock = VisitNoRecurse(E, asc);
2362   for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),
2363        et = E->capture_init_end(); it != et; ++it) {
2364     if (Expr *Init = *it) {
2365       CFGBlock *Tmp = Visit(Init);
2366       if (Tmp)
2367         LastBlock = Tmp;
2368     }
2369   }
2370   return LastBlock;
2371 }
2372 
VisitGotoStmt(GotoStmt * G)2373 CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
2374   // Goto is a control-flow statement.  Thus we stop processing the current
2375   // block and create a new one.
2376 
2377   Block = createBlock(false);
2378   Block->setTerminator(G);
2379 
2380   // If we already know the mapping to the label block add the successor now.
2381   LabelMapTy::iterator I = LabelMap.find(G->getLabel());
2382 
2383   if (I == LabelMap.end())
2384     // We will need to backpatch this block later.
2385     BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
2386   else {
2387     JumpTarget JT = I->second;
2388     addAutomaticObjDtors(ScopePos, JT.scopePosition, G);
2389     addSuccessor(Block, JT.block);
2390   }
2391 
2392   return Block;
2393 }
2394 
VisitForStmt(ForStmt * F)2395 CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
2396   CFGBlock *LoopSuccessor = nullptr;
2397 
2398   // Save local scope position because in case of condition variable ScopePos
2399   // won't be restored when traversing AST.
2400   SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2401 
2402   // Create local scope for init statement and possible condition variable.
2403   // Add destructor for init statement and condition variable.
2404   // Store scope position for continue statement.
2405   if (Stmt *Init = F->getInit())
2406     addLocalScopeForStmt(Init);
2407   LocalScope::const_iterator LoopBeginScopePos = ScopePos;
2408 
2409   if (VarDecl *VD = F->getConditionVariable())
2410     addLocalScopeForVarDecl(VD);
2411   LocalScope::const_iterator ContinueScopePos = ScopePos;
2412 
2413   addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F);
2414 
2415   // "for" is a control-flow statement.  Thus we stop processing the current
2416   // block.
2417   if (Block) {
2418     if (badCFG)
2419       return nullptr;
2420     LoopSuccessor = Block;
2421   } else
2422     LoopSuccessor = Succ;
2423 
2424   // Save the current value for the break targets.
2425   // All breaks should go to the code following the loop.
2426   SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
2427   BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2428 
2429   CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
2430 
2431   // Now create the loop body.
2432   {
2433     assert(F->getBody());
2434 
2435     // Save the current values for Block, Succ, continue and break targets.
2436     SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2437     SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
2438 
2439     // Create an empty block to represent the transition block for looping back
2440     // to the head of the loop.  If we have increment code, it will
2441     // go in this block as well.
2442     Block = Succ = TransitionBlock = createBlock(false);
2443     TransitionBlock->setLoopTarget(F);
2444 
2445     if (Stmt *I = F->getInc()) {
2446       // Generate increment code in its own basic block.  This is the target of
2447       // continue statements.
2448       Succ = addStmt(I);
2449     }
2450 
2451     // Finish up the increment (or empty) block if it hasn't been already.
2452     if (Block) {
2453       assert(Block == Succ);
2454       if (badCFG)
2455         return nullptr;
2456       Block = nullptr;
2457     }
2458 
2459    // The starting block for the loop increment is the block that should
2460    // represent the 'loop target' for looping back to the start of the loop.
2461    ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
2462    ContinueJumpTarget.block->setLoopTarget(F);
2463 
2464     // Loop body should end with destructor of Condition variable (if any).
2465     addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F);
2466 
2467     // If body is not a compound statement create implicit scope
2468     // and add destructors.
2469     if (!isa<CompoundStmt>(F->getBody()))
2470       addLocalScopeAndDtors(F->getBody());
2471 
2472     // Now populate the body block, and in the process create new blocks as we
2473     // walk the body of the loop.
2474     BodyBlock = addStmt(F->getBody());
2475 
2476     if (!BodyBlock) {
2477       // In the case of "for (...;...;...);" we can have a null BodyBlock.
2478       // Use the continue jump target as the proxy for the body.
2479       BodyBlock = ContinueJumpTarget.block;
2480     }
2481     else if (badCFG)
2482       return nullptr;
2483   }
2484 
2485   // Because of short-circuit evaluation, the condition of the loop can span
2486   // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that
2487   // evaluate the condition.
2488   CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
2489 
2490   do {
2491     Expr *C = F->getCond();
2492 
2493     // Specially handle logical operators, which have a slightly
2494     // more optimal CFG representation.
2495     if (BinaryOperator *Cond =
2496             dyn_cast_or_null<BinaryOperator>(C ? C->IgnoreParens() : nullptr))
2497       if (Cond->isLogicalOp()) {
2498         std::tie(EntryConditionBlock, ExitConditionBlock) =
2499           VisitLogicalOperator(Cond, F, BodyBlock, LoopSuccessor);
2500         break;
2501       }
2502 
2503     // The default case when not handling logical operators.
2504     EntryConditionBlock = ExitConditionBlock = createBlock(false);
2505     ExitConditionBlock->setTerminator(F);
2506 
2507     // See if this is a known constant.
2508     TryResult KnownVal(true);
2509 
2510     if (C) {
2511       // Now add the actual condition to the condition block.
2512       // Because the condition itself may contain control-flow, new blocks may
2513       // be created.  Thus we update "Succ" after adding the condition.
2514       Block = ExitConditionBlock;
2515       EntryConditionBlock = addStmt(C);
2516 
2517       // If this block contains a condition variable, add both the condition
2518       // variable and initializer to the CFG.
2519       if (VarDecl *VD = F->getConditionVariable()) {
2520         if (Expr *Init = VD->getInit()) {
2521           autoCreateBlock();
2522           appendStmt(Block, F->getConditionVariableDeclStmt());
2523           EntryConditionBlock = addStmt(Init);
2524           assert(Block == EntryConditionBlock);
2525         }
2526       }
2527 
2528       if (Block && badCFG)
2529         return nullptr;
2530 
2531       KnownVal = tryEvaluateBool(C);
2532     }
2533 
2534     // Add the loop body entry as a successor to the condition.
2535     addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);
2536     // Link up the condition block with the code that follows the loop.  (the
2537     // false branch).
2538     addSuccessor(ExitConditionBlock,
2539                  KnownVal.isTrue() ? nullptr : LoopSuccessor);
2540 
2541   } while (false);
2542 
2543   // Link up the loop-back block to the entry condition block.
2544   addSuccessor(TransitionBlock, EntryConditionBlock);
2545 
2546   // The condition block is the implicit successor for any code above the loop.
2547   Succ = EntryConditionBlock;
2548 
2549   // If the loop contains initialization, create a new block for those
2550   // statements.  This block can also contain statements that precede the loop.
2551   if (Stmt *I = F->getInit()) {
2552     Block = createBlock();
2553     return addStmt(I);
2554   }
2555 
2556   // There is no loop initialization.  We are thus basically a while loop.
2557   // NULL out Block to force lazy block construction.
2558   Block = nullptr;
2559   Succ = EntryConditionBlock;
2560   return EntryConditionBlock;
2561 }
2562 
VisitMemberExpr(MemberExpr * M,AddStmtChoice asc)2563 CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
2564   if (asc.alwaysAdd(*this, M)) {
2565     autoCreateBlock();
2566     appendStmt(Block, M);
2567   }
2568   return Visit(M->getBase());
2569 }
2570 
VisitObjCForCollectionStmt(ObjCForCollectionStmt * S)2571 CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
2572   // Objective-C fast enumeration 'for' statements:
2573   //  http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
2574   //
2575   //  for ( Type newVariable in collection_expression ) { statements }
2576   //
2577   //  becomes:
2578   //
2579   //   prologue:
2580   //     1. collection_expression
2581   //     T. jump to loop_entry
2582   //   loop_entry:
2583   //     1. side-effects of element expression
2584   //     1. ObjCForCollectionStmt [performs binding to newVariable]
2585   //     T. ObjCForCollectionStmt  TB, FB  [jumps to TB if newVariable != nil]
2586   //   TB:
2587   //     statements
2588   //     T. jump to loop_entry
2589   //   FB:
2590   //     what comes after
2591   //
2592   //  and
2593   //
2594   //  Type existingItem;
2595   //  for ( existingItem in expression ) { statements }
2596   //
2597   //  becomes:
2598   //
2599   //   the same with newVariable replaced with existingItem; the binding works
2600   //   the same except that for one ObjCForCollectionStmt::getElement() returns
2601   //   a DeclStmt and the other returns a DeclRefExpr.
2602   //
2603 
2604   CFGBlock *LoopSuccessor = nullptr;
2605 
2606   if (Block) {
2607     if (badCFG)
2608       return nullptr;
2609     LoopSuccessor = Block;
2610     Block = nullptr;
2611   } else
2612     LoopSuccessor = Succ;
2613 
2614   // Build the condition blocks.
2615   CFGBlock *ExitConditionBlock = createBlock(false);
2616 
2617   // Set the terminator for the "exit" condition block.
2618   ExitConditionBlock->setTerminator(S);
2619 
2620   // The last statement in the block should be the ObjCForCollectionStmt, which
2621   // performs the actual binding to 'element' and determines if there are any
2622   // more items in the collection.
2623   appendStmt(ExitConditionBlock, S);
2624   Block = ExitConditionBlock;
2625 
2626   // Walk the 'element' expression to see if there are any side-effects.  We
2627   // generate new blocks as necessary.  We DON'T add the statement by default to
2628   // the CFG unless it contains control-flow.
2629   CFGBlock *EntryConditionBlock = Visit(S->getElement(),
2630                                         AddStmtChoice::NotAlwaysAdd);
2631   if (Block) {
2632     if (badCFG)
2633       return nullptr;
2634     Block = nullptr;
2635   }
2636 
2637   // The condition block is the implicit successor for the loop body as well as
2638   // any code above the loop.
2639   Succ = EntryConditionBlock;
2640 
2641   // Now create the true branch.
2642   {
2643     // Save the current values for Succ, continue and break targets.
2644     SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2645     SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
2646                                save_break(BreakJumpTarget);
2647 
2648     // Add an intermediate block between the BodyBlock and the
2649     // EntryConditionBlock to represent the "loop back" transition, for looping
2650     // back to the head of the loop.
2651     CFGBlock *LoopBackBlock = nullptr;
2652     Succ = LoopBackBlock = createBlock();
2653     LoopBackBlock->setLoopTarget(S);
2654 
2655     BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2656     ContinueJumpTarget = JumpTarget(Succ, ScopePos);
2657 
2658     CFGBlock *BodyBlock = addStmt(S->getBody());
2659 
2660     if (!BodyBlock)
2661       BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;"
2662     else if (Block) {
2663       if (badCFG)
2664         return nullptr;
2665     }
2666 
2667     // This new body block is a successor to our "exit" condition block.
2668     addSuccessor(ExitConditionBlock, BodyBlock);
2669   }
2670 
2671   // Link up the condition block with the code that follows the loop.
2672   // (the false branch).
2673   addSuccessor(ExitConditionBlock, LoopSuccessor);
2674 
2675   // Now create a prologue block to contain the collection expression.
2676   Block = createBlock();
2677   return addStmt(S->getCollection());
2678 }
2679 
VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt * S)2680 CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) {
2681   // Inline the body.
2682   return addStmt(S->getSubStmt());
2683   // TODO: consider adding cleanups for the end of @autoreleasepool scope.
2684 }
2685 
VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt * S)2686 CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
2687   // FIXME: Add locking 'primitives' to CFG for @synchronized.
2688 
2689   // Inline the body.
2690   CFGBlock *SyncBlock = addStmt(S->getSynchBody());
2691 
2692   // The sync body starts its own basic block.  This makes it a little easier
2693   // for diagnostic clients.
2694   if (SyncBlock) {
2695     if (badCFG)
2696       return nullptr;
2697 
2698     Block = nullptr;
2699     Succ = SyncBlock;
2700   }
2701 
2702   // Add the @synchronized to the CFG.
2703   autoCreateBlock();
2704   appendStmt(Block, S);
2705 
2706   // Inline the sync expression.
2707   return addStmt(S->getSynchExpr());
2708 }
2709 
VisitObjCAtTryStmt(ObjCAtTryStmt * S)2710 CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) {
2711   // FIXME
2712   return NYS();
2713 }
2714 
VisitPseudoObjectExpr(PseudoObjectExpr * E)2715 CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {
2716   autoCreateBlock();
2717 
2718   // Add the PseudoObject as the last thing.
2719   appendStmt(Block, E);
2720 
2721   CFGBlock *lastBlock = Block;
2722 
2723   // Before that, evaluate all of the semantics in order.  In
2724   // CFG-land, that means appending them in reverse order.
2725   for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {
2726     Expr *Semantic = E->getSemanticExpr(--i);
2727 
2728     // If the semantic is an opaque value, we're being asked to bind
2729     // it to its source expression.
2730     if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
2731       Semantic = OVE->getSourceExpr();
2732 
2733     if (CFGBlock *B = Visit(Semantic))
2734       lastBlock = B;
2735   }
2736 
2737   return lastBlock;
2738 }
2739 
VisitWhileStmt(WhileStmt * W)2740 CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
2741   CFGBlock *LoopSuccessor = nullptr;
2742 
2743   // Save local scope position because in case of condition variable ScopePos
2744   // won't be restored when traversing AST.
2745   SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2746 
2747   // Create local scope for possible condition variable.
2748   // Store scope position for continue statement.
2749   LocalScope::const_iterator LoopBeginScopePos = ScopePos;
2750   if (VarDecl *VD = W->getConditionVariable()) {
2751     addLocalScopeForVarDecl(VD);
2752     addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
2753   }
2754 
2755   // "while" is a control-flow statement.  Thus we stop processing the current
2756   // block.
2757   if (Block) {
2758     if (badCFG)
2759       return nullptr;
2760     LoopSuccessor = Block;
2761     Block = nullptr;
2762   } else {
2763     LoopSuccessor = Succ;
2764   }
2765 
2766   CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;
2767 
2768   // Process the loop body.
2769   {
2770     assert(W->getBody());
2771 
2772     // Save the current values for Block, Succ, continue and break targets.
2773     SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2774     SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
2775                                save_break(BreakJumpTarget);
2776 
2777     // Create an empty block to represent the transition block for looping back
2778     // to the head of the loop.
2779     Succ = TransitionBlock = createBlock(false);
2780     TransitionBlock->setLoopTarget(W);
2781     ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
2782 
2783     // All breaks should go to the code following the loop.
2784     BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2785 
2786     // Loop body should end with destructor of Condition variable (if any).
2787     addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
2788 
2789     // If body is not a compound statement create implicit scope
2790     // and add destructors.
2791     if (!isa<CompoundStmt>(W->getBody()))
2792       addLocalScopeAndDtors(W->getBody());
2793 
2794     // Create the body.  The returned block is the entry to the loop body.
2795     BodyBlock = addStmt(W->getBody());
2796 
2797     if (!BodyBlock)
2798       BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
2799     else if (Block && badCFG)
2800       return nullptr;
2801   }
2802 
2803   // Because of short-circuit evaluation, the condition of the loop can span
2804   // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that
2805   // evaluate the condition.
2806   CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;
2807 
2808   do {
2809     Expr *C = W->getCond();
2810 
2811     // Specially handle logical operators, which have a slightly
2812     // more optimal CFG representation.
2813     if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(C->IgnoreParens()))
2814       if (Cond->isLogicalOp()) {
2815         std::tie(EntryConditionBlock, ExitConditionBlock) =
2816             VisitLogicalOperator(Cond, W, BodyBlock, LoopSuccessor);
2817         break;
2818       }
2819 
2820     // The default case when not handling logical operators.
2821     ExitConditionBlock = createBlock(false);
2822     ExitConditionBlock->setTerminator(W);
2823 
2824     // Now add the actual condition to the condition block.
2825     // Because the condition itself may contain control-flow, new blocks may
2826     // be created.  Thus we update "Succ" after adding the condition.
2827     Block = ExitConditionBlock;
2828     Block = EntryConditionBlock = addStmt(C);
2829 
2830     // If this block contains a condition variable, add both the condition
2831     // variable and initializer to the CFG.
2832     if (VarDecl *VD = W->getConditionVariable()) {
2833       if (Expr *Init = VD->getInit()) {
2834         autoCreateBlock();
2835         appendStmt(Block, W->getConditionVariableDeclStmt());
2836         EntryConditionBlock = addStmt(Init);
2837         assert(Block == EntryConditionBlock);
2838       }
2839     }
2840 
2841     if (Block && badCFG)
2842       return nullptr;
2843 
2844     // See if this is a known constant.
2845     const TryResult& KnownVal = tryEvaluateBool(C);
2846 
2847     // Add the loop body entry as a successor to the condition.
2848     addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);
2849     // Link up the condition block with the code that follows the loop.  (the
2850     // false branch).
2851     addSuccessor(ExitConditionBlock,
2852                  KnownVal.isTrue() ? nullptr : LoopSuccessor);
2853 
2854   } while(false);
2855 
2856   // Link up the loop-back block to the entry condition block.
2857   addSuccessor(TransitionBlock, EntryConditionBlock);
2858 
2859   // There can be no more statements in the condition block since we loop back
2860   // to this block.  NULL out Block to force lazy creation of another block.
2861   Block = nullptr;
2862 
2863   // Return the condition block, which is the dominating block for the loop.
2864   Succ = EntryConditionBlock;
2865   return EntryConditionBlock;
2866 }
2867 
2868 
VisitObjCAtCatchStmt(ObjCAtCatchStmt * S)2869 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) {
2870   // FIXME: For now we pretend that @catch and the code it contains does not
2871   //  exit.
2872   return Block;
2873 }
2874 
VisitObjCAtThrowStmt(ObjCAtThrowStmt * S)2875 CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
2876   // FIXME: This isn't complete.  We basically treat @throw like a return
2877   //  statement.
2878 
2879   // If we were in the middle of a block we stop processing that block.
2880   if (badCFG)
2881     return nullptr;
2882 
2883   // Create the new block.
2884   Block = createBlock(false);
2885 
2886   // The Exit block is the only successor.
2887   addSuccessor(Block, &cfg->getExit());
2888 
2889   // Add the statement to the block.  This may create new blocks if S contains
2890   // control-flow (short-circuit operations).
2891   return VisitStmt(S, AddStmtChoice::AlwaysAdd);
2892 }
2893 
VisitCXXThrowExpr(CXXThrowExpr * T)2894 CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
2895   // If we were in the middle of a block we stop processing that block.
2896   if (badCFG)
2897     return nullptr;
2898 
2899   // Create the new block.
2900   Block = createBlock(false);
2901 
2902   if (TryTerminatedBlock)
2903     // The current try statement is the only successor.
2904     addSuccessor(Block, TryTerminatedBlock);
2905   else
2906     // otherwise the Exit block is the only successor.
2907     addSuccessor(Block, &cfg->getExit());
2908 
2909   // Add the statement to the block.  This may create new blocks if S contains
2910   // control-flow (short-circuit operations).
2911   return VisitStmt(T, AddStmtChoice::AlwaysAdd);
2912 }
2913 
VisitDoStmt(DoStmt * D)2914 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
2915   CFGBlock *LoopSuccessor = nullptr;
2916 
2917   // "do...while" is a control-flow statement.  Thus we stop processing the
2918   // current block.
2919   if (Block) {
2920     if (badCFG)
2921       return nullptr;
2922     LoopSuccessor = Block;
2923   } else
2924     LoopSuccessor = Succ;
2925 
2926   // Because of short-circuit evaluation, the condition of the loop can span
2927   // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that
2928   // evaluate the condition.
2929   CFGBlock *ExitConditionBlock = createBlock(false);
2930   CFGBlock *EntryConditionBlock = ExitConditionBlock;
2931 
2932   // Set the terminator for the "exit" condition block.
2933   ExitConditionBlock->setTerminator(D);
2934 
2935   // Now add the actual condition to the condition block.  Because the condition
2936   // itself may contain control-flow, new blocks may be created.
2937   if (Stmt *C = D->getCond()) {
2938     Block = ExitConditionBlock;
2939     EntryConditionBlock = addStmt(C);
2940     if (Block) {
2941       if (badCFG)
2942         return nullptr;
2943     }
2944   }
2945 
2946   // The condition block is the implicit successor for the loop body.
2947   Succ = EntryConditionBlock;
2948 
2949   // See if this is a known constant.
2950   const TryResult &KnownVal = tryEvaluateBool(D->getCond());
2951 
2952   // Process the loop body.
2953   CFGBlock *BodyBlock = nullptr;
2954   {
2955     assert(D->getBody());
2956 
2957     // Save the current values for Block, Succ, and continue and break targets
2958     SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2959     SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
2960         save_break(BreakJumpTarget);
2961 
2962     // All continues within this loop should go to the condition block
2963     ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
2964 
2965     // All breaks should go to the code following the loop.
2966     BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2967 
2968     // NULL out Block to force lazy instantiation of blocks for the body.
2969     Block = nullptr;
2970 
2971     // If body is not a compound statement create implicit scope
2972     // and add destructors.
2973     if (!isa<CompoundStmt>(D->getBody()))
2974       addLocalScopeAndDtors(D->getBody());
2975 
2976     // Create the body.  The returned block is the entry to the loop body.
2977     BodyBlock = addStmt(D->getBody());
2978 
2979     if (!BodyBlock)
2980       BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
2981     else if (Block) {
2982       if (badCFG)
2983         return nullptr;
2984     }
2985 
2986     if (!KnownVal.isFalse()) {
2987       // Add an intermediate block between the BodyBlock and the
2988       // ExitConditionBlock to represent the "loop back" transition.  Create an
2989       // empty block to represent the transition block for looping back to the
2990       // head of the loop.
2991       // FIXME: Can we do this more efficiently without adding another block?
2992       Block = nullptr;
2993       Succ = BodyBlock;
2994       CFGBlock *LoopBackBlock = createBlock();
2995       LoopBackBlock->setLoopTarget(D);
2996 
2997       // Add the loop body entry as a successor to the condition.
2998       addSuccessor(ExitConditionBlock, LoopBackBlock);
2999     }
3000     else
3001       addSuccessor(ExitConditionBlock, nullptr);
3002   }
3003 
3004   // Link up the condition block with the code that follows the loop.
3005   // (the false branch).
3006   addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);
3007 
3008   // There can be no more statements in the body block(s) since we loop back to
3009   // the body.  NULL out Block to force lazy creation of another block.
3010   Block = nullptr;
3011 
3012   // Return the loop body, which is the dominating block for the loop.
3013   Succ = BodyBlock;
3014   return BodyBlock;
3015 }
3016 
VisitContinueStmt(ContinueStmt * C)3017 CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
3018   // "continue" is a control-flow statement.  Thus we stop processing the
3019   // current block.
3020   if (badCFG)
3021     return nullptr;
3022 
3023   // Now create a new block that ends with the continue statement.
3024   Block = createBlock(false);
3025   Block->setTerminator(C);
3026 
3027   // If there is no target for the continue, then we are looking at an
3028   // incomplete AST.  This means the CFG cannot be constructed.
3029   if (ContinueJumpTarget.block) {
3030     addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C);
3031     addSuccessor(Block, ContinueJumpTarget.block);
3032   } else
3033     badCFG = true;
3034 
3035   return Block;
3036 }
3037 
VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr * E,AddStmtChoice asc)3038 CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
3039                                                     AddStmtChoice asc) {
3040 
3041   if (asc.alwaysAdd(*this, E)) {
3042     autoCreateBlock();
3043     appendStmt(Block, E);
3044   }
3045 
3046   // VLA types have expressions that must be evaluated.
3047   CFGBlock *lastBlock = Block;
3048 
3049   if (E->isArgumentType()) {
3050     for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());
3051          VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr()))
3052       lastBlock = addStmt(VA->getSizeExpr());
3053   }
3054   return lastBlock;
3055 }
3056 
3057 /// VisitStmtExpr - Utility method to handle (nested) statement
3058 ///  expressions (a GCC extension).
VisitStmtExpr(StmtExpr * SE,AddStmtChoice asc)3059 CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
3060   if (asc.alwaysAdd(*this, SE)) {
3061     autoCreateBlock();
3062     appendStmt(Block, SE);
3063   }
3064   return VisitCompoundStmt(SE->getSubStmt());
3065 }
3066 
VisitSwitchStmt(SwitchStmt * Terminator)3067 CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
3068   // "switch" is a control-flow statement.  Thus we stop processing the current
3069   // block.
3070   CFGBlock *SwitchSuccessor = nullptr;
3071 
3072   // Save local scope position because in case of condition variable ScopePos
3073   // won't be restored when traversing AST.
3074   SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3075 
3076   // Create local scope for C++17 switch init-stmt if one exists.
3077   if (Stmt *Init = Terminator->getInit()) {
3078     LocalScope::const_iterator BeginScopePos = ScopePos;
3079     addLocalScopeForStmt(Init);
3080     addAutomaticObjDtors(ScopePos, BeginScopePos, Terminator);
3081   }
3082 
3083   // Create local scope for possible condition variable.
3084   // Store scope position. Add implicit destructor.
3085   if (VarDecl *VD = Terminator->getConditionVariable()) {
3086     LocalScope::const_iterator SwitchBeginScopePos = ScopePos;
3087     addLocalScopeForVarDecl(VD);
3088     addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator);
3089   }
3090 
3091   if (Block) {
3092     if (badCFG)
3093       return nullptr;
3094     SwitchSuccessor = Block;
3095   } else SwitchSuccessor = Succ;
3096 
3097   // Save the current "switch" context.
3098   SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
3099                             save_default(DefaultCaseBlock);
3100   SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
3101 
3102   // Set the "default" case to be the block after the switch statement.  If the
3103   // switch statement contains a "default:", this value will be overwritten with
3104   // the block for that code.
3105   DefaultCaseBlock = SwitchSuccessor;
3106 
3107   // Create a new block that will contain the switch statement.
3108   SwitchTerminatedBlock = createBlock(false);
3109 
3110   // Now process the switch body.  The code after the switch is the implicit
3111   // successor.
3112   Succ = SwitchSuccessor;
3113   BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
3114 
3115   // When visiting the body, the case statements should automatically get linked
3116   // up to the switch.  We also don't keep a pointer to the body, since all
3117   // control-flow from the switch goes to case/default statements.
3118   assert(Terminator->getBody() && "switch must contain a non-NULL body");
3119   Block = nullptr;
3120 
3121   // For pruning unreachable case statements, save the current state
3122   // for tracking the condition value.
3123   SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered,
3124                                                      false);
3125 
3126   // Determine if the switch condition can be explicitly evaluated.
3127   assert(Terminator->getCond() && "switch condition must be non-NULL");
3128   Expr::EvalResult result;
3129   bool b = tryEvaluate(Terminator->getCond(), result);
3130   SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond,
3131                                                     b ? &result : nullptr);
3132 
3133   // If body is not a compound statement create implicit scope
3134   // and add destructors.
3135   if (!isa<CompoundStmt>(Terminator->getBody()))
3136     addLocalScopeAndDtors(Terminator->getBody());
3137 
3138   addStmt(Terminator->getBody());
3139   if (Block) {
3140     if (badCFG)
3141       return nullptr;
3142   }
3143 
3144   // If we have no "default:" case, the default transition is to the code
3145   // following the switch body.  Moreover, take into account if all the
3146   // cases of a switch are covered (e.g., switching on an enum value).
3147   //
3148   // Note: We add a successor to a switch that is considered covered yet has no
3149   //       case statements if the enumeration has no enumerators.
3150   bool SwitchAlwaysHasSuccessor = false;
3151   SwitchAlwaysHasSuccessor |= switchExclusivelyCovered;
3152   SwitchAlwaysHasSuccessor |= Terminator->isAllEnumCasesCovered() &&
3153                               Terminator->getSwitchCaseList();
3154   addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock,
3155                !SwitchAlwaysHasSuccessor);
3156 
3157   // Add the terminator and condition in the switch block.
3158   SwitchTerminatedBlock->setTerminator(Terminator);
3159   Block = SwitchTerminatedBlock;
3160   CFGBlock *LastBlock = addStmt(Terminator->getCond());
3161 
3162   // If the SwitchStmt contains a condition variable, add both the
3163   // SwitchStmt and the condition variable initialization to the CFG.
3164   if (VarDecl *VD = Terminator->getConditionVariable()) {
3165     if (Expr *Init = VD->getInit()) {
3166       autoCreateBlock();
3167       appendStmt(Block, Terminator->getConditionVariableDeclStmt());
3168       LastBlock = addStmt(Init);
3169     }
3170   }
3171 
3172   // Finally, if the SwitchStmt contains a C++17 init-stmt, add it to the CFG.
3173   if (Stmt *Init = Terminator->getInit()) {
3174     autoCreateBlock();
3175     LastBlock = addStmt(Init);
3176   }
3177 
3178   return LastBlock;
3179 }
3180 
shouldAddCase(bool & switchExclusivelyCovered,const Expr::EvalResult * switchCond,const CaseStmt * CS,ASTContext & Ctx)3181 static bool shouldAddCase(bool &switchExclusivelyCovered,
3182                           const Expr::EvalResult *switchCond,
3183                           const CaseStmt *CS,
3184                           ASTContext &Ctx) {
3185   if (!switchCond)
3186     return true;
3187 
3188   bool addCase = false;
3189 
3190   if (!switchExclusivelyCovered) {
3191     if (switchCond->Val.isInt()) {
3192       // Evaluate the LHS of the case value.
3193       const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
3194       const llvm::APSInt &condInt = switchCond->Val.getInt();
3195 
3196       if (condInt == lhsInt) {
3197         addCase = true;
3198         switchExclusivelyCovered = true;
3199       }
3200       else if (condInt > lhsInt) {
3201         if (const Expr *RHS = CS->getRHS()) {
3202           // Evaluate the RHS of the case value.
3203           const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
3204           if (V2 >= condInt) {
3205             addCase = true;
3206             switchExclusivelyCovered = true;
3207           }
3208         }
3209       }
3210     }
3211     else
3212       addCase = true;
3213   }
3214   return addCase;
3215 }
3216 
VisitCaseStmt(CaseStmt * CS)3217 CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
3218   // CaseStmts are essentially labels, so they are the first statement in a
3219   // block.
3220   CFGBlock *TopBlock = nullptr, *LastBlock = nullptr;
3221 
3222   if (Stmt *Sub = CS->getSubStmt()) {
3223     // For deeply nested chains of CaseStmts, instead of doing a recursion
3224     // (which can blow out the stack), manually unroll and create blocks
3225     // along the way.
3226     while (isa<CaseStmt>(Sub)) {
3227       CFGBlock *currentBlock = createBlock(false);
3228       currentBlock->setLabel(CS);
3229 
3230       if (TopBlock)
3231         addSuccessor(LastBlock, currentBlock);
3232       else
3233         TopBlock = currentBlock;
3234 
3235       addSuccessor(SwitchTerminatedBlock,
3236                    shouldAddCase(switchExclusivelyCovered, switchCond,
3237                                  CS, *Context)
3238                    ? currentBlock : nullptr);
3239 
3240       LastBlock = currentBlock;
3241       CS = cast<CaseStmt>(Sub);
3242       Sub = CS->getSubStmt();
3243     }
3244 
3245     addStmt(Sub);
3246   }
3247 
3248   CFGBlock *CaseBlock = Block;
3249   if (!CaseBlock)
3250     CaseBlock = createBlock();
3251 
3252   // Cases statements partition blocks, so this is the top of the basic block we
3253   // were processing (the "case XXX:" is the label).
3254   CaseBlock->setLabel(CS);
3255 
3256   if (badCFG)
3257     return nullptr;
3258 
3259   // Add this block to the list of successors for the block with the switch
3260   // statement.
3261   assert(SwitchTerminatedBlock);
3262   addSuccessor(SwitchTerminatedBlock, CaseBlock,
3263                shouldAddCase(switchExclusivelyCovered, switchCond,
3264                              CS, *Context));
3265 
3266   // We set Block to NULL to allow lazy creation of a new block (if necessary)
3267   Block = nullptr;
3268 
3269   if (TopBlock) {
3270     addSuccessor(LastBlock, CaseBlock);
3271     Succ = TopBlock;
3272   } else {
3273     // This block is now the implicit successor of other blocks.
3274     Succ = CaseBlock;
3275   }
3276 
3277   return Succ;
3278 }
3279 
VisitDefaultStmt(DefaultStmt * Terminator)3280 CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
3281   if (Terminator->getSubStmt())
3282     addStmt(Terminator->getSubStmt());
3283 
3284   DefaultCaseBlock = Block;
3285 
3286   if (!DefaultCaseBlock)
3287     DefaultCaseBlock = createBlock();
3288 
3289   // Default statements partition blocks, so this is the top of the basic block
3290   // we were processing (the "default:" is the label).
3291   DefaultCaseBlock->setLabel(Terminator);
3292 
3293   if (badCFG)
3294     return nullptr;
3295 
3296   // Unlike case statements, we don't add the default block to the successors
3297   // for the switch statement immediately.  This is done when we finish
3298   // processing the switch statement.  This allows for the default case
3299   // (including a fall-through to the code after the switch statement) to always
3300   // be the last successor of a switch-terminated block.
3301 
3302   // We set Block to NULL to allow lazy creation of a new block (if necessary)
3303   Block = nullptr;
3304 
3305   // This block is now the implicit successor of other blocks.
3306   Succ = DefaultCaseBlock;
3307 
3308   return DefaultCaseBlock;
3309 }
3310 
VisitCXXTryStmt(CXXTryStmt * Terminator)3311 CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
3312   // "try"/"catch" is a control-flow statement.  Thus we stop processing the
3313   // current block.
3314   CFGBlock *TrySuccessor = nullptr;
3315 
3316   if (Block) {
3317     if (badCFG)
3318       return nullptr;
3319     TrySuccessor = Block;
3320   } else TrySuccessor = Succ;
3321 
3322   CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
3323 
3324   // Create a new block that will contain the try statement.
3325   CFGBlock *NewTryTerminatedBlock = createBlock(false);
3326   // Add the terminator in the try block.
3327   NewTryTerminatedBlock->setTerminator(Terminator);
3328 
3329   bool HasCatchAll = false;
3330   for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) {
3331     // The code after the try is the implicit successor.
3332     Succ = TrySuccessor;
3333     CXXCatchStmt *CS = Terminator->getHandler(h);
3334     if (CS->getExceptionDecl() == nullptr) {
3335       HasCatchAll = true;
3336     }
3337     Block = nullptr;
3338     CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);
3339     if (!CatchBlock)
3340       return nullptr;
3341     // Add this block to the list of successors for the block with the try
3342     // statement.
3343     addSuccessor(NewTryTerminatedBlock, CatchBlock);
3344   }
3345   if (!HasCatchAll) {
3346     if (PrevTryTerminatedBlock)
3347       addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);
3348     else
3349       addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
3350   }
3351 
3352   // The code after the try is the implicit successor.
3353   Succ = TrySuccessor;
3354 
3355   // Save the current "try" context.
3356   SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock);
3357   cfg->addTryDispatchBlock(TryTerminatedBlock);
3358 
3359   assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
3360   Block = nullptr;
3361   return addStmt(Terminator->getTryBlock());
3362 }
3363 
VisitCXXCatchStmt(CXXCatchStmt * CS)3364 CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
3365   // CXXCatchStmt are treated like labels, so they are the first statement in a
3366   // block.
3367 
3368   // Save local scope position because in case of exception variable ScopePos
3369   // won't be restored when traversing AST.
3370   SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3371 
3372   // Create local scope for possible exception variable.
3373   // Store scope position. Add implicit destructor.
3374   if (VarDecl *VD = CS->getExceptionDecl()) {
3375     LocalScope::const_iterator BeginScopePos = ScopePos;
3376     addLocalScopeForVarDecl(VD);
3377     addAutomaticObjDtors(ScopePos, BeginScopePos, CS);
3378   }
3379 
3380   if (CS->getHandlerBlock())
3381     addStmt(CS->getHandlerBlock());
3382 
3383   CFGBlock *CatchBlock = Block;
3384   if (!CatchBlock)
3385     CatchBlock = createBlock();
3386 
3387   // CXXCatchStmt is more than just a label.  They have semantic meaning
3388   // as well, as they implicitly "initialize" the catch variable.  Add
3389   // it to the CFG as a CFGElement so that the control-flow of these
3390   // semantics gets captured.
3391   appendStmt(CatchBlock, CS);
3392 
3393   // Also add the CXXCatchStmt as a label, to mirror handling of regular
3394   // labels.
3395   CatchBlock->setLabel(CS);
3396 
3397   // Bail out if the CFG is bad.
3398   if (badCFG)
3399     return nullptr;
3400 
3401   // We set Block to NULL to allow lazy creation of a new block (if necessary)
3402   Block = nullptr;
3403 
3404   return CatchBlock;
3405 }
3406 
VisitCXXForRangeStmt(CXXForRangeStmt * S)3407 CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
3408   // C++0x for-range statements are specified as [stmt.ranged]:
3409   //
3410   // {
3411   //   auto && __range = range-init;
3412   //   for ( auto __begin = begin-expr,
3413   //         __end = end-expr;
3414   //         __begin != __end;
3415   //         ++__begin ) {
3416   //     for-range-declaration = *__begin;
3417   //     statement
3418   //   }
3419   // }
3420 
3421   // Save local scope position before the addition of the implicit variables.
3422   SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
3423 
3424   // Create local scopes and destructors for range, begin and end variables.
3425   if (Stmt *Range = S->getRangeStmt())
3426     addLocalScopeForStmt(Range);
3427   if (Stmt *Begin = S->getBeginStmt())
3428     addLocalScopeForStmt(Begin);
3429   if (Stmt *End = S->getEndStmt())
3430     addLocalScopeForStmt(End);
3431   addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S);
3432 
3433   LocalScope::const_iterator ContinueScopePos = ScopePos;
3434 
3435   // "for" is a control-flow statement.  Thus we stop processing the current
3436   // block.
3437   CFGBlock *LoopSuccessor = nullptr;
3438   if (Block) {
3439     if (badCFG)
3440       return nullptr;
3441     LoopSuccessor = Block;
3442   } else
3443     LoopSuccessor = Succ;
3444 
3445   // Save the current value for the break targets.
3446   // All breaks should go to the code following the loop.
3447   SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
3448   BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
3449 
3450   // The block for the __begin != __end expression.
3451   CFGBlock *ConditionBlock = createBlock(false);
3452   ConditionBlock->setTerminator(S);
3453 
3454   // Now add the actual condition to the condition block.
3455   if (Expr *C = S->getCond()) {
3456     Block = ConditionBlock;
3457     CFGBlock *BeginConditionBlock = addStmt(C);
3458     if (badCFG)
3459       return nullptr;
3460     assert(BeginConditionBlock == ConditionBlock &&
3461            "condition block in for-range was unexpectedly complex");
3462     (void)BeginConditionBlock;
3463   }
3464 
3465   // The condition block is the implicit successor for the loop body as well as
3466   // any code above the loop.
3467   Succ = ConditionBlock;
3468 
3469   // See if this is a known constant.
3470   TryResult KnownVal(true);
3471 
3472   if (S->getCond())
3473     KnownVal = tryEvaluateBool(S->getCond());
3474 
3475   // Now create the loop body.
3476   {
3477     assert(S->getBody());
3478 
3479     // Save the current values for Block, Succ, and continue targets.
3480     SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
3481     SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
3482 
3483     // Generate increment code in its own basic block.  This is the target of
3484     // continue statements.
3485     Block = nullptr;
3486     Succ = addStmt(S->getInc());
3487     if (badCFG)
3488       return nullptr;
3489     ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
3490 
3491     // The starting block for the loop increment is the block that should
3492     // represent the 'loop target' for looping back to the start of the loop.
3493     ContinueJumpTarget.block->setLoopTarget(S);
3494 
3495     // Finish up the increment block and prepare to start the loop body.
3496     assert(Block);
3497     if (badCFG)
3498       return nullptr;
3499     Block = nullptr;
3500 
3501     // Add implicit scope and dtors for loop variable.
3502     addLocalScopeAndDtors(S->getLoopVarStmt());
3503 
3504     // Populate a new block to contain the loop body and loop variable.
3505     addStmt(S->getBody());
3506     if (badCFG)
3507       return nullptr;
3508     CFGBlock *LoopVarStmtBlock = addStmt(S->getLoopVarStmt());
3509     if (badCFG)
3510       return nullptr;
3511 
3512     // This new body block is a successor to our condition block.
3513     addSuccessor(ConditionBlock,
3514                  KnownVal.isFalse() ? nullptr : LoopVarStmtBlock);
3515   }
3516 
3517   // Link up the condition block with the code that follows the loop (the
3518   // false branch).
3519   addSuccessor(ConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);
3520 
3521   // Add the initialization statements.
3522   Block = createBlock();
3523   addStmt(S->getBeginStmt());
3524   addStmt(S->getEndStmt());
3525   return addStmt(S->getRangeStmt());
3526 }
3527 
VisitExprWithCleanups(ExprWithCleanups * E,AddStmtChoice asc)3528 CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
3529     AddStmtChoice asc) {
3530   if (BuildOpts.AddTemporaryDtors) {
3531     // If adding implicit destructors visit the full expression for adding
3532     // destructors of temporaries.
3533     TempDtorContext Context;
3534     VisitForTemporaryDtors(E->getSubExpr(), false, Context);
3535 
3536     // Full expression has to be added as CFGStmt so it will be sequenced
3537     // before destructors of it's temporaries.
3538     asc = asc.withAlwaysAdd(true);
3539   }
3540   return Visit(E->getSubExpr(), asc);
3541 }
3542 
VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr * E,AddStmtChoice asc)3543 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
3544                                                 AddStmtChoice asc) {
3545   if (asc.alwaysAdd(*this, E)) {
3546     autoCreateBlock();
3547     appendStmt(Block, E);
3548 
3549     // We do not want to propagate the AlwaysAdd property.
3550     asc = asc.withAlwaysAdd(false);
3551   }
3552   return Visit(E->getSubExpr(), asc);
3553 }
3554 
VisitCXXConstructExpr(CXXConstructExpr * C,AddStmtChoice asc)3555 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
3556                                             AddStmtChoice asc) {
3557   autoCreateBlock();
3558   appendStmt(Block, C);
3559 
3560   return VisitChildren(C);
3561 }
3562 
VisitCXXNewExpr(CXXNewExpr * NE,AddStmtChoice asc)3563 CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,
3564                                       AddStmtChoice asc) {
3565 
3566   autoCreateBlock();
3567   appendStmt(Block, NE);
3568 
3569   if (NE->getInitializer())
3570     Block = Visit(NE->getInitializer());
3571   if (BuildOpts.AddCXXNewAllocator)
3572     appendNewAllocator(Block, NE);
3573   if (NE->isArray())
3574     Block = Visit(NE->getArraySize());
3575   for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),
3576        E = NE->placement_arg_end(); I != E; ++I)
3577     Block = Visit(*I);
3578   return Block;
3579 }
3580 
VisitCXXDeleteExpr(CXXDeleteExpr * DE,AddStmtChoice asc)3581 CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,
3582                                          AddStmtChoice asc) {
3583   autoCreateBlock();
3584   appendStmt(Block, DE);
3585   QualType DTy = DE->getDestroyedType();
3586   DTy = DTy.getNonReferenceType();
3587   CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl();
3588   if (RD) {
3589     if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())
3590       appendDeleteDtor(Block, RD, DE);
3591   }
3592 
3593   return VisitChildren(DE);
3594 }
3595 
VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr * E,AddStmtChoice asc)3596 CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
3597                                                  AddStmtChoice asc) {
3598   if (asc.alwaysAdd(*this, E)) {
3599     autoCreateBlock();
3600     appendStmt(Block, E);
3601     // We do not want to propagate the AlwaysAdd property.
3602     asc = asc.withAlwaysAdd(false);
3603   }
3604   return Visit(E->getSubExpr(), asc);
3605 }
3606 
VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr * C,AddStmtChoice asc)3607 CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
3608                                                   AddStmtChoice asc) {
3609   autoCreateBlock();
3610   appendStmt(Block, C);
3611   return VisitChildren(C);
3612 }
3613 
VisitImplicitCastExpr(ImplicitCastExpr * E,AddStmtChoice asc)3614 CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
3615                                             AddStmtChoice asc) {
3616   if (asc.alwaysAdd(*this, E)) {
3617     autoCreateBlock();
3618     appendStmt(Block, E);
3619   }
3620   return Visit(E->getSubExpr(), AddStmtChoice());
3621 }
3622 
VisitIndirectGotoStmt(IndirectGotoStmt * I)3623 CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
3624   // Lazily create the indirect-goto dispatch block if there isn't one already.
3625   CFGBlock *IBlock = cfg->getIndirectGotoBlock();
3626 
3627   if (!IBlock) {
3628     IBlock = createBlock(false);
3629     cfg->setIndirectGotoBlock(IBlock);
3630   }
3631 
3632   // IndirectGoto is a control-flow statement.  Thus we stop processing the
3633   // current block and create a new one.
3634   if (badCFG)
3635     return nullptr;
3636 
3637   Block = createBlock(false);
3638   Block->setTerminator(I);
3639   addSuccessor(Block, IBlock);
3640   return addStmt(I->getTarget());
3641 }
3642 
VisitForTemporaryDtors(Stmt * E,bool BindToTemporary,TempDtorContext & Context)3643 CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary,
3644                                              TempDtorContext &Context) {
3645   assert(BuildOpts.AddImplicitDtors && BuildOpts.AddTemporaryDtors);
3646 
3647 tryAgain:
3648   if (!E) {
3649     badCFG = true;
3650     return nullptr;
3651   }
3652   switch (E->getStmtClass()) {
3653     default:
3654       return VisitChildrenForTemporaryDtors(E, Context);
3655 
3656     case Stmt::BinaryOperatorClass:
3657       return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E),
3658                                                   Context);
3659 
3660     case Stmt::CXXBindTemporaryExprClass:
3661       return VisitCXXBindTemporaryExprForTemporaryDtors(
3662           cast<CXXBindTemporaryExpr>(E), BindToTemporary, Context);
3663 
3664     case Stmt::BinaryConditionalOperatorClass:
3665     case Stmt::ConditionalOperatorClass:
3666       return VisitConditionalOperatorForTemporaryDtors(
3667           cast<AbstractConditionalOperator>(E), BindToTemporary, Context);
3668 
3669     case Stmt::ImplicitCastExprClass:
3670       // For implicit cast we want BindToTemporary to be passed further.
3671       E = cast<CastExpr>(E)->getSubExpr();
3672       goto tryAgain;
3673 
3674     case Stmt::CXXFunctionalCastExprClass:
3675       // For functional cast we want BindToTemporary to be passed further.
3676       E = cast<CXXFunctionalCastExpr>(E)->getSubExpr();
3677       goto tryAgain;
3678 
3679     case Stmt::ParenExprClass:
3680       E = cast<ParenExpr>(E)->getSubExpr();
3681       goto tryAgain;
3682 
3683     case Stmt::MaterializeTemporaryExprClass: {
3684       const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(E);
3685       BindToTemporary = (MTE->getStorageDuration() != SD_FullExpression);
3686       SmallVector<const Expr *, 2> CommaLHSs;
3687       SmallVector<SubobjectAdjustment, 2> Adjustments;
3688       // Find the expression whose lifetime needs to be extended.
3689       E = const_cast<Expr *>(
3690           cast<MaterializeTemporaryExpr>(E)
3691               ->GetTemporaryExpr()
3692               ->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments));
3693       // Visit the skipped comma operator left-hand sides for other temporaries.
3694       for (const Expr *CommaLHS : CommaLHSs) {
3695         VisitForTemporaryDtors(const_cast<Expr *>(CommaLHS),
3696                                /*BindToTemporary=*/false, Context);
3697       }
3698       goto tryAgain;
3699     }
3700 
3701     case Stmt::BlockExprClass:
3702       // Don't recurse into blocks; their subexpressions don't get evaluated
3703       // here.
3704       return Block;
3705 
3706     case Stmt::LambdaExprClass: {
3707       // For lambda expressions, only recurse into the capture initializers,
3708       // and not the body.
3709       auto *LE = cast<LambdaExpr>(E);
3710       CFGBlock *B = Block;
3711       for (Expr *Init : LE->capture_inits()) {
3712         if (CFGBlock *R = VisitForTemporaryDtors(
3713                 Init, /*BindToTemporary=*/false, Context))
3714           B = R;
3715       }
3716       return B;
3717     }
3718 
3719     case Stmt::CXXDefaultArgExprClass:
3720       E = cast<CXXDefaultArgExpr>(E)->getExpr();
3721       goto tryAgain;
3722 
3723     case Stmt::CXXDefaultInitExprClass:
3724       E = cast<CXXDefaultInitExpr>(E)->getExpr();
3725       goto tryAgain;
3726   }
3727 }
3728 
VisitChildrenForTemporaryDtors(Stmt * E,TempDtorContext & Context)3729 CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E,
3730                                                      TempDtorContext &Context) {
3731   if (isa<LambdaExpr>(E)) {
3732     // Do not visit the children of lambdas; they have their own CFGs.
3733     return Block;
3734   }
3735 
3736   // When visiting children for destructors we want to visit them in reverse
3737   // order that they will appear in the CFG.  Because the CFG is built
3738   // bottom-up, this means we visit them in their natural order, which
3739   // reverses them in the CFG.
3740   CFGBlock *B = Block;
3741   for (Stmt *Child : E->children())
3742     if (Child)
3743       if (CFGBlock *R = VisitForTemporaryDtors(Child, false, Context))
3744         B = R;
3745 
3746   return B;
3747 }
3748 
VisitBinaryOperatorForTemporaryDtors(BinaryOperator * E,TempDtorContext & Context)3749 CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(
3750     BinaryOperator *E, TempDtorContext &Context) {
3751   if (E->isLogicalOp()) {
3752     VisitForTemporaryDtors(E->getLHS(), false, Context);
3753     TryResult RHSExecuted = tryEvaluateBool(E->getLHS());
3754     if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr)
3755       RHSExecuted.negate();
3756 
3757     // We do not know at CFG-construction time whether the right-hand-side was
3758     // executed, thus we add a branch node that depends on the temporary
3759     // constructor call.
3760     TempDtorContext RHSContext(
3761         bothKnownTrue(Context.KnownExecuted, RHSExecuted));
3762     VisitForTemporaryDtors(E->getRHS(), false, RHSContext);
3763     InsertTempDtorDecisionBlock(RHSContext);
3764 
3765     return Block;
3766   }
3767 
3768   if (E->isAssignmentOp()) {
3769     // For assignment operator (=) LHS expression is visited
3770     // before RHS expression. For destructors visit them in reverse order.
3771     CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);
3772     CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
3773     return LHSBlock ? LHSBlock : RHSBlock;
3774   }
3775 
3776   // For any other binary operator RHS expression is visited before
3777   // LHS expression (order of children). For destructors visit them in reverse
3778   // order.
3779   CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);
3780   CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);
3781   return RHSBlock ? RHSBlock : LHSBlock;
3782 }
3783 
VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr * E,bool BindToTemporary,TempDtorContext & Context)3784 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
3785     CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context) {
3786   // First add destructors for temporaries in subexpression.
3787   CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr(), false, Context);
3788   if (!BindToTemporary) {
3789     // If lifetime of temporary is not prolonged (by assigning to constant
3790     // reference) add destructor for it.
3791 
3792     const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
3793 
3794     if (Dtor->getParent()->isAnyDestructorNoReturn()) {
3795       // If the destructor is marked as a no-return destructor, we need to
3796       // create a new block for the destructor which does not have as a
3797       // successor anything built thus far. Control won't flow out of this
3798       // block.
3799       if (B) Succ = B;
3800       Block = createNoReturnBlock();
3801     } else if (Context.needsTempDtorBranch()) {
3802       // If we need to introduce a branch, we add a new block that we will hook
3803       // up to a decision block later.
3804       if (B) Succ = B;
3805       Block = createBlock();
3806     } else {
3807       autoCreateBlock();
3808     }
3809     if (Context.needsTempDtorBranch()) {
3810       Context.setDecisionPoint(Succ, E);
3811     }
3812     appendTemporaryDtor(Block, E);
3813 
3814     B = Block;
3815   }
3816   return B;
3817 }
3818 
InsertTempDtorDecisionBlock(const TempDtorContext & Context,CFGBlock * FalseSucc)3819 void CFGBuilder::InsertTempDtorDecisionBlock(const TempDtorContext &Context,
3820                                              CFGBlock *FalseSucc) {
3821   if (!Context.TerminatorExpr) {
3822     // If no temporary was found, we do not need to insert a decision point.
3823     return;
3824   }
3825   assert(Context.TerminatorExpr);
3826   CFGBlock *Decision = createBlock(false);
3827   Decision->setTerminator(CFGTerminator(Context.TerminatorExpr, true));
3828   addSuccessor(Decision, Block, !Context.KnownExecuted.isFalse());
3829   addSuccessor(Decision, FalseSucc ? FalseSucc : Context.Succ,
3830                !Context.KnownExecuted.isTrue());
3831   Block = Decision;
3832 }
3833 
VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator * E,bool BindToTemporary,TempDtorContext & Context)3834 CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
3835     AbstractConditionalOperator *E, bool BindToTemporary,
3836     TempDtorContext &Context) {
3837   VisitForTemporaryDtors(E->getCond(), false, Context);
3838   CFGBlock *ConditionBlock = Block;
3839   CFGBlock *ConditionSucc = Succ;
3840   TryResult ConditionVal = tryEvaluateBool(E->getCond());
3841   TryResult NegatedVal = ConditionVal;
3842   if (NegatedVal.isKnown()) NegatedVal.negate();
3843 
3844   TempDtorContext TrueContext(
3845       bothKnownTrue(Context.KnownExecuted, ConditionVal));
3846   VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary, TrueContext);
3847   CFGBlock *TrueBlock = Block;
3848 
3849   Block = ConditionBlock;
3850   Succ = ConditionSucc;
3851   TempDtorContext FalseContext(
3852       bothKnownTrue(Context.KnownExecuted, NegatedVal));
3853   VisitForTemporaryDtors(E->getFalseExpr(), BindToTemporary, FalseContext);
3854 
3855   if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) {
3856     InsertTempDtorDecisionBlock(FalseContext, TrueBlock);
3857   } else if (TrueContext.TerminatorExpr) {
3858     Block = TrueBlock;
3859     InsertTempDtorDecisionBlock(TrueContext);
3860   } else {
3861     InsertTempDtorDecisionBlock(FalseContext);
3862   }
3863   return Block;
3864 }
3865 
3866 } // end anonymous namespace
3867 
3868 /// createBlock - Constructs and adds a new CFGBlock to the CFG.  The block has
3869 ///  no successors or predecessors.  If this is the first block created in the
3870 ///  CFG, it is automatically set to be the Entry and Exit of the CFG.
createBlock()3871 CFGBlock *CFG::createBlock() {
3872   bool first_block = begin() == end();
3873 
3874   // Create the block.
3875   CFGBlock *Mem = getAllocator().Allocate<CFGBlock>();
3876   new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this);
3877   Blocks.push_back(Mem, BlkBVC);
3878 
3879   // If this is the first block, set it as the Entry and Exit.
3880   if (first_block)
3881     Entry = Exit = &back();
3882 
3883   // Return the block.
3884   return &back();
3885 }
3886 
3887 /// buildCFG - Constructs a CFG from an AST.
buildCFG(const Decl * D,Stmt * Statement,ASTContext * C,const BuildOptions & BO)3888 std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,
3889                                    ASTContext *C, const BuildOptions &BO) {
3890   CFGBuilder Builder(C, BO);
3891   return Builder.buildCFG(D, Statement);
3892 }
3893 
3894 const CXXDestructorDecl *
getDestructorDecl(ASTContext & astContext) const3895 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
3896   switch (getKind()) {
3897     case CFGElement::Statement:
3898     case CFGElement::Initializer:
3899     case CFGElement::NewAllocator:
3900       llvm_unreachable("getDestructorDecl should only be used with "
3901                        "ImplicitDtors");
3902     case CFGElement::AutomaticObjectDtor: {
3903       const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();
3904       QualType ty = var->getType();
3905       ty = ty.getNonReferenceType();
3906       while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {
3907         ty = arrayType->getElementType();
3908       }
3909       const RecordType *recordType = ty->getAs<RecordType>();
3910       const CXXRecordDecl *classDecl =
3911       cast<CXXRecordDecl>(recordType->getDecl());
3912       return classDecl->getDestructor();
3913     }
3914     case CFGElement::DeleteDtor: {
3915       const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr();
3916       QualType DTy = DE->getDestroyedType();
3917       DTy = DTy.getNonReferenceType();
3918       const CXXRecordDecl *classDecl =
3919           astContext.getBaseElementType(DTy)->getAsCXXRecordDecl();
3920       return classDecl->getDestructor();
3921     }
3922     case CFGElement::TemporaryDtor: {
3923       const CXXBindTemporaryExpr *bindExpr =
3924         castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
3925       const CXXTemporary *temp = bindExpr->getTemporary();
3926       return temp->getDestructor();
3927     }
3928     case CFGElement::BaseDtor:
3929     case CFGElement::MemberDtor:
3930 
3931       // Not yet supported.
3932       return nullptr;
3933   }
3934   llvm_unreachable("getKind() returned bogus value");
3935 }
3936 
isNoReturn(ASTContext & astContext) const3937 bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const {
3938   if (const CXXDestructorDecl *DD = getDestructorDecl(astContext))
3939     return DD->isNoReturn();
3940   return false;
3941 }
3942 
3943 //===----------------------------------------------------------------------===//
3944 // CFGBlock operations.
3945 //===----------------------------------------------------------------------===//
3946 
AdjacentBlock(CFGBlock * B,bool IsReachable)3947 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable)
3948   : ReachableBlock(IsReachable ? B : nullptr),
3949     UnreachableBlock(!IsReachable ? B : nullptr,
3950                      B && IsReachable ? AB_Normal : AB_Unreachable) {}
3951 
AdjacentBlock(CFGBlock * B,CFGBlock * AlternateBlock)3952 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock)
3953   : ReachableBlock(B),
3954     UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock,
3955                      B == AlternateBlock ? AB_Alternate : AB_Normal) {}
3956 
addSuccessor(AdjacentBlock Succ,BumpVectorContext & C)3957 void CFGBlock::addSuccessor(AdjacentBlock Succ,
3958                             BumpVectorContext &C) {
3959   if (CFGBlock *B = Succ.getReachableBlock())
3960     B->Preds.push_back(AdjacentBlock(this, Succ.isReachable()), C);
3961 
3962   if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock())
3963     UnreachableB->Preds.push_back(AdjacentBlock(this, false), C);
3964 
3965   Succs.push_back(Succ, C);
3966 }
3967 
FilterEdge(const CFGBlock::FilterOptions & F,const CFGBlock * From,const CFGBlock * To)3968 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
3969         const CFGBlock *From, const CFGBlock *To) {
3970 
3971   if (F.IgnoreNullPredecessors && !From)
3972     return true;
3973 
3974   if (To && From && F.IgnoreDefaultsWithCoveredEnums) {
3975     // If the 'To' has no label or is labeled but the label isn't a
3976     // CaseStmt then filter this edge.
3977     if (const SwitchStmt *S =
3978         dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) {
3979       if (S->isAllEnumCasesCovered()) {
3980         const Stmt *L = To->getLabel();
3981         if (!L || !isa<CaseStmt>(L))
3982           return true;
3983       }
3984     }
3985   }
3986 
3987   return false;
3988 }
3989 
3990 //===----------------------------------------------------------------------===//
3991 // CFG pretty printing
3992 //===----------------------------------------------------------------------===//
3993 
3994 namespace {
3995 
3996 class StmtPrinterHelper : public PrinterHelper  {
3997   typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy;
3998   typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy;
3999   StmtMapTy StmtMap;
4000   DeclMapTy DeclMap;
4001   signed currentBlock;
4002   unsigned currStmt;
4003   const LangOptions &LangOpts;
4004 public:
4005 
StmtPrinterHelper(const CFG * cfg,const LangOptions & LO)4006   StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
4007     : currentBlock(0), currStmt(0), LangOpts(LO)
4008   {
4009     for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
4010       unsigned j = 1;
4011       for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
4012            BI != BEnd; ++BI, ++j ) {
4013         if (Optional<CFGStmt> SE = BI->getAs<CFGStmt>()) {
4014           const Stmt *stmt= SE->getStmt();
4015           std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
4016           StmtMap[stmt] = P;
4017 
4018           switch (stmt->getStmtClass()) {
4019             case Stmt::DeclStmtClass:
4020                 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;
4021                 break;
4022             case Stmt::IfStmtClass: {
4023               const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();
4024               if (var)
4025                 DeclMap[var] = P;
4026               break;
4027             }
4028             case Stmt::ForStmtClass: {
4029               const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();
4030               if (var)
4031                 DeclMap[var] = P;
4032               break;
4033             }
4034             case Stmt::WhileStmtClass: {
4035               const VarDecl *var =
4036                 cast<WhileStmt>(stmt)->getConditionVariable();
4037               if (var)
4038                 DeclMap[var] = P;
4039               break;
4040             }
4041             case Stmt::SwitchStmtClass: {
4042               const VarDecl *var =
4043                 cast<SwitchStmt>(stmt)->getConditionVariable();
4044               if (var)
4045                 DeclMap[var] = P;
4046               break;
4047             }
4048             case Stmt::CXXCatchStmtClass: {
4049               const VarDecl *var =
4050                 cast<CXXCatchStmt>(stmt)->getExceptionDecl();
4051               if (var)
4052                 DeclMap[var] = P;
4053               break;
4054             }
4055             default:
4056               break;
4057           }
4058         }
4059       }
4060     }
4061   }
4062 
~StmtPrinterHelper()4063   ~StmtPrinterHelper() override {}
4064 
getLangOpts() const4065   const LangOptions &getLangOpts() const { return LangOpts; }
setBlockID(signed i)4066   void setBlockID(signed i) { currentBlock = i; }
setStmtID(unsigned i)4067   void setStmtID(unsigned i) { currStmt = i; }
4068 
handledStmt(Stmt * S,raw_ostream & OS)4069   bool handledStmt(Stmt *S, raw_ostream &OS) override {
4070     StmtMapTy::iterator I = StmtMap.find(S);
4071 
4072     if (I == StmtMap.end())
4073       return false;
4074 
4075     if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
4076                           && I->second.second == currStmt) {
4077       return false;
4078     }
4079 
4080     OS << "[B" << I->second.first << "." << I->second.second << "]";
4081     return true;
4082   }
4083 
handleDecl(const Decl * D,raw_ostream & OS)4084   bool handleDecl(const Decl *D, raw_ostream &OS) {
4085     DeclMapTy::iterator I = DeclMap.find(D);
4086 
4087     if (I == DeclMap.end())
4088       return false;
4089 
4090     if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
4091                           && I->second.second == currStmt) {
4092       return false;
4093     }
4094 
4095     OS << "[B" << I->second.first << "." << I->second.second << "]";
4096     return true;
4097   }
4098 };
4099 } // end anonymous namespace
4100 
4101 
4102 namespace {
4103 class CFGBlockTerminatorPrint
4104   : public StmtVisitor<CFGBlockTerminatorPrint,void> {
4105 
4106   raw_ostream &OS;
4107   StmtPrinterHelper* Helper;
4108   PrintingPolicy Policy;
4109 public:
CFGBlockTerminatorPrint(raw_ostream & os,StmtPrinterHelper * helper,const PrintingPolicy & Policy)4110   CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
4111                           const PrintingPolicy &Policy)
4112     : OS(os), Helper(helper), Policy(Policy) {
4113     this->Policy.IncludeNewlines = false;
4114   }
4115 
VisitIfStmt(IfStmt * I)4116   void VisitIfStmt(IfStmt *I) {
4117     OS << "if ";
4118     if (Stmt *C = I->getCond())
4119       C->printPretty(OS, Helper, Policy);
4120   }
4121 
4122   // Default case.
VisitStmt(Stmt * Terminator)4123   void VisitStmt(Stmt *Terminator) {
4124     Terminator->printPretty(OS, Helper, Policy);
4125   }
4126 
VisitDeclStmt(DeclStmt * DS)4127   void VisitDeclStmt(DeclStmt *DS) {
4128     VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());
4129     OS << "static init " << VD->getName();
4130   }
4131 
VisitForStmt(ForStmt * F)4132   void VisitForStmt(ForStmt *F) {
4133     OS << "for (" ;
4134     if (F->getInit())
4135       OS << "...";
4136     OS << "; ";
4137     if (Stmt *C = F->getCond())
4138       C->printPretty(OS, Helper, Policy);
4139     OS << "; ";
4140     if (F->getInc())
4141       OS << "...";
4142     OS << ")";
4143   }
4144 
VisitWhileStmt(WhileStmt * W)4145   void VisitWhileStmt(WhileStmt *W) {
4146     OS << "while " ;
4147     if (Stmt *C = W->getCond())
4148       C->printPretty(OS, Helper, Policy);
4149   }
4150 
VisitDoStmt(DoStmt * D)4151   void VisitDoStmt(DoStmt *D) {
4152     OS << "do ... while ";
4153     if (Stmt *C = D->getCond())
4154       C->printPretty(OS, Helper, Policy);
4155   }
4156 
VisitSwitchStmt(SwitchStmt * Terminator)4157   void VisitSwitchStmt(SwitchStmt *Terminator) {
4158     OS << "switch ";
4159     Terminator->getCond()->printPretty(OS, Helper, Policy);
4160   }
4161 
VisitCXXTryStmt(CXXTryStmt * CS)4162   void VisitCXXTryStmt(CXXTryStmt *CS) {
4163     OS << "try ...";
4164   }
4165 
VisitAbstractConditionalOperator(AbstractConditionalOperator * C)4166   void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
4167     if (Stmt *Cond = C->getCond())
4168       Cond->printPretty(OS, Helper, Policy);
4169     OS << " ? ... : ...";
4170   }
4171 
VisitChooseExpr(ChooseExpr * C)4172   void VisitChooseExpr(ChooseExpr *C) {
4173     OS << "__builtin_choose_expr( ";
4174     if (Stmt *Cond = C->getCond())
4175       Cond->printPretty(OS, Helper, Policy);
4176     OS << " )";
4177   }
4178 
VisitIndirectGotoStmt(IndirectGotoStmt * I)4179   void VisitIndirectGotoStmt(IndirectGotoStmt *I) {
4180     OS << "goto *";
4181     if (Stmt *T = I->getTarget())
4182       T->printPretty(OS, Helper, Policy);
4183   }
4184 
VisitBinaryOperator(BinaryOperator * B)4185   void VisitBinaryOperator(BinaryOperator* B) {
4186     if (!B->isLogicalOp()) {
4187       VisitExpr(B);
4188       return;
4189     }
4190 
4191     if (B->getLHS())
4192       B->getLHS()->printPretty(OS, Helper, Policy);
4193 
4194     switch (B->getOpcode()) {
4195       case BO_LOr:
4196         OS << " || ...";
4197         return;
4198       case BO_LAnd:
4199         OS << " && ...";
4200         return;
4201       default:
4202         llvm_unreachable("Invalid logical operator.");
4203     }
4204   }
4205 
VisitExpr(Expr * E)4206   void VisitExpr(Expr *E) {
4207     E->printPretty(OS, Helper, Policy);
4208   }
4209 
4210 public:
print(CFGTerminator T)4211   void print(CFGTerminator T) {
4212     if (T.isTemporaryDtorsBranch())
4213       OS << "(Temp Dtor) ";
4214     Visit(T.getStmt());
4215   }
4216 };
4217 } // end anonymous namespace
4218 
print_elem(raw_ostream & OS,StmtPrinterHelper & Helper,const CFGElement & E)4219 static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,
4220                        const CFGElement &E) {
4221   if (Optional<CFGStmt> CS = E.getAs<CFGStmt>()) {
4222     const Stmt *S = CS->getStmt();
4223     assert(S != nullptr && "Expecting non-null Stmt");
4224 
4225     // special printing for statement-expressions.
4226     if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) {
4227       const CompoundStmt *Sub = SE->getSubStmt();
4228 
4229       auto Children = Sub->children();
4230       if (Children.begin() != Children.end()) {
4231         OS << "({ ... ; ";
4232         Helper.handledStmt(*SE->getSubStmt()->body_rbegin(),OS);
4233         OS << " })\n";
4234         return;
4235       }
4236     }
4237     // special printing for comma expressions.
4238     if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
4239       if (B->getOpcode() == BO_Comma) {
4240         OS << "... , ";
4241         Helper.handledStmt(B->getRHS(),OS);
4242         OS << '\n';
4243         return;
4244       }
4245     }
4246     S->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));
4247 
4248     if (isa<CXXOperatorCallExpr>(S)) {
4249       OS << " (OperatorCall)";
4250     }
4251     else if (isa<CXXBindTemporaryExpr>(S)) {
4252       OS << " (BindTemporary)";
4253     }
4254     else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) {
4255       OS << " (CXXConstructExpr, " << CCE->getType().getAsString() << ")";
4256     }
4257     else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) {
4258       OS << " (" << CE->getStmtClassName() << ", "
4259          << CE->getCastKindName()
4260          << ", " << CE->getType().getAsString()
4261          << ")";
4262     }
4263 
4264     // Expressions need a newline.
4265     if (isa<Expr>(S))
4266       OS << '\n';
4267 
4268   } else if (Optional<CFGInitializer> IE = E.getAs<CFGInitializer>()) {
4269     const CXXCtorInitializer *I = IE->getInitializer();
4270     if (I->isBaseInitializer())
4271       OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
4272     else if (I->isDelegatingInitializer())
4273       OS << I->getTypeSourceInfo()->getType()->getAsCXXRecordDecl()->getName();
4274     else OS << I->getAnyMember()->getName();
4275 
4276     OS << "(";
4277     if (Expr *IE = I->getInit())
4278       IE->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));
4279     OS << ")";
4280 
4281     if (I->isBaseInitializer())
4282       OS << " (Base initializer)\n";
4283     else if (I->isDelegatingInitializer())
4284       OS << " (Delegating initializer)\n";
4285     else OS << " (Member initializer)\n";
4286 
4287   } else if (Optional<CFGAutomaticObjDtor> DE =
4288                  E.getAs<CFGAutomaticObjDtor>()) {
4289     const VarDecl *VD = DE->getVarDecl();
4290     Helper.handleDecl(VD, OS);
4291 
4292     const Type* T = VD->getType().getTypePtr();
4293     if (const ReferenceType* RT = T->getAs<ReferenceType>())
4294       T = RT->getPointeeType().getTypePtr();
4295     T = T->getBaseElementTypeUnsafe();
4296 
4297     OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()";
4298     OS << " (Implicit destructor)\n";
4299 
4300   } else if (Optional<CFGNewAllocator> NE = E.getAs<CFGNewAllocator>()) {
4301     OS << "CFGNewAllocator(";
4302     if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr())
4303       AllocExpr->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
4304     OS << ")\n";
4305   } else if (Optional<CFGDeleteDtor> DE = E.getAs<CFGDeleteDtor>()) {
4306     const CXXRecordDecl *RD = DE->getCXXRecordDecl();
4307     if (!RD)
4308       return;
4309     CXXDeleteExpr *DelExpr =
4310         const_cast<CXXDeleteExpr*>(DE->getDeleteExpr());
4311     Helper.handledStmt(cast<Stmt>(DelExpr->getArgument()), OS);
4312     OS << "->~" << RD->getName().str() << "()";
4313     OS << " (Implicit destructor)\n";
4314   } else if (Optional<CFGBaseDtor> BE = E.getAs<CFGBaseDtor>()) {
4315     const CXXBaseSpecifier *BS = BE->getBaseSpecifier();
4316     OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
4317     OS << " (Base object destructor)\n";
4318 
4319   } else if (Optional<CFGMemberDtor> ME = E.getAs<CFGMemberDtor>()) {
4320     const FieldDecl *FD = ME->getFieldDecl();
4321     const Type *T = FD->getType()->getBaseElementTypeUnsafe();
4322     OS << "this->" << FD->getName();
4323     OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
4324     OS << " (Member object destructor)\n";
4325 
4326   } else if (Optional<CFGTemporaryDtor> TE = E.getAs<CFGTemporaryDtor>()) {
4327     const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr();
4328     OS << "~";
4329     BT->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));
4330     OS << "() (Temporary object destructor)\n";
4331   }
4332 }
4333 
print_block(raw_ostream & OS,const CFG * cfg,const CFGBlock & B,StmtPrinterHelper & Helper,bool print_edges,bool ShowColors)4334 static void print_block(raw_ostream &OS, const CFG* cfg,
4335                         const CFGBlock &B,
4336                         StmtPrinterHelper &Helper, bool print_edges,
4337                         bool ShowColors) {
4338 
4339   Helper.setBlockID(B.getBlockID());
4340 
4341   // Print the header.
4342   if (ShowColors)
4343     OS.changeColor(raw_ostream::YELLOW, true);
4344 
4345   OS << "\n [B" << B.getBlockID();
4346 
4347   if (&B == &cfg->getEntry())
4348     OS << " (ENTRY)]\n";
4349   else if (&B == &cfg->getExit())
4350     OS << " (EXIT)]\n";
4351   else if (&B == cfg->getIndirectGotoBlock())
4352     OS << " (INDIRECT GOTO DISPATCH)]\n";
4353   else if (B.hasNoReturnElement())
4354     OS << " (NORETURN)]\n";
4355   else
4356     OS << "]\n";
4357 
4358   if (ShowColors)
4359     OS.resetColor();
4360 
4361   // Print the label of this block.
4362   if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {
4363 
4364     if (print_edges)
4365       OS << "  ";
4366 
4367     if (LabelStmt *L = dyn_cast<LabelStmt>(Label))
4368       OS << L->getName();
4369     else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
4370       OS << "case ";
4371       if (C->getLHS())
4372         C->getLHS()->printPretty(OS, &Helper,
4373                                  PrintingPolicy(Helper.getLangOpts()));
4374       if (C->getRHS()) {
4375         OS << " ... ";
4376         C->getRHS()->printPretty(OS, &Helper,
4377                                  PrintingPolicy(Helper.getLangOpts()));
4378       }
4379     } else if (isa<DefaultStmt>(Label))
4380       OS << "default";
4381     else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) {
4382       OS << "catch (";
4383       if (CS->getExceptionDecl())
4384         CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper.getLangOpts()),
4385                                       0);
4386       else
4387         OS << "...";
4388       OS << ")";
4389 
4390     } else
4391       llvm_unreachable("Invalid label statement in CFGBlock.");
4392 
4393     OS << ":\n";
4394   }
4395 
4396   // Iterate through the statements in the block and print them.
4397   unsigned j = 1;
4398 
4399   for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
4400        I != E ; ++I, ++j ) {
4401 
4402     // Print the statement # in the basic block and the statement itself.
4403     if (print_edges)
4404       OS << " ";
4405 
4406     OS << llvm::format("%3d", j) << ": ";
4407 
4408     Helper.setStmtID(j);
4409 
4410     print_elem(OS, Helper, *I);
4411   }
4412 
4413   // Print the terminator of this block.
4414   if (B.getTerminator()) {
4415     if (ShowColors)
4416       OS.changeColor(raw_ostream::GREEN);
4417 
4418     OS << "   T: ";
4419 
4420     Helper.setBlockID(-1);
4421 
4422     PrintingPolicy PP(Helper.getLangOpts());
4423     CFGBlockTerminatorPrint TPrinter(OS, &Helper, PP);
4424     TPrinter.print(B.getTerminator());
4425     OS << '\n';
4426 
4427     if (ShowColors)
4428       OS.resetColor();
4429   }
4430 
4431   if (print_edges) {
4432     // Print the predecessors of this block.
4433     if (!B.pred_empty()) {
4434       const raw_ostream::Colors Color = raw_ostream::BLUE;
4435       if (ShowColors)
4436         OS.changeColor(Color);
4437       OS << "   Preds " ;
4438       if (ShowColors)
4439         OS.resetColor();
4440       OS << '(' << B.pred_size() << "):";
4441       unsigned i = 0;
4442 
4443       if (ShowColors)
4444         OS.changeColor(Color);
4445 
4446       for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
4447            I != E; ++I, ++i) {
4448 
4449         if (i % 10 == 8)
4450           OS << "\n     ";
4451 
4452         CFGBlock *B = *I;
4453         bool Reachable = true;
4454         if (!B) {
4455           Reachable = false;
4456           B = I->getPossiblyUnreachableBlock();
4457         }
4458 
4459         OS << " B" << B->getBlockID();
4460         if (!Reachable)
4461           OS << "(Unreachable)";
4462       }
4463 
4464       if (ShowColors)
4465         OS.resetColor();
4466 
4467       OS << '\n';
4468     }
4469 
4470     // Print the successors of this block.
4471     if (!B.succ_empty()) {
4472       const raw_ostream::Colors Color = raw_ostream::MAGENTA;
4473       if (ShowColors)
4474         OS.changeColor(Color);
4475       OS << "   Succs ";
4476       if (ShowColors)
4477         OS.resetColor();
4478       OS << '(' << B.succ_size() << "):";
4479       unsigned i = 0;
4480 
4481       if (ShowColors)
4482         OS.changeColor(Color);
4483 
4484       for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
4485            I != E; ++I, ++i) {
4486 
4487         if (i % 10 == 8)
4488           OS << "\n    ";
4489 
4490         CFGBlock *B = *I;
4491 
4492         bool Reachable = true;
4493         if (!B) {
4494           Reachable = false;
4495           B = I->getPossiblyUnreachableBlock();
4496         }
4497 
4498         if (B) {
4499           OS << " B" << B->getBlockID();
4500           if (!Reachable)
4501             OS << "(Unreachable)";
4502         }
4503         else {
4504           OS << " NULL";
4505         }
4506       }
4507 
4508       if (ShowColors)
4509         OS.resetColor();
4510       OS << '\n';
4511     }
4512   }
4513 }
4514 
4515 
4516 /// dump - A simple pretty printer of a CFG that outputs to stderr.
dump(const LangOptions & LO,bool ShowColors) const4517 void CFG::dump(const LangOptions &LO, bool ShowColors) const {
4518   print(llvm::errs(), LO, ShowColors);
4519 }
4520 
4521 /// print - A simple pretty printer of a CFG that outputs to an ostream.
print(raw_ostream & OS,const LangOptions & LO,bool ShowColors) const4522 void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
4523   StmtPrinterHelper Helper(this, LO);
4524 
4525   // Print the entry block.
4526   print_block(OS, this, getEntry(), Helper, true, ShowColors);
4527 
4528   // Iterate through the CFGBlocks and print them one by one.
4529   for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
4530     // Skip the entry block, because we already printed it.
4531     if (&(**I) == &getEntry() || &(**I) == &getExit())
4532       continue;
4533 
4534     print_block(OS, this, **I, Helper, true, ShowColors);
4535   }
4536 
4537   // Print the exit block.
4538   print_block(OS, this, getExit(), Helper, true, ShowColors);
4539   OS << '\n';
4540   OS.flush();
4541 }
4542 
4543 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
dump(const CFG * cfg,const LangOptions & LO,bool ShowColors) const4544 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
4545                     bool ShowColors) const {
4546   print(llvm::errs(), cfg, LO, ShowColors);
4547 }
4548 
dump() const4549 LLVM_DUMP_METHOD void CFGBlock::dump() const {
4550   dump(getParent(), LangOptions(), false);
4551 }
4552 
4553 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
4554 ///   Generally this will only be called from CFG::print.
print(raw_ostream & OS,const CFG * cfg,const LangOptions & LO,bool ShowColors) const4555 void CFGBlock::print(raw_ostream &OS, const CFG* cfg,
4556                      const LangOptions &LO, bool ShowColors) const {
4557   StmtPrinterHelper Helper(cfg, LO);
4558   print_block(OS, cfg, *this, Helper, true, ShowColors);
4559   OS << '\n';
4560 }
4561 
4562 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
printTerminator(raw_ostream & OS,const LangOptions & LO) const4563 void CFGBlock::printTerminator(raw_ostream &OS,
4564                                const LangOptions &LO) const {
4565   CFGBlockTerminatorPrint TPrinter(OS, nullptr, PrintingPolicy(LO));
4566   TPrinter.print(getTerminator());
4567 }
4568 
getTerminatorCondition(bool StripParens)4569 Stmt *CFGBlock::getTerminatorCondition(bool StripParens) {
4570   Stmt *Terminator = this->Terminator;
4571   if (!Terminator)
4572     return nullptr;
4573 
4574   Expr *E = nullptr;
4575 
4576   switch (Terminator->getStmtClass()) {
4577     default:
4578       break;
4579 
4580     case Stmt::CXXForRangeStmtClass:
4581       E = cast<CXXForRangeStmt>(Terminator)->getCond();
4582       break;
4583 
4584     case Stmt::ForStmtClass:
4585       E = cast<ForStmt>(Terminator)->getCond();
4586       break;
4587 
4588     case Stmt::WhileStmtClass:
4589       E = cast<WhileStmt>(Terminator)->getCond();
4590       break;
4591 
4592     case Stmt::DoStmtClass:
4593       E = cast<DoStmt>(Terminator)->getCond();
4594       break;
4595 
4596     case Stmt::IfStmtClass:
4597       E = cast<IfStmt>(Terminator)->getCond();
4598       break;
4599 
4600     case Stmt::ChooseExprClass:
4601       E = cast<ChooseExpr>(Terminator)->getCond();
4602       break;
4603 
4604     case Stmt::IndirectGotoStmtClass:
4605       E = cast<IndirectGotoStmt>(Terminator)->getTarget();
4606       break;
4607 
4608     case Stmt::SwitchStmtClass:
4609       E = cast<SwitchStmt>(Terminator)->getCond();
4610       break;
4611 
4612     case Stmt::BinaryConditionalOperatorClass:
4613       E = cast<BinaryConditionalOperator>(Terminator)->getCond();
4614       break;
4615 
4616     case Stmt::ConditionalOperatorClass:
4617       E = cast<ConditionalOperator>(Terminator)->getCond();
4618       break;
4619 
4620     case Stmt::BinaryOperatorClass: // '&&' and '||'
4621       E = cast<BinaryOperator>(Terminator)->getLHS();
4622       break;
4623 
4624     case Stmt::ObjCForCollectionStmtClass:
4625       return Terminator;
4626   }
4627 
4628   if (!StripParens)
4629     return E;
4630 
4631   return E ? E->IgnoreParens() : nullptr;
4632 }
4633 
4634 //===----------------------------------------------------------------------===//
4635 // CFG Graphviz Visualization
4636 //===----------------------------------------------------------------------===//
4637 
4638 
4639 #ifndef NDEBUG
4640 static StmtPrinterHelper* GraphHelper;
4641 #endif
4642 
viewCFG(const LangOptions & LO) const4643 void CFG::viewCFG(const LangOptions &LO) const {
4644 #ifndef NDEBUG
4645   StmtPrinterHelper H(this, LO);
4646   GraphHelper = &H;
4647   llvm::ViewGraph(this,"CFG");
4648   GraphHelper = nullptr;
4649 #endif
4650 }
4651 
4652 namespace llvm {
4653 template<>
4654 struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
4655 
DOTGraphTraitsllvm::DOTGraphTraits4656   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
4657 
getNodeLabelllvm::DOTGraphTraits4658   static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) {
4659 
4660 #ifndef NDEBUG
4661     std::string OutSStr;
4662     llvm::raw_string_ostream Out(OutSStr);
4663     print_block(Out,Graph, *Node, *GraphHelper, false, false);
4664     std::string& OutStr = Out.str();
4665 
4666     if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
4667 
4668     // Process string output to make it nicer...
4669     for (unsigned i = 0; i != OutStr.length(); ++i)
4670       if (OutStr[i] == '\n') {                            // Left justify
4671         OutStr[i] = '\\';
4672         OutStr.insert(OutStr.begin()+i+1, 'l');
4673       }
4674 
4675     return OutStr;
4676 #else
4677     return "";
4678 #endif
4679   }
4680 };
4681 } // end namespace llvm
4682