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 /* #define NV50PC_DEBUG */
  24
  25 #include "nv50_pc.h"
  26
  27 #define DESCEND_ARBITRARY(j, f)                                 \
  28 do {                                                            \
  29    b->pass_seq = ctx->pc->pass_seq;                             \
  30                                                                 \
  31    for (j = 0; j < 2; ++j)                                      \
  32       if (b->out[j] && b->out[j]->pass_seq < ctx->pc->pass_seq) \
  33          f(ctx, b->out[j]);                                       \
  34 } while (0)
  35
  36 extern unsigned nv50_inst_min_size(struct nv_instruction *);
  37
  38 struct nv_pc_pass {
  39    struct nv_pc *pc;
  40 };
  41
  42 static INLINE boolean
  43 values_equal(struct nv_value *a, struct nv_value *b)
  44 {
  45    /* XXX: sizes */
  46    return (a->reg.file == b->reg.file && a->join->reg.id == b->join->reg.id);
  47 }
  48
  49 static INLINE boolean
  50 inst_commutation_check(struct nv_instruction *a,
  51                        struct nv_instruction *b)
  52 {
  53    int si, di;
  54
  55    for (di = 0; di < 4; ++di) {
  56       if (!a->def[di])
  57          break;
  58       for (si = 0; si < 5; ++si) {
  59          if (!b->src[si])
  60             continue;
  61          if (values_equal(a->def[di], b->src[si]->value))
  62             return FALSE;
  63       }
  64    }
  65
  66    if (b->flags_src && b->flags_src->value == a->flags_def)
  67       return FALSE;
  68
  69    return TRUE;
  70 }
  71
  72 /* Check whether we can swap the order of the instructions,
  73  * where a & b may be either the earlier or the later one.
  74  */
  75 static boolean
  76 inst_commutation_legal(struct nv_instruction *a,
  77                        struct nv_instruction *b)
  78 {
  79    return inst_commutation_check(a, b) && inst_commutation_check(b, a);
  80 }
  81
  82 static INLINE boolean
  83 inst_cullable(struct nv_instruction *nvi)
  84 {
  85    return (!(nvi->is_terminator || nvi->is_join ||
  86              nvi->target ||
  87              nvi->fixed ||
  88              nv_nvi_refcount(nvi)));
  89 }
  90
  91 static INLINE boolean
  92 nvi_isnop(struct nv_instruction *nvi)
  93 {
  94    if (nvi->opcode == NV_OP_EXPORT || nvi->opcode == NV_OP_UNDEF)
  95       return TRUE;
  96
  97    if (nvi->fixed ||
  98        nvi->is_terminator ||
  99        nvi->flags_src ||
 100        nvi->flags_def ||
 101        nvi->is_join)
 102       return FALSE;
 103
 104    if (nvi->def[0]->join->reg.id < 0)
 105       return TRUE;
 106
 107    if (nvi->opcode != NV_OP_MOV && nvi->opcode != NV_OP_SELECT)
 108       return FALSE;
 109
 110    if (nvi->def[0]->reg.file != nvi->src[0]->value->reg.file)
 111       return FALSE;
 112
 113    if (nvi->src[0]->value->join->reg.id < 0) {
 114       NV50_DBGMSG("nvi_isnop: orphaned value detected\n");
 115       return TRUE;
 116    }
 117
 118    if (nvi->opcode == NV_OP_SELECT)
 119       if (!values_equal(nvi->def[0], nvi->src[1]->value))
 120          return FALSE;
 121
 122    return values_equal(nvi->def[0], nvi->src[0]->value);
 123 }
 124
 125 struct nv_pass {
 126    struct nv_pc *pc;
 127    int n;
 128    void *priv;
 129 };
 130
 131 static int
 132 nv_pass_flatten(struct nv_pass *ctx, struct nv_basic_block *b);
 133
 134 static void
 135 nv_pc_pass_pre_emission(void *priv, struct nv_basic_block *b)
 136 {
 137    struct nv_pc *pc = (struct nv_pc *)priv;
 138    struct nv_basic_block *in;
 139    struct nv_instruction *nvi, *next;
 140    int j;
 141    uint size, n32 = 0;
 142
 143    for (j = pc->num_blocks - 1; j >= 0 && !pc->bb_list[j]->bin_size; --j);
 144    if (j >= 0) {
 145       in = pc->bb_list[j];
 146
 147       /* check for no-op branches (BRA $PC+8) */
 148       if (in->exit && in->exit->opcode == NV_OP_BRA && in->exit->target == b) {
 149          in->bin_size -= 8;
 150          pc->bin_size -= 8;
 151
 152          for (++j; j < pc->num_blocks; ++j)
 153             pc->bb_list[j]->bin_pos -= 8;
 154
 155          nv_nvi_delete(in->exit);
 156       }
 157       b->bin_pos = in->bin_pos + in->bin_size;
 158    }
 159
 160    pc->bb_list[pc->num_blocks++] = b;
 161
 162    /* visit node */
 163
 164    for (nvi = b->entry; nvi; nvi = next) {
 165       next = nvi->next;
 166       if (nvi_isnop(nvi))
 167          nv_nvi_delete(nvi);
 168    }
 169
 170    for (nvi = b->entry; nvi; nvi = next) {
 171       next = nvi->next;
 172
 173       size = nv50_inst_min_size(nvi);
 174       if (nvi->next && size < 8)
 175          ++n32;
 176       else
 177       if ((n32 & 1) && nvi->next &&
 178           nv50_inst_min_size(nvi->next) == 4 &&
 179           inst_commutation_legal(nvi, nvi->next)) {
 180          ++n32;
 181          nv_nvi_permute(nvi, nvi->next);
 182          next = nvi;
 183       } else {
 184          nvi->is_long = 1;
 185
 186          b->bin_size += n32 & 1;
 187          if (n32 & 1)
 188             nvi->prev->is_long = 1;
 189          n32 = 0;
 190       }
 191       b->bin_size += 1 + nvi->is_long;
 192    }
 193
 194    if (!b->entry) {
 195       NV50_DBGMSG("block %p is now empty\n", b);
 196    } else
 197    if (!b->exit->is_long) {
 198       assert(n32);
 199       b->exit->is_long = 1;
 200       b->bin_size += 1;
 201
 202       /* might have del'd a hole tail of instructions */
 203       if (!b->exit->prev->is_long && !(n32 & 1)) {
 204          b->bin_size += 1;
 205          b->exit->prev->is_long = 1;
 206       }
 207    }
 208    assert(!b->entry || (b->exit && b->exit->is_long));
 209
 210    pc->bin_size += b->bin_size *= 4;
 211 }
 212
 213 int
 214 nv_pc_exec_pass2(struct nv_pc *pc)
 215 {
 216    struct nv_pass pass;
 217
 218    pass.pc = pc;
 219
 220    pc->pass_seq++;
 221    nv_pass_flatten(&pass, pc->root);
 222
 223    NV50_DBGMSG("preparing %u blocks for emission\n", pc->num_blocks);
 224
 225    pc->bb_list = CALLOC(pc->num_blocks, sizeof(struct nv_basic_block *));
 226    pc->num_blocks = 0;
 227
 228    nv_pc_pass_in_order(pc->root, nv_pc_pass_pre_emission, pc);
 229
 230    return 0;
 231 }
 232
 233 static INLINE boolean
 234 is_cmem_load(struct nv_instruction *nvi)
 235 {
 236    return (nvi->opcode == NV_OP_LDA &&
 237            nvi->src[0]->value->reg.file >= NV_FILE_MEM_C(0) &&
 238            nvi->src[0]->value->reg.file <= NV_FILE_MEM_C(15));
 239 }
 240
 241 static INLINE boolean
 242 is_smem_load(struct nv_instruction *nvi)
 243 {
 244    return (nvi->opcode == NV_OP_LDA &&
 245            (nvi->src[0]->value->reg.file == NV_FILE_MEM_S ||
 246             nvi->src[0]->value->reg.file <= NV_FILE_MEM_P));
 247 }
 248
 249 static INLINE boolean
 250 is_immd_move(struct nv_instruction *nvi)
 251 {
 252    return (nvi->opcode == NV_OP_MOV &&
 253            nvi->src[0]->value->reg.file == NV_FILE_IMM);
 254 }
 255
 256 static INLINE void
 257 check_swap_src_0_1(struct nv_instruction *nvi)
 258 {
 259    static const ubyte cc_swapped[8] = { 0, 4, 2, 6, 1, 5, 3, 7 };
 260
 261    struct nv_ref *src0 = nvi->src[0], *src1 = nvi->src[1];
 262
 263    if (!nv_op_commutative(nvi->opcode))
 264       return;
 265    assert(src0 && src1);
 266
 267    if (src1->value->reg.file == NV_FILE_IMM)
 268       return;
 269
 270    if (is_cmem_load(src0->value->insn)) {
 271       if (!is_cmem_load(src1->value->insn)) {
 272          nvi->src[0] = src1;
 273          nvi->src[1] = src0;
 274          /* debug_printf("swapping cmem load to 1\n"); */
 275       }
 276    } else
 277    if (is_smem_load(src1->value->insn)) {
 278       if (!is_smem_load(src0->value->insn)) {
 279          nvi->src[0] = src1;
 280          nvi->src[1] = src0;
 281          /* debug_printf("swapping smem load to 0\n"); */
 282       }
 283    }
 284
 285    if (nvi->opcode == NV_OP_SET && nvi->src[0] != src0)
 286       nvi->set_cond = cc_swapped[nvi->set_cond];
 287 }
 288
 289 static int
 290 nv_pass_fold_stores(struct nv_pass *ctx, struct nv_basic_block *b)
 291 {
 292    struct nv_instruction *nvi, *sti, *next;
 293    int j;
 294
 295    for (sti = b->entry; sti; sti = next) {
 296       next = sti->next;
 297
 298       /* only handling MOV to $oX here */
 299       if (!sti->def[0] || sti->def[0]->reg.file != NV_FILE_OUT)
 300          continue;
 301       if (sti->opcode != NV_OP_MOV && sti->opcode != NV_OP_STA)
 302          continue;
 303
 304       nvi = sti->src[0]->value->insn;
 305       if (!nvi || nvi->opcode == NV_OP_PHI || nv_is_vector_op(nvi->opcode))
 306          continue;
 307       assert(nvi->def[0] == sti->src[0]->value);
 308
 309       if (nvi->def[0]->refc > 1)
 310          continue;
 311
 312       /* cannot write to $oX when using immediate */
 313       for (j = 0; j < 4 && nvi->src[j]; ++j)
 314          if (nvi->src[j]->value->reg.file == NV_FILE_IMM)
 315             break;
 316       if (j < 4 && nvi->src[j])
 317          continue;
 318
 319       nvi->def[0] = sti->def[0];
 320       nvi->fixed = sti->fixed;
 321
 322       nv_nvi_delete(sti);
 323    }
 324    DESCEND_ARBITRARY(j, nv_pass_fold_stores);
 325
 326    return 0;
 327 }
 328
 329 static int
 330 nv_pass_fold_loads(struct nv_pass *ctx, struct nv_basic_block *b)
 331 {
 332    struct nv_instruction *nvi, *ld;
 333    int j;
 334
 335    for (nvi = b->entry; nvi; nvi = nvi->next) {
 336       check_swap_src_0_1(nvi);
 337
 338       for (j = 0; j < 3; ++j) {
 339          if (!nvi->src[j])
 340             break;
 341          ld = nvi->src[j]->value->insn;
 342          if (!ld)
 343             continue;
 344
 345          if (is_immd_move(ld) && nv50_nvi_can_use_imm(nvi, j)) {
 346             nv_reference(ctx->pc, &nvi->src[j], ld->src[0]->value);
 347             continue;
 348          }
 349
 350          if (ld->opcode != NV_OP_LDA)
 351             continue;
 352          if (!nv50_nvi_can_load(nvi, j, ld->src[0]->value))
 353             continue;
 354
 355          if (j == 0 && ld->src[4]) /* can't load shared mem */
 356             continue;
 357
 358          /* fold it ! */ /* XXX: ref->insn */
 359          nv_reference(ctx->pc, &nvi->src[j], ld->src[0]->value);
 360          if (ld->src[4])
 361             nv_reference(ctx->pc, &nvi->src[4], ld->src[4]->value);
 362
 363          if (!nv_nvi_refcount(ld))
 364             nv_nvi_delete(ld);
 365       }
 366    }
 367    DESCEND_ARBITRARY(j, nv_pass_fold_loads);
 368
 369    return 0;
 370 }
 371
 372 static int
 373 nv_pass_lower_mods(struct nv_pass *ctx, struct nv_basic_block *b)
 374 {
 375    int j;
 376    struct nv_instruction *nvi, *mi, *next;
 377    ubyte mod;
 378
 379    for (nvi = b->entry; nvi; nvi = next) {
 380       next = nvi->next;
 381       if (nvi->opcode == NV_OP_SUB) {
 382          nvi->opcode = NV_OP_ADD;
 383          nvi->src[1]->mod ^= NV_MOD_NEG;
 384       }
 385
 386       /* should not put any modifiers on NEG and ABS */
 387       assert(nvi->opcode != NV_MOD_NEG || !nvi->src[0]->mod);
 388       assert(nvi->opcode != NV_MOD_ABS || !nvi->src[0]->mod);
 389
 390       for (j = 0; j < 4; ++j) {
 391          if (!nvi->src[j])
 392             break;
 393
 394          mi = nvi->src[j]->value->insn;
 395          if (!mi)
 396             continue;
 397          if (mi->def[0]->refc > 1)
 398             continue;
 399
 400          if (mi->opcode == NV_OP_NEG) mod = NV_MOD_NEG;
 401          else
 402          if (mi->opcode == NV_OP_ABS) mod = NV_MOD_ABS;
 403          else
 404             continue;
 405
 406          if (nvi->opcode == NV_OP_ABS)
 407             mod &= ~(NV_MOD_NEG | NV_MOD_ABS);
 408          else
 409          if (nvi->opcode == NV_OP_NEG && mod == NV_MOD_NEG) {
 410             nvi->opcode = NV_OP_MOV;
 411             mod = 0;
 412          }
 413
 414          if (!(nv50_supported_src_mods(nvi->opcode, j) & mod))
 415             continue;
 416
 417          nv_reference(ctx->pc, &nvi->src[j], mi->src[0]->value);
 418
 419          nvi->src[j]->mod ^= mod;
 420       }
 421
 422       if (nvi->opcode == NV_OP_SAT) {
 423          mi = nvi->src[0]->value->insn;
 424
 425          if ((mi->opcode == NV_OP_MAD) && !mi->flags_def) {
 426             mi->saturate = 1;
 427             mi->def[0] = nvi->def[0];
 428             nv_nvi_delete(nvi);
 429          }
 430       }
 431    }
 432    DESCEND_ARBITRARY(j, nv_pass_lower_mods);
 433
 434    return 0;
 435 }
 436
 437 #define SRC_IS_MUL(s) ((s)->insn && (s)->insn->opcode == NV_OP_MUL)
 438
 439 static struct nv_value *
 440 find_immediate(struct nv_ref *ref)
 441 {
 442    struct nv_value *src;
 443
 444    if (!ref)
 445       return NULL;
 446
 447    src = ref->value;
 448    while (src->insn && src->insn->opcode == NV_OP_MOV) {
 449       assert(!src->insn->src[0]->mod);
 450       src = src->insn->src[0]->value;
 451    }
 452    return (src->reg.file == NV_FILE_IMM) ? src : NULL;
 453 }
 454
 455 static void
 456 modifiers_apply(uint32_t *val, ubyte type, ubyte mod)
 457 {
 458    if (mod & NV_MOD_ABS) {
 459       if (type == NV_TYPE_F32)
 460          *val &= 0x7fffffff;
 461       else
 462       if ((*val) & (1 << 31))
 463          *val = ~(*val) + 1;
 464    }
 465    if (mod & NV_MOD_NEG) {
 466       if (type == NV_TYPE_F32)
 467          *val ^= 0x80000000;
 468       else
 469          *val = ~(*val) + 1;
 470    }
 471 }
 472
 473 static INLINE uint
 474 modifiers_opcode(ubyte mod)
 475 {
 476    switch (mod) {
 477    case NV_MOD_NEG: return NV_OP_NEG;
 478    case NV_MOD_ABS: return NV_OP_ABS;
 479    case 0:
 480       return NV_OP_MOV;
 481    default:
 482       return NV_OP_NOP;
 483    }
 484 }
 485
 486 static void
 487 constant_expression(struct nv_pc *pc, struct nv_instruction *nvi,
 488                     struct nv_value *src0, struct nv_value *src1)
 489 {
 490    struct nv_value *val;
 491    union {
 492       float f32;
 493       uint32_t u32;
 494       int32_t s32;
 495    } u0, u1, u;
 496    ubyte type;
 497
 498    if (!nvi->def[0])
 499       return;
 500    type = nvi->def[0]->reg.type;
 501
 502    u.u32 = 0;
 503    u0.u32 = src0->reg.imm.u32;
 504    u1.u32 = src1->reg.imm.u32;
 505
 506    modifiers_apply(&u0.u32, type, nvi->src[0]->mod);
 507    modifiers_apply(&u1.u32, type, nvi->src[1]->mod);
 508
 509    switch (nvi->opcode) {
 510    case NV_OP_MAD:
 511       if (nvi->src[2]->value->reg.file != NV_FILE_GPR)
 512          return;
 513       /* fall through */
 514    case NV_OP_MUL:
 515       switch (type) {
 516       case NV_TYPE_F32: u.f32 = u0.f32 * u1.f32; break;
 517       case NV_TYPE_U32: u.u32 = u0.u32 * u1.u32; break;
 518       case NV_TYPE_S32: u.s32 = u0.s32 * u1.s32; break;
 519       default:
 520          assert(0);
 521          break;
 522       }
 523       break;
 524    case NV_OP_ADD:
 525       switch (type) {
 526       case NV_TYPE_F32: u.f32 = u0.f32 + u1.f32; break;
 527       case NV_TYPE_U32: u.u32 = u0.u32 + u1.u32; break;
 528       case NV_TYPE_S32: u.s32 = u0.s32 + u1.s32; break;
 529       default:
 530          assert(0);
 531          break;
 532       }
 533       break;
 534    case NV_OP_SUB:
 535       switch (type) {
 536       case NV_TYPE_F32: u.f32 = u0.f32 - u1.f32; break;
 537       case NV_TYPE_U32: u.u32 = u0.u32 - u1.u32; break;
 538       case NV_TYPE_S32: u.s32 = u0.s32 - u1.s32; break;
 539       default:
 540          assert(0);
 541          break;
 542       }
 543       break;
 544    default:
 545       return;
 546    }
 547
 548    nvi->opcode = NV_OP_MOV;
 549
 550    val = new_value(pc, NV_FILE_IMM, type);
 551
 552    val->reg.imm.u32 = u.u32;
 553
 554    nv_reference(pc, &nvi->src[1], NULL);
 555    nv_reference(pc, &nvi->src[0], val);
 556
 557    if (nvi->src[2]) { /* from MAD */
 558       nvi->src[1] = nvi->src[0];
 559       nvi->src[0] = nvi->src[2];
 560       nvi->src[2] = NULL;
 561       nvi->opcode = NV_OP_ADD;
 562    }
 563 }
 564
 565 static void
 566 constant_operand(struct nv_pc *pc,
 567                  struct nv_instruction *nvi, struct nv_value *val, int s)
 568 {
 569    union {
 570       float f32;
 571       uint32_t u32;
 572       int32_t s32;
 573    } u;
 574    int t = s ? 0 : 1;
 575    uint op;
 576    ubyte type;
 577
 578    if (!nvi->def[0])
 579       return;
 580    type = nvi->def[0]->reg.type;
 581
 582    u.u32 = val->reg.imm.u32;
 583    modifiers_apply(&u.u32, type, nvi->src[s]->mod);
 584
 585    switch (nvi->opcode) {
 586    case NV_OP_MUL:
 587       if ((type == NV_TYPE_F32 && u.f32 == 1.0f) ||
 588           (NV_TYPE_ISINT(type) && u.u32 == 1)) {
 589          if ((op = modifiers_opcode(nvi->src[t]->mod)) == NV_OP_NOP)
 590             break;
 591          nvi->opcode = op;
 592          nv_reference(pc, &nvi->src[s], NULL);
 593          nvi->src[0] = nvi->src[t];
 594          nvi->src[1] = NULL;
 595       } else
 596       if ((type == NV_TYPE_F32 && u.f32 == 2.0f) ||
 597           (NV_TYPE_ISINT(type) && u.u32 == 2)) {
 598          nvi->opcode = NV_OP_ADD;
 599          nv_reference(pc, &nvi->src[s], nvi->src[t]->value);
 600          nvi->src[s]->mod = nvi->src[t]->mod;
 601       } else
 602       if (type == NV_TYPE_F32 && u.f32 == -1.0f) {
 603          if (nvi->src[t]->mod & NV_MOD_NEG)
 604             nvi->opcode = NV_OP_MOV;
 605          else
 606             nvi->opcode = NV_OP_NEG;
 607          nv_reference(pc, &nvi->src[s], NULL);
 608          nvi->src[0] = nvi->src[t];
 609          nvi->src[1] = NULL;
 610       } else
 611       if (type == NV_TYPE_F32 && u.f32 == -2.0f) {
 612          nvi->opcode = NV_OP_ADD;
 613          nv_reference(pc, &nvi->src[s], nvi->src[t]->value);
 614          nvi->src[s]->mod = (nvi->src[t]->mod ^= NV_MOD_NEG);
 615       } else
 616       if (u.u32 == 0) {
 617          nvi->opcode = NV_OP_MOV;
 618          nv_reference(pc, &nvi->src[t], NULL);
 619          if (s) {
 620             nvi->src[0] = nvi->src[1];
 621             nvi->src[1] = NULL;
 622          }
 623       }
 624       break;
 625    case NV_OP_ADD:
 626       if (u.u32 == 0) {
 627          if ((op = modifiers_opcode(nvi->src[t]->mod)) == NV_OP_NOP)
 628             break;
 629          nvi->opcode = op;
 630          nv_reference(pc, &nvi->src[s], NULL);
 631          nvi->src[0] = nvi->src[t];
 632          nvi->src[1] = NULL;
 633       }
 634       break;
 635    case NV_OP_RCP:
 636       u.f32 = 1.0f / u.f32;
 637       (val = new_value(pc, NV_FILE_IMM, NV_TYPE_F32))->reg.imm.f32 = u.f32;
 638       nvi->opcode = NV_OP_MOV;
 639       assert(s == 0);
 640       nv_reference(pc, &nvi->src[0], val);
 641       break;
 642    case NV_OP_RSQ:
 643       u.f32 = 1.0f / sqrtf(u.f32);
 644       (val = new_value(pc, NV_FILE_IMM, NV_TYPE_F32))->reg.imm.f32 = u.f32;
 645       nvi->opcode = NV_OP_MOV;
 646       assert(s == 0);
 647       nv_reference(pc, &nvi->src[0], val);
 648       break;
 649    default:
 650       break;
 651    }
 652 }
 653
 654 static int
 655 nv_pass_lower_arith(struct nv_pass *ctx, struct nv_basic_block *b)
 656 {
 657    struct nv_instruction *nvi, *next;
 658    int j;
 659
 660    for (nvi = b->entry; nvi; nvi = next) {
 661       struct nv_value *src0, *src1, *src;
 662       int mod;
 663
 664       next = nvi->next;
 665
 666       src0 = find_immediate(nvi->src[0]);
 667       src1 = find_immediate(nvi->src[1]);
 668
 669       if (src0 && src1)
 670          constant_expression(ctx->pc, nvi, src0, src1);
 671       else {
 672          if (src0)
 673             constant_operand(ctx->pc, nvi, src0, 0);
 674          else
 675          if (src1)
 676             constant_operand(ctx->pc, nvi, src1, 1);
 677       }
 678
 679       /* try to combine MUL, ADD into MAD */
 680       if (nvi->opcode != NV_OP_ADD)
 681          continue;
 682
 683       src0 = nvi->src[0]->value;
 684       src1 = nvi->src[1]->value;
 685
 686       if (SRC_IS_MUL(src0) && src0->refc == 1)
 687          src = src0;
 688       else
 689       if (SRC_IS_MUL(src1) && src1->refc == 1)
 690          src = src1;
 691       else
 692          continue;
 693
 694       nvi->opcode = NV_OP_MAD;
 695       mod = nvi->src[(src == src0) ? 0 : 1]->mod;
 696       nv_reference(ctx->pc, &nvi->src[(src == src0) ? 0 : 1], NULL);
 697       nvi->src[2] = nvi->src[(src == src0) ? 1 : 0];
 698
 699       assert(!(mod & ~NV_MOD_NEG));
 700       nvi->src[0] = new_ref(ctx->pc, src->insn->src[0]->value);
 701       nvi->src[1] = new_ref(ctx->pc, src->insn->src[1]->value);
 702       nvi->src[0]->mod = src->insn->src[0]->mod ^ mod;
 703       nvi->src[1]->mod = src->insn->src[1]->mod;
 704    }
 705    DESCEND_ARBITRARY(j, nv_pass_lower_arith);
 706
 707    return 0;
 708 }
 709
 710 /* TODO: redundant store elimination */
 711
 712 struct load_record {
 713    struct load_record *next;
 714    uint64_t data;
 715    struct nv_value *value;
 716 };
 717
 718 #define LOAD_RECORD_POOL_SIZE 1024
 719
 720 struct nv_pass_reld_elim {
 721    struct nv_pc *pc;
 722
 723    struct load_record *imm;
 724    struct load_record *mem_s;
 725    struct load_record *mem_v;
 726    struct load_record *mem_c[16];
 727    struct load_record *mem_l;
 728
 729    struct load_record pool[LOAD_RECORD_POOL_SIZE];
 730    int alloc;
 731 };
 732
 733 static int
 734 nv_pass_reload_elim(struct nv_pass_reld_elim *ctx, struct nv_basic_block *b)
 735 {
 736    struct load_record **rec, *it;
 737    struct nv_instruction *ld, *next;
 738    uint64_t data;
 739    struct nv_value *val;
 740    int j;
 741
 742    for (ld = b->entry; ld; ld = next) {
 743       next = ld->next;
 744       if (!ld->src[0])
 745          continue;
 746       val = ld->src[0]->value;
 747       rec = NULL;
 748
 749       if (ld->opcode == NV_OP_LINTERP || ld->opcode == NV_OP_PINTERP) {
 750          data = val->reg.id;
 751          rec = &ctx->mem_v;
 752       } else
 753       if (ld->opcode == NV_OP_LDA) {
 754          data = val->reg.id;
 755          if (val->reg.file >= NV_FILE_MEM_C(0) &&
 756              val->reg.file <= NV_FILE_MEM_C(15))
 757             rec = &ctx->mem_c[val->reg.file - NV_FILE_MEM_C(0)];
 758          else
 759          if (val->reg.file == NV_FILE_MEM_S)
 760             rec = &ctx->mem_s;
 761          else
 762          if (val->reg.file == NV_FILE_MEM_L)
 763             rec = &ctx->mem_l;
 764       } else
 765       if ((ld->opcode == NV_OP_MOV) && (val->reg.file == NV_FILE_IMM)) {
 766          data = val->reg.imm.u32;
 767          rec = &ctx->imm;
 768       }
 769
 770       if (!rec || !ld->def[0]->refc)
 771          continue;
 772
 773       for (it = *rec; it; it = it->next)
 774          if (it->data == data)
 775             break;
 776
 777       if (it) {
 778          if (ld->def[0]->reg.id >= 0)
 779             it->value = ld->def[0];
 780          else
 781             nvcg_replace_value(ctx->pc, ld->def[0], it->value);
 782       } else {
 783          if (ctx->alloc == LOAD_RECORD_POOL_SIZE)
 784             continue;
 785          it = &ctx->pool[ctx->alloc++];
 786          it->next = *rec;
 787          it->data = data;
 788          it->value = ld->def[0];
 789          *rec = it;
 790       }
 791    }
 792
 793    ctx->imm = NULL;
 794    ctx->mem_s = NULL;
 795    ctx->mem_v = NULL;
 796    for (j = 0; j < 16; ++j)
 797       ctx->mem_c[j] = NULL;
 798    ctx->mem_l = NULL;
 799    ctx->alloc = 0;
 800
 801    DESCEND_ARBITRARY(j, nv_pass_reload_elim);
 802
 803    return 0;
 804 }
 805
 806 static int
 807 nv_pass_tex_mask(struct nv_pass *ctx, struct nv_basic_block *b)
 808 {
 809    int i, c, j;
 810
 811    for (i = 0; i < ctx->pc->num_instructions; ++i) {
 812       struct nv_instruction *nvi = &ctx->pc->instructions[i];
 813       struct nv_value *def[4];
 814
 815       if (!nv_is_vector_op(nvi->opcode))
 816          continue;
 817       nvi->tex_mask = 0;
 818
 819       for (c = 0; c < 4; ++c) {
 820          if (nvi->def[c]->refc)
 821             nvi->tex_mask |= 1 << c;
 822          def[c] = nvi->def[c];
 823       }
 824
 825       j = 0;
 826       for (c = 0; c < 4; ++c)
 827          if (nvi->tex_mask & (1 << c))
 828             nvi->def[j++] = def[c];
 829       for (c = 0; c < 4; ++c)
 830          if (!(nvi->tex_mask & (1 << c)))
 831            nvi->def[j++] = def[c];
 832       assert(j == 4);
 833    }
 834    return 0;
 835 }
 836
 837 struct nv_pass_dce {
 838    struct nv_pc *pc;
 839    uint removed;
 840 };
 841
 842 static int
 843 nv_pass_dce(struct nv_pass_dce *ctx, struct nv_basic_block *b)
 844 {
 845    int j;
 846    struct nv_instruction *nvi, *next;
 847
 848    for (nvi = b->phi ? b->phi : b->entry; nvi; nvi = next) {
 849       next = nvi->next;
 850
 851       if (inst_cullable(nvi)) {
 852          nv_nvi_delete(nvi);
 853
 854          ++ctx->removed;
 855       }
 856    }
 857    DESCEND_ARBITRARY(j, nv_pass_dce);
 858
 859    return 0;
 860 }
 861
 862 /* Register allocation inserted ELSE blocks for all IF/ENDIF without ELSE.
 863  * Returns TRUE if @bb initiates an IF/ELSE/ENDIF clause, or is an IF with
 864  * BREAK and dummy ELSE block.
 865  */
 866 static INLINE boolean
 867 bb_is_if_else_endif(struct nv_basic_block *bb)
 868 {
 869    if (!bb->out[0] || !bb->out[1])
 870       return FALSE;
 871
 872    if (bb->out[0]->out_kind[0] == CFG_EDGE_LOOP_LEAVE) {
 873       return (bb->out[0]->out[1] == bb->out[1]->out[0] &&
 874               !bb->out[1]->out[1]);
 875    } else {
 876       return (bb->out[0]->out[0] == bb->out[1]->out[0] &&
 877               !bb->out[0]->out[1] &&
 878               !bb->out[1]->out[1]);
 879    }
 880 }
 881
 882 /* predicate instructions and remove branch at the end */
 883 static void
 884 predicate_instructions(struct nv_pc *pc, struct nv_basic_block *b,
 885                        struct nv_value *p, ubyte cc)
 886 {
 887    struct nv_instruction *nvi;
 888
 889    if (!b->entry)
 890       return;
 891    for (nvi = b->entry; nvi->next; nvi = nvi->next) {
 892       if (!nvi_isnop(nvi)) {
 893          nvi->cc = cc;
 894          nv_reference(pc, &nvi->flags_src, p);
 895       }
 896    }
 897
 898    if (nvi->opcode == NV_OP_BRA)
 899       nv_nvi_delete(nvi);
 900    else
 901    if (!nvi_isnop(nvi)) {
 902       nvi->cc = cc;
 903       nv_reference(pc, &nvi->flags_src, p);
 904    }
 905 }
 906
 907 /* NOTE: Run this after register allocation, we can just cut out the cflow
 908  * instructions and hook the predicates to the conditional OPs if they are
 909  * not using immediates; better than inserting SELECT to join definitions.
 910  *
 911  * NOTE: Should adapt prior optimization to make this possible more often.
 912  */
 913 static int
 914 nv_pass_flatten(struct nv_pass *ctx, struct nv_basic_block *b)
 915 {
 916    struct nv_instruction *nvi;
 917    struct nv_value *pred;
 918    int i;
 919    int n0 = 0, n1 = 0;
 920
 921    if (bb_is_if_else_endif(b)) {
 922
 923       NV50_DBGMSG("pass_flatten: IF/ELSE/ENDIF construct at BB:%i\n", b->id);
 924
 925       for (n0 = 0, nvi = b->out[0]->entry; nvi; nvi = nvi->next, ++n0)
 926          if (!nv50_nvi_can_predicate(nvi))
 927             break;
 928       if (!nvi) {
 929          for (n1 = 0, nvi = b->out[1]->entry; nvi; nvi = nvi->next, ++n1)
 930             if (!nv50_nvi_can_predicate(nvi))
 931                break;
 932 #ifdef NV50_PC_DEBUG
 933          if (nvi) {
 934             debug_printf("cannot predicate: "); nv_print_instruction(nvi);
 935          }
 936       } else {
 937          debug_printf("cannot predicate: "); nv_print_instruction(nvi);
 938 #endif
 939       }
 940
 941       if (!nvi && n0 < 12 && n1 < 12) { /* 12 as arbitrary limit */
 942          assert(b->exit && b->exit->flags_src);
 943          pred = b->exit->flags_src->value;
 944
 945          predicate_instructions(ctx->pc, b->out[0], pred, NV_CC_NE | NV_CC_U);
 946          predicate_instructions(ctx->pc, b->out[1], pred, NV_CC_EQ);
 947
 948          assert(b->exit && b->exit->opcode == NV_OP_BRA);
 949          nv_nvi_delete(b->exit);
 950
 951          if (b->exit && b->exit->opcode == NV_OP_JOINAT)
 952             nv_nvi_delete(b->exit);
 953
 954          i = (b->out[0]->out_kind[0] == CFG_EDGE_LOOP_LEAVE) ? 1 : 0;
 955
 956          if ((nvi = b->out[0]->out[i]->entry)) {
 957             nvi->is_join = 0;
 958             if (nvi->opcode == NV_OP_JOIN)
 959                nv_nvi_delete(nvi);
 960          }
 961       }
 962    }
 963    DESCEND_ARBITRARY(i, nv_pass_flatten);
 964
 965    return 0;
 966 }
 967
 968 /* local common subexpression elimination, stupid O(n^2) implementation */
 969 static int
 970 nv_pass_cse(struct nv_pass *ctx, struct nv_basic_block *b)
 971 {
 972    struct nv_instruction *ir, *ik, *next;
 973    struct nv_instruction *entry = b->phi ? b->phi : b->entry;
 974    int s;
 975    unsigned int reps;
 976
 977    do {
 978       reps = 0;
 979       for (ir = entry; ir; ir = next) {
 980          next = ir->next;
 981          for (ik = entry; ik != ir; ik = ik->next) {
 982             if (ir->opcode != ik->opcode)
 983                continue;
 984
 985             if (!ir->def[0] || !ik->def[0] ||
 986                 ik->opcode == NV_OP_LDA ||
 987                 ik->opcode == NV_OP_STA ||
 988                 ik->opcode == NV_OP_MOV ||
 989                 nv_is_vector_op(ik->opcode))
 990                continue; /* ignore loads, stores & moves */
 991
 992             if (ik->src[4] || ir->src[4])
 993                continue; /* don't mess with address registers */
 994
 995             if (ik->flags_src || ir->flags_src ||
 996                 ik->flags_def || ir->flags_def)
 997                continue; /* and also not with flags, for now */
 998
 999             if (ik->def[0]->reg.file == NV_FILE_OUT ||
1000                 ir->def[0]->reg.file == NV_FILE_OUT ||
1001                 !values_equal(ik->def[0], ir->def[0]))
1002                continue;
1003
1004             for (s = 0; s < 3; ++s) {
1005                struct nv_value *a, *b;
1006
1007                if (!ik->src[s]) {
1008                   if (ir->src[s])
1009                      break;
1010                   continue;
1011                }
1012                if (ik->src[s]->mod != ir->src[s]->mod)
1013                   break;
1014                a = ik->src[s]->value;
1015                b = ir->src[s]->value;
1016                if (a == b)
1017                   continue;
1018                if (a->reg.file != b->reg.file ||
1019                    a->reg.id < 0 ||
1020                    a->reg.id != b->reg.id)
1021                   break;
1022             }
1023             if (s == 3) {
1024                nv_nvi_delete(ir);
1025                ++reps;
1026                nvcg_replace_value(ctx->pc, ir->def[0], ik->def[0]);
1027                break;
1028             }
1029          }
1030       }
1031    } while(reps);
1032
1033    DESCEND_ARBITRARY(s, nv_pass_cse);
1034
1035    return 0;
1036 }
1037
1038 int
1039 nv_pc_exec_pass0(struct nv_pc *pc)
1040 {
1041    struct nv_pass_reld_elim *reldelim;
1042    struct nv_pass pass;
1043    struct nv_pass_dce dce;
1044    int ret;
1045
1046    pass.n = 0;
1047    pass.pc = pc;
1048
1049    /* Do this first, so we don't have to pay attention
1050     * to whether sources are supported memory loads.
1051     */
1052    pc->pass_seq++;
1053    ret = nv_pass_lower_arith(&pass, pc->root);
1054    if (ret)
1055       return ret;
1056
1057    pc->pass_seq++;
1058    ret = nv_pass_fold_loads(&pass, pc->root);
1059    if (ret)
1060       return ret;
1061
1062    pc->pass_seq++;
1063    ret = nv_pass_fold_stores(&pass, pc->root);
1064    if (ret)
1065       return ret;
1066
1067    reldelim = CALLOC_STRUCT(nv_pass_reld_elim);
1068    reldelim->pc = pc;
1069    pc->pass_seq++;
1070    ret = nv_pass_reload_elim(reldelim, pc->root);
1071    FREE(reldelim);
1072    if (ret)
1073       return ret;
1074
1075    pc->pass_seq++;
1076    ret = nv_pass_cse(&pass, pc->root);
1077    if (ret)
1078       return ret;
1079
1080    pc->pass_seq++;
1081    ret = nv_pass_lower_mods(&pass, pc->root);
1082    if (ret)
1083       return ret;
1084
1085    dce.pc = pc;
1086    do {
1087       dce.removed = 0;
1088       pc->pass_seq++;
1089       ret = nv_pass_dce(&dce, pc->root);
1090       if (ret)
1091          return ret;
1092    } while (dce.removed);
1093
1094    ret = nv_pass_tex_mask(&pass, pc->root);
1095    if (ret)
1096       return ret;
1097
1098    return ret;
1099 }