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