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