1/* Data references and dependences detectors.
2   Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3   Contributed by Sebastian Pop <s.pop@laposte.net>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-1301, USA.  */
21
22#ifndef GCC_TREE_DATA_REF_H
23#define GCC_TREE_DATA_REF_H
24
25#include "lambda.h"
26
27/** {base_address + offset + init} is the first location accessed by data-ref
28      in the loop, and step is the stride of data-ref in the loop in bytes;
29      e.g.:
30
31                       Example 1                      Example 2
32      data-ref         a[j].b[i][j]                   a + x + 16B (a is int*)
33
34First location info:
35      base_address     &a                             a
36      offset           j_0*D_j + i_0*D_i + C_a        x
37      init             C_b                            16
38      step             D_j                            4
39      access_fn        NULL                           {16, +, 1}
40
41Base object info:
42      base_object      a                              NULL
43      access_fn        <access_fns of indexes of b>   NULL
44
45  **/
46struct first_location_in_loop
47{
48  tree base_address;
49  tree offset;
50  tree init;
51  tree step;
52  /* Access function related to first location in the loop.  */
53  VEC(tree,heap) *access_fns;
54
55};
56
57struct base_object_info
58{
59  /* The object.  */
60  tree base_object;
61
62  /* A list of chrecs.  Access functions related to BASE_OBJECT.  */
63  VEC(tree,heap) *access_fns;
64};
65
66enum data_ref_type {
67  ARRAY_REF_TYPE,
68  POINTER_REF_TYPE
69};
70
71struct data_reference
72{
73  /* A pointer to the statement that contains this DR.  */
74  tree stmt;
75
76  /* A pointer to the ARRAY_REF node.  */
77  tree ref;
78
79  /* Auxiliary info specific to a pass.  */
80  int aux;
81
82  /* True when the data reference is in RHS of a stmt.  */
83  bool is_read;
84
85  /* First location accessed by the data-ref in the loop.  */
86  struct first_location_in_loop first_location;
87
88  /* Base object related info.  */
89  struct base_object_info object_info;
90
91  /* Aliasing information.  This field represents the symbol that
92     should be aliased by a pointer holding the address of this data
93     reference.  If the original data reference was a pointer
94     dereference, then this field contains the memory tag that should
95     be used by the new vector-pointer.  */
96  tree memtag;
97  struct ptr_info_def *ptr_info;
98  subvar_t subvars;
99
100  /* Alignment information.  */
101  /* The offset of the data-reference from its base in bytes.  */
102  tree misalignment;
103  /* The maximum data-ref's alignment.  */
104  tree aligned_to;
105
106  /* The type of the data-ref.  */
107  enum data_ref_type type;
108};
109
110#define DR_STMT(DR)                (DR)->stmt
111#define DR_REF(DR)                 (DR)->ref
112#define DR_BASE_OBJECT(DR)         (DR)->object_info.base_object
113#define DR_TYPE(DR)                (DR)->type
114#define DR_ACCESS_FNS(DR)\
115  (DR_TYPE(DR) == ARRAY_REF_TYPE ?  \
116   (DR)->object_info.access_fns : (DR)->first_location.access_fns)
117#define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
118#define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))
119#define DR_IS_READ(DR)             (DR)->is_read
120#define DR_BASE_ADDRESS(DR)        (DR)->first_location.base_address
121#define DR_OFFSET(DR)              (DR)->first_location.offset
122#define DR_INIT(DR)                (DR)->first_location.init
123#define DR_STEP(DR)                (DR)->first_location.step
124#define DR_MEMTAG(DR)              (DR)->memtag
125#define DR_ALIGNED_TO(DR)          (DR)->aligned_to
126#define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
127#define DR_PTR_INFO(DR)            (DR)->ptr_info
128#define DR_SUBVARS(DR)             (DR)->subvars
129
130#define DR_ACCESS_FNS_ADDR(DR)       \
131  (DR_TYPE(DR) == ARRAY_REF_TYPE ?   \
132   &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
133#define DR_SET_ACCESS_FNS(DR, ACC_FNS)         \
134{                                              \
135  if (DR_TYPE(DR) == ARRAY_REF_TYPE)           \
136    (DR)->object_info.access_fns = ACC_FNS;    \
137  else                                         \
138    (DR)->first_location.access_fns = ACC_FNS; \
139}
140#define DR_FREE_ACCESS_FNS(DR)                              \
141{                                                           \
142  if (DR_TYPE(DR) == ARRAY_REF_TYPE)                        \
143    VEC_free (tree, heap, (DR)->object_info.access_fns);    \
144  else                                                      \
145    VEC_free (tree, heap, (DR)->first_location.access_fns); \
146}
147
148enum data_dependence_direction {
149  dir_positive,
150  dir_negative,
151  dir_equal,
152  dir_positive_or_negative,
153  dir_positive_or_equal,
154  dir_negative_or_equal,
155  dir_star,
156  dir_independent
157};
158
159/* What is a subscript?  Given two array accesses a subscript is the
160   tuple composed of the access functions for a given dimension.
161   Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
162   subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
163   are stored in the data_dependence_relation structure under the form
164   of an array of subscripts.  */
165
166struct subscript
167{
168  /* A description of the iterations for which the elements are
169     accessed twice.  */
170  tree conflicting_iterations_in_a;
171  tree conflicting_iterations_in_b;
172
173  /* This field stores the information about the iteration domain
174     validity of the dependence relation.  */
175  tree last_conflict;
176
177  /* Distance from the iteration that access a conflicting element in
178     A to the iteration that access this same conflicting element in
179     B.  The distance is a tree scalar expression, i.e. a constant or a
180     symbolic expression, but certainly not a chrec function.  */
181  tree distance;
182};
183
184#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
185#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
186#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
187#define SUB_DISTANCE(SUB) SUB->distance
188
189/* A data_dependence_relation represents a relation between two
190   data_references A and B.  */
191
192struct data_dependence_relation
193{
194
195  struct data_reference *a;
196  struct data_reference *b;
197
198  /* When the dependence relation is affine, it can be represented by
199     a distance vector.  */
200  bool affine_p;
201
202  /* A "yes/no/maybe" field for the dependence relation:
203
204     - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
205       relation between A and B, and the description of this relation
206       is given in the SUBSCRIPTS array,
207
208     - when "ARE_DEPENDENT == chrec_known", there is no dependence and
209       SUBSCRIPTS is empty,
210
211     - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
212       but the analyzer cannot be more specific.  */
213  tree are_dependent;
214
215  /* For each subscript in the dependence test, there is an element in
216     this array.  This is the attribute that labels the edge A->B of
217     the data_dependence_relation.  */
218  varray_type subscripts;
219
220  /* The size of the direction/distance vectors: the depth of the
221     analyzed loop nest.  */
222  int size_vect;
223
224  /* The classic direction vector.  */
225  VEC(lambda_vector,heap) *dir_vects;
226
227  /* The classic distance vector.  */
228  VEC(lambda_vector,heap) *dist_vects;
229};
230
231#define DDR_A(DDR) DDR->a
232#define DDR_B(DDR) DDR->b
233#define DDR_AFFINE_P(DDR) DDR->affine_p
234#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
235#define DDR_SUBSCRIPTS(DDR) DDR->subscripts
236#define DDR_SUBSCRIPTS_VECTOR_INIT(DDR, N) \
237  VARRAY_GENERIC_PTR_INIT (DDR_SUBSCRIPTS (DDR), N, "subscripts_vector");
238#define DDR_SUBSCRIPT(DDR, I) VARRAY_GENERIC_PTR (DDR_SUBSCRIPTS (DDR), I)
239#define DDR_NUM_SUBSCRIPTS(DDR) VARRAY_ACTIVE_SIZE (DDR_SUBSCRIPTS (DDR))
240#define DDR_SIZE_VECT(DDR) DDR->size_vect
241
242#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
243#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
244#define DDR_NUM_DIST_VECTS(DDR) \
245  (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
246#define DDR_NUM_DIR_VECTS(DDR) \
247  (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
248#define DDR_DIR_VECT(DDR, I) \
249  VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
250#define DDR_DIST_VECT(DDR, I) \
251  VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
252
253
254
255extern tree find_data_references_in_loop (struct loop *, varray_type *);
256extern struct data_dependence_relation *initialize_data_dependence_relation
257(struct data_reference *, struct data_reference *);
258extern void compute_affine_dependence (struct data_dependence_relation *);
259extern void analyze_all_data_dependences (struct loops *);
260extern void compute_data_dependences_for_loop (struct loop *, bool,
261					       varray_type *, varray_type *);
262
263extern void dump_subscript (FILE *, struct subscript *);
264extern void dump_ddrs (FILE *, varray_type);
265extern void dump_dist_dir_vectors (FILE *, varray_type);
266extern void dump_data_reference (FILE *, struct data_reference *);
267extern void dump_data_references (FILE *, varray_type);
268extern void dump_data_dependence_relation (FILE *,
269					   struct data_dependence_relation *);
270extern void dump_data_dependence_relations (FILE *, varray_type);
271extern void dump_data_dependence_direction (FILE *,
272					    enum data_dependence_direction);
273extern void free_dependence_relation (struct data_dependence_relation *);
274extern void free_dependence_relations (varray_type);
275extern void free_data_refs (varray_type);
276extern void compute_subscript_distance (struct data_dependence_relation *);
277extern struct data_reference *analyze_array (tree, tree, bool);
278extern void estimate_iters_using_array (tree, tree);
279
280
281
282
283#endif  /* GCC_TREE_DATA_REF_H  */
284