cranelift_codegen/machinst/
buffer.rs

1//! In-memory representation of compiled machine code, with labels and fixups to
2//! refer to those labels. Handles constant-pool island insertion and also
3//! veneer insertion for out-of-range jumps.
4//!
5//! This code exists to solve three problems:
6//!
7//! - Branch targets for forward branches are not known until later, when we
8//!   emit code in a single pass through the instruction structs.
9//!
10//! - On many architectures, address references or offsets have limited range.
11//!   For example, on AArch64, conditional branches can only target code +/- 1MB
12//!   from the branch itself.
13//!
14//! - The lowering of control flow from the CFG-with-edges produced by
15//!   [BlockLoweringOrder](super::BlockLoweringOrder), combined with many empty
16//!   edge blocks when the register allocator does not need to insert any
17//!   spills/reloads/moves in edge blocks, results in many suboptimal branch
18//!   patterns. The lowering also pays no attention to block order, and so
19//!   two-target conditional forms (cond-br followed by uncond-br) can often by
20//!   avoided because one of the targets is the fallthrough. There are several
21//!   cases here where we can simplify to use fewer branches.
22//!
23//! This "buffer" implements a single-pass code emission strategy (with a later
24//! "fixup" pass, but only through recorded fixups, not all instructions). The
25//! basic idea is:
26//!
27//! - Emit branches as they are, including two-target (cond/uncond) compound
28//!   forms, but with zero offsets and optimistically assuming the target will be
29//!   in range. Record the "fixup" for later. Targets are denoted instead by
30//!   symbolic "labels" that are then bound to certain offsets in the buffer as
31//!   we emit code. (Nominally, there is a label at the start of every basic
32//!   block.)
33//!
34//! - As we do this, track the offset in the buffer at which the first label
35//!   reference "goes out of range". We call this the "deadline". If we reach the
36//!   deadline and we still have not bound the label to which an unresolved branch
37//!   refers, we have a problem!
38//!
39//! - To solve this problem, we emit "islands" full of "veneers". An island is
40//!   simply a chunk of code inserted in the middle of the code actually produced
41//!   by the emitter (e.g., vcode iterating over instruction structs). The emitter
42//!   has some awareness of this: it either asks for an island between blocks, so
43//!   it is not accidentally executed, or else it emits a branch around the island
44//!   when all other options fail (see `Inst::EmitIsland` meta-instruction).
45//!
46//! - A "veneer" is an instruction (or sequence of instructions) in an "island"
47//!   that implements a longer-range reference to a label. The idea is that, for
48//!   example, a branch with a limited range can branch to a "veneer" instead,
49//!   which is simply a branch in a form that can use a longer-range reference. On
50//!   AArch64, for example, conditionals have a +/- 1 MB range, but a conditional
51//!   can branch to an unconditional branch which has a +/- 128 MB range. Hence, a
52//!   conditional branch's label reference can be fixed up with a "veneer" to
53//!   achieve a longer range.
54//!
55//! - To implement all of this, we require the backend to provide a `LabelUse`
56//!   type that implements a trait. This is nominally an enum that records one of
57//!   several kinds of references to an offset in code -- basically, a relocation
58//!   type -- and will usually correspond to different instruction formats. The
59//!   `LabelUse` implementation specifies the maximum range, how to patch in the
60//!   actual label location when known, and how to generate a veneer to extend the
61//!   range.
62//!
63//! That satisfies label references, but we still may have suboptimal branch
64//! patterns. To clean up the branches, we do a simple "peephole"-style
65//! optimization on the fly. To do so, the emitter (e.g., `Inst::emit()`)
66//! informs the buffer of branches in the code and, in the case of conditionals,
67//! the code that would have been emitted to invert this branch's condition. We
68//! track the "latest branches": these are branches that are contiguous up to
69//! the current offset. (If any code is emitted after a branch, that branch or
70//! run of contiguous branches is no longer "latest".) The latest branches are
71//! those that we can edit by simply truncating the buffer and doing something
72//! else instead.
73//!
74//! To optimize branches, we implement several simple rules, and try to apply
75//! them to the "latest branches" when possible:
76//!
77//! - A branch with a label target, when that label is bound to the ending
78//!   offset of the branch (the fallthrough location), can be removed altogether,
79//!   because the branch would have no effect).
80//!
81//! - An unconditional branch that starts at a label location, and branches to
82//!   another label, results in a "label alias": all references to the label bound
83//!   *to* this branch instruction are instead resolved to the *target* of the
84//!   branch instruction. This effectively removes empty blocks that just
85//!   unconditionally branch to the next block. We call this "branch threading".
86//!
87//! - A conditional followed by an unconditional, when the conditional branches
88//!   to the unconditional's fallthrough, results in (i) the truncation of the
89//!   unconditional, (ii) the inversion of the condition's condition, and (iii)
90//!   replacement of the conditional's target (using the original target of the
91//!   unconditional). This is a fancy way of saying "we can flip a two-target
92//!   conditional branch's taken/not-taken targets if it works better with our
93//!   fallthrough". To make this work, the emitter actually gives the buffer
94//!   *both* forms of every conditional branch: the true form is emitted into the
95//!   buffer, and the "inverted" machine-code bytes are provided as part of the
96//!   branch-fixup metadata.
97//!
98//! - An unconditional B preceded by another unconditional P, when B's label(s) have
99//!   been redirected to target(B), can be removed entirely. This is an extension
100//!   of the branch-threading optimization, and is valid because if we know there
101//!   will be no fallthrough into this branch instruction (the prior instruction
102//!   is an unconditional jump), and if we know we have successfully redirected
103//!   all labels, then this branch instruction is unreachable. Note that this
104//!   works because the redirection happens before the label is ever resolved
105//!   (fixups happen at island emission time, at which point latest-branches are
106//!   cleared, or at the end of emission), so we are sure to catch and redirect
107//!   all possible paths to this instruction.
108//!
109//! # Branch-optimization Correctness
110//!
111//! The branch-optimization mechanism depends on a few data structures with
112//! invariants, which are always held outside the scope of top-level public
113//! methods:
114//!
115//! - The latest-branches list. Each entry describes a span of the buffer
116//!   (start/end offsets), the label target, the corresponding fixup-list entry
117//!   index, and the bytes (must be the same length) for the inverted form, if
118//!   conditional. The list of labels that are bound to the start-offset of this
119//!   branch is *complete* (if any label has a resolved offset equal to `start`
120//!   and is not an alias, it must appear in this list) and *precise* (no label
121//!   in this list can be bound to another offset). No label in this list should
122//!   be an alias.  No two branch ranges can overlap, and branches are in
123//!   ascending-offset order.
124//!
125//! - The labels-at-tail list. This contains all MachLabels that have been bound
126//!   to (whose resolved offsets are equal to) the tail offset of the buffer.
127//!   No label in this list should be an alias.
128//!
129//! - The label_offsets array, containing the bound offset of a label or
130//!   UNKNOWN. No label can be bound at an offset greater than the current
131//!   buffer tail.
132//!
133//! - The label_aliases array, containing another label to which a label is
134//!   bound or UNKNOWN. A label's resolved offset is the resolved offset
135//!   of the label it is aliased to, if this is set.
136//!
137//! We argue below, at each method, how the invariants in these data structures
138//! are maintained (grep for "Post-invariant").
139//!
140//! Given these invariants, we argue why each optimization preserves execution
141//! semantics below (grep for "Preserves execution semantics").
142//!
143//! # Avoiding Quadratic Behavior
144//!
145//! There are two cases where we've had to take some care to avoid
146//! quadratic worst-case behavior:
147//!
148//! - The "labels at this branch" list can grow unboundedly if the
149//!   code generator binds many labels at one location. If the count
150//!   gets too high (defined by the `LABEL_LIST_THRESHOLD` constant), we
151//!   simply abort an optimization early in a way that is always correct
152//!   but is conservative.
153//!
154//! - The fixup list can interact with island emission to create
155//!   "quadratic island behavior". In a little more detail, one can hit
156//!   this behavior by having some pending fixups (forward label
157//!   references) with long-range label-use kinds, and some others
158//!   with shorter-range references that nonetheless still are pending
159//!   long enough to trigger island generation. In such a case, we
160//!   process the fixup list, generate veneers to extend some forward
161//!   references' ranges, but leave the other (longer-range) ones
162//!   alone. The way this was implemented put them back on a list and
163//!   resulted in quadratic behavior.
164//!
165//!   To avoid this fixups are split into two lists: one "pending" list and one
166//!   final list. The pending list is kept around for handling fixups related to
167//!   branches so it can be edited/truncated. When an island is reached, which
168//!   starts processing fixups, all pending fixups are flushed into the final
169//!   list. The final list is a `BinaryHeap` which enables fixup processing to
170//!   only process those which are required during island emission, deferring
171//!   all longer-range fixups to later.
172
173use crate::binemit::{Addend, CodeOffset, Reloc};
174use crate::ir::function::FunctionParameters;
175use crate::ir::{DebugTag, ExceptionTag, ExternalName, RelSourceLoc, SourceLoc, TrapCode};
176use crate::isa::unwind::UnwindInst;
177use crate::machinst::{
178    BlockIndex, MachInstLabelUse, TextSectionBuilder, VCodeConstant, VCodeConstants, VCodeInst,
179};
180use crate::trace;
181use crate::{MachInstEmitState, ir};
182use crate::{VCodeConstantData, timing};
183use core::ops::Range;
184use cranelift_control::ControlPlane;
185use cranelift_entity::{PrimaryMap, SecondaryMap, entity_impl};
186use smallvec::SmallVec;
187use std::cmp::Ordering;
188use std::collections::BinaryHeap;
189use std::mem;
190use std::string::String;
191use std::vec::Vec;
192
193#[cfg(feature = "enable-serde")]
194use serde::{Deserialize, Serialize};
195
196#[cfg(feature = "enable-serde")]
197pub trait CompilePhase {
198    type MachSrcLocType: for<'a> Deserialize<'a> + Serialize + core::fmt::Debug + PartialEq + Clone;
199    type SourceLocType: for<'a> Deserialize<'a> + Serialize + core::fmt::Debug + PartialEq + Clone;
200}
201
202#[cfg(not(feature = "enable-serde"))]
203pub trait CompilePhase {
204    type MachSrcLocType: core::fmt::Debug + PartialEq + Clone;
205    type SourceLocType: core::fmt::Debug + PartialEq + Clone;
206}
207
208/// Status of a compiled artifact that needs patching before being used.
209#[derive(Clone, Debug, PartialEq)]
210#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
211pub struct Stencil;
212
213/// Status of a compiled artifact ready to use.
214#[derive(Clone, Debug, PartialEq)]
215pub struct Final;
216
217impl CompilePhase for Stencil {
218    type MachSrcLocType = MachSrcLoc<Stencil>;
219    type SourceLocType = RelSourceLoc;
220}
221
222impl CompilePhase for Final {
223    type MachSrcLocType = MachSrcLoc<Final>;
224    type SourceLocType = SourceLoc;
225}
226
227#[derive(Clone, Copy, Debug, PartialEq, Eq)]
228enum ForceVeneers {
229    Yes,
230    No,
231}
232
233/// A buffer of output to be produced, fixed up, and then emitted to a CodeSink
234/// in bulk.
235///
236/// This struct uses `SmallVec`s to support small-ish function bodies without
237/// any heap allocation. As such, it will be several kilobytes large. This is
238/// likely fine as long as it is stack-allocated for function emission then
239/// thrown away; but beware if many buffer objects are retained persistently.
240pub struct MachBuffer<I: VCodeInst> {
241    /// The buffer contents, as raw bytes.
242    data: SmallVec<[u8; 1024]>,
243    /// The required alignment of this buffer.
244    min_alignment: u32,
245    /// Any relocations referring to this code. Note that only *external*
246    /// relocations are tracked here; references to labels within the buffer are
247    /// resolved before emission.
248    relocs: SmallVec<[MachReloc; 16]>,
249    /// Any trap records referring to this code.
250    traps: SmallVec<[MachTrap; 16]>,
251    /// Any call site records referring to this code.
252    call_sites: SmallVec<[MachCallSite; 16]>,
253    /// Any exception-handler records referred to at call sites.
254    exception_handlers: SmallVec<[MachExceptionHandler; 16]>,
255    /// Any source location mappings referring to this code.
256    srclocs: SmallVec<[MachSrcLoc<Stencil>; 64]>,
257    /// Any debug tags referring to this code.
258    debug_tags: Vec<MachDebugTags>,
259    /// Pool of debug tags referenced by `MachDebugTags` entries.
260    debug_tag_pool: Vec<DebugTag>,
261    /// Any user stack maps for this code.
262    ///
263    /// Each entry is an `(offset, span, stack_map)` triple. Entries are sorted
264    /// by code offset, and each stack map covers `span` bytes on the stack.
265    user_stack_maps: SmallVec<[(CodeOffset, u32, ir::UserStackMap); 8]>,
266    /// Any unwind info at a given location.
267    unwind_info: SmallVec<[(CodeOffset, UnwindInst); 8]>,
268    /// The current source location in progress (after `start_srcloc()` and
269    /// before `end_srcloc()`).  This is a (start_offset, src_loc) tuple.
270    cur_srcloc: Option<(CodeOffset, RelSourceLoc)>,
271    /// Known label offsets; `UNKNOWN_LABEL_OFFSET` if unknown.
272    label_offsets: SmallVec<[CodeOffset; 16]>,
273    /// Label aliases: when one label points to an unconditional jump, and that
274    /// jump points to another label, we can redirect references to the first
275    /// label immediately to the second.
276    ///
277    /// Invariant: we don't have label-alias cycles. We ensure this by,
278    /// before setting label A to alias label B, resolving B's alias
279    /// target (iteratively until a non-aliased label); if B is already
280    /// aliased to A, then we cannot alias A back to B.
281    label_aliases: SmallVec<[MachLabel; 16]>,
282    /// Constants that must be emitted at some point.
283    pending_constants: SmallVec<[VCodeConstant; 16]>,
284    /// Byte size of all constants in `pending_constants`.
285    pending_constants_size: CodeOffset,
286    /// Traps that must be emitted at some point.
287    pending_traps: SmallVec<[MachLabelTrap; 16]>,
288    /// Fixups that haven't yet been flushed into `fixup_records` below and may
289    /// be related to branches that are chomped. These all get added to
290    /// `fixup_records` during island emission.
291    pending_fixup_records: SmallVec<[MachLabelFixup<I>; 16]>,
292    /// The nearest upcoming deadline for entries in `pending_fixup_records`.
293    pending_fixup_deadline: CodeOffset,
294    /// Fixups that must be performed after all code is emitted.
295    fixup_records: BinaryHeap<MachLabelFixup<I>>,
296    /// Latest branches, to facilitate in-place editing for better fallthrough
297    /// behavior and empty-block removal.
298    latest_branches: SmallVec<[MachBranch; 4]>,
299    /// All labels at the current offset (emission tail). This is lazily
300    /// cleared: it is actually accurate as long as the current offset is
301    /// `labels_at_tail_off`, but if `cur_offset()` has grown larger, it should
302    /// be considered as empty.
303    ///
304    /// For correctness, this *must* be complete (i.e., the vector must contain
305    /// all labels whose offsets are resolved to the current tail), because we
306    /// rely on it to update labels when we truncate branches.
307    labels_at_tail: SmallVec<[MachLabel; 4]>,
308    /// The last offset at which `labels_at_tail` is valid. It is conceptually
309    /// always describing the tail of the buffer, but we do not clear
310    /// `labels_at_tail` eagerly when the tail grows, rather we lazily clear it
311    /// when the offset has grown past this (`labels_at_tail_off`) point.
312    /// Always <= `cur_offset()`.
313    labels_at_tail_off: CodeOffset,
314    /// Metadata about all constants that this function has access to.
315    ///
316    /// This records the size/alignment of all constants (not the actual data)
317    /// along with the last available label generated for the constant. This map
318    /// is consulted when constants are referred to and the label assigned to a
319    /// constant may change over time as well.
320    constants: PrimaryMap<VCodeConstant, MachBufferConstant>,
321    /// All recorded usages of constants as pairs of the constant and where the
322    /// constant needs to be placed within `self.data`. Note that the same
323    /// constant may appear in this array multiple times if it was emitted
324    /// multiple times.
325    used_constants: SmallVec<[(VCodeConstant, CodeOffset); 4]>,
326    /// Indicates when a patchable region is currently open, to guard that it's
327    /// not possible to nest patchable regions.
328    open_patchable: bool,
329    /// Stack frame layout metadata. If provided for a MachBuffer
330    /// containing a function body, this allows interpretation of
331    /// runtime state given a view of an active stack frame.
332    frame_layout: Option<MachBufferFrameLayout>,
333}
334
335impl MachBufferFinalized<Stencil> {
336    /// Get a finalized machine buffer by applying the function's base source location.
337    pub fn apply_base_srcloc(self, base_srcloc: SourceLoc) -> MachBufferFinalized<Final> {
338        MachBufferFinalized {
339            data: self.data,
340            relocs: self.relocs,
341            traps: self.traps,
342            call_sites: self.call_sites,
343            exception_handlers: self.exception_handlers,
344            srclocs: self
345                .srclocs
346                .into_iter()
347                .map(|srcloc| srcloc.apply_base_srcloc(base_srcloc))
348                .collect(),
349            debug_tags: self.debug_tags,
350            debug_tag_pool: self.debug_tag_pool,
351            user_stack_maps: self.user_stack_maps,
352            unwind_info: self.unwind_info,
353            alignment: self.alignment,
354            frame_layout: self.frame_layout,
355        }
356    }
357}
358
359/// A `MachBuffer` once emission is completed: holds generated code and records,
360/// without fixups. This allows the type to be independent of the backend.
361#[derive(PartialEq, Debug, Clone)]
362#[cfg_attr(
363    feature = "enable-serde",
364    derive(serde_derive::Serialize, serde_derive::Deserialize)
365)]
366pub struct MachBufferFinalized<T: CompilePhase> {
367    /// The buffer contents, as raw bytes.
368    pub(crate) data: SmallVec<[u8; 1024]>,
369    /// Any relocations referring to this code. Note that only *external*
370    /// relocations are tracked here; references to labels within the buffer are
371    /// resolved before emission.
372    pub(crate) relocs: SmallVec<[FinalizedMachReloc; 16]>,
373    /// Any trap records referring to this code.
374    pub(crate) traps: SmallVec<[MachTrap; 16]>,
375    /// Any call site records referring to this code.
376    pub(crate) call_sites: SmallVec<[MachCallSite; 16]>,
377    /// Any exception-handler records referred to at call sites.
378    pub(crate) exception_handlers: SmallVec<[FinalizedMachExceptionHandler; 16]>,
379    /// Any source location mappings referring to this code.
380    pub(crate) srclocs: SmallVec<[T::MachSrcLocType; 64]>,
381    /// Any debug tags referring to this code.
382    pub(crate) debug_tags: Vec<MachDebugTags>,
383    /// Pool of debug tags referenced by `MachDebugTags` entries.
384    pub(crate) debug_tag_pool: Vec<DebugTag>,
385    /// Any user stack maps for this code.
386    ///
387    /// Each entry is an `(offset, span, stack_map)` triple. Entries are sorted
388    /// by code offset, and each stack map covers `span` bytes on the stack.
389    pub(crate) user_stack_maps: SmallVec<[(CodeOffset, u32, ir::UserStackMap); 8]>,
390    /// Stack frame layout metadata. If provided for a MachBuffer
391    /// containing a function body, this allows interpretation of
392    /// runtime state given a view of an active stack frame.
393    pub(crate) frame_layout: Option<MachBufferFrameLayout>,
394    /// Any unwind info at a given location.
395    pub unwind_info: SmallVec<[(CodeOffset, UnwindInst); 8]>,
396    /// The required alignment of this buffer.
397    pub alignment: u32,
398}
399
400const UNKNOWN_LABEL_OFFSET: CodeOffset = 0xffff_ffff;
401const UNKNOWN_LABEL: MachLabel = MachLabel(0xffff_ffff);
402
403/// Threshold on max length of `labels_at_this_branch` list to avoid
404/// unbounded quadratic behavior (see comment below at use-site).
405const LABEL_LIST_THRESHOLD: usize = 100;
406
407/// A label refers to some offset in a `MachBuffer`. It may not be resolved at
408/// the point at which it is used by emitted code; the buffer records "fixups"
409/// for references to the label, and will come back and patch the code
410/// appropriately when the label's location is eventually known.
411#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
412pub struct MachLabel(u32);
413entity_impl!(MachLabel);
414
415impl MachLabel {
416    /// Get a label for a block. (The first N MachLabels are always reserved for
417    /// the N blocks in the vcode.)
418    pub fn from_block(bindex: BlockIndex) -> MachLabel {
419        MachLabel(bindex.index() as u32)
420    }
421
422    /// Creates a string representing this label, for convenience.
423    pub fn to_string(&self) -> String {
424        format!("label{}", self.0)
425    }
426}
427
428impl Default for MachLabel {
429    fn default() -> Self {
430        UNKNOWN_LABEL
431    }
432}
433
434/// Represents the beginning of an editable region in the [`MachBuffer`], while code emission is
435/// still occurring. An [`OpenPatchRegion`] is closed by [`MachBuffer::end_patchable`], consuming
436/// the [`OpenPatchRegion`] token in the process.
437pub struct OpenPatchRegion(usize);
438
439/// A region in the [`MachBuffer`] code buffer that can be edited prior to finalization. An example
440/// of where you might want to use this is for patching instructions that mention constants that
441/// won't be known until later: [`MachBuffer::start_patchable`] can be used to begin the patchable
442/// region, instructions can be emitted with placeholder constants, and the [`PatchRegion`] token
443/// can be produced by [`MachBuffer::end_patchable`]. Once the values of those constants are known,
444/// the [`PatchRegion::patch`] function can be used to get a mutable buffer to the instruction
445/// bytes, and the constants uses can be updated directly.
446pub struct PatchRegion {
447    range: Range<usize>,
448}
449
450impl PatchRegion {
451    /// Consume the patch region to yield a mutable slice of the [`MachBuffer`] data buffer.
452    pub fn patch<I: VCodeInst>(self, buffer: &mut MachBuffer<I>) -> &mut [u8] {
453        &mut buffer.data[self.range]
454    }
455}
456
457impl<I: VCodeInst> MachBuffer<I> {
458    /// Create a new section, known to start at `start_offset` and with a size limited to
459    /// `length_limit`.
460    pub fn new() -> MachBuffer<I> {
461        MachBuffer {
462            data: SmallVec::new(),
463            min_alignment: I::function_alignment().minimum,
464            relocs: SmallVec::new(),
465            traps: SmallVec::new(),
466            call_sites: SmallVec::new(),
467            exception_handlers: SmallVec::new(),
468            srclocs: SmallVec::new(),
469            debug_tags: vec![],
470            debug_tag_pool: vec![],
471            user_stack_maps: SmallVec::new(),
472            unwind_info: SmallVec::new(),
473            cur_srcloc: None,
474            label_offsets: SmallVec::new(),
475            label_aliases: SmallVec::new(),
476            pending_constants: SmallVec::new(),
477            pending_constants_size: 0,
478            pending_traps: SmallVec::new(),
479            pending_fixup_records: SmallVec::new(),
480            pending_fixup_deadline: u32::MAX,
481            fixup_records: Default::default(),
482            latest_branches: SmallVec::new(),
483            labels_at_tail: SmallVec::new(),
484            labels_at_tail_off: 0,
485            constants: Default::default(),
486            used_constants: Default::default(),
487            open_patchable: false,
488            frame_layout: None,
489        }
490    }
491
492    /// Current offset from start of buffer.
493    pub fn cur_offset(&self) -> CodeOffset {
494        self.data.len() as CodeOffset
495    }
496
497    /// Add a byte.
498    pub fn put1(&mut self, value: u8) {
499        self.data.push(value);
500
501        // Post-invariant: conceptual-labels_at_tail contains a complete and
502        // precise list of labels bound at `cur_offset()`. We have advanced
503        // `cur_offset()`, hence if it had been equal to `labels_at_tail_off`
504        // before, it is not anymore (and it cannot become equal, because
505        // `labels_at_tail_off` is always <= `cur_offset()`). Thus the list is
506        // conceptually empty (even though it is only lazily cleared). No labels
507        // can be bound at this new offset (by invariant on `label_offsets`).
508        // Hence the invariant holds.
509    }
510
511    /// Add 2 bytes.
512    pub fn put2(&mut self, value: u16) {
513        let bytes = value.to_le_bytes();
514        self.data.extend_from_slice(&bytes[..]);
515
516        // Post-invariant: as for `put1()`.
517    }
518
519    /// Add 4 bytes.
520    pub fn put4(&mut self, value: u32) {
521        let bytes = value.to_le_bytes();
522        self.data.extend_from_slice(&bytes[..]);
523
524        // Post-invariant: as for `put1()`.
525    }
526
527    /// Add 8 bytes.
528    pub fn put8(&mut self, value: u64) {
529        let bytes = value.to_le_bytes();
530        self.data.extend_from_slice(&bytes[..]);
531
532        // Post-invariant: as for `put1()`.
533    }
534
535    /// Add a slice of bytes.
536    pub fn put_data(&mut self, data: &[u8]) {
537        self.data.extend_from_slice(data);
538
539        // Post-invariant: as for `put1()`.
540    }
541
542    /// Reserve appended space and return a mutable slice referring to it.
543    pub fn get_appended_space(&mut self, len: usize) -> &mut [u8] {
544        let off = self.data.len();
545        let new_len = self.data.len() + len;
546        self.data.resize(new_len, 0);
547        &mut self.data[off..]
548
549        // Post-invariant: as for `put1()`.
550    }
551
552    /// Align up to the given alignment.
553    pub fn align_to(&mut self, align_to: CodeOffset) {
554        trace!("MachBuffer: align to {}", align_to);
555        assert!(
556            align_to.is_power_of_two(),
557            "{align_to} is not a power of two"
558        );
559        while self.cur_offset() & (align_to - 1) != 0 {
560            self.put1(0);
561        }
562
563        // Post-invariant: as for `put1()`.
564    }
565
566    /// Begin a region of patchable code. There is one requirement for the
567    /// code that is emitted: It must not introduce any instructions that
568    /// could be chomped (branches are an example of this). In other words,
569    /// you must not call [`MachBuffer::add_cond_branch`] or
570    /// [`MachBuffer::add_uncond_branch`] between calls to this method and
571    /// [`MachBuffer::end_patchable`].
572    pub fn start_patchable(&mut self) -> OpenPatchRegion {
573        assert!(!self.open_patchable, "Patchable regions may not be nested");
574        self.open_patchable = true;
575        OpenPatchRegion(usize::try_from(self.cur_offset()).unwrap())
576    }
577
578    /// End a region of patchable code, yielding a [`PatchRegion`] value that
579    /// can be consumed later to produce a one-off mutable slice to the
580    /// associated region of the data buffer.
581    pub fn end_patchable(&mut self, open: OpenPatchRegion) -> PatchRegion {
582        // No need to assert the state of `open_patchable` here, as we take
583        // ownership of the only `OpenPatchable` value.
584        self.open_patchable = false;
585        let end = usize::try_from(self.cur_offset()).unwrap();
586        PatchRegion { range: open.0..end }
587    }
588
589    /// Allocate a `Label` to refer to some offset. May not be bound to a fixed
590    /// offset yet.
591    pub fn get_label(&mut self) -> MachLabel {
592        let l = self.label_offsets.len() as u32;
593        self.label_offsets.push(UNKNOWN_LABEL_OFFSET);
594        self.label_aliases.push(UNKNOWN_LABEL);
595        trace!("MachBuffer: new label -> {:?}", MachLabel(l));
596        MachLabel(l)
597
598        // Post-invariant: the only mutation is to add a new label; it has no
599        // bound offset yet, so it trivially satisfies all invariants.
600    }
601
602    /// Reserve the first N MachLabels for blocks.
603    pub fn reserve_labels_for_blocks(&mut self, blocks: usize) {
604        trace!("MachBuffer: first {} labels are for blocks", blocks);
605        debug_assert!(self.label_offsets.is_empty());
606        self.label_offsets.resize(blocks, UNKNOWN_LABEL_OFFSET);
607        self.label_aliases.resize(blocks, UNKNOWN_LABEL);
608
609        // Post-invariant: as for `get_label()`.
610    }
611
612    /// Registers metadata in this `MachBuffer` about the `constants` provided.
613    ///
614    /// This will record the size/alignment of all constants which will prepare
615    /// them for emission later on.
616    pub fn register_constants(&mut self, constants: &VCodeConstants) {
617        for (c, val) in constants.iter() {
618            self.register_constant(&c, val);
619        }
620    }
621
622    /// Similar to [`MachBuffer::register_constants`] but registers a
623    /// single constant metadata. This function is useful in
624    /// situations where not all constants are known at the time of
625    /// emission.
626    pub fn register_constant(&mut self, constant: &VCodeConstant, data: &VCodeConstantData) {
627        let c2 = self.constants.push(MachBufferConstant {
628            upcoming_label: None,
629            align: data.alignment(),
630            size: data.as_slice().len(),
631        });
632        assert_eq!(*constant, c2);
633    }
634
635    /// Completes constant emission by iterating over `self.used_constants` and
636    /// filling in the "holes" with the constant values provided by `constants`.
637    ///
638    /// Returns the alignment required for this entire buffer. Alignment starts
639    /// at the ISA's minimum function alignment and can be increased due to
640    /// constant requirements.
641    fn finish_constants(&mut self, constants: &VCodeConstants) -> u32 {
642        let mut alignment = self.min_alignment;
643        for (constant, offset) in mem::take(&mut self.used_constants) {
644            let constant = constants.get(constant);
645            let data = constant.as_slice();
646            self.data[offset as usize..][..data.len()].copy_from_slice(data);
647            alignment = constant.alignment().max(alignment);
648        }
649        alignment
650    }
651
652    /// Returns a label that can be used to refer to the `constant` provided.
653    ///
654    /// This will automatically defer a new constant to be emitted for
655    /// `constant` if it has not been previously emitted. Note that this
656    /// function may return a different label for the same constant at
657    /// different points in time. The label is valid to use only from the
658    /// current location; the MachBuffer takes care to emit the same constant
659    /// multiple times if needed so the constant is always in range.
660    pub fn get_label_for_constant(&mut self, constant: VCodeConstant) -> MachLabel {
661        let MachBufferConstant {
662            align,
663            size,
664            upcoming_label,
665        } = self.constants[constant];
666        if let Some(label) = upcoming_label {
667            return label;
668        }
669
670        let label = self.get_label();
671        trace!(
672            "defer constant: eventually emit {size} bytes aligned \
673             to {align} at label {label:?}",
674        );
675        self.pending_constants.push(constant);
676        self.pending_constants_size += size as u32;
677        self.constants[constant].upcoming_label = Some(label);
678        label
679    }
680
681    /// Bind a label to the current offset. A label can only be bound once.
682    pub fn bind_label(&mut self, label: MachLabel, ctrl_plane: &mut ControlPlane) {
683        trace!(
684            "MachBuffer: bind label {:?} at offset {}",
685            label,
686            self.cur_offset()
687        );
688        debug_assert_eq!(self.label_offsets[label.0 as usize], UNKNOWN_LABEL_OFFSET);
689        debug_assert_eq!(self.label_aliases[label.0 as usize], UNKNOWN_LABEL);
690        let offset = self.cur_offset();
691        self.label_offsets[label.0 as usize] = offset;
692        self.lazily_clear_labels_at_tail();
693        self.labels_at_tail.push(label);
694
695        // Invariants hold: bound offset of label is <= cur_offset (in fact it
696        // is equal). If the `labels_at_tail` list was complete and precise
697        // before, it is still, because we have bound this label to the current
698        // offset and added it to the list (which contains all labels at the
699        // current offset).
700
701        self.optimize_branches(ctrl_plane);
702
703        // Post-invariant: by `optimize_branches()` (see argument there).
704    }
705
706    /// Lazily clear `labels_at_tail` if the tail offset has moved beyond the
707    /// offset that it applies to.
708    fn lazily_clear_labels_at_tail(&mut self) {
709        let offset = self.cur_offset();
710        if offset > self.labels_at_tail_off {
711            self.labels_at_tail_off = offset;
712            self.labels_at_tail.clear();
713        }
714
715        // Post-invariant: either labels_at_tail_off was at cur_offset, and
716        // state is untouched, or was less than cur_offset, in which case the
717        // labels_at_tail list was conceptually empty, and is now actually
718        // empty.
719    }
720
721    /// Resolve a label to an offset, if known. May return `UNKNOWN_LABEL_OFFSET`.
722    pub(crate) fn resolve_label_offset(&self, mut label: MachLabel) -> CodeOffset {
723        let mut iters = 0;
724        while self.label_aliases[label.0 as usize] != UNKNOWN_LABEL {
725            label = self.label_aliases[label.0 as usize];
726            // To protect against an infinite loop (despite our assurances to
727            // ourselves that the invariants make this impossible), assert out
728            // after 1M iterations. The number of basic blocks is limited
729            // in most contexts anyway so this should be impossible to hit with
730            // a legitimate input.
731            iters += 1;
732            assert!(iters < 1_000_000, "Unexpected cycle in label aliases");
733        }
734        self.label_offsets[label.0 as usize]
735
736        // Post-invariant: no mutations.
737    }
738
739    /// Emit a reference to the given label with the given reference type (i.e.,
740    /// branch-instruction format) at the current offset.  This is like a
741    /// relocation, but handled internally.
742    ///
743    /// This can be called before the branch is actually emitted; fixups will
744    /// not happen until an island is emitted or the buffer is finished.
745    pub fn use_label_at_offset(&mut self, offset: CodeOffset, label: MachLabel, kind: I::LabelUse) {
746        trace!(
747            "MachBuffer: use_label_at_offset: offset {} label {:?} kind {:?}",
748            offset, label, kind
749        );
750
751        // Add the fixup, and update the worst-case island size based on a
752        // veneer for this label use.
753        let fixup = MachLabelFixup {
754            label,
755            offset,
756            kind,
757        };
758        self.pending_fixup_deadline = self.pending_fixup_deadline.min(fixup.deadline());
759        self.pending_fixup_records.push(fixup);
760
761        // Post-invariant: no mutations to branches/labels data structures.
762    }
763
764    /// Inform the buffer of an unconditional branch at the given offset,
765    /// targeting the given label. May be used to optimize branches.
766    /// The last added label-use must correspond to this branch.
767    /// This must be called when the current offset is equal to `start`; i.e.,
768    /// before actually emitting the branch. This implies that for a branch that
769    /// uses a label and is eligible for optimizations by the MachBuffer, the
770    /// proper sequence is:
771    ///
772    /// - Call `use_label_at_offset()` to emit the fixup record.
773    /// - Call `add_uncond_branch()` to make note of the branch.
774    /// - Emit the bytes for the branch's machine code.
775    ///
776    /// Additional requirement: no labels may be bound between `start` and `end`
777    /// (exclusive on both ends).
778    pub fn add_uncond_branch(&mut self, start: CodeOffset, end: CodeOffset, target: MachLabel) {
779        debug_assert!(
780            !self.open_patchable,
781            "Branch instruction inserted within a patchable region"
782        );
783        assert!(self.cur_offset() == start);
784        debug_assert!(end > start);
785        assert!(!self.pending_fixup_records.is_empty());
786        let fixup = self.pending_fixup_records.len() - 1;
787        self.lazily_clear_labels_at_tail();
788        self.latest_branches.push(MachBranch {
789            start,
790            end,
791            target,
792            fixup,
793            inverted: None,
794            labels_at_this_branch: self.labels_at_tail.clone(),
795        });
796
797        // Post-invariant: we asserted branch start is current tail; the list of
798        // labels at branch is cloned from list of labels at current tail.
799    }
800
801    /// Inform the buffer of a conditional branch at the given offset,
802    /// targeting the given label. May be used to optimize branches.
803    /// The last added label-use must correspond to this branch.
804    ///
805    /// Additional requirement: no labels may be bound between `start` and `end`
806    /// (exclusive on both ends).
807    pub fn add_cond_branch(
808        &mut self,
809        start: CodeOffset,
810        end: CodeOffset,
811        target: MachLabel,
812        inverted: &[u8],
813    ) {
814        debug_assert!(
815            !self.open_patchable,
816            "Branch instruction inserted within a patchable region"
817        );
818        assert!(self.cur_offset() == start);
819        debug_assert!(end > start);
820        assert!(!self.pending_fixup_records.is_empty());
821        debug_assert!(
822            inverted.len() == (end - start) as usize,
823            "branch length = {}, but inverted length = {}",
824            end - start,
825            inverted.len()
826        );
827        let fixup = self.pending_fixup_records.len() - 1;
828        let inverted = Some(SmallVec::from(inverted));
829        self.lazily_clear_labels_at_tail();
830        self.latest_branches.push(MachBranch {
831            start,
832            end,
833            target,
834            fixup,
835            inverted,
836            labels_at_this_branch: self.labels_at_tail.clone(),
837        });
838
839        // Post-invariant: we asserted branch start is current tail; labels at
840        // branch list is cloned from list of labels at current tail.
841    }
842
843    fn truncate_last_branch(&mut self) {
844        debug_assert!(
845            !self.open_patchable,
846            "Branch instruction truncated within a patchable region"
847        );
848
849        self.lazily_clear_labels_at_tail();
850        // Invariants hold at this point.
851
852        let b = self.latest_branches.pop().unwrap();
853        assert!(b.end == self.cur_offset());
854
855        // State:
856        //    [PRE CODE]
857        //  Offset b.start, b.labels_at_this_branch:
858        //    [BRANCH CODE]
859        //  cur_off, self.labels_at_tail -->
860        //    (end of buffer)
861        self.data.truncate(b.start as usize);
862        self.pending_fixup_records.truncate(b.fixup);
863
864        // Trim srclocs and debug tags now past the end of the buffer.
865        while let Some(last_srcloc) = self.srclocs.last_mut() {
866            if last_srcloc.end <= b.start {
867                break;
868            }
869            if last_srcloc.start < b.start {
870                last_srcloc.end = b.start;
871                break;
872            }
873            self.srclocs.pop();
874        }
875        while let Some(last_debug_tag) = self.debug_tags.last() {
876            if last_debug_tag.offset <= b.start {
877                break;
878            }
879            self.debug_tags.pop();
880        }
881
882        // State:
883        //    [PRE CODE]
884        //  cur_off, Offset b.start, b.labels_at_this_branch:
885        //    (end of buffer)
886        //
887        //  self.labels_at_tail -->  (past end of buffer)
888        let cur_off = self.cur_offset();
889        self.labels_at_tail_off = cur_off;
890        // State:
891        //    [PRE CODE]
892        //  cur_off, Offset b.start, b.labels_at_this_branch,
893        //  self.labels_at_tail:
894        //    (end of buffer)
895        //
896        // resolve_label_offset(l) for l in labels_at_tail:
897        //    (past end of buffer)
898
899        trace!(
900            "truncate_last_branch: truncated {:?}; off now {}",
901            b, cur_off
902        );
903
904        // Fix up resolved label offsets for labels at tail.
905        for &l in &self.labels_at_tail {
906            self.label_offsets[l.0 as usize] = cur_off;
907        }
908        // Old labels_at_this_branch are now at cur_off.
909        self.labels_at_tail.extend(b.labels_at_this_branch);
910
911        // Post-invariant: this operation is defined to truncate the buffer,
912        // which moves cur_off backward, and to move labels at the end of the
913        // buffer back to the start-of-branch offset.
914        //
915        // latest_branches satisfies all invariants:
916        // - it has no branches past the end of the buffer (branches are in
917        //   order, we removed the last one, and we truncated the buffer to just
918        //   before the start of that branch)
919        // - no labels were moved to lower offsets than the (new) cur_off, so
920        //   the labels_at_this_branch list for any other branch need not change.
921        //
922        // labels_at_tail satisfies all invariants:
923        // - all labels that were at the tail after the truncated branch are
924        //   moved backward to just before the branch, which becomes the new tail;
925        //   thus every element in the list should remain (ensured by `.extend()`
926        //   above).
927        // - all labels that refer to the new tail, which is the start-offset of
928        //   the truncated branch, must be present. The `labels_at_this_branch`
929        //   list in the truncated branch's record is a complete and precise list
930        //   of exactly these labels; we append these to labels_at_tail.
931        // - labels_at_tail_off is at cur_off after truncation occurs, so the
932        //   list is valid (not to be lazily cleared).
933        //
934        // The stated operation was performed:
935        // - For each label at the end of the buffer prior to this method, it
936        //   now resolves to the new (truncated) end of the buffer: it must have
937        //   been in `labels_at_tail` (this list is precise and complete, and
938        //   the tail was at the end of the truncated branch on entry), and we
939        //   iterate over this list and set `label_offsets` to the new tail.
940        //   None of these labels could have been an alias (by invariant), so
941        //   `label_offsets` is authoritative for each.
942        // - No other labels will be past the end of the buffer, because of the
943        //   requirement that no labels be bound to the middle of branch ranges
944        //   (see comments to `add_{cond,uncond}_branch()`).
945        // - The buffer is truncated to just before the last branch, and the
946        //   fixup record referring to that last branch is removed.
947    }
948
949    /// Performs various optimizations on branches pointing at the current label.
950    pub fn optimize_branches(&mut self, ctrl_plane: &mut ControlPlane) {
951        if ctrl_plane.get_decision() {
952            return;
953        }
954
955        self.lazily_clear_labels_at_tail();
956        // Invariants valid at this point.
957
958        trace!(
959            "enter optimize_branches:\n b = {:?}\n l = {:?}\n f = {:?}",
960            self.latest_branches, self.labels_at_tail, self.pending_fixup_records
961        );
962
963        // We continue to munch on branches at the tail of the buffer until no
964        // more rules apply. Note that the loop only continues if a branch is
965        // actually truncated (or if labels are redirected away from a branch),
966        // so this always makes progress.
967        while let Some(b) = self.latest_branches.last() {
968            let cur_off = self.cur_offset();
969            trace!("optimize_branches: last branch {:?} at off {}", b, cur_off);
970            // If there has been any code emission since the end of the last branch or
971            // label definition, then there's nothing we can edit (because we
972            // don't move code once placed, only back up and overwrite), so
973            // clear the records and finish.
974            if b.end < cur_off {
975                break;
976            }
977
978            // If the "labels at this branch" list on this branch is
979            // longer than a threshold, don't do any simplification,
980            // and let the branch remain to separate those labels from
981            // the current tail. This avoids quadratic behavior (see
982            // #3468): otherwise, if a long string of "goto next;
983            // next:" patterns are emitted, all of the labels will
984            // coalesce into a long list of aliases for the current
985            // buffer tail. We must track all aliases of the current
986            // tail for correctness, but we are also allowed to skip
987            // optimization (removal) of any branch, so we take the
988            // escape hatch here and let it stand. In effect this
989            // "spreads" the many thousands of labels in the
990            // pathological case among an actual (harmless but
991            // suboptimal) instruction once per N labels.
992            if b.labels_at_this_branch.len() > LABEL_LIST_THRESHOLD {
993                break;
994            }
995
996            // Invariant: we are looking at a branch that ends at the tail of
997            // the buffer.
998
999            // For any branch, conditional or unconditional:
1000            // - If the target is a label at the current offset, then remove
1001            //   the conditional branch, and reset all labels that targeted
1002            //   the current offset (end of branch) to the truncated
1003            //   end-of-code.
1004            //
1005            // Preserves execution semantics: a branch to its own fallthrough
1006            // address is equivalent to a no-op; in both cases, nextPC is the
1007            // fallthrough.
1008            if self.resolve_label_offset(b.target) == cur_off {
1009                trace!("branch with target == cur off; truncating");
1010                self.truncate_last_branch();
1011                continue;
1012            }
1013
1014            // If latest is an unconditional branch:
1015            //
1016            // - If the branch's target is not its own start address, then for
1017            //   each label at the start of branch, make the label an alias of the
1018            //   branch target, and remove the label from the "labels at this
1019            //   branch" list.
1020            //
1021            //   - Preserves execution semantics: an unconditional branch's
1022            //     only effect is to set PC to a new PC; this change simply
1023            //     collapses one step in the step-semantics.
1024            //
1025            //   - Post-invariant: the labels that were bound to the start of
1026            //     this branch become aliases, so they must not be present in any
1027            //     labels-at-this-branch list or the labels-at-tail list. The
1028            //     labels are removed form the latest-branch record's
1029            //     labels-at-this-branch list, and are never placed in the
1030            //     labels-at-tail list. Furthermore, it is correct that they are
1031            //     not in either list, because they are now aliases, and labels
1032            //     that are aliases remain aliases forever.
1033            //
1034            // - If there is a prior unconditional branch that ends just before
1035            //   this one begins, and this branch has no labels bound to its
1036            //   start, then we can truncate this branch, because it is entirely
1037            //   unreachable (we have redirected all labels that make it
1038            //   reachable otherwise). Do so and continue around the loop.
1039            //
1040            //   - Preserves execution semantics: the branch is unreachable,
1041            //     because execution can only flow into an instruction from the
1042            //     prior instruction's fallthrough or from a branch bound to that
1043            //     instruction's start offset. Unconditional branches have no
1044            //     fallthrough, so if the prior instruction is an unconditional
1045            //     branch, no fallthrough entry can happen. The
1046            //     labels-at-this-branch list is complete (by invariant), so if it
1047            //     is empty, then the instruction is entirely unreachable. Thus,
1048            //     it can be removed.
1049            //
1050            //   - Post-invariant: ensured by truncate_last_branch().
1051            //
1052            // - If there is a prior conditional branch whose target label
1053            //   resolves to the current offset (branches around the
1054            //   unconditional branch), then remove the unconditional branch,
1055            //   and make the target of the unconditional the target of the
1056            //   conditional instead.
1057            //
1058            //   - Preserves execution semantics: previously we had:
1059            //
1060            //         L1:
1061            //            cond_br L2
1062            //            br L3
1063            //         L2:
1064            //            (end of buffer)
1065            //
1066            //     by removing the last branch, we have:
1067            //
1068            //         L1:
1069            //            cond_br L2
1070            //         L2:
1071            //            (end of buffer)
1072            //
1073            //     we then fix up the records for the conditional branch to
1074            //     have:
1075            //
1076            //         L1:
1077            //           cond_br.inverted L3
1078            //         L2:
1079            //
1080            //     In the original code, control flow reaches L2 when the
1081            //     conditional branch's predicate is true, and L3 otherwise. In
1082            //     the optimized code, the same is true.
1083            //
1084            //   - Post-invariant: all edits to latest_branches and
1085            //     labels_at_tail are performed by `truncate_last_branch()`,
1086            //     which maintains the invariants at each step.
1087
1088            if b.is_uncond() {
1089                // Set any label equal to current branch's start as an alias of
1090                // the branch's target, if the target is not the branch itself
1091                // (i.e., an infinite loop).
1092                //
1093                // We cannot perform this aliasing if the target of this branch
1094                // ultimately aliases back here; if so, we need to keep this
1095                // branch, so break out of this loop entirely (and clear the
1096                // latest-branches list below).
1097                //
1098                // Note that this check is what prevents cycles from forming in
1099                // `self.label_aliases`. To see why, consider an arbitrary start
1100                // state:
1101                //
1102                // label_aliases[L1] = L2, label_aliases[L2] = L3, ..., up to
1103                // Ln, which is not aliased.
1104                //
1105                // We would create a cycle if we assigned label_aliases[Ln]
1106                // = L1.  Note that the below assignment is the only write
1107                // to label_aliases.
1108                //
1109                // By our other invariants, we have that Ln (`l` below)
1110                // resolves to the offset `b.start`, because it is in the
1111                // set `b.labels_at_this_branch`.
1112                //
1113                // If L1 were already aliased, through some arbitrarily deep
1114                // chain, to Ln, then it must also resolve to this offset
1115                // `b.start`.
1116                //
1117                // By checking the resolution of `L1` against this offset,
1118                // and aborting this branch-simplification if they are
1119                // equal, we prevent the below assignment from ever creating
1120                // a cycle.
1121                if self.resolve_label_offset(b.target) != b.start {
1122                    let redirected = b.labels_at_this_branch.len();
1123                    for &l in &b.labels_at_this_branch {
1124                        trace!(
1125                            " -> label at start of branch {:?} redirected to target {:?}",
1126                            l, b.target
1127                        );
1128                        self.label_aliases[l.0 as usize] = b.target;
1129                        // NOTE: we continue to ensure the invariant that labels
1130                        // pointing to tail of buffer are in `labels_at_tail`
1131                        // because we already ensured above that the last branch
1132                        // cannot have a target of `cur_off`; so we never have
1133                        // to put the label into `labels_at_tail` when moving it
1134                        // here.
1135                    }
1136                    // Maintain invariant: all branches have been redirected
1137                    // and are no longer pointing at the start of this branch.
1138                    let mut_b = self.latest_branches.last_mut().unwrap();
1139                    mut_b.labels_at_this_branch.clear();
1140
1141                    if redirected > 0 {
1142                        trace!(" -> after label redirects, restarting loop");
1143                        continue;
1144                    }
1145                } else {
1146                    break;
1147                }
1148
1149                let b = self.latest_branches.last().unwrap();
1150
1151                // Examine any immediately preceding branch.
1152                if self.latest_branches.len() > 1 {
1153                    let prev_b = &self.latest_branches[self.latest_branches.len() - 2];
1154                    trace!(" -> more than one branch; prev_b = {:?}", prev_b);
1155                    // This uncond is immediately after another uncond; we
1156                    // should have already redirected labels to this uncond away
1157                    // (but check to be sure); so we can truncate this uncond.
1158                    if prev_b.is_uncond()
1159                        && prev_b.end == b.start
1160                        && b.labels_at_this_branch.is_empty()
1161                    {
1162                        trace!(" -> uncond follows another uncond; truncating");
1163                        self.truncate_last_branch();
1164                        continue;
1165                    }
1166
1167                    // This uncond is immediately after a conditional, and the
1168                    // conditional's target is the end of this uncond, and we've
1169                    // already redirected labels to this uncond away; so we can
1170                    // truncate this uncond, flip the sense of the conditional, and
1171                    // set the conditional's target (in `latest_branches` and in
1172                    // `fixup_records`) to the uncond's target.
1173                    if prev_b.is_cond()
1174                        && prev_b.end == b.start
1175                        && self.resolve_label_offset(prev_b.target) == cur_off
1176                    {
1177                        trace!(
1178                            " -> uncond follows a conditional, and conditional's target resolves to current offset"
1179                        );
1180                        // Save the target of the uncond (this becomes the
1181                        // target of the cond), and truncate the uncond.
1182                        let target = b.target;
1183                        let data = prev_b.inverted.clone().unwrap();
1184                        self.truncate_last_branch();
1185
1186                        // Mutate the code and cond branch.
1187                        let off_before_edit = self.cur_offset();
1188                        let prev_b = self.latest_branches.last_mut().unwrap();
1189                        let not_inverted = SmallVec::from(
1190                            &self.data[(prev_b.start as usize)..(prev_b.end as usize)],
1191                        );
1192
1193                        // Low-level edit: replaces bytes of branch with
1194                        // inverted form. cur_off remains the same afterward, so
1195                        // we do not need to modify label data structures.
1196                        self.data.truncate(prev_b.start as usize);
1197                        self.data.extend_from_slice(&data[..]);
1198
1199                        // Save the original code as the inversion of the
1200                        // inverted branch, in case we later edit this branch
1201                        // again.
1202                        prev_b.inverted = Some(not_inverted);
1203                        self.pending_fixup_records[prev_b.fixup].label = target;
1204                        trace!(" -> reassigning target of condbr to {:?}", target);
1205                        prev_b.target = target;
1206                        debug_assert_eq!(off_before_edit, self.cur_offset());
1207                        continue;
1208                    }
1209                }
1210            }
1211
1212            // If we couldn't do anything with the last branch, then break.
1213            break;
1214        }
1215
1216        self.purge_latest_branches();
1217
1218        trace!(
1219            "leave optimize_branches:\n b = {:?}\n l = {:?}\n f = {:?}",
1220            self.latest_branches, self.labels_at_tail, self.pending_fixup_records
1221        );
1222    }
1223
1224    fn purge_latest_branches(&mut self) {
1225        // All of our branch simplification rules work only if a branch ends at
1226        // the tail of the buffer, with no following code; and branches are in
1227        // order in latest_branches; so if the last entry ends prior to
1228        // cur_offset, then clear all entries.
1229        let cur_off = self.cur_offset();
1230        if let Some(l) = self.latest_branches.last() {
1231            if l.end < cur_off {
1232                trace!("purge_latest_branches: removing branch {:?}", l);
1233                self.latest_branches.clear();
1234            }
1235        }
1236
1237        // Post-invariant: no invariant requires any branch to appear in
1238        // `latest_branches`; it is always optional. The list-clear above thus
1239        // preserves all semantics.
1240    }
1241
1242    /// Emit a trap at some point in the future with the specified code and
1243    /// stack map.
1244    ///
1245    /// This function returns a [`MachLabel`] which will be the future address
1246    /// of the trap. Jumps should refer to this label, likely by using the
1247    /// [`MachBuffer::use_label_at_offset`] method, to get a relocation
1248    /// patched in once the address of the trap is known.
1249    ///
1250    /// This will batch all traps into the end of the function.
1251    pub fn defer_trap(&mut self, code: TrapCode) -> MachLabel {
1252        let label = self.get_label();
1253        self.pending_traps.push(MachLabelTrap {
1254            label,
1255            code,
1256            loc: self.cur_srcloc.map(|(_start, loc)| loc),
1257        });
1258        label
1259    }
1260
1261    /// Is an island needed within the next N bytes?
1262    pub fn island_needed(&self, distance: CodeOffset) -> bool {
1263        let deadline = match self.fixup_records.peek() {
1264            Some(fixup) => fixup.deadline().min(self.pending_fixup_deadline),
1265            None => self.pending_fixup_deadline,
1266        };
1267        deadline < u32::MAX && self.worst_case_end_of_island(distance) > deadline
1268    }
1269
1270    /// Returns the maximal offset that islands can reach if `distance` more
1271    /// bytes are appended.
1272    ///
1273    /// This is used to determine if veneers need insertions since jumps that
1274    /// can't reach past this point must get a veneer of some form.
1275    fn worst_case_end_of_island(&self, distance: CodeOffset) -> CodeOffset {
1276        // Assume that all fixups will require veneers and that the veneers are
1277        // the worst-case size for each platform. This is an over-generalization
1278        // to avoid iterating over the `fixup_records` list or maintaining
1279        // information about it as we go along.
1280        let island_worst_case_size = ((self.fixup_records.len() + self.pending_fixup_records.len())
1281            as u32)
1282            * (I::LabelUse::worst_case_veneer_size())
1283            + self.pending_constants_size
1284            + (self.pending_traps.len() * I::TRAP_OPCODE.len()) as u32;
1285        self.cur_offset()
1286            .saturating_add(distance)
1287            .saturating_add(island_worst_case_size)
1288    }
1289
1290    /// Emit all pending constants and required pending veneers.
1291    ///
1292    /// Should only be called if `island_needed()` returns true, i.e., if we
1293    /// actually reach a deadline. It's not necessarily a problem to do so
1294    /// otherwise but it may result in unnecessary work during emission.
1295    pub fn emit_island(&mut self, distance: CodeOffset, ctrl_plane: &mut ControlPlane) {
1296        self.emit_island_maybe_forced(ForceVeneers::No, distance, ctrl_plane);
1297    }
1298
1299    /// Same as `emit_island`, but an internal API with a `force_veneers`
1300    /// argument to force all veneers to always get emitted for debugging.
1301    fn emit_island_maybe_forced(
1302        &mut self,
1303        force_veneers: ForceVeneers,
1304        distance: CodeOffset,
1305        ctrl_plane: &mut ControlPlane,
1306    ) {
1307        // We're going to purge fixups, so no latest-branch editing can happen
1308        // anymore.
1309        self.latest_branches.clear();
1310
1311        // End the current location tracking since anything emitted during this
1312        // function shouldn't be attributed to whatever the current source
1313        // location is.
1314        //
1315        // Note that the current source location, if it's set right now, will be
1316        // restored at the end of this island emission.
1317        let cur_loc = self.cur_srcloc.map(|(_, loc)| loc);
1318        if cur_loc.is_some() {
1319            self.end_srcloc();
1320        }
1321
1322        let forced_threshold = self.worst_case_end_of_island(distance);
1323
1324        // First flush out all traps/constants so we have more labels in case
1325        // fixups are applied against these labels.
1326        //
1327        // Note that traps are placed first since this typically happens at the
1328        // end of the function and for disassemblers we try to keep all the code
1329        // contiguously together.
1330        for MachLabelTrap { label, code, loc } in mem::take(&mut self.pending_traps) {
1331            // If this trap has source information associated with it then
1332            // emit this information for the trap instruction going out now too.
1333            if let Some(loc) = loc {
1334                self.start_srcloc(loc);
1335            }
1336            self.align_to(I::LabelUse::ALIGN);
1337            self.bind_label(label, ctrl_plane);
1338            self.add_trap(code);
1339            self.put_data(I::TRAP_OPCODE);
1340            if loc.is_some() {
1341                self.end_srcloc();
1342            }
1343        }
1344
1345        for constant in mem::take(&mut self.pending_constants) {
1346            let MachBufferConstant { align, size, .. } = self.constants[constant];
1347            let label = self.constants[constant].upcoming_label.take().unwrap();
1348            self.align_to(align);
1349            self.bind_label(label, ctrl_plane);
1350            self.used_constants.push((constant, self.cur_offset()));
1351            self.get_appended_space(size);
1352        }
1353
1354        // Either handle all pending fixups because they're ready or move them
1355        // onto the `BinaryHeap` tracking all pending fixups if they aren't
1356        // ready.
1357        assert!(self.latest_branches.is_empty());
1358        for fixup in mem::take(&mut self.pending_fixup_records) {
1359            if self.should_apply_fixup(&fixup, forced_threshold) {
1360                self.handle_fixup(fixup, force_veneers, forced_threshold);
1361            } else {
1362                self.fixup_records.push(fixup);
1363            }
1364        }
1365        self.pending_fixup_deadline = u32::MAX;
1366        while let Some(fixup) = self.fixup_records.peek() {
1367            trace!("emit_island: fixup {:?}", fixup);
1368
1369            // If this fixup shouldn't be applied, that means its label isn't
1370            // defined yet and there'll be remaining space to apply a veneer if
1371            // necessary in the future after this island. In that situation
1372            // because `fixup_records` is sorted by deadline this loop can
1373            // exit.
1374            if !self.should_apply_fixup(fixup, forced_threshold) {
1375                break;
1376            }
1377
1378            let fixup = self.fixup_records.pop().unwrap();
1379            self.handle_fixup(fixup, force_veneers, forced_threshold);
1380        }
1381
1382        if let Some(loc) = cur_loc {
1383            self.start_srcloc(loc);
1384        }
1385    }
1386
1387    fn should_apply_fixup(&self, fixup: &MachLabelFixup<I>, forced_threshold: CodeOffset) -> bool {
1388        let label_offset = self.resolve_label_offset(fixup.label);
1389        label_offset != UNKNOWN_LABEL_OFFSET || fixup.deadline() < forced_threshold
1390    }
1391
1392    fn handle_fixup(
1393        &mut self,
1394        fixup: MachLabelFixup<I>,
1395        force_veneers: ForceVeneers,
1396        forced_threshold: CodeOffset,
1397    ) {
1398        let MachLabelFixup {
1399            label,
1400            offset,
1401            kind,
1402        } = fixup;
1403        let start = offset as usize;
1404        let end = (offset + kind.patch_size()) as usize;
1405        let label_offset = self.resolve_label_offset(label);
1406
1407        if label_offset != UNKNOWN_LABEL_OFFSET {
1408            // If the offset of the label for this fixup is known then
1409            // we're going to do something here-and-now. We're either going
1410            // to patch the original offset because it's an in-bounds jump,
1411            // or we're going to generate a veneer, patch the fixup to jump
1412            // to the veneer, and then keep going.
1413            //
1414            // If the label comes after the original fixup, then we should
1415            // be guaranteed that the jump is in-bounds. Otherwise there's
1416            // a bug somewhere because this method wasn't called soon
1417            // enough. All forward-jumps are tracked and should get veneers
1418            // before their deadline comes and they're unable to jump
1419            // further.
1420            //
1421            // Otherwise if the label is before the fixup, then that's a
1422            // backwards jump. If it's past the maximum negative range
1423            // then we'll emit a veneer that to jump forward to which can
1424            // then jump backwards.
1425            let veneer_required = if label_offset >= offset {
1426                assert!((label_offset - offset) <= kind.max_pos_range());
1427                false
1428            } else {
1429                (offset - label_offset) > kind.max_neg_range()
1430            };
1431            trace!(
1432                " -> label_offset = {}, known, required = {} (pos {} neg {})",
1433                label_offset,
1434                veneer_required,
1435                kind.max_pos_range(),
1436                kind.max_neg_range()
1437            );
1438
1439            if (force_veneers == ForceVeneers::Yes && kind.supports_veneer()) || veneer_required {
1440                self.emit_veneer(label, offset, kind);
1441            } else {
1442                let slice = &mut self.data[start..end];
1443                trace!(
1444                    "patching in-range! slice = {slice:?}; offset = {offset:#x}; label_offset = {label_offset:#x}"
1445                );
1446                kind.patch(slice, offset, label_offset);
1447            }
1448        } else {
1449            // If the offset of this label is not known at this time then
1450            // that means that a veneer is required because after this
1451            // island the target can't be in range of the original target.
1452            assert!(forced_threshold - offset > kind.max_pos_range());
1453            self.emit_veneer(label, offset, kind);
1454        }
1455    }
1456
1457    /// Emits a "veneer" the `kind` code at `offset` to jump to `label`.
1458    ///
1459    /// This will generate extra machine code, using `kind`, to get a
1460    /// larger-jump-kind than `kind` allows. The code at `offset` is then
1461    /// patched to jump to our new code, and then the new code is enqueued for
1462    /// a fixup to get processed at some later time.
1463    fn emit_veneer(&mut self, label: MachLabel, offset: CodeOffset, kind: I::LabelUse) {
1464        // If this `kind` doesn't support a veneer then that's a bug in the
1465        // backend because we need to implement support for such a veneer.
1466        assert!(
1467            kind.supports_veneer(),
1468            "jump beyond the range of {kind:?} but a veneer isn't supported",
1469        );
1470
1471        // Allocate space for a veneer in the island.
1472        self.align_to(I::LabelUse::ALIGN);
1473        let veneer_offset = self.cur_offset();
1474        trace!("making a veneer at {}", veneer_offset);
1475        let start = offset as usize;
1476        let end = (offset + kind.patch_size()) as usize;
1477        let slice = &mut self.data[start..end];
1478        // Patch the original label use to refer to the veneer.
1479        trace!(
1480            "patching original at offset {} to veneer offset {}",
1481            offset, veneer_offset
1482        );
1483        kind.patch(slice, offset, veneer_offset);
1484        // Generate the veneer.
1485        let veneer_slice = self.get_appended_space(kind.veneer_size() as usize);
1486        let (veneer_fixup_off, veneer_label_use) =
1487            kind.generate_veneer(veneer_slice, veneer_offset);
1488        trace!(
1489            "generated veneer; fixup offset {}, label_use {:?}",
1490            veneer_fixup_off, veneer_label_use
1491        );
1492        // Register a new use of `label` with our new veneer fixup and
1493        // offset. This'll recalculate deadlines accordingly and
1494        // enqueue this fixup to get processed at some later
1495        // time.
1496        self.use_label_at_offset(veneer_fixup_off, label, veneer_label_use);
1497    }
1498
1499    fn finish_emission_maybe_forcing_veneers(
1500        &mut self,
1501        force_veneers: ForceVeneers,
1502        ctrl_plane: &mut ControlPlane,
1503    ) {
1504        while !self.pending_constants.is_empty()
1505            || !self.pending_traps.is_empty()
1506            || !self.fixup_records.is_empty()
1507            || !self.pending_fixup_records.is_empty()
1508        {
1509            // `emit_island()` will emit any pending veneers and constants, and
1510            // as a side-effect, will also take care of any fixups with resolved
1511            // labels eagerly.
1512            self.emit_island_maybe_forced(force_veneers, u32::MAX, ctrl_plane);
1513        }
1514
1515        // Ensure that all labels have been fixed up after the last island is emitted. This is a
1516        // full (release-mode) assert because an unresolved label means the emitted code is
1517        // incorrect.
1518        assert!(self.fixup_records.is_empty());
1519        assert!(self.pending_fixup_records.is_empty());
1520    }
1521
1522    /// Finish any deferred emissions and/or fixups.
1523    pub fn finish(
1524        mut self,
1525        constants: &VCodeConstants,
1526        ctrl_plane: &mut ControlPlane,
1527    ) -> MachBufferFinalized<Stencil> {
1528        let _tt = timing::vcode_emit_finish();
1529
1530        self.finish_emission_maybe_forcing_veneers(ForceVeneers::No, ctrl_plane);
1531
1532        let alignment = self.finish_constants(constants);
1533
1534        // Resolve all labels to their offsets.
1535        let finalized_relocs = self
1536            .relocs
1537            .iter()
1538            .map(|reloc| FinalizedMachReloc {
1539                offset: reloc.offset,
1540                kind: reloc.kind,
1541                addend: reloc.addend,
1542                target: match &reloc.target {
1543                    RelocTarget::ExternalName(name) => {
1544                        FinalizedRelocTarget::ExternalName(name.clone())
1545                    }
1546                    RelocTarget::Label(label) => {
1547                        FinalizedRelocTarget::Func(self.resolve_label_offset(*label))
1548                    }
1549                },
1550            })
1551            .collect();
1552
1553        let finalized_exception_handlers = self
1554            .exception_handlers
1555            .iter()
1556            .map(|handler| handler.finalize(|label| self.resolve_label_offset(label)))
1557            .collect();
1558
1559        let mut srclocs = self.srclocs;
1560        srclocs.sort_by_key(|entry| entry.start);
1561
1562        MachBufferFinalized {
1563            data: self.data,
1564            relocs: finalized_relocs,
1565            traps: self.traps,
1566            call_sites: self.call_sites,
1567            exception_handlers: finalized_exception_handlers,
1568            srclocs,
1569            debug_tags: self.debug_tags,
1570            debug_tag_pool: self.debug_tag_pool,
1571            user_stack_maps: self.user_stack_maps,
1572            unwind_info: self.unwind_info,
1573            alignment,
1574            frame_layout: self.frame_layout,
1575        }
1576    }
1577
1578    /// Add an external relocation at the given offset.
1579    pub fn add_reloc_at_offset<T: Into<RelocTarget> + Clone>(
1580        &mut self,
1581        offset: CodeOffset,
1582        kind: Reloc,
1583        target: &T,
1584        addend: Addend,
1585    ) {
1586        let target: RelocTarget = target.clone().into();
1587        // FIXME(#3277): This should use `I::LabelUse::from_reloc` to optionally
1588        // generate a label-use statement to track whether an island is possibly
1589        // needed to escape this function to actually get to the external name.
1590        // This is most likely to come up on AArch64 where calls between
1591        // functions use a 26-bit signed offset which gives +/- 64MB. This means
1592        // that if a function is 128MB in size and there's a call in the middle
1593        // it's impossible to reach the actual target. Also, while it's
1594        // technically possible to jump to the start of a function and then jump
1595        // further, island insertion below always inserts islands after
1596        // previously appended code so for Cranelift's own implementation this
1597        // is also a problem for 64MB functions on AArch64 which start with a
1598        // call instruction, those won't be able to escape.
1599        //
1600        // Ideally what needs to happen here is that a `LabelUse` is
1601        // transparently generated (or call-sites of this function are audited
1602        // to generate a `LabelUse` instead) and tracked internally. The actual
1603        // relocation would then change over time if and when a veneer is
1604        // inserted, where the relocation here would be patched by this
1605        // `MachBuffer` to jump to the veneer. The problem, though, is that all
1606        // this still needs to end up, in the case of a singular function,
1607        // generating a final relocation pointing either to this particular
1608        // relocation or to the veneer inserted. Additionally
1609        // `MachBuffer` needs the concept of a label which will never be
1610        // resolved, so `emit_island` doesn't trip over not actually ever
1611        // knowning what some labels are. Currently the loop in
1612        // `finish_emission_maybe_forcing_veneers` would otherwise infinitely
1613        // loop.
1614        //
1615        // For now this means that because relocs aren't tracked at all that
1616        // AArch64 functions have a rough size limits of 64MB. For now that's
1617        // somewhat reasonable and the failure mode is a panic in `MachBuffer`
1618        // when a relocation can't otherwise be resolved later, so it shouldn't
1619        // actually result in any memory unsafety or anything like that.
1620        self.relocs.push(MachReloc {
1621            offset,
1622            kind,
1623            target,
1624            addend,
1625        });
1626    }
1627
1628    /// Add an external relocation at the current offset.
1629    pub fn add_reloc<T: Into<RelocTarget> + Clone>(
1630        &mut self,
1631        kind: Reloc,
1632        target: &T,
1633        addend: Addend,
1634    ) {
1635        self.add_reloc_at_offset(self.data.len() as CodeOffset, kind, target, addend);
1636    }
1637
1638    /// Add a trap record at the current offset.
1639    pub fn add_trap(&mut self, code: TrapCode) {
1640        self.traps.push(MachTrap {
1641            offset: self.data.len() as CodeOffset,
1642            code,
1643        });
1644    }
1645
1646    /// Add a call-site record at the current offset.
1647    pub fn add_call_site(&mut self) {
1648        self.add_try_call_site(None, core::iter::empty());
1649    }
1650
1651    /// Add a call-site record at the current offset with exception
1652    /// handlers.
1653    pub fn add_try_call_site(
1654        &mut self,
1655        frame_offset: Option<u32>,
1656        exception_handlers: impl Iterator<Item = MachExceptionHandler>,
1657    ) {
1658        let start = u32::try_from(self.exception_handlers.len()).unwrap();
1659        self.exception_handlers.extend(exception_handlers);
1660        let end = u32::try_from(self.exception_handlers.len()).unwrap();
1661        let exception_handler_range = start..end;
1662
1663        self.call_sites.push(MachCallSite {
1664            ret_addr: self.data.len() as CodeOffset,
1665            frame_offset,
1666            exception_handler_range,
1667        });
1668    }
1669
1670    /// Add an unwind record at the current offset.
1671    pub fn add_unwind(&mut self, unwind: UnwindInst) {
1672        self.unwind_info.push((self.cur_offset(), unwind));
1673    }
1674
1675    /// Set the `SourceLoc` for code from this offset until the offset at the
1676    /// next call to `end_srcloc()`.
1677    /// Returns the current [CodeOffset] and [RelSourceLoc].
1678    pub fn start_srcloc(&mut self, loc: RelSourceLoc) -> (CodeOffset, RelSourceLoc) {
1679        let cur = (self.cur_offset(), loc);
1680        self.cur_srcloc = Some(cur);
1681        cur
1682    }
1683
1684    /// Mark the end of the `SourceLoc` segment started at the last
1685    /// `start_srcloc()` call.
1686    pub fn end_srcloc(&mut self) {
1687        let (start, loc) = self
1688            .cur_srcloc
1689            .take()
1690            .expect("end_srcloc() called without start_srcloc()");
1691        let end = self.cur_offset();
1692        // Skip zero-length extends.
1693        debug_assert!(end >= start);
1694        if end > start {
1695            self.srclocs.push(MachSrcLoc { start, end, loc });
1696        }
1697    }
1698
1699    /// Push a user stack map onto this buffer.
1700    ///
1701    /// The stack map is associated with the given `return_addr` code
1702    /// offset. This must be the PC for the instruction just *after* this stack
1703    /// map's associated instruction. For example in the sequence `call $foo;
1704    /// add r8, rax`, the `return_addr` must be the offset of the start of the
1705    /// `add` instruction.
1706    ///
1707    /// Stack maps must be pushed in sorted `return_addr` order.
1708    pub fn push_user_stack_map(
1709        &mut self,
1710        emit_state: &I::State,
1711        return_addr: CodeOffset,
1712        mut stack_map: ir::UserStackMap,
1713    ) {
1714        let span = emit_state.frame_layout().active_size();
1715        trace!("Adding user stack map @ {return_addr:#x} spanning {span} bytes: {stack_map:?}");
1716
1717        debug_assert!(
1718            self.user_stack_maps
1719                .last()
1720                .map_or(true, |(prev_addr, _, _)| *prev_addr < return_addr),
1721            "pushed stack maps out of order: {} is not less than {}",
1722            self.user_stack_maps.last().unwrap().0,
1723            return_addr,
1724        );
1725
1726        stack_map.finalize(emit_state.frame_layout().sp_to_sized_stack_slots());
1727        self.user_stack_maps.push((return_addr, span, stack_map));
1728    }
1729
1730    /// Push a debug tag associated with the current buffer offset.
1731    pub fn push_debug_tags(&mut self, pos: MachDebugTagPos, tags: &[DebugTag]) {
1732        trace!("debug tags at offset {}: {tags:?}", self.cur_offset());
1733        let start = u32::try_from(self.debug_tag_pool.len()).unwrap();
1734        self.debug_tag_pool.extend(tags.iter().cloned());
1735        let end = u32::try_from(self.debug_tag_pool.len()).unwrap();
1736        self.debug_tags.push(MachDebugTags {
1737            offset: self.cur_offset(),
1738            pos,
1739            range: start..end,
1740        });
1741    }
1742
1743    /// Increase the alignment of the buffer to the given alignment if bigger
1744    /// than the current alignment.
1745    pub fn set_log2_min_function_alignment(&mut self, align_to: u8) {
1746        self.min_alignment = self.min_alignment.max(
1747            1u32.checked_shl(u32::from(align_to))
1748                .expect("log2_min_function_alignment too large"),
1749        );
1750    }
1751
1752    /// Set the frame layout metadata.
1753    pub fn set_frame_layout(&mut self, frame_layout: MachBufferFrameLayout) {
1754        debug_assert!(self.frame_layout.is_none());
1755        self.frame_layout = Some(frame_layout);
1756    }
1757}
1758
1759impl<I: VCodeInst> Extend<u8> for MachBuffer<I> {
1760    fn extend<T: IntoIterator<Item = u8>>(&mut self, iter: T) {
1761        for b in iter {
1762            self.put1(b);
1763        }
1764    }
1765}
1766
1767impl<T: CompilePhase> MachBufferFinalized<T> {
1768    /// Get a list of source location mapping tuples in sorted-by-start-offset order.
1769    pub fn get_srclocs_sorted(&self) -> &[T::MachSrcLocType] {
1770        &self.srclocs[..]
1771    }
1772
1773    /// Get all debug tags, sorted by associated offset.
1774    pub fn debug_tags(&self) -> impl Iterator<Item = MachBufferDebugTagList<'_>> {
1775        self.debug_tags.iter().map(|tags| {
1776            let start = usize::try_from(tags.range.start).unwrap();
1777            let end = usize::try_from(tags.range.end).unwrap();
1778            MachBufferDebugTagList {
1779                offset: tags.offset,
1780                pos: tags.pos,
1781                tags: &self.debug_tag_pool[start..end],
1782            }
1783        })
1784    }
1785
1786    /// Get the total required size for the code.
1787    pub fn total_size(&self) -> CodeOffset {
1788        self.data.len() as CodeOffset
1789    }
1790
1791    /// Return the code in this mach buffer as a hex string for testing purposes.
1792    pub fn stringify_code_bytes(&self) -> String {
1793        // This is pretty lame, but whatever ..
1794        use std::fmt::Write;
1795        let mut s = String::with_capacity(self.data.len() * 2);
1796        for b in &self.data {
1797            write!(&mut s, "{b:02X}").unwrap();
1798        }
1799        s
1800    }
1801
1802    /// Get the code bytes.
1803    pub fn data(&self) -> &[u8] {
1804        // N.B.: we emit every section into the .text section as far as
1805        // the `CodeSink` is concerned; we do not bother to segregate
1806        // the contents into the actual program text, the jumptable and the
1807        // rodata (constant pool). This allows us to generate code assuming
1808        // that these will not be relocated relative to each other, and avoids
1809        // having to designate each section as belonging in one of the three
1810        // fixed categories defined by `CodeSink`. If this becomes a problem
1811        // later (e.g. because of memory permissions or similar), we can
1812        // add this designation and segregate the output; take care, however,
1813        // to add the appropriate relocations in this case.
1814
1815        &self.data[..]
1816    }
1817
1818    /// Get the list of external relocations for this code.
1819    pub fn relocs(&self) -> &[FinalizedMachReloc] {
1820        &self.relocs[..]
1821    }
1822
1823    /// Get the list of trap records for this code.
1824    pub fn traps(&self) -> &[MachTrap] {
1825        &self.traps[..]
1826    }
1827
1828    /// Get the user stack map metadata for this code.
1829    pub fn user_stack_maps(&self) -> &[(CodeOffset, u32, ir::UserStackMap)] {
1830        &self.user_stack_maps
1831    }
1832
1833    /// Take this buffer's user strack map metadata.
1834    pub fn take_user_stack_maps(&mut self) -> SmallVec<[(CodeOffset, u32, ir::UserStackMap); 8]> {
1835        mem::take(&mut self.user_stack_maps)
1836    }
1837
1838    /// Get the list of call sites for this code, along with
1839    /// associated exception handlers.
1840    ///
1841    /// Each item yielded by the returned iterator is a struct with:
1842    ///
1843    /// - The call site metadata record, with a `ret_addr` field
1844    ///   directly accessible and denoting the offset of the return
1845    ///   address into this buffer's code.
1846    /// - The slice of pairs of exception tags and code offsets
1847    ///   denoting exception-handler entry points associated with this
1848    ///   call site.
1849    pub fn call_sites(&self) -> impl Iterator<Item = FinalizedMachCallSite<'_>> + '_ {
1850        self.call_sites.iter().map(|call_site| {
1851            let handler_range = call_site.exception_handler_range.clone();
1852            let handler_range = usize::try_from(handler_range.start).unwrap()
1853                ..usize::try_from(handler_range.end).unwrap();
1854            FinalizedMachCallSite {
1855                ret_addr: call_site.ret_addr,
1856                frame_offset: call_site.frame_offset,
1857                exception_handlers: &self.exception_handlers[handler_range],
1858            }
1859        })
1860    }
1861
1862    /// Get the frame layout, if known.
1863    pub fn frame_layout(&self) -> Option<&MachBufferFrameLayout> {
1864        self.frame_layout.as_ref()
1865    }
1866}
1867
1868/// An item in the exception-handler list for a callsite, with label
1869/// references.  Items are interpreted in left-to-right order and the
1870/// first match wins.
1871#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1872pub enum MachExceptionHandler {
1873    /// A specific tag (in the current dynamic context) should be
1874    /// handled by the code at the given offset.
1875    Tag(ExceptionTag, MachLabel),
1876    /// All exceptions should be handled by the code at the given
1877    /// offset.
1878    Default(MachLabel),
1879    /// The dynamic context for interpreting tags is updated to the
1880    /// value stored in the given machine location (in this frame's
1881    /// context).
1882    Context(ExceptionContextLoc),
1883}
1884
1885impl MachExceptionHandler {
1886    fn finalize<F: Fn(MachLabel) -> CodeOffset>(self, f: F) -> FinalizedMachExceptionHandler {
1887        match self {
1888            Self::Tag(tag, label) => FinalizedMachExceptionHandler::Tag(tag, f(label)),
1889            Self::Default(label) => FinalizedMachExceptionHandler::Default(f(label)),
1890            Self::Context(loc) => FinalizedMachExceptionHandler::Context(loc),
1891        }
1892    }
1893}
1894
1895/// An item in the exception-handler list for a callsite, with final
1896/// (lowered) code offsets. Items are interpreted in left-to-right
1897/// order and the first match wins.
1898#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1899#[cfg_attr(
1900    feature = "enable-serde",
1901    derive(serde_derive::Serialize, serde_derive::Deserialize)
1902)]
1903pub enum FinalizedMachExceptionHandler {
1904    /// A specific tag (in the current dynamic context) should be
1905    /// handled by the code at the given offset.
1906    Tag(ExceptionTag, CodeOffset),
1907    /// All exceptions should be handled by the code at the given
1908    /// offset.
1909    Default(CodeOffset),
1910    /// The dynamic context for interpreting tags is updated to the
1911    /// value stored in the given machine location (in this frame's
1912    /// context).
1913    Context(ExceptionContextLoc),
1914}
1915
1916/// A location for a dynamic exception context value.
1917#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1918#[cfg_attr(
1919    feature = "enable-serde",
1920    derive(serde_derive::Serialize, serde_derive::Deserialize)
1921)]
1922pub enum ExceptionContextLoc {
1923    /// An offset from SP at the callsite.
1924    SPOffset(u32),
1925    /// A GPR at the callsite. The physical register number for the
1926    /// GPR register file on the target architecture is used.
1927    GPR(u8),
1928}
1929
1930/// Metadata about a constant.
1931struct MachBufferConstant {
1932    /// A label which has not yet been bound which can be used for this
1933    /// constant.
1934    ///
1935    /// This is lazily created when a label is requested for a constant and is
1936    /// cleared when a constant is emitted.
1937    upcoming_label: Option<MachLabel>,
1938    /// Required alignment.
1939    align: CodeOffset,
1940    /// The byte size of this constant.
1941    size: usize,
1942}
1943
1944/// A trap that is deferred to the next time an island is emitted for either
1945/// traps, constants, or fixups.
1946struct MachLabelTrap {
1947    /// This label will refer to the trap's offset.
1948    label: MachLabel,
1949    /// The code associated with this trap.
1950    code: TrapCode,
1951    /// An optional source location to assign for this trap.
1952    loc: Option<RelSourceLoc>,
1953}
1954
1955/// A fixup to perform on the buffer once code is emitted. Fixups always refer
1956/// to labels and patch the code based on label offsets. Hence, they are like
1957/// relocations, but internal to one buffer.
1958#[derive(Debug)]
1959struct MachLabelFixup<I: VCodeInst> {
1960    /// The label whose offset controls this fixup.
1961    label: MachLabel,
1962    /// The offset to fix up / patch to refer to this label.
1963    offset: CodeOffset,
1964    /// The kind of fixup. This is architecture-specific; each architecture may have,
1965    /// e.g., several types of branch instructions, each with differently-sized
1966    /// offset fields and different places within the instruction to place the
1967    /// bits.
1968    kind: I::LabelUse,
1969}
1970
1971impl<I: VCodeInst> MachLabelFixup<I> {
1972    fn deadline(&self) -> CodeOffset {
1973        self.offset.saturating_add(self.kind.max_pos_range())
1974    }
1975}
1976
1977impl<I: VCodeInst> PartialEq for MachLabelFixup<I> {
1978    fn eq(&self, other: &Self) -> bool {
1979        self.deadline() == other.deadline()
1980    }
1981}
1982
1983impl<I: VCodeInst> Eq for MachLabelFixup<I> {}
1984
1985impl<I: VCodeInst> PartialOrd for MachLabelFixup<I> {
1986    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1987        Some(self.cmp(other))
1988    }
1989}
1990
1991impl<I: VCodeInst> Ord for MachLabelFixup<I> {
1992    fn cmp(&self, other: &Self) -> Ordering {
1993        other.deadline().cmp(&self.deadline())
1994    }
1995}
1996
1997/// A relocation resulting from a compilation.
1998#[derive(Clone, Debug, PartialEq)]
1999#[cfg_attr(
2000    feature = "enable-serde",
2001    derive(serde_derive::Serialize, serde_derive::Deserialize)
2002)]
2003pub struct MachRelocBase<T> {
2004    /// The offset at which the relocation applies, *relative to the
2005    /// containing section*.
2006    pub offset: CodeOffset,
2007    /// The kind of relocation.
2008    pub kind: Reloc,
2009    /// The external symbol / name to which this relocation refers.
2010    pub target: T,
2011    /// The addend to add to the symbol value.
2012    pub addend: i64,
2013}
2014
2015type MachReloc = MachRelocBase<RelocTarget>;
2016
2017/// A relocation resulting from a compilation.
2018pub type FinalizedMachReloc = MachRelocBase<FinalizedRelocTarget>;
2019
2020/// A Relocation target
2021#[derive(Debug, Clone, PartialEq, Eq, Hash)]
2022pub enum RelocTarget {
2023    /// Points to an [ExternalName] outside the current function.
2024    ExternalName(ExternalName),
2025    /// Points to a [MachLabel] inside this function.
2026    /// This is different from [MachLabelFixup] in that both the relocation and the
2027    /// label will be emitted and are only resolved at link time.
2028    ///
2029    /// There is no reason to prefer this over [MachLabelFixup] unless the ABI requires it.
2030    Label(MachLabel),
2031}
2032
2033impl From<ExternalName> for RelocTarget {
2034    fn from(name: ExternalName) -> Self {
2035        Self::ExternalName(name)
2036    }
2037}
2038
2039impl From<MachLabel> for RelocTarget {
2040    fn from(label: MachLabel) -> Self {
2041        Self::Label(label)
2042    }
2043}
2044
2045/// A Relocation target
2046#[derive(Debug, Clone, PartialEq, Eq, Hash)]
2047#[cfg_attr(
2048    feature = "enable-serde",
2049    derive(serde_derive::Serialize, serde_derive::Deserialize)
2050)]
2051pub enum FinalizedRelocTarget {
2052    /// Points to an [ExternalName] outside the current function.
2053    ExternalName(ExternalName),
2054    /// Points to a [CodeOffset] from the start of the current function.
2055    Func(CodeOffset),
2056}
2057
2058impl FinalizedRelocTarget {
2059    /// Returns a display for the current [FinalizedRelocTarget], with extra context to prettify the
2060    /// output.
2061    pub fn display<'a>(&'a self, params: Option<&'a FunctionParameters>) -> String {
2062        match self {
2063            FinalizedRelocTarget::ExternalName(name) => format!("{}", name.display(params)),
2064            FinalizedRelocTarget::Func(offset) => format!("func+{offset}"),
2065        }
2066    }
2067}
2068
2069/// A trap record resulting from a compilation.
2070#[derive(Clone, Debug, PartialEq)]
2071#[cfg_attr(
2072    feature = "enable-serde",
2073    derive(serde_derive::Serialize, serde_derive::Deserialize)
2074)]
2075pub struct MachTrap {
2076    /// The offset at which the trap instruction occurs, *relative to the
2077    /// containing section*.
2078    pub offset: CodeOffset,
2079    /// The trap code.
2080    pub code: TrapCode,
2081}
2082
2083/// A call site record resulting from a compilation.
2084#[derive(Clone, Debug, PartialEq)]
2085#[cfg_attr(
2086    feature = "enable-serde",
2087    derive(serde_derive::Serialize, serde_derive::Deserialize)
2088)]
2089pub struct MachCallSite {
2090    /// The offset of the call's return address, *relative to the
2091    /// start of the buffer*.
2092    pub ret_addr: CodeOffset,
2093
2094    /// The offset from the FP at this callsite down to the SP when
2095    /// the call occurs, if known. In other words, the size of the
2096    /// stack frame up to the saved FP slot. Useful to recover the
2097    /// start of the stack frame and to look up dynamic contexts
2098    /// stored in [`ExceptionContextLoc::SPOffset`].
2099    ///
2100    /// If `None`, the compiler backend did not specify a frame
2101    /// offset. The runtime in use with the compiled code may require
2102    /// the frame offset if exception handlers are present or dynamic
2103    /// context is used, but that is not Cranelift's concern: the
2104    /// frame offset is optional at this level.
2105    pub frame_offset: Option<u32>,
2106
2107    /// Range in `exception_handlers` corresponding to the exception
2108    /// handlers for this callsite.
2109    exception_handler_range: Range<u32>,
2110}
2111
2112/// A call site record resulting from a compilation.
2113#[derive(Clone, Debug, PartialEq)]
2114pub struct FinalizedMachCallSite<'a> {
2115    /// The offset of the call's return address, *relative to the
2116    /// start of the buffer*.
2117    pub ret_addr: CodeOffset,
2118
2119    /// The offset from the FP at this callsite down to the SP when
2120    /// the call occurs, if known. In other words, the size of the
2121    /// stack frame up to the saved FP slot. Useful to recover the
2122    /// start of the stack frame and to look up dynamic contexts
2123    /// stored in [`ExceptionContextLoc::SPOffset`].
2124    ///
2125    /// If `None`, the compiler backend did not specify a frame
2126    /// offset. The runtime in use with the compiled code may require
2127    /// the frame offset if exception handlers are present or dynamic
2128    /// context is used, but that is not Cranelift's concern: the
2129    /// frame offset is optional at this level.
2130    pub frame_offset: Option<u32>,
2131
2132    /// Exception handlers at this callsite, with target offsets
2133    /// *relative to the start of the buffer*.
2134    pub exception_handlers: &'a [FinalizedMachExceptionHandler],
2135}
2136
2137/// A source-location mapping resulting from a compilation.
2138#[derive(PartialEq, Debug, Clone)]
2139#[cfg_attr(
2140    feature = "enable-serde",
2141    derive(serde_derive::Serialize, serde_derive::Deserialize)
2142)]
2143pub struct MachSrcLoc<T: CompilePhase> {
2144    /// The start of the region of code corresponding to a source location.
2145    /// This is relative to the start of the function, not to the start of the
2146    /// section.
2147    pub start: CodeOffset,
2148    /// The end of the region of code corresponding to a source location.
2149    /// This is relative to the start of the function, not to the start of the
2150    /// section.
2151    pub end: CodeOffset,
2152    /// The source location.
2153    pub loc: T::SourceLocType,
2154}
2155
2156impl MachSrcLoc<Stencil> {
2157    fn apply_base_srcloc(self, base_srcloc: SourceLoc) -> MachSrcLoc<Final> {
2158        MachSrcLoc {
2159            start: self.start,
2160            end: self.end,
2161            loc: self.loc.expand(base_srcloc),
2162        }
2163    }
2164}
2165
2166/// Record of branch instruction in the buffer, to facilitate editing.
2167#[derive(Clone, Debug)]
2168struct MachBranch {
2169    start: CodeOffset,
2170    end: CodeOffset,
2171    target: MachLabel,
2172    fixup: usize,
2173    inverted: Option<SmallVec<[u8; 8]>>,
2174    /// All labels pointing to the start of this branch. For correctness, this
2175    /// *must* be complete (i.e., must contain all labels whose resolved offsets
2176    /// are at the start of this branch): we rely on being able to redirect all
2177    /// labels that could jump to this branch before removing it, if it is
2178    /// otherwise unreachable.
2179    labels_at_this_branch: SmallVec<[MachLabel; 4]>,
2180}
2181
2182impl MachBranch {
2183    fn is_cond(&self) -> bool {
2184        self.inverted.is_some()
2185    }
2186    fn is_uncond(&self) -> bool {
2187        self.inverted.is_none()
2188    }
2189}
2190
2191/// Stack-frame layout information carried through to machine
2192/// code. This provides sufficient information to interpret an active
2193/// stack frame from a running function, if provided.
2194#[derive(Clone, Debug, PartialEq)]
2195#[cfg_attr(
2196    feature = "enable-serde",
2197    derive(serde_derive::Serialize, serde_derive::Deserialize)
2198)]
2199pub struct MachBufferFrameLayout {
2200    /// Offset from bottom of frame to FP (near top of frame). This
2201    /// allows reading the frame given only FP.
2202    pub frame_to_fp_offset: u32,
2203    /// Offset from bottom of frame for each StackSlot,
2204    pub stackslots: SecondaryMap<ir::StackSlot, MachBufferStackSlot>,
2205}
2206
2207/// Descriptor for a single stack slot in the compiled function.
2208#[derive(Clone, Debug, PartialEq, Default)]
2209#[cfg_attr(
2210    feature = "enable-serde",
2211    derive(serde_derive::Serialize, serde_derive::Deserialize)
2212)]
2213pub struct MachBufferStackSlot {
2214    /// Offset from the bottom of the stack frame.
2215    pub offset: u32,
2216
2217    /// User-provided key to describe this stack slot.
2218    pub key: Option<ir::StackSlotKey>,
2219}
2220
2221/// Debug tags: a sequence of references to a stack slot, or a
2222/// user-defined value, at a particular PC.
2223#[derive(Clone, Debug, PartialEq)]
2224#[cfg_attr(
2225    feature = "enable-serde",
2226    derive(serde_derive::Serialize, serde_derive::Deserialize)
2227)]
2228pub(crate) struct MachDebugTags {
2229    /// Offset at which this tag applies.
2230    pub offset: CodeOffset,
2231
2232    /// Position on the attached instruction. This indicates whether
2233    /// the tags attach to the prior instruction (i.e., as a return
2234    /// point from a call) or the current instruction (i.e., as a PC
2235    /// seen during a trap).
2236    pub pos: MachDebugTagPos,
2237
2238    /// The range in the tag pool.
2239    pub range: Range<u32>,
2240}
2241
2242/// Debug tag position on an instruction.
2243///
2244/// We need to distinguish position on an instruction, and not just
2245/// use offsets, because of the following case:
2246///
2247/// ```plain
2248/// <tag1, tag2> call ...
2249/// <tag3, tag4> trapping_store ...
2250/// ```
2251///
2252/// If the stack is walked and interpreted with debug tags while
2253/// within the call, the PC seen will be the return point, i.e. the
2254/// address after the call. If the stack is walked and interpreted
2255/// with debug tags upon a trap of the following instruction, it will
2256/// be the PC of that instruction -- which is the same PC! Thus to
2257/// disambiguate which tags we want, we attach a "pre/post" flag to
2258/// every group of tags at an offset; and when we look up tags, we
2259/// look them up for an offset and "position" at that offset.
2260///
2261/// Thus there are logically two positions at every offset -- so the
2262/// above will be emitted as
2263///
2264/// ```plain
2265/// 0: call ...
2266///                          4, post: <tag1, tag2>
2267///                          4, pre: <tag3, tag4>
2268/// 4: trapping_store ...
2269/// ```
2270#[derive(Clone, Copy, Debug, PartialEq, Eq)]
2271#[cfg_attr(
2272    feature = "enable-serde",
2273    derive(serde_derive::Serialize, serde_derive::Deserialize)
2274)]
2275pub enum MachDebugTagPos {
2276    /// Tags attached after the instruction that ends at this offset.
2277    ///
2278    /// This is used to attach tags to a call, because the PC we see
2279    /// when walking the stack is the *return point*.
2280    Post,
2281    /// Tags attached before the instruction that starts at this offset.
2282    ///
2283    /// This is used to attach tags to every other kind of
2284    /// instruction, because the PC we see when processing a trap of
2285    /// that instruction is the PC of that instruction, not the
2286    /// following one.
2287    Pre,
2288}
2289
2290/// Iterator item for visiting debug tags.
2291pub struct MachBufferDebugTagList<'a> {
2292    /// Offset at which this tag applies.
2293    pub offset: CodeOffset,
2294
2295    /// Position at this offset ("post", attaching to prior
2296    /// instruction, or "pre", attaching to next instruction).
2297    pub pos: MachDebugTagPos,
2298
2299    /// The underlying tags.
2300    pub tags: &'a [DebugTag],
2301}
2302
2303/// Implementation of the `TextSectionBuilder` trait backed by `MachBuffer`.
2304///
2305/// Note that `MachBuffer` was primarily written for intra-function references
2306/// of jumps between basic blocks, but it's also quite usable for entire text
2307/// sections and resolving references between functions themselves. This
2308/// builder interprets "blocks" as labeled functions for the purposes of
2309/// resolving labels internally in the buffer.
2310pub struct MachTextSectionBuilder<I: VCodeInst> {
2311    buf: MachBuffer<I>,
2312    next_func: usize,
2313    force_veneers: ForceVeneers,
2314}
2315
2316impl<I: VCodeInst> MachTextSectionBuilder<I> {
2317    /// Creates a new text section builder which will have `num_funcs` functions
2318    /// pushed into it.
2319    pub fn new(num_funcs: usize) -> MachTextSectionBuilder<I> {
2320        let mut buf = MachBuffer::new();
2321        buf.reserve_labels_for_blocks(num_funcs);
2322        MachTextSectionBuilder {
2323            buf,
2324            next_func: 0,
2325            force_veneers: ForceVeneers::No,
2326        }
2327    }
2328}
2329
2330impl<I: VCodeInst> TextSectionBuilder for MachTextSectionBuilder<I> {
2331    fn append(
2332        &mut self,
2333        labeled: bool,
2334        func: &[u8],
2335        align: u32,
2336        ctrl_plane: &mut ControlPlane,
2337    ) -> u64 {
2338        // Conditionally emit an island if it's necessary to resolve jumps
2339        // between functions which are too far away.
2340        let size = func.len() as u32;
2341        if self.force_veneers == ForceVeneers::Yes || self.buf.island_needed(size) {
2342            self.buf
2343                .emit_island_maybe_forced(self.force_veneers, size, ctrl_plane);
2344        }
2345
2346        self.buf.align_to(align);
2347        let pos = self.buf.cur_offset();
2348        if labeled {
2349            self.buf.bind_label(
2350                MachLabel::from_block(BlockIndex::new(self.next_func)),
2351                ctrl_plane,
2352            );
2353            self.next_func += 1;
2354        }
2355        self.buf.put_data(func);
2356        u64::from(pos)
2357    }
2358
2359    fn resolve_reloc(&mut self, offset: u64, reloc: Reloc, addend: Addend, target: usize) -> bool {
2360        crate::trace!(
2361            "Resolving relocation @ {offset:#x} + {addend:#x} to target {target} of kind {reloc:?}"
2362        );
2363        let label = MachLabel::from_block(BlockIndex::new(target));
2364        let offset = u32::try_from(offset).unwrap();
2365        match I::LabelUse::from_reloc(reloc, addend) {
2366            Some(label_use) => {
2367                self.buf.use_label_at_offset(offset, label, label_use);
2368                true
2369            }
2370            None => false,
2371        }
2372    }
2373
2374    fn force_veneers(&mut self) {
2375        self.force_veneers = ForceVeneers::Yes;
2376    }
2377
2378    fn write(&mut self, offset: u64, data: &[u8]) {
2379        self.buf.data[offset.try_into().unwrap()..][..data.len()].copy_from_slice(data);
2380    }
2381
2382    fn finish(&mut self, ctrl_plane: &mut ControlPlane) -> Vec<u8> {
2383        // Double-check all functions were pushed.
2384        assert_eq!(self.next_func, self.buf.label_offsets.len());
2385
2386        // Finish up any veneers, if necessary.
2387        self.buf
2388            .finish_emission_maybe_forcing_veneers(self.force_veneers, ctrl_plane);
2389
2390        // We don't need the data any more, so return it to the caller.
2391        mem::take(&mut self.buf.data).into_vec()
2392    }
2393}
2394
2395// We use an actual instruction definition to do tests, so we depend on the `arm64` feature here.
2396#[cfg(all(test, feature = "arm64"))]
2397mod test {
2398    use cranelift_entity::EntityRef as _;
2399
2400    use super::*;
2401    use crate::ir::UserExternalNameRef;
2402    use crate::isa::aarch64::inst::{BranchTarget, CondBrKind, EmitInfo, Inst};
2403    use crate::isa::aarch64::inst::{OperandSize, xreg};
2404    use crate::machinst::{MachInstEmit, MachInstEmitState};
2405    use crate::settings;
2406
2407    fn label(n: u32) -> MachLabel {
2408        MachLabel::from_block(BlockIndex::new(n as usize))
2409    }
2410    fn target(n: u32) -> BranchTarget {
2411        BranchTarget::Label(label(n))
2412    }
2413
2414    #[test]
2415    fn test_elide_jump_to_next() {
2416        let info = EmitInfo::new(settings::Flags::new(settings::builder()));
2417        let mut buf = MachBuffer::new();
2418        let mut state = <Inst as MachInstEmit>::State::default();
2419        let constants = Default::default();
2420
2421        buf.reserve_labels_for_blocks(2);
2422        buf.bind_label(label(0), state.ctrl_plane_mut());
2423        let inst = Inst::Jump { dest: target(1) };
2424        inst.emit(&mut buf, &info, &mut state);
2425        buf.bind_label(label(1), state.ctrl_plane_mut());
2426        let buf = buf.finish(&constants, state.ctrl_plane_mut());
2427        assert_eq!(0, buf.total_size());
2428    }
2429
2430    #[test]
2431    fn test_elide_trivial_jump_blocks() {
2432        let info = EmitInfo::new(settings::Flags::new(settings::builder()));
2433        let mut buf = MachBuffer::new();
2434        let mut state = <Inst as MachInstEmit>::State::default();
2435        let constants = Default::default();
2436
2437        buf.reserve_labels_for_blocks(4);
2438
2439        buf.bind_label(label(0), state.ctrl_plane_mut());
2440        let inst = Inst::CondBr {
2441            kind: CondBrKind::NotZero(xreg(0), OperandSize::Size64),
2442            taken: target(1),
2443            not_taken: target(2),
2444        };
2445        inst.emit(&mut buf, &info, &mut state);
2446
2447        buf.bind_label(label(1), state.ctrl_plane_mut());
2448        let inst = Inst::Jump { dest: target(3) };
2449        inst.emit(&mut buf, &info, &mut state);
2450
2451        buf.bind_label(label(2), state.ctrl_plane_mut());
2452        let inst = Inst::Jump { dest: target(3) };
2453        inst.emit(&mut buf, &info, &mut state);
2454
2455        buf.bind_label(label(3), state.ctrl_plane_mut());
2456
2457        let buf = buf.finish(&constants, state.ctrl_plane_mut());
2458        assert_eq!(0, buf.total_size());
2459    }
2460
2461    #[test]
2462    fn test_flip_cond() {
2463        let info = EmitInfo::new(settings::Flags::new(settings::builder()));
2464        let mut buf = MachBuffer::new();
2465        let mut state = <Inst as MachInstEmit>::State::default();
2466        let constants = Default::default();
2467
2468        buf.reserve_labels_for_blocks(4);
2469
2470        buf.bind_label(label(0), state.ctrl_plane_mut());
2471        let inst = Inst::CondBr {
2472            kind: CondBrKind::Zero(xreg(0), OperandSize::Size64),
2473            taken: target(1),
2474            not_taken: target(2),
2475        };
2476        inst.emit(&mut buf, &info, &mut state);
2477
2478        buf.bind_label(label(1), state.ctrl_plane_mut());
2479        let inst = Inst::Nop4;
2480        inst.emit(&mut buf, &info, &mut state);
2481
2482        buf.bind_label(label(2), state.ctrl_plane_mut());
2483        let inst = Inst::Udf {
2484            trap_code: TrapCode::STACK_OVERFLOW,
2485        };
2486        inst.emit(&mut buf, &info, &mut state);
2487
2488        buf.bind_label(label(3), state.ctrl_plane_mut());
2489
2490        let buf = buf.finish(&constants, state.ctrl_plane_mut());
2491
2492        let mut buf2 = MachBuffer::new();
2493        let mut state = Default::default();
2494        let inst = Inst::TrapIf {
2495            kind: CondBrKind::NotZero(xreg(0), OperandSize::Size64),
2496            trap_code: TrapCode::STACK_OVERFLOW,
2497        };
2498        inst.emit(&mut buf2, &info, &mut state);
2499        let inst = Inst::Nop4;
2500        inst.emit(&mut buf2, &info, &mut state);
2501
2502        let buf2 = buf2.finish(&constants, state.ctrl_plane_mut());
2503
2504        assert_eq!(buf.data, buf2.data);
2505    }
2506
2507    #[test]
2508    fn test_island() {
2509        let info = EmitInfo::new(settings::Flags::new(settings::builder()));
2510        let mut buf = MachBuffer::new();
2511        let mut state = <Inst as MachInstEmit>::State::default();
2512        let constants = Default::default();
2513
2514        buf.reserve_labels_for_blocks(4);
2515
2516        buf.bind_label(label(0), state.ctrl_plane_mut());
2517        let inst = Inst::CondBr {
2518            kind: CondBrKind::NotZero(xreg(0), OperandSize::Size64),
2519            taken: target(2),
2520            not_taken: target(3),
2521        };
2522        inst.emit(&mut buf, &info, &mut state);
2523
2524        buf.bind_label(label(1), state.ctrl_plane_mut());
2525        while buf.cur_offset() < 2000000 {
2526            if buf.island_needed(0) {
2527                buf.emit_island(0, state.ctrl_plane_mut());
2528            }
2529            let inst = Inst::Nop4;
2530            inst.emit(&mut buf, &info, &mut state);
2531        }
2532
2533        buf.bind_label(label(2), state.ctrl_plane_mut());
2534        let inst = Inst::Nop4;
2535        inst.emit(&mut buf, &info, &mut state);
2536
2537        buf.bind_label(label(3), state.ctrl_plane_mut());
2538        let inst = Inst::Nop4;
2539        inst.emit(&mut buf, &info, &mut state);
2540
2541        let buf = buf.finish(&constants, state.ctrl_plane_mut());
2542
2543        assert_eq!(2000000 + 8, buf.total_size());
2544
2545        let mut buf2 = MachBuffer::new();
2546        let mut state = Default::default();
2547        let inst = Inst::CondBr {
2548            kind: CondBrKind::NotZero(xreg(0), OperandSize::Size64),
2549
2550            // This conditionally taken branch has a 19-bit constant, shifted
2551            // to the left by two, giving us a 21-bit range in total. Half of
2552            // this range positive so the we should be around 1 << 20 bytes
2553            // away for our jump target.
2554            //
2555            // There are two pending fixups by the time we reach this point,
2556            // one for this 19-bit jump and one for the unconditional 26-bit
2557            // jump below. A 19-bit veneer is 4 bytes large and the 26-bit
2558            // veneer is 20 bytes large, which means that pessimistically
2559            // assuming we'll need two veneers. Currently each veneer is
2560            // pessimistically assumed to be the maximal size which means we
2561            // need 40 bytes of extra space, meaning that the actual island
2562            // should come 40-bytes before the deadline.
2563            taken: BranchTarget::ResolvedOffset((1 << 20) - 20 - 20),
2564
2565            // This branch is in-range so no veneers should be needed, it should
2566            // go directly to the target.
2567            not_taken: BranchTarget::ResolvedOffset(2000000 + 4 - 4),
2568        };
2569        inst.emit(&mut buf2, &info, &mut state);
2570
2571        let buf2 = buf2.finish(&constants, state.ctrl_plane_mut());
2572
2573        assert_eq!(&buf.data[0..8], &buf2.data[..]);
2574    }
2575
2576    #[test]
2577    fn test_island_backward() {
2578        let info = EmitInfo::new(settings::Flags::new(settings::builder()));
2579        let mut buf = MachBuffer::new();
2580        let mut state = <Inst as MachInstEmit>::State::default();
2581        let constants = Default::default();
2582
2583        buf.reserve_labels_for_blocks(4);
2584
2585        buf.bind_label(label(0), state.ctrl_plane_mut());
2586        let inst = Inst::Nop4;
2587        inst.emit(&mut buf, &info, &mut state);
2588
2589        buf.bind_label(label(1), state.ctrl_plane_mut());
2590        let inst = Inst::Nop4;
2591        inst.emit(&mut buf, &info, &mut state);
2592
2593        buf.bind_label(label(2), state.ctrl_plane_mut());
2594        while buf.cur_offset() < 2000000 {
2595            let inst = Inst::Nop4;
2596            inst.emit(&mut buf, &info, &mut state);
2597        }
2598
2599        buf.bind_label(label(3), state.ctrl_plane_mut());
2600        let inst = Inst::CondBr {
2601            kind: CondBrKind::NotZero(xreg(0), OperandSize::Size64),
2602            taken: target(0),
2603            not_taken: target(1),
2604        };
2605        inst.emit(&mut buf, &info, &mut state);
2606
2607        let buf = buf.finish(&constants, state.ctrl_plane_mut());
2608
2609        assert_eq!(2000000 + 12, buf.total_size());
2610
2611        let mut buf2 = MachBuffer::new();
2612        let mut state = Default::default();
2613        let inst = Inst::CondBr {
2614            kind: CondBrKind::NotZero(xreg(0), OperandSize::Size64),
2615            taken: BranchTarget::ResolvedOffset(8),
2616            not_taken: BranchTarget::ResolvedOffset(4 - (2000000 + 4)),
2617        };
2618        inst.emit(&mut buf2, &info, &mut state);
2619        let inst = Inst::Jump {
2620            dest: BranchTarget::ResolvedOffset(-(2000000 + 8)),
2621        };
2622        inst.emit(&mut buf2, &info, &mut state);
2623
2624        let buf2 = buf2.finish(&constants, state.ctrl_plane_mut());
2625
2626        assert_eq!(&buf.data[2000000..], &buf2.data[..]);
2627    }
2628
2629    #[test]
2630    fn test_multiple_redirect() {
2631        // label0:
2632        //   cbz x0, label1
2633        //   b label2
2634        // label1:
2635        //   b label3
2636        // label2:
2637        //   nop
2638        //   nop
2639        //   b label0
2640        // label3:
2641        //   b label4
2642        // label4:
2643        //   b label5
2644        // label5:
2645        //   b label7
2646        // label6:
2647        //   nop
2648        // label7:
2649        //   ret
2650        //
2651        // -- should become:
2652        //
2653        // label0:
2654        //   cbz x0, label7
2655        // label2:
2656        //   nop
2657        //   nop
2658        //   b label0
2659        // label6:
2660        //   nop
2661        // label7:
2662        //   ret
2663
2664        let info = EmitInfo::new(settings::Flags::new(settings::builder()));
2665        let mut buf = MachBuffer::new();
2666        let mut state = <Inst as MachInstEmit>::State::default();
2667        let constants = Default::default();
2668
2669        buf.reserve_labels_for_blocks(8);
2670
2671        buf.bind_label(label(0), state.ctrl_plane_mut());
2672        let inst = Inst::CondBr {
2673            kind: CondBrKind::Zero(xreg(0), OperandSize::Size64),
2674            taken: target(1),
2675            not_taken: target(2),
2676        };
2677        inst.emit(&mut buf, &info, &mut state);
2678
2679        buf.bind_label(label(1), state.ctrl_plane_mut());
2680        let inst = Inst::Jump { dest: target(3) };
2681        inst.emit(&mut buf, &info, &mut state);
2682
2683        buf.bind_label(label(2), state.ctrl_plane_mut());
2684        let inst = Inst::Nop4;
2685        inst.emit(&mut buf, &info, &mut state);
2686        inst.emit(&mut buf, &info, &mut state);
2687        let inst = Inst::Jump { dest: target(0) };
2688        inst.emit(&mut buf, &info, &mut state);
2689
2690        buf.bind_label(label(3), state.ctrl_plane_mut());
2691        let inst = Inst::Jump { dest: target(4) };
2692        inst.emit(&mut buf, &info, &mut state);
2693
2694        buf.bind_label(label(4), state.ctrl_plane_mut());
2695        let inst = Inst::Jump { dest: target(5) };
2696        inst.emit(&mut buf, &info, &mut state);
2697
2698        buf.bind_label(label(5), state.ctrl_plane_mut());
2699        let inst = Inst::Jump { dest: target(7) };
2700        inst.emit(&mut buf, &info, &mut state);
2701
2702        buf.bind_label(label(6), state.ctrl_plane_mut());
2703        let inst = Inst::Nop4;
2704        inst.emit(&mut buf, &info, &mut state);
2705
2706        buf.bind_label(label(7), state.ctrl_plane_mut());
2707        let inst = Inst::Ret {};
2708        inst.emit(&mut buf, &info, &mut state);
2709
2710        let buf = buf.finish(&constants, state.ctrl_plane_mut());
2711
2712        let golden_data = vec![
2713            0xa0, 0x00, 0x00, 0xb4, // cbz x0, 0x14
2714            0x1f, 0x20, 0x03, 0xd5, // nop
2715            0x1f, 0x20, 0x03, 0xd5, // nop
2716            0xfd, 0xff, 0xff, 0x17, // b 0
2717            0x1f, 0x20, 0x03, 0xd5, // nop
2718            0xc0, 0x03, 0x5f, 0xd6, // ret
2719        ];
2720
2721        assert_eq!(&golden_data[..], &buf.data[..]);
2722    }
2723
2724    #[test]
2725    fn test_handle_branch_cycle() {
2726        // label0:
2727        //   b label1
2728        // label1:
2729        //   b label2
2730        // label2:
2731        //   b label3
2732        // label3:
2733        //   b label4
2734        // label4:
2735        //   b label1  // note: not label0 (to make it interesting).
2736        //
2737        // -- should become:
2738        //
2739        // label0, label1, ..., label4:
2740        //   b label0
2741        let info = EmitInfo::new(settings::Flags::new(settings::builder()));
2742        let mut buf = MachBuffer::new();
2743        let mut state = <Inst as MachInstEmit>::State::default();
2744        let constants = Default::default();
2745
2746        buf.reserve_labels_for_blocks(5);
2747
2748        buf.bind_label(label(0), state.ctrl_plane_mut());
2749        let inst = Inst::Jump { dest: target(1) };
2750        inst.emit(&mut buf, &info, &mut state);
2751
2752        buf.bind_label(label(1), state.ctrl_plane_mut());
2753        let inst = Inst::Jump { dest: target(2) };
2754        inst.emit(&mut buf, &info, &mut state);
2755
2756        buf.bind_label(label(2), state.ctrl_plane_mut());
2757        let inst = Inst::Jump { dest: target(3) };
2758        inst.emit(&mut buf, &info, &mut state);
2759
2760        buf.bind_label(label(3), state.ctrl_plane_mut());
2761        let inst = Inst::Jump { dest: target(4) };
2762        inst.emit(&mut buf, &info, &mut state);
2763
2764        buf.bind_label(label(4), state.ctrl_plane_mut());
2765        let inst = Inst::Jump { dest: target(1) };
2766        inst.emit(&mut buf, &info, &mut state);
2767
2768        let buf = buf.finish(&constants, state.ctrl_plane_mut());
2769
2770        let golden_data = vec![
2771            0x00, 0x00, 0x00, 0x14, // b 0
2772        ];
2773
2774        assert_eq!(&golden_data[..], &buf.data[..]);
2775    }
2776
2777    #[test]
2778    fn metadata_records() {
2779        let mut buf = MachBuffer::<Inst>::new();
2780        let ctrl_plane = &mut Default::default();
2781        let constants = Default::default();
2782
2783        buf.reserve_labels_for_blocks(3);
2784
2785        buf.bind_label(label(0), ctrl_plane);
2786        buf.put1(1);
2787        buf.add_trap(TrapCode::HEAP_OUT_OF_BOUNDS);
2788        buf.put1(2);
2789        buf.add_trap(TrapCode::INTEGER_OVERFLOW);
2790        buf.add_trap(TrapCode::INTEGER_DIVISION_BY_ZERO);
2791        buf.add_try_call_site(
2792            Some(0x10),
2793            [
2794                MachExceptionHandler::Tag(ExceptionTag::new(42), label(2)),
2795                MachExceptionHandler::Default(label(1)),
2796            ]
2797            .into_iter(),
2798        );
2799        buf.add_reloc(
2800            Reloc::Abs4,
2801            &ExternalName::User(UserExternalNameRef::new(0)),
2802            0,
2803        );
2804        buf.put1(3);
2805        buf.add_reloc(
2806            Reloc::Abs8,
2807            &ExternalName::User(UserExternalNameRef::new(1)),
2808            1,
2809        );
2810        buf.put1(4);
2811        buf.bind_label(label(1), ctrl_plane);
2812        buf.put1(0xff);
2813        buf.bind_label(label(2), ctrl_plane);
2814        buf.put1(0xff);
2815
2816        let buf = buf.finish(&constants, ctrl_plane);
2817
2818        assert_eq!(buf.data(), &[1, 2, 3, 4, 0xff, 0xff]);
2819        assert_eq!(
2820            buf.traps()
2821                .iter()
2822                .map(|trap| (trap.offset, trap.code))
2823                .collect::<Vec<_>>(),
2824            vec![
2825                (1, TrapCode::HEAP_OUT_OF_BOUNDS),
2826                (2, TrapCode::INTEGER_OVERFLOW),
2827                (2, TrapCode::INTEGER_DIVISION_BY_ZERO)
2828            ]
2829        );
2830        let call_sites: Vec<_> = buf.call_sites().collect();
2831        assert_eq!(call_sites[0].ret_addr, 2);
2832        assert_eq!(call_sites[0].frame_offset, Some(0x10));
2833        assert_eq!(
2834            call_sites[0].exception_handlers,
2835            &[
2836                FinalizedMachExceptionHandler::Tag(ExceptionTag::new(42), 5),
2837                FinalizedMachExceptionHandler::Default(4)
2838            ],
2839        );
2840        assert_eq!(
2841            buf.relocs()
2842                .iter()
2843                .map(|reloc| (reloc.offset, reloc.kind))
2844                .collect::<Vec<_>>(),
2845            vec![(2, Reloc::Abs4), (3, Reloc::Abs8)]
2846        );
2847    }
2848}