Previously, a phi node's sources were implicitly ordered by the inbound edge order. This changes that so that a phi node instead has a basic block stored for each source in a deque.
Signed-off-by: Rhys Perry <[email protected]> --- src/gallium/drivers/nouveau/codegen/nv50_ir.cpp | 20 +++++- src/gallium/drivers/nouveau/codegen/nv50_ir.h | 9 ++- .../drivers/nouveau/codegen/nv50_ir_print.cpp | 2 + src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp | 73 ++++++---------------- .../drivers/nouveau/codegen/nv50_ir_ssa.cpp | 7 ++- 5 files changed, 50 insertions(+), 61 deletions(-) diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp index d28022fce5..07a5325cbe 100644 --- a/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp +++ b/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp @@ -1132,12 +1132,21 @@ PhiInstruction::clone(ClonePolicy<Function>& pol, BaseInstruction *i) const new_PhiInstruction(pol.context(), dType)); BaseInstruction::clone(pol, phi); + phi->basicBlocks.resize(basicBlocks.size()); + for (size_t i = 0; i < basicBlocks.size(); i++) + phi->basicBlocks[i] = basicBlocks[i]; return phi; } +BasicBlock * +PhiInstruction::getBB(int s) const +{ + return s >= (int)basicBlocks.size() ? NULL : basicBlocks[s]; +} + void -PhiInstruction::setSrc(int s, Value *val) +PhiInstruction::setSrcBB(int s, Value *val, BasicBlock *bb) { int size = srcs.size(); if (s >= size) { @@ -1146,13 +1155,18 @@ PhiInstruction::setSrc(int s, Value *val) srcs[size++].setInsn(this); } + size = basicBlocks.size(); + if (s >= size) + basicBlocks.resize(s + 1); + srcs[s].set(val); + basicBlocks[s] = bb; } void -PhiInstruction::setSrc(int s, const ValueRef& ref) +PhiInstruction::setSrcBB(int s, const ValueRef& ref, BasicBlock *bb) { - setSrc(s, ref.get()); + setSrcBB(s, ref.get(), bb); srcs[s].mod = ref.mod; } diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir.h b/src/gallium/drivers/nouveau/codegen/nv50_ir.h index b80397a0b9..1eb9fa7bb2 100644 --- a/src/gallium/drivers/nouveau/codegen/nv50_ir.h +++ b/src/gallium/drivers/nouveau/codegen/nv50_ir.h @@ -870,8 +870,13 @@ public: virtual PhiInstruction *clone(ClonePolicy<Function>&, BaseInstruction * = NULL) const; - void setSrc(int s, Value *); - void setSrc(int s, const ValueRef&); + BasicBlock *getBB(int s) const; + + void setSrcBB(int s, Value *, BasicBlock *); + void setSrcBB(int s, const ValueRef&, BasicBlock *); + +private: + std::deque<BasicBlock *> basicBlocks; }; class Instruction : public BaseInstruction diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_print.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_print.cpp index 29e45b7ebf..e4b6b68b56 100644 --- a/src/gallium/drivers/nouveau/codegen/nv50_ir_print.cpp +++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_print.cpp @@ -678,6 +678,8 @@ void BaseInstruction::print() const getIndirect(s, 1)); else pos += getSrc(s)->print(&buf[pos], BUFSZ - pos, sType); + if (op == OP_PHI) + PRINT("%s(BB:%i)", colour[TXT_INSN], asPhi(this)->getBB(s)->getId()); } if (i && i->exit) PRINT("%s exit", colour[TXT_INSN]); diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp index 26cbe20fb4..80f83c88c9 100644 --- a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp +++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp @@ -372,20 +372,13 @@ typedef unordered_map< std::pair<PhiInstruction *, BasicBlock *>, Value *, PhiMapHash> PhiMap; // Critical edges need to be split up so that work can be inserted along -// specific edge transitions. Unfortunately manipulating incident edges into a -// BB invalidates all the PHI nodes since their sources are implicitly ordered -// by incident edge order. -// -// TODO: Make it so that that is not the case, and PHI nodes store pointers to -// the original BBs. +// specific edge transitions. void RegAlloc::PhiMovesPass::splitEdges(BasicBlock *bb) { BasicBlock *pb, *pn; - PhiInstruction *phi; Graph::EdgeIterator ei; std::stack<BasicBlock *> stack; - int j = 0; for (ei = bb->cfg.incident(); !ei.end(); ei.next()) { pb = BasicBlock::get(ei.getNode()); @@ -394,22 +387,6 @@ RegAlloc::PhiMovesPass::splitEdges(BasicBlock *bb) stack.push(pb); } - // No critical edges were found, no need to perform any work. - if (stack.empty()) - return; - - // We're about to, potentially, reorder the inbound edges. This means that - // we need to hold on to the (phi, bb) -> src mapping, and fix up the phi - // nodes after the graph has been modified. - PhiMap phis; - - j = 0; - for (ei = bb->cfg.incident(); !ei.end(); ei.next(), j++) { - pb = BasicBlock::get(ei.getNode()); - for (phi = bb->getPhi(); phi; phi = asPhi(phi->next)) - phis.insert(std::make_pair(std::make_pair(phi, pb), phi->getSrc(j))); - } - while (!stack.empty()) { pb = stack.top(); pn = new BasicBlock(func); @@ -423,24 +400,12 @@ RegAlloc::PhiMovesPass::splitEdges(BasicBlock *bb) if (pb->getExit()->asFlow()->target.bb == bb) pb->getExit()->asFlow()->target.bb = pn; - - for (phi = bb->getPhi(); phi; phi = asPhi(phi->next)) { - PhiMap::iterator it = phis.find(std::make_pair(phi, pb)); - assert(it != phis.end()); - phis.insert(std::make_pair(std::make_pair(phi, pn), it->second)); - phis.erase(it); - } - } - - // Now go through and fix up all of the phi node sources. - j = 0; - for (ei = bb->cfg.incident(); !ei.end(); ei.next(), j++) { - pb = BasicBlock::get(ei.getNode()); - for (phi = bb->getPhi(); phi; phi = asPhi(phi->next)) { - PhiMap::const_iterator it = phis.find(std::make_pair(phi, pb)); - assert(it != phis.end()); - - phi->setSrc(j, it->second); + PhiInstruction *phi = asPhi(bb->getPhi()); + for (; phi; phi = asPhi(phi->next)) { + for (int s = 0; phi->srcExists(s); s++) { + if (phi->getBB(s) == pb) + phi->setSrcBB(s, phi->src(s), pn); + } } } } @@ -456,29 +421,29 @@ RegAlloc::PhiMovesPass::splitEdges(BasicBlock *bb) bool RegAlloc::PhiMovesPass::visit(BasicBlock *bb) { - PhiInstruction *phi; - Instruction *mov; - splitEdges(bb); - // insert MOVs (phi->src(j) should stem from j-th in-BB) - int j = 0; + // ensure incoming basic blocks are terminated for (Graph::EdgeIterator ei = bb->cfg.incident(); !ei.end(); ei.next()) { BasicBlock *pb = BasicBlock::get(ei.getNode()); if (!pb->isTerminated()) pb->insertTail(new_FlowInstruction(func, OP_BRA, bb)); + } - for (phi = bb->getPhi(); phi; phi = asPhi(phi->next)) { - LValue *tmp = new_LValue(func, phi->getDef(0)->asLValue()); - mov = new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size)); + // insert MOVs + PhiInstruction *phi = asPhi(bb->getPhi()); + for (; phi; phi = asPhi(phi->next)) { + for (int i = 0; phi->srcExists(i); i++) { + BasicBlock *pb = phi->getBB(i); - mov->setSrc(0, phi->getSrc(j)); + LValue *tmp = new_LValue(func, phi->getDef(0)->asLValue()); + Instruction *mov = new_Instruction(func, OP_MOV, typeOfSize(tmp->reg.size)); + mov->setSrc(0, phi->getSrc(i)); mov->setDef(0, tmp); - phi->setSrc(j, tmp); - pb->insertBefore(pb->getExit(), mov); + + phi->setSrcBB(i, tmp, pb); } - ++j; } return true; diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_ssa.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_ssa.cpp index e2f7522c74..97ba4dd3fd 100644 --- a/src/gallium/drivers/nouveau/codegen/nv50_ir_ssa.cpp +++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_ssa.cpp @@ -387,7 +387,7 @@ Function::convertToSSA() phi->setDef(0, lval); for (Graph::EdgeIterator ei = dfBB->cfg.incident(); !ei.end(); ei.next()) - phi->setSrc(phi->srcCount(), lval); + phi->setSrcBB(phi->srcCount(), lval, BasicBlock::get(ei.getNode())); if (work[dfBB->getId()] < iterCount) { work[dfBB->getId()] = iterCount; @@ -514,10 +514,13 @@ void RenamePass::search(BasicBlock *bb) assert(p < sb->cfg.incidentCount()); for (phi = sb->getPhi(); phi; phi = asPhi(phi->next)) { + // phi instructions are supposed to handle when this isn't true, but + // it's always true during conversion to SSA. + assert(asPhi(phi)->getBB(p) == bb); lval = getStackTop(phi->getSrc(p)); if (!lval) lval = mkUndefined(phi->getSrc(p)); - phi->setSrc(p, lval); + phi->setSrcBB(p, lval, phi->getBB(p)); } } -- 2.14.4 _______________________________________________ mesa-dev mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/mesa-dev
