[graphite] Weekly phone call notes

[graphite] Weekly phone call notes

[Tobias Grosser]

Hi gcc developers, hi graphities

here are some notes from our weekly phone call. Unfortunately I missed
to send out the notes from the last two phone calls, but I hope to get
them out more regulary. Believe in me! ;-)

http://gcc.gnu.org/wiki/Graphite_Phone_Call/2009_04_29

Attendees: Li, Jan, Konrad, Sebastian, Tobias, David, Christophe 

      * Reductions: Diego OK with going out of SSA. 
              * Patch not yet ready. The higher code coverage exposes an
                IVSTACK bug. 
      * IVStack: Sebastian is working on removing it 
      * Data dependence analysis: Committed to graphite branch. 
              * Not yet enabled, as the data reference still does not
                bootstrap. The lexicographic smaller than constraint is
                not yet added. This is not wrong but very conservative.
                Dependence test should be enabled with
                -fgraphite-identity. 
      * Loop transformations: We need some simple transformations to
        check data dependency analysis. 
              * Pranav? We did not hear anything yet. 
      * Data reference: Last bugs have to be fixed. 
              * Not yet enabled. Blocks data dependence analysis. 
      * PCP: 
              * Jan Implemented simplification/canonicalization for
                expressions. This will allow a systematic translation of
                expressions to constraints. Jan will work on a reduced
                polyhedral interface that is used in PCP. First PCP
                integration in gcc - later extended by reductions. 
                
                No good representation for reductions for the general
                case. Like conditions and PHI nodes (Sebastian) Maybe
                for a subset of the reductions we can add commutativaty
                of operations. 
                
      * Autopar: Li prepared some patches to trigger autopar by
        graphite. 
              * Autopar failed in the graphite branch even without
                graphite enabled. It seems we introduced a bug while
                using some code of it for graphite. The breakage happens
                in the reductions part. 
      * Merge from trunk: 
              * Sebastian wants to work on this Changes in vectorizer
                Last merge 4 months ago Tried mid march but was
                difficult. So stopped because of ENOTIME. 
      * Parts of graphite working well?: The polyhedral part of the
        graphite architecture will be described 
              * in the Tobias' paper at the summit and the PCP part by
                Jan. 
      * Worldwide interest: Cristianno Martins from Brazil showed some
        interest 
              * http://gcc.gnu.org/ml/gcc/2009-04/msg00711.html 
                
              * We already have people from the US, Europe and China
                contributing. 

Re: [graphite] Weekly phone call notes

[Richard Guenther]

On Wed, Apr 29, 2009 at 11:34 PM, Tobias Grosser
<grosser@fim.uni-passau.de> wrote:
> Hi gcc developers, hi graphities
>
> here are some notes from our weekly phone call. Unfortunately I missed
> to send out the notes from the last two phone calls, but I hope to get
> them out more regulary. Believe in me! ;-)
>
> http://gcc.gnu.org/wiki/Graphite_Phone_Call/2009_04_29
>
> Attendees: Li, Jan, Konrad, Sebastian, Tobias, David, Christophe
>
>      * Reductions: Diego OK with going out of SSA.

You will loose all points-to information.  I think going out of SSA is
a very bad idea.

Richard.

>              * Patch not yet ready. The higher code coverage exposes an
>                IVSTACK bug.
>      * IVStack: Sebastian is working on removing it
>      * Data dependence analysis: Committed to graphite branch.
>              * Not yet enabled, as the data reference still does not
>                bootstrap. The lexicographic smaller than constraint is
>                not yet added. This is not wrong but very conservative.
>                Dependence test should be enabled with
>                -fgraphite-identity.
>      * Loop transformations: We need some simple transformations to
>        check data dependency analysis.
>              * Pranav? We did not hear anything yet.
>      * Data reference: Last bugs have to be fixed.
>              * Not yet enabled. Blocks data dependence analysis.
>      * PCP:
>              * Jan Implemented simplification/canonicalization for
>                expressions. This will allow a systematic translation of
>                expressions to constraints. Jan will work on a reduced
>                polyhedral interface that is used in PCP. First PCP
>                integration in gcc - later extended by reductions.
>
>                No good representation for reductions for the general
>                case. Like conditions and PHI nodes (Sebastian) Maybe
>                for a subset of the reductions we can add commutativaty
>                of operations.
>
>      * Autopar: Li prepared some patches to trigger autopar by
>        graphite.
>              * Autopar failed in the graphite branch even without
>                graphite enabled. It seems we introduced a bug while
>                using some code of it for graphite. The breakage happens
>                in the reductions part.
>      * Merge from trunk:
>              * Sebastian wants to work on this Changes in vectorizer
>                Last merge 4 months ago Tried mid march but was
>                difficult. So stopped because of ENOTIME.
>      * Parts of graphite working well?: The polyhedral part of the
>        graphite architecture will be described
>              * in the Tobias' paper at the summit and the PCP part by
>                Jan.
>      * Worldwide interest: Cristianno Martins from Brazil showed some
>        interest
>              * http://gcc.gnu.org/ml/gcc/2009-04/msg00711.html
>
>              * We already have people from the US, Europe and China
>                contributing.
>
>
>
>

