cranelift_codegen_meta/

gen_isle.rs

use crate::cdsl::formats::InstructionFormat;
use crate::cdsl::instructions::AllInstructions;
use crate::error;
use cranelift_srcgen::{Formatter, Language, fmtln};
use std::{borrow::Cow, cmp::Ordering, rc::Rc};

/// Which ISLE target are we generating code for?
#[derive(Clone, Copy, PartialEq, Eq)]
enum IsleTarget {
    /// Generating code for instruction selection and lowering.
    Lower,
    /// Generating code for CLIF to CLIF optimizations.
    Opt,
}

fn gen_common_isle(
    formats: &[Rc<InstructionFormat>],
    instructions: &AllInstructions,
    fmt: &mut Formatter,
    isle_target: IsleTarget,
) {
    use std::collections::{BTreeMap, BTreeSet};
    use std::fmt::Write;

    use crate::cdsl::formats::FormatField;

    fmt.multi_line(
        r#"
;; GENERATED BY `gen_isle`. DO NOT EDIT!!!
;;
;; This ISLE file defines all the external type declarations for Cranelift's
;; data structures that ISLE will process, such as `InstructionData` and
;; `Opcode`.
        "#,
    );
    fmt.empty_line();

    // Collect and deduplicate the immediate types from the instruction fields.
    let rust_name = |f: &FormatField| f.kind.rust_type.rsplit("::").next().unwrap();
    let fields = |f: &FormatField| f.kind.fields.clone();
    let immediate_types: BTreeMap<_, _> = formats
        .iter()
        .flat_map(|f| {
            f.imm_fields
                .iter()
                .map(|i| (rust_name(i), fields(i)))
                .collect::<Vec<_>>()
        })
        .collect();

    // Separate the `enum` immediates (e.g., `FloatCC`) from other kinds of
    // immediates.
    let (enums, others): (BTreeMap<_, _>, BTreeMap<_, _>) = immediate_types
        .iter()
        .partition(|(_, field)| field.enum_values().is_some());

    // Generate all the extern type declarations we need for the non-`enum`
    // immediates.
    fmt.line(";;;; Extern type declarations for immediates ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;");
    fmt.empty_line();
    for ty in others.keys() {
        fmtln!(fmt, "(type {} (primitive {}))", ty, ty);
    }
    fmt.empty_line();

    // Generate the `enum` immediates, expanding all of the available variants
    // into ISLE.
    for (name, field) in enums {
        let field = field.enum_values().expect("only enums considered here");
        let variants = field.values().cloned().collect();
        gen_isle_enum(name, variants, fmt)
    }

    // Generate all of the value arrays we need for `InstructionData` as well as
    // the constructors and extractors for them.
    fmt.line(";;;; Value Arrays ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;");
    fmt.empty_line();
    let value_array_arities: BTreeSet<_> = formats
        .iter()
        .filter(|f| f.typevar_operand.is_some() && !f.has_value_list && f.num_value_operands != 1)
        .map(|f| f.num_value_operands)
        .collect();
    for n in value_array_arities {
        fmtln!(fmt, ";; ISLE representation of `[Value; {}]`.", n);
        fmtln!(fmt, "(type ValueArray{} extern (enum))", n);
        fmt.empty_line();

        fmtln!(
            fmt,
            "(decl value_array_{} ({}) ValueArray{})",
            n,
            (0..n).map(|_| "Value").collect::<Vec<_>>().join(" "),
            n
        );
        fmtln!(
            fmt,
            "(extern constructor value_array_{} pack_value_array_{})",
            n,
            n
        );
        fmtln!(
            fmt,
            "(extern extractor infallible value_array_{} unpack_value_array_{})",
            n,
            n
        );
        fmt.empty_line();
    }

    // Generate all of the block arrays we need for `InstructionData` as well as
    // the constructors and extractors for them.
    fmt.line(";;;; Block Arrays ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;");
    fmt.empty_line();
    let block_array_arities: BTreeSet<_> = formats
        .iter()
        .filter(|f| f.num_block_operands > 1)
        .map(|f| f.num_block_operands)
        .collect();
    for n in block_array_arities {
        fmtln!(fmt, ";; ISLE representation of `[BlockCall; {}]`.", n);
        fmtln!(fmt, "(type BlockArray{} extern (enum))", n);
        fmt.empty_line();

        fmtln!(
            fmt,
            "(decl block_array_{0} ({1}) BlockArray{0})",
            n,
            (0..n).map(|_| "BlockCall").collect::<Vec<_>>().join(" ")
        );

        fmtln!(
            fmt,
            "(extern constructor block_array_{0} pack_block_array_{0})",
            n
        );

        fmtln!(
            fmt,
            "(extern extractor infallible block_array_{0} unpack_block_array_{0})",
            n
        );
        fmt.empty_line();
    }

    // Generate the extern type declaration for `Opcode`.
    fmt.line(";;;; `Opcode` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;");
    fmt.empty_line();
    fmt.line("(type Opcode extern");
    fmt.indent(|fmt| {
        fmt.line("(enum");
        fmt.indent(|fmt| {
            for inst in instructions {
                fmtln!(fmt, "{}", inst.camel_name);
            }
        });
        fmt.line(")");
    });
    fmt.line(")");
    fmt.empty_line();

    // Generate the extern type declaration for `InstructionData`.
    fmtln!(
        fmt,
        ";;;; `InstructionData` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;",
    );
    fmt.empty_line();
    fmtln!(fmt, "(type InstructionData extern");
    fmt.indent(|fmt| {
        fmt.line("(enum");
        fmt.indent(|fmt| {
            for format in formats {
                let mut s = format!("({} (opcode Opcode)", format.name);
                if format.has_value_list {
                    s.push_str(" (args ValueList)");
                } else if format.num_value_operands == 1 {
                    s.push_str(" (arg Value)");
                } else if format.num_value_operands > 1 {
                    write!(&mut s, " (args ValueArray{})", format.num_value_operands).unwrap();
                }

                match format.num_block_operands {
                    0 => (),
                    1 => write!(&mut s, " (destination BlockCall)").unwrap(),
                    n => write!(&mut s, " (blocks BlockArray{n})").unwrap(),
                }

                for field in &format.imm_fields {
                    write!(
                        &mut s,
                        " ({} {})",
                        field.member,
                        field.kind.rust_type.rsplit("::").next().unwrap()
                    )
                    .unwrap();
                }
                s.push(')');
                fmt.line(&s);
            }
        });
        fmt.line(")");
    });
    fmt.line(")");
    fmt.empty_line();

    // Generate the helper extractors for each opcode's full instruction.
    fmtln!(
        fmt,
        ";;;; Extracting Opcode, Operands, and Immediates from `InstructionData` ;;;;;;;;",
    );
    fmt.empty_line();
    for inst in instructions {
        let results_len = inst.value_results.len();
        let is_var_args = inst.format.has_value_list;
        let has_side_effects = inst.can_trap || inst.other_side_effects;

        let (ret_ty, ty_in_decl, make_inst_ctor, inst_data_etor) =
            match (isle_target, is_var_args, results_len, has_side_effects) {
                // The mid-end does not deal with instructions that have var-args right now.
                (IsleTarget::Opt, true, _, _) => continue,

                (IsleTarget::Opt, _, 1, false) => ("Value", true, "make_inst", "inst_data_value"),
                (IsleTarget::Opt, _, _, _) => ("Inst", false, "make_skeleton_inst", "inst_data"),
                (IsleTarget::Lower, _, _, _) => ("Inst", false, "make_inst", "inst_data_value"),
            };

        fmtln!(
            fmt,
            "(decl {} ({}{}) {})",
            inst.name,
            if ty_in_decl { "Type " } else { "" },
            inst.operands_in
                .iter()
                .map(|o| {
                    let ty = o.kind.rust_type;
                    if ty == "&[Value]" {
                        "ValueSlice"
                    } else {
                        ty.rsplit("::").next().unwrap()
                    }
                })
                .collect::<Vec<_>>()
                .join(" "),
            ret_ty
        );
        fmtln!(fmt, "(extractor");
        fmt.indent(|fmt| {
            fmtln!(
                fmt,
                "({} {}{})",
                inst.name,
                if ty_in_decl { "ty " } else { "" },
                inst.operands_in
                    .iter()
                    .map(|o| { o.name })
                    .collect::<Vec<_>>()
                    .join(" ")
            );

            let mut s = format!(
                "({inst_data_etor} {}(InstructionData.{} (Opcode.{})",
                if ty_in_decl { "ty " } else { "" },
                inst.format.name,
                inst.camel_name
            );

            // Value and varargs operands.
            if inst.format.has_value_list {
                // The instruction format uses a value list, but the
                // instruction itself might have not only a `&[Value]`
                // varargs operand, but also one or more `Value` operands as
                // well. If this is the case, then we need to read them off
                // the front of the `ValueList`.
                let values: Vec<_> = inst
                    .operands_in
                    .iter()
                    .filter(|o| o.is_value())
                    .map(|o| o.name)
                    .collect();
                let varargs = inst
                    .operands_in
                    .iter()
                    .find(|o| o.is_varargs())
                    .unwrap()
                    .name;
                if values.is_empty() {
                    write!(&mut s, " (value_list_slice {varargs})").unwrap();
                } else {
                    write!(
                        &mut s,
                        " (unwrap_head_value_list_{} {} {})",
                        values.len(),
                        values.join(" "),
                        varargs
                    )
                    .unwrap();
                }
            } else if inst.format.num_value_operands == 1 {
                write!(
                    &mut s,
                    " {}",
                    inst.operands_in.iter().find(|o| o.is_value()).unwrap().name
                )
                .unwrap();
            } else if inst.format.num_value_operands > 1 {
                let values = inst
                    .operands_in
                    .iter()
                    .filter(|o| o.is_value())
                    .map(|o| o.name)
                    .collect::<Vec<_>>();
                assert_eq!(values.len(), inst.format.num_value_operands);
                let values = values.join(" ");
                write!(
                    &mut s,
                    " (value_array_{} {})",
                    inst.format.num_value_operands, values,
                )
                .unwrap();
            }

            // Immediates.
            let imm_operands: Vec<_> = inst
                .operands_in
                .iter()
                .filter(|o| !o.is_value() && !o.is_varargs() && !o.kind.is_block())
                .collect();
            assert_eq!(imm_operands.len(), inst.format.imm_fields.len(),);
            for op in imm_operands {
                write!(&mut s, " {}", op.name).unwrap();
            }

            // Blocks.
            let block_operands: Vec<_> = inst
                .operands_in
                .iter()
                .filter(|o| o.kind.is_block())
                .collect();
            assert_eq!(block_operands.len(), inst.format.num_block_operands);
            assert!(block_operands.len() <= 2);

            if !block_operands.is_empty() {
                if block_operands.len() == 1 {
                    write!(&mut s, " {}", block_operands[0].name).unwrap();
                } else {
                    let blocks: Vec<_> = block_operands.iter().map(|o| o.name).collect();
                    let blocks = blocks.join(" ");
                    write!(
                        &mut s,
                        " (block_array_{} {})",
                        inst.format.num_block_operands, blocks,
                    )
                    .unwrap();
                }
            }

            s.push_str("))");
            fmt.line(&s);
        });
        fmt.line(")");

        // Generate a constructor if this is the mid-end prelude.
        if isle_target == IsleTarget::Opt {
            fmtln!(
                fmt,
                "(rule ({}{} {})",
                inst.name,
                if ty_in_decl { " ty" } else { "" },
                inst.operands_in
                    .iter()
                    .map(|o| o.name)
                    .collect::<Vec<_>>()
                    .join(" ")
            );
            fmt.indent(|fmt| {
                let mut s = format!(
                    "({make_inst_ctor}{} (InstructionData.{} (Opcode.{})",
                    if ty_in_decl { " ty" } else { "" },
                    inst.format.name,
                    inst.camel_name
                );

                // Handle values. Note that we skip generating
                // constructors for any instructions with variadic
                // value lists. This is fine for the mid-end because
                // in practice only calls and branches (for branch
                // args) use this functionality, and neither can
                // really be optimized or rewritten in the mid-end
                // (currently).
                //
                // As a consequence, we only have to handle the
                // one-`Value` case, in which the `Value` is directly
                // in the `InstructionData`, and the multiple-`Value`
                // case, in which the `Value`s are in a
                // statically-sized array (e.g. `[Value; 2]` for a
                // binary op).
                assert!(!inst.format.has_value_list);
                if inst.format.num_value_operands == 1 {
                    write!(
                        &mut s,
                        " {}",
                        inst.operands_in.iter().find(|o| o.is_value()).unwrap().name
                    )
                    .unwrap();
                } else if inst.format.num_value_operands > 1 {
                    // As above, get all bindings together, and pass
                    // to a sub-term; here we use a constructor to
                    // build the value array.
                    let values = inst
                        .operands_in
                        .iter()
                        .filter(|o| o.is_value())
                        .map(|o| o.name)
                        .collect::<Vec<_>>();
                    assert_eq!(values.len(), inst.format.num_value_operands);
                    let values = values.join(" ");
                    write!(
                        &mut s,
                        " (value_array_{}_ctor {})",
                        inst.format.num_value_operands, values
                    )
                    .unwrap();
                }

                if inst.format.num_block_operands > 0 {
                    let blocks: Vec<_> = inst
                        .operands_in
                        .iter()
                        .filter(|o| o.kind.is_block())
                        .map(|o| o.name)
                        .collect();
                    if inst.format.num_block_operands == 1 {
                        write!(&mut s, " {}", blocks.first().unwrap(),).unwrap();
                    } else {
                        write!(
                            &mut s,
                            " (block_array_{} {})",
                            inst.format.num_block_operands,
                            blocks.join(" ")
                        )
                        .unwrap();
                    }
                }

                // Immediates (non-value args).
                for o in inst
                    .operands_in
                    .iter()
                    .filter(|o| !o.is_value() && !o.is_varargs() && !o.kind.is_block())
                {
                    write!(&mut s, " {}", o.name).unwrap();
                }
                s.push_str("))");
                fmt.line(&s);
            });
            fmt.line(")");
        }

        fmt.empty_line();
    }
}

