1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 /* This pass walks a given loop structure searching for array
23 references. The information about the array accesses is recorded
24 in DATA_REFERENCE structures.
25
26 The basic test for determining the dependences is:
27 given two access functions chrec1 and chrec2 to a same array, and
28 x and y two vectors from the iteration domain, the same element of
29 the array is accessed twice at iterations x and y if and only if:
30 | chrec1 (x) == chrec2 (y).
31
32 The goals of this analysis are:
33
34 - to determine the independence: the relation between two
35 independent accesses is qualified with the chrec_known (this
36 information allows a loop parallelization),
37
38 - when two data references access the same data, to qualify the
39 dependence relation with classic dependence representations:
40
41 - distance vectors
42 - direction vectors
43 - loop carried level dependence
44 - polyhedron dependence
45 or with the chains of recurrences based representation,
46
47 - to define a knowledge base for storing the data dependence
48 information,
49
50 - to define an interface to access this data.
51
52
53 Definitions:
54
55 - subscript: given two array accesses a subscript is the tuple
56 composed of the access functions for a given dimension. Example:
57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
58 (f1, g1), (f2, g2), (f3, g3).
59
60 - Diophantine equation: an equation whose coefficients and
61 solutions are integer constants, for example the equation
62 | 3*x + 2*y = 1
63 has an integer solution x = 1 and y = -1.
64
65 References:
66
67 - "Advanced Compilation for High Performance Computing" by Randy
68 Allen and Ken Kennedy.
69 http://citeseer.ist.psu.edu/goff91practical.html
70
71 - "Loop Transformations for Restructuring Compilers - The Foundations"
72 by Utpal Banerjee.
73
74
75 */
76
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "gimple-pretty-print.h"
81 #include "tree-flow.h"
82 #include "cfgloop.h"
83 #include "tree-data-ref.h"
84 #include "tree-scalar-evolution.h"
85 #include "tree-pass.h"
86 #include "langhooks.h"
87 #include "tree-affine.h"
88 #include "params.h"
89
90 static struct datadep_stats
91 {
92 int num_dependence_tests;
93 int num_dependence_dependent;
94 int num_dependence_independent;
95 int num_dependence_undetermined;
96
97 int num_subscript_tests;
98 int num_subscript_undetermined;
99 int num_same_subscript_function;
100
101 int num_ziv;
102 int num_ziv_independent;
103 int num_ziv_dependent;
104 int num_ziv_unimplemented;
105
106 int num_siv;
107 int num_siv_independent;
108 int num_siv_dependent;
109 int num_siv_unimplemented;
110
111 int num_miv;
112 int num_miv_independent;
113 int num_miv_dependent;
114 int num_miv_unimplemented;
115 } dependence_stats;
116
117 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
118 struct data_reference *,
119 struct data_reference *,
120 struct loop *);
121 /* Returns true iff A divides B. */
122
123 static inline bool
tree_fold_divides_p(const_tree a,const_tree b)124 tree_fold_divides_p (const_tree a, const_tree b)
125 {
126 gcc_assert (TREE_CODE (a) == INTEGER_CST);
127 gcc_assert (TREE_CODE (b) == INTEGER_CST);
128 return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a));
129 }
130
131 /* Returns true iff A divides B. */
132
133 static inline bool
int_divides_p(int a,int b)134 int_divides_p (int a, int b)
135 {
136 return ((b % a) == 0);
137 }
138
139
140
141 /* Dump into FILE all the data references from DATAREFS. */
142
143 void
dump_data_references(FILE * file,VEC (data_reference_p,heap)* datarefs)144 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
145 {
146 unsigned int i;
147 struct data_reference *dr;
148
149 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
150 dump_data_reference (file, dr);
151 }
152
153 /* Dump into STDERR all the data references from DATAREFS. */
154
155 DEBUG_FUNCTION void
debug_data_references(VEC (data_reference_p,heap)* datarefs)156 debug_data_references (VEC (data_reference_p, heap) *datarefs)
157 {
158 dump_data_references (stderr, datarefs);
159 }
160
161 /* Dump to STDERR all the dependence relations from DDRS. */
162
163 DEBUG_FUNCTION void
debug_data_dependence_relations(VEC (ddr_p,heap)* ddrs)164 debug_data_dependence_relations (VEC (ddr_p, heap) *ddrs)
165 {
166 dump_data_dependence_relations (stderr, ddrs);
167 }
168
169 /* Dump into FILE all the dependence relations from DDRS. */
170
171 void
dump_data_dependence_relations(FILE * file,VEC (ddr_p,heap)* ddrs)172 dump_data_dependence_relations (FILE *file,
173 VEC (ddr_p, heap) *ddrs)
174 {
175 unsigned int i;
176 struct data_dependence_relation *ddr;
177
178 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
179 dump_data_dependence_relation (file, ddr);
180 }
181
182 /* Print to STDERR the data_reference DR. */
183
184 DEBUG_FUNCTION void
debug_data_reference(struct data_reference * dr)185 debug_data_reference (struct data_reference *dr)
186 {
187 dump_data_reference (stderr, dr);
188 }
189
190 /* Dump function for a DATA_REFERENCE structure. */
191
192 void
dump_data_reference(FILE * outf,struct data_reference * dr)193 dump_data_reference (FILE *outf,
194 struct data_reference *dr)
195 {
196 unsigned int i;
197
198 fprintf (outf, "#(Data Ref: \n");
199 fprintf (outf, "# bb: %d \n", gimple_bb (DR_STMT (dr))->index);
200 fprintf (outf, "# stmt: ");
201 print_gimple_stmt (outf, DR_STMT (dr), 0, 0);
202 fprintf (outf, "# ref: ");
203 print_generic_stmt (outf, DR_REF (dr), 0);
204 fprintf (outf, "# base_object: ");
205 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
206
207 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
208 {
209 fprintf (outf, "# Access function %d: ", i);
210 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
211 }
212 fprintf (outf, "#)\n");
213 }
214
215 /* Dumps the affine function described by FN to the file OUTF. */
216
217 static void
dump_affine_function(FILE * outf,affine_fn fn)218 dump_affine_function (FILE *outf, affine_fn fn)
219 {
220 unsigned i;
221 tree coef;
222
223 print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
224 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
225 {
226 fprintf (outf, " + ");
227 print_generic_expr (outf, coef, TDF_SLIM);
228 fprintf (outf, " * x_%u", i);
229 }
230 }
231
232 /* Dumps the conflict function CF to the file OUTF. */
233
234 static void
dump_conflict_function(FILE * outf,conflict_function * cf)235 dump_conflict_function (FILE *outf, conflict_function *cf)
236 {
237 unsigned i;
238
239 if (cf->n == NO_DEPENDENCE)
240 fprintf (outf, "no dependence\n");
241 else if (cf->n == NOT_KNOWN)
242 fprintf (outf, "not known\n");
243 else
244 {
245 for (i = 0; i < cf->n; i++)
246 {
247 fprintf (outf, "[");
248 dump_affine_function (outf, cf->fns[i]);
249 fprintf (outf, "]\n");
250 }
251 }
252 }
253
254 /* Dump function for a SUBSCRIPT structure. */
255
256 void
dump_subscript(FILE * outf,struct subscript * subscript)257 dump_subscript (FILE *outf, struct subscript *subscript)
258 {
259 conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
260
261 fprintf (outf, "\n (subscript \n");
262 fprintf (outf, " iterations_that_access_an_element_twice_in_A: ");
263 dump_conflict_function (outf, cf);
264 if (CF_NONTRIVIAL_P (cf))
265 {
266 tree last_iteration = SUB_LAST_CONFLICT (subscript);
267 fprintf (outf, " last_conflict: ");
268 print_generic_stmt (outf, last_iteration, 0);
269 }
270
271 cf = SUB_CONFLICTS_IN_B (subscript);
272 fprintf (outf, " iterations_that_access_an_element_twice_in_B: ");
273 dump_conflict_function (outf, cf);
274 if (CF_NONTRIVIAL_P (cf))
275 {
276 tree last_iteration = SUB_LAST_CONFLICT (subscript);
277 fprintf (outf, " last_conflict: ");
278 print_generic_stmt (outf, last_iteration, 0);
279 }
280
281 fprintf (outf, " (Subscript distance: ");
282 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
283 fprintf (outf, " )\n");
284 fprintf (outf, " )\n");
285 }
286
287 /* Print the classic direction vector DIRV to OUTF. */
288
289 void
print_direction_vector(FILE * outf,lambda_vector dirv,int length)290 print_direction_vector (FILE *outf,
291 lambda_vector dirv,
292 int length)
293 {
294 int eq;
295
296 for (eq = 0; eq < length; eq++)
297 {
298 enum data_dependence_direction dir = ((enum data_dependence_direction)
299 dirv[eq]);
300
301 switch (dir)
302 {
303 case dir_positive:
304 fprintf (outf, " +");
305 break;
306 case dir_negative:
307 fprintf (outf, " -");
308 break;
309 case dir_equal:
310 fprintf (outf, " =");
311 break;
312 case dir_positive_or_equal:
313 fprintf (outf, " +=");
314 break;
315 case dir_positive_or_negative:
316 fprintf (outf, " +-");
317 break;
318 case dir_negative_or_equal:
319 fprintf (outf, " -=");
320 break;
321 case dir_star:
322 fprintf (outf, " *");
323 break;
324 default:
325 fprintf (outf, "indep");
326 break;
327 }
328 }
329 fprintf (outf, "\n");
330 }
331
332 /* Print a vector of direction vectors. */
333
334 void
print_dir_vectors(FILE * outf,VEC (lambda_vector,heap)* dir_vects,int length)335 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
336 int length)
337 {
338 unsigned j;
339 lambda_vector v;
340
341 FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, v)
342 print_direction_vector (outf, v, length);
343 }
344
345 /* Print out a vector VEC of length N to OUTFILE. */
346
347 static inline void
print_lambda_vector(FILE * outfile,lambda_vector vector,int n)348 print_lambda_vector (FILE * outfile, lambda_vector vector, int n)
349 {
350 int i;
351
352 for (i = 0; i < n; i++)
353 fprintf (outfile, "%3d ", vector[i]);
354 fprintf (outfile, "\n");
355 }
356
357 /* Print a vector of distance vectors. */
358
359 void
print_dist_vectors(FILE * outf,VEC (lambda_vector,heap)* dist_vects,int length)360 print_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
361 int length)
362 {
363 unsigned j;
364 lambda_vector v;
365
366 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, v)
367 print_lambda_vector (outf, v, length);
368 }
369
370 /* Debug version. */
371
372 DEBUG_FUNCTION void
debug_data_dependence_relation(struct data_dependence_relation * ddr)373 debug_data_dependence_relation (struct data_dependence_relation *ddr)
374 {
375 dump_data_dependence_relation (stderr, ddr);
376 }
377
378 /* Dump function for a DATA_DEPENDENCE_RELATION structure. */
379
380 void
dump_data_dependence_relation(FILE * outf,struct data_dependence_relation * ddr)381 dump_data_dependence_relation (FILE *outf,
382 struct data_dependence_relation *ddr)
383 {
384 struct data_reference *dra, *drb;
385
386 fprintf (outf, "(Data Dep: \n");
387
388 if (!ddr || DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
389 {
390 if (ddr)
391 {
392 dra = DDR_A (ddr);
393 drb = DDR_B (ddr);
394 if (dra)
395 dump_data_reference (outf, dra);
396 else
397 fprintf (outf, " (nil)\n");
398 if (drb)
399 dump_data_reference (outf, drb);
400 else
401 fprintf (outf, " (nil)\n");
402 }
403 fprintf (outf, " (don't know)\n)\n");
404 return;
405 }
406
407 dra = DDR_A (ddr);
408 drb = DDR_B (ddr);
409 dump_data_reference (outf, dra);
410 dump_data_reference (outf, drb);
411
412 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
413 fprintf (outf, " (no dependence)\n");
414
415 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
416 {
417 unsigned int i;
418 struct loop *loopi;
419
420 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
421 {
422 fprintf (outf, " access_fn_A: ");
423 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
424 fprintf (outf, " access_fn_B: ");
425 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
426 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
427 }
428
429 fprintf (outf, " inner loop index: %d\n", DDR_INNER_LOOP (ddr));
430 fprintf (outf, " loop nest: (");
431 FOR_EACH_VEC_ELT (loop_p, DDR_LOOP_NEST (ddr), i, loopi)
432 fprintf (outf, "%d ", loopi->num);
433 fprintf (outf, ")\n");
434
435 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
436 {
437 fprintf (outf, " distance_vector: ");
438 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
439 DDR_NB_LOOPS (ddr));
440 }
441
442 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
443 {
444 fprintf (outf, " direction_vector: ");
445 print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
446 DDR_NB_LOOPS (ddr));
447 }
448 }
449
450 fprintf (outf, ")\n");
451 }
452
453 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */
454
455 void
dump_data_dependence_direction(FILE * file,enum data_dependence_direction dir)456 dump_data_dependence_direction (FILE *file,
457 enum data_dependence_direction dir)
458 {
459 switch (dir)
460 {
461 case dir_positive:
462 fprintf (file, "+");
463 break;
464
465 case dir_negative:
466 fprintf (file, "-");
467 break;
468
469 case dir_equal:
470 fprintf (file, "=");
471 break;
472
473 case dir_positive_or_negative:
474 fprintf (file, "+-");
475 break;
476
477 case dir_positive_or_equal:
478 fprintf (file, "+=");
479 break;
480
481 case dir_negative_or_equal:
482 fprintf (file, "-=");
483 break;
484
485 case dir_star:
486 fprintf (file, "*");
487 break;
488
489 default:
490 break;
491 }
492 }
493
494 /* Dumps the distance and direction vectors in FILE. DDRS contains
495 the dependence relations, and VECT_SIZE is the size of the
496 dependence vectors, or in other words the number of loops in the
497 considered nest. */
498
499 void
dump_dist_dir_vectors(FILE * file,VEC (ddr_p,heap)* ddrs)500 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
501 {
502 unsigned int i, j;
503 struct data_dependence_relation *ddr;
504 lambda_vector v;
505
506 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
507 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
508 {
509 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), j, v)
510 {
511 fprintf (file, "DISTANCE_V (");
512 print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
513 fprintf (file, ")\n");
514 }
515
516 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), j, v)
517 {
518 fprintf (file, "DIRECTION_V (");
519 print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
520 fprintf (file, ")\n");
521 }
522 }
523
524 fprintf (file, "\n\n");
525 }
526
527 /* Dumps the data dependence relations DDRS in FILE. */
528
529 void
dump_ddrs(FILE * file,VEC (ddr_p,heap)* ddrs)530 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
531 {
532 unsigned int i;
533 struct data_dependence_relation *ddr;
534
535 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
536 dump_data_dependence_relation (file, ddr);
537
538 fprintf (file, "\n\n");
539 }
540
541 /* Helper function for split_constant_offset. Expresses OP0 CODE OP1
542 (the type of the result is TYPE) as VAR + OFF, where OFF is a nonzero
543 constant of type ssizetype, and returns true. If we cannot do this
544 with OFF nonzero, OFF and VAR are set to NULL_TREE instead and false
545 is returned. */
546
547 static bool
split_constant_offset_1(tree type,tree op0,enum tree_code code,tree op1,tree * var,tree * off)548 split_constant_offset_1 (tree type, tree op0, enum tree_code code, tree op1,
549 tree *var, tree *off)
550 {
551 tree var0, var1;
552 tree off0, off1;
553 enum tree_code ocode = code;
554
555 *var = NULL_TREE;
556 *off = NULL_TREE;
557
558 switch (code)
559 {
560 case INTEGER_CST:
561 *var = build_int_cst (type, 0);
562 *off = fold_convert (ssizetype, op0);
563 return true;
564
565 case POINTER_PLUS_EXPR:
566 ocode = PLUS_EXPR;
567 /* FALLTHROUGH */
568 case PLUS_EXPR:
569 case MINUS_EXPR:
570 split_constant_offset (op0, &var0, &off0);
571 split_constant_offset (op1, &var1, &off1);
572 *var = fold_build2 (code, type, var0, var1);
573 *off = size_binop (ocode, off0, off1);
574 return true;
575
576 case MULT_EXPR:
577 if (TREE_CODE (op1) != INTEGER_CST)
578 return false;
579
580 split_constant_offset (op0, &var0, &off0);
581 *var = fold_build2 (MULT_EXPR, type, var0, op1);
582 *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, op1));
583 return true;
584
585 case ADDR_EXPR:
586 {
587 tree base, poffset;
588 HOST_WIDE_INT pbitsize, pbitpos;
589 enum machine_mode pmode;
590 int punsignedp, pvolatilep;
591
592 op0 = TREE_OPERAND (op0, 0);
593 base = get_inner_reference (op0, &pbitsize, &pbitpos, &poffset,
594 &pmode, &punsignedp, &pvolatilep, false);
595
596 if (pbitpos % BITS_PER_UNIT != 0)
597 return false;
598 base = build_fold_addr_expr (base);
599 off0 = ssize_int (pbitpos / BITS_PER_UNIT);
600
601 if (poffset)
602 {
603 split_constant_offset (poffset, &poffset, &off1);
604 off0 = size_binop (PLUS_EXPR, off0, off1);
605 if (POINTER_TYPE_P (TREE_TYPE (base)))
606 base = fold_build_pointer_plus (base, poffset);
607 else
608 base = fold_build2 (PLUS_EXPR, TREE_TYPE (base), base,
609 fold_convert (TREE_TYPE (base), poffset));
610 }
611
612 var0 = fold_convert (type, base);
613
614 /* If variable length types are involved, punt, otherwise casts
615 might be converted into ARRAY_REFs in gimplify_conversion.
616 To compute that ARRAY_REF's element size TYPE_SIZE_UNIT, which
617 possibly no longer appears in current GIMPLE, might resurface.
618 This perhaps could run
619 if (CONVERT_EXPR_P (var0))
620 {
621 gimplify_conversion (&var0);
622 // Attempt to fill in any within var0 found ARRAY_REF's
623 // element size from corresponding op embedded ARRAY_REF,
624 // if unsuccessful, just punt.
625 } */
626 while (POINTER_TYPE_P (type))
627 type = TREE_TYPE (type);
628 if (int_size_in_bytes (type) < 0)
629 return false;
630
631 *var = var0;
632 *off = off0;
633 return true;
634 }
635
636 case SSA_NAME:
637 {
638 gimple def_stmt = SSA_NAME_DEF_STMT (op0);
639 enum tree_code subcode;
640
641 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
642 return false;
643
644 var0 = gimple_assign_rhs1 (def_stmt);
645 subcode = gimple_assign_rhs_code (def_stmt);
646 var1 = gimple_assign_rhs2 (def_stmt);
647
648 return split_constant_offset_1 (type, var0, subcode, var1, var, off);
649 }
650 CASE_CONVERT:
651 {
652 /* We must not introduce undefined overflow, and we must not change the value.
653 Hence we're okay if the inner type doesn't overflow to start with
654 (pointer or signed), the outer type also is an integer or pointer
655 and the outer precision is at least as large as the inner. */
656 tree itype = TREE_TYPE (op0);
657 if ((POINTER_TYPE_P (itype)
658 || (INTEGRAL_TYPE_P (itype) && TYPE_OVERFLOW_UNDEFINED (itype)))
659 && TYPE_PRECISION (type) >= TYPE_PRECISION (itype)
660 && (POINTER_TYPE_P (type) || INTEGRAL_TYPE_P (type)))
661 {
662 split_constant_offset (op0, &var0, off);
663 *var = fold_convert (type, var0);
664 return true;
665 }
666 return false;
667 }
668
669 default:
670 return false;
671 }
672 }
673
674 /* Expresses EXP as VAR + OFF, where off is a constant. The type of OFF
675 will be ssizetype. */
676
677 void
split_constant_offset(tree exp,tree * var,tree * off)678 split_constant_offset (tree exp, tree *var, tree *off)
679 {
680 tree type = TREE_TYPE (exp), otype, op0, op1, e, o;
681 enum tree_code code;
682
683 *var = exp;
684 *off = ssize_int (0);
685 STRIP_NOPS (exp);
686
687 if (tree_is_chrec (exp)
688 || get_gimple_rhs_class (TREE_CODE (exp)) == GIMPLE_TERNARY_RHS)
689 return;
690
691 otype = TREE_TYPE (exp);
692 code = TREE_CODE (exp);
693 extract_ops_from_tree (exp, &code, &op0, &op1);
694 if (split_constant_offset_1 (otype, op0, code, op1, &e, &o))
695 {
696 *var = fold_convert (type, e);
697 *off = o;
698 }
699 }
700
701 /* Returns the address ADDR of an object in a canonical shape (without nop
702 casts, and with type of pointer to the object). */
703
704 static tree
canonicalize_base_object_address(tree addr)705 canonicalize_base_object_address (tree addr)
706 {
707 tree orig = addr;
708
709 STRIP_NOPS (addr);
710
711 /* The base address may be obtained by casting from integer, in that case
712 keep the cast. */
713 if (!POINTER_TYPE_P (TREE_TYPE (addr)))
714 return orig;
715
716 if (TREE_CODE (addr) != ADDR_EXPR)
717 return addr;
718
719 return build_fold_addr_expr (TREE_OPERAND (addr, 0));
720 }
721
722 /* Analyzes the behavior of the memory reference DR in the innermost loop or
723 basic block that contains it. Returns true if analysis succeed or false
724 otherwise. */
725
726 bool
dr_analyze_innermost(struct data_reference * dr,struct loop * nest)727 dr_analyze_innermost (struct data_reference *dr, struct loop *nest)
728 {
729 gimple stmt = DR_STMT (dr);
730 struct loop *loop = loop_containing_stmt (stmt);
731 tree ref = DR_REF (dr);
732 HOST_WIDE_INT pbitsize, pbitpos;
733 tree base, poffset;
734 enum machine_mode pmode;
735 int punsignedp, pvolatilep;
736 affine_iv base_iv, offset_iv;
737 tree init, dinit, step;
738 bool in_loop = (loop && loop->num);
739
740 if (dump_file && (dump_flags & TDF_DETAILS))
741 fprintf (dump_file, "analyze_innermost: ");
742
743 base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
744 &pmode, &punsignedp, &pvolatilep, false);
745 gcc_assert (base != NULL_TREE);
746
747 if (pbitpos % BITS_PER_UNIT != 0)
748 {
749 if (dump_file && (dump_flags & TDF_DETAILS))
750 fprintf (dump_file, "failed: bit offset alignment.\n");
751 return false;
752 }
753
754 if (TREE_CODE (base) == MEM_REF)
755 {
756 if (!integer_zerop (TREE_OPERAND (base, 1)))
757 {
758 if (!poffset)
759 {
760 double_int moff = mem_ref_offset (base);
761 poffset = double_int_to_tree (sizetype, moff);
762 }
763 else
764 poffset = size_binop (PLUS_EXPR, poffset, TREE_OPERAND (base, 1));
765 }
766 base = TREE_OPERAND (base, 0);
767 }
768 else
769 base = build_fold_addr_expr (base);
770
771 if (in_loop)
772 {
773 if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv,
774 false))
775 {
776 if (nest)
777 {
778 if (dump_file && (dump_flags & TDF_DETAILS))
779 fprintf (dump_file, "failed: evolution of base is not"
780 " affine.\n");
781 return false;
782 }
783 else
784 {
785 base_iv.base = base;
786 base_iv.step = ssize_int (0);
787 base_iv.no_overflow = true;
788 }
789 }
790 }
791 else
792 {
793 base_iv.base = base;
794 base_iv.step = ssize_int (0);
795 base_iv.no_overflow = true;
796 }
797
798 if (!poffset)
799 {
800 offset_iv.base = ssize_int (0);
801 offset_iv.step = ssize_int (0);
802 }
803 else
804 {
805 if (!in_loop)
806 {
807 offset_iv.base = poffset;
808 offset_iv.step = ssize_int (0);
809 }
810 else if (!simple_iv (loop, loop_containing_stmt (stmt),
811 poffset, &offset_iv, false))
812 {
813 if (nest)
814 {
815 if (dump_file && (dump_flags & TDF_DETAILS))
816 fprintf (dump_file, "failed: evolution of offset is not"
817 " affine.\n");
818 return false;
819 }
820 else
821 {
822 offset_iv.base = poffset;
823 offset_iv.step = ssize_int (0);
824 }
825 }
826 }
827
828 init = ssize_int (pbitpos / BITS_PER_UNIT);
829 split_constant_offset (base_iv.base, &base_iv.base, &dinit);
830 init = size_binop (PLUS_EXPR, init, dinit);
831 split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
832 init = size_binop (PLUS_EXPR, init, dinit);
833
834 step = size_binop (PLUS_EXPR,
835 fold_convert (ssizetype, base_iv.step),
836 fold_convert (ssizetype, offset_iv.step));
837
838 DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
839
840 DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
841 DR_INIT (dr) = init;
842 DR_STEP (dr) = step;
843
844 DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
845
846 if (dump_file && (dump_flags & TDF_DETAILS))
847 fprintf (dump_file, "success.\n");
848
849 return true;
850 }
851
852 /* Determines the base object and the list of indices of memory reference
853 DR, analyzed in LOOP and instantiated in loop nest NEST. */
854
855 static void
dr_analyze_indices(struct data_reference * dr,loop_p nest,loop_p loop)856 dr_analyze_indices (struct data_reference *dr, loop_p nest, loop_p loop)
857 {
858 VEC (tree, heap) *access_fns = NULL;
859 tree ref, op;
860 tree base, off, access_fn;
861 basic_block before_loop;
862
863 /* If analyzing a basic-block there are no indices to analyze
864 and thus no access functions. */
865 if (!nest)
866 {
867 DR_BASE_OBJECT (dr) = DR_REF (dr);
868 DR_ACCESS_FNS (dr) = NULL;
869 return;
870 }
871
872 ref = DR_REF (dr);
873 before_loop = block_before_loop (nest);
874
875 /* REALPART_EXPR and IMAGPART_EXPR can be handled like accesses
876 into a two element array with a constant index. The base is
877 then just the immediate underlying object. */
878 if (TREE_CODE (ref) == REALPART_EXPR)
879 {
880 ref = TREE_OPERAND (ref, 0);
881 VEC_safe_push (tree, heap, access_fns, integer_zero_node);
882 }
883 else if (TREE_CODE (ref) == IMAGPART_EXPR)
884 {
885 ref = TREE_OPERAND (ref, 0);
886 VEC_safe_push (tree, heap, access_fns, integer_one_node);
887 }
888
889 /* Analyze access functions of dimensions we know to be independent. */
890 while (handled_component_p (ref))
891 {
892 if (TREE_CODE (ref) == ARRAY_REF)
893 {
894 op = TREE_OPERAND (ref, 1);
895 access_fn = analyze_scalar_evolution (loop, op);
896 access_fn = instantiate_scev (before_loop, loop, access_fn);
897 VEC_safe_push (tree, heap, access_fns, access_fn);
898 }
899 else if (TREE_CODE (ref) == COMPONENT_REF
900 && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0))) == RECORD_TYPE)
901 {
902 /* For COMPONENT_REFs of records (but not unions!) use the
903 FIELD_DECL offset as constant access function so we can
904 disambiguate a[i].f1 and a[i].f2. */
905 tree off = component_ref_field_offset (ref);
906 off = size_binop (PLUS_EXPR,
907 size_binop (MULT_EXPR,
908 fold_convert (bitsizetype, off),
909 bitsize_int (BITS_PER_UNIT)),
910 DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)));
911 VEC_safe_push (tree, heap, access_fns, off);
912 }
913 else
914 /* If we have an unhandled component we could not translate
915 to an access function stop analyzing. We have determined
916 our base object in this case. */
917 break;
918
919 ref = TREE_OPERAND (ref, 0);
920 }
921
922 /* If the address operand of a MEM_REF base has an evolution in the
923 analyzed nest, add it as an additional independent access-function. */
924 if (TREE_CODE (ref) == MEM_REF)
925 {
926 op = TREE_OPERAND (ref, 0);
927 access_fn = analyze_scalar_evolution (loop, op);
928 access_fn = instantiate_scev (before_loop, loop, access_fn);
929 if (TREE_CODE (access_fn) == POLYNOMIAL_CHREC)
930 {
931 tree orig_type;
932 tree memoff = TREE_OPERAND (ref, 1);
933 base = initial_condition (access_fn);
934 orig_type = TREE_TYPE (base);
935 STRIP_USELESS_TYPE_CONVERSION (base);
936 split_constant_offset (base, &base, &off);
937 /* Fold the MEM_REF offset into the evolutions initial
938 value to make more bases comparable. */
939 if (!integer_zerop (memoff))
940 {
941 off = size_binop (PLUS_EXPR, off,
942 fold_convert (ssizetype, memoff));
943 memoff = build_int_cst (TREE_TYPE (memoff), 0);
944 }
945 access_fn = chrec_replace_initial_condition
946 (access_fn, fold_convert (orig_type, off));
947 /* ??? This is still not a suitable base object for
948 dr_may_alias_p - the base object needs to be an
949 access that covers the object as whole. With
950 an evolution in the pointer this cannot be
951 guaranteed.
952 As a band-aid, mark the access so we can special-case
953 it in dr_may_alias_p. */
954 ref = fold_build2_loc (EXPR_LOCATION (ref),
955 MEM_REF, TREE_TYPE (ref),
956 base, memoff);
957 DR_UNCONSTRAINED_BASE (dr) = true;
958 VEC_safe_push (tree, heap, access_fns, access_fn);
959 }
960 }
961 else if (DECL_P (ref))
962 {
963 /* Canonicalize DR_BASE_OBJECT to MEM_REF form. */
964 ref = build2 (MEM_REF, TREE_TYPE (ref),
965 build_fold_addr_expr (ref),
966 build_int_cst (reference_alias_ptr_type (ref), 0));
967 }
968
969 DR_BASE_OBJECT (dr) = ref;
970 DR_ACCESS_FNS (dr) = access_fns;
971 }
972
973 /* Extracts the alias analysis information from the memory reference DR. */
974
975 static void
dr_analyze_alias(struct data_reference * dr)976 dr_analyze_alias (struct data_reference *dr)
977 {
978 tree ref = DR_REF (dr);
979 tree base = get_base_address (ref), addr;
980
981 if (INDIRECT_REF_P (base)
982 || TREE_CODE (base) == MEM_REF)
983 {
984 addr = TREE_OPERAND (base, 0);
985 if (TREE_CODE (addr) == SSA_NAME)
986 DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
987 }
988 }
989
990 /* Frees data reference DR. */
991
992 void
free_data_ref(data_reference_p dr)993 free_data_ref (data_reference_p dr)
994 {
995 VEC_free (tree, heap, DR_ACCESS_FNS (dr));
996 free (dr);
997 }
998
999 /* Analyzes memory reference MEMREF accessed in STMT. The reference
1000 is read if IS_READ is true, write otherwise. Returns the
1001 data_reference description of MEMREF. NEST is the outermost loop
1002 in which the reference should be instantiated, LOOP is the loop in
1003 which the data reference should be analyzed. */
1004
1005 struct data_reference *
create_data_ref(loop_p nest,loop_p loop,tree memref,gimple stmt,bool is_read)1006 create_data_ref (loop_p nest, loop_p loop, tree memref, gimple stmt,
1007 bool is_read)
1008 {
1009 struct data_reference *dr;
1010
1011 if (dump_file && (dump_flags & TDF_DETAILS))
1012 {
1013 fprintf (dump_file, "Creating dr for ");
1014 print_generic_expr (dump_file, memref, TDF_SLIM);
1015 fprintf (dump_file, "\n");
1016 }
1017
1018 dr = XCNEW (struct data_reference);
1019 DR_STMT (dr) = stmt;
1020 DR_REF (dr) = memref;
1021 DR_IS_READ (dr) = is_read;
1022
1023 dr_analyze_innermost (dr, nest);
1024 dr_analyze_indices (dr, nest, loop);
1025 dr_analyze_alias (dr);
1026
1027 if (dump_file && (dump_flags & TDF_DETAILS))
1028 {
1029 unsigned i;
1030 fprintf (dump_file, "\tbase_address: ");
1031 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1032 fprintf (dump_file, "\n\toffset from base address: ");
1033 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1034 fprintf (dump_file, "\n\tconstant offset from base address: ");
1035 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1036 fprintf (dump_file, "\n\tstep: ");
1037 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1038 fprintf (dump_file, "\n\taligned to: ");
1039 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1040 fprintf (dump_file, "\n\tbase_object: ");
1041 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1042 fprintf (dump_file, "\n");
1043 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
1044 {
1045 fprintf (dump_file, "\tAccess function %d: ", i);
1046 print_generic_stmt (dump_file, DR_ACCESS_FN (dr, i), TDF_SLIM);
1047 }
1048 }
1049
1050 return dr;
1051 }
1052
1053 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
1054 expressions. */
1055 static bool
dr_equal_offsets_p1(tree offset1,tree offset2)1056 dr_equal_offsets_p1 (tree offset1, tree offset2)
1057 {
1058 bool res;
1059
1060 STRIP_NOPS (offset1);
1061 STRIP_NOPS (offset2);
1062
1063 if (offset1 == offset2)
1064 return true;
1065
1066 if (TREE_CODE (offset1) != TREE_CODE (offset2)
1067 || (!BINARY_CLASS_P (offset1) && !UNARY_CLASS_P (offset1)))
1068 return false;
1069
1070 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 0),
1071 TREE_OPERAND (offset2, 0));
1072
1073 if (!res || !BINARY_CLASS_P (offset1))
1074 return res;
1075
1076 res = dr_equal_offsets_p1 (TREE_OPERAND (offset1, 1),
1077 TREE_OPERAND (offset2, 1));
1078
1079 return res;
1080 }
1081
1082 /* Check if DRA and DRB have equal offsets. */
1083 bool
dr_equal_offsets_p(struct data_reference * dra,struct data_reference * drb)1084 dr_equal_offsets_p (struct data_reference *dra,
1085 struct data_reference *drb)
1086 {
1087 tree offset1, offset2;
1088
1089 offset1 = DR_OFFSET (dra);
1090 offset2 = DR_OFFSET (drb);
1091
1092 return dr_equal_offsets_p1 (offset1, offset2);
1093 }
1094
1095 /* Returns true if FNA == FNB. */
1096
1097 static bool
affine_function_equal_p(affine_fn fna,affine_fn fnb)1098 affine_function_equal_p (affine_fn fna, affine_fn fnb)
1099 {
1100 unsigned i, n = VEC_length (tree, fna);
1101
1102 if (n != VEC_length (tree, fnb))
1103 return false;
1104
1105 for (i = 0; i < n; i++)
1106 if (!operand_equal_p (VEC_index (tree, fna, i),
1107 VEC_index (tree, fnb, i), 0))
1108 return false;
1109
1110 return true;
1111 }
1112
1113 /* If all the functions in CF are the same, returns one of them,
1114 otherwise returns NULL. */
1115
1116 static affine_fn
common_affine_function(conflict_function * cf)1117 common_affine_function (conflict_function *cf)
1118 {
1119 unsigned i;
1120 affine_fn comm;
1121
1122 if (!CF_NONTRIVIAL_P (cf))
1123 return NULL;
1124
1125 comm = cf->fns[0];
1126
1127 for (i = 1; i < cf->n; i++)
1128 if (!affine_function_equal_p (comm, cf->fns[i]))
1129 return NULL;
1130
1131 return comm;
1132 }
1133
1134 /* Returns the base of the affine function FN. */
1135
1136 static tree
affine_function_base(affine_fn fn)1137 affine_function_base (affine_fn fn)
1138 {
1139 return VEC_index (tree, fn, 0);
1140 }
1141
1142 /* Returns true if FN is a constant. */
1143
1144 static bool
affine_function_constant_p(affine_fn fn)1145 affine_function_constant_p (affine_fn fn)
1146 {
1147 unsigned i;
1148 tree coef;
1149
1150 for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
1151 if (!integer_zerop (coef))
1152 return false;
1153
1154 return true;
1155 }
1156
1157 /* Returns true if FN is the zero constant function. */
1158
1159 static bool
affine_function_zero_p(affine_fn fn)1160 affine_function_zero_p (affine_fn fn)
1161 {
1162 return (integer_zerop (affine_function_base (fn))
1163 && affine_function_constant_p (fn));
1164 }
1165
1166 /* Returns a signed integer type with the largest precision from TA
1167 and TB. */
1168
1169 static tree
signed_type_for_types(tree ta,tree tb)1170 signed_type_for_types (tree ta, tree tb)
1171 {
1172 if (TYPE_PRECISION (ta) > TYPE_PRECISION (tb))
1173 return signed_type_for (ta);
1174 else
1175 return signed_type_for (tb);
1176 }
1177
1178 /* Applies operation OP on affine functions FNA and FNB, and returns the
1179 result. */
1180
1181 static affine_fn
affine_fn_op(enum tree_code op,affine_fn fna,affine_fn fnb)1182 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
1183 {
1184 unsigned i, n, m;
1185 affine_fn ret;
1186 tree coef;
1187
1188 if (VEC_length (tree, fnb) > VEC_length (tree, fna))
1189 {
1190 n = VEC_length (tree, fna);
1191 m = VEC_length (tree, fnb);
1192 }
1193 else
1194 {
1195 n = VEC_length (tree, fnb);
1196 m = VEC_length (tree, fna);
1197 }
1198
1199 ret = VEC_alloc (tree, heap, m);
1200 for (i = 0; i < n; i++)
1201 {
1202 tree type = signed_type_for_types (TREE_TYPE (VEC_index (tree, fna, i)),
1203 TREE_TYPE (VEC_index (tree, fnb, i)));
1204
1205 VEC_quick_push (tree, ret,
1206 fold_build2 (op, type,
1207 VEC_index (tree, fna, i),
1208 VEC_index (tree, fnb, i)));
1209 }
1210
1211 for (; VEC_iterate (tree, fna, i, coef); i++)
1212 VEC_quick_push (tree, ret,
1213 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1214 coef, integer_zero_node));
1215 for (; VEC_iterate (tree, fnb, i, coef); i++)
1216 VEC_quick_push (tree, ret,
1217 fold_build2 (op, signed_type_for (TREE_TYPE (coef)),
1218 integer_zero_node, coef));
1219
1220 return ret;
1221 }
1222
1223 /* Returns the sum of affine functions FNA and FNB. */
1224
1225 static affine_fn
affine_fn_plus(affine_fn fna,affine_fn fnb)1226 affine_fn_plus (affine_fn fna, affine_fn fnb)
1227 {
1228 return affine_fn_op (PLUS_EXPR, fna, fnb);
1229 }
1230
1231 /* Returns the difference of affine functions FNA and FNB. */
1232
1233 static affine_fn
affine_fn_minus(affine_fn fna,affine_fn fnb)1234 affine_fn_minus (affine_fn fna, affine_fn fnb)
1235 {
1236 return affine_fn_op (MINUS_EXPR, fna, fnb);
1237 }
1238
1239 /* Frees affine function FN. */
1240
1241 static void
affine_fn_free(affine_fn fn)1242 affine_fn_free (affine_fn fn)
1243 {
1244 VEC_free (tree, heap, fn);
1245 }
1246
1247 /* Determine for each subscript in the data dependence relation DDR
1248 the distance. */
1249
1250 static void
compute_subscript_distance(struct data_dependence_relation * ddr)1251 compute_subscript_distance (struct data_dependence_relation *ddr)
1252 {
1253 conflict_function *cf_a, *cf_b;
1254 affine_fn fn_a, fn_b, diff;
1255
1256 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1257 {
1258 unsigned int i;
1259
1260 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1261 {
1262 struct subscript *subscript;
1263
1264 subscript = DDR_SUBSCRIPT (ddr, i);
1265 cf_a = SUB_CONFLICTS_IN_A (subscript);
1266 cf_b = SUB_CONFLICTS_IN_B (subscript);
1267
1268 fn_a = common_affine_function (cf_a);
1269 fn_b = common_affine_function (cf_b);
1270 if (!fn_a || !fn_b)
1271 {
1272 SUB_DISTANCE (subscript) = chrec_dont_know;
1273 return;
1274 }
1275 diff = affine_fn_minus (fn_a, fn_b);
1276
1277 if (affine_function_constant_p (diff))
1278 SUB_DISTANCE (subscript) = affine_function_base (diff);
1279 else
1280 SUB_DISTANCE (subscript) = chrec_dont_know;
1281
1282 affine_fn_free (diff);
1283 }
1284 }
1285 }
1286
1287 /* Returns the conflict function for "unknown". */
1288
1289 static conflict_function *
conflict_fn_not_known(void)1290 conflict_fn_not_known (void)
1291 {
1292 conflict_function *fn = XCNEW (conflict_function);
1293 fn->n = NOT_KNOWN;
1294
1295 return fn;
1296 }
1297
1298 /* Returns the conflict function for "independent". */
1299
1300 static conflict_function *
conflict_fn_no_dependence(void)1301 conflict_fn_no_dependence (void)
1302 {
1303 conflict_function *fn = XCNEW (conflict_function);
1304 fn->n = NO_DEPENDENCE;
1305
1306 return fn;
1307 }
1308
1309 /* Returns true if the address of OBJ is invariant in LOOP. */
1310
1311 static bool
object_address_invariant_in_loop_p(const struct loop * loop,const_tree obj)1312 object_address_invariant_in_loop_p (const struct loop *loop, const_tree obj)
1313 {
1314 while (handled_component_p (obj))
1315 {
1316 if (TREE_CODE (obj) == ARRAY_REF)
1317 {
1318 /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1319 need to check the stride and the lower bound of the reference. */
1320 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1321 loop->num)
1322 || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1323 loop->num))
1324 return false;
1325 }
1326 else if (TREE_CODE (obj) == COMPONENT_REF)
1327 {
1328 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1329 loop->num))
1330 return false;
1331 }
1332 obj = TREE_OPERAND (obj, 0);
1333 }
1334
1335 if (!INDIRECT_REF_P (obj)
1336 && TREE_CODE (obj) != MEM_REF)
1337 return true;
1338
1339 return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1340 loop->num);
1341 }
1342
1343 /* Returns false if we can prove that data references A and B do not alias,
1344 true otherwise. If LOOP_NEST is false no cross-iteration aliases are
1345 considered. */
1346
1347 bool
dr_may_alias_p(const struct data_reference * a,const struct data_reference * b,bool loop_nest)1348 dr_may_alias_p (const struct data_reference *a, const struct data_reference *b,
1349 bool loop_nest)
1350 {
1351 tree addr_a = DR_BASE_OBJECT (a);
1352 tree addr_b = DR_BASE_OBJECT (b);
1353
1354 /* If we are not processing a loop nest but scalar code we
1355 do not need to care about possible cross-iteration dependences
1356 and thus can process the full original reference. Do so,
1357 similar to how loop invariant motion applies extra offset-based
1358 disambiguation. */
1359 if (!loop_nest)
1360 {
1361 aff_tree off1, off2;
1362 double_int size1, size2;
1363 get_inner_reference_aff (DR_REF (a), &off1, &size1);
1364 get_inner_reference_aff (DR_REF (b), &off2, &size2);
1365 aff_combination_scale (&off1, double_int_minus_one);
1366 aff_combination_add (&off2, &off1);
1367 if (aff_comb_cannot_overlap_p (&off2, size1, size2))
1368 return false;
1369 }
1370
1371 /* If we had an evolution in a MEM_REF BASE_OBJECT we do not know
1372 the size of the base-object. So we cannot do any offset/overlap
1373 based analysis but have to rely on points-to information only. */
1374 if (TREE_CODE (addr_a) == MEM_REF
1375 && DR_UNCONSTRAINED_BASE (a))
1376 {
1377 if (TREE_CODE (addr_b) == MEM_REF
1378 && DR_UNCONSTRAINED_BASE (b))
1379 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1380 TREE_OPERAND (addr_b, 0));
1381 else
1382 return ptr_derefs_may_alias_p (TREE_OPERAND (addr_a, 0),
1383 build_fold_addr_expr (addr_b));
1384 }
1385 else if (TREE_CODE (addr_b) == MEM_REF
1386 && DR_UNCONSTRAINED_BASE (b))
1387 return ptr_derefs_may_alias_p (build_fold_addr_expr (addr_a),
1388 TREE_OPERAND (addr_b, 0));
1389
1390 /* Otherwise DR_BASE_OBJECT is an access that covers the whole object
1391 that is being subsetted in the loop nest. */
1392 if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
1393 return refs_output_dependent_p (addr_a, addr_b);
1394 else if (DR_IS_READ (a) && DR_IS_WRITE (b))
1395 return refs_anti_dependent_p (addr_a, addr_b);
1396 return refs_may_alias_p (addr_a, addr_b);
1397 }
1398
1399 /* Initialize a data dependence relation between data accesses A and
1400 B. NB_LOOPS is the number of loops surrounding the references: the
1401 size of the classic distance/direction vectors. */
1402
1403 struct data_dependence_relation *
initialize_data_dependence_relation(struct data_reference * a,struct data_reference * b,VEC (loop_p,heap)* loop_nest)1404 initialize_data_dependence_relation (struct data_reference *a,
1405 struct data_reference *b,
1406 VEC (loop_p, heap) *loop_nest)
1407 {
1408 struct data_dependence_relation *res;
1409 unsigned int i;
1410
1411 res = XNEW (struct data_dependence_relation);
1412 DDR_A (res) = a;
1413 DDR_B (res) = b;
1414 DDR_LOOP_NEST (res) = NULL;
1415 DDR_REVERSED_P (res) = false;
1416 DDR_SUBSCRIPTS (res) = NULL;
1417 DDR_DIR_VECTS (res) = NULL;
1418 DDR_DIST_VECTS (res) = NULL;
1419
1420 if (a == NULL || b == NULL)
1421 {
1422 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1423 return res;
1424 }
1425
1426 /* If the data references do not alias, then they are independent. */
1427 if (!dr_may_alias_p (a, b, loop_nest != NULL))
1428 {
1429 DDR_ARE_DEPENDENT (res) = chrec_known;
1430 return res;
1431 }
1432
1433 /* The case where the references are exactly the same. */
1434 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
1435 {
1436 if (loop_nest
1437 && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1438 DR_BASE_OBJECT (a)))
1439 {
1440 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1441 return res;
1442 }
1443 DDR_AFFINE_P (res) = true;
1444 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1445 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1446 DDR_LOOP_NEST (res) = loop_nest;
1447 DDR_INNER_LOOP (res) = 0;
1448 DDR_SELF_REFERENCE (res) = true;
1449 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1450 {
1451 struct subscript *subscript;
1452
1453 subscript = XNEW (struct subscript);
1454 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1455 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1456 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1457 SUB_DISTANCE (subscript) = chrec_dont_know;
1458 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1459 }
1460 return res;
1461 }
1462
1463 /* If the references do not access the same object, we do not know
1464 whether they alias or not. */
1465 if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1466 {
1467 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1468 return res;
1469 }
1470
1471 /* If the base of the object is not invariant in the loop nest, we cannot
1472 analyze it. TODO -- in fact, it would suffice to record that there may
1473 be arbitrary dependences in the loops where the base object varies. */
1474 if (loop_nest
1475 && !object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1476 DR_BASE_OBJECT (a)))
1477 {
1478 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1479 return res;
1480 }
1481
1482 /* If the number of dimensions of the access to not agree we can have
1483 a pointer access to a component of the array element type and an
1484 array access while the base-objects are still the same. Punt. */
1485 if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
1486 {
1487 DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1488 return res;
1489 }
1490
1491 DDR_AFFINE_P (res) = true;
1492 DDR_ARE_DEPENDENT (res) = NULL_TREE;
1493 DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1494 DDR_LOOP_NEST (res) = loop_nest;
1495 DDR_INNER_LOOP (res) = 0;
1496 DDR_SELF_REFERENCE (res) = false;
1497
1498 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1499 {
1500 struct subscript *subscript;
1501
1502 subscript = XNEW (struct subscript);
1503 SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1504 SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1505 SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1506 SUB_DISTANCE (subscript) = chrec_dont_know;
1507 VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1508 }
1509
1510 return res;
1511 }
1512
1513 /* Frees memory used by the conflict function F. */
1514
1515 static void
free_conflict_function(conflict_function * f)1516 free_conflict_function (conflict_function *f)
1517 {
1518 unsigned i;
1519
1520 if (CF_NONTRIVIAL_P (f))
1521 {
1522 for (i = 0; i < f->n; i++)
1523 affine_fn_free (f->fns[i]);
1524 }
1525 free (f);
1526 }
1527
1528 /* Frees memory used by SUBSCRIPTS. */
1529
1530 static void
free_subscripts(VEC (subscript_p,heap)* subscripts)1531 free_subscripts (VEC (subscript_p, heap) *subscripts)
1532 {
1533 unsigned i;
1534 subscript_p s;
1535
1536 FOR_EACH_VEC_ELT (subscript_p, subscripts, i, s)
1537 {
1538 free_conflict_function (s->conflicting_iterations_in_a);
1539 free_conflict_function (s->conflicting_iterations_in_b);
1540 free (s);
1541 }
1542 VEC_free (subscript_p, heap, subscripts);
1543 }
1544
1545 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1546 description. */
1547
1548 static inline void
finalize_ddr_dependent(struct data_dependence_relation * ddr,tree chrec)1549 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1550 tree chrec)
1551 {
1552 if (dump_file && (dump_flags & TDF_DETAILS))
1553 {
1554 fprintf (dump_file, "(dependence classified: ");
1555 print_generic_expr (dump_file, chrec, 0);
1556 fprintf (dump_file, ")\n");
1557 }
1558
1559 DDR_ARE_DEPENDENT (ddr) = chrec;
1560 free_subscripts (DDR_SUBSCRIPTS (ddr));
1561 DDR_SUBSCRIPTS (ddr) = NULL;
1562 }
1563
1564 /* The dependence relation DDR cannot be represented by a distance
1565 vector. */
1566
1567 static inline void
non_affine_dependence_relation(struct data_dependence_relation * ddr)1568 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1569 {
1570 if (dump_file && (dump_flags & TDF_DETAILS))
1571 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1572
1573 DDR_AFFINE_P (ddr) = false;
1574 }
1575
1576
1577
1578 /* This section contains the classic Banerjee tests. */
1579
1580 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1581 variables, i.e., if the ZIV (Zero Index Variable) test is true. */
1582
1583 static inline bool
ziv_subscript_p(const_tree chrec_a,const_tree chrec_b)1584 ziv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1585 {
1586 return (evolution_function_is_constant_p (chrec_a)
1587 && evolution_function_is_constant_p (chrec_b));
1588 }
1589
1590 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1591 variable, i.e., if the SIV (Single Index Variable) test is true. */
1592
1593 static bool
siv_subscript_p(const_tree chrec_a,const_tree chrec_b)1594 siv_subscript_p (const_tree chrec_a, const_tree chrec_b)
1595 {
1596 if ((evolution_function_is_constant_p (chrec_a)
1597 && evolution_function_is_univariate_p (chrec_b))
1598 || (evolution_function_is_constant_p (chrec_b)
1599 && evolution_function_is_univariate_p (chrec_a)))
1600 return true;
1601
1602 if (evolution_function_is_univariate_p (chrec_a)
1603 && evolution_function_is_univariate_p (chrec_b))
1604 {
1605 switch (TREE_CODE (chrec_a))
1606 {
1607 case POLYNOMIAL_CHREC:
1608 switch (TREE_CODE (chrec_b))
1609 {
1610 case POLYNOMIAL_CHREC:
1611 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1612 return false;
1613
1614 default:
1615 return true;
1616 }
1617
1618 default:
1619 return true;
1620 }
1621 }
1622
1623 return false;
1624 }
1625
1626 /* Creates a conflict function with N dimensions. The affine functions
1627 in each dimension follow. */
1628
1629 static conflict_function *
conflict_fn(unsigned n,...)1630 conflict_fn (unsigned n, ...)
1631 {
1632 unsigned i;
1633 conflict_function *ret = XCNEW (conflict_function);
1634 va_list ap;
1635
1636 gcc_assert (0 < n && n <= MAX_DIM);
1637 va_start(ap, n);
1638
1639 ret->n = n;
1640 for (i = 0; i < n; i++)
1641 ret->fns[i] = va_arg (ap, affine_fn);
1642 va_end(ap);
1643
1644 return ret;
1645 }
1646
1647 /* Returns constant affine function with value CST. */
1648
1649 static affine_fn
affine_fn_cst(tree cst)1650 affine_fn_cst (tree cst)
1651 {
1652 affine_fn fn = VEC_alloc (tree, heap, 1);
1653 VEC_quick_push (tree, fn, cst);
1654 return fn;
1655 }
1656
1657 /* Returns affine function with single variable, CST + COEF * x_DIM. */
1658
1659 static affine_fn
affine_fn_univar(tree cst,unsigned dim,tree coef)1660 affine_fn_univar (tree cst, unsigned dim, tree coef)
1661 {
1662 affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1663 unsigned i;
1664
1665 gcc_assert (dim > 0);
1666 VEC_quick_push (tree, fn, cst);
1667 for (i = 1; i < dim; i++)
1668 VEC_quick_push (tree, fn, integer_zero_node);
1669 VEC_quick_push (tree, fn, coef);
1670 return fn;
1671 }
1672
1673 /* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and
1674 *OVERLAPS_B are initialized to the functions that describe the
1675 relation between the elements accessed twice by CHREC_A and
1676 CHREC_B. For k >= 0, the following property is verified:
1677
1678 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1679
1680 static void
analyze_ziv_subscript(tree chrec_a,tree chrec_b,conflict_function ** overlaps_a,conflict_function ** overlaps_b,tree * last_conflicts)1681 analyze_ziv_subscript (tree chrec_a,
1682 tree chrec_b,
1683 conflict_function **overlaps_a,
1684 conflict_function **overlaps_b,
1685 tree *last_conflicts)
1686 {
1687 tree type, difference;
1688 dependence_stats.num_ziv++;
1689
1690 if (dump_file && (dump_flags & TDF_DETAILS))
1691 fprintf (dump_file, "(analyze_ziv_subscript \n");
1692
1693 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1694 chrec_a = chrec_convert (type, chrec_a, NULL);
1695 chrec_b = chrec_convert (type, chrec_b, NULL);
1696 difference = chrec_fold_minus (type, chrec_a, chrec_b);
1697
1698 switch (TREE_CODE (difference))
1699 {
1700 case INTEGER_CST:
1701 if (integer_zerop (difference))
1702 {
1703 /* The difference is equal to zero: the accessed index
1704 overlaps for each iteration in the loop. */
1705 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1706 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1707 *last_conflicts = chrec_dont_know;
1708 dependence_stats.num_ziv_dependent++;
1709 }
1710 else
1711 {
1712 /* The accesses do not overlap. */
1713 *overlaps_a = conflict_fn_no_dependence ();
1714 *overlaps_b = conflict_fn_no_dependence ();
1715 *last_conflicts = integer_zero_node;
1716 dependence_stats.num_ziv_independent++;
1717 }
1718 break;
1719
1720 default:
1721 /* We're not sure whether the indexes overlap. For the moment,
1722 conservatively answer "don't know". */
1723 if (dump_file && (dump_flags & TDF_DETAILS))
1724 fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1725
1726 *overlaps_a = conflict_fn_not_known ();
1727 *overlaps_b = conflict_fn_not_known ();
1728 *last_conflicts = chrec_dont_know;
1729 dependence_stats.num_ziv_unimplemented++;
1730 break;
1731 }
1732
1733 if (dump_file && (dump_flags & TDF_DETAILS))
1734 fprintf (dump_file, ")\n");
1735 }
1736
1737 /* Similar to max_stmt_executions_int, but returns the bound as a tree,
1738 and only if it fits to the int type. If this is not the case, or the
1739 bound on the number of iterations of LOOP could not be derived, returns
1740 chrec_dont_know. */
1741
1742 static tree
max_stmt_executions_tree(struct loop * loop)1743 max_stmt_executions_tree (struct loop *loop)
1744 {
1745 double_int nit;
1746
1747 if (!max_stmt_executions (loop, true, &nit))
1748 return chrec_dont_know;
1749
1750 if (!double_int_fits_to_tree_p (unsigned_type_node, nit))
1751 return chrec_dont_know;
1752
1753 return double_int_to_tree (unsigned_type_node, nit);
1754 }
1755
1756 /* Determine whether the CHREC is always positive/negative. If the expression
1757 cannot be statically analyzed, return false, otherwise set the answer into
1758 VALUE. */
1759
1760 static bool
chrec_is_positive(tree chrec,bool * value)1761 chrec_is_positive (tree chrec, bool *value)
1762 {
1763 bool value0, value1, value2;
1764 tree end_value, nb_iter;
1765
1766 switch (TREE_CODE (chrec))
1767 {
1768 case POLYNOMIAL_CHREC:
1769 if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
1770 || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
1771 return false;
1772
1773 /* FIXME -- overflows. */
1774 if (value0 == value1)
1775 {
1776 *value = value0;
1777 return true;
1778 }
1779
1780 /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
1781 and the proof consists in showing that the sign never
1782 changes during the execution of the loop, from 0 to
1783 loop->nb_iterations. */
1784 if (!evolution_function_is_affine_p (chrec))
1785 return false;
1786
1787 nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
1788 if (chrec_contains_undetermined (nb_iter))
1789 return false;
1790
1791 #if 0
1792 /* TODO -- If the test is after the exit, we may decrease the number of
1793 iterations by one. */
1794 if (after_exit)
1795 nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
1796 #endif
1797
1798 end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
1799
1800 if (!chrec_is_positive (end_value, &value2))
1801 return false;
1802
1803 *value = value0;
1804 return value0 == value1;
1805
1806 case INTEGER_CST:
1807 switch (tree_int_cst_sgn (chrec))
1808 {
1809 case -1:
1810 *value = false;
1811 break;
1812 case 1:
1813 *value = true;
1814 break;
1815 default:
1816 return false;
1817 }
1818 return true;
1819
1820 default:
1821 return false;
1822 }
1823 }
1824
1825
1826 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1827 constant, and CHREC_B is an affine function. *OVERLAPS_A and
1828 *OVERLAPS_B are initialized to the functions that describe the
1829 relation between the elements accessed twice by CHREC_A and
1830 CHREC_B. For k >= 0, the following property is verified:
1831
1832 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
1833
1834 static void
analyze_siv_subscript_cst_affine(tree chrec_a,tree chrec_b,conflict_function ** overlaps_a,conflict_function ** overlaps_b,tree * last_conflicts)1835 analyze_siv_subscript_cst_affine (tree chrec_a,
1836 tree chrec_b,
1837 conflict_function **overlaps_a,
1838 conflict_function **overlaps_b,
1839 tree *last_conflicts)
1840 {
1841 bool value0, value1, value2;
1842 tree type, difference, tmp;
1843
1844 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
1845 chrec_a = chrec_convert (type, chrec_a, NULL);
1846 chrec_b = chrec_convert (type, chrec_b, NULL);
1847 difference = chrec_fold_minus (type, initial_condition (chrec_b), chrec_a);
1848
1849 /* Special case overlap in the first iteration. */
1850 if (integer_zerop (difference))
1851 {
1852 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1853 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1854 *last_conflicts = integer_one_node;
1855 return;
1856 }
1857
1858 if (!chrec_is_positive (initial_condition (difference), &value0))
1859 {
1860 if (dump_file && (dump_flags & TDF_DETAILS))
1861 fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1862
1863 dependence_stats.num_siv_unimplemented++;
1864 *overlaps_a = conflict_fn_not_known ();
1865 *overlaps_b = conflict_fn_not_known ();
1866 *last_conflicts = chrec_dont_know;
1867 return;
1868 }
1869 else
1870 {
1871 if (value0 == false)
1872 {
1873 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1874 {
1875 if (dump_file && (dump_flags & TDF_DETAILS))
1876 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1877
1878 *overlaps_a = conflict_fn_not_known ();
1879 *overlaps_b = conflict_fn_not_known ();
1880 *last_conflicts = chrec_dont_know;
1881 dependence_stats.num_siv_unimplemented++;
1882 return;
1883 }
1884 else
1885 {
1886 if (value1 == true)
1887 {
1888 /* Example:
1889 chrec_a = 12
1890 chrec_b = {10, +, 1}
1891 */
1892
1893 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1894 {
1895 HOST_WIDE_INT numiter;
1896 struct loop *loop = get_chrec_loop (chrec_b);
1897
1898 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1899 tmp = fold_build2 (EXACT_DIV_EXPR, type,
1900 fold_build1 (ABS_EXPR, type, difference),
1901 CHREC_RIGHT (chrec_b));
1902 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1903 *last_conflicts = integer_one_node;
1904
1905
1906 /* Perform weak-zero siv test to see if overlap is
1907 outside the loop bounds. */
1908 numiter = max_stmt_executions_int (loop, true);
1909
1910 if (numiter >= 0
1911 && compare_tree_int (tmp, numiter) > 0)
1912 {
1913 free_conflict_function (*overlaps_a);
1914 free_conflict_function (*overlaps_b);
1915 *overlaps_a = conflict_fn_no_dependence ();
1916 *overlaps_b = conflict_fn_no_dependence ();
1917 *last_conflicts = integer_zero_node;
1918 dependence_stats.num_siv_independent++;
1919 return;
1920 }
1921 dependence_stats.num_siv_dependent++;
1922 return;
1923 }
1924
1925 /* When the step does not divide the difference, there are
1926 no overlaps. */
1927 else
1928 {
1929 *overlaps_a = conflict_fn_no_dependence ();
1930 *overlaps_b = conflict_fn_no_dependence ();
1931 *last_conflicts = integer_zero_node;
1932 dependence_stats.num_siv_independent++;
1933 return;
1934 }
1935 }
1936
1937 else
1938 {
1939 /* Example:
1940 chrec_a = 12
1941 chrec_b = {10, +, -1}
1942
1943 In this case, chrec_a will not overlap with chrec_b. */
1944 *overlaps_a = conflict_fn_no_dependence ();
1945 *overlaps_b = conflict_fn_no_dependence ();
1946 *last_conflicts = integer_zero_node;
1947 dependence_stats.num_siv_independent++;
1948 return;
1949 }
1950 }
1951 }
1952 else
1953 {
1954 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1955 {
1956 if (dump_file && (dump_flags & TDF_DETAILS))
1957 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1958
1959 *overlaps_a = conflict_fn_not_known ();
1960 *overlaps_b = conflict_fn_not_known ();
1961 *last_conflicts = chrec_dont_know;
1962 dependence_stats.num_siv_unimplemented++;
1963 return;
1964 }
1965 else
1966 {
1967 if (value2 == false)
1968 {
1969 /* Example:
1970 chrec_a = 3
1971 chrec_b = {10, +, -1}
1972 */
1973 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1974 {
1975 HOST_WIDE_INT numiter;
1976 struct loop *loop = get_chrec_loop (chrec_b);
1977
1978 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1979 tmp = fold_build2 (EXACT_DIV_EXPR, type, difference,
1980 CHREC_RIGHT (chrec_b));
1981 *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1982 *last_conflicts = integer_one_node;
1983
1984 /* Perform weak-zero siv test to see if overlap is
1985 outside the loop bounds. */
1986 numiter = max_stmt_executions_int (loop, true);
1987
1988 if (numiter >= 0
1989 && compare_tree_int (tmp, numiter) > 0)
1990 {
1991 free_conflict_function (*overlaps_a);
1992 free_conflict_function (*overlaps_b);
1993 *overlaps_a = conflict_fn_no_dependence ();
1994 *overlaps_b = conflict_fn_no_dependence ();
1995 *last_conflicts = integer_zero_node;
1996 dependence_stats.num_siv_independent++;
1997 return;
1998 }
1999 dependence_stats.num_siv_dependent++;
2000 return;
2001 }
2002
2003 /* When the step does not divide the difference, there
2004 are no overlaps. */
2005 else
2006 {
2007 *overlaps_a = conflict_fn_no_dependence ();
2008 *overlaps_b = conflict_fn_no_dependence ();
2009 *last_conflicts = integer_zero_node;
2010 dependence_stats.num_siv_independent++;
2011 return;
2012 }
2013 }
2014 else
2015 {
2016 /* Example:
2017 chrec_a = 3
2018 chrec_b = {4, +, 1}
2019
2020 In this case, chrec_a will not overlap with chrec_b. */
2021 *overlaps_a = conflict_fn_no_dependence ();
2022 *overlaps_b = conflict_fn_no_dependence ();
2023 *last_conflicts = integer_zero_node;
2024 dependence_stats.num_siv_independent++;
2025 return;
2026 }
2027 }
2028 }
2029 }
2030 }
2031
2032 /* Helper recursive function for initializing the matrix A. Returns
2033 the initial value of CHREC. */
2034
2035 static tree
initialize_matrix_A(lambda_matrix A,tree chrec,unsigned index,int mult)2036 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2037 {
2038 gcc_assert (chrec);
2039
2040 switch (TREE_CODE (chrec))
2041 {
2042 case POLYNOMIAL_CHREC:
2043 gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST);
2044
2045 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2046 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2047
2048 case PLUS_EXPR:
2049 case MULT_EXPR:
2050 case MINUS_EXPR:
2051 {
2052 tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2053 tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult);
2054
2055 return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1);
2056 }
2057
2058 case NOP_EXPR:
2059 {
2060 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2061 return chrec_convert (chrec_type (chrec), op, NULL);
2062 }
2063
2064 case BIT_NOT_EXPR:
2065 {
2066 /* Handle ~X as -1 - X. */
2067 tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult);
2068 return chrec_fold_op (MINUS_EXPR, chrec_type (chrec),
2069 build_int_cst (TREE_TYPE (chrec), -1), op);
2070 }
2071
2072 case INTEGER_CST:
2073 return chrec;
2074
2075 default:
2076 gcc_unreachable ();
2077 return NULL_TREE;
2078 }
2079 }
2080
2081 #define FLOOR_DIV(x,y) ((x) / (y))
2082
2083 /* Solves the special case of the Diophantine equation:
2084 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2085
2086 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the
2087 number of iterations that loops X and Y run. The overlaps will be
2088 constructed as evolutions in dimension DIM. */
2089
2090 static void
compute_overlap_steps_for_affine_univar(int niter,int step_a,int step_b,affine_fn * overlaps_a,affine_fn * overlaps_b,tree * last_conflicts,int dim)2091 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2092 affine_fn *overlaps_a,
2093 affine_fn *overlaps_b,
2094 tree *last_conflicts, int dim)
2095 {
2096 if (((step_a > 0 && step_b > 0)
2097 || (step_a < 0 && step_b < 0)))
2098 {
2099 int step_overlaps_a, step_overlaps_b;
2100 int gcd_steps_a_b, last_conflict, tau2;
2101
2102 gcd_steps_a_b = gcd (step_a, step_b);
2103 step_overlaps_a = step_b / gcd_steps_a_b;
2104 step_overlaps_b = step_a / gcd_steps_a_b;
2105
2106 if (niter > 0)
2107 {
2108 tau2 = FLOOR_DIV (niter, step_overlaps_a);
2109 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2110 last_conflict = tau2;
2111 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2112 }
2113 else
2114 *last_conflicts = chrec_dont_know;
2115
2116 *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2117 build_int_cst (NULL_TREE,
2118 step_overlaps_a));
2119 *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2120 build_int_cst (NULL_TREE,
2121 step_overlaps_b));
2122 }
2123
2124 else
2125 {
2126 *overlaps_a = affine_fn_cst (integer_zero_node);
2127 *overlaps_b = affine_fn_cst (integer_zero_node);
2128 *last_conflicts = integer_zero_node;
2129 }
2130 }
2131
2132 /* Solves the special case of a Diophantine equation where CHREC_A is
2133 an affine bivariate function, and CHREC_B is an affine univariate
2134 function. For example,
2135
2136 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2137
2138 has the following overlapping functions:
2139
2140 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2141 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2142 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2143
2144 FORNOW: This is a specialized implementation for a case occurring in
2145 a common benchmark. Implement the general algorithm. */
2146
2147 static void
compute_overlap_steps_for_affine_1_2(tree chrec_a,tree chrec_b,conflict_function ** overlaps_a,conflict_function ** overlaps_b,tree * last_conflicts)2148 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2149 conflict_function **overlaps_a,
2150 conflict_function **overlaps_b,
2151 tree *last_conflicts)
2152 {
2153 bool xz_p, yz_p, xyz_p;
2154 int step_x, step_y, step_z;
2155 HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2156 affine_fn overlaps_a_xz, overlaps_b_xz;
2157 affine_fn overlaps_a_yz, overlaps_b_yz;
2158 affine_fn overlaps_a_xyz, overlaps_b_xyz;
2159 affine_fn ova1, ova2, ovb;
2160 tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2161
2162 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2163 step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2164 step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2165
2166 niter_x =
2167 max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
2168 niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
2169 niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
2170
2171 if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2172 {
2173 if (dump_file && (dump_flags & TDF_DETAILS))
2174 fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2175
2176 *overlaps_a = conflict_fn_not_known ();
2177 *overlaps_b = conflict_fn_not_known ();
2178 *last_conflicts = chrec_dont_know;
2179 return;
2180 }
2181
2182 niter = MIN (niter_x, niter_z);
2183 compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2184 &overlaps_a_xz,
2185 &overlaps_b_xz,
2186 &last_conflicts_xz, 1);
2187 niter = MIN (niter_y, niter_z);
2188 compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2189 &overlaps_a_yz,
2190 &overlaps_b_yz,
2191 &last_conflicts_yz, 2);
2192 niter = MIN (niter_x, niter_z);
2193 niter = MIN (niter_y, niter);
2194 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2195 &overlaps_a_xyz,
2196 &overlaps_b_xyz,
2197 &last_conflicts_xyz, 3);
2198
2199 xz_p = !integer_zerop (last_conflicts_xz);
2200 yz_p = !integer_zerop (last_conflicts_yz);
2201 xyz_p = !integer_zerop (last_conflicts_xyz);
2202
2203 if (xz_p || yz_p || xyz_p)
2204 {
2205 ova1 = affine_fn_cst (integer_zero_node);
2206 ova2 = affine_fn_cst (integer_zero_node);
2207 ovb = affine_fn_cst (integer_zero_node);
2208 if (xz_p)
2209 {
2210 affine_fn t0 = ova1;
2211 affine_fn t2 = ovb;
2212
2213 ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2214 ovb = affine_fn_plus (ovb, overlaps_b_xz);
2215 affine_fn_free (t0);
2216 affine_fn_free (t2);
2217 *last_conflicts = last_conflicts_xz;
2218 }
2219 if (yz_p)
2220 {
2221 affine_fn t0 = ova2;
2222 affine_fn t2 = ovb;
2223
2224 ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2225 ovb = affine_fn_plus (ovb, overlaps_b_yz);
2226 affine_fn_free (t0);
2227 affine_fn_free (t2);
2228 *last_conflicts = last_conflicts_yz;
2229 }
2230 if (xyz_p)
2231 {
2232 affine_fn t0 = ova1;
2233 affine_fn t2 = ova2;
2234 affine_fn t4 = ovb;
2235
2236 ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2237 ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2238 ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2239 affine_fn_free (t0);
2240 affine_fn_free (t2);
2241 affine_fn_free (t4);
2242 *last_conflicts = last_conflicts_xyz;
2243 }
2244 *overlaps_a = conflict_fn (2, ova1, ova2);
2245 *overlaps_b = conflict_fn (1, ovb);
2246 }
2247 else
2248 {
2249 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2250 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2251 *last_conflicts = integer_zero_node;
2252 }
2253
2254 affine_fn_free (overlaps_a_xz);
2255 affine_fn_free (overlaps_b_xz);
2256 affine_fn_free (overlaps_a_yz);
2257 affine_fn_free (overlaps_b_yz);
2258 affine_fn_free (overlaps_a_xyz);
2259 affine_fn_free (overlaps_b_xyz);
2260 }
2261
2262 /* Copy the elements of vector VEC1 with length SIZE to VEC2. */
2263
2264 static void
lambda_vector_copy(lambda_vector vec1,lambda_vector vec2,int size)2265 lambda_vector_copy (lambda_vector vec1, lambda_vector vec2,
2266 int size)
2267 {
2268 memcpy (vec2, vec1, size * sizeof (*vec1));
2269 }
2270
2271 /* Copy the elements of M x N matrix MAT1 to MAT2. */
2272
2273 static void
lambda_matrix_copy(lambda_matrix mat1,lambda_matrix mat2,int m,int n)2274 lambda_matrix_copy (lambda_matrix mat1, lambda_matrix mat2,
2275 int m, int n)
2276 {
2277 int i;
2278
2279 for (i = 0; i < m; i++)
2280 lambda_vector_copy (mat1[i], mat2[i], n);
2281 }
2282
2283 /* Store the N x N identity matrix in MAT. */
2284
2285 static void
lambda_matrix_id(lambda_matrix mat,int size)2286 lambda_matrix_id (lambda_matrix mat, int size)
2287 {
2288 int i, j;
2289
2290 for (i = 0; i < size; i++)
2291 for (j = 0; j < size; j++)
2292 mat[i][j] = (i == j) ? 1 : 0;
2293 }
2294
2295 /* Return the first nonzero element of vector VEC1 between START and N.
2296 We must have START <= N. Returns N if VEC1 is the zero vector. */
2297
2298 static int
lambda_vector_first_nz(lambda_vector vec1,int n,int start)2299 lambda_vector_first_nz (lambda_vector vec1, int n, int start)
2300 {
2301 int j = start;
2302 while (j < n && vec1[j] == 0)
2303 j++;
2304 return j;
2305 }
2306
2307 /* Add a multiple of row R1 of matrix MAT with N columns to row R2:
2308 R2 = R2 + CONST1 * R1. */
2309
2310 static void
lambda_matrix_row_add(lambda_matrix mat,int n,int r1,int r2,int const1)2311 lambda_matrix_row_add (lambda_matrix mat, int n, int r1, int r2, int const1)
2312 {
2313 int i;
2314
2315 if (const1 == 0)
2316 return;
2317
2318 for (i = 0; i < n; i++)
2319 mat[r2][i] += const1 * mat[r1][i];
2320 }
2321
2322 /* Swap rows R1 and R2 in matrix MAT. */
2323
2324 static void
lambda_matrix_row_exchange(lambda_matrix mat,int r1,int r2)2325 lambda_matrix_row_exchange (lambda_matrix mat, int r1, int r2)
2326 {
2327 lambda_vector row;
2328
2329 row = mat[r1];
2330 mat[r1] = mat[r2];
2331 mat[r2] = row;
2332 }
2333
2334 /* Multiply vector VEC1 of length SIZE by a constant CONST1,
2335 and store the result in VEC2. */
2336
2337 static void
lambda_vector_mult_const(lambda_vector vec1,lambda_vector vec2,int size,int const1)2338 lambda_vector_mult_const (lambda_vector vec1, lambda_vector vec2,
2339 int size, int const1)
2340 {
2341 int i;
2342
2343 if (const1 == 0)
2344 lambda_vector_clear (vec2, size);
2345 else
2346 for (i = 0; i < size; i++)
2347 vec2[i] = const1 * vec1[i];
2348 }
2349
2350 /* Negate vector VEC1 with length SIZE and store it in VEC2. */
2351
2352 static void
lambda_vector_negate(lambda_vector vec1,lambda_vector vec2,int size)2353 lambda_vector_negate (lambda_vector vec1, lambda_vector vec2,
2354 int size)
2355 {
2356 lambda_vector_mult_const (vec1, vec2, size, -1);
2357 }
2358
2359 /* Negate row R1 of matrix MAT which has N columns. */
2360
2361 static void
lambda_matrix_row_negate(lambda_matrix mat,int n,int r1)2362 lambda_matrix_row_negate (lambda_matrix mat, int n, int r1)
2363 {
2364 lambda_vector_negate (mat[r1], mat[r1], n);
2365 }
2366
2367 /* Return true if two vectors are equal. */
2368
2369 static bool
lambda_vector_equal(lambda_vector vec1,lambda_vector vec2,int size)2370 lambda_vector_equal (lambda_vector vec1, lambda_vector vec2, int size)
2371 {
2372 int i;
2373 for (i = 0; i < size; i++)
2374 if (vec1[i] != vec2[i])
2375 return false;
2376 return true;
2377 }
2378
2379 /* Given an M x N integer matrix A, this function determines an M x
2380 M unimodular matrix U, and an M x N echelon matrix S such that
2381 "U.A = S". This decomposition is also known as "right Hermite".
2382
2383 Ref: Algorithm 2.1 page 33 in "Loop Transformations for
2384 Restructuring Compilers" Utpal Banerjee. */
2385
2386 static void
lambda_matrix_right_hermite(lambda_matrix A,int m,int n,lambda_matrix S,lambda_matrix U)2387 lambda_matrix_right_hermite (lambda_matrix A, int m, int n,
2388 lambda_matrix S, lambda_matrix U)
2389 {
2390 int i, j, i0 = 0;
2391
2392 lambda_matrix_copy (A, S, m, n);
2393 lambda_matrix_id (U, m);
2394
2395 for (j = 0; j < n; j++)
2396 {
2397 if (lambda_vector_first_nz (S[j], m, i0) < m)
2398 {
2399 ++i0;
2400 for (i = m - 1; i >= i0; i--)
2401 {
2402 while (S[i][j] != 0)
2403 {
2404 int sigma, factor, a, b;
2405
2406 a = S[i-1][j];
2407 b = S[i][j];
2408 sigma = (a * b < 0) ? -1: 1;
2409 a = abs (a);
2410 b = abs (b);
2411 factor = sigma * (a / b);
2412
2413 lambda_matrix_row_add (S, n, i, i-1, -factor);
2414 lambda_matrix_row_exchange (S, i, i-1);
2415
2416 lambda_matrix_row_add (U, m, i, i-1, -factor);
2417 lambda_matrix_row_exchange (U, i, i-1);
2418 }
2419 }
2420 }
2421 }
2422 }
2423
2424 /* Determines the overlapping elements due to accesses CHREC_A and
2425 CHREC_B, that are affine functions. This function cannot handle
2426 symbolic evolution functions, ie. when initial conditions are
2427 parameters, because it uses lambda matrices of integers. */
2428
2429 static void
analyze_subscript_affine_affine(tree chrec_a,tree chrec_b,conflict_function ** overlaps_a,conflict_function ** overlaps_b,tree * last_conflicts)2430 analyze_subscript_affine_affine (tree chrec_a,
2431 tree chrec_b,
2432 conflict_function **overlaps_a,
2433 conflict_function **overlaps_b,
2434 tree *last_conflicts)
2435 {
2436 unsigned nb_vars_a, nb_vars_b, dim;
2437 HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2438 lambda_matrix A, U, S;
2439 struct obstack scratch_obstack;
2440
2441 if (eq_evolutions_p (chrec_a, chrec_b))
2442 {
2443 /* The accessed index overlaps for each iteration in the
2444 loop. */
2445 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2446 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2447 *last_conflicts = chrec_dont_know;
2448 return;
2449 }
2450 if (dump_file && (dump_flags & TDF_DETAILS))
2451 fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2452
2453 /* For determining the initial intersection, we have to solve a
2454 Diophantine equation. This is the most time consuming part.
2455
2456 For answering to the question: "Is there a dependence?" we have
2457 to prove that there exists a solution to the Diophantine
2458 equation, and that the solution is in the iteration domain,
2459 i.e. the solution is positive or zero, and that the solution
2460 happens before the upper bound loop.nb_iterations. Otherwise
2461 there is no dependence. This function outputs a description of
2462 the iterations that hold the intersections. */
2463
2464 nb_vars_a = nb_vars_in_chrec (chrec_a);
2465 nb_vars_b = nb_vars_in_chrec (chrec_b);
2466
2467 gcc_obstack_init (&scratch_obstack);
2468
2469 dim = nb_vars_a + nb_vars_b;
2470 U = lambda_matrix_new (dim, dim, &scratch_obstack);
2471 A = lambda_matrix_new (dim, 1, &scratch_obstack);
2472 S = lambda_matrix_new (dim, 1, &scratch_obstack);
2473
2474 init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1));
2475 init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1));
2476 gamma = init_b - init_a;
2477
2478 /* Don't do all the hard work of solving the Diophantine equation
2479 when we already know the solution: for example,
2480 | {3, +, 1}_1
2481 | {3, +, 4}_2
2482 | gamma = 3 - 3 = 0.
2483 Then the first overlap occurs during the first iterations:
2484 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2485 */
2486 if (gamma == 0)
2487 {
2488 if (nb_vars_a == 1 && nb_vars_b == 1)
2489 {
2490 HOST_WIDE_INT step_a, step_b;
2491 HOST_WIDE_INT niter, niter_a, niter_b;
2492 affine_fn ova, ovb;
2493
2494 niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a), true);
2495 niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b), true);
2496 niter = MIN (niter_a, niter_b);
2497 step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2498 step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2499
2500 compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2501 &ova, &ovb,
2502 last_conflicts, 1);
2503 *overlaps_a = conflict_fn (1, ova);
2504 *overlaps_b = conflict_fn (1, ovb);
2505 }
2506
2507 else if (nb_vars_a == 2 && nb_vars_b == 1)
2508 compute_overlap_steps_for_affine_1_2
2509 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2510
2511 else if (nb_vars_a == 1 && nb_vars_b == 2)
2512 compute_overlap_steps_for_affine_1_2
2513 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2514
2515 else
2516 {
2517 if (dump_file && (dump_flags & TDF_DETAILS))
2518 fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2519 *overlaps_a = conflict_fn_not_known ();
2520 *overlaps_b = conflict_fn_not_known ();
2521 *last_conflicts = chrec_dont_know;
2522 }
2523 goto end_analyze_subs_aa;
2524 }
2525
2526 /* U.A = S */
2527 lambda_matrix_right_hermite (A, dim, 1, S, U);
2528
2529 if (S[0][0] < 0)
2530 {
2531 S[0][0] *= -1;
2532 lambda_matrix_row_negate (U, dim, 0);
2533 }
2534 gcd_alpha_beta = S[0][0];
2535
2536 /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2537 but that is a quite strange case. Instead of ICEing, answer
2538 don't know. */
2539 if (gcd_alpha_beta == 0)
2540 {
2541 *overlaps_a = conflict_fn_not_known ();
2542 *overlaps_b = conflict_fn_not_known ();
2543 *last_conflicts = chrec_dont_know;
2544 goto end_analyze_subs_aa;
2545 }
2546
2547 /* The classic "gcd-test". */
2548 if (!int_divides_p (gcd_alpha_beta, gamma))
2549 {
2550 /* The "gcd-test" has determined that there is no integer
2551 solution, i.e. there is no dependence. */
2552 *overlaps_a = conflict_fn_no_dependence ();
2553 *overlaps_b = conflict_fn_no_dependence ();
2554 *last_conflicts = integer_zero_node;
2555 }
2556
2557 /* Both access functions are univariate. This includes SIV and MIV cases. */
2558 else if (nb_vars_a == 1 && nb_vars_b == 1)
2559 {
2560 /* Both functions should have the same evolution sign. */
2561 if (((A[0][0] > 0 && -A[1][0] > 0)
2562 || (A[0][0] < 0 && -A[1][0] < 0)))
2563 {
2564 /* The solutions are given by:
2565 |
2566 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0]
2567 | [u21 u22] [y0]
2568
2569 For a given integer t. Using the following variables,
2570
2571 | i0 = u11 * gamma / gcd_alpha_beta
2572 | j0 = u12 * gamma / gcd_alpha_beta
2573 | i1 = u21
2574 | j1 = u22
2575
2576 the solutions are:
2577
2578 | x0 = i0 + i1 * t,
2579 | y0 = j0 + j1 * t. */
2580 HOST_WIDE_INT i0, j0, i1, j1;
2581
2582 i0 = U[0][0] * gamma / gcd_alpha_beta;
2583 j0 = U[0][1] * gamma / gcd_alpha_beta;
2584 i1 = U[1][0];
2585 j1 = U[1][1];
2586
2587 if ((i1 == 0 && i0 < 0)
2588 || (j1 == 0 && j0 < 0))
2589 {
2590 /* There is no solution.
2591 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2592 falls in here, but for the moment we don't look at the
2593 upper bound of the iteration domain. */
2594 *overlaps_a = conflict_fn_no_dependence ();
2595 *overlaps_b = conflict_fn_no_dependence ();
2596 *last_conflicts = integer_zero_node;
2597 goto end_analyze_subs_aa;
2598 }
2599
2600 if (i1 > 0 && j1 > 0)
2601 {
2602 HOST_WIDE_INT niter_a = max_stmt_executions_int
2603 (get_chrec_loop (chrec_a), true);
2604 HOST_WIDE_INT niter_b = max_stmt_executions_int
2605 (get_chrec_loop (chrec_b), true);
2606 HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2607
2608 /* (X0, Y0) is a solution of the Diophantine equation:
2609 "chrec_a (X0) = chrec_b (Y0)". */
2610 HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2611 CEIL (-j0, j1));
2612 HOST_WIDE_INT x0 = i1 * tau1 + i0;
2613 HOST_WIDE_INT y0 = j1 * tau1 + j0;
2614
2615 /* (X1, Y1) is the smallest positive solution of the eq
2616 "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2617 first conflict occurs. */
2618 HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2619 HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2620 HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2621
2622 if (niter > 0)
2623 {
2624 HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2625 FLOOR_DIV (niter - j0, j1));
2626 HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2627
2628 /* If the overlap occurs outside of the bounds of the
2629 loop, there is no dependence. */
2630 if (x1 >= niter || y1 >= niter)
2631 {
2632 *overlaps_a = conflict_fn_no_dependence ();
2633 *overlaps_b = conflict_fn_no_dependence ();
2634 *last_conflicts = integer_zero_node;
2635 goto end_analyze_subs_aa;
2636 }
2637 else
2638 *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2639 }
2640 else
2641 *last_conflicts = chrec_dont_know;
2642
2643 *overlaps_a
2644 = conflict_fn (1,
2645 affine_fn_univar (build_int_cst (NULL_TREE, x1),
2646 1,
2647 build_int_cst (NULL_TREE, i1)));
2648 *overlaps_b
2649 = conflict_fn (1,
2650 affine_fn_univar (build_int_cst (NULL_TREE, y1),
2651 1,
2652 build_int_cst (NULL_TREE, j1)));
2653 }
2654 else
2655 {
2656 /* FIXME: For the moment, the upper bound of the
2657 iteration domain for i and j is not checked. */
2658 if (dump_file && (dump_flags & TDF_DETAILS))
2659 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2660 *overlaps_a = conflict_fn_not_known ();
2661 *overlaps_b = conflict_fn_not_known ();
2662 *last_conflicts = chrec_dont_know;
2663 }
2664 }
2665 else
2666 {
2667 if (dump_file && (dump_flags & TDF_DETAILS))
2668 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2669 *overlaps_a = conflict_fn_not_known ();
2670 *overlaps_b = conflict_fn_not_known ();
2671 *last_conflicts = chrec_dont_know;
2672 }
2673 }
2674 else
2675 {
2676 if (dump_file && (dump_flags & TDF_DETAILS))
2677 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2678 *overlaps_a = conflict_fn_not_known ();
2679 *overlaps_b = conflict_fn_not_known ();
2680 *last_conflicts = chrec_dont_know;
2681 }
2682
2683 end_analyze_subs_aa:
2684 obstack_free (&scratch_obstack, NULL);
2685 if (dump_file && (dump_flags & TDF_DETAILS))
2686 {
2687 fprintf (dump_file, " (overlaps_a = ");
2688 dump_conflict_function (dump_file, *overlaps_a);
2689 fprintf (dump_file, ")\n (overlaps_b = ");
2690 dump_conflict_function (dump_file, *overlaps_b);
2691 fprintf (dump_file, ")\n");
2692 fprintf (dump_file, ")\n");
2693 }
2694 }
2695
2696 /* Returns true when analyze_subscript_affine_affine can be used for
2697 determining the dependence relation between chrec_a and chrec_b,
2698 that contain symbols. This function modifies chrec_a and chrec_b
2699 such that the analysis result is the same, and such that they don't
2700 contain symbols, and then can safely be passed to the analyzer.
2701
2702 Example: The analysis of the following tuples of evolutions produce
2703 the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2704 vs. {0, +, 1}_1
2705
2706 {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2707 {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2708 */
2709
2710 static bool
can_use_analyze_subscript_affine_affine(tree * chrec_a,tree * chrec_b)2711 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2712 {
2713 tree diff, type, left_a, left_b, right_b;
2714
2715 if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2716 || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2717 /* FIXME: For the moment not handled. Might be refined later. */
2718 return false;
2719
2720 type = chrec_type (*chrec_a);
2721 left_a = CHREC_LEFT (*chrec_a);
2722 left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL);
2723 diff = chrec_fold_minus (type, left_a, left_b);
2724
2725 if (!evolution_function_is_constant_p (diff))
2726 return false;
2727
2728 if (dump_file && (dump_flags & TDF_DETAILS))
2729 fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2730
2731 *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2732 diff, CHREC_RIGHT (*chrec_a));
2733 right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL);
2734 *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2735 build_int_cst (type, 0),
2736 right_b);
2737 return true;
2738 }
2739
2740 /* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and
2741 *OVERLAPS_B are initialized to the functions that describe the
2742 relation between the elements accessed twice by CHREC_A and
2743 CHREC_B. For k >= 0, the following property is verified:
2744
2745 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2746
2747 static void
analyze_siv_subscript(tree chrec_a,tree chrec_b,conflict_function ** overlaps_a,conflict_function ** overlaps_b,tree * last_conflicts,int loop_nest_num)2748 analyze_siv_subscript (tree chrec_a,
2749 tree chrec_b,
2750 conflict_function **overlaps_a,
2751 conflict_function **overlaps_b,
2752 tree *last_conflicts,
2753 int loop_nest_num)
2754 {
2755 dependence_stats.num_siv++;
2756
2757 if (dump_file && (dump_flags & TDF_DETAILS))
2758 fprintf (dump_file, "(analyze_siv_subscript \n");
2759
2760 if (evolution_function_is_constant_p (chrec_a)
2761 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2762 analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2763 overlaps_a, overlaps_b, last_conflicts);
2764
2765 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2766 && evolution_function_is_constant_p (chrec_b))
2767 analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2768 overlaps_b, overlaps_a, last_conflicts);
2769
2770 else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num)
2771 && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num))
2772 {
2773 if (!chrec_contains_symbols (chrec_a)
2774 && !chrec_contains_symbols (chrec_b))
2775 {
2776 analyze_subscript_affine_affine (chrec_a, chrec_b,
2777 overlaps_a, overlaps_b,
2778 last_conflicts);
2779
2780 if (CF_NOT_KNOWN_P (*overlaps_a)
2781 || CF_NOT_KNOWN_P (*overlaps_b))
2782 dependence_stats.num_siv_unimplemented++;
2783 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2784 || CF_NO_DEPENDENCE_P (*overlaps_b))
2785 dependence_stats.num_siv_independent++;
2786 else
2787 dependence_stats.num_siv_dependent++;
2788 }
2789 else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2790 &chrec_b))
2791 {
2792 analyze_subscript_affine_affine (chrec_a, chrec_b,
2793 overlaps_a, overlaps_b,
2794 last_conflicts);
2795
2796 if (CF_NOT_KNOWN_P (*overlaps_a)
2797 || CF_NOT_KNOWN_P (*overlaps_b))
2798 dependence_stats.num_siv_unimplemented++;
2799 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2800 || CF_NO_DEPENDENCE_P (*overlaps_b))
2801 dependence_stats.num_siv_independent++;
2802 else
2803 dependence_stats.num_siv_dependent++;
2804 }
2805 else
2806 goto siv_subscript_dontknow;
2807 }
2808
2809 else
2810 {
2811 siv_subscript_dontknow:;
2812 if (dump_file && (dump_flags & TDF_DETAILS))
2813 fprintf (dump_file, "siv test failed: unimplemented.\n");
2814 *overlaps_a = conflict_fn_not_known ();
2815 *overlaps_b = conflict_fn_not_known ();
2816 *last_conflicts = chrec_dont_know;
2817 dependence_stats.num_siv_unimplemented++;
2818 }
2819
2820 if (dump_file && (dump_flags & TDF_DETAILS))
2821 fprintf (dump_file, ")\n");
2822 }
2823
2824 /* Returns false if we can prove that the greatest common divisor of the steps
2825 of CHREC does not divide CST, false otherwise. */
2826
2827 static bool
gcd_of_steps_may_divide_p(const_tree chrec,const_tree cst)2828 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2829 {
2830 HOST_WIDE_INT cd = 0, val;
2831 tree step;
2832
2833 if (!host_integerp (cst, 0))
2834 return true;
2835 val = tree_low_cst (cst, 0);
2836
2837 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2838 {
2839 step = CHREC_RIGHT (chrec);
2840 if (!host_integerp (step, 0))
2841 return true;
2842 cd = gcd (cd, tree_low_cst (step, 0));
2843 chrec = CHREC_LEFT (chrec);
2844 }
2845
2846 return val % cd == 0;
2847 }
2848
2849 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2850 LOOP_NEST. *OVERLAPS_A and *OVERLAPS_B are initialized to the
2851 functions that describe the relation between the elements accessed
2852 twice by CHREC_A and CHREC_B. For k >= 0, the following property
2853 is verified:
2854
2855 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */
2856
2857 static void
analyze_miv_subscript(tree chrec_a,tree chrec_b,conflict_function ** overlaps_a,conflict_function ** overlaps_b,tree * last_conflicts,struct loop * loop_nest)2858 analyze_miv_subscript (tree chrec_a,
2859 tree chrec_b,
2860 conflict_function **overlaps_a,
2861 conflict_function **overlaps_b,
2862 tree *last_conflicts,
2863 struct loop *loop_nest)
2864 {
2865 tree type, difference;
2866
2867 dependence_stats.num_miv++;
2868 if (dump_file && (dump_flags & TDF_DETAILS))
2869 fprintf (dump_file, "(analyze_miv_subscript \n");
2870
2871 type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2872 chrec_a = chrec_convert (type, chrec_a, NULL);
2873 chrec_b = chrec_convert (type, chrec_b, NULL);
2874 difference = chrec_fold_minus (type, chrec_a, chrec_b);
2875
2876 if (eq_evolutions_p (chrec_a, chrec_b))
2877 {
2878 /* Access functions are the same: all the elements are accessed
2879 in the same order. */
2880 *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2881 *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2882 *last_conflicts = max_stmt_executions_tree (get_chrec_loop (chrec_a));
2883 dependence_stats.num_miv_dependent++;
2884 }
2885
2886 else if (evolution_function_is_constant_p (difference)
2887 /* For the moment, the following is verified:
2888 evolution_function_is_affine_multivariate_p (chrec_a,
2889 loop_nest->num) */
2890 && !gcd_of_steps_may_divide_p (chrec_a, difference))
2891 {
2892 /* testsuite/.../ssa-chrec-33.c
2893 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2
2894
2895 The difference is 1, and all the evolution steps are multiples
2896 of 2, consequently there are no overlapping elements. */
2897 *overlaps_a = conflict_fn_no_dependence ();
2898 *overlaps_b = conflict_fn_no_dependence ();
2899 *last_conflicts = integer_zero_node;
2900 dependence_stats.num_miv_independent++;
2901 }
2902
2903 else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2904 && !chrec_contains_symbols (chrec_a)
2905 && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2906 && !chrec_contains_symbols (chrec_b))
2907 {
2908 /* testsuite/.../ssa-chrec-35.c
2909 {0, +, 1}_2 vs. {0, +, 1}_3
2910 the overlapping elements are respectively located at iterations:
2911 {0, +, 1}_x and {0, +, 1}_x,
2912 in other words, we have the equality:
2913 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2914
2915 Other examples:
2916 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2917 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2918
2919 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2920 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2921 */
2922 analyze_subscript_affine_affine (chrec_a, chrec_b,
2923 overlaps_a, overlaps_b, last_conflicts);
2924
2925 if (CF_NOT_KNOWN_P (*overlaps_a)
2926 || CF_NOT_KNOWN_P (*overlaps_b))
2927 dependence_stats.num_miv_unimplemented++;
2928 else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2929 || CF_NO_DEPENDENCE_P (*overlaps_b))
2930 dependence_stats.num_miv_independent++;
2931 else
2932 dependence_stats.num_miv_dependent++;
2933 }
2934
2935 else
2936 {
2937 /* When the analysis is too difficult, answer "don't know". */
2938 if (dump_file && (dump_flags & TDF_DETAILS))
2939 fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2940
2941 *overlaps_a = conflict_fn_not_known ();
2942 *overlaps_b = conflict_fn_not_known ();
2943 *last_conflicts = chrec_dont_know;
2944 dependence_stats.num_miv_unimplemented++;
2945 }
2946
2947 if (dump_file && (dump_flags & TDF_DETAILS))
2948 fprintf (dump_file, ")\n");
2949 }
2950
2951 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2952 with respect to LOOP_NEST. OVERLAP_ITERATIONS_A and
2953 OVERLAP_ITERATIONS_B are initialized with two functions that
2954 describe the iterations that contain conflicting elements.
2955
2956 Remark: For an integer k >= 0, the following equality is true:
2957
2958 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2959 */
2960
2961 static void
analyze_overlapping_iterations(tree chrec_a,tree chrec_b,conflict_function ** overlap_iterations_a,conflict_function ** overlap_iterations_b,tree * last_conflicts,struct loop * loop_nest)2962 analyze_overlapping_iterations (tree chrec_a,
2963 tree chrec_b,
2964 conflict_function **overlap_iterations_a,
2965 conflict_function **overlap_iterations_b,
2966 tree *last_conflicts, struct loop *loop_nest)
2967 {
2968 unsigned int lnn = loop_nest->num;
2969
2970 dependence_stats.num_subscript_tests++;
2971
2972 if (dump_file && (dump_flags & TDF_DETAILS))
2973 {
2974 fprintf (dump_file, "(analyze_overlapping_iterations \n");
2975 fprintf (dump_file, " (chrec_a = ");
2976 print_generic_expr (dump_file, chrec_a, 0);
2977 fprintf (dump_file, ")\n (chrec_b = ");
2978 print_generic_expr (dump_file, chrec_b, 0);
2979 fprintf (dump_file, ")\n");
2980 }
2981
2982 if (chrec_a == NULL_TREE
2983 || chrec_b == NULL_TREE
2984 || chrec_contains_undetermined (chrec_a)
2985 || chrec_contains_undetermined (chrec_b))
2986 {
2987 dependence_stats.num_subscript_undetermined++;
2988
2989 *overlap_iterations_a = conflict_fn_not_known ();
2990 *overlap_iterations_b = conflict_fn_not_known ();
2991 }
2992
2993 /* If they are the same chrec, and are affine, they overlap
2994 on every iteration. */
2995 else if (eq_evolutions_p (chrec_a, chrec_b)
2996 && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2997 || operand_equal_p (chrec_a, chrec_b, 0)))
2998 {
2999 dependence_stats.num_same_subscript_function++;
3000 *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3001 *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3002 *last_conflicts = chrec_dont_know;
3003 }
3004
3005 /* If they aren't the same, and aren't affine, we can't do anything
3006 yet. */
3007 else if ((chrec_contains_symbols (chrec_a)
3008 || chrec_contains_symbols (chrec_b))
3009 && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
3010 || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
3011 {
3012 dependence_stats.num_subscript_undetermined++;
3013 *overlap_iterations_a = conflict_fn_not_known ();
3014 *overlap_iterations_b = conflict_fn_not_known ();
3015 }
3016
3017 else if (ziv_subscript_p (chrec_a, chrec_b))
3018 analyze_ziv_subscript (chrec_a, chrec_b,
3019 overlap_iterations_a, overlap_iterations_b,
3020 last_conflicts);
3021
3022 else if (siv_subscript_p (chrec_a, chrec_b))
3023 analyze_siv_subscript (chrec_a, chrec_b,
3024 overlap_iterations_a, overlap_iterations_b,
3025 last_conflicts, lnn);
3026
3027 else
3028 analyze_miv_subscript (chrec_a, chrec_b,
3029 overlap_iterations_a, overlap_iterations_b,
3030 last_conflicts, loop_nest);
3031
3032 if (dump_file && (dump_flags & TDF_DETAILS))
3033 {
3034 fprintf (dump_file, " (overlap_iterations_a = ");
3035 dump_conflict_function (dump_file, *overlap_iterations_a);
3036 fprintf (dump_file, ")\n (overlap_iterations_b = ");
3037 dump_conflict_function (dump_file, *overlap_iterations_b);
3038 fprintf (dump_file, ")\n");
3039 fprintf (dump_file, ")\n");
3040 }
3041 }
3042
3043 /* Helper function for uniquely inserting distance vectors. */
3044
3045 static void
save_dist_v(struct data_dependence_relation * ddr,lambda_vector dist_v)3046 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3047 {
3048 unsigned i;
3049 lambda_vector v;
3050
3051 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, v)
3052 if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3053 return;
3054
3055 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3056 }
3057
3058 /* Helper function for uniquely inserting direction vectors. */
3059
3060 static void
save_dir_v(struct data_dependence_relation * ddr,lambda_vector dir_v)3061 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3062 {
3063 unsigned i;
3064 lambda_vector v;
3065
3066 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), i, v)
3067 if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3068 return;
3069
3070 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3071 }
3072
3073 /* Add a distance of 1 on all the loops outer than INDEX. If we
3074 haven't yet determined a distance for this outer loop, push a new
3075 distance vector composed of the previous distance, and a distance
3076 of 1 for this outer loop. Example:
3077
3078 | loop_1
3079 | loop_2
3080 | A[10]
3081 | endloop_2
3082 | endloop_1
3083
3084 Saved vectors are of the form (dist_in_1, dist_in_2). First, we
3085 save (0, 1), then we have to save (1, 0). */
3086
3087 static void
add_outer_distances(struct data_dependence_relation * ddr,lambda_vector dist_v,int index)3088 add_outer_distances (struct data_dependence_relation *ddr,
3089 lambda_vector dist_v, int index)
3090 {
3091 /* For each outer loop where init_v is not set, the accesses are
3092 in dependence of distance 1 in the loop. */
3093 while (--index >= 0)
3094 {
3095 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3096 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3097 save_v[index] = 1;
3098 save_dist_v (ddr, save_v);
3099 }
3100 }
3101
3102 /* Return false when fail to represent the data dependence as a
3103 distance vector. INIT_B is set to true when a component has been
3104 added to the distance vector DIST_V. INDEX_CARRY is then set to
3105 the index in DIST_V that carries the dependence. */
3106
3107 static bool
build_classic_dist_vector_1(struct data_dependence_relation * ddr,struct data_reference * ddr_a,struct data_reference * ddr_b,lambda_vector dist_v,bool * init_b,int * index_carry)3108 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3109 struct data_reference *ddr_a,
3110 struct data_reference *ddr_b,
3111 lambda_vector dist_v, bool *init_b,
3112 int *index_carry)
3113 {
3114 unsigned i;
3115 lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3116
3117 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3118 {
3119 tree access_fn_a, access_fn_b;
3120 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3121
3122 if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3123 {
3124 non_affine_dependence_relation (ddr);
3125 return false;
3126 }
3127
3128 access_fn_a = DR_ACCESS_FN (ddr_a, i);
3129 access_fn_b = DR_ACCESS_FN (ddr_b, i);
3130
3131 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3132 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3133 {
3134 int dist, index;
3135 int var_a = CHREC_VARIABLE (access_fn_a);
3136 int var_b = CHREC_VARIABLE (access_fn_b);
3137
3138 if (var_a != var_b
3139 || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3140 {
3141 non_affine_dependence_relation (ddr);
3142 return false;
3143 }
3144
3145 dist = int_cst_value (SUB_DISTANCE (subscript));
3146 index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
3147 *index_carry = MIN (index, *index_carry);
3148
3149 /* This is the subscript coupling test. If we have already
3150 recorded a distance for this loop (a distance coming from
3151 another subscript), it should be the same. For example,
3152 in the following code, there is no dependence:
3153
3154 | loop i = 0, N, 1
3155 | T[i+1][i] = ...
3156 | ... = T[i][i]
3157 | endloop
3158 */
3159 if (init_v[index] != 0 && dist_v[index] != dist)
3160 {
3161 finalize_ddr_dependent (ddr, chrec_known);
3162 return false;
3163 }
3164
3165 dist_v[index] = dist;
3166 init_v[index] = 1;
3167 *init_b = true;
3168 }
3169 else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
3170 {
3171 /* This can be for example an affine vs. constant dependence
3172 (T[i] vs. T[3]) that is not an affine dependence and is
3173 not representable as a distance vector. */
3174 non_affine_dependence_relation (ddr);
3175 return false;
3176 }
3177 }
3178
3179 return true;
3180 }
3181
3182 /* Return true when the DDR contains only constant access functions. */
3183
3184 static bool
constant_access_functions(const struct data_dependence_relation * ddr)3185 constant_access_functions (const struct data_dependence_relation *ddr)
3186 {
3187 unsigned i;
3188
3189 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3190 if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
3191 || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
3192 return false;
3193
3194 return true;
3195 }
3196
3197 /* Helper function for the case where DDR_A and DDR_B are the same
3198 multivariate access function with a constant step. For an example
3199 see pr34635-1.c. */
3200
3201 static void
add_multivariate_self_dist(struct data_dependence_relation * ddr,tree c_2)3202 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3203 {
3204 int x_1, x_2;
3205 tree c_1 = CHREC_LEFT (c_2);
3206 tree c_0 = CHREC_LEFT (c_1);
3207 lambda_vector dist_v;
3208 int v1, v2, cd;
3209
3210 /* Polynomials with more than 2 variables are not handled yet. When
3211 the evolution steps are parameters, it is not possible to
3212 represent the dependence using classical distance vectors. */
3213 if (TREE_CODE (c_0) != INTEGER_CST
3214 || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
3215 || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
3216 {
3217 DDR_AFFINE_P (ddr) = false;
3218 return;
3219 }
3220
3221 x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3222 x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3223
3224 /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */
3225 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3226 v1 = int_cst_value (CHREC_RIGHT (c_1));
3227 v2 = int_cst_value (CHREC_RIGHT (c_2));
3228 cd = gcd (v1, v2);
3229 v1 /= cd;
3230 v2 /= cd;
3231
3232 if (v2 < 0)
3233 {
3234 v2 = -v2;
3235 v1 = -v1;
3236 }
3237
3238 dist_v[x_1] = v2;
3239 dist_v[x_2] = -v1;
3240 save_dist_v (ddr, dist_v);
3241
3242 add_outer_distances (ddr, dist_v, x_1);
3243 }
3244
3245 /* Helper function for the case where DDR_A and DDR_B are the same
3246 access functions. */
3247
3248 static void
add_other_self_distances(struct data_dependence_relation * ddr)3249 add_other_self_distances (struct data_dependence_relation *ddr)
3250 {
3251 lambda_vector dist_v;
3252 unsigned i;
3253 int index_carry = DDR_NB_LOOPS (ddr);
3254
3255 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3256 {
3257 tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3258
3259 if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3260 {
3261 if (!evolution_function_is_univariate_p (access_fun))
3262 {
3263 if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3264 {
3265 DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3266 return;
3267 }
3268
3269 access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
3270
3271 if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
3272 add_multivariate_self_dist (ddr, access_fun);
3273 else
3274 /* The evolution step is not constant: it varies in
3275 the outer loop, so this cannot be represented by a
3276 distance vector. For example in pr34635.c the
3277 evolution is {0, +, {0, +, 4}_1}_2. */
3278 DDR_AFFINE_P (ddr) = false;
3279
3280 return;
3281 }
3282
3283 index_carry = MIN (index_carry,
3284 index_in_loop_nest (CHREC_VARIABLE (access_fun),
3285 DDR_LOOP_NEST (ddr)));
3286 }
3287 }
3288
3289 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3290 add_outer_distances (ddr, dist_v, index_carry);
3291 }
3292
3293 static void
insert_innermost_unit_dist_vector(struct data_dependence_relation * ddr)3294 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
3295 {
3296 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3297
3298 dist_v[DDR_INNER_LOOP (ddr)] = 1;
3299 save_dist_v (ddr, dist_v);
3300 }
3301
3302 /* Adds a unit distance vector to DDR when there is a 0 overlap. This
3303 is the case for example when access functions are the same and
3304 equal to a constant, as in:
3305
3306 | loop_1
3307 | A[3] = ...
3308 | ... = A[3]
3309 | endloop_1
3310
3311 in which case the distance vectors are (0) and (1). */
3312
3313 static void
add_distance_for_zero_overlaps(struct data_dependence_relation * ddr)3314 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
3315 {
3316 unsigned i, j;
3317
3318 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3319 {
3320 subscript_p sub = DDR_SUBSCRIPT (ddr, i);
3321 conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
3322 conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
3323
3324 for (j = 0; j < ca->n; j++)
3325 if (affine_function_zero_p (ca->fns[j]))
3326 {
3327 insert_innermost_unit_dist_vector (ddr);
3328 return;
3329 }
3330
3331 for (j = 0; j < cb->n; j++)
3332 if (affine_function_zero_p (cb->fns[j]))
3333 {
3334 insert_innermost_unit_dist_vector (ddr);
3335 return;
3336 }
3337 }
3338 }
3339
3340 /* Compute the classic per loop distance vector. DDR is the data
3341 dependence relation to build a vector from. Return false when fail
3342 to represent the data dependence as a distance vector. */
3343
3344 static bool
build_classic_dist_vector(struct data_dependence_relation * ddr,struct loop * loop_nest)3345 build_classic_dist_vector (struct data_dependence_relation *ddr,
3346 struct loop *loop_nest)
3347 {
3348 bool init_b = false;
3349 int index_carry = DDR_NB_LOOPS (ddr);
3350 lambda_vector dist_v;
3351
3352 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3353 return false;
3354
3355 if (same_access_functions (ddr))
3356 {
3357 /* Save the 0 vector. */
3358 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3359 save_dist_v (ddr, dist_v);
3360
3361 if (constant_access_functions (ddr))
3362 add_distance_for_zero_overlaps (ddr);
3363
3364 if (DDR_NB_LOOPS (ddr) > 1)
3365 add_other_self_distances (ddr);
3366
3367 return true;
3368 }
3369
3370 dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3371 if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3372 dist_v, &init_b, &index_carry))
3373 return false;
3374
3375 /* Save the distance vector if we initialized one. */
3376 if (init_b)
3377 {
3378 /* Verify a basic constraint: classic distance vectors should
3379 always be lexicographically positive.
3380
3381 Data references are collected in the order of execution of
3382 the program, thus for the following loop
3383
3384 | for (i = 1; i < 100; i++)
3385 | for (j = 1; j < 100; j++)
3386 | {
3387 | t = T[j+1][i-1]; // A
3388 | T[j][i] = t + 2; // B
3389 | }
3390
3391 references are collected following the direction of the wind:
3392 A then B. The data dependence tests are performed also
3393 following this order, such that we're looking at the distance
3394 separating the elements accessed by A from the elements later
3395 accessed by B. But in this example, the distance returned by
3396 test_dep (A, B) is lexicographically negative (-1, 1), that
3397 means that the access A occurs later than B with respect to
3398 the outer loop, ie. we're actually looking upwind. In this
3399 case we solve test_dep (B, A) looking downwind to the
3400 lexicographically positive solution, that returns the
3401 distance vector (1, -1). */
3402 if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3403 {
3404 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3405 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3406 loop_nest))
3407 return false;
3408 compute_subscript_distance (ddr);
3409 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3410 save_v, &init_b, &index_carry))
3411 return false;
3412 save_dist_v (ddr, save_v);
3413 DDR_REVERSED_P (ddr) = true;
3414
3415 /* In this case there is a dependence forward for all the
3416 outer loops:
3417
3418 | for (k = 1; k < 100; k++)
3419 | for (i = 1; i < 100; i++)
3420 | for (j = 1; j < 100; j++)
3421 | {
3422 | t = T[j+1][i-1]; // A
3423 | T[j][i] = t + 2; // B
3424 | }
3425
3426 the vectors are:
3427 (0, 1, -1)
3428 (1, 1, -1)
3429 (1, -1, 1)
3430 */
3431 if (DDR_NB_LOOPS (ddr) > 1)
3432 {
3433 add_outer_distances (ddr, save_v, index_carry);
3434 add_outer_distances (ddr, dist_v, index_carry);
3435 }
3436 }
3437 else
3438 {
3439 lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3440 lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3441
3442 if (DDR_NB_LOOPS (ddr) > 1)
3443 {
3444 lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3445
3446 if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3447 DDR_A (ddr), loop_nest))
3448 return false;
3449 compute_subscript_distance (ddr);
3450 if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3451 opposite_v, &init_b,
3452 &index_carry))
3453 return false;
3454
3455 save_dist_v (ddr, save_v);
3456 add_outer_distances (ddr, dist_v, index_carry);
3457 add_outer_distances (ddr, opposite_v, index_carry);
3458 }
3459 else
3460 save_dist_v (ddr, save_v);
3461 }
3462 }
3463 else
3464 {
3465 /* There is a distance of 1 on all the outer loops: Example:
3466 there is a dependence of distance 1 on loop_1 for the array A.
3467
3468 | loop_1
3469 | A[5] = ...
3470 | endloop
3471 */
3472 add_outer_distances (ddr, dist_v,
3473 lambda_vector_first_nz (dist_v,
3474 DDR_NB_LOOPS (ddr), 0));
3475 }
3476
3477 if (dump_file && (dump_flags & TDF_DETAILS))
3478 {
3479 unsigned i;
3480
3481 fprintf (dump_file, "(build_classic_dist_vector\n");
3482 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3483 {
3484 fprintf (dump_file, " dist_vector = (");
3485 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3486 DDR_NB_LOOPS (ddr));
3487 fprintf (dump_file, " )\n");
3488 }
3489 fprintf (dump_file, ")\n");
3490 }
3491
3492 return true;
3493 }
3494
3495 /* Return the direction for a given distance.
3496 FIXME: Computing dir this way is suboptimal, since dir can catch
3497 cases that dist is unable to represent. */
3498
3499 static inline enum data_dependence_direction
dir_from_dist(int dist)3500 dir_from_dist (int dist)
3501 {
3502 if (dist > 0)
3503 return dir_positive;
3504 else if (dist < 0)
3505 return dir_negative;
3506 else
3507 return dir_equal;
3508 }
3509
3510 /* Compute the classic per loop direction vector. DDR is the data
3511 dependence relation to build a vector from. */
3512
3513 static void
build_classic_dir_vector(struct data_dependence_relation * ddr)3514 build_classic_dir_vector (struct data_dependence_relation *ddr)
3515 {
3516 unsigned i, j;
3517 lambda_vector dist_v;
3518
3519 FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v)
3520 {
3521 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3522
3523 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3524 dir_v[j] = dir_from_dist (dist_v[j]);
3525
3526 save_dir_v (ddr, dir_v);
3527 }
3528 }
3529
3530 /* Helper function. Returns true when there is a dependence between
3531 data references DRA and DRB. */
3532
3533 static bool
subscript_dependence_tester_1(struct data_dependence_relation * ddr,struct data_reference * dra,struct data_reference * drb,struct loop * loop_nest)3534 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3535 struct data_reference *dra,
3536 struct data_reference *drb,
3537 struct loop *loop_nest)
3538 {
3539 unsigned int i;
3540 tree last_conflicts;
3541 struct subscript *subscript;
3542 tree res = NULL_TREE;
3543
3544 for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3545 i++)
3546 {
3547 conflict_function *overlaps_a, *overlaps_b;
3548
3549 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3550 DR_ACCESS_FN (drb, i),
3551 &overlaps_a, &overlaps_b,
3552 &last_conflicts, loop_nest);
3553
3554 if (SUB_CONFLICTS_IN_A (subscript))
3555 free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3556 if (SUB_CONFLICTS_IN_B (subscript))
3557 free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3558
3559 SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3560 SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3561 SUB_LAST_CONFLICT (subscript) = last_conflicts;
3562
3563 /* If there is any undetermined conflict function we have to
3564 give a conservative answer in case we cannot prove that
3565 no dependence exists when analyzing another subscript. */
3566 if (CF_NOT_KNOWN_P (overlaps_a)
3567 || CF_NOT_KNOWN_P (overlaps_b))
3568 {
3569 res = chrec_dont_know;
3570 continue;
3571 }
3572
3573 /* When there is a subscript with no dependence we can stop. */
3574 else if (CF_NO_DEPENDENCE_P (overlaps_a)
3575 || CF_NO_DEPENDENCE_P (overlaps_b))
3576 {
3577 res = chrec_known;
3578 break;
3579 }
3580 }
3581
3582 if (res == NULL_TREE)
3583 return true;
3584
3585 if (res == chrec_known)
3586 dependence_stats.num_dependence_independent++;
3587 else
3588 dependence_stats.num_dependence_undetermined++;
3589 finalize_ddr_dependent (ddr, res);
3590 return false;
3591 }
3592
3593 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */
3594
3595 static void
subscript_dependence_tester(struct data_dependence_relation * ddr,struct loop * loop_nest)3596 subscript_dependence_tester (struct data_dependence_relation *ddr,
3597 struct loop *loop_nest)
3598 {
3599
3600 if (dump_file && (dump_flags & TDF_DETAILS))
3601 fprintf (dump_file, "(subscript_dependence_tester \n");
3602
3603 if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3604 dependence_stats.num_dependence_dependent++;
3605
3606 compute_subscript_distance (ddr);
3607 if (build_classic_dist_vector (ddr, loop_nest))
3608 build_classic_dir_vector (ddr);
3609
3610 if (dump_file && (dump_flags & TDF_DETAILS))
3611 fprintf (dump_file, ")\n");
3612 }
3613
3614 /* Returns true when all the access functions of A are affine or
3615 constant with respect to LOOP_NEST. */
3616
3617 static bool
access_functions_are_affine_or_constant_p(const struct data_reference * a,const struct loop * loop_nest)3618 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3619 const struct loop *loop_nest)
3620 {
3621 unsigned int i;
3622 VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3623 tree t;
3624
3625 FOR_EACH_VEC_ELT (tree, fns, i, t)
3626 if (!evolution_function_is_invariant_p (t, loop_nest->num)
3627 && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3628 return false;
3629
3630 return true;
3631 }
3632
3633 /* Initializes an equation for an OMEGA problem using the information
3634 contained in the ACCESS_FUN. Returns true when the operation
3635 succeeded.
3636
3637 PB is the omega constraint system.
3638 EQ is the number of the equation to be initialized.
3639 OFFSET is used for shifting the variables names in the constraints:
3640 a constrain is composed of 2 * the number of variables surrounding
3641 dependence accesses. OFFSET is set either to 0 for the first n variables,
3642 then it is set to n.
3643 ACCESS_FUN is expected to be an affine chrec. */
3644
3645 static bool
init_omega_eq_with_af(omega_pb pb,unsigned eq,unsigned int offset,tree access_fun,struct data_dependence_relation * ddr)3646 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3647 unsigned int offset, tree access_fun,
3648 struct data_dependence_relation *ddr)
3649 {
3650 switch (TREE_CODE (access_fun))
3651 {
3652 case POLYNOMIAL_CHREC:
3653 {
3654 tree left = CHREC_LEFT (access_fun);
3655 tree right = CHREC_RIGHT (access_fun);
3656 int var = CHREC_VARIABLE (access_fun);
3657 unsigned var_idx;
3658
3659 if (TREE_CODE (right) != INTEGER_CST)
3660 return false;
3661
3662 var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3663 pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3664
3665 /* Compute the innermost loop index. */
3666 DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3667
3668 if (offset == 0)
3669 pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3670 += int_cst_value (right);
3671
3672 switch (TREE_CODE (left))
3673 {
3674 case POLYNOMIAL_CHREC:
3675 return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3676
3677 case INTEGER_CST:
3678 pb->eqs[eq].coef[0] += int_cst_value (left);
3679 return true;
3680
3681 default:
3682 return false;
3683 }
3684 }
3685
3686 case INTEGER_CST:
3687 pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3688 return true;
3689
3690 default:
3691 return false;
3692 }
3693 }
3694
3695 /* As explained in the comments preceding init_omega_for_ddr, we have
3696 to set up a system for each loop level, setting outer loops
3697 variation to zero, and current loop variation to positive or zero.
3698 Save each lexico positive distance vector. */
3699
3700 static void
omega_extract_distance_vectors(omega_pb pb,struct data_dependence_relation * ddr)3701 omega_extract_distance_vectors (omega_pb pb,
3702 struct data_dependence_relation *ddr)
3703 {
3704 int eq, geq;
3705 unsigned i, j;
3706 struct loop *loopi, *loopj;
3707 enum omega_result res;
3708
3709 /* Set a new problem for each loop in the nest. The basis is the
3710 problem that we have initialized until now. On top of this we
3711 add new constraints. */
3712 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3713 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3714 {
3715 int dist = 0;
3716 omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3717 DDR_NB_LOOPS (ddr));
3718
3719 omega_copy_problem (copy, pb);
3720
3721 /* For all the outer loops "loop_j", add "dj = 0". */
3722 for (j = 0;
3723 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3724 {
3725 eq = omega_add_zero_eq (copy, omega_black);
3726 copy->eqs[eq].coef[j + 1] = 1;
3727 }
3728
3729 /* For "loop_i", add "0 <= di". */
3730 geq = omega_add_zero_geq (copy, omega_black);
3731 copy->geqs[geq].coef[i + 1] = 1;
3732
3733 /* Reduce the constraint system, and test that the current
3734 problem is feasible. */
3735 res = omega_simplify_problem (copy);
3736 if (res == omega_false
3737 || res == omega_unknown
3738 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3739 goto next_problem;
3740
3741 for (eq = 0; eq < copy->num_subs; eq++)
3742 if (copy->subs[eq].key == (int) i + 1)
3743 {
3744 dist = copy->subs[eq].coef[0];
3745 goto found_dist;
3746 }
3747
3748 if (dist == 0)
3749 {
3750 /* Reinitialize problem... */
3751 omega_copy_problem (copy, pb);
3752 for (j = 0;
3753 j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3754 {
3755 eq = omega_add_zero_eq (copy, omega_black);
3756 copy->eqs[eq].coef[j + 1] = 1;
3757 }
3758
3759 /* ..., but this time "di = 1". */
3760 eq = omega_add_zero_eq (copy, omega_black);
3761 copy->eqs[eq].coef[i + 1] = 1;
3762 copy->eqs[eq].coef[0] = -1;
3763
3764 res = omega_simplify_problem (copy);
3765 if (res == omega_false
3766 || res == omega_unknown
3767 || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3768 goto next_problem;
3769
3770 for (eq = 0; eq < copy->num_subs; eq++)
3771 if (copy->subs[eq].key == (int) i + 1)
3772 {
3773 dist = copy->subs[eq].coef[0];
3774 goto found_dist;
3775 }
3776 }
3777
3778 found_dist:;
3779 /* Save the lexicographically positive distance vector. */
3780 if (dist >= 0)
3781 {
3782 lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3783 lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3784
3785 dist_v[i] = dist;
3786
3787 for (eq = 0; eq < copy->num_subs; eq++)
3788 if (copy->subs[eq].key > 0)
3789 {
3790 dist = copy->subs[eq].coef[0];
3791 dist_v[copy->subs[eq].key - 1] = dist;
3792 }
3793
3794 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3795 dir_v[j] = dir_from_dist (dist_v[j]);
3796
3797 save_dist_v (ddr, dist_v);
3798 save_dir_v (ddr, dir_v);
3799 }
3800
3801 next_problem:;
3802 omega_free_problem (copy);
3803 }
3804 }
3805
3806 /* This is called for each subscript of a tuple of data references:
3807 insert an equality for representing the conflicts. */
3808
3809 static bool
omega_setup_subscript(tree access_fun_a,tree access_fun_b,struct data_dependence_relation * ddr,omega_pb pb,bool * maybe_dependent)3810 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3811 struct data_dependence_relation *ddr,
3812 omega_pb pb, bool *maybe_dependent)
3813 {
3814 int eq;
3815 tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3816 TREE_TYPE (access_fun_b));
3817 tree fun_a = chrec_convert (type, access_fun_a, NULL);
3818 tree fun_b = chrec_convert (type, access_fun_b, NULL);
3819 tree difference = chrec_fold_minus (type, fun_a, fun_b);
3820 tree minus_one;
3821
3822 /* When the fun_a - fun_b is not constant, the dependence is not
3823 captured by the classic distance vector representation. */
3824 if (TREE_CODE (difference) != INTEGER_CST)
3825 return false;
3826
3827 /* ZIV test. */
3828 if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3829 {
3830 /* There is no dependence. */
3831 *maybe_dependent = false;
3832 return true;
3833 }
3834
3835 minus_one = build_int_cst (type, -1);
3836 fun_b = chrec_fold_multiply (type, fun_b, minus_one);
3837
3838 eq = omega_add_zero_eq (pb, omega_black);
3839 if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3840 || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3841 /* There is probably a dependence, but the system of
3842 constraints cannot be built: answer "don't know". */
3843 return false;
3844
3845 /* GCD test. */
3846 if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3847 && !int_divides_p (lambda_vector_gcd
3848 ((lambda_vector) &(pb->eqs[eq].coef[1]),
3849 2 * DDR_NB_LOOPS (ddr)),
3850 pb->eqs[eq].coef[0]))
3851 {
3852 /* There is no dependence. */
3853 *maybe_dependent = false;
3854 return true;
3855 }
3856
3857 return true;
3858 }
3859
3860 /* Helper function, same as init_omega_for_ddr but specialized for
3861 data references A and B. */
3862
3863 static bool
init_omega_for_ddr_1(struct data_reference * dra,struct data_reference * drb,struct data_dependence_relation * ddr,omega_pb pb,bool * maybe_dependent)3864 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3865 struct data_dependence_relation *ddr,
3866 omega_pb pb, bool *maybe_dependent)
3867 {
3868 unsigned i;
3869 int ineq;
3870 struct loop *loopi;
3871 unsigned nb_loops = DDR_NB_LOOPS (ddr);
3872
3873 /* Insert an equality per subscript. */
3874 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3875 {
3876 if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3877 ddr, pb, maybe_dependent))
3878 return false;
3879 else if (*maybe_dependent == false)
3880 {
3881 /* There is no dependence. */
3882 DDR_ARE_DEPENDENT (ddr) = chrec_known;
3883 return true;
3884 }
3885 }
3886
3887 /* Insert inequalities: constraints corresponding to the iteration
3888 domain, i.e. the loops surrounding the references "loop_x" and
3889 the distance variables "dx". The layout of the OMEGA
3890 representation is as follows:
3891 - coef[0] is the constant
3892 - coef[1..nb_loops] are the protected variables that will not be
3893 removed by the solver: the "dx"
3894 - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3895 */
3896 for (i = 0; i <= DDR_INNER_LOOP (ddr)
3897 && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3898 {
3899 HOST_WIDE_INT nbi = max_stmt_executions_int (loopi, true);
3900
3901 /* 0 <= loop_x */
3902 ineq = omega_add_zero_geq (pb, omega_black);
3903 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3904
3905 /* 0 <= loop_x + dx */
3906 ineq = omega_add_zero_geq (pb, omega_black);
3907 pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3908 pb->geqs[ineq].coef[i + 1] = 1;
3909
3910 if (nbi != -1)
3911 {
3912 /* loop_x <= nb_iters */
3913 ineq = omega_add_zero_geq (pb, omega_black);
3914 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3915 pb->geqs[ineq].coef[0] = nbi;
3916
3917 /* loop_x + dx <= nb_iters */
3918 ineq = omega_add_zero_geq (pb, omega_black);
3919 pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3920 pb->geqs[ineq].coef[i + 1] = -1;
3921 pb->geqs[ineq].coef[0] = nbi;
3922
3923 /* A step "dx" bigger than nb_iters is not feasible, so
3924 add "0 <= nb_iters + dx", */
3925 ineq = omega_add_zero_geq (pb, omega_black);
3926 pb->geqs[ineq].coef[i + 1] = 1;
3927 pb->geqs[ineq].coef[0] = nbi;
3928 /* and "dx <= nb_iters". */
3929 ineq = omega_add_zero_geq (pb, omega_black);
3930 pb->geqs[ineq].coef[i + 1] = -1;
3931 pb->geqs[ineq].coef[0] = nbi;
3932 }
3933 }
3934
3935 omega_extract_distance_vectors (pb, ddr);
3936
3937 return true;
3938 }
3939
3940 /* Sets up the Omega dependence problem for the data dependence
3941 relation DDR. Returns false when the constraint system cannot be
3942 built, ie. when the test answers "don't know". Returns true
3943 otherwise, and when independence has been proved (using one of the
3944 trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3945 set MAYBE_DEPENDENT to true.
3946
3947 Example: for setting up the dependence system corresponding to the
3948 conflicting accesses
3949
3950 | loop_i
3951 | loop_j
3952 | A[i, i+1] = ...
3953 | ... A[2*j, 2*(i + j)]
3954 | endloop_j
3955 | endloop_i
3956
3957 the following constraints come from the iteration domain:
3958
3959 0 <= i <= Ni
3960 0 <= i + di <= Ni
3961 0 <= j <= Nj
3962 0 <= j + dj <= Nj
3963
3964 where di, dj are the distance variables. The constraints
3965 representing the conflicting elements are:
3966
3967 i = 2 * (j + dj)
3968 i + 1 = 2 * (i + di + j + dj)
3969
3970 For asking that the resulting distance vector (di, dj) be
3971 lexicographically positive, we insert the constraint "di >= 0". If
3972 "di = 0" in the solution, we fix that component to zero, and we
3973 look at the inner loops: we set a new problem where all the outer
3974 loop distances are zero, and fix this inner component to be
3975 positive. When one of the components is positive, we save that
3976 distance, and set a new problem where the distance on this loop is
3977 zero, searching for other distances in the inner loops. Here is
3978 the classic example that illustrates that we have to set for each
3979 inner loop a new problem:
3980
3981 | loop_1
3982 | loop_2
3983 | A[10]
3984 | endloop_2
3985 | endloop_1
3986
3987 we have to save two distances (1, 0) and (0, 1).
3988
3989 Given two array references, refA and refB, we have to set the
3990 dependence problem twice, refA vs. refB and refB vs. refA, and we
3991 cannot do a single test, as refB might occur before refA in the
3992 inner loops, and the contrary when considering outer loops: ex.
3993
3994 | loop_0
3995 | loop_1
3996 | loop_2
3997 | T[{1,+,1}_2][{1,+,1}_1] // refA
3998 | T[{2,+,1}_2][{0,+,1}_1] // refB
3999 | endloop_2
4000 | endloop_1
4001 | endloop_0
4002
4003 refB touches the elements in T before refA, and thus for the same
4004 loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
4005 but for successive loop_0 iterations, we have (1, -1, 1)
4006
4007 The Omega solver expects the distance variables ("di" in the
4008 previous example) to come first in the constraint system (as
4009 variables to be protected, or "safe" variables), the constraint
4010 system is built using the following layout:
4011
4012 "cst | distance vars | index vars".
4013 */
4014
4015 static bool
init_omega_for_ddr(struct data_dependence_relation * ddr,bool * maybe_dependent)4016 init_omega_for_ddr (struct data_dependence_relation *ddr,
4017 bool *maybe_dependent)
4018 {
4019 omega_pb pb;
4020 bool res = false;
4021
4022 *maybe_dependent = true;
4023
4024 if (same_access_functions (ddr))
4025 {
4026 unsigned j;
4027 lambda_vector dir_v;
4028
4029 /* Save the 0 vector. */
4030 save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4031 dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4032 for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4033 dir_v[j] = dir_equal;
4034 save_dir_v (ddr, dir_v);
4035
4036 /* Save the dependences carried by outer loops. */
4037 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4038 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4039 maybe_dependent);
4040 omega_free_problem (pb);
4041 return res;
4042 }
4043
4044 /* Omega expects the protected variables (those that have to be kept
4045 after elimination) to appear first in the constraint system.
4046 These variables are the distance variables. In the following
4047 initialization we declare NB_LOOPS safe variables, and the total
4048 number of variables for the constraint system is 2*NB_LOOPS. */
4049 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4050 res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
4051 maybe_dependent);
4052 omega_free_problem (pb);
4053
4054 /* Stop computation if not decidable, or no dependence. */
4055 if (res == false || *maybe_dependent == false)
4056 return res;
4057
4058 pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
4059 res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
4060 maybe_dependent);
4061 omega_free_problem (pb);
4062
4063 return res;
4064 }
4065
4066 /* Return true when DDR contains the same information as that stored
4067 in DIR_VECTS and in DIST_VECTS, return false otherwise. */
4068
4069 static bool
ddr_consistent_p(FILE * file,struct data_dependence_relation * ddr,VEC (lambda_vector,heap)* dist_vects,VEC (lambda_vector,heap)* dir_vects)4070 ddr_consistent_p (FILE *file,
4071 struct data_dependence_relation *ddr,
4072 VEC (lambda_vector, heap) *dist_vects,
4073 VEC (lambda_vector, heap) *dir_vects)
4074 {
4075 unsigned int i, j;
4076
4077 /* If dump_file is set, output there. */
4078 if (dump_file && (dump_flags & TDF_DETAILS))
4079 file = dump_file;
4080
4081 if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
4082 {
4083 lambda_vector b_dist_v;
4084 fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
4085 VEC_length (lambda_vector, dist_vects),
4086 DDR_NUM_DIST_VECTS (ddr));
4087
4088 fprintf (file, "Banerjee dist vectors:\n");
4089 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, i, b_dist_v)
4090 print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
4091
4092 fprintf (file, "Omega dist vectors:\n");
4093 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4094 print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
4095
4096 fprintf (file, "data dependence relation:\n");
4097 dump_data_dependence_relation (file, ddr);
4098
4099 fprintf (file, ")\n");
4100 return false;
4101 }
4102
4103 if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
4104 {
4105 fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
4106 VEC_length (lambda_vector, dir_vects),
4107 DDR_NUM_DIR_VECTS (ddr));
4108 return false;
4109 }
4110
4111 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
4112 {
4113 lambda_vector a_dist_v;
4114 lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
4115
4116 /* Distance vectors are not ordered in the same way in the DDR
4117 and in the DIST_VECTS: search for a matching vector. */
4118 FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, a_dist_v)
4119 if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
4120 break;
4121
4122 if (j == VEC_length (lambda_vector, dist_vects))
4123 {
4124 fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
4125 print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
4126 fprintf (file, "not found in Omega dist vectors:\n");
4127 print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
4128 fprintf (file, "data dependence relation:\n");
4129 dump_data_dependence_relation (file, ddr);
4130 fprintf (file, ")\n");
4131 }
4132 }
4133
4134 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
4135 {
4136 lambda_vector a_dir_v;
4137 lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
4138
4139 /* Direction vectors are not ordered in the same way in the DDR
4140 and in the DIR_VECTS: search for a matching vector. */
4141 FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, a_dir_v)
4142 if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
4143 break;
4144
4145 if (j == VEC_length (lambda_vector, dist_vects))
4146 {
4147 fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
4148 print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
4149 fprintf (file, "not found in Omega dir vectors:\n");
4150 print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
4151 fprintf (file, "data dependence relation:\n");
4152 dump_data_dependence_relation (file, ddr);
4153 fprintf (file, ")\n");
4154 }
4155 }
4156
4157 return true;
4158 }
4159
4160 /* This computes the affine dependence relation between A and B with
4161 respect to LOOP_NEST. CHREC_KNOWN is used for representing the
4162 independence between two accesses, while CHREC_DONT_KNOW is used
4163 for representing the unknown relation.
4164
4165 Note that it is possible to stop the computation of the dependence
4166 relation the first time we detect a CHREC_KNOWN element for a given
4167 subscript. */
4168
4169 static void
compute_affine_dependence(struct data_dependence_relation * ddr,struct loop * loop_nest)4170 compute_affine_dependence (struct data_dependence_relation *ddr,
4171 struct loop *loop_nest)
4172 {
4173 struct data_reference *dra = DDR_A (ddr);
4174 struct data_reference *drb = DDR_B (ddr);
4175
4176 if (dump_file && (dump_flags & TDF_DETAILS))
4177 {
4178 fprintf (dump_file, "(compute_affine_dependence\n");
4179 fprintf (dump_file, " stmt_a: ");
4180 print_gimple_stmt (dump_file, DR_STMT (dra), 0, TDF_SLIM);
4181 fprintf (dump_file, " stmt_b: ");
4182 print_gimple_stmt (dump_file, DR_STMT (drb), 0, TDF_SLIM);
4183 }
4184
4185 /* Analyze only when the dependence relation is not yet known. */
4186 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4187 {
4188 dependence_stats.num_dependence_tests++;
4189
4190 if (access_functions_are_affine_or_constant_p (dra, loop_nest)
4191 && access_functions_are_affine_or_constant_p (drb, loop_nest))
4192 {
4193 if (flag_check_data_deps)
4194 {
4195 /* Compute the dependences using the first algorithm. */
4196 subscript_dependence_tester (ddr, loop_nest);
4197
4198 if (dump_file && (dump_flags & TDF_DETAILS))
4199 {
4200 fprintf (dump_file, "\n\nBanerjee Analyzer\n");
4201 dump_data_dependence_relation (dump_file, ddr);
4202 }
4203
4204 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4205 {
4206 bool maybe_dependent;
4207 VEC (lambda_vector, heap) *dir_vects, *dist_vects;
4208
4209 /* Save the result of the first DD analyzer. */
4210 dist_vects = DDR_DIST_VECTS (ddr);
4211 dir_vects = DDR_DIR_VECTS (ddr);
4212
4213 /* Reset the information. */
4214 DDR_DIST_VECTS (ddr) = NULL;
4215 DDR_DIR_VECTS (ddr) = NULL;
4216
4217 /* Compute the same information using Omega. */
4218 if (!init_omega_for_ddr (ddr, &maybe_dependent))
4219 goto csys_dont_know;
4220
4221 if (dump_file && (dump_flags & TDF_DETAILS))
4222 {
4223 fprintf (dump_file, "Omega Analyzer\n");
4224 dump_data_dependence_relation (dump_file, ddr);
4225 }
4226
4227 /* Check that we get the same information. */
4228 if (maybe_dependent)
4229 gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
4230 dir_vects));
4231 }
4232 }
4233 else
4234 subscript_dependence_tester (ddr, loop_nest);
4235 }
4236
4237 /* As a last case, if the dependence cannot be determined, or if
4238 the dependence is considered too difficult to determine, answer
4239 "don't know". */
4240 else
4241 {
4242 csys_dont_know:;
4243 dependence_stats.num_dependence_undetermined++;
4244
4245 if (dump_file && (dump_flags & TDF_DETAILS))
4246 {
4247 fprintf (dump_file, "Data ref a:\n");
4248 dump_data_reference (dump_file, dra);
4249 fprintf (dump_file, "Data ref b:\n");
4250 dump_data_reference (dump_file, drb);
4251 fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4252 }
4253 finalize_ddr_dependent (ddr, chrec_dont_know);
4254 }
4255 }
4256
4257 if (dump_file && (dump_flags & TDF_DETAILS))
4258 {
4259 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4260 fprintf (dump_file, ") -> no dependence\n");
4261 else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4262 fprintf (dump_file, ") -> dependence analysis failed\n");
4263 else
4264 fprintf (dump_file, ")\n");
4265 }
4266 }
4267
4268 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4269 the data references in DATAREFS, in the LOOP_NEST. When
4270 COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4271 relations. Return true when successful, i.e. data references number
4272 is small enough to be handled. */
4273
4274 bool
compute_all_dependences(VEC (data_reference_p,heap)* datarefs,VEC (ddr_p,heap)** dependence_relations,VEC (loop_p,heap)* loop_nest,bool compute_self_and_rr)4275 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
4276 VEC (ddr_p, heap) **dependence_relations,
4277 VEC (loop_p, heap) *loop_nest,
4278 bool compute_self_and_rr)
4279 {
4280 struct data_dependence_relation *ddr;
4281 struct data_reference *a, *b;
4282 unsigned int i, j;
4283
4284 if ((int) VEC_length (data_reference_p, datarefs)
4285 > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
4286 {
4287 struct data_dependence_relation *ddr;
4288
4289 /* Insert a single relation into dependence_relations:
4290 chrec_dont_know. */
4291 ddr = initialize_data_dependence_relation (NULL, NULL, loop_nest);
4292 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4293 return false;
4294 }
4295
4296 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
4297 for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4298 if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
4299 {
4300 ddr = initialize_data_dependence_relation (a, b, loop_nest);
4301 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4302 if (loop_nest)
4303 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4304 }
4305
4306 if (compute_self_and_rr)
4307 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
4308 {
4309 ddr = initialize_data_dependence_relation (a, a, loop_nest);
4310 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4311 if (loop_nest)
4312 compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4313 }
4314
4315 return true;
4316 }
4317
4318 /* Stores the locations of memory references in STMT to REFERENCES. Returns
4319 true if STMT clobbers memory, false otherwise. */
4320
4321 bool
get_references_in_stmt(gimple stmt,VEC (data_ref_loc,heap)** references)4322 get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
4323 {
4324 bool clobbers_memory = false;
4325 data_ref_loc *ref;
4326 tree *op0, *op1;
4327 enum gimple_code stmt_code = gimple_code (stmt);
4328
4329 *references = NULL;
4330
4331 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4332 Calls have side-effects, except those to const or pure
4333 functions. */
4334 if ((stmt_code == GIMPLE_CALL
4335 && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
4336 || (stmt_code == GIMPLE_ASM
4337 && (gimple_asm_volatile_p (stmt) || gimple_vuse (stmt))))
4338 clobbers_memory = true;
4339
4340 if (!gimple_vuse (stmt))
4341 return clobbers_memory;
4342
4343 if (stmt_code == GIMPLE_ASSIGN)
4344 {
4345 tree base;
4346 op0 = gimple_assign_lhs_ptr (stmt);
4347 op1 = gimple_assign_rhs1_ptr (stmt);
4348
4349 if (DECL_P (*op1)
4350 || (REFERENCE_CLASS_P (*op1)
4351 && (base = get_base_address (*op1))
4352 && TREE_CODE (base) != SSA_NAME))
4353 {
4354 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4355 ref->pos = op1;
4356 ref->is_read = true;
4357 }
4358 }
4359 else if (stmt_code == GIMPLE_CALL)
4360 {
4361 unsigned i, n;
4362
4363 op0 = gimple_call_lhs_ptr (stmt);
4364 n = gimple_call_num_args (stmt);
4365 for (i = 0; i < n; i++)
4366 {
4367 op1 = gimple_call_arg_ptr (stmt, i);
4368
4369 if (DECL_P (*op1)
4370 || (REFERENCE_CLASS_P (*op1) && get_base_address (*op1)))
4371 {
4372 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4373 ref->pos = op1;
4374 ref->is_read = true;
4375 }
4376 }
4377 }
4378 else
4379 return clobbers_memory;
4380
4381 if (*op0
4382 && (DECL_P (*op0)
4383 || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0))))
4384 {
4385 ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4386 ref->pos = op0;
4387 ref->is_read = false;
4388 }
4389 return clobbers_memory;
4390 }
4391
4392 /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
4393 reference, returns false, otherwise returns true. NEST is the outermost
4394 loop of the loop nest in which the references should be analyzed. */
4395
4396 bool
find_data_references_in_stmt(struct loop * nest,gimple stmt,VEC (data_reference_p,heap)** datarefs)4397 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4398 VEC (data_reference_p, heap) **datarefs)
4399 {
4400 unsigned i;
4401 VEC (data_ref_loc, heap) *references;
4402 data_ref_loc *ref;
4403 bool ret = true;
4404 data_reference_p dr;
4405
4406 if (get_references_in_stmt (stmt, &references))
4407 {
4408 VEC_free (data_ref_loc, heap, references);
4409 return false;
4410 }
4411
4412 FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4413 {
4414 dr = create_data_ref (nest, loop_containing_stmt (stmt),
4415 *ref->pos, stmt, ref->is_read);
4416 gcc_assert (dr != NULL);
4417 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4418 }
4419 VEC_free (data_ref_loc, heap, references);
4420 return ret;
4421 }
4422
4423 /* Stores the data references in STMT to DATAREFS. If there is an
4424 unanalyzable reference, returns false, otherwise returns true.
4425 NEST is the outermost loop of the loop nest in which the references
4426 should be instantiated, LOOP is the loop in which the references
4427 should be analyzed. */
4428
4429 bool
graphite_find_data_references_in_stmt(loop_p nest,loop_p loop,gimple stmt,VEC (data_reference_p,heap)** datarefs)4430 graphite_find_data_references_in_stmt (loop_p nest, loop_p loop, gimple stmt,
4431 VEC (data_reference_p, heap) **datarefs)
4432 {
4433 unsigned i;
4434 VEC (data_ref_loc, heap) *references;
4435 data_ref_loc *ref;
4436 bool ret = true;
4437 data_reference_p dr;
4438
4439 if (get_references_in_stmt (stmt, &references))
4440 {
4441 VEC_free (data_ref_loc, heap, references);
4442 return false;
4443 }
4444
4445 FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4446 {
4447 dr = create_data_ref (nest, loop, *ref->pos, stmt, ref->is_read);
4448 gcc_assert (dr != NULL);
4449 VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4450 }
4451
4452 VEC_free (data_ref_loc, heap, references);
4453 return ret;
4454 }
4455
4456 /* Search the data references in LOOP, and record the information into
4457 DATAREFS. Returns chrec_dont_know when failing to analyze a
4458 difficult case, returns NULL_TREE otherwise. */
4459
4460 tree
find_data_references_in_bb(struct loop * loop,basic_block bb,VEC (data_reference_p,heap)** datarefs)4461 find_data_references_in_bb (struct loop *loop, basic_block bb,
4462 VEC (data_reference_p, heap) **datarefs)
4463 {
4464 gimple_stmt_iterator bsi;
4465
4466 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4467 {
4468 gimple stmt = gsi_stmt (bsi);
4469
4470 if (!find_data_references_in_stmt (loop, stmt, datarefs))
4471 {
4472 struct data_reference *res;
4473 res = XCNEW (struct data_reference);
4474 VEC_safe_push (data_reference_p, heap, *datarefs, res);
4475
4476 return chrec_dont_know;
4477 }
4478 }
4479
4480 return NULL_TREE;
4481 }
4482
4483 /* Search the data references in LOOP, and record the information into
4484 DATAREFS. Returns chrec_dont_know when failing to analyze a
4485 difficult case, returns NULL_TREE otherwise.
4486
4487 TODO: This function should be made smarter so that it can handle address
4488 arithmetic as if they were array accesses, etc. */
4489
4490 static tree
find_data_references_in_loop(struct loop * loop,VEC (data_reference_p,heap)** datarefs)4491 find_data_references_in_loop (struct loop *loop,
4492 VEC (data_reference_p, heap) **datarefs)
4493 {
4494 basic_block bb, *bbs;
4495 unsigned int i;
4496
4497 bbs = get_loop_body_in_dom_order (loop);
4498
4499 for (i = 0; i < loop->num_nodes; i++)
4500 {
4501 bb = bbs[i];
4502
4503 if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
4504 {
4505 free (bbs);
4506 return chrec_dont_know;
4507 }
4508 }
4509 free (bbs);
4510
4511 return NULL_TREE;
4512 }
4513
4514 /* Recursive helper function. */
4515
4516 static bool
find_loop_nest_1(struct loop * loop,VEC (loop_p,heap)** loop_nest)4517 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4518 {
4519 /* Inner loops of the nest should not contain siblings. Example:
4520 when there are two consecutive loops,
4521
4522 | loop_0
4523 | loop_1
4524 | A[{0, +, 1}_1]
4525 | endloop_1
4526 | loop_2
4527 | A[{0, +, 1}_2]
4528 | endloop_2
4529 | endloop_0
4530
4531 the dependence relation cannot be captured by the distance
4532 abstraction. */
4533 if (loop->next)
4534 return false;
4535
4536 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4537 if (loop->inner)
4538 return find_loop_nest_1 (loop->inner, loop_nest);
4539 return true;
4540 }
4541
4542 /* Return false when the LOOP is not well nested. Otherwise return
4543 true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will
4544 contain the loops from the outermost to the innermost, as they will
4545 appear in the classic distance vector. */
4546
4547 bool
find_loop_nest(struct loop * loop,VEC (loop_p,heap)** loop_nest)4548 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4549 {
4550 VEC_safe_push (loop_p, heap, *loop_nest, loop);
4551 if (loop->inner)
4552 return find_loop_nest_1 (loop->inner, loop_nest);
4553 return true;
4554 }
4555
4556 /* Returns true when the data dependences have been computed, false otherwise.
4557 Given a loop nest LOOP, the following vectors are returned:
4558 DATAREFS is initialized to all the array elements contained in this loop,
4559 DEPENDENCE_RELATIONS contains the relations between the data references.
4560 Compute read-read and self relations if
4561 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4562
4563 bool
compute_data_dependences_for_loop(struct loop * loop,bool compute_self_and_read_read_dependences,VEC (loop_p,heap)** loop_nest,VEC (data_reference_p,heap)** datarefs,VEC (ddr_p,heap)** dependence_relations)4564 compute_data_dependences_for_loop (struct loop *loop,
4565 bool compute_self_and_read_read_dependences,
4566 VEC (loop_p, heap) **loop_nest,
4567 VEC (data_reference_p, heap) **datarefs,
4568 VEC (ddr_p, heap) **dependence_relations)
4569 {
4570 bool res = true;
4571
4572 memset (&dependence_stats, 0, sizeof (dependence_stats));
4573
4574 /* If the loop nest is not well formed, or one of the data references
4575 is not computable, give up without spending time to compute other
4576 dependences. */
4577 if (!loop
4578 || !find_loop_nest (loop, loop_nest)
4579 || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
4580 || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
4581 compute_self_and_read_read_dependences))
4582 res = false;
4583
4584 if (dump_file && (dump_flags & TDF_STATS))
4585 {
4586 fprintf (dump_file, "Dependence tester statistics:\n");
4587
4588 fprintf (dump_file, "Number of dependence tests: %d\n",
4589 dependence_stats.num_dependence_tests);
4590 fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4591 dependence_stats.num_dependence_dependent);
4592 fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4593 dependence_stats.num_dependence_independent);
4594 fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4595 dependence_stats.num_dependence_undetermined);
4596
4597 fprintf (dump_file, "Number of subscript tests: %d\n",
4598 dependence_stats.num_subscript_tests);
4599 fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4600 dependence_stats.num_subscript_undetermined);
4601 fprintf (dump_file, "Number of same subscript function: %d\n",
4602 dependence_stats.num_same_subscript_function);
4603
4604 fprintf (dump_file, "Number of ziv tests: %d\n",
4605 dependence_stats.num_ziv);
4606 fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4607 dependence_stats.num_ziv_dependent);
4608 fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4609 dependence_stats.num_ziv_independent);
4610 fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4611 dependence_stats.num_ziv_unimplemented);
4612
4613 fprintf (dump_file, "Number of siv tests: %d\n",
4614 dependence_stats.num_siv);
4615 fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4616 dependence_stats.num_siv_dependent);
4617 fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4618 dependence_stats.num_siv_independent);
4619 fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4620 dependence_stats.num_siv_unimplemented);
4621
4622 fprintf (dump_file, "Number of miv tests: %d\n",
4623 dependence_stats.num_miv);
4624 fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4625 dependence_stats.num_miv_dependent);
4626 fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4627 dependence_stats.num_miv_independent);
4628 fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4629 dependence_stats.num_miv_unimplemented);
4630 }
4631
4632 return res;
4633 }
4634
4635 /* Returns true when the data dependences for the basic block BB have been
4636 computed, false otherwise.
4637 DATAREFS is initialized to all the array elements contained in this basic
4638 block, DEPENDENCE_RELATIONS contains the relations between the data
4639 references. Compute read-read and self relations if
4640 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */
4641 bool
compute_data_dependences_for_bb(basic_block bb,bool compute_self_and_read_read_dependences,VEC (data_reference_p,heap)** datarefs,VEC (ddr_p,heap)** dependence_relations)4642 compute_data_dependences_for_bb (basic_block bb,
4643 bool compute_self_and_read_read_dependences,
4644 VEC (data_reference_p, heap) **datarefs,
4645 VEC (ddr_p, heap) **dependence_relations)
4646 {
4647 if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
4648 return false;
4649
4650 return compute_all_dependences (*datarefs, dependence_relations, NULL,
4651 compute_self_and_read_read_dependences);
4652 }
4653
4654 /* Entry point (for testing only). Analyze all the data references
4655 and the dependence relations in LOOP.
4656
4657 The data references are computed first.
4658
4659 A relation on these nodes is represented by a complete graph. Some
4660 of the relations could be of no interest, thus the relations can be
4661 computed on demand.
4662
4663 In the following function we compute all the relations. This is
4664 just a first implementation that is here for:
4665 - for showing how to ask for the dependence relations,
4666 - for the debugging the whole dependence graph,
4667 - for the dejagnu testcases and maintenance.
4668
4669 It is possible to ask only for a part of the graph, avoiding to
4670 compute the whole dependence graph. The computed dependences are
4671 stored in a knowledge base (KB) such that later queries don't
4672 recompute the same information. The implementation of this KB is
4673 transparent to the optimizer, and thus the KB can be changed with a
4674 more efficient implementation, or the KB could be disabled. */
4675 static void
analyze_all_data_dependences(struct loop * loop)4676 analyze_all_data_dependences (struct loop *loop)
4677 {
4678 unsigned int i;
4679 int nb_data_refs = 10;
4680 VEC (data_reference_p, heap) *datarefs =
4681 VEC_alloc (data_reference_p, heap, nb_data_refs);
4682 VEC (ddr_p, heap) *dependence_relations =
4683 VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4684 VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3);
4685
4686 /* Compute DDs on the whole function. */
4687 compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
4688 &dependence_relations);
4689
4690 if (dump_file)
4691 {
4692 dump_data_dependence_relations (dump_file, dependence_relations);
4693 fprintf (dump_file, "\n\n");
4694
4695 if (dump_flags & TDF_DETAILS)
4696 dump_dist_dir_vectors (dump_file, dependence_relations);
4697
4698 if (dump_flags & TDF_STATS)
4699 {
4700 unsigned nb_top_relations = 0;
4701 unsigned nb_bot_relations = 0;
4702 unsigned nb_chrec_relations = 0;
4703 struct data_dependence_relation *ddr;
4704
4705 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4706 {
4707 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4708 nb_top_relations++;
4709
4710 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4711 nb_bot_relations++;
4712
4713 else
4714 nb_chrec_relations++;
4715 }
4716
4717 gather_stats_on_scev_database ();
4718 }
4719 }
4720
4721 VEC_free (loop_p, heap, loop_nest);
4722 free_dependence_relations (dependence_relations);
4723 free_data_refs (datarefs);
4724 }
4725
4726 /* Computes all the data dependences and check that the results of
4727 several analyzers are the same. */
4728
4729 void
tree_check_data_deps(void)4730 tree_check_data_deps (void)
4731 {
4732 loop_iterator li;
4733 struct loop *loop_nest;
4734
4735 FOR_EACH_LOOP (li, loop_nest, 0)
4736 analyze_all_data_dependences (loop_nest);
4737 }
4738
4739 /* Free the memory used by a data dependence relation DDR. */
4740
4741 void
free_dependence_relation(struct data_dependence_relation * ddr)4742 free_dependence_relation (struct data_dependence_relation *ddr)
4743 {
4744 if (ddr == NULL)
4745 return;
4746
4747 if (DDR_SUBSCRIPTS (ddr))
4748 free_subscripts (DDR_SUBSCRIPTS (ddr));
4749 if (DDR_DIST_VECTS (ddr))
4750 VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4751 if (DDR_DIR_VECTS (ddr))
4752 VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4753
4754 free (ddr);
4755 }
4756
4757 /* Free the memory used by the data dependence relations from
4758 DEPENDENCE_RELATIONS. */
4759
4760 void
free_dependence_relations(VEC (ddr_p,heap)* dependence_relations)4761 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4762 {
4763 unsigned int i;
4764 struct data_dependence_relation *ddr;
4765
4766 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4767 if (ddr)
4768 free_dependence_relation (ddr);
4769
4770 VEC_free (ddr_p, heap, dependence_relations);
4771 }
4772
4773 /* Free the memory used by the data references from DATAREFS. */
4774
4775 void
free_data_refs(VEC (data_reference_p,heap)* datarefs)4776 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4777 {
4778 unsigned int i;
4779 struct data_reference *dr;
4780
4781 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
4782 free_data_ref (dr);
4783 VEC_free (data_reference_p, heap, datarefs);
4784 }
4785
4786
4787
4788 /* Dump vertex I in RDG to FILE. */
4789
4790 void
dump_rdg_vertex(FILE * file,struct graph * rdg,int i)4791 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4792 {
4793 struct vertex *v = &(rdg->vertices[i]);
4794 struct graph_edge *e;
4795
4796 fprintf (file, "(vertex %d: (%s%s) (in:", i,
4797 RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4798 RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4799
4800 if (v->pred)
4801 for (e = v->pred; e; e = e->pred_next)
4802 fprintf (file, " %d", e->src);
4803
4804 fprintf (file, ") (out:");
4805
4806 if (v->succ)
4807 for (e = v->succ; e; e = e->succ_next)
4808 fprintf (file, " %d", e->dest);
4809
4810 fprintf (file, ")\n");
4811 print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
4812 fprintf (file, ")\n");
4813 }
4814
4815 /* Call dump_rdg_vertex on stderr. */
4816
4817 DEBUG_FUNCTION void
debug_rdg_vertex(struct graph * rdg,int i)4818 debug_rdg_vertex (struct graph *rdg, int i)
4819 {
4820 dump_rdg_vertex (stderr, rdg, i);
4821 }
4822
4823 /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
4824 dumped vertices to that bitmap. */
4825
dump_rdg_component(FILE * file,struct graph * rdg,int c,bitmap dumped)4826 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4827 {
4828 int i;
4829
4830 fprintf (file, "(%d\n", c);
4831
4832 for (i = 0; i < rdg->n_vertices; i++)
4833 if (rdg->vertices[i].component == c)
4834 {
4835 if (dumped)
4836 bitmap_set_bit (dumped, i);
4837
4838 dump_rdg_vertex (file, rdg, i);
4839 }
4840
4841 fprintf (file, ")\n");
4842 }
4843
4844 /* Call dump_rdg_vertex on stderr. */
4845
4846 DEBUG_FUNCTION void
debug_rdg_component(struct graph * rdg,int c)4847 debug_rdg_component (struct graph *rdg, int c)
4848 {
4849 dump_rdg_component (stderr, rdg, c, NULL);
4850 }
4851
4852 /* Dump the reduced dependence graph RDG to FILE. */
4853
4854 void
dump_rdg(FILE * file,struct graph * rdg)4855 dump_rdg (FILE *file, struct graph *rdg)
4856 {
4857 int i;
4858 bitmap dumped = BITMAP_ALLOC (NULL);
4859
4860 fprintf (file, "(rdg\n");
4861
4862 for (i = 0; i < rdg->n_vertices; i++)
4863 if (!bitmap_bit_p (dumped, i))
4864 dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4865
4866 fprintf (file, ")\n");
4867 BITMAP_FREE (dumped);
4868 }
4869
4870 /* Call dump_rdg on stderr. */
4871
4872 DEBUG_FUNCTION void
debug_rdg(struct graph * rdg)4873 debug_rdg (struct graph *rdg)
4874 {
4875 dump_rdg (stderr, rdg);
4876 }
4877
4878 static void
dot_rdg_1(FILE * file,struct graph * rdg)4879 dot_rdg_1 (FILE *file, struct graph *rdg)
4880 {
4881 int i;
4882
4883 fprintf (file, "digraph RDG {\n");
4884
4885 for (i = 0; i < rdg->n_vertices; i++)
4886 {
4887 struct vertex *v = &(rdg->vertices[i]);
4888 struct graph_edge *e;
4889
4890 /* Highlight reads from memory. */
4891 if (RDG_MEM_READS_STMT (rdg, i))
4892 fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4893
4894 /* Highlight stores to memory. */
4895 if (RDG_MEM_WRITE_STMT (rdg, i))
4896 fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4897
4898 if (v->succ)
4899 for (e = v->succ; e; e = e->succ_next)
4900 switch (RDGE_TYPE (e))
4901 {
4902 case input_dd:
4903 fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4904 break;
4905
4906 case output_dd:
4907 fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4908 break;
4909
4910 case flow_dd:
4911 /* These are the most common dependences: don't print these. */
4912 fprintf (file, "%d -> %d \n", i, e->dest);
4913 break;
4914
4915 case anti_dd:
4916 fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4917 break;
4918
4919 default:
4920 gcc_unreachable ();
4921 }
4922 }
4923
4924 fprintf (file, "}\n\n");
4925 }
4926
4927 /* Display the Reduced Dependence Graph using dotty. */
4928 extern void dot_rdg (struct graph *);
4929
4930 DEBUG_FUNCTION void
dot_rdg(struct graph * rdg)4931 dot_rdg (struct graph *rdg)
4932 {
4933 /* When debugging, enable the following code. This cannot be used
4934 in production compilers because it calls "system". */
4935 #if 0
4936 FILE *file = fopen ("/tmp/rdg.dot", "w");
4937 gcc_assert (file != NULL);
4938
4939 dot_rdg_1 (file, rdg);
4940 fclose (file);
4941
4942 system ("dotty /tmp/rdg.dot &");
4943 #else
4944 dot_rdg_1 (stderr, rdg);
4945 #endif
4946 }
4947
4948 /* This structure is used for recording the mapping statement index in
4949 the RDG. */
4950
4951 struct GTY(()) rdg_vertex_info
4952 {
4953 gimple stmt;
4954 int index;
4955 };
4956
4957 /* Returns the index of STMT in RDG. */
4958
4959 int
rdg_vertex_for_stmt(struct graph * rdg,gimple stmt)4960 rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
4961 {
4962 struct rdg_vertex_info rvi, *slot;
4963
4964 rvi.stmt = stmt;
4965 slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4966
4967 if (!slot)
4968 return -1;
4969
4970 return slot->index;
4971 }
4972
4973 /* Creates an edge in RDG for each distance vector from DDR. The
4974 order that we keep track of in the RDG is the order in which
4975 statements have to be executed. */
4976
4977 static void
create_rdg_edge_for_ddr(struct graph * rdg,ddr_p ddr)4978 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4979 {
4980 struct graph_edge *e;
4981 int va, vb;
4982 data_reference_p dra = DDR_A (ddr);
4983 data_reference_p drb = DDR_B (ddr);
4984 unsigned level = ddr_dependence_level (ddr);
4985
4986 /* For non scalar dependences, when the dependence is REVERSED,
4987 statement B has to be executed before statement A. */
4988 if (level > 0
4989 && !DDR_REVERSED_P (ddr))
4990 {
4991 data_reference_p tmp = dra;
4992 dra = drb;
4993 drb = tmp;
4994 }
4995
4996 va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4997 vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4998
4999 if (va < 0 || vb < 0)
5000 return;
5001
5002 e = add_edge (rdg, va, vb);
5003 e->data = XNEW (struct rdg_edge);
5004
5005 RDGE_LEVEL (e) = level;
5006 RDGE_RELATION (e) = ddr;
5007
5008 /* Determines the type of the data dependence. */
5009 if (DR_IS_READ (dra) && DR_IS_READ (drb))
5010 RDGE_TYPE (e) = input_dd;
5011 else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
5012 RDGE_TYPE (e) = output_dd;
5013 else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
5014 RDGE_TYPE (e) = flow_dd;
5015 else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
5016 RDGE_TYPE (e) = anti_dd;
5017 }
5018
5019 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
5020 the index of DEF in RDG. */
5021
5022 static void
create_rdg_edges_for_scalar(struct graph * rdg,tree def,int idef)5023 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
5024 {
5025 use_operand_p imm_use_p;
5026 imm_use_iterator iterator;
5027
5028 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
5029 {
5030 struct graph_edge *e;
5031 int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
5032
5033 if (use < 0)
5034 continue;
5035
5036 e = add_edge (rdg, idef, use);
5037 e->data = XNEW (struct rdg_edge);
5038 RDGE_TYPE (e) = flow_dd;
5039 RDGE_RELATION (e) = NULL;
5040 }
5041 }
5042
5043 /* Creates the edges of the reduced dependence graph RDG. */
5044
5045 static void
create_rdg_edges(struct graph * rdg,VEC (ddr_p,heap)* ddrs)5046 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
5047 {
5048 int i;
5049 struct data_dependence_relation *ddr;
5050 def_operand_p def_p;
5051 ssa_op_iter iter;
5052
5053 FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
5054 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
5055 create_rdg_edge_for_ddr (rdg, ddr);
5056
5057 for (i = 0; i < rdg->n_vertices; i++)
5058 FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
5059 iter, SSA_OP_DEF)
5060 create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
5061 }
5062
5063 /* Build the vertices of the reduced dependence graph RDG. */
5064
5065 void
create_rdg_vertices(struct graph * rdg,VEC (gimple,heap)* stmts)5066 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
5067 {
5068 int i, j;
5069 gimple stmt;
5070
5071 FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
5072 {
5073 VEC (data_ref_loc, heap) *references;
5074 data_ref_loc *ref;
5075 struct vertex *v = &(rdg->vertices[i]);
5076 struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
5077 struct rdg_vertex_info **slot;
5078
5079 rvi->stmt = stmt;
5080 rvi->index = i;
5081 slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
5082
5083 if (!*slot)
5084 *slot = rvi;
5085 else
5086 free (rvi);
5087
5088 v->data = XNEW (struct rdg_vertex);
5089 RDG_STMT (rdg, i) = stmt;
5090
5091 RDG_MEM_WRITE_STMT (rdg, i) = false;
5092 RDG_MEM_READS_STMT (rdg, i) = false;
5093 if (gimple_code (stmt) == GIMPLE_PHI)
5094 continue;
5095
5096 get_references_in_stmt (stmt, &references);
5097 FOR_EACH_VEC_ELT (data_ref_loc, references, j, ref)
5098 if (!ref->is_read)
5099 RDG_MEM_WRITE_STMT (rdg, i) = true;
5100 else
5101 RDG_MEM_READS_STMT (rdg, i) = true;
5102
5103 VEC_free (data_ref_loc, heap, references);
5104 }
5105 }
5106
5107 /* Initialize STMTS with all the statements of LOOP. When
5108 INCLUDE_PHIS is true, include also the PHI nodes. The order in
5109 which we discover statements is important as
5110 generate_loops_for_partition is using the same traversal for
5111 identifying statements. */
5112
5113 static void
stmts_from_loop(struct loop * loop,VEC (gimple,heap)** stmts)5114 stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5115 {
5116 unsigned int i;
5117 basic_block *bbs = get_loop_body_in_dom_order (loop);
5118
5119 for (i = 0; i < loop->num_nodes; i++)
5120 {
5121 basic_block bb = bbs[i];
5122 gimple_stmt_iterator bsi;
5123 gimple stmt;
5124
5125 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5126 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
5127
5128 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5129 {
5130 stmt = gsi_stmt (bsi);
5131 if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
5132 VEC_safe_push (gimple, heap, *stmts, stmt);
5133 }
5134 }
5135
5136 free (bbs);
5137 }
5138
5139 /* Returns true when all the dependences are computable. */
5140
5141 static bool
known_dependences_p(VEC (ddr_p,heap)* dependence_relations)5142 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
5143 {
5144 ddr_p ddr;
5145 unsigned int i;
5146
5147 FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
5148 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
5149 return false;
5150
5151 return true;
5152 }
5153
5154 /* Computes a hash function for element ELT. */
5155
5156 static hashval_t
hash_stmt_vertex_info(const void * elt)5157 hash_stmt_vertex_info (const void *elt)
5158 {
5159 const struct rdg_vertex_info *const rvi =
5160 (const struct rdg_vertex_info *) elt;
5161 gimple stmt = rvi->stmt;
5162
5163 return htab_hash_pointer (stmt);
5164 }
5165
5166 /* Compares database elements E1 and E2. */
5167
5168 static int
eq_stmt_vertex_info(const void * e1,const void * e2)5169 eq_stmt_vertex_info (const void *e1, const void *e2)
5170 {
5171 const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
5172 const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
5173
5174 return elt1->stmt == elt2->stmt;
5175 }
5176
5177 /* Free the element E. */
5178
5179 static void
hash_stmt_vertex_del(void * e)5180 hash_stmt_vertex_del (void *e)
5181 {
5182 free (e);
5183 }
5184
5185 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5186 statement of the loop nest, and one edge per data dependence or
5187 scalar dependence. */
5188
5189 struct graph *
build_empty_rdg(int n_stmts)5190 build_empty_rdg (int n_stmts)
5191 {
5192 int nb_data_refs = 10;
5193 struct graph *rdg = new_graph (n_stmts);
5194
5195 rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
5196 eq_stmt_vertex_info, hash_stmt_vertex_del);
5197 return rdg;
5198 }
5199
5200 /* Build the Reduced Dependence Graph (RDG) with one vertex per
5201 statement of the loop nest, and one edge per data dependence or
5202 scalar dependence. */
5203
5204 struct graph *
build_rdg(struct loop * loop,VEC (loop_p,heap)** loop_nest,VEC (ddr_p,heap)** dependence_relations,VEC (data_reference_p,heap)** datarefs)5205 build_rdg (struct loop *loop,
5206 VEC (loop_p, heap) **loop_nest,
5207 VEC (ddr_p, heap) **dependence_relations,
5208 VEC (data_reference_p, heap) **datarefs)
5209 {
5210 struct graph *rdg = NULL;
5211
5212 if (compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
5213 dependence_relations)
5214 && known_dependences_p (*dependence_relations))
5215 {
5216 VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
5217 stmts_from_loop (loop, &stmts);
5218 rdg = build_empty_rdg (VEC_length (gimple, stmts));
5219 create_rdg_vertices (rdg, stmts);
5220 create_rdg_edges (rdg, *dependence_relations);
5221 VEC_free (gimple, heap, stmts);
5222 }
5223
5224 return rdg;
5225 }
5226
5227 /* Free the reduced dependence graph RDG. */
5228
5229 void
free_rdg(struct graph * rdg)5230 free_rdg (struct graph *rdg)
5231 {
5232 int i;
5233
5234 for (i = 0; i < rdg->n_vertices; i++)
5235 {
5236 struct vertex *v = &(rdg->vertices[i]);
5237 struct graph_edge *e;
5238
5239 for (e = v->succ; e; e = e->succ_next)
5240 free (e->data);
5241
5242 free (v->data);
5243 }
5244
5245 htab_delete (rdg->indices);
5246 free_graph (rdg);
5247 }
5248
5249 /* Initialize STMTS with all the statements of LOOP that contain a
5250 store to memory. */
5251
5252 void
stores_from_loop(struct loop * loop,VEC (gimple,heap)** stmts)5253 stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5254 {
5255 unsigned int i;
5256 basic_block *bbs = get_loop_body_in_dom_order (loop);
5257
5258 for (i = 0; i < loop->num_nodes; i++)
5259 {
5260 basic_block bb = bbs[i];
5261 gimple_stmt_iterator bsi;
5262
5263 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
5264 if (gimple_vdef (gsi_stmt (bsi)))
5265 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
5266 }
5267
5268 free (bbs);
5269 }
5270
5271 /* Returns true when the statement at STMT is of the form "A[i] = 0"
5272 that contains a data reference on its LHS with a stride of the same
5273 size as its unit type. */
5274
5275 bool
stmt_with_adjacent_zero_store_dr_p(gimple stmt)5276 stmt_with_adjacent_zero_store_dr_p (gimple stmt)
5277 {
5278 tree lhs, rhs;
5279 bool res;
5280 struct data_reference *dr;
5281
5282 if (!stmt
5283 || !gimple_vdef (stmt)
5284 || !gimple_assign_single_p (stmt))
5285 return false;
5286
5287 lhs = gimple_assign_lhs (stmt);
5288 rhs = gimple_assign_rhs1 (stmt);
5289
5290 /* If this is a bitfield store bail out. */
5291 if (TREE_CODE (lhs) == COMPONENT_REF
5292 && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
5293 return false;
5294
5295 if (!(integer_zerop (rhs) || real_zerop (rhs)))
5296 return false;
5297
5298 dr = XCNEW (struct data_reference);
5299
5300 DR_STMT (dr) = stmt;
5301 DR_REF (dr) = lhs;
5302
5303 res = dr_analyze_innermost (dr, loop_containing_stmt (stmt))
5304 && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (lhs));
5305
5306 free_data_ref (dr);
5307 return res;
5308 }
5309
5310 /* Initialize STMTS with all the statements of LOOP that contain a
5311 store to memory of the form "A[i] = 0". */
5312
5313 void
stores_zero_from_loop(struct loop * loop,VEC (gimple,heap)** stmts)5314 stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5315 {
5316 unsigned int i;
5317 basic_block bb;
5318 gimple_stmt_iterator si;
5319 gimple stmt;
5320 basic_block *bbs = get_loop_body_in_dom_order (loop);
5321
5322 for (i = 0; i < loop->num_nodes; i++)
5323 for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5324 if ((stmt = gsi_stmt (si))
5325 && stmt_with_adjacent_zero_store_dr_p (stmt))
5326 VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
5327
5328 free (bbs);
5329 }
5330
5331 /* For a data reference REF, return the declaration of its base
5332 address or NULL_TREE if the base is not determined. */
5333
5334 static inline tree
ref_base_address(gimple stmt,data_ref_loc * ref)5335 ref_base_address (gimple stmt, data_ref_loc *ref)
5336 {
5337 tree base = NULL_TREE;
5338 tree base_address;
5339 struct data_reference *dr = XCNEW (struct data_reference);
5340
5341 DR_STMT (dr) = stmt;
5342 DR_REF (dr) = *ref->pos;
5343 dr_analyze_innermost (dr, loop_containing_stmt (stmt));
5344 base_address = DR_BASE_ADDRESS (dr);
5345
5346 if (!base_address)
5347 goto end;
5348
5349 switch (TREE_CODE (base_address))
5350 {
5351 case ADDR_EXPR:
5352 base = TREE_OPERAND (base_address, 0);
5353 break;
5354
5355 default:
5356 base = base_address;
5357 break;
5358 }
5359
5360 end:
5361 free_data_ref (dr);
5362 return base;
5363 }
5364
5365 /* Determines whether the statement from vertex V of the RDG has a
5366 definition used outside the loop that contains this statement. */
5367
5368 bool
rdg_defs_used_in_other_loops_p(struct graph * rdg,int v)5369 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
5370 {
5371 gimple stmt = RDG_STMT (rdg, v);
5372 struct loop *loop = loop_containing_stmt (stmt);
5373 use_operand_p imm_use_p;
5374 imm_use_iterator iterator;
5375 ssa_op_iter it;
5376 def_operand_p def_p;
5377
5378 if (!loop)
5379 return true;
5380
5381 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
5382 {
5383 FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
5384 {
5385 if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
5386 return true;
5387 }
5388 }
5389
5390 return false;
5391 }
5392
5393 /* Determines whether statements S1 and S2 access to similar memory
5394 locations. Two memory accesses are considered similar when they
5395 have the same base address declaration, i.e. when their
5396 ref_base_address is the same. */
5397
5398 bool
have_similar_memory_accesses(gimple s1,gimple s2)5399 have_similar_memory_accesses (gimple s1, gimple s2)
5400 {
5401 bool res = false;
5402 unsigned i, j;
5403 VEC (data_ref_loc, heap) *refs1, *refs2;
5404 data_ref_loc *ref1, *ref2;
5405
5406 get_references_in_stmt (s1, &refs1);
5407 get_references_in_stmt (s2, &refs2);
5408
5409 FOR_EACH_VEC_ELT (data_ref_loc, refs1, i, ref1)
5410 {
5411 tree base1 = ref_base_address (s1, ref1);
5412
5413 if (base1)
5414 FOR_EACH_VEC_ELT (data_ref_loc, refs2, j, ref2)
5415 if (base1 == ref_base_address (s2, ref2))
5416 {
5417 res = true;
5418 goto end;
5419 }
5420 }
5421
5422 end:
5423 VEC_free (data_ref_loc, heap, refs1);
5424 VEC_free (data_ref_loc, heap, refs2);
5425 return res;
5426 }
5427
5428 /* Helper function for the hashtab. */
5429
5430 static int
have_similar_memory_accesses_1(const void * s1,const void * s2)5431 have_similar_memory_accesses_1 (const void *s1, const void *s2)
5432 {
5433 return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
5434 CONST_CAST_GIMPLE ((const_gimple) s2));
5435 }
5436
5437 /* Helper function for the hashtab. */
5438
5439 static hashval_t
ref_base_address_1(const void * s)5440 ref_base_address_1 (const void *s)
5441 {
5442 gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
5443 unsigned i;
5444 VEC (data_ref_loc, heap) *refs;
5445 data_ref_loc *ref;
5446 hashval_t res = 0;
5447
5448 get_references_in_stmt (stmt, &refs);
5449
5450 FOR_EACH_VEC_ELT (data_ref_loc, refs, i, ref)
5451 if (!ref->is_read)
5452 {
5453 res = htab_hash_pointer (ref_base_address (stmt, ref));
5454 break;
5455 }
5456
5457 VEC_free (data_ref_loc, heap, refs);
5458 return res;
5459 }
5460
5461 /* Try to remove duplicated write data references from STMTS. */
5462
5463 void
remove_similar_memory_refs(VEC (gimple,heap)** stmts)5464 remove_similar_memory_refs (VEC (gimple, heap) **stmts)
5465 {
5466 unsigned i;
5467 gimple stmt;
5468 htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
5469 have_similar_memory_accesses_1, NULL);
5470
5471 for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
5472 {
5473 void **slot;
5474
5475 slot = htab_find_slot (seen, stmt, INSERT);
5476
5477 if (*slot)
5478 VEC_ordered_remove (gimple, *stmts, i);
5479 else
5480 {
5481 *slot = (void *) stmt;
5482 i++;
5483 }
5484 }
5485
5486 htab_delete (seen);
5487 }
5488
5489 /* Returns the index of PARAMETER in the parameters vector of the
5490 ACCESS_MATRIX. If PARAMETER does not exist return -1. */
5491
5492 int
access_matrix_get_index_for_parameter(tree parameter,struct access_matrix * access_matrix)5493 access_matrix_get_index_for_parameter (tree parameter,
5494 struct access_matrix *access_matrix)
5495 {
5496 int i;
5497 VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5498 tree lambda_parameter;
5499
5500 FOR_EACH_VEC_ELT (tree, lambda_parameters, i, lambda_parameter)
5501 if (lambda_parameter == parameter)
5502 return i + AM_NB_INDUCTION_VARS (access_matrix);
5503
5504 return -1;
5505 }
5506