1 //! Topological order of blocks, according to the dominator tree.
2 
3 use crate::dominator_tree::DominatorTree;
4 use crate::entity::EntitySet;
5 use crate::ir::{Block, Layout};
6 use alloc::vec::Vec;
7 
8 /// Present blocks in a topological order such that all dominating blocks are guaranteed to be visited
9 /// before the current block.
10 ///
11 /// There are many topological orders of the blocks in a function, so it is possible to provide a
12 /// preferred order, and the `TopoOrder` will present blocks in an order that is as close as possible
13 /// to the preferred order.
14 pub struct TopoOrder {
15     /// Preferred order of blocks to visit.
16     preferred: Vec<Block>,
17 
18     /// Next entry to get from `preferred`.
19     next: usize,
20 
21     /// Set of visited blocks.
22     visited: EntitySet<Block>,
23 
24     /// Stack of blocks to be visited next, already in `visited`.
25     stack: Vec<Block>,
26 }
27 
28 impl TopoOrder {
29     /// Create a new empty topological order.
new() -> Self30     pub fn new() -> Self {
31         Self {
32             preferred: Vec::new(),
33             next: 0,
34             visited: EntitySet::new(),
35             stack: Vec::new(),
36         }
37     }
38 
39     /// Clear all data structures in this topological order.
clear(&mut self)40     pub fn clear(&mut self) {
41         self.preferred.clear();
42         self.next = 0;
43         self.visited.clear();
44         self.stack.clear();
45     }
46 
47     /// Reset and initialize with a preferred sequence of blocks. The resulting topological order is
48     /// guaranteed to contain all of the blocks in `preferred` as well as any dominators.
reset<Blocks>(&mut self, preferred: Blocks) where Blocks: IntoIterator<Item = Block>,49     pub fn reset<Blocks>(&mut self, preferred: Blocks)
50     where
51         Blocks: IntoIterator<Item = Block>,
52     {
53         self.preferred.clear();
54         self.preferred.extend(preferred);
55         self.next = 0;
56         self.visited.clear();
57         self.stack.clear();
58     }
59 
60     /// Get the next block in the topological order.
61     ///
62     /// Two things are guaranteed about the blocks returned by this function:
63     ///
64     /// - All blocks in the `preferred` iterator given to `reset` will be returned.
65     /// - All dominators are visited before the block returned.
next(&mut self, layout: &Layout, domtree: &DominatorTree) -> Option<Block>66     pub fn next(&mut self, layout: &Layout, domtree: &DominatorTree) -> Option<Block> {
67         self.visited.resize(layout.block_capacity());
68         // Any entries in `stack` should be returned immediately. They have already been added to
69         // `visited`.
70         while self.stack.is_empty() {
71             match self.preferred.get(self.next).cloned() {
72                 None => return None,
73                 Some(mut block) => {
74                     // We have the next block in the preferred order.
75                     self.next += 1;
76                     // Push it along with any non-visited dominators.
77                     while self.visited.insert(block) {
78                         self.stack.push(block);
79                         match domtree.idom(block) {
80                             Some(idom) => {
81                                 block = layout.inst_block(idom).expect("idom not in layout")
82                             }
83                             None => break,
84                         }
85                     }
86                 }
87             }
88         }
89         self.stack.pop()
90     }
91 }
92 
93 #[cfg(test)]
94 mod tests {
95     use super::*;
96     use crate::cursor::{Cursor, FuncCursor};
97     use crate::dominator_tree::DominatorTree;
98     use crate::flowgraph::ControlFlowGraph;
99     use crate::ir::{Function, InstBuilder};
100     use core::iter;
101 
102     #[test]
empty()103     fn empty() {
104         let func = Function::new();
105         let cfg = ControlFlowGraph::with_function(&func);
106         let domtree = DominatorTree::with_function(&func, &cfg);
107         let mut topo = TopoOrder::new();
108 
109         assert_eq!(topo.next(&func.layout, &domtree), None);
110         topo.reset(func.layout.blocks());
111         assert_eq!(topo.next(&func.layout, &domtree), None);
112     }
113 
114     #[test]
simple()115     fn simple() {
116         let mut func = Function::new();
117         let block0 = func.dfg.make_block();
118         let block1 = func.dfg.make_block();
119 
120         {
121             let mut cur = FuncCursor::new(&mut func);
122 
123             cur.insert_block(block0);
124             cur.ins().jump(block1, &[]);
125             cur.insert_block(block1);
126             cur.ins().jump(block1, &[]);
127         }
128 
129         let cfg = ControlFlowGraph::with_function(&func);
130         let domtree = DominatorTree::with_function(&func, &cfg);
131         let mut topo = TopoOrder::new();
132 
133         topo.reset(iter::once(block1));
134         assert_eq!(topo.next(&func.layout, &domtree), Some(block0));
135         assert_eq!(topo.next(&func.layout, &domtree), Some(block1));
136         assert_eq!(topo.next(&func.layout, &domtree), None);
137     }
138 }
139