fn gen_opt_isle(
    formats: &[Rc<InstructionFormat>],
    instructions: &AllInstructions,
    fmt: &mut Formatter,
) {
    gen_common_isle(formats, instructions, fmt, IsleTarget::Opt);
}

fn gen_lower_isle(
    formats: &[Rc<InstructionFormat>],
    instructions: &AllInstructions,
    fmt: &mut Formatter,
) {
    gen_common_isle(formats, instructions, fmt, IsleTarget::Lower);
}

/// Generate an `enum` immediate in ISLE.
fn gen_isle_enum(name: &str, mut variants: Vec<&str>, fmt: &mut Formatter) {
    variants.sort();
    let prefix = format!(";;;; Enumerated Immediate: {name} ");
    fmtln!(fmt, "{:;<80}", prefix);
    fmt.empty_line();
    fmtln!(fmt, "(type {} extern", name);
    fmt.indent(|fmt| {
        fmt.line("(enum");
        fmt.indent(|fmt| {
            for variant in variants {
                fmtln!(fmt, "{}", variant);
            }
        });
        fmt.line(")");
    });
    fmt.line(")");
    fmt.empty_line();
}

#[derive(Clone, Copy, PartialEq, Eq)]
struct NumericType {
    signed: bool,
    byte_width: u8,
}

