[Mesa-dev] [PATCH 08/10] nir: add a loop unrolling pass

[Timothy Arceri]

On Thu, 2016-10-06 at 13:25 +1100, Timothy Arceri wrote:

<snip>

> > > +
> > > +static void
> > > +update_remap_tables(bool is_first_iteration, struct hash_table
> > > *remap_table,
> > > +                    struct hash_table *phi_remap,
> > > +                    struct hash_table *src_before_loop,
> > > +                    struct hash_table *src_after_loop)
> > > +{
> > > +   struct hash_entry *phi_hte;
> > > +   hash_table_foreach(phi_remap, phi_hte) {
> > > +      struct hash_entry *remap_hte =
> > > +         _mesa_hash_table_search(remap_table, phi_hte->data);
> > > +
> > > +      nir_ssa_def *phi_def = (nir_ssa_def *) phi_hte->key;
> > > +      nir_ssa_def *phi_src = (nir_ssa_def *) phi_hte->data;
> > > +
> > > +      if (!remap_hte && is_first_iteration) {
> > > +         _mesa_hash_table_insert(remap_table, phi_hte->key,
> > > phi_hte->data);
> > > +         continue;
> > > +      }
> > > +
> > > +      if (is_phi_src_phi_from_loop_header(phi_def, phi_src)) {
> > > +          /* After copy propagation we can end up with phis
> > > inside
> > > loops
> > > +           * that look like this:
> > > +           *
> > > +           *    vec1 32 ssa_14 = phi block_0: ssa_9, block_4:
> > > ssa_13
> > > +           *    vec1 32 ssa_13 = phi block_0: ssa_8, block_4:
> > > ssa_12
> > > +           *    vec1 32 ssa_12 = phi block_0: ssa_7, block_4:
> > > ssa_11
> > > +           *    vec1 32 ssa_11 = phi block_0: ssa_6, block_4:
> > > ssa_14
> > > +           *
> > > +           * For each iteration of the loop we need to update
> > > the
> > > phi and
> > > +           * cloning remap tables so that we use the correct src
> > > for the
> > > +           * next iteration.
> > > +           */
> > > +          struct hash_entry *sbl_hte =
> > > +             _mesa_hash_table_search(src_before_loop, phi_hte-
> > > > 
> > > > data);
> > > +          _mesa_hash_table_insert(remap_table, phi_hte->key,
> > > sbl_hte->data);
> > > +
> > > +          struct hash_entry *sal_hte =
> > > +             _mesa_hash_table_search(src_after_loop, phi_hte-
> > > > 
> > > > data);
> > > +          phi_hte->data = sal_hte->data;
> > > +      } else if (remap_hte) {
> > > +          _mesa_hash_table_insert(remap_table, phi_hte->key,
> > > remap_hte->data);
> > > +      }
> > 
> > Hrm... I understand the problem but I would have thought we could
> > have done it with fewer remap tables... 
> >  My naeve idea would be to do
> > as follows:
> > 
> > In create_remap_tables, populate the remap table with phi_dst ->
> > phi_src where phi_src is the source with pred == block_before_loop.
> > 
> > In update_remap_tables, populate the remap table with phi_dst ->
> > remap(phi_src) where phi_src is the soure with pred ==
> > continue_block
> > 
> > Am I just over-simplifying things here?
> 
> I believe you are. The remap table is updated by the cloning process
> our job here is to simply make sure it is in the right state before
> we
> do the next clone. The key thing is that we are always cloning the
> original header/body (were are not cloning the previous clone).
> 
> So the above code is acting more as a reset, or initialisation of the
> remap table for the next iteration of the loop (although we want to
> keep what it already contains).
> 
> Essentially the code is doing what you are suggesting you are just
> leaving out the part where updating phi_src with the source from pred
> == continue_block only works for the first iteration. For the next
> iteration we use the value already in the remap table after the
> clone,
> or the case where there is no mov i.e no clone we need to set things
> up
> manually using the src_before_loop/src_after_loop hash tables.
> 
> Does this make sense? 
> 
> It would be nice if we could distill this into an easy to follow
> comment to put on the function itself, happy for your input to help
> get
> to something that not only I understand :)
> 
> How about something like:
> 
> /*
>  * The remap_table is updated by the cloning process, our job here
> is 
>  * to simply make sure it is in the right state before we do the next
>  * clone. The key thing is that we are always cloning the original 
>  * header/body (were are not cloning the previous clone).
>  *
>  * Since the cloning process is updating the remap_table we can think
>  * of this function as acting more as a reset, or initialisation of
> the
>  * remap table for the next iteration of the loop (although we want
> to
>  * keep what it already contains).
>  *
>  * After the first iteration we use the value already in remap_table
> to
>  * update the phi_src with the new src from the previous clone, or in
>  * the case where there is no mov i.e no clone, we update the 
>  * remap_table using the src_before_loop/src_after_loop hash tables.
>  */
> 

More simply here is an explanation of the functions of each individual
table:

- remap_table: is used during cloning, and for remapping lcssa phis
after unrolling.

- phi_remap: is used to remap the remap_table each iteration so that is
can be used to clone the original loop contents by pointing ssa_defs to
the latest src from the previous clone.

- src_{after,before}_loop: are use to remap both the remap_table and
phi_remap table when copy propagation has reduce the movs to phis that
simply reorder the src each iteration.