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