tree-data-ref.c (dump_subscript): Use dump_conflict_function.

	* tree-data-ref.c (dump_subscript): Use dump_conflict_function.
	(compute_subscript_distance, initialize_data_dependence_relation,
	finalize_ddr_dependent, analyze_ziv_subscript,
	analyze_siv_subscript_cst_affine,
	compute_overlap_steps_for_affine_univar,
	compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine,
	analyze_siv_subscript, analyze_miv_subscript,
	analyze_overlapping_iterations, subscript_dependence_tester_1,
	compute_self_dependence, free_dependence_relation): Work
	with affine_fn instead of chrecs.
	(dump_affine_function, dump_conflict_function, affine_function_equal_p,
	common_affine_function, affine_function_base,
	affine_function_constant_p, affine_fn_op, affine_fn_plus,
	affine_fn_minus, affine_fn_free, conflict_fn_not_known,
	conflict_fn_no_dependence, free_conflict_function, free_subscripts,
	conflict_fn, affine_fn_cst, affine_fn_univar): New functions.
	(all_chrecs_equal_p): Removed.
	* tree-data-ref.h (affine_fn, conflict_function): New types.
	(struct subscript): Change type of conflicting_iterations_in_a
	and conflicting_iterations_in_b.

From-SVN: r121212

1 files changed, 474 insertions, 239 deletions

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 4d60da027bb..2da59db43ff 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -626,35 +626,66 @@ dump_data_reference (FILE *outf,
   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)
 {
-  tree chrec = SUB_CONFLICTS_IN_A (subscript);
+  conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
 
   fprintf (outf, "\n (subscript \n");
   fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
-  print_generic_stmt (outf, chrec, 0);
-  if (chrec == chrec_known)
-    fprintf (outf, "    (no dependence)\n");
-  else if (chrec_contains_undetermined (chrec))
-    fprintf (outf, "    (don't know)\n");
-  else
+  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);
     }
 	  
-  chrec = SUB_CONFLICTS_IN_B (subscript);
+  cf = SUB_CONFLICTS_IN_B (subscript);
   fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
-  print_generic_stmt (outf, chrec, 0);
-  if (chrec == chrec_known)
-    fprintf (outf, "    (no dependence)\n");
-  else if (chrec_contains_undetermined (chrec))
-    fprintf (outf, "    (don't know)\n");
-  else
+  dump_conflict_function (outf, cf);
+  if (CF_NONTRIVIAL_P (cf))
     {
       tree last_iteration = SUB_LAST_CONFLICT (subscript);
       fprintf (outf, "  last_conflict: ");
@@ -2003,80 +2034,193 @@ create_data_ref (tree memref, tree stmt, bool is_read)
   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);
 
-/* Returns true when all the functions of a tree_vec CHREC are the
-   same.  */
+  gcc_assert (n == VEC_length (tree, fnb));
 
-static bool 
-all_chrecs_equal_p (tree chrec)
+  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)
 {
-  int j;
+  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;
+}
 
