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