OSDN Git Service

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