Alternative check for vector refs with same alignment

Message ID 87zieus7dt.fsf@linaro.org
State New
Headers show

Commit Message

Richard Sandiford May 3, 2017, 7:54 a.m.
vect_find_same_alignment_drs uses the ddr dependence distance
to tell whether two references have the same alignment.  Although
that's safe with the current code, there's no particular reason
why a dependence distance of 0 should mean that the accesses start
on the same byte.  E.g. a reference to a full complex value could
in principle depend on a reference to the imaginary component.
A later patch adds support for this kind of dependence.

On the other side, checking modulo vf is pessimistic when the step
divided by the element size is a factor of 2.

This patch instead looks for cases in which the drs have the same
base, offset and step, and for which the difference in their constant
initial values is a multiple of the alignment.

Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

Thanks,
Richard


gcc/
2017-05-03  Richard Sandiford  <richard.sandiford@linaro.org>

	* tree-vect-data-refs.c (vect_find_same_alignment_drs): Remove
	loop_vinfo argument and use of dependence distance vectors.
	Check instead whether the two references differ only in their
	initial value and assume that they have the same alignment if the
	difference is a multiple of the vector alignment.
	(vect_analyze_data_refs_alignment): Update call accordingly.

gcc/testsuite/
	* gcc.dg/vect/vect-103.c: Update wording of dump message.

Comments

Richard Biener May 3, 2017, 10:07 a.m. | #1
On Wed, May 3, 2017 at 9:54 AM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> vect_find_same_alignment_drs uses the ddr dependence distance

> to tell whether two references have the same alignment.  Although

> that's safe with the current code, there's no particular reason

> why a dependence distance of 0 should mean that the accesses start

> on the same byte.  E.g. a reference to a full complex value could

> in principle depend on a reference to the imaginary component.

> A later patch adds support for this kind of dependence.

>

> On the other side, checking modulo vf is pessimistic when the step

> divided by the element size is a factor of 2.

>

> This patch instead looks for cases in which the drs have the same

> base, offset and step, and for which the difference in their constant

> initial values is a multiple of the alignment.


I'm a bit wary about trusting operand_equal_p over dependence analysis.
So, did you (can you) add an assert that the new code computes
same alignment in all cases where the old one did?

> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?


Otherwise looks ok.

Thanks,
Richard.

> Thanks,

> Richard

>

>

> gcc/

> 2017-05-03  Richard Sandiford  <richard.sandiford@linaro.org>

>

>         * tree-vect-data-refs.c (vect_find_same_alignment_drs): Remove

>         loop_vinfo argument and use of dependence distance vectors.

>         Check instead whether the two references differ only in their

>         initial value and assume that they have the same alignment if the

>         difference is a multiple of the vector alignment.

>         (vect_analyze_data_refs_alignment): Update call accordingly.

>

> gcc/testsuite/

>         * gcc.dg/vect/vect-103.c: Update wording of dump message.

>

> Index: gcc/tree-vect-data-refs.c

> ===================================================================

> --- gcc/tree-vect-data-refs.c   2017-04-18 19:52:35.060164268 +0100

> +++ gcc/tree-vect-data-refs.c   2017-05-03 08:48:30.536704993 +0100

> @@ -2042,20 +2042,12 @@ vect_enhance_data_refs_alignment (loop_v

>     vectorization factor.  */

>

>  static void

> -vect_find_same_alignment_drs (struct data_dependence_relation *ddr,

> -                             loop_vec_info loop_vinfo)

> +vect_find_same_alignment_drs (struct data_dependence_relation *ddr)

>  {

> -  unsigned int i;

> -  struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);

> -  int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);

>    struct data_reference *dra = DDR_A (ddr);

>    struct data_reference *drb = DDR_B (ddr);

>    stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));

>    stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));

> -  int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));

> -  int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));

> -  lambda_vector dist_v;

> -  unsigned int loop_depth;

>

>    if (DDR_ARE_DEPENDENT (ddr) == chrec_known)

>      return;

