Remove the lambda framework and make -ftree-loop-linear an alias of -floop-interchange.

2011-01-17  Sebastian Pop  <sebastian.pop@amd.com>

toplev/
	* MAINTAINERS (linear loop transforms): Removed.

toplev/gcc/
	* Makefile.in (LAMBDA_H): Removed.
	(TREE_DATA_REF_H): Remove dependence on LAMBDA_H.
	(OBJS-common): Remove dependence on lambda-code.o, lambda-mat.o,
	lambda-trans.o, and tree-loop-linear.o.
	(lto-symtab.o): Remove dependence on LAMBDA_H.
	(tree-loop-linear.o): Remove rule.
	(lambda-mat.o): Same.
	(lambda-trans.o): Same.
	(lambda-code.o): Same.
	(tree-vect-loop.o): Add missing dependence on TREE_DATA_REF_H.
	(tree-vect-slp.o): Same.
	* hwint.h (gcd): Moved here.
	(least_common_multiple): Same.
	* lambda-code.c: Removed.
	* lambda-mat.c: Removed.
	* lambda-trans.c: Removed.
	* lambda.h: Removed.
	* tree-loop-linear.c: Removed.
	* lto-symtab.c: Do not include lambda.h.
	* omega.c (gcd): Removed.
	* passes.c (init_optimization_passes): Remove pass_linear_transform.
	* tree-data-ref.c (print_lambda_vector): Moved here.
	(lambda_vector_copy): Same.
	(lambda_matrix_copy): Same.
	(lambda_matrix_id): Same.
	(lambda_vector_first_nz): Same.
	(lambda_matrix_row_add): Same.
	(lambda_matrix_row_exchange): Same.
	(lambda_vector_mult_const): Same.
	(lambda_vector_negate): Same.
	(lambda_matrix_row_negate): Same.
	(lambda_vector_equal): Same.
	(lambda_matrix_right_hermite): Same.
	* tree-data-ref.h: Do not include lambda.h.
	(lambda_vector): Moved here.
	(lambda_matrix): Same.
	(dependence_level): Same.
	(lambda_transform_legal_p): Removed declaration.
	(lambda_collect_parameters): Same.
	(lambda_compute_access_matrices): Same.
	(lambda_vector_gcd): Same.
	(lambda_vector_new): Same.
	(lambda_vector_clear): Same.
	(lambda_vector_lexico_pos): Same.
	(lambda_vector_zerop): Same.
	(lambda_matrix_new): Same.
	* tree-flow.h (least_common_multiple): Removed declaration.
	* tree-parloops.c (lambda_trans_matrix): Moved here.
	(LTM_MATRIX): Same.
	(LTM_ROWSIZE): Same.
	(LTM_COLSIZE): Same.
	(LTM_DENOMINATOR): Same.
	(lambda_trans_matrix_new): Same.
	(lambda_matrix_vector_mult): Same.
	(lambda_transform_legal_p): Same.
	* tree-pass.h (pass_linear_transform): Removed declaration.
	* tree-ssa-loop.c (tree_linear_transform): Removed.
	(gate_tree_linear_transform): Removed.
	(pass_linear_transform): Removed.
	(gate_graphite_transforms): Make flag_tree_loop_linear an alias of
	flag_loop_interchange.

toplev/gcc/testsuite/
	* gfortran.dg/graphite/interchange-4.f: New.
	* gfortran.dg/graphite/interchange-5.f: New.

	* gcc.dg/tree-ssa/ltrans-1.c: Removed.
	* gcc.dg/tree-ssa/ltrans-2.c: Removed.
	* gcc.dg/tree-ssa/ltrans-3.c: Removed.
	* gcc.dg/tree-ssa/ltrans-4.c: Removed.
	* gcc.dg/tree-ssa/ltrans-5.c: Removed.
	* gcc.dg/tree-ssa/ltrans-6.c: Removed.
	* gcc.dg/tree-ssa/ltrans-8.c: Removed.
	* gfortran.dg/ltrans-7.f90: Removed.
	* gcc.dg/tree-ssa/data-dep-1.c: Removed.

	* gcc.dg/pr18792.c: -> gcc.dg/graphite/pr18792.c
	* gcc.dg/pr19910.c: -> gcc.dg/graphite/pr19910.c
	* gcc.dg/tree-ssa/20041110-1.c: -> gcc.dg/graphite/pr20041110-1.c
	* gcc.dg/tree-ssa/pr20256.c: -> gcc.dg/graphite/pr20256.c
	* gcc.dg/pr23625.c: -> gcc.dg/graphite/pr23625.c
	* gcc.dg/tree-ssa/pr23820.c: -> gcc.dg/graphite/pr23820.c
	* gcc.dg/tree-ssa/pr24309.c: -> gcc.dg/graphite/pr24309.c
	* gcc.dg/tree-ssa/pr26435.c: -> gcc.dg/graphite/pr26435.c
	* gcc.dg/pr29330.c: -> gcc.dg/graphite/pr29330.c
	* gcc.dg/pr29581-1.c: -> gcc.dg/graphite/pr29581-1.c
	* gcc.dg/pr29581-2.c: -> gcc.dg/graphite/pr29581-2.c
	* gcc.dg/pr29581-3.c: -> gcc.dg/graphite/pr29581-3.c
	* gcc.dg/pr29581-4.c: -> gcc.dg/graphite/pr29581-4.c
	* gcc.dg/tree-ssa/loop-27.c: -> gcc.dg/graphite/pr30565.c
	* gcc.dg/tree-ssa/pr31183.c: -> gcc.dg/graphite/pr31183.c
	* gcc.dg/tree-ssa/pr33576.c: -> gcc.dg/graphite/pr33576.c
	* gcc.dg/tree-ssa/pr33766.c: -> gcc.dg/graphite/pr33766.c
	* gcc.dg/pr34016.c: -> gcc.dg/graphite/pr34016.c
	* gcc.dg/tree-ssa/pr34017.c: -> gcc.dg/graphite/pr34017.c
	* gcc.dg/tree-ssa/pr34123.c: -> gcc.dg/graphite/pr34123.c
	* gcc.dg/tree-ssa/pr36287.c: -> gcc.dg/graphite/pr36287.c
	* gcc.dg/tree-ssa/pr37686.c: -> gcc.dg/graphite/pr37686.c
	* gcc.dg/pr42917.c: -> gcc.dg/graphite/pr42917.c
	* gfortran.dg/loop_nest_1.f90: -> gfortran.dg/graphite/pr29290.f90
	* gfortran.dg/pr29581.f90: -> gfortran.dg/graphite/pr29581.f90
	* gfortran.dg/pr36286.f90: -> gfortran.dg/graphite/pr36286.f90
	* gfortran.dg/pr36922.f: -> gfortran.dg/graphite/pr36922.f
	* gfortran.dg/pr39516.f: -> gfortran.dg/graphite/pr39516.f

