src/gallium/drivers/nv50/nv50_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 NV50PC_DEBUG */
  24
  25 #include "nv50_pc.h"
  26 #include "nv50_program.h"
  27
  28 #include <stdio.h>
  29
  30 /* returns TRUE if operands 0 and 1 can be swapped */
  31 boolean
  32 nv_op_commutative(uint opcode)
  33 {
  34    switch (opcode) {
  35    case NV_OP_ADD:
  36    case NV_OP_MUL:
  37    case NV_OP_MAD:
  38    case NV_OP_AND:
  39    case NV_OP_OR:
  40    case NV_OP_XOR:
  41    case NV_OP_MIN:
  42    case NV_OP_MAX:
  43    case NV_OP_SAD:
  44      return TRUE;
  45    default:
  46      return FALSE;
  47    }
  48 }
  49
  50 /* return operand to which the address register applies */
  51 int
  52 nv50_indirect_opnd(struct nv_instruction *i)
  53 {
  54    if (!i->src[4])
  55       return -1;
  56
  57    switch (i->opcode) {
  58    case NV_OP_MOV:
  59    case NV_OP_LDA:
  60       return 0;
  61    default:
  62       return 1;
  63    }
  64 }
  65
  66 boolean
  67 nv50_nvi_can_use_imm(struct nv_instruction *nvi, int s)
  68 {
  69    if (nvi->flags_src || nvi->flags_def)
  70       return FALSE;
  71
  72    switch (nvi->opcode) {
  73    case NV_OP_ADD:
  74    case NV_OP_MUL:
  75    case NV_OP_AND:
  76    case NV_OP_OR:
  77    case NV_OP_XOR:
  78    case NV_OP_SHL:
  79    case NV_OP_SHR:
  80       return (s == 1) && (nvi->src[0]->value->reg.file == NV_FILE_GPR) &&
  81          (nvi->def[0]->reg.file == NV_FILE_GPR);
  82    case NV_OP_MOV:
  83       assert(s == 0);
  84       return (nvi->def[0]->reg.file == NV_FILE_GPR);
  85    default:
  86       return FALSE;
  87    }
  88 }
  89
  90 boolean
  91 nv50_nvi_can_load(struct nv_instruction *nvi, int s, struct nv_value *value)
  92 {
  93    int i;
  94
  95    for (i = 0; i < 3 && nvi->src[i]; ++i)
  96       if (nvi->src[i]->value->reg.file == NV_FILE_IMM)
  97          return FALSE;
  98
  99    switch (nvi->opcode) {
 100    case NV_OP_ABS:
 101    case NV_OP_ADD:
 102    case NV_OP_CEIL:
 103    case NV_OP_FLOOR:
 104    case NV_OP_TRUNC:
 105    case NV_OP_CVT:
 106    case NV_OP_MAD:
 107    case NV_OP_MUL:
 108    case NV_OP_SAT:
 109    case NV_OP_SUB:
 110    case NV_OP_MAX:
 111    case NV_OP_MIN:
 112       if (s == 0 && (value->reg.file == NV_FILE_MEM_S ||
 113                      value->reg.file == NV_FILE_MEM_P))
 114          return TRUE;
 115       if (s == 1 &&
 116           value->reg.file >= NV_FILE_MEM_C(0) &&
 117           value->reg.file <= NV_FILE_MEM_C(15))
 118          return TRUE;
 119       if (s == 2 && nvi->src[1]->value->reg.file == NV_FILE_GPR)
 120          return TRUE;
 121       return FALSE;
 122    case NV_OP_MOV:
 123       assert(s == 0);
 124       return TRUE;
 125    default:
 126       return FALSE;
 127    }
 128 }
 129
 130 /* Return whether this instruction can be executed conditionally. */
 131 boolean
 132 nv50_nvi_can_predicate(struct nv_instruction *nvi)
 133 {
 134    int i;
 135
 136    if (nvi->flags_src)
 137       return FALSE;
 138    for (i = 0; i < 4 && nvi->src[i]; ++i)
 139       if (nvi->src[i]->value->reg.file == NV_FILE_IMM)
 140          return FALSE;
 141    return TRUE;
 142 }
 143
 144 ubyte
 145 nv50_supported_src_mods(uint opcode, int s)
 146 {
 147    switch (opcode) {
 148    case NV_OP_ABS:
 149       return NV_MOD_NEG | NV_MOD_ABS; /* obviously */
 150    case NV_OP_ADD:
 151    case NV_OP_MUL:
 152    case NV_OP_MAD:
 153       return NV_MOD_NEG;
 154    case NV_OP_DFDX:
 155    case NV_OP_DFDY:
 156       assert(s == 0);
 157       return NV_MOD_NEG;
 158    case NV_OP_MAX:
 159    case NV_OP_MIN:
 160       return NV_MOD_ABS;
 161    case NV_OP_CVT:
 162    case NV_OP_LG2:
 163    case NV_OP_NEG:
 164    case NV_OP_PREEX2:
 165    case NV_OP_PRESIN:
 166    case NV_OP_RCP:
 167    case NV_OP_RSQ:
 168       return NV_MOD_ABS | NV_MOD_NEG;
 169    default:
 170       return 0;
 171    }
 172 }
 173
 174 int
 175 nv_nvi_refcount(struct nv_instruction *nvi)
 176 {
 177    int i, rc;
 178
 179    rc = nvi->flags_def ? nvi->flags_def->refc : 0;
 180
 181    for (i = 0; i < 4; ++i) {
 182       if (!nvi->def[i])
 183          return rc;
 184       rc += nvi->def[i]->refc;
 185    }
 186    return rc;
 187 }
 188
 189 int
 190 nvcg_replace_value(struct nv_pc *pc, struct nv_value *old_val,
 191                    struct nv_value *new_val)
 192 {
 193    int i, n;
 194
 195    if (old_val == new_val)
 196       return old_val->refc;
 197
 198    for (i = 0, n = 0; i < pc->num_refs; ++i) {
 199       if (pc->refs[i]->value == old_val) {
 200          ++n;
 201          nv_reference(pc, &pc->refs[i], new_val);
 202       }
 203    }
 204    return n;
 205 }
 206
 207 struct nv_value *
 208 nvcg_find_constant(struct nv_ref *ref)
 209 {
 210    struct nv_value *src;
 211
 212    if (!ref)
 213       return NULL;
 214
 215    src = ref->value;
 216    while (src->insn && src->insn->opcode == NV_OP_MOV) {
 217       assert(!src->insn->src[0]->mod);
 218       src = src->insn->src[0]->value;
 219    }
 220    if ((src->reg.file == NV_FILE_IMM) ||
 221        (src->insn && src->insn->opcode == NV_OP_LDA &&
 222         src->insn->src[0]->value->reg.file >= NV_FILE_MEM_C(0) &&
 223         src->insn->src[0]->value->reg.file <= NV_FILE_MEM_C(15)))
 224       return src;
 225    return NULL;
 226 }
 227
 228 struct nv_value *
 229 nvcg_find_immediate(struct nv_ref *ref)
 230 {
 231    struct nv_value *src = nvcg_find_constant(ref);
 232
 233    return (src && src->reg.file == NV_FILE_IMM) ? src : NULL;
 234 }
 235
 236 static void
 237 nv_pc_free_refs(struct nv_pc *pc)
 238 {
 239    int i;
 240    for (i = 0; i < pc->num_refs; i += 64)
 241       FREE(pc->refs[i]);
 242 }
 243
 244 static const char *
 245 edge_name(ubyte type)
 246 {
 247    switch (type) {
 248    case CFG_EDGE_FORWARD: return "forward";
 249    case CFG_EDGE_BACK: return "back";
 250    case CFG_EDGE_LOOP_ENTER: return "loop";
 251    case CFG_EDGE_LOOP_LEAVE: return "break";
 252    case CFG_EDGE_FAKE: return "fake";
 253    default:
 254       return "?";
 255    }
 256 }
 257
 258 void
 259 nv_pc_pass_in_order(struct nv_basic_block *root, nv_pc_pass_func f, void *priv)
 260 {
 261    struct nv_basic_block *bb[64], *bbb[16], *b;
 262    int j, p, pp;
 263
 264    bb[0] = root;
 265    p = 1;
 266    pp = 0;
 267
 268    while (p > 0) {
 269       b = bb[--p];
 270       b->priv = 0;
 271
 272       for (j = 1; j >= 0; --j) {
 273          if (!b->out[j])
 274             continue;
 275
 276          switch (b->out_kind[j]) {
 277          case CFG_EDGE_BACK:
 278             continue;
 279          case CFG_EDGE_FORWARD:
 280          case CFG_EDGE_FAKE:
 281             if (++b->out[j]->priv == b->out[j]->num_in)
 282                bb[p++] = b->out[j];
 283             break;
 284          case CFG_EDGE_LOOP_ENTER:
 285             bb[p++] = b->out[j];
 286             break;
 287          case CFG_EDGE_LOOP_LEAVE:
 288             bbb[pp++] = b->out[j];
 289             break;
 290          default:
 291             assert(0);
 292             break;
 293          }
 294       }
 295
 296       f(priv, b);
 297
 298       if (!p) {
 299          p = pp;
 300          for (; pp > 0; --pp)
 301             bb[pp - 1] = bbb[pp - 1];
 302       }
 303    }
 304 }
 305
 306 static void
 307 nv_do_print_program(void *priv, struct nv_basic_block *b)
 308 {
 309    struct nv_instruction *i = b->phi;
 310
 311    debug_printf("=== BB %i ", b->id);
 312    if (b->out[0])
 313       debug_printf("[%s -> %i] ", edge_name(b->out_kind[0]), b->out[0]->id);
 314    if (b->out[1])
 315       debug_printf("[%s -> %i] ", edge_name(b->out_kind[1]), b->out[1]->id);
 316    debug_printf("===\n");
 317
 318    i = b->phi;
 319    if (!i)
 320       i = b->entry;
 321    for (; i; i = i->next)
 322       nv_print_instruction(i);
 323 }
 324
 325 void
 326 nv_print_program(struct nv_basic_block *root)
 327 {
 328    nv_pc_pass_in_order(root, nv_do_print_program, root);
 329
 330    debug_printf("END\n\n");
 331 }
 332
 333 static INLINE void
 334 nvcg_show_bincode(struct nv_pc *pc)
 335 {
 336    int i;
 337
 338    for (i = 0; i < pc->bin_size / 4; ++i)
 339       debug_printf("0x%08x ", pc->emit[i]);
 340    debug_printf("\n");
 341 }
 342
 343 static int
 344 nv50_emit_program(struct nv_pc *pc)
 345 {
 346    uint32_t *code = pc->emit;
 347    int n;
 348
 349    NV50_DBGMSG("emitting program: size = %u\n", pc->bin_size);
 350
 351    for (n = 0; n < pc->num_blocks; ++n) {
 352       struct nv_instruction *i;
 353       struct nv_basic_block *b = pc->bb_list[n];
 354
 355       for (i = b->entry; i; i = i->next) {
 356          nv50_emit_instruction(pc, i);
 357
 358          pc->bin_pos += 1 + (pc->emit[0] & 1);
 359          pc->emit += 1 + (pc->emit[0] & 1);
 360       }
 361    }
 362    assert(pc->emit == &code[pc->bin_size / 4]);
 363
 364    /* XXX: we can do better than this ... */
 365    if (!(pc->emit[-2] & 1) || (pc->emit[-2] & 2) || (pc->emit[-1] & 3)) {
 366       pc->emit[0] = 0xf0000001;
 367       pc->emit[1] = 0xe0000000;
 368       pc->bin_size += 8;
 369    }
 370
 371    pc->emit = code;
 372    code[pc->bin_size / 4 - 1] |= 1;
 373
 374 #ifdef NV50PC_DEBUG
 375    nvcg_show_bincode(pc);
 376 #endif
 377
 378    return 0;
 379 }
 380
 381 int
 382 nv50_generate_code(struct nv50_translation_info *ti)
 383 {
 384    struct nv_pc *pc;
 385    int ret;
 386
 387    pc = CALLOC_STRUCT(nv_pc);
 388    if (!pc)
 389       return 1;
 390
 391    ret = nv50_tgsi_to_nc(pc, ti);
 392    if (ret)
 393       goto out;
 394 #ifdef NV50PC_DEBUG
 395    nv_print_program(pc->root);
 396 #endif
 397
 398    /* optimization */
 399    ret = nv_pc_exec_pass0(pc);
 400    if (ret)
 401       goto out;
 402 #ifdef NV50PC_DEBUG
 403    nv_print_program(pc->root);
 404 #endif
 405
 406    /* register allocation */
 407    ret = nv_pc_exec_pass1(pc);
 408    if (ret)
 409       goto out;
 410 #ifdef NV50PC_DEBUG
 411    nv_print_program(pc->root);
 412 #endif
 413
 414    /* prepare for emission */
 415    ret = nv_pc_exec_pass2(pc);
 416    if (ret)
 417       goto out;
 418
 419    pc->emit = CALLOC(pc->bin_size / 4 + 2, 4);
 420    if (!pc->emit) {
 421       ret = 3;
 422       goto out;
 423    }
 424    ret = nv50_emit_program(pc);
 425    if (ret)
 426       goto out;
 427
 428    ti->p->code_size = pc->bin_size;
 429    ti->p->code = pc->emit;
 430
 431    ti->p->immd_size = pc->immd_count * 4;
 432    ti->p->immd = pc->immd_buf;
 433
 434    /* highest 16 bit reg to num of 32 bit regs */
 435    ti->p->max_gpr = (pc->max_reg[NV_FILE_GPR] >> 1) + 1;
 436
 437    ti->p->fixups = pc->fixups;
 438    ti->p->num_fixups = pc->num_fixups;
 439
 440    NV50_DBGMSG("SHADER TRANSLATION - %s\n", ret ? "failure" : "success");
 441
 442 out:
 443    nv_pc_free_refs(pc);
 444    if (ret) {
 445       if (pc->emit)
 446          free(pc->emit);
 447       if (pc->immd_buf)
 448          free(pc->immd_buf);
 449       if (pc->fixups)
 450          free(pc->fixups);
 451    }
 452    free(pc);
 453
 454    return ret;
 455 }
 456
 457 static void
 458 nvbb_insert_phi(struct nv_basic_block *b, struct nv_instruction *i)
 459 {
 460    if (!b->phi) {
 461       i->prev = NULL;
 462       b->phi = i;
 463       i->next = b->entry;
 464       if (b->entry) {
 465          assert(!b->entry->prev && b->exit);
 466          b->entry->prev = i;
 467       } else {
 468          b->entry = i;
 469          b->exit = i;
 470       }
 471    } else {
 472       assert(b->entry);
 473       if (b->entry->opcode == NV_OP_PHI) { /* insert after entry */
 474          assert(b->entry == b->exit);
 475          b->entry->next = i;
 476          i->prev = b->entry;
 477          b->entry = i;
 478          b->exit = i;
 479       } else { /* insert before entry */
 480          assert(b->entry->prev && b->exit);
 481          i->next = b->entry;
 482          i->prev = b->entry->prev;
 483          b->entry->prev = i;
 484          i->prev->next = i;
 485       }
 486    }
 487 }
 488
 489 void
 490 nvbb_insert_tail(struct nv_basic_block *b, struct nv_instruction *i)
 491 {
 492    if (i->opcode == NV_OP_PHI) {
 493       nvbb_insert_phi(b, i);
 494    } else {
 495       i->prev = b->exit;
 496       if (b->exit)
 497          b->exit->next = i;
 498       b->exit = i;
 499       if (!b->entry)
 500          b->entry = i;
 501       else
 502       if (i->prev && i->prev->opcode == NV_OP_PHI)
 503          b->entry = i;
 504    }
 505
 506    i->bb = b;
 507    b->num_instructions++;
 508 }
 509
 510 void
 511 nv_nvi_delete(struct nv_instruction *nvi)
 512 {
 513    struct nv_basic_block *b = nvi->bb;
 514    int j;
 515
 516    /* debug_printf("REM: "); nv_print_instruction(nvi); */
 517
 518    for (j = 0; j < 5; ++j)
 519       nv_reference(NULL, &nvi->src[j], NULL);
 520    nv_reference(NULL, &nvi->flags_src, NULL);
 521
 522    if (nvi->next)
 523       nvi->next->prev = nvi->prev;
 524    else {
 525       assert(nvi == b->exit);
 526       b->exit = nvi->prev;
 527    }
 528
 529    if (nvi->prev)
 530       nvi->prev->next = nvi->next;
 531
 532    if (nvi == b->entry) {
 533       /* PHIs don't get hooked to b->entry */
 534       b->entry = nvi->next;
 535       assert(!nvi->prev || nvi->prev->opcode == NV_OP_PHI);
 536    }
 537
 538    if (nvi == b->phi) {
 539       if (nvi->opcode != NV_OP_PHI)
 540          NV50_DBGMSG("NOTE: b->phi points to non-PHI instruction\n");
 541
 542       assert(!nvi->prev);
 543       if (!nvi->next || nvi->next->opcode != NV_OP_PHI)
 544          b->phi = NULL;
 545       else
 546          b->phi = nvi->next;
 547    }
 548 }
 549
 550 void
 551 nv_nvi_permute(struct nv_instruction *i1, struct nv_instruction *i2)
 552 {
 553    struct nv_basic_block *b = i1->bb;
 554
 555    assert(i1->opcode != NV_OP_PHI &&
 556           i2->opcode != NV_OP_PHI);
 557    assert(i1->next == i2);
 558
 559    if (b->exit == i2)
 560       b->exit = i1;
 561
 562    if (b->entry == i1)
 563       b->entry = i2;
 564
 565    i2->prev = i1->prev;
 566    i1->next = i2->next;
 567    i2->next = i1;
 568    i1->prev = i2;
 569
 570    if (i2->prev)
 571       i2->prev->next = i2;
 572    if (i1->next)
 573       i1->next->prev = i1;
 574 }
 575
 576 void
 577 nvbb_attach_block(struct nv_basic_block *parent,
 578                   struct nv_basic_block *b, ubyte edge_kind)
 579 {
 580    assert(b->num_in < 8);
 581
 582    if (parent->out[0]) {
 583       assert(!parent->out[1]);
 584       parent->out[1] = b;
 585       parent->out_kind[1] = edge_kind;
 586    } else {
 587       parent->out[0] = b;
 588       parent->out_kind[0] = edge_kind;
 589    }
 590
 591    b->in[b->num_in] = parent;
 592    b->in_kind[b->num_in++] = edge_kind;
 593 }
 594
 595 /* NOTE: all BRKs are treated as conditional, so there are 2 outgoing BBs */
 596
 597 boolean
 598 nvbb_dominated_by(struct nv_basic_block *b, struct nv_basic_block *d)
 599 {
 600    int j;
 601
 602    if (b == d)
 603       return TRUE;
 604
 605    for (j = 0; j < b->num_in; ++j)
 606       if ((b->in_kind[j] != CFG_EDGE_BACK) && !nvbb_dominated_by(b->in[j], d))
 607          return FALSE;
 608
 609    return j ? TRUE : FALSE;
 610 }
 611
 612 /* check if bf (future) can be reached from bp (past) */
 613 boolean
 614 nvbb_reachable_by(struct nv_basic_block *bf, struct nv_basic_block *bp,
 615                   struct nv_basic_block *bt)
 616 {
 617    if (bf == bp)
 618       return TRUE;
 619    if (bp == bt)
 620       return FALSE;
 621
 622    if (bp->out[0] && !IS_WALL_EDGE(bp->out_kind[0]) &&
 623        nvbb_reachable_by(bf, bp->out[0], bt))
 624       return TRUE;
 625    if (bp->out[1] && !IS_WALL_EDGE(bp->out_kind[1]) &&
 626        nvbb_reachable_by(bf, bp->out[1], bt))
 627       return TRUE;
 628    return FALSE;
 629 }
 630
 631 static struct nv_basic_block *
 632 nvbb_find_dom_frontier(struct nv_basic_block *b, struct nv_basic_block *df)
 633 {
 634    struct nv_basic_block *out;
 635    int i;
 636
 637    if (!nvbb_dominated_by(df, b)) {
 638       for (i = 0; i < df->num_in; ++i) {
 639          if (df->in_kind[i] == CFG_EDGE_BACK)
 640             continue;
 641          if (nvbb_dominated_by(df->in[i], b))
 642             return df;
 643       }
 644    }
 645    for (i = 0; i < 2 && df->out[i]; ++i) {
 646       if (df->out_kind[i] == CFG_EDGE_BACK)
 647          continue;
 648       if ((out = nvbb_find_dom_frontier(b, df->out[i])))
 649          return out;
 650    }
 651    return NULL;
 652 }
 653
 654 struct nv_basic_block *
 655 nvbb_dom_frontier(struct nv_basic_block *b)
 656 {
 657    struct nv_basic_block *df;
 658    int i;
 659
 660    for (i = 0; i < 2 && b->out[i]; ++i)
 661       if ((df = nvbb_find_dom_frontier(b, b->out[i])))
 662          return df;
 663    return NULL;
 664 }