This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[lno] we now intechange loops on a well known benchmark...


Hi,

This patch should do the work for interchanging loops on swim, and
probably other non optimal code.  I have tested that the transform
matrix is built and validated on a reduced testcase
(aka. ssa-chrec-62.c) 

Some low level comments: the dependence on this testcase is tricky
{{0, +, 1}_1, +, 1335}_2   vs.   {0, +, 1336}_1

and for getting it right one has to bound the dependence domain.  This
is done by estimating the number of iterations in loops 1 and 2 by
looking at the size of the data and at the access functions.  I will
be grateful if somebody could comment on the way this information is
extracted in estimate_niter_from_size_of_data.  This is probably not
the best solution, but it works on that testcase...

Sebastian


Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.259
diff -c -3 -p -r1.1.2.259 ChangeLog.lno
*** ChangeLog.lno	31 Aug 2004 14:26:40 -0000	1.1.2.259
--- ChangeLog.lno	1 Sep 2004 23:30:55 -0000
***************
*** 1,3 ****
--- 1,63 ----
+ 2004-09-01  Sebastian Pop  <pop@cri.ensmp.fr>
+ 
+ 	* cfgloop.h (struct loop): New fields parallel_p, and 
+ 	estimated_nb_iterations.
+ 	* tree-chrec.c (nb_vars_in_chrec): New.
+ 	* tree-chrec.h (nb_vars_in_chrec): Declared here.
+ 	* tree-data-ref.c (tree_fold_divides_p): Don't test for a equals one, 
+ 	this test is already in tree_fold_gcd.
+ 	(gcd): For integers, yet again a copy defined static.
+ 	(int_divides_p): Same for integers.
+ 	(dump_data_dependence_relation): Fix dumping.  Dump dir and dist 
+ 	vectors.
+ 	(dump_dist_dir_vectors): Don't pass in the size of the
+ 	vectors; it is now read from DDR_SIZE_VECT.
+ 	(dump_ddrs, estimate_niter_from_size_of_data, all_chrecs_equal_p): New.
+ 	(compute_distance_vector): Renamed compute_subscript_distance.
+ 	Fix comment.
+ 	(compute_distance_vector): Handle the case where the description of 
+ 	a multivariate function is a TREE_VEC.
+ 	(analyze_ziv_subscript, analyze_siv_subscript_cst_affine, 
+ 	analyze_siv_subscript, analyze_miv_subscript, 
+ 	analyze_overlapping_iterations, ): 
+ 	Pass in a pointer to last_conflicts, and initialize it.
+ 	(initialize_matrix_A, FLOOR, compute_overlap_steps_for_affine_univar, 
+ 	compute_overlap_steps_for_affine_1_2): New.
+ 	(analyze_siv_subscript_affine_cst): Removed, replaced its uses with
+ 	analyze_siv_subscript_cst_affine.
+ 	(analyze_subscript_affine_affine): Pass in a pointer to
+ 	last_conflicts, and initialize it.  Add a special case for avoiding 
+ 	the computation of the Hermite normal form when there exist a trivial 
+ 	solution: when gamma is zero.  Rewrite the dependence tester for using 
+ 	fewer tree nodes, it now uses integers for the computations.
+ 	(no_conflicts_p): Fix typo: return true when overlaps is chrec_known.
+ 	(subscript_dependence_tester): Compute the last conflict.  Initialize 
+ 	SUB_LAST_CONFLICT.
+ 	(build_classic_dist_vector, build_classic_dir_vector): Conflict 
+ 	functions don't store the loop number that carry the dependence.  
+ 	Retrieve this information from the array access function. 
+ 	Initialize DDR_SIZE_VECT.
+ 	(find_data_references_in_loop): Detect parallel loops when all the 
+ 	data accesses are in read only mode.  Insert a single chrec_dont_know
+ 	node in the data dependence graph.
+ 	* tree-data-ref.h (struct data_dependence_relation): Add a field
+ 	size_vect.
+ 	(DDR_SIZE_VECT): New.
+ 	(dump_ddrs): Declared here.
+ 	(dump_dist_dir_vectors): Modify the declaration.
+ 	(gather_interchange_stats): Fix leading comment.  Gather also the 
+ 	access strides, and consequently pass in the datarefs array from which
+ 	this information is extracted.  Correctly parenthesize the access to
+ 	nb_deps_not_carried_by_loop such that its value is incremented.
+ 	Modify the constants, such that in the unknown and known cases the 
+ 	dependence steps are not increased.
+ 	(try_interchange_loops): Pass in the datarefs array.  Add more 
+ 	comments.  Add a test for temporal locality: inner loops
+ 	should have smallest array access strides.
+ 	* tree-pretty-print.c (dump_generic_node): BINFO_TYPE has nothing to do 
+ 	with the TREE_VEC node.  Correctly dump the TREE_VEC node printing 
+ 	all its elements.
+ 
  2004-08-31  Keith Besaw  <kbesaw@us.ibm.com>
  
  	* tree-vectorizer.h (struct _loop_vec_info): Add fields ptr_mask,
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.2.4.9.2.23
diff -c -3 -p -r1.2.4.9.2.23 cfgloop.h
*** cfgloop.h	4 Aug 2004 19:13:49 -0000	1.2.4.9.2.23
--- cfgloop.h	1 Sep 2004 23:30:55 -0000
*************** struct loop
*** 183,194 ****
--- 183,204 ----
       information in this field.  */
    tree nb_iterations;
  
+   /* An INTEGER_CST estimation of the number of iterations.  NULL_TREE
+      if there is no estimation.  */
+   tree estimated_nb_iterations;
+ 
    /* Upper bound on number of iterations of a loop.  */
    struct nb_iter_bound *bounds;
  
    /* If not NULL, loop has just single exit edge stored here (edges to the
       EXIT_BLOCK_PTR do not count.  */
    edge single_exit;
+ 
+   /* True when the loop does not carry data dependences, and
+      consequently the iterations can be executed in any order.  False
+      when the loop carries data dependences, or when the property is
+      not decidable.  */
+   bool parallel_p;
  };
  
  /* Flags for state of loop structure.  */
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 1.1.2.32
diff -c -3 -p -r1.1.2.32 tree-chrec.c
*** tree-chrec.c	15 Aug 2004 21:37:35 -0000	1.1.2.32
--- tree-chrec.c	1 Sep 2004 23:30:55 -0000
*************** chrec_component_in_loop_num (tree chrec,
*** 641,647 ****
  }
  
  /* Returns the evolution part in LOOP_NUM.  Example: the call
!    evolution_part_in_loop_num (1, {{0, +, 1}_1, +, 2}_1) returns 
     {1, +, 2}_1  */
  
  tree 
--- 641,647 ----
  }
  
  /* Returns the evolution part in LOOP_NUM.  Example: the call
!    evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns 
     {1, +, 2}_1  */
  
  tree 
*************** evolution_part_in_loop_num (tree chrec, 
*** 652,658 ****
  }
  
  /* Returns the initial condition in LOOP_NUM.  Example: the call
!    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 1) returns 
     {0, +, 1}_1  */
  
  tree 
--- 652,658 ----
  }
  
  /* Returns the initial condition in LOOP_NUM.  Example: the call
!    initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns 
     {0, +, 1}_1  */
  
  tree 
*************** evolution_function_is_univariate_p (tree
*** 937,942 ****
--- 937,962 ----
      }
  }
  