-  for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
-    if (!eq_evolutions_p (TREE_VEC_ELT (chrec, j),
-			  TREE_VEC_ELT (chrec, j + 1)))
+/* 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;
 }
 
+/* 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++)
+    VEC_quick_push (tree, ret,
+		    fold_build2 (op, integer_type_node,
+				 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, integer_type_node,
+				 coef, integer_zero_node));
+  for (; VEC_iterate (tree, fnb, i, coef); i++)
+    VEC_quick_push (tree, ret,
+		    fold_build2 (op, integer_type_node,
+				 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++)
  	{
- 	  tree conflicts_a, conflicts_b, difference;
  	  struct subscript *subscript;
  	  
  	  subscript = DDR_SUBSCRIPT (ddr, i);
- 	  conflicts_a = SUB_CONFLICTS_IN_A (subscript);
- 	  conflicts_b = SUB_CONFLICTS_IN_B (subscript);
+ 	  cf_a = SUB_CONFLICTS_IN_A (subscript);
+ 	  cf_b = SUB_CONFLICTS_IN_B (subscript);
 
-	  if (TREE_CODE (conflicts_a) == TREE_VEC)
+	  fn_a = common_affine_function (cf_a);
+	  fn_b = common_affine_function (cf_b);
+	  if (!fn_a || !fn_b)
 	    {
-	      if (!all_chrecs_equal_p (conflicts_a))
-		{
-		  SUB_DISTANCE (subscript) = chrec_dont_know;
-		  return;
-		}
-	      else
-		conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
-	    }
-
-	  if (TREE_CODE (conflicts_b) == TREE_VEC)
-	    {
-	      if (!all_chrecs_equal_p (conflicts_b))
-		{
-		  SUB_DISTANCE (subscript) = chrec_dont_know;
-		  return;
-		}
-	      else
-		conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
+	      SUB_DISTANCE (subscript) = chrec_dont_know;
+	      return;
 	    }
-
-	  conflicts_b = chrec_convert (integer_type_node, conflicts_b,
-				       NULL_TREE);
-	  conflicts_a = chrec_convert (integer_type_node, conflicts_a,
-				       NULL_TREE);
-	  difference = chrec_fold_minus 
-	    (integer_type_node, conflicts_b, conflicts_a);
- 	  
- 	  if (evolution_function_is_constant_p (difference))
- 	    SUB_DISTANCE (subscript) = difference;
+	  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;
+}
+
 /* 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.  */
@@ -2141,8 +2285,8 @@ initialize_data_dependence_relation (struct data_reference *a,
       struct subscript *subscript;
 	  
       subscript = XNEW (struct subscript);
-      SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
-      SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
+      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);
@@ -2151,6 +2295,37 @@ initialize_data_dependence_relation (struct data_reference *a,
   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);
+    }
+  VEC_free (subscript_p, heap, subscripts);
+}
+
 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
    description.  */
 
@@ -2166,7 +2341,7 @@ finalize_ddr_dependent (struct data_dependence_relation *ddr,
     }
 
   DDR_ARE_DEPENDENT (ddr) = chrec;  
-  VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
+  free_subscripts (DDR_SUBSCRIPTS (ddr));
 }
 
 /* The dependence relation DDR cannot be represented by a distance
@@ -2233,6 +2408,52 @@ siv_subscript_p (tree chrec_a,
   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;
+
+  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
@@ -2243,8 +2464,8 @@ siv_subscript_p (tree chrec_a,
 static void 
 analyze_ziv_subscript (tree chrec_a, 
 		       tree chrec_b, 
-		       tree *overlaps_a,
-		       tree *overlaps_b, 
+		       conflict_function **overlaps_a,
+		       conflict_function **overlaps_b, 
 		       tree *last_conflicts)
 {
   tree difference;
@@ -2264,16 +2485,16 @@ analyze_ziv_subscript (tree chrec_a,
 	{
 	  /* The difference is equal to zero: the accessed index
 	     overlaps for each iteration in the loop.  */
-	  *overlaps_a = integer_zero_node;
-	  *overlaps_b = integer_zero_node;
+	  *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 = chrec_known;
-	  *overlaps_b = chrec_known;
+	  *overlaps_a = conflict_fn_no_dependence ();
+	  *overlaps_b = conflict_fn_no_dependence ();
 	  *last_conflicts = integer_zero_node;
 	  dependence_stats.num_ziv_independent++;
 	}
@@ -2285,8 +2506,8 @@ analyze_ziv_subscript (tree chrec_a,
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
 
-      *overlaps_a = chrec_dont_know;
-      *overlaps_b = chrec_dont_know;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
       *last_conflicts = chrec_dont_know;
       dependence_stats.num_ziv_unimplemented++;
       break;
@@ -2330,12 +2551,12 @@ get_number_of_iters_for_loop (int loopnum)
 static void
 analyze_siv_subscript_cst_affine (tree chrec_a, 
 				  tree chrec_b,
-				  tree *overlaps_a, 
-				  tree *overlaps_b, 
+				  conflict_function **overlaps_a, 
+				  conflict_function **overlaps_b, 
 				  tree *last_conflicts)
 {
   bool value0, value1, value2;
-  tree difference;
+  tree difference, tmp;
 
   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
@@ -2348,8 +2569,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 	fprintf (dump_file, "siv test failed: chrec is not positive.\n"); 
 
       dependence_stats.num_siv_unimplemented++;
-      *overlaps_a = chrec_dont_know;
-      *overlaps_b = chrec_dont_know;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
       *last_conflicts = chrec_dont_know;
       return;
     }
@@ -2362,8 +2583,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file, "siv test failed: chrec not positive.\n");
 
