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