From 7170838f84c0267a1c57debc97d86ea38f4f10d5 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 7 Jun 2001 21:18:08 +0000 Subject: [PATCH] New file git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@13 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CFG.h | 282 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 282 insertions(+) create mode 100644 include/llvm/CFG.h diff --git a/include/llvm/CFG.h b/include/llvm/CFG.h new file mode 100644 index 00000000000..389042c816b --- /dev/null +++ b/include/llvm/CFG.h @@ -0,0 +1,282 @@ +//===-- llvm/CFG.h - CFG definitions and useful classes ----------*- C++ -*--=// +// +// This file contains the class definitions useful for operating on the control +// flow graph. +// +// Currently it contains functionality for these three applications: +// +// 1. Iterate over the predecessors of a basic block: +// pred_iterator, pred_const_iterator, pred_begin, pred_end +// 2. Iterate over the successors of a basic block: +// succ_iterator, succ_const_iterator, succ_begin, succ_end +//an iterator to iterate over the basic +// blocks of a method in depth first order. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CFG_H +#define LLVM_CFG_H + +#include +#include +#include "llvm/BasicBlock.h" +#include "llvm/InstrTypes.h" + +//===----------------------------------------------------------------------===// +// Interface +//===----------------------------------------------------------------------===// + +//===--------------------------------------------------------------------===// +// Predecessor iterator code +//===--------------------------------------------------------------------===// +// +// This is used to figure out what basic blocks we could be coming from. +// + +// Forward declare iterator class template... +template class PredIterator; + +typedef PredIterator pred_iterator; +typedef PredIterator pred_const_iterator; + +inline pred_iterator pred_begin( BasicBlock *BB); +inline pred_const_iterator pred_begin(const BasicBlock *BB); +inline pred_iterator pred_end ( BasicBlock *BB); +inline pred_const_iterator pred_end (const BasicBlock *BB); + + +//===--------------------------------------------------------------------===// +// Successor iterator code +//===--------------------------------------------------------------------===// +// +// This is used to figure out what basic blocks we could be going to... +// + +// Forward declare iterator class template... +template class SuccIterator; + +typedef SuccIterator succ_iterator; +typedef SuccIterator succ_const_iterator; + +inline succ_iterator succ_begin( BasicBlock *BB); +inline succ_const_iterator succ_begin(const BasicBlock *BB); +inline succ_iterator succ_end ( BasicBlock *BB); +inline succ_const_iterator succ_end (const BasicBlock *BB); + + +//===--------------------------------------------------------------------===// +// Depth First CFG iterator code +//===--------------------------------------------------------------------===// +// +// This is used to figure out what basic blocks we could be going to... +// + +// Forward declare iterator class template... +template class DFIterator; + +typedef DFIterator df_iterator; +typedef DFIterator df_const_iterator; + +inline df_iterator df_begin( BasicBlock *BB); +inline df_const_iterator df_begin(const BasicBlock *BB); +inline df_iterator df_end ( BasicBlock *BB); +inline df_const_iterator df_end (const BasicBlock *BB); + + + +//===----------------------------------------------------------------------===// +// Implementation +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// Basic Block Predecessor Iterator +// + +template // Predecessor Iterator +class PredIterator { + const _Ptr ThisBB; + _USE_iterator It; +public: + typedef PredIterator<_Ptr,_USE_iterator> _Self; + + typedef bidirectional_iterator_tag iterator_category; + typedef _Ptr pointer; + + inline void advancePastConstPool() { + // Loop to ignore constant pool references + while (It != ThisBB->use_end() && + ((*It)->getValueType() != Value::InstructionVal)) + ++It; + } + + inline PredIterator(_Ptr BB) : ThisBB(BB), It(BB->use_begin()) { + advancePastConstPool(); + } + inline PredIterator(_Ptr BB, bool) : ThisBB(BB), It(BB->use_end()) {} + + inline bool operator==(const _Self& x) const { return It == x.It; } + inline bool operator!=(const _Self& x) const { return !operator==(x); } + + inline pointer operator*() const { + assert ((*It)->getValueType() == Value::InstructionVal); + return ((Instruction *)(*It))->getParent(); + } + inline pointer *operator->() const { return &(operator*()); } + + inline _Self& operator++() { // Preincrement + ++It; advancePastConstPool(); + return *this; + } + + inline _Self operator++(int) { // Postincrement + _Self tmp = *this; ++*this; return tmp; + } + + inline _Self& operator--() { --It; return *this; } // Predecrement + inline _Self operator--(int) { // Postdecrement + _Self tmp = *this; --*this; return tmp; + } +}; + +inline pred_iterator pred_begin( BasicBlock *BB) { + return pred_iterator(BB); +} +inline pred_const_iterator pred_begin(const BasicBlock *BB) { + return pred_const_iterator(BB); +} +inline pred_iterator pred_end( BasicBlock *BB) { + return pred_iterator(BB,true); +} +inline pred_const_iterator pred_end(const BasicBlock *BB) { + return pred_const_iterator(BB,true); +} + + +//===----------------------------------------------------------------------===// +// Basic Block Successor Iterator +// + +template // Successor Iterator +class SuccIterator { + const _Term Term; + unsigned idx; +public: + typedef SuccIterator<_Term, _BB> _Self; + typedef forward_iterator_tag iterator_category; + typedef _BB pointer; + + inline SuccIterator(_Term T) : Term(T), idx(0) {} // begin iterator + inline SuccIterator(_Term T, bool) + : Term(T), idx(Term->getNumSuccessors()) {} // end iterator + + inline bool operator==(const _Self& x) const { return idx == x.idx; } + inline bool operator!=(const _Self& x) const { return !operator==(x); } + + inline pointer operator*() const { return Term->getSuccessor(idx); } + inline pointer *operator->() const { return &(operator*()); } + + inline _Self& operator++() { ++idx; return *this; } // Preincrement + inline _Self operator++(int) { // Postincrement + _Self tmp = *this; ++*this; return tmp; + } + + inline _Self& operator--() { --idx; return *this; } // Predecrement + inline _Self operator--(int) { // Postdecrement + _Self tmp = *this; --*this; return tmp; + } +}; + +inline succ_iterator succ_begin( BasicBlock *BB) { + return succ_iterator(BB->getTerminator()); +} +inline succ_const_iterator succ_begin(const BasicBlock *BB) { + return succ_const_iterator(BB->getTerminator()); +} +inline succ_iterator succ_end( BasicBlock *BB) { + return succ_iterator(BB->getTerminator(),true); +} +inline succ_const_iterator succ_end(const BasicBlock *BB) { + return succ_const_iterator(BB->getTerminator(),true); +} + + +//===----------------------------------------------------------------------===// +// Depth First Iterator +// + +template +class DFIterator { // BasicBlock Depth First Iterator + set Visited; // All of the blocks visited so far... + // VisitStack - Used to maintain the ordering. Top = current block + // First element is basic block pointer, second is the 'next child' to visit + stack > VisitStack; +public: + typedef DFIterator _Self; + + typedef forward_iterator_tag iterator_category; + typedef BBType *pointer; + + inline DFIterator(BBType *BB) { + Visited.insert(BB); + VisitStack.push(make_pair(BB, succ_begin(BB))); + } + inline DFIterator(BBType *BB, bool) { /* End is when stack is empty */ } + + inline bool operator==(const _Self& x) const { + return VisitStack == x.VisitStack; + } + inline bool operator!=(const _Self& x) const { return !operator==(x); } + + inline pointer operator*() const { + return VisitStack.top().first; + } + + // This is a nonstandard operator-> that dereferences the pointer an extra + // time... so that you can actually call methods ON the BasicBlock, because + // the contained type is a pointer. This allows BBIt->getTerminator() f.e. + // + inline BBType *operator->() const { return operator*(); } + + inline _Self& operator++() { // Preincrement + do { + pair &Top = VisitStack.top(); + BBType *BB = Top.first; + SuccItTy &It = Top.second; + + do { + BBType *Next = *It++; + if (!Visited.count(Next)) { // Has our next sibling been visited? + // No, do it now. + VisitStack.push(make_pair(Next, succ_begin(BB))); + return *this; + } + } while (It != succ_end(BB)); + + // Oops, ran out of successors... go up a level on the stack. + VisitStack.pop(); + } while (!VisitStack.empty()); + return *this; + } + + inline _Self operator++(int) { // Postincrement + _Self tmp = *this; ++*this; return tmp; + } +}; + +inline df_iterator df_begin(BasicBlock *BB) { + return df_iterator(BB); +} +inline df_const_iterator df_begin(const BasicBlock *BB) { + return df_const_iterator(BB); +} +inline df_iterator df_end(BasicBlock *BB) { + return df_iterator(BB, true); +} +inline df_const_iterator df_end(const BasicBlock *BB) { + return df_const_iterator(BB, true); +} + +#endif -- 2.34.1