Struct DominatorTree

pub struct DominatorTree { /* private fields */ }

The dominator tree for a single function, computed using Semi-NCA algorithm.

Implementations

impl DominatorTree

Methods for querying the dominator tree.

pub fn is_reachable(&self, block: Block) -> bool

Is block reachable from the entry block?

pub fn cfg_postorder(&self) -> &[Block]

Get the CFG post-order of blocks that was used to compute the dominator tree.

Note that this post-order is not updated automatically when the CFG is modified. It is computed from scratch and cached by compute().

pub fn cfg_rpo(&self) -> impl Iterator<Item = &Block>

Get an iterator over CFG reverse post-order of blocks used to compute the dominator tree.

Note that the post-order is not updated automatically when the CFG is modified. It is computed from scratch and cached by compute().

pub fn idom(&self, block: Block) -> Option<Block>

Returns the immediate dominator of block.

block_a is said to dominate block_b if all control flow paths from the function entry to block_b must go through block_a.

The immediate dominator is the dominator that is closest to block. All other dominators also dominate the immediate dominator.

This returns None if block is not reachable from the entry block, or if it is the entry block which has no dominators.

pub fn dominates<A, B>(&self, a: A, b: B, layout: &Layout) -> bool

where A: Into<ProgramPoint>, B: Into<ProgramPoint>,

Returns true if a dominates b.

This means that every control-flow path from the function entry to b must go through a.

Dominance is ill defined for unreachable blocks. This function can always determine dominance for instructions in the same block, but otherwise returns false if either block is unreachable.

An instruction is considered to dominate itself. A block is also considered to dominate itself.

impl DominatorTree

pub fn new() -> Self

Allocate a new blank dominator tree. Use compute to compute the dominator tree for a function.

pub fn with_function(func: &Function, cfg: &ControlFlowGraph) -> Self

Allocate and compute a dominator tree.

pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph)

Reset and compute a CFG post-order and dominator tree, using Semi-NCA algorithm, described in the paper:

Linear-Time Algorithms for Dominators and Related Problems. Loukas Georgiadis, Princeton University, November 2005.

The same algorithm is used by Julia, SpiderMonkey and LLVM, the implementation is heavily inspired by them.

pub fn clear(&mut self)

Clear the data structures used to represent the dominator tree. This will leave the tree in a state where is_valid() returns false.

pub fn is_valid(&self) -> bool

Check if the dominator tree is in a valid state.

Note that this doesn’t perform any kind of validity checks. It simply checks if the compute() method has been called since the last clear(). It does not check that the dominator tree is consistent with the CFG.