1/* Data references and dependences detectors. 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <s.pop@laposte.net> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22/* This pass walks a given loop structure searching for array 23 references. The information about the array accesses is recorded 24 in DATA_REFERENCE structures. 25 26 The basic test for determining the dependences is: 27 given two access functions chrec1 and chrec2 to a same array, and 28 x and y two vectors from the iteration domain, the same element of 29 the array is accessed twice at iterations x and y if and only if: 30 | chrec1 (x) == chrec2 (y). 31 32 The goals of this analysis are: 33 34 - to determine the independence: the relation between two 35 independent accesses is qualified with the chrec_known (this 36 information allows a loop parallelization), 37 38 - when two data references access the same data, to qualify the 39 dependence relation with classic dependence representations: 40 41 - distance vectors 42 - direction vectors 43 - loop carried level dependence 44 - polyhedron dependence 45 or with the chains of recurrences based representation, 46 47 - to define a knowledge base for storing the data dependence 48 information, 49 50 - to define an interface to access this data. 51 52 53 Definitions: 54 55 - subscript: given two array accesses a subscript is the tuple 56 composed of the access functions for a given dimension. Example: 57 Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts: 58 (f1, g1), (f2, g2), (f3, g3). 59 60 - Diophantine equation: an equation whose coefficients and 61 solutions are integer constants, for example the equation 62 | 3*x + 2*y = 1 63 has an integer solution x = 1 and y = -1. 64 65 References: 66 67 - "Advanced Compilation for High Performance Computing" by Randy 68 Allen and Ken Kennedy. 69 http://citeseer.ist.psu.edu/goff91practical.html 70 71 - "Loop Transformations for Restructuring Compilers - The Foundations" 72 by Utpal Banerjee. 73 74 75*/ 76 77#include "config.h" 78#include "system.h" 79#include "coretypes.h" 80#include "tm.h" 81#include "ggc.h" 82#include "tree.h" 83 84/* These RTL headers are needed for basic-block.h. */ 85#include "rtl.h" 86#include "basic-block.h" 87#include "diagnostic.h" 88#include "tree-flow.h" 89#include "tree-dump.h" 90#include "timevar.h" 91#include "cfgloop.h" 92#include "tree-chrec.h" 93#include "tree-data-ref.h" 94#include "tree-scalar-evolution.h" 95#include "tree-pass.h" 96 97static tree object_analysis (tree, tree, bool, struct data_reference **, 98 tree *, tree *, tree *, tree *, tree *, 99 struct ptr_info_def **, subvar_t *); 100static struct data_reference * init_data_ref (tree, tree, tree, tree, bool, 101 tree, tree, tree, tree, tree, 102 struct ptr_info_def *, 103 enum data_ref_type); 104 105/* Determine if PTR and DECL may alias, the result is put in ALIASED. 106 Return FALSE if there is no type memory tag for PTR. 107*/ 108static bool 109ptr_decl_may_alias_p (tree ptr, tree decl, 110 struct data_reference *ptr_dr, 111 bool *aliased) 112{ 113 tree tag; 114 115 gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl)); 116 117 tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag; 118 if (!tag) 119 tag = DR_MEMTAG (ptr_dr); 120 if (!tag) 121 return false; 122 123 *aliased = is_aliased_with (tag, decl); 124 return true; 125} 126 127 128/* Determine if two pointers may alias, the result is put in ALIASED. 129 Return FALSE if there is no type memory tag for one of the pointers. 130*/ 131static bool 132ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b, 133 struct data_reference *dra, 134 struct data_reference *drb, 135 bool *aliased) 136{ 137 tree tag_a, tag_b; 138 139 tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->type_mem_tag; 140 if (!tag_a) 141 tag_a = DR_MEMTAG (dra); 142 if (!tag_a) 143 return false; 144 tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->type_mem_tag; 145 if (!tag_b) 146 tag_b = DR_MEMTAG (drb); 147 if (!tag_b) 148 return false; 149 150 if (tag_a == tag_b) 151 *aliased = true; 152 else 153 *aliased = may_aliases_intersect (tag_a, tag_b); 154 155 return true; 156} 157 158 159/* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED. 160 Return FALSE if there is no type memory tag for one of the symbols. 161*/ 162static bool 163may_alias_p (tree base_a, tree base_b, 164 struct data_reference *dra, 165 struct data_reference *drb, 166 bool *aliased) 167{ 168 if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR) 169 { 170 if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR) 171 { 172 *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)); 173 return true; 174 } 175 if (TREE_CODE (base_a) == ADDR_EXPR) 176 return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb, 177 aliased); 178 else 179 return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra, 180 aliased); 181 } 182 183 return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased); 184} 185 186 187/* Determine if a pointer (BASE_A) and a record/union access (BASE_B) 188 are not aliased. Return TRUE if they differ. */ 189static bool 190record_ptr_differ_p (struct data_reference *dra, 191 struct data_reference *drb) 192{ 193 bool aliased; 194 tree base_a = DR_BASE_OBJECT (dra); 195 tree base_b = DR_BASE_OBJECT (drb); 196 197 if (TREE_CODE (base_b) != COMPONENT_REF) 198 return false; 199 200 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs. 201 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b. 202 Probably will be unnecessary with struct alias analysis. */ 203 while (TREE_CODE (base_b) == COMPONENT_REF) 204 base_b = TREE_OPERAND (base_b, 0); 205 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer 206 ((*q)[i]). */ 207 if (TREE_CODE (base_a) == INDIRECT_REF 208 && ((TREE_CODE (base_b) == VAR_DECL 209 && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra, 210 &aliased) 211 && !aliased)) 212 || (TREE_CODE (base_b) == INDIRECT_REF 213 && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0), 214 TREE_OPERAND (base_b, 0), dra, drb, 215 &aliased) 216 && !aliased)))) 217 return true; 218 else 219 return false; 220} 221 222 223/* Determine if an array access (BASE_A) and a record/union access (BASE_B) 224 are not aliased. Return TRUE if they differ. */ 225static bool 226record_array_differ_p (struct data_reference *dra, 227 struct data_reference *drb) 228{ 229 bool aliased; 230 tree base_a = DR_BASE_OBJECT (dra); 231 tree base_b = DR_BASE_OBJECT (drb); 232 233 if (TREE_CODE (base_b) != COMPONENT_REF) 234 return false; 235 236 /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs. 237 For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b. 238 Probably will be unnecessary with struct alias analysis. */ 239 while (TREE_CODE (base_b) == COMPONENT_REF) 240 base_b = TREE_OPERAND (base_b, 0); 241 242 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 243 (a[i]). In case of p->c[i] use alias analysis to verify that p is not 244 pointing to a. */ 245 if (TREE_CODE (base_a) == VAR_DECL 246 && (TREE_CODE (base_b) == VAR_DECL 247 || (TREE_CODE (base_b) == INDIRECT_REF 248 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, 249 &aliased) 250 && !aliased)))) 251 return true; 252 else 253 return false; 254} 255 256 257/* Determine if an array access (BASE_A) and a pointer (BASE_B) 258 are not aliased. Return TRUE if they differ. */ 259static bool 260array_ptr_differ_p (tree base_a, tree base_b, 261 struct data_reference *drb) 262{ 263 bool aliased; 264 265 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the 266 help of alias analysis that p is not pointing to a. */ 267 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF 268 && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased) 269 && !aliased)) 270 return true; 271 else 272 return false; 273} 274 275 276/* This is the simplest data dependence test: determines whether the 277 data references A and B access the same array/region. Returns 278 false when the property is not computable at compile time. 279 Otherwise return true, and DIFFER_P will record the result. This 280 utility will not be necessary when alias_sets_conflict_p will be 281 less conservative. */ 282 283static bool 284base_object_differ_p (struct data_reference *a, 285 struct data_reference *b, 286 bool *differ_p) 287{ 288 tree base_a = DR_BASE_OBJECT (a); 289 tree base_b = DR_BASE_OBJECT (b); 290 bool aliased; 291 292 if (!base_a || !base_b) 293 return false; 294 295 /* Determine if same base. Example: for the array accesses 296 a[i], b[i] or pointer accesses *a, *b, bases are a, b. */ 297 if (base_a == base_b) 298 { 299 *differ_p = false; 300 return true; 301 } 302 303 /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p) 304 and (*q) */ 305 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF 306 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)) 307 { 308 *differ_p = false; 309 return true; 310 } 311 312 /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */ 313 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF 314 && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0) 315 && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1)) 316 { 317 *differ_p = false; 318 return true; 319 } 320 321 322 /* Determine if different bases. */ 323 324 /* At this point we know that base_a != base_b. However, pointer 325 accesses of the form x=(*p) and y=(*q), whose bases are p and q, 326 may still be pointing to the same base. In SSAed GIMPLE p and q will 327 be SSA_NAMES in this case. Therefore, here we check if they are 328 really two different declarations. */ 329 if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL) 330 { 331 *differ_p = true; 332 return true; 333 } 334 335 /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the 336 help of alias analysis that p is not pointing to a. */ 337 if (array_ptr_differ_p (base_a, base_b, b) 338 || array_ptr_differ_p (base_b, base_a, a)) 339 { 340 *differ_p = true; 341 return true; 342 } 343 344 /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the 345 help of alias analysis they don't point to the same bases. */ 346 if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF 347 && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b, 348 &aliased) 349 && !aliased)) 350 { 351 *differ_p = true; 352 return true; 353 } 354 355 /* Compare two record/union bases s.a and t.b: s != t or (a != b and 356 s and t are not unions). */ 357 if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF 358 && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL 359 && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL 360 && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0)) 361 || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE 362 && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE 363 && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1)))) 364 { 365 *differ_p = true; 366 return true; 367 } 368 369 /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer 370 ((*q)[i]). */ 371 if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a)) 372 { 373 *differ_p = true; 374 return true; 375 } 376 377 /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 378 (a[i]). In case of p->c[i] use alias analysis to verify that p is not 379 pointing to a. */ 380 if (record_array_differ_p (a, b) || record_array_differ_p (b, a)) 381 { 382 *differ_p = true; 383 return true; 384 } 385 386 return false; 387} 388 389/* Function base_addr_differ_p. 390 391 This is the simplest data dependence test: determines whether the 392 data references DRA and DRB access the same array/region. Returns 393 false when the property is not computable at compile time. 394 Otherwise return true, and DIFFER_P will record the result. 395 396 The algorithm: 397 1. if (both DRA and DRB are represented as arrays) 398 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT 399 2. else if (both DRA and DRB are represented as pointers) 400 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION 401 3. else if (DRA and DRB are represented differently or 2. fails) 402 only try to prove that the bases are surely different 403*/ 404 405 406static bool 407base_addr_differ_p (struct data_reference *dra, 408 struct data_reference *drb, 409 bool *differ_p) 410{ 411 tree addr_a = DR_BASE_ADDRESS (dra); 412 tree addr_b = DR_BASE_ADDRESS (drb); 413 tree type_a, type_b; 414 bool aliased; 415 416 if (!addr_a || !addr_b) 417 return false; 418 419 type_a = TREE_TYPE (addr_a); 420 type_b = TREE_TYPE (addr_b); 421 422 gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b)); 423 424 /* 1. if (both DRA and DRB are represented as arrays) 425 compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */ 426 if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE) 427 return base_object_differ_p (dra, drb, differ_p); 428 429 430 /* 2. else if (both DRA and DRB are represented as pointers) 431 try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */ 432 /* If base addresses are the same, we check the offsets, since the access of 433 the data-ref is described by {base addr + offset} and its access function, 434 i.e., in order to decide whether the bases of data-refs are the same we 435 compare both base addresses and offsets. */ 436 if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE 437 && (addr_a == addr_b 438 || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR 439 && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0)))) 440 { 441 /* Compare offsets. */ 442 tree offset_a = DR_OFFSET (dra); 443 tree offset_b = DR_OFFSET (drb); 444 445 STRIP_NOPS (offset_a); 446 STRIP_NOPS (offset_b); 447 448 /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle 449 PLUS_EXPR. */ 450 if ((offset_a == offset_b) 451 || (TREE_CODE (offset_a) == MULT_EXPR 452 && TREE_CODE (offset_b) == MULT_EXPR 453 && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0) 454 && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1))) 455 { 456 *differ_p = false; 457 return true; 458 } 459 } 460 461 /* 3. else if (DRA and DRB are represented differently or 2. fails) 462 only try to prove that the bases are surely different. */ 463 464 /* Apply alias analysis. */ 465 if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased) 466 { 467 *differ_p = true; 468 return true; 469 } 470 471 /* An instruction writing through a restricted pointer is "independent" of any 472 instruction reading or writing through a different pointer, in the same 473 block/scope. */ 474 else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra)) 475 || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb))) 476 { 477 *differ_p = true; 478 return true; 479 } 480 return false; 481} 482 483 484/* Returns true iff A divides B. */ 485 486static inline bool 487tree_fold_divides_p (tree a, 488 tree b) 489{ 490 /* Determines whether (A == gcd (A, B)). */ 491 return tree_int_cst_equal (a, tree_fold_gcd (a, b)); 492} 493 494/* Compute the greatest common denominator of two numbers using 495 Euclid's algorithm. */ 496 497static int 498gcd (int a, int b) 499{ 500 501 int x, y, z; 502 503 x = abs (a); 504 y = abs (b); 505 506 while (x>0) 507 { 508 z = y % x; 509 y = x; 510 x = z; 511 } 512 513 return (y); 514} 515 516/* Returns true iff A divides B. */ 517 518static inline bool 519int_divides_p (int a, int b) 520{ 521 return ((b % a) == 0); 522} 523 524 525 526/* Dump into FILE all the data references from DATAREFS. */ 527 528void 529dump_data_references (FILE *file, 530 varray_type datarefs) 531{ 532 unsigned int i; 533 534 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) 535 dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i)); 536} 537 538/* Dump into FILE all the dependence relations from DDR. */ 539 540void 541dump_data_dependence_relations (FILE *file, 542 varray_type ddr) 543{ 544 unsigned int i; 545 546 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++) 547 dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i)); 548} 549 550/* Dump function for a DATA_REFERENCE structure. */ 551 552void 553dump_data_reference (FILE *outf, 554 struct data_reference *dr) 555{ 556 unsigned int i; 557 558 fprintf (outf, "(Data Ref: \n stmt: "); 559 print_generic_stmt (outf, DR_STMT (dr), 0); 560 fprintf (outf, " ref: "); 561 print_generic_stmt (outf, DR_REF (dr), 0); 562 fprintf (outf, " base_name: "); 563 print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0); 564 565 for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) 566 { 567 fprintf (outf, " Access function %d: ", i); 568 print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0); 569 } 570 fprintf (outf, ")\n"); 571} 572 573/* Dump function for a SUBSCRIPT structure. */ 574 575void 576dump_subscript (FILE *outf, struct subscript *subscript) 577{ 578 tree chrec = SUB_CONFLICTS_IN_A (subscript); 579 580 fprintf (outf, "\n (subscript \n"); 581 fprintf (outf, " iterations_that_access_an_element_twice_in_A: "); 582 print_generic_stmt (outf, chrec, 0); 583 if (chrec == chrec_known) 584 fprintf (outf, " (no dependence)\n"); 585 else if (chrec_contains_undetermined (chrec)) 586 fprintf (outf, " (don't know)\n"); 587 else 588 { 589 tree last_iteration = SUB_LAST_CONFLICT (subscript); 590 fprintf (outf, " last_conflict: "); 591 print_generic_stmt (outf, last_iteration, 0); 592 } 593 594 chrec = SUB_CONFLICTS_IN_B (subscript); 595 fprintf (outf, " iterations_that_access_an_element_twice_in_B: "); 596 print_generic_stmt (outf, chrec, 0); 597 if (chrec == chrec_known) 598 fprintf (outf, " (no dependence)\n"); 599 else if (chrec_contains_undetermined (chrec)) 600 fprintf (outf, " (don't know)\n"); 601 else 602 { 603 tree last_iteration = SUB_LAST_CONFLICT (subscript); 604 fprintf (outf, " last_conflict: "); 605 print_generic_stmt (outf, last_iteration, 0); 606 } 607 608 fprintf (outf, " (Subscript distance: "); 609 print_generic_stmt (outf, SUB_DISTANCE (subscript), 0); 610 fprintf (outf, " )\n"); 611 fprintf (outf, " )\n"); 612} 613 614/* Dump function for a DATA_DEPENDENCE_RELATION structure. */ 615 616void 617dump_data_dependence_relation (FILE *outf, 618 struct data_dependence_relation *ddr) 619{ 620 struct data_reference *dra, *drb; 621 622 dra = DDR_A (ddr); 623 drb = DDR_B (ddr); 624 fprintf (outf, "(Data Dep: \n"); 625 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) 626 fprintf (outf, " (don't know)\n"); 627 628 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) 629 fprintf (outf, " (no dependence)\n"); 630 631 else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) 632 { 633 unsigned int i; 634 635 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 636 { 637 fprintf (outf, " access_fn_A: "); 638 print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0); 639 fprintf (outf, " access_fn_B: "); 640 print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0); 641 dump_subscript (outf, DDR_SUBSCRIPT (ddr, i)); 642 } 643 644 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) 645 { 646 fprintf (outf, " distance_vector: "); 647 print_lambda_vector (outf, DDR_DIST_VECT (ddr, i), 648 DDR_SIZE_VECT (ddr)); 649 } 650 651 for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++) 652 { 653 fprintf (outf, " direction_vector: "); 654 print_lambda_vector (outf, DDR_DIR_VECT (ddr, i), 655 DDR_SIZE_VECT (ddr)); 656 } 657 } 658 659 fprintf (outf, ")\n"); 660} 661 662 663 664/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ 665 666void 667dump_data_dependence_direction (FILE *file, 668 enum data_dependence_direction dir) 669{ 670 switch (dir) 671 { 672 case dir_positive: 673 fprintf (file, "+"); 674 break; 675 676 case dir_negative: 677 fprintf (file, "-"); 678 break; 679 680 case dir_equal: 681 fprintf (file, "="); 682 break; 683 684 case dir_positive_or_negative: 685 fprintf (file, "+-"); 686 break; 687 688 case dir_positive_or_equal: 689 fprintf (file, "+="); 690 break; 691 692 case dir_negative_or_equal: 693 fprintf (file, "-="); 694 break; 695 696 case dir_star: 697 fprintf (file, "*"); 698 break; 699 700 default: 701 break; 702 } 703} 704 705/* Dumps the distance and direction vectors in FILE. DDRS contains 706 the dependence relations, and VECT_SIZE is the size of the 707 dependence vectors, or in other words the number of loops in the 708 considered nest. */ 709 710void 711dump_dist_dir_vectors (FILE *file, varray_type ddrs) 712{ 713 unsigned int i, j; 714 715 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) 716 { 717 struct data_dependence_relation *ddr = 718 (struct data_dependence_relation *) 719 VARRAY_GENERIC_PTR (ddrs, i); 720 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE 721 && DDR_AFFINE_P (ddr)) 722 { 723 for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++) 724 { 725 fprintf (file, "DISTANCE_V ("); 726 print_lambda_vector (file, DDR_DIST_VECT (ddr, j), 727 DDR_SIZE_VECT (ddr)); 728 fprintf (file, ")\n"); 729 } 730 731 for (j = 0; j < DDR_NUM_DIR_VECTS (ddr); j++) 732 { 733 fprintf (file, "DIRECTION_V ("); 734 print_lambda_vector (file, DDR_DIR_VECT (ddr, j), 735 DDR_SIZE_VECT (ddr)); 736 fprintf (file, ")\n"); 737 } 738 } 739 } 740 fprintf (file, "\n\n"); 741} 742 743/* Dumps the data dependence relations DDRS in FILE. */ 744 745void 746dump_ddrs (FILE *file, varray_type ddrs) 747{ 748 unsigned int i; 749 750 for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++) 751 { 752 struct data_dependence_relation *ddr = 753 (struct data_dependence_relation *) 754 VARRAY_GENERIC_PTR (ddrs, i); 755 dump_data_dependence_relation (file, ddr); 756 } 757 fprintf (file, "\n\n"); 758} 759 760 761 762/* Estimate the number of iterations from the size of the data and the 763 access functions. */ 764 765static void 766estimate_niter_from_size_of_data (struct loop *loop, 767 tree opnd0, 768 tree access_fn, 769 tree stmt) 770{ 771 tree estimation = NULL_TREE; 772 tree array_size, data_size, element_size; 773 tree init, step; 774 775 init = initial_condition (access_fn); 776 step = evolution_part_in_loop_num (access_fn, loop->num); 777 778 array_size = TYPE_SIZE (TREE_TYPE (opnd0)); 779 element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0))); 780 if (array_size == NULL_TREE 781 || TREE_CODE (array_size) != INTEGER_CST 782 || TREE_CODE (element_size) != INTEGER_CST) 783 return; 784 785 data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node, 786 array_size, element_size); 787 788 if (init != NULL_TREE 789 && step != NULL_TREE 790 && TREE_CODE (init) == INTEGER_CST 791 && TREE_CODE (step) == INTEGER_CST) 792 { 793 tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step); 794 tree sign = fold_build2 (GT_EXPR, boolean_type_node, i_plus_s, init); 795 796 if (sign == boolean_true_node) 797 estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node, 798 fold_build2 (MINUS_EXPR, integer_type_node, 799 data_size, init), step); 800 801 /* When the step is negative, as in PR23386: (init = 3, step = 802 0ffffffff, data_size = 100), we have to compute the 803 estimation as ceil_div (init, 0 - step) + 1. */ 804 else if (sign == boolean_false_node) 805 estimation = 806 fold_build2 (PLUS_EXPR, integer_type_node, 807 fold_build2 (CEIL_DIV_EXPR, integer_type_node, 808 init, 809 fold_build2 (MINUS_EXPR, unsigned_type_node, 810 integer_zero_node, step)), 811 integer_one_node); 812 813 if (estimation) 814 record_estimate (loop, estimation, boolean_true_node, stmt); 815 } 816} 817 818/* Given an ARRAY_REF node REF, records its access functions. 819 Example: given A[i][3], record in ACCESS_FNS the opnd1 function, 820 i.e. the constant "3", then recursively call the function on opnd0, 821 i.e. the ARRAY_REF "A[i]". 822 If ESTIMATE_ONLY is true, we just set the estimated number of loop 823 iterations, we don't store the access function. 824 The function returns the base name: "A". */ 825 826static tree 827analyze_array_indexes (struct loop *loop, 828 VEC(tree,heap) **access_fns, 829 tree ref, tree stmt, 830 bool estimate_only) 831{ 832 tree opnd0, opnd1; 833 tree access_fn; 834 835 opnd0 = TREE_OPERAND (ref, 0); 836 opnd1 = TREE_OPERAND (ref, 1); 837 838 /* The detection of the evolution function for this data access is 839 postponed until the dependence test. This lazy strategy avoids 840 the computation of access functions that are of no interest for 841 the optimizers. */ 842 access_fn = instantiate_parameters 843 (loop, analyze_scalar_evolution (loop, opnd1)); 844 845 if (estimate_only 846 && chrec_contains_undetermined (loop->estimated_nb_iterations)) 847 estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt); 848 849 if (!estimate_only) 850 VEC_safe_push (tree, heap, *access_fns, access_fn); 851 852 /* Recursively record other array access functions. */ 853 if (TREE_CODE (opnd0) == ARRAY_REF) 854 return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only); 855 856 /* Return the base name of the data access. */ 857 else 858 return opnd0; 859} 860 861/* For an array reference REF contained in STMT, attempt to bound the 862 number of iterations in the loop containing STMT */ 863 864void 865estimate_iters_using_array (tree stmt, tree ref) 866{ 867 analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt, 868 true); 869} 870 871/* For a data reference REF contained in the statement STMT, initialize 872 a DATA_REFERENCE structure, and return it. IS_READ flag has to be 873 set to true when REF is in the right hand side of an 874 assignment. */ 875 876struct data_reference * 877analyze_array (tree stmt, tree ref, bool is_read) 878{ 879 struct data_reference *res; 880 VEC(tree,heap) *acc_fns; 881 882 if (dump_file && (dump_flags & TDF_DETAILS)) 883 { 884 fprintf (dump_file, "(analyze_array \n"); 885 fprintf (dump_file, " (ref = "); 886 print_generic_stmt (dump_file, ref, 0); 887 fprintf (dump_file, ")\n"); 888 } 889 890 res = xmalloc (sizeof (struct data_reference)); 891 892 DR_STMT (res) = stmt; 893 DR_REF (res) = ref; 894 acc_fns = VEC_alloc (tree, heap, 3); 895 DR_BASE_OBJECT (res) = analyze_array_indexes 896 (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false); 897 DR_TYPE (res) = ARRAY_REF_TYPE; 898 DR_SET_ACCESS_FNS (res, acc_fns); 899 DR_IS_READ (res) = is_read; 900 DR_BASE_ADDRESS (res) = NULL_TREE; 901 DR_OFFSET (res) = NULL_TREE; 902 DR_INIT (res) = NULL_TREE; 903 DR_STEP (res) = NULL_TREE; 904 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE; 905 DR_MEMTAG (res) = NULL_TREE; 906 DR_PTR_INFO (res) = NULL; 907 908 if (dump_file && (dump_flags & TDF_DETAILS)) 909 fprintf (dump_file, ")\n"); 910 911 return res; 912} 913 914 915/* Analyze an indirect memory reference, REF, that comes from STMT. 916 IS_READ is true if this is an indirect load, and false if it is 917 an indirect store. 918 Return a new data reference structure representing the indirect_ref, or 919 NULL if we cannot describe the access function. */ 920 921static struct data_reference * 922analyze_indirect_ref (tree stmt, tree ref, bool is_read) 923{ 924 struct loop *loop = loop_containing_stmt (stmt); 925 tree ptr_ref = TREE_OPERAND (ref, 0); 926 tree access_fn = analyze_scalar_evolution (loop, ptr_ref); 927 tree init = initial_condition_in_loop_num (access_fn, loop->num); 928 tree base_address = NULL_TREE, evolution, step = NULL_TREE; 929 struct ptr_info_def *ptr_info = NULL; 930 931 if (TREE_CODE (ptr_ref) == SSA_NAME) 932 ptr_info = SSA_NAME_PTR_INFO (ptr_ref); 933 934 STRIP_NOPS (init); 935 if (access_fn == chrec_dont_know || !init || init == chrec_dont_know) 936 { 937 if (dump_file && (dump_flags & TDF_DETAILS)) 938 { 939 fprintf (dump_file, "\nBad access function of ptr: "); 940 print_generic_expr (dump_file, ref, TDF_SLIM); 941 fprintf (dump_file, "\n"); 942 } 943 return NULL; 944 } 945 946 if (dump_file && (dump_flags & TDF_DETAILS)) 947 { 948 fprintf (dump_file, "\nAccess function of ptr: "); 949 print_generic_expr (dump_file, access_fn, TDF_SLIM); 950 fprintf (dump_file, "\n"); 951 } 952 953 if (!expr_invariant_in_loop_p (loop, init)) 954 { 955 if (dump_file && (dump_flags & TDF_DETAILS)) 956 fprintf (dump_file, "\ninitial condition is not loop invariant.\n"); 957 } 958 else 959 { 960 base_address = init; 961 evolution = evolution_part_in_loop_num (access_fn, loop->num); 962 if (evolution != chrec_dont_know) 963 { 964 if (!evolution) 965 step = ssize_int (0); 966 else 967 { 968 if (TREE_CODE (evolution) == INTEGER_CST) 969 step = fold_convert (ssizetype, evolution); 970 else 971 if (dump_file && (dump_flags & TDF_DETAILS)) 972 fprintf (dump_file, "\nnon constant step for ptr access.\n"); 973 } 974 } 975 else 976 if (dump_file && (dump_flags & TDF_DETAILS)) 977 fprintf (dump_file, "\nunknown evolution of ptr.\n"); 978 } 979 return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address, 980 NULL_TREE, step, NULL_TREE, NULL_TREE, 981 ptr_info, POINTER_REF_TYPE); 982} 983 984/* For a data reference REF contained in the statement STMT, initialize 985 a DATA_REFERENCE structure, and return it. */ 986 987struct data_reference * 988init_data_ref (tree stmt, 989 tree ref, 990 tree base, 991 tree access_fn, 992 bool is_read, 993 tree base_address, 994 tree init_offset, 995 tree step, 996 tree misalign, 997 tree memtag, 998 struct ptr_info_def *ptr_info, 999 enum data_ref_type type) 1000{ 1001 struct data_reference *res; 1002 VEC(tree,heap) *acc_fns; 1003 1004 if (dump_file && (dump_flags & TDF_DETAILS)) 1005 { 1006 fprintf (dump_file, "(init_data_ref \n"); 1007 fprintf (dump_file, " (ref = "); 1008 print_generic_stmt (dump_file, ref, 0); 1009 fprintf (dump_file, ")\n"); 1010 } 1011 1012 res = xmalloc (sizeof (struct data_reference)); 1013 1014 DR_STMT (res) = stmt; 1015 DR_REF (res) = ref; 1016 DR_BASE_OBJECT (res) = base; 1017 DR_TYPE (res) = type; 1018 acc_fns = VEC_alloc (tree, heap, 3); 1019 DR_SET_ACCESS_FNS (res, acc_fns); 1020 VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn); 1021 DR_IS_READ (res) = is_read; 1022 DR_BASE_ADDRESS (res) = base_address; 1023 DR_OFFSET (res) = init_offset; 1024 DR_INIT (res) = NULL_TREE; 1025 DR_STEP (res) = step; 1026 DR_OFFSET_MISALIGNMENT (res) = misalign; 1027 DR_MEMTAG (res) = memtag; 1028 DR_PTR_INFO (res) = ptr_info; 1029 1030 if (dump_file && (dump_flags & TDF_DETAILS)) 1031 fprintf (dump_file, ")\n"); 1032 1033 return res; 1034} 1035 1036 1037 1038/* Function strip_conversions 1039 1040 Strip conversions that don't narrow the mode. */ 1041 1042static tree 1043strip_conversion (tree expr) 1044{ 1045 tree to, ti, oprnd0; 1046 1047 while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR) 1048 { 1049 to = TREE_TYPE (expr); 1050 oprnd0 = TREE_OPERAND (expr, 0); 1051 ti = TREE_TYPE (oprnd0); 1052 1053 if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti)) 1054 return NULL_TREE; 1055 if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti))) 1056 return NULL_TREE; 1057 1058 expr = oprnd0; 1059 } 1060 return expr; 1061} 1062 1063 1064/* Function analyze_offset_expr 1065 1066 Given an offset expression EXPR received from get_inner_reference, analyze 1067 it and create an expression for INITIAL_OFFSET by substituting the variables 1068 of EXPR with initial_condition of the corresponding access_fn in the loop. 1069 E.g., 1070 for i 1071 for (j = 3; j < N; j++) 1072 a[j].b[i][j] = 0; 1073 1074 For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be 1075 substituted, since its access_fn in the inner loop is i. 'j' will be 1076 substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where 1077 C` = 3 * C_j + C. 1078 1079 Compute MISALIGN (the misalignment of the data reference initial access from 1080 its base). Misalignment can be calculated only if all the variables can be 1081 substituted with constants, otherwise, we record maximum possible alignment 1082 in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN 1083 will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be 1084 recorded in ALIGNED_TO. 1085 1086 STEP is an evolution of the data reference in this loop in bytes. 1087 In the above example, STEP is C_j. 1088 1089 Return FALSE, if the analysis fails, e.g., there is no access_fn for a 1090 variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO 1091 and STEP) are NULL_TREEs. Otherwise, return TRUE. 1092 1093*/ 1094 1095static bool 1096analyze_offset_expr (tree expr, 1097 struct loop *loop, 1098 tree *initial_offset, 1099 tree *misalign, 1100 tree *aligned_to, 1101 tree *step) 1102{ 1103 tree oprnd0; 1104 tree oprnd1; 1105 tree left_offset = ssize_int (0); 1106 tree right_offset = ssize_int (0); 1107 tree left_misalign = ssize_int (0); 1108 tree right_misalign = ssize_int (0); 1109 tree left_step = ssize_int (0); 1110 tree right_step = ssize_int (0); 1111 enum tree_code code; 1112 tree init, evolution; 1113 tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE; 1114 1115 *step = NULL_TREE; 1116 *misalign = NULL_TREE; 1117 *aligned_to = NULL_TREE; 1118 *initial_offset = NULL_TREE; 1119 1120 /* Strip conversions that don't narrow the mode. */ 1121 expr = strip_conversion (expr); 1122 if (!expr) 1123 return false; 1124 1125 /* Stop conditions: 1126 1. Constant. */ 1127 if (TREE_CODE (expr) == INTEGER_CST) 1128 { 1129 *initial_offset = fold_convert (ssizetype, expr); 1130 *misalign = fold_convert (ssizetype, expr); 1131 *step = ssize_int (0); 1132 return true; 1133 } 1134 1135 /* 2. Variable. Try to substitute with initial_condition of the corresponding 1136 access_fn in the current loop. */ 1137 if (SSA_VAR_P (expr)) 1138 { 1139 tree access_fn = analyze_scalar_evolution (loop, expr); 1140 1141 if (access_fn == chrec_dont_know) 1142 /* No access_fn. */ 1143 return false; 1144 1145 init = initial_condition_in_loop_num (access_fn, loop->num); 1146 if (!expr_invariant_in_loop_p (loop, init)) 1147 /* Not enough information: may be not loop invariant. 1148 E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its 1149 initial_condition is D, but it depends on i - loop's induction 1150 variable. */ 1151 return false; 1152 1153 evolution = evolution_part_in_loop_num (access_fn, loop->num); 1154 if (evolution && TREE_CODE (evolution) != INTEGER_CST) 1155 /* Evolution is not constant. */ 1156 return false; 1157 1158 if (TREE_CODE (init) == INTEGER_CST) 1159 *misalign = fold_convert (ssizetype, init); 1160 else 1161 /* Not constant, misalignment cannot be calculated. */ 1162 *misalign = NULL_TREE; 1163 1164 *initial_offset = fold_convert (ssizetype, init); 1165 1166 *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0); 1167 return true; 1168 } 1169 1170 /* Recursive computation. */ 1171 if (!BINARY_CLASS_P (expr)) 1172 { 1173 /* We expect to get binary expressions (PLUS/MINUS and MULT). */ 1174 if (dump_file && (dump_flags & TDF_DETAILS)) 1175 { 1176 fprintf (dump_file, "\nNot binary expression "); 1177 print_generic_expr (dump_file, expr, TDF_SLIM); 1178 fprintf (dump_file, "\n"); 1179 } 1180 return false; 1181 } 1182 oprnd0 = TREE_OPERAND (expr, 0); 1183 oprnd1 = TREE_OPERAND (expr, 1); 1184 1185 if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign, 1186 &left_aligned_to, &left_step) 1187 || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign, 1188 &right_aligned_to, &right_step)) 1189 return false; 1190 1191 /* The type of the operation: plus, minus or mult. */ 1192 code = TREE_CODE (expr); 1193 switch (code) 1194 { 1195 case MULT_EXPR: 1196 if (TREE_CODE (right_offset) != INTEGER_CST) 1197 /* RIGHT_OFFSET can be not constant. For example, for arrays of variable 1198 sized types. 1199 FORNOW: We don't support such cases. */ 1200 return false; 1201 1202 /* Strip conversions that don't narrow the mode. */ 1203 left_offset = strip_conversion (left_offset); 1204 if (!left_offset) 1205 return false; 1206 /* Misalignment computation. */ 1207 if (SSA_VAR_P (left_offset)) 1208 { 1209 /* If the left side contains variables that can't be substituted with 1210 constants, the misalignment is unknown. However, if the right side 1211 is a multiple of some alignment, we know that the expression is 1212 aligned to it. Therefore, we record such maximum possible value. 1213 */ 1214 *misalign = NULL_TREE; 1215 *aligned_to = ssize_int (highest_pow2_factor (right_offset)); 1216 } 1217 else 1218 { 1219 /* The left operand was successfully substituted with constant. */ 1220 if (left_misalign) 1221 { 1222 /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is 1223 NULL_TREE. */ 1224 *misalign = size_binop (code, left_misalign, right_misalign); 1225 if (left_aligned_to && right_aligned_to) 1226 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, 1227 right_aligned_to); 1228 else 1229 *aligned_to = left_aligned_to ? 1230 left_aligned_to : right_aligned_to; 1231 } 1232 else 1233 *misalign = NULL_TREE; 1234 } 1235 1236 /* Step calculation. */ 1237 /* Multiply the step by the right operand. */ 1238 *step = size_binop (MULT_EXPR, left_step, right_offset); 1239 break; 1240 1241 case PLUS_EXPR: 1242 case MINUS_EXPR: 1243 /* Combine the recursive calculations for step and misalignment. */ 1244 *step = size_binop (code, left_step, right_step); 1245 1246 /* Unknown alignment. */ 1247 if ((!left_misalign && !left_aligned_to) 1248 || (!right_misalign && !right_aligned_to)) 1249 { 1250 *misalign = NULL_TREE; 1251 *aligned_to = NULL_TREE; 1252 break; 1253 } 1254 1255 if (left_misalign && right_misalign) 1256 *misalign = size_binop (code, left_misalign, right_misalign); 1257 else 1258 *misalign = left_misalign ? left_misalign : right_misalign; 1259 1260 if (left_aligned_to && right_aligned_to) 1261 *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to); 1262 else 1263 *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to; 1264 1265 break; 1266 1267 default: 1268 gcc_unreachable (); 1269 } 1270 1271 /* Compute offset. */ 1272 *initial_offset = fold_convert (ssizetype, 1273 fold_build2 (code, TREE_TYPE (left_offset), 1274 left_offset, 1275 right_offset)); 1276 return true; 1277} 1278 1279/* Function address_analysis 1280 1281 Return the BASE of the address expression EXPR. 1282 Also compute the OFFSET from BASE, MISALIGN and STEP. 1283 1284 Input: 1285 EXPR - the address expression that is being analyzed 1286 STMT - the statement that contains EXPR or its original memory reference 1287 IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR 1288 DR - data_reference struct for the original memory reference 1289 1290 Output: 1291 BASE (returned value) - the base of the data reference EXPR. 1292 INITIAL_OFFSET - initial offset of EXPR from BASE (an expression) 1293 MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the 1294 computation is impossible 1295 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 1296 calculated (doesn't depend on variables) 1297 STEP - evolution of EXPR in the loop 1298 1299 If something unexpected is encountered (an unsupported form of data-ref), 1300 then NULL_TREE is returned. 1301 */ 1302 1303static tree 1304address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr, 1305 tree *offset, tree *misalign, tree *aligned_to, tree *step) 1306{ 1307 tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1; 1308 tree address_offset = ssize_int (0), address_misalign = ssize_int (0); 1309 tree dummy, address_aligned_to = NULL_TREE; 1310 struct ptr_info_def *dummy1; 1311 subvar_t dummy2; 1312 1313 switch (TREE_CODE (expr)) 1314 { 1315 case PLUS_EXPR: 1316 case MINUS_EXPR: 1317 /* EXPR is of form {base +/- offset} (or {offset +/- base}). */ 1318 oprnd0 = TREE_OPERAND (expr, 0); 1319 oprnd1 = TREE_OPERAND (expr, 1); 1320 1321 STRIP_NOPS (oprnd0); 1322 STRIP_NOPS (oprnd1); 1323 1324 /* Recursively try to find the base of the address contained in EXPR. 1325 For offset, the returned base will be NULL. */ 1326 base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset, 1327 &address_misalign, &address_aligned_to, 1328 step); 1329 1330 base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset, 1331 &address_misalign, &address_aligned_to, 1332 step); 1333 1334 /* We support cases where only one of the operands contains an 1335 address. */ 1336 if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1)) 1337 { 1338 if (dump_file && (dump_flags & TDF_DETAILS)) 1339 { 1340 fprintf (dump_file, 1341 "\neither more than one address or no addresses in expr "); 1342 print_generic_expr (dump_file, expr, TDF_SLIM); 1343 fprintf (dump_file, "\n"); 1344 } 1345 return NULL_TREE; 1346 } 1347 1348 /* To revert STRIP_NOPS. */ 1349 oprnd0 = TREE_OPERAND (expr, 0); 1350 oprnd1 = TREE_OPERAND (expr, 1); 1351 1352 offset_expr = base_addr0 ? 1353 fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0); 1354 1355 /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is 1356 a number, we can add it to the misalignment value calculated for base, 1357 otherwise, misalignment is NULL. */ 1358 if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign) 1359 { 1360 *misalign = size_binop (TREE_CODE (expr), address_misalign, 1361 offset_expr); 1362 *aligned_to = address_aligned_to; 1363 } 1364 else 1365 { 1366 *misalign = NULL_TREE; 1367 *aligned_to = NULL_TREE; 1368 } 1369 1370 /* Combine offset (from EXPR {base + offset}) with the offset calculated 1371 for base. */ 1372 *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr); 1373 return base_addr0 ? base_addr0 : base_addr1; 1374 1375 case ADDR_EXPR: 1376 base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read, 1377 &dr, offset, misalign, aligned_to, step, 1378 &dummy, &dummy1, &dummy2); 1379 return base_address; 1380 1381 case SSA_NAME: 1382 if (!POINTER_TYPE_P (TREE_TYPE (expr))) 1383 { 1384 if (dump_file && (dump_flags & TDF_DETAILS)) 1385 { 1386 fprintf (dump_file, "\nnot pointer SSA_NAME "); 1387 print_generic_expr (dump_file, expr, TDF_SLIM); 1388 fprintf (dump_file, "\n"); 1389 } 1390 return NULL_TREE; 1391 } 1392 *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr)))); 1393 *misalign = ssize_int (0); 1394 *offset = ssize_int (0); 1395 *step = ssize_int (0); 1396 return expr; 1397 1398 default: 1399 return NULL_TREE; 1400 } 1401} 1402 1403 1404/* Function object_analysis 1405 1406 Create a data-reference structure DR for MEMREF. 1407 Return the BASE of the data reference MEMREF if the analysis is possible. 1408 Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP. 1409 E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset 1410 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET 1411 instantiated with initial_conditions of access_functions of variables, 1412 and STEP is the evolution of the DR_REF in this loop. 1413 1414 Function get_inner_reference is used for the above in case of ARRAY_REF and 1415 COMPONENT_REF. 1416 1417 The structure of the function is as follows: 1418 Part 1: 1419 Case 1. For handled_component_p refs 1420 1.1 build data-reference structure for MEMREF 1421 1.2 call get_inner_reference 1422 1.2.1 analyze offset expr received from get_inner_reference 1423 (fall through with BASE) 1424 Case 2. For declarations 1425 2.1 set MEMTAG 1426 Case 3. For INDIRECT_REFs 1427 3.1 build data-reference structure for MEMREF 1428 3.2 analyze evolution and initial condition of MEMREF 1429 3.3 set data-reference structure for MEMREF 1430 3.4 call address_analysis to analyze INIT of the access function 1431 3.5 extract memory tag 1432 1433 Part 2: 1434 Combine the results of object and address analysis to calculate 1435 INITIAL_OFFSET, STEP and misalignment info. 1436 1437 Input: 1438 MEMREF - the memory reference that is being analyzed 1439 STMT - the statement that contains MEMREF 1440 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF 1441 1442 Output: 1443 BASE_ADDRESS (returned value) - the base address of the data reference MEMREF 1444 E.g, if MEMREF is a.b[k].c[i][j] the returned 1445 base is &a. 1446 DR - data_reference struct for MEMREF 1447 INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression) 1448 MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of 1449 ALIGNMENT or NULL_TREE if the computation is impossible 1450 ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 1451 calculated (doesn't depend on variables) 1452 STEP - evolution of the DR_REF in the loop 1453 MEMTAG - memory tag for aliasing purposes 1454 PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME 1455 SUBVARS - Sub-variables of the variable 1456 1457 If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned, 1458 but DR can be created anyway. 1459 1460*/ 1461 1462static tree 1463object_analysis (tree memref, tree stmt, bool is_read, 1464 struct data_reference **dr, tree *offset, tree *misalign, 1465 tree *aligned_to, tree *step, tree *memtag, 1466 struct ptr_info_def **ptr_info, subvar_t *subvars) 1467{ 1468 tree base = NULL_TREE, base_address = NULL_TREE; 1469 tree object_offset = ssize_int (0), object_misalign = ssize_int (0); 1470 tree object_step = ssize_int (0), address_step = ssize_int (0); 1471 tree address_offset = ssize_int (0), address_misalign = ssize_int (0); 1472 HOST_WIDE_INT pbitsize, pbitpos; 1473 tree poffset, bit_pos_in_bytes; 1474 enum machine_mode pmode; 1475 int punsignedp, pvolatilep; 1476 tree ptr_step = ssize_int (0), ptr_init = NULL_TREE; 1477 struct loop *loop = loop_containing_stmt (stmt); 1478 struct data_reference *ptr_dr = NULL; 1479 tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE; 1480 1481 *ptr_info = NULL; 1482 1483 /* Part 1: */ 1484 /* Case 1. handled_component_p refs. */ 1485 if (handled_component_p (memref)) 1486 { 1487 /* 1.1 build data-reference structure for MEMREF. */ 1488 /* TODO: handle COMPONENT_REFs. */ 1489 if (!(*dr)) 1490 { 1491 if (TREE_CODE (memref) == ARRAY_REF) 1492 *dr = analyze_array (stmt, memref, is_read); 1493 else 1494 { 1495 /* FORNOW. */ 1496 if (dump_file && (dump_flags & TDF_DETAILS)) 1497 { 1498 fprintf (dump_file, "\ndata-ref of unsupported type "); 1499 print_generic_expr (dump_file, memref, TDF_SLIM); 1500 fprintf (dump_file, "\n"); 1501 } 1502 return NULL_TREE; 1503 } 1504 } 1505 1506 /* 1.2 call get_inner_reference. */ 1507 /* Find the base and the offset from it. */ 1508 base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset, 1509 &pmode, &punsignedp, &pvolatilep, false); 1510 if (!base) 1511 { 1512 if (dump_file && (dump_flags & TDF_DETAILS)) 1513 { 1514 fprintf (dump_file, "\nfailed to get inner ref for "); 1515 print_generic_expr (dump_file, memref, TDF_SLIM); 1516 fprintf (dump_file, "\n"); 1517 } 1518 return NULL_TREE; 1519 } 1520 1521 /* 1.2.1 analyze offset expr received from get_inner_reference. */ 1522 if (poffset 1523 && !analyze_offset_expr (poffset, loop, &object_offset, 1524 &object_misalign, &object_aligned_to, 1525 &object_step)) 1526 { 1527 if (dump_file && (dump_flags & TDF_DETAILS)) 1528 { 1529 fprintf (dump_file, "\nfailed to compute offset or step for "); 1530 print_generic_expr (dump_file, memref, TDF_SLIM); 1531 fprintf (dump_file, "\n"); 1532 } 1533 return NULL_TREE; 1534 } 1535 1536 /* Add bit position to OFFSET and MISALIGN. */ 1537 1538 bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT); 1539 /* Check that there is no remainder in bits. */ 1540 if (pbitpos%BITS_PER_UNIT) 1541 { 1542 if (dump_file && (dump_flags & TDF_DETAILS)) 1543 fprintf (dump_file, "\nbit offset alignment.\n"); 1544 return NULL_TREE; 1545 } 1546 object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset); 1547 if (object_misalign) 1548 object_misalign = size_binop (PLUS_EXPR, object_misalign, 1549 bit_pos_in_bytes); 1550 1551 memref = base; /* To continue analysis of BASE. */ 1552 /* fall through */ 1553 } 1554 1555 /* Part 1: Case 2. Declarations. */ 1556 if (DECL_P (memref)) 1557 { 1558 /* We expect to get a decl only if we already have a DR. */ 1559 if (!(*dr)) 1560 { 1561 if (dump_file && (dump_flags & TDF_DETAILS)) 1562 { 1563 fprintf (dump_file, "\nunhandled decl "); 1564 print_generic_expr (dump_file, memref, TDF_SLIM); 1565 fprintf (dump_file, "\n"); 1566 } 1567 return NULL_TREE; 1568 } 1569 1570 /* TODO: if during the analysis of INDIRECT_REF we get to an object, put 1571 the object in BASE_OBJECT field if we can prove that this is O.K., 1572 i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT. 1573 (e.g., if the object is an array base 'a', where 'a[N]', we must prove 1574 that every access with 'p' (the original INDIRECT_REF based on '&a') 1575 in the loop is within the array boundaries - from a[0] to a[N-1]). 1576 Otherwise, our alias analysis can be incorrect. 1577 Even if an access function based on BASE_OBJECT can't be build, update 1578 BASE_OBJECT field to enable us to prove that two data-refs are 1579 different (without access function, distance analysis is impossible). 1580 */ 1581 if (SSA_VAR_P (memref) && var_can_have_subvars (memref)) 1582 *subvars = get_subvars_for_var (memref); 1583 base_address = build_fold_addr_expr (memref); 1584 /* 2.1 set MEMTAG. */ 1585 *memtag = memref; 1586 } 1587 1588 /* Part 1: Case 3. INDIRECT_REFs. */ 1589 else if (TREE_CODE (memref) == INDIRECT_REF) 1590 { 1591 tree ptr_ref = TREE_OPERAND (memref, 0); 1592 if (TREE_CODE (ptr_ref) == SSA_NAME) 1593 *ptr_info = SSA_NAME_PTR_INFO (ptr_ref); 1594 1595 /* 3.1 build data-reference structure for MEMREF. */ 1596 ptr_dr = analyze_indirect_ref (stmt, memref, is_read); 1597 if (!ptr_dr) 1598 { 1599 if (dump_file && (dump_flags & TDF_DETAILS)) 1600 { 1601 fprintf (dump_file, "\nfailed to create dr for "); 1602 print_generic_expr (dump_file, memref, TDF_SLIM); 1603 fprintf (dump_file, "\n"); 1604 } 1605 return NULL_TREE; 1606 } 1607 1608 /* 3.2 analyze evolution and initial condition of MEMREF. */ 1609 ptr_step = DR_STEP (ptr_dr); 1610 ptr_init = DR_BASE_ADDRESS (ptr_dr); 1611 if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init))) 1612 { 1613 *dr = (*dr) ? *dr : ptr_dr; 1614 if (dump_file && (dump_flags & TDF_DETAILS)) 1615 { 1616 fprintf (dump_file, "\nbad pointer access "); 1617 print_generic_expr (dump_file, memref, TDF_SLIM); 1618 fprintf (dump_file, "\n"); 1619 } 1620 return NULL_TREE; 1621 } 1622 1623 if (integer_zerop (ptr_step) && !(*dr)) 1624 { 1625 if (dump_file && (dump_flags & TDF_DETAILS)) 1626 fprintf (dump_file, "\nptr is loop invariant.\n"); 1627 *dr = ptr_dr; 1628 return NULL_TREE; 1629 1630 /* If there exists DR for MEMREF, we are analyzing the base of 1631 handled component (PTR_INIT), which not necessary has evolution in 1632 the loop. */ 1633 } 1634 object_step = size_binop (PLUS_EXPR, object_step, ptr_step); 1635 1636 /* 3.3 set data-reference structure for MEMREF. */ 1637 if (!*dr) 1638 *dr = ptr_dr; 1639 1640 /* 3.4 call address_analysis to analyze INIT of the access 1641 function. */ 1642 base_address = address_analysis (ptr_init, stmt, is_read, *dr, 1643 &address_offset, &address_misalign, 1644 &address_aligned_to, &address_step); 1645 if (!base_address) 1646 { 1647 if (dump_file && (dump_flags & TDF_DETAILS)) 1648 { 1649 fprintf (dump_file, "\nfailed to analyze address "); 1650 print_generic_expr (dump_file, ptr_init, TDF_SLIM); 1651 fprintf (dump_file, "\n"); 1652 } 1653 return NULL_TREE; 1654 } 1655 1656 /* 3.5 extract memory tag. */ 1657 switch (TREE_CODE (base_address)) 1658 { 1659 case SSA_NAME: 1660 *memtag = get_var_ann (SSA_NAME_VAR (base_address))->type_mem_tag; 1661 if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME) 1662 *memtag = get_var_ann ( 1663 SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->type_mem_tag; 1664 break; 1665 case ADDR_EXPR: 1666 *memtag = TREE_OPERAND (base_address, 0); 1667 break; 1668 default: 1669 if (dump_file && (dump_flags & TDF_DETAILS)) 1670 { 1671 fprintf (dump_file, "\nno memtag for "); 1672 print_generic_expr (dump_file, memref, TDF_SLIM); 1673 fprintf (dump_file, "\n"); 1674 } 1675 *memtag = NULL_TREE; 1676 break; 1677 } 1678 } 1679 1680 if (!base_address) 1681 { 1682 /* MEMREF cannot be analyzed. */ 1683 if (dump_file && (dump_flags & TDF_DETAILS)) 1684 { 1685 fprintf (dump_file, "\ndata-ref of unsupported type "); 1686 print_generic_expr (dump_file, memref, TDF_SLIM); 1687 fprintf (dump_file, "\n"); 1688 } 1689 return NULL_TREE; 1690 } 1691 1692 if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag)) 1693 *subvars = get_subvars_for_var (*memtag); 1694 1695 /* Part 2: Combine the results of object and address analysis to calculate 1696 INITIAL_OFFSET, STEP and misalignment info. */ 1697 *offset = size_binop (PLUS_EXPR, object_offset, address_offset); 1698 1699 if ((!object_misalign && !object_aligned_to) 1700 || (!address_misalign && !address_aligned_to)) 1701 { 1702 *misalign = NULL_TREE; 1703 *aligned_to = NULL_TREE; 1704 } 1705 else 1706 { 1707 if (object_misalign && address_misalign) 1708 *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign); 1709 else 1710 *misalign = object_misalign ? object_misalign : address_misalign; 1711 if (object_aligned_to && address_aligned_to) 1712 *aligned_to = size_binop (MIN_EXPR, object_aligned_to, 1713 address_aligned_to); 1714 else 1715 *aligned_to = object_aligned_to ? 1716 object_aligned_to : address_aligned_to; 1717 } 1718 *step = size_binop (PLUS_EXPR, object_step, address_step); 1719 1720 return base_address; 1721} 1722 1723/* Function analyze_offset. 1724 1725 Extract INVARIANT and CONSTANT parts from OFFSET. 1726 1727*/ 1728static bool 1729analyze_offset (tree offset, tree *invariant, tree *constant) 1730{ 1731 tree op0, op1, constant_0, constant_1, invariant_0, invariant_1; 1732 enum tree_code code = TREE_CODE (offset); 1733 1734 *invariant = NULL_TREE; 1735 *constant = NULL_TREE; 1736 1737 /* Not PLUS/MINUS expression - recursion stop condition. */ 1738 if (code != PLUS_EXPR && code != MINUS_EXPR) 1739 { 1740 if (TREE_CODE (offset) == INTEGER_CST) 1741 *constant = offset; 1742 else 1743 *invariant = offset; 1744 return true; 1745 } 1746 1747 op0 = TREE_OPERAND (offset, 0); 1748 op1 = TREE_OPERAND (offset, 1); 1749 1750 /* Recursive call with the operands. */ 1751 if (!analyze_offset (op0, &invariant_0, &constant_0) 1752 || !analyze_offset (op1, &invariant_1, &constant_1)) 1753 return false; 1754 1755 /* Combine the results. Add negation to the subtrahend in case of 1756 subtraction. */ 1757 if (constant_0 && constant_1) 1758 return false; 1759 *constant = constant_0 ? constant_0 : constant_1; 1760 if (code == MINUS_EXPR && constant_1) 1761 *constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant); 1762 1763 if (invariant_0 && invariant_1) 1764 *invariant = 1765 fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1); 1766 else 1767 { 1768 *invariant = invariant_0 ? invariant_0 : invariant_1; 1769 if (code == MINUS_EXPR && invariant_1) 1770 *invariant = 1771 fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant); 1772 } 1773 return true; 1774} 1775 1776 1777/* Function create_data_ref. 1778 1779 Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS, 1780 DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO, 1781 DR_MEMTAG, and DR_POINTSTO_INFO fields. 1782 1783 Input: 1784 MEMREF - the memory reference that is being analyzed 1785 STMT - the statement that contains MEMREF 1786 IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF 1787 1788 Output: 1789 DR (returned value) - data_reference struct for MEMREF 1790*/ 1791 1792static struct data_reference * 1793create_data_ref (tree memref, tree stmt, bool is_read) 1794{ 1795 struct data_reference *dr = NULL; 1796 tree base_address, offset, step, misalign, memtag; 1797 struct loop *loop = loop_containing_stmt (stmt); 1798 tree invariant = NULL_TREE, constant = NULL_TREE; 1799 tree type_size, init_cond; 1800 struct ptr_info_def *ptr_info; 1801 subvar_t subvars = NULL; 1802 tree aligned_to; 1803 1804 if (!memref) 1805 return NULL; 1806 1807 base_address = object_analysis (memref, stmt, is_read, &dr, &offset, 1808 &misalign, &aligned_to, &step, &memtag, 1809 &ptr_info, &subvars); 1810 if (!dr || !base_address) 1811 { 1812 if (dump_file && (dump_flags & TDF_DETAILS)) 1813 { 1814 fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for "); 1815 print_generic_expr (dump_file, memref, TDF_SLIM); 1816 fprintf (dump_file, "\n"); 1817 } 1818 return NULL; 1819 } 1820 1821 DR_BASE_ADDRESS (dr) = base_address; 1822 DR_OFFSET (dr) = offset; 1823 DR_INIT (dr) = ssize_int (0); 1824 DR_STEP (dr) = step; 1825 DR_OFFSET_MISALIGNMENT (dr) = misalign; 1826 DR_ALIGNED_TO (dr) = aligned_to; 1827 DR_MEMTAG (dr) = memtag; 1828 DR_PTR_INFO (dr) = ptr_info; 1829 DR_SUBVARS (dr) = subvars; 1830 1831 type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); 1832 1833 /* Change the access function for INIDIRECT_REFs, according to 1834 DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is 1835 an expression that can contain loop invariant expressions and constants. 1836 We put the constant part in the initial condition of the access function 1837 (for data dependence tests), and in DR_INIT of the data-ref. The loop 1838 invariant part is put in DR_OFFSET. 1839 The evolution part of the access function is STEP calculated in 1840 object_analysis divided by the size of data type. 1841 */ 1842 if (!DR_BASE_OBJECT (dr)) 1843 { 1844 tree access_fn; 1845 tree new_step; 1846 1847 /* Extract CONSTANT and INVARIANT from OFFSET, and put them in DR_INIT and 1848 DR_OFFSET fields of DR. */ 1849 if (!analyze_offset (offset, &invariant, &constant)) 1850 { 1851 if (dump_file && (dump_flags & TDF_DETAILS)) 1852 { 1853 fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's"); 1854 fprintf (dump_file, " offset for "); 1855 print_generic_expr (dump_file, memref, TDF_SLIM); 1856 fprintf (dump_file, "\n"); 1857 } 1858 return NULL; 1859 } 1860 if (constant) 1861 { 1862 DR_INIT (dr) = fold_convert (ssizetype, constant); 1863 init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant), 1864 constant, type_size); 1865 } 1866 else 1867 DR_INIT (dr) = init_cond = ssize_int (0);; 1868 1869 if (invariant) 1870 DR_OFFSET (dr) = invariant; 1871 else 1872 DR_OFFSET (dr) = ssize_int (0); 1873 1874 /* Update access function. */ 1875 access_fn = DR_ACCESS_FN (dr, 0); 1876 new_step = size_binop (TRUNC_DIV_EXPR, 1877 fold_convert (ssizetype, step), type_size); 1878 1879 access_fn = chrec_replace_initial_condition (access_fn, init_cond); 1880 access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step); 1881 1882 VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn); 1883 } 1884 1885 if (dump_file && (dump_flags & TDF_DETAILS)) 1886 { 1887 struct ptr_info_def *pi = DR_PTR_INFO (dr); 1888 1889 fprintf (dump_file, "\nCreated dr for "); 1890 print_generic_expr (dump_file, memref, TDF_SLIM); 1891 fprintf (dump_file, "\n\tbase_address: "); 1892 print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM); 1893 fprintf (dump_file, "\n\toffset from base address: "); 1894 print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM); 1895 fprintf (dump_file, "\n\tconstant offset from base address: "); 1896 print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM); 1897 fprintf (dump_file, "\n\tbase_object: "); 1898 print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); 1899 fprintf (dump_file, "\n\tstep: "); 1900 print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); 1901 fprintf (dump_file, "B\n\tmisalignment from base: "); 1902 print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM); 1903 if (DR_OFFSET_MISALIGNMENT (dr)) 1904 fprintf (dump_file, "B"); 1905 if (DR_ALIGNED_TO (dr)) 1906 { 1907 fprintf (dump_file, "\n\taligned to: "); 1908 print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM); 1909 } 1910 fprintf (dump_file, "\n\tmemtag: "); 1911 print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM); 1912 fprintf (dump_file, "\n"); 1913 if (pi && pi->name_mem_tag) 1914 { 1915 fprintf (dump_file, "\n\tnametag: "); 1916 print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM); 1917 fprintf (dump_file, "\n"); 1918 } 1919 } 1920 return dr; 1921} 1922 1923 1924/* Returns true when all the functions of a tree_vec CHREC are the 1925 same. */ 1926 1927static bool 1928all_chrecs_equal_p (tree chrec) 1929{ 1930 int j; 1931 1932 for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++) 1933 { 1934 tree chrec_j = TREE_VEC_ELT (chrec, j); 1935 tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1); 1936 if (!integer_zerop 1937 (chrec_fold_minus 1938 (integer_type_node, chrec_j, chrec_j_1))) 1939 return false; 1940 } 1941 return true; 1942} 1943 1944/* Determine for each subscript in the data dependence relation DDR 1945 the distance. */ 1946 1947void 1948compute_subscript_distance (struct data_dependence_relation *ddr) 1949{ 1950 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) 1951 { 1952 unsigned int i; 1953 1954 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 1955 { 1956 tree conflicts_a, conflicts_b, difference; 1957 struct subscript *subscript; 1958 1959 subscript = DDR_SUBSCRIPT (ddr, i); 1960 conflicts_a = SUB_CONFLICTS_IN_A (subscript); 1961 conflicts_b = SUB_CONFLICTS_IN_B (subscript); 1962 1963 if (TREE_CODE (conflicts_a) == TREE_VEC) 1964 { 1965 if (!all_chrecs_equal_p (conflicts_a)) 1966 { 1967 SUB_DISTANCE (subscript) = chrec_dont_know; 1968 return; 1969 } 1970 else 1971 conflicts_a = TREE_VEC_ELT (conflicts_a, 0); 1972 } 1973 1974 if (TREE_CODE (conflicts_b) == TREE_VEC) 1975 { 1976 if (!all_chrecs_equal_p (conflicts_b)) 1977 { 1978 SUB_DISTANCE (subscript) = chrec_dont_know; 1979 return; 1980 } 1981 else 1982 conflicts_b = TREE_VEC_ELT (conflicts_b, 0); 1983 } 1984 1985 difference = chrec_fold_minus 1986 (integer_type_node, conflicts_b, conflicts_a); 1987 1988 if (evolution_function_is_constant_p (difference)) 1989 SUB_DISTANCE (subscript) = difference; 1990 1991 else 1992 SUB_DISTANCE (subscript) = chrec_dont_know; 1993 } 1994 } 1995} 1996 1997/* Initialize a ddr. */ 1998 1999struct data_dependence_relation * 2000initialize_data_dependence_relation (struct data_reference *a, 2001 struct data_reference *b) 2002{ 2003 struct data_dependence_relation *res; 2004 bool differ_p; 2005 unsigned int i; 2006 2007 res = xmalloc (sizeof (struct data_dependence_relation)); 2008 DDR_A (res) = a; 2009 DDR_B (res) = b; 2010 2011 if (a == NULL || b == NULL) 2012 { 2013 DDR_ARE_DEPENDENT (res) = chrec_dont_know; 2014 return res; 2015 } 2016 2017 /* When A and B are arrays and their dimensions differ, we directly 2018 initialize the relation to "there is no dependence": chrec_known. */ 2019 if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b) 2020 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)) 2021 { 2022 DDR_ARE_DEPENDENT (res) = chrec_known; 2023 return res; 2024 } 2025 2026 /* Compare the bases of the data-refs. */ 2027 if (!base_addr_differ_p (a, b, &differ_p)) 2028 { 2029 /* Can't determine whether the data-refs access the same memory 2030 region. */ 2031 DDR_ARE_DEPENDENT (res) = chrec_dont_know; 2032 return res; 2033 } 2034 if (differ_p) 2035 { 2036 DDR_ARE_DEPENDENT (res) = chrec_known; 2037 return res; 2038 } 2039 2040 DDR_AFFINE_P (res) = true; 2041 DDR_ARE_DEPENDENT (res) = NULL_TREE; 2042 DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a)); 2043 DDR_SIZE_VECT (res) = 0; 2044 DDR_DIR_VECTS (res) = NULL; 2045 DDR_DIST_VECTS (res) = NULL; 2046 2047 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) 2048 { 2049 struct subscript *subscript; 2050 2051 subscript = xmalloc (sizeof (struct subscript)); 2052 SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know; 2053 SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know; 2054 SUB_LAST_CONFLICT (subscript) = chrec_dont_know; 2055 SUB_DISTANCE (subscript) = chrec_dont_know; 2056 VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript); 2057 } 2058 2059 return res; 2060} 2061 2062/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap 2063 description. */ 2064 2065static inline void 2066finalize_ddr_dependent (struct data_dependence_relation *ddr, 2067 tree chrec) 2068{ 2069 if (dump_file && (dump_flags & TDF_DETAILS)) 2070 { 2071 fprintf (dump_file, "(dependence classified: "); 2072 print_generic_expr (dump_file, chrec, 0); 2073 fprintf (dump_file, ")\n"); 2074 } 2075 2076 DDR_ARE_DEPENDENT (ddr) = chrec; 2077 varray_clear (DDR_SUBSCRIPTS (ddr)); 2078} 2079 2080/* The dependence relation DDR cannot be represented by a distance 2081 vector. */ 2082 2083static inline void 2084non_affine_dependence_relation (struct data_dependence_relation *ddr) 2085{ 2086 if (dump_file && (dump_flags & TDF_DETAILS)) 2087 fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n"); 2088 2089 DDR_AFFINE_P (ddr) = false; 2090} 2091 2092 2093 2094/* This section contains the classic Banerjee tests. */ 2095 2096/* Returns true iff CHREC_A and CHREC_B are not dependent on any index 2097 variables, i.e., if the ZIV (Zero Index Variable) test is true. */ 2098 2099static inline bool 2100ziv_subscript_p (tree chrec_a, 2101 tree chrec_b) 2102{ 2103 return (evolution_function_is_constant_p (chrec_a) 2104 && evolution_function_is_constant_p (chrec_b)); 2105} 2106 2107/* Returns true iff CHREC_A and CHREC_B are dependent on an index 2108 variable, i.e., if the SIV (Single Index Variable) test is true. */ 2109 2110static bool 2111siv_subscript_p (tree chrec_a, 2112 tree chrec_b) 2113{ 2114 if ((evolution_function_is_constant_p (chrec_a) 2115 && evolution_function_is_univariate_p (chrec_b)) 2116 || (evolution_function_is_constant_p (chrec_b) 2117 && evolution_function_is_univariate_p (chrec_a))) 2118 return true; 2119 2120 if (evolution_function_is_univariate_p (chrec_a) 2121 && evolution_function_is_univariate_p (chrec_b)) 2122 { 2123 switch (TREE_CODE (chrec_a)) 2124 { 2125 case POLYNOMIAL_CHREC: 2126 switch (TREE_CODE (chrec_b)) 2127 { 2128 case POLYNOMIAL_CHREC: 2129 if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b)) 2130 return false; 2131 2132 default: 2133 return true; 2134 } 2135 2136 default: 2137 return true; 2138 } 2139 } 2140 2141 return false; 2142} 2143 2144/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and 2145 *OVERLAPS_B are initialized to the functions that describe the 2146 relation between the elements accessed twice by CHREC_A and 2147 CHREC_B. For k >= 0, the following property is verified: 2148 2149 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 2150 2151static void 2152analyze_ziv_subscript (tree chrec_a, 2153 tree chrec_b, 2154 tree *overlaps_a, 2155 tree *overlaps_b, 2156 tree *last_conflicts) 2157{ 2158 tree difference; 2159 2160 if (dump_file && (dump_flags & TDF_DETAILS)) 2161 fprintf (dump_file, "(analyze_ziv_subscript \n"); 2162 2163 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); 2164 2165 switch (TREE_CODE (difference)) 2166 { 2167 case INTEGER_CST: 2168 if (integer_zerop (difference)) 2169 { 2170 /* The difference is equal to zero: the accessed index 2171 overlaps for each iteration in the loop. */ 2172 *overlaps_a = integer_zero_node; 2173 *overlaps_b = integer_zero_node; 2174 *last_conflicts = chrec_dont_know; 2175 } 2176 else 2177 { 2178 /* The accesses do not overlap. */ 2179 *overlaps_a = chrec_known; 2180 *overlaps_b = chrec_known; 2181 *last_conflicts = integer_zero_node; 2182 } 2183 break; 2184 2185 default: 2186 /* We're not sure whether the indexes overlap. For the moment, 2187 conservatively answer "don't know". */ 2188 *overlaps_a = chrec_dont_know; 2189 *overlaps_b = chrec_dont_know; 2190 *last_conflicts = chrec_dont_know; 2191 break; 2192 } 2193 2194 if (dump_file && (dump_flags & TDF_DETAILS)) 2195 fprintf (dump_file, ")\n"); 2196} 2197 2198/* Get the real or estimated number of iterations for LOOPNUM, whichever is 2199 available. Return the number of iterations as a tree, or NULL_TREE if 2200 we don't know. */ 2201 2202static tree 2203get_number_of_iters_for_loop (int loopnum) 2204{ 2205 tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]); 2206 2207 if (TREE_CODE (numiter) != INTEGER_CST) 2208 numiter = current_loops->parray[loopnum]->estimated_nb_iterations; 2209 if (chrec_contains_undetermined (numiter)) 2210 return NULL_TREE; 2211 return numiter; 2212} 2213 2214/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a 2215 constant, and CHREC_B is an affine function. *OVERLAPS_A and 2216 *OVERLAPS_B are initialized to the functions that describe the 2217 relation between the elements accessed twice by CHREC_A and 2218 CHREC_B. For k >= 0, the following property is verified: 2219 2220 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 2221 2222static void 2223analyze_siv_subscript_cst_affine (tree chrec_a, 2224 tree chrec_b, 2225 tree *overlaps_a, 2226 tree *overlaps_b, 2227 tree *last_conflicts) 2228{ 2229 bool value0, value1, value2; 2230 tree difference = chrec_fold_minus 2231 (integer_type_node, CHREC_LEFT (chrec_b), chrec_a); 2232 2233 if (!chrec_is_positive (initial_condition (difference), &value0)) 2234 { 2235 *overlaps_a = chrec_dont_know; 2236 *overlaps_b = chrec_dont_know; 2237 *last_conflicts = chrec_dont_know; 2238 return; 2239 } 2240 else 2241 { 2242 if (value0 == false) 2243 { 2244 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1)) 2245 { 2246 *overlaps_a = chrec_dont_know; 2247 *overlaps_b = chrec_dont_know; 2248 *last_conflicts = chrec_dont_know; 2249 return; 2250 } 2251 else 2252 { 2253 if (value1 == true) 2254 { 2255 /* Example: 2256 chrec_a = 12 2257 chrec_b = {10, +, 1} 2258 */ 2259 2260 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) 2261 { 2262 tree numiter; 2263 int loopnum = CHREC_VARIABLE (chrec_b); 2264 2265 *overlaps_a = integer_zero_node; 2266 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node, 2267 fold_build1 (ABS_EXPR, 2268 integer_type_node, 2269 difference), 2270 CHREC_RIGHT (chrec_b)); 2271 *last_conflicts = integer_one_node; 2272 2273 2274 /* Perform weak-zero siv test to see if overlap is 2275 outside the loop bounds. */ 2276 numiter = get_number_of_iters_for_loop (loopnum); 2277 2278 if (numiter != NULL_TREE 2279 && TREE_CODE (*overlaps_b) == INTEGER_CST 2280 && tree_int_cst_lt (numiter, *overlaps_b)) 2281 { 2282 *overlaps_a = chrec_known; 2283 *overlaps_b = chrec_known; 2284 *last_conflicts = integer_zero_node; 2285 return; 2286 } 2287 return; 2288 } 2289 2290 /* When the step does not divide the difference, there are 2291 no overlaps. */ 2292 else 2293 { 2294 *overlaps_a = chrec_known; 2295 *overlaps_b = chrec_known; 2296 *last_conflicts = integer_zero_node; 2297 return; 2298 } 2299 } 2300 2301 else 2302 { 2303 /* Example: 2304 chrec_a = 12 2305 chrec_b = {10, +, -1} 2306 2307 In this case, chrec_a will not overlap with chrec_b. */ 2308 *overlaps_a = chrec_known; 2309 *overlaps_b = chrec_known; 2310 *last_conflicts = integer_zero_node; 2311 return; 2312 } 2313 } 2314 } 2315 else 2316 { 2317 if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) 2318 { 2319 *overlaps_a = chrec_dont_know; 2320 *overlaps_b = chrec_dont_know; 2321 *last_conflicts = chrec_dont_know; 2322 return; 2323 } 2324 else 2325 { 2326 if (value2 == false) 2327 { 2328 /* Example: 2329 chrec_a = 3 2330 chrec_b = {10, +, -1} 2331 */ 2332 if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) 2333 { 2334 tree numiter; 2335 int loopnum = CHREC_VARIABLE (chrec_b); 2336 2337 *overlaps_a = integer_zero_node; 2338 *overlaps_b = fold_build2 (EXACT_DIV_EXPR, 2339 integer_type_node, difference, 2340 CHREC_RIGHT (chrec_b)); 2341 *last_conflicts = integer_one_node; 2342 2343 /* Perform weak-zero siv test to see if overlap is 2344 outside the loop bounds. */ 2345 numiter = get_number_of_iters_for_loop (loopnum); 2346 2347 if (numiter != NULL_TREE 2348 && TREE_CODE (*overlaps_b) == INTEGER_CST 2349 && tree_int_cst_lt (numiter, *overlaps_b)) 2350 { 2351 *overlaps_a = chrec_known; 2352 *overlaps_b = chrec_known; 2353 *last_conflicts = integer_zero_node; 2354 return; 2355 } 2356 return; 2357 } 2358 2359 /* When the step does not divide the difference, there 2360 are no overlaps. */ 2361 else 2362 { 2363 *overlaps_a = chrec_known; 2364 *overlaps_b = chrec_known; 2365 *last_conflicts = integer_zero_node; 2366 return; 2367 } 2368 } 2369 else 2370 { 2371 /* Example: 2372 chrec_a = 3 2373 chrec_b = {4, +, 1} 2374 2375 In this case, chrec_a will not overlap with chrec_b. */ 2376 *overlaps_a = chrec_known; 2377 *overlaps_b = chrec_known; 2378 *last_conflicts = integer_zero_node; 2379 return; 2380 } 2381 } 2382 } 2383 } 2384} 2385 2386/* Helper recursive function for initializing the matrix A. Returns 2387 the initial value of CHREC. */ 2388 2389static int 2390initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) 2391{ 2392 gcc_assert (chrec); 2393 2394 if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 2395 return int_cst_value (chrec); 2396 2397 A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); 2398 return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); 2399} 2400 2401#define FLOOR_DIV(x,y) ((x) / (y)) 2402 2403/* Solves the special case of the Diophantine equation: 2404 | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B) 2405 2406 Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the 2407 number of iterations that loops X and Y run. The overlaps will be 2408 constructed as evolutions in dimension DIM. */ 2409 2410static void 2411compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, 2412 tree *overlaps_a, tree *overlaps_b, 2413 tree *last_conflicts, int dim) 2414{ 2415 if (((step_a > 0 && step_b > 0) 2416 || (step_a < 0 && step_b < 0))) 2417 { 2418 int step_overlaps_a, step_overlaps_b; 2419 int gcd_steps_a_b, last_conflict, tau2; 2420 2421 gcd_steps_a_b = gcd (step_a, step_b); 2422 step_overlaps_a = step_b / gcd_steps_a_b; 2423 step_overlaps_b = step_a / gcd_steps_a_b; 2424 2425 tau2 = FLOOR_DIV (niter, step_overlaps_a); 2426 tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); 2427 last_conflict = tau2; 2428 2429 *overlaps_a = build_polynomial_chrec 2430 (dim, integer_zero_node, 2431 build_int_cst (NULL_TREE, step_overlaps_a)); 2432 *overlaps_b = build_polynomial_chrec 2433 (dim, integer_zero_node, 2434 build_int_cst (NULL_TREE, step_overlaps_b)); 2435 *last_conflicts = build_int_cst (NULL_TREE, last_conflict); 2436 } 2437 2438 else 2439 { 2440 *overlaps_a = integer_zero_node; 2441 *overlaps_b = integer_zero_node; 2442 *last_conflicts = integer_zero_node; 2443 } 2444} 2445 2446 2447/* Solves the special case of a Diophantine equation where CHREC_A is 2448 an affine bivariate function, and CHREC_B is an affine univariate 2449 function. For example, 2450 2451 | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z 2452 2453 has the following overlapping functions: 2454 2455 | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v 2456 | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v 2457 | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v 2458 2459 FORNOW: This is a specialized implementation for a case occurring in 2460 a common benchmark. Implement the general algorithm. */ 2461 2462static void 2463compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 2464 tree *overlaps_a, tree *overlaps_b, 2465 tree *last_conflicts) 2466{ 2467 bool xz_p, yz_p, xyz_p; 2468 int step_x, step_y, step_z; 2469 int niter_x, niter_y, niter_z, niter; 2470 tree numiter_x, numiter_y, numiter_z; 2471 tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz; 2472 tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz; 2473 tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz; 2474 2475 step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a))); 2476 step_y = int_cst_value (CHREC_RIGHT (chrec_a)); 2477 step_z = int_cst_value (CHREC_RIGHT (chrec_b)); 2478 2479 numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a))); 2480 numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 2481 numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); 2482 2483 if (numiter_x == NULL_TREE || numiter_y == NULL_TREE 2484 || numiter_z == NULL_TREE) 2485 { 2486 *overlaps_a = chrec_dont_know; 2487 *overlaps_b = chrec_dont_know; 2488 *last_conflicts = chrec_dont_know; 2489 return; 2490 } 2491 2492 niter_x = int_cst_value (numiter_x); 2493 niter_y = int_cst_value (numiter_y); 2494 niter_z = int_cst_value (numiter_z); 2495 2496 niter = MIN (niter_x, niter_z); 2497 compute_overlap_steps_for_affine_univar (niter, step_x, step_z, 2498 &overlaps_a_xz, 2499 &overlaps_b_xz, 2500 &last_conflicts_xz, 1); 2501 niter = MIN (niter_y, niter_z); 2502 compute_overlap_steps_for_affine_univar (niter, step_y, step_z, 2503 &overlaps_a_yz, 2504 &overlaps_b_yz, 2505 &last_conflicts_yz, 2); 2506 niter = MIN (niter_x, niter_z); 2507 niter = MIN (niter_y, niter); 2508 compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z, 2509 &overlaps_a_xyz, 2510 &overlaps_b_xyz, 2511 &last_conflicts_xyz, 3); 2512 2513 xz_p = !integer_zerop (last_conflicts_xz); 2514 yz_p = !integer_zerop (last_conflicts_yz); 2515 xyz_p = !integer_zerop (last_conflicts_xyz); 2516 2517 if (xz_p || yz_p || xyz_p) 2518 { 2519 *overlaps_a = make_tree_vec (2); 2520 TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node; 2521 TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node; 2522 *overlaps_b = integer_zero_node; 2523 if (xz_p) 2524 { 2525 TREE_VEC_ELT (*overlaps_a, 0) = 2526 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), 2527 overlaps_a_xz); 2528 *overlaps_b = 2529 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz); 2530 *last_conflicts = last_conflicts_xz; 2531 } 2532 if (yz_p) 2533 { 2534 TREE_VEC_ELT (*overlaps_a, 1) = 2535 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), 2536 overlaps_a_yz); 2537 *overlaps_b = 2538 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz); 2539 *last_conflicts = last_conflicts_yz; 2540 } 2541 if (xyz_p) 2542 { 2543 TREE_VEC_ELT (*overlaps_a, 0) = 2544 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0), 2545 overlaps_a_xyz); 2546 TREE_VEC_ELT (*overlaps_a, 1) = 2547 chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1), 2548 overlaps_a_xyz); 2549 *overlaps_b = 2550 chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz); 2551 *last_conflicts = last_conflicts_xyz; 2552 } 2553 } 2554 else 2555 { 2556 *overlaps_a = integer_zero_node; 2557 *overlaps_b = integer_zero_node; 2558 *last_conflicts = integer_zero_node; 2559 } 2560} 2561 2562/* Determines the overlapping elements due to accesses CHREC_A and 2563 CHREC_B, that are affine functions. This is a part of the 2564 subscript analyzer. */ 2565 2566static void 2567analyze_subscript_affine_affine (tree chrec_a, 2568 tree chrec_b, 2569 tree *overlaps_a, 2570 tree *overlaps_b, 2571 tree *last_conflicts) 2572{ 2573 unsigned nb_vars_a, nb_vars_b, dim; 2574 int init_a, init_b, gamma, gcd_alpha_beta; 2575 int tau1, tau2; 2576 lambda_matrix A, U, S; 2577 tree difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); 2578 2579 if (integer_zerop (difference)) 2580 { 2581 /* The difference is equal to zero: the accessed index 2582 overlaps for each iteration in the loop. */ 2583 *overlaps_a = integer_zero_node; 2584 *overlaps_b = integer_zero_node; 2585 *last_conflicts = chrec_dont_know; 2586 return; 2587 } 2588 if (dump_file && (dump_flags & TDF_DETAILS)) 2589 fprintf (dump_file, "(analyze_subscript_affine_affine \n"); 2590 2591 /* For determining the initial intersection, we have to solve a 2592 Diophantine equation. This is the most time consuming part. 2593 2594 For answering to the question: "Is there a dependence?" we have 2595 to prove that there exists a solution to the Diophantine 2596 equation, and that the solution is in the iteration domain, 2597 i.e. the solution is positive or zero, and that the solution 2598 happens before the upper bound loop.nb_iterations. Otherwise 2599 there is no dependence. This function outputs a description of 2600 the iterations that hold the intersections. */ 2601 2602 2603 nb_vars_a = nb_vars_in_chrec (chrec_a); 2604 nb_vars_b = nb_vars_in_chrec (chrec_b); 2605 2606 dim = nb_vars_a + nb_vars_b; 2607 U = lambda_matrix_new (dim, dim); 2608 A = lambda_matrix_new (dim, 1); 2609 S = lambda_matrix_new (dim, 1); 2610 2611 init_a = initialize_matrix_A (A, chrec_a, 0, 1); 2612 init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1); 2613 gamma = init_b - init_a; 2614 2615 /* Don't do all the hard work of solving the Diophantine equation 2616 when we already know the solution: for example, 2617 | {3, +, 1}_1 2618 | {3, +, 4}_2 2619 | gamma = 3 - 3 = 0. 2620 Then the first overlap occurs during the first iterations: 2621 | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) 2622 */ 2623 if (gamma == 0) 2624 { 2625 if (nb_vars_a == 1 && nb_vars_b == 1) 2626 { 2627 int step_a, step_b; 2628 int niter, niter_a, niter_b; 2629 tree numiter_a, numiter_b; 2630 2631 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 2632 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); 2633 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) 2634 { 2635 *overlaps_a = chrec_dont_know; 2636 *overlaps_b = chrec_dont_know; 2637 *last_conflicts = chrec_dont_know; 2638 return; 2639 } 2640 2641 niter_a = int_cst_value (numiter_a); 2642 niter_b = int_cst_value (numiter_b); 2643 niter = MIN (niter_a, niter_b); 2644 2645 step_a = int_cst_value (CHREC_RIGHT (chrec_a)); 2646 step_b = int_cst_value (CHREC_RIGHT (chrec_b)); 2647 2648 compute_overlap_steps_for_affine_univar (niter, step_a, step_b, 2649 overlaps_a, overlaps_b, 2650 last_conflicts, 1); 2651 } 2652 2653 else if (nb_vars_a == 2 && nb_vars_b == 1) 2654 compute_overlap_steps_for_affine_1_2 2655 (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); 2656 2657 else if (nb_vars_a == 1 && nb_vars_b == 2) 2658 compute_overlap_steps_for_affine_1_2 2659 (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts); 2660 2661 else 2662 { 2663 *overlaps_a = chrec_dont_know; 2664 *overlaps_b = chrec_dont_know; 2665 *last_conflicts = chrec_dont_know; 2666 } 2667 return; 2668 } 2669 2670 /* U.A = S */ 2671 lambda_matrix_right_hermite (A, dim, 1, S, U); 2672 2673 if (S[0][0] < 0) 2674 { 2675 S[0][0] *= -1; 2676 lambda_matrix_row_negate (U, dim, 0); 2677 } 2678 gcd_alpha_beta = S[0][0]; 2679 2680 /* The classic "gcd-test". */ 2681 if (!int_divides_p (gcd_alpha_beta, gamma)) 2682 { 2683 /* The "gcd-test" has determined that there is no integer 2684 solution, i.e. there is no dependence. */ 2685 *overlaps_a = chrec_known; 2686 *overlaps_b = chrec_known; 2687 *last_conflicts = integer_zero_node; 2688 } 2689 2690 /* Both access functions are univariate. This includes SIV and MIV cases. */ 2691 else if (nb_vars_a == 1 && nb_vars_b == 1) 2692 { 2693 /* Both functions should have the same evolution sign. */ 2694 if (((A[0][0] > 0 && -A[1][0] > 0) 2695 || (A[0][0] < 0 && -A[1][0] < 0))) 2696 { 2697 /* The solutions are given by: 2698 | 2699 | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0] 2700 | [u21 u22] [y0] 2701 2702 For a given integer t. Using the following variables, 2703 2704 | i0 = u11 * gamma / gcd_alpha_beta 2705 | j0 = u12 * gamma / gcd_alpha_beta 2706 | i1 = u21 2707 | j1 = u22 2708 2709 the solutions are: 2710 2711 | x0 = i0 + i1 * t, 2712 | y0 = j0 + j1 * t. */ 2713 2714 int i0, j0, i1, j1; 2715 2716 /* X0 and Y0 are the first iterations for which there is a 2717 dependence. X0, Y0 are two solutions of the Diophantine 2718 equation: chrec_a (X0) = chrec_b (Y0). */ 2719 int x0, y0; 2720 int niter, niter_a, niter_b; 2721 tree numiter_a, numiter_b; 2722 2723 numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 2724 numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); 2725 2726 if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) 2727 { 2728 *overlaps_a = chrec_dont_know; 2729 *overlaps_b = chrec_dont_know; 2730 *last_conflicts = chrec_dont_know; 2731 return; 2732 } 2733 2734 niter_a = int_cst_value (numiter_a); 2735 niter_b = int_cst_value (numiter_b); 2736 niter = MIN (niter_a, niter_b); 2737 2738 i0 = U[0][0] * gamma / gcd_alpha_beta; 2739 j0 = U[0][1] * gamma / gcd_alpha_beta; 2740 i1 = U[1][0]; 2741 j1 = U[1][1]; 2742 2743 if ((i1 == 0 && i0 < 0) 2744 || (j1 == 0 && j0 < 0)) 2745 { 2746 /* There is no solution. 2747 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 2748 falls in here, but for the moment we don't look at the 2749 upper bound of the iteration domain. */ 2750 *overlaps_a = chrec_known; 2751 *overlaps_b = chrec_known; 2752 *last_conflicts = integer_zero_node; 2753 } 2754 2755 else 2756 { 2757 if (i1 > 0) 2758 { 2759 tau1 = CEIL (-i0, i1); 2760 tau2 = FLOOR_DIV (niter - i0, i1); 2761 2762 if (j1 > 0) 2763 { 2764 int last_conflict, min_multiple; 2765 tau1 = MAX (tau1, CEIL (-j0, j1)); 2766 tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1)); 2767 2768 x0 = i1 * tau1 + i0; 2769 y0 = j1 * tau1 + j0; 2770 2771 /* At this point (x0, y0) is one of the 2772 solutions to the Diophantine equation. The 2773 next step has to compute the smallest 2774 positive solution: the first conflicts. */ 2775 min_multiple = MIN (x0 / i1, y0 / j1); 2776 x0 -= i1 * min_multiple; 2777 y0 -= j1 * min_multiple; 2778 2779 tau1 = (x0 - i0)/i1; 2780 last_conflict = tau2 - tau1; 2781 2782 /* If the overlap occurs outside of the bounds of the 2783 loop, there is no dependence. */ 2784 if (x0 > niter || y0 > niter) 2785 2786 { 2787 *overlaps_a = chrec_known; 2788 *overlaps_b = chrec_known; 2789 *last_conflicts = integer_zero_node; 2790 } 2791 else 2792 { 2793 *overlaps_a = build_polynomial_chrec 2794 (1, 2795 build_int_cst (NULL_TREE, x0), 2796 build_int_cst (NULL_TREE, i1)); 2797 *overlaps_b = build_polynomial_chrec 2798 (1, 2799 build_int_cst (NULL_TREE, y0), 2800 build_int_cst (NULL_TREE, j1)); 2801 *last_conflicts = build_int_cst (NULL_TREE, last_conflict); 2802 } 2803 } 2804 else 2805 { 2806 /* FIXME: For the moment, the upper bound of the 2807 iteration domain for j is not checked. */ 2808 *overlaps_a = chrec_dont_know; 2809 *overlaps_b = chrec_dont_know; 2810 *last_conflicts = chrec_dont_know; 2811 } 2812 } 2813 2814 else 2815 { 2816 /* FIXME: For the moment, the upper bound of the 2817 iteration domain for i is not checked. */ 2818 *overlaps_a = chrec_dont_know; 2819 *overlaps_b = chrec_dont_know; 2820 *last_conflicts = chrec_dont_know; 2821 } 2822 } 2823 } 2824 else 2825 { 2826 *overlaps_a = chrec_dont_know; 2827 *overlaps_b = chrec_dont_know; 2828 *last_conflicts = chrec_dont_know; 2829 } 2830 } 2831 2832 else 2833 { 2834 *overlaps_a = chrec_dont_know; 2835 *overlaps_b = chrec_dont_know; 2836 *last_conflicts = chrec_dont_know; 2837 } 2838 2839 2840 if (dump_file && (dump_flags & TDF_DETAILS)) 2841 { 2842 fprintf (dump_file, " (overlaps_a = "); 2843 print_generic_expr (dump_file, *overlaps_a, 0); 2844 fprintf (dump_file, ")\n (overlaps_b = "); 2845 print_generic_expr (dump_file, *overlaps_b, 0); 2846 fprintf (dump_file, ")\n"); 2847 } 2848 2849 if (dump_file && (dump_flags & TDF_DETAILS)) 2850 fprintf (dump_file, ")\n"); 2851} 2852 2853/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and 2854 *OVERLAPS_B are initialized to the functions that describe the 2855 relation between the elements accessed twice by CHREC_A and 2856 CHREC_B. For k >= 0, the following property is verified: 2857 2858 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 2859 2860static void 2861analyze_siv_subscript (tree chrec_a, 2862 tree chrec_b, 2863 tree *overlaps_a, 2864 tree *overlaps_b, 2865 tree *last_conflicts) 2866{ 2867 if (dump_file && (dump_flags & TDF_DETAILS)) 2868 fprintf (dump_file, "(analyze_siv_subscript \n"); 2869 2870 if (evolution_function_is_constant_p (chrec_a) 2871 && evolution_function_is_affine_p (chrec_b)) 2872 analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 2873 overlaps_a, overlaps_b, last_conflicts); 2874 2875 else if (evolution_function_is_affine_p (chrec_a) 2876 && evolution_function_is_constant_p (chrec_b)) 2877 analyze_siv_subscript_cst_affine (chrec_b, chrec_a, 2878 overlaps_b, overlaps_a, last_conflicts); 2879 2880 else if (evolution_function_is_affine_p (chrec_a) 2881 && evolution_function_is_affine_p (chrec_b)) 2882 analyze_subscript_affine_affine (chrec_a, chrec_b, 2883 overlaps_a, overlaps_b, last_conflicts); 2884 else 2885 { 2886 *overlaps_a = chrec_dont_know; 2887 *overlaps_b = chrec_dont_know; 2888 *last_conflicts = chrec_dont_know; 2889 } 2890 2891 if (dump_file && (dump_flags & TDF_DETAILS)) 2892 fprintf (dump_file, ")\n"); 2893} 2894 2895/* Return true when the evolution steps of an affine CHREC divide the 2896 constant CST. */ 2897 2898static bool 2899chrec_steps_divide_constant_p (tree chrec, 2900 tree cst) 2901{ 2902 switch (TREE_CODE (chrec)) 2903 { 2904 case POLYNOMIAL_CHREC: 2905 return (tree_fold_divides_p (CHREC_RIGHT (chrec), cst) 2906 && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst)); 2907 2908 default: 2909 /* On the initial condition, return true. */ 2910 return true; 2911 } 2912} 2913 2914/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and 2915 *OVERLAPS_B are initialized to the functions that describe the 2916 relation between the elements accessed twice by CHREC_A and 2917 CHREC_B. For k >= 0, the following property is verified: 2918 2919 CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 2920 2921static void 2922analyze_miv_subscript (tree chrec_a, 2923 tree chrec_b, 2924 tree *overlaps_a, 2925 tree *overlaps_b, 2926 tree *last_conflicts) 2927{ 2928 /* FIXME: This is a MIV subscript, not yet handled. 2929 Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from 2930 (A[i] vs. A[j]). 2931 2932 In the SIV test we had to solve a Diophantine equation with two 2933 variables. In the MIV case we have to solve a Diophantine 2934 equation with 2*n variables (if the subscript uses n IVs). 2935 */ 2936 tree difference; 2937 2938 if (dump_file && (dump_flags & TDF_DETAILS)) 2939 fprintf (dump_file, "(analyze_miv_subscript \n"); 2940 2941 difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); 2942 2943 if (chrec_zerop (difference)) 2944 { 2945 /* Access functions are the same: all the elements are accessed 2946 in the same order. */ 2947 *overlaps_a = integer_zero_node; 2948 *overlaps_b = integer_zero_node; 2949 *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 2950 2951 } 2952 2953 else if (evolution_function_is_constant_p (difference) 2954 /* For the moment, the following is verified: 2955 evolution_function_is_affine_multivariate_p (chrec_a) */ 2956 && !chrec_steps_divide_constant_p (chrec_a, difference)) 2957 { 2958 /* testsuite/.../ssa-chrec-33.c 2959 {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 2960 2961 The difference is 1, and the evolution steps are equal to 2, 2962 consequently there are no overlapping elements. */ 2963 *overlaps_a = chrec_known; 2964 *overlaps_b = chrec_known; 2965 *last_conflicts = integer_zero_node; 2966 } 2967 2968 else if (evolution_function_is_affine_multivariate_p (chrec_a) 2969 && evolution_function_is_affine_multivariate_p (chrec_b)) 2970 { 2971 /* testsuite/.../ssa-chrec-35.c 2972 {0, +, 1}_2 vs. {0, +, 1}_3 2973 the overlapping elements are respectively located at iterations: 2974 {0, +, 1}_x and {0, +, 1}_x, 2975 in other words, we have the equality: 2976 {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x) 2977 2978 Other examples: 2979 {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = 2980 {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y) 2981 2982 {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = 2983 {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) 2984 */ 2985 analyze_subscript_affine_affine (chrec_a, chrec_b, 2986 overlaps_a, overlaps_b, last_conflicts); 2987 } 2988 2989 else 2990 { 2991 /* When the analysis is too difficult, answer "don't know". */ 2992 *overlaps_a = chrec_dont_know; 2993 *overlaps_b = chrec_dont_know; 2994 *last_conflicts = chrec_dont_know; 2995 } 2996 2997 if (dump_file && (dump_flags & TDF_DETAILS)) 2998 fprintf (dump_file, ")\n"); 2999} 3000 3001/* Determines the iterations for which CHREC_A is equal to CHREC_B. 3002 OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with 3003 two functions that describe the iterations that contain conflicting 3004 elements. 3005 3006 Remark: For an integer k >= 0, the following equality is true: 3007 3008 CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)). 3009*/ 3010 3011static void 3012analyze_overlapping_iterations (tree chrec_a, 3013 tree chrec_b, 3014 tree *overlap_iterations_a, 3015 tree *overlap_iterations_b, 3016 tree *last_conflicts) 3017{ 3018 if (dump_file && (dump_flags & TDF_DETAILS)) 3019 { 3020 fprintf (dump_file, "(analyze_overlapping_iterations \n"); 3021 fprintf (dump_file, " (chrec_a = "); 3022 print_generic_expr (dump_file, chrec_a, 0); 3023 fprintf (dump_file, ")\n chrec_b = "); 3024 print_generic_expr (dump_file, chrec_b, 0); 3025 fprintf (dump_file, ")\n"); 3026 } 3027 3028 if (chrec_a == NULL_TREE 3029 || chrec_b == NULL_TREE 3030 || chrec_contains_undetermined (chrec_a) 3031 || chrec_contains_undetermined (chrec_b) 3032 || chrec_contains_symbols (chrec_a) 3033 || chrec_contains_symbols (chrec_b)) 3034 { 3035 *overlap_iterations_a = chrec_dont_know; 3036 *overlap_iterations_b = chrec_dont_know; 3037 } 3038 3039 else if (ziv_subscript_p (chrec_a, chrec_b)) 3040 analyze_ziv_subscript (chrec_a, chrec_b, 3041 overlap_iterations_a, overlap_iterations_b, 3042 last_conflicts); 3043 3044 else if (siv_subscript_p (chrec_a, chrec_b)) 3045 analyze_siv_subscript (chrec_a, chrec_b, 3046 overlap_iterations_a, overlap_iterations_b, 3047 last_conflicts); 3048 3049 else 3050 analyze_miv_subscript (chrec_a, chrec_b, 3051 overlap_iterations_a, overlap_iterations_b, 3052 last_conflicts); 3053 3054 if (dump_file && (dump_flags & TDF_DETAILS)) 3055 { 3056 fprintf (dump_file, " (overlap_iterations_a = "); 3057 print_generic_expr (dump_file, *overlap_iterations_a, 0); 3058 fprintf (dump_file, ")\n (overlap_iterations_b = "); 3059 print_generic_expr (dump_file, *overlap_iterations_b, 0); 3060 fprintf (dump_file, ")\n"); 3061 } 3062} 3063 3064 3065 3066/* This section contains the affine functions dependences detector. */ 3067 3068/* Computes the conflicting iterations, and initialize DDR. */ 3069 3070static void 3071subscript_dependence_tester (struct data_dependence_relation *ddr) 3072{ 3073 unsigned int i; 3074 struct data_reference *dra = DDR_A (ddr); 3075 struct data_reference *drb = DDR_B (ddr); 3076 tree last_conflicts; 3077 3078 if (dump_file && (dump_flags & TDF_DETAILS)) 3079 fprintf (dump_file, "(subscript_dependence_tester \n"); 3080 3081 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 3082 { 3083 tree overlaps_a, overlaps_b; 3084 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); 3085 3086 analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 3087 DR_ACCESS_FN (drb, i), 3088 &overlaps_a, &overlaps_b, 3089 &last_conflicts); 3090 3091 if (chrec_contains_undetermined (overlaps_a) 3092 || chrec_contains_undetermined (overlaps_b)) 3093 { 3094 finalize_ddr_dependent (ddr, chrec_dont_know); 3095 break; 3096 } 3097 3098 else if (overlaps_a == chrec_known 3099 || overlaps_b == chrec_known) 3100 { 3101 finalize_ddr_dependent (ddr, chrec_known); 3102 break; 3103 } 3104 3105 else 3106 { 3107 SUB_CONFLICTS_IN_A (subscript) = overlaps_a; 3108 SUB_CONFLICTS_IN_B (subscript) = overlaps_b; 3109 SUB_LAST_CONFLICT (subscript) = last_conflicts; 3110 } 3111 } 3112 3113 if (dump_file && (dump_flags & TDF_DETAILS)) 3114 fprintf (dump_file, ")\n"); 3115} 3116 3117/* Compute the classic per loop distance vector. 3118 3119 DDR is the data dependence relation to build a vector from. 3120 NB_LOOPS is the total number of loops we are considering. 3121 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed 3122 loop nest. 3123 Return FALSE when fail to represent the data dependence as a distance 3124 vector. 3125 Return TRUE otherwise. */ 3126 3127static bool 3128build_classic_dist_vector (struct data_dependence_relation *ddr, 3129 int nb_loops, int first_loop_depth) 3130{ 3131 unsigned i; 3132 lambda_vector dist_v, init_v; 3133 bool init_b = false; 3134 3135 DDR_SIZE_VECT (ddr) = nb_loops; 3136 dist_v = lambda_vector_new (nb_loops); 3137 init_v = lambda_vector_new (nb_loops); 3138 lambda_vector_clear (dist_v, nb_loops); 3139 lambda_vector_clear (init_v, nb_loops); 3140 3141 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) 3142 return true; 3143 3144 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 3145 { 3146 tree access_fn_a, access_fn_b; 3147 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); 3148 3149 if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) 3150 { 3151 non_affine_dependence_relation (ddr); 3152 return true; 3153 } 3154 3155 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); 3156 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); 3157 3158 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC 3159 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) 3160 { 3161 int dist, loop_nb, loop_depth; 3162 int loop_nb_a = CHREC_VARIABLE (access_fn_a); 3163 int loop_nb_b = CHREC_VARIABLE (access_fn_b); 3164 struct loop *loop_a = current_loops->parray[loop_nb_a]; 3165 struct loop *loop_b = current_loops->parray[loop_nb_b]; 3166 3167 /* If the loop for either variable is at a lower depth than 3168 the first_loop's depth, then we can't possibly have a 3169 dependency at this level of the loop. */ 3170 3171 if (loop_a->depth < first_loop_depth 3172 || loop_b->depth < first_loop_depth) 3173 return false; 3174 3175 if (loop_nb_a != loop_nb_b 3176 && !flow_loop_nested_p (loop_a, loop_b) 3177 && !flow_loop_nested_p (loop_b, loop_a)) 3178 { 3179 /* Example: when there are two consecutive loops, 3180 3181 | loop_1 3182 | A[{0, +, 1}_1] 3183 | endloop_1 3184 | loop_2 3185 | A[{0, +, 1}_2] 3186 | endloop_2 3187 3188 the dependence relation cannot be captured by the 3189 distance abstraction. */ 3190 non_affine_dependence_relation (ddr); 3191 return true; 3192 } 3193 3194 /* The dependence is carried by the outermost loop. Example: 3195 | loop_1 3196 | A[{4, +, 1}_1] 3197 | loop_2 3198 | A[{5, +, 1}_2] 3199 | endloop_2 3200 | endloop_1 3201 In this case, the dependence is carried by loop_1. */ 3202 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; 3203 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; 3204 3205 /* If the loop number is still greater than the number of 3206 loops we've been asked to analyze, or negative, 3207 something is borked. */ 3208 gcc_assert (loop_depth >= 0); 3209 gcc_assert (loop_depth < nb_loops); 3210 if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) 3211 { 3212 non_affine_dependence_relation (ddr); 3213 return true; 3214 } 3215 3216 dist = int_cst_value (SUB_DISTANCE (subscript)); 3217 3218 /* This is the subscript coupling test. 3219 | loop i = 0, N, 1 3220 | T[i+1][i] = ... 3221 | ... = T[i][i] 3222 | endloop 3223 There is no dependence. */ 3224 if (init_v[loop_depth] != 0 3225 && dist_v[loop_depth] != dist) 3226 { 3227 finalize_ddr_dependent (ddr, chrec_known); 3228 return true; 3229 } 3230 3231 dist_v[loop_depth] = dist; 3232 init_v[loop_depth] = 1; 3233 init_b = true; 3234 } 3235 } 3236 3237 /* Save the distance vector if we initialized one. */ 3238 if (init_b) 3239 { 3240 lambda_vector save_v; 3241 3242 /* Verify a basic constraint: classic distance vectors should always 3243 be lexicographically positive. */ 3244 if (!lambda_vector_lexico_pos (dist_v, DDR_SIZE_VECT (ddr))) 3245 { 3246 if (DDR_SIZE_VECT (ddr) == 1) 3247 /* This one is simple to fix, and can be fixed. 3248 Multidimensional arrays cannot be fixed that simply. */ 3249 lambda_vector_negate (dist_v, dist_v, DDR_SIZE_VECT (ddr)); 3250 else 3251 /* This is not valid: we need the delta test for properly 3252 fixing all this. */ 3253 return false; 3254 } 3255 3256 save_v = lambda_vector_new (DDR_SIZE_VECT (ddr)); 3257 lambda_vector_copy (dist_v, save_v, DDR_SIZE_VECT (ddr)); 3258 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), save_v); 3259 3260 /* There is nothing more to do when there are no outer loops. */ 3261 if (DDR_SIZE_VECT (ddr) == 1) 3262 goto classic_dist_done; 3263 } 3264 3265 /* There is a distance of 1 on all the outer loops: 3266 3267 Example: there is a dependence of distance 1 on loop_1 for the array A. 3268 | loop_1 3269 | A[5] = ... 3270 | endloop 3271 */ 3272 { 3273 struct loop *lca, *loop_a, *loop_b; 3274 struct data_reference *a = DDR_A (ddr); 3275 struct data_reference *b = DDR_B (ddr); 3276 int lca_depth; 3277 loop_a = loop_containing_stmt (DR_STMT (a)); 3278 loop_b = loop_containing_stmt (DR_STMT (b)); 3279 3280 /* Get the common ancestor loop. */ 3281 lca = find_common_loop (loop_a, loop_b); 3282 lca_depth = lca->depth - first_loop_depth; 3283 3284 gcc_assert (lca_depth >= 0); 3285 gcc_assert (lca_depth < nb_loops); 3286 3287 /* For each outer loop where init_v is not set, the accesses are 3288 in dependence of distance 1 in the loop. */ 3289 while (lca->depth != 0) 3290 { 3291 /* If we're considering just a sub-nest, then don't record 3292 any information on the outer loops. */ 3293 if (lca_depth < 0) 3294 break; 3295 3296 gcc_assert (lca_depth < nb_loops); 3297 3298 /* If we haven't yet determined a distance for this outer 3299 loop, push a new distance vector composed of the previous 3300 distance, and a distance of 1 for this outer loop. 3301 Example: 3302 3303 | loop_1 3304 | loop_2 3305 | A[10] 3306 | endloop_2 3307 | endloop_1 3308 3309 Saved vectors are of the form (dist_in_1, dist_in_2). 3310 First, we save (0, 1), then we have to save (1, 0). */ 3311 if (init_v[lca_depth] == 0) 3312 { 3313 lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr)); 3314 3315 lambda_vector_copy (dist_v, save_v, DDR_SIZE_VECT (ddr)); 3316 save_v[lca_depth] = 1; 3317 VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), save_v); 3318 } 3319 3320 lca = lca->outer; 3321 lca_depth = lca->depth - first_loop_depth; 3322 } 3323 } 3324 3325 classic_dist_done:; 3326 3327 if (dump_file && (dump_flags & TDF_DETAILS)) 3328 { 3329 fprintf (dump_file, "(build_classic_dist_vector\n"); 3330 3331 for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) 3332 { 3333 fprintf (dump_file, " dist_vector = ("); 3334 print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i), 3335 DDR_SIZE_VECT (ddr)); 3336 fprintf (dump_file, " )\n"); 3337 } 3338 fprintf (dump_file, ")\n"); 3339 } 3340 3341 return true; 3342} 3343 3344/* Compute the classic per loop direction vector. 3345 3346 DDR is the data dependence relation to build a vector from. 3347 NB_LOOPS is the total number of loops we are considering. 3348 FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed 3349 loop nest. 3350 Return FALSE if the dependence relation is outside of the loop nest 3351 at FIRST_LOOP_DEPTH. 3352 Return TRUE otherwise. */ 3353 3354static bool 3355build_classic_dir_vector (struct data_dependence_relation *ddr, 3356 int nb_loops, int first_loop_depth) 3357{ 3358 unsigned i; 3359 lambda_vector dir_v, init_v; 3360 bool init_b = false; 3361 3362 dir_v = lambda_vector_new (nb_loops); 3363 init_v = lambda_vector_new (nb_loops); 3364 lambda_vector_clear (dir_v, nb_loops); 3365 lambda_vector_clear (init_v, nb_loops); 3366 3367 DDR_SIZE_VECT (ddr) = nb_loops; 3368 3369 if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) 3370 return true; 3371 3372 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 3373 { 3374 tree access_fn_a, access_fn_b; 3375 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); 3376 3377 if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) 3378 { 3379 non_affine_dependence_relation (ddr); 3380 return true; 3381 } 3382 3383 access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i); 3384 access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i); 3385 if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC 3386 && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) 3387 { 3388 int dist, loop_nb, loop_depth; 3389 enum data_dependence_direction dir = dir_star; 3390 int loop_nb_a = CHREC_VARIABLE (access_fn_a); 3391 int loop_nb_b = CHREC_VARIABLE (access_fn_b); 3392 struct loop *loop_a = current_loops->parray[loop_nb_a]; 3393 struct loop *loop_b = current_loops->parray[loop_nb_b]; 3394 3395 /* If the loop for either variable is at a lower depth than 3396 the first_loop's depth, then we can't possibly have a 3397 dependency at this level of the loop. */ 3398 3399 if (loop_a->depth < first_loop_depth 3400 || loop_b->depth < first_loop_depth) 3401 return false; 3402 3403 if (loop_nb_a != loop_nb_b 3404 && !flow_loop_nested_p (loop_a, loop_b) 3405 && !flow_loop_nested_p (loop_b, loop_a)) 3406 { 3407 /* Example: when there are two consecutive loops, 3408 3409 | loop_1 3410 | A[{0, +, 1}_1] 3411 | endloop_1 3412 | loop_2 3413 | A[{0, +, 1}_2] 3414 | endloop_2 3415 3416 the dependence relation cannot be captured by the 3417 distance abstraction. */ 3418 non_affine_dependence_relation (ddr); 3419 return true; 3420 } 3421 3422 /* The dependence is carried by the outermost loop. Example: 3423 | loop_1 3424 | A[{4, +, 1}_1] 3425 | loop_2 3426 | A[{5, +, 1}_2] 3427 | endloop_2 3428 | endloop_1 3429 In this case, the dependence is carried by loop_1. */ 3430 loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b; 3431 loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth; 3432 3433 /* If the loop number is still greater than the number of 3434 loops we've been asked to analyze, or negative, 3435 something is borked. */ 3436 gcc_assert (loop_depth >= 0); 3437 gcc_assert (loop_depth < nb_loops); 3438 3439 if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) 3440 { 3441 non_affine_dependence_relation (ddr); 3442 return true; 3443 } 3444 3445 dist = int_cst_value (SUB_DISTANCE (subscript)); 3446 3447 if (dist == 0) 3448 dir = dir_equal; 3449 else if (dist > 0) 3450 dir = dir_positive; 3451 else if (dist < 0) 3452 dir = dir_negative; 3453 3454 /* This is the subscript coupling test. 3455 | loop i = 0, N, 1 3456 | T[i+1][i] = ... 3457 | ... = T[i][i] 3458 | endloop 3459 There is no dependence. */ 3460 if (init_v[loop_depth] != 0 3461 && dir != dir_star 3462 && (enum data_dependence_direction) dir_v[loop_depth] != dir 3463 && (enum data_dependence_direction) dir_v[loop_depth] != dir_star) 3464 { 3465 finalize_ddr_dependent (ddr, chrec_known); 3466 return true; 3467 } 3468 3469 dir_v[loop_depth] = dir; 3470 init_v[loop_depth] = 1; 3471 init_b = true; 3472 } 3473 } 3474 3475 /* Save the direction vector if we initialized one. */ 3476 if (init_b) 3477 { 3478 lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr)); 3479 3480 lambda_vector_copy (dir_v, save_v, DDR_SIZE_VECT (ddr)); 3481 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), save_v); 3482 } 3483 3484 /* There is a distance of 1 on all the outer loops: 3485 3486 Example: there is a dependence of distance 1 on loop_1 for the array A. 3487 | loop_1 3488 | A[5] = ... 3489 | endloop 3490 */ 3491 { 3492 struct loop *lca, *loop_a, *loop_b; 3493 struct data_reference *a = DDR_A (ddr); 3494 struct data_reference *b = DDR_B (ddr); 3495 int lca_depth; 3496 loop_a = loop_containing_stmt (DR_STMT (a)); 3497 loop_b = loop_containing_stmt (DR_STMT (b)); 3498 3499 /* Get the common ancestor loop. */ 3500 lca = find_common_loop (loop_a, loop_b); 3501 lca_depth = lca->depth - first_loop_depth; 3502 3503 gcc_assert (lca_depth >= 0); 3504 gcc_assert (lca_depth < nb_loops); 3505 3506 while (lca->depth != 0) 3507 { 3508 /* If we're considering just a sub-nest, then don't record 3509 any information on the outer loops. */ 3510 if (lca_depth < 0) 3511 break; 3512 3513 gcc_assert (lca_depth < nb_loops); 3514 3515 if (init_v[lca_depth] == 0) 3516 { 3517 lambda_vector save_v = lambda_vector_new (DDR_SIZE_VECT (ddr)); 3518 3519 lambda_vector_copy (dir_v, save_v, DDR_SIZE_VECT (ddr)); 3520 save_v[lca_depth] = dir_positive; 3521 VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), save_v); 3522 } 3523 3524 lca = lca->outer; 3525 lca_depth = lca->depth - first_loop_depth; 3526 3527 } 3528 } 3529 3530 return true; 3531} 3532 3533/* Returns true when all the access functions of A are affine or 3534 constant. */ 3535 3536static bool 3537access_functions_are_affine_or_constant_p (struct data_reference *a) 3538{ 3539 unsigned int i; 3540 VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a); 3541 tree t; 3542 3543 for (i = 0; VEC_iterate (tree, *fns, i, t); i++) 3544 if (!evolution_function_is_constant_p (t) 3545 && !evolution_function_is_affine_multivariate_p (t)) 3546 return false; 3547 3548 return true; 3549} 3550 3551/* This computes the affine dependence relation between A and B. 3552 CHREC_KNOWN is used for representing the independence between two 3553 accesses, while CHREC_DONT_KNOW is used for representing the unknown 3554 relation. 3555 3556 Note that it is possible to stop the computation of the dependence 3557 relation the first time we detect a CHREC_KNOWN element for a given 3558 subscript. */ 3559 3560void 3561compute_affine_dependence (struct data_dependence_relation *ddr) 3562{ 3563 struct data_reference *dra = DDR_A (ddr); 3564 struct data_reference *drb = DDR_B (ddr); 3565 3566 if (dump_file && (dump_flags & TDF_DETAILS)) 3567 { 3568 fprintf (dump_file, "(compute_affine_dependence\n"); 3569 fprintf (dump_file, " (stmt_a = \n"); 3570 print_generic_expr (dump_file, DR_STMT (dra), 0); 3571 fprintf (dump_file, ")\n (stmt_b = \n"); 3572 print_generic_expr (dump_file, DR_STMT (drb), 0); 3573 fprintf (dump_file, ")\n"); 3574 } 3575 3576 /* Analyze only when the dependence relation is not yet known. */ 3577 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) 3578 { 3579 if (access_functions_are_affine_or_constant_p (dra) 3580 && access_functions_are_affine_or_constant_p (drb)) 3581 subscript_dependence_tester (ddr); 3582 3583 /* As a last case, if the dependence cannot be determined, or if 3584 the dependence is considered too difficult to determine, answer 3585 "don't know". */ 3586 else 3587 finalize_ddr_dependent (ddr, chrec_dont_know); 3588 } 3589 3590 if (dump_file && (dump_flags & TDF_DETAILS)) 3591 fprintf (dump_file, ")\n"); 3592} 3593 3594/* This computes the dependence relation for the same data 3595 reference into DDR. */ 3596 3597static void 3598compute_self_dependence (struct data_dependence_relation *ddr) 3599{ 3600 unsigned int i; 3601 3602 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 3603 { 3604 struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); 3605 3606 /* The accessed index overlaps for each iteration. */ 3607 SUB_CONFLICTS_IN_A (subscript) = integer_zero_node; 3608 SUB_CONFLICTS_IN_B (subscript) = integer_zero_node; 3609 SUB_LAST_CONFLICT (subscript) = chrec_dont_know; 3610 } 3611} 3612 3613 3614typedef struct data_dependence_relation *ddr_p; 3615DEF_VEC_P(ddr_p); 3616DEF_VEC_ALLOC_P(ddr_p,heap); 3617 3618/* Compute a subset of the data dependence relation graph. Don't 3619 compute read-read and self relations if 3620 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is FALSE, and avoid the computation 3621 of the opposite relation, i.e. when AB has been computed, don't compute BA. 3622 DATAREFS contains a list of data references, and the result is set 3623 in DEPENDENCE_RELATIONS. */ 3624 3625static void 3626compute_all_dependences (varray_type datarefs, 3627 bool compute_self_and_read_read_dependences, 3628 VEC(ddr_p,heap) **dependence_relations) 3629{ 3630 unsigned int i, j, N; 3631 3632 N = VARRAY_ACTIVE_SIZE (datarefs); 3633 3634 /* Note that we specifically skip i == j because it's a self dependence, and 3635 use compute_self_dependence below. */ 3636 3637 for (i = 0; i < N; i++) 3638 for (j = i + 1; j < N; j++) 3639 { 3640 struct data_reference *a, *b; 3641 struct data_dependence_relation *ddr; 3642 3643 a = VARRAY_GENERIC_PTR (datarefs, i); 3644 b = VARRAY_GENERIC_PTR (datarefs, j); 3645 if (DR_IS_READ (a) && DR_IS_READ (b) 3646 && !compute_self_and_read_read_dependences) 3647 continue; 3648 ddr = initialize_data_dependence_relation (a, b); 3649 3650 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); 3651 compute_affine_dependence (ddr); 3652 compute_subscript_distance (ddr); 3653 } 3654 if (!compute_self_and_read_read_dependences) 3655 return; 3656 3657 /* Compute self dependence relation of each dataref to itself. */ 3658 3659 for (i = 0; i < N; i++) 3660 { 3661 struct data_reference *a, *b; 3662 struct data_dependence_relation *ddr; 3663 3664 a = VARRAY_GENERIC_PTR (datarefs, i); 3665 b = VARRAY_GENERIC_PTR (datarefs, i); 3666 ddr = initialize_data_dependence_relation (a, b); 3667 3668 VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); 3669 compute_self_dependence (ddr); 3670 compute_subscript_distance (ddr); 3671 } 3672} 3673 3674/* Search the data references in LOOP, and record the information into 3675 DATAREFS. Returns chrec_dont_know when failing to analyze a 3676 difficult case, returns NULL_TREE otherwise. 3677 3678 TODO: This function should be made smarter so that it can handle address 3679 arithmetic as if they were array accesses, etc. */ 3680 3681tree 3682find_data_references_in_loop (struct loop *loop, varray_type *datarefs) 3683{ 3684 basic_block bb, *bbs; 3685 unsigned int i; 3686 block_stmt_iterator bsi; 3687 struct data_reference *dr; 3688 3689 bbs = get_loop_body (loop); 3690 3691 for (i = 0; i < loop->num_nodes; i++) 3692 { 3693 bb = bbs[i]; 3694 3695 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 3696 { 3697 tree stmt = bsi_stmt (bsi); 3698 3699 /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects. 3700 Calls have side-effects, except those to const or pure 3701 functions. */ 3702 if ((TREE_CODE (stmt) == CALL_EXPR 3703 && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE))) 3704 || (TREE_CODE (stmt) == ASM_EXPR 3705 && ASM_VOLATILE_P (stmt))) 3706 goto insert_dont_know_node; 3707 3708 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 3709 continue; 3710 3711 switch (TREE_CODE (stmt)) 3712 { 3713 case MODIFY_EXPR: 3714 { 3715 bool one_inserted = false; 3716 tree opnd0 = TREE_OPERAND (stmt, 0); 3717 tree opnd1 = TREE_OPERAND (stmt, 1); 3718 3719 if (TREE_CODE (opnd0) == ARRAY_REF 3720 || TREE_CODE (opnd0) == INDIRECT_REF) 3721 { 3722 dr = create_data_ref (opnd0, stmt, false); 3723 if (dr) 3724 { 3725 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr); 3726 one_inserted = true; 3727 } 3728 } 3729 3730 if (TREE_CODE (opnd1) == ARRAY_REF 3731 || TREE_CODE (opnd1) == INDIRECT_REF) 3732 { 3733 dr = create_data_ref (opnd1, stmt, true); 3734 if (dr) 3735 { 3736 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr); 3737 one_inserted = true; 3738 } 3739 } 3740 3741 if (!one_inserted) 3742 goto insert_dont_know_node; 3743 3744 break; 3745 } 3746 3747 case CALL_EXPR: 3748 { 3749 tree args; 3750 bool one_inserted = false; 3751 3752 for (args = TREE_OPERAND (stmt, 1); args; 3753 args = TREE_CHAIN (args)) 3754 if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF 3755 || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF) 3756 { 3757 dr = create_data_ref (TREE_VALUE (args), stmt, true); 3758 if (dr) 3759 { 3760 VARRAY_PUSH_GENERIC_PTR (*datarefs, dr); 3761 one_inserted = true; 3762 } 3763 } 3764 3765 if (!one_inserted) 3766 goto insert_dont_know_node; 3767 3768 break; 3769 } 3770 3771 default: 3772 { 3773 struct data_reference *res; 3774 3775 insert_dont_know_node:; 3776 res = xmalloc (sizeof (struct data_reference)); 3777 DR_STMT (res) = NULL_TREE; 3778 DR_REF (res) = NULL_TREE; 3779 DR_BASE_OBJECT (res) = NULL; 3780 DR_TYPE (res) = ARRAY_REF_TYPE; 3781 DR_SET_ACCESS_FNS (res, NULL); 3782 DR_BASE_OBJECT (res) = NULL; 3783 DR_IS_READ (res) = false; 3784 DR_BASE_ADDRESS (res) = NULL_TREE; 3785 DR_OFFSET (res) = NULL_TREE; 3786 DR_INIT (res) = NULL_TREE; 3787 DR_STEP (res) = NULL_TREE; 3788 DR_OFFSET_MISALIGNMENT (res) = NULL_TREE; 3789 DR_MEMTAG (res) = NULL_TREE; 3790 DR_PTR_INFO (res) = NULL; 3791 VARRAY_PUSH_GENERIC_PTR (*datarefs, res); 3792 3793 free (bbs); 3794 return chrec_dont_know; 3795 } 3796 } 3797 3798 /* When there are no defs in the loop, the loop is parallel. */ 3799 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 3800 loop->parallel_p = false; 3801 } 3802 } 3803 3804 free (bbs); 3805 3806 return NULL_TREE; 3807} 3808 3809 3810 3811/* This section contains all the entry points. */ 3812 3813/* Given a loop nest LOOP, the following vectors are returned: 3814 *DATAREFS is initialized to all the array elements contained in this loop, 3815 *DEPENDENCE_RELATIONS contains the relations between the data references. 3816 Compute read-read and self relations if 3817 COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */ 3818 3819void 3820compute_data_dependences_for_loop (struct loop *loop, 3821 bool compute_self_and_read_read_dependences, 3822 varray_type *datarefs, 3823 varray_type *dependence_relations) 3824{ 3825 unsigned int i, nb_loops; 3826 VEC(ddr_p,heap) *allrelations; 3827 struct data_dependence_relation *ddr; 3828 struct loop *loop_nest = loop; 3829 3830 while (loop_nest && loop_nest->outer && loop_nest->outer->outer) 3831 loop_nest = loop_nest->outer; 3832 3833 nb_loops = loop_nest->level; 3834 3835 /* If one of the data references is not computable, give up without 3836 spending time to compute other dependences. */ 3837 if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know) 3838 { 3839 struct data_dependence_relation *ddr; 3840 3841 /* Insert a single relation into dependence_relations: 3842 chrec_dont_know. */ 3843 ddr = initialize_data_dependence_relation (NULL, NULL); 3844 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); 3845 build_classic_dist_vector (ddr, nb_loops, loop->depth); 3846 build_classic_dir_vector (ddr, nb_loops, loop->depth); 3847 return; 3848 } 3849 3850 allrelations = NULL; 3851 compute_all_dependences (*datarefs, compute_self_and_read_read_dependences, 3852 &allrelations); 3853 3854 for (i = 0; VEC_iterate (ddr_p, allrelations, i, ddr); i++) 3855 { 3856 if (build_classic_dist_vector (ddr, nb_loops, loop_nest->depth)) 3857 { 3858 VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr); 3859 build_classic_dir_vector (ddr, nb_loops, loop_nest->depth); 3860 } 3861 } 3862} 3863 3864/* Entry point (for testing only). Analyze all the data references 3865 and the dependence relations. 3866 3867 The data references are computed first. 3868 3869 A relation on these nodes is represented by a complete graph. Some 3870 of the relations could be of no interest, thus the relations can be 3871 computed on demand. 3872 3873 In the following function we compute all the relations. This is 3874 just a first implementation that is here for: 3875 - for showing how to ask for the dependence relations, 3876 - for the debugging the whole dependence graph, 3877 - for the dejagnu testcases and maintenance. 3878 3879 It is possible to ask only for a part of the graph, avoiding to 3880 compute the whole dependence graph. The computed dependences are 3881 stored in a knowledge base (KB) such that later queries don't 3882 recompute the same information. The implementation of this KB is 3883 transparent to the optimizer, and thus the KB can be changed with a 3884 more efficient implementation, or the KB could be disabled. */ 3885 3886void 3887analyze_all_data_dependences (struct loops *loops) 3888{ 3889 unsigned int i; 3890 varray_type datarefs; 3891 varray_type dependence_relations; 3892 int nb_data_refs = 10; 3893 3894 VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs"); 3895 VARRAY_GENERIC_PTR_INIT (dependence_relations, 3896 nb_data_refs * nb_data_refs, 3897 "dependence_relations"); 3898 3899 /* Compute DDs on the whole function. */ 3900 compute_data_dependences_for_loop (loops->parray[0], false, 3901 &datarefs, &dependence_relations); 3902 3903 if (dump_file) 3904 { 3905 dump_data_dependence_relations (dump_file, dependence_relations); 3906 fprintf (dump_file, "\n\n"); 3907 3908 if (dump_flags & TDF_DETAILS) 3909 dump_dist_dir_vectors (dump_file, dependence_relations); 3910 3911 if (dump_flags & TDF_STATS) 3912 { 3913 unsigned nb_top_relations = 0; 3914 unsigned nb_bot_relations = 0; 3915 unsigned nb_basename_differ = 0; 3916 unsigned nb_chrec_relations = 0; 3917 3918 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) 3919 { 3920 struct data_dependence_relation *ddr; 3921 ddr = VARRAY_GENERIC_PTR (dependence_relations, i); 3922 3923 if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) 3924 nb_top_relations++; 3925 3926 else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) 3927 { 3928 struct data_reference *a = DDR_A (ddr); 3929 struct data_reference *b = DDR_B (ddr); 3930 bool differ_p; 3931 3932 if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b) 3933 && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)) 3934 || (base_object_differ_p (a, b, &differ_p) 3935 && differ_p)) 3936 nb_basename_differ++; 3937 else 3938 nb_bot_relations++; 3939 } 3940 3941 else 3942 nb_chrec_relations++; 3943 } 3944 3945 gather_stats_on_scev_database (); 3946 } 3947 } 3948 3949 free_dependence_relations (dependence_relations); 3950 free_data_refs (datarefs); 3951} 3952 3953/* Free the memory used by a data dependence relation DDR. */ 3954 3955void 3956free_dependence_relation (struct data_dependence_relation *ddr) 3957{ 3958 if (ddr == NULL) 3959 return; 3960 3961 if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) 3962 varray_clear (DDR_SUBSCRIPTS (ddr)); 3963 free (ddr); 3964} 3965 3966/* Free the memory used by the data dependence relations from 3967 DEPENDENCE_RELATIONS. */ 3968 3969void 3970free_dependence_relations (varray_type dependence_relations) 3971{ 3972 unsigned int i; 3973 if (dependence_relations == NULL) 3974 return; 3975 3976 for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++) 3977 free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i)); 3978 varray_clear (dependence_relations); 3979} 3980 3981/* Free the memory used by the data references from DATAREFS. */ 3982 3983void 3984free_data_refs (varray_type datarefs) 3985{ 3986 unsigned int i; 3987 3988 if (datarefs == NULL) 3989 return; 3990 3991 for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++) 3992 { 3993 struct data_reference *dr = (struct data_reference *) 3994 VARRAY_GENERIC_PTR (datarefs, i); 3995 if (dr) 3996 { 3997 DR_FREE_ACCESS_FNS (dr); 3998 free (dr); 3999 } 4000 } 4001 varray_clear (datarefs); 4002} 4003 4004