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