1 //! A control flow graph represented as mappings of basic blocks to their predecessors 2 //! and successors. 3 //! 4 //! Successors are represented as basic blocks while predecessors are represented by basic 5 //! blocks. Basic blocks are denoted by tuples of block and branch/jump instructions. Each 6 //! predecessor tuple corresponds to the end of a basic block. 7 //! 8 //! ```c 9 //! Block0: 10 //! ... ; beginning of basic block 11 //! 12 //! ... 13 //! 14 //! brz vx, Block1 ; end of basic block 15 //! 16 //! ... ; beginning of basic block 17 //! 18 //! ... 19 //! 20 //! jmp Block2 ; end of basic block 21 //! ``` 22 //! 23 //! Here `Block1` and `Block2` would each have a single predecessor denoted as `(Block0, brz)` 24 //! and `(Block0, jmp Block2)` respectively. 25 26 use crate::bforest; 27 use crate::entity::SecondaryMap; 28 use crate::ir::instructions::BranchInfo; 29 use crate::ir::{Block, Function, Inst}; 30 use crate::timing; 31 use core::mem; 32 33 /// A basic block denoted by its enclosing Block and last instruction. 34 #[derive(Debug, PartialEq, Eq)] 35 pub struct BlockPredecessor { 36 /// Enclosing Block key. 37 pub block: Block, 38 /// Last instruction in the basic block. 39 pub inst: Inst, 40 } 41 42 impl BlockPredecessor { 43 /// Convenient method to construct new BlockPredecessor. 44 pub fn new(block: Block, inst: Inst) -> Self { 45 Self { block, inst } 46 } 47 } 48 49 /// A container for the successors and predecessors of some Block. 50 #[derive(Clone, Default)] 51 struct CFGNode { 52 /// Instructions that can branch or jump to this block. 53 /// 54 /// This maps branch instruction -> predecessor block which is redundant since the block containing 55 /// the branch instruction is available from the `layout.inst_block()` method. We store the 56 /// redundant information because: 57 /// 58 /// 1. Many `pred_iter()` consumers want the block anyway, so it is handily available. 59 /// 2. The `invalidate_block_successors()` may be called *after* branches have been removed from 60 /// their block, but we still need to remove them form the old block predecessor map. 61 /// 62 /// The redundant block stored here is always consistent with the CFG successor lists, even after 63 /// the IR has been edited. 64 pub predecessors: bforest::Map<Inst, Block>, 65 66 /// Set of blocks that are the targets of branches and jumps in this block. 67 /// The set is ordered by block number, indicated by the `()` comparator type. 68 pub successors: bforest::Set<Block>, 69 } 70 71 /// The Control Flow Graph maintains a mapping of blocks to their predecessors 72 /// and successors where predecessors are basic blocks and successors are 73 /// basic blocks. 74 pub struct ControlFlowGraph { 75 data: SecondaryMap<Block, CFGNode>, 76 pred_forest: bforest::MapForest<Inst, Block>, 77 succ_forest: bforest::SetForest<Block>, 78 valid: bool, 79 } 80 81 impl ControlFlowGraph { 82 /// Allocate a new blank control flow graph. 83 pub fn new() -> Self { 84 Self { 85 data: SecondaryMap::new(), 86 valid: false, 87 pred_forest: bforest::MapForest::new(), 88 succ_forest: bforest::SetForest::new(), 89 } 90 } 91 92 /// Clear all data structures in this control flow graph. 93 pub fn clear(&mut self) { 94 self.data.clear(); 95 self.pred_forest.clear(); 96 self.succ_forest.clear(); 97 self.valid = false; 98 } 99 100 /// Allocate and compute the control flow graph for `func`. 101 pub fn with_function(func: &Function) -> Self { 102 let mut cfg = Self::new(); 103 cfg.compute(func); 104 cfg 105 } 106 107 /// Compute the control flow graph of `func`. 108 /// 109 /// This will clear and overwrite any information already stored in this data structure. 110 pub fn compute(&mut self, func: &Function) { 111 let _tt = timing::flowgraph(); 112 self.clear(); 113 self.data.resize(func.dfg.num_blocks()); 114 115 for block in &func.layout { 116 self.compute_block(func, block); 117 } 118 119 self.valid = true; 120 } 121 122 fn compute_block(&mut self, func: &Function, block: Block) { 123 for inst in func.layout.block_likely_branches(block) { 124 match func.dfg.analyze_branch(inst) { 125 BranchInfo::SingleDest(dest) => { 126 self.add_edge(block, inst, dest.block(&func.dfg.value_lists)); 127 } 128 BranchInfo::Table(jt, dest) => { 129 self.add_edge(block, inst, dest); 130 131 for dest in func.jump_tables[jt].iter() { 132 self.add_edge(block, inst, *dest); 133 } 134 } 135 BranchInfo::NotABranch => {} 136 } 137 } 138 } 139 140 fn invalidate_block_successors(&mut self, block: Block) { 141 // Temporarily take ownership because we need mutable access to self.data inside the loop. 142 // Unfortunately borrowck cannot see that our mut accesses to predecessors don't alias 143 // our iteration over successors. 144 let mut successors = mem::replace(&mut self.data[block].successors, Default::default()); 145 for succ in successors.iter(&self.succ_forest) { 146 self.data[succ] 147 .predecessors 148 .retain(&mut self.pred_forest, |_, &mut e| e != block); 149 } 150 successors.clear(&mut self.succ_forest); 151 } 152 153 /// Recompute the control flow graph of `block`. 154 /// 155 /// This is for use after modifying instructions within a specific block. It recomputes all edges 156 /// from `block` while leaving edges to `block` intact. Its functionality a subset of that of the 157 /// more expensive `compute`, and should be used when we know we don't need to recompute the CFG 158 /// from scratch, but rather that our changes have been restricted to specific blocks. 159 pub fn recompute_block(&mut self, func: &Function, block: Block) { 160 debug_assert!(self.is_valid()); 161 self.invalidate_block_successors(block); 162 self.compute_block(func, block); 163 } 164 165 fn add_edge(&mut self, from: Block, from_inst: Inst, to: Block) { 166 self.data[from] 167 .successors 168 .insert(to, &mut self.succ_forest, &()); 169 self.data[to] 170 .predecessors 171 .insert(from_inst, from, &mut self.pred_forest, &()); 172 } 173 174 /// Get an iterator over the CFG predecessors to `block`. 175 pub fn pred_iter(&self, block: Block) -> PredIter { 176 PredIter(self.data[block].predecessors.iter(&self.pred_forest)) 177 } 178 179 /// Get an iterator over the CFG successors to `block`. 180 pub fn succ_iter(&self, block: Block) -> SuccIter { 181 debug_assert!(self.is_valid()); 182 self.data[block].successors.iter(&self.succ_forest) 183 } 184 185 /// Check if the CFG is in a valid state. 186 /// 187 /// Note that this doesn't perform any kind of validity checks. It simply checks if the 188 /// `compute()` method has been called since the last `clear()`. It does not check that the 189 /// CFG is consistent with the function. 190 pub fn is_valid(&self) -> bool { 191 self.valid 192 } 193 } 194 195 /// An iterator over block predecessors. The iterator type is `BlockPredecessor`. 196 /// 197 /// Each predecessor is an instruction that branches to the block. 198 pub struct PredIter<'a>(bforest::MapIter<'a, Inst, Block>); 199 200 impl<'a> Iterator for PredIter<'a> { 201 type Item = BlockPredecessor; 202 203 fn next(&mut self) -> Option<BlockPredecessor> { 204 self.0.next().map(|(i, e)| BlockPredecessor::new(e, i)) 205 } 206 } 207 208 /// An iterator over block successors. The iterator type is `Block`. 209 pub type SuccIter<'a> = bforest::SetIter<'a, Block>; 210 211 #[cfg(test)] 212 mod tests { 213 use super::*; 214 use crate::cursor::{Cursor, FuncCursor}; 215 use crate::ir::{types, Function, InstBuilder}; 216 use alloc::vec::Vec; 217 218 #[test] 219 fn empty() { 220 let func = Function::new(); 221 ControlFlowGraph::with_function(&func); 222 } 223 224 #[test] 225 fn no_predecessors() { 226 let mut func = Function::new(); 227 let block0 = func.dfg.make_block(); 228 let block1 = func.dfg.make_block(); 229 let block2 = func.dfg.make_block(); 230 func.layout.append_block(block0); 231 func.layout.append_block(block1); 232 func.layout.append_block(block2); 233 234 let cfg = ControlFlowGraph::with_function(&func); 235 236 let mut fun_blocks = func.layout.blocks(); 237 for block in func.layout.blocks() { 238 assert_eq!(block, fun_blocks.next().unwrap()); 239 assert_eq!(cfg.pred_iter(block).count(), 0); 240 assert_eq!(cfg.succ_iter(block).count(), 0); 241 } 242 } 243 244 #[test] 245 fn branches_and_jumps() { 246 let mut func = Function::new(); 247 let block0 = func.dfg.make_block(); 248 let cond = func.dfg.append_block_param(block0, types::I32); 249 let block1 = func.dfg.make_block(); 250 let block2 = func.dfg.make_block(); 251 252 let br_block0_block2; 253 let br_block1_block1; 254 let jmp_block0_block1; 255 let jmp_block1_block2; 256 257 { 258 let mut cur = FuncCursor::new(&mut func); 259 260 cur.insert_block(block0); 261 br_block0_block2 = cur.ins().brnz(cond, block2, &[]); 262 jmp_block0_block1 = cur.ins().jump(block1, &[]); 263 264 cur.insert_block(block1); 265 br_block1_block1 = cur.ins().brnz(cond, block1, &[]); 266 jmp_block1_block2 = cur.ins().jump(block2, &[]); 267 268 cur.insert_block(block2); 269 } 270 271 let mut cfg = ControlFlowGraph::with_function(&func); 272 273 { 274 let block0_predecessors = cfg.pred_iter(block0).collect::<Vec<_>>(); 275 let block1_predecessors = cfg.pred_iter(block1).collect::<Vec<_>>(); 276 let block2_predecessors = cfg.pred_iter(block2).collect::<Vec<_>>(); 277 278 let block0_successors = cfg.succ_iter(block0).collect::<Vec<_>>(); 279 let block1_successors = cfg.succ_iter(block1).collect::<Vec<_>>(); 280 let block2_successors = cfg.succ_iter(block2).collect::<Vec<_>>(); 281 282 assert_eq!(block0_predecessors.len(), 0); 283 assert_eq!(block1_predecessors.len(), 2); 284 assert_eq!(block2_predecessors.len(), 2); 285 286 assert_eq!( 287 block1_predecessors.contains(&BlockPredecessor::new(block0, jmp_block0_block1)), 288 true 289 ); 290 assert_eq!( 291 block1_predecessors.contains(&BlockPredecessor::new(block1, br_block1_block1)), 292 true 293 ); 294 assert_eq!( 295 block2_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block2)), 296 true 297 ); 298 assert_eq!( 299 block2_predecessors.contains(&BlockPredecessor::new(block1, jmp_block1_block2)), 300 true 301 ); 302 303 assert_eq!(block0_successors, [block1, block2]); 304 assert_eq!(block1_successors, [block1, block2]); 305 assert_eq!(block2_successors, []); 306 } 307 308 // Change some instructions and recompute block0 309 func.dfg.replace(br_block0_block2).brnz(cond, block1, &[]); 310 func.dfg.replace(jmp_block0_block1).return_(&[]); 311 cfg.recompute_block(&mut func, block0); 312 let br_block0_block1 = br_block0_block2; 313 314 { 315 let block0_predecessors = cfg.pred_iter(block0).collect::<Vec<_>>(); 316 let block1_predecessors = cfg.pred_iter(block1).collect::<Vec<_>>(); 317 let block2_predecessors = cfg.pred_iter(block2).collect::<Vec<_>>(); 318 319 let block0_successors = cfg.succ_iter(block0); 320 let block1_successors = cfg.succ_iter(block1); 321 let block2_successors = cfg.succ_iter(block2); 322 323 assert_eq!(block0_predecessors.len(), 0); 324 assert_eq!(block1_predecessors.len(), 2); 325 assert_eq!(block2_predecessors.len(), 1); 326 327 assert_eq!( 328 block1_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block1)), 329 true 330 ); 331 assert_eq!( 332 block1_predecessors.contains(&BlockPredecessor::new(block1, br_block1_block1)), 333 true 334 ); 335 assert_eq!( 336 block2_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block2)), 337 false 338 ); 339 assert_eq!( 340 block2_predecessors.contains(&BlockPredecessor::new(block1, jmp_block1_block2)), 341 true 342 ); 343 344 assert_eq!(block0_successors.collect::<Vec<_>>(), [block1]); 345 assert_eq!(block1_successors.collect::<Vec<_>>(), [block1, block2]); 346 assert_eq!(block2_successors.collect::<Vec<_>>(), []); 347 } 348 } 349 } 350