decode.c 18.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 * Copyright © 2020 Google, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <assert.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "util/bitset.h"
#include "util/compiler.h"
#include "util/half_float.h"
35
#include "util/hash_table.h"
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "util/ralloc.h"
#include "util/u_debug.h"
#include "util/u_math.h"

#include "decode.h"
#include "isa.h"

/**
 * The set of leaf node bitsets in the bitset hiearchy which defines all
 * the possible instructions.
 *
 * TODO maybe we want to pass this in as parameter so this same decoder
 * can work with multiple different instruction sets.
 */
extern const struct isa_bitset *__instruction[];

struct decode_state;

/**
 * Decode scope.  When parsing a field that is itself a bitset, we push a
 * new scope to the stack.  A nested bitset is allowed to resolve fields
 * from an enclosing scope (needed, for example, to decode src register
 * bitsets, where half/fullness is determined by fields outset if bitset
 * in the instruction containing the bitset.
 *
 * But the field being resolved could be a derived field, or different
 * depending on an override at a higher level of the stack, requiring
 * expression evaluation which could in turn reference variables which
 * triggers a recursive field lookup.  But those lookups should not start
 * from the top of the stack, but instead the current stack level.  This
 * prevents a field from accidentally resolving to different values
 * depending on the starting point of the lookup.  (Not only causing
 * confusion, but this is behavior we don't want to depend on if we
 * wanted to optimize things by caching field lookup results.)
 */
struct decode_scope {
	/**
	 * Enclosing scope
	 */
	struct decode_scope *parent;

	/**
	 * Current bitset value being decoded
	 */
80
	bitmask_t val;
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

	/**
	 * Current bitset.
	 */
	const struct isa_bitset *bitset;

	/**
	 * Field name remapping.
	 */
	const struct isa_field_params *params;

	/**
	 * Pointer back to decode state, for convenience.
	 */
	struct decode_state *state;
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

	/**
	 * Cache expression evaluation results.  Expressions for overrides can
	 * be repeatedly evaluated for each field being resolved.  And each
	 * field reference to a derived field (potentially from another expr)
	 * would require re-evaluation.  But for a given scope, each evaluation
	 * of an expression gives the same result.  So we can cache to speed
	 * things up.
	 *
	 * TODO we could maybe be clever and assign a unique idx to each expr
	 * and use a direct lookup table?  Would be a bit more clever if it was
	 * smart enough to allow unrelated expressions that are never involved
	 * in a given scope to have overlapping cache lookup idx's.
	 */
	struct hash_table *cache;
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
};

/**
 * Current decode state
 */
struct decode_state {
	const struct isa_decode_options *options;
	FILE *out;

	/**
	 * Current instruction being decoded:
	 */
	unsigned n;

	/**
	 * Number of instructions being decoded
	 */
	unsigned num_instr;

130
131
132
133
134
	/**
	 * Column number of current line
	 */
	unsigned line_column;

135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
	/**
	 * Bitset of instructions that are branch targets (if options->branch_labels
	 * is enabled)
	 */
	BITSET_WORD *branch_targets;

	/**
	 * We allow a limited amount of expression evaluation recursion, but
	 * not recursive evaluation of any given expression, to prevent infinite
	 * recursion.
	 */
	int expr_sp;
	isa_expr_t expr_stack[8];

	/**
	 * Current topmost/innermost level of scope used for decoding fields,
	 * including derived fields which may in turn rely on decoding other
	 * fields, potentially from a lower/out level in the stack.
	 */
	struct decode_scope *scope;

	/**
	 * A small fixed upper limit on # of decode errors to capture per-
	 * instruction seems reasonable.
	 */
	unsigned num_errors;
	char *errors[4];
};

164
165
166
167
168
169
static void
print(struct decode_state *state, const char *fmt, ...)
{
	va_list args;

	va_start(args, fmt);
170
	state->line_column += vfprintf(state->out, fmt, args);
171
172
173
	va_end(args);
}

174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
static void display(struct decode_scope *scope);
static void decode_error(struct decode_state *state, const char *fmt, ...) _util_printf_format(2,3);

