cranelift_codegen_meta/

gen_encodings.rs

//! Generate sources for instruction encoding.
//!
//! The tables and functions generated here support the `TargetISA::encode()` function which
//! determines if a given instruction is legal, and if so, its `Encoding` data which consists of a
//! *recipe* and some *encoding* bits.
//!
//! The `encode` function doesn't actually generate the binary machine bits. Each recipe has a
//! corresponding hand-written function to do that after registers are allocated.
//!
//! This is the information available to us:
//!
//! - The instruction to be encoded as an `InstructionData` reference.
//! - The controlling type variable.
//! - The data-flow graph giving us access to the types of all values involved. This is needed for
//! testing any secondary type variables.
//! - A `PredicateView` reference for the ISA-specific settings for evaluating ISA predicates.
//! - The currently active CPU mode is determined by the ISA.
//!
//! ## Level 1 table lookup
//!
//! The CPU mode provides the first table. The key is the instruction's controlling type variable.
//! If the instruction is not polymorphic, use `INVALID` for the type variable. The table values
//! are level 2 tables.
//!
//! ## Level 2 table lookup
//!
//! The level 2 table is keyed by the instruction's opcode. The table values are *encoding lists*.
//!
//! The two-level table lookup allows the level 2 tables to be much smaller with good locality.
//! Code in any given function usually only uses a few different types, so many of the level 2
//! tables will be cold.
//!
//! ## Encoding lists
//!
//! An encoding list is a non-empty sequence of list entries. Each entry has one of these forms:
//!
//! 1. Recipe + bits. Use this encoding if the recipe predicate is satisfied.
//! 2. Recipe + bits, final entry. Use this encoding if the recipe predicate is satisfied.
//!    Otherwise, stop with the default legalization code.
//! 3. Stop with legalization code.
//! 4. Predicate + skip count. Test predicate and skip N entries if it is false.
//! 5. Predicate + stop. Test predicate and stop with the default legalization code if it is false.
//!
//! The instruction predicate is also used to distinguish between polymorphic instructions with
//! different types for secondary type variables.

use std::collections::btree_map;
use std::collections::{BTreeMap, HashMap, HashSet};
use std::convert::TryFrom;
use std::iter::FromIterator;

use cranelift_codegen_shared::constant_hash::generate_table;
use cranelift_entity::EntityRef;

use crate::error;
use crate::srcgen::Formatter;

use crate::cdsl::cpu_modes::CpuMode;
use crate::cdsl::encodings::Encoding;
use crate::cdsl::instructions::{Instruction, InstructionPredicate, InstructionPredicateNumber};
use crate::cdsl::isa::TargetIsa;
use crate::cdsl::recipes::{EncodingRecipe, OperandConstraint, Recipes, Register};
use crate::cdsl::regs::IsaRegs;
use crate::cdsl::settings::SettingPredicateNumber;
use crate::cdsl::types::ValueType;
use crate::cdsl::xform::TransformGroupIndex;

use crate::shared::Definitions as SharedDefinitions;

use crate::default_map::MapWithDefault;
use crate::unique_table::UniqueSeqTable;

/// Emit code for matching an instruction predicate against an `InstructionData` reference called
/// `inst`.
///
/// The generated code is an `if let` pattern match that falls through if the instruction has an
/// unexpected format. This should lead to a panic.
fn emit_instp(instp: &InstructionPredicate, has_func: bool, fmt: &mut Formatter) {
    if let Some(type_predicate) = instp.type_predicate("func") {
        fmt.line("let args = inst.arguments(&func.dfg.value_lists);");
        fmt.line(type_predicate);
        return;
    }

    let leaves = instp.collect_leaves();

    let mut has_type_check = false;
    let mut format_name = None;
    let mut field_names = HashSet::new();

    for leaf in leaves {
        if leaf.is_type_predicate() {
            has_type_check = true;
        } else {
            field_names.insert(leaf.format_destructuring_member_name());
            let leaf_format_name = leaf.format_name();
            match format_name {
                None => format_name = Some(leaf_format_name),
                Some(previous_format_name) => {
                    assert!(
                        previous_format_name == leaf_format_name,
                        format!("Format predicate can only operate on a single InstructionFormat; trying to use both {} and {}", previous_format_name, leaf_format_name
                    ));
                }
            }
        }
    }

    let mut fields = Vec::from_iter(field_names);
    fields.sort();
    let fields = fields.join(", ");

    let format_name = format_name.expect("There should be a format name!");

    fmtln!(
        fmt,
        "if let crate::ir::InstructionData::{} {{ {}, .. }} = *inst {{",
        format_name,
        fields
    );
    fmt.indent(|fmt| {
        if has_type_check {
            // We could implement this.
            assert!(has_func, "recipe predicates can't check type variables.");
            fmt.line("let args = inst.arguments(&func.dfg.value_lists);");
        } else if has_func {
            // Silence dead argument.
            fmt.line("let _ = func;");
        }
        fmtln!(fmt, "return {};", instp.rust_predicate("func").unwrap());
    });
    fmtln!(fmt, "}");

    fmt.line("unreachable!();");
}

