[Mesa-dev] [PATCH 01/47] nir: rewrite nir_foreach_block and friends
Jason Ekstrand
jason at jlekstrand.net
Wed Apr 13 18:49:01 UTC 2016
On Wed, Apr 13, 2016 at 8:15 AM, Jason Ekstrand <jason at jlekstrand.net>
wrote:
>
> 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))
>
I'm sorry in advance for this comment, but can we put impl and block in the
other order. This is something that's been bothering me for some time
now. NIR's iterators are inconsistent as to which order the parameters
go. This isn't your fault at all; I'm the one who added most of them. :-(
In most languages that have a foreach such as C++11, Java, and python, it's
usually "for (thing : container)" or "for thing in container:". I think we
should follow that convention.
I'll write the patches to fix the others, but let's do this one correctly.
> > +
> > > +#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/8335fa26/attachment-0001.html>
More information about the mesa-dev
mailing list