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