LLVM: llvm::ModifiedPostOrder< ContextT > Class Template Reference (original) (raw)

template
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.