nv50_ir_bb.cpp

/*
 * 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 "nv50_ir.h"

namespace nv50_ir {

Function::Function(Program *p, const char *fnName, uint32_t label)
   : call(this),
     label(label),
     name(fnName),
     prog(p)
{
   cfgExit = NULL;
   domTree = NULL;

   bbArray = NULL;
   bbCount = 0;
   loopNestingBound = 0;
   regClobberMax = 0;

   binPos = 0;
   binSize = 0;

   stackPtr = NULL;
   tlsBase = 0;
   tlsSize = 0;

   prog->add(this, id);
}

Function::~Function()
{
   prog->del(this, id);

   if (domTree)
      delete domTree;
   if (bbArray)
      delete[] bbArray;

   // clear value refs and defs
   ins.clear();
   outs.clear();

   for (ArrayList::Iterator it = allInsns.iterator(); !it.end(); it.next())
      delete_Instruction(prog, reinterpret_cast<Instruction *>(it.get()));

   for (ArrayList::Iterator it = allLValues.iterator(); !it.end(); it.next())
      delete_Value(prog, reinterpret_cast<LValue *>(it.get()));

   for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next())
      delete reinterpret_cast<BasicBlock *>(BBs.get());
}

BasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn)
{
   program = func->getProgram();

   joinAt = phi = entry = exit = NULL;

   numInsns = 0;
   binPos = 0;
   binSize = 0;

   explicitCont = false;

   func->add(this, this->id);
}

BasicBlock::~BasicBlock()
{
   // nothing yet
}

BasicBlock *
BasicBlock::clone(ClonePolicy<Function>& pol) const
{
   BasicBlock *bb = new BasicBlock(pol.context());

   pol.set(this, bb);

   for (Instruction *i = getFirst(); i; i = i->next)
      bb->insertTail(i->clone(pol));

   pol.context()->cfg.insert(&bb->cfg);

   for (Graph::EdgeIterator it = cfg.outgoing(); !it.end(); it.next()) {
      BasicBlock *obb = BasicBlock::get(it.getNode());
      bb->cfg.attach(&pol.get(obb)->cfg, it.getType());
   }

   return bb;
}

BasicBlock *
BasicBlock::idom() const
{
   Graph::Node *dn = dom.parent();
   return dn ? BasicBlock::get(dn) : NULL;
}

void
BasicBlock::insertHead(Instruction *inst)
{
   assert(inst->next == 0 && inst->prev == 0);

   if (inst->op == OP_PHI) {
      if (phi) {
         insertBefore(phi, inst);
      } else {
         if (entry) {
            insertBefore(entry, inst);
         } else {
            assert(!exit);
            phi = exit = inst;
            inst->bb = this;
            ++numInsns;
         }
      }
   } else {
      if (entry) {
         insertBefore(entry, inst);
      } else {
         if (phi) {
            insertAfter(exit, inst); // after last phi
         } else {
            assert(!exit);
            entry = exit = inst;
            inst->bb = this;
            ++numInsns;
         }
      }
   }
}

void
BasicBlock::insertTail(Instruction *inst)
{
   assert(inst->next == 0 && inst->prev == 0);

   if (inst->op == OP_PHI) {
      if (entry) {
         insertBefore(entry, inst);
      } else
      if (exit) {
         assert(phi);
         insertAfter(exit, inst);
      } else {
         assert(!phi);
         phi = exit = inst;
         inst->bb = this;
         ++numInsns;
      }
   } else {
      if (exit) {
         insertAfter(exit, inst);
      } else {
         assert(!phi);
         entry = exit = inst;
         inst->bb = this;
         ++numInsns;
      }
   }
}

void
BasicBlock::insertBefore(Instruction *q, Instruction *p)
{
   assert(p && q);

   assert(p->next == 0 && p->prev == 0);

   if (q == entry) {
      if (p->op == OP_PHI) {
         if (!phi)
            phi = p;
      } else {
         entry = p;
      }
   } else
   if (q == phi) {
      assert(p->op == OP_PHI);
      phi = p;
   }

   p->next = q;
   p->prev = q->prev;
   if (p->prev)
      p->prev->next = p;
   q->prev = p;

   p->bb = this;
   ++numInsns;
}

void
BasicBlock::insertAfter(Instruction *p, Instruction *q)
{
   assert(p && q);
   assert(q->op != OP_PHI || p->op == OP_PHI);

   assert(q->next == 0 && q->prev == 0);

   if (p == exit)
      exit = q;
   if (p->op == OP_PHI && q->op != OP_PHI)
      entry = q;

   q->prev = p;
   q->next = p->next;
   if (q->next)
      q->next->prev = q;
   p->next = q;

   q->bb = this;
   ++numInsns;
}

void
BasicBlock::remove(Instruction *insn)
{
   assert(insn->bb == this);

   if (insn->prev)
      insn->prev->next = insn->next;

   if (insn->next)
      insn->next->prev = insn->prev;
   else
      exit = insn->prev;

   if (insn == entry) {
      if (insn->next)
         entry = insn->next;
      else
      if (insn->prev && insn->prev->op != OP_PHI)
         entry = insn->prev;
      else
         entry = NULL;
   }

   if (insn == phi)
      phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0;

   --numInsns;
   insn->bb = NULL;
   insn->next =
   insn->prev = NULL;
}

void BasicBlock::permuteAdjacent(Instruction *a, Instruction *b)
{
   assert(a->bb == b->bb);

   if (a->next != b) {
      Instruction *i = a;
      a = b;
      b = i;
   }
   assert(a->next == b);
   assert(a->op != OP_PHI && b->op != OP_PHI);

   if (b == exit)
      exit = a;
   if (a == entry)
      entry = b;

   b->prev = a->prev;
   a->next = b->next;
   b->next = a;
   a->prev = b;

   if (b->prev)
      b->prev->next = b;
   if (a->next)
      a->next->prev = a;
}

void
BasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach)
{
   bb->entry = insn;

   if (insn) {
      exit = insn->prev;
      insn->prev = NULL;
   }

   if (exit)
      exit->next = NULL;
   else
      entry = NULL;

   while (!cfg.outgoing(true).end()) {
      Graph::Edge *e = cfg.outgoing(true).getEdge();
      bb->cfg.attach(e->getTarget(), e->getType());
      this->cfg.detach(e->getTarget());
   }

   for (; insn; insn = insn->next) {
      this->numInsns--;
      bb->numInsns++;
      insn->bb = bb;
      bb->exit = insn;
   }
   if (attach)
      this->cfg.attach(&bb->cfg, Graph::Edge::TREE);
}

BasicBlock *
BasicBlock::splitBefore(Instruction *insn, bool attach)
{
   BasicBlock *bb = new BasicBlock(func);
   assert(!insn || insn->op != OP_PHI);

   bb->joinAt = joinAt;
   joinAt = NULL;

   splitCommon(insn, bb, attach);
   return bb;
}

BasicBlock *
BasicBlock::splitAfter(Instruction *insn, bool attach)
{
   BasicBlock *bb = new BasicBlock(func);
   assert(!insn || insn->op != OP_PHI);

   bb->joinAt = joinAt;
   joinAt = NULL;

   splitCommon(insn ? insn->next : NULL, bb, attach);
   return bb;
}

bool
BasicBlock::dominatedBy(BasicBlock *that)
{
   Graph::Node *bn = &that->dom;
   Graph::Node *dn = &this->dom;

   while (dn && dn != bn)
      dn = dn->parent();

   return dn != NULL;
}

unsigned int
BasicBlock::initiatesSimpleConditional() const
{
   Graph::Node *out[2];
   int n;
   Graph::Edge::Type eR;

   if (cfg.outgoingCount() != 2) // -> if and -> else/endif
      return false;

   n = 0;
   for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next())
      out[n++] = ei.getNode();
   eR = out[1]->outgoing().getType();

   // IF block is out edge to the right
   if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK)
      return 0x2;

   if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence
      return 0x0;
   // do they reconverge immediately ?
   if (out[1]->outgoing().getNode() == out[0])
      return 0x1;
   if (out[0]->outgoingCount() == 1)
      if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode())
         return 0x3;

   return 0x0;
}

bool
Function::setEntry(BasicBlock *bb)
{
   if (cfg.getRoot())
      return false;
   cfg.insert(&bb->cfg);
   return true;
}

bool
Function::setExit(BasicBlock *bb)
{
   if (cfgExit)
      return false;
   cfgExit = &bb->cfg;
   return true;
}

unsigned int
Function::orderInstructions(ArrayList &result)
{
   result.clear();

   for (IteratorRef it = cfg.iteratorCFG(); !it->end(); it->next()) {
      BasicBlock *bb =
         BasicBlock::get(reinterpret_cast<Graph::Node *>(it->get()));

      for (Instruction *insn = bb->getFirst(); insn; insn = insn->next)
         result.insert(insn, insn->serial);
   }

   return result.getSize();
}

void
Function::buildLiveSets()
{
   for (unsigned i = 0; i <= loopNestingBound; ++i)
      buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), cfg.nextSequence());

   for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
      BasicBlock::get(bi)->liveSet.marker = false;
}

void
Function::buildDefSets()
{
   for (unsigned i = 0; i <= loopNestingBound; ++i)
      buildDefSetsPreSSA(BasicBlock::get(cfgExit), cfg.nextSequence());

   for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
      BasicBlock::get(bi)->liveSet.marker = false;
}

bool
Pass::run(Program *prog, bool ordered, bool skipPhi)
{
   this->prog = prog;
   err = false;
   return doRun(prog, ordered, skipPhi);
}

bool
Pass::doRun(Program *prog, bool ordered, bool skipPhi)
{
   for (IteratorRef it = prog->calls.iteratorDFS(false);
        !it->end(); it->next()) {
      Graph::Node *n = reinterpret_cast<Graph::Node *>(it->get());
      if (!doRun(Function::get(n), ordered, skipPhi))
         return false;
   }
   return !err;
}

bool
Pass::run(Function *func, bool ordered, bool skipPhi)
{
   prog = func->getProgram();
   err = false;
   return doRun(func, ordered, skipPhi);
}

bool
Pass::doRun(Function *func, bool ordered, bool skipPhi)
{
   IteratorRef bbIter;
   BasicBlock *bb;
   Instruction *insn, *next;

   this->func = func;
   if (!visit(func))
      return false;

   bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS();

   for (; !bbIter->end(); bbIter->next()) {
      bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get()));
      if (!visit(bb))
         break;
      for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL;
           insn = next) {
         next = insn->next;
         if (!visit(insn))
            break;
      }
   }

   return !err;
}

void
Function::printCFGraph(const char *filePath)
{
   FILE *out = fopen(filePath, "a");
   if (!out) {
      ERROR("failed to open file: %s\n", filePath);
      return;
   }
   INFO("printing control flow graph to: %s\n", filePath);

   fprintf(out, "digraph G {\n");

   for (IteratorRef it = cfg.iteratorDFS(); !it->end(); it->next()) {
      BasicBlock *bb = BasicBlock::get(
         reinterpret_cast<Graph::Node *>(it->get()));
      int idA = bb->getId();
      for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
         int idB = BasicBlock::get(ei.getNode())->getId();
         switch (ei.getType()) {
         case Graph::Edge::TREE:
            fprintf(out, "\t%i -> %i;\n", idA, idB);
            break;
         case Graph::Edge::FORWARD:
            fprintf(out, "\t%i -> %i [color=green];\n", idA, idB);
            break;
         case Graph::Edge::CROSS:
            fprintf(out, "\t%i -> %i [color=red];\n", idA, idB);
            break;
         case Graph::Edge::BACK:
            fprintf(out, "\t%i -> %i;\n", idA, idB);
            break;
         default:
            assert(0);
            break;
         }
      }
   }

   fprintf(out, "}\n");
   fclose(out);
}

} // namespace nv50_ir