Improve get_ref_base_and_extent with range-info

Message ID alpine.LSU.2.20.1805171408330.24704@zhemvz.fhfr.qr
State New
Headers show
Series
  • Improve get_ref_base_and_extent with range-info
Related show

Commit Message

Richard Biener May 17, 2018, 12:13 p.m.
The following makes use of range-info to improve the basic building
block of the alias-oracle so we can tell that in

  a[0] = 1;
  for (int i = 5; i < 17; ++i)
    a[i] = i;
  a[0] = 2;

the ao_ref for a[i] does not alias the a[0] acceses.  Given range-info
is not always going to improve things over knowledge gained from
the type size of the access I'm only improving it over information
gathered from the size.

For the above this allows us to DSE the first store with another
DSE improvement I'm testing separately.

Bootstrap & regtest in progress on x86_64-unknown-linux-gnu.

Richard.

2018-05-17  Richard Biener  <rguenther@suse.de>

	* tree-dfa.c (get_ref_base_and_extent): Use range-info to refine
	results when processing array refs with variable index.

	* gcc.dg/tree-ssa/ssa-dse-35.c: New testcase.

Comments

Richard Biener May 18, 2018, 10:10 a.m. | #1
On Thu, 17 May 2018, Richard Biener wrote:

> 
> The following makes use of range-info to improve the basic building
> block of the alias-oracle so we can tell that in
> 
>   a[0] = 1;
>   for (int i = 5; i < 17; ++i)
>     a[i] = i;
>   a[0] = 2;
> 
> the ao_ref for a[i] does not alias the a[0] acceses.  Given range-info
> is not always going to improve things over knowledge gained from
> the type size of the access I'm only improving it over information
> gathered from the size.
> 
> For the above this allows us to DSE the first store with another
> DSE improvement I'm testing separately.
> 
> Bootstrap & regtest in progress on x86_64-unknown-linux-gnu.

I've committed the following sligtly safer with respect to
flexarray - I'll improve it as followup but need to refactor things
a bit for that.  I've also adjusted graphite testcases producing
dead data.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.

Richard.

2018-05-18  Richard Biener  <rguenther@suse.de>

	* tree-dfa.c (get_ref_base_and_extent): Use range-info to refine
	results when processing array refs with variable index.

	* gcc.dg/tree-ssa/ssa-dse-35.c: New testcase.
	* gcc.dg/graphite/scop-10.c: Adjust to avoid dead code.
	* gcc.dg/graphite/scop-6.c: Likewise.
	* gcc.dg/graphite/scop-7.c: Likewise.
	* gcc.dg/graphite/scop-8.c: Likewise.
	* gcc.dg/graphite/scop-9.c: Likewise.

diff --git a/gcc/testsuite/gcc.dg/graphite/scop-10.c b/gcc/testsuite/gcc.dg/graphite/scop-10.c
index 20d53510b4e..d04183072f3 100644
--- a/gcc/testsuite/gcc.dg/graphite/scop-10.c
+++ b/gcc/testsuite/gcc.dg/graphite/scop-10.c
@@ -22,7 +22,7 @@ int toto()
         b[i+k] = b[i+k-5] + 2;
     }
 
-  return a[3][5] + b[1];
+  return a[3][5] + b[2];
 }
 
 /* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */
diff --git a/gcc/testsuite/gcc.dg/graphite/scop-6.c b/gcc/testsuite/gcc.dg/graphite/scop-6.c
index 1da486a2ddf..9bc1d9f4ccd 100644
--- a/gcc/testsuite/gcc.dg/graphite/scop-6.c
+++ b/gcc/testsuite/gcc.dg/graphite/scop-6.c
@@ -23,7 +23,7 @@ int toto()
         b[i+k] = b[i+k-5] + 2;
     }
 
-  return a[3][5] + b[1];
+  return a[3][5] + b[2];
 }
 
 /* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */
diff --git a/gcc/testsuite/gcc.dg/graphite/scop-7.c b/gcc/testsuite/gcc.dg/graphite/scop-7.c
index 2f0a50470e9..f4f3093fcaf 100644
--- a/gcc/testsuite/gcc.dg/graphite/scop-7.c
+++ b/gcc/testsuite/gcc.dg/graphite/scop-7.c
@@ -23,7 +23,7 @@ int toto()
         b[i+k] = b[i+k-5] + 2;
     }
 
-  return a[3][5] + b[1];
+  return a[3][5] + b[2];
 }
 
 /* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */
diff --git a/gcc/testsuite/gcc.dg/graphite/scop-8.c b/gcc/testsuite/gcc.dg/graphite/scop-8.c
index 3ceb5d874d6..b06265108c6 100644
--- a/gcc/testsuite/gcc.dg/graphite/scop-8.c
+++ b/gcc/testsuite/gcc.dg/graphite/scop-8.c
@@ -23,7 +23,7 @@ int toto()
         b[i+k] = b[i+k-5] + 2;
     }
 
-  return a[3][5] + b[1];
+  return a[3][5] + b[2];
 }
 
 /* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */
diff --git a/gcc/testsuite/gcc.dg/graphite/scop-9.c b/gcc/testsuite/gcc.dg/graphite/scop-9.c
index 93888728b0d..b19291be2f8 100644
--- a/gcc/testsuite/gcc.dg/graphite/scop-9.c
+++ b/gcc/testsuite/gcc.dg/graphite/scop-9.c
@@ -18,7 +18,7 @@ int toto()
         b[i+k] = b[i+k-5] + 2;
     }
 
