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