1 //! Generate CLIF instruction data (including opcodes, formats, builders, etc.). 2 3 use crate::cdsl::camel_case; 4 use crate::cdsl::formats::InstructionFormat; 5 use crate::cdsl::instructions::{AllInstructions, Instruction}; 6 use crate::cdsl::operands::{Operand, OperandKindFields}; 7 use crate::cdsl::typevar::{TypeSet, TypeVar}; 8 use crate::unique_table::{UniqueSeqTable, UniqueTable}; 9 use cranelift_codegen_shared::constant_hash; 10 use cranelift_srcgen::{Formatter, Language, Match, error, fmtln}; 11 use std::fmt; 12 use std::rc::Rc; 13 14 // TypeSet indexes are encoded in 8 bits, with `0xff` reserved. 15 const TYPESET_LIMIT: usize = 0xff; 16 17 /// Generate an instruction format enumeration. 18 fn gen_formats(formats: &[Rc<InstructionFormat>], fmt: &mut Formatter) { 19 fmt.doc_comment( 20 r#" 21 An instruction format 22 23 Every opcode has a corresponding instruction format 24 which is represented by both the `InstructionFormat` 25 and the `InstructionData` enums. 26 "#, 27 ); 28 fmt.line("#[derive(Copy, Clone, PartialEq, Eq, Debug)]"); 29 fmt.add_block("pub enum InstructionFormat", |fmt| { 30 for format in formats { 31 fmt.doc_comment(format.to_string()); 32 fmtln!(fmt, "{},", format.name); 33 } 34 }); 35 fmt.empty_line(); 36 37 // Emit a From<InstructionData> which also serves to verify that 38 // InstructionFormat and InstructionData are in sync. 39 fmt.add_block( 40 "impl<'a> From<&'a InstructionData> for InstructionFormat", 41 |fmt| { 42 fmt.add_block("fn from(inst: &'a InstructionData) -> Self", |fmt| { 43 let mut m = Match::new("*inst"); 44 for format in formats { 45 m.arm( 46 format!("InstructionData::{}", format.name), 47 vec![".."], 48 format!("Self::{}", format.name), 49 ); 50 } 51 fmt.add_match(m); 52 }); 53 }, 54 ); 55 fmt.empty_line(); 56 } 57 58 /// Generate the InstructionData enum. 59 /// 60 /// Every variant must contain an `opcode` field. The size of `InstructionData` should be kept at 61 /// 16 bytes on 64-bit architectures. If more space is needed to represent an instruction, use a 62 /// `ValueList` to store the additional information out of line. 63 fn gen_instruction_data(formats: &[Rc<InstructionFormat>], fmt: &mut Formatter) { 64 fmt.line("#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]"); 65 fmt.line(r#"#[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]"#); 66 fmt.line("#[allow(missing_docs, reason = \"generated code\")]"); 67 fmt.add_block("pub enum InstructionData", |fmt| { 68 for format in formats { 69 fmt.add_block(&format!("{}", format.name), |fmt| { 70 fmt.line("opcode: Opcode,"); 71 if format.has_value_list { 72 fmt.line("args: ValueList,"); 73 } else if format.num_value_operands == 1 { 74 fmt.line("arg: Value,"); 75 } else if format.num_value_operands > 0 { 76 fmtln!(fmt, "args: [Value; {}],", format.num_value_operands); 77 } 78 79 match format.num_block_operands { 80 0 => (), 81 1 => fmt.line("destination: ir::BlockCall,"), 82 2 => fmtln!( 83 fmt, 84 "blocks: [ir::BlockCall; {}],", 85 format.num_block_operands 86 ), 87 n => panic!("Too many block operands in instruction: {n}"), 88 } 89 90 for field in &format.imm_fields { 91 fmtln!(fmt, "{}: {},", field.member, field.kind.rust_type); 92 } 93 }); 94 fmtln!(fmt, ","); 95 } 96 }); 97 } 98 99 fn gen_arguments_method(formats: &[Rc<InstructionFormat>], fmt: &mut Formatter, is_mut: bool) { 100 let (method, mut_, rslice, as_slice) = if is_mut { 101 ( 102 "arguments_mut", 103 "mut ", 104 "core::slice::from_mut", 105 "as_mut_slice", 106 ) 107 } else { 108 ("arguments", "", "core::slice::from_ref", "as_slice") 109 }; 110 111 fmt.add_block(&format!( 112 "pub fn {method}<'a>(&'a {mut_}self, pool: &'a {mut_}ir::ValueListPool) -> &'a {mut_}[Value]"), 113 114 |fmt| { 115 let mut m = Match::new("*self"); 116 for format in formats { 117 let name = format!("Self::{}", format.name); 118 119 // Formats with a value list put all of their arguments in the list. We don't split 120 // them up, just return it all as variable arguments. (I expect the distinction to go 121 // away). 122 if format.has_value_list { 123 m.arm( 124 name, 125 vec![format!("ref {}args", mut_), "..".to_string()], 126 format!("args.{as_slice}(pool)"), 127 ); 128 continue; 129 } 130 131 // Fixed args. 132 let mut fields = Vec::new(); 133 let arg = if format.num_value_operands == 0 { 134 format!("&{mut_}[]") 135 } else if format.num_value_operands == 1 { 136 fields.push(format!("ref {mut_}arg")); 137 format!("{rslice}(arg)") 138 } else { 139 let arg = format!("args_arity{}", format.num_value_operands); 140 fields.push(format!("args: ref {mut_}{arg}")); 141 arg 142 }; 143 fields.push("..".into()); 144 145 m.arm(name, fields, arg); 146 } 147 fmt.add_match(m); 148 }); 149 } 150 151 /// Generate the boring parts of the InstructionData implementation. 152 /// 153 /// These methods in `impl InstructionData` can be generated automatically from the instruction 154 /// formats: 155 /// 156 /// - `pub fn opcode(&self) -> Opcode` 157 /// - `pub fn arguments(&self, &pool) -> &[Value]` 158 /// - `pub fn arguments_mut(&mut self, &pool) -> &mut [Value]` 159 /// - `pub fn eq(&self, &other: Self, &pool) -> bool` 160 /// - `pub fn hash<H: Hasher>(&self, state: &mut H, &pool)` 161 fn gen_instruction_data_impl(formats: &[Rc<InstructionFormat>], fmt: &mut Formatter) { 162 fmt.add_block("impl InstructionData", |fmt| { 163 fmt.doc_comment("Get the opcode of this instruction."); 164 fmt.add_block("pub fn opcode(&self) -> Opcode",|fmt| { 165 let mut m = Match::new("*self"); 166 for format in formats { 167 m.arm(format!("Self::{}", format.name), vec!["opcode", ".."], 168 "opcode".to_string()); 169 } 170 fmt.add_match(m); 171 }); 172 fmt.empty_line(); 173 174 fmt.doc_comment("Get the controlling type variable operand."); 175 fmt.add_block("pub fn typevar_operand(&self, pool: &ir::ValueListPool) -> Option<Value>",|fmt| { 176 let mut m = Match::new("*self"); 177 for format in formats { 178 let name = format!("Self::{}", format.name); 179 if format.typevar_operand.is_none() { 180 m.arm(name, vec![".."], "None".to_string()); 181 } else if format.has_value_list { 182 // We keep all arguments in a value list. 183 m.arm(name, vec!["ref args", ".."], format!("args.get({}, pool)", format.typevar_operand.unwrap())); 184 } else if format.num_value_operands == 1 { 185 m.arm(name, vec!["arg", ".."], "Some(arg)".to_string()); 186 } else { 187 // We have multiple value operands and an array `args`. 188 // Which `args` index to use? 189 let args = format!("args_arity{}", format.num_value_operands); 190 m.arm(name, vec![format!("args: ref {}", args), "..".to_string()], 191 format!("Some({}[{}])", args, format.typevar_operand.unwrap())); 192 } 193 } 194 fmt.add_match(m); 195 }); 196 fmt.empty_line(); 197 198 fmt.doc_comment("Get the value arguments to this instruction."); 199 gen_arguments_method(formats, fmt, false); 200 fmt.empty_line(); 201 202 fmt.doc_comment(r#"Get mutable references to the value arguments to this 203 instruction."#); 204 gen_arguments_method(formats, fmt, true); 205 fmt.empty_line(); 206 207 fmt.doc_comment(r#" 208 Compare two `InstructionData` for equality. 209 210 This operation requires a reference to a `ValueListPool` to 211 determine if the contents of any `ValueLists` are equal. 212 213 This operation takes a closure that is allowed to map each 214 argument value to some other value before the instructions 215 are compared. This allows various forms of canonicalization. 216 "#); 217 fmt.add_block("pub fn eq(&self, other: &Self, pool: &ir::ValueListPool) -> bool", |fmt| { 218 fmt.add_block("if ::core::mem::discriminant(self) != ::core::mem::discriminant(other)", |fmt| { 219 fmt.line("return false;"); 220 }); 221 222 fmt.add_block("match (self, other)",|fmt| { 223 for format in formats { 224 let name = format!("&Self::{}", format.name); 225 let mut members = vec!["opcode"]; 226 227 let args_eq = if format.has_value_list { 228 members.push("args"); 229 Some("args1.as_slice(pool).iter().zip(args2.as_slice(pool).iter()).all(|(a, b)| a == b)") 230 } else if format.num_value_operands == 1 { 231 members.push("arg"); 232 Some("arg1 == arg2") 233 } else if format.num_value_operands > 0 { 234 members.push("args"); 235 Some("args1.iter().zip(args2.iter()).all(|(a, b)| a == b)") 236 } else { 237 None 238 }; 239 240 let blocks_eq = match format.num_block_operands { 241 0 => None, 242 1 => { 243 members.push("destination"); 244 Some("destination1 == destination2") 245 }, 246 _ => { 247 members.push("blocks"); 248 Some("blocks1.iter().zip(blocks2.iter()).all(|(a, b)| a.block(pool) == b.block(pool))") 249 } 250 }; 251 252 for field in &format.imm_fields { 253 members.push(field.member); 254 } 255 256 let pat1 = members.iter().map(|x| format!("{x}: ref {x}1")).collect::<Vec<_>>().join(", "); 257 let pat2 = members.iter().map(|x| format!("{x}: ref {x}2")).collect::<Vec<_>>().join(", "); 258 fmt.add_block(&format!("({name} {{ {pat1} }}, {name} {{ {pat2} }}) => "), |fmt| { 259 fmt.line("opcode1 == opcode2"); 260 for field in &format.imm_fields { 261 fmtln!(fmt, "&& {}1 == {}2", field.member, field.member); 262 } 263 if let Some(args_eq) = args_eq { 264 fmtln!(fmt, "&& {}", args_eq); 265 } 266 if let Some(blocks_eq) = blocks_eq { 267 fmtln!(fmt, "&& {}", blocks_eq); 268 } 269 }); 270 } 271 fmt.line("_ => unreachable!()"); 272 }); 273 }); 274 fmt.empty_line(); 275 276 fmt.doc_comment(r#" 277 Hash an `InstructionData`. 278 279 This operation requires a reference to a `ValueListPool` to 280 hash the contents of any `ValueLists`. 281 282 This operation takes a closure that is allowed to map each 283 argument value to some other value before it is hashed. This 284 allows various forms of canonicalization. 285 "#); 286 fmt.add_block("pub fn hash<H: ::core::hash::Hasher>(&self, state: &mut H, pool: &ir::ValueListPool)",|fmt| { 287 fmt.add_block("match *self",|fmt| { 288 for format in formats { 289 let name = format!("Self::{}", format.name); 290 let mut members = vec!["opcode"]; 291 292 let (args, len) = if format.has_value_list { 293 members.push("ref args"); 294 (Some("args.as_slice(pool)"), "args.len(pool)") 295 } else if format.num_value_operands == 1 { 296 members.push("ref arg"); 297 (Some("std::slice::from_ref(arg)"), "1") 298 } else if format.num_value_operands > 0 { 299 members.push("ref args"); 300 (Some("args"), "args.len()") 301 } else { 302 (None, "0") 303 }; 304 305 let blocks = match format.num_block_operands { 306 0 => None, 307 1 => { 308 members.push("ref destination"); 309 Some(("std::slice::from_ref(destination)", "1")) 310 } 311 _ => { 312 members.push("ref blocks"); 313 Some(("blocks", "blocks.len()")) 314 } 315 }; 316 317 for field in &format.imm_fields { 318 members.push(field.member); 319 } 320 let members = members.join(", "); 321 322 fmt.add_block(&format!("{name}{{{members}}} => "), |fmt| { 323 fmt.line("::core::hash::Hash::hash( &::core::mem::discriminant(self), state);"); 324 fmt.line("::core::hash::Hash::hash(&opcode, state);"); 325 for field in &format.imm_fields { 326 fmtln!(fmt, "::core::hash::Hash::hash(&{}, state);", field.member); 327 } 328 fmtln!(fmt, "::core::hash::Hash::hash(&{}, state);", len); 329 if let Some(args) = args { 330 fmt.add_block(&format!("for &arg in {args}"), |fmt| { 331 fmtln!(fmt, "::core::hash::Hash::hash(&arg, state);"); 332 }); 333 } 334 335 if let Some((blocks, len)) = blocks { 336 fmtln!(fmt, "::core::hash::Hash::hash(&{len}, state);"); 337 fmt.add_block(&format!("for &block in {blocks}"), |fmt| { 338 fmtln!(fmt, "::core::hash::Hash::hash(&block.block(pool), state);"); 339 fmt.add_block("for arg in block.args(pool)", |fmt| { 340 fmtln!(fmt, "::core::hash::Hash::hash(&arg, state);"); 341 }); 342 }); 343 } 344 }); 345 } 346 }); 347 }); 348 349 fmt.empty_line(); 350 351 fmt.doc_comment(r#" 352 Deep-clone an `InstructionData`, including any referenced lists. 353 354 This operation requires a reference to a `ValueListPool` to 355 clone the `ValueLists`. 356 "#); 357 fmt.add_block("pub fn deep_clone(&self, pool: &mut ir::ValueListPool) -> Self",|fmt| { 358 fmt.add_block("match *self",|fmt| { 359 for format in formats { 360 let name = format!("Self::{}", format.name); 361 let mut members = vec!["opcode"]; 362 363 if format.has_value_list { 364 members.push("ref args"); 365 } else if format.num_value_operands == 1 { 366 members.push("arg"); 367 } else if format.num_value_operands > 0 { 368 members.push("args"); 369 } 370 371 match format.num_block_operands { 372 0 => {} 373 1 => { 374 members.push("destination"); 375 } 376 _ => { 377 members.push("blocks"); 378 } 379 }; 380 381 for field in &format.imm_fields { 382 members.push(field.member); 383 } 384 let members = members.join(", "); 385 386 fmt.add_block(&format!("{name}{{{members}}} => "),|fmt| { 387 fmt.add_block(&format!("Self::{}", format.name), |fmt| { 388 fmtln!(fmt, "opcode,"); 389 390 if format.has_value_list { 391 fmtln!(fmt, "args: args.deep_clone(pool),"); 392 } else if format.num_value_operands == 1 { 393 fmtln!(fmt, "arg,"); 394 } else if format.num_value_operands > 0 { 395 fmtln!(fmt, "args,"); 396 } 397 398 match format.num_block_operands { 399 0 => {} 400 1 => { 401 fmtln!(fmt, "destination: destination.deep_clone(pool),"); 402 } 403 2 => { 404 fmtln!(fmt, "blocks: [blocks[0].deep_clone(pool), blocks[1].deep_clone(pool)],"); 405 } 406 _ => panic!("Too many block targets in instruction"), 407 } 408 409 for field in &format.imm_fields { 410 fmtln!(fmt, "{},", field.member); 411 } 412 }); 413 }); 414 } 415 }); 416 }); 417 fmt.doc_comment(r#" 418 Map some functions, described by the given `InstructionMapper`, over each of the 419 entities within this instruction, producing a new `InstructionData`. 420 "#); 421 fmt.add_block("pub fn map(&self, mut mapper: impl crate::ir::instructions::InstructionMapper) -> Self", |fmt| { 422 fmt.add_block("match *self",|fmt| { 423 for format in formats { 424 let name = format!("Self::{}", format.name); 425 let mut members = vec!["opcode"]; 426 427 if format.has_value_list { 428 members.push("args"); 429 } else if format.num_value_operands == 1 { 430 members.push("arg"); 431 } else if format.num_value_operands > 0 { 432 members.push("args"); 433 } 434 435 match format.num_block_operands { 436 0 => {} 437 1 => { 438 members.push("destination"); 439 } 440 _ => { 441 members.push("blocks"); 442 } 443 }; 444 445 for field in &format.imm_fields { 446 members.push(field.member); 447 } 448 let members = members.join(", "); 449 450 fmt.add_block(&format!("{name}{{{members}}} => "), |fmt| { 451 fmt.add_block(&format!("Self::{}", format.name), |fmt| { 452 fmtln!(fmt, "opcode,"); 453 454 if format.has_value_list { 455 fmtln!(fmt, "args: mapper.map_value_list(args),"); 456 } else if format.num_value_operands == 1 { 457 fmtln!(fmt, "arg: mapper.map_value(arg),"); 458 } else if format.num_value_operands > 0 { 459 let maps = (0..format.num_value_operands) 460 .map(|i| format!("mapper.map_value(args[{i}])")) 461 .collect::<Box<[_]>>() 462 .join(", "); 463 fmtln!(fmt, "args: [{maps}],"); 464 } 465 466 match format.num_block_operands { 467 0 => {} 468 1 => { 469 fmtln!(fmt, "destination: mapper.map_block_call(destination),"); 470 } 471 2 => { 472 fmtln!(fmt, "blocks: [mapper.map_block_call(blocks[0]), mapper.map_block_call(blocks[1])],"); 473 } 474 _ => panic!("Too many block targets in instruction"), 475 } 476 477 for field in &format.imm_fields { 478 let member = field.member; 479 match &field.kind.fields { 480 OperandKindFields::EntityRef => { 481 let mut kind = heck::ToSnakeCase::to_snake_case( 482 field 483 .kind 484 .rust_type 485 .split("::") 486 .last() 487 .unwrap_or(field.kind.rust_type), 488 ); 489 if kind == "block" { 490 kind.push_str("_call"); 491 } 492 fmtln!(fmt, "{member}: mapper.map_{kind}({member}),"); 493 } 494 OperandKindFields::VariableArgs => { 495 fmtln!(fmt, "{member}: mapper.map_value_list({member}),"); 496 } 497 OperandKindFields::ImmValue | 498 OperandKindFields::ImmEnum(_) | 499 OperandKindFields::TypeVar(_) => fmtln!(fmt, "{member},"), 500 } 501 } 502 }); 503 }); 504 } 505 }); 506 }); 507 }); 508 } 509 510 fn gen_bool_accessor<T: Fn(&Instruction) -> bool>( 511 all_inst: &AllInstructions, 512 get_attr: T, 513 name: &'static str, 514 doc: &'static str, 515 fmt: &mut Formatter, 516 ) { 517 fmt.doc_comment(doc); 518 fmt.add_block(&format!("pub fn {name}(self) -> bool"), |fmt| { 519 let mut m = Match::new("self"); 520 for inst in all_inst.iter() { 521 if get_attr(inst) { 522 m.arm_no_fields(format!("Self::{}", inst.camel_name), "true"); 523 } 524 } 525 m.arm_no_fields("_", "false"); 526 fmt.add_match(m); 527 }); 528 fmt.empty_line(); 529 } 530 531 fn gen_opcodes(all_inst: &AllInstructions, fmt: &mut Formatter) { 532 fmt.doc_comment( 533 r#" 534 An instruction opcode. 535 536 All instructions from all supported ISAs are present. 537 "#, 538 ); 539 fmt.line("#[repr(u8)]"); 540 fmt.line("#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]"); 541 fmt.line( 542 r#"#[cfg_attr( 543 feature = "enable-serde", 544 derive(serde_derive::Serialize, serde_derive::Deserialize) 545 )]"#, 546 ); 547 548 // We explicitly set the discriminant of the first variant to 1, which allows us to take 549 // advantage of the NonZero optimization, meaning that wrapping enums can use the 0 550 // discriminant instead of increasing the size of the whole type, and so the size of 551 // Option<Opcode> is the same as Opcode's. 552 fmt.add_block("pub enum Opcode", |fmt| { 553 let mut is_first_opcode = true; 554 for inst in all_inst.iter() { 555 fmt.doc_comment(format!("`{}`. ({})", inst, inst.format.name)); 556 557 // Document polymorphism. 558 if let Some(poly) = &inst.polymorphic_info { 559 if poly.use_typevar_operand { 560 let op_num = inst.value_opnums[inst.format.typevar_operand.unwrap()]; 561 fmt.doc_comment(format!( 562 "Type inferred from `{}`.", 563 inst.operands_in[op_num].name 564 )); 565 } 566 } 567 568 // Enum variant itself. 569 if is_first_opcode { 570 fmtln!(fmt, "{} = 1,", inst.camel_name); 571 is_first_opcode = false; 572 } else { 573 fmtln!(fmt, "{},", inst.camel_name) 574 } 575 } 576 }); 577 fmt.empty_line(); 578 579 fmt.add_block("impl Opcode", |fmt| { 580 gen_bool_accessor( 581 all_inst, 582 |inst| inst.is_terminator, 583 "is_terminator", 584 "True for instructions that terminate the block", 585 fmt, 586 ); 587 gen_bool_accessor( 588 all_inst, 589 |inst| inst.is_branch, 590 "is_branch", 591 "True for all branch or jump instructions.", 592 fmt, 593 ); 594 gen_bool_accessor( 595 all_inst, 596 |inst| inst.is_call, 597 "is_call", 598 "Is this a call instruction?", 599 fmt, 600 ); 601 gen_bool_accessor( 602 all_inst, 603 |inst| inst.is_return, 604 "is_return", 605 "Is this a return instruction?", 606 fmt, 607 ); 608 gen_bool_accessor( 609 all_inst, 610 |inst| inst.can_load, 611 "can_load", 612 "Can this instruction read from memory?", 613 fmt, 614 ); 615 gen_bool_accessor( 616 all_inst, 617 |inst| inst.can_store, 618 "can_store", 619 "Can this instruction write to memory?", 620 fmt, 621 ); 622 gen_bool_accessor( 623 all_inst, 624 |inst| inst.can_trap, 625 "can_trap", 626 "Can this instruction cause a trap?", 627 fmt, 628 ); 629 gen_bool_accessor( 630 all_inst, 631 |inst| inst.other_side_effects, 632 "other_side_effects", 633 "Does this instruction have other side effects besides can_* flags?", 634 fmt, 635 ); 636 gen_bool_accessor( 637 all_inst, 638 |inst| inst.side_effects_idempotent, 639 "side_effects_idempotent", 640 "Despite having side effects, is this instruction okay to GVN?", 641 fmt, 642 ); 643 644 // Generate an opcode list, for iterating over all known opcodes. 645 fmt.doc_comment("All cranelift opcodes."); 646 fmt.add_block("pub fn all() -> &'static [Opcode]", |fmt| { 647 fmt.line("return &["); 648 for inst in all_inst { 649 fmt.indent(|fmt| { 650 fmtln!(fmt, "Opcode::{},", inst.camel_name); 651 }); 652 } 653 fmt.line("];"); 654 }); 655 fmt.empty_line(); 656 }); 657 fmt.empty_line(); 658 659 // Generate a private opcode_format table. 660 fmtln!( 661 fmt, 662 "const OPCODE_FORMAT: [InstructionFormat; {}] = [", 663 all_inst.len() 664 ); 665 fmt.indent(|fmt| { 666 for inst in all_inst.iter() { 667 fmtln!( 668 fmt, 669 "InstructionFormat::{}, // {}", 670 inst.format.name, 671 inst.name 672 ); 673 } 674 }); 675 fmtln!(fmt, "];"); 676 fmt.empty_line(); 677 678 // Generate a private opcode_name function. 679 fmt.add_block("fn opcode_name(opc: Opcode) -> &\'static str", |fmt| { 680 let mut m = Match::new("opc"); 681 for inst in all_inst.iter() { 682 m.arm_no_fields( 683 format!("Opcode::{}", inst.camel_name), 684 format!("\"{}\"", inst.name), 685 ); 686 } 687 fmt.add_match(m); 688 }); 689 fmt.empty_line(); 690 691 // Generate an opcode hash table for looking up opcodes by name. 692 let hash_table = 693 crate::constant_hash::generate_table(all_inst.iter(), all_inst.len(), |inst| { 694 constant_hash::simple_hash(&inst.name) 695 }); 696 fmtln!( 697 fmt, 698 "const OPCODE_HASH_TABLE: [Option<Opcode>; {}] = [", 699 hash_table.len() 700 ); 701 fmt.indent(|fmt| { 702 for i in hash_table { 703 match i { 704 Some(i) => fmtln!(fmt, "Some(Opcode::{}),", i.camel_name), 705 None => fmtln!(fmt, "None,"), 706 } 707 } 708 }); 709 fmtln!(fmt, "];"); 710 fmt.empty_line(); 711 } 712 713 /// Get the value type constraint for an SSA value operand, where 714 /// `ctrl_typevar` is the controlling type variable. 715 /// 716 /// Each operand constraint is represented as a string, one of: 717 /// - `Concrete(vt)`, where `vt` is a value type name. 718 /// - `Free(idx)` where `idx` is an index into `type_sets`. 719 /// - `Same`, `Lane`, `AsTruthy` for controlling typevar-derived constraints. 720 fn get_constraint<'entries, 'table>( 721 operand: &'entries Operand, 722 ctrl_typevar: Option<&TypeVar>, 723 type_sets: &'table mut UniqueTable<'entries, TypeSet>, 724 ) -> String { 725 assert!(operand.is_value()); 726 let type_var = operand.type_var().unwrap(); 727 728 if let Some(typ) = type_var.singleton_type() { 729 return format!("Concrete({})", typ.rust_name()); 730 } 731 732 if let Some(free_typevar) = type_var.free_typevar() { 733 if ctrl_typevar.is_some() && free_typevar != *ctrl_typevar.unwrap() { 734 assert!(type_var.base.is_none()); 735 return format!("Free({})", type_sets.add(type_var.get_raw_typeset())); 736 } 737 } 738 739 if let Some(base) = &type_var.base { 740 assert!(base.type_var == *ctrl_typevar.unwrap()); 741 return camel_case(base.derived_func.name()); 742 } 743 744 assert!(type_var == ctrl_typevar.unwrap()); 745 "Same".into() 746 } 747 748 fn gen_bitset<'a, T: IntoIterator<Item = &'a u16>>( 749 iterable: T, 750 name: &'static str, 751 field_size: u8, 752 fmt: &mut Formatter, 753 ) { 754 let bits = iterable.into_iter().fold(0, |acc, x| { 755 assert!(x.is_power_of_two()); 756 assert!(u32::from(*x) < (1 << u32::from(field_size))); 757 acc | x 758 }); 759 fmtln!(fmt, "{}: ScalarBitSet::<u{}>({}),", name, field_size, bits); 760 } 761 762 fn iterable_to_string<I: fmt::Display, T: IntoIterator<Item = I>>(iterable: T) -> String { 763 let elems = iterable 764 .into_iter() 765 .map(|x| x.to_string()) 766 .collect::<Vec<_>>() 767 .join(", "); 768 format!("{{{elems}}}") 769 } 770 771 fn typeset_to_string(ts: &TypeSet) -> String { 772 let mut result = format!("TypeSet(lanes={}", iterable_to_string(&ts.lanes)); 773 if !ts.ints.is_empty() { 774 result += &format!(", ints={}", iterable_to_string(&ts.ints)); 775 } 776 if !ts.floats.is_empty() { 777 result += &format!(", floats={}", iterable_to_string(&ts.floats)); 778 } 779 result += ")"; 780 result 781 } 782 783 /// Generate the table of ValueTypeSets described by type_sets. 784 pub(crate) fn gen_typesets_table(type_sets: &UniqueTable<TypeSet>, fmt: &mut Formatter) { 785 if type_sets.len() == 0 { 786 return; 787 } 788 789 fmt.comment("Table of value type sets."); 790 assert!(type_sets.len() <= TYPESET_LIMIT, "Too many type sets!"); 791 fmtln!( 792 fmt, 793 "const TYPE_SETS: [ir::instructions::ValueTypeSet; {}] = [", 794 type_sets.len() 795 ); 796 fmt.indent(|fmt| { 797 for ts in type_sets.iter() { 798 fmt.add_block("ir::instructions::ValueTypeSet", |fmt| { 799 fmt.comment(typeset_to_string(ts)); 800 gen_bitset(&ts.lanes, "lanes", 16, fmt); 801 gen_bitset(&ts.dynamic_lanes, "dynamic_lanes", 16, fmt); 802 gen_bitset(&ts.ints, "ints", 8, fmt); 803 gen_bitset(&ts.floats, "floats", 8, fmt); 804 }); 805 fmt.line(","); 806 } 807 }); 808 fmtln!(fmt, "];"); 809 } 810 811 /// Generate value type constraints for all instructions. 812 /// - Emit a compact constant table of ValueTypeSet objects. 813 /// - Emit a compact constant table of OperandConstraint objects. 814 /// - Emit an opcode-indexed table of instruction constraints. 815 fn gen_type_constraints(all_inst: &AllInstructions, fmt: &mut Formatter) { 816 // Table of TypeSet instances. 817 let mut type_sets = UniqueTable::new(); 818 819 // Table of operand constraint sequences (as tuples). Each operand 820 // constraint is represented as a string, one of: 821 // - `Concrete(vt)`, where `vt` is a value type name. 822 // - `Free(idx)` where `idx` is an index into `type_sets`. 823 // - `Same`, `Lane`, `AsTruthy` for controlling typevar-derived constraints. 824 let mut operand_seqs = UniqueSeqTable::new(); 825 826 // Preload table with constraints for typical binops. 827 operand_seqs.add(&vec!["Same".to_string(); 3]); 828 829 fmt.comment("Table of opcode constraints."); 830 fmtln!( 831 fmt, 832 "const OPCODE_CONSTRAINTS: [OpcodeConstraints; {}] = [", 833 all_inst.len() 834 ); 835 fmt.indent(|fmt| { 836 for inst in all_inst.iter() { 837 let (ctrl_typevar, ctrl_typeset) = if let Some(poly) = &inst.polymorphic_info { 838 let index = type_sets.add(poly.ctrl_typevar.get_raw_typeset()); 839 (Some(&poly.ctrl_typevar), index) 840 } else { 841 (None, TYPESET_LIMIT) 842 }; 843 844 // Collect constraints for the value results, not including `variable_args` results 845 // which are always special cased. 846 let mut constraints = Vec::new(); 847 for &index in &inst.value_results { 848 constraints.push(get_constraint(&inst.operands_out[index], ctrl_typevar, &mut type_sets)); 849 } 850 for &index in &inst.value_opnums { 851 constraints.push(get_constraint(&inst.operands_in[index], ctrl_typevar, &mut type_sets)); 852 } 853 854 let constraint_offset = operand_seqs.add(&constraints); 855 856 let fixed_results = inst.value_results.len(); 857 let fixed_values = inst.value_opnums.len(); 858 859 // Can the controlling type variable be inferred from the designated operand? 860 let use_typevar_operand = if let Some(poly) = &inst.polymorphic_info { 861 poly.use_typevar_operand 862 } else { 863 false 864 }; 865 866 // Can the controlling type variable be inferred from the result? 867 let use_result = fixed_results > 0 && inst.operands_out[inst.value_results[0]].type_var() == ctrl_typevar; 868 869 // Are we required to use the designated operand instead of the result? 870 let requires_typevar_operand = use_typevar_operand && !use_result; 871 872 fmt.comment( 873 format!("{}: fixed_results={}, use_typevar_operand={}, requires_typevar_operand={}, fixed_values={}", 874 inst.camel_name, 875 fixed_results, 876 use_typevar_operand, 877 requires_typevar_operand, 878 fixed_values) 879 ); 880 fmt.comment(format!("Constraints=[{}]", constraints 881 .iter() 882 .map(|x| format!("'{x}'")) 883 .collect::<Vec<_>>() 884 .join(", "))); 885 if let Some(poly) = &inst.polymorphic_info { 886 fmt.comment(format!("Polymorphic over {}", typeset_to_string(poly.ctrl_typevar.get_raw_typeset()))); 887 } 888 889 // Compute the bit field encoding, c.f. instructions.rs. 890 assert!(fixed_results < 8 && fixed_values < 8, "Bit field encoding too tight"); 891 let mut flags = fixed_results; // 3 bits 892 if use_typevar_operand { 893 flags |= 1<<3; // 4th bit 894 } 895 if requires_typevar_operand { 896 flags |= 1<<4; // 5th bit 897 } 898 flags |= fixed_values << 5; // 6th bit and more 899 900 fmt.add_block("OpcodeConstraints",|fmt| { 901 fmtln!(fmt, "flags: {:#04x},", flags); 902 fmtln!(fmt, "typeset_offset: {},", ctrl_typeset); 903 fmtln!(fmt, "constraint_offset: {},", constraint_offset); 904 }); 905 fmt.line(","); 906 } 907 }); 908 fmtln!(fmt, "];"); 909 fmt.empty_line(); 910 911 gen_typesets_table(&type_sets, fmt); 912 fmt.empty_line(); 913 914 fmt.comment("Table of operand constraint sequences."); 915 fmtln!( 916 fmt, 917 "const OPERAND_CONSTRAINTS: [OperandConstraint; {}] = [", 918 operand_seqs.len() 919 ); 920 fmt.indent(|fmt| { 921 for constraint in operand_seqs.iter() { 922 fmtln!(fmt, "OperandConstraint::{},", constraint); 923 } 924 }); 925 fmtln!(fmt, "];"); 926 } 927 928 /// Emit member initializers for an instruction format. 929 fn gen_member_inits(format: &InstructionFormat, fmt: &mut Formatter) { 930 // Immediate operands. 931 // We have local variables with the same names as the members. 932 for f in &format.imm_fields { 933 fmtln!(fmt, "{},", f.member); 934 } 935 936 // Value operands. 937 if format.has_value_list { 938 fmt.line("args,"); 939 } else if format.num_value_operands == 1 { 940 fmt.line("arg: arg0,"); 941 } else if format.num_value_operands > 1 { 942 let mut args = Vec::new(); 943 for i in 0..format.num_value_operands { 944 args.push(format!("arg{i}")); 945 } 946 fmtln!(fmt, "args: [{}],", args.join(", ")); 947 } 948 949 // Block operands 950 match format.num_block_operands { 951 0 => (), 952 1 => fmt.line("destination: block0"), 953 n => { 954 let mut blocks = Vec::new(); 955 for i in 0..n { 956 blocks.push(format!("block{i}")); 957 } 958 fmtln!(fmt, "blocks: [{}],", blocks.join(", ")); 959 } 960 } 961 } 962 963 /// Emit a method for creating and inserting an instruction format. 964 /// 965 /// All instruction formats take an `opcode` argument and a `ctrl_typevar` argument for deducing 966 /// the result types. 967 fn gen_format_constructor(format: &InstructionFormat, fmt: &mut Formatter) { 968 // Construct method arguments. 969 let mut args = vec![ 970 "self".to_string(), 971 "opcode: Opcode".into(), 972 "ctrl_typevar: Type".into(), 973 ]; 974 975 // Normal operand arguments. Start with the immediate operands. 976 for f in &format.imm_fields { 977 args.push(format!("{}: {}", f.member, f.kind.rust_type)); 978 } 979 980 // Then the block operands. 981 args.extend((0..format.num_block_operands).map(|i| format!("block{i}: ir::BlockCall"))); 982 983 // Then the value operands. 984 if format.has_value_list { 985 // Take all value arguments as a finished value list. The value lists 986 // are created by the individual instruction constructors. 987 args.push("args: ir::ValueList".into()); 988 } else { 989 // Take a fixed number of value operands. 990 for i in 0..format.num_value_operands { 991 args.push(format!("arg{i}: Value")); 992 } 993 } 994 995 let proto = format!( 996 "{}({}) -> (Inst, &'f mut ir::DataFlowGraph)", 997 format.name, 998 args.join(", ") 999 ); 1000 1001 let imms_need_masking = format 1002 .imm_fields 1003 .iter() 1004 .any(|f| f.kind.rust_type == "ir::immediates::Imm64"); 1005 1006 fmt.doc_comment(format.to_string()); 1007 fmt.line("#[allow(non_snake_case, reason = \"generated code\")]"); 1008 fmt.add_block(&format!("fn {proto}"), |fmt| { 1009 // Generate the instruction data. 1010 fmt.add_block(&format!( 1011 "let{} data = ir::InstructionData::{}", 1012 if imms_need_masking { " mut" } else { "" }, 1013 format.name 1014 ), |fmt| { 1015 fmt.line("opcode,"); 1016 gen_member_inits(format, fmt); 1017 }); 1018 fmtln!(fmt, ";"); 1019 1020 if imms_need_masking { 1021 fmtln!(fmt, "data.mask_immediates(ctrl_typevar);"); 1022 } 1023 1024 // Assert that this opcode belongs to this format 1025 fmtln!(fmt, "debug_assert_eq!(opcode.format(), InstructionFormat::from(&data), \"Wrong InstructionFormat for Opcode: {{opcode}}\");"); 1026 1027 fmt.line("self.build(data, ctrl_typevar)"); 1028 }); 1029 } 1030 1031 /// Emit a method for generating the instruction `inst`. 1032 /// 1033 /// The method will create and insert an instruction, then return the result values, or the 1034 /// instruction reference itself for instructions that don't have results. 1035 fn gen_inst_builder(inst: &Instruction, format: &InstructionFormat, fmt: &mut Formatter) { 1036 // Construct method arguments. 1037 let mut args = vec![String::new()]; 1038 1039 let mut args_doc = Vec::new(); 1040 let mut rets_doc = Vec::new(); 1041 1042 // The controlling type variable will be inferred from the input values if 1043 // possible. Otherwise, it is the first method argument. 1044 if let Some(poly) = &inst.polymorphic_info { 1045 if !poly.use_typevar_operand { 1046 args.push(format!("{}: crate::ir::Type", poly.ctrl_typevar.name)); 1047 args_doc.push(format!( 1048 "- {} (controlling type variable): {}", 1049 poly.ctrl_typevar.name, poly.ctrl_typevar.doc 1050 )); 1051 } 1052 } 1053 1054 let mut tmpl_types = Vec::new(); 1055 let mut into_args = Vec::new(); 1056 let mut block_args = Vec::new(); 1057 let mut lifetime_param = None; 1058 for op in &inst.operands_in { 1059 if op.kind.is_block() { 1060 args.push(format!("{}_label: {}", op.name, "ir::Block")); 1061 args_doc.push(format!( 1062 "- {}_label: {}", 1063 op.name, "Destination basic block" 1064 )); 1065 1066 let lifetime = *lifetime_param.get_or_insert_with(|| { 1067 tmpl_types.insert(0, "'a".to_string()); 1068 "'a" 1069 }); 1070 args.push(format!( 1071 "{}_args: impl IntoIterator<Item = &{} BlockArg>", 1072 op.name, lifetime, 1073 )); 1074 args_doc.push(format!("- {}_args: {}", op.name, "Block arguments")); 1075 1076 block_args.push(op); 1077 } else { 1078 let t = if op.is_immediate() { 1079 let t = format!("T{}", tmpl_types.len() + 1); 1080 tmpl_types.push(format!("{}: Into<{}>", t, op.kind.rust_type)); 1081 into_args.push(op.name); 1082 t 1083 } else { 1084 op.kind.rust_type.to_string() 1085 }; 1086 args.push(format!("{}: {}", op.name, t)); 1087 args_doc.push(format!("- {}: {}", op.name, op.doc())); 1088 } 1089 } 1090 1091 // We need to mutate `self` if this instruction accepts a value list, or will construct 1092 // BlockCall values. 1093 if format.has_value_list || !block_args.is_empty() { 1094 args[0].push_str("mut self"); 1095 } else { 1096 args[0].push_str("self"); 1097 } 1098 1099 for op in &inst.operands_out { 1100 rets_doc.push(format!("- {}: {}", op.name, op.doc())); 1101 } 1102 1103 let rtype = match inst.value_results.len() { 1104 0 => "Inst".into(), 1105 1 => "Value".into(), 1106 _ => format!("({})", vec!["Value"; inst.value_results.len()].join(", ")), 1107 }; 1108 1109 let tmpl = if !tmpl_types.is_empty() { 1110 format!("<{}>", tmpl_types.join(", ")) 1111 } else { 1112 "".into() 1113 }; 1114 1115 let proto = format!( 1116 "{}{}({}) -> {}", 1117 inst.snake_name(), 1118 tmpl, 1119 args.join(", "), 1120 rtype 1121 ); 1122 1123 fmt.doc_comment(&inst.doc); 1124 if !args_doc.is_empty() { 1125 fmt.line("///"); 1126 fmt.doc_comment("Inputs:"); 1127 fmt.line("///"); 1128 for doc_line in args_doc { 1129 fmt.doc_comment(doc_line); 1130 } 1131 } 1132 if !rets_doc.is_empty() { 1133 fmt.line("///"); 1134 fmt.doc_comment("Outputs:"); 1135 fmt.line("///"); 1136 for doc_line in rets_doc { 1137 fmt.doc_comment(doc_line); 1138 } 1139 } 1140 1141 fmt.line("#[allow(non_snake_case, reason = \"generated code\")]"); 1142 fmt.add_block(&format!("fn {proto}"), |fmt| { 1143 // Convert all of the `Into<>` arguments. 1144 for arg in into_args { 1145 fmtln!(fmt, "let {} = {}.into();", arg, arg); 1146 } 1147 1148 // Convert block references 1149 for op in block_args { 1150 fmtln!( 1151 fmt, 1152 "let {0} = self.data_flow_graph_mut().block_call({0}_label, {0}_args);", 1153 op.name 1154 ); 1155 } 1156 1157 // Arguments for instruction constructor. 1158 let first_arg = format!("Opcode::{}", inst.camel_name); 1159 let mut args = vec![first_arg.as_str()]; 1160 if let Some(poly) = &inst.polymorphic_info { 1161 if poly.use_typevar_operand { 1162 // Infer the controlling type variable from the input operands. 1163 let op_num = inst.value_opnums[format.typevar_operand.unwrap()]; 1164 fmtln!( 1165 fmt, 1166 "let ctrl_typevar = self.data_flow_graph().value_type({});", 1167 inst.operands_in[op_num].name 1168 ); 1169 1170 // The format constructor will resolve the result types from the type var. 1171 args.push("ctrl_typevar"); 1172 } else { 1173 // This was an explicit method argument. 1174 args.push(&poly.ctrl_typevar.name); 1175 } 1176 } else { 1177 // No controlling type variable needed. 1178 args.push("types::INVALID"); 1179 } 1180 1181 // Now add all of the immediate operands to the constructor arguments. 1182 for &op_num in &inst.imm_opnums { 1183 args.push(inst.operands_in[op_num].name); 1184 } 1185 1186 // Finally, the value operands. 1187 if format.has_value_list { 1188 // We need to build a value list with all the arguments. 1189 fmt.line("let mut vlist = ir::ValueList::default();"); 1190 args.push("vlist"); 1191 fmt.line("{"); 1192 fmt.indent(|fmt| { 1193 fmt.line("let pool = &mut self.data_flow_graph_mut().value_lists;"); 1194 for op in &inst.operands_in { 1195 if op.is_value() { 1196 fmtln!(fmt, "vlist.push({}, pool);", op.name); 1197 } else if op.is_varargs() { 1198 fmtln!(fmt, "vlist.extend({}.iter().cloned(), pool);", op.name); 1199 } 1200 } 1201 }); 1202 fmt.line("}"); 1203 } else { 1204 // With no value list, we're guaranteed to just have a set of fixed value operands. 1205 for &op_num in &inst.value_opnums { 1206 args.push(inst.operands_in[op_num].name); 1207 } 1208 } 1209 1210 // Call to the format constructor, 1211 let fcall = format!("self.{}({})", format.name, args.join(", ")); 1212 1213 fmtln!(fmt, "let (inst, dfg) = {};", fcall); 1214 fmtln!( 1215 fmt, 1216 "crate::trace!(\"inserted {{inst:?}}: {{}}\", dfg.display_inst(inst));" 1217 ); 1218 1219 if inst.value_results.is_empty() { 1220 fmtln!(fmt, "inst"); 1221 return; 1222 } 1223 1224 if inst.value_results.len() == 1 { 1225 fmt.line("dfg.first_result(inst)"); 1226 } else { 1227 fmtln!( 1228 fmt, 1229 "let results = &dfg.inst_results(inst)[0..{}];", 1230 inst.value_results.len() 1231 ); 1232 fmtln!( 1233 fmt, 1234 "({})", 1235 inst.value_results 1236 .iter() 1237 .enumerate() 1238 .map(|(i, _)| format!("results[{i}]")) 1239 .collect::<Vec<_>>() 1240 .join(", ") 1241 ); 1242 } 1243 }); 1244 } 1245 1246 /// Generate a Builder trait with methods for all instructions. 1247 fn gen_builder( 1248 instructions: &AllInstructions, 1249 formats: &[Rc<InstructionFormat>], 1250 fmt: &mut Formatter, 1251 ) { 1252 fmt.doc_comment( 1253 r#" 1254 Convenience methods for building instructions. 1255 1256 The `InstBuilder` trait has one method per instruction opcode for 1257 conveniently constructing the instruction with minimum arguments. 1258 Polymorphic instructions infer their result types from the input 1259 arguments when possible. In some cases, an explicit `ctrl_typevar` 1260 argument is required. 1261 1262 The opcode methods return the new instruction's result values, or 1263 the `Inst` itself for instructions that don't have any results. 1264 1265 There is also a method per instruction format. These methods all 1266 return an `Inst`. 1267 1268 When an address to a load or store is specified, its integer 1269 size is required to be equal to the platform's pointer width. 1270 "#, 1271 ); 1272 fmt.add_block("pub trait InstBuilder<'f>: InstBuilderBase<'f>", |fmt| { 1273 for inst in instructions.iter() { 1274 gen_inst_builder(inst, &inst.format, fmt); 1275 fmt.empty_line(); 1276 } 1277 for (i, format) in formats.iter().enumerate() { 1278 gen_format_constructor(format, fmt); 1279 if i + 1 != formats.len() { 1280 fmt.empty_line(); 1281 } 1282 } 1283 }); 1284 } 1285 1286 pub(crate) fn generate( 1287 formats: &[Rc<InstructionFormat>], 1288 all_inst: &AllInstructions, 1289 opcode_filename: &str, 1290 inst_builder_filename: &str, 1291 out_dir: &std::path::Path, 1292 ) -> Result<(), error::Error> { 1293 // Opcodes. 1294 let mut fmt = Formatter::new(Language::Rust); 1295 gen_formats(&formats, &mut fmt); 1296 gen_instruction_data(&formats, &mut fmt); 1297 fmt.empty_line(); 1298 gen_instruction_data_impl(&formats, &mut fmt); 1299 fmt.empty_line(); 1300 gen_opcodes(all_inst, &mut fmt); 1301 fmt.empty_line(); 1302 gen_type_constraints(all_inst, &mut fmt); 1303 fmt.write(opcode_filename, out_dir)?; 1304 1305 // Instruction builder. 1306 let mut fmt = Formatter::new(Language::Rust); 1307 gen_builder(all_inst, &formats, &mut fmt); 1308 fmt.write(inst_builder_filename, out_dir)?; 1309 1310 Ok(()) 1311 } 1312