Move nv30, nv50 and nvc0 to nouveau.

It is planned to ship openSUSE 13.1 with -shared libs.
nouveau.la, nv30.la, nv50.la and nvc0.la are currently LIBADDs in all nouveau
related targets.
This change makes it possible to easily build one shared libnouveau.so which is
then LIBADDed.
Also dlopen will be faster for one library instead of three and build time on
-jX will be reduced.

Whitespace fixes were requested by 'git am'.

Signed-off-by: Johannes Obermayr <johannesobermayr@gmx.de>
Acked-by: Christoph Bumiller <christoph.bumiller@speed.at>
Acked-by: Ian Romanick <ian.d.romanick@intel.com>

1 files changed, 2050 insertions, 0 deletions

diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
new file mode 100644
index 00000000000..d65003ce4eb
--- /dev/null
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
@@ -0,0 +1,2050 @@
+/*
+ * Copyright 2011 Christoph Bumiller
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#include "codegen/nv50_ir.h"
+#include "codegen/nv50_ir_target.h"
+
+#include <stack>
+#include <limits>
+
+namespace nv50_ir {
+
+#define MAX_REGISTER_FILE_SIZE 256
+
+class RegisterSet
+{
+public:
+   RegisterSet(const Target *);
+
+   void init(const Target *);
+   void reset(DataFile, bool resetMax = false);
+
+   void periodicMask(DataFile f, uint32_t lock, uint32_t unlock);
+   void intersect(DataFile f, const RegisterSet *);
+
+   bool assign(int32_t& reg, DataFile f, unsigned int size);
+   void release(DataFile f, int32_t reg, unsigned int size);
+   void occupy(DataFile f, int32_t reg, unsigned int size);
+   void occupy(const Value *);
+   void occupyMask(DataFile f, int32_t reg, uint8_t mask);
+   bool isOccupied(DataFile f, int32_t reg, unsigned int size) const;
+   bool testOccupy(const Value *);
+   bool testOccupy(DataFile f, int32_t reg, unsigned int size);
+
+   inline int getMaxAssigned(DataFile f) const { return fill[f]; }
+
+   inline unsigned int getFileSize(DataFile f, uint8_t regSize) const
+   {
+      if (restrictedGPR16Range && f == FILE_GPR && regSize == 2)
+         return (last[f] + 1) / 2;
+      return last[f] + 1;
+   }
+
+   inline unsigned int units(DataFile f, unsigned int size) const
+   {
+      return size >> unit[f];
+   }
+   // for regs of size >= 4, id is counted in 4-byte words (like nv50/c0 binary)
+   inline unsigned int idToBytes(const Value *v) const
+   {
+      return v->reg.data.id * MIN2(v->reg.size, 4);
+   }
+   inline unsigned int idToUnits(const Value *v) const
+   {
+      return units(v->reg.file, idToBytes(v));
+   }
+   inline int bytesToId(Value *v, unsigned int bytes) const
+   {
+      if (v->reg.size < 4)
+         return units(v->reg.file, bytes);
+      return bytes / 4;
+   }
+   inline int unitsToId(DataFile f, int u, uint8_t size) const
+   {
+      if (u < 0)
+         return -1;
+      return (size < 4) ? u : ((u << unit[f]) / 4);
+   }
+
+   void print() const;
+
+private:
+   BitSet bits[LAST_REGISTER_FILE + 1];
+
+   int unit[LAST_REGISTER_FILE + 1]; // log2 of allocation granularity
+
+   int last[LAST_REGISTER_FILE + 1];
+   int fill[LAST_REGISTER_FILE + 1];
+
+   const bool restrictedGPR16Range;
+};
+
+void
+RegisterSet::reset(DataFile f, bool resetMax)
+{
+   bits[f].fill(0);
+   if (resetMax)
+      fill[f] = -1;
+}
+
+void
+RegisterSet::init(const Target *targ)
+{
+   for (unsigned int rf = 0; rf <= FILE_ADDRESS; ++rf) {
+      DataFile f = static_cast<DataFile>(rf);
+      last[rf] = targ->getFileSize(f) - 1;
+      unit[rf] = targ->getFileUnit(f);
+      fill[rf] = -1;
+      assert(last[rf] < MAX_REGISTER_FILE_SIZE);
+      bits[rf].allocate(last[rf] + 1, true);
+   }
+}
+
+RegisterSet::RegisterSet(const Target *targ)
+  : restrictedGPR16Range(targ->getChipset() < 0xc0)
+{
+   init(targ);
+   for (unsigned int i = 0; i <= LAST_REGISTER_FILE; ++i)
+      reset(static_cast<DataFile>(i));
+}
+
+void
+RegisterSet::periodicMask(DataFile f, uint32_t lock, uint32_t unlock)
+{
+   bits[f].periodicMask32(lock, unlock);
+}
+
+void
+RegisterSet::intersect(DataFile f, const RegisterSet *set)
+{
+   bits[f] |= set->bits[f];
+}
+
+void
+RegisterSet::print() const
+{
+   INFO("GPR:");
+   bits[FILE_GPR].print();
+   INFO("\n");
+}
+
+bool
+RegisterSet::assign(int32_t& reg, DataFile f, unsigned int size)
+{
+   reg = bits[f].findFreeRange(size);
+   if (reg < 0)
+      return false;
+   fill[f] = MAX2(fill[f], (int32_t)(reg + size - 1));
+   return true;
+}
+
+bool
+RegisterSet::isOccupied(DataFile f, int32_t reg, unsigned int size) const
+{
+   return bits[f].testRange(reg, size);
+}
+
+void
+RegisterSet::occupy(const Value *v)
+{
+   occupy(v->reg.file, idToUnits(v), v->reg.size >> unit[v->reg.file]);
+}
+
+void
+RegisterSet::occupyMask(DataFile f, int32_t reg, uint8_t mask)
+{
+   bits[f].setMask(reg & ~31, static_cast<uint32_t>(mask) << (reg % 32));
+}
+
+void
+RegisterSet::occupy(DataFile f, int32_t reg, unsigned int size)
+{
+   bits[f].setRange(reg, size);
+
+   INFO_DBG(0, REG_ALLOC, "reg occupy: %u[%i] %u\n", f, reg, size);
+
+   fill[f] = MAX2(fill[f], (int32_t)(reg + size - 1));
+}
+
+bool
+RegisterSet::testOccupy(const Value *v)
+{
+   return testOccupy(v->reg.file,
+                     idToUnits(v), v->reg.size >> unit[v->reg.file]);
+}
+
+bool
+RegisterSet::testOccupy(DataFile f, int32_t reg, unsigned int size)
+{
+   if (isOccupied(f, reg, size))
+      return false;
+   occupy(f, reg, size);
+   return true;
+}
+
+void
+RegisterSet::release(DataFile f, int32_t reg, unsigned int size)
+{
+   bits[f].clrRange(reg, size);
+
+   INFO_DBG(0, REG_ALLOC, "reg release: %u[%i] %u\n", f, reg, size);
+}
+
+class RegAlloc
+{
+public:
+   RegAlloc(Program *program) : prog(program), sequence(0) { }
+
+   bool exec();
+   bool execFunc();
+
+private:
+   class PhiMovesPass : public Pass {
+   private:
+      virtual bool visit(BasicBlock *);
+      inline bool needNewElseBlock(BasicBlock *b, BasicBlock *p);
+   };
+
+   class ArgumentMovesPass : public Pass {
+   private:
+      virtual bool visit(BasicBlock *);
+   };
+
+   class BuildIntervalsPass : public Pass {
+   private:
+      virtual bool visit(BasicBlock *);
+      void collectLiveValues(BasicBlock *);
+      void addLiveRange(Value *, const BasicBlock *, int end);
+   };
+
+   class InsertConstraintsPass : public Pass {
+   public:
+      bool exec(Function *func);
+   private:
+      virtual bool visit(BasicBlock *);
+
+      bool insertConstraintMoves();
+
+      void condenseDefs(Instruction *);
+      void condenseSrcs(Instruction *, const int first, const int last);
+
+      void addHazard(Instruction *i, const ValueRef *src);
+      void textureMask(TexInstruction *);
+      void addConstraint(Instruction *, int s, int n);
+      bool detectConflict(Instruction *, int s);
+
+      // target specific functions, TODO: put in subclass or Target
+      void texConstraintNV50(TexInstruction *);
+      void texConstraintNVC0(TexInstruction *);
+      void texConstraintNVE0(TexInstruction *);
+
+      std::list<Instruction *> constrList;
+
+      const Target *targ;
+   };
+
+   bool buildLiveSets(BasicBlock *);
+
+private:
+   Program *prog;
+   Function *func;
+
+   // instructions in control flow / chronological order
+   ArrayList insns;
+
+   int sequence; // for manual passes through CFG
+};
+
+typedef std::pair<Value *, Value *> ValuePair;
+
+class SpillCodeInserter
+{
+public:
+   SpillCodeInserter(Function *fn) : func(fn), stackSize(0), stackBase(0) { }
+
+   bool run(const std::list<ValuePair>&);
+
+   Symbol *assignSlot(const Interval&, const unsigned int size);
+   inline int32_t getStackSize() const { return stackSize; }
+
+private:
+   Function *func;
+
+   struct SpillSlot
+   {
+      Interval occup;
+      std::list<Value *> residents; // needed to recalculate occup
+      Symbol *sym;
+      int32_t offset;
+      inline uint8_t size() const { return sym->reg.size; }
+   };
+   std::list<SpillSlot> slots;
+   int32_t stackSize;
+   int32_t stackBase;
+
+   LValue *unspill(Instruction *usei, LValue *, Value *slot);
+   void spill(Instruction *defi, Value *slot, LValue *);
+};
+
+void
+RegAlloc::BuildIntervalsPass::addLiveRange(Value *val,
+                                           const BasicBlock *bb,
+                                           int end)
+{
+   Instruction *insn = val->getUniqueInsn();
+
+   if (!insn)
+      insn = bb->getFirst();
+
+   assert(bb->getFirst()->serial <= bb->getExit()->serial);
+   assert(bb->getExit()->serial + 1 >= end);
+
+   int begin = insn->serial;
+   if (begin < bb->getEntry()->serial || begin > bb->getExit()->serial)
+      begin = bb->getEntry()->serial;
+
+   INFO_DBG(prog->dbgFlags, REG_ALLOC, "%%%i <- live range [%i(%i), %i)\n",
+            val->id, begin, insn->serial, end);
+
+   if (begin != end) // empty ranges are only added as hazards for fixed regs
+      val->livei.extend(begin, end);
+}
+
+bool
+RegAlloc::PhiMovesPass::needNewElseBlock(BasicBlock *b, BasicBlock *p)
+{
+   if (b->cfg.incidentCount() <= 1)
+      return false;
+
+   int n = 0;
+   for (Graph::EdgeIterator ei = p->cfg.outgoing(); !ei.end(); ei.next())
+      if (ei.getType() == Graph::Edge::TREE ||
+          ei.getType() == Graph::Edge::FORWARD)
+         ++n;
+   return (n == 2);
+}
+
+// For each operand of each PHI in b, generate a new value by inserting a MOV
+// at the end of the block it is coming from and replace the operand with its
+// result. This eliminates liveness conflicts and enables us to let values be
+// copied to the right register if such a conflict exists nonetheless.
+//
+// These MOVs are also crucial in making sure the live intervals of phi srces
+// are extended until the end of the loop, since they are not included in the
+// live-in sets.
+bool
+RegAlloc::PhiMovesPass::visit(BasicBlock *bb)
+{
+   Instruction *phi, *mov;
+   BasicBlock *pb, *pn;
+
+   std::stack<BasicBlock *> stack;
+
+   for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) {
+      pb = BasicBlock::get(ei.getNode());
+      assert(pb);
+      if (needNewElseBlock(bb, pb))
+         stack.push(pb);
+   }
+   while (!stack.empty()) {
+      pb = stack.top();
+      pn = new BasicBlock(func);
+      stack.pop();
+
+      pb->cfg.detach(&bb->cfg);
+      pb->cfg.attach(&pn->cfg, Graph::Edge::TREE);
+      pn->cfg.attach(&bb->cfg, Graph::Edge::FORWARD);
+
+      assert(pb->getExit()->op != OP_CALL);
+      if (pb->getExit()->asFlow()->target.bb == bb)
+         pb->getExit()->asFlow()->target.bb = pn;
+   }
+
+   // insert MOVs (phi->src(j) should stem from j-th in-BB)
+   int j = 0;
+   for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) {
+      pb = BasicBlock::get(ei.getNode());
+      if (!pb->isTerminated())
+         pb->insertTail(new_FlowInstruction(func, OP_BRA, bb));
+
+      for (phi = bb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) {
+         mov = new_Instruction(func, OP_MOV, TYPE_U32);
+
+         mov->setSrc(0, phi->getSrc(j));
+         mov->setDef(0, new_LValue(func, phi->getDef(0)->asLValue()));
+         phi->setSrc(j, mov->getDef(0));
+
+         pb->insertBefore(pb->getExit(), mov);
+      }
+      ++j;
+   }
+
+   return true;
+}
+
+bool
+RegAlloc::ArgumentMovesPass::visit(BasicBlock *bb)
+{
+   // Bind function call inputs/outputs to the same physical register
+   // the callee uses, inserting moves as appropriate for the case a
+   // conflict arises.
+   for (Instruction *i = bb->getEntry(); i; i = i->next) {
+      FlowInstruction *cal = i->asFlow();
+      // TODO: Handle indirect calls.
+      // Right now they should only be generated for builtins.
+      if (!cal || cal->op != OP_CALL || cal->builtin || cal->indirect)
+         continue;
+      RegisterSet clobberSet(prog->getTarget());
+
+      // Bind input values.
+      for (int s = cal->indirect ? 1 : 0; cal->srcExists(s); ++s) {
+         const int t = cal->indirect ? (s - 1) : s;
+         LValue *tmp = new_LValue(func, cal->getSrc(s)->asLValue());
+         tmp->reg.data.id = cal->target.fn->ins[t].rep()->reg.data.id;
+
+         Instruction *mov =
+            new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size));
+         mov->setDef(0, tmp);
+         mov->setSrc(0, cal->getSrc(s));
+         cal->setSrc(s, tmp);
+
+         bb->insertBefore(cal, mov);
+      }
+
+      // Bind output values.
+      for (int d = 0; cal->defExists(d); ++d) {
+         LValue *tmp = new_LValue(func, cal->getDef(d)->asLValue());
+         tmp->reg.data.id = cal->target.fn->outs[d].rep()->reg.data.id;
+
+         Instruction *mov =
+            new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size));
+         mov->setSrc(0, tmp);
+         mov->setDef(0, cal->getDef(d));
+         cal->setDef(d, tmp);
+
+         bb->insertAfter(cal, mov);
+         clobberSet.occupy(tmp);
+      }
+
+      // Bind clobbered values.
+      for (std::deque<Value *>::iterator it = cal->target.fn->clobbers.begin();
+           it != cal->target.fn->clobbers.end();
+           ++it) {
+         if (clobberSet.testOccupy(*it)) {
+            Value *tmp = new_LValue(func, (*it)->asLValue());
+            tmp->reg.data.id = (*it)->reg.data.id;
+            cal->setDef(cal->defCount(), tmp);
+         }
+      }
+   }
+
+   // Update the clobber set of the function.
+   if (BasicBlock::get(func->cfgExit) == bb) {
+      func->buildDefSets();
+      for (unsigned int i = 0; i < bb->defSet.getSize(); ++i)
+         if (bb->defSet.test(i))
+            func->clobbers.push_back(func->getLValue(i));
+   }
+
+   return true;
+}
+
+// Build the set of live-in variables of bb.
+bool
+RegAlloc::buildLiveSets(BasicBlock *bb)
+{
+   Function *f = bb->getFunction();
+   BasicBlock *bn;
+   Instruction *i;
+   unsigned int s, d;
+
+   INFO_DBG(prog->dbgFlags, REG_ALLOC, "buildLiveSets(BB:%i)\n", bb->getId());
+
+   bb->liveSet.allocate(func->allLValues.getSize(), false);
+
+   int n = 0;
+   for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
+      bn = BasicBlock::get(ei.getNode());
+      if (bn == bb)
+         continue;
+      if (bn->cfg.visit(sequence))
+         if (!buildLiveSets(bn))
+            return false;
+      if (n++ || bb->liveSet.marker)
+         bb->liveSet |= bn->liveSet;
+      else
+         bb->liveSet = bn->liveSet;
+   }
+   if (!n && !bb->liveSet.marker)
+      bb->liveSet.fill(0);
+   bb->liveSet.marker = true;
+
+   if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) {
+      INFO("BB:%i live set of out blocks:\n", bb->getId());
+      bb->liveSet.print();
+   }
+
+   // if (!bb->getEntry())
+   //   return true;
+
+   if (bb == BasicBlock::get(f->cfgExit)) {
+      for (std::deque<ValueRef>::iterator it = f->outs.begin();
+           it != f->outs.end(); ++it) {
+         assert(it->get()->asLValue());
+         bb->liveSet.set(it->get()->id);
+      }
+   }
+
+   for (i = bb->getExit(); i && i != bb->getEntry()->prev; i = i->prev) {
+      for (d = 0; i->defExists(d); ++d)
+         bb->liveSet.clr(i->getDef(d)->id);
+      for (s = 0; i->srcExists(s); ++s)
+         if (i->getSrc(s)->asLValue())
+            bb->liveSet.set(i->getSrc(s)->id);
+   }
+   for (i = bb->getPhi(); i && i->op == OP_PHI; i = i->next)
+      bb->liveSet.clr(i->getDef(0)->id);
+
+   if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) {
+      INFO("BB:%i live set after propagation:\n", bb->getId());
+      bb->liveSet.print();
+   }
+
+   return true;
+}
+
+void
+RegAlloc::BuildIntervalsPass::collectLiveValues(BasicBlock *bb)
+{
+   BasicBlock *bbA = NULL, *bbB = NULL;
+
+   if (bb->cfg.outgoingCount()) {
+      // trickery to save a loop of OR'ing liveSets
+      // aliasing works fine with BitSet::setOr
+      for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
+         if (ei.getType() == Graph::Edge::DUMMY)
+            continue;
+         if (bbA) {
+            bb->liveSet.setOr(&bbA->liveSet, &bbB->liveSet);
+            bbA = bb;
+         } else {
+            bbA = bbB;
+         }
+         bbB = BasicBlock::get(ei.getNode());
+      }
+      bb->liveSet.setOr(&bbB->liveSet, bbA ? &bbA->liveSet : NULL);
+   } else
+   if (bb->cfg.incidentCount()) {
+      bb->liveSet.fill(0);
+   }
+}
+
+bool
+RegAlloc::BuildIntervalsPass::visit(BasicBlock *bb)
+{
+   collectLiveValues(bb);
+
+   INFO_DBG(prog->dbgFlags, REG_ALLOC, "BuildIntervals(BB:%i)\n", bb->getId());
+
+   // go through out blocks and delete phi sources that do not originate from
+   // the current block from the live set
+   for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
+      BasicBlock *out = BasicBlock::get(ei.getNode());
+
+      for (Instruction *i = out->getPhi(); i && i->op == OP_PHI; i = i->next) {
+         bb->liveSet.clr(i->getDef(0)->id);
+
+         for (int s = 0; i->srcExists(s); ++s) {
+            assert(i->src(s).getInsn());
+            if (i->getSrc(s)->getUniqueInsn()->bb == bb) // XXX: reachableBy ?
+               bb->liveSet.set(i->getSrc(s)->id);
+            else
+               bb->liveSet.clr(i->getSrc(s)->id);
+         }
+      }
+   }
+
+   // remaining live-outs are live until end
+   if (bb->getExit()) {
+      for (unsigned int j = 0; j < bb->liveSet.getSize(); ++j)
+         if (bb->liveSet.test(j))
+            addLiveRange(func->getLValue(j), bb, bb->getExit()->serial + 1);
+   }
+
+   for (Instruction *i = bb->getExit(); i && i->op != OP_PHI; i = i->prev) {
+      for (int d = 0; i->defExists(d); ++d) {
+         bb->liveSet.clr(i->getDef(d)->id);
+         if (i->getDef(d)->reg.data.id >= 0) // add hazard for fixed regs
+            i->getDef(d)->livei.extend(i->serial, i->serial);
+      }
+
+      for (int s = 0; i->srcExists(s); ++s) {
+         if (!i->getSrc(s)->asLValue())
+            continue;
+         if (!bb->liveSet.test(i->getSrc(s)->id)) {
+            bb->liveSet.set(i->getSrc(s)->id);
+            addLiveRange(i->getSrc(s), bb, i->serial);
+         }
+      }
+   }
+
+   if (bb == BasicBlock::get(func->cfg.getRoot())) {
+      for (std::deque<ValueDef>::iterator it = func->ins.begin();
+           it != func->ins.end(); ++it) {
+         if (it->get()->reg.data.id >= 0) // add hazard for fixed regs
+            it->get()->livei.extend(0, 1);
+      }
+   }
+
+   return true;
+}
+
+
+#define JOIN_MASK_PHI        (1 << 0)
+#define JOIN_MASK_UNION      (1 << 1)
+#define JOIN_MASK_MOV        (1 << 2)
+#define JOIN_MASK_TEX        (1 << 3)
+
+class GCRA
+{
+public:
+   GCRA(Function *, SpillCodeInserter&);
+   ~GCRA();
+
+   bool allocateRegisters(ArrayList& insns);
+
+   void printNodeInfo() const;
+
+private:
+   class RIG_Node : public Graph::Node
+   {
+   public:
+      RIG_Node();
+
+      void init(const RegisterSet&, LValue *);
+
+      void addInterference(RIG_Node *);
+      void addRegPreference(RIG_Node *);
+
+      inline LValue *getValue() const
+      {
+         return reinterpret_cast<LValue *>(data);
+      }
+      inline void setValue(LValue *lval) { data = lval; }
+
+      inline uint8_t getCompMask() const
+      {
+         return ((1 << colors) - 1) << (reg & 7);
+      }
+
+      static inline RIG_Node *get(const Graph::EdgeIterator& ei)
+      {
+         return static_cast<RIG_Node *>(ei.getNode());
+      }
+
+   public:
+      uint32_t degree;
+      uint16_t degreeLimit; // if deg < degLimit, node is trivially colourable
+      uint16_t colors;
+
+      DataFile f;
+      int32_t reg;
+
+      float weight;
+
+      // list pointers for simplify() phase
+      RIG_Node *next;
+      RIG_Node *prev;
+
+      // union of the live intervals of all coalesced values (we want to retain
+      //  the separate intervals for testing interference of compound values)
+      Interval livei;
+
+      std::list<RIG_Node *> prefRegs;
+   };
+
+private:
+   inline RIG_Node *getNode(const LValue *v) const { return &nodes[v->id]; }
+
+   void buildRIG(ArrayList&);
+   bool coalesce(ArrayList&);
+   bool doCoalesce(ArrayList&, unsigned int mask);
+   void calculateSpillWeights();
+   void simplify();
+   bool selectRegisters();
+   void cleanup(const bool success);
+
+   void simplifyEdge(RIG_Node *, RIG_Node *);
+   void simplifyNode(RIG_Node *);
+
+   bool coalesceValues(Value *, Value *, bool force);
+   void resolveSplitsAndMerges();
+   void makeCompound(Instruction *, bool isSplit);
+
+   inline void checkInterference(const RIG_Node *, Graph::EdgeIterator&);
+
+   inline void insertOrderedTail(std::list<RIG_Node *>&, RIG_Node *);
+   void checkList(std::list<RIG_Node *>&);
+
+private:
+   std::stack<uint32_t> stack;
+
+   // list headers for simplify() phase
+   RIG_Node lo[2];
+   RIG_Node hi;
+
+   Graph RIG;
+   RIG_Node *nodes;
+   unsigned int nodeCount;
+
+   Function *func;
+   Program *prog;
+
+   static uint8_t relDegree[17][17];
+
+   RegisterSet regs;
+
+   // need to fixup register id for participants of OP_MERGE/SPLIT
+   std::list<Instruction *> merges;
+   std::list<Instruction *> splits;
+
+   SpillCodeInserter& spill;
+   std::list<ValuePair> mustSpill;
+};
+
+uint8_t GCRA::relDegree[17][17];
+
+GCRA::RIG_Node::RIG_Node() : Node(NULL), next(this), prev(this)
+{
+   colors = 0;
+}
+
+void
+GCRA::printNodeInfo() const
+{
+   for (unsigned int i = 0; i < nodeCount; ++i) {
+      if (!nodes[i].colors)
+         continue;
+      INFO("RIG_Node[%%%i]($[%u]%i): %u colors, weight %f, deg %u/%u\n X",
+           i,
+           nodes[i].f,nodes[i].reg,nodes[i].colors,
+           nodes[i].weight,
+           nodes[i].degree, nodes[i].degreeLimit);
+
+      for (Graph::EdgeIterator ei = nodes[i].outgoing(); !ei.end(); ei.next())
+         INFO(" %%%i", RIG_Node::get(ei)->getValue()->id);
+      for (Graph::EdgeIterator ei = nodes[i].incident(); !ei.end(); ei.next())
+         INFO(" %%%i", RIG_Node::get(ei)->getValue()->id);
+      INFO("\n");
+   }
+}
+
+void
+GCRA::RIG_Node::init(const RegisterSet& regs, LValue *lval)
+{
+   setValue(lval);
+   if (lval->reg.data.id >= 0)
+      lval->noSpill = lval->fixedReg = 1;
+
+   colors = regs.units(lval->reg.file, lval->reg.size);
+   f = lval->reg.file;
+   reg = -1;
+   if (lval->reg.data.id >= 0)
+      reg = regs.idToUnits(lval);
+
+   weight = std::numeric_limits<float>::infinity();
+   degree = 0;
+   degreeLimit = regs.getFileSize(f, lval->reg.size);
+
+   livei.insert(lval->livei);
+}
+
+bool
+GCRA::coalesceValues(Value *dst, Value *src, bool force)
+{
+   LValue *rep = dst->join->asLValue();
+   LValue *val = src->join->asLValue();
+
+   if (!force && val->reg.data.id >= 0) {
+      rep = src->join->asLValue();
+      val = dst->join->asLValue();
+   }
+   RIG_Node *nRep = &nodes[rep->id];
+   RIG_Node *nVal = &nodes[val->id];
+
+   if (src->reg.file != dst->reg.file) {
+      if (!force)
+         return false;
+      WARN("forced coalescing of values in different files !\n");
+   }
+   if (!force && dst->reg.size != src->reg.size)
+      return false;
+
+   if ((rep->reg.data.id >= 0) && (rep->reg.data.id != val->reg.data.id)) {
+      if (force) {
+         if (val->reg.data.id >= 0)
+            WARN("forced coalescing of values in different fixed regs !\n");
+      } else {
+         if (val->reg.data.id >= 0)
+            return false;
+         // make sure that there is no overlap with the fixed register of rep
+         for (ArrayList::Iterator it = func->allLValues.iterator();
+              !it.end(); it.next()) {
+            Value *reg = reinterpret_cast<Value *>(it.get())->asLValue();
+            assert(reg);
+            if (reg->interfers(rep) && reg->livei.overlaps(nVal->livei))
+               return false;
+         }
+      }
+   }
+
+   if (!force && nRep->livei.overlaps(nVal->livei))
+      return false;
+
+   INFO_DBG(prog->dbgFlags, REG_ALLOC, "joining %%%i($%i) <- %%%i\n",
+            rep->id, rep->reg.data.id, val->id);
+
+   // set join pointer of all values joined with val
+   for (Value::DefIterator def = val->defs.begin(); def != val->defs.end();
+        ++def)
+      (*def)->get()->join = rep;
+   assert(rep->join == rep && val->join == rep);
+
+   // add val's definitions to rep and extend the live interval of its RIG node
+   rep->defs.insert(rep->defs.end(), val->defs.begin(), val->defs.end());
+   nRep->livei.unify(nVal->livei);
+   return true;
+}
+
+bool
+GCRA::coalesce(ArrayList& insns)
+{
+   bool ret = doCoalesce(insns, JOIN_MASK_PHI);
+   if (!ret)
+      return false;
+   switch (func->getProgram()->getTarget()->getChipset() & ~0xf) {
+   case 0x50:
+   case 0x80:
+   case 0x90:
+   case 0xa0:
+      ret = doCoalesce(insns, JOIN_MASK_UNION | JOIN_MASK_TEX);
+      break;
+   case 0xc0:
+   case 0xd0:
+   case 0xe0:
+      ret = doCoalesce(insns, JOIN_MASK_UNION);
+      break;
+   default:
+      break;
+   }
+   if (!ret)
+      return false;
+   return doCoalesce(insns, JOIN_MASK_MOV);
+}
+
+static inline uint8_t makeCompMask(int compSize, int base, int size)
+{
+   uint8_t m = ((1 << size) - 1) << base;
+
+   switch (compSize) {
+   case 1:
+      return 0xff;
+   case 2:
+      m |= (m << 2);
+      return (m << 4) | m;
+   case 3:
+   case 4:
+      return (m << 4) | m;
+   default:
+      assert(compSize <= 8);
+      return m;
+   }
+}
+
+// Used when coalescing moves. The non-compound value will become one, e.g.:
+// mov b32 $r0 $r2            / merge b64 $r0d { $r0 $r1 }
+// split b64 { $r0 $r1 } $r0d / mov b64 $r0d f64 $r2d
+static inline void copyCompound(Value *dst, Value *src)
+{
+   LValue *ldst = dst->asLValue();
+   LValue *lsrc = src->asLValue();
+
+   if (ldst->compound && !lsrc->compound) {
+      LValue *swap = lsrc;
+      lsrc = ldst;
+      ldst = swap;
+   }
+
+   ldst->compound = lsrc->compound;
+   ldst->compMask = lsrc->compMask;
+}
+
+void
+GCRA::makeCompound(Instruction *insn, bool split)
+{
+   LValue *rep = (split ? insn->getSrc(0) : insn->getDef(0))->asLValue();
+
+   if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC) {
+      INFO("makeCompound(split = %i): ", split);
+      insn->print();
+   }
+
+   const unsigned int size = getNode(rep)->colors;
+   unsigned int base = 0;
+
+   if (!rep->compound)
+      rep->compMask = 0xff;
+   rep->compound = 1;
+
+   for (int c = 0; split ? insn->defExists(c) : insn->srcExists(c); ++c) {
+      LValue *val = (split ? insn->getDef(c) : insn->getSrc(c))->asLValue();
+
+      val->compound = 1;
+      if (!val->compMask)
+         val->compMask = 0xff;
+      val->compMask &= makeCompMask(size, base, getNode(val)->colors);
+      assert(val->compMask);
+
+      INFO_DBG(prog->dbgFlags, REG_ALLOC, "compound: %%%i:%02x <- %%%i:%02x\n",
+           rep->id, rep->compMask, val->id, val->compMask);
+
+      base += getNode(val)->colors;
+   }
+   assert(base == size);
+}
+
+bool
+GCRA::doCoalesce(ArrayList& insns, unsigned int mask)
+{
+   int c, n;
+
+   for (n = 0; n < insns.getSize(); ++n) {
+      Instruction *i;
+      Instruction *insn = reinterpret_cast<Instruction *>(insns.get(n));
+
+      switch (insn->op) {
+      case OP_PHI:
+         if (!(mask & JOIN_MASK_PHI))
+            break;
+         for (c = 0; insn->srcExists(c); ++c)
+            if (!coalesceValues(insn->getDef(0), insn->getSrc(c), false)) {
+               // this is bad
+               ERROR("failed to coalesce phi operands\n");
+               return false;
+            }
+         break;
+      case OP_UNION:
+      case OP_MERGE:
+         if (!(mask & JOIN_MASK_UNION))
+            break;
+         for (c = 0; insn->srcExists(c); ++c)
+            coalesceValues(insn->getDef(0), insn->getSrc(c), true);
+         if (insn->op == OP_MERGE) {
+            merges.push_back(insn);
+            if (insn->srcExists(1))
+               makeCompound(insn, false);
+         }
+         break;
+      case OP_SPLIT:
+         if (!(mask & JOIN_MASK_UNION))
+            break;
+         splits.push_back(insn);
+         for (c = 0; insn->defExists(c); ++c)
+            coalesceValues(insn->getSrc(0), insn->getDef(c), true);
+         makeCompound(insn, true);
+         break;
+      case OP_MOV:
+         if (!(mask & JOIN_MASK_MOV))
+            break;
+         i = NULL;
+         if (!insn->getDef(0)->uses.empty())
+            i = insn->getDef(0)->uses.front()->getInsn();
+         // if this is a contraint-move there will only be a single use
+         if (i && i->op == OP_MERGE) // do we really still need this ?
+            break;
+         i = insn->getSrc(0)->getUniqueInsn();
+         if (i && !i->constrainedDefs()) {
+            if (coalesceValues(insn->getDef(0), insn->getSrc(0), false))
+               copyCompound(insn->getSrc(0), insn->getDef(0));
+         }
+         break;
+      case OP_TEX:
+      case OP_TXB:
+      case OP_TXL:
+      case OP_TXF:
+      case OP_TXQ:
+      case OP_TXD:
+      case OP_TXG:
+      case OP_TEXCSAA:
+         if (!(mask & JOIN_MASK_TEX))
+            break;
+         for (c = 0; insn->srcExists(c) && c != insn->predSrc; ++c)
+            coalesceValues(insn->getDef(c), insn->getSrc(c), true);
+         break;
+      default:
+         break;
+      }
+   }
+   return true;
+}
+
+void
+GCRA::RIG_Node::addInterference(RIG_Node *node)
+{
+   this->degree += relDegree[node->colors][colors];
+   node->degree += relDegree[colors][node->colors];
+
+   this->attach(node, Graph::Edge::CROSS);
+}
+
+void
+GCRA::RIG_Node::addRegPreference(RIG_Node *node)
+{
+   prefRegs.push_back(node);
+}
+
+GCRA::GCRA(Function *fn, SpillCodeInserter& spill) :
+   func(fn),
+   regs(fn->getProgram()->getTarget()),
+   spill(spill)
+{
+   prog = func->getProgram();
+
+   // initialize relative degrees array - i takes away from j
+   for (int i = 1; i <= 16; ++i)
+      for (int j = 1; j <= 16; ++j)
+         relDegree[i][j] = j * ((i + j - 1) / j);
+}
+
+GCRA::~GCRA()
+{
+   if (nodes)
+      delete[] nodes;
+}
+
+void
+GCRA::checkList(std::list<RIG_Node *>& lst)
+{
+   GCRA::RIG_Node *prev = NULL;
+
+   for (std::list<RIG_Node *>::iterator it = lst.begin();
+        it != lst.end();
+        ++it) {
+      assert((*it)->getValue()->join == (*it)->getValue());
+      if (prev)
+         assert(prev->livei.begin() <= (*it)->livei.begin());
+      prev = *it;
+   }
+}
+
+void
+GCRA::insertOrderedTail(std::list<RIG_Node *>& list, RIG_Node *node)
+{
+   if (node->livei.isEmpty())
+      return;
+   // only the intervals of joined values don't necessarily arrive in order
+   std::list<RIG_Node *>::iterator prev, it;
+   for (it = list.end(); it != list.begin(); it = prev) {
+      prev = it;
+      --prev;
+      if ((*prev)->livei.begin() <= node->livei.begin())
+         break;
+   }
+   list.insert(it, node);
+}
+
+void
+GCRA::buildRIG(ArrayList& insns)
+{
+   std::list<RIG_Node *> values, active;
+
+   for (std::deque<ValueDef>::iterator it = func->ins.begin();
+        it != func->ins.end(); ++it)
+      insertOrderedTail(values, getNode(it->get()->asLValue()));
+
+   for (int i = 0; i < insns.getSize(); ++i) {
+      Instruction *insn = reinterpret_cast<Instruction *>(insns.get(i));
+      for (int d = 0; insn->defExists(d); ++d)
+         if (insn->getDef(d)->rep() == insn->getDef(d))
+            insertOrderedTail(values, getNode(insn->getDef(d)->asLValue()));
+   }
+   checkList(values);
+
+   while (!values.empty()) {
+      RIG_Node *cur = values.front();
+
+      for (std::list<RIG_Node *>::iterator it = active.begin();
+           it != active.end();) {
+         RIG_Node *node = *it;
+
+         if (node->livei.end() <= cur->livei.begin()) {
+            it = active.erase(it);
+         } else {
+            if (node->f == cur->f && node->livei.overlaps(cur->livei))
+               cur->addInterference(node);
+            ++it;
+         }
+      }
+      values.pop_front();
+      active.push_back(cur);
+   }
+}
+
+void
+GCRA::calculateSpillWeights()
+{
+   for (unsigned int i = 0; i < nodeCount; ++i) {
+      RIG_Node *const n = &nodes[i];
+      if (!nodes[i].colors || nodes[i].livei.isEmpty())
+         continue;
+      if (nodes[i].reg >= 0) {
+         // update max reg
+         regs.occupy(n->f, n->reg, n->colors);
+         continue;
+      }
+      LValue *val = nodes[i].getValue();
+
+      if (!val->noSpill) {
+         int rc = 0;
+         for (Value::DefIterator it = val->defs.begin();
+              it != val->defs.end();
+              ++it)
+            rc += (*it)->get()->refCount();
+
+         nodes[i].weight =
+            (float)rc * (float)rc / (float)nodes[i].livei.extent();
+      }
+
+      if (nodes[i].degree < nodes[i].degreeLimit) {
+         int l = 0;
+         if (val->reg.size > 4)
+            l = 1;
+         DLLIST_ADDHEAD(&lo[l], &nodes[i]);
+      } else {
+         DLLIST_ADDHEAD(&hi, &nodes[i]);
+      }
+   }
+   if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
+      printNodeInfo();
+}
+
+void
+GCRA::simplifyEdge(RIG_Node *a, RIG_Node *b)
+{
+   bool move = b->degree >= b->degreeLimit;
+
+   INFO_DBG(prog->dbgFlags, REG_ALLOC,
+            "edge: (%%%i, deg %u/%u) >-< (%%%i, deg %u/%u)\n",
+            a->getValue()->id, a->degree, a->degreeLimit,
+            b->getValue()->id, b->degree, b->degreeLimit);
+
+   b->degree -= relDegree[a->colors][b->colors];
+
+   move = move && b->degree < b->degreeLimit;
+   if (move && !DLLIST_EMPTY(b)) {
+      int l = (b->getValue()->reg.size > 4) ? 1 : 0;
+      DLLIST_DEL(b);
+      DLLIST_ADDTAIL(&lo[l], b);
+   }
+}
+
+void
+GCRA::simplifyNode(RIG_Node *node)
+{
+   for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next())
+      simplifyEdge(node, RIG_Node::get(ei));
+
+   for (Graph::EdgeIterator ei = node->incident(); !ei.end(); ei.next())
+      simplifyEdge(node, RIG_Node::get(ei));
+
+   DLLIST_DEL(node);
+   stack.push(node->getValue()->id);
+
+   INFO_DBG(prog->dbgFlags, REG_ALLOC, "SIMPLIFY: pushed %%%i%s\n",
+            node->getValue()->id,
+            (node->degree < node->degreeLimit) ? "" : "(spill)");
+}
+
+void
+GCRA::simplify()
+{
+   for (;;) {
+      if (!DLLIST_EMPTY(&lo[0])) {
+         do {
+            simplifyNode(lo[0].next);
+         } while (!DLLIST_EMPTY(&lo[0]));
+      } else
+      if (!DLLIST_EMPTY(&lo[1])) {
+         simplifyNode(lo[1].next);
+      } else
+      if (!DLLIST_EMPTY(&hi)) {
+         RIG_Node *best = hi.next;
+         float bestScore = best->weight / (float)best->degree;
+         // spill candidate
+         for (RIG_Node *it = best->next; it != &hi; it = it->next) {
+            float score = it->weight / (float)it->degree;
+            if (score < bestScore) {
+               best = it;
+               bestScore = score;
+            }
+         }
+         if (isinf(bestScore)) {
+            ERROR("no viable spill candidates left\n");
+            break;
+         }
+         simplifyNode(best);
+      } else {
+         break;
+      }
+   }
+}
+
+void
+GCRA::checkInterference(const RIG_Node *node, Graph::EdgeIterator& ei)
+{
+   const RIG_Node *intf = RIG_Node::get(ei);
+
+   if (intf->reg < 0)
+      return;
+   const LValue *vA = node->getValue();
+   const LValue *vB = intf->getValue();
+
+   const uint8_t intfMask = ((1 << intf->colors) - 1) << (intf->reg & 7);
+
+   if (vA->compound | vB->compound) {
+      // NOTE: this only works for >aligned< register tuples !
+      for (Value::DefCIterator D = vA->defs.begin(); D != vA->defs.end(); ++D) {
+      for (Value::DefCIterator d = vB->defs.begin(); d != vB->defs.end(); ++d) {
+         const LValue *vD = (*D)->get()->asLValue();
+         const LValue *vd = (*d)->get()->asLValue();
+
+         if (!vD->livei.overlaps(vd->livei)) {
+            INFO_DBG(prog->dbgFlags, REG_ALLOC, "(%%%i) X (%%%i): no overlap\n",
+                     vD->id, vd->id);
+            continue;
+         }
+
+         uint8_t mask = vD->compound ? vD->compMask : ~0;
+         if (vd->compound) {
+            assert(vB->compound);
+            mask &= vd->compMask & vB->compMask;
+         } else {
+            mask &= intfMask;
+         }
+
+         INFO_DBG(prog->dbgFlags, REG_ALLOC,
+                  "(%%%i)%02x X (%%%i)%02x & %02x: $r%i.%02x\n",
+                  vD->id,
+                  vD->compound ? vD->compMask : 0xff,
+                  vd->id,
+                  vd->compound ? vd->compMask : intfMask,
+                  vB->compMask, intf->reg & ~7, mask);
+         if (mask)
+            regs.occupyMask(node->f, intf->reg & ~7, mask);
+      }
+      }
+   } else {
+      INFO_DBG(prog->dbgFlags, REG_ALLOC,
+               "(%%%i) X (%%%i): $r%i + %u\n",
+               vA->id, vB->id, intf->reg, intf->colors);
+      regs.occupy(node->f, intf->reg, intf->colors);
+   }
+}
+
+bool
+GCRA::selectRegisters()
+{
+   INFO_DBG(prog->dbgFlags, REG_ALLOC, "\nSELECT phase\n");
+
+   while (!stack.empty()) {
+      RIG_Node *node = &nodes[stack.top()];
+      stack.pop();
+
+      regs.reset(node->f);
+
+      INFO_DBG(prog->dbgFlags, REG_ALLOC, "\nNODE[%%%i, %u colors]\n",
+               node->getValue()->id, node->colors);
+
+      for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next())
+         checkInterference(node, ei);
+      for (Graph::EdgeIterator ei = node->incident(); !ei.end(); ei.next())
+         checkInterference(node, ei);
+
+      if (!node->prefRegs.empty()) {
+         for (std::list<RIG_Node *>::const_iterator it = node->prefRegs.begin();
+              it != node->prefRegs.end();
+              ++it) {
+            if ((*it)->reg >= 0 &&
+                regs.testOccupy(node->f, (*it)->reg, node->colors)) {
+               node->reg = (*it)->reg;
+               break;
+            }
+         }
+      }
+      if (node->reg >= 0)
+         continue;
+      LValue *lval = node->getValue();
+      if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
+         regs.print();
+      bool ret = regs.assign(node->reg, node->f, node->colors);
+      if (ret) {
+         INFO_DBG(prog->dbgFlags, REG_ALLOC, "assigned reg %i\n", node->reg);
+         lval->compMask = node->getCompMask();
+      } else {
+         INFO_DBG(prog->dbgFlags, REG_ALLOC, "must spill: %%%i (size %u)\n",
+                  lval->id, lval->reg.size);
+         Symbol *slot = NULL;
+         if (lval->reg.file == FILE_GPR)
+            slot = spill.assignSlot(node->livei, lval->reg.size);
+         mustSpill.push_back(ValuePair(lval, slot));
+      }
+   }
+   if (!mustSpill.empty())
+      return false;
+   for (unsigned int i = 0; i < nodeCount; ++i) {
+      LValue *lval = nodes[i].getValue();
+      if (nodes[i].reg >= 0 && nodes[i].colors > 0)
+         lval->reg.data.id =
+            regs.unitsToId(nodes[i].f, nodes[i].reg, lval->reg.size);
+   }
+   return true;
+}
+
+bool
+GCRA::allocateRegisters(ArrayList& insns)
+{
+   bool ret;
+
+   INFO_DBG(prog->dbgFlags, REG_ALLOC,
+            "allocateRegisters to %u instructions\n", insns.getSize());
+
+   nodeCount = func->allLValues.getSize();
+   nodes = new RIG_Node[nodeCount];
+   if (!nodes)
+      return false;
+   for (unsigned int i = 0; i < nodeCount; ++i) {
+      LValue *lval = reinterpret_cast<LValue *>(func->allLValues.get(i));
+      if (lval) {
+         nodes[i].init(regs, lval);
+         RIG.insert(&nodes[i]);
+      }
+   }
+
+   // coalesce first, we use only 1 RIG node for a group of joined values
+   ret = coalesce(insns);
+   if (!ret)
+      goto out;
+
+   if (func->getProgram()->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
+      func->printLiveIntervals();
+
+   buildRIG(insns);
+   calculateSpillWeights();
+   simplify();
+
+   ret = selectRegisters();
+   if (!ret) {
+      INFO_DBG(prog->dbgFlags, REG_ALLOC,
+               "selectRegisters failed, inserting spill code ...\n");
+      regs.reset(FILE_GPR, true);
+      spill.run(mustSpill);
+      if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
+         func->print();
+   } else {
+      prog->maxGPR = std::max(prog->maxGPR, regs.getMaxAssigned(FILE_GPR));
+   }
+
+out:
+   cleanup(ret);
+   return ret;
+}
+
+void
+GCRA::cleanup(const bool success)
+{
+   mustSpill.clear();
+
+   for (ArrayList::Iterator it = func->allLValues.iterator();
+        !it.end(); it.next()) {
+      LValue *lval =  reinterpret_cast<LValue *>(it.get());
+
+      lval->livei.clear();
+
+      lval->compound = 0;
+      lval->compMask = 0;
+
+      if (lval->join == lval)
+         continue;
+
+      if (success) {
+         lval->reg.data.id = lval->join->reg.data.id;
+      } else {
+         for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end();
+              ++d)
+            lval->join->defs.remove(*d);
+         lval->join = lval;
+      }
+   }
+
+   if (success)
+      resolveSplitsAndMerges();
+   splits.clear(); // avoid duplicate entries on next coalesce pass
+   merges.clear();
+
+   delete[] nodes;
+   nodes = NULL;
+}
+
+Symbol *
+SpillCodeInserter::assignSlot(const Interval &livei, const unsigned int size)
+{
+   SpillSlot slot;
+   int32_t offsetBase = stackSize;
+   int32_t offset;
+   std::list<SpillSlot>::iterator pos = slots.end(), it = slots.begin();
+
+   if (offsetBase % size)
+      offsetBase += size - (offsetBase % size);
+
+   slot.sym = NULL;
+
+   for (offset = offsetBase; offset < stackSize; offset += size) {
+      const int32_t entryEnd = offset + size;
+      while (it != slots.end() && it->offset < offset)
+         ++it;
+      if (it == slots.end()) // no slots left
+         break;
+      std::list<SpillSlot>::iterator bgn = it;
+
+      while (it != slots.end() && it->offset < entryEnd) {
+         it->occup.print();
+         if (it->occup.overlaps(livei))
+            break;
+         ++it;
+      }
+      if (it == slots.end() || it->offset >= entryEnd) {
+         // fits
+         for (; bgn != slots.end() && bgn->offset < entryEnd; ++bgn) {
+            bgn->occup.insert(livei);
+            if (bgn->size() == size)
+               slot.sym = bgn->sym;
+         }
+         break;
+      }
+   }
+   if (!slot.sym) {
+      stackSize = offset + size;
+      slot.offset = offset;
+      slot.sym = new_Symbol(func->getProgram(), FILE_MEMORY_LOCAL);
+      if (!func->stackPtr)
+         offset += func->tlsBase;
+      slot.sym->setAddress(NULL, offset);
+      slot.sym->reg.size = size;
+      slots.insert(pos, slot)->occup.insert(livei);
+   }
+   return slot.sym;
+}
+
+void
+SpillCodeInserter::spill(Instruction *defi, Value *slot, LValue *lval)
+{
+   const DataType ty = typeOfSize(slot->reg.size);
+
+   Instruction *st;
+   if (slot->reg.file == FILE_MEMORY_LOCAL) {
+      st = new_Instruction(func, OP_STORE, ty);
+      st->setSrc(0, slot);
+      st->setSrc(1, lval);
+      lval->noSpill = 1;
+   } else {
+      st = new_Instruction(func, OP_CVT, ty);
+      st->setDef(0, slot);
+      st->setSrc(0, lval);
+   }
+   defi->bb->insertAfter(defi, st);
+}
+
+LValue *
+SpillCodeInserter::unspill(Instruction *usei, LValue *lval, Value *slot)
+{
+   const DataType ty = typeOfSize(slot->reg.size);
+
+   lval = cloneShallow(func, lval);
+
+   Instruction *ld;
+   if (slot->reg.file == FILE_MEMORY_LOCAL) {
+      lval->noSpill = 1;
+      ld = new_Instruction(func, OP_LOAD, ty);
+   } else {
+      ld = new_Instruction(func, OP_CVT, ty);
+   }
+   ld->setDef(0, lval);
+   ld->setSrc(0, slot);
+
+   usei->bb->insertBefore(usei, ld);
+   return lval;
+}
+
+bool
+SpillCodeInserter::run(const std::list<ValuePair>& lst)
+{
+   for (std::list<ValuePair>::const_iterator it = lst.begin(); it != lst.end();
+        ++it) {
+      LValue *lval = it->first->asLValue();
+      Symbol *mem = it->second ? it->second->asSym() : NULL;
+
+      for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end();
+           ++d) {
+         Value *slot = mem ?
+            static_cast<Value *>(mem) : new_LValue(func, FILE_GPR);
+         Value *tmp = NULL;
+         Instruction *last = NULL;
+
+         LValue *dval = (*d)->get()->asLValue();
+         Instruction *defi = (*d)->getInsn();
+
+         // handle uses first or they'll contain the spill stores
+         while (!dval->uses.empty()) {
+            ValueRef *u = dval->uses.front();
+            Instruction *usei = u->getInsn();
+            assert(usei);
+            if (usei->op == OP_PHI) {
+               tmp = (slot->reg.file == FILE_MEMORY_LOCAL) ? NULL : slot;
+               last = NULL;
+            } else
+            if (!last || usei != last->next) { // TODO: sort uses
+               tmp = unspill(usei, dval, slot);
+               last = usei;
+            }
+            u->set(tmp);
+         }
+
+         assert(defi);
+         if (defi->op == OP_PHI) {
+            d = lval->defs.erase(d);
+            --d;
+            if (slot->reg.file == FILE_MEMORY_LOCAL)
+               delete_Instruction(func->getProgram(), defi);
+            else
+               defi->setDef(0, slot);
+         } else {
+            spill(defi, slot, dval);
+         }
+      }
+
+   }
+
+   // TODO: We're not trying to reuse old slots in a potential next iteration.
+   //  We have to update the slots' livei intervals to be able to do that.
+   stackBase = stackSize;
+   slots.clear();
+   return true;
+}
+
+bool
+RegAlloc::exec()
+{
+   for (IteratorRef it = prog->calls.iteratorDFS(false);
+        !it->end(); it->next()) {
+      func = Function::get(reinterpret_cast<Graph::Node *>(it->get()));
+
+      func->tlsBase = prog->tlsSize;
+      if (!execFunc())
+         return false;
+      prog->tlsSize += func->tlsSize;
+   }
+   return true;
+}
+
+bool
+RegAlloc::execFunc()
+{
+   InsertConstraintsPass insertConstr;
+   PhiMovesPass insertPhiMoves;
+   ArgumentMovesPass insertArgMoves;
+   BuildIntervalsPass buildIntervals;
+   SpillCodeInserter insertSpills(func);
+
+   GCRA gcra(func, insertSpills);
+
+   unsigned int i, retries;
+   bool ret;
+
+   if (!func->ins.empty()) {
+      // Insert a nop at the entry so inputs only used by the first instruction
+      // don't count as having an empty live range.
+      Instruction *nop = new_Instruction(func, OP_NOP, TYPE_NONE);
+      BasicBlock::get(func->cfg.getRoot())->insertHead(nop);
+   }
+
+   ret = insertConstr.exec(func);
+   if (!ret)
+      goto out;
+
+   ret = insertPhiMoves.run(func);
+   if (!ret)
+      goto out;
+
+   ret = insertArgMoves.run(func);
+   if (!ret)
+      goto out;
+
+   // TODO: need to fix up spill slot usage ranges to support > 1 retry
+   for (retries = 0; retries < 3; ++retries) {
+      if (retries && (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC))
+         INFO("Retry: %i\n", retries);
+      if (prog->dbgFlags & NV50_IR_DEBUG_REG_ALLOC)
+         func->print();
+
+      // spilling to registers may add live ranges, need to rebuild everything
+      ret = true;
+      for (sequence = func->cfg.nextSequence(), i = 0;
+           ret && i <= func->loopNestingBound;
+           sequence = func->cfg.nextSequence(), ++i)
+         ret = buildLiveSets(BasicBlock::get(func->cfg.getRoot()));
+      if (!ret)
+         break;
+      func->orderInstructions(this->insns);
+
+      ret = buildIntervals.run(func);
+      if (!ret)
+         break;
+      ret = gcra.allocateRegisters(insns);
+      if (ret)
+         break; // success
+   }
+   INFO_DBG(prog->dbgFlags, REG_ALLOC, "RegAlloc done: %i\n", ret);
+
+   func->tlsSize = insertSpills.getStackSize();
+out:
+   return ret;
+}
+
+// TODO: check if modifying Instruction::join here breaks anything
+void
+GCRA::resolveSplitsAndMerges()
+{
+   for (std::list<Instruction *>::iterator it = splits.begin();
+        it != splits.end();
+        ++it) {
+      Instruction *split = *it;
+      unsigned int reg = regs.idToBytes(split->getSrc(0));
+      for (int d = 0; split->defExists(d); ++d) {
+         Value *v = split->getDef(d);
+         v->reg.data.id = regs.bytesToId(v, reg);
+         v->join = v;
+         reg += v->reg.size;
+      }
+   }
+   splits.clear();
+
+   for (std::list<Instruction *>::iterator it = merges.begin();
+        it != merges.end();
+        ++it) {
+      Instruction *merge = *it;
+      unsigned int reg = regs.idToBytes(merge->getDef(0));
+      for (int s = 0; merge->srcExists(s); ++s) {
+         Value *v = merge->getSrc(s);
+         v->reg.data.id = regs.bytesToId(v, reg);
+         v->join = v;
+         reg += v->reg.size;
+      }
+   }
+   merges.clear();
+}
+
+bool Program::registerAllocation()
+{
+   RegAlloc ra(this);
+   return ra.exec();
+}
+
+bool
+RegAlloc::InsertConstraintsPass::exec(Function *ir)
+{
+   constrList.clear();
+
+   bool ret = run(ir, true, true);
+   if (ret)
+      ret = insertConstraintMoves();
+   return ret;
+}
+
+// TODO: make part of texture insn
+void
+RegAlloc::InsertConstraintsPass::textureMask(TexInstruction *tex)
+{
+   Value *def[4];
+   int c, k, d;
+   uint8_t mask = 0;
+
+   for (d = 0, k = 0, c = 0; c < 4; ++c) {
+      if (!(tex->tex.mask & (1 << c)))
+         continue;
+      if (tex->getDef(k)->refCount()) {
+         mask |= 1 << c;
+         def[d++] = tex->getDef(k);
+      }
+      ++k;
+   }
+   tex->tex.mask = mask;
+
+   for (c = 0; c < d; ++c)
+      tex->setDef(c, def[c]);
+   for (; c < 4; ++c)
+      tex->setDef(c, NULL);
+}
+
+bool
+RegAlloc::InsertConstraintsPass::detectConflict(Instruction *cst, int s)
+{
+   Value *v = cst->getSrc(s);
+
+   // current register allocation can't handle it if a value participates in
+   // multiple constraints
+   for (Value::UseIterator it = v->uses.begin(); it != v->uses.end(); ++it) {
+      if (cst != (*it)->getInsn())
+         return true;
+   }
+
+   // can start at s + 1 because detectConflict is called on all sources
+   for (int c = s + 1; cst->srcExists(c); ++c)
+      if (v == cst->getSrc(c))
+         return true;
+
+   Instruction *defi = v->getInsn();
+
+   return (!defi || defi->constrainedDefs());
+}
+
+void
+RegAlloc::InsertConstraintsPass::addConstraint(Instruction *i, int s, int n)
+{
+   Instruction *cst;
+   int d;
+
+   // first, look for an existing identical constraint op
+   for (std::list<Instruction *>::iterator it = constrList.begin();
+        it != constrList.end();
+        ++it) {
+      cst = (*it);
+      if (!i->bb->dominatedBy(cst->bb))
+         break;
+      for (d = 0; d < n; ++d)
+         if (cst->getSrc(d) != i->getSrc(d + s))
+            break;
+      if (d >= n) {
+         for (d = 0; d < n; ++d, ++s)
+            i->setSrc(s, cst->getDef(d));
+         return;
+      }
+   }
+   cst = new_Instruction(func, OP_CONSTRAINT, i->dType);
+
+   for (d = 0; d < n; ++s, ++d) {
+      cst->setDef(d, new_LValue(func, FILE_GPR));
+      cst->setSrc(d, i->getSrc(s));
+      i->setSrc(s, cst->getDef(d));
+   }
+   i->bb->insertBefore(i, cst);
+
+   constrList.push_back(cst);
+}
+
+// Add a dummy use of the pointer source of >= 8 byte loads after the load
+// to prevent it from being assigned a register which overlapping the load's
+// destination, which would produce random corruptions.
+void
+RegAlloc::InsertConstraintsPass::addHazard(Instruction *i, const ValueRef *src)
+{
+   Instruction *hzd = new_Instruction(func, OP_NOP, TYPE_NONE);
+   hzd->setSrc(0, src->get());
+   i->bb->insertAfter(i, hzd);
+
+}
+
+// b32 { %r0 %r1 %r2 %r3 } -> b128 %r0q
+void
+RegAlloc::InsertConstraintsPass::condenseDefs(Instruction *insn)
+{
+   uint8_t size = 0;
+   int n;
+   for (n = 0; insn->defExists(n) && insn->def(n).getFile() == FILE_GPR; ++n)
+      size += insn->getDef(n)->reg.size;
+   if (n < 2)
+      return;
+   LValue *lval = new_LValue(func, FILE_GPR);
+   lval->reg.size = size;
+
+   Instruction *split = new_Instruction(func, OP_SPLIT, typeOfSize(size));
+   split->setSrc(0, lval);
+   for (int d = 0; d < n; ++d) {
+      split->setDef(d, insn->getDef(d));
+      insn->setDef(d, NULL);
+   }
+   insn->setDef(0, lval);
+
+   for (int k = 1, d = n; insn->defExists(d); ++d, ++k) {
+      insn->setDef(k, insn->getDef(d));
+      insn->setDef(d, NULL);
+   }
+   // carry over predicate if any (mainly for OP_UNION uses)
+   split->setPredicate(insn->cc, insn->getPredicate());
+
+   insn->bb->insertAfter(insn, split);
+   constrList.push_back(split);
+}
+void
+RegAlloc::InsertConstraintsPass::condenseSrcs(Instruction *insn,
+                                              const int a, const int b)
+{
+   uint8_t size = 0;
+   if (a >= b)
+      return;
+   for (int s = a; s <= b; ++s)
+      size += insn->getSrc(s)->reg.size;
+   if (!size)
+      return;
+   LValue *lval = new_LValue(func, FILE_GPR);
+   lval->reg.size = size;
+
+   Value *save[3];
+   insn->takeExtraSources(0, save);
+
+   Instruction *merge = new_Instruction(func, OP_MERGE, typeOfSize(size));
+   merge->setDef(0, lval);
+   for (int s = a, i = 0; s <= b; ++s, ++i) {
+      merge->setSrc(i, insn->getSrc(s));
+      insn->setSrc(s, NULL);
+   }
+   insn->setSrc(a, lval);
+
+   for (int k = a + 1, s = b + 1; insn->srcExists(s); ++s, ++k) {
+      insn->setSrc(k, insn->getSrc(s));
+      insn->setSrc(s, NULL);
+   }
+   insn->bb->insertBefore(insn, merge);
+
+   insn->putExtraSources(0, save);
+
+   constrList.push_back(merge);
+}
+
+void
+RegAlloc::InsertConstraintsPass::texConstraintNVE0(TexInstruction *tex)
+{
+   if (isTextureOp(tex->op))
+      textureMask(tex);
+   condenseDefs(tex);
+
+   if (tex->op == OP_SUSTB || tex->op == OP_SUSTP) {
+      condenseSrcs(tex, 3, (3 + typeSizeof(tex->dType) / 4) - 1);
+   } else
+   if (isTextureOp(tex->op)) {
+      int n = tex->srcCount(0xff, true);
+      if (n > 4) {
+         condenseSrcs(tex, 0, 3);
+         if (n > 5) // NOTE: first call modified positions already
+            condenseSrcs(tex, 4 - (4 - 1), n - 1 - (4 - 1));
+      } else
+      if (n > 1) {
+         condenseSrcs(tex, 0, n - 1);
+      }
+   }
+}
+
+void
+RegAlloc::InsertConstraintsPass::texConstraintNVC0(TexInstruction *tex)
+{
+   int n, s;
+
+   textureMask(tex);
+
+   if (tex->op == OP_TXQ) {
+      s = tex->srcCount(0xff);
+      n = 0;
+   } else {
+      s = tex->tex.target.getArgCount();
+      if (!tex->tex.target.isArray() &&
+          (tex->tex.rIndirectSrc >= 0 || tex->tex.sIndirectSrc >= 0))
+         ++s;
+      if (tex->op == OP_TXD && tex->tex.useOffsets)
+         ++s;
+      n = tex->srcCount(0xff) - s;
+      assert(n <= 4);
+   }
+
+   if (s > 1)
+      condenseSrcs(tex, 0, s - 1);
+   if (n > 1) // NOTE: first call modified positions already
+      condenseSrcs(tex, 1, n);
+
+   condenseDefs(tex);
+}
+
+void
+RegAlloc::InsertConstraintsPass::texConstraintNV50(TexInstruction *tex)
+{
+   Value *pred = tex->getPredicate();
+   if (pred)
+      tex->setPredicate(tex->cc, NULL);
+
+   textureMask(tex);
+
+   assert(tex->defExists(0) && tex->srcExists(0));
+   // make src and def count match
+   int c;
+   for (c = 0; tex->srcExists(c) || tex->defExists(c); ++c) {
+      if (!tex->srcExists(c))
+         tex->setSrc(c, new_LValue(func, tex->getSrc(0)->asLValue()));
+      if (!tex->defExists(c))
+         tex->setDef(c, new_LValue(func, tex->getDef(0)->asLValue()));
+   }
+   if (pred)
+      tex->setPredicate(tex->cc, pred);
+   condenseDefs(tex);
+   condenseSrcs(tex, 0, c - 1);
+}
+
+// Insert constraint markers for instructions whose multiple sources must be
+// located in consecutive registers.
+bool
+RegAlloc::InsertConstraintsPass::visit(BasicBlock *bb)
+{
+   TexInstruction *tex;
+   Instruction *next;
+   int s, size;
+
+   targ = bb->getProgram()->getTarget();
+
+   for (Instruction *i = bb->getEntry(); i; i = next) {
+      next = i->next;
+
+      if ((tex = i->asTex())) {
+         switch (targ->getChipset() & ~0xf) {
+         case 0x50:
+         case 0x80:
+         case 0x90:
+         case 0xa0:
+            texConstraintNV50(tex);
+            break;
+         case 0xc0:
+         case 0xd0:
+            texConstraintNVC0(tex);
+            break;
+         case 0xe0:
+         case NVISA_GK110_CHIPSET:
+            texConstraintNVE0(tex);
+            break;
+         default:
+            break;
+         }
+      } else
+      if (i->op == OP_EXPORT || i->op == OP_STORE) {
+         for (size = typeSizeof(i->dType), s = 1; size > 0; ++s) {
+            assert(i->srcExists(s));
+            size -= i->getSrc(s)->reg.size;
+         }
+         condenseSrcs(i, 1, s - 1);
+      } else
+      if (i->op == OP_LOAD || i->op == OP_VFETCH) {
+         condenseDefs(i);
+         if (i->src(0).isIndirect(0) && typeSizeof(i->dType) >= 8)
+            addHazard(i, i->src(0).getIndirect(0));
+      } else
+      if (i->op == OP_UNION ||
+          i->op == OP_MERGE ||
+          i->op == OP_SPLIT) {
+         constrList.push_back(i);
+      }
+   }
+   return true;
+}
+
+// Insert extra moves so that, if multiple register constraints on a value are
+// in conflict, these conflicts can be resolved.
+bool
+RegAlloc::InsertConstraintsPass::insertConstraintMoves()
+{
+   for (std::list<Instruction *>::iterator it = constrList.begin();
+        it != constrList.end();
+        ++it) {
+      Instruction *cst = *it;
+      Instruction *mov;
+
+      if (cst->op == OP_SPLIT && 0) {
+         // spilling splits is annoying, just make sure they're separate
+         for (int d = 0; cst->defExists(d); ++d) {
+            if (!cst->getDef(d)->refCount())
+               continue;
+            LValue *lval = new_LValue(func, cst->def(d).getFile());
+            const uint8_t size = cst->def(d).getSize();
+            lval->reg.size = size;
+
+            mov = new_Instruction(func, OP_MOV, typeOfSize(size));
+            mov->setSrc(0, lval);
+            mov->setDef(0, cst->getDef(d));
+            cst->setDef(d, mov->getSrc(0));
+            cst->bb->insertAfter(cst, mov);
+
+            cst->getSrc(0)->asLValue()->noSpill = 1;
+            mov->getSrc(0)->asLValue()->noSpill = 1;
+         }
+      } else
+      if (cst->op == OP_MERGE || cst->op == OP_UNION) {
+         for (int s = 0; cst->srcExists(s); ++s) {
+            const uint8_t size = cst->src(s).getSize();
+
+            if (!cst->getSrc(s)->defs.size()) {
+               mov = new_Instruction(func, OP_NOP, typeOfSize(size));
+               mov->setDef(0, cst->getSrc(s));
+               cst->bb->insertBefore(cst, mov);
+               continue;
+            }
+            assert(cst->getSrc(s)->defs.size() == 1); // still SSA
+
+            Instruction *defi = cst->getSrc(s)->defs.front()->getInsn();
+            // catch some cases where don't really need MOVs
+            if (cst->getSrc(s)->refCount() == 1 && !defi->constrainedDefs())
+               continue;
+
+            LValue *lval = new_LValue(func, cst->src(s).getFile());
+            lval->reg.size = size;
+
+            mov = new_Instruction(func, OP_MOV, typeOfSize(size));
+            mov->setDef(0, lval);
+            mov->setSrc(0, cst->getSrc(s));
+            cst->setSrc(s, mov->getDef(0));
+            cst->bb->insertBefore(cst, mov);
+
+            cst->getDef(0)->asLValue()->noSpill = 1; // doesn't help
+
+            if (cst->op == OP_UNION)
+               mov->setPredicate(defi->cc, defi->getPredicate());
+         }
+      }
+   }
+
+   return true;
+}
+
+} // namespace nv50_ir