OSDN Git Service

* dwarf2out.c (gen_compile_unit_die): Use DW_LANG_Go for Go.
[pf3gnuchains/gcc-fork.git] / gcc / tree-data-ref.h
1 /* Data references and dependences detectors.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3    Free Software Foundation, Inc.
4    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5
6 This file is part of GCC.
7
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.
12
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.
17
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/>.  */
21
22 #ifndef GCC_TREE_DATA_REF_H
23 #define GCC_TREE_DATA_REF_H
24
25 #include "graphds.h"
26 #include "omega.h"
27 #include "tree-chrec.h"
28
29 /*
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
35
36   for (i = 0; i < 100; i++)
37     for (j = 3; j < 100; j++)
38
39                        Example 1                      Example 2
40       data-ref         a[j].b[i][j]                   *(p + x + 16B + 4B * j)
41
42
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
48
49   */
50 struct innermost_loop_behavior
51 {
52   tree base_address;
53   tree offset;
54   tree init;
55   tree step;
56
57   /* Alignment information.  ALIGNED_TO is set to the largest power of two
58      that divides OFFSET.  */
59   tree aligned_to;
60 };
61
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,
70
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
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,heap) *access_fns;
84 };
85
86 struct dr_alias
87 {
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;
91
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;
96 };
97
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);
106
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;
110
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.
118
119    For example, in
120
121    | loop_1
122    |    loop_2
123    |      a[i+3][2*j+n-1]
124
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:
127
128    | loop_1  loop_2  param_n  cst
129    |   1       0        0      3
130    |   0       2        1     -1
131
132    whereas the access matrix with respect to loop_2 considers "i" as
133    a parameter:
134
135    | loop_2  param_i  param_n  cst
136    |   0       1         0      3
137    |   2       0         1     -1
138 */
139 struct access_matrix
140 {
141   VEC (loop_p, heap) *loop_nest;
142   int nb_induction_vars;
143   VEC (tree, heap) *parameters;
144   VEC (lambda_vector, gc) *matrix;
145 };
146
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]
156
157 /* Return the column in the access matrix of LOOP_NUM.  */
158
159 static inline int
160 am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num)
161 {
162   int i;
163   loop_p l;
164
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;
168
169   gcc_unreachable();
170 }
171
172 int access_matrix_get_index_for_parameter (tree, struct access_matrix *);
173
174 struct data_reference
175 {
176   /* A pointer to the statement that contains this DR.  */
177   gimple stmt;
178
179   /* A pointer to the memory reference.  */
180   tree ref;
181
182   /* Auxiliary info specific to a pass.  */
183   void *aux;
184
185   /* True when the data reference is in RHS of a stmt.  */
186   bool is_read;
187
188   /* Behavior of the memory reference in the innermost loop.  */
189   struct innermost_loop_behavior innermost;
190
191   /* Subscripts of this data reference.  */
192   struct indices indices;
193
194   /* Alias information for the data reference.  */
195   struct dr_alias alias;
196
197   /* Matrix representation for the data access functions.  */
198   struct access_matrix *access_matrix;
199 };
200
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
216
217 typedef struct data_reference *data_reference_p;
218 DEF_VEC_P(data_reference_p);
219 DEF_VEC_ALLOC_P (data_reference_p, heap);
220
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
230 };
231
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.  */
237
238 #define MAX_DIM 2
239
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)
246
247 typedef VEC (tree, heap) *affine_fn;
248
249 typedef struct
250 {
251   unsigned n;
252   affine_fn fns[MAX_DIM];
253 } conflict_function;
254
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.  */
261
262 struct subscript
263 {
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;
268
269   /* This field stores the information about the iteration domain
270      validity of the dependence relation.  */
271   tree last_conflict;
272
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;
278 };
279
280 typedef struct subscript *subscript_p;
281 DEF_VEC_P(subscript_p);
282 DEF_VEC_ALLOC_P (subscript_p, heap);
283
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
288
289 /* A data_dependence_relation represents a relation between two
290    data_references A and B.  */
291
292 struct data_dependence_relation
293 {
294
295   struct data_reference *a;
296   struct data_reference *b;
297
298   /* A "yes/no/maybe" field for the dependence relation:
299
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,
303
304      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
305        SUBSCRIPTS is empty,
306
307      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
308        but the analyzer cannot be more specific.  */
309   tree are_dependent;
310
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;
315
316   /* The analyzed loop nest.  */
317   VEC (loop_p, heap) *loop_nest;
318
319   /* The classic direction vector.  */
320   VEC (lambda_vector, heap) *dir_vects;
321
322   /* The classic distance vector.  */
323   VEC (lambda_vector, heap) *dist_vects;
324
325   /* An index in loop_nest for the innermost loop that varies for
326      this data dependence relation.  */
327   unsigned inner_loop;
328
329   /* Is the dependence reversed with respect to the lexicographic order?  */
330   bool reversed_p;
331
332   /* When the dependence relation is affine, it can be represented by
333      a distance vector.  */
334   bool affine_p;
335
336   /* Set to true when the dependence relation is on the same data
337      access.  */
338   bool self_reference_p;
339 };
340
341 typedef struct data_dependence_relation *ddr_p;
342 DEF_VEC_P(ddr_p);
343 DEF_VEC_ALLOC_P(ddr_p,heap);
344
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))
352
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
359
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
371
372 \f
373
374 /* Describes a location of a memory reference.  */
375
376 typedef struct data_ref_loc_d
377 {
378   /* Position of the memory reference.  */
379   tree *pos;
380
381   /* True if the memory reference is read.  */
382   bool is_read;
383 } data_ref_loc;
384
385 DEF_VEC_O (data_ref_loc);
386 DEF_VEC_ALLOC_O (data_ref_loc, heap);
387
388 bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **);
389 bool dr_analyze_innermost (struct data_reference *, struct loop *);
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 struct data_dependence_relation *initialize_data_dependence_relation
427      (struct data_reference *, struct data_reference *, VEC (loop_p, heap) *); 
428 extern void compute_self_dependence (struct data_dependence_relation *);
429 extern void compute_all_dependences (VEC (data_reference_p, heap) *,
430                                      VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
431                                      bool);
432 extern tree find_data_references_in_bb (struct loop *, basic_block,
433                                         VEC (data_reference_p, heap) **);
434
435 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
436 extern bool dr_may_alias_p (const struct data_reference *,
437                             const struct data_reference *, bool);
438 extern bool dr_equal_offsets_p (struct data_reference *,
439                                 struct data_reference *);
440
441
442 /* Return true when the base objects of data references A and B are
443    the same memory object.  */
444
445 static inline bool
446 same_data_refs_base_objects (data_reference_p a, data_reference_p b)
447 {
448   return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b)
449     && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0);
450 }
451
452 /* Return true when the data references A and B are accessing the same
453    memory object with the same access functions.  */
454
455 static inline bool
456 same_data_refs (data_reference_p a, data_reference_p b)
457 {
458   unsigned int i;
459
460   /* The references are exactly the same.  */
461   if (operand_equal_p (DR_REF (a), DR_REF (b), 0))
462     return true;
463
464   if (!same_data_refs_base_objects (a, b))
465     return false;
466
467   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
468     if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i)))
469       return false;
470
471   return true;
472 }
473
474 /* Return true when the DDR contains two data references that have the
475    same access functions.  */
476
477 static inline bool
478 same_access_functions (const struct data_dependence_relation *ddr)
479 {
480   unsigned i;
481
482   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
483     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
484                           DR_ACCESS_FN (DDR_B (ddr), i)))
485       return false;
486
487   return true;
488 }
489
490 /* Return true when DDR is an anti-dependence relation.  */
491
492 static inline bool
493 ddr_is_anti_dependent (ddr_p ddr)
494 {
495   return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
496           && DR_IS_READ (DDR_A (ddr))
497           && DR_IS_WRITE (DDR_B (ddr))
498           && !same_access_functions (ddr));
499 }
500
501 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence.  */
502
503 static inline bool
504 ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
505 {
506   unsigned i;
507   ddr_p ddr;
508
509   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
510     if (ddr_is_anti_dependent (ddr))
511       return true;
512
513   return false;
514 }
515
516 /* Returns the dependence level for a vector DIST of size LENGTH.
517    LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
518    to the sequence of statements, not carried by any loop.  */
519
520 static inline unsigned
521 dependence_level (lambda_vector dist_vect, int length)
522 {
523   int i;
524
525   for (i = 0; i < length; i++)
526     if (dist_vect[i] != 0)
527       return i + 1;
528
529   return 0;
530 }
531
532 /* Return the dependence level for the DDR relation.  */
533
534 static inline unsigned
535 ddr_dependence_level (ddr_p ddr)
536 {
537   unsigned vector;
538   unsigned level = 0;
539
540   if (DDR_DIST_VECTS (ddr))
541     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
542
543   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
544     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
545                                           DDR_NB_LOOPS (ddr)));
546   return level;
547 }
548
549 \f
550
551 /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
552 typedef struct rdg_vertex
553 {
554   /* The statement represented by this vertex.  */
555   gimple stmt;
556
557   /* True when the statement contains a write to memory.  */
558   bool has_mem_write;
559
560   /* True when the statement contains a read from memory.  */
561   bool has_mem_reads;
562 } *rdg_vertex_p;
563
564 #define RDGV_STMT(V)     ((struct rdg_vertex *) ((V)->data))->stmt
565 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
566 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
567 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
568 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
569 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
570
571 void dump_rdg_vertex (FILE *, struct graph *, int);
572 void debug_rdg_vertex (struct graph *, int);
573 void dump_rdg_component (FILE *, struct graph *, int, bitmap);
574 void debug_rdg_component (struct graph *, int);
575 void dump_rdg (FILE *, struct graph *);
576 void debug_rdg (struct graph *);
577 int rdg_vertex_for_stmt (struct graph *, gimple);
578
579 /* Data dependence type.  */
580
581 enum rdg_dep_type
582 {
583   /* Read After Write (RAW).  */
584   flow_dd = 'f',
585
586   /* Write After Read (WAR).  */
587   anti_dd = 'a',
588
589   /* Write After Write (WAW).  */
590   output_dd = 'o',
591
592   /* Read After Read (RAR).  */
593   input_dd = 'i'
594 };
595
596 /* Dependence information attached to an edge of the RDG.  */
597
598 typedef struct rdg_edge
599 {
600   /* Type of the dependence.  */
601   enum rdg_dep_type type;
602
603   /* Levels of the dependence: the depth of the loops that carry the
604      dependence.  */
605   unsigned level;
606
607   /* Dependence relation between data dependences, NULL when one of
608      the vertices is a scalar.  */
609   ddr_p relation;
610 } *rdg_edge_p;
611
612 #define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
613 #define RDGE_LEVEL(E)       ((struct rdg_edge *) ((E)->data))->level
614 #define RDGE_RELATION(E)    ((struct rdg_edge *) ((E)->data))->relation
615
616 struct graph *build_rdg (struct loop *,
617                          VEC (loop_p, heap) **,
618                          VEC (ddr_p, heap) **,
619                          VEC (data_reference_p, heap) **);
620 struct graph *build_empty_rdg (int);
621 void free_rdg (struct graph *);
622
623 /* Return the index of the variable VAR in the LOOP_NEST array.  */
624
625 static inline int
626 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
627 {
628   struct loop *loopi;
629   int var_index;
630
631   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
632        var_index++)
633     if (loopi->num == var)
634       break;
635
636   return var_index;
637 }
638
639 void stores_from_loop (struct loop *, VEC (gimple, heap) **);
640 void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **);
641 void remove_similar_memory_refs (VEC (gimple, heap) **);
642 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
643 bool have_similar_memory_accesses (gimple, gimple);
644 bool stmt_with_adjacent_zero_store_dr_p (gimple);
645
646 /* Returns true when STRIDE is equal in absolute value to the size of
647    the unit type of TYPE.  */
648
649 static inline bool
650 stride_of_unit_type_p (tree stride, tree type)
651 {
652   return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride),
653                                          stride),
654                              TYPE_SIZE_UNIT (type));
655 }
656
657 /* Determines whether RDG vertices V1 and V2 access to similar memory
658    locations, in which case they have to be in the same partition.  */
659
660 static inline bool
661 rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
662 {
663   return have_similar_memory_accesses (RDG_STMT (rdg, v1),
664                                        RDG_STMT (rdg, v2));
665 }
666
667 /* In tree-data-ref.c  */
668 void split_constant_offset (tree , tree *, tree *);
669
670 /* Strongly connected components of the reduced data dependence graph.  */
671
672 typedef struct rdg_component
673 {
674   int num;
675   VEC (int, heap) *vertices;
676 } *rdgc;
677
678 DEF_VEC_P (rdgc);
679 DEF_VEC_ALLOC_P (rdgc, heap);
680
681 DEF_VEC_P (bitmap);
682 DEF_VEC_ALLOC_P (bitmap, heap);
683
684 /* Compute the greatest common divisor of a VECTOR of SIZE numbers.  */
685
686 static inline int
687 lambda_vector_gcd (lambda_vector vector, int size)
688 {
689   int i;
690   int gcd1 = 0;
691
692   if (size > 0)
693     {
694       gcd1 = vector[0];
695       for (i = 1; i < size; i++)
696         gcd1 = gcd (gcd1, vector[i]);
697     }
698   return gcd1;
699 }
700
701 /* Allocate a new vector of given SIZE.  */
702
703 static inline lambda_vector
704 lambda_vector_new (int size)
705 {
706   return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size);
707 }
708
709 /* Clear out vector VEC1 of length SIZE.  */
710
711 static inline void
712 lambda_vector_clear (lambda_vector vec1, int size)
713 {
714   memset (vec1, 0, size * sizeof (*vec1));
715 }
716
717 /* Returns true when the vector V is lexicographically positive, in
718    other words, when the first nonzero element is positive.  */
719
720 static inline bool
721 lambda_vector_lexico_pos (lambda_vector v,
722                           unsigned n)
723 {
724   unsigned i;
725   for (i = 0; i < n; i++)
726     {
727       if (v[i] == 0)
728         continue;
729       if (v[i] < 0)
730         return false;
731       if (v[i] > 0)
732         return true;
733     }
734   return true;
735 }
736
737 /* Return true if vector VEC1 of length SIZE is the zero vector.  */
738
739 static inline bool
740 lambda_vector_zerop (lambda_vector vec1, int size)
741 {
742   int i;
743   for (i = 0; i < size; i++)
744     if (vec1[i] != 0)
745       return false;
746   return true;
747 }
748
749 /* Allocate a matrix of M rows x  N cols.  */
750
751 static inline lambda_matrix
752 lambda_matrix_new (int m, int n, struct obstack *lambda_obstack)
753 {
754   lambda_matrix mat;
755   int i;
756
757   mat = (lambda_matrix) obstack_alloc (lambda_obstack,
758                                        sizeof (lambda_vector *) * m);
759
760   for (i = 0; i < m; i++)
761     mat[i] = lambda_vector_new (n);
762
763   return mat;
764 }
765
766 #endif  /* GCC_TREE_DATA_REF_H  */