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