[Mesa-dev] [PATCH 1/2] nir: Add a worklist helper structure
Connor Abbott
cwabbott0 at gmail.com
Thu Jan 15 13:54:00 PST 2015
Series is
Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>
As you know, I have a branch that generalizes this and adds a worklist
for SSA definitions as well. But I think we won't want the SSA-def
worklist for DCE, since just like with phi-node placement we only ever
push something onto the worklist once, and we use a flag on the
instruction both to not put things in the worklist that are already on
the worklist and to delete dead instructions when we're done, so the
bit-set of things in the worklist won't help us. I guess we'll wait on
this until we add a dataflow analysis pass that needs it like my range
analysis pass.
On Thu, Jan 15, 2015 at 10:54 AM, Jason Ekstrand <jason at jlekstrand.net> wrote:
> A worklist is a common concept in optimizations. This adds a structure
> that we can reuse for many different types of optimizations.
> ---
> src/glsl/Makefile.sources | 2 +
> src/glsl/nir/nir_worklist.c | 144 ++++++++++++++++++++++++++++++++++++++++++++
> src/glsl/nir/nir_worklist.h | 91 ++++++++++++++++++++++++++++
> 3 files changed, 237 insertions(+)
> create mode 100644 src/glsl/nir/nir_worklist.c
> create mode 100644 src/glsl/nir/nir_worklist.h
>
> diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
> index 006e947..a951ca7 100644
> --- a/src/glsl/Makefile.sources
> +++ b/src/glsl/Makefile.sources
> @@ -50,6 +50,8 @@ NIR_FILES = \
> $(GLSL_SRCDIR)/nir/nir_split_var_copies.c \
> $(GLSL_SRCDIR)/nir/nir_to_ssa.c \
> $(GLSL_SRCDIR)/nir/nir_validate.c \
> + $(GLSL_SRCDIR)/nir/nir_worklist.c \
> + $(GLSL_SRCDIR)/nir/nir_worklist.h \
> $(GLSL_SRCDIR)/nir/nir_types.cpp \
> $(GLSL_SRCDIR)/nir/glsl_to_nir.cpp \
> $(NIR_GENERATED_FILES)
> diff --git a/src/glsl/nir/nir_worklist.c b/src/glsl/nir/nir_worklist.c
> new file mode 100644
> index 0000000..7f4315d
> --- /dev/null
> +++ b/src/glsl/nir/nir_worklist.c
> @@ -0,0 +1,144 @@
> +/*
> + * 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 (jason at jlekstrand.net)
> + *
> + */
> +
> +#include "nir_worklist.h"
> +
> +void
> +nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
> + void *mem_ctx)
> +{
> + w->size = num_blocks;
> + w->count = 0;
> + w->start = 0;
> +
> + w->blocks_present = rzalloc_array(mem_ctx, BITSET_WORD,
> + BITSET_WORDS(num_blocks));
> + w->blocks = ralloc_array(mem_ctx, nir_block *, num_blocks);
> +}
> +
> +void
> +nir_block_worklist_fini(nir_block_worklist *w)
> +{
> + ralloc_free(w->blocks_present);
> + ralloc_free(w->blocks);
> +}
> +
> +static bool
> +worklist_add_block(nir_block *block, void *w)
> +{
> + nir_block_worklist_push_tail(w, block);
> +
> + return true;
> +}
> +
> +void
> +nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl)
> +{
> + nir_foreach_block(impl, worklist_add_block, w);
> +}
> +
> +void
> +nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block)
> +{
> + /* Pushing a block we already have is a no-op */
> + if (BITSET_TEST(w->blocks_present, block->index))
> + return;
> +
> + assert(w->count < w->size);
> +
> + if (w->start == 0)
> + w->start = w->size - 1;
> + else
> + w->start--;
> +
> + w->count++;
> +
> + w->blocks[w->start] = block;
> + BITSET_SET(w->blocks_present, block->index);
> +}
> +
> +nir_block *
> +nir_block_worklist_peek_head(nir_block_worklist *w)
> +{
> + assert(w->count > 0);
> +
> + return w->blocks[w->start];
> +}
> +
> +nir_block *
> +nir_block_worklist_pop_head(nir_block_worklist *w)
> +{
> + assert(w->count > 0);
> +
> + unsigned head = w->start;
> +
> + w->start = (w->start + 1) % w->size;
> + w->count--;
> +
> + BITSET_CLEAR(w->blocks_present, w->blocks[head]->index);
> + return w->blocks[head];
> +}
> +
> +void
> +nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block)
> +{
> + /* Pushing a block we already have is a no-op */
> + if (BITSET_TEST(w->blocks_present, block->index))
> + return;
> +
> + assert(w->count < w->size);
> +
> + w->count++;
> +
> + unsigned tail = w->start = (w->start + w->count - 1) % w->size;
> +
> + w->blocks[tail] = block;
> + BITSET_SET(w->blocks_present, block->index);
> +}
> +
> +nir_block *
> +nir_block_worklist_peek_tail(nir_block_worklist *w)
> +{
> + assert(w->count > 0);
> +
> + unsigned tail = w->start = (w->start + w->count - 1) % w->size;
> +
> + return w->blocks[tail];
> +}
> +
> +nir_block *
> +nir_block_worklist_pop_tail(nir_block_worklist *w)
> +{
> + assert(w->count > 0);
> +
> + unsigned tail = w->start = (w->start + w->count - 1) % w->size;
> +
> + w->count--;
> +
> + BITSET_CLEAR(w->blocks_present, w->blocks[tail]->index);
> + return w->blocks[tail];
> +}
> diff --git a/src/glsl/nir/nir_worklist.h b/src/glsl/nir/nir_worklist.h
> new file mode 100644
> index 0000000..d5a8568
> --- /dev/null
> +++ b/src/glsl/nir/nir_worklist.h
> @@ -0,0 +1,91 @@
> +/*
> + * 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 (jason at jlekstrand.net)
> + *
> + */
> +
> +#pragma once
> +
> +#ifndef _NIR_WORKLIST_
> +#define _NIR_WORKLIST_
> +
> +#include "nir.h"
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +/** Represents a double-ended queue of unique blocks
> + *
> + * The worklist datastructure guarantees that eacy block is in the queue at
> + * most once. Pushing a block onto either end of the queue is a no-op if
> + * the block is already in the queue. In order for this to work, the
> + * caller must ensure that the blocks are properly indexed.
> + */
> +typedef struct {
> + /* The total size of the worklist */
> + unsigned size;
> +
> + /* The number of blocks currently in the worklist */
> + unsigned count;
> +
> + /* The offset in the array of blocks at which the list starts */
> + unsigned start;
> +
> + /* A bitset of all of the blocks currently present in the worklist */
> + BITSET_WORD *blocks_present;
> +
> + /* The actual worklist */
> + nir_block **blocks;
> +} nir_block_worklist;
> +
> +void nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
> + void *mem_ctx);
> +void nir_block_worklist_fini(nir_block_worklist *w);
> +
> +void nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl);
> +
> +static inline bool
> +nir_block_worklist_is_empty(const nir_block_worklist *w)
> +{
> + return w->count == 0;
> +}
> +
> +void nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block);
> +
> +nir_block *nir_block_worklist_peek_head(nir_block_worklist *w);
> +
> +nir_block *nir_block_worklist_pop_head(nir_block_worklist *w);
> +
> +void nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block);
> +
> +nir_block *nir_block_worklist_peek_tail(nir_block_worklist *w);
> +
> +nir_block *nir_block_worklist_pop_tail(nir_block_worklist *w);
> +
> +#ifdef __cplusplus
> +} /* extern "C" */
> +#endif
> +
> +#endif /* _NIR_WORKLIST_ */
> --
> 2.2.1
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list