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 prog->getTarget()->getChipset() < 0xc0) { 1471 Instruction *insn = lval->getInsn(); 1472 if (insn->op == OP_MAD || insn->op == OP_FMA || insn->op == OP_SAD) 1473 // Short encoding only possible if they're all GPRs, no need to 1474 // affect them otherwise. 1475 if (insn->flagsDef < 0 && 1476 insn->src(0).getFile() == FILE_GPR && 1477 insn->src(1).getFile() == FILE_GPR && 1478 insn->src(2).getFile() == FILE_GPR) 1479 nodes[i].addRegPreference(getNode(insn->getSrc(2)->asLValue())); 1480 } 1481 } 1482 } 1483 1484 // coalesce first, we use only 1 RIG node for a group of joined values 1485 ret = coalesce(insns); 1486 if (!ret) 1487 goto out; 1488 1489 if (func->getProgram()->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1490 func->printLiveIntervals(); 1491 1492 buildRIG(insns); 1493 calculateSpillWeights(); 1494 ret = simplify(); 1495 if (!ret) 1496 goto out; 1497 1498 ret = selectRegisters(); 1499 if (!ret) { 1500 INFO_DBG(prog->dbgFlags, REG_ALLOC, 1501 "selectRegisters failed, inserting spill code ...\n"); 1502 regs.reset(FILE_GPR, true); 1503 spill.run(mustSpill); 1504 if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1505 func->print(); 1506 } else { 1507 prog->maxGPR = std::max(prog->maxGPR, regs.getMaxAssigned(FILE_GPR)); 1508 } 1509 1510 out: 1511 cleanup(ret); 1512 return ret; 1513 } 1514 1515 void 1516 GCRA::cleanup(const bool success) 1517 { 1518 mustSpill.clear(); 1519 1520 for (ArrayList::Iterator it = func->allLValues.iterator(); 1521 !it.end(); it.next()) { 1522 LValue *lval = reinterpret_cast<LValue *>(it.get()); 1523 1524 lval->livei.clear(); 1525 1526 lval->compound = 0; 1527 lval->compMask = 0; 1528 1529 if (lval->join == lval) 1530 continue; 1531 1532 if (success) { 1533 lval->reg.data.id = lval->join->reg.data.id; 1534 } else { 1535 for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end(); 1536 ++d) 1537 lval->join->defs.remove(*d); 1538 lval->join = lval; 1539 } 1540 } 1541 1542 if (success) 1543 resolveSplitsAndMerges(); 1544 splits.clear(); // avoid duplicate entries on next coalesce pass 1545 merges.clear(); 1546 1547 delete[] nodes; 1548 nodes = NULL; 1549 hi.next = hi.prev = &hi; 1550 lo[0].next = lo[0].prev = &lo[0]; 1551 lo[1].next = lo[1].prev = &lo[1]; 1552 } 1553 1554 Symbol * 1555 SpillCodeInserter::assignSlot(const Interval &livei, const unsigned int size) 1556 { 1557 SpillSlot slot; 1558 int32_t offsetBase = stackSize; 1559 int32_t offset; 1560 std::list<SpillSlot>::iterator pos = slots.end(), it = slots.begin(); 1561 1562 if (offsetBase % size) 1563 offsetBase += size - (offsetBase % size); 1564 1565 slot.sym = NULL; 1566 1567 for (offset = offsetBase; offset < stackSize; offset += size) { 1568 const int32_t entryEnd = offset + size; 1569 while (it != slots.end() && it->offset < offset) 1570 ++it; 1571 if (it == slots.end()) // no slots left 1572 break; 1573 std::list<SpillSlot>::iterator bgn = it; 1574 1575 while (it != slots.end() && it->offset < entryEnd) { 1576 it->occup.print(); 1577 if (it->occup.overlaps(livei)) 1578 break; 1579 ++it; 1580 } 1581 if (it == slots.end() || it->offset >= entryEnd) { 1582 // fits 1583 for (; bgn != slots.end() && bgn->offset < entryEnd; ++bgn) { 1584 bgn->occup.insert(livei); 1585 if (bgn->size() == size) 1586 slot.sym = bgn->sym; 1587 } 1588 break; 1589 } 1590 } 1591 if (!slot.sym) { 1592 stackSize = offset + size; 1593 slot.offset = offset; 1594 slot.sym = new_Symbol(func->getProgram(), FILE_MEMORY_LOCAL); 1595 if (!func->stackPtr) 1596 offset += func->tlsBase; 1597 slot.sym->setAddress(NULL, offset); 1598 slot.sym->reg.size = size; 1599 slots.insert(pos, slot)->occup.insert(livei); 1600 } 1601 return slot.sym; 1602 } 1603 1604 Value * 1605 SpillCodeInserter::offsetSlot(Value *base, const LValue *lval) 1606 { 1607 if (!lval->compound || (lval->compMask & 0x1)) 1608 return base; 1609 Value *slot = cloneShallow(func, base); 1610 1611 slot->reg.data.offset += (ffs(lval->compMask) - 1) * lval->reg.size; 1612 slot->reg.size = lval->reg.size; 1613 1614 return slot; 1615 } 1616 1617 void 1618 SpillCodeInserter::spill(Instruction *defi, Value *slot, LValue *lval) 1619 { 1620 const DataType ty = typeOfSize(lval->reg.size); 1621 1622 slot = offsetSlot(slot, lval); 1623 1624 Instruction *st; 1625 if (slot->reg.file == FILE_MEMORY_LOCAL) { 1626 lval->noSpill = 1; 1627 if (ty != TYPE_B96) { 1628 st = new_Instruction(func, OP_STORE, ty); 1629 st->setSrc(0, slot); 1630 st->setSrc(1, lval); 1631 } else { 1632 st = new_Instruction(func, OP_SPLIT, ty); 1633 st->setSrc(0, lval); 1634 for (int d = 0; d < lval->reg.size / 4; ++d) 1635 st->setDef(d, new_LValue(func, FILE_GPR)); 1636 1637 for (int d = lval->reg.size / 4 - 1; d >= 0; --d) { 1638 Value *tmp = cloneShallow(func, slot); 1639 tmp->reg.size = 4; 1640 tmp->reg.data.offset += 4 * d; 1641 1642 Instruction *s = new_Instruction(func, OP_STORE, TYPE_U32); 1643 s->setSrc(0, tmp); 1644 s->setSrc(1, st->getDef(d)); 1645 defi->bb->insertAfter(defi, s); 1646 } 1647 } 1648 } else { 1649 st = new_Instruction(func, OP_CVT, ty); 1650 st->setDef(0, slot); 1651 st->setSrc(0, lval); 1652 if (lval->reg.file == FILE_FLAGS) 1653 st->flagsSrc = 0; 1654 } 1655 defi->bb->insertAfter(defi, st); 1656 } 1657 1658 LValue * 1659 SpillCodeInserter::unspill(Instruction *usei, LValue *lval, Value *slot) 1660 { 1661 const DataType ty = typeOfSize(lval->reg.size); 1662 1663 slot = offsetSlot(slot, lval); 1664 lval = cloneShallow(func, lval); 1665 1666 Instruction *ld; 1667 if (slot->reg.file == FILE_MEMORY_LOCAL) { 1668 lval->noSpill = 1; 1669 if (ty != TYPE_B96) { 1670 ld = new_Instruction(func, OP_LOAD, ty); 1671 } else { 1672 ld = new_Instruction(func, OP_MERGE, ty); 1673 for (int d = 0; d < lval->reg.size / 4; ++d) { 1674 Value *tmp = cloneShallow(func, slot); 1675 LValue *val; 1676 tmp->reg.size = 4; 1677 tmp->reg.data.offset += 4 * d; 1678 1679 Instruction *l = new_Instruction(func, OP_LOAD, TYPE_U32); 1680 l->setDef(0, (val = new_LValue(func, FILE_GPR))); 1681 l->setSrc(0, tmp); 1682 usei->bb->insertBefore(usei, l); 1683 ld->setSrc(d, val); 1684 val->noSpill = 1; 1685 } 1686 ld->setDef(0, lval); 1687 usei->bb->insertBefore(usei, ld); 1688 return lval; 1689 } 1690 } else { 1691 ld = new_Instruction(func, OP_CVT, ty); 1692 } 1693 ld->setDef(0, lval); 1694 ld->setSrc(0, slot); 1695 if (lval->reg.file == FILE_FLAGS) 1696 ld->flagsDef = 0; 1697 1698 usei->bb->insertBefore(usei, ld); 1699 return lval; 1700 } 1701 1702 static bool 1703 value_cmp(ValueRef *a, ValueRef *b) { 1704 Instruction *ai = a->getInsn(), *bi = b->getInsn(); 1705 if (ai->bb != bi->bb) 1706 return ai->bb->getId() < bi->bb->getId(); 1707 return ai->serial < bi->serial; 1708 } 1709 1710 // For each value that is to be spilled, go through all its definitions. 1711 // A value can have multiple definitions if it has been coalesced before. 1712 // For each definition, first go through all its uses and insert an unspill 1713 // instruction before it, then replace the use with the temporary register. 1714 // Unspill can be either a load from memory or simply a move to another 1715 // register file. 1716 // For "Pseudo" instructions (like PHI, SPLIT, MERGE) we can erase the use 1717 // if we have spilled to a memory location, or simply with the new register. 1718 // No load or conversion instruction should be needed. 1719 bool 1720 SpillCodeInserter::run(const std::list<ValuePair>& lst) 1721 { 1722 for (std::list<ValuePair>::const_iterator it = lst.begin(); it != lst.end(); 1723 ++it) { 1724 LValue *lval = it->first->asLValue(); 1725 Symbol *mem = it->second ? it->second->asSym() : NULL; 1726 1727 // Keep track of which instructions to delete later. Deleting them 1728 // inside the loop is unsafe since a single instruction may have 1729 // multiple destinations that all need to be spilled (like OP_SPLIT). 1730 unordered_set<Instruction *> to_del; 1731 1732 for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end(); 1733 ++d) { 1734 Value *slot = mem ? 1735 static_cast<Value *>(mem) : new_LValue(func, FILE_GPR); 1736 Value *tmp = NULL; 1737 Instruction *last = NULL; 1738 1739 LValue *dval = (*d)->get()->asLValue(); 1740 Instruction *defi = (*d)->getInsn(); 1741 1742 // Sort all the uses by BB/instruction so that we don't unspill 1743 // multiple times in a row, and also remove a source of 1744 // non-determinism. 1745 std::vector<ValueRef *> refs(dval->uses.begin(), dval->uses.end()); 1746 std::sort(refs.begin(), refs.end(), value_cmp); 1747 1748 // Unspill at each use *before* inserting spill instructions, 1749 // we don't want to have the spill instructions in the use list here. 1750 for (std::vector<ValueRef*>::const_iterator it = refs.begin(); 1751 it != refs.end(); ++it) { 1752 ValueRef *u = *it; 1753 Instruction *usei = u->getInsn(); 1754 assert(usei); 1755 if (usei->isPseudo()) { 1756 tmp = (slot->reg.file == FILE_MEMORY_LOCAL) ? NULL : slot; 1757 last = NULL; 1758 } else { 1759 if (!last || (usei != last->next && usei != last)) 1760 tmp = unspill(usei, dval, slot); 1761 last = usei; 1762 } 1763 u->set(tmp); 1764 } 1765 1766 assert(defi); 1767 if (defi->isPseudo()) { 1768 d = lval->defs.erase(d); 1769 --d; 1770 if (slot->reg.file == FILE_MEMORY_LOCAL) 1771 to_del.insert(defi); 1772 else 1773 defi->setDef(0, slot); 1774 } else { 1775 spill(defi, slot, dval); 1776 } 1777 } 1778 1779 for (unordered_set<Instruction *>::const_iterator it = to_del.begin(); 1780 it != to_del.end(); ++it) 1781 delete_Instruction(func->getProgram(), *it); 1782 } 1783 1784 // TODO: We're not trying to reuse old slots in a potential next iteration. 1785 // We have to update the slots' livei intervals to be able to do that. 1786 stackBase = stackSize; 1787 slots.clear(); 1788 return true; 1789 } 1790 1791 bool 1792 RegAlloc::exec() 1793 { 1794 for (IteratorRef it = prog->calls.iteratorDFS(false); 1795 !it->end(); it->next()) { 1796 func = Function::get(reinterpret_cast<Graph::Node *>(it->get())); 1797 1798 func->tlsBase = prog->tlsSize; 1799 if (!execFunc()) 1800 return false; 1801 prog->tlsSize += func->tlsSize; 1802 } 1803 return true; 1804 } 1805 1806 bool 1807 RegAlloc::execFunc() 1808 { 1809 InsertConstraintsPass insertConstr; 1810 PhiMovesPass insertPhiMoves; 1811 ArgumentMovesPass insertArgMoves; 1812 BuildIntervalsPass buildIntervals; 1813 SpillCodeInserter insertSpills(func); 1814 1815 GCRA gcra(func, insertSpills); 1816 1817 unsigned int i, retries; 1818 bool ret; 1819 1820 if (!func->ins.empty()) { 1821 // Insert a nop at the entry so inputs only used by the first instruction 1822 // don't count as having an empty live range. 1823 Instruction *nop = new_Instruction(func, OP_NOP, TYPE_NONE); 1824 BasicBlock::get(func->cfg.getRoot())->insertHead(nop); 1825 } 1826 1827 ret = insertConstr.exec(func); 1828 if (!ret) 1829 goto out; 1830 1831 ret = insertPhiMoves.run(func); 1832 if (!ret) 1833 goto out; 1834 1835 ret = insertArgMoves.run(func); 1836 if (!ret) 1837 goto out; 1838 1839 // TODO: need to fix up spill slot usage ranges to support > 1 retry 1840 for (retries = 0; retries < 3; ++retries) { 1841 if (retries && (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)) 1842 INFO("Retry: %i\n", retries); 1843 if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) 1844 func->print(); 1845 1846 // spilling to registers may add live ranges, need to rebuild everything 1847 ret = true; 1848 for (sequence = func->cfg.nextSequence(), i = 0; 1849 ret && i <= func->loopNestingBound; 1850 sequence = func->cfg.nextSequence(), ++i) 1851 ret = buildLiveSets(BasicBlock::get(func->cfg.getRoot())); 1852 // reset marker 1853 for (ArrayList::Iterator bi = func->allBBlocks.iterator(); 1854 !bi.end(); bi.next()) 1855 BasicBlock::get(bi)->liveSet.marker = false; 1856 if (!ret) 1857 break; 1858 func->orderInstructions(this->insns); 1859 1860 ret = buildIntervals.run(func); 1861 if (!ret) 1862 break; 1863 ret = gcra.allocateRegisters(insns); 1864 if (ret) 1865 break; // success 1866 } 1867 INFO_DBG(prog->dbgFlags, REG_ALLOC, "RegAlloc done: %i\n", ret); 1868 1869 func->tlsSize = insertSpills.getStackSize(); 1870 out: 1871 return ret; 1872 } 1873 1874 // TODO: check if modifying Instruction::join here breaks anything 1875 void 1876 GCRA::resolveSplitsAndMerges() 1877 { 1878 for (std::list<Instruction *>::iterator it = splits.begin(); 1879 it != splits.end(); 1880 ++it) { 1881 Instruction *split = *it; 1882 unsigned int reg = regs.idToBytes(split->getSrc(0)); 1883 for (int d = 0; split->defExists(d); ++d) { 1884 Value *v = split->getDef(d); 1885 v->reg.data.id = regs.bytesToId(v, reg); 1886 v->join = v; 1887 reg += v->reg.size; 1888 } 1889 } 1890 splits.clear(); 1891 1892 for (std::list<Instruction *>::iterator it = merges.begin(); 1893 it != merges.end(); 1894 ++it) { 1895 Instruction *merge = *it; 1896 unsigned int reg = regs.idToBytes(merge->getDef(0)); 1897 for (int s = 0; merge->srcExists(s); ++s) { 1898 Value *v = merge->getSrc(s); 1899 v->reg.data.id = regs.bytesToId(v, reg); 1900 v->join = v; 1901 // If the value is defined by a phi/union node, we also need to 1902 // perform the same fixup on that node's sources, since after RA 1903 // their registers should be identical. 1904 if (v->getInsn()->op == OP_PHI || v->getInsn()->op == OP_UNION) { 1905 Instruction *phi = v->getInsn(); 1906 for (int phis = 0; phi->srcExists(phis); ++phis) { 1907 phi->getSrc(phis)->join = v; 1908 phi->getSrc(phis)->reg.data.id = v->reg.data.id; 1909 } 1910 } 1911 reg += v->reg.size; 1912 } 1913 } 1914 merges.clear(); 1915 } 1916 1917 bool Program::registerAllocation() 1918 { 1919 RegAlloc ra(this); 1920 return ra.exec(); 1921 } 1922 1923 bool 1924 RegAlloc::InsertConstraintsPass::exec(Function *ir) 1925 { 1926 constrList.clear(); 1927 1928 bool ret = run(ir, true, true); 1929 if (ret) 1930 ret = insertConstraintMoves(); 1931 return ret; 1932 } 1933 1934 // TODO: make part of texture insn 1935 void 1936 RegAlloc::InsertConstraintsPass::textureMask(TexInstruction *tex) 1937 { 1938 Value *def[4]; 1939 int c, k, d; 1940 uint8_t mask = 0; 1941 1942 for (d = 0, k = 0, c = 0; c < 4; ++c) { 1943 if (!(tex->tex.mask & (1 << c))) 1944 continue; 1945 if (tex->getDef(k)->refCount()) { 1946 mask |= 1 << c; 1947 def[d++] = tex->getDef(k); 1948 } 1949 ++k; 1950 } 1951 tex->tex.mask = mask; 1952 1953 for (c = 0; c < d; ++c) 1954 tex->setDef(c, def[c]); 1955 for (; c < 4; ++c) 1956 tex->setDef(c, NULL); 1957 } 1958 1959 bool 1960 RegAlloc::InsertConstraintsPass::detectConflict(Instruction *cst, int s) 1961 { 1962 Value *v = cst->getSrc(s); 1963 1964 // current register allocation can't handle it if a value participates in 1965 // multiple constraints 1966 for (Value::UseIterator it = v->uses.begin(); it != v->uses.end(); ++it) { 1967 if (cst != (*it)->getInsn()) 1968 return true; 1969 } 1970 1971 // can start at s + 1 because detectConflict is called on all sources 1972 for (int c = s + 1; cst->srcExists(c); ++c) 1973 if (v == cst->getSrc(c)) 1974 return true; 1975 1976 Instruction *defi = v->getInsn(); 1977 1978 return (!defi || defi->constrainedDefs()); 1979 } 1980 1981 void 1982 RegAlloc::InsertConstraintsPass::addConstraint(Instruction *i, int s, int n) 1983 { 1984 Instruction *cst; 1985 int d; 1986 1987 // first, look for an existing identical constraint op 1988 for (std::list<Instruction *>::iterator it = constrList.begin(); 1989 it != constrList.end(); 1990 ++it) { 1991 cst = (*it); 1992 if (!i->bb->dominatedBy(cst->bb)) 1993 break; 1994 for (d = 0; d < n; ++d) 1995 if (cst->getSrc(d) != i->getSrc(d + s)) 1996 break; 1997 if (d >= n) { 1998 for (d = 0; d < n; ++d, ++s) 1999 i->setSrc(s, cst->getDef(d)); 2000 return; 2001 } 2002 } 2003 cst = new_Instruction(func, OP_CONSTRAINT, i->dType); 2004 2005 for (d = 0; d < n; ++s, ++d) { 2006 cst->setDef(d, new_LValue(func, FILE_GPR)); 2007 cst->setSrc(d, i->getSrc(s)); 2008 i->setSrc(s, cst->getDef(d)); 2009 } 2010 i->bb->insertBefore(i, cst); 2011 2012 constrList.push_back(cst); 2013 } 2014 2015 // Add a dummy use of the pointer source of >= 8 byte loads after the load 2016 // to prevent it from being assigned a register which overlapping the load's 2017 // destination, which would produce random corruptions. 2018 void 2019 RegAlloc::InsertConstraintsPass::addHazard(Instruction *i, const ValueRef *src) 2020 { 2021 Instruction *hzd = new_Instruction(func, OP_NOP, TYPE_NONE); 2022 hzd->setSrc(0, src->get()); 2023 i->bb->insertAfter(i, hzd); 2024 2025 } 2026 2027 // b32 { %r0 %r1 %r2 %r3 } -> b128 %r0q 2028 void 2029 RegAlloc::InsertConstraintsPass::condenseDefs(Instruction *insn) 2030 { 2031 uint8_t size = 0; 2032 int n; 2033 for (n = 0; insn->defExists(n) && insn->def(n).getFile() == FILE_GPR; ++n) 2034 size += insn->getDef(n)->reg.size; 2035 if (n < 2) 2036 return; 2037 LValue *lval = new_LValue(func, FILE_GPR); 2038 lval->reg.size = size; 2039 2040 Instruction *split = new_Instruction(func, OP_SPLIT, typeOfSize(size)); 2041 split->setSrc(0, lval); 2042 for (int d = 0; d < n; ++d) { 2043 split->setDef(d, insn->getDef(d)); 2044 insn->setDef(d, NULL); 2045 } 2046 insn->setDef(0, lval); 2047 2048 for (int k = 1, d = n; insn->defExists(d); ++d, ++k) { 2049 insn->setDef(k, insn->getDef(d)); 2050 insn->setDef(d, NULL); 2051 } 2052 // carry over predicate if any (mainly for OP_UNION uses) 2053 split->setPredicate(insn->cc, insn->getPredicate()); 2054 2055 insn->bb->insertAfter(insn, split); 2056 constrList.push_back(split); 2057 } 2058 void 2059 RegAlloc::InsertConstraintsPass::condenseSrcs(Instruction *insn, 2060 const int a, const int b) 2061 { 2062 uint8_t size = 0; 2063 if (a >= b) 2064 return; 2065 for (int s = a; s <= b; ++s) 2066 size += insn->getSrc(s)->reg.size; 2067 if (!size) 2068 return; 2069 LValue *lval = new_LValue(func, FILE_GPR); 2070 lval->reg.size = size; 2071 2072 Value *save[3]; 2073 insn->takeExtraSources(0, save); 2074 2075 Instruction *merge = new_Instruction(func, OP_MERGE, typeOfSize(size)); 2076 merge->setDef(0, lval); 2077 for (int s = a, i = 0; s <= b; ++s, ++i) { 2078 merge->setSrc(i, insn->getSrc(s)); 2079 } 2080 insn->moveSources(b + 1, a - b); 2081 insn->setSrc(a, lval); 2082 insn->bb->insertBefore(insn, merge); 2083 2084 insn->putExtraSources(0, save); 2085 2086 constrList.push_back(merge); 2087 } 2088 2089 void 2090 RegAlloc::InsertConstraintsPass::texConstraintGM107(TexInstruction *tex) 2091 { 2092 int n, s; 2093 2094 if (isTextureOp(tex->op)) 2095 textureMask(tex); 2096 condenseDefs(tex); 2097 2098 if (isSurfaceOp(tex->op)) { 2099 int s = tex->tex.target.getDim() + 2100 (tex->tex.target.isArray() || tex->tex.target.isCube()); 2101 int n = 0; 2102 2103 switch (tex->op) { 2104 case OP_SUSTB: 2105 case OP_SUSTP: 2106 n = 4; 2107 break; 2108 case OP_SUREDB: 2109 case OP_SUREDP: 2110 if (tex->subOp == NV50_IR_SUBOP_ATOM_CAS) 2111 n = 2; 2112 break; 2113 default: 2114 break; 2115 } 2116 2117 if (s > 1) 2118 condenseSrcs(tex, 0, s - 1); 2119 if (n > 1) 2120 condenseSrcs(tex, 1, n); // do not condense the tex handle 2121 } else 2122 if (isTextureOp(tex->op)) { 2123 if (tex->op != OP_TXQ) { 2124 s = tex->tex.target.getArgCount() - tex->tex.target.isMS(); 2125 if (tex->op == OP_TXD) { 2126 // Indirect handle belongs in the first arg 2127 if (tex->tex.rIndirectSrc >= 0) 2128 s++; 2129 if (!tex->tex.target.isArray() && tex->tex.useOffsets) 2130 s++; 2131 } 2132 n = tex->srcCount(0xff) - s; 2133 } else { 2134 s = tex->srcCount(0xff); 2135 n = 0; 2136 } 2137 2138 if (s > 1) 2139 condenseSrcs(tex, 0, s - 1); 2140 if (n > 1) // NOTE: first call modified positions already 2141 condenseSrcs(tex, 1, n); 2142 } 2143 } 2144 2145 void 2146 RegAlloc::InsertConstraintsPass::texConstraintNVE0(TexInstruction *tex) 2147 { 2148 if (isTextureOp(tex->op)) 2149 textureMask(tex); 2150 condenseDefs(tex); 2151 2152 if (tex->op == OP_SUSTB || tex->op == OP_SUSTP) { 2153 condenseSrcs(tex, 3, 6); 2154 } else 2155 if (isTextureOp(tex->op)) { 2156 int n = tex->srcCount(0xff, true); 2157 if (n > 4) { 2158 condenseSrcs(tex, 0, 3); 2159 if (n > 5) // NOTE: first call modified positions already 2160 condenseSrcs(tex, 4 - (4 - 1), n - 1 - (4 - 1)); 2161 } else 2162 if (n > 1) { 2163 condenseSrcs(tex, 0, n - 1); 2164 } 2165 } 2166 } 2167 2168 void 2169 RegAlloc::InsertConstraintsPass::texConstraintNVC0(TexInstruction *tex) 2170 { 2171 int n, s; 2172 2173 if (isTextureOp(tex->op)) 2174 textureMask(tex); 2175 2176 if (tex->op == OP_TXQ) { 2177 s = tex->srcCount(0xff); 2178 n = 0; 2179 } else if (isSurfaceOp(tex->op)) { 2180 s = tex->tex.target.getDim() + (tex->tex.target.isArray() || tex->tex.target.isCube()); 2181 if (tex->op == OP_SUSTB || tex->op == OP_SUSTP) 2182 n = 4; 2183 else 2184 n = 0; 2185 } else { 2186 s = tex->tex.target.getArgCount() - tex->tex.target.isMS(); 2187 if (!tex->tex.target.isArray() && 2188 (tex->tex.rIndirectSrc >= 0 || tex->tex.sIndirectSrc >= 0)) 2189 ++s; 2190 if (tex->op == OP_TXD && tex->tex.useOffsets) 2191 ++s; 2192 n = tex->srcCount(0xff) - s; 2193 assert(n <= 4); 2194 } 2195 2196 if (s > 1) 2197 condenseSrcs(tex, 0, s - 1); 2198 if (n > 1) // NOTE: first call modified positions already 2199 condenseSrcs(tex, 1, n); 2200 2201 condenseDefs(tex); 2202 } 2203 2204 void 2205 RegAlloc::InsertConstraintsPass::texConstraintNV50(TexInstruction *tex) 2206 { 2207 Value *pred = tex->getPredicate(); 2208 if (pred) 2209 tex->setPredicate(tex->cc, NULL); 2210 2211 textureMask(tex); 2212 2213 assert(tex->defExists(0) && tex->srcExists(0)); 2214 // make src and def count match 2215 int c; 2216 for (c = 0; tex->srcExists(c) || tex->defExists(c); ++c) { 2217 if (!tex->srcExists(c)) 2218 tex->setSrc(c, new_LValue(func, tex->getSrc(0)->asLValue())); 2219 if (!tex->defExists(c)) 2220 tex->setDef(c, new_LValue(func, tex->getDef(0)->asLValue())); 2221 } 2222 if (pred) 2223 tex->setPredicate(tex->cc, pred); 2224 condenseDefs(tex); 2225 condenseSrcs(tex, 0, c - 1); 2226 } 2227 2228 // Insert constraint markers for instructions whose multiple sources must be 2229 // located in consecutive registers. 2230 bool 2231 RegAlloc::InsertConstraintsPass::visit(BasicBlock *bb) 2232 { 2233 TexInstruction *tex; 2234 Instruction *next; 2235 int s, size; 2236 2237 targ = bb->getProgram()->getTarget(); 2238 2239 for (Instruction *i = bb->getEntry(); i; i = next) { 2240 next = i->next; 2241 2242 if ((tex = i->asTex())) { 2243 switch (targ->getChipset() & ~0xf) { 2244 case 0x50: 2245 case 0x80: 2246 case 0x90: 2247 case 0xa0: 2248 texConstraintNV50(tex); 2249 break; 2250 case 0xc0: 2251 case 0xd0: 2252 texConstraintNVC0(tex); 2253 break; 2254 case 0xe0: 2255 case 0xf0: 2256 case 0x100: 2257 texConstraintNVE0(tex); 2258 break; 2259 case 0x110: 2260 case 0x120: 2261 case 0x130: 2262 texConstraintGM107(tex); 2263 break; 2264 default: 2265 break; 2266 } 2267 } else 2268 if (i->op == OP_EXPORT || i->op == OP_STORE) { 2269 for (size = typeSizeof(i->dType), s = 1; size > 0; ++s) { 2270 assert(i->srcExists(s)); 2271 size -= i->getSrc(s)->reg.size; 2272 } 2273 condenseSrcs(i, 1, s - 1); 2274 } else 2275 if (i->op == OP_LOAD || i->op == OP_VFETCH) { 2276 condenseDefs(i); 2277 if (i->src(0).isIndirect(0) && typeSizeof(i->dType) >= 8) 2278 addHazard(i, i->src(0).getIndirect(0)); 2279 if (i->src(0).isIndirect(1) && typeSizeof(i->dType) >= 8) 2280 addHazard(i, i->src(0).getIndirect(1)); 2281 } else 2282 if (i->op == OP_UNION || 2283 i->op == OP_MERGE || 2284 i->op == OP_SPLIT) { 2285 constrList.push_back(i); 2286 } 2287 } 2288 return true; 2289 } 2290 2291 // Insert extra moves so that, if multiple register constraints on a value are 2292 // in conflict, these conflicts can be resolved. 2293 bool 2294 RegAlloc::InsertConstraintsPass::insertConstraintMoves() 2295 { 2296 for (std::list<Instruction *>::iterator it = constrList.begin(); 2297 it != constrList.end(); 2298 ++it) { 2299 Instruction *cst = *it; 2300 Instruction *mov; 2301 2302 if (cst->op == OP_SPLIT && 0) { 2303 // spilling splits is annoying, just make sure they're separate 2304 for (int d = 0; cst->defExists(d); ++d) { 2305 if (!cst->getDef(d)->refCount()) 2306 continue; 2307 LValue *lval = new_LValue(func, cst->def(d).getFile()); 2308 const uint8_t size = cst->def(d).getSize(); 2309 lval->reg.size = size; 2310 2311 mov = new_Instruction(func, OP_MOV, typeOfSize(size)); 2312 mov->setSrc(0, lval); 2313 mov->setDef(0, cst->getDef(d)); 2314 cst->setDef(d, mov->getSrc(0)); 2315 cst->bb->insertAfter(cst, mov); 2316 2317 cst->getSrc(0)->asLValue()->noSpill = 1; 2318 mov->getSrc(0)->asLValue()->noSpill = 1; 2319 } 2320 } else 2321 if (cst->op == OP_MERGE || cst->op == OP_UNION) { 2322 for (int s = 0; cst->srcExists(s); ++s) { 2323 const uint8_t size = cst->src(s).getSize(); 2324 2325 if (!cst->getSrc(s)->defs.size()) { 2326 mov = new_Instruction(func, OP_NOP, typeOfSize(size)); 2327 mov->setDef(0, cst->getSrc(s)); 2328 cst->bb->insertBefore(cst, mov); 2329 continue; 2330 } 2331 assert(cst->getSrc(s)->defs.size() == 1); // still SSA 2332 2333 Instruction *defi = cst->getSrc(s)->defs.front()->getInsn(); 2334 bool imm = defi->op == OP_MOV && 2335 defi->src(0).getFile() == FILE_IMMEDIATE; 2336 bool load = defi->op == OP_LOAD && 2337 defi->src(0).getFile() == FILE_MEMORY_CONST && 2338 !defi->src(0).isIndirect(0); 2339 // catch some cases where don't really need MOVs 2340 if (cst->getSrc(s)->refCount() == 1 && !defi->constrainedDefs()) { 2341 if (imm || load) { 2342 // Move the defi right before the cst. No point in expanding 2343 // the range. 2344 defi->bb->remove(defi); 2345 cst->bb->insertBefore(cst, defi); 2346 } 2347 continue; 2348 } 2349 2350 LValue *lval = new_LValue(func, cst->src(s).getFile()); 2351 lval->reg.size = size; 2352 2353 mov = new_Instruction(func, OP_MOV, typeOfSize(size)); 2354 mov->setDef(0, lval); 2355 mov->setSrc(0, cst->getSrc(s)); 2356 2357 if (load) { 2358 mov->op = OP_LOAD; 2359 mov->setSrc(0, defi->getSrc(0)); 2360 } else if (imm) { 2361 mov->setSrc(0, defi->getSrc(0)); 2362 } 2363 2364 cst->setSrc(s, mov->getDef(0)); 2365 cst->bb->insertBefore(cst, mov); 2366 2367 cst->getDef(0)->asLValue()->noSpill = 1; // doesn't help 2368 2369 if (cst->op == OP_UNION) 2370 mov->setPredicate(defi->cc, defi->getPredicate()); 2371 } 2372 } 2373 } 2374 2375 return true; 2376 } 2377 2378 } // namespace nv50_ir 2379