[Mesa-dev] [PATCH RESEND] nv50/ir: use unordered_set instead of list to keep track of var defs
Tobias Klausmann
tobias.johannes.klausmann at mni.thm.de
Tue Dec 2 12:19:01 PST 2014
The set of variable defs does not need to be ordered in any way, and
removing/adding elements is a fairly common operation in various
optimization passes.
This shortens runtime of piglit test fp-long-alu to ~11s from ~22s
No piglit regressions observed on nvc0!
Signed-off-by: Tobias Klausmann <tobias.johannes.klausmann at mni.thm.de>
---
src/gallium/drivers/nouveau/codegen/nv50_ir.cpp | 4 ++--
src/gallium/drivers/nouveau/codegen/nv50_ir.h | 7 +++---
.../drivers/nouveau/codegen/nv50_ir_inlines.h | 28 +++++++++++++---------
.../nouveau/codegen/nv50_ir_lowering_nv50.cpp | 4 ++--
.../nouveau/codegen/nv50_ir_lowering_nvc0.cpp | 6 ++---
.../drivers/nouveau/codegen/nv50_ir_peephole.cpp | 4 ++--
src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp | 17 +++++++------
7 files changed, 38 insertions(+), 32 deletions(-)
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp
index ca3c806..3138118 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir.cpp
@@ -154,9 +154,9 @@ ValueDef::set(Value *defVal)
if (value == defVal)
return;
if (value)
- value->defs.remove(this);
+ value->defs.erase(this);
if (defVal)
- defVal->defs.push_back(this);
+ defVal->defs.insert(this);
value = defVal;
}
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir.h b/src/gallium/drivers/nouveau/codegen/nv50_ir.h
index 0ff5e5d..56033f1 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir.h
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir.h
@@ -567,6 +567,7 @@ public:
inline Value *rep() const { return join; }
+ inline Instruction *getUniqueInsnMerged() const;
inline Instruction *getUniqueInsn() const;
inline Instruction *getInsn() const; // use when uniqueness is certain
@@ -583,11 +584,11 @@ public:
static inline Value *get(Iterator&);
std::tr1::unordered_set<ValueRef *> uses;
- std::list<ValueDef *> defs;
+ std::tr1::unordered_set<ValueDef *> defs;
typedef std::tr1::unordered_set<ValueRef *>::iterator UseIterator;
typedef std::tr1::unordered_set<ValueRef *>::const_iterator UseCIterator;
- typedef std::list<ValueDef *>::iterator DefIterator;
- typedef std::list<ValueDef *>::const_iterator DefCIterator;
+ typedef std::tr1::unordered_set<ValueDef *>::iterator DefIterator;
+ typedef std::tr1::unordered_set<ValueDef *>::const_iterator DefCIterator;
int id;
Storage reg;
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_inlines.h b/src/gallium/drivers/nouveau/codegen/nv50_ir_inlines.h
index 255324f..471d47f 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_inlines.h
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_inlines.h
@@ -205,21 +205,26 @@ const LValue *ValueDef::preSSA() const
Instruction *Value::getInsn() const
{
- return defs.empty() ? NULL : defs.front()->getInsn();
+ return defs.empty() ? NULL : (*defs.begin())->getInsn();
}
-Instruction *Value::getUniqueInsn() const
+Instruction *Value::getUniqueInsnMerged() const
{
if (defs.empty())
return NULL;
+ /* It is not guaranteed that this is the first in the set, lets find it */
+ for (DefCIterator it = defs.begin(); it != defs.end(); ++it)
+ if ((*it)->get() == this)
+ return (*it)->getInsn();
+ /* We should never hit this assert */
+ assert(0);
+ return NULL;
+}
- // after regalloc, the definitions of coalesced values are linked
- if (join != this) {
- for (DefCIterator it = defs.begin(); it != defs.end(); ++it)
- if ((*it)->get() == this)
- return (*it)->getInsn();
- // should be unreachable and trigger assertion at the end
- }
+Instruction *Value::getUniqueInsn() const
+{
+ if (defs.empty())
+ return NULL;
#ifdef DEBUG
if (reg.data.id < 0) {
int n = 0;
@@ -230,8 +235,9 @@ Instruction *Value::getUniqueInsn() const
WARN("value %%%i not uniquely defined\n", id); // return NULL ?
}
#endif
- assert(defs.front()->get() == this);
- return defs.front()->getInsn();
+ ValueDef *def = *defs.begin();
+ assert(def->get() == this);
+ return def->getInsn();
}
inline bool Instruction::constrainedDefs() const
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nv50.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nv50.cpp
index e283424..f13e0d4 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nv50.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nv50.cpp
@@ -211,7 +211,7 @@ NV50LegalizePostRA::visit(Function *fn)
if (outWrites) {
for (std::list<Instruction *>::iterator it = outWrites->begin();
it != outWrites->end(); ++it)
- (*it)->getSrc(1)->defs.front()->getInsn()->setDef(0, (*it)->getSrc(0));
+ (*(*it)->getSrc(1)->defs.begin())->getInsn()->setDef(0, (*it)->getSrc(0));
// instructions will be deleted on exit
outWrites->clear();
}
@@ -343,7 +343,7 @@ NV50LegalizeSSA::propagateWriteToOutput(Instruction *st)
return;
// check def instruction can store
- Instruction *di = st->getSrc(1)->defs.front()->getInsn();
+ Instruction *di =(*st->getSrc(1)->defs.begin())->getInsn();
// TODO: move exports (if beneficial) in common opt pass
if (di->isPseudo() || isTextureOp(di->op) || di->defCount(0xff, true) > 1)
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nvc0.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nvc0.cpp
index 9c06d04..ab28f3a 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nvc0.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_lowering_nvc0.cpp
@@ -148,7 +148,7 @@ NVC0LegalizePostRA::findOverwritingDefs(const Instruction *texi,
std::list<TexUse> &uses)
{
while (insn->op == OP_MOV && insn->getDef(0)->equals(insn->getSrc(0)))
- insn = insn->getSrc(0)->getUniqueInsn();
+ insn = insn->getSrc(0)->getUniqueInsnMerged();
if (!insn->bb->reachableBy(texi->bb, term))
return;
@@ -163,7 +163,7 @@ NVC0LegalizePostRA::findOverwritingDefs(const Instruction *texi,
case OP_UNION:
/* recurse again */
for (int s = 0; insn->srcExists(s); ++s)
- findOverwritingDefs(texi, insn->getSrc(s)->getUniqueInsn(), term,
+ findOverwritingDefs(texi, insn->getSrc(s)->getUniqueInsnMerged(), term,
uses);
break;
default:
@@ -200,7 +200,7 @@ NVC0LegalizePostRA::findFirstUses(
if (usei->op == OP_PHI || usei->op == OP_UNION) {
// need a barrier before WAW cases
for (int s = 0; usei->srcExists(s); ++s) {
- Instruction *defi = usei->getSrc(s)->getUniqueInsn();
+ Instruction *defi = usei->getSrc(s)->getUniqueInsnMerged();
if (defi && &usei->src(s) != *u)
findOverwritingDefs(texi, defi, usei->bb, uses);
}
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_peephole.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_peephole.cpp
index f520dc6..ff3f8c3 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_peephole.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_peephole.cpp
@@ -2144,7 +2144,7 @@ FlatteningPass::isConstantCondition(Value *pred)
return false;
for (int s = 0; s < 2 && insn->srcExists(s); ++s) {
- Instruction *ld = insn->getSrc(s)->getUniqueInsn();
+ Instruction *ld = insn->getSrc(s)->getUniqueInsnMerged();
DataFile file;
if (ld) {
if (ld->op != OP_MOV && ld->op != OP_LOAD)
@@ -2185,7 +2185,7 @@ FlatteningPass::removeFlow(Instruction *insn)
delete_Instruction(prog, term);
if (pred && pred->refCount() == 0) {
- Instruction *pSet = pred->getUniqueInsn();
+ Instruction *pSet = pred->getUniqueInsnMerged();
pred->join->reg.data.id = -1; // deallocate
if (pSet->isDead())
delete_Instruction(prog, pSet);
diff --git a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
index 898653c..8961237 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
@@ -313,7 +313,7 @@ RegAlloc::BuildIntervalsPass::addLiveRange(Value *val,
const BasicBlock *bb,
int end)
{
- Instruction *insn = val->getUniqueInsn();
+ Instruction *insn = val->getUniqueInsnMerged();
if (!insn)
insn = bb->getFirst();
@@ -579,7 +579,7 @@ RegAlloc::BuildIntervalsPass::visit(BasicBlock *bb)
for (int s = 0; i->srcExists(s); ++s) {
assert(i->src(s).getInsn());
- if (i->getSrc(s)->getUniqueInsn()->bb == bb) // XXX: reachableBy ?
+ if (i->getSrc(s)->getUniqueInsnMerged()->bb == bb) // XXX: reachableBy ?
bb->liveSet.set(i->getSrc(s)->id);
else
bb->liveSet.clr(i->getSrc(s)->id);
@@ -835,7 +835,7 @@ GCRA::coalesceValues(Value *dst, Value *src, bool force)
assert(rep->join == rep && val->join == rep);
// add val's definitions to rep and extend the live interval of its RIG node
- rep->defs.insert(rep->defs.end(), val->defs.begin(), val->defs.end());
+ rep->defs.insert(val->defs.begin(), val->defs.end());
nRep->livei.unify(nVal->livei);
return true;
}
@@ -989,7 +989,7 @@ GCRA::doCoalesce(ArrayList& insns, unsigned int mask)
// if this is a contraint-move there will only be a single use
if (i && i->op == OP_MERGE) // do we really still need this ?
break;
- i = insn->getSrc(0)->getUniqueInsn();
+ i = insn->getSrc(0)->getUniqueInsnMerged();
if (i && !i->constrainedDefs()) {
if (coalesceValues(insn->getDef(0), insn->getSrc(0), false))
copyCompound(insn->getSrc(0), insn->getDef(0));
@@ -1410,7 +1410,7 @@ GCRA::cleanup(const bool success)
} else {
for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end();
++d)
- lval->join->defs.remove(*d);
+ lval->join->defs.erase(*d);
lval->join = lval;
}
}
@@ -1553,8 +1553,7 @@ SpillCodeInserter::run(const std::list<ValuePair>& lst)
// multiple destinations that all need to be spilled (like OP_SPLIT).
std::tr1::unordered_set<Instruction *> to_del;
- for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end();
- ++d) {
+ for (Value::DefIterator d = lval->defs.begin(); d != lval->defs.end();) {
Value *slot = mem ?
static_cast<Value *>(mem) : new_LValue(func, FILE_GPR);
Value *tmp = NULL;
@@ -1583,13 +1582,13 @@ SpillCodeInserter::run(const std::list<ValuePair>& lst)
assert(defi);
if (defi->isPseudo()) {
d = lval->defs.erase(d);
- --d;
if (slot->reg.file == FILE_MEMORY_LOCAL)
to_del.insert(defi);
else
defi->setDef(0, slot);
} else {
spill(defi, slot, dval);
+ ++d;
}
}
@@ -2118,7 +2117,7 @@ RegAlloc::InsertConstraintsPass::insertConstraintMoves()
}
assert(cst->getSrc(s)->defs.size() == 1); // still SSA
- Instruction *defi = cst->getSrc(s)->defs.front()->getInsn();
+ Instruction *defi =(*cst->getSrc(s)->defs.begin())->getInsn();
// catch some cases where don't really need MOVs
if (cst->getSrc(s)->refCount() == 1 && !defi->constrainedDefs())
continue;
--
2.1.3
More information about the mesa-dev
mailing list