CbC/CbC_gcc: gcc/tree-data-ref.c comparison

comparison gcc/tree-data-ref.c @ 67:f6334be47118

update gcc from gcc-4.6-20100522 to gcc-4.6-20110318

author	nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Tue, 22 Mar 2011 17:18:12 +0900
parents	b7f97abdc517
children	04ced10e8804

comparison

equal deleted inserted replaced

-:65488c3d617d
+:f6334be47118
 */
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "flags.h"
-#include "tree.h"
-/* These RTL headers are needed for basic-block.h.  */
-#include "basic-block.h"
-#include "diagnostic.h"
-#include "tree-pretty-print.h"
 #include "gimple-pretty-print.h"
 #include "tree-flow.h"
-#include "tree-dump.h"
-#include "timevar.h"
 #include "cfgloop.h"
 #include "tree-data-ref.h"
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
 #include "langhooks.h"
 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
 {
 unsigned int i;
 struct data_reference *dr;
-for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
+FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
 dump_data_reference (file, dr);
 }
 /* Dump into STDERR all the data references from DATAREFS.  */
-void
+DEBUG_FUNCTION void
 debug_data_references (VEC (data_reference_p, heap) *datarefs)
 {
 dump_data_references (stderr, datarefs);
 }
 /* Dump to STDERR all the dependence relations from DDRS.  */
-void
+DEBUG_FUNCTION void
 debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
 {
 dump_data_dependence_relations (stderr, ddrs);
 }
 				VEC (ddr_p, heap) *ddrs)
 {
 unsigned int i;
 struct data_dependence_relation *ddr;
-for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
 dump_data_dependence_relation (file, ddr);
 }
 /* Print to STDERR the data_reference DR.  */
-void
+DEBUG_FUNCTION void
 debug_data_reference (struct data_reference *dr)
 {
 dump_data_reference (stderr, dr);
 }
 dump_data_reference (FILE *outf,
 		     struct data_reference *dr)
 {
 unsigned int i;
-fprintf (outf, "#(Data Ref: \n#  stmt: ");
+fprintf (outf, "#(Data Ref: \n");
+fprintf (outf, "#  bb: %d \n", gimple_bb (DR_STMT (dr))->index);
+fprintf (outf, "#  stmt: ");
 print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
 fprintf (outf, "#  ref: ");
 print_generic_stmt (outf, DR_REF (dr), 0);
 fprintf (outf, "#  base_object: ");
 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
 		   int length)
 {
 unsigned j;
 lambda_vector v;
-for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
+FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, v)
 print_direction_vector (outf, v, length);
+}
+/* Print out a vector VEC of length N to OUTFILE.  */
+static inline void
+print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
+{
+int i;
+for (i = 0; i < n; i++)
+fprintf (outfile, "%3d ", vector[i]);
+fprintf (outfile, "\n");
 }
 /* Print a vector of distance vectors.  */
 void
 		     int length)
 {
 unsigned j;
 lambda_vector v;
-for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
+FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, v)
 print_lambda_vector (outf, v, length);
 }
 /* Debug version.  */
-void
+DEBUG_FUNCTION void
 debug_data_dependence_relation (struct data_dependence_relation *ddr)
 {
 dump_data_dependence_relation (stderr, ddr);
 }
 	  dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
 	}
 fprintf (outf, "  inner loop index: %d\n", DDR_INNER_LOOP (ddr));
 fprintf (outf, "  loop nest: (");
-for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+FOR_EACH_VEC_ELT (loop_p, DDR_LOOP_NEST (ddr), i, loopi)
 	fprintf (outf, "%d ", loopi->num);
 fprintf (outf, ")\n");
 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
 	{
 {
 unsigned int i, j;
 struct data_dependence_relation *ddr;
 lambda_vector v;
-for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
 {
-	for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
+	FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), j, v)
 	  {
 	    fprintf (file, "DISTANCE_V (");
 	    print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
 	    fprintf (file, ")\n");
 	  }
-	for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
+	FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), j, v)
 	  {
 	    fprintf (file, "DIRECTION_V (");
 	    print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
 	    fprintf (file, ")\n");
 	  }
 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
 {
 unsigned int i;
 struct data_dependence_relation *ddr;
-for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
 dump_data_dependence_relation (file, ddr);
 fprintf (file, "\n\n");
 }
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "failed: bit offset alignment.\n");
 return false;
 }
-base = build_fold_addr_expr (base);
+if (TREE_CODE (base) == MEM_REF)
+{
+if (!integer_zerop (TREE_OPERAND (base, 1)))
+	{
+	  if (!poffset)
+	    {
+	      double_int moff = mem_ref_offset (base);
+	      poffset = double_int_to_tree (sizetype, moff);
+	    }
+	  else
+	    poffset = size_binop (PLUS_EXPR, poffset, TREE_OPERAND (base, 1));
+	}
+base = TREE_OPERAND (base, 0);
+}
+else
+base = build_fold_addr_expr (base);
 if (in_loop)
 {
 if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
 false))
 {
 return true;
 }
 /* Determines the base object and the list of indices of memory reference
-DR, analyzed in loop nest NEST.  */
+DR, analyzed in LOOP and instantiated in loop nest NEST.  */
 static void
