[Bug tree-optimization/106019] New: Surprising SLP failure on trivial code

[Bug tree-optimization/106019] New: Surprising SLP failure on trivial code

[amonakov at gcc dot gnu.org]

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

            Bug ID: 106019
           Summary: Surprising SLP failure on trivial code
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amonakov at gcc dot gnu.org
  Target Milestone: ---

In the following code, 'f' is not SLP-vectorized, but 'g' is. From a brief look
at slp2 dump, looks like dependence analysis for p[i] vs. p[i+1] fails?

void f(double *p, long i)
{
    p[i+0] += 1;
    p[i+1] += 1;
}
void g(double *p, long i)
{
    double *q = p + i;
    q[0] += 1;
    q[1] += 1;
}

[Bug tree-optimization/106019] Surprising SLP failure on trivial code

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-06-20
             Status|UNCONFIRMED                 |NEW
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
     Ever confirmed|0                           |1

[Bug tree-optimization/106019] Surprising SLP failure on trivial code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rsandifo at gcc dot gnu.org

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

Creating dr for *_3
analyze_innermost: success.
        base_address: p_12(D) + (sizetype) i_11(D) * 8
        offset from base address: 0
        constant offset from base address: 0
        step: 0
        base alignment: 8
        base misalignment: 0
        offset alignment: 128
        step alignment: 128
        base_object: *_3

vs.

Creating dr for *_8
analyze_innermost: success.
        base_address: p_12(D) + (sizetype) i_11(D) * 8
        offset from base address: 0
        constant offset from base address: 8
        step: 0
        base alignment: 8
        base misalignment: 0
        offset alignment: 128
        step alignment: 128
        base_object: *_8

the base_object are different which makes dependence analysis fail.  I
suppose we could look at the case of equal base_address here - the
loop based dependence analysis might be not the optimal thing to check.

Richard, any opinions how we should deal with this API wise?
This is vect_slp_analyze_node_dependences

[Bug tree-optimization/106019] Surprising SLP failure on trivial code

[rsandifo at gcc dot gnu.org]

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

rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |rsandifo at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #2 from rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> ---
Created attachment 53172
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53172&action=edit
Candidate patch

Huh, yeah, surprising this has been present so long.

Running aff_combination_expand on off2 before the query in
(from dr_may_alias_p):

      aff_tree off1, off2;
      poly_widest_int size1, size2;
      get_inner_reference_aff (DR_REF (a), &off1, &size1);
      get_inner_reference_aff (DR_REF (b), &off2, &size2);
      aff_combination_scale (&off1, -1);
      aff_combination_add (&off2, &off1);
      if (aff_comb_cannot_overlap_p (&off2, size1, size2))
        return false;

seems to fix it, but I guess that then adds the burden of
maintaining the cache.  Since we've already done similar
SSA_NAME expansion for DR_BASE_ADDRESS/DR_OFFSET, perhaps
we should just try to use that instead?  The attached patch
does that and fixes the testcase.

But maybe there are cases that aff_combination_expand
would handle and this patch wouldn't -- not sure.

[Bug tree-optimization/106019] Surprising SLP failure on trivial code

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to rsandifo@gcc.gnu.org from comment #2)
> Created attachment 53172 [details]
> Candidate patch
> 
> Huh, yeah, surprising this has been present so long.
> 
> Running aff_combination_expand on off2 before the query in
> (from dr_may_alias_p):
> 
>       aff_tree off1, off2;
>       poly_widest_int size1, size2;
>       get_inner_reference_aff (DR_REF (a), &off1, &size1);
>       get_inner_reference_aff (DR_REF (b), &off2, &size2);
>       aff_combination_scale (&off1, -1);
>       aff_combination_add (&off2, &off1);
>       if (aff_comb_cannot_overlap_p (&off2, size1, size2))
>         return false;
> 
> seems to fix it, but I guess that then adds the burden of
> maintaining the cache.  Since we've already done similar
> SSA_NAME expansion for DR_BASE_ADDRESS/DR_OFFSET, perhaps
> we should just try to use that instead?  The attached patch
> does that and fixes the testcase.

Ah, that seems to be a good idea.  I guess doing that first would
make sense.

> But maybe there are cases that aff_combination_expand
> would handle and this patch wouldn't -- not sure.

I suppose we could add statistics to the base-address case
added by the patch, the existing DR_REF handling (I suppose
this might no longer catch anything with the base-address handling?).

Indeed we'd need to maintain a cache for the aff combination
expansion if we go that route, but the proposed patch looks like
a good improvement (as said, I'd do the check first).

[Bug tree-optimization/106019] Surprising SLP failure on trivial code

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Richard Sandiford <rsandifo@gcc.gnu.org>:

https://gcc.gnu.org/g:038b077689bb5310386b04d40a2cea234f01e6aa

commit r13-1203-g038b077689bb5310386b04d40a2cea234f01e6aa
Author: Richard Sandiford <richard.sandiford@arm.com>
Date:   Wed Jun 22 11:27:15 2022 +0100

    data-ref: Improve non-loop disambiguation [PR106019]

    When dr_may_alias_p is called without a loop context, it tries
    to use the tree-affine interface to calculate the difference
    between the two addresses and use that difference to check whether
    the gap between the accesses is known at compile time.  However, as the
    example in the PR shows, this doesn't expand SSA_NAMEs and so can easily
    be defeated by things like reassociation.

    One fix would have been to use aff_combination_expand to expand the
    SSA_NAMEs, but we'd then need some way of maintaining the associated
    cache.  This patch instead reuses the innermost_loop_behavior fields
    (which exist even when no loop context is provided).

    It might still be useful to do the aff_combination_expand thing too,
    if an example turns out to need it.

    gcc/
            PR tree-optimization/106019
            * tree-data-ref.cc (dr_may_alias_p): Try using the
            innermost_loop_behavior to disambiguate non-loop queries.

    gcc/testsuite/
            PR tree-optimization/106019
            * gcc.dg/vect/bb-slp-pr106019.c: New test.

[Bug tree-optimization/106019] Surprising SLP failure on trivial code

[rsandifo at gcc dot gnu.org]

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

rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #5 from rsandifo at gcc dot gnu.org <rsandifo at gcc dot gnu.org> ---
Fixed -- thanks for the catch.