2
* Copyright © 2020 Google, Inc.
4
* Permission is hereby granted, free of charge, to any person obtaining a
5
* copy of this software and associated documentation files (the "Software"),
6
* to deal in the Software without restriction, including without limitation
7
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
8
* and/or sell copies of the Software, and to permit persons to whom the
9
* Software is furnished to do so, subject to the following conditions:
11
* The above copyright notice and this permission notice (including the next
12
* paragraph) shall be included in all copies or substantial portions of the
15
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
32
#include "util/bitset.h"
33
#include "util/compiler.h"
34
#include "util/half_float.h"
35
#include "util/hash_table.h"
36
#include "util/ralloc.h"
37
#include "util/u_debug.h"
38
#include "util/u_math.h"
44
* The set of leaf node bitsets in the bitset hiearchy which defines all
45
* the possible instructions.
47
* TODO maybe we want to pass this in as parameter so this same decoder
48
* can work with multiple different instruction sets.
50
extern const struct isa_bitset *__instruction[];
55
* Decode scope. When parsing a field that is itself a bitset, we push a
56
* new scope to the stack. A nested bitset is allowed to resolve fields
57
* from an enclosing scope (needed, for example, to decode src register
58
* bitsets, where half/fullness is determined by fields outset if bitset
59
* in the instruction containing the bitset.
61
* But the field being resolved could be a derived field, or different
62
* depending on an override at a higher level of the stack, requiring
63
* expression evaluation which could in turn reference variables which
64
* triggers a recursive field lookup. But those lookups should not start
65
* from the top of the stack, but instead the current stack level. This
66
* prevents a field from accidentally resolving to different values
67
* depending on the starting point of the lookup. (Not only causing
68
* confusion, but this is behavior we don't want to depend on if we
69
* wanted to optimize things by caching field lookup results.)
75
struct decode_scope *parent;
78
* Current bitset value being decoded
85
const struct isa_bitset *bitset;
88
* Field name remapping.
90
const struct isa_field_params *params;
93
* Pointer back to decode state, for convenience.
95
struct decode_state *state;
98
* Cache expression evaluation results. Expressions for overrides can
99
* be repeatedly evaluated for each field being resolved. And each
100
* field reference to a derived field (potentially from another expr)
101
* would require re-evaluation. But for a given scope, each evaluation
102
* of an expression gives the same result. So we can cache to speed
105
* TODO we could maybe be clever and assign a unique idx to each expr
106
* and use a direct lookup table? Would be a bit more clever if it was
107
* smart enough to allow unrelated expressions that are never involved
108
* in a given scope to have overlapping cache lookup idx's.
110
struct hash_table *cache;
114
* Current decode state
116
struct decode_state {
117
const struct isa_decode_options *options;
121
* Current instruction being decoded:
126
* Number of instructions being decoded
131
* Column number of current line
133
unsigned line_column;
136
* Bitset of instructions that are branch targets (if options->branch_labels
139
BITSET_WORD *branch_targets;
142
* We allow a limited amount of expression evaluation recursion, but
143
* not recursive evaluation of any given expression, to prevent infinite
147
isa_expr_t expr_stack[8];
150
* Current topmost/innermost level of scope used for decoding fields,
151
* including derived fields which may in turn rely on decoding other
152
* fields, potentially from a lower/out level in the stack.
154
struct decode_scope *scope;
157
* A small fixed upper limit on # of decode errors to capture per-
158
* instruction seems reasonable.
165
print(struct decode_state *state, const char *fmt, ...)
172
ret = vasprintf(&buffer, fmt, args);
176
const size_t len = strlen(buffer);
178
for (size_t i = 0; i < len; i++) {
179
const char c = buffer[i];
181
fputc(c, state->out);
182
state->line_column++;
185
state->line_column = 0;
195
static void display(struct decode_scope *scope);
196
static void decode_error(struct decode_state *state, const char *fmt, ...) _util_printf_format(2,3);
199
decode_error(struct decode_state *state, const char *fmt, ...)
201
if (!state->options->show_errors) {
205
if (state->num_errors == ARRAY_SIZE(state->errors)) {
206
/* too many errors, bail */
212
vasprintf(&state->errors[state->num_errors++], fmt, ap);
217
flush_errors(struct decode_state *state)
219
unsigned num_errors = state->num_errors;
221
print(state, "\t; ");
222
for (unsigned i = 0; i < num_errors; i++) {
223
print(state, "%s%s", (i > 0) ? ", " : "", state->errors[i]);
224
free(state->errors[i]);
226
state->num_errors = 0;
232
push_expr(struct decode_state *state, isa_expr_t expr)
234
for (int i = state->expr_sp - 1; i > 0; i--) {
235
if (state->expr_stack[i] == expr) {
239
state->expr_stack[state->expr_sp++] = expr;
244
pop_expr(struct decode_state *state)
246
assert(state->expr_sp > 0);
250
static struct decode_scope *
251
push_scope(struct decode_state *state, const struct isa_bitset *bitset, bitmask_t val)
253
struct decode_scope *scope = rzalloc_size(state, sizeof(*scope));
255
BITSET_COPY(scope->val.bitset, val.bitset);
256
scope->bitset = bitset;
257
scope->parent = state->scope;
258
scope->state = state;
260
state->scope = scope;
266
pop_scope(struct decode_scope *scope)
268
assert(scope->state->scope == scope); /* must be top of stack */
270
scope->state->scope = scope->parent;
275
* Evaluate an expression, returning it's resulting value
278
evaluate_expr(struct decode_scope *scope, isa_expr_t expr)
281
struct hash_entry *entry = _mesa_hash_table_search(scope->cache, expr);
283
return *(uint64_t *)entry->data;
286
scope->cache = _mesa_pointer_hash_table_create(scope);
289
if (!push_expr(scope->state, expr))
292
uint64_t ret = expr(scope);
294
pop_expr(scope->state);
296
uint64_t *retp = ralloc_size(scope->cache, sizeof(*retp));
298
_mesa_hash_table_insert(scope->cache, expr, retp);
304
* Find the bitset in NULL terminated bitset hiearchy root table which
305
* matches against 'val'
307
static const struct isa_bitset *
308
find_bitset(struct decode_state *state, const struct isa_bitset **bitsets,
311
const struct isa_bitset *match = NULL;
312
for (int n = 0; bitsets[n]; n++) {
313
if (state->options->gpu_id > bitsets[n]->gen.max)
315
if (state->options->gpu_id < bitsets[n]->gen.min)
318
// m = (val & bitsets[n]->mask) & ~bitsets[n]->dontcare;
320
bitmask_t not_dontcare;
322
BITSET_AND(m.bitset, val.bitset, bitsets[n]->mask.bitset);
324
BITSET_COPY(not_dontcare.bitset, bitsets[n]->dontcare.bitset);
325
BITSET_NOT(not_dontcare.bitset);
327
BITSET_AND(m.bitset, m.bitset, not_dontcare.bitset);
329
if (!BITSET_EQUAL(m.bitset, bitsets[n]->match.bitset)) {
333
/* We should only have exactly one match
335
* TODO more complete/formal way to validate that any given
336
* bit pattern will only have a single match?
339
decode_error(state, "bitset conflict: %s vs %s", match->name,
349
BITSET_AND(m.bitset, match->dontcare.bitset, val.bitset);
351
if (BITSET_COUNT(m.bitset)) {
352
decode_error(state, "dontcare bits in %s: %"BITSET_FORMAT,
353
match->name, BITSET_VALUE(m.bitset));
360
static const struct isa_field *
361
find_field(struct decode_scope *scope, const struct isa_bitset *bitset,
362
const char *name, size_t name_len)
364
for (unsigned i = 0; i < bitset->num_cases; i++) {
365
const struct isa_case *c = bitset->cases[i];
368
struct decode_state *state = scope->state;
370
/* When resolving a field for evaluating an expression,
371
* temporarily assume the expression evaluates to true.
372
* This allows <override/>'s to speculatively refer to
373
* fields defined within the override:
375
isa_expr_t cur_expr = NULL;
376
if (state->expr_sp > 0)
377
cur_expr = state->expr_stack[state->expr_sp - 1];
378
if ((cur_expr != c->expr) && !evaluate_expr(scope, c->expr))
382
for (unsigned i = 0; i < c->num_fields; i++) {
383
if (!strncmp(name, c->fields[i].name, name_len) &&
384
(c->fields[i].name[name_len] == '\0')) {
385
return &c->fields[i];
390
if (bitset->parent) {
391
const struct isa_field *f = find_field(scope, bitset->parent, name, name_len);
401
extract_field(struct decode_scope *scope, const struct isa_field *field)
405
BITSET_COPY(val.bitset, scope->val.bitset);
406
BITSET_ZERO(mask.bitset);
408
BITSET_SET_RANGE(mask.bitset, field->low, field->high);
409
BITSET_AND(val.bitset, val.bitset, mask.bitset);
410
BITSET_SHR(val.bitset, field->low);
416
* Find the display template for a given bitset, recursively searching
417
* parents in the bitset hierarchy.
420
find_display(struct decode_scope *scope, const struct isa_bitset *bitset)
422
for (unsigned i = 0; i < bitset->num_cases; i++) {
423
const struct isa_case *c = bitset->cases[i];
424
if (c->expr && !evaluate_expr(scope, c->expr))
426
/* since this is the chosen case, it seems like a good place
427
* to check asserted bits:
429
for (unsigned j = 0; j < c->num_fields; j++) {
430
if (c->fields[j].type == TYPE_ASSERT) {
431
const struct isa_field *f = &c->fields[j];
434
val = extract_field(scope, f);
435
if (!BITSET_EQUAL(val.bitset, f->val.bitset)) {
436
decode_error(scope->state, "WARNING: unexpected "
437
"bits[%u:%u] in %s: %"BITSET_FORMAT" vs %"BITSET_FORMAT,
438
f->low, f->high, bitset->name,
439
BITSET_VALUE(val.bitset), BITSET_VALUE(f->val.bitset));
449
* If we didn't find something check up the bitset hierarchy.
451
if (bitset->parent) {
452
return find_display(scope, bitset->parent);
459
* Decode a field that is itself another bitset type
462
display_bitset_field(struct decode_scope *scope, const struct isa_field *field, bitmask_t val)
464
const struct isa_bitset *b = find_bitset(scope->state, field->bitsets, val);
466
decode_error(scope->state, "no match: FIELD: '%s.%s': %"BITSET_FORMAT,
467
scope->bitset->name, field->name, BITSET_VALUE(val.bitset));
471
struct decode_scope *nested_scope =
472
push_scope(scope->state, b, val);
473
nested_scope->params = field->params;
474
display(nested_scope);
475
pop_scope(nested_scope);
479
display_enum_field(struct decode_scope *scope, const struct isa_field *field, bitmask_t val)
481
const struct isa_enum *e = field->enums;
482
const uint64_t ui = bitmask_to_uint64_t(val);
484
for (unsigned i = 0; i < e->num_values; i++) {
485
if (e->values[i].val == ui) {
486
print(scope->state, "%s", e->values[i].display);
491
print(scope->state, "%u", (unsigned)ui);
494
static const struct isa_field *
495
resolve_field(struct decode_scope *scope, const char *field_name, size_t field_name_len, bitmask_t *valp)
498
/* We've reached the bottom of the stack! */
502
const struct isa_field *field =
503
find_field(scope, scope->bitset, field_name, field_name_len);
505
if (!field && scope->params) {
506
for (unsigned i = 0; i < scope->params->num_params; i++) {
507
if (!strncmp(field_name, scope->params->params[i].as, field_name_len) &&
508
(scope->params->params[i].as[field_name_len] == '\0')) {
509
const char *param_name = scope->params->params[i].name;
510
return resolve_field(scope->parent, param_name, strlen(param_name), valp);
519
/* extract out raw field value: */
521
uint64_t val = evaluate_expr(scope, field->expr);
523
*valp = uint64_t_to_bitmask(val);
525
*valp = extract_field(scope, field);
531
/* This is also used from generated expr functions */
533
isa_decode_field(struct decode_scope *scope, const char *field_name)
536
const struct isa_field *field = resolve_field(scope, field_name, strlen(field_name), &val);
538
decode_error(scope->state, "no field '%s'", field_name);
542
return bitmask_to_uint64_t(val);
546
display_field(struct decode_scope *scope, const char *field_name)
548
const struct isa_decode_options *options = scope->state->options;
549
struct decode_state *state = scope->state;
550
size_t field_name_len = strlen(field_name);
553
/* alignment handling */
554
const char *align = strstr(field_name, ":align=");
557
const char *value = strstr(align, "=") + 1;
559
field_name_len = align - field_name;
560
num_align = atoi(value);
563
/* Special case ':algin=' should only do alignment */
564
if (field_name == align) {
565
while (scope->state->line_column < num_align)
571
/* Special case 'NAME' maps to instruction/bitset name: */
572
if (!strncmp("NAME", field_name, field_name_len)) {
573
if (options->field_cb) {
574
options->field_cb(options->cbdata, field_name, &(struct isa_decode_value){
575
.str = scope->bitset->name,
579
while (scope->state->line_column < num_align)
582
print(scope->state, "%s", scope->bitset->name);
588
const struct isa_field *field = resolve_field(scope, field_name, field_name_len, &v);
590
decode_error(scope->state, "no field '%.*s'", (int)field_name_len, field_name);
594
uint64_t val = bitmask_to_uint64_t(v);
596
if (options->field_cb) {
597
options->field_cb(options->cbdata, field_name, &(struct isa_decode_value){
602
unsigned width = 1 + field->high - field->low;
604
while (scope->state->line_column < num_align)
607
switch (field->type) {
610
if (scope->state->options->branch_labels) {
611
int offset = util_sign_extend(val, width) + scope->state->n;
612
if (offset < scope->state->num_instr) {
613
print(scope->state, "l%d", offset);
614
BITSET_SET(scope->state->branch_targets, offset);
620
print(scope->state, "%"PRId64, util_sign_extend(val, width));
623
print(scope->state, "%"PRIu64, val);
626
// TODO format # of digits based on field width?
627
print(scope->state, "%"PRIx64, val);
631
print(scope->state, "%+"PRId64, util_sign_extend(val, width));
636
print(scope->state, "+%"PRIu64, val);
641
print(scope->state, "%f", _mesa_half_to_float(val));
644
print(scope->state, "%f", uif(val));
648
if (field->display) {
650
print(scope->state, "%s", field->display);
653
print(scope->state, "%u", (unsigned)val);
657
display_enum_field(scope, field, v);
661
/* assert fields are not for display */
665
/* For fields that are decoded with another bitset hierarchy: */
667
display_bitset_field(scope, field, v);
670
decode_error(scope->state, "Bad field type: %d (%s)",
671
field->type, field->name);
676
display(struct decode_scope *scope)
678
const struct isa_bitset *bitset = scope->bitset;
679
const char *display = find_display(scope, bitset);
682
decode_error(scope->state, "%s: no display template", bitset->name);
686
const char *p = display;
695
char *field_name = strndup(p, e-p);
696
display_field(scope, field_name);
701
fputc(*p, scope->state->out);
702
scope->state->line_column++;
709
decode(struct decode_state *state, void *bin, int sz)
711
BITSET_WORD *instrs = bin;
712
unsigned errors = 0; /* number of consecutive unmatched instructions */
714
assert(sz % BITMASK_WORDS == 0);
716
for (state->n = 0; state->n < state->num_instr; state->n++) {
717
bitmask_t instr = { 0 };
719
next_instruction(&instr, &instrs[state->n * BITMASK_WORDS]);
720
state->line_column = 0;
722
if (state->options->max_errors && (errors > state->options->max_errors)) {
726
if (state->options->branch_labels &&
727
BITSET_TEST(state->branch_targets, state->n)) {
728
if (state->options->instr_cb) {
729
state->options->instr_cb(state->options->cbdata,
730
state->n, instr.bitset);
732
print(state, "l%d:\n", state->n);
735
if (state->options->instr_cb) {
736
state->options->instr_cb(state->options->cbdata, state->n, instr.bitset);
739
const struct isa_bitset *b = find_bitset(state, __instruction, instr);
741
print(state, "no match: %"BITSET_FORMAT"\n", BITSET_VALUE(instr.bitset));
746
struct decode_scope *scope = push_scope(state, b, instr);
749
if (flush_errors(state)) {
758
if (state->options->stop) {
765
isa_decode(void *bin, int sz, FILE *out, const struct isa_decode_options *options)
767
const struct isa_decode_options default_options = {
768
.gpu_id = options ? options->gpu_id : 0,
769
.branch_labels = options ? options->branch_labels : false
771
struct decode_state *state;
774
options = &default_options;
776
util_cpu_detect(); /* needed for _mesa_half_to_float() */
778
state = rzalloc_size(NULL, sizeof(*state));
779
state->options = options;
780
state->num_instr = sz / (BITMASK_WORDS * sizeof(BITSET_WORD));
782
if (state->options->branch_labels) {
783
state->branch_targets = rzalloc_size(state,
784
sizeof(BITSET_WORD) * BITSET_WORDS(state->num_instr));
786
/* Do a pre-pass to find all the branch targets: */
787
state->out = fopen("/dev/null", "w");
788
state->options = &default_options; /* skip hooks for prepass */
789
decode(state, bin, sz);
792
state->options = options;
798
decode(state, bin, sz);