This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
RE: [graphite] Get graphite backend working again [scalar variable handling]
Hi Jan,
On Mon, 2008-08-18 at 17:37 -0500, Sjodin, Jan wrote:
> > As the current code generation does not support conditional
> > statements,
> > we fail to generate code for them.
> >
> > Who will work on that one?
>
> I am working on this.
Great!
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;
ï------------------------
ïThe problem seems to become more complicate, if there exist two or more
ivs.
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.
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.
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.
2. If we can ignore the scalar variables, we can also ignore their
dependencies. So we have more freedom to schedule the bbs.
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?