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