-dr_analyze_indices (struct data_reference *dr, struct loop *nest)
+dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
 {
-gimple stmt = DR_STMT (dr);
-struct loop *loop = loop_containing_stmt (stmt);
 VEC (tree, heap) *access_fns = NULL;
 tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
 tree base, off, access_fn = NULL_TREE;
 basic_block before_loop = NULL;
 	}
 aref = TREE_OPERAND (aref, 0);
 }
-if (nest && INDIRECT_REF_P (aref))
+if (nest
+&& (INDIRECT_REF_P (aref)
+	  || TREE_CODE (aref) == MEM_REF))
 {
 op = TREE_OPERAND (aref, 0);
 access_fn = analyze_scalar_evolution (loop, op);
 access_fn = instantiate_scev (before_loop, loop, access_fn);
 base = initial_condition (access_fn);
 split_constant_offset (base, &base, &off);
+if (TREE_CODE (aref) == MEM_REF)
+	off = size_binop (PLUS_EXPR, off,
+			  fold_convert (ssizetype, TREE_OPERAND (aref, 1)));
 access_fn = chrec_replace_initial_condition (access_fn,
 			fold_convert (TREE_TYPE (base), off));
 TREE_OPERAND (aref, 0) = base;
 VEC_safe_push (tree, heap, access_fns, access_fn);
 }
+if (TREE_CODE (aref) == MEM_REF)
+TREE_OPERAND (aref, 1)
+= build_int_cst (TREE_TYPE (TREE_OPERAND (aref, 1)), 0);
+if (TREE_CODE (ref) == MEM_REF
+&& TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR
+&& integer_zerop (TREE_OPERAND (ref, 1)))
+ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0);
+/* For canonicalization purposes we'd like to strip all outermost
+zero-offset component-refs.
+???  For now simply handle zero-index array-refs.  */
+while (TREE_CODE (ref) == ARRAY_REF
+	 && integer_zerop (TREE_OPERAND (ref, 1)))
+ref = TREE_OPERAND (ref, 0);
 DR_BASE_OBJECT (dr) = ref;
 DR_ACCESS_FNS (dr) = access_fns;
 }
 /* Extracts the alias analysis information from the memory reference DR.  */
 dr_analyze_alias (struct data_reference *dr)
 {
 tree ref = DR_REF (dr);
 tree base = get_base_address (ref), addr;
-if (INDIRECT_REF_P (base))
+if (INDIRECT_REF_P (base)
+|| TREE_CODE (base) == MEM_REF)
 {
 addr = TREE_OPERAND (base, 0);
 if (TREE_CODE (addr) == SSA_NAME)
 	DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
 }
 dr_address_invariant_p (struct data_reference *dr)
 {
 unsigned i;
 tree idx;
-for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++)
+FOR_EACH_VEC_ELT (tree, DR_ACCESS_FNS (dr), i, idx)
 if (tree_contains_chrecs (idx, NULL))
 return false;
 return true;
 }
 free (dr);
 }
 /* Analyzes memory reference MEMREF accessed in STMT.  The reference
 is read if IS_READ is true, write otherwise.  Returns the
-data_reference description of MEMREF.  NEST is the outermost loop of the
+data_reference description of MEMREF.  NEST is the outermost loop
-loop nest in that the reference should be analyzed.  */
+in which the reference should be instantiated, LOOP is the loop in
+which the data reference should be analyzed.  */
 struct data_reference *
-create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read)
+create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
+		 bool is_read)
 {
 struct data_reference *dr;
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 DR_STMT (dr) = stmt;
 DR_REF (dr) = memref;
 DR_IS_READ (dr) = is_read;
 dr_analyze_innermost (dr);
-dr_analyze_indices (dr, nest);
+dr_analyze_indices (dr, nest, loop);
 dr_analyze_alias (dr);
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 fprintf (dump_file, "\tbase_address: ");
 	    return false;
 	}
 obj = TREE_OPERAND (obj, 0);
 }
-if (!INDIRECT_REF_P (obj))
+if (!INDIRECT_REF_P (obj)
+&& TREE_CODE (obj) != MEM_REF)
 return true;
 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
 						  loop->num);
 }
