OSDN Git Service

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