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