Re: [graphite] Weekly phone call notes

[Tobias Grosser]

On Wed, 2009-04-29 at 23:57 +0200, Richard Guenther wrote:
> On Wed, Apr 29, 2009 at 11:34 PM, Tobias Grosser
> <grosser@fim.uni-passau.de> wrote:
> > Hi gcc developers, hi graphities
> >
> > here are some notes from our weekly phone call. Unfortunately I missed
> > to send out the notes from the last two phone calls, but I hope to get
> > them out more regulary. Believe in me! ;-)
> >
> > http://gcc.gnu.org/wiki/Graphite_Phone_Call/2009_04_29
> >
> > Attendees: Li, Jan, Konrad, Sebastian, Tobias, David, Christophe
> >
> >      * Reductions: Diego OK with going out of SSA.
> 
> You will loose all points-to information.  I think going out of SSA is
> a very bad idea.

It makes live a lot easier and it is just for reductions. ;-) But you
are right we should get SSA back.

The point was more if it is the right moment to try to regenerate SSA as
the polyhedral model is actually not single assignment. Or actually the
other way around. More single assignment than SSA.

We postponed this complication or silently hoped that a later pass might
clean up our mess. Actually Sebastian already looked at the output and
there seems to be a later gcc pass, that cleans it up and reintroduces
SSA. But we have to investigate this further or at least document it
correctly. The final goal has to be to get an optimized loop, that is
still in SSA. The way we take is not completely clear yet.

> >              * Patch not yet ready. The higher code coverage exposes an
> >                IVSTACK bug.
> >      * IVStack: Sebastian is working on removing it
> >      * Data dependence analysis: Committed to graphite branch.
> >              * Not yet enabled, as the data reference still does not
> >                bootstrap. The lexicographic smaller than constraint is
> >                not yet added. This is not wrong but very conservative.
> >                Dependence test should be enabled with
> >                -fgraphite-identity.
> >      * Loop transformations: We need some simple transformations to
> >        check data dependency analysis.
> >              * Pranav? We did not hear anything yet.
> >      * Data reference: Last bugs have to be fixed.
> >              * Not yet enabled. Blocks data dependence analysis.
> >      * PCP:
> >              * Jan Implemented simplification/canonicalization for
> >                expressions. This will allow a systematic translation of
> >                expressions to constraints. Jan will work on a reduced
> >                polyhedral interface that is used in PCP. First PCP
> >                integration in gcc - later extended by reductions.
> >
> >                No good representation for reductions for the general
> >                case. Like conditions and PHI nodes (Sebastian) Maybe
> >                for a subset of the reductions we can add commutativaty
> >                of operations.
> >
> >      * Autopar: Li prepared some patches to trigger autopar by
> >        graphite.
> >              * Autopar failed in the graphite branch even without
> >                graphite enabled. It seems we introduced a bug while
> >                using some code of it for graphite. The breakage happens
> >                in the reductions part.
> >      * Merge from trunk:
> >              * Sebastian wants to work on this Changes in vectorizer
> >                Last merge 4 months ago Tried mid march but was
> >                difficult. So stopped because of ENOTIME.
> >      * Parts of graphite working well?: The polyhedral part of the
> >        graphite architecture will be described
> >              * in the Tobias' paper at the summit and the PCP part by
> >                Jan.
> >      * Worldwide interest: Cristianno Martins from Brazil showed some
> >        interest
> >              * http://gcc.gnu.org/ml/gcc/2009-04/msg00711.html
> >
> >              * We already have people from the US, Europe and China
> >                contributing.
> >
> >
> >
> >

Re: [graphite] Weekly phone call notes

[Richard Guenther]

On Thu, Apr 30, 2009 at 12:06 AM, Tobias Grosser
<grosser@fim.uni-passau.de> wrote:
> On Wed, 2009-04-29 at 23:57 +0200, Richard Guenther wrote:
>> On Wed, Apr 29, 2009 at 11:34 PM, Tobias Grosser
>> <grosser@fim.uni-passau.de> wrote:
>> > Hi gcc developers, hi graphities
>> >
>> > here are some notes from our weekly phone call. Unfortunately I missed
>> > to send out the notes from the last two phone calls, but I hope to get
>> > them out more regulary. Believe in me! ;-)
>> >
>> > http://gcc.gnu.org/wiki/Graphite_Phone_Call/2009_04_29
>> >
>> > Attendees: Li, Jan, Konrad, Sebastian, Tobias, David, Christophe
>> >
>> >      * Reductions: Diego OK with going out of SSA.
>>
>> You will loose all points-to information.  I think going out of SSA is
>> a very bad idea.
>
> It makes live a lot easier and it is just for reductions. ;-) But you
> are right we should get SSA back.

I don't see how SSA form makes anything more complicated ;)

> The point was more if it is the right moment to try to regenerate SSA as
> the polyhedral model is actually not single assignment. Or actually the
> other way around. More single assignment than SSA.

Certainly different single assignment.  But for parameters it should be a
non-problem, induction variables are implicit anyway and yes - reductions
may be interesting - but the only thing you need to do is move the
reduction variable "out of SSA" (or rather, by the fact you recognize
a reduction you have done enough work already - code generation
simply needs to create a PHI node for the reduction).

> We postponed this complication or silently hoped that a later pass might
> clean up our mess. Actually Sebastian already looked at the output and
> there seems to be a later gcc pass, that cleans it up and reintroduces
> SSA. But we have to investigate this further or at least document it
> correctly. The final goal has to be to get an optimized loop, that is
> still in SSA. The way we take is not completely clear yet.

Well, the challenge is to retain the per SSA name information across
Graphite.  At some point we need to stop re-computing points-to
information because we cannot do so with retaining IPA results.

Richard.

Re: [graphite] Weekly phone call notes

[Steven Bosscher]

On Thu, Apr 30, 2009 at 12:15 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> Well, the challenge is to retain the per SSA name information across
> Graphite.  At some point we need to stop re-computing points-to
> information because we cannot do so with retaining IPA results.

Not to mention the compile time pains it causes...

Ciao!
Steven

Re: [graphite] Weekly phone call notes

[Daniel Berlin]

On Wed, Apr 29, 2009 at 6:19 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Thu, Apr 30, 2009 at 12:15 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> Well, the challenge is to retain the per SSA name information across
>> Graphite.  At some point we need to stop re-computing points-to
>> information because we cannot do so with retaining IPA results.
>
> Not to mention the compile time pains it causes...

Not to mention it's a lot easier for me to hide bugs if we stop
running it so much ;)

Re: [graphite] Weekly phone call notes

[Sebastian Pop]

On Wed, Apr 29, 2009 at 17:15, Richard Guenther
<richard.guenther@gmail.com> wrote:
> I don't see how SSA form makes anything more complicated ;)
>

One of the difficulties was regenerating the phi nodes after code
hoisting: CLooG optimizes

for (i)
  if (invariant of i)
    s += A[i];

into

if (invariant of i)
  for (i)
    s += A[i];

In the transformed code you have no place to put the phi nodes that
you had after the condition.

Add to this the problem of code duplication that CLooG does sometimes:

if (invariant of i)
  for (i in domain1)
    s += A[i];
  for (i in domain2)
    s += A[i];
  ...

Maintaining the SSA form for s is difficult after such transforms.  If
you figure out a good way to maintain the SSA form, I'm very
interested to hear about.

Thanks,
Sebastian

Re: [graphite] Weekly phone call notes

[Sebastian Pop]

On Wed, Apr 29, 2009 at 16:57, Richard Guenther
<richard.guenther@gmail.com> wrote:
>>
>>      * Reductions: Diego OK with going out of SSA.
>
> You will loose all points-to information.  I think going out of SSA is
> a very bad idea.
>

There is no loss of information: we go out of SSA only for scalar phi
nodes that cannot be represented by scev: for each phi node we
introduce an array with one element.  These arrays are eliminated
after graphite by a scalar cleanup and we obtain again the program
in SSA form.

