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