OSDN Git Service

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