1169689Skan 2169689Skan/* Data references and dependences detectors. 3169689Skan Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 4169689Skan Contributed by Sebastian Pop <pop@cri.ensmp.fr> 5169689Skan 6169689SkanThis file is part of GCC. 7169689Skan 8169689SkanGCC is free software; you can redistribute it and/or modify it under 9169689Skanthe terms of the GNU General Public License as published by the Free 10169689SkanSoftware Foundation; either version 2, or (at your option) any later 11169689Skanversion. 12169689Skan 13169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 14169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 15169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16169689Skanfor more details. 17169689Skan 18169689SkanYou should have received a copy of the GNU General Public License 19169689Skanalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 22169689Skan 23169689Skan/* This pass walks a given loop structure searching for array 24169689Skan references. The information about the array accesses is recorded 25169689Skan in DATA_REFERENCE structures. 26169689Skan 27169689Skan The basic test for determining the dependences is: 28169689Skan given two access functions chrec1 and chrec2 to a same array, and 29169689Skan x and y two vectors from the iteration domain, the same element of 30169689Skan the array is accessed twice at iterations x and y if and only if: 31169689Skan | chrec1 (x) == chrec2 (y). 32169689Skan 33169689Skan The goals of this analysis are: 34169689Skan 35169689Skan - to determine the independence: the relation between two 36169689Skan independent accesses is qualified with the chrec_known (this 37169689Skan information allows a loop parallelization), 38169689Skan 39169689Skan - when two data references access the same data, to qualify the 40169689Skan dependence relation with classic dependence representations: 41169689Skan 42169689Skan - distance vectors 43169689Skan - direction vectors 44169689Skan - loop carried level dependence 45169689Skan - polyhedron dependence 46169689Skan or with the chains of recurrences based representation, 47169689Skan 48169689Skan - to define a knowledge base for storing the data dependence 49169689Skan information, 50169689Skan 51169689Skan - to define an interface to access this data. 52169689Skan 53169689Skan 54169689Skan Definitions: 55169689Skan 56169689Skan - subscript: given two array accesses a subscript is the tuple 57169689Skan composed of the access functions for a given dimension. Example: 58169689Skan Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts: 59169689Skan (f1, g1), (f2, g2), (f3, g3). 60169689Skan 61169689Skan - Diophantine equation: an equation whose coefficients and 62169689Skan solutions are integer constants, for example the equation 63169689Skan | 3*x + 2*y = 1 64169689Skan has an integer solution x = 1 and y = -1. 65169689Skan 66169689Skan References: 67169689Skan 68169689Skan - "Advanced Compilation for High Performance Computing" by Randy 69169689Skan Allen and Ken Kennedy. 70169689Skan http://citeseer.ist.psu.edu/goff91practical.html 71169689Skan 72169689Skan - "Loop Transformations for Restructuring Compilers - The Foundations" 73169689Skan by Utpal Banerjee. 74169689Skan 75169689Skan 76169689Skan*/ 77169689Skan 78169689Skan#include "config.h" 79169689Skan#include "system.h" 80169689Skan#include "coretypes.h" 81169689Skan#include "tm.h" 82169689Skan#include "ggc.h" 83169689Skan#include "tree.h" 84169689Skan 85169689Skan/* These RTL headers are needed for basic-block.h. */ 86169689Skan#include "rtl.h" 87169689Skan#include "basic-block.h" 88169689Skan#include "diagnostic.h" 89169689Skan#include "tree-flow.h" 90169689Skan#include "tree-dump.h" 91169689Skan#include "timevar.h" 92169689Skan#include "cfgloop.h" 93169689Skan#include "tree-chrec.h" 94169689Skan#include "tree-data-ref.h" 95169689Skan#include "tree-scalar-evolution.h" 96169689Skan#include "tree-pass.h" 97169689Skan 98169689Skanstatic struct datadep_stats 99169689Skan{ 100169689Skan int num_dependence_tests; 101169689Skan int num_dependence_dependent; 102169689Skan int num_dependence_independent; 103169689Skan int num_dependence_undetermined; 104169689Skan 105169689Skan int num_subscript_tests; 106169689Skan int num_subscript_undetermined; 107169689Skan int num_same_subscript_function; 108169689Skan 109169689Skan int num_ziv; 110169689Skan int num_ziv_independent; 111169689Skan int num_ziv_dependent; 112169689Skan int num_ziv_unimplemented; 113169689Skan 114169689Skan int num_siv; 115169689Skan int num_siv_independent; 116169689Skan int num_siv_dependent; 117169689Skan int num_siv_unimplemented; 118169689Skan 119169689Skan int num_miv; 120169689Skan int num_miv_independent; 121169689Skan int num_miv_dependent; 122169689Skan int num_miv_unimplemented; 123169689Skan} dependence_stats; 124169689Skan 125169689Skanstatic tree object_analysis (tree, tree, bool, struct data_reference **, 126169689Skan tree *, tree *, tree *, tree *, tree *, 127169689Skan struct ptr_info_def **, subvar_t *); 128169689Skanstatic struct data_reference * init_data_ref (tree, tree, tree, tree, bool, 129169689Skan tree, tree, tree, tree, tree, 130169689Skan struct ptr_info_def *, 131169689Skan enum data_ref_type); 132169689Skanstatic bool subscript_dependence_tester_1 (struct data_dependence_relation *, 133169689Skan struct data_reference *, 134169689Skan struct data_reference *); 135169689Skan 136169689Skan/* Determine if PTR and DECL may alias, the result is put in ALIASED. 137169689Skan Return FALSE if there is no symbol memory tag for PTR. */ 138169689Skan 139169689Skanstatic bool 140169689Skanptr_decl_may_alias_p (tree ptr, tree decl, 141169689Skan struct data_reference *ptr_dr, 142169689Skan bool *aliased) 143169689Skan{ 144169689Skan tree tag = NULL_TREE; 145169689Skan struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr); 146169689Skan 147169689Skan gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl)); 148169689Skan 149169689Skan if (pi) 150169689Skan tag = pi->name_mem_tag; 151169689Skan if (!tag) 152169689Skan tag = get_var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag; 153169689Skan if (!tag) 154169689Skan tag = DR_MEMTAG (ptr_dr); 155169689Skan if (!tag) 156169689Skan return false; 157169689Skan 158169689Skan *aliased = is_aliased_with (tag, decl); 159169689Skan return true; 160169689Skan} 161169689Skan 162169689Skan 163169689Skan/* Determine if two pointers may alias, the result is put in ALIASED. 164169689Skan Return FALSE if there is no symbol memory tag for one of the pointers. */ 165169689Skan 166169689Skanstatic bool 167169689Skanptr_ptr_may_alias_p (tree ptr_a, tree ptr_b, 168169689Skan struct data_reference *dra, 169169689Skan struct data_reference *drb, 170169689Skan bool *aliased) 171169689Skan{ 172169689Skan tree tag_a = NULL_TREE, tag_b = NULL_TREE; 173169689Skan struct ptr_info_def *pi_a = DR_PTR_INFO (dra); 174169689Skan struct ptr_info_def *pi_b = DR_PTR_INFO (drb); 175169689Skan 176169689Skan if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag) 177169689Skan { 178169689Skan tag_a = pi_a->name_mem_tag; 179169689Skan tag_b = pi_b->name_mem_tag; 180169689Skan } 181169689Skan else 182169689Skan { 183169689Skan tag_a = get_var_ann (SSA_NAME_VAR (ptr_a))->symbol_mem_tag; 184169689Skan if (!tag_a) 185169689Skan tag_a = DR_MEMTAG (dra); 186169689Skan if (!tag_a) 187169689Skan return false; 188169689Skan 189169689Skan tag_b = get_var_ann (SSA_NAME_VAR (ptr_b))->symbol_mem_tag; 190169689Skan if (!tag_b) 191169689Skan tag_b = DR_MEMTAG (drb); 192169689Skan if (!tag_b) 193169689Skan return false; 194169689Skan } 195169689Skan 196169689Skan if (tag_a == tag_b) 197169689Skan *aliased = true; 198169689Skan else 199169689Skan *aliased = may_aliases_intersect (tag_a, tag_b); 200169689Skan 201169689Skan return true; 202169689Skan} 203169689Skan 204169689Skan 205169689Skan/* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED. 206169689Skan Return FALSE if there is no symbol memory tag for one of the symbols. */ 207169689Skan 208169689Skanstatic bool 209169689Skanmay_alias_p (tree base_a, tree base_b, 210169689Skan struct data_reference *dra, 211169689Skan struct data_reference *drb, 212169689Skan bool *aliased) 213169689Skan{ 214169689Skan if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR) 215169689Skan { 216169689Skan if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR) 217169689Skan { 218169689Skan *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)); 219169689Skan return true; 220169689Skan } 221169689Skan if (TREE_CODE (base_a) == ADDR_EXPR) 222169689Skan return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb, 223169689Skan aliased); 224169689Skan else 225169689Skan return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra, 226169689Skan aliased); 227169689Skan } 228169689Skan 229169689Skan return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased); 230169689Skan} 231169689Skan 232169689Skan 233169689Skan/* Determine if a pointer (BASE_A) and a record/union access (BASE_B) 234169689Skan are not aliased. Return TRUE if they differ. */ 235169689Skanstatic bool 236169689Skanrecord_ptr_differ_p (struct data_reference *dra, 237169689Skan struct data_reference *drb) 238169689Skan{ 239169689Skan bool aliased; 240169689Skan tree base_a = DR_BASE_OBJECT (dra); 241169689Skan tree base_b = DR_BASE_OBJECT (drb); 242169689Skan 243169689Skan if (TREE_CODE (base_b) != COMPONENT_REF) 244169689Skan return false; 245169689Skan 246169689Skan /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs. 247169689Skan For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b. 248169689Skan Probably will be unnecessary with struct alias analysis. */ 249169689Skan while (TREE_CODE (base_b) == COMPONENT_REF) 250169689Skan base_b = TREE_OPERAND (base_b, 0); 251169689Skan /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer 252169689Skan ((*q)[i]). */ 253169689Skan if (TREE_CODE (base_a) == INDIRECT_REF 254169689Skan && ((TREE_CODE (base_b) == VAR_DECL 255169689Skan && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra, 256169689Skan &aliased) 257169689Skan && !aliased)) 258169689Skan || (TREE_CODE (base_b) == INDIRECT_REF 259169689Skan && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0), 260169689Skan TREE_OPERAND (base_b, 0), dra, drb, 261169689Skan &aliased) 262169689Skan && !aliased)))) 263169689Skan return true; 264169689Skan else 265169689Skan return false; 266169689Skan} 267169689Skan 268169689Skan/* Determine if two record/union accesses are aliased. Return TRUE if they 269169689Skan differ. */ 270169689Skanstatic bool 271169689Skanrecord_record_differ_p (struct data_reference *dra, 272169689Skan struct data_reference *drb) 273169689Skan{ 274169689Skan bool aliased; 275169689Skan tree base_a = DR_BASE_OBJECT (dra); 276169689Skan tree base_b = DR_BASE_OBJECT (drb); 277169689Skan 278169689Skan if (TREE_CODE (base_b) != COMPONENT_REF 279169689Skan || TREE_CODE (base_a) != COMPONENT_REF) 280169689Skan return false; 281169689Skan 282169689Skan /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs. 283169689Skan For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b. 284169689Skan Probably will be unnecessary with struct alias analysis. */ 285169689Skan while (TREE_CODE (base_b) == COMPONENT_REF) 286169689Skan base_b = TREE_OPERAND (base_b, 0); 287169689Skan while (TREE_CODE (base_a) == COMPONENT_REF) 288169689Skan base_a = TREE_OPERAND (base_a, 0); 289169689Skan 290169689Skan if (TREE_CODE (base_a) == INDIRECT_REF 291169689Skan && TREE_CODE (base_b) == INDIRECT_REF 292169689Skan && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0), 293169689Skan TREE_OPERAND (base_b, 0), 294169689Skan dra, drb, &aliased) 295169689Skan && !aliased) 296169689Skan return true; 297169689Skan else 298169689Skan return false; 299169689Skan} 300169689Skan 301169689Skan/* Determine if an array access (BASE_A) and a record/union access (BASE_B) 302169689Skan are not aliased. Return TRUE if they differ. */ 303169689Skanstatic bool 304169689Skanrecord_array_differ_p (struct data_reference *dra, 305169689Skan struct data_reference *drb) 306169689Skan{ 307169689Skan bool aliased; 308169689Skan tree base_a = DR_BASE_OBJECT (dra); 309169689Skan tree base_b = DR_BASE_OBJECT (drb); 310169689Skan 311169689Skan if (TREE_CODE (base_b) != COMPONENT_REF) 312169689Skan return false; 313169689Skan 314169689Skan /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs. 315169689Skan For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b. 316169689Skan Probably will be unnecessary with struct alias analysis. */ 317169689Skan while (TREE_CODE (base_b) == COMPONENT_REF) 318169689Skan base_b = TREE_OPERAND (base_b, 0); 319169689Skan 320169689Skan /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 321169689Skan (a[i]). In case of p->c[i] use alias analysis to verify that p is not 322169689Skan pointing to a. */ 323169689Skan if (TREE_CODE (base_a) == VAR_DECL 324169689Skan && (TREE_CODE (base_b) == VAR_DECL 325169689Skan || (TREE_CODE (base_b) == INDIRECT_REF 326169689Skan && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, 327169689Skan &aliased) 328169689Skan && !aliased)))) 329169689Skan return true; 330169689Skan else 331169689Skan return false; 332169689Skan} 333169689Skan 334169689Skan 335169689Skan/* Determine if an array access (BASE_A) and a pointer (BASE_B) 336169689Skan are not aliased. Return TRUE if they differ. */ 337169689Skanstatic bool 338169689Skanarray_ptr_differ_p (tree base_a, tree base_b, 339169689Skan struct data_reference *drb) 340169689Skan{ 341169689Skan bool aliased; 342169689Skan 343169689Skan /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the 344169689Skan help of alias analysis that p is not pointing to a. */ 345169689Skan if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF 346169689Skan && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased) 347169689Skan && !aliased)) 348169689Skan return true; 349169689Skan else 350169689Skan return false; 351169689Skan} 352169689Skan 353169689Skan 354169689Skan/* This is the simplest data dependence test: determines whether the 355169689Skan data references A and B access the same array/region. Returns 356169689Skan false when the property is not computable at compile time. 357169689Skan Otherwise return true, and DIFFER_P will record the result. This 358169689Skan utility will not be necessary when alias_sets_conflict_p will be 359169689Skan less conservative. */ 360169689Skan 361169689Skanstatic bool 362169689Skanbase_object_differ_p (struct data_reference *a, 363169689Skan struct data_reference *b, 364169689Skan bool *differ_p) 365169689Skan{ 366169689Skan tree base_a = DR_BASE_OBJECT (a); 367169689Skan tree base_b = DR_BASE_OBJECT (b); 368169689Skan bool aliased; 369169689Skan 370169689Skan if (!base_a || !base_b) 371169689Skan return false; 372169689Skan 373169689Skan /* Determine if same base. Example: for the array accesses 374169689Skan a[i], b[i] or pointer accesses *a, *b, bases are a, b. */ 375169689Skan if (base_a == base_b) 376169689Skan { 377169689Skan *differ_p = false; 378169689Skan return true; 379169689Skan } 380169689Skan 381169689Skan /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p) 382169689Skan and (*q) */ 383169689Skan if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF 384169689Skan && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)) 385169689Skan { 386169689Skan *differ_p = false; 387169689Skan return true; 388169689Skan } 389169689Skan 390169689Skan /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b. */ 391169689Skan if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF 392169689Skan && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0) 393169689Skan && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1)) 394169689Skan { 395169689Skan *differ_p = false; 396169689Skan return true; 397169689Skan } 398169689Skan 399169689Skan 400169689Skan /* Determine if different bases. */ 401169689Skan 402169689Skan /* At this point we know that base_a != base_b. However, pointer 403169689Skan accesses of the form x=(*p) and y=(*q), whose bases are p and q, 404169689Skan may still be pointing to the same base. In SSAed GIMPLE p and q will 405169689Skan be SSA_NAMES in this case. Therefore, here we check if they are 406169689Skan really two different declarations. */ 407169689Skan if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL) 408169689Skan { 409169689Skan *differ_p = true; 410169689Skan return true; 411169689Skan } 412169689Skan 413169689Skan /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the 414169689Skan help of alias analysis that p is not pointing to a. */ 415169689Skan if (array_ptr_differ_p (base_a, base_b, b) 416169689Skan || array_ptr_differ_p (base_b, base_a, a)) 417169689Skan { 418169689Skan *differ_p = true; 419169689Skan return true; 420169689Skan } 421169689Skan 422169689Skan /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the 423169689Skan help of alias analysis they don't point to the same bases. */ 424169689Skan if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF 425169689Skan && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b, 426169689Skan &aliased) 427169689Skan && !aliased)) 428169689Skan { 429169689Skan *differ_p = true; 430169689Skan return true; 431169689Skan } 432169689Skan 433169689Skan /* Compare two record/union bases s.a and t.b: s != t or (a != b and 434169689Skan s and t are not unions). */ 435169689Skan if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF 436169689Skan && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL 437169689Skan && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL 438169689Skan && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0)) 439169689Skan || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE 440169689Skan && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE 441169689Skan && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1)))) 442169689Skan { 443169689Skan *differ_p = true; 444169689Skan return true; 445169689Skan } 446169689Skan 447169689Skan /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer 448169689Skan ((*q)[i]). */ 449169689Skan if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a)) 450169689Skan { 451169689Skan *differ_p = true; 452169689Skan return true; 453169689Skan } 454169689Skan 455169689Skan /* Compare a record/union access (b.c[i] or p->c[i]) and an array access 456169689Skan (a[i]). In case of p->c[i] use alias analysis to verify that p is not 457169689Skan pointing to a. */ 458169689Skan if (record_array_differ_p (a, b) || record_array_differ_p (b, a)) 459169689Skan { 460169689Skan *differ_p = true; 461169689Skan return true; 462169689Skan } 463169689Skan 464169689Skan /* Compare two record/union accesses (b.c[i] or p->c[i]). */ 465169689Skan if (record_record_differ_p (a, b)) 466169689Skan { 467169689Skan *differ_p = true; 468169689Skan return true; 469169689Skan } 470169689Skan 471169689Skan return false; 472169689Skan} 473169689Skan 474169689Skan/* Function base_addr_differ_p. 475169689Skan 476169689Skan This is the simplest data dependence test: determines whether the 477169689Skan data references DRA and DRB access the same array/region. Returns 478169689Skan false when the property is not computable at compile time. 479169689Skan Otherwise return true, and DIFFER_P will record the result. 480169689Skan 481169689Skan The algorithm: 482169689Skan 1. if (both DRA and DRB are represented as arrays) 483169689Skan compare DRA.BASE_OBJECT and DRB.BASE_OBJECT 484169689Skan 2. else if (both DRA and DRB are represented as pointers) 485169689Skan try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION 486169689Skan 3. else if (DRA and DRB are represented differently or 2. fails) 487169689Skan only try to prove that the bases are surely different 488169689Skan*/ 489169689Skan 490169689Skanstatic bool 491169689Skanbase_addr_differ_p (struct data_reference *dra, 492169689Skan struct data_reference *drb, 493169689Skan bool *differ_p) 494169689Skan{ 495169689Skan tree addr_a = DR_BASE_ADDRESS (dra); 496169689Skan tree addr_b = DR_BASE_ADDRESS (drb); 497169689Skan tree type_a, type_b; 498169689Skan bool aliased; 499169689Skan 500169689Skan if (!addr_a || !addr_b) 501169689Skan return false; 502169689Skan 503169689Skan type_a = TREE_TYPE (addr_a); 504169689Skan type_b = TREE_TYPE (addr_b); 505169689Skan 506169689Skan gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b)); 507169689Skan 508169689Skan /* 1. if (both DRA and DRB are represented as arrays) 509169689Skan compare DRA.BASE_OBJECT and DRB.BASE_OBJECT. */ 510169689Skan if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE) 511169689Skan return base_object_differ_p (dra, drb, differ_p); 512169689Skan 513169689Skan /* 2. else if (both DRA and DRB are represented as pointers) 514169689Skan try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION. */ 515169689Skan /* If base addresses are the same, we check the offsets, since the access of 516169689Skan the data-ref is described by {base addr + offset} and its access function, 517169689Skan i.e., in order to decide whether the bases of data-refs are the same we 518169689Skan compare both base addresses and offsets. */ 519169689Skan if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE 520169689Skan && (addr_a == addr_b 521169689Skan || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR 522169689Skan && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0)))) 523169689Skan { 524169689Skan /* Compare offsets. */ 525169689Skan tree offset_a = DR_OFFSET (dra); 526169689Skan tree offset_b = DR_OFFSET (drb); 527169689Skan 528169689Skan STRIP_NOPS (offset_a); 529169689Skan STRIP_NOPS (offset_b); 530169689Skan 531169689Skan /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle 532169689Skan PLUS_EXPR. */ 533169689Skan if (offset_a == offset_b 534169689Skan || (TREE_CODE (offset_a) == MULT_EXPR 535169689Skan && TREE_CODE (offset_b) == MULT_EXPR 536169689Skan && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0) 537169689Skan && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1))) 538169689Skan { 539169689Skan *differ_p = false; 540169689Skan return true; 541169689Skan } 542169689Skan } 543169689Skan 544169689Skan /* 3. else if (DRA and DRB are represented differently or 2. fails) 545169689Skan only try to prove that the bases are surely different. */ 546169689Skan 547169689Skan /* Apply alias analysis. */ 548169689Skan if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased) 549169689Skan { 550169689Skan *differ_p = true; 551169689Skan return true; 552169689Skan } 553169689Skan 554169689Skan /* An instruction writing through a restricted pointer is "independent" of any 555169689Skan instruction reading or writing through a different pointer, in the same 556169689Skan block/scope. */ 557169689Skan else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra)) 558169689Skan || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb))) 559169689Skan { 560169689Skan *differ_p = true; 561169689Skan return true; 562169689Skan } 563169689Skan return false; 564169689Skan} 565169689Skan 566169689Skan/* Returns true iff A divides B. */ 567169689Skan 568169689Skanstatic inline bool 569169689Skantree_fold_divides_p (tree a, 570169689Skan tree b) 571169689Skan{ 572169689Skan /* Determines whether (A == gcd (A, B)). */ 573169689Skan return tree_int_cst_equal (a, tree_fold_gcd (a, b)); 574169689Skan} 575169689Skan 576169689Skan/* Returns true iff A divides B. */ 577169689Skan 578169689Skanstatic inline bool 579169689Skanint_divides_p (int a, int b) 580169689Skan{ 581169689Skan return ((b % a) == 0); 582169689Skan} 583169689Skan 584169689Skan 585169689Skan 586169689Skan/* Dump into FILE all the data references from DATAREFS. */ 587169689Skan 588169689Skanvoid 589169689Skandump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs) 590169689Skan{ 591169689Skan unsigned int i; 592169689Skan struct data_reference *dr; 593169689Skan 594169689Skan for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 595169689Skan dump_data_reference (file, dr); 596169689Skan} 597169689Skan 598169689Skan/* Dump into FILE all the dependence relations from DDRS. */ 599169689Skan 600169689Skanvoid 601169689Skandump_data_dependence_relations (FILE *file, 602169689Skan VEC (ddr_p, heap) *ddrs) 603169689Skan{ 604169689Skan unsigned int i; 605169689Skan struct data_dependence_relation *ddr; 606169689Skan 607169689Skan for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) 608169689Skan dump_data_dependence_relation (file, ddr); 609169689Skan} 610169689Skan 611169689Skan/* Dump function for a DATA_REFERENCE structure. */ 612169689Skan 613169689Skanvoid 614169689Skandump_data_reference (FILE *outf, 615169689Skan struct data_reference *dr) 616169689Skan{ 617169689Skan unsigned int i; 618169689Skan 619169689Skan fprintf (outf, "(Data Ref: \n stmt: "); 620169689Skan print_generic_stmt (outf, DR_STMT (dr), 0); 621169689Skan fprintf (outf, " ref: "); 622169689Skan print_generic_stmt (outf, DR_REF (dr), 0); 623169689Skan fprintf (outf, " base_object: "); 624169689Skan print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0); 625169689Skan 626169689Skan for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++) 627169689Skan { 628169689Skan fprintf (outf, " Access function %d: ", i); 629169689Skan print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0); 630169689Skan } 631169689Skan fprintf (outf, ")\n"); 632169689Skan} 633169689Skan 634169689Skan/* Dump function for a SUBSCRIPT structure. */ 635169689Skan 636169689Skanvoid 637169689Skandump_subscript (FILE *outf, struct subscript *subscript) 638169689Skan{ 639169689Skan tree chrec = SUB_CONFLICTS_IN_A (subscript); 640169689Skan 641169689Skan fprintf (outf, "\n (subscript \n"); 642169689Skan fprintf (outf, " iterations_that_access_an_element_twice_in_A: "); 643169689Skan print_generic_stmt (outf, chrec, 0); 644169689Skan if (chrec == chrec_known) 645169689Skan fprintf (outf, " (no dependence)\n"); 646169689Skan else if (chrec_contains_undetermined (chrec)) 647169689Skan fprintf (outf, " (don't know)\n"); 648169689Skan else 649169689Skan { 650169689Skan tree last_iteration = SUB_LAST_CONFLICT (subscript); 651169689Skan fprintf (outf, " last_conflict: "); 652169689Skan print_generic_stmt (outf, last_iteration, 0); 653169689Skan } 654169689Skan 655169689Skan chrec = SUB_CONFLICTS_IN_B (subscript); 656169689Skan fprintf (outf, " iterations_that_access_an_element_twice_in_B: "); 657169689Skan print_generic_stmt (outf, chrec, 0); 658169689Skan if (chrec == chrec_known) 659169689Skan fprintf (outf, " (no dependence)\n"); 660169689Skan else if (chrec_contains_undetermined (chrec)) 661169689Skan fprintf (outf, " (don't know)\n"); 662169689Skan else 663169689Skan { 664169689Skan tree last_iteration = SUB_LAST_CONFLICT (subscript); 665169689Skan fprintf (outf, " last_conflict: "); 666169689Skan print_generic_stmt (outf, last_iteration, 0); 667169689Skan } 668169689Skan 669169689Skan fprintf (outf, " (Subscript distance: "); 670169689Skan print_generic_stmt (outf, SUB_DISTANCE (subscript), 0); 671169689Skan fprintf (outf, " )\n"); 672169689Skan fprintf (outf, " )\n"); 673169689Skan} 674169689Skan 675169689Skan/* Print the classic direction vector DIRV to OUTF. */ 676169689Skan 677169689Skanvoid 678169689Skanprint_direction_vector (FILE *outf, 679169689Skan lambda_vector dirv, 680169689Skan int length) 681169689Skan{ 682169689Skan int eq; 683169689Skan 684169689Skan for (eq = 0; eq < length; eq++) 685169689Skan { 686169689Skan enum data_dependence_direction dir = dirv[eq]; 687169689Skan 688169689Skan switch (dir) 689169689Skan { 690169689Skan case dir_positive: 691169689Skan fprintf (outf, " +"); 692169689Skan break; 693169689Skan case dir_negative: 694169689Skan fprintf (outf, " -"); 695169689Skan break; 696169689Skan case dir_equal: 697169689Skan fprintf (outf, " ="); 698169689Skan break; 699169689Skan case dir_positive_or_equal: 700169689Skan fprintf (outf, " +="); 701169689Skan break; 702169689Skan case dir_positive_or_negative: 703169689Skan fprintf (outf, " +-"); 704169689Skan break; 705169689Skan case dir_negative_or_equal: 706169689Skan fprintf (outf, " -="); 707169689Skan break; 708169689Skan case dir_star: 709169689Skan fprintf (outf, " *"); 710169689Skan break; 711169689Skan default: 712169689Skan fprintf (outf, "indep"); 713169689Skan break; 714169689Skan } 715169689Skan } 716169689Skan fprintf (outf, "\n"); 717169689Skan} 718169689Skan 719169689Skan/* Print a vector of direction vectors. */ 720169689Skan 721169689Skanvoid 722169689Skanprint_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects, 723169689Skan int length) 724169689Skan{ 725169689Skan unsigned j; 726169689Skan lambda_vector v; 727169689Skan 728169689Skan for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++) 729169689Skan print_direction_vector (outf, v, length); 730169689Skan} 731169689Skan 732169689Skan/* Print a vector of distance vectors. */ 733169689Skan 734169689Skanvoid 735169689Skanprint_dist_vectors (FILE *outf, VEC (lambda_vector, heap) *dist_vects, 736169689Skan int length) 737169689Skan{ 738169689Skan unsigned j; 739169689Skan lambda_vector v; 740169689Skan 741169689Skan for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++) 742169689Skan print_lambda_vector (outf, v, length); 743169689Skan} 744169689Skan 745169689Skan/* Debug version. */ 746169689Skan 747169689Skanvoid 748169689Skandebug_data_dependence_relation (struct data_dependence_relation *ddr) 749169689Skan{ 750169689Skan dump_data_dependence_relation (stderr, ddr); 751169689Skan} 752169689Skan 753169689Skan/* Dump function for a DATA_DEPENDENCE_RELATION structure. */ 754169689Skan 755169689Skanvoid 756169689Skandump_data_dependence_relation (FILE *outf, 757169689Skan struct data_dependence_relation *ddr) 758169689Skan{ 759169689Skan struct data_reference *dra, *drb; 760169689Skan 761169689Skan dra = DDR_A (ddr); 762169689Skan drb = DDR_B (ddr); 763169689Skan fprintf (outf, "(Data Dep: \n"); 764169689Skan if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) 765169689Skan fprintf (outf, " (don't know)\n"); 766169689Skan 767169689Skan else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) 768169689Skan fprintf (outf, " (no dependence)\n"); 769169689Skan 770169689Skan else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) 771169689Skan { 772169689Skan unsigned int i; 773169689Skan struct loop *loopi; 774169689Skan 775169689Skan for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 776169689Skan { 777169689Skan fprintf (outf, " access_fn_A: "); 778169689Skan print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0); 779169689Skan fprintf (outf, " access_fn_B: "); 780169689Skan print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0); 781169689Skan dump_subscript (outf, DDR_SUBSCRIPT (ddr, i)); 782169689Skan } 783169689Skan 784169689Skan fprintf (outf, " loop nest: ("); 785169689Skan for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++) 786169689Skan fprintf (outf, "%d ", loopi->num); 787169689Skan fprintf (outf, ")\n"); 788169689Skan 789169689Skan for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) 790169689Skan { 791169689Skan fprintf (outf, " distance_vector: "); 792169689Skan print_lambda_vector (outf, DDR_DIST_VECT (ddr, i), 793169689Skan DDR_NB_LOOPS (ddr)); 794169689Skan } 795169689Skan 796169689Skan for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++) 797169689Skan { 798169689Skan fprintf (outf, " direction_vector: "); 799169689Skan print_direction_vector (outf, DDR_DIR_VECT (ddr, i), 800169689Skan DDR_NB_LOOPS (ddr)); 801169689Skan } 802169689Skan } 803169689Skan 804169689Skan fprintf (outf, ")\n"); 805169689Skan} 806169689Skan 807169689Skan/* Dump function for a DATA_DEPENDENCE_DIRECTION structure. */ 808169689Skan 809169689Skanvoid 810169689Skandump_data_dependence_direction (FILE *file, 811169689Skan enum data_dependence_direction dir) 812169689Skan{ 813169689Skan switch (dir) 814169689Skan { 815169689Skan case dir_positive: 816169689Skan fprintf (file, "+"); 817169689Skan break; 818169689Skan 819169689Skan case dir_negative: 820169689Skan fprintf (file, "-"); 821169689Skan break; 822169689Skan 823169689Skan case dir_equal: 824169689Skan fprintf (file, "="); 825169689Skan break; 826169689Skan 827169689Skan case dir_positive_or_negative: 828169689Skan fprintf (file, "+-"); 829169689Skan break; 830169689Skan 831169689Skan case dir_positive_or_equal: 832169689Skan fprintf (file, "+="); 833169689Skan break; 834169689Skan 835169689Skan case dir_negative_or_equal: 836169689Skan fprintf (file, "-="); 837169689Skan break; 838169689Skan 839169689Skan case dir_star: 840169689Skan fprintf (file, "*"); 841169689Skan break; 842169689Skan 843169689Skan default: 844169689Skan break; 845169689Skan } 846169689Skan} 847169689Skan 848169689Skan/* Dumps the distance and direction vectors in FILE. DDRS contains 849169689Skan the dependence relations, and VECT_SIZE is the size of the 850169689Skan dependence vectors, or in other words the number of loops in the 851169689Skan considered nest. */ 852169689Skan 853169689Skanvoid 854169689Skandump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs) 855169689Skan{ 856169689Skan unsigned int i, j; 857169689Skan struct data_dependence_relation *ddr; 858169689Skan lambda_vector v; 859169689Skan 860169689Skan for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) 861169689Skan if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr)) 862169689Skan { 863169689Skan for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++) 864169689Skan { 865169689Skan fprintf (file, "DISTANCE_V ("); 866169689Skan print_lambda_vector (file, v, DDR_NB_LOOPS (ddr)); 867169689Skan fprintf (file, ")\n"); 868169689Skan } 869169689Skan 870169689Skan for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++) 871169689Skan { 872169689Skan fprintf (file, "DIRECTION_V ("); 873169689Skan print_direction_vector (file, v, DDR_NB_LOOPS (ddr)); 874169689Skan fprintf (file, ")\n"); 875169689Skan } 876169689Skan } 877169689Skan 878169689Skan fprintf (file, "\n\n"); 879169689Skan} 880169689Skan 881169689Skan/* Dumps the data dependence relations DDRS in FILE. */ 882169689Skan 883169689Skanvoid 884169689Skandump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs) 885169689Skan{ 886169689Skan unsigned int i; 887169689Skan struct data_dependence_relation *ddr; 888169689Skan 889169689Skan for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) 890169689Skan dump_data_dependence_relation (file, ddr); 891169689Skan 892169689Skan fprintf (file, "\n\n"); 893169689Skan} 894169689Skan 895169689Skan 896169689Skan 897169689Skan/* Estimate the number of iterations from the size of the data and the 898169689Skan access functions. */ 899169689Skan 900169689Skanstatic void 901169689Skanestimate_niter_from_size_of_data (struct loop *loop, 902169689Skan tree opnd0, 903169689Skan tree access_fn, 904169689Skan tree stmt) 905169689Skan{ 906169689Skan tree estimation = NULL_TREE; 907169689Skan tree array_size, data_size, element_size; 908169689Skan tree init, step; 909169689Skan 910169689Skan init = initial_condition (access_fn); 911169689Skan step = evolution_part_in_loop_num (access_fn, loop->num); 912169689Skan 913169689Skan array_size = TYPE_SIZE (TREE_TYPE (opnd0)); 914169689Skan element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0))); 915169689Skan if (array_size == NULL_TREE 916169689Skan || TREE_CODE (array_size) != INTEGER_CST 917169689Skan || TREE_CODE (element_size) != INTEGER_CST) 918169689Skan return; 919169689Skan 920169689Skan data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node, 921169689Skan array_size, element_size); 922169689Skan 923169689Skan if (init != NULL_TREE 924169689Skan && step != NULL_TREE 925169689Skan && TREE_CODE (init) == INTEGER_CST 926169689Skan && TREE_CODE (step) == INTEGER_CST) 927169689Skan { 928169689Skan tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step); 929169689Skan tree sign = fold_binary (GT_EXPR, boolean_type_node, i_plus_s, init); 930169689Skan 931169689Skan if (sign == boolean_true_node) 932169689Skan estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node, 933169689Skan fold_build2 (MINUS_EXPR, integer_type_node, 934169689Skan data_size, init), step); 935169689Skan 936169689Skan /* When the step is negative, as in PR23386: (init = 3, step = 937169689Skan 0ffffffff, data_size = 100), we have to compute the 938169689Skan estimation as ceil_div (init, 0 - step) + 1. */ 939169689Skan else if (sign == boolean_false_node) 940169689Skan estimation = 941169689Skan fold_build2 (PLUS_EXPR, integer_type_node, 942169689Skan fold_build2 (CEIL_DIV_EXPR, integer_type_node, 943169689Skan init, 944169689Skan fold_build2 (MINUS_EXPR, unsigned_type_node, 945169689Skan integer_zero_node, step)), 946169689Skan integer_one_node); 947169689Skan 948169689Skan if (estimation) 949169689Skan record_estimate (loop, estimation, boolean_true_node, stmt); 950169689Skan } 951169689Skan} 952169689Skan 953169689Skan/* Given an ARRAY_REF node REF, records its access functions. 954169689Skan Example: given A[i][3], record in ACCESS_FNS the opnd1 function, 955169689Skan i.e. the constant "3", then recursively call the function on opnd0, 956169689Skan i.e. the ARRAY_REF "A[i]". 957169689Skan If ESTIMATE_ONLY is true, we just set the estimated number of loop 958169689Skan iterations, we don't store the access function. 959169689Skan The function returns the base name: "A". */ 960169689Skan 961169689Skanstatic tree 962169689Skananalyze_array_indexes (struct loop *loop, 963169689Skan VEC(tree,heap) **access_fns, 964169689Skan tree ref, tree stmt, 965169689Skan bool estimate_only) 966169689Skan{ 967169689Skan tree opnd0, opnd1; 968169689Skan tree access_fn; 969169689Skan 970169689Skan opnd0 = TREE_OPERAND (ref, 0); 971169689Skan opnd1 = TREE_OPERAND (ref, 1); 972169689Skan 973169689Skan /* The detection of the evolution function for this data access is 974169689Skan postponed until the dependence test. This lazy strategy avoids 975169689Skan the computation of access functions that are of no interest for 976169689Skan the optimizers. */ 977169689Skan access_fn = instantiate_parameters 978169689Skan (loop, analyze_scalar_evolution (loop, opnd1)); 979169689Skan 980169689Skan if (estimate_only 981169689Skan && chrec_contains_undetermined (loop->estimated_nb_iterations)) 982169689Skan estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt); 983169689Skan 984169689Skan if (!estimate_only) 985169689Skan VEC_safe_push (tree, heap, *access_fns, access_fn); 986169689Skan 987169689Skan /* Recursively record other array access functions. */ 988169689Skan if (TREE_CODE (opnd0) == ARRAY_REF) 989169689Skan return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only); 990169689Skan 991169689Skan /* Return the base name of the data access. */ 992169689Skan else 993169689Skan return opnd0; 994169689Skan} 995169689Skan 996169689Skan/* For an array reference REF contained in STMT, attempt to bound the 997169689Skan number of iterations in the loop containing STMT */ 998169689Skan 999169689Skanvoid 1000169689Skanestimate_iters_using_array (tree stmt, tree ref) 1001169689Skan{ 1002169689Skan analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt, 1003169689Skan true); 1004169689Skan} 1005169689Skan 1006169689Skan/* For a data reference REF contained in the statement STMT, initialize 1007169689Skan a DATA_REFERENCE structure, and return it. IS_READ flag has to be 1008169689Skan set to true when REF is in the right hand side of an 1009169689Skan assignment. */ 1010169689Skan 1011169689Skanstruct data_reference * 1012169689Skananalyze_array (tree stmt, tree ref, bool is_read) 1013169689Skan{ 1014169689Skan struct data_reference *res; 1015169689Skan VEC(tree,heap) *acc_fns; 1016169689Skan 1017169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1018169689Skan { 1019169689Skan fprintf (dump_file, "(analyze_array \n"); 1020169689Skan fprintf (dump_file, " (ref = "); 1021169689Skan print_generic_stmt (dump_file, ref, 0); 1022169689Skan fprintf (dump_file, ")\n"); 1023169689Skan } 1024169689Skan 1025169689Skan res = XNEW (struct data_reference); 1026169689Skan 1027169689Skan DR_STMT (res) = stmt; 1028169689Skan DR_REF (res) = ref; 1029169689Skan acc_fns = VEC_alloc (tree, heap, 3); 1030169689Skan DR_BASE_OBJECT (res) = analyze_array_indexes 1031169689Skan (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false); 1032169689Skan DR_TYPE (res) = ARRAY_REF_TYPE; 1033169689Skan DR_SET_ACCESS_FNS (res, acc_fns); 1034169689Skan DR_IS_READ (res) = is_read; 1035169689Skan DR_BASE_ADDRESS (res) = NULL_TREE; 1036169689Skan DR_OFFSET (res) = NULL_TREE; 1037169689Skan DR_INIT (res) = NULL_TREE; 1038169689Skan DR_STEP (res) = NULL_TREE; 1039169689Skan DR_OFFSET_MISALIGNMENT (res) = NULL_TREE; 1040169689Skan DR_MEMTAG (res) = NULL_TREE; 1041169689Skan DR_PTR_INFO (res) = NULL; 1042169689Skan 1043169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1044169689Skan fprintf (dump_file, ")\n"); 1045169689Skan 1046169689Skan return res; 1047169689Skan} 1048169689Skan 1049169689Skan/* Analyze an indirect memory reference, REF, that comes from STMT. 1050169689Skan IS_READ is true if this is an indirect load, and false if it is 1051169689Skan an indirect store. 1052169689Skan Return a new data reference structure representing the indirect_ref, or 1053169689Skan NULL if we cannot describe the access function. */ 1054169689Skan 1055169689Skanstatic struct data_reference * 1056169689Skananalyze_indirect_ref (tree stmt, tree ref, bool is_read) 1057169689Skan{ 1058169689Skan struct loop *loop = loop_containing_stmt (stmt); 1059169689Skan tree ptr_ref = TREE_OPERAND (ref, 0); 1060169689Skan tree access_fn = analyze_scalar_evolution (loop, ptr_ref); 1061169689Skan tree init = initial_condition_in_loop_num (access_fn, loop->num); 1062169689Skan tree base_address = NULL_TREE, evolution, step = NULL_TREE; 1063169689Skan struct ptr_info_def *ptr_info = NULL; 1064169689Skan 1065169689Skan if (TREE_CODE (ptr_ref) == SSA_NAME) 1066169689Skan ptr_info = SSA_NAME_PTR_INFO (ptr_ref); 1067169689Skan 1068169689Skan STRIP_NOPS (init); 1069169689Skan if (access_fn == chrec_dont_know || !init || init == chrec_dont_know) 1070169689Skan { 1071169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1072169689Skan { 1073169689Skan fprintf (dump_file, "\nBad access function of ptr: "); 1074169689Skan print_generic_expr (dump_file, ref, TDF_SLIM); 1075169689Skan fprintf (dump_file, "\n"); 1076169689Skan } 1077169689Skan return NULL; 1078169689Skan } 1079169689Skan 1080169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1081169689Skan { 1082169689Skan fprintf (dump_file, "\nAccess function of ptr: "); 1083169689Skan print_generic_expr (dump_file, access_fn, TDF_SLIM); 1084169689Skan fprintf (dump_file, "\n"); 1085169689Skan } 1086169689Skan 1087169689Skan if (!expr_invariant_in_loop_p (loop, init)) 1088169689Skan { 1089169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1090169689Skan fprintf (dump_file, "\ninitial condition is not loop invariant.\n"); 1091169689Skan } 1092169689Skan else 1093169689Skan { 1094169689Skan base_address = init; 1095169689Skan evolution = evolution_part_in_loop_num (access_fn, loop->num); 1096169689Skan if (evolution != chrec_dont_know) 1097169689Skan { 1098169689Skan if (!evolution) 1099169689Skan step = ssize_int (0); 1100169689Skan else 1101169689Skan { 1102169689Skan if (TREE_CODE (evolution) == INTEGER_CST) 1103169689Skan step = fold_convert (ssizetype, evolution); 1104169689Skan else 1105169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1106169689Skan fprintf (dump_file, "\nnon constant step for ptr access.\n"); 1107169689Skan } 1108169689Skan } 1109169689Skan else 1110169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1111169689Skan fprintf (dump_file, "\nunknown evolution of ptr.\n"); 1112169689Skan } 1113169689Skan return init_data_ref (stmt, ref, NULL_TREE, access_fn, is_read, base_address, 1114169689Skan NULL_TREE, step, NULL_TREE, NULL_TREE, 1115169689Skan ptr_info, POINTER_REF_TYPE); 1116169689Skan} 1117169689Skan 1118169689Skan/* For a data reference REF contained in the statement STMT, initialize 1119169689Skan a DATA_REFERENCE structure, and return it. */ 1120169689Skan 1121169689Skanstruct data_reference * 1122169689Skaninit_data_ref (tree stmt, 1123169689Skan tree ref, 1124169689Skan tree base, 1125169689Skan tree access_fn, 1126169689Skan bool is_read, 1127169689Skan tree base_address, 1128169689Skan tree init_offset, 1129169689Skan tree step, 1130169689Skan tree misalign, 1131169689Skan tree memtag, 1132169689Skan struct ptr_info_def *ptr_info, 1133169689Skan enum data_ref_type type) 1134169689Skan{ 1135169689Skan struct data_reference *res; 1136169689Skan VEC(tree,heap) *acc_fns; 1137169689Skan 1138169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1139169689Skan { 1140169689Skan fprintf (dump_file, "(init_data_ref \n"); 1141169689Skan fprintf (dump_file, " (ref = "); 1142169689Skan print_generic_stmt (dump_file, ref, 0); 1143169689Skan fprintf (dump_file, ")\n"); 1144169689Skan } 1145169689Skan 1146169689Skan res = XNEW (struct data_reference); 1147169689Skan 1148169689Skan DR_STMT (res) = stmt; 1149169689Skan DR_REF (res) = ref; 1150169689Skan DR_BASE_OBJECT (res) = base; 1151169689Skan DR_TYPE (res) = type; 1152169689Skan acc_fns = VEC_alloc (tree, heap, 3); 1153169689Skan DR_SET_ACCESS_FNS (res, acc_fns); 1154169689Skan VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn); 1155169689Skan DR_IS_READ (res) = is_read; 1156169689Skan DR_BASE_ADDRESS (res) = base_address; 1157169689Skan DR_OFFSET (res) = init_offset; 1158169689Skan DR_INIT (res) = NULL_TREE; 1159169689Skan DR_STEP (res) = step; 1160169689Skan DR_OFFSET_MISALIGNMENT (res) = misalign; 1161169689Skan DR_MEMTAG (res) = memtag; 1162169689Skan DR_PTR_INFO (res) = ptr_info; 1163169689Skan 1164169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1165169689Skan fprintf (dump_file, ")\n"); 1166169689Skan 1167169689Skan return res; 1168169689Skan} 1169169689Skan 1170169689Skan/* Function strip_conversions 1171169689Skan 1172169689Skan Strip conversions that don't narrow the mode. */ 1173169689Skan 1174169689Skanstatic tree 1175169689Skanstrip_conversion (tree expr) 1176169689Skan{ 1177169689Skan tree to, ti, oprnd0; 1178169689Skan 1179169689Skan while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR) 1180169689Skan { 1181169689Skan to = TREE_TYPE (expr); 1182169689Skan oprnd0 = TREE_OPERAND (expr, 0); 1183169689Skan ti = TREE_TYPE (oprnd0); 1184169689Skan 1185169689Skan if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti)) 1186169689Skan return NULL_TREE; 1187169689Skan if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti))) 1188169689Skan return NULL_TREE; 1189169689Skan 1190169689Skan expr = oprnd0; 1191169689Skan } 1192169689Skan return expr; 1193169689Skan} 1194169689Skan 1195169689Skan 1196169689Skan/* Function analyze_offset_expr 1197169689Skan 1198169689Skan Given an offset expression EXPR received from get_inner_reference, analyze 1199169689Skan it and create an expression for INITIAL_OFFSET by substituting the variables 1200169689Skan of EXPR with initial_condition of the corresponding access_fn in the loop. 1201169689Skan E.g., 1202169689Skan for i 1203169689Skan for (j = 3; j < N; j++) 1204169689Skan a[j].b[i][j] = 0; 1205169689Skan 1206169689Skan For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be 1207169689Skan substituted, since its access_fn in the inner loop is i. 'j' will be 1208169689Skan substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where 1209169689Skan C` = 3 * C_j + C. 1210169689Skan 1211169689Skan Compute MISALIGN (the misalignment of the data reference initial access from 1212169689Skan its base). Misalignment can be calculated only if all the variables can be 1213169689Skan substituted with constants, otherwise, we record maximum possible alignment 1214169689Skan in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN 1215169689Skan will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be 1216169689Skan recorded in ALIGNED_TO. 1217169689Skan 1218169689Skan STEP is an evolution of the data reference in this loop in bytes. 1219169689Skan In the above example, STEP is C_j. 1220169689Skan 1221169689Skan Return FALSE, if the analysis fails, e.g., there is no access_fn for a 1222169689Skan variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO 1223169689Skan and STEP) are NULL_TREEs. Otherwise, return TRUE. 1224169689Skan 1225169689Skan*/ 1226169689Skan 1227169689Skanstatic bool 1228169689Skananalyze_offset_expr (tree expr, 1229169689Skan struct loop *loop, 1230169689Skan tree *initial_offset, 1231169689Skan tree *misalign, 1232169689Skan tree *aligned_to, 1233169689Skan tree *step) 1234169689Skan{ 1235169689Skan tree oprnd0; 1236169689Skan tree oprnd1; 1237169689Skan tree left_offset = ssize_int (0); 1238169689Skan tree right_offset = ssize_int (0); 1239169689Skan tree left_misalign = ssize_int (0); 1240169689Skan tree right_misalign = ssize_int (0); 1241169689Skan tree left_step = ssize_int (0); 1242169689Skan tree right_step = ssize_int (0); 1243169689Skan enum tree_code code; 1244169689Skan tree init, evolution; 1245169689Skan tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE; 1246169689Skan 1247169689Skan *step = NULL_TREE; 1248169689Skan *misalign = NULL_TREE; 1249169689Skan *aligned_to = NULL_TREE; 1250169689Skan *initial_offset = NULL_TREE; 1251169689Skan 1252169689Skan /* Strip conversions that don't narrow the mode. */ 1253169689Skan expr = strip_conversion (expr); 1254169689Skan if (!expr) 1255169689Skan return false; 1256169689Skan 1257169689Skan /* Stop conditions: 1258169689Skan 1. Constant. */ 1259169689Skan if (TREE_CODE (expr) == INTEGER_CST) 1260169689Skan { 1261169689Skan *initial_offset = fold_convert (ssizetype, expr); 1262169689Skan *misalign = fold_convert (ssizetype, expr); 1263169689Skan *step = ssize_int (0); 1264169689Skan return true; 1265169689Skan } 1266169689Skan 1267169689Skan /* 2. Variable. Try to substitute with initial_condition of the corresponding 1268169689Skan access_fn in the current loop. */ 1269169689Skan if (SSA_VAR_P (expr)) 1270169689Skan { 1271169689Skan tree access_fn = analyze_scalar_evolution (loop, expr); 1272169689Skan 1273169689Skan if (access_fn == chrec_dont_know) 1274169689Skan /* No access_fn. */ 1275169689Skan return false; 1276169689Skan 1277169689Skan init = initial_condition_in_loop_num (access_fn, loop->num); 1278169689Skan if (!expr_invariant_in_loop_p (loop, init)) 1279169689Skan /* Not enough information: may be not loop invariant. 1280169689Skan E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its 1281169689Skan initial_condition is D, but it depends on i - loop's induction 1282169689Skan variable. */ 1283169689Skan return false; 1284169689Skan 1285169689Skan evolution = evolution_part_in_loop_num (access_fn, loop->num); 1286169689Skan if (evolution && TREE_CODE (evolution) != INTEGER_CST) 1287169689Skan /* Evolution is not constant. */ 1288169689Skan return false; 1289169689Skan 1290169689Skan if (TREE_CODE (init) == INTEGER_CST) 1291169689Skan *misalign = fold_convert (ssizetype, init); 1292169689Skan else 1293169689Skan /* Not constant, misalignment cannot be calculated. */ 1294169689Skan *misalign = NULL_TREE; 1295169689Skan 1296169689Skan *initial_offset = fold_convert (ssizetype, init); 1297169689Skan 1298169689Skan *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0); 1299169689Skan return true; 1300169689Skan } 1301169689Skan 1302169689Skan /* Recursive computation. */ 1303169689Skan if (!BINARY_CLASS_P (expr)) 1304169689Skan { 1305169689Skan /* We expect to get binary expressions (PLUS/MINUS and MULT). */ 1306169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1307169689Skan { 1308169689Skan fprintf (dump_file, "\nNot binary expression "); 1309169689Skan print_generic_expr (dump_file, expr, TDF_SLIM); 1310169689Skan fprintf (dump_file, "\n"); 1311169689Skan } 1312169689Skan return false; 1313169689Skan } 1314169689Skan oprnd0 = TREE_OPERAND (expr, 0); 1315169689Skan oprnd1 = TREE_OPERAND (expr, 1); 1316169689Skan 1317169689Skan if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign, 1318169689Skan &left_aligned_to, &left_step) 1319169689Skan || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign, 1320169689Skan &right_aligned_to, &right_step)) 1321169689Skan return false; 1322169689Skan 1323169689Skan /* The type of the operation: plus, minus or mult. */ 1324169689Skan code = TREE_CODE (expr); 1325169689Skan switch (code) 1326169689Skan { 1327169689Skan case MULT_EXPR: 1328169689Skan if (TREE_CODE (right_offset) != INTEGER_CST) 1329169689Skan /* RIGHT_OFFSET can be not constant. For example, for arrays of variable 1330169689Skan sized types. 1331169689Skan FORNOW: We don't support such cases. */ 1332169689Skan return false; 1333169689Skan 1334169689Skan /* Strip conversions that don't narrow the mode. */ 1335169689Skan left_offset = strip_conversion (left_offset); 1336169689Skan if (!left_offset) 1337169689Skan return false; 1338169689Skan /* Misalignment computation. */ 1339169689Skan if (SSA_VAR_P (left_offset)) 1340169689Skan { 1341169689Skan /* If the left side contains variables that can't be substituted with 1342169689Skan constants, the misalignment is unknown. However, if the right side 1343169689Skan is a multiple of some alignment, we know that the expression is 1344169689Skan aligned to it. Therefore, we record such maximum possible value. 1345169689Skan */ 1346169689Skan *misalign = NULL_TREE; 1347169689Skan *aligned_to = ssize_int (highest_pow2_factor (right_offset)); 1348169689Skan } 1349169689Skan else 1350169689Skan { 1351169689Skan /* The left operand was successfully substituted with constant. */ 1352169689Skan if (left_misalign) 1353169689Skan { 1354169689Skan /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is 1355169689Skan NULL_TREE. */ 1356169689Skan *misalign = size_binop (code, left_misalign, right_misalign); 1357169689Skan if (left_aligned_to && right_aligned_to) 1358169689Skan *aligned_to = size_binop (MIN_EXPR, left_aligned_to, 1359169689Skan right_aligned_to); 1360169689Skan else 1361169689Skan *aligned_to = left_aligned_to ? 1362169689Skan left_aligned_to : right_aligned_to; 1363169689Skan } 1364169689Skan else 1365169689Skan *misalign = NULL_TREE; 1366169689Skan } 1367169689Skan 1368169689Skan /* Step calculation. */ 1369169689Skan /* Multiply the step by the right operand. */ 1370169689Skan *step = size_binop (MULT_EXPR, left_step, right_offset); 1371169689Skan break; 1372169689Skan 1373169689Skan case PLUS_EXPR: 1374169689Skan case MINUS_EXPR: 1375169689Skan /* Combine the recursive calculations for step and misalignment. */ 1376169689Skan *step = size_binop (code, left_step, right_step); 1377169689Skan 1378169689Skan /* Unknown alignment. */ 1379169689Skan if ((!left_misalign && !left_aligned_to) 1380169689Skan || (!right_misalign && !right_aligned_to)) 1381169689Skan { 1382169689Skan *misalign = NULL_TREE; 1383169689Skan *aligned_to = NULL_TREE; 1384169689Skan break; 1385169689Skan } 1386169689Skan 1387169689Skan if (left_misalign && right_misalign) 1388169689Skan *misalign = size_binop (code, left_misalign, right_misalign); 1389169689Skan else 1390169689Skan *misalign = left_misalign ? left_misalign : right_misalign; 1391169689Skan 1392169689Skan if (left_aligned_to && right_aligned_to) 1393169689Skan *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to); 1394169689Skan else 1395169689Skan *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to; 1396169689Skan 1397169689Skan break; 1398169689Skan 1399169689Skan default: 1400169689Skan gcc_unreachable (); 1401169689Skan } 1402169689Skan 1403169689Skan /* Compute offset. */ 1404169689Skan *initial_offset = fold_convert (ssizetype, 1405169689Skan fold_build2 (code, TREE_TYPE (left_offset), 1406169689Skan left_offset, 1407169689Skan right_offset)); 1408169689Skan return true; 1409169689Skan} 1410169689Skan 1411169689Skan/* Function address_analysis 1412169689Skan 1413169689Skan Return the BASE of the address expression EXPR. 1414169689Skan Also compute the OFFSET from BASE, MISALIGN and STEP. 1415169689Skan 1416169689Skan Input: 1417169689Skan EXPR - the address expression that is being analyzed 1418169689Skan STMT - the statement that contains EXPR or its original memory reference 1419169689Skan IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR 1420169689Skan DR - data_reference struct for the original memory reference 1421169689Skan 1422169689Skan Output: 1423169689Skan BASE (returned value) - the base of the data reference EXPR. 1424169689Skan INITIAL_OFFSET - initial offset of EXPR from BASE (an expression) 1425169689Skan MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the 1426169689Skan computation is impossible 1427169689Skan ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 1428169689Skan calculated (doesn't depend on variables) 1429169689Skan STEP - evolution of EXPR in the loop 1430169689Skan 1431169689Skan If something unexpected is encountered (an unsupported form of data-ref), 1432169689Skan then NULL_TREE is returned. 1433169689Skan */ 1434169689Skan 1435169689Skanstatic tree 1436169689Skanaddress_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr, 1437169689Skan tree *offset, tree *misalign, tree *aligned_to, tree *step) 1438169689Skan{ 1439169689Skan tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1; 1440169689Skan tree address_offset = ssize_int (0), address_misalign = ssize_int (0); 1441169689Skan tree dummy, address_aligned_to = NULL_TREE; 1442169689Skan struct ptr_info_def *dummy1; 1443169689Skan subvar_t dummy2; 1444169689Skan 1445169689Skan switch (TREE_CODE (expr)) 1446169689Skan { 1447169689Skan case PLUS_EXPR: 1448169689Skan case MINUS_EXPR: 1449169689Skan /* EXPR is of form {base +/- offset} (or {offset +/- base}). */ 1450169689Skan oprnd0 = TREE_OPERAND (expr, 0); 1451169689Skan oprnd1 = TREE_OPERAND (expr, 1); 1452169689Skan 1453169689Skan STRIP_NOPS (oprnd0); 1454169689Skan STRIP_NOPS (oprnd1); 1455169689Skan 1456169689Skan /* Recursively try to find the base of the address contained in EXPR. 1457169689Skan For offset, the returned base will be NULL. */ 1458169689Skan base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset, 1459169689Skan &address_misalign, &address_aligned_to, 1460169689Skan step); 1461169689Skan 1462169689Skan base_addr1 = address_analysis (oprnd1, stmt, is_read, dr, &address_offset, 1463169689Skan &address_misalign, &address_aligned_to, 1464169689Skan step); 1465169689Skan 1466169689Skan /* We support cases where only one of the operands contains an 1467169689Skan address. */ 1468169689Skan if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1)) 1469169689Skan { 1470169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1471169689Skan { 1472169689Skan fprintf (dump_file, 1473169689Skan "\neither more than one address or no addresses in expr "); 1474169689Skan print_generic_expr (dump_file, expr, TDF_SLIM); 1475169689Skan fprintf (dump_file, "\n"); 1476169689Skan } 1477169689Skan return NULL_TREE; 1478169689Skan } 1479169689Skan 1480169689Skan /* To revert STRIP_NOPS. */ 1481169689Skan oprnd0 = TREE_OPERAND (expr, 0); 1482169689Skan oprnd1 = TREE_OPERAND (expr, 1); 1483169689Skan 1484169689Skan offset_expr = base_addr0 ? 1485169689Skan fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0); 1486169689Skan 1487169689Skan /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is 1488169689Skan a number, we can add it to the misalignment value calculated for base, 1489169689Skan otherwise, misalignment is NULL. */ 1490169689Skan if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign) 1491169689Skan { 1492169689Skan *misalign = size_binop (TREE_CODE (expr), address_misalign, 1493169689Skan offset_expr); 1494169689Skan *aligned_to = address_aligned_to; 1495169689Skan } 1496169689Skan else 1497169689Skan { 1498169689Skan *misalign = NULL_TREE; 1499169689Skan *aligned_to = NULL_TREE; 1500169689Skan } 1501169689Skan 1502169689Skan /* Combine offset (from EXPR {base + offset}) with the offset calculated 1503169689Skan for base. */ 1504169689Skan *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr); 1505169689Skan return base_addr0 ? base_addr0 : base_addr1; 1506169689Skan 1507169689Skan case ADDR_EXPR: 1508169689Skan base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read, 1509169689Skan &dr, offset, misalign, aligned_to, step, 1510169689Skan &dummy, &dummy1, &dummy2); 1511169689Skan return base_address; 1512169689Skan 1513169689Skan case SSA_NAME: 1514169689Skan if (!POINTER_TYPE_P (TREE_TYPE (expr))) 1515169689Skan { 1516169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1517169689Skan { 1518169689Skan fprintf (dump_file, "\nnot pointer SSA_NAME "); 1519169689Skan print_generic_expr (dump_file, expr, TDF_SLIM); 1520169689Skan fprintf (dump_file, "\n"); 1521169689Skan } 1522169689Skan return NULL_TREE; 1523169689Skan } 1524169689Skan *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr)))); 1525169689Skan *misalign = ssize_int (0); 1526169689Skan *offset = ssize_int (0); 1527169689Skan *step = ssize_int (0); 1528169689Skan return expr; 1529169689Skan 1530169689Skan default: 1531169689Skan return NULL_TREE; 1532169689Skan } 1533169689Skan} 1534169689Skan 1535169689Skan 1536169689Skan/* Function object_analysis 1537169689Skan 1538169689Skan Create a data-reference structure DR for MEMREF. 1539169689Skan Return the BASE of the data reference MEMREF if the analysis is possible. 1540169689Skan Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP. 1541169689Skan E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset 1542169689Skan 'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET 1543169689Skan instantiated with initial_conditions of access_functions of variables, 1544169689Skan and STEP is the evolution of the DR_REF in this loop. 1545169689Skan 1546169689Skan Function get_inner_reference is used for the above in case of ARRAY_REF and 1547169689Skan COMPONENT_REF. 1548169689Skan 1549169689Skan The structure of the function is as follows: 1550169689Skan Part 1: 1551169689Skan Case 1. For handled_component_p refs 1552169689Skan 1.1 build data-reference structure for MEMREF 1553169689Skan 1.2 call get_inner_reference 1554169689Skan 1.2.1 analyze offset expr received from get_inner_reference 1555169689Skan (fall through with BASE) 1556169689Skan Case 2. For declarations 1557169689Skan 2.1 set MEMTAG 1558169689Skan Case 3. For INDIRECT_REFs 1559169689Skan 3.1 build data-reference structure for MEMREF 1560169689Skan 3.2 analyze evolution and initial condition of MEMREF 1561169689Skan 3.3 set data-reference structure for MEMREF 1562169689Skan 3.4 call address_analysis to analyze INIT of the access function 1563169689Skan 3.5 extract memory tag 1564169689Skan 1565169689Skan Part 2: 1566169689Skan Combine the results of object and address analysis to calculate 1567169689Skan INITIAL_OFFSET, STEP and misalignment info. 1568169689Skan 1569169689Skan Input: 1570169689Skan MEMREF - the memory reference that is being analyzed 1571169689Skan STMT - the statement that contains MEMREF 1572169689Skan IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF 1573169689Skan 1574169689Skan Output: 1575169689Skan BASE_ADDRESS (returned value) - the base address of the data reference MEMREF 1576169689Skan E.g, if MEMREF is a.b[k].c[i][j] the returned 1577169689Skan base is &a. 1578169689Skan DR - data_reference struct for MEMREF 1579169689Skan INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression) 1580169689Skan MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of 1581169689Skan ALIGNMENT or NULL_TREE if the computation is impossible 1582169689Skan ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be 1583169689Skan calculated (doesn't depend on variables) 1584169689Skan STEP - evolution of the DR_REF in the loop 1585169689Skan MEMTAG - memory tag for aliasing purposes 1586169689Skan PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME 1587169689Skan SUBVARS - Sub-variables of the variable 1588169689Skan 1589169689Skan If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned, 1590169689Skan but DR can be created anyway. 1591169689Skan 1592169689Skan*/ 1593169689Skan 1594169689Skanstatic tree 1595169689Skanobject_analysis (tree memref, tree stmt, bool is_read, 1596169689Skan struct data_reference **dr, tree *offset, tree *misalign, 1597169689Skan tree *aligned_to, tree *step, tree *memtag, 1598169689Skan struct ptr_info_def **ptr_info, subvar_t *subvars) 1599169689Skan{ 1600169689Skan tree base = NULL_TREE, base_address = NULL_TREE; 1601169689Skan tree object_offset = ssize_int (0), object_misalign = ssize_int (0); 1602169689Skan tree object_step = ssize_int (0), address_step = ssize_int (0); 1603169689Skan tree address_offset = ssize_int (0), address_misalign = ssize_int (0); 1604169689Skan HOST_WIDE_INT pbitsize, pbitpos; 1605169689Skan tree poffset, bit_pos_in_bytes; 1606169689Skan enum machine_mode pmode; 1607169689Skan int punsignedp, pvolatilep; 1608169689Skan tree ptr_step = ssize_int (0), ptr_init = NULL_TREE; 1609169689Skan struct loop *loop = loop_containing_stmt (stmt); 1610169689Skan struct data_reference *ptr_dr = NULL; 1611169689Skan tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE; 1612169689Skan tree comp_ref = NULL_TREE; 1613169689Skan 1614169689Skan *ptr_info = NULL; 1615169689Skan 1616169689Skan /* Part 1: */ 1617169689Skan /* Case 1. handled_component_p refs. */ 1618169689Skan if (handled_component_p (memref)) 1619169689Skan { 1620169689Skan /* 1.1 build data-reference structure for MEMREF. */ 1621169689Skan if (!(*dr)) 1622169689Skan { 1623169689Skan if (TREE_CODE (memref) == ARRAY_REF) 1624169689Skan *dr = analyze_array (stmt, memref, is_read); 1625169689Skan else if (TREE_CODE (memref) == COMPONENT_REF) 1626169689Skan comp_ref = memref; 1627169689Skan else 1628169689Skan { 1629169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1630169689Skan { 1631169689Skan fprintf (dump_file, "\ndata-ref of unsupported type "); 1632169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1633169689Skan fprintf (dump_file, "\n"); 1634169689Skan } 1635169689Skan return NULL_TREE; 1636169689Skan } 1637169689Skan } 1638169689Skan 1639169689Skan /* 1.2 call get_inner_reference. */ 1640169689Skan /* Find the base and the offset from it. */ 1641169689Skan base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset, 1642169689Skan &pmode, &punsignedp, &pvolatilep, false); 1643169689Skan if (!base) 1644169689Skan { 1645169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1646169689Skan { 1647169689Skan fprintf (dump_file, "\nfailed to get inner ref for "); 1648169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1649169689Skan fprintf (dump_file, "\n"); 1650169689Skan } 1651169689Skan return NULL_TREE; 1652169689Skan } 1653169689Skan 1654169689Skan /* 1.2.1 analyze offset expr received from get_inner_reference. */ 1655169689Skan if (poffset 1656169689Skan && !analyze_offset_expr (poffset, loop, &object_offset, 1657169689Skan &object_misalign, &object_aligned_to, 1658169689Skan &object_step)) 1659169689Skan { 1660169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1661169689Skan { 1662169689Skan fprintf (dump_file, "\nfailed to compute offset or step for "); 1663169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1664169689Skan fprintf (dump_file, "\n"); 1665169689Skan } 1666169689Skan return NULL_TREE; 1667169689Skan } 1668169689Skan 1669169689Skan /* Add bit position to OFFSET and MISALIGN. */ 1670169689Skan 1671169689Skan bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT); 1672169689Skan /* Check that there is no remainder in bits. */ 1673169689Skan if (pbitpos%BITS_PER_UNIT) 1674169689Skan { 1675169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1676169689Skan fprintf (dump_file, "\nbit offset alignment.\n"); 1677169689Skan return NULL_TREE; 1678169689Skan } 1679169689Skan object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset); 1680169689Skan if (object_misalign) 1681169689Skan object_misalign = size_binop (PLUS_EXPR, object_misalign, 1682169689Skan bit_pos_in_bytes); 1683169689Skan 1684169689Skan memref = base; /* To continue analysis of BASE. */ 1685169689Skan /* fall through */ 1686169689Skan } 1687169689Skan 1688169689Skan /* Part 1: Case 2. Declarations. */ 1689169689Skan if (DECL_P (memref)) 1690169689Skan { 1691169689Skan /* We expect to get a decl only if we already have a DR, or with 1692169689Skan COMPONENT_REFs of type 'a[i].b'. */ 1693169689Skan if (!(*dr)) 1694169689Skan { 1695169689Skan if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF) 1696169689Skan { 1697169689Skan *dr = analyze_array (stmt, TREE_OPERAND (comp_ref, 0), is_read); 1698169689Skan if (DR_NUM_DIMENSIONS (*dr) != 1) 1699169689Skan { 1700169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1701169689Skan { 1702169689Skan fprintf (dump_file, "\n multidimensional component ref "); 1703169689Skan print_generic_expr (dump_file, comp_ref, TDF_SLIM); 1704169689Skan fprintf (dump_file, "\n"); 1705169689Skan } 1706169689Skan return NULL_TREE; 1707169689Skan } 1708169689Skan } 1709169689Skan else 1710169689Skan { 1711169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1712169689Skan { 1713169689Skan fprintf (dump_file, "\nunhandled decl "); 1714169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1715169689Skan fprintf (dump_file, "\n"); 1716169689Skan } 1717169689Skan return NULL_TREE; 1718169689Skan } 1719169689Skan } 1720169689Skan 1721169689Skan /* TODO: if during the analysis of INDIRECT_REF we get to an object, put 1722169689Skan the object in BASE_OBJECT field if we can prove that this is O.K., 1723169689Skan i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT. 1724169689Skan (e.g., if the object is an array base 'a', where 'a[N]', we must prove 1725169689Skan that every access with 'p' (the original INDIRECT_REF based on '&a') 1726169689Skan in the loop is within the array boundaries - from a[0] to a[N-1]). 1727169689Skan Otherwise, our alias analysis can be incorrect. 1728169689Skan Even if an access function based on BASE_OBJECT can't be build, update 1729169689Skan BASE_OBJECT field to enable us to prove that two data-refs are 1730169689Skan different (without access function, distance analysis is impossible). 1731169689Skan */ 1732169689Skan if (SSA_VAR_P (memref) && var_can_have_subvars (memref)) 1733169689Skan *subvars = get_subvars_for_var (memref); 1734169689Skan base_address = build_fold_addr_expr (memref); 1735169689Skan /* 2.1 set MEMTAG. */ 1736169689Skan *memtag = memref; 1737169689Skan } 1738169689Skan 1739169689Skan /* Part 1: Case 3. INDIRECT_REFs. */ 1740169689Skan else if (TREE_CODE (memref) == INDIRECT_REF) 1741169689Skan { 1742169689Skan tree ptr_ref = TREE_OPERAND (memref, 0); 1743169689Skan if (TREE_CODE (ptr_ref) == SSA_NAME) 1744169689Skan *ptr_info = SSA_NAME_PTR_INFO (ptr_ref); 1745169689Skan 1746169689Skan /* 3.1 build data-reference structure for MEMREF. */ 1747169689Skan ptr_dr = analyze_indirect_ref (stmt, memref, is_read); 1748169689Skan if (!ptr_dr) 1749169689Skan { 1750169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1751169689Skan { 1752169689Skan fprintf (dump_file, "\nfailed to create dr for "); 1753169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1754169689Skan fprintf (dump_file, "\n"); 1755169689Skan } 1756169689Skan return NULL_TREE; 1757169689Skan } 1758169689Skan 1759169689Skan /* 3.2 analyze evolution and initial condition of MEMREF. */ 1760169689Skan ptr_step = DR_STEP (ptr_dr); 1761169689Skan ptr_init = DR_BASE_ADDRESS (ptr_dr); 1762169689Skan if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init))) 1763169689Skan { 1764169689Skan *dr = (*dr) ? *dr : ptr_dr; 1765169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1766169689Skan { 1767169689Skan fprintf (dump_file, "\nbad pointer access "); 1768169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1769169689Skan fprintf (dump_file, "\n"); 1770169689Skan } 1771169689Skan return NULL_TREE; 1772169689Skan } 1773169689Skan 1774169689Skan if (integer_zerop (ptr_step) && !(*dr)) 1775169689Skan { 1776169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1777169689Skan fprintf (dump_file, "\nptr is loop invariant.\n"); 1778169689Skan *dr = ptr_dr; 1779169689Skan return NULL_TREE; 1780169689Skan 1781169689Skan /* If there exists DR for MEMREF, we are analyzing the base of 1782169689Skan handled component (PTR_INIT), which not necessary has evolution in 1783169689Skan the loop. */ 1784169689Skan } 1785169689Skan object_step = size_binop (PLUS_EXPR, object_step, ptr_step); 1786169689Skan 1787169689Skan /* 3.3 set data-reference structure for MEMREF. */ 1788169689Skan if (!*dr) 1789169689Skan *dr = ptr_dr; 1790169689Skan 1791169689Skan /* 3.4 call address_analysis to analyze INIT of the access 1792169689Skan function. */ 1793169689Skan base_address = address_analysis (ptr_init, stmt, is_read, *dr, 1794169689Skan &address_offset, &address_misalign, 1795169689Skan &address_aligned_to, &address_step); 1796169689Skan if (!base_address) 1797169689Skan { 1798169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1799169689Skan { 1800169689Skan fprintf (dump_file, "\nfailed to analyze address "); 1801169689Skan print_generic_expr (dump_file, ptr_init, TDF_SLIM); 1802169689Skan fprintf (dump_file, "\n"); 1803169689Skan } 1804169689Skan return NULL_TREE; 1805169689Skan } 1806169689Skan 1807169689Skan /* 3.5 extract memory tag. */ 1808169689Skan switch (TREE_CODE (base_address)) 1809169689Skan { 1810169689Skan case SSA_NAME: 1811169689Skan *memtag = get_var_ann (SSA_NAME_VAR (base_address))->symbol_mem_tag; 1812169689Skan if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME) 1813169689Skan *memtag = get_var_ann ( 1814169689Skan SSA_NAME_VAR (TREE_OPERAND (memref, 0)))->symbol_mem_tag; 1815169689Skan break; 1816169689Skan case ADDR_EXPR: 1817169689Skan *memtag = TREE_OPERAND (base_address, 0); 1818169689Skan break; 1819169689Skan default: 1820169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1821169689Skan { 1822169689Skan fprintf (dump_file, "\nno memtag for "); 1823169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1824169689Skan fprintf (dump_file, "\n"); 1825169689Skan } 1826169689Skan *memtag = NULL_TREE; 1827169689Skan break; 1828169689Skan } 1829169689Skan } 1830169689Skan 1831169689Skan if (!base_address) 1832169689Skan { 1833169689Skan /* MEMREF cannot be analyzed. */ 1834169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1835169689Skan { 1836169689Skan fprintf (dump_file, "\ndata-ref of unsupported type "); 1837169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1838169689Skan fprintf (dump_file, "\n"); 1839169689Skan } 1840169689Skan return NULL_TREE; 1841169689Skan } 1842169689Skan 1843169689Skan if (comp_ref) 1844169689Skan DR_REF (*dr) = comp_ref; 1845169689Skan 1846169689Skan if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag)) 1847169689Skan *subvars = get_subvars_for_var (*memtag); 1848169689Skan 1849169689Skan /* Part 2: Combine the results of object and address analysis to calculate 1850169689Skan INITIAL_OFFSET, STEP and misalignment info. */ 1851169689Skan *offset = size_binop (PLUS_EXPR, object_offset, address_offset); 1852169689Skan 1853169689Skan if ((!object_misalign && !object_aligned_to) 1854169689Skan || (!address_misalign && !address_aligned_to)) 1855169689Skan { 1856169689Skan *misalign = NULL_TREE; 1857169689Skan *aligned_to = NULL_TREE; 1858169689Skan } 1859169689Skan else 1860169689Skan { 1861169689Skan if (object_misalign && address_misalign) 1862169689Skan *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign); 1863169689Skan else 1864169689Skan *misalign = object_misalign ? object_misalign : address_misalign; 1865169689Skan if (object_aligned_to && address_aligned_to) 1866169689Skan *aligned_to = size_binop (MIN_EXPR, object_aligned_to, 1867169689Skan address_aligned_to); 1868169689Skan else 1869169689Skan *aligned_to = object_aligned_to ? 1870169689Skan object_aligned_to : address_aligned_to; 1871169689Skan } 1872169689Skan *step = size_binop (PLUS_EXPR, object_step, address_step); 1873169689Skan 1874169689Skan return base_address; 1875169689Skan} 1876169689Skan 1877169689Skan/* Function analyze_offset. 1878169689Skan 1879169689Skan Extract INVARIANT and CONSTANT parts from OFFSET. 1880169689Skan 1881169689Skan*/ 1882169689Skanstatic bool 1883169689Skananalyze_offset (tree offset, tree *invariant, tree *constant) 1884169689Skan{ 1885169689Skan tree op0, op1, constant_0, constant_1, invariant_0, invariant_1; 1886169689Skan enum tree_code code = TREE_CODE (offset); 1887169689Skan 1888169689Skan *invariant = NULL_TREE; 1889169689Skan *constant = NULL_TREE; 1890169689Skan 1891169689Skan /* Not PLUS/MINUS expression - recursion stop condition. */ 1892169689Skan if (code != PLUS_EXPR && code != MINUS_EXPR) 1893169689Skan { 1894169689Skan if (TREE_CODE (offset) == INTEGER_CST) 1895169689Skan *constant = offset; 1896169689Skan else 1897169689Skan *invariant = offset; 1898169689Skan return true; 1899169689Skan } 1900169689Skan 1901169689Skan op0 = TREE_OPERAND (offset, 0); 1902169689Skan op1 = TREE_OPERAND (offset, 1); 1903169689Skan 1904169689Skan /* Recursive call with the operands. */ 1905169689Skan if (!analyze_offset (op0, &invariant_0, &constant_0) 1906169689Skan || !analyze_offset (op1, &invariant_1, &constant_1)) 1907169689Skan return false; 1908169689Skan 1909169689Skan /* Combine the results. Add negation to the subtrahend in case of 1910169689Skan subtraction. */ 1911169689Skan if (constant_0 && constant_1) 1912169689Skan return false; 1913169689Skan *constant = constant_0 ? constant_0 : constant_1; 1914169689Skan if (code == MINUS_EXPR && constant_1) 1915169689Skan *constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant); 1916169689Skan 1917169689Skan if (invariant_0 && invariant_1) 1918169689Skan *invariant = 1919169689Skan fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1); 1920169689Skan else 1921169689Skan { 1922169689Skan *invariant = invariant_0 ? invariant_0 : invariant_1; 1923169689Skan if (code == MINUS_EXPR && invariant_1) 1924169689Skan *invariant = 1925169689Skan fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant); 1926169689Skan } 1927169689Skan return true; 1928169689Skan} 1929169689Skan 1930169689Skan/* Free the memory used by the data reference DR. */ 1931169689Skan 1932169689Skanstatic void 1933169689Skanfree_data_ref (data_reference_p dr) 1934169689Skan{ 1935169689Skan DR_FREE_ACCESS_FNS (dr); 1936169689Skan free (dr); 1937169689Skan} 1938169689Skan 1939169689Skan/* Function create_data_ref. 1940169689Skan 1941169689Skan Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS, 1942169689Skan DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO, 1943169689Skan DR_MEMTAG, and DR_POINTSTO_INFO fields. 1944169689Skan 1945169689Skan Input: 1946169689Skan MEMREF - the memory reference that is being analyzed 1947169689Skan STMT - the statement that contains MEMREF 1948169689Skan IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF 1949169689Skan 1950169689Skan Output: 1951169689Skan DR (returned value) - data_reference struct for MEMREF 1952169689Skan*/ 1953169689Skan 1954169689Skanstatic struct data_reference * 1955169689Skancreate_data_ref (tree memref, tree stmt, bool is_read) 1956169689Skan{ 1957169689Skan struct data_reference *dr = NULL; 1958169689Skan tree base_address, offset, step, misalign, memtag; 1959169689Skan struct loop *loop = loop_containing_stmt (stmt); 1960169689Skan tree invariant = NULL_TREE, constant = NULL_TREE; 1961169689Skan tree type_size, init_cond; 1962169689Skan struct ptr_info_def *ptr_info; 1963169689Skan subvar_t subvars = NULL; 1964169689Skan tree aligned_to, type = NULL_TREE, orig_offset; 1965169689Skan 1966169689Skan if (!memref) 1967169689Skan return NULL; 1968169689Skan 1969169689Skan base_address = object_analysis (memref, stmt, is_read, &dr, &offset, 1970169689Skan &misalign, &aligned_to, &step, &memtag, 1971169689Skan &ptr_info, &subvars); 1972169689Skan if (!dr || !base_address) 1973169689Skan { 1974169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1975169689Skan { 1976169689Skan fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for "); 1977169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 1978169689Skan fprintf (dump_file, "\n"); 1979169689Skan } 1980169689Skan return NULL; 1981169689Skan } 1982169689Skan 1983169689Skan DR_BASE_ADDRESS (dr) = base_address; 1984169689Skan DR_OFFSET (dr) = offset; 1985169689Skan DR_INIT (dr) = ssize_int (0); 1986169689Skan DR_STEP (dr) = step; 1987169689Skan DR_OFFSET_MISALIGNMENT (dr) = misalign; 1988169689Skan DR_ALIGNED_TO (dr) = aligned_to; 1989169689Skan DR_MEMTAG (dr) = memtag; 1990169689Skan DR_PTR_INFO (dr) = ptr_info; 1991169689Skan DR_SUBVARS (dr) = subvars; 1992169689Skan 1993169689Skan type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); 1994169689Skan 1995169689Skan /* Extract CONSTANT and INVARIANT from OFFSET. */ 1996169689Skan /* Remove cast from OFFSET and restore it for INVARIANT part. */ 1997169689Skan orig_offset = offset; 1998169689Skan STRIP_NOPS (offset); 1999169689Skan if (offset != orig_offset) 2000169689Skan type = TREE_TYPE (orig_offset); 2001169689Skan if (!analyze_offset (offset, &invariant, &constant)) 2002169689Skan { 2003169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2004169689Skan { 2005169689Skan fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's"); 2006169689Skan fprintf (dump_file, " offset for "); 2007169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 2008169689Skan fprintf (dump_file, "\n"); 2009169689Skan } 2010169689Skan return NULL; 2011169689Skan } 2012169689Skan if (type && invariant) 2013169689Skan invariant = fold_convert (type, invariant); 2014169689Skan 2015169689Skan /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field 2016169689Skan of DR. */ 2017169689Skan if (constant) 2018169689Skan { 2019169689Skan DR_INIT (dr) = fold_convert (ssizetype, constant); 2020169689Skan init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant), 2021169689Skan constant, type_size); 2022169689Skan } 2023169689Skan else 2024169689Skan DR_INIT (dr) = init_cond = ssize_int (0); 2025169689Skan 2026169689Skan if (invariant) 2027169689Skan DR_OFFSET (dr) = invariant; 2028169689Skan else 2029169689Skan DR_OFFSET (dr) = ssize_int (0); 2030169689Skan 2031169689Skan /* Change the access function for INIDIRECT_REFs, according to 2032169689Skan DR_BASE_ADDRESS. Analyze OFFSET calculated in object_analysis. OFFSET is 2033169689Skan an expression that can contain loop invariant expressions and constants. 2034169689Skan We put the constant part in the initial condition of the access function 2035169689Skan (for data dependence tests), and in DR_INIT of the data-ref. The loop 2036169689Skan invariant part is put in DR_OFFSET. 2037169689Skan The evolution part of the access function is STEP calculated in 2038169689Skan object_analysis divided by the size of data type. 2039169689Skan */ 2040169689Skan if (!DR_BASE_OBJECT (dr) 2041169689Skan || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1)) 2042169689Skan { 2043169689Skan tree access_fn; 2044169689Skan tree new_step; 2045169689Skan 2046169689Skan /* Update access function. */ 2047169689Skan access_fn = DR_ACCESS_FN (dr, 0); 2048169689Skan if (automatically_generated_chrec_p (access_fn)) 2049169689Skan { 2050169689Skan free_data_ref (dr); 2051169689Skan return NULL; 2052169689Skan } 2053169689Skan 2054169689Skan new_step = size_binop (TRUNC_DIV_EXPR, 2055169689Skan fold_convert (ssizetype, step), type_size); 2056169689Skan 2057169689Skan init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt); 2058169689Skan new_step = chrec_convert (chrec_type (access_fn), new_step, stmt); 2059169689Skan if (automatically_generated_chrec_p (init_cond) 2060169689Skan || automatically_generated_chrec_p (new_step)) 2061169689Skan { 2062169689Skan free_data_ref (dr); 2063169689Skan return NULL; 2064169689Skan } 2065169689Skan access_fn = chrec_replace_initial_condition (access_fn, init_cond); 2066169689Skan access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step); 2067169689Skan 2068169689Skan VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn); 2069169689Skan } 2070169689Skan 2071169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2072169689Skan { 2073169689Skan struct ptr_info_def *pi = DR_PTR_INFO (dr); 2074169689Skan 2075169689Skan fprintf (dump_file, "\nCreated dr for "); 2076169689Skan print_generic_expr (dump_file, memref, TDF_SLIM); 2077169689Skan fprintf (dump_file, "\n\tbase_address: "); 2078169689Skan print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM); 2079169689Skan fprintf (dump_file, "\n\toffset from base address: "); 2080169689Skan print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM); 2081169689Skan fprintf (dump_file, "\n\tconstant offset from base address: "); 2082169689Skan print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM); 2083169689Skan fprintf (dump_file, "\n\tbase_object: "); 2084169689Skan print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM); 2085169689Skan fprintf (dump_file, "\n\tstep: "); 2086169689Skan print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM); 2087169689Skan fprintf (dump_file, "B\n\tmisalignment from base: "); 2088169689Skan print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM); 2089169689Skan if (DR_OFFSET_MISALIGNMENT (dr)) 2090169689Skan fprintf (dump_file, "B"); 2091169689Skan if (DR_ALIGNED_TO (dr)) 2092169689Skan { 2093169689Skan fprintf (dump_file, "\n\taligned to: "); 2094169689Skan print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM); 2095169689Skan } 2096169689Skan fprintf (dump_file, "\n\tmemtag: "); 2097169689Skan print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM); 2098169689Skan fprintf (dump_file, "\n"); 2099169689Skan if (pi && pi->name_mem_tag) 2100169689Skan { 2101169689Skan fprintf (dump_file, "\n\tnametag: "); 2102169689Skan print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM); 2103169689Skan fprintf (dump_file, "\n"); 2104169689Skan } 2105169689Skan } 2106169689Skan return dr; 2107169689Skan} 2108169689Skan 2109169689Skan 2110169689Skan/* Returns true when all the functions of a tree_vec CHREC are the 2111169689Skan same. */ 2112169689Skan 2113169689Skanstatic bool 2114169689Skanall_chrecs_equal_p (tree chrec) 2115169689Skan{ 2116169689Skan int j; 2117169689Skan 2118169689Skan for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++) 2119169689Skan if (!eq_evolutions_p (TREE_VEC_ELT (chrec, j), 2120169689Skan TREE_VEC_ELT (chrec, j + 1))) 2121169689Skan return false; 2122169689Skan 2123169689Skan return true; 2124169689Skan} 2125169689Skan 2126169689Skan/* Determine for each subscript in the data dependence relation DDR 2127169689Skan the distance. */ 2128169689Skan 2129169689Skanstatic void 2130169689Skancompute_subscript_distance (struct data_dependence_relation *ddr) 2131169689Skan{ 2132169689Skan if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) 2133169689Skan { 2134169689Skan unsigned int i; 2135169689Skan 2136169689Skan for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 2137169689Skan { 2138169689Skan tree conflicts_a, conflicts_b, difference; 2139169689Skan struct subscript *subscript; 2140169689Skan 2141169689Skan subscript = DDR_SUBSCRIPT (ddr, i); 2142169689Skan conflicts_a = SUB_CONFLICTS_IN_A (subscript); 2143169689Skan conflicts_b = SUB_CONFLICTS_IN_B (subscript); 2144169689Skan 2145169689Skan if (TREE_CODE (conflicts_a) == TREE_VEC) 2146169689Skan { 2147169689Skan if (!all_chrecs_equal_p (conflicts_a)) 2148169689Skan { 2149169689Skan SUB_DISTANCE (subscript) = chrec_dont_know; 2150169689Skan return; 2151169689Skan } 2152169689Skan else 2153169689Skan conflicts_a = TREE_VEC_ELT (conflicts_a, 0); 2154169689Skan } 2155169689Skan 2156169689Skan if (TREE_CODE (conflicts_b) == TREE_VEC) 2157169689Skan { 2158169689Skan if (!all_chrecs_equal_p (conflicts_b)) 2159169689Skan { 2160169689Skan SUB_DISTANCE (subscript) = chrec_dont_know; 2161169689Skan return; 2162169689Skan } 2163169689Skan else 2164169689Skan conflicts_b = TREE_VEC_ELT (conflicts_b, 0); 2165169689Skan } 2166169689Skan 2167169689Skan conflicts_b = chrec_convert (integer_type_node, conflicts_b, 2168169689Skan NULL_TREE); 2169169689Skan conflicts_a = chrec_convert (integer_type_node, conflicts_a, 2170169689Skan NULL_TREE); 2171169689Skan difference = chrec_fold_minus 2172169689Skan (integer_type_node, conflicts_b, conflicts_a); 2173169689Skan 2174169689Skan if (evolution_function_is_constant_p (difference)) 2175169689Skan SUB_DISTANCE (subscript) = difference; 2176169689Skan 2177169689Skan else 2178169689Skan SUB_DISTANCE (subscript) = chrec_dont_know; 2179169689Skan } 2180169689Skan } 2181169689Skan} 2182169689Skan 2183169689Skan/* Initialize a data dependence relation between data accesses A and 2184169689Skan B. NB_LOOPS is the number of loops surrounding the references: the 2185169689Skan size of the classic distance/direction vectors. */ 2186169689Skan 2187169689Skanstatic struct data_dependence_relation * 2188169689Skaninitialize_data_dependence_relation (struct data_reference *a, 2189169689Skan struct data_reference *b, 2190169689Skan VEC (loop_p, heap) *loop_nest) 2191169689Skan{ 2192169689Skan struct data_dependence_relation *res; 2193169689Skan bool differ_p, known_dependence; 2194169689Skan unsigned int i; 2195169689Skan 2196169689Skan res = XNEW (struct data_dependence_relation); 2197169689Skan DDR_A (res) = a; 2198169689Skan DDR_B (res) = b; 2199169689Skan DDR_LOOP_NEST (res) = NULL; 2200169689Skan 2201169689Skan if (a == NULL || b == NULL) 2202169689Skan { 2203169689Skan DDR_ARE_DEPENDENT (res) = chrec_dont_know; 2204169689Skan return res; 2205169689Skan } 2206169689Skan 2207169689Skan /* When A and B are arrays and their dimensions differ, we directly 2208169689Skan initialize the relation to "there is no dependence": chrec_known. */ 2209169689Skan if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b) 2210169689Skan && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)) 2211169689Skan { 2212169689Skan DDR_ARE_DEPENDENT (res) = chrec_known; 2213169689Skan return res; 2214169689Skan } 2215169689Skan 2216169689Skan if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b)) 2217169689Skan known_dependence = base_addr_differ_p (a, b, &differ_p); 2218169689Skan else 2219169689Skan known_dependence = base_object_differ_p (a, b, &differ_p); 2220169689Skan 2221169689Skan if (!known_dependence) 2222169689Skan { 2223169689Skan /* Can't determine whether the data-refs access the same memory 2224169689Skan region. */ 2225169689Skan DDR_ARE_DEPENDENT (res) = chrec_dont_know; 2226169689Skan return res; 2227169689Skan } 2228169689Skan 2229169689Skan if (differ_p) 2230169689Skan { 2231169689Skan DDR_ARE_DEPENDENT (res) = chrec_known; 2232169689Skan return res; 2233169689Skan } 2234169689Skan 2235169689Skan DDR_AFFINE_P (res) = true; 2236169689Skan DDR_ARE_DEPENDENT (res) = NULL_TREE; 2237169689Skan DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a)); 2238169689Skan DDR_LOOP_NEST (res) = loop_nest; 2239169689Skan DDR_DIR_VECTS (res) = NULL; 2240169689Skan DDR_DIST_VECTS (res) = NULL; 2241169689Skan 2242169689Skan for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) 2243169689Skan { 2244169689Skan struct subscript *subscript; 2245169689Skan 2246169689Skan subscript = XNEW (struct subscript); 2247169689Skan SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know; 2248169689Skan SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know; 2249169689Skan SUB_LAST_CONFLICT (subscript) = chrec_dont_know; 2250169689Skan SUB_DISTANCE (subscript) = chrec_dont_know; 2251169689Skan VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript); 2252169689Skan } 2253169689Skan 2254169689Skan return res; 2255169689Skan} 2256169689Skan 2257169689Skan/* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap 2258169689Skan description. */ 2259169689Skan 2260169689Skanstatic inline void 2261169689Skanfinalize_ddr_dependent (struct data_dependence_relation *ddr, 2262169689Skan tree chrec) 2263169689Skan{ 2264169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2265169689Skan { 2266169689Skan fprintf (dump_file, "(dependence classified: "); 2267169689Skan print_generic_expr (dump_file, chrec, 0); 2268169689Skan fprintf (dump_file, ")\n"); 2269169689Skan } 2270169689Skan 2271169689Skan DDR_ARE_DEPENDENT (ddr) = chrec; 2272169689Skan VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr)); 2273169689Skan} 2274169689Skan 2275169689Skan/* The dependence relation DDR cannot be represented by a distance 2276169689Skan vector. */ 2277169689Skan 2278169689Skanstatic inline void 2279169689Skannon_affine_dependence_relation (struct data_dependence_relation *ddr) 2280169689Skan{ 2281169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2282169689Skan fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n"); 2283169689Skan 2284169689Skan DDR_AFFINE_P (ddr) = false; 2285169689Skan} 2286169689Skan 2287169689Skan 2288169689Skan 2289169689Skan/* This section contains the classic Banerjee tests. */ 2290169689Skan 2291169689Skan/* Returns true iff CHREC_A and CHREC_B are not dependent on any index 2292169689Skan variables, i.e., if the ZIV (Zero Index Variable) test is true. */ 2293169689Skan 2294169689Skanstatic inline bool 2295169689Skanziv_subscript_p (tree chrec_a, 2296169689Skan tree chrec_b) 2297169689Skan{ 2298169689Skan return (evolution_function_is_constant_p (chrec_a) 2299169689Skan && evolution_function_is_constant_p (chrec_b)); 2300169689Skan} 2301169689Skan 2302169689Skan/* Returns true iff CHREC_A and CHREC_B are dependent on an index 2303169689Skan variable, i.e., if the SIV (Single Index Variable) test is true. */ 2304169689Skan 2305169689Skanstatic bool 2306169689Skansiv_subscript_p (tree chrec_a, 2307169689Skan tree chrec_b) 2308169689Skan{ 2309169689Skan if ((evolution_function_is_constant_p (chrec_a) 2310169689Skan && evolution_function_is_univariate_p (chrec_b)) 2311169689Skan || (evolution_function_is_constant_p (chrec_b) 2312169689Skan && evolution_function_is_univariate_p (chrec_a))) 2313169689Skan return true; 2314169689Skan 2315169689Skan if (evolution_function_is_univariate_p (chrec_a) 2316169689Skan && evolution_function_is_univariate_p (chrec_b)) 2317169689Skan { 2318169689Skan switch (TREE_CODE (chrec_a)) 2319169689Skan { 2320169689Skan case POLYNOMIAL_CHREC: 2321169689Skan switch (TREE_CODE (chrec_b)) 2322169689Skan { 2323169689Skan case POLYNOMIAL_CHREC: 2324169689Skan if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b)) 2325169689Skan return false; 2326169689Skan 2327169689Skan default: 2328169689Skan return true; 2329169689Skan } 2330169689Skan 2331169689Skan default: 2332169689Skan return true; 2333169689Skan } 2334169689Skan } 2335169689Skan 2336169689Skan return false; 2337169689Skan} 2338169689Skan 2339169689Skan/* Analyze a ZIV (Zero Index Variable) subscript. *OVERLAPS_A and 2340169689Skan *OVERLAPS_B are initialized to the functions that describe the 2341169689Skan relation between the elements accessed twice by CHREC_A and 2342169689Skan CHREC_B. For k >= 0, the following property is verified: 2343169689Skan 2344169689Skan CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 2345169689Skan 2346169689Skanstatic void 2347169689Skananalyze_ziv_subscript (tree chrec_a, 2348169689Skan tree chrec_b, 2349169689Skan tree *overlaps_a, 2350169689Skan tree *overlaps_b, 2351169689Skan tree *last_conflicts) 2352169689Skan{ 2353169689Skan tree difference; 2354169689Skan dependence_stats.num_ziv++; 2355169689Skan 2356169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2357169689Skan fprintf (dump_file, "(analyze_ziv_subscript \n"); 2358169689Skan 2359169689Skan chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE); 2360169689Skan chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE); 2361169689Skan difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); 2362169689Skan 2363169689Skan switch (TREE_CODE (difference)) 2364169689Skan { 2365169689Skan case INTEGER_CST: 2366169689Skan if (integer_zerop (difference)) 2367169689Skan { 2368169689Skan /* The difference is equal to zero: the accessed index 2369169689Skan overlaps for each iteration in the loop. */ 2370169689Skan *overlaps_a = integer_zero_node; 2371169689Skan *overlaps_b = integer_zero_node; 2372169689Skan *last_conflicts = chrec_dont_know; 2373169689Skan dependence_stats.num_ziv_dependent++; 2374169689Skan } 2375169689Skan else 2376169689Skan { 2377169689Skan /* The accesses do not overlap. */ 2378169689Skan *overlaps_a = chrec_known; 2379169689Skan *overlaps_b = chrec_known; 2380169689Skan *last_conflicts = integer_zero_node; 2381169689Skan dependence_stats.num_ziv_independent++; 2382169689Skan } 2383169689Skan break; 2384169689Skan 2385169689Skan default: 2386169689Skan /* We're not sure whether the indexes overlap. For the moment, 2387169689Skan conservatively answer "don't know". */ 2388169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2389169689Skan fprintf (dump_file, "ziv test failed: difference is non-integer.\n"); 2390169689Skan 2391169689Skan *overlaps_a = chrec_dont_know; 2392169689Skan *overlaps_b = chrec_dont_know; 2393169689Skan *last_conflicts = chrec_dont_know; 2394169689Skan dependence_stats.num_ziv_unimplemented++; 2395169689Skan break; 2396169689Skan } 2397169689Skan 2398169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2399169689Skan fprintf (dump_file, ")\n"); 2400169689Skan} 2401169689Skan 2402169689Skan/* Get the real or estimated number of iterations for LOOPNUM, whichever is 2403169689Skan available. Return the number of iterations as a tree, or NULL_TREE if 2404169689Skan we don't know. */ 2405169689Skan 2406169689Skanstatic tree 2407169689Skanget_number_of_iters_for_loop (int loopnum) 2408169689Skan{ 2409169689Skan tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]); 2410169689Skan 2411169689Skan if (TREE_CODE (numiter) != INTEGER_CST) 2412169689Skan numiter = current_loops->parray[loopnum]->estimated_nb_iterations; 2413169689Skan if (chrec_contains_undetermined (numiter)) 2414169689Skan return NULL_TREE; 2415169689Skan return numiter; 2416169689Skan} 2417169689Skan 2418169689Skan/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a 2419169689Skan constant, and CHREC_B is an affine function. *OVERLAPS_A and 2420169689Skan *OVERLAPS_B are initialized to the functions that describe the 2421169689Skan relation between the elements accessed twice by CHREC_A and 2422169689Skan CHREC_B. For k >= 0, the following property is verified: 2423169689Skan 2424169689Skan CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 2425169689Skan 2426169689Skanstatic void 2427169689Skananalyze_siv_subscript_cst_affine (tree chrec_a, 2428169689Skan tree chrec_b, 2429169689Skan tree *overlaps_a, 2430169689Skan tree *overlaps_b, 2431169689Skan tree *last_conflicts) 2432169689Skan{ 2433169689Skan bool value0, value1, value2; 2434169689Skan tree difference; 2435169689Skan 2436169689Skan chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE); 2437169689Skan chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE); 2438169689Skan difference = chrec_fold_minus 2439169689Skan (integer_type_node, initial_condition (chrec_b), chrec_a); 2440169689Skan 2441169689Skan if (!chrec_is_positive (initial_condition (difference), &value0)) 2442169689Skan { 2443169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2444169689Skan fprintf (dump_file, "siv test failed: chrec is not positive.\n"); 2445169689Skan 2446169689Skan dependence_stats.num_siv_unimplemented++; 2447169689Skan *overlaps_a = chrec_dont_know; 2448169689Skan *overlaps_b = chrec_dont_know; 2449169689Skan *last_conflicts = chrec_dont_know; 2450169689Skan return; 2451169689Skan } 2452169689Skan else 2453169689Skan { 2454169689Skan if (value0 == false) 2455169689Skan { 2456169689Skan if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1)) 2457169689Skan { 2458169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2459169689Skan fprintf (dump_file, "siv test failed: chrec not positive.\n"); 2460169689Skan 2461169689Skan *overlaps_a = chrec_dont_know; 2462169689Skan *overlaps_b = chrec_dont_know; 2463169689Skan *last_conflicts = chrec_dont_know; 2464169689Skan dependence_stats.num_siv_unimplemented++; 2465169689Skan return; 2466169689Skan } 2467169689Skan else 2468169689Skan { 2469169689Skan if (value1 == true) 2470169689Skan { 2471169689Skan /* Example: 2472169689Skan chrec_a = 12 2473169689Skan chrec_b = {10, +, 1} 2474169689Skan */ 2475169689Skan 2476169689Skan if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) 2477169689Skan { 2478169689Skan tree numiter; 2479169689Skan int loopnum = CHREC_VARIABLE (chrec_b); 2480169689Skan 2481169689Skan *overlaps_a = integer_zero_node; 2482169689Skan *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node, 2483169689Skan fold_build1 (ABS_EXPR, 2484169689Skan integer_type_node, 2485169689Skan difference), 2486169689Skan CHREC_RIGHT (chrec_b)); 2487169689Skan *last_conflicts = integer_one_node; 2488169689Skan 2489169689Skan 2490169689Skan /* Perform weak-zero siv test to see if overlap is 2491169689Skan outside the loop bounds. */ 2492169689Skan numiter = get_number_of_iters_for_loop (loopnum); 2493169689Skan 2494169689Skan if (numiter != NULL_TREE 2495169689Skan && TREE_CODE (*overlaps_b) == INTEGER_CST 2496169689Skan && tree_int_cst_lt (numiter, *overlaps_b)) 2497169689Skan { 2498169689Skan *overlaps_a = chrec_known; 2499169689Skan *overlaps_b = chrec_known; 2500169689Skan *last_conflicts = integer_zero_node; 2501169689Skan dependence_stats.num_siv_independent++; 2502169689Skan return; 2503169689Skan } 2504169689Skan dependence_stats.num_siv_dependent++; 2505169689Skan return; 2506169689Skan } 2507169689Skan 2508169689Skan /* When the step does not divide the difference, there are 2509169689Skan no overlaps. */ 2510169689Skan else 2511169689Skan { 2512169689Skan *overlaps_a = chrec_known; 2513169689Skan *overlaps_b = chrec_known; 2514169689Skan *last_conflicts = integer_zero_node; 2515169689Skan dependence_stats.num_siv_independent++; 2516169689Skan return; 2517169689Skan } 2518169689Skan } 2519169689Skan 2520169689Skan else 2521169689Skan { 2522169689Skan /* Example: 2523169689Skan chrec_a = 12 2524169689Skan chrec_b = {10, +, -1} 2525169689Skan 2526169689Skan In this case, chrec_a will not overlap with chrec_b. */ 2527169689Skan *overlaps_a = chrec_known; 2528169689Skan *overlaps_b = chrec_known; 2529169689Skan *last_conflicts = integer_zero_node; 2530169689Skan dependence_stats.num_siv_independent++; 2531169689Skan return; 2532169689Skan } 2533169689Skan } 2534169689Skan } 2535169689Skan else 2536169689Skan { 2537169689Skan if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2)) 2538169689Skan { 2539169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2540169689Skan fprintf (dump_file, "siv test failed: chrec not positive.\n"); 2541169689Skan 2542169689Skan *overlaps_a = chrec_dont_know; 2543169689Skan *overlaps_b = chrec_dont_know; 2544169689Skan *last_conflicts = chrec_dont_know; 2545169689Skan dependence_stats.num_siv_unimplemented++; 2546169689Skan return; 2547169689Skan } 2548169689Skan else 2549169689Skan { 2550169689Skan if (value2 == false) 2551169689Skan { 2552169689Skan /* Example: 2553169689Skan chrec_a = 3 2554169689Skan chrec_b = {10, +, -1} 2555169689Skan */ 2556169689Skan if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) 2557169689Skan { 2558169689Skan tree numiter; 2559169689Skan int loopnum = CHREC_VARIABLE (chrec_b); 2560169689Skan 2561169689Skan *overlaps_a = integer_zero_node; 2562169689Skan *overlaps_b = fold_build2 (EXACT_DIV_EXPR, 2563169689Skan integer_type_node, difference, 2564169689Skan CHREC_RIGHT (chrec_b)); 2565169689Skan *last_conflicts = integer_one_node; 2566169689Skan 2567169689Skan /* Perform weak-zero siv test to see if overlap is 2568169689Skan outside the loop bounds. */ 2569169689Skan numiter = get_number_of_iters_for_loop (loopnum); 2570169689Skan 2571169689Skan if (numiter != NULL_TREE 2572169689Skan && TREE_CODE (*overlaps_b) == INTEGER_CST 2573169689Skan && tree_int_cst_lt (numiter, *overlaps_b)) 2574169689Skan { 2575169689Skan *overlaps_a = chrec_known; 2576169689Skan *overlaps_b = chrec_known; 2577169689Skan *last_conflicts = integer_zero_node; 2578169689Skan dependence_stats.num_siv_independent++; 2579169689Skan return; 2580169689Skan } 2581169689Skan dependence_stats.num_siv_dependent++; 2582169689Skan return; 2583169689Skan } 2584169689Skan 2585169689Skan /* When the step does not divide the difference, there 2586169689Skan are no overlaps. */ 2587169689Skan else 2588169689Skan { 2589169689Skan *overlaps_a = chrec_known; 2590169689Skan *overlaps_b = chrec_known; 2591169689Skan *last_conflicts = integer_zero_node; 2592169689Skan dependence_stats.num_siv_independent++; 2593169689Skan return; 2594169689Skan } 2595169689Skan } 2596169689Skan else 2597169689Skan { 2598169689Skan /* Example: 2599169689Skan chrec_a = 3 2600169689Skan chrec_b = {4, +, 1} 2601169689Skan 2602169689Skan In this case, chrec_a will not overlap with chrec_b. */ 2603169689Skan *overlaps_a = chrec_known; 2604169689Skan *overlaps_b = chrec_known; 2605169689Skan *last_conflicts = integer_zero_node; 2606169689Skan dependence_stats.num_siv_independent++; 2607169689Skan return; 2608169689Skan } 2609169689Skan } 2610169689Skan } 2611169689Skan } 2612169689Skan} 2613169689Skan 2614169689Skan/* Helper recursive function for initializing the matrix A. Returns 2615169689Skan the initial value of CHREC. */ 2616169689Skan 2617169689Skanstatic int 2618169689Skaninitialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) 2619169689Skan{ 2620169689Skan gcc_assert (chrec); 2621169689Skan 2622169689Skan if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 2623169689Skan return int_cst_value (chrec); 2624169689Skan 2625169689Skan A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); 2626169689Skan return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); 2627169689Skan} 2628169689Skan 2629169689Skan#define FLOOR_DIV(x,y) ((x) / (y)) 2630169689Skan 2631169689Skan/* Solves the special case of the Diophantine equation: 2632169689Skan | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B) 2633169689Skan 2634169689Skan Computes the descriptions OVERLAPS_A and OVERLAPS_B. NITER is the 2635169689Skan number of iterations that loops X and Y run. The overlaps will be 2636169689Skan constructed as evolutions in dimension DIM. */ 2637169689Skan 2638169689Skanstatic void 2639169689Skancompute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b, 2640169689Skan tree *overlaps_a, tree *overlaps_b, 2641169689Skan tree *last_conflicts, int dim) 2642169689Skan{ 2643169689Skan if (((step_a > 0 && step_b > 0) 2644169689Skan || (step_a < 0 && step_b < 0))) 2645169689Skan { 2646169689Skan int step_overlaps_a, step_overlaps_b; 2647169689Skan int gcd_steps_a_b, last_conflict, tau2; 2648169689Skan 2649169689Skan gcd_steps_a_b = gcd (step_a, step_b); 2650169689Skan step_overlaps_a = step_b / gcd_steps_a_b; 2651169689Skan step_overlaps_b = step_a / gcd_steps_a_b; 2652169689Skan 2653169689Skan tau2 = FLOOR_DIV (niter, step_overlaps_a); 2654169689Skan tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b)); 2655169689Skan last_conflict = tau2; 2656169689Skan 2657169689Skan *overlaps_a = build_polynomial_chrec 2658169689Skan (dim, integer_zero_node, 2659169689Skan build_int_cst (NULL_TREE, step_overlaps_a)); 2660169689Skan *overlaps_b = build_polynomial_chrec 2661169689Skan (dim, integer_zero_node, 2662169689Skan build_int_cst (NULL_TREE, step_overlaps_b)); 2663169689Skan *last_conflicts = build_int_cst (NULL_TREE, last_conflict); 2664169689Skan } 2665169689Skan 2666169689Skan else 2667169689Skan { 2668169689Skan *overlaps_a = integer_zero_node; 2669169689Skan *overlaps_b = integer_zero_node; 2670169689Skan *last_conflicts = integer_zero_node; 2671169689Skan } 2672169689Skan} 2673169689Skan 2674169689Skan 2675169689Skan/* Solves the special case of a Diophantine equation where CHREC_A is 2676169689Skan an affine bivariate function, and CHREC_B is an affine univariate 2677169689Skan function. For example, 2678169689Skan 2679169689Skan | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z 2680169689Skan 2681169689Skan has the following overlapping functions: 2682169689Skan 2683169689Skan | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v 2684169689Skan | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v 2685169689Skan | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v 2686169689Skan 2687169689Skan FORNOW: This is a specialized implementation for a case occurring in 2688169689Skan a common benchmark. Implement the general algorithm. */ 2689169689Skan 2690169689Skanstatic void 2691169689Skancompute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, 2692169689Skan tree *overlaps_a, tree *overlaps_b, 2693169689Skan tree *last_conflicts) 2694169689Skan{ 2695169689Skan bool xz_p, yz_p, xyz_p; 2696169689Skan int step_x, step_y, step_z; 2697169689Skan int niter_x, niter_y, niter_z, niter; 2698169689Skan tree numiter_x, numiter_y, numiter_z; 2699169689Skan tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz; 2700169689Skan tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz; 2701169689Skan tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz; 2702169689Skan 2703169689Skan step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a))); 2704169689Skan step_y = int_cst_value (CHREC_RIGHT (chrec_a)); 2705169689Skan step_z = int_cst_value (CHREC_RIGHT (chrec_b)); 2706169689Skan 2707169689Skan numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a))); 2708169689Skan numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 2709169689Skan numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); 2710169689Skan 2711169689Skan if (numiter_x == NULL_TREE || numiter_y == NULL_TREE 2712169689Skan || numiter_z == NULL_TREE) 2713169689Skan { 2714169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2715169689Skan fprintf (dump_file, "overlap steps test failed: no iteration counts.\n"); 2716169689Skan 2717169689Skan *overlaps_a = chrec_dont_know; 2718169689Skan *overlaps_b = chrec_dont_know; 2719169689Skan *last_conflicts = chrec_dont_know; 2720169689Skan return; 2721169689Skan } 2722169689Skan 2723169689Skan niter_x = int_cst_value (numiter_x); 2724169689Skan niter_y = int_cst_value (numiter_y); 2725169689Skan niter_z = int_cst_value (numiter_z); 2726169689Skan 2727169689Skan niter = MIN (niter_x, niter_z); 2728169689Skan compute_overlap_steps_for_affine_univar (niter, step_x, step_z, 2729169689Skan &overlaps_a_xz, 2730169689Skan &overlaps_b_xz, 2731169689Skan &last_conflicts_xz, 1); 2732169689Skan niter = MIN (niter_y, niter_z); 2733169689Skan compute_overlap_steps_for_affine_univar (niter, step_y, step_z, 2734169689Skan &overlaps_a_yz, 2735169689Skan &overlaps_b_yz, 2736169689Skan &last_conflicts_yz, 2); 2737169689Skan niter = MIN (niter_x, niter_z); 2738169689Skan niter = MIN (niter_y, niter); 2739169689Skan compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z, 2740169689Skan &overlaps_a_xyz, 2741169689Skan &overlaps_b_xyz, 2742169689Skan &last_conflicts_xyz, 3); 2743169689Skan 2744169689Skan xz_p = !integer_zerop (last_conflicts_xz); 2745169689Skan yz_p = !integer_zerop (last_conflicts_yz); 2746169689Skan xyz_p = !integer_zerop (last_conflicts_xyz); 2747169689Skan 2748169689Skan if (xz_p || yz_p || xyz_p) 2749169689Skan { 2750169689Skan *overlaps_a = make_tree_vec (2); 2751169689Skan TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node; 2752169689Skan TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node; 2753169689Skan *overlaps_b = integer_zero_node; 2754169689Skan if (xz_p) 2755169689Skan { 2756169689Skan tree t0 = chrec_convert (integer_type_node, 2757169689Skan TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE); 2758169689Skan tree t1 = chrec_convert (integer_type_node, overlaps_a_xz, 2759169689Skan NULL_TREE); 2760169689Skan tree t2 = chrec_convert (integer_type_node, *overlaps_b, 2761169689Skan NULL_TREE); 2762169689Skan tree t3 = chrec_convert (integer_type_node, overlaps_b_xz, 2763169689Skan NULL_TREE); 2764169689Skan 2765169689Skan TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node, 2766169689Skan t0, t1); 2767169689Skan *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3); 2768169689Skan *last_conflicts = last_conflicts_xz; 2769169689Skan } 2770169689Skan if (yz_p) 2771169689Skan { 2772169689Skan tree t0 = chrec_convert (integer_type_node, 2773169689Skan TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE); 2774169689Skan tree t1 = chrec_convert (integer_type_node, overlaps_a_yz, NULL_TREE); 2775169689Skan tree t2 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE); 2776169689Skan tree t3 = chrec_convert (integer_type_node, overlaps_b_yz, NULL_TREE); 2777169689Skan 2778169689Skan TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node, 2779169689Skan t0, t1); 2780169689Skan *overlaps_b = chrec_fold_plus (integer_type_node, t2, t3); 2781169689Skan *last_conflicts = last_conflicts_yz; 2782169689Skan } 2783169689Skan if (xyz_p) 2784169689Skan { 2785169689Skan tree t0 = chrec_convert (integer_type_node, 2786169689Skan TREE_VEC_ELT (*overlaps_a, 0), NULL_TREE); 2787169689Skan tree t1 = chrec_convert (integer_type_node, overlaps_a_xyz, 2788169689Skan NULL_TREE); 2789169689Skan tree t2 = chrec_convert (integer_type_node, 2790169689Skan TREE_VEC_ELT (*overlaps_a, 1), NULL_TREE); 2791169689Skan tree t3 = chrec_convert (integer_type_node, overlaps_a_xyz, 2792169689Skan NULL_TREE); 2793169689Skan tree t4 = chrec_convert (integer_type_node, *overlaps_b, NULL_TREE); 2794169689Skan tree t5 = chrec_convert (integer_type_node, overlaps_b_xyz, 2795169689Skan NULL_TREE); 2796169689Skan 2797169689Skan TREE_VEC_ELT (*overlaps_a, 0) = chrec_fold_plus (integer_type_node, 2798169689Skan t0, t1); 2799169689Skan TREE_VEC_ELT (*overlaps_a, 1) = chrec_fold_plus (integer_type_node, 2800169689Skan t2, t3); 2801169689Skan *overlaps_b = chrec_fold_plus (integer_type_node, t4, t5); 2802169689Skan *last_conflicts = last_conflicts_xyz; 2803169689Skan } 2804169689Skan } 2805169689Skan else 2806169689Skan { 2807169689Skan *overlaps_a = integer_zero_node; 2808169689Skan *overlaps_b = integer_zero_node; 2809169689Skan *last_conflicts = integer_zero_node; 2810169689Skan } 2811169689Skan} 2812169689Skan 2813169689Skan/* Determines the overlapping elements due to accesses CHREC_A and 2814169689Skan CHREC_B, that are affine functions. This function cannot handle 2815169689Skan symbolic evolution functions, ie. when initial conditions are 2816169689Skan parameters, because it uses lambda matrices of integers. */ 2817169689Skan 2818169689Skanstatic void 2819169689Skananalyze_subscript_affine_affine (tree chrec_a, 2820169689Skan tree chrec_b, 2821169689Skan tree *overlaps_a, 2822169689Skan tree *overlaps_b, 2823169689Skan tree *last_conflicts) 2824169689Skan{ 2825169689Skan unsigned nb_vars_a, nb_vars_b, dim; 2826169689Skan int init_a, init_b, gamma, gcd_alpha_beta; 2827169689Skan int tau1, tau2; 2828169689Skan lambda_matrix A, U, S; 2829169689Skan 2830169689Skan if (eq_evolutions_p (chrec_a, chrec_b)) 2831169689Skan { 2832169689Skan /* The accessed index overlaps for each iteration in the 2833169689Skan loop. */ 2834169689Skan *overlaps_a = integer_zero_node; 2835169689Skan *overlaps_b = integer_zero_node; 2836169689Skan *last_conflicts = chrec_dont_know; 2837169689Skan return; 2838169689Skan } 2839169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2840169689Skan fprintf (dump_file, "(analyze_subscript_affine_affine \n"); 2841169689Skan 2842169689Skan /* For determining the initial intersection, we have to solve a 2843169689Skan Diophantine equation. This is the most time consuming part. 2844169689Skan 2845169689Skan For answering to the question: "Is there a dependence?" we have 2846169689Skan to prove that there exists a solution to the Diophantine 2847169689Skan equation, and that the solution is in the iteration domain, 2848169689Skan i.e. the solution is positive or zero, and that the solution 2849169689Skan happens before the upper bound loop.nb_iterations. Otherwise 2850169689Skan there is no dependence. This function outputs a description of 2851169689Skan the iterations that hold the intersections. */ 2852169689Skan 2853169689Skan nb_vars_a = nb_vars_in_chrec (chrec_a); 2854169689Skan nb_vars_b = nb_vars_in_chrec (chrec_b); 2855169689Skan 2856169689Skan dim = nb_vars_a + nb_vars_b; 2857169689Skan U = lambda_matrix_new (dim, dim); 2858169689Skan A = lambda_matrix_new (dim, 1); 2859169689Skan S = lambda_matrix_new (dim, 1); 2860169689Skan 2861169689Skan init_a = initialize_matrix_A (A, chrec_a, 0, 1); 2862169689Skan init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1); 2863169689Skan gamma = init_b - init_a; 2864169689Skan 2865169689Skan /* Don't do all the hard work of solving the Diophantine equation 2866169689Skan when we already know the solution: for example, 2867169689Skan | {3, +, 1}_1 2868169689Skan | {3, +, 4}_2 2869169689Skan | gamma = 3 - 3 = 0. 2870169689Skan Then the first overlap occurs during the first iterations: 2871169689Skan | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x) 2872169689Skan */ 2873169689Skan if (gamma == 0) 2874169689Skan { 2875169689Skan if (nb_vars_a == 1 && nb_vars_b == 1) 2876169689Skan { 2877169689Skan int step_a, step_b; 2878169689Skan int niter, niter_a, niter_b; 2879169689Skan tree numiter_a, numiter_b; 2880169689Skan 2881169689Skan numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 2882169689Skan numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); 2883169689Skan if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) 2884169689Skan { 2885169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2886169689Skan fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); 2887169689Skan *overlaps_a = chrec_dont_know; 2888169689Skan *overlaps_b = chrec_dont_know; 2889169689Skan *last_conflicts = chrec_dont_know; 2890169689Skan goto end_analyze_subs_aa; 2891169689Skan } 2892169689Skan 2893169689Skan niter_a = int_cst_value (numiter_a); 2894169689Skan niter_b = int_cst_value (numiter_b); 2895169689Skan niter = MIN (niter_a, niter_b); 2896169689Skan 2897169689Skan step_a = int_cst_value (CHREC_RIGHT (chrec_a)); 2898169689Skan step_b = int_cst_value (CHREC_RIGHT (chrec_b)); 2899169689Skan 2900169689Skan compute_overlap_steps_for_affine_univar (niter, step_a, step_b, 2901169689Skan overlaps_a, overlaps_b, 2902169689Skan last_conflicts, 1); 2903169689Skan } 2904169689Skan 2905169689Skan else if (nb_vars_a == 2 && nb_vars_b == 1) 2906169689Skan compute_overlap_steps_for_affine_1_2 2907169689Skan (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); 2908169689Skan 2909169689Skan else if (nb_vars_a == 1 && nb_vars_b == 2) 2910169689Skan compute_overlap_steps_for_affine_1_2 2911169689Skan (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts); 2912169689Skan 2913169689Skan else 2914169689Skan { 2915169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2916169689Skan fprintf (dump_file, "affine-affine test failed: too many variables.\n"); 2917169689Skan *overlaps_a = chrec_dont_know; 2918169689Skan *overlaps_b = chrec_dont_know; 2919169689Skan *last_conflicts = chrec_dont_know; 2920169689Skan } 2921169689Skan goto end_analyze_subs_aa; 2922169689Skan } 2923169689Skan 2924169689Skan /* U.A = S */ 2925169689Skan lambda_matrix_right_hermite (A, dim, 1, S, U); 2926169689Skan 2927169689Skan if (S[0][0] < 0) 2928169689Skan { 2929169689Skan S[0][0] *= -1; 2930169689Skan lambda_matrix_row_negate (U, dim, 0); 2931169689Skan } 2932169689Skan gcd_alpha_beta = S[0][0]; 2933169689Skan 2934169689Skan /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5, 2935169689Skan but that is a quite strange case. Instead of ICEing, answer 2936169689Skan don't know. */ 2937169689Skan if (gcd_alpha_beta == 0) 2938169689Skan { 2939169689Skan *overlaps_a = chrec_dont_know; 2940169689Skan *overlaps_b = chrec_dont_know; 2941169689Skan *last_conflicts = chrec_dont_know; 2942169689Skan goto end_analyze_subs_aa; 2943169689Skan } 2944169689Skan 2945169689Skan /* The classic "gcd-test". */ 2946169689Skan if (!int_divides_p (gcd_alpha_beta, gamma)) 2947169689Skan { 2948169689Skan /* The "gcd-test" has determined that there is no integer 2949169689Skan solution, i.e. there is no dependence. */ 2950169689Skan *overlaps_a = chrec_known; 2951169689Skan *overlaps_b = chrec_known; 2952169689Skan *last_conflicts = integer_zero_node; 2953169689Skan } 2954169689Skan 2955169689Skan /* Both access functions are univariate. This includes SIV and MIV cases. */ 2956169689Skan else if (nb_vars_a == 1 && nb_vars_b == 1) 2957169689Skan { 2958169689Skan /* Both functions should have the same evolution sign. */ 2959169689Skan if (((A[0][0] > 0 && -A[1][0] > 0) 2960169689Skan || (A[0][0] < 0 && -A[1][0] < 0))) 2961169689Skan { 2962169689Skan /* The solutions are given by: 2963169689Skan | 2964169689Skan | [GAMMA/GCD_ALPHA_BETA t].[u11 u12] = [x0] 2965169689Skan | [u21 u22] [y0] 2966169689Skan 2967169689Skan For a given integer t. Using the following variables, 2968169689Skan 2969169689Skan | i0 = u11 * gamma / gcd_alpha_beta 2970169689Skan | j0 = u12 * gamma / gcd_alpha_beta 2971169689Skan | i1 = u21 2972169689Skan | j1 = u22 2973169689Skan 2974169689Skan the solutions are: 2975169689Skan 2976169689Skan | x0 = i0 + i1 * t, 2977169689Skan | y0 = j0 + j1 * t. */ 2978169689Skan 2979169689Skan int i0, j0, i1, j1; 2980169689Skan 2981169689Skan /* X0 and Y0 are the first iterations for which there is a 2982169689Skan dependence. X0, Y0 are two solutions of the Diophantine 2983169689Skan equation: chrec_a (X0) = chrec_b (Y0). */ 2984169689Skan int x0, y0; 2985169689Skan int niter, niter_a, niter_b; 2986169689Skan tree numiter_a, numiter_b; 2987169689Skan 2988169689Skan numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 2989169689Skan numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); 2990169689Skan 2991169689Skan if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) 2992169689Skan { 2993169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2994169689Skan fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); 2995169689Skan *overlaps_a = chrec_dont_know; 2996169689Skan *overlaps_b = chrec_dont_know; 2997169689Skan *last_conflicts = chrec_dont_know; 2998169689Skan goto end_analyze_subs_aa; 2999169689Skan } 3000169689Skan 3001169689Skan niter_a = int_cst_value (numiter_a); 3002169689Skan niter_b = int_cst_value (numiter_b); 3003169689Skan niter = MIN (niter_a, niter_b); 3004169689Skan 3005169689Skan i0 = U[0][0] * gamma / gcd_alpha_beta; 3006169689Skan j0 = U[0][1] * gamma / gcd_alpha_beta; 3007169689Skan i1 = U[1][0]; 3008169689Skan j1 = U[1][1]; 3009169689Skan 3010169689Skan if ((i1 == 0 && i0 < 0) 3011169689Skan || (j1 == 0 && j0 < 0)) 3012169689Skan { 3013169689Skan /* There is no solution. 3014169689Skan FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 3015169689Skan falls in here, but for the moment we don't look at the 3016169689Skan upper bound of the iteration domain. */ 3017169689Skan *overlaps_a = chrec_known; 3018169689Skan *overlaps_b = chrec_known; 3019169689Skan *last_conflicts = integer_zero_node; 3020169689Skan } 3021169689Skan 3022169689Skan else 3023169689Skan { 3024169689Skan if (i1 > 0) 3025169689Skan { 3026169689Skan tau1 = CEIL (-i0, i1); 3027169689Skan tau2 = FLOOR_DIV (niter - i0, i1); 3028169689Skan 3029169689Skan if (j1 > 0) 3030169689Skan { 3031169689Skan int last_conflict, min_multiple; 3032169689Skan tau1 = MAX (tau1, CEIL (-j0, j1)); 3033169689Skan tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1)); 3034169689Skan 3035169689Skan x0 = i1 * tau1 + i0; 3036169689Skan y0 = j1 * tau1 + j0; 3037169689Skan 3038169689Skan /* At this point (x0, y0) is one of the 3039169689Skan solutions to the Diophantine equation. The 3040169689Skan next step has to compute the smallest 3041169689Skan positive solution: the first conflicts. */ 3042169689Skan min_multiple = MIN (x0 / i1, y0 / j1); 3043169689Skan x0 -= i1 * min_multiple; 3044169689Skan y0 -= j1 * min_multiple; 3045169689Skan 3046169689Skan tau1 = (x0 - i0)/i1; 3047169689Skan last_conflict = tau2 - tau1; 3048169689Skan 3049169689Skan /* If the overlap occurs outside of the bounds of the 3050169689Skan loop, there is no dependence. */ 3051169689Skan if (x0 > niter || y0 > niter) 3052169689Skan { 3053169689Skan *overlaps_a = chrec_known; 3054169689Skan *overlaps_b = chrec_known; 3055169689Skan *last_conflicts = integer_zero_node; 3056169689Skan } 3057169689Skan else 3058169689Skan { 3059169689Skan *overlaps_a = build_polynomial_chrec 3060169689Skan (1, 3061169689Skan build_int_cst (NULL_TREE, x0), 3062169689Skan build_int_cst (NULL_TREE, i1)); 3063169689Skan *overlaps_b = build_polynomial_chrec 3064169689Skan (1, 3065169689Skan build_int_cst (NULL_TREE, y0), 3066169689Skan build_int_cst (NULL_TREE, j1)); 3067169689Skan *last_conflicts = build_int_cst (NULL_TREE, last_conflict); 3068169689Skan } 3069169689Skan } 3070169689Skan else 3071169689Skan { 3072169689Skan /* FIXME: For the moment, the upper bound of the 3073169689Skan iteration domain for j is not checked. */ 3074169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3075169689Skan fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); 3076169689Skan *overlaps_a = chrec_dont_know; 3077169689Skan *overlaps_b = chrec_dont_know; 3078169689Skan *last_conflicts = chrec_dont_know; 3079169689Skan } 3080169689Skan } 3081169689Skan 3082169689Skan else 3083169689Skan { 3084169689Skan /* FIXME: For the moment, the upper bound of the 3085169689Skan iteration domain for i is not checked. */ 3086169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3087169689Skan fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); 3088169689Skan *overlaps_a = chrec_dont_know; 3089169689Skan *overlaps_b = chrec_dont_know; 3090169689Skan *last_conflicts = chrec_dont_know; 3091169689Skan } 3092169689Skan } 3093169689Skan } 3094169689Skan else 3095169689Skan { 3096169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3097169689Skan fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); 3098169689Skan *overlaps_a = chrec_dont_know; 3099169689Skan *overlaps_b = chrec_dont_know; 3100169689Skan *last_conflicts = chrec_dont_know; 3101169689Skan } 3102169689Skan } 3103169689Skan 3104169689Skan else 3105169689Skan { 3106169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3107169689Skan fprintf (dump_file, "affine-affine test failed: unimplemented.\n"); 3108169689Skan *overlaps_a = chrec_dont_know; 3109169689Skan *overlaps_b = chrec_dont_know; 3110169689Skan *last_conflicts = chrec_dont_know; 3111169689Skan } 3112169689Skan 3113169689Skanend_analyze_subs_aa: 3114169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3115169689Skan { 3116169689Skan fprintf (dump_file, " (overlaps_a = "); 3117169689Skan print_generic_expr (dump_file, *overlaps_a, 0); 3118169689Skan fprintf (dump_file, ")\n (overlaps_b = "); 3119169689Skan print_generic_expr (dump_file, *overlaps_b, 0); 3120169689Skan fprintf (dump_file, ")\n"); 3121169689Skan fprintf (dump_file, ")\n"); 3122169689Skan } 3123169689Skan} 3124169689Skan 3125169689Skan/* Returns true when analyze_subscript_affine_affine can be used for 3126169689Skan determining the dependence relation between chrec_a and chrec_b, 3127169689Skan that contain symbols. This function modifies chrec_a and chrec_b 3128169689Skan such that the analysis result is the same, and such that they don't 3129169689Skan contain symbols, and then can safely be passed to the analyzer. 3130169689Skan 3131169689Skan Example: The analysis of the following tuples of evolutions produce 3132169689Skan the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1 3133169689Skan vs. {0, +, 1}_1 3134169689Skan 3135169689Skan {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1) 3136169689Skan {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1) 3137169689Skan*/ 3138169689Skan 3139169689Skanstatic bool 3140169689Skancan_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b) 3141169689Skan{ 3142169689Skan tree diff, type, left_a, left_b, right_b; 3143169689Skan 3144169689Skan if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a)) 3145169689Skan || chrec_contains_symbols (CHREC_RIGHT (*chrec_b))) 3146169689Skan /* FIXME: For the moment not handled. Might be refined later. */ 3147169689Skan return false; 3148169689Skan 3149169689Skan type = chrec_type (*chrec_a); 3150169689Skan left_a = CHREC_LEFT (*chrec_a); 3151169689Skan left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE); 3152169689Skan diff = chrec_fold_minus (type, left_a, left_b); 3153169689Skan 3154169689Skan if (!evolution_function_is_constant_p (diff)) 3155169689Skan return false; 3156169689Skan 3157169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3158169689Skan fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n"); 3159169689Skan 3160169689Skan *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a), 3161169689Skan diff, CHREC_RIGHT (*chrec_a)); 3162169689Skan right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE); 3163169689Skan *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b), 3164169689Skan build_int_cst (type, 0), 3165169689Skan right_b); 3166169689Skan return true; 3167169689Skan} 3168169689Skan 3169169689Skan/* Analyze a SIV (Single Index Variable) subscript. *OVERLAPS_A and 3170169689Skan *OVERLAPS_B are initialized to the functions that describe the 3171169689Skan relation between the elements accessed twice by CHREC_A and 3172169689Skan CHREC_B. For k >= 0, the following property is verified: 3173169689Skan 3174169689Skan CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 3175169689Skan 3176169689Skanstatic void 3177169689Skananalyze_siv_subscript (tree chrec_a, 3178169689Skan tree chrec_b, 3179169689Skan tree *overlaps_a, 3180169689Skan tree *overlaps_b, 3181169689Skan tree *last_conflicts) 3182169689Skan{ 3183169689Skan dependence_stats.num_siv++; 3184169689Skan 3185169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3186169689Skan fprintf (dump_file, "(analyze_siv_subscript \n"); 3187169689Skan 3188169689Skan if (evolution_function_is_constant_p (chrec_a) 3189169689Skan && evolution_function_is_affine_p (chrec_b)) 3190169689Skan analyze_siv_subscript_cst_affine (chrec_a, chrec_b, 3191169689Skan overlaps_a, overlaps_b, last_conflicts); 3192169689Skan 3193169689Skan else if (evolution_function_is_affine_p (chrec_a) 3194169689Skan && evolution_function_is_constant_p (chrec_b)) 3195169689Skan analyze_siv_subscript_cst_affine (chrec_b, chrec_a, 3196169689Skan overlaps_b, overlaps_a, last_conflicts); 3197169689Skan 3198169689Skan else if (evolution_function_is_affine_p (chrec_a) 3199169689Skan && evolution_function_is_affine_p (chrec_b)) 3200169689Skan { 3201169689Skan if (!chrec_contains_symbols (chrec_a) 3202169689Skan && !chrec_contains_symbols (chrec_b)) 3203169689Skan { 3204169689Skan analyze_subscript_affine_affine (chrec_a, chrec_b, 3205169689Skan overlaps_a, overlaps_b, 3206169689Skan last_conflicts); 3207169689Skan 3208169689Skan if (*overlaps_a == chrec_dont_know 3209169689Skan || *overlaps_b == chrec_dont_know) 3210169689Skan dependence_stats.num_siv_unimplemented++; 3211169689Skan else if (*overlaps_a == chrec_known 3212169689Skan || *overlaps_b == chrec_known) 3213169689Skan dependence_stats.num_siv_independent++; 3214169689Skan else 3215169689Skan dependence_stats.num_siv_dependent++; 3216169689Skan } 3217169689Skan else if (can_use_analyze_subscript_affine_affine (&chrec_a, 3218169689Skan &chrec_b)) 3219169689Skan { 3220169689Skan analyze_subscript_affine_affine (chrec_a, chrec_b, 3221169689Skan overlaps_a, overlaps_b, 3222169689Skan last_conflicts); 3223169689Skan /* FIXME: The number of iterations is a symbolic expression. 3224169689Skan Compute it properly. */ 3225169689Skan *last_conflicts = chrec_dont_know; 3226169689Skan 3227169689Skan if (*overlaps_a == chrec_dont_know 3228169689Skan || *overlaps_b == chrec_dont_know) 3229169689Skan dependence_stats.num_siv_unimplemented++; 3230169689Skan else if (*overlaps_a == chrec_known 3231169689Skan || *overlaps_b == chrec_known) 3232169689Skan dependence_stats.num_siv_independent++; 3233169689Skan else 3234169689Skan dependence_stats.num_siv_dependent++; 3235169689Skan } 3236169689Skan else 3237169689Skan goto siv_subscript_dontknow; 3238169689Skan } 3239169689Skan 3240169689Skan else 3241169689Skan { 3242169689Skan siv_subscript_dontknow:; 3243169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3244169689Skan fprintf (dump_file, "siv test failed: unimplemented.\n"); 3245169689Skan *overlaps_a = chrec_dont_know; 3246169689Skan *overlaps_b = chrec_dont_know; 3247169689Skan *last_conflicts = chrec_dont_know; 3248169689Skan dependence_stats.num_siv_unimplemented++; 3249169689Skan } 3250169689Skan 3251169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3252169689Skan fprintf (dump_file, ")\n"); 3253169689Skan} 3254169689Skan 3255169689Skan/* Return true when the property can be computed. RES should contain 3256169689Skan true when calling the first time this function, then it is set to 3257169689Skan false when one of the evolution steps of an affine CHREC does not 3258169689Skan divide the constant CST. */ 3259169689Skan 3260169689Skanstatic bool 3261169689Skanchrec_steps_divide_constant_p (tree chrec, 3262169689Skan tree cst, 3263169689Skan bool *res) 3264169689Skan{ 3265169689Skan switch (TREE_CODE (chrec)) 3266169689Skan { 3267169689Skan case POLYNOMIAL_CHREC: 3268169689Skan if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))) 3269169689Skan { 3270169689Skan if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst)) 3271169689Skan /* Keep RES to true, and iterate on other dimensions. */ 3272169689Skan return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res); 3273169689Skan 3274169689Skan *res = false; 3275169689Skan return true; 3276169689Skan } 3277169689Skan else 3278169689Skan /* When the step is a parameter the result is undetermined. */ 3279169689Skan return false; 3280169689Skan 3281169689Skan default: 3282169689Skan /* On the initial condition, return true. */ 3283169689Skan return true; 3284169689Skan } 3285169689Skan} 3286169689Skan 3287169689Skan/* Analyze a MIV (Multiple Index Variable) subscript. *OVERLAPS_A and 3288169689Skan *OVERLAPS_B are initialized to the functions that describe the 3289169689Skan relation between the elements accessed twice by CHREC_A and 3290169689Skan CHREC_B. For k >= 0, the following property is verified: 3291169689Skan 3292169689Skan CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)). */ 3293169689Skan 3294169689Skanstatic void 3295169689Skananalyze_miv_subscript (tree chrec_a, 3296169689Skan tree chrec_b, 3297169689Skan tree *overlaps_a, 3298169689Skan tree *overlaps_b, 3299169689Skan tree *last_conflicts) 3300169689Skan{ 3301169689Skan /* FIXME: This is a MIV subscript, not yet handled. 3302169689Skan Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from 3303169689Skan (A[i] vs. A[j]). 3304169689Skan 3305169689Skan In the SIV test we had to solve a Diophantine equation with two 3306169689Skan variables. In the MIV case we have to solve a Diophantine 3307169689Skan equation with 2*n variables (if the subscript uses n IVs). 3308169689Skan */ 3309169689Skan bool divide_p = true; 3310169689Skan tree difference; 3311169689Skan dependence_stats.num_miv++; 3312169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3313169689Skan fprintf (dump_file, "(analyze_miv_subscript \n"); 3314169689Skan 3315169689Skan chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE); 3316169689Skan chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE); 3317169689Skan difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b); 3318169689Skan 3319169689Skan if (eq_evolutions_p (chrec_a, chrec_b)) 3320169689Skan { 3321169689Skan /* Access functions are the same: all the elements are accessed 3322169689Skan in the same order. */ 3323169689Skan *overlaps_a = integer_zero_node; 3324169689Skan *overlaps_b = integer_zero_node; 3325169689Skan *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); 3326169689Skan dependence_stats.num_miv_dependent++; 3327169689Skan } 3328169689Skan 3329169689Skan else if (evolution_function_is_constant_p (difference) 3330169689Skan /* For the moment, the following is verified: 3331169689Skan evolution_function_is_affine_multivariate_p (chrec_a) */ 3332169689Skan && chrec_steps_divide_constant_p (chrec_a, difference, ÷_p) 3333169689Skan && !divide_p) 3334169689Skan { 3335169689Skan /* testsuite/.../ssa-chrec-33.c 3336169689Skan {{21, +, 2}_1, +, -2}_2 vs. {{20, +, 2}_1, +, -2}_2 3337169689Skan 3338169689Skan The difference is 1, and the evolution steps are equal to 2, 3339169689Skan consequently there are no overlapping elements. */ 3340169689Skan *overlaps_a = chrec_known; 3341169689Skan *overlaps_b = chrec_known; 3342169689Skan *last_conflicts = integer_zero_node; 3343169689Skan dependence_stats.num_miv_independent++; 3344169689Skan } 3345169689Skan 3346169689Skan else if (evolution_function_is_affine_multivariate_p (chrec_a) 3347169689Skan && !chrec_contains_symbols (chrec_a) 3348169689Skan && evolution_function_is_affine_multivariate_p (chrec_b) 3349169689Skan && !chrec_contains_symbols (chrec_b)) 3350169689Skan { 3351169689Skan /* testsuite/.../ssa-chrec-35.c 3352169689Skan {0, +, 1}_2 vs. {0, +, 1}_3 3353169689Skan the overlapping elements are respectively located at iterations: 3354169689Skan {0, +, 1}_x and {0, +, 1}_x, 3355169689Skan in other words, we have the equality: 3356169689Skan {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x) 3357169689Skan 3358169689Skan Other examples: 3359169689Skan {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) = 3360169689Skan {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y) 3361169689Skan 3362169689Skan {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) = 3363169689Skan {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) 3364169689Skan */ 3365169689Skan analyze_subscript_affine_affine (chrec_a, chrec_b, 3366169689Skan overlaps_a, overlaps_b, last_conflicts); 3367169689Skan 3368169689Skan if (*overlaps_a == chrec_dont_know 3369169689Skan || *overlaps_b == chrec_dont_know) 3370169689Skan dependence_stats.num_miv_unimplemented++; 3371169689Skan else if (*overlaps_a == chrec_known 3372169689Skan || *overlaps_b == chrec_known) 3373169689Skan dependence_stats.num_miv_independent++; 3374169689Skan else 3375169689Skan dependence_stats.num_miv_dependent++; 3376169689Skan } 3377169689Skan 3378169689Skan else 3379169689Skan { 3380169689Skan /* When the analysis is too difficult, answer "don't know". */ 3381169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3382169689Skan fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n"); 3383169689Skan 3384169689Skan *overlaps_a = chrec_dont_know; 3385169689Skan *overlaps_b = chrec_dont_know; 3386169689Skan *last_conflicts = chrec_dont_know; 3387169689Skan dependence_stats.num_miv_unimplemented++; 3388169689Skan } 3389169689Skan 3390169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3391169689Skan fprintf (dump_file, ")\n"); 3392169689Skan} 3393169689Skan 3394169689Skan/* Determines the iterations for which CHREC_A is equal to CHREC_B. 3395169689Skan OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with 3396169689Skan two functions that describe the iterations that contain conflicting 3397169689Skan elements. 3398169689Skan 3399169689Skan Remark: For an integer k >= 0, the following equality is true: 3400169689Skan 3401169689Skan CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)). 3402169689Skan*/ 3403169689Skan 3404169689Skanstatic void 3405169689Skananalyze_overlapping_iterations (tree chrec_a, 3406169689Skan tree chrec_b, 3407169689Skan tree *overlap_iterations_a, 3408169689Skan tree *overlap_iterations_b, 3409169689Skan tree *last_conflicts) 3410169689Skan{ 3411169689Skan dependence_stats.num_subscript_tests++; 3412169689Skan 3413169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3414169689Skan { 3415169689Skan fprintf (dump_file, "(analyze_overlapping_iterations \n"); 3416169689Skan fprintf (dump_file, " (chrec_a = "); 3417169689Skan print_generic_expr (dump_file, chrec_a, 0); 3418169689Skan fprintf (dump_file, ")\n (chrec_b = "); 3419169689Skan print_generic_expr (dump_file, chrec_b, 0); 3420169689Skan fprintf (dump_file, ")\n"); 3421169689Skan } 3422169689Skan 3423169689Skan if (chrec_a == NULL_TREE 3424169689Skan || chrec_b == NULL_TREE 3425169689Skan || chrec_contains_undetermined (chrec_a) 3426169689Skan || chrec_contains_undetermined (chrec_b)) 3427169689Skan { 3428169689Skan dependence_stats.num_subscript_undetermined++; 3429169689Skan 3430169689Skan *overlap_iterations_a = chrec_dont_know; 3431169689Skan *overlap_iterations_b = chrec_dont_know; 3432169689Skan } 3433169689Skan 3434169689Skan /* If they are the same chrec, and are affine, they overlap 3435169689Skan on every iteration. */ 3436169689Skan else if (eq_evolutions_p (chrec_a, chrec_b) 3437169689Skan && evolution_function_is_affine_multivariate_p (chrec_a)) 3438169689Skan { 3439169689Skan dependence_stats.num_same_subscript_function++; 3440169689Skan *overlap_iterations_a = integer_zero_node; 3441169689Skan *overlap_iterations_b = integer_zero_node; 3442169689Skan *last_conflicts = chrec_dont_know; 3443169689Skan } 3444169689Skan 3445169689Skan /* If they aren't the same, and aren't affine, we can't do anything 3446169689Skan yet. */ 3447169689Skan else if ((chrec_contains_symbols (chrec_a) 3448169689Skan || chrec_contains_symbols (chrec_b)) 3449169689Skan && (!evolution_function_is_affine_multivariate_p (chrec_a) 3450169689Skan || !evolution_function_is_affine_multivariate_p (chrec_b))) 3451169689Skan { 3452169689Skan dependence_stats.num_subscript_undetermined++; 3453169689Skan *overlap_iterations_a = chrec_dont_know; 3454169689Skan *overlap_iterations_b = chrec_dont_know; 3455169689Skan } 3456169689Skan 3457169689Skan else if (ziv_subscript_p (chrec_a, chrec_b)) 3458169689Skan analyze_ziv_subscript (chrec_a, chrec_b, 3459169689Skan overlap_iterations_a, overlap_iterations_b, 3460169689Skan last_conflicts); 3461169689Skan 3462169689Skan else if (siv_subscript_p (chrec_a, chrec_b)) 3463169689Skan analyze_siv_subscript (chrec_a, chrec_b, 3464169689Skan overlap_iterations_a, overlap_iterations_b, 3465169689Skan last_conflicts); 3466169689Skan 3467169689Skan else 3468169689Skan analyze_miv_subscript (chrec_a, chrec_b, 3469169689Skan overlap_iterations_a, overlap_iterations_b, 3470169689Skan last_conflicts); 3471169689Skan 3472169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3473169689Skan { 3474169689Skan fprintf (dump_file, " (overlap_iterations_a = "); 3475169689Skan print_generic_expr (dump_file, *overlap_iterations_a, 0); 3476169689Skan fprintf (dump_file, ")\n (overlap_iterations_b = "); 3477169689Skan print_generic_expr (dump_file, *overlap_iterations_b, 0); 3478169689Skan fprintf (dump_file, ")\n"); 3479169689Skan fprintf (dump_file, ")\n"); 3480169689Skan } 3481169689Skan} 3482169689Skan 3483169689Skan/* Helper function for uniquely inserting distance vectors. */ 3484169689Skan 3485169689Skanstatic void 3486169689Skansave_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v) 3487169689Skan{ 3488169689Skan unsigned i; 3489169689Skan lambda_vector v; 3490169689Skan 3491169689Skan for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++) 3492169689Skan if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr))) 3493169689Skan return; 3494169689Skan 3495169689Skan VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v); 3496169689Skan} 3497169689Skan 3498169689Skan/* Helper function for uniquely inserting direction vectors. */ 3499169689Skan 3500169689Skanstatic void 3501169689Skansave_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v) 3502169689Skan{ 3503169689Skan unsigned i; 3504169689Skan lambda_vector v; 3505169689Skan 3506169689Skan for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++) 3507169689Skan if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr))) 3508169689Skan return; 3509169689Skan 3510169689Skan VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v); 3511169689Skan} 3512169689Skan 3513169689Skan/* Add a distance of 1 on all the loops outer than INDEX. If we 3514169689Skan haven't yet determined a distance for this outer loop, push a new 3515169689Skan distance vector composed of the previous distance, and a distance 3516169689Skan of 1 for this outer loop. Example: 3517169689Skan 3518169689Skan | loop_1 3519169689Skan | loop_2 3520169689Skan | A[10] 3521169689Skan | endloop_2 3522169689Skan | endloop_1 3523169689Skan 3524169689Skan Saved vectors are of the form (dist_in_1, dist_in_2). First, we 3525169689Skan save (0, 1), then we have to save (1, 0). */ 3526169689Skan 3527169689Skanstatic void 3528169689Skanadd_outer_distances (struct data_dependence_relation *ddr, 3529169689Skan lambda_vector dist_v, int index) 3530169689Skan{ 3531169689Skan /* For each outer loop where init_v is not set, the accesses are 3532169689Skan in dependence of distance 1 in the loop. */ 3533169689Skan while (--index >= 0) 3534169689Skan { 3535169689Skan lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3536169689Skan lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr)); 3537169689Skan save_v[index] = 1; 3538169689Skan save_dist_v (ddr, save_v); 3539169689Skan } 3540169689Skan} 3541169689Skan 3542169689Skan/* Return false when fail to represent the data dependence as a 3543169689Skan distance vector. INIT_B is set to true when a component has been 3544169689Skan added to the distance vector DIST_V. INDEX_CARRY is then set to 3545169689Skan the index in DIST_V that carries the dependence. */ 3546169689Skan 3547169689Skanstatic bool 3548169689Skanbuild_classic_dist_vector_1 (struct data_dependence_relation *ddr, 3549169689Skan struct data_reference *ddr_a, 3550169689Skan struct data_reference *ddr_b, 3551169689Skan lambda_vector dist_v, bool *init_b, 3552169689Skan int *index_carry) 3553169689Skan{ 3554169689Skan unsigned i; 3555169689Skan lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3556169689Skan 3557169689Skan for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 3558169689Skan { 3559169689Skan tree access_fn_a, access_fn_b; 3560169689Skan struct subscript *subscript = DDR_SUBSCRIPT (ddr, i); 3561169689Skan 3562169689Skan if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) 3563169689Skan { 3564169689Skan non_affine_dependence_relation (ddr); 3565169689Skan return false; 3566169689Skan } 3567169689Skan 3568169689Skan access_fn_a = DR_ACCESS_FN (ddr_a, i); 3569169689Skan access_fn_b = DR_ACCESS_FN (ddr_b, i); 3570169689Skan 3571169689Skan if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC 3572169689Skan && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC) 3573169689Skan { 3574169689Skan int dist, index; 3575169689Skan int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a), 3576169689Skan DDR_LOOP_NEST (ddr)); 3577169689Skan int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b), 3578169689Skan DDR_LOOP_NEST (ddr)); 3579169689Skan 3580169689Skan /* The dependence is carried by the outermost loop. Example: 3581169689Skan | loop_1 3582169689Skan | A[{4, +, 1}_1] 3583169689Skan | loop_2 3584169689Skan | A[{5, +, 1}_2] 3585169689Skan | endloop_2 3586169689Skan | endloop_1 3587169689Skan In this case, the dependence is carried by loop_1. */ 3588169689Skan index = index_a < index_b ? index_a : index_b; 3589169689Skan *index_carry = MIN (index, *index_carry); 3590169689Skan 3591169689Skan if (chrec_contains_undetermined (SUB_DISTANCE (subscript))) 3592169689Skan { 3593169689Skan non_affine_dependence_relation (ddr); 3594169689Skan return false; 3595169689Skan } 3596169689Skan 3597169689Skan dist = int_cst_value (SUB_DISTANCE (subscript)); 3598169689Skan 3599169689Skan /* This is the subscript coupling test. If we have already 3600169689Skan recorded a distance for this loop (a distance coming from 3601169689Skan another subscript), it should be the same. For example, 3602169689Skan in the following code, there is no dependence: 3603169689Skan 3604169689Skan | loop i = 0, N, 1 3605169689Skan | T[i+1][i] = ... 3606169689Skan | ... = T[i][i] 3607169689Skan | endloop 3608169689Skan */ 3609169689Skan if (init_v[index] != 0 && dist_v[index] != dist) 3610169689Skan { 3611169689Skan finalize_ddr_dependent (ddr, chrec_known); 3612169689Skan return false; 3613169689Skan } 3614169689Skan 3615169689Skan dist_v[index] = dist; 3616169689Skan init_v[index] = 1; 3617169689Skan *init_b = true; 3618169689Skan } 3619169689Skan else 3620169689Skan { 3621169689Skan /* This can be for example an affine vs. constant dependence 3622169689Skan (T[i] vs. T[3]) that is not an affine dependence and is 3623169689Skan not representable as a distance vector. */ 3624169689Skan non_affine_dependence_relation (ddr); 3625169689Skan return false; 3626169689Skan } 3627169689Skan } 3628169689Skan 3629169689Skan return true; 3630169689Skan} 3631169689Skan 3632169689Skan/* Return true when the DDR contains two data references that have the 3633169689Skan same access functions. */ 3634169689Skan 3635169689Skanstatic bool 3636169689Skansame_access_functions (struct data_dependence_relation *ddr) 3637169689Skan{ 3638169689Skan unsigned i; 3639169689Skan 3640169689Skan for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 3641169689Skan if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), 3642169689Skan DR_ACCESS_FN (DDR_B (ddr), i))) 3643169689Skan return false; 3644169689Skan 3645169689Skan return true; 3646169689Skan} 3647169689Skan 3648169689Skan/* Helper function for the case where DDR_A and DDR_B are the same 3649169689Skan multivariate access function. */ 3650169689Skan 3651169689Skanstatic void 3652169689Skanadd_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2) 3653169689Skan{ 3654169689Skan int x_1, x_2; 3655169689Skan tree c_1 = CHREC_LEFT (c_2); 3656169689Skan tree c_0 = CHREC_LEFT (c_1); 3657169689Skan lambda_vector dist_v; 3658169689Skan 3659169689Skan /* Polynomials with more than 2 variables are not handled yet. */ 3660169689Skan if (TREE_CODE (c_0) != INTEGER_CST) 3661169689Skan { 3662169689Skan DDR_ARE_DEPENDENT (ddr) = chrec_dont_know; 3663169689Skan return; 3664169689Skan } 3665169689Skan 3666169689Skan x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr)); 3667169689Skan x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr)); 3668169689Skan 3669169689Skan /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2). */ 3670169689Skan dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3671169689Skan dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2)); 3672169689Skan dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1)); 3673169689Skan save_dist_v (ddr, dist_v); 3674169689Skan 3675169689Skan add_outer_distances (ddr, dist_v, x_1); 3676169689Skan} 3677169689Skan 3678169689Skan/* Helper function for the case where DDR_A and DDR_B are the same 3679169689Skan access functions. */ 3680169689Skan 3681169689Skanstatic void 3682169689Skanadd_other_self_distances (struct data_dependence_relation *ddr) 3683169689Skan{ 3684169689Skan lambda_vector dist_v; 3685169689Skan unsigned i; 3686169689Skan int index_carry = DDR_NB_LOOPS (ddr); 3687169689Skan 3688169689Skan for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 3689169689Skan { 3690169689Skan tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i); 3691169689Skan 3692169689Skan if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC) 3693169689Skan { 3694169689Skan if (!evolution_function_is_univariate_p (access_fun)) 3695169689Skan { 3696169689Skan if (DDR_NUM_SUBSCRIPTS (ddr) != 1) 3697169689Skan { 3698169689Skan DDR_ARE_DEPENDENT (ddr) = chrec_dont_know; 3699169689Skan return; 3700169689Skan } 3701169689Skan 3702169689Skan add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0)); 3703169689Skan return; 3704169689Skan } 3705169689Skan 3706169689Skan index_carry = MIN (index_carry, 3707169689Skan index_in_loop_nest (CHREC_VARIABLE (access_fun), 3708169689Skan DDR_LOOP_NEST (ddr))); 3709169689Skan } 3710169689Skan } 3711169689Skan 3712169689Skan dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3713169689Skan add_outer_distances (ddr, dist_v, index_carry); 3714169689Skan} 3715169689Skan 3716169689Skan/* Compute the classic per loop distance vector. DDR is the data 3717169689Skan dependence relation to build a vector from. Return false when fail 3718169689Skan to represent the data dependence as a distance vector. */ 3719169689Skan 3720169689Skanstatic bool 3721169689Skanbuild_classic_dist_vector (struct data_dependence_relation *ddr) 3722169689Skan{ 3723169689Skan bool init_b = false; 3724169689Skan int index_carry = DDR_NB_LOOPS (ddr); 3725169689Skan lambda_vector dist_v; 3726169689Skan 3727169689Skan if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) 3728169689Skan return true; 3729169689Skan 3730169689Skan if (same_access_functions (ddr)) 3731169689Skan { 3732169689Skan /* Save the 0 vector. */ 3733169689Skan dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3734169689Skan save_dist_v (ddr, dist_v); 3735169689Skan 3736169689Skan if (DDR_NB_LOOPS (ddr) > 1) 3737169689Skan add_other_self_distances (ddr); 3738169689Skan 3739169689Skan return true; 3740169689Skan } 3741169689Skan 3742169689Skan dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3743169689Skan if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr), 3744169689Skan dist_v, &init_b, &index_carry)) 3745169689Skan return false; 3746169689Skan 3747169689Skan /* Save the distance vector if we initialized one. */ 3748169689Skan if (init_b) 3749169689Skan { 3750169689Skan /* Verify a basic constraint: classic distance vectors should 3751169689Skan always be lexicographically positive. 3752169689Skan 3753169689Skan Data references are collected in the order of execution of 3754169689Skan the program, thus for the following loop 3755169689Skan 3756169689Skan | for (i = 1; i < 100; i++) 3757169689Skan | for (j = 1; j < 100; j++) 3758169689Skan | { 3759169689Skan | t = T[j+1][i-1]; // A 3760169689Skan | T[j][i] = t + 2; // B 3761169689Skan | } 3762169689Skan 3763169689Skan references are collected following the direction of the wind: 3764169689Skan A then B. The data dependence tests are performed also 3765169689Skan following this order, such that we're looking at the distance 3766169689Skan separating the elements accessed by A from the elements later 3767169689Skan accessed by B. But in this example, the distance returned by 3768169689Skan test_dep (A, B) is lexicographically negative (-1, 1), that 3769169689Skan means that the access A occurs later than B with respect to 3770169689Skan the outer loop, ie. we're actually looking upwind. In this 3771169689Skan case we solve test_dep (B, A) looking downwind to the 3772169689Skan lexicographically positive solution, that returns the 3773169689Skan distance vector (1, -1). */ 3774169689Skan if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr))) 3775169689Skan { 3776169689Skan lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3777169689Skan subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr)); 3778169689Skan compute_subscript_distance (ddr); 3779169689Skan build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), 3780169689Skan save_v, &init_b, &index_carry); 3781169689Skan save_dist_v (ddr, save_v); 3782169689Skan 3783169689Skan /* In this case there is a dependence forward for all the 3784169689Skan outer loops: 3785169689Skan 3786169689Skan | for (k = 1; k < 100; k++) 3787169689Skan | for (i = 1; i < 100; i++) 3788169689Skan | for (j = 1; j < 100; j++) 3789169689Skan | { 3790169689Skan | t = T[j+1][i-1]; // A 3791169689Skan | T[j][i] = t + 2; // B 3792169689Skan | } 3793169689Skan 3794169689Skan the vectors are: 3795169689Skan (0, 1, -1) 3796169689Skan (1, 1, -1) 3797169689Skan (1, -1, 1) 3798169689Skan */ 3799169689Skan if (DDR_NB_LOOPS (ddr) > 1) 3800169689Skan { 3801169689Skan add_outer_distances (ddr, save_v, index_carry); 3802169689Skan add_outer_distances (ddr, dist_v, index_carry); 3803169689Skan } 3804169689Skan } 3805169689Skan else 3806169689Skan { 3807169689Skan lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3808169689Skan lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr)); 3809169689Skan save_dist_v (ddr, save_v); 3810169689Skan 3811169689Skan if (DDR_NB_LOOPS (ddr) > 1) 3812169689Skan { 3813169689Skan lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3814169689Skan 3815169689Skan subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr)); 3816169689Skan compute_subscript_distance (ddr); 3817169689Skan build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr), 3818169689Skan opposite_v, &init_b, &index_carry); 3819169689Skan 3820169689Skan add_outer_distances (ddr, dist_v, index_carry); 3821169689Skan add_outer_distances (ddr, opposite_v, index_carry); 3822169689Skan } 3823169689Skan } 3824169689Skan } 3825169689Skan else 3826169689Skan { 3827169689Skan /* There is a distance of 1 on all the outer loops: Example: 3828169689Skan there is a dependence of distance 1 on loop_1 for the array A. 3829169689Skan 3830169689Skan | loop_1 3831169689Skan | A[5] = ... 3832169689Skan | endloop 3833169689Skan */ 3834169689Skan add_outer_distances (ddr, dist_v, 3835169689Skan lambda_vector_first_nz (dist_v, 3836169689Skan DDR_NB_LOOPS (ddr), 0)); 3837169689Skan } 3838169689Skan 3839169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3840169689Skan { 3841169689Skan unsigned i; 3842169689Skan 3843169689Skan fprintf (dump_file, "(build_classic_dist_vector\n"); 3844169689Skan for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++) 3845169689Skan { 3846169689Skan fprintf (dump_file, " dist_vector = ("); 3847169689Skan print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i), 3848169689Skan DDR_NB_LOOPS (ddr)); 3849169689Skan fprintf (dump_file, " )\n"); 3850169689Skan } 3851169689Skan fprintf (dump_file, ")\n"); 3852169689Skan } 3853169689Skan 3854169689Skan return true; 3855169689Skan} 3856169689Skan 3857169689Skan/* Return the direction for a given distance. 3858169689Skan FIXME: Computing dir this way is suboptimal, since dir can catch 3859169689Skan cases that dist is unable to represent. */ 3860169689Skan 3861169689Skanstatic inline enum data_dependence_direction 3862169689Skandir_from_dist (int dist) 3863169689Skan{ 3864169689Skan if (dist > 0) 3865169689Skan return dir_positive; 3866169689Skan else if (dist < 0) 3867169689Skan return dir_negative; 3868169689Skan else 3869169689Skan return dir_equal; 3870169689Skan} 3871169689Skan 3872169689Skan/* Compute the classic per loop direction vector. DDR is the data 3873169689Skan dependence relation to build a vector from. */ 3874169689Skan 3875169689Skanstatic void 3876169689Skanbuild_classic_dir_vector (struct data_dependence_relation *ddr) 3877169689Skan{ 3878169689Skan unsigned i, j; 3879169689Skan lambda_vector dist_v; 3880169689Skan 3881169689Skan for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++) 3882169689Skan { 3883169689Skan lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); 3884169689Skan 3885169689Skan for (j = 0; j < DDR_NB_LOOPS (ddr); j++) 3886169689Skan dir_v[j] = dir_from_dist (dist_v[j]); 3887169689Skan 3888169689Skan save_dir_v (ddr, dir_v); 3889169689Skan } 3890169689Skan} 3891169689Skan 3892169689Skan/* Helper function. Returns true when there is a dependence between 3893169689Skan data references DRA and DRB. */ 3894169689Skan 3895169689Skanstatic bool 3896169689Skansubscript_dependence_tester_1 (struct data_dependence_relation *ddr, 3897169689Skan struct data_reference *dra, 3898169689Skan struct data_reference *drb) 3899169689Skan{ 3900169689Skan unsigned int i; 3901169689Skan tree last_conflicts; 3902169689Skan struct subscript *subscript; 3903169689Skan 3904169689Skan for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); 3905169689Skan i++) 3906169689Skan { 3907169689Skan tree overlaps_a, overlaps_b; 3908169689Skan 3909169689Skan analyze_overlapping_iterations (DR_ACCESS_FN (dra, i), 3910169689Skan DR_ACCESS_FN (drb, i), 3911169689Skan &overlaps_a, &overlaps_b, 3912169689Skan &last_conflicts); 3913169689Skan 3914169689Skan if (chrec_contains_undetermined (overlaps_a) 3915169689Skan || chrec_contains_undetermined (overlaps_b)) 3916169689Skan { 3917169689Skan finalize_ddr_dependent (ddr, chrec_dont_know); 3918169689Skan dependence_stats.num_dependence_undetermined++; 3919169689Skan return false; 3920169689Skan } 3921169689Skan 3922169689Skan else if (overlaps_a == chrec_known 3923169689Skan || overlaps_b == chrec_known) 3924169689Skan { 3925169689Skan finalize_ddr_dependent (ddr, chrec_known); 3926169689Skan dependence_stats.num_dependence_independent++; 3927169689Skan return false; 3928169689Skan } 3929169689Skan 3930169689Skan else 3931169689Skan { 3932169689Skan SUB_CONFLICTS_IN_A (subscript) = overlaps_a; 3933169689Skan SUB_CONFLICTS_IN_B (subscript) = overlaps_b; 3934169689Skan SUB_LAST_CONFLICT (subscript) = last_conflicts; 3935169689Skan } 3936169689Skan } 3937169689Skan 3938169689Skan return true; 3939169689Skan} 3940169689Skan 3941169689Skan/* Computes the conflicting iterations, and initialize DDR. */ 3942169689Skan 3943169689Skanstatic void 3944169689Skansubscript_dependence_tester (struct data_dependence_relation *ddr) 3945169689Skan{ 3946169689Skan 3947169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3948169689Skan fprintf (dump_file, "(subscript_dependence_tester \n"); 3949169689Skan 3950169689Skan if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr))) 3951169689Skan dependence_stats.num_dependence_dependent++; 3952169689Skan 3953169689Skan compute_subscript_distance (ddr); 3954169689Skan if (build_classic_dist_vector (ddr)) 3955169689Skan build_classic_dir_vector (ddr); 3956169689Skan 3957169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3958169689Skan fprintf (dump_file, ")\n"); 3959169689Skan} 3960169689Skan 3961169689Skan/* Returns true when all the access functions of A are affine or 3962169689Skan constant. */ 3963169689Skan 3964169689Skanstatic bool 3965169689Skanaccess_functions_are_affine_or_constant_p (struct data_reference *a) 3966169689Skan{ 3967169689Skan unsigned int i; 3968169689Skan VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a); 3969169689Skan tree t; 3970169689Skan 3971169689Skan for (i = 0; VEC_iterate (tree, *fns, i, t); i++) 3972169689Skan if (!evolution_function_is_constant_p (t) 3973169689Skan && !evolution_function_is_affine_multivariate_p (t)) 3974169689Skan return false; 3975169689Skan 3976169689Skan return true; 3977169689Skan} 3978169689Skan 3979169689Skan/* This computes the affine dependence relation between A and B. 3980169689Skan CHREC_KNOWN is used for representing the independence between two 3981169689Skan accesses, while CHREC_DONT_KNOW is used for representing the unknown 3982169689Skan relation. 3983169689Skan 3984169689Skan Note that it is possible to stop the computation of the dependence 3985169689Skan relation the first time we detect a CHREC_KNOWN element for a given 3986169689Skan subscript. */ 3987169689Skan 3988169689Skanstatic void 3989169689Skancompute_affine_dependence (struct data_dependence_relation *ddr) 3990169689Skan{ 3991169689Skan struct data_reference *dra = DDR_A (ddr); 3992169689Skan struct data_reference *drb = DDR_B (ddr); 3993169689Skan 3994169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 3995169689Skan { 3996169689Skan fprintf (dump_file, "(compute_affine_dependence\n"); 3997169689Skan fprintf (dump_file, " (stmt_a = \n"); 3998169689Skan print_generic_expr (dump_file, DR_STMT (dra), 0); 3999169689Skan fprintf (dump_file, ")\n (stmt_b = \n"); 4000169689Skan print_generic_expr (dump_file, DR_STMT (drb), 0); 4001169689Skan fprintf (dump_file, ")\n"); 4002169689Skan } 4003169689Skan 4004169689Skan /* Analyze only when the dependence relation is not yet known. */ 4005169689Skan if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) 4006169689Skan { 4007169689Skan dependence_stats.num_dependence_tests++; 4008169689Skan 4009169689Skan if (access_functions_are_affine_or_constant_p (dra) 4010169689Skan && access_functions_are_affine_or_constant_p (drb)) 4011169689Skan subscript_dependence_tester (ddr); 4012169689Skan 4013169689Skan /* As a last case, if the dependence cannot be determined, or if 4014169689Skan the dependence is considered too difficult to determine, answer 4015169689Skan "don't know". */ 4016169689Skan else 4017169689Skan { 4018169689Skan dependence_stats.num_dependence_undetermined++; 4019169689Skan 4020169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4021169689Skan { 4022169689Skan fprintf (dump_file, "Data ref a:\n"); 4023169689Skan dump_data_reference (dump_file, dra); 4024169689Skan fprintf (dump_file, "Data ref b:\n"); 4025169689Skan dump_data_reference (dump_file, drb); 4026169689Skan fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n"); 4027169689Skan } 4028169689Skan finalize_ddr_dependent (ddr, chrec_dont_know); 4029169689Skan } 4030169689Skan } 4031169689Skan 4032169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 4033169689Skan fprintf (dump_file, ")\n"); 4034169689Skan} 4035169689Skan 4036169689Skan/* This computes the dependence relation for the same data 4037169689Skan reference into DDR. */ 4038169689Skan 4039169689Skanstatic void 4040169689Skancompute_self_dependence (struct data_dependence_relation *ddr) 4041169689Skan{ 4042169689Skan unsigned int i; 4043169689Skan struct subscript *subscript; 4044169689Skan 4045169689Skan for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript); 4046169689Skan i++) 4047169689Skan { 4048169689Skan /* The accessed index overlaps for each iteration. */ 4049169689Skan SUB_CONFLICTS_IN_A (subscript) = integer_zero_node; 4050169689Skan SUB_CONFLICTS_IN_B (subscript) = integer_zero_node; 4051169689Skan SUB_LAST_CONFLICT (subscript) = chrec_dont_know; 4052169689Skan } 4053169689Skan 4054169689Skan /* The distance vector is the zero vector. */ 4055169689Skan save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr))); 4056169689Skan save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr))); 4057169689Skan} 4058169689Skan 4059169689Skan/* Compute in DEPENDENCE_RELATIONS the data dependence graph for all 4060169689Skan the data references in DATAREFS, in the LOOP_NEST. When 4061169689Skan COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self 4062169689Skan relations. */ 4063169689Skan 4064169689Skanstatic void 4065169689Skancompute_all_dependences (VEC (data_reference_p, heap) *datarefs, 4066169689Skan VEC (ddr_p, heap) **dependence_relations, 4067169689Skan VEC (loop_p, heap) *loop_nest, 4068169689Skan bool compute_self_and_rr) 4069169689Skan{ 4070169689Skan struct data_dependence_relation *ddr; 4071169689Skan struct data_reference *a, *b; 4072169689Skan unsigned int i, j; 4073169689Skan 4074169689Skan for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++) 4075169689Skan for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++) 4076169689Skan if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr) 4077169689Skan { 4078169689Skan ddr = initialize_data_dependence_relation (a, b, loop_nest); 4079169689Skan VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); 4080169689Skan compute_affine_dependence (ddr); 4081169689Skan } 4082169689Skan 4083169689Skan if (compute_self_and_rr) 4084169689Skan for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++) 4085169689Skan { 4086169689Skan ddr = initialize_data_dependence_relation (a, a, loop_nest); 4087169689Skan VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); 4088169689Skan compute_self_dependence (ddr); 4089169689Skan } 4090169689Skan} 4091169689Skan 4092169689Skan/* Search the data references in LOOP, and record the information into 4093169689Skan DATAREFS. Returns chrec_dont_know when failing to analyze a 4094169689Skan difficult case, returns NULL_TREE otherwise. 4095169689Skan 4096169689Skan TODO: This function should be made smarter so that it can handle address 4097169689Skan arithmetic as if they were array accesses, etc. */ 4098169689Skan 4099169689Skantree 4100169689Skanfind_data_references_in_loop (struct loop *loop, 4101169689Skan VEC (data_reference_p, heap) **datarefs) 4102169689Skan{ 4103169689Skan basic_block bb, *bbs; 4104169689Skan unsigned int i; 4105169689Skan block_stmt_iterator bsi; 4106169689Skan struct data_reference *dr; 4107169689Skan 4108169689Skan bbs = get_loop_body (loop); 4109169689Skan 4110169689Skan for (i = 0; i < loop->num_nodes; i++) 4111169689Skan { 4112169689Skan bb = bbs[i]; 4113169689Skan 4114169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 4115169689Skan { 4116169689Skan tree stmt = bsi_stmt (bsi); 4117169689Skan 4118169689Skan /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects. 4119169689Skan Calls have side-effects, except those to const or pure 4120169689Skan functions. */ 4121169689Skan if ((TREE_CODE (stmt) == CALL_EXPR 4122169689Skan && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE))) 4123169689Skan || (TREE_CODE (stmt) == ASM_EXPR 4124169689Skan && ASM_VOLATILE_P (stmt))) 4125169689Skan goto insert_dont_know_node; 4126169689Skan 4127169689Skan if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) 4128169689Skan continue; 4129169689Skan 4130169689Skan switch (TREE_CODE (stmt)) 4131169689Skan { 4132169689Skan case MODIFY_EXPR: 4133169689Skan { 4134169689Skan bool one_inserted = false; 4135169689Skan tree opnd0 = TREE_OPERAND (stmt, 0); 4136169689Skan tree opnd1 = TREE_OPERAND (stmt, 1); 4137169689Skan 4138169689Skan if (TREE_CODE (opnd0) == ARRAY_REF 4139169689Skan || TREE_CODE (opnd0) == INDIRECT_REF 4140169689Skan || TREE_CODE (opnd0) == COMPONENT_REF) 4141169689Skan { 4142169689Skan dr = create_data_ref (opnd0, stmt, false); 4143169689Skan if (dr) 4144169689Skan { 4145169689Skan VEC_safe_push (data_reference_p, heap, *datarefs, dr); 4146169689Skan one_inserted = true; 4147169689Skan } 4148169689Skan } 4149169689Skan 4150169689Skan if (TREE_CODE (opnd1) == ARRAY_REF 4151169689Skan || TREE_CODE (opnd1) == INDIRECT_REF 4152169689Skan || TREE_CODE (opnd1) == COMPONENT_REF) 4153169689Skan { 4154169689Skan dr = create_data_ref (opnd1, stmt, true); 4155169689Skan if (dr) 4156169689Skan { 4157169689Skan VEC_safe_push (data_reference_p, heap, *datarefs, dr); 4158169689Skan one_inserted = true; 4159169689Skan } 4160169689Skan } 4161169689Skan 4162169689Skan if (!one_inserted) 4163169689Skan goto insert_dont_know_node; 4164169689Skan 4165169689Skan break; 4166169689Skan } 4167169689Skan 4168169689Skan case CALL_EXPR: 4169169689Skan { 4170169689Skan tree args; 4171169689Skan bool one_inserted = false; 4172169689Skan 4173169689Skan for (args = TREE_OPERAND (stmt, 1); args; 4174169689Skan args = TREE_CHAIN (args)) 4175169689Skan if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF 4176169689Skan || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF 4177169689Skan || TREE_CODE (TREE_VALUE (args)) == COMPONENT_REF) 4178169689Skan { 4179169689Skan dr = create_data_ref (TREE_VALUE (args), stmt, true); 4180169689Skan if (dr) 4181169689Skan { 4182169689Skan VEC_safe_push (data_reference_p, heap, *datarefs, dr); 4183169689Skan one_inserted = true; 4184169689Skan } 4185169689Skan } 4186169689Skan 4187169689Skan if (!one_inserted) 4188169689Skan goto insert_dont_know_node; 4189169689Skan 4190169689Skan break; 4191169689Skan } 4192169689Skan 4193169689Skan default: 4194169689Skan { 4195169689Skan struct data_reference *res; 4196169689Skan 4197169689Skan insert_dont_know_node:; 4198169689Skan res = XNEW (struct data_reference); 4199169689Skan DR_STMT (res) = NULL_TREE; 4200169689Skan DR_REF (res) = NULL_TREE; 4201169689Skan DR_BASE_OBJECT (res) = NULL; 4202169689Skan DR_TYPE (res) = ARRAY_REF_TYPE; 4203169689Skan DR_SET_ACCESS_FNS (res, NULL); 4204169689Skan DR_BASE_OBJECT (res) = NULL; 4205169689Skan DR_IS_READ (res) = false; 4206169689Skan DR_BASE_ADDRESS (res) = NULL_TREE; 4207169689Skan DR_OFFSET (res) = NULL_TREE; 4208169689Skan DR_INIT (res) = NULL_TREE; 4209169689Skan DR_STEP (res) = NULL_TREE; 4210169689Skan DR_OFFSET_MISALIGNMENT (res) = NULL_TREE; 4211169689Skan DR_MEMTAG (res) = NULL_TREE; 4212169689Skan DR_PTR_INFO (res) = NULL; 4213169689Skan VEC_safe_push (data_reference_p, heap, *datarefs, res); 4214169689Skan 4215169689Skan free (bbs); 4216169689Skan return chrec_dont_know; 4217169689Skan } 4218169689Skan } 4219169689Skan 4220169689Skan /* When there are no defs in the loop, the loop is parallel. */ 4221169689Skan if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 4222169689Skan loop->parallel_p = false; 4223169689Skan } 4224169689Skan } 4225169689Skan 4226169689Skan free (bbs); 4227169689Skan 4228169689Skan return NULL_TREE; 4229169689Skan} 4230169689Skan 4231169689Skan/* Recursive helper function. */ 4232169689Skan 4233169689Skanstatic bool 4234169689Skanfind_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest) 4235169689Skan{ 4236169689Skan /* Inner loops of the nest should not contain siblings. Example: 4237169689Skan when there are two consecutive loops, 4238169689Skan 4239169689Skan | loop_0 4240169689Skan | loop_1 4241169689Skan | A[{0, +, 1}_1] 4242169689Skan | endloop_1 4243169689Skan | loop_2 4244169689Skan | A[{0, +, 1}_2] 4245169689Skan | endloop_2 4246169689Skan | endloop_0 4247169689Skan 4248169689Skan the dependence relation cannot be captured by the distance 4249169689Skan abstraction. */ 4250169689Skan if (loop->next) 4251169689Skan return false; 4252169689Skan 4253169689Skan VEC_safe_push (loop_p, heap, *loop_nest, loop); 4254169689Skan if (loop->inner) 4255169689Skan return find_loop_nest_1 (loop->inner, loop_nest); 4256169689Skan return true; 4257169689Skan} 4258169689Skan 4259169689Skan/* Return false when the LOOP is not well nested. Otherwise return 4260169689Skan true and insert in LOOP_NEST the loops of the nest. LOOP_NEST will 4261169689Skan contain the loops from the outermost to the innermost, as they will 4262169689Skan appear in the classic distance vector. */ 4263169689Skan 4264169689Skanstatic bool 4265169689Skanfind_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest) 4266169689Skan{ 4267169689Skan VEC_safe_push (loop_p, heap, *loop_nest, loop); 4268169689Skan if (loop->inner) 4269169689Skan return find_loop_nest_1 (loop->inner, loop_nest); 4270169689Skan return true; 4271169689Skan} 4272169689Skan 4273169689Skan/* Given a loop nest LOOP, the following vectors are returned: 4274169689Skan DATAREFS is initialized to all the array elements contained in this loop, 4275169689Skan DEPENDENCE_RELATIONS contains the relations between the data references. 4276169689Skan Compute read-read and self relations if 4277169689Skan COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */ 4278169689Skan 4279169689Skanvoid 4280169689Skancompute_data_dependences_for_loop (struct loop *loop, 4281169689Skan bool compute_self_and_read_read_dependences, 4282169689Skan VEC (data_reference_p, heap) **datarefs, 4283169689Skan VEC (ddr_p, heap) **dependence_relations) 4284169689Skan{ 4285169689Skan struct loop *loop_nest = loop; 4286169689Skan VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3); 4287169689Skan 4288169689Skan memset (&dependence_stats, 0, sizeof (dependence_stats)); 4289169689Skan 4290169689Skan /* If the loop nest is not well formed, or one of the data references 4291169689Skan is not computable, give up without spending time to compute other 4292169689Skan dependences. */ 4293169689Skan if (!loop_nest 4294169689Skan || !find_loop_nest (loop_nest, &vloops) 4295169689Skan || find_data_references_in_loop (loop, datarefs) == chrec_dont_know) 4296169689Skan { 4297169689Skan struct data_dependence_relation *ddr; 4298169689Skan 4299169689Skan /* Insert a single relation into dependence_relations: 4300169689Skan chrec_dont_know. */ 4301169689Skan ddr = initialize_data_dependence_relation (NULL, NULL, vloops); 4302169689Skan VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); 4303169689Skan } 4304169689Skan else 4305169689Skan compute_all_dependences (*datarefs, dependence_relations, vloops, 4306169689Skan compute_self_and_read_read_dependences); 4307169689Skan 4308169689Skan if (dump_file && (dump_flags & TDF_STATS)) 4309169689Skan { 4310169689Skan fprintf (dump_file, "Dependence tester statistics:\n"); 4311169689Skan 4312169689Skan fprintf (dump_file, "Number of dependence tests: %d\n", 4313169689Skan dependence_stats.num_dependence_tests); 4314169689Skan fprintf (dump_file, "Number of dependence tests classified dependent: %d\n", 4315169689Skan dependence_stats.num_dependence_dependent); 4316169689Skan fprintf (dump_file, "Number of dependence tests classified independent: %d\n", 4317169689Skan dependence_stats.num_dependence_independent); 4318169689Skan fprintf (dump_file, "Number of undetermined dependence tests: %d\n", 4319169689Skan dependence_stats.num_dependence_undetermined); 4320169689Skan 4321169689Skan fprintf (dump_file, "Number of subscript tests: %d\n", 4322169689Skan dependence_stats.num_subscript_tests); 4323169689Skan fprintf (dump_file, "Number of undetermined subscript tests: %d\n", 4324169689Skan dependence_stats.num_subscript_undetermined); 4325169689Skan fprintf (dump_file, "Number of same subscript function: %d\n", 4326169689Skan dependence_stats.num_same_subscript_function); 4327169689Skan 4328169689Skan fprintf (dump_file, "Number of ziv tests: %d\n", 4329169689Skan dependence_stats.num_ziv); 4330169689Skan fprintf (dump_file, "Number of ziv tests returning dependent: %d\n", 4331169689Skan dependence_stats.num_ziv_dependent); 4332169689Skan fprintf (dump_file, "Number of ziv tests returning independent: %d\n", 4333169689Skan dependence_stats.num_ziv_independent); 4334169689Skan fprintf (dump_file, "Number of ziv tests unimplemented: %d\n", 4335169689Skan dependence_stats.num_ziv_unimplemented); 4336169689Skan 4337169689Skan fprintf (dump_file, "Number of siv tests: %d\n", 4338169689Skan dependence_stats.num_siv); 4339169689Skan fprintf (dump_file, "Number of siv tests returning dependent: %d\n", 4340169689Skan dependence_stats.num_siv_dependent); 4341169689Skan fprintf (dump_file, "Number of siv tests returning independent: %d\n", 4342169689Skan dependence_stats.num_siv_independent); 4343169689Skan fprintf (dump_file, "Number of siv tests unimplemented: %d\n", 4344169689Skan dependence_stats.num_siv_unimplemented); 4345169689Skan 4346169689Skan fprintf (dump_file, "Number of miv tests: %d\n", 4347169689Skan dependence_stats.num_miv); 4348169689Skan fprintf (dump_file, "Number of miv tests returning dependent: %d\n", 4349169689Skan dependence_stats.num_miv_dependent); 4350169689Skan fprintf (dump_file, "Number of miv tests returning independent: %d\n", 4351169689Skan dependence_stats.num_miv_independent); 4352169689Skan fprintf (dump_file, "Number of miv tests unimplemented: %d\n", 4353169689Skan dependence_stats.num_miv_unimplemented); 4354169689Skan } 4355169689Skan} 4356169689Skan 4357169689Skan/* Entry point (for testing only). Analyze all the data references 4358169689Skan and the dependence relations. 4359169689Skan 4360169689Skan The data references are computed first. 4361169689Skan 4362169689Skan A relation on these nodes is represented by a complete graph. Some 4363169689Skan of the relations could be of no interest, thus the relations can be 4364169689Skan computed on demand. 4365169689Skan 4366169689Skan In the following function we compute all the relations. This is 4367169689Skan just a first implementation that is here for: 4368169689Skan - for showing how to ask for the dependence relations, 4369169689Skan - for the debugging the whole dependence graph, 4370169689Skan - for the dejagnu testcases and maintenance. 4371169689Skan 4372169689Skan It is possible to ask only for a part of the graph, avoiding to 4373169689Skan compute the whole dependence graph. The computed dependences are 4374169689Skan stored in a knowledge base (KB) such that later queries don't 4375169689Skan recompute the same information. The implementation of this KB is 4376169689Skan transparent to the optimizer, and thus the KB can be changed with a 4377169689Skan more efficient implementation, or the KB could be disabled. */ 4378169689Skan#if 0 4379169689Skanstatic void 4380169689Skananalyze_all_data_dependences (struct loops *loops) 4381169689Skan{ 4382169689Skan unsigned int i; 4383169689Skan int nb_data_refs = 10; 4384169689Skan VEC (data_reference_p, heap) *datarefs = 4385169689Skan VEC_alloc (data_reference_p, heap, nb_data_refs); 4386169689Skan VEC (ddr_p, heap) *dependence_relations = 4387169689Skan VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs); 4388169689Skan 4389169689Skan /* Compute DDs on the whole function. */ 4390169689Skan compute_data_dependences_for_loop (loops->parray[0], false, 4391169689Skan &datarefs, &dependence_relations); 4392169689Skan 4393169689Skan if (dump_file) 4394169689Skan { 4395169689Skan dump_data_dependence_relations (dump_file, dependence_relations); 4396169689Skan fprintf (dump_file, "\n\n"); 4397169689Skan 4398169689Skan if (dump_flags & TDF_DETAILS) 4399169689Skan dump_dist_dir_vectors (dump_file, dependence_relations); 4400169689Skan 4401169689Skan if (dump_flags & TDF_STATS) 4402169689Skan { 4403169689Skan unsigned nb_top_relations = 0; 4404169689Skan unsigned nb_bot_relations = 0; 4405169689Skan unsigned nb_basename_differ = 0; 4406169689Skan unsigned nb_chrec_relations = 0; 4407169689Skan struct data_dependence_relation *ddr; 4408169689Skan 4409169689Skan for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) 4410169689Skan { 4411169689Skan if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr))) 4412169689Skan nb_top_relations++; 4413169689Skan 4414169689Skan else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) 4415169689Skan { 4416169689Skan struct data_reference *a = DDR_A (ddr); 4417169689Skan struct data_reference *b = DDR_B (ddr); 4418169689Skan bool differ_p; 4419169689Skan 4420169689Skan if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b) 4421169689Skan && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)) 4422169689Skan || (base_object_differ_p (a, b, &differ_p) 4423169689Skan && differ_p)) 4424169689Skan nb_basename_differ++; 4425169689Skan else 4426169689Skan nb_bot_relations++; 4427169689Skan } 4428169689Skan 4429169689Skan else 4430169689Skan nb_chrec_relations++; 4431169689Skan } 4432169689Skan 4433169689Skan gather_stats_on_scev_database (); 4434169689Skan } 4435169689Skan } 4436169689Skan 4437169689Skan free_dependence_relations (dependence_relations); 4438169689Skan free_data_refs (datarefs); 4439169689Skan} 4440169689Skan#endif 4441169689Skan 4442169689Skan/* Free the memory used by a data dependence relation DDR. */ 4443169689Skan 4444169689Skanvoid 4445169689Skanfree_dependence_relation (struct data_dependence_relation *ddr) 4446169689Skan{ 4447169689Skan if (ddr == NULL) 4448169689Skan return; 4449169689Skan 4450169689Skan if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr)) 4451169689Skan VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr)); 4452169689Skan 4453169689Skan free (ddr); 4454169689Skan} 4455169689Skan 4456169689Skan/* Free the memory used by the data dependence relations from 4457169689Skan DEPENDENCE_RELATIONS. */ 4458169689Skan 4459169689Skanvoid 4460169689Skanfree_dependence_relations (VEC (ddr_p, heap) *dependence_relations) 4461169689Skan{ 4462169689Skan unsigned int i; 4463169689Skan struct data_dependence_relation *ddr; 4464169689Skan VEC (loop_p, heap) *loop_nest = NULL; 4465169689Skan 4466169689Skan for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) 4467169689Skan { 4468169689Skan if (ddr == NULL) 4469169689Skan continue; 4470169689Skan if (loop_nest == NULL) 4471169689Skan loop_nest = DDR_LOOP_NEST (ddr); 4472169689Skan else 4473169689Skan gcc_assert (DDR_LOOP_NEST (ddr) == NULL 4474169689Skan || DDR_LOOP_NEST (ddr) == loop_nest); 4475169689Skan free_dependence_relation (ddr); 4476169689Skan } 4477169689Skan 4478169689Skan if (loop_nest) 4479169689Skan VEC_free (loop_p, heap, loop_nest); 4480169689Skan VEC_free (ddr_p, heap, dependence_relations); 4481169689Skan} 4482169689Skan 4483169689Skan/* Free the memory used by the data references from DATAREFS. */ 4484169689Skan 4485169689Skanvoid 4486169689Skanfree_data_refs (VEC (data_reference_p, heap) *datarefs) 4487169689Skan{ 4488169689Skan unsigned int i; 4489169689Skan struct data_reference *dr; 4490169689Skan 4491169689Skan for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 4492169689Skan free_data_ref (dr); 4493169689Skan VEC_free (data_reference_p, heap, datarefs); 4494169689Skan} 4495169689Skan 4496