OSDN Git Service

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