Re: [Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
On Mon, Apr 27, 2015 at 11:12 AM, Connor Abbott cwabbo...@gmail.com wrote: On Mon, Apr 27, 2015 at 1:36 PM, Eric Anholt e...@anholt.net wrote: Jason Ekstrand ja...@jlekstrand.net writes: 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. Yes, please! I have never liked exec_list, and being gratuitously different from the other projects that we work on (linux, X) is really frustrating. I'd like us to use the same actual names as the kernel does if possible, but I understand if for now we want to have namespaced names for the functions because we might need to interact with two different types of lists. FWIW, if we want to go through with this (which it seems like a pretty big performance win and it gives us a lot more determinism, so why not?) then the consensus is that we should take gallium's u_double_list.h and move it to src/util/list.h. We'd need to clean up a few things, like s/INLINE/inline/ and perhaps make the iterators not ALL_CAPS, and we'd need to add C99-style iterators for NIR, but otherwise it's basically the same as the kernel list. Right. I think I'll take Rob's suggestion to make lower_case iterators for C99 and leave the UPPER_CASE ones for non-c99. the s/INLINE/inline should be easy and I'll get it moved to util/list.h --Jason ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
Jason Ekstrand ja...@jlekstrand.net writes: 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. Yes, please! I have never liked exec_list, and being gratuitously different from the other projects that we work on (linux, X) is really frustrating. I'd like us to use the same actual names as the kernel does if possible, but I understand if for now we want to have namespaced names for the functions because we might need to interact with two different types of lists. signature.asc Description: PGP signature ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
On Mon, Apr 27, 2015 at 1:36 PM, Eric Anholt e...@anholt.net wrote: Jason Ekstrand ja...@jlekstrand.net writes: 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. Yes, please! I have never liked exec_list, and being gratuitously different from the other projects that we work on (linux, X) is really frustrating. I'd like us to use the same actual names as the kernel does if possible, but I understand if for now we want to have namespaced names for the functions because we might need to interact with two different types of lists. FWIW, if we want to go through with this (which it seems like a pretty big performance win and it gives us a lot more determinism, so why not?) then the consensus is that we should take gallium's u_double_list.h and move it to src/util/list.h. We'd need to clean up a few things, like s/INLINE/inline/ and perhaps make the iterators not ALL_CAPS, and we'd need to add C99-style iterators for NIR, but otherwise it's basically the same as the kernel list. ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
[Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
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 000..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 (ja...@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
Re: [Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
On Fri, Apr 24, 2015 at 7:32 PM, Jason Ekstrand ja...@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 000..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 (ja...@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. + */ +
Re: [Mesa-dev] [RFC 6/9] nir: Add an entirely C-based linked list implementation
On Apr 24, 2015 4:46 PM, Rob Clark robdcl...@gmail.com wrote: On Fri, Apr 24, 2015 at 7:32 PM, Jason Ekstrand ja...@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 000..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
