gcc/tree-data-ref.h

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003-2018 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 "tree-chrec.h"
  26 #include "opt-problem.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   /* BASE_ADDRESS is known to be misaligned by BASE_MISALIGNMENT bytes
  57      from an alignment boundary of BASE_ALIGNMENT bytes.  For example,
  58      if we had:
  59
  60        struct S __attribute__((aligned(16))) { ... };
  61
  62        char *ptr;
  63        ... *(struct S *) (ptr - 4) ...;
  64
  65      the information would be:
  66
  67        base_address:      ptr
  68        base_aligment:      16
  69        base_misalignment:   4
  70        init:               -4
  71
  72      where init cancels the base misalignment.  If instead we had a
  73      reference to a particular field:
  74
  75        struct S __attribute__((aligned(16))) { ... int f; ... };
  76
  77        char *ptr;
  78        ... ((struct S *) (ptr - 4))->f ...;
  79
  80      the information would be:
  81
  82        base_address:      ptr
  83        base_aligment:      16
  84        base_misalignment:   4
  85        init:               -4 + offsetof (S, f)
  86
  87      where base_address + init might also be misaligned, and by a different
  88      amount from base_address.  */
  89   unsigned int base_alignment;
  90   unsigned int base_misalignment;
  91
  92   /* The largest power of two that divides OFFSET, capped to a suitably
  93      high value if the offset is zero.  This is a byte rather than a bit
  94      quantity.  */
  95   unsigned int offset_alignment;
  96
  97   /* Likewise for STEP.  */
  98   unsigned int step_alignment;
  99 };
 100
 101 /* Describes the evolutions of indices of the memory reference.  The indices
 102    are indices of the ARRAY_REFs, indexes in artificial dimensions
 103    added for member selection of records and the operands of MEM_REFs.
 104    BASE_OBJECT is the part of the reference that is loop-invariant
 105    (note that this reference does not have to cover the whole object
 106    being accessed, in which case UNCONSTRAINED_BASE is set; hence it is
 107    not recommended to use BASE_OBJECT in any code generation).
 108    For the examples above,
 109
 110    base_object:        a                              *(p + x + 4B * j_0)
 111    indices:            {j_0, +, 1}_2                  {16, +, 4}_2
 112                        4
 113                        {i_0, +, 1}_1
 114                        {j_0, +, 1}_2
 115 */
 116
 117 struct indices
 118 {
 119   /* The object.  */
 120   tree base_object;
 121
 122   /* A list of chrecs.  Access functions of the indices.  */
 123   vec<tree> access_fns;
 124
 125   /* Whether BASE_OBJECT is an access representing the whole object
 126      or whether the access could not be constrained.  */
 127   bool unconstrained_base;
 128 };
 129
 130 struct dr_alias
 131 {
 132   /* The alias information that should be used for new pointers to this
 133      location.  */
 134   struct ptr_info_def *ptr_info;
 135 };
 136
 137 /* An integer vector.  A vector formally consists of an element of a vector
 138    space. A vector space is a set that is closed under vector addition
 139    and scalar multiplication.  In this vector space, an element is a list of
 140    integers.  */
 141 typedef int *lambda_vector;
 142
 143 /* An integer matrix.  A matrix consists of m vectors of length n (IE
 144    all vectors are the same length).  */
 145 typedef lambda_vector *lambda_matrix;
 146
 147
 148
 149 struct data_reference
 150 {
 151   /* A pointer to the statement that contains this DR.  */
 152   gimple *stmt;
 153
 154   /* A pointer to the memory reference.  */
 155   tree ref;
 156
 157   /* Auxiliary info specific to a pass.  */
 158   void *aux;
 159
 160   /* True when the data reference is in RHS of a stmt.  */
 161   bool is_read;
 162
 163   /* True when the data reference is conditional within STMT,
 164      i.e. if it might not occur even when the statement is executed
 165      and runs to completion.  */
 166   bool is_conditional_in_stmt;
 167
 168   /* Behavior of the memory reference in the innermost loop.  */
 169   struct innermost_loop_behavior innermost;
 170
 171   /* Subscripts of this data reference.  */
 172   struct indices indices;
 173
 174   /* Alias information for the data reference.  */
 175   struct dr_alias alias;
 176 };
 177
 178 #define DR_STMT(DR)                (DR)->stmt
 179 #define DR_REF(DR)                 (DR)->ref
 180 #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
 181 #define DR_UNCONSTRAINED_BASE(DR)  (DR)->indices.unconstrained_base
 182 #define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
 183 #define DR_ACCESS_FN(DR, I)        DR_ACCESS_FNS (DR)[I]
 184 #define DR_NUM_DIMENSIONS(DR)      DR_ACCESS_FNS (DR).length ()
 185 #define DR_IS_READ(DR)             (DR)->is_read
 186 #define DR_IS_WRITE(DR)            (!DR_IS_READ (DR))
 187 #define DR_IS_CONDITIONAL_IN_STMT(DR) (DR)->is_conditional_in_stmt
 188 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
 189 #define DR_OFFSET(DR)              (DR)->innermost.offset
 190 #define DR_INIT(DR)                (DR)->innermost.init
 191 #define DR_STEP(DR)                (DR)->innermost.step
 192 #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
 193 #define DR_BASE_ALIGNMENT(DR)      (DR)->innermost.base_alignment
 194 #define DR_BASE_MISALIGNMENT(DR)   (DR)->innermost.base_misalignment
 195 #define DR_OFFSET_ALIGNMENT(DR)    (DR)->innermost.offset_alignment
 196 #define DR_STEP_ALIGNMENT(DR)      (DR)->innermost.step_alignment
 197 #define DR_INNERMOST(DR)           (DR)->innermost
 198
 199 typedef struct data_reference *data_reference_p;
 200
 201 /* This struct is used to store the information of a data reference,
 202    including the data ref itself and the segment length for aliasing
 203    checks.  This is used to merge alias checks.  */
 204
 205 struct dr_with_seg_len
 206 {
 207   dr_with_seg_len (data_reference_p d, tree len, unsigned HOST_WIDE_INT size,
 208                    unsigned int a)
 209     : dr (d), seg_len (len), access_size (size), align (a) {}
 210
 211   data_reference_p dr;
 212   /* The offset of the last access that needs to be checked minus
 213      the offset of the first.  */
 214   tree seg_len;
 215   /* A value that, when added to abs (SEG_LEN), gives the total number of
 216      bytes in the segment.  */
 217   poly_uint64 access_size;
 218   /* The minimum common alignment of DR's start address, SEG_LEN and
 219      ACCESS_SIZE.  */
 220   unsigned int align;
 221 };
 222
 223 /* This struct contains two dr_with_seg_len objects with aliasing data
 224    refs.  Two comparisons are generated from them.  */
 225
 226 struct dr_with_seg_len_pair_t
 227 {
 228   dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
 229                                const dr_with_seg_len& d2)
 230     : first (d1), second (d2) {}
 231
 232   dr_with_seg_len first;
 233   dr_with_seg_len second;
 234 };
 235
 236 enum data_dependence_direction {
 237   dir_positive,
 238   dir_negative,
 239   dir_equal,
 240   dir_positive_or_negative,
 241   dir_positive_or_equal,
 242   dir_negative_or_equal,
 243   dir_star,
 244   dir_independent
 245 };
 246
 247 /* The description of the grid of iterations that overlap.  At most
 248    two loops are considered at the same time just now, hence at most
 249    two functions are needed.  For each of the functions, we store
 250    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
 251    where x, y, ... are variables.  */
 252
 253 #define MAX_DIM 2
 254
 255 /* Special values of N.  */
 256 #define NO_DEPENDENCE 0
 257 #define NOT_KNOWN (MAX_DIM + 1)
 258 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
 259 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
 260 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
 261
 262 typedef vec<tree> affine_fn;
 263
 264 struct conflict_function
 265 {
 266   unsigned n;
 267   affine_fn fns[MAX_DIM];
 268 };
 269
 270 /* What is a subscript?  Given two array accesses a subscript is the
 271    tuple composed of the access functions for a given dimension.
 272    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
 273    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
 274    are stored in the data_dependence_relation structure under the form
 275    of an array of subscripts.  */
 276
 277 struct subscript
 278 {
 279   /* The access functions of the two references.  */
 280   tree access_fn[2];
 281
 282   /* A description of the iterations for which the elements are
 283      accessed twice.  */
 284   conflict_function *conflicting_iterations_in_a;
 285   conflict_function *conflicting_iterations_in_b;
 286
 287   /* This field stores the information about the iteration domain
 288      validity of the dependence relation.  */
 289   tree last_conflict;
 290
 291   /* Distance from the iteration that access a conflicting element in
 292      A to the iteration that access this same conflicting element in
 293      B.  The distance is a tree scalar expression, i.e. a constant or a
 294      symbolic expression, but certainly not a chrec function.  */
 295   tree distance;
 296 };
 297
 298 typedef struct subscript *subscript_p;
 299
 300 #define SUB_ACCESS_FN(SUB, I) (SUB)->access_fn[I]
 301 #define SUB_CONFLICTS_IN_A(SUB) (SUB)->conflicting_iterations_in_a
 302 #define SUB_CONFLICTS_IN_B(SUB) (SUB)->conflicting_iterations_in_b
 303 #define SUB_LAST_CONFLICT(SUB) (SUB)->last_conflict
 304 #define SUB_DISTANCE(SUB) (SUB)->distance
 305
 306 /* A data_dependence_relation represents a relation between two
 307    data_references A and B.  */
 308
 309 struct data_dependence_relation
 310 {
 311
 312   struct data_reference *a;
 313   struct data_reference *b;
 314
 315   /* A "yes/no/maybe" field for the dependence relation:
 316
 317      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
 318        relation between A and B, and the description of this relation
 319        is given in the SUBSCRIPTS array,
 320
 321      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
 322        SUBSCRIPTS is empty,
 323
 324      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
 325        but the analyzer cannot be more specific.  */
 326   tree are_dependent;
 327
 328   /* If nonnull, COULD_BE_INDEPENDENT_P is true and the accesses are
 329      independent when the runtime addresses of OBJECT_A and OBJECT_B
 330      are different.  The addresses of both objects are invariant in the
 331      loop nest.  */
 332   tree object_a;
 333   tree object_b;
 334
 335   /* For each subscript in the dependence test, there is an element in
 336      this array.  This is the attribute that labels the edge A->B of
 337      the data_dependence_relation.  */
 338   vec<subscript_p> subscripts;
 339
 340   /* The analyzed loop nest.  */
 341   vec<loop_p> loop_nest;
 342
 343   /* The classic direction vector.  */
 344   vec<lambda_vector> dir_vects;
 345
 346   /* The classic distance vector.  */
 347   vec<lambda_vector> dist_vects;
 348
 349   /* An index in loop_nest for the innermost loop that varies for
 350      this data dependence relation.  */
 351   unsigned inner_loop;
 352
 353   /* Is the dependence reversed with respect to the lexicographic order?  */
 354   bool reversed_p;
 355
 356   /* When the dependence relation is affine, it can be represented by
 357      a distance vector.  */
 358   bool affine_p;
 359
 360   /* Set to true when the dependence relation is on the same data
 361      access.  */
 362   bool self_reference_p;
 363
 364   /* True if the dependence described is conservatively correct rather
 365      than exact, and if it is still possible for the accesses to be
 366      conditionally independent.  For example, the a and b references in:
 367
 368        struct s *a, *b;
 369        for (int i = 0; i < n; ++i)
 370          a->f[i] += b->f[i];
 371
 372      conservatively have a distance vector of (0), for the case in which
 373      a == b, but the accesses are independent if a != b.  Similarly,
 374      the a and b references in:
 375
 376        struct s *a, *b;
 377        for (int i = 0; i < n; ++i)
 378          a[0].f[i] += b[i].f[i];
 379
 380      conservatively have a distance vector of (0), but they are indepenent
 381      when a != b + i.  In contrast, the references in:
 382
 383        struct s *a;
 384        for (int i = 0; i < n; ++i)
 385          a->f[i] += a->f[i];
 386
 387      have the same distance vector of (0), but the accesses can never be
 388      independent.  */
 389   bool could_be_independent_p;
 390 };
 391
 392 typedef struct data_dependence_relation *ddr_p;
 393
 394 #define DDR_A(DDR) (DDR)->a
 395 #define DDR_B(DDR) (DDR)->b
 396 #define DDR_AFFINE_P(DDR) (DDR)->affine_p
 397 #define DDR_ARE_DEPENDENT(DDR) (DDR)->are_dependent
 398 #define DDR_OBJECT_A(DDR) (DDR)->object_a
 399 #define DDR_OBJECT_B(DDR) (DDR)->object_b
 400 #define DDR_SUBSCRIPTS(DDR) (DDR)->subscripts
 401 #define DDR_SUBSCRIPT(DDR, I) DDR_SUBSCRIPTS (DDR)[I]
 402 #define DDR_NUM_SUBSCRIPTS(DDR) DDR_SUBSCRIPTS (DDR).length ()
 403
 404 #define DDR_LOOP_NEST(DDR) (DDR)->loop_nest
 405 /* The size of the direction/distance vectors: the number of loops in
 406    the loop nest.  */
 407 #define DDR_NB_LOOPS(DDR) (DDR_LOOP_NEST (DDR).length ())
 408 #define DDR_INNER_LOOP(DDR) (DDR)->inner_loop
 409 #define DDR_SELF_REFERENCE(DDR) (DDR)->self_reference_p
 410
 411 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
 412 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
 413 #define DDR_NUM_DIST_VECTS(DDR) \
 414   (DDR_DIST_VECTS (DDR).length ())
 415 #define DDR_NUM_DIR_VECTS(DDR) \
 416   (DDR_DIR_VECTS (DDR).length ())
 417 #define DDR_DIR_VECT(DDR, I) \
 418   DDR_DIR_VECTS (DDR)[I]
 419 #define DDR_DIST_VECT(DDR, I) \
 420   DDR_DIST_VECTS (DDR)[I]
 421 #define DDR_REVERSED_P(DDR) (DDR)->reversed_p
 422 #define DDR_COULD_BE_INDEPENDENT_P(DDR) (DDR)->could_be_independent_p
 423
 424 \f
 425 opt_result dr_analyze_innermost (innermost_loop_behavior *, tree,
 426                                  struct loop *, const gimple *);
 427 extern bool compute_data_dependences_for_loop (struct loop *, bool,
 428                                                vec<loop_p> *,
 429                                                vec<data_reference_p> *,
 430                                                vec<ddr_p> *);
 431 extern void debug_ddrs (vec<ddr_p> );
 432 extern void dump_data_reference (FILE *, struct data_reference *);
 433 extern void debug (data_reference &ref);
 434 extern void debug (data_reference *ptr);
 435 extern void debug_data_reference (struct data_reference *);
 436 extern void debug_data_references (vec<data_reference_p> );
 437 extern void debug (vec<data_reference_p> &ref);
 438 extern void debug (vec<data_reference_p> *ptr);
 439 extern void debug_data_dependence_relation (struct data_dependence_relation *);
 440 extern void dump_data_dependence_relations (FILE *, vec<ddr_p> );
 441 extern void debug (vec<ddr_p> &ref);
 442 extern void debug (vec<ddr_p> *ptr);
 443 extern void debug_data_dependence_relations (vec<ddr_p> );
 444 extern void free_dependence_relation (struct data_dependence_relation *);
 445 extern void free_dependence_relations (vec<ddr_p> );
 446 extern void free_data_ref (data_reference_p);
 447 extern void free_data_refs (vec<data_reference_p> );
 448 extern opt_result find_data_references_in_stmt (struct loop *, gimple *,
 449                                                 vec<data_reference_p> *);
 450 extern bool graphite_find_data_references_in_stmt (edge, loop_p, gimple *,
 451                                                    vec<data_reference_p> *);
 452 tree find_data_references_in_loop (struct loop *, vec<data_reference_p> *);
 453 bool loop_nest_has_data_refs (loop_p loop);
 454 struct data_reference *create_data_ref (edge, loop_p, tree, gimple *, bool,
 455                                         bool);
 456 extern bool find_loop_nest (struct loop *, vec<loop_p> *);
 457 extern struct data_dependence_relation *initialize_data_dependence_relation
 458      (struct data_reference *, struct data_reference *, vec<loop_p>);
 459 extern void compute_affine_dependence (struct data_dependence_relation *,
 460                                        loop_p);
 461 extern void compute_self_dependence (struct data_dependence_relation *);
 462 extern bool compute_all_dependences (vec<data_reference_p> ,
 463                                      vec<ddr_p> *,
 464                                      vec<loop_p>, bool);
 465 extern tree find_data_references_in_bb (struct loop *, basic_block,
 466                                         vec<data_reference_p> *);
 467 extern unsigned int dr_alignment (innermost_loop_behavior *);
 468 extern tree get_base_for_alignment (tree, unsigned int *);
 469
 470 /* Return the alignment in bytes that DR is guaranteed to have at all
 471    times.  */
 472
 473 inline unsigned int
 474 dr_alignment (data_reference *dr)
 475 {
 476   return dr_alignment (&DR_INNERMOST (dr));
 477 }
 478
 479 extern bool dr_may_alias_p (const struct data_reference *,
 480                             const struct data_reference *, bool);
 481 extern bool dr_equal_offsets_p (struct data_reference *,
 482                                 struct data_reference *);
 483
 484 extern opt_result runtime_alias_check_p (ddr_p, struct loop *, bool);
 485 extern int data_ref_compare_tree (tree, tree);
 486 extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
 487                                            poly_uint64);
 488 extern void create_runtime_alias_checks (struct loop *,
 489                                          vec<dr_with_seg_len_pair_t> *, tree*);
 490 extern tree dr_direction_indicator (struct data_reference *);
 491 extern tree dr_zero_step_indicator (struct data_reference *);
 492 extern bool dr_known_forward_stride_p (struct data_reference *);
 493
 494 /* Return true when the base objects of data references A and B are
 495    the same memory object.  */
 496
 497 static inline bool
 498 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
 499 {
 500   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
 501     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
 502 }
 503
 504 /* Return true when the data references A and B are accessing the same
 505    memory object with the same access functions.  */
 506
 507 static inline bool
 508 same_data_refs (data_reference_p a, data_reference_p b)
 509 {
 510   unsigned int i;
 511
 512   /* The references are exactly the same.  */
 513   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
 514     return true;
 515
 516   if (!same_data_refs_base_objects (a, b))
 517     return false;
 518
 519   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
 520     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
 521       return false;
 522
 523   return true;
 524 }
 525
 526 /* Returns true when all the dependences are computable.  */
 527
 528 inline bool
 529 known_dependences_p (vec<ddr_p> dependence_relations)
 530 {
 531   ddr_p ddr;
 532   unsigned int i;
 533
 534   FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
 535     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 536       return false;
 537
 538   return true;
 539 }
 540
 541 /* Returns the dependence level for a vector DIST of size LENGTH.
 542    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
 543    to the sequence of statements, not carried by any loop.  */
 544
 545 static inline unsigned
 546 dependence_level (lambda_vector dist_vect, int length)
 547 {
 548   int i;
 549
 550   for (i = 0; i < length; i++)
 551     if (dist_vect[i] != 0)
 552       return i + 1;
 553
 554   return 0;
 555 }
 556
 557 /* Return the dependence level for the DDR relation.  */
 558
 559 static inline unsigned
 560 ddr_dependence_level (ddr_p ddr)
 561 {
 562   unsigned vector;
 563   unsigned level = 0;
 564
 565   if (DDR_DIST_VECTS (ddr).exists ())
 566     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
 567
 568   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
 569     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
 570                                           DDR_NB_LOOPS (ddr)));
 571   return level;
 572 }
 573
 574 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 575
 576 static inline int
 577 index_in_loop_nest (int var, vec<loop_p> loop_nest)
 578 {
 579   struct loop *loopi;
 580   int var_index;
 581
 582   for (var_index = 0; loop_nest.iterate (var_index, &loopi);
 583        var_index++)
 584     if (loopi->num == var)
 585       break;
 586
 587   return var_index;
 588 }
 589
 590 /* Returns true when the data reference DR the form "A[i] = ..."
 591    with a stride equal to its unit type size.  */
 592
 593 static inline bool
 594 adjacent_dr_p (struct data_reference *dr)
 595 {
 596   /* If this is a bitfield store bail out.  */
 597   if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
 598       && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
 599     return false;
 600
 601   if (!DR_STEP (dr)
 602       || TREE_CODE (DR_STEP (dr)) != INTEGER_CST)
 603     return false;
 604
 605   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (DR_STEP (dr)),
 606                                          DR_STEP (dr)),
 607                              TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
 608 }
 609
 610 void split_constant_offset (tree , tree *, tree *);
 611
 612 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
 613
 614 static inline int
 615 lambda_vector_gcd (lambda_vector vector, int size)
 616 {
 617   int i;
 618   int gcd1 = 0;
 619
 620   if (size > 0)
 621     {
 622       gcd1 = vector[0];
 623       for (i = 1; i < size; i++)
 624         gcd1 = gcd (gcd1, vector[i]);
 625     }
 626   return gcd1;
 627 }
 628
 629 /* Allocate a new vector of given SIZE.  */
 630
 631 static inline lambda_vector
 632 lambda_vector_new (int size)
 633 {
 634   /* ???  We shouldn't abuse the GC allocator here.  */
 635   return ggc_cleared_vec_alloc<int> (size);
 636 }
 637
 638 /* Clear out vector VEC1 of length SIZE.  */
 639
 640 static inline void
 641 lambda_vector_clear (lambda_vector vec1, int size)
 642 {
 643   memset (vec1, 0, size * sizeof (*vec1));
 644 }
 645
 646 /* Returns true when the vector V is lexicographically positive, in
 647    other words, when the first nonzero element is positive.  */
 648
 649 static inline bool
 650 lambda_vector_lexico_pos (lambda_vector v,
 651                           unsigned n)
 652 {
 653   unsigned i;
 654   for (i = 0; i < n; i++)
 655     {
 656       if (v[i] == 0)
 657         continue;
 658       if (v[i] < 0)
 659         return false;
 660       if (v[i] > 0)
 661         return true;
 662     }
 663   return true;
 664 }
 665
 666 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
 667
 668 static inline bool
 669 lambda_vector_zerop (lambda_vector vec1, int size)
 670 {
 671   int i;
 672   for (i = 0; i < size; i++)
 673     if (vec1[i] != 0)
 674       return false;
 675   return true;
 676 }
 677
 678 /* Allocate a matrix of M rows x  N cols.  */
 679
 680 static inline lambda_matrix
 681 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
 682 {
 683   lambda_matrix mat;
 684   int i;
 685
 686   mat = XOBNEWVEC (lambda_obstack, lambda_vector, m);
 687
 688   for (i = 0; i < m; i++)
 689     mat[i] = XOBNEWVEC (lambda_obstack, int, n);
 690
 691   return mat;
 692 }
 693
 694 #endif  /* GCC_TREE_DATA_REF_H  */