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

   1 /*
   2  * Copyright 2011 Christoph Bumiller
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  17  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  18  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  19  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  20  * OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #include "codegen/nv50_ir.h"
  24 #include "codegen/nv50_ir_target.h"
  25
  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