/// Emit private functions for checking recipe predicates as well as a static `RECIPE_PREDICATES`
/// array indexed by recipe number.
///
/// A recipe predicate is a combination of an ISA predicate and an instruction predicate. Many
/// recipes have identical predicates.
fn emit_recipe_predicates(isa: &TargetIsa, fmt: &mut Formatter) {
    let mut predicate_names = HashMap::new();

    fmt.comment(format!("{} recipe predicates.", isa.name));
    for recipe in isa.recipes.values() {
        let (isap, instp) = match (&recipe.isa_predicate, &recipe.inst_predicate) {
            (None, None) => continue,
            (isap, instp) if predicate_names.contains_key(&(isap, instp)) => continue,
            (isap, instp) => (isap, instp),
        };

        let func_name = format!("recipe_predicate_{}", recipe.name.to_lowercase());
        predicate_names.insert((isap, instp), func_name.clone());

        // Generate the predicate function.
        fmtln!(
            fmt,
            "fn {}({}: crate::settings::PredicateView, {}: &ir::InstructionData) -> bool {{",
            func_name,
            if isap.is_some() { "isap" } else { "_" },
            if instp.is_some() { "inst" } else { "_" }
        );
        fmt.indent(|fmt| {
            match (isap, instp) {
                (Some(isap), None) => {
                    fmtln!(fmt, "isap.test({})", isap);
                }
                (None, Some(instp)) => {
                    emit_instp(instp, /* has func */ false, fmt);
                }
                (Some(isap), Some(instp)) => {
                    fmtln!(fmt, "isap.test({}) &&", isap);
                    emit_instp(instp, /* has func */ false, fmt);
                }
                _ => panic!("skipped above"),
            }
        });
        fmtln!(fmt, "}");
    }
    fmt.empty_line();

    // Generate the static table.
    fmt.doc_comment(format!(
        r#"{} recipe predicate table.

        One entry per recipe, set to Some only when the recipe is guarded by a predicate."#,
        isa.name
    ));
    fmtln!(
        fmt,
        "pub static RECIPE_PREDICATES: [RecipePredicate; {}] = [",
        isa.recipes.len()
    );
    fmt.indent(|fmt| {
        for recipe in isa.recipes.values() {
            match (&recipe.isa_predicate, &recipe.inst_predicate) {
                (None, None) => fmt.line("None,"),
                key => fmtln!(fmt, "Some({}),", predicate_names.get(&key).unwrap()),
            }
        }
    });
    fmtln!(fmt, "];");
    fmt.empty_line();
}

/// Emit private functions for matching instruction predicates as well as a static
/// `INST_PREDICATES` array indexed by predicate number.
fn emit_inst_predicates(isa: &TargetIsa, fmt: &mut Formatter) {
    fmt.comment(format!("{} instruction predicates.", isa.name));
    for (id, instp) in isa.encodings_predicates.iter() {
        fmtln!(fmt, "fn inst_predicate_{}(func: &crate::ir::Function, inst: &crate::ir::InstructionData) -> bool {{", id.index());
        fmt.indent(|fmt| {
            emit_instp(instp, /* has func */ true, fmt);
        });
        fmtln!(fmt, "}");
    }
    fmt.empty_line();

    // Generate the static table.
    fmt.doc_comment(format!(
        r#"{} instruction predicate table.

        One entry per instruction predicate, so the encoding bytecode can embed indexes into this
        table."#,
        isa.name
    ));
    fmtln!(
        fmt,
        "pub static INST_PREDICATES: [InstPredicate; {}] = [",
        isa.encodings_predicates.len()
    );
    fmt.indent(|fmt| {
        for id in isa.encodings_predicates.keys() {
            fmtln!(fmt, "inst_predicate_{},", id.index());
        }
    });
    fmtln!(fmt, "];");
    fmt.empty_line();
}

