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 #include "codegen/nv50_ir_target.h" 25 26 namespace nv50_ir { 27 28 // Converts nv50 IR generated from TGSI to SSA form. 29 30 // DominatorTree implements an algorithm for finding immediate dominators, 31 // as described by T. Lengauer & R. Tarjan. 32 class DominatorTree : public Graph 33 { 34 public: 35 DominatorTree(Graph *cfg); 36 ~DominatorTree() { } 37 38 bool dominates(BasicBlock *, BasicBlock *); 39 40 void findDominanceFrontiers(); 41 42 private: 43 void build(); 44 void buildDFS(Node *); 45 46 void squash(int); 47 inline void link(int, int); 48 inline int eval(int); 49 50 void debugPrint(); 51 52 Graph *cfg; 53 54 Node **vert; 55 int *data; 56 const int count; 57 58 #define SEMI(i) (data[(i) + 0 * count]) 59 #define ANCESTOR(i) (data[(i) + 1 * count]) 60 #define PARENT(i) (data[(i) + 2 * count]) 61 #define LABEL(i) (data[(i) + 3 * count]) 62 #define DOM(i) (data[(i) + 4 * count]) 63 }; 64 65 void DominatorTree::debugPrint() 66 { 67 for (int i = 0; i < count; ++i) { 68 INFO("SEMI(%i) = %i\n", i, SEMI(i)); 69 INFO("ANCESTOR(%i) = %i\n", i, ANCESTOR(i)); 70 INFO("PARENT(%i) = %i\n", i, PARENT(i)); 71 INFO("LABEL(%i) = %i\n", i, LABEL(i)); 72 INFO("DOM(%i) = %i\n", i, DOM(i)); 73 } 74 } 75 76 DominatorTree::DominatorTree(Graph *cfgraph) : cfg(cfgraph), 77 count(cfg->getSize()) 78 { 79 int i = 0; 80 81 vert = new Node * [count]; 82 data = new int[5 * count]; 83 84 for (IteratorRef it = cfg->iteratorDFS(true); !it->end(); it->next(), ++i) { 85 vert[i] = reinterpret_cast<Node *>(it->get()); 86 vert[i]->tag = i; 87 LABEL(i) = i; 88 SEMI(i) = ANCESTOR(i) = -1; 89 } 90 assert(i == count); 91 92 build(); 93 94 delete[] vert; 95 delete[] data; 96 } 97 98 void DominatorTree::buildDFS(Graph::Node *node) 99 { 100 SEMI(node->tag) = node->tag; 101 102 for (Graph::EdgeIterator ei = node->outgoing(); !ei.end(); ei.next()) { 103 if (SEMI(ei.getNode()->tag) < 0) { 104 buildDFS(ei.getNode()); 105 PARENT(ei.getNode()->tag) = node->tag; 106 } 107 } 108 } 109 110 void DominatorTree::squash(int v) 111 { 112 if (ANCESTOR(ANCESTOR(v)) >= 0) { 113 squash(ANCESTOR(v)); 114 115 if (SEMI(LABEL(ANCESTOR(v))) < SEMI(LABEL(v))) 116 LABEL(v) = LABEL(ANCESTOR(v)); 117 ANCESTOR(v) = ANCESTOR(ANCESTOR(v)); 118 } 119 } 120 121 int DominatorTree::eval(int v) 122 { 123 if (ANCESTOR(v) < 0) 124 return v; 125 squash(v); 126 return LABEL(v); 127 } 128 129 void DominatorTree::link(int v, int w) 130 { 131 ANCESTOR(w) = v; 132 } 133 134 void DominatorTree::build() 135 { 136 DLList *bucket = new DLList[count]; 137 Node *nv, *nw; 138 int p, u, v, w; 139 140 buildDFS(cfg->getRoot()); 141 142 for (w = count - 1; w >= 1; --w) { 143 nw = vert[w]; 144 assert(nw->tag == w); 145 for (Graph::EdgeIterator ei = nw->incident(); !ei.end(); ei.next()) { 146 nv = ei.getNode(); 147 v = nv->tag; 148 u = eval(v); 149 if (SEMI(u) < SEMI(w)) 150 SEMI(w) = SEMI(u); 151 } 152 p = PARENT(w); 153 bucket[SEMI(w)].insert(nw); 154 link(p, w); 155 156 for (DLList::Iterator it = bucket[p].iterator(); !it.end(); it.erase()) { 157 v = reinterpret_cast<Node *>(it.get())->tag; 158 u = eval(v); 159 DOM(v) = (SEMI(u) < SEMI(v)) ? u : p; 160 } 161 } 162 for (w = 1; w < count; ++w) { 163 if (DOM(w) != SEMI(w)) 164 DOM(w) = DOM(DOM(w)); 165 } 166 DOM(0) = 0; 167 168 insert(&BasicBlock::get(cfg->getRoot())->dom); 169 do { 170 p = 0; 171 for (v = 1; v < count; ++v) { 172 nw = &BasicBlock::get(vert[DOM(v)])->dom; 173 nv = &BasicBlock::get(vert[v])->dom; 174 if (nw->getGraph() && !nv->getGraph()) { 175 ++p; 176 nw->attach(nv, Graph::Edge::TREE); 177 } 178 } 179 } while (p); 180 181 delete[] bucket; 182 } 183 184 #undef SEMI 185 #undef ANCESTOR 186 #undef PARENT 187 #undef LABEL 188 #undef DOM 189 190 void DominatorTree::findDominanceFrontiers() 191 { 192 BasicBlock *bb; 193 194 for (IteratorRef dtIt = iteratorDFS(false); !dtIt->end(); dtIt->next()) { 195 EdgeIterator succIt, chldIt; 196 197 bb = BasicBlock::get(reinterpret_cast<Node *>(dtIt->get())); 198 bb->getDF().clear(); 199 200 for (succIt = bb->cfg.outgoing(); !succIt.end(); succIt.next()) { 201 BasicBlock *dfLocal = BasicBlock::get(succIt.getNode()); 202 if (dfLocal->idom() != bb) 203 bb->getDF().insert(dfLocal); 204 } 205 206 for (chldIt = bb->dom.outgoing(); !chldIt.end(); chldIt.next()) { 207 BasicBlock *cb = BasicBlock::get(chldIt.getNode()); 208 209 DLList::Iterator dfIt = cb->getDF().iterator(); 210 for (; !dfIt.end(); dfIt.next()) { 211 BasicBlock *dfUp = BasicBlock::get(dfIt); 212 if (dfUp->idom() != bb) 213 bb->getDF().insert(dfUp); 214 } 215 } 216 } 217 } 218 219 // liveIn(bb) = usedBeforeAssigned(bb) U (liveOut(bb) - assigned(bb)) 220 void 221 Function::buildLiveSetsPreSSA(BasicBlock *bb, const int seq) 222 { 223 Function *f = bb->getFunction(); 224 BitSet usedBeforeAssigned(allLValues.getSize(), true); 225 BitSet assigned(allLValues.getSize(), true); 226 227 bb->liveSet.allocate(allLValues.getSize(), false); 228 229 int n = 0; 230 for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 231 BasicBlock *out = BasicBlock::get(ei.getNode()); 232 if (out == bb) 233 continue; 234 if (out->cfg.visit(seq)) 235 buildLiveSetsPreSSA(out, seq); 236 if (!n++) 237 bb->liveSet = out->liveSet; 238 else 239 bb->liveSet |= out->liveSet; 240 } 241 if (!n && !bb->liveSet.marker) 242 bb->liveSet.fill(0); 243 bb->liveSet.marker = true; 244 245 for (Instruction *i = bb->getEntry(); i; i = i->next) { 246 for (int s = 0; i->srcExists(s); ++s) 247 if (i->getSrc(s)->asLValue() && !assigned.test(i->getSrc(s)->id)) 248 usedBeforeAssigned.set(i->getSrc(s)->id); 249 for (int d = 0; i->defExists(d); ++d) 250 assigned.set(i->getDef(d)->id); 251 } 252 253 if (bb == BasicBlock::get(f->cfgExit)) { 254 for (std::deque<ValueRef>::iterator it = f->outs.begin(); 255 it != f->outs.end(); ++it) { 256 if (!assigned.test(it->get()->id)) 257 usedBeforeAssigned.set(it->get()->id); 258 } 259 } 260 261 bb->liveSet.andNot(assigned); 262 bb->liveSet |= usedBeforeAssigned; 263 } 264 265 void 266 Function::buildDefSetsPreSSA(BasicBlock *bb, const int seq) 267 { 268 bb->defSet.allocate(allLValues.getSize(), !bb->liveSet.marker); 269 bb->liveSet.marker = true; 270 271 for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) { 272 BasicBlock *in = BasicBlock::get(ei.getNode()); 273 274 if (in->cfg.visit(seq)) 275 buildDefSetsPreSSA(in, seq); 276 277 bb->defSet |= in->defSet; 278 } 279 280 for (Instruction *i = bb->getEntry(); i; i = i->next) { 281 for (int d = 0; i->defExists(d); ++d) 282 bb->defSet.set(i->getDef(d)->id); 283 } 284 } 285 286 class RenamePass 287 { 288 public: 289 RenamePass(Function *); 290 ~RenamePass(); 291 292 bool run(); 293 void search(BasicBlock *); 294 295 inline LValue *getStackTop(Value *); 296 297 LValue *mkUndefined(Value *); 298 299 private: 300 Stack *stack; 301 Function *func; 302 Program *prog; 303 }; 304 305 bool 306 Program::convertToSSA() 307 { 308 for (ArrayList::Iterator fi = allFuncs.iterator(); !fi.end(); fi.next()) { 309 Function *fn = reinterpret_cast<Function *>(fi.get()); 310 if (!fn->convertToSSA()) 311 return false; 312 } 313 return true; 314 } 315 316 // XXX: add edge from entry to exit ? 317 318 // Efficiently Computing Static Single Assignment Form and 319 // the Control Dependence Graph, 320 // R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, F. K. Zadeck 321 bool 322 Function::convertToSSA() 323 { 324 // 0. calculate live in variables (for pruned SSA) 325 buildLiveSets(); 326 327 // 1. create the dominator tree 328 domTree = new DominatorTree(&cfg); 329 reinterpret_cast<DominatorTree *>(domTree)->findDominanceFrontiers(); 330 331 // 2. insert PHI functions 332 DLList workList; 333 LValue *lval; 334 BasicBlock *bb; 335 int var; 336 int iterCount = 0; 337 int *hasAlready = new int[allBBlocks.getSize() * 2]; 338 int *work = &hasAlready[allBBlocks.getSize()]; 339 340 memset(hasAlready, 0, allBBlocks.getSize() * 2 * sizeof(int)); 341 342 // for each variable 343 for (var = 0; var < allLValues.getSize(); ++var) { 344 if (!allLValues.get(var)) 345 continue; 346 lval = reinterpret_cast<Value *>(allLValues.get(var))->asLValue(); 347 if (!lval || lval->defs.empty()) 348 continue; 349 ++iterCount; 350 351 // TODO: don't add phi functions for values that aren't used outside 352 // the BB they're defined in 353 354 // gather blocks with assignments to lval in workList 355 for (Value::DefIterator d = lval->defs.begin(); 356 d != lval->defs.end(); ++d) { 357 bb = ((*d)->getInsn() ? (*d)->getInsn()->bb : NULL); 358 if (!bb) 359 continue; // instruction likely been removed but not XXX deleted 360 361 if (work[bb->getId()] == iterCount) 362 continue; 363 work[bb->getId()] = iterCount; 364 workList.insert(bb); 365 } 366 367 // for each block in workList, insert a phi for lval in the block's 368 // dominance frontier (if we haven't already done so) 369 for (DLList::Iterator wI = workList.iterator(); !wI.end(); wI.erase()) { 370 bb = BasicBlock::get(wI); 371 372 DLList::Iterator dfIter = bb->getDF().iterator(); 373 for (; !dfIter.end(); dfIter.next()) { 374 Instruction *phi; 375 BasicBlock *dfBB = BasicBlock::get(dfIter); 376 377 if (hasAlready[dfBB->getId()] >= iterCount) 378 continue; 379 hasAlready[dfBB->getId()] = iterCount; 380 381 // pruned SSA: don't need a phi if the value is not live-in 382 if (!dfBB->liveSet.test(lval->id)) 383 continue; 384 385 phi = new_Instruction(this, OP_PHI, typeOfSize(lval->reg.size)); 386 dfBB->insertTail(phi); 387 388 phi->setDef(0, lval); 389 for (int s = 0; s < dfBB->cfg.incidentCount(); ++s) 390 phi->setSrc(s, lval); 391 392 if (work[dfBB->getId()] < iterCount) { 393 work[dfBB->getId()] = iterCount; 394 wI.insert(dfBB); 395 } 396 } 397 } 398 } 399 delete[] hasAlready; 400 401 RenamePass rename(this); 402 return rename.run(); 403 } 404 405 RenamePass::RenamePass(Function *fn) : func(fn), prog(fn->getProgram()) 406 { 407 stack = new Stack[func->allLValues.getSize()]; 408 } 409 410 RenamePass::~RenamePass() 411 { 412 if (stack) 413 delete[] stack; 414 } 415 416 LValue * 417 RenamePass::getStackTop(Value *val) 418 { 419 if (!stack[val->id].getSize()) 420 return 0; 421 return reinterpret_cast<LValue *>(stack[val->id].peek().u.p); 422 } 423 424 LValue * 425 RenamePass::mkUndefined(Value *val) 426 { 427 LValue *lval = val->asLValue(); 428 assert(lval); 429 LValue *ud = new_LValue(func, lval); 430 Instruction *nop = new_Instruction(func, OP_NOP, typeOfSize(lval->reg.size)); 431 nop->setDef(0, ud); 432 BasicBlock::get(func->cfg.getRoot())->insertHead(nop); 433 return ud; 434 } 435 436 bool RenamePass::run() 437 { 438 if (!stack) 439 return false; 440 search(BasicBlock::get(func->domTree->getRoot())); 441 442 return true; 443 } 444 445 // Go through BBs in dominance order, create new values for each definition, 446 // and replace all sources with their current new values. 447 // 448 // NOTE: The values generated for function inputs/outputs have no connection 449 // to their corresponding outputs/inputs in other functions. Only allocation 450 // of physical registers will establish this connection. 451 // 452 void RenamePass::search(BasicBlock *bb) 453 { 454 LValue *lval, *ssa; 455 int d, s; 456 const Target *targ = prog->getTarget(); 457 458 // Put current definitions for function inputs values on the stack. 459 // They can be used before any redefinitions are pushed. 460 if (bb == BasicBlock::get(func->cfg.getRoot())) { 461 for (std::deque<ValueDef>::iterator it = func->ins.begin(); 462 it != func->ins.end(); ++it) { 463 lval = it->get()->asLValue(); 464 assert(lval); 465 466 ssa = new_LValue(func, targ->nativeFile(lval->reg.file)); 467 ssa->reg.size = lval->reg.size; 468 ssa->reg.data.id = lval->reg.data.id; 469 470 it->setSSA(ssa); 471 stack[lval->id].push(ssa); 472 } 473 } 474 475 for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) { 476 // PHI sources get definitions from the passes through the incident BBs, 477 // so skip them here. 478 if (stmt->op != OP_PHI) { 479 for (s = 0; stmt->srcExists(s); ++s) { 480 lval = stmt->getSrc(s)->asLValue(); 481 if (!lval) 482 continue; 483 // Values on the stack created in previously visited blocks, and 484 // function inputs, will be valid because they dominate this one. 485 lval = getStackTop(lval); 486 if (!lval) 487 lval = mkUndefined(stmt->getSrc(s)); 488 stmt->setSrc(s, lval); 489 } 490 } 491 for (d = 0; stmt->defExists(d); ++d) { 492 lval = stmt->def(d).get()->asLValue(); 493 assert(lval); 494 stmt->def(d).setSSA( 495 new_LValue(func, targ->nativeFile(lval->reg.file))); 496 stmt->def(d).get()->reg.size = lval->reg.size; 497 stmt->def(d).get()->reg.data.id = lval->reg.data.id; 498 stack[lval->id].push(stmt->def(d).get()); 499 } 500 } 501 502 // Update sources of PHI ops corresponding to this BB in outgoing BBs. 503 for (Graph::EdgeIterator ei = bb->cfg.outgoing(); !ei.end(); ei.next()) { 504 Instruction *phi; 505 int p = 0; 506 BasicBlock *sb = BasicBlock::get(ei.getNode()); 507 508 // which predecessor of sb is bb ? 509 for (Graph::EdgeIterator ei = sb->cfg.incident(); !ei.end(); ei.next()) { 510 if (ei.getNode() == &bb->cfg) 511 break; 512 ++p; 513 } 514 assert(p < sb->cfg.incidentCount()); 515 516 for (phi = sb->getPhi(); phi && phi->op == OP_PHI; phi = phi->next) { 517 lval = getStackTop(phi->getSrc(p)); 518 if (!lval) 519 lval = mkUndefined(phi->getSrc(p)); 520 phi->setSrc(p, lval); 521 } 522 } 523 524 // Visit the BBs we dominate. 525 for (Graph::EdgeIterator ei = bb->dom.outgoing(); !ei.end(); ei.next()) 526 search(BasicBlock::get(ei.getNode())); 527 528 // Update function outputs to the last definitions of their pre-SSA values. 529 // I hope they're unique, i.e. that we get PHIs for all of them ... 530 if (bb == BasicBlock::get(func->cfgExit)) { 531 for (std::deque<ValueRef>::iterator it = func->outs.begin(); 532 it != func->outs.end(); ++it) { 533 lval = it->get()->asLValue(); 534 if (!lval) 535 continue; 536 lval = getStackTop(lval); 537 if (!lval) 538 lval = mkUndefined(it->get()); 539 it->set(lval); 540 } 541 } 542 543 // Pop the values we created in this block from the stack because we will 544 // return to blocks that we do not dominate. 545 for (Instruction *stmt = bb->getFirst(); stmt; stmt = stmt->next) { 546 if (stmt->op == OP_NOP) 547 continue; 548 for (d = 0; stmt->defExists(d); ++d) 549 stack[stmt->def(d).preSSA()->id].pop(); 550 } 551 } 552 553 } // namespace nv50_ir 554