--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/tree-data-ref.c	Fri Jul 17 14:47:48 2009 +0900
@@ -0,0 +1,5123 @@
+/* Data references and dependences detectors.
+   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+   Free Software Foundation, Inc.
+   Contributed by Sebastian Pop <pop@cri.ensmp.fr>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* This pass walks a given loop structure searching for array
+   references.  The information about the array accesses is recorded
+   in DATA_REFERENCE structures. 
+   
+   The basic test for determining the dependences is: 
+   given two access functions chrec1 and chrec2 to a same array, and 
+   x and y two vectors from the iteration domain, the same element of 
+   the array is accessed twice at iterations x and y if and only if:
+   |             chrec1 (x) == chrec2 (y).
+   
+   The goals of this analysis are:
+   
+   - to determine the independence: the relation between two
+     independent accesses is qualified with the chrec_known (this
+     information allows a loop parallelization),
+     
+   - when two data references access the same data, to qualify the
+     dependence relation with classic dependence representations:
+     
+       - distance vectors
+       - direction vectors
+       - loop carried level dependence
+       - polyhedron dependence
+     or with the chains of recurrences based representation,
+     
+   - to define a knowledge base for storing the data dependence 
+     information,
+     
+   - to define an interface to access this data.
+   
+   
+   Definitions:
+   
+   - subscript: given two array accesses a subscript is the tuple
+   composed of the access functions for a given dimension.  Example:
+   Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
+   (f1, g1), (f2, g2), (f3, g3).
+
+   - Diophantine equation: an equation whose coefficients and
+   solutions are integer constants, for example the equation 
+   |   3*x + 2*y = 1
+   has an integer solution x = 1 and y = -1.
+     
+   References:
+   
+   - "Advanced Compilation for High Performance Computing" by Randy
+   Allen and Ken Kennedy.
+   http://citeseer.ist.psu.edu/goff91practical.html 
+   
+   - "Loop Transformations for Restructuring Compilers - The Foundations" 
+   by Utpal Banerjee.
+
+   
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "ggc.h"
+#include "tree.h"
+
+/* These RTL headers are needed for basic-block.h.  */
+#include "rtl.h"
+#include "basic-block.h"
+#include "diagnostic.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"
+
+static struct datadep_stats
+{
+  int num_dependence_tests;
+  int num_dependence_dependent;
+  int num_dependence_independent;
+  int num_dependence_undetermined;
+
+  int num_subscript_tests;
+  int num_subscript_undetermined;
+  int num_same_subscript_function;
+
+  int num_ziv;
+  int num_ziv_independent;
+  int num_ziv_dependent;
+  int num_ziv_unimplemented;
+
+  int num_siv;
+  int num_siv_independent;
+  int num_siv_dependent;
+  int num_siv_unimplemented;
+
+  int num_miv;
+  int num_miv_independent;
+  int num_miv_dependent;
+  int num_miv_unimplemented;
+} dependence_stats;
+
+static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
+					   struct data_reference *,
+					   struct data_reference *,
+					   struct loop *);
+/* Returns true iff A divides B.  */
+
+static inline bool 
+tree_fold_divides_p (const_tree a, const_tree b)
+{
+  gcc_assert (TREE_CODE (a) == INTEGER_CST);
+  gcc_assert (TREE_CODE (b) == INTEGER_CST);
+  return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
+}
+
+/* Returns true iff A divides B.  */
+
+static inline bool 
+int_divides_p (int a, int b)
+{
+  return ((b % a) == 0);
+}
+
+
+
+/* Dump into FILE all the data references from DATAREFS.  */ 
+
+void 
+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++)
+    dump_data_reference (file, dr);
+}
+
+/* Dump to STDERR all the dependence relations from DDRS.  */ 
+
+void 
+debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
+{
+  dump_data_dependence_relations (stderr, ddrs);
+}
+
+/* Dump into FILE all the dependence relations from DDRS.  */ 
+
+void 
+dump_data_dependence_relations (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++)
+    dump_data_dependence_relation (file, ddr);
+}
+
+/* Dump function for a DATA_REFERENCE structure.  */
+
+void 
+dump_data_reference (FILE *outf, 
+		     struct data_reference *dr)
+{
+  unsigned int i;
+  
+  fprintf (outf, "(Data Ref: \n  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);
+  
+  for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
+    {
+      fprintf (outf, "  Access function %d: ", i);
+      print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
+    }
+  fprintf (outf, ")\n");
+}
+
+/* Dumps the affine function described by FN to the file OUTF.  */
+
+static void
+dump_affine_function (FILE *outf, affine_fn fn)
+{
+  unsigned i;
+  tree coef;
+
+  print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
+  for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
+    {
+      fprintf (outf, " + ");
+      print_generic_expr (outf, coef, TDF_SLIM);
+      fprintf (outf, " * x_%u", i);
+    }
+}
+
+/* Dumps the conflict function CF to the file OUTF.  */
+
+static void
+dump_conflict_function (FILE *outf, conflict_function *cf)
+{
+  unsigned i;
+
+  if (cf->n == NO_DEPENDENCE)
+    fprintf (outf, "no dependence\n");
+  else if (cf->n == NOT_KNOWN)
+    fprintf (outf, "not known\n");
+  else
+    {
+      for (i = 0; i < cf->n; i++)
+	{
+	  fprintf (outf, "[");
+	  dump_affine_function (outf, cf->fns[i]);
+	  fprintf (outf, "]\n");
+	}
+    }
+}
+
+/* Dump function for a SUBSCRIPT structure.  */
+
+void 
+dump_subscript (FILE *outf, struct subscript *subscript)
+{
+  conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
+
+  fprintf (outf, "\n (subscript \n");
+  fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
+  dump_conflict_function (outf, cf);
+  if (CF_NONTRIVIAL_P (cf))
+    {
+      tree last_iteration = SUB_LAST_CONFLICT (subscript);
+      fprintf (outf, "  last_conflict: ");
+      print_generic_stmt (outf, last_iteration, 0);
+    }
+	  
+  cf = SUB_CONFLICTS_IN_B (subscript);
+  fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
+  dump_conflict_function (outf, cf);
+  if (CF_NONTRIVIAL_P (cf))
+    {
+      tree last_iteration = SUB_LAST_CONFLICT (subscript);
+      fprintf (outf, "  last_conflict: ");
+      print_generic_stmt (outf, last_iteration, 0);
+    }
+
+  fprintf (outf, "  (Subscript distance: ");
+  print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
+  fprintf (outf, "  )\n");
+  fprintf (outf, " )\n");
+}
+
+/* Print the classic direction vector DIRV to OUTF.  */
+
+void
+print_direction_vector (FILE *outf,
+			lambda_vector dirv,
+			int length)
+{
+  int eq;
+
+  for (eq = 0; eq < length; eq++)
+    {
+      enum data_dependence_direction dir = dirv[eq];
+
+      switch (dir)
+	{
+	case dir_positive:
+	  fprintf (outf, "    +");
+	  break;
+	case dir_negative:
+	  fprintf (outf, "    -");
+	  break;
+	case dir_equal:
+	  fprintf (outf, "    =");
+	  break;
+	case dir_positive_or_equal:
+	  fprintf (outf, "   +=");
+	  break;
+	case dir_positive_or_negative:
+	  fprintf (outf, "   +-");
+	  break;
+	case dir_negative_or_equal:
+	  fprintf (outf, "   -=");
+	  break;
+	case dir_star:
+	  fprintf (outf, "    *");
+	  break;
+	default:
+	  fprintf (outf, "indep");
+	  break;
+	}
+    }
+  fprintf (outf, "\n");
+}
+
+/* Print a vector of direction vectors.  */
+
+void
+print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
+		   int length)
+{
+  unsigned j;
+  lambda_vector v;
+
+  for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
+    print_direction_vector (outf, v, length);
+}
+
+/* Print a vector of distance vectors.  */
+
+void
+print_dist_vectors  (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
+		     int length)
+{
+  unsigned j;
+  lambda_vector v;
+
+  for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
+    print_lambda_vector (outf, v, length);
+}
+
+/* Debug version.  */
+
+void 
+debug_data_dependence_relation (struct data_dependence_relation *ddr)
+{
+  dump_data_dependence_relation (stderr, ddr);
+}
+
+/* Dump function for a DATA_DEPENDENCE_RELATION structure.  */
+
+void 
+dump_data_dependence_relation (FILE *outf, 
+			       struct data_dependence_relation *ddr)
+{
+  struct data_reference *dra, *drb;
+
+  fprintf (outf, "(Data Dep: \n");
+
+  if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+    {
+      fprintf (outf, "    (don't know)\n)\n");
+      return;
+    }
+
+  dra = DDR_A (ddr);
+  drb = DDR_B (ddr);
+  dump_data_reference (outf, dra);
+  dump_data_reference (outf, drb);
+
+  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+    fprintf (outf, "    (no dependence)\n");
+  
+  else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+    {
+      unsigned int i;
+      struct loop *loopi;
+
+      for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+	{
+	  fprintf (outf, "  access_fn_A: ");
+	  print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
+	  fprintf (outf, "  access_fn_B: ");
+	  print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
+	  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++)
+	fprintf (outf, "%d ", loopi->num);
+      fprintf (outf, ")\n");
+
+      for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+	{
+	  fprintf (outf, "  distance_vector: ");
+	  print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
+			       DDR_NB_LOOPS (ddr));
+	}
+
+      for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
+	{
+	  fprintf (outf, "  direction_vector: ");
+	  print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
+				  DDR_NB_LOOPS (ddr));
+	}
+    }
+
+  fprintf (outf, ")\n");
+}
+
+/* Dump function for a DATA_DEPENDENCE_DIRECTION structure.  */
+
+void
+dump_data_dependence_direction (FILE *file, 
+				enum data_dependence_direction dir)
+{
+  switch (dir)
+    {
+    case dir_positive: 
+      fprintf (file, "+");
+      break;
+      
+    case dir_negative:
+      fprintf (file, "-");
+      break;
+      
+    case dir_equal:
+      fprintf (file, "=");
+      break;
+      
+    case dir_positive_or_negative:
+      fprintf (file, "+-");
+      break;
+      
+    case dir_positive_or_equal: 
+      fprintf (file, "+=");
+      break;
+      
+    case dir_negative_or_equal: 
+      fprintf (file, "-=");
+      break;
+      
+    case dir_star: 
+      fprintf (file, "*"); 
+      break;
+      
+    default: 
+      break;
+    }
+}
+
+/* Dumps the distance and direction vectors in FILE.  DDRS contains
+   the dependence relations, and VECT_SIZE is the size of the
+   dependence vectors, or in other words the number of loops in the
+   considered nest.  */
+
+void 
+dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
+{
+  unsigned int i, j;
+  struct data_dependence_relation *ddr;
+  lambda_vector v;
+
+  for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+    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++)
+	  {
+	    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++)
+	  {
+	    fprintf (file, "DIRECTION_V (");
+	    print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
+	    fprintf (file, ")\n");
+	  }
+      }
+
+  fprintf (file, "\n\n");
+}
+
+/* Dumps the data dependence relations DDRS in FILE.  */
+
+void 
+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++)
+    dump_data_dependence_relation (file, ddr);
+
+  fprintf (file, "\n\n");
+}
+
+/* Helper function for split_constant_offset.  Expresses OP0 CODE OP1
+   (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
+   constant of type ssizetype, and returns true.  If we cannot do this
+   with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
+   is returned.  */
+
+static bool
+split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
+			 tree *var, tree *off)
+{
+  tree var0, var1;
+  tree off0, off1;
+  enum tree_code ocode = code;
+
+  *var = NULL_TREE;
+  *off = NULL_TREE;
+
+  switch (code)
+    {
+    case INTEGER_CST:
+      *var = build_int_cst (type, 0);
+      *off = fold_convert (ssizetype, op0);
+      return true;
+
+    case POINTER_PLUS_EXPR:
+      ocode = PLUS_EXPR;
+      /* FALLTHROUGH */
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+      split_constant_offset (op0, &var0, &off0);
+      split_constant_offset (op1, &var1, &off1);
+      *var = fold_build2 (code, type, var0, var1);
+      *off = size_binop (ocode, off0, off1);
+      return true;
+
+    case MULT_EXPR:
+      if (TREE_CODE (op1) != INTEGER_CST)
+	return false;
+
+      split_constant_offset (op0, &var0, &off0);
+      *var = fold_build2 (MULT_EXPR, type, var0, op1);
+      *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
+      return true;
+
+    case ADDR_EXPR:
+      {
+	tree base, poffset;
+	HOST_WIDE_INT pbitsize, pbitpos;
+	enum machine_mode pmode;
+	int punsignedp, pvolatilep;
+
+	op0 = TREE_OPERAND (op0, 0);
+	if (!handled_component_p (op0))
+	  return false;
+
+	base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
+				    &pmode, &punsignedp, &pvolatilep, false);
+
+	if (pbitpos % BITS_PER_UNIT != 0)
+	  return false;
+	base = build_fold_addr_expr (base);
+	off0 = ssize_int (pbitpos / BITS_PER_UNIT);
+
+	if (poffset)
+	  {
+	    split_constant_offset (poffset, &poffset, &off1);
+	    off0 = size_binop (PLUS_EXPR, off0, off1);
+	    if (POINTER_TYPE_P (TREE_TYPE (base)))
+	      base = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (base),
+				  base, fold_convert (sizetype, poffset));
+	    else
+	      base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
+				  fold_convert (TREE_TYPE (base), poffset));
+	  }
+
+	var0 = fold_convert (type, base);
+
+	/* If variable length types are involved, punt, otherwise casts
+	   might be converted into ARRAY_REFs in gimplify_conversion.
+	   To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
+	   possibly no longer appears in current GIMPLE, might resurface.
+	   This perhaps could run
+	   if (CONVERT_EXPR_P (var0))
+	     {
+	       gimplify_conversion (&var0);
+	       // Attempt to fill in any within var0 found ARRAY_REF's
+	       // element size from corresponding op embedded ARRAY_REF,
+	       // if unsuccessful, just punt.
+	     }  */
+	while (POINTER_TYPE_P (type))
+	  type = TREE_TYPE (type);
+	if (int_size_in_bytes (type) < 0)
+	  return false;
+
+	*var = var0;
+	*off = off0;
+	return true;
+      }
+
+    case SSA_NAME:
+      {
+	gimple def_stmt = SSA_NAME_DEF_STMT (op0);
+	enum tree_code subcode;
+
+	if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
+	  return false;
+
+	var0 = gimple_assign_rhs1 (def_stmt);
+	subcode = gimple_assign_rhs_code (def_stmt);
+	var1 = gimple_assign_rhs2 (def_stmt);
+
+	return split_constant_offset_1 (type, var0, subcode, var1, var, off);
+      }
+
+    default:
+      return false;
+    }
+}
+
+/* Expresses EXP as VAR + OFF, where off is a constant.  The type of OFF
+   will be ssizetype.  */
+
+void
+split_constant_offset (tree exp, tree *var, tree *off)
+{
+  tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
+  enum tree_code code;
+
+  *var = exp;
+  *off = ssize_int (0);
+  STRIP_NOPS (exp);
+
+  if (automatically_generated_chrec_p (exp))
+    return;
+
+  otype = TREE_TYPE (exp);
+  code = TREE_CODE (exp);
+  extract_ops_from_tree (exp, &code, &op0, &op1);
+  if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
+    {
+      *var = fold_convert (type, e);
+      *off = o;
+    }
+}
+
+/* Returns the address ADDR of an object in a canonical shape (without nop
+   casts, and with type of pointer to the object).  */
+
+static tree
+canonicalize_base_object_address (tree addr)
+{
+  tree orig = addr;
+
+  STRIP_NOPS (addr);
+
+  /* The base address may be obtained by casting from integer, in that case
+     keep the cast.  */
+  if (!POINTER_TYPE_P (TREE_TYPE (addr)))
+    return orig;
+
+  if (TREE_CODE (addr) != ADDR_EXPR)
+    return addr;
+
+  return build_fold_addr_expr (TREE_OPERAND (addr, 0));
+}
+
+/* Analyzes the behavior of the memory reference DR in the innermost loop that
+   contains it. Returns true if analysis succeed or false otherwise.  */
+
+bool
+dr_analyze_innermost (struct data_reference *dr)
+{
+  gimple stmt = DR_STMT (dr);
+  struct loop *loop = loop_containing_stmt (stmt);
+  tree ref = DR_REF (dr);
+  HOST_WIDE_INT pbitsize, pbitpos;
+  tree base, poffset;
+  enum machine_mode pmode;
+  int punsignedp, pvolatilep;
+  affine_iv base_iv, offset_iv;
+  tree init, dinit, step;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "analyze_innermost: ");
+
+  base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
+			      &pmode, &punsignedp, &pvolatilep, false);
+  gcc_assert (base != NULL_TREE);
+
+  if (pbitpos % BITS_PER_UNIT != 0)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "failed: bit offset alignment.\n");
+      return false;
+    }
+
+  base = build_fold_addr_expr (base);
+  if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv, false))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "failed: evolution of base is not affine.\n");
+      return false;
+    }
+  if (!poffset)
+    {
+      offset_iv.base = ssize_int (0);
+      offset_iv.step = ssize_int (0);
+    }
+  else if (!simple_iv (loop, loop_containing_stmt (stmt),
+		       poffset, &offset_iv, false))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "failed: evolution of offset is not affine.\n");
+      return false;
+    }
+
+  init = ssize_int (pbitpos / BITS_PER_UNIT);
+  split_constant_offset (base_iv.base, &base_iv.base, &dinit);
+  init =  size_binop (PLUS_EXPR, init, dinit);
+  split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
+  init =  size_binop (PLUS_EXPR, init, dinit);
+
+  step = size_binop (PLUS_EXPR,
+		     fold_convert (ssizetype, base_iv.step),
+		     fold_convert (ssizetype, offset_iv.step));
+
+  DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
+
+  DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
+  DR_INIT (dr) = init;
+  DR_STEP (dr) = step;
+
+  DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "success.\n");
+
+  return true;
+}
+
+/* Determines the base object and the list of indices of memory reference
+   DR, analyzed in loop nest NEST.  */
+
+static void
+dr_analyze_indices (struct data_reference *dr, struct loop *nest)
+{
+  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;
+  basic_block before_loop = block_before_loop (nest);
+
+  while (handled_component_p (aref))
+    {
+      if (TREE_CODE (aref) == ARRAY_REF)
+	{
+	  op = TREE_OPERAND (aref, 1);
+	  access_fn = analyze_scalar_evolution (loop, op);
+	  access_fn = instantiate_scev (before_loop, loop, access_fn);
+	  VEC_safe_push (tree, heap, access_fns, access_fn);
+
+	  TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
+	}
+      
+      aref = TREE_OPERAND (aref, 0);
+    }
+
+  if (INDIRECT_REF_P (aref))
+    {
+      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);
+      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);
+    }
+
+  DR_BASE_OBJECT (dr) = ref;
+  DR_ACCESS_FNS (dr) = access_fns;
+}
+
+/* Extracts the alias analysis information from the memory reference DR.  */
+
+static void
+dr_analyze_alias (struct data_reference *dr)
+{
+  gimple stmt = DR_STMT (dr);
+  tree ref = DR_REF (dr);
+  tree base = get_base_address (ref), addr, smt = NULL_TREE;
+  ssa_op_iter it;
+  tree op;
+  bitmap vops;
+
+  if (DECL_P (base))
+    smt = base;
+  else if (INDIRECT_REF_P (base))
+    {
+      addr = TREE_OPERAND (base, 0);
+      if (TREE_CODE (addr) == SSA_NAME)
+	{
+	  smt = symbol_mem_tag (SSA_NAME_VAR (addr));
+	  DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
+	}
+    }
+
+  DR_SYMBOL_TAG (dr) = smt;
+
+  vops = BITMAP_ALLOC (NULL);
+  FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
+    {
+      bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
+    }
+
+  DR_VOPS (dr) = vops;
+}
+
+/* Returns true if the address of DR is invariant.  */
+
+static bool
+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++)
+    if (tree_contains_chrecs (idx, NULL))
+      return false;
+
+  return true;
+}
+
+/* Frees data reference DR.  */
+
+void
+free_data_ref (data_reference_p dr)
+{
+  BITMAP_FREE (DR_VOPS (dr));
+  VEC_free (tree, heap, DR_ACCESS_FNS (dr));
+  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
+   loop nest in that the reference should be analyzed.  */
+
+struct data_reference *
+create_data_ref (struct loop *nest, tree memref, gimple stmt, bool is_read)
+{
+  struct data_reference *dr;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Creating dr for ");
+      print_generic_expr (dump_file, memref, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  dr = XCNEW (struct data_reference);
+  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_alias (dr);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "\tbase_address: ");
+      print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
+      fprintf (dump_file, "\n\toffset from base address: ");
+      print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
+      fprintf (dump_file, "\n\tconstant offset from base address: ");
+      print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
+      fprintf (dump_file, "\n\tstep: ");
+      print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
+      fprintf (dump_file, "\n\taligned to: ");
+      print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
+      fprintf (dump_file, "\n\tbase_object: ");
+      print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
+      fprintf (dump_file, "\n\tsymbol tag: ");
+      print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  return dr;  
+}
+
+/* Returns true if FNA == FNB.  */
+
+static bool
+affine_function_equal_p (affine_fn fna, affine_fn fnb)
+{
+  unsigned i, n = VEC_length (tree, fna);
+
+  if (n != VEC_length (tree, fnb))
+    return false;
+
+  for (i = 0; i < n; i++)
+    if (!operand_equal_p (VEC_index (tree, fna, i),
+			  VEC_index (tree, fnb, i), 0))
+      return false;
+
+  return true;
+}
+
+/* If all the functions in CF are the same, returns one of them,
+   otherwise returns NULL.  */
+
+static affine_fn
+common_affine_function (conflict_function *cf)
+{
+  unsigned i;
+  affine_fn comm;
+
+  if (!CF_NONTRIVIAL_P (cf))
+    return NULL;
+
+  comm = cf->fns[0];
+
+  for (i = 1; i < cf->n; i++)
+    if (!affine_function_equal_p (comm, cf->fns[i]))
+      return NULL;
+
+  return comm;
+}
+
+/* Returns the base of the affine function FN.  */
+
+static tree
+affine_function_base (affine_fn fn)
+{
+  return VEC_index (tree, fn, 0);
+}
+
+/* Returns true if FN is a constant.  */
+
+static bool
+affine_function_constant_p (affine_fn fn)
+{
+  unsigned i;
+  tree coef;
+
+  for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
+    if (!integer_zerop (coef))
+      return false;
+
+  return true;
+}
+
+/* Returns true if FN is the zero constant function.  */
+
+static bool
+affine_function_zero_p (affine_fn fn)
+{
+  return (integer_zerop (affine_function_base (fn))
+	  && affine_function_constant_p (fn));
+}
+
+/* Returns a signed integer type with the largest precision from TA
+   and TB.  */
+
+static tree
+signed_type_for_types (tree ta, tree tb)
+{
+  if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
+    return signed_type_for (ta);
+  else
+    return signed_type_for (tb);
+}
+
+/* Applies operation OP on affine functions FNA and FNB, and returns the
+   result.  */
+
+static affine_fn
+affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
+{
+  unsigned i, n, m;
+  affine_fn ret;
+  tree coef;
+
+  if (VEC_length (tree, fnb) > VEC_length (tree, fna))
+    {
+      n = VEC_length (tree, fna);
+      m = VEC_length (tree, fnb);
+    }
+  else
+    {
+      n = VEC_length (tree, fnb);
+      m = VEC_length (tree, fna);
+    }
+
+  ret = VEC_alloc (tree, heap, m);
+  for (i = 0; i < n; i++)
+    {
+      tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
+					 TREE_TYPE (VEC_index (tree, fnb, i)));
+
+      VEC_quick_push (tree, ret,
+		      fold_build2 (op, type,
+				   VEC_index (tree, fna, i), 
+				   VEC_index (tree, fnb, i)));
+    }
+
+  for (; VEC_iterate (tree, fna, i, coef); i++)
+    VEC_quick_push (tree, ret,
+		    fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
+				 coef, integer_zero_node));
+  for (; VEC_iterate (tree, fnb, i, coef); i++)
+    VEC_quick_push (tree, ret,
+		    fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
+				 integer_zero_node, coef));
+
+  return ret;
+}
+
+/* Returns the sum of affine functions FNA and FNB.  */
+
+static affine_fn
+affine_fn_plus (affine_fn fna, affine_fn fnb)
+{
+  return affine_fn_op (PLUS_EXPR, fna, fnb);
+}
+
+/* Returns the difference of affine functions FNA and FNB.  */
+
+static affine_fn
+affine_fn_minus (affine_fn fna, affine_fn fnb)
+{
+  return affine_fn_op (MINUS_EXPR, fna, fnb);
+}
+
+/* Frees affine function FN.  */
+
+static void
+affine_fn_free (affine_fn fn)
+{
+  VEC_free (tree, heap, fn);
+}
+
+/* Determine for each subscript in the data dependence relation DDR
+   the distance.  */
+
+static void
+compute_subscript_distance (struct data_dependence_relation *ddr)
+{
+  conflict_function *cf_a, *cf_b;
+  affine_fn fn_a, fn_b, diff;
+
+  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+    {
+      unsigned int i;
+      
+      for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+ 	{
+ 	  struct subscript *subscript;
+ 	  
+ 	  subscript = DDR_SUBSCRIPT (ddr, i);
+ 	  cf_a = SUB_CONFLICTS_IN_A (subscript);
+ 	  cf_b = SUB_CONFLICTS_IN_B (subscript);
+
+	  fn_a = common_affine_function (cf_a);
+	  fn_b = common_affine_function (cf_b);
+	  if (!fn_a || !fn_b)
+	    {
+	      SUB_DISTANCE (subscript) = chrec_dont_know;
+	      return;
+	    }
+	  diff = affine_fn_minus (fn_a, fn_b);
+ 	  
+ 	  if (affine_function_constant_p (diff))
+ 	    SUB_DISTANCE (subscript) = affine_function_base (diff);
+ 	  else
+ 	    SUB_DISTANCE (subscript) = chrec_dont_know;
+
+	  affine_fn_free (diff);
+ 	}
+    }
+}
+
+/* Returns the conflict function for "unknown".  */
+
+static conflict_function *
+conflict_fn_not_known (void)
+{
+  conflict_function *fn = XCNEW (conflict_function);
+  fn->n = NOT_KNOWN;
+
+  return fn;
+}
+
+/* Returns the conflict function for "independent".  */
+
+static conflict_function *
+conflict_fn_no_dependence (void)
+{
+  conflict_function *fn = XCNEW (conflict_function);
+  fn->n = NO_DEPENDENCE;
+
+  return fn;
+}
+
+/* Returns true if the address of OBJ is invariant in LOOP.  */
+
+static bool
+object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
+{
+  while (handled_component_p (obj))
+    {
+      if (TREE_CODE (obj) == ARRAY_REF)
+	{
+	  /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
+	     need to check the stride and the lower bound of the reference.  */
+	  if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
+						      loop->num)
+	      || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
+							 loop->num))
+	    return false;
+	}
+      else if (TREE_CODE (obj) == COMPONENT_REF)
+	{
+	  if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
+						      loop->num))
+	    return false;
+	}
+      obj = TREE_OPERAND (obj, 0);
+    }
+
+  if (!INDIRECT_REF_P (obj))
+    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);
+  const_tree addr_b = DR_BASE_ADDRESS (b);
+  const_tree type_a, type_b;
+  const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
+
+  /* If the sets of virtual operands are disjoint, the memory references do not
+     alias.  */
+  if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
+    return false;
+
+  /* If the accessed objects are disjoint, the memory references do not
+     alias.  */
+  if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (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,
+     since currently we cannot distinguish between pointer and offset in pointer
+     arithmetics).  */
+  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
+   B.  NB_LOOPS is the number of loops surrounding the references: the
+   size of the classic distance/direction vectors.  */
+
+static struct data_dependence_relation *
+initialize_data_dependence_relation (struct data_reference *a, 
+				     struct data_reference *b,
+ 				     VEC (loop_p, heap) *loop_nest)
+{
+  struct data_dependence_relation *res;
+  unsigned int i;
+  
+  res = XNEW (struct data_dependence_relation);
+  DDR_A (res) = a;
+  DDR_B (res) = b;
+  DDR_LOOP_NEST (res) = NULL;
+  DDR_REVERSED_P (res) = false;
+  DDR_SUBSCRIPTS (res) = NULL;
+  DDR_DIR_VECTS (res) = NULL;
+  DDR_DIST_VECTS (res) = NULL;
+
+  if (a == NULL || b == NULL)
+    {
+      DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
+      return res;
+    }   
+
+  /* If the data references do not alias, then they are independent.  */
+  if (!dr_may_alias_p (a, b))
+    {
+      DDR_ARE_DEPENDENT (res) = chrec_known;    
+      return res;
+    }
+
+  /* When the references are exactly the same, don't spend time doing
+     the data dependence tests, just initialize the ddr and return.  */
+  if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
+    {
+      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;
+      DDR_INNER_LOOP (res) = 0;
+      DDR_SELF_REFERENCE (res) = true;
+      compute_self_dependence (res);
+      return res;
+    }
+
+  /* If the references do not access the same object, we do not know
+     whether they alias or not.  */
+  if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
+    {
+      DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
+      return res;
+    }
+
+  /* If the base of the object is not invariant in the loop nest, we cannot
+     analyze it.  TODO -- in fact, it would suffice to record that there may
+     be arbitrary dependences in the loops where the base object varies.  */
+  if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
+					   DR_BASE_OBJECT (a)))
+    {
+      DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
+      return res;
+    }
+
+  gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
+
+  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;
+  DDR_INNER_LOOP (res) = 0;
+  DDR_SELF_REFERENCE (res) = false;
+
+  for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
+    {
+      struct subscript *subscript;
+	  
+      subscript = XNEW (struct subscript);
+      SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
+      SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
+      SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
+      SUB_DISTANCE (subscript) = chrec_dont_know;
+      VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
+    }
+
+  return res;
+}
+
+/* Frees memory used by the conflict function F.  */
+
+static void
+free_conflict_function (conflict_function *f)
+{
+  unsigned i;
+
+  if (CF_NONTRIVIAL_P (f))
+    {
+      for (i = 0; i < f->n; i++)
+	affine_fn_free (f->fns[i]);
+    }
+  free (f);
+}
+
+/* Frees memory used by SUBSCRIPTS.  */
+
+static void
+free_subscripts (VEC (subscript_p, heap) *subscripts)
+{
+  unsigned i;
+  subscript_p s;
+
+  for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
+    {
+      free_conflict_function (s->conflicting_iterations_in_a);
+      free_conflict_function (s->conflicting_iterations_in_b);
+      free (s);
+    }
+  VEC_free (subscript_p, heap, subscripts);
+}
+
+/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
+   description.  */
+
+static inline void
+finalize_ddr_dependent (struct data_dependence_relation *ddr, 
+			tree chrec)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "(dependence classified: ");
+      print_generic_expr (dump_file, chrec, 0);
+      fprintf (dump_file, ")\n");
+    }
+
+  DDR_ARE_DEPENDENT (ddr) = chrec;  
+  free_subscripts (DDR_SUBSCRIPTS (ddr));
+  DDR_SUBSCRIPTS (ddr) = NULL;
+}
+
+/* The dependence relation DDR cannot be represented by a distance
+   vector.  */
+
+static inline void
+non_affine_dependence_relation (struct data_dependence_relation *ddr)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
+
+  DDR_AFFINE_P (ddr) = false;
+}
+
+
+
+/* This section contains the classic Banerjee tests.  */
+
+/* Returns true iff CHREC_A and CHREC_B are not dependent on any index
+   variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
+
+static inline bool
+ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
+{
+  return (evolution_function_is_constant_p (chrec_a)
+	  && evolution_function_is_constant_p (chrec_b));
+}
+
+/* Returns true iff CHREC_A and CHREC_B are dependent on an index
+   variable, i.e., if the SIV (Single Index Variable) test is true.  */
+
+static bool
+siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
+{
+  if ((evolution_function_is_constant_p (chrec_a)
+       && evolution_function_is_univariate_p (chrec_b))
+      || (evolution_function_is_constant_p (chrec_b)
+	  && evolution_function_is_univariate_p (chrec_a)))
+    return true;
+  
+  if (evolution_function_is_univariate_p (chrec_a)
+      && evolution_function_is_univariate_p (chrec_b))
+    {
+      switch (TREE_CODE (chrec_a))
+	{
+	case POLYNOMIAL_CHREC:
+	  switch (TREE_CODE (chrec_b))
+	    {
+	    case POLYNOMIAL_CHREC:
+	      if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
+		return false;
+	      
+	    default:
+	      return true;
+	    }
+	  
+	default:
+	  return true;
+	}
+    }
+  
+  return false;
+}
+
+/* Creates a conflict function with N dimensions.  The affine functions
+   in each dimension follow.  */
+
+static conflict_function *
+conflict_fn (unsigned n, ...)
+{
+  unsigned i;
+  conflict_function *ret = XCNEW (conflict_function);
+  va_list ap;
+
+  gcc_assert (0 < n && n <= MAX_DIM);
+  va_start(ap, n);
+		       
+  ret->n = n;
+  for (i = 0; i < n; i++)
+    ret->fns[i] = va_arg (ap, affine_fn);
+  va_end(ap);
+
+  return ret;
+}
+
+/* Returns constant affine function with value CST.  */
+
+static affine_fn
+affine_fn_cst (tree cst)
+{
+  affine_fn fn = VEC_alloc (tree, heap, 1);
+  VEC_quick_push (tree, fn, cst);
+  return fn;
+}
+
+/* Returns affine function with single variable, CST + COEF * x_DIM.  */
+
+static affine_fn
+affine_fn_univar (tree cst, unsigned dim, tree coef)
+{
+  affine_fn fn = VEC_alloc (tree, heap, dim + 1);
+  unsigned i;
+
+  gcc_assert (dim > 0);
+  VEC_quick_push (tree, fn, cst);
+  for (i = 1; i < dim; i++)
+    VEC_quick_push (tree, fn, integer_zero_node);
+  VEC_quick_push (tree, fn, coef);
+  return fn;
+}
+
+/* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
+   *OVERLAPS_B are initialized to the functions that describe the
+   relation between the elements accessed twice by CHREC_A and
+   CHREC_B.  For k >= 0, the following property is verified:
+
+   CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
+
+static void 
+analyze_ziv_subscript (tree chrec_a, 
+		       tree chrec_b, 
+		       conflict_function **overlaps_a,
+		       conflict_function **overlaps_b, 
+		       tree *last_conflicts)
+{
+  tree type, difference;
+  dependence_stats.num_ziv++;
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "(analyze_ziv_subscript \n");
+
+  type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+  chrec_a = chrec_convert (type, chrec_a, NULL);
+  chrec_b = chrec_convert (type, chrec_b, NULL);
+  difference = chrec_fold_minus (type, chrec_a, chrec_b);
+  
+  switch (TREE_CODE (difference))
+    {
+    case INTEGER_CST:
+      if (integer_zerop (difference))
+	{
+	  /* The difference is equal to zero: the accessed index
+	     overlaps for each iteration in the loop.  */
+	  *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+	  *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+	  *last_conflicts = chrec_dont_know;
+	  dependence_stats.num_ziv_dependent++;
+	}
+      else
+	{
+	  /* The accesses do not overlap.  */
+	  *overlaps_a = conflict_fn_no_dependence ();
+	  *overlaps_b = conflict_fn_no_dependence ();
+	  *last_conflicts = integer_zero_node;
+	  dependence_stats.num_ziv_independent++;
+	}
+      break;
+      
+    default:
+      /* We're not sure whether the indexes overlap.  For the moment, 
+	 conservatively answer "don't know".  */
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
+
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
+      *last_conflicts = chrec_dont_know;
+      dependence_stats.num_ziv_unimplemented++;
+      break;
+    }
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, ")\n");
+}
+
+/* Sets NIT to the estimated number of executions of the statements in
+   LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
+   large as the number of iterations.  If we have no reliable estimate,
+   the function returns false, otherwise returns true.  */
+
+bool
+estimated_loop_iterations (struct loop *loop, bool conservative,
+			   double_int *nit)
+{
+  estimate_numbers_of_iterations_loop (loop);
+  if (conservative)
+    {
+      if (!loop->any_upper_bound)
+	return false;
+
+      *nit = loop->nb_iterations_upper_bound;
+    }
+  else
+    {
+      if (!loop->any_estimate)
+	return false;
+
+      *nit = loop->nb_iterations_estimate;
+    }
+
+  return true;
+}
+
+/* Similar to estimated_loop_iterations, but returns the estimate only
+   if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
+   on the number of iterations of LOOP could not be derived, returns -1.  */
+
+HOST_WIDE_INT
+estimated_loop_iterations_int (struct loop *loop, bool conservative)
+{
+  double_int nit;
+  HOST_WIDE_INT hwi_nit;
+
+  if (!estimated_loop_iterations (loop, conservative, &nit))
+    return -1;
+
+  if (!double_int_fits_in_shwi_p (nit))
+    return -1;
+  hwi_nit = double_int_to_shwi (nit);
+
+  return hwi_nit < 0 ? -1 : hwi_nit;
+}
+    
+/* Similar to estimated_loop_iterations, but returns the estimate as a tree,
+   and only if it fits to the int type.  If this is not the case, or the
+   estimate on the number of iterations of LOOP could not be derived, returns
+   chrec_dont_know.  */
+
+static tree
+estimated_loop_iterations_tree (struct loop *loop, bool conservative)
+{
+  double_int nit;
+  tree type;
+
+  if (!estimated_loop_iterations (loop, conservative, &nit))
+    return chrec_dont_know;
+
+  type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
+  if (!double_int_fits_to_tree_p (type, nit))
+    return chrec_dont_know;
+
+  return double_int_to_tree (type, nit);
+}
+
+/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
+   constant, and CHREC_B is an affine function.  *OVERLAPS_A and
+   *OVERLAPS_B are initialized to the functions that describe the
+   relation between the elements accessed twice by CHREC_A and
+   CHREC_B.  For k >= 0, the following property is verified:
+
+   CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
+
+static void
+analyze_siv_subscript_cst_affine (tree chrec_a, 
+				  tree chrec_b,
+				  conflict_function **overlaps_a, 
+				  conflict_function **overlaps_b, 
+				  tree *last_conflicts)
+{
+  bool value0, value1, value2;
+  tree type, difference, tmp;
+
+  type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+  chrec_a = chrec_convert (type, chrec_a, NULL);
+  chrec_b = chrec_convert (type, chrec_b, NULL);
+  difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
+  
+  if (!chrec_is_positive (initial_condition (difference), &value0))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "siv test failed: chrec is not positive.\n"); 
+
+      dependence_stats.num_siv_unimplemented++;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
+      *last_conflicts = chrec_dont_know;
+      return;
+    }
+  else
+    {
+      if (value0 == false)
+	{
+	  if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "siv test failed: chrec not positive.\n");
+
+	      *overlaps_a = conflict_fn_not_known ();
+	      *overlaps_b = conflict_fn_not_known ();      
+	      *last_conflicts = chrec_dont_know;
+	      dependence_stats.num_siv_unimplemented++;
+	      return;
+	    }
+	  else
+	    {
+	      if (value1 == true)
+		{
+		  /* Example:  
+		     chrec_a = 12
+		     chrec_b = {10, +, 1}
+		  */
+		  
+		  if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
+		    {
+		      HOST_WIDE_INT numiter;
+		      struct loop *loop = get_chrec_loop (chrec_b);
+
+		      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+		      tmp = fold_build2 (EXACT_DIV_EXPR, type,
+					 fold_build1 (ABS_EXPR, type, difference),
+					 CHREC_RIGHT (chrec_b));
+		      *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
+		      *last_conflicts = integer_one_node;
+		      
+
+		      /* Perform weak-zero siv test to see if overlap is
+			 outside the loop bounds.  */
+		      numiter = estimated_loop_iterations_int (loop, false);
+
+		      if (numiter >= 0
+			  && compare_tree_int (tmp, numiter) > 0)
+			{
+			  free_conflict_function (*overlaps_a);
+			  free_conflict_function (*overlaps_b);
+			  *overlaps_a = conflict_fn_no_dependence ();
+			  *overlaps_b = conflict_fn_no_dependence ();
+			  *last_conflicts = integer_zero_node;
+			  dependence_stats.num_siv_independent++;
+			  return;
+			}		
+		      dependence_stats.num_siv_dependent++;
+		      return;
+		    }
+		  
+		  /* When the step does not divide the difference, there are
+		     no overlaps.  */
+		  else
+		    {
+		      *overlaps_a = conflict_fn_no_dependence ();
+		      *overlaps_b = conflict_fn_no_dependence ();      
+		      *last_conflicts = integer_zero_node;
+		      dependence_stats.num_siv_independent++;
+		      return;
+		    }
+		}
+	      
+	      else
+		{
+		  /* Example:  
+		     chrec_a = 12
+		     chrec_b = {10, +, -1}
+		     
+		     In this case, chrec_a will not overlap with chrec_b.  */
+		  *overlaps_a = conflict_fn_no_dependence ();
+		  *overlaps_b = conflict_fn_no_dependence ();
+		  *last_conflicts = integer_zero_node;
+		  dependence_stats.num_siv_independent++;
+		  return;
+		}
+	    }
+	}
+      else 
+	{
+	  if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "siv test failed: chrec not positive.\n");
+
+	      *overlaps_a = conflict_fn_not_known ();
+	      *overlaps_b = conflict_fn_not_known ();      
+	      *last_conflicts = chrec_dont_know;
+	      dependence_stats.num_siv_unimplemented++;
+	      return;
+	    }
+	  else
+	    {
+	      if (value2 == false)
+		{
+		  /* Example:  
+		     chrec_a = 3
+		     chrec_b = {10, +, -1}
+		  */
+		  if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
+		    {
+		      HOST_WIDE_INT numiter;
+		      struct loop *loop = get_chrec_loop (chrec_b);
+
+		      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+		      tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
+					 CHREC_RIGHT (chrec_b));
+		      *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
+		      *last_conflicts = integer_one_node;
+
+		      /* Perform weak-zero siv test to see if overlap is
+			 outside the loop bounds.  */
+		      numiter = estimated_loop_iterations_int (loop, false);
+
+		      if (numiter >= 0
+			  && compare_tree_int (tmp, numiter) > 0)
+			{
+			  free_conflict_function (*overlaps_a);
+			  free_conflict_function (*overlaps_b);
+			  *overlaps_a = conflict_fn_no_dependence ();
+			  *overlaps_b = conflict_fn_no_dependence ();
+			  *last_conflicts = integer_zero_node;
+			  dependence_stats.num_siv_independent++;
+			  return;
+			}	
+		      dependence_stats.num_siv_dependent++;
+		      return;
+		    }
+		  
+		  /* When the step does not divide the difference, there
+		     are no overlaps.  */
+		  else
+		    {
+		      *overlaps_a = conflict_fn_no_dependence ();
+		      *overlaps_b = conflict_fn_no_dependence ();      
+		      *last_conflicts = integer_zero_node;
+		      dependence_stats.num_siv_independent++;
+		      return;
+		    }
+		}
+	      else
+		{
+		  /* Example:  
+		     chrec_a = 3  
+		     chrec_b = {4, +, 1}
+		 
+		     In this case, chrec_a will not overlap with chrec_b.  */
+		  *overlaps_a = conflict_fn_no_dependence ();
+		  *overlaps_b = conflict_fn_no_dependence ();
+		  *last_conflicts = integer_zero_node;
+		  dependence_stats.num_siv_independent++;
+		  return;
+		}
+	    }
+	}
+    }
+}
+
+/* Helper recursive function for initializing the matrix A.  Returns
+   the initial value of CHREC.  */
+
+static tree
+initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
+{
+  gcc_assert (chrec);
+
+  switch (TREE_CODE (chrec))
+    {
+    case POLYNOMIAL_CHREC:
+      gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
+
+      A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
+      return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
+
+    case PLUS_EXPR:
+    case MULT_EXPR:
+    case MINUS_EXPR:
+      {
+	tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+	tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
+
+	return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
+      }
+
+    case NOP_EXPR:
+      {
+	tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+	return chrec_convert (chrec_type (chrec), op, NULL);
+      }
+
+    case BIT_NOT_EXPR:
+      {
+	/* Handle ~X as -1 - X.  */
+	tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
+	return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
+			      build_int_cst (TREE_TYPE (chrec), -1), op);
+      }
+
+    case INTEGER_CST:
+      return chrec;
+
+    default:
+      gcc_unreachable ();
+      return NULL_TREE;
+    }
+}
+
+#define FLOOR_DIV(x,y) ((x) / (y))
+
+/* Solves the special case of the Diophantine equation: 
+   | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
+
+   Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
+   number of iterations that loops X and Y run.  The overlaps will be
+   constructed as evolutions in dimension DIM.  */
+
+static void
+compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, 
+					 affine_fn *overlaps_a,
+					 affine_fn *overlaps_b, 
+					 tree *last_conflicts, int dim)
+{
+  if (((step_a > 0 && step_b > 0)
+       || (step_a < 0 && step_b < 0)))
+    {
+      int step_overlaps_a, step_overlaps_b;
+      int gcd_steps_a_b, last_conflict, tau2;
+
+      gcd_steps_a_b = gcd (step_a, step_b);
+      step_overlaps_a = step_b / gcd_steps_a_b;
+      step_overlaps_b = step_a / gcd_steps_a_b;
+
+      if (niter > 0)
+	{
+	  tau2 = FLOOR_DIV (niter, step_overlaps_a);
+	  tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
+	  last_conflict = tau2;
+	  *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+	}
+      else
+	*last_conflicts = chrec_dont_know;
+
+      *overlaps_a = affine_fn_univar (integer_zero_node, dim, 
+				      build_int_cst (NULL_TREE,
+						     step_overlaps_a));
+      *overlaps_b = affine_fn_univar (integer_zero_node, dim, 
+				      build_int_cst (NULL_TREE, 
+						     step_overlaps_b));
+    }
+
+  else
+    {
+      *overlaps_a = affine_fn_cst (integer_zero_node);
+      *overlaps_b = affine_fn_cst (integer_zero_node);
+      *last_conflicts = integer_zero_node;
+    }
+}
+
+/* Solves the special case of a Diophantine equation where CHREC_A is
+   an affine bivariate function, and CHREC_B is an affine univariate
+   function.  For example, 
+
+   | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
+   
+   has the following overlapping functions: 
+
+   | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
+   | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
+   | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
+
+   FORNOW: This is a specialized implementation for a case occurring in
+   a common benchmark.  Implement the general algorithm.  */
+
+static void
+compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 
+				      conflict_function **overlaps_a,
+				      conflict_function **overlaps_b, 
+				      tree *last_conflicts)
+{
+  bool xz_p, yz_p, xyz_p;
+  int step_x, step_y, step_z;
+  HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
+  affine_fn overlaps_a_xz, overlaps_b_xz;
+  affine_fn overlaps_a_yz, overlaps_b_yz;
+  affine_fn overlaps_a_xyz, overlaps_b_xyz;
+  affine_fn ova1, ova2, ovb;
+  tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
+
+  step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
+  step_y = int_cst_value (CHREC_RIGHT (chrec_a));
+  step_z = int_cst_value (CHREC_RIGHT (chrec_b));
+
+  niter_x = 
+    estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
+				   false);
+  niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
+  niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
+  
+  if (niter_x < 0 || niter_y < 0 || niter_z < 0)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
+	   
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
+      *last_conflicts = chrec_dont_know;
+      return;
+    }
+
+  niter = MIN (niter_x, niter_z);
+  compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
+					   &overlaps_a_xz,
+					   &overlaps_b_xz,
+					   &last_conflicts_xz, 1);
+  niter = MIN (niter_y, niter_z);
+  compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
+					   &overlaps_a_yz,
+					   &overlaps_b_yz,
+					   &last_conflicts_yz, 2);
+  niter = MIN (niter_x, niter_z);
+  niter = MIN (niter_y, niter);
+  compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
+					   &overlaps_a_xyz,
+					   &overlaps_b_xyz,
+					   &last_conflicts_xyz, 3);
+
+  xz_p = !integer_zerop (last_conflicts_xz);
+  yz_p = !integer_zerop (last_conflicts_yz);
+  xyz_p = !integer_zerop (last_conflicts_xyz);
+
+  if (xz_p || yz_p || xyz_p)
+    {
+      ova1 = affine_fn_cst (integer_zero_node);
+      ova2 = affine_fn_cst (integer_zero_node);
+      ovb = affine_fn_cst (integer_zero_node);
+      if (xz_p)
+	{
+	  affine_fn t0 = ova1;
+	  affine_fn t2 = ovb;
+
+	  ova1 = affine_fn_plus (ova1, overlaps_a_xz);
+	  ovb = affine_fn_plus (ovb, overlaps_b_xz);
+	  affine_fn_free (t0);
+	  affine_fn_free (t2);
+	  *last_conflicts = last_conflicts_xz;
+	}
+      if (yz_p)
+	{
+	  affine_fn t0 = ova2;
+	  affine_fn t2 = ovb;
+
+	  ova2 = affine_fn_plus (ova2, overlaps_a_yz);
+	  ovb = affine_fn_plus (ovb, overlaps_b_yz);
+	  affine_fn_free (t0);
+	  affine_fn_free (t2);
+	  *last_conflicts = last_conflicts_yz;
+	}
+      if (xyz_p)
+	{
+	  affine_fn t0 = ova1;
+	  affine_fn t2 = ova2;
+	  affine_fn t4 = ovb;
+
+	  ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
+	  ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
+	  ovb = affine_fn_plus (ovb, overlaps_b_xyz);
+	  affine_fn_free (t0);
+	  affine_fn_free (t2);
+	  affine_fn_free (t4);
+	  *last_conflicts = last_conflicts_xyz;
+	}
+      *overlaps_a = conflict_fn (2, ova1, ova2);
+      *overlaps_b = conflict_fn (1, ovb);
+    }
+  else
+    {
+      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *last_conflicts = integer_zero_node;
+    }
+
+  affine_fn_free (overlaps_a_xz);
+  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);
+}
+
+/* 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
+   parameters, because it uses lambda matrices of integers.  */
+
+static void
+analyze_subscript_affine_affine (tree chrec_a, 
+				 tree chrec_b,
+				 conflict_function **overlaps_a, 
+				 conflict_function **overlaps_b, 
+				 tree *last_conflicts)
+{
+  unsigned nb_vars_a, nb_vars_b, dim;
+  HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
+  lambda_matrix A, U, S;
+
+  if (eq_evolutions_p (chrec_a, chrec_b))
+    {
+      /* The accessed index overlaps for each iteration in the
+	 loop.  */
+      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *last_conflicts = chrec_dont_know;
+      return;
+    }
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "(analyze_subscript_affine_affine \n");
+  
+  /* For determining the initial intersection, we have to solve a
+     Diophantine equation.  This is the most time consuming part.
+     
+     For answering to the question: "Is there a dependence?" we have
+     to prove that there exists a solution to the Diophantine
+     equation, and that the solution is in the iteration domain,
+     i.e. the solution is positive or zero, and that the solution
+     happens before the upper bound loop.nb_iterations.  Otherwise
+     there is no dependence.  This function outputs a description of
+     the iterations that hold the intersections.  */
+
+  nb_vars_a = nb_vars_in_chrec (chrec_a);
+  nb_vars_b = nb_vars_in_chrec (chrec_b);
+
+  dim = nb_vars_a + nb_vars_b;
+  U = lambda_matrix_new (dim, dim);
+  A = lambda_matrix_new (dim, 1);
+  S = lambda_matrix_new (dim, 1);
+
+  init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
+  init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
+  gamma = init_b - init_a;
+
+  /* Don't do all the hard work of solving the Diophantine equation
+     when we already know the solution: for example, 
+     | {3, +, 1}_1
+     | {3, +, 4}_2
+     | gamma = 3 - 3 = 0.
+     Then the first overlap occurs during the first iterations: 
+     | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
+  */
+  if (gamma == 0)
+    {
+      if (nb_vars_a == 1 && nb_vars_b == 1)
+	{
+	  HOST_WIDE_INT step_a, step_b;
+	  HOST_WIDE_INT niter, niter_a, niter_b;
+	  affine_fn ova, ovb;
+
+	  niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
+						   false);
+	  niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
+						   false);
+	  niter = MIN (niter_a, niter_b);
+	  step_a = int_cst_value (CHREC_RIGHT (chrec_a));
+	  step_b = int_cst_value (CHREC_RIGHT (chrec_b));
+
+	  compute_overlap_steps_for_affine_univar (niter, step_a, step_b, 
+						   &ova, &ovb, 
+						   last_conflicts, 1);
+	  *overlaps_a = conflict_fn (1, ova);
+	  *overlaps_b = conflict_fn (1, ovb);
+	}
+
+      else if (nb_vars_a == 2 && nb_vars_b == 1)
+	compute_overlap_steps_for_affine_1_2
+	  (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
+
+      else if (nb_vars_a == 1 && nb_vars_b == 2)
+	compute_overlap_steps_for_affine_1_2
+	  (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
+
+      else
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "affine-affine test failed: too many variables.\n");
+	  *overlaps_a = conflict_fn_not_known ();
+	  *overlaps_b = conflict_fn_not_known ();
+	  *last_conflicts = chrec_dont_know;
+	}
+      goto end_analyze_subs_aa;
+    }
+
+  /* U.A = S */
+  lambda_matrix_right_hermite (A, dim, 1, S, U);
+
+  if (S[0][0] < 0)
+    {
+      S[0][0] *= -1;
+      lambda_matrix_row_negate (U, dim, 0);
+    }
+  gcd_alpha_beta = S[0][0];
+
+  /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
+     but that is a quite strange case.  Instead of ICEing, answer
+     don't know.  */
+  if (gcd_alpha_beta == 0)
+    {
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
+      *last_conflicts = chrec_dont_know;
+      goto end_analyze_subs_aa;
+    }
+
+  /* The classic "gcd-test".  */
+  if (!int_divides_p (gcd_alpha_beta, gamma))
+    {
+      /* The "gcd-test" has determined that there is no integer
+	 solution, i.e. there is no dependence.  */
+      *overlaps_a = conflict_fn_no_dependence ();
+      *overlaps_b = conflict_fn_no_dependence ();
+      *last_conflicts = integer_zero_node;
+    }
+
+  /* Both access functions are univariate.  This includes SIV and MIV cases.  */
+  else if (nb_vars_a == 1 && nb_vars_b == 1)
+    {
+      /* Both functions should have the same evolution sign.  */
+      if (((A[0][0] > 0 && -A[1][0] > 0)
+	   || (A[0][0] < 0 && -A[1][0] < 0)))
+	{
+	  /* The solutions are given by:
+	     | 
+	     | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
+	     |                           [u21 u22]    [y0]
+	 
+	     For a given integer t.  Using the following variables,
+	 
+	     | i0 = u11 * gamma / gcd_alpha_beta
+	     | j0 = u12 * gamma / gcd_alpha_beta
+	     | i1 = u21
+	     | j1 = u22
+	 
+	     the solutions are:
+	 
+	     | x0 = i0 + i1 * t, 
+	     | y0 = j0 + j1 * t.  */
+      	  HOST_WIDE_INT i0, j0, i1, j1;
+
+	  i0 = U[0][0] * gamma / gcd_alpha_beta;
+	  j0 = U[0][1] * gamma / gcd_alpha_beta;
+	  i1 = U[1][0];
+	  j1 = U[1][1];
+
+	  if ((i1 == 0 && i0 < 0)
+	      || (j1 == 0 && j0 < 0))
+	    {
+	      /* There is no solution.  
+		 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 
+		 falls in here, but for the moment we don't look at the 
+		 upper bound of the iteration domain.  */
+	      *overlaps_a = conflict_fn_no_dependence ();
+	      *overlaps_b = conflict_fn_no_dependence ();
+	      *last_conflicts = integer_zero_node;
+	      goto end_analyze_subs_aa;
+	    }
+
+	  if (i1 > 0 && j1 > 0)
+	    {
+	      HOST_WIDE_INT niter_a = estimated_loop_iterations_int
+		(get_chrec_loop (chrec_a), false);
+	      HOST_WIDE_INT niter_b = estimated_loop_iterations_int
+		(get_chrec_loop (chrec_b), false);
+	      HOST_WIDE_INT niter = MIN (niter_a, niter_b);
+
+	      /* (X0, Y0) is a solution of the Diophantine equation:
+		 "chrec_a (X0) = chrec_b (Y0)".  */
+	      HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
+					CEIL (-j0, j1));
+	      HOST_WIDE_INT x0 = i1 * tau1 + i0;
+	      HOST_WIDE_INT y0 = j1 * tau1 + j0;
+
+	      /* (X1, Y1) is the smallest positive solution of the eq
+		 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
+		 first conflict occurs.  */
+	      HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
+	      HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
+	      HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
+
+	      if (niter > 0)
+		{
+		  HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
+					    FLOOR_DIV (niter - j0, j1));
+		  HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
+
+		  /* If the overlap occurs outside of the bounds of the
+		     loop, there is no dependence.  */
+		  if (x1 >= niter || y1 >= niter)
+		    {
+		      *overlaps_a = conflict_fn_no_dependence ();
+		      *overlaps_b = conflict_fn_no_dependence ();
+		      *last_conflicts = integer_zero_node;
+		      goto end_analyze_subs_aa;
+		    }
+		  else
+		    *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
+		}
+	      else
+		*last_conflicts = chrec_dont_know;
+
+	      *overlaps_a
+		= conflict_fn (1,
+			       affine_fn_univar (build_int_cst (NULL_TREE, x1),
+						 1,
+						 build_int_cst (NULL_TREE, i1)));
+	      *overlaps_b
+		= conflict_fn (1,
+			       affine_fn_univar (build_int_cst (NULL_TREE, y1),
+						 1,
+						 build_int_cst (NULL_TREE, j1)));
+	    }
+	  else
+	    {
+	      /* FIXME: For the moment, the upper bound of the
+		 iteration domain for i and j is not checked.  */
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+	      *overlaps_a = conflict_fn_not_known ();
+	      *overlaps_b = conflict_fn_not_known ();
+	      *last_conflicts = chrec_dont_know;
+	    }
+	}
+      else
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+	  *overlaps_a = conflict_fn_not_known ();
+	  *overlaps_b = conflict_fn_not_known ();
+	  *last_conflicts = chrec_dont_know;
+	}
+    }
+  else
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
+      *last_conflicts = chrec_dont_know;
+    }
+
+end_analyze_subs_aa:  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  (overlaps_a = ");
+      dump_conflict_function (dump_file, *overlaps_a);
+      fprintf (dump_file, ")\n  (overlaps_b = ");
+      dump_conflict_function (dump_file, *overlaps_b);
+      fprintf (dump_file, ")\n");
+      fprintf (dump_file, ")\n");
+    }
+}
+
+/* Returns true when analyze_subscript_affine_affine can be used for
+   determining the dependence relation between chrec_a and chrec_b,
+   that contain symbols.  This function modifies chrec_a and chrec_b
+   such that the analysis result is the same, and such that they don't
+   contain symbols, and then can safely be passed to the analyzer.  
+
+   Example: The analysis of the following tuples of evolutions produce
+   the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
+   vs. {0, +, 1}_1
+   
+   {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
+   {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
+*/
+
+static bool
+can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
+{
+  tree diff, type, left_a, left_b, right_b;
+
+  if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
+      || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
+    /* FIXME: For the moment not handled.  Might be refined later.  */
+    return false;
+
+  type = chrec_type (*chrec_a);
+  left_a = CHREC_LEFT (*chrec_a);
+  left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
+  diff = chrec_fold_minus (type, left_a, left_b);
+
+  if (!evolution_function_is_constant_p (diff))
+    return false;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
+
+  *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a), 
+				     diff, CHREC_RIGHT (*chrec_a));
+  right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
+  *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
+				     build_int_cst (type, 0),
+				     right_b);
+  return true;
+}
+
+/* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
+   *OVERLAPS_B are initialized to the functions that describe the
+   relation between the elements accessed twice by CHREC_A and
+   CHREC_B.  For k >= 0, the following property is verified:
+
+   CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
+
+static void
+analyze_siv_subscript (tree chrec_a, 
+		       tree chrec_b,
+		       conflict_function **overlaps_a, 
+		       conflict_function **overlaps_b, 
+		       tree *last_conflicts,
+		       int loop_nest_num)
+{
+  dependence_stats.num_siv++;
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "(analyze_siv_subscript \n");
+  
+  if (evolution_function_is_constant_p (chrec_a)
+      && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
+    analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 
+				      overlaps_a, overlaps_b, last_conflicts);
+  
+  else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
+	   && evolution_function_is_constant_p (chrec_b))
+    analyze_siv_subscript_cst_affine (chrec_b, chrec_a, 
+				      overlaps_b, overlaps_a, last_conflicts);
+  
+  else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
+	   && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
+    {
+      if (!chrec_contains_symbols (chrec_a)
+	  && !chrec_contains_symbols (chrec_b))
+	{
+	  analyze_subscript_affine_affine (chrec_a, chrec_b, 
+					   overlaps_a, overlaps_b, 
+					   last_conflicts);
+
+	  if (CF_NOT_KNOWN_P (*overlaps_a)
+	      || CF_NOT_KNOWN_P (*overlaps_b))
+	    dependence_stats.num_siv_unimplemented++;
+	  else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+		   || CF_NO_DEPENDENCE_P (*overlaps_b))
+	    dependence_stats.num_siv_independent++;
+	  else
+	    dependence_stats.num_siv_dependent++;
+	}
+      else if (can_use_analyze_subscript_affine_affine (&chrec_a, 
+							&chrec_b))
+	{
+	  analyze_subscript_affine_affine (chrec_a, chrec_b, 
+					   overlaps_a, overlaps_b, 
+					   last_conflicts);
+
+	  if (CF_NOT_KNOWN_P (*overlaps_a)
+	      || CF_NOT_KNOWN_P (*overlaps_b))
+	    dependence_stats.num_siv_unimplemented++;
+	  else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+		   || CF_NO_DEPENDENCE_P (*overlaps_b))
+	    dependence_stats.num_siv_independent++;
+	  else
+	    dependence_stats.num_siv_dependent++;
+	}
+      else
+	goto siv_subscript_dontknow;
+    }
+
+  else
+    {
+    siv_subscript_dontknow:;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "siv test failed: unimplemented.\n");
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
+      *last_conflicts = chrec_dont_know;
+      dependence_stats.num_siv_unimplemented++;
+    }
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, ")\n");
+}
+
+/* Returns false if we can prove that the greatest common divisor of the steps
+   of CHREC does not divide CST, false otherwise.  */
+
+static bool
+gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
+{
+  HOST_WIDE_INT cd = 0, val;
+  tree step;
+
+  if (!host_integerp (cst, 0))
+    return true;
+  val = tree_low_cst (cst, 0);
+
+  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
+    {
+      step = CHREC_RIGHT (chrec);
+      if (!host_integerp (step, 0))
+	return true;
+      cd = gcd (cd, tree_low_cst (step, 0));
+      chrec = CHREC_LEFT (chrec);
+    }
+
+  return val % cd == 0;
+}
+
+/* Analyze a MIV (Multiple Index Variable) subscript with respect to
+   LOOP_NEST.  *OVERLAPS_A and *OVERLAPS_B are initialized to the
+   functions that describe the relation between the elements accessed
+   twice by CHREC_A and CHREC_B.  For k >= 0, the following property
+   is verified:
+
+   CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
+
+static void
+analyze_miv_subscript (tree chrec_a, 
+		       tree chrec_b, 
+		       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");
+
+  type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
+  chrec_a = chrec_convert (type, chrec_a, NULL);
+  chrec_b = chrec_convert (type, chrec_b, NULL);
+  difference = chrec_fold_minus (type, chrec_a, chrec_b);
+  
+  if (eq_evolutions_p (chrec_a, chrec_b))
+    {
+      /* Access functions are the same: all the elements are accessed
+	 in the same order.  */
+      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *last_conflicts = estimated_loop_iterations_tree
+				(get_chrec_loop (chrec_a), true);
+      dependence_stats.num_miv_dependent++;
+    }
+  
+  else if (evolution_function_is_constant_p (difference)
+	   /* For the moment, the following is verified:
+	      evolution_function_is_affine_multivariate_p (chrec_a,
+	      loop_nest->num) */
+	   && !gcd_of_steps_may_divide_p (chrec_a, difference))
+    {
+      /* testsuite/.../ssa-chrec-33.c
+	 {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2 
+	 
+	 The difference is 1, and all the evolution steps are multiples
+	 of 2, consequently there are no overlapping elements.  */
+      *overlaps_a = conflict_fn_no_dependence ();
+      *overlaps_b = conflict_fn_no_dependence ();
+      *last_conflicts = integer_zero_node;
+      dependence_stats.num_miv_independent++;
+    }
+  
+  else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
+	   && !chrec_contains_symbols (chrec_a)
+	   && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
+	   && !chrec_contains_symbols (chrec_b))
+    {
+      /* testsuite/.../ssa-chrec-35.c
+	 {0, +, 1}_2  vs.  {0, +, 1}_3
+	 the overlapping elements are respectively located at iterations:
+	 {0, +, 1}_x and {0, +, 1}_x, 
+	 in other words, we have the equality: 
+	 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
+	 
+	 Other examples: 
+	 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = 
+	 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
+
+	 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = 
+	 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
+      */
+      analyze_subscript_affine_affine (chrec_a, chrec_b, 
+				       overlaps_a, overlaps_b, last_conflicts);
+
+      if (CF_NOT_KNOWN_P (*overlaps_a)
+ 	  || CF_NOT_KNOWN_P (*overlaps_b))
+	dependence_stats.num_miv_unimplemented++;
+      else if (CF_NO_DEPENDENCE_P (*overlaps_a)
+	       || CF_NO_DEPENDENCE_P (*overlaps_b))
+	dependence_stats.num_miv_independent++;
+      else
+	dependence_stats.num_miv_dependent++;
+    }
+  
+  else
+    {
+      /* When the analysis is too difficult, answer "don't know".  */
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
+
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
+      *last_conflicts = chrec_dont_know;
+      dependence_stats.num_miv_unimplemented++;
+    }
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, ")\n");
+}
+
+/* Determines the iterations for which CHREC_A is equal to CHREC_B in
+   with respect to LOOP_NEST.  OVERLAP_ITERATIONS_A and
+   OVERLAP_ITERATIONS_B are initialized with two functions that
+   describe the iterations that contain conflicting elements.
+   
+   Remark: For an integer k >= 0, the following equality is true:
+   
+   CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
+*/
+
+static void 
+analyze_overlapping_iterations (tree chrec_a, 
+				tree chrec_b, 
+				conflict_function **overlap_iterations_a, 
+				conflict_function **overlap_iterations_b, 
+				tree *last_conflicts, struct loop *loop_nest)
+{
+  unsigned int lnn = loop_nest->num;
+
+  dependence_stats.num_subscript_tests++;
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "(analyze_overlapping_iterations \n");
+      fprintf (dump_file, "  (chrec_a = ");
+      print_generic_expr (dump_file, chrec_a, 0);
+      fprintf (dump_file, ")\n  (chrec_b = ");
+      print_generic_expr (dump_file, chrec_b, 0);
+      fprintf (dump_file, ")\n");
+    }
+
+  if (chrec_a == NULL_TREE
+      || chrec_b == NULL_TREE
+      || chrec_contains_undetermined (chrec_a)
+      || chrec_contains_undetermined (chrec_b))
+    {
+      dependence_stats.num_subscript_undetermined++;
+      
+      *overlap_iterations_a = conflict_fn_not_known ();
+      *overlap_iterations_b = conflict_fn_not_known ();
+    }
+
+  /* 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))
+    {
+      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. */
+  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)))
+    {
+      dependence_stats.num_subscript_undetermined++;
+      *overlap_iterations_a = conflict_fn_not_known ();
+      *overlap_iterations_b = conflict_fn_not_known ();
+    }
+
+  else if (ziv_subscript_p (chrec_a, chrec_b))
+    analyze_ziv_subscript (chrec_a, chrec_b, 
+			   overlap_iterations_a, overlap_iterations_b,
+			   last_conflicts);
+  
+  else if (siv_subscript_p (chrec_a, chrec_b))
+    analyze_siv_subscript (chrec_a, chrec_b, 
+			   overlap_iterations_a, overlap_iterations_b, 
+			   last_conflicts, lnn);
+  
+  else
+    analyze_miv_subscript (chrec_a, chrec_b, 
+			   overlap_iterations_a, overlap_iterations_b,
+			   last_conflicts, loop_nest);
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  (overlap_iterations_a = ");
+      dump_conflict_function (dump_file, *overlap_iterations_a);
+      fprintf (dump_file, ")\n  (overlap_iterations_b = ");
+      dump_conflict_function (dump_file, *overlap_iterations_b);
+      fprintf (dump_file, ")\n");
+      fprintf (dump_file, ")\n");
+    }
+}
+
+/* Helper function for uniquely inserting distance vectors.  */
+
+static void
+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++)
+    if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
+      return;
+
+  VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
+}
+
+/* Helper function for uniquely inserting direction vectors.  */
+
+static void
+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++)
+    if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
+      return;
+
+  VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
+}
+
+/* Add a distance of 1 on all the loops outer than INDEX.  If we
+   haven't yet determined a distance for this outer loop, push a new
+   distance vector composed of the previous distance, and a distance
+   of 1 for this outer loop.  Example:
+
+   | loop_1
+   |   loop_2
+   |     A[10]
+   |   endloop_2
+   | endloop_1
+
+   Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
+   save (0, 1), then we have to save (1, 0).  */
+
+static void
+add_outer_distances (struct data_dependence_relation *ddr,
+		     lambda_vector dist_v, int index)
+{
+  /* For each outer loop where init_v is not set, the accesses are
+     in dependence of distance 1 in the loop.  */
+  while (--index >= 0)
+    {
+      lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+      lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
+      save_v[index] = 1;
+      save_dist_v (ddr, save_v);
+    }
+}
+
+/* Return false when fail to represent the data dependence as a
+   distance vector.  INIT_B is set to true when a component has been
+   added to the distance vector DIST_V.  INDEX_CARRY is then set to
+   the index in DIST_V that carries the dependence.  */
+
+static bool
+build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
+			     struct data_reference *ddr_a,
+			     struct data_reference *ddr_b,
+			     lambda_vector dist_v, bool *init_b,
+			     int *index_carry)
+{
+  unsigned i;
+  lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+    {
+      tree access_fn_a, access_fn_b;
+      struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
+
+      if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+	{
+	  non_affine_dependence_relation (ddr);
+	  return false;
+	}
+
+      access_fn_a = DR_ACCESS_FN (ddr_a, i);
+      access_fn_b = DR_ACCESS_FN (ddr_b, i);
+
+      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),
+					    DDR_LOOP_NEST (ddr));
+	  int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
+					    DDR_LOOP_NEST (ddr));
+
+	  /* 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));
+
+	  /* 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:
+
+	     | loop i = 0, N, 1
+	     |   T[i+1][i] = ...
+	     |   ... = T[i][i]
+	     | endloop
+	  */
+	  if (init_v[index] != 0 && dist_v[index] != dist)
+	    {
+	      finalize_ddr_dependent (ddr, chrec_known);
+	      return false;
+	    }
+
+	  dist_v[index] = dist;
+	  init_v[index] = 1;
+	  *init_b = true;
+	}
+      else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
+	{
+	  /* This can be for example an affine vs. constant dependence
+	     (T[i] vs. T[3]) that is not an affine dependence and is
+	     not representable as a distance vector.  */
+	  non_affine_dependence_relation (ddr);
+	  return false;
+	}
+    }
+
+  return true;
+}
+
+/* Return true when the DDR contains only constant access functions.  */
+
+static bool
+constant_access_functions (const struct data_dependence_relation *ddr)
+{
+  unsigned i;
+
+  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+    if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
+	|| !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
+      return false;
+
+  return true;
+}
+
+/* Helper function for the case where DDR_A and DDR_B are the same
+   multivariate access function with a constant step.  For an example
+   see pr34635-1.c.  */
+
+static void
+add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
+{
+  int x_1, x_2;
+  tree c_1 = CHREC_LEFT (c_2);
+  tree c_0 = CHREC_LEFT (c_1);
+  lambda_vector dist_v;
+  int v1, v2, cd;
+
+  /* Polynomials with more than 2 variables are not handled yet.  When
+     the evolution steps are parameters, it is not possible to
+     represent the dependence using classical distance vectors.  */
+  if (TREE_CODE (c_0) != INTEGER_CST
+      || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
+      || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
+    {
+      DDR_AFFINE_P (ddr) = false;
+      return;
+    }
+
+  x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
+  x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
+
+  /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2).  */
+  dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+  v1 = int_cst_value (CHREC_RIGHT (c_1));
+  v2 = int_cst_value (CHREC_RIGHT (c_2));
+  cd = gcd (v1, v2);
+  v1 /= cd;
+  v2 /= cd;
+
+  if (v2 < 0)
+    {
+      v2 = -v2;
+      v1 = -v1;
+    }
+
+  dist_v[x_1] = v2;
+  dist_v[x_2] = -v1;
+  save_dist_v (ddr, dist_v);
+
+  add_outer_distances (ddr, dist_v, x_1);
+}
+
+/* Helper function for the case where DDR_A and DDR_B are the same
+   access functions.  */
+
+static void
+add_other_self_distances (struct data_dependence_relation *ddr)
+{
+  lambda_vector dist_v;
+  unsigned i;
+  int index_carry = DDR_NB_LOOPS (ddr);
+
+  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+    {
+      tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
+
+      if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
+	{
+	  if (!evolution_function_is_univariate_p (access_fun))
+	    {
+	      if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
+		{
+		  DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
+		  return;
+		}
+
+	      access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
+
+	      if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
+		add_multivariate_self_dist (ddr, access_fun);
+	      else
+		/* The evolution step is not constant: it varies in
+		   the outer loop, so this cannot be represented by a
+		   distance vector.  For example in pr34635.c the
+		   evolution is {0, +, {0, +, 4}_1}_2.  */
+		DDR_AFFINE_P (ddr) = false;
+
+	      return;
+	    }
+
+	  index_carry = MIN (index_carry,
+			     index_in_loop_nest (CHREC_VARIABLE (access_fun),
+						 DDR_LOOP_NEST (ddr)));
+	}
+    }
+
+  dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+  add_outer_distances (ddr, dist_v, index_carry);
+}
+
+static void
+insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
+{
+  lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+  dist_v[DDR_INNER_LOOP (ddr)] = 1;
+  save_dist_v (ddr, dist_v);
+}
+
+/* Adds a unit distance vector to DDR when there is a 0 overlap.  This
+   is the case for example when access functions are the same and
+   equal to a constant, as in:
+
+   | loop_1
+   |   A[3] = ...
+   |   ... = A[3]
+   | endloop_1
+
+   in which case the distance vectors are (0) and (1).  */
+
+static void
+add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
+{
+  unsigned i, j;
+
+  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+    {
+      subscript_p sub = DDR_SUBSCRIPT (ddr, i);
+      conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
+      conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
+
+      for (j = 0; j < ca->n; j++)
+	if (affine_function_zero_p (ca->fns[j]))
+	  {
+	    insert_innermost_unit_dist_vector (ddr);
+	    return;
+	  }
+
+      for (j = 0; j < cb->n; j++)
+	if (affine_function_zero_p (cb->fns[j]))
+	  {
+	    insert_innermost_unit_dist_vector (ddr);
+	    return;
+	  }
+    }
+}
+
+/* Compute the classic per loop distance vector.  DDR is the data
+   dependence relation to build a vector from.  Return false when fail
+   to represent the data dependence as a distance vector.  */
+
+static bool
+build_classic_dist_vector (struct data_dependence_relation *ddr,
+			   struct loop *loop_nest)
+{
+  bool init_b = false;
+  int index_carry = DDR_NB_LOOPS (ddr);
+  lambda_vector dist_v;
+
+  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
+    return false;
+
+  if (same_access_functions (ddr))
+    {
+      /* Save the 0 vector.  */
+      dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+      save_dist_v (ddr, dist_v);
+
+      if (constant_access_functions (ddr))
+	add_distance_for_zero_overlaps (ddr);
+
+      if (DDR_NB_LOOPS (ddr) > 1)
+	add_other_self_distances (ddr);
+
+      return true;
+    }
+
+  dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+  if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
+				    dist_v, &init_b, &index_carry))
+    return false;
+
+  /* Save the distance vector if we initialized one.  */
+  if (init_b)
+    {
+      /* Verify a basic constraint: classic distance vectors should
+	 always be lexicographically positive.
+
+	 Data references are collected in the order of execution of
+	 the program, thus for the following loop
+
+	 | for (i = 1; i < 100; i++)
+	 |   for (j = 1; j < 100; j++)
+	 |     {
+	 |       t = T[j+1][i-1];  // A
+	 |       T[j][i] = t + 2;  // B
+	 |     }
+
+	 references are collected following the direction of the wind:
+	 A then B.  The data dependence tests are performed also
+	 following this order, such that we're looking at the distance
+	 separating the elements accessed by A from the elements later
+	 accessed by B.  But in this example, the distance returned by
+	 test_dep (A, B) is lexicographically negative (-1, 1), that
+	 means that the access A occurs later than B with respect to
+	 the outer loop, ie. we're actually looking upwind.  In this
+	 case we solve test_dep (B, A) looking downwind to the
+	 lexicographically positive solution, that returns the
+	 distance vector (1, -1).  */
+      if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
+	{
+	  lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+	  if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+					      loop_nest))
+	    return false;
+	  compute_subscript_distance (ddr);
+	  if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+					    save_v, &init_b, &index_carry))
+	    return false;
+	  save_dist_v (ddr, save_v);
+	  DDR_REVERSED_P (ddr) = true;
+
+	  /* In this case there is a dependence forward for all the
+	     outer loops:
+
+	     | for (k = 1; k < 100; k++)
+	     |  for (i = 1; i < 100; i++)
+	     |   for (j = 1; j < 100; j++)
+	     |     {
+	     |       t = T[j+1][i-1];  // A
+	     |       T[j][i] = t + 2;  // B
+	     |     }
+
+	     the vectors are: 
+	     (0,  1, -1)
+	     (1,  1, -1)
+	     (1, -1,  1)
+	  */
+	  if (DDR_NB_LOOPS (ddr) > 1)
+	    {
+ 	      add_outer_distances (ddr, save_v, index_carry);
+	      add_outer_distances (ddr, dist_v, index_carry);
+	    }
+	}
+      else
+	{
+	  lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+	  lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
+
+	  if (DDR_NB_LOOPS (ddr) > 1)
+	    {
+	      lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+	      if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
+						  DDR_A (ddr), loop_nest))
+		return false;
+	      compute_subscript_distance (ddr);
+	      if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
+						opposite_v, &init_b,
+						&index_carry))
+		return false;
+
+	      save_dist_v (ddr, save_v);
+	      add_outer_distances (ddr, dist_v, index_carry);
+	      add_outer_distances (ddr, opposite_v, index_carry);
+	    }
+	  else
+	    save_dist_v (ddr, save_v);
+	}
+    }
+  else
+    {
+      /* There is a distance of 1 on all the outer loops: Example:
+	 there is a dependence of distance 1 on loop_1 for the array A.
+
+	 | loop_1
+	 |   A[5] = ...
+	 | endloop
+      */
+      add_outer_distances (ddr, dist_v,
+			   lambda_vector_first_nz (dist_v,
+						   DDR_NB_LOOPS (ddr), 0));
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      unsigned i;
+
+      fprintf (dump_file, "(build_classic_dist_vector\n");
+      for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+	{
+	  fprintf (dump_file, "  dist_vector = (");
+	  print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
+			       DDR_NB_LOOPS (ddr));
+	  fprintf (dump_file, "  )\n");
+	}
+      fprintf (dump_file, ")\n");
+    }
+
+  return true;
+}
+
+/* Return the direction for a given distance.
+   FIXME: Computing dir this way is suboptimal, since dir can catch
+   cases that dist is unable to represent.  */
+
+static inline enum data_dependence_direction
+dir_from_dist (int dist)
+{
+  if (dist > 0)
+    return dir_positive;
+  else if (dist < 0)
+    return dir_negative;
+  else
+    return dir_equal;
+}
+
+/* Compute the classic per loop direction vector.  DDR is the data
+   dependence relation to build a vector from.  */
+
+static void
+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++)
+    {
+      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]);
+
+      save_dir_v (ddr, dir_v);
+    }
+}
+
+/* Helper function.  Returns true when there is a dependence between
+   data references DRA and DRB.  */
+
+static bool
+subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
+			       struct data_reference *dra,
+			       struct data_reference *drb,
+			       struct loop *loop_nest)
+{
+  unsigned int i;
+  tree last_conflicts;
+  struct subscript *subscript;
+
+  for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
+       i++)
+    {
+      conflict_function *overlaps_a, *overlaps_b;
+
+      analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 
+				      DR_ACCESS_FN (drb, i),
+				      &overlaps_a, &overlaps_b, 
+				      &last_conflicts, loop_nest);
+
+      if (CF_NOT_KNOWN_P (overlaps_a)
+ 	  || CF_NOT_KNOWN_P (overlaps_b))
+ 	{
+ 	  finalize_ddr_dependent (ddr, chrec_dont_know);
+	  dependence_stats.num_dependence_undetermined++;
+	  free_conflict_function (overlaps_a);
+	  free_conflict_function (overlaps_b);
+	  return false;
+ 	}
+
+      else if (CF_NO_DEPENDENCE_P (overlaps_a)
+ 	       || CF_NO_DEPENDENCE_P (overlaps_b))
+ 	{
+ 	  finalize_ddr_dependent (ddr, chrec_known);
+	  dependence_stats.num_dependence_independent++;
+	  free_conflict_function (overlaps_a);
+	  free_conflict_function (overlaps_b);
+	  return false;
+ 	}
+
+      else
+ 	{
+	  if (SUB_CONFLICTS_IN_A (subscript))
+	    free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
+	  if (SUB_CONFLICTS_IN_B (subscript))
+	    free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
+
+ 	  SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
+ 	  SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
+	  SUB_LAST_CONFLICT (subscript) = last_conflicts;
+ 	}
+    }
+
+  return true;
+}
+
+/* Computes the conflicting iterations in LOOP_NEST, and initialize DDR.  */
+
+static void
+subscript_dependence_tester (struct data_dependence_relation *ddr,
+			     struct loop *loop_nest)
+{
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "(subscript_dependence_tester \n");
+  
+  if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
+    dependence_stats.num_dependence_dependent++;
+
+  compute_subscript_distance (ddr);
+  if (build_classic_dist_vector (ddr, loop_nest))
+    build_classic_dir_vector (ddr);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, ")\n");
+}
+
+/* Returns true when all the access functions of A are affine or
+   constant with respect to LOOP_NEST.  */
+
+static bool 
+access_functions_are_affine_or_constant_p (const struct data_reference *a,
+					   const struct loop *loop_nest)
+{
+  unsigned int i;
+  VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
+  tree t;
+
+  for (i = 0; VEC_iterate (tree, fns, i, t); i++)
+    if (!evolution_function_is_invariant_p (t, loop_nest->num)
+	&& !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
+      return false;
+  
+  return true;
+}
+
+/* Return true if we can create an affine data-ref for OP in STMT.  */
+
+bool
+stmt_simple_memref_p (struct loop *loop, gimple stmt, tree op)
+{
+  data_reference_p dr;
+  bool res = true;
+
+  dr = create_data_ref (loop, op, stmt, true);
+  if (!access_functions_are_affine_or_constant_p (dr, loop))
+    res = false;
+
+  free_data_ref (dr);
+  return res;
+}
+
+/* Initializes an equation for an OMEGA problem using the information
+   contained in the ACCESS_FUN.  Returns true when the operation
+   succeeded.
+
+   PB is the omega constraint system.
+   EQ is the number of the equation to be initialized.
+   OFFSET is used for shifting the variables names in the constraints:
+   a constrain is composed of 2 * the number of variables surrounding
+   dependence accesses.  OFFSET is set either to 0 for the first n variables,
+   then it is set to n.
+   ACCESS_FUN is expected to be an affine chrec.  */
+
+static bool
+init_omega_eq_with_af (omega_pb pb, unsigned eq, 
+		       unsigned int offset, tree access_fun, 
+		       struct data_dependence_relation *ddr)
+{
+  switch (TREE_CODE (access_fun))
+    {
+    case POLYNOMIAL_CHREC:
+      {
+	tree left = CHREC_LEFT (access_fun);
+	tree right = CHREC_RIGHT (access_fun);
+	int var = CHREC_VARIABLE (access_fun);
+	unsigned var_idx;
+
+	if (TREE_CODE (right) != INTEGER_CST)
+	  return false;
+
+	var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
+	pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
+
+	/* Compute the innermost loop index.  */
+	DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
+
+	if (offset == 0)
+	  pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1] 
+	    += int_cst_value (right);
+
+	switch (TREE_CODE (left))
+	  {
+	  case POLYNOMIAL_CHREC:
+	    return init_omega_eq_with_af (pb, eq, offset, left, ddr);
+
+	  case INTEGER_CST:
+	    pb->eqs[eq].coef[0] += int_cst_value (left);
+	    return true;
+
+	  default:
+	    return false;
+	  }
+      }
+
+    case INTEGER_CST:
+      pb->eqs[eq].coef[0] += int_cst_value (access_fun);
+      return true;
+
+    default:
+      return false;
+    }
+}
+
+/* As explained in the comments preceding init_omega_for_ddr, we have
+   to set up a system for each loop level, setting outer loops
+   variation to zero, and current loop variation to positive or zero.
+   Save each lexico positive distance vector.  */
+
+static void
+omega_extract_distance_vectors (omega_pb pb,
+				struct data_dependence_relation *ddr)
+{
+  int eq, geq;
+  unsigned i, j;
+  struct loop *loopi, *loopj;
+  enum omega_result res;
+
+  /* Set a new problem for each loop in the nest.  The basis is the
+     problem that we have initialized until now.  On top of this we
+     add new constraints.  */
+  for (i = 0; i <= DDR_INNER_LOOP (ddr) 
+	 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+    {
+      int dist = 0;
+      omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
+					   DDR_NB_LOOPS (ddr));
+
+      omega_copy_problem (copy, pb);
+
+      /* For all the outer loops "loop_j", add "dj = 0".  */
+      for (j = 0;
+	   j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
+	{
+	  eq = omega_add_zero_eq (copy, omega_black);
+	  copy->eqs[eq].coef[j + 1] = 1;
+	}
+
+      /* For "loop_i", add "0 <= di".  */
+      geq = omega_add_zero_geq (copy, omega_black);
+      copy->geqs[geq].coef[i + 1] = 1;
+
+      /* Reduce the constraint system, and test that the current
+	 problem is feasible.  */
+      res = omega_simplify_problem (copy);
+      if (res == omega_false 
+	  || res == omega_unknown
+	  || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
+	goto next_problem;
+
+      for (eq = 0; eq < copy->num_subs; eq++)
+	if (copy->subs[eq].key == (int) i + 1)
+	  {
+	    dist = copy->subs[eq].coef[0];
+	    goto found_dist;
+	  }
+
+      if (dist == 0)
+	{
+	  /* Reinitialize problem...  */
+	  omega_copy_problem (copy, pb);
+	  for (j = 0;
+	       j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
+	    {
+	      eq = omega_add_zero_eq (copy, omega_black);
+	      copy->eqs[eq].coef[j + 1] = 1;
+	    }
+
+	  /* ..., but this time "di = 1".  */
+	  eq = omega_add_zero_eq (copy, omega_black);
+	  copy->eqs[eq].coef[i + 1] = 1;
+	  copy->eqs[eq].coef[0] = -1;
+
+	  res = omega_simplify_problem (copy);
+	  if (res == omega_false 
+	      || res == omega_unknown
+	      || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
+	    goto next_problem;
+
+	  for (eq = 0; eq < copy->num_subs; eq++)
+	    if (copy->subs[eq].key == (int) i + 1)
+	      {
+		dist = copy->subs[eq].coef[0];
+		goto found_dist;
+	      }
+	}
+
+    found_dist:;
+      /* Save the lexicographically positive distance vector.  */
+      if (dist >= 0)
+	{
+	  lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+	  lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+
+	  dist_v[i] = dist;
+
+	  for (eq = 0; eq < copy->num_subs; eq++)
+	    if (copy->subs[eq].key > 0)
+	      {
+		dist = copy->subs[eq].coef[0];
+		dist_v[copy->subs[eq].key - 1] = dist;
+	      }
+
+	  for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+	    dir_v[j] = dir_from_dist (dist_v[j]);
+
+	  save_dist_v (ddr, dist_v);
+	  save_dir_v (ddr, dir_v);
+	}
+
+    next_problem:;
+      omega_free_problem (copy);
+    }
+}
+
+/* This is called for each subscript of a tuple of data references:
+   insert an equality for representing the conflicts.  */
+
+static bool
+omega_setup_subscript (tree access_fun_a, tree access_fun_b,
+		       struct data_dependence_relation *ddr,
+		       omega_pb pb, bool *maybe_dependent)
+{
+  int eq;
+  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);
+
+  /* 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;
+
+  /* ZIV test.  */
+  if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
+    {
+      /* There is no dependence.  */
+      *maybe_dependent = false;
+      return true;
+    }
+
+  fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
+
+  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
+       constraints cannot be built: answer "don't know".  */
+    return false;
+
+  /* GCD test.  */
+  if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
+      && !int_divides_p (lambda_vector_gcd 
+			 ((lambda_vector) &(pb->eqs[eq].coef[1]),
+			  2 * DDR_NB_LOOPS (ddr)),
+			 pb->eqs[eq].coef[0]))
+    {
+      /* There is no dependence.  */
+      *maybe_dependent = false;
+      return true;
+    }
+
+  return true;
+}
+
+/* Helper function, same as init_omega_for_ddr but specialized for
+   data references A and B.  */
+
+static bool
+init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
+		      struct data_dependence_relation *ddr,
+		      omega_pb pb, bool *maybe_dependent)
+{
+  unsigned i;
+  int ineq;
+  struct loop *loopi;
+  unsigned nb_loops = DDR_NB_LOOPS (ddr);
+
+  /* Insert an equality per subscript.  */
+  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
+    {
+      if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
+				  ddr, pb, maybe_dependent))
+	return false;
+      else if (*maybe_dependent == false)
+	{
+	  /* There is no dependence.  */
+	  DDR_ARE_DEPENDENT (ddr) = chrec_known;
+	  return true;
+	}
+    }
+
+  /* Insert inequalities: constraints corresponding to the iteration
+     domain, i.e. the loops surrounding the references "loop_x" and
+     the distance variables "dx".  The layout of the OMEGA
+     representation is as follows:
+     - coef[0] is the constant
+     - coef[1..nb_loops] are the protected variables that will not be
+     removed by the solver: the "dx"
+     - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
+  */
+  for (i = 0; i <= DDR_INNER_LOOP (ddr) 
+	 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
+    {
+      HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
+
+      /* 0 <= loop_x */
+      ineq = omega_add_zero_geq (pb, omega_black);
+      pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
+
+      /* 0 <= loop_x + dx */
+      ineq = omega_add_zero_geq (pb, omega_black);
+      pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
+      pb->geqs[ineq].coef[i + 1] = 1;
+
+      if (nbi != -1)
+	{
+	  /* loop_x <= nb_iters */
+	  ineq = omega_add_zero_geq (pb, omega_black);
+	  pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
+	  pb->geqs[ineq].coef[0] = nbi;
+
+	  /* loop_x + dx <= nb_iters */
+	  ineq = omega_add_zero_geq (pb, omega_black);
+	  pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
+	  pb->geqs[ineq].coef[i + 1] = -1;
+	  pb->geqs[ineq].coef[0] = nbi;
+
+	  /* A step "dx" bigger than nb_iters is not feasible, so
+	     add "0 <= nb_iters + dx",  */
+	  ineq = omega_add_zero_geq (pb, omega_black);
+	  pb->geqs[ineq].coef[i + 1] = 1;
+	  pb->geqs[ineq].coef[0] = nbi;
+	  /* and "dx <= nb_iters".  */
+	  ineq = omega_add_zero_geq (pb, omega_black);
+	  pb->geqs[ineq].coef[i + 1] = -1;
+	  pb->geqs[ineq].coef[0] = nbi;
+	}
+    }
+
+  omega_extract_distance_vectors (pb, ddr);
+
+  return true;
+}
+
+/* Sets up the Omega dependence problem for the data dependence
+   relation DDR.  Returns false when the constraint system cannot be
+   built, ie. when the test answers "don't know".  Returns true
+   otherwise, and when independence has been proved (using one of the
+   trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
+   set MAYBE_DEPENDENT to true.
+
+   Example: for setting up the dependence system corresponding to the
+   conflicting accesses 
+
+   | loop_i
+   |   loop_j
+   |     A[i, i+1] = ...
+   |     ... A[2*j, 2*(i + j)]
+   |   endloop_j
+   | endloop_i
+   
+   the following constraints come from the iteration domain:
+
+   0 <= i <= Ni
+   0 <= i + di <= Ni
+   0 <= j <= Nj
+   0 <= j + dj <= Nj
+
+   where di, dj are the distance variables.  The constraints
+   representing the conflicting elements are:
+
+   i = 2 * (j + dj)
+   i + 1 = 2 * (i + di + j + dj)
+
+   For asking that the resulting distance vector (di, dj) be
+   lexicographically positive, we insert the constraint "di >= 0".  If
+   "di = 0" in the solution, we fix that component to zero, and we
+   look at the inner loops: we set a new problem where all the outer
+   loop distances are zero, and fix this inner component to be
+   positive.  When one of the components is positive, we save that
+   distance, and set a new problem where the distance on this loop is
+   zero, searching for other distances in the inner loops.  Here is
+   the classic example that illustrates that we have to set for each
+   inner loop a new problem:
+
+   | loop_1
+   |   loop_2
+   |     A[10]
+   |   endloop_2
+   | endloop_1
+
+   we have to save two distances (1, 0) and (0, 1).
+
+   Given two array references, refA and refB, we have to set the
+   dependence problem twice, refA vs. refB and refB vs. refA, and we
+   cannot do a single test, as refB might occur before refA in the
+   inner loops, and the contrary when considering outer loops: ex.
+
+   | loop_0
+   |   loop_1
+   |     loop_2
+   |       T[{1,+,1}_2][{1,+,1}_1]  // refA
+   |       T[{2,+,1}_2][{0,+,1}_1]  // refB
+   |     endloop_2
+   |   endloop_1
+   | endloop_0
+
+   refB touches the elements in T before refA, and thus for the same
+   loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
+   but for successive loop_0 iterations, we have (1, -1, 1)
+
+   The Omega solver expects the distance variables ("di" in the
+   previous example) to come first in the constraint system (as
+   variables to be protected, or "safe" variables), the constraint
+   system is built using the following layout:
+
+   "cst | distance vars | index vars".
+*/
+
+static bool
+init_omega_for_ddr (struct data_dependence_relation *ddr,
+		    bool *maybe_dependent)
+{
+  omega_pb pb;
+  bool res = false;
+
+  *maybe_dependent = true;
+
+  if (same_access_functions (ddr))
+    {
+      unsigned j;
+      lambda_vector dir_v;
+
+      /* Save the 0 vector.  */
+      save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+      dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
+      for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
+	dir_v[j] = dir_equal;
+      save_dir_v (ddr, dir_v);
+
+      /* Save the dependences carried by outer loops.  */
+      pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+      res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
+				  maybe_dependent);
+      omega_free_problem (pb);
+      return res;
+    }
+
+  /* Omega expects the protected variables (those that have to be kept
+     after elimination) to appear first in the constraint system.
+     These variables are the distance variables.  In the following
+     initialization we declare NB_LOOPS safe variables, and the total
+     number of variables for the constraint system is 2*NB_LOOPS.  */
+  pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+  res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
+			      maybe_dependent);
+  omega_free_problem (pb);
+
+  /* Stop computation if not decidable, or no dependence.  */
+  if (res == false || *maybe_dependent == false)
+    return res;
+
+  pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
+  res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
+			      maybe_dependent);
+  omega_free_problem (pb);
+
+  return res;
+}
+
+/* Return true when DDR contains the same information as that stored
+   in DIR_VECTS and in DIST_VECTS, return false otherwise.   */
+
+static bool
+ddr_consistent_p (FILE *file,
+		  struct data_dependence_relation *ddr,
+		  VEC (lambda_vector, heap) *dist_vects,
+		  VEC (lambda_vector, heap) *dir_vects)
+{
+  unsigned int i, j;
+
+  /* If dump_file is set, output there.  */
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    file = dump_file;
+
+  if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
+    {
+      lambda_vector b_dist_v;
+      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++)
+	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));
+
+      fprintf (file, "data dependence relation:\n");
+      dump_data_dependence_relation (file, ddr);
+
+      fprintf (file, ")\n");
+      return false;
+    }
+
+  if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
+    {
+      fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
+	       VEC_length (lambda_vector, dir_vects),
+	       DDR_NUM_DIR_VECTS (ddr));
+      return false;
+    }
+
+  for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
+    {
+      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++)
+	if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
+	  break;
+
+      if (j == VEC_length (lambda_vector, dist_vects))
+	{
+	  fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
+	  print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
+	  fprintf (file, "not found in Omega dist vectors:\n");
+	  print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
+	  fprintf (file, "data dependence relation:\n");
+	  dump_data_dependence_relation (file, ddr);
+	  fprintf (file, ")\n");
+	}
+    }
+
+  for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
+    {
+      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++)
+	if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
+	  break;
+
+      if (j == VEC_length (lambda_vector, dist_vects))
+	{
+	  fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
+	  print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
+	  fprintf (file, "not found in Omega dir vectors:\n");
+	  print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
+	  fprintf (file, "data dependence relation:\n");
+	  dump_data_dependence_relation (file, ddr);
+	  fprintf (file, ")\n");
+	}
+    }
+
+  return true;  
+}
+
+/* This computes the affine dependence relation between A and B with
+   respect to LOOP_NEST.  CHREC_KNOWN is used for representing the
+   independence between two accesses, while CHREC_DONT_KNOW is used
+   for representing the unknown relation.
+   
+   Note that it is possible to stop the computation of the dependence
+   relation the first time we detect a CHREC_KNOWN element for a given
+   subscript.  */
+
+static void
+compute_affine_dependence (struct data_dependence_relation *ddr,
+			   struct loop *loop_nest)
+{
+  struct data_reference *dra = DDR_A (ddr);
+  struct data_reference *drb = DDR_B (ddr);
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "(compute_affine_dependence\n");
+      fprintf (dump_file, "  (stmt_a = \n");
+      print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0);
+      fprintf (dump_file, ")\n  (stmt_b = \n");
+      print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0);
+      fprintf (dump_file, ")\n");
+    }
+
+  /* Analyze only when the dependence relation is not yet known.  */
+  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
+      && !DDR_SELF_REFERENCE (ddr))
+    {
+      dependence_stats.num_dependence_tests++;
+
+      if (access_functions_are_affine_or_constant_p (dra, loop_nest)
+	  && access_functions_are_affine_or_constant_p (drb, loop_nest))
+	{
+	  if (flag_check_data_deps)
+	    {
+	      /* Compute the dependences using the first algorithm.  */
+	      subscript_dependence_tester (ddr, loop_nest);
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "\n\nBanerjee Analyzer\n");
+		  dump_data_dependence_relation (dump_file, ddr);
+		}
+
+	      if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+		{
+		  bool maybe_dependent;
+		  VEC (lambda_vector, heap) *dir_vects, *dist_vects;
+
+		  /* Save the result of the first DD analyzer.  */
+		  dist_vects = DDR_DIST_VECTS (ddr);
+		  dir_vects = DDR_DIR_VECTS (ddr);
+
+		  /* Reset the information.  */
+		  DDR_DIST_VECTS (ddr) = NULL;
+		  DDR_DIR_VECTS (ddr) = NULL;
+
+		  /* Compute the same information using Omega.  */
+		  if (!init_omega_for_ddr (ddr, &maybe_dependent))
+		    goto csys_dont_know;
+
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    {
+		      fprintf (dump_file, "Omega Analyzer\n");
+		      dump_data_dependence_relation (dump_file, ddr);
+		    }
+
+		  /* Check that we get the same information.  */
+		  if (maybe_dependent)
+		    gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
+						  dir_vects));
+		}
+	    }
+	  else
+	    subscript_dependence_tester (ddr, loop_nest);
+	}
+     
+      /* As a last case, if the dependence cannot be determined, or if
+	 the dependence is considered too difficult to determine, answer
+	 "don't know".  */
+      else
+	{
+	csys_dont_know:;
+	  dependence_stats.num_dependence_undetermined++;
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Data ref a:\n");
+	      dump_data_reference (dump_file, dra);
+	      fprintf (dump_file, "Data ref b:\n");
+	      dump_data_reference (dump_file, drb);
+	      fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
+	    }
+	  finalize_ddr_dependent (ddr, chrec_dont_know);
+	}
+    }
+  
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, ")\n");
+}
+
+/* This computes the dependence relation for the same data
+   reference into DDR.  */
+
+static void
+compute_self_dependence (struct data_dependence_relation *ddr)
+{
+  unsigned int i;
+  struct subscript *subscript;
+
+  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
+    return;
+
+  for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
+       i++)
+    {
+      if (SUB_CONFLICTS_IN_A (subscript))
+	free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
+      if (SUB_CONFLICTS_IN_B (subscript))
+	free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
+
+      /* The accessed index overlaps for each iteration.  */
+      SUB_CONFLICTS_IN_A (subscript)
+	= conflict_fn (1, affine_fn_cst (integer_zero_node));
+      SUB_CONFLICTS_IN_B (subscript)
+	= conflict_fn (1, affine_fn_cst (integer_zero_node));
+      SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
+    }
+
+  /* The distance vector is the zero vector.  */
+  save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+  save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
+}
+
+/* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
+   the data references in DATAREFS, in the LOOP_NEST.  When
+   COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
+   relations.  */
+
+void 
+compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
+			 VEC (ddr_p, heap) **dependence_relations,
+			 VEC (loop_p, heap) *loop_nest,
+			 bool compute_self_and_rr)
+{
+  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 (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)
+	{
+	  ddr = initialize_data_dependence_relation (a, b, loop_nest);
+	  VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+	  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++)
+      {
+	ddr = initialize_data_dependence_relation (a, a, loop_nest);
+	VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+	compute_self_dependence (ddr);
+      }
+}
+
+/* Stores the locations of memory references in STMT to REFERENCES.  Returns
+   true if STMT clobbers memory, false otherwise.  */
+
+bool
+get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
+{
+  bool clobbers_memory = false;
+  data_ref_loc *ref;
+  tree *op0, *op1;
+  enum gimple_code stmt_code = gimple_code (stmt);
+
+  *references = NULL;
+
+  /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
+     Calls have side-effects, except those to const or pure
+     functions.  */
+  if ((stmt_code == GIMPLE_CALL
+       && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
+      || (stmt_code == GIMPLE_ASM
+	  && gimple_asm_volatile_p (stmt)))
+    clobbers_memory = true;
+
+  if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+    return clobbers_memory;
+
+  if (stmt_code == GIMPLE_ASSIGN)
+    {
+      tree base;
+      op0 = gimple_assign_lhs_ptr (stmt);
+      op1 = gimple_assign_rhs1_ptr (stmt);
+		
+      if (DECL_P (*op1)
+	  || (REFERENCE_CLASS_P (*op1)
+	      && (base = get_base_address (*op1))
+	      && TREE_CODE (base) != SSA_NAME))
+	{
+	  ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+	  ref->pos = op1;
+	  ref->is_read = true;
+	}
+
+      if (DECL_P (*op0)
+	  || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
+	{
+	  ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+	  ref->pos = op0;
+	  ref->is_read = false;
+	}
+    }
+  else if (stmt_code == GIMPLE_CALL)
+    {
+      unsigned i, n = gimple_call_num_args (stmt);
+
+      for (i = 0; i < n; i++)
+	{
+	  op0 = gimple_call_arg_ptr (stmt, i);
+
+	  if (DECL_P (*op0)
+	      || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
+	    {
+	      ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+	      ref->pos = op0;
+	      ref->is_read = true;
+	    }
+	}
+    }
+
+  return clobbers_memory;
+}
+
+/* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
+   reference, returns false, otherwise returns true.  NEST is the outermost
+   loop of the loop nest in which the references should be analyzed.  */
+
+bool
+find_data_references_in_stmt (struct loop *nest, gimple stmt,
+			      VEC (data_reference_p, heap) **datarefs)
+{
+  unsigned i;
+  VEC (data_ref_loc, heap) *references;
+  data_ref_loc *ref;
+  bool ret = true;
+  data_reference_p dr;
+
+  if (get_references_in_stmt (stmt, &references))
+    {
+      VEC_free (data_ref_loc, heap, references);
+      return false;
+    }
+
+  for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
+    {
+      dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
+      gcc_assert (dr != NULL);
+  
+      /* FIXME -- data dependence analysis does not work correctly for objects with
+	 invariant addresses.  Let us fail here until the problem is fixed.  */
+      if (dr_address_invariant_p (dr))
+	{
+	  free_data_ref (dr);
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "\tFAILED as dr address is invariant\n");
+	  ret = false;
+	  break;
+	}
+
+      VEC_safe_push (data_reference_p, heap, *datarefs, dr);
+    }
+  VEC_free (data_ref_loc, heap, references);
+  return ret;
+}
+
+/* Search the data references in LOOP, and record the information into
+   DATAREFS.  Returns chrec_dont_know when failing to analyze a
+   difficult case, returns NULL_TREE otherwise.
+
+   TODO: This function should be made smarter so that it can handle address
+   arithmetic as if they were array accesses, etc.  */
+
+tree 
+find_data_references_in_loop (struct loop *loop,
+			      VEC (data_reference_p, heap) **datarefs)
+{
+  basic_block bb, *bbs;
+  unsigned int i;
+  gimple_stmt_iterator bsi;
+
+  bbs = get_loop_body_in_dom_order (loop);
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      bb = bbs[i];
+
+      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	{
+	  gimple stmt = gsi_stmt (bsi);
+
+	  if (!find_data_references_in_stmt (loop, stmt, datarefs))
+	    {
+	      struct data_reference *res;
+	      res = XCNEW (struct data_reference);
+	      VEC_safe_push (data_reference_p, heap, *datarefs, res);
+
+	      free (bbs);
+	      return chrec_dont_know;
+	    }
+	}
+    }
+  free (bbs);
+
+  return NULL_TREE;
+}
+
+/* Recursive helper function.  */
+
+static bool
+find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
+{
+  /* Inner loops of the nest should not contain siblings.  Example:
+     when there are two consecutive loops,
+
+     | loop_0
+     |   loop_1
+     |     A[{0, +, 1}_1]
+     |   endloop_1
+     |   loop_2
+     |     A[{0, +, 1}_2]
+     |   endloop_2
+     | endloop_0
+
+     the dependence relation cannot be captured by the distance
+     abstraction.  */
+  if (loop->next)
+    return false;
+
+  VEC_safe_push (loop_p, heap, *loop_nest, loop);
+  if (loop->inner)
+    return find_loop_nest_1 (loop->inner, loop_nest);
+  return true;
+}
+
+/* Return false when the LOOP is not well nested.  Otherwise return
+   true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
+   contain the loops from the outermost to the innermost, as they will
+   appear in the classic distance vector.  */
+
+bool
+find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
+{
+  VEC_safe_push (loop_p, heap, *loop_nest, loop);
+  if (loop->inner)
+    return find_loop_nest_1 (loop->inner, loop_nest);
+  return true;
+}
+
+/* Returns true when the data dependences have been computed, false otherwise.
+   Given a loop nest LOOP, the following vectors are returned:
+   DATAREFS is initialized to all the array elements contained in this loop, 
+   DEPENDENCE_RELATIONS contains the relations between the data references.  
+   Compute read-read and self relations if 
+   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 (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_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);
+      VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+      res = false;
+    }
+  else
+    compute_all_dependences (*datarefs, dependence_relations, vloops,
+			     compute_self_and_read_read_dependences);
+
+  if (dump_file && (dump_flags & TDF_STATS))
+    {
+      fprintf (dump_file, "Dependence tester statistics:\n");
+
+      fprintf (dump_file, "Number of dependence tests: %d\n", 
+	       dependence_stats.num_dependence_tests);
+      fprintf (dump_file, "Number of dependence tests classified dependent: %d\n", 
+	       dependence_stats.num_dependence_dependent);
+      fprintf (dump_file, "Number of dependence tests classified independent: %d\n", 
+	       dependence_stats.num_dependence_independent);
+      fprintf (dump_file, "Number of undetermined dependence tests: %d\n", 
+	       dependence_stats.num_dependence_undetermined);
+
+      fprintf (dump_file, "Number of subscript tests: %d\n", 
+	       dependence_stats.num_subscript_tests);
+      fprintf (dump_file, "Number of undetermined subscript tests: %d\n", 
+	       dependence_stats.num_subscript_undetermined);
+      fprintf (dump_file, "Number of same subscript function: %d\n", 
+	       dependence_stats.num_same_subscript_function);
+
+      fprintf (dump_file, "Number of ziv tests: %d\n",
+	       dependence_stats.num_ziv);
+      fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
+	       dependence_stats.num_ziv_dependent);
+      fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
+	       dependence_stats.num_ziv_independent);
+      fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
+	       dependence_stats.num_ziv_unimplemented);      
+
+      fprintf (dump_file, "Number of siv tests: %d\n", 
+	       dependence_stats.num_siv);
+      fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
+	       dependence_stats.num_siv_dependent);
+      fprintf (dump_file, "Number of siv tests returning independent: %d\n",
+	       dependence_stats.num_siv_independent);
+      fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
+	       dependence_stats.num_siv_unimplemented);
+
+      fprintf (dump_file, "Number of miv tests: %d\n", 
+	       dependence_stats.num_miv);
+      fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
+	       dependence_stats.num_miv_dependent);
+      fprintf (dump_file, "Number of miv tests returning independent: %d\n",
+	       dependence_stats.num_miv_independent);
+      fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
+	       dependence_stats.num_miv_unimplemented);
+    }
+
+  return res;
+}
+
+/* Entry point (for testing only).  Analyze all the data references
+   and the dependence relations in LOOP.
+
+   The data references are computed first.  
+   
+   A relation on these nodes is represented by a complete graph.  Some
+   of the relations could be of no interest, thus the relations can be
+   computed on demand.
+   
+   In the following function we compute all the relations.  This is
+   just a first implementation that is here for:
+   - for showing how to ask for the dependence relations, 
+   - for the debugging the whole dependence graph,
+   - for the dejagnu testcases and maintenance.
+   
+   It is possible to ask only for a part of the graph, avoiding to
+   compute the whole dependence graph.  The computed dependences are
+   stored in a knowledge base (KB) such that later queries don't
+   recompute the same information.  The implementation of this KB is
+   transparent to the optimizer, and thus the KB can be changed with a
+   more efficient implementation, or the KB could be disabled.  */
+static void 
+analyze_all_data_dependences (struct loop *loop)
+{
+  unsigned int i;
+  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);
+
+  /* Compute DDs on the whole function.  */
+  compute_data_dependences_for_loop (loop, false, &datarefs,
+				     &dependence_relations);
+
+  if (dump_file)
+    {
+      dump_data_dependence_relations (dump_file, dependence_relations);
+      fprintf (dump_file, "\n\n");
+
+      if (dump_flags & TDF_DETAILS)
+	dump_dist_dir_vectors (dump_file, dependence_relations);
+
+      if (dump_flags & TDF_STATS)
+	{
+	  unsigned nb_top_relations = 0;
+	  unsigned nb_bot_relations = 0;
+	  unsigned nb_basename_differ = 0;
+	  unsigned nb_chrec_relations = 0;
+	  struct data_dependence_relation *ddr;
+
+	  for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+	    {
+	      if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
+		nb_top_relations++;
+	  
+	      else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+		{
+		  struct data_reference *a = DDR_A (ddr);
+		  struct data_reference *b = DDR_B (ddr);
+
+		  if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
+		    nb_basename_differ++;
+		  else
+		    nb_bot_relations++;
+		}
+	  
+	      else 
+		nb_chrec_relations++;
+	    }
+      
+	  gather_stats_on_scev_database ();
+	}
+    }
+
+  free_dependence_relations (dependence_relations);
+  free_data_refs (datarefs);
+}
+
+/* Computes all the data dependences and check that the results of
+   several analyzers are the same.  */
+
+void
+tree_check_data_deps (void)
+{
+  loop_iterator li;
+  struct loop *loop_nest;
+
+  FOR_EACH_LOOP (li, loop_nest, 0)
+    analyze_all_data_dependences (loop_nest);
+}
+
+/* Free the memory used by a data dependence relation DDR.  */
+
+void
+free_dependence_relation (struct data_dependence_relation *ddr)
+{
+  if (ddr == NULL)
+    return;
+
+  if (DDR_SUBSCRIPTS (ddr))
+    free_subscripts (DDR_SUBSCRIPTS (ddr));
+  if (DDR_DIST_VECTS (ddr))
+    VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
+  if (DDR_DIR_VECTS (ddr))
+    VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
+
+  free (ddr);
+}
+
+/* Free the memory used by the data dependence relations from
+   DEPENDENCE_RELATIONS.  */
+
+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 (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+    {
+      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.  */
+
+void
+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++)
+    free_data_ref (dr);
+  VEC_free (data_reference_p, heap, datarefs);
+}
+
+
+
+/* Dump vertex I in RDG to FILE.  */
+
+void
+dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
+{
+  struct vertex *v = &(rdg->vertices[i]);
+  struct graph_edge *e;
+
+  fprintf (file, "(vertex %d: (%s%s) (in:", i, 
+	   RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
+	   RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
+
+  if (v->pred)
+    for (e = v->pred; e; e = e->pred_next)
+      fprintf (file, " %d", e->src);
+
+  fprintf (file, ") (out:");
+
+  if (v->succ)
+    for (e = v->succ; e; e = e->succ_next)
+      fprintf (file, " %d", e->dest);
+
+  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_rdg_vertex (struct graph *rdg, int i)
+{
+  dump_rdg_vertex (stderr, rdg, i);
+}
+
+/* Dump component C of RDG to FILE.  If DUMPED is non-null, set the
+   dumped vertices to that bitmap.  */
+
+void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
+{
+  int i;
+
+  fprintf (file, "(%d\n", c);
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    if (rdg->vertices[i].component == c)
+      {
+	if (dumped)
+	  bitmap_set_bit (dumped, i);
+
+	dump_rdg_vertex (file, rdg, i);
+      }
+
+  fprintf (file, ")\n");
+}
+
+/* Call dump_rdg_vertex on stderr.  */
+
+void
+debug_rdg_component (struct graph *rdg, int c)
+{
+  dump_rdg_component (stderr, rdg, c, NULL);
+}
+
+/* Dump the reduced dependence graph RDG to FILE.  */
+
+void
+dump_rdg (FILE *file, struct graph *rdg)
+{
+  int i;
+  bitmap dumped = BITMAP_ALLOC (NULL);
+
+  fprintf (file, "(rdg\n");
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    if (!bitmap_bit_p (dumped, i))
+      dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
+
+  fprintf (file, ")\n");
+  BITMAP_FREE (dumped);
+}
+
+/* Call dump_rdg on stderr.  */
+
+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 SCOP using dotty.  */
+
+void
+dot_rdg (struct graph *rdg)
+{
+  FILE *file = fopen ("/tmp/rdg.dot", "w");
+  gcc_assert (file != NULL);
+
+  dot_rdg_1 (file, rdg);
+  fclose (file);
+
+  system ("dotty /tmp/rdg.dot");
+}
+
+
+/* This structure is used for recording the mapping statement index in
+   the RDG.  */
+
+struct rdg_vertex_info GTY(())
+{
+  gimple stmt;
+  int index;
+};
+
+/* Returns the index of STMT in RDG.  */
+
+int
+rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
+{
+  struct rdg_vertex_info rvi, *slot;
+
+  rvi.stmt = stmt;
+  slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
+
+  if (!slot)
+    return -1;
+
+  return slot->index;
+}
+
+/* Creates an edge in RDG for each distance vector from DDR.  The
+   order that we keep track of in the RDG is the order in which
+   statements have to be executed.  */
+
+static void
+create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+{
+  struct graph_edge *e;
+  int va, vb;
+  data_reference_p dra = DDR_A (ddr);
+  data_reference_p drb = DDR_B (ddr);
+  unsigned level = ddr_dependence_level (ddr);
+
+  /* For non scalar dependences, when the dependence is REVERSED,
+     statement B has to be executed before statement A.  */
+  if (level > 0
+      && !DDR_REVERSED_P (ddr))
+    {
+      data_reference_p tmp = dra;
+      dra = drb;
+      drb = tmp;
+    }
+
+  va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
+  vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
+
+  if (va < 0 || vb < 0)
+    return;
+
+  e = add_edge (rdg, va, vb);
+  e->data = XNEW (struct rdg_edge);
+
+  RDGE_LEVEL (e) = level;
+  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))
+    RDGE_TYPE (e) = output_dd;
+  else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
+    RDGE_TYPE (e) = flow_dd;
+  else if (DR_IS_READ (dra) && !DR_IS_READ (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.  */
+
+static void
+create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
+{
+  use_operand_p imm_use_p;
+  imm_use_iterator iterator;
+           
+  FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
+    {
+      struct graph_edge *e;
+      int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
+
+      if (use < 0)
+	continue;
+
+      e = add_edge (rdg, idef, use);
+      e->data = XNEW (struct rdg_edge);
+      RDGE_TYPE (e) = flow_dd;
+      RDGE_RELATION (e) = NULL;
+    }
+}
+
+/* Creates the edges of the reduced dependence graph RDG.  */
+
+static void
+create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
+{
+  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++)
+    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),
+			      iter, SSA_OP_DEF)
+      create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
+}
+
+/* Build the vertices of the reduced dependence graph RDG.  */
+
+void
+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++)
+    {
+      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);
+      struct rdg_vertex_info **slot;
+
+      rvi->stmt = stmt;
+      rvi->index = i;
+      slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
+
+      if (!*slot)
+	*slot = rvi;
+      else
+	free (rvi);
+
+      v->data = XNEW (struct rdg_vertex);
+      RDG_STMT (rdg, i) = stmt;
+
+      RDG_MEM_WRITE_STMT (rdg, i) = false;
+      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++)
+	if (!ref->is_read)
+	  RDG_MEM_WRITE_STMT (rdg, i) = true;
+	else
+	  RDG_MEM_READS_STMT (rdg, i) = true;
+
+      VEC_free (data_ref_loc, heap, references);
+    }
+}
+
+/* Initialize STMTS with all the statements of LOOP.  When
+   INCLUDE_PHIS is true, include also the PHI nodes.  The order in
+   which we discover statements is important as
+   generate_loops_for_partition is using the same traversal for
+   identifying statements. */
+
+static void
+stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
+{
+  unsigned int i;
+  basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = bbs[i];
+      gimple_stmt_iterator bsi;
+      gimple stmt;
+
+      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
+
+      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	{
+	  stmt = gsi_stmt (bsi);
+	  if (gimple_code (stmt) != GIMPLE_LABEL)
+	    VEC_safe_push (gimple, heap, *stmts, stmt);
+	}
+    }
+
+  free (bbs);
+}
+
+/* Returns true when all the dependences are computable.  */
+
+static bool
+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++)
+    if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+      return false;
+ 
+  return true;
+}
+
+/* Computes a hash function for element ELT.  */
+
+static hashval_t
+hash_stmt_vertex_info (const void *elt)
+{
+  const struct rdg_vertex_info *const rvi =
+    (const struct rdg_vertex_info *) elt;
+  gimple stmt = rvi->stmt;
+
+  return htab_hash_pointer (stmt);
+}
+
+/* Compares database elements E1 and E2.  */
+
+static int
+eq_stmt_vertex_info (const void *e1, const void *e2)
+{
+  const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
+  const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
+
+  return elt1->stmt == elt2->stmt;
+}
+
+/* Free the element E.  */
+
+static void
+hash_stmt_vertex_del (void *e)
+{
+  free (e);
+}
+
+/* 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_empty_rdg (int n_stmts)
+{
+  int nb_data_refs = 10;
+  struct graph *rdg = new_graph (n_stmts);
+
+  rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
+			      eq_stmt_vertex_info, hash_stmt_vertex_del);
+  return rdg;
+}
+
+/* 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)
+{
+  int nb_data_refs = 10;
+  struct graph *rdg = NULL;
+  VEC (ddr_p, heap) *dependence_relations;
+  VEC (data_reference_p, heap) *datarefs;
+  VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
+  
+  dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
+  datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
+  compute_data_dependences_for_loop (loop, 
+                                     false,
+                                     &datarefs,
+                                     &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 the reduced dependence graph RDG.  */
+
+void
+free_rdg (struct graph *rdg)
+{
+  int i;
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    free (rdg->vertices[i].data);
+
+  htab_delete (rdg->indices);
+  free_graph (rdg);
+}
+
+/* Initialize STMTS with all the statements of LOOP that contain a
+   store to memory.  */
+
+void
+stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
+{
+  unsigned int i;
+  basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = bbs[i];
+      gimple_stmt_iterator bsi;
+
+      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF))
+	  VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
+    }
+
+  free (bbs);
+}
+
+/* For a data reference REF, return the declaration of its base
+   address or NULL_TREE if the base is not determined.  */
+
+static inline tree
+ref_base_address (gimple stmt, data_ref_loc *ref)
+{
+  tree base = NULL_TREE;
+  tree base_address;
+  struct data_reference *dr = XCNEW (struct data_reference);
+
+  DR_STMT (dr) = stmt;
+  DR_REF (dr) = *ref->pos;
+  dr_analyze_innermost (dr);
+  base_address = DR_BASE_ADDRESS (dr);
+
+  if (!base_address)
+    goto end;
+
+  switch (TREE_CODE (base_address))
+    {
+    case ADDR_EXPR:
+      base = TREE_OPERAND (base_address, 0);
+      break;
+
+    default:
+      base = base_address;
+      break;
+    }
+
+ end:
+  free_data_ref (dr);
+  return base;
+}
+
+/* Determines whether the statement from vertex V of the RDG has a
+   definition used outside the loop that contains this statement.  */
+
+bool
+rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
+{
+  gimple stmt = RDG_STMT (rdg, v);
+  struct loop *loop = loop_containing_stmt (stmt);
+  use_operand_p imm_use_p;
+  imm_use_iterator iterator;
+  ssa_op_iter it;
+  def_operand_p def_p;
+
+  if (!loop)
+    return true;
+
+  FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
+    {
+      FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
+	{
+	  if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
+	    return true;
+	}
+    }
+
+  return false;
+}
+
+/* Determines whether statements S1 and S2 access to similar memory
+   locations.  Two memory accesses are considered similar when they
+   have the same base address declaration, i.e. when their
+   ref_base_address is the same.  */
+
+bool
+have_similar_memory_accesses (gimple s1, gimple s2)
+{
+  bool res = false;
+  unsigned i, j;
+  VEC (data_ref_loc, heap) *refs1, *refs2;
+  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++)
+    {
+      tree base1 = ref_base_address (s1, ref1);
+
+      if (base1)
+	for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
+	  if (base1 == ref_base_address (s2, ref2))
+	    {
+	      res = true;
+	      goto end;
+	    }
+    }
+
+ end:
+  VEC_free (data_ref_loc, heap, refs1);
+  VEC_free (data_ref_loc, heap, refs2);
+  return res;
+}
+
+/* Helper function for the hashtab.  */
+
+static int
+have_similar_memory_accesses_1 (const void *s1, const void *s2)
+{
+  return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
+				       CONST_CAST_GIMPLE ((const_gimple) s2));
+}
+
+/* Helper function for the hashtab.  */
+
+static hashval_t
+ref_base_address_1 (const void *s)
+{
+  gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
+  unsigned i;
+  VEC (data_ref_loc, heap) *refs;
+  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++)
+    if (!ref->is_read)
+      {
+	res = htab_hash_pointer (ref_base_address (stmt, ref));
+	break;
+      }
+
+  VEC_free (data_ref_loc, heap, refs);
+  return res;
+}
+
+/* Try to remove duplicated write data references from STMTS.  */
+
+void
+remove_similar_memory_refs (VEC (gimple, heap) **stmts)
+{
+  unsigned i;
+  gimple stmt;
+  htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
+			     have_similar_memory_accesses_1, NULL);
+
+  for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
+    {
+      void **slot;
+
+      slot = htab_find_slot (seen, stmt, INSERT);
+
+      if (*slot)
+	VEC_ordered_remove (gimple, *stmts, i);
+      else
+	{
+	  *slot = (void *) stmt;
+	  i++;
+	}
+    }
+
+  htab_delete (seen);
+}
+
+/* Returns the index of PARAMETER in the parameters vector of the
+   ACCESS_MATRIX.  If PARAMETER does not exist return -1.  */
+
+int 
+access_matrix_get_index_for_parameter (tree parameter, 
+				       struct access_matrix *access_matrix)
+{
+  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++)
+    if (lambda_parameter == parameter)
+      return i + AM_NB_INDUCTION_VARS (access_matrix);
+
+  return -1;
+}