[Mesa-dev] [PATCH 10/13] nir: add helper for cloning loops
Jason Ekstrand
jason at jlekstrand.net
Tue Aug 30 06:05:57 UTC 2016
I don't think anyone is trying to throw away phi's... I think what Connor
is proposing is more a better interface to this cloning operation than
anything else. Instead of having a separate list of phi's, you can just
pre-populate the remap table before doing the clone. For the first loop
iteration, you add remaps that remap all of the "header phi's" (those in
the first block in the loop) to their values coming from before the loop.
For each subsequent copy operation, you populate the remap table such that
the header phis map to their values from the previous iteration which you
can get from the final state of the remap table after the clone is complete.
This should be completely safe as the only way for a value to propagate
from one iteration to the next is through a header phi and, assuming no
continues, each header phi will have exactly two sources: one from before
the loop and one from the previous iteration.
This would substantially simplify the interface as well as remove the
linear walk over the phi remap table every time we do a remap.
--Jason
On Aug 29, 2016 9:40 PM, "Timothy Arceri" <timothy.arceri at collabora.com>
wrote:
On Mon, 2016-08-29 at 21:06 -0400, Connor Abbott wrote:
> So, you've noticed that your method of handling phi's while cloning
> doesn't handle phi's that point to other phi's in the same block.
> Particularly, something like:
>
> a = phi(b, ...)
> b = phi(a, ...)
>
> which is supposed to swap a and b each iteration. Here's a better
> strategy which should be simpler than this and fixes that problem.
> Create a new remap_table for each iteration of the loop. On the first
> iteration, make all the phi nodes remap to their pre-loop sources
> before cloning the body. On each successive iteration, make each phi
> node map to what the *old* remap table (from the previous iteration)
> says that it's source from the previous iteration remaps to. In
> pseudocode:
>
> nir_cf_list loop_body;
> extract loop body into loop_body
> move loop header instructions (minus phi nodes) into loop_body
>
> struct hash_table *old_remap_table = NULL, *remap_table;
> for each iteration:
> remap_table = new dictionary;
> for each phi in original loop:
> if old_remap_table:
> remap_table[phi] = old_remap_table[phi source pointing to
> end of loop]
> else:
> remap_table[phi] = phi source pointing to block before
> loop
> nir_cf_list cloned_body;
> clone loop_body to cloned_body using remap_table
> insert cloned_body before loop
>
> delete loop_body
> delete loop
I see what you are getting at but what about something like this?
int j = 0;
for (int i=0 ; i < 5; i++) {
...
j++;
if (uniform)
j += 2;
}
I'm not sure we can throw away phis so easily.
>
> This should eliminate the need to expose nir_cf_list_cleanup(),
> stitch_blocks(), etc. publicly as well as the previous patch, and it
> should handle the phi swapping case correctly.
>
>
> On Mon, Aug 29, 2016 at 12:59 AM, Timothy Arceri
> <timothy.arceri at collabora.com> wrote:
> >
> > ---
> > src/compiler/nir/nir.h | 3 +++
> > src/compiler/nir/nir_clone.c | 64
> > +++++++++++++++++++++++++++++++++++++++-----
> > 2 files changed, 60 insertions(+), 7 deletions(-)
> >
> > diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> > index 0ab3ebc..9083bd0 100644
> > --- a/src/compiler/nir/nir.h
> > +++ b/src/compiler/nir/nir.h
> > @@ -2372,6 +2372,9 @@ void nir_print_instr(const nir_instr *instr,
> > FILE *fp);
> >
> > nir_shader *nir_shader_clone(void *mem_ctx, const nir_shader *s);
> > nir_function_impl *nir_function_impl_clone(const nir_function_impl
> > *fi);
> > +void nir_clone_loop_list(struct exec_list *dst, const struct
> > exec_list *list,
> > + struct hash_table *remap_table,
> > + struct hash_table *phi_remap, nir_shader
> > *ns);
> > nir_constant *nir_constant_clone(const nir_constant *c,
> > nir_variable *var);
> > nir_variable *nir_variable_clone(const nir_variable *c, nir_shader
> > *shader);
> >
> > diff --git a/src/compiler/nir/nir_clone.c
> > b/src/compiler/nir/nir_clone.c
> > index 8808333..071afc9 100644
> > --- a/src/compiler/nir/nir_clone.c
> > +++ b/src/compiler/nir/nir_clone.c
> > @@ -35,9 +35,17 @@ typedef struct {
> > /* True if we are cloning an entire shader. */
> > bool global_clone;
> >
> > + /* This allows us to clone a loop body without having to add
> > srcs from
> > + * outside the loop to the remap table. This is useful for loop
> > unrolling.
> > + */
> > + bool allow_remap_fallback;
> > +
> > /* maps orig ptr -> cloned ptr: */
> > struct hash_table *remap_table;
> >
> > + /* used for remaping when cloning loop body for loop unrolling
> > */
> > + struct hash_table *phi_remap_table;
> > +
> > /* List of phi sources. */
> > struct list_head phi_srcs;
> >
> > @@ -46,11 +54,20 @@ typedef struct {
> > } clone_state;
> >
> > static void
> > -init_clone_state(clone_state *state, bool global)
> > +init_clone_state(clone_state *state, struct hash_table
> > *remap_table,
> > + bool global, bool allow_remap_fallback)
> > {
> > state->global_clone = global;
> > - state->remap_table = _mesa_hash_table_create(NULL,
> > _mesa_hash_pointer,
> > - _mesa_key_pointer_
> > equal);
> > + state->allow_remap_fallback = allow_remap_fallback;
> > +
> > + state->phi_remap_table = NULL;
> > + if (remap_table) {
> > + state->remap_table = remap_table;
> > + } else {
> > + state->remap_table = _mesa_hash_table_create(NULL,
> > _mesa_hash_pointer,
> > + _mesa_key_point
> > er_equal);
> > + }
> > +
> > list_inithead(&state->phi_srcs);
> > }
> >
> > @@ -72,16 +89,32 @@ _lookup_ptr(clone_state *state, const void
> > *ptr, bool global)
> > return (void *)ptr;
> >
> > entry = _mesa_hash_table_search(state->remap_table, ptr);
> > - assert(entry && "Failed to find pointer!");
> > if (!entry)
> > - return NULL;
> > + return state->allow_remap_fallback ? (void *)ptr : NULL;
> >
> > return entry->data;
> > }
> >
> > +/**
> > + * Updates a phi remap table used for unrolling loops.
> > + */
> > +static void
> > +update_phi_remap_table(clone_state *state, const void *ptr, void
> > *nptr)
> > +{
> > + if (state->phi_remap_table == NULL)
> > + return;
> > +
> > + struct hash_entry *hte;
> > + hash_table_foreach(state->phi_remap_table, hte) {
> > + if (hte->data == ptr)
> > + hte->data = nptr;
> > + }
> > +}
> > +
> > static void
> > add_remap(clone_state *state, void *nptr, const void *ptr)
> > {
> > + update_phi_remap_table(state, ptr, nptr);
> > _mesa_hash_table_insert(state->remap_table, ptr, nptr);
> > }
> >
> > @@ -613,6 +646,23 @@ fixup_phi_srcs(clone_state *state)
> > assert(list_empty(&state->phi_srcs));
> > }
> >
> > +void
> > +nir_clone_loop_list(struct exec_list *dst, const struct exec_list
> > *list,
> > + struct hash_table *remap_table,
> > + struct hash_table *phi_remap, nir_shader *ns)
> > +{
> > + clone_state state;
> > + init_clone_state(&state, remap_table, false, true);
> > +
> > + /* We use the same shader */
> > + state.ns = ns;
> > + state.phi_remap_table = phi_remap;
> > +
> > + clone_cf_list(&state, dst, list);
> > +
> > + fixup_phi_srcs(&state);
> > +}
> > +
> > static nir_function_impl *
> > clone_function_impl(clone_state *state, const nir_function_impl
> > *fi)
> > {
> > @@ -646,7 +696,7 @@ nir_function_impl *
> > nir_function_impl_clone(const nir_function_impl *fi)
> > {
> > clone_state state;
> > - init_clone_state(&state, false);
> > + init_clone_state(&state, NULL, false, false);
> >
> > /* We use the same shader */
> > state.ns = fi->function->shader;
> > @@ -686,7 +736,7 @@ nir_shader *
> > nir_shader_clone(void *mem_ctx, const nir_shader *s)
> > {
> > clone_state state;
> > - init_clone_state(&state, true);
> > + init_clone_state(&state, NULL, true, false);
> >
> > nir_shader *ns = nir_shader_create(mem_ctx, s->stage, s-
> > >options);
> > state.ns = ns;
> > --
> > 2.7.4
> >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev at lists.freedesktop.org
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
_______________________________________________
mesa-dev mailing list
mesa-dev at lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20160829/bfed539d/attachment-0001.html>
More information about the mesa-dev
mailing list