OSDN Git Service

57f20bb730792326410669b3e5be63d79b0a9f19
[pf3gnuchains/gcc-fork.git] / gcc / tree-data-ref.c
1 /* Data references and dependences detectors.
2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
3    Contributed by Sebastian Pop <s.pop@laposte.net>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 /* This pass walks a given loop structure searching for array
23    references.  The information about the array accesses is recorded
24    in DATA_REFERENCE structures. 
25    
26    The basic test for determining the dependences is: 
27    given two access functions chrec1 and chrec2 to a same array, and 
28    x and y two vectors from the iteration domain, the same element of 
29    the array is accessed twice at iterations x and y if and only if:
30    |             chrec1 (x) == chrec2 (y).
31    
32    The goals of this analysis are:
33    
34    - to determine the independence: the relation between two
35      independent accesses is qualified with the chrec_known (this
36      information allows a loop parallelization),
37      
38    - when two data references access the same data, to qualify the
39      dependence relation with classic dependence representations:
40      
41        - distance vectors
42        - direction vectors
43        - loop carried level dependence
44        - polyhedron dependence
45      or with the chains of recurrences based representation,
46      
47    - to define a knowledge base for storing the data dependences 
48      information,
49      
50    - to define an interface to access this data.
51    
52    
53    Definitions:
54    
55    - subscript: given two array accesses a subscript is the tuple
56    composed of the access functions for a given dimension.  Example:
57    Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58    (f1, g1), (f2, g2), (f3, g3).
59
60    - Diophantine equation: an equation whose coefficients and
61    solutions are integer constants, for example the equation 
62    |   3*x + 2*y = 1
63    has an integer solution x = 1 and y = -1.
64      
65    References:
66    
67    - "Advanced Compilation for High Performance Computing" by Randy
68    Allen and Ken Kennedy.
69    http://citeseer.ist.psu.edu/goff91practical.html 
70    
71    - "Loop Transformations for Restructuring Compilers - The Foundations" 
72    by Utpal Banerjee.
73
74    
75 */
76
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "tm.h"
81 #include "errors.h"
82 #include "ggc.h"
83 #include "tree.h"
84
85 /* These RTL headers are needed for basic-block.h.  */
86 #include "rtl.h"
87 #include "basic-block.h"
88 #include "diagnostic.h"
89 #include "tree-flow.h"
90 #include "tree-dump.h"
91 #include "timevar.h"
92 #include "cfgloop.h"
93 #include "tree-chrec.h"
94 #include "tree-data-ref.h"
95 #include "tree-scalar-evolution.h"
96 #include "tree-pass.h"
97 #include "lambda.h"
98
99 \f
100 /* This is the simplest data dependence test: determines whether the
101    data references A and B access the same array/region. If can't determine -
102    return false; Otherwise, return true, and DIFFER_P will record
103    the result. This utility will not be necessary when alias_sets_conflict_p
104    will be less conservative.  */
105
106 bool
107 array_base_name_differ_p (struct data_reference *a,
108                           struct data_reference *b,
109                           bool *differ_p)
110 {
111   tree base_a = DR_BASE_NAME (a);
112   tree base_b = DR_BASE_NAME (b);
113   tree ta = TREE_TYPE (base_a);
114   tree tb = TREE_TYPE (base_b);
115
116
117   /** Determine if same base  **/
118
119   /* array accesses: a[i],b[i] or pointer accesses: *a,*b. bases are a,b.  */
120   if (base_a == base_b)
121     {
122       *differ_p = false;
123       return true;
124     }
125
126   /* pointer based accesses - (*p)[i],(*q)[j]. bases are (*p),(*q)  */
127   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
128       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
129     {
130       *differ_p = false;
131       return true;
132     }
133
134   /* record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b.  */ 
135   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
136       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
137       && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
138     {
139       *differ_p = false;
140       return true;
141     }
142
143
144   /** Determine if different bases  **/
145
146   /* at this point we know that base_a != base_b. However, pointer accesses
147      of the form x=(*p) and y=(*q), which bases are p and q, may still by pointing
148      to the same base. In SSAed GIMPLE p and q will be SSA_NAMES in this case.
149      Therefore, here we check if it's really two diferent declarations.  */
150   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
151     {
152       *differ_p = true;
153       return true;
154     }
155
156   /* compare two record/union bases s.a and t.b: 
157      s != t or (a != b and s and t are not unions)  */
158   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
159       && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
160            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
161            && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
162           || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE 
163               && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
164               && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
165     {
166       *differ_p = true;
167       return true;
168     }
169
170   /* compare a record/union access and an array access.  */ 
171   if ((TREE_CODE (base_a) == VAR_DECL
172        && (TREE_CODE (base_b) == COMPONENT_REF
173            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
174       || (TREE_CODE (base_b) == VAR_DECL
175        && (TREE_CODE (base_a) == COMPONENT_REF
176            && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
177     {
178       *differ_p = true;
179       return true;
180     }
181
182   if (!alias_sets_conflict_p (get_alias_set (base_a), get_alias_set (base_b)))
183     {
184       *differ_p = true;
185       return true;
186     }
187
188   /* An insn writing through a restricted pointer is "independent" of any
189      insn reading or writing through a different pointer, in the same
190      block/scope.
191    */
192   if ((TREE_CODE (ta) == POINTER_TYPE && TYPE_RESTRICT (ta)
193        && !DR_IS_READ(a))
194       || (TREE_CODE (tb) == POINTER_TYPE && TYPE_RESTRICT (tb)
195           && !DR_IS_READ(b)))
196     {
197       *differ_p = true;
198       return true;
199     }
200
201   *differ_p = false; /* Don't know, but be conservative.  */
202   return false;
203 }
204
205 /* Returns true iff A divides B.  */
206
207 static inline bool 
208 tree_fold_divides_p (tree type, 
209                      tree a, 
210                      tree b)
211 {
212   if (integer_onep (a))
213     return true;
214   
215   /* Determines whether (A == gcd (A, B)).  */
216   return integer_zerop 
217     (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
218 }
219
220 /* Bezout: Let A1 and A2 be two integers; there exist two integers U11
221    and U12 such that, 
222    
223    |  U11 * A1 + U12 * A2 = gcd (A1, A2).
224    
225    This function computes the greatest common divisor using the
226    Blankinship algorithm.  The gcd is returned, and the coefficients
227    of the unimodular matrix U are (U11, U12, U21, U22) such that, 
228
229    |  U.A = S
230    
231    |  (U11 U12) (A1) = (gcd)
232    |  (U21 U22) (A2)   (0)
233    
234    FIXME: Use lambda_..._hermite for implementing this function.
235 */
236
237 static tree 
238 tree_fold_bezout (tree a1, 
239                   tree a2,
240                   tree *u11, tree *u12,
241                   tree *u21, tree *u22)
242 {
243   tree s1, s2;
244   
245   /* Initialize S with the coefficients of A.  */
246   s1 = a1;
247   s2 = a2;
248   
249   /* Initialize the U matrix */
250   *u11 = integer_one_node; 
251   *u12 = integer_zero_node;
252   *u21 = integer_zero_node;
253   *u22 = integer_one_node;
254   
255   if (integer_zerop (a1)
256       || integer_zerop (a2))
257     return integer_zero_node;
258   
259   while (!integer_zerop (s2))
260     {
261       int sign;
262       tree z, zu21, zu22, zs2;
263       
264       sign = tree_int_cst_sgn (s1) * tree_int_cst_sgn (s2);
265       z = fold (build (FLOOR_DIV_EXPR, integer_type_node, 
266                        fold (build1 (ABS_EXPR, integer_type_node, s1)), 
267                        fold (build1 (ABS_EXPR, integer_type_node, s2))));
268       zu21 = fold (build (MULT_EXPR, integer_type_node, z, *u21));
269       zu22 = fold (build (MULT_EXPR, integer_type_node, z, *u22));
270       zs2 = fold (build (MULT_EXPR, integer_type_node, z, s2));
271       
272       /* row1 -= z * row2.  */
273       if (sign < 0)
274         {
275           *u11 = fold (build (PLUS_EXPR, integer_type_node, *u11, zu21));
276           *u12 = fold (build (PLUS_EXPR, integer_type_node, *u12, zu22));
277           s1 = fold (build (PLUS_EXPR, integer_type_node, s1, zs2));
278         }
279       else if (sign > 0)
280         {
281           *u11 = fold (build (MINUS_EXPR, integer_type_node, *u11, zu21));
282           *u12 = fold (build (MINUS_EXPR, integer_type_node, *u12, zu22));
283           s1 = fold (build (MINUS_EXPR, integer_type_node, s1, zs2));
284         }
285       else
286         /* Should not happen.  */
287         abort ();
288       
289       /* Interchange row1 and row2.  */
290       {
291         tree flip;
292         
293         flip = *u11;
294         *u11 = *u21;
295         *u21 = flip;
296
297         flip = *u12;
298         *u12 = *u22;
299         *u22 = flip;
300         
301         flip = s1;
302         s1 = s2;
303         s2 = flip;
304       }
305     }
306   
307   if (tree_int_cst_sgn (s1) < 0)
308     {
309       *u11 = fold (build (MULT_EXPR, integer_type_node, *u11, 
310                           integer_minus_one_node));
311       *u12 = fold (build (MULT_EXPR, integer_type_node, *u12, 
312                                  integer_minus_one_node));
313       s1 = fold (build (MULT_EXPR, integer_type_node, s1, integer_minus_one_node));
314     }
315   
316   return s1;
317 }
318
319 \f
320
321 /* Dump into FILE all the data references from DATAREFS.  */ 
322
323 void 
324 dump_data_references (FILE *file, 
325                       varray_type datarefs)
326 {
327   unsigned int i;
328   
329   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
330     dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
331 }
332
333 /* Dump into FILE all the dependence relations from DDR.  */ 
334
335 void 
336 dump_data_dependence_relations (FILE *file, 
337                                 varray_type ddr)
338 {
339   unsigned int i;
340   
341   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
342     dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
343 }
344
345 /* Dump function for a DATA_REFERENCE structure.  */
346
347 void 
348 dump_data_reference (FILE *outf, 
349                      struct data_reference *dr)
350 {
351   unsigned int i;
352   
353   fprintf (outf, "(Data Ref: \n  stmt: ");
354   print_generic_stmt (outf, DR_STMT (dr), 0);
355   fprintf (outf, "  ref: ");
356   print_generic_stmt (outf, DR_REF (dr), 0);
357   fprintf (outf, "  base_name: ");
358   print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
359   
360   for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
361     {
362       fprintf (outf, "  Access function %d: ", i);
363       print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
364     }
365   fprintf (outf, ")\n");
366 }
367
368 /* Dump function for a DATA_DEPENDENCE_RELATION structure.  */
369
370 void 
371 dump_data_dependence_relation (FILE *outf, 
372                                struct data_dependence_relation *ddr)
373 {
374   unsigned int i;
375   struct data_reference *dra, *drb;
376   
377   dra = DDR_A (ddr);
378   drb = DDR_B (ddr);
379   
380   if (dra && drb)
381     fprintf (outf, "(Data Dep:");
382   else
383     fprintf (outf, "(Data Dep:");
384
385   if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
386     fprintf (outf, "    (don't know)\n");
387   
388   else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
389     fprintf (outf, "    (no dependence)\n");
390   
391   else
392     {
393       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
394         {
395           tree chrec;
396           struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
397           
398           fprintf (outf, "\n (subscript %d:\n", i);
399           fprintf (outf, "  access_fn_A: ");
400           print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
401           fprintf (outf, "  access_fn_B: ");
402           print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
403           
404           chrec = SUB_CONFLICTS_IN_A (subscript);
405           fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
406           print_generic_stmt (outf, chrec, 0);
407           if (chrec == chrec_known)
408             fprintf (outf, "    (no dependence)\n");
409           else if (chrec_contains_undetermined (chrec))
410             fprintf (outf, "    (don't know)\n");
411           else
412             {
413               tree last_iteration = SUB_LAST_CONFLICT_IN_A (subscript);
414               fprintf (outf, "  last_iteration_that_access_an_element_twice_in_A: ");
415               print_generic_stmt (outf, last_iteration, 0);
416             }
417           
418           chrec = SUB_CONFLICTS_IN_B (subscript);
419           fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
420           print_generic_stmt (outf, chrec, 0);
421           if (chrec == chrec_known)
422             fprintf (outf, "    (no dependence)\n");
423           else if (chrec_contains_undetermined (chrec))
424             fprintf (outf, "    (don't know)\n");
425           else
426             {
427               tree last_iteration = SUB_LAST_CONFLICT_IN_B (subscript);
428               fprintf (outf, "  last_iteration_that_access_an_element_twice_in_B: ");
429               print_generic_stmt (outf, last_iteration, 0);
430             }
431       
432           fprintf (outf, " )\n");
433         }
434   
435       fprintf (outf, " (Distance Vector: \n");
436       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
437         {
438           struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
439       
440           fprintf (outf, "(");
441           print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
442           fprintf (outf, ")\n");
443         }
444       fprintf (outf, " )\n");
445     }
446
447   fprintf (outf, ")\n");
448 }
449
450
451
452 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure.  */
453
454 void
455 dump_data_dependence_direction (FILE *file, 
456                                 enum data_dependence_direction dir)
457 {
458   switch (dir)
459     {
460     case dir_positive: 
461       fprintf (file, "+");
462       break;
463       
464     case dir_negative:
465       fprintf (file, "-");
466       break;
467       
468     case dir_equal:
469       fprintf (file, "=");
470       break;
471       
472     case dir_positive_or_negative:
473       fprintf (file, "+-");
474       break;
475       
476     case dir_positive_or_equal: 
477       fprintf (file, "+=");
478       break;
479       
480     case dir_negative_or_equal: 
481       fprintf (file, "-=");
482       break;
483       
484     case dir_star: 
485       fprintf (file, "*"); 
486       break;
487       
488     default: 
489       break;
490     }
491 }
492
493 \f
494
495 /* Given an ARRAY_REF node REF, records its access functions.
496    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
497    ie. the constant "3", then recursively call the function on opnd0,
498    ie. the ARRAY_REF "A[i]".  The function returns the base name:
499    "A".  */
500
501 static tree
502 analyze_array_indexes (struct loop *loop,
503                        varray_type access_fns, 
504                        tree ref)
505 {
506   tree opnd0, opnd1;
507   tree access_fn;
508   
509   opnd0 = TREE_OPERAND (ref, 0);
510   opnd1 = TREE_OPERAND (ref, 1);
511   
512   /* The detection of the evolution function for this data access is
513      postponed until the dependence test.  This lazy strategy avoids
514      the computation of access functions that are of no interest for
515      the optimizers.  */
516   access_fn = instantiate_parameters 
517     (loop, analyze_scalar_evolution (loop, opnd1));
518   
519   VARRAY_PUSH_TREE (access_fns, access_fn);
520   
521   /* Recursively record other array access functions.  */
522   if (TREE_CODE (opnd0) == ARRAY_REF)
523     return analyze_array_indexes (loop, access_fns, opnd0);
524   
525   /* Return the base name of the data access.  */
526   else
527     return opnd0;
528 }
529
530 /* For a data reference REF contained in the statemet STMT, initialize
531    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
532    set to true when REF is in the right hand side of an
533    assignment.  */
534
535 struct data_reference *
536 analyze_array (tree stmt, tree ref, bool is_read)
537 {
538   struct data_reference *res;
539
540   if (dump_file && (dump_flags & TDF_DETAILS))
541     {
542       fprintf (dump_file, "(analyze_array \n");
543       fprintf (dump_file, "  (ref = ");
544       print_generic_stmt (dump_file, ref, 0);
545       fprintf (dump_file, ")\n");
546     }
547   
548   res = xmalloc (sizeof (struct data_reference));
549   
550   DR_STMT (res) = stmt;
551   DR_REF (res) = ref;
552   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
553   DR_BASE_NAME (res) = analyze_array_indexes 
554     (loop_containing_stmt (stmt), DR_ACCESS_FNS (res), ref);
555   DR_IS_READ (res) = is_read;
556   
557   if (dump_file && (dump_flags & TDF_DETAILS))
558     fprintf (dump_file, ")\n");
559   
560   return res;
561 }
562
563 /* For a data reference REF contained in the statemet STMT, initialize
564    a DATA_REFERENCE structure, and return it.  */
565
566 struct data_reference *
567 init_data_ref (tree stmt, 
568                tree ref,
569                tree base,
570                tree access_fn,
571                bool is_read)
572 {
573   struct data_reference *res;
574
575   if (dump_file && (dump_flags & TDF_DETAILS))
576     {
577       fprintf (dump_file, "(init_data_ref \n");
578       fprintf (dump_file, "  (ref = ");
579       print_generic_stmt (dump_file, ref, 0);
580       fprintf (dump_file, ")\n");
581     }
582   
583   res = xmalloc (sizeof (struct data_reference));
584   
585   DR_STMT (res) = stmt;
586   DR_REF (res) = ref;
587   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
588   DR_BASE_NAME (res) = base;
589   VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
590   DR_IS_READ (res) = is_read;
591   
592   if (dump_file && (dump_flags & TDF_DETAILS))
593     fprintf (dump_file, ")\n");
594   
595   return res;
596 }
597
598 \f
599
600 /* When there exists a dependence relation, determine its distance
601    vector.  */
602
603 static void
604 compute_distance_vector (struct data_dependence_relation *ddr)
605 {
606   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
607     {
608       unsigned int i;
609       
610       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
611         {
612           tree conflicts_a, conflicts_b, difference;
613           struct subscript *subscript;
614           
615           subscript = DDR_SUBSCRIPT (ddr, i);
616           conflicts_a = SUB_CONFLICTS_IN_A (subscript);
617           conflicts_b = SUB_CONFLICTS_IN_B (subscript);
618           difference = chrec_fold_minus 
619             (integer_type_node, conflicts_b, conflicts_a);
620           
621           if (evolution_function_is_constant_p (difference))
622             SUB_DISTANCE (subscript) = difference;
623           
624           else
625             SUB_DISTANCE (subscript) = chrec_dont_know;
626         }
627     }
628 }
629
630 /* Initialize a ddr.  */
631
632 struct data_dependence_relation *
633 initialize_data_dependence_relation (struct data_reference *a, 
634                                      struct data_reference *b)
635 {
636   struct data_dependence_relation *res;
637   bool differ_p;
638   
639   res = xmalloc (sizeof (struct data_dependence_relation));
640   DDR_A (res) = a;
641   DDR_B (res) = b;
642
643   if (a == NULL || b == NULL 
644       || DR_BASE_NAME (a) == NULL_TREE
645       || DR_BASE_NAME (b) == NULL_TREE)
646     DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
647
648   /* When the dimensions of A and B differ, we directly initialize
649      the relation to "there is no dependence": chrec_known.  */
650   else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
651            || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
652     DDR_ARE_DEPENDENT (res) = chrec_known;
653   
654   else
655     {
656       unsigned int i;
657       DDR_ARE_DEPENDENT (res) = NULL_TREE;
658       DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
659       
660       for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
661         {
662           struct subscript *subscript;
663           
664           subscript = xmalloc (sizeof (struct subscript));
665           SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
666           SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
667           SUB_LAST_CONFLICT_IN_A (subscript) = chrec_dont_know;
668           SUB_LAST_CONFLICT_IN_B (subscript) = chrec_dont_know;
669           SUB_DISTANCE (subscript) = chrec_dont_know;
670           VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
671         }
672     }
673   
674   return res;
675 }
676
677 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
678    description.  */
679
680 static inline void
681 finalize_ddr_dependent (struct data_dependence_relation *ddr, 
682                         tree chrec)
683 {
684   if (dump_file && (dump_flags & TDF_DETAILS))
685     {
686       fprintf (dump_file, "(dependence classified: ");
687       print_generic_expr (dump_file, chrec, 0);
688       fprintf (dump_file, ")\n");
689     }
690
691   DDR_ARE_DEPENDENT (ddr) = chrec;  
692   varray_clear (DDR_SUBSCRIPTS (ddr));
693 }
694
695 \f
696
697 /* This section contains the classic Banerjee tests.  */
698
699 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
700    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
701
702 static inline bool
703 ziv_subscript_p (tree chrec_a, 
704                  tree chrec_b)
705 {
706   return (evolution_function_is_constant_p (chrec_a)
707           && evolution_function_is_constant_p (chrec_b));
708 }
709
710 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
711    variable, i.e., if the SIV (Single Index Variable) test is true.  */
712
713 static bool
714 siv_subscript_p (tree chrec_a,
715                  tree chrec_b)
716 {
717   if ((evolution_function_is_constant_p (chrec_a)
718        && evolution_function_is_univariate_p (chrec_b))
719       || (evolution_function_is_constant_p (chrec_b)
720           && evolution_function_is_univariate_p (chrec_a)))
721     return true;
722   
723   if (evolution_function_is_univariate_p (chrec_a)
724       && evolution_function_is_univariate_p (chrec_b))
725     {
726       switch (TREE_CODE (chrec_a))
727         {
728         case POLYNOMIAL_CHREC:
729           switch (TREE_CODE (chrec_b))
730             {
731             case POLYNOMIAL_CHREC:
732               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
733                 return false;
734               
735             default:
736               return true;
737             }
738           
739         default:
740           return true;
741         }
742     }
743   
744   return false;
745 }
746
747 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
748    *OVERLAPS_B are initialized to the functions that describe the
749    relation between the elements accessed twice by CHREC_A and
750    CHREC_B.  For k >= 0, the following property is verified:
751
752    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
753
754 static void 
755 analyze_ziv_subscript (tree chrec_a, 
756                        tree chrec_b, 
757                        tree *overlaps_a,
758                        tree *overlaps_b)
759 {
760   tree difference;
761   
762   if (dump_file && (dump_flags & TDF_DETAILS))
763     fprintf (dump_file, "(analyze_ziv_subscript \n");
764   
765   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
766   
767   switch (TREE_CODE (difference))
768     {
769     case INTEGER_CST:
770       if (integer_zerop (difference))
771         {
772           /* The difference is equal to zero: the accessed index
773              overlaps for each iteration in the loop.  */
774           *overlaps_a = integer_zero_node;
775           *overlaps_b = integer_zero_node;
776         }
777       else
778         {
779           /* The accesses do not overlap.  */
780           *overlaps_a = chrec_known;
781           *overlaps_b = chrec_known;      
782         }
783       break;
784       
785     default:
786       /* We're not sure whether the indexes overlap.  For the moment, 
787          conservatively answer "don't know".  */
788       *overlaps_a = chrec_dont_know;
789       *overlaps_b = chrec_dont_know;      
790       break;
791     }
792   
793   if (dump_file && (dump_flags & TDF_DETAILS))
794     fprintf (dump_file, ")\n");
795 }
796
797 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
798    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
799    *OVERLAPS_B are initialized to the functions that describe the
800    relation between the elements accessed twice by CHREC_A and
801    CHREC_B.  For k >= 0, the following property is verified:
802
803    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
804
805 static void
806 analyze_siv_subscript_cst_affine (tree chrec_a, 
807                                   tree chrec_b,
808                                   tree *overlaps_a, 
809                                   tree *overlaps_b)
810 {
811   bool value0, value1, value2;
812   tree difference = chrec_fold_minus 
813     (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
814   
815   if (!chrec_is_positive (initial_condition (difference), &value0))
816     {
817       *overlaps_a = chrec_dont_know;
818       *overlaps_b = chrec_dont_know;
819       return;
820     }
821   else
822     {
823       if (value0 == false)
824         {
825           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
826             {
827               *overlaps_a = chrec_dont_know;
828               *overlaps_b = chrec_dont_know;      
829               return;
830             }
831           else
832             {
833               if (value1 == true)
834                 {
835                   /* Example:  
836                      chrec_a = 12
837                      chrec_b = {10, +, 1}
838                   */
839                   
840                   if (tree_fold_divides_p 
841                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
842                     {
843                       *overlaps_a = integer_zero_node;
844                       *overlaps_b = fold 
845                         (build (EXACT_DIV_EXPR, integer_type_node, 
846                                 fold (build1 (ABS_EXPR, integer_type_node, difference)), 
847                                 CHREC_RIGHT (chrec_b)));
848                       return;
849                     }
850                   
851                   /* When the step does not divides the difference, there are
852                      no overlaps.  */
853                   else
854                     {
855                       *overlaps_a = chrec_known;
856                       *overlaps_b = chrec_known;      
857                       return;
858                     }
859                 }
860               
861               else
862                 {
863                   /* Example:  
864                      chrec_a = 12
865                      chrec_b = {10, +, -1}
866                      
867                      In this case, chrec_a will not overlap with chrec_b.  */
868                   *overlaps_a = chrec_known;
869                   *overlaps_b = chrec_known;
870                   return;
871                 }
872             }
873         }
874       else 
875         {
876           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
877             {
878               *overlaps_a = chrec_dont_know;
879               *overlaps_b = chrec_dont_know;      
880               return;
881             }
882           else
883             {
884               if (value2 == false)
885                 {
886                   /* Example:  
887                      chrec_a = 3
888                      chrec_b = {10, +, -1}
889                   */
890                   if (tree_fold_divides_p 
891                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
892                     {
893                       *overlaps_a = integer_zero_node;
894                       *overlaps_b = fold 
895                         (build (EXACT_DIV_EXPR, integer_type_node, difference, 
896                                 CHREC_RIGHT (chrec_b)));
897                       return;
898                     }
899                   
900                   /* When the step does not divides the difference, there
901                      are no overlaps.  */
902                   else
903                     {
904                       *overlaps_a = chrec_known;
905                       *overlaps_b = chrec_known;      
906                       return;
907                     }
908                 }
909               else
910                 {
911                   /* Example:  
912                      chrec_a = 3  
913                      chrec_b = {4, +, 1}
914                  
915                      In this case, chrec_a will not overlap with chrec_b.  */
916                   *overlaps_a = chrec_known;
917                   *overlaps_b = chrec_known;
918                   return;
919                 }
920             }
921         }
922     }
923 }
924
925 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is an
926    affine function, and CHREC_B is a constant.  *OVERLAPS_A and
927    *OVERLAPS_B are initialized to the functions that describe the
928    relation between the elements accessed twice by CHREC_A and
929    CHREC_B.  For k >= 0, the following property is verified:
930
931    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
932
933 static void
934 analyze_siv_subscript_affine_cst (tree chrec_a, 
935                                   tree chrec_b,
936                                   tree *overlaps_a, 
937                                   tree *overlaps_b)
938 {
939   analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a);
940 }
941
942 /* Determines the overlapping elements due to accesses CHREC_A and
943    CHREC_B, that are affine functions.  This is a part of the
944    subscript analyzer.  */
945
946 static void
947 analyze_subscript_affine_affine (tree chrec_a, 
948                                  tree chrec_b,
949                                  tree *overlaps_a, 
950                                  tree *overlaps_b)
951 {
952   tree left_a, left_b, right_a, right_b;
953   
954   if (dump_file && (dump_flags & TDF_DETAILS))
955     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
956   
957   /* For determining the initial intersection, we have to solve a
958      Diophantine equation.  This is the most time consuming part.
959      
960      For answering to the question: "Is there a dependence?" we have
961      to prove that there exists a solution to the Diophantine
962      equation, and that the solution is in the iteration domain,
963      ie. the solution is positive or zero, and that the solution
964      happens before the upper bound loop.nb_iterations.  Otherwise
965      there is no dependence.  This function outputs a description of
966      the iterations that hold the intersections.  */
967
968   left_a = CHREC_LEFT (chrec_a);
969   left_b = CHREC_LEFT (chrec_b);
970   right_a = CHREC_RIGHT (chrec_a);
971   right_b = CHREC_RIGHT (chrec_b);
972   
973   if (chrec_zerop (chrec_fold_minus (integer_type_node, left_a, left_b)))
974     {
975       /* The first element accessed twice is on the first
976          iteration.  */
977       *overlaps_a = build_polynomial_chrec 
978         (CHREC_VARIABLE (chrec_b), integer_zero_node, integer_one_node);
979       *overlaps_b = build_polynomial_chrec 
980         (CHREC_VARIABLE (chrec_a), integer_zero_node, integer_one_node);
981     }
982   
983   else if (TREE_CODE (left_a) == INTEGER_CST
984            && TREE_CODE (left_b) == INTEGER_CST
985            && TREE_CODE (right_a) == INTEGER_CST 
986            && TREE_CODE (right_b) == INTEGER_CST
987            
988            /* Both functions should have the same evolution sign.  */
989            && ((tree_int_cst_sgn (right_a) > 0 
990                 && tree_int_cst_sgn (right_b) > 0)
991                || (tree_int_cst_sgn (right_a) < 0
992                    && tree_int_cst_sgn (right_b) < 0)))
993     {
994       /* Here we have to solve the Diophantine equation.  Reference
995          book: "Loop Transformations for Restructuring Compilers - The
996          Foundations" by Utpal Banerjee, pages 59-80.
997          
998          ALPHA * X0 = BETA * Y0 + GAMMA.  
999          
1000          with:
1001          ALPHA = RIGHT_A
1002          BETA = RIGHT_B
1003          GAMMA = LEFT_B - LEFT_A
1004          CHREC_A = {LEFT_A, +, RIGHT_A}
1005          CHREC_B = {LEFT_B, +, RIGHT_B}
1006          
1007          The Diophantine equation has a solution if and only if gcd
1008          (ALPHA, BETA) divides GAMMA.  This is commonly known under
1009          the name of the "gcd-test".
1010       */
1011       tree alpha, beta, gamma;
1012       tree la, lb;
1013       tree gcd_alpha_beta;
1014       tree u11, u12, u21, u22;
1015
1016       /* Both alpha and beta have to be integer_type_node. The gcd
1017          function does not work correctly otherwise.  */
1018       alpha = copy_node (right_a);
1019       beta = copy_node (right_b);
1020       la = copy_node (left_a);
1021       lb = copy_node (left_b);
1022       TREE_TYPE (alpha) = integer_type_node;
1023       TREE_TYPE (beta) = integer_type_node;
1024       TREE_TYPE (la) = integer_type_node;
1025       TREE_TYPE (lb) = integer_type_node;
1026       
1027       gamma = fold (build (MINUS_EXPR, integer_type_node, lb, la));
1028       
1029       /* FIXME: Use lambda_*_Hermite for implementing Bezout.  */
1030       gcd_alpha_beta = tree_fold_bezout 
1031         (alpha, 
1032          fold (build (MULT_EXPR, integer_type_node, beta, 
1033                       integer_minus_one_node)),
1034          &u11, &u12, 
1035          &u21, &u22);
1036       
1037       if (dump_file && (dump_flags & TDF_DETAILS))
1038         {
1039           fprintf (dump_file, "  (alpha = ");
1040           print_generic_expr (dump_file, alpha, 0);
1041           fprintf (dump_file, ")\n  (beta = ");
1042           print_generic_expr (dump_file, beta, 0);
1043           fprintf (dump_file, ")\n  (gamma = ");
1044           print_generic_expr (dump_file, gamma, 0);
1045           fprintf (dump_file, ")\n  (gcd_alpha_beta = ");
1046           print_generic_expr (dump_file, gcd_alpha_beta, 0);
1047           fprintf (dump_file, ")\n");
1048         }
1049       
1050       /* The classic "gcd-test".  */
1051       if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma))
1052         {
1053           /* The "gcd-test" has determined that there is no integer
1054              solution, ie. there is no dependence.  */
1055           *overlaps_a = chrec_known;
1056           *overlaps_b = chrec_known;
1057         }
1058       
1059       else
1060         {
1061           /* The solutions are given by:
1062              | 
1063              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [X]
1064              |                           [u21 u22]    [Y]
1065              
1066              For a given integer t.  Using the following variables,
1067              
1068              | i0 = u11 * gamma / gcd_alpha_beta
1069              | j0 = u12 * gamma / gcd_alpha_beta
1070              | i1 = u21
1071              | j1 = u22
1072              
1073              the solutions are:
1074              
1075              | x = i0 + i1 * t, 
1076              | y = j0 + j1 * t.  */
1077           
1078           tree i0, j0, i1, j1, t;
1079           tree gamma_gcd;
1080           
1081           /* X0 and Y0 are the first iterations for which there is a
1082              dependence.  X0, Y0 are two solutions of the Diophantine
1083              equation: chrec_a (X0) = chrec_b (Y0).  */
1084           tree x0, y0;
1085       
1086           /* Exact div because in this case gcd_alpha_beta divides
1087              gamma.  */
1088           gamma_gcd = fold (build (EXACT_DIV_EXPR, integer_type_node, gamma, 
1089                                    gcd_alpha_beta));
1090           i0 = fold (build (MULT_EXPR, integer_type_node, u11, gamma_gcd));
1091           j0 = fold (build (MULT_EXPR, integer_type_node, u12, gamma_gcd));
1092           i1 = u21;
1093           j1 = u22;
1094           
1095           if ((tree_int_cst_sgn (i1) == 0
1096                && tree_int_cst_sgn (i0) < 0)
1097               || (tree_int_cst_sgn (j1) == 0
1098                   && tree_int_cst_sgn (j0) < 0))
1099             {
1100               /* There is no solution.  
1101                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 
1102                  falls in here, but for the moment we don't look at the 
1103                  upper bound of the iteration domain.  */
1104               *overlaps_a = chrec_known;
1105               *overlaps_b = chrec_known;
1106             }
1107           
1108           else 
1109             {
1110               if (tree_int_cst_sgn (i1) > 0)
1111                 {
1112                   t = fold 
1113                     (build (CEIL_DIV_EXPR, integer_type_node, 
1114                             fold (build (MULT_EXPR, integer_type_node, i0, 
1115                                          integer_minus_one_node)), 
1116                             i1));
1117                   
1118                   if (tree_int_cst_sgn (j1) > 0)
1119                     {
1120                       t = fold 
1121                         (build (MAX_EXPR, integer_type_node, t,
1122                                 fold (build (CEIL_DIV_EXPR, integer_type_node,
1123                                              fold (build 
1124                                                    (MULT_EXPR,
1125                                                     integer_type_node, j0,
1126                                                     integer_minus_one_node)),
1127                                              j1))));
1128                       
1129                       x0 = fold 
1130                         (build (PLUS_EXPR, integer_type_node, i0, 
1131                                 fold (build 
1132                                       (MULT_EXPR, integer_type_node, i1, t))));
1133                       y0 = fold 
1134                         (build (PLUS_EXPR, integer_type_node, j0, 
1135                                 fold (build 
1136                                       (MULT_EXPR, integer_type_node, j1, t))));
1137                       
1138                       *overlaps_a = build_polynomial_chrec 
1139                         (CHREC_VARIABLE (chrec_b), x0, u21);
1140                       *overlaps_b = build_polynomial_chrec 
1141                         (CHREC_VARIABLE (chrec_a), y0, u22);
1142                     }
1143                   else
1144                     {
1145                       /* FIXME: For the moment, the upper bound of the
1146                          iteration domain for j is not checked. */
1147                       *overlaps_a = chrec_dont_know;
1148                       *overlaps_b = chrec_dont_know;
1149                     }
1150                 }
1151               
1152               else
1153                 {
1154                   /* FIXME: For the moment, the upper bound of the
1155                      iteration domain for i is not checked. */
1156                   *overlaps_a = chrec_dont_know;
1157                   *overlaps_b = chrec_dont_know;
1158                 }
1159             }
1160         }
1161     }
1162   
1163   else
1164     {
1165       /* For the moment, "don't know".  */
1166       *overlaps_a = chrec_dont_know;
1167       *overlaps_b = chrec_dont_know;
1168     }
1169   
1170   if (dump_file && (dump_flags & TDF_DETAILS))
1171     {
1172       fprintf (dump_file, "  (overlaps_a = ");
1173       print_generic_expr (dump_file, *overlaps_a, 0);
1174       fprintf (dump_file, ")\n  (overlaps_b = ");
1175       print_generic_expr (dump_file, *overlaps_b, 0);
1176       fprintf (dump_file, ")\n");
1177     }
1178   
1179   if (dump_file && (dump_flags & TDF_DETAILS))
1180     fprintf (dump_file, ")\n");
1181 }
1182
1183 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
1184    *OVERLAPS_B are initialized to the functions that describe the
1185    relation between the elements accessed twice by CHREC_A and
1186    CHREC_B.  For k >= 0, the following property is verified:
1187
1188    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1189
1190 static void
1191 analyze_siv_subscript (tree chrec_a, 
1192                        tree chrec_b,
1193                        tree *overlaps_a, 
1194                        tree *overlaps_b)
1195 {
1196   if (dump_file && (dump_flags & TDF_DETAILS))
1197     fprintf (dump_file, "(analyze_siv_subscript \n");
1198   
1199   if (evolution_function_is_constant_p (chrec_a)
1200       && evolution_function_is_affine_p (chrec_b))
1201     analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 
1202                                       overlaps_a, overlaps_b);
1203   
1204   else if (evolution_function_is_affine_p (chrec_a)
1205            && evolution_function_is_constant_p (chrec_b))
1206     analyze_siv_subscript_affine_cst (chrec_a, chrec_b, 
1207                                       overlaps_a, overlaps_b);
1208   
1209   else if (evolution_function_is_affine_p (chrec_a)
1210            && evolution_function_is_affine_p (chrec_b)
1211            && (CHREC_VARIABLE (chrec_a) == CHREC_VARIABLE (chrec_b)))
1212     analyze_subscript_affine_affine (chrec_a, chrec_b, 
1213                                      overlaps_a, overlaps_b);
1214   else
1215     {
1216       *overlaps_a = chrec_dont_know;
1217       *overlaps_b = chrec_dont_know;
1218     }
1219   
1220   if (dump_file && (dump_flags & TDF_DETAILS))
1221     fprintf (dump_file, ")\n");
1222 }
1223
1224 /* Return true when the evolution steps of an affine CHREC divide the
1225    constant CST.  */
1226
1227 static bool
1228 chrec_steps_divide_constant_p (tree chrec, 
1229                                tree cst)
1230 {
1231   switch (TREE_CODE (chrec))
1232     {
1233     case POLYNOMIAL_CHREC:
1234       return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
1235               && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
1236       
1237     default:
1238       /* On the initial condition, return true.  */
1239       return true;
1240     }
1241 }
1242
1243 /* Analyze a MIV (Multiple Index Variable) subscript.  *OVERLAPS_A and
1244    *OVERLAPS_B are initialized to the functions that describe the
1245    relation between the elements accessed twice by CHREC_A and
1246    CHREC_B.  For k >= 0, the following property is verified:
1247
1248    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1249
1250 static void
1251 analyze_miv_subscript (tree chrec_a, 
1252                        tree chrec_b, 
1253                        tree *overlaps_a, 
1254                        tree *overlaps_b)
1255 {
1256   /* FIXME:  This is a MIV subscript, not yet handled.
1257      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from 
1258      (A[i] vs. A[j]).  
1259      
1260      In the SIV test we had to solve a Diophantine equation with two
1261      variables.  In the MIV case we have to solve a Diophantine
1262      equation with 2*n variables (if the subscript uses n IVs).
1263   */
1264   tree difference;
1265   
1266   if (dump_file && (dump_flags & TDF_DETAILS))
1267     fprintf (dump_file, "(analyze_miv_subscript \n");
1268   
1269   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1270   
1271   if (chrec_zerop (difference))
1272     {
1273       /* Access functions are the same: all the elements are accessed
1274          in the same order.  */
1275       *overlaps_a = integer_zero_node;
1276       *overlaps_b = integer_zero_node;
1277     }
1278   
1279   else if (evolution_function_is_constant_p (difference)
1280            /* For the moment, the following is verified:
1281               evolution_function_is_affine_multivariate_p (chrec_a) */
1282            && !chrec_steps_divide_constant_p (chrec_a, difference))
1283     {
1284       /* testsuite/.../ssa-chrec-33.c
1285          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2 
1286         
1287          The difference is 1, and the evolution steps are equal to 2,
1288          consequently there are no overlapping elements.  */
1289       *overlaps_a = chrec_known;
1290       *overlaps_b = chrec_known;
1291     }
1292   
1293   else if (evolution_function_is_univariate_p (chrec_a)
1294            && evolution_function_is_univariate_p (chrec_b))
1295     {
1296       /* testsuite/.../ssa-chrec-35.c
1297          {0, +, 1}_2  vs.  {0, +, 1}_3
1298          the overlapping elements are respectively located at iterations:
1299          {0, +, 1}_3 and {0, +, 1}_2.
1300       */
1301       if (evolution_function_is_affine_p (chrec_a)
1302           && evolution_function_is_affine_p (chrec_b))
1303         analyze_subscript_affine_affine (chrec_a, chrec_b, 
1304                                          overlaps_a, overlaps_b);
1305       else
1306         {
1307           *overlaps_a = chrec_dont_know;
1308           *overlaps_b = chrec_dont_know;
1309         }
1310     }
1311   
1312   else
1313     {
1314       /* When the analysis is too difficult, answer "don't know".  */
1315       *overlaps_a = chrec_dont_know;
1316       *overlaps_b = chrec_dont_know;
1317     }
1318   
1319   if (dump_file && (dump_flags & TDF_DETAILS))
1320     fprintf (dump_file, ")\n");
1321 }
1322
1323 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1324    OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1325    two functions that describe the iterations that contain conflicting
1326    elements.
1327    
1328    Remark: For an integer k >= 0, the following equality is true:
1329    
1330    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1331 */
1332
1333 static void 
1334 analyze_overlapping_iterations (tree chrec_a, 
1335                                 tree chrec_b, 
1336                                 tree *overlap_iterations_a, 
1337                                 tree *overlap_iterations_b)
1338 {
1339   if (dump_file && (dump_flags & TDF_DETAILS))
1340     {
1341       fprintf (dump_file, "(analyze_overlapping_iterations \n");
1342       fprintf (dump_file, "  (chrec_a = ");
1343       print_generic_expr (dump_file, chrec_a, 0);
1344       fprintf (dump_file, ")\n  chrec_b = ");
1345       print_generic_expr (dump_file, chrec_b, 0);
1346       fprintf (dump_file, ")\n");
1347     }
1348   
1349   if (chrec_a == NULL_TREE
1350       || chrec_b == NULL_TREE
1351       || chrec_contains_undetermined (chrec_a)
1352       || chrec_contains_undetermined (chrec_b)
1353       || chrec_contains_symbols (chrec_a)
1354       || chrec_contains_symbols (chrec_b))
1355     {
1356       *overlap_iterations_a = chrec_dont_know;
1357       *overlap_iterations_b = chrec_dont_know;
1358     }
1359   
1360   else if (ziv_subscript_p (chrec_a, chrec_b))
1361     analyze_ziv_subscript (chrec_a, chrec_b, 
1362                            overlap_iterations_a, overlap_iterations_b);
1363   
1364   else if (siv_subscript_p (chrec_a, chrec_b))
1365     analyze_siv_subscript (chrec_a, chrec_b, 
1366                            overlap_iterations_a, overlap_iterations_b);
1367   
1368   else
1369     analyze_miv_subscript (chrec_a, chrec_b, 
1370                            overlap_iterations_a, overlap_iterations_b);
1371   
1372   if (dump_file && (dump_flags & TDF_DETAILS))
1373     {
1374       fprintf (dump_file, "  (overlap_iterations_a = ");
1375       print_generic_expr (dump_file, *overlap_iterations_a, 0);
1376       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
1377       print_generic_expr (dump_file, *overlap_iterations_b, 0);
1378       fprintf (dump_file, ")\n");
1379     }
1380 }
1381
1382 \f
1383
1384 /* This section contains the affine functions dependences detector.  */
1385
1386 /* Computes the conflicting iterations, and initialize DDR.  */
1387
1388 static void
1389 subscript_dependence_tester (struct data_dependence_relation *ddr)
1390 {
1391   unsigned int i;
1392   struct data_reference *dra = DDR_A (ddr);
1393   struct data_reference *drb = DDR_B (ddr);
1394   
1395   if (dump_file && (dump_flags & TDF_DETAILS))
1396     fprintf (dump_file, "(subscript_dependence_tester \n");
1397   
1398   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1399     {
1400       tree overlaps_a, overlaps_b;
1401       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1402       
1403       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 
1404                                       DR_ACCESS_FN (drb, i),
1405                                       &overlaps_a, &overlaps_b);
1406       
1407       if (chrec_contains_undetermined (overlaps_a)
1408           || chrec_contains_undetermined (overlaps_b))
1409         {
1410           finalize_ddr_dependent (ddr, chrec_dont_know);
1411           break;
1412         }
1413       
1414       else if (overlaps_a == chrec_known
1415                || overlaps_b == chrec_known)
1416         {
1417           finalize_ddr_dependent (ddr, chrec_known);
1418           break;
1419         }
1420       
1421       else
1422         {
1423           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
1424           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
1425         }
1426     }
1427   
1428   if (dump_file && (dump_flags & TDF_DETAILS))
1429     fprintf (dump_file, ")\n");
1430 }
1431
1432 /* Compute the classic per loop distance vector.
1433
1434    DDR is the data dependence relation to build a vector from.
1435    NB_LOOPS is the total number of loops we are considering.
1436    FIRST_LOOP is the loop->num of the first loop.  */
1437
1438 static void
1439 build_classic_dist_vector (struct data_dependence_relation *ddr, 
1440                            int nb_loops, unsigned int first_loop)
1441 {
1442   unsigned i;
1443   lambda_vector dist_v, init_v;
1444   
1445   dist_v = lambda_vector_new (nb_loops);
1446   init_v = lambda_vector_new (nb_loops);
1447   lambda_vector_clear (dist_v, nb_loops);
1448   lambda_vector_clear (init_v, nb_loops);
1449   
1450   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1451     return;
1452   
1453   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1454     {
1455       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1456
1457       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1458         return;
1459
1460       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
1461         {
1462           int dist;
1463           int loop_nb;
1464           loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
1465           loop_nb -= first_loop;
1466           /* If the loop number is still greater than the number of
1467              loops we've been asked to analyze, or negative,
1468              something is borked.  */
1469           if (loop_nb < 0 || loop_nb >= nb_loops)
1470             abort ();
1471           dist = int_cst_value (SUB_DISTANCE (subscript));
1472
1473           /* This is the subscript coupling test.  
1474              | loop i = 0, N, 1
1475              |   T[i+1][i] = ...
1476              |   ... = T[i][i]
1477              | endloop
1478              There is no dependence.  */
1479           if (init_v[loop_nb] != 0
1480               && dist_v[loop_nb] != dist)
1481             {
1482               finalize_ddr_dependent (ddr, chrec_known);
1483               return;
1484             }
1485
1486           dist_v[loop_nb] = dist;
1487           init_v[loop_nb] = 1;
1488         }
1489     }
1490   
1491   /* There is a distance of 1 on all the outer loops: 
1492      
1493      Example: there is a dependence of distance 1 on loop_1 for the array A.
1494      | loop_1
1495      |   A[5] = ...
1496      | endloop
1497   */
1498   {
1499     struct loop *lca, *loop_a, *loop_b;
1500     struct data_reference *a = DDR_A (ddr);
1501     struct data_reference *b = DDR_B (ddr);
1502     int lca_nb;
1503     loop_a = loop_containing_stmt (DR_STMT (a));
1504     loop_b = loop_containing_stmt (DR_STMT (b));
1505     
1506     /* Get the common ancestor loop.  */
1507     lca = find_common_loop (loop_a, loop_b); 
1508     
1509     lca_nb = lca->num;
1510     lca_nb -= first_loop;
1511     if (lca_nb < 0 || lca_nb >= nb_loops)
1512       abort ();
1513     /* For each outer loop where init_v is not set, the accesses are
1514        in dependence of distance 1 in the loop.  */
1515     if (lca != loop_a
1516         && lca != loop_b
1517         && init_v[lca_nb] == 0)
1518       dist_v[lca_nb] = 1;
1519     
1520     lca = lca->outer;
1521     
1522     if (lca)
1523       {
1524         lca_nb = lca->num - first_loop;
1525         while (lca->depth != 0)
1526           {
1527             if (lca_nb < 0 || lca_nb >= nb_loops)
1528               abort ();
1529             if (init_v[lca_nb] == 0)
1530               dist_v[lca_nb] = 1;
1531             lca = lca->outer;
1532             lca_nb = lca->num - first_loop;
1533           
1534           }
1535       }
1536   }
1537   
1538   DDR_DIST_VECT (ddr) = dist_v;
1539 }
1540
1541 /* Compute the classic per loop direction vector.  
1542
1543    DDR is the data dependence relation to build a vector from.
1544    NB_LOOPS is the total number of loops we are considering.
1545    FIRST_LOOP is the loop->num of the first loop.  */
1546
1547 static void
1548 build_classic_dir_vector (struct data_dependence_relation *ddr, 
1549                           int nb_loops, unsigned int first_loop)
1550 {
1551   unsigned i;
1552   lambda_vector dir_v, init_v;
1553   
1554   dir_v = lambda_vector_new (nb_loops);
1555   init_v = lambda_vector_new (nb_loops);
1556   lambda_vector_clear (dir_v, nb_loops);
1557   lambda_vector_clear (init_v, nb_loops);
1558   
1559   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1560     return;
1561   
1562   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1563     {
1564       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1565
1566       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
1567           && TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
1568         {
1569           int loop_nb;
1570           
1571           enum data_dependence_direction dir = dir_star;
1572           loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
1573           loop_nb -= first_loop;
1574
1575           /* If the loop number is still greater than the number of
1576              loops we've been asked to analyze, or negative,
1577              something is borked.  */
1578           if (loop_nb < 0 || loop_nb >= nb_loops)
1579             abort ();     
1580           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1581             {
1582               
1583             }
1584           else
1585             {
1586               int dist = int_cst_value (SUB_DISTANCE (subscript));
1587               
1588               if (dist == 0)
1589                 dir = dir_equal;
1590               else if (dist > 0)
1591                 dir = dir_positive;
1592               else if (dist < 0)
1593                 dir = dir_negative;
1594             }
1595           
1596           /* This is the subscript coupling test.  
1597              | loop i = 0, N, 1
1598              |   T[i+1][i] = ...
1599              |   ... = T[i][i]
1600              | endloop
1601              There is no dependence.  */
1602           if (init_v[loop_nb] != 0
1603               && dir != dir_star
1604               && (enum data_dependence_direction) dir_v[loop_nb] != dir
1605               && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
1606             {
1607               finalize_ddr_dependent (ddr, chrec_known);
1608               return;
1609             }
1610           
1611           dir_v[loop_nb] = dir;
1612           init_v[loop_nb] = 1;
1613         }
1614     }
1615   
1616   /* There is a distance of 1 on all the outer loops: 
1617      
1618      Example: there is a dependence of distance 1 on loop_1 for the array A.
1619      | loop_1
1620      |   A[5] = ...
1621      | endloop
1622   */
1623   {
1624     struct loop *lca, *loop_a, *loop_b;
1625     struct data_reference *a = DDR_A (ddr);
1626     struct data_reference *b = DDR_B (ddr);
1627     int lca_nb;
1628     loop_a = loop_containing_stmt (DR_STMT (a));
1629     loop_b = loop_containing_stmt (DR_STMT (b));
1630     
1631     /* Get the common ancestor loop.  */
1632     lca = find_common_loop (loop_a, loop_b); 
1633     lca_nb = lca->num - first_loop;
1634
1635     if (lca_nb < 0 || lca_nb >= nb_loops)
1636       abort ();
1637     /* For each outer loop where init_v is not set, the accesses are
1638        in dependence of distance 1 in the loop.  */
1639     if (lca != loop_a
1640         && lca != loop_b
1641         && init_v[lca_nb] == 0)
1642       dir_v[lca_nb] = dir_positive;
1643     
1644     lca = lca->outer;
1645     if (lca)
1646       {
1647         lca_nb = lca->num - first_loop;
1648         while (lca->depth != 0)
1649           {
1650             if (lca_nb < 0 || lca_nb >= nb_loops)
1651               abort ();
1652             if (init_v[lca_nb] == 0)
1653               dir_v[lca_nb] = dir_positive;
1654             lca = lca->outer;
1655             lca_nb = lca->num - first_loop;
1656            
1657           }
1658       }
1659   }
1660   
1661   DDR_DIR_VECT (ddr) = dir_v;
1662 }
1663
1664 /* Returns true when all the access functions of A are affine or
1665    constant.  */
1666
1667 static bool 
1668 access_functions_are_affine_or_constant_p (struct data_reference *a)
1669 {
1670   unsigned int i;
1671   varray_type fns = DR_ACCESS_FNS (a);
1672   
1673   for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
1674     if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
1675         && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
1676       return false;
1677   
1678   return true;
1679 }
1680
1681 /* This computes the affine dependence relation between A and B.
1682    CHREC_KNOWN is used for representing the independence between two
1683    accesses, while CHREC_DONT_KNOW is used for representing the unknown
1684    relation.
1685    
1686    Note that it is possible to stop the computation of the dependence
1687    relation the first time we detect a CHREC_KNOWN element for a given
1688    subscript.  */
1689
1690 void
1691 compute_affine_dependence (struct data_dependence_relation *ddr)
1692 {
1693   struct data_reference *dra = DDR_A (ddr);
1694   struct data_reference *drb = DDR_B (ddr);
1695   
1696   if (dump_file && (dump_flags & TDF_DETAILS))
1697     {
1698       fprintf (dump_file, "(compute_affine_dependence\n");
1699       fprintf (dump_file, "  (stmt_a = \n");
1700       print_generic_expr (dump_file, DR_STMT (dra), 0);
1701       fprintf (dump_file, ")\n  (stmt_b = \n");
1702       print_generic_expr (dump_file, DR_STMT (drb), 0);
1703       fprintf (dump_file, ")\n");
1704     }
1705   
1706   /* Analyze only when the dependence relation is not yet known.  */
1707   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1708     {
1709       if (access_functions_are_affine_or_constant_p (dra)
1710           && access_functions_are_affine_or_constant_p (drb))
1711         subscript_dependence_tester (ddr);
1712       
1713       /* As a last case, if the dependence cannot be determined, or if
1714          the dependence is considered too difficult to determine, answer
1715          "don't know".  */
1716       else
1717         finalize_ddr_dependent (ddr, chrec_dont_know);
1718     }
1719   
1720   if (dump_file && (dump_flags & TDF_DETAILS))
1721     fprintf (dump_file, ")\n");
1722 }
1723
1724 /* Compute a subset of the data dependence relation graph.  Don't
1725    compute read-read relations, and avoid the computation of the
1726    opposite relation, ie. when AB has been computed, don't compute BA.
1727    DATAREFS contains a list of data references, and the result is set
1728    in DEPENDENCE_RELATIONS.  */
1729
1730 static void 
1731 compute_all_dependences (varray_type datarefs, 
1732                          varray_type *dependence_relations)
1733 {
1734   unsigned int i, j, N;
1735
1736   N = VARRAY_ACTIVE_SIZE (datarefs);
1737
1738   for (i = 0; i < N; i++)
1739     for (j = i; j < N; j++)
1740       {
1741         struct data_reference *a, *b;
1742         struct data_dependence_relation *ddr;
1743
1744         a = VARRAY_GENERIC_PTR (datarefs, i);
1745         b = VARRAY_GENERIC_PTR (datarefs, j);
1746
1747         ddr = initialize_data_dependence_relation (a, b);
1748
1749         VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
1750         compute_affine_dependence (ddr);
1751         compute_distance_vector (ddr);
1752       }
1753 }
1754
1755 /* Search the data references in LOOP, and record the information into
1756    DATAREFS.  Returns chrec_dont_know when failing to analyze a
1757    difficult case, returns NULL_TREE otherwise.
1758    
1759    FIXME: This is a "dumb" walker over all the trees in the loop body.
1760    Find another technique that avoids this costly walk.  This is
1761    acceptable for the moment, since this function is used only for
1762    debugging purposes.  */
1763
1764 static tree 
1765 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
1766 {
1767   basic_block bb;
1768   block_stmt_iterator bsi;
1769   
1770   FOR_EACH_BB (bb)
1771     {
1772       if (!flow_bb_inside_loop_p (loop, bb))
1773         continue;
1774       
1775       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1776         {
1777           tree stmt = bsi_stmt (bsi);
1778           stmt_ann_t ann = stmt_ann (stmt);
1779
1780           if (TREE_CODE (stmt) != MODIFY_EXPR)
1781             continue;
1782
1783           if (!VUSE_OPS (ann)
1784               && !V_MUST_DEF_OPS (ann)
1785               && !V_MAY_DEF_OPS (ann))
1786             continue;
1787
1788           /* In the GIMPLE representation, a modify expression
1789              contains a single load or store to memory.  */
1790           if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
1791             VARRAY_PUSH_GENERIC_PTR 
1792                     (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0), 
1793                                                false));
1794
1795           else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
1796             VARRAY_PUSH_GENERIC_PTR 
1797                     (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), 
1798                                                true));
1799
1800           else
1801             return chrec_dont_know;
1802         }
1803     }
1804
1805   return NULL_TREE;
1806 }
1807
1808 \f
1809
1810 /* This section contains all the entry points.  */
1811
1812 /* Given a loop nest LOOP, the following vectors are returned:
1813    *DATAREFS is initialized to all the array elements contained in this loop, 
1814    *DEPENDENCE_RELATIONS contains the relations between the data references.  */
1815
1816 void
1817 compute_data_dependences_for_loop (unsigned nb_loops, 
1818                                    struct loop *loop,
1819                                    varray_type *datarefs,
1820                                    varray_type *dependence_relations)
1821 {
1822   unsigned int i;
1823
1824   /* If one of the data references is not computable, give up without
1825      spending time to compute other dependences.  */
1826   if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
1827     {
1828       struct data_dependence_relation *ddr;
1829
1830       /* Insert a single relation into dependence_relations:
1831          chrec_dont_know.  */
1832       ddr = initialize_data_dependence_relation (NULL, NULL);
1833       VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
1834       build_classic_dist_vector (ddr, nb_loops, loop->num);
1835       build_classic_dir_vector (ddr, nb_loops, loop->num);
1836       return;
1837     }
1838
1839   compute_all_dependences (*datarefs, dependence_relations);
1840
1841   for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
1842     {
1843       struct data_dependence_relation *ddr;
1844       ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
1845       build_classic_dist_vector (ddr, nb_loops, loop->num);
1846       build_classic_dir_vector (ddr, nb_loops, loop->num);    
1847     }
1848 }
1849
1850 /* Entry point (for testing only).  Analyze all the data references
1851    and the dependence relations.
1852
1853    The data references are computed first.  
1854    
1855    A relation on these nodes is represented by a complete graph.  Some
1856    of the relations could be of no interest, thus the relations can be
1857    computed on demand.
1858    
1859    In the following function we compute all the relations.  This is
1860    just a first implementation that is here for:
1861    - for showing how to ask for the dependence relations, 
1862    - for the debugging the whole dependence graph,
1863    - for the dejagnu testcases and maintenance.
1864    
1865    It is possible to ask only for a part of the graph, avoiding to
1866    compute the whole dependence graph.  The computed dependences are
1867    stored in a knowledge base (KB) such that later queries don't
1868    recompute the same information.  The implementation of this KB is
1869    transparent to the optimizer, and thus the KB can be changed with a
1870    more efficient implementation, or the KB could be disabled.  */
1871
1872 void 
1873 analyze_all_data_dependences (struct loops *loops)
1874 {
1875   unsigned int i;
1876   varray_type datarefs;
1877   varray_type dependence_relations;
1878   int nb_data_refs = 10;
1879
1880   VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
1881   VARRAY_GENERIC_PTR_INIT (dependence_relations, 
1882                            nb_data_refs * nb_data_refs,
1883                            "dependence_relations");
1884
1885   /* Compute DDs on the whole function.  */
1886   compute_data_dependences_for_loop (loops->num, loops->parray[0], 
1887                                      &datarefs, &dependence_relations);
1888
1889   if (dump_file)
1890     {
1891       dump_data_dependence_relations (dump_file, dependence_relations);
1892       fprintf (dump_file, "\n\n");
1893     }
1894
1895   /* Don't dump distances in order to avoid to update the
1896      testsuite.  */
1897   if (dump_file && (dump_flags & TDF_DETAILS))
1898     {
1899       for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
1900         {
1901           struct data_dependence_relation *ddr = 
1902             (struct data_dependence_relation *) 
1903             VARRAY_GENERIC_PTR (dependence_relations, i);
1904           if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1905             {
1906               fprintf (dump_file, "DISTANCE_V (");
1907               print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), loops->num);
1908               fprintf (dump_file, ")\n");
1909               fprintf (dump_file, "DIRECTION_V (");
1910               print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), loops->num);
1911               fprintf (dump_file, ")\n");
1912             }
1913         }
1914       fprintf (dump_file, "\n\n");
1915     }
1916
1917   if (dump_file && (dump_flags & TDF_STATS))
1918     {
1919       unsigned nb_top_relations = 0;
1920       unsigned nb_bot_relations = 0;
1921       unsigned nb_basename_differ = 0;
1922       unsigned nb_chrec_relations = 0;
1923
1924       for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
1925         {
1926           struct data_dependence_relation *ddr;
1927           ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
1928           
1929           if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
1930             nb_top_relations++;
1931           
1932           else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1933             {
1934               struct data_reference *a = DDR_A (ddr);
1935               struct data_reference *b = DDR_B (ddr);
1936               bool differ_p;    
1937               
1938               if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
1939                   || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
1940                 nb_basename_differ++;
1941               else
1942                 nb_bot_relations++;
1943             }
1944           
1945           else 
1946             nb_chrec_relations++;
1947         }
1948       
1949       gather_stats_on_scev_database ();
1950     }
1951
1952   free_dependence_relations (dependence_relations);
1953   free_data_refs (datarefs);
1954 }
1955
1956 /* Free the memory used by a data dependence relation DDR.  */
1957
1958 void
1959 free_dependence_relation (struct data_dependence_relation *ddr)
1960 {
1961   if (ddr == NULL)
1962     return;
1963
1964   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
1965     varray_clear (DDR_SUBSCRIPTS (ddr));
1966   free (ddr);
1967 }
1968
1969 /* Free the memory used by the data dependence relations from
1970    DEPENDENCE_RELATIONS.  */
1971
1972 void 
1973 free_dependence_relations (varray_type dependence_relations)
1974 {
1975   unsigned int i;
1976   if (dependence_relations == NULL)
1977     return;
1978
1979   for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
1980     free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
1981   varray_clear (dependence_relations);
1982 }
1983
1984 /* Free the memory used by the data references from DATAREFS.  */
1985
1986 void
1987 free_data_refs (varray_type datarefs)
1988 {
1989   unsigned int i;
1990   
1991   if (datarefs == NULL)
1992     return;
1993
1994   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1995     {
1996       struct data_reference *dr = (struct data_reference *) 
1997         VARRAY_GENERIC_PTR (datarefs, i);
1998       if (dr && DR_ACCESS_FNS (dr))
1999         varray_clear (DR_ACCESS_FNS (dr));
2000     }
2001   varray_clear (datarefs);
2002 }