[Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation

[Rob Clark]

On Fri, Apr 24, 2015 at 7:32 PM, Jason Ekstrand <jason at jlekstrand.net> wrote:
> This commit adds a C-based linked list implementation for NIR.  Unlike
> exec_list in glsl/list.h, there is no C++ API.  Also, this list is based on
> wl_list (from the Wayland project) which is, in turn, based on the kernel
> list.  As such, it should be fairly familiar to people who have done
> anything in kernel space.
>
> Doesn't exec_list already have a C api?
>
> Yes, it does.  However, exec_list has C++ constructors for exec_list and
> exec_node.  In the patches that follow, I use linked lists for use/def sets
> for registers and SSA values.  In order to do so, I have to be able to
> place lists and links inside of unions.  Since exec_list and exec_node have
> constructors, doing so causes any C++ code that includes nir.h to die in a
> fire.  Therefore, we can't just use exec_list.
>
> What about simple_list?  Why re-create it?
>
> I thought about that too.  However, the simple_list is badly named and the
> API isn't that great.  Making it usable as a first-class datastructure
> would have taken as much work as adding nir_list.  Also, simple_list isn't
> really a standard as it's only ever used in errors.c and the vc4 driver.
>
> Why a kernel list; why not keep the symantics of exec_list?
>
> The short version:  I like it better.  Also, while exec_list is familiar to
> people who have worked inside the mesa GLSL compiler, I think that the
> kernel list will be more familiar to people in the open-source graphics
> community in general.  For whatever it's worth, I explicitly designed it
> with separate nir_list and nir_link structures so that we can switch from
> kernel list to exec_list symantics if we want to.

jfwiw, I am in favor of kernel(ish) lists.. although (as mentioned on
irc) maybe we just want to hoist gallium's u_double_list.h out into
util so it can be used more widely.  (fwiw, I am already using
u_double_list in freedreno)

BR,
-R


> Why put this in NIR and not in util?
>
> At the moment, NIR is the only user.  I do expect that Eric may want to use
> it in vc4 over simple_list.  However, vc4 is already using NIR anyway, so
> it's not really that polluting.
>
> It has also been suggested by Ken that we just pull the C bits out of
> exec_list and keep one underlying implementation for both C and C++ only
> with different names.  While I think that this is definitely doable and may
> be the best long-term solution, I didn't want to do that refactoring prior
> to getting this series up-and-going and adding a list was easier.  I'm ok
> with doing that instead of adding a list.
> ---
>  src/glsl/Makefile.sources |   1 +
>  src/glsl/nir/nir_list.h   | 183 ++++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 184 insertions(+)
>  create mode 100644 src/glsl/nir/nir_list.h
>
> diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
> index c471eca..fa51dcb 100644
> --- a/src/glsl/Makefile.sources
> +++ b/src/glsl/Makefile.sources
> @@ -28,6 +28,7 @@ NIR_FILES = \
>         nir/nir_from_ssa.c \
>         nir/nir_intrinsics.c \
>         nir/nir_intrinsics.h \
> +       nir/nir_list.h \
>         nir/nir_live_variables.c \
>         nir/nir_lower_alu_to_scalar.c \
>         nir/nir_lower_atomics.c \
> diff --git a/src/glsl/nir/nir_list.h b/src/glsl/nir/nir_list.h
> new file mode 100644
> index 0000000..330a660
> --- /dev/null
> +++ b/src/glsl/nir/nir_list.h
> @@ -0,0 +1,183 @@
> +/*
> + * Copyright © 2015 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> + * IN THE SOFTWARE.
> + *
> + * Authors:
> + *    Jason Ekstrand (jason at jlekstrand.net)
> + *
> + */
> +
> +#pragma once
> +
> +#ifndef _NIR_LIST_H_
> +#define _NIR_LIST_H_
> +
> +/** A simple linked list implementation.
> + *
> + * This linked list implementation is based on wl_list from the Wayland
> + * project which is, in turn, based on the kernel list.  As such, it should
> + * be fairly familiar to anyone who has worked in kernel space.
> + */
> +
> +/* Required for exec_node_data */
> +#include "../list.h"
> +
> +struct nir_link;
> +
> +/** \class nir_list
> + *
> + * \brief doubly-linked list
> + *
> + * The list head is of type nir_list and must be initialized using
> + * nir_list_init().  All entries in the list must be of the same type.  The
> + * item type must have a nir_link member which must be initialized to zero.
> + * To query if the list is empty in O(1), use nir_list_is_empty().
> + *
> + * Let's call the list reference "nir_list foo_list", the item type as
> + * "item_t", and the item member as "nir_link link".
> + *
> + * The following code will initialize a list:
> + * \code
> + * nir_list foo_list;
> + *
> + * struct item_t {
> + *     int foo;
> + *     nir_link link;
> + * };
> + * struct item_t item1, item2, item3;
> + *
> + * nir_list_init(&foo_list);
> + * nir_list_insert_after(&foo_list, &item1.link);   // Pushes item1 at the head
> + * nir_list_insert_after(&foo_list, &item2.link);   // Pushes item2 at the head
> + * nir_list_insert_after(&item2.link, &item3.link); // Pushes item3 after item2
> + * \endcode
> + *
> + * The list now looks like [item2, item3, item1]
> + *
> + * Iterate the list in ascending order:
> + * \code
> + * item_t *item;
> + * nir_list_foreach(item, foo_list, link) {
> + *     Do_something_with_item(item);
> + * }
> + * \endcode
> + */
> +typedef struct nir_list {
> +   struct nir_link *tail;
> +   struct nir_link *head;
> +} nir_list;
> +
> +typedef struct nir_link {
> +   struct nir_link *prev;
> +   struct nir_link *next;
> +} nir_link;
> +
> +static inline void
> +nir_list_init(nir_list *list)
> +{
> +   list->head = (nir_link *)list;
> +   list->tail = (nir_link *)list;
> +}
> +
> +static inline bool
> +nir_list_is_empty(nir_list *list)
> +{
> +   return list->head == (nir_link *)list;
> +}
> +
> +static inline void
> +nir_link_init(nir_link *link)
> +{
> +   link->next = NULL;
> +   link->prev = NULL;
> +}
> +
> +static inline void
> +nir_link_insert_after(nir_link *link_in_list, nir_link *after)
> +{
> +   assert(after->next == NULL && after->prev == NULL);
> +   after->prev = link_in_list;
> +   after->next = link_in_list->next;
> +   link_in_list->next = after;
> +   after->next->prev = after;
> +}
> +
> +static inline void
> +nir_link_insert_before(nir_link *link_in_list, nir_link *before)
> +{
> +   assert(before->next == NULL && before->prev == NULL);
> +   before->next = link_in_list;
> +   before->prev = link_in_list->prev;
> +   link_in_list->prev = before;
> +   before->prev->next = before;
> +}
> +
> +static inline void
> +nir_link_remove(nir_link *link)
> +{
> +   link->prev->next = link->next;
> +   link->next->prev = link->prev;
> +   nir_link_init(link);
> +}
> +
> +static inline void
> +nir_list_push_head(nir_list *list, nir_link *elem)
> +{
> +   nir_link_insert_after((nir_link *)list, elem);
> +}
> +
> +static inline void
> +nir_list_push_tail(nir_list *list, nir_link *elem)
> +{
> +   nir_link_insert_before((nir_link *)list, elem);
> +}
> +
> +#define nir_list_foreach(__type, __node, __field, __list)                  \
> +   for (__type *__node = exec_node_data(__type, (__list)->head, __field);  \
> +        &(__node)->__field != (nir_link *)(__list);                        \
> +        __node = exec_node_data(__type, (__node)->__field.next, __field))
> +
> +#define nir_list_foreach_safe(__type, __node, __field, __list)             \
> +   for (__type *__node = exec_node_data(__type, (__list)->head, __field),  \
> +               *__next = exec_node_data(__type, (__node)->__field.next, __field); \
> +        &(__node)->__field != (nir_link *)(__list);                        \
> +        __node = __next,                                                   \
> +        __next = exec_node_data(__type, (__next)->__field.next, __field))
> +
> +static inline unsigned
> +nir_list_length(nir_list *list)
> +{
> +   unsigned count = 0;
> +   for (nir_link *l = list->head; l != (nir_link *)list; l = l->next)
> +      count++;
> +   return count;
> +}
> +
> +static inline void
> +nir_list_validate(nir_list *list)
> +{
> +   assert(list->head->prev == (nir_link *)list);
> +   assert(list->tail->next == (nir_link *)list);
> +   for (nir_link *l = list->head; l != (nir_link *)list; l = l->next)
> +      assert(l->next->prev == l && l->prev->next == l);
> +}
> +
> +#endif /* _NIR_LIST_H_ */
> --
> 2.3.6
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev