public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: "Bin.Cheng" <amker.cheng@gmail.com>
To: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
		Richard Sandiford <richard.sandiford@linaro.org>
Subject: Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
Date: Wed, 24 May 2017 10:54:00 -0000	[thread overview]
Message-ID: <CAHFci2_EMsCfRvriHKb2BPeJaJVWX9Aoy8Co-kFh2N8=rB8zvQ@mail.gmail.com> (raw)
In-Reply-To: <87r2zfzch4.fsf@linaro.org>

[-- Attachment #1: Type: text/plain, Size: 9308 bytes --]

On Tue, May 23, 2017 at 6:53 PM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> AIUI, the reason the old code mishandled negative steps was that the
> associated segment lengths were stored as sizetype and so looked like
> big unsigned values.  Those values therefore satisfied tree_fits_uhwi_p
> even though they were semantically negative.  Is that right?
Yes, and the undesired wrapping behavior when such large unsigned hwi
is involved in computation.  But I think there are possible leaks in
the code even after this patch, as embedded below.
>
> Assuming yes, and quoting the change as a context diff...
>
>> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
>> index a5f8c1c..f0799d9 100644
>> *** a/gcc/tree-data-ref.c
>> --- b/gcc/tree-data-ref.c
>> ***************
>> *** 1259,1264 ****
>> --- 1259,1273 ----
>>             != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node))
>>           continue;
>>
>> +       bool neg_step
>> +         = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0);
>> +
>> +       /* DR_A1 and DR_A2 must have the same step if it's negative.  */
>> +       if (neg_step
>> +           && tree_int_cst_compare (DR_STEP (dr_a1->dr),
>> +                                    DR_STEP (dr_a2->dr)) != 0)
>> +         continue;
>> +
>
> [Why do they need to be the same step?]
There are two reasons.  First is to simplify diff computation between
dr_a1 and dr_a2, otherwise we need to adjust diff for negative steps.
And wrapping behavior needs to be handled when adjusting diff with
steps.  The second reason is not fully handled in this patch.  We now
only set merged segment length to MAX only when both dr_a1->seg_len
and dr_a2->seg_len are constant, as below:
+          if (tree_fits_uhwi_p (dr_a1->seg_len)
+              && tree_fits_uhwi_p (dr_a2->seg_len))
+            new_seg_len
+              = size_int (MAX (tree_to_uhwi (dr_a1->seg_len),
+                       diff + tree_to_uhwi (dr_a2->seg_len)));
+          else
+            new_seg_len
+              = size_binop (PLUS_EXPR, dr_a2->seg_len, size_int (diff));
In fact, we should do this for else branch too.  with different steps,
it is still possible that dr_a1-seg_len > dr_a2->seg_len + diff.  Here
I only restrict it to negative DR_STEP.  Patch updated with
explanation in comment.
>
>>         /* Make sure dr_a1 starts left of dr_a2.  */
>>         if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
>>           std::swap (*dr_a1, *dr_a2);
>> ***************
>> *** 1266,1325 ****
>>         bool do_remove = false;
>>         unsigned HOST_WIDE_INT diff
>>           = (tree_to_shwi (DR_INIT (dr_a2->dr))
>> !                - tree_to_shwi (DR_INIT (dr_a1->dr)));
>>
>> !       /* If the left segment does not extend beyond the start of the
>> !          right segment the new segment length is that of the right
>> !          plus the segment distance.  */
>> !       if (tree_fits_uhwi_p (dr_a1->seg_len)
>> !           && compare_tree_int (dr_a1->seg_len, diff) <= 0)
>>           {
>> !           dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
>> !                                        size_int (diff));
>> !           do_remove = true;
>>           }
>> !       /* Generally the new segment length is the maximum of the
>> !          left segment size and the right segment size plus the distance.
>> !          ???  We can also build tree MAX_EXPR here but it's not clear this
>> !          is profitable.  */
>> !       else if (tree_fits_uhwi_p (dr_a1->seg_len)
>> !                && tree_fits_uhwi_p (dr_a2->seg_len))
>> !         {
>> !           unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
>> !           unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
>> !           dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
>> !           do_remove = true;
>> !         }
>> !       /* Now we check if the following condition is satisfied:
>>
>> !          DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
>>
>> !          where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
>> !          SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
>> !          have to make a best estimation.  We can get the minimum value
>> !          of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
>> !          then either of the following two conditions can guarantee the
>> !          one above:
>>
>> !          1: DIFF <= MIN_SEG_LEN_B
>> !          2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
>> !       else
>>           {
>> !           unsigned HOST_WIDE_INT min_seg_len_b
>> !             = (tree_fits_uhwi_p (dr_b1->seg_len)
>> !                ? tree_to_uhwi (dr_b1->seg_len)
>> !                : factor);
>>
>>             if (diff <= min_seg_len_b
>>                 || (tree_fits_uhwi_p (dr_a1->seg_len)
>> !                   && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
>>               {
>> !               dr_a1->seg_len = size_binop (PLUS_EXPR,
>> !                                            dr_a2->seg_len, size_int (diff));
>>                 do_remove = true;
>>               }
>>           }
>>
>>         if (do_remove)
>>           {
>>             if (dump_enabled_p ())
>> --- 1275,1375 ----
>>         bool do_remove = false;
>>         unsigned HOST_WIDE_INT diff
>>           = (tree_to_shwi (DR_INIT (dr_a2->dr))
>> !            - tree_to_shwi (DR_INIT (dr_a1->dr)));
>> !       tree new_seg_len;
>> !       unsigned HOST_WIDE_INT min_seg_len_b;
>>
>> !       if (tree_fits_uhwi_p (dr_b1->seg_len))
>>           {
>> !           min_seg_len_b = tree_to_uhwi (dr_b1->seg_len);
>> !           if (tree_int_cst_sign_bit (dr_b1->seg_len))
>> !             min_seg_len_b = 0 - min_seg_len_b;
>>           }
>> !       else
>> !         min_seg_len_b = factor;
>
> ...I'm not sure how safe this or the later neg_step handling is
> for 16-bit and 32-bit sizetypes.  It might be better to use wide_int
I think it could be a problem in case sizetype is smaller than
unsigned_type_for(ptr).
> instead, so that all arithmetic and comparisons happen in the precision
> of sizetype.
I was trying to make minimal refactoring for fixing the negative step
issue.  Also I guess your SVE patches will rewrite this part entirely?
>
> The situation seems very close to RTL in the sense that the segment
> length has no inherent sign and we have to instead get the sign from
> the DR_STEP.  Unless we can change that of course...
>
>>
>> !       /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b.
>>
>> !          Case A:
>> !            check if the following condition is satisfied:
>>
>> !            DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
>> !
>> !            where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
>> !            SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
>> !            have to make a best estimation.  We can get the minimum value
>> !            of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
>> !            then either of the following two conditions can guarantee the
>> !            one above:
>> !
>> !            1: DIFF <= MIN_SEG_LEN_B
>> !            2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B
>> !               Because DIFF - SEGMENT_LENGTH_A is done in sizetype, we need
>> !               to take care of wrapping behavior in it.
>> !
>> !          Case B:
>> !            If the left segment does not extend beyond the start of the
>> !            right segment the new segment length is that of the right
>> !            plus the segment distance.
>> !
>> !          Note 1: Case A.2 and B combined together effectively merges every
>> !          dr_a1 & dr_b and dr_a2 & dr_b when SEGMENT_LENGTH_A is const.  We
>> !          test them separately for clarity, also because Case A never
>> !          introduces false alias, while Case B does.
>> !
>> !          Note 2: Above description is based on positive DR_STEP, we need to
>> !          take care of negative DR_STEP for wrapping behavior.  See PR80815
>> !          for more information.  */
>> !       if (neg_step)
>>           {
>> !           /* Case A.  */
>> !           if (diff <= min_seg_len_b
>> !               || (tree_fits_uhwi_p (dr_a1->seg_len)
>> !                   && (diff + tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b
>> !                       || diff < 0 - tree_to_uhwi (dr_a1->seg_len)))
>> !               /* Case B.  */
>> !               || (tree_fits_uhwi_p (dr_a1->seg_len)
>> !                   && diff > 0 - tree_to_uhwi (dr_a1->seg_len)))
>
> a2 is to the right of a1, and both segment lengths are conceptually
> negative, so I think this should be using dr_a2->seg_len instead of
> dr_a1->seg_len.  E.g. for A.2, A2's segment overlaps A1's if
>
>   diff < 0 - tree_to_uhwi (dr_a2->seg_len)
Yeah, I copied this code from !neg_step case, but forgot to change it
in conditions...  Fixed now.
>
> TBH, given that the comment has already explained why this reduces to:
>
>   (diff <= min_seg_len_b
>    || TREE_CODE (dr_a2(?)->seg_len) == INTEGER_CST)
>
> I think it'd better just to write that.  The clarity kind-of belongs in the
> comments instead.
Updated as you suggested.  Also refined comment a bit for this.

Bootstrap and test ongoing.

Thanks,
bin

[-- Attachment #2: 0003-negative-step-alias-check-20170517.txt --]
[-- Type: text/plain, Size: 8694 bytes --]

From 5142f79dc357900d8be869a9fbf488132a6a6db2 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 19 May 2017 18:46:14 +0100
Subject: [PATCH 3/6] negative-step-alias-check-20170517.txt

---
 gcc/testsuite/gcc.dg/vect/pr80815-1.c |  38 ++++++++++
 gcc/testsuite/gcc.dg/vect/pr80815-2.c |  46 +++++++++++++
 gcc/tree-data-ref.c                   | 126 +++++++++++++++++++++++-----------
 3 files changed, 169 insertions(+), 41 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/vect/pr80815-1.c
 create mode 100644 gcc/testsuite/gcc.dg/vect/pr80815-2.c

diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-1.c b/gcc/testsuite/gcc.dg/vect/pr80815-1.c
new file mode 100644
index 0000000..98c06c0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr80815-1.c
@@ -0,0 +1,38 @@
+/* { dg-require-effective-target vect_int } */
+
+#include "tree-vect.h"
+int arr[2048];
+
+__attribute__ ((noinline)) int
+foo (int *a, int *b)
+{
+  int i;
+  int *a1 = a;
+  int *a0 = a1 - 512;
+  for (i = 0; i < 500; i++)
+    {
+      *b = *a0 + *a1;
+      b++;
+      a0--;
+      a1--;
+    }
+  return 0;
+}
+
+int main (void)
+{
+  int *a = &arr[1027];
+  int *b = &arr[1024];
+
+  int i;
+  for (i = 0; i < 2048; i++)
+    arr[i] = i;
+
+  foo (a, b);
+
+  if (arr[1026] != 2053 || arr[1027] != 2054)
+    abort ();
+
+  return 0;
+}
+
diff --git a/gcc/testsuite/gcc.dg/vect/pr80815-2.c b/gcc/testsuite/gcc.dg/vect/pr80815-2.c
new file mode 100644
index 0000000..83557da
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/pr80815-2.c
@@ -0,0 +1,46 @@
+/* { dg-require-effective-target vect_int } */
+
+#include "tree-vect.h"
+int arr[2048];
+int res[100] = { 13198, 13224, 12735, 12760, 12270, 12294,
+		 11803, 11826, 11334, 11356, 10863, 10884,
+		 10390, 10410, 9915, 9934, 9438, 9456,
+		 8959, 8976, 8478, 8494, 7995, 8010,
+		 7510, 7524, 7023, 7036, 6534, 6546,
+		 6043, 6054, 5550, 5560, 5055, 5064,
+		 4558, 4566, 4059, 4066, 3558, 3564,
+		 3055, 3060, 2550, 2554, 2043, 0};
+
+__attribute__ ((noinline)) int
+foo (int *a, int *b)
+{
+  int i;
+  int *a1 = a;
+  int *a0 = a1 - 512;
+  for (i = 0; i < 50; i++)
+    {
+      *b = *a0 + *a1;
+      b--;
+      a0--;
+      a1--;
+    }
+  return 0;
+}
+
+int main (void)
+{
+  int *a = &arr[1024];
+  int *b = &arr[1022];
+
+  int i;
+  for (i = 0; i < 2048; i++)
+    arr[i] = i;
+
+  foo (a, b);
+
+  for (i = 973; i < 1020; i++)
+    if (arr[i] != res[i - 973])
+      abort ();
+
+  return 0;
+}
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index a5f8c1c..a014aea 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1259,6 +1259,16 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs,
 	      != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node))
 	    continue;
 
