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