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