/// Emit a table of encoding recipe names keyed by recipe number.
///
/// This is used for pretty-printing encodings.
fn emit_recipe_names(isa: &TargetIsa, fmt: &mut Formatter) {
    fmt.doc_comment(format!(
        r#"{} recipe names, using the same recipe index spaces as the one specified by the
        corresponding binemit file."#,
        isa.name
    ));
    fmtln!(
        fmt,
        "static RECIPE_NAMES: [&str; {}] = [",
        isa.recipes.len()
    );
    fmt.indent(|fmt| {
        for recipe in isa.recipes.values() {
            fmtln!(fmt, r#""{}","#, recipe.name);
        }
    });
    fmtln!(fmt, "];");
    fmt.empty_line();
}

/// Returns a set of all the registers involved in fixed register constraints.
fn get_fixed_registers(operands_in: &[OperandConstraint]) -> HashSet<Register> {
    HashSet::from_iter(
        operands_in
            .iter()
            .map(|constraint| {
                if let OperandConstraint::FixedReg(reg) = &constraint {
                    Some(*reg)
                } else {
                    None
                }
            })
            .filter(|opt| opt.is_some())
            .map(|opt| opt.unwrap()),
    )
}

/// Emit a struct field initializer for an array of operand constraints.
///
/// Note "fixed_registers" must refer to the other kind of operands (i.e. if we're operating on
/// inputs, fixed_registers must contain the fixed output registers).
fn emit_operand_constraints(
    registers: &IsaRegs,
    recipe: &EncodingRecipe,
    constraints: &[OperandConstraint],
    field_name: &'static str,
    tied_operands: &HashMap<usize, usize>,
    fixed_registers: &HashSet<Register>,
    fmt: &mut Formatter,
) {
    if constraints.is_empty() {
        fmtln!(fmt, "{}: &[],", field_name);
        return;
    }

    fmtln!(fmt, "{}: &[", field_name);
    fmt.indent(|fmt| {
        for (n, constraint) in constraints.iter().enumerate() {
            fmt.line("OperandConstraint {");
            fmt.indent(|fmt| {
                match constraint {
                    OperandConstraint::RegClass(reg_class) => {
                        if let Some(tied_input) = tied_operands.get(&n) {
                            fmtln!(fmt, "kind: ConstraintKind::Tied({}),", tied_input);
                        } else {
                            fmt.line("kind: ConstraintKind::Reg,");
                        }
                        fmtln!(
                            fmt,
                            "regclass: &{}_DATA,",
                            registers.classes[*reg_class].name
                        );
                    }
                    OperandConstraint::FixedReg(reg) => {
                        assert!(!tied_operands.contains_key(&n), "can't tie fixed registers");
                        let constraint_kind = if fixed_registers.contains(&reg) {
                            "FixedTied"
                        } else {
                            "FixedReg"
                        };
                        fmtln!(
                            fmt,
                            "kind: ConstraintKind::{}({}),",
                            constraint_kind,
                            reg.unit
                        );
                        fmtln!(
                            fmt,
                            "regclass: &{}_DATA,",
                            registers.classes[reg.regclass].name
                        );
                    }
                    OperandConstraint::TiedInput(tied_input) => {
                        // This is a tied output constraint. It should never happen
                        // for input constraints.
                        assert!(
                            tied_input == tied_operands.get(&n).unwrap(),
                            "invalid tied constraint"
                        );
                        fmtln!(fmt, "kind: ConstraintKind::Tied({}),", tied_input);

                        let tied_class = if let OperandConstraint::RegClass(tied_class) =
                            recipe.operands_in[*tied_input]
                        {
                            tied_class
                        } else {
                            panic!("tied constraints relate only to register inputs");
                        };

                        fmtln!(
                            fmt,
                            "regclass: &{}_DATA,",
                            registers.classes[tied_class].name
                        );
                    }
                    OperandConstraint::Stack(stack) => {
                        assert!(!tied_operands.contains_key(&n), "can't tie stack operand");
                        fmt.line("kind: ConstraintKind::Stack,");
                        fmtln!(
                            fmt,
                            "regclass: &{}_DATA,",
                            registers.classes[stack.regclass].name
                        );
                    }
                }
            });
            fmt.line("},");
        }
    });
    fmtln!(fmt, "],");
}

/// Emit a table of encoding recipe operand constraints keyed by recipe number.
///
/// These are used by the register allocator to pick registers that can be properly encoded.
fn emit_recipe_constraints(isa: &TargetIsa, fmt: &mut Formatter) {
    fmt.doc_comment(format!(
        r#"{} recipe constraints list, using the same recipe index spaces as the one
        specified by the corresponding binemit file. These constraints are used by register
        allocation to select the right location to use for input and output values."#,
        isa.name
    ));
    fmtln!(
        fmt,
        "static RECIPE_CONSTRAINTS: [RecipeConstraints; {}] = [",
        isa.recipes.len()
    );
    fmt.indent(|fmt| {
        for recipe in isa.recipes.values() {
            // Compute a mapping of tied operands in both directions (input tied to outputs and
            // conversely).
            let mut tied_in_to_out = HashMap::new();
            let mut tied_out_to_in = HashMap::new();
            for (out_index, constraint) in recipe.operands_out.iter().enumerate() {
                if let OperandConstraint::TiedInput(in_index) = &constraint {
                    tied_in_to_out.insert(*in_index, out_index);
                    tied_out_to_in.insert(out_index, *in_index);
                }
            }

            // Find the sets of registers involved in fixed register constraints.
            let fixed_inputs = get_fixed_registers(&recipe.operands_in);
            let fixed_outputs = get_fixed_registers(&recipe.operands_out);

            fmt.comment(format!("Constraints for recipe {}:", recipe.name));
            fmt.line("RecipeConstraints {");
            fmt.indent(|fmt| {
                emit_operand_constraints(
                    &isa.regs,
                    recipe,
                    &recipe.operands_in,
                    "ins",
                    &tied_in_to_out,
                    &fixed_outputs,
                    fmt,
                );
                emit_operand_constraints(
                    &isa.regs,
                    recipe,
                    &recipe.operands_out,
                    "outs",
                    &tied_out_to_in,
                    &fixed_inputs,
                    fmt,
                );
                fmtln!(
                    fmt,
                    "fixed_ins: {},",
                    if !fixed_inputs.is_empty() {
                        "true"
                    } else {
                        "false"
                    }
                );
                fmtln!(
                    fmt,
                    "fixed_outs: {},",
                    if !fixed_outputs.is_empty() {
                        "true"
                    } else {
                        "false"
                    }
                );
                fmtln!(
                    fmt,
                    "tied_ops: {},",
                    if !tied_in_to_out.is_empty() {
                        "true"
                    } else {
                        "false"
                    }
                );
                fmtln!(
                    fmt,
                    "clobbers_flags: {},",
                    if recipe.clobbers_flags {
                        "true"
                    } else {
                        "false"
                    }
                );
            });
            fmt.line("},");
        }
    });
    fmtln!(fmt, "];");
    fmt.empty_line();
}

/// Emit a table of encoding recipe code size information.
fn emit_recipe_sizing(isa: &TargetIsa, fmt: &mut Formatter) {
    fmt.doc_comment(format!(
        r#"{} recipe sizing descriptors, using the same recipe index spaces as the one
        specified by the corresponding binemit file. These are used to compute the final size of an
        instruction, as well as to compute the range of branches."#,
        isa.name
    ));
    fmtln!(
        fmt,
        "static RECIPE_SIZING: [RecipeSizing; {}] = [",
        isa.recipes.len()
    );
    fmt.indent(|fmt| {
        for recipe in isa.recipes.values() {
            fmt.comment(format!("Code size information for recipe {}:", recipe.name));
            fmt.line("RecipeSizing {");
            fmt.indent(|fmt| {
                fmtln!(fmt, "base_size: {},", recipe.base_size);
                fmtln!(fmt, "compute_size: {},", recipe.compute_size);
                if let Some(range) = &recipe.branch_range {
                    fmtln!(
                        fmt,
                        "branch_range: Some(BranchRange {{ origin: {}, bits: {} }}),",
                        range.inst_size,
                        range.range
                    );
                } else {
                    fmt.line("branch_range: None,");
                }
            });
            fmt.line("},");
        }
    });
    fmtln!(fmt, "];");
    fmt.empty_line();
}

/// Level 1 table mapping types to `Level2` objects.
struct Level1Table<'cpu_mode> {
    cpu_mode: &'cpu_mode CpuMode,
    legalize_code: TransformGroupIndex,

    table_map: HashMap<Option<ValueType>, usize>,
    table_vec: Vec<Level2Table>,
}

