1/* Data references and dependences detectors. 2 Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 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 110typedef struct data_reference *data_reference_p; 111DEF_VEC_P(data_reference_p); 112DEF_VEC_ALLOC_P (data_reference_p, heap); 113 114#define DR_STMT(DR) (DR)->stmt 115#define DR_REF(DR) (DR)->ref 116#define DR_BASE_OBJECT(DR) (DR)->object_info.base_object 117#define DR_TYPE(DR) (DR)->type 118#define DR_ACCESS_FNS(DR)\ 119 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ 120 (DR)->object_info.access_fns : (DR)->first_location.access_fns) 121#define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I) 122#define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR)) 123#define DR_IS_READ(DR) (DR)->is_read 124#define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address 125#define DR_OFFSET(DR) (DR)->first_location.offset 126#define DR_INIT(DR) (DR)->first_location.init 127#define DR_STEP(DR) (DR)->first_location.step 128#define DR_MEMTAG(DR) (DR)->memtag 129#define DR_ALIGNED_TO(DR) (DR)->aligned_to 130#define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment 131#define DR_PTR_INFO(DR) (DR)->ptr_info 132#define DR_SUBVARS(DR) (DR)->subvars 133 134#define DR_ACCESS_FNS_ADDR(DR) \ 135 (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ 136 &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns)) 137#define DR_SET_ACCESS_FNS(DR, ACC_FNS) \ 138{ \ 139 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ 140 (DR)->object_info.access_fns = ACC_FNS; \ 141 else \ 142 (DR)->first_location.access_fns = ACC_FNS; \ 143} 144#define DR_FREE_ACCESS_FNS(DR) \ 145{ \ 146 if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ 147 VEC_free (tree, heap, (DR)->object_info.access_fns); \ 148 else \ 149 VEC_free (tree, heap, (DR)->first_location.access_fns); \ 150} 151 152enum data_dependence_direction { 153 dir_positive, 154 dir_negative, 155 dir_equal, 156 dir_positive_or_negative, 157 dir_positive_or_equal, 158 dir_negative_or_equal, 159 dir_star, 160 dir_independent 161}; 162 163/* What is a subscript? Given two array accesses a subscript is the 164 tuple composed of the access functions for a given dimension. 165 Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three 166 subscripts: (f1, g1), (f2, g2), (f3, g3). These three subscripts 167 are stored in the data_dependence_relation structure under the form 168 of an array of subscripts. */ 169 170struct subscript 171{ 172 /* A description of the iterations for which the elements are 173 accessed twice. */ 174 tree conflicting_iterations_in_a; 175 tree conflicting_iterations_in_b; 176 177 /* This field stores the information about the iteration domain 178 validity of the dependence relation. */ 179 tree last_conflict; 180 181 /* Distance from the iteration that access a conflicting element in 182 A to the iteration that access this same conflicting element in 183 B. The distance is a tree scalar expression, i.e. a constant or a 184 symbolic expression, but certainly not a chrec function. */ 185 tree distance; 186}; 187 188typedef struct subscript *subscript_p; 189DEF_VEC_P(subscript_p); 190DEF_VEC_ALLOC_P (subscript_p, heap); 191 192#define SUB_CONFLICTS_IN_A(SUB) SUB->conflicting_iterations_in_a 193#define SUB_CONFLICTS_IN_B(SUB) SUB->conflicting_iterations_in_b 194#define SUB_LAST_CONFLICT(SUB) SUB->last_conflict 195#define SUB_DISTANCE(SUB) SUB->distance 196 197typedef struct loop *loop_p; 198DEF_VEC_P(loop_p); 199DEF_VEC_ALLOC_P (loop_p, heap); 200 201/* A data_dependence_relation represents a relation between two 202 data_references A and B. */ 203 204struct data_dependence_relation 205{ 206 207 struct data_reference *a; 208 struct data_reference *b; 209 210 /* When the dependence relation is affine, it can be represented by 211 a distance vector. */ 212 bool affine_p; 213 214 /* A "yes/no/maybe" field for the dependence relation: 215 216 - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence 217 relation between A and B, and the description of this relation 218 is given in the SUBSCRIPTS array, 219 220 - when "ARE_DEPENDENT == chrec_known", there is no dependence and 221 SUBSCRIPTS is empty, 222 223 - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, 224 but the analyzer cannot be more specific. */ 225 tree are_dependent; 226 227 /* For each subscript in the dependence test, there is an element in 228 this array. This is the attribute that labels the edge A->B of 229 the data_dependence_relation. */ 230 VEC (subscript_p, heap) *subscripts; 231 232 /* The analyzed loop nest. */ 233 VEC (loop_p, heap) *loop_nest; 234 235 /* The classic direction vector. */ 236 VEC (lambda_vector, heap) *dir_vects; 237 238 /* The classic distance vector. */ 239 VEC (lambda_vector, heap) *dist_vects; 240}; 241 242typedef struct data_dependence_relation *ddr_p; 243DEF_VEC_P(ddr_p); 244DEF_VEC_ALLOC_P(ddr_p,heap); 245 246#define DDR_A(DDR) DDR->a 247#define DDR_B(DDR) DDR->b 248#define DDR_AFFINE_P(DDR) DDR->affine_p 249#define DDR_ARE_DEPENDENT(DDR) DDR->are_dependent 250#define DDR_SUBSCRIPTS(DDR) DDR->subscripts 251#define DDR_SUBSCRIPT(DDR, I) VEC_index (subscript_p, DDR_SUBSCRIPTS (DDR), I) 252#define DDR_NUM_SUBSCRIPTS(DDR) VEC_length (subscript_p, DDR_SUBSCRIPTS (DDR)) 253 254#define DDR_LOOP_NEST(DDR) DDR->loop_nest 255/* The size of the direction/distance vectors: the number of loops in 256 the loop nest. */ 257#define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR))) 258 259#define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) 260#define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) 261#define DDR_NUM_DIST_VECTS(DDR) \ 262 (VEC_length (lambda_vector, DDR_DIST_VECTS (DDR))) 263#define DDR_NUM_DIR_VECTS(DDR) \ 264 (VEC_length (lambda_vector, DDR_DIR_VECTS (DDR))) 265#define DDR_DIR_VECT(DDR, I) \ 266 VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I) 267#define DDR_DIST_VECT(DDR, I) \ 268 VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I) 269 270 271 272extern tree find_data_references_in_loop (struct loop *, 273 VEC (data_reference_p, heap) **); 274extern void compute_data_dependences_for_loop (struct loop *, bool, 275 VEC (data_reference_p, heap) **, 276 VEC (ddr_p, heap) **); 277extern void print_direction_vector (FILE *, lambda_vector, int); 278extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int); 279extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int); 280extern void dump_subscript (FILE *, struct subscript *); 281extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *); 282extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *); 283extern void dump_data_reference (FILE *, struct data_reference *); 284extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *); 285extern void debug_data_dependence_relation (struct data_dependence_relation *); 286extern void dump_data_dependence_relation (FILE *, 287 struct data_dependence_relation *); 288extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *); 289extern void dump_data_dependence_direction (FILE *, 290 enum data_dependence_direction); 291extern void free_dependence_relation (struct data_dependence_relation *); 292extern void free_dependence_relations (VEC (ddr_p, heap) *); 293extern void free_data_refs (VEC (data_reference_p, heap) *); 294extern struct data_reference *analyze_array (tree, tree, bool); 295extern void estimate_iters_using_array (tree, tree); 296 297 298/* Return the index of the variable VAR in the LOOP_NEST array. */ 299 300static inline int 301index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest) 302{ 303 struct loop *loopi; 304 int var_index; 305 306 for (var_index = 0; VEC_iterate (loop_p, loop_nest, var_index, loopi); 307 var_index++) 308 if (loopi->num == var) 309 break; 310 311 return var_index; 312} 313 314/* In lambda-code.c */ 315bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *); 316 317#endif /* GCC_TREE_DATA_REF_H */ 318