gcc/tree-data-ref.h

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