[Mesa-dev] [PATCH 01/47] nir: rewrite nir_foreach_block and friends
Jason Ekstrand
jason at jlekstrand.net
Wed Apr 13 15:15:14 UTC 2016
On Apr 13, 2016 4:57 AM, "Rob Clark" <robdclark at gmail.com> wrote:
>
> On Wed, Apr 13, 2016 at 12:34 AM, 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 */
> > }
> >
> > - 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);
>
>
> so, I like the new iterator macros, but this is one giant massive
> unbisectable flag-day change :-(
>
> I'd prefer an approach that kept the old fxns implemented in terms of
> the new macros at the beginning of the patchset, then removed them
> once everyone else was converted. Which is slightly annoying since
> you'd kinda want to use the same names. But less of a pita wrt new
> nir passes that haven't been pushed yet (I've got a bunch.. I'm not
> sure if all of Jason's vulkan stuff has landed yet either)
I think enough Vulkan stuff has landed to make this not terrible but you're
right about the scope of things. How about starting with a patch that
renames nir_foreach_block to something else, say nir_foreach_block_call.
Then patch 1 then a patch to implement nir_foreach_block_call in terms of
the macro and then the switchover patches. The rename will have to touch
everything but it will be trivially correct. The rest can be incremental.
That said, I'm still going to look through the patches to see what I think
of the end result.
> BR,
> -R
>
> > +/*
> > + * 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
> _______________________________________________
> 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/20160413/e47e78f5/attachment-0001.html>
More information about the mesa-dev
mailing list