[Bug tree-optimization/51254] New: Missed Optimization: IVOPTS don't handle unaligned memory access.

[Bug tree-optimization/51254] New: Missed Optimization: IVOPTS don't handle unaligned memory access.

[duyuehai at gmail dot com]

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

             Bug #: 51254
           Summary: Missed Optimization: IVOPTS don't handle unaligned
                    memory access.
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: duyuehai@gmail.com


IVOPTS don't handle unaligned memory access because
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17949. but without this
optimization, we may generate sub-optimal code.

here is a case from EEMBC autcor00:

fxpAutoCorrelation (
    e_s16 *InputData,
    e_s16 *AutoCorrData,
    e_s16 DataSize,
    e_s16 NumberOfLags,
    e_s16 Scale
)
{
    n_int i;
    n_int lag;
    n_int LastIndex;
    e_s32 Accumulator;


    for (lag = 0; lag < NumberOfLags; lag++) {
        Accumulator = 0;
        LastIndex = DataSize - lag;
        for (i = 0; i < LastIndex; i++) {
            Accumulator += ((e_s32) InputData[i] * (e_s32) InputData[i+lag]) >>
Scale;
        }


        AutoCorrData[lag] = (e_s16) (Accumulator >> 16) ;
    }
}

Compile it with a arm cross-compiler
Compile flags:
-O3 -mfpu=neon -mfloat-abi=softfp 

the key vectorized loop is:

.L8:
    add    r7, ip, sl
    vldmia    ip, {d18-d19}
    vld1.16    {q8}, [r7]
    vmull.s16 q12, d18, d16
    vshl.s32    q12, q12, q11
    vmull.s16 q8, d19, d17
    add    r4, r4, #1
    vadd.i32    q10, q12, q10
    vshl.s32    q8, q8, q11
    cmp    r4, r8
    vadd.i32    q10, q8, q10
    add    ip, ip, #16
    bcc    .L8

  There are three ADD insn in it which used to calculate address and loop
counter, but we can see we only need one ADD insn for calculating loop counter,
other two can be optimized with address post increment operation.

  The root cause of this is because IVOPTS don't handle unaligned memory
access. if we remove those check in find_interesting_uses_address, the result
is:

.L8:
    vldmia    r6!, {d18-d19}
    vld1.16    {q8}, [r7]!
    vmull.s16 q12, d18, d16
    vshl.s32    q12, q12, q11
    vmull.s16 q8, d19, d17
    add    r4, r4, #1
    vadd.i32    q10, q12, q10
    vshl.s32    q8, q8, q11
    cmp    r4, sl
    vadd.i32    q10, q8, q10
    bcc    .L8

  This should be the result we want.

see http://gcc.gnu.org/ml/gcc/2011-11/msg00311.html for more details.

[Bug tree-optimization/51254] Missed Optimization: IVOPTS don't handle unaligned memory access.

[duyuehai at gmail dot com]

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

--- Comment #1 from Yuehai Du <duyuehai at gmail dot com> 2011-11-21 04:23:44 UTC ---
Created attachment 25870
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25870
testcase

[Bug tree-optimization/51254] Missed Optimization: IVOPTS don't handle unaligned memory access.

[duyuehai at gmail dot com]

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

Yuehai Du <duyuehai at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |duyuehai at gmail dot com,
                   |                            |rguenth at gcc dot gnu.org

--- Comment #2 from Yuehai Du <duyuehai at gmail dot com> 2011-12-13 04:15:12 UTC ---
Hi Richard
  would it be ok if i submit a patch like this to fix this bug:

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c    (版本 182270)
+++ gcc/tree-ssa-loop-ivopts.c    (工作副本)
@@ -102,6 +102,7 @@ along with GCC; see the file COPYING3.  If not see
    cost of different addressing modes.  This should be moved to a TBD
    interface between the GIMPLE and RTL worlds.  */
 #include "expr.h"
+#include "optabs.h"

 /* The infinite cost.  */
 #define INFTY 10000000
