Subversion Repositories Kolibri OS

Rev

Go to most recent revision | 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 "nv50_ir.h"
  24. #include "nv50_ir_target.h"
  25.  
  26. #include <stack>
  27. #include <limits>
  28.  
  29. namespace nv50_ir {
  30.  
  31. #define MAX_REGISTER_FILE_SIZE 256
  32.  
  33. class RegisterSet
  34. {
  35. public:
  36.    RegisterSet(const Target *);
  37.  
  38.    void init(const Target *);
  39.    void reset(DataFile, bool resetMax = false);
  40.  
  41.    void periodicMask(DataFile f, uint32_t lock, uint32_t unlock);
  42.    void intersect(DataFile f, const RegisterSet *);
  43.  
  44.    bool assign(int32_t& reg, DataFile f, unsigned int size);
  45.    void release(DataFile f, int32_t reg, unsigned int size);
  46.    void occupy(DataFile f, int32_t reg, unsigned int size);
  47.    void occupy(const Value *);
  48.    void occupyMask(DataFile f, int32_t reg, uint8_t mask);
  49.    bool isOccupied(DataFile f, int32_t reg, unsigned int size) const;
  50.    bool testOccupy(const Value *);
  51.    bool testOccupy(DataFile f, int32_t reg, unsigned int size);
  52.  
  53.    inline int getMaxAssigned(DataFile f) const { return fill[f]; }
  54.  
  55.    inline unsigned int getFileSize(DataFile f, uint8_t regSize) const
  56.    {
  57.       if (restrictedGPR16Range && f == FILE_GPR && regSize == 2)
  58.          return (last[f] + 1) / 2;
  59.       return last[f] + 1;
  60.    }
  61.  
  62.    inline unsigned int units(DataFile f, unsigned int size) const
  63.    {
  64.       return size >> unit[f];
  65.    }
  66.    // for regs of size >= 4, id is counted in 4-byte words (like nv50/c0 binary)
  67.    inline unsigned int idToBytes(const Value *v) const
  68.    {
  69.       return v->reg.data.id * MIN2(v->reg.size, 4);
  70.    }
  71.    inline unsigned int idToUnits(const Value *v) const
  72.    {
  73.       return units(v->reg.file, idToBytes(v));
  74.    }
  75.    inline int bytesToId(Value *v, unsigned int bytes) const
  76.    {
  77.       if (v->reg.size < 4)
  78.          return units(v->reg.file, bytes);
  79.       return bytes / 4;
  80.    }
  81.    inline int unitsToId(DataFile f, int u, uint8_t size) const
  82.    {
  83.       if (u < 0)
  84.          return -1;
  85.       return (size < 4) ? u : ((u << unit[f]) / 4);
  86.    }
  87.  
  88.    void print() const;
  89.  
  90. private:
  91.    BitSet bits[LAST_REGISTER_FILE + 1];
  92.  
  93.    int unit[LAST_REGISTER_FILE + 1]; // log2 of allocation granularity
  94.  
  95.    int last[LAST_REGISTER_FILE + 1];
  96.    int fill[LAST_REGISTER_FILE + 1];
  97.  
  98.    const bool restrictedGPR16Range;
  99. };
  100.  
  101. void
  102. RegisterSet::reset(DataFile f, bool resetMax)
  103. {
  104.    bits[f].fill(0);
  105.    if (resetMax)
  106.       fill[f] = -1;
  107. }
  108.  
  109. void
  110. RegisterSet::init(const Target *targ)
  111. {
  112.    for (unsigned int rf = 0; rf <= FILE_ADDRESS; ++rf) {
  113.       DataFile f = static_cast<DataFile>(rf);
  114.       last[rf] = targ->getFileSize(f) - 1;
  115.       unit[rf] = targ->getFileUnit(f);
  116.       fill[rf] = -1;
  117.       assert(last[rf] < MAX_REGISTER_FILE_SIZE);
  118.       bits[rf].allocate(last[rf] + 1, true);
  119.    }
  120. }
  121.  
  122. RegisterSet::RegisterSet(const Target *targ)
  123.   : restrictedGPR16Range(targ->getChipset() < 0xc0)
  124. {
  125.    init(targ);
  126.    for (unsigned int i = 0; i <= LAST_REGISTER_FILE; ++i)
  127.       reset(static_cast<DataFile>(i));
  128. }
  129.  
  130. void
  131. RegisterSet::periodicMask(DataFile f, uint32_t lock, uint32_t unlock)
  132. {
  133.    bits[f].periodicMask32(lock, unlock);
  134. }
  135.  
  136. void
  137. RegisterSet::intersect(DataFile f, const RegisterSet *set)
  138. {
  139.    bits[f] |= set->bits[f];
  140. }
  141.  
  142. void
  143. RegisterSet::print() const
  144. {
  145.    INFO("GPR:");
  146.    bits[FILE_GPR].print();
  147.    INFO("\n");
  148. }
  149.  
  150. bool
  151. RegisterSet::assign(int32_t& reg, DataFile f, unsigned int size)
  152. {
  153.    reg = bits[f].findFreeRange(size);
  154.    if (reg < 0)
  155.       return false;
  156.    fill[f] = MAX2(fill[f], (int32_t)(reg + size - 1));
  157.    return true;
  158. }
  159.  
  160. bool
  161. RegisterSet::isOccupied(DataFile f, int32_t reg, unsigned int size) const
  162. {
  163.    return bits[f].testRange(reg, size);
  164. }
  165.  
  166. void
  167. RegisterSet::occupy(const Value *v)
  168. {
  169.    occupy(v->reg.file, idToUnits(v), v->reg.size >> unit[v->reg.file]);
  170. }
  171.  
  172. void
  173. RegisterSet::occupyMask(DataFile f, int32_t reg, uint8_t mask)
  174. {
  175.    bits[f].setMask(reg & ~31, static_cast<uint32_t>(mask) << (reg % 32));
  176. }
  177.  
  178. void
  179. RegisterSet::occupy(DataFile f, int32_t reg, unsigned int size)
  180. {
  181.    bits[f].setRange(reg, size);
  182.  
  183.    INFO_DBG(0, REG_ALLOC, "reg occupy: %u[%i] %u\n", f, reg, size);
  184.  
  185.    fill[f] = MAX2(fill[f], (int32_t)(reg + size - 1));
  186. }
  187.  
  188. bool
  189. RegisterSet::testOccupy(const Value *v)
  190. {
  191.    return testOccupy(v->reg.file,
  192.                      idToUnits(v), v->reg.size >> unit[v->reg.file]);
  193. }
  194.  
  195. bool
  196. RegisterSet::testOccupy(DataFile f, int32_t reg, unsigned int size)
  197. {
  198.    if (isOccupied(f, reg, size))
  199.       return false;
  200.    occupy(f, reg, size);
  201.    return true;
  202. }
  203.  
  204. void
  205. RegisterSet::release(DataFile f, int32_t reg, unsigned int size)
  206. {
  207.    bits[f].clrRange(reg, size);
  208.  
  209.    INFO_DBG(0, REG_ALLOC, "reg release: %u[%i] %u\n", f, reg, size);
  210. }
  211.  
  212. class RegAlloc
  213. {
  214. public:
  215.    RegAlloc(Program *program) : prog(program), sequence(0) { }
  216.  
  217.    bool exec();
  218.    bool execFunc();
  219.  
  220. private:
  221.    class PhiMovesPass : public Pass {
  222.    private:
  223.       virtual bool visit(BasicBlock *);
  224.       inline bool needNewElseBlock(BasicBlock *b, BasicBlock *p);
  225.    };
  226.  
  227.    class ArgumentMovesPass : public Pass {
  228.    private:
  229.       virtual bool visit(BasicBlock *);
  230.    };
  231.  
  232.    class BuildIntervalsPass : public Pass {
  233.    private:
  234.       virtual bool visit(BasicBlock *);
  235.       void collectLiveValues(BasicBlock *);
  236.       void addLiveRange(Value *, const BasicBlock *, int end);
  237.    };
  238.  
  239.    class InsertConstraintsPass : public Pass {
  240.    public:
  241.       bool exec(Function *func);
  242.    private:
  243.       virtual bool visit(BasicBlock *);
  244.  
  245.       bool insertConstraintMoves();
  246.  
  247.       void condenseDefs(Instruction *);
  248.       void condenseSrcs(Instruction *, const int first, const int last);
  249.  
  250.       void addHazard(Instruction *i, const ValueRef *src);
  251.       void textureMask(TexInstruction *);
  252.       void addConstraint(Instruction *, int s, int n);
  253.       bool detectConflict(Instruction *, int s);
  254.  
  255.       // target specific functions, TODO: put in subclass or Target
  256.       void texConstraintNV50(TexInstruction *);
  257.       void texConstraintNVC0(TexInstruction *);
  258.       void texConstraintNVE0(TexInstruction *);
  259.  
  260.       std::list<Instruction *> constrList;
  261.  
  262.       const Target *targ;
  263.    };
  264.  
  265.    bool buildLiveSets(BasicBlock *);
  266.  
  267. private:
  268.    Program *prog;
  269.    Function *func;
  270.  
  271.    // instructions in control flow / chronological order
  272.    ArrayList insns;
  273.  
  274.    int sequence; // for manual passes through CFG
  275. };
  276.  
  277. typedef std::pair<Value *, Value *> ValuePair;
  278.  
  279. class SpillCodeInserter
  280. {
  281. public:
  282.    SpillCodeInserter(Function *fn) : func(fn), stackSize(0), stackBase(0) { }
  283.  
  284.    bool run(const std::list<ValuePair>&);
  285.  
  286.    Symbol *assignSlot(const Interval&, const unsigned int size);
  287.    inline int32_t getStackSize() const { return stackSize; }
  288.  
  289. private:
  290.    Function *func;
  291.  
  292.    struct SpillSlot
  293.    {
  294.       Interval occup;
  295.       std::list<Value *> residents; // needed to recalculate occup
  296.       Symbol *sym;
  297.       int32_t offset;
  298.       inline uint8_t size() const { return sym->reg.size; }
  299.    };
  300.    std::list<SpillSlot> slots;
  301.    int32_t stackSize;
  302.    int32_t stackBase;
  303.  
  304.    LValue *unspill(Instruction *usei, LValue *, Value *slot);
  305.    void spill(Instruction *defi, Value *slot, LValue *);
  306. };
  307.  
  308. void
  309. RegAlloc::BuildIntervalsPass::addLiveRange(Value *val,
  310.                                            const BasicBlock *bb,
  311.                                            int end)
  312. {
  313.    Instruction *insn = val->getUniqueInsn();
  314.  
  315.    if (!insn)
  316.       insn = bb->getFirst();
  317.  
  318.    assert(bb->getFirst()->serial <= bb->getExit()->serial);
  319.    assert(bb->getExit()->serial + 1 >= end);
  320.  
  321.    int begin = insn->serial;
  322.    if (begin < bb->getEntry()->serial || begin > bb->getExit()->serial)
  323.       begin = bb->getEntry()->serial;
  324.  
  325.    INFO_DBG(prog->dbgFlags, REG_ALLOC, "%%%i <- live range [%i(%i), %i)\n",
  326.             val->id, begin, insn->serial, end);
  327.  
  328.    if (begin != end) // empty ranges are only added as hazards for fixed regs
  329.       val->livei.extend(begin, end);
  330. }
  331.  
  332. bool
  333. RegAlloc::PhiMovesPass::needNewElseBlock(BasicBlock *b, BasicBlock *p)
  334. {
  335.    if (b->cfg.incidentCount() <= 1)
  336.       return false;
  337.  
  338.    int n = 0;
  339.    for (Graph::EdgeIterator ei = p->cfg.outgoing(); !ei.end(); ei.next())
  340.       if (ei.getType() == Graph::Edge::TREE ||
  341.           ei.getType() == Graph::Edge::FORWARD)
  342.          ++n;
  343.    return (n == 2);
  344. }
  345.  
  346. // For each operand of each PHI in b, generate a new value by inserting a MOV
  347. // at the end of the block it is coming from and replace the operand with its
  348. // result. This eliminates liveness conflicts and enables us to let values be
  349. // copied to the right register if such a conflict exists nonetheless.
  350. //
  351. // These MOVs are also crucial in making sure the live intervals of phi srces
  352. // are extended until the end of the loop, since they are not included in the
  353. // live-in sets.
  354. bool
  355. RegAlloc::PhiMovesPass::visit(BasicBlock *bb)
  356. {
  357.    Instruction *phi, *mov;
  358.    BasicBlock *pb, *pn;
  359.  
  360.    std::stack<BasicBlock *> stack;
  361.  
  362.    for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) {
  363.       pb = BasicBlock::get(ei.getNode());
  364.       assert(pb);
  365.       if (needNewElseBlock(bb, pb))
  366.          stack.push(pb);
  367.    }
  368.    while (!stack.empty()) {
  369.       pb = stack.top();
  370.       pn = new BasicBlock(func);
  371.       stack.pop();
  372.  
  373.       pb->cfg.detach(&bb->cfg);
  374.       pb->cfg.attach(&pn->cfg, Graph::Edge::TREE);
  375.       pn->cfg.attach(&bb->cfg, Graph::Edge::FORWARD);
  376.  
  377.       assert(pb->getExit()->op != OP_CALL);
  378.       if (pb->getExit()->asFlow()->target.bb == bb)
  379.          pb->getExit()->asFlow()->target.bb = pn;
  380.    }
  381.  
  382.    // insert MOVs (phi->src(j) should stem from j-th in-BB)
  383.    int j = 0;
  384.    for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) {
  385.       pb = BasicBlock::get(ei.getNode());
  386.       if (!pb->isTerminated())
  387.          pb->insertTail(new_FlowInstruction(func, OP_BRA, bb));
  388.  
  389.       for (phi = bb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) {
  390.          mov = new_Instruction(func, OP_MOV, TYPE_U32);
  391.  
  392.          mov->setSrc(0, phi->getSrc(j));
  393.          mov->setDef(0, new_LValue(func, phi->getDef(0)->asLValue()));
  394.          phi->setSrc(j, mov->getDef(0));
  395.  
  396.          pb->insertBefore(pb->getExit(), mov);
  397.       }
  398.       ++j;
  399.    }
  400.  
  401.    return true;
  402. }
  403.  
  404. bool
  405. RegAlloc::ArgumentMovesPass::visit(BasicBlock *bb)
  406. {
  407.    // Bind function call inputs/outputs to the same physical register
  408.    // the callee uses, inserting moves as appropriate for the case a
  409.    // conflict arises.
  410.    for (Instruction *i = bb->getEntry(); i; i = i->next) {
  411.       FlowInstruction *cal = i->asFlow();
  412.       // TODO: Handle indirect calls.
  413.       // Right now they should only be generated for builtins.
  414.       if (!cal || cal->op != OP_CALL || cal->builtin || cal->indirect)
  415.          continue;
  416.       RegisterSet clobberSet(prog->getTarget());
  417.  
  418.       // Bind input values.
  419.       for (int s = cal->indirect ? 1 : 0; cal->srcExists(s); ++s) {
  420.          const int t = cal->indirect ? (s - 1) : s;
  421.          LValue *tmp = new_LValue(func, cal->getSrc(s)->asLValue());
  422.          tmp->reg.data.id = cal->target.fn->ins[t].rep()->reg.data.id;
  423.  
  424.          Instruction *mov =
  425.             new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size));
  426.          mov->setDef(0, tmp);
  427.          mov->setSrc(0, cal->getSrc(s));
  428.          cal->setSrc(s, tmp);
  429.  
  430.          bb->insertBefore(cal, mov);
  431.       }
  432.  
  433.       // Bind output values.
  434.       for (int d = 0; cal->defExists(d); ++d) {
  435.          LValue *tmp = new_LValue(func, cal->getDef(d)->asLValue());
  436.          tmp->reg.data.id = cal->target.fn->outs[d].rep()->reg.data.id;
  437.  
  438.          Instruction *mov =
  439.             new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size));
  440.          mov->setSrc(0, tmp);
  441.          mov->setDef(0, cal->getDef(d));
  442.          cal->setDef(d, tmp);
  443.  
  444.          bb->insertAfter(cal, mov);
  445.          clobberSet.occupy(tmp);
  446.       }
  447.  
  448.       // Bind clobbered values.
  449.       for (std::deque<Value *>::iterator it = cal->target.fn->clobbers.begin();
  450.            it != cal->target.fn->clobbers.end();
  451.            ++it) {
  452.          if (clobberSet.testOccupy(*it)) {
  453.             Value *tmp = new_LValue(func, (*it)->asLValue());
  454.             tmp->reg.data.id = (*it)->reg.data.id;
  455.             cal->setDef(cal->defCount(), tmp);
  456.          }
  457.       }
  458.    }
  459.  
  460.    // Update the clobber set of the function.
  461.    if (BasicBlock::get(func->cfgExit) == bb) {
  462.       func->buildDefSets();
  463.       for (unsigned int i = 0; i < bb->defSet.getSize(); ++i)
  464.          if (bb->defSet.test(i))
  465.             func->clobbers.push_back(func->getLValue(i));
  466.    }
  467.  
  468.    return true;
  469. }
  470.  
  471. // Build the set of live-in variables of bb.
  472. bool
  473. RegAlloc::buildLiveSets(BasicBlock *bb)
  474. {
  475.    Function *f = bb->getFunction();
  476.    BasicBlock *bn;
  477.    Instruction *i;
  478.    unsigned int s, d;
  479.  
  480.    INFO_DBG(prog->dbgFlags, REG_ALLOC, "buildLiveSets(BB:%i)\n", bb->getId());
  481.  
  482.    bb->liveSet.allocate(func->allLValues.getSize(), false);
  483.  
  484.    int n = 0;
  485.    for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
  486.       bn = BasicBlock::get(ei.getNode());
  487.       if (bn == bb)
  488.          continue;
  489.       if (bn->cfg.visit(sequence))
  490.          if (!buildLiveSets(bn))
  491.             return false;
  492.       if (n++ || bb->liveSet.marker)
  493.          bb->liveSet |= bn->liveSet;
  494.       else
  495.          bb->liveSet = bn->liveSet;
  496.    }
  497.    if (!n && !bb->liveSet.marker)
  498.       bb->liveSet.fill(0);
  499.    bb->liveSet.marker = true;
  500.  
  501.    if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) {
  502.       INFO("BB:%i live set of out blocks:\n", bb->getId());
  503.       bb->liveSet.print();
  504.    }
  505.  
  506.    // if (!bb->getEntry())
  507.    //   return true;
  508.  
  509.    if (bb == BasicBlock::get(f->cfgExit)) {
  510.       for (std::deque<ValueRef>::iterator it = f->outs.begin();
  511.            it != f->outs.end(); ++it) {
  512.          assert(it->get()->asLValue());
  513.          bb->liveSet.set(it->get()->id);
  514.       }
  515.    }
  516.  
  517.    for (i = bb->getExit(); i && i != bb->getEntry()->prev; i = i->prev) {
  518.       for (d = 0; i->defExists(d); ++d)
  519.          bb->liveSet.clr(i->getDef(d)->id);
  520.       for (s = 0; i->srcExists(s); ++s)
  521.          if (i->getSrc(s)->asLValue())
  522.             bb->liveSet.set(i->getSrc(s)->id);
  523.    }
  524.    for (i = bb->getPhi(); i && i->op == OP_PHI; i = i->next)
  525.       bb->liveSet.clr(i->getDef(0)->id);
  526.  
  527.    if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) {
  528.       INFO("BB:%i live set after propagation:\n", bb->getId());
  529.       bb->liveSet.print();
  530.    }
  531.  
  532.    return true;
  533. }
  534.  
  535. void
  536. RegAlloc::BuildIntervalsPass::collectLiveValues(BasicBlock *bb)
  537. {
  538.    BasicBlock *bbA = NULL, *bbB = NULL;
  539.  
  540.    if (bb->cfg.outgoingCount()) {
  541.       // trickery to save a loop of OR'ing liveSets
  542.       // aliasing works fine with BitSet::setOr
  543.       for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
  544.          if (ei.getType() == Graph::Edge::DUMMY)
  545.             continue;
  546.          if (bbA) {
  547.             bb->liveSet.setOr(&bbA->liveSet, &bbB->liveSet);
  548.             bbA = bb;
  549.          } else {
  550.             bbA = bbB;
  551.          }
  552.          bbB = BasicBlock::get(ei.getNode());
  553.       }
  554.       bb->liveSet.setOr(&bbB->liveSet, bbA ? &bbA->liveSet : NULL);
  555.    } else
  556.    if (bb->cfg.incidentCount()) {
  557.       bb->liveSet.fill(0);
  558.    }
  559. }
  560.  
  561. bool
  562. RegAlloc::BuildIntervalsPass::visit(BasicBlock *bb)
  563. {
  564.    collectLiveValues(bb);
  565.  
  566.    INFO_DBG(prog->dbgFlags, REG_ALLOC, "BuildIntervals(BB:%i)\n", bb->getId());
  567.  
  568.    // go through out blocks and delete phi sources that do not originate from
  569.    // the current block from the live set
  570.    for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
  571.       BasicBlock *out = BasicBlock::get(ei.getNode());
  572.  
  573.       for (Instruction *i = out->getPhi(); i && i->op == OP_PHI; i = i->next) {
  574.          bb->liveSet.clr(i->getDef(0)->id);
  575.  
  576.          for (int s = 0; i->srcExists(s); ++s) {
  577.             assert(i->src(s).getInsn());
  578.             if (i->getSrc(s)->getUniqueInsn()->bb == bb) // XXX: reachableBy ?
  579.                bb->liveSet.set(i->getSrc(s)->id);
  580.             else
  581.                bb->liveSet.clr(i->getSrc(s)->id);
  582.          }
  583.       }
  584.    }
  585.  
  586.    // remaining live-outs are live until end
  587.    if (bb->getExit()) {
  588.       for (unsigned int j = 0; j < bb->liveSet.getSize(); ++j)
  589.          if (bb->liveSet.test(j))
  590.             addLiveRange(func->getLValue(j), bb, bb->getExit()->serial + 1);
  591.    }
  592.  
  593.    for (Instruction *i = bb->getExit(); i && i->op != OP_PHI; i = i->prev) {
  594.       for (int d = 0; i->defExists(d); ++d) {
  595.          bb->liveSet.clr(i->getDef(d)->id);
  596.          if (i->getDef(d)->reg.data.id >= 0) // add hazard for fixed regs
  597.             i->getDef(d)->livei.extend(i->serial, i->serial);
  598.       }
  599.  
  600.       for (int s = 0; i->srcExists(s); ++s) {
  601.          if (!i->getSrc(s)->asLValue())
  602.             continue;
  603.          if (!bb->liveSet.test(i->getSrc(s)->id)) {
  604.             bb->liveSet.set(i->getSrc(s)->id);
  605.             addLiveRange(i->getSrc(s), bb, i->serial);
  606.          }
  607.       }
  608.    }
  609.  
  610.    if (bb == BasicBlock::get(func->cfg.getRoot())) {
  611.       for (std::deque<ValueDef>::iterator it = func->ins.begin();
  612.            it != func->ins.end(); ++it) {
  613.          if (it->get()->reg.data.id >= 0) // add hazard for fixed regs
  614.             it->get()->livei.extend(0, 1);
  615.       }
  616.    }
  617.  
  618.    return true;
  619. }
  620.  
  621.  
  622. #define JOIN_MASK_PHI        (1 << 0)
  623. #define JOIN_MASK_UNION      (1 << 1)
  624. #define JOIN_MASK_MOV        (1 << 2)
  625. #define JOIN_MASK_TEX        (1 << 3)
  626.  
  627. class GCRA
  628. {
  629. public:
  630.    GCRA(Function *, SpillCodeInserter&);
  631.    ~GCRA();
  632.  
  633.    bool allocateRegisters(ArrayList& insns);
  634.  
  635.    void printNodeInfo() const;
  636.  
  637. private:
  638.    class RIG_Node : public Graph::Node
  639.    {
  640.    public:
  641.       RIG_Node();
  642.  
  643.       void init(const RegisterSet&, LValue *);
  644.  
  645.       void addInterference(RIG_Node *);
  646.       void addRegPreference(RIG_Node *);
  647.  
  648.       inline LValue *getValue() const
  649.       {
  650.          return reinterpret_cast<LValue *>(data);
  651.       }
  652.       inline void setValue(LValue *lval) { data = lval; }
  653.  
  654.       inline uint8_t getCompMask() const
  655.       {
  656.          return ((1 << colors) - 1) << (reg & 7);
  657.       }
  658.  
  659.       static inline RIG_Node *get(const Graph::EdgeIterator& ei)
  660.       {
  661.          return static_cast<RIG_Node *>(ei.getNode());
  662.       }
  663.  
  664.    public:
  665.       uint32_t degree;
  666.       uint16_t degreeLimit; // if deg < degLimit, node is trivially colourable
  667.       uint16_t colors;
  668.  
  669.       DataFile f;
  670.       int32_t reg;
  671.  
  672.       float weight;
  673.  
  674.       // list pointers for simplify() phase
  675.       RIG_Node *next;
  676.       RIG_Node *prev;
  677.  
  678.       // union of the live intervals of all coalesced values (we want to retain
  679.       //  the separate intervals for testing interference of compound values)
  680.       Interval livei;
  681.  
  682.       std::list<RIG_Node *> prefRegs;
  683.    };
  684.  
  685. private:
  686.    inline RIG_Node *getNode(const LValue *v) const { return &nodes[v->id]; }
  687.  
  688.    void buildRIG(ArrayList&);
  689.    bool coalesce(ArrayList&);
  690.    bool doCoalesce(ArrayList&, unsigned int mask);
  691.    void calculateSpillWeights();
  692.    void simplify();
  693.    bool selectRegisters();
  694.    void cleanup(const bool success);
  695.  
  696.    void simplifyEdge(RIG_Node *, RIG_Node *);
  697.    void simplifyNode(RIG_Node *);
  698.  
  699.    bool coalesceValues(Value *, Value *, bool force);
  700.    void resolveSplitsAndMerges();
  701.    void makeCompound(Instruction *, bool isSplit);
  702.  
  703.    inline void checkInterference(const RIG_Node *, Graph::EdgeIterator&);
  704.  
  705.    inline void insertOrderedTail(std::list<RIG_Node *>&, RIG_Node *);
  706.    void checkList(std::list<RIG_Node *>&);
  707.  
  708. private:
  709.    std::stack<uint32_t> stack;
  710.  
  711.    // list headers for simplify() phase
  712.    RIG_Node lo[2];
  713.    RIG_Node hi;
  714.  
  715.    Graph RIG;
  716.    RIG_Node *nodes;
  717.    unsigned int nodeCount;
  718.  
  719.    Function *func;
  720.    Program *prog;
  721.  
  722.    static uint8_t relDegree[17][17];
  723.  
  724.    RegisterSet regs;
  725.  
  726.    // need to fixup register id for participants of OP_MERGE/SPLIT
  727.    std::list<Instruction *> merges;
  728.    std::list<Instruction *> splits;
  729.  
  730.    SpillCodeInserter& spill;
  731.    std::list<ValuePair> mustSpill;
  732. };
  733.  
  734. uint8_t GCRA::relDegree[17][17];
  735.  
  736. GCRA::RIG_Node::RIG_Node() : Node(NULL), next(this), prev(this)
  737. {
  738.    colors = 0;
  739. }
  740.  
  741. void
  742. GCRA::printNodeInfo() const
  743. {
  744.    for (unsigned int i = 0; i < nodeCount; ++i) {
  745.       if (!nodes[i].colors)
  746.          continue;
  747.       INFO("RIG_Node[%%%i]($[%u]%i): %u colors, weight %f, deg %u/%u\n X",
  748.            i,
  749.            nodes[i].f,nodes[i].reg,nodes[i].colors,
  750.            nodes[i].weight,
  751.            nodes[i].degree, nodes[i].degreeLimit);
  752.  
  753.       for (Graph::EdgeIterator ei = nodes[i].outgoing(); !ei.end(); ei.next())
  754.          INFO(" %%%i", RIG_Node::get(ei)->getValue()->id);
  755.       for (Graph::EdgeIterator ei = nodes[i].incident(); !ei.end(); ei.next())
  756.          INFO(" %%%i", RIG_Node::get(ei)->getValue()->id);
  757.       INFO("\n");
  758.    }
  759. }
  760.  
  761. void
  762. GCRA::RIG_Node::init(const RegisterSet& regs, LValue *lval)
  763. {
  764.    setValue(lval);
  765.    if (lval->reg.data.id >= 0)
  766.       lval->noSpill = lval->fixedReg = 1;
  767.  
  768.    colors = regs.units(lval->reg.file, lval->reg.size);
  769.    f = lval->reg.file;
  770.    reg = -1;
  771.    if (lval->reg.data.id >= 0)
  772.       reg = regs.idToUnits(lval);
  773.  
  774.    weight = std::numeric_limits<float>::infinity();
  775.    degree = 0;
  776.    degreeLimit = regs.getFileSize(f, lval->reg.size);
  777.  
  778.    livei.insert(lval->livei);
  779. }
  780.  
  781. bool
  782. GCRA::coalesceValues(Value *dst, Value *src, bool force)
  783. {
  784.    LValue *rep = dst->join->asLValue();
  785.    LValue *val = src->join->asLValue();
  786.  
  787.    if (!force && val->reg.data.id >= 0) {
  788.       rep = src->join->asLValue();
  789.       val = dst->join->asLValue();
  790.    }
  791.    RIG_Node *nRep = &nodes[rep->id];
  792.    RIG_Node *nVal = &nodes[val->id];
  793.  
  794.    if (src->reg.file != dst->reg.file) {
  795.       if (!force)
  796.          return false;
  797.       WARN("forced coalescing of values in different files !\n");
  798.    }
  799.    if (!force && dst->reg.size != src->reg.size)
  800.       return false;
  801.  
  802.    if ((rep->reg.data.id >= 0) && (rep->reg.data.id != val->reg.data.id)) {
  803.       if (force) {
  804.          if (val->reg.data.id >= 0)
  805.             WARN("forced coalescing of values in different fixed regs !\n");
  806.       } else {
  807.          if (val->reg.data.id >= 0)
  808.             return false;
  809.          // make sure that there is no overlap with the fixed register of rep
  810.          for (ArrayList::Iterator it = func->allLValues.iterator();
  811.               !it.end(); it.next()) {
  812.             Value *reg = reinterpret_cast<Value *>(it.get())->asLValue();
  813.             assert(reg);
  814.             if (reg->interfers(rep) && reg->livei.overlaps(nVal->livei))
  815.                return false;
  816.          }
  817.       }
  818.    }
  819.  
  820.    if (!force && nRep->livei.overlaps(nVal->livei))
  821.       return false;
  822.  
  823.    INFO_DBG(prog->dbgFlags, REG_ALLOC, "joining %%%i($%i) <- %%%i\n",
  824.             rep->id, rep->reg.data.id, val->id);
  825.  
  826.    // set join pointer of all values joined with val
  827.    for (Value::DefIterator def = val->defs.begin(); def != val->defs.end();
  828.         ++def)
  829.       (*def)->get()->join = rep;
  830.    assert(rep->join == rep && val->join == rep);
  831.  
  832.    // add val's definitions to rep and extend the live interval of its RIG node
  833.    rep->defs.insert(rep->defs.end(), val->defs.begin(), val->defs.end());
  834.    nRep->livei.unify(nVal->livei);
  835.    return true;
  836. }
  837.  
  838. bool
  839. GCRA::coalesce(ArrayList& insns)
  840. {
  841.    bool ret = doCoalesce(insns, JOIN_MASK_PHI);
  842.    if (!ret)
  843.       return false;
  844.    switch (func->getProgram()->getTarget()->getChipset() & ~0xf) {
  845.    case 0x50:
  846.    case 0x80:
  847.    case 0x90:
  848.    case 0xa0:
  849.       ret = doCoalesce(insns, JOIN_MASK_UNION | JOIN_MASK_TEX);
  850.       break;
  851.    case 0xc0:
  852.    case 0xd0:
  853.    case 0xe0:
  854.       ret = doCoalesce(insns, JOIN_MASK_UNION);
  855.       break;
  856.    default:
  857.       break;
  858.    }
  859.    if (!ret)
  860.       return false;
  861.    return doCoalesce(insns, JOIN_MASK_MOV);
  862. }
  863.  
  864. static inline uint8_t makeCompMask(int compSize, int base, int size)
  865. {
  866.    uint8_t m = ((1 << size) - 1) << base;
  867.  
  868.    switch (compSize) {
  869.    case 1:
  870.       return 0xff;
  871.    case 2:
  872.       m |= (m << 2);
  873.       return (m << 4) | m;
  874.    case 3:
  875.    case 4:
  876.       return (m << 4) | m;
  877.    default:
  878.       assert(compSize <= 8);
  879.       return m;
  880.    }
  881. }
  882.  
  883. // Used when coalescing moves. The non-compound value will become one, e.g.:
  884. // mov b32 $r0 $r2            / merge b64 $r0d { $r0 $r1 }
  885. // split b64 { $r0 $r1 } $r0d / mov b64 $r0d f64 $r2d
  886. static inline void copyCompound(Value *dst, Value *src)
  887. {
  888.    LValue *ldst = dst->asLValue();
  889.    LValue *lsrc = src->asLValue();
  890.  
  891.    if (ldst->compound && !lsrc->compound) {
  892.       LValue *swap = lsrc;
  893.       lsrc = ldst;
  894.       ldst = swap;
  895.    }
  896.  
  897.    ldst->compound = lsrc->compound;
  898.    ldst->compMask = lsrc->compMask;
  899. }
  900.  
  901. void
  902. GCRA::makeCompound(Instruction *insn, bool split)
  903. {
  904.    LValue *rep = (split ? insn->getSrc(0) : insn->getDef(0))->asLValue();
  905.  
  906.    if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) {
  907.       INFO("makeCompound(split = %i): ", split);
  908.       insn->print();
  909.    }
  910.  
  911.    const unsigned int size = getNode(rep)->colors;
  912.    unsigned int base = 0;
  913.  
  914.    if (!rep->compound)
  915.       rep->compMask = 0xff;
  916.    rep->compound = 1;
  917.  
  918.    for (int c = 0; split ? insn->defExists(c) : insn->srcExists(c); ++c) {
  919.       LValue *val = (split ? insn->getDef(c) : insn->getSrc(c))->asLValue();
  920.  
  921.       val->compound = 1;
  922.       if (!val->compMask)
  923.          val->compMask = 0xff;
  924.       val->compMask &= makeCompMask(size, base, getNode(val)->colors);
  925.       assert(val->compMask);
  926.  
  927.       INFO_DBG(prog->dbgFlags, REG_ALLOC, "compound: %%%i:%02x <- %%%i:%02x\n",
  928.            rep->id, rep->compMask, val->id, val->compMask);
  929.  
  930.       base += getNode(val)->colors;
  931.    }
  932.    assert(base == size);
  933. }
  934.  
  935. bool
  936. GCRA::doCoalesce(ArrayList& insns, unsigned int mask)
  937. {
  938.    int c, n;
  939.  
  940.    for (n = 0; n < insns.getSize(); ++n) {
  941.       Instruction *i;
  942.       Instruction *insn = reinterpret_cast<Instruction *>(insns.get(n));
  943.  
  944.       switch (insn->op) {
  945.       case OP_PHI:
  946.          if (!(mask & JOIN_MASK_PHI))
  947.             break;
  948.          for (c = 0; insn->srcExists(c); ++c)
  949.             if (!coalesceValues(insn->getDef(0), insn->getSrc(c), false)) {
  950.                // this is bad
  951.                ERROR("failed to coalesce phi operands\n");
  952.                return false;
  953.             }
  954.          break;
  955.       case OP_UNION:
  956.       case OP_MERGE:
  957.          if (!(mask & JOIN_MASK_UNION))
  958.             break;
  959.          for (c = 0; insn->srcExists(c); ++c)
  960.             coalesceValues(insn->getDef(0), insn->getSrc(c), true);
  961.          if (insn->op == OP_MERGE) {
  962.             merges.push_back(insn);
  963.             if (insn->srcExists(1))
  964.                makeCompound(insn, false);
  965.          }
  966.          break;
  967.       case OP_SPLIT:
  968.          if (!(mask & JOIN_MASK_UNION))
  969.             break;
  970.          splits.push_back(insn);
  971.          for (c = 0; insn->defExists(c); ++c)
  972.             coalesceValues(insn->getSrc(0), insn->getDef(c), true);
  973.          makeCompound(insn, true);
  974.          break;
  975.       case OP_MOV:
  976.          if (!(mask & JOIN_MASK_MOV))
  977.             break;
  978.          i = NULL;
  979.          if (!insn->getDef(0)->uses.empty())
  980.             i = insn->getDef(0)->uses.front()->getInsn();
  981.          // if this is a contraint-move there will only be a single use
  982.          if (i && i->op == OP_MERGE) // do we really still need this ?
  983.             break;
  984.          i = insn->getSrc(0)->getUniqueInsn();
  985.          if (i && !i->constrainedDefs()) {
  986.             if (coalesceValues(insn->getDef(0), insn->getSrc(0), false))
  987.                copyCompound(insn->getSrc(0), insn->getDef(0));
  988.          }
  989.          break;
  990.       case OP_TEX:
  991.       case OP_TXB:
  992.       case OP_TXL:
  993.       case OP_TXF:
  994.       case OP_TXQ:
  995.       case OP_TXD:
  996.       case OP_TXG:
  997.       case OP_TEXCSAA:
  998.          if (!(mask & JOIN_MASK_TEX))
  999.             break;
  1000.          for (c = 0; insn->srcExists(c) && c != insn->predSrc; ++c)
  1001.             coalesceValues(insn->getDef(c), insn->getSrc(c), true);
  1002.          break;
  1003.       default:
  1004.          break;
  1005.       }
  1006.    }
  1007.    return true;
  1008. }
  1009.  
  1010. void
  1011. GCRA::RIG_Node::addInterference(RIG_Node *node)
  1012. {
  1013.    this->degree += relDegree[node->colors][colors];
  1014.    node->degree += relDegree[colors][node->colors];
  1015.  
  1016.    this->attach(node, Graph::Edge::CROSS);
  1017. }
  1018.  
  1019. void
  1020. GCRA::RIG_Node::addRegPreference(RIG_Node *node)
  1021. {
  1022.    prefRegs.push_back(node);
  1023. }
  1024.  
  1025. GCRA::GCRA(Function *fn, SpillCodeInserter& spill) :
  1026.    func(fn),
  1027.    regs(fn->getProgram()->getTarget()),
  1028.    spill(spill)
  1029. {
  1030.    prog = func->getProgram();
  1031.  
  1032.    // initialize relative degrees array - i takes away from j
  1033.    for (int i = 1; i <= 16; ++i)
  1034.       for (int j = 1; j <= 16; ++j)
  1035.          relDegree[i][j] = j * ((i + j - 1) / j);
  1036. }
  1037.  
  1038. GCRA::~GCRA()
  1039. {
  1040.    if (nodes)
  1041.       delete[] nodes;
  1042. }
  1043.  
  1044. void
  1045. GCRA::checkList(std::list<RIG_Node *>& lst)
  1046. {
  1047.    GCRA::RIG_Node *prev = NULL;
  1048.  
  1049.    for (std::list<RIG_Node *>::iterator it = lst.begin();
  1050.         it != lst.end();
  1051.         ++it) {
  1052.       assert((*it)->getValue()->join == (*it)->getValue());
  1053.       if (prev)
  1054.          assert(prev->livei.begin() <= (*it)->livei.begin());
  1055.       prev = *it;
  1056.    }
  1057. }
  1058.  
  1059. void
  1060. GCRA::insertOrderedTail(std::list<RIG_Node *>& list, RIG_Node *node)
  1061. {
  1062.    if (node->livei.isEmpty())
  1063.       return;
  1064.    // only the intervals of joined values don't necessarily arrive in order
  1065.    std::list<RIG_Node *>::iterator prev, it;
  1066.    for (it = list.end(); it != list.begin(); it = prev) {
  1067.       prev = it;
  1068.       --prev;
  1069.       if ((*prev)->livei.begin() <= node->livei.begin())
  1070.          break;
  1071.    }
  1072.    list.insert(it, node);
  1073. }
  1074.  
  1075. void
  1076. GCRA::buildRIG(ArrayList& insns)
  1077. {
  1078.    std::list<RIG_Node *> values, active;
  1079.  
  1080.    for (std::deque<ValueDef>::iterator it = func->ins.begin();
  1081.         it != func->ins.end(); ++it)
  1082.       insertOrderedTail(values, getNode(it->get()->asLValue()));
  1083.  
  1084.    for (int i = 0; i < insns.getSize(); ++i) {
  1085.       Instruction *insn = reinterpret_cast<Instruction *>(insns.get(i));
  1086.       for (int d = 0; insn->defExists(d); ++d)
  1087.          if (insn->getDef(d)->rep() == insn->getDef(d))
  1088.             insertOrderedTail(values, getNode(insn->getDef(d)->asLValue()));
  1089.    }
  1090.    checkList(values);
  1091.  
  1092.    while (!values.empty()) {
  1093.       RIG_Node *cur = values.front();
  1094.  
  1095.       for (std::list<RIG_Node *>::iterator it = active.begin();
  1096.            it != active.end();) {
  1097.          RIG_Node *node = *it;
  1098.  
  1099.          if (node->livei.end() <= cur->livei.begin()) {
  1100.             it = active.erase(it);
  1101.          } else {
  1102.             if (node->f == cur->f && node->livei.overlaps(cur->livei))
  1103.                cur->addInterference(node);
  1104.             ++it;
  1105.          }
  1106.       }
  1107.       values.pop_front();
  1108.       active.push_back(cur);
  1109.    }
  1110. }
  1111.  
  1112. void
  1113. GCRA::calculateSpillWeights()
  1114. {
  1115.    for (unsigned int i = 0; i < nodeCount; ++i) {
  1116.       RIG_Node *const n = &nodes[i];
  1117.       if (!nodes[i].colors || nodes[i].livei.isEmpty())
  1118.          continue;
  1119.       if (nodes[i].reg >= 0) {
  1120.          // update max reg
  1121.          regs.occupy(n->f, n->reg, n->colors);
  1122.          continue;
  1123.       }
  1124.       LValue *val = nodes[i].getValue();
  1125.  
  1126.       if (!val->noSpill) {
  1127.          int rc = 0;
  1128.          for (Value::DefIterator it = val->defs.begin();
  1129.               it != val->defs.end();
  1130.               ++it)
  1131.             rc += (*it)->get()->refCount();
  1132.  
  1133.          nodes[i].weight =
  1134.             (float)rc * (float)rc / (float)nodes[i].livei.extent();
  1135.       }
  1136.  
  1137.       if (nodes[i].degree < nodes[i].degreeLimit) {
  1138.          int l = 0;
  1139.          if (val->reg.size > 4)
  1140.             l = 1;
  1141.          DLLIST_ADDHEAD(&lo[l], &nodes[i]);
  1142.       } else {
  1143.          DLLIST_ADDHEAD(&hi, &nodes[i]);
  1144.       }
  1145.    }
  1146.    if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
  1147.       printNodeInfo();
  1148. }
  1149.  
  1150. void
  1151. GCRA::simplifyEdge(RIG_Node *a, RIG_Node *b)
  1152. {
  1153.    bool move = b->degree >= b->degreeLimit;
  1154.  
  1155.    INFO_DBG(prog->dbgFlags, REG_ALLOC,
  1156.             "edge: (%%%i, deg %u/%u) >-< (%%%i, deg %u/%u)\n",
  1157.             a->getValue()->id, a->degree, a->degreeLimit,
  1158.             b->getValue()->id, b->degree, b->degreeLimit);
  1159.  
  1160.    b->degree -= relDegree[a->colors][b->colors];
  1161.  
  1162.    move = move && b->degree < b->degreeLimit;
  1163.    if (move && !DLLIST_EMPTY(b)) {
  1164.       int l = (b->getValue()->reg.size > 4) ? 1 : 0;
  1165.       DLLIST_DEL(b);
  1166.       DLLIST_ADDTAIL(&lo[l], b);
  1167.    }
  1168. }
  1169.  
  1170. void
  1171. GCRA::simplifyNode(RIG_Node *node)
  1172. {
  1173.    for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next())
  1174.       simplifyEdge(node, RIG_Node::get(ei));
  1175.  
  1176.    for (Graph::EdgeIterator ei = node->incident(); !ei.end(); ei.next())
  1177.       simplifyEdge(node, RIG_Node::get(ei));
  1178.  
  1179.    DLLIST_DEL(node);
  1180.    stack.push(node->getValue()->id);
  1181.  
  1182.    INFO_DBG(prog->dbgFlags, REG_ALLOC, "SIMPLIFY: pushed %%%i%s\n",
  1183.             node->getValue()->id,
  1184.             (node->degree < node->degreeLimit) ? "" : "(spill)");
  1185. }
  1186.  
  1187. void
  1188. GCRA::simplify()
  1189. {
  1190.    for (;;) {
  1191.       if (!DLLIST_EMPTY(&lo[0])) {
  1192.          do {
  1193.             simplifyNode(lo[0].next);
  1194.          } while (!DLLIST_EMPTY(&lo[0]));
  1195.       } else
  1196.       if (!DLLIST_EMPTY(&lo[1])) {
  1197.          simplifyNode(lo[1].next);
  1198.       } else
  1199.       if (!DLLIST_EMPTY(&hi)) {
  1200.          RIG_Node *best = hi.next;
  1201.          float bestScore = best->weight / (float)best->degree;
  1202.          // spill candidate
  1203.          for (RIG_Node *it = best->next; it != &hi; it = it->next) {
  1204.             float score = it->weight / (float)it->degree;
  1205.             if (score < bestScore) {
  1206.                best = it;
  1207.                bestScore = score;
  1208.             }
  1209.          }
  1210.          if (isinf(bestScore)) {
  1211.             ERROR("no viable spill candidates left\n");
  1212.             break;
  1213.          }
  1214.          simplifyNode(best);
  1215.       } else {
  1216.          break;
  1217.       }
  1218.    }
  1219. }
  1220.  
  1221. void
  1222. GCRA::checkInterference(const RIG_Node *node, Graph::EdgeIterator& ei)
  1223. {
  1224.    const RIG_Node *intf = RIG_Node::get(ei);
  1225.  
  1226.    if (intf->reg < 0)
  1227.       return;
  1228.    const LValue *vA = node->getValue();
  1229.    const LValue *vB = intf->getValue();
  1230.  
  1231.    const uint8_t intfMask = ((1 << intf->colors) - 1) << (intf->reg & 7);
  1232.  
  1233.    if (vA->compound | vB->compound) {
  1234.       // NOTE: this only works for >aligned< register tuples !
  1235.       for (Value::DefCIterator D = vA->defs.begin(); D != vA->defs.end(); ++D) {
  1236.       for (Value::DefCIterator d = vB->defs.begin(); d != vB->defs.end(); ++d) {
  1237.          const LValue *vD = (*D)->get()->asLValue();
  1238.          const LValue *vd = (*d)->get()->asLValue();
  1239.  
  1240.          if (!vD->livei.overlaps(vd->livei)) {
  1241.             INFO_DBG(prog->dbgFlags, REG_ALLOC, "(%%%i) X (%%%i): no overlap\n",
  1242.                      vD->id, vd->id);
  1243.             continue;
  1244.          }
  1245.  
  1246.          uint8_t mask = vD->compound ? vD->compMask : ~0;
  1247.          if (vd->compound) {
  1248.             assert(vB->compound);
  1249.             mask &= vd->compMask & vB->compMask;
  1250.          } else {
  1251.             mask &= intfMask;
  1252.          }
  1253.  
  1254.          INFO_DBG(prog->dbgFlags, REG_ALLOC,
  1255.                   "(%%%i)%02x X (%%%i)%02x & %02x: $r%i.%02x\n",
  1256.                   vD->id,
  1257.                   vD->compound ? vD->compMask : 0xff,
  1258.                   vd->id,
  1259.                   vd->compound ? vd->compMask : intfMask,
  1260.                   vB->compMask, intf->reg & ~7, mask);
  1261.          if (mask)
  1262.             regs.occupyMask(node->f, intf->reg & ~7, mask);
  1263.       }
  1264.       }
  1265.    } else {
  1266.       INFO_DBG(prog->dbgFlags, REG_ALLOC,
  1267.                "(%%%i) X (%%%i): $r%i + %u\n",
  1268.                vA->id, vB->id, intf->reg, intf->colors);
  1269.       regs.occupy(node->f, intf->reg, intf->colors);
  1270.    }
  1271. }
  1272.  
  1273. bool
  1274. GCRA::selectRegisters()
  1275. {
  1276.    INFO_DBG(prog->dbgFlags, REG_ALLOC, "\nSELECT phase\n");
  1277.  
  1278.    while (!stack.empty()) {
  1279.       RIG_Node *node = &nodes[stack.top()];
  1280.       stack.pop();
  1281.  
  1282.       regs.reset(node->f);
  1283.  
  1284.       INFO_DBG(prog->dbgFlags, REG_ALLOC, "\nNODE[%%%i, %u colors]\n",
  1285.                node->getValue()->id, node->colors);
  1286.  
  1287.       for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next())
  1288.          checkInterference(node, ei);
  1289.       for (Graph::EdgeIterator ei = node->incident(); !ei.end(); ei.next())
  1290.          checkInterference(node, ei);
  1291.  
  1292.       if (!node->prefRegs.empty()) {
  1293.          for (std::list<RIG_Node *>::const_iterator it = node->prefRegs.begin();
  1294.               it != node->prefRegs.end();
  1295.               ++it) {
  1296.             if ((*it)->reg >= 0 &&
  1297.                 regs.testOccupy(node->f, (*it)->reg, node->colors)) {
  1298.                node->reg = (*it)->reg;
  1299.                break;
  1300.             }
  1301.          }
  1302.       }
  1303.       if (node->reg >= 0)
  1304.          continue;
  1305.       LValue *lval = node->getValue();
  1306.       if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
  1307.          regs.print();
  1308.       bool ret = regs.assign(node->reg, node->f, node->colors);
  1309.       if (ret) {
  1310.          INFO_DBG(prog->dbgFlags, REG_ALLOC, "assigned reg %i\n", node->reg);
  1311.          lval->compMask = node->getCompMask();
  1312.       } else {
  1313.          INFO_DBG(prog->dbgFlags, REG_ALLOC, "must spill: %%%i (size %u)\n",
  1314.                   lval->id, lval->reg.size);
  1315.          Symbol *slot = NULL;
  1316.          if (lval->reg.file == FILE_GPR)
  1317.             slot = spill.assignSlot(node->livei, lval->reg.size);
  1318.          mustSpill.push_back(ValuePair(lval, slot));
  1319.       }
  1320.    }
  1321.    if (!mustSpill.empty())
  1322.       return false;
  1323.    for (unsigned int i = 0; i < nodeCount; ++i) {
  1324.       LValue *lval = nodes[i].getValue();
  1325.       if (nodes[i].reg >= 0 && nodes[i].colors > 0)
  1326.          lval->reg.data.id =
  1327.             regs.unitsToId(nodes[i].f, nodes[i].reg, lval->reg.size);
  1328.    }
  1329.    return true;
  1330. }
  1331.  
  1332. bool
  1333. GCRA::allocateRegisters(ArrayList& insns)
  1334. {
  1335.    bool ret;
  1336.  
  1337.    INFO_DBG(prog->dbgFlags, REG_ALLOC,
  1338.             "allocateRegisters to %u instructions\n", insns.getSize());
  1339.  
  1340.    nodeCount = func->allLValues.getSize();
  1341.    nodes = new RIG_Node[nodeCount];
  1342.    if (!nodes)
  1343.       return false;
  1344.    for (unsigned int i = 0; i < nodeCount; ++i) {
  1345.       LValue *lval = reinterpret_cast<LValue *>(func->allLValues.get(i));
  1346.       if (lval) {
  1347.          nodes[i].init(regs, lval);
  1348.          RIG.insert(&nodes[i]);
  1349.       }
  1350.    }
  1351.  
  1352.    // coalesce first, we use only 1 RIG node for a group of joined values
  1353.    ret = coalesce(insns);
  1354.    if (!ret)
  1355.       goto out;
  1356.  
  1357.    if (func->getProgram()->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
  1358.       func->printLiveIntervals();
  1359.  
  1360.    buildRIG(insns);
  1361.    calculateSpillWeights();
  1362.    simplify();
  1363.  
  1364.    ret = selectRegisters();
  1365.    if (!ret) {
  1366.       INFO_DBG(prog->dbgFlags, REG_ALLOC,
  1367.                "selectRegisters failed, inserting spill code ...\n");
  1368.       regs.reset(FILE_GPR, true);
  1369.       spill.run(mustSpill);
  1370.       if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
  1371.          func->print();
  1372.    } else {
  1373.       prog->maxGPR = std::max(prog->maxGPR, regs.getMaxAssigned(FILE_GPR));
  1374.    }
  1375.  
  1376. out:
  1377.    cleanup(ret);
  1378.    return ret;
  1379. }
  1380.  
  1381. void
  1382. GCRA::cleanup(const bool success)
  1383. {
  1384.    mustSpill.clear();
  1385.  
  1386.    for (ArrayList::Iterator it = func->allLValues.iterator();
  1387.         !it.end(); it.next()) {
  1388.       LValue *lval =  reinterpret_cast<LValue *>(it.get());
  1389.  
  1390.       lval->livei.clear();
  1391.  
  1392.       lval->compound = 0;
  1393.       lval->compMask = 0;
  1394.  
  1395.       if (lval->join == lval)
  1396.          continue;
  1397.  
  1398.       if (success) {
  1399.          lval->reg.data.id = lval->join->reg.data.id;
  1400.       } else {
  1401.          for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end();
  1402.               ++d)
  1403.             lval->join->defs.remove(*d);
  1404.          lval->join = lval;
  1405.       }
  1406.    }
  1407.  
  1408.    if (success)
  1409.       resolveSplitsAndMerges();
  1410.    splits.clear(); // avoid duplicate entries on next coalesce pass
  1411.    merges.clear();
  1412.  
  1413.    delete[] nodes;
  1414.    nodes = NULL;
  1415. }
  1416.  
  1417. Symbol *
  1418. SpillCodeInserter::assignSlot(const Interval &livei, const unsigned int size)
  1419. {
  1420.    SpillSlot slot;
  1421.    int32_t offsetBase = stackSize;
  1422.    int32_t offset;
  1423.    std::list<SpillSlot>::iterator pos = slots.end(), it = slots.begin();
  1424.  
  1425.    if (offsetBase % size)
  1426.       offsetBase += size - (offsetBase % size);
  1427.  
  1428.    slot.sym = NULL;
  1429.  
  1430.    for (offset = offsetBase; offset < stackSize; offset += size) {
  1431.       const int32_t entryEnd = offset + size;
  1432.       while (it != slots.end() && it->offset < offset)
  1433.          ++it;
  1434.       if (it == slots.end()) // no slots left
  1435.          break;
  1436.       std::list<SpillSlot>::iterator bgn = it;
  1437.  
  1438.       while (it != slots.end() && it->offset < entryEnd) {
  1439.          it->occup.print();
  1440.          if (it->occup.overlaps(livei))
  1441.             break;
  1442.          ++it;
  1443.       }
  1444.       if (it == slots.end() || it->offset >= entryEnd) {
  1445.          // fits
  1446.          for (; bgn != slots.end() && bgn->offset < entryEnd; ++bgn) {
  1447.             bgn->occup.insert(livei);
  1448.             if (bgn->size() == size)
  1449.                slot.sym = bgn->sym;
  1450.          }
  1451.          break;
  1452.       }
  1453.    }
  1454.    if (!slot.sym) {
  1455.       stackSize = offset + size;
  1456.       slot.offset = offset;
  1457.       slot.sym = new_Symbol(func->getProgram(), FILE_MEMORY_LOCAL);
  1458.       if (!func->stackPtr)
  1459.          offset += func->tlsBase;
  1460.       slot.sym->setAddress(NULL, offset);
  1461.       slot.sym->reg.size = size;
  1462.       slots.insert(pos, slot)->occup.insert(livei);
  1463.    }
  1464.    return slot.sym;
  1465. }
  1466.  
  1467. void
  1468. SpillCodeInserter::spill(Instruction *defi, Value *slot, LValue *lval)
  1469. {
  1470.    const DataType ty = typeOfSize(slot->reg.size);
  1471.  
  1472.    Instruction *st;
  1473.    if (slot->reg.file == FILE_MEMORY_LOCAL) {
  1474.       st = new_Instruction(func, OP_STORE, ty);
  1475.       st->setSrc(0, slot);
  1476.       st->setSrc(1, lval);
  1477.       lval->noSpill = 1;
  1478.    } else {
  1479.       st = new_Instruction(func, OP_CVT, ty);
  1480.       st->setDef(0, slot);
  1481.       st->setSrc(0, lval);
  1482.    }
  1483.    defi->bb->insertAfter(defi, st);
  1484. }
  1485.  
  1486. LValue *
  1487. SpillCodeInserter::unspill(Instruction *usei, LValue *lval, Value *slot)
  1488. {
  1489.    const DataType ty = typeOfSize(slot->reg.size);
  1490.  
  1491.    lval = cloneShallow(func, lval);
  1492.  
  1493.    Instruction *ld;
  1494.    if (slot->reg.file == FILE_MEMORY_LOCAL) {
  1495.       lval->noSpill = 1;
  1496.       ld = new_Instruction(func, OP_LOAD, ty);
  1497.    } else {
  1498.       ld = new_Instruction(func, OP_CVT, ty);
  1499.    }
  1500.    ld->setDef(0, lval);
  1501.    ld->setSrc(0, slot);
  1502.  
  1503.    usei->bb->insertBefore(usei, ld);
  1504.    return lval;
  1505. }
  1506.  
  1507. bool
  1508. SpillCodeInserter::run(const std::list<ValuePair>& lst)
  1509. {
  1510.    for (std::list<ValuePair>::const_iterator it = lst.begin(); it != lst.end();
  1511.         ++it) {
  1512.       LValue *lval = it->first->asLValue();
  1513.       Symbol *mem = it->second ? it->second->asSym() : NULL;
  1514.  
  1515.       for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end();
  1516.            ++d) {
  1517.          Value *slot = mem ?
  1518.             static_cast<Value *>(mem) : new_LValue(func, FILE_GPR);
  1519.          Value *tmp = NULL;
  1520.          Instruction *last = NULL;
  1521.  
  1522.          LValue *dval = (*d)->get()->asLValue();
  1523.          Instruction *defi = (*d)->getInsn();
  1524.  
  1525.          // handle uses first or they'll contain the spill stores
  1526.          while (!dval->uses.empty()) {
  1527.             ValueRef *u = dval->uses.front();
  1528.             Instruction *usei = u->getInsn();
  1529.             assert(usei);
  1530.             if (usei->op == OP_PHI) {
  1531.                tmp = (slot->reg.file == FILE_MEMORY_LOCAL) ? NULL : slot;
  1532.                last = NULL;
  1533.             } else
  1534.             if (!last || usei != last->next) { // TODO: sort uses
  1535.                tmp = unspill(usei, dval, slot);
  1536.                last = usei;
  1537.             }
  1538.             u->set(tmp);
  1539.          }
  1540.  
  1541.          assert(defi);
  1542.          if (defi->op == OP_PHI) {
  1543.             d = lval->defs.erase(d);
  1544.             --d;
  1545.             if (slot->reg.file == FILE_MEMORY_LOCAL)
  1546.                delete_Instruction(func->getProgram(), defi);
  1547.             else
  1548.                defi->setDef(0, slot);
  1549.          } else {
  1550.             spill(defi, slot, dval);
  1551.          }
  1552.       }
  1553.  
  1554.    }
  1555.  
  1556.    // TODO: We're not trying to reuse old slots in a potential next iteration.
  1557.    //  We have to update the slots' livei intervals to be able to do that.
  1558.    stackBase = stackSize;
  1559.    slots.clear();
  1560.    return true;
  1561. }
  1562.  
  1563. bool
  1564. RegAlloc::exec()
  1565. {
  1566.    for (IteratorRef it = prog->calls.iteratorDFS(false);
  1567.         !it->end(); it->next()) {
  1568.       func = Function::get(reinterpret_cast<Graph::Node *>(it->get()));
  1569.  
  1570.       func->tlsBase = prog->tlsSize;
  1571.       if (!execFunc())
  1572.          return false;
  1573.       prog->tlsSize += func->tlsSize;
  1574.    }
  1575.    return true;
  1576. }
  1577.  
  1578. bool
  1579. RegAlloc::execFunc()
  1580. {
  1581.    InsertConstraintsPass insertConstr;
  1582.    PhiMovesPass insertPhiMoves;
  1583.    ArgumentMovesPass insertArgMoves;
  1584.    BuildIntervalsPass buildIntervals;
  1585.    SpillCodeInserter insertSpills(func);
  1586.  
  1587.    GCRA gcra(func, insertSpills);
  1588.  
  1589.    unsigned int i, retries;
  1590.    bool ret;
  1591.  
  1592.    if (!func->ins.empty()) {
  1593.       // Insert a nop at the entry so inputs only used by the first instruction
  1594.       // don't count as having an empty live range.
  1595.       Instruction *nop = new_Instruction(func, OP_NOP, TYPE_NONE);
  1596.       BasicBlock::get(func->cfg.getRoot())->insertHead(nop);
  1597.    }
  1598.  
  1599.    ret = insertConstr.exec(func);
  1600.    if (!ret)
  1601.       goto out;
  1602.  
  1603.    ret = insertPhiMoves.run(func);
  1604.    if (!ret)
  1605.       goto out;
  1606.  
  1607.    ret = insertArgMoves.run(func);
  1608.    if (!ret)
  1609.       goto out;
  1610.  
  1611.    // TODO: need to fix up spill slot usage ranges to support > 1 retry
  1612.    for (retries = 0; retries < 3; ++retries) {
  1613.       if (retries && (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC))
  1614.          INFO("Retry: %i\n", retries);
  1615.       if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
  1616.          func->print();
  1617.  
  1618.       // spilling to registers may add live ranges, need to rebuild everything
  1619.       ret = true;
  1620.       for (sequence = func->cfg.nextSequence(), i = 0;
  1621.            ret && i <= func->loopNestingBound;
  1622.            sequence = func->cfg.nextSequence(), ++i)
  1623.          ret = buildLiveSets(BasicBlock::get(func->cfg.getRoot()));
  1624.       if (!ret)
  1625.          break;
  1626.       func->orderInstructions(this->insns);
  1627.  
  1628.       ret = buildIntervals.run(func);
  1629.       if (!ret)
  1630.          break;
  1631.       ret = gcra.allocateRegisters(insns);
  1632.       if (ret)
  1633.          break; // success
  1634.    }
  1635.    INFO_DBG(prog->dbgFlags, REG_ALLOC, "RegAlloc done: %i\n", ret);
  1636.  
  1637.    func->tlsSize = insertSpills.getStackSize();
  1638. out:
  1639.    return ret;
  1640. }
  1641.  
  1642. // TODO: check if modifying Instruction::join here breaks anything
  1643. void
  1644. GCRA::resolveSplitsAndMerges()
  1645. {
  1646.    for (std::list<Instruction *>::iterator it = splits.begin();
  1647.         it != splits.end();
  1648.         ++it) {
  1649.       Instruction *split = *it;
  1650.       unsigned int reg = regs.idToBytes(split->getSrc(0));
  1651.       for (int d = 0; split->defExists(d); ++d) {
  1652.          Value *v = split->getDef(d);
  1653.          v->reg.data.id = regs.bytesToId(v, reg);
  1654.          v->join = v;
  1655.          reg += v->reg.size;
  1656.       }
  1657.    }
  1658.    splits.clear();
  1659.  
  1660.    for (std::list<Instruction *>::iterator it = merges.begin();
  1661.         it != merges.end();
  1662.         ++it) {
  1663.       Instruction *merge = *it;
  1664.       unsigned int reg = regs.idToBytes(merge->getDef(0));
  1665.       for (int s = 0; merge->srcExists(s); ++s) {
  1666.          Value *v = merge->getSrc(s);
  1667.          v->reg.data.id = regs.bytesToId(v, reg);
  1668.          v->join = v;
  1669.          reg += v->reg.size;
  1670.       }
  1671.    }
  1672.    merges.clear();
  1673. }
  1674.  
  1675. bool Program::registerAllocation()
  1676. {
  1677.    RegAlloc ra(this);
  1678.    return ra.exec();
  1679. }
  1680.  
  1681. bool
  1682. RegAlloc::InsertConstraintsPass::exec(Function *ir)
  1683. {
  1684.    constrList.clear();
  1685.  
  1686.    bool ret = run(ir, true, true);
  1687.    if (ret)
  1688.       ret = insertConstraintMoves();
  1689.    return ret;
  1690. }
  1691.  
  1692. // TODO: make part of texture insn
  1693. void
  1694. RegAlloc::InsertConstraintsPass::textureMask(TexInstruction *tex)
  1695. {
  1696.    Value *def[4];
  1697.    int c, k, d;
  1698.    uint8_t mask = 0;
  1699.  
  1700.    for (d = 0, k = 0, c = 0; c < 4; ++c) {
  1701.       if (!(tex->tex.mask & (1 << c)))
  1702.          continue;
  1703.       if (tex->getDef(k)->refCount()) {
  1704.          mask |= 1 << c;
  1705.          def[d++] = tex->getDef(k);
  1706.       }
  1707.       ++k;
  1708.    }
  1709.    tex->tex.mask = mask;
  1710.  
  1711.    for (c = 0; c < d; ++c)
  1712.       tex->setDef(c, def[c]);
  1713.    for (; c < 4; ++c)
  1714.       tex->setDef(c, NULL);
  1715. }
  1716.  
  1717. bool
  1718. RegAlloc::InsertConstraintsPass::detectConflict(Instruction *cst, int s)
  1719. {
  1720.    Value *v = cst->getSrc(s);
  1721.  
  1722.    // current register allocation can't handle it if a value participates in
  1723.    // multiple constraints
  1724.    for (Value::UseIterator it = v->uses.begin(); it != v->uses.end(); ++it) {
  1725.       if (cst != (*it)->getInsn())
  1726.          return true;
  1727.    }
  1728.  
  1729.    // can start at s + 1 because detectConflict is called on all sources
  1730.    for (int c = s + 1; cst->srcExists(c); ++c)
  1731.       if (v == cst->getSrc(c))
  1732.          return true;
  1733.  
  1734.    Instruction *defi = v->getInsn();
  1735.  
  1736.    return (!defi || defi->constrainedDefs());
  1737. }
  1738.  
  1739. void
  1740. RegAlloc::InsertConstraintsPass::addConstraint(Instruction *i, int s, int n)
  1741. {
  1742.    Instruction *cst;
  1743.    int d;
  1744.  
  1745.    // first, look for an existing identical constraint op
  1746.    for (std::list<Instruction *>::iterator it = constrList.begin();
  1747.         it != constrList.end();
  1748.         ++it) {
  1749.       cst = (*it);
  1750.       if (!i->bb->dominatedBy(cst->bb))
  1751.          break;
  1752.       for (d = 0; d < n; ++d)
  1753.          if (cst->getSrc(d) != i->getSrc(d + s))
  1754.             break;
  1755.       if (d >= n) {
  1756.          for (d = 0; d < n; ++d, ++s)
  1757.             i->setSrc(s, cst->getDef(d));
  1758.          return;
  1759.       }
  1760.    }
  1761.    cst = new_Instruction(func, OP_CONSTRAINT, i->dType);
  1762.  
  1763.    for (d = 0; d < n; ++s, ++d) {
  1764.       cst->setDef(d, new_LValue(func, FILE_GPR));
  1765.       cst->setSrc(d, i->getSrc(s));
  1766.       i->setSrc(s, cst->getDef(d));
  1767.    }
  1768.    i->bb->insertBefore(i, cst);
  1769.  
  1770.    constrList.push_back(cst);
  1771. }
  1772.  
  1773. // Add a dummy use of the pointer source of >= 8 byte loads after the load
  1774. // to prevent it from being assigned a register which overlapping the load's
  1775. // destination, which would produce random corruptions.
  1776. void
  1777. RegAlloc::InsertConstraintsPass::addHazard(Instruction *i, const ValueRef *src)
  1778. {
  1779.    Instruction *hzd = new_Instruction(func, OP_NOP, TYPE_NONE);
  1780.    hzd->setSrc(0, src->get());
  1781.    i->bb->insertAfter(i, hzd);
  1782.  
  1783. }
  1784.  
  1785. // b32 { %r0 %r1 %r2 %r3 } -> b128 %r0q
  1786. void
  1787. RegAlloc::InsertConstraintsPass::condenseDefs(Instruction *insn)
  1788. {
  1789.    uint8_t size = 0;
  1790.    int n;
  1791.    for (n = 0; insn->defExists(n) && insn->def(n).getFile() == FILE_GPR; ++n)
  1792.       size += insn->getDef(n)->reg.size;
  1793.    if (n < 2)
  1794.       return;
  1795.    LValue *lval = new_LValue(func, FILE_GPR);
  1796.    lval->reg.size = size;
  1797.  
  1798.    Instruction *split = new_Instruction(func, OP_SPLIT, typeOfSize(size));
  1799.    split->setSrc(0, lval);
  1800.    for (int d = 0; d < n; ++d) {
  1801.       split->setDef(d, insn->getDef(d));
  1802.       insn->setDef(d, NULL);
  1803.    }
  1804.    insn->setDef(0, lval);
  1805.  
  1806.    for (int k = 1, d = n; insn->defExists(d); ++d, ++k) {
  1807.       insn->setDef(k, insn->getDef(d));
  1808.       insn->setDef(d, NULL);
  1809.    }
  1810.    // carry over predicate if any (mainly for OP_UNION uses)
  1811.    split->setPredicate(insn->cc, insn->getPredicate());
  1812.  
  1813.    insn->bb->insertAfter(insn, split);
  1814.    constrList.push_back(split);
  1815. }
  1816. void
  1817. RegAlloc::InsertConstraintsPass::condenseSrcs(Instruction *insn,
  1818.                                               const int a, const int b)
  1819. {
  1820.    uint8_t size = 0;
  1821.    if (a >= b)
  1822.       return;
  1823.    for (int s = a; s <= b; ++s)
  1824.       size += insn->getSrc(s)->reg.size;
  1825.    if (!size)
  1826.       return;
  1827.    LValue *lval = new_LValue(func, FILE_GPR);
  1828.    lval->reg.size = size;
  1829.  
  1830.    Value *save[3];
  1831.    insn->takeExtraSources(0, save);
  1832.  
  1833.    Instruction *merge = new_Instruction(func, OP_MERGE, typeOfSize(size));
  1834.    merge->setDef(0, lval);
  1835.    for (int s = a, i = 0; s <= b; ++s, ++i) {
  1836.       merge->setSrc(i, insn->getSrc(s));
  1837.       insn->setSrc(s, NULL);
  1838.    }
  1839.    insn->setSrc(a, lval);
  1840.  
  1841.    for (int k = a + 1, s = b + 1; insn->srcExists(s); ++s, ++k) {
  1842.       insn->setSrc(k, insn->getSrc(s));
  1843.       insn->setSrc(s, NULL);
  1844.    }
  1845.    insn->bb->insertBefore(insn, merge);
  1846.  
  1847.    insn->putExtraSources(0, save);
  1848.  
  1849.    constrList.push_back(merge);
  1850. }
  1851.  
  1852. void
  1853. RegAlloc::InsertConstraintsPass::texConstraintNVE0(TexInstruction *tex)
  1854. {
  1855.    if (isTextureOp(tex->op))
  1856.       textureMask(tex);
  1857.    condenseDefs(tex);
  1858.  
  1859.    if (tex->op == OP_SUSTB || tex->op == OP_SUSTP) {
  1860.       condenseSrcs(tex, 3, (3 + typeSizeof(tex->dType) / 4) - 1);
  1861.    } else
  1862.    if (isTextureOp(tex->op)) {
  1863.       int n = tex->srcCount(0xff, true);
  1864.       if (n > 4) {
  1865.          condenseSrcs(tex, 0, 3);
  1866.          if (n > 5) // NOTE: first call modified positions already
  1867.             condenseSrcs(tex, 4 - (4 - 1), n - 1 - (4 - 1));
  1868.       } else
  1869.       if (n > 1) {
  1870.          condenseSrcs(tex, 0, n - 1);
  1871.       }
  1872.    }
  1873. }
  1874.  
  1875. void
  1876. RegAlloc::InsertConstraintsPass::texConstraintNVC0(TexInstruction *tex)
  1877. {
  1878.    int n, s;
  1879.  
  1880.    textureMask(tex);
  1881.  
  1882.    if (tex->op == OP_TXQ) {
  1883.       s = tex->srcCount(0xff);
  1884.       n = 0;
  1885.    } else {
  1886.       s = tex->tex.target.getArgCount();
  1887.       if (!tex->tex.target.isArray() &&
  1888.           (tex->tex.rIndirectSrc >= 0 || tex->tex.sIndirectSrc >= 0))
  1889.          ++s;
  1890.       if (tex->op == OP_TXD && tex->tex.useOffsets)
  1891.          ++s;
  1892.       n = tex->srcCount(0xff) - s;
  1893.       assert(n <= 4);
  1894.    }
  1895.  
  1896.    if (s > 1)
  1897.       condenseSrcs(tex, 0, s - 1);
  1898.    if (n > 1) // NOTE: first call modified positions already
  1899.       condenseSrcs(tex, 1, n);
  1900.  
  1901.    condenseDefs(tex);
  1902. }
  1903.  
  1904. void
  1905. RegAlloc::InsertConstraintsPass::texConstraintNV50(TexInstruction *tex)
  1906. {
  1907.    Value *pred = tex->getPredicate();
  1908.    if (pred)
  1909.       tex->setPredicate(tex->cc, NULL);
  1910.  
  1911.    textureMask(tex);
  1912.  
  1913.    assert(tex->defExists(0) && tex->srcExists(0));
  1914.    // make src and def count match
  1915.    int c;
  1916.    for (c = 0; tex->srcExists(c) || tex->defExists(c); ++c) {
  1917.       if (!tex->srcExists(c))
  1918.          tex->setSrc(c, new_LValue(func, tex->getSrc(0)->asLValue()));
  1919.       if (!tex->defExists(c))
  1920.          tex->setDef(c, new_LValue(func, tex->getDef(0)->asLValue()));
  1921.    }
  1922.    if (pred)
  1923.       tex->setPredicate(tex->cc, pred);
  1924.    condenseDefs(tex);
  1925.    condenseSrcs(tex, 0, c - 1);
  1926. }
  1927.  
  1928. // Insert constraint markers for instructions whose multiple sources must be
  1929. // located in consecutive registers.
  1930. bool
  1931. RegAlloc::InsertConstraintsPass::visit(BasicBlock *bb)
  1932. {
  1933.    TexInstruction *tex;
  1934.    Instruction *next;
  1935.    int s, size;
  1936.  
  1937.    targ = bb->getProgram()->getTarget();
  1938.  
  1939.    for (Instruction *i = bb->getEntry(); i; i = next) {
  1940.       next = i->next;
  1941.  
  1942.       if ((tex = i->asTex())) {
  1943.          switch (targ->getChipset() & ~0xf) {
  1944.          case 0x50:
  1945.          case 0x80:
  1946.          case 0x90:
  1947.          case 0xa0:
  1948.             texConstraintNV50(tex);
  1949.             break;
  1950.          case 0xc0:
  1951.          case 0xd0:
  1952.             texConstraintNVC0(tex);
  1953.             break;
  1954.          case 0xe0:
  1955.          case NVISA_GK110_CHIPSET:
  1956.             texConstraintNVE0(tex);
  1957.             break;
  1958.          default:
  1959.             break;
  1960.          }
  1961.       } else
  1962.       if (i->op == OP_EXPORT || i->op == OP_STORE) {
  1963.          for (size = typeSizeof(i->dType), s = 1; size > 0; ++s) {
  1964.             assert(i->srcExists(s));
  1965.             size -= i->getSrc(s)->reg.size;
  1966.          }
  1967.          condenseSrcs(i, 1, s - 1);
  1968.       } else
  1969.       if (i->op == OP_LOAD || i->op == OP_VFETCH) {
  1970.          condenseDefs(i);
  1971.          if (i->src(0).isIndirect(0) && typeSizeof(i->dType) >= 8)
  1972.             addHazard(i, i->src(0).getIndirect(0));
  1973.       } else
  1974.       if (i->op == OP_UNION ||
  1975.           i->op == OP_MERGE ||
  1976.           i->op == OP_SPLIT) {
  1977.          constrList.push_back(i);
  1978.       }
  1979.    }
  1980.    return true;
  1981. }
  1982.  
  1983. // Insert extra moves so that, if multiple register constraints on a value are
  1984. // in conflict, these conflicts can be resolved.
  1985. bool
  1986. RegAlloc::InsertConstraintsPass::insertConstraintMoves()
  1987. {
  1988.    for (std::list<Instruction *>::iterator it = constrList.begin();
  1989.         it != constrList.end();
  1990.         ++it) {
  1991.       Instruction *cst = *it;
  1992.       Instruction *mov;
  1993.  
  1994.       if (cst->op == OP_SPLIT && 0) {
  1995.          // spilling splits is annoying, just make sure they're separate
  1996.          for (int d = 0; cst->defExists(d); ++d) {
  1997.             if (!cst->getDef(d)->refCount())
  1998.                continue;
  1999.             LValue *lval = new_LValue(func, cst->def(d).getFile());
  2000.             const uint8_t size = cst->def(d).getSize();
  2001.             lval->reg.size = size;
  2002.  
  2003.             mov = new_Instruction(func, OP_MOV, typeOfSize(size));
  2004.             mov->setSrc(0, lval);
  2005.             mov->setDef(0, cst->getDef(d));
  2006.             cst->setDef(d, mov->getSrc(0));
  2007.             cst->bb->insertAfter(cst, mov);
  2008.  
  2009.             cst->getSrc(0)->asLValue()->noSpill = 1;
  2010.             mov->getSrc(0)->asLValue()->noSpill = 1;
  2011.          }
  2012.       } else
  2013.       if (cst->op == OP_MERGE || cst->op == OP_UNION) {
  2014.          for (int s = 0; cst->srcExists(s); ++s) {
  2015.             const uint8_t size = cst->src(s).getSize();
  2016.  
  2017.             if (!cst->getSrc(s)->defs.size()) {
  2018.                mov = new_Instruction(func, OP_NOP, typeOfSize(size));
  2019.                mov->setDef(0, cst->getSrc(s));
  2020.                cst->bb->insertBefore(cst, mov);
  2021.                continue;
  2022.             }
  2023.             assert(cst->getSrc(s)->defs.size() == 1); // still SSA
  2024.  
  2025.             Instruction *defi = cst->getSrc(s)->defs.front()->getInsn();
  2026.             // catch some cases where don't really need MOVs
  2027.             if (cst->getSrc(s)->refCount() == 1 && !defi->constrainedDefs())
  2028.                continue;
  2029.  
  2030.             LValue *lval = new_LValue(func, cst->src(s).getFile());
  2031.             lval->reg.size = size;
  2032.  
  2033.             mov = new_Instruction(func, OP_MOV, typeOfSize(size));
  2034.             mov->setDef(0, lval);
  2035.             mov->setSrc(0, cst->getSrc(s));
  2036.             cst->setSrc(s, mov->getDef(0));
  2037.             cst->bb->insertBefore(cst, mov);
  2038.  
  2039.             cst->getDef(0)->asLValue()->noSpill = 1; // doesn't help
  2040.  
  2041.             if (cst->op == OP_UNION)
  2042.                mov->setPredicate(defi->cc, defi->getPredicate());
  2043.          }
  2044.       }
  2045.    }
  2046.  
  2047.    return true;
  2048. }
  2049.  
  2050. } // namespace nv50_ir
  2051.