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
25namespace nv50_ir {
26
27Function::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
51Function::~Function()
52{
53   prog->del(this, id);
54
55   if (domTree)
56      delete domTree;
57   if (bbArray)
58      delete[] bbArray;
59
60   for (ArrayList::Iterator it = allInsns.iterator(); !it.end(); it.next())
61      delete_Instruction(prog, reinterpret_cast<Instruction *>(it.get()));
62
63   for (ArrayList::Iterator it = allLValues.iterator(); !it.end(); it.next())
64      delete_Value(prog, reinterpret_cast<LValue *>(it.get()));
65
66   for (ArrayList::Iterator BBs = allBBlocks.iterator(); !BBs.end(); BBs.next())
67      delete reinterpret_cast<BasicBlock *>(BBs.get());
68}
69
70BasicBlock::BasicBlock(Function *fn) : cfg(this), dom(this), func(fn)
71{
72   program = func->getProgram();
73
74   joinAt = phi = entry = exit = NULL;
75
76   numInsns = 0;
77   binPos = 0;
78   binSize = 0;
79
80   explicitCont = false;
81
82   func->add(this, this->id);
83}
84
85BasicBlock::~BasicBlock()
86{
87   // nothing yet
88}
89
90BasicBlock *
91BasicBlock::clone(ClonePolicy<Function>& pol) const
92{
93   BasicBlock *bb = new BasicBlock(pol.context());
94
95   pol.set(this, bb);
96
97   for (Instruction *i = getFirst(); i; i = i->next)
98      bb->insertTail(i->clone(pol));
99
100   pol.context()->cfg.insert(&bb->cfg);
101
102   for (Graph::EdgeIterator it = cfg.outgoing(); !it.end(); it.next()) {
103      BasicBlock *obb = BasicBlock::get(it.getNode());
104      bb->cfg.attach(&pol.get(obb)->cfg, it.getType());
105   }
106
107   return bb;
108}
109
110BasicBlock *
111BasicBlock::idom() const
112{
113   Graph::Node *dn = dom.parent();
114   return dn ? BasicBlock::get(dn) : NULL;
115}
116
117void
118BasicBlock::insertHead(Instruction *inst)
119{
120   assert(inst->next == 0 && inst->prev == 0);
121
122   if (inst->op == OP_PHI) {
123      if (phi) {
124         insertBefore(phi, inst);
125      } else {
126         if (entry) {
127            insertBefore(entry, inst);
128         } else {
129            assert(!exit);
130            phi = exit = inst;
131            inst->bb = this;
132            ++numInsns;
133         }
134      }
135   } else {
136      if (entry) {
137         insertBefore(entry, inst);
138      } else {
139         if (phi) {
140            insertAfter(exit, inst); // after last phi
141         } else {
142            assert(!exit);
143            entry = exit = inst;
144            inst->bb = this;
145            ++numInsns;
146         }
147      }
148   }
149}
150
151void
152BasicBlock::insertTail(Instruction *inst)
153{
154   assert(inst->next == 0 && inst->prev == 0);
155
156   if (inst->op == OP_PHI) {
157      if (entry) {
158         insertBefore(entry, inst);
159      } else
160      if (exit) {
161         assert(phi);
162         insertAfter(exit, inst);
163      } else {
164         assert(!phi);
165         phi = exit = inst;
166         inst->bb = this;
167         ++numInsns;
168      }
169   } else {
170      if (exit) {
171         insertAfter(exit, inst);
172      } else {
173         assert(!phi);
174         entry = exit = inst;
175         inst->bb = this;
176         ++numInsns;
177      }
178   }
179}
180
181void
182BasicBlock::insertBefore(Instruction *q, Instruction *p)
183{
184   assert(p && q);
185
186   assert(p->next == 0 && p->prev == 0);
187
188   if (q == entry) {
189      if (p->op == OP_PHI) {
190         if (!phi)
191            phi = p;
192      } else {
193         entry = p;
194      }
195   } else
196   if (q == phi) {
197      assert(p->op == OP_PHI);
198      phi = p;
199   }
200
201   p->next = q;
202   p->prev = q->prev;
203   if (p->prev)
204      p->prev->next = p;
205   q->prev = p;
206
207   p->bb = this;
208   ++numInsns;
209}
210
211void
212BasicBlock::insertAfter(Instruction *p, Instruction *q)
213{
214   assert(p && q);
215   assert(q->op != OP_PHI || p->op == OP_PHI);
216
217   assert(q->next == 0 && q->prev == 0);
218
219   if (p == exit)
220      exit = q;
221   if (p->op == OP_PHI && q->op != OP_PHI)
222      entry = q;
223
224   q->prev = p;
225   q->next = p->next;
226   if (q->next)
227      q->next->prev = q;
228   p->next = q;
229
230   q->bb = this;
231   ++numInsns;
232}
233
234void
235BasicBlock::remove(Instruction *insn)
236{
237   assert(insn->bb == this);
238
239   if (insn->prev)
240      insn->prev->next = insn->next;
241
242   if (insn->next)
243      insn->next->prev = insn->prev;
244   else
245      exit = insn->prev;
246
247   if (insn == entry) {
248      if (insn->next)
249         entry = insn->next;
250      else
251      if (insn->prev && insn->prev->op != OP_PHI)
252         entry = insn->prev;
253      else
254         entry = NULL;
255   }
256
257   if (insn == phi)
258      phi = (insn->next && insn->next->op == OP_PHI) ? insn->next : 0;
259
260   --numInsns;
261   insn->bb = NULL;
262   insn->next =
263   insn->prev = NULL;
264}
265
266void BasicBlock::permuteAdjacent(Instruction *a, Instruction *b)
267{
268   assert(a->bb == b->bb);
269
270   if (a->next != b) {
271      Instruction *i = a;
272      a = b;
273      b = i;
274   }
275   assert(a->next == b);
276   assert(a->op != OP_PHI && b->op != OP_PHI);
277
278   if (b == exit)
279      exit = a;
280   if (a == entry)
281      entry = b;
282
283   b->prev = a->prev;
284   a->next = b->next;
285   b->next = a;
286   a->prev = b;
287
288   if (b->prev)
289      b->prev->next = b;
290   if (a->prev)
291      a->next->prev = a;
292}
293
294void
295BasicBlock::splitCommon(Instruction *insn, BasicBlock *bb, bool attach)
296{
297   bb->entry = insn;
298
299   if (insn) {
300      exit = insn->prev;
301      insn->prev = NULL;
302   }
303
304   if (exit)
305      exit->next = NULL;
306   else
307      entry = NULL;
308
309   while (!cfg.outgoing(true).end()) {
310      Graph::Edge *e = cfg.outgoing(true).getEdge();
311      bb->cfg.attach(e->getTarget(), e->getType());
312      this->cfg.detach(e->getTarget());
313   }
314
315   for (; insn; insn = insn->next) {
316      this->numInsns--;
317      bb->numInsns++;
318      insn->bb = bb;
319      bb->exit = insn;
320   }
321   if (attach)
322      this->cfg.attach(&bb->cfg, Graph::Edge::TREE);
323}
324
325BasicBlock *
326BasicBlock::splitBefore(Instruction *insn, bool attach)
327{
328   BasicBlock *bb = new BasicBlock(func);
329   assert(!insn || insn->op != OP_PHI);
330
331   splitCommon(insn, bb, attach);
332   return bb;
333}
334
335BasicBlock *
336BasicBlock::splitAfter(Instruction *insn, bool attach)
337{
338   BasicBlock *bb = new BasicBlock(func);
339   assert(!insn || insn->op != OP_PHI);
340
341   bb->joinAt = joinAt;
342   joinAt = NULL;
343
344   splitCommon(insn ? insn->next : NULL, bb, attach);
345   return bb;
346}
347
348bool
349BasicBlock::dominatedBy(BasicBlock *that)
350{
351   Graph::Node *bn = &that->dom;
352   Graph::Node *dn = &this->dom;
353
354   while (dn && dn != bn)
355      dn = dn->parent();
356
357   return dn != NULL;
358}
359
360unsigned int
361BasicBlock::initiatesSimpleConditional() const
362{
363   Graph::Node *out[2];
364   int n;
365   Graph::Edge::Type eR;
366
367   if (cfg.outgoingCount() != 2) // -> if and -> else/endif
368      return false;
369
370   n = 0;
371   for (Graph::EdgeIterator ei = cfg.outgoing(); !ei.end(); ei.next())
372      out[n++] = ei.getNode();
373   eR = out[1]->outgoing().getType();
374
375   // IF block is out edge to the right
376   if (eR == Graph::Edge::CROSS || eR == Graph::Edge::BACK)
377      return 0x2;
378
379   if (out[1]->outgoingCount() != 1) // 0 is IF { RET; }, >1 is more divergence
380      return 0x0;
381   // do they reconverge immediately ?
382   if (out[1]->outgoing().getNode() == out[0])
383      return 0x1;
384   if (out[0]->outgoingCount() == 1)
385      if (out[0]->outgoing().getNode() == out[1]->outgoing().getNode())
386         return 0x3;
387
388   return 0x0;
389}
390
391bool
392Function::setEntry(BasicBlock *bb)
393{
394   if (cfg.getRoot())
395      return false;
396   cfg.insert(&bb->cfg);
397   return true;
398}
399
400bool
401Function::setExit(BasicBlock *bb)
402{
403   if (cfgExit)
404      return false;
405   cfgExit = &bb->cfg;
406   return true;
407}
408
409unsigned int
410Function::orderInstructions(ArrayList &result)
411{
412   result.clear();
413
414   for (IteratorRef it = cfg.iteratorCFG(); !it->end(); it->next()) {
415      BasicBlock *bb =
416         BasicBlock::get(reinterpret_cast<Graph::Node *>(it->get()));
417
418      for (Instruction *insn = bb->getFirst(); insn; insn = insn->next)
419         result.insert(insn, insn->serial);
420   }
421
422   return result.getSize();
423}
424
425void
426Function::buildLiveSets()
427{
428   for (unsigned i = 0; i <= loopNestingBound; ++i)
429      buildLiveSetsPreSSA(BasicBlock::get(cfg.getRoot()), cfg.nextSequence());
430
431   for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
432      BasicBlock::get(bi)->liveSet.marker = false;
433}
434
435void
436Function::buildDefSets()
437{
438   for (unsigned i = 0; i <= loopNestingBound; ++i)
439      buildDefSetsPreSSA(BasicBlock::get(cfgExit), cfg.nextSequence());
440
441   for (ArrayList::Iterator bi = allBBlocks.iterator(); !bi.end(); bi.next())
442      BasicBlock::get(bi)->liveSet.marker = false;
443}
444
445bool
446Pass::run(Program *prog, bool ordered, bool skipPhi)
447{
448   this->prog = prog;
449   err = false;
450   return doRun(prog, ordered, skipPhi);
451}
452
453bool
454Pass::doRun(Program *prog, bool ordered, bool skipPhi)
455{
456   for (IteratorRef it = prog->calls.iteratorDFS(false);
457        !it->end(); it->next()) {
458      Graph::Node *n = reinterpret_cast<Graph::Node *>(it->get());
459      if (!doRun(Function::get(n), ordered, skipPhi))
460         return false;
461   }
462   return !err;
463}
464
465bool
466Pass::run(Function *func, bool ordered, bool skipPhi)
467{
468   prog = func->getProgram();
469   err = false;
470   return doRun(func, ordered, skipPhi);
471}
472
473bool
474Pass::doRun(Function *func, bool ordered, bool skipPhi)
475{
476   IteratorRef bbIter;
477   BasicBlock *bb;
478   Instruction *insn, *next;
479
480   this->func = func;
481   if (!visit(func))
482      return false;
483
484   bbIter = ordered ? func->cfg.iteratorCFG() : func->cfg.iteratorDFS();
485
486   for (; !bbIter->end(); bbIter->next()) {
487      bb = BasicBlock::get(reinterpret_cast<Graph::Node *>(bbIter->get()));
488      if (!visit(bb))
489         break;
490      for (insn = skipPhi ? bb->getEntry() : bb->getFirst(); insn != NULL;
491           insn = next) {
492         next = insn->next;
493         if (!visit(insn))
494            break;
495      }
496   }
497
498   return !err;
499}
500
501void
502Function::printCFGraph(const char *filePath)
503{
504   FILE *out = fopen(filePath, "a");
505   if (!out) {
506      ERROR("failed to open file: %s\n", filePath);
507      return;
508   }
509   INFO("printing control flow graph to: %s\n", filePath);
510
511   fprintf(out, "digraph G {\n");
512
513   for (IteratorRef it = cfg.iteratorDFS(); !it->end(); it->next()) {
514      BasicBlock *bb = BasicBlock::get(
515         reinterpret_cast<Graph::Node *>(it->get()));
516      int idA = bb->getId();
517      for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) {
518         int idB = BasicBlock::get(ei.getNode())->getId();
519         switch (ei.getType()) {
520         case Graph::Edge::TREE:
521            fprintf(out, "\t%i -> %i;\n", idA, idB);
522            break;
523         case Graph::Edge::FORWARD:
524            fprintf(out, "\t%i -> %i [color=green];\n", idA, idB);
525            break;
526         case Graph::Edge::CROSS:
527            fprintf(out, "\t%i -> %i [color=red];\n", idA, idB);
528            break;
529         case Graph::Edge::BACK:
530            fprintf(out, "\t%i -> %i;\n", idA, idB);
531            break;
532         case Graph::Edge::DUMMY:
533            fprintf(out, "\t%i -> %i [style=dotted];\n", idA, idB);
534            break;
535         default:
536            assert(0);
537            break;
538         }
539      }
540   }
541
542   fprintf(out, "}\n");
543   fclose(out);
544}
545
546} // namespace nv50_ir
547