public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
@ 2017-05-23 16:23 Bin Cheng
  2017-05-23 17:56 ` Richard Sandiford
  0 siblings, 1 reply; 8+ messages in thread
From: Bin Cheng @ 2017-05-23 16:23 UTC (permalink / raw)
  To: gcc-patches; +Cc: nd

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

Hi,
This patch fixes PR80815 in which negative DR_STEP is mis-handled.  It does below:
  1) Reorder three cases in which we merge alias checks, in order like:
       old_case_A   ->  new_case_B
       old_case_B   ->  new_case_C (and removed as described in 3))
       old_case_C   ->  new_case_A
     This is because new_case_1 is accurate check that doesn't introduce false alias,
     while the other two does.
  2) Explicitly comment that Case A and B combined together can merge all dr_a1&dr_b and
     dr_a2&dr_b pairs if SEGMENT_LEN_A is constant.  We still keep Case A/B separately
     for clarity, also because Case A doesn't introduces false alias, while B does.
  3) Remove the old_case_C:
       	  /* 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))
     This check is actually covered by A and B.
  4) Handle negative DR_STEPs explicitly.
  5) Add two tests illustrating wrong alias checking issue.

Bootstrap and test on x86_64 and AArch64, is it OK?

BTW, I tried to keep the change as minimal as possible, but ended up with quite
amount refactoring because the old cases are somehow duplicated/complicated,
and not fit to negative DR_STEPs handling.

Thanks,
bin
2017-05-22  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/80815
	* tree-data-ref.c (prune_runtime_alias_test_list): Simplify condition
	for merging runtime alias checks.  Handle negative DR_STEPs.

gcc/testsuite/ChangeLog
2017-05-22  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/80815
	* gcc.dg/vect/pr80815-1.c: New test.
	* gcc.dg/vect/pr80815-2.c: New test.

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

From af1dda073f8bd1a371cd1207fcaf467be0dc1106 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-20170516.txt

---
 gcc/testsuite/gcc.dg/vect/pr80815-1.c |  38 ++++++++++
 gcc/testsuite/gcc.dg/vect/pr80815-2.c |  46 ++++++++++++
 gcc/tree-data-ref.c                   | 131 +++++++++++++++++++++++-----------
 3 files changed, 175 insertions(+), 40 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..f0799d9 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1259,6 +1259,15 @@ 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);
+
+	  /* 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;
+
 	  /* 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 +1275,101 @@ 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)
+	  if (tree_fits_uhwi_p (dr_b1->seg_len))
 	    {
-	      dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
-					   size_int (diff));
-	      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;
 	    }
-	  /* 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:
+	  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.
+
+	     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)
 	    {
-	      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.  */
+	      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)))
+		{
+		  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.  */
 	      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 - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b
+			  || diff < tree_to_uhwi (dr_a1->seg_len)))
+		  /* Case B.  */
+		  || (tree_fits_uhwi_p (dr_a1->seg_len)
+		      && diff > tree_to_uhwi (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 +1384,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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
  2017-05-23 16:23 [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check Bin Cheng
@ 2017-05-23 17:56 ` Richard Sandiford
  2017-05-24 10:54   ` Bin.Cheng
  0 siblings, 1 reply; 8+ messages in thread
From: Richard Sandiford @ 2017-05-23 17:56 UTC (permalink / raw)
  To: Bin Cheng; +Cc: gcc-patches, nd

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?

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?]

>   	  /* 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
instead, so that all arithmetic and comparisons happen in the precision
of sizetype.

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)

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.

> ! 		{
> ! 		  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.  */
>   	      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 < tree_to_uhwi (dr_a1->seg_len)))
> ! 		  /* Case B.  */
> ! 		  || (tree_fits_uhwi_p (dr_a1->seg_len)
> ! 		      && diff > tree_to_uhwi (dr_a1->seg_len)))
>   		{
> ! 		  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,1340 ****
>   		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
>   		  dump_printf (MSG_NOTE, "\n");
>   		}
> ! 	      alias_pairs->ordered_remove (i--);
>   	    }
>   	}
>       }
> - - 
> --- 1384,1391 ----
>   		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
>   		  dump_printf (MSG_NOTE, "\n");
>   		}
> ! 	      alias_pairs->ordered_remove (neg_step ? i - 1 : i);
> ! 	      i--;
>   	    }
>   	}
>       }

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
  2017-05-23 17:56 ` Richard Sandiford
@ 2017-05-24 10:54   ` Bin.Cheng
  2017-05-24 10:55     ` Richard Sandiford
  0 siblings, 1 reply; 8+ messages in thread
