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 table of the function (instructions, operands, blocks, ...) would
157    /// exceed its 32-bit ids, or virtual registers would exceed
158    /// [`VReg::MAX`].
159    Limit,
160}
161
162impl fmt::Display for MirError {
163    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
164        match self {
165            MirError::UnknownOpcode { inst, opcode } => {
166                write!(f, "{inst}: opcode {} is not in the target", opcode.index())
167            }
168            MirError::OperandCount {
169                inst,
170                expected,
171                found,
172            } => write!(f, "{inst}: takes {expected} operands, {found} given"),
173            MirError::OperandShape { inst, index } => {
174                write!(
175                    f,
176                    "{inst}: operand {index} has a shape this position does not take"
177                )
178            }
179            MirError::RegClass { inst, index } => {
180                write!(
181                    f,
182                    "{inst}: operand {index} is a register of the wrong class"
183                )
184            }
185            MirError::ImmediateRange { inst, index, value } => write!(
186                f,
187                "{inst}: immediate {value} in operand {index} is out of range; load it into a register"
188            ),
189            MirError::TooManyMemOperands { inst } => {
190                write!(f, "{inst}: too many memory operands for one instruction")
191            }
192            MirError::ArgCount {
193                inst,
194                block,
195                expected,
196                found,
197            } => write!(
198                f,
199                "{inst}: {block} has {expected} parameters but {found} arguments are passed"
200            ),
201            MirError::ArgClass { inst, block, index } => write!(
202                f,
203                "{inst}: argument {index} to {block} is not of its parameter's class"
204            ),
205            MirError::DuplicateDestination { inst } => {
206                write!(f, "{inst}: a parallel copy writes one destination twice")
207            }
208            MirError::BadParam { block } => write!(
209                f,
210                "{block}: a parameter must be a register or a whole stack slot"
211            ),
212            MirError::BadArg { block } => write!(
213                f,
214                "an argument to {block} must be a register, a whole stack slot, or an immediate"
215            ),
216            MirError::UnknownVReg(v) => write!(f, "virtual register {v:?} does not exist"),
217            MirError::UnknownPReg(p) => {
218                write!(f, "physical register {} is not in the target", p.index())
219            }
220            MirError::UnknownSlot(s) => write!(f, "stack slot {s} does not exist"),
221            MirError::UnknownBlock(b) => write!(f, "{b} does not exist"),
222            MirError::UnknownSymbol(s) => write!(f, "symbol {s} does not exist"),
223            MirError::UnknownClass(c) => {
224                write!(f, "register class {} is not in the target", c.index())
225            }
226            MirError::MultipleDefs { vreg } => {
227                write!(f, "{vreg:?} is defined more than once")
228            }
229            MirError::MissingTerminator { block } => {
230                write!(
231                    f,
232                    "{block} does not end with a jump, branch, return, or trap"
233                )
234            }
235            MirError::MisplacedTerminator { inst } => {
236                write!(
237                    f,
238                    "{inst}: a terminator must be the last instruction of its block"
239                )
240            }
241            MirError::NoBlocks => f.write_str("the function has no blocks"),
242            MirError::Limit => f.write_str("the function exceeds its 32-bit tables"),
243        }
244    }
245}
246
247impl core::error::Error for MirError {}
248
249/// A location key for duplicate detection: registers and slots in disjoint
250/// ranges of `u64`.
251fn loc_key(op: &Operand) -> Option<u64> {
252    match op {
253        Operand::Reg(r) => Some(match (r.as_phys(), r.as_virt()) {
254            (Some(p), _) => p.index() as u64,
255            (_, Some(v)) => (1 << 32) | v.index() as u64,
256            _ => return None,
257        }),
258        Operand::Slot { slot, .. } => Some((2 << 32) | slot.index() as u64),
259        _ => None,
260    }
261}
262
263impl Function {
264    /// Checks one instruction's operands against its opcode's description.
265    pub(crate) fn check_inst(
266        &self,
267        inst: Inst,
268        opcode: Opcode,
269        operands: &[Operand],
270    ) -> Result<(), MirError> {
271        let target = self.target();
272        let desc = target
273            .inst(opcode)
274            .ok_or(MirError::UnknownOpcode { inst, opcode })?;
275        match desc.kind() {
276            InstKind::Copy => {
277                if operands.len() != 2 {
278                    return Err(MirError::OperandCount {
279                        inst,
280                        expected: 2,
281                        found: operands.len(),
282                    });
283                }
284                self.check_copy_pair(inst, operands, 0, 1)
285            }
286            InstKind::ParallelCopy => {
287                if operands.len() % 2 != 0 {
288                    return Err(MirError::OperandCount {
289                        inst,
290                        expected: operands.len() + 1,
291                        found: operands.len(),
292                    });
293                }
294                let n = operands.len() / 2;
295                for i in 0..n {
296                    self.check_copy_pair(inst, operands, i, n + i)?;
297                }
298                let mut keys: Vec<u64> = operands[..n].iter().filter_map(loc_key).collect();
299                keys.sort_unstable();
300                if keys.windows(2).any(|w| w[0] == w[1]) {
301                    return Err(MirError::DuplicateDestination { inst });
302                }
303                Ok(())
304            }
305            _ => {
306                let rules = desc.operands();
307                if rules.len() != operands.len() {
308                    return Err(MirError::OperandCount {
309                        inst,
310                        expected: rules.len(),
311                        found: operands.len(),
312                    });
313                }
314                let mut mems = 0usize;
315                for (index, (rule, op)) in rules.iter().zip(operands).enumerate() {
316                    self.check_operand(inst, index, *rule, op, rules, &mut mems)?;
317                }
318                if mems > usize::from(target.max_mem_operands()) {
319                    return Err(MirError::TooManyMemOperands { inst });
320                }
321                Ok(())
322            }
323        }
324    }
325
326    /// A copy's destination (register or whole slot) and source (register,
327    /// whole slot, or immediate); registers on both sides share a class.
328    fn check_copy_pair(
329        &self,
330        inst: Inst,
331        ops: &[Operand],
332        dst: usize,
333        src: usize,
334    ) -> Result<(), MirError> {
335        let shape = |index| MirError::OperandShape { inst, index };
336        let (d, s) = (ops[dst], ops[src]);
337        match d {
338            Operand::Reg(r) => self.check_reg(r)?,
339            Operand::Slot { slot, offset: 0 } => self.check_slot(slot)?,
340            _ => return Err(shape(dst)),
341        }
342        match s {
343            Operand::Reg(r) => self.check_reg(r)?,
344            Operand::Slot { slot, offset: 0 } => self.check_slot(slot)?,
345            Operand::Imm(_) => {}
346            _ => return Err(shape(src)),
347        }
348        if let (Some(a), Some(b)) = (d.reg(), s.reg()) {
349            if self.reg_class(a) != self.reg_class(b) {
350                return Err(MirError::RegClass { inst, index: src });
351            }
352        }
353        Ok(())
354    }
355
356    fn reg_in(&self, inst: Inst, index: usize, reg: Reg, class: RegClass) -> Result<(), MirError> {
357        self.check_reg(reg)?;
358        if self.reg_class(reg) == Some(class) {
359            Ok(())
360        } else {
361            Err(MirError::RegClass { inst, index })
362        }
363    }
364
365    fn check_operand(
366        &self,
367        inst: Inst,
368        index: usize,
369        rule: OperandRule,
370        op: &Operand,
371        rules: &[OperandRule],
372        mems: &mut usize,
373    ) -> Result<(), MirError> {
374        let target = self.target();
375        let shape = MirError::OperandShape { inst, index };
376        match rule {
377            OperandRule::Def(class) => match op {
378                Operand::Reg(r) => self.reg_in(inst, index, *r, class),
379                _ => Err(shape),
380            },
381            OperandRule::Tied(def) => {
382                let class = match rules.get(usize::from(def)) {
383                    Some(OperandRule::Def(c)) => *c,
384                    _ => return Err(shape),
385                };
386                match op {
387                    Operand::Reg(r) => self.reg_in(inst, index, *r, class),
388                    _ => Err(shape),
389                }
390            }
391            OperandRule::Use(class, accept) => match *op {
392                Operand::Reg(r) if accept.reg() => self.reg_in(inst, index, r, class),
393                Operand::Imm(value) if accept.imm() != crate::target::ImmRange::None => {
394                    if accept.imm().fits(value) {
395                        Ok(())
396                    } else {
397                        Err(MirError::ImmediateRange { inst, index, value })
398                    }
399                }
400                Operand::Mem(m) if accept.mem() => {
401                    *mems += 1;
402                    for r in m.regs() {
403                        self.reg_in(inst, index, r, target.addr_class())?;
404                    }
405                    Ok(())
406                }
407                Operand::Slot { slot, .. } if accept.mem() => {
408                    *mems += 1;
409                    self.check_slot(slot)
410                }
411                Operand::Symbol(s) if accept.symbol() => {
412                    if s.index() < self.symbols.len() {
413                        Ok(())
414                    } else {
415                        Err(MirError::UnknownSymbol(s))
416                    }
417                }
418                _ => Err(shape),
419            },
420            OperandRule::Cond => match op {
421                Operand::Cond(c) if c.code() < target.conds() => Ok(()),
422                _ => Err(shape),
423            },
424            OperandRule::Block => match op {
425                Operand::Block(call) => self.check_block_call(inst, call),
426                _ => Err(shape),
427            },
428        }
429    }
430
431    fn check_block_call(&self, inst: Inst, call: &BlockCall) -> Result<(), MirError> {
432        let block = call.block();
433        let params = self
434            .blocks
435            .get(block.index())
436            .ok_or(MirError::UnknownBlock(block))?
437            .params
438            .as_slice();
439        // A call made by another function would index past this pool.
440        let args = self
441            .args
442            .get(call.range())
443            .ok_or(MirError::UnknownBlock(block))?;
444        if args.len() != params.len() {
445            return Err(MirError::ArgCount {
446                inst,
447                block,
448                expected: params.len(),
449                found: args.len(),
450            });
451        }
452        for (index, (a, p)) in args.iter().zip(params).enumerate() {
453            if let (Some(a), Some(p)) = (a.reg(), p.reg()) {
454                if self.reg_class(a) != self.reg_class(p) {
455                    return Err(MirError::ArgClass { inst, block, index });
456                }
457            }
458        }
459        Ok(())
460    }
461
462    /// Checks the whole function: every instruction against its opcode (again,
463    /// since block parameters may have been added after branches to them),
464    /// every block ends with exactly one terminator, and every virtual
465    /// register is defined at most once (MIR before register allocation is
466    /// SSA; block parameters count as definitions).
467    ///
468    /// Runs in time linear in the function's size. Dominance (every use
469    /// defined on every path to it) is the register allocator's
470    /// precondition and is checked with it (backend-lang 0.5).
471    ///
472    /// # Errors
473    ///
474    /// The first [`MirError`] found, in block order.
475    ///
476    /// # Examples
477    ///
478    /// ```
479    /// use backend_lang::mir::{Function, MirError, Operand};
480    /// use backend_lang::x86_64::{op, GPR, SYSV};
481    ///
482    /// let mut f = Function::new("f", &SYSV);
483    /// let b = f.block()?;
484    /// let v = f.vreg(GPR)?;
485    /// f.push(b, op::MOV64RI, &[v.into(), Operand::Imm(1)])?;
486    /// assert_eq!(f.verify(), Err(MirError::MissingTerminator { block: b }));
487    /// f.push(b, op::MOV64RI, &[v.into(), Operand::Imm(2)])?;
488    /// f.push(b, op::RET, &[])?;
489    /// assert_eq!(f.verify(), Err(MirError::MultipleDefs { vreg: v.as_virt().unwrap() }));
490    /// # Ok::<(), MirError>(())
491    /// ```
492    pub fn verify(&self) -> Result<(), MirError> {
493        if self.blocks.is_empty() {
494            return Err(MirError::NoBlocks);
495        }
496        let target = self.target();
497        let mut defined = vec![false; self.vregs.len()];
498        let mut define = |r: Option<Reg>| -> Result<(), MirError> {
499            if let Some(v) = r.and_then(Reg::as_virt) {
500                let seen = defined.get_mut(v.index()).ok_or(MirError::UnknownVReg(v))?;
501                if *seen {
502                    return Err(MirError::MultipleDefs { vreg: v });
503                }
504                *seen = true;
505            }
506            Ok(())
507        };
508        for (b, data) in self.blocks.iter().enumerate() {
509            let block = Block::from_index(b);
510            for p in &data.params {
511                define(p.reg())?;
512            }
513            let Some(&last) = data.insts.last() else {
514                return Err(MirError::MissingTerminator { block });
515            };
516            for &inst in data.insts.iter() {
517                let d = self.insts.get(inst.index()).ok_or(MirError::Limit)?;
518                let ops = self.operands(inst);
519                self.check_inst(inst, d.opcode, ops)?;
520                let desc = target.inst(d.opcode).ok_or(MirError::UnknownOpcode {
521                    inst,
522                    opcode: d.opcode,
523                })?;
524                let defs = match desc.kind() {
525                    InstKind::Copy => 1,
526                    InstKind::ParallelCopy => ops.len() / 2,
527                    _ => desc.defs(),
528                };
529                for op in ops.iter().take(defs) {
530                    define(op.reg())?;
531                }
532                let terminator = desc.kind().is_terminator();
533                if terminator && inst != last {
534                    return Err(MirError::MisplacedTerminator { inst });
535                }
536                if !terminator && inst == last {
537                    return Err(MirError::MissingTerminator { block });
538                }
539            }
540        }
541        Ok(())
542    }
543}
backend_lang/mir/verify.rs

backend_lang/mir/
verify.rs
