[Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
Jason Ekstrand
jason at jlekstrand.net
Fri Apr 24 19:27:10 PDT 2015
On Apr 24, 2015 4:46 PM, "Rob Clark" <robdclark at gmail.com> wrote:
>
> 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)
I took a quick look through it. While I like the nir_list api a little
better, it would work just as well. I'm not going to quibble to much over
what gets used. I prefer C99 iterators, it's a *lot* better than
simple_list.
--Jason
> > 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150424/74db9565/attachment-0001.html>
More information about the mesa-dev
mailing list