OSDN Git Service

2008-05-16 Sebastian Pop <sebastian.pop@amd.com>
[pf3gnuchains/gcc-fork.git] / gcc / tree-data-ref.h
1 /* Data references and dependences detectors. 
2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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 "lambda.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   tree symbol_tag;
91   struct ptr_info_def *ptr_info;
92
93   /* The set of virtual operands corresponding to this memory reference,
94      serving as a description of the alias information for the memory
95      reference.  This could be eliminated if we had alias oracle.  */
96   bitmap vops;
97 };
98
99 struct data_reference
100 {
101   /* A pointer to the statement that contains this DR.  */
102   tree stmt;
103   
104   /* A pointer to the memory reference.  */
105   tree ref;
106
107   /* Auxiliary info specific to a pass.  */
108   void *aux;
109
110   /* True when the data reference is in RHS of a stmt.  */
111   bool is_read;
112
113   /* Behavior of the memory reference in the innermost loop.  */
114   struct innermost_loop_behavior innermost;
115
116   /* Decomposition to indices for alias analysis.  */
117   struct indices indices;
118
119   /* Alias information for the data reference.  */
120   struct dr_alias alias;
121 };
122
123 typedef struct data_reference *data_reference_p;
124 DEF_VEC_P(data_reference_p);
125 DEF_VEC_ALLOC_P (data_reference_p, heap);
126
127 #define DR_STMT(DR)                (DR)->stmt
128 #define DR_REF(DR)                 (DR)->ref
129 #define DR_BASE_OBJECT(DR)         (DR)->indices.base_object
130 #define DR_ACCESS_FNS(DR)          (DR)->indices.access_fns
131 #define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
132 #define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))  
133 #define DR_IS_READ(DR)             (DR)->is_read
134 #define DR_BASE_ADDRESS(DR)        (DR)->innermost.base_address
135 #define DR_OFFSET(DR)              (DR)->innermost.offset
136 #define DR_INIT(DR)                (DR)->innermost.init
137 #define DR_STEP(DR)                (DR)->innermost.step
138 #define DR_SYMBOL_TAG(DR)          (DR)->alias.symbol_tag
139 #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
140 #define DR_VOPS(DR)                (DR)->alias.vops
141 #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
142
143 enum data_dependence_direction {
144   dir_positive, 
145   dir_negative, 
146   dir_equal, 
147   dir_positive_or_negative,
148   dir_positive_or_equal,
149   dir_negative_or_equal,
150   dir_star,
151   dir_independent
152 };
153
154 /* The description of the grid of iterations that overlap.  At most
155    two loops are considered at the same time just now, hence at most
156    two functions are needed.  For each of the functions, we store
157    the vector of coefficients, f[0] + x * f[1] + y * f[2] + ...,
158    where x, y, ... are variables.  */
159
160 #define MAX_DIM 2
161
162 /* Special values of N.  */
163 #define NO_DEPENDENCE 0
164 #define NOT_KNOWN (MAX_DIM + 1)
165 #define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN)
166 #define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN)
167 #define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE)
168
169 typedef VEC (tree, heap) *affine_fn;
170
171 typedef struct
172 {
173   unsigned n;
174   affine_fn fns[MAX_DIM];
175 } conflict_function;
176
177 /* What is a subscript?  Given two array accesses a subscript is the
178    tuple composed of the access functions for a given dimension.
179    Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
180    subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
181    are stored in the data_dependence_relation structure under the form
182    of an array of subscripts.  */
183
184 struct subscript
185 {
186   /* A description of the iterations for which the elements are
187      accessed twice.  */
188   conflict_function *conflicting_iterations_in_a;
189   conflict_function *conflicting_iterations_in_b;
190   
191   /* This field stores the information about the iteration domain
192      validity of the dependence relation.  */
193   tree last_conflict;
194   
195   /* Distance from the iteration that access a conflicting element in
196      A to the iteration that access this same conflicting element in
197      B.  The distance is a tree scalar expression, i.e. a constant or a
198      symbolic expression, but certainly not a chrec function.  */
199   tree distance;
200 };
201
202 typedef struct subscript *subscript_p;
203 DEF_VEC_P(subscript_p);
204 DEF_VEC_ALLOC_P (subscript_p, heap);
205
206 #define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
207 #define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
208 #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
209 #define SUB_DISTANCE(SUB) SUB->distance
210
211 /* A data_dependence_relation represents a relation between two
212    data_references A and B.  */
213
214 struct data_dependence_relation
215 {
216   
217   struct data_reference *a;
218   struct data_reference *b;
219
220   /* When the dependence relation is affine, it can be represented by
221      a distance vector.  */
222   bool affine_p;
223
224   /* Set to true when the dependence relation is on the same data
225      access.  */
226   bool self_reference_p;
227
228   /* A "yes/no/maybe" field for the dependence relation:
229      
230      - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
231        relation between A and B, and the description of this relation
232        is given in the SUBSCRIPTS array,
233      
234      - when "ARE_DEPENDENT == chrec_known", there is no dependence and
235        SUBSCRIPTS is empty,
236      
237      - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
238        but the analyzer cannot be more specific.  */
239   tree are_dependent;
240   
241   /* For each subscript in the dependence test, there is an element in
242      this array.  This is the attribute that labels the edge A->B of
243      the data_dependence_relation.  */
244   VEC (subscript_p, heap) *subscripts;
245
246   /* The analyzed loop nest.  */
247   VEC (loop_p, heap) *loop_nest;
248
249   /* An index in loop_nest for the innermost loop that varies for
250      this data dependence relation.  */
251   unsigned inner_loop;
252
253   /* The classic direction vector.  */
254   VEC (lambda_vector, heap) *dir_vects;
255
256   /* The classic distance vector.  */
257   VEC (lambda_vector, heap) *dist_vects;
258
259   /* Is the dependence reversed with respect to the lexicographic order?  */
260   bool reversed_p;
261 };
262
263 typedef struct data_dependence_relation *ddr_p;
264 DEF_VEC_P(ddr_p);
265 DEF_VEC_ALLOC_P(ddr_p,heap);
266
267 #define DDR_A(DDR) DDR->a
268 #define DDR_B(DDR) DDR->b
269 #define DDR_AFFINE_P(DDR) DDR->affine_p
270 #define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
271 #define DDR_SUBSCRIPTS(DDR) DDR->subscripts
272 #define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
273 #define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
274
275 #define DDR_LOOP_NEST(DDR) DDR->loop_nest
276 /* The size of the direction/distance vectors: the number of loops in
277    the loop nest.  */
278 #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
279 #define DDR_INNER_LOOP(DDR) DDR->inner_loop
280 #define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p
281
282 #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
283 #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
284 #define DDR_NUM_DIST_VECTS(DDR) \
285   (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
286 #define DDR_NUM_DIR_VECTS(DDR) \
287   (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
288 #define DDR_DIR_VECT(DDR, I) \
289   VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
290 #define DDR_DIST_VECT(DDR, I) \
291   VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
292 #define DDR_REVERSED_P(DDR) DDR->reversed_p
293
294 \f
295
296 /* Describes a location of a memory reference.  */
297
298 typedef struct data_ref_loc_d
299 {
300   /* Position of the memory reference.  */
301   tree *pos;
302
303   /* True if the memory reference is read.  */
304   bool is_read;
305 } data_ref_loc;
306
307 DEF_VEC_O (data_ref_loc);
308 DEF_VEC_ALLOC_O (data_ref_loc, heap);
309
310 bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
311 void dr_analyze_innermost (struct data_reference *);
312 extern void compute_data_dependences_for_loop (struct loop *, bool,
313                                                VEC (data_reference_p, heap) **,
314                                                VEC (ddr_p, heap) **);
315 extern void print_direction_vector (FILE *, lambda_vector, int);
316 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
317 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
318 extern void dump_subscript (FILE *, struct subscript *);
319 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
320 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
321 extern void dump_data_reference (FILE *, struct data_reference *);
322 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
323 extern void debug_data_dependence_relation (struct data_dependence_relation *);
324 extern void dump_data_dependence_relation (FILE *, 
325                                            struct data_dependence_relation *);
326 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
327 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
328 extern void dump_data_dependence_direction (FILE *, 
329                                             enum data_dependence_direction);
330 extern void free_dependence_relation (struct data_dependence_relation *);
331 extern void free_dependence_relations (VEC (ddr_p, heap) *);
332 extern void free_data_ref (data_reference_p);
333 extern void free_data_refs (VEC (data_reference_p, heap) *);
334 struct data_reference *create_data_ref (struct loop *, tree, tree, bool);
335 bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
336 void compute_all_dependences (VEC (data_reference_p, heap) *,
337                               VEC (ddr_p, heap) **, VEC (loop_p, heap) *, bool);
338
339 /* Return true when the DDR contains two data references that have the
340    same access functions.  */
341
342 static inline bool
343 same_access_functions (const struct data_dependence_relation *ddr)
344 {
345   unsigned i;
346
347   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
348     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
349                           DR_ACCESS_FN (DDR_B (ddr), i)))
350       return false;
351
352   return true;
353 }
354
355 /* Return true when DDR is an anti-dependence relation.  */
356
357 static inline bool
358 ddr_is_anti_dependent (ddr_p ddr)
359 {
360   return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
361           && DR_IS_READ (DDR_A (ddr))
362           && !DR_IS_READ (DDR_B (ddr))
363           && !same_access_functions (ddr));
364 }
365
366 /* Return true when DEPENDENCE_RELATIONS contains an anti-dependence.  */
367
368 static inline bool
369 ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations)
370 {
371   unsigned i;
372   ddr_p ddr;
373
374   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
375     if (ddr_is_anti_dependent (ddr))
376       return true;
377
378   return false;
379 }
380
381 /* Return the dependence level for the DDR relation.  */
382
383 static inline unsigned
384 ddr_dependence_level (ddr_p ddr)
385 {
386   unsigned vector;
387   unsigned level = 0;
388
389   if (DDR_DIST_VECTS (ddr))
390     level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr));
391
392   for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++)
393     level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector),
394                                           DDR_NB_LOOPS (ddr)));
395   return level;
396 }
397
398 \f
399
400 /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
401 typedef struct rdg_vertex
402 {
403   /* The statement represented by this vertex.  */
404   tree stmt;
405
406   /* True when the statement contains a write to memory.  */
407   bool has_mem_write;
408
409   /* True when the statement contains a read from memory.  */
410   bool has_mem_reads;
411 } *rdg_vertex_p;
412
413 #define RDGV_STMT(V)     ((struct rdg_vertex *) ((V)->data))->stmt
414 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
415 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
416 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
417 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
418 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
419
420 void dump_rdg_vertex (FILE *, struct graph *, int);
421 void debug_rdg_vertex (struct graph *, int);
422 void dump_rdg_component (FILE *, struct graph *, int, bitmap);
423 void debug_rdg_component (struct graph *, int);
424 void dump_rdg (FILE *, struct graph *);
425 void debug_rdg (struct graph *);
426 void dot_rdg (struct graph *);
427 int rdg_vertex_for_stmt (struct graph *, tree);
428
429 /* Data dependence type.  */
430
431 enum rdg_dep_type 
432 {
433   /* Read After Write (RAW).  */
434   flow_dd = 'f',
435   
436   /* Write After Read (WAR).  */
437   anti_dd = 'a',
438   
439   /* Write After Write (WAW).  */
440   output_dd = 'o', 
441   
442   /* Read After Read (RAR).  */
443   input_dd = 'i' 
444 };
445
446 /* Dependence information attached to an edge of the RDG.  */
447
448 typedef struct rdg_edge 
449 {
450   /* Type of the dependence.  */
451   enum rdg_dep_type type;
452
453   /* Levels of the dependence: the depth of the loops that
454     carry the dependence.  */
455   unsigned level;
456 } *rdg_edge_p;
457
458 #define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
459 #define RDGE_LEVEL(E)       ((struct rdg_edge *) ((E)->data))->level
460
461 struct graph *build_rdg (struct loop *);
462 void free_rdg (struct graph *);
463
464 /* Return the index of the variable VAR in the LOOP_NEST array.  */
465
466 static inline int
467 index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
468 {
469   struct loop *loopi;
470   int var_index;
471
472   for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
473        var_index++)
474     if (loopi->num == var)
475       break;
476
477   return var_index;
478 }
479
480 void stores_from_loop (struct loop *, VEC (tree, heap) **);
481 void remove_similar_memory_refs (VEC (tree, heap) **);
482 bool rdg_defs_used_in_other_loops_p (struct graph *, int);
483 bool have_similar_memory_accesses (tree, tree);
484
485 /* Determines whether RDG vertices V1 and V2 access to similar memory
486    locations, in which case they have to be in the same partition.  */
487
488 static inline bool
489 rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2)
490 {
491   return have_similar_memory_accesses (RDG_STMT (rdg, v1),
492                                        RDG_STMT (rdg, v2));
493 }
494
495 /* In lambda-code.c  */
496 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
497
498 /* In tree-data-refs.c  */
499 void split_constant_offset (tree , tree *, tree *);
500
501 #endif  /* GCC_TREE_DATA_REF_H  */