#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;
static int
nir_block_ptr_cmp(const void *_a, const void *_b)
{
- nir_block *const *a = _a;
- nir_block *const *b = _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,
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 *
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,
projects / mesa.git / blobdiff