| 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 |
#include "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 |
unsigned 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 |