llvm::ModifiedPostOrder< ContextT > Class Template Reference

Construct a specially modified post-order traversal of cycles. More...

#include "llvm/ADT/GenericUniformityImpl.h"

Public Types
using	BlockT = typename ContextT::BlockT
using	FunctionT = typename ContextT::FunctionT
using	DominatorTreeT = typename ContextT::DominatorTreeT
using	CycleInfoT = GenericCycleInfo< ContextT >
using	CycleT = typename CycleInfoT::CycleT
using	const_iterator = typename std::vector< BlockT * >::const_iterator

Public Member Functions
	ModifiedPostOrder (const ContextT &C)
bool	empty () const
size_t	size () const
void	clear ()
void	compute (const CycleInfoT &CI)
	Generically compute the modified post order.
unsigned	count (BlockT *BB) const
const BlockT *	operator[] (size_t idx) const
void	appendBlock (const BlockT &BB, bool isReducibleCycleHeader=false)
unsigned	getIndex (const BlockT *BB) const
bool	isReducibleCycleHeader (const BlockT *BB) const

Detailed Description

template<typename ContextT>
class llvm::ModifiedPostOrder< ContextT >

Construct a specially modified post-order traversal of cycles.

The ModifiedPO is contructed using a virtually modified CFG as follows:

1. The successors of pre-entry nodes (predecessors of an cycle entry that are outside the cycle) are replaced by the successors of the successors of the header.
2. Successors of the cycle header are replaced by the exit blocks of the cycle.

Effectively, we produce a depth-first numbering with the following properties:

1. Nodes after a cycle are numbered earlier than the cycle header.
2. The header is numbered earlier than the nodes in the cycle.
3. The numbering of the nodes within the cycle forms an interval starting with the header.

Effectively, the virtual modification arranges the nodes in a cycle as a DAG with the header as the sole leaf, and successors of the header as the roots. A reverse traversal of this numbering has the following invariant on the unmodified original CFG:

Each node is visited after all its predecessors, except if that predecessor is the cycle header.

Definition at line 86 of file GenericUniformityImpl.h.

Member Typedef Documentation

BlockT

template<typename ContextT >

using llvm::ModifiedPostOrder< ContextT >::BlockT = typename ContextT::BlockT

Definition at line 88 of file GenericUniformityImpl.h.

const_iterator

template<typename ContextT >

using llvm::ModifiedPostOrder< ContextT >::const_iterator = typename std::vector<BlockT *>::const_iterator

Definition at line 94 of file GenericUniformityImpl.h.

CycleInfoT

template<typename ContextT >

using llvm::ModifiedPostOrder< ContextT >::CycleInfoT = GenericCycleInfo<ContextT>

Definition at line 92 of file GenericUniformityImpl.h.

CycleT

template<typename ContextT >

using llvm::ModifiedPostOrder< ContextT >::CycleT = typename CycleInfoT::CycleT

Definition at line 93 of file GenericUniformityImpl.h.

DominatorTreeT

template<typename ContextT >

using llvm::ModifiedPostOrder< ContextT >::DominatorTreeT = typename ContextT::DominatorTreeT

Definition at line 90 of file GenericUniformityImpl.h.

FunctionT

template<typename ContextT >

using llvm::ModifiedPostOrder< ContextT >::FunctionT = typename ContextT::FunctionT

Definition at line 89 of file GenericUniformityImpl.h.

Constructor & Destructor Documentation

ModifiedPostOrder()

template<typename ContextT >

llvm::ModifiedPostOrder< ContextT >::ModifiedPostOrder ( const ContextT &  C )

inline

Definition at line 96 of file GenericUniformityImpl.h.

Member Function Documentation

appendBlock()

template<typename ContextT >

void llvm::ModifiedPostOrder< ContextT >::appendBlock ( const BlockT &  BB, bool  isReducibleCycleHeader = false  )

inline

Definition at line 107 of file GenericUniformityImpl.h.

References llvm::dbgs(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::ModifiedPostOrder< ContextT >::isReducibleCycleHeader(), LLVM_DEBUG, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().

clear()

template<typename ContextT >

void llvm::ModifiedPostOrder< ContextT >::clear ( )

inline

Definition at line 101 of file GenericUniformityImpl.h.

References llvm::SmallVectorImpl< T >::clear().

compute()

template<typename ContextT >

void llvm::ModifiedPostOrder< ContextT >::compute

(

const CycleInfoT &

CI

)

Generically compute the modified post order.

Definition at line 1361 of file GenericUniformityImpl.h.

References F.

count()

template<typename ContextT >

unsigned llvm::ModifiedPostOrder< ContextT >::count ( BlockT *  BB ) const

inline

Definition at line 104 of file GenericUniformityImpl.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count().

empty()

template<typename ContextT >

bool llvm::ModifiedPostOrder< ContextT >::empty ( ) const

inline

Definition at line 98 of file GenericUniformityImpl.h.

References llvm::SmallVectorBase< Size_T >::empty().

getIndex()

template<typename ContextT >

unsigned llvm::ModifiedPostOrder< ContextT >::getIndex ( const BlockT *  BB ) const

inline

Definition at line 116 of file GenericUniformityImpl.h.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup().

isReducibleCycleHeader()

template<typename ContextT >

bool llvm::ModifiedPostOrder< ContextT >::isReducibleCycleHeader ( const BlockT *  BB ) const

inline

Definition at line 121 of file GenericUniformityImpl.h.

References llvm::SmallPtrSetImpl< PtrType >::contains().

Referenced by llvm::ModifiedPostOrder< ContextT >::appendBlock().

operator[]()

template<typename ContextT >

const BlockT * llvm::ModifiedPostOrder< ContextT >::operator[] ( size_t  idx ) const

inline

Definition at line 105 of file GenericUniformityImpl.h.

size()

template<typename ContextT >

size_t llvm::ModifiedPostOrder< ContextT >::size ( ) const

inline

Definition at line 99 of file GenericUniformityImpl.h.

References llvm::SmallVectorBase< Size_T >::size().

---

The documentation for this class was generated from the following file:

• include/llvm/ADT/GenericUniformityImpl.h