Debian Codegraph @

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

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