> @@ -2063,48 +2055,37 @@ vect_find_same_alignment_drs (struct dat

>    if (dra == drb)

>      return;

>

> -  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)

> -    return;

> -

> -  /* Loop-based vectorization and known data dependence.  */

> -  if (DDR_NUM_DIST_VECTS (ddr) == 0)

> -    return;

> -

> -  /* Data-dependence analysis reports a distance vector of zero

> -     for data-references that overlap only in the first iteration

> -     but have different sign step (see PR45764).

> -     So as a sanity check require equal DR_STEP.  */

> -  if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

> +  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

> +                       OEP_ADDRESS_OF)

> +      || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

> +      || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>      return;

>

> -  loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));

> -  FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)

> +  /* Two references with distance zero have the same alignment.  */

> +  offset_int diff = (wi::to_offset (DR_INIT (dra))

> +                    - wi::to_offset (DR_INIT (drb)));

> +  if (diff != 0)

>      {

> -      int dist = dist_v[loop_depth];

> +      /* Get the wider of the two alignments.  */

> +      unsigned int align_a = TYPE_ALIGN_UNIT (STMT_VINFO_VECTYPE (stmtinfo_a));

> +      unsigned int align_b = TYPE_ALIGN_UNIT (STMT_VINFO_VECTYPE (stmtinfo_b));

> +      unsigned int max_align = MAX (align_a, align_b);

> +

> +      /* Require the gap to be a multiple of the larger vector alignment.  */

> +      if (!wi::multiple_of_p (diff, max_align, SIGNED))

> +       return;

> +    }

>

> -      if (dump_enabled_p ())

> -       dump_printf_loc (MSG_NOTE, vect_location,

> -                        "dependence distance  = %d.\n", dist);

> -

> -      /* Same loop iteration.  */

> -      if (dist == 0

> -         || (dist % vectorization_factor == 0 && dra_size == drb_size))

> -       {

> -         /* Two references with distance zero have the same alignment.  */

> -         STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);

> -         STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);

> -         if (dump_enabled_p ())

> -           {

> -             dump_printf_loc (MSG_NOTE, vect_location,

> -                              "accesses have the same alignment.\n");

> -             dump_printf (MSG_NOTE,

> -                          "dependence distance modulo vf == 0 between ");

> -             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));

> -             dump_printf (MSG_NOTE,  " and ");

> -             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));

> -             dump_printf (MSG_NOTE, "\n");

> -           }

> -       }

> +  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);

> +  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);

> +  if (dump_enabled_p ())

> +    {

> +      dump_printf_loc (MSG_NOTE, vect_location,

> +                      "accesses have the same alignment: ");

> +      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));

> +      dump_printf (MSG_NOTE,  " and ");

> +      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));

> +      dump_printf (MSG_NOTE, "\n");

>      }

>  }

>

> @@ -2128,7 +2109,7 @@ vect_analyze_data_refs_alignment (loop_v

>    unsigned int i;

>

>    FOR_EACH_VEC_ELT (ddrs, i, ddr)

> -    vect_find_same_alignment_drs (ddr, vinfo);

> +    vect_find_same_alignment_drs (ddr);

>

>    vec<data_reference_p> datarefs = vinfo->datarefs;

>    struct data_reference *dr;

> Index: gcc/testsuite/gcc.dg/vect/vect-103.c

> ===================================================================

> --- gcc/testsuite/gcc.dg/vect/vect-103.c        2015-06-02 23:53:38.000000000 +0100

> +++ gcc/testsuite/gcc.dg/vect/vect-103.c        2017-05-03 08:48:30.536704993 +0100

> @@ -55,5 +55,5 @@ int main (void)

>  }

>

>  /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */

> -/* { dg-final { scan-tree-dump-times "dependence distance modulo vf == 0" 1 "vect" } } */

> +/* { dg-final { scan-tree-dump-times "accesses have the same alignment" 1 "vect" } } */

>
Bin.Cheng May 3, 2017, 10:16 a.m. | #2
On Wed, May 3, 2017 at 11:07 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Wed, May 3, 2017 at 9:54 AM, Richard Sandiford

