gcc/tree-data-ref.h

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