OSDN Git Service

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