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