Home | History | Annotate | Download | only in codegen 
      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
    547