Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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