OSDN Git Service

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