[Bug target/105075] New: [nvptx] Generate sad insn (sum of absolute differences)

[Bug target/105075] New: [nvptx] Generate sad insn (sum of absolute differences)

[vries at gcc dot gnu.org]

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

            Bug ID: 105075
           Summary: [nvptx] Generate sad insn (sum of absolute
                    differences)
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vries at gcc dot gnu.org
  Target Milestone: ---

ptx has sad ((sum of absolute differences)) insn, which is currently not
modeled in the .md file.

[Bug target/105075] [nvptx] Generate sad insn (sum of absolute differences)

[vries at gcc dot gnu.org]

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

--- Comment #1 from Tom de Vries <vries at gcc dot gnu.org> ---
Created attachment 52693
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52693&action=edit
Demonstrator patch

This patch adds:
- modeling of insn sad.u32 in the .md file
- peephole2 to generate it
  (which is incomplete, it needs some safety-checks related to
  using unique intermediate regs)
- extra instance of peephole2 pass (otherwise, the peephole is not triggered)
- extra instance of fast_rtl_dce pass (otherwise, unused intermediate
  insn are not cleaned up)

So for the usad_2 in the test-case, we have without the patch:
...
                cvt.u64.u32     %r32, %r28;                                     
                cvt.u64.u32     %r33, %r29;                                     
                sub.u64 %r34, %r32, %r33;                                       
                abs.s64 %r35, %r34;                                             
                cvt.u32.u64     %r36, %r35;                                     
                add.u32 %value, %r36, %r30;                                     
...
and with:
...
                sad.u32 %value, %r28, %r29, %r30;                               
...

[Bug target/105075] [nvptx] Generate sad insn (sum of absolute differences)

[vries at gcc dot gnu.org]

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

--- Comment #2 from Tom de Vries <vries at gcc dot gnu.org> ---
AFAIU, at gimple level support is limited to vectors, so that doesn't help to
generate the insn for the simple, scalar case.

It would be nice if combine could generate it and we wouldn't have to use a
peephole, but AFAIU the pattern is too complex for that.

I wonder if reformulating using a conditional could help there (ptx isa
describes semantics using "c + ((a<b) ? b-a : a-b)".

Also, I wonder if defining a stepping-stone intermediate pattern could help
combine.

[Bug target/105075] [nvptx] Generate sad insn (sum of absolute differences)

[vries at gcc dot gnu.org]

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

Tom de Vries <vries at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #52693|0                           |1
        is obsolete|                            |

--- Comment #3 from Tom de Vries <vries at gcc dot gnu.org> ---
Created attachment 52694
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52694&action=edit
Demonstrator patch v2

Forgot to add test-case.

[Bug target/105075] [nvptx] Generate sad insn (sum of absolute differences)

[tschwinge at gcc dot gnu.org]

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

Thomas Schwinge <tschwinge at gcc dot gnu.org> changed:

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

--- Comment #4 from Thomas Schwinge <tschwinge at gcc dot gnu.org> ---
(In reply to Tom de Vries from comment #0)
> ptx has sad ((sum of absolute differences)) insn, which is currently not
> modeled in the .md file.

I also had noticed this, a while ago (but no opportunity to work on it
properly).

I had found GCC/RTL 'ssad', 'usad', and 'gcc/tree.def:SAD_EXPR', but not
verified their applicability.


(In reply to Tom de Vries from comment #2)
> AFAIU, at gimple level support is limited to vectors, so that doesn't help
> to generate the insn for the simple, scalar case.
> 
> It would be nice if combine could generate it and we wouldn't have to use a
> peephole, but AFAIU the pattern is too complex for that.
> 
> I wonder if reformulating using a conditional could help there (ptx isa
> describes semantics using "c + ((a<b) ? b-a : a-b)".

Would that not be a case for a proper TREE-level representation, and
'gcc/match.pd' patterns to catch and transform any appearances to that, and
then let each back end generate an ideal sequence of instructions (with a
default to the expression you gave above)?

> Also, I wonder if defining a stepping-stone intermediate pattern could help
> combine.

[Bug target/105075] [nvptx] Generate sad insn (sum of absolute differences)

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
@cindex @code{ssad@var{m}} instruction pattern
@item @samp{ssad@var{m}}
@cindex @code{usad@var{m}} instruction pattern
@item @samp{usad@var{m}}
Compute the sum of absolute differences of two signed/unsigned elements.
Operand 1 and operand 2 are of the same mode. Their absolute difference, which
is of a wider mode, is computed and added to operand 3. Operand 3 is of a mode
equal or wider than the mode of the absolute difference. The result is placed
in operand 0, which is of the same mode as operand 3.


That cruically "misses" a detail for the vector case where the sum will
also sum across (unspecified!) lanes when operand 3 is wider than the
absolute difference and has a lower number of lanes than the input vectors.

The unspecified part makes it a hart fit for pattern matching (unrolled)
code when actual output lanes are used and they are not being reduced to
a single scalar in the end.

For scalar instruction matching the patterns should be usable.

Note the SAD_EXPR on GENERIC has the same issue when vectors types are
used - the exact semantics are unspecified.

The same is true for DOT_PROD_EXPR and WIDEN_SUM_EXPR and a bunch of others.

These days we'd go for matching them to direct internal function calls
using the {u,s}sad optabs and I don't see any reason to not allow scalar
modes for them.  I'd rather get rid of all the tree codes we have for
vectorizer reduction patterns in favor of those so if you can avoid
introducing new ones or adding more uses of existing ones that would be nice.

[Bug target/105075] [nvptx] Generate sad insn (sum of absolute differences)

[vries at gcc dot gnu.org]

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

--- Comment #6 from Tom de Vries <vries at gcc dot gnu.org> ---
Created attachment 52698
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52698&action=edit
Demonstrator patch with stepping stone patterns for combine

(In reply to Tom de Vries from comment #2)
> Also, I wonder if defining a stepping-stone intermediate pattern could help
> combine.

Well, that approach seems to work.

[Bug target/105075] [nvptx] Generate sad insn (sum of absolute differences)

[rguenther at suse dot de]

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

--- Comment #7 from rguenther at suse dot de <rguenther at suse dot de> ---
On Mon, 28 Mar 2022, vries at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105075
> 
> --- Comment #6 from Tom de Vries <vries at gcc dot gnu.org> ---
> Created attachment 52698
>   --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52698&action=edit
> Demonstrator patch with stepping stone patterns for combine
> 
> (In reply to Tom de Vries from comment #2)
> > Also, I wonder if defining a stepping-stone intermediate pattern could help
> > combine.
> 
> Well, that approach seems to work.

Another possibility is to do this on GIMPLE where we detect widen 
multiplication and friends 
(tree-ssa-math-opts.cc:pass_optimize_widening_mul).