[Mesa-dev] [PATCH] nv50/ir: use unordered_set instead of list to keep track of var defs
Tobias Klausmann
tobias.johannes.klausmann at mni.thm.de
Mon Sep 1 11:30:28 PDT 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 | 25 ++++++++++++++++------
.../nouveau/codegen/nv50_ir_lowering_nv50.cpp | 4 ++--
src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp | 11 +++++-----
5 files changed, 31 insertions(+), 20 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..ec80796 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 *findOwnDefInsn() 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..e9c6c21 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_inlines.h
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_inlines.h
@@ -205,19 +205,25 @@ 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::findOwnDefInsn() const
+{
+ for (DefCIterator it = defs.begin(); it != defs.end(); ++it)
+ if ((*it)->get() == this)
+ return (*it)->getInsn();
+ /* should be unreachable */
+ return NULL;
}
Instruction *Value::getUniqueInsn() const
{
if (defs.empty())
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();
+ return findOwnDefInsn();
// should be unreachable and trigger assertion at the end
}
#ifdef DEBUG
@@ -230,8 +236,13 @@ Instruction *Value::getUniqueInsn() const
WARN("value %%%i not uniquely defined\n", id); // return NULL ?
}
#endif
- assert(defs.front()->get() == this);
- return defs.front()->getInsn();
+
+ /* It is not guaranteed that this is the first in the set, lets find it */
+ if ((*defs.begin())->get() != this) {
+ return findOwnDefInsn();
+ }
+ assert((*defs.begin())->get() == this);
+ return (*defs.begin())->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_ra.cpp b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
index 5ab6570..7bb28c6 100644
--- a/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
+++ b/src/gallium/drivers/nouveau/codegen/nv50_ir_ra.cpp
@@ -834,7 +834,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;
}
@@ -1409,7 +1409,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;
}
}
@@ -1547,8 +1547,7 @@ SpillCodeInserter::run(const std::list<ValuePair>& lst)
LValue *lval = it->first->asLValue();
Symbol *mem = it->second ? it->second->asSym() : NULL;
- 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;
@@ -1577,13 +1576,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)
delete_Instruction(func->getProgram(), defi);
else
defi->setDef(0, slot);
} else {
spill(defi, slot, dval);
+ d++;
}
}
@@ -2098,7 +2097,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;
--
1.8.4.5
More information about the mesa-dev
mailing list