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