public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: "Bin.Cheng" <amker.cheng@gmail.com>
To: "Bin.Cheng" <amker.cheng@gmail.com>,
		"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: Thu, 25 May 2017 15:16:00 -0000	[thread overview]
Message-ID: <CAHFci29-ab_Ov8sbx+OHdoQRRO7Q5QbszbJ1a+7RzdNojksY4g@mail.gmail.com> (raw)
In-Reply-To: <87a862zfrt.fsf@linaro.org>

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

On Wed, May 24, 2017 at 11:54 AM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> "Bin.Cheng" <amker.cheng@gmail.com> writes:
>> 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.
>
> What kind of adjustment would be needed?  Could you give an example?
I handled negative step in updated patch by adjusting diff according
to access size of references.

>
>> 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).
>
> But I think it would a problem even for "normal" 32-bit and 16-bit
> targets, because you're doing uhwi (i.e. 64-bit) negation on things that
> come from 32-bit and 16-bit unsigned values.  E.g. a segment length of
> -32 on a 32-bit target would be 0xffffffe0.  If you read that as a uhwi
> and negate it, you get 0xffffffff00000020 rather than 32.
>
> Using wide_ints would avoid that.  I don't think the existing code
> needed it (because the existing code didn't handle negative steps
> properly at all).
Right, patch updated using wide_int to compare diff and compute merged
segment length.
Bootstrap and test on x86_64 and AArch64.

Thanks,
bin
>
>>> 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?
>
> Not sure TBH :-)  I'll have to see how it works out when I merge it in.
>
> Thanks,
> Richard

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

From a31c45912c6b3621f926106a734087837e8e901e 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-20170520.txt

---
 gcc/testsuite/gcc.dg/vect/pr80815-1.c |  38 +++++++++
 gcc/testsuite/gcc.dg/vect/pr80815-2.c |  46 +++++++++++
 gcc/tree-data-ref.c                   | 143 +++++++++++++++++++++++-----------
 3 files changed, 182 insertions(+), 45 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..1a28000 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1259,63 +1259,115 @@ 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);
+
+	  /* We need to compute merged segment length at compilation time for
+	     dr_a1 and dr_a2, which is impossible if either one has non-const
+	     segment length.  */
+	  if ((!tree_fits_uhwi_p (dr_a1->seg_len)
+	       || !tree_fits_uhwi_p (dr_a2->seg_len))
+	      && 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);
 
 	  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))
+	  wide_int diff = wi::sub (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr));
+	  wide_int min_seg_len_b;
+	  tree new_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 = dr_b1->seg_len;
+	      if (tree_int_cst_sign_bit (dr_b1->seg_len))
+		min_seg_len_b = wi::neg (min_seg_len_b);
 	    }
-	  /* Now we check if the following condition is satisfied:
+	  else
+	    min_seg_len_b = wi::uhwi (factor, TYPE_PRECISION (sizetype));
+
+	  /* 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.
 
-	     DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+	     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:
 
-	     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:
+	       DIFF >= SEGMENT_LENGTH_A   ;SEGMENT_LENGTH_A is a constant.
 
-	     1: DIFF <= MIN_SEG_LEN_B
-	     2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
+	     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)
+	    {
+	      /* Adjust diff according to access size of both references.  */
+	      tree size_a1 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a1->dr)));
+	      tree size_a2 = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a2->dr)));
+	      diff = wi::add (diff, wi::sub (size_a2, size_a1));
+	      /* Case A.1.  */
+	      if (wi::leu_p (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
+		      = wide_int_to_tree (sizetype,
+					  wi::umin (wi::sub (dr_a1->seg_len,
+							     diff),
+						    dr_a2->seg_len));
+		  else
+		    new_seg_len
+		      = size_binop (MINUS_EXPR, dr_a2->seg_len,
+				    wide_int_to_tree (sizetype, diff));
+
+		  dr_a2->seg_len = new_seg_len;
+		  do_remove = true;
+		}
+	    }
 	  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))
+	      /* Case A.1.  */
+	      if (wi::leu_p (diff, 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
+		      = wide_int_to_tree (sizetype,
+					  wi::umax (wi::add (dr_a2->seg_len,
+							     diff),
+						    dr_a1->seg_len));
+		  else
+		    new_seg_len
+		      = size_binop (PLUS_EXPR, dr_a2->seg_len,
+				    wide_int_to_tree (sizetype, diff));
+
+		  dr_a1->seg_len = new_seg_len;
 		  do_remove = true;
 		}
 	    }
@@ -1334,7 +1386,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-25 15:15 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
2017-05-24 10:55     ` Richard Sandiford
2017-05-25 15:16       ` Bin.Cheng [this message]
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=CAHFci29-ab_Ov8sbx+OHdoQRRO7Q5QbszbJ1a+7RzdNojksY4g@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).