#include "nir.h"
#include "nir_builder.h"
+#include "nir_vla.h"
+
+#define NIR_LOWER_GOTO_IFS_DEBUG 0
struct path {
/** Set of blocks which this path represents
};
struct routes {
+ struct set *outside;
struct path regular;
struct path brk;
struct path cont;
/** Reach set from inside_outside if irreducable */
struct set *reach;
+ /** Outside set from inside_outside if irreducable */
+ struct set *outside;
+
/** True if a skip region starts with this level */
bool skip_start;
bool irreducible;
};
+static int
+nir_block_ptr_cmp(const void *_a, const void *_b)
+{
+ const nir_block *const *a = _a;
+ const nir_block *const *b = _b;
+ return (int)(*a)->index - (int)(*b)->index;
+}
+
+static void
+print_block_set(const struct set *set)
+{
+ printf("{ ");
+ if (set != NULL) {
+ unsigned count = 0;
+ set_foreach(set, entry) {
+ if (count++)
+ printf(", ");
+ printf("%u", ((nir_block *)entry->key)->index);
+ }
+ }
+ printf(" }\n");
+}
+
+/** Return a sorted array of blocks for a set
+ *
+ * Hash set ordering is non-deterministic. We hash based on pointers and so,
+ * if any pointer ever changes from one run to another, the order of the set
+ * may change. Any time we're going to make decisions which may affect the
+ * final structure which may depend on ordering, we should first sort the
+ * blocks.
+ */
+static nir_block **
+sorted_block_arr_for_set(const struct set *block_set, void *mem_ctx)
+{
+ const unsigned num_blocks = block_set->entries;
+ nir_block **block_arr = ralloc_array(mem_ctx, nir_block *, num_blocks);
+ unsigned i = 0;
+ set_foreach(block_set, entry)
+ block_arr[i++] = (nir_block *)entry->key;
+ assert(i == num_blocks);
+ qsort(block_arr, num_blocks, sizeof(*block_arr), nir_block_ptr_cmp);
+ return block_arr;
+}
+
+static nir_block *
+block_for_singular_set(const struct set *block_set)
+{
+ assert(block_set->entries == 1);
+ return (nir_block *)_mesa_set_next_entry(block_set, NULL)->key;
+}
+
/**
* Sets all path variables to reach the target block via a fork
*/
static void
loop_routing_start(struct routes *routing, nir_builder *b,
struct path loop_path, struct set *reach,
- void *mem_ctx)
+ struct set *outside, void *mem_ctx)
{
+ if (NIR_LOWER_GOTO_IFS_DEBUG) {
+ printf("loop_routing_start:\n");
+ printf(" reach = ");
+ print_block_set(reach);
+ printf(" outside = ");
+ print_block_set(outside);
+ printf(" loop_path.reachable = ");
+ print_block_set(loop_path.reachable);
+ printf(" routing->outside = ");
+ print_block_set(routing->outside);
+ printf(" routing->regular.reachable = ");
+ print_block_set(routing->regular.reachable);
+ printf(" routing->brk.reachable = ");
+ print_block_set(routing->brk.reachable);
+ printf(" routing->cont.reachable = ");
+ print_block_set(routing->cont.reachable);
+ printf("\n");
+ }
+
struct routes *routing_backup = ralloc(mem_ctx, struct routes);
*routing_backup = *routing;
bool break_needed = false;
continue_needed = true;
}
+ if (outside && outside->entries) {
+ routing->outside = _mesa_set_clone(routing->outside, routing);
+ set_foreach(outside, entry)
+ _mesa_set_add_pre_hashed(routing->outside, entry->hash, entry->key);
+ }
+
routing->brk = routing_backup->regular;
routing->cont = loop_path;
routing->regular = loop_path;
_mesa_set_add(remaining, block->dom_children[i]);
}
+
+ if (NIR_LOWER_GOTO_IFS_DEBUG) {
+ printf("inside_outside(%u):\n", block->index);
+ printf(" loop_heads = ");
+ print_block_set(loop_heads);
+ printf(" reach = ");
+ print_block_set(reach);
+ printf(" brk_reach = ");
+ print_block_set(brk_reachable);
+ printf(" remaining = ");
+ print_block_set(remaining);
+ printf("\n");
+ }
+
bool progress = true;
while (remaining->entries && progress) {
progress = false;
_mesa_set_add(reach, block->successors[i]);
}
}
+
+ if (NIR_LOWER_GOTO_IFS_DEBUG) {
+ printf("outside(%u) = ", block->index);
+ print_block_set(outside);
+ printf("reach(%u) = ", block->index);
+ print_block_set(reach);
+ }
+}
+
+static struct path_fork *
+select_fork_recur(struct nir_block **blocks, unsigned start, unsigned end,
+ nir_function_impl *impl, bool need_var, void *mem_ctx)
+{
+ if (start == end - 1)
+ return NULL;
+
+ struct path_fork *fork = ralloc(mem_ctx, struct path_fork);
+ fork->is_var = need_var;
+ if (need_var)
+ fork->path_var = nir_local_variable_create(impl, glsl_bool_type(),
+ "path_select");
+
+ unsigned mid = start + (end - start) / 2;
+
+ fork->paths[0].reachable = _mesa_pointer_set_create(fork);
+ for (unsigned i = start; i < mid; i++)
+ _mesa_set_add(fork->paths[0].reachable, blocks[i]);
+ fork->paths[0].fork =
+ select_fork_recur(blocks, start, mid, impl, need_var, mem_ctx);
+
+ fork->paths[1].reachable = _mesa_pointer_set_create(fork);
+ for (unsigned i = mid; i < end; i++)
+ _mesa_set_add(fork->paths[1].reachable, blocks[i]);
+ fork->paths[1].fork =
+ select_fork_recur(blocks, mid, end, impl, need_var, mem_ctx);
+
+ return fork;
}
/**
select_fork(struct set *reachable, nir_function_impl *impl, bool need_var,
void *mem_ctx)
{
- struct path_fork *fork = NULL;
- if (reachable->entries > 1) {
- fork = ralloc(mem_ctx, struct path_fork);
- fork->is_var = need_var;
- if (need_var)
- fork->path_var = nir_local_variable_create(impl, glsl_bool_type(),
- "path_select");
- fork->paths[0].reachable = _mesa_pointer_set_create(fork);
- struct set_entry *entry = NULL;
- while (fork->paths[0].reachable->entries < reachable->entries / 2 &&
- (entry = _mesa_set_next_entry(reachable, entry))) {
- _mesa_set_add_pre_hashed(fork->paths[0].reachable,
- entry->hash, entry->key);
- }
- fork->paths[0].fork = select_fork(fork->paths[0].reachable, impl,
- need_var, mem_ctx);
- fork->paths[1].reachable = _mesa_pointer_set_create(fork);
- while ((entry = _mesa_set_next_entry(reachable, entry))) {
- _mesa_set_add_pre_hashed(fork->paths[1].reachable,
- entry->hash, entry->key);
- }
- fork->paths[1].fork = select_fork(fork->paths[1].reachable, impl,
- need_var, mem_ctx);
- }
- return fork;
+ assert(reachable->entries > 0);
+ if (reachable->entries <= 1)
+ return NULL;
+
+ /* Hash set ordering is non-deterministic. We're about to turn a set into
+ * a tree so we really want things to be in a deterministic ordering.
+ */
+ return select_fork_recur(sorted_block_arr_for_set(reachable, mem_ctx),
+ 0, reachable->entries, impl, need_var, mem_ctx);
}
/**
struct set *old_candidates = _mesa_pointer_set_create(mem_ctx);
while (candidate) {
_mesa_set_add(old_candidates, candidate);
- nir_block *to_be_added = candidate;
- candidate = NULL;
+ /* Start with just the candidate block */
_mesa_set_clear(curr_level->blocks, NULL);
- while (to_be_added) {
- _mesa_set_add(curr_level->blocks, to_be_added);
- to_be_added = NULL;
-
- set_foreach(remaining, entry) {
- nir_block *remaining_block = (nir_block *) entry->key;
- if (!_mesa_set_search(curr_level->blocks, remaining_block)
- && _mesa_set_intersects(remaining_block->dom_frontier,
- curr_level->blocks)) {
- if (_mesa_set_search(old_candidates, remaining_block))
- to_be_added = remaining_block;
- else
- candidate = remaining_block;
+ _mesa_set_add(curr_level->blocks, candidate);
+
+ candidate = NULL;
+ set_foreach(remaining, entry) {
+ nir_block *remaining_block = (nir_block *) entry->key;
+ if (!_mesa_set_search(curr_level->blocks, remaining_block) &&
+ _mesa_set_intersects(remaining_block->dom_frontier,
+ curr_level->blocks)) {
+ if (_mesa_set_search(old_candidates, remaining_block)) {
+ _mesa_set_add(curr_level->blocks, remaining_block);
+ } else {
+ candidate = remaining_block;
break;
}
}
inside_outside((nir_block *) entry->key, loop_heads, remaining,
curr_level->reach, brk_reachable, mem_ctx);
}
+ curr_level->outside = remaining;
_mesa_set_destroy(loop_heads, NULL);
}
* zeroth level
*/
static void
-organize_levels(struct list_head *levels, struct set *remaining,
+organize_levels(struct list_head *levels, struct set *children,
struct set *reach, struct routes *routing,
nir_function_impl *impl, bool is_domminated, void *mem_ctx)
{
+ if (NIR_LOWER_GOTO_IFS_DEBUG) {
+ printf("organize_levels:\n");
+ printf(" children = ");
+ print_block_set(children);
+ printf(" reach = ");
+ print_block_set(reach);
+ }
+
+ /* Duplicate remaining because we're going to destroy it */
+ struct set *remaining = _mesa_set_clone(children, mem_ctx);
+
/* blocks that can be reached by the remaining blocks */
struct set *remaining_frontier = _mesa_pointer_set_create(mem_ctx);
list_addtail(&curr_level->link, levels);
}
+ if (NIR_LOWER_GOTO_IFS_DEBUG) {
+ printf(" levels:\n");
+ list_for_each_entry(struct strct_lvl, level, levels, link) {
+ printf(" ");
+ print_block_set(level->blocks);
+ }
+ printf("\n");
+ }
+
if (skip_targets->entries)
list_last_entry(levels, struct strct_lvl, link)->skip_end = 1;
struct path in_path, void *mem_ctx)
{
if (!in_path.fork) {
- nir_structurize(routing, b, (nir_block *)
- _mesa_set_next_entry(in_path.reachable, NULL)->key,
- mem_ctx);
+ nir_block *block = block_for_singular_set(in_path.reachable);
+ nir_structurize(routing, b, block, mem_ctx);
} else {
assert(!(in_path.fork->is_var &&
strcmp(in_path.fork->path_var->name, "path_select")));
}
struct path in_path = routing->regular;
routing->regular = level->out_path;
- if (level->irreducible)
- loop_routing_start(routing, b, in_path, level->reach, mem_ctx);
+ if (level->irreducible) {
+ loop_routing_start(routing, b, in_path, level->reach,
+ level->outside, mem_ctx);
+ }
select_blocks(routing, b, in_path, mem_ctx);
if (level->irreducible)
loop_routing_end(routing, b);
{
struct set *remaining = _mesa_pointer_set_create(mem_ctx);
for (int i = 0; i < block->num_dom_children; i++) {
- if (!_mesa_set_search(routing->brk.reachable, block->dom_children[i]))
+ if (!_mesa_set_search(routing->outside, block->dom_children[i]))
_mesa_set_add(remaining, block->dom_children[i]);
}
};
_mesa_set_add(loop_path.reachable, block);
- loop_routing_start(routing, b, loop_path, reach, mem_ctx);
+ loop_routing_start(routing, b, loop_path, reach, outside, mem_ctx);
}
struct set *reach = _mesa_pointer_set_create(mem_ctx);
struct routes *routing = ralloc(mem_ctx, struct routes);
*routing = (struct routes) {
+ .outside = empty_set,
.regular.reachable = end_set,
.brk.reachable = empty_set,
.cont.reachable = empty_set,