1 /* Data references and dependences detectors. 2 Copyright (C) 2003-2016 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 148 typedef struct data_reference *data_reference_p; 149 150 enum data_dependence_direction { 151 dir_positive, 152 dir_negative, 153 dir_equal, 154 dir_positive_or_negative, 155 dir_positive_or_equal, 156 dir_negative_or_equal, 157 dir_star, 158 dir_independent 159 }; 160 161 /* The description of the grid of iterations that overlap. At most 162 two loops are considered at the same time just now, hence at most 163 two functions are needed. For each of the functions, we store 164 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ..., 165 where x, y, ... are variables. */ 166 167 #define MAX_DIM 2 168 169 /* Special values of N. */ 170 #define NO_DEPENDENCE 0 171 #define NOT_KNOWN (MAX_DIM + 1) 172 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN) 173 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN) 174 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE) 175 176 typedef vec<tree> affine_fn; 177 178 struct conflict_function 179 { 180 unsigned n; 181 affine_fn fns[MAX_DIM]; 182 }; 183 184 /* What is a subscript? Given two array accesses a subscript is the 185 tuple composed of the access functions for a given dimension. 186 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three 187 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts 188 are stored in the data_dependence_relation structure under the form 189 of an array of subscripts. */ 190 191 struct subscript 192 { 193 /* A description of the iterations for which the elements are 194 accessed twice. */ 195 conflict_function *conflicting_iterations_in_a; 196 conflict_function *conflicting_iterations_in_b; 197 198 /* This field stores the information about the iteration domain 199 validity of the dependence relation. */ 200 tree last_conflict; 201 202 /* Distance from the iteration that access a conflicting element in 203 A to the iteration that access this same conflicting element in 204 B. The distance is a tree scalar expression, i.e. a constant or a 205 symbolic expression, but certainly not a chrec function. */ 206 tree distance; 207 }; 208 209 typedef struct subscript *subscript_p; 210 211 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a 212 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b 213 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict 214 #define SUB_DISTANCE(SUB) SUB->distance 215 216 /* A data_dependence_relation represents a relation between two 217 data_references A and B. */ 218 219 struct data_dependence_relation 220 { 221 222 struct data_reference *a; 223 struct data_reference *b; 224 225 /* A "yes/no/maybe" field for the dependence relation: 226 227 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 228 relation between A and B, and the description of this relation 229 is given in the SUBSCRIPTS array, 230 231 - when "ARE_DEPENDENT == chrec_known", there is no dependence and 232 SUBSCRIPTS is empty, 233 234 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 235 but the analyzer cannot be more specific. */ 236 tree are_dependent; 237 238 /* For each subscript in the dependence test, there is an element in 239 this array. This is the attribute that labels the edge A->B of 240 the data_dependence_relation. */ 241 vec<subscript_p> subscripts; 242 243 /* The analyzed loop nest. */ 244 vec<loop_p> loop_nest; 245 246 /* The classic direction vector. */ 247 vec<lambda_vector> dir_vects; 248 249 /* The classic distance vector. */ 250 vec<lambda_vector> dist_vects; 251 252 /* An index in loop_nest for the innermost loop that varies for 253 this data dependence relation. */ 254 unsigned inner_loop; 255 256 /* Is the dependence reversed with respect to the lexicographic order? */ 257 bool reversed_p; 258 259 /* When the dependence relation is affine, it can be represented by 260 a distance vector. */ 261 bool affine_p; 262 263 /* Set to true when the dependence relation is on the same data 264 access. */ 265 bool self_reference_p; 266 }; 267 268 typedef struct data_dependence_relation *ddr_p; 269 270 #define DDR_A(DDR) DDR->a 271 #define DDR_B(DDR) DDR->b 272 #define DDR_AFFINE_P(DDR) DDR->affine_p 273 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent 274 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts 275 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I] 276 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length () 277 278 #define DDR_LOOP_NEST(DDR) DDR->loop_nest 279 /* The size of the direction/distance vectors: the number of loops in 280 the loop nest. */ 281 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ()) 282 #define DDR_INNER_LOOP(DDR) DDR->inner_loop 283 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p 284 285 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) 286 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) 287 #define DDR_NUM_DIST_VECTS(DDR) \ 288 (DDR_DIST_VECTS (DDR).length ()) 289 #define DDR_NUM_DIR_VECTS(DDR) \ 290 (DDR_DIR_VECTS (DDR).length ()) 291 #define DDR_DIR_VECT(DDR, I) \ 292 DDR_DIR_VECTS (DDR)[I] 293 #define DDR_DIST_VECT(DDR, I) \ 294 DDR_DIST_VECTS (DDR)[I] 295 #define DDR_REVERSED_P(DDR) DDR->reversed_p 296 297 298 bool dr_analyze_innermost (struct data_reference *, struct loop *); 299 extern bool compute_data_dependences_for_loop (struct loop *, bool, 300 vec<loop_p> *, 301 vec<data_reference_p> *, 302 vec<ddr_p> *); 303 extern void debug_ddrs (vec<ddr_p> ); 304 extern void dump_data_reference (FILE *, struct data_reference *); 305 extern void debug (data_reference &ref); 306 extern void debug (data_reference *ptr); 307 extern void debug_data_reference (struct data_reference *); 308 extern void debug_data_references (vec<data_reference_p> ); 309 extern void debug (vec<data_reference_p> &ref); 310 extern void debug (vec<data_reference_p> *ptr); 311 extern void debug_data_dependence_relation (struct data_dependence_relation *); 312 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> ); 313 extern void debug (vec<ddr_p> &ref); 314 extern void debug (vec<ddr_p> *ptr); 315 extern void debug_data_dependence_relations (vec<ddr_p> ); 316 extern void free_dependence_relation (struct data_dependence_relation *); 317 extern void free_dependence_relations (vec<ddr_p> ); 318 extern void free_data_ref (data_reference_p); 319 extern void free_data_refs (vec<data_reference_p> ); 320 extern bool find_data_references_in_stmt (struct loop *, gimple *, 321 vec<data_reference_p> *); 322 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple *, 323 vec<data_reference_p> *); 324 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *); 325 bool loop_nest_has_data_refs (loop_p loop); 326 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple *, bool); 327 extern bool find_loop_nest (struct loop *, vec<loop_p> *); 328 extern struct data_dependence_relation *initialize_data_dependence_relation 329 (struct data_reference *, struct data_reference *, vec<loop_p>); 330 extern void compute_affine_dependence (struct data_dependence_relation *, 331 loop_p); 332 extern void compute_self_dependence (struct data_dependence_relation *); 333 extern bool compute_all_dependences (vec<data_reference_p> , 334 vec<ddr_p> *, 335 vec<loop_p>, bool); 336 extern tree find_data_references_in_bb (struct loop *, basic_block, 337 vec<data_reference_p> *); 338 339 extern bool dr_may_alias_p (const struct data_reference *, 340 const struct data_reference *, bool); 341 extern bool dr_equal_offsets_p (struct data_reference *, 342 struct data_reference *); 343 344 /* Return true when the base objects of data references A and B are 345 the same memory object. */ 346 347 static inline bool 348 same_data_refs_base_objects (data_reference_p a, data_reference_p b) 349 { 350 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b) 351 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0); 352 } 353 354 /* Return true when the data references A and B are accessing the same 355 memory object with the same access functions. */ 356 357 static inline bool 358 same_data_refs (data_reference_p a, data_reference_p b) 359 { 360 unsigned int i; 361 362 /* The references are exactly the same. */ 363 if (operand_equal_p (DR_REF (a), DR_REF (b), 0)) 364 return true; 365 366 if (!same_data_refs_base_objects (a, b)) 367 return false; 368 369 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) 370 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i))) 371 return false; 372 373 return true; 374 } 375 376 /* Return true when the DDR contains two data references that have the 377 same access functions. */ 378 379 static inline bool 380 same_access_functions (const struct data_dependence_relation *ddr) 381 { 382 unsigned i; 383 384 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 385 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), 386 DR_ACCESS_FN (DDR_B (ddr), i))) 387 return false; 388 389 return true; 390 } 391 392 /* Returns true when all the dependences are computable. */ 393 394 inline bool 395 known_dependences_p (vec<ddr_p> dependence_relations) 396 { 397 ddr_p ddr; 398 unsigned int i; 399 400 FOR_EACH_VEC_ELT (dependence_relations, i, ddr) 401 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) 402 return false; 403 404 return true; 405 } 406 407 /* Returns the dependence level for a vector DIST of size LENGTH. 408 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due 409 to the sequence of statements, not carried by any loop. */ 410 411 static inline unsigned 412 dependence_level (lambda_vector dist_vect, int length) 413 { 414 int i; 415 416 for (i = 0; i < length; i++) 417 if (dist_vect[i] != 0) 418 return i + 1; 419 420 return 0; 421 } 422 423 /* Return the dependence level for the DDR relation. */ 424 425 static inline unsigned 426 ddr_dependence_level (ddr_p ddr) 427 { 428 unsigned vector; 429 unsigned level = 0; 430 431 if (DDR_DIST_VECTS (ddr).exists ()) 432 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)); 433 434 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++) 435 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector), 436 DDR_NB_LOOPS (ddr))); 437 return level; 438 } 439 440 /* Return the index of the variable VAR in the LOOP_NEST array. */ 441 442 static inline int 443 index_in_loop_nest (int var, vec<loop_p> loop_nest) 444 { 445 struct loop *loopi; 446 int var_index; 447 448 for (var_index = 0; loop_nest.iterate (var_index, &loopi); 449 var_index++) 450 if (loopi->num == var) 451 break; 452 453 return var_index; 454 } 455 456 /* Returns true when the data reference DR the form "A[i] = ..." 457 with a stride equal to its unit type size. */ 458 459 static inline bool 460 adjacent_dr_p (struct data_reference *dr) 461 { 462 /* If this is a bitfield store bail out. */ 463 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF 464 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1))) 465 return false; 466 467 if (!DR_STEP (dr) 468 || TREE_CODE (DR_STEP (dr)) != INTEGER_CST) 469 return false; 470 471 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)), 472 DR_STEP (dr)), 473 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); 474 } 475 476 void split_constant_offset (tree , tree *, tree *); 477 478 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */ 479 480 static inline int 481 lambda_vector_gcd (lambda_vector vector, int size) 482 { 483 int i; 484 int gcd1 = 0; 485 486 if (size > 0) 487 { 488 gcd1 = vector[0]; 489 for (i = 1; i < size; i++) 490 gcd1 = gcd (gcd1, vector[i]); 491 } 492 return gcd1; 493 } 494 495 /* Allocate a new vector of given SIZE. */ 496 497 static inline lambda_vector 498 lambda_vector_new (int size) 499 { 500 /* ??? We shouldn't abuse the GC allocator here. */ 501 return ggc_cleared_vec_alloc<int> (size); 502 } 503 504 /* Clear out vector VEC1 of length SIZE. */ 505 506 static inline void 507 lambda_vector_clear (lambda_vector vec1, int size) 508 { 509 memset (vec1, 0, size * sizeof (*vec1)); 510 } 511 512 /* Returns true when the vector V is lexicographically positive, in 513 other words, when the first nonzero element is positive. */ 514 515 static inline bool 516 lambda_vector_lexico_pos (lambda_vector v, 517 unsigned n) 518 { 519 unsigned i; 520 for (i = 0; i < n; i++) 521 { 522 if (v[i] == 0) 523 continue; 524 if (v[i] < 0) 525 return false; 526 if (v[i] > 0) 527 return true; 528 } 529 return true; 530 } 531 532 /* Return true if vector VEC1 of length SIZE is the zero vector. */ 533 534 static inline bool 535 lambda_vector_zerop (lambda_vector vec1, int size) 536 { 537 int i; 538 for (i = 0; i < size; i++) 539 if (vec1[i] != 0) 540 return false; 541 return true; 542 } 543 544 /* Allocate a matrix of M rows x N cols. */ 545 546 static inline lambda_matrix 547 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack) 548 { 549 lambda_matrix mat; 550 int i; 551 552 mat = XOBNEWVEC (lambda_obstack, lambda_vector, m); 553 554 for (i = 0; i < m; i++) 555 mat[i] = XOBNEWVEC (lambda_obstack, int, n); 556 557 return mat; 558 } 559 560 #endif /* GCC_TREE_DATA_REF_H */ 561