> <richard.sandiford@linaro.org> wrote:

>> vect_find_same_alignment_drs uses the ddr dependence distance

>> to tell whether two references have the same alignment.  Although

>> that's safe with the current code, there's no particular reason

>> why a dependence distance of 0 should mean that the accesses start

>> on the same byte.  E.g. a reference to a full complex value could

>> in principle depend on a reference to the imaginary component.

>> A later patch adds support for this kind of dependence.

>>

>> On the other side, checking modulo vf is pessimistic when the step

>> divided by the element size is a factor of 2.

>>

>> This patch instead looks for cases in which the drs have the same

>> base, offset and step, and for which the difference in their constant

>> initial values is a multiple of the alignment.

>

> I'm a bit wary about trusting operand_equal_p over dependence analysis.

> So, did you (can you) add an assert that the new code computes

> same alignment in all cases where the old one did?

At the moment operand_equal_p method looks more powerful than
dependence analysis, for example, it can handle the same memory
reference with pointer/array_ref forms like in PR65206.  However,
given dependence check is not expensive here, is it possible to build
the patch on top of it when it fails?

Thanks,
bin
>

>> Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

>

> Otherwise looks ok.

>

> Thanks,

> Richard.

>

>> Thanks,

>> Richard

>>

>>

>> gcc/

>> 2017-05-03  Richard Sandiford  <richard.sandiford@linaro.org>

>>

>>         * tree-vect-data-refs.c (vect_find_same_alignment_drs): Remove

>>         loop_vinfo argument and use of dependence distance vectors.

>>         Check instead whether the two references differ only in their

>>         initial value and assume that they have the same alignment if the

>>         difference is a multiple of the vector alignment.

>>         (vect_analyze_data_refs_alignment): Update call accordingly.

>>

>> gcc/testsuite/

>>         * gcc.dg/vect/vect-103.c: Update wording of dump message.

>>

>> Index: gcc/tree-vect-data-refs.c

>> ===================================================================

>> --- gcc/tree-vect-data-refs.c   2017-04-18 19:52:35.060164268 +0100

>> +++ gcc/tree-vect-data-refs.c   2017-05-03 08:48:30.536704993 +0100

>> @@ -2042,20 +2042,12 @@ vect_enhance_data_refs_alignment (loop_v

>>     vectorization factor.  */

>>

>>  static void

>> -vect_find_same_alignment_drs (struct data_dependence_relation *ddr,

>> -                             loop_vec_info loop_vinfo)

>> +vect_find_same_alignment_drs (struct data_dependence_relation *ddr)

>>  {

>> -  unsigned int i;

>> -  struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);

>> -  int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);

>>    struct data_reference *dra = DDR_A (ddr);

>>    struct data_reference *drb = DDR_B (ddr);

>>    stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));

>>    stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));

>> -  int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));

>> -  int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));

>> -  lambda_vector dist_v;

>> -  unsigned int loop_depth;

>>

>>    if (DDR_ARE_DEPENDENT (ddr) == chrec_known)

>>      return;

>> @@ -2063,48 +2055,37 @@ vect_find_same_alignment_drs (struct dat

>>    if (dra == drb)

>>      return;

>>

>> -  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)

>> -    return;

>> -

>> -  /* Loop-based vectorization and known data dependence.  */

>> -  if (DDR_NUM_DIST_VECTS (ddr) == 0)

>> -    return;

>> -

>> -  /* Data-dependence analysis reports a distance vector of zero

>> -     for data-references that overlap only in the first iteration

>> -     but have different sign step (see PR45764).

>> -     So as a sanity check require equal DR_STEP.  */

>> -  if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>> +  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),

>> +                       OEP_ADDRESS_OF)

>> +      || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)

>> +      || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))

>>      return;

>>

>> -  loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));

>> -  FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)

>> +  /* Two references with distance zero have the same alignment.  */

>> +  offset_int diff = (wi::to_offset (DR_INIT (dra))

>> +                    - wi::to_offset (DR_INIT (drb)));

>> +  if (diff != 0)