impl<'cpu_mode> Level1Table<'cpu_mode> {
    fn new(cpu_mode: &'cpu_mode CpuMode) -> Self {
        Self {
            cpu_mode,
            legalize_code: cpu_mode.get_default_legalize_code(),
            table_map: HashMap::new(),
            table_vec: Vec::new(),
        }
    }

    /// Returns the level2 table for the given type; None means monomorphic, in this context.
    fn l2table_for(&mut self, typ: Option<ValueType>) -> &mut Level2Table {
        let cpu_mode = &self.cpu_mode;
        let index = match self.table_map.get(&typ) {
            Some(&index) => index,
            None => {
                let legalize_code = cpu_mode.get_legalize_code_for(&typ);
                let table = Level2Table::new(typ.clone(), legalize_code);
                let index = self.table_vec.len();
                self.table_map.insert(typ, index);
                self.table_vec.push(table);
                index
            }
        };
        self.table_vec.get_mut(index).unwrap()
    }

    fn l2tables(&mut self) -> Vec<&mut Level2Table> {
        self.table_vec
            .iter_mut()
            .filter(|table| !table.is_empty())
            .collect::<Vec<_>>()
    }
}

struct Level2HashTableEntry {
    inst_name: String,
    offset: usize,
}

/// Level 2 table mapping instruction opcodes to `EncList` objects.
///
/// A level 2 table can be completely empty if it only holds a custom legalization action for `ty`.
struct Level2Table {
    typ: Option<ValueType>,
    legalize_code: TransformGroupIndex,
    inst_to_encodings: BTreeMap<String, EncodingList>,
    hash_table_offset: Option<usize>,
    hash_table_len: Option<usize>,
}

