Hi Tobi,
On Fri, 29 Jun 2012, Tobias Grosser wrote:
> > +static isl_constraint *
> > +build_linearized_memory_access (isl_map *map, poly_dr_p pdr)
> > +{
> > +}
>
> The function itself looks correct. However, I would personally have returned
> an isl_map instead of an isl_constraint.
As you noticed I modelled all my isl code after the existing PPL code
(which returned an expression here, turned into a conflict in the caller).
I couldn't learn the polyhedral basics, PPL basics, isl basics _and_ the
correct isl idioms on one weekend :) So many thanks for the hints.
> A map {A[i,j] -> [200 * i]} is probably a nicer way to represent a
> transformation from the higher level array type to an actual memory
> reference.
Hmm. This ignores the 'j' input dimension. Can I also have a map ala
{A[i,j] -> [200 * i + j]}? I don't directly see how, as for that I'd need
at least another dimension (the 'L' in the callers map).
> > +pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr)
> > +{
> > + poly_bb_p pbb = PDR_PBB (pdr);
> > + isl_map *map;
> > + isl_set *set;
> > + isl_aff *aff;
> > + isl_space *dc;
> > + isl_constraint *lma, *c;
> > + isl_int islstride;
> > + enum isl_lp_result lpres;
> > + graphite_dim_t time_depth;
> > + unsigned offset, nt;
> > + unsigned i;
> > + /* pdr->accesses: [P1..nb_param,I1..nb_domain]->[a,S1..nb_subscript]
> > + ??? [P] not used for PDRs?
> > + pdr->extent: [a,S1..nb_subscript]
> > + pbb->domain: [P1..nb_param,I1..nb_domain]
> > + pbb->transformed: [P1..nb_param,I1..nb_domain]->[T1..Tnb_sctr]
> > + [T] includes local vars (currently unused)
> > +
> > + First we create [P,I] -> [T,a,S]. */
> > +
> > + map = isl_map_flat_range_product (isl_map_copy (pbb->transformed),
> > + isl_map_copy (pdr->accesses));
> > + /* Add a dimension for L: [P,I] -> [T,a,S,L].*/
> > + map = isl_map_add_dims (map, isl_dim_out, 1);
> > + /* Build a constraint for "lma[S] - L == 0", effectively calculating
> > + L in terms of subscripts. */
> > + lma = build_linearized_memory_access (map, pdr);
> > + /* And add it to the map, so we now have:
> > + [P,I] -> [T,a,S,L] : lma([S]) == L. */
> > + map = isl_map_add_constraint (map, lma);
> > +
> > + /* Then we create [P,I,P',I'] -> [T,a,S,L,T',a',S',L']. */
> > + map = isl_map_flat_product (map, isl_map_copy (map));
>
> Your analysis is here a 1:1 mapping from PPL to isl. That works, but is
> probably not the nicest/conceptually cleanest way to implement this. In
> general, in isl we try to avoid adding/removing individual dimensions
> explicitly.
Yeah, I noticed that, but didn't know how to get around adding the L
dimension (I at least used flat_product for creating the X' dimensions
instead of explicit dimension insertions and moving).
> The canonical way to express such transformations is to create a
> new map and to "apply" this map on the set/map you want to modify. For this
> algorithm, I would start with the pdr->accesses map and 'apply'
> pbb->transformed to map the original iteration space into the scattering
> space.
Let's see if I understand: So, we have [PI]->[aS] (Params, Iteration
domain, alias set, Subscript) as accesses, and we have [PI]->[T]
(Transformed) as the scattering. Indeed what I ideally wanted to have is
a [T]->[aS] mapping, but I couldn't see how to construct such. So you're
saying that I can apply the PI->T to the domain of PI->aS, and that gives
me the T->aS? Probably I was confused by the functional syntax (the ->),
as in normal functions you can't simply apply a function to a functions
domain and expect to get anything sensible out of that. I see that in
your code you reverse the scattering first (T->PI), IIRC that's one thing
I also tried, but I got stuck somewhere.
> I would than apply the isl_map calculated by
> build_linearized_memory_access to map the array to the actual data
> location accessed. Now you create a map 'scattering->scattering' that
> maps from one scattering time point to the next. And apply the map
> 'scattering->memory' on both the range and the domain. You will end up
> with a map memory -> memory.
Yeah. If my above understanding is correct the path is clear.
> Here you can use the deltas function to give you the distances. ;-)
I couldn't figure out from isls user manual what exactly the delta
functions do :) From the description above I think I understand now. Let
me experiment a bit more.
> You can have a look in Polly, where I implement a similar calculation:
>
> http://repo.or.cz/w/polly-mirror.git/blob/HEAD:/lib/Analysis/ScopInfo.cpp#l390
The games you play with projecting out some dimensions are related to
which dimension you want to calculate the stride, right? (As you always
calculate the next scatterting to have n+1 in the last dimension, not an
arbitrary one).
> > +print_isl_map (FILE *f, isl_map *map)
>
> If this is the
> case, you can either use isl_set_dump(set), isl_map_dump(map), ..
There functions weren't documented. Thanks. But I need a file argument
anyway as the plan is to use them also for debug dumps.
> Also, you can get the_isl_ctx, by calling isl_map_get_ctx(map).
Indeed, that occurred to me only later.
> > + /* Even shorter and more correct method: map the iteration domain
> > + through the current scatter, and work on the resulting set. */
> > + isl_set_free (lbset);
> > + lbset = isl_set_apply (isl_set_copy (pbb->domain),
> > + isl_map_copy (pbb->transformed));
> > + lpres = isl_set_min (lbset, aff,&isllb);
> > + lpres = isl_set_max (lbset, aff,&islub);
> > +
> > + isl_int_sub (islub, islub, isllb);
> > + isl_int_add_ui (islub, islub, 1);
>
> This is again modeling the PPL code.
Actually the PPL code translation is the one I removed from my reply here.
The above is what made that code dead and what is in the final version
(with renamed variables and such). Is using _deltas really better? I
would have to construct a map from
lexmin(transformed-domain)->lexmax(transformed-domain), then apply
_delts and the still extract the number.
> > +++ b/gcc/graphite.c
> > @@ -253,6 +253,8 @@ graphite_finalize (bool need_cfg_cleanup_p)
> > print_loops (dump_file, 3);
> > }
> >
> > +isl_ctx *the_isl_ctx;
>
> Why are you creating a global ctx here?
For the printer, before I was aware of the fact that of course all isl
objects know about their context.
Ciao,
Michael.
