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 "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   // 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
74BasicBlock::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
89BasicBlock::~BasicBlock()
90{
91   // nothing yet
92}
93
94BasicBlock *
95BasicBlock::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
114BasicBlock *
115BasicBlock::idom() const
116{
117   Graph::Node *dn = dom.parent();
118   return dn ? BasicBlock::get(dn) : NULL;
119}
120
121void
122BasicBlock::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
155void
156BasicBlock::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
185void
186BasicBlock::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
215void
216BasicBlock::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
238void
239BasicBlock::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
270void 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
298void
299BasicBlock::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
329BasicBlock *
330BasicBlock::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
342BasicBlock *
343BasicBlock::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
355bool
356BasicBlock::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
367unsigned int
368BasicBlock::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
398bool
399Function::setEntry(BasicBlock *bb)
400{
401   if (cfg.getRoot())
402      return false;
403   cfg.insert(&bb->cfg);
404   return true;
405}
406
407bool
408Function::setExit(BasicBlock *bb)
409{
410   if (cfgExit)
411      return false;
412   cfgExit = &bb->cfg;
413   return true;
414}
415
416unsigned int
417Function::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
432void
433Function::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
442void
443Function::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
452bool
453Pass::run(Program *prog, bool ordered, bool skipPhi)
454{
455   this->prog = prog;
456   err = false;
457   return doRun(prog, ordered, skipPhi);
458}
459
460bool
461Pass::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
472bool
473Pass::run(Function *func, bool ordered, bool skipPhi)
474{
475   prog = func->getProgram();
476   err = false;
477   return doRun(func, ordered, skipPhi);
478}
479
480bool
481Pass::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
508void
509Function::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         default:
540            assert(0);
541            break;
542         }
543      }
544   }
545
546   fprintf(out, "}\n");
547   fclose(out);
548}
549
550} // namespace nv50_ir
551