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