[Mesa-dev] [PATCH 01/47] nir: rewrite nir_foreach_block and friends
Connor Abbott
cwabbott0 at gmail.com
Wed Apr 13 19:15:26 UTC 2016
On Wed, Apr 13, 2016 at 2:49 PM, Jason Ekstrand <jason at jlekstrand.net> wrote:
>
>
> 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.
Well, from looking through nir.h it seems like most of the iterators
use the same order I did. The only ones that don't are
nir_foreach_variable() and nir_foreach_variable_safe(). I'd rather
keep them consistent with each other now, and then change everything
at once. As-is, it would stick out like a sore thumb, especially since
after this series it's a relatively common pattern to do:
nir_foreach_block(impl, block) {
nir_foreach_instr(block, instr) {
...
}
}
After all, changing the other iterators would have to be a flag-day
rename touching basically everything already, so it can't be much
worse if you change nir_foreach_block() as well.
>
>> > > +
>> > > +#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
>
>
More information about the mesa-dev
mailing list