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