>>      {

>> -      int dist = dist_v[loop_depth];

>> +      /* Get the wider of the two alignments.  */

>> +      unsigned int align_a = TYPE_ALIGN_UNIT (STMT_VINFO_VECTYPE (stmtinfo_a));

>> +      unsigned int align_b = TYPE_ALIGN_UNIT (STMT_VINFO_VECTYPE (stmtinfo_b));

>> +      unsigned int max_align = MAX (align_a, align_b);

>> +

>> +      /* Require the gap to be a multiple of the larger vector alignment.  */

>> +      if (!wi::multiple_of_p (diff, max_align, SIGNED))

>> +       return;

>> +    }

>>

>> -      if (dump_enabled_p ())

>> -       dump_printf_loc (MSG_NOTE, vect_location,

>> -                        "dependence distance  = %d.\n", dist);

>> -

>> -      /* Same loop iteration.  */

>> -      if (dist == 0

>> -         || (dist % vectorization_factor == 0 && dra_size == drb_size))

>> -       {

>> -         /* Two references with distance zero have the same alignment.  */

>> -         STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);

>> -         STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);

>> -         if (dump_enabled_p ())

>> -           {

>> -             dump_printf_loc (MSG_NOTE, vect_location,

>> -                              "accesses have the same alignment.\n");

>> -             dump_printf (MSG_NOTE,

>> -                          "dependence distance modulo vf == 0 between ");

>> -             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));

>> -             dump_printf (MSG_NOTE,  " and ");

>> -             dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));

>> -             dump_printf (MSG_NOTE, "\n");

>> -           }

>> -       }

>> +  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);

>> +  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);

>> +  if (dump_enabled_p ())

>> +    {

>> +      dump_printf_loc (MSG_NOTE, vect_location,

>> +                      "accesses have the same alignment: ");

>> +      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));

>> +      dump_printf (MSG_NOTE,  " and ");

>> +      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));

>> +      dump_printf (MSG_NOTE, "\n");

>>      }

>>  }

>>

>> @@ -2128,7 +2109,7 @@ vect_analyze_data_refs_alignment (loop_v

>>    unsigned int i;

>>

>>    FOR_EACH_VEC_ELT (ddrs, i, ddr)

>> -    vect_find_same_alignment_drs (ddr, vinfo);

>> +    vect_find_same_alignment_drs (ddr);

>>

>>    vec<data_reference_p> datarefs = vinfo->datarefs;

>>    struct data_reference *dr;

>> Index: gcc/testsuite/gcc.dg/vect/vect-103.c

>> ===================================================================

>> --- gcc/testsuite/gcc.dg/vect/vect-103.c        2015-06-02 23:53:38.000000000 +0100

>> +++ gcc/testsuite/gcc.dg/vect/vect-103.c        2017-05-03 08:48:30.536704993 +0100

>> @@ -55,5 +55,5 @@ int main (void)

>>  }

>>

>>  /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */

>> -/* { dg-final { scan-tree-dump-times "dependence distance modulo vf == 0" 1 "vect" } } */

>> +/* { dg-final { scan-tree-dump-times "accesses have the same alignment" 1 "vect" } } */

>>
Richard Sandiford May 3, 2017, 10:28 a.m. | #3
"Bin.Cheng" <amker.cheng@gmail.com> writes:
> On Wed, May 3, 2017 at 11:07 AM, Richard Biener

> <richard.guenther@gmail.com> wrote:

>> On Wed, May 3, 2017 at 9:54 AM, Richard Sandiford

>> <richard.sandiford@linaro.org> wrote:

>>> vect_find_same_alignment_drs uses the ddr dependence distance

>>> to tell whether two references have the same alignment.  Although

>>> that's safe with the current code, there's no particular reason

>>> why a dependence distance of 0 should mean that the accesses start

>>> on the same byte.  E.g. a reference to a full complex value could

>>> in principle depend on a reference to the imaginary component.

>>> A later patch adds support for this kind of dependence.

>>>

>>> On the other side, checking modulo vf is pessimistic when the step

