On Apr 12, 2016 9:36 PM, "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 */ Maybe assert this? > } > > - return true; > + case nir_cf_node_loop: { > + nir_cf_node *node = nir_cf_node_next(parent); > + return nir_cf_node_as_block(node); No need for the temporary; just compose functions. > + } And you can ditch the braces if you do. In general in this patch I'd like to see the unneeded braces go. > + > + 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 */ Assert > + } > + > + case nir_cf_node_loop: { > + nir_cf_node *node = nir_cf_node_prev(parent); > + return nir_cf_node_as_block(node); Compose > + } > + > + 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); Compose > + } > > - 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); Compose > } > > - 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)); Should be loop_last_cf_node. :-) > + } > + > + 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); > +/* > + * 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 ><a href="mailto:mesa-dev@lists.freedesktop.org"> mesa-dev@lists.freedesktop.org</a> ><a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev"> https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a>