OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-data-ref.h] - Blame information for rev 867

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* 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 "lambda.h"
25
 
26
/** {base_address + offset + init} is the first location accessed by data-ref
27
      in the loop, and step is the stride of data-ref in the loop in bytes;
28
      e.g.:
29
 
30
                       Example 1                      Example 2
31
      data-ref         a[j].b[i][j]                   a + x + 16B (a is int*)
32
 
33
First location info:
34
      base_address     &a                             a
35
      offset           j_0*D_j + i_0*D_i + C_a        x
36
      init             C_b                            16
37
      step             D_j                            4
38
      access_fn        NULL                           {16, +, 1}
39
 
40
Base object info:
41
      base_object      a                              NULL
42
      access_fn        <access_fns of indexes of b>   NULL
43
 
44
  **/
45
struct first_location_in_loop
46
{
47
  tree base_address;
48
  tree offset;
49
  tree init;
50
  tree step;
51
  /* Access function related to first location in the loop.  */
52
  VEC(tree,heap) *access_fns;
53
 
54
};
55
 
56
struct base_object_info
57
{
58
  /* The object.  */
59
  tree base_object;
60
 
61
  /* A list of chrecs.  Access functions related to BASE_OBJECT.  */
62
  VEC(tree,heap) *access_fns;
63
};
64
 
65
enum data_ref_type {
66
  ARRAY_REF_TYPE,
67
  POINTER_REF_TYPE
68
};
69
 
70
struct data_reference
71
{
72
  /* A pointer to the statement that contains this DR.  */
73
  tree stmt;
74
 
75
  /* A pointer to the ARRAY_REF node.  */
76
  tree ref;
77
 
78
  /* Auxiliary info specific to a pass.  */
79
  int aux;
80
 
81
  /* True when the data reference is in RHS of a stmt.  */
82
  bool is_read;
83
 
84
  /* First location accessed by the data-ref in the loop.  */
85
  struct first_location_in_loop first_location;
86
 
87
  /* Base object related info.  */
88
  struct base_object_info object_info;
89
 
90
  /* Aliasing information.  This field represents the symbol that
91
     should be aliased by a pointer holding the address of this data
92
     reference.  If the original data reference was a pointer
93
     dereference, then this field contains the memory tag that should
94
     be used by the new vector-pointer.  */
95
  tree memtag;
96
  struct ptr_info_def *ptr_info;
97
  subvar_t subvars;
98
 
99
  /* Alignment information.  */
100
  /* The offset of the data-reference from its base in bytes.  */
101
  tree misalignment;
102
  /* The maximum data-ref's alignment.  */
103
  tree aligned_to;
104
 
105
  /* The type of the data-ref.  */
106
  enum data_ref_type type;
107
};
108
 
109
typedef struct data_reference *data_reference_p;
110
DEF_VEC_P(data_reference_p);
111
DEF_VEC_ALLOC_P (data_reference_p, heap);
112
 
113
#define DR_STMT(DR)                (DR)->stmt
114
#define DR_REF(DR)                 (DR)->ref
115
#define DR_BASE_OBJECT(DR)         (DR)->object_info.base_object
116
#define DR_TYPE(DR)                (DR)->type
117
#define DR_ACCESS_FNS(DR)\
118
  (DR_TYPE(DR) == ARRAY_REF_TYPE ?  \
119
   (DR)->object_info.access_fns : (DR)->first_location.access_fns)
120
#define DR_ACCESS_FN(DR, I)        VEC_index (tree, DR_ACCESS_FNS (DR), I)
121
#define DR_NUM_DIMENSIONS(DR)      VEC_length (tree, DR_ACCESS_FNS (DR))  
122
#define DR_IS_READ(DR)             (DR)->is_read
123
#define DR_BASE_ADDRESS(DR)        (DR)->first_location.base_address
124
#define DR_OFFSET(DR)              (DR)->first_location.offset
125
#define DR_INIT(DR)                (DR)->first_location.init
126
#define DR_STEP(DR)                (DR)->first_location.step
127
#define DR_MEMTAG(DR)              (DR)->memtag
128
#define DR_ALIGNED_TO(DR)          (DR)->aligned_to
129
#define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment
130
#define DR_PTR_INFO(DR)            (DR)->ptr_info
131
#define DR_SUBVARS(DR)             (DR)->subvars
132
 
133
#define DR_ACCESS_FNS_ADDR(DR)       \
134
  (DR_TYPE(DR) == ARRAY_REF_TYPE ?   \
135
   &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns))
136
#define DR_SET_ACCESS_FNS(DR, ACC_FNS)         \
137
{                                              \
138
  if (DR_TYPE(DR) == ARRAY_REF_TYPE)           \
139
    (DR)->object_info.access_fns = ACC_FNS;    \
140
  else                                         \
141
    (DR)->first_location.access_fns = ACC_FNS; \
142
}
143
#define DR_FREE_ACCESS_FNS(DR)                              \
144
{                                                           \
145
  if (DR_TYPE(DR) == ARRAY_REF_TYPE)                        \
146
    VEC_free (tree, heap, (DR)->object_info.access_fns);    \
147
  else                                                      \
148
    VEC_free (tree, heap, (DR)->first_location.access_fns); \
149
}
150
 
151
enum data_dependence_direction {
152
  dir_positive,
153
  dir_negative,
154
  dir_equal,
155
  dir_positive_or_negative,
156
  dir_positive_or_equal,
157
  dir_negative_or_equal,
158
  dir_star,
159
  dir_independent
160
};
161
 