Handling reductions in SSA form is not an option for the moment.

Sebastian

[graphite] Weekly phone call notes

[Tobias Grosser]

Hi folks, hi graphities,

here you are with the latest notes from our graphite phone call.

It is also available on the wiki:

http://gcc.gnu.org/wiki/Graphite_Phone_Call/2009_05_06

All the best

Tobi


Attendees: Sebastian, Tobias, Christophe, Albert, Li, Jan, Razya,
Konrad, Antoniu 

      * Sebastian: 
              * Working on IVstack removal, 
              * Several other patches like "remove strcmp". (Will be
                committed as soon as possible) 
              * in clast-to-gimple: 
                      * There is a problem finding the type of induction
                        variables and upper bound expressions, as cloog
                        does not carry information about them. 
                              * We will try "unsigned long long" and
                                have to insert casts. (This might
                                trigger problems in the vectorizer and
                                might be slow. Maybe we can optimize the
                                size of the iv later.) Before: Used we
                                used the type of the old IV. But with
                                strip mining there is no 1 to 1 relation
                                in between ivs, so there is not always a
                                type. Other idea: infer types from upper
                                and lower bound expressions. But does
                                not seem to work either. This blocks the
                                work on removal IVSTACK. 
                      * Removal of IVStack: Blocked by types. But
                        already triggers some bugs. 
                      * Reductions: Blocking by IVSTack. 
      * Li: 
              * Mark loops as parallel with -fgraphite-force-parallel
                (committed). 
              * Trigger autopar with loop->can_be_parallel (committed). 
                
              * Started testsuite for graphite_autopar (sent for review
                to gcc-patches). 
              * 
              * Autopar fails in graphite branch on this line; 
------------------------------------------------------------------------
red = reduction_phi (reduction_list, reduc_phi);
      if (red == NULL)
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
          fprintf (dump_file,
                   "  FAILED: it is not a part of reduction.\n");
        return false;
      }
------------------------------------------------------------------------

      * Tobias: 
              * Fix bugs to enable data reference building (Now only
                gfortran.dg/transpose_conjg_1.f90 fails). 
              * Bootstrapped dependency testing. Worked except one test
                case (gfortran.dg/cray_pointers_2.f90). 
              * Working on his paper about the polyhedral part of
                graphite to attract more research in this area. 
              * 
      * Jan: 
              * Got gcc summit paper accepted. Will be about the design
                of Graphite: IR, components of the Graphite
                infrastructure, testsuite, example, internals,
                integration with external prototyping tools (POCC). We
                should have some discussions about who describes what in
                graphite, as Tobias also has a paper accepted. 
              * Worked on the translation of PCP to Polyhedral
                representation. 

Re: [graphite] Weekly phone call notes

[Richard Guenther]

On Wed, May 6, 2009 at 11:15 PM, Tobias Grosser
<grosser@fim.uni-passau.de> wrote:
> Hi folks, hi graphities,
>
> here you are with the latest notes from our graphite phone call.
>
> It is also available on the wiki:
>
> http://gcc.gnu.org/wiki/Graphite_Phone_Call/2009_05_06
>
> All the best
>
> Tobi
>
>
> Attendees: Sebastian, Tobias, Christophe, Albert, Li, Jan, Razya,
> Konrad, Antoniu
>
>      * Sebastian:
>              * Working on IVstack removal,
>              * Several other patches like "remove strcmp". (Will be
>                committed as soon as possible)
>              * in clast-to-gimple:
>                      * There is a problem finding the type of induction
>                        variables and upper bound expressions, as cloog
>                        does not carry information about them.
>                              * We will try "unsigned long long" and
>                                have to insert casts. (This might
>                                trigger problems in the vectorizer and
>                                might be slow. Maybe we can optimize the
>                                size of the iv later.) Before: Used we
>                                used the type of the old IV. But with
>                                strip mining there is no 1 to 1 relation
>                                in between ivs, so there is not always a
>                                type. Other idea: infer types from upper
>                                and lower bound expressions. But does
>                                not seem to work either. This blocks the
>                                work on removal IVSTACK.

If the induction variables are only used to iterate over the domain then
deriving them from upper and lower bounds (well - if you can constrain
them) should be the right thing to do.  In that context, when the IVs
are then only used to index into arrays or used as offsets for pointers
then using sizetype instead of unsigned long long would be a better
default choice.

