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