162
/* What is a subscript?  Given two array accesses a subscript is the
163
   tuple composed of the access functions for a given dimension.
164
   Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three
165
   subscripts: (f1, g1), (f2, g2), (f3, g3).  These three subscripts
166
   are stored in the data_dependence_relation structure under the form
167
   of an array of subscripts.  */
168
 
169
struct subscript
170
{
171
  /* A description of the iterations for which the elements are
172
     accessed twice.  */
173
  tree conflicting_iterations_in_a;
174
  tree conflicting_iterations_in_b;
175
 
176
  /* This field stores the information about the iteration domain
177
     validity of the dependence relation.  */
178
  tree last_conflict;
179
 
180
  /* Distance from the iteration that access a conflicting element in
181
     A to the iteration that access this same conflicting element in
182
     B.  The distance is a tree scalar expression, i.e. a constant or a
183
     symbolic expression, but certainly not a chrec function.  */
184
  tree distance;
185
};
186
 
187
typedef struct subscript *subscript_p;
188
DEF_VEC_P(subscript_p);
189
DEF_VEC_ALLOC_P (subscript_p, heap);
190
 
191
#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a
192
#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b
193
#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict
194
#define SUB_DISTANCE(SUB) SUB->distance
195
 
196
typedef struct loop *loop_p;
197
DEF_VEC_P(loop_p);
198
DEF_VEC_ALLOC_P (loop_p, heap);
199
 
200
/* A data_dependence_relation represents a relation between two
201
   data_references A and B.  */
202
 
203
struct data_dependence_relation
204
{
205
 
206
  struct data_reference *a;
207
  struct data_reference *b;
208
 
209
  /* When the dependence relation is affine, it can be represented by
210
     a distance vector.  */
211
  bool affine_p;
212
 
213
  /* A "yes/no/maybe" field for the dependence relation:
214
 
215
     - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
216
       relation between A and B, and the description of this relation
217
       is given in the SUBSCRIPTS array,
218
 
219
     - when "ARE_DEPENDENT == chrec_known", there is no dependence and
220
       SUBSCRIPTS is empty,
221
 
222
     - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
223
       but the analyzer cannot be more specific.  */
224
  tree are_dependent;
225
 
226
  /* For each subscript in the dependence test, there is an element in
227
     this array.  This is the attribute that labels the edge A->B of
228
     the data_dependence_relation.  */
229
  VEC (subscript_p, heap) *subscripts;
230
 
231
  /* The analyzed loop nest.  */
232
  VEC (loop_p, heap) *loop_nest;
233
 
234
  /* The classic direction vector.  */
235
  VEC (lambda_vector, heap) *dir_vects;
236
 
237
  /* The classic distance vector.  */
238
  VEC (lambda_vector, heap) *dist_vects;
239
};
240
 
241
typedef struct data_dependence_relation *ddr_p;
242
DEF_VEC_P(ddr_p);
243
DEF_VEC_ALLOC_P(ddr_p,heap);
244
 
245
#define DDR_A(DDR) DDR->a
246
#define DDR_B(DDR) DDR->b
247
#define DDR_AFFINE_P(DDR) DDR->affine_p
248
#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent
249
#define DDR_SUBSCRIPTS(DDR) DDR->subscripts
250
#define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I)
251
#define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR))
252
 
253
#define DDR_LOOP_NEST(DDR) DDR->loop_nest
254
/* The size of the direction/distance vectors: the number of loops in
255
   the loop nest.  */
256
#define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR)))
257
 
258
#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects)
259
#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects)
260
#define DDR_NUM_DIST_VECTS(DDR) \
261
  (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR)))
262
#define DDR_NUM_DIR_VECTS(DDR) \
263
  (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR)))
264
#define DDR_DIR_VECT(DDR, I) \
265
  VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I)
266
#define DDR_DIST_VECT(DDR, I) \
267
  VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I)
268
 
269
 
270
 
271
extern tree find_data_references_in_loop (struct loop *,
272
                                          VEC (data_reference_p, heap) **);
273
extern void compute_data_dependences_for_loop (struct loop *, bool,
274
                                               VEC (data_reference_p, heap) **,
275
                                               VEC (ddr_p, heap) **);
276
extern void print_direction_vector (FILE *, lambda_vector, int);
277
extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
278
extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
279
extern void dump_subscript (FILE *, struct subscript *);
280
extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
281
extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
282
extern void dump_data_reference (FILE *, struct data_reference *);
283
extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
284
extern void debug_data_dependence_relation (struct data_dependence_relation *);
285
extern void dump_data_dependence_relation (FILE *,
286
                                           struct data_dependence_relation *);
287
extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
288
extern void dump_data_dependence_direction (FILE *,
289
                                            enum data_dependence_direction);
290
extern void free_dependence_relation (struct data_dependence_relation *);
291
extern void free_dependence_relations (VEC (ddr_p, heap) *);
292
extern void free_data_refs (VEC (data_reference_p, heap) *);
293
extern struct data_reference *analyze_array (tree, tree, bool);
294
extern void estimate_iters_using_array (tree, tree);
295
 
296
 
297
/* Return the index of the variable VAR in the LOOP_NEST array.  */
298
 
299
static inline int
300
index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest)
301
{
302
  struct loop *loopi;
303
  int var_index;
304
 
305
  for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi);
306
       var_index++)
307
    if (loopi->num == var)
308
      break;
309
 
310
  return var_index;
311
}
312
 
313
/* In lambda-code.c  */
314
bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
315
 
316
#endif  /* GCC_TREE_DATA_REF_H  */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.