OSDN Git Service

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