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. new(block: Block, inst: Inst) -> Self44 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. new() -> Self83 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. clear(&mut self)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`. with_function(func: &Function) -> Self101 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. compute(&mut self, func: &Function)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 compute_block(&mut self, func: &Function, block: Block)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); 127 } 128 BranchInfo::Table(jt, dest) => { 129 if let Some(dest) = dest { 130 self.add_edge(block, inst, dest); 131 } 132 for dest in func.jump_tables[jt].iter() { 133 self.add_edge(block, inst, *dest); 134 } 135 } 136 BranchInfo::NotABranch => {} 137 } 138 } 139 } 140 invalidate_block_successors(&mut self, block: Block)141 fn invalidate_block_successors(&mut self, block: Block) { 142 // Temporarily take ownership because we need mutable access to self.data inside the loop. 143 // Unfortunately borrowck cannot see that our mut accesses to predecessors don't alias 144 // our iteration over successors. 145 let mut successors = mem::replace(&mut self.data[block].successors, Default::default()); 146 for succ in successors.iter(&self.succ_forest) { 147 self.data[succ] 148 .predecessors 149 .retain(&mut self.pred_forest, |_, &mut e| e != block); 150 } 151 successors.clear(&mut self.succ_forest); 152 } 153 154 /// Recompute the control flow graph of `block`. 155 /// 156 /// This is for use after modifying instructions within a specific block. It recomputes all edges 157 /// from `block` while leaving edges to `block` intact. Its functionality a subset of that of the 158 /// more expensive `compute`, and should be used when we know we don't need to recompute the CFG 159 /// from scratch, but rather that our changes have been restricted to specific blocks. recompute_block(&mut self, func: &Function, block: Block)160 pub fn recompute_block(&mut self, func: &Function, block: Block) { 161 debug_assert!(self.is_valid()); 162 self.invalidate_block_successors(block); 163 self.compute_block(func, block); 164 } 165 add_edge(&mut self, from: Block, from_inst: Inst, to: Block)166 fn add_edge(&mut self, from: Block, from_inst: Inst, to: Block) { 167 self.data[from] 168 .successors 169 .insert(to, &mut self.succ_forest, &()); 170 self.data[to] 171 .predecessors 172 .insert(from_inst, from, &mut self.pred_forest, &()); 173 } 174 175 /// Get an iterator over the CFG predecessors to `block`. pred_iter(&self, block: Block) -> PredIter176 pub fn pred_iter(&self, block: Block) -> PredIter { 177 PredIter(self.data[block].predecessors.iter(&self.pred_forest)) 178 } 179 180 /// Get an iterator over the CFG successors to `block`. succ_iter(&self, block: Block) -> SuccIter181 pub fn succ_iter(&self, block: Block) -> SuccIter { 182 debug_assert!(self.is_valid()); 183 self.data[block].successors.iter(&self.succ_forest) 184 } 185 186 /// Check if the CFG is in a valid state. 187 /// 188 /// Note that this doesn't perform any kind of validity checks. It simply checks if the 189 /// `compute()` method has been called since the last `clear()`. It does not check that the 190 /// CFG is consistent with the function. is_valid(&self) -> bool191 pub fn is_valid(&self) -> bool { 192 self.valid 193 } 194 } 195 196 /// An iterator over block predecessors. The iterator type is `BlockPredecessor`. 197 /// 198 /// Each predecessor is an instruction that branches to the block. 199 pub struct PredIter<'a>(bforest::MapIter<'a, Inst, Block>); 200 201 impl<'a> Iterator for PredIter<'a> { 202 type Item = BlockPredecessor; 203 next(&mut self) -> Option<BlockPredecessor>204 fn next(&mut self) -> Option<BlockPredecessor> { 205 self.0.next().map(|(i, e)| BlockPredecessor::new(e, i)) 206 } 207 } 208 209 /// An iterator over block successors. The iterator type is `Block`. 210 pub type SuccIter<'a> = bforest::SetIter<'a, Block>; 211 212 #[cfg(test)] 213 mod tests { 214 use super::*; 215 use crate::cursor::{Cursor, FuncCursor}; 216 use crate::ir::{types, Function, InstBuilder}; 217 use alloc::vec::Vec; 218 219 #[test] empty()220 fn empty() { 221 let func = Function::new(); 222 ControlFlowGraph::with_function(&func); 223 } 224 225 #[test] no_predecessors()226 fn no_predecessors() { 227 let mut func = Function::new(); 228 let block0 = func.dfg.make_block(); 229 let block1 = func.dfg.make_block(); 230 let block2 = func.dfg.make_block(); 231 func.layout.append_block(block0); 232 func.layout.append_block(block1); 233 func.layout.append_block(block2); 234 235 let cfg = ControlFlowGraph::with_function(&func); 236 237 let mut fun_blocks = func.layout.blocks(); 238 for block in func.layout.blocks() { 239 assert_eq!(block, fun_blocks.next().unwrap()); 240 assert_eq!(cfg.pred_iter(block).count(), 0); 241 assert_eq!(cfg.succ_iter(block).count(), 0); 242 } 243 } 244 245 #[test] branches_and_jumps()246 fn branches_and_jumps() { 247 let mut func = Function::new(); 248 let block0 = func.dfg.make_block(); 249 let cond = func.dfg.append_block_param(block0, types::I32); 250 let block1 = func.dfg.make_block(); 251 let block2 = func.dfg.make_block(); 252 253 let br_block0_block2; 254 let br_block1_block1; 255 let jmp_block0_block1; 256 let jmp_block1_block2; 257 258 { 259 let mut cur = FuncCursor::new(&mut func); 260 261 cur.insert_block(block0); 262 br_block0_block2 = cur.ins().brnz(cond, block2, &[]); 263 jmp_block0_block1 = cur.ins().jump(block1, &[]); 264 265 cur.insert_block(block1); 266 br_block1_block1 = cur.ins().brnz(cond, block1, &[]); 267 jmp_block1_block2 = cur.ins().jump(block2, &[]); 268 269 cur.insert_block(block2); 270 } 271 272 let mut cfg = ControlFlowGraph::with_function(&func); 273 274 { 275 let block0_predecessors = cfg.pred_iter(block0).collect::<Vec<_>>(); 276 let block1_predecessors = cfg.pred_iter(block1).collect::<Vec<_>>(); 277 let block2_predecessors = cfg.pred_iter(block2).collect::<Vec<_>>(); 278 279 let block0_successors = cfg.succ_iter(block0).collect::<Vec<_>>(); 280 let block1_successors = cfg.succ_iter(block1).collect::<Vec<_>>(); 281 let block2_successors = cfg.succ_iter(block2).collect::<Vec<_>>(); 282 283 assert_eq!(block0_predecessors.len(), 0); 284 assert_eq!(block1_predecessors.len(), 2); 285 assert_eq!(block2_predecessors.len(), 2); 286 287 assert_eq!( 288 block1_predecessors.contains(&BlockPredecessor::new(block0, jmp_block0_block1)), 289 true 290 ); 291 assert_eq!( 292 block1_predecessors.contains(&BlockPredecessor::new(block1, br_block1_block1)), 293 true 294 ); 295 assert_eq!( 296 block2_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block2)), 297 true 298 ); 299 assert_eq!( 300 block2_predecessors.contains(&BlockPredecessor::new(block1, jmp_block1_block2)), 301 true 302 ); 303 304 assert_eq!(block0_successors, [block1, block2]); 305 assert_eq!(block1_successors, [block1, block2]); 306 assert_eq!(block2_successors, []); 307 } 308 309 // Change some instructions and recompute block0 310 func.dfg.replace(br_block0_block2).brnz(cond, block1, &[]); 311 func.dfg.replace(jmp_block0_block1).return_(&[]); 312 cfg.recompute_block(&mut func, block0); 313 let br_block0_block1 = br_block0_block2; 314 315 { 316 let block0_predecessors = cfg.pred_iter(block0).collect::<Vec<_>>(); 317 let block1_predecessors = cfg.pred_iter(block1).collect::<Vec<_>>(); 318 let block2_predecessors = cfg.pred_iter(block2).collect::<Vec<_>>(); 319 320 let block0_successors = cfg.succ_iter(block0); 321 let block1_successors = cfg.succ_iter(block1); 322 let block2_successors = cfg.succ_iter(block2); 323 324 assert_eq!(block0_predecessors.len(), 0); 325 assert_eq!(block1_predecessors.len(), 2); 326 assert_eq!(block2_predecessors.len(), 1); 327 328 assert_eq!( 329 block1_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block1)), 330 true 331 ); 332 assert_eq!( 333 block1_predecessors.contains(&BlockPredecessor::new(block1, br_block1_block1)), 334 true 335 ); 336 assert_eq!( 337 block2_predecessors.contains(&BlockPredecessor::new(block0, br_block0_block2)), 338 false 339 ); 340 assert_eq!( 341 block2_predecessors.contains(&BlockPredecessor::new(block1, jmp_block1_block2)), 342 true 343 ); 344 345 assert_eq!(block0_successors.collect::<Vec<_>>(), [block1]); 346 assert_eq!(block1_successors.collect::<Vec<_>>(), [block1, block2]); 347 assert_eq!(block2_successors.collect::<Vec<_>>(), []); 348 } 349 } 350 } 351