"Fossies" - the Fresh Open Source Software Archive

Member "mesa-20.1.8/src/gallium/drivers/nouveau/codegen/nv50_ir_bb.cpp" (16 Sep 2020, 12207 Bytes) of package /linux/misc/mesa-20.1.8.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "nv50_ir_bb.cpp" see the Fossies "Dox" file reference documentation.

    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          default:
  540             assert(0);
  541             break;
  542          }
  543       }
  544    }
  545 
  546    fprintf(out, "}\n");
  547    fclose(out);
  548 }
  549 
  550 } // namespace nv50_ir