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