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