+	  bool neg_step
+	    = (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node) < 0);
+
+	  /* Require the same step for DR_A1 and DR_A2 if it's negative.  This
+	     simplifies diff computation between DR_A1 and DR_A2.  */
+	  if (neg_step
+	      && tree_int_cst_compare (DR_STEP (dr_a1->dr),
+				       DR_STEP (dr_a2->dr)) != 0)
+	    continue;
+
 	  /* Make sure dr_a1 starts left of dr_a2.  */
 	  if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
 	    std::swap (*dr_a1, *dr_a2);
@@ -1266,60 +1276,93 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs,
 	  bool do_remove = false;
 	  unsigned HOST_WIDE_INT diff
 	    = (tree_to_shwi (DR_INIT (dr_a2->dr))
-               - tree_to_shwi (DR_INIT (dr_a1->dr)));
+	       - tree_to_shwi (DR_INIT (dr_a1->dr)));
+	  tree new_seg_len;
+	  unsigned HOST_WIDE_INT min_seg_len_b;
 
-	  /* If the left segment does not extend beyond the start of the
-	     right segment the new segment length is that of the right
-	     plus the segment distance.  */
-	  if (tree_fits_uhwi_p (dr_a1->seg_len)
-	      && compare_tree_int (dr_a1->seg_len, diff) <= 0)
-	    {
-	      dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
-					   size_int (diff));
-	      do_remove = true;
-	    }
-	  /* Generally the new segment length is the maximum of the
-	     left segment size and the right segment size plus the distance.
-	     ???  We can also build tree MAX_EXPR here but it's not clear this
-	     is profitable.  */
-	  else if (tree_fits_uhwi_p (dr_a1->seg_len)
-		   && tree_fits_uhwi_p (dr_a2->seg_len))
+	  if (tree_fits_uhwi_p (dr_b1->seg_len))
 	    {
-	      unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
-	      unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
-	      dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
-	      do_remove = true;
+	      min_seg_len_b = tree_to_uhwi (dr_b1->seg_len);
+	      if (tree_int_cst_sign_bit (dr_b1->seg_len))
+		min_seg_len_b = 0 - min_seg_len_b;
 	    }
