Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-data-ref.h @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents a06113de4d67
children b7f97abdc517
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
1 /* Data references and dependences detectors. 1 /* Data references and dependences detectors.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc. 3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 4 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
5 5
6 This file is part of GCC. 6 This file is part of GCC.
30 /* 30 /*
31 innermost_loop_behavior describes the evolution of the address of the memory 31 innermost_loop_behavior describes the evolution of the address of the memory
32 reference in the innermost enclosing loop. The address is expressed as 32 reference in the innermost enclosing loop. The address is expressed as
33 BASE + STEP * # of iteration, and base is further decomposed as the base 33 BASE + STEP * # of iteration, and base is further decomposed as the base
34 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and 34 pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and
35 constant offset (INIT). Examples, in loop nest 35 constant offset (INIT). Examples, in loop nest
36 36
37 for (i = 0; i < 100; i++) 37 for (i = 0; i < 100; i++)
38 for (j = 3; j < 100; j++) 38 for (j = 3; j < 100; j++)
39 39
40 Example 1 Example 2 40 Example 1 Example 2
41 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j) 41 data-ref a[j].b[i][j] *(p + x + 16B + 4B * j)
42 42
43 43
44 innermost_loop_behavior 44 innermost_loop_behavior
45 base_address &a p 45 base_address &a p
46 offset i * D_i x 46 offset i * D_i x
47 init 3 * D_j + offsetof (b) 28 47 init 3 * D_j + offsetof (b) 28
77 77
78 struct indices 78 struct indices
79 { 79 {
80 /* The object. */ 80 /* The object. */
81 tree base_object; 81 tree base_object;
82 82
83 /* A list of chrecs. Access functions of the indices. */ 83 /* A list of chrecs. Access functions of the indices. */
84 VEC(tree,heap) *access_fns; 84 VEC(tree,heap) *access_fns;
85 }; 85 };
86 86
87 struct dr_alias 87 struct dr_alias
88 { 88 {
89 /* The alias information that should be used for new pointers to this 89 /* The alias information that should be used for new pointers to this
90 location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */ 90 location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */
91 tree symbol_tag;
92 struct ptr_info_def *ptr_info; 91 struct ptr_info_def *ptr_info;
93 92
94 /* The set of virtual operands corresponding to this memory reference, 93 /* The set of virtual operands corresponding to this memory reference,
95 serving as a description of the alias information for the memory 94 serving as a description of the alias information for the memory
96 reference. This could be eliminated if we had alias oracle. */ 95 reference. This could be eliminated if we had alias oracle. */
97 bitmap vops; 96 bitmap vops;
98 }; 97 };
99
100 typedef struct scop *scop_p;
101 98
102 /* Each vector of the access matrix represents a linear access 99 /* Each vector of the access matrix represents a linear access
103 function for a subscript. First elements correspond to the 100 function for a subscript. First elements correspond to the
104 leftmost indices, ie. for a[i][j] the first vector corresponds to 101 leftmost indices, ie. for a[i][j] the first vector corresponds to
105 the subscript in "i". The elements of a vector are relative to 102 the subscript in "i". The elements of a vector are relative to
111 108
112 | loop_1 109 | loop_1
113 | loop_2 110 | loop_2
114 | a[i+3][2*j+n-1] 111 | a[i+3][2*j+n-1]
115 112
116 if "i" varies in loop_1 and "j" varies in loop_2, the access 113 if "i" varies in loop_1 and "j" varies in loop_2, the access
117 matrix with respect to the loop nest {loop_1, loop_2} is: 114 matrix with respect to the loop nest {loop_1, loop_2} is:
118 115
119 | loop_1 loop_2 param_n cst 116 | loop_1 loop_2 param_n cst
120 | 1 0 0 3 117 | 1 0 0 3
121 | 0 2 1 -1 118 | 0 2 1 -1
164 161
165 struct data_reference 162 struct data_reference
166 { 163 {
167 /* A pointer to the statement that contains this DR. */ 164 /* A pointer to the statement that contains this DR. */
168 gimple stmt; 165 gimple stmt;
169 166
170 /* A pointer to the memory reference. */ 167 /* A pointer to the memory reference. */
171 tree ref; 168 tree ref;
172 169
173 /* Auxiliary info specific to a pass. */ 170 /* Auxiliary info specific to a pass. */
174 void *aux; 171 void *aux;
183 struct indices indices; 180 struct indices indices;
184 181
185 /* Alias information for the data reference. */ 182 /* Alias information for the data reference. */
186 struct dr_alias alias; 183 struct dr_alias alias;
187 184
188 /* The SCoP in which the data reference was analyzed. */
189 scop_p scop;
190
191 /* Matrix representation for the data access functions. */ 185 /* Matrix representation for the data access functions. */
192 struct access_matrix *access_matrix; 186 struct access_matrix *access_matrix;
193 }; 187 };
194 188
195 #define DR_SCOP(DR) (DR)->scop
196 #define DR_STMT(DR) (DR)->stmt 189 #define DR_STMT(DR) (DR)->stmt
197 #define DR_REF(DR) (DR)->ref 190 #define DR_REF(DR) (DR)->ref
198 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object 191 #define DR_BASE_OBJECT(DR) (DR)->indices.base_object
199 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns 192 #define DR_ACCESS_FNS(DR) (DR)->indices.access_fns
200 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I) 193 #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I)
201 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR)) 194 #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR))
202 #define DR_IS_READ(DR) (DR)->is_read 195 #define DR_IS_READ(DR) (DR)->is_read
203 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address 196 #define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address
204 #define DR_OFFSET(DR) (DR)->innermost.offset 197 #define DR_OFFSET(DR) (DR)->innermost.offset
205 #define DR_INIT(DR) (DR)->innermost.init 198 #define DR_INIT(DR) (DR)->innermost.init
206 #define DR_STEP(DR) (DR)->innermost.step 199 #define DR_STEP(DR) (DR)->innermost.step
207 #define DR_SYMBOL_TAG(DR) (DR)->alias.symbol_tag
208 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info 200 #define DR_PTR_INFO(DR) (DR)->alias.ptr_info
209 #define DR_VOPS(DR) (DR)->alias.vops
210 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to 201 #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to
211 #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix 202 #define DR_ACCESS_MATRIX(DR) (DR)->access_matrix
212 203
213 typedef struct data_reference *data_reference_p; 204 typedef struct data_reference *data_reference_p;
214 DEF_VEC_P(data_reference_p); 205 DEF_VEC_P(data_reference_p);
215 DEF_VEC_ALLOC_P (data_reference_p, heap); 206 DEF_VEC_ALLOC_P (data_reference_p, heap);
216 207
217 enum data_dependence_direction { 208 enum data_dependence_direction {
218 dir_positive, 209 dir_positive,
219 dir_negative, 210 dir_negative,
220 dir_equal, 211 dir_equal,
221 dir_positive_or_negative, 212 dir_positive_or_negative,
222 dir_positive_or_equal, 213 dir_positive_or_equal,
223 dir_negative_or_equal, 214 dir_negative_or_equal,
224 dir_star, 215 dir_star,
225 dir_independent 216 dir_independent
259 { 250 {
260 /* A description of the iterations for which the elements are 251 /* A description of the iterations for which the elements are
261 accessed twice. */ 252 accessed twice. */
262 conflict_function *conflicting_iterations_in_a; 253 conflict_function *conflicting_iterations_in_a;
263 conflict_function *conflicting_iterations_in_b; 254 conflict_function *conflicting_iterations_in_b;
264 255
265 /* This field stores the information about the iteration domain 256 /* This field stores the information about the iteration domain
266 validity of the dependence relation. */ 257 validity of the dependence relation. */
267 tree last_conflict; 258 tree last_conflict;
268 259
269 /* Distance from the iteration that access a conflicting element in 260 /* Distance from the iteration that access a conflicting element in
270 A to the iteration that access this same conflicting element in 261 A to the iteration that access this same conflicting element in
271 B. The distance is a tree scalar expression, i.e. a constant or a 262 B. The distance is a tree scalar expression, i.e. a constant or a
272 symbolic expression, but certainly not a chrec function. */ 263 symbolic expression, but certainly not a chrec function. */
273 tree distance; 264 tree distance;
285 /* A data_dependence_relation represents a relation between two 276 /* A data_dependence_relation represents a relation between two
286 data_references A and B. */ 277 data_references A and B. */
287 278
288 struct data_dependence_relation 279 struct data_dependence_relation
289 { 280 {
290 281
291 struct data_reference *a; 282 struct data_reference *a;
292 struct data_reference *b; 283 struct data_reference *b;
293 284
294 /* A "yes/no/maybe" field for the dependence relation: 285 /* A "yes/no/maybe" field for the dependence relation:
295 286
296 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 287 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence
297 relation between A and B, and the description of this relation 288 relation between A and B, and the description of this relation
298 is given in the SUBSCRIPTS array, 289 is given in the SUBSCRIPTS array,
299 290
300 - when "ARE_DEPENDENT == chrec_known", there is no dependence and 291 - when "ARE_DEPENDENT == chrec_known", there is no dependence and
301 SUBSCRIPTS is empty, 292 SUBSCRIPTS is empty,
302 293
303 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 294 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
304 but the analyzer cannot be more specific. */ 295 but the analyzer cannot be more specific. */
305 tree are_dependent; 296 tree are_dependent;
306 297
307 /* For each subscript in the dependence test, there is an element in 298 /* For each subscript in the dependence test, there is an element in
308 this array. This is the attribute that labels the edge A->B of 299 this array. This is the attribute that labels the edge A->B of
309 the data_dependence_relation. */ 300 the data_dependence_relation. */
310 VEC (subscript_p, heap) *subscripts; 301 VEC (subscript_p, heap) *subscripts;
311 302
384 bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **); 375 bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **);
385 bool dr_analyze_innermost (struct data_reference *); 376 bool dr_analyze_innermost (struct data_reference *);
386 extern bool compute_data_dependences_for_loop (struct loop *, bool, 377 extern bool compute_data_dependences_for_loop (struct loop *, bool,
387 VEC (data_reference_p, heap) **, 378 VEC (data_reference_p, heap) **,
388 VEC (ddr_p, heap) **); 379 VEC (ddr_p, heap) **);
389 extern tree find_data_references_in_loop (struct loop *, 380 extern bool compute_data_dependences_for_bb (basic_block, bool,
381 VEC (data_reference_p, heap) **,
382 VEC (ddr_p, heap) **);
383 extern tree find_data_references_in_loop (struct loop *,
390 VEC (data_reference_p, heap) **); 384 VEC (data_reference_p, heap) **);
391 extern void print_direction_vector (FILE *, lambda_vector, int); 385 extern void print_direction_vector (FILE *, lambda_vector, int);
392 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int); 386 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
393 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int); 387 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
394 extern void dump_subscript (FILE *, struct subscript *); 388 extern void dump_subscript (FILE *, struct subscript *);
395 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *); 389 extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *);
396 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *); 390 extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *);
397 extern void dump_data_reference (FILE *, struct data_reference *); 391 extern void dump_data_reference (FILE *, struct data_reference *);
392 extern void debug_data_reference (struct data_reference *);
398 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *); 393 extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *);
394 extern void debug_data_references (VEC (data_reference_p, heap) *);
399 extern void debug_data_dependence_relation (struct data_dependence_relation *); 395 extern void debug_data_dependence_relation (struct data_dependence_relation *);
400 extern void dump_data_dependence_relation (FILE *, 396 extern void dump_data_dependence_relation (FILE *,
401 struct data_dependence_relation *); 397 struct data_dependence_relation *);
402 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *); 398 extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *);
403 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *); 399 extern void debug_data_dependence_relations (VEC (ddr_p, heap) *);
404 extern void dump_data_dependence_direction (FILE *, 400 extern void dump_data_dependence_direction (FILE *,
405 enum data_dependence_direction); 401 enum data_dependence_direction);
406 extern void free_dependence_relation (struct data_dependence_relation *); 402 extern void free_dependence_relation (struct data_dependence_relation *);
407 extern void free_dependence_relations (VEC (ddr_p, heap) *); 403 extern void free_dependence_relations (VEC (ddr_p, heap) *);
408 extern void free_data_ref (data_reference_p); 404 extern void free_data_ref (data_reference_p);
409 extern void free_data_refs (VEC (data_reference_p, heap) *); 405 extern void free_data_refs (VEC (data_reference_p, heap) *);
410 extern bool find_data_references_in_stmt (struct loop *, gimple, 406 extern bool find_data_references_in_stmt (struct loop *, gimple,
411 VEC (data_reference_p, heap) **); 407 VEC (data_reference_p, heap) **);
408 extern bool graphite_find_data_references_in_stmt (struct loop *, gimple,
409 VEC (data_reference_p, heap) **);
412 struct data_reference *create_data_ref (struct loop *, tree, gimple, bool); 410 struct data_reference *create_data_ref (struct loop *, tree, gimple, bool);
413 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **); 411 extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
414 extern void compute_all_dependences (VEC (data_reference_p, heap) *, 412 extern void compute_all_dependences (VEC (data_reference_p, heap) *,
415 VEC (ddr_p, heap) **, VEC (loop_p, heap) *, 413 VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
416 bool); 414 bool);
417 415
418 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *); 416 extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *);
419 extern bool dr_may_alias_p (const struct data_reference *, 417 extern bool dr_may_alias_p (const struct data_reference *,
420 const struct data_reference *); 418 const struct data_reference *);
421 extern bool stmt_simple_memref_p (struct loop *, gimple, tree);
422 419
423 /* Return true when the DDR contains two data references that have the 420 /* Return true when the DDR contains two data references that have the
424 same access functions. */ 421 same access functions. */
425 422
426 static inline bool 423 static inline bool
505 void debug_rdg_vertex (struct graph *, int); 502 void debug_rdg_vertex (struct graph *, int);
506 void dump_rdg_component (FILE *, struct graph *, int, bitmap); 503 void dump_rdg_component (FILE *, struct graph *, int, bitmap);
507 void debug_rdg_component (struct graph *, int); 504 void debug_rdg_component (struct graph *, int);
508 void dump_rdg (FILE *, struct graph *); 505 void dump_rdg (FILE *, struct graph *);
509 void debug_rdg (struct graph *); 506 void debug_rdg (struct graph *);
510 void dot_rdg (struct graph *);
511 int rdg_vertex_for_stmt (struct graph *, gimple); 507 int rdg_vertex_for_stmt (struct graph *, gimple);
512 508
513 /* Data dependence type. */ 509 /* Data dependence type. */
514 510
515 enum rdg_dep_type 511 enum rdg_dep_type
516 { 512 {
517 /* Read After Write (RAW). */ 513 /* Read After Write (RAW). */
518 flow_dd = 'f', 514 flow_dd = 'f',
519 515
520 /* Write After Read (WAR). */ 516 /* Write After Read (WAR). */
521 anti_dd = 'a', 517 anti_dd = 'a',
522 518
523 /* Write After Write (WAW). */ 519 /* Write After Write (WAW). */
524 output_dd = 'o', 520 output_dd = 'o',
525 521
526 /* Read After Read (RAR). */ 522 /* Read After Read (RAR). */
527 input_dd = 'i' 523 input_dd = 'i'
528 }; 524 };
529 525
530 /* Dependence information attached to an edge of the RDG. */ 526 /* Dependence information attached to an edge of the RDG. */
531 527
532 typedef struct rdg_edge 528 typedef struct rdg_edge
533 { 529 {
534 /* Type of the dependence. */ 530 /* Type of the dependence. */
535 enum rdg_dep_type type; 531 enum rdg_dep_type type;
536 532
537 /* Levels of the dependence: the depth of the loops that carry the 533 /* Levels of the dependence: the depth of the loops that carry the