static void
decode_error(struct decode_state *state, const char *fmt, ...)
{
	if (!state->options->show_errors) {
		return;
	}

	if (state->num_errors == ARRAY_SIZE(state->errors)) {
		/* too many errors, bail */
		return;
	}

	va_list ap;
	va_start(ap, fmt);
	vasprintf(&state->errors[state->num_errors++], fmt, ap);
	va_end(ap);
}

static unsigned
flush_errors(struct decode_state *state)
{
	unsigned num_errors = state->num_errors;
	if (num_errors > 0)
200
		print(state, "\t; ");
201
	for (unsigned i = 0; i < num_errors; i++) {
202
		print(state, "%s%s", (i > 0) ? ", " : "", state->errors[i]);
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
		free(state->errors[i]);
	}
	state->num_errors = 0;
	return num_errors;
}


static bool
push_expr(struct decode_state *state, isa_expr_t expr)
{
	for (int i = state->expr_sp - 1; i > 0; i--) {
		if (state->expr_stack[i] == expr) {
			return false;
		}
	}
	state->expr_stack[state->expr_sp++] = expr;
	return true;
}

static void
pop_expr(struct decode_state *state)
{
	assert(state->expr_sp > 0);
	state->expr_sp--;
}

static struct decode_scope *
230
push_scope(struct decode_state *state, const struct isa_bitset *bitset, bitmask_t val)
231
232
233
{
	struct decode_scope *scope = rzalloc_size(state, sizeof(*scope));

234
	BITSET_COPY(scope->val.bitset, val.bitset);
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
	scope->bitset = bitset;
	scope->parent = state->scope;
	scope->state  = state;

	state->scope = scope;

	return scope;
}

static void
pop_scope(struct decode_scope *scope)
{
	assert(scope->state->scope == scope);  /* must be top of stack */

	scope->state->scope = scope->parent;
	ralloc_free(scope);
}

/**
 * Evaluate an expression, returning it's resulting value
 */
static uint64_t
evaluate_expr(struct decode_scope *scope, isa_expr_t expr)
{
259
260
261
262
263
264
265
266
267
	if (scope->cache) {
		struct hash_entry *entry = _mesa_hash_table_search(scope->cache, expr);
		if (entry) {
			return *(uint64_t *)entry->data;
		}
	} else {
		scope->cache = _mesa_pointer_hash_table_create(scope);
	}

268
269
270
271
272
273
274
	if (!push_expr(scope->state, expr))
		return 0;

	uint64_t ret = expr(scope);

	pop_expr(scope->state);

275
276
277
278
	uint64_t *retp = ralloc_size(scope->cache, sizeof(*retp));
	*retp = ret;
	_mesa_hash_table_insert(scope->cache, expr, retp);

279
280
281
282
283
284
285
286
287
	return ret;
}

/**
 * Find the bitset in NULL terminated bitset hiearchy root table which
 * matches against 'val'
 */
static const struct isa_bitset *
find_bitset(struct decode_state *state, const struct isa_bitset **bitsets,
288
		bitmask_t val)
289
290
291
292
293
294
295
296
{
	const struct isa_bitset *match = NULL;
	for (int n = 0; bitsets[n]; n++) {
		if (state->options->gpu_id > bitsets[n]->gen.max)
			continue;
		if (state->options->gpu_id < bitsets[n]->gen.min)
			continue;

297
298
299
300
301
302
303
304
		// m = (val & bitsets[n]->mask) & ~bitsets[n]->dontcare;
		bitmask_t m = { 0 };
		bitmask_t not_dontcare;

		BITSET_AND(m.bitset, val.bitset, bitsets[n]->mask.bitset);

		BITSET_COPY(not_dontcare.bitset, bitsets[n]->dontcare.bitset);
		BITSET_NOT(not_dontcare.bitset);
305

306
307
308
		BITSET_AND(m.bitset, m.bitset, not_dontcare.bitset);

		if (!BITSET_EQUAL(m.bitset, bitsets[n]->match.bitset)) {
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
			continue;
		}

		/* We should only have exactly one match
		 *
		 * TODO more complete/formal way to validate that any given
		 * bit pattern will only have a single match?
		 */
		if (match) {
			decode_error(state, "bitset conflict: %s vs %s", match->name,
					bitsets[n]->name);
			return NULL;
		}

		match = bitsets[n];
	}

326
327
328
329
330
331
332
333
	if (match) {
		bitmask_t m = { 0 };
		BITSET_AND(m.bitset, match->dontcare.bitset, val.bitset);

		if (BITSET_COUNT(m.bitset)) {
			decode_error(state, "dontcare bits in %s: %"BITSET_FORMAT,
					match->name, BITSET_VALUE(m.bitset));
		}
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
	}

	return match;
}

