OSDN Git Service

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