>>> divided by the element size is a factor of 2.

>>>

>>> This patch instead looks for cases in which the drs have the same

>>> base, offset and step, and for which the difference in their constant

>>> initial values is a multiple of the alignment.

>>

>> I'm a bit wary about trusting operand_equal_p over dependence analysis.

>> So, did you (can you) add an assert that the new code computes

>> same alignment in all cases where the old one did?


FWIW, the operand_equal_p for the base addresses is the same as the one
used by the dependence analysis:

  /* If the references do not access the same object, we do not know
     whether they alias or not.  We do not care about TBAA or alignment
     info so we can use OEP_ADDRESS_OF to avoid false negatives.
     But the accesses have to use compatible types as otherwise the
     built indices would not match.  */
  if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), OEP_ADDRESS_OF)
      || !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (a)),
			      TREE_TYPE (DR_BASE_OBJECT (b))))
    {
      DDR_ARE_DEPENDENT (res) = chrec_dont_know;
      return res;
    }

> At the moment operand_equal_p method looks more powerful than

> dependence analysis, for example, it can handle the same memory

> reference with pointer/array_ref forms like in PR65206.  However,

> given dependence check is not expensive here, is it possible to build

> the patch on top of it when it fails?


The old check isn't valid after my later patches, because there's
no guarantee that the accesses start on the same byte.  And like
you say, the new check is more powerful in some ways (including
the modulo vf thing I mentioned).

So I'm not sure we can do anything useful with the dependence distance
information.  Sometimes it would give false positives and sometimes
it would give false negatives.

Thanks,
Richard
Richard Sandiford May 31, 2017, 6:55 a.m. | #4
Richard Sandiford <richard.sandiford@linaro.org> writes:
> "Bin.Cheng" <amker.cheng@gmail.com> writes:

>> On Wed, May 3, 2017 at 11:07 AM, Richard Biener

>> <richard.guenther@gmail.com> wrote:

>>> On Wed, May 3, 2017 at 9:54 AM, Richard Sandiford

>>> <richard.sandiford@linaro.org> wrote:

>>>> vect_find_same_alignment_drs uses the ddr dependence distance

>>>> to tell whether two references have the same alignment.  Although

>>>> that's safe with the current code, there's no particular reason

>>>> why a dependence distance of 0 should mean that the accesses start

>>>> on the same byte.  E.g. a reference to a full complex value could

>>>> in principle depend on a reference to the imaginary component.

>>>> A later patch adds support for this kind of dependence.

>>>>

>>>> On the other side, checking modulo vf is pessimistic when the step

>>>> divided by the element size is a factor of 2.

>>>>

>>>> This patch instead looks for cases in which the drs have the same

>>>> base, offset and step, and for which the difference in their constant

>>>> initial values is a multiple of the alignment.

>>>

>>> I'm a bit wary about trusting operand_equal_p over dependence analysis.

>>> So, did you (can you) add an assert that the new code computes

>>> same alignment in all cases where the old one did?

>

> FWIW, the operand_equal_p for the base addresses is the same as the one

> used by the dependence analysis:

>

>   /* If the references do not access the same object, we do not know

>      whether they alias or not.  We do not care about TBAA or alignment

>      info so we can use OEP_ADDRESS_OF to avoid false negatives.

>      But the accesses have to use compatible types as otherwise the

>      built indices would not match.  */

>   if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), OEP_ADDRESS_OF)

>       || !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (a)),

> 			      TREE_TYPE (DR_BASE_OBJECT (b))))

>     {

>       DDR_ARE_DEPENDENT (res) = chrec_dont_know;

>       return res;

>     }

>

>> At the moment operand_equal_p method looks more powerful than

>> dependence analysis, for example, it can handle the same memory

>> reference with pointer/array_ref forms like in PR65206.  However,

>> given dependence check is not expensive here, is it possible to build

>> the patch on top of it when it fails?

>

> The old check isn't valid after my later patches, because there's

> no guarantee that the accesses start on the same byte.  And like

> you say, the new check is more powerful in some ways (including

> the modulo vf thing I mentioned).

