src/gallium/drivers/nouveau/codegen/nv50_ir_peephole.cpp

   1 /*
   2  * Copyright 2011 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 OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  18  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  19  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  20  * OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #include "codegen/nv50_ir.h"
  24 #include "codegen/nv50_ir_target.h"
  25 #include "codegen/nv50_ir_build_util.h"
  26
  27 extern "C" {
  28 #include "util/u_math.h"
  29 }
  30
  31 namespace nv50_ir {
  32
  33 bool
  34 Instruction::isNop() const
  35 {
  36    if (op == OP_PHI || op == OP_SPLIT || op == OP_MERGE || op == OP_CONSTRAINT)
  37       return true;
  38    if (terminator || join) // XXX: should terminator imply flow ?
  39       return false;
  40    if (op == OP_ATOM)
  41       return false;
  42    if (!fixed && op == OP_NOP)
  43       return true;
  44
  45    if (defExists(0) && def(0).rep()->reg.data.id < 0) {
  46       for (int d = 1; defExists(d); ++d)
  47          if (def(d).rep()->reg.data.id >= 0)
  48             WARN("part of vector result is unused !\n");
  49       return true;
  50    }
  51
  52    if (op == OP_MOV || op == OP_UNION) {
  53       if (!getDef(0)->equals(getSrc(0)))
  54          return false;
  55       if (op == OP_UNION)
  56          if (!def(0).rep()->equals(getSrc(1)))
  57             return false;
  58       return true;
  59    }
  60
  61    return false;
  62 }
  63
  64 bool Instruction::isDead() const
  65 {
  66    if (op == OP_STORE ||
  67        op == OP_EXPORT ||
  68        op == OP_ATOM ||
  69        op == OP_SUSTB || op == OP_SUSTP || op == OP_SUREDP || op == OP_SUREDB ||
  70        op == OP_WRSV)
  71       return false;
  72
  73    for (int d = 0; defExists(d); ++d)
  74       if (getDef(d)->refCount() || getDef(d)->reg.data.id >= 0)
  75          return false;
  76
  77    if (terminator || asFlow())
  78       return false;
  79    if (fixed)
  80       return false;
  81
  82    return true;
  83 };
  84
  85 // =============================================================================
  86
  87 class CopyPropagation : public Pass
  88 {
  89 private:
  90    virtual bool visit(BasicBlock *);
  91 };
  92
  93 // Propagate all MOVs forward to make subsequent optimization easier, except if
  94 // the sources stem from a phi, in which case we don't want to mess up potential
  95 // swaps $rX <-> $rY, i.e. do not create live range overlaps of phi src and def.
  96 bool
  97 CopyPropagation::visit(BasicBlock *bb)
  98 {
  99    Instruction *mov, *si, *next;
 100
 101    for (mov = bb->getEntry(); mov; mov = next) {
 102       next = mov->next;
 103       if (mov->op != OP_MOV || mov->fixed || !mov->getSrc(0)->asLValue())
 104          continue;
 105       if (mov->getPredicate())
 106          continue;
 107       if (mov->def(0).getFile() != mov->src(0).getFile())
 108          continue;
 109       si = mov->getSrc(0)->getInsn();
 110       if (mov->getDef(0)->reg.data.id < 0 && si && si->op != OP_PHI) {
 111          // propagate
 112          mov->def(0).replace(mov->getSrc(0), false);
 113          delete_Instruction(prog, mov);
 114       }
 115    }
 116    return true;
 117 }
 118
 119 // =============================================================================
 120
 121 class MergeSplits : public Pass
 122 {
 123 private:
 124    virtual bool visit(BasicBlock *);
 125 };
 126
 127 // For SPLIT / MERGE pairs that operate on the same registers, replace the
 128 // post-merge def with the SPLIT's source.
 129 bool
 130 MergeSplits::visit(BasicBlock *bb)
 131 {
 132    Instruction *i, *next, *si;
 133
 134    for (i = bb->getEntry(); i; i = next) {
 135       next = i->next;
 136       if (i->op != OP_MERGE || typeSizeof(i->dType) != 8)
 137          continue;
 138       si = i->getSrc(0)->getInsn();
 139       if (si->op != OP_SPLIT || si != i->getSrc(1)->getInsn())
 140          continue;
 141       i->def(0).replace(si->getSrc(0), false);
 142       delete_Instruction(prog, i);
 143    }
 144
 145    return true;
 146 }
 147
 148 // =============================================================================
 149
 150 class LoadPropagation : public Pass
 151 {
 152 private:
 153    virtual bool visit(BasicBlock *);
 154
 155    void checkSwapSrc01(Instruction *);
 156
 157    bool isCSpaceLoad(Instruction *);
 158    bool isImmd32Load(Instruction *);
 159    bool isAttribOrSharedLoad(Instruction *);
 160 };
 161
 162 bool
 163 LoadPropagation::isCSpaceLoad(Instruction *ld)
 164 {
 165    return ld && ld->op == OP_LOAD && ld->src(0).getFile() == FILE_MEMORY_CONST;
 166 }
 167
 168 bool
 169 LoadPropagation::isImmd32Load(Instruction *ld)
 170 {
 171    if (!ld || (ld->op != OP_MOV) || (typeSizeof(ld->dType) != 4))
 172       return false;
 173    return ld->src(0).getFile() == FILE_IMMEDIATE;
 174 }
 175
 176 bool
 177 LoadPropagation::isAttribOrSharedLoad(Instruction *ld)
 178 {
 179    return ld &&
 180       (ld->op == OP_VFETCH ||
 181        (ld->op == OP_LOAD &&
 182         (ld->src(0).getFile() == FILE_SHADER_INPUT ||
 183          ld->src(0).getFile() == FILE_MEMORY_SHARED)));
 184 }
 185
 186 void
 187 LoadPropagation::checkSwapSrc01(Instruction *insn)
 188 {
 189    if (!prog->getTarget()->getOpInfo(insn).commutative)
 190       if (insn->op != OP_SET && insn->op != OP_SLCT)
 191          return;
 192    if (insn->src(1).getFile() != FILE_GPR)
 193       return;
 194
 195    Instruction *i0 = insn->getSrc(0)->getInsn();
 196    Instruction *i1 = insn->getSrc(1)->getInsn();
 197
 198    if (isCSpaceLoad(i0)) {
 199       if (!isCSpaceLoad(i1))
 200          insn->swapSources(0, 1);
 201       else
 202          return;
 203    } else
 204    if (isImmd32Load(i0)) {
 205       if (!isCSpaceLoad(i1) && !isImmd32Load(i1))
 206          insn->swapSources(0, 1);
 207       else
 208          return;
 209    } else
 210    if (isAttribOrSharedLoad(i1)) {
 211       if (!isAttribOrSharedLoad(i0))
 212          insn->swapSources(0, 1);
 213       else
 214          return;
 215    } else {
 216       return;
 217    }
 218
 219    if (insn->op == OP_SET || insn->op == OP_SET_AND ||
 220        insn->op == OP_SET_OR || insn->op == OP_SET_XOR)
 221       insn->asCmp()->setCond = reverseCondCode(insn->asCmp()->setCond);
 222    else
 223    if (insn->op == OP_SLCT)
 224       insn->asCmp()->setCond = inverseCondCode(insn->asCmp()->setCond);
 225 }
 226
 227 bool
 228 LoadPropagation::visit(BasicBlock *bb)
 229 {
 230    const Target *targ = prog->getTarget();
 231    Instruction *next;
 232
 233    for (Instruction *i = bb->getEntry(); i; i = next) {
 234       next = i->next;
 235
 236       if (i->op == OP_CALL) // calls have args as sources, they must be in regs
 237          continue;
 238
 239       if (i->op == OP_PFETCH) // pfetch expects arg1 to be a reg
 240          continue;
 241
 242       if (i->srcExists(1))
 243          checkSwapSrc01(i);
 244
 245       for (int s = 0; i->srcExists(s); ++s) {
 246          Instruction *ld = i->getSrc(s)->getInsn();
 247
 248          if (!ld || ld->fixed || (ld->op != OP_LOAD && ld->op != OP_MOV))
 249             continue;
 250          if (!targ->insnCanLoad(i, s, ld))
 251             continue;
 252
 253          // propagate !
 254          i->setSrc(s, ld->getSrc(0));
 255          if (ld->src(0).isIndirect(0))
 256             i->setIndirect(s, 0, ld->getIndirect(0, 0));
 257
 258          if (ld->getDef(0)->refCount() == 0)
 259             delete_Instruction(prog, ld);
 260       }
 261    }
 262    return true;
 263 }
 264
 265 // =============================================================================
 266
 267 // Evaluate constant expressions.
 268 class ConstantFolding : public Pass
 269 {
 270 public:
 271    bool foldAll(Program *);
 272
 273 private:
 274    virtual bool visit(BasicBlock *);
 275
 276    void expr(Instruction *, ImmediateValue&, ImmediateValue&);
 277    void expr(Instruction *, ImmediateValue&, ImmediateValue&, ImmediateValue&);
 278    void opnd(Instruction *, ImmediateValue&, int s);
 279
 280    void unary(Instruction *, const ImmediateValue&);
 281
 282    void tryCollapseChainedMULs(Instruction *, const int s, ImmediateValue&);
 283
 284    CmpInstruction *findOriginForTestWithZero(Value *);
 285
 286    unsigned int foldCount;
 287
 288    BuildUtil bld;
 289 };
 290
 291 // TODO: remember generated immediates and only revisit these
 292 bool
 293 ConstantFolding::foldAll(Program *prog)
 294 {
 295    unsigned int iterCount = 0;
 296    do {
 297       foldCount = 0;
 298       if (!run(prog))
 299          return false;
 300    } while (foldCount && ++iterCount < 2);
 301    return true;
 302 }
 303
 304 bool
 305 ConstantFolding::visit(BasicBlock *bb)
 306 {
 307    Instruction *i, *next;
 308
 309    for (i = bb->getEntry(); i; i = next) {
 310       next = i->next;
 311       if (i->op == OP_MOV || i->op == OP_CALL)
 312          continue;
 313
 314       ImmediateValue src0, src1, src2;
 315
 316       if (i->srcExists(2) &&
 317           i->src(0).getImmediate(src0) &&
 318           i->src(1).getImmediate(src1) &&
 319           i->src(2).getImmediate(src2))
 320          expr(i, src0, src1, src2);
 321       else
 322       if (i->srcExists(1) &&
 323           i->src(0).getImmediate(src0) && i->src(1).getImmediate(src1))
 324          expr(i, src0, src1);
 325       else
 326       if (i->srcExists(0) && i->src(0).getImmediate(src0))
 327          opnd(i, src0, 0);
 328       else
 329       if (i->srcExists(1) && i->src(1).getImmediate(src1))
 330          opnd(i, src1, 1);
 331    }
 332    return true;
 333 }
 334
 335 CmpInstruction *
 336 ConstantFolding::findOriginForTestWithZero(Value *value)
 337 {
 338    if (!value)
 339       return NULL;
 340    Instruction *insn = value->getInsn();
 341
 342    if (insn->asCmp() && insn->op != OP_SLCT)
 343       return insn->asCmp();
 344
 345    /* Sometimes mov's will sneak in as a result of other folding. This gets
 346     * cleaned up later.
 347     */
 348    if (insn->op == OP_MOV)
 349       return findOriginForTestWithZero(insn->getSrc(0));
 350
 351    /* Deal with AND 1.0 here since nv50 can't fold into boolean float */
 352    if (insn->op == OP_AND) {
 353       int s = 0;
 354       ImmediateValue imm;
 355       if (!insn->src(s).getImmediate(imm)) {
 356          s = 1;
 357          if (!insn->src(s).getImmediate(imm))
 358             return NULL;
 359       }
 360       if (imm.reg.data.f32 != 1.0f)
 361          return NULL;
 362       /* TODO: Come up with a way to handle the condition being inverted */
 363       if (insn->src(!s).mod != Modifier(0))
 364          return NULL;
 365       return findOriginForTestWithZero(insn->getSrc(!s));
 366    }
 367
 368    return NULL;
 369 }
 370
 371 void
 372 Modifier::applyTo(ImmediateValue& imm) const
 373 {
 374    if (!bits) // avoid failure if imm.reg.type is unhandled (e.g. b128)
 375       return;
 376    switch (imm.reg.type) {
 377    case TYPE_F32:
 378       if (bits & NV50_IR_MOD_ABS)
 379          imm.reg.data.f32 = fabsf(imm.reg.data.f32);
 380       if (bits & NV50_IR_MOD_NEG)
 381          imm.reg.data.f32 = -imm.reg.data.f32;
 382       if (bits & NV50_IR_MOD_SAT) {
 383          if (imm.reg.data.f32 < 0.0f)
 384             imm.reg.data.f32 = 0.0f;
 385          else
 386          if (imm.reg.data.f32 > 1.0f)
 387             imm.reg.data.f32 = 1.0f;
 388       }
 389       assert(!(bits & NV50_IR_MOD_NOT));
 390       break;
 391
 392    case TYPE_S8: // NOTE: will be extended
 393    case TYPE_S16:
 394    case TYPE_S32:
 395    case TYPE_U8: // NOTE: treated as signed
 396    case TYPE_U16:
 397    case TYPE_U32:
 398       if (bits & NV50_IR_MOD_ABS)
 399          imm.reg.data.s32 = (imm.reg.data.s32 >= 0) ?
 400             imm.reg.data.s32 : -imm.reg.data.s32;
 401       if (bits & NV50_IR_MOD_NEG)
 402          imm.reg.data.s32 = -imm.reg.data.s32;
 403       if (bits & NV50_IR_MOD_NOT)
 404          imm.reg.data.s32 = ~imm.reg.data.s32;
 405       break;
 406
 407    case TYPE_F64:
 408       if (bits & NV50_IR_MOD_ABS)
 409          imm.reg.data.f64 = fabs(imm.reg.data.f64);
 410       if (bits & NV50_IR_MOD_NEG)
 411          imm.reg.data.f64 = -imm.reg.data.f64;
 412       if (bits & NV50_IR_MOD_SAT) {
 413          if (imm.reg.data.f64 < 0.0)
 414             imm.reg.data.f64 = 0.0;
 415          else
 416          if (imm.reg.data.f64 > 1.0)
 417             imm.reg.data.f64 = 1.0;
 418       }
 419       assert(!(bits & NV50_IR_MOD_NOT));
 420       break;
 421
 422    default:
 423       assert(!"invalid/unhandled type");
 424       imm.reg.data.u64 = 0;
 425       break;
 426    }
 427 }
 428
 429 operation
 430 Modifier::getOp() const
 431 {
 432    switch (bits) {
 433    case NV50_IR_MOD_ABS: return OP_ABS;
 434    case NV50_IR_MOD_NEG: return OP_NEG;
 435    case NV50_IR_MOD_SAT: return OP_SAT;
 436    case NV50_IR_MOD_NOT: return OP_NOT;
 437    case 0:
 438       return OP_MOV;
 439    default:
 440       return OP_CVT;
 441    }
 442 }
 443
 444 void
 445 ConstantFolding::expr(Instruction *i,
 446                       ImmediateValue &imm0, ImmediateValue &imm1)
 447 {
 448    struct Storage *const a = &imm0.reg, *const b = &imm1.reg;
 449    struct Storage res;
 450
 451    memset(&res.data, 0, sizeof(res.data));
 452
 453    switch (i->op) {
 454    case OP_MAD:
 455    case OP_FMA:
 456    case OP_MUL:
 457       if (i->dnz && i->dType == TYPE_F32) {
 458          if (!isfinite(a->data.f32))
 459             a->data.f32 = 0.0f;
 460          if (!isfinite(b->data.f32))
 461             b->data.f32 = 0.0f;
 462       }
 463       switch (i->dType) {
 464       case TYPE_F32:
 465          res.data.f32 = a->data.f32 * b->data.f32 * exp2f(i->postFactor);
 466          break;
 467       case TYPE_F64: res.data.f64 = a->data.f64 * b->data.f64; break;
 468       case TYPE_S32:
 469          if (i->subOp == NV50_IR_SUBOP_MUL_HIGH) {
 470             res.data.s32 = ((int64_t)a->data.s32 * b->data.s32) >> 32;
 471             break;
 472          }
 473          /* fallthrough */
 474       case TYPE_U32:
 475          if (i->subOp == NV50_IR_SUBOP_MUL_HIGH) {
 476             res.data.u32 = ((uint64_t)a->data.u32 * b->data.u32) >> 32;
 477             break;
 478          }
 479          res.data.u32 = a->data.u32 * b->data.u32; break;
 480       default:
 481          return;
 482       }
 483       break;
 484    case OP_DIV:
 485       if (b->data.u32 == 0)
 486          break;
 487       switch (i->dType) {
 488       case TYPE_F32: res.data.f32 = a->data.f32 / b->data.f32; break;
 489       case TYPE_F64: res.data.f64 = a->data.f64 / b->data.f64; break;
 490       case TYPE_S32: res.data.s32 = a->data.s32 / b->data.s32; break;
 491       case TYPE_U32: res.data.u32 = a->data.u32 / b->data.u32; break;
 492       default:
 493          return;
 494       }
 495       break;
 496    case OP_ADD:
 497       switch (i->dType) {
 498       case TYPE_F32: res.data.f32 = a->data.f32 + b->data.f32; break;
 499       case TYPE_F64: res.data.f64 = a->data.f64 + b->data.f64; break;
 500       case TYPE_S32:
 501       case TYPE_U32: res.data.u32 = a->data.u32 + b->data.u32; break;
 502       default:
 503          return;
 504       }
 505       break;
 506    case OP_POW:
 507       switch (i->dType) {
 508       case TYPE_F32: res.data.f32 = pow(a->data.f32, b->data.f32); break;
 509       case TYPE_F64: res.data.f64 = pow(a->data.f64, b->data.f64); break;
 510       default:
 511          return;
 512       }
 513       break;
 514    case OP_MAX:
 515       switch (i->dType) {
 516       case TYPE_F32: res.data.f32 = MAX2(a->data.f32, b->data.f32); break;
 517       case TYPE_F64: res.data.f64 = MAX2(a->data.f64, b->data.f64); break;
 518       case TYPE_S32: res.data.s32 = MAX2(a->data.s32, b->data.s32); break;
 519       case TYPE_U32: res.data.u32 = MAX2(a->data.u32, b->data.u32); break;
 520       default:
 521          return;
 522       }
 523       break;
 524    case OP_MIN:
 525       switch (i->dType) {
 526       case TYPE_F32: res.data.f32 = MIN2(a->data.f32, b->data.f32); break;
 527       case TYPE_F64: res.data.f64 = MIN2(a->data.f64, b->data.f64); break;
 528       case TYPE_S32: res.data.s32 = MIN2(a->data.s32, b->data.s32); break;
 529       case TYPE_U32: res.data.u32 = MIN2(a->data.u32, b->data.u32); break;
 530       default:
 531          return;
 532       }
 533       break;
 534    case OP_AND:
 535       res.data.u64 = a->data.u64 & b->data.u64;
 536       break;
 537    case OP_OR:
 538       res.data.u64 = a->data.u64 | b->data.u64;
 539       break;
 540    case OP_XOR:
 541       res.data.u64 = a->data.u64 ^ b->data.u64;
 542       break;
 543    case OP_SHL:
 544       res.data.u32 = a->data.u32 << b->data.u32;
 545       break;
 546    case OP_SHR:
 547       switch (i->dType) {
 548       case TYPE_S32: res.data.s32 = a->data.s32 >> b->data.u32; break;
 549       case TYPE_U32: res.data.u32 = a->data.u32 >> b->data.u32; break;
 550       default:
 551          return;
 552       }
 553       break;
 554    case OP_SLCT:
 555       if (a->data.u32 != b->data.u32)
 556          return;
 557       res.data.u32 = a->data.u32;
 558       break;
 559    case OP_EXTBF: {
 560       int offset = b->data.u32 & 0xff;
 561       int width = (b->data.u32 >> 8) & 0xff;
 562       int rshift = offset;
 563       int lshift = 0;
 564       if (width == 0) {
 565          res.data.u32 = 0;
 566          break;
 567       }
 568       if (width + offset < 32) {
 569          rshift = 32 - width;
 570          lshift = 32 - width - offset;
 571       }
 572       if (i->subOp == NV50_IR_SUBOP_EXTBF_REV)
 573          res.data.u32 = util_bitreverse(a->data.u32);
 574       else
 575          res.data.u32 = a->data.u32;
 576       switch (i->dType) {
 577       case TYPE_S32: res.data.s32 = (res.data.s32 << lshift) >> rshift; break;
 578       case TYPE_U32: res.data.u32 = (res.data.u32 << lshift) >> rshift; break;
 579       default:
 580          return;
 581       }
 582       break;
 583    }
 584    case OP_POPCNT:
 585       res.data.u32 = util_bitcount(a->data.u32 & b->data.u32);
 586       break;
 587    case OP_PFETCH:
 588       // The two arguments to pfetch are logically added together. Normally
 589       // the second argument will not be constant, but that can happen.
 590       res.data.u32 = a->data.u32 + b->data.u32;
 591       break;
 592    default:
 593       return;
 594    }
 595    ++foldCount;
 596
 597    i->src(0).mod = Modifier(0);
 598    i->src(1).mod = Modifier(0);
 599    i->postFactor = 0;
 600
 601    i->setSrc(0, new_ImmediateValue(i->bb->getProgram(), res.data.u32));
 602    i->setSrc(1, NULL);
 603
 604    i->getSrc(0)->reg.data = res.data;
 605
 606    switch (i->op) {
 607    case OP_MAD:
 608    case OP_FMA: {
 609       i->op = OP_ADD;
 610
 611       /* Move the immediate to the second arg, otherwise the ADD operation
 612        * won't be emittable
 613        */
 614       i->setSrc(1, i->getSrc(0));
 615       i->setSrc(0, i->getSrc(2));
 616       i->src(0).mod = i->src(2).mod;
 617       i->setSrc(2, NULL);
 618
 619       ImmediateValue src0;
 620       if (i->src(0).getImmediate(src0))
 621          expr(i, src0, *i->getSrc(1)->asImm());
 622       if (i->saturate && !prog->getTarget()->isSatSupported(i)) {
 623          bld.setPosition(i, false);
 624          i->setSrc(1, bld.loadImm(NULL, res.data.u32));
 625       }
 626       break;
 627    }
 628    case OP_PFETCH:
 629       // Leave PFETCH alone... we just folded its 2 args into 1.
 630       break;
 631    default:
 632       i->op = i->saturate ? OP_SAT : OP_MOV; /* SAT handled by unary() */
 633       break;
 634    }
 635    i->subOp = 0;
 636 }
 637
 638 void
 639 ConstantFolding::expr(Instruction *i,
 640                       ImmediateValue &imm0,
 641                       ImmediateValue &imm1,
 642                       ImmediateValue &imm2)
 643 {
 644    struct Storage *const a = &imm0.reg, *const b = &imm1.reg, *const c = &imm2.reg;
 645    struct Storage res;
 646
 647    memset(&res.data, 0, sizeof(res.data));
 648
 649    switch (i->op) {
 650    case OP_INSBF: {
 651       int offset = b->data.u32 & 0xff;
 652       int width = (b->data.u32 >> 8) & 0xff;
 653       unsigned bitmask = ((1 << width) - 1) << offset;
 654       res.data.u32 = ((a->data.u32 << offset) & bitmask) | (c->data.u32 & ~bitmask);
 655       break;
 656    }
 657    default:
 658       return;
 659    }
 660
 661    ++foldCount;
 662    i->src(0).mod = Modifier(0);
 663    i->src(1).mod = Modifier(0);
 664    i->src(2).mod = Modifier(0);
 665
 666    i->setSrc(0, new_ImmediateValue(i->bb->getProgram(), res.data.u32));
 667    i->setSrc(1, NULL);
 668    i->setSrc(2, NULL);
 669
 670    i->getSrc(0)->reg.data = res.data;
 671
 672    i->op = OP_MOV;
 673 }
 674
 675 void
 676 ConstantFolding::unary(Instruction *i, const ImmediateValue &imm)
 677 {
 678    Storage res;
 679
 680    if (i->dType != TYPE_F32)
 681       return;
 682    switch (i->op) {
 683    case OP_NEG: res.data.f32 = -imm.reg.data.f32; break;
 684    case OP_ABS: res.data.f32 = fabsf(imm.reg.data.f32); break;
 685    case OP_SAT: res.data.f32 = CLAMP(imm.reg.data.f32, 0.0f, 1.0f); break;
 686    case OP_RCP: res.data.f32 = 1.0f / imm.reg.data.f32; break;
 687    case OP_RSQ: res.data.f32 = 1.0f / sqrtf(imm.reg.data.f32); break;
 688    case OP_LG2: res.data.f32 = log2f(imm.reg.data.f32); break;
 689    case OP_EX2: res.data.f32 = exp2f(imm.reg.data.f32); break;
 690    case OP_SIN: res.data.f32 = sinf(imm.reg.data.f32); break;
 691    case OP_COS: res.data.f32 = cosf(imm.reg.data.f32); break;
 692    case OP_SQRT: res.data.f32 = sqrtf(imm.reg.data.f32); break;
 693    case OP_PRESIN:
 694    case OP_PREEX2:
 695       // these should be handled in subsequent OP_SIN/COS/EX2
 696       res.data.f32 = imm.reg.data.f32;
 697       break;
 698    default:
 699       return;
 700    }
 701    i->op = OP_MOV;
 702    i->setSrc(0, new_ImmediateValue(i->bb->getProgram(), res.data.f32));
 703    i->src(0).mod = Modifier(0);
 704 }
 705
 706 void
 707 ConstantFolding::tryCollapseChainedMULs(Instruction *mul2,
 708                                         const int s, ImmediateValue& imm2)
 709 {
 710    const int t = s ? 0 : 1;
 711    Instruction *insn;
 712    Instruction *mul1 = NULL; // mul1 before mul2
 713    int e = 0;
 714    float f = imm2.reg.data.f32 * exp2f(mul2->postFactor);
 715    ImmediateValue imm1;
 716
 717    assert(mul2->op == OP_MUL && mul2->dType == TYPE_F32);
 718
 719    if (mul2->getSrc(t)->refCount() == 1) {
 720       insn = mul2->getSrc(t)->getInsn();
 721       if (!mul2->src(t).mod && insn->op == OP_MUL && insn->dType == TYPE_F32)
 722          mul1 = insn;
 723       if (mul1 && !mul1->saturate) {
 724          int s1;
 725
 726          if (mul1->src(s1 = 0).getImmediate(imm1) ||
 727              mul1->src(s1 = 1).getImmediate(imm1)) {
 728             bld.setPosition(mul1, false);
 729             // a = mul r, imm1
 730             // d = mul a, imm2 -> d = mul r, (imm1 * imm2)
 731             mul1->setSrc(s1, bld.loadImm(NULL, f * imm1.reg.data.f32));
 732             mul1->src(s1).mod = Modifier(0);
 733             mul2->def(0).replace(mul1->getDef(0), false);
 734             mul1->saturate = mul2->saturate;
 735          } else
 736          if (prog->getTarget()->isPostMultiplySupported(OP_MUL, f, e)) {
 737             // c = mul a, b
 738             // d = mul c, imm   -> d = mul_x_imm a, b
 739             mul1->postFactor = e;
 740             mul2->def(0).replace(mul1->getDef(0), false);
 741             if (f < 0)
 742                mul1->src(0).mod *= Modifier(NV50_IR_MOD_NEG);
 743             mul1->saturate = mul2->saturate;
 744          }
 745          return;
 746       }
 747    }
 748    if (mul2->getDef(0)->refCount() == 1 && !mul2->saturate) {
 749       // b = mul a, imm
 750       // d = mul b, c   -> d = mul_x_imm a, c
 751       int s2, t2;
 752       insn = (*mul2->getDef(0)->uses.begin())->getInsn();
 753       if (!insn)
 754          return;
 755       mul1 = mul2;
 756       mul2 = NULL;
 757       s2 = insn->getSrc(0) == mul1->getDef(0) ? 0 : 1;
 758       t2 = s2 ? 0 : 1;
 759       if (insn->op == OP_MUL && insn->dType == TYPE_F32)
 760          if (!insn->src(s2).mod && !insn->src(t2).getImmediate(imm1))
 761             mul2 = insn;
 762       if (mul2 && prog->getTarget()->isPostMultiplySupported(OP_MUL, f, e)) {
 763          mul2->postFactor = e;
 764          mul2->setSrc(s2, mul1->src(t));
 765          if (f < 0)
 766             mul2->src(s2).mod *= Modifier(NV50_IR_MOD_NEG);
 767       }
 768    }
 769 }
 770
 771 void
 772 ConstantFolding::opnd(Instruction *i, ImmediateValue &imm0, int s)
 773 {
 774    const int t = !s;
 775    const operation op = i->op;
 776    Instruction *newi = i;
 777
 778    switch (i->op) {
 779    case OP_MUL:
 780       if (i->dType == TYPE_F32)
 781          tryCollapseChainedMULs(i, s, imm0);
 782
 783       if (i->subOp == NV50_IR_SUBOP_MUL_HIGH) {
 784          assert(!isFloatType(i->sType));
 785          if (imm0.isInteger(1) && i->dType == TYPE_S32) {
 786             bld.setPosition(i, false);
 787             // Need to set to the sign value, which is a compare.
 788             newi = bld.mkCmp(OP_SET, CC_LT, TYPE_S32, i->getDef(0),
 789                              TYPE_S32, i->getSrc(t), bld.mkImm(0));
 790             delete_Instruction(prog, i);
 791          } else if (imm0.isInteger(0) || imm0.isInteger(1)) {
 792             // The high bits can't be set in this case (either mul by 0 or
 793             // unsigned by 1)
 794             i->op = OP_MOV;
 795             i->subOp = 0;
 796             i->setSrc(0, new_ImmediateValue(prog, 0u));
 797             i->src(0).mod = Modifier(0);
 798             i->setSrc(1, NULL);
 799          } else if (!imm0.isNegative() && imm0.isPow2()) {
 800             // Translate into a shift
 801             imm0.applyLog2();
 802             i->op = OP_SHR;
 803             i->subOp = 0;
 804             imm0.reg.data.u32 = 32 - imm0.reg.data.u32;
 805             i->setSrc(0, i->getSrc(t));
 806             i->src(0).mod = i->src(t).mod;
 807             i->setSrc(1, new_ImmediateValue(prog, imm0.reg.data.u32));
 808             i->src(1).mod = 0;
 809          }
 810       } else
 811       if (imm0.isInteger(0)) {
 812          i->op = OP_MOV;
 813          i->setSrc(0, new_ImmediateValue(prog, 0u));
 814          i->src(0).mod = Modifier(0);
 815          i->postFactor = 0;
 816          i->setSrc(1, NULL);
 817       } else
 818       if (!i->postFactor && (imm0.isInteger(1) || imm0.isInteger(-1))) {
 819          if (imm0.isNegative())
 820             i->src(t).mod = i->src(t).mod ^ Modifier(NV50_IR_MOD_NEG);
 821          i->op = i->src(t).mod.getOp();
 822          if (s == 0) {
 823             i->setSrc(0, i->getSrc(1));
 824             i->src(0).mod = i->src(1).mod;
 825             i->src(1).mod = 0;
 826          }
 827          if (i->op != OP_CVT)
 828             i->src(0).mod = 0;
 829          i->setSrc(1, NULL);
 830       } else
 831       if (!i->postFactor && (imm0.isInteger(2) || imm0.isInteger(-2))) {
 832          if (imm0.isNegative())
 833             i->src(t).mod = i->src(t).mod ^ Modifier(NV50_IR_MOD_NEG);
 834          i->op = OP_ADD;
 835          i->setSrc(s, i->getSrc(t));
 836          i->src(s).mod = i->src(t).mod;
 837       } else
 838       if (!isFloatType(i->sType) && !imm0.isNegative() && imm0.isPow2()) {
 839          i->op = OP_SHL;
 840          imm0.applyLog2();
 841          i->setSrc(0, i->getSrc(t));
 842          i->src(0).mod = i->src(t).mod;
 843          i->setSrc(1, new_ImmediateValue(prog, imm0.reg.data.u32));
 844          i->src(1).mod = 0;
 845       }
 846       break;
 847    case OP_MAD:
 848       if (imm0.isInteger(0)) {
 849          i->setSrc(0, i->getSrc(2));
 850          i->src(0).mod = i->src(2).mod;
 851          i->setSrc(1, NULL);
 852          i->setSrc(2, NULL);
 853          i->op = i->src(0).mod.getOp();
 854          if (i->op != OP_CVT)
 855             i->src(0).mod = 0;
 856       } else
 857       if (imm0.isInteger(1) || imm0.isInteger(-1)) {
 858          if (imm0.isNegative())
 859             i->src(t).mod = i->src(t).mod ^ Modifier(NV50_IR_MOD_NEG);
 860          if (s == 0) {
 861             i->setSrc(0, i->getSrc(1));
 862             i->src(0).mod = i->src(1).mod;
 863          }
 864          i->setSrc(1, i->getSrc(2));
 865          i->src(1).mod = i->src(2).mod;
 866          i->setSrc(2, NULL);
 867          i->op = OP_ADD;
 868       }
 869       break;
 870    case OP_ADD:
 871       if (i->usesFlags())
 872          break;
 873       if (imm0.isInteger(0)) {
 874          if (s == 0) {
 875             i->setSrc(0, i->getSrc(1));
 876             i->src(0).mod = i->src(1).mod;
 877          }
 878          i->setSrc(1, NULL);
 879          i->op = i->src(0).mod.getOp();
 880          if (i->op != OP_CVT)
 881             i->src(0).mod = Modifier(0);
 882       }
 883       break;
 884
 885    case OP_DIV:
 886       if (s != 1 || (i->dType != TYPE_S32 && i->dType != TYPE_U32))
 887          break;
 888       bld.setPosition(i, false);
 889       if (imm0.reg.data.u32 == 0) {
 890          break;
 891       } else
 892       if (imm0.reg.data.u32 == 1) {
 893          i->op = OP_MOV;
 894          i->setSrc(1, NULL);
 895       } else
 896       if (i->dType == TYPE_U32 && imm0.isPow2()) {
 897          i->op = OP_SHR;
 898          i->setSrc(1, bld.mkImm(util_logbase2(imm0.reg.data.u32)));
 899       } else
 900       if (i->dType == TYPE_U32) {
 901          Instruction *mul;
 902          Value *tA, *tB;
 903          const uint32_t d = imm0.reg.data.u32;
 904          uint32_t m;
 905          int r, s;
 906          uint32_t l = util_logbase2(d);
 907          if (((uint32_t)1 << l) < d)
 908             ++l;
 909          m = (((uint64_t)1 << 32) * (((uint64_t)1 << l) - d)) / d + 1;
 910          r = l ? 1 : 0;
 911          s = l ? (l - 1) : 0;
 912
 913          tA = bld.getSSA();
 914          tB = bld.getSSA();
 915          mul = bld.mkOp2(OP_MUL, TYPE_U32, tA, i->getSrc(0),
 916                          bld.loadImm(NULL, m));
 917          mul->subOp = NV50_IR_SUBOP_MUL_HIGH;
 918          bld.mkOp2(OP_SUB, TYPE_U32, tB, i->getSrc(0), tA);
 919          tA = bld.getSSA();
 920          if (r)
 921             bld.mkOp2(OP_SHR, TYPE_U32, tA, tB, bld.mkImm(r));
 922          else
 923             tA = tB;
 924          tB = s ? bld.getSSA() : i->getDef(0);
 925          newi = bld.mkOp2(OP_ADD, TYPE_U32, tB, mul->getDef(0), tA);
 926          if (s)
 927             bld.mkOp2(OP_SHR, TYPE_U32, i->getDef(0), tB, bld.mkImm(s));
 928
 929          delete_Instruction(prog, i);
 930       } else
 931       if (imm0.reg.data.s32 == -1) {
 932          i->op = OP_NEG;
 933          i->setSrc(1, NULL);
 934       } else {
 935          LValue *tA, *tB;
 936          LValue *tD;
 937          const int32_t d = imm0.reg.data.s32;
 938          int32_t m;
 939          int32_t l = util_logbase2(static_cast<unsigned>(abs(d)));
 940          if ((1 << l) < abs(d))
 941             ++l;
 942          if (!l)
 943             l = 1;
 944          m = ((uint64_t)1 << (32 + l - 1)) / abs(d) + 1 - ((uint64_t)1 << 32);
 945
 946          tA = bld.getSSA();
 947          tB = bld.getSSA();
 948          bld.mkOp3(OP_MAD, TYPE_S32, tA, i->getSrc(0), bld.loadImm(NULL, m),
 949                    i->getSrc(0))->subOp = NV50_IR_SUBOP_MUL_HIGH;
 950          if (l > 1)
 951             bld.mkOp2(OP_SHR, TYPE_S32, tB, tA, bld.mkImm(l - 1));
 952          else
 953             tB = tA;
 954          tA = bld.getSSA();
 955          bld.mkCmp(OP_SET, CC_LT, TYPE_S32, tA, TYPE_S32, i->getSrc(0), bld.mkImm(0));
 956          tD = (d < 0) ? bld.getSSA() : i->getDef(0)->asLValue();
 957          newi = bld.mkOp2(OP_SUB, TYPE_U32, tD, tB, tA);
 958          if (d < 0)
 959             bld.mkOp1(OP_NEG, TYPE_S32, i->getDef(0), tB);
 960
 961          delete_Instruction(prog, i);
 962       }
 963       break;
 964
 965    case OP_MOD:
 966       if (i->sType == TYPE_U32 && imm0.isPow2()) {
 967          bld.setPosition(i, false);
 968          i->op = OP_AND;
 969          i->setSrc(1, bld.loadImm(NULL, imm0.reg.data.u32 - 1));
 970       }
 971       break;
 972
 973    case OP_SET: // TODO: SET_AND,OR,XOR
 974    {
 975       /* This optimizes the case where the output of a set is being compared
 976        * to zero. Since the set can only produce 0/-1 (int) or 0/1 (float), we
 977        * can be a lot cleverer in our comparison.
 978        */
 979       CmpInstruction *si = findOriginForTestWithZero(i->getSrc(t));
 980       CondCode cc, ccZ;
 981       if (imm0.reg.data.u32 != 0 || !si)
 982          return;
 983       cc = si->setCond;
 984       ccZ = (CondCode)((unsigned int)i->asCmp()->setCond & ~CC_U);
 985       // We do everything assuming var (cmp) 0, reverse the condition if 0 is
 986       // first.
 987       if (s == 0)
 988          ccZ = reverseCondCode(ccZ);
 989       // If there is a negative modifier, we need to undo that, by flipping
 990       // the comparison to zero.
 991       if (i->src(t).mod.neg())
 992          ccZ = reverseCondCode(ccZ);
 993       // If this is a signed comparison, we expect the input to be a regular
 994       // boolean, i.e. 0/-1. However the rest of the logic assumes that true
 995       // is positive, so just flip the sign.
 996       if (i->sType == TYPE_S32) {
 997          assert(!isFloatType(si->dType));
 998          ccZ = reverseCondCode(ccZ);
 999       }
1000       switch (ccZ) {
1001       case CC_LT: cc = CC_FL; break; // bool < 0 -- this is never true
1002       case CC_GE: cc = CC_TR; break; // bool >= 0 -- this is always true
1003       case CC_EQ: cc = inverseCondCode(cc); break; // bool == 0 -- !bool
1004       case CC_LE: cc = inverseCondCode(cc); break; // bool <= 0 -- !bool
1005       case CC_GT: break; // bool > 0 -- bool
1006       case CC_NE: break; // bool != 0 -- bool
1007       default:
1008          return;
1009       }
1010
1011       // Update the condition of this SET to be identical to the origin set,
1012       // but with the updated condition code. The original SET should get
1013       // DCE'd, ideally.
1014       i->op = si->op;
1015       i->asCmp()->setCond = cc;
1016       i->setSrc(0, si->src(0));
1017       i->setSrc(1, si->src(1));
1018       if (si->srcExists(2))
1019          i->setSrc(2, si->src(2));
1020       i->sType = si->sType;
1021    }
1022       break;
1023
1024    case OP_AND:
1025    {
1026       CmpInstruction *cmp = i->getSrc(t)->getInsn()->asCmp();
1027       if (!cmp || cmp->op == OP_SLCT || cmp->getDef(0)->refCount() > 1)
1028          return;
1029       if (!prog->getTarget()->isOpSupported(cmp->op, TYPE_F32))
1030          return;
1031       if (imm0.reg.data.f32 != 1.0)
1032          return;
1033       if (i->getSrc(t)->getInsn()->dType != TYPE_U32)
1034          return;
1035
1036       i->getSrc(t)->getInsn()->dType = TYPE_F32;
1037       if (i->src(t).mod != Modifier(0)) {
1038          assert(i->src(t).mod == Modifier(NV50_IR_MOD_NOT));
1039          i->src(t).mod = Modifier(0);
1040          cmp->setCond = inverseCondCode(cmp->setCond);
1041       }
1042       i->op = OP_MOV;
1043       i->setSrc(s, NULL);
1044       if (t) {
1045          i->setSrc(0, i->getSrc(t));
1046          i->setSrc(t, NULL);
1047       }
1048    }
1049       break;
1050
1051    case OP_SHL:
1052    {
1053       if (s != 1 || i->src(0).mod != Modifier(0))
1054          break;
1055       // try to concatenate shifts
1056       Instruction *si = i->getSrc(0)->getInsn();
1057       if (!si || si->op != OP_SHL)
1058          break;
1059       ImmediateValue imm1;
1060       if (si->src(1).getImmediate(imm1)) {
1061          bld.setPosition(i, false);
1062          i->setSrc(0, si->getSrc(0));
1063          i->setSrc(1, bld.loadImm(NULL, imm0.reg.data.u32 + imm1.reg.data.u32));
1064       }
1065    }
1066       break;
1067
1068    case OP_ABS:
1069    case OP_NEG:
1070    case OP_SAT:
1071    case OP_LG2:
1072    case OP_RCP:
1073    case OP_SQRT:
1074    case OP_RSQ:
1075    case OP_PRESIN:
1076    case OP_SIN:
1077    case OP_COS:
1078    case OP_PREEX2:
1079    case OP_EX2:
1080       unary(i, imm0);
1081       break;
1082    case OP_BFIND: {
1083       int32_t res;
1084       switch (i->dType) {
1085       case TYPE_S32: res = util_last_bit_signed(imm0.reg.data.s32) - 1; break;
1086       case TYPE_U32: res = util_last_bit(imm0.reg.data.u32) - 1; break;
1087       default:
1088          return;
1089       }
1090       if (i->subOp == NV50_IR_SUBOP_BFIND_SAMT && res >= 0)
1091          res = 31 - res;
1092       bld.setPosition(i, false); /* make sure bld is init'ed */
1093       i->setSrc(0, bld.mkImm(res));
1094       i->setSrc(1, NULL);
1095       i->op = OP_MOV;
1096       i->subOp = 0;
1097       break;
1098    }
1099    case OP_POPCNT: {
1100       // Only deal with 1-arg POPCNT here
1101       if (i->srcExists(1))
1102          break;
1103       uint32_t res = util_bitcount(imm0.reg.data.u32);
1104       i->setSrc(0, new_ImmediateValue(i->bb->getProgram(), res));
1105       i->setSrc(1, NULL);
1106       i->op = OP_MOV;
1107       break;
1108    }
1109    default:
1110       return;
1111    }
1112    if (newi->op != op)
1113       foldCount++;
1114 }
1115
1116 // =============================================================================
1117
1118 // Merge modifier operations (ABS, NEG, NOT) into ValueRefs where allowed.
1119 class ModifierFolding : public Pass
1120 {
1121 private:
1122    virtual bool visit(BasicBlock *);
1123 };
1124
1125 bool
1126 ModifierFolding::visit(BasicBlock *bb)
1127 {
1128    const Target *target = prog->getTarget();
1129
1130    Instruction *i, *next, *mi;
1131    Modifier mod;
1132
1133    for (i = bb->getEntry(); i; i = next) {
1134       next = i->next;
1135
1136       if (0 && i->op == OP_SUB) {
1137          // turn "sub" into "add neg" (do we really want this ?)
1138          i->op = OP_ADD;
1139          i->src(0).mod = i->src(0).mod ^ Modifier(NV50_IR_MOD_NEG);
1140       }
1141
1142       for (int s = 0; s < 3 && i->srcExists(s); ++s) {
1143          mi = i->getSrc(s)->getInsn();
1144          if (!mi ||
1145              mi->predSrc >= 0 || mi->getDef(0)->refCount() > 8)
1146             continue;
1147          if (i->sType == TYPE_U32 && mi->dType == TYPE_S32) {
1148             if ((i->op != OP_ADD &&
1149                  i->op != OP_MUL) ||
1150                 (mi->op != OP_ABS &&
1151                  mi->op != OP_NEG))
1152                continue;
1153          } else
1154          if (i->sType != mi->dType) {
1155             continue;
1156          }
1157          if ((mod = Modifier(mi->op)) == Modifier(0))
1158             continue;
1159          mod *= mi->src(0).mod;
1160
1161          if ((i->op == OP_ABS) || i->src(s).mod.abs()) {
1162             // abs neg [abs] = abs
1163             mod = mod & Modifier(~(NV50_IR_MOD_NEG | NV50_IR_MOD_ABS));
1164          } else
1165          if ((i->op == OP_NEG) && mod.neg()) {
1166             assert(s == 0);
1167             // neg as both opcode and modifier on same insn is prohibited
1168             // neg neg abs = abs, neg neg = identity
1169             mod = mod & Modifier(~NV50_IR_MOD_NEG);
1170             i->op = mod.getOp();
1171             mod = mod & Modifier(~NV50_IR_MOD_ABS);
1172             if (mod == Modifier(0))
1173                i->op = OP_MOV;
1174          }
1175
1176          if (target->isModSupported(i, s, mod)) {
1177             i->setSrc(s, mi->getSrc(0));
1178             i->src(s).mod *= mod;
1179          }
1180       }
1181
1182       if (i->op == OP_SAT) {
1183          mi = i->getSrc(0)->getInsn();
1184          if (mi &&
1185              mi->getDef(0)->refCount() <= 1 && target->isSatSupported(mi)) {
1186             mi->saturate = 1;
1187             mi->setDef(0, i->getDef(0));
1188             delete_Instruction(prog, i);
1189          }
1190       }
1191    }
1192
1193    return true;
1194 }
1195
1196 // =============================================================================
1197
1198 // MUL + ADD -> MAD/FMA
1199 // MIN/MAX(a, a) -> a, etc.
1200 // SLCT(a, b, const) -> cc(const) ? a : b
1201 // RCP(RCP(a)) -> a
1202 // MUL(MUL(a, b), const) -> MUL_Xconst(a, b)
1203 class AlgebraicOpt : public Pass
1204 {
1205 private:
1206    virtual bool visit(BasicBlock *);
1207
1208    void handleABS(Instruction *);
1209    bool handleADD(Instruction *);
1210    bool tryADDToMADOrSAD(Instruction *, operation toOp);
1211    void handleMINMAX(Instruction *);
1212    void handleRCP(Instruction *);
1213    void handleSLCT(Instruction *);
1214    void handleLOGOP(Instruction *);
1215    void handleCVT(Instruction *);
1216    void handleSUCLAMP(Instruction *);
1217
1218    BuildUtil bld;
1219 };
1220
1221 void
1222 AlgebraicOpt::handleABS(Instruction *abs)
1223 {
1224    Instruction *sub = abs->getSrc(0)->getInsn();
1225    DataType ty;
1226    if (!sub ||
1227        !prog->getTarget()->isOpSupported(OP_SAD, abs->dType))
1228       return;
1229    // expect not to have mods yet, if we do, bail
1230    if (sub->src(0).mod || sub->src(1).mod)
1231       return;
1232    // hidden conversion ?
1233    ty = intTypeToSigned(sub->dType);
1234    if (abs->dType != abs->sType || ty != abs->sType)
1235       return;
1236
1237    if ((sub->op != OP_ADD && sub->op != OP_SUB) ||
1238        sub->src(0).getFile() != FILE_GPR || sub->src(0).mod ||
1239        sub->src(1).getFile() != FILE_GPR || sub->src(1).mod)
1240          return;
1241
1242    Value *src0 = sub->getSrc(0);
1243    Value *src1 = sub->getSrc(1);
1244
1245    if (sub->op == OP_ADD) {
1246       Instruction *neg = sub->getSrc(1)->getInsn();
1247       if (neg && neg->op != OP_NEG) {
1248          neg = sub->getSrc(0)->getInsn();
1249          src0 = sub->getSrc(1);
1250       }
1251       if (!neg || neg->op != OP_NEG ||
1252           neg->dType != neg->sType || neg->sType != ty)
1253          return;
1254       src1 = neg->getSrc(0);
1255    }
1256
1257    // found ABS(SUB))
1258    abs->moveSources(1, 2); // move sources >=1 up by 2
1259    abs->op = OP_SAD;
1260    abs->setType(sub->dType);
1261    abs->setSrc(0, src0);
1262    abs->setSrc(1, src1);
1263    bld.setPosition(abs, false);
1264    abs->setSrc(2, bld.loadImm(bld.getSSA(typeSizeof(ty)), 0));
1265 }
1266
1267 bool
1268 AlgebraicOpt::handleADD(Instruction *add)
1269 {
1270    Value *src0 = add->getSrc(0);
1271    Value *src1 = add->getSrc(1);
1272
1273    if (src0->reg.file != FILE_GPR || src1->reg.file != FILE_GPR)
1274       return false;
1275
1276    bool changed = false;
1277    if (!changed && prog->getTarget()->isOpSupported(OP_MAD, add->dType))
1278       changed = tryADDToMADOrSAD(add, OP_MAD);
1279    if (!changed && prog->getTarget()->isOpSupported(OP_SAD, add->dType))
1280       changed = tryADDToMADOrSAD(add, OP_SAD);
1281    return changed;
1282 }
1283
1284 // ADD(SAD(a,b,0), c) -> SAD(a,b,c)
1285 // ADD(MUL(a,b), c) -> MAD(a,b,c)
1286 bool
1287 AlgebraicOpt::tryADDToMADOrSAD(Instruction *add, operation toOp)
1288 {
1289    Value *src0 = add->getSrc(0);
1290    Value *src1 = add->getSrc(1);
1291    Value *src;
1292    int s;
1293    const operation srcOp = toOp == OP_SAD ? OP_SAD : OP_MUL;
1294    const Modifier modBad = Modifier(~((toOp == OP_MAD) ? NV50_IR_MOD_NEG : 0));
1295    Modifier mod[4];
1296
1297    if (src0->refCount() == 1 &&
1298        src0->getUniqueInsn() && src0->getUniqueInsn()->op == srcOp)
1299       s = 0;
1300    else
1301    if (src1->refCount() == 1 &&
1302        src1->getUniqueInsn() && src1->getUniqueInsn()->op == srcOp)
1303       s = 1;
1304    else
1305       return false;
1306
1307    if ((src0->getUniqueInsn() && src0->getUniqueInsn()->bb != add->bb) ||
1308        (src1->getUniqueInsn() && src1->getUniqueInsn()->bb != add->bb))
1309       return false;
1310
1311    src = add->getSrc(s);
1312
1313    if (src->getInsn()->postFactor)
1314       return false;
1315    if (toOp == OP_SAD) {
1316       ImmediateValue imm;
1317       if (!src->getInsn()->src(2).getImmediate(imm))
1318          return false;
1319       if (!imm.isInteger(0))
1320          return false;
1321    }
1322
1323    mod[0] = add->src(0).mod;
1324    mod[1] = add->src(1).mod;
1325    mod[2] = src->getUniqueInsn()->src(0).mod;
1326    mod[3] = src->getUniqueInsn()->src(1).mod;
1327
1328    if (((mod[0] | mod[1]) | (mod[2] | mod[3])) & modBad)
1329       return false;
1330
1331    add->op = toOp;
1332    add->subOp = src->getInsn()->subOp; // potentially mul-high
1333
1334    add->setSrc(2, add->src(s ? 0 : 1));
1335
1336    add->setSrc(0, src->getInsn()->getSrc(0));
1337    add->src(0).mod = mod[2] ^ mod[s];
1338    add->setSrc(1, src->getInsn()->getSrc(1));
1339    add->src(1).mod = mod[3];
1340
1341    return true;
1342 }
1343
1344 void
1345 AlgebraicOpt::handleMINMAX(Instruction *minmax)
1346 {
1347    Value *src0 = minmax->getSrc(0);
1348    Value *src1 = minmax->getSrc(1);
1349
1350    if (src0 != src1 || src0->reg.file != FILE_GPR)
1351       return;
1352    if (minmax->src(0).mod == minmax->src(1).mod) {
1353       if (minmax->def(0).mayReplace(minmax->src(0))) {
1354          minmax->def(0).replace(minmax->src(0), false);
1355          minmax->bb->remove(minmax);
1356       } else {
1357          minmax->op = OP_CVT;
1358          minmax->setSrc(1, NULL);
1359       }
1360    } else {
1361       // TODO:
1362       // min(x, -x) = -abs(x)
1363       // min(x, -abs(x)) = -abs(x)
1364       // min(x, abs(x)) = x
1365       // max(x, -abs(x)) = x
1366       // max(x, abs(x)) = abs(x)
1367       // max(x, -x) = abs(x)
1368    }
1369 }
1370
1371 void
1372 AlgebraicOpt::handleRCP(Instruction *rcp)
1373 {
1374    Instruction *si = rcp->getSrc(0)->getUniqueInsn();
1375
1376    if (si && si->op == OP_RCP) {
1377       Modifier mod = rcp->src(0).mod * si->src(0).mod;
1378       rcp->op = mod.getOp();
1379       rcp->setSrc(0, si->getSrc(0));
1380    }
1381 }
1382
1383 void
1384 AlgebraicOpt::handleSLCT(Instruction *slct)
1385 {
1386    if (slct->getSrc(2)->reg.file == FILE_IMMEDIATE) {
1387       if (slct->getSrc(2)->asImm()->compare(slct->asCmp()->setCond, 0.0f))
1388          slct->setSrc(0, slct->getSrc(1));
1389    } else
1390    if (slct->getSrc(0) != slct->getSrc(1)) {
1391       return;
1392    }
1393    slct->op = OP_MOV;
1394    slct->setSrc(1, NULL);
1395    slct->setSrc(2, NULL);
1396 }
1397
1398 void
1399 AlgebraicOpt::handleLOGOP(Instruction *logop)
1400 {
1401    Value *src0 = logop->getSrc(0);
1402    Value *src1 = logop->getSrc(1);
1403
1404    if (src0->reg.file != FILE_GPR || src1->reg.file != FILE_GPR)
1405       return;
1406
1407    if (src0 == src1) {
1408       if ((logop->op == OP_AND || logop->op == OP_OR) &&
1409           logop->def(0).mayReplace(logop->src(0))) {
1410          logop->def(0).replace(logop->src(0), false);
1411          delete_Instruction(prog, logop);
1412       }
1413    } else {
1414       // try AND(SET, SET) -> SET_AND(SET)
1415       Instruction *set0 = src0->getInsn();
1416       Instruction *set1 = src1->getInsn();
1417
1418       if (!set0 || set0->fixed || !set1 || set1->fixed)
1419          return;
1420       if (set1->op != OP_SET) {
1421          Instruction *xchg = set0;
1422          set0 = set1;
1423          set1 = xchg;
1424          if (set1->op != OP_SET)
1425             return;
1426       }
1427       operation redOp = (logop->op == OP_AND ? OP_SET_AND :
1428                          logop->op == OP_XOR ? OP_SET_XOR : OP_SET_OR);
1429       if (!prog->getTarget()->isOpSupported(redOp, set1->sType))
1430          return;
1431       if (set0->op != OP_SET &&
1432           set0->op != OP_SET_AND &&
1433           set0->op != OP_SET_OR &&
1434           set0->op != OP_SET_XOR)
1435          return;
1436       if (set0->getDef(0)->refCount() > 1 &&
1437           set1->getDef(0)->refCount() > 1)
1438          return;
1439       if (set0->getPredicate() || set1->getPredicate())
1440          return;
1441       // check that they don't source each other
1442       for (int s = 0; s < 2; ++s)
1443          if (set0->getSrc(s) == set1->getDef(0) ||
1444              set1->getSrc(s) == set0->getDef(0))
1445             return;
1446
1447       set0 = cloneForward(func, set0);
1448       set1 = cloneShallow(func, set1);
1449       logop->bb->insertAfter(logop, set1);
1450       logop->bb->insertAfter(logop, set0);
1451
1452       set0->dType = TYPE_U8;
1453       set0->getDef(0)->reg.file = FILE_PREDICATE;
1454       set0->getDef(0)->reg.size = 1;
1455       set1->setSrc(2, set0->getDef(0));
1456       set1->op = redOp;
1457       set1->setDef(0, logop->getDef(0));
1458       delete_Instruction(prog, logop);
1459    }
1460 }
1461
1462 // F2I(NEG(SET with result 1.0f/0.0f)) -> SET with result -1/0
1463 // nv50:
1464 //  F2I(NEG(I2F(ABS(SET))))
1465 void
1466 AlgebraicOpt::handleCVT(Instruction *cvt)
1467 {
1468    if (cvt->sType != TYPE_F32 ||
1469        cvt->dType != TYPE_S32 || cvt->src(0).mod != Modifier(0))
1470       return;
1471    Instruction *insn = cvt->getSrc(0)->getInsn();
1472    if (!insn || insn->op != OP_NEG || insn->dType != TYPE_F32)
1473       return;
1474    if (insn->src(0).mod != Modifier(0))
1475       return;
1476    insn = insn->getSrc(0)->getInsn();
1477
1478    // check for nv50 SET(-1,0) -> SET(1.0f/0.0f) chain and nvc0's f32 SET
1479    if (insn && insn->op == OP_CVT &&
1480        insn->dType == TYPE_F32 &&
1481        insn->sType == TYPE_S32) {
1482       insn = insn->getSrc(0)->getInsn();
1483       if (!insn || insn->op != OP_ABS || insn->sType != TYPE_S32 ||
1484           insn->src(0).mod)
1485          return;
1486       insn = insn->getSrc(0)->getInsn();
1487       if (!insn || insn->op != OP_SET || insn->dType != TYPE_U32)
1488          return;
1489    } else
1490    if (!insn || insn->op != OP_SET || insn->dType != TYPE_F32) {
1491       return;
1492    }
1493
1494    Instruction *bset = cloneShallow(func, insn);
1495    bset->dType = TYPE_U32;
1496    bset->setDef(0, cvt->getDef(0));
1497    cvt->bb->insertAfter(cvt, bset);
1498    delete_Instruction(prog, cvt);
1499 }
1500
1501 // SUCLAMP dst, (ADD b imm), k, 0 -> SUCLAMP dst, b, k, imm (if imm fits s6)
1502 void
1503 AlgebraicOpt::handleSUCLAMP(Instruction *insn)
1504 {
1505    ImmediateValue imm;
1506    int32_t val = insn->getSrc(2)->asImm()->reg.data.s32;
1507    int s;
1508    Instruction *add;
1509
1510    assert(insn->srcExists(0) && insn->src(0).getFile() == FILE_GPR);
1511
1512    // look for ADD (TODO: only count references by non-SUCLAMP)
1513    if (insn->getSrc(0)->refCount() > 1)
1514       return;
1515    add = insn->getSrc(0)->getInsn();
1516    if (!add || add->op != OP_ADD ||
1517        (add->dType != TYPE_U32 &&
1518         add->dType != TYPE_S32))
1519       return;
1520
1521    // look for immediate
1522    for (s = 0; s < 2; ++s)
1523       if (add->src(s).getImmediate(imm))
1524          break;
1525    if (s >= 2)
1526       return;
1527    s = s ? 0 : 1;
1528    // determine if immediate fits
1529    val += imm.reg.data.s32;
1530    if (val > 31 || val < -32)
1531       return;
1532    // determine if other addend fits
1533    if (add->src(s).getFile() != FILE_GPR || add->src(s).mod != Modifier(0))
1534       return;
1535
1536    bld.setPosition(insn, false); // make sure bld is init'ed
1537    // replace sources
1538    insn->setSrc(2, bld.mkImm(val));
1539    insn->setSrc(0, add->getSrc(s));
1540 }
1541
1542 bool
1543 AlgebraicOpt::visit(BasicBlock *bb)
1544 {
1545    Instruction *next;
1546    for (Instruction *i = bb->getEntry(); i; i = next) {
1547       next = i->next;
1548       switch (i->op) {
1549       case OP_ABS:
1550          handleABS(i);
1551          break;
1552       case OP_ADD:
1553          handleADD(i);
1554          break;
1555       case OP_RCP:
1556          handleRCP(i);
1557          break;
1558       case OP_MIN:
1559       case OP_MAX:
1560          handleMINMAX(i);
1561          break;
1562       case OP_SLCT:
1563          handleSLCT(i);
1564          break;
1565       case OP_AND:
1566       case OP_OR:
1567       case OP_XOR:
1568          handleLOGOP(i);
1569          break;
1570       case OP_CVT:
1571          handleCVT(i);
1572          break;
1573       case OP_SUCLAMP:
1574          handleSUCLAMP(i);
1575          break;
1576       default:
1577          break;
1578       }
1579    }
1580
1581    return true;
1582 }
1583
1584 // =============================================================================
1585
1586 static inline void
1587 updateLdStOffset(Instruction *ldst, int32_t offset, Function *fn)
1588 {
1589    if (offset != ldst->getSrc(0)->reg.data.offset) {
1590       if (ldst->getSrc(0)->refCount() > 1)
1591          ldst->setSrc(0, cloneShallow(fn, ldst->getSrc(0)));
1592       ldst->getSrc(0)->reg.data.offset = offset;
1593    }
1594 }
1595
1596 // Combine loads and stores, forward stores to loads where possible.
1597 class MemoryOpt : public Pass
1598 {
1599 private:
1600    class Record
1601    {
1602    public:
1603       Record *next;
1604       Instruction *insn;
1605       const Value *rel[2];
1606       const Value *base;
1607       int32_t offset;
1608       int8_t fileIndex;
1609       uint8_t size;
1610       bool locked;
1611       Record *prev;
1612
1613       bool overlaps(const Instruction *ldst) const;
1614
1615       inline void link(Record **);
1616       inline void unlink(Record **);
1617       inline void set(const Instruction *ldst);
1618    };
1619
1620 public:
1621    MemoryOpt();
1622
1623    Record *loads[DATA_FILE_COUNT];
1624    Record *stores[DATA_FILE_COUNT];
1625
1626    MemoryPool recordPool;
1627
1628 private:
1629    virtual bool visit(BasicBlock *);
1630    bool runOpt(BasicBlock *);
1631
1632    Record **getList(const Instruction *);
1633
1634    Record *findRecord(const Instruction *, bool load, bool& isAdjacent) const;
1635
1636    // merge @insn into load/store instruction from @rec
1637    bool combineLd(Record *rec, Instruction *ld);
1638    bool combineSt(Record *rec, Instruction *st);
1639
1640    bool replaceLdFromLd(Instruction *ld, Record *ldRec);
1641    bool replaceLdFromSt(Instruction *ld, Record *stRec);
1642    bool replaceStFromSt(Instruction *restrict st, Record *stRec);
1643
1644    void addRecord(Instruction *ldst);
1645    void purgeRecords(Instruction *const st, DataFile);
1646    void lockStores(Instruction *const ld);
1647    void reset();
1648
1649 private:
1650    Record *prevRecord;
1651 };
1652
1653 MemoryOpt::MemoryOpt() : recordPool(sizeof(MemoryOpt::Record), 6)
1654 {
1655    for (int i = 0; i < DATA_FILE_COUNT; ++i) {
1656       loads[i] = NULL;
1657       stores[i] = NULL;
1658    }
1659    prevRecord = NULL;
1660 }
1661
1662 void
1663 MemoryOpt::reset()
1664 {
1665    for (unsigned int i = 0; i < DATA_FILE_COUNT; ++i) {
1666       Record *it, *next;
1667       for (it = loads[i]; it; it = next) {
1668          next = it->next;
1669          recordPool.release(it);
1670       }
1671       loads[i] = NULL;
1672       for (it = stores[i]; it; it = next) {
1673          next = it->next;
1674          recordPool.release(it);
1675       }
1676       stores[i] = NULL;
1677    }
1678 }
1679
1680 bool
1681 MemoryOpt::combineLd(Record *rec, Instruction *ld)
1682 {
1683    int32_t offRc = rec->offset;
1684    int32_t offLd = ld->getSrc(0)->reg.data.offset;
1685    int sizeRc = rec->size;
1686    int sizeLd = typeSizeof(ld->dType);
1687    int size = sizeRc + sizeLd;
1688    int d, j;
1689
1690    if (!prog->getTarget()->
1691        isAccessSupported(ld->getSrc(0)->reg.file, typeOfSize(size)))
1692       return false;
1693    // no unaligned loads
1694    if (((size == 0x8) && (MIN2(offLd, offRc) & 0x7)) ||
1695        ((size == 0xc) && (MIN2(offLd, offRc) & 0xf)))
1696       return false;
1697
1698    assert(sizeRc + sizeLd <= 16 && offRc != offLd);
1699
1700    for (j = 0; sizeRc; sizeRc -= rec->insn->getDef(j)->reg.size, ++j);
1701
1702    if (offLd < offRc) {
1703       int sz;
1704       for (sz = 0, d = 0; sz < sizeLd; sz += ld->getDef(d)->reg.size, ++d);
1705       // d: nr of definitions in ld
1706       // j: nr of definitions in rec->insn, move:
1707       for (d = d + j - 1; j > 0; --j, --d)
1708          rec->insn->setDef(d, rec->insn->getDef(j - 1));
1709
1710       if (rec->insn->getSrc(0)->refCount() > 1)
1711          rec->insn->setSrc(0, cloneShallow(func, rec->insn->getSrc(0)));
1712       rec->offset = rec->insn->getSrc(0)->reg.data.offset = offLd;
1713
1714       d = 0;
1715    } else {
1716       d = j;
1717    }
1718    // move definitions of @ld to @rec->insn
1719    for (j = 0; sizeLd; ++j, ++d) {
1720       sizeLd -= ld->getDef(j)->reg.size;
1721       rec->insn->setDef(d, ld->getDef(j));
1722    }
1723
1724    rec->size = size;
1725    rec->insn->getSrc(0)->reg.size = size;
1726    rec->insn->setType(typeOfSize(size));
1727
1728    delete_Instruction(prog, ld);
1729
1730    return true;
1731 }
1732
1733 bool
1734 MemoryOpt::combineSt(Record *rec, Instruction *st)
1735 {
1736    int32_t offRc = rec->offset;
1737    int32_t offSt = st->getSrc(0)->reg.data.offset;
1738    int sizeRc = rec->size;
1739    int sizeSt = typeSizeof(st->dType);
1740    int s = sizeSt / 4;
1741    int size = sizeRc + sizeSt;
1742    int j, k;
1743    Value *src[4]; // no modifiers in ValueRef allowed for st
1744    Value *extra[3];
1745
1746    if (!prog->getTarget()->
1747        isAccessSupported(st->getSrc(0)->reg.file, typeOfSize(size)))
1748       return false;
1749    if (size == 8 && MIN2(offRc, offSt) & 0x7)
1750       return false;
1751
1752    st->takeExtraSources(0, extra); // save predicate and indirect address
1753
1754    if (offRc < offSt) {
1755       // save values from @st
1756       for (s = 0; sizeSt; ++s) {
1757          sizeSt -= st->getSrc(s + 1)->reg.size;
1758          src[s] = st->getSrc(s + 1);
1759       }
1760       // set record's values as low sources of @st
1761       for (j = 1; sizeRc; ++j) {
1762          sizeRc -= rec->insn->getSrc(j)->reg.size;
1763          st->setSrc(j, rec->insn->getSrc(j));
1764       }
1765       // set saved values as high sources of @st
1766       for (k = j, j = 0; j < s; ++j)
1767          st->setSrc(k++, src[j]);
1768
1769       updateLdStOffset(st, offRc, func);
1770    } else {
1771       for (j = 1; sizeSt; ++j)
1772          sizeSt -= st->getSrc(j)->reg.size;
1773       for (s = 1; sizeRc; ++j, ++s) {
1774          sizeRc -= rec->insn->getSrc(s)->reg.size;
1775          st->setSrc(j, rec->insn->getSrc(s));
1776       }
1777       rec->offset = offSt;
1778    }
1779    st->putExtraSources(0, extra); // restore pointer and predicate
1780
1781    delete_Instruction(prog, rec->insn);
1782    rec->insn = st;
1783    rec->size = size;
1784    rec->insn->getSrc(0)->reg.size = size;
1785    rec->insn->setType(typeOfSize(size));
1786    return true;
1787 }
1788
1789 void
1790 MemoryOpt::Record::set(const Instruction *ldst)
1791 {
1792    const Symbol *mem = ldst->getSrc(0)->asSym();
1793    fileIndex = mem->reg.fileIndex;
1794    rel[0] = ldst->getIndirect(0, 0);
1795    rel[1] = ldst->getIndirect(0, 1);
1796    offset = mem->reg.data.offset;
1797    base = mem->getBase();
1798    size = typeSizeof(ldst->sType);
1799 }
1800
1801 void
1802 MemoryOpt::Record::link(Record **list)
1803 {
1804    next = *list;
1805    if (next)
1806       next->prev = this;
1807    prev = NULL;
1808    *list = this;
1809 }
1810
1811 void
1812 MemoryOpt::Record::unlink(Record **list)
1813 {
1814    if (next)
1815       next->prev = prev;
1816    if (prev)
1817       prev->next = next;
1818    else
1819       *list = next;
1820 }
1821
1822 MemoryOpt::Record **
1823 MemoryOpt::getList(const Instruction *insn)
1824 {
1825    if (insn->op == OP_LOAD || insn->op == OP_VFETCH)
1826       return &loads[insn->src(0).getFile()];
1827    return &stores[insn->src(0).getFile()];
1828 }
1829
1830 void
1831 MemoryOpt::addRecord(Instruction *i)
1832 {
1833    Record **list = getList(i);
1834    Record *it = reinterpret_cast<Record *>(recordPool.allocate());
1835
1836    it->link(list);
1837    it->set(i);
1838    it->insn = i;
1839    it->locked = false;
1840 }
1841
1842 MemoryOpt::Record *
1843 MemoryOpt::findRecord(const Instruction *insn, bool load, bool& isAdj) const
1844 {
1845    const Symbol *sym = insn->getSrc(0)->asSym();
1846    const int size = typeSizeof(insn->sType);
1847    Record *rec = NULL;
1848    Record *it = load ? loads[sym->reg.file] : stores[sym->reg.file];
1849
1850    for (; it; it = it->next) {
1851       if (it->locked && insn->op != OP_LOAD)
1852          continue;
1853       if ((it->offset >> 4) != (sym->reg.data.offset >> 4) ||
1854           it->rel[0] != insn->getIndirect(0, 0) ||
1855           it->fileIndex != sym->reg.fileIndex ||
1856           it->rel[1] != insn->getIndirect(0, 1))
1857          continue;
1858
1859       if (it->offset < sym->reg.data.offset) {
1860          if (it->offset + it->size >= sym->reg.data.offset) {
1861             isAdj = (it->offset + it->size == sym->reg.data.offset);
1862             if (!isAdj)
1863                return it;
1864             if (!(it->offset & 0x7))
1865                rec = it;
1866          }
1867       } else {
1868          isAdj = it->offset != sym->reg.data.offset;
1869          if (size <= it->size && !isAdj)
1870             return it;
1871          else
1872          if (!(sym->reg.data.offset & 0x7))
1873             if (it->offset - size <= sym->reg.data.offset)
1874                rec = it;
1875       }
1876    }
1877    return rec;
1878 }
1879
1880 bool
1881 MemoryOpt::replaceLdFromSt(Instruction *ld, Record *rec)
1882 {
1883    Instruction *st = rec->insn;
1884    int32_t offSt = rec->offset;
1885    int32_t offLd = ld->getSrc(0)->reg.data.offset;
1886    int d, s;
1887
1888    for (s = 1; offSt != offLd && st->srcExists(s); ++s)
1889       offSt += st->getSrc(s)->reg.size;
1890    if (offSt != offLd)
1891       return false;
1892
1893    for (d = 0; ld->defExists(d) && st->srcExists(s); ++d, ++s) {
1894       if (ld->getDef(d)->reg.size != st->getSrc(s)->reg.size)
1895          return false;
1896       if (st->getSrc(s)->reg.file != FILE_GPR)
1897          return false;
1898       ld->def(d).replace(st->src(s), false);
1899    }
1900    ld->bb->remove(ld);
1901    return true;
1902 }
1903
1904 bool
1905 MemoryOpt::replaceLdFromLd(Instruction *ldE, Record *rec)
1906 {
1907    Instruction *ldR = rec->insn;
1908    int32_t offR = rec->offset;
1909    int32_t offE = ldE->getSrc(0)->reg.data.offset;
1910    int dR, dE;
1911
1912    assert(offR <= offE);
1913    for (dR = 0; offR < offE && ldR->defExists(dR); ++dR)
1914       offR += ldR->getDef(dR)->reg.size;
1915    if (offR != offE)
1916       return false;
1917
1918    for (dE = 0; ldE->defExists(dE) && ldR->defExists(dR); ++dE, ++dR) {
1919       if (ldE->getDef(dE)->reg.size != ldR->getDef(dR)->reg.size)
1920          return false;
1921       ldE->def(dE).replace(ldR->getDef(dR), false);
1922    }
1923
1924    delete_Instruction(prog, ldE);
1925    return true;
1926 }
1927
1928 bool
1929 MemoryOpt::replaceStFromSt(Instruction *restrict st, Record *rec)
1930 {
1931    const Instruction *const ri = rec->insn;
1932    Value *extra[3];
1933
1934    int32_t offS = st->getSrc(0)->reg.data.offset;
1935    int32_t offR = rec->offset;
1936    int32_t endS = offS + typeSizeof(st->dType);
1937    int32_t endR = offR + typeSizeof(ri->dType);
1938
1939    rec->size = MAX2(endS, endR) - MIN2(offS, offR);
1940
1941    st->takeExtraSources(0, extra);
1942
1943    if (offR < offS) {
1944       Value *vals[10];
1945       int s, n;
1946       int k = 0;
1947       // get non-replaced sources of ri
1948       for (s = 1; offR < offS; offR += ri->getSrc(s)->reg.size, ++s)
1949          vals[k++] = ri->getSrc(s);
1950       n = s;
1951       // get replaced sources of st
1952       for (s = 1; st->srcExists(s); offS += st->getSrc(s)->reg.size, ++s)
1953          vals[k++] = st->getSrc(s);
1954       // skip replaced sources of ri
1955       for (s = n; offR < endS; offR += ri->getSrc(s)->reg.size, ++s);
1956       // get non-replaced sources after values covered by st
1957       for (; offR < endR; offR += ri->getSrc(s)->reg.size, ++s)
1958          vals[k++] = ri->getSrc(s);
1959       assert((unsigned int)k <= Elements(vals));
1960       for (s = 0; s < k; ++s)
1961          st->setSrc(s + 1, vals[s]);
1962       st->setSrc(0, ri->getSrc(0));
1963    } else
1964    if (endR > endS) {
1965       int j, s;
1966       for (j = 1; offR < endS; offR += ri->getSrc(j++)->reg.size);
1967       for (s = 1; offS < endS; offS += st->getSrc(s++)->reg.size);
1968       for (; offR < endR; offR += ri->getSrc(j++)->reg.size)
1969          st->setSrc(s++, ri->getSrc(j));
1970    }
1971    st->putExtraSources(0, extra);
1972
1973    delete_Instruction(prog, rec->insn);
1974
1975    rec->insn = st;
1976    rec->offset = st->getSrc(0)->reg.data.offset;
1977
1978    st->setType(typeOfSize(rec->size));
1979
1980    return true;
1981 }
1982
1983 bool
1984 MemoryOpt::Record::overlaps(const Instruction *ldst) const
1985 {
1986    Record that;
1987    that.set(ldst);
1988
1989    if (this->fileIndex != that.fileIndex)
1990       return false;
1991
1992    if (this->rel[0] || that.rel[0])
1993       return this->base == that.base;
1994    return
1995       (this->offset < that.offset + that.size) &&
1996       (this->offset + this->size > that.offset);
1997 }
1998
1999 // We must not eliminate stores that affect the result of @ld if
2000 // we find later stores to the same location, and we may no longer
2001 // merge them with later stores.
2002 // The stored value can, however, still be used to determine the value
2003 // returned by future loads.
2004 void
2005 MemoryOpt::lockStores(Instruction *const ld)
2006 {
2007    for (Record *r = stores[ld->src(0).getFile()]; r; r = r->next)
2008       if (!r->locked && r->overlaps(ld))
2009          r->locked = true;
2010 }
2011
2012 // Prior loads from the location of @st are no longer valid.
2013 // Stores to the location of @st may no longer be used to derive
2014 // the value at it nor be coalesced into later stores.
2015 void
2016 MemoryOpt::purgeRecords(Instruction *const st, DataFile f)
2017 {
2018    if (st)
2019       f = st->src(0).getFile();
2020
2021    for (Record *r = loads[f]; r; r = r->next)
2022       if (!st || r->overlaps(st))
2023          r->unlink(&loads[f]);
2024
2025    for (Record *r = stores[f]; r; r = r->next)
2026       if (!st || r->overlaps(st))
2027          r->unlink(&stores[f]);
2028 }
2029
2030 bool
2031 MemoryOpt::visit(BasicBlock *bb)
2032 {
2033    bool ret = runOpt(bb);
2034    // Run again, one pass won't combine 4 32 bit ld/st to a single 128 bit ld/st
2035    // where 96 bit memory operations are forbidden.
2036    if (ret)
2037       ret = runOpt(bb);
2038    return ret;
2039 }
2040
2041 bool
2042 MemoryOpt::runOpt(BasicBlock *bb)
2043 {
2044    Instruction *ldst, *next;
2045    Record *rec;
2046    bool isAdjacent = true;
2047
2048    for (ldst = bb->getEntry(); ldst; ldst = next) {
2049       bool keep = true;
2050       bool isLoad = true;
2051       next = ldst->next;
2052
2053       if (ldst->op == OP_LOAD || ldst->op == OP_VFETCH) {
2054          if (ldst->isDead()) {
2055             // might have been produced by earlier optimization
2056             delete_Instruction(prog, ldst);
2057             continue;
2058          }
2059       } else
2060       if (ldst->op == OP_STORE || ldst->op == OP_EXPORT) {
2061          isLoad = false;
2062       } else {
2063          // TODO: maybe have all fixed ops act as barrier ?
2064          if (ldst->op == OP_CALL ||
2065              ldst->op == OP_BAR ||
2066              ldst->op == OP_MEMBAR) {
2067             purgeRecords(NULL, FILE_MEMORY_LOCAL);
2068             purgeRecords(NULL, FILE_MEMORY_GLOBAL);
2069             purgeRecords(NULL, FILE_MEMORY_SHARED);
2070             purgeRecords(NULL, FILE_SHADER_OUTPUT);
2071          } else
2072          if (ldst->op == OP_ATOM || ldst->op == OP_CCTL) {
2073             if (ldst->src(0).getFile() == FILE_MEMORY_GLOBAL) {
2074                purgeRecords(NULL, FILE_MEMORY_LOCAL);
2075                purgeRecords(NULL, FILE_MEMORY_GLOBAL);
2076                purgeRecords(NULL, FILE_MEMORY_SHARED);
2077             } else {
2078                purgeRecords(NULL, ldst->src(0).getFile());
2079             }
2080          } else
2081          if (ldst->op == OP_EMIT || ldst->op == OP_RESTART) {
2082             purgeRecords(NULL, FILE_SHADER_OUTPUT);
2083          }
2084          continue;
2085       }
2086       if (ldst->getPredicate()) // TODO: handle predicated ld/st
2087          continue;
2088
2089       if (isLoad) {
2090          DataFile file = ldst->src(0).getFile();
2091
2092          // if ld l[]/g[] look for previous store to eliminate the reload
2093          if (file == FILE_MEMORY_GLOBAL || file == FILE_MEMORY_LOCAL) {
2094             // TODO: shared memory ?
2095             rec = findRecord(ldst, false, isAdjacent);
2096             if (rec && !isAdjacent)
2097                keep = !replaceLdFromSt(ldst, rec);
2098          }
2099
2100          // or look for ld from the same location and replace this one
2101          rec = keep ? findRecord(ldst, true, isAdjacent) : NULL;
2102          if (rec) {
2103             if (!isAdjacent)
2104                keep = !replaceLdFromLd(ldst, rec);
2105             else
2106                // or combine a previous load with this one
2107                keep = !combineLd(rec, ldst);
2108          }
2109          if (keep)
2110             lockStores(ldst);
2111       } else {
2112          rec = findRecord(ldst, false, isAdjacent);
2113          if (rec) {
2114             if (!isAdjacent)
2115                keep = !replaceStFromSt(ldst, rec);
2116             else
2117                keep = !combineSt(rec, ldst);
2118          }
2119          if (keep)
2120             purgeRecords(ldst, DATA_FILE_COUNT);
2121       }
2122       if (keep)
2123          addRecord(ldst);
2124    }
2125    reset();
2126
2127    return true;
2128 }
2129
2130 // =============================================================================
2131
2132 // Turn control flow into predicated instructions (after register allocation !).
2133 // TODO:
2134 // Could move this to before register allocation on NVC0 and also handle nested
2135 // constructs.
2136 class FlatteningPass : public Pass
2137 {
2138 private:
2139    virtual bool visit(BasicBlock *);
2140
2141    bool tryPredicateConditional(BasicBlock *);
2142    void predicateInstructions(BasicBlock *, Value *pred, CondCode cc);
2143    void tryPropagateBranch(BasicBlock *);
2144    inline bool isConstantCondition(Value *pred);
2145    inline bool mayPredicate(const Instruction *, const Value *pred) const;
2146    inline void removeFlow(Instruction *);
2147 };
2148
2149 bool
2150 FlatteningPass::isConstantCondition(Value *pred)
2151 {
2152    Instruction *insn = pred->getUniqueInsn();
2153    assert(insn);
2154    if (insn->op != OP_SET || insn->srcExists(2))
2155       return false;
2156
2157    for (int s = 0; s < 2 && insn->srcExists(s); ++s) {
2158       Instruction *ld = insn->getSrc(s)->getUniqueInsn();
2159       DataFile file;
2160       if (ld) {
2161          if (ld->op != OP_MOV && ld->op != OP_LOAD)
2162             return false;
2163          if (ld->src(0).isIndirect(0))
2164             return false;
2165          file = ld->src(0).getFile();
2166       } else {
2167          file = insn->src(s).getFile();
2168          // catch $r63 on NVC0
2169          if (file == FILE_GPR && insn->getSrc(s)->reg.data.id > prog->maxGPR)
2170             file = FILE_IMMEDIATE;
2171       }
2172       if (file != FILE_IMMEDIATE && file != FILE_MEMORY_CONST)
2173          return false;
2174    }
2175    return true;
2176 }
2177
2178 void
2179 FlatteningPass::removeFlow(Instruction *insn)
2180 {
2181    FlowInstruction *term = insn ? insn->asFlow() : NULL;
2182    if (!term)
2183       return;
2184    Graph::Edge::Type ty = term->bb->cfg.outgoing().getType();
2185
2186    if (term->op == OP_BRA) {
2187       // TODO: this might get more difficult when we get arbitrary BRAs
2188       if (ty == Graph::Edge::CROSS || ty == Graph::Edge::BACK)
2189          return;
2190    } else
2191    if (term->op != OP_JOIN)
2192       return;
2193
2194    Value *pred = term->getPredicate();
2195
2196    delete_Instruction(prog, term);
2197
2198    if (pred && pred->refCount() == 0) {
2199       Instruction *pSet = pred->getUniqueInsn();
2200       pred->join->reg.data.id = -1; // deallocate
2201       if (pSet->isDead())
2202          delete_Instruction(prog, pSet);
2203    }
2204 }
2205
2206 void
2207 FlatteningPass::predicateInstructions(BasicBlock *bb, Value *pred, CondCode cc)
2208 {
2209    for (Instruction *i = bb->getEntry(); i; i = i->next) {
2210       if (i->isNop())
2211          continue;
2212       assert(!i->getPredicate());
2213       i->setPredicate(cc, pred);
2214    }
2215    removeFlow(bb->getExit());
2216 }
2217
2218 bool
2219 FlatteningPass::mayPredicate(const Instruction *insn, const Value *pred) const
2220 {
2221    if (insn->isPseudo())
2222       return true;
2223    // TODO: calls where we don't know which registers are modified
2224
2225    if (!prog->getTarget()->mayPredicate(insn, pred))
2226       return false;
2227    for (int d = 0; insn->defExists(d); ++d)
2228       if (insn->getDef(d)->equals(pred))
2229          return false;
2230    return true;
2231 }
2232
2233 // If we jump to BRA/RET/EXIT, replace the jump with it.
2234 // NOTE: We do not update the CFG anymore here !
2235 //
2236 // TODO: Handle cases where we skip over a branch (maybe do that elsewhere ?):
2237 //  BB:0
2238 //   @p0 bra BB:2 -> @!p0 bra BB:3 iff (!) BB:2 immediately adjoins BB:1
2239 //  BB1:
2240 //   bra BB:3
2241 //  BB2:
2242 //   ...
2243 //  BB3:
2244 //   ...
2245 void
2246 FlatteningPass::tryPropagateBranch(BasicBlock *bb)
2247 {
2248    for (Instruction *i = bb->getExit(); i && i->op == OP_BRA; i = i->prev) {
2249       BasicBlock *bf = i->asFlow()->target.bb;
2250
2251       if (bf->getInsnCount() != 1)
2252          continue;
2253
2254       FlowInstruction *bra = i->asFlow();
2255       FlowInstruction *rep = bf->getExit()->asFlow();
2256
2257       if (!rep || rep->getPredicate())
2258          continue;
2259       if (rep->op != OP_BRA &&
2260           rep->op != OP_JOIN &&
2261           rep->op != OP_EXIT)
2262          continue;
2263
2264       // TODO: If there are multiple branches to @rep, only the first would
2265       // be replaced, so only remove them after this pass is done ?
2266       // Also, need to check all incident blocks for fall-through exits and
2267       // add the branch there.
2268       bra->op = rep->op;
2269       bra->target.bb = rep->target.bb;
2270       if (bf->cfg.incidentCount() == 1)
2271          bf->remove(rep);
2272    }
2273 }
2274
2275 bool
2276 FlatteningPass::visit(BasicBlock *bb)
2277 {
2278    if (tryPredicateConditional(bb))
2279       return true;
2280
2281    // try to attach join to previous instruction
2282    if (prog->getTarget()->hasJoin) {
2283       Instruction *insn = bb->getExit();
2284       if (insn && insn->op == OP_JOIN && !insn->getPredicate()) {
2285          insn = insn->prev;
2286          if (insn && !insn->getPredicate() &&
2287              !insn->asFlow() &&
2288              insn->op != OP_TEXBAR &&
2289              !isTextureOp(insn->op) && // probably just nve4
2290              !isSurfaceOp(insn->op) && // not confirmed
2291              insn->op != OP_LINTERP && // probably just nve4
2292              insn->op != OP_PINTERP && // probably just nve4
2293              ((insn->op != OP_LOAD && insn->op != OP_STORE) ||
2294               (typeSizeof(insn->dType) <= 4 && !insn->src(0).isIndirect(0))) &&
2295              !insn->isNop()) {
2296             insn->join = 1;
2297             bb->remove(bb->getExit());
2298             return true;
2299          }
2300       }
2301    }
2302
2303    tryPropagateBranch(bb);
2304
2305    return true;
2306 }
2307
2308 bool
2309 FlatteningPass::tryPredicateConditional(BasicBlock *bb)
2310 {
2311    BasicBlock *bL = NULL, *bR = NULL;
2312    unsigned int nL = 0, nR = 0, limit = 12;
2313    Instruction *insn;
2314    unsigned int mask;
2315
2316    mask = bb->initiatesSimpleConditional();
2317    if (!mask)
2318       return false;
2319
2320    assert(bb->getExit());
2321    Value *pred = bb->getExit()->getPredicate();
2322    assert(pred);
2323
2324    if (isConstantCondition(pred))
2325       limit = 4;
2326
2327    Graph::EdgeIterator ei = bb->cfg.outgoing();
2328
2329    if (mask & 1) {
2330       bL = BasicBlock::get(ei.getNode());
2331       for (insn = bL->getEntry(); insn; insn = insn->next, ++nL)
2332          if (!mayPredicate(insn, pred))
2333             return false;
2334       if (nL > limit)
2335          return false; // too long, do a real branch
2336    }
2337    ei.next();
2338
2339    if (mask & 2) {
2340       bR = BasicBlock::get(ei.getNode());
2341       for (insn = bR->getEntry(); insn; insn = insn->next, ++nR)
2342          if (!mayPredicate(insn, pred))
2343             return false;
2344       if (nR > limit)
2345          return false; // too long, do a real branch
2346    }
2347
2348    if (bL)
2349       predicateInstructions(bL, pred, bb->getExit()->cc);
2350    if (bR)
2351       predicateInstructions(bR, pred, inverseCondCode(bb->getExit()->cc));
2352
2353    if (bb->joinAt) {
2354       bb->remove(bb->joinAt);
2355       bb->joinAt = NULL;
2356    }
2357    removeFlow(bb->getExit()); // delete the branch/join at the fork point
2358
2359    // remove potential join operations at the end of the conditional
2360    if (prog->getTarget()->joinAnterior) {
2361       bb = BasicBlock::get((bL ? bL : bR)->cfg.outgoing().getNode());
2362       if (bb->getEntry() && bb->getEntry()->op == OP_JOIN)
2363          removeFlow(bb->getEntry());
2364    }
2365
2366    return true;
2367 }
2368
2369 // =============================================================================
2370
2371 // Fold Immediate into MAD; must be done after register allocation due to
2372 // constraint SDST == SSRC2
2373 // TODO:
2374 // Does NVC0+ have other situations where this pass makes sense?
2375 class NV50PostRaConstantFolding : public Pass
2376 {
2377 private:
2378    virtual bool visit(BasicBlock *);
2379 };
2380
2381 bool
2382 NV50PostRaConstantFolding::visit(BasicBlock *bb)
2383 {
2384    Value *vtmp;
2385    Instruction *def;
2386
2387    for (Instruction *i = bb->getFirst(); i; i = i->next) {
2388       switch (i->op) {
2389       case OP_MAD:
2390          if (i->def(0).getFile() != FILE_GPR ||
2391              i->src(0).getFile() != FILE_GPR ||
2392              i->src(1).getFile() != FILE_GPR ||
2393              i->src(2).getFile() != FILE_GPR ||
2394              i->getDef(0)->reg.data.id != i->getSrc(2)->reg.data.id ||
2395              !isFloatType(i->dType))
2396             break;
2397
2398          def = i->getSrc(1)->getInsn();
2399          if (def->op == OP_MOV && def->src(0).getFile() == FILE_IMMEDIATE) {
2400             vtmp = i->getSrc(1);
2401             i->setSrc(1, def->getSrc(0));
2402
2403             /* There's no post-RA dead code elimination, so do it here
2404              * XXX: if we add more code-removing post-RA passes, we might
2405              *      want to create a post-RA dead-code elim pass */
2406             if (vtmp->refCount() == 0)
2407                delete_Instruction(bb->getProgram(), def);
2408
2409             break;
2410          }
2411          break;
2412       default:
2413          break;
2414       }
2415    }
2416
2417    return true;
2418 }
2419
2420 // =============================================================================
2421
2422 // Common subexpression elimination. Stupid O^2 implementation.
2423 class LocalCSE : public Pass
2424 {
2425 private:
2426    virtual bool visit(BasicBlock *);
2427
2428    inline bool tryReplace(Instruction **, Instruction *);
2429
2430    DLList ops[OP_LAST + 1];
2431 };
2432
2433 class GlobalCSE : public Pass
2434 {
2435 private:
2436    virtual bool visit(BasicBlock *);
2437 };
2438
2439 bool
2440 Instruction::isActionEqual(const Instruction *that) const
2441 {
2442    if (this->op != that->op ||
2443        this->dType != that->dType ||
2444        this->sType != that->sType)
2445       return false;
2446    if (this->cc != that->cc)
2447       return false;
2448
2449    if (this->asTex()) {
2450       if (memcmp(&this->asTex()->tex,
2451                  &that->asTex()->tex,
2452                  sizeof(this->asTex()->tex)))
2453          return false;
2454    } else
2455    if (this->asCmp()) {
2456       if (this->asCmp()->setCond != that->asCmp()->setCond)
2457          return false;
2458    } else
2459    if (this->asFlow()) {
2460       return false;
2461    } else {
2462       if (this->ipa != that->ipa ||
2463           this->lanes != that->lanes ||
2464           this->perPatch != that->perPatch)
2465          return false;
2466       if (this->postFactor != that->postFactor)
2467          return false;
2468    }
2469
2470    if (this->subOp != that->subOp ||
2471        this->saturate != that->saturate ||
2472        this->rnd != that->rnd ||
2473        this->ftz != that->ftz ||
2474        this->dnz != that->dnz ||
2475        this->cache != that->cache ||
2476        this->mask != that->mask)
2477       return false;
2478
2479    return true;
2480 }
2481
2482 bool
2483 Instruction::isResultEqual(const Instruction *that) const
2484 {
2485    unsigned int d, s;
2486
2487    // NOTE: location of discard only affects tex with liveOnly and quadops
2488    if (!this->defExists(0) && this->op != OP_DISCARD)
2489       return false;
2490
2491    if (!isActionEqual(that))
2492       return false;
2493
2494    if (this->predSrc != that->predSrc)
2495       return false;
2496
2497    for (d = 0; this->defExists(d); ++d) {
2498       if (!that->defExists(d) ||
2499           !this->getDef(d)->equals(that->getDef(d), false))
2500          return false;
2501    }
2502    if (that->defExists(d))
2503       return false;
2504
2505    for (s = 0; this->srcExists(s); ++s) {
2506       if (!that->srcExists(s))
2507          return false;
2508       if (this->src(s).mod != that->src(s).mod)
2509          return false;
2510       if (!this->getSrc(s)->equals(that->getSrc(s), true))
2511          return false;
2512    }
2513    if (that->srcExists(s))
2514       return false;
2515
2516    if (op == OP_LOAD || op == OP_VFETCH) {
2517       switch (src(0).getFile()) {
2518       case FILE_MEMORY_CONST:
2519       case FILE_SHADER_INPUT:
2520          return true;
2521       default:
2522          return false;
2523       }
2524    }
2525
2526    return true;
2527 }
2528
2529 // pull through common expressions from different in-blocks
2530 bool
2531 GlobalCSE::visit(BasicBlock *bb)
2532 {
2533    Instruction *phi, *next, *ik;
2534    int s;
2535
2536    // TODO: maybe do this with OP_UNION, too
2537
2538    for (phi = bb->getPhi(); phi && phi->op == OP_PHI; phi = next) {
2539       next = phi->next;
2540       if (phi->getSrc(0)->refCount() > 1)
2541          continue;
2542       ik = phi->getSrc(0)->getInsn();
2543       if (!ik)
2544          continue; // probably a function input
2545       for (s = 1; phi->srcExists(s); ++s) {
2546          if (phi->getSrc(s)->refCount() > 1)
2547             break;
2548          if (!phi->getSrc(s)->getInsn() ||
2549              !phi->getSrc(s)->getInsn()->isResultEqual(ik))
2550             break;
2551       }
2552       if (!phi->srcExists(s)) {
2553          Instruction *entry = bb->getEntry();
2554          ik->bb->remove(ik);
2555          if (!entry || entry->op != OP_JOIN)
2556             bb->insertHead(ik);
2557          else
2558             bb->insertAfter(entry, ik);
2559          ik->setDef(0, phi->getDef(0));
2560          delete_Instruction(prog, phi);
2561       }
2562    }
2563
2564    return true;
2565 }
2566
2567 bool
2568 LocalCSE::tryReplace(Instruction **ptr, Instruction *i)
2569 {
2570    Instruction *old = *ptr;
2571
2572    // TODO: maybe relax this later (causes trouble with OP_UNION)
2573    if (i->isPredicated())
2574       return false;
2575
2576    if (!old->isResultEqual(i))
2577       return false;
2578
2579    for (int d = 0; old->defExists(d); ++d)
2580       old->def(d).replace(i->getDef(d), false);
2581    delete_Instruction(prog, old);
2582    *ptr = NULL;
2583    return true;
2584 }
2585
2586 bool
2587 LocalCSE::visit(BasicBlock *bb)
2588 {
2589    unsigned int replaced;
2590
2591    do {
2592       Instruction *ir, *next;
2593
2594       replaced = 0;
2595
2596       // will need to know the order of instructions
2597       int serial = 0;
2598       for (ir = bb->getFirst(); ir; ir = ir->next)
2599          ir->serial = serial++;
2600
2601       for (ir = bb->getEntry(); ir; ir = next) {
2602          int s;
2603          Value *src = NULL;
2604
2605          next = ir->next;
2606
2607          if (ir->fixed) {
2608             ops[ir->op].insert(ir);
2609             continue;
2610          }
2611
2612          for (s = 0; ir->srcExists(s); ++s)
2613             if (ir->getSrc(s)->asLValue())
2614                if (!src || ir->getSrc(s)->refCount() < src->refCount())
2615                   src = ir->getSrc(s);
2616
2617          if (src) {
2618             for (Value::UseIterator it = src->uses.begin();
2619                  it != src->uses.end(); ++it) {
2620                Instruction *ik = (*it)->getInsn();
2621                if (ik && ik->bb == ir->bb && ik->serial < ir->serial)
2622                   if (tryReplace(&ir, ik))
2623                      break;
2624             }
2625          } else {
2626             DLLIST_FOR_EACH(&ops[ir->op], iter)
2627             {
2628                Instruction *ik = reinterpret_cast<Instruction *>(iter.get());
2629                if (tryReplace(&ir, ik))
2630                   break;
2631             }
2632          }
2633
2634          if (ir)
2635             ops[ir->op].insert(ir);
2636          else
2637             ++replaced;
2638       }
2639       for (unsigned int i = 0; i <= OP_LAST; ++i)
2640          ops[i].clear();
2641
2642    } while (replaced);
2643
2644    return true;
2645 }
2646
2647 // =============================================================================
2648
2649 // Remove computations of unused values.
2650 class DeadCodeElim : public Pass
2651 {
2652 public:
2653    bool buryAll(Program *);
2654
2655 private:
2656    virtual bool visit(BasicBlock *);
2657
2658    void checkSplitLoad(Instruction *ld); // for partially dead loads
2659
2660    unsigned int deadCount;
2661 };
2662
2663 bool
2664 DeadCodeElim::buryAll(Program *prog)
2665 {
2666    do {
2667       deadCount = 0;
2668       if (!this->run(prog, false, false))
2669          return false;
2670    } while (deadCount);
2671
2672    return true;
2673 }
2674
2675 bool
2676 DeadCodeElim::visit(BasicBlock *bb)
2677 {
2678    Instruction *next;
2679
2680    for (Instruction *i = bb->getFirst(); i; i = next) {
2681       next = i->next;
2682       if (i->isDead()) {
2683          ++deadCount;
2684          delete_Instruction(prog, i);
2685       } else
2686       if (i->defExists(1) && (i->op == OP_VFETCH || i->op == OP_LOAD)) {
2687          checkSplitLoad(i);
2688       } else
2689       if (i->defExists(0) && !i->getDef(0)->refCount()) {
2690          if (i->op == OP_ATOM ||
2691              i->op == OP_SUREDP ||
2692              i->op == OP_SUREDB)
2693             i->setDef(0, NULL);
2694       }
2695    }
2696    return true;
2697 }
2698
2699 void
2700 DeadCodeElim::checkSplitLoad(Instruction *ld1)
2701 {
2702    Instruction *ld2 = NULL; // can get at most 2 loads
2703    Value *def1[4];
2704    Value *def2[4];
2705    int32_t addr1, addr2;
2706    int32_t size1, size2;
2707    int d, n1, n2;
2708    uint32_t mask = 0xffffffff;
2709
2710    for (d = 0; ld1->defExists(d); ++d)
2711       if (!ld1->getDef(d)->refCount() && ld1->getDef(d)->reg.data.id < 0)
2712          mask &= ~(1 << d);
2713    if (mask == 0xffffffff)
2714       return;
2715
2716    addr1 = ld1->getSrc(0)->reg.data.offset;
2717    n1 = n2 = 0;
2718    size1 = size2 = 0;
2719    for (d = 0; ld1->defExists(d); ++d) {
2720       if (mask & (1 << d)) {
2721          if (size1 && (addr1 & 0x7))
2722             break;
2723          def1[n1] = ld1->getDef(d);
2724          size1 += def1[n1++]->reg.size;
2725       } else
2726       if (!n1) {
2727          addr1 += ld1->getDef(d)->reg.size;
2728       } else {
2729          break;
2730       }
2731    }
2732    for (addr2 = addr1 + size1; ld1->defExists(d); ++d) {
2733       if (mask & (1 << d)) {
2734          def2[n2] = ld1->getDef(d);
2735          size2 += def2[n2++]->reg.size;
2736       } else {
2737          assert(!n2);
2738          addr2 += ld1->getDef(d)->reg.size;
2739       }
2740    }
2741
2742    updateLdStOffset(ld1, addr1, func);
2743    ld1->setType(typeOfSize(size1));
2744    for (d = 0; d < 4; ++d)
2745       ld1->setDef(d, (d < n1) ? def1[d] : NULL);
2746
2747    if (!n2)
2748       return;
2749
2750    ld2 = cloneShallow(func, ld1);
2751    updateLdStOffset(ld2, addr2, func);
2752    ld2->setType(typeOfSize(size2));
2753    for (d = 0; d < 4; ++d)
2754       ld2->setDef(d, (d < n2) ? def2[d] : NULL);
2755
2756    ld1->bb->insertAfter(ld1, ld2);
2757 }
2758
2759 // =============================================================================
2760
2761 #define RUN_PASS(l, n, f)                       \
2762    if (level >= (l)) {                          \
2763       if (dbgFlags & NV50_IR_DEBUG_VERBOSE)     \
2764          INFO("PEEPHOLE: %s\n", #n);            \
2765       n pass;                                   \
2766       if (!pass.f(this))                        \
2767          return false;                          \
2768    }
2769
2770 bool
2771 Program::optimizeSSA(int level)
2772 {
2773    RUN_PASS(1, DeadCodeElim, buryAll);
2774    RUN_PASS(1, CopyPropagation, run);
2775    RUN_PASS(1, MergeSplits, run);
2776    RUN_PASS(2, GlobalCSE, run);
2777    RUN_PASS(1, LocalCSE, run);
2778    RUN_PASS(2, AlgebraicOpt, run);
2779    RUN_PASS(2, ModifierFolding, run); // before load propagation -> less checks
2780    RUN_PASS(1, ConstantFolding, foldAll);
2781    RUN_PASS(1, LoadPropagation, run);
2782    RUN_PASS(2, MemoryOpt, run);
2783    RUN_PASS(2, LocalCSE, run);
2784    RUN_PASS(0, DeadCodeElim, buryAll);
2785
2786    return true;
2787 }
2788
2789 bool
2790 Program::optimizePostRA(int level)
2791 {
2792    RUN_PASS(2, FlatteningPass, run);
2793    if (getTarget()->getChipset() < 0xc0)
2794       RUN_PASS(2, NV50PostRaConstantFolding, run);
2795
2796    return true;
2797 }
2798
2799 }