OSDN Git Service

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