backend_lang/isel/
mod.rs

1//! Instruction selection: one ir-lang 2.0 function to a MIR function on
2//! virtual registers.
3//!
4//! Blocks and block parameters map one to one (IR.md §15): an IR edge's
5//! arguments become the MIR branch's arguments, resolved as a parallel copy
6//! at emission. Every value of an integer, `bool`, `ptr`, or `ref` type lives
7//! in one general-purpose virtual register, and in this release so does a
8//! float's bit pattern (see below).
9//!
10//! # Value representation
11//!
12//! A value of a type narrower than 64 bits occupies the low bits of its
13//! register; the bits above its width are **unspecified**, exactly as the
14//! x86-64 32-bit operations leave them. Arithmetic on 8-, 16-, and 32-bit
15//! types runs at 32 bits; wherever the upper bits matter (comparisons,
16//! division, right shifts, overflow checks, widening conversions, switch
17//! values, array indices) the value is extended first by its type's
18//! signedness. `bool` is the exception: always exactly 0 or 1, so it can be
19//! tested, stored, and converted directly; booleans entering from outside
20//! (parameters, call results, loads) are normalized.
21//!
22//! # Policies
23//!
24//! Every OPS integer operation is selected under every policy ir-lang can
25//! carry (IR.md §4): `wrap` computes modulo the width; `trap` branches to a
26//! per-function trap block that calls the runtime trap handler
27//! ([`Options::trap_symbol`](crate::Options)) with the OPS code; `error`
28//! (only inside a `check` terminator) branches to the error edge, passing
29//! the OPS code as `err`. Division checks zero, then `MIN / -1`, before it
30//! divides, so the processor never faults. Shifts check, mask, or saturate
31//! their amount (`saturate`, OPS v2: an amount at or past the width shifts
32//! every bit out, leaving the sign for an arithmetic right shift; a negative
33//! amount is still `ShiftOutOfRange`).
34//!
35//! Integer `pow` (OPS v2) is repeated squaring: unrolled when the exponent
36//! is a constant (at most 64 squarings and 64 multiplications), a loop over
37//! the exponent's bits otherwise (at most 64 iterations), each product
38//! checked for overflow under `trap` and `error`. A negative exponent is the
39//! `NegativeExponent` error (code 6) under every policy, which is why
40//! ir-lang 2.0.0-alpha.3 makes every signed `pow` the operation of a `check`
41//! (`BinaryOp::can_error`).
42//!
43//! # Floats as bit patterns
44//!
45//! isa-lang 0.2 encodes no SSE, so this release keeps a float in a
46//! general-purpose register as its bit pattern (`f32` in the low 32 bits,
47//! the upper bits unspecified, like `i32`). Everything that only moves a
48//! value works on floats: constants, `bitcast` to and from the integer of
49//! the same width, loads, stores, `select`, block parameters and edge
50//! arguments. Float `pow` calls the runtime's `ls_pow` routine
51//! ([`Options::pow_f64_symbol`](crate::Options::pow_f64_symbol),
52//! [`Options::pow_f32_symbol`](crate::Options::pow_f32_symbol)) with the bit
53//! patterns in integer registers: ir-lang's own routine, never a platform
54//! libm, so the result is bit-identical to every other tier.
55//!
56//! # What is not selected yet
57//!
58//! Float arithmetic other than `pow`, float comparisons, conversions between
59//! floats and integers, and float arguments and results (both conventions
60//! pass them in vector registers) wait on isa-lang's SSE forms (ISSUES P11),
61//! as do `lock`-prefixed atomic read-modify-writes other than `xchg` and
62//! `cmpxchg`; `aapcs64` waits on the AArch64 target; 32-bit pointer modules
63//! on a 32-bit target. Each is reported as [`IselError::Unsupported`], never
64//! miscompiled.
65
66mod call;
67mod mem;
68mod ops;
69mod term;
70
71use alloc::collections::BTreeMap;
72use alloc::string::String;
73use alloc::vec;
74use alloc::vec::Vec;
75use core::fmt;
76
77use ir_lang::{
78    Block as IBlock, CallConv, FuncId, InstData, Module, PointerWidth, StackSlot as IStackSlot,
79    Terminator, Type, Value,
80};
81
82use crate::compile::Options;
83use crate::mir::{self, Block, Effects, Function, Inst, MirError, Operand, StackSlot, Symbol};
84use crate::regs::{PReg, Reg};
85use crate::target::abi::Abi;
86use crate::x86_64::{self, GPR, op};
87
88/// Why a function could not be selected.
89///
90/// # Examples
91///
92/// ```
93/// use backend_lang::isel::IselError;
94/// use backend_lang::Options;
95/// use ir_lang::{Linkage, Module, Signature, Type};
96///
97/// let mut m = Module::new("m");
98/// let f = m.declare_function("f", &Signature::new(&[Type::F64], &[]), Linkage::Export)?;
99/// let mut b = m.build(f)?;
100/// b.ret(&[])?;
101/// let err = backend_lang::isel::select(&m, f, &Options::sysv()).unwrap_err();
102/// assert!(matches!(err, IselError::Unsupported { .. }));
103/// # Ok::<(), Box<dyn std::error::Error>>(())
104/// ```
105#[derive(Clone, Debug, PartialEq, Eq)]
106#[non_exhaustive]
107pub enum IselError {
108    /// The module does not validate (ir-lang's [`Module::validate`]).
109    Invalid(ir_lang::ValidationError),
110    /// The function handle is not in the module, or it is an import.
111    NoBody(FuncId),
112    /// A construct this release does not select, and why.
113    Unsupported {
114        /// The function.
115        func: FuncId,
116        /// What, and what it waits on.
117        what: &'static str,
118    },
119    /// Building the MIR failed (a 32-bit table limit, or an internal
120    /// inconsistency reported rather than panicking).
121    Mir(MirError),
122}
123
124impl fmt::Display for IselError {
125    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
126        match self {
127            IselError::Invalid(e) => write!(f, "invalid module: {e}"),
128            IselError::NoBody(func) => write!(f, "{func} has no body to select"),
129            IselError::Unsupported { func, what } => write!(f, "{func}: {what}"),
130            IselError::Mir(e) => write!(f, "building machine IR: {e}"),
131        }
132    }
133}
134
135impl core::error::Error for IselError {
136    fn source(&self) -> Option<&(dyn core::error::Error + 'static)> {
137        match self {
138            IselError::Invalid(e) => Some(e),
139            IselError::Mir(e) => Some(e),
140            _ => None,
141        }
142    }
143}
144
145impl From<MirError> for IselError {
146    fn from(e: MirError) -> IselError {
147        IselError::Mir(e)
148    }
149}
150
151type Result<T> = core::result::Result<T, IselError>;
152
153/// Selects `func` of a validated `module` into a MIR function on virtual
154/// registers, named after the function and under the calling convention its
155/// signature selects. The module is validated first.
156///
157/// # Errors
158///
159/// [`IselError`].
160///
161/// # Examples
162///
163/// ```
164/// use backend_lang::Options;
165/// use ir_lang::{Linkage, Module, Overflow, Signature, Type};
166///
167/// let mut m = Module::new("m");
168/// let f = m.declare_function("inc", &Signature::new(&[Type::I64], &[Type::I64]), Linkage::Export)?;
169/// let mut b = m.build(f)?;
170/// let x = b.param(0)?;
171/// let one = b.iconst(Type::I64, 1)?;
172/// let y = b.add(x, one, Overflow::Wrap)?;
173/// b.ret(&[y])?;
174///
175/// let mir = backend_lang::isel::select(&m, f, &Options::sysv())?;
176/// assert_eq!(mir.name(), "inc");
177/// assert!(mir.to_string().contains("add64"));
178/// # Ok::<(), Box<dyn std::error::Error>>(())
179/// ```
180pub fn select(module: &Module, func: FuncId, options: &Options) -> Result<Function> {
181    module.validate().map_err(IselError::Invalid)?;
182    select_validated(module, func, options)
183}
184
185/// [`select`] for a module the caller has already validated.
186pub(crate) fn select_validated(
187    module: &Module,
188    func: FuncId,
189    options: &Options,
190) -> Result<Function> {
191    let decl = module.func_decl(func).ok_or(IselError::NoBody(func))?;
192    let body = module.function(func).ok_or(IselError::NoBody(func))?;
193    let sig = module.func_signature(func).ok_or(IselError::NoBody(func))?;
194    if module.pointer_width() != PointerWidth::P64 {
195        return Err(IselError::Unsupported {
196            func,
197            what: "32-bit pointers need a 32-bit target",
198        });
199    }
200    let abi = abi_for(func, sig.conv, options)?;
201    let mut sel = Sel::new(module, func, body, decl.name(), abi, options);
202    sel.run(sig)?;
203    Ok(sel.f)
204}
205
206/// The convention a signature's tag selects.
207pub(crate) fn abi_for(func: FuncId, conv: CallConv, options: &Options) -> Result<&'static Abi> {
208    match conv {
209        CallConv::Fast | CallConv::C => Ok(options.abi),
210        CallConv::SysV64 => Ok(&x86_64::SYSV),
211        CallConv::Win64 => Ok(&x86_64::WIN64),
212        _ => Err(IselError::Unsupported {
213            func,
214            what: "the aapcs64 convention needs the AArch64 target",
215        }),
216    }
217}
218
219/// How a narrow value is widened when its upper bits matter.
220#[derive(Clone, Copy, Debug, PartialEq, Eq)]
221pub(crate) enum Ext {
222    /// By the type's signedness.
223    Type,
224    /// With zeros.
225    Zero,
226    /// With copies of the sign bit.
227    Sign,
228}
229
230/// What a failing operation does: branch to a `check`'s error edge, or trap.
231#[derive(Clone, Copy, Debug)]
232pub(crate) enum Fail<'a> {
233    /// The error edge of a `check` (the OPS code becomes `err`).
234    Edge(&'a ir_lang::BlockCall),
235    /// A deterministic trap with the OPS code.
236    Trap,
237}
238
239/// Where an address comes from, for folding constant offsets into memory
240/// operands.
241#[derive(Clone, Copy, Debug)]
242pub(crate) enum Addr {
243    /// `slot + offset`, addressed from the stack pointer.
244    Slot(StackSlot, i64),
245    /// `reg + offset`.
246    Reg(Reg, i64),
247}
248
249/// The selection state of one function.
250pub(crate) struct Sel<'m> {
251    pub(crate) m: &'m Module,
252    pub(crate) func: FuncId,
253    pub(crate) irf: &'m ir_lang::Function,
254    pub(crate) opts: &'m Options,
255    pub(crate) abi: &'static Abi,
256    pub(crate) f: Function,
257    /// The register of each IR value.
258    vals: Vec<Option<Reg>>,
259    /// The bits of each IR value known to be a constant.
260    consts: Vec<Option<u64>>,
261    /// Folded addresses of IR address values.
262    addrs: Vec<Option<Addr>>,
263    /// Uses of each IR value.
264    uses: Vec<u32>,
265    /// Compares lowered at their single use (a branch or select in the same
266    /// block) so the flags reach it.
267    pub(crate) fused: Vec<bool>,
268    blocks: Vec<Option<Block>>,
269    /// IR slot → MIR slot, and the alignment to round its address up to when
270    /// the frame cannot align it.
271    slots: Vec<(StackSlot, u32)>,
272    syms: BTreeMap<String, Symbol>,
273    traps: BTreeMap<u32, Block>,
274    gc_slots: Vec<StackSlot>,
275    incoming: BTreeMap<u32, StackSlot>,
276    fence_slot: Option<StackSlot>,
277    /// The block instructions are appended to.
278    pub(crate) cur: Block,
279}
280
281impl<'m> Sel<'m> {
282    fn new(
283        m: &'m Module,
284        func: FuncId,
285        irf: &'m ir_lang::Function,
286        name: &str,
287        abi: &'static Abi,
288        opts: &'m Options,
289    ) -> Sel<'m> {
290        let nv = irf.value_count();
291        let mut f = Function::with_capacity(name, abi, irf.inst_count() * 2, irf.inst_count() * 6);
292        if !opts.frame_pointer {
293            f.omit_frame_pointer();
294        }
295        Sel {
296            m,
297            func,
298            irf,
299            opts,
300            abi,
301            f,
302            vals: vec![None; nv],
303            consts: vec![None; nv],
304            addrs: vec![None; nv],
305            uses: vec![0; nv],
306            fused: vec![false; nv],
307            blocks: vec![None; irf.block_count()],
308            slots: Vec::new(),
309            syms: BTreeMap::new(),
310            traps: BTreeMap::new(),
311            gc_slots: Vec::new(),
312            incoming: BTreeMap::new(),
313            fence_slot: None,
314            cur: Block::new(0),
315        }
316    }
317
318    pub(crate) fn unsupported<T>(&self, what: &'static str) -> Result<T> {
319        Err(IselError::Unsupported {
320            func: self.func,
321            what,
322        })
323    }
324
325    fn run(&mut self, sig: &ir_lang::Signature) -> Result<()> {
326        let irf = self.irf;
327        // Reverse postorder of the reachable IR blocks: MIR blocks are laid
328        // out in this order, the entry first.
329        let order = ir_rpo(irf);
330        self.count_uses(&order);
331        for &b in &order {
332            let mb = self.f.block()?;
333            self.blocks[b.index()] = Some(mb);
334        }
335        for &b in &order {
336            if b == irf.entry() {
337                continue;
338            }
339            let mb = self.block(b)?;
340            for &p in irf.block_params(b) {
341                // Any type: a float parameter holds its bit pattern.
342                let _ = self.ty_any(p)?;
343                let v = self.new_reg()?;
344                self.vals[p.index()] = Some(v);
345                self.f.add_param(mb, v.into())?;
346            }
347        }
348        for slot in 0..irf.slot_count() {
349            let data = irf
350                .slot(IStackSlot::from_u32(slot as u32))
351                .ok_or(MirError::Limit)?;
352            // The frame aligns slots to at most 16; a larger alignment is
353            // reached by rounding the slot's address up at run time inside a
354            // slot made large enough for it.
355            let (size, align, round) = if data.align > 16 {
356                (data.size.saturating_add(data.align - 16), 16, data.align)
357            } else {
358                (data.size, data.align.max(1), 0)
359            };
360            let s = self.f.stack_slot(mir::SlotKind::Local { size, align })?;
361            self.slots.push((s, round));
362        }
363        self.entry(sig)?;
364        for &b in &order {
365            self.cur = self.block(b)?;
366            let insts: Vec<ir_lang::Inst> = irf.insts(b).collect();
367            for inst in insts {
368                self.inst(inst)?;
369            }
370            let term = irf.terminator(b).ok_or(MirError::NoBlocks)?;
371            self.terminator(b, term)?;
372        }
373        Ok(())
374    }
375
376    /// The entry: incoming arguments from their ABI locations into virtual
377    /// registers with one parallel copy.
378    fn entry(&mut self, sig: &ir_lang::Signature) -> Result<()> {
379        let irf = self.irf;
380        let entry = self.block(irf.entry())?;
381        self.cur = entry;
382        let classes = self.arg_classes(&sig.params)?;
383        let mut locs = Vec::new();
384        let _ = self.abi.assign_args(&classes, &mut locs);
385        let mut dsts = Vec::with_capacity(locs.len());
386        let mut srcs = Vec::with_capacity(locs.len());
387        for (k, (&p, loc)) in irf.block_params(irf.entry()).iter().zip(&locs).enumerate() {
388            let src: Operand = match *loc {
389                crate::target::abi::ArgLoc::Reg(r) => {
390                    self.f.add_param(entry, r.into())?;
391                    r.into()
392                }
393                crate::target::abi::ArgLoc::Stack(off) => {
394                    let s = self.incoming_slot(off)?;
395                    self.f.add_param(entry, Operand::slot(s))?;
396                    Operand::slot(s)
397                }
398            };
399            let v = self.new_reg()?;
400            dsts.push(Operand::from(v));
401            srcs.push(src);
402            self.vals[p.index()] = Some(v);
403            let _ = k;
404        }
405        if !dsts.is_empty() {
406            dsts.extend(srcs);
407            let _ = self.f.push(entry, op::PCOPY, &dsts)?;
408        }
409        // Booleans from outside are normalized to 0 or 1.
410        for &p in irf.block_params(irf.entry()) {
411            if irf.value_type(p) == Some(Type::Bool) {
412                let r = self.val(p)?;
413                let n = self.emit_def(op::MOVZX8, &[r.into()])?;
414                self.vals[p.index()] = Some(n);
415            }
416        }
417        Ok(())
418    }
419
420    /// The incoming-argument slot at `offset` above the canonical frame
421    /// address (one per offset, shared by the entry and tail calls).
422    pub(crate) fn incoming_slot(&mut self, offset: u32) -> Result<StackSlot> {
423        if let Some(&s) = self.incoming.get(&offset) {
424            return Ok(s);
425        }
426        let s = self
427            .f
428            .stack_slot(mir::SlotKind::Incoming { offset, size: 8 })?;
429        let _ = self.incoming.insert(offset, s);
430        Ok(s)
431    }
432
433    /// The `i`-th GC root slot (shared by every safepoint: each reloads its
434    /// relocated references right after its call).
435    pub(crate) fn gc_slot(&mut self, i: usize) -> Result<StackSlot> {
436        while self.gc_slots.len() <= i {
437            let s = self
438                .f
439                .stack_slot(mir::SlotKind::Local { size: 8, align: 8 })?;
440            self.gc_slots.push(s);
441        }
442        self.gc_slots
443            .get(i)
444            .copied()
445            .ok_or(IselError::Mir(MirError::Limit))
446    }
447
448    /// A slot whose only use is a full-barrier `xchg`.
449    pub(crate) fn fence_slot(&mut self) -> Result<StackSlot> {
450        if let Some(s) = self.fence_slot {
451            return Ok(s);
452        }
453        let s = self
454            .f
455            .stack_slot(mir::SlotKind::Local { size: 8, align: 8 })?;
456        self.fence_slot = Some(s);
457        Ok(s)
458    }
459
460    fn count_uses(&mut self, order: &[IBlock]) {
461        let irf = self.irf;
462        for &b in order {
463            for inst in irf.insts(b) {
464                if let Some(data) = irf.inst(inst) {
465                    data.for_each_operand(|v| {
466                        let v = irf.resolve(v);
467                        if let Some(n) = self.uses.get_mut(v.index()) {
468                            *n += 1;
469                        }
470                    });
471                }
472            }
473            if let Some(t) = irf.terminator(b) {
474                t.for_each_operand(|v| {
475                    let v = irf.resolve(v);
476                    if let Some(n) = self.uses.get_mut(v.index()) {
477                        *n += 1;
478                    }
479                });
480            }
481        }
482        // A compare whose only use is the branch or a select later in its own
483        // block is lowered there, so the flags it sets reach the use. The
484        // candidates of the current block are stamped with its position in
485        // `order` (plus one), so each test is O(1) however long the block.
486        let mut stamp: Vec<u32> = vec![0; self.fused.len()];
487        for (k, &b) in order.iter().enumerate() {
488            let here = k as u32 + 1;
489            let candidate = |stamp: &[u32], c: Value| stamp.get(c.index()) == Some(&here);
490            for inst in irf.insts(b) {
491                if let Some(InstData::Compare { args, .. }) = irf.inst(inst) {
492                    let r = irf.results(inst);
493                    if let Some(v) = r.first() {
494                        let fusible_ty = irf
495                            .value_type(irf.resolve(args[0]))
496                            .is_some_and(|t| !t.is_float());
497                        if self.uses.get(v.index()) == Some(&1) && fusible_ty {
498                            if let Some(s) = stamp.get_mut(v.index()) {
499                                *s = here;
500                            }
501                        }
502                    }
503                }
504                if let Some(InstData::Select { cond, .. }) = irf.inst(inst) {
505                    let c = irf.resolve(*cond);
506                    if candidate(&stamp, c) {
507                        self.fused[c.index()] = true;
508                    }
509                }
510            }
511            if let Some(Terminator::Branch { cond, .. }) = irf.terminator(b) {
512                let c = irf.resolve(*cond);
513                if candidate(&stamp, c) {
514                    self.fused[c.index()] = true;
515                }
516            }
517        }
518    }
519
520    /// The MIR block of an IR block.
521    pub(crate) fn block(&self, b: IBlock) -> Result<Block> {
522        self.blocks
523            .get(b.index())
524            .copied()
525            .flatten()
526            .ok_or(IselError::Mir(MirError::UnknownBlock(Block::new(
527                b.as_u32(),
528            ))))
529    }
530
531    /// A fresh general-purpose virtual register.
532    pub(crate) fn new_reg(&mut self) -> Result<Reg> {
533        Ok(self.f.vreg(GPR)?)
534    }
535
536    /// The type of an IR value that an integer operation reads; floats are
537    /// refused (their arithmetic waits on isa-lang's SSE forms).
538    pub(crate) fn ty(&self, v: Value) -> Result<Type> {
539        let t = self.ty_any(v)?;
540        if t.is_float() {
541            return self.unsupported(FLOAT_ARITH);
542        }
543        Ok(t)
544    }
545
546    /// The type of an IR value, floats included: for code that only moves
547    /// a value (edges, `select`, loads, stores, `bitcast`), where a float is
548    /// its bit pattern in a general-purpose register.
549    pub(crate) fn ty_any(&self, v: Value) -> Result<Type> {
550        self.irf
551            .value_type(self.irf.resolve(v))
552            .ok_or(IselError::Mir(MirError::Limit))
553    }
554
555    /// The register holding IR value `v`.
556    pub(crate) fn val(&self, v: Value) -> Result<Reg> {
557        let v = self.irf.resolve(v);
558        self.vals
559            .get(v.index())
560            .copied()
561            .flatten()
562            .ok_or(IselError::Mir(MirError::Limit))
563    }
564
565    /// The constant bits of `v`, if it is one.
566    pub(crate) fn konst(&self, v: Value) -> Option<u64> {
567        let v = self.irf.resolve(v);
568        self.consts.get(v.index()).copied().flatten()
569    }
570
571    /// The operands of a commutative two-address operation in the order that
572    /// spares a copy: the definition shares the first operand's register,
573    /// which it can only do when that operand dies here. So a constant moves
574    /// to the right (where it becomes an immediate), and a left operand still
575    /// needed later trades places with a right operand used only here.
576    pub(crate) fn commute(&self, args: [Value; 2]) -> [Value; 2] {
577        let uses = |v: Value| {
578            let v = self.irf.resolve(v);
579            self.uses.get(v.index()).copied().unwrap_or(0)
580        };
581        let (k0, k1) = (self.konst(args[0]).is_some(), self.konst(args[1]).is_some());
582        if (k0 && !k1) || (!k1 && uses(args[0]) > 1 && uses(args[1]) == 1) {
583            [args[1], args[0]]
584        } else {
585            args
586        }
587    }
588
589    pub(crate) fn set_val(&mut self, v: Value, r: Reg) {
590        if let Some(slot) = self.vals.get_mut(v.index()) {
591            *slot = Some(r);
592        }
593    }
594
595    pub(crate) fn set_addr(&mut self, v: Value, a: Addr) {
596        if let Some(slot) = self.addrs.get_mut(v.index()) {
597            *slot = Some(a);
598        }
599    }
600
601    pub(crate) fn addr_of(&self, v: Value) -> Option<Addr> {
602        let v = self.irf.resolve(v);
603        self.addrs.get(v.index()).copied().flatten()
604    }
605
606    pub(crate) fn mir_slot(&self, s: IStackSlot) -> Result<(StackSlot, u32)> {
607        self.slots
608            .get(s.index())
609            .copied()
610            .ok_or(IselError::Mir(MirError::UnknownSlot(StackSlot::new(
611                s.as_u32(),
612            ))))
613    }
614
615    /// The symbol for `name` in the function under construction.
616    pub(crate) fn symbol(&mut self, name: &str) -> Result<Symbol> {
617        if let Some(&s) = self.syms.get(name) {
618            return Ok(s);
619        }
620        let s = self.f.symbol(name)?;
621        let _ = self.syms.insert(String::from(name), s);
622        Ok(s)
623    }
624
625    /// Appends an instruction to the current block.
626    pub(crate) fn emit(&mut self, opcode: crate::target::Opcode, ops: &[Operand]) -> Result<Inst> {
627        Ok(self.f.push(self.cur, opcode, ops)?)
628    }
629
630    /// Appends an instruction with extra implicit operands.
631    pub(crate) fn emit_with(
632        &mut self,
633        opcode: crate::target::Opcode,
634        ops: &[Operand],
635        effects: Effects<'_>,
636    ) -> Result<Inst> {
637        Ok(self.f.push_with(self.cur, opcode, ops, effects)?)
638    }
639
640    /// Appends `d = opcode ops...` with a fresh `d`, returning it.
641    pub(crate) fn emit_def(
642        &mut self,
643        opcode: crate::target::Opcode,
644        ops: &[Operand],
645    ) -> Result<Reg> {
646        let d = self.new_reg()?;
647        let mut all = [Operand::Imm(0); 5];
648        all[0] = d.into();
649        let n = ops.len().min(4);
650        all[1..=n].copy_from_slice(&ops[..n]);
651        let _ = self.emit(opcode, &all[..=n])?;
652        Ok(d)
653    }
654
655    /// `d = src` into a fresh register.
656    pub(crate) fn copy_to_new(&mut self, src: Operand) -> Result<Reg> {
657        let d = self.new_reg()?;
658        let _ = self.emit(op::COPY, &[d.into(), src])?;
659        Ok(d)
660    }
661
662    /// Starts a new block (with no parameters) and makes it current.
663    pub(crate) fn new_block(&mut self) -> Result<Block> {
664        Ok(self.f.block()?)
665    }
666
667    /// `jcc cc, then(), else()` from the current block.
668    pub(crate) fn branch(
669        &mut self,
670        cc: isa_lang::x86_64::Cond,
671        then: Block,
672        other: Block,
673    ) -> Result<()> {
674        let t = self.f.block_call(then, &[])?;
675        let e = self.f.block_call(other, &[])?;
676        let _ = self.emit(op::JCC, &[x86_64::cond(cc).into(), t.into(), e.into()])?;
677        Ok(())
678    }
679
680    /// `jmp target(args)` from the current block.
681    pub(crate) fn jump(&mut self, target: Block, args: &[Operand]) -> Result<()> {
682        let c = self.f.block_call(target, args)?;
683        let _ = self.emit(op::JMP, &[c.into()])?;
684        Ok(())
685    }
686
687    /// The trap block for `code`: the code into the first argument register,
688    /// a call to the trap handler, `ud2` after it in case it returns.
689    pub(crate) fn trap_block(&mut self, code: u32) -> Result<Block> {
690        if let Some(&b) = self.traps.get(&code) {
691            return Ok(b);
692        }
693        let saved = self.cur;
694        let b = self.new_block()?;
695        self.cur = b;
696        self.trap_call(code)?;
697        self.cur = saved;
698        let _ = self.traps.insert(code, b);
699        Ok(b)
700    }
701
702    /// In the current block: call the trap handler with `code`, then `ud2`.
703    pub(crate) fn trap_call(&mut self, code: u32) -> Result<()> {
704        let c_abi = self.opts.abi;
705        let arg = first_int_arg(c_abi)?;
706        let sym = self.symbol(self.opts.trap_symbol)?;
707        let _ = self.emit(op::COPY, &[arg.into(), Operand::Imm(i64::from(code))])?;
708        let uses = [arg];
709        let _ = self.emit_with(
710            op::CALL,
711            &[sym.into()],
712            Effects::new().uses(&uses).clobbers(c_abi.call_clobbers()),
713        )?;
714        let _ = self.emit(op::UD2, &[])?;
715        Ok(())
716    }
717
718    /// Branches to the failure of an operation when `cc` holds, continuing in
719    /// a fresh block otherwise. `code` is the OPS error code.
720    pub(crate) fn fail_if(
721        &mut self,
722        cc: isa_lang::x86_64::Cond,
723        fail: Fail<'_>,
724        code: u32,
725    ) -> Result<()> {
726        let next = self.new_block()?;
727        match fail {
728            Fail::Trap => {
729                let t = self.trap_block(code)?;
730                self.branch(cc, t, next)?;
731            }
732            Fail::Edge(dest) => {
733                let call = self.edge(dest, &[], None, Some(Operand::Imm(i64::from(code))))?;
734                let e = self.f.block_call(next, &[])?;
735                let _ = self.emit(op::JCC, &[x86_64::cond(cc).into(), call.into(), e.into()])?;
736            }
737        }
738        self.cur = next;
739        Ok(())
740    }
741
742    /// Lowers an IR edge to a MIR branch target: arguments are values (an
743    /// immediate when constant), call results, the exception payload, or the
744    /// error code.
745    pub(crate) fn edge(
746        &mut self,
747        dest: &ir_lang::BlockCall,
748        results: &[Operand],
749        exn: Option<Operand>,
750        err: Option<Operand>,
751    ) -> Result<mir::BlockCall> {
752        let target = self.block(dest.block)?;
753        let mut args = Vec::with_capacity(dest.args.len());
754        for a in &dest.args {
755            let op = match *a {
756                ir_lang::BlockArg::Value(v) => self.operand(v)?,
757                ir_lang::BlockArg::Result(i) => results
758                    .get(i as usize)
759                    .copied()
760                    .ok_or(IselError::Mir(MirError::Limit))?,
761                ir_lang::BlockArg::Exception => exn.ok_or(IselError::Mir(MirError::Limit))?,
762                ir_lang::BlockArg::ErrorCode => err.ok_or(IselError::Mir(MirError::Limit))?,
763                _ => return self.unsupported("an edge argument kind this release does not know"),
764            };
765            args.push(op);
766        }
767        Ok(self.f.block_call(target, &args)?)
768    }
769
770    /// A value as an operand: an immediate when it is a constant, else its
771    /// register.
772    pub(crate) fn operand(&self, v: Value) -> Result<Operand> {
773        match self.konst(v) {
774            Some(bits) => Ok(Operand::Imm(bits as i64)),
775            None => Ok(self.val(v)?.into()),
776        }
777    }
778
779    fn inst(&mut self, inst: ir_lang::Inst) -> Result<()> {
780        let irf = self.irf;
781        let data = irf.inst(inst).ok_or(MirError::Limit)?.clone();
782        let results = irf.results(inst);
783        match data {
784            InstData::Const { bits, .. } => {
785                // A float constant is its bit pattern (`f32` in the low 32
786                // bits), like any other constant.
787                let r = results.first().ok_or(MirError::Limit)?;
788                let d = self.emit_def(op::MOV64RI, &[Operand::Imm(bits as i64)])?;
789                self.set_val(r, d);
790                if let Some(c) = self.consts.get_mut(r.index()) {
791                    *c = Some(bits);
792                }
793                Ok(())
794            }
795            InstData::Unary { op, policy, arg } => {
796                let r = results.first().ok_or(MirError::Limit)?;
797                let d = self.unary(op, policy, arg, Fail::Trap)?;
798                self.set_val(r, d);
799                Ok(())
800            }
801            InstData::Binary { op, policy, args } => {
802                let r = results.first().ok_or(MirError::Limit)?;
803                let d = self.binary(op, policy, args, Fail::Trap)?;
804                self.set_val(r, d);
805                Ok(())
806            }
807            InstData::Compare { op, args } => {
808                let r = results.first().ok_or(MirError::Limit)?;
809                if self.fused.get(r.index()).copied().unwrap_or(false) {
810                    return Ok(());
811                }
812                let cc = self.compare(op, args)?;
813                let s = self.emit_def(op::SETCC, &[x86_64::cond(cc).into()])?;
814                let d = self.emit_def(op::MOVZX8, &[s.into()])?;
815                self.set_val(r, d);
816                Ok(())
817            }
818            InstData::Convert {
819                op,
820                policy,
821                to,
822                arg,
823            } => {
824                let r = results.first().ok_or(MirError::Limit)?;
825                let d = self.convert(op, policy, to, arg, Fail::Trap)?;
826                self.set_val(r, d);
827                Ok(())
828            }
829            InstData::Select { cond, args } => {
830                let r = results.first().ok_or(MirError::Limit)?;
831                let _ = self.ty_any(r)?;
832                let cc = self.condition(cond)?;
833                let (a, b) = (self.val(args[0])?, self.val(args[1])?);
834                // d = cc ? a : b
835                let d =
836                    self.emit_def(op::CMOV64, &[b.into(), a.into(), x86_64::cond(cc).into()])?;
837                self.set_val(r, d);
838                Ok(())
839            }
840            InstData::Fma { .. } => self.unsupported(FLOAT_ARITH),
841            InstData::Call(call) => self.call(&call, results),
842            InstData::Safepoint { gc } => self.safepoint(&gc, results),
843            other => self.memory(&other, results),
844        }
845    }
846
847    /// The condition code that holds when IR boolean `cond` is true, with
848    /// the flags set: a fused compare, or a test of the boolean.
849    pub(crate) fn condition(&mut self, cond: Value) -> Result<isa_lang::x86_64::Cond> {
850        let c = self.irf.resolve(cond);
851        if self.fused.get(c.index()).copied().unwrap_or(false) {
852            if let Some(inst) = self.irf.defining_inst(c) {
853                if let Some(InstData::Compare { op, args }) = self.irf.inst(inst) {
854                    let (op, args) = (*op, *args);
855                    return self.compare(op, args);
856                }
857            }
858        }
859        let r = self.val(c)?;
860        let _ = self.emit(op::TEST32, &[r.into(), r.into()])?;
861        Ok(isa_lang::x86_64::Cond::Ne)
862    }
863}
864
865/// Why floating-point arithmetic is refused.
866pub(crate) const FLOAT_ARITH: &str = "floating-point arithmetic waits on isa-lang's SSE forms (ISSUES P11); only pow, bitcast, constants, loads, stores, select, and edges are selected";
867
868/// The first integer argument register of a convention.
869pub(crate) fn first_int_arg(abi: &Abi) -> Result<PReg> {
870    abi.args()
871        .int()
872        .first()
873        .copied()
874        .ok_or(IselError::Mir(MirError::Limit))
875}
876
877/// The reachable blocks of an IR function in reverse postorder.
878fn ir_rpo(f: &ir_lang::Function) -> Vec<IBlock> {
879    let n = f.block_count();
880    let mut seen = vec![false; n];
881    let mut post = Vec::new();
882    let entry = f.entry();
883    if entry.index() >= n {
884        return post;
885    }
886    let mut stack: Vec<(IBlock, Vec<IBlock>, usize)> = Vec::new();
887    let succs = |b: IBlock| -> Vec<IBlock> {
888        f.terminator(b)
889            .map(|t| t.successors().map(|c| c.block).collect())
890            .unwrap_or_default()
891    };
892    seen[entry.index()] = true;
893    stack.push((entry, succs(entry), 0));
894    while let Some(top) = stack.last_mut() {
895        if let Some(&s) = top.1.get(top.2) {
896            top.2 += 1;
897            if s.index() < n && !seen[s.index()] {
898                seen[s.index()] = true;
899                let next = succs(s);
900                stack.push((s, next, 0));
901            }
902        } else {
903            post.push(top.0);
904            let _ = stack.pop();
905        }
906    }
907    post.reverse();
908    post
909}
backend_lang/isel/mod.rs

backend_lang/isel/
mod.rs
