backend_lang/mir/function.rs
1//! A machine function: blocks of target instructions over virtual and
2//! physical registers, with block parameters, stack slots, and symbols.
3
4use alloc::string::String;
5use alloc::vec::Vec;
6
7use super::entity::{Block, Inst, StackSlot, Symbol};
8use super::operand::{BlockCall, Implicit, ImplicitKind, Operand};
9use super::verify::MirError;
10use crate::regs::{PReg, Reg, RegClass, RegSet, VReg};
11use crate::target::abi::Abi;
12use crate::target::frame::{FrameError, FrameInput, FrameLayout};
13use crate::target::{InstKind, Opcode, OperandRule, Target};
14
15/// What a stack slot is.
16///
17/// # Examples
18///
19/// ```
20/// use backend_lang::mir::{Function, SlotKind};
21/// use backend_lang::x86_64::SYSV;
22///
23/// let mut f = Function::new("f", &SYSV);
24/// let local = f.stack_slot(SlotKind::Local { size: 24, align: 8 })?;
25/// let arg = f.stack_slot(SlotKind::Incoming { offset: 0, size: 8 })?;
26/// assert_eq!(f.slot(local), Some(SlotKind::Local { size: 24, align: 8 }));
27/// assert!(matches!(f.slot(arg), Some(SlotKind::Incoming { .. })));
28/// # Ok::<(), backend_lang::mir::MirError>(())
29/// ```
30#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
31#[non_exhaustive]
32pub enum SlotKind {
33 /// Space in this function's frame.
34 Local {
35 /// Bytes.
36 size: u32,
37 /// Alignment in bytes: a power of two up to the stack alignment.
38 align: u32,
39 },
40 /// An argument the caller passed on the stack, at `offset` bytes above
41 /// the canonical frame address (see
42 /// [`ArgLoc::Stack`](crate::target::abi::ArgLoc::Stack)).
43 Incoming {
44 /// Offset from the canonical frame address.
45 offset: u32,
46 /// Bytes.
47 size: u32,
48 },
49}
50
51impl SlotKind {
52 /// The slot's size in bytes.
53 ///
54 /// # Examples
55 ///
56 /// ```
57 /// use backend_lang::mir::SlotKind;
58 ///
59 /// assert_eq!(SlotKind::Incoming { offset: 8, size: 8 }.size(), 8);
60 /// ```
61 #[inline]
62 #[must_use]
63 pub const fn size(self) -> u32 {
64 match self {
65 SlotKind::Local { size, .. } | SlotKind::Incoming { size, .. } => size,
66 }
67 }
68}
69
70/// Extra implicit operands for one instruction: registers it reads and
71/// writes without naming them, and registers it clobbers, beyond what its
72/// opcode always has. Used for calls (argument registers, return registers,
73/// the convention's clobbers), returns (result registers), and system calls.
74///
75/// # Examples
76///
77/// ```
78/// use backend_lang::mir::Effects;
79/// use backend_lang::x86_64::{SYSV, RAX, RDI};
80///
81/// let e = Effects::new().uses(&[RDI]).defs(&[RAX]).clobbers(SYSV.call_clobbers());
82/// assert_eq!(e.uses_regs(), [RDI]);
83/// assert!(e.clobber_set().contains(RAX));
84/// ```
85#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
86pub struct Effects<'a> {
87 uses: &'a [PReg],
88 defs: &'a [PReg],
89 clobbers: RegSet,
90}
91
92impl<'a> Effects<'a> {
93 /// No extra operands.
94 ///
95 /// # Examples
96 ///
97 /// ```
98 /// use backend_lang::mir::Effects;
99 ///
100 /// assert!(Effects::new().uses_regs().is_empty());
101 /// ```
102 #[must_use]
103 pub const fn new() -> Effects<'a> {
104 Effects {
105 uses: &[],
106 defs: &[],
107 clobbers: RegSet::EMPTY,
108 }
109 }
110
111 /// Registers read.
112 ///
113 /// # Examples
114 ///
115 /// ```
116 /// use backend_lang::mir::Effects;
117 /// use backend_lang::x86_64::RSI;
118 ///
119 /// assert_eq!(Effects::new().uses(&[RSI]).uses_regs(), [RSI]);
120 /// ```
121 #[must_use]
122 pub const fn uses(self, regs: &'a [PReg]) -> Effects<'a> {
123 Effects { uses: regs, ..self }
124 }
125
126 /// Registers written with defined values.
127 ///
128 /// # Examples
129 ///
130 /// ```
131 /// use backend_lang::mir::Effects;
132 /// use backend_lang::x86_64::RAX;
133 ///
134 /// assert_eq!(Effects::new().defs(&[RAX]).defs_regs(), [RAX]);
135 /// ```
136 #[must_use]
137 pub const fn defs(self, regs: &'a [PReg]) -> Effects<'a> {
138 Effects { defs: regs, ..self }
139 }
140
141 /// Registers left with unspecified contents.
142 ///
143 /// # Examples
144 ///
145 /// ```
146 /// use backend_lang::RegSet;
147 /// use backend_lang::mir::Effects;
148 /// use backend_lang::x86_64::R11;
149 ///
150 /// assert!(Effects::new().clobbers(RegSet::of(&[R11])).clobber_set().contains(R11));
151 /// ```
152 #[must_use]
153 pub const fn clobbers(self, regs: RegSet) -> Effects<'a> {
154 Effects {
155 clobbers: regs,
156 ..self
157 }
158 }
159
160 /// The registers read.
161 ///
162 /// # Examples
163 ///
164 /// ```
165 /// use backend_lang::mir::Effects;
166 ///
167 /// assert!(Effects::new().uses_regs().is_empty());
168 /// ```
169 #[must_use]
170 pub const fn uses_regs(&self) -> &'a [PReg] {
171 self.uses
172 }
173
174 /// The registers written.
175 ///
176 /// # Examples
177 ///
178 /// ```
179 /// use backend_lang::mir::Effects;
180 ///
181 /// assert!(Effects::new().defs_regs().is_empty());
182 /// ```
183 #[must_use]
184 pub const fn defs_regs(&self) -> &'a [PReg] {
185 self.defs
186 }
187
188 /// The registers clobbered.
189 ///
190 /// # Examples
191 ///
192 /// ```
193 /// use backend_lang::mir::Effects;
194 ///
195 /// assert!(Effects::new().clobber_set().is_empty());
196 /// ```
197 #[must_use]
198 pub const fn clobber_set(&self) -> RegSet {
199 self.clobbers
200 }
201}
202
203/// One instruction's record. Operands, implicit operands, and clobber sets
204/// live in the function's shared pools; the record holds ranges into them.
205#[derive(Clone, Copy, Debug)]
206pub(crate) struct InstData {
207 pub(crate) opcode: Opcode,
208 pub(crate) block: Block,
209 pub(crate) ops: u32,
210 pub(crate) nops: u32,
211 pub(crate) imp: u32,
212 pub(crate) nimp: u32,
213 /// Index into `clobbers`, or `NO_CLOBBERS`.
214 pub(crate) clobber: u32,
215}
216
217pub(crate) const NO_CLOBBERS: u32 = u32::MAX;
218
219#[derive(Clone, Debug, Default)]
220pub(crate) struct BlockData {
221 pub(crate) params: Vec<Operand>,
222 pub(crate) insts: Vec<Inst>,
223}
224
225/// The most entries any one table of a function may hold (instructions,
226/// operands, blocks, slots, symbols): ids are 32-bit.
227pub(crate) const MAX_ENTRIES: usize = u32::MAX as usize - 1;
228
229/// A machine function.
230///
231/// Blocks hold target instructions in order; the first block is the entry.
232/// Instructions name virtual registers (each typed by a register class) or
233/// physical registers, stack slots, and other functions by symbol. Control
234/// flow passes values between blocks through **block parameters**: a branch
235/// names its target with arguments, and on the edge every parameter receives
236/// its argument at once (a parallel copy). Block parameters are SSA's phi
237/// nodes written at the edge, which is the form an SSA register allocator
238/// works on and the form ir-lang already uses; see the crate docs for the
239/// rationale.
240///
241/// Every table is a dense vector indexed by its id type; nothing is
242/// recursive.
243///
244/// # Examples
245///
246/// Sum `1..=n` with virtual registers:
247///
248/// ```
249/// use backend_lang::mir::{Function, Operand};
250/// use backend_lang::x86_64::{self, op, GPR, SYSV};
251/// use isa_lang::x86_64::Cond;
252///
253/// let mut f = Function::new("sum", &SYSV);
254/// let entry = f.block()?;
255/// let head = f.block()?;
256/// let exit = f.block()?;
257/// let n = f.vreg(GPR)?;
258/// f.add_param(entry, n.into())?;
259/// // Parameters come first: branches are checked against them.
260/// let (acc, i) = (f.vreg(GPR)?, f.vreg(GPR)?);
261/// f.add_param(head, acc.into())?;
262/// f.add_param(head, i.into())?;
263/// let result = f.vreg(GPR)?;
264/// f.add_param(exit, result.into())?;
265///
266/// let zero = f.vreg(GPR)?;
267/// f.push(entry, op::MOV64RI, &[zero.into(), Operand::Imm(0)])?;
268/// let to_head = f.block_call(head, &[zero.into(), n.into()])?;
269/// f.push(entry, op::JMP, &[to_head.into()])?;
270///
271/// let (acc2, i2) = (f.vreg(GPR)?, f.vreg(GPR)?);
272/// f.push(head, op::ADD64, &[acc2.into(), acc.into(), i.into()])?;
273/// f.push(head, op::SUB64, &[i2.into(), i.into(), Operand::Imm(1)])?;
274/// let again = f.block_call(head, &[acc2.into(), i2.into()])?;
275/// let done = f.block_call(exit, &[acc2.into()])?;
276/// f.push(head, op::JCC, &[x86_64::cond(Cond::Ne).into(), again.into(), done.into()])?;
277///
278/// f.push(exit, op::RET, &[])?;
279///
280/// f.verify()?;
281/// assert!(f.to_string().contains("%5:gpr = add64 %1, %2"));
282/// # Ok::<(), backend_lang::mir::MirError>(())
283/// ```
284#[derive(Clone, Debug)]
285pub struct Function {
286 name: String,
287 abi: &'static Abi,
288 pub(crate) vregs: Vec<RegClass>,
289 pub(crate) blocks: Vec<BlockData>,
290 pub(crate) insts: Vec<InstData>,
291 pub(crate) operands: Vec<Operand>,
292 pub(crate) args: Vec<Operand>,
293 pub(crate) implicits: Vec<Implicit>,
294 pub(crate) clobbers: Vec<RegSet>,
295 pub(crate) slots: Vec<SlotKind>,
296 pub(crate) symbols: Vec<String>,
297 outgoing: u32,
298 frame_pointer: bool,
299}
300
301/// Fails unless a table of `len` entries has room for one more id.
302fn room(len: usize) -> Result<(), MirError> {
303 next_id(len).map(|_| ())
304}
305
306fn next_id(len: usize) -> Result<u32, MirError> {
307 if len < MAX_ENTRIES {
308 Ok(len as u32)
309 } else {
310 Err(MirError::Limit)
311 }
312}
313
314impl Function {
315 /// An empty function named `name`, under calling convention `abi` (which
316 /// also fixes the target).
317 ///
318 /// # Examples
319 ///
320 /// ```
321 /// use backend_lang::mir::Function;
322 /// use backend_lang::x86_64::WIN64;
323 ///
324 /// let f = Function::new("main", &WIN64);
325 /// assert_eq!(f.name(), "main");
326 /// assert_eq!(f.abi().name(), "win64");
327 /// ```
328 #[must_use]
329 pub fn new(name: &str, abi: &'static Abi) -> Function {
330 Function {
331 name: String::from(name),
332 abi,
333 vregs: Vec::new(),
334 blocks: Vec::new(),
335 insts: Vec::new(),
336 operands: Vec::new(),
337 args: Vec::new(),
338 implicits: Vec::new(),
339 clobbers: Vec::new(),
340 slots: Vec::new(),
341 symbols: Vec::new(),
342 outgoing: 0,
343 frame_pointer: true,
344 }
345 }
346
347 /// An empty function with room for `insts` instructions and `operands`
348 /// operands, so building a large function does not reallocate.
349 ///
350 /// # Examples
351 ///
352 /// ```
353 /// use backend_lang::mir::Function;
354 /// use backend_lang::x86_64::SYSV;
355 ///
356 /// let f = Function::with_capacity("big", &SYSV, 100_000, 300_000);
357 /// assert_eq!(f.inst_count(), 0);
358 /// ```
359 #[must_use]
360 pub fn with_capacity(name: &str, abi: &'static Abi, insts: usize, operands: usize) -> Function {
361 let mut f = Function::new(name, abi);
362 f.insts.reserve(insts);
363 f.operands.reserve(operands);
364 f
365 }
366
367 /// The function's name, which is also the symbol other functions call it
368 /// by.
369 ///
370 /// # Examples
371 ///
372 /// ```
373 /// use backend_lang::mir::Function;
374 /// use backend_lang::x86_64::SYSV;
375 ///
376 /// assert_eq!(Function::new("f", &SYSV).name(), "f");
377 /// ```
378 #[inline]
379 #[must_use]
380 pub fn name(&self) -> &str {
381 &self.name
382 }
383
384 /// The calling convention.
385 ///
386 /// # Examples
387 ///
388 /// ```
389 /// use backend_lang::mir::Function;
390 /// use backend_lang::x86_64::SYSV;
391 ///
392 /// assert_eq!(Function::new("f", &SYSV).abi().name(), "sysv64");
393 /// ```
394 #[inline]
395 #[must_use]
396 pub fn abi(&self) -> &'static Abi {
397 self.abi
398 }
399
400 /// The target (the calling convention's).
401 ///
402 /// # Examples
403 ///
404 /// ```
405 /// use backend_lang::mir::Function;
406 /// use backend_lang::x86_64::SYSV;
407 ///
408 /// assert_eq!(Function::new("f", &SYSV).target().name(), "x86-64");
409 /// ```
410 #[inline]
411 #[must_use]
412 pub fn target(&self) -> &'static Target {
413 self.abi.target()
414 }
415
416 /// A new virtual register of `class`.
417 ///
418 /// # Errors
419 ///
420 /// [`MirError::UnknownClass`] if the target has no such class,
421 /// [`MirError::Limit`] past [`VReg::MAX`] registers.
422 ///
423 /// # Examples
424 ///
425 /// ```
426 /// use backend_lang::RegClass;
427 /// use backend_lang::mir::{Function, MirError};
428 /// use backend_lang::x86_64::{SYSV, VEC};
429 ///
430 /// let mut f = Function::new("f", &SYSV);
431 /// assert!(f.vreg(VEC)?.is_virtual());
432 /// assert_eq!(f.vreg(RegClass::new(7)), Err(MirError::UnknownClass(RegClass::new(7))));
433 /// # Ok::<(), MirError>(())
434 /// ```
435 pub fn vreg(&mut self, class: RegClass) -> Result<Reg, MirError> {
436 if !self.target().has_class(class) {
437 return Err(MirError::UnknownClass(class));
438 }
439 if self.vregs.len() >= VReg::MAX {
440 return Err(MirError::Limit);
441 }
442 let v = VReg::from_index(self.vregs.len() as u32);
443 self.vregs.push(class);
444 Ok(v.into())
445 }
446
447 /// The class of a virtual register, or `None` if the function does not
448 /// have it.
449 ///
450 /// # Examples
451 ///
452 /// ```
453 /// use backend_lang::mir::Function;
454 /// use backend_lang::x86_64::{GPR, SYSV};
455 ///
456 /// let mut f = Function::new("f", &SYSV);
457 /// let v = f.vreg(GPR)?.as_virt().unwrap();
458 /// assert_eq!(f.vreg_class(v), Some(GPR));
459 /// # Ok::<(), backend_lang::mir::MirError>(())
460 /// ```
461 #[inline]
462 #[must_use]
463 pub fn vreg_class(&self, vreg: VReg) -> Option<RegClass> {
464 self.vregs.get(vreg.index()).copied()
465 }
466
467 /// The number of virtual registers.
468 ///
469 /// # Examples
470 ///
471 /// ```
472 /// use backend_lang::mir::Function;
473 /// use backend_lang::x86_64::{GPR, SYSV};
474 ///
475 /// let mut f = Function::new("f", &SYSV);
476 /// let _ = f.vreg(GPR)?;
477 /// assert_eq!(f.vreg_count(), 1);
478 /// # Ok::<(), backend_lang::mir::MirError>(())
479 /// ```
480 #[inline]
481 #[must_use]
482 pub fn vreg_count(&self) -> usize {
483 self.vregs.len()
484 }
485
486 /// The class of any register: a virtual register's declared class, or
487 /// a physical register's class in the target.
488 ///
489 /// # Examples
490 ///
491 /// ```
492 /// use backend_lang::mir::Function;
493 /// use backend_lang::x86_64::{GPR, SYSV, VEC, XMM2};
494 ///
495 /// let mut f = Function::new("f", &SYSV);
496 /// let v = f.vreg(GPR)?;
497 /// assert_eq!(f.reg_class(v), Some(GPR));
498 /// assert_eq!(f.reg_class(XMM2.into()), Some(VEC));
499 /// # Ok::<(), backend_lang::mir::MirError>(())
500 /// ```
501 #[must_use]
502 pub fn reg_class(&self, reg: Reg) -> Option<RegClass> {
503 match (reg.as_phys(), reg.as_virt()) {
504 (Some(p), _) => self.target().class_of(p),
505 (_, Some(v)) => self.vreg_class(v),
506 _ => None,
507 }
508 }
509
510 /// A new, empty block. The first block is the entry.
511 ///
512 /// # Errors
513 ///
514 /// [`MirError::Limit`] past `u32::MAX - 1` blocks.
515 ///
516 /// # Examples
517 ///
518 /// ```
519 /// use backend_lang::mir::Function;
520 /// use backend_lang::x86_64::SYSV;
521 ///
522 /// let mut f = Function::new("f", &SYSV);
523 /// let entry = f.block()?;
524 /// assert_eq!(f.entry(), Some(entry));
525 /// # Ok::<(), backend_lang::mir::MirError>(())
526 /// ```
527 pub fn block(&mut self) -> Result<Block, MirError> {
528 let id = next_id(self.blocks.len())?;
529 self.blocks.push(BlockData::default());
530 Ok(Block::new(id))
531 }
532
533 /// The entry block, if any block exists.
534 ///
535 /// # Examples
536 ///
537 /// ```
538 /// use backend_lang::mir::Function;
539 /// use backend_lang::x86_64::SYSV;
540 ///
541 /// assert_eq!(Function::new("f", &SYSV).entry(), None);
542 /// ```
543 #[inline]
544 #[must_use]
545 pub fn entry(&self) -> Option<Block> {
546 if self.blocks.is_empty() {
547 None
548 } else {
549 Some(Block::new(0))
550 }
551 }
552
553 /// The blocks, in layout order (the order emission lays them out).
554 ///
555 /// # Examples
556 ///
557 /// ```
558 /// use backend_lang::mir::Function;
559 /// use backend_lang::x86_64::SYSV;
560 ///
561 /// let mut f = Function::new("f", &SYSV);
562 /// let a = f.block()?;
563 /// let b = f.block()?;
564 /// assert_eq!(f.blocks().collect::<Vec<_>>(), [a, b]);
565 /// # Ok::<(), backend_lang::mir::MirError>(())
566 /// ```
567 pub fn blocks(&self) -> impl ExactSizeIterator<Item = Block> + '_ {
568 (0..self.blocks.len()).map(Block::from_index)
569 }
570
571 /// The number of blocks.
572 ///
573 /// # Examples
574 ///
575 /// ```
576 /// use backend_lang::mir::Function;
577 /// use backend_lang::x86_64::SYSV;
578 ///
579 /// assert_eq!(Function::new("f", &SYSV).block_count(), 0);
580 /// ```
581 #[inline]
582 #[must_use]
583 pub fn block_count(&self) -> usize {
584 self.blocks.len()
585 }
586
587 /// Appends a parameter to `block`: a register (virtual before
588 /// allocation, physical after) or a whole stack slot
589 /// ([`Operand::slot`]). The entry block's parameters are the function's
590 /// incoming arguments.
591 ///
592 /// # Errors
593 ///
594 /// [`MirError::UnknownBlock`] for a block the function does not have,
595 /// [`MirError::BadParam`] for any other operand shape (including a slot
596 /// operand with an offset), [`MirError::UnknownVReg`],
597 /// [`MirError::UnknownPReg`], or [`MirError::UnknownSlot`] for a register
598 /// or slot the function or target does not have.
599 ///
600 /// # Examples
601 ///
602 /// ```
603 /// use backend_lang::mir::{Function, Operand};
604 /// use backend_lang::x86_64::{RDI, SYSV};
605 ///
606 /// let mut f = Function::new("f", &SYSV);
607 /// let entry = f.block()?;
608 /// f.add_param(entry, RDI.into())?;
609 /// assert_eq!(f.params(entry), [Operand::from(RDI)]);
610 /// assert!(f.add_param(entry, Operand::Imm(1)).is_err());
611 /// # Ok::<(), backend_lang::mir::MirError>(())
612 /// ```
613 pub fn add_param(&mut self, block: Block, param: Operand) -> Result<(), MirError> {
614 match param {
615 Operand::Reg(r) => self.check_reg(r)?,
616 Operand::Slot { slot, offset: 0 } => self.check_slot(slot)?,
617 _ => return Err(MirError::BadParam { block }),
618 }
619 let data = self
620 .blocks
621 .get_mut(block.index())
622 .ok_or(MirError::UnknownBlock(block))?;
623 room(data.params.len())?;
624 data.params.push(param);
625 Ok(())
626 }
627
628 /// A block's parameters (empty for a block the function does not have).
629 ///
630 /// # Examples
631 ///
632 /// ```
633 /// use backend_lang::mir::Function;
634 /// use backend_lang::x86_64::SYSV;
635 ///
636 /// let mut f = Function::new("f", &SYSV);
637 /// let b = f.block()?;
638 /// assert!(f.params(b).is_empty());
639 /// # Ok::<(), backend_lang::mir::MirError>(())
640 /// ```
641 #[inline]
642 #[must_use]
643 pub fn params(&self, block: Block) -> &[Operand] {
644 self.blocks
645 .get(block.index())
646 .map_or(&[], |b| b.params.as_slice())
647 }
648
649 /// A new stack slot.
650 ///
651 /// # Errors
652 ///
653 /// [`MirError::Limit`] past `u32::MAX - 1` slots. Sizes and alignments
654 /// are checked when the frame is laid out.
655 ///
656 /// # Examples
657 ///
658 /// ```
659 /// use backend_lang::mir::{Function, SlotKind};
660 /// use backend_lang::x86_64::SYSV;
661 ///
662 /// let mut f = Function::new("f", &SYSV);
663 /// let s = f.stack_slot(SlotKind::Local { size: 16, align: 16 })?;
664 /// assert_eq!(f.slot(s).map(SlotKind::size), Some(16));
665 /// # Ok::<(), backend_lang::mir::MirError>(())
666 /// ```
667 pub fn stack_slot(&mut self, kind: SlotKind) -> Result<StackSlot, MirError> {
668 let id = next_id(self.slots.len())?;
669 self.slots.push(kind);
670 Ok(StackSlot::new(id))
671 }
672
673 /// A new stack slot sized and aligned to hold one value of `class`.
674 ///
675 /// # Errors
676 ///
677 /// [`MirError::UnknownClass`] for a class the target does not have,
678 /// [`MirError::Limit`] past `u32::MAX - 1` slots.
679 ///
680 /// # Examples
681 ///
682 /// ```
683 /// use backend_lang::mir::{Function, SlotKind};
684 /// use backend_lang::x86_64::{SYSV, VEC};
685 ///
686 /// let mut f = Function::new("f", &SYSV);
687 /// let s = f.spill_slot(VEC)?;
688 /// assert_eq!(f.slot(s), Some(SlotKind::Local { size: 16, align: 16 }));
689 /// # Ok::<(), backend_lang::mir::MirError>(())
690 /// ```
691 pub fn spill_slot(&mut self, class: RegClass) -> Result<StackSlot, MirError> {
692 if !self.target().has_class(class) {
693 return Err(MirError::UnknownClass(class));
694 }
695 let info = self.target().class(class);
696 self.stack_slot(SlotKind::Local {
697 size: info.spill_size(),
698 align: info.spill_align(),
699 })
700 }
701
702 /// A slot's kind, or `None` if the function does not have it.
703 ///
704 /// # Examples
705 ///
706 /// ```
707 /// use backend_lang::mir::{Function, StackSlot};
708 /// use backend_lang::x86_64::SYSV;
709 ///
710 /// assert_eq!(Function::new("f", &SYSV).slot(StackSlot::new(0)), None);
711 /// ```
712 #[inline]
713 #[must_use]
714 pub fn slot(&self, slot: StackSlot) -> Option<SlotKind> {
715 self.slots.get(slot.index()).copied()
716 }
717
718 /// Every slot's kind, indexed by [`StackSlot::index`].
719 ///
720 /// # Examples
721 ///
722 /// ```
723 /// use backend_lang::mir::Function;
724 /// use backend_lang::x86_64::SYSV;
725 ///
726 /// assert!(Function::new("f", &SYSV).slots().is_empty());
727 /// ```
728 #[inline]
729 #[must_use]
730 pub fn slots(&self) -> &[SlotKind] {
731 &self.slots
732 }
733
734 /// A new reference to the function named `name`.
735 ///
736 /// # Errors
737 ///
738 /// [`MirError::Limit`] past `u32::MAX - 1` symbols.
739 ///
740 /// # Examples
741 ///
742 /// ```
743 /// use backend_lang::mir::Function;
744 /// use backend_lang::x86_64::SYSV;
745 ///
746 /// let mut f = Function::new("f", &SYSV);
747 /// let callee = f.symbol("g")?;
748 /// assert_eq!(f.symbol_name(callee), Some("g"));
749 /// # Ok::<(), backend_lang::mir::MirError>(())
750 /// ```
751 pub fn symbol(&mut self, name: &str) -> Result<Symbol, MirError> {
752 let id = next_id(self.symbols.len())?;
753 self.symbols.push(String::from(name));
754 Ok(Symbol::new(id))
755 }
756
757 /// A symbol's name, or `None` if the function does not have it.
758 ///
759 /// # Examples
760 ///
761 /// ```
762 /// use backend_lang::mir::{Function, Symbol};
763 /// use backend_lang::x86_64::SYSV;
764 ///
765 /// assert_eq!(Function::new("f", &SYSV).symbol_name(Symbol::new(0)), None);
766 /// ```
767 #[inline]
768 #[must_use]
769 pub fn symbol_name(&self, symbol: Symbol) -> Option<&str> {
770 self.symbols.get(symbol.index()).map(String::as_str)
771 }
772
773 /// A branch target: `block` with `args` for its parameters, as an
774 /// operand for a jump or branch. The arguments are registers, whole
775 /// stack slots, or immediates.
776 ///
777 /// # Errors
778 ///
779 /// [`MirError::UnknownBlock`], [`MirError::BadArg`] for another operand
780 /// shape, the `Unknown*` errors for registers or slots the function does
781 /// not have, and [`MirError::Limit`] when the argument pool is full.
782 /// Argument counts and classes are checked when the branch is pushed.
783 ///
784 /// # Examples
785 ///
786 /// ```
787 /// use backend_lang::mir::{Function, Operand};
788 /// use backend_lang::x86_64::{op, SYSV};
789 ///
790 /// let mut f = Function::new("f", &SYSV);
791 /// let entry = f.block()?;
792 /// let target = f.block()?;
793 /// let call = f.block_call(target, &[])?;
794 /// f.push(entry, op::JMP, &[call.into()])?;
795 /// # Ok::<(), backend_lang::mir::MirError>(())
796 /// ```
797 pub fn block_call(&mut self, block: Block, args: &[Operand]) -> Result<BlockCall, MirError> {
798 if block.index() >= self.blocks.len() {
799 return Err(MirError::UnknownBlock(block));
800 }
801 for &a in args {
802 match a {
803 Operand::Reg(r) => self.check_reg(r)?,
804 Operand::Slot { slot, offset: 0 } => self.check_slot(slot)?,
805 Operand::Imm(_) => {}
806 _ => return Err(MirError::BadArg { block }),
807 }
808 }
809 let start = next_id(self.args.len())?;
810 let len = u32::try_from(args.len()).map_err(|_| MirError::Limit)?;
811 room(self.args.len().saturating_add(args.len()))?;
812 self.args.extend_from_slice(args);
813 Ok(BlockCall::new(block, start, len))
814 }
815
816 /// The arguments of a branch target (empty for one this function did not
817 /// make).
818 ///
819 /// # Examples
820 ///
821 /// ```
822 /// use backend_lang::mir::{Function, Operand};
823 /// use backend_lang::x86_64::SYSV;
824 ///
825 /// let mut f = Function::new("f", &SYSV);
826 /// let b = f.block()?;
827 /// let call = f.block_call(b, &[Operand::Imm(7)])?;
828 /// assert_eq!(f.args(call), [Operand::Imm(7)]);
829 /// # Ok::<(), backend_lang::mir::MirError>(())
830 /// ```
831 #[inline]
832 #[must_use]
833 pub fn args(&self, call: BlockCall) -> &[Operand] {
834 self.args.get(call.range()).unwrap_or(&[])
835 }
836
837 /// Appends an instruction to `block`.
838 ///
839 /// The operands are checked against the opcode's description at once:
840 /// their count, each one's shape and class, immediate ranges, branch
841 /// argument counts against the target block's parameters (so a block's
842 /// parameters must be added before branches to it), and the target's
843 /// memory-operand limit.
844 ///
845 /// # Errors
846 ///
847 /// A [`MirError`] naming the problem; nothing is appended then.
848 ///
849 /// # Examples
850 ///
851 /// ```
852 /// use backend_lang::mir::{Function, MirError, Operand};
853 /// use backend_lang::x86_64::{op, GPR, SYSV};
854 ///
855 /// let mut f = Function::new("f", &SYSV);
856 /// let b = f.block()?;
857 /// let (a, c) = (f.vreg(GPR)?, f.vreg(GPR)?);
858 /// f.push(b, op::MOV64RI, &[a.into(), Operand::Imm(40)])?;
859 /// f.push(b, op::ADD64, &[c.into(), a.into(), Operand::Imm(2)])?;
860 /// // add64 takes a 32-bit immediate at most.
861 /// let err = f.push(b, op::ADD64, &[c.into(), a.into(), Operand::Imm(1 << 40)]).unwrap_err();
862 /// assert!(matches!(err, MirError::ImmediateRange { .. }));
863 /// # Ok::<(), MirError>(())
864 /// ```
865 pub fn push(
866 &mut self,
867 block: Block,
868 opcode: Opcode,
869 operands: &[Operand],
870 ) -> Result<Inst, MirError> {
871 self.push_with(block, opcode, operands, Effects::new())
872 }
873
874 /// Appends an instruction with extra implicit operands (see
875 /// [`Effects`]).
876 ///
877 /// # Errors
878 ///
879 /// As for [`Function::push`], plus [`MirError::UnknownPReg`] for an
880 /// implicit register the target does not have.
881 ///
882 /// # Examples
883 ///
884 /// ```
885 /// use backend_lang::mir::{Effects, Function, Operand};
886 /// use backend_lang::x86_64::{op, SYSV, RAX, RDI};
887 ///
888 /// let mut f = Function::new("f", &SYSV);
889 /// let b = f.block()?;
890 /// f.push(b, op::MOV64RI, &[RAX.into(), Operand::Imm(60)])?;
891 /// f.push_with(b, op::SYSCALL, &[], Effects::new().uses(&[RDI]))?;
892 /// f.push(b, op::UD2, &[])?;
893 /// assert!(f.to_string().contains("syscall implicit(rdi)"));
894 /// # Ok::<(), backend_lang::mir::MirError>(())
895 /// ```
896 pub fn push_with(
897 &mut self,
898 block: Block,
899 opcode: Opcode,
900 operands: &[Operand],
901 effects: Effects<'_>,
902 ) -> Result<Inst, MirError> {
903 if block.index() >= self.blocks.len() {
904 return Err(MirError::UnknownBlock(block));
905 }
906 let inst = Inst::new(next_id(self.insts.len())?);
907 self.check_inst(inst, opcode, operands)?;
908 for &r in effects.uses.iter().chain(effects.defs) {
909 if !self.target().has_reg(r) {
910 return Err(MirError::UnknownPReg(r));
911 }
912 }
913 let ops = next_id(self.operands.len())?;
914 room(self.operands.len().saturating_add(operands.len()))?;
915 let imp = next_id(self.implicits.len())?;
916 let nimp = effects.uses.len() + effects.defs.len();
917 room(self.implicits.len().saturating_add(nimp))?;
918 let clobber = if effects.clobbers.is_empty() {
919 NO_CLOBBERS
920 } else {
921 let id = next_id(self.clobbers.len())?;
922 self.clobbers.push(effects.clobbers);
923 id
924 };
925 self.operands.extend_from_slice(operands);
926 self.implicits
927 .extend(effects.uses.iter().map(|®| Implicit {
928 reg,
929 kind: ImplicitKind::Use,
930 }));
931 self.implicits
932 .extend(effects.defs.iter().map(|®| Implicit {
933 reg,
934 kind: ImplicitKind::Def,
935 }));
936 self.insts.push(InstData {
937 opcode,
938 block,
939 ops,
940 nops: operands.len() as u32,
941 imp,
942 nimp: nimp as u32,
943 clobber,
944 });
945 if let Some(b) = self.blocks.get_mut(block.index()) {
946 b.insts.push(inst);
947 }
948 Ok(inst)
949 }
950
951 /// The instructions of `block`, in order (empty for a block the function
952 /// does not have).
953 ///
954 /// # Examples
955 ///
956 /// ```
957 /// use backend_lang::mir::Function;
958 /// use backend_lang::x86_64::{op, SYSV};
959 ///
960 /// let mut f = Function::new("f", &SYSV);
961 /// let b = f.block()?;
962 /// let r = f.push(b, op::RET, &[])?;
963 /// assert_eq!(f.insts(b), [r]);
964 /// # Ok::<(), backend_lang::mir::MirError>(())
965 /// ```
966 #[inline]
967 #[must_use]
968 pub fn insts(&self, block: Block) -> &[Inst] {
969 self.blocks
970 .get(block.index())
971 .map_or(&[], |b| b.insts.as_slice())
972 }
973
974 /// The number of instructions in the function.
975 ///
976 /// # Examples
977 ///
978 /// ```
979 /// use backend_lang::mir::Function;
980 /// use backend_lang::x86_64::SYSV;
981 ///
982 /// assert_eq!(Function::new("f", &SYSV).inst_count(), 0);
983 /// ```
984 #[inline]
985 #[must_use]
986 pub fn inst_count(&self) -> usize {
987 self.insts.len()
988 }
989
990 /// An instruction's opcode, or `None` for one the function does not have.
991 ///
992 /// # Examples
993 ///
994 /// ```
995 /// use backend_lang::mir::Function;
996 /// use backend_lang::x86_64::{op, SYSV};
997 ///
998 /// let mut f = Function::new("f", &SYSV);
999 /// let b = f.block()?;
1000 /// let r = f.push(b, op::RET, &[])?;
1001 /// assert_eq!(f.opcode(r), Some(op::RET));
1002 /// # Ok::<(), backend_lang::mir::MirError>(())
1003 /// ```
1004 #[inline]
1005 #[must_use]
1006 pub fn opcode(&self, inst: Inst) -> Option<Opcode> {
1007 self.insts.get(inst.index()).map(|d| d.opcode)
1008 }
1009
1010 /// The block an instruction is in.
1011 ///
1012 /// # Examples
1013 ///
1014 /// ```
1015 /// use backend_lang::mir::Function;
1016 /// use backend_lang::x86_64::{op, SYSV};
1017 ///
1018 /// let mut f = Function::new("f", &SYSV);
1019 /// let b = f.block()?;
1020 /// let r = f.push(b, op::RET, &[])?;
1021 /// assert_eq!(f.inst_block(r), Some(b));
1022 /// # Ok::<(), backend_lang::mir::MirError>(())
1023 /// ```
1024 #[inline]
1025 #[must_use]
1026 pub fn inst_block(&self, inst: Inst) -> Option<Block> {
1027 self.insts.get(inst.index()).map(|d| d.block)
1028 }
1029
1030 /// An instruction's explicit operands (empty for one the function does
1031 /// not have).
1032 ///
1033 /// # Examples
1034 ///
1035 /// ```
1036 /// use backend_lang::mir::{Function, Operand};
1037 /// use backend_lang::x86_64::{op, SYSV, RAX};
1038 ///
1039 /// let mut f = Function::new("f", &SYSV);
1040 /// let b = f.block()?;
1041 /// let i = f.push(b, op::MOV64RI, &[RAX.into(), Operand::Imm(5)])?;
1042 /// assert_eq!(f.operands(i), [Operand::from(RAX), Operand::Imm(5)]);
1043 /// # Ok::<(), backend_lang::mir::MirError>(())
1044 /// ```
1045 #[inline]
1046 #[must_use]
1047 pub fn operands(&self, inst: Inst) -> &[Operand] {
1048 self.insts
1049 .get(inst.index())
1050 .and_then(|d| {
1051 self.operands
1052 .get(d.ops as usize..d.ops as usize + d.nops as usize)
1053 })
1054 .unwrap_or(&[])
1055 }
1056
1057 /// An instruction's extra implicit operands, uses first (empty for one
1058 /// the function does not have). The opcode's own implicit operands are in
1059 /// its [`InstDesc`](crate::target::InstDesc).
1060 ///
1061 /// # Examples
1062 ///
1063 /// ```
1064 /// use backend_lang::mir::{Effects, Function};
1065 /// use backend_lang::x86_64::{op, SYSV, RAX};
1066 ///
1067 /// let mut f = Function::new("f", &SYSV);
1068 /// let b = f.block()?;
1069 /// let r = f.push_with(b, op::RET, &[], Effects::new().uses(&[RAX]))?;
1070 /// assert_eq!(f.implicit(r).len(), 1);
1071 /// # Ok::<(), backend_lang::mir::MirError>(())
1072 /// ```
1073 #[inline]
1074 #[must_use]
1075 pub fn implicit(&self, inst: Inst) -> &[Implicit] {
1076 self.insts
1077 .get(inst.index())
1078 .and_then(|d| {
1079 self.implicits
1080 .get(d.imp as usize..d.imp as usize + d.nimp as usize)
1081 })
1082 .unwrap_or(&[])
1083 }
1084
1085 /// An instruction's extra clobbers (empty for one the function does not
1086 /// have).
1087 ///
1088 /// # Examples
1089 ///
1090 /// ```
1091 /// use backend_lang::mir::{Effects, Function};
1092 /// use backend_lang::x86_64::{op, SYSV};
1093 ///
1094 /// let mut f = Function::new("f", &SYSV);
1095 /// let b = f.block()?;
1096 /// let callee = f.symbol("g")?;
1097 /// let c = f.push_with(b, op::CALL, &[callee.into()], Effects::new().clobbers(SYSV.call_clobbers()))?;
1098 /// assert_eq!(f.clobbers(c), SYSV.call_clobbers());
1099 /// # Ok::<(), backend_lang::mir::MirError>(())
1100 /// ```
1101 #[inline]
1102 #[must_use]
1103 pub fn clobbers(&self, inst: Inst) -> RegSet {
1104 self.insts
1105 .get(inst.index())
1106 .and_then(|d| self.clobbers.get(d.clobber as usize))
1107 .copied()
1108 .unwrap_or(RegSet::EMPTY)
1109 }
1110
1111 /// Reserves `bytes` of outgoing argument area at the bottom of the frame
1112 /// (the largest over all calls; see
1113 /// [`Abi::assign_args`](crate::target::abi::Abi::assign_args)). Stack
1114 /// arguments are stored to `[sp + offset]` before a call. Calling it
1115 /// again keeps the larger value.
1116 ///
1117 /// # Examples
1118 ///
1119 /// ```
1120 /// use backend_lang::mir::Function;
1121 /// use backend_lang::x86_64::SYSV;
1122 ///
1123 /// let mut f = Function::new("f", &SYSV);
1124 /// f.reserve_outgoing(24);
1125 /// f.reserve_outgoing(8);
1126 /// assert_eq!(f.outgoing(), 24);
1127 /// ```
1128 pub fn reserve_outgoing(&mut self, bytes: u32) {
1129 self.outgoing = self.outgoing.max(bytes);
1130 }
1131
1132 /// The outgoing argument area reserved.
1133 ///
1134 /// # Examples
1135 ///
1136 /// ```
1137 /// use backend_lang::mir::Function;
1138 /// use backend_lang::x86_64::SYSV;
1139 ///
1140 /// assert_eq!(Function::new("f", &SYSV).outgoing(), 0);
1141 /// ```
1142 #[inline]
1143 #[must_use]
1144 pub fn outgoing(&self) -> u32 {
1145 self.outgoing
1146 }
1147
1148 /// Lays the frame out without a frame pointer, which frees the frame
1149 /// pointer register for the body (it is then saved like any other
1150 /// callee-saved register it writes). The frame pointer is kept by
1151 /// default.
1152 ///
1153 /// # Examples
1154 ///
1155 /// ```
1156 /// use backend_lang::mir::Function;
1157 /// use backend_lang::x86_64::SYSV;
1158 ///
1159 /// let mut f = Function::new("f", &SYSV);
1160 /// f.omit_frame_pointer();
1161 /// assert!(!f.frame_pointer());
1162 /// assert!(f.frame_layout().unwrap().prologue().is_empty());
1163 /// ```
1164 pub fn omit_frame_pointer(&mut self) {
1165 self.frame_pointer = false;
1166 }
1167
1168 /// Whether the frame keeps a frame pointer.
1169 ///
1170 /// # Examples
1171 ///
1172 /// ```
1173 /// use backend_lang::mir::Function;
1174 /// use backend_lang::x86_64::SYSV;
1175 ///
1176 /// assert!(Function::new("f", &SYSV).frame_pointer());
1177 /// ```
1178 #[inline]
1179 #[must_use]
1180 pub fn frame_pointer(&self) -> bool {
1181 self.frame_pointer
1182 }
1183
1184 /// The registers reserved for the frame, which the body may read but not
1185 /// write: the stack pointer, and the frame pointer when it is kept.
1186 ///
1187 /// # Examples
1188 ///
1189 /// ```
1190 /// use backend_lang::mir::Function;
1191 /// use backend_lang::x86_64::{SYSV, RBP, RSP};
1192 ///
1193 /// let f = Function::new("f", &SYSV);
1194 /// assert!(f.reserved().contains(RSP) && f.reserved().contains(RBP));
1195 /// ```
1196 #[must_use]
1197 pub fn reserved(&self) -> RegSet {
1198 let t = self.target();
1199 let set = RegSet::of(&[t.stack_pointer()]);
1200 if self.frame_pointer {
1201 set.with(t.frame_pointer())
1202 } else {
1203 set
1204 }
1205 }
1206
1207 /// Whether any instruction is a call.
1208 ///
1209 /// # Examples
1210 ///
1211 /// ```
1212 /// use backend_lang::mir::Function;
1213 /// use backend_lang::x86_64::SYSV;
1214 ///
1215 /// assert!(!Function::new("f", &SYSV).has_calls());
1216 /// ```
1217 #[must_use]
1218 pub fn has_calls(&self) -> bool {
1219 let t = self.target();
1220 self.insts.iter().any(|d| {
1221 t.inst(d.opcode)
1222 .is_some_and(|desc| desc.kind() == InstKind::Call)
1223 })
1224 }
1225
1226 /// Every physical register the function's instructions may write:
1227 /// explicit and implicit definitions, clobbers, and physical block
1228 /// parameters (written by the moves on the edges into them). The
1229 /// callee-saved registers among them are what the prologue saves.
1230 ///
1231 /// # Examples
1232 ///
1233 /// ```
1234 /// use backend_lang::mir::{Function, Operand};
1235 /// use backend_lang::x86_64::{op, SYSV, RBX, RDX, RAX, FLAGS};
1236 ///
1237 /// let mut f = Function::new("f", &SYSV);
1238 /// let b = f.block()?;
1239 /// f.push(b, op::MOV64RI, &[RBX.into(), Operand::Imm(1)])?;
1240 /// f.push(b, op::CQO, &[])?;
1241 /// let w = f.written_regs();
1242 /// assert!(w.contains(RBX) && w.contains(RDX));
1243 /// assert!(!w.contains(RAX));
1244 /// # Ok::<(), backend_lang::mir::MirError>(())
1245 /// ```
1246 #[must_use]
1247 pub fn written_regs(&self) -> RegSet {
1248 let t = self.target();
1249 let mut set = RegSet::EMPTY;
1250 for (i, d) in self.insts.iter().enumerate() {
1251 let inst = Inst::from_index(i);
1252 let Some(desc) = t.inst(d.opcode) else {
1253 continue;
1254 };
1255 for p in desc.implicit_defs() {
1256 set = set.with(*p);
1257 }
1258 set = set.union(desc.clobbers()).union(self.clobbers(inst));
1259 for imp in self.implicit(inst) {
1260 if imp.kind == ImplicitKind::Def {
1261 set = set.with(imp.reg);
1262 }
1263 }
1264 let ops = self.operands(inst);
1265 let defs = match desc.kind() {
1266 InstKind::Copy => ops.len().min(1),
1267 InstKind::ParallelCopy => ops.len() / 2,
1268 _ => desc
1269 .operands()
1270 .iter()
1271 .take_while(|r| matches!(r, OperandRule::Def(_)))
1272 .count(),
1273 };
1274 for op in ops.iter().take(defs) {
1275 if let Some(p) = op.reg().and_then(Reg::as_phys) {
1276 set = set.with(p);
1277 }
1278 }
1279 }
1280 for b in &self.blocks {
1281 for p in &b.params {
1282 if let Some(r) = p.reg().and_then(Reg::as_phys) {
1283 set = set.with(r);
1284 }
1285 }
1286 }
1287 set
1288 }
1289
1290 /// Lays out the function's frame under its calling convention.
1291 ///
1292 /// # Errors
1293 ///
1294 /// [`FrameError`] for a slot alignment the frame cannot provide,
1295 /// overlapping incoming slots, or a frame beyond 32-bit offsets.
1296 ///
1297 /// # Examples
1298 ///
1299 /// ```
1300 /// use backend_lang::mir::{Function, SlotKind};
1301 /// use backend_lang::x86_64::WIN64;
1302 ///
1303 /// let mut f = Function::new("f", &WIN64);
1304 /// let s = f.stack_slot(SlotKind::Local { size: 8, align: 8 })?;
1305 /// let frame = f.frame_layout().unwrap();
1306 /// // Win64 has no red zone; after the rbp push the stack pointer is
1307 /// // 16-aligned, so 8 bytes of locals round up to 16.
1308 /// assert_eq!(frame.alloc(), 16);
1309 /// assert_eq!(frame.slot_offset(s), Some(0));
1310 /// # Ok::<(), backend_lang::mir::MirError>(())
1311 /// ```
1312 pub fn frame_layout(&self) -> Result<FrameLayout, FrameError> {
1313 self.abi.layout_frame(&FrameInput {
1314 slots: &self.slots,
1315 written: self.written_regs(),
1316 has_calls: self.has_calls(),
1317 outgoing: self.outgoing,
1318 frame_pointer: self.frame_pointer,
1319 })
1320 }
1321
1322 pub(crate) fn check_reg(&self, reg: Reg) -> Result<(), MirError> {
1323 match (reg.as_phys(), reg.as_virt()) {
1324 (Some(p), _) if !self.target().has_reg(p) => Err(MirError::UnknownPReg(p)),
1325 (_, Some(v)) if v.index() >= self.vregs.len() => Err(MirError::UnknownVReg(v)),
1326 _ => Ok(()),
1327 }
1328 }
1329
1330 pub(crate) fn check_slot(&self, slot: StackSlot) -> Result<(), MirError> {
1331 if slot.index() < self.slots.len() {
1332 Ok(())
1333 } else {
1334 Err(MirError::UnknownSlot(slot))
1335 }
1336 }
1337}