static const struct isa_field *
find_field(struct decode_scope *scope, const struct isa_bitset *bitset,
		const char *name)
{
	for (unsigned i = 0; i < bitset->num_cases; i++) {
		const struct isa_case *c = bitset->cases[i];

		if (c->expr) {
			struct decode_state *state = scope->state;

			/* When resolving a field for evaluating an expression,
			 * temporarily assume the expression evaluates to true.
			 * This allows <override/>'s to speculatively refer to
			 * fields defined within the override:
			 */
			isa_expr_t cur_expr = NULL;
			if (state->expr_sp > 0)
				cur_expr = state->expr_stack[state->expr_sp - 1];
			if ((cur_expr != c->expr) && !evaluate_expr(scope, c->expr))
				continue;
		}

		for (unsigned i = 0; i < c->num_fields; i++) {
			if (!strcmp(name, c->fields[i].name)) {
				return &c->fields[i];
			}
		}
	}

	if (bitset->parent) {
		const struct isa_field *f = find_field(scope, bitset->parent, name);
		if (f) {
			return f;
		}
	}

	return NULL;
}

378
static bitmask_t
379
380
extract_field(struct decode_scope *scope, const struct isa_field *field)
{
381
382
383
384
385
386
387
388
389
390
   bitmask_t val, mask;

   BITSET_COPY(val.bitset, scope->val.bitset);
   BITSET_ZERO(mask.bitset);

   BITSET_SET_RANGE(mask.bitset, field->low, field->high);
   BITSET_AND(val.bitset, val.bitset, mask.bitset);
   BITSET_SHR(val.bitset, field->low);

   return val;
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
}

/**
 * Find the display template for a given bitset, recursively searching
 * parents in the bitset hierarchy.
 */
static const char *
find_display(struct decode_scope *scope, const struct isa_bitset *bitset)
{
	for (unsigned i = 0; i < bitset->num_cases; i++) {
		const struct isa_case *c = bitset->cases[i];
		if (c->expr && !evaluate_expr(scope, c->expr))
			continue;
		/* since this is the chosen case, it seems like a good place
		 * to check asserted bits:
		 */
		for (unsigned j = 0; j < c->num_fields; j++) {
			if (c->fields[j].type == TYPE_ASSERT) {
				const struct isa_field *f = &c->fields[j];
410
411
412
413
				bitmask_t val;

				val = extract_field(scope, f);
				if (!BITSET_EQUAL(val.bitset, f->val.bitset)) {
414
					decode_error(scope->state, "WARNING: unexpected "
415
							"bits[%u:%u] in %s: %"BITSET_FORMAT" vs %"BITSET_FORMAT,
416
							f->low, f->high, bitset->name,
417
							BITSET_VALUE(val.bitset), BITSET_VALUE(f->val.bitset));
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
				}
			}
		}
		if (!c->display)
			continue;
		return c->display;
	}

	/**
	 * If we didn't find something check up the bitset hierarchy.
	 */
	if (bitset->parent) {
		return find_display(scope, bitset->parent);
	}

	return NULL;
}

/**
 * Decode a field that is itself another bitset type
 */
static void
440
display_bitset_field(struct decode_scope *scope, const struct isa_field *field, bitmask_t val)
441
442
443
{
	const struct isa_bitset *b = find_bitset(scope->state, field->bitsets, val);
	if (!b) {
444
		decode_error(scope->state, "no match: FIELD: '%s.%s': %"BITSET_FORMAT,
445
				scope->bitset->name, field->name, BITSET_VALUE(val.bitset));
446
447
448
449
450
451
452
453
454
455
456
		return;
	}

	struct decode_scope *nested_scope =
			push_scope(scope->state, b, val);
	nested_scope->params = field->params;
	display(nested_scope);
	pop_scope(nested_scope);
}

