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