impl Level2Table {
    fn new(typ: Option<ValueType>, legalize_code: TransformGroupIndex) -> Self {
        Self {
            typ,
            legalize_code,
            inst_to_encodings: BTreeMap::new(),
            hash_table_offset: None,
            hash_table_len: None,
        }
    }

    fn enclist_for(&mut self, inst: &Instruction) -> &mut EncodingList {
        let copied_typ = self.typ.clone();
        self.inst_to_encodings
            .entry(inst.name.clone())
            .or_insert_with(|| EncodingList::new(inst, copied_typ))
    }

    fn enclists(&mut self) -> btree_map::ValuesMut<'_, String, EncodingList> {
        self.inst_to_encodings.values_mut()
    }

    fn is_empty(&self) -> bool {
        self.inst_to_encodings.is_empty()
    }

    fn layout_hashtable(
        &mut self,
        level2_hashtables: &mut Vec<Option<Level2HashTableEntry>>,
        level2_doc: &mut HashMap<usize, Vec<String>>,
    ) {
        let hash_table = generate_table(
            self.inst_to_encodings.values(),
            self.inst_to_encodings.len(),
            // TODO the Python code wanted opcode numbers to start from 1.
            |enc_list| enc_list.inst.opcode_number.index() + 1,
        );

        let hash_table_offset = level2_hashtables.len();
        let hash_table_len = hash_table.len();

        assert!(self.hash_table_offset.is_none());
        assert!(self.hash_table_len.is_none());
        self.hash_table_offset = Some(hash_table_offset);
        self.hash_table_len = Some(hash_table_len);

        level2_hashtables.extend(hash_table.iter().map(|opt_enc_list| {
            opt_enc_list.map(|enc_list| Level2HashTableEntry {
                inst_name: enc_list.inst.camel_name.clone(),
                offset: enc_list.offset.unwrap(),
            })
        }));

        let typ_comment = match &self.typ {
            Some(ty) => ty.to_string(),
            None => "typeless".into(),
        };

        level2_doc.get_or_default(hash_table_offset).push(format!(
            "{:06x}: {}, {} entries",
            hash_table_offset, typ_comment, hash_table_len
        ));
    }
}

/// The u16 values in an encoding list entry are interpreted as follows:
///
/// NR = len(all_recipes)
///
/// entry < 2*NR
///     Try Encoding(entry/2, next_entry) if the recipe predicate is satisfied.
///     If bit 0 is set, stop with the default legalization code.
///     If bit 0 is clear, keep going down the list.
/// entry < PRED_START
///     Stop with legalization code `entry - 2*NR`.
///
/// Remaining entries are interpreted as (skip, pred) pairs, where:
///
/// skip = (entry - PRED_START) >> PRED_BITS
/// pred = (entry - PRED_START) & PRED_MASK
///
/// If the predicate is satisfied, keep going. Otherwise skip over the next
/// `skip` entries. If skip == 0, stop with the default legalization code.
///
/// The `pred` predicate number is interpreted as an instruction predicate if it
/// is in range, otherwise an ISA predicate.

/// Encoding lists are represented as u16 arrays.
const CODE_BITS: usize = 16;

/// Beginning of the predicate code words.
const PRED_START: u16 = 0x1000;

/// Number of bits used to hold a predicate number (instruction + ISA predicates).
const PRED_BITS: usize = 12;

/// Mask for extracting the predicate number.
const PRED_MASK: usize = (1 << PRED_BITS) - 1;

/// Encoder for the list format above.
struct Encoder {
    num_instruction_predicates: usize,

    /// u16 encoding list words.
    words: Vec<u16>,

    /// Documentation comments: Index into `words` + comment.
    docs: Vec<(usize, String)>,
}

impl Encoder {
    fn new(num_instruction_predicates: usize) -> Self {
        Self {
            num_instruction_predicates,
            words: Vec::new(),
            docs: Vec::new(),
        }
    }

    /// Add a recipe+bits entry to the list.
    fn recipe(&mut self, recipes: &Recipes, enc: &Encoding, is_final: bool) {
        let code = (2 * enc.recipe.index() + if is_final { 1 } else { 0 }) as u16;
        assert!(code < PRED_START);

        let doc = format!(
            "--> {}{}",
            enc.to_rust_comment(recipes),
            if is_final { " and stop" } else { "" }
        );
        self.docs.push((self.words.len(), doc));

        self.words.push(code);
        self.words.push(enc.encbits);
    }