static void
457
display_enum_field(struct decode_scope *scope, const struct isa_field *field, bitmask_t val)
458
459
{
	const struct isa_enum *e = field->enums;
460
461
	const uint64_t ui = bitmask_to_uint64_t(val);

462
	for (unsigned i = 0; i < e->num_values; i++) {
463
		if (e->values[i].val == ui) {
464
			print(scope->state, "%s", e->values[i].display);
465
466
467
468
			return;
		}
	}

469
	print(scope->state, "%u", (unsigned)ui);
470
471
472
}

static const struct isa_field *
473
resolve_field(struct decode_scope *scope, const char *field_name, bitmask_t *valp)
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
{
	if (!scope) {
		/* We've reached the bottom of the stack! */
		return NULL;
	}

	const struct isa_field *field =
			find_field(scope, scope->bitset, field_name);

	if (!field && scope->params) {
		for (unsigned i = 0; i < scope->params->num_params; i++) {
			if (!strcmp(field_name, scope->params->params[i].as)) {
				const char *param_name = scope->params->params[i].name;
				return resolve_field(scope->parent, param_name, valp);
			}
		}
	}

	if (!field) {
		return NULL;
	}

	/* extract out raw field value: */
	if (field->expr) {
498
499
500
		uint64_t val = evaluate_expr(scope, field->expr);

		*valp = uint64_t_to_bitmask(val);
501
502
503
504
505
506
507
508
509
510
511
	} else {
		*valp = extract_field(scope, field);
	}

	return field;
}

/* This is also used from generated expr functions */
uint64_t
isa_decode_field(struct decode_scope *scope, const char *field_name)
{
512
	bitmask_t val;
513
514
515
516
517
518
	const struct isa_field *field = resolve_field(scope, field_name, &val);
	if (!field) {
		decode_error(scope->state, "no field '%s'", field_name);
		return 0;
	}

519
	return bitmask_to_uint64_t(val);
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
}

static void
display_field(struct decode_scope *scope, const char *field_name)
{
	const struct isa_decode_options *options = scope->state->options;

	/* Special case 'NAME' maps to instruction/bitset name: */
	if (!strcmp("NAME", field_name)) {
		if (options->field_cb) {
			options->field_cb(options->cbdata, field_name, &(struct isa_decode_value){
				.str = scope->bitset->name,
			});
		}

535
		print(scope->state, "%s", scope->bitset->name);
536
537
538
539

		return;
	}

540
541
	bitmask_t v;
	const struct isa_field *field = resolve_field(scope, field_name, &v);
542
543
544
545
546
	if (!field) {
		decode_error(scope->state, "no field '%s'", field_name);
		return;
	}

547
548
	uint64_t val = bitmask_to_uint64_t(v);

549
550
551
552
553
554
555
556
557
558
559
560
	if (options->field_cb) {
		options->field_cb(options->cbdata, field_name, &(struct isa_decode_value){
			.num = val,
		});
	}

	unsigned width = 1 + field->high - field->low;

	switch (field->type) {
	/* Basic types: */
	case TYPE_BRANCH:
		if (scope->state->options->branch_labels) {
Italo Nicola's avatar
Italo Nicola committed
561
			int offset = util_sign_extend(val, width) + scope->state->n;
562
			if (offset < scope->state->num_instr) {
563
				print(scope->state, "l%d", offset);
564
565
566
567
568
569
				BITSET_SET(scope->state->branch_targets, offset);
				break;
			}
		}
		FALLTHROUGH;
	case TYPE_INT:
570
		print(scope->state, "%"PRId64, util_sign_extend(val, width));
571
572
		break;
	case TYPE_UINT:
573
		print(scope->state, "%"PRIu64, val);
574
575
576
		break;
	case TYPE_HEX:
		// TODO format # of digits based on field width?
577
		print(scope->state, "%"PRIx64, val);
578
579
580
		break;
	case TYPE_OFFSET:
		if (val != 0) {
581
			print(scope->state, "%+"PRId64, util_sign_extend(val, width));
582
583
		}
		break;
584
585
	case TYPE_UOFFSET:
		if (val != 0) {
586
			print(scope->state, "+%"PRIu64, val);
587
588
		}
		break;
589
590
	case TYPE_FLOAT:
		if (width == 16) {
591
			print(scope->state, "%f", _mesa_half_to_float(val));
592
593
		} else {
			assert(width == 32);
594
			print(scope->state, "%f", uif(val));
595
596
597
598
599
		}
		break;
	case TYPE_BOOL:
		if (field->display) {
			if (val) {
600
				print(scope->state, "%s", field->display);
601
602
			}
		} else {
603
			print(scope->state, "%u", (unsigned)val);
604
605
606
		}
		break;
	case TYPE_ENUM:
607
		display_enum_field(scope, field, v);
608
609
610
611
612
613
614
615
616
		break;

	case TYPE_ASSERT:
		/* assert fields are not for display */
		assert(0);
		break;

	/* For fields that are decoded with another bitset hierarchy: */
	case TYPE_BITSET:
617
		display_bitset_field(scope, field, v);
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
		break;
	default:
		decode_error(scope->state, "Bad field type: %d (%s)",
				field->type, field->name);
	}
}

