This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [graphite] Get graphite backend working again [scalar variable handling]


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?


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]