-/* Returns true if A and B are accesses to different objects, or to different
-fields of the same object.  */
-static bool
-disjoint_objects_p (tree a, tree b)
-{
-tree base_a, base_b;
-VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
-bool ret;
-base_a = get_base_address (a);
-base_b = get_base_address (b);
-if (DECL_P (base_a)
-&& DECL_P (base_b)
-&& base_a != base_b)
-return true;
-if (!operand_equal_p (base_a, base_b, 0))
-return false;
-/* Compare the component references of A and B.  We must start from the inner
-ones, so record them to the vector first.  */
-while (handled_component_p (a))
-{
-VEC_safe_push (tree, heap, comp_a, a);
-a = TREE_OPERAND (a, 0);
-}
-while (handled_component_p (b))
-{
-VEC_safe_push (tree, heap, comp_b, b);
-b = TREE_OPERAND (b, 0);
-}
-ret = false;
-while (1)
-{
-if (VEC_length (tree, comp_a) == 0
-	  || VEC_length (tree, comp_b) == 0)
-	break;
-a = VEC_pop (tree, comp_a);
-b = VEC_pop (tree, comp_b);
-/* Real and imaginary part of a variable do not alias.  */
-if ((TREE_CODE (a) == REALPART_EXPR
-	   && TREE_CODE (b) == IMAGPART_EXPR)
-	  || (TREE_CODE (a) == IMAGPART_EXPR
-	      && TREE_CODE (b) == REALPART_EXPR))
-	{
-	  ret = true;
-	  break;
-	}
-if (TREE_CODE (a) != TREE_CODE (b))
-	break;
-/* Nothing to do for ARRAY_REFs, as the indices of array_refs in
-	 DR_BASE_OBJECT are always zero.  */
-if (TREE_CODE (a) == ARRAY_REF)
-	continue;
-else if (TREE_CODE (a) == COMPONENT_REF)
-	{
-	  if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
-	    continue;
-	  /* Different fields of unions may overlap.  */
-	  base_a = TREE_OPERAND (a, 0);
-	  if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
-	    break;
-	  /* Different fields of structures cannot.  */
-	  ret = true;
-	  break;
-	}
-else
-	break;
-}
-VEC_free (tree, heap, comp_a);
-VEC_free (tree, heap, comp_b);
-return ret;
-}
 /* Returns false if we can prove that data references A and B do not alias,
 true otherwise.  */
 bool
 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
 {
-const_tree addr_a = DR_BASE_ADDRESS (a);
+tree addr_a = DR_BASE_OBJECT (a);
-const_tree addr_b = DR_BASE_ADDRESS (b);
+tree addr_b = DR_BASE_OBJECT (b);
-const_tree type_a, type_b;
-const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
+if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
+return refs_output_dependent_p (addr_a, addr_b);
-/* If the accessed objects are disjoint, the memory references do not
+else if (DR_IS_READ (a) && DR_IS_WRITE (b))
-alias.  */
+return refs_anti_dependent_p (addr_a, addr_b);
-if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
+return refs_may_alias_p (addr_a, addr_b);
-return false;
-/* Query the alias oracle.  */
-if (!DR_IS_READ (a) && !DR_IS_READ (b))
-{
-if (!refs_output_dependent_p (DR_REF (a), DR_REF (b)))
-	return false;
-}
-else if (DR_IS_READ (a) && !DR_IS_READ (b))
-{
-if (!refs_anti_dependent_p (DR_REF (a), DR_REF (b)))
-	return false;
-}
-else if (!refs_may_alias_p (DR_REF (a), DR_REF (b)))
-return false;
-if (!addr_a || !addr_b)
-return true;
-/* If the references are based on different static objects, they cannot
-alias (PTA should be able to disambiguate such accesses, but often
-it fails to).  */
-if (TREE_CODE (addr_a) == ADDR_EXPR
-&& TREE_CODE (addr_b) == ADDR_EXPR)
-return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
-/* An instruction writing through a restricted pointer is "independent" of any
-instruction reading or writing through a different restricted pointer,
-in the same block/scope.  */
-type_a = TREE_TYPE (addr_a);
-type_b = TREE_TYPE (addr_b);
-gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
-if (TREE_CODE (addr_a) == SSA_NAME)
-decl_a = SSA_NAME_VAR (addr_a);
-if (TREE_CODE (addr_b) == SSA_NAME)
-decl_b = SSA_NAME_VAR (addr_b);
-if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
-&& (!DR_IS_READ (a) || !DR_IS_READ (b))
-&& decl_a && DECL_P (decl_a)
-&& decl_b && DECL_P (decl_b)
-&& decl_a != decl_b
-&& TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
-&& DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
-return false;
-return true;
 }
 static void compute_self_dependence (struct data_dependence_relation *);
 /* Initialize a data dependence relation between data accesses A and
 {
 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
 return res;
 }
-gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
+/* If the number of dimensions of the access to not agree we can have
+a pointer access to a component of the array element type and an
+array access while the base-objects are still the same.  Punt.  */
+if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
+{
+DDR_ARE_DEPENDENT (res) = chrec_dont_know;
+return res;
+}
 DDR_AFFINE_P (res) = true;
 DDR_ARE_DEPENDENT (res) = NULL_TREE;
 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
 DDR_LOOP_NEST (res) = loop_nest;
 free_subscripts (VEC (subscript_p, heap) *subscripts)
 {
 unsigned i;
 subscript_p s;
-for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
+FOR_EACH_VEC_ELT (subscript_p, subscripts, i, s)
 {
 free_conflict_function (s->conflicting_iterations_in_a);
 free_conflict_function (s->conflicting_iterations_in_b);
 free (s);
 }
 bool
 estimated_loop_iterations (struct loop *loop, bool conservative,
 			   double_int *nit)
 {
-estimate_numbers_of_iterations_loop (loop);
+estimate_numbers_of_iterations_loop (loop, true);
 if (conservative)
 {
 if (!loop->any_upper_bound)
 	return false;
 affine_fn_free (overlaps_b_xz);
 affine_fn_free (overlaps_a_yz);
 affine_fn_free (overlaps_b_yz);
 affine_fn_free (overlaps_a_xyz);
 affine_fn_free (overlaps_b_xyz);
+}
+/* Copy the elements of vector VEC1 with length SIZE to VEC2.  */
+static void
+lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
+		    int size)
+{
+memcpy (vec2, vec1, size * sizeof (*vec1));
+}
+/* Copy the elements of M x N matrix MAT1 to MAT2.  */
+static void
+lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
+		    int m, int n)
+{
+int i;
+for (i = 0; i < m; i++)
+lambda_vector_copy (mat1[i], mat2[i], n);
+}
+/* Store the N x N identity matrix in MAT.  */
+static void
+lambda_matrix_id (lambda_matrix mat, int size)
+{
+int i, j;
+for (i = 0; i < size; i++)
+for (j = 0; j < size; j++)
+mat[i][j] = (i == j) ? 1 : 0;
+}
+/* Return the first nonzero element of vector VEC1 between START and N.
+We must have START <= N.   Returns N if VEC1 is the zero vector.  */
+static int
+lambda_vector_first_nz (lambda_vector vec1, int n, int start)
+{
+int j = start;
+while (j < n && vec1[j] == 0)
+j++;
+return j;
+}
+/* Add a multiple of row R1 of matrix MAT with N columns to row R2:
+R2 = R2 + CONST1 * R1.  */
+static void
+lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
+{
+int i;
+if (const1 == 0)
+return;
+for (i = 0; i < n; i++)
+mat[r2][i] += const1 * mat[r1][i];
+}
+/* Swap rows R1 and R2 in matrix MAT.  */
+static void
+lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
+{
+lambda_vector row;
+row = mat[r1];
+mat[r1] = mat[r2];
+mat[r2] = row;
+}
+/* Multiply vector VEC1 of length SIZE by a constant CONST1,
+and store the result in VEC2.  */
+static void
+lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
+			  int size, int const1)
+{
+int i;
+if (const1 == 0)
+lambda_vector_clear (vec2, size);
+else
+for (i = 0; i < size; i++)
+vec2[i] = const1 * vec1[i];
+}
+/* Negate vector VEC1 with length SIZE and store it in VEC2.  */
+static void
+lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
+		      int size)
+{
+lambda_vector_mult_const (vec1, vec2, size, -1);
+}
+/* Negate row R1 of matrix MAT which has N columns.  */
+static void
+lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
+{
+lambda_vector_negate (mat[r1], mat[r1], n);
+}
+/* Return true if two vectors are equal.  */
+static bool
+lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
+{
+int i;
+for (i = 0; i < size; i++)
+if (vec1[i] != vec2[i])
+return false;
+return true;
+}
+/* Given an M x N integer matrix A, this function determines an M x
+M unimodular matrix U, and an M x N echelon matrix S such that
+"U.A = S".  This decomposition is also known as "right Hermite".
+Ref: Algorithm 2.1 page 33 in "Loop Transformations for
+Restructuring Compilers" Utpal Banerjee.  */
+static void
+lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
+			     lambda_matrix S, lambda_matrix U)
+{
+int i, j, i0 = 0;
+lambda_matrix_copy (A, S, m, n);
+lambda_matrix_id (U, m);
+for (j = 0; j < n; j++)
+{
+if (lambda_vector_first_nz (S[j], m, i0) < m)
+	{
+	  ++i0;
+	  for (i = m - 1; i >= i0; i--)
+	    {
+	      while (S[i][j] != 0)
+		{
+		  int sigma, factor, a, b;
+		  a = S[i-1][j];
+		  b = S[i][j];
+		  sigma = (a * b < 0) ? -1: 1;
+		  a = abs (a);
+		  b = abs (b);
+		  factor = sigma * (a / b);
+		  lambda_matrix_row_add (S, n, i, i-1, -factor);
+		  lambda_matrix_row_exchange (S, i, i-1);
+		  lambda_matrix_row_add (U, m, i, i-1, -factor);
+		  lambda_matrix_row_exchange (U, i, i-1);
+		}
+	    }
+	}
+}
 }
 /* Determines the overlapping elements due to accesses CHREC_A and
 CHREC_B, that are affine functions.  This function cannot handle
 symbolic evolution functions, ie. when initial conditions are
 		       conflict_function **overlaps_a,
 		       conflict_function **overlaps_b,
 		       tree *last_conflicts,
 		       struct loop *loop_nest)
 {
-/* FIXME:  This is a MIV subscript, not yet handled.
-Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
-(A[i] vs. A[j]).
-In the SIV test we had to solve a Diophantine equation with two
-variables.  In the MIV case we have to solve a Diophantine
-equation with 2*n variables (if the subscript uses n IVs).
-*/
 tree type, difference;
 dependence_stats.num_miv++;
 if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file, "(analyze_miv_subscript \n");
 }
 /* If they are the same chrec, and are affine, they overlap
 on every iteration.  */
 else if (eq_evolutions_p (chrec_a, chrec_b)
-	   && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
+	   && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
+	       || operand_equal_p (chrec_a, chrec_b, 0)))
 {
 dependence_stats.num_same_subscript_function++;
 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
 *last_conflicts = chrec_dont_know;
 }
 /* If they aren't the same, and aren't affine, we can't do anything
-yet. */
+yet.  */
 else if ((chrec_contains_symbols (chrec_a)
 	    || chrec_contains_symbols (chrec_b))
 	   && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
 	       || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
 {
 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
 {
 unsigned i;
 lambda_vector v;
-for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
+FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, v)
 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
 return;
 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
 }
 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
 {
 unsigned i;
 lambda_vector v;
-for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
+FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), i, v)
 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
 return;
 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
 }
 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
 	  && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
 	{
 	  int dist, index;
-	  int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
+	  int var_a = CHREC_VARIABLE (access_fn_a);
-					    DDR_LOOP_NEST (ddr));
+	  int var_b = CHREC_VARIABLE (access_fn_b);
-	  int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
-					    DDR_LOOP_NEST (ddr));
+	  if (var_a != var_b
+	      || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
-	  /* The dependence is carried by the outermost loop.  Example:
-	     | loop_1
-	     |   A[{4, +, 1}_1]
-	     |   loop_2
-	     |     A[{5, +, 1}_2]
-	     |   endloop_2
-	     | endloop_1
-	     In this case, the dependence is carried by loop_1.  */
-	  index = index_a < index_b ? index_a : index_b;
-	  *index_carry = MIN (index, *index_carry);
-	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
 	      non_affine_dependence_relation (ddr);
 	      return false;
 	    }
 	  dist = int_cst_value (SUB_DISTANCE (subscript));
