1 //! This implements the VCode container: a CFG of Insts that have been lowered. 2 //! 3 //! VCode is virtual-register code. An instruction in VCode is almost a machine 4 //! instruction; however, its register slots can refer to virtual registers in 5 //! addition to real machine registers. 6 //! 7 //! VCode is structured with traditional basic blocks, and 8 //! each block must be terminated by an unconditional branch (one target), a 9 //! conditional branch (two targets), or a return (no targets). Note that this 10 //! slightly differs from the machine code of most ISAs: in most ISAs, a 11 //! conditional branch has one target (and the not-taken case falls through). 12 //! However, we expect that machine backends will elide branches to the following 13 //! block (i.e., zero-offset jumps), and will be able to codegen a branch-cond / 14 //! branch-uncond pair if *both* targets are not fallthrough. This allows us to 15 //! play with layout prior to final binary emission, as well, if we want. 16 //! 17 //! See the main module comment in `mod.rs` for more details on the VCode-based 18 //! backend pipeline. 19 20 use crate::fx::FxHashMap; 21 use crate::fx::FxHashSet; 22 use crate::ir::pcc::*; 23 use crate::ir::{self, types, Constant, ConstantData, ValueLabel}; 24 use crate::machinst::*; 25 use crate::timing; 26 use crate::trace; 27 use crate::CodegenError; 28 use crate::{LabelValueLoc, ValueLocRange}; 29 use regalloc2::{ 30 Edit, Function as RegallocFunction, InstOrEdit, InstRange, MachineEnv, Operand, OperandKind, 31 PRegSet, RegClass, 32 }; 33 34 use cranelift_entity::{entity_impl, Keys}; 35 use std::collections::hash_map::Entry; 36 use std::collections::HashMap; 37 use std::fmt; 38 39 /// Index referring to an instruction in VCode. 40 pub type InsnIndex = regalloc2::Inst; 41 42 /// Index referring to a basic block in VCode. 43 pub type BlockIndex = regalloc2::Block; 44 45 /// VCodeInst wraps all requirements for a MachInst to be in VCode: it must be 46 /// a `MachInst` and it must be able to emit itself at least to a `SizeCodeSink`. 47 pub trait VCodeInst: MachInst + MachInstEmit {} 48 impl<I: MachInst + MachInstEmit> VCodeInst for I {} 49 50 /// A function in "VCode" (virtualized-register code) form, after 51 /// lowering. This is essentially a standard CFG of basic blocks, 52 /// where each basic block consists of lowered instructions produced 53 /// by the machine-specific backend. 54 /// 55 /// Note that the VCode is immutable once produced, and is not 56 /// modified by register allocation in particular. Rather, register 57 /// allocation on the `VCode` produces a separate `regalloc2::Output` 58 /// struct, and this can be passed to `emit`. `emit` in turn does not 59 /// modify the vcode, but produces an `EmitResult`, which contains the 60 /// machine code itself, and the associated disassembly and/or 61 /// metadata as requested. 62 pub struct VCode<I: VCodeInst> { 63 /// VReg IR-level types. 64 vreg_types: Vec<Type>, 65 66 /// Lowered machine instructions in order corresponding to the original IR. 67 insts: Vec<I>, 68 69 /// Operands: pre-regalloc references to virtual registers with 70 /// constraints, in one flattened array. This allows the regalloc 71 /// to efficiently access all operands without requiring expensive 72 /// matches or method invocations on insts. 73 operands: Vec<Operand>, 74 75 /// Operand index ranges: for each instruction in `insts`, there 76 /// is a tuple here providing the range in `operands` for that 77 /// instruction's operands. 78 operand_ranges: Vec<(u32, u32)>, 79 80 /// Clobbers: a sparse map from instruction indices to clobber masks. 81 clobbers: FxHashMap<InsnIndex, PRegSet>, 82 83 /// Source locations for each instruction. (`SourceLoc` is a `u32`, so it is 84 /// reasonable to keep one of these per instruction.) 85 srclocs: Vec<RelSourceLoc>, 86 87 /// Entry block. 88 entry: BlockIndex, 89 90 /// Block instruction indices. 91 block_ranges: Vec<(InsnIndex, InsnIndex)>, 92 93 /// Block successors: index range in the `block_succs_preds` list. 94 block_succ_range: Vec<(u32, u32)>, 95 96 /// Block predecessors: index range in the `block_succs_preds` list. 97 block_pred_range: Vec<(u32, u32)>, 98 99 /// Block successor and predecessor lists, concatenated into one 100 /// Vec. The `block_succ_range` and `block_pred_range` lists of 101 /// tuples above give (start, end) ranges within this list that 102 /// correspond to each basic block's successors or predecessors, 103 /// respectively. 104 block_succs_preds: Vec<regalloc2::Block>, 105 106 /// Block parameters: index range in `block_params` below. 107 block_params_range: Vec<(u32, u32)>, 108 109 /// Block parameter lists, concatenated into one vec. The 110 /// `block_params_range` list of tuples above gives (start, end) 111 /// ranges within this list that correspond to each basic block's 112 /// blockparam vregs. 113 block_params: Vec<regalloc2::VReg>, 114 115 /// Outgoing block arguments on branch instructions, concatenated 116 /// into one list. 117 /// 118 /// Note that this is conceptually a 3D array: we have a VReg list 119 /// per block, per successor. We flatten those three dimensions 120 /// into this 1D vec, then store index ranges in two levels of 121 /// indirection. 122 /// 123 /// Indexed by the indices in `branch_block_arg_succ_range`. 124 branch_block_args: Vec<regalloc2::VReg>, 125 126 /// Array of sequences of (start, end) tuples in 127 /// `branch_block_args`, one for each successor; these sequences 128 /// for each block are concatenated. 129 /// 130 /// Indexed by the indices in `branch_block_arg_succ_range`. 131 branch_block_arg_range: Vec<(u32, u32)>, 132 133 /// For a given block, indices in `branch_block_arg_range` 134 /// corresponding to all of its successors. 135 branch_block_arg_succ_range: Vec<(u32, u32)>, 136 137 /// VReg aliases. Each key in this table is translated to its 138 /// value when gathering Operands from instructions. Aliases are 139 /// not chased transitively (we do not further look up the 140 /// translated reg to see if it is another alias). 141 /// 142 /// We use these aliases to rename an instruction's expected 143 /// result vregs to the returned vregs from lowering, which are 144 /// usually freshly-allocated temps. 145 /// 146 /// Operands and branch arguments will already have been 147 /// translated through this alias table; but it helps to make 148 /// sense of instructions when pretty-printed, for example. 149 vreg_aliases: FxHashMap<regalloc2::VReg, regalloc2::VReg>, 150 151 /// Block-order information. 152 block_order: BlockLoweringOrder, 153 154 /// ABI object. 155 pub(crate) abi: Callee<I::ABIMachineSpec>, 156 157 /// Constant information used during code emission. This should be 158 /// immutable across function compilations within the same module. 159 emit_info: I::Info, 160 161 /// Reference-typed `regalloc2::VReg`s. The regalloc requires 162 /// these in a dense slice (as opposed to querying the 163 /// reftype-status of each vreg) for efficient iteration. 164 reftyped_vregs: Vec<VReg>, 165 166 /// Constants. 167 pub(crate) constants: VCodeConstants, 168 169 /// Value labels for debuginfo attached to vregs. 170 debug_value_labels: Vec<(VReg, InsnIndex, InsnIndex, u32)>, 171 172 pub(crate) sigs: SigSet, 173 174 /// Facts on VRegs, for proof-carrying code verification. 175 facts: Vec<Option<Fact>>, 176 } 177 178 /// The result of `VCode::emit`. Contains all information computed 179 /// during emission: actual machine code, optionally a disassembly, 180 /// and optionally metadata about the code layout. 181 pub struct EmitResult { 182 /// The MachBuffer containing the machine code. 183 pub buffer: MachBufferFinalized<Stencil>, 184 185 /// Offset of each basic block, recorded during emission. Computed 186 /// only if `debug_value_labels` is non-empty. 187 pub bb_offsets: Vec<CodeOffset>, 188 189 /// Final basic-block edges, in terms of code offsets of 190 /// bb-starts. Computed only if `debug_value_labels` is non-empty. 191 pub bb_edges: Vec<(CodeOffset, CodeOffset)>, 192 193 /// Final length of function body. 194 pub func_body_len: CodeOffset, 195 196 /// The pretty-printed disassembly, if any. This uses the same 197 /// pretty-printing for MachInsts as the pre-regalloc VCode Debug 198 /// implementation, but additionally includes the prologue and 199 /// epilogue(s), and makes use of the regalloc results. 200 pub disasm: Option<String>, 201 202 /// Offsets of sized stackslots. 203 pub sized_stackslot_offsets: PrimaryMap<StackSlot, u32>, 204 205 /// Offsets of dynamic stackslots. 206 pub dynamic_stackslot_offsets: PrimaryMap<DynamicStackSlot, u32>, 207 208 /// Value-labels information (debug metadata). 209 pub value_labels_ranges: ValueLabelsRanges, 210 211 /// Stack frame size. 212 pub frame_size: u32, 213 } 214 215 /// A builder for a VCode function body. 216 /// 217 /// This builder has the ability to accept instructions in either 218 /// forward or reverse order, depending on the pass direction that 219 /// produces the VCode. The lowering from CLIF to VCode<MachInst> 220 /// ordinarily occurs in reverse order (in order to allow instructions 221 /// to be lowered only if used, and not merged) so a reversal will 222 /// occur at the end of lowering to ensure the VCode is in machine 223 /// order. 224 /// 225 /// If built in reverse, block and instruction indices used once the 226 /// VCode is built are relative to the final (reversed) order, not the 227 /// order of construction. Note that this means we do not know the 228 /// final block or instruction indices when building, so we do not 229 /// hand them out. (The user is assumed to know them when appending 230 /// terminator instructions with successor blocks.) 231 pub struct VCodeBuilder<I: VCodeInst> { 232 /// In-progress VCode. 233 pub(crate) vcode: VCode<I>, 234 235 /// In what direction is the build occuring? 236 direction: VCodeBuildDirection, 237 238 /// Index of the last block-start in the vcode. 239 block_start: usize, 240 241 /// Start of succs for the current block in the concatenated succs list. 242 succ_start: usize, 243 244 /// Start of blockparams for the current block in the concatenated 245 /// blockparams list. 246 block_params_start: usize, 247 248 /// Start of successor blockparam arg list entries in 249 /// the concatenated branch_block_arg_range list. 250 branch_block_arg_succ_start: usize, 251 252 /// Current source location. 253 cur_srcloc: RelSourceLoc, 254 255 /// Debug-value label in-progress map, keyed by label. For each 256 /// label, we keep disjoint ranges mapping to vregs. We'll flatten 257 /// this into (vreg, range, label) tuples when done. 258 debug_info: FxHashMap<ValueLabel, Vec<(InsnIndex, InsnIndex, VReg)>>, 259 } 260 261 /// Direction in which a VCodeBuilder builds VCode. 262 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 263 pub enum VCodeBuildDirection { 264 // TODO: add `Forward` once we need it and can test it adequately. 265 /// Backward-build pass: we expect the producer to call `emit()` 266 /// with instructions in reverse program order within each block. 267 Backward, 268 } 269 270 impl<I: VCodeInst> VCodeBuilder<I> { 271 /// Create a new VCodeBuilder. 272 pub fn new( 273 sigs: SigSet, 274 abi: Callee<I::ABIMachineSpec>, 275 emit_info: I::Info, 276 block_order: BlockLoweringOrder, 277 constants: VCodeConstants, 278 direction: VCodeBuildDirection, 279 ) -> VCodeBuilder<I> { 280 let vcode = VCode::new(sigs, abi, emit_info, block_order, constants); 281 282 VCodeBuilder { 283 vcode, 284 direction, 285 block_start: 0, 286 succ_start: 0, 287 block_params_start: 0, 288 branch_block_arg_succ_start: 0, 289 cur_srcloc: Default::default(), 290 debug_info: FxHashMap::default(), 291 } 292 } 293 294 pub fn init_retval_area(&mut self, vregs: &mut VRegAllocator<I>) -> CodegenResult<()> { 295 self.vcode.abi.init_retval_area(&self.vcode.sigs, vregs) 296 } 297 298 /// Access the ABI object. 299 pub fn abi(&self) -> &Callee<I::ABIMachineSpec> { 300 &self.vcode.abi 301 } 302 303 /// Access the ABI object. 304 pub fn abi_mut(&mut self) -> &mut Callee<I::ABIMachineSpec> { 305 &mut self.vcode.abi 306 } 307 308 pub fn sigs(&self) -> &SigSet { 309 &self.vcode.sigs 310 } 311 312 pub fn sigs_mut(&mut self) -> &mut SigSet { 313 &mut self.vcode.sigs 314 } 315 316 /// Access to the BlockLoweringOrder object. 317 pub fn block_order(&self) -> &BlockLoweringOrder { 318 &self.vcode.block_order 319 } 320 321 /// Set the current block as the entry block. 322 pub fn set_entry(&mut self, block: BlockIndex) { 323 self.vcode.entry = block; 324 } 325 326 /// End the current basic block. Must be called after emitting vcode insts 327 /// for IR insts and prior to ending the function (building the VCode). 328 pub fn end_bb(&mut self) { 329 let start_idx = self.block_start; 330 let end_idx = self.vcode.insts.len(); 331 self.block_start = end_idx; 332 // Add the instruction index range to the list of blocks. 333 self.vcode 334 .block_ranges 335 .push((InsnIndex::new(start_idx), InsnIndex::new(end_idx))); 336 // End the successors list. 337 let succ_end = self.vcode.block_succs_preds.len(); 338 self.vcode 339 .block_succ_range 340 .push((self.succ_start as u32, succ_end as u32)); 341 self.succ_start = succ_end; 342 // End the blockparams list. 343 let block_params_end = self.vcode.block_params.len(); 344 self.vcode 345 .block_params_range 346 .push((self.block_params_start as u32, block_params_end as u32)); 347 self.block_params_start = block_params_end; 348 // End the branch blockparam args list. 349 let branch_block_arg_succ_end = self.vcode.branch_block_arg_range.len(); 350 self.vcode.branch_block_arg_succ_range.push(( 351 self.branch_block_arg_succ_start as u32, 352 branch_block_arg_succ_end as u32, 353 )); 354 self.branch_block_arg_succ_start = branch_block_arg_succ_end; 355 } 356 357 pub fn add_block_param(&mut self, param: VirtualReg) { 358 self.vcode.block_params.push(param.into()); 359 } 360 361 fn add_branch_args_for_succ(&mut self, args: &[Reg]) { 362 let start = self.vcode.branch_block_args.len(); 363 self.vcode 364 .branch_block_args 365 .extend(args.iter().map(|&arg| VReg::from(arg))); 366 let end = self.vcode.branch_block_args.len(); 367 self.vcode 368 .branch_block_arg_range 369 .push((start as u32, end as u32)); 370 } 371 372 /// Push an instruction for the current BB and current IR inst 373 /// within the BB. 374 pub fn push(&mut self, insn: I) { 375 self.vcode.insts.push(insn); 376 self.vcode.srclocs.push(self.cur_srcloc); 377 } 378 379 /// Add a successor block with branch args. 380 pub fn add_succ(&mut self, block: BlockIndex, args: &[Reg]) { 381 self.vcode.block_succs_preds.push(block); 382 self.add_branch_args_for_succ(args); 383 } 384 385 /// Set the current source location. 386 pub fn set_srcloc(&mut self, srcloc: RelSourceLoc) { 387 self.cur_srcloc = srcloc; 388 } 389 390 /// Add a debug value label to a register. 391 pub fn add_value_label(&mut self, reg: Reg, label: ValueLabel) { 392 // We'll fix up labels in reverse(). Because we're generating 393 // code bottom-to-top, the liverange of the label goes *from* 394 // the last index at which was defined (or 0, which is the end 395 // of the eventual function) *to* just this instruction, and 396 // no further. 397 let inst = InsnIndex::new(self.vcode.insts.len()); 398 let labels = self.debug_info.entry(label).or_insert_with(|| vec![]); 399 let last = labels 400 .last() 401 .map(|(_start, end, _vreg)| *end) 402 .unwrap_or(InsnIndex::new(0)); 403 labels.push((last, inst, reg.into())); 404 } 405 406 pub fn set_vreg_alias(&mut self, from: Reg, to: Reg) { 407 let from = from.into(); 408 let resolved_to = self.vcode.resolve_vreg_alias(to.into()); 409 // Disallow cycles (see below). 410 assert_ne!(resolved_to, from); 411 self.vcode.vreg_aliases.insert(from, resolved_to); 412 } 413 414 /// Access the constants. 415 pub fn constants(&mut self) -> &mut VCodeConstants { 416 &mut self.vcode.constants 417 } 418 419 fn compute_preds_from_succs(&mut self) { 420 // Compute predecessors from successors. In order to gather 421 // all preds for a block into a contiguous sequence, we build 422 // a list of (succ, pred) tuples and then sort. 423 let mut succ_pred_edges: Vec<(BlockIndex, BlockIndex)> = 424 Vec::with_capacity(self.vcode.block_succs_preds.len()); 425 for (pred, &(start, end)) in self.vcode.block_succ_range.iter().enumerate() { 426 let pred = BlockIndex::new(pred); 427 for i in start..end { 428 let succ = BlockIndex::new(self.vcode.block_succs_preds[i as usize].index()); 429 succ_pred_edges.push((succ, pred)); 430 } 431 } 432 succ_pred_edges.sort_unstable(); 433 434 let mut i = 0; 435 for succ in 0..self.vcode.num_blocks() { 436 let succ = BlockIndex::new(succ); 437 let start = self.vcode.block_succs_preds.len(); 438 while i < succ_pred_edges.len() && succ_pred_edges[i].0 == succ { 439 let pred = succ_pred_edges[i].1; 440 self.vcode.block_succs_preds.push(pred); 441 i += 1; 442 } 443 let end = self.vcode.block_succs_preds.len(); 444 self.vcode.block_pred_range.push((start as u32, end as u32)); 445 } 446 } 447 448 /// Called once, when a build in Backward order is complete, to 449 /// perform the overall reversal (into final forward order) and 450 /// finalize metadata accordingly. 451 fn reverse_and_finalize(&mut self) { 452 let n_insts = self.vcode.insts.len(); 453 if n_insts == 0 { 454 return; 455 } 456 457 // Reverse the per-block and per-inst sequences. 458 self.vcode.block_ranges.reverse(); 459 // block_params_range is indexed by block (and blocks were 460 // traversed in reverse) so we reverse it; but block-param 461 // sequences in the concatenated vec can remain in reverse 462 // order (it is effectively an arena of arbitrarily-placed 463 // referenced sequences). 464 self.vcode.block_params_range.reverse(); 465 // Likewise, we reverse block_succ_range, but the block_succ 466 // concatenated array can remain as-is. 467 self.vcode.block_succ_range.reverse(); 468 self.vcode.insts.reverse(); 469 self.vcode.srclocs.reverse(); 470 // Likewise, branch_block_arg_succ_range is indexed by block 471 // so must be reversed. 472 self.vcode.branch_block_arg_succ_range.reverse(); 473 474 // To translate an instruction index *endpoint* in reversed 475 // order to forward order, compute `n_insts - i`. 476 // 477 // Why not `n_insts - 1 - i`? That would be correct to 478 // translate an individual instruction index (for ten insts 0 479 // to 9 inclusive, inst 0 becomes 9, and inst 9 becomes 480 // 0). But for the usual inclusive-start, exclusive-end range 481 // idiom, inclusive starts become exclusive ends and 482 // vice-versa, so e.g. an (inclusive) start of 0 becomes an 483 // (exclusive) end of 10. 484 let translate = |inst: InsnIndex| InsnIndex::new(n_insts - inst.index()); 485 486 // Edit the block-range instruction indices. 487 for tuple in &mut self.vcode.block_ranges { 488 let (start, end) = *tuple; 489 *tuple = (translate(end), translate(start)); // Note reversed order. 490 } 491 492 // Generate debug-value labels based on per-label maps. 493 for (label, tuples) in &self.debug_info { 494 for &(start, end, vreg) in tuples { 495 let vreg = self.vcode.resolve_vreg_alias(vreg); 496 let fwd_start = translate(end); 497 let fwd_end = translate(start); 498 self.vcode 499 .debug_value_labels 500 .push((vreg, fwd_start, fwd_end, label.as_u32())); 501 } 502 } 503 504 // Now sort debug value labels by VReg, as required 505 // by regalloc2. 506 self.vcode 507 .debug_value_labels 508 .sort_unstable_by_key(|(vreg, _, _, _)| *vreg); 509 } 510 511 fn collect_operands(&mut self) { 512 let allocatable = PRegSet::from(self.vcode.machine_env()); 513 for (i, insn) in self.vcode.insts.iter().enumerate() { 514 // Push operands from the instruction onto the operand list. 515 // 516 // We rename through the vreg alias table as we collect 517 // the operands. This is better than a separate post-pass 518 // over operands, because it has more cache locality: 519 // operands only need to pass through L1 once. This is 520 // also better than renaming instructions' 521 // operands/registers while lowering, because here we only 522 // need to do the `match` over the instruction to visit 523 // its register fields (which is slow, branchy code) once. 524 525 let vreg_aliases = &self.vcode.vreg_aliases; 526 let mut op_collector = 527 OperandCollector::new(&mut self.vcode.operands, allocatable, |vreg| { 528 VCode::<I>::resolve_vreg_alias_impl(vreg_aliases, vreg) 529 }); 530 insn.get_operands(&mut op_collector); 531 let (ops, clobbers) = op_collector.finish(); 532 self.vcode.operand_ranges.push(ops); 533 534 if clobbers != PRegSet::default() { 535 self.vcode.clobbers.insert(InsnIndex::new(i), clobbers); 536 } 537 538 if let Some((dst, src)) = insn.is_move() { 539 // We should never see non-virtual registers present in move 540 // instructions. 541 assert!( 542 src.is_virtual(), 543 "the real register {:?} was used as the source of a move instruction", 544 src 545 ); 546 assert!( 547 dst.to_reg().is_virtual(), 548 "the real register {:?} was used as the destination of a move instruction", 549 dst.to_reg() 550 ); 551 } 552 } 553 554 // Translate blockparam args via the vreg aliases table as well. 555 for arg in &mut self.vcode.branch_block_args { 556 let new_arg = VCode::<I>::resolve_vreg_alias_impl(&self.vcode.vreg_aliases, *arg); 557 trace!("operandcollector: block arg {:?} -> {:?}", arg, new_arg); 558 *arg = new_arg; 559 } 560 } 561 562 /// Build the final VCode. 563 pub fn build(mut self, vregs: VRegAllocator<I>) -> VCode<I> { 564 self.vcode.vreg_types = vregs.vreg_types; 565 self.vcode.facts = vregs.facts; 566 self.vcode.reftyped_vregs = vregs.reftyped_vregs; 567 568 if self.direction == VCodeBuildDirection::Backward { 569 self.reverse_and_finalize(); 570 } 571 self.collect_operands(); 572 573 // Apply register aliases to the `reftyped_vregs` list since this list 574 // will be returned directly to `regalloc2` eventually and all 575 // operands/results of instructions will use the alias-resolved vregs 576 // from `regalloc2`'s perspective. 577 // 578 // Also note that `reftyped_vregs` can't have duplicates, so after the 579 // aliases are applied duplicates are removed. 580 for reg in self.vcode.reftyped_vregs.iter_mut() { 581 *reg = VCode::<I>::resolve_vreg_alias_impl(&self.vcode.vreg_aliases, *reg); 582 } 583 self.vcode.reftyped_vregs.sort(); 584 self.vcode.reftyped_vregs.dedup(); 585 586 self.compute_preds_from_succs(); 587 self.vcode.debug_value_labels.sort_unstable(); 588 self.vcode 589 } 590 } 591 592 /// Is this type a reference type? 593 fn is_reftype(ty: Type) -> bool { 594 ty == types::R64 || ty == types::R32 595 } 596 597 const NO_INST_OFFSET: CodeOffset = u32::MAX; 598 599 impl<I: VCodeInst> VCode<I> { 600 /// New empty VCode. 601 fn new( 602 sigs: SigSet, 603 abi: Callee<I::ABIMachineSpec>, 604 emit_info: I::Info, 605 block_order: BlockLoweringOrder, 606 constants: VCodeConstants, 607 ) -> VCode<I> { 608 let n_blocks = block_order.lowered_order().len(); 609 VCode { 610 sigs, 611 vreg_types: vec![], 612 insts: Vec::with_capacity(10 * n_blocks), 613 operands: Vec::with_capacity(30 * n_blocks), 614 operand_ranges: Vec::with_capacity(10 * n_blocks), 615 clobbers: FxHashMap::default(), 616 srclocs: Vec::with_capacity(10 * n_blocks), 617 entry: BlockIndex::new(0), 618 block_ranges: Vec::with_capacity(n_blocks), 619 block_succ_range: Vec::with_capacity(n_blocks), 620 block_succs_preds: Vec::with_capacity(2 * n_blocks), 621 block_pred_range: Vec::with_capacity(n_blocks), 622 block_params_range: Vec::with_capacity(n_blocks), 623 block_params: Vec::with_capacity(5 * n_blocks), 624 branch_block_args: Vec::with_capacity(10 * n_blocks), 625 branch_block_arg_range: Vec::with_capacity(2 * n_blocks), 626 branch_block_arg_succ_range: Vec::with_capacity(n_blocks), 627 block_order, 628 abi, 629 emit_info, 630 reftyped_vregs: vec![], 631 constants, 632 debug_value_labels: vec![], 633 vreg_aliases: FxHashMap::with_capacity_and_hasher(10 * n_blocks, Default::default()), 634 facts: vec![], 635 } 636 } 637 638 /// Get the ABI-dependent MachineEnv for managing register allocation. 639 pub fn machine_env(&self) -> &MachineEnv { 640 self.abi.machine_env(&self.sigs) 641 } 642 643 /// Get the number of blocks. Block indices will be in the range `0 .. 644 /// (self.num_blocks() - 1)`. 645 pub fn num_blocks(&self) -> usize { 646 self.block_ranges.len() 647 } 648 649 /// The number of lowered instructions. 650 pub fn num_insts(&self) -> usize { 651 self.insts.len() 652 } 653 654 /// Get the successors for a block. 655 pub fn succs(&self, block: BlockIndex) -> &[BlockIndex] { 656 let (start, end) = self.block_succ_range[block.index()]; 657 &self.block_succs_preds[start as usize..end as usize] 658 } 659 660 fn compute_clobbers(&self, regalloc: ®alloc2::Output) -> Vec<Writable<RealReg>> { 661 let mut clobbered = PRegSet::default(); 662 663 // All moves are included in clobbers. 664 for (_, Edit::Move { to, .. }) in ®alloc.edits { 665 if let Some(preg) = to.as_reg() { 666 clobbered.add(preg); 667 } 668 } 669 670 for (i, (start, end)) in self.operand_ranges.iter().enumerate() { 671 // Skip this instruction if not "included in clobbers" as 672 // per the MachInst. (Some backends use this to implement 673 // ABI specifics; e.g., excluding calls of the same ABI as 674 // the current function from clobbers, because by 675 // definition everything clobbered by the call can be 676 // clobbered by this function without saving as well.) 677 if !self.insts[i].is_included_in_clobbers() { 678 continue; 679 } 680 681 let start = *start as usize; 682 let end = *end as usize; 683 let operands = &self.operands[start..end]; 684 let allocs = ®alloc.allocs[start..end]; 685 for (operand, alloc) in operands.iter().zip(allocs.iter()) { 686 if operand.kind() == OperandKind::Def { 687 if let Some(preg) = alloc.as_reg() { 688 clobbered.add(preg); 689 } 690 } 691 } 692 693 // Also add explicitly-clobbered registers. 694 if let Some(&inst_clobbered) = self.clobbers.get(&InsnIndex::new(i)) { 695 clobbered.union_from(inst_clobbered); 696 } 697 } 698 699 clobbered 700 .into_iter() 701 .map(|preg| Writable::from_reg(RealReg::from(preg))) 702 .collect() 703 } 704 705 /// Emit the instructions to a `MachBuffer`, containing fixed-up 706 /// code and external reloc/trap/etc. records ready for use. Takes 707 /// the regalloc results as well. 708 /// 709 /// Returns the machine code itself, and optionally metadata 710 /// and/or a disassembly, as an `EmitResult`. The `VCode` itself 711 /// is consumed by the emission process. 712 pub fn emit( 713 mut self, 714 regalloc: ®alloc2::Output, 715 want_disasm: bool, 716 flags: &settings::Flags, 717 ctrl_plane: &mut ControlPlane, 718 ) -> EmitResult 719 where 720 I: VCodeInst, 721 { 722 // To write into disasm string. 723 use core::fmt::Write; 724 725 let _tt = timing::vcode_emit(); 726 let mut buffer = MachBuffer::new(); 727 let mut bb_starts: Vec<Option<CodeOffset>> = vec![]; 728 729 // The first M MachLabels are reserved for block indices. 730 buffer.reserve_labels_for_blocks(self.num_blocks()); 731 732 // Register all allocated constants with the `MachBuffer` to ensure that 733 // any references to the constants during instructions can be handled 734 // correctly. 735 buffer.register_constants(&self.constants); 736 737 // Construct the final order we emit code in: cold blocks at the end. 738 let mut final_order: SmallVec<[BlockIndex; 16]> = smallvec![]; 739 let mut cold_blocks: SmallVec<[BlockIndex; 16]> = smallvec![]; 740 for block in 0..self.num_blocks() { 741 let block = BlockIndex::new(block); 742 if self.block_order.is_cold(block) { 743 cold_blocks.push(block); 744 } else { 745 final_order.push(block); 746 } 747 } 748 final_order.extend(cold_blocks.clone()); 749 750 // Compute/save info we need for the prologue: clobbers and 751 // number of spillslots. 752 // 753 // We clone `abi` here because we will mutate it as we 754 // generate the prologue and set other info, but we can't 755 // mutate `VCode`. The info it usually carries prior to 756 // setting clobbers is fairly minimal so this should be 757 // relatively cheap. 758 let clobbers = self.compute_clobbers(regalloc); 759 self.abi 760 .compute_frame_layout(&self.sigs, regalloc.num_spillslots, clobbers); 761 762 // Emit blocks. 763 let mut cur_srcloc = None; 764 let mut last_offset = None; 765 let mut inst_offsets = vec![]; 766 let mut state = I::State::new(&self.abi, std::mem::take(ctrl_plane)); 767 768 let mut disasm = String::new(); 769 770 if !self.debug_value_labels.is_empty() { 771 inst_offsets.resize(self.insts.len(), NO_INST_OFFSET); 772 } 773 774 // Count edits per block ahead of time; this is needed for 775 // lookahead island emission. (We could derive it per-block 776 // with binary search in the edit list, but it's more 777 // efficient to do it in one pass here.) 778 let mut ra_edits_per_block: SmallVec<[u32; 64]> = smallvec![]; 779 let mut edit_idx = 0; 780 for block in 0..self.num_blocks() { 781 let end_inst = self.block_ranges[block].1; 782 let start_edit_idx = edit_idx; 783 while edit_idx < regalloc.edits.len() && regalloc.edits[edit_idx].0.inst() < end_inst { 784 edit_idx += 1; 785 } 786 let end_edit_idx = edit_idx; 787 ra_edits_per_block.push((end_edit_idx - start_edit_idx) as u32); 788 } 789 790 let is_forward_edge_cfi_enabled = self.abi.is_forward_edge_cfi_enabled(); 791 let mut bb_padding = match flags.bb_padding_log2_minus_one() { 792 0 => Vec::new(), 793 n => vec![0; 1 << (n - 1)], 794 }; 795 let mut total_bb_padding = 0; 796 797 for (block_order_idx, &block) in final_order.iter().enumerate() { 798 trace!("emitting block {:?}", block); 799 800 // Call the new block hook for state 801 state.on_new_block(); 802 803 // Emit NOPs to align the block. 804 let new_offset = I::align_basic_block(buffer.cur_offset()); 805 while new_offset > buffer.cur_offset() { 806 // Pad with NOPs up to the aligned block offset. 807 let nop = I::gen_nop((new_offset - buffer.cur_offset()) as usize); 808 nop.emit(&[], &mut buffer, &self.emit_info, &mut Default::default()); 809 } 810 assert_eq!(buffer.cur_offset(), new_offset); 811 812 let do_emit = |inst: &I, 813 allocs: &[Allocation], 814 disasm: &mut String, 815 buffer: &mut MachBuffer<I>, 816 state: &mut I::State| { 817 if want_disasm && !inst.is_args() { 818 let mut s = state.clone(); 819 writeln!(disasm, " {}", inst.pretty_print_inst(allocs, &mut s)).unwrap(); 820 } 821 inst.emit(allocs, buffer, &self.emit_info, state); 822 }; 823 824 // Is this the first block? Emit the prologue directly if so. 825 if block == self.entry { 826 trace!(" -> entry block"); 827 buffer.start_srcloc(Default::default()); 828 for inst in &self.abi.gen_prologue() { 829 do_emit(&inst, &[], &mut disasm, &mut buffer, &mut state); 830 } 831 buffer.end_srcloc(); 832 } 833 834 // Now emit the regular block body. 835 836 buffer.bind_label(MachLabel::from_block(block), state.ctrl_plane_mut()); 837 838 if want_disasm { 839 writeln!(&mut disasm, "block{}:", block.index()).unwrap(); 840 } 841 842 if flags.machine_code_cfg_info() { 843 // Track BB starts. If we have backed up due to MachBuffer 844 // branch opts, note that the removed blocks were removed. 845 let cur_offset = buffer.cur_offset(); 846 if last_offset.is_some() && cur_offset <= last_offset.unwrap() { 847 for i in (0..bb_starts.len()).rev() { 848 if bb_starts[i].is_some() && cur_offset > bb_starts[i].unwrap() { 849 break; 850 } 851 bb_starts[i] = None; 852 } 853 } 854 bb_starts.push(Some(cur_offset)); 855 last_offset = Some(cur_offset); 856 } 857 858 if let Some(block_start) = I::gen_block_start( 859 self.block_order.is_indirect_branch_target(block), 860 is_forward_edge_cfi_enabled, 861 ) { 862 do_emit(&block_start, &[], &mut disasm, &mut buffer, &mut state); 863 } 864 865 for inst_or_edit in regalloc.block_insts_and_edits(&self, block) { 866 match inst_or_edit { 867 InstOrEdit::Inst(iix) => { 868 if !self.debug_value_labels.is_empty() { 869 // If we need to produce debug info, 870 // record the offset of each instruction 871 // so that we can translate value-label 872 // ranges to machine-code offsets. 873 874 // Cold blocks violate monotonicity 875 // assumptions elsewhere (that 876 // instructions in inst-index order are in 877 // order in machine code), so we omit 878 // their offsets here. Value-label range 879 // generation below will skip empty ranges 880 // and ranges with to-offsets of zero. 881 if !self.block_order.is_cold(block) { 882 inst_offsets[iix.index()] = buffer.cur_offset(); 883 } 884 } 885 886 // Update the srcloc at this point in the buffer. 887 let srcloc = self.srclocs[iix.index()]; 888 if cur_srcloc != Some(srcloc) { 889 if cur_srcloc.is_some() { 890 buffer.end_srcloc(); 891 } 892 buffer.start_srcloc(srcloc); 893 cur_srcloc = Some(srcloc); 894 } 895 896 // If this is a safepoint, compute a stack map 897 // and pass it to the emit state. 898 if self.insts[iix.index()].is_safepoint() { 899 let mut safepoint_slots: SmallVec<[SpillSlot; 8]> = smallvec![]; 900 // Find the contiguous range of 901 // (progpoint, allocation) safepoint slot 902 // records in `regalloc.safepoint_slots` 903 // for this instruction index. 904 let safepoint_slots_start = regalloc 905 .safepoint_slots 906 .binary_search_by(|(progpoint, _alloc)| { 907 if progpoint.inst() >= iix { 908 std::cmp::Ordering::Greater 909 } else { 910 std::cmp::Ordering::Less 911 } 912 }) 913 .unwrap_err(); 914 915 for (_, alloc) in regalloc.safepoint_slots[safepoint_slots_start..] 916 .iter() 917 .take_while(|(progpoint, _)| progpoint.inst() == iix) 918 { 919 let slot = alloc.as_stack().unwrap(); 920 safepoint_slots.push(slot); 921 } 922 if !safepoint_slots.is_empty() { 923 let stack_map = self 924 .abi 925 .spillslots_to_stack_map(&safepoint_slots[..], &state); 926 state.pre_safepoint(stack_map); 927 } 928 } 929 930 // Get the allocations for this inst from the regalloc result. 931 let allocs = regalloc.inst_allocs(iix); 932 933 // If the instruction we are about to emit is 934 // a return, place an epilogue at this point 935 // (and don't emit the return; the actual 936 // epilogue will contain it). 937 if self.insts[iix.index()].is_term() == MachTerminator::Ret { 938 for inst in self.abi.gen_epilogue() { 939 do_emit(&inst, &[], &mut disasm, &mut buffer, &mut state); 940 } 941 } else { 942 // Emit the instruction! 943 do_emit( 944 &self.insts[iix.index()], 945 allocs, 946 &mut disasm, 947 &mut buffer, 948 &mut state, 949 ); 950 } 951 } 952 953 InstOrEdit::Edit(Edit::Move { from, to }) => { 954 // Create a move/spill/reload instruction and 955 // immediately emit it. 956 match (from.as_reg(), to.as_reg()) { 957 (Some(from), Some(to)) => { 958 // Reg-to-reg move. 959 let from_rreg = Reg::from(from); 960 let to_rreg = Writable::from_reg(Reg::from(to)); 961 debug_assert_eq!(from.class(), to.class()); 962 let ty = I::canonical_type_for_rc(from.class()); 963 let mv = I::gen_move(to_rreg, from_rreg, ty); 964 do_emit(&mv, &[], &mut disasm, &mut buffer, &mut state); 965 } 966 (Some(from), None) => { 967 // Spill from register to spillslot. 968 let to = to.as_stack().unwrap(); 969 let from_rreg = RealReg::from(from); 970 let spill = self.abi.gen_spill(to, from_rreg); 971 do_emit(&spill, &[], &mut disasm, &mut buffer, &mut state); 972 } 973 (None, Some(to)) => { 974 // Load from spillslot to register. 975 let from = from.as_stack().unwrap(); 976 let to_rreg = Writable::from_reg(RealReg::from(to)); 977 let reload = self.abi.gen_reload(to_rreg, from); 978 do_emit(&reload, &[], &mut disasm, &mut buffer, &mut state); 979 } 980 (None, None) => { 981 panic!("regalloc2 should have eliminated stack-to-stack moves!"); 982 } 983 } 984 } 985 } 986 } 987 988 if cur_srcloc.is_some() { 989 buffer.end_srcloc(); 990 cur_srcloc = None; 991 } 992 993 // Do we need an island? Get the worst-case size of the next BB, add 994 // it to the optional padding behind the block, and pass this to the 995 // `MachBuffer` to determine if an island is necessary. 996 let worst_case_next_bb = if block_order_idx < final_order.len() - 1 { 997 let next_block = final_order[block_order_idx + 1]; 998 let next_block_range = self.block_ranges[next_block.index()]; 999 let next_block_size = 1000 (next_block_range.1.index() - next_block_range.0.index()) as u32; 1001 let next_block_ra_insertions = ra_edits_per_block[next_block.index()]; 1002 I::worst_case_size() * (next_block_size + next_block_ra_insertions) 1003 } else { 1004 0 1005 }; 1006 let padding = if bb_padding.is_empty() { 1007 0 1008 } else { 1009 bb_padding.len() as u32 + I::LabelUse::ALIGN - 1 1010 }; 1011 if buffer.island_needed(padding + worst_case_next_bb) { 1012 buffer.emit_island(padding + worst_case_next_bb, ctrl_plane); 1013 } 1014 1015 // Insert padding, if configured, to stress the `MachBuffer`'s 1016 // relocation and island calculations. 1017 // 1018 // Padding can get quite large during fuzzing though so place a 1019 // total cap on it where when a per-function threshold is exceeded 1020 // the padding is turned back down to zero. This avoids a small-ish 1021 // test case generating a GB+ memory footprint in Cranelift for 1022 // example. 1023 if !bb_padding.is_empty() { 1024 buffer.put_data(&bb_padding); 1025 buffer.align_to(I::LabelUse::ALIGN); 1026 total_bb_padding += bb_padding.len(); 1027 if total_bb_padding > (150 << 20) { 1028 bb_padding = Vec::new(); 1029 } 1030 } 1031 } 1032 1033 // Do any optimizations on branches at tail of buffer, as if we had 1034 // bound one last label. 1035 buffer.optimize_branches(ctrl_plane); 1036 1037 // emission state is not needed anymore, move control plane back out 1038 *ctrl_plane = state.take_ctrl_plane(); 1039 1040 let func_body_len = buffer.cur_offset(); 1041 1042 // Create `bb_edges` and final (filtered) `bb_starts`. 1043 let mut bb_edges = vec![]; 1044 let mut bb_offsets = vec![]; 1045 if flags.machine_code_cfg_info() { 1046 for block in 0..self.num_blocks() { 1047 if bb_starts[block].is_none() { 1048 // Block was deleted by MachBuffer; skip. 1049 continue; 1050 } 1051 let from = bb_starts[block].unwrap(); 1052 1053 bb_offsets.push(from); 1054 // Resolve each `succ` label and add edges. 1055 let succs = self.block_succs(BlockIndex::new(block)); 1056 for &succ in succs.iter() { 1057 let to = buffer.resolve_label_offset(MachLabel::from_block(succ)); 1058 bb_edges.push((from, to)); 1059 } 1060 } 1061 } 1062 1063 self.monotonize_inst_offsets(&mut inst_offsets[..], func_body_len); 1064 let value_labels_ranges = 1065 self.compute_value_labels_ranges(regalloc, &inst_offsets[..], func_body_len); 1066 let frame_size = self.abi.frame_size(); 1067 1068 EmitResult { 1069 buffer: buffer.finish(&self.constants, ctrl_plane), 1070 bb_offsets, 1071 bb_edges, 1072 func_body_len, 1073 disasm: if want_disasm { Some(disasm) } else { None }, 1074 sized_stackslot_offsets: self.abi.sized_stackslot_offsets().clone(), 1075 dynamic_stackslot_offsets: self.abi.dynamic_stackslot_offsets().clone(), 1076 value_labels_ranges, 1077 frame_size, 1078 } 1079 } 1080 1081 fn monotonize_inst_offsets(&self, inst_offsets: &mut [CodeOffset], func_body_len: u32) { 1082 if self.debug_value_labels.is_empty() { 1083 return; 1084 } 1085 1086 // During emission, branch removal can make offsets of instructions incorrect. 1087 // Consider the following sequence: [insi][jmp0][jmp1][jmp2][insj] 1088 // It will be recorded as (say): [30] [34] [38] [42] [<would be 46>] 1089 // When the jumps get removed we are left with (in "inst_offsets"): 1090 // [insi][jmp0][jmp1][jmp2][insj][...] 1091 // [30] [34] [38] [42] [34] 1092 // Which violates the monotonicity invariant. This method sets offsets of these 1093 // removed instructions such as to make them appear zero-sized: 1094 // [insi][jmp0][jmp1][jmp2][insj][...] 1095 // [30] [34] [34] [34] [34] 1096 // 1097 let mut next_offset = func_body_len; 1098 for inst_index in (0..(inst_offsets.len() - 1)).rev() { 1099 let inst_offset = inst_offsets[inst_index]; 1100 1101 // Not all instructions get their offsets recorded. 1102 if inst_offset == NO_INST_OFFSET { 1103 continue; 1104 } 1105 1106 if inst_offset > next_offset { 1107 trace!( 1108 "Fixing code offset of the removed Inst {}: {} -> {}", 1109 inst_index, 1110 inst_offset, 1111 next_offset 1112 ); 1113 inst_offsets[inst_index] = next_offset; 1114 continue; 1115 } 1116 1117 next_offset = inst_offset; 1118 } 1119 } 1120 1121 fn compute_value_labels_ranges( 1122 &self, 1123 regalloc: ®alloc2::Output, 1124 inst_offsets: &[CodeOffset], 1125 func_body_len: u32, 1126 ) -> ValueLabelsRanges { 1127 if self.debug_value_labels.is_empty() { 1128 return ValueLabelsRanges::default(); 1129 } 1130 1131 let mut value_labels_ranges: ValueLabelsRanges = HashMap::new(); 1132 for &(label, from, to, alloc) in ®alloc.debug_locations { 1133 let ranges = value_labels_ranges 1134 .entry(ValueLabel::from_u32(label)) 1135 .or_insert_with(|| vec![]); 1136 let from_offset = inst_offsets[from.inst().index()]; 1137 let to_offset = if to.inst().index() == inst_offsets.len() { 1138 func_body_len 1139 } else { 1140 inst_offsets[to.inst().index()] 1141 }; 1142 1143 // Empty ranges or unavailable offsets can happen 1144 // due to cold blocks and branch removal (see above). 1145 if from_offset == NO_INST_OFFSET 1146 || to_offset == NO_INST_OFFSET 1147 || from_offset == to_offset 1148 { 1149 continue; 1150 } 1151 1152 let loc = if let Some(preg) = alloc.as_reg() { 1153 LabelValueLoc::Reg(Reg::from(preg)) 1154 } else { 1155 let slot = alloc.as_stack().unwrap(); 1156 let sp_offset = self.abi.get_spillslot_offset(slot); 1157 let sp_to_caller_sp_offset = self.abi.nominal_sp_to_caller_sp_offset(); 1158 let caller_sp_to_cfa_offset = 1159 crate::isa::unwind::systemv::caller_sp_to_cfa_offset(); 1160 let cfa_to_sp_offset = -((sp_to_caller_sp_offset + caller_sp_to_cfa_offset) as i64); 1161 LabelValueLoc::CFAOffset(cfa_to_sp_offset + sp_offset) 1162 }; 1163 1164 // ValueLocRanges are recorded by *instruction-end 1165 // offset*. `from_offset` is the *start* of the 1166 // instruction; that is the same as the end of another 1167 // instruction, so we only want to begin coverage once 1168 // we are past the previous instruction's end. 1169 let start = from_offset + 1; 1170 1171 // Likewise, `end` is exclusive, but we want to 1172 // *include* the end of the last 1173 // instruction. `to_offset` is the start of the 1174 // `to`-instruction, which is the exclusive end, i.e., 1175 // the first instruction not covered. That 1176 // instruction's start is the same as the end of the 1177 // last instruction that is included, so we go one 1178 // byte further to be sure to include it. 1179 let end = to_offset + 1; 1180 1181 // Coalesce adjacent ranges that for the same location 1182 // to minimize output size here and for the consumers. 1183 if let Some(last_loc_range) = ranges.last_mut() { 1184 if last_loc_range.loc == loc && last_loc_range.end == start { 1185 trace!( 1186 "Extending debug range for VL{} in {:?} to {}", 1187 label, 1188 loc, 1189 end 1190 ); 1191 last_loc_range.end = end; 1192 continue; 1193 } 1194 } 1195 1196 trace!( 1197 "Recording debug range for VL{} in {:?}: [Inst {}..Inst {}) [{}..{})", 1198 label, 1199 loc, 1200 from.inst().index(), 1201 to.inst().index(), 1202 start, 1203 end 1204 ); 1205 1206 ranges.push(ValueLocRange { loc, start, end }); 1207 } 1208 1209 value_labels_ranges 1210 } 1211 1212 /// Get the IR block for a BlockIndex, if one exists. 1213 pub fn bindex_to_bb(&self, block: BlockIndex) -> Option<ir::Block> { 1214 self.block_order.lowered_order()[block.index()].orig_block() 1215 } 1216 1217 fn resolve_vreg_alias(&self, from: regalloc2::VReg) -> regalloc2::VReg { 1218 Self::resolve_vreg_alias_impl(&self.vreg_aliases, from) 1219 } 1220 1221 /// Implementation of alias resolution. Separate helper that does 1222 /// not borrow `self` in order to allow working around borrowing 1223 /// restrictions. 1224 fn resolve_vreg_alias_impl( 1225 aliases: &FxHashMap<regalloc2::VReg, regalloc2::VReg>, 1226 from: regalloc2::VReg, 1227 ) -> regalloc2::VReg { 1228 // We prevent cycles from existing by resolving targets of 1229 // aliases eagerly before setting them. If the target resolves 1230 // to the origin of the alias, then a cycle would be created 1231 // and the alias is disallowed. Because of the structure of 1232 // SSA code (one instruction can refer to another's defs but 1233 // not vice-versa, except indirectly through 1234 // phis/blockparams), cycles should not occur as we use 1235 // aliases to redirect vregs to the temps that actually define 1236 // them. 1237 1238 let mut vreg = from; 1239 while let Some(to) = aliases.get(&vreg) { 1240 vreg = *to; 1241 } 1242 vreg 1243 } 1244 1245 #[inline] 1246 fn debug_assert_no_vreg_aliases(&self, mut list: impl Iterator<Item = VReg>) { 1247 debug_assert!(list.all(|vreg| !self.vreg_aliases.contains_key(&vreg))); 1248 } 1249 1250 /// Get the type of a VReg. 1251 pub fn vreg_type(&self, vreg: VReg) -> Type { 1252 self.vreg_types[vreg.vreg()] 1253 } 1254 1255 /// Get the fact, if any, for a given VReg. 1256 pub fn vreg_fact(&self, vreg: VReg) -> Option<&Fact> { 1257 let vreg = self.resolve_vreg_alias(vreg); 1258 self.facts[vreg.vreg()].as_ref() 1259 } 1260 1261 /// Set the fact for a given VReg. 1262 pub fn set_vreg_fact(&mut self, vreg: VReg, fact: Fact) { 1263 let vreg = self.resolve_vreg_alias(vreg); 1264 trace!("set fact on {}: {:?}", vreg, fact); 1265 self.facts[vreg.vreg()] = Some(fact); 1266 } 1267 1268 /// Does a given instruction define any facts? 1269 pub fn inst_defines_facts(&self, inst: InsnIndex) -> bool { 1270 self.inst_operands(inst) 1271 .iter() 1272 .filter(|o| o.kind() == OperandKind::Def) 1273 .map(|o| o.vreg()) 1274 .any(|vreg| self.facts[vreg.vreg()].is_some()) 1275 } 1276 } 1277 1278 impl<I: VCodeInst> std::ops::Index<InsnIndex> for VCode<I> { 1279 type Output = I; 1280 fn index(&self, idx: InsnIndex) -> &Self::Output { 1281 &self.insts[idx.index()] 1282 } 1283 } 1284 1285 impl<I: VCodeInst> RegallocFunction for VCode<I> { 1286 fn num_insts(&self) -> usize { 1287 self.insts.len() 1288 } 1289 1290 fn num_blocks(&self) -> usize { 1291 self.block_ranges.len() 1292 } 1293 1294 fn entry_block(&self) -> BlockIndex { 1295 self.entry 1296 } 1297 1298 fn block_insns(&self, block: BlockIndex) -> InstRange { 1299 let (start, end) = self.block_ranges[block.index()]; 1300 InstRange::forward(start, end) 1301 } 1302 1303 fn block_succs(&self, block: BlockIndex) -> &[BlockIndex] { 1304 let (start, end) = self.block_succ_range[block.index()]; 1305 &self.block_succs_preds[start as usize..end as usize] 1306 } 1307 1308 fn block_preds(&self, block: BlockIndex) -> &[BlockIndex] { 1309 let (start, end) = self.block_pred_range[block.index()]; 1310 &self.block_succs_preds[start as usize..end as usize] 1311 } 1312 1313 fn block_params(&self, block: BlockIndex) -> &[VReg] { 1314 // As a special case we don't return block params for the entry block, as all the arguments 1315 // will be defined by the `Inst::Args` instruction. 1316 if block == self.entry { 1317 return &[]; 1318 } 1319 1320 let (start, end) = self.block_params_range[block.index()]; 1321 let ret = &self.block_params[start as usize..end as usize]; 1322 // Currently block params are never aliased to another vreg, but 1323 // double-check just to be sure. 1324 self.debug_assert_no_vreg_aliases(ret.iter().copied()); 1325 ret 1326 } 1327 1328 fn branch_blockparams(&self, block: BlockIndex, _insn: InsnIndex, succ_idx: usize) -> &[VReg] { 1329 let (succ_range_start, succ_range_end) = self.branch_block_arg_succ_range[block.index()]; 1330 let succ_ranges = 1331 &self.branch_block_arg_range[succ_range_start as usize..succ_range_end as usize]; 1332 let (branch_block_args_start, branch_block_args_end) = succ_ranges[succ_idx]; 1333 let ret = &self.branch_block_args 1334 [branch_block_args_start as usize..branch_block_args_end as usize]; 1335 self.debug_assert_no_vreg_aliases(ret.iter().copied()); 1336 ret 1337 } 1338 1339 fn is_ret(&self, insn: InsnIndex) -> bool { 1340 match self.insts[insn.index()].is_term() { 1341 // We treat blocks terminated by an unconditional trap like a return for regalloc. 1342 MachTerminator::None => self.insts[insn.index()].is_trap(), 1343 MachTerminator::Ret | MachTerminator::RetCall => true, 1344 MachTerminator::Uncond | MachTerminator::Cond | MachTerminator::Indirect => false, 1345 } 1346 } 1347 1348 fn is_branch(&self, insn: InsnIndex) -> bool { 1349 match self.insts[insn.index()].is_term() { 1350 MachTerminator::Cond | MachTerminator::Uncond | MachTerminator::Indirect => true, 1351 _ => false, 1352 } 1353 } 1354 1355 fn requires_refs_on_stack(&self, insn: InsnIndex) -> bool { 1356 self.insts[insn.index()].is_safepoint() 1357 } 1358 1359 fn inst_operands(&self, insn: InsnIndex) -> &[Operand] { 1360 let (start, end) = self.operand_ranges[insn.index()]; 1361 let ret = &self.operands[start as usize..end as usize]; 1362 // It should be true by construction that `Operand`s do not contain any 1363 // aliased vregs since they're all collected and mapped when the VCode 1364 // is itself constructed. 1365 self.debug_assert_no_vreg_aliases(ret.iter().map(|op| op.vreg())); 1366 ret 1367 } 1368 1369 fn inst_clobbers(&self, insn: InsnIndex) -> PRegSet { 1370 self.clobbers.get(&insn).cloned().unwrap_or_default() 1371 } 1372 1373 fn num_vregs(&self) -> usize { 1374 std::cmp::max(self.vreg_types.len(), first_user_vreg_index()) 1375 } 1376 1377 fn reftype_vregs(&self) -> &[VReg] { 1378 let ret = &self.reftyped_vregs; 1379 self.debug_assert_no_vreg_aliases(ret.iter().copied()); 1380 ret 1381 } 1382 1383 fn debug_value_labels(&self) -> &[(VReg, InsnIndex, InsnIndex, u32)] { 1384 // VRegs here are inserted into `debug_value_labels` after code is 1385 // generated and aliases are fully defined, so double-check that 1386 // aliases are not lingering. 1387 let ret = &self.debug_value_labels; 1388 self.debug_assert_no_vreg_aliases(ret.iter().map(|&(vreg, ..)| vreg)); 1389 ret 1390 } 1391 1392 fn spillslot_size(&self, regclass: RegClass) -> usize { 1393 self.abi.get_spillslot_size(regclass) as usize 1394 } 1395 1396 fn allow_multiple_vreg_defs(&self) -> bool { 1397 // At least the s390x backend requires this, because the 1398 // `Loop` pseudo-instruction aggregates all Operands so pinned 1399 // vregs (RealRegs) may occur more than once. 1400 true 1401 } 1402 } 1403 1404 impl<I: VCodeInst> fmt::Debug for VCode<I> { 1405 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 1406 writeln!(f, "VCode {{")?; 1407 writeln!(f, " Entry block: {}", self.entry.index())?; 1408 1409 let mut state = Default::default(); 1410 1411 let mut alias_keys = self.vreg_aliases.keys().cloned().collect::<Vec<_>>(); 1412 alias_keys.sort_unstable(); 1413 for key in alias_keys { 1414 let dest = self.vreg_aliases.get(&key).unwrap(); 1415 writeln!(f, " {:?} := {:?}", Reg::from(key), Reg::from(*dest))?; 1416 } 1417 1418 for block in 0..self.num_blocks() { 1419 let block = BlockIndex::new(block); 1420 writeln!(f, "Block {}:", block.index())?; 1421 if let Some(bb) = self.bindex_to_bb(block) { 1422 writeln!(f, " (original IR block: {})", bb)?; 1423 } 1424 for succ in self.succs(block) { 1425 writeln!(f, " (successor: Block {})", succ.index())?; 1426 } 1427 let (start, end) = self.block_ranges[block.index()]; 1428 writeln!( 1429 f, 1430 " (instruction range: {} .. {})", 1431 start.index(), 1432 end.index() 1433 )?; 1434 for inst in start.index()..end.index() { 1435 writeln!( 1436 f, 1437 " Inst {}: {}", 1438 inst, 1439 self.insts[inst].pretty_print_inst(&[], &mut state) 1440 )?; 1441 for operand in self.inst_operands(InsnIndex::new(inst)) { 1442 if operand.kind() == OperandKind::Def { 1443 if let Some(fact) = &self.facts[operand.vreg().vreg()] { 1444 writeln!(f, " v{} ! {}", operand.vreg().vreg(), fact)?; 1445 } 1446 } 1447 } 1448 } 1449 } 1450 1451 writeln!(f, "}}")?; 1452 Ok(()) 1453 } 1454 } 1455 1456 /// This structure manages VReg allocation during the lifetime of the VCodeBuilder. 1457 pub struct VRegAllocator<I> { 1458 /// Next virtual register number to allocate. 1459 next_vreg: usize, 1460 1461 /// VReg IR-level types. 1462 vreg_types: Vec<Type>, 1463 1464 /// A set with the same contents as `reftyped_vregs`, in order to 1465 /// avoid inserting more than once. 1466 reftyped_vregs_set: FxHashSet<VReg>, 1467 1468 /// Reference-typed `regalloc2::VReg`s. The regalloc requires 1469 /// these in a dense slice (as opposed to querying the 1470 /// reftype-status of each vreg) for efficient iteration. 1471 reftyped_vregs: Vec<VReg>, 1472 1473 /// A deferred error, to be bubbled up to the top level of the 1474 /// lowering algorithm. We take this approach because we cannot 1475 /// currently propagate a `Result` upward through ISLE code (the 1476 /// lowering rules) or some ABI code. 1477 deferred_error: Option<CodegenError>, 1478 1479 /// Facts on VRegs, for proof-carrying code. 1480 facts: Vec<Option<Fact>>, 1481 1482 /// The type of instruction that this allocator makes registers for. 1483 _inst: core::marker::PhantomData<I>, 1484 } 1485 1486 impl<I: VCodeInst> VRegAllocator<I> { 1487 /// Make a new VRegAllocator. 1488 pub fn new() -> Self { 1489 Self { 1490 next_vreg: first_user_vreg_index(), 1491 vreg_types: vec![], 1492 facts: vec![], 1493 reftyped_vregs_set: FxHashSet::default(), 1494 reftyped_vregs: vec![], 1495 deferred_error: None, 1496 _inst: core::marker::PhantomData::default(), 1497 } 1498 } 1499 1500 /// Allocate a fresh ValueRegs. 1501 pub fn alloc(&mut self, ty: Type) -> CodegenResult<ValueRegs<Reg>> { 1502 if self.deferred_error.is_some() { 1503 return Err(CodegenError::CodeTooLarge); 1504 } 1505 let v = self.next_vreg; 1506 let (regclasses, tys) = I::rc_for_type(ty)?; 1507 self.next_vreg += regclasses.len(); 1508 if self.next_vreg >= VReg::MAX { 1509 return Err(CodegenError::CodeTooLarge); 1510 } 1511 1512 let regs: ValueRegs<Reg> = match regclasses { 1513 &[rc0] => ValueRegs::one(VReg::new(v, rc0).into()), 1514 &[rc0, rc1] => ValueRegs::two(VReg::new(v, rc0).into(), VReg::new(v + 1, rc1).into()), 1515 // We can extend this if/when we support 32-bit targets; e.g., 1516 // an i128 on a 32-bit machine will need up to four machine regs 1517 // for a `Value`. 1518 _ => panic!("Value must reside in 1 or 2 registers"), 1519 }; 1520 for (®_ty, ®) in tys.iter().zip(regs.regs().iter()) { 1521 self.set_vreg_type(reg.to_virtual_reg().unwrap(), reg_ty); 1522 } 1523 1524 // Create empty facts for each allocated vreg. 1525 self.facts 1526 .resize(usize::try_from(self.next_vreg).unwrap(), None); 1527 1528 Ok(regs) 1529 } 1530 1531 /// Allocate a fresh ValueRegs, deferring any out-of-vregs 1532 /// errors. This is useful in places where we cannot bubble a 1533 /// `CodegenResult` upward easily, and which are known to be 1534 /// invoked from within the lowering loop that checks the deferred 1535 /// error status below. 1536 pub fn alloc_with_deferred_error(&mut self, ty: Type) -> ValueRegs<Reg> { 1537 match self.alloc(ty) { 1538 Ok(x) => x, 1539 Err(e) => { 1540 self.deferred_error = Some(e); 1541 self.bogus_for_deferred_error(ty) 1542 } 1543 } 1544 } 1545 1546 /// Take any deferred error that was accumulated by `alloc_with_deferred_error`. 1547 pub fn take_deferred_error(&mut self) -> Option<CodegenError> { 1548 self.deferred_error.take() 1549 } 1550 1551 /// Produce an bogus VReg placeholder with the proper number of 1552 /// registers for the given type. This is meant to be used with 1553 /// deferred allocation errors (see `Lower::alloc_tmp()`). 1554 fn bogus_for_deferred_error(&self, ty: Type) -> ValueRegs<Reg> { 1555 let (regclasses, _tys) = I::rc_for_type(ty).expect("must have valid type"); 1556 match regclasses { 1557 &[rc0] => ValueRegs::one(VReg::new(0, rc0).into()), 1558 &[rc0, rc1] => ValueRegs::two(VReg::new(0, rc0).into(), VReg::new(1, rc1).into()), 1559 _ => panic!("Value must reside in 1 or 2 registers"), 1560 } 1561 } 1562 1563 /// Set the type of this virtual register. 1564 pub fn set_vreg_type(&mut self, vreg: VirtualReg, ty: Type) { 1565 if self.vreg_types.len() <= vreg.index() { 1566 self.vreg_types.resize(vreg.index() + 1, ir::types::INVALID); 1567 } 1568 self.vreg_types[vreg.index()] = ty; 1569 if is_reftype(ty) { 1570 let vreg: VReg = vreg.into(); 1571 if self.reftyped_vregs_set.insert(vreg) { 1572 self.reftyped_vregs.push(vreg); 1573 } 1574 } 1575 } 1576 1577 /// Set the proof-carrying code fact on a given virtual register. 1578 /// 1579 /// Returns the old fact, if any (only one fact can be stored). 1580 pub fn set_fact(&mut self, vreg: VirtualReg, fact: Fact) -> Option<Fact> { 1581 trace!("vreg {:?} has fact: {:?}", vreg, fact); 1582 self.facts[vreg.index()].replace(fact) 1583 } 1584 1585 /// Take (and remove) a fact about a VReg. Used when setting up 1586 /// aliases: we want to move a fact from the alias vreg to the 1587 /// aliased vreg, to preserve facts about a value that were stated 1588 /// before we lowered its producer. 1589 pub fn take_fact(&mut self, vreg: VirtualReg) -> Option<Fact> { 1590 self.facts[vreg.index()].take() 1591 } 1592 1593 /// Set a fact only if one doesn't already exist. 1594 pub fn set_fact_if_missing(&mut self, vreg: VirtualReg, fact: Fact) { 1595 if self.facts[vreg.index()].is_none() { 1596 self.set_fact(vreg, fact); 1597 } 1598 } 1599 1600 /// Allocate a fresh ValueRegs, with a given fact to apply if 1601 /// the value fits in one VReg. 1602 pub fn alloc_with_maybe_fact( 1603 &mut self, 1604 ty: Type, 1605 fact: Option<Fact>, 1606 ) -> CodegenResult<ValueRegs<Reg>> { 1607 let result = self.alloc(ty)?; 1608 1609 // Ensure that we don't lose a fact on a value that splits 1610 // into multiple VRegs. 1611 assert!(result.len() == 1 || fact.is_none()); 1612 if let Some(fact) = fact { 1613 self.set_fact(result.regs()[0].to_virtual_reg().unwrap(), fact); 1614 } 1615 1616 Ok(result) 1617 } 1618 } 1619 1620 /// This structure tracks the large constants used in VCode that will be emitted separately by the 1621 /// [MachBuffer]. 1622 /// 1623 /// First, during the lowering phase, constants are inserted using 1624 /// [VCodeConstants.insert]; an intermediate handle, `VCodeConstant`, tracks what constants are 1625 /// used in this phase. Some deduplication is performed, when possible, as constant 1626 /// values are inserted. 1627 /// 1628 /// Secondly, during the emission phase, the [MachBuffer] assigns [MachLabel]s for each of the 1629 /// constants so that instructions can refer to the value's memory location. The [MachBuffer] 1630 /// then writes the constant values to the buffer. 1631 #[derive(Default)] 1632 pub struct VCodeConstants { 1633 constants: PrimaryMap<VCodeConstant, VCodeConstantData>, 1634 pool_uses: HashMap<Constant, VCodeConstant>, 1635 well_known_uses: HashMap<*const [u8], VCodeConstant>, 1636 u64s: HashMap<[u8; 8], VCodeConstant>, 1637 } 1638 impl VCodeConstants { 1639 /// Initialize the structure with the expected number of constants. 1640 pub fn with_capacity(expected_num_constants: usize) -> Self { 1641 Self { 1642 constants: PrimaryMap::with_capacity(expected_num_constants), 1643 pool_uses: HashMap::with_capacity(expected_num_constants), 1644 well_known_uses: HashMap::new(), 1645 u64s: HashMap::new(), 1646 } 1647 } 1648 1649 /// Insert a constant; using this method indicates that a constant value will be used and thus 1650 /// will be emitted to the `MachBuffer`. The current implementation can deduplicate constants 1651 /// that are [VCodeConstantData::Pool] or [VCodeConstantData::WellKnown] but not 1652 /// [VCodeConstantData::Generated]. 1653 pub fn insert(&mut self, data: VCodeConstantData) -> VCodeConstant { 1654 match data { 1655 VCodeConstantData::Generated(_) => self.constants.push(data), 1656 VCodeConstantData::Pool(constant, _) => match self.pool_uses.get(&constant) { 1657 None => { 1658 let vcode_constant = self.constants.push(data); 1659 self.pool_uses.insert(constant, vcode_constant); 1660 vcode_constant 1661 } 1662 Some(&vcode_constant) => vcode_constant, 1663 }, 1664 VCodeConstantData::WellKnown(data_ref) => { 1665 match self.well_known_uses.entry(data_ref as *const [u8]) { 1666 Entry::Vacant(v) => { 1667 let vcode_constant = self.constants.push(data); 1668 v.insert(vcode_constant); 1669 vcode_constant 1670 } 1671 Entry::Occupied(o) => *o.get(), 1672 } 1673 } 1674 VCodeConstantData::U64(value) => match self.u64s.entry(value) { 1675 Entry::Vacant(v) => { 1676 let vcode_constant = self.constants.push(data); 1677 v.insert(vcode_constant); 1678 vcode_constant 1679 } 1680 Entry::Occupied(o) => *o.get(), 1681 }, 1682 } 1683 } 1684 1685 /// Return the number of constants inserted. 1686 pub fn len(&self) -> usize { 1687 self.constants.len() 1688 } 1689 1690 /// Iterate over the `VCodeConstant` keys inserted in this structure. 1691 pub fn keys(&self) -> Keys<VCodeConstant> { 1692 self.constants.keys() 1693 } 1694 1695 /// Iterate over the `VCodeConstant` keys and the data (as a byte slice) inserted in this 1696 /// structure. 1697 pub fn iter(&self) -> impl Iterator<Item = (VCodeConstant, &VCodeConstantData)> { 1698 self.constants.iter() 1699 } 1700 1701 /// Returns the data associated with the specified constant. 1702 pub fn get(&self, c: VCodeConstant) -> &VCodeConstantData { 1703 &self.constants[c] 1704 } 1705 1706 /// Checks if the given [VCodeConstantData] is registered as 1707 /// used by the pool. 1708 pub fn pool_uses(&self, constant: &VCodeConstantData) -> bool { 1709 match constant { 1710 VCodeConstantData::Pool(c, _) => self.pool_uses.contains_key(c), 1711 _ => false, 1712 } 1713 } 1714 } 1715 1716 /// A use of a constant by one or more VCode instructions; see [VCodeConstants]. 1717 #[derive(Clone, Copy, Debug, PartialEq, Eq)] 1718 pub struct VCodeConstant(u32); 1719 entity_impl!(VCodeConstant); 1720 1721 /// Identify the different types of constant that can be inserted into [VCodeConstants]. Tracking 1722 /// these separately instead of as raw byte buffers allows us to avoid some duplication. 1723 pub enum VCodeConstantData { 1724 /// A constant already present in the Cranelift IR 1725 /// [ConstantPool](crate::ir::constant::ConstantPool). 1726 Pool(Constant, ConstantData), 1727 /// A reference to a well-known constant value that is statically encoded within the compiler. 1728 WellKnown(&'static [u8]), 1729 /// A constant value generated during lowering; the value may depend on the instruction context 1730 /// which makes it difficult to de-duplicate--if possible, use other variants. 1731 Generated(ConstantData), 1732 /// A constant of at most 64 bits. These are deduplicated as 1733 /// well. Stored as a fixed-size array of `u8` so that we do not 1734 /// encounter endianness problems when cross-compiling. 1735 U64([u8; 8]), 1736 } 1737 impl VCodeConstantData { 1738 /// Retrieve the constant data as a byte slice. 1739 pub fn as_slice(&self) -> &[u8] { 1740 match self { 1741 VCodeConstantData::Pool(_, d) | VCodeConstantData::Generated(d) => d.as_slice(), 1742 VCodeConstantData::WellKnown(d) => d, 1743 VCodeConstantData::U64(value) => &value[..], 1744 } 1745 } 1746 1747 /// Calculate the alignment of the constant data. 1748 pub fn alignment(&self) -> u32 { 1749 if self.as_slice().len() <= 8 { 1750 8 1751 } else { 1752 16 1753 } 1754 } 1755 } 1756 1757 #[cfg(test)] 1758 mod test { 1759 use super::*; 1760 use std::mem::size_of; 1761 1762 #[test] 1763 fn size_of_constant_structs() { 1764 assert_eq!(size_of::<Constant>(), 4); 1765 assert_eq!(size_of::<VCodeConstant>(), 4); 1766 assert_eq!(size_of::<ConstantData>(), 24); 1767 assert_eq!(size_of::<VCodeConstantData>(), 32); 1768 assert_eq!( 1769 size_of::<PrimaryMap<VCodeConstant, VCodeConstantData>>(), 1770 24 1771 ); 1772 // TODO The VCodeConstants structure's memory size could be further optimized. 1773 // With certain versions of Rust, each `HashMap` in `VCodeConstants` occupied at 1774 // least 48 bytes, making an empty `VCodeConstants` cost 120 bytes. 1775 } 1776 } 1777