    /// Add a predicate entry.
    fn pred(&mut self, pred_comment: String, skip: usize, n: usize) {
        assert!(n <= PRED_MASK);
        let entry = (PRED_START as usize) + (n | (skip << PRED_BITS));
        assert!(entry < (1 << CODE_BITS));
        let entry = entry as u16;

        let doc = if skip == 0 {
            "stop".to_string()
        } else {
            format!("skip {}", skip)
        };
        let doc = format!("{} unless {}", doc, pred_comment);

        self.docs.push((self.words.len(), doc));
        self.words.push(entry);
    }

    /// Add an instruction predicate entry.
    fn inst_predicate(&mut self, pred: InstructionPredicateNumber, skip: usize) {
        let number = pred.index();
        let pred_comment = format!("inst_predicate_{}", number);
        self.pred(pred_comment, skip, number);
    }

    /// Add an ISA predicate entry.
    fn isa_predicate(&mut self, pred: SettingPredicateNumber, skip: usize) {
        // ISA predicates follow the instruction predicates.
        let n = self.num_instruction_predicates + (pred as usize);
        let pred_comment = format!("PredicateView({})", pred);
        self.pred(pred_comment, skip, n);
    }
}

/// List of instructions for encoding a given type + opcode pair.
///
/// An encoding list contains a sequence of predicates and encoding recipes, all encoded as u16
/// values.
struct EncodingList {
    inst: Instruction,
    typ: Option<ValueType>,
    encodings: Vec<Encoding>,
    offset: Option<usize>,
}

impl EncodingList {
    fn new(inst: &Instruction, typ: Option<ValueType>) -> Self {
        Self {
            inst: inst.clone(),
            typ,
            encodings: Default::default(),
            offset: None,
        }
    }

    /// Encode this list as a sequence of u16 numbers.
    ///
    /// Adds the sequence to `enc_lists` and records the returned offset as
    /// `self.offset`.
    ///
    /// Adds comment lines to `enc_lists_doc` keyed by enc_lists offsets.
    fn encode(
        &mut self,
        isa: &TargetIsa,
        cpu_mode: &CpuMode,
        enc_lists: &mut UniqueSeqTable<u16>,
        enc_lists_doc: &mut HashMap<usize, Vec<String>>,
    ) {
        assert!(!self.encodings.is_empty());

        let mut encoder = Encoder::new(isa.encodings_predicates.len());

        let mut index = 0;
        while index < self.encodings.len() {
            let encoding = &self.encodings[index];

            // Try to see how many encodings are following and have the same ISA predicate and
            // instruction predicate, so as to reduce the number of tests carried out by the
            // encoding list interpreter..
            //
            // Encodings with similar tests are hereby called a group. The group includes the
            // current encoding we're looking at.
            let (isa_predicate, inst_predicate) =
                (&encoding.isa_predicate, &encoding.inst_predicate);

            let group_size = {
                let mut group_size = 1;
                while index + group_size < self.encodings.len() {
                    let next_encoding = &self.encodings[index + group_size];
                    if &next_encoding.inst_predicate != inst_predicate
                        || &next_encoding.isa_predicate != isa_predicate
                    {
                        break;
                    }
                    group_size += 1;
                }
                group_size
            };

            let is_last_group = index + group_size == self.encodings.len();

            // The number of entries to skip when a predicate isn't satisfied is the size of both
            // predicates + the size of the group, minus one (for this predicate). Each recipe
            // entry has a size of two u16 (recipe index + bits).
            let mut skip = if is_last_group {
                0
            } else {
                let isap_size = match isa_predicate {
                    Some(_) => 1,
                    None => 0,
                };
                let instp_size = match inst_predicate {
                    Some(_) => 1,
                    None => 0,
                };
                isap_size + instp_size + group_size * 2 - 1
            };

            if let Some(pred) = isa_predicate {
                encoder.isa_predicate(*pred, skip);
                if !is_last_group {
                    skip -= 1;
                }
            }

            if let Some(pred) = inst_predicate {
                encoder.inst_predicate(*pred, skip);
                // No need to update skip, it's dead after this point.
            }

            for i in 0..group_size {
                let encoding = &self.encodings[index + i];
                let is_last_encoding = index + i == self.encodings.len() - 1;
                encoder.recipe(&isa.recipes, encoding, is_last_encoding);
            }

            index += group_size;
        }

        assert!(self.offset.is_none());
        let offset = enc_lists.add(&encoder.words);
        self.offset = Some(offset);

        // Doc comments.
        let recipe_typ_mode_name = format!(
            "{}{} ({})",
            self.inst.name,
            if let Some(typ) = &self.typ {
                format!(".{}", typ.to_string())
            } else {
                "".into()
            },
            cpu_mode.name
        );

        enc_lists_doc
            .get_or_default(offset)
            .push(format!("{:06x}: {}", offset, recipe_typ_mode_name));
        for (pos, doc) in encoder.docs {
            enc_lists_doc.get_or_default(offset + pos).push(doc);
        }
        enc_lists_doc
            .get_or_default(offset + encoder.words.len())
            .insert(0, format!("end of {}", recipe_typ_mode_name));
    }
}

