[Mesa-dev] [PATCH 2/2] nv50/ir: don't rely on inbound edge order in phi nodes
Rhys Perry
pendingchaos02 at gmail.com
Wed Jul 11 15:58:12 UTC 2018
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 <pendingchaos02 at gmail.com>
---
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
More information about the mesa-dev
mailing list