src/gallium/drivers/nv50/codegen/nv50_ir_bb.cpp

   1
   2 #include "nv50_ir.h"
   3
   4 namespace nv50_ir {
   5
   6 Function::Function(Program *p, const char *fnName)
   7    : call(this),
   8      name(fnName),
   9      prog(p)
  10 {
  11    cfgExit = NULL;
  12    domTree = NULL;
  13
  14    bbArray = NULL;
  15    bbCount = 0;
  16    loopNestingBound = 0;
  17    regClobberMax = 0;
  18
  19    binPos = 0;
  20    binSize = 0;
  21
  22    prog->add(this, id);
  23 }
  24
  25 Function::~Function()
  26 {
  27    if (domTree)
  28       delete domTree;
  29    if (bbArray)
  30       delete[] bbArray;
  31
  32    for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next())
  33       delete reinterpret_cast<BasicBlock *>(BBs.get());
  34 }
  35
  36 BasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn)
  37 {
  38    program = func->getProgram();
  39
  40    joinAt = phi = entry = exit = NULL;
  41
  42    numInsns = 0;
  43    binPos = 0;
  44    binSize = 0;
  45
  46    explicitCont = false;
  47
  48    func->add(this, this->id);
  49 }
  50
  51 BasicBlock::~BasicBlock()
  52 {
  53    // nothing yet
  54 }
  55
  56 BasicBlock *
  57 BasicBlock::idom() const
  58 {
  59    Graph::Node *dn = dom.parent();
  60    return dn ? BasicBlock::get(dn) : NULL;
  61 }
  62
  63 void
  64 BasicBlock::insertHead(Instruction *inst)
  65 {
  66    assert(inst->next == 0 && inst->prev == 0);
  67
  68    if (inst->op == OP_PHI) {
  69       if (phi) {
  70          insertBefore(phi, inst);
  71       } else {
  72          if (entry) {
  73             insertBefore(entry, phi);
  74          } else {
  75             assert(!exit);
  76             phi = exit = inst;
  77             inst->bb = this;
  78             ++numInsns;
  79          }
  80       }
  81    } else {
  82       if (entry) {
  83          insertBefore(entry, inst);
  84       } else {
  85          if (phi) {
  86             insertAfter(phi, inst);
  87          } else {
  88             assert(!exit);
  89             entry = exit = inst;
  90             inst->bb = this;
  91             ++numInsns;
  92          }
  93       }
  94    }
  95 }
  96
  97 void
  98 BasicBlock::insertTail(Instruction *inst)
  99 {
 100    assert(inst->next == 0 && inst->prev == 0);
 101
 102    if (inst->op == OP_PHI) {
 103       if (entry) {
 104          insertBefore(entry, inst);
 105       } else
 106       if (exit) {
 107          assert(phi);
 108          insertAfter(exit, inst);
 109       } else {
 110          assert(!phi);
 111          phi = exit = inst;
 112          inst->bb = this;
 113          ++numInsns;
 114       }
 115    } else {
 116       if (exit) {
 117          insertAfter(exit, inst);
 118       } else {
 119          assert(!phi);
 120          entry = exit = inst;
 121          inst->bb = this;
 122          ++numInsns;
 123       }
 124    }
 125 }
 126
 127 void
 128 BasicBlock::insertBefore(Instruction *q, Instruction *p)
 129 {
 130    assert(p && q);
 131
 132    assert(p->next == 0 && p->prev == 0);
 133
 134    if (q == entry) {
 135       if (p->op == OP_PHI) {
 136          if (!phi)
 137             phi = p;
 138       } else {
 139          entry = p;
 140       }
 141    } else
 142    if (q == phi) {
 143       assert(p->op == OP_PHI);
 144       phi = p;
 145    }
 146
 147    p->next = q;
 148    p->prev = q->prev;
 149    if (p->prev)
 150       p->prev->next = p;
 151    q->prev = p;
 152
 153    p->bb = this;
 154    ++numInsns;
 155 }
 156
 157 void
 158 BasicBlock::insertAfter(Instruction *p, Instruction *q)
 159 {
 160    assert(p && q);
 161    assert(q->op != OP_PHI || p->op == OP_PHI);
 162
 163    assert(q->next == 0 && q->prev == 0);
 164
 165    if (p == exit)
 166       exit = q;
 167    if (p->op == OP_PHI && q->op != OP_PHI)
 168       entry = q;
 169
 170    q->prev = p;
 171    q->next = p->next;
 172    if (q->next)
 173       q->next->prev = q;
 174    p->next = q;
 175
 176    q->bb = this;
 177    ++numInsns;
 178 }
 179
 180 void
 181 BasicBlock::remove(Instruction *insn)
 182 {
 183    assert(insn->bb == this);
 184
 185    if (insn->prev)
 186       insn->prev->next = insn->next;
 187
 188    if (insn->next)
 189       insn->next->prev = insn->prev;
 190    else
 191       exit = insn->prev;
 192
 193    if (insn == entry)
 194       entry = insn->next ? insn->next : insn->prev;
 195
 196    if (insn == phi)
 197       phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0;
 198
 199    --numInsns;
 200    insn->bb = NULL;
 201    insn->next =
 202    insn->prev = NULL;
 203 }
 204
 205 void BasicBlock::permuteAdjacent(Instruction *a, Instruction *b)
 206 {
 207    assert(a->bb == b->bb);
 208
 209    if (a->next != b) {
 210       Instruction *i = a;
 211       a = b;
 212       b = i;
 213    }
 214    assert(a->next == b);
 215    assert(a->op != OP_PHI && b->op != OP_PHI);
 216
 217    if (b == exit)
 218       exit = a;
 219    if (a == entry)
 220       entry = b;
 221
 222    b->prev = a->prev;
 223    a->next = b->next;
 224    b->next = a;
 225    a->prev = b;
 226
 227    if (b->prev)
 228       b->prev->next = b;
 229    if (a->prev)
 230       a->next->prev = a;
 231 }
 232
 233 bool
 234 BasicBlock::dominatedBy(BasicBlock *that)
 235 {
 236    Graph::Node *bn = &that->dom;
 237    Graph::Node *dn = &this->dom;
 238
 239    while (dn && dn != bn)
 240       dn = dn->parent();
 241
 242    return dn != NULL;
 243 }
 244
 245 unsigned int
 246 BasicBlock::initiatesSimpleConditional() const
 247 {
 248    Graph::Node *out[2];
 249    int n;
 250    Graph::Edge::Type eR;
 251
 252    if (cfg.outgoingCount() != 2) // -> if and -> else/endif
 253       return false;
 254
 255    n = 0;
 256    for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next())
 257       out[n++] = ei.getNode();
 258    eR = out[1]->outgoing().getType();
 259
 260    // IF block is out edge to the right
 261    if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK)
 262       return 0x2;
 263
 264    if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence
 265       return 0x0;
 266    // do they reconverge immediately ?
 267    if (out[1]->outgoing().getNode() == out[0])
 268       return 0x1;
 269    if (out[0]->outgoingCount() == 1)
 270       if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode())
 271          return 0x3;
 272
 273    return 0x0;
 274 }
 275
 276 bool
 277 Function::setEntry(BasicBlock *bb)
 278 {
 279    if (cfg.getRoot())
 280       return false;
 281    cfg.insert(&bb->cfg);
 282    return true;
 283 }
 284
 285 bool
 286 Function::setExit(BasicBlock *bb)
 287 {
 288    if (cfgExit)
 289       return false;
 290    cfgExit = &bb->cfg;
 291    return true;
 292 }
 293
 294 unsigned int
 295 Function::orderInstructions(ArrayList &result)
 296 {
 297    Iterator *iter;
 298    for (iter = cfg.iteratorCFG(); !iter->end(); iter->next())
 299       for (Instruction *insn = BasicBlock::get(*iter)->getFirst();
 300            insn; insn = insn->next)
 301          result.insert(insn, insn->serial);
 302    cfg.putIterator(iter);
 303    return result.getSize();
 304 }
 305
 306 bool
 307 Pass::run(Program *prog, bool ordered, bool skipPhi)
 308 {
 309    this->prog = prog;
 310    err = false;
 311    return doRun(prog, ordered, skipPhi);
 312 }
 313
 314 bool
 315 Pass::doRun(Program *prog, bool ordered, bool skipPhi)
 316 {
 317    for (ArrayList::Iterator fi = prog->allFuncs.iterator();
 318         !fi.end(); fi.next()) {
 319       Function *fn = reinterpret_cast<Function *>(fi.get());
 320       if (!doRun(fn, ordered, skipPhi))
 321          return false;
 322    }
 323    return !err;
 324 }
 325
 326 bool
 327 Pass::run(Function *func, bool ordered, bool skipPhi)
 328 {
 329    prog = func->getProgram();
 330    err = false;
 331    return doRun(func, ordered, skipPhi);
 332 }
 333
 334 bool
 335 Pass::doRun(Function *func, bool ordered, bool skipPhi)
 336 {
 337    Iterator *bbIter;
 338    BasicBlock *bb;
 339    Instruction *insn, *next;
 340
 341    this->func = func;
 342    if (!visit(func))
 343       return false;
 344
 345    bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS();
 346
 347    for (; !bbIter->end(); bbIter->next()) {
 348       bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get()));
 349       if (!visit(bb))
 350          break;
 351       for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL;
 352            insn = next) {
 353          next = insn->next;
 354          if (!visit(insn))
 355             break;
 356       }
 357    }
 358    func->cfg.putIterator(bbIter);
 359    return !err;
 360 }
 361
 362 void
 363 Function::printCFGraph(const char *filePath)
 364 {
 365    FILE *out = fopen(filePath, "a");
 366    if (!out) {
 367       ERROR("failed to open file: %s\n", filePath);
 368       return;
 369    }
 370    INFO("printing control flow graph to: %s\n", filePath);
 371
 372    fprintf(out, "digraph G {\n");
 373
 374    Iterator *iter;
 375    for (iter = cfg.iteratorDFS(); !iter->end(); iter->next()) {
 376       BasicBlock *bb = BasicBlock::get(
 377          reinterpret_cast<Graph::Node *>(iter->get()));
 378       int idA = bb->getId();
 379       for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
 380          int idB = BasicBlock::get(ei.getNode())->getId();
 381          switch (ei.getType()) {
 382          case Graph::Edge::TREE:
 383             fprintf(out, "\t%i -> %i;\n", idA, idB);
 384             break;
 385          case Graph::Edge::FORWARD:
 386             fprintf(out, "\t%i -> %i [color=green];\n", idA, idB);
 387             break;
 388          case Graph::Edge::CROSS:
 389             fprintf(out, "\t%i -> %i [color=red];\n", idA, idB);
 390             break;
 391          case Graph::Edge::BACK:
 392             fprintf(out, "\t%i -> %i;\n", idA, idB);
 393             break;
 394          case Graph::Edge::DUMMY:
 395             fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB);
 396             break;
 397          default:
 398             assert(0);
 399             break;
 400          }
 401       }
 402    }
 403    cfg.putIterator(iter);
 404
 405    fprintf(out, "}\n");
 406    fclose(out);
 407 }
 408
 409 } // namespace nv50_ir