[Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
Jason Ekstrand
jason at jlekstrand.net
Fri Apr 24 16:32:03 PDT 2015
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.
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
More information about the mesa-dev
mailing list