1 //! Generate sources for instruction encoding.
2 //!
3 //! The tables and functions generated here support the `TargetISA::encode()` function which
4 //! determines if a given instruction is legal, and if so, its `Encoding` data which consists of a
5 //! *recipe* and some *encoding* bits.
6 //!
7 //! The `encode` function doesn't actually generate the binary machine bits. Each recipe has a
8 //! corresponding hand-written function to do that after registers are allocated.
9 //!
10 //! This is the information available to us:
11 //!
12 //! - The instruction to be encoded as an `InstructionData` reference.
13 //! - The controlling type variable.
14 //! - The data-flow graph giving us access to the types of all values involved. This is needed for
15 //! testing any secondary type variables.
16 //! - A `PredicateView` reference for the ISA-specific settings for evaluating ISA predicates.
17 //! - The currently active CPU mode is determined by the ISA.
18 //!
19 //! ## Level 1 table lookup
20 //!
21 //! The CPU mode provides the first table. The key is the instruction's controlling type variable.
22 //! If the instruction is not polymorphic, use `INVALID` for the type variable. The table values
23 //! are level 2 tables.
24 //!
25 //! ## Level 2 table lookup
26 //!
27 //! The level 2 table is keyed by the instruction's opcode. The table values are *encoding lists*.
28 //!
29 //! The two-level table lookup allows the level 2 tables to be much smaller with good locality.
30 //! Code in any given function usually only uses a few different types, so many of the level 2
31 //! tables will be cold.
32 //!
33 //! ## Encoding lists
34 //!
35 //! An encoding list is a non-empty sequence of list entries. Each entry has one of these forms:
36 //!
37 //! 1. Recipe + bits. Use this encoding if the recipe predicate is satisfied.
38 //! 2. Recipe + bits, final entry. Use this encoding if the recipe predicate is satisfied.
39 //! Otherwise, stop with the default legalization code.
40 //! 3. Stop with legalization code.
41 //! 4. Predicate + skip count. Test predicate and skip N entries if it is false.
42 //! 5. Predicate + stop. Test predicate and stop with the default legalization code if it is false.
43 //!
44 //! The instruction predicate is also used to distinguish between polymorphic instructions with
45 //! different types for secondary type variables.
46
47 use std::collections::btree_map;
48 use std::collections::{BTreeMap, HashMap, HashSet};
49 use std::convert::TryFrom;
50 use std::iter::FromIterator;
51
52 use cranelift_codegen_shared::constant_hash::generate_table;
53 use cranelift_entity::EntityRef;
54
55 use crate::error;
56 use crate::srcgen::Formatter;
57
58 use crate::cdsl::cpu_modes::CpuMode;
59 use crate::cdsl::encodings::Encoding;
60 use crate::cdsl::instructions::{Instruction, InstructionPredicate, InstructionPredicateNumber};
61 use crate::cdsl::isa::TargetIsa;
62 use crate::cdsl::recipes::{EncodingRecipe, OperandConstraint, Recipes, Register};
63 use crate::cdsl::regs::IsaRegs;
64 use crate::cdsl::settings::SettingPredicateNumber;
65 use crate::cdsl::types::ValueType;
66 use crate::cdsl::xform::TransformGroupIndex;
67
68 use crate::shared::Definitions as SharedDefinitions;
69
70 use crate::default_map::MapWithDefault;
71 use crate::unique_table::UniqueSeqTable;
72
73 /// Emit code for matching an instruction predicate against an `InstructionData` reference called
74 /// `inst`.
75 ///
76 /// The generated code is an `if let` pattern match that falls through if the instruction has an
77 /// unexpected format. This should lead to a panic.
emit_instp(instp: &InstructionPredicate, has_func: bool, fmt: &mut Formatter)78 fn emit_instp(instp: &InstructionPredicate, has_func: bool, fmt: &mut Formatter) {
79 if let Some(type_predicate) = instp.type_predicate("func") {
80 fmt.line("let args = inst.arguments(&func.dfg.value_lists);");
81 fmt.line(type_predicate);
82 return;
83 }
84
85 let leaves = instp.collect_leaves();
86
87 let mut has_type_check = false;
88 let mut format_name = None;
89 let mut field_names = HashSet::new();
90
91 for leaf in leaves {
92 if leaf.is_type_predicate() {
93 has_type_check = true;
94 } else {
95 field_names.insert(leaf.format_destructuring_member_name());
96 let leaf_format_name = leaf.format_name();
97 match format_name {
98 None => format_name = Some(leaf_format_name),
99 Some(previous_format_name) => {
100 assert!(
101 previous_format_name == leaf_format_name,
102 "Format predicate can only operate on a single InstructionFormat; trying to use both {} and {}", previous_format_name, leaf_format_name
103 );
104 }
105 }
106 }
107 }
108
109 let mut fields = Vec::from_iter(field_names);
110 fields.sort();
111 let fields = fields.join(", ");
112
113 let format_name = format_name.expect("There should be a format name!");
114
115 fmtln!(
116 fmt,
117 "if let crate::ir::InstructionData::{} {{ {}, .. }} = *inst {{",
118 format_name,
119 fields
120 );
121 fmt.indent(|fmt| {
122 if has_type_check {
123 // We could implement this.
124 assert!(has_func, "recipe predicates can't check type variables.");
125 fmt.line("let args = inst.arguments(&func.dfg.value_lists);");
126 } else if has_func {
127 // Silence dead argument.
128 fmt.line("let _ = func;");
129 }
130 fmtln!(fmt, "return {};", instp.rust_predicate("func").unwrap());
131 });
132 fmtln!(fmt, "}");
133
134 fmt.line("unreachable!();");
135 }
136
137 /// Emit private functions for checking recipe predicates as well as a static `RECIPE_PREDICATES`
138 /// array indexed by recipe number.
139 ///
140 /// A recipe predicate is a combination of an ISA predicate and an instruction predicate. Many
141 /// recipes have identical predicates.
emit_recipe_predicates(isa: &TargetIsa, fmt: &mut Formatter)142 fn emit_recipe_predicates(isa: &TargetIsa, fmt: &mut Formatter) {
143 let mut predicate_names = HashMap::new();
144
145 fmt.comment(format!("{} recipe predicates.", isa.name));
146 for recipe in isa.recipes.values() {
147 let (isap, instp) = match (&recipe.isa_predicate, &recipe.inst_predicate) {
148 (None, None) => continue,
149 (isap, instp) if predicate_names.contains_key(&(isap, instp)) => continue,
150 (isap, instp) => (isap, instp),
151 };
152
153 let func_name = format!("recipe_predicate_{}", recipe.name.to_lowercase());
154 predicate_names.insert((isap, instp), func_name.clone());
155
156 // Generate the predicate function.
157 fmtln!(
158 fmt,
159 "fn {}({}: crate::settings::PredicateView, {}: &ir::InstructionData) -> bool {{",
160 func_name,
161 if isap.is_some() { "isap" } else { "_" },
162 if instp.is_some() { "inst" } else { "_" }
163 );
164 fmt.indent(|fmt| {
165 match (isap, instp) {
166 (Some(isap), None) => {
167 fmtln!(fmt, "isap.test({})", isap);
168 }
169 (None, Some(instp)) => {
170 emit_instp(instp, /* has func */ false, fmt);
171 }
172 (Some(isap), Some(instp)) => {
173 fmtln!(fmt, "isap.test({}) &&", isap);
174 emit_instp(instp, /* has func */ false, fmt);
175 }
176 _ => panic!("skipped above"),
177 }
178 });
179 fmtln!(fmt, "}");
180 }
181 fmt.empty_line();
182
183 // Generate the static table.
184 fmt.doc_comment(format!(
185 r#"{} recipe predicate table.
186
187 One entry per recipe, set to Some only when the recipe is guarded by a predicate."#,
188 isa.name
189 ));
190 fmtln!(
191 fmt,
192 "pub static RECIPE_PREDICATES: [RecipePredicate; {}] = [",
193 isa.recipes.len()
194 );
195 fmt.indent(|fmt| {
196 for recipe in isa.recipes.values() {
197 match (&recipe.isa_predicate, &recipe.inst_predicate) {
198 (None, None) => fmt.line("None,"),
199 key => fmtln!(fmt, "Some({}),", predicate_names.get(&key).unwrap()),
200 }
201 }
202 });
203 fmtln!(fmt, "];");
204 fmt.empty_line();
205 }
206
207 /// Emit private functions for matching instruction predicates as well as a static
208 /// `INST_PREDICATES` array indexed by predicate number.
emit_inst_predicates(isa: &TargetIsa, fmt: &mut Formatter)209 fn emit_inst_predicates(isa: &TargetIsa, fmt: &mut Formatter) {
210 fmt.comment(format!("{} instruction predicates.", isa.name));
211 for (id, instp) in isa.encodings_predicates.iter() {
212 fmtln!(fmt, "fn inst_predicate_{}(func: &crate::ir::Function, inst: &crate::ir::InstructionData) -> bool {{", id.index());
213 fmt.indent(|fmt| {
214 emit_instp(instp, /* has func */ true, fmt);
215 });
216 fmtln!(fmt, "}");
217 }
218 fmt.empty_line();
219
220 // Generate the static table.
221 fmt.doc_comment(format!(
222 r#"{} instruction predicate table.
223
224 One entry per instruction predicate, so the encoding bytecode can embed indexes into this
225 table."#,
226 isa.name
227 ));
228 fmtln!(
229 fmt,
230 "pub static INST_PREDICATES: [InstPredicate; {}] = [",
231 isa.encodings_predicates.len()
232 );
233 fmt.indent(|fmt| {
234 for id in isa.encodings_predicates.keys() {
235 fmtln!(fmt, "inst_predicate_{},", id.index());
236 }
237 });
238 fmtln!(fmt, "];");
239 fmt.empty_line();
240 }
241
242 /// Emit a table of encoding recipe names keyed by recipe number.
243 ///
244 /// This is used for pretty-printing encodings.
emit_recipe_names(isa: &TargetIsa, fmt: &mut Formatter)245 fn emit_recipe_names(isa: &TargetIsa, fmt: &mut Formatter) {
246 fmt.doc_comment(format!(
247 r#"{} recipe names, using the same recipe index spaces as the one specified by the
248 corresponding binemit file."#,
249 isa.name
250 ));
251 fmtln!(
252 fmt,
253 "static RECIPE_NAMES: [&str; {}] = [",
254 isa.recipes.len()
255 );
256 fmt.indent(|fmt| {
257 for recipe in isa.recipes.values() {
258 fmtln!(fmt, r#""{}","#, recipe.name);
259 }
260 });
261 fmtln!(fmt, "];");
262 fmt.empty_line();
263 }
264
265 /// Returns a set of all the registers involved in fixed register constraints.
get_fixed_registers(operands_in: &[OperandConstraint]) -> HashSet<Register>266 fn get_fixed_registers(operands_in: &[OperandConstraint]) -> HashSet<Register> {
267 HashSet::from_iter(
268 operands_in
269 .iter()
270 .map(|constraint| {
271 if let OperandConstraint::FixedReg(reg) = &constraint {
272 Some(*reg)
273 } else {
274 None
275 }
276 })
277 .filter(|opt| opt.is_some())
278 .map(|opt| opt.unwrap()),
279 )
280 }
281
282 /// Emit a struct field initializer for an array of operand constraints.
283 ///
284 /// Note "fixed_registers" must refer to the other kind of operands (i.e. if we're operating on
285 /// inputs, fixed_registers must contain the fixed output registers).
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, )286 fn emit_operand_constraints(
287 registers: &IsaRegs,
288 recipe: &EncodingRecipe,
289 constraints: &[OperandConstraint],
290 field_name: &'static str,
291 tied_operands: &HashMap<usize, usize>,
292 fixed_registers: &HashSet<Register>,
293 fmt: &mut Formatter,
294 ) {
295 if constraints.is_empty() {
296 fmtln!(fmt, "{}: &[],", field_name);
297 return;
298 }
299
300 fmtln!(fmt, "{}: &[", field_name);
301 fmt.indent(|fmt| {
302 for (n, constraint) in constraints.iter().enumerate() {
303 fmt.line("OperandConstraint {");
304 fmt.indent(|fmt| {
305 match constraint {
306 OperandConstraint::RegClass(reg_class) => {
307 if let Some(tied_input) = tied_operands.get(&n) {
308 fmtln!(fmt, "kind: ConstraintKind::Tied({}),", tied_input);
309 } else {
310 fmt.line("kind: ConstraintKind::Reg,");
311 }
312 fmtln!(
313 fmt,
314 "regclass: &{}_DATA,",
315 registers.classes[*reg_class].name
316 );
317 }
318 OperandConstraint::FixedReg(reg) => {
319 assert!(!tied_operands.contains_key(&n), "can't tie fixed registers");
320 let constraint_kind = if fixed_registers.contains(®) {
321 "FixedTied"
322 } else {
323 "FixedReg"
324 };
325 fmtln!(
326 fmt,
327 "kind: ConstraintKind::{}({}),",
328 constraint_kind,
329 reg.unit
330 );
331 fmtln!(
332 fmt,
333 "regclass: &{}_DATA,",
334 registers.classes[reg.regclass].name
335 );
336 }
337 OperandConstraint::TiedInput(tied_input) => {
338 // This is a tied output constraint. It should never happen
339 // for input constraints.
340 assert!(
341 tied_input == tied_operands.get(&n).unwrap(),
342 "invalid tied constraint"
343 );
344 fmtln!(fmt, "kind: ConstraintKind::Tied({}),", tied_input);
345
346 let tied_class = if let OperandConstraint::RegClass(tied_class) =
347 recipe.operands_in[*tied_input]
348 {
349 tied_class
350 } else {
351 panic!("tied constraints relate only to register inputs");
352 };
353
354 fmtln!(
355 fmt,
356 "regclass: &{}_DATA,",
357 registers.classes[tied_class].name
358 );
359 }
360 OperandConstraint::Stack(stack) => {
361 assert!(!tied_operands.contains_key(&n), "can't tie stack operand");
362 fmt.line("kind: ConstraintKind::Stack,");
363 fmtln!(
364 fmt,
365 "regclass: &{}_DATA,",
366 registers.classes[stack.regclass].name
367 );
368 }
369 }
370 });
371 fmt.line("},");
372 }
373 });
374 fmtln!(fmt, "],");
375 }
376
377 /// Emit a table of encoding recipe operand constraints keyed by recipe number.
378 ///
379 /// These are used by the register allocator to pick registers that can be properly encoded.
emit_recipe_constraints(isa: &TargetIsa, fmt: &mut Formatter)380 fn emit_recipe_constraints(isa: &TargetIsa, fmt: &mut Formatter) {
381 fmt.doc_comment(format!(
382 r#"{} recipe constraints list, using the same recipe index spaces as the one
383 specified by the corresponding binemit file. These constraints are used by register
384 allocation to select the right location to use for input and output values."#,
385 isa.name
386 ));
387 fmtln!(
388 fmt,
389 "static RECIPE_CONSTRAINTS: [RecipeConstraints; {}] = [",
390 isa.recipes.len()
391 );
392 fmt.indent(|fmt| {
393 for recipe in isa.recipes.values() {
394 // Compute a mapping of tied operands in both directions (input tied to outputs and
395 // conversely).
396 let mut tied_in_to_out = HashMap::new();
397 let mut tied_out_to_in = HashMap::new();
398 for (out_index, constraint) in recipe.operands_out.iter().enumerate() {
399 if let OperandConstraint::TiedInput(in_index) = &constraint {
400 tied_in_to_out.insert(*in_index, out_index);
401 tied_out_to_in.insert(out_index, *in_index);
402 }
403 }
404
405 // Find the sets of registers involved in fixed register constraints.
406 let fixed_inputs = get_fixed_registers(&recipe.operands_in);
407 let fixed_outputs = get_fixed_registers(&recipe.operands_out);
408
409 fmt.comment(format!("Constraints for recipe {}:", recipe.name));
410 fmt.line("RecipeConstraints {");
411 fmt.indent(|fmt| {
412 emit_operand_constraints(
413 &isa.regs,
414 recipe,
415 &recipe.operands_in,
416 "ins",
417 &tied_in_to_out,
418 &fixed_outputs,
419 fmt,
420 );
421 emit_operand_constraints(
422 &isa.regs,
423 recipe,
424 &recipe.operands_out,
425 "outs",
426 &tied_out_to_in,
427 &fixed_inputs,
428 fmt,
429 );
430 fmtln!(
431 fmt,
432 "fixed_ins: {},",
433 if !fixed_inputs.is_empty() {
434 "true"
435 } else {
436 "false"
437 }
438 );
439 fmtln!(
440 fmt,
441 "fixed_outs: {},",
442 if !fixed_outputs.is_empty() {
443 "true"
444 } else {
445 "false"
446 }
447 );
448 fmtln!(
449 fmt,
450 "tied_ops: {},",
451 if !tied_in_to_out.is_empty() {
452 "true"
453 } else {
454 "false"
455 }
456 );
457 fmtln!(
458 fmt,
459 "clobbers_flags: {},",
460 if recipe.clobbers_flags {
461 "true"
462 } else {
463 "false"
464 }
465 );
466 });
467 fmt.line("},");
468 }
469 });
470 fmtln!(fmt, "];");
471 fmt.empty_line();
472 }
473
474 /// Emit a table of encoding recipe code size information.
emit_recipe_sizing(isa: &TargetIsa, fmt: &mut Formatter)475 fn emit_recipe_sizing(isa: &TargetIsa, fmt: &mut Formatter) {
476 fmt.doc_comment(format!(
477 r#"{} recipe sizing descriptors, using the same recipe index spaces as the one
478 specified by the corresponding binemit file. These are used to compute the final size of an
479 instruction, as well as to compute the range of branches."#,
480 isa.name
481 ));
482 fmtln!(
483 fmt,
484 "static RECIPE_SIZING: [RecipeSizing; {}] = [",
485 isa.recipes.len()
486 );
487 fmt.indent(|fmt| {
488 for recipe in isa.recipes.values() {
489 fmt.comment(format!("Code size information for recipe {}:", recipe.name));
490 fmt.line("RecipeSizing {");
491 fmt.indent(|fmt| {
492 fmtln!(fmt, "base_size: {},", recipe.base_size);
493 fmtln!(fmt, "compute_size: {},", recipe.compute_size);
494 if let Some(range) = &recipe.branch_range {
495 fmtln!(
496 fmt,
497 "branch_range: Some(BranchRange {{ origin: {}, bits: {} }}),",
498 range.inst_size,
499 range.range
500 );
501 } else {
502 fmt.line("branch_range: None,");
503 }
504 });
505 fmt.line("},");
506 }
507 });
508 fmtln!(fmt, "];");
509 fmt.empty_line();
510 }
511
512 /// Level 1 table mapping types to `Level2` objects.
513 struct Level1Table<'cpu_mode> {
514 cpu_mode: &'cpu_mode CpuMode,
515 legalize_code: TransformGroupIndex,
516
517 table_map: HashMap<Option<ValueType>, usize>,
518 table_vec: Vec<Level2Table>,
519 }
520
521 impl<'cpu_mode> Level1Table<'cpu_mode> {
new(cpu_mode: &'cpu_mode CpuMode) -> Self522 fn new(cpu_mode: &'cpu_mode CpuMode) -> Self {
523 Self {
524 cpu_mode,
525 legalize_code: cpu_mode.get_default_legalize_code(),
526 table_map: HashMap::new(),
527 table_vec: Vec::new(),
528 }
529 }
530
531 /// Returns the level2 table for the given type; None means monomorphic, in this context.
l2table_for(&mut self, typ: Option<ValueType>) -> &mut Level2Table532 fn l2table_for(&mut self, typ: Option<ValueType>) -> &mut Level2Table {
533 let cpu_mode = &self.cpu_mode;
534 let index = match self.table_map.get(&typ) {
535 Some(&index) => index,
536 None => {
537 let legalize_code = cpu_mode.get_legalize_code_for(&typ);
538 let table = Level2Table::new(typ.clone(), legalize_code);
539 let index = self.table_vec.len();
540 self.table_map.insert(typ, index);
541 self.table_vec.push(table);
542 index
543 }
544 };
545 self.table_vec.get_mut(index).unwrap()
546 }
547
l2tables(&mut self) -> Vec<&mut Level2Table>548 fn l2tables(&mut self) -> Vec<&mut Level2Table> {
549 self.table_vec
550 .iter_mut()
551 .filter(|table| !table.is_empty())
552 .collect::<Vec<_>>()
553 }
554 }
555
556 struct Level2HashTableEntry {
557 inst_name: String,
558 offset: usize,
559 }
560
561 /// Level 2 table mapping instruction opcodes to `EncList` objects.
562 ///
563 /// A level 2 table can be completely empty if it only holds a custom legalization action for `ty`.
564 struct Level2Table {
565 typ: Option<ValueType>,
566 legalize_code: TransformGroupIndex,
567 inst_to_encodings: BTreeMap<String, EncodingList>,
568 hash_table_offset: Option<usize>,
569 hash_table_len: Option<usize>,
570 }
571
572 impl Level2Table {
new(typ: Option<ValueType>, legalize_code: TransformGroupIndex) -> Self573 fn new(typ: Option<ValueType>, legalize_code: TransformGroupIndex) -> Self {
574 Self {
575 typ,
576 legalize_code,
577 inst_to_encodings: BTreeMap::new(),
578 hash_table_offset: None,
579 hash_table_len: None,
580 }
581 }
582
enclist_for(&mut self, inst: &Instruction) -> &mut EncodingList583 fn enclist_for(&mut self, inst: &Instruction) -> &mut EncodingList {
584 let copied_typ = self.typ.clone();
585 self.inst_to_encodings
586 .entry(inst.name.clone())
587 .or_insert_with(|| EncodingList::new(inst, copied_typ))
588 }
589
enclists(&mut self) -> btree_map::ValuesMut<'_, String, EncodingList>590 fn enclists(&mut self) -> btree_map::ValuesMut<'_, String, EncodingList> {
591 self.inst_to_encodings.values_mut()
592 }
593
is_empty(&self) -> bool594 fn is_empty(&self) -> bool {
595 self.inst_to_encodings.is_empty()
596 }
597
layout_hashtable( &mut self, level2_hashtables: &mut Vec<Option<Level2HashTableEntry>>, level2_doc: &mut HashMap<usize, Vec<String>>, )598 fn layout_hashtable(
599 &mut self,
600 level2_hashtables: &mut Vec<Option<Level2HashTableEntry>>,
601 level2_doc: &mut HashMap<usize, Vec<String>>,
602 ) {
603 let hash_table = generate_table(
604 self.inst_to_encodings.values(),
605 self.inst_to_encodings.len(),
606 // TODO the Python code wanted opcode numbers to start from 1.
607 |enc_list| enc_list.inst.opcode_number.index() + 1,
608 );
609
610 let hash_table_offset = level2_hashtables.len();
611 let hash_table_len = hash_table.len();
612
613 assert!(self.hash_table_offset.is_none());
614 assert!(self.hash_table_len.is_none());
615 self.hash_table_offset = Some(hash_table_offset);
616 self.hash_table_len = Some(hash_table_len);
617
618 level2_hashtables.extend(hash_table.iter().map(|opt_enc_list| {
619 opt_enc_list.map(|enc_list| Level2HashTableEntry {
620 inst_name: enc_list.inst.camel_name.clone(),
621 offset: enc_list.offset.unwrap(),
622 })
623 }));
624
625 let typ_comment = match &self.typ {
626 Some(ty) => ty.to_string(),
627 None => "typeless".into(),
628 };
629
630 level2_doc.get_or_default(hash_table_offset).push(format!(
631 "{:06x}: {}, {} entries",
632 hash_table_offset, typ_comment, hash_table_len
633 ));
634 }
635 }
636
637 /// The u16 values in an encoding list entry are interpreted as follows:
638 ///
639 /// NR = len(all_recipes)
640 ///
641 /// entry < 2*NR
642 /// Try Encoding(entry/2, next_entry) if the recipe predicate is satisfied.
643 /// If bit 0 is set, stop with the default legalization code.
644 /// If bit 0 is clear, keep going down the list.
645 /// entry < PRED_START
646 /// Stop with legalization code `entry - 2*NR`.
647 ///
648 /// Remaining entries are interpreted as (skip, pred) pairs, where:
649 ///
650 /// skip = (entry - PRED_START) >> PRED_BITS
651 /// pred = (entry - PRED_START) & PRED_MASK
652 ///
653 /// If the predicate is satisfied, keep going. Otherwise skip over the next
654 /// `skip` entries. If skip == 0, stop with the default legalization code.
655 ///
656 /// The `pred` predicate number is interpreted as an instruction predicate if it
657 /// is in range, otherwise an ISA predicate.
658
659 /// Encoding lists are represented as u16 arrays.
660 const CODE_BITS: usize = 16;
661
662 /// Beginning of the predicate code words.
663 const PRED_START: u16 = 0x1000;
664
665 /// Number of bits used to hold a predicate number (instruction + ISA predicates).
666 const PRED_BITS: usize = 12;
667
668 /// Mask for extracting the predicate number.
669 const PRED_MASK: usize = (1 << PRED_BITS) - 1;
670
671 /// Encoder for the list format above.
672 struct Encoder {
673 num_instruction_predicates: usize,
674
675 /// u16 encoding list words.
676 words: Vec<u16>,
677
678 /// Documentation comments: Index into `words` + comment.
679 docs: Vec<(usize, String)>,
680 }
681
682 impl Encoder {
new(num_instruction_predicates: usize) -> Self683 fn new(num_instruction_predicates: usize) -> Self {
684 Self {
685 num_instruction_predicates,
686 words: Vec::new(),
687 docs: Vec::new(),
688 }
689 }
690
691 /// Add a recipe+bits entry to the list.
recipe(&mut self, recipes: &Recipes, enc: &Encoding, is_final: bool)692 fn recipe(&mut self, recipes: &Recipes, enc: &Encoding, is_final: bool) {
693 let code = (2 * enc.recipe.index() + if is_final { 1 } else { 0 }) as u16;
694 assert!(code < PRED_START);
695
696 let doc = format!(
697 "--> {}{}",
698 enc.to_rust_comment(recipes),
699 if is_final { " and stop" } else { "" }
700 );
701 self.docs.push((self.words.len(), doc));
702
703 self.words.push(code);
704 self.words.push(enc.encbits);
705 }
706
707 /// Add a predicate entry.
pred(&mut self, pred_comment: String, skip: usize, n: usize)708 fn pred(&mut self, pred_comment: String, skip: usize, n: usize) {
709 assert!(n <= PRED_MASK);
710 let entry = (PRED_START as usize) + (n | (skip << PRED_BITS));
711 assert!(entry < (1 << CODE_BITS));
712 let entry = entry as u16;
713
714 let doc = if skip == 0 {
715 "stop".to_string()
716 } else {
717 format!("skip {}", skip)
718 };
719 let doc = format!("{} unless {}", doc, pred_comment);
720
721 self.docs.push((self.words.len(), doc));
722 self.words.push(entry);
723 }
724
725 /// Add an instruction predicate entry.
inst_predicate(&mut self, pred: InstructionPredicateNumber, skip: usize)726 fn inst_predicate(&mut self, pred: InstructionPredicateNumber, skip: usize) {
727 let number = pred.index();
728 let pred_comment = format!("inst_predicate_{}", number);
729 self.pred(pred_comment, skip, number);
730 }
731
732 /// Add an ISA predicate entry.
isa_predicate(&mut self, pred: SettingPredicateNumber, skip: usize)733 fn isa_predicate(&mut self, pred: SettingPredicateNumber, skip: usize) {
734 // ISA predicates follow the instruction predicates.
735 let n = self.num_instruction_predicates + (pred as usize);
736 let pred_comment = format!("PredicateView({})", pred);
737 self.pred(pred_comment, skip, n);
738 }
739 }
740
741 /// List of instructions for encoding a given type + opcode pair.
742 ///
743 /// An encoding list contains a sequence of predicates and encoding recipes, all encoded as u16
744 /// values.
745 struct EncodingList {
746 inst: Instruction,
747 typ: Option<ValueType>,
748 encodings: Vec<Encoding>,
749 offset: Option<usize>,
750 }
751
752 impl EncodingList {
new(inst: &Instruction, typ: Option<ValueType>) -> Self753 fn new(inst: &Instruction, typ: Option<ValueType>) -> Self {
754 Self {
755 inst: inst.clone(),
756 typ,
757 encodings: Default::default(),
758 offset: None,
759 }
760 }
761
762 /// Encode this list as a sequence of u16 numbers.
763 ///
764 /// Adds the sequence to `enc_lists` and records the returned offset as
765 /// `self.offset`.
766 ///
767 /// Adds comment lines to `enc_lists_doc` keyed by enc_lists offsets.
encode( &mut self, isa: &TargetIsa, cpu_mode: &CpuMode, enc_lists: &mut UniqueSeqTable<u16>, enc_lists_doc: &mut HashMap<usize, Vec<String>>, )768 fn encode(
769 &mut self,
770 isa: &TargetIsa,
771 cpu_mode: &CpuMode,
772 enc_lists: &mut UniqueSeqTable<u16>,
773 enc_lists_doc: &mut HashMap<usize, Vec<String>>,
774 ) {
775 assert!(!self.encodings.is_empty());
776
777 let mut encoder = Encoder::new(isa.encodings_predicates.len());
778
779 let mut index = 0;
780 while index < self.encodings.len() {
781 let encoding = &self.encodings[index];
782
783 // Try to see how many encodings are following and have the same ISA predicate and
784 // instruction predicate, so as to reduce the number of tests carried out by the
785 // encoding list interpreter..
786 //
787 // Encodings with similar tests are hereby called a group. The group includes the
788 // current encoding we're looking at.
789 let (isa_predicate, inst_predicate) =
790 (&encoding.isa_predicate, &encoding.inst_predicate);
791
792 let group_size = {
793 let mut group_size = 1;
794 while index + group_size < self.encodings.len() {
795 let next_encoding = &self.encodings[index + group_size];
796 if &next_encoding.inst_predicate != inst_predicate
797 || &next_encoding.isa_predicate != isa_predicate
798 {
799 break;
800 }
801 group_size += 1;
802 }
803 group_size
804 };
805
806 let is_last_group = index + group_size == self.encodings.len();
807
808 // The number of entries to skip when a predicate isn't satisfied is the size of both
809 // predicates + the size of the group, minus one (for this predicate). Each recipe
810 // entry has a size of two u16 (recipe index + bits).
811 let mut skip = if is_last_group {
812 0
813 } else {
814 let isap_size = match isa_predicate {
815 Some(_) => 1,
816 None => 0,
817 };
818 let instp_size = match inst_predicate {
819 Some(_) => 1,
820 None => 0,
821 };
822 isap_size + instp_size + group_size * 2 - 1
823 };
824
825 if let Some(pred) = isa_predicate {
826 encoder.isa_predicate(*pred, skip);
827 if !is_last_group {
828 skip -= 1;
829 }
830 }
831
832 if let Some(pred) = inst_predicate {
833 encoder.inst_predicate(*pred, skip);
834 // No need to update skip, it's dead after this point.
835 }
836
837 for i in 0..group_size {
838 let encoding = &self.encodings[index + i];
839 let is_last_encoding = index + i == self.encodings.len() - 1;
840 encoder.recipe(&isa.recipes, encoding, is_last_encoding);
841 }
842
843 index += group_size;
844 }
845
846 assert!(self.offset.is_none());
847 let offset = enc_lists.add(&encoder.words);
848 self.offset = Some(offset);
849
850 // Doc comments.
851 let recipe_typ_mode_name = format!(
852 "{}{} ({})",
853 self.inst.name,
854 if let Some(typ) = &self.typ {
855 format!(".{}", typ.to_string())
856 } else {
857 "".into()
858 },
859 cpu_mode.name
860 );
861
862 enc_lists_doc
863 .get_or_default(offset)
864 .push(format!("{:06x}: {}", offset, recipe_typ_mode_name));
865 for (pos, doc) in encoder.docs {
866 enc_lists_doc.get_or_default(offset + pos).push(doc);
867 }
868 enc_lists_doc
869 .get_or_default(offset + encoder.words.len())
870 .insert(0, format!("end of {}", recipe_typ_mode_name));
871 }
872 }
873
make_tables(cpu_mode: &CpuMode) -> Level1Table874 fn make_tables(cpu_mode: &CpuMode) -> Level1Table {
875 let mut table = Level1Table::new(cpu_mode);
876
877 for encoding in &cpu_mode.encodings {
878 table
879 .l2table_for(encoding.bound_type.clone())
880 .enclist_for(encoding.inst())
881 .encodings
882 .push(encoding.clone());
883 }
884
885 // Ensure there are level 1 table entries for all types with a custom legalize action.
886 for value_type in cpu_mode.get_legalized_types() {
887 table.l2table_for(Some(value_type.clone()));
888 }
889 // ... and also for monomorphic instructions.
890 table.l2table_for(None);
891
892 table
893 }
894
895 /// Compute encodings and doc comments for encoding lists in `level1`.
encode_enclists( isa: &TargetIsa, cpu_mode: &CpuMode, level1: &mut Level1Table, enc_lists: &mut UniqueSeqTable<u16>, enc_lists_doc: &mut HashMap<usize, Vec<String>>, )896 fn encode_enclists(
897 isa: &TargetIsa,
898 cpu_mode: &CpuMode,
899 level1: &mut Level1Table,
900 enc_lists: &mut UniqueSeqTable<u16>,
901 enc_lists_doc: &mut HashMap<usize, Vec<String>>,
902 ) {
903 for level2 in level1.l2tables() {
904 for enclist in level2.enclists() {
905 enclist.encode(isa, cpu_mode, enc_lists, enc_lists_doc);
906 }
907 }
908 }
909
encode_level2_hashtables<'a>( level1: &'a mut Level1Table, level2_hashtables: &mut Vec<Option<Level2HashTableEntry>>, level2_doc: &mut HashMap<usize, Vec<String>>, )910 fn encode_level2_hashtables<'a>(
911 level1: &'a mut Level1Table,
912 level2_hashtables: &mut Vec<Option<Level2HashTableEntry>>,
913 level2_doc: &mut HashMap<usize, Vec<String>>,
914 ) {
915 for level2 in level1.l2tables() {
916 level2.layout_hashtable(level2_hashtables, level2_doc);
917 }
918 }
919
emit_encoding_tables(defs: &SharedDefinitions, isa: &TargetIsa, fmt: &mut Formatter)920 fn emit_encoding_tables(defs: &SharedDefinitions, isa: &TargetIsa, fmt: &mut Formatter) {
921 // Level 1 tables, one per CPU mode.
922 let mut level1_tables: HashMap<&'static str, Level1Table> = HashMap::new();
923
924 // Single table containing all the level2 hash tables.
925 let mut level2_hashtables = Vec::new();
926 let mut level2_doc: HashMap<usize, Vec<String>> = HashMap::new();
927
928 // Tables for encoding lists with comments.
929 let mut enc_lists = UniqueSeqTable::new();
930 let mut enc_lists_doc = HashMap::new();
931
932 for cpu_mode in &isa.cpu_modes {
933 level2_doc
934 .get_or_default(level2_hashtables.len())
935 .push(cpu_mode.name.into());
936
937 let mut level1 = make_tables(cpu_mode);
938
939 encode_enclists(
940 isa,
941 cpu_mode,
942 &mut level1,
943 &mut enc_lists,
944 &mut enc_lists_doc,
945 );
946 encode_level2_hashtables(&mut level1, &mut level2_hashtables, &mut level2_doc);
947
948 level1_tables.insert(cpu_mode.name, level1);
949 }
950
951 // Compute an appropriate Rust integer type to use for offsets into a table of the given length.
952 let offset_type = |length: usize| {
953 if length <= 0x10000 {
954 "u16"
955 } else {
956 assert!(u32::try_from(length).is_ok(), "table too big!");
957 "u32"
958 }
959 };
960
961 let level1_offset_type = offset_type(level2_hashtables.len());
962 let level2_offset_type = offset_type(enc_lists.len());
963
964 // Emit encoding lists.
965 fmt.doc_comment(
966 format!(r#"{} encoding lists.
967
968 This contains the entire encodings bytecode for every single instruction; the encodings
969 interpreter knows where to start from thanks to the initial lookup in the level 1 and level 2
970 table entries below."#, isa.name)
971 );
972 fmtln!(fmt, "pub static ENCLISTS: [u16; {}] = [", enc_lists.len());
973 fmt.indent(|fmt| {
974 let mut line = Vec::new();
975 for (index, entry) in enc_lists.iter().enumerate() {
976 if let Some(comments) = enc_lists_doc.get(&index) {
977 if !line.is_empty() {
978 fmtln!(fmt, "{},", line.join(", "));
979 line.clear();
980 }
981 for comment in comments {
982 fmt.comment(comment);
983 }
984 }
985 line.push(format!("{:#06x}", entry));
986 }
987 if !line.is_empty() {
988 fmtln!(fmt, "{},", line.join(", "));
989 }
990 });
991 fmtln!(fmt, "];");
992 fmt.empty_line();
993
994 // Emit the full concatenation of level 2 hash tables.
995 fmt.doc_comment(format!(
996 r#"{} level 2 hash tables.
997
998 This hash table, keyed by instruction opcode, contains all the starting offsets for the
999 encodings interpreter, for all the CPU modes. It is jumped to after a lookup on the
1000 instruction's controlling type in the level 1 hash table."#,
1001 isa.name
1002 ));
1003 fmtln!(
1004 fmt,
1005 "pub static LEVEL2: [Level2Entry<{}>; {}] = [",
1006 level2_offset_type,
1007 level2_hashtables.len()
1008 );
1009 fmt.indent(|fmt| {
1010 for (offset, entry) in level2_hashtables.iter().enumerate() {
1011 if let Some(comments) = level2_doc.get(&offset) {
1012 for comment in comments {
1013 fmt.comment(comment);
1014 }
1015 }
1016 if let Some(entry) = entry {
1017 fmtln!(
1018 fmt,
1019 "Level2Entry {{ opcode: Some(crate::ir::Opcode::{}), offset: {:#08x} }},",
1020 entry.inst_name,
1021 entry.offset
1022 );
1023 } else {
1024 fmt.line("Level2Entry { opcode: None, offset: 0 },");
1025 }
1026 }
1027 });
1028 fmtln!(fmt, "];");
1029 fmt.empty_line();
1030
1031 // Emit a level 1 hash table for each CPU mode.
1032 for cpu_mode in &isa.cpu_modes {
1033 let level1 = &level1_tables.get(cpu_mode.name).unwrap();
1034 let hash_table = generate_table(
1035 level1.table_vec.iter(),
1036 level1.table_vec.len(),
1037 |level2_table| {
1038 if let Some(typ) = &level2_table.typ {
1039 typ.number().expect("type without a number") as usize
1040 } else {
1041 0
1042 }
1043 },
1044 );
1045
1046 fmt.doc_comment(format!(
1047 r#"{} level 1 hash table for the CPU mode {}.
1048
1049 This hash table, keyed by instruction controlling type, contains all the level 2
1050 hash-tables offsets for the given CPU mode, as well as a legalization identifier indicating
1051 which legalization scheme to apply when the instruction doesn't have any valid encoding for
1052 this CPU mode.
1053 "#,
1054 isa.name, cpu_mode.name
1055 ));
1056 fmtln!(
1057 fmt,
1058 "pub static LEVEL1_{}: [Level1Entry<{}>; {}] = [",
1059 cpu_mode.name.to_uppercase(),
1060 level1_offset_type,
1061 hash_table.len()
1062 );
1063 fmt.indent(|fmt| {
1064 for opt_level2 in hash_table {
1065 let level2 = match opt_level2 {
1066 None => {
1067 // Empty hash table entry. Include the default legalization action.
1068 fmtln!(fmt, "Level1Entry {{ ty: ir::types::INVALID, log2len: !0, offset: 0, legalize: {} }},",
1069 isa.translate_group_index(level1.legalize_code));
1070 continue;
1071 }
1072 Some(level2) => level2,
1073 };
1074
1075 let legalize_comment = defs.transform_groups.get(level2.legalize_code).name;
1076 let legalize_code = isa.translate_group_index(level2.legalize_code);
1077
1078 let typ_name = if let Some(typ) = &level2.typ {
1079 typ.rust_name()
1080 } else {
1081 "ir::types::INVALID".into()
1082 };
1083
1084 if level2.is_empty() {
1085 // Empty level 2 table: Only a specialized legalization action, no actual
1086 // table.
1087 // Set an offset that is out of bounds, but make sure it doesn't overflow its
1088 // type when adding `1<<log2len`.
1089 fmtln!(fmt, "Level1Entry {{ ty: {}, log2len: 0, offset: !0 - 1, legalize: {} }}, // {}",
1090 typ_name, legalize_code, legalize_comment);
1091 continue;
1092 }
1093
1094 // Proper level 2 hash table.
1095 let l2l = (level2.hash_table_len.unwrap() as f64).log2() as i32;
1096 assert!(l2l > 0, "Level2 hash table was too small.");
1097 fmtln!(fmt, "Level1Entry {{ ty: {}, log2len: {}, offset: {:#08x}, legalize: {} }}, // {}",
1098 typ_name, l2l, level2.hash_table_offset.unwrap(), legalize_code, legalize_comment);
1099 }
1100 });
1101 fmtln!(fmt, "];");
1102 fmt.empty_line();
1103 }
1104 }
1105
gen_isa(defs: &SharedDefinitions, isa: &TargetIsa, fmt: &mut Formatter)1106 fn gen_isa(defs: &SharedDefinitions, isa: &TargetIsa, fmt: &mut Formatter) {
1107 // Make the `RECIPE_PREDICATES` table.
1108 emit_recipe_predicates(isa, fmt);
1109
1110 // Make the `INST_PREDICATES` table.
1111 emit_inst_predicates(isa, fmt);
1112
1113 emit_encoding_tables(defs, isa, fmt);
1114
1115 emit_recipe_names(isa, fmt);
1116 emit_recipe_constraints(isa, fmt);
1117 emit_recipe_sizing(isa, fmt);
1118
1119 // Finally, tie it all together in an `EncInfo`.
1120 fmt.line("pub static INFO: isa::EncInfo = isa::EncInfo {");
1121 fmt.indent(|fmt| {
1122 fmt.line("constraints: &RECIPE_CONSTRAINTS,");
1123 fmt.line("sizing: &RECIPE_SIZING,");
1124 fmt.line("names: &RECIPE_NAMES,");
1125 });
1126 fmt.line("};");
1127 }
1128
generate( defs: &SharedDefinitions, isa: &TargetIsa, filename: &str, out_dir: &str, ) -> Result<(), error::Error>1129 pub(crate) fn generate(
1130 defs: &SharedDefinitions,
1131 isa: &TargetIsa,
1132 filename: &str,
1133 out_dir: &str,
1134 ) -> Result<(), error::Error> {
1135 let mut fmt = Formatter::new();
1136 gen_isa(defs, isa, &mut fmt);
1137 fmt.update_file(filename, out_dir)?;
1138 Ok(())
1139 }
1140