CFG.h revision 63b3afa98460ce38a1c48d3c44ef6edfdaf37b77
1386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===-- llvm/Support/CFG.h - Process LLVM structures as graphs --*- C++ -*-===// 2386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// 3386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// The LLVM Compiler Infrastructure 4386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// 5386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// This file was developed by the LLVM research group and is distributed under 6386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// the University of Illinois Open Source License. See LICENSE.TXT for details. 7386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// 8386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===----------------------------------------------------------------------===// 9386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// 10386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// This file defines specializations of GraphTraits that allow Function and 11386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// BasicBlock graphs to be treated as proper graphs for generic algorithms. 12386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// 13386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===----------------------------------------------------------------------===// 14386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 15386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifndef LLVM_SUPPORT_CFG_H 16386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#define LLVM_SUPPORT_CFG_H 17386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 18386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "llvm/ADT/GraphTraits.h" 19386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "llvm/Function.h" 20386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "llvm/InstrTypes.h" 21386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "llvm/ADT/iterator" 22386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 23386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarinamespace llvm { 24386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 25386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 26386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// BasicBlock pred_iterator definition 27386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 28386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 29386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <class _Ptr, class _USE_iterator> // Predecessor Iterator 30386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariclass PredIterator : public forward_iterator<_Ptr, ptrdiff_t> { 31386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef forward_iterator<_Ptr, ptrdiff_t> super; 32386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari _Ptr *BB; 33386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari _USE_iterator It; 34386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaripublic: 35386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef PredIterator<_Ptr,_USE_iterator> _Self; 36386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef typename super::pointer pointer; 37386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 38386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline void advancePastNonTerminators() { 39386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // Loop to ignore non terminator uses (for example PHI nodes)... 40386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari while (It != BB->use_end() && !isa<TerminatorInst>(*It)) 41386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++It; 42386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 43386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 44386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) { 45386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari advancePastNonTerminators(); 46386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 47386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {} 48386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 49386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline bool operator==(const _Self& x) const { return It == x.It; } 50386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline bool operator!=(const _Self& x) const { return !operator==(x); } 51386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 52386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline pointer operator*() const { 53386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari assert(It != BB->use_end() && "pred_iterator out of range!"); 54386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return cast<TerminatorInst>(*It)->getParent(); 55386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 56386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline pointer *operator->() const { return &(operator*()); } 57386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 58386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline _Self& operator++() { // Preincrement 59386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari assert(It != BB->use_end() && "pred_iterator out of range!"); 60386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++It; advancePastNonTerminators(); 61386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return *this; 62386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 63386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 64386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline _Self operator++(int) { // Postincrement 65386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari _Self tmp = *this; ++*this; return tmp; 66386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 67386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 68386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 69386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritypedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator; 70386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritypedef PredIterator<const BasicBlock, 71386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari Value::use_const_iterator> pred_const_iterator; 72386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 73386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); } 74386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline pred_const_iterator pred_begin(const BasicBlock *BB) { 75386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return pred_const_iterator(BB); 76386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 77386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);} 78386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline pred_const_iterator pred_end(const BasicBlock *BB) { 79386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return pred_const_iterator(BB, true); 80386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 81386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 82386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 83386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 84386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 85386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// BasicBlock succ_iterator definition 86386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 87386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 88386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <class Term_, class BB_> // Successor Iterator 89386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariclass SuccIterator : public bidirectional_iterator<BB_, ptrdiff_t> { 90386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari const Term_ Term; 91386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari unsigned idx; 92386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef bidirectional_iterator<BB_, ptrdiff_t> super; 93386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaripublic: 94386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef SuccIterator<Term_, BB_> _Self; 95386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef typename super::pointer pointer; 96386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // TODO: This can be random access iterator, need operator+ and stuff tho 97386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 98386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline SuccIterator(Term_ T) : Term(T), idx(0) { // begin iterator 99386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari assert(T && "getTerminator returned null!"); 100386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 101386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline SuccIterator(Term_ T, bool) // end iterator 102386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari : Term(T), idx(Term->getNumSuccessors()) { 103386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari assert(T && "getTerminator returned null!"); 104386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 105386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 106386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline const _Self &operator=(const _Self &I) { 107386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari assert(Term == I.Term &&"Cannot assign iterators to two different blocks!"); 108386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari idx = I.idx; 109386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return *this; 110386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 111386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 112386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /// getSuccessorIndex - This is used to interface between code that wants to 113386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /// operate on terminator instructions directly. 114386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari unsigned getSuccessorIndex() const { return idx; } 115386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 116386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline bool operator==(const _Self& x) const { return idx == x.idx; } 117386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline bool operator!=(const _Self& x) const { return !operator==(x); } 118386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 119386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline pointer operator*() const { return Term->getSuccessor(idx); } 120386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline pointer operator->() const { return operator*(); } 121386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 122386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline _Self& operator++() { ++idx; return *this; } // Preincrement 123386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline _Self operator++(int) { // Postincrement 124386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari _Self tmp = *this; ++*this; return tmp; 125386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 126386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 127386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline _Self& operator--() { --idx; return *this; } // Predecrement 128386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari inline _Self operator--(int) { // Postdecrement 129386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari _Self tmp = *this; --*this; return tmp; 130386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 131386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 132386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 133386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritypedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator; 134386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritypedef SuccIterator<const TerminatorInst*, 135386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari const BasicBlock> succ_const_iterator; 136386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 137386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline succ_iterator succ_begin(BasicBlock *BB) { 138386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_iterator(BB->getTerminator()); 139386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 140386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline succ_const_iterator succ_begin(const BasicBlock *BB) { 141386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_const_iterator(BB->getTerminator()); 142386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 143386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline succ_iterator succ_end(BasicBlock *BB) { 144386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_iterator(BB->getTerminator(), true); 145386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 146386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariinline succ_const_iterator succ_end(const BasicBlock *BB) { 147386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_const_iterator(BB->getTerminator(), true); 148386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 149386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 150386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 151386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 152386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 153386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// GraphTraits specializations for basic block graphs (CFGs) 154386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 155386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 156386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// Provide specializations of GraphTraits to be able to treat a function as a 157386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// graph of basic blocks... 158386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 159386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <> struct GraphTraits<BasicBlock*> { 160386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef BasicBlock NodeType; 161386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef succ_iterator ChildIteratorType; 162386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 163386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static NodeType *getEntryNode(BasicBlock *BB) { return BB; } 164386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_begin(NodeType *N) { 165386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_begin(N); 166386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 167386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_end(NodeType *N) { 168386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_end(N); 169386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 170386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 171386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 172386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <> struct GraphTraits<const BasicBlock*> { 173386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef const BasicBlock NodeType; 174386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef succ_const_iterator ChildIteratorType; 175386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 176386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } 177386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 178386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_begin(NodeType *N) { 179386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_begin(N); 180386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 181386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_end(NodeType *N) { 182386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return succ_end(N); 183386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 184386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 185386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 186386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// Provide specializations of GraphTraits to be able to treat a function as a 187386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// graph of basic blocks... and to walk it in inverse order. Inverse order for 188386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// a function is considered to be when traversing the predecessor edges of a BB 189386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// instead of the successor edges. 190386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// 191386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <> struct GraphTraits<Inverse<BasicBlock*> > { 192386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef BasicBlock NodeType; 193386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef pred_iterator ChildIteratorType; 194386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; } 195386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_begin(NodeType *N) { 196386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return pred_begin(N); 197386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 198386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_end(NodeType *N) { 199386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return pred_end(N); 200386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 201386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 202386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 203386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <> struct GraphTraits<Inverse<const BasicBlock*> > { 204386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef const BasicBlock NodeType; 205386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef pred_const_iterator ChildIteratorType; 206386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static NodeType *getEntryNode(Inverse<const BasicBlock*> G) { 207386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return G.Graph; 208386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 209386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_begin(NodeType *N) { 210386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return pred_begin(N); 211386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 212386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static inline ChildIteratorType child_end(NodeType *N) { 213386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return pred_end(N); 214386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 215386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 216386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 217386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 218386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 219386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 220386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// GraphTraits specializations for function basic block graphs (CFGs) 221386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari//===--------------------------------------------------------------------===// 222386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 223386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// Provide specializations of GraphTraits to be able to treat a function as a 224386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// graph of basic blocks... these are the same as the basic block iterators, 225386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// except that the root node is implicitly the first node of the function. 226386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// 227386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> { 228386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); } 229386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 230386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 231386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef Function::iterator nodes_iterator; 232386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static nodes_iterator nodes_begin(Function *F) { return F->begin(); } 233386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static nodes_iterator nodes_end (Function *F) { return F->end(); } 234386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 235386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritemplate <> struct GraphTraits<const Function*> : 236386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari public GraphTraits<const BasicBlock*> { 237386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();} 238386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 239386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 240386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari typedef Function::const_iterator nodes_iterator; 241386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static nodes_iterator nodes_begin(const Function *F) { return F->begin(); } 242386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari static nodes_iterator nodes_end (const Function *F) { return F->end(); } 243386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari}; 244386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 245386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 246386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// Provide specializations of GraphTraits to be able to treat a function as a 247386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// graph of basic blocks... and to walk it in inverse order. Inverse order for 248386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari// a function is considered to be when traversing the predecessor edges of a BB 249// instead of the successor edges. 250// 251template <> struct GraphTraits<Inverse<Function*> > : 252 public GraphTraits<Inverse<BasicBlock*> > { 253 static NodeType *getEntryNode(Inverse<Function*> G) { 254 return &G.Graph->getEntryBlock(); 255 } 256}; 257template <> struct GraphTraits<Inverse<const Function*> > : 258 public GraphTraits<Inverse<const BasicBlock*> > { 259 static NodeType *getEntryNode(Inverse<const Function *> G) { 260 return &G.Graph->getEntryBlock(); 261 } 262}; 263 264} // End llvm namespace 265 266#endif 267