1/* 2 * Copyright © 2020 Google, Inc. 3 * 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: 10 * 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 13 * Software. 14 * 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 21 * SOFTWARE. 22 */ 23 24#include <assert.h> 25#include <inttypes.h> 26#include <stdbool.h> 27#include <stdint.h> 28#include <stdio.h> 29#include <stdlib.h> 30#include <string.h> 31 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" 39 40#include "decode.h" 41#include "isa.h" 42 43/** 44 * The set of leaf node bitsets in the bitset hiearchy which defines all 45 * the possible instructions. 46 * 47 * TODO maybe we want to pass this in as parameter so this same decoder 48 * can work with multiple different instruction sets. 49 */ 50extern const struct isa_bitset *__instruction[]; 51 52struct decode_state; 53 54/** 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. 60 * 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.) 70 */ 71struct decode_scope { 72 /** 73 * Enclosing scope 74 */ 75 struct decode_scope *parent; 76 77 /** 78 * Current bitset value being decoded 79 */ 80 bitmask_t val; 81 82 /** 83 * Current bitset. 84 */ 85 const struct isa_bitset *bitset; 86 87 /** 88 * Field name remapping. 89 */ 90 const struct isa_field_params *params; 91 92 /** 93 * Pointer back to decode state, for convenience. 94 */ 95 struct decode_state *state; 96 97 /** 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 103 * things up. 104 * 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. 109 */ 110 struct hash_table *cache; 111}; 112 113/** 114 * Current decode state 115 */ 116struct decode_state { 117 const struct isa_decode_options *options; 118 FILE *out; 119 120 /** 121 * Current instruction being decoded: 122 */ 123 unsigned n; 124 125 /** 126 * Number of instructions being decoded 127 */ 128 unsigned num_instr; 129 130 /** 131 * Column number of current line 132 */ 133 unsigned line_column; 134 135 /** 136 * Bitset of instructions that are branch targets (if options->branch_labels 137 * is enabled) 138 */ 139 BITSET_WORD *branch_targets; 140 141 /** 142 * We allow a limited amount of expression evaluation recursion, but 143 * not recursive evaluation of any given expression, to prevent infinite 144 * recursion. 145 */ 146 int expr_sp; 147 isa_expr_t expr_stack[8]; 148 149 /** 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. 153 */ 154 struct decode_scope *scope; 155 156 /** 157 * A small fixed upper limit on # of decode errors to capture per- 158 * instruction seems reasonable. 159 */ 160 unsigned num_errors; 161 char *errors[4]; 162}; 163 164static void 165print(struct decode_state *state, const char *fmt, ...) 166{ 167 char *buffer; 168 va_list args; 169 int ret; 170 171 va_start(args, fmt); 172 ret = vasprintf(&buffer, fmt, args); 173 va_end(args); 174 175 if (ret != -1) { 176 const size_t len = strlen(buffer); 177 178 for (size_t i = 0; i < len; i++) { 179 const char c = buffer[i]; 180 181 fputc(c, state->out); 182 state->line_column++; 183 184 if (c == '\n') { 185 state->line_column = 0; 186 } 187 } 188 189 free(buffer); 190 191 return; 192 } 193} 194 195static void display(struct decode_scope *scope); 196static void decode_error(struct decode_state *state, const char *fmt, ...) _util_printf_format(2,3); 197 198static void 199decode_error(struct decode_state *state, const char *fmt, ...) 200{ 201 if (!state->options->show_errors) { 202 return; 203 } 204 205 if (state->num_errors == ARRAY_SIZE(state->errors)) { 206 /* too many errors, bail */ 207 return; 208 } 209 210 va_list ap; 211 va_start(ap, fmt); 212 vasprintf(&state->errors[state->num_errors++], fmt, ap); 213 va_end(ap); 214} 215 216static unsigned 217flush_errors(struct decode_state *state) 218{ 219 unsigned num_errors = state->num_errors; 220 if (num_errors > 0) 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]); 225 } 226 state->num_errors = 0; 227 return num_errors; 228} 229 230 231static bool 232push_expr(struct decode_state *state, isa_expr_t expr) 233{ 234 for (int i = state->expr_sp - 1; i > 0; i--) { 235 if (state->expr_stack[i] == expr) { 236 return false; 237 } 238 } 239 state->expr_stack[state->expr_sp++] = expr; 240 return true; 241} 242 243static void 244pop_expr(struct decode_state *state) 245{ 246 assert(state->expr_sp > 0); 247 state->expr_sp--; 248} 249 250static struct decode_scope * 251push_scope(struct decode_state *state, const struct isa_bitset *bitset, bitmask_t val) 252{ 253 struct decode_scope *scope = rzalloc_size(state, sizeof(*scope)); 254 255 BITSET_COPY(scope->val.bitset, val.bitset); 256 scope->bitset = bitset; 257 scope->parent = state->scope; 258 scope->state = state; 259 260 state->scope = scope; 261 262 return scope; 263} 264 265static void 266pop_scope(struct decode_scope *scope) 267{ 268 assert(scope->state->scope == scope); /* must be top of stack */ 269 270 scope->state->scope = scope->parent; 271 ralloc_free(scope); 272} 273 274/** 275 * Evaluate an expression, returning it's resulting value 276 */ 277static uint64_t 278evaluate_expr(struct decode_scope *scope, isa_expr_t expr) 279{ 280 if (scope->cache) { 281 struct hash_entry *entry = _mesa_hash_table_search(scope->cache, expr); 282 if (entry) { 283 return *(uint64_t *)entry->data; 284 } 285 } else { 286 scope->cache = _mesa_pointer_hash_table_create(scope); 287 } 288 289 if (!push_expr(scope->state, expr)) 290 return 0; 291 292 uint64_t ret = expr(scope); 293 294 pop_expr(scope->state); 295 296 uint64_t *retp = ralloc_size(scope->cache, sizeof(*retp)); 297 *retp = ret; 298 _mesa_hash_table_insert(scope->cache, expr, retp); 299 300 return ret; 301} 302 303/** 304 * Find the bitset in NULL terminated bitset hiearchy root table which 305 * matches against 'val' 306 */ 307static const struct isa_bitset * 308find_bitset(struct decode_state *state, const struct isa_bitset **bitsets, 309 bitmask_t val) 310{ 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) 314 continue; 315 if (state->options->gpu_id < bitsets[n]->gen.min) 316 continue; 317 318 // m = (val & bitsets[n]->mask) & ~bitsets[n]->dontcare; 319 bitmask_t m = { 0 }; 320 bitmask_t not_dontcare; 321 322 BITSET_AND(m.bitset, val.bitset, bitsets[n]->mask.bitset); 323 324 BITSET_COPY(not_dontcare.bitset, bitsets[n]->dontcare.bitset); 325 BITSET_NOT(not_dontcare.bitset); 326 327 BITSET_AND(m.bitset, m.bitset, not_dontcare.bitset); 328 329 if (!BITSET_EQUAL(m.bitset, bitsets[n]->match.bitset)) { 330 continue; 331 } 332 333 /* We should only have exactly one match 334 * 335 * TODO more complete/formal way to validate that any given 336 * bit pattern will only have a single match? 337 */ 338 if (match) { 339 decode_error(state, "bitset conflict: %s vs %s", match->name, 340 bitsets[n]->name); 341 return NULL; 342 } 343 344 match = bitsets[n]; 345 } 346 347 if (match) { 348 bitmask_t m = { 0 }; 349 BITSET_AND(m.bitset, match->dontcare.bitset, val.bitset); 350 351 if (BITSET_COUNT(m.bitset)) { 352 decode_error(state, "dontcare bits in %s: %"BITSET_FORMAT, 353 match->name, BITSET_VALUE(m.bitset)); 354 } 355 } 356 357 return match; 358} 359 360static const struct isa_field * 361find_field(struct decode_scope *scope, const struct isa_bitset *bitset, 362 const char *name, size_t name_len) 363{ 364 for (unsigned i = 0; i < bitset->num_cases; i++) { 365 const struct isa_case *c = bitset->cases[i]; 366 367 if (c->expr) { 368 struct decode_state *state = scope->state; 369 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: 374 */ 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)) 379 continue; 380 } 381 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]; 386 } 387 } 388 } 389 390 if (bitset->parent) { 391 const struct isa_field *f = find_field(scope, bitset->parent, name, name_len); 392 if (f) { 393 return f; 394 } 395 } 396 397 return NULL; 398} 399 400static bitmask_t 401extract_field(struct decode_scope *scope, const struct isa_field *field) 402{ 403 bitmask_t val, mask; 404 405 BITSET_COPY(val.bitset, scope->val.bitset); 406 BITSET_ZERO(mask.bitset); 407 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); 411 412 return val; 413} 414 415/** 416 * Find the display template for a given bitset, recursively searching 417 * parents in the bitset hierarchy. 418 */ 419static const char * 420find_display(struct decode_scope *scope, const struct isa_bitset *bitset) 421{ 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)) 425 continue; 426 /* since this is the chosen case, it seems like a good place 427 * to check asserted bits: 428 */ 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]; 432 bitmask_t val; 433 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)); 440 } 441 } 442 } 443 if (!c->display) 444 continue; 445 return c->display; 446 } 447 448 /** 449 * If we didn't find something check up the bitset hierarchy. 450 */ 451 if (bitset->parent) { 452 return find_display(scope, bitset->parent); 453 } 454 455 return NULL; 456} 457 458/** 459 * Decode a field that is itself another bitset type 460 */ 461static void 462display_bitset_field(struct decode_scope *scope, const struct isa_field *field, bitmask_t val) 463{ 464 const struct isa_bitset *b = find_bitset(scope->state, field->bitsets, val); 465 if (!b) { 466 decode_error(scope->state, "no match: FIELD: '%s.%s': %"BITSET_FORMAT, 467 scope->bitset->name, field->name, BITSET_VALUE(val.bitset)); 468 return; 469 } 470 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); 476} 477 478static void 479display_enum_field(struct decode_scope *scope, const struct isa_field *field, bitmask_t val) 480{ 481 const struct isa_enum *e = field->enums; 482 const uint64_t ui = bitmask_to_uint64_t(val); 483 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); 487 return; 488 } 489 } 490 491 print(scope->state, "%u", (unsigned)ui); 492} 493 494static const struct isa_field * 495resolve_field(struct decode_scope *scope, const char *field_name, size_t field_name_len, bitmask_t *valp) 496{ 497 if (!scope) { 498 /* We've reached the bottom of the stack! */ 499 return NULL; 500 } 501 502 const struct isa_field *field = 503 find_field(scope, scope->bitset, field_name, field_name_len); 504 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); 511 } 512 } 513 } 514 515 if (!field) { 516 return NULL; 517 } 518 519 /* extract out raw field value: */ 520 if (field->expr) { 521 uint64_t val = evaluate_expr(scope, field->expr); 522 523 *valp = uint64_t_to_bitmask(val); 524 } else { 525 *valp = extract_field(scope, field); 526 } 527 528 return field; 529} 530 531/* This is also used from generated expr functions */ 532uint64_t 533isa_decode_field(struct decode_scope *scope, const char *field_name) 534{ 535 bitmask_t val; 536 const struct isa_field *field = resolve_field(scope, field_name, strlen(field_name), &val); 537 if (!field) { 538 decode_error(scope->state, "no field '%s'", field_name); 539 return 0; 540 } 541 542 return bitmask_to_uint64_t(val); 543} 544 545static void 546display_field(struct decode_scope *scope, const char *field_name) 547{ 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); 551 int num_align = 0; 552 553 /* alignment handling */ 554 const char *align = strstr(field_name, ":align="); 555 556 if (align) { 557 const char *value = strstr(align, "=") + 1; 558 559 field_name_len = align - field_name; 560 num_align = atoi(value); 561 } 562 563 /* Special case ':algin=' should only do alignment */ 564 if (field_name == align) { 565 while (scope->state->line_column < num_align) 566 print(state, " "); 567 568 return; 569 } 570 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, 576 }); 577 } 578 579 while (scope->state->line_column < num_align) 580 print(state, " "); 581 582 print(scope->state, "%s", scope->bitset->name); 583 584 return; 585 } 586 587 bitmask_t v; 588 const struct isa_field *field = resolve_field(scope, field_name, field_name_len, &v); 589 if (!field) { 590 decode_error(scope->state, "no field '%.*s'", (int)field_name_len, field_name); 591 return; 592 } 593 594 uint64_t val = bitmask_to_uint64_t(v); 595 596 if (options->field_cb) { 597 options->field_cb(options->cbdata, field_name, &(struct isa_decode_value){ 598 .num = val, 599 }); 600 } 601 602 unsigned width = 1 + field->high - field->low; 603 604 while (scope->state->line_column < num_align) 605 print(state, " "); 606 607 switch (field->type) { 608 /* Basic types: */ 609 case TYPE_BRANCH: 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); 615 break; 616 } 617 } 618 FALLTHROUGH; 619 case TYPE_INT: 620 print(scope->state, "%"PRId64, util_sign_extend(val, width)); 621 break; 622 case TYPE_UINT: 623 print(scope->state, "%"PRIu64, val); 624 break; 625 case TYPE_HEX: 626 // TODO format # of digits based on field width? 627 print(scope->state, "%"PRIx64, val); 628 break; 629 case TYPE_OFFSET: 630 if (val != 0) { 631 print(scope->state, "%+"PRId64, util_sign_extend(val, width)); 632 } 633 break; 634 case TYPE_UOFFSET: 635 if (val != 0) { 636 print(scope->state, "+%"PRIu64, val); 637 } 638 break; 639 case TYPE_FLOAT: 640 if (width == 16) { 641 print(scope->state, "%f", _mesa_half_to_float(val)); 642 } else { 643 assert(width == 32); 644 print(scope->state, "%f", uif(val)); 645 } 646 break; 647 case TYPE_BOOL: 648 if (field->display) { 649 if (val) { 650 print(scope->state, "%s", field->display); 651 } 652 } else { 653 print(scope->state, "%u", (unsigned)val); 654 } 655 break; 656 case TYPE_ENUM: 657 display_enum_field(scope, field, v); 658 break; 659 660 case TYPE_ASSERT: 661 /* assert fields are not for display */ 662 assert(0); 663 break; 664 665 /* For fields that are decoded with another bitset hierarchy: */ 666 case TYPE_BITSET: 667 display_bitset_field(scope, field, v); 668 break; 669 default: 670 decode_error(scope->state, "Bad field type: %d (%s)", 671 field->type, field->name); 672 } 673} 674 675static void 676display(struct decode_scope *scope) 677{ 678 const struct isa_bitset *bitset = scope->bitset; 679 const char *display = find_display(scope, bitset); 680 681 if (!display) { 682 decode_error(scope->state, "%s: no display template", bitset->name); 683 return; 684 } 685 686 const char *p = display; 687 688 while (*p != '\0') { 689 if (*p == '{') { 690 const char *e = ++p; 691 while (*e != '}') { 692 e++; 693 } 694 695 char *field_name = strndup(p, e-p); 696 display_field(scope, field_name); 697 free(field_name); 698 699 p = e; 700 } else { 701 fputc(*p, scope->state->out); 702 scope->state->line_column++; 703 } 704 p++; 705 } 706} 707 708static void 709decode(struct decode_state *state, void *bin, int sz) 710{ 711 BITSET_WORD *instrs = bin; 712 unsigned errors = 0; /* number of consecutive unmatched instructions */ 713 714 assert(sz % BITMASK_WORDS == 0); 715 716 for (state->n = 0; state->n < state->num_instr; state->n++) { 717 bitmask_t instr = { 0 }; 718 719 next_instruction(&instr, &instrs[state->n * BITMASK_WORDS]); 720 state->line_column = 0; 721 722 if (state->options->max_errors && (errors > state->options->max_errors)) { 723 break; 724 } 725 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); 731 } 732 print(state, "l%d:\n", state->n); 733 } 734 735 if (state->options->instr_cb) { 736 state->options->instr_cb(state->options->cbdata, state->n, instr.bitset); 737 } 738 739 const struct isa_bitset *b = find_bitset(state, __instruction, instr); 740 if (!b) { 741 print(state, "no match: %"BITSET_FORMAT"\n", BITSET_VALUE(instr.bitset)); 742 errors++; 743 continue; 744 } 745 746 struct decode_scope *scope = push_scope(state, b, instr); 747 748 display(scope); 749 if (flush_errors(state)) { 750 errors++; 751 } else { 752 errors = 0; 753 } 754 print(state, "\n"); 755 756 pop_scope(scope); 757 758 if (state->options->stop) { 759 break; 760 } 761 } 762} 763 764void 765isa_decode(void *bin, int sz, FILE *out, const struct isa_decode_options *options) 766{ 767 const struct isa_decode_options default_options = { 768 .gpu_id = options ? options->gpu_id : 0, 769 .branch_labels = options ? options->branch_labels : false 770 }; 771 struct decode_state *state; 772 773 if (!options) 774 options = &default_options; 775 776 state = rzalloc_size(NULL, sizeof(*state)); 777 state->options = options; 778 state->num_instr = sz / (BITMASK_WORDS * sizeof(BITSET_WORD)); 779 780 if (state->options->branch_labels) { 781 state->branch_targets = rzalloc_size(state, 782 sizeof(BITSET_WORD) * BITSET_WORDS(state->num_instr)); 783 784 /* Do a pre-pass to find all the branch targets: */ 785 state->out = fopen("/dev/null", "w"); 786 state->options = &default_options; /* skip hooks for prepass */ 787 decode(state, bin, sz); 788 fclose(state->out); 789 if (options) { 790 state->options = options; 791 } 792 } 793 794 state->out = out; 795 796 decode(state, bin, sz); 797 798 ralloc_free(state); 799} 800