Skip to main content

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