cranelift_codegen/
dominator_tree.rs

1//! A Dominator Tree represented as mappings of Blocks to their immediate dominator.
2
3use crate::entity::SecondaryMap;
4use crate::flowgraph::{BlockPredecessor, ControlFlowGraph};
5use crate::ir::{Block, Function, Inst, Layout, ProgramPoint};
6use crate::packed_option::PackedOption;
7use crate::timing;
8use crate::traversals::Dfs;
9use alloc::vec::Vec;
10use core::cmp;
11use core::cmp::Ordering;
12use core::mem;
13
14/// RPO numbers are not first assigned in a contiguous way but as multiples of STRIDE, to leave
15/// room for modifications of the dominator tree.
16const STRIDE: u32 = 4;
17
18/// Dominator tree node. We keep one of these per block.
19#[derive(Clone, Default)]
20struct DomNode {
21    /// Number of this node in a reverse post-order traversal of the CFG, starting from 1.
22    /// This number is monotonic in the reverse postorder but not contiguous, since we leave
23    /// holes for later localized modifications of the dominator tree.
24    /// Unreachable nodes get number 0, all others are positive.
25    rpo_number: u32,
26
27    /// The immediate dominator of this block, represented as the branch or jump instruction at the
28    /// end of the dominating basic block.
29    ///
30    /// This is `None` for unreachable blocks and the entry block which doesn't have an immediate
31    /// dominator.
32    idom: PackedOption<Inst>,
33}
34
35/// The dominator tree for a single function.
36pub struct DominatorTree {
37    nodes: SecondaryMap<Block, DomNode>,
38
39    /// CFG post-order of all reachable blocks.
40    postorder: Vec<Block>,
41
42    /// Scratch traversal state used by `compute_postorder()`.
43    dfs: Dfs,
44
45    valid: bool,
46}
47
48/// Methods for querying the dominator tree.
49impl DominatorTree {
50    /// Is `block` reachable from the entry block?
51    pub fn is_reachable(&self, block: Block) -> bool {
52        self.nodes[block].rpo_number != 0
53    }
54
55    /// Get the CFG post-order of blocks that was used to compute the dominator tree.
56    ///
57    /// Note that this post-order is not updated automatically when the CFG is modified. It is
58    /// computed from scratch and cached by `compute()`.
59    pub fn cfg_postorder(&self) -> &[Block] {
60        debug_assert!(self.is_valid());
61        &self.postorder
62    }
63
64    /// Returns the immediate dominator of `block`.
65    ///
66    /// The immediate dominator of a basic block is a basic block which we represent by
67    /// the branch or jump instruction at the end of the basic block. This does not have to be the
68    /// terminator of its block.
69    ///
70    /// A branch or jump is said to *dominate* `block` if all control flow paths from the function
71    /// entry to `block` must go through the branch.
72    ///
73    /// The *immediate dominator* is the dominator that is closest to `block`. All other dominators
74    /// also dominate the immediate dominator.
75    ///
76    /// This returns `None` if `block` is not reachable from the entry block, or if it is the entry block
77    /// which has no dominators.
78    pub fn idom(&self, block: Block) -> Option<Inst> {
79        self.nodes[block].idom.into()
80    }
81
82    /// Compare two blocks relative to the reverse post-order.
83    pub fn rpo_cmp_block(&self, a: Block, b: Block) -> Ordering {
84        self.nodes[a].rpo_number.cmp(&self.nodes[b].rpo_number)
85    }
86
87    /// Compare two program points relative to a reverse post-order traversal of the control-flow
88    /// graph.
89    ///
90    /// Return `Ordering::Less` if `a` comes before `b` in the RPO.
91    ///
92    /// If `a` and `b` belong to the same block, compare their relative position in the block.
93    pub fn rpo_cmp<A, B>(&self, a: A, b: B, layout: &Layout) -> Ordering
94    where
95        A: Into<ProgramPoint>,
96        B: Into<ProgramPoint>,
97    {
98        let a = a.into();
99        let b = b.into();
100        self.rpo_cmp_block(layout.pp_block(a), layout.pp_block(b))
101            .then_with(|| layout.pp_cmp(a, b))
102    }
103
104    /// Returns `true` if `a` dominates `b`.
105    ///
106    /// This means that every control-flow path from the function entry to `b` must go through `a`.
107    ///
108    /// Dominance is ill defined for unreachable blocks. This function can always determine
109    /// dominance for instructions in the same block, but otherwise returns `false` if either block
110    /// is unreachable.
111    ///
112    /// An instruction is considered to dominate itself.
113    pub fn dominates<A, B>(&self, a: A, b: B, layout: &Layout) -> bool
114    where
115        A: Into<ProgramPoint>,
116        B: Into<ProgramPoint>,
117    {
118        let a = a.into();
119        let b = b.into();
120        match a {
121            ProgramPoint::Block(block_a) => {
122                a == b || self.last_dominator(block_a, b, layout).is_some()
123            }
124            ProgramPoint::Inst(inst_a) => {
125                let block_a = layout
126                    .inst_block(inst_a)
127                    .expect("Instruction not in layout.");
128                match self.last_dominator(block_a, b, layout) {
129                    Some(last) => layout.pp_cmp(inst_a, last) != Ordering::Greater,
130                    None => false,
131                }
132            }
133        }
134    }
135
136    /// Find the last instruction in `a` that dominates `b`.
137    /// If no instructions in `a` dominate `b`, return `None`.
138    pub fn last_dominator<B>(&self, a: Block, b: B, layout: &Layout) -> Option<Inst>
139    where
140        B: Into<ProgramPoint>,
141    {
142        let (mut block_b, mut inst_b) = match b.into() {
143            ProgramPoint::Block(block) => (block, None),
144            ProgramPoint::Inst(inst) => (
145                layout.inst_block(inst).expect("Instruction not in layout."),
146                Some(inst),
147            ),
148        };
149        let rpo_a = self.nodes[a].rpo_number;
150
151        // Run a finger up the dominator tree from b until we see a.
152        // Do nothing if b is unreachable.
153        while rpo_a < self.nodes[block_b].rpo_number {
154            let idom = match self.idom(block_b) {
155                Some(idom) => idom,
156                None => return None, // a is unreachable, so we climbed past the entry
157            };
158            block_b = layout.inst_block(idom).expect("Dominator got removed.");
159            inst_b = Some(idom);
160        }
161        if a == block_b {
162            inst_b
163        } else {
164            None
165        }
166    }
167
168    /// Compute the common dominator of two basic blocks.
169    ///
170    /// Both basic blocks are assumed to be reachable.
171    pub fn common_dominator(
172        &self,
173        mut a: BlockPredecessor,
174        mut b: BlockPredecessor,
175        layout: &Layout,
176    ) -> BlockPredecessor {
177        loop {
178            match self.rpo_cmp_block(a.block, b.block) {
179                Ordering::Less => {
180                    // `a` comes before `b` in the RPO. Move `b` up.
181                    let idom = self.nodes[b.block].idom.expect("Unreachable basic block?");
182                    b = BlockPredecessor::new(
183                        layout.inst_block(idom).expect("Dangling idom instruction"),
184                        idom,
185                    );
186                }
187                Ordering::Greater => {
188                    // `b` comes before `a` in the RPO. Move `a` up.
189                    let idom = self.nodes[a.block].idom.expect("Unreachable basic block?");
190                    a = BlockPredecessor::new(
191                        layout.inst_block(idom).expect("Dangling idom instruction"),
192                        idom,
193                    );
194                }
195                Ordering::Equal => break,
196            }
197        }
198
199        debug_assert_eq!(
200            a.block, b.block,
201            "Unreachable block passed to common_dominator?"
202        );
203
204        // We're in the same block. The common dominator is the earlier instruction.
205        if layout.pp_cmp(a.inst, b.inst) == Ordering::Less {
206            a
207        } else {
208            b
209        }
210    }
211}
212
213impl DominatorTree {
214    /// Allocate a new blank dominator tree. Use `compute` to compute the dominator tree for a
215    /// function.
216    pub fn new() -> Self {
217        Self {
218            nodes: SecondaryMap::new(),
219            postorder: Vec::new(),
220            dfs: Dfs::new(),
221            valid: false,
222        }
223    }
224
225    /// Allocate and compute a dominator tree.
226    pub fn with_function(func: &Function, cfg: &ControlFlowGraph) -> Self {
227        let block_capacity = func.layout.block_capacity();
228        let mut domtree = Self {
229            nodes: SecondaryMap::with_capacity(block_capacity),
230            postorder: Vec::with_capacity(block_capacity),
231            dfs: Dfs::new(),
232            valid: false,
233        };
234        domtree.compute(func, cfg);
235        domtree
236    }
237
238    /// Reset and compute a CFG post-order and dominator tree.
239    pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph) {
240        let _tt = timing::domtree();
241        debug_assert!(cfg.is_valid());
242        self.compute_postorder(func);
243        self.compute_domtree(func, cfg);
244        self.valid = true;
245    }
246
247    /// Clear the data structures used to represent the dominator tree. This will leave the tree in
248    /// a state where `is_valid()` returns false.
249    pub fn clear(&mut self) {
250        self.nodes.clear();
251        self.postorder.clear();
252        self.valid = false;
253    }
254
255    /// Check if the dominator tree is in a valid state.
256    ///
257    /// Note that this doesn't perform any kind of validity checks. It simply checks if the
258    /// `compute()` method has been called since the last `clear()`. It does not check that the
259    /// dominator tree is consistent with the CFG.
260    pub fn is_valid(&self) -> bool {
261        self.valid
262    }
263
264    /// Reset all internal data structures and compute a post-order of the control flow graph.
265    ///
266    /// This leaves `rpo_number == 1` for all reachable blocks, 0 for unreachable ones.
267    fn compute_postorder(&mut self, func: &Function) {
268        self.clear();
269        self.nodes.resize(func.dfg.num_blocks());
270        self.postorder.extend(self.dfs.post_order_iter(func));
271    }
272
273    /// Build a dominator tree from a control flow graph using Keith D. Cooper's
274    /// "Simple, Fast Dominator Algorithm."
275    fn compute_domtree(&mut self, func: &Function, cfg: &ControlFlowGraph) {
276        // During this algorithm, `rpo_number` has the following values:
277        //
278        // 0: block is not reachable.
279        // 1: block is reachable, but has not yet been visited during the first pass. This is set by
280        // `compute_postorder`.
281        // 2+: block is reachable and has an assigned RPO number.
282
283        // We'll be iterating over a reverse post-order of the CFG, skipping the entry block.
284        let (entry_block, postorder) = match self.postorder.as_slice().split_last() {
285            Some((&eb, rest)) => (eb, rest),
286            None => return,
287        };
288        debug_assert_eq!(Some(entry_block), func.layout.entry_block());
289
290        // Do a first pass where we assign RPO numbers to all reachable nodes.
291        self.nodes[entry_block].rpo_number = 2 * STRIDE;
292        for (rpo_idx, &block) in postorder.iter().rev().enumerate() {
293            // Update the current node and give it an RPO number.
294            // The entry block got 2, the rest start at 3 by multiples of STRIDE to leave
295            // room for future dominator tree modifications.
296            //
297            // Since `compute_idom` will only look at nodes with an assigned RPO number, the
298            // function will never see an uninitialized predecessor.
299            //
300            // Due to the nature of the post-order traversal, every node we visit will have at
301            // least one predecessor that has previously been visited during this RPO.
302            self.nodes[block] = DomNode {
303                idom: self.compute_idom(block, cfg, &func.layout).into(),
304                rpo_number: (rpo_idx as u32 + 3) * STRIDE,
305            }
306        }
307
308        // Now that we have RPO numbers for everything and initial immediate dominator estimates,
309        // iterate until convergence.
310        //
311        // If the function is free of irreducible control flow, this will exit after one iteration.
312        let mut changed = true;
313        while changed {
314            changed = false;
315            for &block in postorder.iter().rev() {
316                let idom = self.compute_idom(block, cfg, &func.layout).into();
317                if self.nodes[block].idom != idom {
318                    self.nodes[block].idom = idom;
319                    changed = true;
320                }
321            }
322        }
323    }
324
325    // Compute the immediate dominator for `block` using the current `idom` states for the reachable
326    // nodes.
327    fn compute_idom(&self, block: Block, cfg: &ControlFlowGraph, layout: &Layout) -> Inst {
328        // Get an iterator with just the reachable, already visited predecessors to `block`.
329        // Note that during the first pass, `rpo_number` is 1 for reachable blocks that haven't
330        // been visited yet, 0 for unreachable blocks.
331        let mut reachable_preds = cfg
332            .pred_iter(block)
333            .filter(|&BlockPredecessor { block: pred, .. }| self.nodes[pred].rpo_number > 1);
334
335        // The RPO must visit at least one predecessor before this node.
336        let mut idom = reachable_preds
337            .next()
338            .expect("block node must have one reachable predecessor");
339
340        for pred in reachable_preds {
341            idom = self.common_dominator(idom, pred, layout);
342        }
343
344        idom.inst
345    }
346}
347
348/// Optional pre-order information that can be computed for a dominator tree.
349///
350/// This data structure is computed from a `DominatorTree` and provides:
351///
352/// - A forward traversable dominator tree through the `children()` iterator.
353/// - An ordering of blocks according to a dominator tree pre-order.
354/// - Constant time dominance checks at the block granularity.
355///
356/// The information in this auxiliary data structure is not easy to update when the control flow
357/// graph changes, which is why it is kept separate.
358pub struct DominatorTreePreorder {
359    nodes: SecondaryMap<Block, ExtraNode>,
360
361    // Scratch memory used by `compute_postorder()`.
362    stack: Vec<Block>,
363}
364
365#[derive(Default, Clone)]
366struct ExtraNode {
367    /// First child node in the domtree.
368    child: PackedOption<Block>,
369
370    /// Next sibling node in the domtree. This linked list is ordered according to the CFG RPO.
371    sibling: PackedOption<Block>,
372
373    /// Sequence number for this node in a pre-order traversal of the dominator tree.
374    /// Unreachable blocks have number 0, the entry block is 1.
375    pre_number: u32,
376
377    /// Maximum `pre_number` for the sub-tree of the dominator tree that is rooted at this node.
378    /// This is always >= `pre_number`.
379    pre_max: u32,
380}
381
382/// Creating and computing the dominator tree pre-order.
383impl DominatorTreePreorder {
384    /// Create a new blank `DominatorTreePreorder`.
385    pub fn new() -> Self {
386        Self {
387            nodes: SecondaryMap::new(),
388            stack: Vec::new(),
389        }
390    }
391
392    /// Recompute this data structure to match `domtree`.
393    pub fn compute(&mut self, domtree: &DominatorTree, layout: &Layout) {
394        self.nodes.clear();
395
396        // Step 1: Populate the child and sibling links.
397        //
398        // By following the CFG post-order and pushing to the front of the lists, we make sure that
399        // sibling lists are ordered according to the CFG reverse post-order.
400        for &block in domtree.cfg_postorder() {
401            if let Some(idom_inst) = domtree.idom(block) {
402                let idom = layout
403                    .inst_block(idom_inst)
404                    .expect("Instruction not in layout.");
405                let sib = mem::replace(&mut self.nodes[idom].child, block.into());
406                self.nodes[block].sibling = sib;
407            } else {
408                // The only block without an immediate dominator is the entry.
409                self.stack.push(block);
410            }
411        }
412
413        // Step 2. Assign pre-order numbers from a DFS of the dominator tree.
414        debug_assert!(self.stack.len() <= 1);
415        let mut n = 0;
416        while let Some(block) = self.stack.pop() {
417            n += 1;
418            let node = &mut self.nodes[block];
419            node.pre_number = n;
420            node.pre_max = n;
421            if let Some(n) = node.sibling.expand() {
422                self.stack.push(n);
423            }
424            if let Some(n) = node.child.expand() {
425                self.stack.push(n);
426            }
427        }
428
429        // Step 3. Propagate the `pre_max` numbers up the tree.
430        // The CFG post-order is topologically ordered w.r.t. dominance so a node comes after all
431        // its dominator tree children.
432        for &block in domtree.cfg_postorder() {
433            if let Some(idom_inst) = domtree.idom(block) {
434                let idom = layout
435                    .inst_block(idom_inst)
436                    .expect("Instruction not in layout.");
437                let pre_max = cmp::max(self.nodes[block].pre_max, self.nodes[idom].pre_max);
438                self.nodes[idom].pre_max = pre_max;
439            }
440        }
441    }
442}
443
444/// An iterator that enumerates the direct children of a block in the dominator tree.
445pub struct ChildIter<'a> {
446    dtpo: &'a DominatorTreePreorder,
447    next: PackedOption<Block>,
448}
449
450impl<'a> Iterator for ChildIter<'a> {
451    type Item = Block;
452
453    fn next(&mut self) -> Option<Block> {
454        let n = self.next.expand();
455        if let Some(block) = n {
456            self.next = self.dtpo.nodes[block].sibling;
457        }
458        n
459    }
460}
461
462/// Query interface for the dominator tree pre-order.
463impl DominatorTreePreorder {
464    /// Get an iterator over the direct children of `block` in the dominator tree.
465    ///
466    /// These are the block's whose immediate dominator is an instruction in `block`, ordered according
467    /// to the CFG reverse post-order.
468    pub fn children(&self, block: Block) -> ChildIter {
469        ChildIter {
470            dtpo: self,
471            next: self.nodes[block].child,
472        }
473    }
474
475    /// Fast, constant time dominance check with block granularity.
476    ///
477    /// This computes the same result as `domtree.dominates(a, b)`, but in guaranteed fast constant
478    /// time. This is less general than the `DominatorTree` method because it only works with block
479    /// program points.
480    ///
481    /// A block is considered to dominate itself.
482    pub fn dominates(&self, a: Block, b: Block) -> bool {
483        let na = &self.nodes[a];
484        let nb = &self.nodes[b];
485        na.pre_number <= nb.pre_number && na.pre_max >= nb.pre_max
486    }
487
488    /// Compare two blocks according to the dominator pre-order.
489    pub fn pre_cmp_block(&self, a: Block, b: Block) -> Ordering {
490        self.nodes[a].pre_number.cmp(&self.nodes[b].pre_number)
491    }
492
493    /// Compare two program points according to the dominator tree pre-order.
494    ///
495    /// This ordering of program points have the property that given a program point, pp, all the
496    /// program points dominated by pp follow immediately and contiguously after pp in the order.
497    pub fn pre_cmp<A, B>(&self, a: A, b: B, layout: &Layout) -> Ordering
498    where
499        A: Into<ProgramPoint>,
500        B: Into<ProgramPoint>,
501    {
502        let a = a.into();
503        let b = b.into();
504        self.pre_cmp_block(layout.pp_block(a), layout.pp_block(b))
505            .then_with(|| layout.pp_cmp(a, b))
506    }
507}
508
509#[cfg(test)]
510mod tests {
511    use super::*;
512    use crate::cursor::{Cursor, FuncCursor};
513    use crate::ir::types::*;
514    use crate::ir::{InstBuilder, TrapCode};
515
516    #[test]
517    fn empty() {
518        let func = Function::new();
519        let cfg = ControlFlowGraph::with_function(&func);
520        debug_assert!(cfg.is_valid());
521        let dtree = DominatorTree::with_function(&func, &cfg);
522        assert_eq!(0, dtree.nodes.keys().count());
523        assert_eq!(dtree.cfg_postorder(), &[]);
524
525        let mut dtpo = DominatorTreePreorder::new();
526        dtpo.compute(&dtree, &func.layout);
527    }
528
529    #[test]
530    fn unreachable_node() {
531        let mut func = Function::new();
532        let block0 = func.dfg.make_block();
533        let v0 = func.dfg.append_block_param(block0, I32);
534        let block1 = func.dfg.make_block();
535        let block2 = func.dfg.make_block();
536        let trap_block = func.dfg.make_block();
537
538        let mut cur = FuncCursor::new(&mut func);
539
540        cur.insert_block(block0);
541        cur.ins().brif(v0, block2, &[], trap_block, &[]);
542
543        cur.insert_block(trap_block);
544        cur.ins().trap(TrapCode::User(0));
545
546        cur.insert_block(block1);
547        let v1 = cur.ins().iconst(I32, 1);
548        let v2 = cur.ins().iadd(v0, v1);
549        cur.ins().jump(block0, &[v2]);
550
551        cur.insert_block(block2);
552        cur.ins().return_(&[v0]);
553
554        let cfg = ControlFlowGraph::with_function(cur.func);
555        let dt = DominatorTree::with_function(cur.func, &cfg);
556
557        // Fall-through-first, prune-at-source DFT:
558        //
559        // block0 {
560        //   brif block2 {
561        //     trap
562        //     block2 {
563        //       return
564        //     } block2
565        // } block0
566        assert_eq!(dt.cfg_postorder(), &[block2, trap_block, block0]);
567
568        let v2_def = cur.func.dfg.value_def(v2).unwrap_inst();
569        assert!(!dt.dominates(v2_def, block0, &cur.func.layout));
570        assert!(!dt.dominates(block0, v2_def, &cur.func.layout));
571
572        let mut dtpo = DominatorTreePreorder::new();
573        dtpo.compute(&dt, &cur.func.layout);
574        assert!(dtpo.dominates(block0, block0));
575        assert!(!dtpo.dominates(block0, block1));
576        assert!(dtpo.dominates(block0, block2));
577        assert!(!dtpo.dominates(block1, block0));
578        assert!(dtpo.dominates(block1, block1));
579        assert!(!dtpo.dominates(block1, block2));
580        assert!(!dtpo.dominates(block2, block0));
581        assert!(!dtpo.dominates(block2, block1));
582        assert!(dtpo.dominates(block2, block2));
583    }
584
585    #[test]
586    fn non_zero_entry_block() {
587        let mut func = Function::new();
588        let block0 = func.dfg.make_block();
589        let block1 = func.dfg.make_block();
590        let block2 = func.dfg.make_block();
591        let block3 = func.dfg.make_block();
592        let cond = func.dfg.append_block_param(block3, I32);
593
594        let mut cur = FuncCursor::new(&mut func);
595
596        cur.insert_block(block3);
597        let jmp_block3_block1 = cur.ins().jump(block1, &[]);
598
599        cur.insert_block(block1);
600        let br_block1_block0_block2 = cur.ins().brif(cond, block0, &[], block2, &[]);
601
602        cur.insert_block(block2);
603        cur.ins().jump(block0, &[]);
604
605        cur.insert_block(block0);
606
607        let cfg = ControlFlowGraph::with_function(cur.func);
608        let dt = DominatorTree::with_function(cur.func, &cfg);
609
610        // Fall-through-first, prune-at-source DFT:
611        //
612        // block3 {
613        //   block3:jump block1 {
614        //     block1 {
615        //       block1:brif block0 {
616        //         block1:jump block2 {
617        //           block2 {
618        //             block2:jump block0 (seen)
619        //           } block2
620        //         } block1:jump block2
621        //         block0 {
622        //         } block0
623        //       } block1:brif block0
624        //     } block1
625        //   } block3:jump block1
626        // } block3
627
628        assert_eq!(dt.cfg_postorder(), &[block0, block2, block1, block3]);
629
630        assert_eq!(cur.func.layout.entry_block().unwrap(), block3);
631        assert_eq!(dt.idom(block3), None);
632        assert_eq!(dt.idom(block1).unwrap(), jmp_block3_block1);
633        assert_eq!(dt.idom(block2).unwrap(), br_block1_block0_block2);
634        assert_eq!(dt.idom(block0).unwrap(), br_block1_block0_block2);
635
636        assert!(dt.dominates(
637            br_block1_block0_block2,
638            br_block1_block0_block2,
639            &cur.func.layout
640        ));
641        assert!(!dt.dominates(br_block1_block0_block2, jmp_block3_block1, &cur.func.layout));
642        assert!(dt.dominates(jmp_block3_block1, br_block1_block0_block2, &cur.func.layout));
643
644        assert_eq!(
645            dt.rpo_cmp(block3, block3, &cur.func.layout),
646            Ordering::Equal
647        );
648        assert_eq!(dt.rpo_cmp(block3, block1, &cur.func.layout), Ordering::Less);
649        assert_eq!(
650            dt.rpo_cmp(block3, jmp_block3_block1, &cur.func.layout),
651            Ordering::Less
652        );
653        assert_eq!(
654            dt.rpo_cmp(jmp_block3_block1, br_block1_block0_block2, &cur.func.layout),
655            Ordering::Less
656        );
657    }
658
659    #[test]
660    fn backwards_layout() {
661        let mut func = Function::new();
662        let block0 = func.dfg.make_block();
663        let block1 = func.dfg.make_block();
664        let block2 = func.dfg.make_block();
665
666        let mut cur = FuncCursor::new(&mut func);
667
668        cur.insert_block(block0);
669        let jmp02 = cur.ins().jump(block2, &[]);
670
671        cur.insert_block(block1);
672        let trap = cur.ins().trap(TrapCode::User(5));
673
674        cur.insert_block(block2);
675        let jmp21 = cur.ins().jump(block1, &[]);
676
677        let cfg = ControlFlowGraph::with_function(cur.func);
678        let dt = DominatorTree::with_function(cur.func, &cfg);
679
680        assert_eq!(cur.func.layout.entry_block(), Some(block0));
681        assert_eq!(dt.idom(block0), None);
682        assert_eq!(dt.idom(block1), Some(jmp21));
683        assert_eq!(dt.idom(block2), Some(jmp02));
684
685        assert!(dt.dominates(block0, block0, &cur.func.layout));
686        assert!(dt.dominates(block0, jmp02, &cur.func.layout));
687        assert!(dt.dominates(block0, block1, &cur.func.layout));
688        assert!(dt.dominates(block0, trap, &cur.func.layout));
689        assert!(dt.dominates(block0, block2, &cur.func.layout));
690        assert!(dt.dominates(block0, jmp21, &cur.func.layout));
691
692        assert!(!dt.dominates(jmp02, block0, &cur.func.layout));
693        assert!(dt.dominates(jmp02, jmp02, &cur.func.layout));
694        assert!(dt.dominates(jmp02, block1, &cur.func.layout));
695        assert!(dt.dominates(jmp02, trap, &cur.func.layout));
696        assert!(dt.dominates(jmp02, block2, &cur.func.layout));
697        assert!(dt.dominates(jmp02, jmp21, &cur.func.layout));
698
699        assert!(!dt.dominates(block1, block0, &cur.func.layout));
700        assert!(!dt.dominates(block1, jmp02, &cur.func.layout));
701        assert!(dt.dominates(block1, block1, &cur.func.layout));
702        assert!(dt.dominates(block1, trap, &cur.func.layout));
703        assert!(!dt.dominates(block1, block2, &cur.func.layout));
704        assert!(!dt.dominates(block1, jmp21, &cur.func.layout));
705
706        assert!(!dt.dominates(trap, block0, &cur.func.layout));
707        assert!(!dt.dominates(trap, jmp02, &cur.func.layout));
708        assert!(!dt.dominates(trap, block1, &cur.func.layout));
709        assert!(dt.dominates(trap, trap, &cur.func.layout));
710        assert!(!dt.dominates(trap, block2, &cur.func.layout));
711        assert!(!dt.dominates(trap, jmp21, &cur.func.layout));
712
713        assert!(!dt.dominates(block2, block0, &cur.func.layout));
714        assert!(!dt.dominates(block2, jmp02, &cur.func.layout));
715        assert!(dt.dominates(block2, block1, &cur.func.layout));
716        assert!(dt.dominates(block2, trap, &cur.func.layout));
717        assert!(dt.dominates(block2, block2, &cur.func.layout));
718        assert!(dt.dominates(block2, jmp21, &cur.func.layout));
719
720        assert!(!dt.dominates(jmp21, block0, &cur.func.layout));
721        assert!(!dt.dominates(jmp21, jmp02, &cur.func.layout));
722        assert!(dt.dominates(jmp21, block1, &cur.func.layout));
723        assert!(dt.dominates(jmp21, trap, &cur.func.layout));
724        assert!(!dt.dominates(jmp21, block2, &cur.func.layout));
725        assert!(dt.dominates(jmp21, jmp21, &cur.func.layout));
726    }
727}
cranelift_codegen/dominator_tree.rs

cranelift_codegen/
dominator_tree.rs
