Struct cranelift_codegen::dominator_tree::DominatorTree
source · pub struct DominatorTree { /* private fields */ }
Expand description
The dominator tree for a single function.
Implementations§
source§impl DominatorTree
impl DominatorTree
Methods for querying the dominator tree.
sourcepub fn is_reachable(&self, ebb: Ebb) -> bool
pub fn is_reachable(&self, ebb: Ebb) -> bool
Is ebb
reachable from the entry block?
sourcepub fn cfg_postorder(&self) -> &[Ebb]
pub fn cfg_postorder(&self) -> &[Ebb]
Get the CFG post-order of EBBs 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()
.
sourcepub fn idom(&self, ebb: Ebb) -> Option<Inst>
pub fn idom(&self, ebb: Ebb) -> Option<Inst>
Returns the immediate dominator of ebb
.
The immediate dominator of an extended basic block is a basic block which we represent by the branch or jump instruction at the end of the basic block. This does not have to be the terminator of its EBB.
A branch or jump is said to dominate ebb
if all control flow paths from the function
entry to ebb
must go through the branch.
The immediate dominator is the dominator that is closest to ebb
. All other dominators
also dominate the immediate dominator.
This returns None
if ebb
is not reachable from the entry EBB, or if it is the entry EBB
which has no dominators.
sourcepub fn rpo_cmp<A, B>(&self, a: A, b: B, layout: &Layout) -> Orderingwhere
A: Into<ExpandedProgramPoint>,
B: Into<ExpandedProgramPoint>,
pub fn rpo_cmp<A, B>(&self, a: A, b: B, layout: &Layout) -> Orderingwhere
A: Into<ExpandedProgramPoint>,
B: Into<ExpandedProgramPoint>,
Compare two program points relative to a reverse post-order traversal of the control-flow graph.
Return Ordering::Less
if a
comes before b
in the RPO.
If a
and b
belong to the same EBB, compare their relative position in the EBB.
sourcepub fn dominates<A, B>(&self, a: A, b: B, layout: &Layout) -> boolwhere
A: Into<ExpandedProgramPoint>,
B: Into<ExpandedProgramPoint>,
pub fn dominates<A, B>(&self, a: A, b: B, layout: &Layout) -> boolwhere
A: Into<ExpandedProgramPoint>,
B: Into<ExpandedProgramPoint>,
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 EBB, but otherwise returns false
if either block
is unreachable.
An instruction is considered to dominate itself.
sourcepub fn last_dominator<B>(&self, a: Ebb, b: B, layout: &Layout) -> Option<Inst>where
B: Into<ExpandedProgramPoint>,
pub fn last_dominator<B>(&self, a: Ebb, b: B, layout: &Layout) -> Option<Inst>where
B: Into<ExpandedProgramPoint>,
Find the last instruction in a
that dominates b
.
If no instructions in a
dominate b
, return None
.
sourcepub fn common_dominator(
&self,
a: BasicBlock,
b: BasicBlock,
layout: &Layout
) -> BasicBlock
pub fn common_dominator(
&self,
a: BasicBlock,
b: BasicBlock,
layout: &Layout
) -> BasicBlock
Compute the common dominator of two basic blocks.
Both basic blocks are assumed to be reachable.
source§impl DominatorTree
impl DominatorTree
sourcepub fn new() -> Self
pub fn new() -> Self
Allocate a new blank dominator tree. Use compute
to compute the dominator tree for a
function.
sourcepub fn with_function(func: &Function, cfg: &ControlFlowGraph) -> Self
pub fn with_function(func: &Function, cfg: &ControlFlowGraph) -> Self
Allocate and compute a dominator tree.
sourcepub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph)
pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph)
Reset and compute a CFG post-order and dominator tree.
source§impl DominatorTree
impl DominatorTree
sourcepub fn recompute_split_ebb(
&mut self,
old_ebb: Ebb,
new_ebb: Ebb,
split_jump_inst: Inst
)
pub fn recompute_split_ebb(
&mut self,
old_ebb: Ebb,
new_ebb: Ebb,
split_jump_inst: Inst
)
When splitting an Ebb
using Layout::split_ebb
, you can use this method to update
the dominator tree locally rather than recomputing it.
old_ebb
is the Ebb
before splitting, and new_ebb
is the Ebb
which now contains
the second half of old_ebb
. split_jump_inst
is the terminator jump instruction of
old_ebb
that points to new_ebb
.