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 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 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 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 89 BasicBlock::~BasicBlock() 90 { 91 // nothing yet 92 } 93 94 BasicBlock * 95 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 * 115 BasicBlock::idom() const 116 { 117 Graph::Node *dn = dom.parent(); 118 return dn ? BasicBlock::get(dn) : NULL; 119 } 120 121 void 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 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 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 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 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 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 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 * 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 * 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 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 368 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 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 408 Function::setExit(BasicBlock *bb) 409 { 410 if (cfgExit) 411 return false; 412 cfgExit = &bb->cfg; 413 return true; 414 } 415 416 unsigned int 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 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 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 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 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 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 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 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