+ /* Returns the number of variables of CHREC.  Example: the call
+    nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2.  */
+ 
+ unsigned 
+ nb_vars_in_chrec (tree chrec)
+ {
+   if (chrec == NULL_TREE)
+     return 0;
+ 
+   switch (TREE_CODE (chrec))
+     {
+     case POLYNOMIAL_CHREC:
+       return 1 + nb_vars_in_chrec 
+ 	(initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
+ 
+     default:
+       return 0;
+     }
+ }
+ 
  
  
  /* Convert the initial condition of chrec to type.  */
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.h,v
retrieving revision 1.1.2.27
diff -c -3 -p -r1.1.2.27 tree-chrec.h
*** tree-chrec.h	15 Aug 2004 21:37:35 -0000	1.1.2.27
--- tree-chrec.h	1 Sep 2004 23:30:55 -0000
*************** extern bool chrec_contains_undetermined 
*** 91,96 ****
--- 91,97 ----
  extern bool tree_contains_chrecs (tree);
  extern bool evolution_function_is_affine_multivariate_p (tree);
  extern bool evolution_function_is_univariate_p (tree);
+ extern unsigned nb_vars_in_chrec (tree);
  
  
  
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 1.1.2.35
diff -c -3 -p -r1.1.2.35 tree-data-ref.c
*** tree-data-ref.c	19 Aug 2004 21:19:32 -0000	1.1.2.35
--- tree-data-ref.c	1 Sep 2004 23:30:55 -0000
*************** tree_fold_divides_p (tree type, 
*** 206,219 ****
  		     tree a, 
  		     tree b)
  {
-   if (integer_onep (a))
-     return true;
-   
    /* Determines whether (A == gcd (A, B)).  */
    return integer_zerop 
      (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
  }
  
  
  
  /* Dump into FILE all the data references from DATAREFS.  */ 
--- 206,246 ----
  		     tree a, 
  		     tree b)
  {
    /* Determines whether (A == gcd (A, B)).  */
    return integer_zerop 
      (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
  }
  
+ /* Compute the greatest common denominator of two numbers using
+    Euclid's algorithm.  */
+ 
+ static int 
+ gcd (int a, int b)
+ {
+   
+   int x, y, z;
+   
+   x = abs (a);
+   y = abs (b);
+ 
+   while (x>0)
+     {
+       z = y % x;
+       y = x;
+       x = z;
+     }
+ 
+   return (y);
+ }
+ 
+ /* Returns true iff A divides B.  */
+ 
+ static inline bool 
+ int_divides_p (int a, int b)
+ {
+   return (a == gcd (a, b));
+ }
+ 
  
  
  /* Dump into FILE all the data references from DATAREFS.  */ 
*************** dump_subscript (FILE *outf, struct subsc
*** 277,284 ****
      fprintf (outf, "    (don't know)\n");
    else
      {
!       tree last_iteration = SUB_LAST_CONFLICT_IN_A (subscript);
!       fprintf (outf, "  last_iteration_that_access_an_element_twice_in_A: ");
        print_generic_stmt (outf, last_iteration, 0);
      }
  	  
--- 304,311 ----
      fprintf (outf, "    (don't know)\n");
    else
      {
!       tree last_iteration = SUB_LAST_CONFLICT (subscript);
!       fprintf (outf, "  last_conflict: ");
        print_generic_stmt (outf, last_iteration, 0);
      }
  	  
*************** dump_subscript (FILE *outf, struct subsc
*** 291,298 ****
      fprintf (outf, "    (don't know)\n");
    else
      {
!       tree last_iteration = SUB_LAST_CONFLICT_IN_B (subscript);
!       fprintf (outf, "  last_iteration_that_access_an_element_twice_in_B: ");
        print_generic_stmt (outf, last_iteration, 0);
      }
  
--- 318,325 ----
      fprintf (outf, "    (don't know)\n");
    else
      {
!       tree last_iteration = SUB_LAST_CONFLICT (subscript);
!       fprintf (outf, "  last_conflict: ");
        print_generic_stmt (outf, last_iteration, 0);
      }
  
*************** dump_data_dependence_relation (FILE *out
*** 313,325 ****
    dra = DDR_A (ddr);
    drb = DDR_B (ddr);
    fprintf (outf, "(Data Dep: \n");
!   if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
      fprintf (outf, "    (don't know)\n");
    
    else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
      fprintf (outf, "    (no dependence)\n");
    
!   else
      {
        unsigned int i;
        for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
--- 340,352 ----
    dra = DDR_A (ddr);
    drb = DDR_B (ddr);
    fprintf (outf, "(Data Dep: \n");
!   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
      fprintf (outf, "    (don't know)\n");
    
    else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
      fprintf (outf, "    (no dependence)\n");
    
!   else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
      {
        unsigned int i;
        for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
*************** dump_data_dependence_relation (FILE *out
*** 330,335 ****
--- 357,366 ----
  	  print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
  	  dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
  	}
+       fprintf (outf, "  distance_vect: ");
+       print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
+       fprintf (outf, "  direction_vect: ");
+       print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
      }
  
    fprintf (outf, ")\n");
*************** dump_data_dependence_direction (FILE *fi
*** 384,390 ****
     considered nest.  */
  
  void 
! dump_dist_dir_vectors (FILE *file, varray_type ddrs, unsigned int vect_size)
  {
    unsigned int i;
  
--- 415,421 ----
     considered nest.  */
  
  void 
! dump_dist_dir_vectors (FILE *file, varray_type ddrs)
  {
    unsigned int i;
  
*************** dump_dist_dir_vectors (FILE *file, varra
*** 397,414 ****
  	  && DDR_AFFINE_P (ddr))
  	{
  	  fprintf (file, "DISTANCE_V (");
! 	  print_lambda_vector (file, DDR_DIST_VECT (ddr), vect_size);
  	  fprintf (file, ")\n");
  	  fprintf (file, "DIRECTION_V (");
! 	  print_lambda_vector (file, DDR_DIR_VECT (ddr), vect_size);
  	  fprintf (file, ")\n");
  	}
      }
    fprintf (file, "\n\n");
  }
  
  
  
  /* Given an ARRAY_REF node REF, records its access functions.
     Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
     ie. the constant "3", then recursively call the function on opnd0,
--- 428,504 ----
  	  && DDR_AFFINE_P (ddr))
  	{
  	  fprintf (file, "DISTANCE_V (");
! 	  print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
  	  fprintf (file, ")\n");
  	  fprintf (file, "DIRECTION_V (");
! 	  print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
  	  fprintf (file, ")\n");
  	}
      }
    fprintf (file, "\n\n");
  }
  
+ /* Dumps the data dependence relations DDRS in FILE.  */
+ 
+ void 
+ dump_ddrs (FILE *file, varray_type ddrs)
+ {
+   unsigned int i;
+ 
+   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
+     {
+       struct data_dependence_relation *ddr = 
+ 	(struct data_dependence_relation *) 
+ 	VARRAY_GENERIC_PTR (ddrs, i);
+       dump_data_dependence_relation (file, ddr);
+     }
+   fprintf (file, "\n\n");
+ }
+ 
  
  
+ /* Estimate the number of iterations from the size of the data and the
+    access functions.  */
+ 
+ static void
+ estimate_niter_from_size_of_data (struct loop *loop, 
+ 				  tree opnd0, 
+ 				  tree access_fn)
+ {
+   tree estimation;
+   tree array_size, data_size, element_size;
+   tree init, step;
+ 
+   init = initial_condition (access_fn);
+   step = evolution_part_in_loop_num (access_fn, loop->num);
+ 
+   array_size = TYPE_SIZE (TREE_TYPE (opnd0));
+   element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
+   data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node, 
+ 			   array_size, element_size));
+ 
+   if (TREE_CODE (init) == INTEGER_CST
+       && TREE_CODE (init) == INTEGER_CST)
+     {
+       estimation = fold (build2 (MINUS_EXPR, integer_type_node, 
+ 				 data_size, init));
+       estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node, 
+ 				 estimation, step));
+ 
+       if (loop->estimated_nb_iterations)
+ 	{
+ 	  /* Update only if we have found a smaller number of
+ 	     iterations.  */
+ 	  if (tree_int_cst_sgn 
+ 	      (fold (build2 (MINUS_EXPR, integer_type_node, 
+ 			     loop->estimated_nb_iterations, estimation))) > 0)
+ 	    loop->estimated_nb_iterations = estimation;
+ 	}
+       else
+ 	loop->estimated_nb_iterations = estimation;
+     }
+ }
+ 
  /* Given an ARRAY_REF node REF, records its access functions.
     Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
     ie. the constant "3", then recursively call the function on opnd0,
*************** analyze_array_indexes (struct loop *loop
*** 432,437 ****
--- 522,530 ----
       the optimizers.  */
    access_fn = instantiate_parameters 
      (loop, analyze_scalar_evolution (loop, opnd1));
+ 
+   if (chrec_contains_symbols (number_of_iterations_in_loop (loop)))
+     estimate_niter_from_size_of_data (loop, opnd0, access_fn);
    
    VARRAY_PUSH_TREE (*access_fns, access_fn);
    
*************** init_data_ref (tree stmt, 
*** 514,524 ****
  
  
  
! /* When there exists a dependence relation, determine its distance
!    vector.  */
  
  static void
! compute_distance_vector (struct data_dependence_relation *ddr)
  {
    if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
      {
--- 607,637 ----
  
  
  
! /* Returns true when all the functions of a tree_vec CHREC are the
!    same.  */
! 
! static bool 
! all_chrecs_equal_p (tree chrec)
! {
!   int j;
! 
!   for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
!     {
!       tree chrec_j = TREE_VEC_ELT (chrec, j);
!       tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
!       if (!integer_zerop 
! 	  (chrec_fold_minus 
! 	   (integer_type_node, chrec_j, chrec_j_1)))
! 	return false;
!     }
!   return true;
! }
! 
! /* Determine for each subscript in the data dependence relation DDR
!    the distance.  */
  
  static void
! compute_subscript_distance (struct data_dependence_relation *ddr)
  {
    if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
      {
*************** compute_distance_vector (struct data_dep
*** 532,538 ****
   	  subscript = DDR_SUBSCRIPT (ddr, i);
   	  conflicts_a = SUB_CONFLICTS_IN_A (subscript);
   	  conflicts_b = SUB_CONFLICTS_IN_B (subscript);
!  	  difference = chrec_fold_minus 
  	    (integer_type_node, conflicts_b, conflicts_a);
   	  
   	  if (evolution_function_is_constant_p (difference))
--- 645,674 ----
   	  subscript = DDR_SUBSCRIPT (ddr, i);
   	  conflicts_a = SUB_CONFLICTS_IN_A (subscript);
   	  conflicts_b = SUB_CONFLICTS_IN_B (subscript);
! 
! 	  if (TREE_CODE (conflicts_a) == TREE_VEC)
! 	    {
! 	      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);
! 	    }
! 
! 	  difference = chrec_fold_minus 
  	    (integer_type_node, conflicts_b, conflicts_a);
   	  
   	  if (evolution_function_is_constant_p (difference))
*************** initialize_data_dependence_relation (str
*** 582,589 ****
  	  subscript = xmalloc (sizeof (struct subscript));
  	  SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
  	  SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
! 	  SUB_LAST_CONFLICT_IN_A (subscript) = chrec_dont_know;
! 	  SUB_LAST_CONFLICT_IN_B (subscript) = chrec_dont_know;
  	  SUB_DISTANCE (subscript) = chrec_dont_know;
  	  VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
  	}
--- 718,724 ----
  	  subscript = xmalloc (sizeof (struct subscript));
  	  SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
  	  SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
! 	  SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
  	  SUB_DISTANCE (subscript) = chrec_dont_know;
  	  VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
  	}
*************** static void 
*** 685,691 ****
  analyze_ziv_subscript (tree chrec_a, 
  		       tree chrec_b, 
  		       tree *overlaps_a,
! 		       tree *overlaps_b)
  {
    tree difference;
    
--- 820,827 ----
  analyze_ziv_subscript (tree chrec_a, 
  		       tree chrec_b, 
  		       tree *overlaps_a,
! 		       tree *overlaps_b, 
! 		       tree *last_conflicts)
  {
    tree difference;
    
*************** analyze_ziv_subscript (tree chrec_a, 
*** 703,714 ****
  	     overlaps for each iteration in the loop.  */
  	  *overlaps_a = integer_zero_node;
  	  *overlaps_b = integer_zero_node;
  	}
        else
  	{
  	  /* The accesses do not overlap.  */
  	  *overlaps_a = chrec_known;
! 	  *overlaps_b = chrec_known;	  
  	}
        break;
        
--- 839,852 ----
  	     overlaps for each iteration in the loop.  */
  	  *overlaps_a = integer_zero_node;
  	  *overlaps_b = integer_zero_node;
+ 	  *last_conflicts = chrec_dont_know;
  	}
        else
  	{
  	  /* The accesses do not overlap.  */
  	  *overlaps_a = chrec_known;
! 	  *overlaps_b = chrec_known;
! 	  *last_conflicts = integer_zero_node;
  	}
        break;
        
*************** analyze_ziv_subscript (tree chrec_a, 
*** 716,722 ****
        /* We're not sure whether the indexes overlap.  For the moment, 
  	 conservatively answer "don't know".  */
        *overlaps_a = chrec_dont_know;
!       *overlaps_b = chrec_dont_know;	  
        break;
      }
    
--- 854,861 ----
        /* We're not sure whether the indexes overlap.  For the moment, 
  	 conservatively answer "don't know".  */
        *overlaps_a = chrec_dont_know;
!       *overlaps_b = chrec_dont_know;
!       *last_conflicts = chrec_dont_know;
        break;
      }
    
*************** static void
*** 736,742 ****
  analyze_siv_subscript_cst_affine (tree chrec_a, 
  				  tree chrec_b,
  				  tree *overlaps_a, 
! 				  tree *overlaps_b)
  {
    bool value0, value1, value2;
    tree difference = chrec_fold_minus 
--- 875,882 ----
  analyze_siv_subscript_cst_affine (tree chrec_a, 
  				  tree chrec_b,
  				  tree *overlaps_a, 
! 				  tree *overlaps_b, 
! 				  tree *last_conflicts)
  {
    bool value0, value1, value2;
    tree difference = chrec_fold_minus 
*************** analyze_siv_subscript_cst_affine (tree c
*** 746,751 ****
--- 886,892 ----
      {
        *overlaps_a = chrec_dont_know;
        *overlaps_b = chrec_dont_know;
+       *last_conflicts = chrec_dont_know;
        return;
      }
    else
*************** analyze_siv_subscript_cst_affine (tree c
*** 756,761 ****
--- 897,903 ----
  	    {
  	      *overlaps_a = chrec_dont_know;
  	      *overlaps_b = chrec_dont_know;      
+ 	      *last_conflicts = chrec_dont_know;
  	      return;
  	    }
  	  else
*************** analyze_siv_subscript_cst_affine (tree c
*** 775,780 ****
--- 917,923 ----
  			(build (EXACT_DIV_EXPR, integer_type_node, 
  				fold (build1 (ABS_EXPR, integer_type_node, difference)), 
  				CHREC_RIGHT (chrec_b)));
+ 		      *last_conflicts = integer_one_node;
  		      return;
  		    }
  		  
*************** analyze_siv_subscript_cst_affine (tree c
*** 784,789 ****
--- 927,933 ----
  		    {
  		      *overlaps_a = chrec_known;
  		      *overlaps_b = chrec_known;      
+ 		      *last_conflicts = integer_zero_node;
  		      return;
  		    }
  		}
*************** analyze_siv_subscript_cst_affine (tree c
*** 797,802 ****
--- 941,947 ----
  		     In this case, chrec_a will not overlap with chrec_b.  */
  		  *overlaps_a = chrec_known;
  		  *overlaps_b = chrec_known;
+ 		  *last_conflicts = integer_zero_node;
  		  return;
  		}
  	    }
*************** analyze_siv_subscript_cst_affine (tree c
*** 807,812 ****
--- 952,958 ----
  	    {
  	      *overlaps_a = chrec_dont_know;
  	      *overlaps_b = chrec_dont_know;      
+ 	      *last_conflicts = chrec_dont_know;
  	      return;
  	    }
  	  else
*************** analyze_siv_subscript_cst_affine (tree c
*** 824,829 ****
--- 970,976 ----
  		      *overlaps_b = fold 
  			(build (EXACT_DIV_EXPR, integer_type_node, difference, 
  				CHREC_RIGHT (chrec_b)));
+ 		      *last_conflicts = integer_one_node;
  		      return;
  		    }
  		  
*************** analyze_siv_subscript_cst_affine (tree c
*** 833,838 ****
--- 980,986 ----
  		    {
  		      *overlaps_a = chrec_known;
  		      *overlaps_b = chrec_known;      
+ 		      *last_conflicts = integer_zero_node;
  		      return;
  		    }
  		}
*************** analyze_siv_subscript_cst_affine (tree c
*** 845,850 ****
--- 993,999 ----
  		     In this case, chrec_a will not overlap with chrec_b.  */
  		  *overlaps_a = chrec_known;
  		  *overlaps_b = chrec_known;
+ 		  *last_conflicts = integer_zero_node;
  		  return;
  		}
  	    }
*************** analyze_siv_subscript_cst_affine (tree c
*** 852,872 ****
      }
  }
  
! /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is an
!    affine function, and CHREC_B is a constant.  *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_affine_cst (tree chrec_a, 
! 				  tree chrec_b,
! 				  tree *overlaps_a, 
! 				  tree *overlaps_b)
! {
!   analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a);
  }
  
  /* Determines the overlapping elements due to accesses CHREC_A and
--- 1001,1196 ----
      }
  }
  
! /* Helper recursive function for intializing the matrix A.  Returns
!    the initial value of CHREC.  */
  
! static int
! initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
! {
! #if defined ENABLE_CHECKING
!   if (chrec == NULL_TREE)
!     abort ();
! #endif
! 
!   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
!     return int_cst_value (chrec);
! 
!   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
!   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
! }
! 
! #define FLOOR(x,y) (CEIL (x, y) - 1)
! 
! /* 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, 
! 					 tree *overlaps_a, tree *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;
! 
!       tau2 = FLOOR (niter, step_overlaps_a);
!       tau2 = MIN (tau2, FLOOR (niter, step_overlaps_b));
!       last_conflict = tau2;
! 
!       *overlaps_a = build_polynomial_chrec
! 	(dim, integer_zero_node,
! 	 build_int_2 (step_overlaps_a, 0));
!       *overlaps_b = build_polynomial_chrec
! 	(dim, integer_zero_node,
! 	 build_int_2 (step_overlaps_b, 0));
!       *last_conflicts = build_int_2 (last_conflict, 0);
!     }
! 
!   else
!     {
!       *overlaps_a = integer_zero_node;
!       *overlaps_b = 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 occuring in
!    a common benchmark.  Implement the general algorithm.  */
! 
! static void
! compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 
! 				      tree *overlaps_a, tree *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;
! 
!   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));
! 
!   numiter_x = number_of_iterations_in_loop 
!     (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
!   numiter_y = number_of_iterations_in_loop 
!     (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
!   numiter_z = number_of_iterations_in_loop 
!     (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
! 
!   if (TREE_CODE (numiter_x) != INTEGER_CST)
!     numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
!       ->estimated_nb_iterations;
!   if (TREE_CODE (numiter_y) != INTEGER_CST)
!     numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
!       ->estimated_nb_iterations;
!   if (TREE_CODE (numiter_z) != INTEGER_CST)
!     numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
!       ->estimated_nb_iterations;
! 
!   if (numiter_x == NULL_TREE || numiter_y == NULL_TREE 
!       || numiter_z == NULL_TREE)
!     {
!       *overlaps_a = chrec_dont_know;
!       *overlaps_b = chrec_dont_know;
!       *last_conflicts = chrec_dont_know;
!       return;
!     }
! 
!   niter_x = int_cst_value (numiter_x);
!   niter_y = int_cst_value (numiter_y);
!   niter_z = int_cst_value (numiter_z);
! 
!   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)
!     {
!       *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;
!       if (xz_p)
! 	{
! 	  TREE_VEC_ELT (*overlaps_a, 0) = 
! 	    chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
! 			     overlaps_a_xz);
! 	  *overlaps_b = 
! 	    chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
! 	  *last_conflicts = last_conflicts_xz;
! 	}
!       if (yz_p)
! 	{
! 	  TREE_VEC_ELT (*overlaps_a, 1) = 
! 	    chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
! 			     overlaps_a_yz);
! 	  *overlaps_b = 
! 	    chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
! 	  *last_conflicts = last_conflicts_yz;
! 	}
!       if (xyz_p)
! 	{
! 	  TREE_VEC_ELT (*overlaps_a, 0) = 
! 	    chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
! 			     overlaps_a_xyz);
! 	  TREE_VEC_ELT (*overlaps_a, 1) = 
! 	    chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
! 			     overlaps_a_xyz);
! 	  *overlaps_b = 
! 	    chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
! 	  *last_conflicts = last_conflicts_xyz;
! 	}
!     }
!   else
!     {
!       *overlaps_a = integer_zero_node;
!       *overlaps_b = integer_zero_node;
!       *last_conflicts = integer_zero_node;
!     }
  }
  
  /* Determines the overlapping elements due to accesses CHREC_A and
*************** static void
*** 877,886 ****
  analyze_subscript_affine_affine (tree chrec_a, 
  				 tree chrec_b,
  				 tree *overlaps_a, 
! 				 tree *overlaps_b)
  {
!   tree left_a, left_b, right_a, right_b;
!   
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "(analyze_subscript_affine_affine \n");
    
--- 1201,1214 ----
  analyze_subscript_affine_affine (tree chrec_a, 
  				 tree chrec_b,
  				 tree *overlaps_a, 
! 				 tree *overlaps_b, 
! 				 tree *last_conflicts)
  {
!   unsigned nb_vars_a, nb_vars_b, dim;
!   int init_a, init_b, gamma, gcd_alpha_beta;
!   int tau1, tau2;
!   lambda_matrix A, U, S;
! 
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "(analyze_subscript_affine_affine \n");
    
*************** analyze_subscript_affine_affine (tree ch
*** 895,1015 ****
       there is no dependence.  This function outputs a description of
       the iterations that hold the intersections.  */
  
!   left_a = CHREC_LEFT (chrec_a);
!   left_b = CHREC_LEFT (chrec_b);
!   right_a = CHREC_RIGHT (chrec_a);
!   right_b = CHREC_RIGHT (chrec_b);
!   
!   if (chrec_zerop (chrec_fold_minus (integer_type_node, left_a, left_b)))
!     {
!       /* The first element accessed twice is on the first
! 	 iteration.  */
!       *overlaps_a = build_polynomial_chrec 
! 	(CHREC_VARIABLE (chrec_b), integer_zero_node, integer_one_node);
!       *overlaps_b = build_polynomial_chrec 
! 	(CHREC_VARIABLE (chrec_a), integer_zero_node, integer_one_node);
!     }
!   
!   else if (TREE_CODE (left_a) == INTEGER_CST
! 	   && TREE_CODE (left_b) == INTEGER_CST
! 	   && TREE_CODE (right_a) == INTEGER_CST 
! 	   && TREE_CODE (right_b) == INTEGER_CST
! 	   
! 	   /* Both functions should have the same evolution sign.  */
! 	   && ((tree_int_cst_sgn (right_a) > 0 
! 		&& tree_int_cst_sgn (right_b) > 0)
! 	       || (tree_int_cst_sgn (right_a) < 0
! 		   && tree_int_cst_sgn (right_b) < 0)))
!     {
!       /* Here we have to solve the Diophantine equation.  Reference
! 	 book: "Loop Transformations for Restructuring Compilers - The
! 	 Foundations" by Utpal Banerjee, pages 59-80.
! 	 
! 	 ALPHA * X0 = BETA * Y0 + GAMMA.  
! 	 
! 	 with:
! 	 ALPHA = RIGHT_A
! 	 BETA = RIGHT_B
! 	 GAMMA = LEFT_B - LEFT_A
! 	 CHREC_A = {LEFT_A, +, RIGHT_A}
! 	 CHREC_B = {LEFT_B, +, RIGHT_B}
! 	 
! 	 The Diophantine equation has a solution if and only if gcd
! 	 (ALPHA, BETA) divides GAMMA.  This is commonly known under
! 	 the name of the "gcd-test".
!       */
!       tree gamma;
!       tree gcd_alpha_beta;
!       lambda_matrix A, U, S;
! 
!       A = lambda_matrix_new (2, 1);
!       U = lambda_matrix_new (2, 2);
!       S = lambda_matrix_new (2, 1);
!       
!       A[0][0] = int_cst_value (right_a);
!       A[1][0] = -1 * int_cst_value (right_b);
  
!       /* U.A = S */
!       lambda_matrix_right_hermite (A, 2, 1, S, U);
  
!       gcd_alpha_beta = build_int_2 (S[0][0] < 0 ? -1 * S[0][0] : S[0][0], 0);
!       gamma = fold (build (MINUS_EXPR, integer_type_node, left_b, left_a));
!       if (tree_int_cst_sgn (gamma) < 0)
! 	gamma = fold (build (MULT_EXPR, integer_type_node, 
! 			     integer_minus_one_node, gamma));
  
!       /* The classic "gcd-test".  */
!       if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma))
  	{
! 	  /* The "gcd-test" has determined that there is no integer
! 	     solution, ie. there is no dependence.  */
! 	  *overlaps_a = chrec_known;
! 	  *overlaps_b = chrec_known;
  	}
!       
!       else
  	{
  	  /* The solutions are given by:
  	     | 
! 	     | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [X]
! 	     |                           [u21 u22]    [Y]
! 	     
  	     For a given integer t.  Using the following variables,
! 	     
! 	     | gamma_gcd = gamma / gcd_alpha_beta
! 	     | i0 = u11 * gamma_gcd
! 	     | j0 = u12 * gamma_gcd
  	     | i1 = u21
  	     | j1 = u22
! 	     
  	     the solutions are:
! 	     
! 	     | x = i0 + i1 * t, 
! 	     | y = j0 + j1 * t.  */
! 	  
! 	  tree i0, j0, i1, j1, t;
! 	  tree gamma_gcd;
! 	  
  	  /* X0 and Y0 are the first iterations for which there is a
  	     dependence.  X0, Y0 are two solutions of the Diophantine
  	     equation: chrec_a (X0) = chrec_b (Y0).  */
! 	  tree x0, y0;
!       
! 	  /* Exact div because in this case gcd_alpha_beta divides
! 	     gamma.  */
! 	  gamma_gcd = fold (build (EXACT_DIV_EXPR, integer_type_node, gamma, 
! 				   gcd_alpha_beta));
! 	  i0 = fold (build (MULT_EXPR, integer_type_node, 
! 			    build_int_2 (U[0][0], 0), gamma_gcd));
! 	  j0 = fold (build (MULT_EXPR, integer_type_node, 
! 			    build_int_2 (U[0][1], 0), gamma_gcd));
! 	  i1 = build_int_2 (U[1][0], 0);
! 	  j1 = build_int_2 (U[1][1], 0);
! 	  
! 	  if ((tree_int_cst_sgn (i1) == 0
! 	       && tree_int_cst_sgn (i0) < 0)
! 	      || (tree_int_cst_sgn (j1) == 0
! 		  && tree_int_cst_sgn (j0) < 0))
  	    {
  	      /* There is no solution.  
  		 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 
--- 1223,1388 ----
       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 = initialize_matrix_A (A, chrec_a, 0, 1);
!   init_b = 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)
! 	{
! 	  int step_a, step_b;
! 	  int niter, niter_a, niter_b;
! 	  tree numiter_a, numiter_b;
! 
! 	  numiter_a = number_of_iterations_in_loop 
! 	    (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
! 	  numiter_b = number_of_iterations_in_loop 
! 	    (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
! 
! 	  if (TREE_CODE (numiter_a) != INTEGER_CST)
! 	    numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
! 	      ->estimated_nb_iterations;
! 	  if (TREE_CODE (numiter_b) != INTEGER_CST)
! 	    numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
! 	      ->estimated_nb_iterations;
! 	  if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
! 	    {
! 	      *overlaps_a = chrec_dont_know;
! 	      *overlaps_b = chrec_dont_know;
! 	      *last_conflicts = chrec_dont_know;
! 	      return;
! 	    }
  
! 	  niter_a = int_cst_value (numiter_a);
! 	  niter_b = int_cst_value (numiter_b);
! 	  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, 
! 						   overlaps_a, overlaps_b, 
! 						   last_conflicts, 1);
! 	}
  
!       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
  	{
! 	  *overlaps_a = chrec_dont_know;
! 	  *overlaps_b = chrec_dont_know;
! 	  *last_conflicts = chrec_dont_know;
  	}
!       return;
!     }
! 
!   /* 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];
! 
!   /* The classic "gcd-test".  */
!   if (!int_divides_p (gcd_alpha_beta, gamma))
!     {
!       /* The "gcd-test" has determined that there is no integer
! 	 solution, ie. there is no dependence.  */
!       *overlaps_a = chrec_known;
!       *overlaps_b = chrec_known;
!       *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.  */
!       
! 	  int i0, j0, i1, j1;
! 
  	  /* X0 and Y0 are the first iterations for which there is a
  	     dependence.  X0, Y0 are two solutions of the Diophantine
  	     equation: chrec_a (X0) = chrec_b (Y0).  */
! 	  int x0, y0;
! 	  int niter, niter_a, niter_b;
! 	  tree numiter_a, numiter_b;
! 
! 	  numiter_a = number_of_iterations_in_loop 
! 	    (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
! 	  numiter_b = number_of_iterations_in_loop 
! 	    (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
! 
! 	  if (TREE_CODE (numiter_a) != INTEGER_CST)
! 	    numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
! 	      ->estimated_nb_iterations;
! 	  if (TREE_CODE (numiter_b) != INTEGER_CST)
! 	    numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
! 	      ->estimated_nb_iterations;
! 	  if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
! 	    {
! 	      *overlaps_a = chrec_dont_know;
! 	      *overlaps_b = chrec_dont_know;
! 	      *last_conflicts = chrec_dont_know;
! 	      return;
! 	    }
! 
! 	  niter_a = int_cst_value (numiter_a);
! 	  niter_b = int_cst_value (numiter_b);
! 	  niter = MIN (niter_a, niter_b);
! 
! 	  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" 
*************** analyze_subscript_affine_affine (tree ch
*** 1017,1059 ****
  		 upper bound of the iteration domain.  */
  	      *overlaps_a = chrec_known;
  	      *overlaps_b = chrec_known;
!   	    }
! 	  
  	  else 
  	    {
! 	      if (tree_int_cst_sgn (i1) > 0)
  		{
! 		  t = fold 
! 		    (build (CEIL_DIV_EXPR, integer_type_node, 
! 			    fold (build (MULT_EXPR, integer_type_node, i0, 
! 					 integer_minus_one_node)), 
! 			    i1));
! 		  
! 		  if (tree_int_cst_sgn (j1) > 0)
  		    {
! 		      t = fold 
! 			(build (MAX_EXPR, integer_type_node, t,
! 				fold (build (CEIL_DIV_EXPR, integer_type_node,
! 					     fold (build 
! 						   (MULT_EXPR,
! 						    integer_type_node, j0,
! 						    integer_minus_one_node)),
! 					     j1))));
! 
! 		      /* At this point, t = max (-i0/i1, -j0/j1) */
! 		      x0 = fold 
! 			(build (PLUS_EXPR, integer_type_node, i0, 
! 				fold (build 
! 				      (MULT_EXPR, integer_type_node, i1, t))));
! 		      y0 = fold 
! 			(build (PLUS_EXPR, integer_type_node, j0, 
! 				fold (build 
! 				      (MULT_EXPR, integer_type_node, j1, t))));
! 		      
! 		      *overlaps_a = build_polynomial_chrec 
! 			(CHREC_VARIABLE (chrec_b), x0, i1);
! 		      *overlaps_b = build_polynomial_chrec 
! 			(CHREC_VARIABLE (chrec_a), y0, j1);
  		    }
  		  else
  		    {
--- 1390,1425 ----
  		 upper bound of the iteration domain.  */
  	      *overlaps_a = chrec_known;
  	      *overlaps_b = chrec_known;
! 	      *last_conflicts = integer_zero_node;
! 	    }
! 
  	  else 
  	    {
! 	      if (i1 > 0)
  		{
! 		  tau1 = CEIL (-i0, i1);
! 		  tau2 = FLOOR (niter - i0, i1);
! 
! 		  if (j1 > 0)
  		    {
! 		      int last_conflict;
! 		      tau1 = MAX (tau1, CEIL (-j0, j1));
! 		      tau2 = MIN (tau2, FLOOR (niter - j0, j1));
! 
! 		      x0 = (i1 * tau1 + i0) % i1;
! 		      y0 = (j1 * tau1 + j0) % j1;
! 		      tau1 = (x0 - i0)/i1;
! 		      last_conflict = tau2 - tau1;
! 
! 		      *overlaps_a = build_polynomial_chrec
! 			(1,
! 			 build_int_2 (x0, 0),
! 			 build_int_2 (i1, 0));
! 		      *overlaps_b = build_polynomial_chrec
! 			(1,
! 			 build_int_2 (y0, 0),
! 			 build_int_2 (j1, 0));
! 		      *last_conflicts = build_int_2 (last_conflict, 0);
  		    }
  		  else
  		    {
*************** analyze_subscript_affine_affine (tree ch
*** 1061,1087 ****
  			 iteration domain for j is not checked. */
  		      *overlaps_a = chrec_dont_know;
  		      *overlaps_b = chrec_dont_know;
  		    }
  		}
! 	      
  	      else
  		{
  		  /* FIXME: For the moment, the upper bound of the
  		     iteration domain for i is not checked. */
  		  *overlaps_a = chrec_dont_know;
  		  *overlaps_b = chrec_dont_know;
  		}
  	    }
  	}
      }
!   
    else
      {
-       /* For the moment, "don't know".  */
        *overlaps_a = chrec_dont_know;
        *overlaps_b = chrec_dont_know;
      }
!   
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "  (overlaps_a = ");
--- 1427,1462 ----
  			 iteration domain for j is not checked. */
  		      *overlaps_a = chrec_dont_know;
  		      *overlaps_b = chrec_dont_know;
+ 		      *last_conflicts = chrec_dont_know;
  		    }
  		}
! 	  
  	      else
  		{
  		  /* FIXME: For the moment, the upper bound of the
  		     iteration domain for i is not checked. */
  		  *overlaps_a = chrec_dont_know;
  		  *overlaps_b = chrec_dont_know;
+ 		  *last_conflicts = chrec_dont_know;
  		}
  	    }
  	}
+       else
+ 	{
+ 	  *overlaps_a = chrec_dont_know;
+ 	  *overlaps_b = chrec_dont_know;
+ 	  *last_conflicts = chrec_dont_know;
+ 	}
      }
! 
    else
      {
        *overlaps_a = chrec_dont_know;
        *overlaps_b = chrec_dont_know;
+       *last_conflicts = chrec_dont_know;
      }
! 
! 
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "  (overlaps_a = ");
*************** static void
*** 1106,1112 ****
  analyze_siv_subscript (tree chrec_a, 
  		       tree chrec_b,
  		       tree *overlaps_a, 
! 		       tree *overlaps_b)
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "(analyze_siv_subscript \n");
--- 1481,1488 ----
  analyze_siv_subscript (tree chrec_a, 
  		       tree chrec_b,
  		       tree *overlaps_a, 
! 		       tree *overlaps_b, 
! 		       tree *last_conflicts)
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "(analyze_siv_subscript \n");
*************** analyze_siv_subscript (tree chrec_a, 
*** 1114,1134 ****
    if (evolution_function_is_constant_p (chrec_a)
        && evolution_function_is_affine_p (chrec_b))
      analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 
! 				      overlaps_a, overlaps_b);
    
    else if (evolution_function_is_affine_p (chrec_a)
  	   && evolution_function_is_constant_p (chrec_b))
