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 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   struct ptr_info_def *ptr_info;
  91
  92   /* The set of virtual operands corresponding to this memory reference,
  93      serving as a description of the alias information for the memory
  94      reference.  This could be eliminated if we had alias oracle.  */
  95   bitmap vops;
  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_ACCESS_FNS(DR)          (DR)->indices.access_fns
 205 #define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
 206 #define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))
 207 #define DR_IS_READ(DR)             (DR)->is_read
 208 #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
 209 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
 210 #define DR_OFFSET(DR)              (DR)->innermost.offset
 211 #define DR_INIT(DR)                (DR)->innermost.init
 212 #define DR_STEP(DR)                (DR)->innermost.step
 213 #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
 214 #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
 215 #define DR_ACCESS_MATRIX(DR)       (DR)->access_matrix
 216
 217 typedef struct data_reference *data_reference_p;
 218 DEF_VEC_P(data_reference_p);
 219 DEF_VEC_ALLOC_P (data_reference_p, heap);
 220
 221 enum data_dependence_direction {
 222   dir_positive,
 223   dir_negative,
 224   dir_equal,
 225   dir_positive_or_negative,
 226   dir_positive_or_equal,
 227   dir_negative_or_equal,
 228   dir_star,
 229   dir_independent
 230 };
 231
 232 /* The description of the grid of iterations that overlap.  At most
 233    two loops are considered at the same time just now, hence at most
 234    two functions are needed.  For each of the functions, we store
 235    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
 236    where x, y, ... are variables.  */
 237
 238 #define MAX_DIM 2
 239
 240 /* Special values of N.  */
 241 #define NO_DEPENDENCE 0
 242 #define NOT_KNOWN (MAX_DIM + 1)
 243 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
 244 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
 245 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
 246
 247 typedef VEC (tree, heap) *affine_fn;
 248
 249 typedef struct
 250 {
 251   unsigned n;
 252   affine_fn fns[MAX_DIM];
 253 } conflict_function;
 254
 255 /* What is a subscript?  Given two array accesses a subscript is the
 256    tuple composed of the access functions for a given dimension.
 257    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 258    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 259    are stored in the data_dependence_relation structure under the form
 260    of an array of subscripts.  */
 261
 262 struct subscript
 263 {
 264   /* A description of the iterations for which the elements are
 265      accessed twice.  */
 266   conflict_function *conflicting_iterations_in_a;
 267   conflict_function *conflicting_iterations_in_b;
 268
 269   /* This field stores the information about the iteration domain
 270      validity of the dependence relation.  */
 271   tree last_conflict;
 272
 273   /* Distance from the iteration that access a conflicting element in
 274      A to the iteration that access this same conflicting element in
 275      B.  The distance is a tree scalar expression, i.e. a constant or a
 276      symbolic expression, but certainly not a chrec function.  */
 277   tree distance;
 278 };
 279
 280 typedef struct subscript *subscript_p;
 281 DEF_VEC_P(subscript_p);
 282 DEF_VEC_ALLOC_P (subscript_p, heap);
 283
 284 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
 285 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
 286 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
 287 #define SUB_DISTANCE(SUB) SUB->distance
 288
 289 /* A data_dependence_relation represents a relation between two
 290    data_references A and B.  */
 291
 292 struct data_dependence_relation
 293 {
 294
 295   struct data_reference *a;
 296   struct data_reference *b;
 297
 298   /* A "yes/no/maybe" field for the dependence relation:
 299
 300      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 301        relation between A and B, and the description of this relation
 302        is given in the SUBSCRIPTS array,
 303
 304      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 305        SUBSCRIPTS is empty,
 306
 307      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 308        but the analyzer cannot be more specific.  */
 309   tree are_dependent;
 310
 311   /* For each subscript in the dependence test, there is an element in
 312      this array.  This is the attribute that labels the edge A->B of
 313      the data_dependence_relation.  */
 314   VEC (subscript_p, heap) *subscripts;
 315
 316   /* The analyzed loop nest.  */
 317   VEC (loop_p, heap) *loop_nest;
 318
 319   /* The classic direction vector.  */
 320   VEC (lambda_vector, heap) *dir_vects;
 321
 322   /* The classic distance vector.  */
 323   VEC (lambda_vector, heap) *dist_vects;
 324
 325   /* An index in loop_nest for the innermost loop that varies for
 326      this data dependence relation.  */
 327   unsigned inner_loop;
 328
 329   /* Is the dependence reversed with respect to the lexicographic order?  */
 330   bool reversed_p;
 331
 332   /* When the dependence relation is affine, it can be represented by
 333      a distance vector.  */
 334   bool affine_p;
 335
 336   /* Set to true when the dependence relation is on the same data
 337      access.  */
 338   bool self_reference_p;
 339 };
 340
 341 typedef struct data_dependence_relation *ddr_p;
 342 DEF_VEC_P(ddr_p);
 343 DEF_VEC_ALLOC_P(ddr_p,heap);
 344
 345 #define DDR_A(DDR) DDR->a
 346 #define DDR_B(DDR) DDR->b
 347 #define DDR_AFFINE_P(DDR) DDR->affine_p
 348 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
 349 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
 350 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
 351 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
 352
 353 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
 354 /* The size of the direction/distance vectors: the number of loops in
 355    the loop nest.  */
 356 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
 357 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
 358 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
 359
 360 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 361 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 362 #define DDR_NUM_DIST_VECTS(DDR) \
 363   (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
 364 #define DDR_NUM_DIR_VECTS(DDR) \
 365   (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
 366 #define DDR_DIR_VECT(DDR, I) \
 367   VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
 368 #define DDR_DIST_VECT(DDR, I) \
 369   VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
 370 #define DDR_REVERSED_P(DDR) DDR->reversed_p
 371
 372 \f
 373
 374 /* Describes a location of a memory reference.  */
 375
 376 typedef struct data_ref_loc_d
 377 {
 378   /* Position of the memory reference.  */
 379   tree *pos;
 380
 381   /* True if the memory reference is read.  */
 382   bool is_read;
 383 } data_ref_loc;
 384
 385 DEF_VEC_O (data_ref_loc);
 386 DEF_VEC_ALLOC_O (data_ref_loc, heap);
 387
 388 bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **);
 389 bool dr_analyze_innermost (struct data_reference *, struct loop *);
 390 extern bool compute_data_dependences_for_loop (struct loop *, bool,
 391                                                VEC (loop_p, heap) **,
 392                                                VEC (data_reference_p, heap) **,
 393                                                VEC (ddr_p, heap) **);
 394 extern bool compute_data_dependences_for_bb (basic_block, bool,
 395                                              VEC (data_reference_p, heap) **,
 396                                              VEC (ddr_p, heap) **);
 397 extern void print_direction_vector (FILE *, lambda_vector, int);
 398 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 399 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 400 extern void dump_subscript (FILE *, struct subscript *);
 401 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
 402 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
 403 extern void dump_data_reference (FILE *, struct data_reference *);
 404 extern void debug_data_reference (struct data_reference *);
 405 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
 406 extern void debug_data_references (VEC (data_reference_p, heap) *);
 407 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 408 extern void dump_data_dependence_relation (FILE *,
 409                                            struct data_dependence_relation *);
 410 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
 411 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
 412 extern void dump_data_dependence_direction (FILE *,
 413                                             enum data_dependence_direction);
 414 extern void free_dependence_relation (struct data_dependence_relation *);
 415 extern void free_dependence_relations (VEC (ddr_p, heap) *);
 416 extern void free_data_ref (data_reference_p);
 417 extern void free_data_refs (VEC (data_reference_p, heap) *);
 418 extern bool find_data_references_in_stmt (struct loop *, gimple,
 419                                           VEC (data_reference_p, heap) **);
 420 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
 421                                                    VEC (data_reference_p, heap) **);
 422 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
 423 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
 424 extern struct data_dependence_relation *initialize_data_dependence_relation
 425      (struct data_reference *, struct data_reference *, VEC (loop_p, heap) *);
 426 extern void compute_self_dependence (struct data_dependence_relation *);
 427 extern bool compute_all_dependences (VEC (data_reference_p, heap) *,
 428                                      VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
 429                                      bool);
 430 extern tree find_data_references_in_bb (struct loop *, basic_block,
 431                                         VEC (data_reference_p, heap) **);
 432
 433 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
 434 extern bool dr_may_alias_p (const struct data_reference *,
 435                             const struct data_reference *, bool);
 436 extern bool dr_equal_offsets_p (struct data_reference *,
 437                                 struct data_reference *);
 438
 439
 440 /* Return true when the base objects of data references A and B are
 441    the same memory object.  */
 442
 443 static inline bool
 444 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
 445 {
 446   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
 447     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
 448 }
 449
 450 /* Return true when the data references A and B are accessing the same
 451    memory object with the same access functions.  */
 452
 453 static inline bool
 454 same_data_refs (data_reference_p a, data_reference_p b)
 455 {
 456   unsigned int i;
 457
 458   /* The references are exactly the same.  */
 459   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
 460     return true;
 461
 462   if (!same_data_refs_base_objects (a, b))
 463     return false;
 464
 465   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
 466     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
 467       return false;
 468
 469   return true;
 470 }
 471
 472 /* Return true when the DDR contains two data references that have the
 473    same access functions.  */
 474
 475 static inline bool
 476 same_access_functions (const struct data_dependence_relation *ddr)
 477 {
 478   unsigned i;
 479
 480   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 481     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
 482                           DR_ACCESS_FN (DDR_B (ddr), i)))
 483       return false;
 484
 485   return true;
 486 }
 487
 488 /* Return true when DDR is an anti-dependence relation.  */
 489
 490 static inline bool
 491 ddr_is_anti_dependent (ddr_p ddr)
 492 {
 493   return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
 494           && DR_IS_READ (DDR_A (ddr))
 495           && DR_IS_WRITE (DDR_B (ddr))
 496           && !same_access_functions (ddr));
 497 }
 498
 499 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence.  */
 500
 501 static inline bool
 502 ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
 503 {
 504   unsigned i;
 505   ddr_p ddr;
 506
 507   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
 508     if (ddr_is_anti_dependent (ddr))
 509       return true;
 510
 511   return false;
 512 }
 513
 514 /* Returns the dependence level for a vector DIST of size LENGTH.
 515    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
 516    to the sequence of statements, not carried by any loop.  */
 517
 518 static inline unsigned
 519 dependence_level (lambda_vector dist_vect, int length)
 520 {
 521   int i;
 522
 523   for (i = 0; i < length; i++)
 524     if (dist_vect[i] != 0)
 525       return i + 1;
 526
 527   return 0;
 528 }
 529
 530 /* Return the dependence level for the DDR relation.  */
 531
 532 static inline unsigned
 533 ddr_dependence_level (ddr_p ddr)
 534 {
 535   unsigned vector;
 536   unsigned level = 0;
 537
 538   if (DDR_DIST_VECTS (ddr))
 539     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
 540
 541   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
 542     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
 543                                           DDR_NB_LOOPS (ddr)));
 544   return level;
 545 }
 546
 547 \f
 548
 549 /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
 550 typedef struct rdg_vertex
 551 {
 552   /* The statement represented by this vertex.  */
 553   gimple stmt;
 554
 555   /* True when the statement contains a write to memory.  */
 556   bool has_mem_write;
 557
 558   /* True when the statement contains a read from memory.  */
 559   bool has_mem_reads;
 560 } *rdg_vertex_p;
 561
 562 #define RDGV_STMT(V)     ((struct rdg_vertex *) ((V)->data))->stmt
 563 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
 564 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
 565 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
 566 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
 567 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
 568
 569 void dump_rdg_vertex (FILE *, struct graph *, int);
 570 void debug_rdg_vertex (struct graph *, int);
 571 void dump_rdg_component (FILE *, struct graph *, int, bitmap);
 572 void debug_rdg_component (struct graph *, int);
 573 void dump_rdg (FILE *, struct graph *);
 574 void debug_rdg (struct graph *);
 575 int rdg_vertex_for_stmt (struct graph *, gimple);
 576
 577 /* Data dependence type.  */
 578
 579 enum rdg_dep_type
 580 {
 581   /* Read After Write (RAW).  */
 582   flow_dd = 'f',
 583
 584   /* Write After Read (WAR).  */
 585   anti_dd = 'a',
 586
 587   /* Write After Write (WAW).  */
 588   output_dd = 'o',
 589
 590   /* Read After Read (RAR).  */
 591   input_dd = 'i'
 592 };
 593
 594 /* Dependence information attached to an edge of the RDG.  */
 595
 596 typedef struct rdg_edge
 597 {
 598   /* Type of the dependence.  */
 599   enum rdg_dep_type type;
 600
 601   /* Levels of the dependence: the depth of the loops that carry the
 602      dependence.  */
 603   unsigned level;
 604
 605   /* Dependence relation between data dependences, NULL when one of
 606      the vertices is a scalar.  */
 607   ddr_p relation;
 608 } *rdg_edge_p;
 609
 610 #define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
 611 #define RDGE_LEVEL(E)       ((struct rdg_edge *) ((E)->data))->level
 612 #define RDGE_RELATION(E)    ((struct rdg_edge *) ((E)->data))->relation
 613
 614 struct graph *build_rdg (struct loop *,
 615                          VEC (loop_p, heap) **,
 616                          VEC (ddr_p, heap) **,
 617                          VEC (data_reference_p, heap) **);
 618 struct graph *build_empty_rdg (int);
 619 void free_rdg (struct graph *);
 620
 621 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 622
 623 static inline int
 624 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
 625 {
 626   struct loop *loopi;
 627   int var_index;
 628
 629   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
 630        var_index++)
 631     if (loopi->num == var)
 632       break;
 633
 634   return var_index;
 635 }
 636
 637 void stores_from_loop (struct loop *, VEC (gimple, heap) **);
 638 void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **);
 639 void remove_similar_memory_refs (VEC (gimple, heap) **);
 640 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
 641 bool have_similar_memory_accesses (gimple, gimple);
 642 bool stmt_with_adjacent_zero_store_dr_p (gimple);
 643
 644 /* Returns true when STRIDE is equal in absolute value to the size of
 645    the unit type of TYPE.  */
 646
 647 static inline bool
 648 stride_of_unit_type_p (tree stride, tree type)
 649 {
 650   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride),
 651                                          stride),
 652                              TYPE_SIZE_UNIT (type));
 653 }
 654
 655 /* Determines whether RDG vertices V1 and V2 access to similar memory
 656    locations, in which case they have to be in the same partition.  */
 657
 658 static inline bool
 659 rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
 660 {
 661   return have_similar_memory_accesses (RDG_STMT (rdg, v1),
 662                                        RDG_STMT (rdg, v2));
 663 }
 664
 665 /* In tree-data-ref.c  */
 666 void split_constant_offset (tree , tree *, tree *);
 667
 668 /* Strongly connected components of the reduced data dependence graph.  */
 669
 670 typedef struct rdg_component
 671 {
 672   int num;
 673   VEC (int, heap) *vertices;
 674 } *rdgc;
 675
 676 DEF_VEC_P (rdgc);
 677 DEF_VEC_ALLOC_P (rdgc, heap);
 678
 679 DEF_VEC_P (bitmap);
 680 DEF_VEC_ALLOC_P (bitmap, heap);
 681
 682 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 683
 684 static inline int
 685 lambda_vector_gcd (lambda_vector vector, int size)
 686 {
 687   int i;
 688   int gcd1 = 0;
 689
 690   if (size > 0)
 691     {
 692       gcd1 = vector[0];
 693       for (i = 1; i < size; i++)
 694         gcd1 = gcd (gcd1, vector[i]);
 695     }
 696   return gcd1;
 697 }
 698
 699 /* Allocate a new vector of given SIZE.  */
 700
 701 static inline lambda_vector
 702 lambda_vector_new (int size)
 703 {
 704   return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size);
 705 }
 706
 707 /* Clear out vector VEC1 of length SIZE.  */
 708
 709 static inline void
 710 lambda_vector_clear (lambda_vector vec1, int size)
 711 {
 712   memset (vec1, 0, size * sizeof (*vec1));
 713 }
 714
 715 /* Returns true when the vector V is lexicographically positive, in
 716    other words, when the first nonzero element is positive.  */
 717
 718 static inline bool
 719 lambda_vector_lexico_pos (lambda_vector v,
 720                           unsigned n)
 721 {
 722   unsigned i;
 723   for (i = 0; i < n; i++)
 724     {
 725       if (v[i] == 0)
 726         continue;
 727       if (v[i] < 0)
 728         return false;
 729       if (v[i] > 0)
 730         return true;
 731     }
 732   return true;
 733 }
 734
 735 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 736
 737 static inline bool
 738 lambda_vector_zerop (lambda_vector vec1, int size)
 739 {
 740   int i;
 741   for (i = 0; i < size; i++)
 742     if (vec1[i] != 0)
 743       return false;
 744   return true;
 745 }
 746
 747 /* Allocate a matrix of M rows x  N cols.  */
 748
 749 static inline lambda_matrix
 750 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
 751 {
 752   lambda_matrix mat;
 753   int i;
 754
 755   mat = (lambda_matrix) obstack_alloc (lambda_obstack,
 756                                        sizeof (lambda_vector *) * m);
 757
 758   for (i = 0; i < m; i++)
 759     mat[i] = lambda_vector_new (n);
 760
 761   return mat;
 762 }
 763
 764 #endif  /* GCC_TREE_DATA_REF_H  */