[Bug tree-optimization/109156] New: Support Absolute Difference detection in GCC

[Bug tree-optimization/109156] New: Support Absolute Difference detection in GCC

[tnfchris at gcc dot gnu.org]

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

            Bug ID: 109156
           Summary: Support Absolute Difference detection in GCC
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tnfchris at gcc dot gnu.org
  Target Milestone: ---
            Target: aarch64*

Today we support Sum of Absolute differences

#include <stdlib.h>

#define TYPE_IN signed char
#define TYPE_OUT signed int

TYPE_OUT SABD_example (int n, TYPE_IN *restrict a, TYPE_IN *restrict b)
{
  TYPE_OUT out = 0;
  for (int i = 0; i < n; i++)
    out += abs(b[i] - a[i]);
  return out;
}

which is implemented through the SAD_EXPR tree code.

The goal is to support absolute difference ABD and widening absolute difference
(no reduction).

#include <stdlib.h>

#define TYPE_IN signed int
#define TYPE_OUT signed int

void ABD_example (int n, TYPE_IN *restrict a, TYPE_IN *restrict b, TYPE_OUT
*restrict out)
{
  for (int i = 0; i < n; i++)
    out[i] = abs(b[i] - a[i]);
}


This code shares 90% of the work with the vect_recog_sad_pattern expression
with one difference, the SAD expression starts at a reduction, the ADB
expressions start at an optional cast but otherwise from the abs.

There are two ways we're thinking of implementing ABD, (ABDL we can't do at the
moment because we can't do widening in IFNs).

1. refactor the SAD detection code such that the body of the code that detects
ABD is refactored out and can be used by a new pattern.  This has the down side
of us having to do duplicate work in patterns that may match this.  In general
this doesn't happen often because SAD stops at the + and should be OK if ADB
matches after SAD. though cast_forwardprop may make this hard to do.

2. It looks like all targets that implement SAD do so with an instruction that
does ABD and then perform a reduction.  So it looks like no target has the
semantics for SAD.

So this brings up the question of why the detection wasn't done based on ABD
instead and leaving the reduction explicit in the vectorizer.

So question is, should we create a completely new standalone pattern for ABD or
should be make ABD the thing being detected and change SAD_EXPR to recognize
ADB + reduction.

Removing SAD completely in favor of ABD + reduction means that hand optimized
versions in targets need updating so I'm in favor of still emitting SAD.

[Bug tree-optimization/109156] Support Absolute Difference detection in GCC

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Tamar Christina from comment #0)
> 2. It looks like all targets that implement SAD do so with an instruction
> that does ABD and then perform a reduction.  So it looks like no target has
> the semantics for SAD.

x86 for example does SAD on 16 QImode data and 4 SImode accumulators which
means it sums 4 QImode absolute differences each (but SAD_EXPR leaves
unspecified which, so SAD_EXPR is only usable when you in the end sum
the accumulator lanes as well).

So I don't think 2. is true.

> So this brings up the question of why the detection wasn't done based on ABD
> instead and leaving the reduction explicit in the vectorizer.
> 
> So question is, should we create a completely new standalone pattern for ABD
> or should be make ABD the thing being detected and change SAD_EXPR to
> recognize ADB + reduction.
> 
> Removing SAD completely in favor of ABD + reduction means that hand
> optimized versions in targets need updating so I'm in favor of still
> emitting SAD.

I'd do a separate internal function for ABD, possibly sharing part of the
detection as you proposed.

[Bug tree-optimization/109156] Support Absolute Difference detection in GCC

[tnfchris at gcc dot gnu.org]

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

--- Comment #2 from Tamar Christina <tnfchris at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> (In reply to Tamar Christina from comment #0)
> > 2. It looks like all targets that implement SAD do so with an instruction
> > that does ABD and then perform a reduction.  So it looks like no target has
> > the semantics for SAD.
> 
> x86 for example does SAD on 16 QImode data and 4 SImode accumulators which
> means it sums 4 QImode absolute differences each (but SAD_EXPR leaves
> unspecified which, so SAD_EXPR is only usable when you in the end sum
> the accumulator lanes as well).
> 

Oh I see, psadbw is actually SAD. sorry I missed the `s` in the instruction!

> So I don't think 2. is true.
> 
> > So this brings up the question of why the detection wasn't done based on ABD
> > instead and leaving the reduction explicit in the vectorizer.
> > 
> > So question is, should we create a completely new standalone pattern for ABD
> > or should be make ABD the thing being detected and change SAD_EXPR to
> > recognize ADB + reduction.
> > 
> > Removing SAD completely in favor of ABD + reduction means that hand
> > optimized versions in targets need updating so I'm in favor of still
> > emitting SAD.
> 
> I'd do a separate internal function for ABD, possibly sharing part of the
> detection as you proposed.

Great, will do so, thanks!

[Bug tree-optimization/109156] Support Absolute Difference detection in GCC

[tnfchris at gcc dot gnu.org]

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

Tamar Christina <tnfchris at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |tnfchris at gcc dot gnu.org

--- Comment #3 from Tamar Christina <tnfchris at gcc dot gnu.org> ---
Reserving work

[Bug tree-optimization/109156] Support Absolute Difference detection in GCC

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2023-03-16
     Ever confirmed|0                           |1

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
.

[Bug tree-optimization/109156] Support Absolute Difference detection in GCC

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 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:ea616f687dccbe42012f786c0ebade5b05850206

commit r14-1833-gea616f687dccbe42012f786c0ebade5b05850206
Author: Oluwatamilore Adebayo <oluwatamilore.adebayo@arm.com>
Date:   Thu Jun 15 07:36:48 2023 +0100

    AArch64: New RTL for ABD

    This patch adds new RTL and tests for sabd and uabd

    PR tree-optimization/109156

    gcc/ChangeLog:

            * config/aarch64/aarch64-simd.md (aarch64_<su>abd<mode>):
            Rename to <su>abd<mode>3.
            * config/aarch64/aarch64-sve.md (<su>abd<mode>_3): Rename
            to <su>abd<mode>3.

    gcc/testsuite/ChangeLog:

            * gcc.target/aarch64/abd.h: New file.
            * gcc.target/aarch64/abd_2.c: New test.
            * gcc.target/aarch64/abd_3.c: New test.
            * gcc.target/aarch64/abd_4.c: New test.
            * gcc.target/aarch64/abd_none_2.c: New test.
            * gcc.target/aarch64/abd_none_3.c: New test.
            * gcc.target/aarch64/abd_none_4.c: New test.
            * gcc.target/aarch64/abd_run_1.c: New test.
            * gcc.target/aarch64/sve/abd_1.c: New test.
            * gcc.target/aarch64/sve/abd_none_1.c: New test.
            * gcc.target/aarch64/sve/abd_2.c: New test.
            * gcc.target/aarch64/sve/abd_none_2.c: New test.

[Bug tree-optimization/109156] Support Absolute Difference detection in GCC

[tnfchris at gcc dot gnu.org]

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

Tamar Christina <tnfchris at gcc dot gnu.org> changed:

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

--- Comment #6 from Tamar Christina <tnfchris at gcc dot gnu.org> ---
This is now implemented