[Bug tree-optimization/51581] New: Integer division by constant is not vectorized

[Bug tree-optimization/51581] New: Integer division by constant is not vectorized

[jakub at gcc dot gnu.org]

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

             Bug #: 51581
           Summary: Integer division by constant is not vectorized
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: jakub@gcc.gnu.org
                CC: irar@gcc.gnu.org


(Now in 4.7 with the exception of division by power of 2 constant).

But as the following testcase shows, if target doesn't have a vector integer
division instruction, we could reuse expmed.c choose_multiplier and parts of
expand_divmod to pattern recognize it as multiplication by some constant and
some shifts.  All we need is a vectorized highpart signed/unsigned
multiplication or widening multiplication for the vector mode in question
(e.g. on i?86/x86_64 we have a highpart signed/unsigned multiplication for
V*HImode vectors and widening multiplication (perhaps for AVX2 purposes we
could
come up with better optimized highpart V8SImode pattern) for V*SImode vectors.

[Bug tree-optimization/51581] Integer division by constant is not vectorized

[jakub at gcc dot gnu.org]

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-12-16 16:25:26 UTC ---
Created attachment 26111
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26111
div2.c

Testcase where f1-f6 are normal integer division loops and f7-f12 the same
division rewritten manually as multiplication the expander performs, so it can
be autovectorized.  With a pattern recognizer we'd do something similar to
this.

Timings for -O3 -mavx on SandyBridge CPU, in each case 500000 calls to fN ():
500000 * 4096 divisions:
/ 3   0m1.964s -> 0m0.706s
/ 3U  0m1.626s -> 0m0.705s
/ 18  0m2.181s -> 0m0.868s
/ 18U 0m1.629s -> 0m0.708s
/ 19  0m2.183s -> 0m0.863s
/ 19U 0m2.635s -> 0m0.862s

[Bug tree-optimization/51581] Integer division by constant is not vectorized

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-12-19
     Ever Confirmed|0                           |1
           Severity|normal                      |enhancement

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-12-19 09:34:08 UTC ---
Confirmed.

[Bug tree-optimization/51581] Integer division by constant is not vectorized

[jakub at gcc dot gnu.org]

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

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 #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-13 19:21:49 UTC ---
Created attachment 27617
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27617
gcc48-pr51581.patch

Untested fix.

[Bug tree-optimization/51581] Integer division by constant is not vectorized

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-14 13:31:57 UTC ---
Created attachment 27618
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27618
gcc48-pr51581.patch

Updated patch.

[Bug tree-optimization/51581] Integer division by constant is not vectorized

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-15 11:07:54 UTC ---
Author: jakub
Date: Fri Jun 15 11:07:47 2012
New Revision: 188656

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=188656
Log:
    PR tree-optimization/51581
    * expr.h (choose_multiplier): New prototype.
    * expmed.c (choose_multiplier): No longer static.
    Change multiplier_ptr from rtx * to UHWI *.
    (expand_divmod): Adjust callers.
    * tree-vect-patterns.c (vect_recog_sdivmod_pow2_pattern):
    Renamed to...
    (vect_recog_divmod_pattern): ... this.  Pass bb_vinfo as last
    argument to new_stmt_vec_info.  Attempt to optimize also divisions
    by non-pow2 constants if integer vector division isn't supported.
    * tree-vect-stmts.c (vect_analyze_stmt): If node != NULL,
    don't look at pattern stmts and sequences.

    * gcc.c-torture/execute/pr51581-1.c: New test.
    * gcc.c-torture/execute/pr51581-2.c: New test.
    * gcc.dg/vect/pr51581-1.c: New test.
    * gcc.dg/vect/pr51581-2.c: New test.
    * gcc.dg/vect/pr51581-3.c: New test.
    * gcc.target/i386/avx-pr51581-1.c: New test.
    * gcc.target/i386/avx-pr51581-2.c: New test.
    * gcc.target/i386/avx2-pr51581-1.c: New test.
    * gcc.target/i386/avx2-pr51581-2.c: New test.
    * gcc.dg/vect/slp-26.c (main1): Divide by 0x8031 instead of 3.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr51581-1.c
    trunk/gcc/testsuite/gcc.c-torture/execute/pr51581-2.c
    trunk/gcc/testsuite/gcc.dg/vect/pr51581-1.c
    trunk/gcc/testsuite/gcc.dg/vect/pr51581-2.c
    trunk/gcc/testsuite/gcc.dg/vect/pr51581-3.c
    trunk/gcc/testsuite/gcc.target/i386/avx-pr51581-1.c
    trunk/gcc/testsuite/gcc.target/i386/avx-pr51581-2.c
    trunk/gcc/testsuite/gcc.target/i386/avx2-pr51581-1.c
    trunk/gcc/testsuite/gcc.target/i386/avx2-pr51581-2.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/expmed.c
    trunk/gcc/expr.h
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/vect/slp-26.c
    trunk/gcc/tree-vect-patterns.c
    trunk/gcc/tree-vect-stmts.c

[Bug tree-optimization/51581] Integer division by constant is not vectorized

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.8.0

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-15 11:09:11 UTC ---
Fixed for 4.8+.

[Bug tree-optimization/51581] Integer division by constant is not vectorized

[jakub at gcc dot gnu.org]

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-06-28 17:54:03 UTC ---
Author: jakub
Date: Thu Jun 28 17:53:58 2012
New Revision: 189053

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189053
Log:
    PR tree-optimization/51581
    * tree-vect-stmts.c (permute_vec_elements): Add forward decl.
    (vectorizable_operation): Handle vectorization of MULT_HIGHPART_EXPR
    also using VEC_WIDEN_MULT_*_EXPR or builtin_mul_widen_* plus
    VEC_PERM_EXPR if vector MULT_HIGHPART_EXPR isn't supported.
    * tree-vect-patterns.c (vect_recog_divmod_pattern): Use
    MULT_HIGHPART_EXPR instead of VEC_WIDEN_MULT_*_EXPR and shifts.

    * gcc.dg/vect/pr51581-4.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/vect/pr51581-4.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vect-patterns.c
    trunk/gcc/tree-vect-stmts.c