Expand description
Finding the dominators in a control-flow graph.
Algorithm based on Loukas Georgiadis, “Linear-Time Algorithms for Dominators and Related Problems”, https://www.cs.princeton.edu/techreports/2005/737.pdf
Additionally useful is the original Lengauer-Tarjan paper on this subject, “A Fast Algorithm for Finding Dominators in a Flowgraph” Thomas Lengauer and Robert Endre Tarjan. https://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf
Structs§
- Dominators
- Inner 🔒
- Tracks the list of dominators for each node.
- PreOrder
Frame 🔒 - Preorder
Index 🔒 - Time 🔒
- Describes the number of vertices discovered at the time when processing of a particular vertex started and when it finished. Both values are zero for unreachable vertices.
Enums§
- Kind 🔒
Functions§
- compress 🔒
- compute_
access_ 🔒time - dominators
- dominators_
impl 🔒 - eval 🔒
- Evaluate the link-eval virtual forest, providing the currently minimum semi
value for the passed
node(which may be itself). - is_
processed 🔒 - is_
small_ 🔒path_ graph