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