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