OSDN Git Service

05361a2fc1628f451dfbbf381bbafd24b354aac7
[pf3gnuchains/gcc-fork.git] / gcc / tree-data-ref.c
1 /* Data references and dependences detectors.
2    Copyright (C) 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, 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 dependence 
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 "ggc.h"
82 #include "tree.h"
83
84 /* These RTL headers are needed for basic-block.h.  */
85 #include "rtl.h"
86 #include "basic-block.h"
87 #include "diagnostic.h"
88 #include "tree-flow.h"
89 #include "tree-dump.h"
90 #include "timevar.h"
91 #include "cfgloop.h"
92 #include "tree-chrec.h"
93 #include "tree-data-ref.h"
94 #include "tree-scalar-evolution.h"
95 #include "tree-pass.h"
96
97 static tree object_analysis (tree, tree, bool, struct data_reference **, 
98                              tree *, tree *, tree *, tree *, tree *,
99                              struct ptr_info_def **, subvar_t *);
100 static struct data_reference * init_data_ref (tree, tree, tree, tree, bool, 
101                                               tree, tree, tree, tree, tree, 
102                                               struct ptr_info_def *,
103                                               enum  data_ref_type);
104
105 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
106    Return FALSE if there is no type memory tag for PTR.
107 */
108 static bool
109 ptr_decl_may_alias_p (tree ptr, tree decl, 
110                       struct data_reference *ptr_dr, 
111                       bool *aliased)
112 {
113   tree tag;
114    
115   gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
116
117   tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
118   if (!tag)
119     tag = DR_MEMTAG (ptr_dr);
120   if (!tag)
121     return false;
122   
123   *aliased = is_aliased_with (tag, decl);      
124   return true;
125 }
126
127
128 /* Determine if two pointers may alias, the result is put in ALIASED.
129    Return FALSE if there is no type memory tag for one of the pointers.
130 */
131 static bool
132 ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b, 
133                      struct data_reference *dra, 
134                      struct data_reference *drb, 
135                      bool *aliased)
136 {  
137   tree tag_a, tag_b;
138
139   tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->type_mem_tag;
140   if (!tag_a)
141     tag_a = DR_MEMTAG (dra);
142   if (!tag_a)
143     return false;
144   tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->type_mem_tag;
145   if (!tag_b)
146     tag_b = DR_MEMTAG (drb);
147   if (!tag_b)
148     return false;
149   *aliased = (tag_a == tag_b);
150   return true;
151 }
152
153
154 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
155    Return FALSE if there is no type memory tag for one of the symbols.
156 */
157 static bool
158 may_alias_p (tree base_a, tree base_b,
159              struct data_reference *dra,
160              struct data_reference *drb,
161              bool *aliased)
162 {
163   if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
164     {
165       if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
166         {
167          *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
168          return true;
169         }
170       if (TREE_CODE (base_a) == ADDR_EXPR)
171         return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb, 
172                                      aliased);
173       else
174         return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra, 
175                                      aliased);
176     }
177
178   return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
179 }
180
181
182 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
183    are not aliased. Return TRUE if they differ.  */
184 static bool
185 record_ptr_differ_p (struct data_reference *dra,
186                      struct data_reference *drb)
187 {
188   bool aliased;
189   tree base_a = DR_BASE_OBJECT (dra);
190   tree base_b = DR_BASE_OBJECT (drb);
191
192   if (TREE_CODE (base_b) != COMPONENT_REF)
193     return false;
194
195   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
196      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.  
197      Probably will be unnecessary with struct alias analysis.  */
198   while (TREE_CODE (base_b) == COMPONENT_REF)
199      base_b = TREE_OPERAND (base_b, 0);
200   /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
201      ((*q)[i]).  */
202   if (TREE_CODE (base_a) == INDIRECT_REF
203       && ((TREE_CODE (base_b) == VAR_DECL
204            && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra, 
205                                      &aliased)
206                && !aliased))
207           || (TREE_CODE (base_b) == INDIRECT_REF
208               && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0), 
209                                        TREE_OPERAND (base_b, 0), dra, drb, 
210                                        &aliased)
211                   && !aliased))))
212     return true;
213   else
214     return false;
215 }
216
217     
218 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
219    are not aliased. Return TRUE if they differ.  */
220 static bool
221 record_array_differ_p (struct data_reference *dra,
222                        struct data_reference *drb)
223 {  
224   bool aliased;
225   tree base_a = DR_BASE_OBJECT (dra);
226   tree base_b = DR_BASE_OBJECT (drb);
227
228   if (TREE_CODE (base_b) != COMPONENT_REF)
229     return false;
230
231   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
232      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.  
233      Probably will be unnecessary with struct alias analysis.  */
234   while (TREE_CODE (base_b) == COMPONENT_REF)
235      base_b = TREE_OPERAND (base_b, 0);
236
237   /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 
238      (a[i]). In case of p->c[i] use alias analysis to verify that p is not
239      pointing to a.  */
240   if (TREE_CODE (base_a) == VAR_DECL
241       && (TREE_CODE (base_b) == VAR_DECL
242           || (TREE_CODE (base_b) == INDIRECT_REF
243               && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, 
244                                         &aliased)
245                   && !aliased))))
246     return true;
247   else
248     return false;
249 }
250
251
252 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
253    are not aliased. Return TRUE if they differ.  */
254 static bool
255 array_ptr_differ_p (tree base_a, tree base_b,        
256                     struct data_reference *drb)
257 {  
258   bool aliased;
259
260   /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
261      help of alias analysis that p is not pointing to a.  */
262   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF 
263       && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
264           && !aliased))
265     return true;
266   else
267     return false;
268 }
269
270
271 /* This is the simplest data dependence test: determines whether the
272    data references A and B access the same array/region.  Returns
273    false when the property is not computable at compile time.
274    Otherwise return true, and DIFFER_P will record the result. This
275    utility will not be necessary when alias_sets_conflict_p will be
276    less conservative.  */
277
278 static bool
279 base_object_differ_p (struct data_reference *a,
280                       struct data_reference *b,
281                       bool *differ_p)
282 {
283   tree base_a = DR_BASE_OBJECT (a);
284   tree base_b = DR_BASE_OBJECT (b);
285   bool aliased;
286
287   if (!base_a || !base_b)
288     return false;
289
290   /* Determine if same base.  Example: for the array accesses
291      a[i], b[i] or pointer accesses *a, *b, bases are a, b.  */
292   if (base_a == base_b)
293     {
294       *differ_p = false;
295       return true;
296     }
297
298   /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
299      and (*q)  */
300   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
301       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
302     {
303       *differ_p = false;
304       return true;
305     }
306
307   /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b.  */ 
308   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
309       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
310       && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
311     {
312       *differ_p = false;
313       return true;
314     }
315
316
317   /* Determine if different bases.  */
318
319   /* At this point we know that base_a != base_b.  However, pointer
320      accesses of the form x=(*p) and y=(*q), whose bases are p and q,
321      may still be pointing to the same base. In SSAed GIMPLE p and q will
322      be SSA_NAMES in this case.  Therefore, here we check if they are
323      really two different declarations.  */
324   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
325     {
326       *differ_p = true;
327       return true;
328     }
329
330   /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
331      help of alias analysis that p is not pointing to a.  */
332   if (array_ptr_differ_p (base_a, base_b, b) 
333       || array_ptr_differ_p (base_b, base_a, a))
334     {
335       *differ_p = true;
336       return true;
337     }
338
339   /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
340      help of alias analysis they don't point to the same bases.  */
341   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF 
342       && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b, 
343                        &aliased)
344           && !aliased))
345     {
346       *differ_p = true;
347       return true;
348     }
349
350   /* Compare two record/union bases s.a and t.b: s != t or (a != b and
351      s and t are not unions).  */
352   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
353       && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
354            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
355            && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
356           || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE 
357               && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
358               && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
359     {
360       *differ_p = true;
361       return true;
362     }
363
364   /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
365      ((*q)[i]).  */
366   if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
367     {
368       *differ_p = true;
369       return true;
370     }
371
372   /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 
373      (a[i]). In case of p->c[i] use alias analysis to verify that p is not
374      pointing to a.  */
375   if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
376     {
377       *differ_p = true;
378       return true;
379     }
380
381   return false;
382 }
383
384 /* Function base_addr_differ_p.
385
386    This is the simplest data dependence test: determines whether the
387    data references A and B access the same array/region.  Returns
388    false when the property is not computable at compile time.
389    Otherwise return true, and DIFFER_P will record the result. This
390    utility will not be necessary when alias_sets_conflict_p will be
391    less conservative.  */
392
393
394 static bool
395 base_addr_differ_p (struct data_reference *dra,
396                     struct data_reference *drb,
397                     bool *differ_p)
398 {
399   tree addr_a = DR_BASE_ADDRESS (dra);
400   tree addr_b = DR_BASE_ADDRESS (drb);
401   tree type_a, type_b;
402   bool aliased;
403
404   if (!addr_a || !addr_b)
405     return false;
406
407   type_a = TREE_TYPE (addr_a);
408   type_b = TREE_TYPE (addr_b);
409
410   gcc_assert (POINTER_TYPE_P (type_a) &&  POINTER_TYPE_P (type_b));
411   
412   /* Compare base objects first if possible. If DR_BASE_OBJECT is NULL, it means
413      that the data-ref is of INDIRECT_REF, and alias analysis will be applied to 
414      reveal the dependence.  */
415   if (DR_BASE_OBJECT (dra) && DR_BASE_OBJECT (drb))
416     return base_object_differ_p (dra, drb, differ_p);
417
418   /* If base addresses are the same, we check the offsets, since the access of 
419      the data-ref is described by {base addr + offset} and its access function,
420      i.e., in order to decide whether the bases of data-refs are the same we 
421      compare both base addresses and offsets.  */
422   if (addr_a == addr_b 
423       || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
424          && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0)))
425     {
426       /* Compare offsets.  */
427       tree offset_a = DR_OFFSET (dra); 
428       tree offset_b = DR_OFFSET (drb);
429       
430       gcc_assert (!DR_BASE_OBJECT (dra) && !DR_BASE_OBJECT (drb));
431
432       STRIP_NOPS (offset_a);
433       STRIP_NOPS (offset_b);
434
435       /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
436          PLUS_EXPR.  */
437       if ((offset_a == offset_b)
438           || (TREE_CODE (offset_a) == MULT_EXPR 
439               && TREE_CODE (offset_b) == MULT_EXPR
440               && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
441               && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
442         {
443           *differ_p = false;
444           return true;
445         }
446     }
447
448   /* Apply alias analysis.  */
449   if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
450     {
451       *differ_p = true;
452       return true;
453     }
454   
455   /* An instruction writing through a restricted pointer is "independent" of any 
456      instruction reading or writing through a different pointer, in the same 
457      block/scope.  */
458   else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
459       || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
460     {
461       *differ_p = true;
462       return true;
463     }
464   return false;
465 }
466
467
468 /* Returns true iff A divides B.  */
469
470 static inline bool 
471 tree_fold_divides_p (tree type, 
472                      tree a, 
473                      tree b)
474 {
475   /* Determines whether (A == gcd (A, B)).  */
476   return integer_zerop 
477     (fold_build2 (MINUS_EXPR, type, a, tree_fold_gcd (a, b)));
478 }
479
480 /* Compute the greatest common denominator of two numbers using
481    Euclid's algorithm.  */
482
483 static int 
484 gcd (int a, int b)
485 {
486   
487   int x, y, z;
488   
489   x = abs (a);
490   y = abs (b);
491
492   while (x>0)
493     {
494       z = y % x;
495       y = x;
496       x = z;
497     }
498
499   return (y);
500 }
501
502 /* Returns true iff A divides B.  */
503
504 static inline bool 
505 int_divides_p (int a, int b)
506 {
507   return ((b % a) == 0);
508 }
509
510 \f
511
512 /* Dump into FILE all the data references from DATAREFS.  */ 
513
514 void 
515 dump_data_references (FILE *file, 
516                       varray_type datarefs)
517 {
518   unsigned int i;
519   
520   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
521     dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
522 }
523
524 /* Dump into FILE all the dependence relations from DDR.  */ 
525
526 void 
527 dump_data_dependence_relations (FILE *file, 
528                                 varray_type ddr)
529 {
530   unsigned int i;
531   
532   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
533     dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
534 }
535
536 /* Dump function for a DATA_REFERENCE structure.  */
537
538 void 
539 dump_data_reference (FILE *outf, 
540                      struct data_reference *dr)
541 {
542   unsigned int i;
543   
544   fprintf (outf, "(Data Ref: \n  stmt: ");
545   print_generic_stmt (outf, DR_STMT (dr), 0);
546   fprintf (outf, "  ref: ");
547   print_generic_stmt (outf, DR_REF (dr), 0);
548   fprintf (outf, "  base_name: ");
549   print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
550   
551   for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
552     {
553       fprintf (outf, "  Access function %d: ", i);
554       print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
555     }
556   fprintf (outf, ")\n");
557 }
558
559 /* Dump function for a SUBSCRIPT structure.  */
560
561 void 
562 dump_subscript (FILE *outf, struct subscript *subscript)
563 {
564   tree chrec = SUB_CONFLICTS_IN_A (subscript);
565
566   fprintf (outf, "\n (subscript \n");
567   fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
568   print_generic_stmt (outf, chrec, 0);
569   if (chrec == chrec_known)
570     fprintf (outf, "    (no dependence)\n");
571   else if (chrec_contains_undetermined (chrec))
572     fprintf (outf, "    (don't know)\n");
573   else
574     {
575       tree last_iteration = SUB_LAST_CONFLICT (subscript);
576       fprintf (outf, "  last_conflict: ");
577       print_generic_stmt (outf, last_iteration, 0);
578     }
579           
580   chrec = SUB_CONFLICTS_IN_B (subscript);
581   fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
582   print_generic_stmt (outf, chrec, 0);
583   if (chrec == chrec_known)
584     fprintf (outf, "    (no dependence)\n");
585   else if (chrec_contains_undetermined (chrec))
586     fprintf (outf, "    (don't know)\n");
587   else
588     {
589       tree last_iteration = SUB_LAST_CONFLICT (subscript);
590       fprintf (outf, "  last_conflict: ");
591       print_generic_stmt (outf, last_iteration, 0);
592     }
593
594   fprintf (outf, "  (Subscript distance: ");
595   print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
596   fprintf (outf, "  )\n");
597   fprintf (outf, " )\n");
598 }
599
600 /* Dump function for a DATA_DEPENDENCE_RELATION structure.  */
601
602 void 
603 dump_data_dependence_relation (FILE *outf, 
604                                struct data_dependence_relation *ddr)
605 {
606   struct data_reference *dra, *drb;
607
608   dra = DDR_A (ddr);
609   drb = DDR_B (ddr);
610   fprintf (outf, "(Data Dep: \n");
611   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
612     fprintf (outf, "    (don't know)\n");
613   
614   else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
615     fprintf (outf, "    (no dependence)\n");
616   
617   else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
618     {
619       unsigned int i;
620       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
621         {
622           fprintf (outf, "  access_fn_A: ");
623           print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
624           fprintf (outf, "  access_fn_B: ");
625           print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
626           dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
627         }
628       if (DDR_DIST_VECT (ddr))
629         {
630           fprintf (outf, "  distance_vect: ");
631           print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
632         }
633       if (DDR_DIR_VECT (ddr))
634         {
635           fprintf (outf, "  direction_vect: ");
636           print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
637         }
638     }
639
640   fprintf (outf, ")\n");
641 }
642
643
644
645 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure.  */
646
647 void
648 dump_data_dependence_direction (FILE *file, 
649                                 enum data_dependence_direction dir)
650 {
651   switch (dir)
652     {
653     case dir_positive: 
654       fprintf (file, "+");
655       break;
656       
657     case dir_negative:
658       fprintf (file, "-");
659       break;
660       
661     case dir_equal:
662       fprintf (file, "=");
663       break;
664       
665     case dir_positive_or_negative:
666       fprintf (file, "+-");
667       break;
668       
669     case dir_positive_or_equal: 
670       fprintf (file, "+=");
671       break;
672       
673     case dir_negative_or_equal: 
674       fprintf (file, "-=");
675       break;
676       
677     case dir_star: 
678       fprintf (file, "*"); 
679       break;
680       
681     default: 
682       break;
683     }
684 }
685
686 /* Dumps the distance and direction vectors in FILE.  DDRS contains
687    the dependence relations, and VECT_SIZE is the size of the
688    dependence vectors, or in other words the number of loops in the
689    considered nest.  */
690
691 void 
692 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
693 {
694   unsigned int i;
695
696   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
697     {
698       struct data_dependence_relation *ddr = 
699         (struct data_dependence_relation *) 
700         VARRAY_GENERIC_PTR (ddrs, i);
701       if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
702           && DDR_AFFINE_P (ddr))
703         {
704           fprintf (file, "DISTANCE_V (");
705           print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
706           fprintf (file, ")\n");
707           fprintf (file, "DIRECTION_V (");
708           print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
709           fprintf (file, ")\n");
710         }
711     }
712   fprintf (file, "\n\n");
713 }
714
715 /* Dumps the data dependence relations DDRS in FILE.  */
716
717 void 
718 dump_ddrs (FILE *file, varray_type ddrs)
719 {
720   unsigned int i;
721
722   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
723     {
724       struct data_dependence_relation *ddr = 
725         (struct data_dependence_relation *) 
726         VARRAY_GENERIC_PTR (ddrs, i);
727       dump_data_dependence_relation (file, ddr);
728     }
729   fprintf (file, "\n\n");
730 }
731
732 \f
733
734 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
735    approximation of the number of iterations for LOOP.  */
736
737 static void
738 compute_estimated_nb_iterations (struct loop *loop)
739 {
740   struct nb_iter_bound *bound;
741   
742   for (bound = loop->bounds; bound; bound = bound->next)
743     if (TREE_CODE (bound->bound) == INTEGER_CST
744         /* Update only when there is no previous estimation.  */
745         && (chrec_contains_undetermined (loop->estimated_nb_iterations)
746             /* Or when the current estimation is smaller.  */
747             || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
748       loop->estimated_nb_iterations = bound->bound;
749 }
750
751 /* Estimate the number of iterations from the size of the data and the
752    access functions.  */
753
754 static void
755 estimate_niter_from_size_of_data (struct loop *loop, 
756                                   tree opnd0, 
757                                   tree access_fn, 
758                                   tree stmt)
759 {
760   tree estimation;
761   tree array_size, data_size, element_size;
762   tree init, step;
763
764   init = initial_condition (access_fn);
765   step = evolution_part_in_loop_num (access_fn, loop->num);
766
767   array_size = TYPE_SIZE (TREE_TYPE (opnd0));
768   element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
769   if (array_size == NULL_TREE 
770       || TREE_CODE (array_size) != INTEGER_CST
771       || TREE_CODE (element_size) != INTEGER_CST)
772     return;
773
774   data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
775                            array_size, element_size);
776
777   if (init != NULL_TREE
778       && step != NULL_TREE
779       && TREE_CODE (init) == INTEGER_CST
780       && TREE_CODE (step) == INTEGER_CST)
781     {
782       estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
783                                 fold_build2 (MINUS_EXPR, integer_type_node,
784                                              data_size, init), step);
785
786       record_estimate (loop, estimation, boolean_true_node, stmt);
787     }
788 }
789
790 /* Given an ARRAY_REF node REF, records its access functions.
791    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
792    i.e. the constant "3", then recursively call the function on opnd0,
793    i.e. the ARRAY_REF "A[i]".  The function returns the base name:
794    "A".  */
795
796 static tree
797 analyze_array_indexes (struct loop *loop,
798                        VEC(tree,heap) **access_fns, 
799                        tree ref, tree stmt)
800 {
801   tree opnd0, opnd1;
802   tree access_fn;
803   
804   opnd0 = TREE_OPERAND (ref, 0);
805   opnd1 = TREE_OPERAND (ref, 1);
806   
807   /* The detection of the evolution function for this data access is
808      postponed until the dependence test.  This lazy strategy avoids
809      the computation of access functions that are of no interest for
810      the optimizers.  */
811   access_fn = instantiate_parameters 
812     (loop, analyze_scalar_evolution (loop, opnd1));
813
814   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
815     estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
816   
817   VEC_safe_push (tree, heap, *access_fns, access_fn);
818   
819   /* Recursively record other array access functions.  */
820   if (TREE_CODE (opnd0) == ARRAY_REF)
821     return analyze_array_indexes (loop, access_fns, opnd0, stmt);
822   
823   /* Return the base name of the data access.  */
824   else
825     return opnd0;
826 }
827
828 /* For a data reference REF contained in the statement STMT, initialize
829    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
830    set to true when REF is in the right hand side of an
831    assignment.  */
832
833 static struct data_reference *
834 analyze_array (tree stmt, tree ref, bool is_read)
835 {
836   struct data_reference *res;
837   VEC(tree,heap) *acc_fns;
838
839   if (dump_file && (dump_flags & TDF_DETAILS))
840     {
841       fprintf (dump_file, "(analyze_array \n");
842       fprintf (dump_file, "  (ref = ");
843       print_generic_stmt (dump_file, ref, 0);
844       fprintf (dump_file, ")\n");
845     }
846   
847   res = xmalloc (sizeof (struct data_reference));
848   
849   DR_STMT (res) = stmt;
850   DR_REF (res) = ref;
851   acc_fns = VEC_alloc (tree, heap, 3);
852   DR_BASE_OBJECT (res) = analyze_array_indexes 
853     (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
854   DR_TYPE (res) = ARRAY_REF_TYPE;
855   DR_SET_ACCESS_FNS (res, acc_fns);
856   DR_IS_READ (res) = is_read;
857   DR_BASE_ADDRESS (res) = NULL_TREE;
858   DR_OFFSET (res) = NULL_TREE;
859   DR_INIT (res) = NULL_TREE;
860   DR_STEP (res) = NULL_TREE;
861   DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
862   DR_MEMTAG (res) = NULL_TREE;
863   DR_PTR_INFO (res) = NULL;
864   
865   if (dump_file && (dump_flags & TDF_DETAILS))
866     fprintf (dump_file, ")\n");
867   
868   return res;
869 }
870
871
872 /* Analyze an indirect memory reference, REF, that comes from STMT.
873    IS_READ is true if this is an indirect load, and false if it is
874    an indirect store.
875    Return a new data reference structure representing the indirect_ref, or
876    NULL if we cannot describe the access function.  */
877   
878 static struct data_reference *
879 analyze_indirect_ref (tree stmt, tree ref, bool is_read) 
880 {
881   struct loop *loop = loop_containing_stmt (stmt);
882   tree ptr_ref = TREE_OPERAND (ref, 0);
883   tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
884   tree init = initial_condition_in_loop_num (access_fn, loop->num);
885   tree base_address = NULL_TREE, evolution, step = NULL_TREE;
886   struct ptr_info_def *ptr_info = NULL;
887
888   if (TREE_CODE (ptr_ref) == SSA_NAME)
889     ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
890
891   STRIP_NOPS (init);   
892   if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
893     {
894       if (dump_file && (dump_flags & TDF_DETAILS))
895         {
896           fprintf (dump_file, "\nBad access function of ptr: ");
897           print_generic_expr (dump_file, ref, TDF_SLIM);
898           fprintf (dump_file, "\n");
899         }
900       return NULL;
901     }
902
903   if (dump_file && (dump_flags & TDF_DETAILS))
904     {
905       fprintf (dump_file, "\nAccess function of ptr: ");
906       print_generic_expr (dump_file, access_fn, TDF_SLIM);
907       fprintf (dump_file, "\n");
908     }
909
910   if (!expr_invariant_in_loop_p (loop, init))
911     {
912     if (dump_file && (dump_flags & TDF_DETAILS))
913         fprintf (dump_file, "\ninitial condition is not loop invariant.\n");    
914     }
915   else
916     {
917       base_address = init;
918       evolution = evolution_part_in_loop_num (access_fn, loop->num);
919       if (evolution != chrec_dont_know)
920         {       
921           if (!evolution)
922             step = ssize_int (0);
923           else  
924             {
925               if (TREE_CODE (evolution) == INTEGER_CST)
926                 step = fold_convert (ssizetype, evolution);
927               else
928                 if (dump_file && (dump_flags & TDF_DETAILS))
929                   fprintf (dump_file, "\nnon constant step for ptr access.\n"); 
930             }
931         }
932       else
933         if (dump_file && (dump_flags & TDF_DETAILS))
934           fprintf (dump_file, "\nunknown evolution of ptr.\n"); 
935     }
936   return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address, 
937                         NULL_TREE, step, NULL_TREE, NULL_TREE, 
938                         ptr_info, POINTER_REF_TYPE);
939 }
940
941 /* For a data reference REF contained in the statement STMT, initialize
942    a DATA_REFERENCE structure, and return it.  */
943
944 struct data_reference *
945 init_data_ref (tree stmt, 
946                tree ref,
947                tree base,
948                tree access_fn,
949                bool is_read,
950                tree base_address,
951                tree init_offset,
952                tree step,
953                tree misalign,
954                tree memtag,
955                struct ptr_info_def *ptr_info,
956                enum data_ref_type type)
957 {
958   struct data_reference *res;
959   VEC(tree,heap) *acc_fns;
960
961   if (dump_file && (dump_flags & TDF_DETAILS))
962     {
963       fprintf (dump_file, "(init_data_ref \n");
964       fprintf (dump_file, "  (ref = ");
965       print_generic_stmt (dump_file, ref, 0);
966       fprintf (dump_file, ")\n");
967     }
968   
969   res = xmalloc (sizeof (struct data_reference));
970   
971   DR_STMT (res) = stmt;
972   DR_REF (res) = ref;
973   DR_BASE_OBJECT (res) = base;
974   DR_TYPE (res) = type;
975   acc_fns = VEC_alloc (tree, heap, 3);
976   DR_SET_ACCESS_FNS (res, acc_fns);
977   VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
978   DR_IS_READ (res) = is_read;
979   DR_BASE_ADDRESS (res) = base_address;
980   DR_OFFSET (res) = init_offset;
981   DR_INIT (res) = NULL_TREE;
982   DR_STEP (res) = step;
983   DR_OFFSET_MISALIGNMENT (res) = misalign;
984   DR_MEMTAG (res) = memtag;
985   DR_PTR_INFO (res) = ptr_info;
986   
987   if (dump_file && (dump_flags & TDF_DETAILS))
988     fprintf (dump_file, ")\n");
989   
990   return res;
991 }
992
993 \f
994
995 /* Function strip_conversions
996
997    Strip conversions that don't narrow the mode.  */
998
999 static tree 
1000 strip_conversion (tree expr)
1001 {
1002   tree to, ti, oprnd0;
1003   
1004   while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1005     {
1006       to = TREE_TYPE (expr);
1007       oprnd0 = TREE_OPERAND (expr, 0);
1008       ti = TREE_TYPE (oprnd0);
1009  
1010       if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1011         return NULL_TREE;
1012       if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1013         return NULL_TREE;
1014       
1015       expr = oprnd0;
1016     }
1017   return expr; 
1018 }
1019 \f
1020
1021 /* Function analyze_offset_expr
1022
1023    Given an offset expression EXPR received from get_inner_reference, analyze
1024    it and create an expression for INITIAL_OFFSET by substituting the variables 
1025    of EXPR with initial_condition of the corresponding access_fn in the loop. 
1026    E.g., 
1027       for i
1028          for (j = 3; j < N; j++)
1029             a[j].b[i][j] = 0;
1030          
1031    For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be 
1032    substituted, since its access_fn in the inner loop is i. 'j' will be 
1033    substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1034    C` =  3 * C_j + C.
1035
1036    Compute MISALIGN (the misalignment of the data reference initial access from
1037    its base). Misalignment can be calculated only if all the variables can be 
1038    substituted with constants, otherwise, we record maximum possible alignment
1039    in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN 
1040    will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be 
1041    recorded in ALIGNED_TO.
1042
1043    STEP is an evolution of the data reference in this loop in bytes.
1044    In the above example, STEP is C_j.
1045
1046    Return FALSE, if the analysis fails, e.g., there is no access_fn for a 
1047    variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1048    and STEP) are NULL_TREEs. Otherwise, return TRUE.
1049
1050 */
1051
1052 static bool
1053 analyze_offset_expr (tree expr, 
1054                      struct loop *loop, 
1055                      tree *initial_offset,
1056                      tree *misalign,
1057                      tree *aligned_to,
1058                      tree *step)
1059 {
1060   tree oprnd0;
1061   tree oprnd1;
1062   tree left_offset = ssize_int (0);
1063   tree right_offset = ssize_int (0);
1064   tree left_misalign = ssize_int (0);
1065   tree right_misalign = ssize_int (0);
1066   tree left_step = ssize_int (0);
1067   tree right_step = ssize_int (0);
1068   enum tree_code code;
1069   tree init, evolution;
1070   tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1071
1072   *step = NULL_TREE;
1073   *misalign = NULL_TREE;
1074   *aligned_to = NULL_TREE;  
1075   *initial_offset = NULL_TREE;
1076
1077   /* Strip conversions that don't narrow the mode.  */
1078   expr = strip_conversion (expr);
1079   if (!expr)
1080     return false;
1081
1082   /* Stop conditions:
1083      1. Constant.  */
1084   if (TREE_CODE (expr) == INTEGER_CST)
1085     {
1086       *initial_offset = fold_convert (ssizetype, expr);
1087       *misalign = fold_convert (ssizetype, expr);      
1088       *step = ssize_int (0);
1089       return true;
1090     }
1091
1092   /* 2. Variable. Try to substitute with initial_condition of the corresponding
1093      access_fn in the current loop.  */
1094   if (SSA_VAR_P (expr))
1095     {
1096       tree access_fn = analyze_scalar_evolution (loop, expr);
1097
1098       if (access_fn == chrec_dont_know)
1099         /* No access_fn.  */
1100         return false;
1101
1102       init = initial_condition_in_loop_num (access_fn, loop->num);
1103       if (init == expr && !expr_invariant_in_loop_p (loop, init))
1104         /* Not enough information: may be not loop invariant.  
1105            E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its 
1106            initial_condition is D, but it depends on i - loop's induction
1107            variable.  */          
1108         return false;
1109
1110       evolution = evolution_part_in_loop_num (access_fn, loop->num);
1111       if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1112         /* Evolution is not constant.  */
1113         return false;
1114
1115       if (TREE_CODE (init) == INTEGER_CST)
1116         *misalign = fold_convert (ssizetype, init);
1117       else
1118         /* Not constant, misalignment cannot be calculated.  */
1119         *misalign = NULL_TREE;
1120
1121       *initial_offset = fold_convert (ssizetype, init); 
1122
1123       *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1124       return true;      
1125     }
1126
1127   /* Recursive computation.  */
1128   if (!BINARY_CLASS_P (expr))
1129     {
1130       /* We expect to get binary expressions (PLUS/MINUS and MULT).  */
1131       if (dump_file && (dump_flags & TDF_DETAILS))
1132         {
1133           fprintf (dump_file, "\nNot binary expression ");
1134           print_generic_expr (dump_file, expr, TDF_SLIM);
1135           fprintf (dump_file, "\n");
1136         }
1137       return false;
1138     }
1139   oprnd0 = TREE_OPERAND (expr, 0);
1140   oprnd1 = TREE_OPERAND (expr, 1);
1141
1142   if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign, 
1143                             &left_aligned_to, &left_step)
1144       || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign, 
1145                                &right_aligned_to, &right_step))
1146     return false;
1147
1148   /* The type of the operation: plus, minus or mult.  */
1149   code = TREE_CODE (expr);
1150   switch (code)
1151     {
1152     case MULT_EXPR:
1153       if (TREE_CODE (right_offset) != INTEGER_CST)
1154         /* RIGHT_OFFSET can be not constant. For example, for arrays of variable 
1155            sized types. 
1156            FORNOW: We don't support such cases.  */
1157         return false;
1158
1159       /* Strip conversions that don't narrow the mode.  */
1160       left_offset = strip_conversion (left_offset);      
1161       if (!left_offset)
1162         return false;      
1163       /* Misalignment computation.  */
1164       if (SSA_VAR_P (left_offset))
1165         {
1166           /* If the left side contains variables that can't be substituted with 
1167              constants, the misalignment is unknown. However, if the right side 
1168              is a multiple of some alignment, we know that the expression is
1169              aligned to it. Therefore, we record such maximum possible value.
1170            */
1171           *misalign = NULL_TREE;
1172           *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1173         }
1174       else 
1175         {
1176           /* The left operand was successfully substituted with constant.  */     
1177           if (left_misalign)
1178             {
1179               /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is 
1180                  NULL_TREE.  */
1181               *misalign  = size_binop (code, left_misalign, right_misalign);
1182               if (left_aligned_to && right_aligned_to)
1183                 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, 
1184                                           right_aligned_to);
1185               else 
1186                 *aligned_to = left_aligned_to ? 
1187                   left_aligned_to : right_aligned_to;
1188             }
1189           else
1190             *misalign = NULL_TREE; 
1191         }
1192
1193       /* Step calculation.  */
1194       /* Multiply the step by the right operand.  */
1195       *step  = size_binop (MULT_EXPR, left_step, right_offset);
1196       break;
1197    
1198     case PLUS_EXPR:
1199     case MINUS_EXPR:
1200       /* Combine the recursive calculations for step and misalignment.  */
1201       *step = size_binop (code, left_step, right_step);
1202
1203       /* Unknown alignment.  */
1204       if ((!left_misalign && !left_aligned_to)
1205           || (!right_misalign && !right_aligned_to))
1206         {
1207           *misalign = NULL_TREE;
1208           *aligned_to = NULL_TREE;
1209           break;
1210         }
1211
1212       if (left_misalign && right_misalign)
1213         *misalign = size_binop (code, left_misalign, right_misalign);
1214       else
1215         *misalign = left_misalign ? left_misalign : right_misalign;
1216
1217       if (left_aligned_to && right_aligned_to)
1218         *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1219       else 
1220         *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1221
1222       break;
1223
1224     default:
1225       gcc_unreachable ();
1226     }
1227
1228   /* Compute offset.  */
1229   *initial_offset = fold_convert (ssizetype, 
1230                                   fold_build2 (code, TREE_TYPE (left_offset), 
1231                                                left_offset, 
1232                                                right_offset));
1233   return true;
1234 }
1235
1236 /* Function address_analysis
1237
1238    Return the BASE of the address expression EXPR.
1239    Also compute the OFFSET from BASE, MISALIGN and STEP.
1240
1241    Input:
1242    EXPR - the address expression that is being analyzed
1243    STMT - the statement that contains EXPR or its original memory reference
1244    IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1245    DR - data_reference struct for the original memory reference
1246
1247    Output:
1248    BASE (returned value) - the base of the data reference EXPR.
1249    INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1250    MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1251               computation is impossible 
1252    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 
1253                 calculated (doesn't depend on variables)
1254    STEP - evolution of EXPR in the loop
1255  
1256    If something unexpected is encountered (an unsupported form of data-ref),
1257    then NULL_TREE is returned.  
1258  */
1259
1260 static tree
1261 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr, 
1262                   tree *offset, tree *misalign, tree *aligned_to, tree *step)
1263 {
1264   tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1265   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1266   tree dummy, address_aligned_to = NULL_TREE;
1267   struct ptr_info_def *dummy1;
1268   subvar_t dummy2;
1269
1270   switch (TREE_CODE (expr))
1271     {
1272     case PLUS_EXPR:
1273     case MINUS_EXPR:
1274       /* EXPR is of form {base +/- offset} (or {offset +/- base}).  */
1275       oprnd0 = TREE_OPERAND (expr, 0);
1276       oprnd1 = TREE_OPERAND (expr, 1);
1277
1278       STRIP_NOPS (oprnd0);
1279       STRIP_NOPS (oprnd1);
1280       
1281       /* Recursively try to find the base of the address contained in EXPR.
1282          For offset, the returned base will be NULL.  */
1283       base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset, 
1284                                      &address_misalign, &address_aligned_to, 
1285                                      step);
1286
1287       base_addr1 = address_analysis (oprnd1, stmt, is_read,  dr, &address_offset, 
1288                                      &address_misalign, &address_aligned_to, 
1289                                      step);
1290
1291       /* We support cases where only one of the operands contains an 
1292          address.  */
1293       if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1294         {
1295           if (dump_file && (dump_flags & TDF_DETAILS))
1296             {
1297               fprintf (dump_file, 
1298                     "\neither more than one address or no addresses in expr ");
1299               print_generic_expr (dump_file, expr, TDF_SLIM);
1300               fprintf (dump_file, "\n");
1301             }   
1302           return NULL_TREE;
1303         }
1304
1305       /* To revert STRIP_NOPS.  */
1306       oprnd0 = TREE_OPERAND (expr, 0);
1307       oprnd1 = TREE_OPERAND (expr, 1);
1308       
1309       offset_expr = base_addr0 ? 
1310         fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1311
1312       /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is 
1313          a number, we can add it to the misalignment value calculated for base,
1314          otherwise, misalignment is NULL.  */
1315       if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1316         {
1317           *misalign = size_binop (TREE_CODE (expr), address_misalign, 
1318                                   offset_expr);
1319           *aligned_to = address_aligned_to;
1320         }
1321       else
1322         {
1323           *misalign = NULL_TREE;
1324           *aligned_to = NULL_TREE;
1325         }
1326
1327       /* Combine offset (from EXPR {base + offset}) with the offset calculated
1328          for base.  */
1329       *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1330       return base_addr0 ? base_addr0 : base_addr1;
1331
1332     case ADDR_EXPR:
1333       base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read, 
1334                                       &dr, offset, misalign, aligned_to, step, 
1335                                       &dummy, &dummy1, &dummy2);
1336       return base_address;
1337
1338     case SSA_NAME:
1339       if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1340         {
1341           if (dump_file && (dump_flags & TDF_DETAILS))
1342             {
1343               fprintf (dump_file, "\nnot pointer SSA_NAME ");
1344               print_generic_expr (dump_file, expr, TDF_SLIM);
1345               fprintf (dump_file, "\n");
1346             }   
1347           return NULL_TREE;
1348         }
1349       *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1350       *misalign = ssize_int (0);
1351       *offset = ssize_int (0);
1352       *step = ssize_int (0);
1353       return expr;
1354       
1355     default:
1356       return NULL_TREE;
1357     }
1358 }
1359
1360
1361 /* Function object_analysis
1362
1363    Create a data-reference structure DR for MEMREF.
1364    Return the BASE of the data reference MEMREF if the analysis is possible.
1365    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1366    E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset  
1367    'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET 
1368    instantiated with initial_conditions of access_functions of variables, 
1369    and STEP is the evolution of the DR_REF in this loop.
1370    
1371    Function get_inner_reference is used for the above in case of ARRAY_REF and
1372    COMPONENT_REF.
1373
1374    The structure of the function is as follows:
1375    Part 1:
1376    Case 1. For handled_component_p refs 
1377           1.1 build data-reference structure for MEMREF
1378           1.2 call get_inner_reference
1379             1.2.1 analyze offset expr received from get_inner_reference
1380           (fall through with BASE)
1381    Case 2. For declarations 
1382           2.1 set MEMTAG
1383    Case 3. For INDIRECT_REFs 
1384           3.1 build data-reference structure for MEMREF
1385           3.2 analyze evolution and initial condition of MEMREF
1386           3.3 set data-reference structure for MEMREF
1387           3.4 call address_analysis to analyze INIT of the access function
1388           3.5 extract memory tag
1389
1390    Part 2:
1391    Combine the results of object and address analysis to calculate 
1392    INITIAL_OFFSET, STEP and misalignment info.   
1393
1394    Input:
1395    MEMREF - the memory reference that is being analyzed
1396    STMT - the statement that contains MEMREF
1397    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1398    
1399    Output:
1400    BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1401                                    E.g, if MEMREF is a.b[k].c[i][j] the returned
1402                                    base is &a.
1403    DR - data_reference struct for MEMREF
1404    INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1405    MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of 
1406               ALIGNMENT or NULL_TREE if the computation is impossible
1407    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 
1408                 calculated (doesn't depend on variables)
1409    STEP - evolution of the DR_REF in the loop
1410    MEMTAG - memory tag for aliasing purposes
1411    PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1412    SUBVARS - Sub-variables of the variable
1413
1414    If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned, 
1415    but DR can be created anyway.
1416    
1417 */
1418  
1419 static tree
1420 object_analysis (tree memref, tree stmt, bool is_read, 
1421                  struct data_reference **dr, tree *offset, tree *misalign, 
1422                  tree *aligned_to, tree *step, tree *memtag,
1423                  struct ptr_info_def **ptr_info, subvar_t *subvars)
1424 {
1425   tree base = NULL_TREE, base_address = NULL_TREE;
1426   tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1427   tree object_step = ssize_int (0), address_step = ssize_int (0);
1428   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1429   HOST_WIDE_INT pbitsize, pbitpos;
1430   tree poffset, bit_pos_in_bytes;
1431   enum machine_mode pmode;
1432   int punsignedp, pvolatilep;
1433   tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1434   struct loop *loop = loop_containing_stmt (stmt);
1435   struct data_reference *ptr_dr = NULL;
1436   tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1437
1438  *ptr_info = NULL;
1439
1440   /* Part 1:  */
1441   /* Case 1. handled_component_p refs.  */
1442   if (handled_component_p (memref))
1443     {
1444       /* 1.1 build data-reference structure for MEMREF.  */
1445       /* TODO: handle COMPONENT_REFs.  */
1446       if (!(*dr))
1447         { 
1448           if (TREE_CODE (memref) == ARRAY_REF)
1449             *dr = analyze_array (stmt, memref, is_read);          
1450           else
1451             {
1452               /* FORNOW.  */
1453               if (dump_file && (dump_flags & TDF_DETAILS))
1454                 {
1455                   fprintf (dump_file, "\ndata-ref of unsupported type ");
1456                   print_generic_expr (dump_file, memref, TDF_SLIM);
1457                   fprintf (dump_file, "\n");
1458                 }
1459               return NULL_TREE;
1460             }
1461         }
1462
1463       /* 1.2 call get_inner_reference.  */
1464       /* Find the base and the offset from it.  */
1465       base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1466                                   &pmode, &punsignedp, &pvolatilep, false);
1467       if (!base)
1468         {
1469           if (dump_file && (dump_flags & TDF_DETAILS))
1470             {
1471               fprintf (dump_file, "\nfailed to get inner ref for ");
1472               print_generic_expr (dump_file, memref, TDF_SLIM);
1473               fprintf (dump_file, "\n");
1474             }     
1475           return NULL_TREE;
1476         }
1477
1478       /* 1.2.1 analyze offset expr received from get_inner_reference.  */
1479       if (poffset 
1480           && !analyze_offset_expr (poffset, loop, &object_offset, 
1481                                    &object_misalign, &object_aligned_to,
1482                                    &object_step))
1483         {
1484           if (dump_file && (dump_flags & TDF_DETAILS))
1485             {
1486               fprintf (dump_file, "\nfailed to compute offset or step for ");
1487               print_generic_expr (dump_file, memref, TDF_SLIM);
1488               fprintf (dump_file, "\n");
1489             }
1490           return NULL_TREE;
1491         }
1492
1493       /* Add bit position to OFFSET and MISALIGN.  */
1494
1495       bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1496       /* Check that there is no remainder in bits.  */
1497       if (pbitpos%BITS_PER_UNIT)
1498         {
1499           if (dump_file && (dump_flags & TDF_DETAILS))
1500             fprintf (dump_file, "\nbit offset alignment.\n");
1501           return NULL_TREE;
1502         }
1503       object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);     
1504       if (object_misalign) 
1505         object_misalign = size_binop (PLUS_EXPR, object_misalign, 
1506                                       bit_pos_in_bytes); 
1507       
1508       memref = base; /* To continue analysis of BASE.  */
1509       /* fall through  */
1510     }
1511   
1512   /*  Part 1: Case 2. Declarations.  */ 
1513   if (DECL_P (memref))
1514     {
1515       /* We expect to get a decl only if we already have a DR.  */
1516       if (!(*dr))
1517         {
1518           if (dump_file && (dump_flags & TDF_DETAILS))
1519             {
1520               fprintf (dump_file, "\nunhandled decl ");
1521               print_generic_expr (dump_file, memref, TDF_SLIM);
1522               fprintf (dump_file, "\n");
1523             }
1524           return NULL_TREE;
1525         }
1526
1527       /* TODO: if during the analysis of INDIRECT_REF we get to an object, put 
1528          the object in BASE_OBJECT field if we can prove that this is O.K., 
1529          i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1530          (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1531          that every access with 'p' (the original INDIRECT_REF based on '&a')
1532          in the loop is within the array boundaries - from a[0] to a[N-1]).
1533          Otherwise, our alias analysis can be incorrect.
1534          Even if an access function based on BASE_OBJECT can't be build, update
1535          BASE_OBJECT field to enable us to prove that two data-refs are 
1536          different (without access function, distance analysis is impossible).
1537       */
1538      if (SSA_VAR_P (memref) && var_can_have_subvars (memref))   
1539         *subvars = get_subvars_for_var (memref);
1540       base_address = build_fold_addr_expr (memref);
1541       /* 2.1 set MEMTAG.  */
1542       *memtag = memref;
1543     }
1544
1545   /* Part 1:  Case 3. INDIRECT_REFs.  */
1546   else if (TREE_CODE (memref) == INDIRECT_REF)
1547     {
1548       tree ptr_ref = TREE_OPERAND (memref, 0);
1549       if (TREE_CODE (ptr_ref) == SSA_NAME)
1550         *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1551
1552       /* 3.1 build data-reference structure for MEMREF.  */
1553       ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1554       if (!ptr_dr)
1555         {
1556           if (dump_file && (dump_flags & TDF_DETAILS))
1557             {
1558               fprintf (dump_file, "\nfailed to create dr for ");
1559               print_generic_expr (dump_file, memref, TDF_SLIM);
1560               fprintf (dump_file, "\n");
1561             }   
1562           return NULL_TREE;      
1563         }
1564
1565       /* 3.2 analyze evolution and initial condition of MEMREF.  */
1566       ptr_step = DR_STEP (ptr_dr);
1567       ptr_init = DR_BASE_ADDRESS (ptr_dr);
1568       if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1569         {
1570           *dr = (*dr) ? *dr : ptr_dr;
1571           if (dump_file && (dump_flags & TDF_DETAILS))
1572             {
1573               fprintf (dump_file, "\nbad pointer access ");
1574               print_generic_expr (dump_file, memref, TDF_SLIM);
1575               fprintf (dump_file, "\n");
1576             }
1577           return NULL_TREE;
1578         }
1579
1580       if (integer_zerop (ptr_step) && !(*dr))
1581         {
1582           if (dump_file && (dump_flags & TDF_DETAILS)) 
1583             fprintf (dump_file, "\nptr is loop invariant.\n");  
1584           *dr = ptr_dr;
1585           return NULL_TREE;
1586         
1587           /* If there exists DR for MEMREF, we are analyzing the base of
1588              handled component (PTR_INIT), which not necessary has evolution in 
1589              the loop.  */
1590         }
1591       object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1592
1593       /* 3.3 set data-reference structure for MEMREF.  */
1594       if (!*dr)
1595         *dr = ptr_dr;
1596
1597       /* 3.4 call address_analysis to analyze INIT of the access 
1598          function.  */
1599       base_address = address_analysis (ptr_init, stmt, is_read, *dr, 
1600                                        &address_offset, &address_misalign, 
1601                                        &address_aligned_to, &address_step);
1602       if (!base_address)
1603         {
1604           if (dump_file && (dump_flags & TDF_DETAILS))
1605             {
1606               fprintf (dump_file, "\nfailed to analyze address ");
1607               print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1608               fprintf (dump_file, "\n");
1609             }
1610           return NULL_TREE;
1611         }
1612
1613       /* 3.5 extract memory tag.  */
1614       switch (TREE_CODE (base_address))
1615         {
1616         case SSA_NAME:
1617           *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1618           if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1619             *memtag = get_var_ann (
1620                       SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1621           break;
1622         case ADDR_EXPR:
1623           *memtag = TREE_OPERAND (base_address, 0);
1624           break;
1625         default:
1626           if (dump_file && (dump_flags & TDF_DETAILS))
1627             {
1628               fprintf (dump_file, "\nno memtag for "); 
1629               print_generic_expr (dump_file, memref, TDF_SLIM);
1630               fprintf (dump_file, "\n");
1631             }
1632           *memtag = NULL_TREE;
1633           break;
1634         }
1635     }      
1636     
1637   if (!base_address)
1638     {
1639       /* MEMREF cannot be analyzed.  */
1640       if (dump_file && (dump_flags & TDF_DETAILS))
1641         {
1642           fprintf (dump_file, "\ndata-ref of unsupported type ");
1643           print_generic_expr (dump_file, memref, TDF_SLIM);
1644           fprintf (dump_file, "\n");
1645         }
1646       return NULL_TREE;
1647     }
1648
1649   if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1650     *subvars = get_subvars_for_var (*memtag);
1651         
1652   /* Part 2: Combine the results of object and address analysis to calculate 
1653      INITIAL_OFFSET, STEP and misalignment info.  */
1654   *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1655
1656   if ((!object_misalign && !object_aligned_to)
1657       || (!address_misalign && !address_aligned_to))
1658     {
1659       *misalign = NULL_TREE;
1660       *aligned_to = NULL_TREE;
1661     }  
1662   else 
1663     {
1664       if (object_misalign && address_misalign)
1665         *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1666       else
1667         *misalign = object_misalign ? object_misalign : address_misalign;
1668       if (object_aligned_to && address_aligned_to)
1669         *aligned_to = size_binop (MIN_EXPR, object_aligned_to, 
1670                                   address_aligned_to);
1671       else
1672         *aligned_to = object_aligned_to ? 
1673           object_aligned_to : address_aligned_to; 
1674     }
1675   *step = size_binop (PLUS_EXPR, object_step, address_step); 
1676
1677   return base_address;
1678 }
1679
1680 /* Function analyze_offset.
1681    
1682    Extract INVARIANT and CONSTANT parts from OFFSET. 
1683
1684 */
1685 static void 
1686 analyze_offset (tree offset, tree *invariant, tree *constant)
1687 {
1688   tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1689   enum tree_code code = TREE_CODE (offset);
1690
1691   *invariant = NULL_TREE;
1692   *constant = NULL_TREE;
1693
1694   /* Not PLUS/MINUS expression - recursion stop condition.  */
1695   if (code != PLUS_EXPR && code != MINUS_EXPR)
1696     {
1697       if (TREE_CODE (offset) == INTEGER_CST)
1698         *constant = offset;
1699       else
1700         *invariant = offset;
1701       return;
1702     }
1703
1704   op0 = TREE_OPERAND (offset, 0);
1705   op1 = TREE_OPERAND (offset, 1);
1706
1707   /* Recursive call with the operands.  */
1708   analyze_offset (op0, &invariant_0, &constant_0);
1709   analyze_offset (op1, &invariant_1, &constant_1);
1710
1711   /* Combine the results.  */
1712   *constant = constant_0 ? constant_0 : constant_1;
1713   if (invariant_0 && invariant_1)
1714     *invariant = 
1715       fold (build (code, TREE_TYPE (invariant_0), invariant_0, invariant_1));
1716   else
1717     *invariant = invariant_0 ? invariant_0 : invariant_1;
1718 }
1719
1720
1721 /* Function create_data_ref.
1722    
1723    Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1724    DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1725    DR_MEMTAG, and DR_POINTSTO_INFO fields. 
1726
1727    Input:
1728    MEMREF - the memory reference that is being analyzed
1729    STMT - the statement that contains MEMREF
1730    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1731
1732    Output:
1733    DR (returned value) - data_reference struct for MEMREF
1734 */
1735
1736 static struct data_reference *
1737 create_data_ref (tree memref, tree stmt, bool is_read)
1738 {
1739   struct data_reference *dr = NULL;
1740   tree base_address, offset, step, misalign, memtag;
1741   struct loop *loop = loop_containing_stmt (stmt);
1742   tree invariant = NULL_TREE, constant = NULL_TREE;
1743   tree type_size, init_cond;
1744   struct ptr_info_def *ptr_info;
1745   subvar_t subvars = NULL;
1746   tree aligned_to;
1747
1748   if (!memref)
1749     return NULL;
1750
1751   base_address = object_analysis (memref, stmt, is_read, &dr, &offset, 
1752                                   &misalign, &aligned_to, &step, &memtag, 
1753                                   &ptr_info, &subvars);
1754   if (!dr || !base_address)
1755     {
1756       if (dump_file && (dump_flags & TDF_DETAILS))
1757         {
1758           fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1759           print_generic_expr (dump_file, memref, TDF_SLIM);
1760           fprintf (dump_file, "\n");
1761         }
1762       return NULL;
1763     }
1764
1765   DR_BASE_ADDRESS (dr) = base_address;
1766   DR_OFFSET (dr) = offset;
1767   DR_INIT (dr) = ssize_int (0);
1768   DR_STEP (dr) = step;
1769   DR_OFFSET_MISALIGNMENT (dr) = misalign;
1770   DR_ALIGNED_TO (dr) = aligned_to;
1771   DR_MEMTAG (dr) = memtag;
1772   DR_PTR_INFO (dr) = ptr_info;
1773   DR_SUBVARS (dr) = subvars;
1774   
1775   type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1776
1777   /* Change the access function for INIDIRECT_REFs, according to 
1778      DR_BASE_ADDRESS.  Analyze OFFSET calculated in object_analysis. OFFSET is 
1779      an expression that can contain loop invariant expressions and constants.
1780      We put the constant part in the initial condition of the access function
1781      (for data dependence tests), and in DR_INIT of the data-ref. The loop
1782      invariant part is put in DR_OFFSET. 
1783      The evolution part of the access function is STEP calculated in
1784      object_analysis divided by the size of data type.
1785   */
1786   if (!DR_BASE_OBJECT (dr))
1787     {
1788       tree access_fn;
1789       tree new_step;
1790
1791       /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and
1792          DR_OFFSET fields of DR.  */
1793       analyze_offset (offset, &invariant, &constant); 
1794       if (constant)
1795         {
1796           DR_INIT (dr) = fold_convert (ssizetype, constant);
1797           init_cond = fold (build (TRUNC_DIV_EXPR, TREE_TYPE (constant), 
1798                                    constant, type_size));
1799         }
1800       else
1801         DR_INIT (dr) = init_cond = ssize_int (0);;
1802
1803       if (invariant)
1804         DR_OFFSET (dr) = invariant;
1805       else
1806         DR_OFFSET (dr) = ssize_int (0);
1807
1808       /* Update access function.  */
1809       access_fn = DR_ACCESS_FN (dr, 0);
1810       new_step = size_binop (TRUNC_DIV_EXPR,  
1811                              fold_convert (ssizetype, step), type_size);
1812
1813       access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1814       access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1815
1816       VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1817     }
1818
1819   if (dump_file && (dump_flags & TDF_DETAILS))
1820     {
1821       struct ptr_info_def *pi = DR_PTR_INFO (dr);
1822
1823       fprintf (dump_file, "\nCreated dr for ");
1824       print_generic_expr (dump_file, memref, TDF_SLIM);
1825       fprintf (dump_file, "\n\tbase_address: ");
1826       print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1827       fprintf (dump_file, "\n\toffset from base address: ");
1828       print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1829       fprintf (dump_file, "\n\tconstant offset from base address: ");
1830       print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1831       fprintf (dump_file, "\n\tbase_object: ");
1832       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1833       fprintf (dump_file, "\n\tstep: ");
1834       print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1835       fprintf (dump_file, "B\n\tmisalignment from base: ");
1836       print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1837       if (DR_OFFSET_MISALIGNMENT (dr))
1838         fprintf (dump_file, "B");
1839       if (DR_ALIGNED_TO (dr))
1840         {
1841           fprintf (dump_file, "\n\taligned to: ");
1842           print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1843         }
1844       fprintf (dump_file, "\n\tmemtag: ");
1845       print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1846       fprintf (dump_file, "\n");
1847       if (pi && pi->name_mem_tag)
1848         {
1849           fprintf (dump_file, "\n\tnametag: ");
1850           print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
1851           fprintf (dump_file, "\n");
1852         }
1853     }  
1854   return dr;  
1855 }
1856
1857
1858 /* Returns true when all the functions of a tree_vec CHREC are the
1859    same.  */
1860
1861 static bool 
1862 all_chrecs_equal_p (tree chrec)
1863 {
1864   int j;
1865
1866   for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
1867     {
1868       tree chrec_j = TREE_VEC_ELT (chrec, j);
1869       tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
1870       if (!integer_zerop 
1871           (chrec_fold_minus 
1872            (integer_type_node, chrec_j, chrec_j_1)))
1873         return false;
1874     }
1875   return true;
1876 }
1877
1878 /* Determine for each subscript in the data dependence relation DDR
1879    the distance.  */
1880
1881 void
1882 compute_subscript_distance (struct data_dependence_relation *ddr)
1883 {
1884   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1885     {
1886       unsigned int i;
1887       
1888       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1889         {
1890           tree conflicts_a, conflicts_b, difference;
1891           struct subscript *subscript;
1892           
1893           subscript = DDR_SUBSCRIPT (ddr, i);
1894           conflicts_a = SUB_CONFLICTS_IN_A (subscript);
1895           conflicts_b = SUB_CONFLICTS_IN_B (subscript);
1896
1897           if (TREE_CODE (conflicts_a) == TREE_VEC)
1898             {
1899               if (!all_chrecs_equal_p (conflicts_a))
1900                 {
1901                   SUB_DISTANCE (subscript) = chrec_dont_know;
1902                   return;
1903                 }
1904               else
1905                 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
1906             }
1907
1908           if (TREE_CODE (conflicts_b) == TREE_VEC)
1909             {
1910               if (!all_chrecs_equal_p (conflicts_b))
1911                 {
1912                   SUB_DISTANCE (subscript) = chrec_dont_know;
1913                   return;
1914                 }
1915               else
1916                 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
1917             }
1918
1919           difference = chrec_fold_minus 
1920             (integer_type_node, conflicts_b, conflicts_a);
1921           
1922           if (evolution_function_is_constant_p (difference))
1923             SUB_DISTANCE (subscript) = difference;
1924           
1925           else
1926             SUB_DISTANCE (subscript) = chrec_dont_know;
1927         }
1928     }
1929 }
1930
1931 /* Initialize a ddr.  */
1932
1933 struct data_dependence_relation *
1934 initialize_data_dependence_relation (struct data_reference *a, 
1935                                      struct data_reference *b)
1936 {
1937   struct data_dependence_relation *res;
1938   bool differ_p;
1939   unsigned int i;  
1940   
1941   res = xmalloc (sizeof (struct data_dependence_relation));
1942   DDR_A (res) = a;
1943   DDR_B (res) = b;
1944
1945   if (a == NULL || b == NULL)
1946     {
1947       DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
1948       return res;
1949     }   
1950
1951   /* When A and B are arrays and their dimensions differ, we directly
1952      initialize the relation to "there is no dependence": chrec_known.  */
1953   if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
1954       && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1955     {
1956       DDR_ARE_DEPENDENT (res) = chrec_known;
1957       return res;
1958     }
1959
1960     /* Compare the bases of the data-refs.  */
1961   if (!base_addr_differ_p (a, b, &differ_p))
1962     {
1963       /* Can't determine whether the data-refs access the same memory 
1964          region.  */
1965       DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
1966       return res;
1967     }
1968   if (differ_p)
1969     {
1970       DDR_ARE_DEPENDENT (res) = chrec_known;    
1971       return res;
1972     }
1973   
1974   DDR_AFFINE_P (res) = true;
1975   DDR_ARE_DEPENDENT (res) = NULL_TREE;
1976   DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
1977   DDR_SIZE_VECT (res) = 0;
1978   DDR_DIST_VECT (res) = NULL;
1979   DDR_DIR_VECT (res) = NULL;
1980       
1981   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1982     {
1983       struct subscript *subscript;
1984           
1985       subscript = xmalloc (sizeof (struct subscript));
1986       SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
1987       SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
1988       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1989       SUB_DISTANCE (subscript) = chrec_dont_know;
1990       VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
1991     }
1992   
1993   return res;
1994 }
1995
1996 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1997    description.  */
1998
1999 static inline void
2000 finalize_ddr_dependent (struct data_dependence_relation *ddr, 
2001                         tree chrec)
2002 {
2003   if (dump_file && (dump_flags & TDF_DETAILS))
2004     {
2005       fprintf (dump_file, "(dependence classified: ");
2006       print_generic_expr (dump_file, chrec, 0);
2007       fprintf (dump_file, ")\n");
2008     }
2009
2010   DDR_ARE_DEPENDENT (ddr) = chrec;  
2011   varray_clear (DDR_SUBSCRIPTS (ddr));
2012 }
2013
2014 /* The dependence relation DDR cannot be represented by a distance
2015    vector.  */
2016
2017 static inline void
2018 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2019 {
2020   if (dump_file && (dump_flags & TDF_DETAILS))
2021     fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2022
2023   DDR_AFFINE_P (ddr) = false;
2024 }
2025
2026 \f
2027
2028 /* This section contains the classic Banerjee tests.  */
2029
2030 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2031    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
2032
2033 static inline bool
2034 ziv_subscript_p (tree chrec_a, 
2035                  tree chrec_b)
2036 {
2037   return (evolution_function_is_constant_p (chrec_a)
2038           && evolution_function_is_constant_p (chrec_b));
2039 }
2040
2041 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2042    variable, i.e., if the SIV (Single Index Variable) test is true.  */
2043
2044 static bool
2045 siv_subscript_p (tree chrec_a,
2046                  tree chrec_b)
2047 {
2048   if ((evolution_function_is_constant_p (chrec_a)
2049        && evolution_function_is_univariate_p (chrec_b))
2050       || (evolution_function_is_constant_p (chrec_b)
2051           && evolution_function_is_univariate_p (chrec_a)))
2052     return true;
2053   
2054   if (evolution_function_is_univariate_p (chrec_a)
2055       && evolution_function_is_univariate_p (chrec_b))
2056     {
2057       switch (TREE_CODE (chrec_a))
2058         {
2059         case POLYNOMIAL_CHREC:
2060           switch (TREE_CODE (chrec_b))
2061             {
2062             case POLYNOMIAL_CHREC:
2063               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2064                 return false;
2065               
2066             default:
2067               return true;
2068             }
2069           
2070         default:
2071           return true;
2072         }
2073     }
2074   
2075   return false;
2076 }
2077
2078 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
2079    *OVERLAPS_B are initialized to the functions that describe the
2080    relation between the elements accessed twice by CHREC_A and
2081    CHREC_B.  For k >= 0, the following property is verified:
2082
2083    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2084
2085 static void 
2086 analyze_ziv_subscript (tree chrec_a, 
2087                        tree chrec_b, 
2088                        tree *overlaps_a,
2089                        tree *overlaps_b, 
2090                        tree *last_conflicts)
2091 {
2092   tree difference;
2093   
2094   if (dump_file && (dump_flags & TDF_DETAILS))
2095     fprintf (dump_file, "(analyze_ziv_subscript \n");
2096   
2097   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2098   
2099   switch (TREE_CODE (difference))
2100     {
2101     case INTEGER_CST:
2102       if (integer_zerop (difference))
2103         {
2104           /* The difference is equal to zero: the accessed index
2105              overlaps for each iteration in the loop.  */
2106           *overlaps_a = integer_zero_node;
2107           *overlaps_b = integer_zero_node;
2108           *last_conflicts = chrec_dont_know;
2109         }
2110       else
2111         {
2112           /* The accesses do not overlap.  */
2113           *overlaps_a = chrec_known;
2114           *overlaps_b = chrec_known;
2115           *last_conflicts = integer_zero_node;
2116         }
2117       break;
2118       
2119     default:
2120       /* We're not sure whether the indexes overlap.  For the moment, 
2121          conservatively answer "don't know".  */
2122       *overlaps_a = chrec_dont_know;
2123       *overlaps_b = chrec_dont_know;
2124       *last_conflicts = chrec_dont_know;
2125       break;
2126     }
2127   
2128   if (dump_file && (dump_flags & TDF_DETAILS))
2129     fprintf (dump_file, ")\n");
2130 }
2131
2132 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2133    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
2134    *OVERLAPS_B are initialized to the functions that describe the
2135    relation between the elements accessed twice by CHREC_A and
2136    CHREC_B.  For k >= 0, the following property is verified:
2137
2138    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2139
2140 static void
2141 analyze_siv_subscript_cst_affine (tree chrec_a, 
2142                                   tree chrec_b,
2143                                   tree *overlaps_a, 
2144                                   tree *overlaps_b, 
2145                                   tree *last_conflicts)
2146 {
2147   bool value0, value1, value2;
2148   tree difference = chrec_fold_minus 
2149     (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2150   
2151   if (!chrec_is_positive (initial_condition (difference), &value0))
2152     {
2153       *overlaps_a = chrec_dont_know;
2154       *overlaps_b = chrec_dont_know;
2155       *last_conflicts = chrec_dont_know;
2156       return;
2157     }
2158   else
2159     {
2160       if (value0 == false)
2161         {
2162           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2163             {
2164               *overlaps_a = chrec_dont_know;
2165               *overlaps_b = chrec_dont_know;      
2166               *last_conflicts = chrec_dont_know;
2167               return;
2168             }
2169           else
2170             {
2171               if (value1 == true)
2172                 {
2173                   /* Example:  
2174                      chrec_a = 12
2175                      chrec_b = {10, +, 1}
2176                   */
2177                   
2178                   if (tree_fold_divides_p 
2179                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2180                     {
2181                       *overlaps_a = integer_zero_node;
2182                       *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2183                                                  fold_build1 (ABS_EXPR,
2184                                                               integer_type_node,
2185                                                               difference),
2186                                                  CHREC_RIGHT (chrec_b));
2187                       *last_conflicts = integer_one_node;
2188                       return;
2189                     }
2190                   
2191                   /* When the step does not divides the difference, there are
2192                      no overlaps.  */
2193                   else
2194                     {
2195                       *overlaps_a = chrec_known;
2196                       *overlaps_b = chrec_known;      
2197                       *last_conflicts = integer_zero_node;
2198                       return;
2199                     }
2200                 }
2201               
2202               else
2203                 {
2204                   /* Example:  
2205                      chrec_a = 12
2206                      chrec_b = {10, +, -1}
2207                      
2208                      In this case, chrec_a will not overlap with chrec_b.  */
2209                   *overlaps_a = chrec_known;
2210                   *overlaps_b = chrec_known;
2211                   *last_conflicts = integer_zero_node;
2212                   return;
2213                 }
2214             }
2215         }
2216       else 
2217         {
2218           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2219             {
2220               *overlaps_a = chrec_dont_know;
2221               *overlaps_b = chrec_dont_know;      
2222               *last_conflicts = chrec_dont_know;
2223               return;
2224             }
2225           else
2226             {
2227               if (value2 == false)
2228                 {
2229                   /* Example:  
2230                      chrec_a = 3
2231                      chrec_b = {10, +, -1}
2232                   */
2233                   if (tree_fold_divides_p 
2234                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2235                     {
2236                       *overlaps_a = integer_zero_node;
2237                       *overlaps_b = fold 
2238                         (build (EXACT_DIV_EXPR, integer_type_node, difference, 
2239                                 CHREC_RIGHT (chrec_b)));
2240                       *last_conflicts = integer_one_node;
2241                       return;
2242                     }
2243                   
2244                   /* When the step does not divides the difference, there
2245                      are no overlaps.  */
2246                   else
2247                     {
2248                       *overlaps_a = chrec_known;
2249                       *overlaps_b = chrec_known;      
2250                       *last_conflicts = integer_zero_node;
2251                       return;
2252                     }
2253                 }
2254               else
2255                 {
2256                   /* Example:  
2257                      chrec_a = 3  
2258                      chrec_b = {4, +, 1}
2259                  
2260                      In this case, chrec_a will not overlap with chrec_b.  */
2261                   *overlaps_a = chrec_known;
2262                   *overlaps_b = chrec_known;
2263                   *last_conflicts = integer_zero_node;
2264                   return;
2265                 }
2266             }
2267         }
2268     }
2269 }
2270
2271 /* Helper recursive function for initializing the matrix A.  Returns
2272    the initial value of CHREC.  */
2273
2274 static int
2275 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2276 {
2277   gcc_assert (chrec);
2278
2279   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2280     return int_cst_value (chrec);
2281
2282   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2283   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2284 }
2285
2286 #define FLOOR_DIV(x,y) ((x) / (y))
2287
2288 /* Solves the special case of the Diophantine equation: 
2289    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2290
2291    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
2292    number of iterations that loops X and Y run.  The overlaps will be
2293    constructed as evolutions in dimension DIM.  */
2294
2295 static void
2296 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, 
2297                                          tree *overlaps_a, tree *overlaps_b, 
2298                                          tree *last_conflicts, int dim)
2299 {
2300   if (((step_a > 0 && step_b > 0)
2301        || (step_a < 0 && step_b < 0)))
2302     {
2303       int step_overlaps_a, step_overlaps_b;
2304       int gcd_steps_a_b, last_conflict, tau2;
2305
2306       gcd_steps_a_b = gcd (step_a, step_b);
2307       step_overlaps_a = step_b / gcd_steps_a_b;
2308       step_overlaps_b = step_a / gcd_steps_a_b;
2309
2310       tau2 = FLOOR_DIV (niter, step_overlaps_a);
2311       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2312       last_conflict = tau2;
2313
2314       *overlaps_a = build_polynomial_chrec
2315         (dim, integer_zero_node,
2316          build_int_cst (NULL_TREE, step_overlaps_a));
2317       *overlaps_b = build_polynomial_chrec
2318         (dim, integer_zero_node,
2319          build_int_cst (NULL_TREE, step_overlaps_b));
2320       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2321     }
2322
2323   else
2324     {
2325       *overlaps_a = integer_zero_node;
2326       *overlaps_b = integer_zero_node;
2327       *last_conflicts = integer_zero_node;
2328     }
2329 }
2330
2331
2332 /* Solves the special case of a Diophantine equation where CHREC_A is
2333    an affine bivariate function, and CHREC_B is an affine univariate
2334    function.  For example, 
2335
2336    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2337    
2338    has the following overlapping functions: 
2339
2340    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2341    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2342    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2343
2344    FORNOW: This is a specialized implementation for a case occurring in
2345    a common benchmark.  Implement the general algorithm.  */
2346
2347 static void
2348 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 
2349                                       tree *overlaps_a, tree *overlaps_b, 
2350                                       tree *last_conflicts)
2351 {
2352   bool xz_p, yz_p, xyz_p;
2353   int step_x, step_y, step_z;
2354   int niter_x, niter_y, niter_z, niter;
2355   tree numiter_x, numiter_y, numiter_z;
2356   tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2357   tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2358   tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2359
2360   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2361   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2362   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2363
2364   numiter_x = number_of_iterations_in_loop 
2365     (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
2366   numiter_y = number_of_iterations_in_loop 
2367     (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2368   numiter_z = number_of_iterations_in_loop 
2369     (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2370
2371   if (TREE_CODE (numiter_x) != INTEGER_CST)
2372     numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
2373       ->estimated_nb_iterations;
2374   if (TREE_CODE (numiter_y) != INTEGER_CST)
2375     numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2376       ->estimated_nb_iterations;
2377   if (TREE_CODE (numiter_z) != INTEGER_CST)
2378     numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2379       ->estimated_nb_iterations;
2380
2381   if (chrec_contains_undetermined (numiter_x)
2382       || chrec_contains_undetermined (numiter_y)
2383       || chrec_contains_undetermined (numiter_z)
2384       || TREE_CODE (numiter_x) != INTEGER_CST
2385       || TREE_CODE (numiter_y) != INTEGER_CST
2386       || TREE_CODE (numiter_z) != INTEGER_CST)
2387     {
2388       *overlaps_a = chrec_dont_know;
2389       *overlaps_b = chrec_dont_know;
2390       *last_conflicts = chrec_dont_know;
2391       return;
2392     }
2393
2394   niter_x = int_cst_value (numiter_x);
2395   niter_y = int_cst_value (numiter_y);
2396   niter_z = int_cst_value (numiter_z);
2397
2398   niter = MIN (niter_x, niter_z);
2399   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2400                                            &overlaps_a_xz,
2401                                            &overlaps_b_xz,
2402                                            &last_conflicts_xz, 1);
2403   niter = MIN (niter_y, niter_z);
2404   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2405                                            &overlaps_a_yz,
2406                                            &overlaps_b_yz,
2407                                            &last_conflicts_yz, 2);
2408   niter = MIN (niter_x, niter_z);
2409   niter = MIN (niter_y, niter);
2410   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2411                                            &overlaps_a_xyz,
2412                                            &overlaps_b_xyz,
2413                                            &last_conflicts_xyz, 3);
2414
2415   xz_p = !integer_zerop (last_conflicts_xz);
2416   yz_p = !integer_zerop (last_conflicts_yz);
2417   xyz_p = !integer_zerop (last_conflicts_xyz);
2418
2419   if (xz_p || yz_p || xyz_p)
2420     {
2421       *overlaps_a = make_tree_vec (2);
2422       TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2423       TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2424       *overlaps_b = integer_zero_node;
2425       if (xz_p)
2426         {
2427           TREE_VEC_ELT (*overlaps_a, 0) = 
2428             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2429                              overlaps_a_xz);
2430           *overlaps_b = 
2431             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2432           *last_conflicts = last_conflicts_xz;
2433         }
2434       if (yz_p)
2435         {
2436           TREE_VEC_ELT (*overlaps_a, 1) = 
2437             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2438                              overlaps_a_yz);
2439           *overlaps_b = 
2440             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2441           *last_conflicts = last_conflicts_yz;
2442         }
2443       if (xyz_p)
2444         {
2445           TREE_VEC_ELT (*overlaps_a, 0) = 
2446             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2447                              overlaps_a_xyz);
2448           TREE_VEC_ELT (*overlaps_a, 1) = 
2449             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2450                              overlaps_a_xyz);
2451           *overlaps_b = 
2452             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2453           *last_conflicts = last_conflicts_xyz;
2454         }
2455     }
2456   else
2457     {
2458       *overlaps_a = integer_zero_node;
2459       *overlaps_b = integer_zero_node;
2460       *last_conflicts = integer_zero_node;
2461     }
2462 }
2463
2464 /* Determines the overlapping elements due to accesses CHREC_A and
2465    CHREC_B, that are affine functions.  This is a part of the
2466    subscript analyzer.  */
2467
2468 static void
2469 analyze_subscript_affine_affine (tree chrec_a, 
2470                                  tree chrec_b,
2471                                  tree *overlaps_a, 
2472                                  tree *overlaps_b, 
2473                                  tree *last_conflicts)
2474 {
2475   unsigned nb_vars_a, nb_vars_b, dim;
2476   int init_a, init_b, gamma, gcd_alpha_beta;
2477   int tau1, tau2;
2478   lambda_matrix A, U, S;
2479
2480   if (dump_file && (dump_flags & TDF_DETAILS))
2481     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2482   
2483   /* For determining the initial intersection, we have to solve a
2484      Diophantine equation.  This is the most time consuming part.
2485      
2486      For answering to the question: "Is there a dependence?" we have
2487      to prove that there exists a solution to the Diophantine
2488      equation, and that the solution is in the iteration domain,
2489      i.e. the solution is positive or zero, and that the solution
2490      happens before the upper bound loop.nb_iterations.  Otherwise
2491      there is no dependence.  This function outputs a description of
2492      the iterations that hold the intersections.  */
2493
2494   
2495   nb_vars_a = nb_vars_in_chrec (chrec_a);
2496   nb_vars_b = nb_vars_in_chrec (chrec_b);
2497
2498   dim = nb_vars_a + nb_vars_b;
2499   U = lambda_matrix_new (dim, dim);
2500   A = lambda_matrix_new (dim, 1);
2501   S = lambda_matrix_new (dim, 1);
2502
2503   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2504   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2505   gamma = init_b - init_a;
2506
2507   /* Don't do all the hard work of solving the Diophantine equation
2508      when we already know the solution: for example, 
2509      | {3, +, 1}_1
2510      | {3, +, 4}_2
2511      | gamma = 3 - 3 = 0.
2512      Then the first overlap occurs during the first iterations: 
2513      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2514   */
2515   if (gamma == 0)
2516     {
2517       if (nb_vars_a == 1 && nb_vars_b == 1)
2518         {
2519           int step_a, step_b;
2520           int niter, niter_a, niter_b;
2521           tree numiter_a, numiter_b;
2522
2523           numiter_a = number_of_iterations_in_loop 
2524             (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2525           numiter_b = number_of_iterations_in_loop 
2526             (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2527
2528           if (TREE_CODE (numiter_a) != INTEGER_CST)
2529             numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2530               ->estimated_nb_iterations;
2531           if (TREE_CODE (numiter_b) != INTEGER_CST)
2532             numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2533               ->estimated_nb_iterations;
2534           if (chrec_contains_undetermined (numiter_a)
2535               || chrec_contains_undetermined (numiter_b)
2536               || TREE_CODE (numiter_a) != INTEGER_CST
2537               || TREE_CODE (numiter_b) != INTEGER_CST)
2538             {
2539               *overlaps_a = chrec_dont_know;
2540               *overlaps_b = chrec_dont_know;
2541               *last_conflicts = chrec_dont_know;
2542               return;
2543             }
2544
2545           niter_a = int_cst_value (numiter_a);
2546           niter_b = int_cst_value (numiter_b);
2547           niter = MIN (niter_a, niter_b);
2548
2549           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2550           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2551
2552           compute_overlap_steps_for_affine_univar (niter, step_a, step_b, 
2553                                                    overlaps_a, overlaps_b, 
2554                                                    last_conflicts, 1);
2555         }
2556
2557       else if (nb_vars_a == 2 && nb_vars_b == 1)
2558         compute_overlap_steps_for_affine_1_2
2559           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2560
2561       else if (nb_vars_a == 1 && nb_vars_b == 2)
2562         compute_overlap_steps_for_affine_1_2
2563           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2564
2565       else
2566         {
2567           *overlaps_a = chrec_dont_know;
2568           *overlaps_b = chrec_dont_know;
2569           *last_conflicts = chrec_dont_know;
2570         }
2571       return;
2572     }
2573
2574   /* U.A = S */
2575   lambda_matrix_right_hermite (A, dim, 1, S, U);
2576
2577   if (S[0][0] < 0)
2578     {
2579       S[0][0] *= -1;
2580       lambda_matrix_row_negate (U, dim, 0);
2581     }
2582   gcd_alpha_beta = S[0][0];
2583
2584   /* The classic "gcd-test".  */
2585   if (!int_divides_p (gcd_alpha_beta, gamma))
2586     {
2587       /* The "gcd-test" has determined that there is no integer
2588          solution, i.e. there is no dependence.  */
2589       *overlaps_a = chrec_known;
2590       *overlaps_b = chrec_known;
2591       *last_conflicts = integer_zero_node;
2592     }
2593
2594   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
2595   else if (nb_vars_a == 1 && nb_vars_b == 1)
2596     {
2597       /* Both functions should have the same evolution sign.  */
2598       if (((A[0][0] > 0 && -A[1][0] > 0)
2599            || (A[0][0] < 0 && -A[1][0] < 0)))
2600         {
2601           /* The solutions are given by:
2602              | 
2603              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
2604              |                           [u21 u22]    [y0]
2605          
2606              For a given integer t.  Using the following variables,
2607          
2608              | i0 = u11 * gamma / gcd_alpha_beta
2609              | j0 = u12 * gamma / gcd_alpha_beta
2610              | i1 = u21
2611              | j1 = u22
2612          
2613              the solutions are:
2614          
2615              | x0 = i0 + i1 * t, 
2616              | y0 = j0 + j1 * t.  */
2617       
2618           int i0, j0, i1, j1;
2619
2620           /* X0 and Y0 are the first iterations for which there is a
2621              dependence.  X0, Y0 are two solutions of the Diophantine
2622              equation: chrec_a (X0) = chrec_b (Y0).  */
2623           int x0, y0;
2624           int niter, niter_a, niter_b;
2625           tree numiter_a, numiter_b;
2626
2627           numiter_a = number_of_iterations_in_loop 
2628             (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2629           numiter_b = number_of_iterations_in_loop 
2630             (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2631
2632           if (TREE_CODE (numiter_a) != INTEGER_CST)
2633             numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2634               ->estimated_nb_iterations;
2635           if (TREE_CODE (numiter_b) != INTEGER_CST)
2636             numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2637               ->estimated_nb_iterations;
2638           if (chrec_contains_undetermined (numiter_a)
2639               || chrec_contains_undetermined (numiter_b)
2640               || TREE_CODE (numiter_a) != INTEGER_CST
2641               || TREE_CODE (numiter_b) != INTEGER_CST)
2642             {
2643               *overlaps_a = chrec_dont_know;
2644               *overlaps_b = chrec_dont_know;
2645               *last_conflicts = chrec_dont_know;
2646               return;
2647             }
2648
2649           niter_a = int_cst_value (numiter_a);
2650           niter_b = int_cst_value (numiter_b);
2651           niter = MIN (niter_a, niter_b);
2652
2653           i0 = U[0][0] * gamma / gcd_alpha_beta;
2654           j0 = U[0][1] * gamma / gcd_alpha_beta;
2655           i1 = U[1][0];
2656           j1 = U[1][1];
2657
2658           if ((i1 == 0 && i0 < 0)
2659               || (j1 == 0 && j0 < 0))
2660             {
2661               /* There is no solution.  
2662                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 
2663                  falls in here, but for the moment we don't look at the 
2664                  upper bound of the iteration domain.  */
2665               *overlaps_a = chrec_known;
2666               *overlaps_b = chrec_known;
2667               *last_conflicts = integer_zero_node;
2668             }
2669
2670           else 
2671             {
2672               if (i1 > 0)
2673                 {
2674                   tau1 = CEIL (-i0, i1);
2675                   tau2 = FLOOR_DIV (niter - i0, i1);
2676
2677                   if (j1 > 0)
2678                     {
2679                       int last_conflict, min_multiple;
2680                       tau1 = MAX (tau1, CEIL (-j0, j1));
2681                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2682
2683                       x0 = i1 * tau1 + i0;
2684                       y0 = j1 * tau1 + j0;
2685
2686                       /* At this point (x0, y0) is one of the
2687                          solutions to the Diophantine equation.  The
2688                          next step has to compute the smallest
2689                          positive solution: the first conflicts.  */
2690                       min_multiple = MIN (x0 / i1, y0 / j1);
2691                       x0 -= i1 * min_multiple;
2692                       y0 -= j1 * min_multiple;
2693
2694                       tau1 = (x0 - i0)/i1;
2695                       last_conflict = tau2 - tau1;
2696
2697                       *overlaps_a = build_polynomial_chrec
2698                         (1,
2699                          build_int_cst (NULL_TREE, x0),
2700                          build_int_cst (NULL_TREE, i1));
2701                       *overlaps_b = build_polynomial_chrec
2702                         (1,
2703                          build_int_cst (NULL_TREE, y0),
2704                          build_int_cst (NULL_TREE, j1));
2705                       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2706                     }
2707                   else
2708                     {
2709                       /* FIXME: For the moment, the upper bound of the
2710                          iteration domain for j is not checked.  */
2711                       *overlaps_a = chrec_dont_know;
2712                       *overlaps_b = chrec_dont_know;
2713                       *last_conflicts = chrec_dont_know;
2714                     }
2715                 }
2716           
2717               else
2718                 {
2719                   /* FIXME: For the moment, the upper bound of the
2720                      iteration domain for i is not checked.  */
2721                   *overlaps_a = chrec_dont_know;
2722                   *overlaps_b = chrec_dont_know;
2723                   *last_conflicts = chrec_dont_know;
2724                 }
2725             }
2726         }
2727       else
2728         {
2729           *overlaps_a = chrec_dont_know;
2730           *overlaps_b = chrec_dont_know;
2731           *last_conflicts = chrec_dont_know;
2732         }
2733     }
2734
2735   else
2736     {
2737       *overlaps_a = chrec_dont_know;
2738       *overlaps_b = chrec_dont_know;
2739       *last_conflicts = chrec_dont_know;
2740     }
2741
2742
2743   if (dump_file && (dump_flags & TDF_DETAILS))
2744     {
2745       fprintf (dump_file, "  (overlaps_a = ");
2746       print_generic_expr (dump_file, *overlaps_a, 0);
2747       fprintf (dump_file, ")\n  (overlaps_b = ");
2748       print_generic_expr (dump_file, *overlaps_b, 0);
2749       fprintf (dump_file, ")\n");
2750     }
2751   
2752   if (dump_file && (dump_flags & TDF_DETAILS))
2753     fprintf (dump_file, ")\n");
2754 }
2755
2756 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
2757    *OVERLAPS_B are initialized to the functions that describe the
2758    relation between the elements accessed twice by CHREC_A and
2759    CHREC_B.  For k >= 0, the following property is verified:
2760
2761    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2762
2763 static void
2764 analyze_siv_subscript (tree chrec_a, 
2765                        tree chrec_b,
2766                        tree *overlaps_a, 
2767                        tree *overlaps_b, 
2768                        tree *last_conflicts)
2769 {
2770   if (dump_file && (dump_flags & TDF_DETAILS))
2771     fprintf (dump_file, "(analyze_siv_subscript \n");
2772   
2773   if (evolution_function_is_constant_p (chrec_a)
2774       && evolution_function_is_affine_p (chrec_b))
2775     analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 
2776                                       overlaps_a, overlaps_b, last_conflicts);
2777   
2778   else if (evolution_function_is_affine_p (chrec_a)
2779            && evolution_function_is_constant_p (chrec_b))
2780     analyze_siv_subscript_cst_affine (chrec_b, chrec_a, 
2781                                       overlaps_b, overlaps_a, last_conflicts);
2782   
2783   else if (evolution_function_is_affine_p (chrec_a)
2784            && evolution_function_is_affine_p (chrec_b))
2785     analyze_subscript_affine_affine (chrec_a, chrec_b, 
2786                                      overlaps_a, overlaps_b, last_conflicts);
2787   else
2788     {
2789       *overlaps_a = chrec_dont_know;
2790       *overlaps_b = chrec_dont_know;
2791       *last_conflicts = chrec_dont_know;
2792     }
2793   
2794   if (dump_file && (dump_flags & TDF_DETAILS))
2795     fprintf (dump_file, ")\n");
2796 }
2797
2798 /* Return true when the evolution steps of an affine CHREC divide the
2799    constant CST.  */
2800
2801 static bool
2802 chrec_steps_divide_constant_p (tree chrec, 
2803                                tree cst)
2804 {
2805   switch (TREE_CODE (chrec))
2806     {
2807     case POLYNOMIAL_CHREC:
2808       return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
2809               && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
2810       
2811     default:
2812       /* On the initial condition, return true.  */
2813       return true;
2814     }
2815 }
2816
2817 /* Analyze a MIV (Multiple Index Variable) subscript.  *OVERLAPS_A and
2818    *OVERLAPS_B are initialized to the functions that describe the
2819    relation between the elements accessed twice by CHREC_A and
2820    CHREC_B.  For k >= 0, the following property is verified:
2821
2822    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2823
2824 static void
2825 analyze_miv_subscript (tree chrec_a, 
2826                        tree chrec_b, 
2827                        tree *overlaps_a, 
2828                        tree *overlaps_b, 
2829                        tree *last_conflicts)
2830 {
2831   /* FIXME:  This is a MIV subscript, not yet handled.
2832      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from 
2833      (A[i] vs. A[j]).  
2834      
2835      In the SIV test we had to solve a Diophantine equation with two
2836      variables.  In the MIV case we have to solve a Diophantine
2837      equation with 2*n variables (if the subscript uses n IVs).
2838   */
2839   tree difference;
2840   
2841   if (dump_file && (dump_flags & TDF_DETAILS))
2842     fprintf (dump_file, "(analyze_miv_subscript \n");
2843   
2844   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2845   
2846   if (chrec_zerop (difference))
2847     {
2848       /* Access functions are the same: all the elements are accessed
2849          in the same order.  */
2850       *overlaps_a = integer_zero_node;
2851       *overlaps_b = integer_zero_node;
2852       *last_conflicts = number_of_iterations_in_loop 
2853         (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2854     }
2855   
2856   else if (evolution_function_is_constant_p (difference)
2857            /* For the moment, the following is verified:
2858               evolution_function_is_affine_multivariate_p (chrec_a) */
2859            && !chrec_steps_divide_constant_p (chrec_a, difference))
2860     {
2861       /* testsuite/.../ssa-chrec-33.c
2862          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2 
2863         
2864          The difference is 1, and the evolution steps are equal to 2,
2865          consequently there are no overlapping elements.  */
2866       *overlaps_a = chrec_known;
2867       *overlaps_b = chrec_known;
2868       *last_conflicts = integer_zero_node;
2869     }
2870   
2871   else if (evolution_function_is_affine_multivariate_p (chrec_a)
2872            && evolution_function_is_affine_multivariate_p (chrec_b))
2873     {
2874       /* testsuite/.../ssa-chrec-35.c
2875          {0, +, 1}_2  vs.  {0, +, 1}_3
2876          the overlapping elements are respectively located at iterations:
2877          {0, +, 1}_x and {0, +, 1}_x, 
2878          in other words, we have the equality: 
2879          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2880          
2881          Other examples: 
2882          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = 
2883          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2884
2885          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = 
2886          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2887       */
2888       analyze_subscript_affine_affine (chrec_a, chrec_b, 
2889                                        overlaps_a, overlaps_b, last_conflicts);
2890     }
2891   
2892   else
2893     {
2894       /* When the analysis is too difficult, answer "don't know".  */
2895       *overlaps_a = chrec_dont_know;
2896       *overlaps_b = chrec_dont_know;
2897       *last_conflicts = chrec_dont_know;
2898     }
2899   
2900   if (dump_file && (dump_flags & TDF_DETAILS))
2901     fprintf (dump_file, ")\n");
2902 }
2903
2904 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2905    OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2906    two functions that describe the iterations that contain conflicting
2907    elements.
2908    
2909    Remark: For an integer k >= 0, the following equality is true:
2910    
2911    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2912 */
2913
2914 static void 
2915 analyze_overlapping_iterations (tree chrec_a, 
2916                                 tree chrec_b, 
2917                                 tree *overlap_iterations_a, 
2918                                 tree *overlap_iterations_b, 
2919                                 tree *last_conflicts)
2920 {
2921   if (dump_file && (dump_flags & TDF_DETAILS))
2922     {
2923       fprintf (dump_file, "(analyze_overlapping_iterations \n");
2924       fprintf (dump_file, "  (chrec_a = ");
2925       print_generic_expr (dump_file, chrec_a, 0);
2926       fprintf (dump_file, ")\n  chrec_b = ");
2927       print_generic_expr (dump_file, chrec_b, 0);
2928       fprintf (dump_file, ")\n");
2929     }
2930   
2931   if (chrec_a == NULL_TREE
2932       || chrec_b == NULL_TREE
2933       || chrec_contains_undetermined (chrec_a)
2934       || chrec_contains_undetermined (chrec_b)
2935       || chrec_contains_symbols (chrec_a)
2936       || chrec_contains_symbols (chrec_b))
2937     {
2938       *overlap_iterations_a = chrec_dont_know;
2939       *overlap_iterations_b = chrec_dont_know;
2940     }
2941   
2942   else if (ziv_subscript_p (chrec_a, chrec_b))
2943     analyze_ziv_subscript (chrec_a, chrec_b, 
2944                            overlap_iterations_a, overlap_iterations_b,
2945                            last_conflicts);
2946   
2947   else if (siv_subscript_p (chrec_a, chrec_b))
2948     analyze_siv_subscript (chrec_a, chrec_b, 
2949                            overlap_iterations_a, overlap_iterations_b, 
2950                            last_conflicts);
2951   
2952   else
2953     analyze_miv_subscript (chrec_a, chrec_b, 
2954                            overlap_iterations_a, overlap_iterations_b,
2955                            last_conflicts);
2956   
2957   if (dump_file && (dump_flags & TDF_DETAILS))
2958     {
2959       fprintf (dump_file, "  (overlap_iterations_a = ");
2960       print_generic_expr (dump_file, *overlap_iterations_a, 0);
2961       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
2962       print_generic_expr (dump_file, *overlap_iterations_b, 0);
2963       fprintf (dump_file, ")\n");
2964     }
2965 }
2966
2967 \f
2968
2969 /* This section contains the affine functions dependences detector.  */
2970
2971 /* Computes the conflicting iterations, and initialize DDR.  */
2972
2973 static void
2974 subscript_dependence_tester (struct data_dependence_relation *ddr)
2975 {
2976   unsigned int i;
2977   struct data_reference *dra = DDR_A (ddr);
2978   struct data_reference *drb = DDR_B (ddr);
2979   tree last_conflicts;
2980   
2981   if (dump_file && (dump_flags & TDF_DETAILS))
2982     fprintf (dump_file, "(subscript_dependence_tester \n");
2983   
2984   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2985     {
2986       tree overlaps_a, overlaps_b;
2987       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2988       
2989       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 
2990                                       DR_ACCESS_FN (drb, i),
2991                                       &overlaps_a, &overlaps_b, 
2992                                       &last_conflicts);
2993       
2994       if (chrec_contains_undetermined (overlaps_a)
2995           || chrec_contains_undetermined (overlaps_b))
2996         {
2997           finalize_ddr_dependent (ddr, chrec_dont_know);
2998           break;
2999         }
3000       
3001       else if (overlaps_a == chrec_known
3002                || overlaps_b == chrec_known)
3003         {
3004           finalize_ddr_dependent (ddr, chrec_known);
3005           break;
3006         }
3007       
3008       else
3009         {
3010           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3011           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3012           SUB_LAST_CONFLICT (subscript) = last_conflicts;
3013         }
3014     }
3015   
3016   if (dump_file && (dump_flags & TDF_DETAILS))
3017     fprintf (dump_file, ")\n");
3018 }
3019
3020 /* Compute the classic per loop distance vector.
3021
3022    DDR is the data dependence relation to build a vector from.
3023    NB_LOOPS is the total number of loops we are considering.
3024    FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3025    loop nest.  
3026    Return FALSE if the dependence relation is outside of the loop nest
3027    starting at FIRST_LOOP_DEPTH. 
3028    Return TRUE otherwise.  */
3029
3030 static bool
3031 build_classic_dist_vector (struct data_dependence_relation *ddr, 
3032                            int nb_loops, int first_loop_depth)
3033 {
3034   unsigned i;
3035   lambda_vector dist_v, init_v;
3036   
3037   dist_v = lambda_vector_new (nb_loops);
3038   init_v = lambda_vector_new (nb_loops);
3039   lambda_vector_clear (dist_v, nb_loops);
3040   lambda_vector_clear (init_v, nb_loops);
3041   
3042   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3043     return true;
3044   
3045   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3046     {
3047       tree access_fn_a, access_fn_b;
3048       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3049
3050       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3051         {
3052           non_affine_dependence_relation (ddr);
3053           return true;
3054         }
3055
3056       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3057       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3058
3059       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC 
3060           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3061         {
3062           int dist, loop_nb, loop_depth;
3063           int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3064           int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3065           struct loop *loop_a = current_loops->parray[loop_nb_a];
3066           struct loop *loop_b = current_loops->parray[loop_nb_b];
3067
3068           /* If the loop for either variable is at a lower depth than 
3069              the first_loop's depth, then we can't possibly have a
3070              dependency at this level of the loop.  */
3071              
3072           if (loop_a->depth < first_loop_depth
3073               || loop_b->depth < first_loop_depth)
3074             return false;
3075
3076           if (loop_nb_a != loop_nb_b
3077               && !flow_loop_nested_p (loop_a, loop_b)
3078               && !flow_loop_nested_p (loop_b, loop_a))
3079             {
3080               /* Example: when there are two consecutive loops,
3081
3082                  | loop_1
3083                  |   A[{0, +, 1}_1]
3084                  | endloop_1
3085                  | loop_2
3086                  |   A[{0, +, 1}_2]
3087                  | endloop_2
3088
3089                  the dependence relation cannot be captured by the
3090                  distance abstraction.  */
3091               non_affine_dependence_relation (ddr);
3092               return true;
3093             }
3094
3095           /* The dependence is carried by the outermost loop.  Example:
3096              | loop_1
3097              |   A[{4, +, 1}_1]
3098              |   loop_2
3099              |     A[{5, +, 1}_2]
3100              |   endloop_2
3101              | endloop_1
3102              In this case, the dependence is carried by loop_1.  */
3103           loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3104           loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3105
3106           /* If the loop number is still greater than the number of
3107              loops we've been asked to analyze, or negative,
3108              something is borked.  */
3109           gcc_assert (loop_depth >= 0);
3110           gcc_assert (loop_depth < nb_loops);
3111           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3112             {
3113               non_affine_dependence_relation (ddr);
3114               return true;
3115             }
3116           
3117           dist = int_cst_value (SUB_DISTANCE (subscript));
3118
3119           /* This is the subscript coupling test.  
3120              | loop i = 0, N, 1
3121              |   T[i+1][i] = ...
3122              |   ... = T[i][i]
3123              | endloop
3124              There is no dependence.  */
3125           if (init_v[loop_depth] != 0
3126               && dist_v[loop_depth] != dist)
3127             {
3128               finalize_ddr_dependent (ddr, chrec_known);
3129               return true;
3130             }
3131
3132           dist_v[loop_depth] = dist;
3133           init_v[loop_depth] = 1;
3134         }
3135     }
3136   
3137   /* There is a distance of 1 on all the outer loops: 
3138      
3139      Example: there is a dependence of distance 1 on loop_1 for the array A.
3140      | loop_1
3141      |   A[5] = ...
3142      | endloop
3143   */
3144   {
3145     struct loop *lca, *loop_a, *loop_b;
3146     struct data_reference *a = DDR_A (ddr);
3147     struct data_reference *b = DDR_B (ddr);
3148     int lca_depth;
3149     loop_a = loop_containing_stmt (DR_STMT (a));
3150     loop_b = loop_containing_stmt (DR_STMT (b));
3151     
3152     /* Get the common ancestor loop.  */
3153     lca = find_common_loop (loop_a, loop_b); 
3154     
3155     lca_depth = lca->depth;
3156     lca_depth -= first_loop_depth;
3157     gcc_assert (lca_depth >= 0);
3158     gcc_assert (lca_depth < nb_loops);
3159
3160     /* For each outer loop where init_v is not set, the accesses are
3161        in dependence of distance 1 in the loop.  */
3162     if (lca != loop_a
3163         && lca != loop_b
3164         && init_v[lca_depth] == 0)
3165       dist_v[lca_depth] = 1;
3166     
3167     lca = lca->outer;
3168     
3169     if (lca)
3170       {
3171         lca_depth = lca->depth - first_loop_depth;
3172         while (lca->depth != 0)
3173           {
3174             /* If we're considering just a sub-nest, then don't record
3175                any information on the outer loops.  */
3176             if (lca_depth < 0)
3177               break;
3178
3179             gcc_assert (lca_depth < nb_loops);
3180
3181             if (init_v[lca_depth] == 0)
3182               dist_v[lca_depth] = 1;
3183             lca = lca->outer;
3184             lca_depth = lca->depth - first_loop_depth;
3185           
3186           }
3187       }
3188   }
3189   
3190   DDR_DIST_VECT (ddr) = dist_v;
3191   DDR_SIZE_VECT (ddr) = nb_loops;
3192   return true;
3193 }
3194
3195 /* Compute the classic per loop direction vector.  
3196
3197    DDR is the data dependence relation to build a vector from.
3198    NB_LOOPS is the total number of loops we are considering.
3199    FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed 
3200    loop nest.
3201    Return FALSE if the dependence relation is outside of the loop nest
3202    at FIRST_LOOP_DEPTH. 
3203    Return TRUE otherwise.  */
3204
3205 static bool
3206 build_classic_dir_vector (struct data_dependence_relation *ddr, 
3207                           int nb_loops, int first_loop_depth)
3208 {
3209   unsigned i;
3210   lambda_vector dir_v, init_v;
3211   
3212   dir_v = lambda_vector_new (nb_loops);
3213   init_v = lambda_vector_new (nb_loops);
3214   lambda_vector_clear (dir_v, nb_loops);
3215   lambda_vector_clear (init_v, nb_loops);
3216   
3217   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3218     return true;
3219   
3220   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3221     {
3222       tree access_fn_a, access_fn_b;
3223       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3224
3225       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3226         {
3227           non_affine_dependence_relation (ddr);
3228           return true;
3229         }
3230
3231       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3232       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3233       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3234           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3235         {
3236           int dist, loop_nb, loop_depth;
3237           enum data_dependence_direction dir = dir_star;
3238           int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3239           int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3240           struct loop *loop_a = current_loops->parray[loop_nb_a];
3241           struct loop *loop_b = current_loops->parray[loop_nb_b];
3242  
3243           /* If the loop for either variable is at a lower depth than 
3244              the first_loop's depth, then we can't possibly have a
3245              dependency at this level of the loop.  */
3246              
3247           if (loop_a->depth < first_loop_depth
3248               || loop_b->depth < first_loop_depth)
3249             return false;
3250
3251           if (loop_nb_a != loop_nb_b
3252               && !flow_loop_nested_p (loop_a, loop_b)
3253               && !flow_loop_nested_p (loop_b, loop_a))
3254             {
3255               /* Example: when there are two consecutive loops,
3256
3257                  | loop_1
3258                  |   A[{0, +, 1}_1]
3259                  | endloop_1
3260                  | loop_2
3261                  |   A[{0, +, 1}_2]
3262                  | endloop_2
3263
3264                  the dependence relation cannot be captured by the
3265                  distance abstraction.  */
3266               non_affine_dependence_relation (ddr);
3267               return true;
3268             }
3269
3270           /* The dependence is carried by the outermost loop.  Example:
3271              | loop_1
3272              |   A[{4, +, 1}_1]
3273              |   loop_2
3274              |     A[{5, +, 1}_2]
3275              |   endloop_2
3276              | endloop_1
3277              In this case, the dependence is carried by loop_1.  */
3278           loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3279           loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3280
3281           /* If the loop number is still greater than the number of
3282              loops we've been asked to analyze, or negative,
3283              something is borked.  */
3284           gcc_assert (loop_depth >= 0);
3285           gcc_assert (loop_depth < nb_loops);
3286
3287           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3288             {
3289               non_affine_dependence_relation (ddr);
3290               return true;
3291             }
3292
3293           dist = int_cst_value (SUB_DISTANCE (subscript));
3294
3295           if (dist == 0)
3296             dir = dir_equal;
3297           else if (dist > 0)
3298             dir = dir_positive;
3299           else if (dist < 0)
3300             dir = dir_negative;
3301           
3302           /* This is the subscript coupling test.  
3303              | loop i = 0, N, 1
3304              |   T[i+1][i] = ...
3305              |   ... = T[i][i]
3306              | endloop
3307              There is no dependence.  */
3308           if (init_v[loop_depth] != 0
3309               && dir != dir_star
3310               && (enum data_dependence_direction) dir_v[loop_depth] != dir
3311               && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
3312             {
3313               finalize_ddr_dependent (ddr, chrec_known);
3314               return true;
3315             }
3316           
3317           dir_v[loop_depth] = dir;
3318           init_v[loop_depth] = 1;
3319         }
3320     }
3321   
3322   /* There is a distance of 1 on all the outer loops: 
3323      
3324      Example: there is a dependence of distance 1 on loop_1 for the array A.
3325      | loop_1
3326      |   A[5] = ...
3327      | endloop
3328   */
3329   {
3330     struct loop *lca, *loop_a, *loop_b;
3331     struct data_reference *a = DDR_A (ddr);
3332     struct data_reference *b = DDR_B (ddr);
3333     int lca_depth;
3334     loop_a = loop_containing_stmt (DR_STMT (a));
3335     loop_b = loop_containing_stmt (DR_STMT (b));
3336     
3337     /* Get the common ancestor loop.  */
3338     lca = find_common_loop (loop_a, loop_b); 
3339     lca_depth = lca->depth - first_loop_depth;
3340
3341     gcc_assert (lca_depth >= 0);
3342     gcc_assert (lca_depth < nb_loops);
3343
3344     /* For each outer loop where init_v is not set, the accesses are
3345        in dependence of distance 1 in the loop.  */
3346     if (lca != loop_a
3347         && lca != loop_b
3348         && init_v[lca_depth] == 0)
3349       dir_v[lca_depth] = dir_positive;
3350     
3351     lca = lca->outer;
3352     if (lca)
3353       {
3354         lca_depth = lca->depth - first_loop_depth;
3355         while (lca->depth != 0)
3356           {
3357             /* If we're considering just a sub-nest, then don't record
3358                any information on the outer loops.  */
3359             if (lca_depth < 0)
3360               break;
3361
3362             gcc_assert (lca_depth < nb_loops);
3363
3364             if (init_v[lca_depth] == 0)
3365               dir_v[lca_depth] = dir_positive;
3366             lca = lca->outer;
3367             lca_depth = lca->depth - first_loop_depth;
3368            
3369           }
3370       }
3371   }
3372   
3373   DDR_DIR_VECT (ddr) = dir_v;
3374   DDR_SIZE_VECT (ddr) = nb_loops;
3375   return true;
3376 }
3377
3378 /* Returns true when all the access functions of A are affine or
3379    constant.  */
3380
3381 static bool 
3382 access_functions_are_affine_or_constant_p (struct data_reference *a)
3383 {
3384   unsigned int i;
3385   VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3386   tree t;
3387   
3388   for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3389     if (!evolution_function_is_constant_p (t)
3390         && !evolution_function_is_affine_multivariate_p (t))
3391       return false;
3392   
3393   return true;
3394 }
3395
3396 /* This computes the affine dependence relation between A and B.
3397    CHREC_KNOWN is used for representing the independence between two
3398    accesses, while CHREC_DONT_KNOW is used for representing the unknown
3399    relation.
3400    
3401    Note that it is possible to stop the computation of the dependence
3402    relation the first time we detect a CHREC_KNOWN element for a given
3403    subscript.  */
3404
3405 void
3406 compute_affine_dependence (struct data_dependence_relation *ddr)
3407 {
3408   struct data_reference *dra = DDR_A (ddr);
3409   struct data_reference *drb = DDR_B (ddr);
3410   
3411   if (dump_file && (dump_flags & TDF_DETAILS))
3412     {
3413       fprintf (dump_file, "(compute_affine_dependence\n");
3414       fprintf (dump_file, "  (stmt_a = \n");
3415       print_generic_expr (dump_file, DR_STMT (dra), 0);
3416       fprintf (dump_file, ")\n  (stmt_b = \n");
3417       print_generic_expr (dump_file, DR_STMT (drb), 0);
3418       fprintf (dump_file, ")\n");
3419     }
3420   
3421   /* Analyze only when the dependence relation is not yet known.  */
3422   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3423     {
3424       if (access_functions_are_affine_or_constant_p (dra)
3425           && access_functions_are_affine_or_constant_p (drb))
3426         subscript_dependence_tester (ddr);
3427       
3428       /* As a last case, if the dependence cannot be determined, or if
3429          the dependence is considered too difficult to determine, answer
3430          "don't know".  */
3431       else
3432         finalize_ddr_dependent (ddr, chrec_dont_know);
3433     }
3434   
3435   if (dump_file && (dump_flags & TDF_DETAILS))
3436     fprintf (dump_file, ")\n");
3437 }
3438
3439 /* This computes the dependence relation for the same data
3440    reference into DDR.  */
3441
3442 static void
3443 compute_self_dependence (struct data_dependence_relation *ddr)
3444 {
3445   unsigned int i;
3446
3447   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3448     {
3449       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3450       
3451       /* The accessed index overlaps for each iteration.  */
3452       SUB_CONFLICTS_IN_A (subscript) = integer_zero_node;
3453       SUB_CONFLICTS_IN_B (subscript) = integer_zero_node;
3454       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3455     }
3456 }
3457
3458
3459 typedef struct data_dependence_relation *ddr_p;
3460 DEF_VEC_P(ddr_p);
3461 DEF_VEC_ALLOC_P(ddr_p,heap);
3462
3463 /* Compute a subset of the data dependence relation graph.  Don't
3464    compute read-read and self relations if 
3465    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation 
3466    of the opposite relation, i.e. when AB has been computed, don't compute BA.
3467    DATAREFS contains a list of data references, and the result is set
3468    in DEPENDENCE_RELATIONS.  */
3469
3470 static void 
3471 compute_all_dependences (varray_type datarefs, 
3472                          bool compute_self_and_read_read_dependences,
3473                          VEC(ddr_p,heap) **dependence_relations)
3474 {
3475   unsigned int i, j, N;
3476
3477   N = VARRAY_ACTIVE_SIZE (datarefs);
3478
3479   /* Note that we specifically skip i == j because it's a self dependence, and
3480      use compute_self_dependence below.  */
3481
3482   for (i = 0; i < N; i++)
3483     for (j = i + 1; j < N; j++)
3484       {
3485         struct data_reference *a, *b;
3486         struct data_dependence_relation *ddr;
3487
3488         a = VARRAY_GENERIC_PTR (datarefs, i);
3489         b = VARRAY_GENERIC_PTR (datarefs, j);
3490         if (DR_IS_READ (a) && DR_IS_READ (b)
3491             && !compute_self_and_read_read_dependences)
3492           continue;
3493         ddr = initialize_data_dependence_relation (a, b);
3494
3495         VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3496         compute_affine_dependence (ddr);
3497         compute_subscript_distance (ddr);
3498       }
3499   if (!compute_self_and_read_read_dependences)
3500     return;
3501
3502   /* Compute self dependence relation of each dataref to itself.  */
3503
3504   for (i = 0; i < N; i++)
3505     {
3506       struct data_reference *a, *b;
3507       struct data_dependence_relation *ddr;
3508
3509       a = VARRAY_GENERIC_PTR (datarefs, i);
3510       b = VARRAY_GENERIC_PTR (datarefs, i);
3511       ddr = initialize_data_dependence_relation (a, b);
3512
3513       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3514       compute_self_dependence (ddr);
3515       compute_subscript_distance (ddr);
3516     }
3517 }
3518
3519 /* Search the data references in LOOP, and record the information into
3520    DATAREFS.  Returns chrec_dont_know when failing to analyze a
3521    difficult case, returns NULL_TREE otherwise.
3522    
3523    TODO: This function should be made smarter so that it can handle address
3524    arithmetic as if they were array accesses, etc.  */
3525
3526 tree 
3527 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
3528 {
3529   basic_block bb, *bbs;
3530   unsigned int i;
3531   block_stmt_iterator bsi;
3532   struct data_reference *dr;
3533
3534   bbs = get_loop_body (loop);
3535
3536   for (i = 0; i < loop->num_nodes; i++)
3537     {
3538       bb = bbs[i];
3539
3540       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3541         {
3542           tree stmt = bsi_stmt (bsi);
3543
3544           /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3545              Calls have side-effects, except those to const or pure
3546              functions.  */
3547           if ((TREE_CODE (stmt) == CALL_EXPR
3548                && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
3549               || (TREE_CODE (stmt) == ASM_EXPR
3550                   && ASM_VOLATILE_P (stmt)))
3551             goto insert_dont_know_node;
3552
3553           if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3554             continue;
3555
3556           switch (TREE_CODE (stmt))
3557             {
3558             case MODIFY_EXPR:
3559               {
3560                 bool one_inserted = false;
3561                 tree opnd0 = TREE_OPERAND (stmt, 0);
3562                 tree opnd1 = TREE_OPERAND (stmt, 1);
3563                 
3564                 if (TREE_CODE (opnd0) == ARRAY_REF 
3565                     || TREE_CODE (opnd0) == INDIRECT_REF)
3566                   {
3567                     dr = create_data_ref (opnd0, stmt, false);
3568                     if (dr) 
3569                       {
3570                         VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3571                         one_inserted = true;
3572                       }
3573                   }
3574
3575                 if (TREE_CODE (opnd1) == ARRAY_REF 
3576                     || TREE_CODE (opnd1) == INDIRECT_REF)
3577                   {
3578                     dr = create_data_ref (opnd1, stmt, true);
3579                     if (dr) 
3580                       {
3581                         VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3582                         one_inserted = true;
3583                       }
3584                   }
3585
3586                 if (!one_inserted)
3587                   goto insert_dont_know_node;
3588
3589                 break;
3590               }
3591
3592             case CALL_EXPR:
3593               {
3594                 tree args;
3595                 bool one_inserted = false;
3596
3597                 for (args = TREE_OPERAND (stmt, 1); args; 
3598                      args = TREE_CHAIN (args))
3599                   if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
3600                       || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF)
3601                     {
3602                       dr = create_data_ref (TREE_VALUE (args), stmt, true);
3603                       if (dr)
3604                         {
3605                           VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
3606                           one_inserted = true;
3607                         }
3608                     }
3609
3610                 if (!one_inserted)
3611                   goto insert_dont_know_node;
3612
3613                 break;
3614               }
3615
3616             default:
3617                 {
3618                   struct data_reference *res;
3619
3620                 insert_dont_know_node:;
3621                   res = xmalloc (sizeof (struct data_reference));
3622                   DR_STMT (res) = NULL_TREE;
3623                   DR_REF (res) = NULL_TREE;
3624                   DR_BASE_OBJECT (res) = NULL;
3625                   DR_TYPE (res) = ARRAY_REF_TYPE;
3626                   DR_SET_ACCESS_FNS (res, NULL);
3627                   DR_BASE_OBJECT (res) = NULL;
3628                   DR_IS_READ (res) = false;
3629                   DR_BASE_ADDRESS (res) = NULL_TREE;
3630                   DR_OFFSET (res) = NULL_TREE;
3631                   DR_INIT (res) = NULL_TREE;
3632                   DR_STEP (res) = NULL_TREE;
3633                   DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
3634                   DR_MEMTAG (res) = NULL_TREE;
3635                   DR_PTR_INFO (res) = NULL;
3636                   VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
3637
3638                   free (bbs);
3639                   return chrec_dont_know;
3640                 }
3641             }
3642
3643           /* When there are no defs in the loop, the loop is parallel.  */
3644           if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
3645             loop->parallel_p = false;
3646         }
3647
3648       if (chrec_contains_undetermined (loop->estimated_nb_iterations))
3649         compute_estimated_nb_iterations (loop);
3650     }
3651
3652   free (bbs);
3653
3654   return NULL_TREE;
3655 }
3656
3657 \f
3658
3659 /* This section contains all the entry points.  */
3660
3661 /* Given a loop nest LOOP, the following vectors are returned:
3662    *DATAREFS is initialized to all the array elements contained in this loop, 
3663    *DEPENDENCE_RELATIONS contains the relations between the data references.  
3664    Compute read-read and self relations if 
3665    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
3666
3667 void
3668 compute_data_dependences_for_loop (struct loop *loop, 
3669                                    bool compute_self_and_read_read_dependences,
3670                                    varray_type *datarefs,
3671                                    varray_type *dependence_relations)
3672 {
3673   unsigned int i, nb_loops;
3674   VEC(ddr_p,heap) *allrelations;
3675   struct data_dependence_relation *ddr;
3676   struct loop *loop_nest = loop;
3677
3678   while (loop_nest && loop_nest->outer && loop_nest->outer->outer)
3679     loop_nest = loop_nest->outer;
3680
3681   nb_loops = loop_nest->level;
3682
3683   /* If one of the data references is not computable, give up without
3684      spending time to compute other dependences.  */
3685   if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
3686     {
3687       struct data_dependence_relation *ddr;
3688
3689       /* Insert a single relation into dependence_relations:
3690          chrec_dont_know.  */
3691       ddr = initialize_data_dependence_relation (NULL, NULL);
3692       VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3693       build_classic_dist_vector (ddr, nb_loops, loop->depth);
3694       build_classic_dir_vector (ddr, nb_loops, loop->depth);
3695       return;
3696     }
3697
3698   allrelations = NULL;
3699   compute_all_dependences (*datarefs, compute_self_and_read_read_dependences,
3700                            &allrelations);
3701
3702   for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++)
3703     {
3704       if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth))
3705         {
3706           VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
3707           build_classic_dir_vector (ddr, nb_loops, loop_nest->depth);
3708         }
3709     }
3710 }
3711
3712 /* Entry point (for testing only).  Analyze all the data references
3713    and the dependence relations.
3714
3715    The data references are computed first.  
3716    
3717    A relation on these nodes is represented by a complete graph.  Some
3718    of the relations could be of no interest, thus the relations can be
3719    computed on demand.
3720    
3721    In the following function we compute all the relations.  This is
3722    just a first implementation that is here for:
3723    - for showing how to ask for the dependence relations, 
3724    - for the debugging the whole dependence graph,
3725    - for the dejagnu testcases and maintenance.
3726    
3727    It is possible to ask only for a part of the graph, avoiding to
3728    compute the whole dependence graph.  The computed dependences are
3729    stored in a knowledge base (KB) such that later queries don't
3730    recompute the same information.  The implementation of this KB is
3731    transparent to the optimizer, and thus the KB can be changed with a
3732    more efficient implementation, or the KB could be disabled.  */
3733
3734 void 
3735 analyze_all_data_dependences (struct loops *loops)
3736 {
3737   unsigned int i;
3738   varray_type datarefs;
3739   varray_type dependence_relations;
3740   int nb_data_refs = 10;
3741
3742   VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
3743   VARRAY_GENERIC_PTR_INIT (dependence_relations, 
3744                            nb_data_refs * nb_data_refs,
3745                            "dependence_relations");
3746
3747   /* Compute DDs on the whole function.  */
3748   compute_data_dependences_for_loop (loops->parray[0], false,
3749                                      &datarefs, &dependence_relations);
3750
3751   if (dump_file)
3752     {
3753       dump_data_dependence_relations (dump_file, dependence_relations);
3754       fprintf (dump_file, "\n\n");
3755
3756       if (dump_flags & TDF_DETAILS)
3757         dump_dist_dir_vectors (dump_file, dependence_relations);
3758
3759       if (dump_flags & TDF_STATS)
3760         {
3761           unsigned nb_top_relations = 0;
3762           unsigned nb_bot_relations = 0;
3763           unsigned nb_basename_differ = 0;
3764           unsigned nb_chrec_relations = 0;
3765
3766           for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3767             {
3768               struct data_dependence_relation *ddr;
3769               ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
3770           
3771               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
3772                 nb_top_relations++;
3773           
3774               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
3775                 {
3776                   struct data_reference *a = DDR_A (ddr);
3777                   struct data_reference *b = DDR_B (ddr);
3778                   bool differ_p;        
3779               
3780                   if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
3781                        && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
3782                       || (base_object_differ_p (a, b, &differ_p) 
3783                           && differ_p))
3784                     nb_basename_differ++;
3785                   else
3786                     nb_bot_relations++;
3787                 }
3788           
3789               else 
3790                 nb_chrec_relations++;
3791             }
3792       
3793           gather_stats_on_scev_database ();
3794         }
3795     }
3796
3797   free_dependence_relations (dependence_relations);
3798   free_data_refs (datarefs);
3799 }
3800
3801 /* Free the memory used by a data dependence relation DDR.  */
3802
3803 void
3804 free_dependence_relation (struct data_dependence_relation *ddr)
3805 {
3806   if (ddr == NULL)
3807     return;
3808
3809   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
3810     varray_clear (DDR_SUBSCRIPTS (ddr));
3811   free (ddr);
3812 }
3813
3814 /* Free the memory used by the data dependence relations from
3815    DEPENDENCE_RELATIONS.  */
3816
3817 void 
3818 free_dependence_relations (varray_type dependence_relations)
3819 {
3820   unsigned int i;
3821   if (dependence_relations == NULL)
3822     return;
3823
3824   for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
3825     free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
3826   varray_clear (dependence_relations);
3827 }
3828
3829 /* Free the memory used by the data references from DATAREFS.  */
3830
3831 void
3832 free_data_refs (varray_type datarefs)
3833 {
3834   unsigned int i;
3835   
3836   if (datarefs == NULL)
3837     return;
3838
3839   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
3840     {
3841       struct data_reference *dr = (struct data_reference *) 
3842         VARRAY_GENERIC_PTR (datarefs, i);
3843       if (dr)
3844         {
3845           DR_FREE_ACCESS_FNS (dr);
3846           free (dr);
3847         }
3848     }
3849   varray_clear (datarefs);
3850 }
3851