From-SVN: r169251

1 files changed, 119 insertions, 0 deletions

diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index 96759cb..9a11f80 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -240,6 +240,125 @@ name_to_copy_elt_hash (const void *aa)
   return (hashval_t) a->version;
 }
 
+/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
+   matrix.  Rather than use floats, we simply keep a single DENOMINATOR that
+   represents the denominator for every element in the matrix.  */
+typedef struct lambda_trans_matrix_s
+{
+  lambda_matrix matrix;
+  int rowsize;
+  int colsize;
+  int denominator;
+} *lambda_trans_matrix;
+#define LTM_MATRIX(T) ((T)->matrix)
+#define LTM_ROWSIZE(T) ((T)->rowsize)
+#define LTM_COLSIZE(T) ((T)->colsize)
+#define LTM_DENOMINATOR(T) ((T)->denominator)
+
+/* Allocate a new transformation matrix.  */
+
+static lambda_trans_matrix
+lambda_trans_matrix_new (int colsize, int rowsize,
+			 struct obstack * lambda_obstack)
+{
+  lambda_trans_matrix ret;
+
+  ret = (lambda_trans_matrix)
+    obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
+  LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
+  LTM_ROWSIZE (ret) = rowsize;
+  LTM_COLSIZE (ret) = colsize;
+  LTM_DENOMINATOR (ret) = 1;
+  return ret;
+}
+
+/* Multiply a vector VEC by a matrix MAT.
+   MAT is an M*N matrix, and VEC is a vector with length N.  The result
+   is stored in DEST which must be a vector of length M.  */
+
+static void
+lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,
+			   lambda_vector vec, lambda_vector dest)
+{
+  int i, j;
+
+  lambda_vector_clear (dest, m);
+  for (i = 0; i < m; i++)
+    for (j = 0; j < n; j++)
+      dest[i] += matrix[i][j] * vec[j];
+}
+
+/* Return true if TRANS is a legal transformation matrix that respects
+   the dependence vectors in DISTS and DIRS.  The conservative answer
+   is false.
+
+   "Wolfe proves that a unimodular transformation represented by the
+   matrix T is legal when applied to a loop nest with a set of
+   lexicographically non-negative distance vectors RDG if and only if
+   for each vector d in RDG, (T.d >= 0) is lexicographically positive.
+   i.e.: if and only if it transforms the lexicographically positive
+   distance vectors to lexicographically positive vectors.  Note that
+   a unimodular matrix must transform the zero vector (and only it) to
+   the zero vector." S.Muchnick.  */
+
+static bool
+lambda_transform_legal_p (lambda_trans_matrix trans,
+			  int nb_loops,
+			  VEC (ddr_p, heap) *dependence_relations)
+{
+  unsigned int i, j;
+  lambda_vector distres;
+  struct data_dependence_relation *ddr;
+
+  gcc_assert (LTM_COLSIZE (trans) == nb_loops
+	      && LTM_ROWSIZE (trans) == nb_loops);
+
+  /* When there are no dependences, the transformation is correct.  */
+  if (VEC_length (ddr_p, dependence_relations) == 0)
+    return true;
+
+  ddr = VEC_index (ddr_p, dependence_relations, 0);
+  if (ddr == NULL)
+    return true;
+
+  /* When there is an unknown relation in the dependence_relations, we
+     know that it is no worth looking at this loop nest: give up.  */
+  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+    return false;
+
+  distres = lambda_vector_new (nb_loops);
+
+  /* For each distance vector in the dependence graph.  */
+  FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
+    {
+      /* Don't care about relations for which we know that there is no
+	 dependence, nor about read-read (aka. output-dependences):
+	 these data accesses can happen in any order.  */
+      if (DDR_ARE_DEPENDENT (ddr) == chrec_known
+	  || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
+	continue;
+
+      /* Conservatively answer: "this transformation is not valid".  */
+      if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+	return false;
+
+      /* If the dependence could not be captured by a distance vector,
+	 conservatively answer that the transform is not valid.  */
+      if (DDR_NUM_DIST_VECTS (ddr) == 0)
+	return false;
+
+      /* Compute trans.dist_vect */
+      for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
+	{
+	  lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
+				     DDR_DIST_VECT (ddr, j), distres);
+
+	  if (!lambda_vector_lexico_pos (distres, nb_loops))
+	    return false;
+	}
+    }
+  return true;
+}
 
 /* Data dependency analysis. Returns true if the iterations of LOOP
    are independent on each other (that is, if we can execute them