gcc/tree-data-ref.h

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