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