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