src/gallium/drivers/nouveau/codegen/nv50_ir_ssa.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 #include "codegen/nv50_ir_target.h"
  25
  26 namespace nv50_ir {
  27
  28 // Converts nv50 IR generated from TGSI to SSA form.
  29
  30 // DominatorTree implements an algorithm for finding immediate dominators,
  31 // as described by T. Lengauer & R. Tarjan.
  32 class DominatorTree : public Graph
  33 {
  34 public:
  35    DominatorTree(Graph *cfg);
  36    ~DominatorTree() { }
  37
  38    bool dominates(BasicBlock *, BasicBlock *);
  39
  40    void findDominanceFrontiers();
  41
  42 private:
  43    void build();
  44    void buildDFS(Node *);
  45
  46    void squash(int);
  47    inline void link(int, int);
  48    inline int eval(int);
  49
  50    void debugPrint();
  51
  52    Graph *cfg;
  53
  54    Node **vert;
  55    int *data;
  56    const int count;
  57
  58    #define SEMI(i)     (data[(i) + 0 * count])
  59    #define ANCESTOR(i) (data[(i) + 1 * count])
  60    #define PARENT(i)   (data[(i) + 2 * count])
  61    #define LABEL(i)    (data[(i) + 3 * count])
  62    #define DOM(i)      (data[(i) + 4 * count])
  63 };
  64
  65 void DominatorTree::debugPrint()
  66 {
  67    for (int i = 0; i < count; ++i) {
  68       INFO("SEMI(%i) = %i\n", i, SEMI(i));
  69       INFO("ANCESTOR(%i) = %i\n", i, ANCESTOR(i));
  70       INFO("PARENT(%i) = %i\n", i, PARENT(i));
  71       INFO("LABEL(%i) = %i\n", i, LABEL(i));
  72       INFO("DOM(%i) = %i\n", i, DOM(i));
  73    }
  74 }
  75
  76 DominatorTree::DominatorTree(Graph *cfgraph) : cfg(cfgraph),
  77                                                count(cfg->getSize())
  78 {
  79    int i = 0;
  80
  81    vert = new Node * [count];
  82    data = new int[5 * count];
  83
  84    for (IteratorRef it = cfg->iteratorDFS(true); !it->end(); it->next(), ++i) {
  85       vert[i] = reinterpret_cast<Node *>(it->get());
  86       vert[i]->tag = i;
  87       LABEL(i) = i;
  88       SEMI(i) = ANCESTOR(i) = -1;
  89    }
  90    assert(i == count);
  91
  92    build();
  93
  94    delete[] vert;
  95    delete[] data;
  96 }
  97
  98 void DominatorTree::buildDFS(Graph::Node *node)
  99 {
 100    SEMI(node->tag) = node->tag;
 101
 102    for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) {
 103       if (SEMI(ei.getNode()->tag) < 0) {
 104          buildDFS(ei.getNode());
 105          PARENT(ei.getNode()->tag) = node->tag;
 106       }
 107    }
 108 }
 109
 110 void DominatorTree::squash(int v)
 111 {
 112    if (ANCESTOR(ANCESTOR(v)) >= 0) {
 113       squash(ANCESTOR(v));
 114
 115       if (SEMI(LABEL(ANCESTOR(v))) < SEMI(LABEL(v)))
 116          LABEL(v) = LABEL(ANCESTOR(v));
 117       ANCESTOR(v) = ANCESTOR(ANCESTOR(v));
 118    }
 119 }
 120
 121 int DominatorTree::eval(int v)
 122 {
 123    if (ANCESTOR(v) < 0)
 124       return v;
 125    squash(v);
 126    return LABEL(v);
 127 }
 128
 129 void DominatorTree::link(int v, int w)
 130 {
 131    ANCESTOR(w) = v;
 132 }
 133
 134 void DominatorTree::build()
 135 {
 136    DLList *bucket = new DLList[count];
 137    Node *nv, *nw;
 138    int p, u, v, w;
 139
 140    buildDFS(cfg->getRoot());
 141
 142    for (w = count - 1; w >= 1; --w) {
 143       nw = vert[w];
 144       assert(nw->tag == w);
 145       for (Graph::EdgeIterator ei = nw->incident(); !ei.end(); ei.next()) {
 146          nv = ei.getNode();
 147          v = nv->tag;
 148          u = eval(v);
 149          if (SEMI(u) < SEMI(w))
 150             SEMI(w) = SEMI(u);
 151       }
 152       p = PARENT(w);
 153       bucket[SEMI(w)].insert(nw);
 154       link(p, w);
 155
 156       for (DLList::Iterator it = bucket[p].iterator(); !it.end(); it.erase()) {
 157          v = reinterpret_cast<Node *>(it.get())->tag;
 158          u = eval(v);
 159          DOM(v) = (SEMI(u) < SEMI(v)) ? u : p;
 160       }
 161    }
 162    for (w = 1; w < count; ++w) {
 163       if (DOM(w) != SEMI(w))
 164          DOM(w) = DOM(DOM(w));
 165    }
 166    DOM(0) = 0;
 167
 168    insert(&BasicBlock::get(cfg->getRoot())->dom);
 169    do {
 170       p = 0;
 171       for (v = 1; v < count; ++v) {
 172          nw = &BasicBlock::get(vert[DOM(v)])->dom;
 173          nv = &BasicBlock::get(vert[v])->dom;
 174          if (nw->getGraph() && !nv->getGraph()) {
 175             ++p;
 176             nw->attach(nv, Graph::Edge::TREE);
 177          }
 178       }
 179    } while (p);
 180
 181    delete[] bucket;
 182 }
 183
 184 #undef SEMI
 185 #undef ANCESTOR
 186 #undef PARENT
 187 #undef LABEL
 188 #undef DOM
 189
 190 void DominatorTree::findDominanceFrontiers()
 191 {
 192    BasicBlock *bb;
 193
 194    for (IteratorRef dtIt = iteratorDFS(false); !dtIt->end(); dtIt->next()) {
 195       EdgeIterator succIt, chldIt;
 196
 197       bb = BasicBlock::get(reinterpret_cast<Node *>(dtIt->get()));
 198       bb->getDF().clear();
 199
 200       for (succIt = bb->cfg.outgoing(); !succIt.end(); succIt.next()) {
 201          BasicBlock *dfLocal = BasicBlock::get(succIt.getNode());
 202          if (dfLocal->idom() != bb)
 203             bb->getDF().insert(dfLocal);
 204       }
 205
 206       for (chldIt = bb->dom.outgoing(); !chldIt.end(); chldIt.next()) {
 207          BasicBlock *cb = BasicBlock::get(chldIt.getNode());
 208
 209          DLList::Iterator dfIt = cb->getDF().iterator();
 210          for (; !dfIt.end(); dfIt.next()) {
 211             BasicBlock *dfUp = BasicBlock::get(dfIt);
 212             if (dfUp->idom() != bb)
 213                bb->getDF().insert(dfUp);
 214          }
 215       }
 216    }
 217 }
 218
 219 // liveIn(bb) = usedBeforeAssigned(bb) U (liveOut(bb) - assigned(bb))
 220 void
 221 Function::buildLiveSetsPreSSA(BasicBlock *bb, const int seq)
 222 {
 223    Function *f = bb->getFunction();
 224    BitSet usedBeforeAssigned(allLValues.getSize(), true);
 225    BitSet assigned(allLValues.getSize(), true);
 226
 227    bb->liveSet.allocate(allLValues.getSize(), false);
 228
 229    int n = 0;
 230    for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
 231       BasicBlock *out = BasicBlock::get(ei.getNode());
 232       if (out == bb)
 233          continue;
 234       if (out->cfg.visit(seq))
 235          buildLiveSetsPreSSA(out, seq);
 236       if (!n++)
 237          bb->liveSet = out->liveSet;
 238       else
 239          bb->liveSet |= out->liveSet;
 240    }
 241    if (!n && !bb->liveSet.marker)
 242       bb->liveSet.fill(0);
 243    bb->liveSet.marker = true;
 244
 245    for (Instruction *i = bb->getEntry(); i; i = i->next) {
 246       for (int s = 0; i->srcExists(s); ++s)
 247          if (i->getSrc(s)->asLValue() && !assigned.test(i->getSrc(s)->id))
 248             usedBeforeAssigned.set(i->getSrc(s)->id);
 249       for (int d = 0; i->defExists(d); ++d)
 250          assigned.set(i->getDef(d)->id);
 251    }
 252
 253    if (bb == BasicBlock::get(f->cfgExit)) {
 254       for (std::deque<ValueRef>::iterator it = f->outs.begin();
 255            it != f->outs.end(); ++it) {
 256          if (!assigned.test(it->get()->id))
 257             usedBeforeAssigned.set(it->get()->id);
 258       }
 259    }
 260
 261    bb->liveSet.andNot(assigned);
 262    bb->liveSet |= usedBeforeAssigned;
 263 }
 264
 265 void
 266 Function::buildDefSetsPreSSA(BasicBlock *bb, const int seq)
 267 {
 268    bb->defSet.allocate(allLValues.getSize(), !bb->liveSet.marker);
 269    bb->liveSet.marker = true;
 270
 271    for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) {
 272       BasicBlock *in = BasicBlock::get(ei.getNode());
 273
 274       if (in->cfg.visit(seq))
 275          buildDefSetsPreSSA(in, seq);
 276
 277       bb->defSet |= in->defSet;
 278    }
 279
 280    for (Instruction *i = bb->getEntry(); i; i = i->next) {
 281       for (int d = 0; i->defExists(d); ++d)
 282          bb->defSet.set(i->getDef(d)->id);
 283    }
 284 }
 285
 286 class RenamePass
 287 {
 288 public:
 289    RenamePass(Function *);
 290    ~RenamePass();
 291
 292    bool run();
 293    void search(BasicBlock *);
 294
 295    inline LValue *getStackTop(Value *);
 296
 297    LValue *mkUndefined(Value *);
 298
 299 private:
 300    Stack *stack;
 301    Function *func;
 302    Program *prog;
 303 };
 304
 305 bool
 306 Program::convertToSSA()
 307 {
 308    for (ArrayList::Iterator fi = allFuncs.iterator(); !fi.end(); fi.next()) {
 309       Function *fn = reinterpret_cast<Function *>(fi.get());
 310       if (!fn->convertToSSA())
 311          return false;
 312    }
 313    return true;
 314 }
 315
 316 // XXX: add edge from entry to exit ?
 317
 318 // Efficiently Computing Static Single Assignment Form and
 319 //  the Control Dependence Graph,
 320 // R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck
 321 bool
 322 Function::convertToSSA()
 323 {
 324    // 0. calculate live in variables (for pruned SSA)
 325    buildLiveSets();
 326
 327    // 1. create the dominator tree
 328    domTree = new DominatorTree(&cfg);
 329    reinterpret_cast<DominatorTree *>(domTree)->findDominanceFrontiers();
 330
 331    // 2. insert PHI functions
 332    DLList workList;
 333    LValue *lval;
 334    BasicBlock *bb;
 335    int var;
 336    int iterCount = 0;
 337    int *hasAlready = new int[allBBlocks.getSize() * 2];
 338    int *work = &hasAlready[allBBlocks.getSize()];
 339
 340    memset(hasAlready, 0, allBBlocks.getSize() * 2 * sizeof(int));
 341
 342    // for each variable
 343    for (var = 0; var < allLValues.getSize(); ++var) {
 344       if (!allLValues.get(var))
 345          continue;
 346       lval = reinterpret_cast<Value *>(allLValues.get(var))->asLValue();
 347       if (!lval || lval->defs.empty())
 348          continue;
 349       ++iterCount;
 350
 351       // TODO: don't add phi functions for values that aren't used outside
 352       //  the BB they're defined in
 353
 354       // gather blocks with assignments to lval in workList
 355       for (Value::DefIterator d = lval->defs.begin();
 356            d != lval->defs.end(); ++d) {
 357          bb = ((*d)->getInsn() ? (*d)->getInsn()->bb : NULL);
 358          if (!bb)
 359             continue; // instruction likely been removed but not XXX deleted
 360
 361          if (work[bb->getId()] == iterCount)
 362             continue;
 363          work[bb->getId()] = iterCount;
 364          workList.insert(bb);
 365       }
 366
 367       // for each block in workList, insert a phi for lval in the block's
 368       //  dominance frontier (if we haven't already done so)
 369       for (DLList::Iterator wI = workList.iterator(); !wI.end(); wI.erase()) {
 370          bb = BasicBlock::get(wI);
 371
 372          DLList::Iterator dfIter = bb->getDF().iterator();
 373          for (; !dfIter.end(); dfIter.next()) {
 374             Instruction *phi;
 375             BasicBlock *dfBB = BasicBlock::get(dfIter);
 376
 377             if (hasAlready[dfBB->getId()] >= iterCount)
 378                continue;
 379             hasAlready[dfBB->getId()] = iterCount;
 380
 381             // pruned SSA: don't need a phi if the value is not live-in
 382             if (!dfBB->liveSet.test(lval->id))
 383                continue;
 384
 385             phi = new_Instruction(this, OP_PHI, typeOfSize(lval->reg.size));
 386             dfBB->insertTail(phi);
 387
 388             phi->setDef(0, lval);
 389             for (int s = 0; s < dfBB->cfg.incidentCount(); ++s)
 390                phi->setSrc(s, lval);
 391
 392             if (work[dfBB->getId()] < iterCount) {
 393                work[dfBB->getId()] = iterCount;
 394                wI.insert(dfBB);
 395             }
 396          }
 397       }
 398    }
 399    delete[] hasAlready;
 400
 401    RenamePass rename(this);
 402    return rename.run();
 403 }
 404
 405 RenamePass::RenamePass(Function *fn) : func(fn), prog(fn->getProgram())
 406 {
 407    stack = new Stack[func->allLValues.getSize()];
 408 }
 409
 410 RenamePass::~RenamePass()
 411 {
 412    if (stack)
 413       delete[] stack;
 414 }
 415
 416 LValue *
 417 RenamePass::getStackTop(Value *val)
 418 {
 419    if (!stack[val->id].getSize())
 420       return 0;
 421    return reinterpret_cast<LValue *>(stack[val->id].peek().u.p);
 422 }
 423
 424 LValue *
 425 RenamePass::mkUndefined(Value *val)
 426 {
 427    LValue *lval = val->asLValue();
 428    assert(lval);
 429    LValue *ud = new_LValue(func, lval);
 430    Instruction *nop = new_Instruction(func, OP_NOP, typeOfSize(lval->reg.size));
 431    nop->setDef(0, ud);
 432    BasicBlock::get(func->cfg.getRoot())->insertHead(nop);
 433    return ud;
 434 }
 435
 436 bool RenamePass::run()
 437 {
 438    if (!stack)
 439       return false;
 440    search(BasicBlock::get(func->domTree->getRoot()));
 441
 442    return true;
 443 }
 444
 445 // Go through BBs in dominance order, create new values for each definition,
 446 // and replace all sources with their current new values.
 447 //
 448 // NOTE: The values generated for function inputs/outputs have no connection
 449 // to their corresponding outputs/inputs in other functions. Only allocation
 450 // of physical registers will establish this connection.
 451 //
 452 void RenamePass::search(BasicBlock *bb)
 453 {
 454    LValue *lval, *ssa;
 455    int d, s;
 456    const Target *targ = prog->getTarget();
 457
 458    // Put current definitions for function inputs values on the stack.
 459    // They can be used before any redefinitions are pushed.
 460    if (bb == BasicBlock::get(func->cfg.getRoot())) {
 461       for (std::deque<ValueDef>::iterator it = func->ins.begin();
 462            it != func->ins.end(); ++it) {
 463          lval = it->get()->asLValue();
 464          assert(lval);
 465
 466          ssa = new_LValue(func, targ->nativeFile(lval->reg.file));
 467          ssa->reg.size = lval->reg.size;
 468          ssa->reg.data.id = lval->reg.data.id;
 469
 470          it->setSSA(ssa);
 471          stack[lval->id].push(ssa);
 472       }
 473    }
 474
 475    for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) {
 476       // PHI sources get definitions from the passes through the incident BBs,
 477       // so skip them here.
 478       if (stmt->op != OP_PHI) {
 479          for (s = 0; stmt->srcExists(s); ++s) {
 480             lval = stmt->getSrc(s)->asLValue();
 481             if (!lval)
 482                continue;
 483             // Values on the stack created in previously visited blocks, and
 484             // function inputs, will be valid because they dominate this one.
 485             lval = getStackTop(lval);
 486             if (!lval)
 487                lval = mkUndefined(stmt->getSrc(s));
 488             stmt->setSrc(s, lval);
 489          }
 490       }
 491       for (d = 0; stmt->defExists(d); ++d) {
 492          lval = stmt->def(d).get()->asLValue();
 493          assert(lval);
 494          stmt->def(d).setSSA(
 495             new_LValue(func, targ->nativeFile(lval->reg.file)));
 496          stmt->def(d).get()->reg.size = lval->reg.size;
 497          stmt->def(d).get()->reg.data.id = lval->reg.data.id;
 498          stack[lval->id].push(stmt->def(d).get());
 499       }
 500    }
 501
 502    // Update sources of PHI ops corresponding to this BB in outgoing BBs.
 503    for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
 504       Instruction *phi;
 505       int p = 0;
 506       BasicBlock *sb = BasicBlock::get(ei.getNode());
 507
 508       // which predecessor of sb is bb ?
 509       for (Graph::EdgeIterator ei = sb->cfg.incident(); !ei.end(); ei.next()) {
 510          if (ei.getNode() == &bb->cfg)
 511             break;
 512          ++p;
 513       }
 514       assert(p < sb->cfg.incidentCount());
 515
 516       for (phi = sb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) {
 517          lval = getStackTop(phi->getSrc(p));
 518          if (!lval)
 519             lval = mkUndefined(phi->getSrc(p));
 520          phi->setSrc(p, lval);
 521       }
 522    }
 523
 524    // Visit the BBs we dominate.
 525    for (Graph::EdgeIterator ei = bb->dom.outgoing(); !ei.end(); ei.next())
 526       search(BasicBlock::get(ei.getNode()));
 527
 528    // Update function outputs to the last definitions of their pre-SSA values.
 529    // I hope they're unique, i.e. that we get PHIs for all of them ...
 530    if (bb == BasicBlock::get(func->cfgExit)) {
 531       for (std::deque<ValueRef>::iterator it = func->outs.begin();
 532            it != func->outs.end(); ++it) {
 533          lval = it->get()->asLValue();
 534          if (!lval)
 535             continue;
 536          lval = getStackTop(lval);
 537          if (!lval)
 538             lval = mkUndefined(it->get());
 539          it->set(lval);
 540       }
 541    }
 542
 543    // Pop the values we created in this block from the stack because we will
 544    // return to blocks that we do not dominate.
 545    for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) {
 546       if (stmt->op == OP_NOP)
 547          continue;
 548       for (d = 0; stmt->defExists(d); ++d)
 549          stack[stmt->def(d).preSSA()->id].pop();
 550    }
 551 }
 552
 553 } // namespace nv50_ir