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
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 default:
540 assert(0);
541 break;
542 }
543 }
544 }
545
546 fprintf(out, "}\n");
547 fclose(out);
548 }
549
550 } // namespace nv50_ir
551