-	      *overlaps_a = chrec_dont_know;
-	      *overlaps_b = chrec_dont_know;      
+	      *overlaps_a = conflict_fn_not_known ();
+	      *overlaps_b = conflict_fn_not_known ();      
 	      *last_conflicts = chrec_dont_know;
 	      dependence_stats.num_siv_unimplemented++;
 	      return;
@@ -2382,12 +2603,13 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		      tree numiter;
 		      int loopnum = CHREC_VARIABLE (chrec_b);
 
-		      *overlaps_a = integer_zero_node;
-		      *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
-						 fold_build1 (ABS_EXPR,
-							      integer_type_node,
-							      difference),
-						 CHREC_RIGHT (chrec_b));
+		      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+		      tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
+					 fold_build1 (ABS_EXPR,
+						      integer_type_node,
+						      difference),
+					 CHREC_RIGHT (chrec_b));
+		      *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
 		      *last_conflicts = integer_one_node;
 		      
 
@@ -2396,11 +2618,13 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		      numiter = get_number_of_iters_for_loop (loopnum);
 
 		      if (numiter != NULL_TREE
-			  && TREE_CODE (*overlaps_b) == INTEGER_CST
-			  && tree_int_cst_lt (numiter, *overlaps_b))
+			  && TREE_CODE (tmp) == INTEGER_CST
+			  && tree_int_cst_lt (numiter, tmp))
 			{
-			  *overlaps_a = chrec_known;
-			  *overlaps_b = chrec_known;
+			  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;
@@ -2413,8 +2637,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		     no overlaps.  */
 		  else
 		    {
-		      *overlaps_a = chrec_known;
-		      *overlaps_b = chrec_known;      
+		      *overlaps_a = conflict_fn_no_dependence ();
+		      *overlaps_b = conflict_fn_no_dependence ();      
 		      *last_conflicts = integer_zero_node;
 		      dependence_stats.num_siv_independent++;
 		      return;
@@ -2428,8 +2652,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		     chrec_b = {10, +, -1}
 		     
 		     In this case, chrec_a will not overlap with chrec_b.  */
-		  *overlaps_a = chrec_known;
-		  *overlaps_b = chrec_known;
+		  *overlaps_a = conflict_fn_no_dependence ();
+		  *overlaps_b = conflict_fn_no_dependence ();
 		  *last_conflicts = integer_zero_node;
 		  dependence_stats.num_siv_independent++;
 		  return;
@@ -2443,8 +2667,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file, "siv test failed: chrec not positive.\n");
 
-	      *overlaps_a = chrec_dont_know;
-	      *overlaps_b = chrec_dont_know;      
+	      *overlaps_a = conflict_fn_not_known ();
+	      *overlaps_b = conflict_fn_not_known ();      
 	      *last_conflicts = chrec_dont_know;
 	      dependence_stats.num_siv_unimplemented++;
 	      return;
@@ -2462,10 +2686,11 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		      tree numiter;
 		      int loopnum = CHREC_VARIABLE (chrec_b);
 
-		      *overlaps_a = integer_zero_node;
-		      *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
-				      		 integer_type_node, difference, 
-						 CHREC_RIGHT (chrec_b));
+		      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+		      tmp = fold_build2 (EXACT_DIV_EXPR,
+					 integer_type_node, 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
@@ -2473,11 +2698,13 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		      numiter = get_number_of_iters_for_loop (loopnum);
 
 		      if (numiter != NULL_TREE
-			  && TREE_CODE (*overlaps_b) == INTEGER_CST
-			  && tree_int_cst_lt (numiter, *overlaps_b))
+			  && TREE_CODE (tmp) == INTEGER_CST
+			  && tree_int_cst_lt (numiter, tmp))
 			{
-			  *overlaps_a = chrec_known;
-			  *overlaps_b = chrec_known;
+			  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;
@@ -2490,8 +2717,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		     are no overlaps.  */
 		  else
 		    {
-		      *overlaps_a = chrec_known;
-		      *overlaps_b = chrec_known;      
+		      *overlaps_a = conflict_fn_no_dependence ();
+		      *overlaps_b = conflict_fn_no_dependence ();      
 		      *last_conflicts = integer_zero_node;
 		      dependence_stats.num_siv_independent++;
 		      return;
@@ -2504,8 +2731,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a,
 		     chrec_b = {4, +, 1}
 		 
 		     In this case, chrec_a will not overlap with chrec_b.  */
-		  *overlaps_a = chrec_known;
-		  *overlaps_b = chrec_known;
+		  *overlaps_a = conflict_fn_no_dependence ();
+		  *overlaps_b = conflict_fn_no_dependence ();
 		  *last_conflicts = integer_zero_node;
 		  dependence_stats.num_siv_independent++;
 		  return;
@@ -2541,7 +2768,8 @@ initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
 
 static void
 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, 
-					 tree *overlaps_a, tree *overlaps_b, 
+					 affine_fn *overlaps_a,
+					 affine_fn *overlaps_b, 
 					 tree *last_conflicts, int dim)
 {
   if (((step_a > 0 && step_b > 0)
@@ -2558,24 +2786,23 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
       last_conflict = tau2;
 
-      *overlaps_a = build_polynomial_chrec
-	(dim, integer_zero_node,
-	 build_int_cst (NULL_TREE, step_overlaps_a));
-      *overlaps_b = build_polynomial_chrec
-	(dim, integer_zero_node,
-	 build_int_cst (NULL_TREE, step_overlaps_b));
+      *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));
       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
     }
 
   else
     {
-      *overlaps_a = integer_zero_node;
-      *overlaps_b = integer_zero_node;
+      *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, 
@@ -2593,16 +2820,19 @@ compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
 
 static void
 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 
-				      tree *overlaps_a, tree *overlaps_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;
   int niter_x, niter_y, niter_z, niter;
   tree numiter_x, numiter_y, numiter_z;
-  tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
-  tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
-  tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
+  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));
@@ -2618,8 +2848,8 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
 	   
