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 //! TODO: 51 //! Ad hoc checking 52 //! 53 //! - Stack slot loads and stores must be in-bounds. 54 //! - Immediate constraints for certain opcodes, like `udiv_imm v3, 0`. 55 //! - `Insertlane` and `extractlane` instructions have immediate lane numbers that must be in 56 //! range for their polymorphic type. 57 //! - Swizzle and shuffle instructions take a variable number of lane arguments. The number 58 //! of arguments must match the destination type, and the lane indexes must be in range. 59 60 use crate::dbg::DisplayList; 61 use crate::dominator_tree::DominatorTree; 62 use crate::entity::SparseSet; 63 use crate::flowgraph::{BlockPredecessor, ControlFlowGraph}; 64 use crate::ir; 65 use crate::ir::entities::AnyEntity; 66 use crate::ir::instructions::{BranchInfo, CallInfo, InstructionFormat, ResolvedConstraint}; 67 use crate::ir::{ 68 types, ArgumentPurpose, Block, Constant, DynamicStackSlot, FuncRef, Function, GlobalValue, 69 Inst, JumpTable, MemFlags, Opcode, SigRef, StackSlot, Type, Value, ValueDef, ValueList, 70 }; 71 use crate::isa::TargetIsa; 72 use crate::iterators::IteratorExtras; 73 use crate::print_errors::pretty_verifier_error; 74 use crate::settings::FlagsOrIsa; 75 use crate::timing; 76 use alloc::collections::BTreeSet; 77 use alloc::string::{String, ToString}; 78 use alloc::vec::Vec; 79 use core::cmp::Ordering; 80 use core::fmt::{self, Display, Formatter}; 81 82 /// A verifier error. 83 #[derive(Debug, PartialEq, Eq, Clone)] 84 pub struct VerifierError { 85 /// The entity causing the verifier error. 86 pub location: AnyEntity, 87 /// Optionally provide some context for the given location; e.g., for `inst42` provide 88 /// `Some("v3 = iconst.i32 0")` for more comprehensible errors. 89 pub context: Option<String>, 90 /// The error message. 91 pub message: String, 92 } 93 94 // This is manually implementing Error and Display instead of using thiserror to reduce the amount 95 // of dependencies used by Cranelift. 96 impl std::error::Error for VerifierError {} 97 98 impl Display for VerifierError { 99 fn fmt(&self, f: &mut Formatter) -> fmt::Result { 100 match &self.context { 101 None => write!(f, "{}: {}", self.location, self.message), 102 Some(context) => write!(f, "{} ({}): {}", self.location, context, self.message), 103 } 104 } 105 } 106 107 /// Convenience converter for making error-reporting less verbose. 108 /// 109 /// Converts a tuple of `(location, context, message)` to a `VerifierError`. 110 /// ``` 111 /// use cranelift_codegen::verifier::VerifierErrors; 112 /// use cranelift_codegen::ir::Inst; 113 /// let mut errors = VerifierErrors::new(); 114 /// errors.report((Inst::from_u32(42), "v3 = iadd v1, v2", "iadd cannot be used with values of this type")); 115 /// // note the double parenthenses to use this syntax 116 /// ``` 117 impl<L, C, M> From<(L, C, M)> for VerifierError 118 where 119 L: Into<AnyEntity>, 120 C: Into<String>, 121 M: Into<String>, 122 { 123 fn from(items: (L, C, M)) -> Self { 124 let (location, context, message) = items; 125 Self { 126 location: location.into(), 127 context: Some(context.into()), 128 message: message.into(), 129 } 130 } 131 } 132 133 /// Convenience converter for making error-reporting less verbose. 134 /// 135 /// Same as above but without `context`. 136 impl<L, M> From<(L, M)> for VerifierError 137 where 138 L: Into<AnyEntity>, 139 M: Into<String>, 140 { 141 fn from(items: (L, M)) -> Self { 142 let (location, message) = items; 143 Self { 144 location: location.into(), 145 context: None, 146 message: message.into(), 147 } 148 } 149 } 150 151 /// Result of a step in the verification process. 152 /// 153 /// Functions that return `VerifierStepResult<()>` should also take a 154 /// mutable reference to `VerifierErrors` as argument in order to report 155 /// errors. 156 /// 157 /// Here, `Ok` represents a step that **did not lead to a fatal error**, 158 /// meaning that the verification process may continue. However, other (non-fatal) 159 /// errors might have been reported through the previously mentioned `VerifierErrors` 160 /// argument. 161 pub type VerifierStepResult<T> = Result<T, ()>; 162 163 /// Result of a verification operation. 164 /// 165 /// Unlike `VerifierStepResult<()>` which may be `Ok` while still having reported 166 /// errors, this type always returns `Err` if an error (fatal or not) was reported. 167 pub type VerifierResult<T> = Result<T, VerifierErrors>; 168 169 /// List of verifier errors. 170 #[derive(Debug, Default, PartialEq, Eq, Clone)] 171 pub struct VerifierErrors(pub Vec<VerifierError>); 172 173 // This is manually implementing Error and Display instead of using thiserror to reduce the amount 174 // of dependencies used by Cranelift. 175 impl std::error::Error for VerifierErrors {} 176 177 impl VerifierErrors { 178 /// Return a new `VerifierErrors` struct. 179 #[inline] 180 pub fn new() -> Self { 181 Self(Vec::new()) 182 } 183 184 /// Return whether no errors were reported. 185 #[inline] 186 pub fn is_empty(&self) -> bool { 187 self.0.is_empty() 188 } 189 190 /// Return whether one or more errors were reported. 191 #[inline] 192 pub fn has_error(&self) -> bool { 193 !self.0.is_empty() 194 } 195 196 /// Return a `VerifierStepResult` that is fatal if at least one error was reported, 197 /// and non-fatal otherwise. 198 #[inline] 199 pub fn as_result(&self) -> VerifierStepResult<()> { 200 if self.is_empty() { 201 Ok(()) 202 } else { 203 Err(()) 204 } 205 } 206 207 /// Report an error, adding it to the list of errors. 208 pub fn report(&mut self, error: impl Into<VerifierError>) { 209 self.0.push(error.into()); 210 } 211 212 /// Report a fatal error and return `Err`. 213 pub fn fatal(&mut self, error: impl Into<VerifierError>) -> VerifierStepResult<()> { 214 self.report(error); 215 Err(()) 216 } 217 218 /// Report a non-fatal error and return `Ok`. 219 pub fn nonfatal(&mut self, error: impl Into<VerifierError>) -> VerifierStepResult<()> { 220 self.report(error); 221 Ok(()) 222 } 223 } 224 225 impl From<Vec<VerifierError>> for VerifierErrors { 226 fn from(v: Vec<VerifierError>) -> Self { 227 Self(v) 228 } 229 } 230 231 impl Into<Vec<VerifierError>> for VerifierErrors { 232 fn into(self) -> Vec<VerifierError> { 233 self.0 234 } 235 } 236 237 impl Into<VerifierResult<()>> for VerifierErrors { 238 fn into(self) -> VerifierResult<()> { 239 if self.is_empty() { 240 Ok(()) 241 } else { 242 Err(self) 243 } 244 } 245 } 246 247 impl Display for VerifierErrors { 248 fn fmt(&self, f: &mut Formatter) -> fmt::Result { 249 for err in &self.0 { 250 writeln!(f, "- {}", err)?; 251 } 252 Ok(()) 253 } 254 } 255 256 /// Verify `func`. 257 pub fn verify_function<'a, FOI: Into<FlagsOrIsa<'a>>>( 258 func: &Function, 259 fisa: FOI, 260 ) -> VerifierResult<()> { 261 let _tt = timing::verifier(); 262 let mut errors = VerifierErrors::default(); 263 let verifier = Verifier::new(func, fisa.into()); 264 let result = verifier.run(&mut errors); 265 if errors.is_empty() { 266 result.unwrap(); 267 Ok(()) 268 } else { 269 Err(errors) 270 } 271 } 272 273 /// Verify `func` after checking the integrity of associated context data structures `cfg` and 274 /// `domtree`. 275 pub fn verify_context<'a, FOI: Into<FlagsOrIsa<'a>>>( 276 func: &Function, 277 cfg: &ControlFlowGraph, 278 domtree: &DominatorTree, 279 fisa: FOI, 280 errors: &mut VerifierErrors, 281 ) -> VerifierStepResult<()> { 282 let _tt = timing::verifier(); 283 let verifier = Verifier::new(func, fisa.into()); 284 if cfg.is_valid() { 285 verifier.cfg_integrity(cfg, errors)?; 286 } 287 if domtree.is_valid() { 288 verifier.domtree_integrity(domtree, errors)?; 289 } 290 verifier.run(errors) 291 } 292 293 struct Verifier<'a> { 294 func: &'a Function, 295 expected_cfg: ControlFlowGraph, 296 expected_domtree: DominatorTree, 297 isa: Option<&'a dyn TargetIsa>, 298 } 299 300 impl<'a> Verifier<'a> { 301 pub fn new(func: &'a Function, fisa: FlagsOrIsa<'a>) -> Self { 302 let expected_cfg = ControlFlowGraph::with_function(func); 303 let expected_domtree = DominatorTree::with_function(func, &expected_cfg); 304 Self { 305 func, 306 expected_cfg, 307 expected_domtree, 308 isa: fisa.isa, 309 } 310 } 311 312 /// Determine a contextual error string for an instruction. 313 #[inline] 314 fn context(&self, inst: Inst) -> String { 315 self.func.dfg.display_inst(inst).to_string() 316 } 317 318 // Check for: 319 // - cycles in the global value declarations. 320 // - use of 'vmctx' when no special parameter declares it. 321 fn verify_global_values(&self, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 322 let mut cycle_seen = false; 323 let mut seen = SparseSet::new(); 324 325 'gvs: for gv in self.func.global_values.keys() { 326 seen.clear(); 327 seen.insert(gv); 328 329 let mut cur = gv; 330 loop { 331 match self.func.global_values[cur] { 332 ir::GlobalValueData::Load { base, .. } 333 | ir::GlobalValueData::IAddImm { base, .. } => { 334 if seen.insert(base).is_some() { 335 if !cycle_seen { 336 errors.report(( 337 gv, 338 format!("global value cycle: {}", DisplayList(seen.as_slice())), 339 )); 340 // ensures we don't report the cycle multiple times 341 cycle_seen = true; 342 } 343 continue 'gvs; 344 } 345 346 cur = base; 347 } 348 _ => break, 349 } 350 } 351 352 match self.func.global_values[gv] { 353 ir::GlobalValueData::VMContext { .. } => { 354 if self 355 .func 356 .special_param(ir::ArgumentPurpose::VMContext) 357 .is_none() 358 { 359 errors.report((gv, format!("undeclared vmctx reference {}", gv))); 360 } 361 } 362 ir::GlobalValueData::IAddImm { 363 base, global_type, .. 364 } => { 365 if !global_type.is_int() { 366 errors.report(( 367 gv, 368 format!("iadd_imm global value with non-int type {}", global_type), 369 )); 370 } else if let Some(isa) = self.isa { 371 let base_type = self.func.global_values[base].global_type(isa); 372 if global_type != base_type { 373 errors.report(( 374 gv, 375 format!( 376 "iadd_imm type {} differs from operand type {}", 377 global_type, base_type 378 ), 379 )); 380 } 381 } 382 } 383 ir::GlobalValueData::Load { base, .. } => { 384 if let Some(isa) = self.isa { 385 let base_type = self.func.global_values[base].global_type(isa); 386 let pointer_type = isa.pointer_type(); 387 if base_type != pointer_type { 388 errors.report(( 389 gv, 390 format!( 391 "base {} has type {}, which is not the pointer type {}", 392 base, base_type, pointer_type 393 ), 394 )); 395 } 396 } 397 } 398 _ => {} 399 } 400 } 401 402 // Invalid global values shouldn't stop us from verifying the rest of the function 403 Ok(()) 404 } 405 406 fn verify_tables(&self, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 407 if let Some(isa) = self.isa { 408 for (table, table_data) in &self.func.tables { 409 let base = table_data.base_gv; 410 if !self.func.global_values.is_valid(base) { 411 return errors.nonfatal((table, format!("invalid base global value {}", base))); 412 } 413 414 let pointer_type = isa.pointer_type(); 415 let base_type = self.func.global_values[base].global_type(isa); 416 if base_type != pointer_type { 417 errors.report(( 418 table, 419 format!( 420 "table base has type {}, which is not the pointer type {}", 421 base_type, pointer_type 422 ), 423 )); 424 } 425 426 let bound_gv = table_data.bound_gv; 427 if !self.func.global_values.is_valid(bound_gv) { 428 return errors 429 .nonfatal((table, format!("invalid bound global value {}", bound_gv))); 430 } 431 432 let index_type = table_data.index_type; 433 let bound_type = self.func.global_values[bound_gv].global_type(isa); 434 if index_type != bound_type { 435 errors.report(( 436 table, 437 format!( 438 "table index type {} differs from the type of its bound, {}", 439 index_type, bound_type 440 ), 441 )); 442 } 443 } 444 } 445 446 Ok(()) 447 } 448 449 fn verify_jump_tables(&self, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 450 for (jt, jt_data) in &self.func.jump_tables { 451 for &block in jt_data.iter() { 452 self.verify_block(jt, block, errors)?; 453 } 454 } 455 Ok(()) 456 } 457 458 /// Check that the given block can be encoded as a BB, by checking that only 459 /// branching instructions are ending the block. 460 fn encodable_as_bb(&self, block: Block, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 461 match self.func.is_block_basic(block) { 462 Ok(()) => Ok(()), 463 Err((inst, message)) => errors.fatal((inst, self.context(inst), message)), 464 } 465 } 466 467 fn block_integrity( 468 &self, 469 block: Block, 470 inst: Inst, 471 errors: &mut VerifierErrors, 472 ) -> VerifierStepResult<()> { 473 let is_terminator = self.func.dfg.insts[inst].opcode().is_terminator(); 474 let is_last_inst = self.func.layout.last_inst(block) == Some(inst); 475 476 if is_terminator && !is_last_inst { 477 // Terminating instructions only occur at the end of blocks. 478 return errors.fatal(( 479 inst, 480 self.context(inst), 481 format!( 482 "a terminator instruction was encountered before the end of {}", 483 block 484 ), 485 )); 486 } 487 if is_last_inst && !is_terminator { 488 return errors.fatal((block, "block does not end in a terminator instruction")); 489 } 490 491 // Instructions belong to the correct block. 492 let inst_block = self.func.layout.inst_block(inst); 493 if inst_block != Some(block) { 494 return errors.fatal(( 495 inst, 496 self.context(inst), 497 format!("should belong to {} not {:?}", block, inst_block), 498 )); 499 } 500 501 // Parameters belong to the correct block. 502 for &arg in self.func.dfg.block_params(block) { 503 match self.func.dfg.value_def(arg) { 504 ValueDef::Param(arg_block, _) => { 505 if block != arg_block { 506 return errors.fatal((arg, format!("does not belong to {}", block))); 507 } 508 } 509 _ => { 510 return errors.fatal((arg, "expected an argument, found a result")); 511 } 512 } 513 } 514 515 Ok(()) 516 } 517 518 fn instruction_integrity( 519 &self, 520 inst: Inst, 521 errors: &mut VerifierErrors, 522 ) -> 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 num_fixed_results = inst_data.opcode().constraints().num_fixed_results(); 536 // var_results is 0 if we aren't a call instruction 537 let var_results = dfg 538 .call_signature(inst) 539 .map_or(0, |sig| dfg.signatures[sig].returns.len()); 540 let total_results = num_fixed_results + var_results; 541 542 // All result values for multi-valued instructions are created 543 let got_results = dfg.inst_results(inst).len(); 544 if got_results != total_results { 545 return errors.fatal(( 546 inst, 547 self.context(inst), 548 format!( 549 "expected {} result values, found {}", 550 total_results, got_results, 551 ), 552 )); 553 } 554 555 self.verify_entity_references(inst, errors) 556 } 557 558 fn verify_entity_references( 559 &self, 560 inst: Inst, 561 errors: &mut VerifierErrors, 562 ) -> VerifierStepResult<()> { 563 use crate::ir::instructions::InstructionData::*; 564 565 for &arg in self.func.dfg.inst_args(inst) { 566 self.verify_inst_arg(inst, arg, errors)?; 567 568 // All used values must be attached to something. 569 let original = self.func.dfg.resolve_aliases(arg); 570 if !self.func.dfg.value_is_attached(original) { 571 errors.report(( 572 inst, 573 self.context(inst), 574 format!("argument {} -> {} is not attached", arg, original), 575 )); 576 } 577 } 578 579 for &res in self.func.dfg.inst_results(inst) { 580 self.verify_inst_result(inst, res, errors)?; 581 } 582 583 match self.func.dfg.insts[inst] { 584 MultiAry { ref args, .. } => { 585 self.verify_value_list(inst, args, errors)?; 586 } 587 Jump { 588 destination, 589 ref args, 590 .. 591 } 592 | Branch { 593 destination, 594 ref args, 595 .. 596 } => { 597 self.verify_block(inst, destination, errors)?; 598 self.verify_value_list(inst, args, errors)?; 599 } 600 BranchTable { 601 table, destination, .. 602 } => { 603 self.verify_block(inst, destination, errors)?; 604 self.verify_jump_table(inst, table, errors)?; 605 } 606 Call { 607 func_ref, ref args, .. 608 } => { 609 self.verify_func_ref(inst, func_ref, errors)?; 610 self.verify_value_list(inst, args, errors)?; 611 } 612 CallIndirect { 613 sig_ref, ref args, .. 614 } => { 615 self.verify_sig_ref(inst, sig_ref, errors)?; 616 self.verify_value_list(inst, args, errors)?; 617 } 618 FuncAddr { func_ref, .. } => { 619 self.verify_func_ref(inst, func_ref, errors)?; 620 } 621 StackLoad { stack_slot, .. } | StackStore { stack_slot, .. } => { 622 self.verify_stack_slot(inst, stack_slot, errors)?; 623 } 624 DynamicStackLoad { 625 dynamic_stack_slot, .. 626 } 627 | DynamicStackStore { 628 dynamic_stack_slot, .. 629 } => { 630 self.verify_dynamic_stack_slot(inst, dynamic_stack_slot, errors)?; 631 } 632 UnaryGlobalValue { global_value, .. } => { 633 self.verify_global_value(inst, global_value, errors)?; 634 } 635 TableAddr { table, .. } => { 636 self.verify_table(inst, table, errors)?; 637 } 638 NullAry { 639 opcode: Opcode::GetPinnedReg, 640 } 641 | Unary { 642 opcode: Opcode::SetPinnedReg, 643 .. 644 } => { 645 if let Some(isa) = &self.isa { 646 if !isa.flags().enable_pinned_reg() { 647 return errors.fatal(( 648 inst, 649 self.context(inst), 650 "GetPinnedReg/SetPinnedReg cannot be used without enable_pinned_reg", 651 )); 652 } 653 } else { 654 return errors.fatal(( 655 inst, 656 self.context(inst), 657 "GetPinnedReg/SetPinnedReg need an ISA!", 658 )); 659 } 660 } 661 NullAry { 662 opcode: Opcode::GetFramePointer | Opcode::GetReturnAddress, 663 } => { 664 if let Some(isa) = &self.isa { 665 // Backends may already rely on this check implicitly, so do 666 // not relax it without verifying that it is safe to do so. 667 if !isa.flags().preserve_frame_pointers() { 668 return errors.fatal(( 669 inst, 670 self.context(inst), 671 "`get_frame_pointer`/`get_return_address` cannot be used without \ 672 enabling `preserve_frame_pointers`", 673 )); 674 } 675 } else { 676 return errors.fatal(( 677 inst, 678 self.context(inst), 679 "`get_frame_pointer`/`get_return_address` require an ISA!", 680 )); 681 } 682 } 683 LoadNoOffset { 684 opcode: Opcode::Bitcast, 685 flags, 686 arg, 687 } => { 688 self.verify_bitcast(inst, flags, arg, errors)?; 689 } 690 UnaryConst { 691 opcode: Opcode::Vconst, 692 constant_handle, 693 .. 694 } => { 695 self.verify_constant_size(inst, constant_handle, errors)?; 696 } 697 698 // Exhaustive list so we can't forget to add new formats 699 AtomicCas { .. } 700 | AtomicRmw { .. } 701 | LoadNoOffset { .. } 702 | StoreNoOffset { .. } 703 | Unary { .. } 704 | UnaryConst { .. } 705 | UnaryImm { .. } 706 | UnaryIeee32 { .. } 707 | UnaryIeee64 { .. } 708 | Binary { .. } 709 | BinaryImm8 { .. } 710 | BinaryImm64 { .. } 711 | Ternary { .. } 712 | TernaryImm8 { .. } 713 | Shuffle { .. } 714 | IntAddTrap { .. } 715 | IntCompare { .. } 716 | IntCompareImm { .. } 717 | FloatCompare { .. } 718 | Load { .. } 719 | Store { .. } 720 | Trap { .. } 721 | CondTrap { .. } 722 | NullAry { .. } => {} 723 } 724 725 Ok(()) 726 } 727 728 fn verify_block( 729 &self, 730 loc: impl Into<AnyEntity>, 731 e: Block, 732 errors: &mut VerifierErrors, 733 ) -> VerifierStepResult<()> { 734 if !self.func.dfg.block_is_valid(e) || !self.func.layout.is_block_inserted(e) { 735 return errors.fatal((loc, format!("invalid block reference {}", e))); 736 } 737 if let Some(entry_block) = self.func.layout.entry_block() { 738 if e == entry_block { 739 return errors.fatal((loc, format!("invalid reference to entry block {}", e))); 740 } 741 } 742 Ok(()) 743 } 744 745 fn verify_sig_ref( 746 &self, 747 inst: Inst, 748 s: SigRef, 749 errors: &mut VerifierErrors, 750 ) -> VerifierStepResult<()> { 751 if !self.func.dfg.signatures.is_valid(s) { 752 errors.fatal(( 753 inst, 754 self.context(inst), 755 format!("invalid signature reference {}", s), 756 )) 757 } else { 758 Ok(()) 759 } 760 } 761 762 fn verify_func_ref( 763 &self, 764 inst: Inst, 765 f: FuncRef, 766 errors: &mut VerifierErrors, 767 ) -> VerifierStepResult<()> { 768 if !self.func.dfg.ext_funcs.is_valid(f) { 769 errors.nonfatal(( 770 inst, 771 self.context(inst), 772 format!("invalid function reference {}", f), 773 )) 774 } else { 775 Ok(()) 776 } 777 } 778 779 fn verify_stack_slot( 780 &self, 781 inst: Inst, 782 ss: StackSlot, 783 errors: &mut VerifierErrors, 784 ) -> VerifierStepResult<()> { 785 if !self.func.sized_stack_slots.is_valid(ss) { 786 errors.nonfatal(( 787 inst, 788 self.context(inst), 789 format!("invalid stack slot {}", ss), 790 )) 791 } else { 792 Ok(()) 793 } 794 } 795 796 fn verify_dynamic_stack_slot( 797 &self, 798 inst: Inst, 799 ss: DynamicStackSlot, 800 errors: &mut VerifierErrors, 801 ) -> VerifierStepResult<()> { 802 if !self.func.dynamic_stack_slots.is_valid(ss) { 803 errors.nonfatal(( 804 inst, 805 self.context(inst), 806 format!("invalid dynamic stack slot {}", ss), 807 )) 808 } else { 809 Ok(()) 810 } 811 } 812 813 fn verify_global_value( 814 &self, 815 inst: Inst, 816 gv: GlobalValue, 817 errors: &mut VerifierErrors, 818 ) -> VerifierStepResult<()> { 819 if !self.func.global_values.is_valid(gv) { 820 errors.nonfatal(( 821 inst, 822 self.context(inst), 823 format!("invalid global value {}", gv), 824 )) 825 } else { 826 Ok(()) 827 } 828 } 829 830 fn verify_table( 831 &self, 832 inst: Inst, 833 table: ir::Table, 834 errors: &mut VerifierErrors, 835 ) -> VerifierStepResult<()> { 836 if !self.func.tables.is_valid(table) { 837 errors.nonfatal((inst, self.context(inst), format!("invalid table {}", table))) 838 } else { 839 Ok(()) 840 } 841 } 842 843 fn verify_value_list( 844 &self, 845 inst: Inst, 846 l: &ValueList, 847 errors: &mut VerifierErrors, 848 ) -> VerifierStepResult<()> { 849 if !l.is_valid(&self.func.dfg.value_lists) { 850 errors.nonfatal(( 851 inst, 852 self.context(inst), 853 format!("invalid value list reference {:?}", l), 854 )) 855 } else { 856 Ok(()) 857 } 858 } 859 860 fn verify_jump_table( 861 &self, 862 inst: Inst, 863 j: JumpTable, 864 errors: &mut VerifierErrors, 865 ) -> VerifierStepResult<()> { 866 if !self.func.jump_tables.is_valid(j) { 867 errors.nonfatal(( 868 inst, 869 self.context(inst), 870 format!("invalid jump table reference {}", j), 871 )) 872 } else { 873 Ok(()) 874 } 875 } 876 877 fn verify_value( 878 &self, 879 loc_inst: Inst, 880 v: Value, 881 errors: &mut VerifierErrors, 882 ) -> VerifierStepResult<()> { 883 let dfg = &self.func.dfg; 884 if !dfg.value_is_valid(v) { 885 errors.nonfatal(( 886 loc_inst, 887 self.context(loc_inst), 888 format!("invalid value reference {}", v), 889 )) 890 } else { 891 Ok(()) 892 } 893 } 894 895 fn verify_inst_arg( 896 &self, 897 loc_inst: Inst, 898 v: Value, 899 errors: &mut VerifierErrors, 900 ) -> VerifierStepResult<()> { 901 self.verify_value(loc_inst, v, errors)?; 902 903 let dfg = &self.func.dfg; 904 let loc_block = self.func.layout.pp_block(loc_inst); 905 let is_reachable = self.expected_domtree.is_reachable(loc_block); 906 907 // SSA form 908 match dfg.value_def(v) { 909 ValueDef::Result(def_inst, _) => { 910 // Value is defined by an instruction that exists. 911 if !dfg.inst_is_valid(def_inst) { 912 return errors.fatal(( 913 loc_inst, 914 self.context(loc_inst), 915 format!("{} is defined by invalid instruction {}", v, def_inst), 916 )); 917 } 918 // Defining instruction is inserted in a block. 919 if self.func.layout.inst_block(def_inst) == None { 920 return errors.fatal(( 921 loc_inst, 922 self.context(loc_inst), 923 format!("{} is defined by {} which has no block", v, def_inst), 924 )); 925 } 926 // Defining instruction dominates the instruction that uses the value. 927 if is_reachable { 928 if !self 929 .expected_domtree 930 .dominates(def_inst, loc_inst, &self.func.layout) 931 { 932 return errors.fatal(( 933 loc_inst, 934 self.context(loc_inst), 935 format!("uses value {} from non-dominating {}", v, def_inst), 936 )); 937 } 938 if def_inst == loc_inst { 939 return errors.fatal(( 940 loc_inst, 941 self.context(loc_inst), 942 format!("uses value {} from itself", v), 943 )); 944 } 945 } 946 } 947 ValueDef::Param(block, _) => { 948 // Value is defined by an existing block. 949 if !dfg.block_is_valid(block) { 950 return errors.fatal(( 951 loc_inst, 952 self.context(loc_inst), 953 format!("{} is defined by invalid block {}", v, block), 954 )); 955 } 956 // Defining block is inserted in the layout 957 if !self.func.layout.is_block_inserted(block) { 958 return errors.fatal(( 959 loc_inst, 960 self.context(loc_inst), 961 format!("{} is defined by {} which is not in the layout", v, block), 962 )); 963 } 964 // The defining block dominates the instruction using this value. 965 if is_reachable 966 && !self 967 .expected_domtree 968 .dominates(block, loc_inst, &self.func.layout) 969 { 970 return errors.fatal(( 971 loc_inst, 972 self.context(loc_inst), 973 format!("uses value arg from non-dominating {}", block), 974 )); 975 } 976 } 977 ValueDef::Union(_, _) => { 978 // Nothing: union nodes themselves have no location, 979 // so we cannot check any dominance properties. 980 } 981 } 982 Ok(()) 983 } 984 985 fn verify_inst_result( 986 &self, 987 loc_inst: Inst, 988 v: Value, 989 errors: &mut VerifierErrors, 990 ) -> VerifierStepResult<()> { 991 self.verify_value(loc_inst, v, errors)?; 992 993 match self.func.dfg.value_def(v) { 994 ValueDef::Result(def_inst, _) => { 995 if def_inst != loc_inst { 996 errors.fatal(( 997 loc_inst, 998 self.context(loc_inst), 999 format!("instruction result {} is not defined by the instruction", v), 1000 )) 1001 } else { 1002 Ok(()) 1003 } 1004 } 1005 ValueDef::Param(_, _) => errors.fatal(( 1006 loc_inst, 1007 self.context(loc_inst), 1008 format!("instruction result {} is not defined by the instruction", v), 1009 )), 1010 ValueDef::Union(_, _) => errors.fatal(( 1011 loc_inst, 1012 self.context(loc_inst), 1013 format!("instruction result {} is a union node", v), 1014 )), 1015 } 1016 } 1017 1018 fn verify_bitcast( 1019 &self, 1020 inst: Inst, 1021 flags: MemFlags, 1022 arg: Value, 1023 errors: &mut VerifierErrors, 1024 ) -> VerifierStepResult<()> { 1025 let typ = self.func.dfg.ctrl_typevar(inst); 1026 let value_type = self.func.dfg.value_type(arg); 1027 1028 if typ.bits() != value_type.bits() { 1029 errors.fatal(( 1030 inst, 1031 format!( 1032 "The bitcast argument {} has a type of {} bits, which doesn't match an expected type of {} bits", 1033 arg, 1034 value_type.bits(), 1035 typ.bits() 1036 ), 1037 )) 1038 } else if flags != MemFlags::new() 1039 && flags != MemFlags::new().with_endianness(ir::Endianness::Little) 1040 && flags != MemFlags::new().with_endianness(ir::Endianness::Big) 1041 { 1042 errors.fatal(( 1043 inst, 1044 "The bitcast instruction only accepts the `big` or `little` memory flags", 1045 )) 1046 } else if flags == MemFlags::new() && typ.lane_count() != value_type.lane_count() { 1047 errors.fatal(( 1048 inst, 1049 "Byte order specifier required for bitcast instruction changing lane count", 1050 )) 1051 } else { 1052 Ok(()) 1053 } 1054 } 1055 1056 fn verify_constant_size( 1057 &self, 1058 inst: Inst, 1059 constant: Constant, 1060 errors: &mut VerifierErrors, 1061 ) -> VerifierStepResult<()> { 1062 let type_size = self.func.dfg.ctrl_typevar(inst).bytes() as usize; 1063 let constant_size = self.func.dfg.constants.get(constant).len(); 1064 if type_size != constant_size { 1065 errors.fatal(( 1066 inst, 1067 format!( 1068 "The instruction expects {} to have a size of {} bytes but it has {}", 1069 constant, type_size, constant_size 1070 ), 1071 )) 1072 } else { 1073 Ok(()) 1074 } 1075 } 1076 1077 fn domtree_integrity( 1078 &self, 1079 domtree: &DominatorTree, 1080 errors: &mut VerifierErrors, 1081 ) -> VerifierStepResult<()> { 1082 // We consider two `DominatorTree`s to be equal if they return the same immediate 1083 // dominator for each block. Therefore the current domtree is valid if it matches the freshly 1084 // computed one. 1085 for block in self.func.layout.blocks() { 1086 let expected = self.expected_domtree.idom(block); 1087 let got = domtree.idom(block); 1088 if got != expected { 1089 return errors.fatal(( 1090 block, 1091 format!( 1092 "invalid domtree, expected idom({}) = {:?}, got {:?}", 1093 block, expected, got 1094 ), 1095 )); 1096 } 1097 } 1098 // We also verify if the postorder defined by `DominatorTree` is sane 1099 if domtree.cfg_postorder().len() != self.expected_domtree.cfg_postorder().len() { 1100 return errors.fatal(( 1101 AnyEntity::Function, 1102 "incorrect number of Blocks in postorder traversal", 1103 )); 1104 } 1105 for (index, (&test_block, &true_block)) in domtree 1106 .cfg_postorder() 1107 .iter() 1108 .zip(self.expected_domtree.cfg_postorder().iter()) 1109 .enumerate() 1110 { 1111 if test_block != true_block { 1112 return errors.fatal(( 1113 test_block, 1114 format!( 1115 "invalid domtree, postorder block number {} should be {}, got {}", 1116 index, true_block, test_block 1117 ), 1118 )); 1119 } 1120 } 1121 // We verify rpo_cmp on pairs of adjacent blocks in the postorder 1122 for (&prev_block, &next_block) in domtree.cfg_postorder().iter().adjacent_pairs() { 1123 if self 1124 .expected_domtree 1125 .rpo_cmp(prev_block, next_block, &self.func.layout) 1126 != Ordering::Greater 1127 { 1128 return errors.fatal(( 1129 next_block, 1130 format!( 1131 "invalid domtree, rpo_cmp does not says {} is greater than {}", 1132 prev_block, next_block 1133 ), 1134 )); 1135 } 1136 } 1137 Ok(()) 1138 } 1139 1140 fn typecheck_entry_block_params(&self, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 1141 if let Some(block) = self.func.layout.entry_block() { 1142 let expected_types = &self.func.signature.params; 1143 let block_param_count = self.func.dfg.num_block_params(block); 1144 1145 if block_param_count != expected_types.len() { 1146 return errors.fatal(( 1147 block, 1148 format!( 1149 "entry block parameters ({}) must match function signature ({})", 1150 block_param_count, 1151 expected_types.len() 1152 ), 1153 )); 1154 } 1155 1156 for (i, &arg) in self.func.dfg.block_params(block).iter().enumerate() { 1157 let arg_type = self.func.dfg.value_type(arg); 1158 if arg_type != expected_types[i].value_type { 1159 errors.report(( 1160 block, 1161 format!( 1162 "entry block parameter {} expected to have type {}, got {}", 1163 i, expected_types[i], arg_type 1164 ), 1165 )); 1166 } 1167 } 1168 } 1169 1170 errors.as_result() 1171 } 1172 1173 fn check_entry_not_cold(&self, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 1174 if let Some(entry_block) = self.func.layout.entry_block() { 1175 if self.func.layout.is_cold(entry_block) { 1176 return errors 1177 .fatal((entry_block, format!("entry block cannot be marked as cold"))); 1178 } 1179 } 1180 errors.as_result() 1181 } 1182 1183 fn typecheck(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 1184 let inst_data = &self.func.dfg.insts[inst]; 1185 let constraints = inst_data.opcode().constraints(); 1186 1187 let ctrl_type = if let Some(value_typeset) = constraints.ctrl_typeset() { 1188 // For polymorphic opcodes, determine the controlling type variable first. 1189 let ctrl_type = self.func.dfg.ctrl_typevar(inst); 1190 1191 if !value_typeset.contains(ctrl_type) { 1192 errors.report(( 1193 inst, 1194 self.context(inst), 1195 format!("has an invalid controlling type {}", ctrl_type), 1196 )); 1197 } 1198 1199 ctrl_type 1200 } else { 1201 // Non-polymorphic instructions don't check the controlling type variable, so `Option` 1202 // is unnecessary and we can just make it `INVALID`. 1203 types::INVALID 1204 }; 1205 1206 // Typechecking instructions is never fatal 1207 let _ = self.typecheck_results(inst, ctrl_type, errors); 1208 let _ = self.typecheck_fixed_args(inst, ctrl_type, errors); 1209 let _ = self.typecheck_variable_args(inst, errors); 1210 let _ = self.typecheck_return(inst, errors); 1211 let _ = self.typecheck_special(inst, ctrl_type, errors); 1212 1213 Ok(()) 1214 } 1215 1216 fn typecheck_results( 1217 &self, 1218 inst: Inst, 1219 ctrl_type: Type, 1220 errors: &mut VerifierErrors, 1221 ) -> VerifierStepResult<()> { 1222 let mut i = 0; 1223 for &result in self.func.dfg.inst_results(inst) { 1224 let result_type = self.func.dfg.value_type(result); 1225 let expected_type = self.func.dfg.compute_result_type(inst, i, ctrl_type); 1226 if let Some(expected_type) = expected_type { 1227 if result_type != expected_type { 1228 errors.report(( 1229 inst, 1230 self.context(inst), 1231 format!( 1232 "expected result {} ({}) to have type {}, found {}", 1233 i, result, expected_type, result_type 1234 ), 1235 )); 1236 } 1237 } else { 1238 return errors.nonfatal(( 1239 inst, 1240 self.context(inst), 1241 "has more result values than expected", 1242 )); 1243 } 1244 i += 1; 1245 } 1246 1247 // There aren't any more result types left. 1248 if self.func.dfg.compute_result_type(inst, i, ctrl_type) != None { 1249 return errors.nonfatal(( 1250 inst, 1251 self.context(inst), 1252 "has fewer result values than expected", 1253 )); 1254 } 1255 Ok(()) 1256 } 1257 1258 fn typecheck_fixed_args( 1259 &self, 1260 inst: Inst, 1261 ctrl_type: Type, 1262 errors: &mut VerifierErrors, 1263 ) -> VerifierStepResult<()> { 1264 let constraints = self.func.dfg.insts[inst].opcode().constraints(); 1265 1266 for (i, &arg) in self.func.dfg.inst_fixed_args(inst).iter().enumerate() { 1267 let arg_type = self.func.dfg.value_type(arg); 1268 match constraints.value_argument_constraint(i, ctrl_type) { 1269 ResolvedConstraint::Bound(expected_type) => { 1270 if arg_type != expected_type { 1271 errors.report(( 1272 inst, 1273 self.context(inst), 1274 format!( 1275 "arg {} ({}) has type {}, expected {}", 1276 i, arg, arg_type, expected_type 1277 ), 1278 )); 1279 } 1280 } 1281 ResolvedConstraint::Free(type_set) => { 1282 if !type_set.contains(arg_type) { 1283 errors.report(( 1284 inst, 1285 self.context(inst), 1286 format!( 1287 "arg {} ({}) with type {} failed to satisfy type set {:?}", 1288 i, arg, arg_type, type_set 1289 ), 1290 )); 1291 } 1292 } 1293 } 1294 } 1295 Ok(()) 1296 } 1297 1298 fn typecheck_variable_args( 1299 &self, 1300 inst: Inst, 1301 errors: &mut VerifierErrors, 1302 ) -> VerifierStepResult<()> { 1303 match self.func.dfg.analyze_branch(inst) { 1304 BranchInfo::SingleDest(block, _) => { 1305 let iter = self 1306 .func 1307 .dfg 1308 .block_params(block) 1309 .iter() 1310 .map(|&v| self.func.dfg.value_type(v)); 1311 self.typecheck_variable_args_iterator(inst, iter, errors)?; 1312 } 1313 BranchInfo::Table(table, block) => { 1314 if let Some(block) = block { 1315 let arg_count = self.func.dfg.num_block_params(block); 1316 if arg_count != 0 { 1317 return errors.nonfatal(( 1318 inst, 1319 self.context(inst), 1320 format!( 1321 "takes no arguments, but had target {} with {} arguments", 1322 block, arg_count, 1323 ), 1324 )); 1325 } 1326 } 1327 for block in self.func.jump_tables[table].iter() { 1328 let arg_count = self.func.dfg.num_block_params(*block); 1329 if arg_count != 0 { 1330 return errors.nonfatal(( 1331 inst, 1332 self.context(inst), 1333 format!( 1334 "takes no arguments, but had target {} with {} arguments", 1335 block, arg_count, 1336 ), 1337 )); 1338 } 1339 } 1340 } 1341 BranchInfo::NotABranch => {} 1342 } 1343 1344 match self.func.dfg.insts[inst].analyze_call(&self.func.dfg.value_lists) { 1345 CallInfo::Direct(func_ref, _) => { 1346 let sig_ref = self.func.dfg.ext_funcs[func_ref].signature; 1347 let arg_types = self.func.dfg.signatures[sig_ref] 1348 .params 1349 .iter() 1350 .map(|a| a.value_type); 1351 self.typecheck_variable_args_iterator(inst, arg_types, errors)?; 1352 } 1353 CallInfo::Indirect(sig_ref, _) => { 1354 let arg_types = self.func.dfg.signatures[sig_ref] 1355 .params 1356 .iter() 1357 .map(|a| a.value_type); 1358 self.typecheck_variable_args_iterator(inst, arg_types, errors)?; 1359 } 1360 CallInfo::NotACall => {} 1361 } 1362 Ok(()) 1363 } 1364 1365 fn typecheck_variable_args_iterator<I: Iterator<Item = Type>>( 1366 &self, 1367 inst: Inst, 1368 iter: I, 1369 errors: &mut VerifierErrors, 1370 ) -> VerifierStepResult<()> { 1371 let variable_args = self.func.dfg.inst_variable_args(inst); 1372 let mut i = 0; 1373 1374 for expected_type in iter { 1375 if i >= variable_args.len() { 1376 // Result count mismatch handled below, we want the full argument count first though 1377 i += 1; 1378 continue; 1379 } 1380 let arg = variable_args[i]; 1381 let arg_type = self.func.dfg.value_type(arg); 1382 if expected_type != arg_type { 1383 errors.report(( 1384 inst, 1385 self.context(inst), 1386 format!( 1387 "arg {} ({}) has type {}, expected {}", 1388 i, variable_args[i], arg_type, expected_type 1389 ), 1390 )); 1391 } 1392 i += 1; 1393 } 1394 if i != variable_args.len() { 1395 return errors.nonfatal(( 1396 inst, 1397 self.context(inst), 1398 format!( 1399 "mismatched argument count for `{}`: got {}, expected {}", 1400 self.func.dfg.display_inst(inst), 1401 variable_args.len(), 1402 i, 1403 ), 1404 )); 1405 } 1406 Ok(()) 1407 } 1408 1409 fn typecheck_return(&self, inst: Inst, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 1410 if self.func.dfg.insts[inst].opcode().is_return() { 1411 let args = self.func.dfg.inst_variable_args(inst); 1412 let expected_types = &self.func.signature.returns; 1413 if args.len() != expected_types.len() { 1414 return errors.nonfatal(( 1415 inst, 1416 self.context(inst), 1417 "arguments of return must match function signature", 1418 )); 1419 } 1420 for (i, (&arg, &expected_type)) in args.iter().zip(expected_types).enumerate() { 1421 let arg_type = self.func.dfg.value_type(arg); 1422 if arg_type != expected_type.value_type { 1423 errors.report(( 1424 inst, 1425 self.context(inst), 1426 format!( 1427 "arg {} ({}) has type {}, must match function signature of {}", 1428 i, arg, arg_type, expected_type 1429 ), 1430 )); 1431 } 1432 } 1433 } 1434 Ok(()) 1435 } 1436 1437 // Check special-purpose type constraints that can't be expressed in the normal opcode 1438 // constraints. 1439 fn typecheck_special( 1440 &self, 1441 inst: Inst, 1442 ctrl_type: Type, 1443 errors: &mut VerifierErrors, 1444 ) -> VerifierStepResult<()> { 1445 match self.func.dfg.insts[inst] { 1446 ir::InstructionData::Unary { opcode, arg } => { 1447 let arg_type = self.func.dfg.value_type(arg); 1448 match opcode { 1449 Opcode::Uextend | Opcode::Sextend | Opcode::Fpromote => { 1450 if arg_type.lane_count() != ctrl_type.lane_count() { 1451 return errors.nonfatal(( 1452 inst, 1453 self.context(inst), 1454 format!( 1455 "input {} and output {} must have same number of lanes", 1456 arg_type, ctrl_type, 1457 ), 1458 )); 1459 } 1460 if arg_type.lane_bits() >= ctrl_type.lane_bits() { 1461 return errors.nonfatal(( 1462 inst, 1463 self.context(inst), 1464 format!( 1465 "input {} must be smaller than output {}", 1466 arg_type, ctrl_type, 1467 ), 1468 )); 1469 } 1470 } 1471 Opcode::Ireduce | Opcode::Fdemote => { 1472 if arg_type.lane_count() != ctrl_type.lane_count() { 1473 return errors.nonfatal(( 1474 inst, 1475 self.context(inst), 1476 format!( 1477 "input {} and output {} must have same number of lanes", 1478 arg_type, ctrl_type, 1479 ), 1480 )); 1481 } 1482 if arg_type.lane_bits() <= ctrl_type.lane_bits() { 1483 return errors.nonfatal(( 1484 inst, 1485 self.context(inst), 1486 format!( 1487 "input {} must be larger than output {}", 1488 arg_type, ctrl_type, 1489 ), 1490 )); 1491 } 1492 } 1493 _ => {} 1494 } 1495 } 1496 ir::InstructionData::TableAddr { table, arg, .. } => { 1497 let index_type = self.func.dfg.value_type(arg); 1498 let table_index_type = self.func.tables[table].index_type; 1499 if index_type != table_index_type { 1500 return errors.nonfatal(( 1501 inst, 1502 self.context(inst), 1503 format!( 1504 "index type {} differs from table index type {}", 1505 index_type, table_index_type, 1506 ), 1507 )); 1508 } 1509 } 1510 ir::InstructionData::UnaryGlobalValue { global_value, .. } => { 1511 if let Some(isa) = self.isa { 1512 let inst_type = self.func.dfg.value_type(self.func.dfg.first_result(inst)); 1513 let global_type = self.func.global_values[global_value].global_type(isa); 1514 if inst_type != global_type { 1515 return errors.nonfatal(( 1516 inst, self.context(inst), 1517 format!( 1518 "global_value instruction with type {} references global value with type {}", 1519 inst_type, global_type 1520 )), 1521 ); 1522 } 1523 } 1524 } 1525 _ => {} 1526 } 1527 Ok(()) 1528 } 1529 1530 fn cfg_integrity( 1531 &self, 1532 cfg: &ControlFlowGraph, 1533 errors: &mut VerifierErrors, 1534 ) -> VerifierStepResult<()> { 1535 let mut expected_succs = BTreeSet::<Block>::new(); 1536 let mut got_succs = BTreeSet::<Block>::new(); 1537 let mut expected_preds = BTreeSet::<Inst>::new(); 1538 let mut got_preds = BTreeSet::<Inst>::new(); 1539 1540 for block in self.func.layout.blocks() { 1541 expected_succs.extend(self.expected_cfg.succ_iter(block)); 1542 got_succs.extend(cfg.succ_iter(block)); 1543 1544 let missing_succs: Vec<Block> = 1545 expected_succs.difference(&got_succs).cloned().collect(); 1546 if !missing_succs.is_empty() { 1547 errors.report(( 1548 block, 1549 format!("cfg lacked the following successor(s) {:?}", missing_succs), 1550 )); 1551 continue; 1552 } 1553 1554 let excess_succs: Vec<Block> = got_succs.difference(&expected_succs).cloned().collect(); 1555 if !excess_succs.is_empty() { 1556 errors.report(( 1557 block, 1558 format!("cfg had unexpected successor(s) {:?}", excess_succs), 1559 )); 1560 continue; 1561 } 1562 1563 expected_preds.extend( 1564 self.expected_cfg 1565 .pred_iter(block) 1566 .map(|BlockPredecessor { inst, .. }| inst), 1567 ); 1568 got_preds.extend( 1569 cfg.pred_iter(block) 1570 .map(|BlockPredecessor { inst, .. }| inst), 1571 ); 1572 1573 let missing_preds: Vec<Inst> = expected_preds.difference(&got_preds).cloned().collect(); 1574 if !missing_preds.is_empty() { 1575 errors.report(( 1576 block, 1577 format!( 1578 "cfg lacked the following predecessor(s) {:?}", 1579 missing_preds 1580 ), 1581 )); 1582 continue; 1583 } 1584 1585 let excess_preds: Vec<Inst> = got_preds.difference(&expected_preds).cloned().collect(); 1586 if !excess_preds.is_empty() { 1587 errors.report(( 1588 block, 1589 format!("cfg had unexpected predecessor(s) {:?}", excess_preds), 1590 )); 1591 continue; 1592 } 1593 1594 expected_succs.clear(); 1595 got_succs.clear(); 1596 expected_preds.clear(); 1597 got_preds.clear(); 1598 } 1599 errors.as_result() 1600 } 1601 1602 fn immediate_constraints( 1603 &self, 1604 inst: Inst, 1605 errors: &mut VerifierErrors, 1606 ) -> VerifierStepResult<()> { 1607 let inst_data = &self.func.dfg.insts[inst]; 1608 1609 match *inst_data { 1610 ir::InstructionData::Store { flags, .. } => { 1611 if flags.readonly() { 1612 errors.fatal(( 1613 inst, 1614 self.context(inst), 1615 "A store instruction cannot have the `readonly` MemFlag", 1616 )) 1617 } else { 1618 Ok(()) 1619 } 1620 } 1621 ir::InstructionData::BinaryImm8 { 1622 opcode: ir::instructions::Opcode::Extractlane, 1623 imm: lane, 1624 arg, 1625 .. 1626 } 1627 | ir::InstructionData::TernaryImm8 { 1628 opcode: ir::instructions::Opcode::Insertlane, 1629 imm: lane, 1630 args: [arg, _], 1631 .. 1632 } => { 1633 // We must be specific about the opcodes above because other instructions are using 1634 // the same formats. 1635 let ty = self.func.dfg.value_type(arg); 1636 if lane as u32 >= ty.lane_count() { 1637 errors.fatal(( 1638 inst, 1639 self.context(inst), 1640 format!("The lane {} does not index into the type {}", lane, ty,), 1641 )) 1642 } else { 1643 Ok(()) 1644 } 1645 } 1646 _ => Ok(()), 1647 } 1648 } 1649 1650 fn typecheck_function_signature(&self, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 1651 self.func 1652 .signature 1653 .params 1654 .iter() 1655 .enumerate() 1656 .filter(|(_, ¶m)| param.value_type == types::INVALID) 1657 .for_each(|(i, _)| { 1658 errors.report(( 1659 AnyEntity::Function, 1660 format!("Parameter at position {} has an invalid type", i), 1661 )); 1662 }); 1663 1664 self.func 1665 .signature 1666 .returns 1667 .iter() 1668 .enumerate() 1669 .filter(|(_, &ret)| ret.value_type == types::INVALID) 1670 .for_each(|(i, _)| { 1671 errors.report(( 1672 AnyEntity::Function, 1673 format!("Return value at position {} has an invalid type", i), 1674 )) 1675 }); 1676 1677 self.func 1678 .signature 1679 .returns 1680 .iter() 1681 .enumerate() 1682 .for_each(|(i, ret)| { 1683 if let ArgumentPurpose::StructArgument(_) = ret.purpose { 1684 errors.report(( 1685 AnyEntity::Function, 1686 format!("Return value at position {} can't be an struct argument", i), 1687 )) 1688 } 1689 }); 1690 1691 if errors.has_error() { 1692 Err(()) 1693 } else { 1694 Ok(()) 1695 } 1696 } 1697 1698 pub fn run(&self, errors: &mut VerifierErrors) -> VerifierStepResult<()> { 1699 self.verify_global_values(errors)?; 1700 self.verify_tables(errors)?; 1701 self.verify_jump_tables(errors)?; 1702 self.typecheck_entry_block_params(errors)?; 1703 self.check_entry_not_cold(errors)?; 1704 self.typecheck_function_signature(errors)?; 1705 1706 for block in self.func.layout.blocks() { 1707 if self.func.layout.first_inst(block).is_none() { 1708 return errors.fatal((block, format!("{} cannot be empty", block))); 1709 } 1710 for inst in self.func.layout.block_insts(block) { 1711 self.block_integrity(block, inst, errors)?; 1712 self.instruction_integrity(inst, errors)?; 1713 self.typecheck(inst, errors)?; 1714 self.immediate_constraints(inst, errors)?; 1715 } 1716 1717 self.encodable_as_bb(block, errors)?; 1718 } 1719 1720 if !errors.is_empty() { 1721 log::warn!( 1722 "Found verifier errors in function:\n{}", 1723 pretty_verifier_error(self.func, None, errors.clone()) 1724 ); 1725 } 1726 1727 Ok(()) 1728 } 1729 } 1730 1731 #[cfg(test)] 1732 mod tests { 1733 use super::{Verifier, VerifierError, VerifierErrors}; 1734 use crate::entity::EntityList; 1735 use crate::ir::instructions::{InstructionData, Opcode}; 1736 use crate::ir::{types, AbiParam, Function}; 1737 use crate::settings; 1738 1739 macro_rules! assert_err_with_msg { 1740 ($e:expr, $msg:expr) => { 1741 match $e.0.get(0) { 1742 None => panic!("Expected an error"), 1743 Some(&VerifierError { ref message, .. }) => { 1744 if !message.contains($msg) { 1745 #[cfg(feature = "std")] 1746 panic!("'{}' did not contain the substring '{}'", message, $msg); 1747 #[cfg(not(feature = "std"))] 1748 panic!("error message did not contain the expected substring"); 1749 } 1750 } 1751 } 1752 }; 1753 } 1754 1755 #[test] 1756 fn empty() { 1757 let func = Function::new(); 1758 let flags = &settings::Flags::new(settings::builder()); 1759 let verifier = Verifier::new(&func, flags.into()); 1760 let mut errors = VerifierErrors::default(); 1761 1762 assert_eq!(verifier.run(&mut errors), Ok(())); 1763 assert!(errors.0.is_empty()); 1764 } 1765 1766 #[test] 1767 fn bad_instruction_format() { 1768 let mut func = Function::new(); 1769 let block0 = func.dfg.make_block(); 1770 func.layout.append_block(block0); 1771 let nullary_with_bad_opcode = func.dfg.make_inst(InstructionData::UnaryImm { 1772 opcode: Opcode::F32const, 1773 imm: 0.into(), 1774 }); 1775 func.layout.append_inst(nullary_with_bad_opcode, block0); 1776 func.stencil.layout.append_inst( 1777 func.stencil.dfg.make_inst(InstructionData::Jump { 1778 opcode: Opcode::Jump, 1779 destination: block0, 1780 args: EntityList::default(), 1781 }), 1782 block0, 1783 ); 1784 let flags = &settings::Flags::new(settings::builder()); 1785 let verifier = Verifier::new(&func, flags.into()); 1786 let mut errors = VerifierErrors::default(); 1787 1788 let _ = verifier.run(&mut errors); 1789 1790 assert_err_with_msg!(errors, "instruction format"); 1791 } 1792 1793 #[test] 1794 fn test_function_invalid_param() { 1795 let mut func = Function::new(); 1796 func.signature.params.push(AbiParam::new(types::INVALID)); 1797 1798 let mut errors = VerifierErrors::default(); 1799 let flags = &settings::Flags::new(settings::builder()); 1800 let verifier = Verifier::new(&func, flags.into()); 1801 1802 let _ = verifier.typecheck_function_signature(&mut errors); 1803 assert_err_with_msg!(errors, "Parameter at position 0 has an invalid type"); 1804 } 1805 1806 #[test] 1807 fn test_function_invalid_return_value() { 1808 let mut func = Function::new(); 1809 func.signature.returns.push(AbiParam::new(types::INVALID)); 1810 1811 let mut errors = VerifierErrors::default(); 1812 let flags = &settings::Flags::new(settings::builder()); 1813 let verifier = Verifier::new(&func, flags.into()); 1814 1815 let _ = verifier.typecheck_function_signature(&mut errors); 1816 assert_err_with_msg!(errors, "Return value at position 0 has an invalid type"); 1817 } 1818 1819 #[test] 1820 fn test_printing_contextual_errors() { 1821 // Build function. 1822 let mut func = Function::new(); 1823 let block0 = func.dfg.make_block(); 1824 func.layout.append_block(block0); 1825 1826 // Build instruction: v0, v1 = iconst 42 1827 let inst = func.dfg.make_inst(InstructionData::UnaryImm { 1828 opcode: Opcode::Iconst, 1829 imm: 42.into(), 1830 }); 1831 func.dfg.append_result(inst, types::I32); 1832 func.dfg.append_result(inst, types::I32); 1833 func.layout.append_inst(inst, block0); 1834 1835 // Setup verifier. 1836 let mut errors = VerifierErrors::default(); 1837 let flags = &settings::Flags::new(settings::builder()); 1838 let verifier = Verifier::new(&func, flags.into()); 1839 1840 // Now the error message, when printed, should contain the instruction sequence causing the 1841 // error (i.e. v0, v1 = iconst.i32 42) and not only its entity value (i.e. inst0) 1842 let _ = verifier.typecheck_results(inst, types::I32, &mut errors); 1843 assert_eq!( 1844 format!("{}", errors.0[0]), 1845 "inst0 (v0, v1 = iconst.i32 42): has more result values than expected" 1846 ) 1847 } 1848 1849 #[test] 1850 fn test_empty_block() { 1851 let mut func = Function::new(); 1852 let block0 = func.dfg.make_block(); 1853 func.layout.append_block(block0); 1854 1855 let flags = &settings::Flags::new(settings::builder()); 1856 let verifier = Verifier::new(&func, flags.into()); 1857 let mut errors = VerifierErrors::default(); 1858 let _ = verifier.run(&mut errors); 1859 1860 assert_err_with_msg!(errors, "block0 cannot be empty"); 1861 } 1862 } 1863