use crate::entity::SecondaryMap;
use crate::flowgraph::{BasicBlock, ControlFlowGraph};
use crate::ir::instructions::BranchInfo;
use crate::ir::{Ebb, ExpandedProgramPoint, Function, Inst, Layout, ProgramOrder, Value};
use crate::packed_option::PackedOption;
use crate::timing;
use alloc::vec::Vec;
use core::cmp;
use core::cmp::Ordering;
use core::mem;
const STRIDE: u32 = 4;
const DONE: u32 = 1;
const SEEN: u32 = 2;
#[derive(Clone, Default)]
struct DomNode {
rpo_number: u32,
idom: PackedOption<Inst>,
}
pub struct DominatorTree {
nodes: SecondaryMap<Ebb, DomNode>,
postorder: Vec<Ebb>,
stack: Vec<Ebb>,
valid: bool,
}
impl DominatorTree {
pub fn is_reachable(&self, ebb: Ebb) -> bool {
self.nodes[ebb].rpo_number != 0
}
pub fn cfg_postorder(&self) -> &[Ebb] {
debug_assert!(self.is_valid());
&self.postorder
}
pub fn idom(&self, ebb: Ebb) -> Option<Inst> {
self.nodes[ebb].idom.into()
}
fn rpo_cmp_ebb(&self, a: Ebb, b: Ebb) -> Ordering {
self.nodes[a].rpo_number.cmp(&self.nodes[b].rpo_number)
}
pub fn rpo_cmp<A, B>(&self, a: A, b: B, layout: &Layout) -> Ordering
where
A: Into<ExpandedProgramPoint>,
B: Into<ExpandedProgramPoint>,
{
let a = a.into();
let b = b.into();
self.rpo_cmp_ebb(layout.pp_ebb(a), layout.pp_ebb(b))
.then(layout.cmp(a, b))
}
pub fn dominates<A, B>(&self, a: A, b: B, layout: &Layout) -> bool
where
A: Into<ExpandedProgramPoint>,
B: Into<ExpandedProgramPoint>,
{
let a = a.into();
let b = b.into();
match a {
ExpandedProgramPoint::Ebb(ebb_a) => {
a == b || self.last_dominator(ebb_a, b, layout).is_some()
}
ExpandedProgramPoint::Inst(inst_a) => {
let ebb_a = layout.inst_ebb(inst_a).expect("Instruction not in layout.");
match self.last_dominator(ebb_a, b, layout) {
Some(last) => layout.cmp(inst_a, last) != Ordering::Greater,
None => false,
}
}
}
}
pub fn last_dominator<B>(&self, a: Ebb, b: B, layout: &Layout) -> Option<Inst>
where
B: Into<ExpandedProgramPoint>,
{
let (mut ebb_b, mut inst_b) = match b.into() {
ExpandedProgramPoint::Ebb(ebb) => (ebb, None),
ExpandedProgramPoint::Inst(inst) => (
layout.inst_ebb(inst).expect("Instruction not in layout."),
Some(inst),
),
};
let rpo_a = self.nodes[a].rpo_number;
while rpo_a < self.nodes[ebb_b].rpo_number {
let idom = match self.idom(ebb_b) {
Some(idom) => idom,
None => return None,
};
ebb_b = layout.inst_ebb(idom).expect("Dominator got removed.");
inst_b = Some(idom);
}
if a == ebb_b {
inst_b
} else {
None
}
}
pub fn common_dominator(
&self,
mut a: BasicBlock,
mut b: BasicBlock,
layout: &Layout,
) -> BasicBlock {
loop {
match self.rpo_cmp_ebb(a.ebb, b.ebb) {
Ordering::Less => {
let idom = self.nodes[b.ebb].idom.expect("Unreachable basic block?");
b = BasicBlock::new(
layout.inst_ebb(idom).expect("Dangling idom instruction"),
idom,
);
}
Ordering::Greater => {
let idom = self.nodes[a.ebb].idom.expect("Unreachable basic block?");
a = BasicBlock::new(
layout.inst_ebb(idom).expect("Dangling idom instruction"),
idom,
);
}
Ordering::Equal => break,
}
}
debug_assert_eq!(
a.ebb, b.ebb,
"Unreachable block passed to common_dominator?"
);
if layout.cmp(a.inst, b.inst) == Ordering::Less {
a
} else {
b
}
}
}
impl DominatorTree {
pub fn new() -> Self {
Self {
nodes: SecondaryMap::new(),
postorder: Vec::new(),
stack: Vec::new(),
valid: false,
}
}
pub fn with_function(func: &Function, cfg: &ControlFlowGraph) -> Self {
let ebb_capacity = func.layout.ebb_capacity();
let mut domtree = Self {
nodes: SecondaryMap::with_capacity(ebb_capacity),
postorder: Vec::with_capacity(ebb_capacity),
stack: Vec::new(),
valid: false,
};
domtree.compute(func, cfg);
domtree
}
pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph) {
let _tt = timing::domtree();
debug_assert!(cfg.is_valid());
self.compute_postorder(func);
self.compute_domtree(func, cfg);
self.valid = true;
}
pub fn clear(&mut self) {
self.nodes.clear();
self.postorder.clear();
debug_assert!(self.stack.is_empty());
self.valid = false;
}
pub fn is_valid(&self) -> bool {
self.valid
}
fn compute_postorder(&mut self, func: &Function) {
self.clear();
self.nodes.resize(func.dfg.num_ebbs());
match func.layout.entry_block() {
Some(ebb) => {
self.stack.push(ebb);
self.nodes[ebb].rpo_number = SEEN;
}
None => return,
}
while let Some(ebb) = self.stack.pop() {
match self.nodes[ebb].rpo_number {
SEEN => {
self.nodes[ebb].rpo_number = DONE;
self.stack.push(ebb);
self.push_successors(func, ebb);
}
DONE => {
self.postorder.push(ebb);
}
_ => unreachable!(),
}
}
}
fn push_successors(&mut self, func: &Function, ebb: Ebb) {
for inst in func.layout.ebb_insts(ebb) {
match func.dfg.analyze_branch(inst) {
BranchInfo::SingleDest(succ, _) => self.push_if_unseen(succ),
BranchInfo::Table(jt, dest) => {
for succ in func.jump_tables[jt].iter() {
self.push_if_unseen(*succ);
}
if let Some(dest) = dest {
self.push_if_unseen(dest);
}
}
BranchInfo::NotABranch => {}
}
}
}
fn push_if_unseen(&mut self, ebb: Ebb) {
if self.nodes[ebb].rpo_number == 0 {
self.nodes[ebb].rpo_number = SEEN;
self.stack.push(ebb);
}
}
fn compute_domtree(&mut self, func: &Function, cfg: &ControlFlowGraph) {
let (entry_block, postorder) = match self.postorder.as_slice().split_last() {
Some((&eb, rest)) => (eb, rest),
None => return,
};
debug_assert_eq!(Some(entry_block), func.layout.entry_block());
self.nodes[entry_block].rpo_number = 2 * STRIDE;
for (rpo_idx, &ebb) in postorder.iter().rev().enumerate() {
self.nodes[ebb] = DomNode {
idom: self.compute_idom(ebb, cfg, &func.layout).into(),
rpo_number: (rpo_idx as u32 + 3) * STRIDE,
}
}
let mut changed = true;
while changed {
changed = false;
for &ebb in postorder.iter().rev() {
let idom = self.compute_idom(ebb, cfg, &func.layout).into();
if self.nodes[ebb].idom != idom {
self.nodes[ebb].idom = idom;
changed = true;
}
}
}
}
fn compute_idom(&self, ebb: Ebb, cfg: &ControlFlowGraph, layout: &Layout) -> Inst {
let mut reachable_preds = cfg
.pred_iter(ebb)
.filter(|&BasicBlock { ebb: pred, .. }| self.nodes[pred].rpo_number > 1);
let mut idom = reachable_preds
.next()
.expect("EBB node must have one reachable predecessor");
for pred in reachable_preds {
idom = self.common_dominator(idom, pred, layout);
}
idom.inst
}
}
impl DominatorTree {
pub fn recompute_split_ebb(&mut self, old_ebb: Ebb, new_ebb: Ebb, split_jump_inst: Inst) {
if !self.is_reachable(old_ebb) {
self.nodes[new_ebb] = Default::default();
return;
}
let old_ebb_postorder_index = self
.postorder
.as_slice()
.binary_search_by(|probe| self.rpo_cmp_ebb(old_ebb, *probe))
.expect("the old ebb is not declared to the dominator tree");
let new_ebb_rpo = self.insert_after_rpo(old_ebb, old_ebb_postorder_index, new_ebb);
self.nodes[new_ebb] = DomNode {
rpo_number: new_ebb_rpo,
idom: Some(split_jump_inst).into(),
};
}
fn insert_after_rpo(&mut self, ebb: Ebb, ebb_postorder_index: usize, new_ebb: Ebb) -> u32 {
let ebb_rpo_number = self.nodes[ebb].rpo_number;
let inserted_rpo_number = ebb_rpo_number + 1;
for (¤t_ebb, current_rpo) in self.postorder[0..ebb_postorder_index]
.iter()
.rev()
.zip(inserted_rpo_number + 1..)
{
if self.nodes[current_ebb].rpo_number < current_rpo {
self.nodes[current_ebb].rpo_number = current_rpo;
} else {
break;
}
}
self.postorder.insert(ebb_postorder_index, new_ebb);
inserted_rpo_number
}
}
pub struct DominatorTreePreorder {
nodes: SecondaryMap<Ebb, ExtraNode>,
stack: Vec<Ebb>,
}
#[derive(Default, Clone)]
struct ExtraNode {
child: PackedOption<Ebb>,
sibling: PackedOption<Ebb>,
pre_number: u32,
pre_max: u32,
}
impl DominatorTreePreorder {
pub fn new() -> Self {
Self {
nodes: SecondaryMap::new(),
stack: Vec::new(),
}
}
pub fn compute(&mut self, domtree: &DominatorTree, layout: &Layout) {
self.nodes.clear();
debug_assert_eq!(self.stack.len(), 0);
for &ebb in domtree.cfg_postorder() {
if let Some(idom_inst) = domtree.idom(ebb) {
let idom = layout.pp_ebb(idom_inst);
let sib = mem::replace(&mut self.nodes[idom].child, ebb.into());
self.nodes[ebb].sibling = sib;
} else {
self.stack.push(ebb);
}
}
debug_assert!(self.stack.len() <= 1);
let mut n = 0;
while let Some(ebb) = self.stack.pop() {
n += 1;
let node = &mut self.nodes[ebb];
node.pre_number = n;
node.pre_max = n;
if let Some(n) = node.sibling.expand() {
self.stack.push(n);
}
if let Some(n) = node.child.expand() {
self.stack.push(n);
}
}
for &ebb in domtree.cfg_postorder() {
if let Some(idom_inst) = domtree.idom(ebb) {
let idom = layout.pp_ebb(idom_inst);
let pre_max = cmp::max(self.nodes[ebb].pre_max, self.nodes[idom].pre_max);
self.nodes[idom].pre_max = pre_max;
}
}
}
}
pub struct ChildIter<'a> {
dtpo: &'a DominatorTreePreorder,
next: PackedOption<Ebb>,
}
impl<'a> Iterator for ChildIter<'a> {
type Item = Ebb;
fn next(&mut self) -> Option<Ebb> {
let n = self.next.expand();
if let Some(ebb) = n {
self.next = self.dtpo.nodes[ebb].sibling;
}
n
}
}
impl DominatorTreePreorder {
pub fn children(&self, ebb: Ebb) -> ChildIter {
ChildIter {
dtpo: self,
next: self.nodes[ebb].child,
}
}
pub fn dominates(&self, a: Ebb, b: Ebb) -> bool {
let na = &self.nodes[a];
let nb = &self.nodes[b];
na.pre_number <= nb.pre_number && na.pre_max >= nb.pre_max
}
pub fn pre_cmp_ebb(&self, a: Ebb, b: Ebb) -> Ordering {
self.nodes[a].pre_number.cmp(&self.nodes[b].pre_number)
}
pub fn pre_cmp<A, B>(&self, a: A, b: B, layout: &Layout) -> Ordering
where
A: Into<ExpandedProgramPoint>,
B: Into<ExpandedProgramPoint>,
{
let a = a.into();
let b = b.into();
self.pre_cmp_ebb(layout.pp_ebb(a), layout.pp_ebb(b))
.then(layout.cmp(a, b))
}
pub fn pre_cmp_def(&self, a: Value, b: Value, func: &Function) -> Ordering {
let da = func.dfg.value_def(a);
let db = func.dfg.value_def(b);
self.pre_cmp(da, db, &func.layout)
.then_with(|| da.num().cmp(&db.num()))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::cursor::{Cursor, FuncCursor};
use crate::flowgraph::ControlFlowGraph;
use crate::ir::types::*;
use crate::ir::{Function, InstBuilder, TrapCode};
use crate::settings;
use crate::verifier::{verify_context, VerifierErrors};
#[test]
fn empty() {
let func = Function::new();
let cfg = ControlFlowGraph::with_function(&func);
debug_assert!(cfg.is_valid());
let dtree = DominatorTree::with_function(&func, &cfg);
assert_eq!(0, dtree.nodes.keys().count());
assert_eq!(dtree.cfg_postorder(), &[]);
let mut dtpo = DominatorTreePreorder::new();
dtpo.compute(&dtree, &func.layout);
}
#[test]
fn unreachable_node() {
let mut func = Function::new();
let ebb0 = func.dfg.make_ebb();
let v0 = func.dfg.append_ebb_param(ebb0, I32);
let ebb1 = func.dfg.make_ebb();
let ebb2 = func.dfg.make_ebb();
let mut cur = FuncCursor::new(&mut func);
cur.insert_ebb(ebb0);
cur.ins().brnz(v0, ebb2, &[]);
cur.ins().trap(TrapCode::User(0));
cur.insert_ebb(ebb1);
let v1 = cur.ins().iconst(I32, 1);
let v2 = cur.ins().iadd(v0, v1);
cur.ins().jump(ebb0, &[v2]);
cur.insert_ebb(ebb2);
cur.ins().return_(&[v0]);
let cfg = ControlFlowGraph::with_function(cur.func);
let dt = DominatorTree::with_function(cur.func, &cfg);
assert_eq!(dt.cfg_postorder(), &[ebb2, ebb0]);
let v2_def = cur.func.dfg.value_def(v2).unwrap_inst();
assert!(!dt.dominates(v2_def, ebb0, &cur.func.layout));
assert!(!dt.dominates(ebb0, v2_def, &cur.func.layout));
let mut dtpo = DominatorTreePreorder::new();
dtpo.compute(&dt, &cur.func.layout);
assert!(dtpo.dominates(ebb0, ebb0));
assert!(!dtpo.dominates(ebb0, ebb1));
assert!(dtpo.dominates(ebb0, ebb2));
assert!(!dtpo.dominates(ebb1, ebb0));
assert!(dtpo.dominates(ebb1, ebb1));
assert!(!dtpo.dominates(ebb1, ebb2));
assert!(!dtpo.dominates(ebb2, ebb0));
assert!(!dtpo.dominates(ebb2, ebb1));
assert!(dtpo.dominates(ebb2, ebb2));
}
#[test]
fn non_zero_entry_block() {
let mut func = Function::new();
let ebb0 = func.dfg.make_ebb();
let ebb1 = func.dfg.make_ebb();
let ebb2 = func.dfg.make_ebb();
let ebb3 = func.dfg.make_ebb();
let cond = func.dfg.append_ebb_param(ebb3, I32);
let mut cur = FuncCursor::new(&mut func);
cur.insert_ebb(ebb3);
let jmp_ebb3_ebb1 = cur.ins().jump(ebb1, &[]);
cur.insert_ebb(ebb1);
let br_ebb1_ebb0 = cur.ins().brnz(cond, ebb0, &[]);
let jmp_ebb1_ebb2 = cur.ins().jump(ebb2, &[]);
cur.insert_ebb(ebb2);
cur.ins().jump(ebb0, &[]);
cur.insert_ebb(ebb0);
let cfg = ControlFlowGraph::with_function(cur.func);
let dt = DominatorTree::with_function(cur.func, &cfg);
assert_eq!(dt.cfg_postorder(), &[ebb2, ebb0, ebb1, ebb3]);
assert_eq!(cur.func.layout.entry_block().unwrap(), ebb3);
assert_eq!(dt.idom(ebb3), None);
assert_eq!(dt.idom(ebb1).unwrap(), jmp_ebb3_ebb1);
assert_eq!(dt.idom(ebb2).unwrap(), jmp_ebb1_ebb2);
assert_eq!(dt.idom(ebb0).unwrap(), br_ebb1_ebb0);
assert!(dt.dominates(br_ebb1_ebb0, br_ebb1_ebb0, &cur.func.layout));
assert!(!dt.dominates(br_ebb1_ebb0, jmp_ebb3_ebb1, &cur.func.layout));
assert!(dt.dominates(jmp_ebb3_ebb1, br_ebb1_ebb0, &cur.func.layout));
assert_eq!(dt.rpo_cmp(ebb3, ebb3, &cur.func.layout), Ordering::Equal);
assert_eq!(dt.rpo_cmp(ebb3, ebb1, &cur.func.layout), Ordering::Less);
assert_eq!(
dt.rpo_cmp(ebb3, jmp_ebb3_ebb1, &cur.func.layout),
Ordering::Less
);
assert_eq!(
dt.rpo_cmp(jmp_ebb3_ebb1, jmp_ebb1_ebb2, &cur.func.layout),
Ordering::Less
);
}
#[test]
fn backwards_layout() {
let mut func = Function::new();
let ebb0 = func.dfg.make_ebb();
let ebb1 = func.dfg.make_ebb();
let ebb2 = func.dfg.make_ebb();
let mut cur = FuncCursor::new(&mut func);
cur.insert_ebb(ebb0);
let jmp02 = cur.ins().jump(ebb2, &[]);
cur.insert_ebb(ebb1);
let trap = cur.ins().trap(TrapCode::User(5));
cur.insert_ebb(ebb2);
let jmp21 = cur.ins().jump(ebb1, &[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let dt = DominatorTree::with_function(cur.func, &cfg);
assert_eq!(cur.func.layout.entry_block(), Some(ebb0));
assert_eq!(dt.idom(ebb0), None);
assert_eq!(dt.idom(ebb1), Some(jmp21));
assert_eq!(dt.idom(ebb2), Some(jmp02));
assert!(dt.dominates(ebb0, ebb0, &cur.func.layout));
assert!(dt.dominates(ebb0, jmp02, &cur.func.layout));
assert!(dt.dominates(ebb0, ebb1, &cur.func.layout));
assert!(dt.dominates(ebb0, trap, &cur.func.layout));
assert!(dt.dominates(ebb0, ebb2, &cur.func.layout));
assert!(dt.dominates(ebb0, jmp21, &cur.func.layout));
assert!(!dt.dominates(jmp02, ebb0, &cur.func.layout));
assert!(dt.dominates(jmp02, jmp02, &cur.func.layout));
assert!(dt.dominates(jmp02, ebb1, &cur.func.layout));
assert!(dt.dominates(jmp02, trap, &cur.func.layout));
assert!(dt.dominates(jmp02, ebb2, &cur.func.layout));
assert!(dt.dominates(jmp02, jmp21, &cur.func.layout));
assert!(!dt.dominates(ebb1, ebb0, &cur.func.layout));
assert!(!dt.dominates(ebb1, jmp02, &cur.func.layout));
assert!(dt.dominates(ebb1, ebb1, &cur.func.layout));
assert!(dt.dominates(ebb1, trap, &cur.func.layout));
assert!(!dt.dominates(ebb1, ebb2, &cur.func.layout));
assert!(!dt.dominates(ebb1, jmp21, &cur.func.layout));
assert!(!dt.dominates(trap, ebb0, &cur.func.layout));
assert!(!dt.dominates(trap, jmp02, &cur.func.layout));
assert!(!dt.dominates(trap, ebb1, &cur.func.layout));
assert!(dt.dominates(trap, trap, &cur.func.layout));
assert!(!dt.dominates(trap, ebb2, &cur.func.layout));
assert!(!dt.dominates(trap, jmp21, &cur.func.layout));
assert!(!dt.dominates(ebb2, ebb0, &cur.func.layout));
assert!(!dt.dominates(ebb2, jmp02, &cur.func.layout));
assert!(dt.dominates(ebb2, ebb1, &cur.func.layout));
assert!(dt.dominates(ebb2, trap, &cur.func.layout));
assert!(dt.dominates(ebb2, ebb2, &cur.func.layout));
assert!(dt.dominates(ebb2, jmp21, &cur.func.layout));
assert!(!dt.dominates(jmp21, ebb0, &cur.func.layout));
assert!(!dt.dominates(jmp21, jmp02, &cur.func.layout));
assert!(dt.dominates(jmp21, ebb1, &cur.func.layout));
assert!(dt.dominates(jmp21, trap, &cur.func.layout));
assert!(!dt.dominates(jmp21, ebb2, &cur.func.layout));
assert!(dt.dominates(jmp21, jmp21, &cur.func.layout));
}
#[test]
fn renumbering() {
let mut func = Function::new();
let entry = func.dfg.make_ebb();
let ebb0 = func.dfg.make_ebb();
let ebb100 = func.dfg.make_ebb();
let mut cur = FuncCursor::new(&mut func);
cur.insert_ebb(entry);
cur.ins().jump(ebb0, &[]);
cur.insert_ebb(ebb0);
let cond = cur.ins().iconst(I32, 0);
let inst2 = cur.ins().brz(cond, ebb0, &[]);
let inst3 = cur.ins().brz(cond, ebb0, &[]);
let inst4 = cur.ins().brz(cond, ebb0, &[]);
let inst5 = cur.ins().brz(cond, ebb0, &[]);
cur.ins().jump(ebb100, &[]);
cur.insert_ebb(ebb100);
cur.ins().return_(&[]);
let mut cfg = ControlFlowGraph::with_function(cur.func);
let mut dt = DominatorTree::with_function(cur.func, &cfg);
let ebb1 = cur.func.dfg.make_ebb();
cur.func.layout.split_ebb(ebb1, inst2);
cur.goto_bottom(ebb0);
let middle_jump_inst = cur.ins().jump(ebb1, &[]);
dt.recompute_split_ebb(ebb0, ebb1, middle_jump_inst);
let ebb2 = cur.func.dfg.make_ebb();
cur.func.layout.split_ebb(ebb2, inst3);
cur.goto_bottom(ebb1);
let middle_jump_inst = cur.ins().jump(ebb2, &[]);
dt.recompute_split_ebb(ebb1, ebb2, middle_jump_inst);
let ebb3 = cur.func.dfg.make_ebb();
cur.func.layout.split_ebb(ebb3, inst4);
cur.goto_bottom(ebb2);
let middle_jump_inst = cur.ins().jump(ebb3, &[]);
dt.recompute_split_ebb(ebb2, ebb3, middle_jump_inst);
let ebb4 = cur.func.dfg.make_ebb();
cur.func.layout.split_ebb(ebb4, inst5);
cur.goto_bottom(ebb3);
let middle_jump_inst = cur.ins().jump(ebb4, &[]);
dt.recompute_split_ebb(ebb3, ebb4, middle_jump_inst);
cfg.compute(cur.func);
let flags = settings::Flags::new(settings::builder());
let mut errors = VerifierErrors::default();
verify_context(cur.func, &cfg, &dt, &flags, &mut errors).unwrap();
assert!(errors.0.is_empty());
}
}