| 1 | .. _decodetree: |
| 2 | |
| 3 | ======================== |
| 4 | Decodetree Specification |
| 5 | ======================== |
| 6 | |
| 7 | A *decodetree* is built from instruction *patterns*. A pattern may |
| 8 | represent a single architectural instruction or a group of same, depending |
| 9 | on what is convenient for further processing. |
| 10 | |
| 11 | Each pattern has both *fixedbits* and *fixedmask*, the combination of which |
| 12 | describes the condition under which the pattern is matched:: |
| 13 | |
| 14 | (insn & fixedmask) == fixedbits |
| 15 | |
| 16 | Each pattern may have *fields*, which are extracted from the insn and |
| 17 | passed along to the translator. Examples of such are registers, |
| 18 | immediates, and sub-opcodes. |
| 19 | |
| 20 | In support of patterns, one may declare *fields*, *argument sets*, and |
| 21 | *formats*, each of which may be re-used to simplify further definitions. |
| 22 | |
| 23 | Fields |
| 24 | ====== |
| 25 | |
| 26 | Syntax:: |
| 27 | |
| 28 | field_def := '%' identifier ( field )* ( !function=identifier )? |
| 29 | field := unnamed_field | named_field |
| 30 | unnamed_field := number ':' ( 's' ) number |
| 31 | named_field := identifier ':' ( 's' ) number |
| 32 | |
| 33 | For *unnamed_field*, the first number is the least-significant bit position |
| 34 | of the field and the second number is the length of the field. If the 's' is |
| 35 | present, the field is considered signed. |
| 36 | |
| 37 | A *named_field* refers to some other field in the instruction pattern |
| 38 | or format. Regardless of the length of the other field where it is |
| 39 | defined, it will be inserted into this field with the specified |
| 40 | signedness and bit width. |
| 41 | |
| 42 | Field definitions that involve loops (i.e. where a field is defined |
| 43 | directly or indirectly in terms of itself) are errors. |
| 44 | |
| 45 | A format can include fields that refer to named fields that are |
| 46 | defined in the instruction pattern(s) that use the format. |
| 47 | Conversely, an instruction pattern can include fields that refer to |
| 48 | named fields that are defined in the format it uses. However you |
| 49 | cannot currently do both at once (i.e. pattern P uses format F; F has |
| 50 | a field A that refers to a named field B that is defined in P, and P |
| 51 | has a field C that refers to a named field D that is defined in F). |
| 52 | |
| 53 | If multiple ``fields`` are present, they are concatenated. |
| 54 | In this way one can define disjoint fields. |
| 55 | |
| 56 | If ``!function`` is specified, the concatenated result is passed through the |
| 57 | named function, taking and returning an integral value. |
| 58 | |
| 59 | One may use ``!function`` with zero ``fields``. This case is called |
| 60 | a *parameter*, and the named function is only passed the ``DisasContext`` |
| 61 | and returns an integral value extracted from there. |
| 62 | |
| 63 | A field with no ``fields`` and no ``!function`` is in error. |
| 64 | |
| 65 | Field examples: |
| 66 | |
| 67 | +-----------------------------+----------------------------------------------+ |
| 68 | | Input | Generated code | |
| 69 | +=============================+==============================================+ |
| 70 | | ``%disp 0:s16`` | :: | |
| 71 | | | | |
| 72 | | | sextract(i, 0, 16) | |
| 73 | +-----------------------------+----------------------------------------------+ |
| 74 | | ``%imm9 16:6 10:3`` | :: | |
| 75 | | | | |
| 76 | | | extract(i, 16, 6) << 3 | extract(i, 10, 3) | |
| 77 | +-----------------------------+----------------------------------------------+ |
| 78 | | ``%disp12 0:s1 1:1 2:10`` | :: | |
| 79 | | | | |
| 80 | | | sextract(i, 0, 1) << 11 | | |
| 81 | | | extract(i, 1, 1) << 10 | | |
| 82 | | | extract(i, 2, 10) | |
| 83 | +-----------------------------+----------------------------------------------+ |
| 84 | | ``%shimm8 5:s8 13:1 | :: | |
| 85 | | !function=expand_shimm8`` | | |
| 86 | | | expand_shimm8(sextract(i, 5, 8) << 1 | | |
| 87 | | | extract(i, 13, 1)) | |
| 88 | +-----------------------------+----------------------------------------------+ |
| 89 | | ``%sz_imm 10:2 sz:3 | :: | |
| 90 | | !function=expand_sz_imm`` | | |
| 91 | | | expand_sz_imm(extract(i, 10, 2) << 3 | | |
| 92 | | | extract(a->sz, 0, 3)) | |
| 93 | +-----------------------------+----------------------------------------------+ |
| 94 | |
| 95 | Argument Sets |
| 96 | ============= |
| 97 | |
| 98 | Syntax:: |
| 99 | |
| 100 | args_def := '&' identifier ( args_elt )+ ( !extern )? |
| 101 | args_elt := identifier (':' identifier)? |
| 102 | |
| 103 | Each *args_elt* defines an argument within the argument set. |
| 104 | If the form of the *args_elt* contains a colon, the first |
| 105 | identifier is the argument name and the second identifier is |
| 106 | the argument type. If the colon is missing, the argument |
| 107 | type will be ``int``. |
| 108 | |
| 109 | Each argument set will be rendered as a C structure "arg_$name" |
| 110 | with each of the fields being one of the member arguments. |
| 111 | |
| 112 | If ``!extern`` is specified, the backing structure is assumed |
| 113 | to have been already declared, typically via a second decoder. |
| 114 | |
| 115 | Argument sets are useful when one wants to define helper functions |
| 116 | for the translator functions that can perform operations on a common |
| 117 | set of arguments. This can ensure, for instance, that the ``AND`` |
| 118 | pattern and the ``OR`` pattern put their operands into the same named |
| 119 | structure, so that a common ``gen_logic_insn`` may be able to handle |
| 120 | the operations common between the two. |
| 121 | |
| 122 | Argument set examples:: |
| 123 | |
| 124 | ®3 ra rb rc |
| 125 | &loadstore reg base offset |
| 126 | &longldst reg base offset:int64_t |
| 127 | |
| 128 | |
| 129 | Formats |
| 130 | ======= |
| 131 | |
| 132 | Syntax:: |
| 133 | |
| 134 | fmt_def := '@' identifier ( fmt_elt )+ |
| 135 | fmt_elt := fixedbit_elt | field_elt | field_ref | args_ref |
| 136 | fixedbit_elt := [01.-]+ |
| 137 | field_elt := identifier ':' 's'? number |
| 138 | field_ref := '%' identifier | identifier '=' '%' identifier |
| 139 | args_ref := '&' identifier |
| 140 | |
| 141 | Defining a format is a handy way to avoid replicating groups of fields |
| 142 | across many instruction patterns. |
| 143 | |
| 144 | A *fixedbit_elt* describes a contiguous sequence of bits that must |
| 145 | be 1, 0, or don't care. The difference between '.' and '-' |
| 146 | is that '.' means that the bit will be covered with a field or a |
| 147 | final 0 or 1 from the pattern, and '-' means that the bit is really |
| 148 | ignored by the cpu and will not be specified. |
| 149 | |
| 150 | A *field_elt* describes a simple field only given a width; the position of |
| 151 | the field is implied by its position with respect to other *fixedbit_elt* |
| 152 | and *field_elt*. |
| 153 | |
| 154 | If any *fixedbit_elt* or *field_elt* appear, then all bits must be defined. |
| 155 | Padding with a *fixedbit_elt* of all '.' is an easy way to accomplish that. |
| 156 | |
| 157 | A *field_ref* incorporates a field by reference. This is the only way to |
| 158 | add a complex field to a format. A field may be renamed in the process |
| 159 | via assignment to another identifier. This is intended to allow the |
| 160 | same argument set be used with disjoint named fields. |
| 161 | |
| 162 | A single *args_ref* may specify an argument set to use for the format. |
| 163 | The set of fields in the format must be a subset of the arguments in |
| 164 | the argument set. If an argument set is not specified, one will be |
| 165 | inferred from the set of fields. |
| 166 | |
| 167 | It is recommended, but not required, that all *field_ref* and *args_ref* |
| 168 | appear at the end of the line, not interleaving with *fixedbit_elf* or |
| 169 | *field_elt*. |
| 170 | |
| 171 | Format examples:: |
| 172 | |
| 173 | @opr ...... ra:5 rb:5 ... 0 ....... rc:5 |
| 174 | @opi ...... ra:5 lit:8 1 ....... rc:5 |
| 175 | |
| 176 | Patterns |
| 177 | ======== |
| 178 | |
| 179 | Syntax:: |
| 180 | |
| 181 | pat_def := identifier ( pat_elt )+ |
| 182 | pat_elt := fixedbit_elt | field_elt | field_ref | args_ref | fmt_ref | const_elt |
| 183 | fmt_ref := '@' identifier |
| 184 | const_elt := identifier '=' number |
| 185 | |
| 186 | The *fixedbit_elt* and *field_elt* specifiers are unchanged from formats. |
| 187 | A pattern that does not specify a named format will have one inferred |
| 188 | from a referenced argument set (if present) and the set of fields. |
| 189 | |
| 190 | A *const_elt* allows a argument to be set to a constant value. This may |
| 191 | come in handy when fields overlap between patterns and one has to |
| 192 | include the values in the *fixedbit_elt* instead. |
| 193 | |
| 194 | The decoder will call a translator function for each pattern matched. |
| 195 | |
| 196 | Pattern examples:: |
| 197 | |
| 198 | addl_r 010000 ..... ..... .... 0000000 ..... @opr |
| 199 | addl_i 010000 ..... ..... .... 0000000 ..... @opi |
| 200 | |
| 201 | which will, in part, invoke:: |
| 202 | |
| 203 | trans_addl_r(ctx, &arg_opr, insn) |
| 204 | |
| 205 | and:: |
| 206 | |
| 207 | trans_addl_i(ctx, &arg_opi, insn) |
| 208 | |
| 209 | Pattern Groups |
| 210 | ============== |
| 211 | |
| 212 | Syntax:: |
| 213 | |
| 214 | group := overlap_group | no_overlap_group |
| 215 | overlap_group := '{' ( pat_def | group )+ '}' |
| 216 | no_overlap_group := '[' ( pat_def | group )+ ']' |
| 217 | |
| 218 | A *group* begins with a lone open-brace or open-bracket, with all |
| 219 | subsequent lines indented two spaces, and ending with a lone |
| 220 | close-brace or close-bracket. Groups may be nested, increasing the |
| 221 | required indentation of the lines within the nested group to two |
| 222 | spaces per nesting level. |
| 223 | |
| 224 | Patterns within overlap groups are allowed to overlap. Conflicts are |
| 225 | resolved by selecting the patterns in order. If all of the fixedbits |
| 226 | for a pattern match, its translate function will be called. If the |
| 227 | translate function returns false, then subsequent patterns within the |
| 228 | group will be matched. |
| 229 | |
| 230 | Patterns within no-overlap groups are not allowed to overlap, just |
| 231 | the same as ungrouped patterns. Thus no-overlap groups are intended |
| 232 | to be nested inside overlap groups. |
| 233 | |
| 234 | The following example from PA-RISC shows specialization of the *or* |
| 235 | instruction:: |
| 236 | |
| 237 | { |
| 238 | { |
| 239 | nop 000010 ----- ----- 0000 001001 0 00000 |
| 240 | copy 000010 00000 r1:5 0000 001001 0 rt:5 |
| 241 | } |
| 242 | or 000010 rt2:5 r1:5 cf:4 001001 0 rt:5 |
| 243 | } |
| 244 | |
| 245 | When the *cf* field is zero, the instruction has no side effects, |
| 246 | and may be specialized. When the *rt* field is zero, the output |
| 247 | is discarded and so the instruction has no effect. When the *rt2* |
| 248 | field is zero, the operation is ``reg[r1] | 0`` and so encodes |
| 249 | the canonical register copy operation. |
| 250 | |
| 251 | The output from the generator might look like:: |
| 252 | |
| 253 | switch (insn & 0xfc000fe0) { |
| 254 | case 0x08000240: |
| 255 | /* 000010.. ........ ....0010 010..... */ |
| 256 | if ((insn & 0x0000f000) == 0x00000000) { |
| 257 | /* 000010.. ........ 00000010 010..... */ |
| 258 | if ((insn & 0x0000001f) == 0x00000000) { |
| 259 | /* 000010.. ........ 00000010 01000000 */ |
| 260 | extract_decode_Fmt_0(&u.f_decode0, insn); |
| 261 | if (trans_nop(ctx, &u.f_decode0)) return true; |
| 262 | } |
| 263 | if ((insn & 0x03e00000) == 0x00000000) { |
| 264 | /* 00001000 000..... 00000010 010..... */ |
| 265 | extract_decode_Fmt_1(&u.f_decode1, insn); |
| 266 | if (trans_copy(ctx, &u.f_decode1)) return true; |
| 267 | } |
| 268 | } |
| 269 | extract_decode_Fmt_2(&u.f_decode2, insn); |
| 270 | if (trans_or(ctx, &u.f_decode2)) return true; |
| 271 | return false; |
| 272 | } |