Re: [Mesa-dev] [PATCH 11/13] nir/nir: Use a linked list instead of a has set for use/def sets
Based on the testing you did, it sounds like switching to linked lists
gives us some pretty good performance gains, but before we go ahead
with this you should collect some numbers using
http://anholt.net/compare-perf/ and put them on this commit message.
Comparing list vs. no-list as well as NIR vs. non-NIR might be useful,
so we can compare the time saved to the total time we spend doing
NIR-related things.
On Tue, Apr 28, 2015 at 12:03 AM, Jason Ekstrand ja...@jlekstrand.net wrote:
This commit switches us from the current setup of using hash sets for
use/def sets to using linked lists. Doing so should save us quite a bit of
memory because we aren't carrying around 3 hash sets per register and 2 per
SSA value. It should also save us CPU time because adding/removing things
from use/def sets is 4 pointer manipulations instead of a hash lookup.
On the code complexity side of things, some things are now much easier and
others are a bit harder. One of the operations we perform constantly in
optimization passes is to replace one source with another. Due to the fact
that an instruction can use the same SSA value multiple times, we had to
iterate through the sources of the instruction and determine if the use we
were replacing was the only one before removing it from the set of uses.
With this patch, uses are per-source not per-instruction so we can just
remove it safely. On the other hand, trying to iterate over all of the
instructions that use a given value is more difficult. Fortunately, the
two places we do that are the ffma peephole where it doesn't matter and GCM
where we already gracefully handle duplicates visits to an instruction.
Another aspect here is that using linked lists in this way can be tricky to
get right. With sets, things were quite forgiving and the worst that
happened if you didn't properly remove a use was that it would get caught
in the validator. With linked lists, it can lead to linked list corruption
which can be harder to track. However, we do just as much validation of
the linked lists as we did of the sets so the validator should still catch
these problems. While working on this series, the vast majority of the
bugs I had to fix were caught by assertions. I don't think the lists are
going to be that much worse than the sets.
---
src/glsl/nir/nir.c | 228
+++-
src/glsl/nir/nir.h | 45 +++--
src/glsl/nir/nir_validate.c | 158 +++---
3 files changed, 194 insertions(+), 237 deletions(-)
diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
index b8f5dd4..be13c90 100644
--- a/src/glsl/nir/nir.c
+++ b/src/glsl/nir/nir.c
@@ -58,12 +58,9 @@ reg_create(void *mem_ctx, struct exec_list *list)
nir_register *reg = ralloc(mem_ctx, nir_register);
reg-parent_instr = NULL;
- reg-uses = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-defs = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-if_uses = _mesa_set_create(reg, _mesa_hash_pointer,
- _mesa_key_pointer_equal);
+ list_inithead(reg-uses);
+ list_inithead(reg-defs);
+ list_inithead(reg-if_uses);
reg-num_components = 0;
reg-num_array_elems = 0;
@@ -1070,11 +1067,14 @@ update_if_uses(nir_cf_node *node)
nir_if *if_stmt = nir_cf_node_as_if(node);
- struct set *if_uses_set = if_stmt-condition.is_ssa ?
- if_stmt-condition.ssa-if_uses :
- if_stmt-condition.reg.reg-uses;
-
- _mesa_set_add(if_uses_set, if_stmt);
+ if_stmt-condition.parent_if = if_stmt;
+ if (if_stmt-condition.is_ssa) {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.ssa-if_uses);
+ } else {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.reg.reg-if_uses);
+ }
}
void
@@ -1227,16 +1227,7 @@ cleanup_cf_node(nir_cf_node *node)
foreach_list_typed(nir_cf_node, child, node, if_stmt-else_list)
cleanup_cf_node(child);
- struct set *if_uses;
- if (if_stmt-condition.is_ssa) {
- if_uses = if_stmt-condition.ssa-if_uses;
- } else {
- if_uses = if_stmt-condition.reg.reg-if_uses;
- }
-
- struct set_entry *entry = _mesa_set_search(if_uses, if_stmt);
- assert(entry);
- _mesa_set_remove(if_uses, entry);
+ list_del(if_stmt-condition.use_link);
break;
}
@@ -1293,9 +1284,9 @@ add_use_cb(nir_src *src, void *state)
{
nir_instr *instr = state;
- struct set *uses_set = src-is_ssa ? src-ssa-uses : src-reg.reg-uses;
-
- _mesa_set_add(uses_set, instr);
+ src-parent_instr = instr;
+ list_addtail(src-use_link,
+src-is_ssa ? src-ssa-uses : src-reg.reg-uses);
return true;
}
@@
Re: [Mesa-dev] [PATCH 11/13] nir/nir: Use a linked list instead of a has set for use/def sets
On Apr 30, 2015 10:05 PM, Connor Abbott cwabbo...@gmail.com wrote:
typedef struct nir_src {
union {
+ nir_instr *parent_instr;
+ struct nir_if *parent_if;
+ };
+
+ struct list_head use_link;
So I was thinking about this, and I realized that putting the list
link here would mean that having SSA-only sources, like my experiments
with making derefs instructions, would be a massive pain. Making a
separate nir_ssa_src to put the use_link and parent_instr/parent_if in
seems like a lot more churn, but would it be harder/even more churn to
do it after this series rather than as a part of it? I don't think it
necessitates re-doing everything or giving up entirely, but I thought
it would be useful to note. I guess we could always use the full
nir_src and then do an assert(is_ssa) in the validator.
We could also put it in nir_reg_src and nir_ssa_src. Since the list is
embedded in a ssa value, we know what kind of source it is. It would
mean
that we would have to split up the iterators though. Not a big deal.
The issue is that nir_ssa_src doesn't exist -- we directly embed the
nir_ssa_def pointer in nir_src. So we would have to replace every
occurrence of foo-src[0].ssa foo[0]-src[0].ssa.def and fixup all the
function definitions, hence all the extra churn.
Right... Yeah, assertions sound better if that's what we want to do.
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 11/13] nir/nir: Use a linked list instead of a has set for use/def sets
You have a typo in the subject line: s/has/hash signature.asc Description: Digital signature ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 11/13] nir/nir: Use a linked list instead of a has set for use/def sets
On Apr 30, 2015 7:37 PM, Connor Abbott cwabbo...@gmail.com wrote:
On Tue, Apr 28, 2015 at 12:03 AM, Jason Ekstrand ja...@jlekstrand.net
wrote:
This commit switches us from the current setup of using hash sets for
use/def sets to using linked lists. Doing so should save us quite a
bit of
memory because we aren't carrying around 3 hash sets per register and 2
per
SSA value. It should also save us CPU time because adding/removing
things
from use/def sets is 4 pointer manipulations instead of a hash lookup.
On the code complexity side of things, some things are now much easier
and
others are a bit harder. One of the operations we perform constantly in
optimization passes is to replace one source with another. Due to the
fact
that an instruction can use the same SSA value multiple times, we had to
iterate through the sources of the instruction and determine if the use
we
were replacing was the only one before removing it from the set of uses.
With this patch, uses are per-source not per-instruction so we can just
remove it safely. On the other hand, trying to iterate over all of the
instructions that use a given value is more difficult. Fortunately, the
two places we do that are the ffma peephole where it doesn't matter and
GCM
where we already gracefully handle duplicates visits to an instruction.
Another aspect here is that using linked lists in this way can be
tricky to
get right. With sets, things were quite forgiving and the worst that
happened if you didn't properly remove a use was that it would get
caught
in the validator. With linked lists, it can lead to linked list
corruption
which can be harder to track. However, we do just as much validation of
the linked lists as we did of the sets so the validator should still
catch
these problems. While working on this series, the vast majority of the
bugs I had to fix were caught by assertions. I don't think the lists
are
going to be that much worse than the sets.
---
src/glsl/nir/nir.c | 228
+++-
src/glsl/nir/nir.h | 45 +++--
src/glsl/nir/nir_validate.c | 158 +++---
3 files changed, 194 insertions(+), 237 deletions(-)
diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
index b8f5dd4..be13c90 100644
--- a/src/glsl/nir/nir.c
+++ b/src/glsl/nir/nir.c
@@ -58,12 +58,9 @@ reg_create(void *mem_ctx, struct exec_list *list)
nir_register *reg = ralloc(mem_ctx, nir_register);
reg-parent_instr = NULL;
- reg-uses = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-defs = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-if_uses = _mesa_set_create(reg, _mesa_hash_pointer,
- _mesa_key_pointer_equal);
+ list_inithead(reg-uses);
+ list_inithead(reg-defs);
+ list_inithead(reg-if_uses);
reg-num_components = 0;
reg-num_array_elems = 0;
@@ -1070,11 +1067,14 @@ update_if_uses(nir_cf_node *node)
nir_if *if_stmt = nir_cf_node_as_if(node);
- struct set *if_uses_set = if_stmt-condition.is_ssa ?
- if_stmt-condition.ssa-if_uses :
- if_stmt-condition.reg.reg-uses;
-
- _mesa_set_add(if_uses_set, if_stmt);
+ if_stmt-condition.parent_if = if_stmt;
+ if (if_stmt-condition.is_ssa) {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.ssa-if_uses);
+ } else {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.reg.reg-if_uses);
+ }
}
void
@@ -1227,16 +1227,7 @@ cleanup_cf_node(nir_cf_node *node)
foreach_list_typed(nir_cf_node, child, node, if_stmt-else_list)
cleanup_cf_node(child);
- struct set *if_uses;
- if (if_stmt-condition.is_ssa) {
- if_uses = if_stmt-condition.ssa-if_uses;
- } else {
- if_uses = if_stmt-condition.reg.reg-if_uses;
- }
-
- struct set_entry *entry = _mesa_set_search(if_uses, if_stmt);
- assert(entry);
- _mesa_set_remove(if_uses, entry);
+ list_del(if_stmt-condition.use_link);
break;
}
@@ -1293,9 +1284,9 @@ add_use_cb(nir_src *src, void *state)
{
nir_instr *instr = state;
- struct set *uses_set = src-is_ssa ? src-ssa-uses :
src-reg.reg-uses;
-
- _mesa_set_add(uses_set, instr);
+ src-parent_instr = instr;
+ list_addtail(src-use_link,
+src-is_ssa ? src-ssa-uses : src-reg.reg-uses);
return true;
}
@@ -1320,8 +1311,10 @@ add_reg_def_cb(nir_dest *dest, void *state)
{
nir_instr *instr = state;
- if (!dest-is_ssa)
- _mesa_set_add(dest-reg.reg-defs, instr);
+ if (!dest-is_ssa) {
+ dest-reg.parent_instr = instr;
Re: [Mesa-dev] [PATCH 11/13] nir/nir: Use a linked list instead of a has set for use/def sets
On Tue, Apr 28, 2015 at 12:03 AM, Jason Ekstrand ja...@jlekstrand.net wrote:
This commit switches us from the current setup of using hash sets for
use/def sets to using linked lists. Doing so should save us quite a bit of
memory because we aren't carrying around 3 hash sets per register and 2 per
SSA value. It should also save us CPU time because adding/removing things
from use/def sets is 4 pointer manipulations instead of a hash lookup.
On the code complexity side of things, some things are now much easier and
others are a bit harder. One of the operations we perform constantly in
optimization passes is to replace one source with another. Due to the fact
that an instruction can use the same SSA value multiple times, we had to
iterate through the sources of the instruction and determine if the use we
were replacing was the only one before removing it from the set of uses.
With this patch, uses are per-source not per-instruction so we can just
remove it safely. On the other hand, trying to iterate over all of the
instructions that use a given value is more difficult. Fortunately, the
two places we do that are the ffma peephole where it doesn't matter and GCM
where we already gracefully handle duplicates visits to an instruction.
Another aspect here is that using linked lists in this way can be tricky to
get right. With sets, things were quite forgiving and the worst that
happened if you didn't properly remove a use was that it would get caught
in the validator. With linked lists, it can lead to linked list corruption
which can be harder to track. However, we do just as much validation of
the linked lists as we did of the sets so the validator should still catch
these problems. While working on this series, the vast majority of the
bugs I had to fix were caught by assertions. I don't think the lists are
going to be that much worse than the sets.
---
src/glsl/nir/nir.c | 228
+++-
src/glsl/nir/nir.h | 45 +++--
src/glsl/nir/nir_validate.c | 158 +++---
3 files changed, 194 insertions(+), 237 deletions(-)
diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
index b8f5dd4..be13c90 100644
--- a/src/glsl/nir/nir.c
+++ b/src/glsl/nir/nir.c
@@ -58,12 +58,9 @@ reg_create(void *mem_ctx, struct exec_list *list)
nir_register *reg = ralloc(mem_ctx, nir_register);
reg-parent_instr = NULL;
- reg-uses = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-defs = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-if_uses = _mesa_set_create(reg, _mesa_hash_pointer,
- _mesa_key_pointer_equal);
+ list_inithead(reg-uses);
+ list_inithead(reg-defs);
+ list_inithead(reg-if_uses);
reg-num_components = 0;
reg-num_array_elems = 0;
@@ -1070,11 +1067,14 @@ update_if_uses(nir_cf_node *node)
nir_if *if_stmt = nir_cf_node_as_if(node);
- struct set *if_uses_set = if_stmt-condition.is_ssa ?
- if_stmt-condition.ssa-if_uses :
- if_stmt-condition.reg.reg-uses;
-
- _mesa_set_add(if_uses_set, if_stmt);
+ if_stmt-condition.parent_if = if_stmt;
+ if (if_stmt-condition.is_ssa) {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.ssa-if_uses);
+ } else {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.reg.reg-if_uses);
+ }
}
void
@@ -1227,16 +1227,7 @@ cleanup_cf_node(nir_cf_node *node)
foreach_list_typed(nir_cf_node, child, node, if_stmt-else_list)
cleanup_cf_node(child);
- struct set *if_uses;
- if (if_stmt-condition.is_ssa) {
- if_uses = if_stmt-condition.ssa-if_uses;
- } else {
- if_uses = if_stmt-condition.reg.reg-if_uses;
- }
-
- struct set_entry *entry = _mesa_set_search(if_uses, if_stmt);
- assert(entry);
- _mesa_set_remove(if_uses, entry);
+ list_del(if_stmt-condition.use_link);
break;
}
@@ -1293,9 +1284,9 @@ add_use_cb(nir_src *src, void *state)
{
nir_instr *instr = state;
- struct set *uses_set = src-is_ssa ? src-ssa-uses : src-reg.reg-uses;
-
- _mesa_set_add(uses_set, instr);
+ src-parent_instr = instr;
+ list_addtail(src-use_link,
+src-is_ssa ? src-ssa-uses : src-reg.reg-uses);
return true;
}
@@ -1320,8 +1311,10 @@ add_reg_def_cb(nir_dest *dest, void *state)
{
nir_instr *instr = state;
- if (!dest-is_ssa)
- _mesa_set_add(dest-reg.reg-defs, instr);
+ if (!dest-is_ssa) {
+ dest-reg.parent_instr = instr;
+ list_addtail(dest-reg.def_link, dest-reg.reg-defs);
+ }
return true;
}
@@ -1436,13 +1429,7 @@ nir_instr_insert_after_cf_list(struct exec_list *list,
Re: [Mesa-dev] [PATCH 11/13] nir/nir: Use a linked list instead of a has set for use/def sets
typedef struct nir_src {
union {
+ nir_instr *parent_instr;
+ struct nir_if *parent_if;
+ };
+
+ struct list_head use_link;
So I was thinking about this, and I realized that putting the list
link here would mean that having SSA-only sources, like my experiments
with making derefs instructions, would be a massive pain. Making a
separate nir_ssa_src to put the use_link and parent_instr/parent_if in
seems like a lot more churn, but would it be harder/even more churn to
do it after this series rather than as a part of it? I don't think it
necessitates re-doing everything or giving up entirely, but I thought
it would be useful to note. I guess we could always use the full
nir_src and then do an assert(is_ssa) in the validator.
We could also put it in nir_reg_src and nir_ssa_src. Since the list is
embedded in a ssa value, we know what kind of source it is. It would mean
that we would have to split up the iterators though. Not a big deal.
The issue is that nir_ssa_src doesn't exist -- we directly embed the
nir_ssa_def pointer in nir_src. So we would have to replace every
occurrence of foo-src[0].ssa foo[0]-src[0].ssa.def and fixup all the
function definitions, hence all the extra churn.
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
[Mesa-dev] [PATCH 11/13] nir/nir: Use a linked list instead of a has set for use/def sets
This commit switches us from the current setup of using hash sets for
use/def sets to using linked lists. Doing so should save us quite a bit of
memory because we aren't carrying around 3 hash sets per register and 2 per
SSA value. It should also save us CPU time because adding/removing things
from use/def sets is 4 pointer manipulations instead of a hash lookup.
On the code complexity side of things, some things are now much easier and
others are a bit harder. One of the operations we perform constantly in
optimization passes is to replace one source with another. Due to the fact
that an instruction can use the same SSA value multiple times, we had to
iterate through the sources of the instruction and determine if the use we
were replacing was the only one before removing it from the set of uses.
With this patch, uses are per-source not per-instruction so we can just
remove it safely. On the other hand, trying to iterate over all of the
instructions that use a given value is more difficult. Fortunately, the
two places we do that are the ffma peephole where it doesn't matter and GCM
where we already gracefully handle duplicates visits to an instruction.
Another aspect here is that using linked lists in this way can be tricky to
get right. With sets, things were quite forgiving and the worst that
happened if you didn't properly remove a use was that it would get caught
in the validator. With linked lists, it can lead to linked list corruption
which can be harder to track. However, we do just as much validation of
the linked lists as we did of the sets so the validator should still catch
these problems. While working on this series, the vast majority of the
bugs I had to fix were caught by assertions. I don't think the lists are
going to be that much worse than the sets.
---
src/glsl/nir/nir.c | 228 +++-
src/glsl/nir/nir.h | 45 +++--
src/glsl/nir/nir_validate.c | 158 +++---
3 files changed, 194 insertions(+), 237 deletions(-)
diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
index b8f5dd4..be13c90 100644
--- a/src/glsl/nir/nir.c
+++ b/src/glsl/nir/nir.c
@@ -58,12 +58,9 @@ reg_create(void *mem_ctx, struct exec_list *list)
nir_register *reg = ralloc(mem_ctx, nir_register);
reg-parent_instr = NULL;
- reg-uses = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-defs = _mesa_set_create(reg, _mesa_hash_pointer,
-_mesa_key_pointer_equal);
- reg-if_uses = _mesa_set_create(reg, _mesa_hash_pointer,
- _mesa_key_pointer_equal);
+ list_inithead(reg-uses);
+ list_inithead(reg-defs);
+ list_inithead(reg-if_uses);
reg-num_components = 0;
reg-num_array_elems = 0;
@@ -1070,11 +1067,14 @@ update_if_uses(nir_cf_node *node)
nir_if *if_stmt = nir_cf_node_as_if(node);
- struct set *if_uses_set = if_stmt-condition.is_ssa ?
- if_stmt-condition.ssa-if_uses :
- if_stmt-condition.reg.reg-uses;
-
- _mesa_set_add(if_uses_set, if_stmt);
+ if_stmt-condition.parent_if = if_stmt;
+ if (if_stmt-condition.is_ssa) {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.ssa-if_uses);
+ } else {
+ list_addtail(if_stmt-condition.use_link,
+ if_stmt-condition.reg.reg-if_uses);
+ }
}
void
@@ -1227,16 +1227,7 @@ cleanup_cf_node(nir_cf_node *node)
foreach_list_typed(nir_cf_node, child, node, if_stmt-else_list)
cleanup_cf_node(child);
- struct set *if_uses;
- if (if_stmt-condition.is_ssa) {
- if_uses = if_stmt-condition.ssa-if_uses;
- } else {
- if_uses = if_stmt-condition.reg.reg-if_uses;
- }
-
- struct set_entry *entry = _mesa_set_search(if_uses, if_stmt);
- assert(entry);
- _mesa_set_remove(if_uses, entry);
+ list_del(if_stmt-condition.use_link);
break;
}
@@ -1293,9 +1284,9 @@ add_use_cb(nir_src *src, void *state)
{
nir_instr *instr = state;
- struct set *uses_set = src-is_ssa ? src-ssa-uses : src-reg.reg-uses;
-
- _mesa_set_add(uses_set, instr);
+ src-parent_instr = instr;
+ list_addtail(src-use_link,
+src-is_ssa ? src-ssa-uses : src-reg.reg-uses);
return true;
}
@@ -1320,8 +1311,10 @@ add_reg_def_cb(nir_dest *dest, void *state)
{
nir_instr *instr = state;
- if (!dest-is_ssa)
- _mesa_set_add(dest-reg.reg-defs, instr);
+ if (!dest-is_ssa) {
+ dest-reg.parent_instr = instr;
+ list_addtail(dest-reg.def_link, dest-reg.reg-defs);
+ }
return true;
}
@@ -1436,13 +1429,7 @@ nir_instr_insert_after_cf_list(struct exec_list *list,
nir_instr *after)
static bool
remove_use_cb(nir_src *src, void *state)
{
- nir_instr *instr = state;
-
- struct set *uses_set = src-is_ssa ? src-ssa-uses : src-reg.reg-uses;
