llvm_codegen/
isel.rs

1//! Machine IR types and instruction-selection backend trait.
2//!
3//! The machine IR (`MachineFunction`, `MInstr`, …) is target-independent.
4//! Target backends implement [`IselBackend`] to lower LLVM IR to machine IR.
5
6use llvm_ir::{Context, Function, Module};
7use std::collections::HashMap;
8
9// ── indices ────────────────────────────────────────────────────────────────
10
11/// Virtual register (unlimited supply, created during instruction selection).
12#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
13pub struct VReg(pub u32);
14
15/// Physical register (target-specific numbering).
16#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
17pub struct PReg(pub u8);
18
19/// Opaque machine opcode (each target provides its own constants).
20#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
21pub struct MOpcode(pub u32);
22
23/// Source-level debug location carried with machine instructions.
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub struct DebugLoc {
26    /// Public API for `line`.
27    pub line: u32,
28    /// Public API for `column`.
29    pub column: u32,
30}
31
32// ── machine operand ────────────────────────────────────────────────────────
33
34/// An operand in a machine instruction.
35#[derive(Clone, Debug, PartialEq, Eq)]
36pub enum MOperand {
37    /// Virtual register (pre-allocation).
38    VReg(VReg),
39    /// Physical register (post-allocation or ABI-fixed).
40    PReg(PReg),
41    /// Immediate integer constant.
42    Imm(i64),
43    /// Branch target: index into `MachineFunction::blocks`.
44    Block(usize),
45}
46
47// ── machine instruction ────────────────────────────────────────────────────
48
49/// A single machine instruction.
50#[derive(Clone, Debug)]
51pub struct MInstr {
52    /// Target-specific opcode.
53    pub opcode: MOpcode,
54    /// Output (destination) virtual register, if any.
55    pub dst: Option<VReg>,
56    /// Input operands (source registers, immediates, branch targets).
57    pub operands: Vec<MOperand>,
58    /// Physical registers that must hold specific values before this instruction
59    /// (e.g. argument registers at a call site).
60    pub phys_uses: Vec<PReg>,
61    /// Physical registers whose values are destroyed by this instruction
62    /// (e.g. caller-saved regs clobbered by a call).
63    pub clobbers: Vec<PReg>,
64    /// Source debug location associated with this machine instruction.
65    pub debug_loc: Option<DebugLoc>,
66}
67
68impl MInstr {
69    /// Public API for `new`.
70    pub fn new(opcode: MOpcode) -> Self {
71        // `Self` variant.
72        Self {
73            opcode,
74            // `dst` field.
75            dst: None,
76            // `operands` field.
77            operands: Vec::new(),
78            // `phys_uses` field.
79            phys_uses: Vec::new(),
80            // `clobbers` field.
81            clobbers: Vec::new(),
82            // `debug_loc` field.
83            debug_loc: None,
84        }
85    }
86
87    /// Public API for `with_dst`.
88    pub fn with_dst(mut self, dst: VReg) -> Self {
89        self.dst = Some(dst);
90        self
91    }
92    /// Public API for `with_vreg`.
93    pub fn with_vreg(mut self, r: VReg) -> Self {
94        self.operands.push(MOperand::VReg(r));
95        self
96    }
97    /// Public API for `with_preg`.
98    pub fn with_preg(mut self, r: PReg) -> Self {
99        self.operands.push(MOperand::PReg(r));
100        self
101    }
102    /// Public API for `with_imm`.
103    pub fn with_imm(mut self, imm: i64) -> Self {
104        self.operands.push(MOperand::Imm(imm));
105        self
106    }
107    /// Public API for `with_block`.
108    pub fn with_block(mut self, b: usize) -> Self {
109        self.operands.push(MOperand::Block(b));
110        self
111    }
112}
113
114// ── machine basic block ────────────────────────────────────────────────────
115
116/// A sequence of machine instructions corresponding to one IR basic block.
117#[derive(Clone, Debug, Default)]
118pub struct MachineBlock {
119    /// Label derived from the IR block name (or function name for entry).
120    pub label: String,
121    /// Instructions in emission order.
122    pub instrs: Vec<MInstr>,
123}
124
125// ── machine function ───────────────────────────────────────────────────────
126
127/// Machine-level representation of a function, ready for register allocation
128/// and code emission.
129#[derive(Clone, Debug)]
130pub struct MachineFunction {
131    /// Name of the function.
132    pub name: String,
133    /// Basic blocks in layout order (block 0 is the entry).
134    pub blocks: Vec<MachineBlock>,
135    /// Counter for allocating fresh virtual registers.
136    pub(crate) next_vreg: u32,
137    /// Physical registers available for allocation (set by the target).
138    pub allocatable_pregs: Vec<PReg>,
139    /// Callee-saved physical registers (set by the target).
140    pub callee_saved_pregs: Vec<PReg>,
141    /// Frame size in bytes (spill slots only; set by insert_spill_reloads).
142    pub frame_size: u32,
143    /// Map from spilled VReg → frame slot index (0-based; emitter converts to byte offset).
144    pub spill_slots: HashMap<VReg, u32>,
145    /// Callee-saved physical registers actually used by this function (populated by apply_allocation).
146    pub used_callee_saved: Vec<PReg>,
147    /// Counter for frame slot allocation.
148    next_slot: u32,
149    /// Source filename used for debug line tables.
150    pub debug_source: Option<String>,
151    /// First source line observed from IR `!dbg` metadata.
152    pub debug_line_start: Option<u32>,
153    /// Debug location automatically attached by [`MachineFunction::push`].
154    pub current_debug_loc: Option<DebugLoc>,
155}
156
157impl MachineFunction {
158    /// Public API for `new`.
159    pub fn new(name: String) -> Self {
160        Self {
161            name,
162            blocks: Vec::new(),
163            next_vreg: 0,
164            allocatable_pregs: Vec::new(),
165            callee_saved_pregs: Vec::new(),
166            frame_size: 0,
167            spill_slots: HashMap::new(),
168            used_callee_saved: Vec::new(),
169            next_slot: 0,
170            debug_source: None,
171            debug_line_start: None,
172            current_debug_loc: None,
173        }
174    }
175
176    /// Allocate a fresh virtual register.
177    pub fn fresh_vreg(&mut self) -> VReg {
178        let id = self.next_vreg;
179        self.next_vreg += 1;
180        VReg(id)
181    }
182
183    /// Allocate a fresh frame slot for a spilled VReg and return its index.
184    ///
185    /// Slot 0 is the first 8-byte slot below the frame pointer.  The emitter
186    /// converts a slot index `n` to a byte offset (e.g. x86: `-(n+1)*8` from
187    /// RBP; AArch64: `(n+2)*8` above the saved FP/LR pair).
188    pub fn alloc_spill_slot(&mut self, vreg: VReg) -> u32 {
189        if let Some(&existing) = self.spill_slots.get(&vreg) {
190            return existing;
191        }
192        let slot = self.next_slot;
193        self.next_slot += 1;
194        self.spill_slots.insert(vreg, slot);
195        // Update frame_size: each slot is 8 bytes.
196        self.frame_size = self.next_slot * 8;
197        slot
198    }
199
200    /// Append a new empty machine block and return its index.
201    pub fn add_block(&mut self, label: impl Into<String>) -> usize {
202        let idx = self.blocks.len();
203        self.blocks.push(MachineBlock {
204            label: label.into(),
205            instrs: Vec::new(),
206        });
207        idx
208    }
209
210    /// Append `instr` to block `block_idx`.
211    pub fn push(&mut self, block_idx: usize, mut instr: MInstr) {
212        if instr.debug_loc.is_none() {
213            instr.debug_loc = self.current_debug_loc;
214        }
215        self.blocks[block_idx].instrs.push(instr);
216    }
217}
218
219// ── IselBackend trait ──────────────────────────────────────────────────────
220
221/// Implemented by each target to lower LLVM IR functions to machine IR.
222pub trait IselBackend {
223    /// Lower a single IR function to a [`MachineFunction`].
224    fn lower_function(
225        &mut self,
226        ctx: &Context,
227        module: &Module,
228        func: &Function,
229    ) -> MachineFunction;
230}
231
232// ── tests ──────────────────────────────────────────────────────────────────
233
234#[cfg(test)]
235mod tests {
236    use super::*;
237
238    #[test]
239    fn machine_function_fresh_vreg() {
240        let mut mf = MachineFunction::new("f".into());
241        let v0 = mf.fresh_vreg();
242        let v1 = mf.fresh_vreg();
243        assert_eq!(v0, VReg(0));
244        assert_eq!(v1, VReg(1));
245    }
246
247    #[test]
248    fn machine_function_add_block() {
249        let mut mf = MachineFunction::new("f".into());
250        let b0 = mf.add_block("entry");
251        let b1 = mf.add_block("exit");
252        assert_eq!(b0, 0);
253        assert_eq!(b1, 1);
254        assert_eq!(mf.blocks[0].label, "entry");
255    }
256
257    #[test]
258    fn minstr_builder() {
259        let v = VReg(0);
260        let p = PReg(1);
261        let mi = MInstr::new(MOpcode(42))
262            .with_dst(v)
263            .with_vreg(v)
264            .with_preg(p)
265            .with_imm(-7)
266            .with_block(3);
267        assert_eq!(mi.dst, Some(v));
268        assert_eq!(mi.operands.len(), 4);
269        assert_eq!(mi.operands[0], MOperand::VReg(v));
270        assert_eq!(mi.operands[1], MOperand::PReg(p));
271        assert_eq!(mi.operands[2], MOperand::Imm(-7));
272        assert_eq!(mi.operands[3], MOperand::Block(3));
273    }
274}
llvm_codegen/isel.rs

llvm_codegen/
isel.rs
