gcc/tree-data-ref.h

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