Are there known constraints on the IV use?  Like that operations on them
never overflow?

Richard.

>                      * Removal of IVStack: Blocked by types. But
>                        already triggers some bugs.
>                      * Reductions: Blocking by IVSTack.
>      * Li:
>              * Mark loops as parallel with -fgraphite-force-parallel
>                (committed).
>              * Trigger autopar with loop->can_be_parallel (committed).
>
>              * Started testsuite for graphite_autopar (sent for review
>                to gcc-patches).
>              *
>              * Autopar fails in graphite branch on this line;
> ------------------------------------------------------------------------
> red = reduction_phi (reduction_list, reduc_phi);
>      if (red == NULL)
>      {
>        if (dump_file && (dump_flags & TDF_DETAILS))
>          fprintf (dump_file,
>                   "  FAILED: it is not a part of reduction.\n");
>        return false;
>      }
> ------------------------------------------------------------------------
>
>      * Tobias:
>              * Fix bugs to enable data reference building (Now only
>                gfortran.dg/transpose_conjg_1.f90 fails).
>              * Bootstrapped dependency testing. Worked except one test
>                case (gfortran.dg/cray_pointers_2.f90).
>              * Working on his paper about the polyhedral part of
>                graphite to attract more research in this area.
>              *
>      * Jan:
>              * Got gcc summit paper accepted. Will be about the design
>                of Graphite: IR, components of the Graphite
>                infrastructure, testsuite, example, internals,
>                integration with external prototyping tools (POCC). We
>                should have some discussions about who describes what in
>                graphite, as Tobias also has a paper accepted.
>              * Worked on the translation of PCP to Polyhedral
>                representation.
>
>

[graphite] Weekly phone call notes

[Tobias Grosser]

Hi folks, hi graphities,

here you are with the latest notes from our graphite phone call.

It is also available on the wiki:

http://gcc.gnu.org/wiki/Graphite_Phone_Call/2009_05_06

All the best

Tobi


Attendees: Sebastian, Tobias, Christophe, Albert, Li, Jan, Razya,
Konrad, Antoniu 

      * Sebastian: 
              * Working on IVstack removal, 
              * Several other patches like "remove strcmp". (Will be
                committed as soon as possible) 
              * in clast-to-gimple: 
                      * There is a problem finding the type of induction
                        variables and upper bound expressions, as cloog
                        does not carry information about them. 
                              * We will try "unsigned long long" and
                                have to insert casts. (This might
                                trigger problems in the vectorizer and
                                might be slow. Maybe we can optimize the
                                size of the iv later.) Before: Used we
                                used the type of the old IV. But with
                                strip mining there is no 1 to 1 relation
                                in between ivs, so there is not always a
                                type. Other idea: infer types from upper
                                and lower bound expressions. But does
                                not seem to work either. This blocks the
                                work on removal IVSTACK. 
                      * Removal of IVStack: Blocked by types. But
                        already triggers some bugs. 
                      * Reductions: Blocking by IVSTack. 
      * Li: 
              * Mark loops as parallel with -fgraphite-force-parallel
                (committed). 
              * Trigger autopar with loop->can_be_parallel (committed). 
                
              * Started testsuite for graphite_autopar (sent for review
                to gcc-patches). 
              * 
              * Autopar fails in graphite branch on this line; 
------------------------------------------------------------------------
red = reduction_phi (reduction_list, reduc_phi);
      if (red == NULL)
      {
        if (dump_file && (dump_flags & TDF_DETAILS))
          fprintf (dump_file,
                   "  FAILED: it is not a part of reduction.\n");
        return false;
      }
------------------------------------------------------------------------

      * Tobias: 
              * Fix bugs to enable data reference building (Now only
                gfortran.dg/transpose_conjg_1.f90 fails). 
              * Bootstrapped dependency testing. Worked except one test
                case (gfortran.dg/cray_pointers_2.f90). 
              * Working on his paper about the polyhedral part of
                graphite to attract more research in this area. 
              * 
      * Jan: 
              * Got gcc summit paper accepted. Will be about the design
                of Graphite: IR, components of the Graphite
                infrastructure, testsuite, example, internals,
                integration with external prototyping tools (POCC). We
                should have some discussions about who describes what in
                graphite, as Tobias also has a paper accepted. 
              * Worked on the translation of PCP to Polyhedral
                representation.