On Wed, 2008-08-20 at 09:10 +0200, Albert Cohen wrote:
> 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?
You are right. May be we can ignore that step completely.
>
> > 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).
Yes, that's also my important point. Later I hope to get rid of all
dependencies between scalar variables, but let's start with the easier
ones, already representable using scev.
>
> > 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 is there a need to name the new ones like the old ones? The only
reason I can think about is debugging. And I am not sure if their exists
a strong relation between old an new ones, that makes it reasonable to
call them identical. During all the code motion, we ignored the scalar
variables completely, and the recreation using scev has only a weak
relation to the original variables. So I think we may get completely new
ones as for me it does not make sense to keep these relation.
But you seem to have a different opinion. What makes you think, the new
ones have to be called like the old ones? What relation do you see?
>
> > 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?
>