>

> So I'm not sure we can do anything useful with the dependence distance

> information.  Sometimes it would give false positives and sometimes

> it would give false negatives.


Upthread you said "otherwise ok" apart from the "I'm a bit wary..." part.
Is the original patch OK given the above?

Thanks,
Richard
Richard Biener May 31, 2017, 7:37 a.m. | #5
On Wed, May 31, 2017 at 8:55 AM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> Richard Sandiford <richard.sandiford@linaro.org> writes:

>> "Bin.Cheng" <amker.cheng@gmail.com> writes:

>>> On Wed, May 3, 2017 at 11:07 AM, Richard Biener

>>> <richard.guenther@gmail.com> wrote:

>>>> On Wed, May 3, 2017 at 9:54 AM, Richard Sandiford

>>>> <richard.sandiford@linaro.org> wrote:

>>>>> vect_find_same_alignment_drs uses the ddr dependence distance

>>>>> to tell whether two references have the same alignment.  Although

>>>>> that's safe with the current code, there's no particular reason

>>>>> why a dependence distance of 0 should mean that the accesses start

>>>>> on the same byte.  E.g. a reference to a full complex value could

>>>>> in principle depend on a reference to the imaginary component.

>>>>> A later patch adds support for this kind of dependence.

>>>>>

>>>>> On the other side, checking modulo vf is pessimistic when the step

>>>>> divided by the element size is a factor of 2.

>>>>>

>>>>> This patch instead looks for cases in which the drs have the same

>>>>> base, offset and step, and for which the difference in their constant

>>>>> initial values is a multiple of the alignment.

>>>>

>>>> I'm a bit wary about trusting operand_equal_p over dependence analysis.

>>>> So, did you (can you) add an assert that the new code computes

>>>> same alignment in all cases where the old one did?

>>

>> FWIW, the operand_equal_p for the base addresses is the same as the one

>> used by the dependence analysis:

>>

>>   /* If the references do not access the same object, we do not know

>>      whether they alias or not.  We do not care about TBAA or alignment

>>      info so we can use OEP_ADDRESS_OF to avoid false negatives.

>>      But the accesses have to use compatible types as otherwise the

>>      built indices would not match.  */

>>   if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), OEP_ADDRESS_OF)

>>       || !types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (a)),

>>                             TREE_TYPE (DR_BASE_OBJECT (b))))

>>     {

>>       DDR_ARE_DEPENDENT (res) = chrec_dont_know;

>>       return res;

>>     }

>>

>>> At the moment operand_equal_p method looks more powerful than

>>> dependence analysis, for example, it can handle the same memory

>>> reference with pointer/array_ref forms like in PR65206.  However,

>>> given dependence check is not expensive here, is it possible to build

>>> the patch on top of it when it fails?

>>

>> The old check isn't valid after my later patches, because there's

>> no guarantee that the accesses start on the same byte.  And like

>> you say, the new check is more powerful in some ways (including

>> the modulo vf thing I mentioned).

>>

>> So I'm not sure we can do anything useful with the dependence distance

>> information.  Sometimes it would give false positives and sometimes

>> it would give false negatives.

>

> Upthread you said "otherwise ok" apart from the "I'm a bit wary..." part.

> Is the original patch OK given the above?


Yes.

Thanks,
Richard.

> Thanks,

> Richard

Patch hide | download patch | download mbox

Index: gcc/tree-vect-data-refs.c
===================================================================
--- gcc/tree-vect-data-refs.c	2017-04-18 19:52:35.060164268 +0100
+++ gcc/tree-vect-data-refs.c	2017-05-03 08:48:30.536704993 +0100
@@ -2042,20 +2042,12 @@  vect_enhance_data_refs_alignment (loop_v
    vectorization factor.  */
 
 static void
-vect_find_same_alignment_drs (struct data_dependence_relation *ddr,
-			      loop_vec_info loop_vinfo)
+vect_find_same_alignment_drs (struct data_dependence_relation *ddr)
 {
-  unsigned int i;
-  struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
-  int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
   struct data_reference *dra = DDR_A (ddr);
   struct data_reference *drb = DDR_B (ddr);
   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
-  int dra_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dra))));
-  int drb_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (drb))));
-  lambda_vector dist_v;
-  unsigned int loop_depth;
 
   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
     return;
