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 pub fn out_edge(&self) -> Option<Block> { 136 match self { 137 &LoweredBlock::CriticalEdge { succ, .. } => Some(succ), 138 &LoweredBlock::Orig { .. } => None, 139 } 140 } 141 } 142 143 impl BlockLoweringOrder { 144 /// Compute and return a lowered block order for `f`. 145 pub fn new( 146 f: &Function, 147 domtree: &DominatorTree, 148 ctrl_plane: &mut ControlPlane, 149 ) -> BlockLoweringOrder { 150 trace!("BlockLoweringOrder: function body {:?}", f); 151 152 // Step 1: compute the in-edge and out-edge count of every block. 153 let mut block_in_count = SecondaryMap::with_default(0); 154 let mut block_out_count = SecondaryMap::with_default(0); 155 156 // Block successors are stored as `LoweredBlocks` to simplify the construction of 157 // `lowered_succs` in the final result. Initially, all entries are `Orig` values, and are 158 // updated to be `CriticalEdge` when those cases are identified in step 2 below. 159 let mut block_succs: SmallVec<[LoweredBlock; 128]> = SmallVec::new(); 160 let mut block_succ_range = SecondaryMap::with_default(0..0); 161 162 let mut indirect_branch_target_clif_blocks = FxHashSet::default(); 163 164 for block in f.layout.blocks() { 165 let start = block_succs.len(); 166 visit_block_succs(f, block, |_, succ, from_table| { 167 block_out_count[block] += 1; 168 block_in_count[succ] += 1; 169 block_succs.push(LoweredBlock::Orig { block: succ }); 170 171 if from_table { 172 indirect_branch_target_clif_blocks.insert(succ); 173 } 174 }); 175 176 // Ensure that blocks terminated by br_table instructions 177 // with an empty jump table are still treated like 178 // conditional blocks from the point of view of critical 179 // edge splitting. Also do the same for TryCall and 180 // TryCallIndirect: we cannot have edge moves before the 181 // branch, even if they have empty handler tables and thus 182 // would otherwise have only one successor. 183 if let Some(inst) = f.layout.last_inst(block) { 184 match f.dfg.insts[inst].opcode() { 185 Opcode::BrTable | Opcode::TryCall | Opcode::TryCallIndirect => { 186 block_out_count[block] = block_out_count[block].max(2); 187 } 188 _ => {} 189 } 190 } 191 192 let end = block_succs.len(); 193 block_succ_range[block] = start..end; 194 } 195 196 // Step 2: walk the postorder from the domtree in reverse to produce our desired node 197 // lowering order, identifying critical edges to split along the way. 198 199 let mut lowered_order = Vec::new(); 200 201 for &block in domtree.cfg_rpo() { 202 lowered_order.push(LoweredBlock::Orig { block }); 203 204 if block_out_count[block] > 1 { 205 let range = block_succ_range[block].clone(); 206 207 // If chaos-mode is enabled in the control plane, iterate over 208 // the successors in an arbitrary order, which should have no 209 // impact on correctness. The order of the blocks is generally 210 // relevant: Uses must be seen before defs for dead-code 211 // elimination. 212 let succs = ctrl_plane.shuffled(block_succs[range].iter_mut().enumerate()); 213 214 for (succ_ix, lb) in succs { 215 let succ = lb.orig_block().unwrap(); 216 if block_in_count[succ] > 1 { 217 // Mutate the successor to be a critical edge, as `block` has multiple 218 // edges leaving it, and `succ` has multiple edges entering it. 219 *lb = LoweredBlock::CriticalEdge { 220 pred: block, 221 succ, 222 succ_idx: succ_ix as u32, 223 }; 224 lowered_order.push(*lb); 225 } 226 } 227 } 228 } 229 230 let lb_to_bindex = FxHashMap::from_iter( 231 lowered_order 232 .iter() 233 .enumerate() 234 .map(|(i, &lb)| (lb, BlockIndex::new(i))), 235 ); 236 237 // Step 3: build the successor tables given the lowering order. We can't perform this step 238 // during the creation of `lowering_order`, as we need `lb_to_bindex` to be fully populated 239 // first. 240 let mut lowered_succ_indices = Vec::new(); 241 let mut cold_blocks = FxHashSet::default(); 242 let mut indirect_branch_targets = FxHashSet::default(); 243 let lowered_succ_ranges = 244 Vec::from_iter(lowered_order.iter().enumerate().map(|(ix, lb)| { 245 let bindex = BlockIndex::new(ix); 246 let start = lowered_succ_indices.len(); 247 let opt_inst = match lb { 248 // Block successors are pulled directly over, as they'll have been mutated when 249 // determining the block order already. 250 &LoweredBlock::Orig { block } => { 251 let range = block_succ_range[block].clone(); 252 lowered_succ_indices 253 .extend(block_succs[range].iter().map(|lb| lb_to_bindex[lb])); 254 255 if f.layout.is_cold(block) { 256 cold_blocks.insert(bindex); 257 } 258 259 if indirect_branch_target_clif_blocks.contains(&block) { 260 indirect_branch_targets.insert(bindex); 261 } 262 263 let last = f.layout.last_inst(block).unwrap(); 264 let opcode = f.dfg.insts[last].opcode(); 265 266 assert!(opcode.is_terminator()); 267 268 opcode.is_branch().then_some(last) 269 } 270 271 // Critical edges won't have successor information in block_succ_range, but 272 // they only have a single known successor to record anyway. 273 &LoweredBlock::CriticalEdge { succ, .. } => { 274 let succ_index = lb_to_bindex[&LoweredBlock::Orig { block: succ }]; 275 lowered_succ_indices.push(succ_index); 276 277 // Edges inherit indirect branch and cold block metadata from their 278 // successor. 279 280 if f.layout.is_cold(succ) { 281 cold_blocks.insert(bindex); 282 } 283 284 if indirect_branch_target_clif_blocks.contains(&succ) { 285 indirect_branch_targets.insert(bindex); 286 } 287 288 None 289 } 290 }; 291 let end = lowered_succ_indices.len(); 292 (opt_inst, start..end) 293 })); 294 295 let result = BlockLoweringOrder { 296 lowered_order, 297 lowered_succ_indices, 298 lowered_succ_ranges, 299 cold_blocks, 300 indirect_branch_targets, 301 }; 302 303 trace!("BlockLoweringOrder: {:#?}", result); 304 result 305 } 306 307 /// Get the lowered order of blocks. 308 pub fn lowered_order(&self) -> &[LoweredBlock] { 309 &self.lowered_order[..] 310 } 311 312 /// Get the successor indices for a lowered block. 313 pub fn succ_indices(&self, block: BlockIndex) -> (Option<Inst>, &[BlockIndex]) { 314 let (opt_inst, range) = &self.lowered_succ_ranges[block.index()]; 315 (*opt_inst, &self.lowered_succ_indices[range.clone()]) 316 } 317 318 /// Determine whether the given lowered-block index is cold. 319 pub fn is_cold(&self, block: BlockIndex) -> bool { 320 self.cold_blocks.contains(&block) 321 } 322 323 /// Determine whether the given lowered block index is an indirect branch 324 /// target. 325 pub fn is_indirect_branch_target(&self, block: BlockIndex) -> bool { 326 self.indirect_branch_targets.contains(&block) 327 } 328 } 329 330 #[cfg(test)] 331 mod test { 332 use super::*; 333 use crate::cursor::{Cursor, FuncCursor}; 334 use crate::flowgraph::ControlFlowGraph; 335 use crate::ir::UserFuncName; 336 use crate::ir::types::*; 337 use crate::ir::{AbiParam, InstBuilder, Signature}; 338 use crate::isa::CallConv; 339 340 fn build_test_func(n_blocks: usize, edges: &[(usize, usize)]) -> BlockLoweringOrder { 341 assert!(n_blocks > 0); 342 343 let name = UserFuncName::testcase("test0"); 344 let mut sig = Signature::new(CallConv::SystemV); 345 sig.params.push(AbiParam::new(I32)); 346 let mut func = Function::with_name_signature(name, sig); 347 let blocks = (0..n_blocks) 348 .map(|i| { 349 let bb = func.dfg.make_block(); 350 assert!(bb.as_u32() == i as u32); 351 bb 352 }) 353 .collect::<Vec<_>>(); 354 355 let arg0 = func.dfg.append_block_param(blocks[0], I32); 356 357 let mut pos = FuncCursor::new(&mut func); 358 359 let mut edge = 0; 360 for i in 0..n_blocks { 361 pos.insert_block(blocks[i]); 362 let mut succs = vec![]; 363 while edge < edges.len() && edges[edge].0 == i { 364 succs.push(edges[edge].1); 365 edge += 1; 366 } 367 if succs.len() == 0 { 368 pos.ins().return_(&[arg0]); 369 } else if succs.len() == 1 { 370 pos.ins().jump(blocks[succs[0]], &[]); 371 } else if succs.len() == 2 { 372 pos.ins() 373 .brif(arg0, blocks[succs[0]], &[], blocks[succs[1]], &[]); 374 } else { 375 panic!("Too many successors"); 376 } 377 } 378 379 let mut cfg = ControlFlowGraph::new(); 380 cfg.compute(&func); 381 let dom_tree = DominatorTree::with_function(&func, &cfg); 382 383 BlockLoweringOrder::new(&func, &dom_tree, &mut Default::default()) 384 } 385 386 #[test] 387 fn test_blockorder_diamond() { 388 let order = build_test_func(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]); 389 390 // This test case doesn't need to introduce any critical edges, as all regalloc allocations 391 // can sit on either the entry or exit of blocks 1 and 2. 392 assert_eq!(order.lowered_order.len(), 4); 393 } 394 395 #[test] 396 fn test_blockorder_critedge() { 397 // 0 398 // / \ 399 // 1 2 400 // / \ \ 401 // 3 4 | 402 // |\ _|____| 403 // | \/ | 404 // | /\ | 405 // 5 6 406 // 407 // (3 -> 5, and 3 -> 6 are critical edges and must be split) 408 // 409 let order = build_test_func( 410 7, 411 &[ 412 (0, 1), 413 (0, 2), 414 (1, 3), 415 (1, 4), 416 (2, 5), 417 (3, 5), 418 (3, 6), 419 (4, 6), 420 ], 421 ); 422 423 assert_eq!(order.lowered_order.len(), 9); 424 println!("ordered = {:?}", order.lowered_order); 425 426 // block 0 427 assert_eq!(order.lowered_order[0].orig_block().unwrap().as_u32(), 0); 428 assert!(order.lowered_order[0].in_edge().is_none()); 429 assert!(order.lowered_order[0].out_edge().is_none()); 430 431 // block 2 432 assert_eq!(order.lowered_order[1].orig_block().unwrap().as_u32(), 2); 433 assert!(order.lowered_order[1].in_edge().is_none()); 434 assert!(order.lowered_order[1].out_edge().is_none()); 435 436 // block 1 437 assert_eq!(order.lowered_order[2].orig_block().unwrap().as_u32(), 1); 438 assert!(order.lowered_order[2].in_edge().is_none()); 439 assert!(order.lowered_order[2].out_edge().is_none()); 440 441 // block 4 442 assert_eq!(order.lowered_order[3].orig_block().unwrap().as_u32(), 4); 443 assert!(order.lowered_order[3].in_edge().is_none()); 444 assert!(order.lowered_order[3].out_edge().is_none()); 445 446 // block 3 447 assert_eq!(order.lowered_order[4].orig_block().unwrap().as_u32(), 3); 448 assert!(order.lowered_order[4].in_edge().is_none()); 449 assert!(order.lowered_order[4].out_edge().is_none()); 450 451 // critical edge 3 -> 5 452 assert!(order.lowered_order[5].orig_block().is_none()); 453 assert_eq!(order.lowered_order[5].in_edge().unwrap().as_u32(), 3); 454 assert_eq!(order.lowered_order[5].out_edge().unwrap().as_u32(), 5); 455 456 // critical edge 3 -> 6 457 assert!(order.lowered_order[6].orig_block().is_none()); 458 assert_eq!(order.lowered_order[6].in_edge().unwrap().as_u32(), 3); 459 assert_eq!(order.lowered_order[6].out_edge().unwrap().as_u32(), 6); 460 461 // block 6 462 assert_eq!(order.lowered_order[7].orig_block().unwrap().as_u32(), 6); 463 assert!(order.lowered_order[7].in_edge().is_none()); 464 assert!(order.lowered_order[7].out_edge().is_none()); 465 466 // block 5 467 assert_eq!(order.lowered_order[8].orig_block().unwrap().as_u32(), 5); 468 assert!(order.lowered_order[8].in_edge().is_none()); 469 assert!(order.lowered_order[8].out_edge().is_none()); 470 } 471 } 472