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