@@ -2063,48 +2055,37 @@  vect_find_same_alignment_drs (struct dat
   if (dra == drb)
     return;
 
-  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
-    return;
-
-  /* Loop-based vectorization and known data dependence.  */
-  if (DDR_NUM_DIST_VECTS (ddr) == 0)
-    return;
-
-  /* Data-dependence analysis reports a distance vector of zero
-     for data-references that overlap only in the first iteration
-     but have different sign step (see PR45764).
-     So as a sanity check require equal DR_STEP.  */
-  if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
+  if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb),
+			OEP_ADDRESS_OF)
+      || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0)
+      || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
     return;
 
-  loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
-  FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
+  /* Two references with distance zero have the same alignment.  */
+  offset_int diff = (wi::to_offset (DR_INIT (dra))
+		     - wi::to_offset (DR_INIT (drb)));
+  if (diff != 0)
     {
-      int dist = dist_v[loop_depth];
+      /* Get the wider of the two alignments.  */
+      unsigned int align_a = TYPE_ALIGN_UNIT (STMT_VINFO_VECTYPE (stmtinfo_a));
+      unsigned int align_b = TYPE_ALIGN_UNIT (STMT_VINFO_VECTYPE (stmtinfo_b));
+      unsigned int max_align = MAX (align_a, align_b);
+
+      /* Require the gap to be a multiple of the larger vector alignment.  */
+      if (!wi::multiple_of_p (diff, max_align, SIGNED))
+	return;
+    }
 
-      if (dump_enabled_p ())
-	dump_printf_loc (MSG_NOTE, vect_location,
-	                 "dependence distance  = %d.\n", dist);
-
-      /* Same loop iteration.  */
-      if (dist == 0
-	  || (dist % vectorization_factor == 0 && dra_size == drb_size))
-	{
-	  /* Two references with distance zero have the same alignment.  */
-	  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);
-	  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);
-	  if (dump_enabled_p ())
-	    {
-	      dump_printf_loc (MSG_NOTE, vect_location,
-	                       "accesses have the same alignment.\n");
-	      dump_printf (MSG_NOTE,
-	                   "dependence distance modulo vf == 0 between ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
-	      dump_printf (MSG_NOTE,  " and ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
-	      dump_printf (MSG_NOTE, "\n");
-	    }
-	}
+  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a).safe_push (drb);
+  STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b).safe_push (dra);
+  if (dump_enabled_p ())
+    {
+      dump_printf_loc (MSG_NOTE, vect_location,
+		       "accesses have the same alignment: ");
+      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dra));
+      dump_printf (MSG_NOTE,  " and ");
+      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (drb));
+      dump_printf (MSG_NOTE, "\n");
     }
 }
 
@@ -2128,7 +2109,7 @@  vect_analyze_data_refs_alignment (loop_v
   unsigned int i;
 
   FOR_EACH_VEC_ELT (ddrs, i, ddr)
-    vect_find_same_alignment_drs (ddr, vinfo);
+    vect_find_same_alignment_drs (ddr);
 
   vec<data_reference_p> datarefs = vinfo->datarefs;
   struct data_reference *dr;
Index: gcc/testsuite/gcc.dg/vect/vect-103.c
===================================================================
--- gcc/testsuite/gcc.dg/vect/vect-103.c	2015-06-02 23:53:38.000000000 +0100
+++ gcc/testsuite/gcc.dg/vect/vect-103.c	2017-05-03 08:48:30.536704993 +0100
@@ -55,5 +55,5 @@  int main (void)
 }
 
 /* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
-/* { dg-final { scan-tree-dump-times "dependence distance modulo vf == 0" 1 "vect" } } */
+/* { dg-final { scan-tree-dump-times "accesses have the same alignment" 1 "vect" } } */