Construct a specially modified post-order traversal of cycles.
Declared in <llvm/ADT/GenericUniformityImpl.h>
template<typename ContextT>
class ModifiedPostOrder;
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.
| Name | Description |
|---|---|
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. |
| Name | Description |
|---|---|
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. |