OSDN Git Service

PR tree-optimization/22236
[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 /* Estimate the number of iterations from the size of the data and the
735    access functions.  */
736
737 static void
738 estimate_niter_from_size_of_data (struct loop *loop, 
739                                   tree opnd0, 
740                                   tree access_fn, 
741                                   tree stmt)
742 {
743   tree estimation;
744   tree array_size, data_size, element_size;
745   tree init, step;
746
747   init = initial_condition (access_fn);
748   step = evolution_part_in_loop_num (access_fn, loop->num);
749
750   array_size = TYPE_SIZE (TREE_TYPE (opnd0));
751   element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
752   if (array_size == NULL_TREE 
753       || TREE_CODE (array_size) != INTEGER_CST
754       || TREE_CODE (element_size) != INTEGER_CST)
755     return;
756
757   data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
758                            array_size, element_size);
759
760   if (init != NULL_TREE
761       && step != NULL_TREE
762       && TREE_CODE (init) == INTEGER_CST
763       && TREE_CODE (step) == INTEGER_CST)
764     {
765       estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
766                                 fold_build2 (MINUS_EXPR, integer_type_node,
767                                              data_size, init), step);
768
769       record_estimate (loop, estimation, boolean_true_node, stmt);
770     }
771 }
772
773 /* Given an ARRAY_REF node REF, records its access functions.
774    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
775    i.e. the constant "3", then recursively call the function on opnd0,
776    i.e. the ARRAY_REF "A[i]".  The function returns the base name:
777    "A".  */
778
779 static tree
780 analyze_array_indexes (struct loop *loop,
781                        VEC(tree,heap) **access_fns, 
782                        tree ref, tree stmt)
783 {
784   tree opnd0, opnd1;
785   tree access_fn;
786   
787   opnd0 = TREE_OPERAND (ref, 0);
788   opnd1 = TREE_OPERAND (ref, 1);
789   
790   /* The detection of the evolution function for this data access is
791      postponed until the dependence test.  This lazy strategy avoids
792      the computation of access functions that are of no interest for
793      the optimizers.  */
794   access_fn = instantiate_parameters 
795     (loop, analyze_scalar_evolution (loop, opnd1));
796
797   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
798     estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
799   
800   VEC_safe_push (tree, heap, *access_fns, access_fn);
801   
802   /* Recursively record other array access functions.  */
803   if (TREE_CODE (opnd0) == ARRAY_REF)
804     return analyze_array_indexes (loop, access_fns, opnd0, stmt);
805   
806   /* Return the base name of the data access.  */
807   else
808     return opnd0;
809 }
810
811 /* For a data reference REF contained in the statement STMT, initialize
812    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
813    set to true when REF is in the right hand side of an
814    assignment.  */
815
816 struct data_reference *
817 analyze_array (tree stmt, tree ref, bool is_read)
818 {
819   struct data_reference *res;
820   VEC(tree,heap) *acc_fns;
821
822   if (dump_file && (dump_flags & TDF_DETAILS))
823     {
824       fprintf (dump_file, "(analyze_array \n");
825       fprintf (dump_file, "  (ref = ");
826       print_generic_stmt (dump_file, ref, 0);
827       fprintf (dump_file, ")\n");
828     }
829   
830   res = xmalloc (sizeof (struct data_reference));
831   
832   DR_STMT (res) = stmt;
833   DR_REF (res) = ref;
834   acc_fns = VEC_alloc (tree, heap, 3);
835   DR_BASE_OBJECT (res) = analyze_array_indexes 
836     (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
837   DR_TYPE (res) = ARRAY_REF_TYPE;
838   DR_SET_ACCESS_FNS (res, acc_fns);
839   DR_IS_READ (res) = is_read;
840   DR_BASE_ADDRESS (res) = NULL_TREE;
841   DR_OFFSET (res) = NULL_TREE;
842   DR_INIT (res) = NULL_TREE;
843   DR_STEP (res) = NULL_TREE;
844   DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
845   DR_MEMTAG (res) = NULL_TREE;
846   DR_PTR_INFO (res) = NULL;
847   
848   if (dump_file && (dump_flags & TDF_DETAILS))
849     fprintf (dump_file, ")\n");
850   
851   return res;
852 }
853
854
855 /* Analyze an indirect memory reference, REF, that comes from STMT.
856    IS_READ is true if this is an indirect load, and false if it is
857    an indirect store.
858    Return a new data reference structure representing the indirect_ref, or
859    NULL if we cannot describe the access function.  */
860   
861 static struct data_reference *
862 analyze_indirect_ref (tree stmt, tree ref, bool is_read) 
863 {
864   struct loop *loop = loop_containing_stmt (stmt);
865   tree ptr_ref = TREE_OPERAND (ref, 0);
866   tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
867   tree init = initial_condition_in_loop_num (access_fn, loop->num);
868   tree base_address = NULL_TREE, evolution, step = NULL_TREE;
869   struct ptr_info_def *ptr_info = NULL;
870
871   if (TREE_CODE (ptr_ref) == SSA_NAME)
872     ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
873
874   STRIP_NOPS (init);   
875   if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
876     {
877       if (dump_file && (dump_flags & TDF_DETAILS))
878         {
879           fprintf (dump_file, "\nBad access function of ptr: ");
880           print_generic_expr (dump_file, ref, TDF_SLIM);
881           fprintf (dump_file, "\n");
882         }
883       return NULL;
884     }
885
886   if (dump_file && (dump_flags & TDF_DETAILS))
887     {
888       fprintf (dump_file, "\nAccess function of ptr: ");
889       print_generic_expr (dump_file, access_fn, TDF_SLIM);
890       fprintf (dump_file, "\n");
891     }
892
893   if (!expr_invariant_in_loop_p (loop, init))
894     {
895     if (dump_file && (dump_flags & TDF_DETAILS))
896         fprintf (dump_file, "\ninitial condition is not loop invariant.\n");    
897     }
898   else
899     {
900       base_address = init;
901       evolution = evolution_part_in_loop_num (access_fn, loop->num);
902       if (evolution != chrec_dont_know)
903         {       
904           if (!evolution)
905             step = ssize_int (0);
906           else  
907             {
908               if (TREE_CODE (evolution) == INTEGER_CST)
909                 step = fold_convert (ssizetype, evolution);
910               else
911                 if (dump_file && (dump_flags & TDF_DETAILS))
912                   fprintf (dump_file, "\nnon constant step for ptr access.\n"); 
913             }
914         }
915       else
916         if (dump_file && (dump_flags & TDF_DETAILS))
917           fprintf (dump_file, "\nunknown evolution of ptr.\n"); 
918     }
919   return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address, 
920                         NULL_TREE, step, NULL_TREE, NULL_TREE, 
921                         ptr_info, POINTER_REF_TYPE);
922 }
923
924 /* For a data reference REF contained in the statement STMT, initialize
925    a DATA_REFERENCE structure, and return it.  */
926
927 struct data_reference *
928 init_data_ref (tree stmt, 
929                tree ref,
930                tree base,
931                tree access_fn,
932                bool is_read,
933                tree base_address,
934                tree init_offset,
935                tree step,
936                tree misalign,
937                tree memtag,
938                struct ptr_info_def *ptr_info,
939                enum data_ref_type type)
940 {
941   struct data_reference *res;
942   VEC(tree,heap) *acc_fns;
943
944   if (dump_file && (dump_flags & TDF_DETAILS))
945     {
946       fprintf (dump_file, "(init_data_ref \n");
947       fprintf (dump_file, "  (ref = ");
948       print_generic_stmt (dump_file, ref, 0);
949       fprintf (dump_file, ")\n");
950     }
951   
952   res = xmalloc (sizeof (struct data_reference));
953   
954   DR_STMT (res) = stmt;
955   DR_REF (res) = ref;
956   DR_BASE_OBJECT (res) = base;
957   DR_TYPE (res) = type;
958   acc_fns = VEC_alloc (tree, heap, 3);
959   DR_SET_ACCESS_FNS (res, acc_fns);
960   VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
961   DR_IS_READ (res) = is_read;
962   DR_BASE_ADDRESS (res) = base_address;
963   DR_OFFSET (res) = init_offset;
964   DR_INIT (res) = NULL_TREE;
965   DR_STEP (res) = step;
966   DR_OFFSET_MISALIGNMENT (res) = misalign;
967   DR_MEMTAG (res) = memtag;
968   DR_PTR_INFO (res) = ptr_info;
969   
970   if (dump_file && (dump_flags & TDF_DETAILS))
971     fprintf (dump_file, ")\n");
972   
973   return res;
974 }
975
976 \f
977
978 /* Function strip_conversions
979
980    Strip conversions that don't narrow the mode.  */
981
982 static tree 
983 strip_conversion (tree expr)
984 {
985   tree to, ti, oprnd0;
986   
987   while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
988     {
989       to = TREE_TYPE (expr);
990       oprnd0 = TREE_OPERAND (expr, 0);
991       ti = TREE_TYPE (oprnd0);
992  
993       if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
994         return NULL_TREE;
995       if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
996         return NULL_TREE;
997       
998       expr = oprnd0;
999     }
1000   return expr; 
1001 }
1002 \f
1003
1004 /* Function analyze_offset_expr
1005
1006    Given an offset expression EXPR received from get_inner_reference, analyze
1007    it and create an expression for INITIAL_OFFSET by substituting the variables 
1008    of EXPR with initial_condition of the corresponding access_fn in the loop. 
1009    E.g., 
1010       for i
1011          for (j = 3; j < N; j++)
1012             a[j].b[i][j] = 0;
1013          
1014    For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be 
1015    substituted, since its access_fn in the inner loop is i. 'j' will be 
1016    substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1017    C` =  3 * C_j + C.
1018
1019    Compute MISALIGN (the misalignment of the data reference initial access from
1020    its base). Misalignment can be calculated only if all the variables can be 
1021    substituted with constants, otherwise, we record maximum possible alignment
1022    in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN 
1023    will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be 
1024    recorded in ALIGNED_TO.
1025
1026    STEP is an evolution of the data reference in this loop in bytes.
1027    In the above example, STEP is C_j.
1028
1029    Return FALSE, if the analysis fails, e.g., there is no access_fn for a 
1030    variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1031    and STEP) are NULL_TREEs. Otherwise, return TRUE.
1032
1033 */
1034
1035 static bool
1036 analyze_offset_expr (tree expr, 
1037                      struct loop *loop, 
1038                      tree *initial_offset,
1039                      tree *misalign,
1040                      tree *aligned_to,
1041                      tree *step)
1042 {
1043   tree oprnd0;
1044   tree oprnd1;
1045   tree left_offset = ssize_int (0);
1046   tree right_offset = ssize_int (0);
1047   tree left_misalign = ssize_int (0);
1048   tree right_misalign = ssize_int (0);
1049   tree left_step = ssize_int (0);
1050   tree right_step = ssize_int (0);
1051   enum tree_code code;
1052   tree init, evolution;
1053   tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1054
1055   *step = NULL_TREE;
1056   *misalign = NULL_TREE;
1057   *aligned_to = NULL_TREE;  
1058   *initial_offset = NULL_TREE;
1059
1060   /* Strip conversions that don't narrow the mode.  */
1061   expr = strip_conversion (expr);
1062   if (!expr)
1063     return false;
1064
1065   /* Stop conditions:
1066      1. Constant.  */
1067   if (TREE_CODE (expr) == INTEGER_CST)
1068     {
1069       *initial_offset = fold_convert (ssizetype, expr);
1070       *misalign = fold_convert (ssizetype, expr);      
1071       *step = ssize_int (0);
1072       return true;
1073     }
1074
1075   /* 2. Variable. Try to substitute with initial_condition of the corresponding
1076      access_fn in the current loop.  */
1077   if (SSA_VAR_P (expr))
1078     {
1079       tree access_fn = analyze_scalar_evolution (loop, expr);
1080
1081       if (access_fn == chrec_dont_know)
1082         /* No access_fn.  */
1083         return false;
1084
1085       init = initial_condition_in_loop_num (access_fn, loop->num);
1086       if (init == expr && !expr_invariant_in_loop_p (loop, init))
1087         /* Not enough information: may be not loop invariant.  
1088            E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its 
1089            initial_condition is D, but it depends on i - loop's induction
1090            variable.  */          
1091         return false;
1092
1093       evolution = evolution_part_in_loop_num (access_fn, loop->num);
1094       if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1095         /* Evolution is not constant.  */
1096         return false;
1097
1098       if (TREE_CODE (init) == INTEGER_CST)
1099         *misalign = fold_convert (ssizetype, init);
1100       else
1101         /* Not constant, misalignment cannot be calculated.  */
1102         *misalign = NULL_TREE;
1103
1104       *initial_offset = fold_convert (ssizetype, init); 
1105
1106       *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1107       return true;      
1108     }
1109
1110   /* Recursive computation.  */
1111   if (!BINARY_CLASS_P (expr))
1112     {
1113       /* We expect to get binary expressions (PLUS/MINUS and MULT).  */
1114       if (dump_file && (dump_flags & TDF_DETAILS))
1115         {
1116           fprintf (dump_file, "\nNot binary expression ");
1117           print_generic_expr (dump_file, expr, TDF_SLIM);
1118           fprintf (dump_file, "\n");
1119         }
1120       return false;
1121     }
1122   oprnd0 = TREE_OPERAND (expr, 0);
1123   oprnd1 = TREE_OPERAND (expr, 1);
1124
1125   if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign, 
1126                             &left_aligned_to, &left_step)
1127       || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign, 
1128                                &right_aligned_to, &right_step))
1129     return false;
1130
1131   /* The type of the operation: plus, minus or mult.  */
1132   code = TREE_CODE (expr);
1133   switch (code)
1134     {
1135     case MULT_EXPR:
1136       if (TREE_CODE (right_offset) != INTEGER_CST)
1137         /* RIGHT_OFFSET can be not constant. For example, for arrays of variable 
1138            sized types. 
1139            FORNOW: We don't support such cases.  */
1140         return false;
1141
1142       /* Strip conversions that don't narrow the mode.  */
1143       left_offset = strip_conversion (left_offset);      
1144       if (!left_offset)
1145         return false;      
1146       /* Misalignment computation.  */
1147       if (SSA_VAR_P (left_offset))
1148         {
1149           /* If the left side contains variables that can't be substituted with 
1150              constants, the misalignment is unknown. However, if the right side 
1151              is a multiple of some alignment, we know that the expression is
1152              aligned to it. Therefore, we record such maximum possible value.
1153            */
1154           *misalign = NULL_TREE;
1155           *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1156         }
1157       else 
1158         {
1159           /* The left operand was successfully substituted with constant.  */     
1160           if (left_misalign)
1161             {
1162               /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is 
1163                  NULL_TREE.  */
1164               *misalign  = size_binop (code, left_misalign, right_misalign);
1165               if (left_aligned_to && right_aligned_to)
1166                 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, 
1167                                           right_aligned_to);
1168               else 
1169                 *aligned_to = left_aligned_to ? 
1170                   left_aligned_to : right_aligned_to;
1171             }
1172           else
1173             *misalign = NULL_TREE; 
1174         }
1175
1176       /* Step calculation.  */
1177       /* Multiply the step by the right operand.  */
1178       *step  = size_binop (MULT_EXPR, left_step, right_offset);
1179       break;
1180    
1181     case PLUS_EXPR:
1182     case MINUS_EXPR:
1183       /* Combine the recursive calculations for step and misalignment.  */
1184       *step = size_binop (code, left_step, right_step);
1185
1186       /* Unknown alignment.  */
1187       if ((!left_misalign && !left_aligned_to)
1188           || (!right_misalign && !right_aligned_to))
1189         {
1190           *misalign = NULL_TREE;
1191           *aligned_to = NULL_TREE;
1192           break;
1193         }
1194
1195       if (left_misalign && right_misalign)
1196         *misalign = size_binop (code, left_misalign, right_misalign);
1197       else
1198         *misalign = left_misalign ? left_misalign : right_misalign;
1199
1200       if (left_aligned_to && right_aligned_to)
1201         *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1202       else 
1203         *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1204
1205       break;
1206
1207     default:
1208       gcc_unreachable ();
1209     }
1210
1211   /* Compute offset.  */
1212   *initial_offset = fold_convert (ssizetype, 
1213                                   fold_build2 (code, TREE_TYPE (left_offset), 
1214                                                left_offset, 
1215                                                right_offset));
1216   return true;
1217 }
1218
1219 /* Function address_analysis
1220
1221    Return the BASE of the address expression EXPR.
1222    Also compute the OFFSET from BASE, MISALIGN and STEP.
1223
1224    Input:
1225    EXPR - the address expression that is being analyzed
1226    STMT - the statement that contains EXPR or its original memory reference
1227    IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1228    DR - data_reference struct for the original memory reference
1229
1230    Output:
1231    BASE (returned value) - the base of the data reference EXPR.
1232    INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1233    MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1234               computation is impossible 
1235    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 
1236                 calculated (doesn't depend on variables)
1237    STEP - evolution of EXPR in the loop
1238  
1239    If something unexpected is encountered (an unsupported form of data-ref),
1240    then NULL_TREE is returned.  
1241  */
1242
1243 static tree
1244 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr, 
1245                   tree *offset, tree *misalign, tree *aligned_to, tree *step)
1246 {
1247   tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1248   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1249   tree dummy, address_aligned_to = NULL_TREE;
1250   struct ptr_info_def *dummy1;
1251   subvar_t dummy2;
1252
1253   switch (TREE_CODE (expr))
1254     {
1255     case PLUS_EXPR:
1256     case MINUS_EXPR:
1257       /* EXPR is of form {base +/- offset} (or {offset +/- base}).  */
1258       oprnd0 = TREE_OPERAND (expr, 0);
1259       oprnd1 = TREE_OPERAND (expr, 1);
1260
1261       STRIP_NOPS (oprnd0);
1262       STRIP_NOPS (oprnd1);
1263       
1264       /* Recursively try to find the base of the address contained in EXPR.
1265          For offset, the returned base will be NULL.  */
1266       base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset, 
1267                                      &address_misalign, &address_aligned_to, 
1268                                      step);
1269
1270       base_addr1 = address_analysis (oprnd1, stmt, is_read,  dr, &address_offset, 
1271                                      &address_misalign, &address_aligned_to, 
1272                                      step);
1273
1274       /* We support cases where only one of the operands contains an 
1275          address.  */
1276       if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1277         {
1278           if (dump_file && (dump_flags & TDF_DETAILS))
1279             {
1280               fprintf (dump_file, 
1281                     "\neither more than one address or no addresses in expr ");
1282               print_generic_expr (dump_file, expr, TDF_SLIM);
1283               fprintf (dump_file, "\n");
1284             }   
1285           return NULL_TREE;
1286         }
1287
1288       /* To revert STRIP_NOPS.  */
1289       oprnd0 = TREE_OPERAND (expr, 0);
1290       oprnd1 = TREE_OPERAND (expr, 1);
1291       
1292       offset_expr = base_addr0 ? 
1293         fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1294
1295       /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is 
1296          a number, we can add it to the misalignment value calculated for base,
1297          otherwise, misalignment is NULL.  */
1298       if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1299         {
1300           *misalign = size_binop (TREE_CODE (expr), address_misalign, 
1301                                   offset_expr);
1302           *aligned_to = address_aligned_to;
1303         }
1304       else
1305         {
1306           *misalign = NULL_TREE;
1307           *aligned_to = NULL_TREE;
1308         }
1309
1310       /* Combine offset (from EXPR {base + offset}) with the offset calculated
1311          for base.  */
1312       *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1313       return base_addr0 ? base_addr0 : base_addr1;
1314
1315     case ADDR_EXPR:
1316       base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read, 
1317                                       &dr, offset, misalign, aligned_to, step, 
1318                                       &dummy, &dummy1, &dummy2);
1319       return base_address;
1320
1321     case SSA_NAME:
1322       if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1323         {
1324           if (dump_file && (dump_flags & TDF_DETAILS))
1325             {
1326               fprintf (dump_file, "\nnot pointer SSA_NAME ");
1327               print_generic_expr (dump_file, expr, TDF_SLIM);
1328               fprintf (dump_file, "\n");
1329             }   
1330           return NULL_TREE;
1331         }
1332       *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1333       *misalign = ssize_int (0);
1334       *offset = ssize_int (0);
1335       *step = ssize_int (0);
1336       return expr;
1337       
1338     default:
1339       return NULL_TREE;
1340     }
1341 }
1342
1343
1344 /* Function object_analysis
1345
1346    Create a data-reference structure DR for MEMREF.
1347    Return the BASE of the data reference MEMREF if the analysis is possible.
1348    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1349    E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset  
1350    'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET 
1351    instantiated with initial_conditions of access_functions of variables, 
1352    and STEP is the evolution of the DR_REF in this loop.
1353    
1354    Function get_inner_reference is used for the above in case of ARRAY_REF and
1355    COMPONENT_REF.
1356
1357    The structure of the function is as follows:
1358    Part 1:
1359    Case 1. For handled_component_p refs 
1360           1.1 build data-reference structure for MEMREF
1361           1.2 call get_inner_reference
1362             1.2.1 analyze offset expr received from get_inner_reference
1363           (fall through with BASE)
1364    Case 2. For declarations 
1365           2.1 set MEMTAG
1366    Case 3. For INDIRECT_REFs 
1367           3.1 build data-reference structure for MEMREF
1368           3.2 analyze evolution and initial condition of MEMREF
1369           3.3 set data-reference structure for MEMREF
1370           3.4 call address_analysis to analyze INIT of the access function
1371           3.5 extract memory tag
1372
1373    Part 2:
1374    Combine the results of object and address analysis to calculate 
1375    INITIAL_OFFSET, STEP and misalignment info.   
1376
1377    Input:
1378    MEMREF - the memory reference that is being analyzed
1379    STMT - the statement that contains MEMREF
1380    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1381    
1382    Output:
1383    BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1384                                    E.g, if MEMREF is a.b[k].c[i][j] the returned
1385                                    base is &a.
1386    DR - data_reference struct for MEMREF
1387    INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1388    MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of 
1389               ALIGNMENT or NULL_TREE if the computation is impossible
1390    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 
1391                 calculated (doesn't depend on variables)
1392    STEP - evolution of the DR_REF in the loop
1393    MEMTAG - memory tag for aliasing purposes
1394    PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1395    SUBVARS - Sub-variables of the variable
1396
1397    If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned, 
1398    but DR can be created anyway.
1399    
1400 */
1401  
1402 static tree
1403 object_analysis (tree memref, tree stmt, bool is_read, 
1404                  struct data_reference **dr, tree *offset, tree *misalign, 
1405                  tree *aligned_to, tree *step, tree *memtag,
1406                  struct ptr_info_def **ptr_info, subvar_t *subvars)
1407 {
1408   tree base = NULL_TREE, base_address = NULL_TREE;
1409   tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1410   tree object_step = ssize_int (0), address_step = ssize_int (0);
1411   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1412   HOST_WIDE_INT pbitsize, pbitpos;
1413   tree poffset, bit_pos_in_bytes;
1414   enum machine_mode pmode;
1415   int punsignedp, pvolatilep;
1416   tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1417   struct loop *loop = loop_containing_stmt (stmt);
1418   struct data_reference *ptr_dr = NULL;
1419   tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1420
1421  *ptr_info = NULL;
1422
1423   /* Part 1:  */
1424   /* Case 1. handled_component_p refs.  */
1425   if (handled_component_p (memref))
1426     {
1427       /* 1.1 build data-reference structure for MEMREF.  */
1428       /* TODO: handle COMPONENT_REFs.  */
1429       if (!(*dr))
1430         { 
1431           if (TREE_CODE (memref) == ARRAY_REF)
1432             *dr = analyze_array (stmt, memref, is_read);          
1433           else
1434             {
1435               /* FORNOW.  */
1436               if (dump_file && (dump_flags & TDF_DETAILS))
1437                 {
1438                   fprintf (dump_file, "\ndata-ref of unsupported type ");
1439                   print_generic_expr (dump_file, memref, TDF_SLIM);
1440                   fprintf (dump_file, "\n");
1441                 }
1442               return NULL_TREE;
1443             }
1444         }
1445
1446       /* 1.2 call get_inner_reference.  */
1447       /* Find the base and the offset from it.  */
1448       base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1449                                   &pmode, &punsignedp, &pvolatilep, false);
1450       if (!base)
1451         {
1452           if (dump_file && (dump_flags & TDF_DETAILS))
1453             {
1454               fprintf (dump_file, "\nfailed to get inner ref for ");
1455               print_generic_expr (dump_file, memref, TDF_SLIM);
1456               fprintf (dump_file, "\n");
1457             }     
1458           return NULL_TREE;
1459         }
1460
1461       /* 1.2.1 analyze offset expr received from get_inner_reference.  */
1462       if (poffset 
1463           && !analyze_offset_expr (poffset, loop, &object_offset, 
1464                                    &object_misalign, &object_aligned_to,
1465                                    &object_step))
1466         {
1467           if (dump_file && (dump_flags & TDF_DETAILS))
1468             {
1469               fprintf (dump_file, "\nfailed to compute offset or step for ");
1470               print_generic_expr (dump_file, memref, TDF_SLIM);
1471               fprintf (dump_file, "\n");
1472             }
1473           return NULL_TREE;
1474         }
1475
1476       /* Add bit position to OFFSET and MISALIGN.  */
1477
1478       bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1479       /* Check that there is no remainder in bits.  */
1480       if (pbitpos%BITS_PER_UNIT)
1481         {
1482           if (dump_file && (dump_flags & TDF_DETAILS))
1483             fprintf (dump_file, "\nbit offset alignment.\n");
1484           return NULL_TREE;
1485         }
1486       object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);     
1487       if (object_misalign) 
1488         object_misalign = size_binop (PLUS_EXPR, object_misalign, 
1489                                       bit_pos_in_bytes); 
1490       
1491       memref = base; /* To continue analysis of BASE.  */
1492       /* fall through  */
1493     }
1494   
1495   /*  Part 1: Case 2. Declarations.  */ 
1496   if (DECL_P (memref))
1497     {
1498       /* We expect to get a decl only if we already have a DR.  */
1499       if (!(*dr))
1500         {
1501           if (dump_file && (dump_flags & TDF_DETAILS))
1502             {
1503               fprintf (dump_file, "\nunhandled decl ");
1504               print_generic_expr (dump_file, memref, TDF_SLIM);
1505               fprintf (dump_file, "\n");
1506             }
1507           return NULL_TREE;
1508         }
1509
1510       /* TODO: if during the analysis of INDIRECT_REF we get to an object, put 
1511          the object in BASE_OBJECT field if we can prove that this is O.K., 
1512          i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1513          (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1514          that every access with 'p' (the original INDIRECT_REF based on '&a')
1515          in the loop is within the array boundaries - from a[0] to a[N-1]).
1516          Otherwise, our alias analysis can be incorrect.
1517          Even if an access function based on BASE_OBJECT can't be build, update
1518          BASE_OBJECT field to enable us to prove that two data-refs are 
1519          different (without access function, distance analysis is impossible).
1520       */
1521      if (SSA_VAR_P (memref) && var_can_have_subvars (memref))   
1522         *subvars = get_subvars_for_var (memref);
1523       base_address = build_fold_addr_expr (memref);
1524       /* 2.1 set MEMTAG.  */
1525       *memtag = memref;
1526     }
1527
1528   /* Part 1:  Case 3. INDIRECT_REFs.  */
1529   else if (TREE_CODE (memref) == INDIRECT_REF)
1530     {
1531       tree ptr_ref = TREE_OPERAND (memref, 0);
1532       if (TREE_CODE (ptr_ref) == SSA_NAME)
1533         *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1534
1535       /* 3.1 build data-reference structure for MEMREF.  */
1536       ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1537       if (!ptr_dr)
1538         {
1539           if (dump_file && (dump_flags & TDF_DETAILS))
1540             {
1541               fprintf (dump_file, "\nfailed to create dr for ");
1542               print_generic_expr (dump_file, memref, TDF_SLIM);
1543               fprintf (dump_file, "\n");
1544             }   
1545           return NULL_TREE;      
1546         }
1547
1548       /* 3.2 analyze evolution and initial condition of MEMREF.  */
1549       ptr_step = DR_STEP (ptr_dr);
1550       ptr_init = DR_BASE_ADDRESS (ptr_dr);
1551       if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1552         {
1553           *dr = (*dr) ? *dr : ptr_dr;
1554           if (dump_file && (dump_flags & TDF_DETAILS))
1555             {
1556               fprintf (dump_file, "\nbad pointer access ");
1557               print_generic_expr (dump_file, memref, TDF_SLIM);
1558               fprintf (dump_file, "\n");
1559             }
1560           return NULL_TREE;
1561         }
1562
1563       if (integer_zerop (ptr_step) && !(*dr))
1564         {
1565           if (dump_file && (dump_flags & TDF_DETAILS)) 
1566             fprintf (dump_file, "\nptr is loop invariant.\n");  
1567           *dr = ptr_dr;
1568           return NULL_TREE;
1569         
1570           /* If there exists DR for MEMREF, we are analyzing the base of
1571              handled component (PTR_INIT), which not necessary has evolution in 
1572              the loop.  */
1573         }
1574       object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1575
1576       /* 3.3 set data-reference structure for MEMREF.  */
1577       if (!*dr)
1578         *dr = ptr_dr;
1579
1580       /* 3.4 call address_analysis to analyze INIT of the access 
1581          function.  */
1582       base_address = address_analysis (ptr_init, stmt, is_read, *dr, 
1583                                        &address_offset, &address_misalign, 
1584                                        &address_aligned_to, &address_step);
1585       if (!base_address)
1586         {
1587           if (dump_file && (dump_flags & TDF_DETAILS))
1588             {
1589               fprintf (dump_file, "\nfailed to analyze address ");
1590               print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1591               fprintf (dump_file, "\n");
1592             }
1593           return NULL_TREE;
1594         }
1595
1596       /* 3.5 extract memory tag.  */
1597       switch (TREE_CODE (base_address))
1598         {
1599         case SSA_NAME:
1600           *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag;
1601           if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1602             *memtag = get_var_ann (
1603                       SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag;
1604           break;
1605         case ADDR_EXPR:
1606           *memtag = TREE_OPERAND (base_address, 0);
1607           break;
1608         default:
1609           if (dump_file && (dump_flags & TDF_DETAILS))
1610             {
1611               fprintf (dump_file, "\nno memtag for "); 
1612               print_generic_expr (dump_file, memref, TDF_SLIM);
1613               fprintf (dump_file, "\n");
1614             }
1615           *memtag = NULL_TREE;
1616           break;
1617         }
1618     }      
1619     
1620   if (!base_address)
1621     {
1622       /* MEMREF cannot be analyzed.  */
1623       if (dump_file && (dump_flags & TDF_DETAILS))
1624         {
1625           fprintf (dump_file, "\ndata-ref of unsupported type ");
1626           print_generic_expr (dump_file, memref, TDF_SLIM);
1627           fprintf (dump_file, "\n");
1628         }
1629       return NULL_TREE;
1630     }
1631
1632   if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1633     *subvars = get_subvars_for_var (*memtag);
1634         
1635   /* Part 2: Combine the results of object and address analysis to calculate 
1636      INITIAL_OFFSET, STEP and misalignment info.  */
1637   *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1638
1639   if ((!object_misalign && !object_aligned_to)
1640       || (!address_misalign && !address_aligned_to))
1641     {
1642       *misalign = NULL_TREE;
1643       *aligned_to = NULL_TREE;
1644     }  
1645   else 
1646     {
1647       if (object_misalign && address_misalign)
1648         *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1649       else
1650         *misalign = object_misalign ? object_misalign : address_misalign;
1651       if (object_aligned_to && address_aligned_to)
1652         *aligned_to = size_binop (MIN_EXPR, object_aligned_to, 
1653                                   address_aligned_to);
1654       else
1655         *aligned_to = object_aligned_to ? 
1656           object_aligned_to : address_aligned_to; 
1657     }
1658   *step = size_binop (PLUS_EXPR, object_step, address_step); 
1659
1660   return base_address;
1661 }
1662
1663 /* Function analyze_offset.
1664    
1665    Extract INVARIANT and CONSTANT parts from OFFSET. 
1666
1667 */
1668 static void 
1669 analyze_offset (tree offset, tree *invariant, tree *constant)
1670 {
1671   tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1672   enum tree_code code = TREE_CODE (offset);
1673
1674   *invariant = NULL_TREE;
1675   *constant = NULL_TREE;
1676
1677   /* Not PLUS/MINUS expression - recursion stop condition.  */
1678   if (code != PLUS_EXPR && code != MINUS_EXPR)
1679     {
1680       if (TREE_CODE (offset) == INTEGER_CST)
1681         *constant = offset;
1682       else
1683         *invariant = offset;
1684       return;
1685     }
1686
1687   op0 = TREE_OPERAND (offset, 0);
1688   op1 = TREE_OPERAND (offset, 1);
1689
1690   /* Recursive call with the operands.  */
1691   analyze_offset (op0, &invariant_0, &constant_0);
1692   analyze_offset (op1, &invariant_1, &constant_1);
1693
1694   /* Combine the results.  */
1695   *constant = constant_0 ? constant_0 : constant_1;
1696   if (invariant_0 && invariant_1)
1697     *invariant = 
1698       fold (build (code, TREE_TYPE (invariant_0), invariant_0, invariant_1));
1699   else
1700     *invariant = invariant_0 ? invariant_0 : invariant_1;
1701 }
1702
1703
1704 /* Function create_data_ref.
1705    
1706    Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1707    DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1708    DR_MEMTAG, and DR_POINTSTO_INFO fields. 
1709
1710    Input:
1711    MEMREF - the memory reference that is being analyzed
1712    STMT - the statement that contains MEMREF
1713    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1714
1715    Output:
1716    DR (returned value) - data_reference struct for MEMREF
1717 */
1718
1719 static struct data_reference *
1720 create_data_ref (tree memref, tree stmt, bool is_read)
1721 {
1722   struct data_reference *dr = NULL;
1723   tree base_address, offset, step, misalign, memtag;
1724   struct loop *loop = loop_containing_stmt (stmt);
1725   tree invariant = NULL_TREE, constant = NULL_TREE;
1726   tree type_size, init_cond;
1727   struct ptr_info_def *ptr_info;
1728   subvar_t subvars = NULL;
1729   tree aligned_to;
1730
1731   if (!memref)
1732     return NULL;
1733
1734   base_address = object_analysis (memref, stmt, is_read, &dr, &offset, 
1735                                   &misalign, &aligned_to, &step, &memtag, 
1736                                   &ptr_info, &subvars);
1737   if (!dr || !base_address)
1738     {
1739       if (dump_file && (dump_flags & TDF_DETAILS))
1740         {
1741           fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1742           print_generic_expr (dump_file, memref, TDF_SLIM);
1743           fprintf (dump_file, "\n");
1744         }
1745       return NULL;
1746     }
1747
1748   DR_BASE_ADDRESS (dr) = base_address;
1749   DR_OFFSET (dr) = offset;
1750   DR_INIT (dr) = ssize_int (0);
1751   DR_STEP (dr) = step;
1752   DR_OFFSET_MISALIGNMENT (dr) = misalign;
1753   DR_ALIGNED_TO (dr) = aligned_to;
1754   DR_MEMTAG (dr) = memtag;
1755   DR_PTR_INFO (dr) = ptr_info;
1756   DR_SUBVARS (dr) = subvars;
1757   
1758   type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1759
1760   /* Change the access function for INIDIRECT_REFs, according to 
1761      DR_BASE_ADDRESS.  Analyze OFFSET calculated in object_analysis. OFFSET is 
1762      an expression that can contain loop invariant expressions and constants.
1763      We put the constant part in the initial condition of the access function
1764      (for data dependence tests), and in DR_INIT of the data-ref. The loop
1765      invariant part is put in DR_OFFSET. 
1766      The evolution part of the access function is STEP calculated in
1767      object_analysis divided by the size of data type.
1768   */
1769   if (!DR_BASE_OBJECT (dr))
1770     {
1771       tree access_fn;
1772       tree new_step;
1773
1774       /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and
1775          DR_OFFSET fields of DR.  */
1776       analyze_offset (offset, &invariant, &constant); 
1777       if (constant)
1778         {
1779           DR_INIT (dr) = fold_convert (ssizetype, constant);
1780           init_cond = fold (build (TRUNC_DIV_EXPR, TREE_TYPE (constant), 
1781                                    constant, type_size));
1782         }
1783       else
1784         DR_INIT (dr) = init_cond = ssize_int (0);;
1785
1786       if (invariant)
1787         DR_OFFSET (dr) = invariant;
1788       else
1789         DR_OFFSET (dr) = ssize_int (0);
1790
1791       /* Update access function.  */
1792       access_fn = DR_ACCESS_FN (dr, 0);
1793       new_step = size_binop (TRUNC_DIV_EXPR,  
1794                              fold_convert (ssizetype, step), type_size);
1795
1796       access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1797       access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1798
1799       VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1800     }
1801
1802   if (dump_file && (dump_flags & TDF_DETAILS))
1803     {
1804       struct ptr_info_def *pi = DR_PTR_INFO (dr);
1805
1806       fprintf (dump_file, "\nCreated dr for ");
1807       print_generic_expr (dump_file, memref, TDF_SLIM);
1808       fprintf (dump_file, "\n\tbase_address: ");
1809       print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1810       fprintf (dump_file, "\n\toffset from base address: ");
1811       print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1812       fprintf (dump_file, "\n\tconstant offset from base address: ");
1813       print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1814       fprintf (dump_file, "\n\tbase_object: ");
1815       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1816       fprintf (dump_file, "\n\tstep: ");
1817       print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1818       fprintf (dump_file, "B\n\tmisalignment from base: ");
1819       print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1820       if (DR_OFFSET_MISALIGNMENT (dr))
1821         fprintf (dump_file, "B");
1822       if (DR_ALIGNED_TO (dr))
1823         {
1824           fprintf (dump_file, "\n\taligned to: ");
1825           print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1826         }
1827       fprintf (dump_file, "\n\tmemtag: ");
1828       print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1829       fprintf (dump_file, "\n");
1830       if (pi && pi->name_mem_tag)
1831         {
1832           fprintf (dump_file, "\n\tnametag: ");
1833           print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
1834           fprintf (dump_file, "\n");
1835         }
1836     }  
1837   return dr;  
1838 }
1839
1840
1841 /* Returns true when all the functions of a tree_vec CHREC are the
1842    same.  */
1843
1844 static bool 
1845 all_chrecs_equal_p (tree chrec)
1846 {
1847   int j;
1848
1849   for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
1850     {
1851       tree chrec_j = TREE_VEC_ELT (chrec, j);
1852       tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
1853       if (!integer_zerop 
1854           (chrec_fold_minus 
1855            (integer_type_node, chrec_j, chrec_j_1)))
1856         return false;
1857     }
1858   return true;
1859 }
1860
1861 /* Determine for each subscript in the data dependence relation DDR
1862    the distance.  */
1863
1864 void
1865 compute_subscript_distance (struct data_dependence_relation *ddr)
1866 {
1867   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1868     {
1869       unsigned int i;
1870       
1871       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1872         {
1873           tree conflicts_a, conflicts_b, difference;
1874           struct subscript *subscript;
1875           
1876           subscript = DDR_SUBSCRIPT (ddr, i);
1877           conflicts_a = SUB_CONFLICTS_IN_A (subscript);
1878           conflicts_b = SUB_CONFLICTS_IN_B (subscript);
1879
1880           if (TREE_CODE (conflicts_a) == TREE_VEC)
1881             {
1882               if (!all_chrecs_equal_p (conflicts_a))
1883                 {
1884                   SUB_DISTANCE (subscript) = chrec_dont_know;
1885                   return;
1886                 }
1887               else
1888                 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
1889             }
1890
1891           if (TREE_CODE (conflicts_b) == TREE_VEC)
1892             {
1893               if (!all_chrecs_equal_p (conflicts_b))
1894                 {
1895                   SUB_DISTANCE (subscript) = chrec_dont_know;
1896                   return;
1897                 }
1898               else
1899                 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
1900             }
1901
1902           difference = chrec_fold_minus 
1903             (integer_type_node, conflicts_b, conflicts_a);
1904           
1905           if (evolution_function_is_constant_p (difference))
1906             SUB_DISTANCE (subscript) = difference;
1907           
1908           else
1909             SUB_DISTANCE (subscript) = chrec_dont_know;
1910         }
1911     }
1912 }
1913
1914 /* Initialize a ddr.  */
1915
1916 struct data_dependence_relation *
1917 initialize_data_dependence_relation (struct data_reference *a, 
1918                                      struct data_reference *b)
1919 {
1920   struct data_dependence_relation *res;
1921   bool differ_p;
1922   unsigned int i;  
1923   
1924   res = xmalloc (sizeof (struct data_dependence_relation));
1925   DDR_A (res) = a;
1926   DDR_B (res) = b;
1927
1928   if (a == NULL || b == NULL)
1929     {
1930       DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
1931       return res;
1932     }   
1933
1934   /* When A and B are arrays and their dimensions differ, we directly
1935      initialize the relation to "there is no dependence": chrec_known.  */
1936   if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
1937       && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1938     {
1939       DDR_ARE_DEPENDENT (res) = chrec_known;
1940       return res;
1941     }
1942
1943     /* Compare the bases of the data-refs.  */
1944   if (!base_addr_differ_p (a, b, &differ_p))
1945     {
1946       /* Can't determine whether the data-refs access the same memory 
1947          region.  */
1948       DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
1949       return res;
1950     }
1951   if (differ_p)
1952     {
1953       DDR_ARE_DEPENDENT (res) = chrec_known;    
1954       return res;
1955     }
1956   
1957   DDR_AFFINE_P (res) = true;
1958   DDR_ARE_DEPENDENT (res) = NULL_TREE;
1959   DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
1960   DDR_SIZE_VECT (res) = 0;
1961   DDR_DIST_VECT (res) = NULL;
1962   DDR_DIR_VECT (res) = NULL;
1963       
1964   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1965     {
1966       struct subscript *subscript;
1967           
1968       subscript = xmalloc (sizeof (struct subscript));
1969       SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
1970       SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
1971       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1972       SUB_DISTANCE (subscript) = chrec_dont_know;
1973       VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
1974     }
1975   
1976   return res;
1977 }
1978
1979 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1980    description.  */
1981
1982 static inline void
1983 finalize_ddr_dependent (struct data_dependence_relation *ddr, 
1984                         tree chrec)
1985 {
1986   if (dump_file && (dump_flags & TDF_DETAILS))
1987     {
1988       fprintf (dump_file, "(dependence classified: ");
1989       print_generic_expr (dump_file, chrec, 0);
1990       fprintf (dump_file, ")\n");
1991     }
1992
1993   DDR_ARE_DEPENDENT (ddr) = chrec;  
1994   varray_clear (DDR_SUBSCRIPTS (ddr));
1995 }
1996
1997 /* The dependence relation DDR cannot be represented by a distance
1998    vector.  */
1999
2000 static inline void
2001 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2002 {
2003   if (dump_file && (dump_flags & TDF_DETAILS))
2004     fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2005
2006   DDR_AFFINE_P (ddr) = false;
2007 }
2008
2009 \f
2010
2011 /* This section contains the classic Banerjee tests.  */
2012
2013 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2014    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
2015
2016 static inline bool
2017 ziv_subscript_p (tree chrec_a, 
2018                  tree chrec_b)
2019 {
2020   return (evolution_function_is_constant_p (chrec_a)
2021           && evolution_function_is_constant_p (chrec_b));
2022 }
2023
2024 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2025    variable, i.e., if the SIV (Single Index Variable) test is true.  */
2026
2027 static bool
2028 siv_subscript_p (tree chrec_a,
2029                  tree chrec_b)
2030 {
2031   if ((evolution_function_is_constant_p (chrec_a)
2032        && evolution_function_is_univariate_p (chrec_b))
2033       || (evolution_function_is_constant_p (chrec_b)
2034           && evolution_function_is_univariate_p (chrec_a)))
2035     return true;
2036   
2037   if (evolution_function_is_univariate_p (chrec_a)
2038       && evolution_function_is_univariate_p (chrec_b))
2039     {
2040       switch (TREE_CODE (chrec_a))
2041         {
2042         case POLYNOMIAL_CHREC:
2043           switch (TREE_CODE (chrec_b))
2044             {
2045             case POLYNOMIAL_CHREC:
2046               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2047                 return false;
2048               
2049             default:
2050               return true;
2051             }
2052           
2053         default:
2054           return true;
2055         }
2056     }
2057   
2058   return false;
2059 }
2060
2061 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
2062    *OVERLAPS_B are initialized to the functions that describe the
2063    relation between the elements accessed twice by CHREC_A and
2064    CHREC_B.  For k >= 0, the following property is verified:
2065
2066    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2067
2068 static void 
2069 analyze_ziv_subscript (tree chrec_a, 
2070                        tree chrec_b, 
2071                        tree *overlaps_a,
2072                        tree *overlaps_b, 
2073                        tree *last_conflicts)
2074 {
2075   tree difference;
2076   
2077   if (dump_file && (dump_flags & TDF_DETAILS))
2078     fprintf (dump_file, "(analyze_ziv_subscript \n");
2079   
2080   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2081   
2082   switch (TREE_CODE (difference))
2083     {
2084     case INTEGER_CST:
2085       if (integer_zerop (difference))
2086         {
2087           /* The difference is equal to zero: the accessed index
2088              overlaps for each iteration in the loop.  */
2089           *overlaps_a = integer_zero_node;
2090           *overlaps_b = integer_zero_node;
2091           *last_conflicts = chrec_dont_know;
2092         }
2093       else
2094         {
2095           /* The accesses do not overlap.  */
2096           *overlaps_a = chrec_known;
2097           *overlaps_b = chrec_known;
2098           *last_conflicts = integer_zero_node;
2099         }
2100       break;
2101       
2102     default:
2103       /* We're not sure whether the indexes overlap.  For the moment, 
2104          conservatively answer "don't know".  */
2105       *overlaps_a = chrec_dont_know;
2106       *overlaps_b = chrec_dont_know;
2107       *last_conflicts = chrec_dont_know;
2108       break;
2109     }
2110   
2111   if (dump_file && (dump_flags & TDF_DETAILS))
2112     fprintf (dump_file, ")\n");
2113 }
2114
2115 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2116    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
2117    *OVERLAPS_B are initialized to the functions that describe the
2118    relation between the elements accessed twice by CHREC_A and
2119    CHREC_B.  For k >= 0, the following property is verified:
2120
2121    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2122
2123 static void
2124 analyze_siv_subscript_cst_affine (tree chrec_a, 
2125                                   tree chrec_b,
2126                                   tree *overlaps_a, 
2127                                   tree *overlaps_b, 
2128                                   tree *last_conflicts)
2129 {
2130   bool value0, value1, value2;
2131   tree difference = chrec_fold_minus 
2132     (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2133   
2134   if (!chrec_is_positive (initial_condition (difference), &value0))
2135     {
2136       *overlaps_a = chrec_dont_know;
2137       *overlaps_b = chrec_dont_know;
2138       *last_conflicts = chrec_dont_know;
2139       return;
2140     }
2141   else
2142     {
2143       if (value0 == false)
2144         {
2145           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2146             {
2147               *overlaps_a = chrec_dont_know;
2148               *overlaps_b = chrec_dont_know;      
2149               *last_conflicts = chrec_dont_know;
2150               return;
2151             }
2152           else
2153             {
2154               if (value1 == true)
2155                 {
2156                   /* Example:  
2157                      chrec_a = 12
2158                      chrec_b = {10, +, 1}
2159                   */
2160                   
2161                   if (tree_fold_divides_p 
2162                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2163                     {
2164                       *overlaps_a = integer_zero_node;
2165                       *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2166                                                  fold_build1 (ABS_EXPR,
2167                                                               integer_type_node,
2168                                                               difference),
2169                                                  CHREC_RIGHT (chrec_b));
2170                       *last_conflicts = integer_one_node;
2171                       return;
2172                     }
2173                   
2174                   /* When the step does not divides the difference, there are
2175                      no overlaps.  */
2176                   else
2177                     {
2178                       *overlaps_a = chrec_known;
2179                       *overlaps_b = chrec_known;      
2180                       *last_conflicts = integer_zero_node;
2181                       return;
2182                     }
2183                 }
2184               
2185               else
2186                 {
2187                   /* Example:  
2188                      chrec_a = 12
2189                      chrec_b = {10, +, -1}
2190                      
2191                      In this case, chrec_a will not overlap with chrec_b.  */
2192                   *overlaps_a = chrec_known;
2193                   *overlaps_b = chrec_known;
2194                   *last_conflicts = integer_zero_node;
2195                   return;
2196                 }
2197             }
2198         }
2199       else 
2200         {
2201           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2202             {
2203               *overlaps_a = chrec_dont_know;
2204               *overlaps_b = chrec_dont_know;      
2205               *last_conflicts = chrec_dont_know;
2206               return;
2207             }
2208           else
2209             {
2210               if (value2 == false)
2211                 {
2212                   /* Example:  
2213                      chrec_a = 3
2214                      chrec_b = {10, +, -1}
2215                   */
2216                   if (tree_fold_divides_p 
2217                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
2218                     {
2219                       *overlaps_a = integer_zero_node;
2220                       *overlaps_b = fold 
2221                         (build (EXACT_DIV_EXPR, integer_type_node, difference, 
2222                                 CHREC_RIGHT (chrec_b)));
2223                       *last_conflicts = integer_one_node;
2224                       return;
2225                     }
2226                   
2227                   /* When the step does not divides the difference, there
2228                      are no overlaps.  */
2229                   else
2230                     {
2231                       *overlaps_a = chrec_known;
2232                       *overlaps_b = chrec_known;      
2233                       *last_conflicts = integer_zero_node;
2234                       return;
2235                     }
2236                 }
2237               else
2238                 {
2239                   /* Example:  
2240                      chrec_a = 3  
2241                      chrec_b = {4, +, 1}
2242                  
2243                      In this case, chrec_a will not overlap with chrec_b.  */
2244                   *overlaps_a = chrec_known;
2245                   *overlaps_b = chrec_known;
2246                   *last_conflicts = integer_zero_node;
2247                   return;
2248                 }
2249             }
2250         }
2251     }
2252 }
2253
2254 /* Helper recursive function for initializing the matrix A.  Returns
2255    the initial value of CHREC.  */
2256
2257 static int
2258 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2259 {
2260   gcc_assert (chrec);
2261
2262   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2263     return int_cst_value (chrec);
2264
2265   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2266   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2267 }
2268
2269 #define FLOOR_DIV(x,y) ((x) / (y))
2270
2271 /* Solves the special case of the Diophantine equation: 
2272    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2273
2274    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
2275    number of iterations that loops X and Y run.  The overlaps will be
2276    constructed as evolutions in dimension DIM.  */
2277
2278 static void
2279 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, 
2280                                          tree *overlaps_a, tree *overlaps_b, 
2281                                          tree *last_conflicts, int dim)
2282 {
2283   if (((step_a > 0 && step_b > 0)
2284        || (step_a < 0 && step_b < 0)))
2285     {
2286       int step_overlaps_a, step_overlaps_b;
2287       int gcd_steps_a_b, last_conflict, tau2;
2288
2289       gcd_steps_a_b = gcd (step_a, step_b);
2290       step_overlaps_a = step_b / gcd_steps_a_b;
2291       step_overlaps_b = step_a / gcd_steps_a_b;
2292
2293       tau2 = FLOOR_DIV (niter, step_overlaps_a);
2294       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2295       last_conflict = tau2;
2296
2297       *overlaps_a = build_polynomial_chrec
2298         (dim, integer_zero_node,
2299          build_int_cst (NULL_TREE, step_overlaps_a));
2300       *overlaps_b = build_polynomial_chrec
2301         (dim, integer_zero_node,
2302          build_int_cst (NULL_TREE, step_overlaps_b));
2303       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2304     }
2305
2306   else
2307     {
2308       *overlaps_a = integer_zero_node;
2309       *overlaps_b = integer_zero_node;
2310       *last_conflicts = integer_zero_node;
2311     }
2312 }
2313
2314
2315 /* Solves the special case of a Diophantine equation where CHREC_A is
2316    an affine bivariate function, and CHREC_B is an affine univariate
2317    function.  For example, 
2318
2319    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2320    
2321    has the following overlapping functions: 
2322
2323    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2324    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2325    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2326
2327    FORNOW: This is a specialized implementation for a case occurring in
2328    a common benchmark.  Implement the general algorithm.  */
2329
2330 static void
2331 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 
2332                                       tree *overlaps_a, tree *overlaps_b, 
2333                                       tree *last_conflicts)
2334 {
2335   bool xz_p, yz_p, xyz_p;
2336   int step_x, step_y, step_z;
2337   int niter_x, niter_y, niter_z, niter;
2338   tree numiter_x, numiter_y, numiter_z;
2339   tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2340   tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2341   tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2342
2343   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2344   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2345   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2346
2347   numiter_x = number_of_iterations_in_loop 
2348     (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
2349   numiter_y = number_of_iterations_in_loop 
2350     (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2351   numiter_z = number_of_iterations_in_loop 
2352     (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2353
2354   if (TREE_CODE (numiter_x) != INTEGER_CST)
2355     numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
2356       ->estimated_nb_iterations;
2357   if (TREE_CODE (numiter_y) != INTEGER_CST)
2358     numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2359       ->estimated_nb_iterations;
2360   if (TREE_CODE (numiter_z) != INTEGER_CST)
2361     numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2362       ->estimated_nb_iterations;
2363
2364   if (chrec_contains_undetermined (numiter_x)
2365       || chrec_contains_undetermined (numiter_y)
2366       || chrec_contains_undetermined (numiter_z)
2367       || TREE_CODE (numiter_x) != INTEGER_CST
2368       || TREE_CODE (numiter_y) != INTEGER_CST
2369       || TREE_CODE (numiter_z) != INTEGER_CST)
2370     {
2371       *overlaps_a = chrec_dont_know;
2372       *overlaps_b = chrec_dont_know;
2373       *last_conflicts = chrec_dont_know;
2374       return;
2375     }
2376
2377   niter_x = int_cst_value (numiter_x);
2378   niter_y = int_cst_value (numiter_y);
2379   niter_z = int_cst_value (numiter_z);
2380
2381   niter = MIN (niter_x, niter_z);
2382   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2383                                            &overlaps_a_xz,
2384                                            &overlaps_b_xz,
2385                                            &last_conflicts_xz, 1);
2386   niter = MIN (niter_y, niter_z);
2387   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2388                                            &overlaps_a_yz,
2389                                            &overlaps_b_yz,
2390                                            &last_conflicts_yz, 2);
2391   niter = MIN (niter_x, niter_z);
2392   niter = MIN (niter_y, niter);
2393   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2394                                            &overlaps_a_xyz,
2395                                            &overlaps_b_xyz,
2396                                            &last_conflicts_xyz, 3);
2397
2398   xz_p = !integer_zerop (last_conflicts_xz);
2399   yz_p = !integer_zerop (last_conflicts_yz);
2400   xyz_p = !integer_zerop (last_conflicts_xyz);
2401
2402   if (xz_p || yz_p || xyz_p)
2403     {
2404       *overlaps_a = make_tree_vec (2);
2405       TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2406       TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2407       *overlaps_b = integer_zero_node;
2408       if (xz_p)
2409         {
2410           TREE_VEC_ELT (*overlaps_a, 0) = 
2411             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2412                              overlaps_a_xz);
2413           *overlaps_b = 
2414             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2415           *last_conflicts = last_conflicts_xz;
2416         }
2417       if (yz_p)
2418         {
2419           TREE_VEC_ELT (*overlaps_a, 1) = 
2420             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2421                              overlaps_a_yz);
2422           *overlaps_b = 
2423             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2424           *last_conflicts = last_conflicts_yz;
2425         }
2426       if (xyz_p)
2427         {
2428           TREE_VEC_ELT (*overlaps_a, 0) = 
2429             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2430                              overlaps_a_xyz);
2431           TREE_VEC_ELT (*overlaps_a, 1) = 
2432             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2433                              overlaps_a_xyz);
2434           *overlaps_b = 
2435             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2436           *last_conflicts = last_conflicts_xyz;
2437         }
2438     }
2439   else
2440     {
2441       *overlaps_a = integer_zero_node;
2442       *overlaps_b = integer_zero_node;
2443       *last_conflicts = integer_zero_node;
2444     }
2445 }
2446
2447 /* Determines the overlapping elements due to accesses CHREC_A and
2448    CHREC_B, that are affine functions.  This is a part of the
2449    subscript analyzer.  */
2450
2451 static void
2452 analyze_subscript_affine_affine (tree chrec_a, 
2453                                  tree chrec_b,
2454                                  tree *overlaps_a, 
2455                                  tree *overlaps_b, 
2456                                  tree *last_conflicts)
2457 {
2458   unsigned nb_vars_a, nb_vars_b, dim;
2459   int init_a, init_b, gamma, gcd_alpha_beta;
2460   int tau1, tau2;
2461   lambda_matrix A, U, S;
2462
2463   if (dump_file && (dump_flags & TDF_DETAILS))
2464     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2465   
2466   /* For determining the initial intersection, we have to solve a
2467      Diophantine equation.  This is the most time consuming part.
2468      
2469      For answering to the question: "Is there a dependence?" we have
2470      to prove that there exists a solution to the Diophantine
2471      equation, and that the solution is in the iteration domain,
2472      i.e. the solution is positive or zero, and that the solution
2473      happens before the upper bound loop.nb_iterations.  Otherwise
2474      there is no dependence.  This function outputs a description of
2475      the iterations that hold the intersections.  */
2476
2477   
2478   nb_vars_a = nb_vars_in_chrec (chrec_a);
2479   nb_vars_b = nb_vars_in_chrec (chrec_b);
2480
2481   dim = nb_vars_a + nb_vars_b;
2482   U = lambda_matrix_new (dim, dim);
2483   A = lambda_matrix_new (dim, 1);
2484   S = lambda_matrix_new (dim, 1);
2485
2486   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2487   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2488   gamma = init_b - init_a;
2489
2490   /* Don't do all the hard work of solving the Diophantine equation
2491      when we already know the solution: for example, 
2492      | {3, +, 1}_1
2493      | {3, +, 4}_2
2494      | gamma = 3 - 3 = 0.
2495      Then the first overlap occurs during the first iterations: 
2496      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2497   */
2498   if (gamma == 0)
2499     {
2500       if (nb_vars_a == 1 && nb_vars_b == 1)
2501         {
2502           int step_a, step_b;
2503           int niter, niter_a, niter_b;
2504           tree numiter_a, numiter_b;
2505
2506           numiter_a = number_of_iterations_in_loop 
2507             (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2508           numiter_b = number_of_iterations_in_loop 
2509             (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2510
2511           if (TREE_CODE (numiter_a) != INTEGER_CST)
2512             numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2513               ->estimated_nb_iterations;
2514           if (TREE_CODE (numiter_b) != INTEGER_CST)
2515             numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2516               ->estimated_nb_iterations;
2517           if (chrec_contains_undetermined (numiter_a)
2518               || chrec_contains_undetermined (numiter_b)
2519               || TREE_CODE (numiter_a) != INTEGER_CST
2520               || TREE_CODE (numiter_b) != INTEGER_CST)
2521             {
2522               *overlaps_a = chrec_dont_know;
2523               *overlaps_b = chrec_dont_know;
2524               *last_conflicts = chrec_dont_know;
2525               return;
2526             }
2527
2528           niter_a = int_cst_value (numiter_a);
2529           niter_b = int_cst_value (numiter_b);
2530           niter = MIN (niter_a, niter_b);
2531
2532           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2533           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2534
2535           compute_overlap_steps_for_affine_univar (niter, step_a, step_b, 
2536                                                    overlaps_a, overlaps_b, 
2537                                                    last_conflicts, 1);
2538         }
2539
2540       else if (nb_vars_a == 2 && nb_vars_b == 1)
2541         compute_overlap_steps_for_affine_1_2
2542           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2543
2544       else if (nb_vars_a == 1 && nb_vars_b == 2)
2545         compute_overlap_steps_for_affine_1_2
2546           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2547
2548       else
2549         {
2550           *overlaps_a = chrec_dont_know;
2551           *overlaps_b = chrec_dont_know;
2552           *last_conflicts = chrec_dont_know;
2553         }
2554       return;
2555     }
2556
2557   /* U.A = S */
2558   lambda_matrix_right_hermite (A, dim, 1, S, U);
2559
2560   if (S[0][0] < 0)
2561     {
2562       S[0][0] *= -1;
2563       lambda_matrix_row_negate (U, dim, 0);
2564     }
2565   gcd_alpha_beta = S[0][0];
2566
2567   /* The classic "gcd-test".  */
2568   if (!int_divides_p (gcd_alpha_beta, gamma))
2569     {
2570       /* The "gcd-test" has determined that there is no integer
2571          solution, i.e. there is no dependence.  */
2572       *overlaps_a = chrec_known;
2573       *overlaps_b = chrec_known;
2574       *last_conflicts = integer_zero_node;
2575     }
2576
2577   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
2578   else if (nb_vars_a == 1 && nb_vars_b == 1)
2579     {
2580       /* Both functions should have the same evolution sign.  */
2581       if (((A[0][0] > 0 && -A[1][0] > 0)
2582            || (A[0][0] < 0 && -A[1][0] < 0)))
2583         {
2584           /* The solutions are given by:
2585              | 
2586              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
2587              |                           [u21 u22]    [y0]
2588          
2589              For a given integer t.  Using the following variables,
2590          
2591              | i0 = u11 * gamma / gcd_alpha_beta
2592              | j0 = u12 * gamma / gcd_alpha_beta
2593              | i1 = u21
2594              | j1 = u22
2595          
2596              the solutions are:
2597          
2598              | x0 = i0 + i1 * t, 
2599              | y0 = j0 + j1 * t.  */
2600       
2601           int i0, j0, i1, j1;
2602
2603           /* X0 and Y0 are the first iterations for which there is a
2604              dependence.  X0, Y0 are two solutions of the Diophantine
2605              equation: chrec_a (X0) = chrec_b (Y0).  */
2606           int x0, y0;
2607           int niter, niter_a, niter_b;
2608           tree numiter_a, numiter_b;
2609
2610           numiter_a = number_of_iterations_in_loop 
2611             (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2612           numiter_b = number_of_iterations_in_loop 
2613             (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
2614
2615           if (TREE_CODE (numiter_a) != INTEGER_CST)
2616             numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
2617               ->estimated_nb_iterations;
2618           if (TREE_CODE (numiter_b) != INTEGER_CST)
2619             numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
2620               ->estimated_nb_iterations;
2621           if (chrec_contains_undetermined (numiter_a)
2622               || chrec_contains_undetermined (numiter_b)
2623               || TREE_CODE (numiter_a) != INTEGER_CST
2624               || TREE_CODE (numiter_b) != INTEGER_CST)
2625             {
2626               *overlaps_a = chrec_dont_know;
2627               *overlaps_b = chrec_dont_know;
2628               *last_conflicts = chrec_dont_know;
2629               return;
2630             }
2631
2632           niter_a = int_cst_value (numiter_a);
2633           niter_b = int_cst_value (numiter_b);
2634           niter = MIN (niter_a, niter_b);
2635
2636           i0 = U[0][0] * gamma / gcd_alpha_beta;
2637           j0 = U[0][1] * gamma / gcd_alpha_beta;
2638           i1 = U[1][0];
2639           j1 = U[1][1];
2640
2641           if ((i1 == 0 && i0 < 0)
2642               || (j1 == 0 && j0 < 0))
2643             {
2644               /* There is no solution.  
2645                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 
2646                  falls in here, but for the moment we don't look at the 
2647                  upper bound of the iteration domain.  */
2648               *overlaps_a = chrec_known;
2649               *overlaps_b = chrec_known;
2650               *last_conflicts = integer_zero_node;
2651             }
2652
2653           else 
2654             {
2655               if (i1 > 0)
2656                 {
2657                   tau1 = CEIL (-i0, i1);
2658                   tau2 = FLOOR_DIV (niter - i0, i1);
2659
2660                   if (j1 > 0)
2661                     {
2662                       int last_conflict, min_multiple;
2663                       tau1 = MAX (tau1, CEIL (-j0, j1));
2664                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2665
2666                       x0 = i1 * tau1 + i0;
2667                       y0 = j1 * tau1 + j0;
2668
2669                       /* At this point (x0, y0) is one of the
2670                          solutions to the Diophantine equation.  The
2671                          next step has to compute the smallest
2672                          positive solution: the first conflicts.  */
2673                       min_multiple = MIN (x0 / i1, y0 / j1);
2674                       x0 -= i1 * min_multiple;
2675                       y0 -= j1 * min_multiple;
2676
2677                       tau1 = (x0 - i0)/i1;
2678                       last_conflict = tau2 - tau1;
2679
2680                       *overlaps_a = build_polynomial_chrec
2681                         (1,
2682                          build_int_cst (NULL_TREE, x0),
2683                          build_int_cst (NULL_TREE, i1));
2684                       *overlaps_b = build_polynomial_chrec
2685                         (1,
2686                          build_int_cst (NULL_TREE, y0),
2687                          build_int_cst (NULL_TREE, j1));
2688                       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2689                     }
2690                   else
2691                     {
2692                       /* FIXME: For the moment, the upper bound of the
2693                          iteration domain for j is not checked.  */
2694                       *overlaps_a = chrec_dont_know;
2695                       *overlaps_b = chrec_dont_know;
2696                       *last_conflicts = chrec_dont_know;
2697                     }
2698                 }
2699           
2700               else
2701                 {
2702                   /* FIXME: For the moment, the upper bound of the
2703                      iteration domain for i is not checked.  */
2704                   *overlaps_a = chrec_dont_know;
2705                   *overlaps_b = chrec_dont_know;
2706                   *last_conflicts = chrec_dont_know;
2707                 }
2708             }
2709         }
2710       else
2711         {
2712           *overlaps_a = chrec_dont_know;
2713           *overlaps_b = chrec_dont_know;
2714           *last_conflicts = chrec_dont_know;
2715         }
2716     }
2717
2718   else
2719     {
2720       *overlaps_a = chrec_dont_know;
2721       *overlaps_b = chrec_dont_know;
2722       *last_conflicts = chrec_dont_know;
2723     }
2724
2725
2726   if (dump_file && (dump_flags & TDF_DETAILS))
2727     {
2728       fprintf (dump_file, "  (overlaps_a = ");
2729       print_generic_expr (dump_file, *overlaps_a, 0);
2730       fprintf (dump_file, ")\n  (overlaps_b = ");
2731       print_generic_expr (dump_file, *overlaps_b, 0);
2732       fprintf (dump_file, ")\n");
2733     }
2734   
2735   if (dump_file && (dump_flags & TDF_DETAILS))
2736     fprintf (dump_file, ")\n");
2737 }
2738
2739 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
2740    *OVERLAPS_B are initialized to the functions that describe the
2741    relation between the elements accessed twice by CHREC_A and
2742    CHREC_B.  For k >= 0, the following property is verified:
2743
2744    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2745
2746 static void
2747 analyze_siv_subscript (tree chrec_a, 
2748                        tree chrec_b,
2749                        tree *overlaps_a, 
2750                        tree *overlaps_b, 
2751                        tree *last_conflicts)
2752 {
2753   if (dump_file && (dump_flags & TDF_DETAILS))
2754     fprintf (dump_file, "(analyze_siv_subscript \n");
2755   
2756   if (evolution_function_is_constant_p (chrec_a)
2757       && evolution_function_is_affine_p (chrec_b))
2758     analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 
2759                                       overlaps_a, overlaps_b, last_conflicts);
2760   
2761   else if (evolution_function_is_affine_p (chrec_a)
2762            && evolution_function_is_constant_p (chrec_b))
2763     analyze_siv_subscript_cst_affine (chrec_b, chrec_a, 
2764                                       overlaps_b, overlaps_a, last_conflicts);
2765   
2766   else if (evolution_function_is_affine_p (chrec_a)
2767            && evolution_function_is_affine_p (chrec_b))
2768     analyze_subscript_affine_affine (chrec_a, chrec_b, 
2769                                      overlaps_a, overlaps_b, last_conflicts);
2770   else
2771     {
2772       *overlaps_a = chrec_dont_know;
2773       *overlaps_b = chrec_dont_know;
2774       *last_conflicts = chrec_dont_know;
2775     }
2776   
2777   if (dump_file && (dump_flags & TDF_DETAILS))
2778     fprintf (dump_file, ")\n");
2779 }
2780
2781 /* Return true when the evolution steps of an affine CHREC divide the
2782    constant CST.  */
2783
2784 static bool
2785 chrec_steps_divide_constant_p (tree chrec, 
2786                                tree cst)
2787 {
2788   switch (TREE_CODE (chrec))
2789     {
2790     case POLYNOMIAL_CHREC:
2791       return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
2792               && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
2793       
2794     default:
2795       /* On the initial condition, return true.  */
2796       return true;
2797     }
2798 }
2799
2800 /* Analyze a MIV (Multiple Index Variable) subscript.  *OVERLAPS_A and
2801    *OVERLAPS_B are initialized to the functions that describe the
2802    relation between the elements accessed twice by CHREC_A and
2803    CHREC_B.  For k >= 0, the following property is verified:
2804
2805    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2806
2807 static void
2808 analyze_miv_subscript (tree chrec_a, 
2809                        tree chrec_b, 
2810                        tree *overlaps_a, 
2811                        tree *overlaps_b, 
2812                        tree *last_conflicts)
2813 {
2814   /* FIXME:  This is a MIV subscript, not yet handled.
2815      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from 
2816      (A[i] vs. A[j]).  
2817      
2818      In the SIV test we had to solve a Diophantine equation with two
2819      variables.  In the MIV case we have to solve a Diophantine
2820      equation with 2*n variables (if the subscript uses n IVs).
2821   */
2822   tree difference;
2823   
2824   if (dump_file && (dump_flags & TDF_DETAILS))
2825     fprintf (dump_file, "(analyze_miv_subscript \n");
2826   
2827   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2828   
2829   if (chrec_zerop (difference))
2830     {
2831       /* Access functions are the same: all the elements are accessed
2832          in the same order.  */
2833       *overlaps_a = integer_zero_node;
2834       *overlaps_b = integer_zero_node;
2835       *last_conflicts = number_of_iterations_in_loop 
2836         (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
2837     }
2838   
2839   else if (evolution_function_is_constant_p (difference)
2840            /* For the moment, the following is verified:
2841               evolution_function_is_affine_multivariate_p (chrec_a) */
2842            && !chrec_steps_divide_constant_p (chrec_a, difference))
2843     {
2844       /* testsuite/.../ssa-chrec-33.c
2845          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2 
2846         
2847          The difference is 1, and the evolution steps are equal to 2,
2848          consequently there are no overlapping elements.  */
2849       *overlaps_a = chrec_known;
2850       *overlaps_b = chrec_known;
2851       *last_conflicts = integer_zero_node;
2852     }
2853   
2854   else if (evolution_function_is_affine_multivariate_p (chrec_a)
2855            && evolution_function_is_affine_multivariate_p (chrec_b))
2856     {
2857       /* testsuite/.../ssa-chrec-35.c
2858          {0, +, 1}_2  vs.  {0, +, 1}_3
2859          the overlapping elements are respectively located at iterations:
2860          {0, +, 1}_x and {0, +, 1}_x, 
2861          in other words, we have the equality: 
2862          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2863          
2864          Other examples: 
2865          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = 
2866          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2867
2868          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = 
2869          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2870       */
2871       analyze_subscript_affine_affine (chrec_a, chrec_b, 
2872                                        overlaps_a, overlaps_b, last_conflicts);
2873     }
2874   
2875   else
2876     {
2877       /* When the analysis is too difficult, answer "don't know".  */
2878       *overlaps_a = chrec_dont_know;
2879       *overlaps_b = chrec_dont_know;
2880       *last_conflicts = chrec_dont_know;
2881     }
2882   
2883   if (dump_file && (dump_flags & TDF_DETAILS))
2884     fprintf (dump_file, ")\n");
2885 }
2886
2887 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
2888    OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
2889    two functions that describe the iterations that contain conflicting
2890    elements.
2891    
2892    Remark: For an integer k >= 0, the following equality is true:
2893    
2894    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2895 */
2896
2897 static void 
2898 analyze_overlapping_iterations (tree chrec_a, 
2899                                 tree chrec_b, 
2900                                 tree *overlap_iterations_a, 
2901                                 tree *overlap_iterations_b, 
2902                                 tree *last_conflicts)
2903 {
2904   if (dump_file && (dump_flags & TDF_DETAILS))
2905     {
2906       fprintf (dump_file, "(analyze_overlapping_iterations \n");
2907       fprintf (dump_file, "  (chrec_a = ");
2908       print_generic_expr (dump_file, chrec_a, 0);
2909       fprintf (dump_file, ")\n  chrec_b = ");
2910       print_generic_expr (dump_file, chrec_b, 0);
2911       fprintf (dump_file, ")\n");
2912     }
2913   
2914   if (chrec_a == NULL_TREE
2915       || chrec_b == NULL_TREE
2916       || chrec_contains_undetermined (chrec_a)
2917       || chrec_contains_undetermined (chrec_b)
2918       || chrec_contains_symbols (chrec_a)
2919       || chrec_contains_symbols (chrec_b))
2920     {
2921       *overlap_iterations_a = chrec_dont_know;
2922       *overlap_iterations_b = chrec_dont_know;
2923     }
2924   
2925   else if (ziv_subscript_p (chrec_a, chrec_b))
2926     analyze_ziv_subscript (chrec_a, chrec_b, 
2927                            overlap_iterations_a, overlap_iterations_b,
2928                            last_conflicts);
2929   
2930   else if (siv_subscript_p (chrec_a, chrec_b))
2931     analyze_siv_subscript (chrec_a, chrec_b, 
2932                            overlap_iterations_a, overlap_iterations_b, 
2933                            last_conflicts);
2934   
2935   else
2936     analyze_miv_subscript (chrec_a, chrec_b, 
2937                            overlap_iterations_a, overlap_iterations_b,
2938                            last_conflicts);
2939   
2940   if (dump_file && (dump_flags & TDF_DETAILS))
2941     {
2942       fprintf (dump_file, "  (overlap_iterations_a = ");
2943       print_generic_expr (dump_file, *overlap_iterations_a, 0);
2944       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
2945       print_generic_expr (dump_file, *overlap_iterations_b, 0);
2946       fprintf (dump_file, ")\n");
2947     }
2948 }
2949
2950 \f
2951
2952 /* This section contains the affine functions dependences detector.  */
2953
2954 /* Computes the conflicting iterations, and initialize DDR.  */
2955
2956 static void
2957 subscript_dependence_tester (struct data_dependence_relation *ddr)
2958 {
2959   unsigned int i;
2960   struct data_reference *dra = DDR_A (ddr);
2961   struct data_reference *drb = DDR_B (ddr);
2962   tree last_conflicts;
2963   
2964   if (dump_file && (dump_flags & TDF_DETAILS))
2965     fprintf (dump_file, "(subscript_dependence_tester \n");
2966   
2967   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2968     {
2969       tree overlaps_a, overlaps_b;
2970       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2971       
2972       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 
2973                                       DR_ACCESS_FN (drb, i),
2974                                       &overlaps_a, &overlaps_b, 
2975                                       &last_conflicts);
2976       
2977       if (chrec_contains_undetermined (overlaps_a)
2978           || chrec_contains_undetermined (overlaps_b))
2979         {
2980           finalize_ddr_dependent (ddr, chrec_dont_know);
2981           break;
2982         }
2983       
2984       else if (overlaps_a == chrec_known
2985                || overlaps_b == chrec_known)
2986         {
2987           finalize_ddr_dependent (ddr, chrec_known);
2988           break;
2989         }
2990       
2991       else
2992         {
2993           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
2994           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
2995           SUB_LAST_CONFLICT (subscript) = last_conflicts;
2996         }
2997     }
2998   
2999   if (dump_file && (dump_flags & TDF_DETAILS))
3000     fprintf (dump_file, ")\n");
3001 }
3002
3003 /* Compute the classic per loop distance vector.
3004
3005    DDR is the data dependence relation to build a vector from.
3006    NB_LOOPS is the total number of loops we are considering.
3007    FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
3008    loop nest.  
3009    Return FALSE if the dependence relation is outside of the loop nest
3010    starting at FIRST_LOOP_DEPTH. 
3011    Return TRUE otherwise.  */
3012
3013 static bool
3014 build_classic_dist_vector (struct data_dependence_relation *ddr, 
3015                            int nb_loops, int first_loop_depth)
3016 {
3017   unsigned i;
3018   lambda_vector dist_v, init_v;
3019   
3020   dist_v = lambda_vector_new (nb_loops);
3021   init_v = lambda_vector_new (nb_loops);
3022   lambda_vector_clear (dist_v, nb_loops);
3023   lambda_vector_clear (init_v, nb_loops);
3024   
3025   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3026     return true;
3027   
3028   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3029     {
3030       tree access_fn_a, access_fn_b;
3031       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3032
3033       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3034         {
3035           non_affine_dependence_relation (ddr);
3036           return true;
3037         }
3038
3039       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3040       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3041
3042       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC 
3043           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3044         {
3045           int dist, loop_nb, loop_depth;
3046           int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3047           int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3048           struct loop *loop_a = current_loops->parray[loop_nb_a];
3049           struct loop *loop_b = current_loops->parray[loop_nb_b];
3050
3051           /* If the loop for either variable is at a lower depth than 
3052              the first_loop's depth, then we can't possibly have a
3053              dependency at this level of the loop.  */
3054              
3055           if (loop_a->depth < first_loop_depth
3056               || loop_b->depth < first_loop_depth)
3057             return false;
3058
3059           if (loop_nb_a != loop_nb_b
3060               && !flow_loop_nested_p (loop_a, loop_b)
3061               && !flow_loop_nested_p (loop_b, loop_a))
3062             {
3063               /* Example: when there are two consecutive loops,
3064
3065                  | loop_1
3066                  |   A[{0, +, 1}_1]
3067                  | endloop_1
3068                  | loop_2
3069                  |   A[{0, +, 1}_2]
3070                  | endloop_2
3071
3072                  the dependence relation cannot be captured by the
3073                  distance abstraction.  */
3074               non_affine_dependence_relation (ddr);
3075               return true;
3076             }
3077
3078           /* The dependence is carried by the outermost loop.  Example:
3079              | loop_1
3080              |   A[{4, +, 1}_1]
3081              |   loop_2
3082              |     A[{5, +, 1}_2]
3083              |   endloop_2
3084              | endloop_1
3085              In this case, the dependence is carried by loop_1.  */
3086           loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3087           loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3088
3089           /* If the loop number is still greater than the number of
3090              loops we've been asked to analyze, or negative,
3091              something is borked.  */
3092           gcc_assert (loop_depth >= 0);
3093           gcc_assert (loop_depth < nb_loops);
3094           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3095             {
3096               non_affine_dependence_relation (ddr);
3097               return true;
3098             }
3099           
3100           dist = int_cst_value (SUB_DISTANCE (subscript));
3101
3102           /* This is the subscript coupling test.  
3103              | loop i = 0, N, 1
3104              |   T[i+1][i] = ...
3105              |   ... = T[i][i]
3106              | endloop
3107              There is no dependence.  */
3108           if (init_v[loop_depth] != 0
3109               && dist_v[loop_depth] != dist)
3110             {
3111               finalize_ddr_dependent (ddr, chrec_known);
3112               return true;
3113             }
3114
3115           dist_v[loop_depth] = dist;
3116           init_v[loop_depth] = 1;
3117         }
3118     }
3119   
3120   /* There is a distance of 1 on all the outer loops: 
3121      
3122      Example: there is a dependence of distance 1 on loop_1 for the array A.
3123      | loop_1
3124      |   A[5] = ...
3125      | endloop
3126   */
3127   {
3128     struct loop *lca, *loop_a, *loop_b;
3129     struct data_reference *a = DDR_A (ddr);
3130     struct data_reference *b = DDR_B (ddr);
3131     int lca_depth;
3132     loop_a = loop_containing_stmt (DR_STMT (a));
3133     loop_b = loop_containing_stmt (DR_STMT (b));
3134     
3135     /* Get the common ancestor loop.  */
3136     lca = find_common_loop (loop_a, loop_b); 
3137     
3138     lca_depth = lca->depth;
3139     lca_depth -= first_loop_depth;
3140     gcc_assert (lca_depth >= 0);
3141     gcc_assert (lca_depth < nb_loops);
3142
3143     /* For each outer loop where init_v is not set, the accesses are
3144        in dependence of distance 1 in the loop.  */
3145     if (lca != loop_a
3146         && lca != loop_b
3147         && init_v[lca_depth] == 0)
3148       dist_v[lca_depth] = 1;
3149     
3150     lca = lca->outer;
3151     
3152     if (lca)
3153       {
3154         lca_depth = lca->depth - first_loop_depth;
3155         while (lca->depth != 0)
3156           {
3157             /* If we're considering just a sub-nest, then don't record
3158                any information on the outer loops.  */
3159             if (lca_depth < 0)
3160               break;
3161
3162             gcc_assert (lca_depth < nb_loops);
3163
3164             if (init_v[lca_depth] == 0)
3165               dist_v[lca_depth] = 1;
3166             lca = lca->outer;
3167             lca_depth = lca->depth - first_loop_depth;
3168           
3169           }
3170       }
3171   }
3172   
3173   DDR_DIST_VECT (ddr) = dist_v;
3174   DDR_SIZE_VECT (ddr) = nb_loops;
3175   return true;
3176 }
3177
3178 /* Compute the classic per loop direction vector.  
3179
3180    DDR is the data dependence relation to build a vector from.
3181    NB_LOOPS is the total number of loops we are considering.
3182    FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed 
3183    loop nest.
3184    Return FALSE if the dependence relation is outside of the loop nest
3185    at FIRST_LOOP_DEPTH. 
3186    Return TRUE otherwise.  */
3187
3188 static bool
3189 build_classic_dir_vector (struct data_dependence_relation *ddr, 
3190                           int nb_loops, int first_loop_depth)
3191 {
3192   unsigned i;
3193   lambda_vector dir_v, init_v;
3194   
3195   dir_v = lambda_vector_new (nb_loops);
3196   init_v = lambda_vector_new (nb_loops);
3197   lambda_vector_clear (dir_v, nb_loops);
3198   lambda_vector_clear (init_v, nb_loops);
3199   
3200   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3201     return true;
3202   
3203   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3204     {
3205       tree access_fn_a, access_fn_b;
3206       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3207
3208       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3209         {
3210           non_affine_dependence_relation (ddr);
3211           return true;
3212         }
3213
3214       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
3215       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
3216       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3217           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3218         {
3219           int dist, loop_nb, loop_depth;
3220           enum data_dependence_direction dir = dir_star;
3221           int loop_nb_a = CHREC_VARIABLE (access_fn_a);
3222           int loop_nb_b = CHREC_VARIABLE (access_fn_b);
3223           struct loop *loop_a = current_loops->parray[loop_nb_a];
3224           struct loop *loop_b = current_loops->parray[loop_nb_b];
3225  
3226           /* If the loop for either variable is at a lower depth than 
3227              the first_loop's depth, then we can't possibly have a
3228              dependency at this level of the loop.  */
3229              
3230           if (loop_a->depth < first_loop_depth
3231               || loop_b->depth < first_loop_depth)
3232             return false;
3233
3234           if (loop_nb_a != loop_nb_b
3235               && !flow_loop_nested_p (loop_a, loop_b)
3236               && !flow_loop_nested_p (loop_b, loop_a))
3237             {
3238               /* Example: when there are two consecutive loops,
3239
3240                  | loop_1
3241                  |   A[{0, +, 1}_1]
3242                  | endloop_1
3243                  | loop_2
3244                  |   A[{0, +, 1}_2]
3245                  | endloop_2
3246
3247                  the dependence relation cannot be captured by the
3248                  distance abstraction.  */
3249               non_affine_dependence_relation (ddr);
3250               return true;
3251             }
3252
3253           /* The dependence is carried by the outermost loop.  Example:
3254              | loop_1
3255              |   A[{4, +, 1}_1]
3256              |   loop_2
3257              |     A[{5, +, 1}_2]
3258              |   endloop_2
3259              | endloop_1
3260              In this case, the dependence is carried by loop_1.  */
3261           loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
3262           loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
3263
3264           /* If the loop number is still greater than the number of
3265              loops we've been asked to analyze, or negative,
3266              something is borked.  */
3267           gcc_assert (loop_depth >= 0);
3268           gcc_assert (loop_depth < nb_loops);
3269
3270           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3271             {
3272               non_affine_dependence_relation (ddr);
3273               return true;
3274             }
3275
3276           dist = int_cst_value (SUB_DISTANCE (subscript));
3277
3278           if (dist == 0)
3279             dir = dir_equal;
3280           else if (dist > 0)
3281             dir = dir_positive;
3282           else if (dist < 0)
3283             dir = dir_negative;
3284           
3285           /* This is the subscript coupling test.  
3286              | loop i = 0, N, 1
3287              |   T[i+1][i] = ...
3288              |   ... = T[i][i]
3289              | endloop
3290              There is no dependence.  */
3291           if (init_v[loop_depth] != 0
3292               && dir != dir_star
3293               && (enum data_dependence_direction) dir_v[loop_depth] != dir
3294               && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
3295             {
3296               finalize_ddr_dependent (ddr, chrec_known);
3297               return true;
3298             }
3299           
3300           dir_v[loop_depth] = dir;
3301           init_v[loop_depth] = 1;
3302         }
3303     }
3304   
3305   /* There is a distance of 1 on all the outer loops: 
3306      
3307      Example: there is a dependence of distance 1 on loop_1 for the array A.
3308      | loop_1
3309      |   A[5] = ...
3310      | endloop
3311   */
3312   {
3313     struct loop *lca, *loop_a, *loop_b;
3314     struct data_reference *a = DDR_A (ddr);
3315     struct data_reference *b = DDR_B (ddr);
3316     int lca_depth;
3317     loop_a = loop_containing_stmt (DR_STMT (a));
3318     loop_b = loop_containing_stmt (DR_STMT (b));
3319     
3320     /* Get the common ancestor loop.  */
3321     lca = find_common_loop (loop_a, loop_b); 
3322     lca_depth = lca->depth - first_loop_depth;
3323
3324     gcc_assert (lca_depth >= 0);
3325     gcc_assert (lca_depth < nb_loops);
3326
3327     /* For each outer loop where init_v is not set, the accesses are
3328        in dependence of distance 1 in the loop.  */
3329     if (lca != loop_a
3330         && lca != loop_b
3331         && init_v[lca_depth] == 0)
3332       dir_v[lca_depth] = dir_positive;
3333     
3334     lca = lca->outer;
3335     if (lca)
3336       {
3337         lca_depth = lca->depth - first_loop_depth;
3338         while (lca->depth != 0)
3339           {
3340             /* If we're considering just a sub-nest, then don't record
3341                any information on the outer loops.  */
3342             if (lca_depth < 0)
3343               break;
3344
3345             gcc_assert (lca_depth < nb_loops);
3346
3347             if (init_v[lca_depth] == 0)
3348               dir_v[lca_depth] = dir_positive;
3349             lca = lca->outer;
3350             lca_depth = lca->depth - first_loop_depth;
3351            
3352           }
3353       }
3354   }
3355   
3356   DDR_DIR_VECT (ddr) = dir_v;
3357   DDR_SIZE_VECT (ddr) = nb_loops;
3358   return true;
3359 }
3360
3361 /* Returns true when all the access functions of A are affine or
3362    constant.  */
3363
3364 static bool 
3365 access_functions_are_affine_or_constant_p (struct data_reference *a)
3366 {
3367   unsigned int i;
3368   VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
3369   tree t;
3370   
3371   for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
3372     if (!evolution_function_is_constant_p (t)
3373         && !evolution_function_is_affine_multivariate_p (t))
3374       return false;
3375   
3376   return true;
3377 }
3378
3379 /* This computes the affine dependence relation between A and B.
3380    CHREC_KNOWN is used for representing the independence between two
3381    accesses, while CHREC_DONT_KNOW is used for representing the unknown
3382    relation.
3383    
3384    Note that it is possible to stop the computation of the dependence
3385    relation the first time we detect a CHREC_KNOWN element for a given
3386    subscript.  */
3387
3388 void
3389 compute_affine_dependence (struct data_dependence_relation *ddr)
3390 {
3391   struct data_reference *dra = DDR_A (ddr);
3392   struct data_reference *drb = DDR_B (ddr);
3393   
3394   if (dump_file && (dump_flags & TDF_DETAILS))
3395     {
3396       fprintf (dump_file, "(compute_affine_dependence\n");
3397       fprintf (dump_file, "  (stmt_a = \n");
3398       print_generic_expr (dump_file, DR_STMT (dra), 0);
3399       fprintf (dump_file, ")\n  (stmt_b = \n");
3400       print_generic_expr (dump_file, DR_STMT (drb), 0);
3401       fprintf (dump_file, ")\n");
3402     }
3403   
3404   /* Analyze only when the dependence relation is not yet known.  */
3405   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3406     {
3407       if (access_functions_are_affine_or_constant_p (dra)
3408           && access_functions_are_affine_or_constant_p (drb))
3409         subscript_dependence_tester (ddr);
3410       
3411       /* As a last case, if the dependence cannot be determined, or if
3412          the dependence is considered too difficult to determine, answer