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; 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)]"); 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 }); 418 } 419 420 fn gen_bool_accessor<T: Fn(&Instruction) -> bool>( 421 all_inst: &AllInstructions, 422 get_attr: T, 423 name: &'static str, 424 doc: &'static str, 425 fmt: &mut Formatter, 426 ) { 427 fmt.doc_comment(doc); 428 fmt.add_block(&format!("pub fn {name}(self) -> bool"), |fmt| { 429 let mut m = Match::new("self"); 430 for inst in all_inst.iter() { 431 if get_attr(inst) { 432 m.arm_no_fields(format!("Self::{}", inst.camel_name), "true"); 433 } 434 } 435 m.arm_no_fields("_", "false"); 436 fmt.add_match(m); 437 }); 438 fmt.empty_line(); 439 } 440 441 fn gen_opcodes(all_inst: &AllInstructions, fmt: &mut Formatter) { 442 fmt.doc_comment( 443 r#" 444 An instruction opcode. 445 446 All instructions from all supported ISAs are present. 447 "#, 448 ); 449 fmt.line("#[repr(u8)]"); 450 fmt.line("#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]"); 451 fmt.line( 452 r#"#[cfg_attr( 453 feature = "enable-serde", 454 derive(serde_derive::Serialize, serde_derive::Deserialize) 455 )]"#, 456 ); 457 458 // We explicitly set the discriminant of the first variant to 1, which allows us to take 459 // advantage of the NonZero optimization, meaning that wrapping enums can use the 0 460 // discriminant instead of increasing the size of the whole type, and so the size of 461 // Option<Opcode> is the same as Opcode's. 462 fmt.add_block("pub enum Opcode", |fmt| { 463 let mut is_first_opcode = true; 464 for inst in all_inst.iter() { 465 fmt.doc_comment(format!("`{}`. ({})", inst, inst.format.name)); 466 467 // Document polymorphism. 468 if let Some(poly) = &inst.polymorphic_info { 469 if poly.use_typevar_operand { 470 let op_num = inst.value_opnums[inst.format.typevar_operand.unwrap()]; 471 fmt.doc_comment(format!( 472 "Type inferred from `{}`.", 473 inst.operands_in[op_num].name 474 )); 475 } 476 } 477 478 // Enum variant itself. 479 if is_first_opcode { 480 fmtln!(fmt, "{} = 1,", inst.camel_name); 481 is_first_opcode = false; 482 } else { 483 fmtln!(fmt, "{},", inst.camel_name) 484 } 485 } 486 }); 487 fmt.empty_line(); 488 489 fmt.add_block("impl Opcode", |fmt| { 490 gen_bool_accessor( 491 all_inst, 492 |inst| inst.is_terminator, 493 "is_terminator", 494 "True for instructions that terminate the block", 495 fmt, 496 ); 497 gen_bool_accessor( 498 all_inst, 499 |inst| inst.is_branch, 500 "is_branch", 501 "True for all branch or jump instructions.", 502 fmt, 503 ); 504 gen_bool_accessor( 505 all_inst, 506 |inst| inst.is_call, 507 "is_call", 508 "Is this a call instruction?", 509 fmt, 510 ); 511 gen_bool_accessor( 512 all_inst, 513 |inst| inst.is_return, 514 "is_return", 515 "Is this a return instruction?", 516 fmt, 517 ); 518 gen_bool_accessor( 519 all_inst, 520 |inst| inst.can_load, 521 "can_load", 522 "Can this instruction read from memory?", 523 fmt, 524 ); 525 gen_bool_accessor( 526 all_inst, 527 |inst| inst.can_store, 528 "can_store", 529 "Can this instruction write to memory?", 530 fmt, 531 ); 532 gen_bool_accessor( 533 all_inst, 534 |inst| inst.can_trap, 535 "can_trap", 536 "Can this instruction cause a trap?", 537 fmt, 538 ); 539 gen_bool_accessor( 540 all_inst, 541 |inst| inst.other_side_effects, 542 "other_side_effects", 543 "Does this instruction have other side effects besides can_* flags?", 544 fmt, 545 ); 546 gen_bool_accessor( 547 all_inst, 548 |inst| inst.side_effects_idempotent, 549 "side_effects_idempotent", 550 "Despite having side effects, is this instruction okay to GVN?", 551 fmt, 552 ); 553 554 // Generate an opcode list, for iterating over all known opcodes. 555 fmt.doc_comment("All cranelift opcodes."); 556 fmt.add_block("pub fn all() -> &'static [Opcode]", |fmt| { 557 fmt.line("return &["); 558 for inst in all_inst { 559 fmt.indent(|fmt| { 560 fmtln!(fmt, "Opcode::{},", inst.camel_name); 561 }); 562 } 563 fmt.line("];"); 564 }); 565 fmt.empty_line(); 566 }); 567 fmt.empty_line(); 568 569 // Generate a private opcode_format table. 570 fmtln!( 571 fmt, 572 "const OPCODE_FORMAT: [InstructionFormat; {}] = [", 573 all_inst.len() 574 ); 575 fmt.indent(|fmt| { 576 for inst in all_inst.iter() { 577 fmtln!( 578 fmt, 579 "InstructionFormat::{}, // {}", 580 inst.format.name, 581 inst.name 582 ); 583 } 584 }); 585 fmtln!(fmt, "];"); 586 fmt.empty_line(); 587 588 // Generate a private opcode_name function. 589 fmt.add_block("fn opcode_name(opc: Opcode) -> &\'static str", |fmt| { 590 let mut m = Match::new("opc"); 591 for inst in all_inst.iter() { 592 m.arm_no_fields( 593 format!("Opcode::{}", inst.camel_name), 594 format!("\"{}\"", inst.name), 595 ); 596 } 597 fmt.add_match(m); 598 }); 599 fmt.empty_line(); 600 601 // Generate an opcode hash table for looking up opcodes by name. 602 let hash_table = 603 crate::constant_hash::generate_table(all_inst.iter(), all_inst.len(), |inst| { 604 constant_hash::simple_hash(&inst.name) 605 }); 606 fmtln!( 607 fmt, 608 "const OPCODE_HASH_TABLE: [Option<Opcode>; {}] = [", 609 hash_table.len() 610 ); 611 fmt.indent(|fmt| { 612 for i in hash_table { 613 match i { 614 Some(i) => fmtln!(fmt, "Some(Opcode::{}),", i.camel_name), 615 None => fmtln!(fmt, "None,"), 616 } 617 } 618 }); 619 fmtln!(fmt, "];"); 620 fmt.empty_line(); 621 } 622 623 /// Get the value type constraint for an SSA value operand, where 624 /// `ctrl_typevar` is the controlling type variable. 625 /// 626 /// Each operand constraint is represented as a string, one of: 627 /// - `Concrete(vt)`, where `vt` is a value type name. 628 /// - `Free(idx)` where `idx` is an index into `type_sets`. 629 /// - `Same`, `Lane`, `AsTruthy` for controlling typevar-derived constraints. 630 fn get_constraint<'entries, 'table>( 631 operand: &'entries Operand, 632 ctrl_typevar: Option<&TypeVar>, 633 type_sets: &'table mut UniqueTable<'entries, TypeSet>, 634 ) -> String { 635 assert!(operand.is_value()); 636 let type_var = operand.type_var().unwrap(); 637 638 if let Some(typ) = type_var.singleton_type() { 639 return format!("Concrete({})", typ.rust_name()); 640 } 641 642 if let Some(free_typevar) = type_var.free_typevar() { 643 if ctrl_typevar.is_some() && free_typevar != *ctrl_typevar.unwrap() { 644 assert!(type_var.base.is_none()); 645 return format!("Free({})", type_sets.add(type_var.get_raw_typeset())); 646 } 647 } 648 649 if let Some(base) = &type_var.base { 650 assert!(base.type_var == *ctrl_typevar.unwrap()); 651 return camel_case(base.derived_func.name()); 652 } 653 654 assert!(type_var == ctrl_typevar.unwrap()); 655 "Same".into() 656 } 657 658 fn gen_bitset<'a, T: IntoIterator<Item = &'a u16>>( 659 iterable: T, 660 name: &'static str, 661 field_size: u8, 662 fmt: &mut Formatter, 663 ) { 664 let bits = iterable.into_iter().fold(0, |acc, x| { 665 assert!(x.is_power_of_two()); 666 assert!(u32::from(*x) < (1 << u32::from(field_size))); 667 acc | x 668 }); 669 fmtln!(fmt, "{}: ScalarBitSet::<u{}>({}),", name, field_size, bits); 670 } 671 672 fn iterable_to_string<I: fmt::Display, T: IntoIterator<Item = I>>(iterable: T) -> String { 673 let elems = iterable 674 .into_iter() 675 .map(|x| x.to_string()) 676 .collect::<Vec<_>>() 677 .join(", "); 678 format!("{{{elems}}}") 679 } 680 681 fn typeset_to_string(ts: &TypeSet) -> String { 682 let mut result = format!("TypeSet(lanes={}", iterable_to_string(&ts.lanes)); 683 if !ts.ints.is_empty() { 684 result += &format!(", ints={}", iterable_to_string(&ts.ints)); 685 } 686 if !ts.floats.is_empty() { 687 result += &format!(", floats={}", iterable_to_string(&ts.floats)); 688 } 689 result += ")"; 690 result 691 } 692 693 /// Generate the table of ValueTypeSets described by type_sets. 694 pub(crate) fn gen_typesets_table(type_sets: &UniqueTable<TypeSet>, fmt: &mut Formatter) { 695 if type_sets.len() == 0 { 696 return; 697 } 698 699 fmt.comment("Table of value type sets."); 700 assert!(type_sets.len() <= TYPESET_LIMIT, "Too many type sets!"); 701 fmtln!( 702 fmt, 703 "const TYPE_SETS: [ir::instructions::ValueTypeSet; {}] = [", 704 type_sets.len() 705 ); 706 fmt.indent(|fmt| { 707 for ts in type_sets.iter() { 708 fmt.add_block("ir::instructions::ValueTypeSet", |fmt| { 709 fmt.comment(typeset_to_string(ts)); 710 gen_bitset(&ts.lanes, "lanes", 16, fmt); 711 gen_bitset(&ts.dynamic_lanes, "dynamic_lanes", 16, fmt); 712 gen_bitset(&ts.ints, "ints", 8, fmt); 713 gen_bitset(&ts.floats, "floats", 8, fmt); 714 }); 715 fmt.line(","); 716 } 717 }); 718 fmtln!(fmt, "];"); 719 } 720 721 /// Generate value type constraints for all instructions. 722 /// - Emit a compact constant table of ValueTypeSet objects. 723 /// - Emit a compact constant table of OperandConstraint objects. 724 /// - Emit an opcode-indexed table of instruction constraints. 725 fn gen_type_constraints(all_inst: &AllInstructions, fmt: &mut Formatter) { 726 // Table of TypeSet instances. 727 let mut type_sets = UniqueTable::new(); 728 729 // Table of operand constraint sequences (as tuples). Each operand 730 // constraint is represented as a string, one of: 731 // - `Concrete(vt)`, where `vt` is a value type name. 732 // - `Free(idx)` where `idx` is an index into `type_sets`. 733 // - `Same`, `Lane`, `AsTruthy` for controlling typevar-derived constraints. 734 let mut operand_seqs = UniqueSeqTable::new(); 735 736 // Preload table with constraints for typical binops. 737 operand_seqs.add(&vec!["Same".to_string(); 3]); 738 739 fmt.comment("Table of opcode constraints."); 740 fmtln!( 741 fmt, 742 "const OPCODE_CONSTRAINTS: [OpcodeConstraints; {}] = [", 743 all_inst.len() 744 ); 745 fmt.indent(|fmt| { 746 for inst in all_inst.iter() { 747 let (ctrl_typevar, ctrl_typeset) = if let Some(poly) = &inst.polymorphic_info { 748 let index = type_sets.add(poly.ctrl_typevar.get_raw_typeset()); 749 (Some(&poly.ctrl_typevar), index) 750 } else { 751 (None, TYPESET_LIMIT) 752 }; 753 754 // Collect constraints for the value results, not including `variable_args` results 755 // which are always special cased. 756 let mut constraints = Vec::new(); 757 for &index in &inst.value_results { 758 constraints.push(get_constraint(&inst.operands_out[index], ctrl_typevar, &mut type_sets)); 759 } 760 for &index in &inst.value_opnums { 761 constraints.push(get_constraint(&inst.operands_in[index], ctrl_typevar, &mut type_sets)); 762 } 763 764 let constraint_offset = operand_seqs.add(&constraints); 765 766 let fixed_results = inst.value_results.len(); 767 let fixed_values = inst.value_opnums.len(); 768 769 // Can the controlling type variable be inferred from the designated operand? 770 let use_typevar_operand = if let Some(poly) = &inst.polymorphic_info { 771 poly.use_typevar_operand 772 } else { 773 false 774 }; 775 776 // Can the controlling type variable be inferred from the result? 777 let use_result = fixed_results > 0 && inst.operands_out[inst.value_results[0]].type_var() == ctrl_typevar; 778 779 // Are we required to use the designated operand instead of the result? 780 let requires_typevar_operand = use_typevar_operand && !use_result; 781 782 fmt.comment( 783 format!("{}: fixed_results={}, use_typevar_operand={}, requires_typevar_operand={}, fixed_values={}", 784 inst.camel_name, 785 fixed_results, 786 use_typevar_operand, 787 requires_typevar_operand, 788 fixed_values) 789 ); 790 fmt.comment(format!("Constraints=[{}]", constraints 791 .iter() 792 .map(|x| format!("'{x}'")) 793 .collect::<Vec<_>>() 794 .join(", "))); 795 if let Some(poly) = &inst.polymorphic_info { 796 fmt.comment(format!("Polymorphic over {}", typeset_to_string(poly.ctrl_typevar.get_raw_typeset()))); 797 } 798 799 // Compute the bit field encoding, c.f. instructions.rs. 800 assert!(fixed_results < 8 && fixed_values < 8, "Bit field encoding too tight"); 801 let mut flags = fixed_results; // 3 bits 802 if use_typevar_operand { 803 flags |= 1<<3; // 4th bit 804 } 805 if requires_typevar_operand { 806 flags |= 1<<4; // 5th bit 807 } 808 flags |= fixed_values << 5; // 6th bit and more 809 810 fmt.add_block("OpcodeConstraints",|fmt| { 811 fmtln!(fmt, "flags: {:#04x},", flags); 812 fmtln!(fmt, "typeset_offset: {},", ctrl_typeset); 813 fmtln!(fmt, "constraint_offset: {},", constraint_offset); 814 }); 815 fmt.line(","); 816 } 817 }); 818 fmtln!(fmt, "];"); 819 fmt.empty_line(); 820 821 gen_typesets_table(&type_sets, fmt); 822 fmt.empty_line(); 823 824 fmt.comment("Table of operand constraint sequences."); 825 fmtln!( 826 fmt, 827 "const OPERAND_CONSTRAINTS: [OperandConstraint; {}] = [", 828 operand_seqs.len() 829 ); 830 fmt.indent(|fmt| { 831 for constraint in operand_seqs.iter() { 832 fmtln!(fmt, "OperandConstraint::{},", constraint); 833 } 834 }); 835 fmtln!(fmt, "];"); 836 } 837 838 /// Emit member initializers for an instruction format. 839 fn gen_member_inits(format: &InstructionFormat, fmt: &mut Formatter) { 840 // Immediate operands. 841 // We have local variables with the same names as the members. 842 for f in &format.imm_fields { 843 fmtln!(fmt, "{},", f.member); 844 } 845 846 // Value operands. 847 if format.has_value_list { 848 fmt.line("args,"); 849 } else if format.num_value_operands == 1 { 850 fmt.line("arg: arg0,"); 851 } else if format.num_value_operands > 1 { 852 let mut args = Vec::new(); 853 for i in 0..format.num_value_operands { 854 args.push(format!("arg{i}")); 855 } 856 fmtln!(fmt, "args: [{}],", args.join(", ")); 857 } 858 859 // Block operands 860 match format.num_block_operands { 861 0 => (), 862 1 => fmt.line("destination: block0"), 863 n => { 864 let mut blocks = Vec::new(); 865 for i in 0..n { 866 blocks.push(format!("block{i}")); 867 } 868 fmtln!(fmt, "blocks: [{}],", blocks.join(", ")); 869 } 870 } 871 } 872 873 /// Emit a method for creating and inserting an instruction format. 874 /// 875 /// All instruction formats take an `opcode` argument and a `ctrl_typevar` argument for deducing 876 /// the result types. 877 fn gen_format_constructor(format: &InstructionFormat, fmt: &mut Formatter) { 878 // Construct method arguments. 879 let mut args = vec![ 880 "self".to_string(), 881 "opcode: Opcode".into(), 882 "ctrl_typevar: Type".into(), 883 ]; 884 885 // Normal operand arguments. Start with the immediate operands. 886 for f in &format.imm_fields { 887 args.push(format!("{}: {}", f.member, f.kind.rust_type)); 888 } 889 890 // Then the block operands. 891 args.extend((0..format.num_block_operands).map(|i| format!("block{i}: ir::BlockCall"))); 892 893 // Then the value operands. 894 if format.has_value_list { 895 // Take all value arguments as a finished value list. The value lists 896 // are created by the individual instruction constructors. 897 args.push("args: ir::ValueList".into()); 898 } else { 899 // Take a fixed number of value operands. 900 for i in 0..format.num_value_operands { 901 args.push(format!("arg{i}: Value")); 902 } 903 } 904 905 let proto = format!( 906 "{}({}) -> (Inst, &'f mut ir::DataFlowGraph)", 907 format.name, 908 args.join(", ") 909 ); 910 911 let imms_need_masking = format 912 .imm_fields 913 .iter() 914 .any(|f| f.kind.rust_type == "ir::immediates::Imm64"); 915 916 fmt.doc_comment(format.to_string()); 917 fmt.line("#[allow(non_snake_case)]"); 918 fmt.add_block(&format!("fn {proto}"), |fmt| { 919 // Generate the instruction data. 920 fmt.add_block(&format!( 921 "let{} data = ir::InstructionData::{}", 922 if imms_need_masking { " mut" } else { "" }, 923 format.name 924 ), |fmt| { 925 fmt.line("opcode,"); 926 gen_member_inits(format, fmt); 927 }); 928 fmtln!(fmt, ";"); 929 930 if imms_need_masking { 931 fmtln!(fmt, "data.mask_immediates(ctrl_typevar);"); 932 } 933 934 // Assert that this opcode belongs to this format 935 fmtln!(fmt, "debug_assert_eq!(opcode.format(), InstructionFormat::from(&data), \"Wrong InstructionFormat for Opcode: {{opcode}}\");"); 936 937 fmt.line("self.build(data, ctrl_typevar)"); 938 }); 939 } 940 941 /// Emit a method for generating the instruction `inst`. 942 /// 943 /// The method will create and insert an instruction, then return the result values, or the 944 /// instruction reference itself for instructions that don't have results. 945 fn gen_inst_builder(inst: &Instruction, format: &InstructionFormat, fmt: &mut Formatter) { 946 // Construct method arguments. 947 let mut args = vec![String::new()]; 948 949 let mut args_doc = Vec::new(); 950 let mut rets_doc = Vec::new(); 951 952 // The controlling type variable will be inferred from the input values if 953 // possible. Otherwise, it is the first method argument. 954 if let Some(poly) = &inst.polymorphic_info { 955 if !poly.use_typevar_operand { 956 args.push(format!("{}: crate::ir::Type", poly.ctrl_typevar.name)); 957 args_doc.push(format!( 958 "- {} (controlling type variable): {}", 959 poly.ctrl_typevar.name, poly.ctrl_typevar.doc 960 )); 961 } 962 } 963 964 let mut tmpl_types = Vec::new(); 965 let mut into_args = Vec::new(); 966 let mut block_args = Vec::new(); 967 let mut lifetime_param = None; 968 for op in &inst.operands_in { 969 if op.kind.is_block() { 970 args.push(format!("{}_label: {}", op.name, "ir::Block")); 971 args_doc.push(format!( 972 "- {}_label: {}", 973 op.name, "Destination basic block" 974 )); 975 976 let lifetime = *lifetime_param.get_or_insert_with(|| { 977 tmpl_types.insert(0, "'a".to_string()); 978 "'a" 979 }); 980 args.push(format!( 981 "{}_args: impl IntoIterator<Item = &{} BlockArg>", 982 op.name, lifetime, 983 )); 984 args_doc.push(format!("- {}_args: {}", op.name, "Block arguments")); 985 986 block_args.push(op); 987 } else { 988 let t = if op.is_immediate() { 989 let t = format!("T{}", tmpl_types.len() + 1); 990 tmpl_types.push(format!("{}: Into<{}>", t, op.kind.rust_type)); 991 into_args.push(op.name); 992 t 993 } else { 994 op.kind.rust_type.to_string() 995 }; 996 args.push(format!("{}: {}", op.name, t)); 997 args_doc.push(format!("- {}: {}", op.name, op.doc())); 998 } 999 } 1000 1001 // We need to mutate `self` if this instruction accepts a value list, or will construct 1002 // BlockCall values. 1003 if format.has_value_list || !block_args.is_empty() { 1004 args[0].push_str("mut self"); 1005 } else { 1006 args[0].push_str("self"); 1007 } 1008 1009 for op in &inst.operands_out { 1010 rets_doc.push(format!("- {}: {}", op.name, op.doc())); 1011 } 1012 1013 let rtype = match inst.value_results.len() { 1014 0 => "Inst".into(), 1015 1 => "Value".into(), 1016 _ => format!("({})", vec!["Value"; inst.value_results.len()].join(", ")), 1017 }; 1018 1019 let tmpl = if !tmpl_types.is_empty() { 1020 format!("<{}>", tmpl_types.join(", ")) 1021 } else { 1022 "".into() 1023 }; 1024 1025 let proto = format!( 1026 "{}{}({}) -> {}", 1027 inst.snake_name(), 1028 tmpl, 1029 args.join(", "), 1030 rtype 1031 ); 1032 1033 fmt.doc_comment(&inst.doc); 1034 if !args_doc.is_empty() { 1035 fmt.line("///"); 1036 fmt.doc_comment("Inputs:"); 1037 fmt.line("///"); 1038 for doc_line in args_doc { 1039 fmt.doc_comment(doc_line); 1040 } 1041 } 1042 if !rets_doc.is_empty() { 1043 fmt.line("///"); 1044 fmt.doc_comment("Outputs:"); 1045 fmt.line("///"); 1046 for doc_line in rets_doc { 1047 fmt.doc_comment(doc_line); 1048 } 1049 } 1050 1051 fmt.line("#[allow(non_snake_case)]"); 1052 fmt.add_block(&format!("fn {proto}"), |fmt| { 1053 // Convert all of the `Into<>` arguments. 1054 for arg in into_args { 1055 fmtln!(fmt, "let {} = {}.into();", arg, arg); 1056 } 1057 1058 // Convert block references 1059 for op in block_args { 1060 fmtln!( 1061 fmt, 1062 "let {0} = self.data_flow_graph_mut().block_call({0}_label, {0}_args);", 1063 op.name 1064 ); 1065 } 1066 1067 // Arguments for instruction constructor. 1068 let first_arg = format!("Opcode::{}", inst.camel_name); 1069 let mut args = vec![first_arg.as_str()]; 1070 if let Some(poly) = &inst.polymorphic_info { 1071 if poly.use_typevar_operand { 1072 // Infer the controlling type variable from the input operands. 1073 let op_num = inst.value_opnums[format.typevar_operand.unwrap()]; 1074 fmtln!( 1075 fmt, 1076 "let ctrl_typevar = self.data_flow_graph().value_type({});", 1077 inst.operands_in[op_num].name 1078 ); 1079 1080 // The format constructor will resolve the result types from the type var. 1081 args.push("ctrl_typevar"); 1082 } else { 1083 // This was an explicit method argument. 1084 args.push(&poly.ctrl_typevar.name); 1085 } 1086 } else { 1087 // No controlling type variable needed. 1088 args.push("types::INVALID"); 1089 } 1090 1091 // Now add all of the immediate operands to the constructor arguments. 1092 for &op_num in &inst.imm_opnums { 1093 args.push(inst.operands_in[op_num].name); 1094 } 1095 1096 // Finally, the value operands. 1097 if format.has_value_list { 1098 // We need to build a value list with all the arguments. 1099 fmt.line("let mut vlist = ir::ValueList::default();"); 1100 args.push("vlist"); 1101 fmt.line("{"); 1102 fmt.indent(|fmt| { 1103 fmt.line("let pool = &mut self.data_flow_graph_mut().value_lists;"); 1104 for op in &inst.operands_in { 1105 if op.is_value() { 1106 fmtln!(fmt, "vlist.push({}, pool);", op.name); 1107 } else if op.is_varargs() { 1108 fmtln!(fmt, "vlist.extend({}.iter().cloned(), pool);", op.name); 1109 } 1110 } 1111 }); 1112 fmt.line("}"); 1113 } else { 1114 // With no value list, we're guaranteed to just have a set of fixed value operands. 1115 for &op_num in &inst.value_opnums { 1116 args.push(inst.operands_in[op_num].name); 1117 } 1118 } 1119 1120 // Call to the format constructor, 1121 let fcall = format!("self.{}({})", format.name, args.join(", ")); 1122 1123 fmtln!(fmt, "let (inst, dfg) = {};", fcall); 1124 fmtln!( 1125 fmt, 1126 "crate::trace!(\"inserted {{inst:?}}: {{}}\", dfg.display_inst(inst));" 1127 ); 1128 1129 if inst.value_results.is_empty() { 1130 fmtln!(fmt, "inst"); 1131 return; 1132 } 1133 1134 if inst.value_results.len() == 1 { 1135 fmt.line("dfg.first_result(inst)"); 1136 } else { 1137 fmtln!( 1138 fmt, 1139 "let results = &dfg.inst_results(inst)[0..{}];", 1140 inst.value_results.len() 1141 ); 1142 fmtln!( 1143 fmt, 1144 "({})", 1145 inst.value_results 1146 .iter() 1147 .enumerate() 1148 .map(|(i, _)| format!("results[{i}]")) 1149 .collect::<Vec<_>>() 1150 .join(", ") 1151 ); 1152 } 1153 }); 1154 } 1155 1156 /// Generate a Builder trait with methods for all instructions. 1157 fn gen_builder( 1158 instructions: &AllInstructions, 1159 formats: &[Rc<InstructionFormat>], 1160 fmt: &mut Formatter, 1161 ) { 1162 fmt.doc_comment( 1163 r#" 1164 Convenience methods for building instructions. 1165 1166 The `InstBuilder` trait has one method per instruction opcode for 1167 conveniently constructing the instruction with minimum arguments. 1168 Polymorphic instructions infer their result types from the input 1169 arguments when possible. In some cases, an explicit `ctrl_typevar` 1170 argument is required. 1171 1172 The opcode methods return the new instruction's result values, or 1173 the `Inst` itself for instructions that don't have any results. 1174 1175 There is also a method per instruction format. These methods all 1176 return an `Inst`. 1177 1178 When an address to a load or store is specified, its integer 1179 size is required to be equal to the platform's pointer width. 1180 "#, 1181 ); 1182 fmt.add_block("pub trait InstBuilder<'f>: InstBuilderBase<'f>", |fmt| { 1183 for inst in instructions.iter() { 1184 gen_inst_builder(inst, &inst.format, fmt); 1185 fmt.empty_line(); 1186 } 1187 for (i, format) in formats.iter().enumerate() { 1188 gen_format_constructor(format, fmt); 1189 if i + 1 != formats.len() { 1190 fmt.empty_line(); 1191 } 1192 } 1193 }); 1194 } 1195 1196 pub(crate) fn generate( 1197 formats: &[Rc<InstructionFormat>], 1198 all_inst: &AllInstructions, 1199 opcode_filename: &str, 1200 inst_builder_filename: &str, 1201 out_dir: &std::path::Path, 1202 ) -> Result<(), error::Error> { 1203 // Opcodes. 1204 let mut fmt = Formatter::new(Language::Rust); 1205 gen_formats(&formats, &mut fmt); 1206 gen_instruction_data(&formats, &mut fmt); 1207 fmt.empty_line(); 1208 gen_instruction_data_impl(&formats, &mut fmt); 1209 fmt.empty_line(); 1210 gen_opcodes(all_inst, &mut fmt); 1211 fmt.empty_line(); 1212 gen_type_constraints(all_inst, &mut fmt); 1213 fmt.write(opcode_filename, out_dir)?; 1214 1215 // Instruction builder. 1216 let mut fmt = Formatter::new(Language::Rust); 1217 gen_builder(all_inst, &formats, &mut fmt); 1218 fmt.write(inst_builder_filename, out_dir)?; 1219 1220 Ok(()) 1221 } 1222