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