OSDN Git Service

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