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

[Jason Ekstrand]

On Mon, Apr 27, 2015 at 11:12 AM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> On Mon, Apr 27, 2015 at 1:36 PM, Eric Anholt <eric at anholt.net> wrote:
>> Jason Ekstrand <jason at 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