[Bug tree-optimization/98598] New: Missed opportunity to optimize dependent loads in loops

[Bug tree-optimization/98598] New: Missed opportunity to optimize dependent loads in loops

[hliu at amperecomputing dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

            Bug ID: 98598
           Summary: Missed opportunity to optimize dependent loads in
                    loops
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hliu at amperecomputing dot com
  Target Milestone: ---

As we know, dependent loads are not friendly to cache. Especially when in
nested loops, dependent loads such as pa->pb->pc->val may be repeated many
times. For example:

typedef struct C { int val; } C;
typedef struct B { C *pc; } B;
typedef struct A { B *pb; } A;

int foo (int n, int m, A *pa) {
  int sum;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      sum += pa[j].pb->pc->val;  // each value is repeatedly loaded "n" times
      // ...
    }
    // ...
  }

  return sum;
}

Such access pattern can be found in real applications and benchmarks, and this
can be critical to performance.

Can we cache the loaded value and avoid repeated dependent loads? E.g.
transform above case into following (suppose there is no alias issue or other
clobber, and "n" is big enough):

int foo (int n, int m, A *pa) {
  int *cache = (int *) malloc(m * sizeof(int));
  for (int j = 0; j < m; j++) {
    cache[j] = pa[j].pb->pc->val;
  }

  int sum;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      sum += cache[j];   // pa[j].pb->pc->val;
      // ...
    }
    // ...
  }

  free(cache);
  return sum;
}

This should improve performance a lot.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|tree-ssa                    |11.0
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2021-01-08
                 CC|                            |amker at gcc dot gnu.org,
                   |                            |matz at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC doesn't have any such capability (introducing temporary storage to allow
loop distribution or other transforms).  But the transform would fit into loop
distribution (or rather after introducing the array loop distribution could
distribute the loop - even though it's cost model likely says that's not
wanted).

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[jiangning.liu at amperecomputing dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #2 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
Loop distribution can only handle very simple case. If the inner loop has
complicated control flow and other memory accesses with loop-carried
dependence, it would be hard to handle it. For example,

int foo (int n, int m, A *pa) {
  int sum;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      sum += pa[j].pb->pc->val;  // each value is repeatedly loaded "n" times
      sum = sum % 7;
    }
    sum = sum % 13;
  }

  return sum;
}

Alternatively, we can detect "invariant" dependent memory loads for the nested
loops with alias conflict checked. If the outer loop is hot enough, we could
have a chance to "hoist" them to create cache.

As for temp storage, is it a gcc's rule of thumb not to introduce temp storage
on heap, or it is just gcc doesn't have it yet and we want to have it?

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #3 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 8 Jan 2021, jiangning.liu at amperecomputing dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598
> 
> --- Comment #2 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
> Loop distribution can only handle very simple case. If the inner loop has
> complicated control flow and other memory accesses with loop-carried
> dependence, it would be hard to handle it. For example,
> 
> int foo (int n, int m, A *pa) {
>   int sum;
> 
>   for (int i = 0; i < n; i++) {
>     for (int j = 0; j < m; j++) {
>       sum += pa[j].pb->pc->val;  // each value is repeatedly loaded "n" times
>       sum = sum % 7;
>     }
>     sum = sum % 13;
>   }
> 
>   return sum;
> }
> 
> Alternatively, we can detect "invariant" dependent memory loads for the nested
> loops with alias conflict checked. If the outer loop is hot enough, we could
> have a chance to "hoist" them to create cache.
> 
> As for temp storage, is it a gcc's rule of thumb not to introduce temp storage
> on heap, or it is just gcc doesn't have it yet and we want to have it?

It has to be done with care of course, cost modeling is difficult
(we need to have a good estimate of n and m or need to version
the whole nest).  That said, usually we attempt the reverse transform.

