1198092Srdivacky//===--- CFG.h - Classes for representing and building CFGs------*- C++ -*-===// 2198092Srdivacky// 3198092Srdivacky// The LLVM Compiler Infrastructure 4198092Srdivacky// 5198092Srdivacky// This file is distributed under the University of Illinois Open Source 6198092Srdivacky// License. See LICENSE.TXT for details. 7198092Srdivacky// 8198092Srdivacky//===----------------------------------------------------------------------===// 9198092Srdivacky// 10198092Srdivacky// This file defines the CFG and CFGBuilder classes for representing and 11198092Srdivacky// building Control-Flow Graphs (CFGs) from ASTs. 12198092Srdivacky// 13198092Srdivacky//===----------------------------------------------------------------------===// 14198092Srdivacky 15198092Srdivacky#ifndef LLVM_CLANG_CFG_H 16198092Srdivacky#define LLVM_CLANG_CFG_H 17198092Srdivacky 18252723Sdim#include "clang/AST/Stmt.h" 19252723Sdim#include "clang/Analysis/Support/BumpVector.h" 20252723Sdim#include "clang/Basic/SourceLocation.h" 21252723Sdim#include "llvm/ADT/DenseMap.h" 22252723Sdim#include "llvm/ADT/GraphTraits.h" 23252723Sdim#include "llvm/ADT/Optional.h" 24252723Sdim#include "llvm/ADT/OwningPtr.h" 25201361Srdivacky#include "llvm/ADT/PointerIntPair.h" 26198092Srdivacky#include "llvm/Support/Allocator.h" 27201361Srdivacky#include "llvm/Support/Casting.h" 28245431Sdim#include <bitset> 29198092Srdivacky#include <cassert> 30218893Sdim#include <iterator> 31198092Srdivacky 32198092Srdivackynamespace clang { 33221345Sdim class CXXDestructorDecl; 34202879Srdivacky class Decl; 35198092Srdivacky class Stmt; 36198092Srdivacky class Expr; 37218893Sdim class FieldDecl; 38218893Sdim class VarDecl; 39218893Sdim class CXXCtorInitializer; 40218893Sdim class CXXBaseSpecifier; 41218893Sdim class CXXBindTemporaryExpr; 42198092Srdivacky class CFG; 43198092Srdivacky class PrinterHelper; 44198092Srdivacky class LangOptions; 45198092Srdivacky class ASTContext; 46263509Sdim class CXXRecordDecl; 47263509Sdim class CXXDeleteExpr; 48198092Srdivacky 49201361Srdivacky/// CFGElement - Represents a top-level expression in a basic block. 50201361Srdivackyclass CFGElement { 51201361Srdivackypublic: 52218893Sdim enum Kind { 53218893Sdim // main kind 54218893Sdim Statement, 55218893Sdim Initializer, 56218893Sdim // dtor kind 57218893Sdim AutomaticObjectDtor, 58263509Sdim DeleteDtor, 59218893Sdim BaseDtor, 60218893Sdim MemberDtor, 61218893Sdim TemporaryDtor, 62221345Sdim DTOR_BEGIN = AutomaticObjectDtor, 63221345Sdim DTOR_END = TemporaryDtor 64218893Sdim }; 65218893Sdim 66218893Sdimprotected: 67221345Sdim // The int bits are used to mark the kind. 68218893Sdim llvm::PointerIntPair<void *, 2> Data1; 69218893Sdim llvm::PointerIntPair<void *, 2> Data2; 70218893Sdim 71221345Sdim CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = 0) 72221345Sdim : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3), 73235633Sdim Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {} 74218893Sdim 75252723Sdim CFGElement() {} 76218893Sdimpublic: 77218893Sdim 78252723Sdim /// \brief Convert to the specified CFGElement type, asserting that this 79252723Sdim /// CFGElement is of the desired type. 80252723Sdim template<typename T> 81252723Sdim T castAs() const { 82252723Sdim assert(T::isKind(*this)); 83252723Sdim T t; 84252723Sdim CFGElement& e = t; 85252723Sdim e = *this; 86252723Sdim return t; 87252723Sdim } 88252723Sdim 89252723Sdim /// \brief Convert to the specified CFGElement type, returning None if this 90252723Sdim /// CFGElement is not of the desired type. 91252723Sdim template<typename T> 92252723Sdim Optional<T> getAs() const { 93252723Sdim if (!T::isKind(*this)) 94252723Sdim return None; 95252723Sdim T t; 96252723Sdim CFGElement& e = t; 97252723Sdim e = *this; 98252723Sdim return t; 99252723Sdim } 100252723Sdim 101235633Sdim Kind getKind() const { 102221345Sdim unsigned x = Data2.getInt(); 103221345Sdim x <<= 2; 104221345Sdim x |= Data1.getInt(); 105221345Sdim return (Kind) x; 106218893Sdim } 107218893Sdim}; 108218893Sdim 109218893Sdimclass CFGStmt : public CFGElement { 110218893Sdimpublic: 111221345Sdim CFGStmt(Stmt *S) : CFGElement(Statement, S) {} 112218893Sdim 113235633Sdim const Stmt *getStmt() const { 114226890Sdim return static_cast<const Stmt *>(Data1.getPointer()); 115226890Sdim } 116218893Sdim 117252723Sdimprivate: 118252723Sdim friend class CFGElement; 119252723Sdim CFGStmt() {} 120252723Sdim static bool isKind(const CFGElement &E) { 121252723Sdim return E.getKind() == Statement; 122218893Sdim } 123201361Srdivacky}; 124201361Srdivacky 125218893Sdim/// CFGInitializer - Represents C++ base or member initializer from 126218893Sdim/// constructor's initialization list. 127218893Sdimclass CFGInitializer : public CFGElement { 128218893Sdimpublic: 129221345Sdim CFGInitializer(CXXCtorInitializer *initializer) 130221345Sdim : CFGElement(Initializer, initializer) {} 131218893Sdim 132218893Sdim CXXCtorInitializer* getInitializer() const { 133218893Sdim return static_cast<CXXCtorInitializer*>(Data1.getPointer()); 134218893Sdim } 135218893Sdim 136252723Sdimprivate: 137252723Sdim friend class CFGElement; 138252723Sdim CFGInitializer() {} 139252723Sdim static bool isKind(const CFGElement &E) { 140252723Sdim return E.getKind() == Initializer; 141218893Sdim } 142218893Sdim}; 143218893Sdim 144218893Sdim/// CFGImplicitDtor - Represents C++ object destructor implicitly generated 145218893Sdim/// by compiler on various occasions. 146218893Sdimclass CFGImplicitDtor : public CFGElement { 147218893Sdimprotected: 148252723Sdim CFGImplicitDtor() {} 149235633Sdim CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = 0) 150221345Sdim : CFGElement(kind, data1, data2) { 151235633Sdim assert(kind >= DTOR_BEGIN && kind <= DTOR_END); 152221345Sdim } 153218893Sdim 154218893Sdimpublic: 155221345Sdim const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const; 156221345Sdim bool isNoReturn(ASTContext &astContext) const; 157218893Sdim 158252723Sdimprivate: 159252723Sdim friend class CFGElement; 160252723Sdim static bool isKind(const CFGElement &E) { 161252723Sdim Kind kind = E.getKind(); 162221345Sdim return kind >= DTOR_BEGIN && kind <= DTOR_END; 163218893Sdim } 164218893Sdim}; 165218893Sdim 166218893Sdim/// CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated 167218893Sdim/// for automatic object or temporary bound to const reference at the point 168218893Sdim/// of leaving its local scope. 169218893Sdimclass CFGAutomaticObjDtor: public CFGImplicitDtor { 170218893Sdimpublic: 171221345Sdim CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt) 172221345Sdim : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {} 173218893Sdim 174221345Sdim const VarDecl *getVarDecl() const { 175218893Sdim return static_cast<VarDecl*>(Data1.getPointer()); 176218893Sdim } 177218893Sdim 178218893Sdim // Get statement end of which triggered the destructor call. 179221345Sdim const Stmt *getTriggerStmt() const { 180218893Sdim return static_cast<Stmt*>(Data2.getPointer()); 181218893Sdim } 182218893Sdim 183252723Sdimprivate: 184252723Sdim friend class CFGElement; 185252723Sdim CFGAutomaticObjDtor() {} 186252723Sdim static bool isKind(const CFGElement &elem) { 187252723Sdim return elem.getKind() == AutomaticObjectDtor; 188218893Sdim } 189218893Sdim}; 190218893Sdim 191263509Sdim/// CFGDeleteDtor - Represents C++ object destructor generated 192263509Sdim/// from a call to delete. 193263509Sdimclass CFGDeleteDtor : public CFGImplicitDtor { 194263509Sdimpublic: 195263509Sdim CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE) 196263509Sdim : CFGImplicitDtor(DeleteDtor, RD, DE) {} 197263509Sdim 198263509Sdim const CXXRecordDecl *getCXXRecordDecl() const { 199263509Sdim return static_cast<CXXRecordDecl*>(Data1.getPointer()); 200263509Sdim } 201263509Sdim 202263509Sdim // Get Delete expression which triggered the destructor call. 203263509Sdim const CXXDeleteExpr *getDeleteExpr() const { 204263509Sdim return static_cast<CXXDeleteExpr *>(Data2.getPointer()); 205263509Sdim } 206263509Sdim 207263509Sdim 208263509Sdimprivate: 209263509Sdim friend class CFGElement; 210263509Sdim CFGDeleteDtor() {} 211263509Sdim static bool isKind(const CFGElement &elem) { 212263509Sdim return elem.getKind() == DeleteDtor; 213263509Sdim } 214263509Sdim}; 215263509Sdim 216218893Sdim/// CFGBaseDtor - Represents C++ object destructor implicitly generated for 217218893Sdim/// base object in destructor. 218218893Sdimclass CFGBaseDtor : public CFGImplicitDtor { 219218893Sdimpublic: 220221345Sdim CFGBaseDtor(const CXXBaseSpecifier *base) 221221345Sdim : CFGImplicitDtor(BaseDtor, base) {} 222218893Sdim 223218893Sdim const CXXBaseSpecifier *getBaseSpecifier() const { 224218893Sdim return static_cast<const CXXBaseSpecifier*>(Data1.getPointer()); 225218893Sdim } 226218893Sdim 227252723Sdimprivate: 228252723Sdim friend class CFGElement; 229252723Sdim CFGBaseDtor() {} 230252723Sdim static bool isKind(const CFGElement &E) { 231252723Sdim return E.getKind() == BaseDtor; 232218893Sdim } 233218893Sdim}; 234218893Sdim 235218893Sdim/// CFGMemberDtor - Represents C++ object destructor implicitly generated for 236218893Sdim/// member object in destructor. 237218893Sdimclass CFGMemberDtor : public CFGImplicitDtor { 238218893Sdimpublic: 239221345Sdim CFGMemberDtor(const FieldDecl *field) 240221345Sdim : CFGImplicitDtor(MemberDtor, field, 0) {} 241218893Sdim 242221345Sdim const FieldDecl *getFieldDecl() const { 243221345Sdim return static_cast<const FieldDecl*>(Data1.getPointer()); 244218893Sdim } 245218893Sdim 246252723Sdimprivate: 247252723Sdim friend class CFGElement; 248252723Sdim CFGMemberDtor() {} 249252723Sdim static bool isKind(const CFGElement &E) { 250252723Sdim return E.getKind() == MemberDtor; 251218893Sdim } 252218893Sdim}; 253218893Sdim 254218893Sdim/// CFGTemporaryDtor - Represents C++ object destructor implicitly generated 255218893Sdim/// at the end of full expression for temporary object. 256218893Sdimclass CFGTemporaryDtor : public CFGImplicitDtor { 257218893Sdimpublic: 258221345Sdim CFGTemporaryDtor(CXXBindTemporaryExpr *expr) 259221345Sdim : CFGImplicitDtor(TemporaryDtor, expr, 0) {} 260218893Sdim 261221345Sdim const CXXBindTemporaryExpr *getBindTemporaryExpr() const { 262221345Sdim return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); 263218893Sdim } 264218893Sdim 265252723Sdimprivate: 266252723Sdim friend class CFGElement; 267252723Sdim CFGTemporaryDtor() {} 268252723Sdim static bool isKind(const CFGElement &E) { 269252723Sdim return E.getKind() == TemporaryDtor; 270218893Sdim } 271218893Sdim}; 272218893Sdim 273218893Sdim/// CFGTerminator - Represents CFGBlock terminator statement. 274218893Sdim/// 275218893Sdim/// TemporaryDtorsBranch bit is set to true if the terminator marks a branch 276218893Sdim/// in control flow of destructors of temporaries. In this case terminator 277218893Sdim/// statement is the same statement that branches control flow in evaluation 278218893Sdim/// of matching full expression. 279218893Sdimclass CFGTerminator { 280218893Sdim llvm::PointerIntPair<Stmt *, 1> Data; 281218893Sdimpublic: 282218893Sdim CFGTerminator() {} 283218893Sdim CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false) 284218893Sdim : Data(S, TemporaryDtorsBranch) {} 285218893Sdim 286218893Sdim Stmt *getStmt() { return Data.getPointer(); } 287218893Sdim const Stmt *getStmt() const { return Data.getPointer(); } 288218893Sdim 289218893Sdim bool isTemporaryDtorsBranch() const { return Data.getInt(); } 290218893Sdim 291218893Sdim operator Stmt *() { return getStmt(); } 292218893Sdim operator const Stmt *() const { return getStmt(); } 293218893Sdim 294218893Sdim Stmt *operator->() { return getStmt(); } 295218893Sdim const Stmt *operator->() const { return getStmt(); } 296218893Sdim 297218893Sdim Stmt &operator*() { return *getStmt(); } 298218893Sdim const Stmt &operator*() const { return *getStmt(); } 299218893Sdim 300263509Sdim LLVM_EXPLICIT operator bool() const { return getStmt(); } 301218893Sdim}; 302218893Sdim 303198092Srdivacky/// CFGBlock - Represents a single basic block in a source-level CFG. 304198092Srdivacky/// It consists of: 305198092Srdivacky/// 306198092Srdivacky/// (1) A set of statements/expressions (which may contain subexpressions). 307198092Srdivacky/// (2) A "terminator" statement (not in the set of statements). 308198092Srdivacky/// (3) A list of successors and predecessors. 309198092Srdivacky/// 310198092Srdivacky/// Terminator: The terminator represents the type of control-flow that occurs 311198092Srdivacky/// at the end of the basic block. The terminator is a Stmt* referring to an 312198092Srdivacky/// AST node that has control-flow: if-statements, breaks, loops, etc. 313198092Srdivacky/// If the control-flow is conditional, the condition expression will appear 314198092Srdivacky/// within the set of statements in the block (usually the last statement). 315198092Srdivacky/// 316198092Srdivacky/// Predecessors: the order in the set of predecessors is arbitrary. 317198092Srdivacky/// 318198092Srdivacky/// Successors: the order in the set of successors is NOT arbitrary. We 319198092Srdivacky/// currently have the following orderings based on the terminator: 320198092Srdivacky/// 321198092Srdivacky/// Terminator Successor Ordering 322198092Srdivacky/// ----------------------------------------------------- 323198092Srdivacky/// if Then Block; Else Block 324198092Srdivacky/// ? operator LHS expression; RHS expression 325198092Srdivacky/// &&, || expression that uses result of && or ||, RHS 326198092Srdivacky/// 327221345Sdim/// But note that any of that may be NULL in case of optimized-out edges. 328221345Sdim/// 329198092Srdivackyclass CFGBlock { 330218893Sdim class ElementList { 331201361Srdivacky typedef BumpVector<CFGElement> ImplTy; 332198092Srdivacky ImplTy Impl; 333198092Srdivacky public: 334218893Sdim ElementList(BumpVectorContext &C) : Impl(C, 4) {} 335235633Sdim 336198092Srdivacky typedef std::reverse_iterator<ImplTy::iterator> iterator; 337198092Srdivacky typedef std::reverse_iterator<ImplTy::const_iterator> const_iterator; 338198092Srdivacky typedef ImplTy::iterator reverse_iterator; 339235633Sdim typedef ImplTy::const_iterator const_reverse_iterator; 340245431Sdim typedef ImplTy::const_reference const_reference; 341235633Sdim 342201361Srdivacky void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); } 343218893Sdim reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E, 344226890Sdim BumpVectorContext &C) { 345218893Sdim return Impl.insert(I, Cnt, E, C); 346218893Sdim } 347218893Sdim 348245431Sdim const_reference front() const { return Impl.back(); } 349245431Sdim const_reference back() const { return Impl.front(); } 350235633Sdim 351198092Srdivacky iterator begin() { return Impl.rbegin(); } 352198092Srdivacky iterator end() { return Impl.rend(); } 353198092Srdivacky const_iterator begin() const { return Impl.rbegin(); } 354198092Srdivacky const_iterator end() const { return Impl.rend(); } 355198092Srdivacky reverse_iterator rbegin() { return Impl.begin(); } 356198092Srdivacky reverse_iterator rend() { return Impl.end(); } 357198092Srdivacky const_reverse_iterator rbegin() const { return Impl.begin(); } 358198092Srdivacky const_reverse_iterator rend() const { return Impl.end(); } 359198092Srdivacky 360201361Srdivacky CFGElement operator[](size_t i) const { 361198092Srdivacky assert(i < Impl.size()); 362198092Srdivacky return Impl[Impl.size() - 1 - i]; 363198092Srdivacky } 364235633Sdim 365198092Srdivacky size_t size() const { return Impl.size(); } 366198092Srdivacky bool empty() const { return Impl.empty(); } 367198092Srdivacky }; 368198092Srdivacky 369198092Srdivacky /// Stmts - The set of statements in the basic block. 370218893Sdim ElementList Elements; 371198092Srdivacky 372198092Srdivacky /// Label - An (optional) label that prefixes the executable 373198092Srdivacky /// statements in the block. When this variable is non-NULL, it is 374202879Srdivacky /// either an instance of LabelStmt, SwitchCase or CXXCatchStmt. 375198092Srdivacky Stmt *Label; 376198092Srdivacky 377198092Srdivacky /// Terminator - The terminator for a basic block that 378198092Srdivacky /// indicates the type of control-flow that occurs between a block 379198092Srdivacky /// and its successors. 380218893Sdim CFGTerminator Terminator; 381198092Srdivacky 382198092Srdivacky /// LoopTarget - Some blocks are used to represent the "loop edge" to 383198092Srdivacky /// the start of a loop from within the loop body. This Stmt* will be 384198092Srdivacky /// refer to the loop statement for such blocks (and be null otherwise). 385198092Srdivacky const Stmt *LoopTarget; 386198092Srdivacky 387198092Srdivacky /// BlockID - A numerical ID assigned to a CFGBlock during construction 388198092Srdivacky /// of the CFG. 389198092Srdivacky unsigned BlockID; 390198092Srdivacky 391198092Srdivacky /// Predecessors/Successors - Keep track of the predecessor / successor 392198092Srdivacky /// CFG blocks. 393198092Srdivacky typedef BumpVector<CFGBlock*> AdjacentBlocks; 394198092Srdivacky AdjacentBlocks Preds; 395198092Srdivacky AdjacentBlocks Succs; 396198092Srdivacky 397226890Sdim /// NoReturn - This bit is set when the basic block contains a function call 398226890Sdim /// or implicit destructor that is attributed as 'noreturn'. In that case, 399226890Sdim /// control cannot technically ever proceed past this block. All such blocks 400226890Sdim /// will have a single immediate successor: the exit block. This allows them 401226890Sdim /// to be easily reached from the exit block and using this bit quickly 402226890Sdim /// recognized without scanning the contents of the block. 403226890Sdim /// 404226890Sdim /// Optimization Note: This bit could be profitably folded with Terminator's 405226890Sdim /// storage if the memory usage of CFGBlock becomes an issue. 406226890Sdim unsigned HasNoReturnElement : 1; 407226890Sdim 408235633Sdim /// Parent - The parent CFG that owns this CFGBlock. 409235633Sdim CFG *Parent; 410235633Sdim 411198092Srdivackypublic: 412235633Sdim explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent) 413235633Sdim : Elements(C), Label(NULL), Terminator(NULL), LoopTarget(NULL), 414235633Sdim BlockID(blockid), Preds(C, 1), Succs(C, 1), HasNoReturnElement(false), 415235633Sdim Parent(parent) {} 416201361Srdivacky ~CFGBlock() {} 417198092Srdivacky 418198092Srdivacky // Statement iterators 419218893Sdim typedef ElementList::iterator iterator; 420218893Sdim typedef ElementList::const_iterator const_iterator; 421218893Sdim typedef ElementList::reverse_iterator reverse_iterator; 422218893Sdim typedef ElementList::const_reverse_iterator const_reverse_iterator; 423198092Srdivacky 424218893Sdim CFGElement front() const { return Elements.front(); } 425218893Sdim CFGElement back() const { return Elements.back(); } 426198092Srdivacky 427218893Sdim iterator begin() { return Elements.begin(); } 428218893Sdim iterator end() { return Elements.end(); } 429218893Sdim const_iterator begin() const { return Elements.begin(); } 430218893Sdim const_iterator end() const { return Elements.end(); } 431198092Srdivacky 432218893Sdim reverse_iterator rbegin() { return Elements.rbegin(); } 433218893Sdim reverse_iterator rend() { return Elements.rend(); } 434218893Sdim const_reverse_iterator rbegin() const { return Elements.rbegin(); } 435218893Sdim const_reverse_iterator rend() const { return Elements.rend(); } 436198092Srdivacky 437218893Sdim unsigned size() const { return Elements.size(); } 438218893Sdim bool empty() const { return Elements.empty(); } 439198092Srdivacky 440218893Sdim CFGElement operator[](size_t i) const { return Elements[i]; } 441198092Srdivacky 442198092Srdivacky // CFG iterators 443198092Srdivacky typedef AdjacentBlocks::iterator pred_iterator; 444198092Srdivacky typedef AdjacentBlocks::const_iterator const_pred_iterator; 445198092Srdivacky typedef AdjacentBlocks::reverse_iterator pred_reverse_iterator; 446198092Srdivacky typedef AdjacentBlocks::const_reverse_iterator const_pred_reverse_iterator; 447198092Srdivacky 448198092Srdivacky typedef AdjacentBlocks::iterator succ_iterator; 449198092Srdivacky typedef AdjacentBlocks::const_iterator const_succ_iterator; 450198092Srdivacky typedef AdjacentBlocks::reverse_iterator succ_reverse_iterator; 451198092Srdivacky typedef AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator; 452198092Srdivacky 453198092Srdivacky pred_iterator pred_begin() { return Preds.begin(); } 454198092Srdivacky pred_iterator pred_end() { return Preds.end(); } 455198092Srdivacky const_pred_iterator pred_begin() const { return Preds.begin(); } 456198092Srdivacky const_pred_iterator pred_end() const { return Preds.end(); } 457198092Srdivacky 458198092Srdivacky pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); } 459198092Srdivacky pred_reverse_iterator pred_rend() { return Preds.rend(); } 460198092Srdivacky const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); } 461198092Srdivacky const_pred_reverse_iterator pred_rend() const { return Preds.rend(); } 462198092Srdivacky 463198092Srdivacky succ_iterator succ_begin() { return Succs.begin(); } 464198092Srdivacky succ_iterator succ_end() { return Succs.end(); } 465198092Srdivacky const_succ_iterator succ_begin() const { return Succs.begin(); } 466198092Srdivacky const_succ_iterator succ_end() const { return Succs.end(); } 467198092Srdivacky 468198092Srdivacky succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); } 469198092Srdivacky succ_reverse_iterator succ_rend() { return Succs.rend(); } 470198092Srdivacky const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); } 471198092Srdivacky const_succ_reverse_iterator succ_rend() const { return Succs.rend(); } 472198092Srdivacky 473198092Srdivacky unsigned succ_size() const { return Succs.size(); } 474198092Srdivacky bool succ_empty() const { return Succs.empty(); } 475198092Srdivacky 476198092Srdivacky unsigned pred_size() const { return Preds.size(); } 477198092Srdivacky bool pred_empty() const { return Preds.empty(); } 478198092Srdivacky 479218893Sdim 480218893Sdim class FilterOptions { 481218893Sdim public: 482218893Sdim FilterOptions() { 483218893Sdim IgnoreDefaultsWithCoveredEnums = 0; 484218893Sdim } 485218893Sdim 486218893Sdim unsigned IgnoreDefaultsWithCoveredEnums : 1; 487218893Sdim }; 488218893Sdim 489218893Sdim static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src, 490218893Sdim const CFGBlock *Dst); 491218893Sdim 492218893Sdim template <typename IMPL, bool IsPred> 493218893Sdim class FilteredCFGBlockIterator { 494218893Sdim private: 495218893Sdim IMPL I, E; 496218893Sdim const FilterOptions F; 497218893Sdim const CFGBlock *From; 498218893Sdim public: 499218893Sdim explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e, 500218893Sdim const CFGBlock *from, 501218893Sdim const FilterOptions &f) 502218893Sdim : I(i), E(e), F(f), From(from) {} 503218893Sdim 504218893Sdim bool hasMore() const { return I != E; } 505218893Sdim 506218893Sdim FilteredCFGBlockIterator &operator++() { 507218893Sdim do { ++I; } while (hasMore() && Filter(*I)); 508218893Sdim return *this; 509218893Sdim } 510218893Sdim 511218893Sdim const CFGBlock *operator*() const { return *I; } 512218893Sdim private: 513218893Sdim bool Filter(const CFGBlock *To) { 514218893Sdim return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To); 515218893Sdim } 516218893Sdim }; 517218893Sdim 518218893Sdim typedef FilteredCFGBlockIterator<const_pred_iterator, true> 519218893Sdim filtered_pred_iterator; 520218893Sdim 521218893Sdim typedef FilteredCFGBlockIterator<const_succ_iterator, false> 522218893Sdim filtered_succ_iterator; 523218893Sdim 524218893Sdim filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const { 525218893Sdim return filtered_pred_iterator(pred_begin(), pred_end(), this, f); 526218893Sdim } 527218893Sdim 528218893Sdim filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const { 529218893Sdim return filtered_succ_iterator(succ_begin(), succ_end(), this, f); 530218893Sdim } 531218893Sdim 532198092Srdivacky // Manipulation of block contents 533198092Srdivacky 534226890Sdim void setTerminator(Stmt *Statement) { Terminator = Statement; } 535226890Sdim void setLabel(Stmt *Statement) { Label = Statement; } 536198092Srdivacky void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; } 537226890Sdim void setHasNoReturnElement() { HasNoReturnElement = true; } 538198092Srdivacky 539218893Sdim CFGTerminator getTerminator() { return Terminator; } 540218893Sdim const CFGTerminator getTerminator() const { return Terminator; } 541198092Srdivacky 542226890Sdim Stmt *getTerminatorCondition(); 543198092Srdivacky 544226890Sdim const Stmt *getTerminatorCondition() const { 545198092Srdivacky return const_cast<CFGBlock*>(this)->getTerminatorCondition(); 546198092Srdivacky } 547198092Srdivacky 548198092Srdivacky const Stmt *getLoopTarget() const { return LoopTarget; } 549198092Srdivacky 550226890Sdim Stmt *getLabel() { return Label; } 551226890Sdim const Stmt *getLabel() const { return Label; } 552198092Srdivacky 553226890Sdim bool hasNoReturnElement() const { return HasNoReturnElement; } 554226890Sdim 555198092Srdivacky unsigned getBlockID() const { return BlockID; } 556198092Srdivacky 557235633Sdim CFG *getParent() const { return Parent; } 558235633Sdim 559235633Sdim void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const; 560235633Sdim void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO, 561235633Sdim bool ShowColors) const; 562226890Sdim void printTerminator(raw_ostream &OS, const LangOptions &LO) const; 563235633Sdim 564226890Sdim void addSuccessor(CFGBlock *Block, BumpVectorContext &C) { 565198092Srdivacky if (Block) 566198092Srdivacky Block->Preds.push_back(this, C); 567198092Srdivacky Succs.push_back(Block, C); 568198092Srdivacky } 569235633Sdim 570226890Sdim void appendStmt(Stmt *statement, BumpVectorContext &C) { 571218893Sdim Elements.push_back(CFGStmt(statement), C); 572202879Srdivacky } 573218893Sdim 574218893Sdim void appendInitializer(CXXCtorInitializer *initializer, 575226890Sdim BumpVectorContext &C) { 576218893Sdim Elements.push_back(CFGInitializer(initializer), C); 577202879Srdivacky } 578218893Sdim 579218893Sdim void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { 580218893Sdim Elements.push_back(CFGBaseDtor(BS), C); 581218893Sdim } 582218893Sdim 583218893Sdim void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) { 584218893Sdim Elements.push_back(CFGMemberDtor(FD), C); 585218893Sdim } 586235633Sdim 587218893Sdim void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) { 588218893Sdim Elements.push_back(CFGTemporaryDtor(E), C); 589218893Sdim } 590218893Sdim 591226890Sdim void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) { 592226890Sdim Elements.push_back(CFGAutomaticObjDtor(VD, S), C); 593226890Sdim } 594226890Sdim 595263509Sdim void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { 596263509Sdim Elements.push_back(CFGDeleteDtor(RD, DE), C); 597263509Sdim } 598263509Sdim 599218893Sdim // Destructors must be inserted in reversed order. So insertion is in two 600218893Sdim // steps. First we prepare space for some number of elements, then we insert 601218893Sdim // the elements beginning at the last position in prepared space. 602218893Sdim iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt, 603226890Sdim BumpVectorContext &C) { 604252723Sdim return iterator(Elements.insert(I.base(), Cnt, CFGAutomaticObjDtor(0, 0), C)); 605218893Sdim } 606226890Sdim iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) { 607218893Sdim *I = CFGAutomaticObjDtor(VD, S); 608218893Sdim return ++I; 609218893Sdim } 610198092Srdivacky}; 611198092Srdivacky 612198092Srdivacky/// CFG - Represents a source-level, intra-procedural CFG that represents the 613198092Srdivacky/// control-flow of a Stmt. The Stmt can represent an entire function body, 614198092Srdivacky/// or a single expression. A CFG will always contain one empty block that 615198092Srdivacky/// represents the Exit point of the CFG. A CFG will also contain a designated 616198092Srdivacky/// Entry block. The CFG solely represents control-flow; it consists of 617198092Srdivacky/// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG 618198092Srdivacky/// was constructed from. 619198092Srdivackyclass CFG { 620198092Srdivackypublic: 621198092Srdivacky //===--------------------------------------------------------------------===// 622198092Srdivacky // CFG Construction & Manipulation. 623198092Srdivacky //===--------------------------------------------------------------------===// 624198092Srdivacky 625218893Sdim class BuildOptions { 626245431Sdim std::bitset<Stmt::lastStmtConstant> alwaysAddMask; 627218893Sdim public: 628221345Sdim typedef llvm::DenseMap<const Stmt *, const CFGBlock*> ForcedBlkExprs; 629235633Sdim ForcedBlkExprs **forcedBlkExprs; 630221345Sdim 631226890Sdim bool PruneTriviallyFalseEdges; 632226890Sdim bool AddEHEdges; 633226890Sdim bool AddInitializers; 634226890Sdim bool AddImplicitDtors; 635245431Sdim bool AddTemporaryDtors; 636252723Sdim bool AddStaticInitBranches; 637235633Sdim 638226890Sdim bool alwaysAdd(const Stmt *stmt) const { 639226890Sdim return alwaysAddMask[stmt->getStmtClass()]; 640226890Sdim } 641235633Sdim 642226890Sdim BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { 643226890Sdim alwaysAddMask[stmtClass] = val; 644226890Sdim return *this; 645226890Sdim } 646235633Sdim 647226890Sdim BuildOptions &setAllAlwaysAdd() { 648226890Sdim alwaysAddMask.set(); 649226890Sdim return *this; 650226890Sdim } 651218893Sdim 652218893Sdim BuildOptions() 653245431Sdim : forcedBlkExprs(0), PruneTriviallyFalseEdges(true) 654226890Sdim ,AddEHEdges(false) 655226890Sdim ,AddInitializers(false) 656245431Sdim ,AddImplicitDtors(false) 657252723Sdim ,AddTemporaryDtors(false) 658252723Sdim ,AddStaticInitBranches(false) {} 659218893Sdim }; 660218893Sdim 661235633Sdim /// \brief Provides a custom implementation of the iterator class to have the 662235633Sdim /// same interface as Function::iterator - iterator returns CFGBlock 663235633Sdim /// (not a pointer to CFGBlock). 664235633Sdim class graph_iterator { 665235633Sdim public: 666235633Sdim typedef const CFGBlock value_type; 667235633Sdim typedef value_type& reference; 668235633Sdim typedef value_type* pointer; 669235633Sdim typedef BumpVector<CFGBlock*>::iterator ImplTy; 670235633Sdim 671235633Sdim graph_iterator(const ImplTy &i) : I(i) {} 672235633Sdim 673235633Sdim bool operator==(const graph_iterator &X) const { return I == X.I; } 674235633Sdim bool operator!=(const graph_iterator &X) const { return I != X.I; } 675235633Sdim 676235633Sdim reference operator*() const { return **I; } 677235633Sdim pointer operator->() const { return *I; } 678235633Sdim operator CFGBlock* () { return *I; } 679235633Sdim 680235633Sdim graph_iterator &operator++() { ++I; return *this; } 681235633Sdim graph_iterator &operator--() { --I; return *this; } 682235633Sdim 683235633Sdim private: 684235633Sdim ImplTy I; 685235633Sdim }; 686235633Sdim 687235633Sdim class const_graph_iterator { 688235633Sdim public: 689235633Sdim typedef const CFGBlock value_type; 690235633Sdim typedef value_type& reference; 691235633Sdim typedef value_type* pointer; 692235633Sdim typedef BumpVector<CFGBlock*>::const_iterator ImplTy; 693235633Sdim 694235633Sdim const_graph_iterator(const ImplTy &i) : I(i) {} 695235633Sdim 696235633Sdim bool operator==(const const_graph_iterator &X) const { return I == X.I; } 697235633Sdim bool operator!=(const const_graph_iterator &X) const { return I != X.I; } 698235633Sdim 699235633Sdim reference operator*() const { return **I; } 700235633Sdim pointer operator->() const { return *I; } 701235633Sdim operator CFGBlock* () const { return *I; } 702235633Sdim 703235633Sdim const_graph_iterator &operator++() { ++I; return *this; } 704235633Sdim const_graph_iterator &operator--() { --I; return *this; } 705235633Sdim 706235633Sdim private: 707235633Sdim ImplTy I; 708235633Sdim }; 709235633Sdim 710198092Srdivacky /// buildCFG - Builds a CFG from an AST. The responsibility to free the 711198092Srdivacky /// constructed CFG belongs to the caller. 712226890Sdim static CFG* buildCFG(const Decl *D, Stmt *AST, ASTContext *C, 713221345Sdim const BuildOptions &BO); 714198092Srdivacky 715198092Srdivacky /// createBlock - Create a new block in the CFG. The CFG owns the block; 716198092Srdivacky /// the caller should not directly free it. 717226890Sdim CFGBlock *createBlock(); 718198092Srdivacky 719198092Srdivacky /// setEntry - Set the entry block of the CFG. This is typically used 720198092Srdivacky /// only during CFG construction. Most CFG clients expect that the 721198092Srdivacky /// entry block has no predecessors and contains no statements. 722198092Srdivacky void setEntry(CFGBlock *B) { Entry = B; } 723198092Srdivacky 724198092Srdivacky /// setIndirectGotoBlock - Set the block used for indirect goto jumps. 725198092Srdivacky /// This is typically used only during CFG construction. 726226890Sdim void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; } 727198092Srdivacky 728198092Srdivacky //===--------------------------------------------------------------------===// 729198092Srdivacky // Block Iterators 730198092Srdivacky //===--------------------------------------------------------------------===// 731198092Srdivacky 732235633Sdim typedef BumpVector<CFGBlock*> CFGBlockListTy; 733198092Srdivacky typedef CFGBlockListTy::iterator iterator; 734198092Srdivacky typedef CFGBlockListTy::const_iterator const_iterator; 735198092Srdivacky typedef std::reverse_iterator<iterator> reverse_iterator; 736198092Srdivacky typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 737198092Srdivacky 738226890Sdim CFGBlock & front() { return *Blocks.front(); } 739226890Sdim CFGBlock & back() { return *Blocks.back(); } 740198092Srdivacky 741198092Srdivacky iterator begin() { return Blocks.begin(); } 742198092Srdivacky iterator end() { return Blocks.end(); } 743198092Srdivacky const_iterator begin() const { return Blocks.begin(); } 744198092Srdivacky const_iterator end() const { return Blocks.end(); } 745198092Srdivacky 746235633Sdim graph_iterator nodes_begin() { return graph_iterator(Blocks.begin()); } 747235633Sdim graph_iterator nodes_end() { return graph_iterator(Blocks.end()); } 748235633Sdim const_graph_iterator nodes_begin() const { 749235633Sdim return const_graph_iterator(Blocks.begin()); 750235633Sdim } 751235633Sdim const_graph_iterator nodes_end() const { 752235633Sdim return const_graph_iterator(Blocks.end()); 753235633Sdim } 754235633Sdim 755198092Srdivacky reverse_iterator rbegin() { return Blocks.rbegin(); } 756198092Srdivacky reverse_iterator rend() { return Blocks.rend(); } 757198092Srdivacky const_reverse_iterator rbegin() const { return Blocks.rbegin(); } 758198092Srdivacky const_reverse_iterator rend() const { return Blocks.rend(); } 759198092Srdivacky 760226890Sdim CFGBlock & getEntry() { return *Entry; } 761226890Sdim const CFGBlock & getEntry() const { return *Entry; } 762226890Sdim CFGBlock & getExit() { return *Exit; } 763226890Sdim const CFGBlock & getExit() const { return *Exit; } 764198092Srdivacky 765226890Sdim CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; } 766226890Sdim const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } 767235633Sdim 768226890Sdim typedef std::vector<const CFGBlock*>::const_iterator try_block_iterator; 769226890Sdim try_block_iterator try_blocks_begin() const { 770226890Sdim return TryDispatchBlocks.begin(); 771226890Sdim } 772226890Sdim try_block_iterator try_blocks_end() const { 773226890Sdim return TryDispatchBlocks.end(); 774226890Sdim } 775235633Sdim 776226890Sdim void addTryDispatchBlock(const CFGBlock *block) { 777226890Sdim TryDispatchBlocks.push_back(block); 778226890Sdim } 779198092Srdivacky 780263509Sdim /// Records a synthetic DeclStmt and the DeclStmt it was constructed from. 781263509Sdim /// 782263509Sdim /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains 783263509Sdim /// multiple decls. 784263509Sdim void addSyntheticDeclStmt(const DeclStmt *Synthetic, 785263509Sdim const DeclStmt *Source) { 786263509Sdim assert(Synthetic->isSingleDecl() && "Can handle single declarations only"); 787263509Sdim assert(Synthetic != Source && "Don't include original DeclStmts in map"); 788263509Sdim assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map"); 789263509Sdim SyntheticDeclStmts[Synthetic] = Source; 790263509Sdim } 791263509Sdim 792263509Sdim typedef llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator 793263509Sdim synthetic_stmt_iterator; 794263509Sdim 795263509Sdim /// Iterates over synthetic DeclStmts in the CFG. 796263509Sdim /// 797263509Sdim /// Each element is a (synthetic statement, source statement) pair. 798263509Sdim /// 799263509Sdim /// \sa addSyntheticDeclStmt 800263509Sdim synthetic_stmt_iterator synthetic_stmt_begin() const { 801263509Sdim return SyntheticDeclStmts.begin(); 802263509Sdim } 803263509Sdim 804263509Sdim /// \sa synthetic_stmt_begin 805263509Sdim synthetic_stmt_iterator synthetic_stmt_end() const { 806263509Sdim return SyntheticDeclStmts.end(); 807263509Sdim } 808263509Sdim 809198092Srdivacky //===--------------------------------------------------------------------===// 810198092Srdivacky // Member templates useful for various batch operations over CFGs. 811198092Srdivacky //===--------------------------------------------------------------------===// 812198092Srdivacky 813198092Srdivacky template <typename CALLBACK> 814198092Srdivacky void VisitBlockStmts(CALLBACK& O) const { 815198092Srdivacky for (const_iterator I=begin(), E=end(); I != E; ++I) 816198092Srdivacky for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end(); 817218893Sdim BI != BE; ++BI) { 818252723Sdim if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) 819226890Sdim O(const_cast<Stmt*>(stmt->getStmt())); 820218893Sdim } 821198092Srdivacky } 822198092Srdivacky 823198092Srdivacky //===--------------------------------------------------------------------===// 824198092Srdivacky // CFG Introspection. 825198092Srdivacky //===--------------------------------------------------------------------===// 826198092Srdivacky 827198092Srdivacky /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which 828198092Srdivacky /// start at 0). 829198092Srdivacky unsigned getNumBlockIDs() const { return NumBlockIDs; } 830198092Srdivacky 831235633Sdim /// size - Return the total number of CFGBlocks within the CFG 832235633Sdim /// This is simply a renaming of the getNumBlockIDs(). This is necessary 833235633Sdim /// because the dominator implementation needs such an interface. 834235633Sdim unsigned size() const { return NumBlockIDs; } 835235633Sdim 836198092Srdivacky //===--------------------------------------------------------------------===// 837198092Srdivacky // CFG Debugging: Pretty-Printing and Visualization. 838198092Srdivacky //===--------------------------------------------------------------------===// 839198092Srdivacky 840198092Srdivacky void viewCFG(const LangOptions &LO) const; 841235633Sdim void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const; 842235633Sdim void dump(const LangOptions &LO, bool ShowColors) const; 843198092Srdivacky 844198092Srdivacky //===--------------------------------------------------------------------===// 845198092Srdivacky // Internal: constructors and data. 846198092Srdivacky //===--------------------------------------------------------------------===// 847198092Srdivacky 848198092Srdivacky CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0), 849263509Sdim Blocks(BlkBVC, 10) {} 850198092Srdivacky 851198092Srdivacky llvm::BumpPtrAllocator& getAllocator() { 852198092Srdivacky return BlkBVC.getAllocator(); 853198092Srdivacky } 854235633Sdim 855198092Srdivacky BumpVectorContext &getBumpVectorContext() { 856198092Srdivacky return BlkBVC; 857198092Srdivacky } 858198092Srdivacky 859198092Srdivackyprivate: 860226890Sdim CFGBlock *Entry; 861226890Sdim CFGBlock *Exit; 862198092Srdivacky CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch 863198092Srdivacky // for indirect gotos 864198092Srdivacky unsigned NumBlockIDs; 865198092Srdivacky 866198092Srdivacky BumpVectorContext BlkBVC; 867235633Sdim 868198092Srdivacky CFGBlockListTy Blocks; 869235633Sdim 870226890Sdim /// C++ 'try' statements are modeled with an indirect dispatch block. 871226890Sdim /// This is the collection of such blocks present in the CFG. 872226890Sdim std::vector<const CFGBlock *> TryDispatchBlocks; 873198092Srdivacky 874263509Sdim /// Collects DeclStmts synthesized for this CFG and maps each one back to its 875263509Sdim /// source DeclStmt. 876263509Sdim llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; 877198092Srdivacky}; 878198092Srdivacky} // end namespace clang 879198092Srdivacky 880198092Srdivacky//===----------------------------------------------------------------------===// 881198092Srdivacky// GraphTraits specializations for CFG basic block graphs (source-level CFGs) 882198092Srdivacky//===----------------------------------------------------------------------===// 883198092Srdivacky 884198092Srdivackynamespace llvm { 885198092Srdivacky 886218893Sdim/// Implement simplify_type for CFGTerminator, so that we can dyn_cast from 887218893Sdim/// CFGTerminator to a specific Stmt class. 888218893Sdimtemplate <> struct simplify_type< ::clang::CFGTerminator> { 889218893Sdim typedef ::clang::Stmt *SimpleType; 890252723Sdim static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) { 891252723Sdim return Val.getStmt(); 892218893Sdim } 893218893Sdim}; 894218893Sdim 895198092Srdivacky// Traits for: CFGBlock 896198092Srdivacky 897226890Sdimtemplate <> struct GraphTraits< ::clang::CFGBlock *> { 898201361Srdivacky typedef ::clang::CFGBlock NodeType; 899201361Srdivacky typedef ::clang::CFGBlock::succ_iterator ChildIteratorType; 900198092Srdivacky 901226890Sdim static NodeType* getEntryNode(::clang::CFGBlock *BB) 902198092Srdivacky { return BB; } 903198092Srdivacky 904198092Srdivacky static inline ChildIteratorType child_begin(NodeType* N) 905198092Srdivacky { return N->succ_begin(); } 906198092Srdivacky 907198092Srdivacky static inline ChildIteratorType child_end(NodeType* N) 908198092Srdivacky { return N->succ_end(); } 909198092Srdivacky}; 910198092Srdivacky 911226890Sdimtemplate <> struct GraphTraits< const ::clang::CFGBlock *> { 912201361Srdivacky typedef const ::clang::CFGBlock NodeType; 913201361Srdivacky typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType; 914198092Srdivacky 915226890Sdim static NodeType* getEntryNode(const clang::CFGBlock *BB) 916198092Srdivacky { return BB; } 917198092Srdivacky 918198092Srdivacky static inline ChildIteratorType child_begin(NodeType* N) 919198092Srdivacky { return N->succ_begin(); } 920198092Srdivacky 921198092Srdivacky static inline ChildIteratorType child_end(NodeType* N) 922198092Srdivacky { return N->succ_end(); } 923198092Srdivacky}; 924198092Srdivacky 925235633Sdimtemplate <> struct GraphTraits<Inverse< ::clang::CFGBlock*> > { 926235633Sdim typedef ::clang::CFGBlock NodeType; 927235633Sdim typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType; 928235633Sdim 929235633Sdim static NodeType *getEntryNode(Inverse< ::clang::CFGBlock*> G) 930235633Sdim { return G.Graph; } 931235633Sdim 932235633Sdim static inline ChildIteratorType child_begin(NodeType* N) 933235633Sdim { return N->pred_begin(); } 934235633Sdim 935235633Sdim static inline ChildIteratorType child_end(NodeType* N) 936235633Sdim { return N->pred_end(); } 937235633Sdim}; 938235633Sdim 939201361Srdivackytemplate <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > { 940201361Srdivacky typedef const ::clang::CFGBlock NodeType; 941201361Srdivacky typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType; 942198092Srdivacky 943201361Srdivacky static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G) 944198092Srdivacky { return G.Graph; } 945198092Srdivacky 946198092Srdivacky static inline ChildIteratorType child_begin(NodeType* N) 947198092Srdivacky { return N->pred_begin(); } 948198092Srdivacky 949198092Srdivacky static inline ChildIteratorType child_end(NodeType* N) 950198092Srdivacky { return N->pred_end(); } 951198092Srdivacky}; 952198092Srdivacky 953198092Srdivacky// Traits for: CFG 954198092Srdivacky 955201361Srdivackytemplate <> struct GraphTraits< ::clang::CFG* > 956226890Sdim : public GraphTraits< ::clang::CFGBlock *> { 957198092Srdivacky 958235633Sdim typedef ::clang::CFG::graph_iterator nodes_iterator; 959198092Srdivacky 960235633Sdim static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); } 961235633Sdim static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} 962235633Sdim static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } 963235633Sdim static unsigned size(::clang::CFG* F) { return F->size(); } 964198092Srdivacky}; 965198092Srdivacky 966201361Srdivackytemplate <> struct GraphTraits<const ::clang::CFG* > 967226890Sdim : public GraphTraits<const ::clang::CFGBlock *> { 968198092Srdivacky 969235633Sdim typedef ::clang::CFG::const_graph_iterator nodes_iterator; 970198092Srdivacky 971201361Srdivacky static NodeType *getEntryNode( const ::clang::CFG* F) { 972201361Srdivacky return &F->getEntry(); 973201361Srdivacky } 974201361Srdivacky static nodes_iterator nodes_begin( const ::clang::CFG* F) { 975235633Sdim return F->nodes_begin(); 976201361Srdivacky } 977201361Srdivacky static nodes_iterator nodes_end( const ::clang::CFG* F) { 978235633Sdim return F->nodes_end(); 979201361Srdivacky } 980235633Sdim static unsigned size(const ::clang::CFG* F) { 981235633Sdim return F->size(); 982235633Sdim } 983198092Srdivacky}; 984198092Srdivacky 985235633Sdimtemplate <> struct GraphTraits<Inverse< ::clang::CFG*> > 986235633Sdim : public GraphTraits<Inverse< ::clang::CFGBlock*> > { 987235633Sdim 988235633Sdim typedef ::clang::CFG::graph_iterator nodes_iterator; 989235633Sdim 990235633Sdim static NodeType *getEntryNode( ::clang::CFG* F) { return &F->getExit(); } 991235633Sdim static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} 992235633Sdim static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } 993235633Sdim}; 994235633Sdim 995201361Srdivackytemplate <> struct GraphTraits<Inverse<const ::clang::CFG*> > 996201361Srdivacky : public GraphTraits<Inverse<const ::clang::CFGBlock*> > { 997198092Srdivacky 998235633Sdim typedef ::clang::CFG::const_graph_iterator nodes_iterator; 999198092Srdivacky 1000201361Srdivacky static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); } 1001235633Sdim static nodes_iterator nodes_begin(const ::clang::CFG* F) { 1002235633Sdim return F->nodes_begin(); 1003235633Sdim } 1004235633Sdim static nodes_iterator nodes_end(const ::clang::CFG* F) { 1005235633Sdim return F->nodes_end(); 1006235633Sdim } 1007198092Srdivacky}; 1008198092Srdivacky} // end llvm namespace 1009198092Srdivacky#endif 1010