-      *overlaps_a = chrec_dont_know;
-      *overlaps_b = chrec_dont_know;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
       *last_conflicts = chrec_dont_know;
       return;
     }
@@ -2651,67 +2881,61 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
 
   if (xz_p || yz_p || xyz_p)
     {
-      *overlaps_a = make_tree_vec (2);
-      TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
-      TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
-      *overlaps_b = integer_zero_node;
+      ova1 = affine_fn_cst (integer_zero_node);
+      ova2 = affine_fn_cst (integer_zero_node);
+      ovb = affine_fn_cst (integer_zero_node);
       if (xz_p)
 	{
-	  tree t0 = chrec_convert (integer_type_node, 
-				   TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
-	  tree t1 = chrec_convert (integer_type_node, overlaps_a_xz,
-				   NULL_TREE);
-	  tree t2 = chrec_convert (integer_type_node, *overlaps_b,
-				   NULL_TREE);
-	  tree t3 = chrec_convert (integer_type_node, overlaps_b_xz,
-				   NULL_TREE);
-
-	  TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
-							   t0, t1);
-	  *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
+	  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)
 	{
-	  tree t0 = chrec_convert (integer_type_node,
-				   TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
-	  tree t1 = chrec_convert (integer_type_node, overlaps_a_yz, NULL_TREE);
-	  tree t2 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
-	  tree t3 = chrec_convert (integer_type_node, overlaps_b_yz, NULL_TREE);
-
-	  TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
-							   t0, t1);
-	  *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3);
+	  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)
 	{
-	  tree t0 = chrec_convert (integer_type_node,
-				   TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE);
-	  tree t1 = chrec_convert (integer_type_node, overlaps_a_xyz,
-				   NULL_TREE);
-	  tree t2 = chrec_convert (integer_type_node,
-				   TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE);
-	  tree t3 = chrec_convert (integer_type_node, overlaps_a_xyz,
-				   NULL_TREE);
-	  tree t4 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE);
-	  tree t5 = chrec_convert (integer_type_node, overlaps_b_xyz,
-				   NULL_TREE);
-
-	  TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node,
-							   t0, t1);
-	  TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node,
-							   t2, t3);
-	  *overlaps_b = chrec_fold_plus (integer_type_node, t4, t5);
+	  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 = integer_zero_node;
-      *overlaps_b = integer_zero_node;
+      *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
@@ -2722,8 +2946,8 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
 static void
 analyze_subscript_affine_affine (tree chrec_a, 
 				 tree chrec_b,
-				 tree *overlaps_a, 
-				 tree *overlaps_b, 
+				 conflict_function **overlaps_a, 
+				 conflict_function **overlaps_b, 
 				 tree *last_conflicts)
 {
   unsigned nb_vars_a, nb_vars_b, dim;
@@ -2735,8 +2959,8 @@ analyze_subscript_affine_affine (tree chrec_a,
     {
       /* The accessed index overlaps for each iteration in the
 	 loop.  */
-      *overlaps_a = integer_zero_node;
-      *overlaps_b = integer_zero_node;
+      *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;
     }
@@ -2781,6 +3005,7 @@ analyze_subscript_affine_affine (tree chrec_a,
 	  int step_a, step_b;
 	  int niter, niter_a, niter_b;
 	  tree numiter_a, numiter_b;
+	  affine_fn ova, ovb;
 
 	  numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
 	  numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
@@ -2788,8 +3013,8 @@ analyze_subscript_affine_affine (tree chrec_a,
 	    {
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
-	      *overlaps_a = chrec_dont_know;
-	      *overlaps_b = chrec_dont_know;
+	      *overlaps_a = conflict_fn_not_known ();
+	      *overlaps_b = conflict_fn_not_known ();
 	      *last_conflicts = chrec_dont_know;
 	      goto end_analyze_subs_aa;
 	    }
@@ -2802,8 +3027,10 @@ analyze_subscript_affine_affine (tree chrec_a,
 	  step_b = int_cst_value (CHREC_RIGHT (chrec_b));
 
 	  compute_overlap_steps_for_affine_univar (niter, step_a, step_b, 
-						   overlaps_a, overlaps_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)
@@ -2818,8 +3045,8 @@ analyze_subscript_affine_affine (tree chrec_a,
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    fprintf (dump_file, "affine-affine test failed: too many variables.\n");
-	  *overlaps_a = chrec_dont_know;
-	  *overlaps_b = chrec_dont_know;
+	  *overlaps_a = conflict_fn_not_known ();
+	  *overlaps_b = conflict_fn_not_known ();
 	  *last_conflicts = chrec_dont_know;
 	}
       goto end_analyze_subs_aa;
@@ -2840,8 +3067,8 @@ analyze_subscript_affine_affine (tree chrec_a,
      don't know.  */
   if (gcd_alpha_beta == 0)
     {
-      *overlaps_a = chrec_dont_know;
-      *overlaps_b = chrec_dont_know;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
       *last_conflicts = chrec_dont_know;
       goto end_analyze_subs_aa;
     }
@@ -2851,8 +3078,8 @@ analyze_subscript_affine_affine (tree chrec_a,
     {
       /* The "gcd-test" has determined that there is no integer
 	 solution, i.e. there is no dependence.  */
-      *overlaps_a = chrec_known;
-      *overlaps_b = chrec_known;
+      *overlaps_a = conflict_fn_no_dependence ();
+      *overlaps_b = conflict_fn_no_dependence ();
       *last_conflicts = integer_zero_node;
     }
 
@@ -2896,8 +3123,8 @@ analyze_subscript_affine_affine (tree chrec_a,
 	    {
 	      if (dump_file && (dump_flags & TDF_DETAILS))
 		fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
-	      *overlaps_a = chrec_dont_know;
-	      *overlaps_b = chrec_dont_know;
+	      *overlaps_a = conflict_fn_not_known ();
+	      *overlaps_b = conflict_fn_not_known ();
 	      *last_conflicts = chrec_dont_know;
 	      goto end_analyze_subs_aa;
 	    }
@@ -2918,8 +3145,8 @@ analyze_subscript_affine_affine (tree chrec_a,
 		 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 = chrec_known;
-	      *overlaps_b = chrec_known;
+	      *overlaps_a = conflict_fn_no_dependence ();
+	      *overlaps_b = conflict_fn_no_dependence ();
 	      *last_conflicts = integer_zero_node;
 	    }
 
@@ -2954,20 +3181,22 @@ analyze_subscript_affine_affine (tree chrec_a,
 			 loop, there is no dependence.  */
 		      if (x0 > niter || y0  > niter)
 			{
-			  *overlaps_a = chrec_known;
-			  *overlaps_b = chrec_known;
+			  *overlaps_a = conflict_fn_no_dependence ();
+			  *overlaps_b = conflict_fn_no_dependence ();
 			  *last_conflicts = integer_zero_node;
 			}
 		      else
 			{
-			  *overlaps_a = build_polynomial_chrec
-			    (1,
-			     build_int_cst (NULL_TREE, x0),
-			     build_int_cst (NULL_TREE, i1));
-			  *overlaps_b = build_polynomial_chrec
-			    (1,
-			     build_int_cst (NULL_TREE, y0),
-			     build_int_cst (NULL_TREE, j1));
+			  *overlaps_a
+			    = conflict_fn (1,
+				affine_fn_univar (build_int_cst (NULL_TREE, x0),
+						  1,
+						  build_int_cst (NULL_TREE, i1)));
+			  *overlaps_b
+			    = conflict_fn (1,
+				affine_fn_univar (build_int_cst (NULL_TREE, y0),
+						  1,
+						  build_int_cst (NULL_TREE, j1)));
 			  *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
 			}
 		    }
@@ -2977,8 +3206,8 @@ analyze_subscript_affine_affine (tree chrec_a,
 			 iteration domain for j is not checked.  */
 		      if (dump_file && (dump_flags & TDF_DETAILS))
 			fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
-		      *overlaps_a = chrec_dont_know;
-		      *overlaps_b = chrec_dont_know;
+		      *overlaps_a = conflict_fn_not_known ();
+		      *overlaps_b = conflict_fn_not_known ();
 		      *last_conflicts = chrec_dont_know;
 		    }
 		}
@@ -2989,8 +3218,8 @@ analyze_subscript_affine_affine (tree chrec_a,
 		     iteration domain for i is not checked.  */
 		  if (dump_file && (dump_flags & TDF_DETAILS))
 		    fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
-		  *overlaps_a = chrec_dont_know;
-		  *overlaps_b = chrec_dont_know;
+		  *overlaps_a = conflict_fn_not_known ();
+		  *overlaps_b = conflict_fn_not_known ();
 		  *last_conflicts = chrec_dont_know;
 		}
 	    }
@@ -2999,8 +3228,8 @@ analyze_subscript_affine_affine (tree chrec_a,
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
-	  *overlaps_a = chrec_dont_know;
-	  *overlaps_b = chrec_dont_know;
+	  *overlaps_a = conflict_fn_not_known ();
+	  *overlaps_b = conflict_fn_not_known ();
 	  *last_conflicts = chrec_dont_know;
 	}
     }
@@ -3009,8 +3238,8 @@ analyze_subscript_affine_affine (tree chrec_a,
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
-      *overlaps_a = chrec_dont_know;
-      *overlaps_b = chrec_dont_know;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
       *last_conflicts = chrec_dont_know;
     }
 
@@ -3018,9 +3247,9 @@ end_analyze_subs_aa:
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "  (overlaps_a = ");
-      print_generic_expr (dump_file, *overlaps_a, 0);
+      dump_conflict_function (dump_file, *overlaps_a);
       fprintf (dump_file, ")\n  (overlaps_b = ");
-      print_generic_expr (dump_file, *overlaps_b, 0);
+      dump_conflict_function (dump_file, *overlaps_b);
       fprintf (dump_file, ")\n");
       fprintf (dump_file, ")\n");
     }
@@ -3080,8 +3309,8 @@ can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
 static void
 analyze_siv_subscript (tree chrec_a, 
 		       tree chrec_b,
-		       tree *overlaps_a, 
-		       tree *overlaps_b, 
+		       conflict_function **overlaps_a, 
+		       conflict_function **overlaps_b, 
 		       tree *last_conflicts)
 {
   dependence_stats.num_siv++;
@@ -3109,11 +3338,11 @@ analyze_siv_subscript (tree chrec_a,
 					   overlaps_a, overlaps_b, 
 					   last_conflicts);
 
-	  if (*overlaps_a == chrec_dont_know
-	      || *overlaps_b == chrec_dont_know)
+	  if (CF_NOT_KNOWN_P (*overlaps_a)
+	      || CF_NOT_KNOWN_P (*overlaps_b))
 	    dependence_stats.num_siv_unimplemented++;
-	  else if (*overlaps_a == chrec_known
-		   || *overlaps_b == chrec_known)
+	  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++;
@@ -3128,11 +3357,11 @@ analyze_siv_subscript (tree chrec_a,
 	     Compute it properly.  */
 	  *last_conflicts = chrec_dont_know;
 
-	  if (*overlaps_a == chrec_dont_know
-	      || *overlaps_b == chrec_dont_know)
+	  if (CF_NOT_KNOWN_P (*overlaps_a)
+	      || CF_NOT_KNOWN_P (*overlaps_b))
 	    dependence_stats.num_siv_unimplemented++;
-	  else if (*overlaps_a == chrec_known
-		   || *overlaps_b == chrec_known)
+	  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++;
@@ -3146,8 +3375,8 @@ analyze_siv_subscript (tree chrec_a,
     siv_subscript_dontknow:;
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "siv test failed: unimplemented.\n");
-      *overlaps_a = chrec_dont_know;
-      *overlaps_b = chrec_dont_know;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
       *last_conflicts = chrec_dont_know;
       dependence_stats.num_siv_unimplemented++;
     }
@@ -3198,8 +3427,8 @@ chrec_steps_divide_constant_p (tree chrec,
 static void
 analyze_miv_subscript (tree chrec_a, 
 		       tree chrec_b, 
-		       tree *overlaps_a, 
-		       tree *overlaps_b, 
+		       conflict_function **overlaps_a, 
+		       conflict_function **overlaps_b, 
 		       tree *last_conflicts)
 {
   /* FIXME:  This is a MIV subscript, not yet handled.
@@ -3224,8 +3453,8 @@ analyze_miv_subscript (tree chrec_a,
     {
       /* Access functions are the same: all the elements are accessed
 	 in the same order.  */
-      *overlaps_a = integer_zero_node;
-      *overlaps_b = integer_zero_node;
+      *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
+      *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
       *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
       dependence_stats.num_miv_dependent++;
     }
@@ -3241,8 +3470,8 @@ analyze_miv_subscript (tree chrec_a,
 	 
 	 The difference is 1, and the evolution steps are equal to 2,
 	 consequently there are no overlapping elements.  */
-      *overlaps_a = chrec_known;
-      *overlaps_b = chrec_known;
+      *overlaps_a = conflict_fn_no_dependence ();
+      *overlaps_b = conflict_fn_no_dependence ();
       *last_conflicts = integer_zero_node;
       dependence_stats.num_miv_independent++;
     }
@@ -3269,11 +3498,11 @@ analyze_miv_subscript (tree chrec_a,
       analyze_subscript_affine_affine (chrec_a, chrec_b, 
 				       overlaps_a, overlaps_b, last_conflicts);
 
-      if (*overlaps_a == chrec_dont_know
-	  || *overlaps_b == chrec_dont_know)
+      if (CF_NOT_KNOWN_P (*overlaps_a)
+ 	  || CF_NOT_KNOWN_P (*overlaps_b))
 	dependence_stats.num_miv_unimplemented++;
-      else if (*overlaps_a == chrec_known
-	       || *overlaps_b == chrec_known)
+      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++;
@@ -3285,8 +3514,8 @@ analyze_miv_subscript (tree chrec_a,
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
 
-      *overlaps_a = chrec_dont_know;
-      *overlaps_b = chrec_dont_know;
+      *overlaps_a = conflict_fn_not_known ();
+      *overlaps_b = conflict_fn_not_known ();
       *last_conflicts = chrec_dont_know;
       dependence_stats.num_miv_unimplemented++;
     }
@@ -3308,8 +3537,8 @@ analyze_miv_subscript (tree chrec_a,
 static void 
 analyze_overlapping_iterations (tree chrec_a, 
 				tree chrec_b, 
-				tree *overlap_iterations_a, 
-				tree *overlap_iterations_b, 
+				conflict_function **overlap_iterations_a, 
+				conflict_function **overlap_iterations_b, 
 				tree *last_conflicts)
 {
   dependence_stats.num_subscript_tests++;
@@ -3331,8 +3560,8 @@ analyze_overlapping_iterations (tree chrec_a,
     {
       dependence_stats.num_subscript_undetermined++;
       
-      *overlap_iterations_a = chrec_dont_know;
-      *overlap_iterations_b = chrec_dont_know;
+      *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 
@@ -3341,8 +3570,8 @@ analyze_overlapping_iterations (tree chrec_a,
 	   && evolution_function_is_affine_multivariate_p (chrec_a))
     {
       dependence_stats.num_same_subscript_function++;
-      *overlap_iterations_a = integer_zero_node;
-      *overlap_iterations_b = integer_zero_node;
+      *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;
     }
 
@@ -3354,8 +3583,8 @@ analyze_overlapping_iterations (tree chrec_a,
 	       || !evolution_function_is_affine_multivariate_p (chrec_b)))
     {
       dependence_stats.num_subscript_undetermined++;
-      *overlap_iterations_a = chrec_dont_know;
-      *overlap_iterations_b = chrec_dont_know;
+      *overlap_iterations_a = conflict_fn_not_known ();
+      *overlap_iterations_b = conflict_fn_not_known ();
     }
 
   else if (ziv_subscript_p (chrec_a, chrec_b))
@@ -3376,9 +3605,9 @@ analyze_overlapping_iterations (tree chrec_a,
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "  (overlap_iterations_a = ");
-      print_generic_expr (dump_file, *overlap_iterations_a, 0);
+      dump_conflict_function (dump_file, *overlap_iterations_a);
       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
-      print_generic_expr (dump_file, *overlap_iterations_b, 0);
+      dump_conflict_function (dump_file, *overlap_iterations_b);
       fprintf (dump_file, ")\n");
       fprintf (dump_file, ")\n");
     }
@@ -3808,26 +4037,30 @@ subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
        i++)
     {
-      tree overlaps_a, overlaps_b;
+      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);
 
-      if (chrec_contains_undetermined (overlaps_a)
- 	  || chrec_contains_undetermined (overlaps_b))
+      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 (overlaps_a == chrec_known
- 	       || overlaps_b == chrec_known)
+      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;
  	}
 
@@ -3950,8 +4183,10 @@ compute_self_dependence (struct data_dependence_relation *ddr)
        i++)
     {
       /* The accessed index overlaps for each iteration.  */
-      SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
-      SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
+      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;
     }
 
@@ -4367,7 +4602,7 @@ free_dependence_relation (struct data_dependence_relation *ddr)
     return;
 
   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
-    VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
+    free_subscripts (DDR_SUBSCRIPTS (ddr));
 
   free (ddr);
 }