<div dir="ltr"> <div class="gmail_extra"> <div class="gmail_quote">On Wed, Apr 13, 2016 at 2:06 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com" target="_blank">cwabbott0@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div class="h5">On Wed, Apr 13, 2016 at 3:20 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote: > > > On Wed, Apr 13, 2016 at 12:15 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote: >> >> On Wed, Apr 13, 2016 at 2:49 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> >> wrote: >> > >> > >> > On Wed, Apr 13, 2016 at 8:15 AM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> >> > wrote: >> >> >> >> >> >> On Apr 13, 2016 4:57 AM, "Rob Clark" <<a href="mailto:robdclark@gmail.com">robdclark@gmail.com</a>> wrote: >> >> > >> >> > On Wed, Apr 13, 2016 at 12:34 AM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> >> >> > 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 <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> >> >> > > --- >> >> > > 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(). > > > Yes, I know and I personally find that order more natural. But I think > consistency with other languages is important too. > >> >> 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. > > > 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 </div></div>Well, I could make the change, but at this point it would be a bit more involved. I'd have to figure out how to get the list of files changed with each commit and then run a sed job on only them (otherwise I'd re-swap the arguments for everything else), and then amend each commit. Probably doable, but it would take some work to make it automated. On the other hand, it's just a simple(r) sed job for you, and you'll have to write a lot of very similar sed jobs anyways. <div class=""><div class="h5"></div></div></blockquote><div> </div><div>I just rebased your patches (I grabbed the v2 from your <a href="http://freedesktop.org">freedesktop.org</a>) on latest master and sedjob'd them to switch the order of parameters. You can find it here: <a href="https://cgit.freedesktop.org/~jekstrand/mesa/log/?h=wip/nir-foreach-block-v3">https://cgit.freedesktop.org/~jekstrand/mesa/log/?h=wip/nir-foreach-block-v3</a> </div><div> </div><div>--Jason </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class=""><div class="h5"> > >> >> > >> >> > > + >> >> > > +#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 >> >> > > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> >> >> > > <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> >> >> > _______________________________________________ >> >> > mesa-dev mailing list >> >> > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> >> >> > <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> >> > >> > > > </div></div></blockquote></div> </div></div>