• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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);
~DominatorTree()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 
debugPrint()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 
DominatorTree(Graph * cfgraph)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 
buildDFS(Graph::Node * node)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 
squash(int v)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 
eval(int v)121 int DominatorTree::eval(int v)
122 {
123    if (ANCESTOR(v) < 0)
124       return v;
125    squash(v);
126    return LABEL(v);
127 }
128 
link(int v,int w)129 void DominatorTree::link(int v, int w)
130 {
131    ANCESTOR(w) = v;
132 }
133 
build()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 
findDominanceFrontiers()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
buildLiveSetsPreSSA(BasicBlock * bb,const int seq)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
buildDefSetsPreSSA(BasicBlock * bb,const int seq)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
convertToSSA()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
convertToSSA()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 
RenamePass(Function * fn)405 RenamePass::RenamePass(Function *fn) : func(fn), prog(fn->getProgram())
406 {
407    stack = new Stack[func->allLValues.getSize()];
408 }
409 
~RenamePass()410 RenamePass::~RenamePass()
411 {
412    if (stack)
413       delete[] stack;
414 }
415 
416 LValue *
getStackTop(Value * val)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 *
mkUndefined(Value * val)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 
run()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 //
search(BasicBlock * bb)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
554