+	  index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
+	  *index_carry = MIN (index, *index_carry);
 	  /* This is the subscript coupling test.  If we have already
 	     recorded a distance for this loop (a distance coming from
 	     another subscript), it should be the same.  For example,
 	     in the following code, there is no dependence:
 build_classic_dir_vector (struct data_dependence_relation *ddr)
 {
 unsigned i, j;
 lambda_vector dist_v;
-for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
+FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v)
 {
 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
 	dir_v[j] = dir_from_dist (dist_v[j]);
 {
 unsigned int i;
 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
 tree t;
-for (i = 0; VEC_iterate (tree, fns, i, t); i++)
+FOR_EACH_VEC_ELT (tree, fns, i, t)
 if (!evolution_function_is_invariant_p (t, loop_nest->num)
 	&& !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
 return false;
 return true;
 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
 				     TREE_TYPE (access_fun_b));
 tree fun_a = chrec_convert (type, access_fun_a, NULL);
 tree fun_b = chrec_convert (type, access_fun_b, NULL);
 tree difference = chrec_fold_minus (type, fun_a, fun_b);
+tree minus_one;
 /* When the fun_a - fun_b is not constant, the dependence is not
 captured by the classic distance vector representation.  */
 if (TREE_CODE (difference) != INTEGER_CST)
 return false;
 /* There is no dependence.  */
 *maybe_dependent = false;
 return true;
 }
-fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
+minus_one = build_int_cst (type, -1);
+fun_b = chrec_fold_multiply (type, fun_b, minus_one);
 eq = omega_add_zero_eq (pb, omega_black);
 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
 /* There is probably a dependence, but the system of
 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
 	       VEC_length (lambda_vector, dist_vects),
 	       DDR_NUM_DIST_VECTS (ddr));
 fprintf (file, "Banerjee dist vectors:\n");
-for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
+FOR_EACH_VEC_ELT (lambda_vector, dist_vects, i, b_dist_v)
 	print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
 fprintf (file, "Omega dist vectors:\n");
 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
 	print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
 lambda_vector a_dist_v;
 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
 /* Distance vectors are not ordered in the same way in the DDR
 	 and in the DIST_VECTS: search for a matching vector.  */
-for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
+FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, a_dist_v)
 	if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
 	  break;
 if (j == VEC_length (lambda_vector, dist_vects))
 	{
 lambda_vector a_dir_v;
 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
 /* Direction vectors are not ordered in the same way in the DDR
 	 and in the DIR_VECTS: search for a matching vector.  */
-for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
+FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, a_dir_v)
 	if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
 	  break;
 if (j == VEC_length (lambda_vector, dist_vects))
 	{
 {
 struct data_dependence_relation *ddr;
 struct data_reference *a, *b;
 unsigned int i, j;
-for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
+FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
-if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
+if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
 	{
 	  ddr = initialize_data_dependence_relation (a, b, loop_nest);
 	  VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
 if (loop_nest)
 	    compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
 	}
 if (compute_self_and_rr)
-for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
+FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
 {
 	ddr = initialize_data_dependence_relation (a, a, loop_nest);
 	VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
 	compute_self_dependence (ddr);
 }
 {
 VEC_free (data_ref_loc, heap, references);
 return false;
 }
-for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
+FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
 {
-dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+dr = create_data_ref (nest, loop_containing_stmt (stmt),
+			    *ref->pos, stmt, ref->is_read);
 gcc_assert (dr != NULL);
 /* FIXME -- data dependence analysis does not work correctly for objects
 with invariant addresses in loop nests.  Let us fail here until the
 	 problem is fixed.  */
 }
 VEC_free (data_ref_loc, heap, references);
 return ret;
 }
-/* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
+/* Stores the data references in STMT to DATAREFS.  If there is an
-reference, returns false, otherwise returns true.  NEST is the outermost
+unanalyzable reference, returns false, otherwise returns true.
-loop of the loop nest in which the references should be analyzed.  */
+NEST is the outermost loop of the loop nest in which the references
+should be instantiated, LOOP is the loop in which the references
+should be analyzed.  */
 bool
-graphite_find_data_references_in_stmt (struct loop *nest, gimple stmt,
+graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
 				       VEC (data_reference_p, heap) **datarefs)
 {
 unsigned i;
 VEC (data_ref_loc, heap) *references;
 data_ref_loc *ref;
 {
 VEC_free (data_ref_loc, heap, references);
 return false;
 }
-for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
+FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
 {
-dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+dr = create_data_ref (nest, loop, *ref->pos, stmt, ref->is_read);
 gcc_assert (dr != NULL);
 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
 }
 VEC_free (data_ref_loc, heap, references);
 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
 bool
 compute_data_dependences_for_loop (struct loop *loop,
 				   bool compute_self_and_read_read_dependences,
+				   VEC (loop_p, heap) **loop_nest,
 				   VEC (data_reference_p, heap) **datarefs,
 				   VEC (ddr_p, heap) **dependence_relations)
 {
 bool res = true;
-VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
 memset (&dependence_stats, 0, sizeof (dependence_stats));
 /* If the loop nest is not well formed, or one of the data references
 is not computable, give up without spending time to compute other
 dependences.  */
 if (!loop
-|| !find_loop_nest (loop, &vloops)
+|| !find_loop_nest (loop, loop_nest)
 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
 {
 struct data_dependence_relation *ddr;
 /* Insert a single relation into dependence_relations:
 	 chrec_dont_know.  */
-ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
+ddr = initialize_data_dependence_relation (NULL, NULL, *loop_nest);
 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
 res = false;
 }
 else
-compute_all_dependences (*datarefs, dependence_relations, vloops,
+compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
 			     compute_self_and_read_read_dependences);
 if (dump_file && (dump_flags & TDF_STATS))
 {
 fprintf (dump_file, "Dependence tester statistics:\n");
 int nb_data_refs = 10;
 VEC (data_reference_p, heap) *datarefs =
 VEC_alloc (data_reference_p, heap, nb_data_refs);
 VEC (ddr_p, heap) *dependence_relations =
 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
+VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3);
 /* Compute DDs on the whole function.  */
-compute_data_dependences_for_loop (loop, false, &datarefs,
+compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
 				     &dependence_relations);
 if (dump_file)
 {
 dump_data_dependence_relations (dump_file, dependence_relations);
 	  unsigned nb_top_relations = 0;
 	  unsigned nb_bot_relations = 0;
 	  unsigned nb_chrec_relations = 0;
 	  struct data_dependence_relation *ddr;
-	  for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+	  FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
 	    {
 	      if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
 		nb_top_relations++;
 	      else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 	  gather_stats_on_scev_database ();
 	}
 }
+VEC_free (loop_p, heap, loop_nest);
 free_dependence_relations (dependence_relations);
 free_data_refs (datarefs);
 }
 /* Computes all the data dependences and check that the results of
 void
 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
 {
 unsigned int i;
 struct data_dependence_relation *ddr;
-VEC (loop_p, heap) *loop_nest = NULL;
+FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
-for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+if (ddr)
-{
-if (ddr == NULL)
-	continue;
-if (loop_nest == NULL)
-	loop_nest = DDR_LOOP_NEST (ddr);
-else
-	gcc_assert (DDR_LOOP_NEST (ddr) == NULL
-		    || DDR_LOOP_NEST (ddr) == loop_nest);
 free_dependence_relation (ddr);
-}
-if (loop_nest)
-VEC_free (loop_p, heap, loop_nest);
 VEC_free (ddr_p, heap, dependence_relations);
 }
 /* Free the memory used by the data references from DATAREFS.  */
 free_data_refs (VEC (data_reference_p, heap) *datarefs)
 {
 unsigned int i;
 struct data_reference *dr;
-for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
+FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
 free_data_ref (dr);
 VEC_free (data_reference_p, heap, datarefs);
 }
 if (v->succ)
 for (e = v->succ; e; e = e->succ_next)
 fprintf (file, " %d", e->dest);
-fprintf (file, ") \n");
+fprintf (file, ")\n");
 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
 fprintf (file, ")\n");
 }
 /* Call dump_rdg_vertex on stderr.  */
-void
+DEBUG_FUNCTION void
 debug_rdg_vertex (struct graph *rdg, int i)
 {
 dump_rdg_vertex (stderr, rdg, i);
 }
 fprintf (file, ")\n");
 }
 /* Call dump_rdg_vertex on stderr.  */
-void
+DEBUG_FUNCTION void
 debug_rdg_component (struct graph *rdg, int c)
 {
 dump_rdg_component (stderr, rdg, c, NULL);
 }
 BITMAP_FREE (dumped);
 }
 /* Call dump_rdg on stderr.  */
