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