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