backend_lang/x86_64/
emit.rs

1//! Emission: a MIR function on physical registers, through isa-lang's
2//! assembler, to x86-64 machine code.
3//!
4//! The emitter lays out the frame, writes the prologue, gives every block a
5//! label, and encodes each instruction through the row's isa-lang mapping.
6//! Control-flow edges with arguments, `copy`, and `pcopy` are parallel copies
7//! and go through the [`MoveResolver`](crate::moves::MoveResolver): register
8//! cycles become `xchg`, memory-to-memory moves go through a register borrowed
9//! around the move (saved to a hidden frame slot), and a cycle through memory
10//! is broken with a second hidden slot. The hidden slots are added to the
11//! frame only when an edge needs them.
12//!
13//! A conditional branch whose taken edge carries moves gets those moves on
14//! its own path: the emitter branches on the negated condition around them,
15//! which splits the critical edge without adding a block. Moves never touch
16//! the flags, and every return runs the epilogue before `ret`.
17//!
18//! Functions are emitted into one [`Emitter`] and call each other by name;
19//! [`Emitter::finish`] runs isa-lang's branch relaxation and patches calls,
20//! and reports any name that was called but never defined.
21
22use alloc::collections::BTreeMap;
23use alloc::string::{String, ToString};
24use alloc::vec::Vec;
25use core::fmt;
26
27use isa_lang::x86_64::{
28    AsmError, Assembler, Cond as ICond, EncodeError, Inst as IInst, Label, Mem as IMem,
29    Mnemonic as M, Operand as IOp, Reg as IReg, Scale as IScale, Size,
30};
31
32use super::table::{DESCS, ENCODINGS, Enc, Fam, Src};
33use super::{GPR, R10, R11, REGS};
34use crate::mir::{
35    Block, BlockCall, Function, ImplicitKind, Inst, Mem, MirError, Operand, Scale, SlotKind,
36    StackSlot,
37};
38use crate::moves::{Loc, Move, MoveEnv, MoveError, MoveResolver, Source, Step};
39use crate::regs::{PReg, Reg, RegClass};
40use crate::target::frame::{FrameError, FrameInput, FrameLayout, FrameStep};
41use crate::target::{InstKind, OperandRule};
42
43/// Why a function could not be emitted.
44///
45/// # Examples
46///
47/// ```
48/// use backend_lang::mir::{Function, Operand};
49/// use backend_lang::x86_64::{op, EmitError, GPR, SYSV};
50///
51/// // Emission needs physical registers: run register allocation first.
52/// let mut f = Function::new("f", &SYSV);
53/// let b = f.block()?;
54/// let v = f.vreg(GPR)?;
55/// f.push(b, op::MOV64RI, &[v.into(), Operand::Imm(1)])?;
56/// f.push(b, op::RET, &[])?;
57/// let err = backend_lang::emit(&f).unwrap_err();
58/// assert!(matches!(err, EmitError::VirtualRegister { .. }));
59/// # Ok::<(), backend_lang::mir::MirError>(())
60/// ```
61#[derive(Clone, Debug, PartialEq, Eq)]
62#[non_exhaustive]
63pub enum EmitError {
64    /// The function is malformed ([`Function::verify`] fails).
65    Mir(MirError),
66    /// The frame cannot be laid out.
67    Frame(FrameError),
68    /// A parallel copy cannot be resolved.
69    Moves(MoveError),
70    /// The function's target is not this crate's x86-64 description (a
71    /// custom [`Target`](crate::target::Target) must reuse its register and
72    /// instruction tables to be emitted by this emitter).
73    UnsupportedTarget,
74    /// A virtual register remains (in an instruction, or, with `inst` absent,
75    /// in a block parameter). Emission runs after register allocation.
76    VirtualRegister {
77        /// The block.
78        block: Block,
79        /// The instruction, if not a parameter.
80        inst: Option<Inst>,
81    },
82    /// A tied use is not the same register as its definition. The register
83    /// allocator must give them one register (or insert a copy).
84    TiedMismatch {
85        /// The instruction.
86        inst: Inst,
87    },
88    /// The body writes the stack pointer, or the frame pointer while it is
89    /// kept (in an instruction, or, with `inst` absent, as a block
90    /// parameter). The frame owns both.
91    ReservedWrite {
92        /// The block.
93        block: Block,
94        /// The instruction, if not a parameter.
95        inst: Option<Inst>,
96    },
97    /// The operation needs an instruction isa-lang 0.2 does not encode: a
98    /// move of a vector register, or a Win64 prologue saving one. (With
99    /// `inst` absent: a prologue, epilogue, or edge move.)
100    Unencodable {
101        /// The instruction, if one.
102        inst: Option<Inst>,
103    },
104    /// isa-lang refused an instruction (with `inst` absent: a prologue,
105    /// epilogue, or edge move).
106    Encode {
107        /// The instruction, if one.
108        inst: Option<Inst>,
109        /// isa-lang's reason.
110        error: EncodeError,
111    },
112    /// The assembler failed (code beyond 2 GiB, or a label error).
113    Asm(AsmError),
114    /// A function was called (or its address taken) but never emitted.
115    UndefinedSymbol(String),
116    /// Two functions with one name were emitted.
117    DuplicateSymbol(String),
118    /// A frame large enough to need a probe loop takes its counter in `r11`
119    /// or `r10`, and the entry block receives values in both.
120    ProbeScratch,
121}
122
123impl fmt::Display for EmitError {
124    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
125        match self {
126            EmitError::Mir(e) => fmt::Display::fmt(e, f),
127            EmitError::Frame(e) => fmt::Display::fmt(e, f),
128            EmitError::Moves(e) => fmt::Display::fmt(e, f),
129            EmitError::UnsupportedTarget => {
130                f.write_str("the function's target is not the x86-64 description this emitter encodes")
131            }
132            EmitError::VirtualRegister { block, inst } => match inst {
133                Some(i) => write!(f, "{i} in {block} still names a virtual register; allocate registers first"),
134                None => write!(f, "a parameter of {block} is a virtual register; allocate registers first"),
135            },
136            EmitError::TiedMismatch { inst } => write!(
137                f,
138                "{inst}: a tied use must be the same register as its definition"
139            ),
140            EmitError::ReservedWrite { block, inst } => match inst {
141                Some(i) => write!(f, "{i} in {block} writes the stack or frame pointer"),
142                None => write!(f, "a parameter of {block} is the stack or frame pointer"),
143            },
144            EmitError::Unencodable { inst } => match inst {
145                Some(i) => write!(f, "{i}: isa-lang 0.2 has no encoding for this vector-register operation"),
146                None => f.write_str("a frame or edge move needs a vector-register instruction isa-lang 0.2 does not encode"),
147            },
148            EmitError::Encode { inst, error } => match inst {
149                Some(i) => write!(f, "{i}: {error}"),
150                None => write!(f, "frame or edge move: {error}"),
151            },
152            EmitError::Asm(e) => fmt::Display::fmt(e, f),
153            EmitError::UndefinedSymbol(name) => {
154                write!(f, "`{name}` is called but no function of that name was emitted")
155            }
156            EmitError::DuplicateSymbol(name) => {
157                write!(f, "two functions named `{name}` were emitted")
158            }
159            EmitError::ProbeScratch => f.write_str(
160                "the stack probe loop needs r10 or r11, and the entry block receives values in both",
161            ),
162        }
163    }
164}
165
166impl core::error::Error for EmitError {
167    fn source(&self) -> Option<&(dyn core::error::Error + 'static)> {
168        match self {
169            EmitError::Mir(e) => Some(e),
170            EmitError::Frame(e) => Some(e),
171            EmitError::Moves(e) => Some(e),
172            EmitError::Encode { error, .. } => Some(error),
173            EmitError::Asm(e) => Some(e),
174            _ => None,
175        }
176    }
177}
178
179impl From<MirError> for EmitError {
180    fn from(e: MirError) -> EmitError {
181        EmitError::Mir(e)
182    }
183}
184
185impl From<FrameError> for EmitError {
186    fn from(e: FrameError) -> EmitError {
187        EmitError::Frame(e)
188    }
189}
190
191impl From<MoveError> for EmitError {
192    fn from(e: MoveError) -> EmitError {
193        EmitError::Moves(e)
194    }
195}
196
197/// What emission decided about one function.
198///
199/// # Examples
200///
201/// ```
202/// use backend_lang::mir::Function;
203/// use backend_lang::x86_64::{op, Emitter, SYSV};
204///
205/// let mut f = Function::new("f", &SYSV);
206/// let b = f.block()?;
207/// f.push(b, op::RET, &[])?;
208/// let mut e = Emitter::new();
209/// let info = e.function(&f)?;
210/// assert_eq!(info.frame().alloc(), 0);
211/// # Ok::<(), Box<dyn std::error::Error>>(())
212/// ```
213#[derive(Clone, Debug, PartialEq, Eq)]
214pub struct FunctionInfo {
215    frame: FrameLayout,
216}
217
218impl FunctionInfo {
219    /// The frame as laid out, including any hidden slots edge moves needed
220    /// (numbered after the function's own).
221    ///
222    /// # Examples
223    ///
224    /// ```
225    /// use backend_lang::mir::{Function, SlotKind};
226    /// use backend_lang::x86_64::{op, Emitter, SYSV};
227    ///
228    /// let mut f = Function::new("f", &SYSV);
229    /// let s = f.stack_slot(SlotKind::Local { size: 8, align: 8 })?;
230    /// let b = f.block()?;
231    /// f.push(b, op::RET, &[])?;
232    /// let info = Emitter::new().function(&f)?;
233    /// assert!(info.frame().slot_offset(s).is_some());
234    /// # Ok::<(), Box<dyn std::error::Error>>(())
235    /// ```
236    #[inline]
237    #[must_use]
238    pub fn frame(&self) -> &FrameLayout {
239        &self.frame
240    }
241}
242
243/// Machine code with the offset of each function.
244///
245/// # Examples
246///
247/// ```
248/// use backend_lang::mir::Function;
249/// use backend_lang::x86_64::{op, Emitter, SYSV};
250///
251/// let mut f = Function::new("f", &SYSV);
252/// let b = f.block()?;
253/// f.push(b, op::RET, &[])?;
254/// let mut e = Emitter::new();
255/// e.function(&f)?;
256/// let program = e.finish()?;
257/// assert_eq!(program.symbol("f"), Some(0));
258/// // push rbp; mov rbp, rsp; pop rbp; ret
259/// assert_eq!(program.bytes(), [0x55, 0x48, 0x89, 0xE5, 0x5D, 0xC3]);
260/// # Ok::<(), Box<dyn std::error::Error>>(())
261/// ```
262#[derive(Clone, Debug, PartialEq, Eq)]
263pub struct Program {
264    bytes: Vec<u8>,
265    symbols: Vec<(String, usize)>,
266}
267
268impl Program {
269    /// The machine code.
270    ///
271    /// # Examples
272    ///
273    /// ```
274    /// use backend_lang::x86_64::Emitter;
275    ///
276    /// assert!(Emitter::new().finish()?.bytes().is_empty());
277    /// # Ok::<(), backend_lang::x86_64::EmitError>(())
278    /// ```
279    #[inline]
280    #[must_use]
281    pub fn bytes(&self) -> &[u8] {
282        &self.bytes
283    }
284
285    /// The machine code, by value.
286    ///
287    /// # Examples
288    ///
289    /// ```
290    /// use backend_lang::x86_64::Emitter;
291    ///
292    /// assert!(Emitter::new().finish()?.into_bytes().is_empty());
293    /// # Ok::<(), backend_lang::x86_64::EmitError>(())
294    /// ```
295    #[must_use]
296    pub fn into_bytes(self) -> Vec<u8> {
297        self.bytes
298    }
299
300    /// The offset of the function named `name`.
301    ///
302    /// # Examples
303    ///
304    /// ```
305    /// use backend_lang::x86_64::Emitter;
306    ///
307    /// assert_eq!(Emitter::new().finish()?.symbol("missing"), None);
308    /// # Ok::<(), backend_lang::x86_64::EmitError>(())
309    /// ```
310    #[must_use]
311    pub fn symbol(&self, name: &str) -> Option<usize> {
312        self.symbols
313            .iter()
314            .find(|(n, _)| n == name)
315            .map(|&(_, off)| off)
316    }
317
318    /// Every function and its offset, in name order.
319    ///
320    /// # Examples
321    ///
322    /// ```
323    /// use backend_lang::x86_64::Emitter;
324    ///
325    /// assert_eq!(Emitter::new().finish()?.symbols().count(), 0);
326    /// # Ok::<(), backend_lang::x86_64::EmitError>(())
327    /// ```
328    pub fn symbols(&self) -> impl Iterator<Item = (&str, usize)> {
329        self.symbols.iter().map(|(n, o)| (n.as_str(), *o))
330    }
331}
332
333#[derive(Clone, Copy, Debug)]
334struct Sym {
335    label: Label,
336    defined: bool,
337}
338
339/// Emits functions into one buffer of x86-64 machine code.
340///
341/// # Examples
342///
343/// Two functions, one calling the other:
344///
345/// ```
346/// use backend_lang::mir::{Effects, Function, Operand};
347/// use backend_lang::x86_64::{op, Emitter, SYSV, RAX};
348///
349/// let mut answer = Function::new("answer", &SYSV);
350/// let b = answer.block()?;
351/// answer.push(b, op::MOV32RI, &[RAX.into(), Operand::Imm(42)])?;
352/// answer.push_with(b, op::RET, &[], Effects::new().uses(&[RAX]))?;
353///
354/// let mut main = Function::new("main", &SYSV);
355/// let b = main.block()?;
356/// let callee = main.symbol("answer")?;
357/// main.push_with(b, op::CALL, &[callee.into()], Effects::new().defs(&[RAX]).clobbers(SYSV.call_clobbers()))?;
358/// main.push_with(b, op::RET, &[], Effects::new().uses(&[RAX]))?;
359///
360/// let mut e = Emitter::new();
361/// e.function(&main)?;
362/// e.function(&answer)?;
363/// let program = e.finish()?;
364/// assert_eq!(program.symbol("main"), Some(0));
365/// assert!(program.symbol("answer").is_some());
366/// # Ok::<(), Box<dyn std::error::Error>>(())
367/// ```
368#[derive(Debug, Default)]
369pub struct Emitter {
370    asm: Assembler,
371    symbols: BTreeMap<String, Sym>,
372    resolver: MoveResolver,
373    moves: Vec<Move>,
374    steps: Vec<Step>,
375    sites: Vec<(u32, u32)>,
376    labels: Vec<Label>,
377}
378
379/// Per-function state while emitting its body.
380struct Ctx<'a> {
381    f: &'a Function,
382    frame: &'a FrameLayout,
383    site: usize,
384}
385
386impl Emitter {
387    /// An empty emitter.
388    ///
389    /// # Examples
390    ///
391    /// ```
392    /// use backend_lang::x86_64::Emitter;
393    ///
394    /// assert!(Emitter::new().finish()?.bytes().is_empty());
395    /// # Ok::<(), backend_lang::x86_64::EmitError>(())
396    /// ```
397    #[must_use]
398    pub fn new() -> Emitter {
399        Emitter::default()
400    }
401
402    /// An empty emitter with room for `bytes` bytes of code.
403    ///
404    /// # Examples
405    ///
406    /// ```
407    /// use backend_lang::x86_64::Emitter;
408    ///
409    /// let _e = Emitter::with_capacity(1 << 20);
410    /// ```
411    #[must_use]
412    pub fn with_capacity(bytes: usize) -> Emitter {
413        Emitter {
414            asm: Assembler::with_capacity(bytes),
415            ..Emitter::default()
416        }
417    }
418
419    /// Emits one function: verifies it, checks it uses only physical
420    /// registers, lays out its frame, and encodes its prologue, blocks, and
421    /// epilogues.
422    ///
423    /// # Errors
424    ///
425    /// An [`EmitError`] naming the problem. After an error the emitter may
426    /// hold part of the function; discard it.
427    ///
428    /// # Examples
429    ///
430    /// ```
431    /// use backend_lang::mir::{Function, Operand};
432    /// use backend_lang::x86_64::{op, Emitter, WIN64, RAX};
433    ///
434    /// let mut f = Function::new("seven", &WIN64);
435    /// let b = f.block()?;
436    /// f.push(b, op::MOV32RI, &[RAX.into(), Operand::Imm(7)])?;
437    /// f.push(b, op::RET, &[])?;
438    /// let mut e = Emitter::new();
439    /// e.function(&f)?;
440    /// // push rbp; mov rbp, rsp; mov eax, 7; pop rbp; ret
441    /// assert_eq!(e.finish()?.bytes(), [0x55, 0x48, 0x89, 0xE5, 0xB8, 7, 0, 0, 0, 0x5D, 0xC3]);
442    /// # Ok::<(), Box<dyn std::error::Error>>(())
443    /// ```
444    pub fn function(&mut self, f: &Function) -> Result<FunctionInfo, EmitError> {
445        let target = f.target();
446        if !core::ptr::eq(target.insts(), &DESCS[..]) || !core::ptr::eq(target.regs(), &REGS[..]) {
447            return Err(EmitError::UnsupportedTarget);
448        }
449        f.verify()?;
450        check_physical(f)?;
451
452        // Resolve every parallel copy first: the frame needs to know whether
453        // any of them borrows the hidden slots.
454        let base = f.slots().len();
455        let scratch = StackSlot::from_index(base);
456        let victim = StackSlot::from_index(base + 1);
457        let env = MoveEnv::new()
458            .with_scratch_slot(scratch)
459            .with_victim_slot(victim);
460        let (mut need_scratch, mut need_victim) = (false, false);
461        self.steps.clear();
462        self.sites.clear();
463        for block in f.blocks() {
464            for &inst in f.insts(block) {
465                let Some(opcode) = f.opcode(inst) else {
466                    continue;
467                };
468                let ops = f.operands(inst);
469                let mut site =
470                    |em: &mut Emitter, pairs: &mut dyn Iterator<Item = (Operand, Operand)>| {
471                        em.moves.clear();
472                        for (d, s) in pairs {
473                            em.moves.push(to_move(f, d, s)?);
474                        }
475                        let start = em.steps.len();
476                        let used = em
477                            .resolver
478                            .resolve(target, &em.moves, &env, &mut em.steps)?;
479                        need_scratch |= used.scratch_slot;
480                        need_victim |= used.victim_slot;
481                        em.sites.push((start as u32, em.steps.len() as u32));
482                        Ok::<(), EmitError>(())
483                    };
484                match ENCODINGS.get(opcode.index()) {
485                    Some(Enc::Copy) => {
486                        site(
487                            self,
488                            &mut ops.first().copied().zip(ops.get(1).copied()).into_iter(),
489                        )?;
490                    }
491                    Some(Enc::Pcopy) => {
492                        let (d, s) = ops.split_at(ops.len() / 2);
493                        site(self, &mut d.iter().copied().zip(s.iter().copied()))?;
494                    }
495                    Some(Enc::Jmp | Enc::Jcc) => {
496                        for op in ops {
497                            if let Operand::Block(call) = op {
498                                let params = f.params(call.block()).iter().copied();
499                                site(self, &mut params.zip(f.args(*call).iter().copied()))?;
500                            }
501                        }
502                    }
503                    _ => {}
504                }
505            }
506        }
507
508        let mut slots: Vec<SlotKind> = Vec::with_capacity(base + 2);
509        slots.extend_from_slice(f.slots());
510        for used in [need_scratch, need_victim] {
511            slots.push(if used {
512                SlotKind::Local {
513                    size: 16,
514                    align: 16,
515                }
516            } else {
517                SlotKind::Local { size: 0, align: 1 }
518            });
519        }
520        let frame = f.abi().layout_frame(&FrameInput {
521            slots: &slots,
522            written: f.written_regs(),
523            has_calls: f.has_calls(),
524            outgoing: f.outgoing(),
525            frame_pointer: f.frame_pointer(),
526        })?;
527
528        let entry = self.define(f.name())?;
529        self.asm.bind(entry).map_err(EmitError::Asm)?;
530        let probe_reg = probe_scratch(f)?;
531        for &step in frame.prologue() {
532            self.frame_step(step, probe_reg)?;
533        }
534        self.labels.clear();
535        for _ in 0..f.block_count() {
536            let l = self.asm.label();
537            self.labels.push(l);
538        }
539        let mut ctx = Ctx {
540            f,
541            frame: &frame,
542            site: 0,
543        };
544        for (bi, block) in f.blocks().enumerate() {
545            let label = self.labels[bi];
546            self.asm.bind(label).map_err(EmitError::Asm)?;
547            for &inst in f.insts(block) {
548                self.inst(&mut ctx, bi, inst)?;
549            }
550        }
551        Ok(FunctionInfo { frame })
552    }
553
554    /// Finishes the code: relaxes branches, patches calls, and returns the
555    /// bytes with every function's offset.
556    ///
557    /// # Errors
558    ///
559    /// [`EmitError::UndefinedSymbol`] for the first name (in name order)
560    /// that was called but never emitted; [`EmitError::Asm`] if the code
561    /// exceeds 2 GiB.
562    ///
563    /// # Examples
564    ///
565    /// ```
566    /// use backend_lang::mir::Function;
567    /// use backend_lang::x86_64::{op, EmitError, Emitter, SYSV};
568    ///
569    /// let mut f = Function::new("f", &SYSV);
570    /// let b = f.block()?;
571    /// let g = f.symbol("g")?;
572    /// f.push(b, op::CALL, &[g.into()])?;
573    /// f.push(b, op::RET, &[])?;
574    /// let mut e = Emitter::new();
575    /// e.function(&f)?;
576    /// assert_eq!(e.finish().unwrap_err(), EmitError::UndefinedSymbol("g".into()));
577    /// # Ok::<(), Box<dyn std::error::Error>>(())
578    /// ```
579    pub fn finish(self) -> Result<Program, EmitError> {
580        if let Some((name, _)) = self.symbols.iter().find(|(_, s)| !s.defined) {
581            return Err(EmitError::UndefinedSymbol(name.clone()));
582        }
583        let code = self.asm.finish().map_err(EmitError::Asm)?;
584        let symbols = self
585            .symbols
586            .iter()
587            .filter_map(|(n, s)| code.label_offset(s.label).map(|o| (n.clone(), o)))
588            .collect();
589        Ok(Program {
590            bytes: code.into_bytes(),
591            symbols,
592        })
593    }
594
595    fn label_for(&mut self, name: &str) -> Label {
596        if let Some(s) = self.symbols.get(name) {
597            return s.label;
598        }
599        let label = self.asm.label();
600        let _ = self.symbols.insert(
601            name.to_string(),
602            Sym {
603                label,
604                defined: false,
605            },
606        );
607        label
608    }
609
610    fn define(&mut self, name: &str) -> Result<Label, EmitError> {
611        let label = self.label_for(name);
612        match self.symbols.get_mut(name) {
613            Some(s) if s.defined => Err(EmitError::DuplicateSymbol(name.to_string())),
614            Some(s) => {
615                s.defined = true;
616                Ok(label)
617            }
618            None => Ok(label),
619        }
620    }
621
622    fn emit(&mut self, inst: Option<Inst>, i: &IInst) -> Result<(), EmitError> {
623        self.asm.emit(i).map_err(|e| asm_error(inst, e))
624    }
625
626    fn frame_step(&mut self, step: FrameStep, probe_reg: PReg) -> Result<(), EmitError> {
627        let rsp = IOp::Reg(IReg::RSP);
628        match step {
629            FrameStep::Push(r) => {
630                self.emit(None, &IInst::new(M::Push, [ireg(None, r, Size::Qword)?]))
631            }
632            FrameStep::Pop(r) => {
633                self.emit(None, &IInst::new(M::Pop, [ireg(None, r, Size::Qword)?]))
634            }
635            FrameStep::SetFramePointer => {
636                self.emit(None, &IInst::new(M::Mov, [IOp::Reg(IReg::RBP), rsp]))
637            }
638            FrameStep::Alloc { bytes, probe } if probe == 0 || bytes < probe => {
639                self.emit(None, &IInst::new(M::Sub, [rsp, IOp::Imm(i64::from(bytes))]))
640            }
641            FrameStep::Alloc { bytes, probe } => self.probe(bytes, probe, probe_reg),
642            FrameStep::Free(bytes) => {
643                self.emit(None, &IInst::new(M::Add, [rsp, IOp::Imm(i64::from(bytes))]))
644            }
645            _ => Err(EmitError::Unencodable { inst: None }),
646        }
647    }
648
649    /// Allocates `bytes` one `page` at a time, touching each new page, so the
650    /// guard page below the stack is never skipped. Up to four pages are
651    /// unrolled; beyond that a counted loop runs in `counter` (a
652    /// caller-saved register the convention does not pass arguments in).
653    fn probe(&mut self, bytes: u32, page: u32, counter: PReg) -> Result<(), EmitError> {
654        let rsp = IOp::Reg(IReg::RSP);
655        let touch = IInst::new(M::Test, [IMem::new(Size::Qword, IReg::RSP).into(), rsp]);
656        let step = IInst::new(M::Sub, [rsp, IOp::Imm(i64::from(page))]);
657        let pages = bytes / page;
658        let rest = bytes % page;
659        if pages <= 4 {
660            for _ in 0..pages {
661                self.emit(None, &step)?;
662                self.emit(None, &touch)?;
663            }
664        } else {
665            let c = ireg(None, counter, Size::Dword)?;
666            self.emit(None, &IInst::new(M::Mov, [c, IOp::Imm(i64::from(pages))]))?;
667            let top = self.asm.label();
668            self.asm.bind(top).map_err(EmitError::Asm)?;
669            self.emit(None, &step)?;
670            self.emit(None, &touch)?;
671            self.emit(None, &IInst::new(M::Dec, [c]))?;
672            self.asm.jcc(ICond::Ne, top).map_err(EmitError::Asm)?;
673        }
674        if rest > 0 {
675            self.emit(None, &IInst::new(M::Sub, [rsp, IOp::Imm(i64::from(rest))]))?;
676        }
677        Ok(())
678    }
679
680    /// Emits the steps of the next parallel-copy site.
681    fn site(&mut self, ctx: &mut Ctx<'_>) -> Result<bool, EmitError> {
682        let (start, end) = self.sites.get(ctx.site).copied().unwrap_or((0, 0));
683        ctx.site += 1;
684        for i in start as usize..end as usize {
685            let step = self.steps[i];
686            self.step(ctx.frame, step)?;
687        }
688        Ok(end > start)
689    }
690
691    fn next_site_empty(&self, ctx: &Ctx<'_>, ahead: usize) -> bool {
692        self.sites
693            .get(ctx.site + ahead)
694            .is_none_or(|&(s, e)| s == e)
695    }
696
697    fn step(&mut self, frame: &FrameLayout, step: Step) -> Result<(), EmitError> {
698        let gpr = |class: RegClass| {
699            if class == GPR {
700                Ok(())
701            } else {
702                Err(EmitError::Unencodable { inst: None })
703            }
704        };
705        match step {
706            Step::Swap { a, b, class } => {
707                gpr(class)?;
708                let i = IInst::new(
709                    M::Xchg,
710                    [ireg(None, a, Size::Qword)?, ireg(None, b, Size::Qword)?],
711                );
712                self.emit(None, &i)
713            }
714            Step::Move { dst, src, class } => {
715                gpr(class)?;
716                let i = match (dst, src) {
717                    (Loc::Reg(d), Source::Imm(v)) => return self.mov_imm(None, d, v),
718                    (Loc::Reg(d), Source::Loc(Loc::Reg(s))) => IInst::new(
719                        M::Mov,
720                        [ireg(None, d, Size::Qword)?, ireg(None, s, Size::Qword)?],
721                    ),
722                    (Loc::Reg(d), Source::Loc(Loc::Slot(s))) => IInst::new(
723                        M::Mov,
724                        [
725                            ireg(None, d, Size::Qword)?,
726                            slot_mem(frame, s, 0, Size::Qword)?.into(),
727                        ],
728                    ),
729                    (Loc::Slot(d), Source::Loc(Loc::Reg(s))) => IInst::new(
730                        M::Mov,
731                        [
732                            slot_mem(frame, d, 0, Size::Qword)?.into(),
733                            ireg(None, s, Size::Qword)?,
734                        ],
735                    ),
736                    (Loc::Slot(d), Source::Imm(v)) => IInst::new(
737                        M::Mov,
738                        [slot_mem(frame, d, 0, Size::Qword)?.into(), IOp::Imm(v)],
739                    ),
740                    // The resolver legalizes memory-to-memory moves away.
741                    (Loc::Slot(_), Source::Loc(Loc::Slot(_))) => {
742                        return Err(EmitError::Unencodable { inst: None });
743                    }
744                };
745                self.emit(None, &i)
746            }
747        }
748    }
749
750    /// `mov r64, imm`, as `mov r32, imm32` when the value is below 2^32 (the
751    /// upper half is zeroed either way).
752    fn mov_imm(&mut self, inst: Option<Inst>, reg: PReg, value: i64) -> Result<(), EmitError> {
753        let i = if (0..=i64::from(u32::MAX)).contains(&value) {
754            IInst::new(
755                M::Mov,
756                [
757                    ireg(inst, reg, Size::Dword)?,
758                    IOp::Imm(i64::from(value as u32 as i32)),
759                ],
760            )
761        } else {
762            IInst::new(M::Mov, [ireg(inst, reg, Size::Qword)?, IOp::Imm(value)])
763        };
764        self.emit(inst, &i)
765    }
766
767    fn inst(&mut self, ctx: &mut Ctx<'_>, bi: usize, inst: Inst) -> Result<(), EmitError> {
768        let f = ctx.f;
769        let Some(opcode) = f.opcode(inst) else {
770            return Ok(());
771        };
772        let ops = f.operands(inst);
773        let enc = ENCODINGS
774            .get(opcode.index())
775            .copied()
776            .ok_or(EmitError::UnsupportedTarget)?;
777        let next = Block::from_index(bi + 1);
778        match enc {
779            Enc::Copy | Enc::Pcopy => {
780                let _ = self.site(ctx)?;
781                Ok(())
782            }
783            Enc::Jmp => {
784                let call = block_operand(ops, 0, inst)?;
785                let _ = self.site(ctx)?;
786                if call.block() != next {
787                    self.jmp(call.block())?;
788                }
789                Ok(())
790            }
791            Enc::Jcc => {
792                let cond = cond_operand(ops, 0, inst)?;
793                let then = block_operand(ops, 1, inst)?;
794                let other = block_operand(ops, 2, inst)?;
795                let then_moves = !self.next_site_empty(ctx, 0);
796                let else_moves = !self.next_site_empty(ctx, 1);
797                if !then_moves {
798                    self.jcc(cond, then.block())?;
799                    let _ = self.site(ctx)?;
800                    let _ = self.site(ctx)?;
801                } else if !else_moves {
802                    self.jcc(cond.negate(), other.block())?;
803                    let _ = self.site(ctx)?;
804                    if then.block() != next {
805                        self.jmp(then.block())?;
806                    }
807                    let _ = self.site(ctx)?;
808                    return Ok(());
809                } else {
810                    let stub = self.asm.label();
811                    self.asm.jcc(cond.negate(), stub).map_err(EmitError::Asm)?;
812                    let _ = self.site(ctx)?;
813                    self.jmp(then.block())?;
814                    self.asm.bind(stub).map_err(EmitError::Asm)?;
815                    let _ = self.site(ctx)?;
816                }
817                if other.block() != next {
818                    self.jmp(other.block())?;
819                }
820                Ok(())
821            }
822            Enc::Ret => {
823                for &step in ctx.frame.epilogue() {
824                    self.frame_step(step, R11)?;
825                }
826                self.emit(Some(inst), &IInst::new(M::Ret, []))
827            }
828            Enc::Call => match ops.first() {
829                Some(Operand::Symbol(s)) => {
830                    let name = f
831                        .symbol_name(*s)
832                        .ok_or(EmitError::Mir(MirError::UnknownSymbol(*s)))?;
833                    let label = self.label_for(name);
834                    self.asm.call(label).map_err(|e| asm_error(Some(inst), e))
835                }
836                Some(op) => {
837                    let target = self.operand(ctx, inst, op, Size::Qword)?;
838                    self.emit(Some(inst), &IInst::new(M::Call, [target]))
839                }
840                None => Err(EmitError::Mir(MirError::OperandShape { inst, index: 0 })),
841            },
842            Enc::MovImm64 => match (
843                ops.first().and_then(Operand::reg).and_then(Reg::as_phys),
844                ops.get(1),
845            ) {
846                (Some(d), Some(Operand::Imm(v))) => self.mov_imm(Some(inst), d, *v),
847                _ => Err(EmitError::Mir(MirError::OperandShape { inst, index: 0 })),
848            },
849            Enc::Raw(bytes) => self.asm.bytes(bytes).map_err(|e| asm_error(Some(inst), e)),
850            Enc::Isa {
851                fam,
852                ops: srcs,
853                cond,
854            } => {
855                let mnemonic = match fam {
856                    Fam::Plain(m) => m,
857                    Fam::Setcc => M::Setcc(cond_operand(ops, usize::from(cond), inst)?),
858                    Fam::Cmovcc => M::Cmovcc(cond_operand(ops, usize::from(cond), inst)?),
859                };
860                let mut out = [IOp::Imm(0); 3];
861                let mut rip = None;
862                for (k, src) in srcs.iter().enumerate().take(3) {
863                    out[k] = match *src {
864                        Src::Fixed(r) => IOp::Reg(r),
865                        Src::Op(n, size) => match ops.get(usize::from(n)) {
866                            Some(Operand::Symbol(s)) => {
867                                rip = Some(*s);
868                                IOp::Mem(IMem::rip(size, 0))
869                            }
870                            Some(op) => self.operand(ctx, inst, op, size)?,
871                            None => {
872                                return Err(EmitError::Mir(MirError::OperandShape {
873                                    inst,
874                                    index: usize::from(n),
875                                }));
876                            }
877                        },
878                    };
879                }
880                let i = IInst::from_slice(mnemonic, &out[..srcs.len().min(3)])
881                    .ok_or(EmitError::Unencodable { inst: Some(inst) })?;
882                match rip {
883                    Some(s) => {
884                        let name = f
885                            .symbol_name(s)
886                            .ok_or(EmitError::Mir(MirError::UnknownSymbol(s)))?;
887                        let label = self.label_for(name);
888                        self.asm
889                            .emit_rip(&i, label)
890                            .map_err(|e| asm_error(Some(inst), e))
891                    }
892                    None => self.emit(Some(inst), &i),
893                }
894            }
895        }
896    }
897
898    fn jmp(&mut self, block: Block) -> Result<(), EmitError> {
899        let label = self
900            .labels
901            .get(block.index())
902            .copied()
903            .ok_or(EmitError::Mir(MirError::UnknownBlock(block)))?;
904        self.asm.jmp(label).map_err(EmitError::Asm)
905    }
906
907    fn jcc(&mut self, cond: ICond, block: Block) -> Result<(), EmitError> {
908        let label = self
909            .labels
910            .get(block.index())
911            .copied()
912            .ok_or(EmitError::Mir(MirError::UnknownBlock(block)))?;
913        self.asm.jcc(cond, label).map_err(EmitError::Asm)
914    }
915
916    fn operand(
917        &self,
918        ctx: &Ctx<'_>,
919        inst: Inst,
920        op: &Operand,
921        size: Size,
922    ) -> Result<IOp, EmitError> {
923        Ok(match *op {
924            Operand::Reg(r) => {
925                let p = r.as_phys().ok_or(EmitError::VirtualRegister {
926                    block: ctx.f.inst_block(inst).unwrap_or(Block::new(0)),
927                    inst: Some(inst),
928                })?;
929                ireg(Some(inst), p, size)?
930            }
931            Operand::Imm(v) => IOp::Imm(v),
932            Operand::Mem(m) => IOp::Mem(mem(inst, &m, size)?),
933            Operand::Slot { slot, offset } => IOp::Mem(slot_mem(ctx.frame, slot, offset, size)?),
934            _ => return Err(EmitError::Unencodable { inst: Some(inst) }),
935        })
936    }
937}
938
939fn asm_error(inst: Option<Inst>, e: AsmError) -> EmitError {
940    match e {
941        AsmError::Encode(error) => EmitError::Encode { inst, error },
942        other => EmitError::Asm(other),
943    }
944}
945
946/// The isa-lang register for a general-purpose physical register.
947fn ireg(inst: Option<Inst>, p: PReg, size: Size) -> Result<IOp, EmitError> {
948    let info = REGS.get(p.index()).ok_or(EmitError::Unencodable { inst })?;
949    if info.class() != GPR {
950        return Err(EmitError::Unencodable { inst });
951    }
952    IReg::new(size, info.hw())
953        .map(IOp::Reg)
954        .ok_or(EmitError::Unencodable { inst })
955}
956
957fn qword(inst: Inst, r: Reg) -> Result<IReg, EmitError> {
958    let p = r
959        .as_phys()
960        .ok_or(EmitError::Unencodable { inst: Some(inst) })?;
961    match ireg(Some(inst), p, Size::Qword)? {
962        IOp::Reg(r) => Ok(r),
963        _ => Err(EmitError::Unencodable { inst: Some(inst) }),
964    }
965}
966
967fn mem(inst: Inst, m: &Mem, size: Size) -> Result<IMem, EmitError> {
968    let mut out = match m.base_reg() {
969        Some(b) => IMem::new(size, qword(inst, b)?),
970        None => IMem::absolute(size, 0),
971    };
972    if let Some((i, s)) = m.index_reg() {
973        let scale = match s {
974            Scale::X1 => IScale::X1,
975            Scale::X2 => IScale::X2,
976            Scale::X4 => IScale::X4,
977            Scale::X8 => IScale::X8,
978        };
979        out = out.with_index(qword(inst, i)?, scale);
980    }
981    Ok(out.with_disp(m.disp()))
982}
983
984fn slot_mem(
985    frame: &FrameLayout,
986    slot: StackSlot,
987    offset: i32,
988    size: Size,
989) -> Result<IMem, EmitError> {
990    let base = frame
991        .slot_offset(slot)
992        .ok_or(EmitError::Mir(MirError::UnknownSlot(slot)))?;
993    let disp = base
994        .checked_add(offset)
995        .ok_or(EmitError::Frame(FrameError::TooLarge))?;
996    Ok(IMem::new(size, IReg::RSP).with_disp(disp))
997}
998
999fn block_operand(ops: &[Operand], index: usize, inst: Inst) -> Result<BlockCall, EmitError> {
1000    match ops.get(index) {
1001        Some(Operand::Block(c)) => Ok(*c),
1002        _ => Err(EmitError::Mir(MirError::OperandShape { inst, index })),
1003    }
1004}
1005
1006fn cond_operand(ops: &[Operand], index: usize, inst: Inst) -> Result<ICond, EmitError> {
1007    match ops.get(index) {
1008        Some(Operand::Cond(c)) => {
1009            ICond::from_code(c.code()).ok_or(EmitError::Mir(MirError::OperandShape { inst, index }))
1010        }
1011        _ => Err(EmitError::Mir(MirError::OperandShape { inst, index })),
1012    }
1013}
1014
1015/// A parallel-copy pair as a resolver move: the destination is a block
1016/// parameter or a copy's destination, the source an argument.
1017fn to_move(f: &Function, dst: Operand, src: Operand) -> Result<Move, EmitError> {
1018    let class_of = |op: &Operand| op.reg().and_then(|r| f.reg_class(r));
1019    let class = class_of(&dst)
1020        .or_else(|| class_of(&src))
1021        .unwrap_or(f.target().addr_class());
1022    let loc = |op: Operand| -> Option<Loc> {
1023        match op {
1024            Operand::Reg(r) => r.as_phys().map(Loc::Reg),
1025            Operand::Slot { slot, offset: 0 } => Some(Loc::Slot(slot)),
1026            _ => None,
1027        }
1028    };
1029    let bad = EmitError::Unencodable { inst: None };
1030    let d = loc(dst).ok_or(bad.clone())?;
1031    let s = match src {
1032        Operand::Imm(v) => Source::Imm(v),
1033        other => Source::Loc(loc(other).ok_or(bad)?),
1034    };
1035    Ok(Move {
1036        dst: d,
1037        src: s,
1038        class,
1039    })
1040}
1041
1042/// The probe loop's counter: `r11`, or `r10` if the entry block receives a
1043/// value in `r11` (neither carries arguments in SysV or Win64).
1044fn probe_scratch(f: &Function) -> Result<PReg, EmitError> {
1045    let params = f.entry().map_or(&[][..], |e| f.params(e));
1046    let taken = |r: PReg| params.iter().any(|p| p.reg() == Some(r.into()));
1047    [R11, R10]
1048        .into_iter()
1049        .find(|&r| !taken(r))
1050        .ok_or(EmitError::ProbeScratch)
1051}
1052
1053/// Checks the function is ready for emission: physical registers only, tied
1054/// operands equal, and the frame's registers never written by the body.
1055fn check_physical(f: &Function) -> Result<(), EmitError> {
1056    let target = f.target();
1057    let reserved = f.reserved();
1058    for block in f.blocks() {
1059        for p in f.params(block) {
1060            if let Some(r) = p.reg() {
1061                match r.as_phys() {
1062                    None => return Err(EmitError::VirtualRegister { block, inst: None }),
1063                    Some(p) if reserved.contains(p) => {
1064                        return Err(EmitError::ReservedWrite { block, inst: None });
1065                    }
1066                    Some(_) => {}
1067                }
1068            }
1069        }
1070        for &inst in f.insts(block) {
1071            let virt = EmitError::VirtualRegister {
1072                block,
1073                inst: Some(inst),
1074            };
1075            let ops = f.operands(inst);
1076            for op in ops {
1077                let any_virtual = match op {
1078                    Operand::Reg(r) => r.is_virtual(),
1079                    Operand::Mem(m) => m.regs().any(Reg::is_virtual),
1080                    Operand::Block(call) => f
1081                        .args(*call)
1082                        .iter()
1083                        .any(|a| a.reg().is_some_and(Reg::is_virtual)),
1084                    _ => false,
1085                };
1086                if any_virtual {
1087                    return Err(virt);
1088                }
1089            }
1090            let Some(desc) = f.opcode(inst).and_then(|o| target.inst(o)) else {
1091                continue;
1092            };
1093            let defs = match desc.kind() {
1094                InstKind::Copy => 1,
1095                InstKind::ParallelCopy => ops.len() / 2,
1096                _ => desc.defs(),
1097            };
1098            let reserved_write = ops
1099                .iter()
1100                .take(defs)
1101                .filter_map(|o| o.reg().and_then(Reg::as_phys))
1102                .chain(
1103                    f.implicit(inst)
1104                        .iter()
1105                        .filter(|i| i.kind == ImplicitKind::Def)
1106                        .map(|i| i.reg),
1107                )
1108                .chain(desc.implicit_defs().iter().copied())
1109                .any(|p| reserved.contains(p))
1110                || !f.clobbers(inst).intersect(reserved).is_empty();
1111            if reserved_write {
1112                return Err(EmitError::ReservedWrite {
1113                    block,
1114                    inst: Some(inst),
1115                });
1116            }
1117            for (i, rule) in desc.operands().iter().enumerate() {
1118                if let OperandRule::Tied(d) = rule {
1119                    if ops.get(i).and_then(Operand::reg)
1120                        != ops.get(usize::from(*d)).and_then(Operand::reg)
1121                    {
1122                        return Err(EmitError::TiedMismatch { inst });
1123                    }
1124                }
1125            }
1126        }
1127    }
1128    Ok(())
1129}
backend_lang/x86_64/emit.rs

backend_lang/x86_64/
emit.rs
