cranelift_codegen_meta/
gen_inst.rs

1//! Generate CLIF instruction data (including opcodes, formats, builders, etc.).
2
3use crate::cdsl::camel_case;
4use crate::cdsl::formats::InstructionFormat;
5use crate::cdsl::instructions::{AllInstructions, Instruction};
6use crate::cdsl::operands::{Operand, OperandKindFields};
7use crate::cdsl::typevar::{TypeSet, TypeVar};
8use crate::unique_table::{UniqueSeqTable, UniqueTable};
9use cranelift_codegen_shared::constant_hash;
10use cranelift_srcgen::{Formatter, Language, Match, error, fmtln};
11use std::fmt;
12use std::rc::Rc;
13
14// TypeSet indexes are encoded in 8 bits, with `0xff` reserved.
15const TYPESET_LIMIT: usize = 0xff;
16
17/// Generate an instruction format enumeration.
18fn 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.
63fn 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
99fn 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)`
161fn 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
510fn 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
531fn 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.
720fn 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
748fn 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
762fn 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
771fn 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.
784pub(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.
815fn 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.
929fn 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.
967fn 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.
1035fn 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.
1247fn 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
1286pub(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}