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