Re: [Mesa-dev] [RFC 7/9] nir/nir: Use a linked list instead of a has set for use/def sets
On Mon, Apr 27, 2015 at 5:25 PM, Jason Ekstrand wrote:
> On Mon, Apr 27, 2015 at 1:35 PM, Connor Abbott wrote:
>> On Fri, Apr 24, 2015 at 7:32 PM, Jason Ekstrand wrote:
>>> +struct nir_if;
>>> +
>>> typedef struct nir_src {
>>> union {
>>> + nir_instr *parent_instr;
>>> + struct nir_if *parent_if;
>>> + };
>>
>> There's something I'm not quite understanding about this... how are we
>> supposed to know which of parent_instr and parent_if are valid? If I
>> walk over all the sources for a given SSA def or register, how am I
>> supposed to know if it's part of an if-condition or an instruction? I
>> would think that you would need a boolean here or have parent_instr
>> and parent_if not be in a union.
>
> We do the same thing we did with the sets before. We have separate
> uses and if_uses sets. If it's in if_uses, you use the if. If it's
> in uses, it's an instr. We could put something in the source but that
> seems like it'll make for even more mess.
> --Jason
D'oh... right. That makes sense.
Connor
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC 7/9] nir/nir: Use a linked list instead of a has set for use/def sets
On Mon, Apr 27, 2015 at 1:35 PM, Connor Abbott wrote:
> On Fri, Apr 24, 2015 at 7:32 PM, Jason Ekstrand wrote:
>> +struct nir_if;
>> +
>> typedef struct nir_src {
>> union {
>> + nir_instr *parent_instr;
>> + struct nir_if *parent_if;
>> + };
>
> There's something I'm not quite understanding about this... how are we
> supposed to know which of parent_instr and parent_if are valid? If I
> walk over all the sources for a given SSA def or register, how am I
> supposed to know if it's part of an if-condition or an instruction? I
> would think that you would need a boolean here or have parent_instr
> and parent_if not be in a union.
We do the same thing we did with the sets before. We have separate
uses and if_uses sets. If it's in if_uses, you use the if. If it's
in uses, it's an instr. We could put something in the source but that
seems like it'll make for even more mess.
--Jason
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC 7/9] nir/nir: Use a linked list instead of a has set for use/def sets
On Fri, Apr 24, 2015 at 7:32 PM, Jason Ekstrand 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 | 232
>
> src/glsl/nir/nir.h | 27 --
> src/glsl/nir/nir_validate.c | 158 +++---
> 3 files changed, 182 insertions(+), 235 deletions(-)
>
> diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
> index b8f5dd4..283b861 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);
> + nir_list_init(®->uses);
> + nir_list_init(®->defs);
> + nir_list_init(®->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) {
> + nir_list_push_tail(&if_stmt->condition.ssa->if_uses,
> + &if_stmt->condition.use_link);
> + } else {
> + nir_list_push_tail(&if_stmt->condition.reg.reg->if_uses,
> + &if_stmt->condition.use_link);
> + }
> }
>
> 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);
> + nir_link_remove(&if_stmt->condition.use_link);
>break;
> }
>
> @@ -1293,9 +1284,10 @@ 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;
> + nir_link_init(&src->use_link);
> + nir_list *uses_list = src->is_ssa ? &src->ssa->uses : &src->reg.reg->uses;
> + nir_list_push_tail(uses_list, &src->use_link);
>
> return true;
> }
> @@ -1320,8 +1312,11 @@ 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
Re: [Mesa-dev] [RFC 7/9] nir/nir: Use a linked list instead of a has set for use/def sets
On Fri, Apr 24, 2015 at 4:32 PM, Jason Ekstrand 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.
I'm going to get some actual performance numbers for this but the
performance looks like we can save about %10 on shader-db. I should
have perf and memory numbers by some time on Monday.
> 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 | 232
>
> src/glsl/nir/nir.h | 27 --
> src/glsl/nir/nir_validate.c | 158 +++---
> 3 files changed, 182 insertions(+), 235 deletions(-)
>
> diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
> index b8f5dd4..283b861 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);
> + nir_list_init(®->uses);
> + nir_list_init(®->defs);
> + nir_list_init(®->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) {
> + nir_list_push_tail(&if_stmt->condition.ssa->if_uses,
> + &if_stmt->condition.use_link);
> + } else {
> + nir_list_push_tail(&if_stmt->condition.reg.reg->if_uses,
> + &if_stmt->condition.use_link);
> + }
> }
>
> 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);
> + nir_link_remove(&if_stmt->condition.use_link);
>break;
> }
>
> @@ -1293,9 +1284,10 @@ 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;
> + nir_link_init(&src->use_link);
> + nir_list *uses_list = src->is_ssa ? &src->ssa->uses : &src->reg.reg->uses;
> + nir_list_push_tail(uses_list, &src->use_link);
>
> return true;
> }
> @@ -1320,
[Mesa-dev] [RFC 7/9] 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 | 232
src/glsl/nir/nir.h | 27 --
src/glsl/nir/nir_validate.c | 158 +++---
3 files changed, 182 insertions(+), 235 deletions(-)
diff --git a/src/glsl/nir/nir.c b/src/glsl/nir/nir.c
index b8f5dd4..283b861 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);
+ nir_list_init(®->uses);
+ nir_list_init(®->defs);
+ nir_list_init(®->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) {
+ nir_list_push_tail(&if_stmt->condition.ssa->if_uses,
+ &if_stmt->condition.use_link);
+ } else {
+ nir_list_push_tail(&if_stmt->condition.reg.reg->if_uses,
+ &if_stmt->condition.use_link);
+ }
}
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);
+ nir_link_remove(&if_stmt->condition.use_link);
break;
}
@@ -1293,9 +1284,10 @@ 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;
+ nir_link_init(&src->use_link);
+ nir_list *uses_list = src->is_ssa ? &src->ssa->uses : &src->reg.reg->uses;
+ nir_list_push_tail(uses_list, &src->use_link);
return true;
}
@@ -1320,8 +1312,11 @@ 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;
+ nir_link_init(&dest->reg.def_link);
+ nir_list_push_tail(&dest->reg.reg->defs, &dest->reg.def_link);
+ }
return true;
}
@@ -1436,13 +1431,7 @@ nir_instr_insert_after_cf_list(struct exec_li
