A lightweight WebAssembly runtime that is fast, secure, and standards-compliant
//! A post-dominator tree for a single function.
//!
//! The *post-dominator tree* is the dual of the [`DominatorTree`]: it answers
//! whether every path from a block to a function exit (a `return`, `trap`,
//! etc.) must pass through some other block.
//!
//! It is computed by reusing the ordinary dominator-tree machinery on a
//! modified version of the control-flow graph:
//!
//! * Add a virtual *sink* node.
//!
//! * Every block whose terminator does not branch anywhere (`return`,
//! `return_call`, `trap`, etc.) is given an edge to the virtual sink.
//!
//! * Reverse every edge in the graph, so `a -> b` becomes `b -> a`.
//!
//! * Compute the dominator tree of this reversed graph, rooted at the virtual
//! sink.
//!
//! Note that we don't actually reify this modified version of the control-flow
//! graph, we instead use the `ReverseGraph` implementation of the
//! `DomTreeGraph` trait.
use crate::dominator_tree::{ChildIter, DomTreeGraph, DominatorTree};
use crate::flowgraph::{BlockPredecessor, ControlFlowGraph};
use crate::ir::{Block, Layout, ProgramPoint};
use core::cmp::Ordering;
/// The reversed control-flow graph, augmented with a virtual sink above the
/// function's exit blocks. Computing a `DominatorTree` over this graph yields
/// the post-dominator tree.
struct ReverseGraph<'a> {
cfg: &'a ControlFlowGraph,
}
impl DomTreeGraph for ReverseGraph<'_> {
fn num_blocks(&self) -> usize {
self.cfg.num_blocks()
}
fn roots(&self) -> impl Iterator<Item = Block> {
// The roots of the post-dominator forest are the function's exit
// blocks: those whose terminator branches nowhere (e.g. `return`,
// `return_call`, `trap`, etc...). These are exactly the blocks with no
// CFG successors, and they are precisely the blocks with an edge to the
// virtual sink.
//
// `cfg.blocks()` may include blocks not in the layout, but those are
// isolated in the graph (no predecessors or successors), so they only
// ever appear as trivial single-node roots and never affect the
// post-domination of any real block.
self.cfg
.blocks()
.filter(|&block| self.cfg.succ_iter(block).next().is_none())
}
fn successors(&self, block: Block) -> impl Iterator<Item = Block> {
// Edges are reversed: a successor in the reversed graph is a
// predecessor in the CFG.
self.cfg
.pred_iter(block)
.map(|pred: BlockPredecessor| pred.block)
}
fn predecessors(&self, block: Block) -> impl Iterator<Item = Block> {
// Edges are reversed: a predecessor in the reversed graph is a
// successor in the CFG.
self.cfg.succ_iter(block)
}
}
/// The post-dominator tree for a single function.
pub struct PostDominatorTree {
/// The dominator tree of the reversed CFG. Its "dominates" relation is
/// post-domination in the original function.
dom_tree: DominatorTree,
}
impl Default for PostDominatorTree {
fn default() -> Self {
Self::new()
}
}
impl PostDominatorTree {
/// Allocate a new blank post-dominator tree.
///
/// Use `compute` to compute the post-dominator tree for a function.
pub fn new() -> Self {
Self {
dom_tree: DominatorTree::new(),
}
}
/// Allocate and compute a post-dominator tree.
pub fn with_cfg(cfg: &ControlFlowGraph) -> Self {
let mut post_domtree = Self::new();
post_domtree.compute(cfg);
post_domtree
}
/// Reset and compute the post-dominator tree from the control-flow graph
/// `cfg`.
pub fn compute(&mut self, cfg: &ControlFlowGraph) {
debug_assert!(cfg.is_valid());
self.dom_tree.compute_from_graph(&ReverseGraph { cfg });
}
/// Clear the data structures used to represent the post-dominator
/// tree.
///
/// This will leave the tree in a state where `is_valid()` returns `false`.
pub fn clear(&mut self) {
self.dom_tree.clear();
}
/// Check if the post-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 post-dominator tree is consistent
/// with the CFG.
pub fn is_valid(&self) -> bool {
self.dom_tree.is_valid()
}
/// Returns the immediate post-dominator of `block`.
///
/// `block_a` is said to *post-dominate* `block_b` if all control-flow paths
/// from `block_b` out of this function (via return or trap) must go through
/// `block_a`.
///
/// The *immediate post-dominator* is the post-dominator that is closest to
/// `block`. All other post-dominators also post-dominate the immediate
/// post-dominator.
///
/// This returns `None` if `block` diverges and cannot exit the function, or
/// if `block` directly exits the function (returns or traps).
pub fn immediate_post_dominator(&self, block: Block) -> Option<Block> {
self.dom_tree.idom(block)
}
/// Returns `true` if every path from `b` out of this function (via return
/// or trap) must go through `a`.
pub fn post_dominates<A, B>(&self, a: A, b: B, layout: &Layout) -> bool
where
A: Into<ProgramPoint>,
B: Into<ProgramPoint>,
{
let a = a.into();
let b = b.into();
match a {
ProgramPoint::Block(block_a) => match b {
ProgramPoint::Block(block_b) => self.block_post_dominates(block_a, block_b),
ProgramPoint::Inst(inst_b) => {
let block_b = layout
.inst_block(inst_b)
.expect("instruction not in layout");
// A block header does not post-dominate a later instruction
// in its own block, but a header does post-dominate
// instructions in blocks that it strictly post-dominates.
block_a != block_b && self.block_post_dominates(block_a, block_b)
}
},
ProgramPoint::Inst(inst_a) => {
let block_a: Block = layout
.inst_block(inst_a)
.expect("Instruction not in layout.");
match b {
ProgramPoint::Block(block_b) => {
// An instruction post-dominates the header of its own
// block: control reaches the instruction after the
// header.
self.block_post_dominates(block_a, block_b)
}
ProgramPoint::Inst(inst_b) => {
let block_b = layout
.inst_block(inst_b)
.expect("instruction not in layout");
if block_a == block_b {
// Within a block, `a` post-dominates `b` iff `a` is
// at or after `b`.
layout.pp_cmp(a, b) != Ordering::Less
} else {
self.block_post_dominates(block_a, block_b)
}
}
}
}
}
}
/// Returns `true` if every path from `b` to a function exit (return or
/// trap) must go through `a`.
pub fn block_post_dominates(&self, block_a: Block, block_b: Block) -> bool {
self.dom_tree.block_dominates(block_a, block_b)
}
/// Get an iterator over the direct children of `block` in the
/// post-dominator tree.
///
/// These are the blocks whose immediate post-dominator is `block`.
pub fn children(&self, block: Block) -> ChildIter<'_> {
self.dom_tree.children(block)
}
/// Is function exit (via return or trap) unreachable from the given block?
pub fn diverges(&self, block: Block) -> bool {
// A block is reachable in the reversed graph iff it can reach a
// function exit; if it cannot, then function exit diverges away from
// it.
!self.dom_tree.is_reachable(block)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::cursor::{Cursor, FuncCursor};
use crate::ir::types::*;
use crate::ir::{Function, InstBuilder, TrapCode};
use alloc::string::String;
use alloc::vec::Vec;
use mutatis::{Mutate, check::Check, mutators as m};
#[test]
fn empty() {
let func = Function::new();
let cfg = ControlFlowGraph::with_function(&func);
let pdt = PostDominatorTree::with_cfg(&cfg);
assert!(pdt.is_valid());
}
#[test]
fn lifecycle() {
let mut func = Function::new();
let block0 = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.ins().return_(&[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let mut pdt = PostDominatorTree::new();
assert!(!pdt.is_valid());
pdt.compute(&cfg);
assert!(pdt.is_valid());
pdt.clear();
assert!(!pdt.is_valid());
// Recompute after clear.
pdt.compute(&cfg);
assert!(pdt.is_valid());
}
#[test]
fn straight_line() {
let mut func = Function::new();
let block0 = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
let v0 = cur.ins().iconst(I32, 1);
let v1 = cur.ins().iadd(v0, v0);
cur.ins().return_(&[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
// The single block is an exit, so it has no post-dominator and does not
// diverge.
assert_eq!(pdt.immediate_post_dominator(block0), None);
assert!(pdt.block_post_dominates(block0, block0));
assert!(!pdt.diverges(block0));
// Instruction-level: a later instruction post-dominates an earlier one.
let v0_def = cur.func.dfg.value_def(v0).unwrap_inst();
let v1_def = cur.func.dfg.value_def(v1).unwrap_inst();
assert!(pdt.post_dominates(v1_def, v0_def, &cur.func.layout));
assert!(!pdt.post_dominates(v0_def, v1_def, &cur.func.layout));
assert!(pdt.post_dominates(v0_def, v0_def, &cur.func.layout));
}
#[test]
fn if_else_diamond() {
let mut func = Function::new();
let block0 = func.dfg.make_block();
let block1 = func.dfg.make_block();
let block2 = func.dfg.make_block();
let join = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
let v0 = cur.ins().iconst(I32, 0);
cur.ins().brif(v0, block1, &[], block2, &[]);
cur.insert_block(block1);
cur.ins().jump(join, &[]);
cur.insert_block(block2);
cur.ins().jump(join, &[]);
cur.insert_block(join);
cur.ins().return_(&[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
// Every path out of the function passes through `join`.
assert_eq!(pdt.immediate_post_dominator(block0), Some(join));
assert_eq!(pdt.immediate_post_dominator(block1), Some(join));
assert_eq!(pdt.immediate_post_dominator(block2), Some(join));
assert_eq!(pdt.immediate_post_dominator(join), None);
assert!(pdt.block_post_dominates(join, block0));
assert!(pdt.block_post_dominates(join, block1));
// An arm does not post-dominate the entry (the other arm avoids it).
assert!(!pdt.block_post_dominates(block1, block0));
assert!(!pdt.block_post_dominates(block2, block0));
// The entry does not post-dominate the join.
assert!(!pdt.block_post_dominates(block0, join));
for block in [block0, block1, block2, join] {
assert!(!pdt.diverges(block));
}
// Cross-block `post_dominates` with instruction/block endpoints.
let layout = &cur.func.layout;
let entry_term = layout.last_inst(block0).unwrap();
let join_term = layout.last_inst(join).unwrap();
// The join's terminator post-dominates the entry's terminator...
assert!(pdt.post_dominates(join_term, entry_term, layout));
// ...but not vice versa.
assert!(!pdt.post_dominates(entry_term, join_term, layout));
// Block/instruction mixes across blocks defer to block post-domination.
assert!(pdt.post_dominates(join, entry_term, layout));
assert!(!pdt.post_dominates(entry_term, join, layout));
// `join` post-dominates the three other blocks.
let mut kids = pdt.children(join).collect::<alloc::vec::Vec<_>>();
kids.sort();
assert_eq!(kids, [block0, block1, block2]);
}
#[test]
fn terminating_loop() {
let mut func = Function::new();
let entry = func.dfg.make_block();
let header = func.dfg.make_block();
let body = func.dfg.make_block();
let exit = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(entry);
cur.ins().jump(header, &[]);
cur.insert_block(header);
let v0 = cur.ins().iconst(I32, 0);
cur.ins().brif(v0, body, &[], exit, &[]);
cur.insert_block(body);
cur.ins().jump(header, &[]);
cur.insert_block(exit);
cur.ins().return_(&[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
assert_eq!(pdt.immediate_post_dominator(entry), Some(header));
assert_eq!(pdt.immediate_post_dominator(header), Some(exit));
assert_eq!(pdt.immediate_post_dominator(body), Some(header));
assert_eq!(pdt.immediate_post_dominator(exit), None);
assert!(pdt.block_post_dominates(exit, entry));
assert!(pdt.block_post_dominates(exit, body));
assert!(pdt.block_post_dominates(header, body));
assert!(!pdt.block_post_dominates(body, header));
// The loop can always exit, so nothing diverges.
for block in [entry, header, body, exit] {
assert!(!pdt.diverges(block));
}
}
#[test]
fn infinite_loop() {
let mut func = Function::new();
let block0 = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
cur.ins().jump(block0, &[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
// There is no exit block, so the function never returns: every block
// diverges and has no post-dominator.
assert!(pdt.is_valid());
assert!(pdt.diverges(block0));
assert_eq!(pdt.immediate_post_dominator(block0), None);
}
#[test]
fn infinite_loop_with_side_exit() {
let mut func = Function::new();
let entry = func.dfg.make_block();
let header = func.dfg.make_block();
let body = func.dfg.make_block();
let exit = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(entry);
cur.ins().jump(header, &[]);
cur.insert_block(header);
let v0 = cur.ins().iconst(I32, 0);
cur.ins().brif(v0, exit, &[], body, &[]);
// `body` loops forever and never reaches an exit.
cur.insert_block(body);
cur.ins().jump(body, &[]);
cur.insert_block(exit);
cur.ins().return_(&[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
// Only `body` diverges.
assert!(pdt.diverges(body));
assert_eq!(pdt.immediate_post_dominator(body), None);
assert!(!pdt.diverges(entry));
assert!(!pdt.diverges(header));
assert!(!pdt.diverges(exit));
assert_eq!(pdt.immediate_post_dominator(header), Some(exit));
assert_eq!(pdt.immediate_post_dominator(entry), Some(header));
assert_eq!(pdt.immediate_post_dominator(exit), None);
}
#[test]
fn multiple_returns() {
let mut func = Function::new();
let entry = func.dfg.make_block();
let block1 = func.dfg.make_block();
let block2 = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(entry);
let v0 = cur.ins().iconst(I32, 0);
cur.ins().brif(v0, block1, &[], block2, &[]);
cur.insert_block(block1);
cur.ins().return_(&[]);
cur.insert_block(block2);
cur.ins().return_(&[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
// Two distinct exit blocks: neither post-dominates the entry, and the
// entry's only post-dominator is the (virtual) sink.
assert_eq!(pdt.immediate_post_dominator(block1), None);
assert_eq!(pdt.immediate_post_dominator(block2), None);
assert_eq!(pdt.immediate_post_dominator(entry), None);
assert!(!pdt.block_post_dominates(block1, entry));
assert!(!pdt.block_post_dominates(block2, entry));
// Blocks in distinct exit subtrees do not post-dominate each other.
assert!(!pdt.block_post_dominates(block1, block2));
assert!(!pdt.block_post_dominates(block2, block1));
for block in [entry, block1, block2] {
assert!(!pdt.diverges(block));
}
}
#[test]
fn trap_as_exit() {
let mut func = Function::new();
let entry = func.dfg.make_block();
let ret_block = func.dfg.make_block();
let trap_block = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(entry);
let v0 = cur.ins().iconst(I32, 0);
cur.ins().brif(v0, ret_block, &[], trap_block, &[]);
cur.insert_block(ret_block);
cur.ins().return_(&[]);
cur.insert_block(trap_block);
cur.ins().trap(TrapCode::unwrap_user(1));
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
// A `trap` is a function exit, so `trap_block` is a root of the forest
// and does not diverge.
assert_eq!(pdt.immediate_post_dominator(trap_block), None);
assert_eq!(pdt.immediate_post_dominator(ret_block), None);
assert_eq!(pdt.immediate_post_dominator(entry), None);
assert!(!pdt.diverges(trap_block));
assert!(!pdt.diverges(ret_block));
assert!(!pdt.diverges(entry));
}
#[test]
fn insts_post_dominate_same_block() {
let mut func = Function::new();
let block0 = func.dfg.make_block();
let mut cur = FuncCursor::new(&mut func);
cur.insert_block(block0);
let v1 = cur.ins().iconst(I32, 1);
let v2 = cur.ins().iadd(v1, v1);
let v3 = cur.ins().iadd(v2, v2);
cur.ins().return_(&[]);
let cfg = ControlFlowGraph::with_function(cur.func);
let pdt = PostDominatorTree::with_cfg(&cfg);
let v1_def = cur.func.dfg.value_def(v1).unwrap_inst();
let v2_def = cur.func.dfg.value_def(v2).unwrap_inst();
let v3_def = cur.func.dfg.value_def(v3).unwrap_inst();
let layout = &cur.func.layout;
// Later instructions post-dominate earlier ones.
assert!(pdt.post_dominates(v2_def, v1_def, layout));
assert!(pdt.post_dominates(v3_def, v1_def, layout));
assert!(pdt.post_dominates(v3_def, v2_def, layout));
// Earlier instructions do not post-dominate later ones.
assert!(!pdt.post_dominates(v1_def, v2_def, layout));
assert!(!pdt.post_dominates(v1_def, v3_def, layout));
// An instruction post-dominates itself.
assert!(pdt.post_dominates(v2_def, v2_def, layout));
// An instruction post-dominates the header of its own block...
assert!(pdt.post_dominates(v1_def, block0, layout));
// ...but a block header does not post-dominate a later instruction in
// its own block.
assert!(!pdt.post_dominates(block0, v1_def, layout));
// A block post-dominates itself.
assert!(pdt.post_dominates(block0, block0, layout));
}
/// Property-based test against a brute-force oracle.
///
/// We mutate a small abstract control-flow graph with `mutatis`, build a
/// corresponding Cranelift function, and compare the `PostDominatorTree`
/// against an independent post-dominance dataflow computed on the abstract
/// graph.
#[test]
fn post_dominators_match_oracle() -> mutatis::check::CheckResult<GraphSpec> {
use Terminator::*;
let corpus = [
// Straight-line: a single returning block.
GraphSpec {
blocks: alloc::vec![Return],
},
// Straight-line: chained jumps and a return.
GraphSpec {
blocks: alloc::vec![Jump(1), Jump(2), Return],
},
// If-else diamond.
GraphSpec {
blocks: alloc::vec![Brif(1, 2), Jump(3), Jump(3), Return],
},
// Terminating loop.
GraphSpec {
blocks: alloc::vec![Jump(1), Brif(1, 2), Return],
},
// Infinite loop.
GraphSpec {
blocks: alloc::vec![Jump(1), Jump(0)],
},
];
Check::new()
.iters(10_000)
.run_with(m::default::<GraphSpec>(), corpus, check_post_dominance)
}
/// Cap on the number of blocks we build, so node indices (plus the virtual
/// sink) fit in a `u64` bitmask.
const MAX_BLOCKS: usize = 12;
/// Description of a whole control-flow graph.
#[derive(Clone, Debug, Default, Mutate)]
struct GraphSpec {
blocks: Vec<Terminator>,
}
impl GraphSpec {
fn fixup(&self) -> Option<Self> {
let n = self.blocks.len().min(MAX_BLOCKS);
if n == 0 {
return None;
}
let mut graph = GraphSpec {
blocks: self.blocks[..n].to_vec(),
};
for terminator in &mut graph.blocks {
terminator.fixup(n);
}
Some(graph)
}
/// Build a Cranelift function realizing `terminators`. Block 0 is the entry.
fn build(&self) -> (Function, Vec<Block>) {
let mut func = Function::new();
let blocks: Vec<Block> = (0..self.blocks.len())
.map(|_| func.dfg.make_block())
.collect();
let mut cur = FuncCursor::new(&mut func);
for (i, terminator) in self.blocks.iter().enumerate() {
cur.insert_block(blocks[i]);
match *terminator {
Terminator::Return => {
cur.ins().return_(&[]);
}
Terminator::Jump(t) => {
cur.ins().jump(blocks[t], &[]);
}
Terminator::Brif(t1, t2) => {
let c = cur.ins().iconst(I32, 0);
cur.ins().brif(c, blocks[t1], &[], blocks[t2], &[]);
}
}
}
(func, blocks)
}
}
/// A block's terminator.
#[derive(Clone, Copy, Debug, Default, Mutate)]
enum Terminator {
#[default]
Return,
Jump(usize),
Brif(usize, usize),
}
impl Terminator {
fn fixup(&mut self, n: usize) {
match self {
Self::Return => {}
Self::Jump(a) => {
*a %= n;
}
Self::Brif(a, b) => {
*a %= n;
*b %= n;
}
}
}
}
/// Check that the `PostDominatorTree` agrees with a brute-force
/// post-dominance dataflow on the abstract graph.
fn check_post_dominance(graph: &GraphSpec) -> Result<(), String> {
let Some(graph) = graph.fixup() else {
return Ok(());
};
let (func, blocks) = graph.build();
let cfg = ControlFlowGraph::with_function(&func);
let pdt = PostDominatorTree::with_cfg(&cfg);
// The virtual sink is node `n`. Exit blocks have an edge to it.
let sink = graph.blocks.len();
let succ: Vec<Vec<usize>> = graph
.blocks
.iter()
.map(|t| match *t {
Terminator::Return => alloc::vec![sink],
Terminator::Jump(x) => alloc::vec![x],
Terminator::Brif(x, y) => alloc::vec![x, y],
})
.collect();
// Which nodes can reach the sink? Those that cannot are the diverging
// blocks. Post-domination is only well-defined for the rest.
let mut reaches = alloc::vec![false; graph.blocks.len() + 1];
reaches[sink] = true;
loop {
let mut changed = false;
for i in 0..graph.blocks.len() {
if !reaches[i] && succ[i].iter().any(|&s| reaches[s]) {
reaches[i] = true;
changed = true;
}
}
if !changed {
break;
}
}
// Post-dominance sets as bitmasks over node indices `0..=sink`, via the
// greatest fixpoint of `pdom(i) = {i} ∪ ⋂_{s ∈ succ(i)} pdom(s)`.
let bit = |x: usize| 1u64 << x;
let universe = bit(graph.blocks.len() + 1) - 1;
let mut pdom = alloc::vec![universe; graph.blocks.len() + 1];
pdom[sink] = bit(sink);
loop {
let mut changed = false;
for i in 0..graph.blocks.len() {
let mut inter = u64::MAX;
for &s in &succ[i] {
inter &= pdom[s];
}
let next = bit(i) | inter;
if next != pdom[i] {
pdom[i] = next;
changed = true;
}
}
if !changed {
break;
}
}
for i in 0..graph.blocks.len() {
let expect_diverges = !reaches[i];
if pdt.diverges(blocks[i]) != expect_diverges {
return Err(format!(
"diverges({i}) = {}, expected {expect_diverges}",
pdt.diverges(blocks[i]),
));
}
if expect_diverges {
if pdt.immediate_post_dominator(blocks[i]).is_some() {
return Err(format!(
"immediate_post_dominator({i}) should be None for a diverging block;",
));
}
continue;
}
// `a` post-dominates `i` iff `a ∈ pdom(i)`.
for a in 0..graph.blocks.len() {
let expect = pdom[i] & bit(a) != 0;
if pdt.block_post_dominates(blocks[a], blocks[i]) != expect {
return Err(format!(
"block_post_dominates({a}, {i}) = {}, expected {expect}",
pdt.block_post_dominates(blocks[a], blocks[i]),
));
}
}
// The immediate post-dominator is the strict post-dominator with
// the largest post-dominator set (i.e. closest to `i`). The
// post-dominators form a chain to the sink with strictly decreasing
// set sizes, so this is unique. The virtual sink maps to `None`.
let strict = pdom[i] & !bit(i);
let mut best: Option<(u32, usize)> = None;
for x in 0..=graph.blocks.len() {
if strict & bit(x) != 0 {
let size = pdom[x].count_ones();
if best.map_or(true, |(best_size, _)| size > best_size) {
best = Some((size, x));
}
}
}
let expect_ipdom = match best {
Some((_, x)) if x != sink => Some(blocks[x]),
_ => None,
};
if pdt.immediate_post_dominator(blocks[i]) != expect_ipdom {
return Err(format!(
"immediate_post_dominator({i}) = {:?}, expected {expect_ipdom:?}",
pdt.immediate_post_dominator(blocks[i]),
));
}
}
Ok(())
}
}