@@ -1771,6 +1772,7 @@ find_interesting_uses_address (struct ivopts_data
     }
   else
     {
+      enum machine_mode mem_mode;
       ifs_ivopts_data.ivopts_data = data;
       ifs_ivopts_data.stmt = stmt;
       ifs_ivopts_data.step = size_zero_node;
@@ -1786,7 +1788,9 @@ find_interesting_uses_address (struct ivopts_data

       /* Moreover, on strict alignment platforms, check that it is
      sufficiently aligned.  */
-      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
+      mem_mode = TYPE_MODE (TREE_TYPE (*op_p));
+      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step)
+          && optab_handler (movmisalign_optab, mem_mode) == CODE_FOR_nothing)
     goto fail;

       base = build_fold_addr_expr (base);

[Bug tree-optimization/51254] Missed Optimization: IVOPTS don't handle unaligned memory access.

[duyuehai at gmail dot com]

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

--- Comment #3 from Yuehai Du <duyuehai at gmail dot com> 2011-12-13 04:16:22 UTC ---
Hi Richard
  would it be ok if i submit a patch like this to fix this bug:

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c    (版本 182270)
+++ gcc/tree-ssa-loop-ivopts.c    (工作副本)
@@ -102,6 +102,7 @@ along with GCC; see the file COPYING3.  If not see
    cost of different addressing modes.  This should be moved to a TBD
    interface between the GIMPLE and RTL worlds.  */
 #include "expr.h"
+#include "optabs.h"

 /* The infinite cost.  */
 #define INFTY 10000000
@@ -1771,6 +1772,7 @@ find_interesting_uses_address (struct ivopts_data
     }
   else
     {
+      enum machine_mode mem_mode;
       ifs_ivopts_data.ivopts_data = data;
       ifs_ivopts_data.stmt = stmt;
       ifs_ivopts_data.step = size_zero_node;
@@ -1786,7 +1788,9 @@ find_interesting_uses_address (struct ivopts_data

       /* Moreover, on strict alignment platforms, check that it is
      sufficiently aligned.  */
-      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
+      mem_mode = TYPE_MODE (TREE_TYPE (*op_p));
+      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step)
+          && optab_handler (movmisalign_optab, mem_mode) == CODE_FOR_nothing)
     goto fail;

       base = build_fold_addr_expr (base);

[Bug tree-optimization/51254] Missed Optimization: IVOPTS don't handle unaligned memory access.

[rguenther at suse dot de]

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

--- Comment #4 from rguenther at suse dot de <rguenther at suse dot de> 2011-12-13 10:27:48 UTC ---
On Tue, 13 Dec 2011, duyuehai at gmail dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51254
> 
> Yuehai Du <duyuehai at gmail dot com> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |duyuehai at gmail dot com,
>                    |                            |rguenth at gcc dot gnu.org
> 
> --- Comment #2 from Yuehai Du <duyuehai at gmail dot com> 2011-12-13 04:15:12 UTC ---
> Hi Richard
>   would it be ok if i submit a patch like this to fix this bug:
> 
> Index: gcc/tree-ssa-loop-ivopts.c
> ===================================================================
> --- gcc/tree-ssa-loop-ivopts.c    (版本 182270)
> +++ gcc/tree-ssa-loop-ivopts.c    (工作副本)
> @@ -102,6 +102,7 @@ along with GCC; see the file COPYING3.  If not see
>     cost of different addressing modes.  This should be moved to a TBD
>     interface between the GIMPLE and RTL worlds.  */
>  #include "expr.h"
> +#include "optabs.h"
> 
>  /* The infinite cost.  */
>  #define INFTY 10000000
> @@ -1771,6 +1772,7 @@ find_interesting_uses_address (struct ivopts_data
>      }
>    else
>      {
> +      enum machine_mode mem_mode;
>        ifs_ivopts_data.ivopts_data = data;
>        ifs_ivopts_data.stmt = stmt;
>        ifs_ivopts_data.step = size_zero_node;
> @@ -1786,7 +1788,9 @@ find_interesting_uses_address (struct ivopts_data
> 
>        /* Moreover, on strict alignment platforms, check that it is
>       sufficiently aligned.  */
> -      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
> +      mem_mode = TYPE_MODE (TREE_TYPE (*op_p));
> +      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step)
> +          && optab_handler (movmisalign_optab, mem_mode) == CODE_FOR_nothing)
>      goto fail;
> 
>        base = build_fold_addr_expr (base);

