src/gallium/drivers/nvc0/nvc0_pc.c

   1 /*
   2  * Copyright 2010 Christoph Bumiller
   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 shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  17  * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  18  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
  19  * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  */
  22
  23 #define NOUVEAU_DEBUG 1
  24
  25 #include "nvc0_pc.h"
  26 #include "nvc0_program.h"
  27
  28 uint8_t
  29 nvc0_ir_reverse_cc(uint8_t cc)
  30 {
  31    static const uint8_t cc_swapped[8] = { 0, 4, 2, 6, 1, 5, 3, 7 };
  32
  33    return cc_swapped[cc & 7] | (cc & ~7);
  34 }
  35
  36 boolean
  37 nvc0_insn_can_load(struct nv_instruction *nvi, int s,
  38                    struct nv_instruction *ld)
  39 {
  40    int i;
  41
  42    if (ld->opcode == NV_OP_MOV && ld->src[0]->value->reg.file == NV_FILE_IMM) {
  43       if (s > 1 || !(nvc0_op_info_table[nvi->opcode].immediate & (1 << s)))
  44          return FALSE;
  45       if (!(nvc0_op_info_table[nvi->opcode].immediate & 4))
  46          if (ld->src[0]->value->reg.imm.u32 & 0xfff)
  47             return FALSE;
  48    } else
  49    if (!(nvc0_op_info_table[nvi->opcode].memory & (1 << s)))
  50       return FALSE;
  51
  52    if (ld->indirect >= 0)
  53       return FALSE;
  54
  55    /* a few ops can use g[] sources directly, but we don't support g[] yet */
  56    if (ld->src[0]->value->reg.file == NV_FILE_MEM_L ||
  57        ld->src[0]->value->reg.file == NV_FILE_MEM_G)
  58       return FALSE;
  59
  60    for (i = 0; i < 3 && nvi->src[i]; ++i)
  61       if (nvi->src[i]->value->reg.file == NV_FILE_IMM)
  62          return FALSE;
  63
  64    return TRUE;
  65 }
  66
  67 /* Return whether this instruction can be executed conditionally. */
  68 boolean
  69 nvc0_insn_is_predicateable(struct nv_instruction *nvi)
  70 {
  71    if (nvi->predicate >= 0) /* already predicated */
  72       return FALSE;
  73    if (!nvc0_op_info_table[nvi->opcode].predicate &&
  74        !nvc0_op_info_table[nvi->opcode].pseudo)
  75       return FALSE;
  76    return TRUE;
  77 }
  78
  79 int
  80 nvc0_insn_refcount(struct nv_instruction *nvi)
  81 {
  82    int rc = 0;
  83    int i;
  84    for (i = 0; i < 5 && nvi->def[i]; ++i) {
  85       if (!nvi->def[i])
  86          return rc;
  87       rc += nvi->def[i]->refc;
  88    }
  89    return rc;
  90 }
  91
  92 int
  93 nvc0_pc_replace_value(struct nv_pc *pc,
  94                       struct nv_value *old_val,
  95                       struct nv_value *new_val)
  96 {
  97    int i, n, s;
  98
  99    if (old_val == new_val)
 100       return old_val->refc;
 101
 102    for (i = 0, n = 0; i < pc->num_refs; ++i) {
 103       if (pc->refs[i]->value == old_val) {
 104          ++n;
 105          for (s = 0; s < 6 && pc->refs[i]->insn->src[s]; ++s)
 106             if (pc->refs[i]->insn->src[s] == pc->refs[i])
 107                break;
 108          assert(s < 6);
 109          nv_reference(pc, pc->refs[i]->insn, s, new_val);
 110       }
 111    }
 112    return n;
 113 }
 114
 115 static INLINE boolean
 116 is_gpr63(struct nv_value *val)
 117 {
 118    return (val->reg.file == NV_FILE_GPR && val->reg.id == 63);
 119 }
 120
 121 struct nv_value *
 122 nvc0_pc_find_constant(struct nv_ref *ref)
 123 {
 124    struct nv_value *src;
 125
 126    if (!ref)
 127       return NULL;
 128
 129    src = ref->value;
 130    while (src->insn && src->insn->opcode == NV_OP_MOV) {
 131       assert(!src->insn->src[0]->mod);
 132       src = src->insn->src[0]->value;
 133    }
 134    if ((src->reg.file == NV_FILE_IMM) || is_gpr63(src) ||
 135        (src->insn &&
 136         src->insn->opcode == NV_OP_LD &&
 137         src->insn->src[0]->value->reg.file >= NV_FILE_MEM_C(0) &&
 138         src->insn->src[0]->value->reg.file <= NV_FILE_MEM_C(15)))
 139       return src;
 140    return NULL;
 141 }
 142
 143 struct nv_value *
 144 nvc0_pc_find_immediate(struct nv_ref *ref)
 145 {
 146    struct nv_value *src = nvc0_pc_find_constant(ref);
 147
 148    return (src && (src->reg.file == NV_FILE_IMM || is_gpr63(src))) ? src : NULL;
 149 }
 150
 151 static void
 152 nv_pc_free_refs(struct nv_pc *pc)
 153 {
 154    int i;
 155    for (i = 0; i < pc->num_refs; i += 64)
 156       FREE(pc->refs[i]);
 157    FREE(pc->refs);
 158 }
 159
 160 static const char *
 161 edge_name(ubyte type)
 162 {
 163    switch (type) {
 164    case CFG_EDGE_FORWARD: return "forward";
 165    case CFG_EDGE_BACK: return "back";
 166    case CFG_EDGE_LOOP_ENTER: return "loop";
 167    case CFG_EDGE_LOOP_LEAVE: return "break";
 168    case CFG_EDGE_FAKE: return "fake";
 169    default:
 170       return "?";
 171    }
 172 }
 173
 174 void
 175 nvc0_pc_pass_in_order(struct nv_basic_block *root, nv_pc_pass_func f,
 176                       void *priv)
 177 {
 178    struct nv_basic_block *bb[64], *bbb[16], *b;
 179    int j, p, pp;
 180
 181    bb[0] = root;
 182    p = 1;
 183    pp = 0;
 184
 185    while (p > 0) {
 186       b = bb[--p];
 187       b->priv = 0;
 188
 189       for (j = 1; j >= 0; --j) {
 190          if (!b->out[j])
 191             continue;
 192
 193          switch (b->out_kind[j]) {
 194          case CFG_EDGE_BACK:
 195             continue;
 196          case CFG_EDGE_FORWARD:
 197          case CFG_EDGE_FAKE:
 198             if (++b->out[j]->priv == b->out[j]->num_in)
 199                bb[p++] = b->out[j];
 200             break;
 201          case CFG_EDGE_LOOP_ENTER:
 202             bb[p++] = b->out[j];
 203             break;
 204          case CFG_EDGE_LOOP_LEAVE:
 205             if (!b->out[j]->priv) {
 206                bbb[pp++] = b->out[j];
 207                b->out[j]->priv = 1;
 208             }
 209             break;
 210          default:
 211             assert(0);
 212             break;
 213          }
 214       }
 215
 216       f(priv, b);
 217
 218       if (!p) {
 219          p = pp;
 220          for (; pp > 0; --pp)
 221             bb[pp - 1] = bbb[pp - 1];
 222       }
 223    }
 224 }
 225
 226 static void
 227 nv_do_print_function(void *priv, struct nv_basic_block *b)
 228 {
 229    struct nv_instruction *i;
 230
 231    debug_printf("=== BB %i ", b->id);
 232    if (b->out[0])
 233       debug_printf("[%s -> %i] ", edge_name(b->out_kind[0]), b->out[0]->id);
 234    if (b->out[1])
 235       debug_printf("[%s -> %i] ", edge_name(b->out_kind[1]), b->out[1]->id);
 236    debug_printf("===\n");
 237
 238    i = b->phi;
 239    if (!i)
 240       i = b->entry;
 241    for (; i; i = i->next)
 242       nvc0_print_instruction(i);
 243 }
 244
 245 void
 246 nvc0_print_function(struct nv_basic_block *root)
 247 {
 248    if (root->subroutine)
 249       debug_printf("SUBROUTINE %i\n", root->subroutine);
 250    else
 251       debug_printf("MAIN\n");
 252
 253    nvc0_pc_pass_in_order(root, nv_do_print_function, root);
 254 }
 255
 256 void
 257 nvc0_print_program(struct nv_pc *pc)
 258 {
 259    int i;
 260    for (i = 0; i < pc->num_subroutines + 1; ++i)
 261       if (pc->root[i])
 262          nvc0_print_function(pc->root[i]);
 263 }
 264
 265 #if NOUVEAU_DEBUG > 1
 266 static void
 267 nv_do_print_cfgraph(struct nv_pc *pc, FILE *f, struct nv_basic_block *b)
 268 {
 269    int i;
 270
 271    b->pass_seq = pc->pass_seq;
 272
 273    fprintf(f, "\t%i [shape=box]\n", b->id);
 274
 275    for (i = 0; i < 2; ++i) {
 276       if (!b->out[i])
 277          continue;
 278       switch (b->out_kind[i]) {
 279       case CFG_EDGE_FORWARD:
 280          fprintf(f, "\t%i -> %i;\n", b->id, b->out[i]->id);
 281          break;
 282       case CFG_EDGE_LOOP_ENTER:
 283          fprintf(f, "\t%i -> %i [color=green];\n", b->id, b->out[i]->id);
 284          break;
 285       case CFG_EDGE_LOOP_LEAVE:
 286          fprintf(f, "\t%i -> %i [color=red];\n", b->id, b->out[i]->id);
 287          break;
 288       case CFG_EDGE_BACK:
 289          fprintf(f, "\t%i -> %i;\n", b->id, b->out[i]->id);
 290          continue;
 291       case CFG_EDGE_FAKE:
 292          fprintf(f, "\t%i -> %i [style=dotted];\n", b->id, b->out[i]->id);
 293          break;
 294       default:
 295          assert(0);
 296          break;
 297       }
 298       if (b->out[i]->pass_seq < pc->pass_seq)
 299          nv_do_print_cfgraph(pc, f, b->out[i]);
 300    }
 301 }
 302
 303 /* Print the control flow graph of subroutine @subr (0 == MAIN) to a file. */
 304 static void
 305 nv_print_cfgraph(struct nv_pc *pc, const char *filepath, int subr)
 306 {
 307    FILE *f;
 308
 309    f = fopen(filepath, "a");
 310    if (!f)
 311       return;
 312
 313    fprintf(f, "digraph G {\n");
 314
 315    ++pc->pass_seq;
 316
 317    nv_do_print_cfgraph(pc, f, pc->root[subr]);
 318
 319    fprintf(f, "}\n");
 320
 321    fclose(f);
 322 }
 323 #endif
 324
 325 static INLINE void
 326 nvc0_pc_print_binary(struct nv_pc *pc)
 327 {
 328    unsigned i;
 329
 330    NOUVEAU_DBG("nvc0_pc_print_binary(%u ops)\n", pc->emit_size / 8);
 331
 332    for (i = 0; i < pc->emit_size / 4; i += 2) {
 333       debug_printf("0x%08x ", pc->emit[i + 0]);
 334       debug_printf("0x%08x ", pc->emit[i + 1]);
 335       if ((i % 16) == 15)
 336          debug_printf("\n");
 337    }
 338    debug_printf("\n");
 339 }
 340
 341 static int
 342 nvc0_emit_program(struct nv_pc *pc)
 343 {
 344    uint32_t *code = pc->emit;
 345    int n;
 346
 347    NOUVEAU_DBG("emitting program: size = %u\n", pc->emit_size);
 348
 349    pc->emit_pos = 0;
 350    for (n = 0; n < pc->num_blocks; ++n) {
 351       struct nv_instruction *i;
 352       struct nv_basic_block *b = pc->bb_list[n];
 353
 354       for (i = b->entry; i; i = i->next) {
 355          nvc0_emit_instruction(pc, i);
 356          pc->emit += 2;
 357          pc->emit_pos += 8;
 358       }
 359    }
 360    assert(pc->emit == &code[pc->emit_size / 4]);
 361
 362    pc->emit[0] = 0x00001de7;
 363    pc->emit[1] = 0x80000000;
 364    pc->emit_size += 8;
 365
 366    pc->emit = code;
 367
 368 #ifdef NOUVEAU_DEBUG
 369    nvc0_pc_print_binary(pc);
 370 #else
 371    debug_printf("not printing binary\n");
 372 #endif
 373    return 0;
 374 }
 375
 376 int
 377 nvc0_generate_code(struct nvc0_translation_info *ti)
 378 {
 379    struct nv_pc *pc;
 380    int ret;
 381    int i;
 382
 383    pc = CALLOC_STRUCT(nv_pc);
 384    if (!pc)
 385       return 1;
 386
 387    pc->is_fragprog = ti->prog->type == PIPE_SHADER_FRAGMENT;
 388
 389    pc->root = CALLOC(ti->num_subrs + 1, sizeof(pc->root[0]));
 390    if (!pc->root) {
 391       FREE(pc);
 392       return 1;
 393    }
 394    pc->num_subroutines = ti->num_subrs;
 395
 396    ret = nvc0_tgsi_to_nc(pc, ti);
 397    if (ret)
 398       goto out;
 399 #if NOUVEAU_DEBUG > 1
 400    nvc0_print_program(pc);
 401 #endif
 402
 403    pc->opt_reload_elim = ti->require_stores ? FALSE : TRUE;
 404
 405    /* optimization */
 406    ret = nvc0_pc_exec_pass0(pc);
 407    if (ret)
 408       goto out;
 409 #ifdef NOUVEAU_DEBUG
 410    nvc0_print_program(pc);
 411 #endif
 412
 413    /* register allocation */
 414    ret = nvc0_pc_exec_pass1(pc);
 415    if (ret)
 416       goto out;
 417 #if NOUVEAU_DEBUG > 1
 418    nvc0_print_program(pc);
 419    nv_print_cfgraph(pc, "nvc0_shader_cfgraph.dot", 0);
 420 #endif
 421
 422    /* prepare for emission */
 423    ret = nvc0_pc_exec_pass2(pc);
 424    if (ret)
 425       goto out;
 426    assert(!(pc->emit_size % 8));
 427
 428    pc->emit = CALLOC(pc->emit_size / 4 + 2, 4);
 429    if (!pc->emit) {
 430       ret = 3;
 431       goto out;
 432    }
 433    ret = nvc0_emit_program(pc);
 434    if (ret)
 435       goto out;
 436
 437    ti->prog->code = pc->emit;
 438    ti->prog->code_base = 0;
 439    ti->prog->code_size = pc->emit_size;
 440    ti->prog->parm_size = 0;
 441
 442    ti->prog->max_gpr = MAX2(4, pc->max_reg[NV_FILE_GPR] + 1);
 443
 444    ti->prog->relocs = pc->reloc_entries;
 445    ti->prog->num_relocs = pc->num_relocs;
 446
 447    NOUVEAU_DBG("SHADER TRANSLATION - %s\n", ret ? "failure" : "success");
 448
 449 out:
 450    nv_pc_free_refs(pc);
 451
 452    for (i = 0; i < pc->num_blocks; ++i)
 453       FREE(pc->bb_list[i]);
 454    if (pc->root)
 455       FREE(pc->root);
 456    if (ret) {
 457       /* on success, these will be referenced by struct nvc0_program */
 458       if (pc->emit)
 459          FREE(pc->emit);
 460       if (pc->immd_buf)
 461          FREE(pc->immd_buf);
 462       if (pc->reloc_entries)
 463          FREE(pc->reloc_entries);
 464    }
 465    FREE(pc);
 466    return ret;
 467 }
 468
 469 static void
 470 nvbb_insert_phi(struct nv_basic_block *b, struct nv_instruction *i)
 471 {
 472    if (!b->phi) {
 473       i->prev = NULL;
 474       b->phi = i;
 475       i->next = b->entry;
 476       if (b->entry) {
 477          assert(!b->entry->prev && b->exit);
 478          b->entry->prev = i;
 479       } else {
 480          b->entry = i;
 481          b->exit = i;
 482       }
 483    } else {
 484       assert(b->entry);
 485       if (b->entry->opcode == NV_OP_PHI) { /* insert after entry */
 486          assert(b->entry == b->exit);
 487          b->entry->next = i;
 488          i->prev = b->entry;
 489          b->entry = i;
 490          b->exit = i;
 491       } else { /* insert before entry */
 492          assert(b->entry->prev && b->exit);
 493          i->next = b->entry;
 494          i->prev = b->entry->prev;
 495          b->entry->prev = i;
 496          i->prev->next = i;
 497       }
 498    }
 499 }
 500
 501 void
 502 nvc0_insn_append(struct nv_basic_block *b, struct nv_instruction *i)
 503 {
 504    if (i->opcode == NV_OP_PHI) {
 505       nvbb_insert_phi(b, i);
 506    } else {
 507       i->prev = b->exit;
 508       if (b->exit)
 509          b->exit->next = i;
 510       b->exit = i;
 511       if (!b->entry)
 512          b->entry = i;
 513       else
 514       if (i->prev && i->prev->opcode == NV_OP_PHI)
 515          b->entry = i;
 516    }
 517
 518    i->bb = b;
 519    b->num_instructions++;
 520
 521    if (i->prev && i->prev->terminator)
 522       nvc0_insns_permute(i->prev, i);
 523 }
 524
 525 void
 526 nvc0_insn_insert_after(struct nv_instruction *at, struct nv_instruction *ni)
 527 {
 528    if (!at->next) {
 529       nvc0_insn_append(at->bb, ni);
 530       return;
 531    }
 532    ni->next = at->next;
 533    ni->prev = at;
 534    ni->next->prev = ni;
 535    ni->prev->next = ni;
 536    ni->bb = at->bb;
 537    ni->bb->num_instructions++;
 538 }
 539
 540 void
 541 nvc0_insn_insert_before(struct nv_instruction *at, struct nv_instruction *ni)
 542 {
 543    nvc0_insn_insert_after(at, ni);
 544    nvc0_insns_permute(at, ni);
 545 }
 546
 547 void
 548 nvc0_insn_delete(struct nv_instruction *nvi)
 549 {
 550    struct nv_basic_block *b = nvi->bb;
 551    int s;
 552
 553    /* debug_printf("REM: "); nv_print_instruction(nvi); */
 554
 555    for (s = 0; s < 6 && nvi->src[s]; ++s)
 556       nv_reference(NULL, nvi, s, NULL);
 557
 558    if (nvi->next)
 559       nvi->next->prev = nvi->prev;
 560    else {
 561       assert(nvi == b->exit);
 562       b->exit = nvi->prev;
 563    }
 564
 565    if (nvi->prev)
 566       nvi->prev->next = nvi->next;
 567
 568    if (nvi == b->entry) {
 569       /* PHIs don't get hooked to b->entry */
 570       b->entry = nvi->next;
 571       assert(!nvi->prev || nvi->prev->opcode == NV_OP_PHI);
 572    }
 573
 574    if (nvi == b->phi) {
 575       if (nvi->opcode != NV_OP_PHI)
 576          NOUVEAU_DBG("NOTE: b->phi points to non-PHI instruction\n");
 577
 578       assert(!nvi->prev);
 579       if (!nvi->next || nvi->next->opcode != NV_OP_PHI)
 580          b->phi = NULL;
 581       else
 582          b->phi = nvi->next;
 583    }
 584 }
 585
 586 void
 587 nvc0_insns_permute(struct nv_instruction *i1, struct nv_instruction *i2)
 588 {
 589    struct nv_basic_block *b = i1->bb;
 590
 591    assert(i1->opcode != NV_OP_PHI &&
 592           i2->opcode != NV_OP_PHI);
 593    assert(i1->next == i2);
 594
 595    if (b->exit == i2)
 596       b->exit = i1;
 597
 598    if (b->entry == i1)
 599       b->entry = i2;
 600
 601    i2->prev = i1->prev;
 602    i1->next = i2->next;
 603    i2->next = i1;
 604    i1->prev = i2;
 605
 606    if (i2->prev)
 607       i2->prev->next = i2;
 608    if (i1->next)
 609       i1->next->prev = i1;
 610 }
 611
 612 void
 613 nvc0_bblock_attach(struct nv_basic_block *parent,
 614                    struct nv_basic_block *b, ubyte edge_kind)
 615 {
 616    assert(b->num_in < 8);
 617
 618    if (parent->out[0]) {
 619       assert(!parent->out[1]);
 620       parent->out[1] = b;
 621       parent->out_kind[1] = edge_kind;
 622    } else {
 623       parent->out[0] = b;
 624       parent->out_kind[0] = edge_kind;
 625    }
 626
 627    b->in[b->num_in] = parent;
 628    b->in_kind[b->num_in++] = edge_kind;
 629 }
 630
 631 /* NOTE: all BRKs are treated as conditional, so there are 2 outgoing BBs */
 632
 633 boolean
 634 nvc0_bblock_dominated_by(struct nv_basic_block *b, struct nv_basic_block *d)
 635 {
 636    int j;
 637
 638    if (b == d)
 639       return TRUE;
 640
 641    for (j = 0; j < b->num_in; ++j)
 642       if ((b->in_kind[j] != CFG_EDGE_BACK) &&
 643           !nvc0_bblock_dominated_by(b->in[j], d))
 644          return FALSE;
 645
 646    return j ? TRUE : FALSE;
 647 }
 648
 649 /* check if @bf (future) can be reached from @bp (past), stop at @bt */
 650 boolean
 651 nvc0_bblock_reachable_by(struct nv_basic_block *bf, struct nv_basic_block *bp,
 652                          struct nv_basic_block *bt)
 653 {
 654    struct nv_basic_block *q[NV_PC_MAX_BASIC_BLOCKS], *b;
 655    int i, p, n;
 656
 657    p = 0;
 658    n = 1;
 659    q[0] = bp;
 660
 661    while (p < n) {
 662       b = q[p++];
 663
 664       if (b == bf)
 665          break;
 666       if (b == bt)
 667          continue;
 668       assert(n <= (1024 - 2));
 669
 670       for (i = 0; i < 2; ++i) {
 671          if (b->out[i] && !IS_WALL_EDGE(b->out_kind[i]) && !b->out[i]->priv) {
 672             q[n] = b->out[i];
 673             q[n++]->priv = 1;
 674          }
 675       }
 676    }
 677    for (--n; n >= 0; --n)
 678       q[n]->priv = 0;
 679
 680    return (b == bf);
 681 }
 682
 683 static struct nv_basic_block *
 684 nvbb_find_dom_frontier(struct nv_basic_block *b, struct nv_basic_block *df)
 685 {
 686    struct nv_basic_block *out;
 687    int i;
 688
 689    if (!nvc0_bblock_dominated_by(df, b)) {
 690       for (i = 0; i < df->num_in; ++i) {
 691          if (df->in_kind[i] == CFG_EDGE_BACK)
 692             continue;
 693          if (nvc0_bblock_dominated_by(df->in[i], b))
 694             return df;
 695       }
 696    }
 697    for (i = 0; i < 2 && df->out[i]; ++i) {
 698       if (df->out_kind[i] == CFG_EDGE_BACK)
 699          continue;
 700       if ((out = nvbb_find_dom_frontier(b, df->out[i])))
 701          return out;
 702    }
 703    return NULL;
 704 }
 705
 706 struct nv_basic_block *
 707 nvc0_bblock_dom_frontier(struct nv_basic_block *b)
 708 {
 709    struct nv_basic_block *df;
 710    int i;
 711
 712    for (i = 0; i < 2 && b->out[i]; ++i)
 713       if ((df = nvbb_find_dom_frontier(b, b->out[i])))
 714          return df;
 715    return NULL;
 716 }