fn make_tables(cpu_mode: &CpuMode) -> Level1Table {
    let mut table = Level1Table::new(cpu_mode);

    for encoding in &cpu_mode.encodings {
        table
            .l2table_for(encoding.bound_type.clone())
            .enclist_for(encoding.inst())
            .encodings
            .push(encoding.clone());
    }

    // Ensure there are level 1 table entries for all types with a custom legalize action.
    for value_type in cpu_mode.get_legalized_types() {
        table.l2table_for(Some(value_type.clone()));
    }
    // ... and also for monomorphic instructions.
    table.l2table_for(None);

    table
}

/// Compute encodings and doc comments for encoding lists in `level1`.
fn encode_enclists(
    isa: &TargetIsa,
    cpu_mode: &CpuMode,
    level1: &mut Level1Table,
    enc_lists: &mut UniqueSeqTable<u16>,
    enc_lists_doc: &mut HashMap<usize, Vec<String>>,
) {
    for level2 in level1.l2tables() {
        for enclist in level2.enclists() {
            enclist.encode(isa, cpu_mode, enc_lists, enc_lists_doc);
        }
    }
}

fn encode_level2_hashtables<'a>(
    level1: &'a mut Level1Table,
    level2_hashtables: &mut Vec<Option<Level2HashTableEntry>>,
    level2_doc: &mut HashMap<usize, Vec<String>>,
) {
    for level2 in level1.l2tables() {
        level2.layout_hashtable(level2_hashtables, level2_doc);
    }
}

