• 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 
25 namespace nv50_ir {
26 
Function(Program * p,const char * fnName,uint32_t label)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 
~Function()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 
BasicBlock(Function * fn)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 
~BasicBlock()89 BasicBlock::~BasicBlock()
90 {
91    // nothing yet
92 }
93 
94 BasicBlock *
clone(ClonePolicy<Function> & pol) const95 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 *
idom() const115 BasicBlock::idom() const
116 {
117    Graph::Node *dn = dom.parent();
118    return dn ? BasicBlock::get(dn) : NULL;
119 }
120 
121 void
insertHead(Instruction * inst)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
insertTail(Instruction * inst)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
insertBefore(Instruction * q,Instruction * p)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
insertAfter(Instruction * p,Instruction * q)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
remove(Instruction * insn)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 
permuteAdjacent(Instruction * a,Instruction * b)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
splitCommon(Instruction * insn,BasicBlock * bb,bool attach)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 *
splitBefore(Instruction * insn,bool attach)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 *
splitAfter(Instruction * insn,bool attach)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
dominatedBy(BasicBlock * that)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
initiatesSimpleConditional() const368 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
setEntry(BasicBlock * bb)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
setExit(BasicBlock * bb)408 Function::setExit(BasicBlock *bb)
409 {
410    if (cfgExit)
411       return false;
412    cfgExit = &bb->cfg;
413    return true;
414 }
415 
416 unsigned int
orderInstructions(ArrayList & result)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
buildLiveSets()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
buildDefSets()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
run(Program * prog,bool ordered,bool skipPhi)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
doRun(Program * prog,bool ordered,bool skipPhi)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
run(Function * func,bool ordered,bool skipPhi)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
doRun(Function * func,bool ordered,bool skipPhi)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
printCFGraph(const char * filePath)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          case Graph::Edge::DUMMY:
540             fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB);
541             break;
542          default:
543             assert(0);
544             break;
545          }
546       }
547    }
548 
549    fprintf(out, "}\n");
550    fclose(out);
551 }
552 
553 } // namespace nv50_ir
554