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