!     analyze_siv_subscript_affine_cst (chrec_a, chrec_b, 
! 				      overlaps_a, overlaps_b);
    
    else if (evolution_function_is_affine_p (chrec_a)
  	   && evolution_function_is_affine_p (chrec_b))
      analyze_subscript_affine_affine (chrec_a, chrec_b, 
! 				     overlaps_a, overlaps_b);
    else
      {
        *overlaps_a = chrec_dont_know;
        *overlaps_b = chrec_dont_know;
      }
    
    if (dump_file && (dump_flags & TDF_DETAILS))
--- 1490,1511 ----
    if (evolution_function_is_constant_p (chrec_a)
        && evolution_function_is_affine_p (chrec_b))
      analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 
! 				      overlaps_a, overlaps_b, last_conflicts);
    
    else if (evolution_function_is_affine_p (chrec_a)
  	   && 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_p (chrec_a)
  	   && evolution_function_is_affine_p (chrec_b))
      analyze_subscript_affine_affine (chrec_a, chrec_b, 
! 				     overlaps_a, overlaps_b, last_conflicts);
    else
      {
        *overlaps_a = chrec_dont_know;
        *overlaps_b = chrec_dont_know;
+       *last_conflicts = chrec_dont_know;
      }
    
    if (dump_file && (dump_flags & TDF_DETAILS))
