src/gallium/drivers/nv50/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 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 #include "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    Iterator *iter;
  80    int i;
  81
  82    vert = new Node * [count];
  83    data = new int[5 * count];
  84
  85    for (i = 0, iter = cfg->iteratorDFS(true); !iter->end(); iter->next(), ++i) {
  86       vert[i] = reinterpret_cast<Node *>(iter->get());
  87       vert[i]->tag = i;
  88       LABEL(i) = i;
  89       SEMI(i) = ANCESTOR(i) = -1;
  90    }
  91    cfg->putIterator(iter);
  92
  93    build();
  94
  95    delete[] vert;
  96    delete[] data;
  97 }
  98
  99 void DominatorTree::buildDFS(Graph::Node *node)
 100 {
 101    SEMI(node->tag) = node->tag;
 102
 103    for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) {
 104       if (SEMI(ei.getNode()->tag) < 0) {
 105          buildDFS(ei.getNode());
 106          PARENT(ei.getNode()->tag) = node->tag;
 107       }
 108    }
 109 }
 110
 111 void DominatorTree::squash(int v)
 112 {
 113    if (ANCESTOR(ANCESTOR(v)) >= 0) {
 114       squash(ANCESTOR(v));
 115
 116       if (SEMI(LABEL(ANCESTOR(v))) < SEMI(LABEL(v)))
 117          LABEL(v) = LABEL(ANCESTOR(v));
 118       ANCESTOR(v) = ANCESTOR(ANCESTOR(v));
 119    }
 120 }
 121
 122 int DominatorTree::eval(int v)
 123 {
 124    if (ANCESTOR(v) < 0)
 125       return v;
 126    squash(v);
 127    return LABEL(v);
 128 }
 129
 130 void DominatorTree::link(int v, int w)
 131 {
 132    ANCESTOR(w) = v;
 133 }
 134
 135 void DominatorTree::build()
 136 {
 137    DLList *bucket = new DLList[count];
 138    Node *nv, *nw;
 139    int p, u, v, w;
 140
 141    buildDFS(cfg->getRoot());
 142
 143    for (w = count - 1; w >= 1; --w) {
 144       nw = vert[w];
 145       assert(nw->tag == w);
 146       for (Graph::EdgeIterator ei = nw->incident(); !ei.end(); ei.next()) {
 147          nv = ei.getNode();
 148          v = nv->tag;
 149          u = eval(v);
 150          if (SEMI(u) < SEMI(w))
 151             SEMI(w) = SEMI(u);
 152       }
 153       p = PARENT(w);
 154       bucket[SEMI(w)].insert(nw);
 155       link(p, w);
 156
 157       for (DLList::Iterator it = bucket[p].iterator(); !it.end(); it.erase()) {
 158          v = reinterpret_cast<Node *>(it.get())->tag;
 159          u = eval(v);
 160          DOM(v) = (SEMI(u) < SEMI(v)) ? u : p;
 161       }
 162    }
 163    for (w = 1; w < count; ++w) {
 164       if (DOM(w) != SEMI(w))
 165          DOM(w) = DOM(DOM(w));
 166    }
 167    DOM(0) = 0;
 168
 169    insert(&BasicBlock::get(cfg->getRoot())->dom);
 170    do {
 171       p = 0;
 172       for (v = 1; v < count; ++v) {
 173          nw = &BasicBlock::get(vert[DOM(v)])->dom;;
 174          nv = &BasicBlock::get(vert[v])->dom;
 175          if (nw->getGraph() && !nv->getGraph()) {
 176             ++p;
 177             nw->attach(nv, Graph::Edge::TREE);
 178          }
 179       }
 180    } while (p);
 181
 182    delete[] bucket;
 183 }
 184
 185 #undef SEMI
 186 #undef ANCESTOR
 187 #undef PARENT
 188 #undef LABEL
 189 #undef DOM
 190
 191 void DominatorTree::findDominanceFrontiers()
 192 {
 193    Iterator *dtIter;
 194    BasicBlock *bb;
 195
 196    for (dtIter = this->iteratorDFS(false); !dtIter->end(); dtIter->next()) {
 197       EdgeIterator succIter, chldIter;
 198
 199       bb = BasicBlock::get(reinterpret_cast<Node *>(dtIter->get()));
 200       bb->getDF().clear();
 201
 202       for (succIter = bb->cfg.outgoing(); !succIter.end(); succIter.next()) {
 203          BasicBlock *dfLocal = BasicBlock::get(succIter.getNode());
 204          if (dfLocal->idom() != bb)
 205             bb->getDF().insert(dfLocal);
 206       }
 207
 208       for (chldIter = bb->dom.outgoing(); !chldIter.end(); chldIter.next()) {
 209          BasicBlock *cb = BasicBlock::get(chldIter.getNode());
 210
 211          DLList::Iterator dfIter = cb->getDF().iterator();
 212          for (; !dfIter.end(); dfIter.next()) {
 213             BasicBlock *dfUp = BasicBlock::get(dfIter);
 214             if (dfUp->idom() != bb)
 215                bb->getDF().insert(dfUp);
 216          }
 217       }
 218    }
 219    this->putIterator(dtIter);
 220 }
 221
 222 // liveIn(bb) = usedBeforeAssigned(bb) U (liveOut(bb) - assigned(bb))
 223 void
 224 Function::buildLiveSetsPreSSA(BasicBlock *bb, const int seq)
 225 {
 226    BitSet usedBeforeAssigned(allLValues.getSize(), true);
 227    BitSet assigned(allLValues.getSize(), true);
 228
 229    bb->liveSet.allocate(allLValues.getSize(), false);
 230
 231    int n = 0;
 232    for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
 233       BasicBlock *out = BasicBlock::get(ei.getNode());
 234       if (out == bb)
 235          continue;
 236       if (out->cfg.visit(seq))
 237          buildLiveSetsPreSSA(out, seq);
 238       if (!n++)
 239          bb->liveSet = out->liveSet;
 240       else
 241          bb->liveSet |= out->liveSet;
 242    }
 243    if (!n && !bb->liveSet.marker)
 244       bb->liveSet.fill(0);
 245    bb->liveSet.marker = true;
 246
 247    for (Instruction *i = bb->getEntry(); i; i = i->next) {
 248       for (int s = 0; i->srcExists(s); ++s)
 249          if (i->getSrc(s)->asLValue() && !assigned.test(i->getSrc(s)->id))
 250             usedBeforeAssigned.set(i->getSrc(s)->id);
 251       for (int d = 0; i->defExists(d); ++d)
 252          assigned.set(i->getDef(d)->id);
 253    }
 254
 255    bb->liveSet.andNot(assigned);
 256    bb->liveSet |= usedBeforeAssigned;
 257 }
 258
 259 class RenamePass
 260 {
 261 public:
 262    RenamePass(Function *);
 263    ~RenamePass();
 264
 265    bool run();
 266    void search(BasicBlock *);
 267
 268    inline LValue *getStackTop(Value *);
 269
 270 private:
 271    Stack *stack;
 272    Function *func;
 273    Program *prog;
 274    Instruction *undef;
 275 };
 276
 277 bool
 278 Program::convertToSSA()
 279 {
 280    for (ArrayList::Iterator fi = allFuncs.iterator(); !fi.end(); fi.next()) {
 281       Function *fn = reinterpret_cast<Function *>(fi.get());
 282       if (!fn->convertToSSA())
 283          return false;
 284    }
 285    return true;
 286 }
 287
 288 // XXX: add edge from entry to exit ?
 289
 290 // Efficiently Computing Static Single Assignment Form and
 291 //  the Control Dependence Graph,
 292 // R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck
 293 bool
 294 Function::convertToSSA()
 295 {
 296    // 0. calculate live in variables (for pruned SSA)
 297    int seq = cfg.nextSequence();
 298    for (unsigned i = 0; i <= loopNestingBound; seq = cfg.nextSequence(), ++i)
 299       buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), seq);
 300
 301    // reset liveSet marker for use in regalloc
 302    for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
 303       reinterpret_cast<BasicBlock *>(bi.get())->liveSet.marker = false;
 304
 305    // 1. create the dominator tree
 306    domTree = new DominatorTree(&cfg);
 307    reinterpret_cast<DominatorTree *>(domTree)->findDominanceFrontiers();
 308
 309    // 2. insert PHI functions
 310    DLList workList;
 311    LValue *lval;
 312    BasicBlock *bb;
 313    int var;
 314    int iterCount = 0;
 315    int *hasAlready = new int[allBBlocks.getSize() * 2];
 316    int *work = &hasAlready[allBBlocks.getSize()];
 317
 318    memset(hasAlready, 0, allBBlocks.getSize() * 2 * sizeof(int));
 319
 320    // for each variable
 321    for (var = 0; var < allLValues.getSize(); ++var) {
 322       if (!allLValues.get(var))
 323          continue;
 324       lval = reinterpret_cast<Value *>(allLValues.get(var))->asLValue();
 325       if (!lval || lval->defs.empty())
 326          continue;
 327       ++iterCount;
 328
 329       // TODO: don't add phi functions for values that aren't used outside
 330       //  the BB they're defined in
 331
 332       // gather blocks with assignments to lval in workList
 333       for (Value::DefIterator d = lval->defs.begin();
 334            d != lval->defs.end(); ++d) {
 335          bb = (*d)->getInsn()->bb;
 336          if (!bb)
 337             continue; // instruction likely been removed but not XXX deleted
 338
 339          if (work[bb->getId()] == iterCount)
 340             continue;
 341          work[bb->getId()] = iterCount;
 342          workList.insert(bb);
 343       }
 344
 345       // for each block in workList, insert a phi for lval in the block's
 346       //  dominance frontier (if we haven't already done so)
 347       for (DLList::Iterator wI = workList.iterator(); !wI.end(); wI.erase()) {
 348          bb = BasicBlock::get(wI);
 349
 350          DLList::Iterator dfIter = bb->getDF().iterator();
 351          for (; !dfIter.end(); dfIter.next()) {
 352             Instruction *phi;
 353             BasicBlock *dfBB = BasicBlock::get(dfIter);
 354
 355             if (hasAlready[dfBB->getId()] >= iterCount)
 356                continue;
 357             hasAlready[dfBB->getId()] = iterCount;
 358
 359             // pruned SSA: don't need a phi if the value is not live-in
 360             if (!dfBB->liveSet.test(lval->id))
 361                continue;
 362
 363             phi = new_Instruction(this, OP_PHI, typeOfSize(lval->reg.size));
 364             dfBB->insertTail(phi);
 365
 366             phi->setDef(0, lval);
 367             for (int s = 0; s < dfBB->cfg.incidentCount(); ++s)
 368                phi->setSrc(s, lval);
 369
 370             if (work[dfBB->getId()] < iterCount) {
 371                work[dfBB->getId()] = iterCount;
 372                wI.insert(dfBB);
 373             }
 374          }
 375       }
 376    }
 377    delete[] hasAlready;
 378
 379    RenamePass rename(this);
 380    return rename.run();
 381 }
 382
 383 RenamePass::RenamePass(Function *fn) : func(fn), prog(fn->getProgram())
 384 {
 385    BasicBlock *root = BasicBlock::get(func->cfg.getRoot());
 386
 387    undef = new_Instruction(func, OP_NOP, TYPE_U32);
 388    undef->setDef(0, new_LValue(func, FILE_GPR));
 389    root->insertHead(undef);
 390
 391    stack = new Stack[func->allLValues.getSize()];
 392 }
 393
 394 RenamePass::~RenamePass()
 395 {
 396    if (stack)
 397       delete[] stack;
 398 }
 399
 400 LValue *
 401 RenamePass::getStackTop(Value *val)
 402 {
 403    if (!stack[val->id].getSize())
 404       return 0;
 405    return reinterpret_cast<LValue *>(stack[val->id].peek().u.p);
 406 }
 407
 408 bool RenamePass::run()
 409 {
 410    if (!stack)
 411       return false;
 412    search(BasicBlock::get(func->domTree->getRoot()));
 413
 414    return true;
 415 }
 416
 417 void RenamePass::search(BasicBlock *bb)
 418 {
 419    LValue *lval;
 420    int d, s;
 421    const Target *targ = prog->getTarget();
 422
 423    for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) {
 424       if (stmt->op != OP_PHI) {
 425          for (s = 0; stmt->srcExists(s); ++s) {
 426             lval = stmt->getSrc(s)->asLValue();
 427             if (!lval)
 428                continue;
 429             lval = getStackTop(lval);
 430             if (!lval)
 431                lval = static_cast<LValue *>(undef->getDef(0));
 432             stmt->setSrc(s, lval);
 433          }
 434       }
 435       for (d = 0; stmt->defExists(d); ++d) {
 436          lval = stmt->def(d).get()->asLValue();
 437          assert(lval);
 438          stmt->def(d).setSSA(
 439             new_LValue(func, targ->nativeFile(lval->reg.file)));
 440          stmt->def(d).get()->reg.size = lval->reg.size;
 441          stmt->def(d).get()->reg.data.id = lval->reg.data.id;
 442          stack[lval->id].push(stmt->def(d).get());
 443       }
 444    }
 445
 446    for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
 447       Instruction *phi;
 448       int p = 0;
 449       BasicBlock *sb = BasicBlock::get(ei.getNode());
 450
 451       // which predecessor of sb is bb ?
 452       for (Graph::EdgeIterator ei = sb->cfg.incident(); !ei.end(); ei.next()) {
 453          if (ei.getNode() == &bb->cfg)
 454             break;
 455          ++p;
 456       }
 457       assert(p < sb->cfg.incidentCount());
 458
 459       for (phi = sb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) {
 460          lval = getStackTop(phi->getSrc(p));
 461          if (!lval)
 462             lval = undef->getDef(0)->asLValue();
 463          phi->setSrc(p, lval);
 464       }
 465    }
 466
 467    for (Graph::EdgeIterator ei = bb->dom.outgoing(); !ei.end(); ei.next())
 468       search(BasicBlock::get(ei.getNode()));
 469
 470    for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) {
 471       for (d = 0; stmt->defExists(d); ++d)
 472          stack[stmt->def(d).preSSA()->id].pop();
 473    }
 474 }
 475
 476 } // namespace nv50_ir