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