<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 13, 2016 at 12:15 PM, Connor Abbott <span dir="ltr"><<a href="mailto:cwabbott0@gmail.com" target="_blank">cwabbott0@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">On Wed, Apr 13, 2016 at 2:49 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote:<br>
><br>
><br>
> On Wed, Apr 13, 2016 at 8:15 AM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>><br>
> wrote:<br>
>><br>
>><br>
>> On Apr 13, 2016 4:57 AM, "Rob Clark" <<a href="mailto:robdclark@gmail.com">robdclark@gmail.com</a>> wrote:<br>
>> ><br>
>> > On Wed, Apr 13, 2016 at 12:34 AM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>><br>
>> > wrote:<br>
>> > > Previously, these were functions which took a callback. This meant<br>
>> > > that<br>
>> > > the per-block code had to be in a separate function, and all the data<br>
>> > > that you wanted to pass in had to be a single void *. They walked the<br>
>> > > control flow tree recursively, doing a depth-first search, and called<br>
>> > > the callback in a preorder, matching the order of the original source<br>
>> > > code. But since each node in the control flow tree has a pointer to<br>
>> > > its<br>
>> > > parent, we can implement a "get-next" and "get-previous" method that<br>
>> > > does the same thing that the recursive function did with no state at<br>
>> > > all. This lets us rewrite nir_foreach_block() as a simple for loop,<br>
>> > > which lets us greatly simplify its users in some cases. This does<br>
>> > > require us to rewrite every user, although the transformation from the<br>
>> > > old nir_foreach_block() to the new nir_foreach_block() is mostly<br>
>> > > trivial.<br>
>> > ><br>
>> > > One subtlety, though, is that the new nir_foreach_block() won't handle<br>
>> > > the case where the current block is deleted, which the old one could.<br>
>> > > There's a new nir_foreach_block_safe() which implements the standard<br>
>> > > trick for solving this. Most users don't modify control flow, though,<br>
>> > > so<br>
>> > > they won't need it. Right now, only opt_select_peephole needs it.<br>
>> > ><br>
>> > > Signed-off-by: Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>><br>
>> > > ---<br>
>> > >  src/compiler/nir/nir.c | 186<br>
>> > > +++++++++++++++++++++++++++++--------------------<br>
>> > >  src/compiler/nir/nir.h |  57 ++++++++++++---<br>
>> > >  2 files changed, 159 insertions(+), 84 deletions(-)<br>
>> > ><br>
>> > > diff --git a/src/compiler/nir/nir.c b/src/compiler/nir/nir.c<br>
>> > > index b67916d..ea8aa88 100644<br>
>> > > --- a/src/compiler/nir/nir.c<br>
>> > > +++ b/src/compiler/nir/nir.c<br>
>> > > @@ -1468,109 +1468,143 @@ nir_ssa_def_rewrite_uses_after(nir_ssa_def<br>
>> > > *def, nir_src new_src,<br>
>> > >        nir_if_rewrite_condition(use_src->parent_if, new_src);<br>
>> > >  }<br>
>> > ><br>
>> > > -static bool foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb<br>
>> > > cb,<br>
>> > > -                            bool reverse, void *state);<br>
>> > > -<br>
>> > > -static inline bool<br>
>> > > -foreach_if(nir_if *if_stmt, nir_foreach_block_cb cb, bool reverse,<br>
>> > > void *state)<br>
>> > > +nir_block *<br>
>> > > +nir_block_cf_tree_next(nir_block *block)<br>
>> > >  {<br>
>> > > -   if (reverse) {<br>
>> > > -      foreach_list_typed_reverse_safe(nir_cf_node, node, node,<br>
>> > > -                                      &if_stmt->else_list) {<br>
>> > > -         if (!foreach_cf_node(node, cb, reverse, state))<br>
>> > > -            return false;<br>
>> > > -      }<br>
>> > > +   if (block == NULL) {<br>
>> > > +      /* nir_foreach_block_safe() will call this function on a NULL<br>
>> > > block<br>
>> > > +       * after the last iteration, but it won't use the result so<br>
>> > > just return<br>
>> > > +       * NULL here.<br>
>> > > +       */<br>
>> > > +      return NULL;<br>
>> > > +   }<br>
>> > ><br>
>> > > -      foreach_list_typed_reverse_safe(nir_cf_node, node, node,<br>
>> > > -                                      &if_stmt->then_list) {<br>
>> > > -         if (!foreach_cf_node(node, cb, reverse, state))<br>
>> > > -            return false;<br>
>> > > -      }<br>
>> > > -   } else {<br>
>> > > -      foreach_list_typed_safe(nir_cf_node, node, node,<br>
>> > > &if_stmt->then_list) {<br>
>> > > -         if (!foreach_cf_node(node, cb, reverse, state))<br>
>> > > -            return false;<br>
>> > > -      }<br>
>> > > +   nir_cf_node *cf_next = nir_cf_node_next(&block->cf_node);<br>
>> > > +   if (cf_next)<br>
>> > > +      return nir_cf_node_cf_tree_first(cf_next);<br>
>> > ><br>
>> > > -      foreach_list_typed_safe(nir_cf_node, node, node,<br>
>> > > &if_stmt->else_list) {<br>
>> > > -         if (!foreach_cf_node(node, cb, reverse, state))<br>
>> > > -            return false;<br>
>> > > -      }<br>
>> > > +   nir_cf_node *parent = block->cf_node.parent;<br>
>> > > +<br>
>> > > +   switch (parent->type) {<br>
>> > > +   case nir_cf_node_if: {<br>
>> > > +      /* Are we at the end of the if? Go to the beginning of the else<br>
>> > > */<br>
>> > > +      nir_if *if_stmt = nir_cf_node_as_if(parent);<br>
>> > > +      if (&block->cf_node == nir_if_last_then_node(if_stmt))<br>
>> > > +         return<br>
>> > > nir_cf_node_as_block(nir_if_first_else_node(if_stmt));<br>
>> > > +      /* We must be at the end of the else, fallthrough */<br>
>> > >     }<br>
>> > ><br>
>> > > -   return true;<br>
>> > > +   case nir_cf_node_loop: {<br>
>> > > +      nir_cf_node *node = nir_cf_node_next(parent);<br>
>> > > +      return nir_cf_node_as_block(node);<br>
>> > > +   }<br>
>> > > +<br>
>> > > +   case nir_cf_node_function:<br>
>> > > +      return NULL;<br>
>> > > +<br>
>> > > +   default:<br>
>> > > +      unreachable("unknown cf node type");<br>
>> > > +   }<br>
>> > >  }<br>
>> > ><br>
>> > > -static inline bool<br>
>> > > -foreach_loop(nir_loop *loop, nir_foreach_block_cb cb, bool reverse,<br>
>> > > void *state)<br>
>> > > +nir_block *<br>
>> > > +nir_block_cf_tree_prev(nir_block *block)<br>
>> > >  {<br>
>> > > -   if (reverse) {<br>
>> > > -      foreach_list_typed_reverse_safe(nir_cf_node, node, node,<br>
>> > > &loop->body) {<br>
>> > > -         if (!foreach_cf_node(node, cb, reverse, state))<br>
>> > > -            return false;<br>
>> > > -      }<br>
>> > > -   } else {<br>
>> > > -      foreach_list_typed_safe(nir_cf_node, node, node, &loop->body) {<br>
>> > > -         if (!foreach_cf_node(node, cb, reverse, state))<br>
>> > > -            return false;<br>
>> > > -      }<br>
>> > > +   if (block == NULL) {<br>
>> > > +      /* do this for consistency with nir_block_cf_tree_next() */<br>
>> > > +      return NULL;<br>
>> > >     }<br>
>> > ><br>
>> > > -   return true;<br>
>> > > +   nir_cf_node *cf_prev = nir_cf_node_prev(&block->cf_node);<br>
>> > > +   if (cf_prev)<br>
>> > > +      return nir_cf_node_cf_tree_last(cf_prev);<br>
>> > > +<br>
>> > > +   nir_cf_node *parent = block->cf_node.parent;<br>
>> > > +<br>
>> > > +   switch (parent->type) {<br>
>> > > +   case nir_cf_node_if: {<br>
>> > > +      /* Are we at the beginning of the else? Go to the end of the if<br>
>> > > */<br>
>> > > +      nir_if *if_stmt = nir_cf_node_as_if(parent);<br>
>> > > +      if (&block->cf_node == nir_if_first_else_node(if_stmt))<br>
>> > > +         return nir_cf_node_as_block(nir_if_last_then_node(if_stmt));<br>
>> > > +      /* We must be at the beginning of the if, fallthrough */<br>
>> > > +   }<br>
>> > > +<br>
>> > > +   case nir_cf_node_loop: {<br>
>> > > +      nir_cf_node *node = nir_cf_node_prev(parent);<br>
>> > > +      return nir_cf_node_as_block(node);<br>
>> > > +   }<br>
>> > > +<br>
>> > > +   case nir_cf_node_function:<br>
>> > > +      return NULL;<br>
>> > > +<br>
>> > > +   default:<br>
>> > > +      unreachable("unknown cf node type");<br>
>> > > +   }<br>
>> > >  }<br>
>> > ><br>
>> > > -static bool<br>
>> > > -foreach_cf_node(nir_cf_node *node, nir_foreach_block_cb cb,<br>
>> > > -                bool reverse, void *state)<br>
>> > > +nir_block *nir_cf_node_cf_tree_first(nir_cf_node *node)<br>
>> > >  {<br>
>> > >     switch (node->type) {<br>
>> > > -   case nir_cf_node_block:<br>
>> > > -      return cb(nir_cf_node_as_block(node), state);<br>
>> > > -   case nir_cf_node_if:<br>
>> > > -      return foreach_if(nir_cf_node_as_if(node), cb, reverse, state);<br>
>> > > -   case nir_cf_node_loop:<br>
>> > > -      return foreach_loop(nir_cf_node_as_loop(node), cb, reverse,<br>
>> > > state);<br>
>> > > -      break;<br>
>> > > +   case nir_cf_node_function: {<br>
>> > > +      nir_function_impl *impl = nir_cf_node_as_function(node);<br>
>> > > +      return nir_start_block(impl);<br>
>> > > +   }<br>
>> > ><br>
>> > > -   default:<br>
>> > > -      unreachable("Invalid CFG node type");<br>
>> > > -      break;<br>
>> > > +   case nir_cf_node_if: {<br>
>> > > +      nir_if *if_stmt = nir_cf_node_as_if(node);<br>
>> > > +      return nir_cf_node_as_block(nir_if_first_then_node(if_stmt));<br>
>> > >     }<br>
>> > ><br>
>> > > -   return false;<br>
>> > > -}<br>
>> > > +   case nir_cf_node_loop: {<br>
>> > > +      nir_loop *loop = nir_cf_node_as_loop(node);<br>
>> > > +      return nir_cf_node_as_block(nir_loop_first_cf_node(loop));<br>
>> > > +   }<br>
>> > > +<br>
>> > > +   case nir_cf_node_block: {<br>
>> > > +      return nir_cf_node_as_block(node);<br>
>> > > +   }<br>
>> > ><br>
>> > > -bool<br>
>> > > -nir_foreach_block_in_cf_node(nir_cf_node *node, nir_foreach_block_cb<br>
>> > > cb,<br>
>> > > -                             void *state)<br>
>> > > -{<br>
>> > > -   return foreach_cf_node(node, cb, false, state);<br>
>> > > +   default:<br>
>> > > +      unreachable("unknown node type");<br>
>> > > +   }<br>
>> > >  }<br>
>> > ><br>
>> > > -bool<br>
>> > > -nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb cb,<br>
>> > > void *state)<br>
>> > > +nir_block *nir_cf_node_cf_tree_last(nir_cf_node *node)<br>
>> > >  {<br>
>> > > -   foreach_list_typed_safe(nir_cf_node, node, node, &impl->body) {<br>
>> > > -      if (!foreach_cf_node(node, cb, false, state))<br>
>> > > -         return false;<br>
>> > > +   switch (node->type) {<br>
>> > > +   case nir_cf_node_function: {<br>
>> > > +      nir_function_impl *impl = nir_cf_node_as_function(node);<br>
>> > > +      return nir_impl_last_block(impl);<br>
>> > >     }<br>
>> > ><br>
>> > > -   return cb(impl->end_block, state);<br>
>> > > -}<br>
>> > > +   case nir_cf_node_if: {<br>
>> > > +      nir_if *if_stmt = nir_cf_node_as_if(node);<br>
>> > > +      return nir_cf_node_as_block(nir_if_last_else_node(if_stmt));<br>
>> > > +   }<br>
>> > ><br>
>> > > -bool<br>
>> > > -nir_foreach_block_reverse(nir_function_impl *impl,<br>
>> > > nir_foreach_block_cb cb,<br>
>> > > -                          void *state)<br>
>> > > -{<br>
>> > > -   if (!cb(impl->end_block, state))<br>
>> > > -      return false;<br>
>> > > +   case nir_cf_node_loop: {<br>
>> > > +      nir_loop *loop = nir_cf_node_as_loop(node);<br>
>> > > +      return nir_cf_node_as_block(nir_loop_first_cf_node(loop));<br>
>> > > +   }<br>
>> > > +<br>
>> > > +   case nir_cf_node_block: {<br>
>> > > +      return nir_cf_node_as_block(node);<br>
>> > > +   }<br>
>> > ><br>
>> > > -   foreach_list_typed_reverse_safe(nir_cf_node, node, node,<br>
>> > > &impl->body) {<br>
>> > > -      if (!foreach_cf_node(node, cb, true, state))<br>
>> > > -         return false;<br>
>> > > +   default:<br>
>> > > +      unreachable("unknown node type");<br>
>> > >     }<br>
>> > > +}<br>
>> > ><br>
>> > > -   return true;<br>
>> > > +nir_block *nir_cf_node_cf_tree_next(nir_cf_node *node)<br>
>> > > +{<br>
>> > > +   if (node->type == nir_cf_node_block)<br>
>> > > +      return nir_cf_node_cf_tree_first(nir_cf_node_next(node));<br>
>> > > +   else if (node->type == nir_cf_node_function)<br>
>> > > +      return NULL;<br>
>> > > +   else<br>
>> > > +      return nir_cf_node_as_block(nir_cf_node_next(node));<br>
>> > >  }<br>
>> > ><br>
>> > >  nir_if *<br>
>> > > diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h<br>
>> > > index c19ae59..54cbcba 100644<br>
>> > > --- a/src/compiler/nir/nir.h<br>
>> > > +++ b/src/compiler/nir/nir.h<br>
>> > > @@ -1513,6 +1513,12 @@ nir_start_block(nir_function_impl *impl)<br>
>> > >     return (nir_block *) exec_list_get_head(&impl->body);<br>
>> > >  }<br>
>> > ><br>
>> > > +static inline nir_block *<br>
>> > > +nir_impl_last_block(nir_function_impl *impl)<br>
>> > > +{<br>
>> > > +   return (nir_block *) exec_list_get_tail(&impl->body);<br>
>> > > +}<br>
>> > > +<br>
>> > >  static inline nir_cf_node *<br>
>> > >  nir_cf_node_next(nir_cf_node *node)<br>
>> > >  {<br>
>> > > @@ -2077,14 +2083,49 @@ void nir_ssa_def_rewrite_uses(nir_ssa_def<br>
>> > > *def, nir_src new_src);<br>
>> > >  void nir_ssa_def_rewrite_uses_after(nir_ssa_def *def, nir_src<br>
>> > > new_src,<br>
>> > >                                      nir_instr *after_me);<br>
>> > ><br>
>> > > -/* visits basic blocks in source-code order */<br>
>> > > -typedef bool (*nir_foreach_block_cb)(nir_block *block, void *state);<br>
>> > > -bool nir_foreach_block(nir_function_impl *impl, nir_foreach_block_cb<br>
>> > > cb,<br>
>> > > -                       void *state);<br>
>> > > -bool nir_foreach_block_reverse(nir_function_impl *impl,<br>
>> > > nir_foreach_block_cb cb,<br>
>> > > -                               void *state);<br>
>> > > -bool nir_foreach_block_in_cf_node(nir_cf_node *node,<br>
>> > > nir_foreach_block_cb cb,<br>
>> > > -                                  void *state);<br>
>> ><br>
>> ><br>
>> > so, I like the new iterator macros, but this is one giant massive<br>
>> > unbisectable flag-day change :-(<br>
>> ><br>
>> > I'd prefer an approach that kept the old fxns implemented in terms of<br>
>> > the new macros at the beginning of the patchset, then removed them<br>
>> > once everyone else was converted.  Which is slightly annoying since<br>
>> > you'd kinda want to use the same names.  But less of a pita wrt new<br>
>> > nir passes that haven't been pushed yet (I've got a bunch.. I'm not<br>
>> > sure if all of Jason's vulkan stuff has landed yet either)<br>
>><br>
>> I think enough Vulkan stuff has landed to make this not terrible but<br>
>> you're right about the scope of things.  How about starting with a patch<br>
>> that renames nir_foreach_block to something else, say<br>
>> nir_foreach_block_call.  Then patch 1 then a patch to implement<br>
>> nir_foreach_block_call in terms of the macro and then the switchover<br>
>> patches.  The rename will have to touch everything but it will be trivially<br>
>> correct. The rest can be incremental.<br>
>><br>
>> That said, I'm still going to look through the patches to see what I think<br>
>> of the end result.<br>
>><br>
>> > BR,<br>
>> > -R<br>
>> ><br>
>> > > +/*<br>
>> > > + * finds the next basic block in source-code order, returns NULL if<br>
>> > > there is<br>
>> > > + * none<br>
>> > > + */<br>
>> > > +<br>
>> > > +nir_block *nir_block_cf_tree_next(nir_block *block);<br>
>> > > +<br>
>> > > +/* Performs the opposite of nir_block_cf_tree_next() */<br>
>> > > +<br>
>> > > +nir_block *nir_block_cf_tree_prev(nir_block *block);<br>
>> > > +<br>
>> > > +/* Gets the first block in a CF node in source-code order */<br>
>> > > +<br>
>> > > +nir_block *nir_cf_node_cf_tree_first(nir_cf_node *node);<br>
>> > > +<br>
>> > > +/* Gets the last block in a CF node in source-code order */<br>
>> > > +<br>
>> > > +nir_block *nir_cf_node_cf_tree_last(nir_cf_node *node);<br>
>> > > +<br>
>> > > +/* Gets the next block after a CF node in source-code order */<br>
>> > > +<br>
>> > > +nir_block *nir_cf_node_cf_tree_next(nir_cf_node *node);<br>
>> > > +<br>
>> > > +/* Macros for loops that visit blocks in source-code order */<br>
>> > > +<br>
>> > > +#define nir_foreach_block(impl, block) \<br>
>> > > +   for (nir_block *block = nir_start_block(impl); block != NULL; \<br>
>> > > +        block = nir_block_cf_tree_next(block))<br>
><br>
><br>
> I'm sorry in advance for this comment, but can we put impl and block in the<br>
> other order.  This is something that's been bothering me for some time now.<br>
> NIR's iterators are inconsistent as to which order the parameters go.  This<br>
> isn't your fault at all; I'm the one who added most of them. :-(  In most<br>
> languages that have a foreach such as C++11, Java, and python, it's usually<br>
> "for (thing : container)" or "for thing in container:".  I think we should<br>
> follow that convention.<br>
><br>
> I'll write the patches to fix the others, but let's do this one correctly.<br>
<br>
</div></div>Well, from looking through nir.h it seems like most of the iterators<br>
use the same order I did. The only ones that don't are<br>
nir_foreach_variable() and nir_foreach_variable_safe().</blockquote><div><br></div><div>Yes, I know and I personally find that order more natural.  But I think consistency with other languages is important too.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> I'd rather<br>
keep them consistent with each other now, and then change everything<br>
at once. As-is, it would stick out like a sore thumb, especially since<br>
after this series it's a relatively common pattern to do:<br>
<br>
nir_foreach_block(impl, block) {<br>
   nir_foreach_instr(block, instr) {<br>
      ...<br>
   }<br>
}<br>
<br>
After all, changing the other iterators would have to be a flag-day<br>
rename touching basically everything already, so it can't be much<br>
worse if you change nir_foreach_block() as well.<br><div class="HOEnZb"><div class="h5"></div></div></blockquote><div><br></div><div>I guess.  However, I don't see why we need to add something now and change the order later.  Other than who has to go make the changes. :-P<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">
><br>
>> > > +<br>
>> > > +#define nir_foreach_block_safe(impl, block) \<br>
>> > > +   for (nir_block *block = nir_start_block(impl), \<br>
>> > > +        *next = nir_block_cf_tree_next(block); \<br>
>> > > +        block != NULL; \<br>
>> > > +        block = next, next = nir_block_cf_tree_next(block))<br>
>> > > +<br>
>> > > +#define nir_foreach_block_reverse(impl, block) \<br>
>> > > +   for (nir_block *block = nir_impl_last_block(impl); block != NULL;<br>
>> > > \<br>
>> > > +        block = nir_block_cf_tree_prev(block))<br>
>> > > +<br>
>> > > +#define nir_foreach_block_in_cf_node(node, block) \<br>
>> > > +   for (nir_block *block = nir_cf_node_cf_tree_first(node); \<br>
>> > > +        block != nir_cf_node_cf_tree_next(node); \<br>
>> > > +        block = nir_block_cf_tree_next(block))<br>
>> > ><br>
>> > >  /* If the following CF node is an if, this function returns that if.<br>
>> > >   * Otherwise, it returns NULL.<br>
>> > > --<br>
>> > > 2.5.0<br>
>> > ><br>
>> > > _______________________________________________<br>
>> > > mesa-dev mailing list<br>
>> > > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
>> > > <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a><br>
>> > _______________________________________________<br>
>> > mesa-dev mailing list<br>
>> > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
>> > <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a><br>
><br>
><br>
</div></div></blockquote></div><br></div></div>