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