llvm::ModifiedPostOrder

Construct a specially modified post-order traversal of cycles.

Synopsis

Declared in <llvm/ADT/GenericUniformityImpl.h>

template<typename ContextT>
class ModifiedPostOrder;

Description

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.

Type Aliases

NameDescription
BlockT Basic-block type from the SSA context.
CycleInfoT Cycle-info type instantiated for this context.
DominatorTreeT Dominator-tree type from the SSA context.
FunctionT Function type from the SSA context.
const_iterator Const iterator over blocks in the modified post-order.

Member Functions

NameDescription
ModifiedPostOrder [constructor]Construct an empty order bound to SSA context C.
appendBlock Append BB to the order, optionally marking it as a reducible cycle header.
clear Remove all blocks from the order.
compute Generically compute the modified post order.
count Return non-zero if BB is present in the order.
empty True if no blocks have been appended yet.
getIndex Return the modified-post-order index of BB.
isReducibleCycleHeader True if BB was recorded as a reducible cycle header.
operator[] Return the block at modified-post-order index Idx.
size Number of blocks currently in the order.