Daily bump.
[official-gcc.git] / gcc / tree-data-ref.h
blob0588136cb8d452dba3af49b4080e1866195156f2
1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #ifndef GCC_TREE_DATA_REF_H
23 #define GCC_TREE_DATA_REF_H
25 #include "graphds.h"
26 #include "omega.h"
27 #include "tree-chrec.h"
30 innermost_loop_behavior describes the evolution of the address of the memory
31 reference in the innermost enclosing loop. The address is expressed as
32 BASE + STEP * # of iteration, and base is further decomposed as the base
33 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
34 constant offset (INIT). Examples, in loop nest
36 for (i = 0; i < 100; i++)
37 for (j = 3; j < 100; j++)
39 Example 1 Example 2
40 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
43 innermost_loop_behavior
44 base_address &a p
45 offset i * D_i x
46 init 3 * D_j + offsetof (b) 28
47 step D_j 4
50 struct innermost_loop_behavior
52 tree base_address;
53 tree offset;
54 tree init;
55 tree step;
57 /* Alignment information. ALIGNED_TO is set to the largest power of two
58 that divides OFFSET. */
59 tree aligned_to;
62 /* Describes the evolutions of indices of the memory reference. The indices
63 are indices of the ARRAY_REFs and the operands of INDIRECT_REFs.
64 For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices
65 (note that this reference does not have to be valid, if zero does not
66 belong to the range of the array; hence it is not recommended to use
67 BASE_OBJECT in any code generation). For INDIRECT_REFs, the address is
68 set to the loop-invariant part of the address of the object, except for
69 the constant offset. For the examples above,
71 base_object: a[0].b[0][0] *(p + x + 4B * j_0)
72 indices: {j_0, +, 1}_2 {16, +, 4}_2
73 {i_0, +, 1}_1
74 {j_0, +, 1}_2
77 struct indices
79 /* The object. */
80 tree base_object;
82 /* A list of chrecs. Access functions of the indices. */
83 VEC(tree,heap) *access_fns;
86 struct dr_alias
88 /* The alias information that should be used for new pointers to this
89 location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */
90 struct ptr_info_def *ptr_info;
92 /* The set of virtual operands corresponding to this memory reference,
93 serving as a description of the alias information for the memory
94 reference. This could be eliminated if we had alias oracle. */
95 bitmap vops;
98 /* An integer vector. A vector formally consists of an element of a vector
99 space. A vector space is a set that is closed under vector addition
100 and scalar multiplication. In this vector space, an element is a list of
101 integers. */
102 typedef int *lambda_vector;
103 DEF_VEC_P(lambda_vector);
104 DEF_VEC_ALLOC_P(lambda_vector,heap);
105 DEF_VEC_ALLOC_P(lambda_vector,gc);
107 /* An integer matrix. A matrix consists of m vectors of length n (IE
108 all vectors are the same length). */
109 typedef lambda_vector *lambda_matrix;
111 /* Each vector of the access matrix represents a linear access
112 function for a subscript. First elements correspond to the
113 leftmost indices, ie. for a[i][j] the first vector corresponds to
114 the subscript in "i". The elements of a vector are relative to
115 the loop nests in which the data reference is considered,
116 i.e. the vector is relative to the SCoP that provides the context
117 in which this data reference occurs.
119 For example, in
121 | loop_1
122 | loop_2
123 | a[i+3][2*j+n-1]
125 if "i" varies in loop_1 and "j" varies in loop_2, the access
126 matrix with respect to the loop nest {loop_1, loop_2} is:
128 | loop_1 loop_2 param_n cst
129 | 1 0 0 3
130 | 0 2 1 -1
132 whereas the access matrix with respect to loop_2 considers "i" as
133 a parameter:
135 | loop_2 param_i param_n cst
136 | 0 1 0 3
137 | 2 0 1 -1
139 struct access_matrix
141 VEC (loop_p, heap) *loop_nest;
142 int nb_induction_vars;
143 VEC (tree, heap) *parameters;
144 VEC (lambda_vector, gc) *matrix;
147 #define AM_LOOP_NEST(M) (M)->loop_nest
148 #define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars
149 #define AM_PARAMETERS(M) (M)->parameters
150 #define AM_MATRIX(M) (M)->matrix
151 #define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M)))
152 #define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
153 #define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
154 #define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I)
155 #define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
157 /* Return the column in the access matrix of LOOP_NUM. */
159 static inline int
160 am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num)
162 int i;
163 loop_p l;
165 for (i = 0; VEC_iterate (loop_p, AM_LOOP_NEST (access_matrix), i, l); i++)
166 if (l->num == loop_num)
167 return i;
169 gcc_unreachable();
172 int access_matrix_get_index_for_parameter (tree, struct access_matrix *);
174 struct data_reference
176 /* A pointer to the statement that contains this DR. */
177 gimple stmt;
179 /* A pointer to the memory reference. */
180 tree ref;
182 /* Auxiliary info specific to a pass. */
183 void *aux;
185 /* True when the data reference is in RHS of a stmt. */
186 bool is_read;
188 /* Behavior of the memory reference in the innermost loop. */
189 struct innermost_loop_behavior innermost;
191 /* Subscripts of this data reference. */
192 struct indices indices;
194 /* Alias information for the data reference. */
195 struct dr_alias alias;
197 /* Matrix representation for the data access functions. */
198 struct access_matrix *access_matrix;
201 #define DR_STMT(DR) (DR)->stmt
202 #define DR_REF(DR) (DR)->ref
203 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
204 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
205 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
206 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
207 #define DR_IS_READ(DR) (DR)->is_read
208 #define DR_IS_WRITE(DR) (!DR_IS_READ (DR))
209 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
210 #define DR_OFFSET(DR) (DR)->innermost.offset
211 #define DR_INIT(DR) (DR)->innermost.init
212 #define DR_STEP(DR) (DR)->innermost.step
213 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
214 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to
215 #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix
217 typedef struct data_reference *data_reference_p;
218 DEF_VEC_P(data_reference_p);
219 DEF_VEC_ALLOC_P (data_reference_p, heap);
221 enum data_dependence_direction {
222 dir_positive,
223 dir_negative,
224 dir_equal,
225 dir_positive_or_negative,
226 dir_positive_or_equal,
227 dir_negative_or_equal,
228 dir_star,
229 dir_independent
232 /* The description of the grid of iterations that overlap. At most
233 two loops are considered at the same time just now, hence at most
234 two functions are needed. For each of the functions, we store
235 the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
236 where x, y, ... are variables. */
238 #define MAX_DIM 2
240 /* Special values of N. */
241 #define NO_DEPENDENCE 0
242 #define NOT_KNOWN (MAX_DIM + 1)
243 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
244 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
245 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
247 typedef VEC (tree, heap) *affine_fn;
249 typedef struct
251 unsigned n;
252 affine_fn fns[MAX_DIM];
253 } conflict_function;
255 /* What is a subscript? Given two array accesses a subscript is the
256 tuple composed of the access functions for a given dimension.
257 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
258 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts
259 are stored in the data_dependence_relation structure under the form
260 of an array of subscripts. */
262 struct subscript
264 /* A description of the iterations for which the elements are
265 accessed twice. */
266 conflict_function *conflicting_iterations_in_a;
267 conflict_function *conflicting_iterations_in_b;
269 /* This field stores the information about the iteration domain
270 validity of the dependence relation. */
271 tree last_conflict;
273 /* Distance from the iteration that access a conflicting element in
274 A to the iteration that access this same conflicting element in
275 B. The distance is a tree scalar expression, i.e. a constant or a
276 symbolic expression, but certainly not a chrec function. */
277 tree distance;
280 typedef struct subscript *subscript_p;
281 DEF_VEC_P(subscript_p);
282 DEF_VEC_ALLOC_P (subscript_p, heap);
284 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
285 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
286 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
287 #define SUB_DISTANCE(SUB) SUB->distance
289 /* A data_dependence_relation represents a relation between two
290 data_references A and B. */
292 struct data_dependence_relation
295 struct data_reference *a;
296 struct data_reference *b;
298 /* A "yes/no/maybe" field for the dependence relation:
300 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
301 relation between A and B, and the description of this relation
302 is given in the SUBSCRIPTS array,
304 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
305 SUBSCRIPTS is empty,
307 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
308 but the analyzer cannot be more specific. */
309 tree are_dependent;
311 /* For each subscript in the dependence test, there is an element in
312 this array. This is the attribute that labels the edge A->B of
313 the data_dependence_relation. */
314 VEC (subscript_p, heap) *subscripts;
316 /* The analyzed loop nest. */
317 VEC (loop_p, heap) *loop_nest;
319 /* The classic direction vector. */
320 VEC (lambda_vector, heap) *dir_vects;
322 /* The classic distance vector. */
323 VEC (lambda_vector, heap) *dist_vects;
325 /* An index in loop_nest for the innermost loop that varies for
326 this data dependence relation. */
327 unsigned inner_loop;
329 /* Is the dependence reversed with respect to the lexicographic order? */
330 bool reversed_p;
332 /* When the dependence relation is affine, it can be represented by
333 a distance vector. */
334 bool affine_p;
336 /* Set to true when the dependence relation is on the same data
337 access. */
338 bool self_reference_p;
341 typedef struct data_dependence_relation *ddr_p;
342 DEF_VEC_P(ddr_p);
343 DEF_VEC_ALLOC_P(ddr_p,heap);
345 #define DDR_A(DDR) DDR->a
346 #define DDR_B(DDR) DDR->b
347 #define DDR_AFFINE_P(DDR) DDR->affine_p
348 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
349 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
350 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
351 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
353 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
354 /* The size of the direction/distance vectors: the number of loops in
355 the loop nest. */
356 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
357 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
358 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
360 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
361 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
362 #define DDR_NUM_DIST_VECTS(DDR) \
363 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
364 #define DDR_NUM_DIR_VECTS(DDR) \
365 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
366 #define DDR_DIR_VECT(DDR, I) \
367 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
368 #define DDR_DIST_VECT(DDR, I) \
369 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
370 #define DDR_REVERSED_P(DDR) DDR->reversed_p
374 /* Describes a location of a memory reference. */
376 typedef struct data_ref_loc_d
378 /* Position of the memory reference. */
379 tree *pos;
381 /* True if the memory reference is read. */
382 bool is_read;
383 } data_ref_loc;
385 DEF_VEC_O (data_ref_loc);
386 DEF_VEC_ALLOC_O (data_ref_loc, heap);
388 bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **);
389 bool dr_analyze_innermost (struct data_reference *);
390 extern bool compute_data_dependences_for_loop (struct loop *, bool,
391 VEC (loop_p, heap) **,
392 VEC (data_reference_p, heap) **,
393 VEC (ddr_p, heap) **);
394 extern bool compute_data_dependences_for_bb (basic_block, bool,
395 VEC (data_reference_p, heap) **,
396 VEC (ddr_p, heap) **);
397 extern tree find_data_references_in_loop (struct loop *,
398 VEC (data_reference_p, heap) **);
399 extern void print_direction_vector (FILE *, lambda_vector, int);
400 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
401 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
402 extern void dump_subscript (FILE *, struct subscript *);
403 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
404 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
405 extern void dump_data_reference (FILE *, struct data_reference *);
406 extern void debug_data_reference (struct data_reference *);
407 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
408 extern void debug_data_references (VEC (data_reference_p, heap) *);
409 extern void debug_data_dependence_relation (struct data_dependence_relation *);
410 extern void dump_data_dependence_relation (FILE *,
411 struct data_dependence_relation *);
412 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
413 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
414 extern void dump_data_dependence_direction (FILE *,
415 enum data_dependence_direction);
416 extern void free_dependence_relation (struct data_dependence_relation *);
417 extern void free_dependence_relations (VEC (ddr_p, heap) *);
418 extern void free_data_ref (data_reference_p);
419 extern void free_data_refs (VEC (data_reference_p, heap) *);
420 extern bool find_data_references_in_stmt (struct loop *, gimple,
421 VEC (data_reference_p, heap) **);
422 extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple,
423 VEC (data_reference_p, heap) **);
424 struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool);
425 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
426 extern void compute_all_dependences (VEC (data_reference_p, heap) *,
427 VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
428 bool);
429 extern tree find_data_references_in_bb (struct loop *, basic_block,
430 VEC (data_reference_p, heap) **);
432 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
433 extern bool dr_may_alias_p (const struct data_reference *,
434 const struct data_reference *);
435 extern bool dr_equal_offsets_p (struct data_reference *,
436 struct data_reference *);
439 /* Return true when the base objects of data references A and B are
440 the same memory object. */
442 static inline bool
443 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
445 return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
446 && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
449 /* Return true when the data references A and B are accessing the same
450 memory object with the same access functions. */
452 static inline bool
453 same_data_refs (data_reference_p a, data_reference_p b)
455 unsigned int i;
457 /* The references are exactly the same. */
458 if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
459 return true;
461 if (!same_data_refs_base_objects (a, b))
462 return false;
464 for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
465 if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
466 return false;
468 return true;
471 /* Return true when the DDR contains two data references that have the
472 same access functions. */
474 static inline bool
475 same_access_functions (const struct data_dependence_relation *ddr)
477 unsigned i;
479 for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
480 if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
481 DR_ACCESS_FN (DDR_B (ddr), i)))
482 return false;
484 return true;
487 /* Return true when DDR is an anti-dependence relation. */
489 static inline bool
490 ddr_is_anti_dependent (ddr_p ddr)
492 return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
493 && DR_IS_READ (DDR_A (ddr))
494 && DR_IS_WRITE (DDR_B (ddr))
495 && !same_access_functions (ddr));
498 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */
500 static inline bool
501 ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
503 unsigned i;
504 ddr_p ddr;
506 for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
507 if (ddr_is_anti_dependent (ddr))
508 return true;
510 return false;
513 /* Returns the dependence level for a vector DIST of size LENGTH.
514 LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
515 to the sequence of statements, not carried by any loop. */
517 static inline unsigned
518 dependence_level (lambda_vector dist_vect, int length)
520 int i;
522 for (i = 0; i < length; i++)
523 if (dist_vect[i] != 0)
524 return i + 1;
526 return 0;
529 /* Return the dependence level for the DDR relation. */
531 static inline unsigned
532 ddr_dependence_level (ddr_p ddr)
534 unsigned vector;
535 unsigned level = 0;
537 if (DDR_DIST_VECTS (ddr))
538 level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
540 for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
541 level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
542 DDR_NB_LOOPS (ddr)));
543 return level;
548 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
549 typedef struct rdg_vertex
551 /* The statement represented by this vertex. */
552 gimple stmt;
554 /* True when the statement contains a write to memory. */
555 bool has_mem_write;
557 /* True when the statement contains a read from memory. */
558 bool has_mem_reads;
559 } *rdg_vertex_p;
561 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
562 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
563 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
564 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
565 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
566 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
568 void dump_rdg_vertex (FILE *, struct graph *, int);
569 void debug_rdg_vertex (struct graph *, int);
570 void dump_rdg_component (FILE *, struct graph *, int, bitmap);
571 void debug_rdg_component (struct graph *, int);
572 void dump_rdg (FILE *, struct graph *);
573 void debug_rdg (struct graph *);
574 int rdg_vertex_for_stmt (struct graph *, gimple);
576 /* Data dependence type. */
578 enum rdg_dep_type
580 /* Read After Write (RAW). */
581 flow_dd = 'f',
583 /* Write After Read (WAR). */
584 anti_dd = 'a',
586 /* Write After Write (WAW). */
587 output_dd = 'o',
589 /* Read After Read (RAR). */
590 input_dd = 'i'
593 /* Dependence information attached to an edge of the RDG. */
595 typedef struct rdg_edge
597 /* Type of the dependence. */
598 enum rdg_dep_type type;
600 /* Levels of the dependence: the depth of the loops that carry the
601 dependence. */
602 unsigned level;
604 /* Dependence relation between data dependences, NULL when one of
605 the vertices is a scalar. */
606 ddr_p relation;
607 } *rdg_edge_p;
609 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
610 #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
611 #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
613 struct graph *build_rdg (struct loop *,
614 VEC (loop_p, heap) **,
615 VEC (ddr_p, heap) **,
616 VEC (data_reference_p, heap) **);
617 struct graph *build_empty_rdg (int);
618 void free_rdg (struct graph *);
620 /* Return the index of the variable VAR in the LOOP_NEST array. */
622 static inline int
623 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
625 struct loop *loopi;
626 int var_index;
628 for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
629 var_index++)
630 if (loopi->num == var)
631 break;
633 return var_index;
636 void stores_from_loop (struct loop *, VEC (gimple, heap) **);
637 void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **);
638 void remove_similar_memory_refs (VEC (gimple, heap) **);
639 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
640 bool have_similar_memory_accesses (gimple, gimple);
641 bool stmt_with_adjacent_zero_store_dr_p (gimple);
643 /* Returns true when STRIDE is equal in absolute value to the size of
644 the unit type of TYPE. */
646 static inline bool
647 stride_of_unit_type_p (tree stride, tree type)
649 return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride),
650 stride),
651 TYPE_SIZE_UNIT (type));
654 /* Determines whether RDG vertices V1 and V2 access to similar memory
655 locations, in which case they have to be in the same partition. */
657 static inline bool
658 rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
660 return have_similar_memory_accesses (RDG_STMT (rdg, v1),
661 RDG_STMT (rdg, v2));
664 /* In tree-data-ref.c */
665 void split_constant_offset (tree , tree *, tree *);
667 /* Strongly connected components of the reduced data dependence graph. */
669 typedef struct rdg_component
671 int num;
672 VEC (int, heap) *vertices;
673 } *rdgc;
675 DEF_VEC_P (rdgc);
676 DEF_VEC_ALLOC_P (rdgc, heap);
678 DEF_VEC_P (bitmap);
679 DEF_VEC_ALLOC_P (bitmap, heap);
681 /* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
683 static inline int
684 lambda_vector_gcd (lambda_vector vector, int size)
686 int i;
687 int gcd1 = 0;
689 if (size > 0)
691 gcd1 = vector[0];
692 for (i = 1; i < size; i++)
693 gcd1 = gcd (gcd1, vector[i]);
695 return gcd1;
698 /* Allocate a new vector of given SIZE. */
700 static inline lambda_vector
701 lambda_vector_new (int size)
703 return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size);
706 /* Clear out vector VEC1 of length SIZE. */
708 static inline void
709 lambda_vector_clear (lambda_vector vec1, int size)
711 memset (vec1, 0, size * sizeof (*vec1));
714 /* Returns true when the vector V is lexicographically positive, in
715 other words, when the first nonzero element is positive. */
717 static inline bool
718 lambda_vector_lexico_pos (lambda_vector v,
719 unsigned n)
721 unsigned i;
722 for (i = 0; i < n; i++)
724 if (v[i] == 0)
725 continue;
726 if (v[i] < 0)
727 return false;
728 if (v[i] > 0)
729 return true;
731 return true;
734 /* Return true if vector VEC1 of length SIZE is the zero vector. */
736 static inline bool
737 lambda_vector_zerop (lambda_vector vec1, int size)
739 int i;
740 for (i = 0; i < size; i++)
741 if (vec1[i] != 0)
742 return false;
743 return true;
746 /* Allocate a matrix of M rows x N cols. */
748 static inline lambda_matrix
749 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
751 lambda_matrix mat;
752 int i;
754 mat = (lambda_matrix) obstack_alloc (lambda_obstack,
755 sizeof (lambda_vector *) * m);
757 for (i = 0; i < m; i++)
758 mat[i] = lambda_vector_new (n);
760 return mat;
763 #endif /* GCC_TREE_DATA_REF_H */