LLVM 20.0.0git
Public Types | Public Member Functions | List of all members
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 BlockToperator[] (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

◆ 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

◆ 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

◆ isReducibleCycleHeader()

template<typename ContextT >
bool llvm::ModifiedPostOrder< ContextT >::isReducibleCycleHeader ( const BlockT BB) const
inline

◆ 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: