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