OSDN Git Service

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