gcc/tree-data-ref.h

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