Fix PR tree-optimization/17672 Fix PR tree-optimization/18168

2004-10-16  Daniel Berlin  <dberlin@dberlin.org>

	Fix PR tree-optimization/17672
	Fix PR tree-optimization/18168

	* lambda-code.c (lambda_lattice_compute_base): Fix reversed
	assert test.
	(gcc_tree_to_linear_expression): Add extra to existing constant.
	(depth_of_nest): Factor out function used in various places.
	(gcc_loop_to_lambda_loop): Clean up code a little bit. No
	functional changes.
	(find_induction_var_from_exit_cond): Stop guessing, and just
	get the right answer :).
	(gcc_loopnest_to_lambda_loopnest): Remove useless pre-allocation.
	Print out message about result of attempt to create perfect nest.
	(lbv_to_gcc_expression): Add type argument, use it to do math
	and induction variable creation.
	(lle_to_gcc_expression): Ditto.
	(lambda_loopnest_to_gcc_loopnest): Create new iv with same type as
	oldiv. Pass type argument to lle_to_gcc_expression and
	lbv_to_gcc_expression.
	Reset number of iterations after transformation.
	(perfect_nestify): Remove useless pre-allocation, and cleanup
	a small amount.

	* tree-data-ref.c (build_classic_dist_vector): Return false for
	dependences completely outside of the loop nest we asked about.
	(build_classic_dir_vector): Ditto.
	(compute_data_dependences_for_loop): Only add dependence relations
	inside the loop we asked about.

	* tree-loop-linear.c (linear_transform_loops): Use DDR_SIZE_VECT.
	Compute immediate uses.

	* tree-optimize.c: Move linear_transform_loops to before ivcanon.

From-SVN: r89945

5 files changed, 101 insertions, 0 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c
new file mode 100644
index 0000000..bbeef87
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-1.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+  int i, j;
+  double sum = 0.0;
+  /* This loop should be converted to a perfect nest and
+     interchanged. */
+  for (i = 0; i < N; i++)
+    {
+      for (j = 0; j < N; j++)
+	sum = sum + u[i + 1335 * j];
+      
+      u[1336 * i] *= 2;
+    }
+  *res = sum + N;
+}
+/* { dg-final { scan-tree-dump-times "converted loop nest to perfect
+   loop nest" 1 "ltrans"} } */ 
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c
new file mode 100644
index 0000000..7ab3e6c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-2.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+  unsigned int i, j;
+  double sum = 0;
+  
+  /* This loop should be converted to a perfect nest and
+     interchanged.  */
+  for (i = 0; i < N; i++)
+    {
+      for (j = 0; j < N; j++)
+	{
+	  sum = sum + u[i + 1335 * j];
+	  if (j == N - 1)
+	    u[1336 * i] *= 2;
+	}
+    }
+  *res = sum + N;
+}
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} {
+   xfail *-*-*} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c
new file mode 100644
index 0000000..81c347c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-3.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+  unsigned int i, j;
+  double sum = 0;
+      for (i = 0; i < N; i++)
+	{
+	  for (j = 0; j < N; j++)
+	    {
+	      sum = sum + u[i + 1335 * j];
+	    }
+	}
+      *res = sum + N;
+}
+
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c
new file mode 100644
index 0000000..5f43da1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-4.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O20 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+double u[1782225];
+int foo(int N, int *res)
+{
+  int i, j;
+  double sum = 0;
+  for (i = 0; i < N; i++)	
+    for (j = 0; j < N; j++)
+      sum = sum + u[i + 1335 * j];
+  
+  for (i = 0; i < N; i++)
+    u[1336 * i] *= 2;
+  *res = sum + N;
+}
+
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c
new file mode 100644
index 0000000..43a2011
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ltrans-5.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+typedef struct rtx_
+{
+} *rtx;
+static rtx regno_save_mem[53][16 / 4 + 1];
+extern set_mem_alias_set (rtx, rtx);
+int main(void)
+{
+  int i, j;
+  for (i = 0; i < 53; i++)
+    for (j = (16 / (0 ? 8 : 4)); j > 0; j--)
+      if (regno_save_mem[i][j] != 0)
+        set_mem_alias_set (regno_save_mem[i][j], 0);
+}
+
+/* { dg-final { scan-tree-dump-times "Linear expression:  constant: 1   invariants:   denominator: 1" 1 "ltrans" } } */
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */