src/gallium/drivers/nv50/nv50_pc_optimize.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
  25 #define DESCEND_ARBITRARY(j, f)                                 \
  26 do {                                                            \
  27    b->pass_seq = ctx->pc->pass_seq;                             \
  28                                                                 \
  29    for (j = 0; j < 2; ++j)                                      \
  30       if (b->out[j] && b->out[j]->pass_seq < ctx->pc->pass_seq) \
  31          f(ctx, b->out[j]);                                       \
  32 } while (0)
  33
  34 extern unsigned nv50_inst_min_size(struct nv_instruction *);
  35
  36 struct nv_pc_pass {
  37    struct nv_pc *pc;
  38 };
  39
  40 static INLINE boolean
  41 values_equal(struct nv_value *a, struct nv_value *b)
  42 {
  43    /* XXX: sizes */
  44    return (a->reg.file == b->reg.file && a->join->reg.id == b->join->reg.id);
  45 }
  46
  47 static INLINE boolean
  48 inst_commutation_check(struct nv_instruction *a,
  49                        struct nv_instruction *b)
  50 {
  51    int si, di;
  52
  53    for (di = 0; di < 4; ++di) {
  54       if (!a->def[di])
  55          break;
  56       for (si = 0; si < 5; ++si) {
  57          if (!b->src[si])
  58             continue;
  59          if (values_equal(a->def[di], b->src[si]->value))
  60             return FALSE;
  61       }
  62    }
  63
  64    if (b->flags_src && b->flags_src->value == a->flags_def)
  65       return FALSE;
  66
  67    return TRUE;
  68 }
  69
  70 /* Check whether we can swap the order of the instructions,
  71  * where a & b may be either the earlier or the later one.
  72  */
  73 static boolean
  74 inst_commutation_legal(struct nv_instruction *a,
  75                        struct nv_instruction *b)
  76 {
  77    return inst_commutation_check(a, b) && inst_commutation_check(b, a);
  78 }
  79
  80 static INLINE boolean
  81 inst_cullable(struct nv_instruction *nvi)
  82 {
  83    return (!(nvi->is_terminator ||
  84              nvi->target ||
  85              nvi->fixed ||
  86              nv_nvi_refcount(nvi)));
  87 }
  88
  89 static INLINE boolean
  90 nvi_isnop(struct nv_instruction *nvi)
  91 {
  92    if (nvi->opcode == NV_OP_EXPORT)
  93       return TRUE;
  94
  95    if (nvi->fixed ||
  96        nvi->is_terminator ||
  97        nvi->flags_src ||
  98        nvi->flags_def)
  99       return FALSE;
 100
 101    if (nvi->def[0]->join->reg.id < 0)
 102       return TRUE;
 103
 104    if (nvi->opcode != NV_OP_MOV && nvi->opcode != NV_OP_SELECT)
 105       return FALSE;
 106
 107    if (nvi->def[0]->reg.file != nvi->src[0]->value->reg.file)
 108       return FALSE;
 109
 110    if (nvi->src[0]->value->join->reg.id < 0) {
 111       debug_printf("nvi_isnop: orphaned value detected\n");
 112       return TRUE;
 113    }
 114
 115    if (nvi->opcode == NV_OP_SELECT)
 116       if (!values_equal(nvi->def[0], nvi->src[1]->value))
 117          return FALSE;
 118
 119    return values_equal(nvi->def[0], nvi->src[0]->value);
 120 }
 121
 122 static void
 123 nv_pc_pass_pre_emission(void *priv, struct nv_basic_block *b)
 124 {
 125    struct nv_pc *pc = (struct nv_pc *)priv;
 126    struct nv_basic_block *in;
 127    struct nv_instruction *nvi, *next;
 128    int j;
 129    uint size, n32 = 0;
 130
 131    for (j = pc->num_blocks - 1; j >= 0 && !pc->bb_list[j]->bin_size; --j);
 132    if (j >= 0) {
 133       in = pc->bb_list[j];
 134
 135       /* check for no-op branches (BRA $PC+8) */
 136       if (in->exit && in->exit->opcode == NV_OP_BRA && in->exit->target == b) {
 137          in->bin_size -= 8;
 138          pc->bin_size -= 8;
 139
 140          for (++j; j < pc->num_blocks; ++j)
 141             pc->bb_list[j]->bin_pos -= 8;
 142
 143          nv_nvi_delete(in->exit);
 144       }
 145       b->bin_pos = in->bin_pos + in->bin_size;
 146    }
 147
 148    pc->bb_list[pc->num_blocks++] = b;
 149
 150    /* visit node */
 151
 152    for (nvi = b->entry; nvi; nvi = next) {
 153       next = nvi->next;
 154       if (nvi_isnop(nvi))
 155          nv_nvi_delete(nvi);
 156    }
 157
 158    for (nvi = b->entry; nvi; nvi = next) {
 159       next = nvi->next;
 160
 161       size = nv50_inst_min_size(nvi);
 162       if (nvi->next && size < 8)
 163          ++n32;
 164       else
 165       if ((n32 & 1) && nvi->next &&
 166           nv50_inst_min_size(nvi->next) == 4 &&
 167           inst_commutation_legal(nvi, nvi->next)) {
 168          ++n32;
 169          debug_printf("permuting: ");
 170          nv_print_instruction(nvi);
 171          nv_print_instruction(nvi->next);
 172          nv_nvi_permute(nvi, nvi->next);
 173          next = nvi;
 174       } else {
 175          nvi->is_long = 1;
 176
 177          b->bin_size += n32 & 1;
 178          if (n32 & 1)
 179             nvi->prev->is_long = 1;
 180          n32 = 0;
 181       }
 182       b->bin_size += 1 + nvi->is_long;
 183    }
 184
 185    if (!b->entry) {
 186       debug_printf("block %p is now empty\n", b);
 187    } else
 188    if (!b->exit->is_long) {
 189       assert(n32);
 190       b->exit->is_long = 1;
 191       b->bin_size += 1;
 192
 193       /* might have del'd a hole tail of instructions */
 194       if (!b->exit->prev->is_long && !(n32 & 1)) {
 195          b->bin_size += 1;
 196          b->exit->prev->is_long = 1;
 197       }
 198    }
 199    assert(!b->entry || (b->exit && b->exit->is_long));
 200
 201    pc->bin_size += b->bin_size *= 4;
 202 }
 203
 204 int
 205 nv_pc_exec_pass2(struct nv_pc *pc)
 206 {
 207    debug_printf("preparing %u blocks for emission\n", pc->num_blocks);
 208
 209    pc->bb_list = CALLOC(pc->num_blocks, sizeof(struct nv_basic_block *));
 210    pc->num_blocks = 0;
 211
 212    nv_pc_pass_in_order(pc->root, nv_pc_pass_pre_emission, pc);
 213
 214    return 0;
 215 }
 216
 217 static INLINE boolean
 218 is_cmem_load(struct nv_instruction *nvi)
 219 {
 220    return (nvi->opcode == NV_OP_LDA &&
 221            nvi->src[0]->value->reg.file >= NV_FILE_MEM_C(0) &&
 222            nvi->src[0]->value->reg.file <= NV_FILE_MEM_C(15));
 223 }
 224
 225 static INLINE boolean
 226 is_smem_load(struct nv_instruction *nvi)
 227 {
 228    return (nvi->opcode == NV_OP_LDA &&
 229            (nvi->src[0]->value->reg.file == NV_FILE_MEM_S ||
 230             nvi->src[0]->value->reg.file <= NV_FILE_MEM_P));
 231 }
 232
 233 static INLINE boolean
 234 is_immd_move(struct nv_instruction *nvi)
 235 {
 236    return (nvi->opcode == NV_OP_MOV &&
 237            nvi->src[0]->value->reg.file == NV_FILE_IMM);
 238 }
 239
 240 static INLINE void
 241 check_swap_src_0_1(struct nv_instruction *nvi)
 242 {
 243    static const ubyte cc_swapped[8] = { 0, 4, 2, 6, 1, 5, 3, 7 };
 244
 245    struct nv_ref *src0 = nvi->src[0], *src1 = nvi->src[1];
 246
 247    if (!nv_op_commutative(nvi->opcode))
 248       return;
 249    assert(src0 && src1);
 250
 251    if (is_cmem_load(src0->value->insn)) {
 252       if (!is_cmem_load(src1->value->insn)) {
 253          nvi->src[0] = src1;
 254          nvi->src[1] = src0;
 255          /* debug_printf("swapping cmem load to 1\n"); */
 256       }
 257    } else
 258    if (is_smem_load(src1->value->insn)) {
 259       if (!is_smem_load(src0->value->insn)) {
 260          nvi->src[0] = src1;
 261          nvi->src[1] = src0;
 262          /* debug_printf("swapping smem load to 0\n"); */
 263       }
 264    }
 265
 266    if (nvi->opcode == NV_OP_SET && nvi->src[0] != src0)
 267       nvi->set_cond = cc_swapped[nvi->set_cond];
 268 }
 269
 270 struct nv_pass {
 271    struct nv_pc *pc;
 272    int n;
 273    void *priv;
 274 };
 275
 276 static int
 277 nv_pass_fold_stores(struct nv_pass *ctx, struct nv_basic_block *b)
 278 {
 279    struct nv_instruction *nvi, *sti;
 280    int j;
 281
 282    for (sti = b->entry; sti; sti = sti->next) {
 283       if (!sti->def[0] || sti->def[0]->reg.file != NV_FILE_OUT)
 284          continue;
 285
 286       /* only handling MOV to $oX here */
 287       if (sti->opcode != NV_OP_MOV && sti->opcode != NV_OP_STA)
 288          continue;
 289
 290       nvi = sti->src[0]->value->insn;
 291       if (!nvi || nvi->opcode == NV_OP_PHI)
 292          continue;
 293       assert(nvi->def[0] == sti->src[0]->value);
 294
 295       if (nvi->def[0]->refc > 1)
 296          continue;
 297
 298       /* cannot write to $oX when using immediate */
 299       for (j = 0; j < 4 && nvi->src[j]; ++j)
 300          if (nvi->src[j]->value->reg.file == NV_FILE_IMM)
 301             break;
 302       if (j < 4)
 303          continue;
 304
 305       nvi->def[0] = sti->def[0];
 306       sti->def[0] = NULL;
 307       nvi->fixed = sti->fixed;
 308       sti->fixed = 0;
 309    }
 310    DESCEND_ARBITRARY(j, nv_pass_fold_stores);
 311
 312    return 0;
 313 }
 314
 315 static int
 316 nv_pass_fold_loads(struct nv_pass *ctx, struct nv_basic_block *b)
 317 {
 318    struct nv_instruction *nvi, *ld;
 319    int j;
 320
 321    for (nvi = b->entry; nvi; nvi = nvi->next) {
 322       check_swap_src_0_1(nvi);
 323
 324       for (j = 0; j < 3; ++j) {
 325          if (!nvi->src[j])
 326             break;
 327          ld = nvi->src[j]->value->insn;
 328          if (!ld)
 329             continue;
 330
 331          if (is_immd_move(ld) && nv50_nvi_can_use_imm(nvi, j)) {
 332             nv_reference(ctx->pc, &nvi->src[j], ld->src[0]->value);
 333             continue;
 334          }
 335
 336          if (ld->opcode != NV_OP_LDA)
 337             continue;
 338          if (!nv50_nvi_can_load(nvi, j, ld->src[0]->value))
 339             continue;
 340
 341          if (j == 0 && ld->src[4]) /* can't load shared mem */
 342             continue;
 343
 344          /* fold it ! */ /* XXX: ref->insn */
 345          nv_reference(ctx->pc, &nvi->src[j], ld->src[0]->value);
 346          if (ld->src[4])
 347             nv_reference(ctx->pc, &nvi->src[4], ld->src[4]->value);
 348       }
 349    }
 350    DESCEND_ARBITRARY(j, nv_pass_fold_loads);
 351
 352    return 0;
 353 }
 354
 355 static int
 356 nv_pass_lower_mods(struct nv_pass *ctx, struct nv_basic_block *b)
 357 {
 358    int j;
 359    struct nv_instruction *nvi, *mi, *next;
 360    ubyte mod;
 361
 362    for (nvi = b->entry; nvi; nvi = next) {
 363       next = nvi->next;
 364       if (nvi->opcode == NV_OP_SUB) {
 365          nvi->opcode = NV_OP_ADD;
 366          nvi->src[1]->mod ^= NV_MOD_NEG;
 367       }
 368
 369       /* should not put any modifiers on NEG and ABS */
 370       assert(nvi->opcode != NV_MOD_NEG || !nvi->src[0]->mod);
 371       assert(nvi->opcode != NV_MOD_ABS || !nvi->src[0]->mod);
 372
 373       for (j = 0; j < 4; ++j) {
 374          if (!nvi->src[j])
 375             break;
 376
 377          mi = nvi->src[j]->value->insn;
 378          if (!mi)
 379             continue;
 380          if (mi->def[0]->refc > 1)
 381             continue;
 382
 383          if (mi->opcode == NV_OP_NEG) mod = NV_MOD_NEG;
 384          else
 385          if (mi->opcode == NV_OP_ABS) mod = NV_MOD_ABS;
 386          else
 387             continue;
 388
 389          if (nvi->opcode == NV_OP_ABS)
 390             mod &= ~(NV_MOD_NEG | NV_MOD_ABS);
 391          else
 392          if (nvi->opcode == NV_OP_NEG && mod == NV_MOD_NEG) {
 393             nvi->opcode = NV_OP_MOV;
 394             mod = 0;
 395          }
 396
 397          if (!(nv50_supported_src_mods(nvi->opcode, j) & mod))
 398             continue;
 399
 400          nv_reference(ctx->pc, &nvi->src[j], mi->src[0]->value);
 401
 402          nvi->src[j]->mod ^= mod;
 403       }
 404
 405       if (nvi->opcode == NV_OP_SAT) {
 406          mi = nvi->src[0]->value->insn;
 407
 408          if ((mi->opcode == NV_OP_MAD) && !mi->flags_def) {
 409             mi->saturate = 1;
 410             mi->def[0] = nvi->def[0];
 411             nv_nvi_delete(nvi);
 412          }
 413       }
 414    }
 415    DESCEND_ARBITRARY(j, nv_pass_lower_mods);
 416
 417    return 0;
 418 }
 419
 420 #define SRC_IS_MUL(s) ((s)->insn && (s)->insn->opcode == NV_OP_MUL)
 421
 422 static struct nv_value *
 423 find_immediate(struct nv_ref *ref)
 424 {
 425    struct nv_value *src;
 426
 427    if (!ref)
 428       return NULL;
 429
 430    src = ref->value;
 431    while (src->insn && src->insn->opcode == NV_OP_MOV) {
 432       assert(!src->insn->src[0]->mod);
 433       src = src->insn->src[0]->value;
 434    }
 435    return (src->reg.file == NV_FILE_IMM) ? src : NULL;
 436 }
 437
 438 static void
 439 constant_operand(struct nv_pc *pc,
 440                  struct nv_instruction *nvi, struct nv_value *val, int s)
 441 {
 442    int t = s ? 0 : 1;
 443    ubyte type;
 444
 445    if (!nvi->def[0])
 446       return;
 447    type = nvi->def[0]->reg.type;
 448
 449    switch (nvi->opcode) {
 450    case NV_OP_MUL:
 451       if ((type == NV_TYPE_F32 && val->reg.imm.f32 == 1.0f) ||
 452           (NV_TYPE_ISINT(type) && val->reg.imm.u32 == 1)) {
 453          nvi->opcode = NV_OP_MOV;
 454          nv_reference(pc, &nvi->src[s], NULL);
 455          if (!s) {
 456             nvi->src[0] = nvi->src[1];
 457             nvi->src[1] = NULL;
 458          }
 459       } else
 460       if ((type == NV_TYPE_F32 && val->reg.imm.f32 == 2.0f) ||
 461           (NV_TYPE_ISINT(type) && val->reg.imm.u32 == 2)) {
 462          nvi->opcode = NV_OP_ADD;
 463          nv_reference(pc, &nvi->src[s], nvi->src[t]->value);
 464       } else
 465       if (type == NV_TYPE_F32 && val->reg.imm.f32 == -1.0f) {
 466          nvi->opcode = NV_OP_NEG;
 467          nv_reference(pc, &nvi->src[s], NULL);
 468          nvi->src[0] = nvi->src[t];
 469          nvi->src[1] = NULL;
 470       } else
 471       if (type == NV_TYPE_F32 && val->reg.imm.f32 == -2.0f) {
 472          nvi->opcode = NV_OP_ADD;
 473          assert(!nvi->src[s]->mod);
 474          nv_reference(pc, &nvi->src[s], nvi->src[t]->value);
 475          nvi->src[t]->mod ^= NV_MOD_NEG;
 476          nvi->src[s]->mod |= NV_MOD_NEG;
 477       } else
 478       if (val->reg.imm.u32 == 0) {
 479          nvi->opcode = NV_OP_MOV;
 480          nv_reference(pc, &nvi->src[t], NULL);
 481          if (s) {
 482             nvi->src[0] = nvi->src[1];
 483             nvi->src[1] = NULL;
 484          }
 485       }
 486       break;
 487    case NV_OP_ADD:
 488       if (val->reg.imm.u32 == 0) {
 489          nvi->opcode = NV_OP_MOV;
 490          nv_reference(pc, &nvi->src[s], NULL);
 491          nvi->src[0] = nvi->src[t];
 492          nvi->src[1] = NULL;
 493       }
 494       break;
 495    default:
 496       break;
 497    }
 498 }
 499
 500 static int
 501 nv_pass_lower_arith(struct nv_pass *ctx, struct nv_basic_block *b)
 502 {
 503    struct nv_instruction *nvi, *next;
 504    int j;
 505
 506    for (nvi = b->entry; nvi; nvi = next) {
 507       struct nv_value *src0, *src1, *src;
 508       int mod;
 509
 510       next = nvi->next;
 511
 512       if ((src = find_immediate(nvi->src[0])) != NULL)
 513          constant_operand(ctx->pc, nvi, src, 0);
 514       else
 515       if ((src = find_immediate(nvi->src[1])) != NULL)
 516          constant_operand(ctx->pc, nvi, src, 1);
 517
 518       /* try to combine MUL, ADD into MAD */
 519       if (nvi->opcode != NV_OP_ADD)
 520          continue;
 521
 522       src0 = nvi->src[0]->value;
 523       src1 = nvi->src[1]->value;
 524
 525       if (SRC_IS_MUL(src0) && src0->refc == 1)
 526          src = src0;
 527       else
 528       if (SRC_IS_MUL(src1) && src1->refc == 1)
 529          src = src1;
 530       else
 531          continue;
 532
 533       nvi->opcode = NV_OP_MAD;
 534       mod = nvi->src[(src == src0) ? 0 : 1]->mod;
 535       nv_reference(ctx->pc, &nvi->src[(src == src0) ? 0 : 1], NULL);
 536       nvi->src[2] = nvi->src[(src == src0) ? 1 : 0];
 537
 538       assert(!(mod & ~NV_MOD_NEG));
 539       nvi->src[0] = new_ref(ctx->pc, src->insn->src[0]->value);
 540       nvi->src[1] = new_ref(ctx->pc, src->insn->src[1]->value);
 541       nvi->src[0]->mod = src->insn->src[0]->mod ^ mod;
 542       nvi->src[1]->mod = src->insn->src[1]->mod;
 543    }
 544    DESCEND_ARBITRARY(j, nv_pass_lower_arith);
 545
 546    return 0;
 547 }
 548
 549 /*
 550 set $r2 g f32 $r2 $r3
 551 cvt abs rn f32 $r2 s32 $r2
 552 cvt f32 $c0 # f32 $r2
 553 e $c0 bra 0x80
 554 */
 555 #if 0
 556 static int
 557 nv_pass_lower_cond(struct nv_pass *ctx, struct nv_basic_block *b)
 558 {
 559    /* XXX: easier in IR builder for now */
 560    return 0;
 561 }
 562 #endif
 563
 564 /* TODO: redundant store elimination */
 565
 566 struct load_record {
 567    struct load_record *next;
 568    uint64_t data;
 569    struct nv_value *value;
 570 };
 571
 572 #define LOAD_RECORD_POOL_SIZE 1024
 573
 574 struct nv_pass_reld_elim {
 575    struct nv_pc *pc;
 576
 577    struct load_record *imm;
 578    struct load_record *mem_s;
 579    struct load_record *mem_v;
 580    struct load_record *mem_c[16];
 581    struct load_record *mem_l;
 582
 583    struct load_record pool[LOAD_RECORD_POOL_SIZE];
 584    int alloc;
 585 };
 586
 587 static int
 588 nv_pass_reload_elim(struct nv_pass_reld_elim *ctx, struct nv_basic_block *b)
 589 {
 590    struct load_record **rec, *it;
 591    struct nv_instruction *ld, *next;
 592    uint64_t data;
 593    struct nv_value *val;
 594    int j;
 595
 596    for (ld = b->entry; ld; ld = next) {
 597       next = ld->next;
 598       if (!ld->src[0])
 599          continue;
 600       val = ld->src[0]->value;
 601       rec = NULL;
 602
 603       if (ld->opcode == NV_OP_LINTERP || ld->opcode == NV_OP_PINTERP) {
 604          data = val->reg.id;
 605          rec = &ctx->mem_v;
 606       } else
 607       if (ld->opcode == NV_OP_LDA) {
 608          data = val->reg.id;
 609          if (val->reg.file >= NV_FILE_MEM_C(0) &&
 610              val->reg.file <= NV_FILE_MEM_C(15))
 611             rec = &ctx->mem_c[val->reg.file - NV_FILE_MEM_C(0)];
 612          else
 613          if (val->reg.file == NV_FILE_MEM_S)
 614             rec = &ctx->mem_s;
 615          else
 616          if (val->reg.file == NV_FILE_MEM_L)
 617             rec = &ctx->mem_l;
 618       } else
 619       if ((ld->opcode == NV_OP_MOV) && (val->reg.file == NV_FILE_IMM)) {
 620          data = val->reg.imm.u32;
 621          rec = &ctx->imm;
 622       }
 623
 624       if (!rec || !ld->def[0]->refc)
 625          continue;
 626
 627       for (it = *rec; it; it = it->next)
 628          if (it->data == data)
 629             break;
 630
 631       if (it) {
 632          if (ld->def[0]->reg.id >= 0)
 633             it->value = ld->def[0];
 634          else
 635             nvcg_replace_value(ctx->pc, ld->def[0], it->value);
 636       } else {
 637          if (ctx->alloc == LOAD_RECORD_POOL_SIZE)
 638             continue;
 639          it = &ctx->pool[ctx->alloc++];
 640          it->next = *rec;
 641          it->data = data;
 642          it->value = ld->def[0];
 643          *rec = it;
 644       }
 645    }
 646
 647    ctx->imm = NULL;
 648    ctx->mem_s = NULL;
 649    ctx->mem_v = NULL;
 650    for (j = 0; j < 16; ++j)
 651       ctx->mem_c[j] = NULL;
 652    ctx->mem_l = NULL;
 653    ctx->alloc = 0;
 654
 655    DESCEND_ARBITRARY(j, nv_pass_reload_elim);
 656
 657    return 0;
 658 }
 659
 660 static int
 661 nv_pass_tex_mask(struct nv_pass *ctx, struct nv_basic_block *b)
 662 {
 663    int i, c, j;
 664
 665    for (i = 0; i < ctx->pc->num_instructions; ++i) {
 666       struct nv_instruction *nvi = &ctx->pc->instructions[i];
 667       struct nv_value *def[4];
 668
 669       if (!nv_is_vector_op(nvi->opcode))
 670          continue;
 671       nvi->tex_mask = 0;
 672
 673       for (c = 0; c < 4; ++c) {
 674          if (nvi->def[c]->refc)
 675             nvi->tex_mask |= 1 << c;
 676          def[c] = nvi->def[c];
 677       }
 678
 679       j = 0;
 680       for (c = 0; c < 4; ++c)
 681          if (nvi->tex_mask & (1 << c))
 682             nvi->def[j++] = def[c];
 683       for (c = 0; c < 4; ++c)
 684          if (!(nvi->tex_mask & (1 << c)))
 685            nvi->def[j++] = def[c];
 686       assert(j == 4);
 687    }
 688    return 0;
 689 }
 690
 691 struct nv_pass_dce {
 692    struct nv_pc *pc;
 693    uint removed;
 694 };
 695
 696 static int
 697 nv_pass_dce(struct nv_pass_dce *ctx, struct nv_basic_block *b)
 698 {
 699    int j;
 700    struct nv_instruction *nvi, *next;
 701
 702    for (nvi = b->entry; nvi; nvi = next) {
 703       next = nvi->next;
 704
 705       if (inst_cullable(nvi)) {
 706          nv_nvi_delete(nvi);
 707
 708          ++ctx->removed;
 709       }
 710    }
 711    DESCEND_ARBITRARY(j, nv_pass_dce);
 712
 713    return 0;
 714 }
 715
 716 static INLINE boolean
 717 bb_simple_if_endif(struct nv_basic_block *bb)
 718 {
 719    return (bb->out[0] && bb->out[1] &&
 720            bb->out[0]->out[0] == bb->out[1] &&
 721            !bb->out[0]->out[1]);
 722 }
 723
 724 static int
 725 nv_pass_flatten(struct nv_pass *ctx, struct nv_basic_block *b)
 726 {
 727    int j;
 728
 729    if (bb_simple_if_endif(b)) {
 730       ++ctx->n;
 731       debug_printf("nv_pass_flatten: total IF/ENDIF constructs: %i\n", ctx->n);
 732    }
 733    DESCEND_ARBITRARY(j, nv_pass_flatten);
 734
 735    return 0;
 736 }
 737
 738 /* local common subexpression elimination, stupid O(n^2) implementation */
 739 static int
 740 nv_pass_cse(struct nv_pass *ctx, struct nv_basic_block *b)
 741 {
 742    struct nv_instruction *ir, *ik, *next;
 743    struct nv_instruction *entry = b->phi ? b->phi : b->entry;
 744    int s;
 745    unsigned int reps;
 746
 747    do {
 748       reps = 0;
 749       for (ir = entry; ir; ir = next) {
 750          next = ir->next;
 751          for (ik = entry; ik != ir; ik = ik->next) {
 752             if (ir->opcode != ik->opcode)
 753                continue;
 754
 755             if (ik->opcode == NV_OP_LDA ||
 756                 ik->opcode == NV_OP_STA ||
 757                 ik->opcode == NV_OP_MOV ||
 758                 nv_is_vector_op(ik->opcode))
 759                continue; /* ignore loads, stores & moves */
 760
 761             if (ik->src[4] || ir->src[4])
 762                continue; /* don't mess with address registers */
 763
 764             if (ik->flags_src || ir->flags_src ||
 765                 ik->flags_def || ir->flags_def)
 766                continue; /* and also not with flags, for now */
 767
 768             for (s = 0; s < 3; ++s) {
 769                struct nv_value *a, *b;
 770
 771                if (!ik->src[s]) {
 772                   if (ir->src[s])
 773                      break;
 774                   continue;
 775                }
 776                if (ik->src[s]->mod != ir->src[s]->mod)
 777                   break;
 778                a = ik->src[s]->value;
 779                b = ir->src[s]->value;
 780                if (a == b)
 781                   continue;
 782                if (a->reg.file != b->reg.file ||
 783                    a->reg.id < 0 ||
 784                    a->reg.id != b->reg.id)
 785                   break;
 786             }
 787             if (s == 3) {
 788                nv_nvi_delete(ir);
 789                ++reps;
 790                nvcg_replace_value(ctx->pc, ir->def[0], ik->def[0]);
 791                break;
 792             }
 793          }
 794       }
 795    } while(reps);
 796
 797    DESCEND_ARBITRARY(s, nv_pass_cse);
 798
 799    return 0;
 800 }
 801
 802 int
 803 nv_pc_exec_pass0(struct nv_pc *pc)
 804 {
 805    struct nv_pass_reld_elim *reldelim;
 806    struct nv_pass pass;
 807    struct nv_pass_dce dce;
 808    int ret;
 809
 810    pass.n = 0;
 811    pass.pc = pc;
 812
 813    pc->pass_seq++;
 814    ret = nv_pass_flatten(&pass, pc->root);
 815    if (ret)
 816       return ret;
 817
 818    /* Do this first, so we don't have to pay attention
 819     * to whether sources are supported memory loads.
 820     */
 821    pc->pass_seq++;
 822    ret = nv_pass_lower_arith(&pass, pc->root);
 823    if (ret)
 824       return ret;
 825
 826    pc->pass_seq++;
 827    ret = nv_pass_fold_loads(&pass, pc->root);
 828    if (ret)
 829       return ret;
 830
 831    pc->pass_seq++;
 832    ret = nv_pass_fold_stores(&pass, pc->root);
 833    if (ret)
 834       return ret;
 835
 836    reldelim = CALLOC_STRUCT(nv_pass_reld_elim);
 837    reldelim->pc = pc;
 838    pc->pass_seq++;
 839    ret = nv_pass_reload_elim(reldelim, pc->root);
 840    FREE(reldelim);
 841    if (ret)
 842       return ret;
 843
 844    pc->pass_seq++;
 845    ret = nv_pass_cse(&pass, pc->root);
 846    if (ret)
 847       return ret;
 848
 849    pc->pass_seq++;
 850    ret = nv_pass_lower_mods(&pass, pc->root);
 851    if (ret)
 852       return ret;
 853
 854    dce.pc = pc;
 855    do {
 856       dce.removed = 0;
 857       pc->pass_seq++;
 858       ret = nv_pass_dce(&dce, pc->root);
 859       if (ret)
 860          return ret;
 861    } while (dce.removed);
 862
 863    ret = nv_pass_tex_mask(&pass, pc->root);
 864    if (ret)
 865       return ret;
 866
 867    return ret;
 868 }