contrib/llvm/tools/clang/include/clang/Analysis/CFG.h

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