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 "llvm/ADT/PointerIntPair.h"
  19 #include "llvm/ADT/GraphTraits.h"
  20 #include "llvm/Support/Allocator.h"
  21 #include "llvm/Support/Casting.h"
  22 #include "clang/Analysis/Support/BumpVector.h"
  23 #include "clang/Basic/SourceLocation.h"
  24 #include <cassert>
  25 #include <iterator>
  26
  27 namespace llvm {
  28   class raw_ostream;
  29 }
  30
  31 namespace clang {
  32   class Decl;
  33   class Stmt;
  34   class Expr;
  35   class FieldDecl;
  36   class VarDecl;
  37   class CXXCtorInitializer;
  38   class CXXBaseSpecifier;
  39   class CXXBindTemporaryExpr;
  40   class CFG;
  41   class PrinterHelper;
  42   class LangOptions;
  43   class ASTContext;
  44
  45 /// CFGElement - Represents a top-level expression in a basic block.
  46 class CFGElement {
  47 public:
  48   enum Kind {
  49     // main kind
  50     Statement,
  51     Initializer,
  52     ImplicitDtor,
  53     // dtor kind
  54     AutomaticObjectDtor,
  55     BaseDtor,
  56     MemberDtor,
  57     TemporaryDtor,
  58     DTOR_BEGIN = AutomaticObjectDtor
  59   };
  60
  61 protected:
  62   // The int bits are used to mark the main kind.
  63   llvm::PointerIntPair<void *, 2> Data1;
  64   // The int bits are used to mark the dtor kind.
  65   llvm::PointerIntPair<void *, 2> Data2;
  66
  67   CFGElement(void *Ptr, unsigned Int) : Data1(Ptr, Int) {}
  68   CFGElement(void *Ptr1, unsigned Int1, void *Ptr2, unsigned Int2)
  69       : Data1(Ptr1, Int1), Data2(Ptr2, Int2) {}
  70
  71 public:
  72   CFGElement() {}
  73
  74   Kind getKind() const { return static_cast<Kind>(Data1.getInt()); }
  75
  76   Kind getDtorKind() const {
  77     assert(getKind() == ImplicitDtor);
  78     return static_cast<Kind>(Data2.getInt() + DTOR_BEGIN);
  79   }
  80
  81   bool isValid() const { return Data1.getPointer(); }
  82
  83   operator bool() const { return isValid(); }
  84
  85   template<class ElemTy> ElemTy getAs() const {
  86     if (llvm::isa<ElemTy>(this))
  87       return *static_cast<const ElemTy*>(this);
  88     return ElemTy();
  89   }
  90
  91   static bool classof(const CFGElement *E) { return true; }
  92 };
  93
  94 class CFGStmt : public CFGElement {
  95 public:
  96   CFGStmt() {}
  97   CFGStmt(Stmt *S) : CFGElement(S, 0) {}
  98
  99   Stmt *getStmt() const { return static_cast<Stmt *>(Data1.getPointer()); }
 100
 101   operator Stmt*() const { return getStmt(); }
 102
 103   static bool classof(const CFGElement *E) {
 104     return E->getKind() == Statement;
 105   }
 106 };
 107
 108 /// CFGInitializer - Represents C++ base or member initializer from
 109 /// constructor's initialization list.
 110 class CFGInitializer : public CFGElement {
 111 public:
 112   CFGInitializer() {}
 113   CFGInitializer(CXXCtorInitializer* I)
 114       : CFGElement(I, Initializer) {}
 115
 116   CXXCtorInitializer* getInitializer() const {
 117     return static_cast<CXXCtorInitializer*>(Data1.getPointer());
 118   }
 119   operator CXXCtorInitializer*() const { return getInitializer(); }
 120
 121   static bool classof(const CFGElement *E) {
 122     return E->getKind() == Initializer;
 123   }
 124 };
 125
 126 /// CFGImplicitDtor - Represents C++ object destructor implicitly generated
 127 /// by compiler on various occasions.
 128 class CFGImplicitDtor : public CFGElement {
 129 protected:
 130   CFGImplicitDtor(unsigned K, void* P, void* S)
 131       : CFGElement(P, ImplicitDtor, S, K - DTOR_BEGIN) {}
 132
 133 public:
 134   CFGImplicitDtor() {}
 135
 136   static bool classof(const CFGElement *E) {
 137     return E->getKind() == ImplicitDtor;
 138   }
 139 };
 140
 141 /// CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated
 142 /// for automatic object or temporary bound to const reference at the point
 143 /// of leaving its local scope.
 144 class CFGAutomaticObjDtor: public CFGImplicitDtor {
 145 public:
 146   CFGAutomaticObjDtor() {}
 147   CFGAutomaticObjDtor(VarDecl* VD, Stmt* S)
 148       : CFGImplicitDtor(AutomaticObjectDtor, VD, S) {}
 149
 150   VarDecl* getVarDecl() const {
 151     return static_cast<VarDecl*>(Data1.getPointer());
 152   }
 153
 154   // Get statement end of which triggered the destructor call.
 155   Stmt* getTriggerStmt() const {
 156     return static_cast<Stmt*>(Data2.getPointer());
 157   }
 158
 159   static bool classof(const CFGElement *E) {
 160     return E->getKind() == ImplicitDtor &&
 161            E->getDtorKind() == AutomaticObjectDtor;
 162   }
 163 };
 164
 165 /// CFGBaseDtor - Represents C++ object destructor implicitly generated for
 166 /// base object in destructor.
 167 class CFGBaseDtor : public CFGImplicitDtor {
 168 public:
 169   CFGBaseDtor() {}
 170   CFGBaseDtor(const CXXBaseSpecifier *BS)
 171       : CFGImplicitDtor(BaseDtor, const_cast<CXXBaseSpecifier*>(BS), NULL) {}
 172
 173   const CXXBaseSpecifier *getBaseSpecifier() const {
 174     return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());
 175   }
 176
 177   static bool classof(const CFGElement *E) {
 178     return E->getKind() == ImplicitDtor && E->getDtorKind() == BaseDtor;
 179   }
 180 };
 181
 182 /// CFGMemberDtor - Represents C++ object destructor implicitly generated for
 183 /// member object in destructor.
 184 class CFGMemberDtor : public CFGImplicitDtor {
 185 public:
 186   CFGMemberDtor() {}
 187   CFGMemberDtor(FieldDecl *FD)
 188       : CFGImplicitDtor(MemberDtor, FD, NULL) {}
 189
 190   FieldDecl *getFieldDecl() const {
 191     return static_cast<FieldDecl*>(Data1.getPointer());
 192   }
 193
 194   static bool classof(const CFGElement *E) {
 195     return E->getKind() == ImplicitDtor && E->getDtorKind() == MemberDtor;
 196   }
 197 };
 198
 199 /// CFGTemporaryDtor - Represents C++ object destructor implicitly generated
 200 /// at the end of full expression for temporary object.
 201 class CFGTemporaryDtor : public CFGImplicitDtor {
 202 public:
 203   CFGTemporaryDtor() {}
 204   CFGTemporaryDtor(CXXBindTemporaryExpr *E)
 205       : CFGImplicitDtor(TemporaryDtor, E, NULL) {}
 206
 207   CXXBindTemporaryExpr *getBindTemporaryExpr() const {
 208     return static_cast<CXXBindTemporaryExpr *>(Data1.getPointer());
 209   }
 210
 211   static bool classof(const CFGElement *E) {
 212     return E->getKind() == ImplicitDtor && E->getDtorKind() == TemporaryDtor;
 213   }
 214 };
 215
 216 /// CFGTerminator - Represents CFGBlock terminator statement.
 217 ///
 218 /// TemporaryDtorsBranch bit is set to true if the terminator marks a branch
 219 /// in control flow of destructors of temporaries. In this case terminator
 220 /// statement is the same statement that branches control flow in evaluation
 221 /// of matching full expression.
 222 class CFGTerminator {
 223   llvm::PointerIntPair<Stmt *, 1> Data;
 224 public:
 225   CFGTerminator() {}
 226   CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false)
 227       : Data(S, TemporaryDtorsBranch) {}
 228
 229   Stmt *getStmt() { return Data.getPointer(); }
 230   const Stmt *getStmt() const { return Data.getPointer(); }
 231
 232   bool isTemporaryDtorsBranch() const { return Data.getInt(); }
 233
 234   operator Stmt *() { return getStmt(); }
 235   operator const Stmt *() const { return getStmt(); }
 236
 237   Stmt *operator->() { return getStmt(); }
 238   const Stmt *operator->() const { return getStmt(); }
 239
 240   Stmt &operator*() { return *getStmt(); }
 241   const Stmt &operator*() const { return *getStmt(); }
 242
 243   operator bool() const { return getStmt(); }
 244 };
 245
 246 /// CFGBlock - Represents a single basic block in a source-level CFG.
 247 ///  It consists of:
 248 ///
 249 ///  (1) A set of statements/expressions (which may contain subexpressions).
 250 ///  (2) A "terminator" statement (not in the set of statements).
 251 ///  (3) A list of successors and predecessors.
 252 ///
 253 /// Terminator: The terminator represents the type of control-flow that occurs
 254 /// at the end of the basic block.  The terminator is a Stmt* referring to an
 255 /// AST node that has control-flow: if-statements, breaks, loops, etc.
 256 /// If the control-flow is conditional, the condition expression will appear
 257 /// within the set of statements in the block (usually the last statement).
 258 ///
 259 /// Predecessors: the order in the set of predecessors is arbitrary.
 260 ///
 261 /// Successors: the order in the set of successors is NOT arbitrary.  We
 262 ///  currently have the following orderings based on the terminator:
 263 ///
 264 ///     Terminator       Successor Ordering
 265 ///  -----------------------------------------------------
 266 ///       if            Then Block;  Else Block
 267 ///     ? operator      LHS expression;  RHS expression
 268 ///     &&, ||          expression that uses result of && or ||, RHS
 269 ///
 270 class CFGBlock {
 271   class ElementList {
 272     typedef BumpVector<CFGElement> ImplTy;
 273     ImplTy Impl;
 274   public:
 275     ElementList(BumpVectorContext &C) : Impl(C, 4) {}
 276
 277     typedef std::reverse_iterator<ImplTy::iterator>       iterator;
 278     typedef std::reverse_iterator<ImplTy::const_iterator> const_iterator;
 279     typedef ImplTy::iterator                              reverse_iterator;
 280     typedef ImplTy::const_iterator                        const_reverse_iterator;
 281
 282     void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
 283     reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
 284         BumpVectorContext& C) {
 285       return Impl.insert(I, Cnt, E, C);
 286     }
 287
 288     CFGElement front() const { return Impl.back(); }
 289     CFGElement back() const { return Impl.front(); }
 290
 291     iterator begin() { return Impl.rbegin(); }
 292     iterator end() { return Impl.rend(); }
 293     const_iterator begin() const { return Impl.rbegin(); }
 294     const_iterator end() const { return Impl.rend(); }
 295     reverse_iterator rbegin() { return Impl.begin(); }
 296     reverse_iterator rend() { return Impl.end(); }
 297     const_reverse_iterator rbegin() const { return Impl.begin(); }
 298     const_reverse_iterator rend() const { return Impl.end(); }
 299
 300    CFGElement operator[](size_t i) const  {
 301      assert(i < Impl.size());
 302      return Impl[Impl.size() - 1 - i];
 303    }
 304
 305     size_t size() const { return Impl.size(); }
 306     bool empty() const { return Impl.empty(); }
 307   };
 308
 309   /// Stmts - The set of statements in the basic block.
 310   ElementList Elements;
 311
 312   /// Label - An (optional) label that prefixes the executable
 313   ///  statements in the block.  When this variable is non-NULL, it is
 314   ///  either an instance of LabelStmt, SwitchCase or CXXCatchStmt.
 315   Stmt *Label;
 316
 317   /// Terminator - The terminator for a basic block that
 318   ///  indicates the type of control-flow that occurs between a block
 319   ///  and its successors.
 320   CFGTerminator Terminator;
 321
 322   /// LoopTarget - Some blocks are used to represent the "loop edge" to
 323   ///  the start of a loop from within the loop body.  This Stmt* will be
 324   ///  refer to the loop statement for such blocks (and be null otherwise).
 325   const Stmt *LoopTarget;
 326
 327   /// BlockID - A numerical ID assigned to a CFGBlock during construction
 328   ///   of the CFG.
 329   unsigned BlockID;
 330
 331   /// Predecessors/Successors - Keep track of the predecessor / successor
 332   /// CFG blocks.
 333   typedef BumpVector<CFGBlock*> AdjacentBlocks;
 334   AdjacentBlocks Preds;
 335   AdjacentBlocks Succs;
 336
 337 public:
 338   explicit CFGBlock(unsigned blockid, BumpVectorContext &C)
 339     : Elements(C), Label(NULL), Terminator(NULL), LoopTarget(NULL),
 340       BlockID(blockid), Preds(C, 1), Succs(C, 1) {}
 341   ~CFGBlock() {}
 342
 343   // Statement iterators
 344   typedef ElementList::iterator                      iterator;
 345   typedef ElementList::const_iterator                const_iterator;
 346   typedef ElementList::reverse_iterator              reverse_iterator;
 347   typedef ElementList::const_reverse_iterator        const_reverse_iterator;
 348
 349   CFGElement                 front()       const { return Elements.front();   }
 350   CFGElement                 back()        const { return Elements.back();    }
 351
 352   iterator                   begin()             { return Elements.begin();   }
 353   iterator                   end()               { return Elements.end();     }
 354   const_iterator             begin()       const { return Elements.begin();   }
 355   const_iterator             end()         const { return Elements.end();     }
 356
 357   reverse_iterator           rbegin()            { return Elements.rbegin();  }
 358   reverse_iterator           rend()              { return Elements.rend();    }
 359   const_reverse_iterator     rbegin()      const { return Elements.rbegin();  }
 360   const_reverse_iterator     rend()        const { return Elements.rend();    }
 361
 362   unsigned                   size()        const { return Elements.size();    }
 363   bool                       empty()       const { return Elements.empty();   }
 364
 365   CFGElement operator[](size_t i) const  { return Elements[i]; }
 366
 367   // CFG iterators
 368   typedef AdjacentBlocks::iterator                              pred_iterator;
 369   typedef AdjacentBlocks::const_iterator                  const_pred_iterator;
 370   typedef AdjacentBlocks::reverse_iterator              pred_reverse_iterator;
 371   typedef AdjacentBlocks::const_reverse_iterator  const_pred_reverse_iterator;
 372
 373   typedef AdjacentBlocks::iterator                              succ_iterator;
 374   typedef AdjacentBlocks::const_iterator                  const_succ_iterator;
 375   typedef AdjacentBlocks::reverse_iterator              succ_reverse_iterator;
 376   typedef AdjacentBlocks::const_reverse_iterator  const_succ_reverse_iterator;
 377
 378   pred_iterator                pred_begin()        { return Preds.begin();   }
 379   pred_iterator                pred_end()          { return Preds.end();     }
 380   const_pred_iterator          pred_begin()  const { return Preds.begin();   }
 381   const_pred_iterator          pred_end()    const { return Preds.end();     }
 382
 383   pred_reverse_iterator        pred_rbegin()       { return Preds.rbegin();  }
 384   pred_reverse_iterator        pred_rend()         { return Preds.rend();    }
 385   const_pred_reverse_iterator  pred_rbegin() const { return Preds.rbegin();  }
 386   const_pred_reverse_iterator  pred_rend()   const { return Preds.rend();    }
 387
 388   succ_iterator                succ_begin()        { return Succs.begin();   }
 389   succ_iterator                succ_end()          { return Succs.end();     }
 390   const_succ_iterator          succ_begin()  const { return Succs.begin();   }
 391   const_succ_iterator          succ_end()    const { return Succs.end();     }
 392
 393   succ_reverse_iterator        succ_rbegin()       { return Succs.rbegin();  }
 394   succ_reverse_iterator        succ_rend()         { return Succs.rend();    }
 395   const_succ_reverse_iterator  succ_rbegin() const { return Succs.rbegin();  }
 396   const_succ_reverse_iterator  succ_rend()   const { return Succs.rend();    }
 397
 398   unsigned                     succ_size()   const { return Succs.size();    }
 399   bool                         succ_empty()  const { return Succs.empty();   }
 400
 401   unsigned                     pred_size()   const { return Preds.size();    }
 402   bool                         pred_empty()  const { return Preds.empty();   }
 403
 404
 405   class FilterOptions {
 406   public:
 407     FilterOptions() {
 408       IgnoreDefaultsWithCoveredEnums = 0;
 409     }
 410
 411     unsigned IgnoreDefaultsWithCoveredEnums : 1;
 412   };
 413
 414   static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
 415        const CFGBlock *Dst);
 416
 417   template <typename IMPL, bool IsPred>
 418   class FilteredCFGBlockIterator {
 419   private:
 420     IMPL I, E;
 421     const FilterOptions F;
 422     const CFGBlock *From;
 423    public:
 424     explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
 425               const CFGBlock *from,
 426               const FilterOptions &f)
 427       : I(i), E(e), F(f), From(from) {}
 428
 429     bool hasMore() const { return I != E; }
 430
 431     FilteredCFGBlockIterator &operator++() {
 432       do { ++I; } while (hasMore() && Filter(*I));
 433       return *this;
 434     }
 435
 436     const CFGBlock *operator*() const { return *I; }
 437   private:
 438     bool Filter(const CFGBlock *To) {
 439       return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
 440     }
 441   };
 442
 443   typedef FilteredCFGBlockIterator<const_pred_iterator, true>
 444           filtered_pred_iterator;
 445
 446   typedef FilteredCFGBlockIterator<const_succ_iterator, false>
 447           filtered_succ_iterator;
 448
 449   filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
 450     return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
 451   }
 452
 453   filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
 454     return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
 455   }
 456
 457   // Manipulation of block contents
 458
 459   void setTerminator(Stmt* Statement) { Terminator = Statement; }
 460   void setLabel(Stmt* Statement) { Label = Statement; }
 461   void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
 462
 463   CFGTerminator getTerminator() { return Terminator; }
 464   const CFGTerminator getTerminator() const { return Terminator; }
 465
 466   Stmt* getTerminatorCondition();
 467
 468   const Stmt* getTerminatorCondition() const {
 469     return const_cast<CFGBlock*>(this)->getTerminatorCondition();
 470   }
 471
 472   const Stmt *getLoopTarget() const { return LoopTarget; }
 473
 474   bool hasBinaryBranchTerminator() const;
 475
 476   Stmt* getLabel() { return Label; }
 477   const Stmt* getLabel() const { return Label; }
 478
 479   unsigned getBlockID() const { return BlockID; }
 480
 481   void dump(const CFG *cfg, const LangOptions &LO) const;
 482   void print(llvm::raw_ostream &OS, const CFG* cfg, const LangOptions &LO) const;
 483   void printTerminator(llvm::raw_ostream &OS, const LangOptions &LO) const;
 484
 485   void addSuccessor(CFGBlock* Block, BumpVectorContext &C) {
 486     if (Block)
 487       Block->Preds.push_back(this, C);
 488     Succs.push_back(Block, C);
 489   }
 490
 491   void appendStmt(Stmt* statement, BumpVectorContext &C) {
 492     Elements.push_back(CFGStmt(statement), C);
 493   }
 494
 495   void appendInitializer(CXXCtorInitializer *initializer,
 496                         BumpVectorContext& C) {
 497     Elements.push_back(CFGInitializer(initializer), C);
 498   }
 499
 500   void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
 501     Elements.push_back(CFGBaseDtor(BS), C);
 502   }
 503
 504   void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
 505     Elements.push_back(CFGMemberDtor(FD), C);
 506   }
 507
 508   void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) {
 509     Elements.push_back(CFGTemporaryDtor(E), C);
 510   }
 511
 512   // Destructors must be inserted in reversed order. So insertion is in two
 513   // steps. First we prepare space for some number of elements, then we insert
 514   // the elements beginning at the last position in prepared space.
 515   iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt,
 516       BumpVectorContext& C) {
 517     return iterator(Elements.insert(I.base(), Cnt, CFGElement(), C));
 518   }
 519   iterator insertAutomaticObjDtor(iterator I, VarDecl* VD, Stmt* S) {
 520     *I = CFGAutomaticObjDtor(VD, S);
 521     return ++I;
 522   }
 523 };
 524
 525 /// CFG - Represents a source-level, intra-procedural CFG that represents the
 526 ///  control-flow of a Stmt.  The Stmt can represent an entire function body,
 527 ///  or a single expression.  A CFG will always contain one empty block that
 528 ///  represents the Exit point of the CFG.  A CFG will also contain a designated
 529 ///  Entry block.  The CFG solely represents control-flow; it consists of
 530 ///  CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
 531 ///  was constructed from.
 532 class CFG {
 533 public:
 534   //===--------------------------------------------------------------------===//
 535   // CFG Construction & Manipulation.
 536   //===--------------------------------------------------------------------===//
 537
 538   class BuildOptions {
 539   public:
 540     bool PruneTriviallyFalseEdges:1;
 541     bool AddEHEdges:1;
 542     bool AddInitializers:1;
 543     bool AddImplicitDtors:1;
 544
 545     BuildOptions()
 546         : PruneTriviallyFalseEdges(true)
 547         , AddEHEdges(false)
 548         , AddInitializers(false)
 549         , AddImplicitDtors(false) {}
 550   };
 551
 552   /// buildCFG - Builds a CFG from an AST.  The responsibility to free the
 553   ///   constructed CFG belongs to the caller.
 554   static CFG* buildCFG(const Decl *D, Stmt* AST, ASTContext *C,
 555       BuildOptions BO = BuildOptions());
 556
 557   /// createBlock - Create a new block in the CFG.  The CFG owns the block;
 558   ///  the caller should not directly free it.
 559   CFGBlock* createBlock();
 560
 561   /// setEntry - Set the entry block of the CFG.  This is typically used
 562   ///  only during CFG construction.  Most CFG clients expect that the
 563   ///  entry block has no predecessors and contains no statements.
 564   void setEntry(CFGBlock *B) { Entry = B; }
 565
 566   /// setIndirectGotoBlock - Set the block used for indirect goto jumps.
 567   ///  This is typically used only during CFG construction.
 568   void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; }
 569
 570   //===--------------------------------------------------------------------===//
 571   // Block Iterators
 572   //===--------------------------------------------------------------------===//
 573
 574   typedef BumpVector<CFGBlock*>                    CFGBlockListTy;
 575   typedef CFGBlockListTy::iterator                 iterator;
 576   typedef CFGBlockListTy::const_iterator           const_iterator;
 577   typedef std::reverse_iterator<iterator>          reverse_iterator;
 578   typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
 579
 580   CFGBlock&                 front()                { return *Blocks.front(); }
 581   CFGBlock&                 back()                 { return *Blocks.back(); }
 582
 583   iterator                  begin()                { return Blocks.begin(); }
 584   iterator                  end()                  { return Blocks.end(); }
 585   const_iterator            begin()       const    { return Blocks.begin(); }
 586   const_iterator            end()         const    { return Blocks.end(); }
 587
 588   reverse_iterator          rbegin()               { return Blocks.rbegin(); }
 589   reverse_iterator          rend()                 { return Blocks.rend(); }
 590   const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
 591   const_reverse_iterator    rend()        const    { return Blocks.rend(); }
 592
 593   CFGBlock&                 getEntry()             { return *Entry; }
 594   const CFGBlock&           getEntry()    const    { return *Entry; }
 595   CFGBlock&                 getExit()              { return *Exit; }
 596   const CFGBlock&           getExit()     const    { return *Exit; }
 597
 598   CFGBlock*        getIndirectGotoBlock() { return IndirectGotoBlock; }
 599   const CFGBlock*  getIndirectGotoBlock() const { return IndirectGotoBlock; }
 600
 601   //===--------------------------------------------------------------------===//
 602   // Member templates useful for various batch operations over CFGs.
 603   //===--------------------------------------------------------------------===//
 604
 605   template <typename CALLBACK>
 606   void VisitBlockStmts(CALLBACK& O) const {
 607     for (const_iterator I=begin(), E=end(); I != E; ++I)
 608       for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
 609            BI != BE; ++BI) {
 610         if (CFGStmt S = BI->getAs<CFGStmt>())
 611           O(S);
 612       }
 613   }
 614
 615   //===--------------------------------------------------------------------===//
 616   // CFG Introspection.
 617   //===--------------------------------------------------------------------===//
 618
 619   struct   BlkExprNumTy {
 620     const signed Idx;
 621     explicit BlkExprNumTy(signed idx) : Idx(idx) {}
 622     explicit BlkExprNumTy() : Idx(-1) {}
 623     operator bool() const { return Idx >= 0; }
 624     operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; }
 625   };
 626
 627   bool          isBlkExpr(const Stmt* S) { return getBlkExprNum(S); }
 628   BlkExprNumTy  getBlkExprNum(const Stmt* S);
 629   unsigned      getNumBlkExprs();
 630
 631   /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which
 632   /// start at 0).
 633   unsigned getNumBlockIDs() const { return NumBlockIDs; }
 634
 635   //===--------------------------------------------------------------------===//
 636   // CFG Debugging: Pretty-Printing and Visualization.
 637   //===--------------------------------------------------------------------===//
 638
 639   void viewCFG(const LangOptions &LO) const;
 640   void print(llvm::raw_ostream& OS, const LangOptions &LO) const;
 641   void dump(const LangOptions &LO) const;
 642
 643   //===--------------------------------------------------------------------===//
 644   // Internal: constructors and data.
 645   //===--------------------------------------------------------------------===//
 646
 647   CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0),
 648           BlkExprMap(NULL), Blocks(BlkBVC, 10) {}
 649
 650   ~CFG();
 651
 652   llvm::BumpPtrAllocator& getAllocator() {
 653     return BlkBVC.getAllocator();
 654   }
 655
 656   BumpVectorContext &getBumpVectorContext() {
 657     return BlkBVC;
 658   }
 659
 660 private:
 661   CFGBlock* Entry;
 662   CFGBlock* Exit;
 663   CFGBlock* IndirectGotoBlock;  // Special block to contain collective dispatch
 664                                 // for indirect gotos
 665   unsigned  NumBlockIDs;
 666
 667   // BlkExprMap - An opaque pointer to prevent inclusion of DenseMap.h.
 668   //  It represents a map from Expr* to integers to record the set of
 669   //  block-level expressions and their "statement number" in the CFG.
 670   void*     BlkExprMap;
 671
 672   BumpVectorContext BlkBVC;
 673
 674   CFGBlockListTy Blocks;
 675
 676 };
 677 } // end namespace clang
 678
 679 //===----------------------------------------------------------------------===//
 680 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
 681 //===----------------------------------------------------------------------===//
 682
 683 namespace llvm {
 684
 685 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
 686 /// CFGTerminator to a specific Stmt class.
 687 template <> struct simplify_type<const ::clang::CFGTerminator> {
 688   typedef const ::clang::Stmt *SimpleType;
 689   static SimpleType getSimplifiedValue(const ::clang::CFGTerminator &Val) {
 690     return Val.getStmt();
 691   }
 692 };
 693
 694 template <> struct simplify_type< ::clang::CFGTerminator> {
 695   typedef ::clang::Stmt *SimpleType;
 696   static SimpleType getSimplifiedValue(const ::clang::CFGTerminator &Val) {
 697     return const_cast<SimpleType>(Val.getStmt());
 698   }
 699 };
 700
 701 // Traits for: CFGBlock
 702
 703 template <> struct GraphTraits< ::clang::CFGBlock* > {
 704   typedef ::clang::CFGBlock NodeType;
 705   typedef ::clang::CFGBlock::succ_iterator ChildIteratorType;
 706
 707   static NodeType* getEntryNode(::clang::CFGBlock* BB)
 708   { return BB; }
 709
 710   static inline ChildIteratorType child_begin(NodeType* N)
 711   { return N->succ_begin(); }
 712
 713   static inline ChildIteratorType child_end(NodeType* N)
 714   { return N->succ_end(); }
 715 };
 716
 717 template <> struct GraphTraits< const ::clang::CFGBlock* > {
 718   typedef const ::clang::CFGBlock NodeType;
 719   typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType;
 720
 721   static NodeType* getEntryNode(const clang::CFGBlock* BB)
 722   { return BB; }
 723
 724   static inline ChildIteratorType child_begin(NodeType* N)
 725   { return N->succ_begin(); }
 726
 727   static inline ChildIteratorType child_end(NodeType* N)
 728   { return N->succ_end(); }
 729 };
 730
 731 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
 732   typedef const ::clang::CFGBlock NodeType;
 733   typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
 734
 735   static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G)
 736   { return G.Graph; }
 737
 738   static inline ChildIteratorType child_begin(NodeType* N)
 739   { return N->pred_begin(); }
 740
 741   static inline ChildIteratorType child_end(NodeType* N)
 742   { return N->pred_end(); }
 743 };
 744
 745 // Traits for: CFG
 746
 747 template <> struct GraphTraits< ::clang::CFG* >
 748     : public GraphTraits< ::clang::CFGBlock* >  {
 749
 750   typedef ::clang::CFG::iterator nodes_iterator;
 751
 752   static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
 753   static nodes_iterator nodes_begin(::clang::CFG* F) { return F->begin(); }
 754   static nodes_iterator nodes_end(::clang::CFG* F) { return F->end(); }
 755 };
 756
 757 template <> struct GraphTraits<const ::clang::CFG* >
 758     : public GraphTraits<const ::clang::CFGBlock* >  {
 759
 760   typedef ::clang::CFG::const_iterator nodes_iterator;
 761
 762   static NodeType *getEntryNode( const ::clang::CFG* F) {
 763     return &F->getEntry();
 764   }
 765   static nodes_iterator nodes_begin( const ::clang::CFG* F) {
 766     return F->begin();
 767   }
 768   static nodes_iterator nodes_end( const ::clang::CFG* F) {
 769     return F->end();
 770   }
 771 };
 772
 773 template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
 774   : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
 775
 776   typedef ::clang::CFG::const_iterator nodes_iterator;
 777
 778   static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
 779   static nodes_iterator nodes_begin(const ::clang::CFG* F) { return F->begin();}
 780   static nodes_iterator nodes_end(const ::clang::CFG* F) { return F->end(); }
 781 };
 782 } // end llvm namespace
 783 #endif