-void
+DEBUG_FUNCTION void
 debug_rdg (struct graph *rdg)
 {
 dump_rdg (stderr, rdg);
+}
+static void
+dot_rdg_1 (FILE *file, struct graph *rdg)
+{
+int i;
+fprintf (file, "digraph RDG {\n");
+for (i = 0; i < rdg->n_vertices; i++)
+{
+struct vertex *v = &(rdg->vertices[i]);
+struct graph_edge *e;
+/* Highlight reads from memory.  */
+if (RDG_MEM_READS_STMT (rdg, i))
+fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
+/* Highlight stores to memory.  */
+if (RDG_MEM_WRITE_STMT (rdg, i))
+fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
+if (v->succ)
+for (e = v->succ; e; e = e->succ_next)
+switch (RDGE_TYPE (e))
+{
+case input_dd:
+fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
+break;
+case output_dd:
+fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
+break;
+case flow_dd:
+/* These are the most common dependences: don't print these. */
+fprintf (file, "%d -> %d \n", i, e->dest);
+break;
+case anti_dd:
+fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
+break;
+default:
+gcc_unreachable ();
+}
+}
+fprintf (file, "}\n\n");
+}
+/* Display the Reduced Dependence Graph using dotty.  */
+extern void dot_rdg (struct graph *);
+DEBUG_FUNCTION void
+dot_rdg (struct graph *rdg)
+{
+/* When debugging, enable the following code.  This cannot be used
+in production compilers because it calls "system".  */
+#if 0
+FILE *file = fopen ("/tmp/rdg.dot", "w");
+gcc_assert (file != NULL);
+dot_rdg_1 (file, rdg);
+fclose (file);
+system ("dotty /tmp/rdg.dot &");
+#else
+dot_rdg_1 (stderr, rdg);
+#endif
 }
 /* This structure is used for recording the mapping statement index in
 the RDG.  */
 RDGE_RELATION (e) = ddr;
 /* Determines the type of the data dependence.  */
 if (DR_IS_READ (dra) && DR_IS_READ (drb))
 RDGE_TYPE (e) = input_dd;
