cranelift_codegen/verifier/
mod.rs

1//! A verifier for ensuring that functions are well formed.
2//! It verifies:
3//!
4//! block integrity
5//!
6//! - All instructions reached from the `block_insts` iterator must belong to
7//!   the block as reported by `inst_block()`.
8//! - Every block must end in a terminator instruction, and no other instruction
9//!   can be a terminator.
10//! - Every value in the `block_params` iterator belongs to the block as reported by `value_block`.
11//!
12//! Instruction integrity
13//!
14//! - The instruction format must match the opcode.
15//! - All result values must be created for multi-valued instructions.
16//! - All referenced entities must exist. (Values, blocks, stack slots, ...)
17//! - Instructions must not reference (eg. branch to) the entry block.
18//!
19//! SSA form
20//!
21//! - Values must be defined by an instruction that exists and that is inserted in
22//!   a block, or be an argument of an existing block.
23//! - Values used by an instruction must dominate the instruction.
24//!
25//! Control flow graph and dominator tree integrity:
26//!
27//! - All predecessors in the CFG must be branches to the block.
28//! - All branches to a block must be present in the CFG.
29//! - A recomputed dominator tree is identical to the existing one.
30//! - The entry block must not be a cold block.
31//!
32//! Type checking
33//!
34//! - Compare input and output values against the opcode's type constraints.
35//!   For polymorphic opcodes, determine the controlling type variable first.
36//! - Branches and jumps must pass arguments to destination blocks that match the
37//!   expected types exactly. The number of arguments must match.
38//! - All blocks in a jump table must take no arguments.
39//! - Function calls are type checked against their signature.
40//! - The entry block must take arguments that match the signature of the current
41//!   function.
42//! - All return instructions must have return value operands matching the current
43//!   function signature.
44//!
45//! Global values
46//!
47//! - Detect cycles in global values.
48//! - Detect use of 'vmctx' global value when no corresponding parameter is defined.
49//!
50//! Memory types
51//!
52//! - Ensure that struct fields are in offset order.
53//! - Ensure that struct fields are completely within the overall
54//!   struct size, and do not overlap.
55//!
56//! TODO:
57//! Ad hoc checking
58//!
59//! - Stack slot loads and stores must be in-bounds.
60//! - Immediate constraints for certain opcodes, like `udiv_imm v3, 0`.
61//! - `Insertlane` and `extractlane` instructions have immediate lane numbers that must be in
62//!   range for their polymorphic type.
63//! - Swizzle and shuffle instructions take a variable number of lane arguments. The number
64//!   of arguments must match the destination type, and the lane indexes must be in range.
65
66use crate::dbg::DisplayList;
67use crate::dominator_tree::DominatorTree;
68use crate::dominator_tree::DominatorTreePreorder;
69use crate::entity::SparseSet;
70use crate::flowgraph::{BlockPredecessor, ControlFlowGraph};
71use crate::ir::ExceptionTableItem;
72use crate::ir::entities::AnyEntity;
73use crate::ir::instructions::{CallInfo, InstructionFormat, ResolvedConstraint};
74use crate::ir::{self, ArgumentExtension, BlockArg, ExceptionTable};
75use crate::ir::{
76    ArgumentPurpose, Block, Constant, DynamicStackSlot, FuncRef, Function, GlobalValue, Inst,
77    JumpTable, MemFlags, MemoryTypeData, Opcode, SigRef, StackSlot, Type, Value, ValueDef,
78    ValueList, types,
79};
80use crate::isa::TargetIsa;
81use crate::print_errors::pretty_verifier_error;
82use crate::settings::FlagsOrIsa;
83use crate::timing;
84use alloc::collections::BTreeSet;
85use alloc::string::{String, ToString};
86use alloc::vec::Vec;
87use core::fmt::{self, Display, Formatter};
88
89/// A verifier error.
90#[derive(Debug, PartialEq, Eq, Clone)]
91pub struct VerifierError {
92    /// The entity causing the verifier error.
93    pub location: AnyEntity,
94    /// Optionally provide some context for the given location; e.g., for `inst42` provide
95    /// `Some("v3 = iconst.i32 0")` for more comprehensible errors.
96    pub context: Option<String>,
97    /// The error message.
98    pub message: String,
99}
100
101// This is manually implementing Error and Display instead of using thiserror to reduce the amount
102// of dependencies used by Cranelift.
103impl std::error::Error for VerifierError {}
104
105impl Display for VerifierError {
106    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
107        match &self.context {
108            None => write!(f, "{}: {}", self.location, self.message),
109            Some(context) => write!(f, "{} ({}): {}", self.location, context, self.message),
110        }
111    }
112}
113
114/// Convenience converter for making error-reporting less verbose.
115///
116/// Converts a tuple of `(location, context, message)` to a `VerifierError`.
117/// ```
118/// use cranelift_codegen::verifier::VerifierErrors;
119/// use cranelift_codegen::ir::Inst;
120/// let mut errors = VerifierErrors::new();
121/// errors.report((Inst::from_u32(42), "v3 = iadd v1, v2", "iadd cannot be used with values of this type"));
122/// // note the double parenthenses to use this syntax
123/// ```
124impl<L, C, M> From<(L, C, M)> for VerifierError
125where
126    L: Into<AnyEntity>,
127    C: Into<String>,
128    M: Into<String>,
129{
130    fn from(items: (L, C, M)) -> Self {
131        let (location, context, message) = items;
132        Self {
133            location: location.into(),
134            context: Some(context.into()),
135            message: message.into(),
136        }
137    }
138}
139
140/// Convenience converter for making error-reporting less verbose.
141///
142/// Same as above but without `context`.
143impl<L, M> From<(L, M)> for VerifierError
144where
145    L: Into<AnyEntity>,
146    M: Into<String>,
147{
148    fn from(items: (L, M)) -> Self {
149        let (location, message) = items;
150        Self {
151            location: location.into(),
152            context: None,
153            message: message.into(),
154        }
155    }
156}
157
158/// Result of a step in the verification process.
159///
160/// Functions that return `VerifierStepResult` should also take a
161/// mutable reference to `VerifierErrors` as argument in order to report
162/// errors.
163///
164/// Here, `Ok` represents a step that **did not lead to a fatal error**,
165/// meaning that the verification process may continue. However, other (non-fatal)
166/// errors might have been reported through the previously mentioned `VerifierErrors`
167/// argument.
168pub type VerifierStepResult = Result<(), ()>;
169
170/// Result of a verification operation.
171///
172/// Unlike `VerifierStepResult` which may be `Ok` while still having reported
173/// errors, this type always returns `Err` if an error (fatal or not) was reported.
174pub type VerifierResult<T> = Result<T, VerifierErrors>;
175
176/// List of verifier errors.
177#[derive(Debug, Default, PartialEq, Eq, Clone)]
178pub struct VerifierErrors(pub Vec<VerifierError>);
179
180// This is manually implementing Error and Display instead of using thiserror to reduce the amount
181// of dependencies used by Cranelift.
182impl std::error::Error for VerifierErrors {}
183
184impl VerifierErrors {
185    /// Return a new `VerifierErrors` struct.
186    #[inline]
187    pub fn new() -> Self {
188        Self(Vec::new())
189    }
190
191    /// Return whether no errors were reported.
192    #[inline]
193    pub fn is_empty(&self) -> bool {
194        self.0.is_empty()
195    }
196
197    /// Return whether one or more errors were reported.
198    #[inline]
199    pub fn has_error(&self) -> bool {
200        !self.0.is_empty()
201    }
202
203    /// Return a `VerifierStepResult` that is fatal if at least one error was reported,
204    /// and non-fatal otherwise.
205    #[inline]
206    pub fn as_result(&self) -> VerifierStepResult {
207        if self.is_empty() { Ok(()) } else { Err(()) }
208    }
209
210    /// Report an error, adding it to the list of errors.
211    pub fn report(&mut self, error: impl Into<VerifierError>) {
212        self.0.push(error.into());
213    }
214
215    /// Report a fatal error and return `Err`.
216    pub fn fatal(&mut self, error: impl Into<VerifierError>) -> VerifierStepResult {
217        self.report(error);
218        Err(())
219    }
220
221    /// Report a non-fatal error and return `Ok`.
222    pub fn nonfatal(&mut self, error: impl Into<VerifierError>) -> VerifierStepResult {
223        self.report(error);
224        Ok(())
225    }
226}
227
228impl From<Vec<VerifierError>> for VerifierErrors {
229    fn from(v: Vec<VerifierError>) -> Self {
230        Self(v)
231    }
232}
233
234impl From<VerifierErrors> for Vec<VerifierError> {
235    fn from(errors: VerifierErrors) -> Vec<VerifierError> {
236        errors.0
237    }
238}
239
240impl From<VerifierErrors> for VerifierResult<()> {
241    fn from(errors: VerifierErrors) -> VerifierResult<()> {
242        if errors.is_empty() {
243            Ok(())
244        } else {
245            Err(errors)
246        }
247    }
248}
249
250impl Display for VerifierErrors {
251    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
252        for err in &self.0 {
253            writeln!(f, "- {err}")?;
254        }
255        Ok(())
256    }
257}
258
259/// Verify `func`.
260pub fn verify_function<'a, FOI: Into<FlagsOrIsa<'a>>>(
261    func: &Function,
262    fisa: FOI,
263) -> VerifierResult<()> {
264    let _tt = timing::verifier();
265    let mut errors = VerifierErrors::default();
266    let verifier = Verifier::new(func, fisa.into());
267    let result = verifier.run(&mut errors);
268    if errors.is_empty() {
269        result.unwrap();
270        Ok(())
271    } else {
272        Err(errors)
273    }
274}
275
276/// Verify `func` after checking the integrity of associated context data structures `cfg` and
277/// `domtree`.
278pub fn verify_context<'a, FOI: Into<FlagsOrIsa<'a>>>(
279    func: &Function,
280    cfg: &ControlFlowGraph,
281    domtree: &DominatorTree,
282    fisa: FOI,
283    errors: &mut VerifierErrors,
284) -> VerifierStepResult {
285    let _tt = timing::verifier();
286    let verifier = Verifier::new(func, fisa.into());
287    if cfg.is_valid() {
288        verifier.cfg_integrity(cfg, errors)?;
289    }
290    if domtree.is_valid() {
291        verifier.domtree_integrity(domtree, errors)?;
292    }
293    verifier.run(errors)
294}
295
296#[derive(Clone, Copy, Debug)]
297enum BlockCallTargetType {
298    Normal,
299    ExNormalRet,
300    Exception,
301}
302
303struct Verifier<'a> {
304    func: &'a Function,
305    expected_cfg: ControlFlowGraph,
306    expected_domtree_preorder: DominatorTreePreorder,
307    expected_domtree: DominatorTree,
308    isa: Option<&'a dyn TargetIsa>,
309}
310
311impl<'a> Verifier<'a> {
312    pub fn new(func: &'a Function, fisa: FlagsOrIsa<'a>) -> Self {
313        let expected_cfg = ControlFlowGraph::with_function(func);
314        let expected_domtree = DominatorTree::with_function(func, &expected_cfg);
315        let mut expected_domtree_preorder = DominatorTreePreorder::new();
316        expected_domtree_preorder.compute(&expected_domtree);
317        Self {
318            func,
319            expected_cfg,
320            expected_domtree,
321            expected_domtree_preorder,
322            isa: fisa.isa,
323        }
324    }
325
326    /// Determine a contextual error string for an instruction.
327    #[inline]
328    fn context(&self, inst: Inst) -> String {
329        self.func.dfg.display_inst(inst).to_string()
330    }
331
332    // Check for:
333    //  - cycles in the global value declarations.
334    //  - use of 'vmctx' when no special parameter declares it.
335    fn verify_global_values(&self, errors: &mut VerifierErrors) -> VerifierStepResult {
336        let mut cycle_seen = false;
337        let mut seen = SparseSet::new();
338
339        'gvs: for gv in self.func.global_values.keys() {
340            seen.clear();
341            seen.insert(gv);
342
343            let mut cur = gv;
344            loop {
345                match self.func.global_values[cur] {
346                    ir::GlobalValueData::Load { base, .. }
347                    | ir::GlobalValueData::IAddImm { base, .. } => {
348                        if seen.insert(base).is_some() {
349                            if !cycle_seen {
350                                errors.report((
351                                    gv,
352                                    format!("global value cycle: {}", DisplayList(seen.as_slice())),
353                                ));
354                                // ensures we don't report the cycle multiple times
355                                cycle_seen = true;
356                            }
357                            continue 'gvs;
358                        }
359
360                        cur = base;
361                    }
362                    _ => break,
363                }
364            }
365
366            match self.func.global_values[gv] {
367                ir::GlobalValueData::VMContext { .. } => {
368                    if self
369                        .func
370                        .special_param(ir::ArgumentPurpose::VMContext)
371                        .is_none()
372                    {
373                        errors.report((gv, format!("undeclared vmctx reference {gv}")));
374                    }
375                }
376                ir::GlobalValueData::IAddImm {
377                    base, global_type, ..
378                } => {
379                    if !global_type.is_int() {
380                        errors.report((
381                            gv,
382                            format!("iadd_imm global value with non-int type {global_type}"),
383                        ));
384                    } else if let Some(isa) = self.isa {
385                        let base_type = self.func.global_values[base].global_type(isa);
386                        if global_type != base_type {
387                            errors.report((
388                                gv,
389                                format!(
390                                    "iadd_imm type {global_type} differs from operand type {base_type}"
391                                ),
392                            ));
393                        }
394                    }
395                }
396                ir::GlobalValueData::Load { base, .. } => {
397                    if let Some(isa) = self.isa {
398                        let base_type = self.func.global_values[base].global_type(isa);
399                        let pointer_type = isa.pointer_type();
400                        if base_type != pointer_type {
401                            errors.report((
402                                gv,
403                                format!(
404                                    "base {base} has type {base_type}, which is not the pointer type {pointer_type}"
405                                ),
406                            ));
407                        }
408                    }
409                }
410                _ => {}
411            }
412        }
413
414        // Invalid global values shouldn't stop us from verifying the rest of the function
415        Ok(())
416    }
417
418    fn verify_memory_types(&self, errors: &mut VerifierErrors) -> VerifierStepResult {
419        // Verify that all fields are statically-sized and lie within
420        // the struct, do not overlap, and are in offset order
421        for (mt, mt_data) in &self.func.memory_types {
422            match mt_data {
423                MemoryTypeData::Struct { size, fields } => {
424                    let mut last_offset = 0;
425                    for field in fields {
426                        if field.offset < last_offset {
427                            errors.report((
428                                mt,
429                                format!(
430                                    "memory type {} has a field at offset {}, which is out-of-order",
431                                    mt, field.offset
432                                ),
433                            ));
434                        }
435                        last_offset = match field.offset.checked_add(u64::from(field.ty.bytes())) {
436                            Some(o) => o,
437                            None => {
438                                errors.report((
439                                        mt,
440                                        format!(
441                                            "memory type {} has a field at offset {} of size {}; offset plus size overflows a u64",
442                                            mt, field.offset, field.ty.bytes()),
443                                ));
444                                break;
445                            }
446                        };
447
448                        if last_offset > *size {
449                            errors.report((
450                                        mt,
451                                        format!(
452                                            "memory type {} has a field at offset {} of size {} that overflows the struct size {}",
453                                            mt, field.offset, field.ty.bytes(), *size),
454                                          ));
455                        }
456                    }
457                }
458                _ => {}
459            }
460        }
461
462        Ok(())
463    }
464
465    /// Check that the given block can be encoded as a BB, by checking that only
466    /// branching instructions are ending the block.
467    fn encodable_as_bb(&self, block: Block, errors: &mut VerifierErrors) -> VerifierStepResult {
468        match self.func.is_block_basic(block) {
469            Ok(()) => Ok(()),
470            Err((inst, message)) => errors.fatal((inst, self.context(inst), message)),
471        }
472    }
473
474    fn block_integrity(
475        &self,
476        block: Block,
477        inst: Inst,
478        errors: &mut VerifierErrors,
479    ) -> VerifierStepResult {
480        let is_terminator = self.func.dfg.insts[inst].opcode().is_terminator();
481        let is_last_inst = self.func.layout.last_inst(block) == Some(inst);
482
483        if is_terminator && !is_last_inst {
484            // Terminating instructions only occur at the end of blocks.
485            return errors.fatal((
486                inst,
487                self.context(inst),
488                format!("a terminator instruction was encountered before the end of {block}"),
489            ));
490        }
491        if is_last_inst && !is_terminator {
492            return errors.fatal((block, "block does not end in a terminator instruction"));
493        }
494
495        // Instructions belong to the correct block.
496        let inst_block = self.func.layout.inst_block(inst);
497        if inst_block != Some(block) {
498            return errors.fatal((
499                inst,
500                self.context(inst),
501                format!("should belong to {block} not {inst_block:?}"),
502            ));
503        }
504
505        // Parameters belong to the correct block.
506        for &arg in self.func.dfg.block_params(block) {
507            match self.func.dfg.value_def(arg) {
508                ValueDef::Param(arg_block, _) => {
509                    if block != arg_block {
510                        return errors.fatal((arg, format!("does not belong to {block}")));
511                    }
512                }
513                _ => {
514                    return errors.fatal((arg, "expected an argument, found a result"));
515                }
516            }
517        }
518
519        Ok(())
520    }
521
522    fn instruction_integrity(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult {
523        let inst_data = &self.func.dfg.insts[inst];
524        let dfg = &self.func.dfg;
525
526        // The instruction format matches the opcode
527        if inst_data.opcode().format() != InstructionFormat::from(inst_data) {
528            return errors.fatal((
529                inst,
530                self.context(inst),
531                "instruction opcode doesn't match instruction format",
532            ));
533        }
534
535        let expected_num_results = dfg.num_expected_results_for_verifier(inst);
536
537        // All result values for multi-valued instructions are created
538        let got_results = dfg.inst_results(inst).len();
539        if got_results != expected_num_results {
540            return errors.fatal((
541                inst,
542                self.context(inst),
543                format!("expected {expected_num_results} result values, found {got_results}"),
544            ));
545        }
546
547        self.verify_entity_references(inst, errors)
548    }
549
550    fn verify_entity_references(
551        &self,
552        inst: Inst,
553        errors: &mut VerifierErrors,
554    ) -> VerifierStepResult {
555        use crate::ir::instructions::InstructionData::*;
556
557        for arg in self.func.dfg.inst_values(inst) {
558            self.verify_inst_arg(inst, arg, errors)?;
559
560            // All used values must be attached to something.
561            let original = self.func.dfg.resolve_aliases(arg);
562            if !self.func.dfg.value_is_attached(original) {
563                errors.report((
564                    inst,
565                    self.context(inst),
566                    format!("argument {arg} -> {original} is not attached"),
567                ));
568            }
569        }
570
571        for &res in self.func.dfg.inst_results(inst) {
572            self.verify_inst_result(inst, res, errors)?;
573        }
574
575        match self.func.dfg.insts[inst] {
576            MultiAry { ref args, .. } => {
577                self.verify_value_list(inst, args, errors)?;
578            }
579            Jump { destination, .. } => {
580                self.verify_block(inst, destination.block(&self.func.dfg.value_lists), errors)?;
581            }
582            Brif {
583                arg,
584                blocks: [block_then, block_else],
585                ..
586            } => {
587                self.verify_value(inst, arg, errors)?;
588                self.verify_block(inst, block_then.block(&self.func.dfg.value_lists), errors)?;
589                self.verify_block(inst, block_else.block(&self.func.dfg.value_lists), errors)?;
590            }
591            BranchTable { table, .. } => {
592                self.verify_jump_table(inst, table, errors)?;
593            }
594            Call {
595                func_ref, ref args, ..
596            } => {
597                self.verify_func_ref(inst, func_ref, errors)?;
598                self.verify_value_list(inst, args, errors)?;
599            }
600            CallIndirect {
601                sig_ref, ref args, ..
602            } => {
603                self.verify_sig_ref(inst, sig_ref, errors)?;
604                self.verify_value_list(inst, args, errors)?;
605            }
606            TryCall {
607                func_ref,
608                ref args,
609                exception,
610                ..
611            } => {
612                self.verify_func_ref(inst, func_ref, errors)?;
613                self.verify_value_list(inst, args, errors)?;
614                self.verify_exception_table(inst, exception, errors)?;
615                self.verify_exception_compatible_abi(inst, exception, errors)?;
616            }
617            TryCallIndirect {
618                ref args,
619                exception,
620                ..
621            } => {
622                self.verify_value_list(inst, args, errors)?;
623                self.verify_exception_table(inst, exception, errors)?;
624                self.verify_exception_compatible_abi(inst, exception, errors)?;
625            }
626            FuncAddr { func_ref, .. } => {
627                self.verify_func_ref(inst, func_ref, errors)?;
628            }
629            StackLoad { stack_slot, .. } | StackStore { stack_slot, .. } => {
630                self.verify_stack_slot(inst, stack_slot, errors)?;
631            }
632            DynamicStackLoad {
633                dynamic_stack_slot, ..
634            }
635            | DynamicStackStore {
636                dynamic_stack_slot, ..
637            } => {
638                self.verify_dynamic_stack_slot(inst, dynamic_stack_slot, errors)?;
639            }
640            UnaryGlobalValue { global_value, .. } => {
641                self.verify_global_value(inst, global_value, errors)?;
642            }
643            NullAry {
644                opcode: Opcode::GetPinnedReg,
645            }
646            | Unary {
647                opcode: Opcode::SetPinnedReg,
648                ..
649            } => {
650                if let Some(isa) = &self.isa {
651                    if !isa.flags().enable_pinned_reg() {
652                        return errors.fatal((
653                            inst,
654                            self.context(inst),
655                            "GetPinnedReg/SetPinnedReg cannot be used without enable_pinned_reg",
656                        ));
657                    }
658                } else {
659                    return errors.fatal((
660                        inst,
661                        self.context(inst),
662                        "GetPinnedReg/SetPinnedReg need an ISA!",
663                    ));
664                }
665            }
666            NullAry {
667                opcode: Opcode::GetFramePointer | Opcode::GetReturnAddress,
668            } => {
669                if let Some(isa) = &self.isa {
670                    // Backends may already rely on this check implicitly, so do
671                    // not relax it without verifying that it is safe to do so.
672                    if !isa.flags().preserve_frame_pointers() {
673                        return errors.fatal((
674                            inst,
675                            self.context(inst),
676                            "`get_frame_pointer`/`get_return_address` cannot be used without \
677                             enabling `preserve_frame_pointers`",
678                        ));
679                    }
680                } else {
681                    return errors.fatal((
682                        inst,
683                        self.context(inst),
684                        "`get_frame_pointer`/`get_return_address` require an ISA!",
685                    ));
686                }
687            }
688            LoadNoOffset {
689                opcode: Opcode::Bitcast,
690                flags,
691                arg,
692            } => {
693                self.verify_bitcast(inst, flags, arg, errors)?;
694            }
695            LoadNoOffset { opcode, arg, .. } if opcode.can_load() => {
696                self.verify_is_address(inst, arg, errors)?;
697            }
698            Load { opcode, arg, .. } if opcode.can_load() => {
699                self.verify_is_address(inst, arg, errors)?;
700            }
701            AtomicCas {
702                opcode,
703                args: [p, _, _],
704                ..
705            } if opcode.can_load() || opcode.can_store() => {
706                self.verify_is_address(inst, p, errors)?;
707            }
708            AtomicRmw {
709                opcode,
710                args: [p, _],
711                ..
712            } if opcode.can_load() || opcode.can_store() => {
713                self.verify_is_address(inst, p, errors)?;
714            }
715            Store {
716                opcode,
717                args: [_, p],
718                ..
719            } if opcode.can_store() => {
720                self.verify_is_address(inst, p, errors)?;
721            }
722            StoreNoOffset {
723                opcode,
724                args: [_, p],
725                ..
726            } if opcode.can_store() => {
727                self.verify_is_address(inst, p, errors)?;
728            }
729            UnaryConst {
730                opcode: opcode @ (Opcode::Vconst | Opcode::F128const),
731                constant_handle,
732                ..
733            } => {
734                self.verify_constant_size(inst, opcode, constant_handle, errors)?;
735            }
736
737            // Exhaustive list so we can't forget to add new formats
738            AtomicCas { .. }
739            | AtomicRmw { .. }
740            | LoadNoOffset { .. }
741            | StoreNoOffset { .. }
742            | Unary { .. }
743            | UnaryConst { .. }
744            | UnaryImm { .. }
745            | UnaryIeee16 { .. }
746            | UnaryIeee32 { .. }
747            | UnaryIeee64 { .. }
748            | Binary { .. }
749            | BinaryImm8 { .. }
750            | BinaryImm64 { .. }
751            | Ternary { .. }
752            | TernaryImm8 { .. }
753            | Shuffle { .. }
754            | IntAddTrap { .. }
755            | IntCompare { .. }
756            | IntCompareImm { .. }
757            | FloatCompare { .. }
758            | Load { .. }
759            | Store { .. }
760            | Trap { .. }
761            | CondTrap { .. }
762            | NullAry { .. } => {}
763        }
764
765        Ok(())
766    }
767
768    fn verify_block(
769        &self,
770        loc: impl Into<AnyEntity>,
771        e: Block,
772        errors: &mut VerifierErrors,
773    ) -> VerifierStepResult {
774        if !self.func.dfg.block_is_valid(e) || !self.func.layout.is_block_inserted(e) {
775            return errors.fatal((loc, format!("invalid block reference {e}")));
776        }
777        if let Some(entry_block) = self.func.layout.entry_block() {
778            if e == entry_block {
779                return errors.fatal((loc, format!("invalid reference to entry block {e}")));
780            }
781        }
782        Ok(())
783    }
784
785    fn verify_sig_ref(
786        &self,
787        inst: Inst,
788        s: SigRef,
789        errors: &mut VerifierErrors,
790    ) -> VerifierStepResult {
791        if !self.func.dfg.signatures.is_valid(s) {
792            errors.fatal((
793                inst,
794                self.context(inst),
795                format!("invalid signature reference {s}"),
796            ))
797        } else {
798            Ok(())
799        }
800    }
801
802    fn verify_func_ref(
803        &self,
804        inst: Inst,
805        f: FuncRef,
806        errors: &mut VerifierErrors,
807    ) -> VerifierStepResult {
808        if !self.func.dfg.ext_funcs.is_valid(f) {
809            errors.nonfatal((
810                inst,
811                self.context(inst),
812                format!("invalid function reference {f}"),
813            ))
814        } else {
815            Ok(())
816        }
817    }
818
819    fn verify_stack_slot(
820        &self,
821        inst: Inst,
822        ss: StackSlot,
823        errors: &mut VerifierErrors,
824    ) -> VerifierStepResult {
825        if !self.func.sized_stack_slots.is_valid(ss) {
826            errors.nonfatal((inst, self.context(inst), format!("invalid stack slot {ss}")))
827        } else {
828            Ok(())
829        }
830    }
831
832    fn verify_dynamic_stack_slot(
833        &self,
834        inst: Inst,
835        ss: DynamicStackSlot,
836        errors: &mut VerifierErrors,
837    ) -> VerifierStepResult {
838        if !self.func.dynamic_stack_slots.is_valid(ss) {
839            errors.nonfatal((
840                inst,
841                self.context(inst),
842                format!("invalid dynamic stack slot {ss}"),
843            ))
844        } else {
845            Ok(())
846        }
847    }
848
849    fn verify_global_value(
850        &self,
851        inst: Inst,
852        gv: GlobalValue,
853        errors: &mut VerifierErrors,
854    ) -> VerifierStepResult {
855        if !self.func.global_values.is_valid(gv) {
856            errors.nonfatal((
857                inst,
858                self.context(inst),
859                format!("invalid global value {gv}"),
860            ))
861        } else {
862            Ok(())
863        }
864    }
865
866    fn verify_value_list(
867        &self,
868        inst: Inst,
869        l: &ValueList,
870        errors: &mut VerifierErrors,
871    ) -> VerifierStepResult {
872        if !l.is_valid(&self.func.dfg.value_lists) {
873            errors.nonfatal((
874                inst,
875                self.context(inst),
876                format!("invalid value list reference {l:?}"),
877            ))
878        } else {
879            Ok(())
880        }
881    }
882
883    fn verify_jump_table(
884        &self,
885        inst: Inst,
886        j: JumpTable,
887        errors: &mut VerifierErrors,
888    ) -> VerifierStepResult {
889        if !self.func.stencil.dfg.jump_tables.is_valid(j) {
890            errors.nonfatal((
891                inst,
892                self.context(inst),
893                format!("invalid jump table reference {j}"),
894            ))
895        } else {
896            let pool = &self.func.stencil.dfg.value_lists;
897            for block in self.func.stencil.dfg.jump_tables[j].all_branches() {
898                self.verify_block(inst, block.block(pool), errors)?;
899            }
900            Ok(())
901        }
902    }
903
904    fn verify_exception_table(
905        &self,
906        inst: Inst,
907        et: ExceptionTable,
908        errors: &mut VerifierErrors,
909    ) -> VerifierStepResult {
910        // Verify that the exception table reference itself is valid.
911        if !self.func.stencil.dfg.exception_tables.is_valid(et) {
912            errors.nonfatal((
913                inst,
914                self.context(inst),
915                format!("invalid exception table reference {et}"),
916            ))?;
917        }
918
919        let pool = &self.func.stencil.dfg.value_lists;
920        let exdata = &self.func.stencil.dfg.exception_tables[et];
921
922        // Verify that the exception table's signature reference
923        // is valid.
924        self.verify_sig_ref(inst, exdata.signature(), errors)?;
925
926        // Verify that the exception table's block references are valid.
927        for block in exdata.all_branches() {
928            self.verify_block(inst, block.block(pool), errors)?;
929        }
930        Ok(())
931    }
932
933    fn verify_exception_compatible_abi(
934        &self,
935        inst: Inst,
936        et: ExceptionTable,
937        errors: &mut VerifierErrors,
938    ) -> VerifierStepResult {
939        let callee_sig_ref = self.func.dfg.exception_tables[et].signature();
940        let callee_sig = &self.func.dfg.signatures[callee_sig_ref];
941        let callee_call_conv = callee_sig.call_conv;
942        if !callee_call_conv.supports_exceptions() {
943            errors.nonfatal((
944                inst,
945                self.context(inst),
946                format!(
947                    "calling convention `{callee_call_conv}` of callee does not support exceptions"
948                ),
949            ))?;
950        }
951        Ok(())
952    }
953
954    fn verify_value(
955        &self,
956        loc_inst: Inst,
957        v: Value,
958        errors: &mut VerifierErrors,
959    ) -> VerifierStepResult {
960        let dfg = &self.func.dfg;
961        if !dfg.value_is_valid(v) {
962            errors.nonfatal((
963                loc_inst,
964                self.context(loc_inst),
965                format!("invalid value reference {v}"),
966            ))
967        } else {
968            Ok(())
969        }
970    }
971
972    fn verify_inst_arg(
973        &self,
974        loc_inst: Inst,
975        v: Value,
976        errors: &mut VerifierErrors,
977    ) -> VerifierStepResult {
978        self.verify_value(loc_inst, v, errors)?;
979
980        let dfg = &self.func.dfg;
981        let loc_block = self
982            .func
983            .layout
984            .inst_block(loc_inst)
985            .expect("Instruction not in layout.");
986        let is_reachable = self.expected_domtree.is_reachable(loc_block);
987
988        // SSA form
989        match dfg.value_def(v) {
990            ValueDef::Result(def_inst, _) => {
991                // Value is defined by an instruction that exists.
992                if !dfg.inst_is_valid(def_inst) {
993                    return errors.fatal((
994                        loc_inst,
995                        self.context(loc_inst),
996                        format!("{v} is defined by invalid instruction {def_inst}"),
997                    ));
998                }
999                // Defining instruction is inserted in a block.
1000                if self.func.layout.inst_block(def_inst) == None {
1001                    return errors.fatal((
1002                        loc_inst,
1003                        self.context(loc_inst),
1004                        format!("{v} is defined by {def_inst} which has no block"),
1005                    ));
1006                }
1007                // Defining instruction dominates the instruction that uses the value.
1008                if is_reachable {
1009                    if !self.expected_domtree_preorder.dominates_inst(
1010                        def_inst,
1011                        loc_inst,
1012                        &self.func.layout,
1013                    ) {
1014                        return errors.fatal((
1015                            loc_inst,
1016                            self.context(loc_inst),
1017                            format!("uses value {v} from non-dominating {def_inst}"),
1018                        ));
1019                    }
1020                    if def_inst == loc_inst {
1021                        return errors.fatal((
1022                            loc_inst,
1023                            self.context(loc_inst),
1024                            format!("uses value {v} from itself"),
1025                        ));
1026                    }
1027                }
1028            }
1029            ValueDef::Param(block, _) => {
1030                // Value is defined by an existing block.
1031                if !dfg.block_is_valid(block) {
1032                    return errors.fatal((
1033                        loc_inst,
1034                        self.context(loc_inst),
1035                        format!("{v} is defined by invalid block {block}"),
1036                    ));
1037                }
1038                // Defining block is inserted in the layout
1039                if !self.func.layout.is_block_inserted(block) {
1040                    return errors.fatal((
1041                        loc_inst,
1042                        self.context(loc_inst),
1043                        format!("{v} is defined by {block} which is not in the layout"),
1044                    ));
1045                }
1046                let user_block = self.func.layout.inst_block(loc_inst).expect("Expected instruction to be in a block as we're traversing code already in layout");
1047                // The defining block dominates the instruction using this value.
1048                if is_reachable && !self.expected_domtree_preorder.dominates(block, user_block) {
1049                    return errors.fatal((
1050                        loc_inst,
1051                        self.context(loc_inst),
1052                        format!("uses value arg from non-dominating {block}"),
1053                    ));
1054                }
1055            }
1056            ValueDef::Union(_, _) => {
1057                // Nothing: union nodes themselves have no location,
1058                // so we cannot check any dominance properties.
1059            }
1060        }
1061        Ok(())
1062    }
1063
1064    fn verify_inst_result(
1065        &self,
1066        loc_inst: Inst,
1067        v: Value,
1068        errors: &mut VerifierErrors,
1069    ) -> VerifierStepResult {
1070        self.verify_value(loc_inst, v, errors)?;
1071
1072        match self.func.dfg.value_def(v) {
1073            ValueDef::Result(def_inst, _) => {
1074                if def_inst != loc_inst {
1075                    errors.fatal((
1076                        loc_inst,
1077                        self.context(loc_inst),
1078                        format!("instruction result {v} is not defined by the instruction"),
1079                    ))
1080                } else {
1081                    Ok(())
1082                }
1083            }
1084            ValueDef::Param(_, _) => errors.fatal((
1085                loc_inst,
1086                self.context(loc_inst),
1087                format!("instruction result {v} is not defined by the instruction"),
1088            )),
1089            ValueDef::Union(_, _) => errors.fatal((
1090                loc_inst,
1091                self.context(loc_inst),
1092                format!("instruction result {v} is a union node"),
1093            )),
1094        }
1095    }
1096
1097    fn verify_bitcast(
1098        &self,
1099        inst: Inst,
1100        flags: MemFlags,
1101        arg: Value,
1102        errors: &mut VerifierErrors,
1103    ) -> VerifierStepResult {
1104        let typ = self.func.dfg.ctrl_typevar(inst);
1105        let value_type = self.func.dfg.value_type(arg);
1106
1107        if typ.bits() != value_type.bits() {
1108            errors.fatal((
1109                inst,
1110                format!(
1111                    "The bitcast argument {} has a type of {} bits, which doesn't match an expected type of {} bits",
1112                    arg,
1113                    value_type.bits(),
1114                    typ.bits()
1115                ),
1116            ))
1117        } else if flags != MemFlags::new()
1118            && flags != MemFlags::new().with_endianness(ir::Endianness::Little)
1119            && flags != MemFlags::new().with_endianness(ir::Endianness::Big)
1120        {
1121            errors.fatal((
1122                inst,
1123                "The bitcast instruction only accepts the `big` or `little` memory flags",
1124            ))
1125        } else if flags == MemFlags::new() && typ.lane_count() != value_type.lane_count() {
1126            errors.fatal((
1127                inst,
1128                "Byte order specifier required for bitcast instruction changing lane count",
1129            ))
1130        } else {
1131            Ok(())
1132        }
1133    }
1134
1135    fn verify_constant_size(
1136        &self,
1137        inst: Inst,
1138        opcode: Opcode,
1139        constant: Constant,
1140        errors: &mut VerifierErrors,
1141    ) -> VerifierStepResult {
1142        let type_size = match opcode {
1143            Opcode::F128const => types::F128.bytes(),
1144            Opcode::Vconst => self.func.dfg.ctrl_typevar(inst).bytes(),
1145            _ => unreachable!("unexpected opcode {opcode:?}"),
1146        } as usize;
1147        let constant_size = self.func.dfg.constants.get(constant).len();
1148        if type_size != constant_size {
1149            errors.fatal((
1150                inst,
1151                format!(
1152                    "The instruction expects {constant} to have a size of {type_size} bytes but it has {constant_size}"
1153                ),
1154            ))
1155        } else {
1156            Ok(())
1157        }
1158    }
1159
1160    fn verify_is_address(
1161        &self,
1162        loc_inst: Inst,
1163        v: Value,
1164        errors: &mut VerifierErrors,
1165    ) -> VerifierStepResult {
1166        if let Some(isa) = self.isa {
1167            let pointer_width = isa.triple().pointer_width()?;
1168            let value_type = self.func.dfg.value_type(v);
1169            let expected_width = pointer_width.bits() as u32;
1170            let value_width = value_type.bits();
1171            if expected_width != value_width {
1172                errors.nonfatal((
1173                    loc_inst,
1174                    self.context(loc_inst),
1175                    format!("invalid pointer width (got {value_width}, expected {expected_width}) encountered {v}"),
1176                ))
1177            } else {
1178                Ok(())
1179            }
1180        } else {
1181            Ok(())
1182        }
1183    }
1184
1185    fn domtree_integrity(
1186        &self,
1187        domtree: &DominatorTree,
1188        errors: &mut VerifierErrors,
1189    ) -> VerifierStepResult {
1190        // We consider two `DominatorTree`s to be equal if they return the same immediate
1191        // dominator for each block. Therefore the current domtree is valid if it matches the freshly
1192        // computed one.
1193        for block in self.func.layout.blocks() {
1194            let expected = self.expected_domtree.idom(block);
1195            let got = domtree.idom(block);
1196            if got != expected {
1197                return errors.fatal((
1198                    block,
1199                    format!("invalid domtree, expected idom({block}) = {expected:?}, got {got:?}"),
1200                ));
1201            }
1202        }
1203        // We also verify if the postorder defined by `DominatorTree` is sane
1204        if domtree.cfg_postorder().len() != self.expected_domtree.cfg_postorder().len() {
1205            return errors.fatal((
1206                AnyEntity::Function,
1207                "incorrect number of Blocks in postorder traversal",
1208            ));
1209        }
1210        for (index, (&test_block, &true_block)) in domtree
1211            .cfg_postorder()
1212            .iter()
1213            .zip(self.expected_domtree.cfg_postorder().iter())
1214            .enumerate()
1215        {
1216            if test_block != true_block {
1217                return errors.fatal((
1218                    test_block,
1219                    format!(
1220                        "invalid domtree, postorder block number {index} should be {true_block}, got {test_block}"
1221                    ),
1222                ));
1223            }
1224        }
1225        Ok(())
1226    }
1227
1228    fn typecheck_entry_block_params(&self, errors: &mut VerifierErrors) -> VerifierStepResult {
1229        if let Some(block) = self.func.layout.entry_block() {
1230            let expected_types = &self.func.signature.params;
1231            let block_param_count = self.func.dfg.num_block_params(block);
1232
1233            if block_param_count != expected_types.len() {
1234                return errors.fatal((
1235                    block,
1236                    format!(
1237                        "entry block parameters ({}) must match function signature ({})",
1238                        block_param_count,
1239                        expected_types.len()
1240                    ),
1241                ));
1242            }
1243
1244            for (i, &arg) in self.func.dfg.block_params(block).iter().enumerate() {
1245                let arg_type = self.func.dfg.value_type(arg);
1246                if arg_type != expected_types[i].value_type {
1247                    errors.report((
1248                        block,
1249                        format!(
1250                            "entry block parameter {} expected to have type {}, got {}",
1251                            i, expected_types[i], arg_type
1252                        ),
1253                    ));
1254                }
1255            }
1256        }
1257
1258        errors.as_result()
1259    }
1260
1261    fn check_entry_not_cold(&self, errors: &mut VerifierErrors) -> VerifierStepResult {
1262        if let Some(entry_block) = self.func.layout.entry_block() {
1263            if self.func.layout.is_cold(entry_block) {
1264                return errors
1265                    .fatal((entry_block, format!("entry block cannot be marked as cold")));
1266            }
1267        }
1268        errors.as_result()
1269    }
1270
1271    fn typecheck(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult {
1272        let inst_data = &self.func.dfg.insts[inst];
1273        let constraints = inst_data.opcode().constraints();
1274
1275        let ctrl_type = if let Some(value_typeset) = constraints.ctrl_typeset() {
1276            // For polymorphic opcodes, determine the controlling type variable first.
1277            let ctrl_type = self.func.dfg.ctrl_typevar(inst);
1278
1279            if !value_typeset.contains(ctrl_type) {
1280                errors.report((
1281                    inst,
1282                    self.context(inst),
1283                    format!(
1284                        "has an invalid controlling type {ctrl_type} (allowed set is {value_typeset:?})"
1285                    ),
1286                ));
1287            }
1288
1289            ctrl_type
1290        } else {
1291            // Non-polymorphic instructions don't check the controlling type variable, so `Option`
1292            // is unnecessary and we can just make it `INVALID`.
1293            types::INVALID
1294        };
1295
1296        // Typechecking instructions is never fatal
1297        let _ = self.typecheck_results(inst, ctrl_type, errors);
1298        let _ = self.typecheck_fixed_args(inst, ctrl_type, errors);
1299        let _ = self.typecheck_variable_args(inst, errors);
1300        let _ = self.typecheck_return(inst, errors);
1301        let _ = self.typecheck_special(inst, errors);
1302
1303        Ok(())
1304    }
1305
1306    fn typecheck_results(
1307        &self,
1308        inst: Inst,
1309        ctrl_type: Type,
1310        errors: &mut VerifierErrors,
1311    ) -> VerifierStepResult {
1312        let mut i = 0;
1313        for &result in self.func.dfg.inst_results(inst) {
1314            let result_type = self.func.dfg.value_type(result);
1315            let expected_type = self.func.dfg.compute_result_type(inst, i, ctrl_type);
1316            if let Some(expected_type) = expected_type {
1317                if result_type != expected_type {
1318                    errors.report((
1319                        inst,
1320                        self.context(inst),
1321                        format!(
1322                            "expected result {i} ({result}) to have type {expected_type}, found {result_type}"
1323                        ),
1324                    ));
1325                }
1326            } else {
1327                return errors.nonfatal((
1328                    inst,
1329                    self.context(inst),
1330                    "has more result values than expected",
1331                ));
1332            }
1333            i += 1;
1334        }
1335
1336        // There aren't any more result types left.
1337        if self.func.dfg.compute_result_type(inst, i, ctrl_type) != None {
1338            return errors.nonfatal((
1339                inst,
1340                self.context(inst),
1341                "has fewer result values than expected",
1342            ));
1343        }
1344        Ok(())
1345    }
1346
1347    fn typecheck_fixed_args(
1348        &self,
1349        inst: Inst,
1350        ctrl_type: Type,
1351        errors: &mut VerifierErrors,
1352    ) -> VerifierStepResult {
1353        let constraints = self.func.dfg.insts[inst].opcode().constraints();
1354
1355        for (i, &arg) in self.func.dfg.inst_fixed_args(inst).iter().enumerate() {
1356            let arg_type = self.func.dfg.value_type(arg);
1357            match constraints.value_argument_constraint(i, ctrl_type) {
1358                ResolvedConstraint::Bound(expected_type) => {
1359                    if arg_type != expected_type {
1360                        errors.report((
1361                            inst,
1362                            self.context(inst),
1363                            format!(
1364                                "arg {i} ({arg}) has type {arg_type}, expected {expected_type}"
1365                            ),
1366                        ));
1367                    }
1368                }
1369                ResolvedConstraint::Free(type_set) => {
1370                    if !type_set.contains(arg_type) {
1371                        errors.report((
1372                            inst,
1373                            self.context(inst),
1374                            format!(
1375                                "arg {i} ({arg}) with type {arg_type} failed to satisfy type set {type_set:?}"
1376                            ),
1377                        ));
1378                    }
1379                }
1380            }
1381        }
1382        Ok(())
1383    }
1384
1385    /// Typecheck both instructions that contain variable arguments like calls, and those that
1386    /// include references to basic blocks with their arguments.
1387    fn typecheck_variable_args(
1388        &self,
1389        inst: Inst,
1390        errors: &mut VerifierErrors,
1391    ) -> VerifierStepResult {
1392        match &self.func.dfg.insts[inst] {
1393            ir::InstructionData::Jump { destination, .. } => {
1394                self.typecheck_block_call(inst, destination, BlockCallTargetType::Normal, errors)?;
1395            }
1396            ir::InstructionData::Brif {
1397                blocks: [block_then, block_else],
1398                ..
1399            } => {
1400                self.typecheck_block_call(inst, block_then, BlockCallTargetType::Normal, errors)?;
1401                self.typecheck_block_call(inst, block_else, BlockCallTargetType::Normal, errors)?;
1402            }
1403            ir::InstructionData::BranchTable { table, .. } => {
1404                for block in self.func.stencil.dfg.jump_tables[*table].all_branches() {
1405                    self.typecheck_block_call(inst, block, BlockCallTargetType::Normal, errors)?;
1406                }
1407            }
1408            ir::InstructionData::TryCall { exception, .. }
1409            | ir::InstructionData::TryCallIndirect { exception, .. } => {
1410                let exdata = &self.func.dfg.exception_tables[*exception];
1411                self.typecheck_block_call(
1412                    inst,
1413                    exdata.normal_return(),
1414                    BlockCallTargetType::ExNormalRet,
1415                    errors,
1416                )?;
1417                for item in exdata.items() {
1418                    match item {
1419                        ExceptionTableItem::Tag(_, block_call)
1420                        | ExceptionTableItem::Default(block_call) => {
1421                            self.typecheck_block_call(
1422                                inst,
1423                                &block_call,
1424                                BlockCallTargetType::Exception,
1425                                errors,
1426                            )?;
1427                        }
1428                        ExceptionTableItem::Context(_) => {}
1429                    }
1430                }
1431            }
1432            inst => debug_assert!(!inst.opcode().is_branch()),
1433        }
1434
1435        match self.func.dfg.insts[inst]
1436            .analyze_call(&self.func.dfg.value_lists, &self.func.dfg.exception_tables)
1437        {
1438            CallInfo::Direct(func_ref, args) => {
1439                let sig_ref = self.func.dfg.ext_funcs[func_ref].signature;
1440                let arg_types = self.func.dfg.signatures[sig_ref]
1441                    .params
1442                    .iter()
1443                    .map(|a| a.value_type);
1444                self.typecheck_variable_args_iterator(inst, arg_types, args, errors)?;
1445            }
1446            CallInfo::DirectWithSig(func_ref, sig_ref, args) => {
1447                let expected_sig_ref = self.func.dfg.ext_funcs[func_ref].signature;
1448                let sigdata = &self.func.dfg.signatures;
1449                // Compare signatures by value, not by ID -- any
1450                // equivalent signature ID is acceptable.
1451                if sigdata[sig_ref] != sigdata[expected_sig_ref] {
1452                    errors.nonfatal((
1453                        inst,
1454                        self.context(inst),
1455                        format!(
1456                            "exception table signature {sig_ref} did not match function {func_ref}'s signature {expected_sig_ref}"
1457                        ),
1458                    ))?;
1459                }
1460                let arg_types = self.func.dfg.signatures[sig_ref]
1461                    .params
1462                    .iter()
1463                    .map(|a| a.value_type);
1464                self.typecheck_variable_args_iterator(inst, arg_types, args, errors)?;
1465            }
1466            CallInfo::Indirect(sig_ref, args) => {
1467                let arg_types = self.func.dfg.signatures[sig_ref]
1468                    .params
1469                    .iter()
1470                    .map(|a| a.value_type);
1471                self.typecheck_variable_args_iterator(inst, arg_types, args, errors)?;
1472            }
1473            CallInfo::NotACall => {}
1474        }
1475        Ok(())
1476    }
1477
1478    fn typecheck_block_call(
1479        &self,
1480        inst: Inst,
1481        block: &ir::BlockCall,
1482        target_type: BlockCallTargetType,
1483        errors: &mut VerifierErrors,
1484    ) -> VerifierStepResult {
1485        let pool = &self.func.dfg.value_lists;
1486        let block_params = self.func.dfg.block_params(block.block(pool));
1487        let args = block.args(pool);
1488        if args.len() != block_params.len() {
1489            return errors.nonfatal((
1490                inst,
1491                self.context(inst),
1492                format!(
1493                    "mismatched argument count for `{}`: got {}, expected {}",
1494                    self.func.dfg.display_inst(inst),
1495                    args.len(),
1496                    block_params.len(),
1497                ),
1498            ));
1499        }
1500        for (arg, param) in args.zip(block_params.iter()) {
1501            let Some(arg_ty) = self.block_call_arg_ty(arg, inst, target_type, errors)? else {
1502                continue;
1503            };
1504            let param_ty = self.func.dfg.value_type(*param);
1505            if arg_ty != param_ty {
1506                errors.nonfatal((
1507                    inst,
1508                    self.context(inst),
1509                    format!("arg {arg} has type {arg_ty}, expected {param_ty}"),
1510                ))?;
1511            }
1512        }
1513        Ok(())
1514    }
1515
1516    fn block_call_arg_ty(
1517        &self,
1518        arg: BlockArg,
1519        inst: Inst,
1520        target_type: BlockCallTargetType,
1521        errors: &mut VerifierErrors,
1522    ) -> Result<Option<Type>, ()> {
1523        match arg {
1524            BlockArg::Value(v) => Ok(Some(self.func.dfg.value_type(v))),
1525            BlockArg::TryCallRet(_) | BlockArg::TryCallExn(_) => {
1526                // Get the invoked signature.
1527                let et = match self.func.dfg.insts[inst].exception_table() {
1528                    Some(et) => et,
1529                    None => {
1530                        errors.fatal((
1531                            inst,
1532                            self.context(inst),
1533                            format!(
1534                                "`retN` block argument in block-call not on `try_call` instruction"
1535                            ),
1536                        ))?;
1537                        unreachable!()
1538                    }
1539                };
1540                let exdata = &self.func.dfg.exception_tables[et];
1541                let sig = &self.func.dfg.signatures[exdata.signature()];
1542
1543                match (arg, target_type) {
1544                    (BlockArg::TryCallRet(i), BlockCallTargetType::ExNormalRet)
1545                        if (i as usize) < sig.returns.len() =>
1546                    {
1547                        Ok(Some(sig.returns[i as usize].value_type))
1548                    }
1549                    (BlockArg::TryCallRet(_), BlockCallTargetType::ExNormalRet) => {
1550                        errors.fatal((
1551                            inst,
1552                            self.context(inst),
1553                            format!("out-of-bounds `retN` block argument"),
1554                        ))?;
1555                        unreachable!()
1556                    }
1557                    (BlockArg::TryCallRet(_), _) => {
1558                        errors.fatal((
1559                            inst,
1560                            self.context(inst),
1561                            format!("`retN` block argument used outside normal-return target of `try_call`"),
1562                        ))?;
1563                        unreachable!()
1564                    }
1565                    (BlockArg::TryCallExn(i), BlockCallTargetType::Exception) => {
1566                        if let Some(isa) = self.isa {
1567                            match sig
1568                                .call_conv
1569                                .exception_payload_types(isa.pointer_type())
1570                                .get(i as usize)
1571                            {
1572                                Some(ty) => Ok(Some(*ty)),
1573                                None => {
1574                                    errors.fatal((
1575                                        inst,
1576                                        self.context(inst),
1577                                        format!("out-of-bounds `exnN` block argument"),
1578                                    ))?;
1579                                    unreachable!()
1580                                }
1581                            }
1582                        } else {
1583                            Ok(None)
1584                        }
1585                    }
1586                    (BlockArg::TryCallExn(_), _) => {
1587                        errors.fatal((
1588                            inst,
1589                            self.context(inst),
1590                            format!("`exnN` block argument used outside normal-return target of `try_call`"),
1591                        ))?;
1592                        unreachable!()
1593                    }
1594                    _ => unreachable!(),
1595                }
1596            }
1597        }
1598    }
1599
1600    fn typecheck_variable_args_iterator(
1601        &self,
1602        inst: Inst,
1603        iter: impl ExactSizeIterator<Item = Type>,
1604        variable_args: &[Value],
1605        errors: &mut VerifierErrors,
1606    ) -> VerifierStepResult {
1607        let mut i = 0;
1608
1609        for expected_type in iter {
1610            if i >= variable_args.len() {
1611                // Result count mismatch handled below, we want the full argument count first though
1612                i += 1;
1613                continue;
1614            }
1615            let arg = variable_args[i];
1616            let arg_type = self.func.dfg.value_type(arg);
1617            if expected_type != arg_type {
1618                errors.report((
1619                    inst,
1620                    self.context(inst),
1621                    format!(
1622                        "arg {} ({}) has type {}, expected {}",
1623                        i, variable_args[i], arg_type, expected_type
1624                    ),
1625                ));
1626            }
1627            i += 1;
1628        }
1629        if i != variable_args.len() {
1630            return errors.nonfatal((
1631                inst,
1632                self.context(inst),
1633                format!(
1634                    "mismatched argument count for `{}`: got {}, expected {}",
1635                    self.func.dfg.display_inst(inst),
1636                    variable_args.len(),
1637                    i,
1638                ),
1639            ));
1640        }
1641        Ok(())
1642    }
1643
1644    fn typecheck_return(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult {
1645        match self.func.dfg.insts[inst] {
1646            ir::InstructionData::MultiAry {
1647                opcode: Opcode::Return,
1648                args,
1649            } => {
1650                let types = args
1651                    .as_slice(&self.func.dfg.value_lists)
1652                    .iter()
1653                    .map(|v| self.func.dfg.value_type(*v));
1654                self.typecheck_return_types(
1655                    inst,
1656                    types,
1657                    errors,
1658                    "arguments of return must match function signature",
1659                )?;
1660            }
1661            ir::InstructionData::Call {
1662                opcode: Opcode::ReturnCall,
1663                func_ref,
1664                ..
1665            } => {
1666                let sig_ref = self.func.dfg.ext_funcs[func_ref].signature;
1667                self.typecheck_tail_call(inst, sig_ref, errors)?;
1668            }
1669            ir::InstructionData::CallIndirect {
1670                opcode: Opcode::ReturnCallIndirect,
1671                sig_ref,
1672                ..
1673            } => {
1674                self.typecheck_tail_call(inst, sig_ref, errors)?;
1675            }
1676            inst => debug_assert!(!inst.opcode().is_return()),
1677        }
1678        Ok(())
1679    }
1680
1681    fn typecheck_tail_call(
1682        &self,
1683        inst: Inst,
1684        sig_ref: SigRef,
1685        errors: &mut VerifierErrors,
1686    ) -> VerifierStepResult {
1687        let signature = &self.func.dfg.signatures[sig_ref];
1688        let cc = signature.call_conv;
1689        if !cc.supports_tail_calls() {
1690            errors.report((
1691                inst,
1692                self.context(inst),
1693                format!("calling convention `{cc}` does not support tail calls"),
1694            ));
1695        }
1696        if cc != self.func.signature.call_conv {
1697            errors.report((
1698                inst,
1699                self.context(inst),
1700                "callee's calling convention must match caller",
1701            ));
1702        }
1703        let types = signature.returns.iter().map(|param| param.value_type);
1704        self.typecheck_return_types(inst, types, errors, "results of callee must match caller")?;
1705        Ok(())
1706    }
1707
1708    fn typecheck_return_types(
1709        &self,
1710        inst: Inst,
1711        actual_types: impl ExactSizeIterator<Item = Type>,
1712        errors: &mut VerifierErrors,
1713        message: &str,
1714    ) -> VerifierStepResult {
1715        let expected_types = &self.func.signature.returns;
1716        if actual_types.len() != expected_types.len() {
1717            return errors.nonfatal((inst, self.context(inst), message));
1718        }
1719        for (i, (actual_type, &expected_type)) in actual_types.zip(expected_types).enumerate() {
1720            if actual_type != expected_type.value_type {
1721                errors.report((
1722                    inst,
1723                    self.context(inst),
1724                    format!(
1725                        "result {i} has type {actual_type}, must match function signature of \
1726                         {expected_type}"
1727                    ),
1728                ));
1729            }
1730        }
1731        Ok(())
1732    }
1733
1734    // Check special-purpose type constraints that can't be expressed in the normal opcode
1735    // constraints.
1736    fn typecheck_special(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult {
1737        match self.func.dfg.insts[inst] {
1738            ir::InstructionData::UnaryGlobalValue { global_value, .. } => {
1739                if let Some(isa) = self.isa {
1740                    let inst_type = self.func.dfg.value_type(self.func.dfg.first_result(inst));
1741                    let global_type = self.func.global_values[global_value].global_type(isa);
1742                    if inst_type != global_type {
1743                        return errors.nonfatal((
1744                            inst, self.context(inst),
1745                            format!(
1746                                "global_value instruction with type {inst_type} references global value with type {global_type}"
1747                            )),
1748                        );
1749                    }
1750                }
1751            }
1752            _ => {}
1753        }
1754        Ok(())
1755    }
1756
1757    fn cfg_integrity(
1758        &self,
1759        cfg: &ControlFlowGraph,
1760        errors: &mut VerifierErrors,
1761    ) -> VerifierStepResult {
1762        let mut expected_succs = BTreeSet::<Block>::new();
1763        let mut got_succs = BTreeSet::<Block>::new();
1764        let mut expected_preds = BTreeSet::<Inst>::new();
1765        let mut got_preds = BTreeSet::<Inst>::new();
1766
1767        for block in self.func.layout.blocks() {
1768            expected_succs.extend(self.expected_cfg.succ_iter(block));
1769            got_succs.extend(cfg.succ_iter(block));
1770
1771            let missing_succs: Vec<Block> =
1772                expected_succs.difference(&got_succs).cloned().collect();
1773            if !missing_succs.is_empty() {
1774                errors.report((
1775                    block,
1776                    format!("cfg lacked the following successor(s) {missing_succs:?}"),
1777                ));
1778                continue;
1779            }
1780
1781            let excess_succs: Vec<Block> = got_succs.difference(&expected_succs).cloned().collect();
1782            if !excess_succs.is_empty() {
1783                errors.report((
1784                    block,
1785                    format!("cfg had unexpected successor(s) {excess_succs:?}"),
1786                ));
1787                continue;
1788            }
1789
1790            expected_preds.extend(
1791                self.expected_cfg
1792                    .pred_iter(block)
1793                    .map(|BlockPredecessor { inst, .. }| inst),
1794            );
1795            got_preds.extend(
1796                cfg.pred_iter(block)
1797                    .map(|BlockPredecessor { inst, .. }| inst),
1798            );
1799
1800            let missing_preds: Vec<Inst> = expected_preds.difference(&got_preds).cloned().collect();
1801            if !missing_preds.is_empty() {
1802                errors.report((
1803                    block,
1804                    format!("cfg lacked the following predecessor(s) {missing_preds:?}"),
1805                ));
1806                continue;
1807            }
1808
1809            let excess_preds: Vec<Inst> = got_preds.difference(&expected_preds).cloned().collect();
1810            if !excess_preds.is_empty() {
1811                errors.report((
1812                    block,
1813                    format!("cfg had unexpected predecessor(s) {excess_preds:?}"),
1814                ));
1815                continue;
1816            }
1817
1818            expected_succs.clear();
1819            got_succs.clear();
1820            expected_preds.clear();
1821            got_preds.clear();
1822        }
1823        errors.as_result()
1824    }
1825
1826    fn immediate_constraints(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult {
1827        let inst_data = &self.func.dfg.insts[inst];
1828
1829        match *inst_data {
1830            ir::InstructionData::Store { flags, .. } => {
1831                if flags.readonly() {
1832                    errors.fatal((
1833                        inst,
1834                        self.context(inst),
1835                        "A store instruction cannot have the `readonly` MemFlag",
1836                    ))
1837                } else {
1838                    Ok(())
1839                }
1840            }
1841            ir::InstructionData::BinaryImm8 {
1842                opcode: ir::instructions::Opcode::Extractlane,
1843                imm: lane,
1844                arg,
1845                ..
1846            }
1847            | ir::InstructionData::TernaryImm8 {
1848                opcode: ir::instructions::Opcode::Insertlane,
1849                imm: lane,
1850                args: [arg, _],
1851                ..
1852            } => {
1853                // We must be specific about the opcodes above because other instructions are using
1854                // the same formats.
1855                let ty = self.func.dfg.value_type(arg);
1856                if lane as u32 >= ty.lane_count() {
1857                    errors.fatal((
1858                        inst,
1859                        self.context(inst),
1860                        format!("The lane {lane} does not index into the type {ty}",),
1861                    ))
1862                } else {
1863                    Ok(())
1864                }
1865            }
1866            ir::InstructionData::Shuffle {
1867                opcode: ir::instructions::Opcode::Shuffle,
1868                imm,
1869                ..
1870            } => {
1871                let imm = self.func.dfg.immediates.get(imm).unwrap().as_slice();
1872                if imm.len() != 16 {
1873                    errors.fatal((
1874                        inst,
1875                        self.context(inst),
1876                        format!("the shuffle immediate wasn't 16-bytes long"),
1877                    ))
1878                } else if let Some(i) = imm.iter().find(|i| **i >= 32) {
1879                    errors.fatal((
1880                        inst,
1881                        self.context(inst),
1882                        format!("shuffle immediate index {i} is larger than the maximum 31"),
1883                    ))
1884                } else {
1885                    Ok(())
1886                }
1887            }
1888            _ => Ok(()),
1889        }
1890    }
1891
1892    fn iconst_bounds(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult {
1893        use crate::ir::instructions::InstructionData::UnaryImm;
1894
1895        let inst_data = &self.func.dfg.insts[inst];
1896        if let UnaryImm {
1897            opcode: Opcode::Iconst,
1898            imm,
1899        } = inst_data
1900        {
1901            let ctrl_typevar = self.func.dfg.ctrl_typevar(inst);
1902            let bounds_mask = match ctrl_typevar {
1903                types::I8 => u8::MAX.into(),
1904                types::I16 => u16::MAX.into(),
1905                types::I32 => u32::MAX.into(),
1906                types::I64 => u64::MAX,
1907                _ => unreachable!(),
1908            };
1909
1910            let value = imm.bits() as u64;
1911            if value & bounds_mask != value {
1912                errors.fatal((
1913                    inst,
1914                    self.context(inst),
1915                    "constant immediate is out of bounds",
1916                ))
1917            } else {
1918                Ok(())
1919            }
1920        } else {
1921            Ok(())
1922        }
1923    }
1924
1925    fn typecheck_function_signature(&self, errors: &mut VerifierErrors) -> VerifierStepResult {
1926        let params = self
1927            .func
1928            .signature
1929            .params
1930            .iter()
1931            .enumerate()
1932            .map(|p| (true, p));
1933        let returns = self
1934            .func
1935            .signature
1936            .returns
1937            .iter()
1938            .enumerate()
1939            .map(|p| (false, p));
1940
1941        for (is_argument, (i, param)) in params.chain(returns) {
1942            let is_return = !is_argument;
1943            let item = if is_argument {
1944                "Parameter"
1945            } else {
1946                "Return value"
1947            };
1948
1949            if param.value_type == types::INVALID {
1950                errors.report((
1951                    AnyEntity::Function,
1952                    format!("{item} at position {i} has an invalid type"),
1953                ));
1954            }
1955
1956            if let ArgumentPurpose::StructArgument(_) = param.purpose {
1957                if is_return {
1958                    errors.report((
1959                        AnyEntity::Function,
1960                        format!("{item} at position {i} can't be an struct argument"),
1961                    ))
1962                }
1963            }
1964
1965            let ty_allows_extension = param.value_type.is_int();
1966            let has_extension = param.extension != ArgumentExtension::None;
1967            if !ty_allows_extension && has_extension {
1968                errors.report((
1969                    AnyEntity::Function,
1970                    format!(
1971                        "{} at position {} has invalid extension {:?}",
1972                        item, i, param.extension
1973                    ),
1974                ));
1975            }
1976        }
1977
1978        if errors.has_error() { Err(()) } else { Ok(()) }
1979    }
1980
1981    pub fn run(&self, errors: &mut VerifierErrors) -> VerifierStepResult {
1982        self.verify_global_values(errors)?;
1983        self.verify_memory_types(errors)?;
1984        self.typecheck_entry_block_params(errors)?;
1985        self.check_entry_not_cold(errors)?;
1986        self.typecheck_function_signature(errors)?;
1987
1988        for block in self.func.layout.blocks() {
1989            if self.func.layout.first_inst(block).is_none() {
1990                return errors.fatal((block, format!("{block} cannot be empty")));
1991            }
1992            for inst in self.func.layout.block_insts(block) {
1993                crate::trace!("verifying {inst:?}: {}", self.func.dfg.display_inst(inst));
1994                self.block_integrity(block, inst, errors)?;
1995                self.instruction_integrity(inst, errors)?;
1996                self.typecheck(inst, errors)?;
1997                self.immediate_constraints(inst, errors)?;
1998                self.iconst_bounds(inst, errors)?;
1999            }
2000
2001            self.encodable_as_bb(block, errors)?;
2002        }
2003
2004        if !errors.is_empty() {
2005            log::warn!(
2006                "Found verifier errors in function:\n{}",
2007                pretty_verifier_error(self.func, None, errors.clone())
2008            );
2009        }
2010
2011        Ok(())
2012    }
2013}
2014
2015#[cfg(test)]
2016mod tests {
2017    use super::{Verifier, VerifierError, VerifierErrors};
2018    use crate::ir::instructions::{InstructionData, Opcode};
2019    use crate::ir::{AbiParam, Function, Type, types};
2020    use crate::settings;
2021
2022    macro_rules! assert_err_with_msg {
2023        ($e:expr, $msg:expr) => {
2024            match $e.0.get(0) {
2025                None => panic!("Expected an error"),
2026                Some(&VerifierError { ref message, .. }) => {
2027                    if !message.contains($msg) {
2028                        #[cfg(feature = "std")]
2029                        panic!("'{}' did not contain the substring '{}'", message, $msg);
2030                        #[cfg(not(feature = "std"))]
2031                        panic!("error message did not contain the expected substring");
2032                    }
2033                }
2034            }
2035        };
2036    }
2037
2038    #[test]
2039    fn empty() {
2040        let func = Function::new();
2041        let flags = &settings::Flags::new(settings::builder());
2042        let verifier = Verifier::new(&func, flags.into());
2043        let mut errors = VerifierErrors::default();
2044
2045        assert_eq!(verifier.run(&mut errors), Ok(()));
2046        assert!(errors.0.is_empty());
2047    }
2048
2049    #[test]
2050    fn bad_instruction_format() {
2051        let mut func = Function::new();
2052        let block0 = func.dfg.make_block();
2053        func.layout.append_block(block0);
2054        let nullary_with_bad_opcode = func.dfg.make_inst(InstructionData::UnaryImm {
2055            opcode: Opcode::F32const,
2056            imm: 0.into(),
2057        });
2058        func.layout.append_inst(nullary_with_bad_opcode, block0);
2059        let destination = func.dfg.block_call(block0, &[]);
2060        func.stencil.layout.append_inst(
2061            func.stencil.dfg.make_inst(InstructionData::Jump {
2062                opcode: Opcode::Jump,
2063                destination,
2064            }),
2065            block0,
2066        );
2067        let flags = &settings::Flags::new(settings::builder());
2068        let verifier = Verifier::new(&func, flags.into());
2069        let mut errors = VerifierErrors::default();
2070
2071        let _ = verifier.run(&mut errors);
2072
2073        assert_err_with_msg!(errors, "instruction format");
2074    }
2075
2076    fn test_iconst_bounds(immediate: i64, ctrl_typevar: Type) -> VerifierErrors {
2077        let mut func = Function::new();
2078        let block0 = func.dfg.make_block();
2079        func.layout.append_block(block0);
2080
2081        let test_inst = func.dfg.make_inst(InstructionData::UnaryImm {
2082            opcode: Opcode::Iconst,
2083            imm: immediate.into(),
2084        });
2085
2086        let end_inst = func.dfg.make_inst(InstructionData::MultiAry {
2087            opcode: Opcode::Return,
2088            args: Default::default(),
2089        });
2090
2091        func.dfg.make_inst_results(test_inst, ctrl_typevar);
2092        func.layout.append_inst(test_inst, block0);
2093        func.layout.append_inst(end_inst, block0);
2094
2095        let flags = &settings::Flags::new(settings::builder());
2096        let verifier = Verifier::new(&func, flags.into());
2097        let mut errors = VerifierErrors::default();
2098
2099        let _ = verifier.run(&mut errors);
2100        errors
2101    }
2102
2103    fn test_iconst_bounds_err(immediate: i64, ctrl_typevar: Type) {
2104        assert_err_with_msg!(
2105            test_iconst_bounds(immediate, ctrl_typevar),
2106            "constant immediate is out of bounds"
2107        );
2108    }
2109
2110    fn test_iconst_bounds_ok(immediate: i64, ctrl_typevar: Type) {
2111        assert!(test_iconst_bounds(immediate, ctrl_typevar).is_empty());
2112    }
2113
2114    #[test]
2115    fn negative_iconst_8() {
2116        test_iconst_bounds_err(-10, types::I8);
2117    }
2118
2119    #[test]
2120    fn negative_iconst_32() {
2121        test_iconst_bounds_err(-1, types::I32);
2122    }
2123
2124    #[test]
2125    fn large_iconst_8() {
2126        test_iconst_bounds_err(1 + u8::MAX as i64, types::I8);
2127    }
2128
2129    #[test]
2130    fn large_iconst_16() {
2131        test_iconst_bounds_err(10 + u16::MAX as i64, types::I16);
2132    }
2133
2134    #[test]
2135    fn valid_iconst_8() {
2136        test_iconst_bounds_ok(10, types::I8);
2137    }
2138
2139    #[test]
2140    fn valid_iconst_32() {
2141        test_iconst_bounds_ok(u32::MAX as i64, types::I32);
2142    }
2143
2144    #[test]
2145    fn test_function_invalid_param() {
2146        let mut func = Function::new();
2147        func.signature.params.push(AbiParam::new(types::INVALID));
2148
2149        let mut errors = VerifierErrors::default();
2150        let flags = &settings::Flags::new(settings::builder());
2151        let verifier = Verifier::new(&func, flags.into());
2152
2153        let _ = verifier.typecheck_function_signature(&mut errors);
2154        assert_err_with_msg!(errors, "Parameter at position 0 has an invalid type");
2155    }
2156
2157    #[test]
2158    fn test_function_invalid_return_value() {
2159        let mut func = Function::new();
2160        func.signature.returns.push(AbiParam::new(types::INVALID));
2161
2162        let mut errors = VerifierErrors::default();
2163        let flags = &settings::Flags::new(settings::builder());
2164        let verifier = Verifier::new(&func, flags.into());
2165
2166        let _ = verifier.typecheck_function_signature(&mut errors);
2167        assert_err_with_msg!(errors, "Return value at position 0 has an invalid type");
2168    }
2169
2170    #[test]
2171    fn test_printing_contextual_errors() {
2172        // Build function.
2173        let mut func = Function::new();
2174        let block0 = func.dfg.make_block();
2175        func.layout.append_block(block0);
2176
2177        // Build instruction "f64const 0.0" (missing one required result)
2178        let inst = func.dfg.make_inst(InstructionData::UnaryIeee64 {
2179            opcode: Opcode::F64const,
2180            imm: 0.0.into(),
2181        });
2182        func.layout.append_inst(inst, block0);
2183
2184        // Setup verifier.
2185        let mut errors = VerifierErrors::default();
2186        let flags = &settings::Flags::new(settings::builder());
2187        let verifier = Verifier::new(&func, flags.into());
2188
2189        // Now the error message, when printed, should contain the instruction sequence causing the
2190        // error (i.e. f64const 0.0) and not only its entity value (i.e. inst0)
2191        let _ = verifier.typecheck_results(inst, types::I32, &mut errors);
2192        assert_eq!(
2193            format!("{}", errors.0[0]),
2194            "inst0 (f64const 0.0): has fewer result values than expected"
2195        )
2196    }
2197
2198    #[test]
2199    fn test_empty_block() {
2200        let mut func = Function::new();
2201        let block0 = func.dfg.make_block();
2202        func.layout.append_block(block0);
2203
2204        let flags = &settings::Flags::new(settings::builder());
2205        let verifier = Verifier::new(&func, flags.into());
2206        let mut errors = VerifierErrors::default();
2207        let _ = verifier.run(&mut errors);
2208
2209        assert_err_with_msg!(errors, "block0 cannot be empty");
2210    }
2211}