[Mesa-dev] [PATCH 01/47] nir: rewrite nir_foreach_block and friends
Jason Ekstrand
jason at jlekstrand.net
Fri Apr 15 00:07:48 UTC 2016
On Apr 12, 2016 9:36 PM, "Connor Abbott" <cwabbott0 at gmail.com> wrote:
>
> 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 */
Maybe assert this?
> }
>
> - return true;
> + case nir_cf_node_loop: {
> + nir_cf_node *node = nir_cf_node_next(parent);
> + return nir_cf_node_as_block(node);
No need for the temporary; just compose functions.
> + }
And you can ditch the braces if you do. In general in this patch I'd like
to see the unneeded braces go.
> +
> + 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 */
Assert
> + }
> +
> + case nir_cf_node_loop: {
> + nir_cf_node *node = nir_cf_node_prev(parent);
> + return nir_cf_node_as_block(node);
Compose
> + }
> +
> + 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);
Compose
> + }
>
> - 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);
Compose
> }
>
> - 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));
Should be loop_last_cf_node. :-)
> + }
> +
> + 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
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20160414/1c548bcd/attachment-0001.html>
More information about the mesa-dev
mailing list