[Mesa-dev] [PATCH 01/47] nir: rewrite nir_foreach_block and friends
Connor Abbott
cwabbott0 at gmail.com
Wed Apr 13 04:34:40 UTC 2016
Previously, these were functions which took a callback. This meant that
the per-block code had to be in a separate function, and all the data
that you wanted to pass in had to be a single void *. They walked the
control flow tree recursively, doing a depth-first search, and called
the callback in a preorder, matching the order of the original source
code. But since each node in the control flow tree has a pointer to its
parent, we can implement a "get-next" and "get-previous" method that
does the same thing that the recursive function did with no state at
all. This lets us rewrite nir_foreach_block() as a simple for loop,
which lets us greatly simplify its users in some cases. This does
require us to rewrite every user, although the transformation from the
old nir_foreach_block() to the new nir_foreach_block() is mostly
trivial.
One subtlety, though, is that the new nir_foreach_block() won't handle
the case where the current block is deleted, which the old one could.
There's a new nir_foreach_block_safe() which implements the standard
trick for solving this. Most users don't modify control flow, though, so
they won't need it. Right now, only opt_select_peephole needs it.
Signed-off-by: Connor Abbott <cwabbott0 at gmail.com>
---
src/compiler/nir/nir.c | 186 +++++++++++++++++++++++++++++--------------------
src/compiler/nir/nir.h | 57 ++++++++++++---
2 files changed, 159 insertions(+), 84 deletions(-)
diff --git a/src/compiler/nir/nir.c b/src/compiler/nir/nir.c
index b67916d..ea8aa88 100644
--- a/src/compiler/nir/nir.c
+++ b/src/compiler/nir/nir.c
@@ -1468,109 +1468,143 @@ nir_ssa_def_rewrite_uses_after(nir_ssa_def *def, nir_src new_src,
nir_if_rewrite_condition(use_src->parent_if, new_src);
}
-static bool foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
- bool reverse, void *state);
-
-static inline bool
-foreach_if(nir_if *if_stmt, nir_foreach_block_cb cb, bool reverse, void *state)
+nir_block *
+nir_block_cf_tree_next(nir_block *block)
{
- if (reverse) {
- foreach_list_typed_reverse_safe(nir_cf_node, node, node,
- &if_stmt->else_list) {
- if (!foreach_cf_node(node, cb, reverse, state))
- return false;
- }
+ if (block == NULL) {
+ /* nir_foreach_block_safe() will call this function on a NULL block
+ * after the last iteration, but it won't use the result so just return
+ * NULL here.
+ */
+ return NULL;
+ }
- foreach_list_typed_reverse_safe(nir_cf_node, node, node,
- &if_stmt->then_list) {
- if (!foreach_cf_node(node, cb, reverse, state))
- return false;
- }
- } else {
- foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->then_list) {
- if (!foreach_cf_node(node, cb, reverse, state))
- return false;
- }
+ nir_cf_node *cf_next = nir_cf_node_next(&block->cf_node);
+ if (cf_next)
+ return nir_cf_node_cf_tree_first(cf_next);
- foreach_list_typed_safe(nir_cf_node, node, node, &if_stmt->else_list) {
- if (!foreach_cf_node(node, cb, reverse, state))
- return false;
- }
+ nir_cf_node *parent = block->cf_node.parent;
+
+ switch (parent->type) {
+ case nir_cf_node_if: {
+ /* Are we at the end of the if? Go to the beginning of the else */
+ nir_if *if_stmt = nir_cf_node_as_if(parent);
+ if (&block->cf_node == nir_if_last_then_node(if_stmt))
+ return nir_cf_node_as_block(nir_if_first_else_node(if_stmt));
+ /* We must be at the end of the else, fallthrough */
}
- return true;
+ case nir_cf_node_loop: {
+ nir_cf_node *node = nir_cf_node_next(parent);
+ return nir_cf_node_as_block(node);
+ }
+
+ case nir_cf_node_function:
+ return NULL;
+
+ default:
+ unreachable("unknown cf node type");
+ }
}
-static inline bool
-foreach_loop(nir_loop *loop, nir_foreach_block_cb cb, bool reverse, void *state)
+nir_block *
+nir_block_cf_tree_prev(nir_block *block)
{
- if (reverse) {
- foreach_list_typed_reverse_safe(nir_cf_node, node, node, &loop->body) {
- if (!foreach_cf_node(node, cb, reverse, state))
- return false;
- }
- } else {
- foreach_list_typed_safe(nir_cf_node, node, node, &loop->body) {
- if (!foreach_cf_node(node, cb, reverse, state))
- return false;
- }
+ if (block == NULL) {
+ /* do this for consistency with nir_block_cf_tree_next() */
+ return NULL;
}
- return true;
+ nir_cf_node *cf_prev = nir_cf_node_prev(&block->cf_node);
+ if (cf_prev)
+ return nir_cf_node_cf_tree_last(cf_prev);
+
+ nir_cf_node *parent = block->cf_node.parent;
+
+ switch (parent->type) {
+ case nir_cf_node_if: {
+ /* Are we at the beginning of the else? Go to the end of the if */
+ nir_if *if_stmt = nir_cf_node_as_if(parent);
+ if (&block->cf_node == nir_if_first_else_node(if_stmt))
+ return nir_cf_node_as_block(nir_if_last_then_node(if_stmt));
+ /* We must be at the beginning of the if, fallthrough */
+ }
+
+ case nir_cf_node_loop: {
+ nir_cf_node *node = nir_cf_node_prev(parent);
+ return nir_cf_node_as_block(node);
+ }
+
+ case nir_cf_node_function:
+ return NULL;
+
+ default:
+ unreachable("unknown cf node type");
+ }
}
-static bool
-foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
- bool reverse, void *state)
+nir_block *nir_cf_node_cf_tree_first(nir_cf_node *node)
{
switch (node->type) {
- case nir_cf_node_block:
- return cb(nir_cf_node_as_block(node), state);
- case nir_cf_node_if:
- return foreach_if(nir_cf_node_as_if(node), cb, reverse, state);
- case nir_cf_node_loop:
- return foreach_loop(nir_cf_node_as_loop(node), cb, reverse, state);
- break;
+ case nir_cf_node_function: {
+ nir_function_impl *impl = nir_cf_node_as_function(node);
+ return nir_start_block(impl);
+ }
- default:
- unreachable("Invalid CFG node type");
- break;
+ case nir_cf_node_if: {
+ nir_if *if_stmt = nir_cf_node_as_if(node);
+ return nir_cf_node_as_block(nir_if_first_then_node(if_stmt));
}
- return false;
-}
+ case nir_cf_node_loop: {
+ nir_loop *loop = nir_cf_node_as_loop(node);
+ return nir_cf_node_as_block(nir_loop_first_cf_node(loop));
+ }
+
+ case nir_cf_node_block: {
+ return nir_cf_node_as_block(node);
+ }
-bool
-nir_foreach_block_in_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
- void *state)
-{
- return foreach_cf_node(node, cb, false, state);
+ default:
+ unreachable("unknown node type");
+ }
}
-bool
-nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb cb, void *state)
+nir_block *nir_cf_node_cf_tree_last(nir_cf_node *node)
{
- foreach_list_typed_safe(nir_cf_node, node, node, &impl->body) {
- if (!foreach_cf_node(node, cb, false, state))
- return false;
+ switch (node->type) {
+ case nir_cf_node_function: {
+ nir_function_impl *impl = nir_cf_node_as_function(node);
+ return nir_impl_last_block(impl);
}
- return cb(impl->end_block, state);
-}
+ case nir_cf_node_if: {
+ nir_if *if_stmt = nir_cf_node_as_if(node);
+ return nir_cf_node_as_block(nir_if_last_else_node(if_stmt));
+ }
-bool
-nir_foreach_block_reverse(nir_function_impl *impl, nir_foreach_block_cb cb,
- void *state)
-{
- if (!cb(impl->end_block, state))
- return false;
+ case nir_cf_node_loop: {
+ nir_loop *loop = nir_cf_node_as_loop(node);
+ return nir_cf_node_as_block(nir_loop_first_cf_node(loop));
+ }
+
+ case nir_cf_node_block: {
+ return nir_cf_node_as_block(node);
+ }
- foreach_list_typed_reverse_safe(nir_cf_node, node, node, &impl->body) {
- if (!foreach_cf_node(node, cb, true, state))
- return false;
+ default:
+ unreachable("unknown node type");
}
+}
- return true;
+nir_block *nir_cf_node_cf_tree_next(nir_cf_node *node)
+{
+ if (node->type == nir_cf_node_block)
+ return nir_cf_node_cf_tree_first(nir_cf_node_next(node));
+ else if (node->type == nir_cf_node_function)
+ return NULL;
+ else
+ return nir_cf_node_as_block(nir_cf_node_next(node));
}
nir_if *
diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
index c19ae59..54cbcba 100644
--- a/src/compiler/nir/nir.h
+++ b/src/compiler/nir/nir.h
@@ -1513,6 +1513,12 @@ nir_start_block(nir_function_impl *impl)
return (nir_block *) exec_list_get_head(&impl->body);
}
+static inline nir_block *
+nir_impl_last_block(nir_function_impl *impl)
+{
+ return (nir_block *) exec_list_get_tail(&impl->body);
+}
+
static inline nir_cf_node *
nir_cf_node_next(nir_cf_node *node)
{
@@ -2077,14 +2083,49 @@ void nir_ssa_def_rewrite_uses(nir_ssa_def *def, nir_src new_src);
void nir_ssa_def_rewrite_uses_after(nir_ssa_def *def, nir_src new_src,
nir_instr *after_me);
-/* visits basic blocks in source-code order */
-typedef bool (*nir_foreach_block_cb)(nir_block *block, void *state);
-bool nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb cb,
- void *state);
-bool nir_foreach_block_reverse(nir_function_impl *impl, nir_foreach_block_cb cb,
- void *state);
-bool nir_foreach_block_in_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,
- void *state);
+/*
+ * finds the next basic block in source-code order, returns NULL if there is
+ * none
+ */
+
+nir_block *nir_block_cf_tree_next(nir_block *block);
+
+/* Performs the opposite of nir_block_cf_tree_next() */
+
+nir_block *nir_block_cf_tree_prev(nir_block *block);
+
+/* Gets the first block in a CF node in source-code order */
+
+nir_block *nir_cf_node_cf_tree_first(nir_cf_node *node);
+
+/* Gets the last block in a CF node in source-code order */
+
+nir_block *nir_cf_node_cf_tree_last(nir_cf_node *node);
+
+/* Gets the next block after a CF node in source-code order */
+
+nir_block *nir_cf_node_cf_tree_next(nir_cf_node *node);
+
+/* Macros for loops that visit blocks in source-code order */
+
+#define nir_foreach_block(impl, block) \
+ for (nir_block *block = nir_start_block(impl); block != NULL; \
+ block = nir_block_cf_tree_next(block))
+
+#define nir_foreach_block_safe(impl, block) \
+ for (nir_block *block = nir_start_block(impl), \
+ *next = nir_block_cf_tree_next(block); \
+ block != NULL; \
+ block = next, next = nir_block_cf_tree_next(block))
+
+#define nir_foreach_block_reverse(impl, block) \
+ for (nir_block *block = nir_impl_last_block(impl); block != NULL; \
+ block = nir_block_cf_tree_prev(block))
+
+#define nir_foreach_block_in_cf_node(node, block) \
+ for (nir_block *block = nir_cf_node_cf_tree_first(node); \
+ block != nir_cf_node_cf_tree_next(node); \
+ block = nir_block_cf_tree_next(block))
/* If the following CF node is an if, this function returns that if.
* Otherwise, it returns NULL.
--
2.5.0
More information about the mesa-dev
mailing list