impl NumericType {
    fn all() -> impl Iterator<Item = NumericType> {
        [1, 2, 4, 8, 16].into_iter().flat_map(|byte_width| {
            [true, false]
                .into_iter()
                .map(move |signed| NumericType { signed, byte_width })
        })
    }

    fn name(&self) -> &'static str {
        let idx = self.byte_width.ilog2();
        let idx = usize::try_from(idx).unwrap();
        if self.signed {
            ["i8", "i16", "i32", "i64", "i128"][idx]
        } else {
            ["u8", "u16", "u32", "u64", "u128"][idx]
        }
    }
}

#[derive(Clone, Default, PartialEq, Eq)]
struct NumericOp<'a> {
    /// The name of this operation.
    name: &'a str,
    /// The return type of this operation.
    ret: &'a str,
    /// Whether this operation is partial.
    partial: bool,
    /// (name, type) pairs of arguments.
    args: Rc<[(&'a str, &'a str)]>,
    /// The source text for the constructor's body.
    body: &'a str,
    /// Whether extractors should be generated for this op.
    ///
    /// Must have `arity == 1`, `ret == bool`, and `name.starts_with("is_")`.
    etors: bool,
}

impl NumericOp<'_> {
    fn ops_for_type(ty: &NumericType) -> impl Iterator<Item = NumericOp<'_>> {
        let arity1 = NumericOp {
            args: [("a", ty.name())].into(),
            ..NumericOp::default()
        };

        let arity2 = NumericOp {
            args: [("a", ty.name()), ("b", ty.name())].into(),
            ..NumericOp::default()
        };

        let comparison = NumericOp {
            ret: "bool",
            ..arity2.clone()
        };

        let predicate = NumericOp {
            ret: "bool",
            etors: true,
            ..arity1.clone()
        };

        let binop = NumericOp {
            ret: ty.name(),
            ..arity2.clone()
        };

        let partial_binop = NumericOp {
            ret: ty.name(),
            partial: true,
            ..binop.clone()
        };

        let unop = NumericOp {
            ret: ty.name(),
            ..arity1.clone()
        };

        let partial_unop = NumericOp {
            ret: ty.name(),
            partial: true,
            ..unop.clone()
        };

        let shift = NumericOp {
            args: [("a", ty.name()), ("b", "u32")].into(),
            ..binop.clone()
        };

        let partial_shift = NumericOp {
            args: [("a", ty.name()), ("b", "u32")].into(),
            ..partial_binop.clone()
        };

        // Operations that apply to both signed and unsigned numbers.
        let ops = [
            // Comparisons.
            NumericOp {
                name: "eq",
                body: "a == b",
                ..comparison.clone()
            },
            NumericOp {
                name: "ne",
                body: "a != b",
                ..comparison.clone()
            },
            NumericOp {
                name: "lt",
                body: "a < b",
                ..comparison.clone()
            },
            NumericOp {
                name: "lt_eq",
                body: "a <= b",
                ..comparison.clone()
            },
            NumericOp {
                name: "gt",
                body: "a > b",
                ..comparison.clone()
            },
            NumericOp {
                name: "gt_eq",
                body: "a >= b",
                ..comparison.clone()
            },
            // Arithmetic operations.
            //
            // For each operation (e.g. addition) we have three variants:
            //
            // * partial ctor `checked_add`: no return value on overflow
            // * ctor `wrapping_add`: wraps on overflow
            // * ctor `add`: non-partial but panics at runtime on overflow
            NumericOp {
                name: "checked_add",
                body: "a.checked_add(b)",
                ..partial_binop.clone()
            },
            NumericOp {
                name: "wrapping_add",
                body: "a.wrapping_add(b)",
                ..binop.clone()
            },
            NumericOp {
                name: "add",
                body: r#"a.checked_add(b).unwrap_or_else(|| panic!("addition overflow: {a} + {b}"))"#,
                ..binop.clone()
            },
            NumericOp {
                name: "checked_sub",
                body: "a.checked_sub(b)",
                ..partial_binop.clone()
            },
            NumericOp {
                name: "wrapping_sub",
                body: "a.wrapping_sub(b)",
                ..binop.clone()
            },
            NumericOp {
                name: "sub",
                body: r#"a.checked_sub(b).unwrap_or_else(|| panic!("subtraction overflow: {a} - {b}"))"#,
                ..binop.clone()
            },
            NumericOp {
                name: "checked_mul",
                body: "a.checked_mul(b)",
                ..partial_binop.clone()
            },
            NumericOp {
                name: "wrapping_mul",
                body: "a.wrapping_mul(b)",
                ..binop.clone()
            },
            NumericOp {
                name: "mul",
                body: r#"a.checked_mul(b).unwrap_or_else(|| panic!("multiplication overflow: {a} * {b}"))"#,
                ..binop.clone()
            },
            NumericOp {
                name: "checked_div",
                body: "a.checked_div(b)",
                ..partial_binop.clone()
            },
            NumericOp {
                name: "wrapping_div",
                body: "a.wrapping_div(b)",
                ..binop.clone()
            },
            NumericOp {
                name: "div",
                body: r#"a.checked_div(b).unwrap_or_else(|| panic!("div failure: {a} / {b}"))"#,
                ..binop.clone()
            },
            // Bitwise operations.
            //
            // When applicable (e.g. shifts) we have checked, wrapping, and
            // unwrapping variants, similar to arithmetic operations.
            NumericOp {
                name: "and",
                body: "a & b",
                ..binop.clone()
            },
            NumericOp {
                name: "or",
                body: "a | b",
                ..binop.clone()
            },
            NumericOp {
                name: "xor",
                body: "a ^ b",
                ..binop.clone()
            },
            NumericOp {
                name: "not",
                body: "!a",
                ..unop.clone()
            },
            NumericOp {
                name: "checked_shl",
                body: "a.checked_shl(b)",
                ..partial_shift.clone()
            },
            NumericOp {
                name: "wrapping_shl",
                body: "a.wrapping_shl(b)",
                ..shift.clone()
            },
            NumericOp {
                name: "shl",
                body: r#"a.checked_shl(b).unwrap_or_else(|| panic!("shl overflow: {a} << {b}"))"#,
                ..shift.clone()
            },
            NumericOp {
                name: "checked_shr",
                body: "a.checked_shr(b)",
                ..partial_shift.clone()
            },
            NumericOp {
                name: "wrapping_shr",
                body: "a.wrapping_shr(b)",
                ..shift.clone()
            },
            NumericOp {
                name: "shr",
                body: r#"a.checked_shr(b).unwrap_or_else(|| panic!("shr overflow: {a} >> {b}"))"#,
                ..shift.clone()
            },
            // Predicates.
            //
            // We generate both pure constructors and a variety of extractors
            // for these. See the relevant comments in `gen_numerics_isle` about
            // the extractors.
            NumericOp {
                name: "is_zero",
                body: "a == 0",
                ..predicate.clone()
            },
            NumericOp {
                name: "is_non_zero",
                body: "a != 0",
                ..predicate.clone()
            },
            NumericOp {
                name: "is_odd",
                body: "a & 1 == 1",
                ..predicate.clone()
            },
            NumericOp {
                name: "is_even",
                body: "a & 1 == 0",
                ..predicate.clone()
            },
            // Miscellaneous unary operations.
            NumericOp {
                name: "checked_ilog2",
                body: "a.checked_ilog2()",
                ret: "u32",
                ..partial_unop.clone()
            },
            NumericOp {
                name: "ilog2",
                body: r#"a.checked_ilog2().unwrap_or_else(|| panic!("ilog2 overflow: {a}"))"#,
                ret: "u32",
                ..unop.clone()
            },
            NumericOp {
                name: "trailing_zeros",
                body: "a.trailing_zeros()",
                ret: "u32",
                ..unop.clone()
            },
            NumericOp {
                name: "trailing_ones",
                body: "a.trailing_ones()",
                ret: "u32",
                ..unop.clone()
            },
            NumericOp {
                name: "leading_zeros",
                body: "a.leading_zeros()",
                ret: "u32",
                ..unop.clone()
            },
            NumericOp {
                name: "leading_ones",
                body: "a.leading_ones()",
                ret: "u32",
                ..unop.clone()
            },
        ];

        // Operations that apply only to signed numbers.
        let signed_ops = [
            NumericOp {
                name: "checked_neg",
                body: "a.checked_neg()",
                ..partial_unop.clone()
            },
            NumericOp {
                name: "wrapping_neg",
                body: "a.wrapping_neg()",
                ..unop.clone()
            },
            NumericOp {
                name: "neg",
                body: r#"a.checked_neg().unwrap_or_else(|| panic!("negation overflow: {a}"))"#,
                ..unop.clone()
            },
        ];

        // Operations that apply only to unsigned numbers.
        let unsigned_ops = [NumericOp {
            name: "is_power_of_two",
            body: "a.is_power_of_two()",
            ..predicate.clone()
        }];

        struct IterIf<I> {
            condition: bool,
            iter: I,
        }

        impl<I: Iterator> Iterator for IterIf<I> {
            type Item = I::Item;

            fn next(&mut self) -> Option<Self::Item> {
                if self.condition {
                    self.iter.next()
                } else {
                    None
                }
            }
        }

        ops.into_iter()
            .chain(IterIf {
                condition: ty.signed,
                iter: signed_ops.into_iter(),
            })
            .chain(IterIf {
                condition: !ty.signed,
                iter: unsigned_ops.into_iter(),
            })
    }
}

