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

[Connor Abbott]

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.