From: Bin.Cheng @ 2017-05-24 10:54 UTC (permalink / raw)
  To: gcc-patches, Richard Sandiford

[-- 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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
  2017-05-24 10:54   ` Bin.Cheng
@ 2017-05-24 10:55     ` Richard Sandiford
  2017-05-25 15:16       ` Bin.Cheng
  0 siblings, 1 reply; 8+ messages in thread
From: Richard Sandiford @ 2017-05-24 10:55 UTC (permalink / raw)
  To: Bin.Cheng; +Cc: gcc-patches

"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?

> 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).

>> 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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
  2017-05-24 10:55     ` Richard Sandiford
@ 2017-05-25 15:16       ` Bin.Cheng
  2017-05-26 11:43         ` Richard Biener
  0 siblings, 1 reply; 8+ messages in thread
From: Bin.Cheng @ 2017-05-25 15:16 UTC (permalink / raw)
  To: Bin.Cheng, gcc-patches, Richard Sandiford

[-- 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


^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
  2017-05-25 15:16       ` Bin.Cheng
@ 2017-05-26 11:43         ` Richard Biener
  2017-05-26 12:01           ` Bin.Cheng
  0 siblings, 1 reply; 8+ messages in thread
From: Richard Biener @ 2017-05-26 11:43 UTC (permalink / raw)
  To: Bin.Cheng; +Cc: gcc-patches, Richard Sandiford

On Thu, May 25, 2017 at 5:15 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> 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.

It's quite hard to follow.  Isn't it more correct to always extend seg-len
by the access size?  And only consider neg_step when deciding which
pair to keep/extend (which DR_BASE_ADDRESS is eventually used)?

>>
>>> 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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
  2017-05-26 11:43         ` Richard Biener
@ 2017-05-26 12:01           ` Bin.Cheng
  2017-05-26 12:31             ` Richard Biener
  0 siblings, 1 reply; 8+ messages in thread
From: Bin.Cheng @ 2017-05-26 12:01 UTC (permalink / raw)
  To: Richard Biener; +Cc: gcc-patches, Richard Sandiford

On Fri, May 26, 2017 at 12:39 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, May 25, 2017 at 5:15 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> 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.
>
> It's quite hard to follow.  Isn't it more correct to always extend seg-len
Extending seg-len unconditionally by access size is more conservative
and safer, but I tried to keep alias pair merging precise by not using
unnecessary approximation.  Using approximation could be simpler in
terms of LoC, but it also causes confusion for others to understand
why/when we are merging.

> by the access size?  And only consider neg_step when deciding which
> pair to keep/extend (which DR_BASE_ADDRESS is eventually used)?
Things like: while pair to keep/extend; how long seg_len should be
extended; the condition when pairs should be considered for merging;
they are all depends on neg_step or not.  It's really hard to abstract
code for pos_step and neg_step cases, so I took the other way around,
simply separate code according to step's sign.  I think the code is
more straightforward, and easier for further changes in this way.

Thanks,
bin
>
>>>
>>>> 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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
  2017-05-26 12:01           ` Bin.Cheng
@ 2017-05-26 12:31             ` Richard Biener
  0 siblings, 0 replies; 8+ messages in thread
From: Richard Biener @ 2017-05-26 12:31 UTC (permalink / raw)
  To: Bin.Cheng; +Cc: gcc-patches, Richard Sandiford

On Fri, May 26, 2017 at 1:59 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Fri, May 26, 2017 at 12:39 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Thu, May 25, 2017 at 5:15 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> 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.
>>
>> It's quite hard to follow.  Isn't it more correct to always extend seg-len
> Extending seg-len unconditionally by access size is more conservative
> and safer, but I tried to keep alias pair merging precise by not using
> unnecessary approximation.  Using approximation could be simpler in
> terms of LoC, but it also causes confusion for others to understand
> why/when we are merging.
>
>> by the access size?  And only consider neg_step when deciding which
>> pair to keep/extend (which DR_BASE_ADDRESS is eventually used)?
> Things like: while pair to keep/extend; how long seg_len should be
> extended; the condition when pairs should be considered for merging;
> they are all depends on neg_step or not.  It's really hard to abstract
> code for pos_step and neg_step cases, so I took the other way around,
> simply separate code according to step's sign.  I think the code is
> more straightforward, and easier for further changes in this way.

Ok, I'll take your word for it ;)

Patch is ok.

Thanks,
Richard.

> Thanks,
> bin
>>
>>>>
>>>>> 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

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2017-05-26 12:28 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-05-23 16:23 [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check 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
2017-05-26 11:43         ` Richard Biener
2017-05-26 12:01           ` Bin.Cheng
2017-05-26 12:31             ` Richard Biener

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).