My personal opinion is that hinting the user to possibly refactor
his code (guided by profiling to be not too noisy) is much
prefered to the idea that the compiler can ever apply such transform
to the loops where it matters and not to the loops where it is
harmful.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[amker at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #4 from bin cheng <amker at gcc dot gnu.org> ---
Didn't go deep into the case.

For simple cases taken as examples, it's possible to interchange the two loops
thus enables loop invariant code motion.  Though loop interchange may fail
because of complicated data dependences, we may take some useful points from
it, for example, the cost model checking new loop invariants wrto the outer
loop.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[jiangning.liu at amperecomputing dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #5 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
> It has to be done with care of course, cost modeling is difficult
> (we need to have a good estimate of n and m or need to version
> the whole nest).  That said, usually we attempt the reverse transform.

Before tuning the cost model good enough, we may implement this optimization by
adding a new optimization command line option. This won't hurt gcc, right?

> 
> My personal opinion is that hinting the user to possibly refactor
> his code (guided by profiling to be not too noisy) is much
> prefered to the idea that the compiler can ever apply such transform
> to the loops where it matters and not to the loops where it is
> harmful.

Sometimes, it is not always easy for the user to modify the code, and even the
user may be lazy and reluctant to change the code. This kind of Memory
Gathering Optimization can make end-user's life easier.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> ---
On January 9, 2021 4:17:17 AM GMT+01:00, "jiangning.liu at amperecomputing dot
com" <gcc-bugzilla@gcc.gnu.org> wrote:
>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598
>
>--- Comment #5 from Jiangning Liu <jiangning.liu at amperecomputing dot
>com> ---
>> It has to be done with care of course, cost modeling is difficult
>> (we need to have a good estimate of n and m or need to version
>> the whole nest).  That said, usually we attempt the reverse
>transform.
>
>Before tuning the cost model good enough, we may implement this
>optimization by
>adding a new optimization command line option. This won't hurt gcc,
>right?

New options not enabled by default tend to bitrot, be broken from the start and
won't be used by the lazy user. So I see no point in doing that. 

>> 
>> My personal opinion is that hinting the user to possibly refactor
>> his code (guided by profiling to be not too noisy) is much
>> prefered to the idea that the compiler can ever apply such transform
>> to the loops where it matters and not to the loops where it is
>> harmful.
>
>Sometimes, it is not always easy for the user to modify the code, and
>even the
>user may be lazy and reluctant to change the code. This kind of Memory
>Gathering Optimization can make end-user's life easier.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[jiangning.liu at amperecomputing dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #7 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
(In reply to rguenther@suse.de from comment #6)
> On January 9, 2021 4:17:17 AM GMT+01:00, "jiangning.liu at amperecomputing
> dot com" <gcc-bugzilla@gcc.gnu.org> wrote:
> >https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598
> >
> >--- Comment #5 from Jiangning Liu <jiangning.liu at amperecomputing dot
> >com> ---
> >> It has to be done with care of course, cost modeling is difficult
> >> (we need to have a good estimate of n and m or need to version
> >> the whole nest).  That said, usually we attempt the reverse
> >transform.
> >
> >Before tuning the cost model good enough, we may implement this
> >optimization by
> >adding a new optimization command line option. This won't hurt gcc,
> >right?
> 
> New options not enabled by default tend to bitrot, be broken from the start
> and won't be used by the lazy user. So I see no point in doing that. 
> 

Understand. I mean we can enable it by default eventually, but we need to
implement and tune it step by step. It is unrealistic to work out the best cost
model at the very beginning.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #8 from rguenther at suse dot de <rguenther at suse dot de> ---
On Sat, 9 Jan 2021, jiangning.liu at amperecomputing dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598
> 
> --- Comment #7 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
> (In reply to rguenther@suse.de from comment #6)
> > On January 9, 2021 4:17:17 AM GMT+01:00, "jiangning.liu at amperecomputing
> > dot com" <gcc-bugzilla@gcc.gnu.org> wrote:
> > >https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598
> > >
> > >--- Comment #5 from Jiangning Liu <jiangning.liu at amperecomputing dot
> > >com> ---
> > >> It has to be done with care of course, cost modeling is difficult
> > >> (we need to have a good estimate of n and m or need to version
> > >> the whole nest).  That said, usually we attempt the reverse
> > >transform.
> > >
> > >Before tuning the cost model good enough, we may implement this
> > >optimization by
> > >adding a new optimization command line option. This won't hurt gcc,
> > >right?
> > 
> > New options not enabled by default tend to bitrot, be broken from the start
> > and won't be used by the lazy user. So I see no point in doing that. 
> > 
> 
> Understand. I mean we can enable it by default eventually, but we need to
> implement and tune it step by step. It is unrealistic to work out the best cost
> model at the very beginning.

Sure.  The "easiest" thing is to rely on a profile from PGO, we did
have some transforms only enabled by -fprofile-use by default.  That is,
the cost model needs to be conservative, esp. if you introduce dynamic
allocation for this.  In the end I guess only a variant that versions
the nest on the size of the temporary will be good enough to not trigger
OOM or excessive overhead for small sizes anyway.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[crazylht at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

Hongtao.liu <crazylht at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |crazylht at gmail dot com

--- Comment #9 from Hongtao.liu <crazylht at gmail dot com> ---
It looks like a SOA/AOC opt opportunity which is discussed in
https://gcc.gnu.org/wiki/cauldron2015?action=AttachFile&do=view&target=Olga+Golovanevsky_+Memory+Layout+Optimizations+of+Structures+and+Objects.pdf

And i remember there's someone working on enabling SOA/AOS opt in GCC.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[jiangning.liu at amperecomputing dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #10 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
(In reply to Hongtao.liu from comment #9)
> It looks like a SOA/AOC opt opportunity which is discussed in
> https://gcc.gnu.org/wiki/
> cauldron2015?action=AttachFile&do=view&target=Olga+Golovanevsky_+Memory+Layou
> t+Optimizations+of+Structures+and+Objects.pdf
> 
> And i remember there's someone working on enabling SOA/AOS opt in GCC.

No. The key difference is the optimization opportunity here doesn't rely on LTO
at all. It is purely a local optimization within a function instead.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[jiangning.liu at amperecomputing dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #11 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
(In reply to rguenther@suse.de from comment #8)
> On Sat, 9 Jan 2021, jiangning.liu at amperecomputing dot com wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598
> > 
> > --- Comment #7 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
> > (In reply to rguenther@suse.de from comment #6)
> > > On January 9, 2021 4:17:17 AM GMT+01:00, "jiangning.liu at amperecomputing
> > > dot com" <gcc-bugzilla@gcc.gnu.org> wrote:
> > > >https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598
> > > >
> > > >--- Comment #5 from Jiangning Liu <jiangning.liu at amperecomputing dot
> > > >com> ---
> > > >> It has to be done with care of course, cost modeling is difficult
> > > >> (we need to have a good estimate of n and m or need to version
> > > >> the whole nest).  That said, usually we attempt the reverse
> > > >transform.
> > > >
> > > >Before tuning the cost model good enough, we may implement this
> > > >optimization by
> > > >adding a new optimization command line option. This won't hurt gcc,
> > > >right?
> > > 
> > > New options not enabled by default tend to bitrot, be broken from the start
> > > and won't be used by the lazy user. So I see no point in doing that. 
> > > 
> > 
> > Understand. I mean we can enable it by default eventually, but we need to
> > implement and tune it step by step. It is unrealistic to work out the best cost
> > model at the very beginning.
> 
> Sure.  The "easiest" thing is to rely on a profile from PGO, we did
> have some transforms only enabled by -fprofile-use by default.  That is,
> the cost model needs to be conservative, esp. if you introduce dynamic
> allocation for this.  In the end I guess only a variant that versions
> the nest on the size of the temporary will be good enough to not trigger
> OOM or excessive overhead for small sizes anyway.

People usually don't use PGO unless they can't find any better static compiler
switches. This optimization should always benefit performance if we can tune
the cost model good enough. It is true that the temp memory size needs to be
checked to avoid OOM, which is one of the runtime overheads.

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[jiangning.liu at amperecomputing dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

--- Comment #12 from Jiangning Liu <jiangning.liu at amperecomputing dot com> ---
MGO RFC is at https://gcc.gnu.org/pipermail/gcc/2021-January/234682.html

[Bug tree-optimization/98598] Missed opportunity to optimize dependent loads in loops

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98598

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement