Tobias Grosser wrote:
> I would like to improve the way how we handle scalar variables and ivs
> during graphite transformation.
> I am not sure, if I got it right and where to put my code in the backend.
> So it would be great, if you could read over my ideas.
>
> The problem:
> ============
> In graphite we represent the complete loop structure using polyhedrons to
> apply our transformations.
> To go back to gimple we have to generate new loop structures and delete
> the old loop structures.
> One step is to remove old ivs and generate new ones.
>
>
> Example:
>
> 1. original bb:
> ------------------------
> D.1918_7 = a[i_22];
> D.1919_8 = D.1918_7 + 1;
> a[j_21] = D.1919_8;
> j_9 = j_21 + 1;
> ------------------------
>
>
> 2. Add new ivs
>
> graphiteIV_1 = PHI (0, graphiteIV_2)
> ------------------------
> D.1918_7 = a[i_22];
> D.1919_8 = D.1918_7 + 1;
> a[j_21] = D.1919_8;
> j_9 = j_21 + 1;
> ------------------------
> graphiteIV_2 = graphiteIV_1 + 1
>
>
> 3. Move ivs usages to the ivs.
>
> graphiteIV_1 = PHI (0, graphiteIV_2)
> ------------------------
> D.1918_7 = a[i_22];
> D.1919_8 = D.1918_7 + 1;
> a[graphiteIV_1] = D.1919_8;
> j_9 = j_21 + 1;
> ------------------------
> graphiteIV_2 = graphiteIV_1 + 1
>
>
> 4. remove ivs (Here {j_9, j_21})
>
> ------------------------
> D.1918_7 = a[i_22];157235101 disconnected
> D.1919_8 = D.1918_7 + 1;
> a[graphiteIV_1] = D.1919_8;
> ------------------------
That's my understanding as well.
> The problem seems to become more complicate, if there exist two or more
> ivs.
More complicated if you want to make sure all dead variables are removed
(with the associated definition code), but is it critical, given that a
PRE/CSE will clean this up afterwards?
> How I would like to solve it:
> =============================
>
> During gimple->graphite transformation we ignore all scalar variables,
> that we can represent using scev. (These contain also all the ivs)
>
> Here {D.1918_7, D.1919_8} are not representable, as they depend on the
> value of a[i_22]. Therefore we can not ignore them.
> But {j_9, j_21} will be representable and we ignore them.
>
> During graphite we have all ivs virtually removed.
This would be very good. I fully agree, yet more motivated by dependence
removal rather than clean-output goals (cf. PRE/CSE argument).
> The next step is during code generation:
> We remove all scalar variables, we ignored before, and recreate for the
> places, where they where used, new scalar variables, that depend on the
> new ivs.
The tricky part might be that those so-called "new variables" have to be
named like the old ones, although plenty of new variables will have
been synthesized in the mean time.
> Why remove all and not just the ivs?
> ------------------------------------
>
> There are two points.
>
> 1. Detection ivs is much work. So I prefer this general algorithm, as I
> hope it is easier to implement and runs faster.
Agree.
> 2. If we can ignore the scalar variables, we can also ignore their
> dependencies. So we have more freedom to schedule the bbs.
Exactly.
>
> See you
> Tobi
>
> P.S.: To start working on my code I would like to get block-0.c running.
> Jan, can I help you with anything?