-	  /* Now we check if the following condition is satisfied:
+	  else
+	    min_seg_len_b = factor;
 
-	     DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+	  /* Now we try to merge alias check dr_a1 & dr_b and dr_a2 & dr_b.
 
-	     where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
-	     SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
-	     have to make a best estimation.  We can get the minimum value
-	     of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
-	     then either of the following two conditions can guarantee the
-	     one above:
+	     Case A:
+	       check if the following condition is satisfied:
 
-	     1: DIFF <= MIN_SEG_LEN_B
-	     2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
-	  else
+	       DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+
+	       where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
+	       SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
+	       have to make a best estimation.  We can get the minimum value
+	       of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
+	       then either of the following two conditions can guarantee the
+	       one above:
+
+	       1: DIFF <= MIN_SEG_LEN_B
+	       2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B
+		  Because DIFF - SEGMENT_LENGTH_A is done in sizetype, we need
+		  to take care of wrapping behavior in it.
+
+	     Case B:
+	       If the left segment does not extend beyond the start of the
+	       right segment the new segment length is that of the right
+	       plus the segment distance.  The condition is like:
+
+	       DIFF >= SEGMENT_LENGTH_A   ;SEGMENT_LENGTH_A is a constant.
+
+	     Note 1: Case A.2 and B combined together effectively merges every
+	     dr_a1 & dr_b and dr_a2 & dr_b when SEGMENT_LENGTH_A is const.
+
+	     Note 2: Above description is based on positive DR_STEP, we need to
+	     take care of negative DR_STEP for wrapping behavior.  See PR80815
+	     for more information.  */
+	  if (neg_step)
 	    {
-	      unsigned HOST_WIDE_INT min_seg_len_b
-		= (tree_fits_uhwi_p (dr_b1->seg_len)
-		   ? tree_to_uhwi (dr_b1->seg_len)
-		   : factor);
+	      /* Case A.1.  */
+	      if (diff <= min_seg_len_b
+		  /* Case A.2 and B combined.  */
+		  || (tree_fits_uhwi_p (dr_a2->seg_len)))
+		{
+		  if (tree_fits_uhwi_p (dr_a1->seg_len)
+		      && tree_fits_uhwi_p (dr_a2->seg_len))
+		    new_seg_len
+		      = size_int (MIN (tree_to_uhwi (dr_a1->seg_len),
+				       tree_to_uhwi (dr_a2->seg_len) - diff));
+		  else
+		    new_seg_len = size_binop (MINUS_EXPR,
+					      dr_a2->seg_len, size_int (diff));
 
+		  dr_a2->seg_len = new_seg_len;
+		  do_remove = true;
+		}
+	    }
+	  else
+	    {
+	      /* Case A.1.  */
 	      if (diff <= min_seg_len_b
-		  || (tree_fits_uhwi_p (dr_a1->seg_len)
-		      && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
+		  /* Case A.2 and B combined.  */
+		  || (tree_fits_uhwi_p (dr_a1->seg_len)))
 		{
-		  dr_a1->seg_len = size_binop (PLUS_EXPR,
-					       dr_a2->seg_len, size_int (diff));
+		  if (tree_fits_uhwi_p (dr_a1->seg_len)
+		      && tree_fits_uhwi_p (dr_a2->seg_len))
+		    new_seg_len
+		      = size_int (MAX (tree_to_uhwi (dr_a1->seg_len),
+				       diff + tree_to_uhwi (dr_a2->seg_len)));
+		  else
+		    new_seg_len
+		      = size_binop (PLUS_EXPR, dr_a2->seg_len, size_int (diff));
+
+		  dr_a1->seg_len = new_seg_len;
 		  do_remove = true;
 		}
 	    }
 
+
 	  if (do_remove)
 	    {
 	      if (dump_enabled_p ())
@@ -1334,7 +1377,8 @@ prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs,
 		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
 		  dump_printf (MSG_NOTE, "\n");
 		}
-	      alias_pairs->ordered_remove (i--);
+	      alias_pairs->ordered_remove (neg_step ? i - 1 : i);
+	      i--;
 	    }
 	}
     }
-- 
1.9.1


  reply	other threads:[~2017-05-24 10:17 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-05-23 16:23 Bin Cheng
2017-05-23 17:56 ` Richard Sandiford
2017-05-24 10:54   ` Bin.Cheng [this message]
2017-05-24 10:55     ` Richard Sandiford
2017-05-25 15:16       ` Bin.Cheng
2017-05-26 11:43         ` Richard Biener
2017-05-26 12:01           ` Bin.Cheng
2017-05-26 12:31             ` Richard Biener

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAHFci2_EMsCfRvriHKb2BPeJaJVWX9Aoy8Co-kFh2N8=rB8zvQ@mail.gmail.com' \
    --to=amker.cheng@gmail.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=richard.sandiford@linaro.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).