-else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
+else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
 RDGE_TYPE (e) = output_dd;
-else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
+else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
 RDGE_TYPE (e) = flow_dd;
-else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
+else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
 RDGE_TYPE (e) = anti_dd;
 }
 /* Creates dependence edges in RDG for all the uses of DEF.  IDEF is
 the index of DEF in RDG.  */
 int i;
 struct data_dependence_relation *ddr;
 def_operand_p def_p;
 ssa_op_iter iter;
-for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 create_rdg_edge_for_ddr (rdg, ddr);
 for (i = 0; i < rdg->n_vertices; i++)
 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
 {
 int i, j;
 gimple stmt;
-for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
+FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
 {
 VEC (data_ref_loc, heap) *references;
 data_ref_loc *ref;
 struct vertex *v = &(rdg->vertices[i]);
 struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
 RDG_MEM_READS_STMT (rdg, i) = false;
 if (gimple_code (stmt) == GIMPLE_PHI)
 	continue;
 get_references_in_stmt (stmt, &references);
-for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++)
+FOR_EACH_VEC_ELT (data_ref_loc, references, j, ref)
 	if (!ref->is_read)
 	  RDG_MEM_WRITE_STMT (rdg, i) = true;
 	else
 	  RDG_MEM_READS_STMT (rdg, i) = true;
 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
 {
 ddr_p ddr;
 unsigned int i;
-for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 return false;
 return true;
 }
 /* Build the Reduced Dependence Graph (RDG) with one vertex per
 statement of the loop nest, and one edge per data dependence or
 scalar dependence.  */
 struct graph *
-build_rdg (struct loop *loop)
+build_rdg (struct loop *loop,
-{
+	   VEC (loop_p, heap) **loop_nest,
-int nb_data_refs = 10;
+	   VEC (ddr_p, heap) **dependence_relations,
+	   VEC (data_reference_p, heap) **datarefs)
+{
 struct graph *rdg = NULL;
-VEC (ddr_p, heap) *dependence_relations;
+VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
-VEC (data_reference_p, heap) *datarefs;
-VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
+compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
+				     dependence_relations);
-dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
-datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
+if (known_dependences_p (*dependence_relations))
-compute_data_dependences_for_loop (loop,
+{
-false,
+stmts_from_loop (loop, &stmts);
-&datarefs,
+rdg = build_empty_rdg (VEC_length (gimple, stmts));
-&dependence_relations);
+create_rdg_vertices (rdg, stmts);
+create_rdg_edges (rdg, *dependence_relations);
-if (!known_dependences_p (dependence_relations))
+}
-{
-free_dependence_relations (dependence_relations);
-free_data_refs (datarefs);
-VEC_free (gimple, heap, stmts);
-return rdg;
-}
-stmts_from_loop (loop, &stmts);
-rdg = build_empty_rdg (VEC_length (gimple, stmts));
-rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
-			      eq_stmt_vertex_info, hash_stmt_vertex_del);
-create_rdg_vertices (rdg, stmts);
-create_rdg_edges (rdg, dependence_relations);
 VEC_free (gimple, heap, stmts);
 return rdg;
 }
 free_rdg (struct graph *rdg)
 {
 int i;
 for (i = 0; i < rdg->n_vertices; i++)
-free (rdg->vertices[i].data);
+{
+struct vertex *v = &(rdg->vertices[i]);
+struct graph_edge *e;
+for (e = v->succ; e; e = e->succ_next)
+	if (e->data)
+	  free (e->data);
+if (v->data)
+	free (v->data);
+}
 htab_delete (rdg->indices);
 free_graph (rdg);
 }
 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 	if (gimple_vdef (gsi_stmt (bsi)))
 	  VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
 }
