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