*************** static void
*** 1165,1171 ****
  analyze_miv_subscript (tree chrec_a, 
  		       tree chrec_b, 
  		       tree *overlaps_a, 
! 		       tree *overlaps_b)
  {
    /* FIXME:  This is a MIV subscript, not yet handled.
       Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from 
--- 1542,1549 ----
  analyze_miv_subscript (tree chrec_a, 
  		       tree chrec_b, 
  		       tree *overlaps_a, 
! 		       tree *overlaps_b, 
! 		       tree *last_conflicts)
  {
    /* FIXME:  This is a MIV subscript, not yet handled.
       Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from 
*************** analyze_miv_subscript (tree chrec_a, 
*** 1188,1193 ****
--- 1566,1573 ----
  	 in the same order.  */
        *overlaps_a = integer_zero_node;
        *overlaps_b = integer_zero_node;
+       *last_conflicts = number_of_iterations_in_loop 
+ 	(current_loops->parray[CHREC_VARIABLE (chrec_a)]);
      }
    
    else if (evolution_function_is_constant_p (difference)
*************** analyze_miv_subscript (tree chrec_a, 
*** 1202,1207 ****
--- 1582,1588 ----
  	 consequently there are no overlapping elements.  */
        *overlaps_a = chrec_known;
        *overlaps_b = chrec_known;
+       *last_conflicts = integer_zero_node;
      }
    
    else if (evolution_function_is_affine_multivariate_p (chrec_a)
*************** analyze_miv_subscript (tree chrec_a, 
*** 1222,1228 ****
  	 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
        */
        analyze_subscript_affine_affine (chrec_a, chrec_b, 
! 				       overlaps_a, overlaps_b);
      }
    
    else
--- 1603,1609 ----
  	 {{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);
      }
    
    else
*************** analyze_miv_subscript (tree chrec_a, 
*** 1230,1235 ****
--- 1611,1617 ----
        /* When the analysis is too difficult, answer "don't know".  */
        *overlaps_a = chrec_dont_know;
        *overlaps_b = chrec_dont_know;
+       *last_conflicts = chrec_dont_know;
      }
    
    if (dump_file && (dump_flags & TDF_DETAILS))
*************** static void 
*** 1250,1256 ****
  analyze_overlapping_iterations (tree chrec_a, 
  				tree chrec_b, 
  				tree *overlap_iterations_a, 
! 				tree *overlap_iterations_b)
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
--- 1632,1639 ----
  analyze_overlapping_iterations (tree chrec_a, 
  				tree chrec_b, 
  				tree *overlap_iterations_a, 
! 				tree *overlap_iterations_b, 
! 				tree *last_conflicts)
  {
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
*************** analyze_overlapping_iterations (tree chr
*** 1275,1289 ****
    
    else if (ziv_subscript_p (chrec_a, chrec_b))
      analyze_ziv_subscript (chrec_a, chrec_b, 
! 			   overlap_iterations_a, overlap_iterations_b);
    
    else if (siv_subscript_p (chrec_a, chrec_b))
      analyze_siv_subscript (chrec_a, chrec_b, 
! 			   overlap_iterations_a, overlap_iterations_b);
    
    else
      analyze_miv_subscript (chrec_a, chrec_b, 
! 			   overlap_iterations_a, overlap_iterations_b);
    
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
--- 1658,1675 ----
    
    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);
    
    else
      analyze_miv_subscript (chrec_a, chrec_b, 
! 			   overlap_iterations_a, overlap_iterations_b,
! 			   last_conflicts);
    
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
*************** undetermined_conflicts_p (tree overlaps)
*** 1317,1323 ****
  static bool
  no_conflicts_p (tree overlaps)
  {
!   if (chrec_contains_undetermined (overlaps))
      return true;
    else
      return false;
--- 1703,1709 ----
  static bool
  no_conflicts_p (tree overlaps)
  {
!   if (overlaps == chrec_known)
      return true;
    else
      return false;
*************** subscript_dependence_tester (struct data
*** 1331,1336 ****
--- 1717,1723 ----
    unsigned int i;
    struct data_reference *dra = DDR_A (ddr);
    struct data_reference *drb = DDR_B (ddr);
+   tree last_conflicts;
    
    if (dump_file && (dump_flags & TDF_DETAILS))
      fprintf (dump_file, "(subscript_dependence_tester \n");
*************** subscript_dependence_tester (struct data
*** 1342,1348 ****
        
        analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 
  				      DR_ACCESS_FN (drb, i),
! 				      &overlaps_a, &overlaps_b);
        
        if (undetermined_conflicts_p (overlaps_a)
   	  || undetermined_conflicts_p (overlaps_b))
--- 1729,1736 ----
        
        analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 
  				      DR_ACCESS_FN (drb, i),
! 				      &overlaps_a, &overlaps_b, 
! 				      &last_conflicts);
        
        if (undetermined_conflicts_p (overlaps_a)
   	  || undetermined_conflicts_p (overlaps_b))
*************** subscript_dependence_tester (struct data
*** 1362,1367 ****
--- 1750,1756 ----
   	{
   	  SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
   	  SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
+ 	  SUB_LAST_CONFLICT (subscript) = last_conflicts;
   	}
      }
    
*************** build_classic_dist_vector (struct data_d
*** 1392,1397 ****
--- 1781,1787 ----
    
    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)))
*************** build_classic_dist_vector (struct data_d
*** 1400,1416 ****
  	  return;
  	}
  
!       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
  	{
! 	  int dist;
! 	  int loop_nb;
! 	  loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
  	  loop_nb -= first_loop;
  	  /* If the loop number is still greater than the number of
  	     loops we've been asked to analyze, or negative,
  	     something is borked.  */
  	  if (loop_nb < 0 || loop_nb >= nb_loops)
  	    abort ();
  	  dist = int_cst_value (SUB_DISTANCE (subscript));
  
  	  /* This is the subscript coupling test.  
--- 1790,1848 ----
  	  return;
  	}
  
!       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
!       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
! 
!       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC 
! 	  && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
  	{
! 	  int dist, loop_nb;
! 	  int loop_nb_a = CHREC_VARIABLE (access_fn_a);
! 	  int loop_nb_b = CHREC_VARIABLE (access_fn_b);
! 	  struct loop *loop_a = current_loops->parray[loop_nb_a];
! 	  struct loop *loop_b = current_loops->parray[loop_nb_b];
! 
! 	  if (loop_nb_a != loop_nb_b
! 	      && !flow_loop_nested_p (loop_a, loop_b)
! 	      && !flow_loop_nested_p (loop_b, loop_a))
! 	    {
! 	      /* Example: when there are two consecutive loops,
! 
! 		 | loop_1
! 		 |   A[{0, +, 1}_1]
! 		 | endloop_1
! 		 | loop_2
! 		 |   A[{0, +, 1}_2]
! 		 | endloop_2
! 
! 		 the dependence relation cannot be captured by the
! 		 distance abstraction.  */
! 	      non_affine_dependence_relation (ddr);
! 	      return;
! 	    }
! 
! 	  /* 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.  */
! 	  loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
  	  loop_nb -= first_loop;
+ 
  	  /* If the loop number is still greater than the number of
  	     loops we've been asked to analyze, or negative,
  	     something is borked.  */
  	  if (loop_nb < 0 || loop_nb >= nb_loops)
  	    abort ();
+ 	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
+ 	    {
+ 	      non_affine_dependence_relation (ddr);
+ 	      return;
+ 	    }
+ 	  
  	  dist = int_cst_value (SUB_DISTANCE (subscript));
  
  	  /* This is the subscript coupling test.  
*************** build_classic_dist_vector (struct data_d
*** 1479,1484 ****
--- 1911,1917 ----
    }
    
    DDR_DIST_VECT (ddr) = dist_v;
+   DDR_SIZE_VECT (ddr) = nb_loops;
  }
  
  /* Compute the classic per loop direction vector.  
*************** build_classic_dir_vector (struct data_de
*** 1504,1509 ****
--- 1937,1943 ----
    
    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)))
*************** build_classic_dir_vector (struct data_de
*** 1512,1524 ****
  	  return;
  	}
  
!       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
! 	  && TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
  	{
! 	  int loop_nb;
! 	  
  	  enum data_dependence_direction dir = dir_star;
! 	  loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
  	  loop_nb -= first_loop;
  
  	  /* If the loop number is still greater than the number of
--- 1946,1991 ----
  	  return;
  	}
  
!       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
!       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
!       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
! 	  && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
  	{
! 	  int dist, loop_nb;
  	  enum data_dependence_direction dir = dir_star;
! 	  int loop_nb_a = CHREC_VARIABLE (access_fn_a);
! 	  int loop_nb_b = CHREC_VARIABLE (access_fn_b);
! 	  struct loop *loop_a = current_loops->parray[loop_nb_a];
! 	  struct loop *loop_b = current_loops->parray[loop_nb_b];
! 
! 	  if (loop_nb_a != loop_nb_b
! 	      && !flow_loop_nested_p (loop_a, loop_b)
! 	      && !flow_loop_nested_p (loop_b, loop_a))
! 	    {
! 	      /* Example: when there are two consecutive loops,
! 
! 		 | loop_1
! 		 |   A[{0, +, 1}_1]
! 		 | endloop_1
! 		 | loop_2
! 		 |   A[{0, +, 1}_2]
! 		 | endloop_2
! 
! 		 the dependence relation cannot be captured by the
! 		 distance abstraction.  */
! 	      non_affine_dependence_relation (ddr);
! 	      return;
! 	    }
! 
! 	  /* 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.  */
! 	  loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
  	  loop_nb -= first_loop;
  
  	  /* If the loop number is still greater than the number of
*************** build_classic_dir_vector (struct data_de
*** 1528,1546 ****
  	    abort ();	  
  	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
  	    {
! 	      
! 	    }
! 	  else
! 	    {
! 	      int dist = int_cst_value (SUB_DISTANCE (subscript));
! 	      
! 	      if (dist == 0)
! 		dir = dir_equal;
! 	      else if (dist > 0)
! 		dir = dir_positive;
! 	      else if (dist < 0)
! 		dir = dir_negative;
  	    }
  	  
  	  /* This is the subscript coupling test.  
  	     | loop i = 0, N, 1
--- 1995,2012 ----
  	    abort ();	  
  	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
  	    {
! 	      non_affine_dependence_relation (ddr);
! 	      return;
  	    }
+ 
+ 	  dist = int_cst_value (SUB_DISTANCE (subscript));
+ 
+ 	  if (dist == 0)
+ 	    dir = dir_equal;
+ 	  else if (dist > 0)
+ 	    dir = dir_positive;
+ 	  else if (dist < 0)
+ 	    dir = dir_negative;
  	  
  	  /* This is the subscript coupling test.  
  	     | loop i = 0, N, 1
*************** build_classic_dir_vector (struct data_de
*** 1608,1613 ****
--- 2074,2080 ----
    }
    
    DDR_DIR_VECT (ddr) = dir_v;
+   DDR_SIZE_VECT (ddr) = nb_loops;
  }
  
  /* Returns true when all the access functions of A are affine or
*************** compute_all_dependences (varray_type dat
*** 1692,1703 ****
  
  	a = VARRAY_GENERIC_PTR (datarefs, i);
  	b = VARRAY_GENERIC_PTR (datarefs, j);
- 
  	ddr = initialize_data_dependence_relation (a, b);
  
  	VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
  	compute_affine_dependence (ddr);
! 	compute_distance_vector (ddr);
        }
  }
  
--- 2159,2169 ----
  
  	a = VARRAY_GENERIC_PTR (datarefs, i);
  	b = VARRAY_GENERIC_PTR (datarefs, j);
  	ddr = initialize_data_dependence_relation (a, b);
  
  	VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
  	compute_affine_dependence (ddr);
! 	compute_subscript_distance (ddr);
        }
  }
  
*************** compute_all_dependences (varray_type dat
*** 1713,1718 ****
--- 2179,2186 ----
  static tree 
  find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
  {
+   bool dont_know_node_not_inserted = true;
+   bool loop_is_parallel = true;
    basic_block bb;
    block_stmt_iterator bsi;
    
*************** find_data_references_in_loop (struct loo
*** 1747,1757 ****
  					       true));
  
    	  else
! 	    return chrec_dont_know;
  	}
      }
  
!   return NULL_TREE;
  }
  
  
--- 2215,2245 ----
  					       true));
  
    	  else
! 	    {
! 	      if (dont_know_node_not_inserted)
! 		{
! 		  struct data_reference *res;
! 		  res = xmalloc (sizeof (struct data_reference));
! 		  DR_STMT (res) = NULL_TREE;
! 		  DR_REF (res) = NULL_TREE;
! 		  DR_ACCESS_FNS (res) = NULL;
! 		  DR_BASE_NAME (res) = NULL;
! 		  DR_IS_READ (res) = false;
! 		  VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
! 
! 		  dont_know_node_not_inserted = false;
! 		}
! 	    }
! 
! 	  /* When there are no defs in the loop, the loop is parallel.  */
! 	  if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
! 	      || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
! 	    loop_is_parallel = false;
  	}
      }
  