fn emit_encoding_tables(defs: &SharedDefinitions, isa: &TargetIsa, fmt: &mut Formatter) {
    // Level 1 tables, one per CPU mode.
    let mut level1_tables: HashMap<&'static str, Level1Table> = HashMap::new();

    // Single table containing all the level2 hash tables.
    let mut level2_hashtables = Vec::new();
    let mut level2_doc: HashMap<usize, Vec<String>> = HashMap::new();

    // Tables for encoding lists with comments.
    let mut enc_lists = UniqueSeqTable::new();
    let mut enc_lists_doc = HashMap::new();

    for cpu_mode in &isa.cpu_modes {
        level2_doc
            .get_or_default(level2_hashtables.len())
            .push(cpu_mode.name.into());

        let mut level1 = make_tables(cpu_mode);

        encode_enclists(
            isa,
            cpu_mode,
            &mut level1,
            &mut enc_lists,
            &mut enc_lists_doc,
        );
        encode_level2_hashtables(&mut level1, &mut level2_hashtables, &mut level2_doc);

        level1_tables.insert(cpu_mode.name, level1);
    }

    // Compute an appropriate Rust integer type to use for offsets into a table of the given length.
    let offset_type = |length: usize| {
        if length <= 0x10000 {
            "u16"
        } else {
            assert!(u32::try_from(length).is_ok(), "table too big!");
            "u32"
        }
    };

    let level1_offset_type = offset_type(level2_hashtables.len());
    let level2_offset_type = offset_type(enc_lists.len());

    // Emit encoding lists.
    fmt.doc_comment(
        format!(r#"{} encoding lists.

        This contains the entire encodings bytecode for every single instruction; the encodings
        interpreter knows where to start from thanks to the initial lookup in the level 1 and level 2
        table entries below."#, isa.name)
    );
    fmtln!(fmt, "pub static ENCLISTS: [u16; {}] = [", enc_lists.len());
    fmt.indent(|fmt| {
        let mut line = Vec::new();
        for (index, entry) in enc_lists.iter().enumerate() {
            if let Some(comments) = enc_lists_doc.get(&index) {
                if !line.is_empty() {
                    fmtln!(fmt, "{},", line.join(", "));
                    line.clear();
                }
                for comment in comments {
                    fmt.comment(comment);
                }
            }
            line.push(format!("{:#06x}", entry));
        }
        if !line.is_empty() {
            fmtln!(fmt, "{},", line.join(", "));
        }
    });
    fmtln!(fmt, "];");
    fmt.empty_line();

    // Emit the full concatenation of level 2 hash tables.
    fmt.doc_comment(format!(
        r#"{} level 2 hash tables.

        This hash table, keyed by instruction opcode, contains all the starting offsets for the
        encodings interpreter, for all the CPU modes. It is jumped to after a lookup on the
        instruction's controlling type in the level 1 hash table."#,
        isa.name
    ));
    fmtln!(
        fmt,
        "pub static LEVEL2: [Level2Entry<{}>; {}] = [",
        level2_offset_type,
        level2_hashtables.len()
    );
    fmt.indent(|fmt| {
        for (offset, entry) in level2_hashtables.iter().enumerate() {
            if let Some(comments) = level2_doc.get(&offset) {
                for comment in comments {
                    fmt.comment(comment);
                }
            }
            if let Some(entry) = entry {
                fmtln!(
                    fmt,
                    "Level2Entry {{ opcode: Some(crate::ir::Opcode::{}), offset: {:#08x} }},",
                    entry.inst_name,
                    entry.offset
                );
            } else {
                fmt.line("Level2Entry { opcode: None, offset: 0 },");
            }
        }
    });
    fmtln!(fmt, "];");
    fmt.empty_line();

    // Emit a level 1 hash table for each CPU mode.
    for cpu_mode in &isa.cpu_modes {
        let level1 = &level1_tables.get(cpu_mode.name).unwrap();
        let hash_table = generate_table(
            level1.table_vec.iter(),
            level1.table_vec.len(),
            |level2_table| {
                if let Some(typ) = &level2_table.typ {
                    typ.number().expect("type without a number") as usize
                } else {
                    0
                }
            },
        );

        fmt.doc_comment(format!(
            r#"{} level 1 hash table for the CPU mode {}.

            This hash table, keyed by instruction controlling type, contains all the level 2
            hash-tables offsets for the given CPU mode, as well as a legalization identifier indicating
            which legalization scheme to apply when the instruction doesn't have any valid encoding for
            this CPU mode.
        "#,
            isa.name, cpu_mode.name
        ));
        fmtln!(
            fmt,
            "pub static LEVEL1_{}: [Level1Entry<{}>; {}] = [",
            cpu_mode.name.to_uppercase(),
            level1_offset_type,
            hash_table.len()
        );
        fmt.indent(|fmt| {
            for opt_level2 in hash_table {
                let level2 = match opt_level2 {
                    None => {
                        // Empty hash table entry. Include the default legalization action.
                        fmtln!(fmt, "Level1Entry {{ ty: ir::types::INVALID, log2len: !0, offset: 0, legalize: {} }},",
                               isa.translate_group_index(level1.legalize_code));
                        continue;
                    }
                    Some(level2) => level2,
                };

                let legalize_comment = defs.transform_groups.get(level2.legalize_code).name;
                let legalize_code = isa.translate_group_index(level2.legalize_code);

                let typ_name = if let Some(typ) = &level2.typ {
                    typ.rust_name()
                } else {
                    "ir::types::INVALID".into()
                };

                if level2.is_empty() {
                    // Empty level 2 table: Only a specialized legalization action, no actual
                    // table.
                    // Set an offset that is out of bounds, but make sure it doesn't overflow its
                    // type when adding `1<<log2len`.
                    fmtln!(fmt, "Level1Entry {{ ty: {}, log2len: 0, offset: !0 - 1, legalize: {} }}, // {}",
                           typ_name, legalize_code, legalize_comment);
                    continue;
                }

                // Proper level 2 hash table.
                let l2l = (level2.hash_table_len.unwrap() as f64).log2() as i32;
                assert!(l2l > 0, "Level2 hash table was too small.");
                fmtln!(fmt, "Level1Entry {{ ty: {}, log2len: {}, offset: {:#08x}, legalize: {} }}, // {}",
                       typ_name, l2l, level2.hash_table_offset.unwrap(), legalize_code, legalize_comment);
            }
        });
        fmtln!(fmt, "];");
        fmt.empty_line();
    }
}

fn gen_isa(defs: &SharedDefinitions, isa: &TargetIsa, fmt: &mut Formatter) {
    // Make the `RECIPE_PREDICATES` table.
    emit_recipe_predicates(isa, fmt);

    // Make the `INST_PREDICATES` table.
    emit_inst_predicates(isa, fmt);

    emit_encoding_tables(defs, isa, fmt);

    emit_recipe_names(isa, fmt);
    emit_recipe_constraints(isa, fmt);
    emit_recipe_sizing(isa, fmt);

    // Finally, tie it all together in an `EncInfo`.
    fmt.line("pub static INFO: isa::EncInfo = isa::EncInfo {");
    fmt.indent(|fmt| {
        fmt.line("constraints: &RECIPE_CONSTRAINTS,");
        fmt.line("sizing: &RECIPE_SIZING,");
        fmt.line("names: &RECIPE_NAMES,");
    });
    fmt.line("};");
}

pub(crate) fn generate(
    defs: &SharedDefinitions,
    isa: &TargetIsa,
    filename: &str,
    out_dir: &str,
) -> Result<(), error::Error> {
    let mut fmt = Formatter::new();
    gen_isa(defs, isa, &mut fmt);
    fmt.update_file(filename, out_dir)?;
    Ok(())
}