This won't fix it - the movmisalign optab will not be used at expansion
time as IVOPTs does not properly transfer the misalignment to the
access type.

Richard.

[Bug tree-optimization/51254] Missed Optimization: IVOPTS don't handle unaligned memory access.

[duyuehai at gmail dot com]

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

--- Comment #5 from Yuehai Du <duyuehai at gmail dot com> 2011-12-14 02:29:07 UTC ---
(In reply to comment #4)
> On Tue, 13 Dec 2011, duyuehai at gmail dot com wrote:
> 
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51254
> > 
> > Yuehai Du <duyuehai at gmail dot com> changed:
> > 
> >            What    |Removed                     |Added
> > ----------------------------------------------------------------------------
> >                  CC|                            |duyuehai at gmail dot com,
> >                    |                            |rguenth at gcc dot gnu.org
> > 
> > --- Comment #2 from Yuehai Du <duyuehai at gmail dot com> 2011-12-13 04:15:12 UTC ---
> > Hi Richard
> >   would it be ok if i submit a patch like this to fix this bug:
> > 
> > Index: gcc/tree-ssa-loop-ivopts.c
> > ===================================================================
> > --- gcc/tree-ssa-loop-ivopts.c    (版本 182270)
> > +++ gcc/tree-ssa-loop-ivopts.c    (工作副本)
> > @@ -102,6 +102,7 @@ along with GCC; see the file COPYING3.  If not see
> >     cost of different addressing modes.  This should be moved to a TBD
> >     interface between the GIMPLE and RTL worlds.  */
> >  #include "expr.h"
> > +#include "optabs.h"
> > 
> >  /* The infinite cost.  */
> >  #define INFTY 10000000
> > @@ -1771,6 +1772,7 @@ find_interesting_uses_address (struct ivopts_data
> >      }
> >    else
> >      {
> > +      enum machine_mode mem_mode;
> >        ifs_ivopts_data.ivopts_data = data;
> >        ifs_ivopts_data.stmt = stmt;
> >        ifs_ivopts_data.step = size_zero_node;
> > @@ -1786,7 +1788,9 @@ find_interesting_uses_address (struct ivopts_data
> > 
> >        /* Moreover, on strict alignment platforms, check that it is
> >       sufficiently aligned.  */
> > -      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
> > +      mem_mode = TYPE_MODE (TREE_TYPE (*op_p));
> > +      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step)
> > +          && optab_handler (movmisalign_optab, mem_mode) == CODE_FOR_nothing)
> >      goto fail;
> > 
> >        base = build_fold_addr_expr (base);
> 
> This won't fix it - the movmisalign optab will not be used at expansion
> time as IVOPTs does not properly transfer the misalignment to the
> access type.

sorry, i made a mistake here. 
My initial target is to make IVOPTS work on vector type misaligned access. And
i see the misalignment information for unaligned vector type access is stored
in type and pointer.
tree-ssa-loop-ivopts.c:
            else if (DR_MISALIGNMENT (first_dr) == -1)
              {
            TREE_TYPE (data_ref)
              = build_aligned_type (TREE_TYPE (data_ref),
                        TYPE_ALIGN (elem_type));
            pi->align = TYPE_ALIGN_UNIT (elem_type);
            pi->misalign = 0;
              }
            else
              {
            TREE_TYPE (data_ref)
              = build_aligned_type (TREE_TYPE (data_ref),
                        TYPE_ALIGN (elem_type));
            pi->misalign = DR_MISALIGNMENT (first_dr);
              }

and IVOPTS will create same type mem_ref when it rewrite use for address. 

so do this work?
      align = TYPE_ALIGN(TREE_TYPE(*op_p));
      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step)
          && !(mem_mode != BLK_MODE 
              && align < GET_MODE_ALIGNMENT (mem_mode)
              && optab_handler (movmisalign_optab, mem_mode) !=
CODE_FOR_nothing
              )

)
    goto fail;

--
Yuehai Du


> 
> Richard.

[Bug tree-optimization/51254] Missed Optimization: IVOPTS don't handle unaligned memory access.

