src/gallium/drivers/nv50/codegen/nv50_ir_bb.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 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  18  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
  19  * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  */
  22
  23 #include "nv50_ir.h"
  24
  25 namespace nv50_ir {
  26
  27 Function::Function(Program *p, const char *fnName)
  28    : call(this),
  29      name(fnName),
  30      prog(p)
  31 {
  32    cfgExit = NULL;
  33    domTree = NULL;
  34
  35    bbArray = NULL;
  36    bbCount = 0;
  37    loopNestingBound = 0;
  38    regClobberMax = 0;
  39
  40    binPos = 0;
  41    binSize = 0;
  42
  43    prog->add(this, id);
  44 }
  45
  46 Function::~Function()
  47 {
  48    if (domTree)
  49       delete domTree;
  50    if (bbArray)
  51       delete[] bbArray;
  52
  53    for (ArrayList::Iterator it = allInsns.iterator(); !it.end(); it.next())
  54       delete_Instruction(prog, reinterpret_cast<Instruction *>(it.get()));
  55
  56    for (ArrayList::Iterator it = allLValues.iterator(); !it.end(); it.next())
  57       delete_Value(prog, reinterpret_cast<LValue *>(it.get()));
  58
  59    for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next())
  60       delete reinterpret_cast<BasicBlock *>(BBs.get());
  61 }
  62
  63 BasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn)
  64 {
  65    program = func->getProgram();
  66
  67    joinAt = phi = entry = exit = NULL;
  68
  69    numInsns = 0;
  70    binPos = 0;
  71    binSize = 0;
  72
  73    explicitCont = false;
  74
  75    func->add(this, this->id);
  76 }
  77
  78 BasicBlock::~BasicBlock()
  79 {
  80    // nothing yet
  81 }
  82
  83 BasicBlock *
  84 BasicBlock::idom() const
  85 {
  86    Graph::Node *dn = dom.parent();
  87    return dn ? BasicBlock::get(dn) : NULL;
  88 }
  89
  90 void
  91 BasicBlock::insertHead(Instruction *inst)
  92 {
  93    assert(inst->next == 0 && inst->prev == 0);
  94
  95    if (inst->op == OP_PHI) {
  96       if (phi) {
  97          insertBefore(phi, inst);
  98       } else {
  99          if (entry) {
 100             insertBefore(entry, inst);
 101          } else {
 102             assert(!exit);
 103             phi = exit = inst;
 104             inst->bb = this;
 105             ++numInsns;
 106          }
 107       }
 108    } else {
 109       if (entry) {
 110          insertBefore(entry, inst);
 111       } else {
 112          if (phi) {
 113             insertAfter(exit, inst); // after last phi
 114          } else {
 115             assert(!exit);
 116             entry = exit = inst;
 117             inst->bb = this;
 118             ++numInsns;
 119          }
 120       }
 121    }
 122 }
 123
 124 void
 125 BasicBlock::insertTail(Instruction *inst)
 126 {
 127    assert(inst->next == 0 && inst->prev == 0);
 128
 129    if (inst->op == OP_PHI) {
 130       if (entry) {
 131          insertBefore(entry, inst);
 132       } else
 133       if (exit) {
 134          assert(phi);
 135          insertAfter(exit, inst);
 136       } else {
 137          assert(!phi);
 138          phi = exit = inst;
 139          inst->bb = this;
 140          ++numInsns;
 141       }
 142    } else {
 143       if (exit) {
 144          insertAfter(exit, inst);
 145       } else {
 146          assert(!phi);
 147          entry = exit = inst;
 148          inst->bb = this;
 149          ++numInsns;
 150       }
 151    }
 152 }
 153
 154 void
 155 BasicBlock::insertBefore(Instruction *q, Instruction *p)
 156 {
 157    assert(p && q);
 158
 159    assert(p->next == 0 && p->prev == 0);
 160
 161    if (q == entry) {
 162       if (p->op == OP_PHI) {
 163          if (!phi)
 164             phi = p;
 165       } else {
 166          entry = p;
 167       }
 168    } else
 169    if (q == phi) {
 170       assert(p->op == OP_PHI);
 171       phi = p;
 172    }
 173
 174    p->next = q;
 175    p->prev = q->prev;
 176    if (p->prev)
 177       p->prev->next = p;
 178    q->prev = p;
 179
 180    p->bb = this;
 181    ++numInsns;
 182 }
 183
 184 void
 185 BasicBlock::insertAfter(Instruction *p, Instruction *q)
 186 {
 187    assert(p && q);
 188    assert(q->op != OP_PHI || p->op == OP_PHI);
 189
 190    assert(q->next == 0 && q->prev == 0);
 191
 192    if (p == exit)
 193       exit = q;
 194    if (p->op == OP_PHI && q->op != OP_PHI)
 195       entry = q;
 196
 197    q->prev = p;
 198    q->next = p->next;
 199    if (q->next)
 200       q->next->prev = q;
 201    p->next = q;
 202
 203    q->bb = this;
 204    ++numInsns;
 205 }
 206
 207 void
 208 BasicBlock::remove(Instruction *insn)
 209 {
 210    assert(insn->bb == this);
 211
 212    if (insn->prev)
 213       insn->prev->next = insn->next;
 214
 215    if (insn->next)
 216       insn->next->prev = insn->prev;
 217    else
 218       exit = insn->prev;
 219
 220    if (insn == entry) {
 221       if (insn->next)
 222          entry = insn->next;
 223       else
 224       if (insn->prev && insn->prev->op != OP_PHI)
 225          entry = insn->prev;
 226       else
 227          entry = NULL;
 228    }
 229
 230    if (insn == phi)
 231       phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0;
 232
 233    --numInsns;
 234    insn->bb = NULL;
 235    insn->next =
 236    insn->prev = NULL;
 237 }
 238
 239 void BasicBlock::permuteAdjacent(Instruction *a, Instruction *b)
 240 {
 241    assert(a->bb == b->bb);
 242
 243    if (a->next != b) {
 244       Instruction *i = a;
 245       a = b;
 246       b = i;
 247    }
 248    assert(a->next == b);
 249    assert(a->op != OP_PHI && b->op != OP_PHI);
 250
 251    if (b == exit)
 252       exit = a;
 253    if (a == entry)
 254       entry = b;
 255
 256    b->prev = a->prev;
 257    a->next = b->next;
 258    b->next = a;
 259    a->prev = b;
 260
 261    if (b->prev)
 262       b->prev->next = b;
 263    if (a->prev)
 264       a->next->prev = a;
 265 }
 266
 267 void
 268 BasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach)
 269 {
 270    bb->entry = insn;
 271
 272    if (insn) {
 273       exit = insn->prev;
 274       insn->prev = NULL;
 275    }
 276
 277    if (exit)
 278       exit->next = NULL;
 279    else
 280       entry = NULL;
 281
 282    while (!cfg.outgoing(true).end()) {
 283       Graph::Edge *e = cfg.outgoing(true).getEdge();
 284       bb->cfg.attach(e->getTarget(), e->getType());
 285       this->cfg.detach(e->getTarget());
 286    }
 287
 288    for (; insn; insn = insn->next) {
 289       this->numInsns--;
 290       bb->numInsns++;
 291       insn->bb = bb;
 292       bb->exit = insn;
 293    }
 294    if (attach)
 295       this->cfg.attach(&bb->cfg, Graph::Edge::TREE);
 296 }
 297
 298 BasicBlock *
 299 BasicBlock::splitBefore(Instruction *insn, bool attach)
 300 {
 301    BasicBlock *bb = new BasicBlock(func);
 302    assert(!insn || insn->op != OP_PHI);
 303
 304    splitCommon(insn, bb, attach);
 305    return bb;
 306 }
 307
 308 BasicBlock *
 309 BasicBlock::splitAfter(Instruction *insn, bool attach)
 310 {
 311    BasicBlock *bb = new BasicBlock(func);
 312    assert(!insn || insn->op != OP_PHI);
 313
 314    bb->joinAt = joinAt;
 315    joinAt = NULL;
 316
 317    splitCommon(insn ? insn->next : NULL, bb, attach);
 318    return bb;
 319 }
 320
 321 bool
 322 BasicBlock::dominatedBy(BasicBlock *that)
 323 {
 324    Graph::Node *bn = &that->dom;
 325    Graph::Node *dn = &this->dom;
 326
 327    while (dn && dn != bn)
 328       dn = dn->parent();
 329
 330    return dn != NULL;
 331 }
 332
 333 unsigned int
 334 BasicBlock::initiatesSimpleConditional() const
 335 {
 336    Graph::Node *out[2];
 337    int n;
 338    Graph::Edge::Type eR;
 339
 340    if (cfg.outgoingCount() != 2) // -> if and -> else/endif
 341       return false;
 342
 343    n = 0;
 344    for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next())
 345       out[n++] = ei.getNode();
 346    eR = out[1]->outgoing().getType();
 347
 348    // IF block is out edge to the right
 349    if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK)
 350       return 0x2;
 351
 352    if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence
 353       return 0x0;
 354    // do they reconverge immediately ?
 355    if (out[1]->outgoing().getNode() == out[0])
 356       return 0x1;
 357    if (out[0]->outgoingCount() == 1)
 358       if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode())
 359          return 0x3;
 360
 361    return 0x0;
 362 }
 363
 364 bool
 365 Function::setEntry(BasicBlock *bb)
 366 {
 367    if (cfg.getRoot())
 368       return false;
 369    cfg.insert(&bb->cfg);
 370    return true;
 371 }
 372
 373 bool
 374 Function::setExit(BasicBlock *bb)
 375 {
 376    if (cfgExit)
 377       return false;
 378    cfgExit = &bb->cfg;
 379    return true;
 380 }
 381
 382 unsigned int
 383 Function::orderInstructions(ArrayList &result)
 384 {
 385    Iterator *iter;
 386    for (iter = cfg.iteratorCFG(); !iter->end(); iter->next()) {
 387       BasicBlock *bb =
 388          BasicBlock::get(reinterpret_cast<Graph::Node *>(iter->get()));
 389
 390       for (Instruction *insn = bb->getFirst(); insn; insn = insn->next)
 391          result.insert(insn, insn->serial);
 392    }
 393
 394    cfg.putIterator(iter);
 395    return result.getSize();
 396 }
 397
 398 bool
 399 Pass::run(Program *prog, bool ordered, bool skipPhi)
 400 {
 401    this->prog = prog;
 402    err = false;
 403    return doRun(prog, ordered, skipPhi);
 404 }
 405
 406 bool
 407 Pass::doRun(Program *prog, bool ordered, bool skipPhi)
 408 {
 409    for (ArrayList::Iterator fi = prog->allFuncs.iterator();
 410         !fi.end(); fi.next()) {
 411       Function *fn = reinterpret_cast<Function *>(fi.get());
 412       if (!doRun(fn, ordered, skipPhi))
 413          return false;
 414    }
 415    return !err;
 416 }
 417
 418 bool
 419 Pass::run(Function *func, bool ordered, bool skipPhi)
 420 {
 421    prog = func->getProgram();
 422    err = false;
 423    return doRun(func, ordered, skipPhi);
 424 }
 425
 426 bool
 427 Pass::doRun(Function *func, bool ordered, bool skipPhi)
 428 {
 429    Iterator *bbIter;
 430    BasicBlock *bb;
 431    Instruction *insn, *next;
 432
 433    this->func = func;
 434    if (!visit(func))
 435       return false;
 436
 437    bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS();
 438
 439    for (; !bbIter->end(); bbIter->next()) {
 440       bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get()));
 441       if (!visit(bb))
 442          break;
 443       for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL;
 444            insn = next) {
 445          next = insn->next;
 446          if (!visit(insn))
 447             break;
 448       }
 449    }
 450    func->cfg.putIterator(bbIter);
 451    return !err;
 452 }
 453
 454 void
 455 Function::printCFGraph(const char *filePath)
 456 {
 457    FILE *out = fopen(filePath, "a");
 458    if (!out) {
 459       ERROR("failed to open file: %s\n", filePath);
 460       return;
 461    }
 462    INFO("printing control flow graph to: %s\n", filePath);
 463
 464    fprintf(out, "digraph G {\n");
 465
 466    Iterator *iter;
 467    for (iter = cfg.iteratorDFS(); !iter->end(); iter->next()) {
 468       BasicBlock *bb = BasicBlock::get(
 469          reinterpret_cast<Graph::Node *>(iter->get()));
 470       int idA = bb->getId();
 471       for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
 472          int idB = BasicBlock::get(ei.getNode())->getId();
 473          switch (ei.getType()) {
 474          case Graph::Edge::TREE:
 475             fprintf(out, "\t%i -> %i;\n", idA, idB);
 476             break;
 477          case Graph::Edge::FORWARD:
 478             fprintf(out, "\t%i -> %i [color=green];\n", idA, idB);
 479             break;
 480          case Graph::Edge::CROSS:
 481             fprintf(out, "\t%i -> %i [color=red];\n", idA, idB);
 482             break;
 483          case Graph::Edge::BACK:
 484             fprintf(out, "\t%i -> %i;\n", idA, idB);
 485             break;
 486          case Graph::Edge::DUMMY:
 487             fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB);
 488             break;
 489          default:
 490             assert(0);
 491             break;
 492          }
 493       }
 494    }
 495    cfg.putIterator(iter);
 496
 497    fprintf(out, "}\n");
 498    fclose(out);
 499 }
 500
 501 } // namespace nv50_ir