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