Daily bump.
[official-gcc.git] / gcc / tree-data-ref.c
blob387da6cb40ecae584667c94dfb848a3ee1c98d5c
1 /* Data references and dependences detectors.
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass walks a given loop structure searching for array
22 references. The information about the array accesses is recorded
23 in DATA_REFERENCE structures.
25 The basic test for determining the dependences is:
26 given two access functions chrec1 and chrec2 to a same array, and
27 x and y two vectors from the iteration domain, the same element of
28 the array is accessed twice at iterations x and y if and only if:
29 | chrec1 (x) == chrec2 (y).
31 The goals of this analysis are:
33 - to determine the independence: the relation between two
34 independent accesses is qualified with the chrec_known (this
35 information allows a loop parallelization),
37 - when two data references access the same data, to qualify the
38 dependence relation with classic dependence representations:
40 - distance vectors
41 - direction vectors
42 - loop carried level dependence
43 - polyhedron dependence
44 or with the chains of recurrences based representation,
46 - to define a knowledge base for storing the data dependence
47 information,
49 - to define an interface to access this data.
52 Definitions:
54 - subscript: given two array accesses a subscript is the tuple
55 composed of the access functions for a given dimension. Example:
56 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
57 (f1, g1), (f2, g2), (f3, g3).
59 - Diophantine equation: an equation whose coefficients and
60 solutions are integer constants, for example the equation
61 | 3*x + 2*y = 1
62 has an integer solution x = 1 and y = -1.
64 References:
66 - "Advanced Compilation for High Performance Computing" by Randy
67 Allen and Ken Kennedy.
68 http://citeseer.ist.psu.edu/goff91practical.html
70 - "Loop Transformations for Restructuring Compilers - The Foundations"
71 by Utpal Banerjee.
76 #include "config.h"
77 #include "system.h"
78 #include "coretypes.h"
79 #include "tree.h"
80 #include "expr.h"
81 #include "gimple-pretty-print.h"
82 #include "predict.h"
83 #include "vec.h"
84 #include "hashtab.h"
85 #include "hash-set.h"
86 #include "machmode.h"
87 #include "tm.h"
88 #include "hard-reg-set.h"
89 #include "input.h"
90 #include "function.h"
91 #include "dominance.h"
92 #include "cfg.h"
93 #include "basic-block.h"
94 #include "tree-ssa-alias.h"
95 #include "internal-fn.h"
96 #include "gimple-expr.h"
97 #include "is-a.h"
98 #include "gimple.h"
99 #include "gimple-iterator.h"
100 #include "tree-ssa-loop-niter.h"
101 #include "tree-ssa-loop.h"
102 #include "tree-ssa.h"
103 #include "cfgloop.h"
104 #include "tree-data-ref.h"
105 #include "tree-scalar-evolution.h"
106 #include "dumpfile.h"
107 #include "langhooks.h"
108 #include "tree-affine.h"
109 #include "params.h"
111 static struct datadep_stats
113 int num_dependence_tests;
114 int num_dependence_dependent;
115 int num_dependence_independent;
116 int num_dependence_undetermined;
118 int num_subscript_tests;
119 int num_subscript_undetermined;
120 int num_same_subscript_function;
122 int num_ziv;
123 int num_ziv_independent;
124 int num_ziv_dependent;
125 int num_ziv_unimplemented;
127 int num_siv;
128 int num_siv_independent;
129 int num_siv_dependent;
130 int num_siv_unimplemented;
132 int num_miv;
133 int num_miv_independent;
134 int num_miv_dependent;
135 int num_miv_unimplemented;
136 } dependence_stats;
138 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
139 struct data_reference *,
140 struct data_reference *,
141 struct loop *);
142 /* Returns true iff A divides B. */
144 static inline bool
145 tree_fold_divides_p (const_tree a, const_tree b)
147 gcc_assert (TREE_CODE (a) == INTEGER_CST);
148 gcc_assert (TREE_CODE (b) == INTEGER_CST);
149 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));
152 /* Returns true iff A divides B. */
154 static inline bool
155 int_divides_p (int a, int b)
157 return ((b % a) == 0);
162 /* Dump into FILE all the data references from DATAREFS. */
164 static void
165 dump_data_references (FILE *file, vec<data_reference_p> datarefs)
167 unsigned int i;
168 struct data_reference *dr;
170 FOR_EACH_VEC_ELT (datarefs, i, dr)
171 dump_data_reference (file, dr);
174 /* Unified dump into FILE all the data references from DATAREFS. */
176 DEBUG_FUNCTION void
177 debug (vec<data_reference_p> &ref)
179 dump_data_references (stderr, ref);
182 DEBUG_FUNCTION void
183 debug (vec<data_reference_p> *ptr)
185 if (ptr)
186 debug (*ptr);
187 else
188 fprintf (stderr, "<nil>\n");
192 /* Dump into STDERR all the data references from DATAREFS. */
194 DEBUG_FUNCTION void
195 debug_data_references (vec<data_reference_p> datarefs)
197 dump_data_references (stderr, datarefs);
200 /* Print to STDERR the data_reference DR. */
202 DEBUG_FUNCTION void
203 debug_data_reference (struct data_reference *dr)
205 dump_data_reference (stderr, dr);
208 /* Dump function for a DATA_REFERENCE structure. */
210 void
211 dump_data_reference (FILE *outf,
212 struct data_reference *dr)
214 unsigned int i;
216 fprintf (outf, "#(Data Ref: \n");
217 fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
218 fprintf (outf, "# stmt: ");
219 print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
220 fprintf (outf, "# ref: ");
221 print_generic_stmt (outf, DR_REF (dr), 0);
222 fprintf (outf, "# base_object: ");
223 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
225 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
227 fprintf (outf, "# Access function %d: ", i);
228 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
230 fprintf (outf, "#)\n");
233 /* Unified dump function for a DATA_REFERENCE structure. */
235 DEBUG_FUNCTION void
236 debug (data_reference &ref)
238 dump_data_reference (stderr, &ref);
241 DEBUG_FUNCTION void
242 debug (data_reference *ptr)
244 if (ptr)
245 debug (*ptr);
246 else
247 fprintf (stderr, "<nil>\n");
251 /* Dumps the affine function described by FN to the file OUTF. */
253 static void
254 dump_affine_function (FILE *outf, affine_fn fn)
256 unsigned i;
257 tree coef;
259 print_generic_expr (outf, fn[0], TDF_SLIM);
260 for (i = 1; fn.iterate (i, &coef); i++)
262 fprintf (outf, " + ");
263 print_generic_expr (outf, coef, TDF_SLIM);
264 fprintf (outf, " * x_%u", i);
268 /* Dumps the conflict function CF to the file OUTF. */
270 static void
271 dump_conflict_function (FILE *outf, conflict_function *cf)
273 unsigned i;
275 if (cf->n == NO_DEPENDENCE)
276 fprintf (outf, "no dependence");
277 else if (cf->n == NOT_KNOWN)
278 fprintf (outf, "not known");
279 else
281 for (i = 0; i < cf->n; i++)
283 if (i != 0)
284 fprintf (outf, " ");
285 fprintf (outf, "[");
286 dump_affine_function (outf, cf->fns[i]);
287 fprintf (outf, "]");
292 /* Dump function for a SUBSCRIPT structure. */
294 static void
295 dump_subscript (FILE *outf, struct subscript *subscript)
297 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
299 fprintf (outf, "\n (subscript \n");
300 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
301 dump_conflict_function (outf, cf);
302 if (CF_NONTRIVIAL_P (cf))
304 tree last_iteration = SUB_LAST_CONFLICT (subscript);
305 fprintf (outf, "\n last_conflict: ");
306 print_generic_expr (outf, last_iteration, 0);
309 cf = SUB_CONFLICTS_IN_B (subscript);
310 fprintf (outf, "\n iterations_that_access_an_element_twice_in_B: ");
311 dump_conflict_function (outf, cf);
312 if (CF_NONTRIVIAL_P (cf))
314 tree last_iteration = SUB_LAST_CONFLICT (subscript);
315 fprintf (outf, "\n last_conflict: ");
316 print_generic_expr (outf, last_iteration, 0);
319 fprintf (outf, "\n (Subscript distance: ");
320 print_generic_expr (outf, SUB_DISTANCE (subscript), 0);
321 fprintf (outf, " ))\n");
324 /* Print the classic direction vector DIRV to OUTF. */
326 static void
327 print_direction_vector (FILE *outf,
328 lambda_vector dirv,
329 int length)
331 int eq;
333 for (eq = 0; eq < length; eq++)
335 enum data_dependence_direction dir = ((enum data_dependence_direction)
336 dirv[eq]);
338 switch (dir)
340 case dir_positive:
341 fprintf (outf, " +");
342 break;
343 case dir_negative:
344 fprintf (outf, " -");
345 break;
346 case dir_equal:
347 fprintf (outf, " =");
348 break;
349 case dir_positive_or_equal:
350 fprintf (outf, " +=");
351 break;
352 case dir_positive_or_negative:
353 fprintf (outf, " +-");
354 break;
355 case dir_negative_or_equal:
356 fprintf (outf, " -=");
357 break;
358 case dir_star:
359 fprintf (outf, " *");
360 break;
361 default:
362 fprintf (outf, "indep");
363 break;
366 fprintf (outf, "\n");
369 /* Print a vector of direction vectors. */
371 static void
372 print_dir_vectors (FILE *outf, vec<lambda_vector> dir_vects,
373 int length)
375 unsigned j;
376 lambda_vector v;
378 FOR_EACH_VEC_ELT (dir_vects, j, v)
379 print_direction_vector (outf, v, length);
382 /* Print out a vector VEC of length N to OUTFILE. */
384 static inline void
385 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
387 int i;
389 for (i = 0; i < n; i++)
390 fprintf (outfile, "%3d ", vector[i]);
391 fprintf (outfile, "\n");
394 /* Print a vector of distance vectors. */
396 static void
397 print_dist_vectors (FILE *outf, vec<lambda_vector> dist_vects,
398 int length)
400 unsigned j;
401 lambda_vector v;
403 FOR_EACH_VEC_ELT (dist_vects, j, v)
404 print_lambda_vector (outf, v, length);
407 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
409 static void
410 dump_data_dependence_relation (FILE *outf,
411 struct data_dependence_relation *ddr)
413 struct data_reference *dra, *drb;
415 fprintf (outf, "(Data Dep: \n");
417 if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
419 if (ddr)
421 dra = DDR_A (ddr);
422 drb = DDR_B (ddr);
423 if (dra)
424 dump_data_reference (outf, dra);
425 else
426 fprintf (outf, " (nil)\n");
427 if (drb)
428 dump_data_reference (outf, drb);
429 else
430 fprintf (outf, " (nil)\n");
432 fprintf (outf, " (don't know)\n)\n");
433 return;
436 dra = DDR_A (ddr);
437 drb = DDR_B (ddr);
438 dump_data_reference (outf, dra);
439 dump_data_reference (outf, drb);
441 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
442 fprintf (outf, " (no dependence)\n");
444 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
446 unsigned int i;
447 struct loop *loopi;
449 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
451 fprintf (outf, " access_fn_A: ");
452 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
453 fprintf (outf, " access_fn_B: ");
454 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
455 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
458 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
459 fprintf (outf, " loop nest: (");
460 FOR_EACH_VEC_ELT (DDR_LOOP_NEST (ddr), i, loopi)
461 fprintf (outf, "%d ", loopi->num);
462 fprintf (outf, ")\n");
464 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
466 fprintf (outf, " distance_vector: ");
467 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
468 DDR_NB_LOOPS (ddr));
471 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
473 fprintf (outf, " direction_vector: ");
474 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
475 DDR_NB_LOOPS (ddr));
479 fprintf (outf, ")\n");
482 /* Debug version. */
484 DEBUG_FUNCTION void
485 debug_data_dependence_relation (struct data_dependence_relation *ddr)
487 dump_data_dependence_relation (stderr, ddr);
490 /* Dump into FILE all the dependence relations from DDRS. */
492 void
493 dump_data_dependence_relations (FILE *file,
494 vec<ddr_p> ddrs)
496 unsigned int i;
497 struct data_dependence_relation *ddr;
499 FOR_EACH_VEC_ELT (ddrs, i, ddr)
500 dump_data_dependence_relation (file, ddr);
503 DEBUG_FUNCTION void
504 debug (vec<ddr_p> &ref)
506 dump_data_dependence_relations (stderr, ref);
509 DEBUG_FUNCTION void
510 debug (vec<ddr_p> *ptr)
512 if (ptr)
513 debug (*ptr);
514 else
515 fprintf (stderr, "<nil>\n");
519 /* Dump to STDERR all the dependence relations from DDRS. */
521 DEBUG_FUNCTION void
522 debug_data_dependence_relations (vec<ddr_p> ddrs)
524 dump_data_dependence_relations (stderr, ddrs);
527 /* Dumps the distance and direction vectors in FILE. DDRS contains
528 the dependence relations, and VECT_SIZE is the size of the
529 dependence vectors, or in other words the number of loops in the
530 considered nest. */
532 static void
533 dump_dist_dir_vectors (FILE *file, vec<ddr_p> ddrs)
535 unsigned int i, j;
536 struct data_dependence_relation *ddr;
537 lambda_vector v;
539 FOR_EACH_VEC_ELT (ddrs, i, ddr)
540 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
542 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), j, v)
544 fprintf (file, "DISTANCE_V (");
545 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
546 fprintf (file, ")\n");
549 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), j, v)
551 fprintf (file, "DIRECTION_V (");
552 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
553 fprintf (file, ")\n");
557 fprintf (file, "\n\n");
560 /* Dumps the data dependence relations DDRS in FILE. */
562 static void
563 dump_ddrs (FILE *file, vec<ddr_p> ddrs)
565 unsigned int i;
566 struct data_dependence_relation *ddr;
568 FOR_EACH_VEC_ELT (ddrs, i, ddr)
569 dump_data_dependence_relation (file, ddr);
571 fprintf (file, "\n\n");
574 DEBUG_FUNCTION void
575 debug_ddrs (vec<ddr_p> ddrs)
577 dump_ddrs (stderr, ddrs);
580 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
581 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
582 constant of type ssizetype, and returns true. If we cannot do this
583 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
584 is returned. */
586 static bool
587 split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
588 tree *var, tree *off)
590 tree var0, var1;
591 tree off0, off1;
592 enum tree_code ocode = code;
594 *var = NULL_TREE;
595 *off = NULL_TREE;
597 switch (code)
599 case INTEGER_CST:
600 *var = build_int_cst (type, 0);
601 *off = fold_convert (ssizetype, op0);
602 return true;
604 case POINTER_PLUS_EXPR:
605 ocode = PLUS_EXPR;
606 /* FALLTHROUGH */
607 case PLUS_EXPR:
608 case MINUS_EXPR:
609 split_constant_offset (op0, &var0, &off0);
610 split_constant_offset (op1, &var1, &off1);
611 *var = fold_build2 (code, type, var0, var1);
612 *off = size_binop (ocode, off0, off1);
613 return true;
615 case MULT_EXPR:
616 if (TREE_CODE (op1) != INTEGER_CST)
617 return false;
619 split_constant_offset (op0, &var0, &off0);
620 *var = fold_build2 (MULT_EXPR, type, var0, op1);
621 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
622 return true;
624 case ADDR_EXPR:
626 tree base, poffset;
627 HOST_WIDE_INT pbitsize, pbitpos;
628 machine_mode pmode;
629 int punsignedp, pvolatilep;
631 op0 = TREE_OPERAND (op0, 0);
632 base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
633 &pmode, &punsignedp, &pvolatilep, false);
635 if (pbitpos % BITS_PER_UNIT != 0)
636 return false;
637 base = build_fold_addr_expr (base);
638 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
640 if (poffset)
642 split_constant_offset (poffset, &poffset, &off1);
643 off0 = size_binop (PLUS_EXPR, off0, off1);
644 if (POINTER_TYPE_P (TREE_TYPE (base)))
645 base = fold_build_pointer_plus (base, poffset);
646 else
647 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
648 fold_convert (TREE_TYPE (base), poffset));
651 var0 = fold_convert (type, base);
653 /* If variable length types are involved, punt, otherwise casts
654 might be converted into ARRAY_REFs in gimplify_conversion.
655 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
656 possibly no longer appears in current GIMPLE, might resurface.
657 This perhaps could run
658 if (CONVERT_EXPR_P (var0))
660 gimplify_conversion (&var0);
661 // Attempt to fill in any within var0 found ARRAY_REF's
662 // element size from corresponding op embedded ARRAY_REF,
663 // if unsuccessful, just punt.
664 } */
665 while (POINTER_TYPE_P (type))
666 type = TREE_TYPE (type);
667 if (int_size_in_bytes (type) < 0)
668 return false;
670 *var = var0;
671 *off = off0;
672 return true;
675 case SSA_NAME:
677 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
678 return false;
680 gimple def_stmt = SSA_NAME_DEF_STMT (op0);
681 enum tree_code subcode;
683 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
684 return false;
686 var0 = gimple_assign_rhs1 (def_stmt);
687 subcode = gimple_assign_rhs_code (def_stmt);
688 var1 = gimple_assign_rhs2 (def_stmt);
690 return split_constant_offset_1 (type, var0, subcode, var1, var, off);
692 CASE_CONVERT:
694 /* We must not introduce undefined overflow, and we must not change the value.
695 Hence we're okay if the inner type doesn't overflow to start with
696 (pointer or signed), the outer type also is an integer or pointer
697 and the outer precision is at least as large as the inner. */
698 tree itype = TREE_TYPE (op0);
699 if ((POINTER_TYPE_P (itype)
700 || (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_UNDEFINED (itype)))
701 && TYPE_PRECISION (type) >= TYPE_PRECISION (itype)
702 && (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)))
704 split_constant_offset (op0, &var0, off);
705 *var = fold_convert (type, var0);
706 return true;
708 return false;
711 default:
712 return false;
716 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
717 will be ssizetype. */
719 void
720 split_constant_offset (tree exp, tree *var, tree *off)
722 tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
723 enum tree_code code;
725 *var = exp;
726 *off = ssize_int (0);
727 STRIP_NOPS (exp);
729 if (tree_is_chrec (exp)
730 || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
731 return;
733 otype = TREE_TYPE (exp);
734 code = TREE_CODE (exp);
735 extract_ops_from_tree (exp, &code, &op0, &op1);
736 if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
738 *var = fold_convert (type, e);
739 *off = o;
743 /* Returns the address ADDR of an object in a canonical shape (without nop
744 casts, and with type of pointer to the object). */
746 static tree
747 canonicalize_base_object_address (tree addr)
749 tree orig = addr;
751 STRIP_NOPS (addr);
753 /* The base address may be obtained by casting from integer, in that case
754 keep the cast. */
755 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
756 return orig;
758 if (TREE_CODE (addr) != ADDR_EXPR)
759 return addr;
761 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
764 /* Analyzes the behavior of the memory reference DR in the innermost loop or
765 basic block that contains it. Returns true if analysis succeed or false
766 otherwise. */
768 bool
769 dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
771 gimple stmt = DR_STMT (dr);
772 struct loop *loop = loop_containing_stmt (stmt);
773 tree ref = DR_REF (dr);
774 HOST_WIDE_INT pbitsize, pbitpos;
775 tree base, poffset;
776 machine_mode pmode;
777 int punsignedp, pvolatilep;
778 affine_iv base_iv, offset_iv;
779 tree init, dinit, step;
780 bool in_loop = (loop && loop->num);
782 if (dump_file && (dump_flags & TDF_DETAILS))
783 fprintf (dump_file, "analyze_innermost: ");
785 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
786 &pmode, &punsignedp, &pvolatilep, false);
787 gcc_assert (base != NULL_TREE);
789 if (pbitpos % BITS_PER_UNIT != 0)
791 if (dump_file && (dump_flags & TDF_DETAILS))
792 fprintf (dump_file, "failed: bit offset alignment.\n");
793 return false;
796 if (TREE_CODE (base) == MEM_REF)
798 if (!integer_zerop (TREE_OPERAND (base, 1)))
800 offset_int moff = mem_ref_offset (base);
801 tree mofft = wide_int_to_tree (sizetype, moff);
802 if (!poffset)
803 poffset = mofft;
804 else
805 poffset = size_binop (PLUS_EXPR, poffset, mofft);
807 base = TREE_OPERAND (base, 0);
809 else
810 base = build_fold_addr_expr (base);
812 if (in_loop)
814 if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
815 nest ? true : false))
817 if (nest)
819 if (dump_file && (dump_flags & TDF_DETAILS))
820 fprintf (dump_file, "failed: evolution of base is not"
821 " affine.\n");
822 return false;
824 else
826 base_iv.base = base;
827 base_iv.step = ssize_int (0);
828 base_iv.no_overflow = true;
832 else
834 base_iv.base = base;
835 base_iv.step = ssize_int (0);
836 base_iv.no_overflow = true;
839 if (!poffset)
841 offset_iv.base = ssize_int (0);
842 offset_iv.step = ssize_int (0);
844 else
846 if (!in_loop)
848 offset_iv.base = poffset;
849 offset_iv.step = ssize_int (0);
851 else if (!simple_iv (loop, loop_containing_stmt (stmt),
852 poffset, &offset_iv,
853 nest ? true : false))
855 if (nest)
857 if (dump_file && (dump_flags & TDF_DETAILS))
858 fprintf (dump_file, "failed: evolution of offset is not"
859 " affine.\n");
860 return false;
862 else
864 offset_iv.base = poffset;
865 offset_iv.step = ssize_int (0);
870 init = ssize_int (pbitpos / BITS_PER_UNIT);
871 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
872 init = size_binop (PLUS_EXPR, init, dinit);
873 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
874 init = size_binop (PLUS_EXPR, init, dinit);
876 step = size_binop (PLUS_EXPR,
877 fold_convert (ssizetype, base_iv.step),
878 fold_convert (ssizetype, offset_iv.step));
880 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
882 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
883 DR_INIT (dr) = init;
884 DR_STEP (dr) = step;
886 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
888 if (dump_file && (dump_flags & TDF_DETAILS))
889 fprintf (dump_file, "success.\n");
891 return true;
894 /* Determines the base object and the list of indices of memory reference
895 DR, analyzed in LOOP and instantiated in loop nest NEST. */
897 static void
898 dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
900 vec<tree> access_fns = vNULL;
901 tree ref, op;
902 tree base, off, access_fn;
903 basic_block before_loop;
905 /* If analyzing a basic-block there are no indices to analyze
906 and thus no access functions. */
907 if (!nest)
909 DR_BASE_OBJECT (dr) = DR_REF (dr);
910 DR_ACCESS_FNS (dr).create (0);
911 return;
914 ref = DR_REF (dr);
915 before_loop = block_before_loop (nest);
917 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
918 into a two element array with a constant index. The base is
919 then just the immediate underlying object. */
920 if (TREE_CODE (ref) == REALPART_EXPR)
922 ref = TREE_OPERAND (ref, 0);
923 access_fns.safe_push (integer_zero_node);
925 else if (TREE_CODE (ref) == IMAGPART_EXPR)
927 ref = TREE_OPERAND (ref, 0);
928 access_fns.safe_push (integer_one_node);
931 /* Analyze access functions of dimensions we know to be independent. */
932 while (handled_component_p (ref))
934 if (TREE_CODE (ref) == ARRAY_REF)
936 op = TREE_OPERAND (ref, 1);
937 access_fn = analyze_scalar_evolution (loop, op);
938 access_fn = instantiate_scev (before_loop, loop, access_fn);
939 access_fns.safe_push (access_fn);
941 else if (TREE_CODE (ref) == COMPONENT_REF
942 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
944 /* For COMPONENT_REFs of records (but not unions!) use the
945 FIELD_DECL offset as constant access function so we can
946 disambiguate a[i].f1 and a[i].f2. */
947 tree off = component_ref_field_offset (ref);
948 off = size_binop (PLUS_EXPR,
949 size_binop (MULT_EXPR,
950 fold_convert (bitsizetype, off),
951 bitsize_int (BITS_PER_UNIT)),
952 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)));
953 access_fns.safe_push (off);
955 else
956 /* If we have an unhandled component we could not translate
957 to an access function stop analyzing. We have determined
958 our base object in this case. */
959 break;
961 ref = TREE_OPERAND (ref, 0);
964 /* If the address operand of a MEM_REF base has an evolution in the
965 analyzed nest, add it as an additional independent access-function. */
966 if (TREE_CODE (ref) == MEM_REF)
968 op = TREE_OPERAND (ref, 0);
969 access_fn = analyze_scalar_evolution (loop, op);
970 access_fn = instantiate_scev (before_loop, loop, access_fn);
971 if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
973 tree orig_type;
974 tree memoff = TREE_OPERAND (ref, 1);
975 base = initial_condition (access_fn);
976 orig_type = TREE_TYPE (base);
977 STRIP_USELESS_TYPE_CONVERSION (base);
978 split_constant_offset (base, &base, &off);
979 STRIP_USELESS_TYPE_CONVERSION (base);
980 /* Fold the MEM_REF offset into the evolutions initial
981 value to make more bases comparable. */
982 if (!integer_zerop (memoff))
984 off = size_binop (PLUS_EXPR, off,
985 fold_convert (ssizetype, memoff));
986 memoff = build_int_cst (TREE_TYPE (memoff), 0);
988 access_fn = chrec_replace_initial_condition
989 (access_fn, fold_convert (orig_type, off));
990 /* ??? This is still not a suitable base object for
991 dr_may_alias_p - the base object needs to be an
992 access that covers the object as whole. With
993 an evolution in the pointer this cannot be
994 guaranteed.
995 As a band-aid, mark the access so we can special-case
996 it in dr_may_alias_p. */
997 tree old = ref;
998 ref = fold_build2_loc (EXPR_LOCATION (ref),
999 MEM_REF, TREE_TYPE (ref),
1000 base, memoff);
1001 MR_DEPENDENCE_CLIQUE (ref) = MR_DEPENDENCE_CLIQUE (old);
1002 MR_DEPENDENCE_BASE (ref) = MR_DEPENDENCE_BASE (old);
1003 access_fns.safe_push (access_fn);
1006 else if (DECL_P (ref))
1008 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
1009 ref = build2 (MEM_REF, TREE_TYPE (ref),
1010 build_fold_addr_expr (ref),
1011 build_int_cst (reference_alias_ptr_type (ref), 0));
1014 DR_BASE_OBJECT (dr) = ref;
1015 DR_ACCESS_FNS (dr) = access_fns;
1018 /* Extracts the alias analysis information from the memory reference DR. */
1020 static void
1021 dr_analyze_alias (struct data_reference *dr)
1023 tree ref = DR_REF (dr);
1024 tree base = get_base_address (ref), addr;
1026 if (INDIRECT_REF_P (base)
1027 || TREE_CODE (base) == MEM_REF)
1029 addr = TREE_OPERAND (base, 0);
1030 if (TREE_CODE (addr) == SSA_NAME)
1031 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
1035 /* Frees data reference DR. */
1037 void
1038 free_data_ref (data_reference_p dr)
1040 DR_ACCESS_FNS (dr).release ();
1041 free (dr);
1044 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1045 is read if IS_READ is true, write otherwise. Returns the
1046 data_reference description of MEMREF. NEST is the outermost loop
1047 in which the reference should be instantiated, LOOP is the loop in
1048 which the data reference should be analyzed. */
1050 struct data_reference *
1051 create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
1052 bool is_read)
1054 struct data_reference *dr;
1056 if (dump_file && (dump_flags & TDF_DETAILS))
1058 fprintf (dump_file, "Creating dr for ");
1059 print_generic_expr (dump_file, memref, TDF_SLIM);
1060 fprintf (dump_file, "\n");
1063 dr = XCNEW (struct data_reference);
1064 DR_STMT (dr) = stmt;
1065 DR_REF (dr) = memref;
1066 DR_IS_READ (dr) = is_read;
1068 dr_analyze_innermost (dr, nest);
1069 dr_analyze_indices (dr, nest, loop);
1070 dr_analyze_alias (dr);
1072 if (dump_file && (dump_flags & TDF_DETAILS))
1074 unsigned i;
1075 fprintf (dump_file, "\tbase_address: ");
1076 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1077 fprintf (dump_file, "\n\toffset from base address: ");
1078 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1079 fprintf (dump_file, "\n\tconstant offset from base address: ");
1080 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1081 fprintf (dump_file, "\n\tstep: ");
1082 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1083 fprintf (dump_file, "\n\taligned to: ");
1084 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1085 fprintf (dump_file, "\n\tbase_object: ");
1086 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1087 fprintf (dump_file, "\n");
1088 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
1090 fprintf (dump_file, "\tAccess function %d: ", i);
1091 print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
1095 return dr;
1098 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1099 expressions. */
1100 static bool
1101 dr_equal_offsets_p1 (tree offset1, tree offset2)
1103 bool res;
1105 STRIP_NOPS (offset1);
1106 STRIP_NOPS (offset2);
1108 if (offset1 == offset2)
1109 return true;
1111 if (TREE_CODE (offset1) != TREE_CODE (offset2)
1112 || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
1113 return false;
1115 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
1116 TREE_OPERAND (offset2, 0));
1118 if (!res || !BINARY_CLASS_P (offset1))
1119 return res;
1121 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
1122 TREE_OPERAND (offset2, 1));
1124 return res;
1127 /* Check if DRA and DRB have equal offsets. */
1128 bool
1129 dr_equal_offsets_p (struct data_reference *dra,
1130 struct data_reference *drb)
1132 tree offset1, offset2;
1134 offset1 = DR_OFFSET (dra);
1135 offset2 = DR_OFFSET (drb);
1137 return dr_equal_offsets_p1 (offset1, offset2);
1140 /* Returns true if FNA == FNB. */
1142 static bool
1143 affine_function_equal_p (affine_fn fna, affine_fn fnb)
1145 unsigned i, n = fna.length ();
1147 if (n != fnb.length ())
1148 return false;
1150 for (i = 0; i < n; i++)
1151 if (!operand_equal_p (fna[i], fnb[i], 0))
1152 return false;
1154 return true;
1157 /* If all the functions in CF are the same, returns one of them,
1158 otherwise returns NULL. */
1160 static affine_fn
1161 common_affine_function (conflict_function *cf)
1163 unsigned i;
1164 affine_fn comm;
1166 if (!CF_NONTRIVIAL_P (cf))
1167 return affine_fn ();
1169 comm = cf->fns[0];
1171 for (i = 1; i < cf->n; i++)
1172 if (!affine_function_equal_p (comm, cf->fns[i]))
1173 return affine_fn ();
1175 return comm;
1178 /* Returns the base of the affine function FN. */
1180 static tree
1181 affine_function_base (affine_fn fn)
1183 return fn[0];
1186 /* Returns true if FN is a constant. */
1188 static bool
1189 affine_function_constant_p (affine_fn fn)
1191 unsigned i;
1192 tree coef;
1194 for (i = 1; fn.iterate (i, &coef); i++)
1195 if (!integer_zerop (coef))
1196 return false;
1198 return true;
1201 /* Returns true if FN is the zero constant function. */
1203 static bool
1204 affine_function_zero_p (affine_fn fn)
1206 return (integer_zerop (affine_function_base (fn))
1207 && affine_function_constant_p (fn));
1210 /* Returns a signed integer type with the largest precision from TA
1211 and TB. */
1213 static tree
1214 signed_type_for_types (tree ta, tree tb)
1216 if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
1217 return signed_type_for (ta);
1218 else
1219 return signed_type_for (tb);
1222 /* Applies operation OP on affine functions FNA and FNB, and returns the
1223 result. */
1225 static affine_fn
1226 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
1228 unsigned i, n, m;
1229 affine_fn ret;
1230 tree coef;
1232 if (fnb.length () > fna.length ())
1234 n = fna.length ();
1235 m = fnb.length ();
1237 else
1239 n = fnb.length ();
1240 m = fna.length ();
1243 ret.create (m);
1244 for (i = 0; i < n; i++)
1246 tree type = signed_type_for_types (TREE_TYPE (fna[i]),
1247 TREE_TYPE (fnb[i]));
1248 ret.quick_push (fold_build2 (op, type, fna[i], fnb[i]));
1251 for (; fna.iterate (i, &coef); i++)
1252 ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1253 coef, integer_zero_node));
1254 for (; fnb.iterate (i, &coef); i++)
1255 ret.quick_push (fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1256 integer_zero_node, coef));
1258 return ret;
1261 /* Returns the sum of affine functions FNA and FNB. */
1263 static affine_fn
1264 affine_fn_plus (affine_fn fna, affine_fn fnb)
1266 return affine_fn_op (PLUS_EXPR, fna, fnb);
1269 /* Returns the difference of affine functions FNA and FNB. */
1271 static affine_fn
1272 affine_fn_minus (affine_fn fna, affine_fn fnb)
1274 return affine_fn_op (MINUS_EXPR, fna, fnb);
1277 /* Frees affine function FN. */
1279 static void
1280 affine_fn_free (affine_fn fn)
1282 fn.release ();
1285 /* Determine for each subscript in the data dependence relation DDR
1286 the distance. */
1288 static void
1289 compute_subscript_distance (struct data_dependence_relation *ddr)
1291 conflict_function *cf_a, *cf_b;
1292 affine_fn fn_a, fn_b, diff;
1294 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1296 unsigned int i;
1298 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1300 struct subscript *subscript;
1302 subscript = DDR_SUBSCRIPT (ddr, i);
1303 cf_a = SUB_CONFLICTS_IN_A (subscript);
1304 cf_b = SUB_CONFLICTS_IN_B (subscript);
1306 fn_a = common_affine_function (cf_a);
1307 fn_b = common_affine_function (cf_b);
1308 if (!fn_a.exists () || !fn_b.exists ())
1310 SUB_DISTANCE (subscript) = chrec_dont_know;
1311 return;
1313 diff = affine_fn_minus (fn_a, fn_b);
1315 if (affine_function_constant_p (diff))
1316 SUB_DISTANCE (subscript) = affine_function_base (diff);
1317 else
1318 SUB_DISTANCE (subscript) = chrec_dont_know;
1320 affine_fn_free (diff);
1325 /* Returns the conflict function for "unknown". */
1327 static conflict_function *
1328 conflict_fn_not_known (void)
1330 conflict_function *fn = XCNEW (conflict_function);
1331 fn->n = NOT_KNOWN;
1333 return fn;
1336 /* Returns the conflict function for "independent". */
1338 static conflict_function *
1339 conflict_fn_no_dependence (void)
1341 conflict_function *fn = XCNEW (conflict_function);
1342 fn->n = NO_DEPENDENCE;
1344 return fn;
1347 /* Returns true if the address of OBJ is invariant in LOOP. */
1349 static bool
1350 object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
1352 while (handled_component_p (obj))
1354 if (TREE_CODE (obj) == ARRAY_REF)
1356 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1357 need to check the stride and the lower bound of the reference. */
1358 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1359 loop->num)
1360 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1361 loop->num))
1362 return false;
1364 else if (TREE_CODE (obj) == COMPONENT_REF)
1366 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1367 loop->num))
1368 return false;
1370 obj = TREE_OPERAND (obj, 0);
1373 if (!INDIRECT_REF_P (obj)
1374 && TREE_CODE (obj) != MEM_REF)
1375 return true;
1377 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1378 loop->num);
1381 /* Returns false if we can prove that data references A and B do not alias,
1382 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1383 considered. */
1385 bool
1386 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
1387 bool loop_nest)
1389 tree addr_a = DR_BASE_OBJECT (a);
1390 tree addr_b = DR_BASE_OBJECT (b);
1392 /* If we are not processing a loop nest but scalar code we
1393 do not need to care about possible cross-iteration dependences
1394 and thus can process the full original reference. Do so,
1395 similar to how loop invariant motion applies extra offset-based
1396 disambiguation. */
1397 if (!loop_nest)
1399 aff_tree off1, off2;
1400 widest_int size1, size2;
1401 get_inner_reference_aff (DR_REF (a), &off1, &size1);
1402 get_inner_reference_aff (DR_REF (b), &off2, &size2);
1403 aff_combination_scale (&off1, -1);
1404 aff_combination_add (&off2, &off1);
1405 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1406 return false;
1409 if ((TREE_CODE (addr_a) == MEM_REF || TREE_CODE (addr_a) == TARGET_MEM_REF)
1410 && (TREE_CODE (addr_b) == MEM_REF || TREE_CODE (addr_b) == TARGET_MEM_REF)
1411 && MR_DEPENDENCE_CLIQUE (addr_a) == MR_DEPENDENCE_CLIQUE (addr_b)
1412 && MR_DEPENDENCE_BASE (addr_a) != MR_DEPENDENCE_BASE (addr_b))
1413 return false;
1415 /* If we had an evolution in a pointer-based MEM_REF BASE_OBJECT we
1416 do not know the size of the base-object. So we cannot do any
1417 offset/overlap based analysis but have to rely on points-to
1418 information only. */
1419 if (TREE_CODE (addr_a) == MEM_REF
1420 && TREE_CODE (TREE_OPERAND (addr_a, 0)) == SSA_NAME)
1422 /* For true dependences we can apply TBAA. */
1423 if (flag_strict_aliasing
1424 && DR_IS_WRITE (a) && DR_IS_READ (b)
1425 && !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
1426 get_alias_set (DR_REF (b))))
1427 return false;
1428 if (TREE_CODE (addr_b) == MEM_REF)
1429 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1430 TREE_OPERAND (addr_b, 0));
1431 else
1432 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1433 build_fold_addr_expr (addr_b));
1435 else if (TREE_CODE (addr_b) == MEM_REF
1436 && TREE_CODE (TREE_OPERAND (addr_b, 0)) == SSA_NAME)
1438 /* For true dependences we can apply TBAA. */
1439 if (flag_strict_aliasing
1440 && DR_IS_WRITE (a) && DR_IS_READ (b)
1441 && !alias_sets_conflict_p (get_alias_set (DR_REF (a)),
1442 get_alias_set (DR_REF (b))))
1443 return false;
1444 if (TREE_CODE (addr_a) == MEM_REF)
1445 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1446 TREE_OPERAND (addr_b, 0));
1447 else
1448 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a),
1449 TREE_OPERAND (addr_b, 0));
1452 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1453 that is being subsetted in the loop nest. */
1454 if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
1455 return refs_output_dependent_p (addr_a, addr_b);
1456 else if (DR_IS_READ (a) && DR_IS_WRITE (b))
1457 return refs_anti_dependent_p (addr_a, addr_b);
1458 return refs_may_alias_p (addr_a, addr_b);
1461 /* Initialize a data dependence relation between data accesses A and
1462 B. NB_LOOPS is the number of loops surrounding the references: the
1463 size of the classic distance/direction vectors. */
1465 struct data_dependence_relation *
1466 initialize_data_dependence_relation (struct data_reference *a,
1467 struct data_reference *b,
1468 vec<loop_p> loop_nest)
1470 struct data_dependence_relation *res;
1471 unsigned int i;
1473 res = XNEW (struct data_dependence_relation);
1474 DDR_A (res) = a;
1475 DDR_B (res) = b;
1476 DDR_LOOP_NEST (res).create (0);
1477 DDR_REVERSED_P (res) = false;
1478 DDR_SUBSCRIPTS (res).create (0);
1479 DDR_DIR_VECTS (res).create (0);
1480 DDR_DIST_VECTS (res).create (0);
1482 if (a == NULL || b == NULL)
1484 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1485 return res;
1488 /* If the data references do not alias, then they are independent. */
1489 if (!dr_may_alias_p (a, b, loop_nest.exists ()))
1491 DDR_ARE_DEPENDENT (res) = chrec_known;
1492 return res;
1495 /* The case where the references are exactly the same. */
1496 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
1498 if (loop_nest.exists ()
1499 && !object_address_invariant_in_loop_p (loop_nest[0],
1500 DR_BASE_OBJECT (a)))
1502 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1503 return res;
1505 DDR_AFFINE_P (res) = true;
1506 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1507 DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
1508 DDR_LOOP_NEST (res) = loop_nest;
1509 DDR_INNER_LOOP (res) = 0;
1510 DDR_SELF_REFERENCE (res) = true;
1511 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1513 struct subscript *subscript;
1515 subscript = XNEW (struct subscript);
1516 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1517 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1518 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1519 SUB_DISTANCE (subscript) = chrec_dont_know;
1520 DDR_SUBSCRIPTS (res).safe_push (subscript);
1522 return res;
1525 /* If the references do not access the same object, we do not know
1526 whether they alias or not. */
1527 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1529 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1530 return res;
1533 /* If the base of the object is not invariant in the loop nest, we cannot
1534 analyze it. TODO -- in fact, it would suffice to record that there may
1535 be arbitrary dependences in the loops where the base object varies. */
1536 if (loop_nest.exists ()
1537 && !object_address_invariant_in_loop_p (loop_nest[0],
1538 DR_BASE_OBJECT (a)))
1540 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1541 return res;
1544 /* If the number of dimensions of the access to not agree we can have
1545 a pointer access to a component of the array element type and an
1546 array access while the base-objects are still the same. Punt. */
1547 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1549 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1550 return res;
1553 DDR_AFFINE_P (res) = true;
1554 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1555 DDR_SUBSCRIPTS (res).create (DR_NUM_DIMENSIONS (a));
1556 DDR_LOOP_NEST (res) = loop_nest;
1557 DDR_INNER_LOOP (res) = 0;
1558 DDR_SELF_REFERENCE (res) = false;
1560 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1562 struct subscript *subscript;
1564 subscript = XNEW (struct subscript);
1565 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1566 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1567 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1568 SUB_DISTANCE (subscript) = chrec_dont_know;
1569 DDR_SUBSCRIPTS (res).safe_push (subscript);
1572 return res;
1575 /* Frees memory used by the conflict function F. */
1577 static void
1578 free_conflict_function (conflict_function *f)
1580 unsigned i;
1582 if (CF_NONTRIVIAL_P (f))
1584 for (i = 0; i < f->n; i++)
1585 affine_fn_free (f->fns[i]);
1587 free (f);
1590 /* Frees memory used by SUBSCRIPTS. */
1592 static void
1593 free_subscripts (vec<subscript_p> subscripts)
1595 unsigned i;
1596 subscript_p s;
1598 FOR_EACH_VEC_ELT (subscripts, i, s)
1600 free_conflict_function (s->conflicting_iterations_in_a);
1601 free_conflict_function (s->conflicting_iterations_in_b);
1602 free (s);
1604 subscripts.release ();
1607 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1608 description. */
1610 static inline void
1611 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1612 tree chrec)
1614 DDR_ARE_DEPENDENT (ddr) = chrec;
1615 free_subscripts (DDR_SUBSCRIPTS (ddr));
1616 DDR_SUBSCRIPTS (ddr).create (0);
1619 /* The dependence relation DDR cannot be represented by a distance
1620 vector. */
1622 static inline void
1623 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1625 if (dump_file && (dump_flags & TDF_DETAILS))
1626 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1628 DDR_AFFINE_P (ddr) = false;
1633 /* This section contains the classic Banerjee tests. */
1635 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1636 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1638 static inline bool
1639 ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1641 return (evolution_function_is_constant_p (chrec_a)
1642 && evolution_function_is_constant_p (chrec_b));
1645 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1646 variable, i.e., if the SIV (Single Index Variable) test is true. */
1648 static bool
1649 siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1651 if ((evolution_function_is_constant_p (chrec_a)
1652 && evolution_function_is_univariate_p (chrec_b))
1653 || (evolution_function_is_constant_p (chrec_b)
1654 && evolution_function_is_univariate_p (chrec_a)))
1655 return true;
1657 if (evolution_function_is_univariate_p (chrec_a)
1658 && evolution_function_is_univariate_p (chrec_b))
1660 switch (TREE_CODE (chrec_a))
1662 case POLYNOMIAL_CHREC:
1663 switch (TREE_CODE (chrec_b))
1665 case POLYNOMIAL_CHREC:
1666 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1667 return false;
1669 default:
1670 return true;
1673 default:
1674 return true;
1678 return false;
1681 /* Creates a conflict function with N dimensions. The affine functions
1682 in each dimension follow. */
1684 static conflict_function *
1685 conflict_fn (unsigned n, ...)
1687 unsigned i;
1688 conflict_function *ret = XCNEW (conflict_function);
1689 va_list ap;
1691 gcc_assert (0 < n && n <= MAX_DIM);
1692 va_start (ap, n);
1694 ret->n = n;
1695 for (i = 0; i < n; i++)
1696 ret->fns[i] = va_arg (ap, affine_fn);
1697 va_end (ap);
1699 return ret;
1702 /* Returns constant affine function with value CST. */
1704 static affine_fn
1705 affine_fn_cst (tree cst)
1707 affine_fn fn;
1708 fn.create (1);
1709 fn.quick_push (cst);
1710 return fn;
1713 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1715 static affine_fn
1716 affine_fn_univar (tree cst, unsigned dim, tree coef)
1718 affine_fn fn;
1719 fn.create (dim + 1);
1720 unsigned i;
1722 gcc_assert (dim > 0);
1723 fn.quick_push (cst);
1724 for (i = 1; i < dim; i++)
1725 fn.quick_push (integer_zero_node);
1726 fn.quick_push (coef);
1727 return fn;
1730 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1731 *OVERLAPS_B are initialized to the functions that describe the
1732 relation between the elements accessed twice by CHREC_A and
1733 CHREC_B. For k >= 0, the following property is verified:
1735 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1737 static void
1738 analyze_ziv_subscript (tree chrec_a,
1739 tree chrec_b,
1740 conflict_function **overlaps_a,
1741 conflict_function **overlaps_b,
1742 tree *last_conflicts)
1744 tree type, difference;
1745 dependence_stats.num_ziv++;
1747 if (dump_file && (dump_flags & TDF_DETAILS))
1748 fprintf (dump_file, "(analyze_ziv_subscript \n");
1750 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1751 chrec_a = chrec_convert (type, chrec_a, NULL);
1752 chrec_b = chrec_convert (type, chrec_b, NULL);
1753 difference = chrec_fold_minus (type, chrec_a, chrec_b);
1755 switch (TREE_CODE (difference))
1757 case INTEGER_CST:
1758 if (integer_zerop (difference))
1760 /* The difference is equal to zero: the accessed index
1761 overlaps for each iteration in the loop. */
1762 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1763 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1764 *last_conflicts = chrec_dont_know;
1765 dependence_stats.num_ziv_dependent++;
1767 else
1769 /* The accesses do not overlap. */
1770 *overlaps_a = conflict_fn_no_dependence ();
1771 *overlaps_b = conflict_fn_no_dependence ();
1772 *last_conflicts = integer_zero_node;
1773 dependence_stats.num_ziv_independent++;
1775 break;
1777 default:
1778 /* We're not sure whether the indexes overlap. For the moment,
1779 conservatively answer "don't know". */
1780 if (dump_file && (dump_flags & TDF_DETAILS))
1781 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1783 *overlaps_a = conflict_fn_not_known ();
1784 *overlaps_b = conflict_fn_not_known ();
1785 *last_conflicts = chrec_dont_know;
1786 dependence_stats.num_ziv_unimplemented++;
1787 break;
1790 if (dump_file && (dump_flags & TDF_DETAILS))
1791 fprintf (dump_file, ")\n");
1794 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1795 and only if it fits to the int type. If this is not the case, or the
1796 bound on the number of iterations of LOOP could not be derived, returns
1797 chrec_dont_know. */
1799 static tree
1800 max_stmt_executions_tree (struct loop *loop)
1802 widest_int nit;
1804 if (!max_stmt_executions (loop, &nit))
1805 return chrec_dont_know;
1807 if (!wi::fits_to_tree_p (nit, unsigned_type_node))
1808 return chrec_dont_know;
1810 return wide_int_to_tree (unsigned_type_node, nit);
1813 /* Determine whether the CHREC is always positive/negative. If the expression
1814 cannot be statically analyzed, return false, otherwise set the answer into
1815 VALUE. */
1817 static bool
1818 chrec_is_positive (tree chrec, bool *value)
1820 bool value0, value1, value2;
1821 tree end_value, nb_iter;
1823 switch (TREE_CODE (chrec))
1825 case POLYNOMIAL_CHREC:
1826 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
1827 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
1828 return false;
1830 /* FIXME -- overflows. */
1831 if (value0 == value1)
1833 *value = value0;
1834 return true;
1837 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1838 and the proof consists in showing that the sign never
1839 changes during the execution of the loop, from 0 to
1840 loop->nb_iterations. */
1841 if (!evolution_function_is_affine_p (chrec))
1842 return false;
1844 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
1845 if (chrec_contains_undetermined (nb_iter))
1846 return false;
1848 #if 0
1849 /* TODO -- If the test is after the exit, we may decrease the number of
1850 iterations by one. */
1851 if (after_exit)
1852 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
1853 #endif
1855 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
1857 if (!chrec_is_positive (end_value, &value2))
1858 return false;
1860 *value = value0;
1861 return value0 == value1;
1863 case INTEGER_CST:
1864 switch (tree_int_cst_sgn (chrec))
1866 case -1:
1867 *value = false;
1868 break;
1869 case 1:
1870 *value = true;
1871 break;
1872 default:
1873 return false;
1875 return true;
1877 default:
1878 return false;
1883 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1884 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1885 *OVERLAPS_B are initialized to the functions that describe the
1886 relation between the elements accessed twice by CHREC_A and
1887 CHREC_B. For k >= 0, the following property is verified:
1889 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1891 static void
1892 analyze_siv_subscript_cst_affine (tree chrec_a,
1893 tree chrec_b,
1894 conflict_function **overlaps_a,
1895 conflict_function **overlaps_b,
1896 tree *last_conflicts)
1898 bool value0, value1, value2;
1899 tree type, difference, tmp;
1901 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1902 chrec_a = chrec_convert (type, chrec_a, NULL);
1903 chrec_b = chrec_convert (type, chrec_b, NULL);
1904 difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
1906 /* Special case overlap in the first iteration. */
1907 if (integer_zerop (difference))
1909 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1910 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1911 *last_conflicts = integer_one_node;
1912 return;
1915 if (!chrec_is_positive (initial_condition (difference), &value0))
1917 if (dump_file && (dump_flags & TDF_DETAILS))
1918 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1920 dependence_stats.num_siv_unimplemented++;
1921 *overlaps_a = conflict_fn_not_known ();
1922 *overlaps_b = conflict_fn_not_known ();
1923 *last_conflicts = chrec_dont_know;
1924 return;
1926 else
1928 if (value0 == false)
1930 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1932 if (dump_file && (dump_flags & TDF_DETAILS))
1933 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1935 *overlaps_a = conflict_fn_not_known ();
1936 *overlaps_b = conflict_fn_not_known ();
1937 *last_conflicts = chrec_dont_know;
1938 dependence_stats.num_siv_unimplemented++;
1939 return;
1941 else
1943 if (value1 == true)
1945 /* Example:
1946 chrec_a = 12
1947 chrec_b = {10, +, 1}
1950 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1952 HOST_WIDE_INT numiter;
1953 struct loop *loop = get_chrec_loop (chrec_b);
1955 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1956 tmp = fold_build2 (EXACT_DIV_EXPR, type,
1957 fold_build1 (ABS_EXPR, type, difference),
1958 CHREC_RIGHT (chrec_b));
1959 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1960 *last_conflicts = integer_one_node;
1963 /* Perform weak-zero siv test to see if overlap is
1964 outside the loop bounds. */
1965 numiter = max_stmt_executions_int (loop);
1967 if (numiter >= 0
1968 && compare_tree_int (tmp, numiter) > 0)
1970 free_conflict_function (*overlaps_a);
1971 free_conflict_function (*overlaps_b);
1972 *overlaps_a = conflict_fn_no_dependence ();
1973 *overlaps_b = conflict_fn_no_dependence ();
1974 *last_conflicts = integer_zero_node;
1975 dependence_stats.num_siv_independent++;
1976 return;
1978 dependence_stats.num_siv_dependent++;
1979 return;
1982 /* When the step does not divide the difference, there are
1983 no overlaps. */
1984 else
1986 *overlaps_a = conflict_fn_no_dependence ();
1987 *overlaps_b = conflict_fn_no_dependence ();
1988 *last_conflicts = integer_zero_node;
1989 dependence_stats.num_siv_independent++;
1990 return;
1994 else
1996 /* Example:
1997 chrec_a = 12
1998 chrec_b = {10, +, -1}
2000 In this case, chrec_a will not overlap with chrec_b. */
2001 *overlaps_a = conflict_fn_no_dependence ();
2002 *overlaps_b = conflict_fn_no_dependence ();
2003 *last_conflicts = integer_zero_node;
2004 dependence_stats.num_siv_independent++;
2005 return;
2009 else
2011 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2013 if (dump_file && (dump_flags & TDF_DETAILS))
2014 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2016 *overlaps_a = conflict_fn_not_known ();
2017 *overlaps_b = conflict_fn_not_known ();
2018 *last_conflicts = chrec_dont_know;
2019 dependence_stats.num_siv_unimplemented++;
2020 return;
2022 else
2024 if (value2 == false)
2026 /* Example:
2027 chrec_a = 3
2028 chrec_b = {10, +, -1}
2030 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2032 HOST_WIDE_INT numiter;
2033 struct loop *loop = get_chrec_loop (chrec_b);
2035 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2036 tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
2037 CHREC_RIGHT (chrec_b));
2038 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2039 *last_conflicts = integer_one_node;
2041 /* Perform weak-zero siv test to see if overlap is
2042 outside the loop bounds. */
2043 numiter = max_stmt_executions_int (loop);
2045 if (numiter >= 0
2046 && compare_tree_int (tmp, numiter) > 0)
2048 free_conflict_function (*overlaps_a);
2049 free_conflict_function (*overlaps_b);
2050 *overlaps_a = conflict_fn_no_dependence ();
2051 *overlaps_b = conflict_fn_no_dependence ();
2052 *last_conflicts = integer_zero_node;
2053 dependence_stats.num_siv_independent++;
2054 return;
2056 dependence_stats.num_siv_dependent++;
2057 return;
2060 /* When the step does not divide the difference, there
2061 are no overlaps. */
2062 else
2064 *overlaps_a = conflict_fn_no_dependence ();
2065 *overlaps_b = conflict_fn_no_dependence ();
2066 *last_conflicts = integer_zero_node;
2067 dependence_stats.num_siv_independent++;
2068 return;
2071 else
2073 /* Example:
2074 chrec_a = 3
2075 chrec_b = {4, +, 1}
2077 In this case, chrec_a will not overlap with chrec_b. */
2078 *overlaps_a = conflict_fn_no_dependence ();
2079 *overlaps_b = conflict_fn_no_dependence ();
2080 *last_conflicts = integer_zero_node;
2081 dependence_stats.num_siv_independent++;
2082 return;
2089 /* Helper recursive function for initializing the matrix A. Returns
2090 the initial value of CHREC. */
2092 static tree
2093 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2095 gcc_assert (chrec);
2097 switch (TREE_CODE (chrec))
2099 case POLYNOMIAL_CHREC:
2100 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
2102 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2103 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2105 case PLUS_EXPR:
2106 case MULT_EXPR:
2107 case MINUS_EXPR:
2109 tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2110 tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
2112 return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
2115 CASE_CONVERT:
2117 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2118 return chrec_convert (chrec_type (chrec), op, NULL);
2121 case BIT_NOT_EXPR:
2123 /* Handle ~X as -1 - X. */
2124 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2125 return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
2126 build_int_cst (TREE_TYPE (chrec), -1), op);
2129 case INTEGER_CST:
2130 return chrec;
2132 default:
2133 gcc_unreachable ();
2134 return NULL_TREE;
2138 #define FLOOR_DIV(x,y) ((x) / (y))
2140 /* Solves the special case of the Diophantine equation:
2141 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2143 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2144 number of iterations that loops X and Y run. The overlaps will be
2145 constructed as evolutions in dimension DIM. */
2147 static void
2148 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2149 affine_fn *overlaps_a,
2150 affine_fn *overlaps_b,
2151 tree *last_conflicts, int dim)
2153 if (((step_a > 0 && step_b > 0)
2154 || (step_a < 0 && step_b < 0)))
2156 int step_overlaps_a, step_overlaps_b;
2157 int gcd_steps_a_b, last_conflict, tau2;
2159 gcd_steps_a_b = gcd (step_a, step_b);
2160 step_overlaps_a = step_b / gcd_steps_a_b;
2161 step_overlaps_b = step_a / gcd_steps_a_b;
2163 if (niter > 0)
2165 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2166 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2167 last_conflict = tau2;
2168 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2170 else
2171 *last_conflicts = chrec_dont_know;
2173 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2174 build_int_cst (NULL_TREE,
2175 step_overlaps_a));
2176 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2177 build_int_cst (NULL_TREE,
2178 step_overlaps_b));
2181 else
2183 *overlaps_a = affine_fn_cst (integer_zero_node);
2184 *overlaps_b = affine_fn_cst (integer_zero_node);
2185 *last_conflicts = integer_zero_node;
2189 /* Solves the special case of a Diophantine equation where CHREC_A is
2190 an affine bivariate function, and CHREC_B is an affine univariate
2191 function. For example,
2193 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2195 has the following overlapping functions:
2197 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2198 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2199 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2201 FORNOW: This is a specialized implementation for a case occurring in
2202 a common benchmark. Implement the general algorithm. */
2204 static void
2205 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2206 conflict_function **overlaps_a,
2207 conflict_function **overlaps_b,
2208 tree *last_conflicts)
2210 bool xz_p, yz_p, xyz_p;
2211 int step_x, step_y, step_z;
2212 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2213 affine_fn overlaps_a_xz, overlaps_b_xz;
2214 affine_fn overlaps_a_yz, overlaps_b_yz;
2215 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2216 affine_fn ova1, ova2, ovb;
2217 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2219 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2220 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2221 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2223 niter_x = max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)));
2224 niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a));
2225 niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b));
2227 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2229 if (dump_file && (dump_flags & TDF_DETAILS))
2230 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2232 *overlaps_a = conflict_fn_not_known ();
2233 *overlaps_b = conflict_fn_not_known ();
2234 *last_conflicts = chrec_dont_know;
2235 return;
2238 niter = MIN (niter_x, niter_z);
2239 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2240 &overlaps_a_xz,
2241 &overlaps_b_xz,
2242 &last_conflicts_xz, 1);
2243 niter = MIN (niter_y, niter_z);
2244 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2245 &overlaps_a_yz,
2246 &overlaps_b_yz,
2247 &last_conflicts_yz, 2);
2248 niter = MIN (niter_x, niter_z);
2249 niter = MIN (niter_y, niter);
2250 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2251 &overlaps_a_xyz,
2252 &overlaps_b_xyz,
2253 &last_conflicts_xyz, 3);
2255 xz_p = !integer_zerop (last_conflicts_xz);
2256 yz_p = !integer_zerop (last_conflicts_yz);
2257 xyz_p = !integer_zerop (last_conflicts_xyz);
2259 if (xz_p || yz_p || xyz_p)
2261 ova1 = affine_fn_cst (integer_zero_node);
2262 ova2 = affine_fn_cst (integer_zero_node);
2263 ovb = affine_fn_cst (integer_zero_node);
2264 if (xz_p)
2266 affine_fn t0 = ova1;
2267 affine_fn t2 = ovb;
2269 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2270 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2271 affine_fn_free (t0);
2272 affine_fn_free (t2);
2273 *last_conflicts = last_conflicts_xz;
2275 if (yz_p)
2277 affine_fn t0 = ova2;
2278 affine_fn t2 = ovb;
2280 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2281 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2282 affine_fn_free (t0);
2283 affine_fn_free (t2);
2284 *last_conflicts = last_conflicts_yz;
2286 if (xyz_p)
2288 affine_fn t0 = ova1;
2289 affine_fn t2 = ova2;
2290 affine_fn t4 = ovb;
2292 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2293 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2294 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2295 affine_fn_free (t0);
2296 affine_fn_free (t2);
2297 affine_fn_free (t4);
2298 *last_conflicts = last_conflicts_xyz;
2300 *overlaps_a = conflict_fn (2, ova1, ova2);
2301 *overlaps_b = conflict_fn (1, ovb);
2303 else
2305 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2306 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2307 *last_conflicts = integer_zero_node;
2310 affine_fn_free (overlaps_a_xz);
2311 affine_fn_free (overlaps_b_xz);
2312 affine_fn_free (overlaps_a_yz);
2313 affine_fn_free (overlaps_b_yz);
2314 affine_fn_free (overlaps_a_xyz);
2315 affine_fn_free (overlaps_b_xyz);
2318 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2320 static void
2321 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
2322 int size)
2324 memcpy (vec2, vec1, size * sizeof (*vec1));
2327 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2329 static void
2330 lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
2331 int m, int n)
2333 int i;
2335 for (i = 0; i < m; i++)
2336 lambda_vector_copy (mat1[i], mat2[i], n);
2339 /* Store the N x N identity matrix in MAT. */
2341 static void
2342 lambda_matrix_id (lambda_matrix mat, int size)
2344 int i, j;
2346 for (i = 0; i < size; i++)
2347 for (j = 0; j < size; j++)
2348 mat[i][j] = (i == j) ? 1 : 0;
2351 /* Return the first nonzero element of vector VEC1 between START and N.
2352 We must have START <= N. Returns N if VEC1 is the zero vector. */
2354 static int
2355 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
2357 int j = start;
2358 while (j < n && vec1[j] == 0)
2359 j++;
2360 return j;
2363 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2364 R2 = R2 + CONST1 * R1. */
2366 static void
2367 lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
2369 int i;
2371 if (const1 == 0)
2372 return;
2374 for (i = 0; i < n; i++)
2375 mat[r2][i] += const1 * mat[r1][i];
2378 /* Swap rows R1 and R2 in matrix MAT. */
2380 static void
2381 lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
2383 lambda_vector row;
2385 row = mat[r1];
2386 mat[r1] = mat[r2];
2387 mat[r2] = row;
2390 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2391 and store the result in VEC2. */
2393 static void
2394 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
2395 int size, int const1)
2397 int i;
2399 if (const1 == 0)
2400 lambda_vector_clear (vec2, size);
2401 else
2402 for (i = 0; i < size; i++)
2403 vec2[i] = const1 * vec1[i];
2406 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2408 static void
2409 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
2410 int size)
2412 lambda_vector_mult_const (vec1, vec2, size, -1);
2415 /* Negate row R1 of matrix MAT which has N columns. */
2417 static void
2418 lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
2420 lambda_vector_negate (mat[r1], mat[r1], n);
2423 /* Return true if two vectors are equal. */
2425 static bool
2426 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
2428 int i;
2429 for (i = 0; i < size; i++)
2430 if (vec1[i] != vec2[i])
2431 return false;
2432 return true;
2435 /* Given an M x N integer matrix A, this function determines an M x
2436 M unimodular matrix U, and an M x N echelon matrix S such that
2437 "U.A = S". This decomposition is also known as "right Hermite".
2439 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2440 Restructuring Compilers" Utpal Banerjee. */
2442 static void
2443 lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
2444 lambda_matrix S, lambda_matrix U)
2446 int i, j, i0 = 0;
2448 lambda_matrix_copy (A, S, m, n);
2449 lambda_matrix_id (U, m);
2451 for (j = 0; j < n; j++)
2453 if (lambda_vector_first_nz (S[j], m, i0) < m)
2455 ++i0;
2456 for (i = m - 1; i >= i0; i--)
2458 while (S[i][j] != 0)
2460 int sigma, factor, a, b;
2462 a = S[i-1][j];
2463 b = S[i][j];
2464 sigma = (a * b < 0) ? -1: 1;
2465 a = abs (a);
2466 b = abs (b);
2467 factor = sigma * (a / b);
2469 lambda_matrix_row_add (S, n, i, i-1, -factor);
2470 lambda_matrix_row_exchange (S, i, i-1);
2472 lambda_matrix_row_add (U, m, i, i-1, -factor);
2473 lambda_matrix_row_exchange (U, i, i-1);
2480 /* Determines the overlapping elements due to accesses CHREC_A and
2481 CHREC_B, that are affine functions. This function cannot handle
2482 symbolic evolution functions, ie. when initial conditions are
2483 parameters, because it uses lambda matrices of integers. */
2485 static void
2486 analyze_subscript_affine_affine (tree chrec_a,
2487 tree chrec_b,
2488 conflict_function **overlaps_a,
2489 conflict_function **overlaps_b,
2490 tree *last_conflicts)
2492 unsigned nb_vars_a, nb_vars_b, dim;
2493 HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2494 lambda_matrix A, U, S;
2495 struct obstack scratch_obstack;
2497 if (eq_evolutions_p (chrec_a, chrec_b))
2499 /* The accessed index overlaps for each iteration in the
2500 loop. */
2501 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2502 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2503 *last_conflicts = chrec_dont_know;
2504 return;
2506 if (dump_file && (dump_flags & TDF_DETAILS))
2507 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2509 /* For determining the initial intersection, we have to solve a
2510 Diophantine equation. This is the most time consuming part.
2512 For answering to the question: "Is there a dependence?" we have
2513 to prove that there exists a solution to the Diophantine
2514 equation, and that the solution is in the iteration domain,
2515 i.e. the solution is positive or zero, and that the solution
2516 happens before the upper bound loop.nb_iterations. Otherwise
2517 there is no dependence. This function outputs a description of
2518 the iterations that hold the intersections. */
2520 nb_vars_a = nb_vars_in_chrec (chrec_a);
2521 nb_vars_b = nb_vars_in_chrec (chrec_b);
2523 gcc_obstack_init (&scratch_obstack);
2525 dim = nb_vars_a + nb_vars_b;
2526 U = lambda_matrix_new (dim, dim, &scratch_obstack);
2527 A = lambda_matrix_new (dim, 1, &scratch_obstack);
2528 S = lambda_matrix_new (dim, 1, &scratch_obstack);
2530 init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
2531 init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
2532 gamma = init_b - init_a;
2534 /* Don't do all the hard work of solving the Diophantine equation
2535 when we already know the solution: for example,
2536 | {3, +, 1}_1
2537 | {3, +, 4}_2
2538 | gamma = 3 - 3 = 0.
2539 Then the first overlap occurs during the first iterations:
2540 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2542 if (gamma == 0)
2544 if (nb_vars_a == 1 && nb_vars_b == 1)
2546 HOST_WIDE_INT step_a, step_b;
2547 HOST_WIDE_INT niter, niter_a, niter_b;
2548 affine_fn ova, ovb;
2550 niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a));
2551 niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b));
2552 niter = MIN (niter_a, niter_b);
2553 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2554 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2556 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2557 &ova, &ovb,
2558 last_conflicts, 1);
2559 *overlaps_a = conflict_fn (1, ova);
2560 *overlaps_b = conflict_fn (1, ovb);
2563 else if (nb_vars_a == 2 && nb_vars_b == 1)
2564 compute_overlap_steps_for_affine_1_2
2565 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2567 else if (nb_vars_a == 1 && nb_vars_b == 2)
2568 compute_overlap_steps_for_affine_1_2
2569 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2571 else
2573 if (dump_file && (dump_flags & TDF_DETAILS))
2574 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2575 *overlaps_a = conflict_fn_not_known ();
2576 *overlaps_b = conflict_fn_not_known ();
2577 *last_conflicts = chrec_dont_know;
2579 goto end_analyze_subs_aa;
2582 /* U.A = S */
2583 lambda_matrix_right_hermite (A, dim, 1, S, U);
2585 if (S[0][0] < 0)
2587 S[0][0] *= -1;
2588 lambda_matrix_row_negate (U, dim, 0);
2590 gcd_alpha_beta = S[0][0];
2592 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2593 but that is a quite strange case. Instead of ICEing, answer
2594 don't know. */
2595 if (gcd_alpha_beta == 0)
2597 *overlaps_a = conflict_fn_not_known ();
2598 *overlaps_b = conflict_fn_not_known ();
2599 *last_conflicts = chrec_dont_know;
2600 goto end_analyze_subs_aa;
2603 /* The classic "gcd-test". */
2604 if (!int_divides_p (gcd_alpha_beta, gamma))
2606 /* The "gcd-test" has determined that there is no integer
2607 solution, i.e. there is no dependence. */
2608 *overlaps_a = conflict_fn_no_dependence ();
2609 *overlaps_b = conflict_fn_no_dependence ();
2610 *last_conflicts = integer_zero_node;
2613 /* Both access functions are univariate. This includes SIV and MIV cases. */
2614 else if (nb_vars_a == 1 && nb_vars_b == 1)
2616 /* Both functions should have the same evolution sign. */
2617 if (((A[0][0] > 0 && -A[1][0] > 0)
2618 || (A[0][0] < 0 && -A[1][0] < 0)))
2620 /* The solutions are given by:
2622 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2623 | [u21 u22] [y0]
2625 For a given integer t. Using the following variables,
2627 | i0 = u11 * gamma / gcd_alpha_beta
2628 | j0 = u12 * gamma / gcd_alpha_beta
2629 | i1 = u21
2630 | j1 = u22
2632 the solutions are:
2634 | x0 = i0 + i1 * t,
2635 | y0 = j0 + j1 * t. */
2636 HOST_WIDE_INT i0, j0, i1, j1;
2638 i0 = U[0][0] * gamma / gcd_alpha_beta;
2639 j0 = U[0][1] * gamma / gcd_alpha_beta;
2640 i1 = U[1][0];
2641 j1 = U[1][1];
2643 if ((i1 == 0 && i0 < 0)
2644 || (j1 == 0 && j0 < 0))
2646 /* There is no solution.
2647 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2648 falls in here, but for the moment we don't look at the
2649 upper bound of the iteration domain. */
2650 *overlaps_a = conflict_fn_no_dependence ();
2651 *overlaps_b = conflict_fn_no_dependence ();
2652 *last_conflicts = integer_zero_node;
2653 goto end_analyze_subs_aa;
2656 if (i1 > 0 && j1 > 0)
2658 HOST_WIDE_INT niter_a
2659 = max_stmt_executions_int (get_chrec_loop (chrec_a));
2660 HOST_WIDE_INT niter_b
2661 = max_stmt_executions_int (get_chrec_loop (chrec_b));
2662 HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2664 /* (X0, Y0) is a solution of the Diophantine equation:
2665 "chrec_a (X0) = chrec_b (Y0)". */
2666 HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2667 CEIL (-j0, j1));
2668 HOST_WIDE_INT x0 = i1 * tau1 + i0;
2669 HOST_WIDE_INT y0 = j1 * tau1 + j0;
2671 /* (X1, Y1) is the smallest positive solution of the eq
2672 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2673 first conflict occurs. */
2674 HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2675 HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2676 HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2678 if (niter > 0)
2680 HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2681 FLOOR_DIV (niter - j0, j1));
2682 HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2684 /* If the overlap occurs outside of the bounds of the
2685 loop, there is no dependence. */
2686 if (x1 >= niter || y1 >= niter)
2688 *overlaps_a = conflict_fn_no_dependence ();
2689 *overlaps_b = conflict_fn_no_dependence ();
2690 *last_conflicts = integer_zero_node;
2691 goto end_analyze_subs_aa;
2693 else
2694 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2696 else
2697 *last_conflicts = chrec_dont_know;
2699 *overlaps_a
2700 = conflict_fn (1,
2701 affine_fn_univar (build_int_cst (NULL_TREE, x1),
2703 build_int_cst (NULL_TREE, i1)));
2704 *overlaps_b
2705 = conflict_fn (1,
2706 affine_fn_univar (build_int_cst (NULL_TREE, y1),
2708 build_int_cst (NULL_TREE, j1)));
2710 else
2712 /* FIXME: For the moment, the upper bound of the
2713 iteration domain for i and j is not checked. */
2714 if (dump_file && (dump_flags & TDF_DETAILS))
2715 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2716 *overlaps_a = conflict_fn_not_known ();
2717 *overlaps_b = conflict_fn_not_known ();
2718 *last_conflicts = chrec_dont_know;
2721 else
2723 if (dump_file && (dump_flags & TDF_DETAILS))
2724 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2725 *overlaps_a = conflict_fn_not_known ();
2726 *overlaps_b = conflict_fn_not_known ();
2727 *last_conflicts = chrec_dont_know;
2730 else
2732 if (dump_file && (dump_flags & TDF_DETAILS))
2733 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2734 *overlaps_a = conflict_fn_not_known ();
2735 *overlaps_b = conflict_fn_not_known ();
2736 *last_conflicts = chrec_dont_know;
2739 end_analyze_subs_aa:
2740 obstack_free (&scratch_obstack, NULL);
2741 if (dump_file && (dump_flags & TDF_DETAILS))
2743 fprintf (dump_file, " (overlaps_a = ");
2744 dump_conflict_function (dump_file, *overlaps_a);
2745 fprintf (dump_file, ")\n (overlaps_b = ");
2746 dump_conflict_function (dump_file, *overlaps_b);
2747 fprintf (dump_file, "))\n");
2751 /* Returns true when analyze_subscript_affine_affine can be used for
2752 determining the dependence relation between chrec_a and chrec_b,
2753 that contain symbols. This function modifies chrec_a and chrec_b
2754 such that the analysis result is the same, and such that they don't
2755 contain symbols, and then can safely be passed to the analyzer.
2757 Example: The analysis of the following tuples of evolutions produce
2758 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2759 vs. {0, +, 1}_1
2761 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2762 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2765 static bool
2766 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2768 tree diff, type, left_a, left_b, right_b;
2770 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2771 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2772 /* FIXME: For the moment not handled. Might be refined later. */
2773 return false;
2775 type = chrec_type (*chrec_a);
2776 left_a = CHREC_LEFT (*chrec_a);
2777 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
2778 diff = chrec_fold_minus (type, left_a, left_b);
2780 if (!evolution_function_is_constant_p (diff))
2781 return false;
2783 if (dump_file && (dump_flags & TDF_DETAILS))
2784 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2786 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2787 diff, CHREC_RIGHT (*chrec_a));
2788 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
2789 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2790 build_int_cst (type, 0),
2791 right_b);
2792 return true;
2795 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2796 *OVERLAPS_B are initialized to the functions that describe the
2797 relation between the elements accessed twice by CHREC_A and
2798 CHREC_B. For k >= 0, the following property is verified:
2800 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2802 static void
2803 analyze_siv_subscript (tree chrec_a,
2804 tree chrec_b,
2805 conflict_function **overlaps_a,
2806 conflict_function **overlaps_b,
2807 tree *last_conflicts,
2808 int loop_nest_num)
2810 dependence_stats.num_siv++;
2812 if (dump_file && (dump_flags & TDF_DETAILS))
2813 fprintf (dump_file, "(analyze_siv_subscript \n");
2815 if (evolution_function_is_constant_p (chrec_a)
2816 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2817 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2818 overlaps_a, overlaps_b, last_conflicts);
2820 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2821 && evolution_function_is_constant_p (chrec_b))
2822 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2823 overlaps_b, overlaps_a, last_conflicts);
2825 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2826 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2828 if (!chrec_contains_symbols (chrec_a)
2829 && !chrec_contains_symbols (chrec_b))
2831 analyze_subscript_affine_affine (chrec_a, chrec_b,
2832 overlaps_a, overlaps_b,
2833 last_conflicts);
2835 if (CF_NOT_KNOWN_P (*overlaps_a)
2836 || CF_NOT_KNOWN_P (*overlaps_b))
2837 dependence_stats.num_siv_unimplemented++;
2838 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2839 || CF_NO_DEPENDENCE_P (*overlaps_b))
2840 dependence_stats.num_siv_independent++;
2841 else
2842 dependence_stats.num_siv_dependent++;
2844 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2845 &chrec_b))
2847 analyze_subscript_affine_affine (chrec_a, chrec_b,
2848 overlaps_a, overlaps_b,
2849 last_conflicts);
2851 if (CF_NOT_KNOWN_P (*overlaps_a)
2852 || CF_NOT_KNOWN_P (*overlaps_b))
2853 dependence_stats.num_siv_unimplemented++;
2854 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2855 || CF_NO_DEPENDENCE_P (*overlaps_b))
2856 dependence_stats.num_siv_independent++;
2857 else
2858 dependence_stats.num_siv_dependent++;
2860 else
2861 goto siv_subscript_dontknow;
2864 else
2866 siv_subscript_dontknow:;
2867 if (dump_file && (dump_flags & TDF_DETAILS))
2868 fprintf (dump_file, " siv test failed: unimplemented");
2869 *overlaps_a = conflict_fn_not_known ();
2870 *overlaps_b = conflict_fn_not_known ();
2871 *last_conflicts = chrec_dont_know;
2872 dependence_stats.num_siv_unimplemented++;
2875 if (dump_file && (dump_flags & TDF_DETAILS))
2876 fprintf (dump_file, ")\n");
2879 /* Returns false if we can prove that the greatest common divisor of the steps
2880 of CHREC does not divide CST, false otherwise. */
2882 static bool
2883 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2885 HOST_WIDE_INT cd = 0, val;
2886 tree step;
2888 if (!tree_fits_shwi_p (cst))
2889 return true;
2890 val = tree_to_shwi (cst);
2892 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2894 step = CHREC_RIGHT (chrec);
2895 if (!tree_fits_shwi_p (step))
2896 return true;
2897 cd = gcd (cd, tree_to_shwi (step));
2898 chrec = CHREC_LEFT (chrec);
2901 return val % cd == 0;
2904 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2905 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2906 functions that describe the relation between the elements accessed
2907 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2908 is verified:
2910 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2912 static void
2913 analyze_miv_subscript (tree chrec_a,
2914 tree chrec_b,
2915 conflict_function **overlaps_a,
2916 conflict_function **overlaps_b,
2917 tree *last_conflicts,
2918 struct loop *loop_nest)
2920 tree type, difference;
2922 dependence_stats.num_miv++;
2923 if (dump_file && (dump_flags & TDF_DETAILS))
2924 fprintf (dump_file, "(analyze_miv_subscript \n");
2926 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2927 chrec_a = chrec_convert (type, chrec_a, NULL);
2928 chrec_b = chrec_convert (type, chrec_b, NULL);
2929 difference = chrec_fold_minus (type, chrec_a, chrec_b);
2931 if (eq_evolutions_p (chrec_a, chrec_b))
2933 /* Access functions are the same: all the elements are accessed
2934 in the same order. */
2935 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2936 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2937 *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
2938 dependence_stats.num_miv_dependent++;
2941 else if (evolution_function_is_constant_p (difference)
2942 /* For the moment, the following is verified:
2943 evolution_function_is_affine_multivariate_p (chrec_a,
2944 loop_nest->num) */
2945 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2947 /* testsuite/.../ssa-chrec-33.c
2948 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2950 The difference is 1, and all the evolution steps are multiples
2951 of 2, consequently there are no overlapping elements. */
2952 *overlaps_a = conflict_fn_no_dependence ();
2953 *overlaps_b = conflict_fn_no_dependence ();
2954 *last_conflicts = integer_zero_node;
2955 dependence_stats.num_miv_independent++;
2958 else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2959 && !chrec_contains_symbols (chrec_a)
2960 && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2961 && !chrec_contains_symbols (chrec_b))
2963 /* testsuite/.../ssa-chrec-35.c
2964 {0, +, 1}_2 vs. {0, +, 1}_3
2965 the overlapping elements are respectively located at iterations:
2966 {0, +, 1}_x and {0, +, 1}_x,
2967 in other words, we have the equality:
2968 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2970 Other examples:
2971 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2972 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2974 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2975 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2977 analyze_subscript_affine_affine (chrec_a, chrec_b,
2978 overlaps_a, overlaps_b, last_conflicts);
2980 if (CF_NOT_KNOWN_P (*overlaps_a)
2981 || CF_NOT_KNOWN_P (*overlaps_b))
2982 dependence_stats.num_miv_unimplemented++;
2983 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2984 || CF_NO_DEPENDENCE_P (*overlaps_b))
2985 dependence_stats.num_miv_independent++;
2986 else
2987 dependence_stats.num_miv_dependent++;
2990 else
2992 /* When the analysis is too difficult, answer "don't know". */
2993 if (dump_file && (dump_flags & TDF_DETAILS))
2994 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2996 *overlaps_a = conflict_fn_not_known ();
2997 *overlaps_b = conflict_fn_not_known ();
2998 *last_conflicts = chrec_dont_know;
2999 dependence_stats.num_miv_unimplemented++;
3002 if (dump_file && (dump_flags & TDF_DETAILS))
3003 fprintf (dump_file, ")\n");
3006 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
3007 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
3008 OVERLAP_ITERATIONS_B are initialized with two functions that
3009 describe the iterations that contain conflicting elements.
3011 Remark: For an integer k >= 0, the following equality is true:
3013 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3016 static void
3017 analyze_overlapping_iterations (tree chrec_a,
3018 tree chrec_b,
3019 conflict_function **overlap_iterations_a,
3020 conflict_function **overlap_iterations_b,
3021 tree *last_conflicts, struct loop *loop_nest)
3023 unsigned int lnn = loop_nest->num;
3025 dependence_stats.num_subscript_tests++;
3027 if (dump_file && (dump_flags & TDF_DETAILS))
3029 fprintf (dump_file, "(analyze_overlapping_iterations \n");
3030 fprintf (dump_file, " (chrec_a = ");
3031 print_generic_expr (dump_file, chrec_a, 0);
3032 fprintf (dump_file, ")\n (chrec_b = ");
3033 print_generic_expr (dump_file, chrec_b, 0);
3034 fprintf (dump_file, ")\n");
3037 if (chrec_a == NULL_TREE
3038 || chrec_b == NULL_TREE
3039 || chrec_contains_undetermined (chrec_a)
3040 || chrec_contains_undetermined (chrec_b))
3042 dependence_stats.num_subscript_undetermined++;
3044 *overlap_iterations_a = conflict_fn_not_known ();
3045 *overlap_iterations_b = conflict_fn_not_known ();
3048 /* If they are the same chrec, and are affine, they overlap
3049 on every iteration. */
3050 else if (eq_evolutions_p (chrec_a, chrec_b)
3051 && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
3052 || operand_equal_p (chrec_a, chrec_b, 0)))
3054 dependence_stats.num_same_subscript_function++;
3055 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3056 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3057 *last_conflicts = chrec_dont_know;
3060 /* If they aren't the same, and aren't affine, we can't do anything
3061 yet. */
3062 else if ((chrec_contains_symbols (chrec_a)
3063 || chrec_contains_symbols (chrec_b))
3064 && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
3065 || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
3067 dependence_stats.num_subscript_undetermined++;
3068 *overlap_iterations_a = conflict_fn_not_known ();
3069 *overlap_iterations_b = conflict_fn_not_known ();
3072 else if (ziv_subscript_p (chrec_a, chrec_b))
3073 analyze_ziv_subscript (chrec_a, chrec_b,
3074 overlap_iterations_a, overlap_iterations_b,
3075 last_conflicts);
3077 else if (siv_subscript_p (chrec_a, chrec_b))
3078 analyze_siv_subscript (chrec_a, chrec_b,
3079 overlap_iterations_a, overlap_iterations_b,
3080 last_conflicts, lnn);
3082 else
3083 analyze_miv_subscript (chrec_a, chrec_b,
3084 overlap_iterations_a, overlap_iterations_b,
3085 last_conflicts, loop_nest);
3087 if (dump_file && (dump_flags & TDF_DETAILS))
3089 fprintf (dump_file, " (overlap_iterations_a = ");
3090 dump_conflict_function (dump_file, *overlap_iterations_a);
3091 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3092 dump_conflict_function (dump_file, *overlap_iterations_b);
3093 fprintf (dump_file, "))\n");
3097 /* Helper function for uniquely inserting distance vectors. */
3099 static void
3100 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3102 unsigned i;
3103 lambda_vector v;
3105 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, v)
3106 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3107 return;
3109 DDR_DIST_VECTS (ddr).safe_push (dist_v);
3112 /* Helper function for uniquely inserting direction vectors. */
3114 static void
3115 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3117 unsigned i;
3118 lambda_vector v;
3120 FOR_EACH_VEC_ELT (DDR_DIR_VECTS (ddr), i, v)
3121 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3122 return;
3124 DDR_DIR_VECTS (ddr).safe_push (dir_v);
3127 /* Add a distance of 1 on all the loops outer than INDEX. If we
3128 haven't yet determined a distance for this outer loop, push a new
3129 distance vector composed of the previous distance, and a distance
3130 of 1 for this outer loop. Example:
3132 | loop_1
3133 | loop_2
3134 | A[10]
3135 | endloop_2
3136 | endloop_1
3138 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3139 save (0, 1), then we have to save (1, 0). */
3141 static void
3142 add_outer_distances (struct data_dependence_relation *ddr,
3143 lambda_vector dist_v, int index)
3145 /* For each outer loop where init_v is not set, the accesses are
3146 in dependence of distance 1 in the loop. */
3147 while (--index >= 0)
3149 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3150 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3151 save_v[index] = 1;
3152 save_dist_v (ddr, save_v);
3156 /* Return false when fail to represent the data dependence as a
3157 distance vector. INIT_B is set to true when a component has been
3158 added to the distance vector DIST_V. INDEX_CARRY is then set to
3159 the index in DIST_V that carries the dependence. */
3161 static bool
3162 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3163 struct data_reference *ddr_a,
3164 struct data_reference *ddr_b,
3165 lambda_vector dist_v, bool *init_b,
3166 int *index_carry)
3168 unsigned i;
3169 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3171 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3173 tree access_fn_a, access_fn_b;
3174 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3176 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3178 non_affine_dependence_relation (ddr);
3179 return false;
3182 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3183 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3185 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3186 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3188 int dist, index;
3189 int var_a = CHREC_VARIABLE (access_fn_a);
3190 int var_b = CHREC_VARIABLE (access_fn_b);
3192 if (var_a != var_b
3193 || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3195 non_affine_dependence_relation (ddr);
3196 return false;
3199 dist = int_cst_value (SUB_DISTANCE (subscript));
3200 index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
3201 *index_carry = MIN (index, *index_carry);
3203 /* This is the subscript coupling test. If we have already
3204 recorded a distance for this loop (a distance coming from
3205 another subscript), it should be the same. For example,
3206 in the following code, there is no dependence:
3208 | loop i = 0, N, 1
3209 | T[i+1][i] = ...
3210 | ... = T[i][i]
3211 | endloop
3213 if (init_v[index] != 0 && dist_v[index] != dist)
3215 finalize_ddr_dependent (ddr, chrec_known);
3216 return false;
3219 dist_v[index] = dist;
3220 init_v[index] = 1;
3221 *init_b = true;
3223 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
3225 /* This can be for example an affine vs. constant dependence
3226 (T[i] vs. T[3]) that is not an affine dependence and is
3227 not representable as a distance vector. */
3228 non_affine_dependence_relation (ddr);
3229 return false;
3233 return true;
3236 /* Return true when the DDR contains only constant access functions. */
3238 static bool
3239 constant_access_functions (const struct data_dependence_relation *ddr)
3241 unsigned i;
3243 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3244 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
3245 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
3246 return false;
3248 return true;
3251 /* Helper function for the case where DDR_A and DDR_B are the same
3252 multivariate access function with a constant step. For an example
3253 see pr34635-1.c. */
3255 static void
3256 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3258 int x_1, x_2;
3259 tree c_1 = CHREC_LEFT (c_2);
3260 tree c_0 = CHREC_LEFT (c_1);
3261 lambda_vector dist_v;
3262 int v1, v2, cd;
3264 /* Polynomials with more than 2 variables are not handled yet. When
3265 the evolution steps are parameters, it is not possible to
3266 represent the dependence using classical distance vectors. */
3267 if (TREE_CODE (c_0) != INTEGER_CST
3268 || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
3269 || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
3271 DDR_AFFINE_P (ddr) = false;
3272 return;
3275 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3276 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3278 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3279 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3280 v1 = int_cst_value (CHREC_RIGHT (c_1));
3281 v2 = int_cst_value (CHREC_RIGHT (c_2));
3282 cd = gcd (v1, v2);
3283 v1 /= cd;
3284 v2 /= cd;
3286 if (v2 < 0)
3288 v2 = -v2;
3289 v1 = -v1;
3292 dist_v[x_1] = v2;
3293 dist_v[x_2] = -v1;
3294 save_dist_v (ddr, dist_v);
3296 add_outer_distances (ddr, dist_v, x_1);
3299 /* Helper function for the case where DDR_A and DDR_B are the same
3300 access functions. */
3302 static void
3303 add_other_self_distances (struct data_dependence_relation *ddr)
3305 lambda_vector dist_v;
3306 unsigned i;
3307 int index_carry = DDR_NB_LOOPS (ddr);
3309 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3311 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3313 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3315 if (!evolution_function_is_univariate_p (access_fun))
3317 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3319 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3320 return;
3323 access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
3325 if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
3326 add_multivariate_self_dist (ddr, access_fun);
3327 else
3328 /* The evolution step is not constant: it varies in
3329 the outer loop, so this cannot be represented by a
3330 distance vector. For example in pr34635.c the
3331 evolution is {0, +, {0, +, 4}_1}_2. */
3332 DDR_AFFINE_P (ddr) = false;
3334 return;
3337 index_carry = MIN (index_carry,
3338 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3339 DDR_LOOP_NEST (ddr)));
3343 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3344 add_outer_distances (ddr, dist_v, index_carry);
3347 static void
3348 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
3350 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3352 dist_v[DDR_INNER_LOOP (ddr)] = 1;
3353 save_dist_v (ddr, dist_v);
3356 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3357 is the case for example when access functions are the same and
3358 equal to a constant, as in:
3360 | loop_1
3361 | A[3] = ...
3362 | ... = A[3]
3363 | endloop_1
3365 in which case the distance vectors are (0) and (1). */
3367 static void
3368 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
3370 unsigned i, j;
3372 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3374 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
3375 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
3376 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
3378 for (j = 0; j < ca->n; j++)
3379 if (affine_function_zero_p (ca->fns[j]))
3381 insert_innermost_unit_dist_vector (ddr);
3382 return;
3385 for (j = 0; j < cb->n; j++)
3386 if (affine_function_zero_p (cb->fns[j]))
3388 insert_innermost_unit_dist_vector (ddr);
3389 return;
3394 /* Compute the classic per loop distance vector. DDR is the data
3395 dependence relation to build a vector from. Return false when fail
3396 to represent the data dependence as a distance vector. */
3398 static bool
3399 build_classic_dist_vector (struct data_dependence_relation *ddr,
3400 struct loop *loop_nest)
3402 bool init_b = false;
3403 int index_carry = DDR_NB_LOOPS (ddr);
3404 lambda_vector dist_v;
3406 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3407 return false;
3409 if (same_access_functions (ddr))
3411 /* Save the 0 vector. */
3412 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3413 save_dist_v (ddr, dist_v);
3415 if (constant_access_functions (ddr))
3416 add_distance_for_zero_overlaps (ddr);
3418 if (DDR_NB_LOOPS (ddr) > 1)
3419 add_other_self_distances (ddr);
3421 return true;
3424 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3425 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3426 dist_v, &init_b, &index_carry))
3427 return false;
3429 /* Save the distance vector if we initialized one. */
3430 if (init_b)
3432 /* Verify a basic constraint: classic distance vectors should
3433 always be lexicographically positive.
3435 Data references are collected in the order of execution of
3436 the program, thus for the following loop
3438 | for (i = 1; i < 100; i++)
3439 | for (j = 1; j < 100; j++)
3441 | t = T[j+1][i-1]; // A
3442 | T[j][i] = t + 2; // B
3445 references are collected following the direction of the wind:
3446 A then B. The data dependence tests are performed also
3447 following this order, such that we're looking at the distance
3448 separating the elements accessed by A from the elements later
3449 accessed by B. But in this example, the distance returned by
3450 test_dep (A, B) is lexicographically negative (-1, 1), that
3451 means that the access A occurs later than B with respect to
3452 the outer loop, ie. we're actually looking upwind. In this
3453 case we solve test_dep (B, A) looking downwind to the
3454 lexicographically positive solution, that returns the
3455 distance vector (1, -1). */
3456 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3458 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3459 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3460 loop_nest))
3461 return false;
3462 compute_subscript_distance (ddr);
3463 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3464 save_v, &init_b, &index_carry))
3465 return false;
3466 save_dist_v (ddr, save_v);
3467 DDR_REVERSED_P (ddr) = true;
3469 /* In this case there is a dependence forward for all the
3470 outer loops:
3472 | for (k = 1; k < 100; k++)
3473 | for (i = 1; i < 100; i++)
3474 | for (j = 1; j < 100; j++)
3476 | t = T[j+1][i-1]; // A
3477 | T[j][i] = t + 2; // B
3480 the vectors are:
3481 (0, 1, -1)
3482 (1, 1, -1)
3483 (1, -1, 1)
3485 if (DDR_NB_LOOPS (ddr) > 1)
3487 add_outer_distances (ddr, save_v, index_carry);
3488 add_outer_distances (ddr, dist_v, index_carry);
3491 else
3493 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3494 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3496 if (DDR_NB_LOOPS (ddr) > 1)
3498 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3500 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3501 DDR_A (ddr), loop_nest))
3502 return false;
3503 compute_subscript_distance (ddr);
3504 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3505 opposite_v, &init_b,
3506 &index_carry))
3507 return false;
3509 save_dist_v (ddr, save_v);
3510 add_outer_distances (ddr, dist_v, index_carry);
3511 add_outer_distances (ddr, opposite_v, index_carry);
3513 else
3514 save_dist_v (ddr, save_v);
3517 else
3519 /* There is a distance of 1 on all the outer loops: Example:
3520 there is a dependence of distance 1 on loop_1 for the array A.
3522 | loop_1
3523 | A[5] = ...
3524 | endloop
3526 add_outer_distances (ddr, dist_v,
3527 lambda_vector_first_nz (dist_v,
3528 DDR_NB_LOOPS (ddr), 0));
3531 if (dump_file && (dump_flags & TDF_DETAILS))
3533 unsigned i;
3535 fprintf (dump_file, "(build_classic_dist_vector\n");
3536 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3538 fprintf (dump_file, " dist_vector = (");
3539 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3540 DDR_NB_LOOPS (ddr));
3541 fprintf (dump_file, " )\n");
3543 fprintf (dump_file, ")\n");
3546 return true;
3549 /* Return the direction for a given distance.
3550 FIXME: Computing dir this way is suboptimal, since dir can catch
3551 cases that dist is unable to represent. */
3553 static inline enum data_dependence_direction
3554 dir_from_dist (int dist)
3556 if (dist > 0)
3557 return dir_positive;
3558 else if (dist < 0)
3559 return dir_negative;
3560 else
3561 return dir_equal;
3564 /* Compute the classic per loop direction vector. DDR is the data
3565 dependence relation to build a vector from. */
3567 static void
3568 build_classic_dir_vector (struct data_dependence_relation *ddr)
3570 unsigned i, j;
3571 lambda_vector dist_v;
3573 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
3575 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3577 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3578 dir_v[j] = dir_from_dist (dist_v[j]);
3580 save_dir_v (ddr, dir_v);
3584 /* Helper function. Returns true when there is a dependence between
3585 data references DRA and DRB. */
3587 static bool
3588 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3589 struct data_reference *dra,
3590 struct data_reference *drb,
3591 struct loop *loop_nest)
3593 unsigned int i;
3594 tree last_conflicts;
3595 struct subscript *subscript;
3596 tree res = NULL_TREE;
3598 for (i = 0; DDR_SUBSCRIPTS (ddr).iterate (i, &subscript); i++)
3600 conflict_function *overlaps_a, *overlaps_b;
3602 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3603 DR_ACCESS_FN (drb, i),
3604 &overlaps_a, &overlaps_b,
3605 &last_conflicts, loop_nest);
3607 if (SUB_CONFLICTS_IN_A (subscript))
3608 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3609 if (SUB_CONFLICTS_IN_B (subscript))
3610 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3612 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3613 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3614 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3616 /* If there is any undetermined conflict function we have to
3617 give a conservative answer in case we cannot prove that
3618 no dependence exists when analyzing another subscript. */
3619 if (CF_NOT_KNOWN_P (overlaps_a)
3620 || CF_NOT_KNOWN_P (overlaps_b))
3622 res = chrec_dont_know;
3623 continue;
3626 /* When there is a subscript with no dependence we can stop. */
3627 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3628 || CF_NO_DEPENDENCE_P (overlaps_b))
3630 res = chrec_known;
3631 break;
3635 if (res == NULL_TREE)
3636 return true;
3638 if (res == chrec_known)
3639 dependence_stats.num_dependence_independent++;
3640 else
3641 dependence_stats.num_dependence_undetermined++;
3642 finalize_ddr_dependent (ddr, res);
3643 return false;
3646 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3648 static void
3649 subscript_dependence_tester (struct data_dependence_relation *ddr,
3650 struct loop *loop_nest)
3652 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3653 dependence_stats.num_dependence_dependent++;
3655 compute_subscript_distance (ddr);
3656 if (build_classic_dist_vector (ddr, loop_nest))
3657 build_classic_dir_vector (ddr);
3660 /* Returns true when all the access functions of A are affine or
3661 constant with respect to LOOP_NEST. */
3663 static bool
3664 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3665 const struct loop *loop_nest)
3667 unsigned int i;
3668 vec<tree> fns = DR_ACCESS_FNS (a);
3669 tree t;
3671 FOR_EACH_VEC_ELT (fns, i, t)
3672 if (!evolution_function_is_invariant_p (t, loop_nest->num)
3673 && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3674 return false;
3676 return true;
3679 /* Initializes an equation for an OMEGA problem using the information
3680 contained in the ACCESS_FUN. Returns true when the operation
3681 succeeded.
3683 PB is the omega constraint system.
3684 EQ is the number of the equation to be initialized.
3685 OFFSET is used for shifting the variables names in the constraints:
3686 a constrain is composed of 2 * the number of variables surrounding
3687 dependence accesses. OFFSET is set either to 0 for the first n variables,
3688 then it is set to n.
3689 ACCESS_FUN is expected to be an affine chrec. */
3691 static bool
3692 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3693 unsigned int offset, tree access_fun,
3694 struct data_dependence_relation *ddr)
3696 switch (TREE_CODE (access_fun))
3698 case POLYNOMIAL_CHREC:
3700 tree left = CHREC_LEFT (access_fun);
3701 tree right = CHREC_RIGHT (access_fun);
3702 int var = CHREC_VARIABLE (access_fun);
3703 unsigned var_idx;
3705 if (TREE_CODE (right) != INTEGER_CST)
3706 return false;
3708 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3709 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3711 /* Compute the innermost loop index. */
3712 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3714 if (offset == 0)
3715 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3716 += int_cst_value (right);
3718 switch (TREE_CODE (left))
3720 case POLYNOMIAL_CHREC:
3721 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3723 case INTEGER_CST:
3724 pb->eqs[eq].coef[0] += int_cst_value (left);
3725 return true;
3727 default:
3728 return false;
3732 case INTEGER_CST:
3733 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3734 return true;
3736 default:
3737 return false;
3741 /* As explained in the comments preceding init_omega_for_ddr, we have
3742 to set up a system for each loop level, setting outer loops
3743 variation to zero, and current loop variation to positive or zero.
3744 Save each lexico positive distance vector. */
3746 static void
3747 omega_extract_distance_vectors (omega_pb pb,
3748 struct data_dependence_relation *ddr)
3750 int eq, geq;
3751 unsigned i, j;
3752 struct loop *loopi, *loopj;
3753 enum omega_result res;
3755 /* Set a new problem for each loop in the nest. The basis is the
3756 problem that we have initialized until now. On top of this we
3757 add new constraints. */
3758 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3759 && DDR_LOOP_NEST (ddr).iterate (i, &loopi); i++)
3761 int dist = 0;
3762 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3763 DDR_NB_LOOPS (ddr));
3765 omega_copy_problem (copy, pb);
3767 /* For all the outer loops "loop_j", add "dj = 0". */
3768 for (j = 0; j < i && DDR_LOOP_NEST (ddr).iterate (j, &loopj); j++)
3770 eq = omega_add_zero_eq (copy, omega_black);
3771 copy->eqs[eq].coef[j + 1] = 1;
3774 /* For "loop_i", add "0 <= di". */
3775 geq = omega_add_zero_geq (copy, omega_black);
3776 copy->geqs[geq].coef[i + 1] = 1;
3778 /* Reduce the constraint system, and test that the current
3779 problem is feasible. */
3780 res = omega_simplify_problem (copy);
3781 if (res == omega_false
3782 || res == omega_unknown
3783 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3784 goto next_problem;
3786 for (eq = 0; eq < copy->num_subs; eq++)
3787 if (copy->subs[eq].key == (int) i + 1)
3789 dist = copy->subs[eq].coef[0];
3790 goto found_dist;
3793 if (dist == 0)
3795 /* Reinitialize problem... */
3796 omega_copy_problem (copy, pb);
3797 for (j = 0; j < i && DDR_LOOP_NEST (ddr).iterate (j, &loopj); j++)
3799 eq = omega_add_zero_eq (copy, omega_black);
3800 copy->eqs[eq].coef[j + 1] = 1;
3803 /* ..., but this time "di = 1". */
3804 eq = omega_add_zero_eq (copy, omega_black);
3805 copy->eqs[eq].coef[i + 1] = 1;
3806 copy->eqs[eq].coef[0] = -1;
3808 res = omega_simplify_problem (copy);
3809 if (res == omega_false
3810 || res == omega_unknown
3811 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3812 goto next_problem;
3814 for (eq = 0; eq < copy->num_subs; eq++)
3815 if (copy->subs[eq].key == (int) i + 1)
3817 dist = copy->subs[eq].coef[0];
3818 goto found_dist;
3822 found_dist:;
3823 /* Save the lexicographically positive distance vector. */
3824 if (dist >= 0)
3826 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3827 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3829 dist_v[i] = dist;
3831 for (eq = 0; eq < copy->num_subs; eq++)
3832 if (copy->subs[eq].key > 0)
3834 dist = copy->subs[eq].coef[0];
3835 dist_v[copy->subs[eq].key - 1] = dist;
3838 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3839 dir_v[j] = dir_from_dist (dist_v[j]);
3841 save_dist_v (ddr, dist_v);
3842 save_dir_v (ddr, dir_v);
3845 next_problem:;
3846 omega_free_problem (copy);
3850 /* This is called for each subscript of a tuple of data references:
3851 insert an equality for representing the conflicts. */
3853 static bool
3854 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3855 struct data_dependence_relation *ddr,
3856 omega_pb pb, bool *maybe_dependent)
3858 int eq;
3859 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3860 TREE_TYPE (access_fun_b));
3861 tree fun_a = chrec_convert (type, access_fun_a, NULL);
3862 tree fun_b = chrec_convert (type, access_fun_b, NULL);
3863 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3864 tree minus_one;
3866 /* When the fun_a - fun_b is not constant, the dependence is not
3867 captured by the classic distance vector representation. */
3868 if (TREE_CODE (difference) != INTEGER_CST)
3869 return false;
3871 /* ZIV test. */
3872 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3874 /* There is no dependence. */
3875 *maybe_dependent = false;
3876 return true;
3879 minus_one = build_int_cst (type, -1);
3880 fun_b = chrec_fold_multiply (type, fun_b, minus_one);
3882 eq = omega_add_zero_eq (pb, omega_black);
3883 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3884 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3885 /* There is probably a dependence, but the system of
3886 constraints cannot be built: answer "don't know". */
3887 return false;
3889 /* GCD test. */
3890 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3891 && !int_divides_p (lambda_vector_gcd
3892 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3893 2 * DDR_NB_LOOPS (ddr)),
3894 pb->eqs[eq].coef[0]))
3896 /* There is no dependence. */
3897 *maybe_dependent = false;
3898 return true;
3901 return true;
3904 /* Helper function, same as init_omega_for_ddr but specialized for
3905 data references A and B. */
3907 static bool
3908 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3909 struct data_dependence_relation *ddr,
3910 omega_pb pb, bool *maybe_dependent)
3912 unsigned i;
3913 int ineq;
3914 struct loop *loopi;
3915 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3917 /* Insert an equality per subscript. */
3918 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3920 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3921 ddr, pb, maybe_dependent))
3922 return false;
3923 else if (*maybe_dependent == false)
3925 /* There is no dependence. */
3926 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3927 return true;
3931 /* Insert inequalities: constraints corresponding to the iteration
3932 domain, i.e. the loops surrounding the references "loop_x" and
3933 the distance variables "dx". The layout of the OMEGA
3934 representation is as follows:
3935 - coef[0] is the constant
3936 - coef[1..nb_loops] are the protected variables that will not be
3937 removed by the solver: the "dx"
3938 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3940 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3941 && DDR_LOOP_NEST (ddr).iterate (i, &loopi); i++)
3943 HOST_WIDE_INT nbi = max_stmt_executions_int (loopi);
3945 /* 0 <= loop_x */
3946 ineq = omega_add_zero_geq (pb, omega_black);
3947 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3949 /* 0 <= loop_x + dx */
3950 ineq = omega_add_zero_geq (pb, omega_black);
3951 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3952 pb->geqs[ineq].coef[i + 1] = 1;
3954 if (nbi != -1)
3956 /* loop_x <= nb_iters */
3957 ineq = omega_add_zero_geq (pb, omega_black);
3958 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3959 pb->geqs[ineq].coef[0] = nbi;
3961 /* loop_x + dx <= nb_iters */
3962 ineq = omega_add_zero_geq (pb, omega_black);
3963 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3964 pb->geqs[ineq].coef[i + 1] = -1;
3965 pb->geqs[ineq].coef[0] = nbi;
3967 /* A step "dx" bigger than nb_iters is not feasible, so
3968 add "0 <= nb_iters + dx", */
3969 ineq = omega_add_zero_geq (pb, omega_black);
3970 pb->geqs[ineq].coef[i + 1] = 1;
3971 pb->geqs[ineq].coef[0] = nbi;
3972 /* and "dx <= nb_iters". */
3973 ineq = omega_add_zero_geq (pb, omega_black);
3974 pb->geqs[ineq].coef[i + 1] = -1;
3975 pb->geqs[ineq].coef[0] = nbi;
3979 omega_extract_distance_vectors (pb, ddr);
3981 return true;
3984 /* Sets up the Omega dependence problem for the data dependence
3985 relation DDR. Returns false when the constraint system cannot be
3986 built, ie. when the test answers "don't know". Returns true
3987 otherwise, and when independence has been proved (using one of the
3988 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3989 set MAYBE_DEPENDENT to true.
3991 Example: for setting up the dependence system corresponding to the
3992 conflicting accesses
3994 | loop_i
3995 | loop_j
3996 | A[i, i+1] = ...
3997 | ... A[2*j, 2*(i + j)]
3998 | endloop_j
3999 | endloop_i
4001 the following constraints come from the iteration domain:
4003 0 <= i <= Ni
4004 0 <= i + di <= Ni
4005 0 <= j <= Nj
4006 0 <= j + dj <= Nj
4008 where di, dj are the distance variables. The constraints
4009 representing the conflicting elements are:
4011 i = 2 * (j + dj)
4012 i + 1 = 2 * (i + di + j + dj)
4014 For asking that the resulting distance vector (di, dj) be
4015 lexicographically positive, we insert the constraint "di >= 0". If
4016 "di = 0" in the solution, we fix that component to zero, and we
4017 look at the inner loops: we set a new problem where all the outer
4018 loop distances are zero, and fix this inner component to be
4019 positive. When one of the components is positive, we save that
4020 distance, and set a new problem where the distance on this loop is
4021 zero, searching for other distances in the inner loops. Here is
4022 the classic example that illustrates that we have to set for each
4023 inner loop a new problem:
4025 | loop_1
4026 | loop_2
4027 | A[10]
4028 | endloop_2
4029 | endloop_1
4031 we have to save two distances (1, 0) and (0, 1).
4033 Given two array references, refA and refB, we have to set the
4034 dependence problem twice, refA vs. refB and refB vs. refA, and we
4035 cannot do a single test, as refB might occur before refA in the
4036 inner loops, and the contrary when considering outer loops: ex.
4038 | loop_0
4039 | loop_1
4040 | loop_2
4041 | T[{1,+,1}_2][{1,+,1}_1] // refA
4042 | T[{2,+,1}_2][{0,+,1}_1] // refB
4043 | endloop_2
4044 | endloop_1
4045 | endloop_0
4047 refB touches the elements in T before refA, and thus for the same
4048 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4049 but for successive loop_0 iterations, we have (1, -1, 1)
4051 The Omega solver expects the distance variables ("di" in the
4052 previous example) to come first in the constraint system (as
4053 variables to be protected, or "safe" variables), the constraint
4054 system is built using the following layout:
4056 "cst | distance vars | index vars".
4059 static bool
4060 init_omega_for_ddr (struct data_dependence_relation *ddr,
4061 bool *maybe_dependent)
4063 omega_pb pb;
4064 bool res = false;
4066 *maybe_dependent = true;
4068 if (same_access_functions (ddr))
4070 unsigned j;
4071 lambda_vector dir_v;
4073 /* Save the 0 vector. */
4074 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4075 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4076 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4077 dir_v[j] = dir_equal;
4078 save_dir_v (ddr, dir_v);
4080 /* Save the dependences carried by outer loops. */
4081 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4082 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4083 maybe_dependent);
4084 omega_free_problem (pb);
4085 return res;
4088 /* Omega expects the protected variables (those that have to be kept
4089 after elimination) to appear first in the constraint system.
4090 These variables are the distance variables. In the following
4091 initialization we declare NB_LOOPS safe variables, and the total
4092 number of variables for the constraint system is 2*NB_LOOPS. */
4093 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4094 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4095 maybe_dependent);
4096 omega_free_problem (pb);
4098 /* Stop computation if not decidable, or no dependence. */
4099 if (res == false || *maybe_dependent == false)
4100 return res;
4102 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4103 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
4104 maybe_dependent);
4105 omega_free_problem (pb);
4107 return res;
4110 /* Return true when DDR contains the same information as that stored
4111 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4113 static bool
4114 ddr_consistent_p (FILE *file,
4115 struct data_dependence_relation *ddr,
4116 vec<lambda_vector> dist_vects,
4117 vec<lambda_vector> dir_vects)
4119 unsigned int i, j;
4121 /* If dump_file is set, output there. */
4122 if (dump_file && (dump_flags & TDF_DETAILS))
4123 file = dump_file;
4125 if (dist_vects.length () != DDR_NUM_DIST_VECTS (ddr))
4127 lambda_vector b_dist_v;
4128 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4129 dist_vects.length (),
4130 DDR_NUM_DIST_VECTS (ddr));
4132 fprintf (file, "Banerjee dist vectors:\n");
4133 FOR_EACH_VEC_ELT (dist_vects, i, b_dist_v)
4134 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
4136 fprintf (file, "Omega dist vectors:\n");
4137 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4138 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
4140 fprintf (file, "data dependence relation:\n");
4141 dump_data_dependence_relation (file, ddr);
4143 fprintf (file, ")\n");
4144 return false;
4147 if (dir_vects.length () != DDR_NUM_DIR_VECTS (ddr))
4149 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4150 dir_vects.length (),
4151 DDR_NUM_DIR_VECTS (ddr));
4152 return false;
4155 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4157 lambda_vector a_dist_v;
4158 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
4160 /* Distance vectors are not ordered in the same way in the DDR
4161 and in the DIST_VECTS: search for a matching vector. */
4162 FOR_EACH_VEC_ELT (dist_vects, j, a_dist_v)
4163 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
4164 break;
4166 if (j == dist_vects.length ())
4168 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
4169 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
4170 fprintf (file, "not found in Omega dist vectors:\n");
4171 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
4172 fprintf (file, "data dependence relation:\n");
4173 dump_data_dependence_relation (file, ddr);
4174 fprintf (file, ")\n");
4178 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
4180 lambda_vector a_dir_v;
4181 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
4183 /* Direction vectors are not ordered in the same way in the DDR
4184 and in the DIR_VECTS: search for a matching vector. */
4185 FOR_EACH_VEC_ELT (dir_vects, j, a_dir_v)
4186 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
4187 break;
4189 if (j == dist_vects.length ())
4191 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
4192 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
4193 fprintf (file, "not found in Omega dir vectors:\n");
4194 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
4195 fprintf (file, "data dependence relation:\n");
4196 dump_data_dependence_relation (file, ddr);
4197 fprintf (file, ")\n");
4201 return true;
4204 /* This computes the affine dependence relation between A and B with
4205 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4206 independence between two accesses, while CHREC_DONT_KNOW is used
4207 for representing the unknown relation.
4209 Note that it is possible to stop the computation of the dependence
4210 relation the first time we detect a CHREC_KNOWN element for a given
4211 subscript. */
4213 void
4214 compute_affine_dependence (struct data_dependence_relation *ddr,
4215 struct loop *loop_nest)
4217 struct data_reference *dra = DDR_A (ddr);
4218 struct data_reference *drb = DDR_B (ddr);
4220 if (dump_file && (dump_flags & TDF_DETAILS))
4222 fprintf (dump_file, "(compute_affine_dependence\n");
4223 fprintf (dump_file, " stmt_a: ");
4224 print_gimple_stmt (dump_file, DR_STMT (dra), 0, TDF_SLIM);
4225 fprintf (dump_file, " stmt_b: ");
4226 print_gimple_stmt (dump_file, DR_STMT (drb), 0, TDF_SLIM);
4229 /* Analyze only when the dependence relation is not yet known. */
4230 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4232 dependence_stats.num_dependence_tests++;
4234 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
4235 && access_functions_are_affine_or_constant_p (drb, loop_nest))
4237 subscript_dependence_tester (ddr, loop_nest);
4239 if (flag_check_data_deps)
4241 /* Dump the dependences from the first algorithm. */
4242 if (dump_file && (dump_flags & TDF_DETAILS))
4244 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
4245 dump_data_dependence_relation (dump_file, ddr);
4248 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4250 bool maybe_dependent;
4251 vec<lambda_vector> dir_vects, dist_vects;
4253 /* Save the result of the first DD analyzer. */
4254 dist_vects = DDR_DIST_VECTS (ddr);
4255 dir_vects = DDR_DIR_VECTS (ddr);
4257 /* Reset the information. */
4258 DDR_DIST_VECTS (ddr).create (0);
4259 DDR_DIR_VECTS (ddr).create (0);
4261 /* Compute the same information using Omega. */
4262 if (!init_omega_for_ddr (ddr, &maybe_dependent))
4263 goto csys_dont_know;
4265 if (dump_file && (dump_flags & TDF_DETAILS))
4267 fprintf (dump_file, "Omega Analyzer\n");
4268 dump_data_dependence_relation (dump_file, ddr);
4271 /* Check that we get the same information. */
4272 if (maybe_dependent)
4273 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
4274 dir_vects));
4279 /* As a last case, if the dependence cannot be determined, or if
4280 the dependence is considered too difficult to determine, answer
4281 "don't know". */
4282 else
4284 csys_dont_know:;
4285 dependence_stats.num_dependence_undetermined++;
4287 if (dump_file && (dump_flags & TDF_DETAILS))
4289 fprintf (dump_file, "Data ref a:\n");
4290 dump_data_reference (dump_file, dra);
4291 fprintf (dump_file, "Data ref b:\n");
4292 dump_data_reference (dump_file, drb);
4293 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4295 finalize_ddr_dependent (ddr, chrec_dont_know);
4299 if (dump_file && (dump_flags & TDF_DETAILS))
4301 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4302 fprintf (dump_file, ") -> no dependence\n");
4303 else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4304 fprintf (dump_file, ") -> dependence analysis failed\n");
4305 else
4306 fprintf (dump_file, ")\n");
4310 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4311 the data references in DATAREFS, in the LOOP_NEST. When
4312 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4313 relations. Return true when successful, i.e. data references number
4314 is small enough to be handled. */
4316 bool
4317 compute_all_dependences (vec<data_reference_p> datarefs,
4318 vec<ddr_p> *dependence_relations,
4319 vec<loop_p> loop_nest,
4320 bool compute_self_and_rr)
4322 struct data_dependence_relation *ddr;
4323 struct data_reference *a, *b;
4324 unsigned int i, j;
4326 if ((int) datarefs.length ()
4327 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
4329 struct data_dependence_relation *ddr;
4331 /* Insert a single relation into dependence_relations:
4332 chrec_dont_know. */
4333 ddr = initialize_data_dependence_relation (NULL, NULL, loop_nest);
4334 dependence_relations->safe_push (ddr);
4335 return false;
4338 FOR_EACH_VEC_ELT (datarefs, i, a)
4339 for (j = i + 1; datarefs.iterate (j, &b); j++)
4340 if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
4342 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4343 dependence_relations->safe_push (ddr);
4344 if (loop_nest.exists ())
4345 compute_affine_dependence (ddr, loop_nest[0]);
4348 if (compute_self_and_rr)
4349 FOR_EACH_VEC_ELT (datarefs, i, a)
4351 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4352 dependence_relations->safe_push (ddr);
4353 if (loop_nest.exists ())
4354 compute_affine_dependence (ddr, loop_nest[0]);
4357 return true;
4360 /* Describes a location of a memory reference. */
4362 typedef struct data_ref_loc_d
4364 /* The memory reference. */
4365 tree ref;
4367 /* True if the memory reference is read. */
4368 bool is_read;
4369 } data_ref_loc;
4372 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4373 true if STMT clobbers memory, false otherwise. */
4375 static bool
4376 get_references_in_stmt (gimple stmt, vec<data_ref_loc, va_heap> *references)
4378 bool clobbers_memory = false;
4379 data_ref_loc ref;
4380 tree op0, op1;
4381 enum gimple_code stmt_code = gimple_code (stmt);
4383 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4384 As we cannot model data-references to not spelled out
4385 accesses give up if they may occur. */
4386 if (stmt_code == GIMPLE_CALL
4387 && !(gimple_call_flags (stmt) & ECF_CONST))
4389 /* Allow IFN_GOMP_SIMD_LANE in their own loops. */
4390 if (gimple_call_internal_p (stmt))
4391 switch (gimple_call_internal_fn (stmt))
4393 case IFN_GOMP_SIMD_LANE:
4395 struct loop *loop = gimple_bb (stmt)->loop_father;
4396 tree uid = gimple_call_arg (stmt, 0);
4397 gcc_assert (TREE_CODE (uid) == SSA_NAME);
4398 if (loop == NULL
4399 || loop->simduid != SSA_NAME_VAR (uid))
4400 clobbers_memory = true;
4401 break;
4403 case IFN_MASK_LOAD:
4404 case IFN_MASK_STORE:
4405 break;
4406 default:
4407 clobbers_memory = true;
4408 break;
4410 else
4411 clobbers_memory = true;
4413 else if (stmt_code == GIMPLE_ASM
4414 && (gimple_asm_volatile_p (as_a <gasm *> (stmt))
4415 || gimple_vuse (stmt)))
4416 clobbers_memory = true;
4418 if (!gimple_vuse (stmt))
4419 return clobbers_memory;
4421 if (stmt_code == GIMPLE_ASSIGN)
4423 tree base;
4424 op0 = gimple_assign_lhs (stmt);
4425 op1 = gimple_assign_rhs1 (stmt);
4427 if (DECL_P (op1)
4428 || (REFERENCE_CLASS_P (op1)
4429 && (base = get_base_address (op1))
4430 && TREE_CODE (base) != SSA_NAME))
4432 ref.ref = op1;
4433 ref.is_read = true;
4434 references->safe_push (ref);
4437 else if (stmt_code == GIMPLE_CALL)
4439 unsigned i, n;
4441 ref.is_read = false;
4442 if (gimple_call_internal_p (stmt))
4443 switch (gimple_call_internal_fn (stmt))
4445 case IFN_MASK_LOAD:
4446 if (gimple_call_lhs (stmt) == NULL_TREE)
4447 break;
4448 ref.is_read = true;
4449 case IFN_MASK_STORE:
4450 ref.ref = fold_build2 (MEM_REF,
4451 ref.is_read
4452 ? TREE_TYPE (gimple_call_lhs (stmt))
4453 : TREE_TYPE (gimple_call_arg (stmt, 3)),
4454 gimple_call_arg (stmt, 0),
4455 gimple_call_arg (stmt, 1));
4456 references->safe_push (ref);
4457 return false;
4458 default:
4459 break;
4462 op0 = gimple_call_lhs (stmt);
4463 n = gimple_call_num_args (stmt);
4464 for (i = 0; i < n; i++)
4466 op1 = gimple_call_arg (stmt, i);
4468 if (DECL_P (op1)
4469 || (REFERENCE_CLASS_P (op1) && get_base_address (op1)))
4471 ref.ref = op1;
4472 ref.is_read = true;
4473 references->safe_push (ref);
4477 else
4478 return clobbers_memory;
4480 if (op0
4481 && (DECL_P (op0)
4482 || (REFERENCE_CLASS_P (op0) && get_base_address (op0))))
4484 ref.ref = op0;
4485 ref.is_read = false;
4486 references->safe_push (ref);
4488 return clobbers_memory;
4491 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4492 reference, returns false, otherwise returns true. NEST is the outermost
4493 loop of the loop nest in which the references should be analyzed. */
4495 bool
4496 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4497 vec<data_reference_p> *datarefs)
4499 unsigned i;
4500 auto_vec<data_ref_loc, 2> references;
4501 data_ref_loc *ref;
4502 bool ret = true;
4503 data_reference_p dr;
4505 if (get_references_in_stmt (stmt, &references))
4506 return false;
4508 FOR_EACH_VEC_ELT (references, i, ref)
4510 dr = create_data_ref (nest, loop_containing_stmt (stmt),
4511 ref->ref, stmt, ref->is_read);
4512 gcc_assert (dr != NULL);
4513 datarefs->safe_push (dr);
4515 references.release ();
4516 return ret;
4519 /* Stores the data references in STMT to DATAREFS. If there is an
4520 unanalyzable reference, returns false, otherwise returns true.
4521 NEST is the outermost loop of the loop nest in which the references
4522 should be instantiated, LOOP is the loop in which the references
4523 should be analyzed. */
4525 bool
4526 graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
4527 vec<data_reference_p> *datarefs)
4529 unsigned i;
4530 auto_vec<data_ref_loc, 2> references;
4531 data_ref_loc *ref;
4532 bool ret = true;
4533 data_reference_p dr;
4535 if (get_references_in_stmt (stmt, &references))
4536 return false;
4538 FOR_EACH_VEC_ELT (references, i, ref)
4540 dr = create_data_ref (nest, loop, ref->ref, stmt, ref->is_read);
4541 gcc_assert (dr != NULL);
4542 datarefs->safe_push (dr);
4545 references.release ();
4546 return ret;
4549 /* Search the data references in LOOP, and record the information into
4550 DATAREFS. Returns chrec_dont_know when failing to analyze a
4551 difficult case, returns NULL_TREE otherwise. */
4553 tree
4554 find_data_references_in_bb (struct loop *loop, basic_block bb,
4555 vec<data_reference_p> *datarefs)
4557 gimple_stmt_iterator bsi;
4559 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4561 gimple stmt = gsi_stmt (bsi);
4563 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4565 struct data_reference *res;
4566 res = XCNEW (struct data_reference);
4567 datarefs->safe_push (res);
4569 return chrec_dont_know;
4573 return NULL_TREE;
4576 /* Search the data references in LOOP, and record the information into
4577 DATAREFS. Returns chrec_dont_know when failing to analyze a
4578 difficult case, returns NULL_TREE otherwise.
4580 TODO: This function should be made smarter so that it can handle address
4581 arithmetic as if they were array accesses, etc. */
4583 tree
4584 find_data_references_in_loop (struct loop *loop,
4585 vec<data_reference_p> *datarefs)
4587 basic_block bb, *bbs;
4588 unsigned int i;
4590 bbs = get_loop_body_in_dom_order (loop);
4592 for (i = 0; i < loop->num_nodes; i++)
4594 bb = bbs[i];
4596 if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
4598 free (bbs);
4599 return chrec_dont_know;
4602 free (bbs);
4604 return NULL_TREE;
4607 /* Recursive helper function. */
4609 static bool
4610 find_loop_nest_1 (struct loop *loop, vec<loop_p> *loop_nest)
4612 /* Inner loops of the nest should not contain siblings. Example:
4613 when there are two consecutive loops,
4615 | loop_0
4616 | loop_1
4617 | A[{0, +, 1}_1]
4618 | endloop_1
4619 | loop_2
4620 | A[{0, +, 1}_2]
4621 | endloop_2
4622 | endloop_0
4624 the dependence relation cannot be captured by the distance
4625 abstraction. */
4626 if (loop->next)
4627 return false;
4629 loop_nest->safe_push (loop);
4630 if (loop->inner)
4631 return find_loop_nest_1 (loop->inner, loop_nest);
4632 return true;
4635 /* Return false when the LOOP is not well nested. Otherwise return
4636 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4637 contain the loops from the outermost to the innermost, as they will
4638 appear in the classic distance vector. */
4640 bool
4641 find_loop_nest (struct loop *loop, vec<loop_p> *loop_nest)
4643 loop_nest->safe_push (loop);
4644 if (loop->inner)
4645 return find_loop_nest_1 (loop->inner, loop_nest);
4646 return true;
4649 /* Returns true when the data dependences have been computed, false otherwise.
4650 Given a loop nest LOOP, the following vectors are returned:
4651 DATAREFS is initialized to all the array elements contained in this loop,
4652 DEPENDENCE_RELATIONS contains the relations between the data references.
4653 Compute read-read and self relations if
4654 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4656 bool
4657 compute_data_dependences_for_loop (struct loop *loop,
4658 bool compute_self_and_read_read_dependences,
4659 vec<loop_p> *loop_nest,
4660 vec<data_reference_p> *datarefs,
4661 vec<ddr_p> *dependence_relations)
4663 bool res = true;
4665 memset (&dependence_stats, 0, sizeof (dependence_stats));
4667 /* If the loop nest is not well formed, or one of the data references
4668 is not computable, give up without spending time to compute other
4669 dependences. */
4670 if (!loop
4671 || !find_loop_nest (loop, loop_nest)
4672 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
4673 || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
4674 compute_self_and_read_read_dependences))
4675 res = false;
4677 if (dump_file && (dump_flags & TDF_STATS))
4679 fprintf (dump_file, "Dependence tester statistics:\n");
4681 fprintf (dump_file, "Number of dependence tests: %d\n",
4682 dependence_stats.num_dependence_tests);
4683 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4684 dependence_stats.num_dependence_dependent);
4685 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4686 dependence_stats.num_dependence_independent);
4687 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4688 dependence_stats.num_dependence_undetermined);
4690 fprintf (dump_file, "Number of subscript tests: %d\n",
4691 dependence_stats.num_subscript_tests);
4692 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4693 dependence_stats.num_subscript_undetermined);
4694 fprintf (dump_file, "Number of same subscript function: %d\n",
4695 dependence_stats.num_same_subscript_function);
4697 fprintf (dump_file, "Number of ziv tests: %d\n",
4698 dependence_stats.num_ziv);
4699 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4700 dependence_stats.num_ziv_dependent);
4701 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4702 dependence_stats.num_ziv_independent);
4703 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4704 dependence_stats.num_ziv_unimplemented);
4706 fprintf (dump_file, "Number of siv tests: %d\n",
4707 dependence_stats.num_siv);
4708 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4709 dependence_stats.num_siv_dependent);
4710 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4711 dependence_stats.num_siv_independent);
4712 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4713 dependence_stats.num_siv_unimplemented);
4715 fprintf (dump_file, "Number of miv tests: %d\n",
4716 dependence_stats.num_miv);
4717 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4718 dependence_stats.num_miv_dependent);
4719 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4720 dependence_stats.num_miv_independent);
4721 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4722 dependence_stats.num_miv_unimplemented);
4725 return res;
4728 /* Returns true when the data dependences for the basic block BB have been
4729 computed, false otherwise.
4730 DATAREFS is initialized to all the array elements contained in this basic
4731 block, DEPENDENCE_RELATIONS contains the relations between the data
4732 references. Compute read-read and self relations if
4733 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4734 bool
4735 compute_data_dependences_for_bb (basic_block bb,
4736 bool compute_self_and_read_read_dependences,
4737 vec<data_reference_p> *datarefs,
4738 vec<ddr_p> *dependence_relations)
4740 if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
4741 return false;
4743 return compute_all_dependences (*datarefs, dependence_relations, vNULL,
4744 compute_self_and_read_read_dependences);
4747 /* Entry point (for testing only). Analyze all the data references
4748 and the dependence relations in LOOP.
4750 The data references are computed first.
4752 A relation on these nodes is represented by a complete graph. Some
4753 of the relations could be of no interest, thus the relations can be
4754 computed on demand.
4756 In the following function we compute all the relations. This is
4757 just a first implementation that is here for:
4758 - for showing how to ask for the dependence relations,
4759 - for the debugging the whole dependence graph,
4760 - for the dejagnu testcases and maintenance.
4762 It is possible to ask only for a part of the graph, avoiding to
4763 compute the whole dependence graph. The computed dependences are
4764 stored in a knowledge base (KB) such that later queries don't
4765 recompute the same information. The implementation of this KB is
4766 transparent to the optimizer, and thus the KB can be changed with a
4767 more efficient implementation, or the KB could be disabled. */
4768 static void
4769 analyze_all_data_dependences (struct loop *loop)
4771 unsigned int i;
4772 int nb_data_refs = 10;
4773 vec<data_reference_p> datarefs;
4774 datarefs.create (nb_data_refs);
4775 vec<ddr_p> dependence_relations;
4776 dependence_relations.create (nb_data_refs * nb_data_refs);
4777 vec<loop_p> loop_nest;
4778 loop_nest.create (3);
4780 /* Compute DDs on the whole function. */
4781 compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
4782 &dependence_relations);
4784 if (dump_file)
4786 dump_data_dependence_relations (dump_file, dependence_relations);
4787 fprintf (dump_file, "\n\n");
4789 if (dump_flags & TDF_DETAILS)
4790 dump_dist_dir_vectors (dump_file, dependence_relations);
4792 if (dump_flags & TDF_STATS)
4794 unsigned nb_top_relations = 0;
4795 unsigned nb_bot_relations = 0;
4796 unsigned nb_chrec_relations = 0;
4797 struct data_dependence_relation *ddr;
4799 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
4801 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4802 nb_top_relations++;
4804 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4805 nb_bot_relations++;
4807 else
4808 nb_chrec_relations++;
4811 gather_stats_on_scev_database ();
4815 loop_nest.release ();
4816 free_dependence_relations (dependence_relations);
4817 free_data_refs (datarefs);
4820 /* Computes all the data dependences and check that the results of
4821 several analyzers are the same. */
4823 void
4824 tree_check_data_deps (void)
4826 struct loop *loop_nest;
4828 FOR_EACH_LOOP (loop_nest, 0)
4829 analyze_all_data_dependences (loop_nest);
4832 /* Free the memory used by a data dependence relation DDR. */
4834 void
4835 free_dependence_relation (struct data_dependence_relation *ddr)
4837 if (ddr == NULL)
4838 return;
4840 if (DDR_SUBSCRIPTS (ddr).exists ())
4841 free_subscripts (DDR_SUBSCRIPTS (ddr));
4842 DDR_DIST_VECTS (ddr).release ();
4843 DDR_DIR_VECTS (ddr).release ();
4845 free (ddr);
4848 /* Free the memory used by the data dependence relations from
4849 DEPENDENCE_RELATIONS. */
4851 void
4852 free_dependence_relations (vec<ddr_p> dependence_relations)
4854 unsigned int i;
4855 struct data_dependence_relation *ddr;
4857 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
4858 if (ddr)
4859 free_dependence_relation (ddr);
4861 dependence_relations.release ();
4864 /* Free the memory used by the data references from DATAREFS. */
4866 void
4867 free_data_refs (vec<data_reference_p> datarefs)
4869 unsigned int i;
4870 struct data_reference *dr;
4872 FOR_EACH_VEC_ELT (datarefs, i, dr)
4873 free_data_ref (dr);
4874 datarefs.release ();