[rguenther at suse dot de]

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

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> 2011-12-14 09:38:51 UTC ---
On Wed, 14 Dec 2011, duyuehai at gmail dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51254
> 
> --- Comment #5 from Yuehai Du <duyuehai at gmail dot com> 2011-12-14 02:29:07 UTC ---
> (In reply to comment #4)
> > On Tue, 13 Dec 2011, duyuehai at gmail dot com wrote:
> > 
> > > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51254
> > > 
> > > Yuehai Du <duyuehai at gmail dot com> changed:
> > > 
> > >            What    |Removed                     |Added
> > > ----------------------------------------------------------------------------
> > >                  CC|                            |duyuehai at gmail dot com,
> > >                    |                            |rguenth at gcc dot gnu.org
> > > 
> > > --- Comment #2 from Yuehai Du <duyuehai at gmail dot com> 2011-12-13 04:15:12 UTC ---
> > > Hi Richard
> > >   would it be ok if i submit a patch like this to fix this bug:
> > > 
> > > Index: gcc/tree-ssa-loop-ivopts.c
> > > ===================================================================
> > > --- gcc/tree-ssa-loop-ivopts.c    (版本 182270)
> > > +++ gcc/tree-ssa-loop-ivopts.c    (工作副本)
> > > @@ -102,6 +102,7 @@ along with GCC; see the file COPYING3.  If not see
> > >     cost of different addressing modes.  This should be moved to a TBD
> > >     interface between the GIMPLE and RTL worlds.  */
> > >  #include "expr.h"
> > > +#include "optabs.h"
> > > 
> > >  /* The infinite cost.  */
> > >  #define INFTY 10000000
> > > @@ -1771,6 +1772,7 @@ find_interesting_uses_address (struct ivopts_data
> > >      }
> > >    else
> > >      {
> > > +      enum machine_mode mem_mode;
> > >        ifs_ivopts_data.ivopts_data = data;
> > >        ifs_ivopts_data.stmt = stmt;
> > >        ifs_ivopts_data.step = size_zero_node;
> > > @@ -1786,7 +1788,9 @@ find_interesting_uses_address (struct ivopts_data
> > > 
> > >        /* Moreover, on strict alignment platforms, check that it is
> > >       sufficiently aligned.  */
> > > -      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step))
> > > +      mem_mode = TYPE_MODE (TREE_TYPE (*op_p));
> > > +      if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step)
> > > +          && optab_handler (movmisalign_optab, mem_mode) == CODE_FOR_nothing)
> > >      goto fail;
> > > 
> > >        base = build_fold_addr_expr (base);
> > 
> > This won't fix it - the movmisalign optab will not be used at expansion
> > time as IVOPTs does not properly transfer the misalignment to the
> > access type.
> 
> sorry, i made a mistake here. 
> My initial target is to make IVOPTS work on vector type misaligned access. And
> i see the misalignment information for unaligned vector type access is stored
> in type and pointer.
> tree-ssa-loop-ivopts.c:
>             else if (DR_MISALIGNMENT (first_dr) == -1)
>               {
>             TREE_TYPE (data_ref)
>               = build_aligned_type (TREE_TYPE (data_ref),
>                         TYPE_ALIGN (elem_type));
>             pi->align = TYPE_ALIGN_UNIT (elem_type);
>             pi->misalign = 0;
>               }
>             else
>               {
>             TREE_TYPE (data_ref)
>               = build_aligned_type (TREE_TYPE (data_ref),
>                         TYPE_ALIGN (elem_type));
>             pi->misalign = DR_MISALIGNMENT (first_dr);
>               }
> 
> and IVOPTS will create same type mem_ref when it rewrite use for address. 
> 
> so do this work?
>       align = TYPE_ALIGN(TREE_TYPE(*op_p));
>       if (STRICT_ALIGNMENT && may_be_unaligned_p (base, step)
>           && !(mem_mode != BLK_MODE 
>               && align < GET_MODE_ALIGNMENT (mem_mode)
>               && optab_handler (movmisalign_optab, mem_mode) !=
> CODE_FOR_nothing
>               )
> 
> )
>     goto fail;

I suppose this should work.



> --
> Yuehai Du
> 
> 
> > 
> > Richard.
> 
>