1 /* Data references and dependences detectors. 2 Copyright (C) 2003-2017 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #ifndef GCC_TREE_DATA_REF_H 22 #define GCC_TREE_DATA_REF_H 23 24 #include "graphds.h" 25 #include "tree-chrec.h" 26 27 /* 28 innermost_loop_behavior describes the evolution of the address of the memory 29 reference in the innermost enclosing loop. The address is expressed as 30 BASE + STEP * # of iteration, and base is further decomposed as the base 31 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and 32 constant offset (INIT). Examples, in loop nest 33 34 for (i = 0; i < 100; i++) 35 for (j = 3; j < 100; j++) 36 37 Example 1 Example 2 38 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j) 39 40 41 innermost_loop_behavior 42 base_address &a p 43 offset i * D_i x 44 init 3 * D_j + offsetof (b) 28 45 step D_j 4 46 47 */ 48 struct innermost_loop_behavior 49 { 50 tree base_address; 51 tree offset; 52 tree init; 53 tree step; 54 55 /* Alignment information. ALIGNED_TO is set to the largest power of two 56 that divides OFFSET. */ 57 tree aligned_to; 58 }; 59 60 /* Describes the evolutions of indices of the memory reference. The indices 61 are indices of the ARRAY_REFs, indexes in artificial dimensions 62 added for member selection of records and the operands of MEM_REFs. 63 BASE_OBJECT is the part of the reference that is loop-invariant 64 (note that this reference does not have to cover the whole object 65 being accessed, in which case UNCONSTRAINED_BASE is set; hence it is 66 not recommended to use BASE_OBJECT in any code generation). 67 For the examples above, 68 69 base_object: a *(p + x + 4B * j_0) 70 indices: {j_0, +, 1}_2 {16, +, 4}_2 71 4 72 {i_0, +, 1}_1 73 {j_0, +, 1}_2 74 */ 75 76 struct indices 77 { 78 /* The object. */ 79 tree base_object; 80 81 /* A list of chrecs. Access functions of the indices. */ 82 vec<tree> access_fns; 83 84 /* Whether BASE_OBJECT is an access representing the whole object 85 or whether the access could not be constrained. */ 86 bool unconstrained_base; 87 }; 88 89 struct dr_alias 90 { 91 /* The alias information that should be used for new pointers to this 92 location. */ 93 struct ptr_info_def *ptr_info; 94 }; 95 96 /* An integer vector. A vector formally consists of an element of a vector 97 space. A vector space is a set that is closed under vector addition 98 and scalar multiplication. In this vector space, an element is a list of 99 integers. */ 100 typedef int *lambda_vector; 101 102 /* An integer matrix. A matrix consists of m vectors of length n (IE 103 all vectors are the same length). */ 104 typedef lambda_vector *lambda_matrix; 105 106 107 108 struct data_reference 109 { 110 /* A pointer to the statement that contains this DR. */ 111 gimple *stmt; 112 113 /* A pointer to the memory reference. */ 114 tree ref; 115 116 /* Auxiliary info specific to a pass. */ 117 void *aux; 118 119 /* True when the data reference is in RHS of a stmt. */ 120 bool is_read; 121 122 /* Behavior of the memory reference in the innermost loop. */ 123 struct innermost_loop_behavior innermost; 124 125 /* Subscripts of this data reference. */ 126 struct indices indices; 127 128 /* Alias information for the data reference. */ 129 struct dr_alias alias; 130 }; 131 132 #define DR_STMT(DR) (DR)->stmt 133 #define DR_REF(DR) (DR)->ref 134 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object 135 #define DR_UNCONSTRAINED_BASE(DR) (DR)->indices.unconstrained_base 136 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns 137 #define DR_ACCESS_FN(DR, I) DR_ACCESS_FNS (DR)[I] 138 #define DR_NUM_DIMENSIONS(DR) DR_ACCESS_FNS (DR).length () 139 #define DR_IS_READ(DR) (DR)->is_read 140 #define DR_IS_WRITE(DR) (!DR_IS_READ (DR)) 141 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address 142 #define DR_OFFSET(DR) (DR)->innermost.offset 143 #define DR_INIT(DR) (DR)->innermost.init 144 #define DR_STEP(DR) (DR)->innermost.step 145 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info 146 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to 147 #define DR_INNERMOST(DR) (DR)->innermost 148 149 typedef struct data_reference *data_reference_p; 150 151 enum data_dependence_direction { 152 dir_positive, 153 dir_negative, 154 dir_equal, 155 dir_positive_or_negative, 156 dir_positive_or_equal, 157 dir_negative_or_equal, 158 dir_star, 159 dir_independent 160 }; 161 162 /* The description of the grid of iterations that overlap. At most 163 two loops are considered at the same time just now, hence at most 164 two functions are needed. For each of the functions, we store 165 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ..., 166 where x, y, ... are variables. */ 167 168 #define MAX_DIM 2 169 170 /* Special values of N. */ 171 #define NO_DEPENDENCE 0 172 #define NOT_KNOWN (MAX_DIM + 1) 173 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN) 174 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN) 175 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE) 176 177 typedef vec<tree> affine_fn; 178 179 struct conflict_function 180 { 181 unsigned n; 182 affine_fn fns[MAX_DIM]; 183 }; 184 185 /* What is a subscript? Given two array accesses a subscript is the 186 tuple composed of the access functions for a given dimension. 187 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three 188 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts 189 are stored in the data_dependence_relation structure under the form 190 of an array of subscripts. */ 191 192 struct subscript 193 { 194 /* A description of the iterations for which the elements are 195 accessed twice. */ 196 conflict_function *conflicting_iterations_in_a; 197 conflict_function *conflicting_iterations_in_b; 198 199 /* This field stores the information about the iteration domain 200 validity of the dependence relation. */ 201 tree last_conflict; 202 203 /* Distance from the iteration that access a conflicting element in 204 A to the iteration that access this same conflicting element in 205 B. The distance is a tree scalar expression, i.e. a constant or a 206 symbolic expression, but certainly not a chrec function. */ 207 tree distance; 208 }; 209 210 typedef struct subscript *subscript_p; 211 212 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a 213 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b 214 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict 215 #define SUB_DISTANCE(SUB) SUB->distance 216 217 /* A data_dependence_relation represents a relation between two 218 data_references A and B. */ 219 220 struct data_dependence_relation 221 { 222 223 struct data_reference *a; 224 struct data_reference *b; 225 226 /* A "yes/no/maybe" field for the dependence relation: 227 228 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 229 relation between A and B, and the description of this relation 230 is given in the SUBSCRIPTS array, 231 232 - when "ARE_DEPENDENT == chrec_known", there is no dependence and 233 SUBSCRIPTS is empty, 234 235 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 236 but the analyzer cannot be more specific. */ 237 tree are_dependent; 238 239 /* For each subscript in the dependence test, there is an element in 240 this array. This is the attribute that labels the edge A->B of 241 the data_dependence_relation. */ 242 vec<subscript_p> subscripts; 243 244 /* The analyzed loop nest. */ 245 vec<loop_p> loop_nest; 246 247 /* The classic direction vector. */ 248 vec<lambda_vector> dir_vects; 249 250 /* The classic distance vector. */ 251 vec<lambda_vector> dist_vects; 252 253 /* An index in loop_nest for the innermost loop that varies for 254 this data dependence relation. */ 255 unsigned inner_loop; 256 257 /* Is the dependence reversed with respect to the lexicographic order? */ 258 bool reversed_p; 259 260 /* When the dependence relation is affine, it can be represented by 261 a distance vector. */ 262 bool affine_p; 263 264 /* Set to true when the dependence relation is on the same data 265 access. */ 266 bool self_reference_p; 267 }; 268 269 typedef struct data_dependence_relation *ddr_p; 270 271 #define DDR_A(DDR) DDR->a 272 #define DDR_B(DDR) DDR->b 273 #define DDR_AFFINE_P(DDR) DDR->affine_p 274 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent 275 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts 276 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I] 277 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length () 278 279 #define DDR_LOOP_NEST(DDR) DDR->loop_nest 280 /* The size of the direction/distance vectors: the number of loops in 281 the loop nest. */ 282 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ()) 283 #define DDR_INNER_LOOP(DDR) DDR->inner_loop 284 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p 285 286 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) 287 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) 288 #define DDR_NUM_DIST_VECTS(DDR) \ 289 (DDR_DIST_VECTS (DDR).length ()) 290 #define DDR_NUM_DIR_VECTS(DDR) \ 291 (DDR_DIR_VECTS (DDR).length ()) 292 #define DDR_DIR_VECT(DDR, I) \ 293 DDR_DIR_VECTS (DDR)[I] 294 #define DDR_DIST_VECT(DDR, I) \ 295 DDR_DIST_VECTS (DDR)[I] 296 #define DDR_REVERSED_P(DDR) DDR->reversed_p 297 298 299 bool dr_analyze_innermost (struct data_reference *, struct loop *); 300 extern bool compute_data_dependences_for_loop (struct loop *, bool, 301 vec<loop_p> *, 302 vec<data_reference_p> *, 303 vec<ddr_p> *); 304 extern void debug_ddrs (vec<ddr_p> ); 305 extern void dump_data_reference (FILE *, struct data_reference *); 306 extern void debug (data_reference &ref); 307 extern void debug (data_reference *ptr); 308 extern void debug_data_reference (struct data_reference *); 309 extern void debug_data_references (vec<data_reference_p> ); 310 extern void debug (vec<data_reference_p> &ref); 311 extern void debug (vec<data_reference_p> *ptr); 312 extern void debug_data_dependence_relation (struct data_dependence_relation *); 313 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> ); 314 extern void debug (vec<ddr_p> &ref); 315 extern void debug (vec<ddr_p> *ptr); 316 extern void debug_data_dependence_relations (vec<ddr_p> ); 317 extern void free_dependence_relation (struct data_dependence_relation *); 318 extern void free_dependence_relations (vec<ddr_p> ); 319 extern void free_data_ref (data_reference_p); 320 extern void free_data_refs (vec<data_reference_p> ); 321 extern bool find_data_references_in_stmt (struct loop *, gimple *, 322 vec<data_reference_p> *); 323 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple *, 324 vec<data_reference_p> *); 325 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *); 326 bool loop_nest_has_data_refs (loop_p loop); 327 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool); 328 extern bool find_loop_nest (struct loop *, vec<loop_p> *); 329 extern struct data_dependence_relation *initialize_data_dependence_relation 330 (struct data_reference *, struct data_reference *, vec<loop_p>); 331 extern void compute_affine_dependence (struct data_dependence_relation *, 332 loop_p); 333 extern void compute_self_dependence (struct data_dependence_relation *); 334 extern bool compute_all_dependences (vec<data_reference_p> , 335 vec<ddr_p> *, 336 vec<loop_p>, bool); 337 extern tree find_data_references_in_bb (struct loop *, basic_block, 338 vec<data_reference_p> *); 339 340 extern bool dr_may_alias_p (const struct data_reference *, 341 const struct data_reference *, bool); 342 extern bool dr_equal_offsets_p (struct data_reference *, 343 struct data_reference *); 344 345 /* Return true when the base objects of data references A and B are 346 the same memory object. */ 347 348 static inline bool 349 same_data_refs_base_objects (data_reference_p a, data_reference_p b) 350 { 351 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b) 352 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0); 353 } 354 355 /* Return true when the data references A and B are accessing the same 356 memory object with the same access functions. */ 357 358 static inline bool 359 same_data_refs (data_reference_p a, data_reference_p b) 360 { 361 unsigned int i; 362 363 /* The references are exactly the same. */ 364 if (operand_equal_p (DR_REF (a), DR_REF (b), 0)) 365 return true; 366 367 if (!same_data_refs_base_objects (a, b)) 368 return false; 369 370 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) 371 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i))) 372 return false; 373 374 return true; 375 } 376 377 /* Return true when the DDR contains two data references that have the 378 same access functions. */ 379 380 static inline bool 381 same_access_functions (const struct data_dependence_relation *ddr) 382 { 383 unsigned i; 384 385 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 386 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), 387 DR_ACCESS_FN (DDR_B (ddr), i))) 388 return false; 389 390 return true; 391 } 392 393 /* Returns true when all the dependences are computable. */ 394 395 inline bool 396 known_dependences_p (vec<ddr_p> dependence_relations) 397 { 398 ddr_p ddr; 399 unsigned int i; 400 401 FOR_EACH_VEC_ELT (dependence_relations, i, ddr) 402 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) 403 return false; 404 405 return true; 406 } 407 408 /* Returns the dependence level for a vector DIST of size LENGTH. 409 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due 410 to the sequence of statements, not carried by any loop. */ 411 412 static inline unsigned 413 dependence_level (lambda_vector dist_vect, int length) 414 { 415 int i; 416 417 for (i = 0; i < length; i++) 418 if (dist_vect[i] != 0) 419 return i + 1; 420 421 return 0; 422 } 423 424 /* Return the dependence level for the DDR relation. */ 425 426 static inline unsigned 427 ddr_dependence_level (ddr_p ddr) 428 { 429 unsigned vector; 430 unsigned level = 0; 431 432 if (DDR_DIST_VECTS (ddr).exists ()) 433 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)); 434 435 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++) 436 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector), 437 DDR_NB_LOOPS (ddr))); 438 return level; 439 } 440 441 /* Return the index of the variable VAR in the LOOP_NEST array. */ 442 443 static inline int 444 index_in_loop_nest (int var, vec<loop_p> loop_nest) 445 { 446 struct loop *loopi; 447 int var_index; 448 449 for (var_index = 0; loop_nest.iterate (var_index, &loopi); 450 var_index++) 451 if (loopi->num == var) 452 break; 453 454 return var_index; 455 } 456 457 /* Returns true when the data reference DR the form "A[i] = ..." 458 with a stride equal to its unit type size. */ 459 460 static inline bool 461 adjacent_dr_p (struct data_reference *dr) 462 { 463 /* If this is a bitfield store bail out. */ 464 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF 465 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1))) 466 return false; 467 468 if (!DR_STEP (dr) 469 || TREE_CODE (DR_STEP (dr)) != INTEGER_CST) 470 return false; 471 472 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)), 473 DR_STEP (dr)), 474 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); 475 } 476 477 void split_constant_offset (tree , tree *, tree *); 478 479 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */ 480 481 static inline int 482 lambda_vector_gcd (lambda_vector vector, int size) 483 { 484 int i; 485 int gcd1 = 0; 486 487 if (size > 0) 488 { 489 gcd1 = vector[0]; 490 for (i = 1; i < size; i++) 491 gcd1 = gcd (gcd1, vector[i]); 492 } 493 return gcd1; 494 } 495 496 /* Allocate a new vector of given SIZE. */ 497 498 static inline lambda_vector 499 lambda_vector_new (int size) 500 { 501 /* ??? We shouldn't abuse the GC allocator here. */ 502 return ggc_cleared_vec_alloc<int> (size); 503 } 504 505 /* Clear out vector VEC1 of length SIZE. */ 506 507 static inline void 508 lambda_vector_clear (lambda_vector vec1, int size) 509 { 510 memset (vec1, 0, size * sizeof (*vec1)); 511 } 512 513 /* Returns true when the vector V is lexicographically positive, in 514 other words, when the first nonzero element is positive. */ 515 516 static inline bool 517 lambda_vector_lexico_pos (lambda_vector v, 518 unsigned n) 519 { 520 unsigned i; 521 for (i = 0; i < n; i++) 522 { 523 if (v[i] == 0) 524 continue; 525 if (v[i] < 0) 526 return false; 527 if (v[i] > 0) 528 return true; 529 } 530 return true; 531 } 532 533 /* Return true if vector VEC1 of length SIZE is the zero vector. */ 534 535 static inline bool 536 lambda_vector_zerop (lambda_vector vec1, int size) 537 { 538 int i; 539 for (i = 0; i < size; i++) 540 if (vec1[i] != 0) 541 return false; 542 return true; 543 } 544 545 /* Allocate a matrix of M rows x N cols. */ 546 547 static inline lambda_matrix 548 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack) 549 { 550 lambda_matrix mat; 551 int i; 552 553 mat = XOBNEWVEC (lambda_obstack, lambda_vector, m); 554 555 for (i = 0; i < m; i++) 556 mat[i] = XOBNEWVEC (lambda_obstack, int, n); 557 558 return mat; 559 } 560 561 #endif /* GCC_TREE_DATA_REF_H */ 562