gcc/tree-data-ref.h

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