cranelift_codegen/machinst/
vcode.rs

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