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