backend_lang/mir/
verify.rs

1//! Checking instructions against their descriptions, and whole functions for
2//! structure: terminators, branch arities, single definitions.
3
4use alloc::vec;
5use alloc::vec::Vec;
6use core::fmt;
7
8use super::entity::{Block, Inst, StackSlot, Symbol};
9use super::function::Function;
10use super::operand::{BlockCall, Operand};
11use crate::regs::{PReg, Reg, RegClass, VReg};
12use crate::target::{InstKind, Opcode, OperandRule};
13
14/// Why an instruction or function is malformed.
15///
16/// Every variant names where the problem is: the instruction (and operand
17/// index), the block, or the entity that does not exist.
18///
19/// # Examples
20///
21/// ```
22/// use backend_lang::mir::{Function, MirError, Operand};
23/// use backend_lang::x86_64::{op, SYSV, XMM0};
24///
25/// let mut f = Function::new("f", &SYSV);
26/// let b = f.block()?;
27/// // A vector register where add64 wants a general-purpose one.
28/// let err = f.push(b, op::ADD64, &[XMM0.into(), XMM0.into(), Operand::Imm(1)]).unwrap_err();
29/// assert!(matches!(err, MirError::RegClass { index: 0, .. }));
30/// assert_eq!(err.to_string(), "inst0: operand 0 is a register of the wrong class");
31/// # Ok::<(), MirError>(())
32/// ```
33#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
34#[non_exhaustive]
35pub enum MirError {
36    /// The target has no such opcode.
37    UnknownOpcode {
38        /// The instruction.
39        inst: Inst,
40        /// The opcode.
41        opcode: Opcode,
42    },
43    /// The instruction has the wrong number of explicit operands. (For
44    /// `pcopy`, an odd number.)
45    OperandCount {
46        /// The instruction.
47        inst: Inst,
48        /// How many the opcode takes.
49        expected: usize,
50        /// How many were given.
51        found: usize,
52    },
53    /// An operand has a shape its position does not take (a memory operand
54    /// where only a register fits, a slot with an offset in a copy, an
55    /// unknown condition code, ...). The opcode's
56    /// [`OperandRule`](crate::target::OperandRule)s list what fits.
57    OperandShape {
58        /// The instruction.
59        inst: Inst,
60        /// The operand's position.
61        index: usize,
62    },
63    /// A register operand is of the wrong class (or, for a tied use or a
64    /// copy, not of its partner's class).
65    RegClass {
66        /// The instruction.
67        inst: Inst,
68        /// The operand's position.
69        index: usize,
70    },
71    /// An immediate is outside the range its position takes. Load wider
72    /// constants into a register first (`mov64ri`).
73    ImmediateRange {
74        /// The instruction.
75        inst: Inst,
76        /// The operand's position.
77        index: usize,
78        /// The immediate.
79        value: i64,
80    },
81    /// The instruction has more memory operands than the target allows in
82    /// one instruction (one, on x86-64).
83    TooManyMemOperands {
84        /// The instruction.
85        inst: Inst,
86    },
87    /// A branch passes a different number of arguments than its target block
88    /// has parameters. (Add a block's parameters before branches to it.)
89    ArgCount {
90        /// The branch.
91        inst: Inst,
92        /// The target block.
93        block: Block,
94        /// The block's parameter count.
95        expected: usize,
96        /// The arguments given.
97        found: usize,
98    },
99    /// A branch argument's class differs from its parameter's.
100    ArgClass {
101        /// The branch.
102        inst: Inst,
103        /// The target block.
104        block: Block,
105        /// The argument's position.
106        index: usize,
107    },
108    /// A parallel copy writes the same register or slot twice.
109    DuplicateDestination {
110        /// The copy.
111        inst: Inst,
112    },
113    /// A block parameter that is not a register or a whole stack slot.
114    BadParam {
115        /// The block.
116        block: Block,
117    },
118    /// A branch argument that is not a register, a whole stack slot, or an
119    /// immediate.
120    BadArg {
121        /// The target block.
122        block: Block,
123    },
124    /// A virtual register the function does not have.
125    UnknownVReg(VReg),
126    /// A physical register the target does not have.
127    UnknownPReg(PReg),
128    /// A stack slot the function does not have.
129    UnknownSlot(StackSlot),
130    /// A block the function does not have, or a branch target this function
131    /// did not make.
132    UnknownBlock(Block),
133    /// A symbol the function does not have.
134    UnknownSymbol(Symbol),
135    /// A register class the target does not have.
136    UnknownClass(RegClass),
137    /// A virtual register is defined more than once (by instructions or as a
138    /// block parameter). Before register allocation MIR is in SSA form.
139    MultipleDefs {
140        /// The register.
141        vreg: VReg,
142    },
143    /// A block does not end with a terminator (jump, branch, return, trap),
144    /// or is empty.
145    MissingTerminator {
146        /// The block.
147        block: Block,
148    },
149    /// A terminator is followed by more instructions in its block.
150    MisplacedTerminator {
151        /// The terminator.
152        inst: Inst,
153    },
154    /// The function has no blocks.
155    NoBlocks,
156    /// A call-site record (stack map or landing pad) names an instruction
157    /// that is not a call.
158    NotACall {
159        /// The instruction.
160        inst: Inst,
161    },
162    /// A virtual register is used but never defined
163    /// ([`Function::verify_ssa`]).
164    UndefinedVReg {
165        /// The register.
166        vreg: VReg,
167    },
168    /// A use of a virtual register in a block reachable from the entry is not
169    /// dominated by its definition ([`Function::verify_ssa`]).
170    NotDominated {
171        /// The register.
172        vreg: VReg,
173        /// The instruction that uses it.
174        inst: Inst,
175    },
176    /// A table of the function (instructions, operands, blocks, ...) would
177    /// exceed its 32-bit ids, or virtual registers would exceed
178    /// [`VReg::MAX`].
179    Limit,
180}
181
182impl fmt::Display for MirError {
183    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
184        match self {
185            MirError::UnknownOpcode { inst, opcode } => {
186                write!(f, "{inst}: opcode {} is not in the target", opcode.index())
187            }
188            MirError::OperandCount {
189                inst,
190                expected,
191                found,
192            } => write!(f, "{inst}: takes {expected} operands, {found} given"),
193            MirError::OperandShape { inst, index } => {
194                write!(
195                    f,
196                    "{inst}: operand {index} has a shape this position does not take"
197                )
198            }
199            MirError::RegClass { inst, index } => {
200                write!(
201                    f,
202                    "{inst}: operand {index} is a register of the wrong class"
203                )
204            }
205            MirError::ImmediateRange { inst, index, value } => write!(
206                f,
207                "{inst}: immediate {value} in operand {index} is out of range; load it into a register"
208            ),
209            MirError::TooManyMemOperands { inst } => {
210                write!(f, "{inst}: too many memory operands for one instruction")
211            }
212            MirError::ArgCount {
213                inst,
214                block,
215                expected,
216                found,
217            } => write!(
218                f,
219                "{inst}: {block} has {expected} parameters but {found} arguments are passed"
220            ),
221            MirError::ArgClass { inst, block, index } => write!(
222                f,
223                "{inst}: argument {index} to {block} is not of its parameter's class"
224            ),
225            MirError::DuplicateDestination { inst } => {
226                write!(f, "{inst}: a parallel copy writes one destination twice")
227            }
228            MirError::BadParam { block } => write!(
229                f,
230                "{block}: a parameter must be a register or a whole stack slot"
231            ),
232            MirError::BadArg { block } => write!(
233                f,
234                "an argument to {block} must be a register, a whole stack slot, or an immediate"
235            ),
236            MirError::UnknownVReg(v) => write!(f, "virtual register {v:?} does not exist"),
237            MirError::UnknownPReg(p) => {
238                write!(f, "physical register {} is not in the target", p.index())
239            }
240            MirError::UnknownSlot(s) => write!(f, "stack slot {s} does not exist"),
241            MirError::UnknownBlock(b) => write!(f, "{b} does not exist"),
242            MirError::UnknownSymbol(s) => write!(f, "symbol {s} does not exist"),
243            MirError::UnknownClass(c) => {
244                write!(f, "register class {} is not in the target", c.index())
245            }
246            MirError::MultipleDefs { vreg } => {
247                write!(f, "{vreg:?} is defined more than once")
248            }
249            MirError::MissingTerminator { block } => {
250                write!(
251                    f,
252                    "{block} does not end with a jump, branch, return, or trap"
253                )
254            }
255            MirError::MisplacedTerminator { inst } => {
256                write!(
257                    f,
258                    "{inst}: a terminator must be the last instruction of its block"
259                )
260            }
261            MirError::NoBlocks => f.write_str("the function has no blocks"),
262            MirError::NotACall { inst } => {
263                write!(
264                    f,
265                    "{inst}: a call-site record names an instruction that is not a call"
266                )
267            }
268            MirError::UndefinedVReg { vreg } => {
269                write!(f, "{vreg:?} is used but never defined")
270            }
271            MirError::NotDominated { vreg, inst } => write!(
272                f,
273                "{inst}: the use of {vreg:?} is not dominated by its definition"
274            ),
275            MirError::Limit => f.write_str("the function exceeds its 32-bit tables"),
276        }
277    }
278}
279
280impl core::error::Error for MirError {}
281
282/// A location key for duplicate detection: registers and slots in disjoint
283/// ranges of `u64`.
284fn loc_key(op: &Operand) -> Option<u64> {
285    match op {
286        Operand::Reg(r) => Some(match (r.as_phys(), r.as_virt()) {
287            (Some(p), _) => p.index() as u64,
288            (_, Some(v)) => (1 << 32) | v.index() as u64,
289            _ => return None,
290        }),
291        Operand::Slot { slot, .. } => Some((2 << 32) | slot.index() as u64),
292        _ => None,
293    }
294}
295
296impl Function {
297    /// Checks one instruction's operands against its opcode's description.
298    pub(crate) fn check_inst(
299        &self,
300        inst: Inst,
301        opcode: Opcode,
302        operands: &[Operand],
303    ) -> Result<(), MirError> {
304        let target = self.target();
305        let desc = target
306            .inst(opcode)
307            .ok_or(MirError::UnknownOpcode { inst, opcode })?;
308        match desc.kind() {
309            InstKind::Copy => {
310                if operands.len() != 2 {
311                    return Err(MirError::OperandCount {
312                        inst,
313                        expected: 2,
314                        found: operands.len(),
315                    });
316                }
317                self.check_copy_pair(inst, operands, 0, 1)
318            }
319            InstKind::ParallelCopy => {
320                if operands.len() % 2 != 0 {
321                    return Err(MirError::OperandCount {
322                        inst,
323                        expected: operands.len() + 1,
324                        found: operands.len(),
325                    });
326                }
327                let n = operands.len() / 2;
328                for i in 0..n {
329                    self.check_copy_pair(inst, operands, i, n + i)?;
330                }
331                let mut keys: Vec<u64> = operands[..n].iter().filter_map(loc_key).collect();
332                keys.sort_unstable();
333                if keys.windows(2).any(|w| w[0] == w[1]) {
334                    return Err(MirError::DuplicateDestination { inst });
335                }
336                Ok(())
337            }
338            InstKind::Switch => {
339                // The fixed operands, then one argument-less target per index.
340                let rules = desc.operands();
341                if operands.len() <= rules.len() {
342                    return Err(MirError::OperandCount {
343                        inst,
344                        expected: rules.len() + 1,
345                        found: operands.len(),
346                    });
347                }
348                let mut mems = 0usize;
349                for (index, (rule, op)) in rules.iter().zip(operands).enumerate() {
350                    self.check_operand(inst, index, *rule, op, rules, &mut mems)?;
351                }
352                for (index, op) in operands.iter().enumerate().skip(rules.len()) {
353                    match op {
354                        Operand::Block(call) => {
355                            self.check_block_call(inst, call)?;
356                            if !call.is_empty() {
357                                return Err(MirError::ArgCount {
358                                    inst,
359                                    block: call.block(),
360                                    expected: 0,
361                                    found: call.len(),
362                                });
363                            }
364                        }
365                        _ => return Err(MirError::OperandShape { inst, index }),
366                    }
367                }
368                Ok(())
369            }
370            _ => {
371                let rules = desc.operands();
372                if rules.len() != operands.len() {
373                    return Err(MirError::OperandCount {
374                        inst,
375                        expected: rules.len(),
376                        found: operands.len(),
377                    });
378                }
379                let mut mems = 0usize;
380                for (index, (rule, op)) in rules.iter().zip(operands).enumerate() {
381                    self.check_operand(inst, index, *rule, op, rules, &mut mems)?;
382                }
383                if mems > usize::from(target.max_mem_operands()) {
384                    return Err(MirError::TooManyMemOperands { inst });
385                }
386                Ok(())
387            }
388        }
389    }
390
391    /// A copy's destination (register or whole slot) and source (register,
392    /// whole slot, or immediate); registers on both sides share a class.
393    fn check_copy_pair(
394        &self,
395        inst: Inst,
396        ops: &[Operand],
397        dst: usize,
398        src: usize,
399    ) -> Result<(), MirError> {
400        let shape = |index| MirError::OperandShape { inst, index };
401        let (d, s) = (ops[dst], ops[src]);
402        match d {
403            Operand::Reg(r) => self.check_reg(r)?,
404            Operand::Slot { slot, offset: 0 } => self.check_slot(slot)?,
405            _ => return Err(shape(dst)),
406        }
407        match s {
408            Operand::Reg(r) => self.check_reg(r)?,
409            Operand::Slot { slot, offset: 0 } => self.check_slot(slot)?,
410            Operand::Imm(_) => {}
411            _ => return Err(shape(src)),
412        }
413        if let (Some(a), Some(b)) = (d.reg(), s.reg()) {
414            if self.reg_class(a) != self.reg_class(b) {
415                return Err(MirError::RegClass { inst, index: src });
416            }
417        }
418        Ok(())
419    }
420
421    fn reg_in(&self, inst: Inst, index: usize, reg: Reg, class: RegClass) -> Result<(), MirError> {
422        self.check_reg(reg)?;
423        if self.reg_class(reg) == Some(class) {
424            Ok(())
425        } else {
426            Err(MirError::RegClass { inst, index })
427        }
428    }
429
430    fn check_operand(
431        &self,
432        inst: Inst,
433        index: usize,
434        rule: OperandRule,
435        op: &Operand,
436        rules: &[OperandRule],
437        mems: &mut usize,
438    ) -> Result<(), MirError> {
439        let target = self.target();
440        let shape = MirError::OperandShape { inst, index };
441        match rule {
442            OperandRule::Def(class) => match op {
443                Operand::Reg(r) => self.reg_in(inst, index, *r, class),
444                _ => Err(shape),
445            },
446            OperandRule::Tied(def) => {
447                let class = match rules.get(usize::from(def)) {
448                    Some(OperandRule::Def(c)) => *c,
449                    _ => return Err(shape),
450                };
451                match op {
452                    Operand::Reg(r) => self.reg_in(inst, index, *r, class),
453                    _ => Err(shape),
454                }
455            }
456            OperandRule::Use(class, accept) => match *op {
457                Operand::Reg(r) if accept.reg() => self.reg_in(inst, index, r, class),
458                Operand::Imm(value) if accept.imm() != crate::target::ImmRange::None => {
459                    if accept.imm().fits(value) {
460                        Ok(())
461                    } else {
462                        Err(MirError::ImmediateRange { inst, index, value })
463                    }
464                }
465                Operand::Mem(m) if accept.mem() => {
466                    *mems += 1;
467                    for r in m.regs() {
468                        self.reg_in(inst, index, r, target.addr_class())?;
469                    }
470                    Ok(())
471                }
472                Operand::Slot { slot, .. } if accept.mem() => {
473                    *mems += 1;
474                    self.check_slot(slot)
475                }
476                Operand::Symbol(s) if accept.symbol() => {
477                    if s.index() < self.symbols.len() {
478                        Ok(())
479                    } else {
480                        Err(MirError::UnknownSymbol(s))
481                    }
482                }
483                _ => Err(shape),
484            },
485            OperandRule::Cond => match op {
486                Operand::Cond(c) if c.code() < target.conds() => Ok(()),
487                _ => Err(shape),
488            },
489            OperandRule::Block => match op {
490                Operand::Block(call) => self.check_block_call(inst, call),
491                _ => Err(shape),
492            },
493        }
494    }
495
496    fn check_block_call(&self, inst: Inst, call: &BlockCall) -> Result<(), MirError> {
497        let block = call.block();
498        let params = self
499            .blocks
500            .get(block.index())
501            .ok_or(MirError::UnknownBlock(block))?
502            .params
503            .as_slice();
504        // A call made by another function would index past this pool.
505        let args = self
506            .args
507            .get(call.range())
508            .ok_or(MirError::UnknownBlock(block))?;
509        if args.len() != params.len() {
510            return Err(MirError::ArgCount {
511                inst,
512                block,
513                expected: params.len(),
514                found: args.len(),
515            });
516        }
517        for (index, (a, p)) in args.iter().zip(params).enumerate() {
518            if let (Some(a), Some(p)) = (a.reg(), p.reg()) {
519                if self.reg_class(a) != self.reg_class(p) {
520                    return Err(MirError::ArgClass { inst, block, index });
521                }
522            }
523        }
524        Ok(())
525    }
526
527    /// Checks the whole function: every instruction against its opcode (again,
528    /// since block parameters may have been added after branches to them),
529    /// every block ends with exactly one terminator, and every virtual
530    /// register is defined at most once (MIR before register allocation is
531    /// SSA; block parameters count as definitions).
532    ///
533    /// Runs in time linear in the function's size. Dominance (every use
534    /// defined on every path to it) is the register allocator's
535    /// precondition and is checked with it (backend-lang 0.5).
536    ///
537    /// # Errors
538    ///
539    /// The first [`MirError`] found, in block order.
540    ///
541    /// # Examples
542    ///
543    /// ```
544    /// use backend_lang::mir::{Function, MirError, Operand};
545    /// use backend_lang::x86_64::{op, GPR, SYSV};
546    ///
547    /// let mut f = Function::new("f", &SYSV);
548    /// let b = f.block()?;
549    /// let v = f.vreg(GPR)?;
550    /// f.push(b, op::MOV64RI, &[v.into(), Operand::Imm(1)])?;
551    /// assert_eq!(f.verify(), Err(MirError::MissingTerminator { block: b }));
552    /// f.push(b, op::MOV64RI, &[v.into(), Operand::Imm(2)])?;
553    /// f.push(b, op::RET, &[])?;
554    /// assert_eq!(f.verify(), Err(MirError::MultipleDefs { vreg: v.as_virt().unwrap() }));
555    /// # Ok::<(), MirError>(())
556    /// ```
557    pub fn verify(&self) -> Result<(), MirError> {
558        if self.blocks.is_empty() {
559            return Err(MirError::NoBlocks);
560        }
561        let target = self.target();
562        let mut defined = vec![false; self.vregs.len()];
563        let mut define = |r: Option<Reg>| -> Result<(), MirError> {
564            if let Some(v) = r.and_then(Reg::as_virt) {
565                let seen = defined.get_mut(v.index()).ok_or(MirError::UnknownVReg(v))?;
566                if *seen {
567                    return Err(MirError::MultipleDefs { vreg: v });
568                }
569                *seen = true;
570            }
571            Ok(())
572        };
573        for (b, data) in self.blocks.iter().enumerate() {
574            let block = Block::from_index(b);
575            for p in &data.params {
576                define(p.reg())?;
577            }
578            let Some(&last) = data.insts.last() else {
579                return Err(MirError::MissingTerminator { block });
580            };
581            for &inst in data.insts.iter() {
582                let d = self.insts.get(inst.index()).ok_or(MirError::Limit)?;
583                let ops = self.operands(inst);
584                self.check_inst(inst, d.opcode, ops)?;
585                let desc = target.inst(d.opcode).ok_or(MirError::UnknownOpcode {
586                    inst,
587                    opcode: d.opcode,
588                })?;
589                let defs = match desc.kind() {
590                    InstKind::Copy => 1,
591                    InstKind::ParallelCopy => ops.len() / 2,
592                    _ => desc.defs(),
593                };
594                for op in ops.iter().take(defs) {
595                    define(op.reg())?;
596                }
597                let terminator = desc.kind().is_terminator();
598                if terminator && inst != last {
599                    return Err(MirError::MisplacedTerminator { inst });
600                }
601                if !terminator && inst == last {
602                    return Err(MirError::MissingTerminator { block });
603                }
604            }
605        }
606        Ok(())
607    }
608}
backend_lang/mir/verify.rs

backend_lang/mir/
verify.rs
