Module rustc_data_structures::graph::dominators

source ·
Expand description

Finding the dominators in a control-flow graph.

Algorithm based on Loukas Georgiadis, “Linear-Time Algorithms for Dominators and Related Problems”,

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.


  • Inner 🔒
    Tracks the list of dominators for each node.
  • 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.