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