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    case NV_OP_STA:
  59       return 0;
  60    default:
  61       return 1;
  62    }
  63 }
  64
  65 boolean
  66 nv50_nvi_can_use_imm(struct nv_instruction *nvi, int s)
  67 {
  68    if (nvi->flags_src || nvi->flags_def)
  69       return FALSE;
  70
  71    switch (nvi->opcode) {
  72    case NV_OP_ADD:
  73    case NV_OP_MUL:
  74    case NV_OP_AND:
  75    case NV_OP_OR:
  76    case NV_OP_XOR:
  77    case NV_OP_SHL:
  78    case NV_OP_SHR:
  79       return (s == 1) && (nvi->src[0]->value->reg.file == NV_FILE_GPR) &&
  80          (nvi->def[0]->reg.file == NV_FILE_GPR);
  81    case NV_OP_MOV:
  82       assert(s == 0);
  83       return (nvi->def[0]->reg.file == NV_FILE_GPR);
  84    default:
  85       return FALSE;
  86    }
  87 }
  88
  89 boolean
  90 nv50_nvi_can_load(struct nv_instruction *nvi, int s, struct nv_value *value)
  91 {
  92    int i;
  93
  94    for (i = 0; i < 3 && nvi->src[i]; ++i)
  95       if (nvi->src[i]->value->reg.file == NV_FILE_IMM)
  96          return FALSE;
  97
  98    switch (nvi->opcode) {
  99    case NV_OP_ABS:
 100    case NV_OP_ADD:
 101    case NV_OP_CEIL:
 102    case NV_OP_FLOOR:
 103    case NV_OP_TRUNC:
 104    case NV_OP_CVT:
 105    case NV_OP_ROUND:
 106    case NV_OP_NEG:
 107    case NV_OP_MAD:
 108    case NV_OP_MUL:
 109    case NV_OP_SAT:
 110    case NV_OP_SUB:
 111    case NV_OP_MAX:
 112    case NV_OP_MIN:
 113       if (s == 0 && (value->reg.file == NV_FILE_MEM_S ||
 114                      value->reg.file == NV_FILE_MEM_P))
 115          return TRUE;
 116       if (value->reg.file < NV_FILE_MEM_C(0) ||
 117           value->reg.file > NV_FILE_MEM_C(15))
 118          return FALSE;
 119       return (s == 1) ||
 120          ((s == 2) && (nvi->src[1]->value->reg.file == NV_FILE_GPR));
 121    case NV_OP_MOV:
 122       assert(s == 0);
 123       return /* TRUE */ FALSE; /* don't turn MOVs into loads */
 124    default:
 125       return FALSE;
 126    }
 127 }
 128
 129 /* Return whether this instruction can be executed conditionally. */
 130 boolean
 131 nv50_nvi_can_predicate(struct nv_instruction *nvi)
 132 {
 133    int i;
 134
 135    if (nvi->flags_src)
 136       return FALSE;
 137    for (i = 0; i < 4 && nvi->src[i]; ++i)
 138       if (nvi->src[i]->value->reg.file == NV_FILE_IMM)
 139          return FALSE;
 140    return TRUE;
 141 }
 142
 143 ubyte
 144 nv50_supported_src_mods(uint opcode, int s)
 145 {
 146    switch (opcode) {
 147    case NV_OP_ABS:
 148       return NV_MOD_NEG | NV_MOD_ABS; /* obviously */
 149    case NV_OP_ADD:
 150    case NV_OP_MUL:
 151    case NV_OP_MAD:
 152       return NV_MOD_NEG;
 153    case NV_OP_DFDX:
 154    case NV_OP_DFDY:
 155       assert(s == 0);
 156       return NV_MOD_NEG;
 157    case NV_OP_MAX:
 158    case NV_OP_MIN:
 159       return NV_MOD_ABS;
 160    case NV_OP_CVT:
 161    case NV_OP_LG2:
 162    case NV_OP_NEG:
 163    case NV_OP_PREEX2:
 164    case NV_OP_PRESIN:
 165    case NV_OP_RCP:
 166    case NV_OP_RSQ:
 167       return NV_MOD_ABS | NV_MOD_NEG;
 168    default:
 169       return 0;
 170    }
 171 }
 172
 173 /* We may want an opcode table. */
 174 boolean
 175 nv50_op_can_write_flags(uint opcode)
 176 {
 177    if (nv_is_vector_op(opcode))
 178       return FALSE;
 179    switch (opcode) { /* obvious ones like KIL, CALL, etc. not included */
 180    case NV_OP_PHI:
 181    case NV_OP_MOV:
 182    case NV_OP_SELECT:
 183    case NV_OP_LINTERP:
 184    case NV_OP_PINTERP:
 185    case NV_OP_LDA:
 186       return FALSE;
 187    default:
 188       break;
 189    }
 190    if (opcode >= NV_OP_RCP && opcode <= NV_OP_PREEX2)
 191       return FALSE;
 192    return TRUE;
 193 }
 194
 195 int
 196 nv_nvi_refcount(struct nv_instruction *nvi)
 197 {
 198    int i, rc;
 199
 200    rc = nvi->flags_def ? nvi->flags_def->refc : 0;
 201
 202    for (i = 0; i < 4; ++i) {
 203       if (!nvi->def[i])
 204          return rc;
 205       rc += nvi->def[i]->refc;
 206    }
 207    return rc;
 208 }
 209
 210 int
 211 nvcg_replace_value(struct nv_pc *pc, struct nv_value *old_val,
 212                    struct nv_value *new_val)
 213 {
 214    int i, n;
 215
 216    if (old_val == new_val)
 217       return old_val->refc;
 218
 219    for (i = 0, n = 0; i < pc->num_refs; ++i) {
 220       if (pc->refs[i]->value == old_val) {
 221          ++n;
 222          nv_reference(pc, &pc->refs[i], new_val);
 223       }
 224    }
 225    return n;
 226 }
 227
 228 struct nv_value *
 229 nvcg_find_constant(struct nv_ref *ref)
 230 {
 231    struct nv_value *src;
 232
 233    if (!ref)
 234       return NULL;
 235
 236    src = ref->value;
 237    while (src->insn && src->insn->opcode == NV_OP_MOV) {
 238       assert(!src->insn->src[0]->mod);
 239       src = src->insn->src[0]->value;
 240    }
 241    if ((src->reg.file == NV_FILE_IMM) ||
 242        (src->insn && src->insn->opcode == NV_OP_LDA &&
 243         src->insn->src[0]->value->reg.file >= NV_FILE_MEM_C(0) &&
 244         src->insn->src[0]->value->reg.file <= NV_FILE_MEM_C(15)))
 245       return src;
 246    return NULL;
 247 }
 248
 249 struct nv_value *
 250 nvcg_find_immediate(struct nv_ref *ref)
 251 {
 252    struct nv_value *src = nvcg_find_constant(ref);
 253
 254    return (src && src->reg.file == NV_FILE_IMM) ? src : NULL;
 255 }
 256
 257 static void
 258 nv_pc_free_refs(struct nv_pc *pc)
 259 {
 260    int i;
 261    for (i = 0; i < pc->num_refs; i += 64)
 262       FREE(pc->refs[i]);
 263    FREE(pc->refs);
 264 }
 265
 266 static const char *
 267 edge_name(ubyte type)
 268 {
 269    switch (type) {
 270    case CFG_EDGE_FORWARD: return "forward";
 271    case CFG_EDGE_BACK: return "back";
 272    case CFG_EDGE_LOOP_ENTER: return "loop";
 273    case CFG_EDGE_LOOP_LEAVE: return "break";
 274    case CFG_EDGE_FAKE: return "fake";
 275    default:
 276       return "?";
 277    }
 278 }
 279
 280 void
 281 nv_pc_pass_in_order(struct nv_basic_block *root, nv_pc_pass_func f, void *priv)
 282 {
 283    struct nv_basic_block *bb[64], *bbb[16], *b;
 284    int j, p, pp;
 285
 286    bb[0] = root;
 287    p = 1;
 288    pp = 0;
 289
 290    while (p > 0) {
 291       b = bb[--p];
 292       b->priv = 0;
 293
 294       for (j = 1; j >= 0; --j) {
 295          if (!b->out[j])
 296             continue;
 297
 298          switch (b->out_kind[j]) {
 299          case CFG_EDGE_BACK:
 300             continue;
 301          case CFG_EDGE_FORWARD:
 302          case CFG_EDGE_FAKE:
 303             if (++b->out[j]->priv == b->out[j]->num_in)
 304                bb[p++] = b->out[j];
 305             break;
 306          case CFG_EDGE_LOOP_ENTER:
 307             bb[p++] = b->out[j];
 308             break;
 309          case CFG_EDGE_LOOP_LEAVE:
 310             if (!b->out[j]->priv) {
 311                bbb[pp++] = b->out[j];
 312                b->out[j]->priv = 1;
 313             }
 314             break;
 315          default:
 316             assert(0);
 317             break;
 318          }
 319       }
 320
 321       f(priv, b);
 322
 323       if (!p) {
 324          p = pp;
 325          for (; pp > 0; --pp)
 326             bb[pp - 1] = bbb[pp - 1];
 327       }
 328    }
 329 }
 330
 331 static void
 332 nv_do_print_function(void *priv, struct nv_basic_block *b)
 333 {
 334    struct nv_instruction *i;
 335
 336    debug_printf("=== BB %i ", b->id);
 337    if (b->out[0])
 338       debug_printf("[%s -> %i] ", edge_name(b->out_kind[0]), b->out[0]->id);
 339    if (b->out[1])
 340       debug_printf("[%s -> %i] ", edge_name(b->out_kind[1]), b->out[1]->id);
 341    debug_printf("===\n");
 342
 343    i = b->phi;
 344    if (!i)
 345       i = b->entry;
 346    for (; i; i = i->next)
 347       nv_print_instruction(i);
 348 }
 349
 350 void
 351 nv_print_function(struct nv_basic_block *root)
 352 {
 353    if (root->subroutine)
 354       debug_printf("SUBROUTINE %i\n", root->subroutine);
 355    else
 356       debug_printf("MAIN\n");
 357
 358    nv_pc_pass_in_order(root, nv_do_print_function, root);
 359 }
 360
 361 void
 362 nv_print_program(struct nv_pc *pc)
 363 {
 364    int i;
 365    for (i = 0; i < pc->num_subroutines + 1; ++i)
 366       if (pc->root[i])
 367          nv_print_function(pc->root[i]);
 368 }
 369
 370 #if NV50_DEBUG & NV50_DEBUG_PROG_CFLOW
 371 static void
 372 nv_do_print_cfgraph(struct nv_pc *pc, FILE *f, struct nv_basic_block *b)
 373 {
 374    int i;
 375
 376    b->pass_seq = pc->pass_seq;
 377
 378    fprintf(f, "\t%i [shape=box]\n", b->id);
 379
 380    for (i = 0; i < 2; ++i) {
 381       if (!b->out[i])
 382          continue;
 383       switch (b->out_kind[i]) {
 384       case CFG_EDGE_FORWARD:
 385          fprintf(f, "\t%i -> %i;\n", b->id, b->out[i]->id);
 386          break;
 387       case CFG_EDGE_LOOP_ENTER:
 388          fprintf(f, "\t%i -> %i [color=green];\n", b->id, b->out[i]->id);
 389          break;
 390       case CFG_EDGE_LOOP_LEAVE:
 391          fprintf(f, "\t%i -> %i [color=red];\n", b->id, b->out[i]->id);
 392          break;
 393       case CFG_EDGE_BACK:
 394          fprintf(f, "\t%i -> %i;\n", b->id, b->out[i]->id);
 395          continue;
 396       case CFG_EDGE_FAKE:
 397          fprintf(f, "\t%i -> %i [style=dotted];\n", b->id, b->out[i]->id);
 398          break;
 399       default:
 400          assert(0);
 401          break;
 402       }
 403       if (b->out[i]->pass_seq < pc->pass_seq)
 404          nv_do_print_cfgraph(pc, f, b->out[i]);
 405    }
 406 }
 407
 408 /* Print the control flow graph of subroutine @subr (0 == MAIN) to a file. */
 409 static void
 410 nv_print_cfgraph(struct nv_pc *pc, const char *filepath, int subr)
 411 {
 412    FILE *f;
 413
 414    f = fopen(filepath, "a");
 415    if (!f)
 416       return;
 417
 418    fprintf(f, "digraph G {\n");
 419
 420    ++pc->pass_seq;
 421
 422    nv_do_print_cfgraph(pc, f, pc->root[subr]);
 423
 424    fprintf(f, "}\n");
 425
 426    fclose(f);
 427 }
 428 #endif /* NV50_DEBUG_PROG_CFLOW */
 429
 430 static INLINE void
 431 nvcg_show_bincode(struct nv_pc *pc)
 432 {
 433    unsigned i;
 434
 435    for (i = 0; i < pc->bin_size / 4; ++i) {
 436       debug_printf("0x%08x ", pc->emit[i]);
 437       if ((i % 16) == 15)
 438          debug_printf("\n");
 439    }
 440    debug_printf("\n");
 441 }
 442
 443 static int
 444 nv50_emit_program(struct nv_pc *pc)
 445 {
 446    uint32_t *code = pc->emit;
 447    int n;
 448
 449    NV50_DBGMSG(SHADER, "emitting program: size = %u\n", pc->bin_size);
 450
 451    for (n = 0; n < pc->num_blocks; ++n) {
 452       struct nv_instruction *i;
 453       struct nv_basic_block *b = pc->bb_list[n];
 454
 455       for (i = b->entry; i; i = i->next) {
 456          nv50_emit_instruction(pc, i);
 457
 458          pc->bin_pos += 1 + (pc->emit[0] & 1);
 459          pc->emit += 1 + (pc->emit[0] & 1);
 460       }
 461    }
 462    assert(pc->emit == &code[pc->bin_size / 4]);
 463
 464    /* XXX: we can do better than this ... */
 465    if (!pc->bin_size ||
 466        !(pc->emit[-2] & 1) || (pc->emit[-2] & 2) || (pc->emit[-1] & 3)) {
 467       pc->emit[0] = 0xf0000001;
 468       pc->emit[1] = 0xe0000000;
 469       pc->bin_size += 8;
 470    }
 471
 472    pc->emit = code;
 473    code[pc->bin_size / 4 - 1] |= 1;
 474
 475 #if NV50_DEBUG & NV50_DEBUG_SHADER
 476    nvcg_show_bincode(pc);
 477 #endif
 478
 479    return 0;
 480 }
 481
 482 int
 483 nv50_generate_code(struct nv50_translation_info *ti)
 484 {
 485    struct nv_pc *pc;
 486    int ret;
 487    int i;
 488
 489    pc = CALLOC_STRUCT(nv_pc);
 490    if (!pc)
 491       return 1;
 492
 493    pc->root = CALLOC(ti->subr_nr + 1, sizeof(pc->root[0]));
 494    if (!pc->root) {
 495       FREE(pc);
 496       return 1;
 497    }
 498    pc->num_subroutines = ti->subr_nr;
 499
 500    ret = nv50_tgsi_to_nc(pc, ti);
 501    if (ret)
 502       goto out;
 503 #if NV50_DEBUG & NV50_DEBUG_PROG_IR
 504    nv_print_program(pc);
 505 #endif
 506
 507    pc->opt_reload_elim = ti->store_to_memory ? FALSE : TRUE;
 508
 509    /* optimization */
 510    ret = nv_pc_exec_pass0(pc);
 511    if (ret)
 512       goto out;
 513 #if NV50_DEBUG & NV50_DEBUG_PROG_IR
 514    nv_print_program(pc);
 515 #endif
 516
 517    /* register allocation */
 518    ret = nv_pc_exec_pass1(pc);
 519    if (ret)
 520       goto out;
 521 #if NV50_DEBUG & NV50_DEBUG_PROG_CFLOW
 522    nv_print_program(pc);
 523    nv_print_cfgraph(pc, "nv50_shader_cfgraph.dot", 0);
 524 #endif
 525
 526    /* prepare for emission */
 527    ret = nv_pc_exec_pass2(pc);
 528    if (ret)
 529       goto out;
 530    assert(!(pc->bin_size % 8));
 531
 532    pc->emit = CALLOC(pc->bin_size / 4 + 2, 4);
 533    if (!pc->emit) {
 534       ret = 3;
 535       goto out;
 536    }
 537    ret = nv50_emit_program(pc);
 538    if (ret)
 539       goto out;
 540
 541    ti->p->code_size = pc->bin_size;
 542    ti->p->code = pc->emit;
 543
 544    ti->p->immd_size = pc->immd_count * 4;
 545    ti->p->immd = pc->immd_buf;
 546
 547    /* highest 16 bit reg to num of 32 bit regs, limit to >= 4 */
 548    ti->p->max_gpr = MAX2(4, (pc->max_reg[NV_FILE_GPR] >> 1) + 1);
 549
 550    ti->p->fixups = pc->fixups;
 551    ti->p->num_fixups = pc->num_fixups;
 552
 553    ti->p->uses_lmem = ti->store_to_memory;
 554
 555    NV50_DBGMSG(SHADER, "SHADER TRANSLATION - %s\n", ret ? "failed" : "success");
 556
 557 out:
 558    nv_pc_free_refs(pc);
 559
 560    for (i = 0; i < pc->num_blocks; ++i)
 561       FREE(pc->bb_list[i]);
 562    if (pc->root)
 563       FREE(pc->root);
 564    if (ret) { /* on success, these will be referenced by nv50_program */
 565       if (pc->emit)
 566          FREE(pc->emit);
 567       if (pc->immd_buf)
 568          FREE(pc->immd_buf);
 569       if (pc->fixups)
 570          FREE(pc->fixups);
 571    }
 572    FREE(pc);
 573    return ret;
 574 }
 575
 576 static void
 577 nvbb_insert_phi(struct nv_basic_block *b, struct nv_instruction *i)
 578 {
 579    if (!b->phi) {
 580       i->prev = NULL;
 581       b->phi = i;
 582       i->next = b->entry;
 583       if (b->entry) {
 584          assert(!b->entry->prev && b->exit);
 585          b->entry->prev = i;
 586       } else {
 587          b->entry = i;
 588          b->exit = i;
 589       }
 590    } else {
 591       assert(b->entry);
 592       if (b->entry->opcode == NV_OP_PHI) { /* insert after entry */
 593          assert(b->entry == b->exit);
 594          b->entry->next = i;
 595          i->prev = b->entry;
 596          b->entry = i;
 597          b->exit = i;
 598       } else { /* insert before entry */
 599          assert(b->entry->prev && b->exit);
 600          i->next = b->entry;
 601          i->prev = b->entry->prev;
 602          b->entry->prev = i;
 603          i->prev->next = i;
 604       }
 605    }
 606 }
 607
 608 void
 609 nvbb_insert_tail(struct nv_basic_block *b, struct nv_instruction *i)
 610 {
 611    if (i->opcode == NV_OP_PHI) {
 612       nvbb_insert_phi(b, i);
 613    } else {
 614       i->prev = b->exit;
 615       if (b->exit)
 616          b->exit->next = i;
 617       b->exit = i;
 618       if (!b->entry)
 619          b->entry = i;
 620       else
 621       if (i->prev && i->prev->opcode == NV_OP_PHI)
 622          b->entry = i;
 623    }
 624
 625    i->bb = b;
 626    b->num_instructions++;
 627
 628    if (i->prev && i->prev->is_terminator)
 629       nv_nvi_permute(i->prev, i);
 630 }
 631
 632 void
 633 nvi_insert_after(struct nv_instruction *at, struct nv_instruction *ni)
 634 {
 635    if (!at->next) {
 636       nvbb_insert_tail(at->bb, ni);
 637       return;
 638    }
 639    ni->next = at->next;
 640    ni->prev = at;
 641    ni->next->prev = ni;
 642    ni->prev->next = ni;
 643 }
 644
 645 void
 646 nv_nvi_delete(struct nv_instruction *nvi)
 647 {
 648    struct nv_basic_block *b = nvi->bb;
 649    int j;
 650
 651    /* debug_printf("REM: "); nv_print_instruction(nvi); */
 652
 653    for (j = 0; j < 5; ++j)
 654       nv_reference(NULL, &nvi->src[j], NULL);
 655    nv_reference(NULL, &nvi->flags_src, NULL);
 656
 657    if (nvi->next)
 658       nvi->next->prev = nvi->prev;
 659    else {
 660       assert(nvi == b->exit);
 661       b->exit = nvi->prev;
 662    }
 663
 664    if (nvi->prev)
 665       nvi->prev->next = nvi->next;
 666
 667    if (nvi == b->entry) {
 668       /* PHIs don't get hooked to b->entry */
 669       b->entry = nvi->next;
 670       assert(!nvi->prev || nvi->prev->opcode == NV_OP_PHI);
 671    }
 672
 673    if (nvi == b->phi) {
 674       if (nvi->opcode != NV_OP_PHI)
 675          NV50_DBGMSG(PROG_IR, "NOTE: b->phi points to non-PHI instruction\n");
 676
 677       assert(!nvi->prev);
 678       if (!nvi->next || nvi->next->opcode != NV_OP_PHI)
 679          b->phi = NULL;
 680       else
 681          b->phi = nvi->next;
 682    }
 683 }
 684
 685 void
 686 nv_nvi_permute(struct nv_instruction *i1, struct nv_instruction *i2)
 687 {
 688    struct nv_basic_block *b = i1->bb;
 689
 690    assert(i1->opcode != NV_OP_PHI &&
 691           i2->opcode != NV_OP_PHI);
 692    assert(i1->next == i2);
 693
 694    if (b->exit == i2)
 695       b->exit = i1;
 696
 697    if (b->entry == i1)
 698       b->entry = i2;
 699
 700    i2->prev = i1->prev;
 701    i1->next = i2->next;
 702    i2->next = i1;
 703    i1->prev = i2;
 704
 705    if (i2->prev)
 706       i2->prev->next = i2;
 707    if (i1->next)
 708       i1->next->prev = i1;
 709 }
 710
 711 void
 712 nvbb_attach_block(struct nv_basic_block *parent,
 713                   struct nv_basic_block *b, ubyte edge_kind)
 714 {
 715    assert(b->num_in < 8);
 716
 717    if (parent->out[0]) {
 718       assert(!parent->out[1]);
 719       parent->out[1] = b;
 720       parent->out_kind[1] = edge_kind;
 721    } else {
 722       parent->out[0] = b;
 723       parent->out_kind[0] = edge_kind;
 724    }
 725
 726    b->in[b->num_in] = parent;
 727    b->in_kind[b->num_in++] = edge_kind;
 728 }
 729
 730 /* NOTE: all BRKs are treated as conditional, so there are 2 outgoing BBs */
 731
 732 boolean
 733 nvbb_dominated_by(struct nv_basic_block *b, struct nv_basic_block *d)
 734 {
 735    int j;
 736
 737    if (b == d)
 738       return TRUE;
 739
 740    for (j = 0; j < b->num_in; ++j)
 741       if ((b->in_kind[j] != CFG_EDGE_BACK) && !nvbb_dominated_by(b->in[j], d))
 742          return FALSE;
 743
 744    return j ? TRUE : FALSE;
 745 }
 746
 747 /* check if @bf (future) can be reached from @bp (past), stop at @bt */
 748 boolean
 749 nvbb_reachable_by(struct nv_basic_block *bf, struct nv_basic_block *bp,
 750                   struct nv_basic_block *bt)
 751 {
 752    struct nv_basic_block *q[NV_PC_MAX_BASIC_BLOCKS], *b;
 753    int i, p, n;
 754
 755    p = 0;
 756    n = 1;
 757    q[0] = bp;
 758
 759    while (p < n) {
 760       b = q[p++];
 761
 762       if (b == bf)
 763          break;
 764       if (b == bt)
 765          continue;
 766       assert(n <= (1024 - 2));
 767
 768       for (i = 0; i < 2; ++i) {
 769          if (b->out[i] && !IS_WALL_EDGE(b->out_kind[i]) && !b->out[i]->priv) {
 770             q[n] = b->out[i];
 771             q[n++]->priv = 1;
 772          }
 773       }
 774    }
 775    for (--n; n >= 0; --n)
 776       q[n]->priv = 0;
 777
 778    return (b == bf);
 779 }
 780
 781 static struct nv_basic_block *
 782 nvbb_find_dom_frontier(struct nv_basic_block *b, struct nv_basic_block *df)
 783 {
 784    struct nv_basic_block *out;
 785    int i;
 786
 787    if (!nvbb_dominated_by(df, b)) {
 788       for (i = 0; i < df->num_in; ++i) {
 789          if (df->in_kind[i] == CFG_EDGE_BACK)
 790             continue;
 791          if (nvbb_dominated_by(df->in[i], b))
 792             return df;
 793       }
 794    }
 795    for (i = 0; i < 2 && df->out[i]; ++i) {
 796       if (df->out_kind[i] == CFG_EDGE_BACK)
 797          continue;
 798       if ((out = nvbb_find_dom_frontier(b, df->out[i])))
 799          return out;
 800    }
 801    return NULL;
 802 }
 803
 804 struct nv_basic_block *
 805 nvbb_dom_frontier(struct nv_basic_block *b)
 806 {
 807    struct nv_basic_block *df;
 808    int i;
 809
 810    for (i = 0; i < 2 && b->out[i]; ++i)
 811       if ((df = nvbb_find_dom_frontier(b, b->out[i])))
 812          return df;
 813    return NULL;
 814 }