Module: Mesa Branch: main Commit: 04a2c6efb172f20d4be1ac0e1603c2bbaddf1e8c URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=04a2c6efb172f20d4be1ac0e1603c2bbaddf1e8c
Author: Alyssa Rosenzweig <[email protected]> Date: Tue Apr 19 11:57:45 2022 -0400 util: Add a generic worklist implementation Models a double-ended queue of elements from an a list. Based on NIR's worklist data structure. This is useful in most backend compilers for data flow analysis. Using this data structure has several advantages for backends: * Simplicity, avoids open-coding a worklist data structure. * Performance, the data structure is lighter weight than e.g sets * Correctness, e.g. sets are nondeterministic and can cause random bugs. Using a worklist approach at all is good for performance of liveness analysis to avoid performing excess walks over the IR. Signed-off-by: Alyssa Rosenzweig <[email protected]> Reviewed-by: Emma Anholt <[email protected]> Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/16046> --- src/util/meson.build | 2 + src/util/u_worklist.c | 130 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/util/u_worklist.h | 111 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 243 insertions(+) diff --git a/src/util/meson.build b/src/util/meson.build index 1443a890eb2..1b9c68f519b 100644 --- a/src/util/meson.build +++ b/src/util/meson.build @@ -145,6 +145,8 @@ files_mesa_util = files( 'u_cpu_detect.h', 'u_printf.c', 'u_printf.h', + 'u_worklist.c', + 'u_worklist.h', 'vl_vlc.h', 'vl_rbsp.h', 'vma.c', diff --git a/src/util/u_worklist.c b/src/util/u_worklist.c new file mode 100644 index 00000000000..7eea0779fa7 --- /dev/null +++ b/src/util/u_worklist.c @@ -0,0 +1,130 @@ +/* + * Copyright (c) 2022 Collabora Ltd. + * Copyright © 2014 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 ([email protected]) + * + */ + +#include "u_worklist.h" +#include "ralloc.h" + +void +u_worklist_init(u_worklist *w, unsigned num_entries, void *mem_ctx) +{ + w->size = num_entries; + w->count = 0; + w->start = 0; + + w->present = rzalloc_array(mem_ctx, BITSET_WORD, BITSET_WORDS(num_entries)); + w->entries = rzalloc_array(mem_ctx, unsigned *, num_entries); +} + +void +u_worklist_fini(u_worklist *w) +{ + ralloc_free(w->present); + ralloc_free(w->entries); +} + +void +u_worklist_push_head_index(u_worklist *w, unsigned *index) +{ + /* Pushing a block we already have is a no-op */ + if (BITSET_TEST(w->present, *index)) + return; + + assert(w->count < w->size); + + if (w->start == 0) + w->start = w->size - 1; + else + w->start--; + + w->count++; + + w->entries[w->start] = index; + BITSET_SET(w->present, *index); +} + +unsigned * +u_worklist_peek_head_index(const u_worklist *w) +{ + assert(w->count > 0); + + return w->entries[w->start]; +} + +unsigned * +u_worklist_pop_head_index(u_worklist *w) +{ + assert(w->count > 0); + + unsigned head = w->start; + + w->start = (w->start + 1) % w->size; + w->count--; + + BITSET_CLEAR(w->present, *(w->entries[head])); + return w->entries[head]; +} + +void +u_worklist_push_tail_index(u_worklist *w, unsigned *index) +{ + /* Pushing a block we already have is a no-op */ + if (BITSET_TEST(w->present, *index)) + return; + + assert(w->count < w->size); + + w->count++; + + unsigned tail = (w->start + w->count - 1) % w->size; + + w->entries[tail] = index; + BITSET_SET(w->present, *index); +} + +unsigned * +u_worklist_peek_tail_index(const u_worklist *w) +{ + assert(w->count > 0); + + unsigned tail = (w->start + w->count - 1) % w->size; + + return w->entries[tail]; +} + +unsigned * +u_worklist_pop_tail_index(u_worklist *w) +{ + assert(w->count > 0); + + unsigned tail = (w->start + w->count - 1) % w->size; + + w->count--; + + BITSET_CLEAR(w->present, *(w->entries[tail])); + return w->entries[tail]; +} diff --git a/src/util/u_worklist.h b/src/util/u_worklist.h new file mode 100644 index 00000000000..a79848cda65 --- /dev/null +++ b/src/util/u_worklist.h @@ -0,0 +1,111 @@ +/* + * Copyright (c) 2022 Collabora Ltd. + * Copyright © 2014 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 ([email protected]) + * + */ + + +#ifndef _U_WORKLIST_ +#define _U_WORKLIST_ + +#include "util/bitset.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** Represents a double-ended queue of unique entries. Each entry must have a + * unique index in the range [0, num_entries). Internally, entries are tracked + * as pointers to that index (so you can go from the index pointer back to a + * containing structure). This requires index pointers to remain valid while + * they are in the worklist (i.e. no realloc). + * + * The worklist data structure guarantees that each entry is in the queue at + * most once. Pushing an entry onto either end of the queue is a no-op if the + * entry is already in the queue. Internally, the data structure maintains a + * bitset of present entries. + */ +typedef struct { + /* The total size of the worklist */ + unsigned size; + + /* The number of entries currently in the worklist */ + unsigned count; + + /* The offset in the array of entries at which the list starts */ + unsigned start; + + /* A bitset of all of the entries currently present in the worklist */ + BITSET_WORD *present; + + /* The actual worklist */ + unsigned **entries; +} u_worklist; + +void u_worklist_init(u_worklist *w, unsigned num_entries, void *mem_ctx); + +void u_worklist_fini(u_worklist *w); + +static inline bool +u_worklist_is_empty(const u_worklist *w) +{ + return w->count == 0; +} + +void u_worklist_push_head_index(u_worklist *w, unsigned *block); + +unsigned *u_worklist_peek_head_index(const u_worklist *w); + +unsigned *u_worklist_pop_head_index(u_worklist *w); + +unsigned *u_worklist_peek_tail_index(const u_worklist *w); + +void u_worklist_push_tail_index(u_worklist *w, unsigned *block); + +unsigned *u_worklist_pop_tail_index(u_worklist *w); + +#define u_worklist_push_tail(w, block, index) \ + u_worklist_push_tail_index(w, &((block)->index)) + +#define u_worklist_push_head(w, block, index) \ + u_worklist_push_head_index(w, &((block)->index)) + +#define u_worklist_pop_head(w, entry_t, index) \ + container_of(u_worklist_pop_head_index(w), entry_t, index) + +#define u_worklist_pop_tail(w, entry_t, index) \ + container_of(u_worklist_pop_tail_index(w), entry_t, index) + +#define u_worklist_peek_head(w, entry_t, index) \ + container_of(u_worklist_peek_head_index(w), entry_t, index) + +#define u_worklist_peek_tail(w, entry_t, index) \ + container_of(u_worklist_peek_tail_index(w), entry_t, index) + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* _U_WORKLIST_ */