-  return a[3][5] + b[1];
+  return a[3][5] + b[2];
 }
 
 /* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-35.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-35.c
new file mode 100644
index 00000000000..1f21670406f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-35.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dse1-details" } */
+
+int a[256];
+void foo (void)
+{
+  a[0] = 1;
+  for (int i = 5; i < 17; ++i)
+    a[i] = i;
+  a[0] = 2;
+}
+
+/* { dg-final { scan-tree-dump-times "Deleted dead store" 1 "dse1" } } */
Index: gcc/tree-dfa.c
===================================================================
--- gcc/tree-dfa.c	(revision 260322)
+++ gcc/tree-dfa.c	(working copy)
@@ -529,6 +529,49 @@ get_ref_base_and_extent (tree exp, poly_
 		/* Remember that we have seen an array ref with a variable
 		   index.  */
 		seen_variable_array_ref = true;
+
+		wide_int min, max;
+		if (TREE_CODE (index) == SSA_NAME
+		    && (low_bound = array_ref_low_bound (exp),
+			poly_int_tree_p (low_bound))
+		    && (unit_size = array_ref_element_size (exp),
+			TREE_CODE (unit_size) == INTEGER_CST)
+		    && get_range_info (index, &min, &max) == VR_RANGE)
+		  {
+		    poly_offset_int lbound = wi::to_poly_offset (low_bound);
+		    /* Try to constrain maxsize with range information.  */
+		    offset_int omax
+		      = offset_int::from (max, TYPE_SIGN (TREE_TYPE (index)));
+		    if (known_lt (lbound, omax))
+		      {
+			poly_offset_int rmaxsize;
+			rmaxsize = (omax - lbound + 1)
+			    * wi::to_offset (unit_size) << LOG2_BITS_PER_UNIT;
+			if (!known_size_p (maxsize)
+			    || known_lt (rmaxsize, maxsize))
+			  {
+			    /* If we know an upper bound below the declared
+			       one this is no longer variable.  */
+			    if (known_size_p (maxsize))
+			      seen_variable_array_ref = false;
+			    maxsize = rmaxsize;
+			  }
+		      }
+		    /* Try to adjust bit_offset with range information.  */
+		    offset_int omin
+		      = offset_int::from (min, TYPE_SIGN (TREE_TYPE (index)));
+		    if (known_le (lbound, omin))
+		      {
+			poly_offset_int woffset
+			  = wi::sext (omin - lbound,
+				      TYPE_PRECISION (TREE_TYPE (index)));
+			woffset *= wi::to_offset (unit_size);
+			woffset <<= LOG2_BITS_PER_UNIT;
+			bit_offset += woffset;
+			if (known_size_p (maxsize))
+			  maxsize -= woffset;
+		      }
+		  }
 	      }
 	  }
 	  break;

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-35.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-35.c
new file mode 100644
index 00000000000..1f21670406f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-35.c
@@ -0,0 +1,13 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dse1-details" } */
+
+int a[256];
+void foo (void)
+{
+  a[0] = 1;
+  for (int i = 5; i < 17; ++i)
+    a[i] = i;
+  a[0] = 2;
+}
+
+/* { dg-final { scan-tree-dump-times "Deleted dead store" 1 "dse1" } } */
diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c
index a121b880bb0..993ac49554d 100644
--- a/gcc/tree-dfa.c
+++ b/gcc/tree-dfa.c
@@ -529,6 +529,48 @@  get_ref_base_and_extent (tree exp, poly_int64_pod *poffset,
 		/* Remember that we have seen an array ref with a variable
 		   index.  */
 		seen_variable_array_ref = true;
+
+		wide_int min, max;
+		if (TREE_CODE (index) == SSA_NAME
+		    && (low_bound = array_ref_low_bound (exp),
+			poly_int_tree_p (low_bound))
+		    && (unit_size = array_ref_element_size (exp),
+			TREE_CODE (unit_size) == INTEGER_CST)
+		    && get_range_info (index, &min, &max) == VR_RANGE)
+		  {
+		    poly_offset_int lbound = wi::to_poly_offset (low_bound);
+		    /* Try to constrain maxsize with range information.  */
+		    offset_int omax
+		      = offset_int::from (max, TYPE_SIGN (TREE_TYPE (index)));
+		    if (known_lt (lbound, omax))
+		      {
+			poly_offset_int rmaxsize;
+			rmaxsize = (omax - lbound + 1)
+			    * wi::to_offset (unit_size) << LOG2_BITS_PER_UNIT;
+			if (!known_size_p (maxsize)
+			    || known_lt (rmaxsize, maxsize))
+			  {
+			    maxsize = rmaxsize;
+			    /* Given we know an upper bound this is no
+			       longer variable.  */
+			    seen_variable_array_ref = false;
+			  }
+		      }
+		    /* Try to adjust bit_offset with range information.  */
+		    offset_int omin
+		      = offset_int::from (min, TYPE_SIGN (TREE_TYPE (index)));
+		    if (known_le (lbound, omin))
+		      {
+			poly_offset_int woffset
+			  = wi::sext (omin - lbound,
+				      TYPE_PRECISION (TREE_TYPE (index)));
+			woffset *= wi::to_offset (unit_size);
+			woffset <<= LOG2_BITS_PER_UNIT;
+			bit_offset += woffset;
+			if (known_size_p (maxsize))
+			  maxsize -= woffset;
+		      }
+		  }
 	      }
 	  }
 	  break;