public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Bin Cheng <Bin.Cheng@arm.com>
To: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
Cc: nd <nd@arm.com>
Subject: [PATCH GCC][3/6]Fix PR80815 by handling negative DR_STEPs in runtime alias check
Date: Tue, 23 May 2017 16:23:00 -0000	[thread overview]
Message-ID: <VI1PR0802MB2176A0FA67956247E4503D5DE7F90@VI1PR0802MB2176.eurprd08.prod.outlook.com> (raw)

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


             reply	other threads:[~2017-05-23 16:23 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-05-23 16:23 Bin Cheng [this message]
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

Reply instructions:

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

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

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

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

  git send-email \
    --in-reply-to=VI1PR0802MB2176A0FA67956247E4503D5DE7F90@VI1PR0802MB2176.eurprd08.prod.outlook.com \
    --to=bin.cheng@arm.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=nd@arm.com \
    /path/to/YOUR_REPLY

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

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