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::clone(ClonePolicy<Function>& pol) const
  85 {
  86    BasicBlock *bb = new BasicBlock(pol.context());
  87
  88    pol.set(this, bb);
  89
  90    for (Instruction *i = getFirst(); i; i = i->next)
  91       bb->insertTail(i->clone(pol));
  92
  93    pol.context()->cfg.insert(&bb->cfg);
  94
  95    for (Graph::EdgeIterator it = cfg.outgoing(); !it.end(); it.next()) {
  96       BasicBlock *obb = BasicBlock::get(it.getNode());
  97       bb->cfg.attach(&pol.get(obb)->cfg, it.getType());
  98    }
  99
 100    return bb;
 101 }
 102
 103 BasicBlock *
 104 BasicBlock::idom() const
 105 {
 106    Graph::Node *dn = dom.parent();
 107    return dn ? BasicBlock::get(dn) : NULL;
 108 }
 109
 110 void
 111 BasicBlock::insertHead(Instruction *inst)
 112 {
 113    assert(inst->next == 0 && inst->prev == 0);
 114
 115    if (inst->op == OP_PHI) {
 116       if (phi) {
 117          insertBefore(phi, inst);
 118       } else {
 119          if (entry) {
 120             insertBefore(entry, inst);
 121          } else {
 122             assert(!exit);
 123             phi = exit = inst;
 124             inst->bb = this;
 125             ++numInsns;
 126          }
 127       }
 128    } else {
 129       if (entry) {
 130          insertBefore(entry, inst);
 131       } else {
 132          if (phi) {
 133             insertAfter(exit, inst); // after last phi
 134          } else {
 135             assert(!exit);
 136             entry = exit = inst;
 137             inst->bb = this;
 138             ++numInsns;
 139          }
 140       }
 141    }
 142 }
 143
 144 void
 145 BasicBlock::insertTail(Instruction *inst)
 146 {
 147    assert(inst->next == 0 && inst->prev == 0);
 148
 149    if (inst->op == OP_PHI) {
 150       if (entry) {
 151          insertBefore(entry, inst);
 152       } else
 153       if (exit) {
 154          assert(phi);
 155          insertAfter(exit, inst);
 156       } else {
 157          assert(!phi);
 158          phi = exit = inst;
 159          inst->bb = this;
 160          ++numInsns;
 161       }
 162    } else {
 163       if (exit) {
 164          insertAfter(exit, inst);
 165       } else {
 166          assert(!phi);
 167          entry = exit = inst;
 168          inst->bb = this;
 169          ++numInsns;
 170       }
 171    }
 172 }
 173
 174 void
 175 BasicBlock::insertBefore(Instruction *q, Instruction *p)
 176 {
 177    assert(p && q);
 178
 179    assert(p->next == 0 && p->prev == 0);
 180
 181    if (q == entry) {
 182       if (p->op == OP_PHI) {
 183          if (!phi)
 184             phi = p;
 185       } else {
 186          entry = p;
 187       }
 188    } else
 189    if (q == phi) {
 190       assert(p->op == OP_PHI);
 191       phi = p;
 192    }
 193
 194    p->next = q;
 195    p->prev = q->prev;
 196    if (p->prev)
 197       p->prev->next = p;
 198    q->prev = p;
 199
 200    p->bb = this;
 201    ++numInsns;
 202 }
 203
 204 void
 205 BasicBlock::insertAfter(Instruction *p, Instruction *q)
 206 {
 207    assert(p && q);
 208    assert(q->op != OP_PHI || p->op == OP_PHI);
 209
 210    assert(q->next == 0 && q->prev == 0);
 211
 212    if (p == exit)
 213       exit = q;
 214    if (p->op == OP_PHI && q->op != OP_PHI)
 215       entry = q;
 216
 217    q->prev = p;
 218    q->next = p->next;
 219    if (q->next)
 220       q->next->prev = q;
 221    p->next = q;
 222
 223    q->bb = this;
 224    ++numInsns;
 225 }
 226
 227 void
 228 BasicBlock::remove(Instruction *insn)
 229 {
 230    assert(insn->bb == this);
 231
 232    if (insn->prev)
 233       insn->prev->next = insn->next;
 234
 235    if (insn->next)
 236       insn->next->prev = insn->prev;
 237    else
 238       exit = insn->prev;
 239
 240    if (insn == entry) {
 241       if (insn->next)
 242          entry = insn->next;
 243       else
 244       if (insn->prev && insn->prev->op != OP_PHI)
 245          entry = insn->prev;
 246       else
 247          entry = NULL;
 248    }
 249
 250    if (insn == phi)
 251       phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0;
 252
 253    --numInsns;
 254    insn->bb = NULL;
 255    insn->next =
 256    insn->prev = NULL;
 257 }
 258
 259 void BasicBlock::permuteAdjacent(Instruction *a, Instruction *b)
 260 {
 261    assert(a->bb == b->bb);
 262
 263    if (a->next != b) {
 264       Instruction *i = a;
 265       a = b;
 266       b = i;
 267    }
 268    assert(a->next == b);
 269    assert(a->op != OP_PHI && b->op != OP_PHI);
 270
 271    if (b == exit)
 272       exit = a;
 273    if (a == entry)
 274       entry = b;
 275
 276    b->prev = a->prev;
 277    a->next = b->next;
 278    b->next = a;
 279    a->prev = b;
 280
 281    if (b->prev)
 282       b->prev->next = b;
 283    if (a->prev)
 284       a->next->prev = a;
 285 }
 286
 287 void
 288 BasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach)
 289 {
 290    bb->entry = insn;
 291
 292    if (insn) {
 293       exit = insn->prev;
 294       insn->prev = NULL;
 295    }
 296
 297    if (exit)
 298       exit->next = NULL;
 299    else
 300       entry = NULL;
 301
 302    while (!cfg.outgoing(true).end()) {
 303       Graph::Edge *e = cfg.outgoing(true).getEdge();
 304       bb->cfg.attach(e->getTarget(), e->getType());
 305       this->cfg.detach(e->getTarget());
 306    }
 307
 308    for (; insn; insn = insn->next) {
 309       this->numInsns--;
 310       bb->numInsns++;
 311       insn->bb = bb;
 312       bb->exit = insn;
 313    }
 314    if (attach)
 315       this->cfg.attach(&bb->cfg, Graph::Edge::TREE);
 316 }
 317
 318 BasicBlock *
 319 BasicBlock::splitBefore(Instruction *insn, bool attach)
 320 {
 321    BasicBlock *bb = new BasicBlock(func);
 322    assert(!insn || insn->op != OP_PHI);
 323
 324    splitCommon(insn, bb, attach);
 325    return bb;
 326 }
 327
 328 BasicBlock *
 329 BasicBlock::splitAfter(Instruction *insn, bool attach)
 330 {
 331    BasicBlock *bb = new BasicBlock(func);
 332    assert(!insn || insn->op != OP_PHI);
 333
 334    bb->joinAt = joinAt;
 335    joinAt = NULL;
 336
 337    splitCommon(insn ? insn->next : NULL, bb, attach);
 338    return bb;
 339 }
 340
 341 bool
 342 BasicBlock::dominatedBy(BasicBlock *that)
 343 {
 344    Graph::Node *bn = &that->dom;
 345    Graph::Node *dn = &this->dom;
 346
 347    while (dn && dn != bn)
 348       dn = dn->parent();
 349
 350    return dn != NULL;
 351 }
 352
 353 unsigned int
 354 BasicBlock::initiatesSimpleConditional() const
 355 {
 356    Graph::Node *out[2];
 357    int n;
 358    Graph::Edge::Type eR;
 359
 360    if (cfg.outgoingCount() != 2) // -> if and -> else/endif
 361       return false;
 362
 363    n = 0;
 364    for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next())
 365       out[n++] = ei.getNode();
 366    eR = out[1]->outgoing().getType();
 367
 368    // IF block is out edge to the right
 369    if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK)
 370       return 0x2;
 371
 372    if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence
 373       return 0x0;
 374    // do they reconverge immediately ?
 375    if (out[1]->outgoing().getNode() == out[0])
 376       return 0x1;
 377    if (out[0]->outgoingCount() == 1)
 378       if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode())
 379          return 0x3;
 380
 381    return 0x0;
 382 }
 383
 384 bool
 385 Function::setEntry(BasicBlock *bb)
 386 {
 387    if (cfg.getRoot())
 388       return false;
 389    cfg.insert(&bb->cfg);
 390    return true;
 391 }
 392
 393 bool
 394 Function::setExit(BasicBlock *bb)
 395 {
 396    if (cfgExit)
 397       return false;
 398    cfgExit = &bb->cfg;
 399    return true;
 400 }
 401
 402 unsigned int
 403 Function::orderInstructions(ArrayList &result)
 404 {
 405    for (IteratorRef it = cfg.iteratorCFG(); !it->end(); it->next()) {
 406       BasicBlock *bb =
 407          BasicBlock::get(reinterpret_cast<Graph::Node *>(it->get()));
 408
 409       for (Instruction *insn = bb->getFirst(); insn; insn = insn->next)
 410          result.insert(insn, insn->serial);
 411    }
 412
 413    return result.getSize();
 414 }
 415
 416 void
 417 Function::buildLiveSets()
 418 {
 419    for (unsigned i = 0; i <= loopNestingBound; ++i)
 420       buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), cfg.nextSequence());
 421
 422    for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
 423       BasicBlock::get(bi)->liveSet.marker = false;
 424 }
 425
 426 void
 427 Function::buildDefSets()
 428 {
 429    for (unsigned i = 0; i <= loopNestingBound; ++i)
 430       buildDefSetsPreSSA(BasicBlock::get(cfgExit), cfg.nextSequence());
 431
 432    for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
 433       BasicBlock::get(bi)->liveSet.marker = false;
 434 }
 435
 436 bool
 437 Pass::run(Program *prog, bool ordered, bool skipPhi)
 438 {
 439    this->prog = prog;
 440    err = false;
 441    return doRun(prog, ordered, skipPhi);
 442 }
 443
 444 bool
 445 Pass::doRun(Program *prog, bool ordered, bool skipPhi)
 446 {
 447    for (ArrayList::Iterator fi = prog->allFuncs.iterator();
 448         !fi.end(); fi.next()) {
 449       Function *fn = reinterpret_cast<Function *>(fi.get());
 450       if (!doRun(fn, ordered, skipPhi))
 451          return false;
 452    }
 453    return !err;
 454 }
 455
 456 bool
 457 Pass::run(Function *func, bool ordered, bool skipPhi)
 458 {
 459    prog = func->getProgram();
 460    err = false;
 461    return doRun(func, ordered, skipPhi);
 462 }
 463
 464 bool
 465 Pass::doRun(Function *func, bool ordered, bool skipPhi)
 466 {
 467    IteratorRef bbIter;
 468    BasicBlock *bb;
 469    Instruction *insn, *next;
 470
 471    this->func = func;
 472    if (!visit(func))
 473       return false;
 474
 475    bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS();
 476
 477    for (; !bbIter->end(); bbIter->next()) {
 478       bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get()));
 479       if (!visit(bb))
 480          break;
 481       for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL;
 482            insn = next) {
 483          next = insn->next;
 484          if (!visit(insn))
 485             break;
 486       }
 487    }
 488
 489    return !err;
 490 }
 491
 492 void
 493 Function::printCFGraph(const char *filePath)
 494 {
 495    FILE *out = fopen(filePath, "a");
 496    if (!out) {
 497       ERROR("failed to open file: %s\n", filePath);
 498       return;
 499    }
 500    INFO("printing control flow graph to: %s\n", filePath);
 501
 502    fprintf(out, "digraph G {\n");
 503
 504    for (IteratorRef it = cfg.iteratorDFS(); !it->end(); it->next()) {
 505       BasicBlock *bb = BasicBlock::get(
 506          reinterpret_cast<Graph::Node *>(it->get()));
 507       int idA = bb->getId();
 508       for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
 509          int idB = BasicBlock::get(ei.getNode())->getId();
 510          switch (ei.getType()) {
 511          case Graph::Edge::TREE:
 512             fprintf(out, "\t%i -> %i;\n", idA, idB);
 513             break;
 514          case Graph::Edge::FORWARD:
 515             fprintf(out, "\t%i -> %i [color=green];\n", idA, idB);
 516             break;
 517          case Graph::Edge::CROSS:
 518             fprintf(out, "\t%i -> %i [color=red];\n", idA, idB);
 519             break;
 520          case Graph::Edge::BACK:
 521             fprintf(out, "\t%i -> %i;\n", idA, idB);
 522             break;
 523          case Graph::Edge::DUMMY:
 524             fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB);
 525             break;
 526          default:
 527             assert(0);
 528             break;
 529          }
 530       }
 531    }
 532
 533    fprintf(out, "}\n");
 534    fclose(out);
 535 }
 536
 537 } // namespace nv50_ir