+free (bbs);
+}
+/* Returns true when the statement at STMT is of the form "A[i] = 0"
+that contains a data reference on its LHS with a stride of the same
+size as its unit type.  */
+bool
+stmt_with_adjacent_zero_store_dr_p (gimple stmt)
+{
+tree op0, op1;
+bool res;
+struct data_reference *dr;
+if (!stmt
+|| !gimple_vdef (stmt)
+|| !is_gimple_assign (stmt)
+|| !gimple_assign_single_p (stmt)
+|| !(op1 = gimple_assign_rhs1 (stmt))
+|| !(integer_zerop (op1) || real_zerop (op1)))
+return false;
+dr = XCNEW (struct data_reference);
+op0 = gimple_assign_lhs (stmt);
+DR_STMT (dr) = stmt;
+DR_REF (dr) = op0;
+res = dr_analyze_innermost (dr)
+&& stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0));
+free_data_ref (dr);
+return res;
+}
+/* Initialize STMTS with all the statements of LOOP that contain a
+store to memory of the form "A[i] = 0".  */
+void
+stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
+{
+unsigned int i;
+basic_block bb;
+gimple_stmt_iterator si;
+gimple stmt;
+basic_block *bbs = get_loop_body_in_dom_order (loop);
+for (i = 0; i < loop->num_nodes; i++)
+for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+if ((stmt = gsi_stmt (si))
+	  && stmt_with_adjacent_zero_store_dr_p (stmt))
+	VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
 free (bbs);
 }
 /* For a data reference REF, return the declaration of its base
 data_ref_loc *ref1, *ref2;
 get_references_in_stmt (s1, &refs1);
 get_references_in_stmt (s2, &refs2);
-for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++)
+FOR_EACH_VEC_ELT (data_ref_loc, refs1, i, ref1)
 {
 tree base1 = ref_base_address (s1, ref1);
 if (base1)
-	for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
+	FOR_EACH_VEC_ELT (data_ref_loc, refs2, j, ref2)
 	  if (base1 == ref_base_address (s2, ref2))
 	    {
 	      res = true;
 	      goto end;
 	    }
 data_ref_loc *ref;
 hashval_t res = 0;
 get_references_in_stmt (stmt, &refs);
-for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++)
+FOR_EACH_VEC_ELT (data_ref_loc, refs, i, ref)
 if (!ref->is_read)
 {
 	res = htab_hash_pointer (ref_base_address (stmt, ref));
 	break;
 }
 {
 int i;
 VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
 tree lambda_parameter;
-for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++)
+FOR_EACH_VEC_ELT (tree, lambda_parameters, i, lambda_parameter)
 if (lambda_parameter == parameter)
 return i + AM_NB_INDUCTION_VARS (access_matrix);
 return -1;
 }

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-data-ref.c @ 67:f6334be47118