Series is Reviewed-by: Connor Abbott <[email protected]>
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 <[email protected]> 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 ([email protected]) > + * > + */ > + > +#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 ([email protected]) > + * > + */ > + > +#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 > [email protected] > http://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list [email protected] http://lists.freedesktop.org/mailman/listinfo/mesa-dev
