1 //! Computation of basic block order in emitted code. 2 //! 3 //! This module handles the translation from CLIF BBs to VCode BBs. 4 //! 5 //! The basic idea is that we compute a sequence of "lowered blocks" that 6 //! correspond to one or more blocks in the graph: (CLIF CFG) `union` (implicit 7 //! block on *every* edge). Conceptually, the lowering pipeline wants to insert 8 //! moves for phi-nodes on every block-to-block transfer; these blocks always 9 //! conceptually exist, but may be merged with an "original" CLIF block (and 10 //! hence not actually exist; this is equivalent to inserting the blocks only on 11 //! critical edges). 12 //! 13 //! In other words, starting from a CFG like this (where each "CLIF block" and 14 //! "(edge N->M)" is a separate basic block): 15 //! 16 //! ```plain 17 //! 18 //! CLIF block 0 19 //! / \ 20 //! (edge 0->1) (edge 0->2) 21 //! | | 22 //! CLIF block 1 CLIF block 2 23 //! \ / 24 //! (edge 1->3) (edge 2->3) 25 //! \ / 26 //! CLIF block 3 27 //! ``` 28 //! 29 //! We can produce a CFG of lowered blocks like so: 30 //! 31 //! ```plain 32 //! +--------------+ 33 //! | CLIF block 0 | 34 //! +--------------+ 35 //! / \ 36 //! +--------------+ +--------------+ 37 //! | (edge 0->1) | | (edge 0->2) | 38 //! | CLIF block 1 | | CLIF block 2 | 39 //! | (edge 1->3) | | (edge 2->3) | 40 //! +--------------+ +--------------+ 41 //! \ / 42 //! \ / 43 //! +------------+ 44 //! |CLIF block 3| 45 //! +------------+ 46 //! ``` 47 //! 48 //! Each `LoweredBlock` names just an original CLIF block, or just an edge block. 49 //! 50 //! To compute this lowering, we do a DFS over the CLIF-plus-edge-block graph 51 //! (never actually materialized, just defined by a "successors" function), and 52 //! compute the reverse postorder. 53 //! 54 //! This algorithm isn't perfect w.r.t. generated code quality: we don't, for 55 //! example, consider any information about whether edge blocks will actually 56 //! have content, because this computation happens as part of lowering *before* 57 //! regalloc, and regalloc may or may not insert moves/spills/reloads on any 58 //! particular edge. But it works relatively well and is conceptually simple. 59 //! Furthermore, the [MachBuffer] machine-code sink performs final peephole-like 60 //! branch editing that in practice elides empty blocks and simplifies some of 61 //! the other redundancies that this scheme produces. 62 63 use crate::dominator_tree::DominatorTree; 64 use crate::entity::SecondaryMap; 65 use crate::inst_predicates::visit_block_succs; 66 use crate::ir::{Block, Function, Inst, Opcode}; 67 use crate::{machinst::*, trace}; 68 use rustc_hash::{FxHashMap, FxHashSet}; 69 70 /// Mapping from CLIF BBs to VCode BBs. 71 #[derive(Debug)] 72 pub struct BlockLoweringOrder { 73 /// Lowered blocks, in BlockIndex order. Each block is some combination of 74 /// (i) a CLIF block, and (ii) inserted crit-edge blocks before or after; 75 /// see [LoweredBlock] for details. 76 lowered_order: Vec<LoweredBlock>, 77 /// BlockIndex values for successors for all lowered blocks, indexing `lowered_order`. 78 lowered_succ_indices: Vec<BlockIndex>, 79 /// Ranges in `lowered_succ_indices` giving the successor lists for each lowered 80 /// block. Indexed by lowering-order index (`BlockIndex`). 81 lowered_succ_ranges: Vec<(Option<Inst>, std::ops::Range<usize>)>, 82 /// Cold blocks. These blocks are not reordered in the 83 /// `lowered_order` above; the lowered order must respect RPO 84 /// (uses after defs) in order for lowering to be 85 /// correct. Instead, this set is used to provide `is_cold()`, 86 /// which is used by VCode emission to sink the blocks at the last 87 /// moment (when we actually emit bytes into the MachBuffer). 88 cold_blocks: FxHashSet<BlockIndex>, 89 /// Lowered blocks that are indirect branch targets. 90 indirect_branch_targets: FxHashSet<BlockIndex>, 91 } 92 93 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] 94 pub enum LoweredBlock { 95 /// Block in original CLIF. 96 Orig { 97 /// Original CLIF block. 98 block: Block, 99 }, 100 101 /// Critical edge between two CLIF blocks. 102 CriticalEdge { 103 /// The predecessor block. 104 pred: Block, 105 106 /// The successor block. 107 succ: Block, 108 109 /// The index of this branch in the successor edges from `pred`, following the same 110 /// indexing order as `inst_predicates::visit_block_succs`. This is used to distinguish 111 /// multiple edges between the same CLIF blocks. 112 succ_idx: u32, 113 }, 114 } 115 116 impl LoweredBlock { 117 /// Unwrap an `Orig` block. 118 pub fn orig_block(&self) -> Option<Block> { 119 match self { 120 &LoweredBlock::Orig { block } => Some(block), 121 &LoweredBlock::CriticalEdge { .. } => None, 122 } 123 } 124 125 /// The associated in-edge predecessor, if this is a critical edge. 126 #[cfg(test)] 127 pub fn in_edge(&self) -> Option<Block> { 128 match self { 129 &LoweredBlock::CriticalEdge { pred, .. } => Some(pred), 130 &LoweredBlock::Orig { .. } => None, 131 } 132 } 133 134 /// The associated out-edge successor, if this is a critical edge. 135 #[cfg(test)] 136 pub fn out_edge(&self) -> Option<Block> { 137 match self { 138 &LoweredBlock::CriticalEdge { succ, .. } => Some(succ), 139 &LoweredBlock::Orig { .. } => None, 140 } 141 } 142 } 143 144 impl BlockLoweringOrder { 145 /// Compute and return a lowered block order for `f`. 146 pub fn new( 147 f: &Function, 148 domtree: &DominatorTree, 149 ctrl_plane: &mut ControlPlane, 150 ) -> BlockLoweringOrder { 151 trace!("BlockLoweringOrder: function body {:?}", f); 152 153 // Step 1: compute the in-edge and out-edge count of every block. 154 let mut block_in_count = SecondaryMap::with_default(0); 155 let mut block_out_count = SecondaryMap::with_default(0); 156 157 // Block successors are stored as `LoweredBlocks` to simplify the construction of 158 // `lowered_succs` in the final result. Initially, all entries are `Orig` values, and are 159 // updated to be `CriticalEdge` when those cases are identified in step 2 below. 160 let mut block_succs: SmallVec<[LoweredBlock; 128]> = SmallVec::new(); 161 let mut block_succ_range = SecondaryMap::with_default(0..0); 162 163 let mut indirect_branch_target_clif_blocks = FxHashSet::default(); 164 165 for block in f.layout.blocks() { 166 let start = block_succs.len(); 167 visit_block_succs(f, block, |_, succ, from_table| { 168 block_out_count[block] += 1; 169 block_in_count[succ] += 1; 170 block_succs.push(LoweredBlock::Orig { block: succ }); 171 172 if from_table { 173 indirect_branch_target_clif_blocks.insert(succ); 174 } 175 }); 176 177 // Ensure that blocks terminated by br_table instructions with an empty jump table are 178 // still treated like conditional blocks from the point of view of critical edge 179 // splitting. 180 if let Some(inst) = f.layout.last_inst(block) { 181 if Opcode::BrTable == f.dfg.insts[inst].opcode() { 182 block_out_count[block] = block_out_count[block].max(2); 183 } 184 } 185 186 let end = block_succs.len(); 187 block_succ_range[block] = start..end; 188 } 189 190 // Step 2: walk the postorder from the domtree in reverse to produce our desired node 191 // lowering order, identifying critical edges to split along the way. 192 193 let mut lowered_order = Vec::new(); 194 195 for &block in domtree.cfg_postorder().iter().rev() { 196 lowered_order.push(LoweredBlock::Orig { block }); 197 198 if block_out_count[block] > 1 { 199 let range = block_succ_range[block].clone(); 200 201 // If chaos-mode is enabled in the control plane, iterate over 202 // the successors in an arbtirary order, which should have no 203 // impact on correctness. The order of the blocks is generally 204 // relevant: Uses must be seen before defs for dead-code 205 // elimination. 206 let succs = ctrl_plane.shuffled(block_succs[range].iter_mut().enumerate()); 207 208 for (succ_ix, lb) in succs { 209 let succ = lb.orig_block().unwrap(); 210 if block_in_count[succ] > 1 { 211 // Mutate the successor to be a critical edge, as `block` has multiple 212 // edges leaving it, and `succ` has multiple edges entering it. 213 *lb = LoweredBlock::CriticalEdge { 214 pred: block, 215 succ, 216 succ_idx: succ_ix as u32, 217 }; 218 lowered_order.push(*lb); 219 } 220 } 221 } 222 } 223 224 let lb_to_bindex = FxHashMap::from_iter( 225 lowered_order 226 .iter() 227 .enumerate() 228 .map(|(i, &lb)| (lb, BlockIndex::new(i))), 229 ); 230 231 // Step 3: build the successor tables given the lowering order. We can't perform this step 232 // during the creation of `lowering_order`, as we need `lb_to_bindex` to be fully populated 233 // first. 234 let mut lowered_succ_indices = Vec::new(); 235 let mut cold_blocks = FxHashSet::default(); 236 let mut indirect_branch_targets = FxHashSet::default(); 237 let lowered_succ_ranges = 238 Vec::from_iter(lowered_order.iter().enumerate().map(|(ix, lb)| { 239 let bindex = BlockIndex::new(ix); 240 let start = lowered_succ_indices.len(); 241 let opt_inst = match lb { 242 // Block successors are pulled directly over, as they'll have been mutated when 243 // determining the block order already. 244 &LoweredBlock::Orig { block } => { 245 let range = block_succ_range[block].clone(); 246 lowered_succ_indices 247 .extend(block_succs[range].iter().map(|lb| lb_to_bindex[lb])); 248 249 if f.layout.is_cold(block) { 250 cold_blocks.insert(bindex); 251 } 252 253 if indirect_branch_target_clif_blocks.contains(&block) { 254 indirect_branch_targets.insert(bindex); 255 } 256 257 let last = f.layout.last_inst(block).unwrap(); 258 let opcode = f.dfg.insts[last].opcode(); 259 260 assert!(opcode.is_terminator()); 261 262 opcode.is_branch().then_some(last) 263 } 264 265 // Critical edges won't have successor information in block_succ_range, but 266 // they only have a single known successor to record anyway. 267 &LoweredBlock::CriticalEdge { succ, .. } => { 268 let succ_index = lb_to_bindex[&LoweredBlock::Orig { block: succ }]; 269 lowered_succ_indices.push(succ_index); 270 271 // Edges inherit indirect branch and cold block metadata from their 272 // successor. 273 274 if f.layout.is_cold(succ) { 275 cold_blocks.insert(bindex); 276 } 277 278 if indirect_branch_target_clif_blocks.contains(&succ) { 279 indirect_branch_targets.insert(bindex); 280 } 281 282 None 283 } 284 }; 285 let end = lowered_succ_indices.len(); 286 (opt_inst, start..end) 287 })); 288 289 let result = BlockLoweringOrder { 290 lowered_order, 291 lowered_succ_indices, 292 lowered_succ_ranges, 293 cold_blocks, 294 indirect_branch_targets, 295 }; 296 297 trace!("BlockLoweringOrder: {:#?}", result); 298 result 299 } 300 301 /// Get the lowered order of blocks. 302 pub fn lowered_order(&self) -> &[LoweredBlock] { 303 &self.lowered_order[..] 304 } 305 306 /// Get the successor indices for a lowered block. 307 pub fn succ_indices(&self, block: BlockIndex) -> (Option<Inst>, &[BlockIndex]) { 308 let (opt_inst, range) = &self.lowered_succ_ranges[block.index()]; 309 (opt_inst.clone(), &self.lowered_succ_indices[range.clone()]) 310 } 311 312 /// Determine whether the given lowered-block index is cold. 313 pub fn is_cold(&self, block: BlockIndex) -> bool { 314 self.cold_blocks.contains(&block) 315 } 316 317 /// Determine whether the given lowered block index is an indirect branch 318 /// target. 319 pub fn is_indirect_branch_target(&self, block: BlockIndex) -> bool { 320 self.indirect_branch_targets.contains(&block) 321 } 322 } 323 324 #[cfg(test)] 325 mod test { 326 use super::*; 327 use crate::cursor::{Cursor, FuncCursor}; 328 use crate::flowgraph::ControlFlowGraph; 329 use crate::ir::types::*; 330 use crate::ir::UserFuncName; 331 use crate::ir::{AbiParam, InstBuilder, Signature}; 332 use crate::isa::CallConv; 333 334 fn build_test_func(n_blocks: usize, edges: &[(usize, usize)]) -> BlockLoweringOrder { 335 assert!(n_blocks > 0); 336 337 let name = UserFuncName::testcase("test0"); 338 let mut sig = Signature::new(CallConv::SystemV); 339 sig.params.push(AbiParam::new(I32)); 340 let mut func = Function::with_name_signature(name, sig); 341 let blocks = (0..n_blocks) 342 .map(|i| { 343 let bb = func.dfg.make_block(); 344 assert!(bb.as_u32() == i as u32); 345 bb 346 }) 347 .collect::<Vec<_>>(); 348 349 let arg0 = func.dfg.append_block_param(blocks[0], I32); 350 351 let mut pos = FuncCursor::new(&mut func); 352 353 let mut edge = 0; 354 for i in 0..n_blocks { 355 pos.insert_block(blocks[i]); 356 let mut succs = vec![]; 357 while edge < edges.len() && edges[edge].0 == i { 358 succs.push(edges[edge].1); 359 edge += 1; 360 } 361 if succs.len() == 0 { 362 pos.ins().return_(&[arg0]); 363 } else if succs.len() == 1 { 364 pos.ins().jump(blocks[succs[0]], &[]); 365 } else if succs.len() == 2 { 366 pos.ins() 367 .brif(arg0, blocks[succs[0]], &[], blocks[succs[1]], &[]); 368 } else { 369 panic!("Too many successors"); 370 } 371 } 372 373 let mut cfg = ControlFlowGraph::new(); 374 cfg.compute(&func); 375 let dom_tree = DominatorTree::with_function(&func, &cfg); 376 377 BlockLoweringOrder::new(&func, &dom_tree, &mut Default::default()) 378 } 379 380 #[test] 381 fn test_blockorder_diamond() { 382 let order = build_test_func(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]); 383 384 // This test case doesn't need to introduce any critical edges, as all regalloc allocations 385 // can sit on either the entry or exit of blocks 1 and 2. 386 assert_eq!(order.lowered_order.len(), 4); 387 } 388 389 #[test] 390 fn test_blockorder_critedge() { 391 // 0 392 // / \ 393 // 1 2 394 // / \ \ 395 // 3 4 | 396 // |\ _|____| 397 // | \/ | 398 // | /\ | 399 // 5 6 400 // 401 // (3 -> 5, and 3 -> 6 are critical edges and must be split) 402 // 403 let order = build_test_func( 404 7, 405 &[ 406 (0, 1), 407 (0, 2), 408 (1, 3), 409 (1, 4), 410 (2, 5), 411 (3, 5), 412 (3, 6), 413 (4, 6), 414 ], 415 ); 416 417 assert_eq!(order.lowered_order.len(), 9); 418 println!("ordered = {:?}", order.lowered_order); 419 420 // block 0 421 assert_eq!(order.lowered_order[0].orig_block().unwrap().as_u32(), 0); 422 assert!(order.lowered_order[0].in_edge().is_none()); 423 assert!(order.lowered_order[0].out_edge().is_none()); 424 425 // block 2 426 assert_eq!(order.lowered_order[1].orig_block().unwrap().as_u32(), 2); 427 assert!(order.lowered_order[1].in_edge().is_none()); 428 assert!(order.lowered_order[1].out_edge().is_none()); 429 430 // block 1 431 assert_eq!(order.lowered_order[2].orig_block().unwrap().as_u32(), 1); 432 assert!(order.lowered_order[2].in_edge().is_none()); 433 assert!(order.lowered_order[2].out_edge().is_none()); 434 435 // block 4 436 assert_eq!(order.lowered_order[3].orig_block().unwrap().as_u32(), 4); 437 assert!(order.lowered_order[3].in_edge().is_none()); 438 assert!(order.lowered_order[3].out_edge().is_none()); 439 440 // block 3 441 assert_eq!(order.lowered_order[4].orig_block().unwrap().as_u32(), 3); 442 assert!(order.lowered_order[4].in_edge().is_none()); 443 assert!(order.lowered_order[4].out_edge().is_none()); 444 445 // critical edge 3 -> 5 446 assert!(order.lowered_order[5].orig_block().is_none()); 447 assert_eq!(order.lowered_order[5].in_edge().unwrap().as_u32(), 3); 448 assert_eq!(order.lowered_order[5].out_edge().unwrap().as_u32(), 5); 449 450 // critical edge 3 -> 6 451 assert!(order.lowered_order[6].orig_block().is_none()); 452 assert_eq!(order.lowered_order[6].in_edge().unwrap().as_u32(), 3); 453 assert_eq!(order.lowered_order[6].out_edge().unwrap().as_u32(), 6); 454 455 // block 6 456 assert_eq!(order.lowered_order[7].orig_block().unwrap().as_u32(), 6); 457 assert!(order.lowered_order[7].in_edge().is_none()); 458 assert!(order.lowered_order[7].out_edge().is_none()); 459 460 // block 5 461 assert_eq!(order.lowered_order[8].orig_block().unwrap().as_u32(), 5); 462 assert!(order.lowered_order[8].in_edge().is_none()); 463 assert!(order.lowered_order[8].out_edge().is_none()); 464 } 465 } 466