Struct cranelift_codegen::dominator_tree::DominatorTreePreorder

pub struct DominatorTreePreorder { /* private fields */ }

Optional pre-order information that can be computed for a dominator tree.

This data structure is computed from a DominatorTree and provides:

• A forward traversable dominator tree through the children() iterator.
• An ordering of EBBs according to a dominator tree pre-order.
• Constant time dominance checks at the EBB granularity.

The information in this auxillary data structure is not easy to update when the control flow graph changes, which is why it is kept separate.

Implementations

impl DominatorTreePreorder

Creating and computing the dominator tree pre-order.

pub fn new() -> Self

Create a new blank DominatorTreePreorder.

pub fn compute(&mut self, domtree: &DominatorTree, layout: &Layout)

Recompute this data structure to match domtree.

impl DominatorTreePreorder

Query interface for the dominator tree pre-order.

pub fn children(&self, ebb: Ebb) -> ChildIter<'_>

Get an iterator over the direct children of ebb in the dominator tree.

These are the EBB’s whose immediate dominator is an instruction in ebb, ordered according to the CFG reverse post-order.

pub fn dominates(&self, a: Ebb, b: Ebb) -> bool

Fast, constant time dominance check with EBB granularity.

This computes the same result as domtree.dominates(a, b), but in guaranteed fast constant time. This is less general than the DominatorTree method because it only works with EBB program points.

An EBB is considered to dominate itself.

pub fn pre_cmp_ebb(&self, a: Ebb, b: Ebb) -> Ordering

Compare two EBBs according to the dominator pre-order.

pub fn pre_cmp<A, B>(&self, a: A, b: B, layout: &Layout) -> Orderingwhere
    A: Into<ExpandedProgramPoint>,
    B: Into<ExpandedProgramPoint>,

Compare two program points according to the dominator tree pre-order.

This ordering of program points have the property that given a program point, pp, all the program points dominated by pp follow immediately and contiguously after pp in the order.

pub fn pre_cmp_def(&self, a: Value, b: Value, func: &Function) -> Ordering

Compare two value defs according to the dominator tree pre-order.

Two values defined at the same program point are compared according to their parameter or result order.

This is a total ordering of the values in the function.