1/* Data references and dependences detectors. 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 3 Free Software Foundation, Inc. 4 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 3, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22#ifndef GCC_TREE_DATA_REF_H 23#define GCC_TREE_DATA_REF_H 24 25#include "graphds.h" 26#include "lambda.h" 27#include "omega.h" 28#include "tree-chrec.h" 29 30/* 31 innermost_loop_behavior describes the evolution of the address of the memory 32 reference in the innermost enclosing loop. The address is expressed as 33 BASE + STEP * # of iteration, and base is further decomposed as the base 34 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and 35 constant offset (INIT). Examples, in loop nest 36 37 for (i = 0; i < 100; i++) 38 for (j = 3; j < 100; j++) 39 40 Example 1 Example 2 41 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j) 42 43 44 innermost_loop_behavior 45 base_address &a p 46 offset i * D_i x 47 init 3 * D_j + offsetof (b) 28 48 step D_j 4 49 50 */ 51struct innermost_loop_behavior 52{ 53 tree base_address; 54 tree offset; 55 tree init; 56 tree step; 57 58 /* Alignment information. ALIGNED_TO is set to the largest power of two 59 that divides OFFSET. */ 60 tree aligned_to; 61}; 62 63/* Describes the evolutions of indices of the memory reference. The indices 64 are indices of the ARRAY_REFs and the operands of INDIRECT_REFs. 65 For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices 66 (note that this reference does not have to be valid, if zero does not 67 belong to the range of the array; hence it is not recommended to use 68 BASE_OBJECT in any code generation). For INDIRECT_REFs, the address is 69 set to the loop-invariant part of the address of the object, except for 70 the constant offset. For the examples above, 71 72 base_object: a[0].b[0][0] *(p + x + 4B * j_0) 73 indices: {j_0, +, 1}_2 {16, +, 4}_2 74 {i_0, +, 1}_1 75 {j_0, +, 1}_2 76*/ 77 78struct indices 79{ 80 /* The object. */ 81 tree base_object; 82 83 /* A list of chrecs. Access functions of the indices. */ 84 VEC(tree,heap) *access_fns; 85}; 86 87struct dr_alias 88{ 89 /* The alias information that should be used for new pointers to this 90 location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */ 91 struct ptr_info_def *ptr_info; 92 93 /* The set of virtual operands corresponding to this memory reference, 94 serving as a description of the alias information for the memory 95 reference. This could be eliminated if we had alias oracle. */ 96 bitmap vops; 97}; 98 99/* Each vector of the access matrix represents a linear access 100 function for a subscript. First elements correspond to the 101 leftmost indices, ie. for a[i][j] the first vector corresponds to 102 the subscript in "i". The elements of a vector are relative to 103 the loop nests in which the data reference is considered, 104 i.e. the vector is relative to the SCoP that provides the context 105 in which this data reference occurs. 106 107 For example, in 108 109 | loop_1 110 | loop_2 111 | a[i+3][2*j+n-1] 112 113 if "i" varies in loop_1 and "j" varies in loop_2, the access 114 matrix with respect to the loop nest {loop_1, loop_2} is: 115 116 | loop_1 loop_2 param_n cst 117 | 1 0 0 3 118 | 0 2 1 -1 119 120 whereas the access matrix with respect to loop_2 considers "i" as 121 a parameter: 122 123 | loop_2 param_i param_n cst 124 | 0 1 0 3 125 | 2 0 1 -1 126*/ 127struct access_matrix 128{ 129 VEC (loop_p, heap) *loop_nest; 130 int nb_induction_vars; 131 VEC (tree, heap) *parameters; 132 VEC (lambda_vector, gc) *matrix; 133}; 134 135#define AM_LOOP_NEST(M) (M)->loop_nest 136#define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars 137#define AM_PARAMETERS(M) (M)->parameters 138#define AM_MATRIX(M) (M)->matrix 139#define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M))) 140#define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M)) 141#define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1) 142#define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I) 143#define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J] 144 145/* Return the column in the access matrix of LOOP_NUM. */ 146 147static inline int 148am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num) 149{ 150 int i; 151 loop_p l; 152 153 for (i = 0; VEC_iterate (loop_p, AM_LOOP_NEST (access_matrix), i, l); i++) 154 if (l->num == loop_num) 155 return i; 156 157 gcc_unreachable(); 158} 159 160int access_matrix_get_index_for_parameter (tree, struct access_matrix *); 161 162struct data_reference 163{ 164 /* A pointer to the statement that contains this DR. */ 165 gimple stmt; 166 167 /* A pointer to the memory reference. */ 168 tree ref; 169 170 /* Auxiliary info specific to a pass. */ 171 void *aux; 172 173 /* True when the data reference is in RHS of a stmt. */ 174 bool is_read; 175 176 /* Behavior of the memory reference in the innermost loop. */ 177 struct innermost_loop_behavior innermost; 178 179 /* Subscripts of this data reference. */ 180 struct indices indices; 181 182 /* Alias information for the data reference. */ 183 struct dr_alias alias; 184 185 /* Matrix representation for the data access functions. */ 186 struct access_matrix *access_matrix; 187}; 188 189#define DR_STMT(DR) (DR)->stmt 190#define DR_REF(DR) (DR)->ref 191#define DR_BASE_OBJECT(DR) (DR)->indices.base_object 192#define DR_ACCESS_FNS(DR) (DR)->indices.access_fns 193#define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I) 194#define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR)) 195#define DR_IS_READ(DR) (DR)->is_read 196#define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address 197#define DR_OFFSET(DR) (DR)->innermost.offset 198#define DR_INIT(DR) (DR)->innermost.init 199#define DR_STEP(DR) (DR)->innermost.step 200#define DR_PTR_INFO(DR) (DR)->alias.ptr_info 201#define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to 202#define DR_ACCESS_MATRIX(DR) (DR)->access_matrix 203 204typedef struct data_reference *data_reference_p; 205DEF_VEC_P(data_reference_p); 206DEF_VEC_ALLOC_P (data_reference_p, heap); 207 208enum data_dependence_direction { 209 dir_positive, 210 dir_negative, 211 dir_equal, 212 dir_positive_or_negative, 213 dir_positive_or_equal, 214 dir_negative_or_equal, 215 dir_star, 216 dir_independent 217}; 218 219/* The description of the grid of iterations that overlap. At most 220 two loops are considered at the same time just now, hence at most 221 two functions are needed. For each of the functions, we store 222 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ..., 223 where x, y, ... are variables. */ 224 225#define MAX_DIM 2 226 227/* Special values of N. */ 228#define NO_DEPENDENCE 0 229#define NOT_KNOWN (MAX_DIM + 1) 230#define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN) 231#define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN) 232#define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE) 233 234typedef VEC (tree, heap) *affine_fn; 235 236typedef struct 237{ 238 unsigned n; 239 affine_fn fns[MAX_DIM]; 240} conflict_function; 241 242/* What is a subscript? Given two array accesses a subscript is the 243 tuple composed of the access functions for a given dimension. 244 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three 245 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts 246 are stored in the data_dependence_relation structure under the form 247 of an array of subscripts. */ 248 249struct subscript 250{ 251 /* A description of the iterations for which the elements are 252 accessed twice. */ 253 conflict_function *conflicting_iterations_in_a; 254 conflict_function *conflicting_iterations_in_b; 255 256 /* This field stores the information about the iteration domain 257 validity of the dependence relation. */ 258 tree last_conflict; 259 260 /* Distance from the iteration that access a conflicting element in 261 A to the iteration that access this same conflicting element in 262 B. The distance is a tree scalar expression, i.e. a constant or a 263 symbolic expression, but certainly not a chrec function. */ 264 tree distance; 265}; 266 267typedef struct subscript *subscript_p; 268DEF_VEC_P(subscript_p); 269DEF_VEC_ALLOC_P (subscript_p, heap); 270 271#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a 272#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b 273#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict 274#define SUB_DISTANCE(SUB) SUB->distance 275 276/* A data_dependence_relation represents a relation between two 277 data_references A and B. */ 278 279struct data_dependence_relation 280{ 281 282 struct data_reference *a; 283 struct data_reference *b; 284 285 /* A "yes/no/maybe" field for the dependence relation: 286 287 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 288 relation between A and B, and the description of this relation 289 is given in the SUBSCRIPTS array, 290 291 - when "ARE_DEPENDENT == chrec_known", there is no dependence and 292 SUBSCRIPTS is empty, 293 294 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 295 but the analyzer cannot be more specific. */ 296 tree are_dependent; 297 298 /* For each subscript in the dependence test, there is an element in 299 this array. This is the attribute that labels the edge A->B of 300 the data_dependence_relation. */ 301 VEC (subscript_p, heap) *subscripts; 302 303 /* The analyzed loop nest. */ 304 VEC (loop_p, heap) *loop_nest; 305 306 /* The classic direction vector. */ 307 VEC (lambda_vector, heap) *dir_vects; 308 309 /* The classic distance vector. */ 310 VEC (lambda_vector, heap) *dist_vects; 311 312 /* An index in loop_nest for the innermost loop that varies for 313 this data dependence relation. */ 314 unsigned inner_loop; 315 316 /* Is the dependence reversed with respect to the lexicographic order? */ 317 bool reversed_p; 318 319 /* When the dependence relation is affine, it can be represented by 320 a distance vector. */ 321 bool affine_p; 322 323 /* Set to true when the dependence relation is on the same data 324 access. */ 325 bool self_reference_p; 326}; 327 328typedef struct data_dependence_relation *ddr_p; 329DEF_VEC_P(ddr_p); 330DEF_VEC_ALLOC_P(ddr_p,heap); 331 332#define DDR_A(DDR) DDR->a 333#define DDR_B(DDR) DDR->b 334#define DDR_AFFINE_P(DDR) DDR->affine_p 335#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent 336#define DDR_SUBSCRIPTS(DDR) DDR->subscripts 337#define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I) 338#define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR)) 339 340#define DDR_LOOP_NEST(DDR) DDR->loop_nest 341/* The size of the direction/distance vectors: the number of loops in 342 the loop nest. */ 343#define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR))) 344#define DDR_INNER_LOOP(DDR) DDR->inner_loop 345#define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p 346 347#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) 348#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) 349#define DDR_NUM_DIST_VECTS(DDR) \ 350 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR))) 351#define DDR_NUM_DIR_VECTS(DDR) \ 352 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR))) 353#define DDR_DIR_VECT(DDR, I) \ 354 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I) 355#define DDR_DIST_VECT(DDR, I) \ 356 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I) 357#define DDR_REVERSED_P(DDR) DDR->reversed_p 358 359 360 361/* Describes a location of a memory reference. */ 362 363typedef struct data_ref_loc_d 364{ 365 /* Position of the memory reference. */ 366 tree *pos; 367 368 /* True if the memory reference is read. */ 369 bool is_read; 370} data_ref_loc; 371 372DEF_VEC_O (data_ref_loc); 373DEF_VEC_ALLOC_O (data_ref_loc, heap); 374 375bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **); 376bool dr_analyze_innermost (struct data_reference *); 377extern bool compute_data_dependences_for_loop (struct loop *, bool, 378 VEC (data_reference_p, heap) **, 379 VEC (ddr_p, heap) **); 380extern bool compute_data_dependences_for_bb (basic_block, bool, 381 VEC (data_reference_p, heap) **, 382 VEC (ddr_p, heap) **); 383extern tree find_data_references_in_loop (struct loop *, 384 VEC (data_reference_p, heap) **); 385extern void print_direction_vector (FILE *, lambda_vector, int); 386extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int); 387extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int); 388extern void dump_subscript (FILE *, struct subscript *); 389extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *); 390extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *); 391extern void dump_data_reference (FILE *, struct data_reference *); 392extern void debug_data_reference (struct data_reference *); 393extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *); 394extern void debug_data_references (VEC (data_reference_p, heap) *); 395extern void debug_data_dependence_relation (struct data_dependence_relation *); 396extern void dump_data_dependence_relation (FILE *, 397 struct data_dependence_relation *); 398extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *); 399extern void debug_data_dependence_relations (VEC (ddr_p, heap) *); 400extern void dump_data_dependence_direction (FILE *, 401 enum data_dependence_direction); 402extern void free_dependence_relation (struct data_dependence_relation *); 403extern void free_dependence_relations (VEC (ddr_p, heap) *); 404extern void free_data_ref (data_reference_p); 405extern void free_data_refs (VEC (data_reference_p, heap) *); 406extern bool find_data_references_in_stmt (struct loop *, gimple, 407 VEC (data_reference_p, heap) **); 408extern bool graphite_find_data_references_in_stmt (struct loop *, gimple, 409 VEC (data_reference_p, heap) **); 410struct data_reference *create_data_ref (struct loop *, tree, gimple, bool); 411extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **); 412extern void compute_all_dependences (VEC (data_reference_p, heap) *, 413 VEC (ddr_p, heap) **, VEC (loop_p, heap) *, 414 bool); 415 416extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *); 417extern bool dr_may_alias_p (const struct data_reference *, 418 const struct data_reference *); 419 420/* Return true when the DDR contains two data references that have the 421 same access functions. */ 422 423static inline bool 424same_access_functions (const struct data_dependence_relation *ddr) 425{ 426 unsigned i; 427 428 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) 429 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), 430 DR_ACCESS_FN (DDR_B (ddr), i))) 431 return false; 432 433 return true; 434} 435 436/* Return true when DDR is an anti-dependence relation. */ 437 438static inline bool 439ddr_is_anti_dependent (ddr_p ddr) 440{ 441 return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE 442 && DR_IS_READ (DDR_A (ddr)) 443 && !DR_IS_READ (DDR_B (ddr)) 444 && !same_access_functions (ddr)); 445} 446 447/* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */ 448 449static inline bool 450ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations) 451{ 452 unsigned i; 453 ddr_p ddr; 454 455 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) 456 if (ddr_is_anti_dependent (ddr)) 457 return true; 458 459 return false; 460} 461 462/* Return the dependence level for the DDR relation. */ 463 464static inline unsigned 465ddr_dependence_level (ddr_p ddr) 466{ 467 unsigned vector; 468 unsigned level = 0; 469 470 if (DDR_DIST_VECTS (ddr)) 471 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)); 472 473 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++) 474 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector), 475 DDR_NB_LOOPS (ddr))); 476 return level; 477} 478 479 480 481/* A Reduced Dependence Graph (RDG) vertex representing a statement. */ 482typedef struct rdg_vertex 483{ 484 /* The statement represented by this vertex. */ 485 gimple stmt; 486 487 /* True when the statement contains a write to memory. */ 488 bool has_mem_write; 489 490 /* True when the statement contains a read from memory. */ 491 bool has_mem_reads; 492} *rdg_vertex_p; 493 494#define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt 495#define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write 496#define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads 497#define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I])) 498#define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I])) 499#define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I])) 500 501void dump_rdg_vertex (FILE *, struct graph *, int); 502void debug_rdg_vertex (struct graph *, int); 503void dump_rdg_component (FILE *, struct graph *, int, bitmap); 504void debug_rdg_component (struct graph *, int); 505void dump_rdg (FILE *, struct graph *); 506void debug_rdg (struct graph *); 507int rdg_vertex_for_stmt (struct graph *, gimple); 508 509/* Data dependence type. */ 510 511enum rdg_dep_type 512{ 513 /* Read After Write (RAW). */ 514 flow_dd = 'f', 515 516 /* Write After Read (WAR). */ 517 anti_dd = 'a', 518 519 /* Write After Write (WAW). */ 520 output_dd = 'o', 521 522 /* Read After Read (RAR). */ 523 input_dd = 'i' 524}; 525 526/* Dependence information attached to an edge of the RDG. */ 527 528typedef struct rdg_edge 529{ 530 /* Type of the dependence. */ 531 enum rdg_dep_type type; 532 533 /* Levels of the dependence: the depth of the loops that carry the 534 dependence. */ 535 unsigned level; 536 537 /* Dependence relation between data dependences, NULL when one of 538 the vertices is a scalar. */ 539 ddr_p relation; 540} *rdg_edge_p; 541 542#define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type 543#define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level 544#define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation 545 546struct graph *build_rdg (struct loop *); 547struct graph *build_empty_rdg (int); 548void free_rdg (struct graph *); 549 550/* Return the index of the variable VAR in the LOOP_NEST array. */ 551 552static inline int 553index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest) 554{ 555 struct loop *loopi; 556 int var_index; 557 558 for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi); 559 var_index++) 560 if (loopi->num == var) 561 break; 562 563 return var_index; 564} 565 566void stores_from_loop (struct loop *, VEC (gimple, heap) **); 567void remove_similar_memory_refs (VEC (gimple, heap) **); 568bool rdg_defs_used_in_other_loops_p (struct graph *, int); 569bool have_similar_memory_accesses (gimple, gimple); 570bool stmt_with_adjacent_zero_store_dr_p (gimple); 571 572/* Returns true when STRIDE is equal in absolute value to the size of 573 the unit type of TYPE. */ 574 575static inline bool 576stride_of_unit_type_p (tree stride, tree type) 577{ 578 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride), 579 stride), 580 TYPE_SIZE_UNIT (type)); 581} 582 583/* Determines whether RDG vertices V1 and V2 access to similar memory 584 locations, in which case they have to be in the same partition. */ 585 586static inline bool 587rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2) 588{ 589 return have_similar_memory_accesses (RDG_STMT (rdg, v1), 590 RDG_STMT (rdg, v2)); 591} 592 593/* In lambda-code.c */ 594bool lambda_transform_legal_p (lambda_trans_matrix, int, 595 VEC (ddr_p, heap) *); 596void lambda_collect_parameters (VEC (data_reference_p, heap) *, 597 VEC (tree, heap) **); 598bool lambda_compute_access_matrices (VEC (data_reference_p, heap) *, 599 VEC (tree, heap) *, VEC (loop_p, heap) *); 600 601/* In tree-data-ref.c */ 602void split_constant_offset (tree , tree *, tree *); 603 604/* Strongly connected components of the reduced data dependence graph. */ 605 606typedef struct rdg_component 607{ 608 int num; 609 VEC (int, heap) *vertices; 610} *rdgc; 611 612DEF_VEC_P (rdgc); 613DEF_VEC_ALLOC_P (rdgc, heap); 614 615DEF_VEC_P (bitmap); 616DEF_VEC_ALLOC_P (bitmap, heap); 617 618#endif /* GCC_TREE_DATA_REF_H */ 619