[Mesa-dev] [PATCH 1/5] nir/worklist: Split out the type-independent parts

Thomas Helland thomashelland90 at gmail.com
Tue Jul 14 15:08:05 PDT 2015


Now, nir_block_worklist is just a thin wraper around nir_worklist.
We can now use nir_worklist also for SSA definitions.

Signed-off-by: Connor Abbott <cwabbott0 at gmail.com>

V2: Correct comments in more places
    Add file to makefile
    Fix EOF blank line
    idx -> index

Signed-off-by: Thomas Helland <thomashelland90 at gmail.com>
---
 src/glsl/Makefile.sources         |   1 +
 src/glsl/nir/nir_block_worklist.h | 112 ++++++++++++++++++++++++++++++++++++++
 src/glsl/nir/nir_live_variables.c |   2 +-
 src/glsl/nir/nir_worklist.c       |  78 +++++++++++---------------
 src/glsl/nir/nir_worklist.h       |  44 ++++++++-------
 5 files changed, 169 insertions(+), 68 deletions(-)
 create mode 100644 src/glsl/nir/nir_block_worklist.h

diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
index d784a81..9ee03bc 100644
--- a/src/glsl/Makefile.sources
+++ b/src/glsl/Makefile.sources
@@ -23,6 +23,7 @@ NIR_FILES = \
 	nir/nir.c \
 	nir/nir.h \
 	nir/nir_array.h \
+	nir/nir_block_worklist.h \
 	nir/nir_builder.h \
 	nir/nir_constant_expressions.h \
 	nir/nir_dominance.c \
diff --git a/src/glsl/nir/nir_block_worklist.h b/src/glsl/nir/nir_block_worklist.h
new file mode 100644
index 0000000..370caf8
--- /dev/null
+++ b/src/glsl/nir/nir_block_worklist.h
@@ -0,0 +1,112 @@
+/*
+ * Copyright © 2014 Connor Abbott
+ *
+ * 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:
+ *    Connor Abbott (cwabbott0 at gmail.com)
+ *
+ */
+
+#include "nir_worklist.h"
+
+#pragma once
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef nir_worklist nir_block_worklist;
+
+static inline void
+nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
+                        void *mem_ctx)
+{
+   nir_worklist_init(w, num_blocks, mem_ctx);
+}
+
+static inline void
+nir_block_worklist_fini(nir_block_worklist *w)
+{
+   nir_worklist_fini(w);
+}
+
+static bool
+block_worklist_add_block(nir_block *block, void *w)
+{
+   nir_worklist_push_tail((nir_worklist *)w, block, block->index);
+   return true;
+}
+
+static inline void
+nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl)
+{
+   nir_foreach_block(impl, block_worklist_add_block, w);
+}
+
+static inline bool
+nir_block_worklist_is_empty(nir_block_worklist *w)
+{
+   return nir_worklist_is_empty(w);
+}
+
+static inline void
+nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block)
+{
+   nir_worklist_push_head(w, block, block->index);
+}
+
+static inline nir_block *
+nir_block_worklist_peek_head(nir_block_worklist *w)
+{
+   return (nir_block *) nir_worklist_peek_head(w);
+}
+
+static inline nir_block *
+nir_block_worklist_pop_head(nir_block_worklist *w)
+{
+   nir_block *block = nir_block_worklist_peek_head(w);
+   nir_worklist_pop_head(w, block->index);
+   return block;
+}
+
+static inline void
+nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block)
+{
+   nir_worklist_push_tail(w, block, block->index);
+}
+
+static inline nir_block *
+nir_block_worklist_peek_tail(nir_block_worklist *w)
+{
+   return (nir_block *) nir_worklist_peek_tail(w);
+}
+
+static inline nir_block *
+nir_block_worklist_pop_tail(nir_block_worklist *w)
+{
+   nir_block *block = nir_block_worklist_peek_tail(w);
+   nir_worklist_pop_tail(w, block->index);
+   return block;
+}
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/src/glsl/nir/nir_live_variables.c b/src/glsl/nir/nir_live_variables.c
index 1c96dcf..ef5c1af 100644
--- a/src/glsl/nir/nir_live_variables.c
+++ b/src/glsl/nir/nir_live_variables.c
@@ -25,7 +25,7 @@
  */
 
 #include "nir.h"
-#include "nir_worklist.h"
+#include "nir_block_worklist.h"
 #include "nir_vla.h"
 
 /*
diff --git a/src/glsl/nir/nir_worklist.c b/src/glsl/nir/nir_worklist.c
index 3087a1d..ffd1a60 100644
--- a/src/glsl/nir/nir_worklist.c
+++ b/src/glsl/nir/nir_worklist.c
@@ -28,44 +28,30 @@
 #include "nir_worklist.h"
 
 void
-nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
+nir_worklist_init(nir_worklist *w, unsigned num_entries,
                         void *mem_ctx)
 {
-   w->size = num_blocks;
+   w->size = num_entries;
    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);
+   w->entries_present = rzalloc_array(mem_ctx, BITSET_WORD,
+                                     BITSET_WORDS(num_entries));
+   w->entries = ralloc_array(mem_ctx, void *, num_entries);
 }
 
 void
-nir_block_worklist_fini(nir_block_worklist *w)
+nir_worklist_fini(nir_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);
+   ralloc_free(w->entries_present);
+   ralloc_free(w->entries);
 }
 
 void
-nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block)
+nir_worklist_push_head(nir_worklist *w, void *entry, unsigned index)
 {
-   /* Pushing a block we already have is a no-op */
-   if (BITSET_TEST(w->blocks_present, block->index))
+   /* Pushing a entry we already have is a no-op */
+   if (BITSET_TEST(w->entries_present, index))
       return;
 
    assert(w->count < w->size);
