1 //! Support types for generated encoding tables.
2 //!
3 //! This module contains types and functions for working with the encoding tables generated by
4 //! `cranelift-codegen/meta/src/gen_encodings.rs`.
5
6 use crate::constant_hash::{probe, Table};
7 use crate::ir::{Function, InstructionData, Opcode, Type};
8 use crate::isa::{Encoding, Legalize};
9 use crate::settings::PredicateView;
10 use core::ops::Range;
11
12 /// A recipe predicate.
13 ///
14 /// This is a predicate function capable of testing ISA and instruction predicates simultaneously.
15 ///
16 /// A None predicate is always satisfied.
17 pub type RecipePredicate = Option<fn(PredicateView, &InstructionData) -> bool>;
18
19 /// An instruction predicate.
20 ///
21 /// This is a predicate function that needs to be tested in addition to the recipe predicate. It
22 /// can't depend on ISA settings.
23 pub type InstPredicate = fn(&Function, &InstructionData) -> bool;
24
25 /// Legalization action to perform when no encoding can be found for an instruction.
26 ///
27 /// This is an index into an ISA-specific table of legalization actions.
28 pub type LegalizeCode = u8;
29
30 /// Level 1 hash table entry.
31 ///
32 /// One level 1 hash table is generated per CPU mode. This table is keyed by the controlling type
33 /// variable, using `INVALID` for non-polymorphic instructions.
34 ///
35 /// The hash table values are references to level 2 hash tables, encoded as an offset in `LEVEL2`
36 /// where the table begins, and the binary logarithm of its length. All the level 2 hash tables
37 /// have a power-of-two size.
38 ///
39 /// Entries are generic over the offset type. It will typically be `u32` or `u16`, depending on the
40 /// size of the `LEVEL2` table.
41 ///
42 /// Empty entries are encoded with a `!0` value for `log2len` which will always be out of range.
43 /// Entries that have a `legalize` value but no level 2 table have an `offset` field that is out of
44 /// bounds.
45 pub struct Level1Entry<OffT: Into<u32> + Copy> {
46 pub ty: Type,
47 pub log2len: u8,
48 pub legalize: LegalizeCode,
49 pub offset: OffT,
50 }
51
52 impl<OffT: Into<u32> + Copy> Level1Entry<OffT> {
53 /// Get the level 2 table range indicated by this entry.
range(&self) -> Range<usize>54 fn range(&self) -> Range<usize> {
55 let b = self.offset.into() as usize;
56 b..b + (1 << self.log2len)
57 }
58 }
59
60 impl<OffT: Into<u32> + Copy> Table<Type> for [Level1Entry<OffT>] {
len(&self) -> usize61 fn len(&self) -> usize {
62 self.len()
63 }
64
key(&self, idx: usize) -> Option<Type>65 fn key(&self, idx: usize) -> Option<Type> {
66 if self[idx].log2len != !0 {
67 Some(self[idx].ty)
68 } else {
69 None
70 }
71 }
72 }
73
74 /// Level 2 hash table entry.
75 ///
76 /// The second level hash tables are keyed by `Opcode`, and contain an offset into the `ENCLISTS`
77 /// table where the encoding recipes for the instruction are stored.
78 ///
79 /// Entries are generic over the offset type which depends on the size of `ENCLISTS`. A `u16`
80 /// offset allows the entries to be only 32 bits each. There is no benefit to dropping down to `u8`
81 /// for tiny ISAs. The entries won't shrink below 32 bits since the opcode is expected to be 16
82 /// bits.
83 ///
84 /// Empty entries are encoded with a `NotAnOpcode` `opcode` field.
85 pub struct Level2Entry<OffT: Into<u32> + Copy> {
86 pub opcode: Option<Opcode>,
87 pub offset: OffT,
88 }
89
90 impl<OffT: Into<u32> + Copy> Table<Opcode> for [Level2Entry<OffT>] {
len(&self) -> usize91 fn len(&self) -> usize {
92 self.len()
93 }
94
key(&self, idx: usize) -> Option<Opcode>95 fn key(&self, idx: usize) -> Option<Opcode> {
96 self[idx].opcode
97 }
98 }
99
100 /// Two-level hash table lookup and iterator construction.
101 ///
102 /// Given the controlling type variable and instruction opcode, find the corresponding encoding
103 /// list.
104 ///
105 /// Returns an iterator that produces legal encodings for `inst`.
lookup_enclist<'a, OffT1, OffT2>( ctrl_typevar: Type, inst: &'a InstructionData, func: &'a Function, level1_table: &'static [Level1Entry<OffT1>], level2_table: &'static [Level2Entry<OffT2>], enclist: &'static [EncListEntry], legalize_actions: &'static [Legalize], recipe_preds: &'static [RecipePredicate], inst_preds: &'static [InstPredicate], isa_preds: PredicateView<'a>, ) -> Encodings<'a> where OffT1: Into<u32> + Copy, OffT2: Into<u32> + Copy,106 pub fn lookup_enclist<'a, OffT1, OffT2>(
107 ctrl_typevar: Type,
108 inst: &'a InstructionData,
109 func: &'a Function,
110 level1_table: &'static [Level1Entry<OffT1>],
111 level2_table: &'static [Level2Entry<OffT2>],
112 enclist: &'static [EncListEntry],
113 legalize_actions: &'static [Legalize],
114 recipe_preds: &'static [RecipePredicate],
115 inst_preds: &'static [InstPredicate],
116 isa_preds: PredicateView<'a>,
117 ) -> Encodings<'a>
118 where
119 OffT1: Into<u32> + Copy,
120 OffT2: Into<u32> + Copy,
121 {
122 let (offset, legalize) = match probe(level1_table, ctrl_typevar, ctrl_typevar.index()) {
123 Err(l1idx) => {
124 // No level 1 entry found for the type.
125 // We have a sentinel entry with the default legalization code.
126 (!0, level1_table[l1idx].legalize)
127 }
128 Ok(l1idx) => {
129 // We have a valid level 1 entry for this type.
130 let l1ent = &level1_table[l1idx];
131 let offset = match level2_table.get(l1ent.range()) {
132 Some(l2tab) => {
133 let opcode = inst.opcode();
134 match probe(l2tab, opcode, opcode as usize) {
135 Ok(l2idx) => l2tab[l2idx].offset.into() as usize,
136 Err(_) => !0,
137 }
138 }
139 // The l1ent range is invalid. This means that we just have a customized
140 // legalization code for this type. The level 2 table is empty.
141 None => !0,
142 };
143 (offset, l1ent.legalize)
144 }
145 };
146
147 // Now we have an offset into `enclist` that is `!0` when no encoding list could be found.
148 // The default legalization code is always valid.
149 Encodings::new(
150 offset,
151 legalize,
152 inst,
153 func,
154 enclist,
155 legalize_actions,
156 recipe_preds,
157 inst_preds,
158 isa_preds,
159 )
160 }
161
162 /// Encoding list entry.
163 ///
164 /// Encoding lists are represented as sequences of u16 words.
165 pub type EncListEntry = u16;
166
167 /// Number of bits used to represent a predicate. c.f. `meta/src/gen_encodings.rs`.
168 const PRED_BITS: u8 = 12;
169 const PRED_MASK: usize = (1 << PRED_BITS) - 1;
170 /// First code word representing a predicate check. c.f. `meta/src/gen_encodings.rs`.
171 const PRED_START: usize = 0x1000;
172
173 /// An iterator over legal encodings for the instruction.
174 pub struct Encodings<'a> {
175 // Current offset into `enclist`, or out of bounds after we've reached the end.
176 offset: usize,
177 // Legalization code to use of no encoding is found.
178 legalize: LegalizeCode,
179 inst: &'a InstructionData,
180 func: &'a Function,
181 enclist: &'static [EncListEntry],
182 legalize_actions: &'static [Legalize],
183 recipe_preds: &'static [RecipePredicate],
184 inst_preds: &'static [InstPredicate],
185 isa_preds: PredicateView<'a>,
186 }
187
188 impl<'a> Encodings<'a> {
189 /// Creates a new instance of `Encodings`.
190 ///
191 /// This iterator provides search for encodings that applies to the given instruction. The
192 /// encoding lists are laid out such that first call to `next` returns valid entry in the list
193 /// or `None`.
new( offset: usize, legalize: LegalizeCode, inst: &'a InstructionData, func: &'a Function, enclist: &'static [EncListEntry], legalize_actions: &'static [Legalize], recipe_preds: &'static [RecipePredicate], inst_preds: &'static [InstPredicate], isa_preds: PredicateView<'a>, ) -> Self194 pub fn new(
195 offset: usize,
196 legalize: LegalizeCode,
197 inst: &'a InstructionData,
198 func: &'a Function,
199 enclist: &'static [EncListEntry],
200 legalize_actions: &'static [Legalize],
201 recipe_preds: &'static [RecipePredicate],
202 inst_preds: &'static [InstPredicate],
203 isa_preds: PredicateView<'a>,
204 ) -> Self {
205 Encodings {
206 offset,
207 inst,
208 func,
209 legalize,
210 isa_preds,
211 recipe_preds,
212 inst_preds,
213 enclist,
214 legalize_actions,
215 }
216 }
217
218 /// Get the legalization action that caused the enumeration of encodings to stop.
219 /// This can be the default legalization action for the type or a custom code for the
220 /// instruction.
221 ///
222 /// This method must only be called after the iterator returns `None`.
legalize(&self) -> Legalize223 pub fn legalize(&self) -> Legalize {
224 debug_assert_eq!(self.offset, !0, "Premature Encodings::legalize()");
225 self.legalize_actions[self.legalize as usize]
226 }
227
228 /// Check if the `rpred` recipe predicate is satisfied.
check_recipe(&self, rpred: RecipePredicate) -> bool229 fn check_recipe(&self, rpred: RecipePredicate) -> bool {
230 match rpred {
231 Some(p) => p(self.isa_preds, self.inst),
232 None => true,
233 }
234 }
235
236 /// Check an instruction or isa predicate.
check_pred(&self, pred: usize) -> bool237 fn check_pred(&self, pred: usize) -> bool {
238 if let Some(&p) = self.inst_preds.get(pred) {
239 p(self.func, self.inst)
240 } else {
241 let pred = pred - self.inst_preds.len();
242 self.isa_preds.test(pred)
243 }
244 }
245 }
246
247 impl<'a> Iterator for Encodings<'a> {
248 type Item = Encoding;
249
next(&mut self) -> Option<Encoding>250 fn next(&mut self) -> Option<Encoding> {
251 while let Some(entryref) = self.enclist.get(self.offset) {
252 let entry = *entryref as usize;
253
254 // Check for "recipe+bits".
255 let recipe = entry >> 1;
256 if let Some(&rpred) = self.recipe_preds.get(recipe) {
257 let bits = self.offset + 1;
258 if entry & 1 == 0 {
259 self.offset += 2; // Next entry.
260 } else {
261 self.offset = !0; // Stop.
262 }
263 if self.check_recipe(rpred) {
264 return Some(Encoding::new(recipe as u16, self.enclist[bits]));
265 }
266 continue;
267 }
268
269 // Check for "stop with legalize".
270 if entry < PRED_START {
271 self.legalize = (entry - 2 * self.recipe_preds.len()) as LegalizeCode;
272 self.offset = !0; // Stop.
273 return None;
274 }
275
276 // Finally, this must be a predicate entry.
277 let pred_entry = entry - PRED_START;
278 let skip = pred_entry >> PRED_BITS;
279 let pred = pred_entry & PRED_MASK;
280
281 if self.check_pred(pred) {
282 self.offset += 1;
283 } else if skip == 0 {
284 self.offset = !0; // Stop.
285 return None;
286 } else {
287 self.offset += 1 + skip;
288 }
289 }
290 None
291 }
292 }
293