include/clang/Analysis/CFG.h

   1 //===- CFG.h - Classes for representing and building CFGs -------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines the CFG and CFGBuilder classes for representing and
  10 //  building Control-Flow Graphs (CFGs) from ASTs.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_ANALYSIS_CFG_H
  15 #define LLVM_CLANG_ANALYSIS_CFG_H
  16
  17 #include "clang/Analysis/Support/BumpVector.h"
  18 #include "clang/Analysis/ConstructionContext.h"
  19 #include "clang/AST/ExprCXX.h"
  20 #include "clang/AST/ExprObjC.h"
  21 #include "clang/Basic/LLVM.h"
  22 #include "llvm/ADT/DenseMap.h"
  23 #include "llvm/ADT/GraphTraits.h"
  24 #include "llvm/ADT/None.h"
  25 #include "llvm/ADT/Optional.h"
  26 #include "llvm/ADT/PointerIntPair.h"
  27 #include "llvm/ADT/iterator_range.h"
  28 #include "llvm/Support/Allocator.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include <bitset>
  31 #include <cassert>
  32 #include <cstddef>
  33 #include <iterator>
  34 #include <memory>
  35 #include <vector>
  36
  37 namespace clang {
  38
  39 class ASTContext;
  40 class BinaryOperator;
  41 class CFG;
  42 class CXXBaseSpecifier;
  43 class CXXBindTemporaryExpr;
  44 class CXXCtorInitializer;
  45 class CXXDeleteExpr;
  46 class CXXDestructorDecl;
  47 class CXXNewExpr;
  48 class CXXRecordDecl;
  49 class Decl;
  50 class FieldDecl;
  51 class LangOptions;
  52 class VarDecl;
  53
  54 /// Represents a top-level expression in a basic block.
  55 class CFGElement {
  56 public:
  57   enum Kind {
  58     // main kind
  59     Initializer,
  60     ScopeBegin,
  61     ScopeEnd,
  62     NewAllocator,
  63     LifetimeEnds,
  64     LoopExit,
  65     // stmt kind
  66     Statement,
  67     Constructor,
  68     CXXRecordTypedCall,
  69     STMT_BEGIN = Statement,
  70     STMT_END = CXXRecordTypedCall,
  71     // dtor kind
  72     AutomaticObjectDtor,
  73     DeleteDtor,
  74     BaseDtor,
  75     MemberDtor,
  76     TemporaryDtor,
  77     DTOR_BEGIN = AutomaticObjectDtor,
  78     DTOR_END = TemporaryDtor
  79   };
  80
  81 protected:
  82   // The int bits are used to mark the kind.
  83   llvm::PointerIntPair<void *, 2> Data1;
  84   llvm::PointerIntPair<void *, 2> Data2;
  85
  86   CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr)
  87       : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),
  88         Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {
  89     assert(getKind() == kind);
  90   }
  91
  92   CFGElement() = default;
  93
  94 public:
  95   /// Convert to the specified CFGElement type, asserting that this
  96   /// CFGElement is of the desired type.
  97   template<typename T>
  98   T castAs() const {
  99     assert(T::isKind(*this));
 100     T t;
 101     CFGElement& e = t;
 102     e = *this;
 103     return t;
 104   }
 105
 106   /// Convert to the specified CFGElement type, returning None if this
 107   /// CFGElement is not of the desired type.
 108   template<typename T>
 109   Optional<T> getAs() const {
 110     if (!T::isKind(*this))
 111       return None;
 112     T t;
 113     CFGElement& e = t;
 114     e = *this;
 115     return t;
 116   }
 117
 118   Kind getKind() const {
 119     unsigned x = Data2.getInt();
 120     x <<= 2;
 121     x |= Data1.getInt();
 122     return (Kind) x;
 123   }
 124
 125   void dumpToStream(llvm::raw_ostream &OS) const;
 126
 127   void dump() const {
 128     dumpToStream(llvm::errs());
 129   }
 130 };
 131
 132 class CFGStmt : public CFGElement {
 133 public:
 134   explicit CFGStmt(Stmt *S, Kind K = Statement) : CFGElement(K, S) {
 135     assert(isKind(*this));
 136   }
 137
 138   const Stmt *getStmt() const {
 139     return static_cast<const Stmt *>(Data1.getPointer());
 140   }
 141
 142 private:
 143   friend class CFGElement;
 144
 145   static bool isKind(const CFGElement &E) {
 146     return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END;
 147   }
 148
 149 protected:
 150   CFGStmt() = default;
 151 };
 152
 153 /// Represents C++ constructor call. Maintains information necessary to figure
 154 /// out what memory is being initialized by the constructor expression. For now
 155 /// this is only used by the analyzer's CFG.
 156 class CFGConstructor : public CFGStmt {
 157 public:
 158   explicit CFGConstructor(CXXConstructExpr *CE, const ConstructionContext *C)
 159       : CFGStmt(CE, Constructor) {
 160     assert(C);
 161     Data2.setPointer(const_cast<ConstructionContext *>(C));
 162   }
 163
 164   const ConstructionContext *getConstructionContext() const {
 165     return static_cast<ConstructionContext *>(Data2.getPointer());
 166   }
 167
 168 private:
 169   friend class CFGElement;
 170
 171   CFGConstructor() = default;
 172
 173   static bool isKind(const CFGElement &E) {
 174     return E.getKind() == Constructor;
 175   }
 176 };
 177
 178 /// Represents a function call that returns a C++ object by value. This, like
 179 /// constructor, requires a construction context in order to understand the
 180 /// storage of the returned object . In C such tracking is not necessary because
 181 /// no additional effort is required for destroying the object or modeling copy
 182 /// elision. Like CFGConstructor, this element is for now only used by the
 183 /// analyzer's CFG.
 184 class CFGCXXRecordTypedCall : public CFGStmt {
 185 public:
 186   /// Returns true when call expression \p CE needs to be represented
 187   /// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt.
 188   static bool isCXXRecordTypedCall(Expr *E) {
 189     assert(isa<CallExpr>(E) || isa<ObjCMessageExpr>(E));
 190     // There is no such thing as reference-type expression. If the function
 191     // returns a reference, it'll return the respective lvalue or xvalue
 192     // instead, and we're only interested in objects.
 193     return !E->isGLValue() &&
 194            E->getType().getCanonicalType()->getAsCXXRecordDecl();
 195   }
 196
 197   explicit CFGCXXRecordTypedCall(Expr *E, const ConstructionContext *C)
 198       : CFGStmt(E, CXXRecordTypedCall) {
 199     assert(isCXXRecordTypedCall(E));
 200     assert(C && (isa<TemporaryObjectConstructionContext>(C) ||
 201                  // These are possible in C++17 due to mandatory copy elision.
 202                  isa<ReturnedValueConstructionContext>(C) ||
 203                  isa<VariableConstructionContext>(C) ||
 204                  isa<ConstructorInitializerConstructionContext>(C) ||
 205                  isa<ArgumentConstructionContext>(C)));
 206     Data2.setPointer(const_cast<ConstructionContext *>(C));
 207   }
 208
 209   const ConstructionContext *getConstructionContext() const {
 210     return static_cast<ConstructionContext *>(Data2.getPointer());
 211   }
 212
 213 private:
 214   friend class CFGElement;
 215
 216   CFGCXXRecordTypedCall() = default;
 217
 218   static bool isKind(const CFGElement &E) {
 219     return E.getKind() == CXXRecordTypedCall;
 220   }
 221 };
 222
 223 /// Represents C++ base or member initializer from constructor's initialization
 224 /// list.
 225 class CFGInitializer : public CFGElement {
 226 public:
 227   explicit CFGInitializer(CXXCtorInitializer *initializer)
 228       : CFGElement(Initializer, initializer) {}
 229
 230   CXXCtorInitializer* getInitializer() const {
 231     return static_cast<CXXCtorInitializer*>(Data1.getPointer());
 232   }
 233
 234 private:
 235   friend class CFGElement;
 236
 237   CFGInitializer() = default;
 238
 239   static bool isKind(const CFGElement &E) {
 240     return E.getKind() == Initializer;
 241   }
 242 };
 243
 244 /// Represents C++ allocator call.
 245 class CFGNewAllocator : public CFGElement {
 246 public:
 247   explicit CFGNewAllocator(const CXXNewExpr *S)
 248     : CFGElement(NewAllocator, S) {}
 249
 250   // Get the new expression.
 251   const CXXNewExpr *getAllocatorExpr() const {
 252     return static_cast<CXXNewExpr *>(Data1.getPointer());
 253   }
 254
 255 private:
 256   friend class CFGElement;
 257
 258   CFGNewAllocator() = default;
 259
 260   static bool isKind(const CFGElement &elem) {
 261     return elem.getKind() == NewAllocator;
 262   }
 263 };
 264
 265 /// Represents the point where a loop ends.
 266 /// This element is is only produced when building the CFG for the static
 267 /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.
 268 ///
 269 /// Note: a loop exit element can be reached even when the loop body was never
 270 /// entered.
 271 class CFGLoopExit : public CFGElement {
 272 public:
 273   explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {}
 274
 275   const Stmt *getLoopStmt() const {
 276     return static_cast<Stmt *>(Data1.getPointer());
 277   }
 278
 279 private:
 280   friend class CFGElement;
 281
 282   CFGLoopExit() = default;
 283
 284   static bool isKind(const CFGElement &elem) {
 285     return elem.getKind() == LoopExit;
 286   }
 287 };
 288
 289 /// Represents the point where the lifetime of an automatic object ends
 290 class CFGLifetimeEnds : public CFGElement {
 291 public:
 292   explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt)
 293       : CFGElement(LifetimeEnds, var, stmt) {}
 294
 295   const VarDecl *getVarDecl() const {
 296     return static_cast<VarDecl *>(Data1.getPointer());
 297   }
 298
 299   const Stmt *getTriggerStmt() const {
 300     return static_cast<Stmt *>(Data2.getPointer());
 301   }
 302
 303 private:
 304   friend class CFGElement;
 305
 306   CFGLifetimeEnds() = default;
 307
 308   static bool isKind(const CFGElement &elem) {
 309     return elem.getKind() == LifetimeEnds;
 310   }
 311 };
 312
 313 /// Represents beginning of a scope implicitly generated
 314 /// by the compiler on encountering a CompoundStmt
 315 class CFGScopeBegin : public CFGElement {
 316 public:
 317   CFGScopeBegin() {}
 318   CFGScopeBegin(const VarDecl *VD, const Stmt *S)
 319       : CFGElement(ScopeBegin, VD, S) {}
 320
 321   // Get statement that triggered a new scope.
 322   const Stmt *getTriggerStmt() const {
 323     return static_cast<Stmt*>(Data2.getPointer());
 324   }
 325
 326   // Get VD that triggered a new scope.
 327   const VarDecl *getVarDecl() const {
 328     return static_cast<VarDecl *>(Data1.getPointer());
 329   }
 330
 331 private:
 332   friend class CFGElement;
 333   static bool isKind(const CFGElement &E) {
 334     Kind kind = E.getKind();
 335     return kind == ScopeBegin;
 336   }
 337 };
 338
 339 /// Represents end of a scope implicitly generated by
 340 /// the compiler after the last Stmt in a CompoundStmt's body
 341 class CFGScopeEnd : public CFGElement {
 342 public:
 343   CFGScopeEnd() {}
 344   CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {}
 345
 346   const VarDecl *getVarDecl() const {
 347     return static_cast<VarDecl *>(Data1.getPointer());
 348   }
 349
 350   const Stmt *getTriggerStmt() const {
 351     return static_cast<Stmt *>(Data2.getPointer());
 352   }
 353
 354 private:
 355   friend class CFGElement;
 356   static bool isKind(const CFGElement &E) {
 357     Kind kind = E.getKind();
 358     return kind == ScopeEnd;
 359   }
 360 };
 361
 362 /// Represents C++ object destructor implicitly generated by compiler on various
 363 /// occasions.
 364 class CFGImplicitDtor : public CFGElement {
 365 protected:
 366   CFGImplicitDtor() = default;
 367
 368   CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr)
 369     : CFGElement(kind, data1, data2) {
 370     assert(kind >= DTOR_BEGIN && kind <= DTOR_END);
 371   }
 372
 373 public:
 374   const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const;
 375   bool isNoReturn(ASTContext &astContext) const;
 376
 377 private:
 378   friend class CFGElement;
 379
 380   static bool isKind(const CFGElement &E) {
 381     Kind kind = E.getKind();
 382     return kind >= DTOR_BEGIN && kind <= DTOR_END;
 383   }
 384 };
 385
 386 /// Represents C++ object destructor implicitly generated for automatic object
 387 /// or temporary bound to const reference at the point of leaving its local
 388 /// scope.
 389 class CFGAutomaticObjDtor: public CFGImplicitDtor {
 390 public:
 391   CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)
 392       : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {}
 393
 394   const VarDecl *getVarDecl() const {
 395     return static_cast<VarDecl*>(Data1.getPointer());
 396   }
 397
 398   // Get statement end of which triggered the destructor call.
 399   const Stmt *getTriggerStmt() const {
 400     return static_cast<Stmt*>(Data2.getPointer());
 401   }
 402
 403 private:
 404   friend class CFGElement;
 405
 406   CFGAutomaticObjDtor() = default;
 407
 408   static bool isKind(const CFGElement &elem) {
 409     return elem.getKind() == AutomaticObjectDtor;
 410   }
 411 };
 412
 413 /// Represents C++ object destructor generated from a call to delete.
 414 class CFGDeleteDtor : public CFGImplicitDtor {
 415 public:
 416   CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE)
 417       : CFGImplicitDtor(DeleteDtor, RD, DE) {}
 418
 419   const CXXRecordDecl *getCXXRecordDecl() const {
 420     return static_cast<CXXRecordDecl*>(Data1.getPointer());
 421   }
 422
 423   // Get Delete expression which triggered the destructor call.
 424   const CXXDeleteExpr *getDeleteExpr() const {
 425     return static_cast<CXXDeleteExpr *>(Data2.getPointer());
 426   }
 427
 428 private:
 429   friend class CFGElement;
 430
 431   CFGDeleteDtor() = default;
 432
 433   static bool isKind(const CFGElement &elem) {
 434     return elem.getKind() == DeleteDtor;
 435   }
 436 };
 437
 438 /// Represents C++ object destructor implicitly generated for base object in
 439 /// destructor.
 440 class CFGBaseDtor : public CFGImplicitDtor {
 441 public:
 442   CFGBaseDtor(const CXXBaseSpecifier *base)
 443       : CFGImplicitDtor(BaseDtor, base) {}
 444
 445   const CXXBaseSpecifier *getBaseSpecifier() const {
 446     return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());
 447   }
 448
 449 private:
 450   friend class CFGElement;
 451
 452   CFGBaseDtor() = default;
 453
 454   static bool isKind(const CFGElement &E) {
 455     return E.getKind() == BaseDtor;
 456   }
 457 };
 458
 459 /// Represents C++ object destructor implicitly generated for member object in
 460 /// destructor.
 461 class CFGMemberDtor : public CFGImplicitDtor {
 462 public:
 463   CFGMemberDtor(const FieldDecl *field)
 464       : CFGImplicitDtor(MemberDtor, field, nullptr) {}
 465
 466   const FieldDecl *getFieldDecl() const {
 467     return static_cast<const FieldDecl*>(Data1.getPointer());
 468   }
 469
 470 private:
 471   friend class CFGElement;
 472
 473   CFGMemberDtor() = default;
 474
 475   static bool isKind(const CFGElement &E) {
 476     return E.getKind() == MemberDtor;
 477   }
 478 };
 479
 480 /// Represents C++ object destructor implicitly generated at the end of full
 481 /// expression for temporary object.
 482 class CFGTemporaryDtor : public CFGImplicitDtor {
 483 public:
 484   CFGTemporaryDtor(CXXBindTemporaryExpr *expr)
 485       : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {}
 486
 487   const CXXBindTemporaryExpr *getBindTemporaryExpr() const {
 488     return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer());
 489   }
 490
 491 private:
 492   friend class CFGElement;
 493
 494   CFGTemporaryDtor() = default;
 495
 496   static bool isKind(const CFGElement &E) {
 497     return E.getKind() == TemporaryDtor;
 498   }
 499 };
 500
 501 /// Represents CFGBlock terminator statement.
 502 ///
 503 class CFGTerminator {
 504 public:
 505   enum Kind {
 506     /// A branch that corresponds to a statement in the code,
 507     /// such as an if-statement.
 508     StmtBranch,
 509     /// A branch in control flow of destructors of temporaries. In this case
 510     /// terminator statement is the same statement that branches control flow
 511     /// in evaluation of matching full expression.
 512     TemporaryDtorsBranch,
 513     /// A shortcut around virtual base initializers. It gets taken when
 514     /// virtual base classes have already been initialized by the constructor
 515     /// of the most derived class while we're in the base class.
 516     VirtualBaseBranch,
 517
 518     /// Number of different kinds, for sanity checks. We subtract 1 so that
 519     /// to keep receiving compiler warnings when we don't cover all enum values
 520     /// in a switch.
 521     NumKindsMinusOne = VirtualBaseBranch
 522   };
 523
 524 private:
 525   static constexpr int KindBits = 2;
 526   static_assert((1 << KindBits) > NumKindsMinusOne,
 527                 "Not enough room for kind!");
 528   llvm::PointerIntPair<Stmt *, KindBits> Data;
 529
 530 public:
 531   CFGTerminator() { assert(!isValid()); }
 532   CFGTerminator(Stmt *S, Kind K = StmtBranch) : Data(S, K) {}
 533
 534   bool isValid() const { return Data.getOpaqueValue() != nullptr; }
 535   Stmt *getStmt() { return Data.getPointer(); }
 536   const Stmt *getStmt() const { return Data.getPointer(); }
 537   Kind getKind() const { return static_cast<Kind>(Data.getInt()); }
 538
 539   bool isStmtBranch() const {
 540     return getKind() == StmtBranch;
 541   }
 542   bool isTemporaryDtorsBranch() const {
 543     return getKind() == TemporaryDtorsBranch;
 544   }
 545   bool isVirtualBaseBranch() const {
 546     return getKind() == VirtualBaseBranch;
 547   }
 548 };
 549
 550 /// Represents a single basic block in a source-level CFG.
 551 ///  It consists of:
 552 ///
 553 ///  (1) A set of statements/expressions (which may contain subexpressions).
 554 ///  (2) A "terminator" statement (not in the set of statements).
 555 ///  (3) A list of successors and predecessors.
 556 ///
 557 /// Terminator: The terminator represents the type of control-flow that occurs
 558 /// at the end of the basic block.  The terminator is a Stmt* referring to an
 559 /// AST node that has control-flow: if-statements, breaks, loops, etc.
 560 /// If the control-flow is conditional, the condition expression will appear
 561 /// within the set of statements in the block (usually the last statement).
 562 ///
 563 /// Predecessors: the order in the set of predecessors is arbitrary.
 564 ///
 565 /// Successors: the order in the set of successors is NOT arbitrary.  We
 566 ///  currently have the following orderings based on the terminator:
 567 ///
 568 ///     Terminator     |   Successor Ordering
 569 ///  ------------------|------------------------------------
 570 ///       if           |  Then Block;  Else Block
 571 ///     ? operator     |  LHS expression;  RHS expression
 572 ///     logical and/or |  expression that consumes the op, RHS
 573 ///     vbase inits    |  already handled by the most derived class; not yet
 574 ///
 575 /// But note that any of that may be NULL in case of optimized-out edges.
 576 class CFGBlock {
 577   class ElementList {
 578     using ImplTy = BumpVector<CFGElement>;
 579
 580     ImplTy Impl;
 581
 582   public:
 583     ElementList(BumpVectorContext &C) : Impl(C, 4) {}
 584
 585     using iterator = std::reverse_iterator<ImplTy::iterator>;
 586     using const_iterator = std::reverse_iterator<ImplTy::const_iterator>;
 587     using reverse_iterator = ImplTy::iterator;
 588     using const_reverse_iterator = ImplTy::const_iterator;
 589     using const_reference = ImplTy::const_reference;
 590
 591     void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
 592
 593     reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
 594         BumpVectorContext &C) {
 595       return Impl.insert(I, Cnt, E, C);
 596     }
 597
 598     const_reference front() const { return Impl.back(); }
 599     const_reference back() const { return Impl.front(); }
 600
 601     iterator begin() { return Impl.rbegin(); }
 602     iterator end() { return Impl.rend(); }
 603     const_iterator begin() const { return Impl.rbegin(); }
 604     const_iterator end() const { return Impl.rend(); }
 605     reverse_iterator rbegin() { return Impl.begin(); }
 606     reverse_iterator rend() { return Impl.end(); }
 607     const_reverse_iterator rbegin() const { return Impl.begin(); }
 608     const_reverse_iterator rend() const { return Impl.end(); }
 609
 610     CFGElement operator[](size_t i) const  {
 611       assert(i < Impl.size());
 612       return Impl[Impl.size() - 1 - i];
 613     }
 614
 615     size_t size() const { return Impl.size(); }
 616     bool empty() const { return Impl.empty(); }
 617   };
 618
 619   /// A convenience class for comparing CFGElements, since methods of CFGBlock
 620   /// like operator[] return CFGElements by value. This is practically a wrapper
 621   /// around a (CFGBlock, Index) pair.
 622   template <bool IsConst> class ElementRefImpl {
 623
 624     template <bool IsOtherConst> friend class ElementRefImpl;
 625
 626     using CFGBlockPtr =
 627         typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
 628
 629     using CFGElementPtr = typename std::conditional<IsConst, const CFGElement *,
 630                                                     CFGElement *>::type;
 631
 632   protected:
 633     CFGBlockPtr Parent;
 634     size_t Index;
 635
 636   public:
 637     ElementRefImpl(CFGBlockPtr Parent, size_t Index)
 638         : Parent(Parent), Index(Index) {}
 639
 640     template <bool IsOtherConst>
 641     ElementRefImpl(ElementRefImpl<IsOtherConst> Other)
 642         : ElementRefImpl(Other.Parent, Other.Index) {}
 643
 644     size_t getIndexInBlock() const { return Index; }
 645
 646     CFGBlockPtr getParent() { return Parent; }
 647     CFGBlockPtr getParent() const { return Parent; }
 648
 649     bool operator<(ElementRefImpl Other) const {
 650       return std::make_pair(Parent, Index) <
 651              std::make_pair(Other.Parent, Other.Index);
 652     }
 653
 654     bool operator==(ElementRefImpl Other) const {
 655       return Parent == Other.Parent && Index == Other.Index;
 656     }
 657
 658     bool operator!=(ElementRefImpl Other) const { return !(*this == Other); }
 659     CFGElement operator*() const { return (*Parent)[Index]; }
 660     CFGElementPtr operator->() const { return &*(Parent->begin() + Index); }
 661
 662     void dumpToStream(llvm::raw_ostream &OS) const {
 663       OS << getIndexInBlock() + 1 << ": ";
 664       (*this)->dumpToStream(OS);
 665     }
 666
 667     void dump() const {
 668       dumpToStream(llvm::errs());
 669     }
 670   };
 671
 672   template <bool IsReverse, bool IsConst> class ElementRefIterator {
 673
 674     template <bool IsOtherReverse, bool IsOtherConst>
 675     friend class ElementRefIterator;
 676
 677     using CFGBlockRef =
 678         typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
 679
 680     using UnderlayingIteratorTy = typename std::conditional<
 681         IsConst,
 682         typename std::conditional<IsReverse,
 683                                   ElementList::const_reverse_iterator,
 684                                   ElementList::const_iterator>::type,
 685         typename std::conditional<IsReverse, ElementList::reverse_iterator,
 686                                   ElementList::iterator>::type>::type;
 687
 688     using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>;
 689     using ElementRef = typename CFGBlock::ElementRefImpl<IsConst>;
 690
 691   public:
 692     using difference_type = typename IteratorTraits::difference_type;
 693     using value_type = ElementRef;
 694     using pointer = ElementRef *;
 695     using iterator_category = typename IteratorTraits::iterator_category;
 696
 697   private:
 698     CFGBlockRef Parent;
 699     UnderlayingIteratorTy Pos;
 700
 701   public:
 702     ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos)
 703         : Parent(Parent), Pos(Pos) {}
 704
 705     template <bool IsOtherConst>
 706     ElementRefIterator(ElementRefIterator<false, IsOtherConst> E)
 707         : ElementRefIterator(E.Parent, E.Pos.base()) {}
 708
 709     template <bool IsOtherConst>
 710     ElementRefIterator(ElementRefIterator<true, IsOtherConst> E)
 711         : ElementRefIterator(E.Parent, llvm::make_reverse_iterator(E.Pos)) {}
 712
 713     bool operator<(ElementRefIterator Other) const {
 714       assert(Parent == Other.Parent);
 715       return Pos < Other.Pos;
 716     }
 717
 718     bool operator==(ElementRefIterator Other) const {
 719       return Parent == Other.Parent && Pos == Other.Pos;
 720     }
 721
 722     bool operator!=(ElementRefIterator Other) const {
 723       return !(*this == Other);
 724     }
 725
 726   private:
 727     template <bool IsOtherConst>
 728     static size_t
 729     getIndexInBlock(CFGBlock::ElementRefIterator<true, IsOtherConst> E) {
 730       return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1;
 731     }
 732
 733     template <bool IsOtherConst>
 734     static size_t
 735     getIndexInBlock(CFGBlock::ElementRefIterator<false, IsOtherConst> E) {
 736       return E.Pos - E.Parent->begin();
 737     }
 738
 739   public:
 740     value_type operator*() { return {Parent, getIndexInBlock(*this)}; }
 741
 742     difference_type operator-(ElementRefIterator Other) const {
 743       return Pos - Other.Pos;
 744     }
 745
 746     ElementRefIterator operator++() {
 747       ++this->Pos;
 748       return *this;
 749     }
 750     ElementRefIterator operator++(int) {
 751       ElementRefIterator Ret = *this;
 752       ++*this;
 753       return Ret;
 754     }
 755     ElementRefIterator operator+(size_t count) {
 756       this->Pos += count;
 757       return *this;
 758     }
 759     ElementRefIterator operator-(size_t count) {
 760       this->Pos -= count;
 761       return *this;
 762     }
 763   };
 764
 765 public:
 766   /// The set of statements in the basic block.
 767   ElementList Elements;
 768
 769   /// An (optional) label that prefixes the executable statements in the block.
 770   /// When this variable is non-NULL, it is either an instance of LabelStmt,
 771   /// SwitchCase or CXXCatchStmt.
 772   Stmt *Label = nullptr;
 773
 774   /// The terminator for a basic block that indicates the type of control-flow
 775   /// that occurs between a block and its successors.
 776   CFGTerminator Terminator;
 777
 778   /// Some blocks are used to represent the "loop edge" to the start of a loop
 779   /// from within the loop body. This Stmt* will be refer to the loop statement
 780   /// for such blocks (and be null otherwise).
 781   const Stmt *LoopTarget = nullptr;
 782
 783   /// A numerical ID assigned to a CFGBlock during construction of the CFG.
 784   unsigned BlockID;
 785
 786 public:
 787   /// This class represents a potential adjacent block in the CFG.  It encodes
 788   /// whether or not the block is actually reachable, or can be proved to be
 789   /// trivially unreachable.  For some cases it allows one to encode scenarios
 790   /// where a block was substituted because the original (now alternate) block
 791   /// is unreachable.
 792   class AdjacentBlock {
 793     enum Kind {
 794       AB_Normal,
 795       AB_Unreachable,
 796       AB_Alternate
 797     };
 798
 799     CFGBlock *ReachableBlock;
 800     llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock;
 801
 802   public:
 803     /// Construct an AdjacentBlock with a possibly unreachable block.
 804     AdjacentBlock(CFGBlock *B, bool IsReachable);
 805
 806     /// Construct an AdjacentBlock with a reachable block and an alternate
 807     /// unreachable block.
 808     AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock);
 809
 810     /// Get the reachable block, if one exists.
 811     CFGBlock *getReachableBlock() const {
 812       return ReachableBlock;
 813     }
 814
 815     /// Get the potentially unreachable block.
 816     CFGBlock *getPossiblyUnreachableBlock() const {
 817       return UnreachableBlock.getPointer();
 818     }
 819
 820     /// Provide an implicit conversion to CFGBlock* so that
 821     /// AdjacentBlock can be substituted for CFGBlock*.
 822     operator CFGBlock*() const {
 823       return getReachableBlock();
 824     }
 825
 826     CFGBlock& operator *() const {
 827       return *getReachableBlock();
 828     }
 829
 830     CFGBlock* operator ->() const {
 831       return getReachableBlock();
 832     }
 833
 834     bool isReachable() const {
 835       Kind K = (Kind) UnreachableBlock.getInt();
 836       return K == AB_Normal || K == AB_Alternate;
 837     }
 838   };
 839
 840 private:
 841   /// Keep track of the predecessor / successor CFG blocks.
 842   using AdjacentBlocks = BumpVector<AdjacentBlock>;
 843   AdjacentBlocks Preds;
 844   AdjacentBlocks Succs;
 845
 846   /// This bit is set when the basic block contains a function call
 847   /// or implicit destructor that is attributed as 'noreturn'. In that case,
 848   /// control cannot technically ever proceed past this block. All such blocks
 849   /// will have a single immediate successor: the exit block. This allows them
 850   /// to be easily reached from the exit block and using this bit quickly
 851   /// recognized without scanning the contents of the block.
 852   ///
 853   /// Optimization Note: This bit could be profitably folded with Terminator's
 854   /// storage if the memory usage of CFGBlock becomes an issue.
 855   unsigned HasNoReturnElement : 1;
 856
 857   /// The parent CFG that owns this CFGBlock.
 858   CFG *Parent;
 859
 860 public:
 861   explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
 862       : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1),
 863         Succs(C, 1), HasNoReturnElement(false), Parent(parent) {}
 864
 865   // Statement iterators
 866   using iterator = ElementList::iterator;
 867   using const_iterator = ElementList::const_iterator;
 868   using reverse_iterator = ElementList::reverse_iterator;
 869   using const_reverse_iterator = ElementList::const_reverse_iterator;
 870
 871   size_t getIndexInCFG() const;
 872
 873   CFGElement                 front()       const { return Elements.front();   }
 874   CFGElement                 back()        const { return Elements.back();    }
 875
 876   iterator                   begin()             { return Elements.begin();   }
 877   iterator                   end()               { return Elements.end();     }
 878   const_iterator             begin()       const { return Elements.begin();   }
 879   const_iterator             end()         const { return Elements.end();     }
 880
 881   reverse_iterator           rbegin()            { return Elements.rbegin();  }
 882   reverse_iterator           rend()              { return Elements.rend();    }
 883   const_reverse_iterator     rbegin()      const { return Elements.rbegin();  }
 884   const_reverse_iterator     rend()        const { return Elements.rend();    }
 885
 886   using CFGElementRef = ElementRefImpl<false>;
 887   using ConstCFGElementRef = ElementRefImpl<true>;
 888
 889   using ref_iterator = ElementRefIterator<false, false>;
 890   using ref_iterator_range = llvm::iterator_range<ref_iterator>;
 891   using const_ref_iterator = ElementRefIterator<false, true>;
 892   using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>;
 893
 894   using reverse_ref_iterator = ElementRefIterator<true, false>;
 895   using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>;
 896
 897   using const_reverse_ref_iterator = ElementRefIterator<true, true>;
 898   using const_reverse_ref_iterator_range =
 899       llvm::iterator_range<const_reverse_ref_iterator>;
 900
 901   ref_iterator ref_begin() { return {this, begin()}; }
 902   ref_iterator ref_end() { return {this, end()}; }
 903   const_ref_iterator ref_begin() const { return {this, begin()}; }
 904   const_ref_iterator ref_end() const { return {this, end()}; }
 905
 906   reverse_ref_iterator rref_begin() { return {this, rbegin()}; }
 907   reverse_ref_iterator rref_end() { return {this, rend()}; }
 908   const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; }
 909   const_reverse_ref_iterator rref_end() const { return {this, rend()}; }
 910
 911   ref_iterator_range refs() { return {ref_begin(), ref_end()}; }
 912   const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; }
 913   reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; }
 914   const_reverse_ref_iterator_range rrefs() const {
 915     return {rref_begin(), rref_end()};
 916   }
 917
 918   unsigned                   size()        const { return Elements.size();    }
 919   bool                       empty()       const { return Elements.empty();   }
 920
 921   CFGElement operator[](size_t i) const  { return Elements[i]; }
 922
 923   // CFG iterators
 924   using pred_iterator = AdjacentBlocks::iterator;
 925   using const_pred_iterator = AdjacentBlocks::const_iterator;
 926   using pred_reverse_iterator = AdjacentBlocks::reverse_iterator;
 927   using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
 928   using pred_range = llvm::iterator_range<pred_iterator>;
 929   using pred_const_range = llvm::iterator_range<const_pred_iterator>;
 930
 931   using succ_iterator = AdjacentBlocks::iterator;
 932   using const_succ_iterator = AdjacentBlocks::const_iterator;
 933   using succ_reverse_iterator = AdjacentBlocks::reverse_iterator;
 934   using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
 935   using succ_range = llvm::iterator_range<succ_iterator>;
 936   using succ_const_range = llvm::iterator_range<const_succ_iterator>;
 937
 938   pred_iterator                pred_begin()        { return Preds.begin();   }
 939   pred_iterator                pred_end()          { return Preds.end();     }
 940   const_pred_iterator          pred_begin()  const { return Preds.begin();   }
 941   const_pred_iterator          pred_end()    const { return Preds.end();     }
 942
 943   pred_reverse_iterator        pred_rbegin()       { return Preds.rbegin();  }
 944   pred_reverse_iterator        pred_rend()         { return Preds.rend();    }
 945   const_pred_reverse_iterator  pred_rbegin() const { return Preds.rbegin();  }
 946   const_pred_reverse_iterator  pred_rend()   const { return Preds.rend();    }
 947
 948   pred_range preds() {
 949     return pred_range(pred_begin(), pred_end());
 950   }
 951
 952   pred_const_range preds() const {
 953     return pred_const_range(pred_begin(), pred_end());
 954   }
 955
 956   succ_iterator                succ_begin()        { return Succs.begin();   }
 957   succ_iterator                succ_end()          { return Succs.end();     }
 958   const_succ_iterator          succ_begin()  const { return Succs.begin();   }
 959   const_succ_iterator          succ_end()    const { return Succs.end();     }
 960
 961   succ_reverse_iterator        succ_rbegin()       { return Succs.rbegin();  }
 962   succ_reverse_iterator        succ_rend()         { return Succs.rend();    }
 963   const_succ_reverse_iterator  succ_rbegin() const { return Succs.rbegin();  }
 964   const_succ_reverse_iterator  succ_rend()   const { return Succs.rend();    }
 965
 966   succ_range succs() {
 967     return succ_range(succ_begin(), succ_end());
 968   }
 969
 970   succ_const_range succs() const {
 971     return succ_const_range(succ_begin(), succ_end());
 972   }
 973
 974   unsigned                     succ_size()   const { return Succs.size();    }
 975   bool                         succ_empty()  const { return Succs.empty();   }
 976
 977   unsigned                     pred_size()   const { return Preds.size();    }
 978   bool                         pred_empty()  const { return Preds.empty();   }
 979
 980
 981   class FilterOptions {
 982   public:
 983     unsigned IgnoreNullPredecessors : 1;
 984     unsigned IgnoreDefaultsWithCoveredEnums : 1;
 985
 986     FilterOptions()
 987         : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {}
 988   };
 989
 990   static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
 991        const CFGBlock *Dst);
 992
 993   template <typename IMPL, bool IsPred>
 994   class FilteredCFGBlockIterator {
 995   private:
 996     IMPL I, E;
 997     const FilterOptions F;
 998     const CFGBlock *From;
 999
1000   public:
1001     explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
1002                                       const CFGBlock *from,
1003                                       const FilterOptions &f)
1004         : I(i), E(e), F(f), From(from) {
1005       while (hasMore() && Filter(*I))
1006         ++I;
1007     }
1008
1009     bool hasMore() const { return I != E; }
1010
1011     FilteredCFGBlockIterator &operator++() {
1012       do { ++I; } while (hasMore() && Filter(*I));
1013       return *this;
1014     }
1015
1016     const CFGBlock *operator*() const { return *I; }
1017
1018   private:
1019     bool Filter(const CFGBlock *To) {
1020       return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
1021     }
1022   };
1023
1024   using filtered_pred_iterator =
1025       FilteredCFGBlockIterator<const_pred_iterator, true>;
1026
1027   using filtered_succ_iterator =
1028       FilteredCFGBlockIterator<const_succ_iterator, false>;
1029
1030   filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
1031     return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
1032   }
1033
1034   filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
1035     return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
1036   }
1037
1038   // Manipulation of block contents
1039
1040   void setTerminator(CFGTerminator Term) { Terminator = Term; }
1041   void setLabel(Stmt *Statement) { Label = Statement; }
1042   void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
1043   void setHasNoReturnElement() { HasNoReturnElement = true; }
1044
1045   /// Returns true if the block would eventually end with a sink (a noreturn
1046   /// node).
1047   bool isInevitablySinking() const;
1048
1049   CFGTerminator getTerminator() const { return Terminator; }
1050
1051   Stmt *getTerminatorStmt() { return Terminator.getStmt(); }
1052   const Stmt *getTerminatorStmt() const { return Terminator.getStmt(); }
1053
1054   /// \returns the last (\c rbegin()) condition, e.g. observe the following code
1055   /// snippet:
1056   ///   if (A && B && C)
1057   /// A block would be created for \c A, \c B, and \c C. For the latter,
1058   /// \c getTerminatorStmt() would retrieve the entire condition, rather than
1059   /// C itself, while this method would only return C.
1060   const Expr *getLastCondition() const;
1061
1062   Stmt *getTerminatorCondition(bool StripParens = true);
1063
1064   const Stmt *getTerminatorCondition(bool StripParens = true) const {
1065     return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
1066   }
1067
1068   const Stmt *getLoopTarget() const { return LoopTarget; }
1069
1070   Stmt *getLabel() { return Label; }
1071   const Stmt *getLabel() const { return Label; }
1072
1073   bool hasNoReturnElement() const { return HasNoReturnElement; }
1074
1075   unsigned getBlockID() const { return BlockID; }
1076
1077   CFG *getParent() const { return Parent; }
1078
1079   void dump() const;
1080
1081   void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
1082   void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
1083              bool ShowColors) const;
1084
1085   void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
1086   void printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
1087                            bool AddQuotes) const;
1088
1089   void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
1090     OS << "BB#" << getBlockID();
1091   }
1092
1093   /// Adds a (potentially unreachable) successor block to the current block.
1094   void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
1095
1096   void appendStmt(Stmt *statement, BumpVectorContext &C) {
1097     Elements.push_back(CFGStmt(statement), C);
1098   }
1099
1100   void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC,
1101                          BumpVectorContext &C) {
1102     Elements.push_back(CFGConstructor(CE, CC), C);
1103   }
1104
1105   void appendCXXRecordTypedCall(Expr *E,
1106                                 const ConstructionContext *CC,
1107                                 BumpVectorContext &C) {
1108     Elements.push_back(CFGCXXRecordTypedCall(E, CC), C);
1109   }
1110
1111   void appendInitializer(CXXCtorInitializer *initializer,
1112                         BumpVectorContext &C) {
1113     Elements.push_back(CFGInitializer(initializer), C);
1114   }
1115
1116   void appendNewAllocator(CXXNewExpr *NE,
1117                           BumpVectorContext &C) {
1118     Elements.push_back(CFGNewAllocator(NE), C);
1119   }
1120
1121   void appendScopeBegin(const VarDecl *VD, const Stmt *S,
1122                         BumpVectorContext &C) {
1123     Elements.push_back(CFGScopeBegin(VD, S), C);
1124   }
1125
1126   void prependScopeBegin(const VarDecl *VD, const Stmt *S,
1127                          BumpVectorContext &C) {
1128     Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C);
1129   }
1130
1131   void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
1132     Elements.push_back(CFGScopeEnd(VD, S), C);
1133   }
1134
1135   void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
1136     Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C);
1137   }
1138
1139   void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
1140     Elements.push_back(CFGBaseDtor(BS), C);
1141   }
1142
1143   void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
1144     Elements.push_back(CFGMemberDtor(FD), C);
1145   }
1146
1147   void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) {
1148     Elements.push_back(CFGTemporaryDtor(E), C);
1149   }
1150
1151   void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
1152     Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
1153   }
1154
1155   void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
1156     Elements.push_back(CFGLifetimeEnds(VD, S), C);
1157   }
1158
1159   void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
1160     Elements.push_back(CFGLoopExit(LoopStmt), C);
1161   }
1162
1163   void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) {
1164     Elements.push_back(CFGDeleteDtor(RD, DE), C);
1165   }
1166
1167   // Destructors must be inserted in reversed order. So insertion is in two
1168   // steps. First we prepare space for some number of elements, then we insert
1169   // the elements beginning at the last position in prepared space.
1170   iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt,
1171       BumpVectorContext &C) {
1172     return iterator(Elements.insert(I.base(), Cnt,
1173                                     CFGAutomaticObjDtor(nullptr, nullptr), C));
1174   }
1175   iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) {
1176     *I = CFGAutomaticObjDtor(VD, S);
1177     return ++I;
1178   }
1179
1180   // Scope leaving must be performed in reversed order. So insertion is in two
1181   // steps. First we prepare space for some number of elements, then we insert
1182   // the elements beginning at the last position in prepared space.
1183   iterator beginLifetimeEndsInsert(iterator I, size_t Cnt,
1184                                    BumpVectorContext &C) {
1185     return iterator(
1186         Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C));
1187   }
1188   iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S) {
1189     *I = CFGLifetimeEnds(VD, S);
1190     return ++I;
1191   }
1192
1193   // Scope leaving must be performed in reversed order. So insertion is in two
1194   // steps. First we prepare space for some number of elements, then we insert
1195   // the elements beginning at the last position in prepared space.
1196   iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) {
1197     return iterator(
1198         Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C));
1199   }
1200   iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S) {
1201     *I = CFGScopeEnd(VD, S);
1202     return ++I;
1203   }
1204 };
1205
1206 /// CFGCallback defines methods that should be called when a logical
1207 /// operator error is found when building the CFG.
1208 class CFGCallback {
1209 public:
1210   CFGCallback() = default;
1211   virtual ~CFGCallback() = default;
1212
1213   virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
1214   virtual void compareBitwiseEquality(const BinaryOperator *B,
1215                                       bool isAlwaysTrue) {}
1216   virtual void compareBitwiseOr(const BinaryOperator *B) {}
1217 };
1218
1219 /// Represents a source-level, intra-procedural CFG that represents the
1220 ///  control-flow of a Stmt.  The Stmt can represent an entire function body,
1221 ///  or a single expression.  A CFG will always contain one empty block that
1222 ///  represents the Exit point of the CFG.  A CFG will also contain a designated
1223 ///  Entry block.  The CFG solely represents control-flow; it consists of
1224 ///  CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
1225 ///  was constructed from.
1226 class CFG {
1227 public:
1228   //===--------------------------------------------------------------------===//
1229   // CFG Construction & Manipulation.
1230   //===--------------------------------------------------------------------===//
1231
1232   class BuildOptions {
1233     std::bitset<Stmt::lastStmtConstant> alwaysAddMask;
1234
1235   public:
1236     using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>;
1237
1238     ForcedBlkExprs **forcedBlkExprs = nullptr;
1239     CFGCallback *Observer = nullptr;
1240     bool PruneTriviallyFalseEdges = true;
1241     bool AddEHEdges = false;
1242     bool AddInitializers = false;
1243     bool AddImplicitDtors = false;
1244     bool AddLifetime = false;
1245     bool AddLoopExit = false;
1246     bool AddTemporaryDtors = false;
1247     bool AddScopes = false;
1248     bool AddStaticInitBranches = false;
1249     bool AddCXXNewAllocator = false;
1250     bool AddCXXDefaultInitExprInCtors = false;
1251     bool AddRichCXXConstructors = false;
1252     bool MarkElidedCXXConstructors = false;
1253     bool AddVirtualBaseBranches = false;
1254
1255     BuildOptions() = default;
1256
1257     bool alwaysAdd(const Stmt *stmt) const {
1258       return alwaysAddMask[stmt->getStmtClass()];
1259     }
1260
1261     BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
1262       alwaysAddMask[stmtClass] = val;
1263       return *this;
1264     }
1265
1266     BuildOptions &setAllAlwaysAdd() {
1267       alwaysAddMask.set();
1268       return *this;
1269     }
1270   };
1271
1272   /// Builds a CFG from an AST.
1273   static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
1274                                        const BuildOptions &BO);
1275
1276   /// Create a new block in the CFG. The CFG owns the block; the caller should
1277   /// not directly free it.
1278   CFGBlock *createBlock();
1279
1280   /// Set the entry block of the CFG. This is typically used only during CFG
1281   /// construction. Most CFG clients expect that the entry block has no
1282   /// predecessors and contains no statements.
1283   void setEntry(CFGBlock *B) { Entry = B; }
1284
1285   /// Set the block used for indirect goto jumps. This is typically used only
1286   /// during CFG construction.
1287   void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
1288
1289   //===--------------------------------------------------------------------===//
1290   // Block Iterators
1291   //===--------------------------------------------------------------------===//
1292
1293   using CFGBlockListTy = BumpVector<CFGBlock *>;
1294   using iterator = CFGBlockListTy::iterator;
1295   using const_iterator = CFGBlockListTy::const_iterator;
1296   using reverse_iterator = std::reverse_iterator<iterator>;
1297   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1298
1299   CFGBlock &                front()                { return *Blocks.front(); }
1300   CFGBlock &                back()                 { return *Blocks.back(); }
1301
1302   iterator                  begin()                { return Blocks.begin(); }
1303   iterator                  end()                  { return Blocks.end(); }
1304   const_iterator            begin()       const    { return Blocks.begin(); }
1305   const_iterator            end()         const    { return Blocks.end(); }
1306
1307   iterator nodes_begin() { return iterator(Blocks.begin()); }
1308   iterator nodes_end() { return iterator(Blocks.end()); }
1309   const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
1310   const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
1311
1312   reverse_iterator          rbegin()               { return Blocks.rbegin(); }
1313   reverse_iterator          rend()                 { return Blocks.rend(); }
1314   const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
1315   const_reverse_iterator    rend()        const    { return Blocks.rend(); }
1316
1317   CFGBlock &                getEntry()             { return *Entry; }
1318   const CFGBlock &          getEntry()    const    { return *Entry; }
1319   CFGBlock &                getExit()              { return *Exit; }
1320   const CFGBlock &          getExit()     const    { return *Exit; }
1321
1322   CFGBlock *       getIndirectGotoBlock() { return IndirectGotoBlock; }
1323   const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
1324
1325   using try_block_iterator = std::vector<const CFGBlock *>::const_iterator;
1326
1327   try_block_iterator try_blocks_begin() const {
1328     return TryDispatchBlocks.begin();
1329   }
1330
1331   try_block_iterator try_blocks_end() const {
1332     return TryDispatchBlocks.end();
1333   }
1334
1335   void addTryDispatchBlock(const CFGBlock *block) {
1336     TryDispatchBlocks.push_back(block);
1337   }
1338
1339   /// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
1340   ///
1341   /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
1342   /// multiple decls.
1343   void addSyntheticDeclStmt(const DeclStmt *Synthetic,
1344                             const DeclStmt *Source) {
1345     assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
1346     assert(Synthetic != Source && "Don't include original DeclStmts in map");
1347     assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
1348     SyntheticDeclStmts[Synthetic] = Source;
1349   }
1350
1351   using synthetic_stmt_iterator =
1352       llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator;
1353   using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>;
1354
1355   /// Iterates over synthetic DeclStmts in the CFG.
1356   ///
1357   /// Each element is a (synthetic statement, source statement) pair.
1358   ///
1359   /// \sa addSyntheticDeclStmt
1360   synthetic_stmt_iterator synthetic_stmt_begin() const {
1361     return SyntheticDeclStmts.begin();
1362   }
1363
1364   /// \sa synthetic_stmt_begin
1365   synthetic_stmt_iterator synthetic_stmt_end() const {
1366     return SyntheticDeclStmts.end();
1367   }
1368
1369   /// \sa synthetic_stmt_begin
1370   synthetic_stmt_range synthetic_stmts() const {
1371     return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end());
1372   }
1373
1374   //===--------------------------------------------------------------------===//
1375   // Member templates useful for various batch operations over CFGs.
1376   //===--------------------------------------------------------------------===//
1377
1378   template <typename CALLBACK>
1379   void VisitBlockStmts(CALLBACK& O) const {
1380     for (const_iterator I = begin(), E = end(); I != E; ++I)
1381       for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end();
1382            BI != BE; ++BI) {
1383         if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
1384           O(const_cast<Stmt*>(stmt->getStmt()));
1385       }
1386   }
1387
1388   //===--------------------------------------------------------------------===//
1389   // CFG Introspection.
1390   //===--------------------------------------------------------------------===//
1391
1392   /// Returns the total number of BlockIDs allocated (which start at 0).
1393   unsigned getNumBlockIDs() const { return NumBlockIDs; }
1394
1395   /// Return the total number of CFGBlocks within the CFG This is simply a
1396   /// renaming of the getNumBlockIDs(). This is necessary because the dominator
1397   /// implementation needs such an interface.
1398   unsigned size() const { return NumBlockIDs; }
1399
1400   /// Returns true if the CFG has no branches. Usually it boils down to the CFG
1401   /// having exactly three blocks (entry, the actual code, exit), but sometimes
1402   /// more blocks appear due to having control flow that can be fully
1403   /// resolved in compile time.
1404   bool isLinear() const;
1405
1406   //===--------------------------------------------------------------------===//
1407   // CFG Debugging: Pretty-Printing and Visualization.
1408   //===--------------------------------------------------------------------===//
1409
1410   void viewCFG(const LangOptions &LO) const;
1411   void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
1412   void dump(const LangOptions &LO, bool ShowColors) const;
1413
1414   //===--------------------------------------------------------------------===//
1415   // Internal: constructors and data.
1416   //===--------------------------------------------------------------------===//
1417
1418   CFG() : Blocks(BlkBVC, 10) {}
1419
1420   llvm::BumpPtrAllocator& getAllocator() {
1421     return BlkBVC.getAllocator();
1422   }
1423
1424   BumpVectorContext &getBumpVectorContext() {
1425     return BlkBVC;
1426   }
1427
1428 private:
1429   CFGBlock *Entry = nullptr;
1430   CFGBlock *Exit = nullptr;
1431
1432   // Special block to contain collective dispatch for indirect gotos
1433   CFGBlock* IndirectGotoBlock = nullptr;
1434
1435   unsigned  NumBlockIDs = 0;
1436
1437   BumpVectorContext BlkBVC;
1438
1439   CFGBlockListTy Blocks;
1440
1441   /// C++ 'try' statements are modeled with an indirect dispatch block.
1442   /// This is the collection of such blocks present in the CFG.
1443   std::vector<const CFGBlock *> TryDispatchBlocks;
1444
1445   /// Collects DeclStmts synthesized for this CFG and maps each one back to its
1446   /// source DeclStmt.
1447   llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
1448 };
1449
1450 } // namespace clang
1451
1452 //===----------------------------------------------------------------------===//
1453 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
1454 //===----------------------------------------------------------------------===//
1455
1456 namespace llvm {
1457
1458 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
1459 /// CFGTerminator to a specific Stmt class.
1460 template <> struct simplify_type< ::clang::CFGTerminator> {
1461   using SimpleType = ::clang::Stmt *;
1462
1463   static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) {
1464     return Val.getStmt();
1465   }
1466 };
1467
1468 // Traits for: CFGBlock
1469
1470 template <> struct GraphTraits< ::clang::CFGBlock *> {
1471   using NodeRef = ::clang::CFGBlock *;
1472   using ChildIteratorType = ::clang::CFGBlock::succ_iterator;
1473
1474   static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
1475   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1476   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1477 };
1478
1479 template <> struct GraphTraits<clang::CFGBlock>
1480     : GraphTraits<clang::CFGBlock *> {};
1481
1482 template <> struct GraphTraits< const ::clang::CFGBlock *> {
1483   using NodeRef = const ::clang::CFGBlock *;
1484   using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator;
1485
1486   static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
1487   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1488   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1489 };
1490
1491 template <> struct GraphTraits<const clang::CFGBlock>
1492     : GraphTraits<clang::CFGBlock *> {};
1493
1494 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
1495   using NodeRef = ::clang::CFGBlock *;
1496   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1497
1498   static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
1499     return G.Graph;
1500   }
1501
1502   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1503   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1504 };
1505
1506 template <> struct GraphTraits<Inverse<clang::CFGBlock>>
1507     : GraphTraits<clang::CFGBlock *> {};
1508
1509 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1510   using NodeRef = const ::clang::CFGBlock *;
1511   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1512
1513   static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
1514     return G.Graph;
1515   }
1516
1517   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1518   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1519 };
1520
1521 template <> struct GraphTraits<const Inverse<clang::CFGBlock>>
1522     : GraphTraits<clang::CFGBlock *> {};
1523
1524 // Traits for: CFG
1525
1526 template <> struct GraphTraits< ::clang::CFG* >
1527     : public GraphTraits< ::clang::CFGBlock *>  {
1528   using nodes_iterator = ::clang::CFG::iterator;
1529
1530   static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
1531   static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
1532   static nodes_iterator   nodes_end(::clang::CFG* F) { return F->nodes_end(); }
1533   static unsigned              size(::clang::CFG* F) { return F->size(); }
1534 };
1535
1536 template <> struct GraphTraits<const ::clang::CFG* >
1537     : public GraphTraits<const ::clang::CFGBlock *>  {
1538   using nodes_iterator = ::clang::CFG::const_iterator;
1539
1540   static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
1541
1542   static nodes_iterator nodes_begin( const ::clang::CFG* F) {
1543     return F->nodes_begin();
1544   }
1545
1546   static nodes_iterator nodes_end( const ::clang::CFG* F) {
1547     return F->nodes_end();
1548   }
1549
1550   static unsigned size(const ::clang::CFG* F) {
1551     return F->size();
1552   }
1553 };
1554
1555 template <> struct GraphTraits<Inverse< ::clang::CFG *>>
1556   : public GraphTraits<Inverse< ::clang::CFGBlock *>> {
1557   using nodes_iterator = ::clang::CFG::iterator;
1558
1559   static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
1560   static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
1561   static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
1562 };
1563
1564 template <> struct GraphTraits<Inverse<const ::clang::CFG *>>
1565   : public GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1566   using nodes_iterator = ::clang::CFG::const_iterator;
1567
1568   static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
1569
1570   static nodes_iterator nodes_begin(const ::clang::CFG* F) {
1571     return F->nodes_begin();
1572   }
1573
1574   static nodes_iterator nodes_end(const ::clang::CFG* F) {
1575     return F->nodes_end();
1576   }
1577 };
1578
1579 } // namespace llvm
1580
1581 #endif // LLVM_CLANG_ANALYSIS_CFG_H