@@ -77,20 +63,20 @@ nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block)
 
    w->count++;
 
-   w->blocks[w->start] = block;
-   BITSET_SET(w->blocks_present, block->index);
+   w->entries[w->start] = entry;
+   BITSET_SET(w->entries_present, index);
 }
 
-nir_block *
-nir_block_worklist_peek_head(const nir_block_worklist *w)
+void *
+nir_worklist_peek_head(const nir_worklist *w)
 {
    assert(w->count > 0);
 
-   return w->blocks[w->start];
+   return w->entries[w->start];
 }
 
-nir_block *
-nir_block_worklist_pop_head(nir_block_worklist *w)
+void *
+nir_worklist_pop_head(nir_worklist *w, unsigned index)
 {
    assert(w->count > 0);
 
@@ -99,15 +85,15 @@ nir_block_worklist_pop_head(nir_block_worklist *w)
    w->start = (w->start + 1) % w->size;
    w->count--;
 
-   BITSET_CLEAR(w->blocks_present, w->blocks[head]->index);
-   return w->blocks[head];
+   BITSET_CLEAR(w->entries_present, index);
+   return w->entries[head];
 }
 
 void
-nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block)
+nir_worklist_push_tail(nir_worklist *w, void *entry, unsigned index)
 {
-   /* Pushing a block we already have is a no-op */
-   if (BITSET_TEST(w->blocks_present, block->index))
+   /* Pushing a entry we already have is a no-op */
+   if (BITSET_TEST(w->entries_present, index))
       return;
 
    assert(w->count < w->size);
@@ -116,22 +102,22 @@ nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block)
 
    unsigned tail = (w->start + w->count - 1) % w->size;
 
-   w->blocks[tail] = block;
-   BITSET_SET(w->blocks_present, block->index);
+   w->entries[tail] = entry;
+   BITSET_SET(w->entries_present, index);
 }
 
-nir_block *
-nir_block_worklist_peek_tail(const nir_block_worklist *w)
+void *
+nir_worklist_peek_tail(const nir_worklist *w)
 {
    assert(w->count > 0);
 
    unsigned tail = (w->start + w->count - 1) % w->size;
 
-   return w->blocks[tail];
+   return w->entries[tail];
 }
 
-nir_block *
-nir_block_worklist_pop_tail(nir_block_worklist *w)
+void *
+nir_worklist_pop_tail(nir_worklist *w, unsigned index)
 {
    assert(w->count > 0);
 
@@ -139,6 +125,6 @@ nir_block_worklist_pop_tail(nir_block_worklist *w)
 
    w->count--;
 
-   BITSET_CLEAR(w->blocks_present, w->blocks[tail]->index);
-   return w->blocks[tail];
+   BITSET_CLEAR(w->entries_present, index);
+   return w->entries[tail];
 }
diff --git a/src/glsl/nir/nir_worklist.h b/src/glsl/nir/nir_worklist.h
index 829bff2..f415d16 100644
--- a/src/glsl/nir/nir_worklist.h
+++ b/src/glsl/nir/nir_worklist.h
@@ -36,53 +36,55 @@
 extern "C" {
 #endif
 
-/** Represents a double-ended queue of unique blocks
+/** Represents a double-ended queue of unique indexed entries
  *
- * 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.
+ * The worklist datastructure 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.  In order for this to work, the
+ * entries must have an index that's given to the worker functions.
  */
 typedef struct {
    /* The total size of the worklist */
    unsigned size;
 
-   /* The number of blocks currently in the worklist */
+   /* The number of entries currently in the worklist */
    unsigned count;
 
-   /* The offset in the array of blocks at which the list starts */
+   /* The offset in the array of entries at which the list starts */
    unsigned start;
 
-   /* A bitset of all of the blocks currently present in the worklist */
-   BITSET_WORD *blocks_present;
+   /* A bitset of all of the entries currently present in the worklist */
+   BITSET_WORD *entries_present;
 
    /* The actual worklist */
-   nir_block **blocks;
-} nir_block_worklist;
+   void **entries;
+} nir_worklist;
 
-void nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
+void nir_worklist_init(nir_worklist *w, unsigned num_entries,
                              void *mem_ctx);
-void nir_block_worklist_fini(nir_block_worklist *w);
+void nir_worklist_fini(nir_worklist *w);
 
-void nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl);
+void nir_worklist_add_all(nir_worklist *w, nir_function_impl *impl);
 
 static inline bool
-nir_block_worklist_is_empty(const nir_block_worklist *w)
+nir_worklist_is_empty(const nir_worklist *w)
 {
    return w->count == 0;
 }
 
-void nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block);
+void nir_worklist_push_head(nir_worklist *w, void *entry, unsigned index);
 
-nir_block *nir_block_worklist_peek_head(const nir_block_worklist *w);
+void *nir_worklist_peek_head(const nir_worklist *w);
 
-nir_block *nir_block_worklist_pop_head(nir_block_worklist *w);
+/* Note that peek_head() must be called first to get the index */
+void *nir_worklist_pop_head(nir_worklist *w, unsigned index);
 
-void nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block);
+void nir_worklist_push_tail(nir_worklist *w, void *entry, unsigned index);
 
-nir_block *nir_block_worklist_peek_tail(const nir_block_worklist *w);
+void *nir_worklist_peek_tail(const nir_worklist *w);
 
-nir_block *nir_block_worklist_pop_tail(nir_block_worklist *w);
+/* Note that peek_tail() must be called first to get the index */
+void *nir_worklist_pop_tail(nir_worklist *w, unsigned index);
 
 #ifdef __cplusplus
 } /* extern "C" */
-- 
2.4.5



More information about the mesa-dev mailing list