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