[Bug c/53645] New: Missed optimization for division of vector types

[Bug c/53645] New: Missed optimization for division of vector types

[andrii.riabushenko at barclays dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

             Bug #: 53645
           Summary: Missed optimization for division of vector types
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: andrii.riabushenko@barclays.com


for the following code

v4si ttt(v4si x) {

     return x / (v4si) {3,3,3,3};
}


GCC generates the following assembler

ttt:
    movdqa    (%rcx), %xmm0
    movl    $1431655766, %ecx
    movd    %xmm0, %r8d
    pextrd    $1, %xmm0, %r10d
    pextrd    $2, %xmm0, %r11d
    movl    %r8d, %eax
    sarl    $31, %r8d
    imull    %ecx
    movl    %r10d, %eax
    sarl    $31, %r10d
    movl    %edx, %r9d
    imull    %ecx
    movl    %r11d, %eax
    subl    %r8d, %r9d
    sarl    $31, %r11d
    movl    %edx, %r8d
    imull    %ecx
    subl    %r10d, %r8d
    movl    %edx, %r10d
    subl    %r11d, %r10d
    pextrd    $3, %xmm0, %r11d
    movl    %r11d, %eax
    imull    %ecx
    sarl    $31, %r11d
    movd    %r10d, %xmm1
    movd    %r9d, %xmm0
    pinsrd    $0x1, %r8d, %xmm0
    subl    %r11d, %edx
    pinsrd    $0x1, %edx, %xmm1
    punpcklqdq    %xmm1, %xmm0
    ret


Thus gcc DOES optimize the division to be done through High Multiplication, but
it is applied to each value separately instead of vectorized ones. Assember
should look like


    movdqa    .LC190(%rip), %xmm0
    pmulld    (%rcx), %xmm0
    pslld    $31, %xmm0
    ret

[Bug c/53645] Missed optimization for division of vector types

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-06-12
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-12 13:34:21 UTC ---
The issue is that no packed integer division exists and that we lower the
vector division to scalar code:

<bb 2>:
  D.2165_4 = BIT_FIELD_REF <x_1(D), 32, 0>;
  D.2166_5 = D.2165_4 / 3;
  D.2167_6 = BIT_FIELD_REF <x_1(D), 32, 32>;
  D.2168_7 = D.2167_6 / 3;
  D.2169_8 = BIT_FIELD_REF <x_1(D), 32, 64>;
  D.2170_9 = D.2169_8 / 3;
  D.2171_10 = BIT_FIELD_REF <x_1(D), 32, 96>;
  D.2172_11 = D.2171_10 / 3;
  D.2159_2 = {D.2166_5, D.2168_7, D.2170_9, D.2172_11};

this lowering should instead try to do the multiplication trick.

Compilable testcase:

typedef int v4si __attribute__((vector_size(16)));
v4si ttt(v4si x) 
{
    return x / (v4si) {3,3,3,3};
}

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
          Component|c                           |tree-optimization
            Summary|Missed optimization for     |Missed optimization for
                   |division of vector types    |vector integer division
                   |                            |lowering
           Severity|normal                      |enhancement

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-12 18:33:56 UTC ---
I think we've talked about enhancing the pattern recognizer to expand it as
mult at the tree level, reusing parts of the expander code for that.  I believe
I've looked at it, but can't find any patch (I think it was around mid December
when
sdivmod pattern recognizer has been added).  I'll look at it again.

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |51581

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-06-12 20:54:43 UTC ---
I think this is a dup of bug 51581.

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-13 09:46:19 UTC ---
(In reply to comment #2)
> I think we've talked about enhancing the pattern recognizer to expand it as
> mult at the tree level, reusing parts of the expander code for that.  I believe
> I've looked at it, but can't find any patch (I think it was around mid December
> when
> sdivmod pattern recognizer has been added).  I'll look at it again.

Note that this is already vector form in source, so enhancing the pattern
recognizer would only help for PR51581.

I think we want to move synth_mult / expand_divmod to the tree level or make
its worker IL independent (possibly with using appropriate costs for vector vs.
scalar during vector lowering).

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |jakub at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-27 08:50:00 UTC ---
Created attachment 27709
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27709
gcc48-pr53645.patch

Untested fix.

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-28 11:38:04 UTC ---
Author: jakub
Date: Thu Jun 28 11:38:01 2012
New Revision: 189043

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189043
Log:
    PR tree-optimization/53645
    * tree-vect-generic.c (add_rshift): New function.
    (expand_vector_divmod): New function.
    (expand_vector_operation): Use it for vector integer
    TRUNC_{DIV,MOD}_EXPR by VECTOR_CST.
    * tree-vect-patterns.c (vect_recog_divmod_pattern): Replace
    unused lguup variable with dummy_int.

    * gcc.c-torture/execute/pr53645.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr53645.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-generic.c
    trunk/gcc/tree-vect-patterns.c

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-28 12:34:10 UTC ---
Fixed.

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-28 17:52:59 UTC ---
Author: jakub
Date: Thu Jun 28 17:52:51 2012
New Revision: 189052

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189052
Log:
    PR tree-optimization/53645
    * tree-vect-generic.c (expand_vector_divmod): Use MULT_HIGHPART_EXPR
    instead of VEC_WIDEN_MULT_{HI,LO}_EXPR followed by VEC_PERM_EXPR
    if possible.

    * gcc.c-torture/execute/pr53645-2.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr53645-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-generic.c

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[ubizjak at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

Uros Bizjak <ubizjak at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
                 CC|                            |ubizjak at gmail dot com
         Resolution|FIXED                       |

--- Comment #9 from Uros Bizjak <ubizjak at gmail dot com> 2012-07-01 10:23:58 UTC ---
Compilation of pr53645.c testcase ICEs with -mno-sse4:

[uros@localhost execute]$ ~/gcc-build/gcc/cc1 -O2 -mno-sse4 -quiet pr53645.c
pr53645.c: In function ‘uq3333’:
pr53645.c:11:11: internal compiler error: in expand_expr_real_2, at expr.c:8971
   *x = *y / ((UV) { a, b, c, d }); \
           ^
pr53645.c:35:1: note: in expansion of macro 'TEST'
 TEST (3, 3, 3, 3)   \
 ^
pr53645.c:40:1: note: in expansion of macro 'TESTS'
 TESTS
 ^
Please submit a full bug report,


(gdb) f 2
#2  0x00000000006bf18d in expand_expr_real_2 (ops=ops@entry=0x7fffffffd120,
target=target@entry=0x0, tmode=tmode@entry=VOIDmode,
modifier=modifier@entry=EXPAND_NORMAL)
    at ../../gcc-svn/trunk/gcc/expr.c:8971
8971          gcc_assert (temp);
(gdb) li
8966            }
8967          else
8968            gcc_assert (GET_MODE_CLASS (GET_MODE (op2)) ==
MODE_VECTOR_INT);
8969
8970          temp = expand_vec_perm (mode, op0, op1, op2, target);
8971          gcc_assert (temp);
8972          return temp;
8973
8974        case DOT_PROD_EXPR:
8975          {
(gdb) p temp
$1 = (rtx_def *) 0x0

expand_vec_perm returns NULL_RTX for mno-sse4.

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-07-02 06:56:28 UTC ---
Author: jakub
Date: Mon Jul  2 06:56:24 2012
New Revision: 189108

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189108
Log:
    PR tree-optimization/53645
    * tree-vect-generic.c (expand_vector_divmod): Use TYPE_MODE (type)
    instead of TYPE_MODE (wider_type) as can_vec_perm_p argument.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-vect-generic.c

[Bug tree-optimization/53645] Missed optimization for vector integer division lowering

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53645

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-07-02 06:59:59 UTC ---
Should be fixed now.