!   loop->parallel_p = loop_is_parallel;
!   return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
  }
  
  
*************** analyze_all_data_dependences (struct loo
*** 1841,1847 ****
        fprintf (dump_file, "\n\n");
  
        if (dump_flags & TDF_DETAILS)
! 	dump_dist_dir_vectors (dump_file, dependence_relations, loops->num);
  
        if (dump_flags & TDF_STATS)
  	{
--- 2329,2335 ----
        fprintf (dump_file, "\n\n");
  
        if (dump_flags & TDF_DETAILS)
! 	dump_dist_dir_vectors (dump_file, dependence_relations);
  
        if (dump_flags & TDF_STATS)
  	{
Index: tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.h,v
retrieving revision 1.1.2.20
diff -c -3 -p -r1.1.2.20 tree-data-ref.h
*** tree-data-ref.h	19 Aug 2004 20:57:03 -0000	1.1.2.20
--- tree-data-ref.h	1 Sep 2004 23:30:55 -0000
*************** struct subscript
*** 79,88 ****
    tree conflicting_iterations_in_a;
    tree conflicting_iterations_in_b;
    
!   /* These fields store the information about the iteration domain
       validity of the dependence relation.  */
!   tree last_conflict_in_a;
!   tree last_conflict_in_b;
    
    /* Distance from the iteration that access a conflicting element in
       A to the iteration that access this same conflicting element in
--- 79,87 ----
    tree conflicting_iterations_in_a;
    tree conflicting_iterations_in_b;
    
!   /* This field store the information about the iteration domain
       validity of the dependence relation.  */
!   tree last_conflict;
    
    /* Distance from the iteration that access a conflicting element in
       A to the iteration that access this same conflicting element in
*************** struct subscript
*** 93,100 ****
  
  #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
  #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
! #define SUB_LAST_CONFLICT_IN_A(SUB) SUB->last_conflict_in_a
! #define SUB_LAST_CONFLICT_IN_B(SUB) SUB->last_conflict_in_b
  #define SUB_DISTANCE(SUB) SUB->distance
  
  /* A data_dependence_relation represents a relation between two
--- 92,98 ----
  
  #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
  #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
! #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
  #define SUB_DISTANCE(SUB) SUB->distance
  
  /* A data_dependence_relation represents a relation between two
*************** struct data_dependence_relation
*** 128,133 ****
--- 126,134 ----
       the data_dependence_relation.  */
    varray_type subscripts;
  
+   /* The size of the direction/distance vectors.  */
+   int size_vect;
+ 
    /* The classic direction vector.  */
    lambda_vector dir_vect;
  
*************** struct data_dependence_relation
*** 144,149 ****
--- 145,151 ----
    VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
  #define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
  #define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
+ #define DDR_SIZE_VECT(DDR) DDR->size_vect
  #define DDR_DIR_VECT(DDR) DDR->dir_vect
  #define DDR_DIST_VECT(DDR) DDR->dist_vect
  
*************** extern struct data_reference * init_data
*** 159,165 ****
  extern struct data_reference *analyze_array (tree, tree, bool);
  
  extern void dump_subscript (FILE *, struct subscript *);
! extern void dump_dist_dir_vectors (FILE *, varray_type, unsigned int);
  extern void dump_data_reference (FILE *, struct data_reference *);
  extern void dump_data_references (FILE *, varray_type);
  extern void dump_data_dependence_relation (FILE *, 
--- 161,168 ----
  extern struct data_reference *analyze_array (tree, tree, bool);
  
  extern void dump_subscript (FILE *, struct subscript *);
! extern void dump_ddrs (FILE *, varray_type);
! extern void dump_dist_dir_vectors (FILE *, varray_type);
  extern void dump_data_reference (FILE *, struct data_reference *);
  extern void dump_data_references (FILE *, varray_type);
  extern void dump_data_dependence_relation (FILE *, 
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-loop-linear.c,v
retrieving revision 1.1.2.13
diff -c -3 -p -r1.1.2.13 tree-loop-linear.c
*** tree-loop-linear.c	19 Aug 2004 20:57:03 -0000	1.1.2.13
--- tree-loop-linear.c	1 Sep 2004 23:30:55 -0000
*************** Software Foundation, 59 Temple Place - S
*** 55,76 ****
     transform matrix for locality purposes.
     TODO: Completion of partial transforms.  */
  
! /* Gather statistics for loop interchange.  Initializes SUM the sum of
!    all the data dependence distances carried by loop LOOP_NUMBER.
!    NB_DEPS_NOT_CARRIED_BY_LOOP is initialized to the number of
!    dependence relations for which the loop LOOP_NUMBER is not carrying
!    any dependence.  */
  
  static void
  gather_interchange_stats (varray_type dependence_relations, 
  			  unsigned int loop_number, 
! 			  unsigned int *sum, 
! 			  unsigned int *nb_deps_not_carried_by_loop)
  {
    unsigned int i;
  
!   *sum = 0;
    *nb_deps_not_carried_by_loop = 0;
    for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
      {
        int dist;
--- 55,104 ----
     transform matrix for locality purposes.
     TODO: Completion of partial transforms.  */
  
! /* Gather statistics for loop interchange.  Initializes
!    - DEPENDENCE_STEPS the sum of all the data dependence distances
!    carried by loop LOOP_NUMBER,
! 
!    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
!    for which the loop LOOP_NUMBER is not carrying any dependence,
! 
!    - ACCESS_STRIDES the sum of all the strides in LOOP_NUMBER.
! 
!    Example: for the following loop,
! 
!    | loop_1 runs 1335 times
!    |   loop_2 runs 1335 times
!    |     A[{{0, +, 1}_1, +, 1335}_2]
!    |     B[{{0, +, 1}_1, +, 1335}_2]
!    |   endloop_2
!    |   A[{0, +, 1336}_1]
!    | endloop_1
! 
!    gather_interchange_stats (in loop_1) will return 
!    DEPENDENCE_STEPS = 3002
!    NB_DEPS_NOT_CARRIED_BY_LOOP = 5
!    ACCESS_STRIDES = 10694
! 
!    gather_interchange_stats (in loop_2) will return 
!    DEPENDENCE_STEPS = 3000
!    NB_DEPS_NOT_CARRIED_BY_LOOP = 7
!    ACCESS_STRIDES = 8010
!   */
  
  static void
  gather_interchange_stats (varray_type dependence_relations, 
+ 			  varray_type datarefs,
  			  unsigned int loop_number, 
! 			  unsigned int *dependence_steps, 
! 			  unsigned int *nb_deps_not_carried_by_loop, 
! 			  unsigned int *access_strides)
  {
    unsigned int i;
  
!   *dependence_steps = 0;
    *nb_deps_not_carried_by_loop = 0;
+   *access_strides = 0;
+ 
    for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
      {
        int dist;
*************** gather_interchange_stats (varray_type de
*** 78,88 ****
  	(struct data_dependence_relation *) 
  	VARRAY_GENERIC_PTR (dependence_relations, i);
  
        if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
  	{
! 	  /* FIXME: Some constants to tweak... maybe this could go as
! 	     a param for fast experimentations?  */
! 	  *sum += 100;
  	  continue;
  	}
  
--- 106,116 ----
  	(struct data_dependence_relation *) 
  	VARRAY_GENERIC_PTR (dependence_relations, i);
  
+       /* Compute the dependence strides.  */
+ 
        if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
  	{
! 	  (*dependence_steps) += 0;
  	  continue;
  	}
  
*************** gather_interchange_stats (varray_type de
*** 90,108 ****
  	 is no reuse of the data.  */
        if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
  	{
! 	  /* FIXME: Some constants to tweak... maybe this could go as
! 	     a param for fast experimentations?  */
! 	  *sum += 1000;
  	  continue;
  	}
  
        dist = DDR_DIST_VECT (ddr)[loop_number];
        if (dist == 0)
! 	*nb_deps_not_carried_by_loop++;
        else if (dist < 0)
! 	*sum += -dist;
        else
! 	*sum += dist;
      }
  }
  
--- 118,153 ----
  	 is no reuse of the data.  */
        if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
  	{
! 	  (*dependence_steps) += 0;
  	  continue;
  	}
  
        dist = DDR_DIST_VECT (ddr)[loop_number];
        if (dist == 0)
! 	(*nb_deps_not_carried_by_loop) += 1;
        else if (dist < 0)
! 	(*dependence_steps) += -dist;
        else
! 	(*dependence_steps) += dist;
!     }
! 
!   /* Compute the access strides.  */
!   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
!     {
!       unsigned int it;
!       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
! 
!       for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
! 	{
! 	  tree chrec = DR_ACCESS_FN (dr, it);
! 	  tree tstride = evolution_part_in_loop_num (chrec, loop_number + 1);
! 	  
! 	  if (tstride == NULL_TREE
! 	      || TREE_CODE (tstride) != INTEGER_CST)
! 	    continue;
! 	  
! 	  (*access_strides) += int_cst_value (tstride);
! 	}
      }
  }
  
*************** gather_interchange_stats (varray_type de
*** 113,122 ****
  static lambda_trans_matrix
  try_interchange_loops (lambda_trans_matrix trans, 
  		       unsigned int depth,		       
! 		       varray_type dependence_relations)
  {
    unsigned int loop_i, loop_j;
!   unsigned int steps_i, steps_j;
    unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
    struct data_dependence_relation *ddr;
  
--- 158,169 ----
  static lambda_trans_matrix
  try_interchange_loops (lambda_trans_matrix trans, 
  		       unsigned int depth,		       
! 		       varray_type dependence_relations,
! 		       varray_type datarefs)
  {
    unsigned int loop_i, loop_j;
!   unsigned int dependence_steps_i, dependence_steps_j;
!   unsigned int access_strides_i, access_strides_j;
    unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
    struct data_dependence_relation *ddr;
  
*************** try_interchange_loops (lambda_trans_matr
*** 131,163 ****
    for (loop_j = 1; loop_j < depth; loop_j++)
      for (loop_i = 0; loop_i < loop_j; loop_i++)
        {
! 	gather_interchange_stats (dependence_relations, loop_i, &steps_i, 
! 				  &nb_deps_not_carried_by_i);
! 	gather_interchange_stats (dependence_relations, loop_j, &steps_j, 
! 				  &nb_deps_not_carried_by_j);
  	
  	/* Heuristics for loop interchange profitability:
! 	   1. Inner loops should have smallest steps.
! 	   2. Inner loops should contain more dependence relations not
! 	   carried by the loop.
  	*/
! 	if (steps_i < steps_j 
! 	    || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j)
  	  {
  	    lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
  	
  	    /* Validate the resulting matrix.  When the transformation
! 	       is not valid, reverse to the previous matrix.  
! 	       
! 	       FIXME: In this case of transformation it could be
! 	       faster to verify the validity of the interchange
! 	       without applying the transform to the matrix.  But for
! 	       the moment do it cleanly: this is just a prototype.  */
  	    if (!lambda_transform_legal_p (trans, depth, dependence_relations))
  	      lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
  	  }
        }
!   
    return trans;
  }
  
--- 178,218 ----
    for (loop_j = 1; loop_j < depth; loop_j++)
      for (loop_i = 0; loop_i < loop_j; loop_i++)
        {
! 	gather_interchange_stats (dependence_relations, datarefs,
! 				  loop_i, 
! 				  &dependence_steps_i, 
! 				  &nb_deps_not_carried_by_i,
! 				  &access_strides_i);
! 	gather_interchange_stats (dependence_relations, datarefs,
! 				  loop_j, 
! 				  &dependence_steps_j, 
! 				  &nb_deps_not_carried_by_j, 
! 				  &access_strides_j);
  	
  	/* Heuristics for loop interchange profitability:
! 
! 	   1. (spatial locality) Inner loops should have smallest
!               dependence steps.
! 
! 	   2. (spatial locality) Inner loops should contain more
! 	   dependence relations not carried by the loop.
! 
! 	   3. (temporal locality) Inner loops should have smallest 
! 	      array access strides.
  	*/
! 	if (dependence_steps_i < dependence_steps_j 
! 	    || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
! 	    || access_strides_i < access_strides_j)
  	  {
  	    lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
  	
  	    /* Validate the resulting matrix.  When the transformation
! 	       is not valid, reverse to the previous transformation.  */
  	    if (!lambda_transform_legal_p (trans, depth, dependence_relations))
  	      lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
  	  }
        }
! 
    return trans;
  }
  
*************** linear_transform_loops (struct loops *lo
*** 220,232 ****
        compute_data_dependences_for_loop (depth, loop_nest,
  					 &datarefs, &dependence_relations);
        if (dump_file && (dump_flags & TDF_DETAILS))
! 	dump_dist_dir_vectors (dump_file, dependence_relations, loops->num);
  
        /* Build the transformation matrix.  */
        trans = lambda_trans_matrix_new (depth, depth);
  #if 1
        lambda_matrix_id (LTM_MATRIX (trans), depth);
!       trans = try_interchange_loops (trans, depth, dependence_relations);
  #else
        /* This is a 2x2 interchange matrix.  */
        LTM_MATRIX (trans)[0][0] = 0;
--- 275,288 ----
        compute_data_dependences_for_loop (depth, loop_nest,
  					 &datarefs, &dependence_relations);
        if (dump_file && (dump_flags & TDF_DETAILS))
! 	dump_dist_dir_vectors (dump_file, dependence_relations);
  
        /* Build the transformation matrix.  */
        trans = lambda_trans_matrix_new (depth, depth);
  #if 1
        lambda_matrix_id (LTM_MATRIX (trans), depth);
!       trans = try_interchange_loops (trans, depth, dependence_relations, 
! 				     datarefs);
  #else
        /* This is a 2x2 interchange matrix.  */
        LTM_MATRIX (trans)[0][0] = 0;
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 1.1.2.70.2.13
diff -c -3 -p -r1.1.2.70.2.13 tree-pretty-print.c
*** tree-pretty-print.c	18 Jul 2004 23:13:37 -0000	1.1.2.70.2.13
--- tree-pretty-print.c	1 Sep 2004 23:30:55 -0000
*************** dump_generic_node (pretty_printer *buffe
*** 273,280 ****
        break;
  
      case TREE_VEC:
!       dump_generic_node (buffer, BINFO_TYPE (node), spc, flags, false);
!       break;
  
      case BLOCK:
        NIY;
--- 273,294 ----
        break;
  
      case TREE_VEC:
!       {
! 	int it;
! 	pp_string (buffer, "TREE_VEC ");
! 	pp_character (buffer, '(');
! 	for (it = 0; it < TREE_VEC_LENGTH (node) - 1; it++)
! 	  {
! 	    dump_generic_node (buffer, TREE_VEC_ELT (node, it), spc, flags, 
! 			       false);
! 	    pp_character (buffer, ',');
! 	    pp_space (buffer);
! 	  }
! 	dump_generic_node (buffer, TREE_VEC_ELT (node, it), spc, flags, 
! 			   false);
! 	pp_character (buffer, ')');
! 	break;
!       }
  
      case BLOCK:
        NIY;


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]