fn gen_numerics_isle(isle: &mut Formatter, rust: &mut Formatter) {
    fmtln!(rust, "#[macro_export]");
    fmtln!(rust, "#[doc(hidden)]");
    fmtln!(rust, "macro_rules! isle_numerics_methods {{");
    rust.indent_push();
    fmtln!(rust, "() => {{");
    rust.indent_push();

    for ty in NumericType::all() {
        for op in NumericOp::ops_for_type(&ty) {
            let ty = ty.name();
            let op_name = format!("{ty}_{}", op.name);
            let partial = if op.partial { " partial" } else { "" };
            let ret = op.ret;
            fmtln!(isle, "(decl pure{partial} {op_name} (");
            isle.indent(|isle| {
                for (_arg_name, arg_ty) in op.args.iter() {
                    fmtln!(isle, "{arg_ty}");
                }
            });
            fmtln!(isle, ") {ret})");
            fmtln!(isle, "(extern constructor {op_name} {op_name})");

            let ret = if op.partial {
                Cow::from(format!("Option<{ret}>"))
            } else {
                Cow::from(ret)
            };
            let body = op.body;
            fmtln!(rust, "#[inline]");
            fmtln!(rust, "fn {op_name}(");
            rust.indent(|rust| {
                fmtln!(rust, "&mut self,");
                for (arg_name, arg_ty) in op.args.iter() {
                    fmtln!(rust, "{arg_name}: {arg_ty},");
                }
            });
            fmtln!(rust, ") -> {ret} {{");
            rust.indent(|rust| {
                fmtln!(rust, "{body}");
            });
            fmtln!(rust, "}}");

            // When generating extractors for a `{ty}_is_foo` predicate,
            // we generate the following:
            //
            // * bool <- ty etor: `{ty}_matches_foo`
            // * ty <- ty etor: `{ty}_extract_foo`
            // * () <- ty etor: `{ty}_when_foo`
            // * () <- ty etor: `{ty}_when_not_foo`
            //
            // The last three are defined as local extractors that are
            // implemented in terms of the first. This gives the ISLE compiler
            // visibility into the extractors' overlapping-ness.
            if op.etors {
                debug_assert_eq!(op.args.len(), 1);
                debug_assert_eq!(op.args[0].1, ty);
                debug_assert_eq!(op.ret, "bool");
                debug_assert!(op.name.starts_with("is_"));

                // Cut of the `is_` prefix.
                let base_name = &op.name[3..];
                debug_assert!(base_name.len() > 0);

                fmtln!(isle, "(decl pure {ty}_matches_{base_name} (bool) {ty})");
                fmtln!(
                    isle,
                    "(extern extractor {ty}_matches_{base_name} {ty}_matches_{base_name})"
                );
                fmtln!(rust, "#[inline]");
                fmtln!(
                    rust,
                    "fn {ty}_matches_{base_name}(&mut self, a: {ty}) -> Option<bool> {{"
                );
                rust.indent(|rust| {
                    fmtln!(rust, "Some({body})");
                });
                fmtln!(rust, "}}");

                fmtln!(isle, "(decl pure {ty}_extract_{base_name} ({ty}) {ty})");
                fmtln!(
                    isle,
                    "(extractor ({ty}_extract_{base_name} x) (and ({ty}_matches_{base_name} true) x))"
                );

                fmtln!(isle, "(decl pure {ty}_when_{base_name} () {ty})");
                fmtln!(
                    isle,
                    "(extractor ({ty}_when_{base_name}) ({ty}_matches_{base_name} true))"
                );

                fmtln!(isle, "(decl pure {ty}_when_not_{base_name} () {ty})");
                fmtln!(
                    isle,
                    "(extractor ({ty}_when_not_{base_name}) ({ty}_matches_{base_name} false))"
                );
            }

            isle.empty_line();
            rust.empty_line();
        }
    }

    // Numeric type conversions.
    //
    // Naming and conventions:
    //
    // * Constructors:
    //   * "<from>_into_<to>" for lossless, infallible conversion
    //   * "<from>_try_into_<to>" for lossless, fallible conversions (exposed as
    //     partial constructors)
    //   * "<from>_unwrap_into_<to>" for lossless, fallible conversions that will
    //     panic at runtime if the conversion would be lossy
    //   * "<from>_truncate_into_<to>" for lossy, infallible conversions that
    //     ignore upper bits
    //   * "<from>_cast_[un]signed" for signed-to-unsigned (and vice versa)
    //     reinterpretation
    // * Extractors:
    //   * "<to>_from_<from>" for both fallible and infallible extractors
    //   * No unwrapping extractors
    //   * No truncating extractors
    //   * No signed-to-unsigned reinterpreting extractors
    for from in NumericType::all() {
        for to in NumericType::all() {
            if from == to {
                continue;
            }

            let from_name = from.name();
            let to_name = to.name();

            let lossy = match (from.byte_width.cmp(&to.byte_width), from.signed, to.signed) {
                // Widening with the same signedness is lossless.
                (Ordering::Less, true, true) | (Ordering::Less, false, false) => false,
                // Widening from unsigned to signed is lossless.
                (Ordering::Less, false, true) => false,
                // Widening from signed to unsigned is lossy.
                (Ordering::Less, true, false) => true,
                // Same width means we must be changing sign, since we skip
                // `from == to`, and this is lossy.
                (Ordering::Equal, _, _) => {
                    debug_assert_ne!(from.signed, to.signed);
                    true
                }
                // Narrowing is always lossy.
                (Ordering::Greater, _, _) => true,
            };

            let (ctor, partial, rust_ret) = if lossy {
                (
                    "try_into",
                    " partial",
                    Cow::from(format!("Option<{to_name}>")),
                )
            } else {
                ("into", "", Cow::from(to_name))
            };

            // Constructor.
            fmtln!(
                isle,
                "(decl pure{partial} {from_name}_{ctor}_{to_name} ({from_name}) {to_name})"
            );
            fmtln!(
                isle,
                "(extern constructor {from_name}_{ctor}_{to_name} {from_name}_{ctor}_{to_name})"
            );
            if !lossy {
                fmtln!(
                    isle,
                    "(convert {from_name} {to_name} {from_name}_{ctor}_{to_name})"
                );
            }
            fmtln!(rust, "#[inline]");
            fmtln!(
                rust,
                "fn {from_name}_{ctor}_{to_name}(&mut self, x: {from_name}) -> {rust_ret} {{"
            );
            rust.indent(|rust| {
                if lossy {
                    fmtln!(rust, "{to_name}::try_from(x).ok()");
                } else {
                    fmtln!(rust, "{to_name}::from(x)");
                }
            });
            fmtln!(rust, "}}");

            // Unwrapping constructor.
            if lossy {
                fmtln!(
                    isle,
                    "(decl pure {from_name}_unwrap_into_{to_name} ({from_name}) {to_name})"
                );
                fmtln!(
                    isle,
                    "(extern constructor {from_name}_unwrap_into_{to_name} {from_name}_unwrap_into_{to_name})"
                );
                fmtln!(rust, "#[inline]");
                fmtln!(
                    rust,
                    "fn {from_name}_unwrap_into_{to_name}(&mut self, x: {from_name}) -> {to_name} {{"
                );
                rust.indent(|rust| {
                    fmtln!(rust, "{to_name}::try_from(x).unwrap()");
                });
                fmtln!(rust, "}}");
            }

            // Truncating constructor.
            if lossy && from.signed == to.signed {
                fmtln!(
                    isle,
                    "(decl pure {from_name}_truncate_into_{to_name} ({from_name}) {to_name})"
                );
                fmtln!(
                    isle,
                    "(extern constructor {from_name}_truncate_into_{to_name} {from_name}_truncate_into_{to_name})"
                );
                fmtln!(rust, "#[inline]");
                fmtln!(
                    rust,
                    "fn {from_name}_truncate_into_{to_name}(&mut self, x: {from_name}) -> {to_name} {{"
                );
                rust.indent(|rust| {
                    fmtln!(rust, "x as {to_name}");
                });
                fmtln!(rust, "}}");
            }

            // Signed-to-unsigned reinterpreting constructor.
            if from.byte_width == to.byte_width {
                debug_assert_ne!(from.signed, to.signed);
                let cast_name = if to.signed {
                    "cast_signed"
                } else {
                    "cast_unsigned"
                };
                fmtln!(
                    isle,
                    "(decl pure {from_name}_{cast_name} ({from_name}) {to_name})"
                );
                fmtln!(
                    isle,
                    "(extern constructor {from_name}_{cast_name} {from_name}_{cast_name})"
                );
                fmtln!(rust, "#[inline]");
                fmtln!(
                    rust,
                    "fn {from_name}_{cast_name}(&mut self, x: {from_name}) -> {to_name} {{"
                );
                rust.indent(|rust| {
                    // TODO: Once our MSRV is >= 1.87, we should use
                    // `x.cast_[un]signed()` here.
                    fmtln!(rust, "x as {to_name}");
                });
                fmtln!(rust, "}}");
            }

            // Extractor.
            fmtln!(
                isle,
                "(decl pure {to_name}_from_{from_name} ({to_name}) {from_name})"
            );
            fmtln!(
                isle,
                "(extern extractor {to_name}_from_{from_name} {from_name}_from_{to_name})"
            );
            fmtln!(rust, "#[inline]");
            fmtln!(
                rust,
                "fn {from_name}_from_{to_name}(&mut self, x: {from_name}) -> Option<{to_name}> {{"
            );
            rust.indent(|rust| {
                if lossy {
                    fmtln!(rust, "x.try_into().ok()");
                } else {
                    fmtln!(rust, "Some(x.into())");
                }
            });
            fmtln!(rust, "}}");

            isle.empty_line();
            rust.empty_line();
        }
    }

    rust.indent_pop();
    fmtln!(rust, "}}");
    rust.indent_pop();
    fmtln!(rust, "}}");
}

pub(crate) fn generate(
    formats: &[Rc<InstructionFormat>],
    all_inst: &AllInstructions,
    isle_numerics_filename: &str,
    rust_numerics_filename: &str,
    isle_opt_filename: &str,
    isle_lower_filename: &str,
    isle_dir: &std::path::Path,
) -> Result<(), error::Error> {
    // Numerics
    let mut isle_fmt = Formatter::new(Language::Isle);
    let mut rust_fmt = Formatter::new(Language::Rust);
    gen_numerics_isle(&mut isle_fmt, &mut rust_fmt);
    isle_fmt.write(isle_numerics_filename, isle_dir)?;
    rust_fmt.write(rust_numerics_filename, isle_dir)?;

    // ISLE DSL: mid-end ("opt") generated bindings.
    let mut fmt = Formatter::new(Language::Isle);
    gen_opt_isle(&formats, all_inst, &mut fmt);
    fmt.write(isle_opt_filename, isle_dir)?;

    // ISLE DSL: lowering generated bindings.
    let mut fmt = Formatter::new(Language::Isle);
    gen_lower_isle(&formats, all_inst, &mut fmt);
    fmt.write(isle_lower_filename, isle_dir)?;

    Ok(())
}