static void
display(struct decode_scope *scope)
{
	const struct isa_bitset *bitset = scope->bitset;
	const char *display = find_display(scope, bitset);

	if (!display) {
		decode_error(scope->state, "%s: no display template", bitset->name);
		return;
	}

	const char *p = display;

	while (*p != '\0') {
		if (*p == '{') {
			const char *e = ++p;
			while (*e != '}') {
				e++;
			}

			char *field_name = strndup(p, e-p);
			display_field(scope, field_name);
			free(field_name);

			p = e;
		} else {
			fputc(*p, scope->state->out);
652
			scope->state->line_column++;
653
654
655
656
657
658
659
660
		}
		p++;
	}
}

static void
decode(struct decode_state *state, void *bin, int sz)
{
661
	BITSET_WORD *instrs = bin;
662
663
	unsigned errors = 0;   /* number of consecutive unmatched instructions */

664
665
	assert(sz % BITMASK_WORDS == 0);

666
	for (state->n = 0; state->n < state->num_instr; state->n++) {
667
668
		bitmask_t instr = { 0 };

669
		next_instruction(&instr, &instrs[state->n * BITMASK_WORDS]);
670
      state->line_column = 0;
671
672
673
674
675
676
677
678
679

		if (state->options->max_errors && (errors > state->options->max_errors)) {
			break;
		}

		if (state->options->branch_labels &&
				BITSET_TEST(state->branch_targets, state->n)) {
			if (state->options->instr_cb) {
				state->options->instr_cb(state->options->cbdata,
680
						state->n, instr.bitset);
681
			}
682
			print(state, "l%d:\n", state->n);
683
684
685
		}

		if (state->options->instr_cb) {
686
			state->options->instr_cb(state->options->cbdata, state->n, instr.bitset);
687
688
689
690
		}

		const struct isa_bitset *b = find_bitset(state, __instruction, instr);
		if (!b) {
691
			print(state, "no match: %"BITSET_FORMAT"\n", BITSET_VALUE(instr.bitset));
692
693
694
695
696
697
698
699
700
701
702
703
			errors++;
			continue;
		}

		struct decode_scope *scope = push_scope(state, b, instr);

		display(scope);
		if (flush_errors(state)) {
			errors++;
		} else {
			errors = 0;
		}
704
		print(state, "\n");
705
706
707
708
709
710
711
712
713
714
715
716

		pop_scope(scope);

		if (state->options->stop) {
			break;
		}
	}
}

void
isa_decode(void *bin, int sz, FILE *out, const struct isa_decode_options *options)
{
717
718
719
	const struct isa_decode_options default_options = {
		.branch_labels = options ? options->branch_labels : false
	};
720
721
722
723
724
	struct decode_state *state;

	if (!options)
		options = &default_options;

725
726
	util_cpu_detect();  /* needed for _mesa_half_to_float() */

727
728
	state = rzalloc_size(NULL, sizeof(*state));
	state->options = options;
729
	state->num_instr = sz / (BITMASK_WORDS * sizeof(BITSET_WORD));
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750

	if (state->options->branch_labels) {
		state->branch_targets = rzalloc_size(state,
				sizeof(BITSET_WORD) * BITSET_WORDS(state->num_instr));

		/* Do a pre-pass to find all the branch targets: */
		state->out = fopen("/dev/null", "w");
		state->options = &default_options;   /* skip hooks for prepass */
		decode(state, bin, sz);
		fclose(state->out);
		if (options) {
			state->options = options;
		}
	}

	state->out = out;

	decode(state, bin, sz);

	ralloc_free(state);
}